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/PostOrderIterator.h"
21 #include "llvm/ADT/SetVector.h"
22 #include "llvm/ADT/SmallVector.h"
23 #include "llvm/Analysis/AliasAnalysis.h"
24 #include "llvm/Analysis/InstructionPrecedenceTracking.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/IR/ValueHandle.h"
30 #include "llvm/Support/Allocator.h"
31 #include "llvm/Support/Compiler.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.
77   void markInstructionForDeletion(Instruction *I) {
78     VN.erase(I);
79     InstrsToErase.push_back(I);
80   }
81 
82   DominatorTree &getDominatorTree() const { return *DT; }
83   AliasAnalysis *getAliasAnalysis() const { return VN.getAliasAnalysis(); }
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 = 0;
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 = nullptr;
111     MemoryDependenceResults *MD = nullptr;
112     DominatorTree *DT = nullptr;
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     bool areCallValsEqual(uint32_t Num, uint32_t NewNum, const BasicBlock *Pred,
124                           const BasicBlock *PhiBlock, GVN &Gvn);
125     std::pair<uint32_t, bool> assignExpNewValueNum(Expression &exp);
126     bool areAllValsInBB(uint32_t num, const BasicBlock *BB, GVN &Gvn);
127 
128   public:
129     ValueTable();
130     ValueTable(const ValueTable &Arg);
131     ValueTable(ValueTable &&Arg);
132     ~ValueTable();
133     ValueTable &operator=(const ValueTable &Arg);
134 
135     uint32_t lookupOrAdd(Value *V);
136     uint32_t lookup(Value *V, bool Verify = true) const;
137     uint32_t lookupOrAddCmp(unsigned Opcode, CmpInst::Predicate Pred,
138                             Value *LHS, Value *RHS);
139     uint32_t phiTranslate(const BasicBlock *BB, const BasicBlock *PhiBlock,
140                           uint32_t Num, GVN &Gvn);
141     void eraseTranslateCacheEntry(uint32_t Num, const BasicBlock &CurrBlock);
142     bool exists(Value *V) const;
143     void add(Value *V, uint32_t num);
144     void clear();
145     void erase(Value *v);
146     void setAliasAnalysis(AliasAnalysis *A) { AA = A; }
147     AliasAnalysis *getAliasAnalysis() const { return AA; }
148     void setMemDep(MemoryDependenceResults *M) { MD = M; }
149     void setDomTree(DominatorTree *D) { DT = D; }
150     uint32_t getNextUnusedValueNumber() { return nextValueNumber; }
151     void verifyRemoved(const Value *) const;
152   };
153 
154 private:
155   friend class gvn::GVNLegacyPass;
156   friend struct DenseMapInfo<Expression>;
157 
158   MemoryDependenceResults *MD = nullptr;
159   DominatorTree *DT = nullptr;
160   const TargetLibraryInfo *TLI = nullptr;
161   AssumptionCache *AC = nullptr;
162   SetVector<BasicBlock *> DeadBlocks;
163   OptimizationRemarkEmitter *ORE = nullptr;
164   ImplicitControlFlowTracking *ICF = nullptr;
165   LoopInfo *LI = nullptr;
166 
167   ValueTable VN;
168 
169   /// A mapping from value numbers to lists of Value*'s that
170   /// have that value number.  Use findLeader to query it.
171   struct LeaderTableEntry {
172     Value *Val;
173     const BasicBlock *BB;
174     LeaderTableEntry *Next;
175   };
176   DenseMap<uint32_t, LeaderTableEntry> LeaderTable;
177   BumpPtrAllocator TableAllocator;
178 
179   // Block-local map of equivalent values to their leader, does not
180   // propagate to any successors. Entries added mid-block are applied
181   // to the remaining instructions in the block.
182   SmallMapVector<Value *, Value *, 4> ReplaceOperandsWithMap;
183   SmallVector<Instruction *, 8> InstrsToErase;
184 
185   // Map the block to reversed postorder traversal number. It is used to
186   // find back edge easily.
187   DenseMap<AssertingVH<BasicBlock>, uint32_t> BlockRPONumber;
188 
189   // This is set 'true' initially and also when new blocks have been added to
190   // the function being analyzed. This boolean is used to control the updating
191   // of BlockRPONumber prior to accessing the contents of BlockRPONumber.
192   bool InvalidBlockRPONumbers = true;
193 
194   using LoadDepVect = SmallVector<NonLocalDepResult, 64>;
195   using AvailValInBlkVect = SmallVector<gvn::AvailableValueInBlock, 64>;
196   using UnavailBlkVect = SmallVector<BasicBlock *, 64>;
197 
198   bool runImpl(Function &F, AssumptionCache &RunAC, DominatorTree &RunDT,
199                const TargetLibraryInfo &RunTLI, AAResults &RunAA,
200                MemoryDependenceResults *RunMD, LoopInfo *LI,
201                OptimizationRemarkEmitter *ORE);
202 
203   /// Push a new Value to the LeaderTable onto the list for its value number.
204   void addToLeaderTable(uint32_t N, Value *V, const BasicBlock *BB) {
205     LeaderTableEntry &Curr = LeaderTable[N];
206     if (!Curr.Val) {
207       Curr.Val = V;
208       Curr.BB = BB;
209       return;
210     }
211 
212     LeaderTableEntry *Node = TableAllocator.Allocate<LeaderTableEntry>();
213     Node->Val = V;
214     Node->BB = BB;
215     Node->Next = Curr.Next;
216     Curr.Next = Node;
217   }
218 
219   /// Scan the list of values corresponding to a given
220   /// value number, and remove the given instruction if encountered.
221   void removeFromLeaderTable(uint32_t N, Instruction *I, BasicBlock *BB) {
222     LeaderTableEntry *Prev = nullptr;
223     LeaderTableEntry *Curr = &LeaderTable[N];
224 
225     while (Curr && (Curr->Val != I || Curr->BB != BB)) {
226       Prev = Curr;
227       Curr = Curr->Next;
228     }
229 
230     if (!Curr)
231       return;
232 
233     if (Prev) {
234       Prev->Next = Curr->Next;
235     } else {
236       if (!Curr->Next) {
237         Curr->Val = nullptr;
238         Curr->BB = nullptr;
239       } else {
240         LeaderTableEntry *Next = Curr->Next;
241         Curr->Val = Next->Val;
242         Curr->BB = Next->BB;
243         Curr->Next = Next->Next;
244       }
245     }
246   }
247 
248   // List of critical edges to be split between iterations.
249   SmallVector<std::pair<Instruction *, unsigned>, 4> toSplit;
250 
251   // Helper functions of redundant load elimination
252   bool processLoad(LoadInst *L);
253   bool processNonLocalLoad(LoadInst *L);
254   bool processAssumeIntrinsic(IntrinsicInst *II);
255 
256   /// Given a local dependency (Def or Clobber) determine if a value is
257   /// available for the load.  Returns true if an value is known to be
258   /// available and populates Res.  Returns false otherwise.
259   bool AnalyzeLoadAvailability(LoadInst *LI, MemDepResult DepInfo,
260                                Value *Address, gvn::AvailableValue &Res);
261 
262   /// Given a list of non-local dependencies, determine if a value is
263   /// available for the load in each specified block.  If it is, add it to
264   /// ValuesPerBlock.  If not, add it to UnavailableBlocks.
265   void AnalyzeLoadAvailability(LoadInst *LI, LoadDepVect &Deps,
266                                AvailValInBlkVect &ValuesPerBlock,
267                                UnavailBlkVect &UnavailableBlocks);
268 
269   bool PerformLoadPRE(LoadInst *LI, AvailValInBlkVect &ValuesPerBlock,
270                       UnavailBlkVect &UnavailableBlocks);
271 
272   // Other helper routines
273   bool processInstruction(Instruction *I);
274   bool processBlock(BasicBlock *BB);
275   void dump(DenseMap<uint32_t, Value *> &d) const;
276   bool iterateOnFunction(Function &F);
277   bool performPRE(Function &F);
278   bool performScalarPRE(Instruction *I);
279   bool performScalarPREInsertion(Instruction *Instr, BasicBlock *Pred,
280                                  BasicBlock *Curr, unsigned int ValNo);
281   Value *findLeader(const BasicBlock *BB, uint32_t num);
282   void cleanupGlobalSets();
283   void fillImplicitControlFlowInfo(BasicBlock *BB);
284   void verifyRemoved(const Instruction *I) const;
285   bool splitCriticalEdges();
286   BasicBlock *splitCriticalEdges(BasicBlock *Pred, BasicBlock *Succ);
287   bool replaceOperandsForInBlockEquality(Instruction *I) const;
288   bool propagateEquality(Value *LHS, Value *RHS, const BasicBlockEdge &Root,
289                          bool DominatesByEdge);
290   bool processFoldableCondBr(BranchInst *BI);
291   void addDeadBlock(BasicBlock *BB);
292   void assignValNumForDeadCode();
293   void assignBlockRPONumber(Function &F);
294 };
295 
296 /// Create a legacy GVN pass. This also allows parameterizing whether or not
297 /// MemDep is enabled.
298 FunctionPass *createGVNPass(bool NoMemDepAnalysis = false);
299 
300 /// A simple and fast domtree-based GVN pass to hoist common expressions
301 /// from sibling branches.
302 struct GVNHoistPass : PassInfoMixin<GVNHoistPass> {
303   /// Run the pass over the function.
304   PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
305 };
306 
307 /// Uses an "inverted" value numbering to decide the similarity of
308 /// expressions and sinks similar expressions into successors.
309 struct GVNSinkPass : PassInfoMixin<GVNSinkPass> {
310   /// Run the pass over the function.
311   PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
312 };
313 
314 } // end namespace llvm
315 
316 #endif // LLVM_TRANSFORMS_SCALAR_GVN_H
317