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