LLVM  10.0.0svn
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 /// The core GVN pass object.
65 ///
66 /// FIXME: We should have a good summary of the GVN algorithm implemented by
67 /// this particular pass here.
68 class GVN : public PassInfoMixin<GVN> {
69 public:
70  struct Expression;
71 
72  /// Run the pass over the function.
74 
75  /// This removes the specified instruction from
76  /// our various maps and marks it for deletion.
78  VN.erase(I);
79  InstrsToErase.push_back(I);
80  }
81 
82  DominatorTree &getDominatorTree() const { return *DT; }
83  AliasAnalysis *getAliasAnalysis() const { return VN.getAliasAnalysis(); }
84  MemoryDependenceResults &getMemDep() const { return *MD; }
85 
86  /// This class holds the mapping between values and value numbers. It is used
87  /// as an efficient mechanism to determine the expression-wise equivalence of
88  /// two values.
89  class ValueTable {
90  DenseMap<Value *, uint32_t> valueNumbering;
91  DenseMap<Expression, uint32_t> expressionNumbering;
92 
93  // Expressions is the vector of Expression. ExprIdx is the mapping from
94  // value number to the index of Expression in Expressions. We use it
95  // instead of a DenseMap because filling such mapping is faster than
96  // filling a DenseMap and the compile time is a little better.
97  uint32_t nextExprNumber;
98 
99  std::vector<Expression> Expressions;
100  std::vector<uint32_t> ExprIdx;
101 
102  // Value number to PHINode mapping. Used for phi-translate in scalarpre.
103  DenseMap<uint32_t, PHINode *> NumberingPhi;
104 
105  // Cache for phi-translate in scalarpre.
106  using PhiTranslateMap =
108  PhiTranslateMap PhiTranslateTable;
109 
110  AliasAnalysis *AA;
112  DominatorTree *DT;
113 
114  uint32_t nextValueNumber = 1;
115 
116  Expression createExpr(Instruction *I);
117  Expression createCmpExpr(unsigned Opcode, CmpInst::Predicate Predicate,
118  Value *LHS, Value *RHS);
119  Expression createExtractvalueExpr(ExtractValueInst *EI);
120  uint32_t lookupOrAddCall(CallInst *C);
121  uint32_t phiTranslateImpl(const BasicBlock *BB, const BasicBlock *PhiBlock,
122  uint32_t Num, GVN &Gvn);
123  std::pair<uint32_t, bool> assignExpNewValueNum(Expression &exp);
124  bool areAllValsInBB(uint32_t num, const BasicBlock *BB, GVN &Gvn);
125 
126  public:
127  ValueTable();
128  ValueTable(const ValueTable &Arg);
129  ValueTable(ValueTable &&Arg);
130  ~ValueTable();
131 
132  uint32_t lookupOrAdd(Value *V);
133  uint32_t lookup(Value *V, bool Verify = true) const;
134  uint32_t lookupOrAddCmp(unsigned Opcode, CmpInst::Predicate Pred,
135  Value *LHS, Value *RHS);
136  uint32_t phiTranslate(const BasicBlock *BB, const BasicBlock *PhiBlock,
137  uint32_t Num, GVN &Gvn);
138  void eraseTranslateCacheEntry(uint32_t Num, const BasicBlock &CurrBlock);
139  bool exists(Value *V) const;
140  void add(Value *V, uint32_t num);
141  void clear();
142  void erase(Value *v);
143  void setAliasAnalysis(AliasAnalysis *A) { AA = A; }
144  AliasAnalysis *getAliasAnalysis() const { return AA; }
145  void setMemDep(MemoryDependenceResults *M) { MD = M; }
146  void setDomTree(DominatorTree *D) { DT = D; }
147  uint32_t getNextUnusedValueNumber() { return nextValueNumber; }
148  void verifyRemoved(const Value *) const;
149  };
150 
151 private:
152  friend class gvn::GVNLegacyPass;
153  friend struct DenseMapInfo<Expression>;
154 
156  DominatorTree *DT;
157  const TargetLibraryInfo *TLI;
158  AssumptionCache *AC;
159  SetVector<BasicBlock *> DeadBlocks;
162  LoopInfo *LI;
163 
164  ValueTable VN;
165 
166  /// A mapping from value numbers to lists of Value*'s that
167  /// have that value number. Use findLeader to query it.
168  struct LeaderTableEntry {
169  Value *Val;
170  const BasicBlock *BB;
171  LeaderTableEntry *Next;
172  };
174  BumpPtrAllocator TableAllocator;
175 
176  // Block-local map of equivalent values to their leader, does not
177  // propagate to any successors. Entries added mid-block are applied
178  // to the remaining instructions in the block.
179  SmallMapVector<Value *, Constant *, 4> ReplaceWithConstMap;
180  SmallVector<Instruction *, 8> InstrsToErase;
181 
182  // Map the block to reversed postorder traversal number. It is used to
183  // find back edge easily.
185 
186  // This is set 'true' initially and also when new blocks have been added to
187  // the function being analyzed. This boolean is used to control the updating
188  // of BlockRPONumber prior to accessing the contents of BlockRPONumber.
189  bool InvalidBlockRPONumbers = true;
190 
194 
195  bool runImpl(Function &F, AssumptionCache &RunAC, DominatorTree &RunDT,
196  const TargetLibraryInfo &RunTLI, AAResults &RunAA,
197  MemoryDependenceResults *RunMD, LoopInfo *LI,
199 
200  /// Push a new Value to the LeaderTable onto the list for its value number.
201  void addToLeaderTable(uint32_t N, Value *V, const BasicBlock *BB) {
202  LeaderTableEntry &Curr = LeaderTable[N];
203  if (!Curr.Val) {
204  Curr.Val = V;
205  Curr.BB = BB;
206  return;
207  }
208 
209  LeaderTableEntry *Node = TableAllocator.Allocate<LeaderTableEntry>();
210  Node->Val = V;
211  Node->BB = BB;
212  Node->Next = Curr.Next;
213  Curr.Next = Node;
214  }
215 
216  /// Scan the list of values corresponding to a given
217  /// value number, and remove the given instruction if encountered.
218  void removeFromLeaderTable(uint32_t N, Instruction *I, BasicBlock *BB) {
219  LeaderTableEntry *Prev = nullptr;
220  LeaderTableEntry *Curr = &LeaderTable[N];
221 
222  while (Curr && (Curr->Val != I || Curr->BB != BB)) {
223  Prev = Curr;
224  Curr = Curr->Next;
225  }
226 
227  if (!Curr)
228  return;
229 
230  if (Prev) {
231  Prev->Next = Curr->Next;
232  } else {
233  if (!Curr->Next) {
234  Curr->Val = nullptr;
235  Curr->BB = nullptr;
236  } else {
237  LeaderTableEntry *Next = Curr->Next;
238  Curr->Val = Next->Val;
239  Curr->BB = Next->BB;
240  Curr->Next = Next->Next;
241  }
242  }
243  }
244 
245  // List of critical edges to be split between iterations.
247 
248  // Helper functions of redundant load elimination
249  bool processLoad(LoadInst *L);
250  bool processNonLocalLoad(LoadInst *L);
251  bool processAssumeIntrinsic(IntrinsicInst *II);
252 
253  /// Given a local dependency (Def or Clobber) determine if a value is
254  /// available for the load. Returns true if an value is known to be
255  /// available and populates Res. Returns false otherwise.
256  bool AnalyzeLoadAvailability(LoadInst *LI, MemDepResult DepInfo,
258 
259  /// Given a list of non-local dependencies, determine if a value is
260  /// available for the load in each specified block. If it is, add it to
261  /// ValuesPerBlock. If not, add it to UnavailableBlocks.
262  void AnalyzeLoadAvailability(LoadInst *LI, LoadDepVect &Deps,
263  AvailValInBlkVect &ValuesPerBlock,
264  UnavailBlkVect &UnavailableBlocks);
265 
266  bool PerformLoadPRE(LoadInst *LI, AvailValInBlkVect &ValuesPerBlock,
267  UnavailBlkVect &UnavailableBlocks);
268 
269  // Other helper routines
270  bool processInstruction(Instruction *I);
271  bool processBlock(BasicBlock *BB);
272  void dump(DenseMap<uint32_t, Value *> &d) const;
273  bool iterateOnFunction(Function &F);
274  bool performPRE(Function &F);
275  bool performScalarPRE(Instruction *I);
276  bool performScalarPREInsertion(Instruction *Instr, BasicBlock *Pred,
277  BasicBlock *Curr, unsigned int ValNo);
278  Value *findLeader(const BasicBlock *BB, uint32_t num);
279  void cleanupGlobalSets();
280  void fillImplicitControlFlowInfo(BasicBlock *BB);
281  void verifyRemoved(const Instruction *I) const;
282  bool splitCriticalEdges();
283  BasicBlock *splitCriticalEdges(BasicBlock *Pred, BasicBlock *Succ);
284  bool replaceOperandsWithConsts(Instruction *I) const;
285  bool propagateEquality(Value *LHS, Value *RHS, const BasicBlockEdge &Root,
286  bool DominatesByEdge);
287  bool processFoldableCondBr(BranchInst *BI);
288  void addDeadBlock(BasicBlock *BB);
289  void assignValNumForDeadCode();
290  void assignBlockRPONumber(Function &F);
291 };
292 
293 /// Create a legacy GVN pass. This also allows parameterizing whether or not
294 /// loads are eliminated by the pass.
295 FunctionPass *createGVNPass(bool NoLoads = false);
296 
297 /// A simple and fast domtree-based GVN pass to hoist common expressions
298 /// from sibling branches.
299 struct GVNHoistPass : PassInfoMixin<GVNHoistPass> {
300  /// Run the pass over the function.
302 };
303 
304 /// Uses an "inverted" value numbering to decide the similarity of
305 /// expressions and sinks similar expressions into successors.
306 struct GVNSinkPass : PassInfoMixin<GVNSinkPass> {
307  /// Run the pass over the function.
309 };
310 
311 } // end namespace llvm
312 
313 #endif // LLVM_TRANSFORMS_SCALAR_GVN_H
uint64_t CallInst * C
void setDomTree(DominatorTree *D)
Definition: GVN.h:146
FunctionPass * createGVNPass(bool NoLoads=false)
Create a legacy GVN pass.
Definition: GVN.cpp:2621
static bool runImpl(Function &F, TargetLibraryInfo &TLI, DominatorTree &DT)
This is the entry point for all transforms.
AliasAnalysis * getAliasAnalysis() const
Definition: GVN.h:144
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:83
This class represents lattice values for constants.
Definition: AllocatorList.h:23
Various leaf nodes.
Definition: ISDOpcodes.h:59
Uses an "inverted" value numbering to decide the similarity of expressions and sinks similar expressi...
Definition: GVN.h:306
This class represents a function call, abstracting a target machine&#39;s calling convention.
A cache of @llvm.assume calls within a function.
void setAliasAnalysis(AliasAnalysis *A)
Definition: GVN.h:143
F(f)
An instruction for reading from memory.
Definition: Instructions.h:167
This file defines the MallocAllocator and BumpPtrAllocator interfaces.
gvn Early GVN Hoisting of Expressions
Definition: GVNHoist.cpp:1203
A simple and fast domtree-based GVN pass to hoist common expressions from sibling branches...
Definition: GVN.h:299
MemoryDependenceResults & getMemDep() const
Definition: GVN.h:84
A MapVector that performs no allocations if smaller than a certain size.
Definition: MapVector.h:232
static const uint16_t * lookup(unsigned opcode, unsigned domain, ArrayRef< uint16_t[3]> Table)
ppc ctr loops PowerPC CTR Loops Verify
The core GVN pass object.
Definition: GVN.h:68
A CRTP mix-in to automatically provide informational APIs needed for passes.
Definition: PassManager.h:372
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:153
LLVM Basic Block Representation.
Definition: BasicBlock.h:57
This class holds the mapping between values and value numbers.
Definition: GVN.h:89
Allocate memory in an ever growing pool, as if by bump-pointer.
Definition: Allocator.h:140
Conditional or Unconditional Branch instruction.
LLVM_ATTRIBUTE_RETURNS_NONNULL LLVM_ATTRIBUTE_RETURNS_NOALIAS void * Allocate(size_t Size, size_t Alignment)
Allocate space at the specified alignment.
Definition: Allocator.h:214
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Definition: InstrTypes.h:732
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:284
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:115
A memory dependence query can return one of three different answers.
DominatorTree & getDominatorTree() const
Definition: GVN.h:82
void markInstructionForDeletion(Instruction *I)
This removes the specified instruction from our various maps and marks it for deletion.
Definition: GVN.h:77
static uint64_t add(uint64_t LeftOp, uint64_t RightOp)
Definition: FileCheck.cpp:243
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:837
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
#define I(x, y, z)
Definition: MD5.cpp:58
#define N
void setMemDep(MemoryDependenceResults *M)
Definition: GVN.h:145
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:163
uint32_t getNextUnusedValueNumber()
Definition: GVN.h:147
LLVM Value Representation.
Definition: Value.h:73
A vector that has set insertion semantics.
Definition: SetVector.h:40
This header defines various interfaces for pass management in LLVM.
bool exists(const basic_file_status &status)
Does file exist?
Definition: Path.cpp:1025
The optimization diagnostic interface.
A wrapper class for inspecting calls to intrinsic functions.
Definition: IntrinsicInst.h:43