1 //=== InstructionWorklist.h - Worklist for InstCombine & others -*- 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_TRANSFORMS_UTILS_INSTRUCTIONWORKLIST_H
10 #define LLVM_TRANSFORMS_UTILS_INSTRUCTIONWORKLIST_H
11 
12 #include "llvm/ADT/DenseMap.h"
13 #include "llvm/ADT/STLExtras.h"
14 #include "llvm/ADT/SetVector.h"
15 #include "llvm/ADT/SmallVector.h"
16 #include "llvm/IR/Instruction.h"
17 #include "llvm/Support/Compiler.h"
18 #include "llvm/Support/Debug.h"
19 #include "llvm/Support/raw_ostream.h"
20 
21 namespace llvm {
22 
23 /// InstructionWorklist - This is the worklist management logic for
24 /// InstCombine and other simplification passes.
25 class InstructionWorklist {
26   SmallVector<Instruction *, 256> Worklist;
27   DenseMap<Instruction *, unsigned> WorklistMap;
28   /// These instructions will be added in reverse order after the current
29   /// combine has finished. This means that these instructions will be visited
30   /// in the order they have been added.
31   SmallSetVector<Instruction *, 16> Deferred;
32 
33 public:
34   InstructionWorklist() = default;
35 
36   InstructionWorklist(InstructionWorklist &&) = default;
37   InstructionWorklist &operator=(InstructionWorklist &&) = default;
38 
isEmpty()39   bool isEmpty() const { return Worklist.empty() && Deferred.empty(); }
40 
41   /// Add instruction to the worklist.
42   /// Instructions will be visited in the order they are added.
43   /// You likely want to use this method.
add(Instruction * I)44   void add(Instruction *I) {
45     if (Deferred.insert(I))
46       LLVM_DEBUG(dbgs() << "ADD DEFERRED: " << *I << '\n');
47   }
48 
49   /// Add value to the worklist if it is an instruction.
50   /// Instructions will be visited in the order they are added.
addValue(Value * V)51   void addValue(Value *V) {
52     if (Instruction *I = dyn_cast<Instruction>(V))
53       add(I);
54   }
55 
56   /// Push the instruction onto the worklist stack.
57   /// Instructions that have been added first will be visited last.
push(Instruction * I)58   void push(Instruction *I) {
59     assert(I);
60     assert(I->getParent() && "Instruction not inserted yet?");
61 
62     if (WorklistMap.insert(std::make_pair(I, Worklist.size())).second) {
63       LLVM_DEBUG(dbgs() << "ADD: " << *I << '\n');
64       Worklist.push_back(I);
65     }
66   }
67 
pushValue(Value * V)68   void pushValue(Value *V) {
69     if (Instruction *I = dyn_cast<Instruction>(V))
70       push(I);
71   }
72 
popDeferred()73   Instruction *popDeferred() {
74     if (Deferred.empty())
75       return nullptr;
76     return Deferred.pop_back_val();
77   }
78 
reserve(size_t Size)79   void reserve(size_t Size) {
80     Worklist.reserve(Size + 16);
81     WorklistMap.reserve(Size);
82   }
83 
84   /// Remove I from the worklist if it exists.
remove(Instruction * I)85   void remove(Instruction *I) {
86     DenseMap<Instruction *, unsigned>::iterator It = WorklistMap.find(I);
87     if (It != WorklistMap.end()) {
88       // Don't bother moving everything down, just null out the slot.
89       Worklist[It->second] = nullptr;
90       WorklistMap.erase(It);
91     }
92 
93     Deferred.remove(I);
94   }
95 
removeOne()96   Instruction *removeOne() {
97     if (Worklist.empty())
98       return nullptr;
99     Instruction *I = Worklist.pop_back_val();
100     WorklistMap.erase(I);
101     return I;
102   }
103 
104   /// When an instruction is simplified, add all users of the instruction
105   /// to the work lists because they might get more simplified now.
pushUsersToWorkList(Instruction & I)106   void pushUsersToWorkList(Instruction &I) {
107     for (User *U : I.users())
108       push(cast<Instruction>(U));
109   }
110 
111   /// Should be called *after* decrementing the use-count on V.
handleUseCountDecrement(Value * V)112   void handleUseCountDecrement(Value *V) {
113     if (auto *I = dyn_cast<Instruction>(V)) {
114       add(I);
115       // Many folds have one-use limitations. If there's only one use left,
116       // revisit that use.
117       if (I->hasOneUse())
118         add(cast<Instruction>(*I->user_begin()));
119     }
120   }
121 
122   /// Check that the worklist is empty and nuke the backing store for the map.
zap()123   void zap() {
124     assert(WorklistMap.empty() && "Worklist empty, but map not?");
125     assert(Deferred.empty() && "Deferred instructions left over");
126 
127     // Do an explicit clear, this shrinks the map if needed.
128     WorklistMap.clear();
129   }
130 };
131 
132 } // end namespace llvm.
133 
134 #endif
135