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  bool areCallValsEqual(uint32_t Num, uint32_t NewNum, const BasicBlock *Pred,
124  const BasicBlock *PhiBlock, GVN &Gvn);
125  std::pair<uint32_t, bool> assignExpNewValueNum(Expression &exp);
126  bool areAllValsInBB(uint32_t num, const BasicBlock *BB, GVN &Gvn);
127 
128  public:
129  ValueTable();
130  ValueTable(const ValueTable &Arg);
131  ValueTable(ValueTable &&Arg);
132  ~ValueTable();
133 
134  uint32_t lookupOrAdd(Value *V);
135  uint32_t lookup(Value *V, bool Verify = true) const;
136  uint32_t lookupOrAddCmp(unsigned Opcode, CmpInst::Predicate Pred,
137  Value *LHS, Value *RHS);
138  uint32_t phiTranslate(const BasicBlock *BB, const BasicBlock *PhiBlock,
139  uint32_t Num, GVN &Gvn);
140  void eraseTranslateCacheEntry(uint32_t Num, const BasicBlock &CurrBlock);
141  bool exists(Value *V) const;
142  void add(Value *V, uint32_t num);
143  void clear();
144  void erase(Value *v);
145  void setAliasAnalysis(AliasAnalysis *A) { AA = A; }
146  AliasAnalysis *getAliasAnalysis() const { return AA; }
147  void setMemDep(MemoryDependenceResults *M) { MD = M; }
148  void setDomTree(DominatorTree *D) { DT = D; }
149  uint32_t getNextUnusedValueNumber() { return nextValueNumber; }
150  void verifyRemoved(const Value *) const;
151  };
152 
153 private:
154  friend class gvn::GVNLegacyPass;
155  friend struct DenseMapInfo<Expression>;
156 
158  DominatorTree *DT;
159  const TargetLibraryInfo *TLI;
160  AssumptionCache *AC;
161  SetVector<BasicBlock *> DeadBlocks;
164  LoopInfo *LI;
165 
166  ValueTable VN;
167 
168  /// A mapping from value numbers to lists of Value*'s that
169  /// have that value number. Use findLeader to query it.
170  struct LeaderTableEntry {
171  Value *Val;
172  const BasicBlock *BB;
173  LeaderTableEntry *Next;
174  };
176  BumpPtrAllocator TableAllocator;
177 
178  // Block-local map of equivalent values to their leader, does not
179  // propagate to any successors. Entries added mid-block are applied
180  // to the remaining instructions in the block.
181  SmallMapVector<Value *, Value *, 4> ReplaceOperandsWithMap;
182  SmallVector<Instruction *, 8> InstrsToErase;
183 
184  // Map the block to reversed postorder traversal number. It is used to
185  // find back edge easily.
187 
188  // This is set 'true' initially and also when new blocks have been added to
189  // the function being analyzed. This boolean is used to control the updating
190  // of BlockRPONumber prior to accessing the contents of BlockRPONumber.
191  bool InvalidBlockRPONumbers = true;
192 
196 
197  bool runImpl(Function &F, AssumptionCache &RunAC, DominatorTree &RunDT,
198  const TargetLibraryInfo &RunTLI, AAResults &RunAA,
199  MemoryDependenceResults *RunMD, LoopInfo *LI,
201 
202  /// Push a new Value to the LeaderTable onto the list for its value number.
203  void addToLeaderTable(uint32_t N, Value *V, const BasicBlock *BB) {
204  LeaderTableEntry &Curr = LeaderTable[N];
205  if (!Curr.Val) {
206  Curr.Val = V;
207  Curr.BB = BB;
208  return;
209  }
210 
211  LeaderTableEntry *Node = TableAllocator.Allocate<LeaderTableEntry>();
212  Node->Val = V;
213  Node->BB = BB;
214  Node->Next = Curr.Next;
215  Curr.Next = Node;
216  }
217 
218  /// Scan the list of values corresponding to a given
219  /// value number, and remove the given instruction if encountered.
220  void removeFromLeaderTable(uint32_t N, Instruction *I, BasicBlock *BB) {
221  LeaderTableEntry *Prev = nullptr;
222  LeaderTableEntry *Curr = &LeaderTable[N];
223 
224  while (Curr && (Curr->Val != I || Curr->BB != BB)) {
225  Prev = Curr;
226  Curr = Curr->Next;
227  }
228 
229  if (!Curr)
230  return;
231 
232  if (Prev) {
233  Prev->Next = Curr->Next;
234  } else {
235  if (!Curr->Next) {
236  Curr->Val = nullptr;
237  Curr->BB = nullptr;
238  } else {
239  LeaderTableEntry *Next = Curr->Next;
240  Curr->Val = Next->Val;
241  Curr->BB = Next->BB;
242  Curr->Next = Next->Next;
243  }
244  }
245  }
246 
247  // List of critical edges to be split between iterations.
249 
250  // Helper functions of redundant load elimination
251  bool processLoad(LoadInst *L);
252  bool processNonLocalLoad(LoadInst *L);
253  bool processAssumeIntrinsic(IntrinsicInst *II);
254 
255  /// Given a local dependency (Def or Clobber) determine if a value is
256  /// available for the load. Returns true if an value is known to be
257  /// available and populates Res. Returns false otherwise.
258  bool AnalyzeLoadAvailability(LoadInst *LI, MemDepResult DepInfo,
260 
261  /// Given a list of non-local dependencies, determine if a value is
262  /// available for the load in each specified block. If it is, add it to
263  /// ValuesPerBlock. If not, add it to UnavailableBlocks.
264  void AnalyzeLoadAvailability(LoadInst *LI, LoadDepVect &Deps,
265  AvailValInBlkVect &ValuesPerBlock,
266  UnavailBlkVect &UnavailableBlocks);
267 
268  bool PerformLoadPRE(LoadInst *LI, AvailValInBlkVect &ValuesPerBlock,
269  UnavailBlkVect &UnavailableBlocks);
270 
271  // Other helper routines
272  bool processInstruction(Instruction *I);
273  bool processBlock(BasicBlock *BB);
274  void dump(DenseMap<uint32_t, Value *> &d) const;
275  bool iterateOnFunction(Function &F);
276  bool performPRE(Function &F);
277  bool performScalarPRE(Instruction *I);
278  bool performScalarPREInsertion(Instruction *Instr, BasicBlock *Pred,
279  BasicBlock *Curr, unsigned int ValNo);
280  Value *findLeader(const BasicBlock *BB, uint32_t num);
281  void cleanupGlobalSets();
282  void fillImplicitControlFlowInfo(BasicBlock *BB);
283  void verifyRemoved(const Instruction *I) const;
284  bool splitCriticalEdges();
285  BasicBlock *splitCriticalEdges(BasicBlock *Pred, BasicBlock *Succ);
286  bool replaceOperandsForInBlockEquality(Instruction *I) const;
287  bool propagateEquality(Value *LHS, Value *RHS, const BasicBlockEdge &Root,
288  bool DominatesByEdge);
289  bool processFoldableCondBr(BranchInst *BI);
290  void addDeadBlock(BasicBlock *BB);
291  void assignValNumForDeadCode();
292  void assignBlockRPONumber(Function &F);
293 };
294 
295 /// Create a legacy GVN pass. This also allows parameterizing whether or not
296 /// loads are eliminated by the pass.
297 FunctionPass *createGVNPass(bool NoLoads = false);
298 
299 /// A simple and fast domtree-based GVN pass to hoist common expressions
300 /// from sibling branches.
301 struct GVNHoistPass : PassInfoMixin<GVNHoistPass> {
302  /// Run the pass over the function.
304 };
305 
306 /// Uses an "inverted" value numbering to decide the similarity of
307 /// expressions and sinks similar expressions into successors.
308 struct GVNSinkPass : PassInfoMixin<GVNSinkPass> {
309  /// Run the pass over the function.
311 };
312 
313 } // end namespace llvm
314 
315 #endif // LLVM_TRANSFORMS_SCALAR_GVN_H
uint64_t CallInst * C
void setDomTree(DominatorTree *D)
Definition: GVN.h:148
FunctionPass * createGVNPass(bool NoLoads=false)
Create a legacy GVN pass.
Definition: GVN.cpp:2712
static bool runImpl(Function &F, TargetLibraryInfo &TLI, DominatorTree &DT)
This is the entry point for all transforms.
AliasAnalysis * getAliasAnalysis() const
Definition: GVN.h:146
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:308
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:145
F(f)
An instruction for reading from memory.
Definition: Instructions.h:169
This file defines the MallocAllocator and BumpPtrAllocator interfaces.
gvn Early GVN Hoisting of Expressions
Definition: GVNHoist.cpp:1202
A simple and fast domtree-based GVN pass to hoist common expressions from sibling branches...
Definition: GVN.h:301
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: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:89
Allocate memory in an ever growing pool, as if by bump-pointer.
Definition: Allocator.h:141
Conditional or Unconditional Branch instruction.
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:124
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:215
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")
LLVM_ATTRIBUTE_RETURNS_NONNULL LLVM_ATTRIBUTE_RETURNS_NOALIAS void * Allocate(size_t Size, Align Alignment)
Allocate space at the specified alignment.
Definition: Allocator.h:215
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:147
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:149
LLVM Value Representation.
Definition: Value.h:74
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