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 ExtractValueInst;
45 class Function;
46 class FunctionPass;
47 class IntrinsicInst;
48 class LoadInst;
49 class LoopInfo;
50 class OptimizationRemarkEmitter;
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.
markInstructionForDeletion(Instruction * I)78   void markInstructionForDeletion(Instruction *I) {
79     VN.erase(I);
80     InstrsToErase.push_back(I);
81   }
82 
getDominatorTree()83   DominatorTree &getDominatorTree() const { return *DT; }
getAliasAnalysis()84   AliasAnalysis *getAliasAnalysis() const { return VN.getAliasAnalysis(); }
getMemDep()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 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);
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);
setAliasAnalysis(AliasAnalysis * A)144     void setAliasAnalysis(AliasAnalysis *A) { AA = A; }
getAliasAnalysis()145     AliasAnalysis *getAliasAnalysis() const { return AA; }
setMemDep(MemoryDependenceResults * M)146     void setMemDep(MemoryDependenceResults *M) { MD = M; }
setDomTree(DominatorTree * D)147     void setDomTree(DominatorTree *D) { DT = D; }
getNextUnusedValueNumber()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