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