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