LLVM  6.0.0svn
GVN.h
Go to the documentation of this file.
1 //===- GVN.h - Eliminate redundant values and loads -------------*- C++ -*-===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 /// \file
10 /// This file provides the interface for LLVM's Global Value Numbering pass
11 /// which eliminates fully redundant instructions. It also does somewhat Ad-Hoc
12 /// PRE and dead load elimination.
13 ///
14 //===----------------------------------------------------------------------===//
15 
16 #ifndef LLVM_TRANSFORMS_SCALAR_GVN_H
17 #define LLVM_TRANSFORMS_SCALAR_GVN_H
18 
19 #include "llvm/ADT/DenseMap.h"
20 #include "llvm/ADT/MapVector.h"
22 #include "llvm/ADT/SetVector.h"
23 #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/Support/Allocator.h"
30 #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  /// \brief 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;
161  // Maps a block to the topmost instruction with implicit control flow in it.
163  FirstImplicitControlFlowInsts;
164 
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 *, Constant *, 4> ReplaceWithConstMap;
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 
191 
192  bool runImpl(Function &F, AssumptionCache &RunAC, DominatorTree &RunDT,
193  const TargetLibraryInfo &RunTLI, AAResults &RunAA,
194  MemoryDependenceResults *RunMD, LoopInfo *LI,
196 
197  /// Push a new Value to the LeaderTable onto the list for its value number.
198  void addToLeaderTable(uint32_t N, Value *V, const BasicBlock *BB) {
199  LeaderTableEntry &Curr = LeaderTable[N];
200  if (!Curr.Val) {
201  Curr.Val = V;
202  Curr.BB = BB;
203  return;
204  }
205 
206  LeaderTableEntry *Node = TableAllocator.Allocate<LeaderTableEntry>();
207  Node->Val = V;
208  Node->BB = BB;
209  Node->Next = Curr.Next;
210  Curr.Next = Node;
211  }
212 
213  /// Scan the list of values corresponding to a given
214  /// value number, and remove the given instruction if encountered.
215  void removeFromLeaderTable(uint32_t N, Instruction *I, BasicBlock *BB) {
216  LeaderTableEntry *Prev = nullptr;
217  LeaderTableEntry *Curr = &LeaderTable[N];
218 
219  while (Curr && (Curr->Val != I || Curr->BB != BB)) {
220  Prev = Curr;
221  Curr = Curr->Next;
222  }
223 
224  if (!Curr)
225  return;
226 
227  if (Prev) {
228  Prev->Next = Curr->Next;
229  } else {
230  if (!Curr->Next) {
231  Curr->Val = nullptr;
232  Curr->BB = nullptr;
233  } else {
234  LeaderTableEntry *Next = Curr->Next;
235  Curr->Val = Next->Val;
236  Curr->BB = Next->BB;
237  Curr->Next = Next->Next;
238  }
239  }
240  }
241 
242  // List of critical edges to be split between iterations.
244 
245  // Helper functions of redundant load elimination
246  bool processLoad(LoadInst *L);
247  bool processNonLocalLoad(LoadInst *L);
248  bool processAssumeIntrinsic(IntrinsicInst *II);
249 
250  /// Given a local dependency (Def or Clobber) determine if a value is
251  /// available for the load. Returns true if an value is known to be
252  /// available and populates Res. Returns false otherwise.
253  bool AnalyzeLoadAvailability(LoadInst *LI, MemDepResult DepInfo,
255 
256  /// Given a list of non-local dependencies, determine if a value is
257  /// available for the load in each specified block. If it is, add it to
258  /// ValuesPerBlock. If not, add it to UnavailableBlocks.
259  void AnalyzeLoadAvailability(LoadInst *LI, LoadDepVect &Deps,
260  AvailValInBlkVect &ValuesPerBlock,
261  UnavailBlkVect &UnavailableBlocks);
262 
263  bool PerformLoadPRE(LoadInst *LI, AvailValInBlkVect &ValuesPerBlock,
264  UnavailBlkVect &UnavailableBlocks);
265 
266  // Other helper routines
267  bool processInstruction(Instruction *I);
268  bool processBlock(BasicBlock *BB);
269  void dump(DenseMap<uint32_t, Value *> &d) const;
270  bool iterateOnFunction(Function &F);
271  bool performPRE(Function &F);
272  bool performScalarPRE(Instruction *I);
273  bool performScalarPREInsertion(Instruction *Instr, BasicBlock *Pred,
274  BasicBlock *Curr, unsigned int ValNo);
275  Value *findLeader(const BasicBlock *BB, uint32_t num);
276  void cleanupGlobalSets();
277  void fillImplicitControlFlowInfo(BasicBlock *BB);
278  void verifyRemoved(const Instruction *I) const;
279  bool splitCriticalEdges();
280  BasicBlock *splitCriticalEdges(BasicBlock *Pred, BasicBlock *Succ);
281  bool replaceOperandsWithConsts(Instruction *I) const;
282  bool propagateEquality(Value *LHS, Value *RHS, const BasicBlockEdge &Root,
283  bool DominatesByEdge);
284  bool processFoldableCondBr(BranchInst *BI);
285  void addDeadBlock(BasicBlock *BB);
286  void assignValNumForDeadCode();
287  void assignBlockRPONumber(Function &F);
288 };
289 
290 /// Create a legacy GVN pass. This also allows parameterizing whether or not
291 /// loads are eliminated by the pass.
292 FunctionPass *createGVNPass(bool NoLoads = false);
293 
294 /// \brief A simple and fast domtree-based GVN pass to hoist common expressions
295 /// from sibling branches.
296 struct GVNHoistPass : PassInfoMixin<GVNHoistPass> {
297  /// \brief Run the pass over the function.
299 };
300 
301 /// \brief Uses an "inverted" value numbering to decide the similarity of
302 /// expressions and sinks similar expressions into successors.
303 struct GVNSinkPass : PassInfoMixin<GVNSinkPass> {
304  /// \brief Run the pass over the function.
306 };
307 
308 } // end namespace llvm
309 
310 #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:2648
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
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
Various leaf nodes.
Definition: ISDOpcodes.h:60
Uses an "inverted" value numbering to decide the similarity of expressions and sinks similar expressi...
Definition: GVN.h:303
This class represents a function call, abstracting a target machine&#39;s calling convention.
A cache of .assume calls within a function.
void setAliasAnalysis(AliasAnalysis *A)
Definition: GVN.h:143
F(f)
An instruction for reading from memory.
Definition: Instructions.h:164
This file defines the MallocAllocator and BumpPtrAllocator interfaces.
gvn Early GVN Hoisting of Expressions
Definition: GVNHoist.cpp:1204
A simple and fast domtree-based GVN pass to hoist common expressions from sibling branches...
Definition: GVN.h:296
static bool runImpl(CallGraphSCC &SCC, AARGetterT AARGetter)
MemoryDependenceResults & getMemDep() const
Definition: GVN.h:84
A MapVector that performs no allocations if smaller than a certain size.
Definition: MapVector.h:229
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:365
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree...
Definition: Dominators.h:140
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:59
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:138
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:212
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Definition: InstrTypes.h:853
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:285
#define LLVM_LIBRARY_VISIBILITY
LLVM_LIBRARY_VISIBILITY - If a class marked with this attribute is linked into a shared library...
Definition: Compiler.h:105
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
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:864
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:27
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
static void clear(coro::Shape &Shape)
Definition: Coroutines.cpp:210
amdgpu Simplify well known AMD library false Value Value * Arg
#define I(x, y, z)
Definition: MD5.cpp:58
#define N
void setMemDep(MemoryDependenceResults *M)
Definition: GVN.h:145
Represents a particular available value that we know how to materialize.
Definition: GVN.cpp:155
uint32_t getNextUnusedValueNumber()
Definition: GVN.h:147
LLVM Value Representation.
Definition: Value.h:73
A vector that has set insertion semantics.
Definition: SetVector.h:41
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:1033
The optimization diagnostic interface.
A wrapper class for inspecting calls to intrinsic functions.
Definition: IntrinsicInst.h:44