1 | //===- GVN.h - Eliminate redundant values and loads -------------*- C++ -*-===// |
2 | // |
3 | // The LLVM Compiler Infrastructure |
4 | // |
5 | // This file is distributed under the University of Illinois Open Source |
6 | // License. See LICENSE.TXT for details. |
7 | // |
8 | //===----------------------------------------------------------------------===// |
9 | /// \file |
10 | /// This file provides the interface for LLVM's Global Value Numbering pass |
11 | /// which eliminates fully redundant instructions. It also does somewhat Ad-Hoc |
12 | /// PRE and dead load elimination. |
13 | /// |
14 | //===----------------------------------------------------------------------===// |
15 | |
16 | #ifndef LLVM_TRANSFORMS_SCALAR_GVN_H |
17 | #define LLVM_TRANSFORMS_SCALAR_GVN_H |
18 | |
19 | #include "llvm/ADT/DenseMap.h" |
20 | #include "llvm/ADT/MapVector.h" |
21 | #include "llvm/ADT/PostOrderIterator.h" |
22 | #include "llvm/ADT/SetVector.h" |
23 | #include "llvm/ADT/SmallVector.h" |
24 | #include "llvm/Analysis/AliasAnalysis.h" |
25 | #include "llvm/Analysis/InstructionPrecedenceTracking.h" |
26 | #include "llvm/Analysis/MemoryDependenceAnalysis.h" |
27 | #include "llvm/IR/Dominators.h" |
28 | #include "llvm/IR/InstrTypes.h" |
29 | #include "llvm/IR/PassManager.h" |
30 | #include "llvm/IR/ValueHandle.h" |
31 | #include "llvm/Support/Allocator.h" |
32 | #include "llvm/Support/Compiler.h" |
33 | #include <cstdint> |
34 | #include <utility> |
35 | #include <vector> |
36 | |
37 | namespace llvm { |
38 | |
39 | class AssumptionCache; |
40 | class BasicBlock; |
41 | class BranchInst; |
42 | class CallInst; |
43 | class Constant; |
44 | class ; |
45 | class Function; |
46 | class FunctionPass; |
47 | class IntrinsicInst; |
48 | class LoadInst; |
49 | class LoopInfo; |
50 | class ; |
51 | class PHINode; |
52 | class TargetLibraryInfo; |
53 | class Value; |
54 | |
55 | /// A private "module" namespace for types and utilities used by GVN. These |
56 | /// are implementation details and should not be used by clients. |
57 | namespace gvn LLVM_LIBRARY_VISIBILITY { |
58 | |
59 | struct AvailableValue; |
60 | struct AvailableValueInBlock; |
61 | class GVNLegacyPass; |
62 | |
63 | } // end namespace gvn |
64 | |
65 | /// The core GVN pass object. |
66 | /// |
67 | /// FIXME: We should have a good summary of the GVN algorithm implemented by |
68 | /// this particular pass here. |
69 | class GVN : public PassInfoMixin<GVN> { |
70 | public: |
71 | struct Expression; |
72 | |
73 | /// Run the pass over the function. |
74 | PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); |
75 | |
76 | /// This removes the specified instruction from |
77 | /// our various maps and marks it for deletion. |
78 | void markInstructionForDeletion(Instruction *I) { |
79 | VN.erase(I); |
80 | InstrsToErase.push_back(I); |
81 | } |
82 | |
83 | DominatorTree &getDominatorTree() const { return *DT; } |
84 | AliasAnalysis *getAliasAnalysis() const { return VN.getAliasAnalysis(); } |
85 | MemoryDependenceResults &getMemDep() const { return *MD; } |
86 | |
87 | /// This class holds the mapping between values and value numbers. It is used |
88 | /// as an efficient mechanism to determine the expression-wise equivalence of |
89 | /// two values. |
90 | class ValueTable { |
91 | DenseMap<Value *, uint32_t> valueNumbering; |
92 | DenseMap<Expression, uint32_t> expressionNumbering; |
93 | |
94 | // Expressions is the vector of Expression. ExprIdx is the mapping from |
95 | // value number to the index of Expression in Expressions. We use it |
96 | // instead of a DenseMap because filling such mapping is faster than |
97 | // filling a DenseMap and the compile time is a little better. |
98 | uint32_t nextExprNumber; |
99 | |
100 | std::vector<Expression> Expressions; |
101 | std::vector<uint32_t> ExprIdx; |
102 | |
103 | // Value number to PHINode mapping. Used for phi-translate in scalarpre. |
104 | DenseMap<uint32_t, PHINode *> NumberingPhi; |
105 | |
106 | // Cache for phi-translate in scalarpre. |
107 | using PhiTranslateMap = |
108 | DenseMap<std::pair<uint32_t, const BasicBlock *>, uint32_t>; |
109 | PhiTranslateMap PhiTranslateTable; |
110 | |
111 | AliasAnalysis *AA; |
112 | MemoryDependenceResults *MD; |
113 | DominatorTree *DT; |
114 | |
115 | uint32_t nextValueNumber = 1; |
116 | |
117 | Expression createExpr(Instruction *I); |
118 | Expression createCmpExpr(unsigned Opcode, CmpInst::Predicate Predicate, |
119 | Value *LHS, Value *RHS); |
120 | Expression (ExtractValueInst *EI); |
121 | uint32_t lookupOrAddCall(CallInst *C); |
122 | uint32_t phiTranslateImpl(const BasicBlock *BB, const BasicBlock *PhiBlock, |
123 | uint32_t Num, GVN &Gvn); |
124 | std::pair<uint32_t, bool> assignExpNewValueNum(Expression &exp); |
125 | bool areAllValsInBB(uint32_t num, const BasicBlock *BB, GVN &Gvn); |
126 | |
127 | public: |
128 | ValueTable(); |
129 | ValueTable(const ValueTable &Arg); |
130 | ValueTable(ValueTable &&Arg); |
131 | ~ValueTable(); |
132 | |
133 | uint32_t lookupOrAdd(Value *V); |
134 | uint32_t lookup(Value *V, bool Verify = true) const; |
135 | uint32_t lookupOrAddCmp(unsigned Opcode, CmpInst::Predicate Pred, |
136 | Value *LHS, Value *RHS); |
137 | uint32_t phiTranslate(const BasicBlock *BB, const BasicBlock *PhiBlock, |
138 | uint32_t Num, GVN &Gvn); |
139 | void eraseTranslateCacheEntry(uint32_t Num, const BasicBlock &CurrBlock); |
140 | bool exists(Value *V) const; |
141 | void add(Value *V, uint32_t num); |
142 | void clear(); |
143 | void erase(Value *v); |
144 | void setAliasAnalysis(AliasAnalysis *A) { AA = A; } |
145 | AliasAnalysis *getAliasAnalysis() const { return AA; } |
146 | void setMemDep(MemoryDependenceResults *M) { MD = M; } |
147 | void setDomTree(DominatorTree *D) { DT = D; } |
148 | uint32_t getNextUnusedValueNumber() { return nextValueNumber; } |
149 | void verifyRemoved(const Value *) const; |
150 | }; |
151 | |
152 | private: |
153 | friend class gvn::GVNLegacyPass; |
154 | friend struct DenseMapInfo<Expression>; |
155 | |
156 | MemoryDependenceResults *MD; |
157 | DominatorTree *DT; |
158 | const TargetLibraryInfo *TLI; |
159 | AssumptionCache *AC; |
160 | SetVector<BasicBlock *> DeadBlocks; |
161 | OptimizationRemarkEmitter *ORE; |
162 | ImplicitControlFlowTracking *ICF; |
163 | |
164 | ValueTable VN; |
165 | |
166 | /// A mapping from value numbers to lists of Value*'s that |
167 | /// have that value number. Use findLeader to query it. |
168 | struct LeaderTableEntry { |
169 | Value *Val; |
170 | const BasicBlock *BB; |
171 | LeaderTableEntry *Next; |
172 | }; |
173 | DenseMap<uint32_t, LeaderTableEntry> LeaderTable; |
174 | BumpPtrAllocator TableAllocator; |
175 | |
176 | // Block-local map of equivalent values to their leader, does not |
177 | // propagate to any successors. Entries added mid-block are applied |
178 | // to the remaining instructions in the block. |
179 | SmallMapVector<Value *, Constant *, 4> ReplaceWithConstMap; |
180 | SmallVector<Instruction *, 8> InstrsToErase; |
181 | |
182 | // Map the block to reversed postorder traversal number. It is used to |
183 | // find back edge easily. |
184 | DenseMap<AssertingVH<BasicBlock>, uint32_t> BlockRPONumber; |
185 | |
186 | // This is set 'true' initially and also when new blocks have been added to |
187 | // the function being analyzed. This boolean is used to control the updating |
188 | // of BlockRPONumber prior to accessing the contents of BlockRPONumber. |
189 | bool InvalidBlockRPONumbers = true; |
190 | |
191 | using LoadDepVect = SmallVector<NonLocalDepResult, 64>; |
192 | using AvailValInBlkVect = SmallVector<gvn::AvailableValueInBlock, 64>; |
193 | using UnavailBlkVect = SmallVector<BasicBlock *, 64>; |
194 | |
195 | bool runImpl(Function &F, AssumptionCache &RunAC, DominatorTree &RunDT, |
196 | const TargetLibraryInfo &RunTLI, AAResults &RunAA, |
197 | MemoryDependenceResults *RunMD, LoopInfo *LI, |
198 | OptimizationRemarkEmitter *ORE); |
199 | |
200 | /// Push a new Value to the LeaderTable onto the list for its value number. |
201 | void addToLeaderTable(uint32_t N, Value *V, const BasicBlock *BB) { |
202 | LeaderTableEntry &Curr = LeaderTable[N]; |
203 | if (!Curr.Val) { |
204 | Curr.Val = V; |
205 | Curr.BB = BB; |
206 | return; |
207 | } |
208 | |
209 | LeaderTableEntry *Node = TableAllocator.Allocate<LeaderTableEntry>(); |
210 | Node->Val = V; |
211 | Node->BB = BB; |
212 | Node->Next = Curr.Next; |
213 | Curr.Next = Node; |
214 | } |
215 | |
216 | /// Scan the list of values corresponding to a given |
217 | /// value number, and remove the given instruction if encountered. |
218 | void removeFromLeaderTable(uint32_t N, Instruction *I, BasicBlock *BB) { |
219 | LeaderTableEntry *Prev = nullptr; |
220 | LeaderTableEntry *Curr = &LeaderTable[N]; |
221 | |
222 | while (Curr && (Curr->Val != I || Curr->BB != BB)) { |
223 | Prev = Curr; |
224 | Curr = Curr->Next; |
225 | } |
226 | |
227 | if (!Curr) |
228 | return; |
229 | |
230 | if (Prev) { |
231 | Prev->Next = Curr->Next; |
232 | } else { |
233 | if (!Curr->Next) { |
234 | Curr->Val = nullptr; |
235 | Curr->BB = nullptr; |
236 | } else { |
237 | LeaderTableEntry *Next = Curr->Next; |
238 | Curr->Val = Next->Val; |
239 | Curr->BB = Next->BB; |
240 | Curr->Next = Next->Next; |
241 | } |
242 | } |
243 | } |
244 | |
245 | // List of critical edges to be split between iterations. |
246 | SmallVector<std::pair<Instruction *, unsigned>, 4> toSplit; |
247 | |
248 | // Helper functions of redundant load elimination |
249 | bool processLoad(LoadInst *L); |
250 | bool processNonLocalLoad(LoadInst *L); |
251 | bool processAssumeIntrinsic(IntrinsicInst *II); |
252 | |
253 | /// Given a local dependency (Def or Clobber) determine if a value is |
254 | /// available for the load. Returns true if an value is known to be |
255 | /// available and populates Res. Returns false otherwise. |
256 | bool AnalyzeLoadAvailability(LoadInst *LI, MemDepResult DepInfo, |
257 | Value *Address, gvn::AvailableValue &Res); |
258 | |
259 | /// Given a list of non-local dependencies, determine if a value is |
260 | /// available for the load in each specified block. If it is, add it to |
261 | /// ValuesPerBlock. If not, add it to UnavailableBlocks. |
262 | void AnalyzeLoadAvailability(LoadInst *LI, LoadDepVect &Deps, |
263 | AvailValInBlkVect &ValuesPerBlock, |
264 | UnavailBlkVect &UnavailableBlocks); |
265 | |
266 | bool PerformLoadPRE(LoadInst *LI, AvailValInBlkVect &ValuesPerBlock, |
267 | UnavailBlkVect &UnavailableBlocks); |
268 | |
269 | // Other helper routines |
270 | bool processInstruction(Instruction *I); |
271 | bool processBlock(BasicBlock *BB); |
272 | void dump(DenseMap<uint32_t, Value *> &d) const; |
273 | bool iterateOnFunction(Function &F); |
274 | bool performPRE(Function &F); |
275 | bool performScalarPRE(Instruction *I); |
276 | bool performScalarPREInsertion(Instruction *Instr, BasicBlock *Pred, |
277 | BasicBlock *Curr, unsigned int ValNo); |
278 | Value *findLeader(const BasicBlock *BB, uint32_t num); |
279 | void cleanupGlobalSets(); |
280 | void fillImplicitControlFlowInfo(BasicBlock *BB); |
281 | void verifyRemoved(const Instruction *I) const; |
282 | bool splitCriticalEdges(); |
283 | BasicBlock *splitCriticalEdges(BasicBlock *Pred, BasicBlock *Succ); |
284 | bool replaceOperandsWithConsts(Instruction *I) const; |
285 | bool propagateEquality(Value *LHS, Value *RHS, const BasicBlockEdge &Root, |
286 | bool DominatesByEdge); |
287 | bool processFoldableCondBr(BranchInst *BI); |
288 | void addDeadBlock(BasicBlock *BB); |
289 | void assignValNumForDeadCode(); |
290 | void assignBlockRPONumber(Function &F); |
291 | }; |
292 | |
293 | /// Create a legacy GVN pass. This also allows parameterizing whether or not |
294 | /// loads are eliminated by the pass. |
295 | FunctionPass *createGVNPass(bool NoLoads = false); |
296 | |
297 | /// A simple and fast domtree-based GVN pass to hoist common expressions |
298 | /// from sibling branches. |
299 | struct GVNHoistPass : PassInfoMixin<GVNHoistPass> { |
300 | /// Run the pass over the function. |
301 | PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); |
302 | }; |
303 | |
304 | /// Uses an "inverted" value numbering to decide the similarity of |
305 | /// expressions and sinks similar expressions into successors. |
306 | struct GVNSinkPass : PassInfoMixin<GVNSinkPass> { |
307 | /// Run the pass over the function. |
308 | PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); |
309 | }; |
310 | |
311 | } // end namespace llvm |
312 | |
313 | #endif // LLVM_TRANSFORMS_SCALAR_GVN_H |
314 | |