1 //===- GVN.h - Eliminate redundant values and loads -------------*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
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.
14 //===----------------------------------------------------------------------===//
16 #ifndef LLVM_TRANSFORMS_SCALAR_GVN_H
17 #define LLVM_TRANSFORMS_SCALAR_GVN_H
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"
39 class AssumptionCache;
44 class ExtractValueInst;
50 class OptimizationRemarkEmitter;
52 class TargetLibraryInfo;
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 {
59 struct AvailableValue;
60 struct AvailableValueInBlock;
63 } // end namespace gvn
65 /// The core GVN pass object.
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> {
73 /// Run the pass over the function.
74 PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
76 /// This removes the specified instruction from
77 /// our various maps and marks it for deletion.
78 void markInstructionForDeletion(Instruction *I) {
80 InstrsToErase.push_back(I);
83 DominatorTree &getDominatorTree() const { return *DT; }
84 AliasAnalysis *getAliasAnalysis() const { return VN.getAliasAnalysis(); }
85 MemoryDependenceResults &getMemDep() const { return *MD; }
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
91 DenseMap<Value *, uint32_t> valueNumbering;
92 DenseMap<Expression, uint32_t> expressionNumbering;
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;
100 std::vector<Expression> Expressions;
101 std::vector<uint32_t> ExprIdx;
103 // Value number to PHINode mapping. Used for phi-translate in scalarpre.
104 DenseMap<uint32_t, PHINode *> NumberingPhi;
106 // Cache for phi-translate in scalarpre.
107 using PhiTranslateMap =
108 DenseMap<std::pair<uint32_t, const BasicBlock *>, uint32_t>;
109 PhiTranslateMap PhiTranslateTable;
112 MemoryDependenceResults *MD;
115 uint32_t nextValueNumber = 1;
117 Expression createExpr(Instruction *I);
118 Expression createCmpExpr(unsigned Opcode, CmpInst::Predicate Predicate,
119 Value *LHS, Value *RHS);
120 Expression createExtractvalueExpr(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);
129 ValueTable(const ValueTable &Arg);
130 ValueTable(ValueTable &&Arg);
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);
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;
153 friend class gvn::GVNLegacyPass;
154 friend struct DenseMapInfo<Expression>;
156 MemoryDependenceResults *MD;
158 const TargetLibraryInfo *TLI;
160 SetVector<BasicBlock *> DeadBlocks;
161 OptimizationRemarkEmitter *ORE;
162 ImplicitControlFlowTracking *ICF;
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 {
170 const BasicBlock *BB;
171 LeaderTableEntry *Next;
173 DenseMap<uint32_t, LeaderTableEntry> LeaderTable;
174 BumpPtrAllocator TableAllocator;
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;
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;
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;
191 using LoadDepVect = SmallVector<NonLocalDepResult, 64>;
192 using AvailValInBlkVect = SmallVector<gvn::AvailableValueInBlock, 64>;
193 using UnavailBlkVect = SmallVector<BasicBlock *, 64>;
195 bool runImpl(Function &F, AssumptionCache &RunAC, DominatorTree &RunDT,
196 const TargetLibraryInfo &RunTLI, AAResults &RunAA,
197 MemoryDependenceResults *RunMD, LoopInfo *LI,
198 OptimizationRemarkEmitter *ORE);
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];
209 LeaderTableEntry *Node = TableAllocator.Allocate<LeaderTableEntry>();
212 Node->Next = Curr.Next;
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];
222 while (Curr && (Curr->Val != I || Curr->BB != BB)) {
231 Prev->Next = Curr->Next;
237 LeaderTableEntry *Next = Curr->Next;
238 Curr->Val = Next->Val;
240 Curr->Next = Next->Next;
245 // List of critical edges to be split between iterations.
246 SmallVector<std::pair<Instruction *, unsigned>, 4> toSplit;
248 // Helper functions of redundant load elimination
249 bool processLoad(LoadInst *L);
250 bool processNonLocalLoad(LoadInst *L);
251 bool processAssumeIntrinsic(IntrinsicInst *II);
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);
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);
266 bool PerformLoadPRE(LoadInst *LI, AvailValInBlkVect &ValuesPerBlock,
267 UnavailBlkVect &UnavailableBlocks);
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);
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);
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);
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);
311 } // end namespace llvm
313 #endif // LLVM_TRANSFORMS_SCALAR_GVN_H