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 <optional>
30 #include <utility>
31 #include <vector>
32 
33 namespace llvm {
34 
35 class AAResults;
36 class AssumeInst;
37 class AssumptionCache;
38 class BasicBlock;
39 class BranchInst;
40 class CallInst;
41 class ExtractValueInst;
42 class Function;
43 class FunctionPass;
44 class GetElementPtrInst;
45 class ImplicitControlFlowTracking;
46 class LoadInst;
47 class LoopInfo;
48 class MemDepResult;
49 class MemoryDependenceResults;
50 class MemorySSA;
51 class MemorySSAUpdater;
52 class NonLocalDepResult;
53 class OptimizationRemarkEmitter;
54 class PHINode;
55 class TargetLibraryInfo;
56 class Value;
57 /// A private "module" namespace for types and utilities used by GVN. These
58 /// are implementation details and should not be used by clients.
59 namespace gvn LLVM_LIBRARY_VISIBILITY {
60 
61 struct AvailableValue;
62 struct AvailableValueInBlock;
63 class GVNLegacyPass;
64 
65 } // end namespace gvn
66 
67 /// A set of parameters to control various transforms performed by GVN pass.
68 //  Each of the optional boolean parameters can be set to:
69 ///      true - enabling the transformation.
70 ///      false - disabling the transformation.
71 ///      None - relying on a global default.
72 /// Intended use is to create a default object, modify parameters with
73 /// additional setters and then pass it to GVN.
74 struct GVNOptions {
75   std::optional<bool> AllowPRE;
76   std::optional<bool> AllowLoadPRE;
77   std::optional<bool> AllowLoadInLoopPRE;
78   std::optional<bool> AllowLoadPRESplitBackedge;
79   std::optional<bool> AllowMemDep;
80 
81   GVNOptions() = default;
82 
83   /// Enables or disables PRE in GVN.
84   GVNOptions &setPRE(bool PRE) {
85     AllowPRE = PRE;
86     return *this;
87   }
88 
89   /// Enables or disables PRE of loads in GVN.
90   GVNOptions &setLoadPRE(bool LoadPRE) {
91     AllowLoadPRE = LoadPRE;
92     return *this;
93   }
94 
95   GVNOptions &setLoadInLoopPRE(bool LoadInLoopPRE) {
96     AllowLoadInLoopPRE = LoadInLoopPRE;
97     return *this;
98   }
99 
100   /// Enables or disables PRE of loads in GVN.
101   GVNOptions &setLoadPRESplitBackedge(bool LoadPRESplitBackedge) {
102     AllowLoadPRESplitBackedge = LoadPRESplitBackedge;
103     return *this;
104   }
105 
106   /// Enables or disables use of MemDepAnalysis.
107   GVNOptions &setMemDep(bool MemDep) {
108     AllowMemDep = MemDep;
109     return *this;
110   }
111 };
112 
113 /// The core GVN pass object.
114 ///
115 /// FIXME: We should have a good summary of the GVN algorithm implemented by
116 /// this particular pass here.
117 class GVNPass : public PassInfoMixin<GVNPass> {
118   GVNOptions Options;
119 
120 public:
121   struct Expression;
122 
123   GVNPass(GVNOptions Options = {}) : Options(Options) {}
124 
125   /// Run the pass over the function.
126   PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
127 
128   void printPipeline(raw_ostream &OS,
129                      function_ref<StringRef(StringRef)> MapClassName2PassName);
130 
131   /// This removes the specified instruction from
132   /// our various maps and marks it for deletion.
133   void markInstructionForDeletion(Instruction *I) {
134     VN.erase(I);
135     InstrsToErase.push_back(I);
136   }
137 
138   DominatorTree &getDominatorTree() const { return *DT; }
139   AAResults *getAliasAnalysis() const { return VN.getAliasAnalysis(); }
140   MemoryDependenceResults &getMemDep() const { return *MD; }
141 
142   bool isPREEnabled() const;
143   bool isLoadPREEnabled() const;
144   bool isLoadInLoopPREEnabled() const;
145   bool isLoadPRESplitBackedgeEnabled() const;
146   bool isMemDepEnabled() const;
147 
148   /// This class holds the mapping between values and value numbers.  It is used
149   /// as an efficient mechanism to determine the expression-wise equivalence of
150   /// two values.
151   class ValueTable {
152     DenseMap<Value *, uint32_t> valueNumbering;
153     DenseMap<Expression, uint32_t> expressionNumbering;
154 
155     // Expressions is the vector of Expression. ExprIdx is the mapping from
156     // value number to the index of Expression in Expressions. We use it
157     // instead of a DenseMap because filling such mapping is faster than
158     // filling a DenseMap and the compile time is a little better.
159     uint32_t nextExprNumber = 0;
160 
161     std::vector<Expression> Expressions;
162     std::vector<uint32_t> ExprIdx;
163 
164     // Value number to PHINode mapping. Used for phi-translate in scalarpre.
165     DenseMap<uint32_t, PHINode *> NumberingPhi;
166 
167     // Cache for phi-translate in scalarpre.
168     using PhiTranslateMap =
169         DenseMap<std::pair<uint32_t, const BasicBlock *>, uint32_t>;
170     PhiTranslateMap PhiTranslateTable;
171 
172     AAResults *AA = nullptr;
173     MemoryDependenceResults *MD = nullptr;
174     DominatorTree *DT = nullptr;
175 
176     uint32_t nextValueNumber = 1;
177 
178     Expression createExpr(Instruction *I);
179     Expression createCmpExpr(unsigned Opcode, CmpInst::Predicate Predicate,
180                              Value *LHS, Value *RHS);
181     Expression createExtractvalueExpr(ExtractValueInst *EI);
182     Expression createGEPExpr(GetElementPtrInst *GEP);
183     uint32_t lookupOrAddCall(CallInst *C);
184     uint32_t phiTranslateImpl(const BasicBlock *BB, const BasicBlock *PhiBlock,
185                               uint32_t Num, GVNPass &Gvn);
186     bool areCallValsEqual(uint32_t Num, uint32_t NewNum, const BasicBlock *Pred,
187                           const BasicBlock *PhiBlock, GVNPass &Gvn);
188     std::pair<uint32_t, bool> assignExpNewValueNum(Expression &exp);
189     bool areAllValsInBB(uint32_t num, const BasicBlock *BB, GVNPass &Gvn);
190 
191   public:
192     ValueTable();
193     ValueTable(const ValueTable &Arg);
194     ValueTable(ValueTable &&Arg);
195     ~ValueTable();
196     ValueTable &operator=(const ValueTable &Arg);
197 
198     uint32_t lookupOrAdd(Value *V);
199     uint32_t lookup(Value *V, bool Verify = true) const;
200     uint32_t lookupOrAddCmp(unsigned Opcode, CmpInst::Predicate Pred,
201                             Value *LHS, Value *RHS);
202     uint32_t phiTranslate(const BasicBlock *BB, const BasicBlock *PhiBlock,
203                           uint32_t Num, GVNPass &Gvn);
204     void eraseTranslateCacheEntry(uint32_t Num, const BasicBlock &CurrBlock);
205     bool exists(Value *V) const;
206     void add(Value *V, uint32_t num);
207     void clear();
208     void erase(Value *v);
209     void setAliasAnalysis(AAResults *A) { AA = A; }
210     AAResults *getAliasAnalysis() const { return AA; }
211     void setMemDep(MemoryDependenceResults *M) { MD = M; }
212     void setDomTree(DominatorTree *D) { DT = D; }
213     uint32_t getNextUnusedValueNumber() { return nextValueNumber; }
214     void verifyRemoved(const Value *) const;
215   };
216 
217 private:
218   friend class gvn::GVNLegacyPass;
219   friend struct DenseMapInfo<Expression>;
220 
221   MemoryDependenceResults *MD = nullptr;
222   DominatorTree *DT = nullptr;
223   const TargetLibraryInfo *TLI = nullptr;
224   AssumptionCache *AC = nullptr;
225   SetVector<BasicBlock *> DeadBlocks;
226   OptimizationRemarkEmitter *ORE = nullptr;
227   ImplicitControlFlowTracking *ICF = nullptr;
228   LoopInfo *LI = nullptr;
229   MemorySSAUpdater *MSSAU = nullptr;
230 
231   ValueTable VN;
232 
233   /// A mapping from value numbers to lists of Value*'s that
234   /// have that value number.  Use findLeader to query it.
235   struct LeaderTableEntry {
236     Value *Val;
237     const BasicBlock *BB;
238     LeaderTableEntry *Next;
239   };
240   DenseMap<uint32_t, LeaderTableEntry> LeaderTable;
241   BumpPtrAllocator TableAllocator;
242 
243   // Block-local map of equivalent values to their leader, does not
244   // propagate to any successors. Entries added mid-block are applied
245   // to the remaining instructions in the block.
246   SmallMapVector<Value *, Value *, 4> ReplaceOperandsWithMap;
247   SmallVector<Instruction *, 8> InstrsToErase;
248 
249   // Map the block to reversed postorder traversal number. It is used to
250   // find back edge easily.
251   DenseMap<AssertingVH<BasicBlock>, uint32_t> BlockRPONumber;
252 
253   // This is set 'true' initially and also when new blocks have been added to
254   // the function being analyzed. This boolean is used to control the updating
255   // of BlockRPONumber prior to accessing the contents of BlockRPONumber.
256   bool InvalidBlockRPONumbers = true;
257 
258   using LoadDepVect = SmallVector<NonLocalDepResult, 64>;
259   using AvailValInBlkVect = SmallVector<gvn::AvailableValueInBlock, 64>;
260   using UnavailBlkVect = SmallVector<BasicBlock *, 64>;
261 
262   bool runImpl(Function &F, AssumptionCache &RunAC, DominatorTree &RunDT,
263                const TargetLibraryInfo &RunTLI, AAResults &RunAA,
264                MemoryDependenceResults *RunMD, LoopInfo *LI,
265                OptimizationRemarkEmitter *ORE, MemorySSA *MSSA = nullptr);
266 
267   /// Push a new Value to the LeaderTable onto the list for its value number.
268   void addToLeaderTable(uint32_t N, Value *V, const BasicBlock *BB) {
269     LeaderTableEntry &Curr = LeaderTable[N];
270     if (!Curr.Val) {
271       Curr.Val = V;
272       Curr.BB = BB;
273       return;
274     }
275 
276     LeaderTableEntry *Node = TableAllocator.Allocate<LeaderTableEntry>();
277     Node->Val = V;
278     Node->BB = BB;
279     Node->Next = Curr.Next;
280     Curr.Next = Node;
281   }
282 
283   /// Scan the list of values corresponding to a given
284   /// value number, and remove the given instruction if encountered.
285   void removeFromLeaderTable(uint32_t N, Instruction *I, BasicBlock *BB) {
286     LeaderTableEntry *Prev = nullptr;
287     LeaderTableEntry *Curr = &LeaderTable[N];
288 
289     while (Curr && (Curr->Val != I || Curr->BB != BB)) {
290       Prev = Curr;
291       Curr = Curr->Next;
292     }
293 
294     if (!Curr)
295       return;
296 
297     if (Prev) {
298       Prev->Next = Curr->Next;
299     } else {
300       if (!Curr->Next) {
301         Curr->Val = nullptr;
302         Curr->BB = nullptr;
303       } else {
304         LeaderTableEntry *Next = Curr->Next;
305         Curr->Val = Next->Val;
306         Curr->BB = Next->BB;
307         Curr->Next = Next->Next;
308       }
309     }
310   }
311 
312   // List of critical edges to be split between iterations.
313   SmallVector<std::pair<Instruction *, unsigned>, 4> toSplit;
314 
315   // Helper functions of redundant load elimination
316   bool processLoad(LoadInst *L);
317   bool processNonLocalLoad(LoadInst *L);
318   bool processAssumeIntrinsic(AssumeInst *II);
319 
320   /// Given a local dependency (Def or Clobber) determine if a value is
321   /// available for the load.
322   std::optional<gvn::AvailableValue>
323   AnalyzeLoadAvailability(LoadInst *Load, MemDepResult DepInfo, Value *Address);
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