LLVM  9.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 
163  ValueTable VN;
164 
165  /// A mapping from value numbers to lists of Value*'s that
166  /// have that value number. Use findLeader to query it.
167  struct LeaderTableEntry {
168  Value *Val;
169  const BasicBlock *BB;
170  LeaderTableEntry *Next;
171  };
173  BumpPtrAllocator TableAllocator;
174 
175  // Block-local map of equivalent values to their leader, does not
176  // propagate to any successors. Entries added mid-block are applied
177  // to the remaining instructions in the block.
178  SmallMapVector<Value *, Constant *, 4> ReplaceWithConstMap;
179  SmallVector<Instruction *, 8> InstrsToErase;
180 
181  // Map the block to reversed postorder traversal number. It is used to
182  // find back edge easily.
184 
185  // This is set 'true' initially and also when new blocks have been added to
186  // the function being analyzed. This boolean is used to control the updating
187  // of BlockRPONumber prior to accessing the contents of BlockRPONumber.
188  bool InvalidBlockRPONumbers = true;
189 
193 
194  bool runImpl(Function &F, AssumptionCache &RunAC, DominatorTree &RunDT,
195  const TargetLibraryInfo &RunTLI, AAResults &RunAA,
196  MemoryDependenceResults *RunMD, LoopInfo *LI,
198 
199  /// Push a new Value to the LeaderTable onto the list for its value number.
200  void addToLeaderTable(uint32_t N, Value *V, const BasicBlock *BB) {
201  LeaderTableEntry &Curr = LeaderTable[N];
202  if (!Curr.Val) {
203  Curr.Val = V;
204  Curr.BB = BB;
205  return;
206  }
207 
208  LeaderTableEntry *Node = TableAllocator.Allocate<LeaderTableEntry>();
209  Node->Val = V;
210  Node->BB = BB;
211  Node->Next = Curr.Next;
212  Curr.Next = Node;
213  }
214 
215  /// Scan the list of values corresponding to a given
216  /// value number, and remove the given instruction if encountered.
217  void removeFromLeaderTable(uint32_t N, Instruction *I, BasicBlock *BB) {
218  LeaderTableEntry *Prev = nullptr;
219  LeaderTableEntry *Curr = &LeaderTable[N];
220 
221  while (Curr && (Curr->Val != I || Curr->BB != BB)) {
222  Prev = Curr;
223  Curr = Curr->Next;
224  }
225 
226  if (!Curr)
227  return;
228 
229  if (Prev) {
230  Prev->Next = Curr->Next;
231  } else {
232  if (!Curr->Next) {
233  Curr->Val = nullptr;
234  Curr->BB = nullptr;
235  } else {
236  LeaderTableEntry *Next = Curr->Next;
237  Curr->Val = Next->Val;
238  Curr->BB = Next->BB;
239  Curr->Next = Next->Next;
240  }
241  }
242  }
243 
244  // List of critical edges to be split between iterations.
246 
247  // Helper functions of redundant load elimination
248  bool processLoad(LoadInst *L);
249  bool processNonLocalLoad(LoadInst *L);
250  bool processAssumeIntrinsic(IntrinsicInst *II);
251 
252  /// Given a local dependency (Def or Clobber) determine if a value is
253  /// available for the load. Returns true if an value is known to be
254  /// available and populates Res. Returns false otherwise.
255  bool AnalyzeLoadAvailability(LoadInst *LI, MemDepResult DepInfo,
257 
258  /// Given a list of non-local dependencies, determine if a value is
259  /// available for the load in each specified block. If it is, add it to
260  /// ValuesPerBlock. If not, add it to UnavailableBlocks.
261  void AnalyzeLoadAvailability(LoadInst *LI, LoadDepVect &Deps,
262  AvailValInBlkVect &ValuesPerBlock,
263  UnavailBlkVect &UnavailableBlocks);
264 
265  bool PerformLoadPRE(LoadInst *LI, AvailValInBlkVect &ValuesPerBlock,
266  UnavailBlkVect &UnavailableBlocks);
267 
268  // Other helper routines
269  bool processInstruction(Instruction *I);
270  bool processBlock(BasicBlock *BB);
271  void dump(DenseMap<uint32_t, Value *> &d) const;
272  bool iterateOnFunction(Function &F);
273  bool performPRE(Function &F);
274  bool performScalarPRE(Instruction *I);
275  bool performScalarPREInsertion(Instruction *Instr, BasicBlock *Pred,
276  BasicBlock *Curr, unsigned int ValNo);
277  Value *findLeader(const BasicBlock *BB, uint32_t num);
278  void cleanupGlobalSets();
279  void fillImplicitControlFlowInfo(BasicBlock *BB);
280  void verifyRemoved(const Instruction *I) const;
281  bool splitCriticalEdges();
282  BasicBlock *splitCriticalEdges(BasicBlock *Pred, BasicBlock *Succ);
283  bool replaceOperandsWithConsts(Instruction *I) const;
284  bool propagateEquality(Value *LHS, Value *RHS, const BasicBlockEdge &Root,
285  bool DominatesByEdge);
286  bool processFoldableCondBr(BranchInst *BI);
287  void addDeadBlock(BasicBlock *BB);
288  void assignValNumForDeadCode();
289  void assignBlockRPONumber(Function &F);
290 };
291 
292 /// Create a legacy GVN pass. This also allows parameterizing whether or not
293 /// loads are eliminated by the pass.
294 FunctionPass *createGVNPass(bool NoLoads = false);
295 
296 /// A simple and fast domtree-based GVN pass to hoist common expressions
297 /// from sibling branches.
298 struct GVNHoistPass : PassInfoMixin<GVNHoistPass> {
299  /// Run the pass over the function.
301 };
302 
303 /// Uses an "inverted" value numbering to decide the similarity of
304 /// expressions and sinks similar expressions into successors.
305 struct GVNSinkPass : PassInfoMixin<GVNSinkPass> {
306  /// Run the pass over the function.
308 };
309 
310 } // end namespace llvm
311 
312 #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:2591
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:305
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:298
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:709
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:107
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:124
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:841
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:211
#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:162
uint32_t getNextUnusedValueNumber()
Definition: GVN.h:147
LLVM Value Representation.
Definition: Value.h:72
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:1025
The optimization diagnostic interface.
A wrapper class for inspecting calls to intrinsic functions.
Definition: IntrinsicInst.h:43