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 
15 namespace llvm {
16 
17 class MachineInstr;
18 class MachineFunction;
19 
20 // Worklist which mostly works similar to InstCombineWorkList, but on
21 // MachineInstrs. The main difference with something like a SetVector is that
22 // erasing an element doesn't move all elements over one place - instead just
23 // nulls out the element of the vector.
24 //
25 // FIXME: Does it make sense to factor out common code with the
26 // instcombinerWorkList?
27 template<unsigned N>
28 class GISelWorkList {
29   SmallVector<MachineInstr *, N> Worklist;
30   DenseMap<MachineInstr *, unsigned> WorklistMap;
31 
32 #ifndef NDEBUG
33   bool Finalized = true;
34 #endif
35 
36 public:
GISelWorkList()37   GISelWorkList() : WorklistMap(N) {}
38 
empty()39   bool empty() const { return WorklistMap.empty(); }
40 
size()41   unsigned size() const { return WorklistMap.size(); }
42 
43   // Since we don't know ahead of time how many instructions we're going to add
44   // to the worklist, and migrating densemap's elements is quite expensive
45   // everytime we resize, only insert to the smallvector (typically during the
46   // initial phase of populating lists). Before the worklist can be used,
47   // finalize should be called. Also assert with NDEBUG if list is ever used
48   // without finalizing. Note that unlike insert, we won't check for duplicates
49   // - so the ideal place to use this is during the initial prepopulating phase
50   // of most passes.
deferred_insert(MachineInstr * I)51   void deferred_insert(MachineInstr *I) {
52     Worklist.push_back(I);
53 #ifndef NDEBUG
54     Finalized = false;
55 #endif
56   }
57 
58   // This should only be called when using deferred_insert.
59   // This asserts that the WorklistMap is empty, and then
60   // inserts all the elements in the Worklist into the map.
61   // It also asserts if there are any duplicate elements found.
finalize()62   void finalize() {
63     assert(WorklistMap.empty() && "Expecting empty worklistmap");
64     if (Worklist.size() > N)
65       WorklistMap.reserve(Worklist.size());
66     for (unsigned i = 0; i < Worklist.size(); ++i)
67       if (!WorklistMap.try_emplace(Worklist[i], i).second)
68         llvm_unreachable("Duplicate elements in the list");
69 #ifndef NDEBUG
70     Finalized = true;
71 #endif
72   }
73 
74   /// Add the specified instruction to the worklist if it isn't already in it.
insert(MachineInstr * I)75   void insert(MachineInstr *I) {
76     assert(Finalized && "GISelWorkList used without finalizing");
77     if (WorklistMap.try_emplace(I, Worklist.size()).second)
78       Worklist.push_back(I);
79   }
80 
81   /// Remove I from the worklist if it exists.
remove(const MachineInstr * I)82   void remove(const MachineInstr *I) {
83     assert((Finalized || WorklistMap.empty()) && "Neither finalized nor empty");
84     auto It = WorklistMap.find(I);
85     if (It == WorklistMap.end())
86       return; // Not in worklist.
87 
88     // Don't bother moving everything down, just null out the slot.
89     Worklist[It->second] = nullptr;
90 
91     WorklistMap.erase(It);
92   }
93 
clear()94   void clear() {
95     Worklist.clear();
96     WorklistMap.clear();
97   }
98 
pop_back_val()99   MachineInstr *pop_back_val() {
100     assert(Finalized && "GISelWorkList used without finalizing");
101     MachineInstr *I;
102     do {
103       I = Worklist.pop_back_val();
104     } while(!I);
105     assert(I && "Pop back on empty worklist");
106     WorklistMap.erase(I);
107     return I;
108   }
109 };
110 
111 } // end namespace llvm.
112 
113 #endif
114