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
33namespace llvm {
34
35class AAResults;
36class AssumeInst;
37class AssumptionCache;
38class BasicBlock;
39class BranchInst;
40class CallInst;
41class ExtractValueInst;
42class Function;
43class FunctionPass;
44class GetElementPtrInst;
45class ImplicitControlFlowTracking;
46class LoadInst;
47class LoopInfo;
48class MemDepResult;
49class MemoryDependenceResults;
50class MemorySSA;
51class MemorySSAUpdater;
52class NonLocalDepResult;
53class OptimizationRemarkEmitter;
54class PHINode;
55class TargetLibraryInfo;
56class 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.
59namespace LLVM_LIBRARY_VISIBILITY gvn {
60
61struct AvailableValue;
62struct AvailableValueInBlock;
63class 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.
74struct 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.
117class GVNPass : public PassInfoMixin<GVNPass> {
118  GVNOptions Options;
119
120public:
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
217private:
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  /// Given a critical edge from Pred to LoadBB, find a load instruction
333  /// which is identical to Load from another successor of Pred.
334  LoadInst *findLoadToHoistIntoPred(BasicBlock *Pred, BasicBlock *LoadBB,
335                                    LoadInst *Load);
336
337  bool PerformLoadPRE(LoadInst *Load, AvailValInBlkVect &ValuesPerBlock,
338                      UnavailBlkVect &UnavailableBlocks);
339
340  /// Try to replace a load which executes on each loop iteraiton with Phi
341  /// translation of load in preheader and load(s) in conditionally executed
342  /// paths.
343  bool performLoopLoadPRE(LoadInst *Load, AvailValInBlkVect &ValuesPerBlock,
344                          UnavailBlkVect &UnavailableBlocks);
345
346  /// Eliminates partially redundant \p Load, replacing it with \p
347  /// AvailableLoads (connected by Phis if needed).
348  void eliminatePartiallyRedundantLoad(
349      LoadInst *Load, AvailValInBlkVect &ValuesPerBlock,
350      MapVector<BasicBlock *, Value *> &AvailableLoads,
351      MapVector<BasicBlock *, LoadInst *> *CriticalEdgePredAndLoad);
352
353  // Other helper routines
354  bool processInstruction(Instruction *I);
355  bool processBlock(BasicBlock *BB);
356  void dump(DenseMap<uint32_t, Value *> &d) const;
357  bool iterateOnFunction(Function &F);
358  bool performPRE(Function &F);
359  bool performScalarPRE(Instruction *I);
360  bool performScalarPREInsertion(Instruction *Instr, BasicBlock *Pred,
361                                 BasicBlock *Curr, unsigned int ValNo);
362  Value *findLeader(const BasicBlock *BB, uint32_t num);
363  void cleanupGlobalSets();
364  void removeInstruction(Instruction *I);
365  void verifyRemoved(const Instruction *I) const;
366  bool splitCriticalEdges();
367  BasicBlock *splitCriticalEdges(BasicBlock *Pred, BasicBlock *Succ);
368  bool replaceOperandsForInBlockEquality(Instruction *I) const;
369  bool propagateEquality(Value *LHS, Value *RHS, const BasicBlockEdge &Root,
370                         bool DominatesByEdge);
371  bool processFoldableCondBr(BranchInst *BI);
372  void addDeadBlock(BasicBlock *BB);
373  void assignValNumForDeadCode();
374  void assignBlockRPONumber(Function &F);
375};
376
377/// Create a legacy GVN pass. This also allows parameterizing whether or not
378/// MemDep is enabled.
379FunctionPass *createGVNPass(bool NoMemDepAnalysis = false);
380
381/// A simple and fast domtree-based GVN pass to hoist common expressions
382/// from sibling branches.
383struct GVNHoistPass : PassInfoMixin<GVNHoistPass> {
384  /// Run the pass over the function.
385  PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
386};
387
388/// Uses an "inverted" value numbering to decide the similarity of
389/// expressions and sinks similar expressions into successors.
390struct GVNSinkPass : PassInfoMixin<GVNSinkPass> {
391  /// Run the pass over the function.
392  PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
393};
394
395} // end namespace llvm
396
397#endif // LLVM_TRANSFORMS_SCALAR_GVN_H
398