Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/include/llvm/CodeGen/GlobalISel/GISelWorkList.h
Line
Count
Source (jump to first uncovered line)
1
//===- GISelWorkList.h - Worklist for GISel passes ----*- C++ -*-===//
2
//
3
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4
// See https://llvm.org/LICENSE.txt for license information.
5
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6
//
7
//===----------------------------------------------------------------------===//
8
9
#ifndef LLVM_GISEL_WORKLIST_H
10
#define LLVM_GISEL_WORKLIST_H
11
12
#include "llvm/ADT/DenseMap.h"
13
#include "llvm/ADT/SmallVector.h"
14
#include "llvm/CodeGen/MachineBasicBlock.h"
15
#include "llvm/CodeGen/MachineInstr.h"
16
#include "llvm/Support/Debug.h"
17
18
namespace llvm {
19
20
class MachineInstr;
21
class MachineFunction;
22
23
// Worklist which mostly works similar to InstCombineWorkList, but on
24
// MachineInstrs. The main difference with something like a SetVector is that
25
// erasing an element doesn't move all elements over one place - instead just
26
// nulls out the element of the vector.
27
//
28
// FIXME: Does it make sense to factor out common code with the
29
// instcombinerWorkList?
30
template<unsigned N>
31
class GISelWorkList {
32
  SmallVector<MachineInstr *, N> Worklist;
33
  DenseMap<MachineInstr *, unsigned> WorklistMap;
34
35
#ifndef NDEBUG
36
  bool Finalized = true;
37
#endif
38
39
public:
40
863k
  GISelWorkList() : WorklistMap(N) {}
llvm::GISelWorkList<4u>::GISelWorkList()
Line
Count
Source
40
72
  GISelWorkList() : WorklistMap(N) {}
llvm::GISelWorkList<8u>::GISelWorkList()
Line
Count
Source
40
14.3k
  GISelWorkList() : WorklistMap(N) {}
llvm::GISelWorkList<512u>::GISelWorkList()
Line
Count
Source
40
369k
  GISelWorkList() : WorklistMap(N) {}
llvm::GISelWorkList<256u>::GISelWorkList()
Line
Count
Source
40
239k
  GISelWorkList() : WorklistMap(N) {}
llvm::GISelWorkList<128u>::GISelWorkList()
Line
Count
Source
40
239k
  GISelWorkList() : WorklistMap(N) {}
41
42
75.6M
  bool empty() const { return WorklistMap.empty(); }
llvm::GISelWorkList<4u>::empty() const
Line
Count
Source
42
321
  bool empty() const { return WorklistMap.empty(); }
llvm::GISelWorkList<8u>::empty() const
Line
Count
Source
42
16.9M
  bool empty() const { return WorklistMap.empty(); }
llvm::GISelWorkList<512u>::empty() const
Line
Count
Source
42
41.7M
  bool empty() const { return WorklistMap.empty(); }
llvm::GISelWorkList<256u>::empty() const
Line
Count
Source
42
14.6M
  bool empty() const { return WorklistMap.empty(); }
llvm::GISelWorkList<128u>::empty() const
Line
Count
Source
42
2.26M
  bool empty() const { return WorklistMap.empty(); }
43
44
  unsigned size() const { return WorklistMap.size(); }
45
46
  // Since we don't know ahead of time how many instructions we're going to add
47
  // to the worklist, and migrating densemap's elements is quite expensive
48
  // everytime we resize, only insert to the smallvector (typically during the
49
  // initial phase of populating lists). Before the worklist can be used,
50
  // finalize should be called. Also assert with NDEBUG if list is ever used
51
  // without finalizing. Note that unlike insert, we won't check for duplicates
52
  // - so the ideal place to use this is during the initial prepopulating phase
53
  // of most passes.
54
52.8M
  void deferred_insert(MachineInstr *I) {
55
52.8M
    Worklist.push_back(I);
56
#ifndef NDEBUG
57
    Finalized = false;
58
#endif
59
  }
llvm::GISelWorkList<512u>::deferred_insert(llvm::MachineInstr*)
Line
Count
Source
54
40.6M
  void deferred_insert(MachineInstr *I) {
55
40.6M
    Worklist.push_back(I);
56
#ifndef NDEBUG
57
    Finalized = false;
58
#endif
59
  }
llvm::GISelWorkList<128u>::deferred_insert(llvm::MachineInstr*)
Line
Count
Source
54
436k
  void deferred_insert(MachineInstr *I) {
55
436k
    Worklist.push_back(I);
56
#ifndef NDEBUG
57
    Finalized = false;
58
#endif
59
  }
llvm::GISelWorkList<256u>::deferred_insert(llvm::MachineInstr*)
Line
Count
Source
54
11.7M
  void deferred_insert(MachineInstr *I) {
55
11.7M
    Worklist.push_back(I);
56
#ifndef NDEBUG
57
    Finalized = false;
58
#endif
59
  }
60
61
  // This should only be called when using deferred_insert.
62
  // This asserts that the WorklistMap is empty, and then
63
  // inserts all the elements in the Worklist into the map.
64
  // It also asserts if there are any duplicate elements found.
65
849k
  void finalize() {
66
849k
    assert(WorklistMap.empty() && "Expecting empty worklistmap");
67
849k
    if (Worklist.size() > N)
68
21.9k
      WorklistMap.reserve(Worklist.size());
69
53.6M
    for (unsigned i = 0; i < Worklist.size(); 
++i52.8M
)
70
52.8M
      if (!WorklistMap.try_emplace(Worklist[i], i).second)
71
52.8M
        
llvm_unreachable0
("Duplicate elements in the list");
72
#ifndef NDEBUG
73
    Finalized = true;
74
#endif
75
  }
llvm::GISelWorkList<512u>::finalize()
Line
Count
Source
65
369k
  void finalize() {
66
369k
    assert(WorklistMap.empty() && "Expecting empty worklistmap");
67
369k
    if (Worklist.size() > N)
68
13.1k
      WorklistMap.reserve(Worklist.size());
69
40.9M
    for (unsigned i = 0; i < Worklist.size(); 
++i40.6M
)
70
40.6M
      if (!WorklistMap.try_emplace(Worklist[i], i).second)
71
40.6M
        
llvm_unreachable0
("Duplicate elements in the list");
72
#ifndef NDEBUG
73
    Finalized = true;
74
#endif
75
  }
llvm::GISelWorkList<128u>::finalize()
Line
Count
Source
65
239k
  void finalize() {
66
239k
    assert(WorklistMap.empty() && "Expecting empty worklistmap");
67
239k
    if (Worklist.size() > N)
68
122
      WorklistMap.reserve(Worklist.size());
69
676k
    for (unsigned i = 0; i < Worklist.size(); 
++i436k
)
70
436k
      if (!WorklistMap.try_emplace(Worklist[i], i).second)
71
436k
        
llvm_unreachable0
("Duplicate elements in the list");
72
#ifndef NDEBUG
73
    Finalized = true;
74
#endif
75
  }
llvm::GISelWorkList<256u>::finalize()
Line
Count
Source
65
239k
  void finalize() {
66
239k
    assert(WorklistMap.empty() && "Expecting empty worklistmap");
67
239k
    if (Worklist.size() > N)
68
8.72k
      WorklistMap.reserve(Worklist.size());
69
12.0M
    for (unsigned i = 0; i < Worklist.size(); 
++i11.7M
)
70
11.7M
      if (!WorklistMap.try_emplace(Worklist[i], i).second)
71
11.7M
        
llvm_unreachable0
("Duplicate elements in the list");
72
#ifndef NDEBUG
73
    Finalized = true;
74
#endif
75
  }
76
77
  /// Add the specified instruction to the worklist if it isn't already in it.
78
19.0M
  void insert(MachineInstr *I) {
79
19.0M
    assert(Finalized && "GISelWorkList used without finalizing");
80
19.0M
    if (WorklistMap.try_emplace(I, Worklist.size()).second)
81
12.0M
      Worklist.push_back(I);
82
19.0M
  }
llvm::GISelWorkList<4u>::insert(llvm::MachineInstr*)
Line
Count
Source
78
268
  void insert(MachineInstr *I) {
79
268
    assert(Finalized && "GISelWorkList used without finalizing");
80
268
    if (WorklistMap.try_emplace(I, Worklist.size()).second)
81
268
      Worklist.push_back(I);
82
268
  }
llvm::GISelWorkList<8u>::insert(llvm::MachineInstr*)
Line
Count
Source
78
8.40M
  void insert(MachineInstr *I) {
79
8.40M
    assert(Finalized && "GISelWorkList used without finalizing");
80
8.40M
    if (WorklistMap.try_emplace(I, Worklist.size()).second)
81
6.27M
      Worklist.push_back(I);
82
8.40M
  }
llvm::GISelWorkList<512u>::insert(llvm::MachineInstr*)
Line
Count
Source
78
3.60M
  void insert(MachineInstr *I) {
79
3.60M
    assert(Finalized && "GISelWorkList used without finalizing");
80
3.60M
    if (WorklistMap.try_emplace(I, Worklist.size()).second)
81
922k
      Worklist.push_back(I);
82
3.60M
  }
llvm::GISelWorkList<128u>::insert(llvm::MachineInstr*)
Line
Count
Source
78
3.54M
  void insert(MachineInstr *I) {
79
3.54M
    assert(Finalized && "GISelWorkList used without finalizing");
80
3.54M
    if (WorklistMap.try_emplace(I, Worklist.size()).second)
81
1.77M
      Worklist.push_back(I);
82
3.54M
  }
llvm::GISelWorkList<256u>::insert(llvm::MachineInstr*)
Line
Count
Source
78
3.48M
  void insert(MachineInstr *I) {
79
3.48M
    assert(Finalized && "GISelWorkList used without finalizing");
80
3.48M
    if (WorklistMap.try_emplace(I, Worklist.size()).second)
81
3.10M
      Worklist.push_back(I);
82
3.48M
  }
83
84
  /// Remove I from the worklist if it exists.
85
19.3M
  void remove(const MachineInstr *I) {
86
19.3M
    assert((Finalized || WorklistMap.empty()) && "Neither finalized nor empty");
87
19.3M
    auto It = WorklistMap.find(I);
88
19.3M
    if (It == WorklistMap.end())
89
12.9M
      return; // Not in worklist.
90
6.36M
91
6.36M
    // Don't bother moving everything down, just null out the slot.
92
6.36M
    Worklist[It->second] = nullptr;
93
6.36M
94
6.36M
    WorklistMap.erase(It);
95
6.36M
  }
llvm::GISelWorkList<8u>::remove(llvm::MachineInstr const*)
Line
Count
Source
85
14.4M
  void remove(const MachineInstr *I) {
86
14.4M
    assert((Finalized || WorklistMap.empty()) && "Neither finalized nor empty");
87
14.4M
    auto It = WorklistMap.find(I);
88
14.4M
    if (It == WorklistMap.end())
89
8.44M
      return; // Not in worklist.
90
6.01M
91
6.01M
    // Don't bother moving everything down, just null out the slot.
92
6.01M
    Worklist[It->second] = nullptr;
93
6.01M
94
6.01M
    WorklistMap.erase(It);
95
6.01M
  }
llvm::GISelWorkList<512u>::remove(llvm::MachineInstr const*)
Line
Count
Source
85
1.66M
  void remove(const MachineInstr *I) {
86
1.66M
    assert((Finalized || WorklistMap.empty()) && "Neither finalized nor empty");
87
1.66M
    auto It = WorklistMap.find(I);
88
1.66M
    if (It == WorklistMap.end())
89
1.54M
      return; // Not in worklist.
90
121k
91
121k
    // Don't bother moving everything down, just null out the slot.
92
121k
    Worklist[It->second] = nullptr;
93
121k
94
121k
    WorklistMap.erase(It);
95
121k
  }
llvm::GISelWorkList<256u>::remove(llvm::MachineInstr const*)
Line
Count
Source
85
1.61M
  void remove(const MachineInstr *I) {
86
1.61M
    assert((Finalized || WorklistMap.empty()) && "Neither finalized nor empty");
87
1.61M
    auto It = WorklistMap.find(I);
88
1.61M
    if (It == WorklistMap.end())
89
1.61M
      return; // Not in worklist.
90
401
91
401
    // Don't bother moving everything down, just null out the slot.
92
401
    Worklist[It->second] = nullptr;
93
401
94
401
    WorklistMap.erase(It);
95
401
  }
llvm::GISelWorkList<128u>::remove(llvm::MachineInstr const*)
Line
Count
Source
85
1.61M
  void remove(const MachineInstr *I) {
86
1.61M
    assert((Finalized || WorklistMap.empty()) && "Neither finalized nor empty");
87
1.61M
    auto It = WorklistMap.find(I);
88
1.61M
    if (It == WorklistMap.end())
89
1.38M
      return; // Not in worklist.
90
233k
91
233k
    // Don't bother moving everything down, just null out the slot.
92
233k
    Worklist[It->second] = nullptr;
93
233k
94
233k
    WorklistMap.erase(It);
95
233k
  }
96
97
955k
  void clear() {
98
955k
    Worklist.clear();
99
955k
    WorklistMap.clear();
100
955k
  }
101
102
57.4M
  MachineInstr *pop_back_val() {
103
57.4M
    assert(Finalized && "GISelWorkList used without finalizing");
104
57.4M
    MachineInstr *I;
105
57.7M
    do {
106
57.7M
      I = Worklist.pop_back_val();
107
57.7M
    } while(!I);
108
57.4M
    assert(I && "Pop back on empty worklist");
109
57.4M
    WorklistMap.erase(I);
110
57.4M
    return I;
111
57.4M
  }
llvm::GISelWorkList<4u>::pop_back_val()
Line
Count
Source
102
268
  MachineInstr *pop_back_val() {
103
268
    assert(Finalized && "GISelWorkList used without finalizing");
104
268
    MachineInstr *I;
105
268
    do {
106
268
      I = Worklist.pop_back_val();
107
268
    } while(!I);
108
268
    assert(I && "Pop back on empty worklist");
109
268
    WorklistMap.erase(I);
110
268
    return I;
111
268
  }
llvm::GISelWorkList<8u>::pop_back_val()
Line
Count
Source
102
265k
  MachineInstr *pop_back_val() {
103
265k
    assert(Finalized && "GISelWorkList used without finalizing");
104
265k
    MachineInstr *I;
105
265k
    do {
106
265k
      I = Worklist.pop_back_val();
107
265k
    } while(!I);
108
265k
    assert(I && "Pop back on empty worklist");
109
265k
    WorklistMap.erase(I);
110
265k
    return I;
111
265k
  }
llvm::GISelWorkList<512u>::pop_back_val()
Line
Count
Source
102
41.4M
  MachineInstr *pop_back_val() {
103
41.4M
    assert(Finalized && "GISelWorkList used without finalizing");
104
41.4M
    MachineInstr *I;
105
41.5M
    do {
106
41.5M
      I = Worklist.pop_back_val();
107
41.5M
    } while(!I);
108
41.4M
    assert(I && "Pop back on empty worklist");
109
41.4M
    WorklistMap.erase(I);
110
41.4M
    return I;
111
41.4M
  }
llvm::GISelWorkList<256u>::pop_back_val()
Line
Count
Source
102
13.9M
  MachineInstr *pop_back_val() {
103
13.9M
    assert(Finalized && "GISelWorkList used without finalizing");
104
13.9M
    MachineInstr *I;
105
13.9M
    do {
106
13.9M
      I = Worklist.pop_back_val();
107
13.9M
    } while(!I);
108
13.9M
    assert(I && "Pop back on empty worklist");
109
13.9M
    WorklistMap.erase(I);
110
13.9M
    return I;
111
13.9M
  }
llvm::GISelWorkList<128u>::pop_back_val()
Line
Count
Source
102
1.88M
  MachineInstr *pop_back_val() {
103
1.88M
    assert(Finalized && "GISelWorkList used without finalizing");
104
1.88M
    MachineInstr *I;
105
2.09M
    do {
106
2.09M
      I = Worklist.pop_back_val();
107
2.09M
    } while(!I);
108
1.88M
    assert(I && "Pop back on empty worklist");
109
1.88M
    WorklistMap.erase(I);
110
1.88M
    return I;
111
1.88M
  }
112
};
113
114
} // end namespace llvm.
115
116
#endif