LLVM  11.0.0git
GVN.h
Go to the documentation of this file.
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"
21 #include "llvm/ADT/SetVector.h"
22 #include "llvm/ADT/SmallVector.h"
26 #include "llvm/IR/Dominators.h"
27 #include "llvm/IR/InstrTypes.h"
28 #include "llvm/IR/PassManager.h"
29 #include "llvm/IR/ValueHandle.h"
30 #include "llvm/Support/Allocator.h"
31 #include "llvm/Support/Compiler.h"
32 #include <cstdint>
33 #include <utility>
34 #include <vector>
35 
36 namespace llvm {
37 
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 OptimizationRemarkEmitter;
50 class PHINode;
51 class TargetLibraryInfo;
52 class Value;
53 
54 /// A private "module" namespace for types and utilities used by GVN. These
55 /// are implementation details and should not be used by clients.
56 namespace gvn LLVM_LIBRARY_VISIBILITY {
57 
58 struct AvailableValue;
59 struct AvailableValueInBlock;
60 class GVNLegacyPass;
61 
62 } // end namespace gvn
63 
64 /// A set of parameters to control various transforms performed by GVN pass.
65 // Each of the optional boolean parameters can be set to:
66 /// true - enabling the transformation.
67 /// false - disabling the transformation.
68 /// None - relying on a global default.
69 /// Intended use is to create a default object, modify parameters with
70 /// additional setters and then pass it to GVN.
71 struct GVNOptions {
72  Optional<bool> AllowPRE = None;
73  Optional<bool> AllowLoadPRE = None;
74  Optional<bool> AllowLoadInLoopPRE = None;
75  Optional<bool> AllowMemDep = None;
76 
77  GVNOptions() = default;
78 
79  /// Enables or disables PRE in GVN.
80  GVNOptions &setPRE(bool PRE) {
81  AllowPRE = PRE;
82  return *this;
83  }
84 
85  /// Enables or disables PRE of loads in GVN.
86  GVNOptions &setLoadPRE(bool LoadPRE) {
87  AllowLoadPRE = LoadPRE;
88  return *this;
89  }
90 
91  GVNOptions &setLoadInLoopPRE(bool LoadInLoopPRE) {
92  AllowLoadInLoopPRE = LoadInLoopPRE;
93  return *this;
94  }
95 
96  /// Enables or disables use of MemDepAnalysis.
97  GVNOptions &setMemDep(bool MemDep) {
98  AllowMemDep = MemDep;
99  return *this;
100  }
101 };
102 
103 /// The core GVN pass object.
104 ///
105 /// FIXME: We should have a good summary of the GVN algorithm implemented by
106 /// this particular pass here.
107 class GVN : public PassInfoMixin<GVN> {
108  GVNOptions Options;
109 
110 public:
111  struct Expression;
112 
113  GVN(GVNOptions Options = {}) : Options(Options) {}
114 
115  /// Run the pass over the function.
117 
118  /// This removes the specified instruction from
119  /// our various maps and marks it for deletion.
121  VN.erase(I);
122  InstrsToErase.push_back(I);
123  }
124 
125  DominatorTree &getDominatorTree() const { return *DT; }
126  AliasAnalysis *getAliasAnalysis() const { return VN.getAliasAnalysis(); }
127  MemoryDependenceResults &getMemDep() const { return *MD; }
128 
129  bool isPREEnabled() const;
130  bool isLoadPREEnabled() const;
131  bool isLoadInLoopPREEnabled() const;
132  bool isMemDepEnabled() const;
133 
134  /// This class holds the mapping between values and value numbers. It is used
135  /// as an efficient mechanism to determine the expression-wise equivalence of
136  /// two values.
137  class ValueTable {
138  DenseMap<Value *, uint32_t> valueNumbering;
139  DenseMap<Expression, uint32_t> expressionNumbering;
140 
141  // Expressions is the vector of Expression. ExprIdx is the mapping from
142  // value number to the index of Expression in Expressions. We use it
143  // instead of a DenseMap because filling such mapping is faster than
144  // filling a DenseMap and the compile time is a little better.
145  uint32_t nextExprNumber = 0;
146 
147  std::vector<Expression> Expressions;
148  std::vector<uint32_t> ExprIdx;
149 
150  // Value number to PHINode mapping. Used for phi-translate in scalarpre.
151  DenseMap<uint32_t, PHINode *> NumberingPhi;
152 
153  // Cache for phi-translate in scalarpre.
154  using PhiTranslateMap =
156  PhiTranslateMap PhiTranslateTable;
157 
158  AliasAnalysis *AA = nullptr;
159  MemoryDependenceResults *MD = nullptr;
160  DominatorTree *DT = nullptr;
161 
162  uint32_t nextValueNumber = 1;
163 
164  Expression createExpr(Instruction *I);
165  Expression createCmpExpr(unsigned Opcode, CmpInst::Predicate Predicate,
166  Value *LHS, Value *RHS);
167  Expression createExtractvalueExpr(ExtractValueInst *EI);
168  uint32_t lookupOrAddCall(CallInst *C);
169  uint32_t phiTranslateImpl(const BasicBlock *BB, const BasicBlock *PhiBlock,
170  uint32_t Num, GVN &Gvn);
171  bool areCallValsEqual(uint32_t Num, uint32_t NewNum, const BasicBlock *Pred,
172  const BasicBlock *PhiBlock, GVN &Gvn);
173  std::pair<uint32_t, bool> assignExpNewValueNum(Expression &exp);
174  bool areAllValsInBB(uint32_t num, const BasicBlock *BB, GVN &Gvn);
175 
176  public:
177  ValueTable();
178  ValueTable(const ValueTable &Arg);
179  ValueTable(ValueTable &&Arg);
180  ~ValueTable();
181  ValueTable &operator=(const ValueTable &Arg);
182 
183  uint32_t lookupOrAdd(Value *V);
184  uint32_t lookup(Value *V, bool Verify = true) const;
185  uint32_t lookupOrAddCmp(unsigned Opcode, CmpInst::Predicate Pred,
186  Value *LHS, Value *RHS);
187  uint32_t phiTranslate(const BasicBlock *BB, const BasicBlock *PhiBlock,
188  uint32_t Num, GVN &Gvn);
189  void eraseTranslateCacheEntry(uint32_t Num, const BasicBlock &CurrBlock);
190  bool exists(Value *V) const;
191  void add(Value *V, uint32_t num);
192  void clear();
193  void erase(Value *v);
194  void setAliasAnalysis(AliasAnalysis *A) { AA = A; }
195  AliasAnalysis *getAliasAnalysis() const { return AA; }
196  void setMemDep(MemoryDependenceResults *M) { MD = M; }
197  void setDomTree(DominatorTree *D) { DT = D; }
198  uint32_t getNextUnusedValueNumber() { return nextValueNumber; }
199  void verifyRemoved(const Value *) const;
200  };
201 
202 private:
203  friend class gvn::GVNLegacyPass;
204  friend struct DenseMapInfo<Expression>;
205 
206  MemoryDependenceResults *MD = nullptr;
207  DominatorTree *DT = nullptr;
208  const TargetLibraryInfo *TLI = nullptr;
209  AssumptionCache *AC = nullptr;
210  SetVector<BasicBlock *> DeadBlocks;
211  OptimizationRemarkEmitter *ORE = nullptr;
212  ImplicitControlFlowTracking *ICF = nullptr;
213  LoopInfo *LI = nullptr;
214 
215  ValueTable VN;
216 
217  /// A mapping from value numbers to lists of Value*'s that
218  /// have that value number. Use findLeader to query it.
219  struct LeaderTableEntry {
220  Value *Val;
221  const BasicBlock *BB;
222  LeaderTableEntry *Next;
223  };
225  BumpPtrAllocator TableAllocator;
226 
227  // Block-local map of equivalent values to their leader, does not
228  // propagate to any successors. Entries added mid-block are applied
229  // to the remaining instructions in the block.
230  SmallMapVector<Value *, Value *, 4> ReplaceOperandsWithMap;
231  SmallVector<Instruction *, 8> InstrsToErase;
232 
233  // Map the block to reversed postorder traversal number. It is used to
234  // find back edge easily.
236 
237  // This is set 'true' initially and also when new blocks have been added to
238  // the function being analyzed. This boolean is used to control the updating
239  // of BlockRPONumber prior to accessing the contents of BlockRPONumber.
240  bool InvalidBlockRPONumbers = true;
241 
245 
246  bool runImpl(Function &F, AssumptionCache &RunAC, DominatorTree &RunDT,
247  const TargetLibraryInfo &RunTLI, AAResults &RunAA,
248  MemoryDependenceResults *RunMD, LoopInfo *LI,
250 
251  /// Push a new Value to the LeaderTable onto the list for its value number.
252  void addToLeaderTable(uint32_t N, Value *V, const BasicBlock *BB) {
253  LeaderTableEntry &Curr = LeaderTable[N];
254  if (!Curr.Val) {
255  Curr.Val = V;
256  Curr.BB = BB;
257  return;
258  }
259 
260  LeaderTableEntry *Node = TableAllocator.Allocate<LeaderTableEntry>();
261  Node->Val = V;
262  Node->BB = BB;
263  Node->Next = Curr.Next;
264  Curr.Next = Node;
265  }
266 
267  /// Scan the list of values corresponding to a given
268  /// value number, and remove the given instruction if encountered.
269  void removeFromLeaderTable(uint32_t N, Instruction *I, BasicBlock *BB) {
270  LeaderTableEntry *Prev = nullptr;
271  LeaderTableEntry *Curr = &LeaderTable[N];
272 
273  while (Curr && (Curr->Val != I || Curr->BB != BB)) {
274  Prev = Curr;
275  Curr = Curr->Next;
276  }
277 
278  if (!Curr)
279  return;
280 
281  if (Prev) {
282  Prev->Next = Curr->Next;
283  } else {
284  if (!Curr->Next) {
285  Curr->Val = nullptr;
286  Curr->BB = nullptr;
287  } else {
288  LeaderTableEntry *Next = Curr->Next;
289  Curr->Val = Next->Val;
290  Curr->BB = Next->BB;
291  Curr->Next = Next->Next;
292  }
293  }
294  }
295 
296  // List of critical edges to be split between iterations.
298 
299  // Helper functions of redundant load elimination
300  bool processLoad(LoadInst *L);
301  bool processNonLocalLoad(LoadInst *L);
302  bool processAssumeIntrinsic(IntrinsicInst *II);
303 
304  /// Given a local dependency (Def or Clobber) determine if a value is
305  /// available for the load. Returns true if an value is known to be
306  /// available and populates Res. Returns false otherwise.
307  bool AnalyzeLoadAvailability(LoadInst *LI, MemDepResult DepInfo,
309 
310  /// Given a list of non-local dependencies, determine if a value is
311  /// available for the load in each specified block. If it is, add it to
312  /// ValuesPerBlock. If not, add it to UnavailableBlocks.
313  void AnalyzeLoadAvailability(LoadInst *LI, LoadDepVect &Deps,
314  AvailValInBlkVect &ValuesPerBlock,
315  UnavailBlkVect &UnavailableBlocks);
316 
317  bool PerformLoadPRE(LoadInst *LI, AvailValInBlkVect &ValuesPerBlock,
318  UnavailBlkVect &UnavailableBlocks);
319 
320  // Other helper routines
321  bool processInstruction(Instruction *I);
322  bool processBlock(BasicBlock *BB);
323  void dump(DenseMap<uint32_t, Value *> &d) const;
324  bool iterateOnFunction(Function &F);
325  bool performPRE(Function &F);
326  bool performScalarPRE(Instruction *I);
327  bool performScalarPREInsertion(Instruction *Instr, BasicBlock *Pred,
328  BasicBlock *Curr, unsigned int ValNo);
329  Value *findLeader(const BasicBlock *BB, uint32_t num);
330  void cleanupGlobalSets();
331  void fillImplicitControlFlowInfo(BasicBlock *BB);
332  void verifyRemoved(const Instruction *I) const;
333  bool splitCriticalEdges();
334  BasicBlock *splitCriticalEdges(BasicBlock *Pred, BasicBlock *Succ);
335  bool replaceOperandsForInBlockEquality(Instruction *I) const;
336  bool propagateEquality(Value *LHS, Value *RHS, const BasicBlockEdge &Root,
337  bool DominatesByEdge);
338  bool processFoldableCondBr(BranchInst *BI);
339  void addDeadBlock(BasicBlock *BB);
340  void assignValNumForDeadCode();
341  void assignBlockRPONumber(Function &F);
342 };
343 
344 /// Create a legacy GVN pass. This also allows parameterizing whether or not
345 /// MemDep is enabled.
346 FunctionPass *createGVNPass(bool NoMemDepAnalysis = false);
347 
348 /// A simple and fast domtree-based GVN pass to hoist common expressions
349 /// from sibling branches.
350 struct GVNHoistPass : PassInfoMixin<GVNHoistPass> {
351  /// Run the pass over the function.
353 };
354 
355 /// Uses an "inverted" value numbering to decide the similarity of
356 /// expressions and sinks similar expressions into successors.
357 struct GVNSinkPass : PassInfoMixin<GVNSinkPass> {
358  /// Run the pass over the function.
360 };
361 
362 } // end namespace llvm
363 
364 #endif // LLVM_TRANSFORMS_SCALAR_GVN_H
uint64_t CallInst * C
void setDomTree(DominatorTree *D)
Definition: GVN.h:197
static bool runImpl(Function &F, TargetLibraryInfo &TLI, DominatorTree &DT)
This is the entry point for all transforms.
AliasAnalysis * getAliasAnalysis() const
Definition: GVN.h:195
Provides a lazy, caching interface for making common memory aliasing information queries, backed by LLVM&#39;s alias analysis passes.
This instruction extracts a struct member or array element value from an aggregate value...
AliasAnalysis * getAliasAnalysis() const
Definition: GVN.h:126
This class represents lattice values for constants.
Definition: AllocatorList.h:23
Various leaf nodes.
Definition: ISDOpcodes.h:63
Uses an "inverted" value numbering to decide the similarity of expressions and sinks similar expressi...
Definition: GVN.h:357
static bool lookup(const GsymReader &GR, DataExtractor &Data, uint64_t &Offset, uint64_t BaseAddr, uint64_t Addr, SourceLocations &SrcLocs, llvm::Error &Err)
A Lookup helper functions.
Definition: InlineInfo.cpp:108
This class represents a function call, abstracting a target machine&#39;s calling convention.
GVNOptions & setLoadInLoopPRE(bool LoadInLoopPRE)
Definition: GVN.h:91
A cache of @llvm.assume calls within a function.
void setAliasAnalysis(AliasAnalysis *A)
Definition: GVN.h:194
F(f)
An instruction for reading from memory.
Definition: Instructions.h:167
This file defines the BumpPtrAllocator interface.
gvn Early GVN Hoisting of Expressions
Definition: GVNHoist.cpp:1206
A simple and fast domtree-based GVN pass to hoist common expressions from sibling branches...
Definition: GVN.h:350
GVNOptions & setMemDep(bool MemDep)
Enables or disables use of MemDepAnalysis.
Definition: GVN.h:97
MemoryDependenceResults & getMemDep() const
Definition: GVN.h:127
A MapVector that performs no allocations if smaller than a certain size.
Definition: MapVector.h:232
ppc ctr loops PowerPC CTR Loops Verify
The core GVN pass object.
Definition: GVN.h:107
A CRTP mix-in to automatically provide informational APIs needed for passes.
Definition: PassManager.h:373
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree...
Definition: Dominators.h:144
void dump(const SparseBitVector< ElementSize > &LHS, raw_ostream &out)
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:154
LLVM Basic Block Representation.
Definition: BasicBlock.h:57
This class holds the mapping between values and value numbers.
Definition: GVN.h:137
Allocate memory in an ever growing pool, as if by bump-pointer.
Definition: Allocator.h:67
Conditional or Unconditional Branch instruction.
A set of parameters to control various transforms performed by GVN pass.
Definition: GVN.h:71
GVNOptions & setLoadPRE(bool LoadPRE)
Enables or disables PRE of loads in GVN.
Definition: GVN.h:86
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Definition: InstrTypes.h:725
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:281
amdgpu Simplify well known AMD library false FunctionCallee Value * Arg
#define LLVM_LIBRARY_VISIBILITY
LLVM_LIBRARY_VISIBILITY - If a class marked with this attribute is linked into a shared library...
Definition: Compiler.h:130
A memory dependence query can return one of three different answers.
DominatorTree & getDominatorTree() const
Definition: GVN.h:125
void markInstructionForDeletion(Instruction *I)
This removes the specified instruction from our various maps and marks it for deletion.
Definition: GVN.h:120
static uint64_t add(uint64_t LeftOp, uint64_t RightOp)
Definition: FileCheck.cpp:342
Provides information about what library functions are available for the current target.
Predicate
Predicate - These are "(BI << 5) | BO" for various predicates.
Definition: PPCPredicates.h:26
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
static void clear(coro::Shape &Shape)
Definition: Coroutines.cpp:225
LLVM_ATTRIBUTE_RETURNS_NONNULL LLVM_ATTRIBUTE_RETURNS_NOALIAS void * Allocate(size_t Size, Align Alignment)
Allocate space at the specified alignment.
Definition: Allocator.h:144
#define I(x, y, z)
Definition: MD5.cpp:59
#define N
void setMemDep(MemoryDependenceResults *M)
Definition: GVN.h:196
This class allows to keep track on instructions with implicit control flow.
Represents a particular available value that we know how to materialize.
Definition: GVN.cpp:166
uint32_t getNextUnusedValueNumber()
Definition: GVN.h:198
LLVM Value Representation.
Definition: Value.h:74
GVN(GVNOptions Options={})
Definition: GVN.h:113
A vector that has set insertion semantics.
Definition: SetVector.h:40
A container for analyses that lazily runs them and caches their results.
This header defines various interfaces for pass management in LLVM.
bool exists(const basic_file_status &status)
Does file exist?
Definition: Path.cpp:1063
GVNOptions & setPRE(bool PRE)
Enables or disables PRE in GVN.
Definition: GVN.h:80
The optimization diagnostic interface.
FunctionPass * createGVNPass(bool NoMemDepAnalysis=false)
Create a legacy GVN pass.
Definition: GVN.cpp:2770
A wrapper class for inspecting calls to intrinsic functions.
Definition: IntrinsicInst.h:44