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