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