1 | //===- GVN.h - Eliminate redundant values and loads -------------*- 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 | /// \file |
9 | /// This file provides the interface for LLVM's Global Value Numbering pass |
10 | /// which eliminates fully redundant instructions. It also does somewhat Ad-Hoc |
11 | /// PRE and dead load elimination. |
12 | /// |
13 | //===----------------------------------------------------------------------===// |
14 | |
15 | #ifndef LLVM_TRANSFORMS_SCALAR_GVN_H |
16 | #define LLVM_TRANSFORMS_SCALAR_GVN_H |
17 | |
18 | #include "llvm/ADT/DenseMap.h" |
19 | #include "llvm/ADT/MapVector.h" |
20 | #include "llvm/ADT/SetVector.h" |
21 | #include "llvm/ADT/SmallVector.h" |
22 | #include "llvm/IR/Dominators.h" |
23 | #include "llvm/IR/InstrTypes.h" |
24 | #include "llvm/IR/PassManager.h" |
25 | #include "llvm/IR/ValueHandle.h" |
26 | #include "llvm/Support/Allocator.h" |
27 | #include "llvm/Support/Compiler.h" |
28 | #include <cstdint> |
29 | #include <optional> |
30 | #include <utility> |
31 | #include <vector> |
32 | |
33 | namespace llvm { |
34 | |
35 | class AAResults; |
36 | class AssumeInst; |
37 | class AssumptionCache; |
38 | class BasicBlock; |
39 | class BranchInst; |
40 | class CallInst; |
41 | class ; |
42 | class Function; |
43 | class FunctionPass; |
44 | class GetElementPtrInst; |
45 | class ImplicitControlFlowTracking; |
46 | class LoadInst; |
47 | class LoopInfo; |
48 | class MemDepResult; |
49 | class MemoryDependenceResults; |
50 | class MemorySSA; |
51 | class MemorySSAUpdater; |
52 | class NonLocalDepResult; |
53 | class ; |
54 | class PHINode; |
55 | class TargetLibraryInfo; |
56 | class Value; |
57 | /// A private "module" namespace for types and utilities used by GVN. These |
58 | /// are implementation details and should not be used by clients. |
59 | namespace LLVM_LIBRARY_VISIBILITY gvn { |
60 | |
61 | struct AvailableValue; |
62 | struct AvailableValueInBlock; |
63 | class GVNLegacyPass; |
64 | |
65 | } // end namespace gvn |
66 | |
67 | /// A set of parameters to control various transforms performed by GVN pass. |
68 | // Each of the optional boolean parameters can be set to: |
69 | /// true - enabling the transformation. |
70 | /// false - disabling the transformation. |
71 | /// None - relying on a global default. |
72 | /// Intended use is to create a default object, modify parameters with |
73 | /// additional setters and then pass it to GVN. |
74 | struct GVNOptions { |
75 | std::optional<bool> AllowPRE; |
76 | std::optional<bool> AllowLoadPRE; |
77 | std::optional<bool> AllowLoadInLoopPRE; |
78 | std::optional<bool> AllowLoadPRESplitBackedge; |
79 | std::optional<bool> AllowMemDep; |
80 | |
81 | GVNOptions() = default; |
82 | |
83 | /// Enables or disables PRE in GVN. |
84 | GVNOptions &setPRE(bool PRE) { |
85 | AllowPRE = PRE; |
86 | return *this; |
87 | } |
88 | |
89 | /// Enables or disables PRE of loads in GVN. |
90 | GVNOptions &setLoadPRE(bool LoadPRE) { |
91 | AllowLoadPRE = LoadPRE; |
92 | return *this; |
93 | } |
94 | |
95 | GVNOptions &setLoadInLoopPRE(bool LoadInLoopPRE) { |
96 | AllowLoadInLoopPRE = LoadInLoopPRE; |
97 | return *this; |
98 | } |
99 | |
100 | /// Enables or disables PRE of loads in GVN. |
101 | GVNOptions &setLoadPRESplitBackedge(bool LoadPRESplitBackedge) { |
102 | AllowLoadPRESplitBackedge = LoadPRESplitBackedge; |
103 | return *this; |
104 | } |
105 | |
106 | /// Enables or disables use of MemDepAnalysis. |
107 | GVNOptions &setMemDep(bool MemDep) { |
108 | AllowMemDep = MemDep; |
109 | return *this; |
110 | } |
111 | }; |
112 | |
113 | /// The core GVN pass object. |
114 | /// |
115 | /// FIXME: We should have a good summary of the GVN algorithm implemented by |
116 | /// this particular pass here. |
117 | class GVNPass : public PassInfoMixin<GVNPass> { |
118 | GVNOptions Options; |
119 | |
120 | public: |
121 | struct Expression; |
122 | |
123 | GVNPass(GVNOptions Options = {}) : Options(Options) {} |
124 | |
125 | /// Run the pass over the function. |
126 | PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); |
127 | |
128 | void printPipeline(raw_ostream &OS, |
129 | function_ref<StringRef(StringRef)> MapClassName2PassName); |
130 | |
131 | /// This removes the specified instruction from |
132 | /// our various maps and marks it for deletion. |
133 | void markInstructionForDeletion(Instruction *I) { |
134 | VN.erase(v: I); |
135 | InstrsToErase.push_back(Elt: I); |
136 | } |
137 | |
138 | DominatorTree &getDominatorTree() const { return *DT; } |
139 | AAResults *getAliasAnalysis() const { return VN.getAliasAnalysis(); } |
140 | MemoryDependenceResults &getMemDep() const { return *MD; } |
141 | |
142 | bool isPREEnabled() const; |
143 | bool isLoadPREEnabled() const; |
144 | bool isLoadInLoopPREEnabled() const; |
145 | bool isLoadPRESplitBackedgeEnabled() const; |
146 | bool isMemDepEnabled() const; |
147 | |
148 | /// This class holds the mapping between values and value numbers. It is used |
149 | /// as an efficient mechanism to determine the expression-wise equivalence of |
150 | /// two values. |
151 | class ValueTable { |
152 | DenseMap<Value *, uint32_t> valueNumbering; |
153 | DenseMap<Expression, uint32_t> expressionNumbering; |
154 | |
155 | // Expressions is the vector of Expression. ExprIdx is the mapping from |
156 | // value number to the index of Expression in Expressions. We use it |
157 | // instead of a DenseMap because filling such mapping is faster than |
158 | // filling a DenseMap and the compile time is a little better. |
159 | uint32_t nextExprNumber = 0; |
160 | |
161 | std::vector<Expression> Expressions; |
162 | std::vector<uint32_t> ExprIdx; |
163 | |
164 | // Value number to PHINode mapping. Used for phi-translate in scalarpre. |
165 | DenseMap<uint32_t, PHINode *> NumberingPhi; |
166 | |
167 | // Cache for phi-translate in scalarpre. |
168 | using PhiTranslateMap = |
169 | DenseMap<std::pair<uint32_t, const BasicBlock *>, uint32_t>; |
170 | PhiTranslateMap PhiTranslateTable; |
171 | |
172 | AAResults *AA = nullptr; |
173 | MemoryDependenceResults *MD = nullptr; |
174 | DominatorTree *DT = nullptr; |
175 | |
176 | uint32_t nextValueNumber = 1; |
177 | |
178 | Expression createExpr(Instruction *I); |
179 | Expression createCmpExpr(unsigned Opcode, CmpInst::Predicate Predicate, |
180 | Value *LHS, Value *RHS); |
181 | Expression (ExtractValueInst *EI); |
182 | Expression createGEPExpr(GetElementPtrInst *GEP); |
183 | uint32_t lookupOrAddCall(CallInst *C); |
184 | uint32_t phiTranslateImpl(const BasicBlock *BB, const BasicBlock *PhiBlock, |
185 | uint32_t Num, GVNPass &Gvn); |
186 | bool areCallValsEqual(uint32_t Num, uint32_t NewNum, const BasicBlock *Pred, |
187 | const BasicBlock *PhiBlock, GVNPass &Gvn); |
188 | std::pair<uint32_t, bool> assignExpNewValueNum(Expression &exp); |
189 | bool areAllValsInBB(uint32_t num, const BasicBlock *BB, GVNPass &Gvn); |
190 | |
191 | public: |
192 | ValueTable(); |
193 | ValueTable(const ValueTable &Arg); |
194 | ValueTable(ValueTable &&Arg); |
195 | ~ValueTable(); |
196 | ValueTable &operator=(const ValueTable &Arg); |
197 | |
198 | uint32_t lookupOrAdd(Value *V); |
199 | uint32_t lookup(Value *V, bool Verify = true) const; |
200 | uint32_t lookupOrAddCmp(unsigned Opcode, CmpInst::Predicate Pred, |
201 | Value *LHS, Value *RHS); |
202 | uint32_t phiTranslate(const BasicBlock *BB, const BasicBlock *PhiBlock, |
203 | uint32_t Num, GVNPass &Gvn); |
204 | void eraseTranslateCacheEntry(uint32_t Num, const BasicBlock &CurrBlock); |
205 | bool exists(Value *V) const; |
206 | void add(Value *V, uint32_t num); |
207 | void clear(); |
208 | void erase(Value *v); |
209 | void setAliasAnalysis(AAResults *A) { AA = A; } |
210 | AAResults *getAliasAnalysis() const { return AA; } |
211 | void setMemDep(MemoryDependenceResults *M) { MD = M; } |
212 | void setDomTree(DominatorTree *D) { DT = D; } |
213 | uint32_t getNextUnusedValueNumber() { return nextValueNumber; } |
214 | void verifyRemoved(const Value *) const; |
215 | }; |
216 | |
217 | private: |
218 | friend class gvn::GVNLegacyPass; |
219 | friend struct DenseMapInfo<Expression>; |
220 | |
221 | MemoryDependenceResults *MD = nullptr; |
222 | DominatorTree *DT = nullptr; |
223 | const TargetLibraryInfo *TLI = nullptr; |
224 | AssumptionCache *AC = nullptr; |
225 | SetVector<BasicBlock *> DeadBlocks; |
226 | OptimizationRemarkEmitter *ORE = nullptr; |
227 | ImplicitControlFlowTracking *ICF = nullptr; |
228 | LoopInfo *LI = nullptr; |
229 | MemorySSAUpdater *MSSAU = nullptr; |
230 | |
231 | ValueTable VN; |
232 | |
233 | /// A mapping from value numbers to lists of Value*'s that |
234 | /// have that value number. Use findLeader to query it. |
235 | struct LeaderTableEntry { |
236 | Value *Val; |
237 | const BasicBlock *BB; |
238 | LeaderTableEntry *Next; |
239 | }; |
240 | DenseMap<uint32_t, LeaderTableEntry> LeaderTable; |
241 | BumpPtrAllocator TableAllocator; |
242 | |
243 | // Block-local map of equivalent values to their leader, does not |
244 | // propagate to any successors. Entries added mid-block are applied |
245 | // to the remaining instructions in the block. |
246 | SmallMapVector<Value *, Value *, 4> ReplaceOperandsWithMap; |
247 | SmallVector<Instruction *, 8> InstrsToErase; |
248 | |
249 | // Map the block to reversed postorder traversal number. It is used to |
250 | // find back edge easily. |
251 | DenseMap<AssertingVH<BasicBlock>, uint32_t> BlockRPONumber; |
252 | |
253 | // This is set 'true' initially and also when new blocks have been added to |
254 | // the function being analyzed. This boolean is used to control the updating |
255 | // of BlockRPONumber prior to accessing the contents of BlockRPONumber. |
256 | bool InvalidBlockRPONumbers = true; |
257 | |
258 | using LoadDepVect = SmallVector<NonLocalDepResult, 64>; |
259 | using AvailValInBlkVect = SmallVector<gvn::AvailableValueInBlock, 64>; |
260 | using UnavailBlkVect = SmallVector<BasicBlock *, 64>; |
261 | |
262 | bool runImpl(Function &F, AssumptionCache &RunAC, DominatorTree &RunDT, |
263 | const TargetLibraryInfo &RunTLI, AAResults &RunAA, |
264 | MemoryDependenceResults *RunMD, LoopInfo &LI, |
265 | OptimizationRemarkEmitter *ORE, MemorySSA *MSSA = nullptr); |
266 | |
267 | /// Push a new Value to the LeaderTable onto the list for its value number. |
268 | void addToLeaderTable(uint32_t N, Value *V, const BasicBlock *BB) { |
269 | LeaderTableEntry &Curr = LeaderTable[N]; |
270 | if (!Curr.Val) { |
271 | Curr.Val = V; |
272 | Curr.BB = BB; |
273 | return; |
274 | } |
275 | |
276 | LeaderTableEntry *Node = TableAllocator.Allocate<LeaderTableEntry>(); |
277 | Node->Val = V; |
278 | Node->BB = BB; |
279 | Node->Next = Curr.Next; |
280 | Curr.Next = Node; |
281 | } |
282 | |
283 | /// Scan the list of values corresponding to a given |
284 | /// value number, and remove the given instruction if encountered. |
285 | void removeFromLeaderTable(uint32_t N, Instruction *I, BasicBlock *BB) { |
286 | LeaderTableEntry *Prev = nullptr; |
287 | LeaderTableEntry *Curr = &LeaderTable[N]; |
288 | |
289 | while (Curr && (Curr->Val != I || Curr->BB != BB)) { |
290 | Prev = Curr; |
291 | Curr = Curr->Next; |
292 | } |
293 | |
294 | if (!Curr) |
295 | return; |
296 | |
297 | if (Prev) { |
298 | Prev->Next = Curr->Next; |
299 | } else { |
300 | if (!Curr->Next) { |
301 | Curr->Val = nullptr; |
302 | Curr->BB = nullptr; |
303 | } else { |
304 | LeaderTableEntry *Next = Curr->Next; |
305 | Curr->Val = Next->Val; |
306 | Curr->BB = Next->BB; |
307 | Curr->Next = Next->Next; |
308 | } |
309 | } |
310 | } |
311 | |
312 | // List of critical edges to be split between iterations. |
313 | SmallVector<std::pair<Instruction *, unsigned>, 4> toSplit; |
314 | |
315 | // Helper functions of redundant load elimination |
316 | bool processLoad(LoadInst *L); |
317 | bool processNonLocalLoad(LoadInst *L); |
318 | bool processAssumeIntrinsic(AssumeInst *II); |
319 | |
320 | /// Given a local dependency (Def or Clobber) determine if a value is |
321 | /// available for the load. |
322 | std::optional<gvn::AvailableValue> |
323 | AnalyzeLoadAvailability(LoadInst *Load, MemDepResult DepInfo, Value *Address); |
324 | |
325 | /// Given a list of non-local dependencies, determine if a value is |
326 | /// available for the load in each specified block. If it is, add it to |
327 | /// ValuesPerBlock. If not, add it to UnavailableBlocks. |
328 | void AnalyzeLoadAvailability(LoadInst *Load, LoadDepVect &Deps, |
329 | AvailValInBlkVect &ValuesPerBlock, |
330 | UnavailBlkVect &UnavailableBlocks); |
331 | |
332 | /// Given a critical edge from Pred to LoadBB, find a load instruction |
333 | /// which is identical to Load from another successor of Pred. |
334 | LoadInst *findLoadToHoistIntoPred(BasicBlock *Pred, BasicBlock *LoadBB, |
335 | LoadInst *Load); |
336 | |
337 | bool PerformLoadPRE(LoadInst *Load, AvailValInBlkVect &ValuesPerBlock, |
338 | UnavailBlkVect &UnavailableBlocks); |
339 | |
340 | /// Try to replace a load which executes on each loop iteraiton with Phi |
341 | /// translation of load in preheader and load(s) in conditionally executed |
342 | /// paths. |
343 | bool performLoopLoadPRE(LoadInst *Load, AvailValInBlkVect &ValuesPerBlock, |
344 | UnavailBlkVect &UnavailableBlocks); |
345 | |
346 | /// Eliminates partially redundant \p Load, replacing it with \p |
347 | /// AvailableLoads (connected by Phis if needed). |
348 | void eliminatePartiallyRedundantLoad( |
349 | LoadInst *Load, AvailValInBlkVect &ValuesPerBlock, |
350 | MapVector<BasicBlock *, Value *> &AvailableLoads, |
351 | MapVector<BasicBlock *, LoadInst *> *CriticalEdgePredAndLoad); |
352 | |
353 | // Other helper routines |
354 | bool processInstruction(Instruction *I); |
355 | bool processBlock(BasicBlock *BB); |
356 | void dump(DenseMap<uint32_t, Value *> &d) const; |
357 | bool iterateOnFunction(Function &F); |
358 | bool performPRE(Function &F); |
359 | bool performScalarPRE(Instruction *I); |
360 | bool performScalarPREInsertion(Instruction *Instr, BasicBlock *Pred, |
361 | BasicBlock *Curr, unsigned int ValNo); |
362 | Value *findLeader(const BasicBlock *BB, uint32_t num); |
363 | void cleanupGlobalSets(); |
364 | void removeInstruction(Instruction *I); |
365 | void verifyRemoved(const Instruction *I) const; |
366 | bool splitCriticalEdges(); |
367 | BasicBlock *splitCriticalEdges(BasicBlock *Pred, BasicBlock *Succ); |
368 | bool replaceOperandsForInBlockEquality(Instruction *I) const; |
369 | bool propagateEquality(Value *LHS, Value *RHS, const BasicBlockEdge &Root, |
370 | bool DominatesByEdge); |
371 | bool processFoldableCondBr(BranchInst *BI); |
372 | void addDeadBlock(BasicBlock *BB); |
373 | void assignValNumForDeadCode(); |
374 | void assignBlockRPONumber(Function &F); |
375 | }; |
376 | |
377 | /// Create a legacy GVN pass. This also allows parameterizing whether or not |
378 | /// MemDep is enabled. |
379 | FunctionPass *createGVNPass(bool NoMemDepAnalysis = false); |
380 | |
381 | /// A simple and fast domtree-based GVN pass to hoist common expressions |
382 | /// from sibling branches. |
383 | struct GVNHoistPass : PassInfoMixin<GVNHoistPass> { |
384 | /// Run the pass over the function. |
385 | PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); |
386 | }; |
387 | |
388 | /// Uses an "inverted" value numbering to decide the similarity of |
389 | /// expressions and sinks similar expressions into successors. |
390 | struct GVNSinkPass : PassInfoMixin<GVNSinkPass> { |
391 | /// Run the pass over the function. |
392 | PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); |
393 | }; |
394 | |
395 | } // end namespace llvm |
396 | |
397 | #endif // LLVM_TRANSFORMS_SCALAR_GVN_H |
398 | |