LLVM  13.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"
25 #include "llvm/IR/Dominators.h"
26 #include "llvm/IR/InstrTypes.h"
27 #include "llvm/IR/PassManager.h"
28 #include "llvm/IR/ValueHandle.h"
29 #include "llvm/Support/Allocator.h"
30 #include "llvm/Support/Compiler.h"
31 #include <cstdint>
32 #include <utility>
33 #include <vector>
34 
35 namespace llvm {
36 
37 class AAResults;
38 class AssumeInst;
39 class AssumptionCache;
40 class BasicBlock;
41 class BranchInst;
42 class CallInst;
43 class Constant;
44 class ExtractValueInst;
45 class Function;
46 class FunctionPass;
47 class IntrinsicInst;
48 class LoadInst;
49 class LoopInfo;
50 class MemorySSA;
51 class MemorySSAUpdater;
52 class OptimizationRemarkEmitter;
53 class PHINode;
54 class TargetLibraryInfo;
55 class Value;
56 /// A private "module" namespace for types and utilities used by GVN. These
57 /// are implementation details and should not be used by clients.
58 namespace gvn LLVM_LIBRARY_VISIBILITY {
59 
60 struct AvailableValue;
61 struct AvailableValueInBlock;
62 class GVNLegacyPass;
63 
64 } // end namespace gvn
65 
66 /// A set of parameters to control various transforms performed by GVN pass.
67 // Each of the optional boolean parameters can be set to:
68 /// true - enabling the transformation.
69 /// false - disabling the transformation.
70 /// None - relying on a global default.
71 /// Intended use is to create a default object, modify parameters with
72 /// additional setters and then pass it to GVN.
73 struct GVNOptions {
79 
80  GVNOptions() = default;
81 
82  /// Enables or disables PRE in GVN.
83  GVNOptions &setPRE(bool PRE) {
84  AllowPRE = PRE;
85  return *this;
86  }
87 
88  /// Enables or disables PRE of loads in GVN.
89  GVNOptions &setLoadPRE(bool LoadPRE) {
90  AllowLoadPRE = LoadPRE;
91  return *this;
92  }
93 
94  GVNOptions &setLoadInLoopPRE(bool LoadInLoopPRE) {
95  AllowLoadInLoopPRE = LoadInLoopPRE;
96  return *this;
97  }
98 
99  /// Enables or disables PRE of loads in GVN.
100  GVNOptions &setLoadPRESplitBackedge(bool LoadPRESplitBackedge) {
101  AllowLoadPRESplitBackedge = LoadPRESplitBackedge;
102  return *this;
103  }
104 
105  /// Enables or disables use of MemDepAnalysis.
106  GVNOptions &setMemDep(bool MemDep) {
107  AllowMemDep = MemDep;
108  return *this;
109  }
110 };
111 
112 /// The core GVN pass object.
113 ///
114 /// FIXME: We should have a good summary of the GVN algorithm implemented by
115 /// this particular pass here.
116 class GVN : public PassInfoMixin<GVN> {
117  GVNOptions Options;
118 
119 public:
120  struct Expression;
121 
122  GVN(GVNOptions Options = {}) : Options(Options) {}
123 
124  /// Run the pass over the function.
125  PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
126 
127  /// This removes the specified instruction from
128  /// our various maps and marks it for deletion.
130  VN.erase(I);
131  InstrsToErase.push_back(I);
132  }
133 
134  DominatorTree &getDominatorTree() const { return *DT; }
135  AAResults *getAliasAnalysis() const { return VN.getAliasAnalysis(); }
136  MemoryDependenceResults &getMemDep() const { return *MD; }
137 
138  bool isPREEnabled() const;
139  bool isLoadPREEnabled() const;
140  bool isLoadInLoopPREEnabled() const;
141  bool isLoadPRESplitBackedgeEnabled() const;
142  bool isMemDepEnabled() const;
143 
144  /// This class holds the mapping between values and value numbers. It is used
145  /// as an efficient mechanism to determine the expression-wise equivalence of
146  /// two values.
147  class ValueTable {
148  DenseMap<Value *, uint32_t> valueNumbering;
149  DenseMap<Expression, uint32_t> expressionNumbering;
150 
151  // Expressions is the vector of Expression. ExprIdx is the mapping from
152  // value number to the index of Expression in Expressions. We use it
153  // instead of a DenseMap because filling such mapping is faster than
154  // filling a DenseMap and the compile time is a little better.
155  uint32_t nextExprNumber = 0;
156 
157  std::vector<Expression> Expressions;
158  std::vector<uint32_t> ExprIdx;
159 
160  // Value number to PHINode mapping. Used for phi-translate in scalarpre.
161  DenseMap<uint32_t, PHINode *> NumberingPhi;
162 
163  // Cache for phi-translate in scalarpre.
164  using PhiTranslateMap =
166  PhiTranslateMap PhiTranslateTable;
167 
168  AAResults *AA = nullptr;
169  MemoryDependenceResults *MD = nullptr;
170  DominatorTree *DT = nullptr;
171 
172  uint32_t nextValueNumber = 1;
173 
174  Expression createExpr(Instruction *I);
175  Expression createCmpExpr(unsigned Opcode, CmpInst::Predicate Predicate,
176  Value *LHS, Value *RHS);
177  Expression createExtractvalueExpr(ExtractValueInst *EI);
178  uint32_t lookupOrAddCall(CallInst *C);
179  uint32_t phiTranslateImpl(const BasicBlock *BB, const BasicBlock *PhiBlock,
180  uint32_t Num, GVN &Gvn);
181  bool areCallValsEqual(uint32_t Num, uint32_t NewNum, const BasicBlock *Pred,
182  const BasicBlock *PhiBlock, GVN &Gvn);
183  std::pair<uint32_t, bool> assignExpNewValueNum(Expression &exp);
184  bool areAllValsInBB(uint32_t num, const BasicBlock *BB, GVN &Gvn);
185 
186  public:
187  ValueTable();
188  ValueTable(const ValueTable &Arg);
190  ~ValueTable();
192 
194  uint32_t lookup(Value *V, bool Verify = true) const;
195  uint32_t lookupOrAddCmp(unsigned Opcode, CmpInst::Predicate Pred,
196  Value *LHS, Value *RHS);
197  uint32_t phiTranslate(const BasicBlock *BB, const BasicBlock *PhiBlock,
198  uint32_t Num, GVN &Gvn);
199  void eraseTranslateCacheEntry(uint32_t Num, const BasicBlock &CurrBlock);
200  bool exists(Value *V) const;
201  void add(Value *V, uint32_t num);
202  void clear();
203  void erase(Value *v);
204  void setAliasAnalysis(AAResults *A) { AA = A; }
205  AAResults *getAliasAnalysis() const { return AA; }
207  void setDomTree(DominatorTree *D) { DT = D; }
208  uint32_t getNextUnusedValueNumber() { return nextValueNumber; }
209  void verifyRemoved(const Value *) const;
210  };
211 
212 private:
213  friend class gvn::GVNLegacyPass;
214  friend struct DenseMapInfo<Expression>;
215 
216  MemoryDependenceResults *MD = nullptr;
217  DominatorTree *DT = nullptr;
218  const TargetLibraryInfo *TLI = nullptr;
219  AssumptionCache *AC = nullptr;
220  SetVector<BasicBlock *> DeadBlocks;
221  OptimizationRemarkEmitter *ORE = nullptr;
222  ImplicitControlFlowTracking *ICF = nullptr;
223  LoopInfo *LI = nullptr;
224  MemorySSAUpdater *MSSAU = nullptr;
225 
226  ValueTable VN;
227 
228  /// A mapping from value numbers to lists of Value*'s that
229  /// have that value number. Use findLeader to query it.
230  struct LeaderTableEntry {
231  Value *Val;
232  const BasicBlock *BB;
233  LeaderTableEntry *Next;
234  };
236  BumpPtrAllocator TableAllocator;
237 
238  // Block-local map of equivalent values to their leader, does not
239  // propagate to any successors. Entries added mid-block are applied
240  // to the remaining instructions in the block.
241  SmallMapVector<Value *, Value *, 4> ReplaceOperandsWithMap;
242  SmallVector<Instruction *, 8> InstrsToErase;
243 
244  // Map the block to reversed postorder traversal number. It is used to
245  // find back edge easily.
247 
248  // This is set 'true' initially and also when new blocks have been added to
249  // the function being analyzed. This boolean is used to control the updating
250  // of BlockRPONumber prior to accessing the contents of BlockRPONumber.
251  bool InvalidBlockRPONumbers = true;
252 
253  using LoadDepVect = SmallVector<NonLocalDepResult, 64>;
254  using AvailValInBlkVect = SmallVector<gvn::AvailableValueInBlock, 64>;
255  using UnavailBlkVect = SmallVector<BasicBlock *, 64>;
256 
257  bool runImpl(Function &F, AssumptionCache &RunAC, DominatorTree &RunDT,
258  const TargetLibraryInfo &RunTLI, AAResults &RunAA,
259  MemoryDependenceResults *RunMD, LoopInfo *LI,
260  OptimizationRemarkEmitter *ORE, MemorySSA *MSSA = nullptr);
261 
262  /// Push a new Value to the LeaderTable onto the list for its value number.
263  void addToLeaderTable(uint32_t N, Value *V, const BasicBlock *BB) {
264  LeaderTableEntry &Curr = LeaderTable[N];
265  if (!Curr.Val) {
266  Curr.Val = V;
267  Curr.BB = BB;
268  return;
269  }
270 
271  LeaderTableEntry *Node = TableAllocator.Allocate<LeaderTableEntry>();
272  Node->Val = V;
273  Node->BB = BB;
274  Node->Next = Curr.Next;
275  Curr.Next = Node;
276  }
277 
278  /// Scan the list of values corresponding to a given
279  /// value number, and remove the given instruction if encountered.
280  void removeFromLeaderTable(uint32_t N, Instruction *I, BasicBlock *BB) {
281  LeaderTableEntry *Prev = nullptr;
282  LeaderTableEntry *Curr = &LeaderTable[N];
283 
284  while (Curr && (Curr->Val != I || Curr->BB != BB)) {
285  Prev = Curr;
286  Curr = Curr->Next;
287  }
288 
289  if (!Curr)
290  return;
291 
292  if (Prev) {
293  Prev->Next = Curr->Next;
294  } else {
295  if (!Curr->Next) {
296  Curr->Val = nullptr;
297  Curr->BB = nullptr;
298  } else {
299  LeaderTableEntry *Next = Curr->Next;
300  Curr->Val = Next->Val;
301  Curr->BB = Next->BB;
302  Curr->Next = Next->Next;
303  }
304  }
305  }
306 
307  // List of critical edges to be split between iterations.
308  SmallVector<std::pair<Instruction *, unsigned>, 4> toSplit;
309 
310  // Helper functions of redundant load elimination
311  bool processLoad(LoadInst *L);
312  bool processNonLocalLoad(LoadInst *L);
313  bool processAssumeIntrinsic(AssumeInst *II);
314 
315  /// Given a local dependency (Def or Clobber) determine if a value is
316  /// available for the load. Returns true if an value is known to be
317  /// available and populates Res. Returns false otherwise.
318  bool AnalyzeLoadAvailability(LoadInst *Load, MemDepResult DepInfo,
319  Value *Address, gvn::AvailableValue &Res);
320 
321  /// Given a list of non-local dependencies, determine if a value is
322  /// available for the load in each specified block. If it is, add it to
323  /// ValuesPerBlock. If not, add it to UnavailableBlocks.
324  void AnalyzeLoadAvailability(LoadInst *Load, LoadDepVect &Deps,
325  AvailValInBlkVect &ValuesPerBlock,
326  UnavailBlkVect &UnavailableBlocks);
327 
328  bool PerformLoadPRE(LoadInst *Load, AvailValInBlkVect &ValuesPerBlock,
329  UnavailBlkVect &UnavailableBlocks);
330 
331  /// Try to replace a load which executes on each loop iteraiton with Phi
332  /// translation of load in preheader and load(s) in conditionally executed
333  /// paths.
334  bool performLoopLoadPRE(LoadInst *Load, AvailValInBlkVect &ValuesPerBlock,
335  UnavailBlkVect &UnavailableBlocks);
336 
337  /// Eliminates partially redundant \p Load, replacing it with \p
338  /// AvailableLoads (connected by Phis if needed).
339  void eliminatePartiallyRedundantLoad(
340  LoadInst *Load, AvailValInBlkVect &ValuesPerBlock,
341  MapVector<BasicBlock *, Value *> &AvailableLoads);
342 
343  // Other helper routines
344  bool processInstruction(Instruction *I);
345  bool processBlock(BasicBlock *BB);
346  void dump(DenseMap<uint32_t, Value *> &d) const;
347  bool iterateOnFunction(Function &F);
348  bool performPRE(Function &F);
349  bool performScalarPRE(Instruction *I);
350  bool performScalarPREInsertion(Instruction *Instr, BasicBlock *Pred,
351  BasicBlock *Curr, unsigned int ValNo);
352  Value *findLeader(const BasicBlock *BB, uint32_t num);
353  void cleanupGlobalSets();
354  void verifyRemoved(const Instruction *I) const;
355  bool splitCriticalEdges();
356  BasicBlock *splitCriticalEdges(BasicBlock *Pred, BasicBlock *Succ);
357  bool replaceOperandsForInBlockEquality(Instruction *I) const;
358  bool propagateEquality(Value *LHS, Value *RHS, const BasicBlockEdge &Root,
359  bool DominatesByEdge);
360  bool processFoldableCondBr(BranchInst *BI);
361  void addDeadBlock(BasicBlock *BB);
362  void assignValNumForDeadCode();
363  void assignBlockRPONumber(Function &F);
364 };
365 
366 /// Create a legacy GVN pass. This also allows parameterizing whether or not
367 /// MemDep is enabled.
368 FunctionPass *createGVNPass(bool NoMemDepAnalysis = false);
369 
370 /// A simple and fast domtree-based GVN pass to hoist common expressions
371 /// from sibling branches.
372 struct GVNHoistPass : PassInfoMixin<GVNHoistPass> {
373  /// Run the pass over the function.
375 };
376 
377 /// Uses an "inverted" value numbering to decide the similarity of
378 /// expressions and sinks similar expressions into successors.
379 struct GVNSinkPass : PassInfoMixin<GVNSinkPass> {
380  /// Run the pass over the function.
382 };
383 
384 } // end namespace llvm
385 
386 #endif // LLVM_TRANSFORMS_SCALAR_GVN_H
llvm::GVNOptions
A set of parameters to control various transforms performed by GVN pass.
Definition: GVN.h:73
llvm::PreservedAnalyses
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:155
llvm::GVN::ValueTable::setAliasAnalysis
void setAliasAnalysis(AAResults *A)
Definition: GVN.h:204
llvm::ImplicitControlFlowTracking
This class allows to keep track on instructions with implicit control flow.
Definition: InstructionPrecedenceTracking.h:99
llvm
Definition: AllocatorList.h:23
M
We currently emits eax Perhaps this is what we really should generate is Is imull three or four cycles eax eax The current instruction priority is based on pattern complexity The former is more complex because it folds a load so the latter will not be emitted Perhaps we should use AddedComplexity to give LEA32r a higher priority We should always try to match LEA first since the LEA matching code does some estimate to determine whether the match is profitable if we care more about code then imull is better It s two bytes shorter than movl leal On a Pentium M
Definition: README.txt:252
llvm::CmpInst::Predicate
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Definition: InstrTypes.h:722
llvm::PassInfoMixin
A CRTP mix-in to automatically provide informational APIs needed for passes.
Definition: PassManager.h:374
llvm::GVNHoistPass
A simple and fast domtree-based GVN pass to hoist common expressions from sibling branches.
Definition: GVN.h:372
llvm::Function
Definition: Function.h:61
llvm::GVN::getAliasAnalysis
AAResults * getAliasAnalysis() const
Definition: GVN.h:135
llvm::GVN::ValueTable::getAliasAnalysis
AAResults * getAliasAnalysis() const
Definition: GVN.h:205
llvm::GVN::ValueTable::verifyRemoved
void verifyRemoved(const Value *) const
verifyRemoved - Verify that the value is removed from all internal data structures.
Definition: GVN.cpp:628
llvm::SmallVector< Instruction *, 8 >
llvm::GVNOptions::AllowLoadInLoopPRE
Optional< bool > AllowLoadInLoopPRE
Definition: GVN.h:76
llvm::SPII::Load
@ Load
Definition: SparcInstrInfo.h:32
MapVector.h
Allocator.h
llvm::GVN::ValueTable::setMemDep
void setMemDep(MemoryDependenceResults *M)
Definition: GVN.h:206
llvm::DominatorTree
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:151
DenseMap.h
llvm::GVNOptions::setLoadInLoopPRE
GVNOptions & setLoadInLoopPRE(bool LoadInLoopPRE)
Definition: GVN.h:94
llvm::GVN::isMemDepEnabled
bool isMemDepEnabled() const
Definition: GVN.cpp:656
llvm::Optional< bool >
llvm::GVN::ValueTable
This class holds the mapping between values and value numbers.
Definition: GVN.h:147
llvm::createGVNPass
FunctionPass * createGVNPass(bool NoMemDepAnalysis=false)
Create a legacy GVN pass.
Definition: GVN.cpp:3047
llvm::GVN::ValueTable::lookupOrAddCmp
uint32_t lookupOrAddCmp(unsigned Opcode, CmpInst::Predicate Pred, Value *LHS, Value *RHS)
Returns the value number of the given comparison, assigning it a new number if it did not have one be...
Definition: GVN.cpp:598
MemoryDependenceAnalysis.h
llvm::GVN::ValueTable::setDomTree
void setDomTree(DominatorTree *D)
Definition: GVN.h:207
llvm::gvn::GVNLegacyPass
Definition: GVN.cpp:2985
F
#define F(x, y, z)
Definition: MD5.cpp:56
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
Arg
amdgpu Simplify well known AMD library false FunctionCallee Value * Arg
Definition: AMDGPULibCalls.cpp:205
llvm::DenseMapInfo
Definition: APInt.h:34
llvm::BumpPtrAllocatorImpl::Allocate
LLVM_ATTRIBUTE_RETURNS_NONNULL LLVM_ATTRIBUTE_RETURNS_NOALIAS void * Allocate(size_t Size, Align Alignment)
Allocate space at the specified alignment.
Definition: Allocator.h:145
llvm::ISD::Constant
@ Constant
Definition: ISDOpcodes.h:69
llvm::AAResults
Definition: AliasAnalysis.h:456
llvm::GVNOptions::setLoadPRESplitBackedge
GVNOptions & setLoadPRESplitBackedge(bool LoadPRESplitBackedge)
Enables or disables PRE of loads in GVN.
Definition: GVN.h:100
llvm::GVN::ValueTable::phiTranslate
uint32_t phiTranslate(const BasicBlock *BB, const BasicBlock *PhiBlock, uint32_t Num, GVN &Gvn)
Wrap phiTranslateImpl to provide caching functionality.
Definition: GVN.cpp:1913
llvm::GVN::Expression
Definition: GVN.cpp:130
C
(vector float) vec_cmpeq(*A, *B) C
Definition: README_ALTIVEC.txt:86
llvm::GVNOptions::setMemDep
GVNOptions & setMemDep(bool MemDep)
Enables or disables use of MemDepAnalysis.
Definition: GVN.h:106
InstrTypes.h
llvm::GVN::isLoadInLoopPREEnabled
bool isLoadInLoopPREEnabled() const
Definition: GVN.cpp:647
llvm::GVN::ValueTable::lookup
uint32_t lookup(Value *V, bool Verify=true) const
Returns the value number of the specified value.
Definition: GVN.cpp:585
llvm::GVNSinkPass
Uses an "inverted" value numbering to decide the similarity of expressions and sinks similar expressi...
Definition: GVN.h:379
llvm::Instruction
Definition: Instruction.h:45
llvm::GVN::getDominatorTree
DominatorTree & getDominatorTree() const
Definition: GVN.h:134
llvm::None
const NoneType None
Definition: None.h:23
llvm::GVN::GVN
GVN(GVNOptions Options={})
Definition: GVN.h:122
llvm::SmallMapVector
A MapVector that performs no allocations if smaller than a certain size.
Definition: MapVector.h:232
llvm::PPC::Predicate
Predicate
Predicate - These are "(BI << 5) | BO" for various predicates.
Definition: PPCPredicates.h:26
Verify
ppc ctr loops PowerPC CTR Loops Verify
Definition: PPCCTRLoops.cpp:77
llvm::GVN
The core GVN pass object.
Definition: GVN.h:116
llvm::GVN::ValueTable::add
void add(Value *V, uint32_t num)
add - Insert a value into the table with a specified value number.
Definition: GVN.cpp:393
D
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
llvm::MemorySSAUpdater
Definition: MemorySSAUpdater.h:56
llvm::BumpPtrAllocatorImpl
Allocate memory in an ever growing pool, as if by bump-pointer.
Definition: Allocator.h:67
llvm::DenseMap
Definition: DenseMap.h:714
llvm::MemorySSA
Encapsulates MemorySSA, including all data associated with memory accesses.
Definition: MemorySSA.h:704
I
#define I(x, y, z)
Definition: MD5.cpp:59
llvm::GVN::ValueTable::eraseTranslateCacheEntry
void eraseTranslateCacheEntry(uint32_t Num, const BasicBlock &CurrBlock)
Erase stale entry from phiTranslate cache so phiTranslate can be computed again.
Definition: GVN.cpp:2016
llvm::GVN::isPREEnabled
bool isPREEnabled() const
Definition: GVN.cpp:639
llvm::GVN::ValueTable::operator=
ValueTable & operator=(const ValueTable &Arg)
llvm::GVN::markInstructionForDeletion
void markInstructionForDeletion(Instruction *I)
This removes the specified instruction from our various maps and marks it for deletion.
Definition: GVN.h:129
llvm::GVN::ValueTable::exists
bool exists(Value *V) const
Returns true if a value number exists for the specified value.
Definition: GVN.cpp:504
llvm::ISD::BasicBlock
@ BasicBlock
Various leaf nodes.
Definition: ISDOpcodes.h:64
llvm::GVN::ValueTable::ValueTable
ValueTable()
llvm::GVN::isLoadPREEnabled
bool isLoadPREEnabled() const
Definition: GVN.cpp:643
llvm::LoopInfo
Definition: LoopInfo.h:1080
llvm::OptimizationRemarkEmitter
The optimization diagnostic interface.
Definition: OptimizationRemarkEmitter.h:33
llvm::AssumptionCache
A cache of @llvm.assume calls within a function.
Definition: AssumptionCache.h:41
llvm::GVN::ValueTable::erase
void erase(Value *v)
Remove a value from the value numbering.
Definition: GVN.cpp:618
llvm::GVNOptions::AllowPRE
Optional< bool > AllowPRE
Definition: GVN.h:74
uint32_t
Compiler.h
llvm::GVNOptions::AllowLoadPRE
Optional< bool > AllowLoadPRE
Definition: GVN.h:75
LLVM_LIBRARY_VISIBILITY
#define LLVM_LIBRARY_VISIBILITY
LLVM_LIBRARY_VISIBILITY - If a class marked with this attribute is linked into a shared library,...
Definition: Compiler.h:131
Node
Definition: ItaniumDemangle.h:114
ValueHandle.h
llvm::GVN::ValueTable::~ValueTable
~ValueTable()
llvm::MemoryDependenceResults
Provides a lazy, caching interface for making common memory aliasing information queries,...
Definition: MemoryDependenceAnalysis.h:276
llvm::ExtractValueInst
This instruction extracts a struct member or array element value from an aggregate value.
Definition: Instructions.h:2318
llvm::TargetStackID::Value
Value
Definition: TargetFrameLowering.h:27
PassManager.h
llvm::TargetLibraryInfo
Provides information about what library functions are available for the current target.
Definition: TargetLibraryInfo.h:208
llvm::GVNOptions::setLoadPRE
GVNOptions & setLoadPRE(bool LoadPRE)
Enables or disables PRE of loads in GVN.
Definition: GVN.h:89
llvm::GVNSinkPass::run
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Run the pass over the function.
Definition: GVNSink.cpp:911
llvm::GVNOptions::AllowLoadPRESplitBackedge
Optional< bool > AllowLoadPRESplitBackedge
Definition: GVN.h:77
llvm::GVNOptions::setPRE
GVNOptions & setPRE(bool PRE)
Enables or disables PRE in GVN.
Definition: GVN.h:83
InstructionPrecedenceTracking.h
llvm::GVNOptions::AllowMemDep
Optional< bool > AllowMemDep
Definition: GVN.h:78
llvm::GVN::getMemDep
MemoryDependenceResults & getMemDep() const
Definition: GVN.h:136
PostOrderIterator.h
llvm::GVN::isLoadPRESplitBackedgeEnabled
bool isLoadPRESplitBackedgeEnabled() const
Definition: GVN.cpp:651
SmallVector.h
llvm::GVN::ValueTable::getNextUnusedValueNumber
uint32_t getNextUnusedValueNumber()
Definition: GVN.h:208
llvm::GVN::ValueTable::lookupOrAdd
uint32_t lookupOrAdd(Value *V)
lookup_or_add - Returns the value number for the specified value, assigning it a new number if it did...
Definition: GVN.cpp:508
llvm::FunctionAnalysisManager
AnalysisManager< Function > FunctionAnalysisManager
Convenience typedef for the Function analysis manager.
Definition: PassManager.h:907
Dominators.h
N
#define N
llvm::GVNHoistPass::run
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Run the pass over the function.
Definition: GVNHoist.cpp:1233
llvm::GVN::ValueTable::clear
void clear()
Remove all entries from the ValueTable.
Definition: GVN.cpp:606
llvm::GVNOptions::GVNOptions
GVNOptions()=default
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:44
llvm::GVN::run
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Run the pass over the function.
Definition: GVN.cpp:660
llvm::CallInst
This class represents a function call, abstracting a target machine's calling convention.
Definition: Instructions.h:1450
BB
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
Definition: README.txt:39
d
the resulting code requires compare and branches when and if the revised code is with conditional branches instead of More there is a byte word extend before each where there should be only and the condition codes are not remembered when the same two values are compared twice More LSR enhancements i8 and i32 load store addressing modes are identical int int int d
Definition: README.txt:418
llvm::SetVector
A vector that has set insertion semantics.
Definition: SetVector.h:40
MemorySSA
early cse Early CSE w MemorySSA
Definition: EarlyCSE.cpp:1715
llvm::Value
LLVM Value Representation.
Definition: Value.h:75
llvm::codeview::PublicSymFlags::Function
@ Function
SetVector.h