Coverage Report

Created: 2019-02-20 00:17

/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
748k
  GISelWorkList() : WorklistMap(N) {}
llvm::GISelWorkList<8u>::GISelWorkList()
Line
Count
Source
40
14.0k
  GISelWorkList() : WorklistMap(N) {}
llvm::GISelWorkList<512u>::GISelWorkList()
Line
Count
Source
40
261k
  GISelWorkList() : WorklistMap(N) {}
llvm::GISelWorkList<256u>::GISelWorkList()
Line
Count
Source
40
236k
  GISelWorkList() : WorklistMap(N) {}
llvm::GISelWorkList<128u>::GISelWorkList()
Line
Count
Source
40
236k
  GISelWorkList() : WorklistMap(N) {}
41
42
62.3M
  bool empty() const { return WorklistMap.empty(); }
llvm::GISelWorkList<8u>::empty() const
Line
Count
Source
42
15.1M
  bool empty() const { return WorklistMap.empty(); }
llvm::GISelWorkList<512u>::empty() const
Line
Count
Source
42
31.0M
  bool empty() const { return WorklistMap.empty(); }
llvm::GISelWorkList<256u>::empty() const
Line
Count
Source
42
13.8M
  bool empty() const { return WorklistMap.empty(); }
llvm::GISelWorkList<128u>::empty() const
Line
Count
Source
42
2.19M
  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
42.6M
  void deferred_insert(MachineInstr *I) {
55
42.6M
    Worklist.push_back(I);
56
42.6M
#ifndef NDEBUG
57
42.6M
    Finalized = false;
58
42.6M
#endif
59
42.6M
  }
llvm::GISelWorkList<512u>::deferred_insert(llvm::MachineInstr*)
Line
Count
Source
54
30.7M
  void deferred_insert(MachineInstr *I) {
55
30.7M
    Worklist.push_back(I);
56
30.7M
#ifndef NDEBUG
57
30.7M
    Finalized = false;
58
30.7M
#endif
59
30.7M
  }
llvm::GISelWorkList<128u>::deferred_insert(llvm::MachineInstr*)
Line
Count
Source
54
478k
  void deferred_insert(MachineInstr *I) {
55
478k
    Worklist.push_back(I);
56
478k
#ifndef NDEBUG
57
478k
    Finalized = false;
58
478k
#endif
59
478k
  }
llvm::GISelWorkList<256u>::deferred_insert(llvm::MachineInstr*)
Line
Count
Source
54
11.3M
  void deferred_insert(MachineInstr *I) {
55
11.3M
    Worklist.push_back(I);
56
11.3M
#ifndef NDEBUG
57
11.3M
    Finalized = false;
58
11.3M
#endif
59
11.3M
  }
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
734k
  void finalize() {
66
734k
    assert(WorklistMap.empty() && "Expecting empty worklistmap");
67
734k
    if (Worklist.size() > N)
68
23.5k
      WorklistMap.reserve(Worklist.size());
69
43.3M
    for (unsigned i = 0; i < Worklist.size(); 
++i42.6M
)
70
42.6M
      if (!WorklistMap.try_emplace(Worklist[i], i).second)
71
42.6M
        
llvm_unreachable0
("Duplicate elements in the list");
72
734k
#ifndef NDEBUG
73
734k
    Finalized = true;
74
734k
#endif
75
734k
  }
llvm::GISelWorkList<512u>::finalize()
Line
Count
Source
65
261k
  void finalize() {
66
261k
    assert(WorklistMap.empty() && "Expecting empty worklistmap");
67
261k
    if (Worklist.size() > N)
68
14.8k
      WorklistMap.reserve(Worklist.size());
69
31.0M
    for (unsigned i = 0; i < Worklist.size(); 
++i30.7M
)
70
30.7M
      if (!WorklistMap.try_emplace(Worklist[i], i).second)
71
30.7M
        
llvm_unreachable0
("Duplicate elements in the list");
72
261k
#ifndef NDEBUG
73
261k
    Finalized = true;
74
261k
#endif
75
261k
  }
llvm::GISelWorkList<128u>::finalize()
Line
Count
Source
65
236k
  void finalize() {
66
236k
    assert(WorklistMap.empty() && "Expecting empty worklistmap");
67
236k
    if (Worklist.size() > N)
68
133
      WorklistMap.reserve(Worklist.size());
69
714k
    for (unsigned i = 0; i < Worklist.size(); 
++i478k
)
70
478k
      if (!WorklistMap.try_emplace(Worklist[i], i).second)
71
478k
        
llvm_unreachable0
("Duplicate elements in the list");
72
236k
#ifndef NDEBUG
73
236k
    Finalized = true;
74
236k
#endif
75
236k
  }
llvm::GISelWorkList<256u>::finalize()
Line
Count
Source
65
236k
  void finalize() {
66
236k
    assert(WorklistMap.empty() && "Expecting empty worklistmap");
67
236k
    if (Worklist.size() > N)
68
8.51k
      WorklistMap.reserve(Worklist.size());
69
11.6M
    for (unsigned i = 0; i < Worklist.size(); 
++i11.3M
)
70
11.3M
      if (!WorklistMap.try_emplace(Worklist[i], i).second)
71
11.3M
        
llvm_unreachable0
("Duplicate elements in the list");
72
236k
#ifndef NDEBUG
73
236k
    Finalized = true;
74
236k
#endif
75
236k
  }
76
77
  /// Add the specified instruction to the worklist if it isn't already in it.
78
16.7M
  void insert(MachineInstr *I) {
79
16.7M
    assert(Finalized && "GISelWorkList used without finalizing");
80
16.7M
    if (WorklistMap.try_emplace(I, Worklist.size()).second)
81
11.6M
      Worklist.push_back(I);
82
16.7M
  }
llvm::GISelWorkList<8u>::insert(llvm::MachineInstr*)
Line
Count
Source
78
8.29M
  void insert(MachineInstr *I) {
79
8.29M
    assert(Finalized && "GISelWorkList used without finalizing");
80
8.29M
    if (WorklistMap.try_emplace(I, Worklist.size()).second)
81
6.00M
      Worklist.push_back(I);
82
8.29M
  }
llvm::GISelWorkList<512u>::insert(llvm::MachineInstr*)
Line
Count
Source
78
408k
  void insert(MachineInstr *I) {
79
408k
    assert(Finalized && "GISelWorkList used without finalizing");
80
408k
    if (WorklistMap.try_emplace(I, Worklist.size()).second)
81
171k
      Worklist.push_back(I);
82
408k
  }
llvm::GISelWorkList<128u>::insert(llvm::MachineInstr*)
Line
Count
Source
78
3.82M
  void insert(MachineInstr *I) {
79
3.82M
    assert(Finalized && "GISelWorkList used without finalizing");
80
3.82M
    if (WorklistMap.try_emplace(I, Worklist.size()).second)
81
1.91M
      Worklist.push_back(I);
82
3.82M
  }
llvm::GISelWorkList<256u>::insert(llvm::MachineInstr*)
Line
Count
Source
78
4.16M
  void insert(MachineInstr *I) {
79
4.16M
    assert(Finalized && "GISelWorkList used without finalizing");
80
4.16M
    if (WorklistMap.try_emplace(I, Worklist.size()).second)
81
3.53M
      Worklist.push_back(I);
82
4.16M
  }
83
84
  /// Remove I from the worklist if it exists.
85
16.6M
  void remove(const MachineInstr *I) {
86
16.6M
    assert((Finalized || WorklistMap.empty()) && "Neither finalized nor empty");
87
16.6M
    auto It = WorklistMap.find(I);
88
16.6M
    if (It == WorklistMap.end())
89
11.1M
      return; // Not in worklist.
90
5.53M
91
5.53M
    // Don't bother moving everything down, just null out the slot.
92
5.53M
    Worklist[It->second] = nullptr;
93
5.53M
94
5.53M
    WorklistMap.erase(It);
95
5.53M
  }
llvm::GISelWorkList<8u>::remove(llvm::MachineInstr const*)
Line
Count
Source
85
13.2M
  void remove(const MachineInstr *I) {
86
13.2M
    assert((Finalized || WorklistMap.empty()) && "Neither finalized nor empty");
87
13.2M
    auto It = WorklistMap.find(I);
88
13.2M
    if (It == WorklistMap.end())
89
8.24M
      return; // Not in worklist.
90
5.03M
91
5.03M
    // Don't bother moving everything down, just null out the slot.
92
5.03M
    Worklist[It->second] = nullptr;
93
5.03M
94
5.03M
    WorklistMap.erase(It);
95
5.03M
  }
llvm::GISelWorkList<512u>::remove(llvm::MachineInstr const*)
Line
Count
Source
85
623k
  void remove(const MachineInstr *I) {
86
623k
    assert((Finalized || WorklistMap.empty()) && "Neither finalized nor empty");
87
623k
    auto It = WorklistMap.find(I);
88
623k
    if (It == WorklistMap.end())
89
494k
      return; // Not in worklist.
90
129k
91
129k
    // Don't bother moving everything down, just null out the slot.
92
129k
    Worklist[It->second] = nullptr;
93
129k
94
129k
    WorklistMap.erase(It);
95
129k
  }
llvm::GISelWorkList<256u>::remove(llvm::MachineInstr const*)
Line
Count
Source
85
1.39M
  void remove(const MachineInstr *I) {
86
1.39M
    assert((Finalized || WorklistMap.empty()) && "Neither finalized nor empty");
87
1.39M
    auto It = WorklistMap.find(I);
88
1.39M
    if (It == WorklistMap.end())
89
1.38M
      return; // Not in worklist.
90
3.84k
91
3.84k
    // Don't bother moving everything down, just null out the slot.
92
3.84k
    Worklist[It->second] = nullptr;
93
3.84k
94
3.84k
    WorklistMap.erase(It);
95
3.84k
  }
llvm::GISelWorkList<128u>::remove(llvm::MachineInstr const*)
Line
Count
Source
85
1.39M
  void remove(const MachineInstr *I) {
86
1.39M
    assert((Finalized || WorklistMap.empty()) && "Neither finalized nor empty");
87
1.39M
    auto It = WorklistMap.find(I);
88
1.39M
    if (It == WorklistMap.end())
89
1.02M
      return; // Not in worklist.
90
364k
91
364k
    // Don't bother moving everything down, just null out the slot.
92
364k
    Worklist[It->second] = nullptr;
93
364k
94
364k
    WorklistMap.erase(It);
95
364k
  }
96
97
949k
  void clear() {
98
949k
    Worklist.clear();
99
949k
    WorklistMap.clear();
100
949k
  }
101
102
46.6M
  MachineInstr *pop_back_val() {
103
46.6M
    assert(Finalized && "GISelWorkList used without finalizing");
104
46.6M
    MachineInstr *I;
105
47.1M
    do {
106
47.1M
      I = Worklist.pop_back_val();
107
47.1M
    } while(!I);
108
46.6M
    assert(I && "Pop back on empty worklist");
109
46.6M
    WorklistMap.erase(I);
110
46.6M
    return I;
111
46.6M
  }
llvm::GISelWorkList<8u>::pop_back_val()
Line
Count
Source
102
915k
  MachineInstr *pop_back_val() {
103
915k
    assert(Finalized && "GISelWorkList used without finalizing");
104
915k
    MachineInstr *I;
105
915k
    do {
106
915k
      I = Worklist.pop_back_val();
107
915k
    } while(!I);
108
915k
    assert(I && "Pop back on empty worklist");
109
915k
    WorklistMap.erase(I);
110
915k
    return I;
111
915k
  }
llvm::GISelWorkList<512u>::pop_back_val()
Line
Count
Source
102
30.8M
  MachineInstr *pop_back_val() {
103
30.8M
    assert(Finalized && "GISelWorkList used without finalizing");
104
30.8M
    MachineInstr *I;
105
30.9M
    do {
106
30.9M
      I = Worklist.pop_back_val();
107
30.9M
    } while(!I);
108
30.8M
    assert(I && "Pop back on empty worklist");
109
30.8M
    WorklistMap.erase(I);
110
30.8M
    return I;
111
30.8M
  }
llvm::GISelWorkList<256u>::pop_back_val()
Line
Count
Source
102
13.1M
  MachineInstr *pop_back_val() {
103
13.1M
    assert(Finalized && "GISelWorkList used without finalizing");
104
13.1M
    MachineInstr *I;
105
13.1M
    do {
106
13.1M
      I = Worklist.pop_back_val();
107
13.1M
    } while(!I);
108
13.1M
    assert(I && "Pop back on empty worklist");
109
13.1M
    WorklistMap.erase(I);
110
13.1M
    return I;
111
13.1M
  }
llvm::GISelWorkList<128u>::pop_back_val()
Line
Count
Source
102
1.81M
  MachineInstr *pop_back_val() {
103
1.81M
    assert(Finalized && "GISelWorkList used without finalizing");
104
1.81M
    MachineInstr *I;
105
2.14M
    do {
106
2.14M
      I = Worklist.pop_back_val();
107
2.14M
    } while(!I);
108
1.81M
    assert(I && "Pop back on empty worklist");
109
1.81M
    WorklistMap.erase(I);
110
1.81M
    return I;
111
1.81M
  }
112
};
113
114
} // end namespace llvm.
115
116
#endif