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