LLVM  14.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"
24 #include "llvm/IR/Dominators.h"
25 #include "llvm/IR/InstrTypes.h"
26 #include "llvm/IR/PassManager.h"
27 #include "llvm/IR/ValueHandle.h"
28 #include "llvm/Support/Allocator.h"
29 #include "llvm/Support/Compiler.h"
30 #include <cstdint>
31 #include <utility>
32 #include <vector>
33 
34 namespace llvm {
35 
36 class AAResults;
37 class AssumeInst;
38 class AssumptionCache;
39 class BasicBlock;
40 class BranchInst;
41 class CallInst;
42 class ExtractValueInst;
43 class Function;
44 class FunctionPass;
45 class LoadInst;
46 class LoopInfo;
47 class MemDepResult;
48 class MemoryDependenceResults;
49 class MemorySSA;
50 class MemorySSAUpdater;
51 class NonLocalDepResult;
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 GVNPass : public PassInfoMixin<GVNPass> {
117  GVNOptions Options;
118 
119 public:
120  struct Expression;
121 
123 
124  /// Run the pass over the function.
125  PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
126 
127  void printPipeline(raw_ostream &OS,
128  function_ref<StringRef(StringRef)> MapClassName2PassName);
129 
130  /// This removes the specified instruction from
131  /// our various maps and marks it for deletion.
133  VN.erase(I);
134  InstrsToErase.push_back(I);
135  }
136 
137  DominatorTree &getDominatorTree() const { return *DT; }
138  AAResults *getAliasAnalysis() const { return VN.getAliasAnalysis(); }
139  MemoryDependenceResults &getMemDep() const { return *MD; }
140 
141  bool isPREEnabled() const;
142  bool isLoadPREEnabled() const;
143  bool isLoadInLoopPREEnabled() const;
144  bool isLoadPRESplitBackedgeEnabled() const;
145  bool isMemDepEnabled() const;
146 
147  /// This class holds the mapping between values and value numbers. It is used
148  /// as an efficient mechanism to determine the expression-wise equivalence of
149  /// two values.
150  class ValueTable {
151  DenseMap<Value *, uint32_t> valueNumbering;
152  DenseMap<Expression, uint32_t> expressionNumbering;
153 
154  // Expressions is the vector of Expression. ExprIdx is the mapping from
155  // value number to the index of Expression in Expressions. We use it
156  // instead of a DenseMap because filling such mapping is faster than
157  // filling a DenseMap and the compile time is a little better.
158  uint32_t nextExprNumber = 0;
159 
160  std::vector<Expression> Expressions;
161  std::vector<uint32_t> ExprIdx;
162 
163  // Value number to PHINode mapping. Used for phi-translate in scalarpre.
164  DenseMap<uint32_t, PHINode *> NumberingPhi;
165 
166  // Cache for phi-translate in scalarpre.
167  using PhiTranslateMap =
169  PhiTranslateMap PhiTranslateTable;
170 
171  AAResults *AA = nullptr;
172  MemoryDependenceResults *MD = nullptr;
173  DominatorTree *DT = nullptr;
174 
175  uint32_t nextValueNumber = 1;
176 
177  Expression createExpr(Instruction *I);
178  Expression createCmpExpr(unsigned Opcode, CmpInst::Predicate Predicate,
179  Value *LHS, Value *RHS);
180  Expression createExtractvalueExpr(ExtractValueInst *EI);
181  uint32_t lookupOrAddCall(CallInst *C);
182  uint32_t phiTranslateImpl(const BasicBlock *BB, const BasicBlock *PhiBlock,
183  uint32_t Num, GVNPass &Gvn);
184  bool areCallValsEqual(uint32_t Num, uint32_t NewNum, const BasicBlock *Pred,
185  const BasicBlock *PhiBlock, GVNPass &Gvn);
186  std::pair<uint32_t, bool> assignExpNewValueNum(Expression &exp);
187  bool areAllValsInBB(uint32_t num, const BasicBlock *BB, GVNPass &Gvn);
188 
189  public:
190  ValueTable();
191  ValueTable(const ValueTable &Arg);
193  ~ValueTable();
195 
197  uint32_t lookup(Value *V, bool Verify = true) const;
198  uint32_t lookupOrAddCmp(unsigned Opcode, CmpInst::Predicate Pred,
199  Value *LHS, Value *RHS);
200  uint32_t phiTranslate(const BasicBlock *BB, const BasicBlock *PhiBlock,
201  uint32_t Num, GVNPass &Gvn);
202  void eraseTranslateCacheEntry(uint32_t Num, const BasicBlock &CurrBlock);
203  bool exists(Value *V) const;
204  void add(Value *V, uint32_t num);
205  void clear();
206  void erase(Value *v);
207  void setAliasAnalysis(AAResults *A) { AA = A; }
208  AAResults *getAliasAnalysis() const { return AA; }
210  void setDomTree(DominatorTree *D) { DT = D; }
211  uint32_t getNextUnusedValueNumber() { return nextValueNumber; }
212  void verifyRemoved(const Value *) const;
213  };
214 
215 private:
216  friend class gvn::GVNLegacyPass;
217  friend struct DenseMapInfo<Expression>;
218 
219  MemoryDependenceResults *MD = nullptr;
220  DominatorTree *DT = nullptr;
221  const TargetLibraryInfo *TLI = nullptr;
222  AssumptionCache *AC = nullptr;
223  SetVector<BasicBlock *> DeadBlocks;
224  OptimizationRemarkEmitter *ORE = nullptr;
225  ImplicitControlFlowTracking *ICF = nullptr;
226  LoopInfo *LI = nullptr;
227  MemorySSAUpdater *MSSAU = nullptr;
228 
229  ValueTable VN;
230 
231  /// A mapping from value numbers to lists of Value*'s that
232  /// have that value number. Use findLeader to query it.
233  struct LeaderTableEntry {
234  Value *Val;
235  const BasicBlock *BB;
236  LeaderTableEntry *Next;
237  };
239  BumpPtrAllocator TableAllocator;
240 
241  // Block-local map of equivalent values to their leader, does not
242  // propagate to any successors. Entries added mid-block are applied
243  // to the remaining instructions in the block.
244  SmallMapVector<Value *, Value *, 4> ReplaceOperandsWithMap;
245  SmallVector<Instruction *, 8> InstrsToErase;
246 
247  // Map the block to reversed postorder traversal number. It is used to
248  // find back edge easily.
250 
251  // This is set 'true' initially and also when new blocks have been added to
252  // the function being analyzed. This boolean is used to control the updating
253  // of BlockRPONumber prior to accessing the contents of BlockRPONumber.
254  bool InvalidBlockRPONumbers = true;
255 
256  using LoadDepVect = SmallVector<NonLocalDepResult, 64>;
257  using AvailValInBlkVect = SmallVector<gvn::AvailableValueInBlock, 64>;
258  using UnavailBlkVect = SmallVector<BasicBlock *, 64>;
259 
260  bool runImpl(Function &F, AssumptionCache &RunAC, DominatorTree &RunDT,
261  const TargetLibraryInfo &RunTLI, AAResults &RunAA,
262  MemoryDependenceResults *RunMD, LoopInfo *LI,
263  OptimizationRemarkEmitter *ORE, MemorySSA *MSSA = nullptr);
264 
265  /// Push a new Value to the LeaderTable onto the list for its value number.
266  void addToLeaderTable(uint32_t N, Value *V, const BasicBlock *BB) {
267  LeaderTableEntry &Curr = LeaderTable[N];
268  if (!Curr.Val) {
269  Curr.Val = V;
270  Curr.BB = BB;
271  return;
272  }
273 
274  LeaderTableEntry *Node = TableAllocator.Allocate<LeaderTableEntry>();
275  Node->Val = V;
276  Node->BB = BB;
277  Node->Next = Curr.Next;
278  Curr.Next = Node;
279  }
280 
281  /// Scan the list of values corresponding to a given
282  /// value number, and remove the given instruction if encountered.
283  void removeFromLeaderTable(uint32_t N, Instruction *I, BasicBlock *BB) {
284  LeaderTableEntry *Prev = nullptr;
285  LeaderTableEntry *Curr = &LeaderTable[N];
286 
287  while (Curr && (Curr->Val != I || Curr->BB != BB)) {
288  Prev = Curr;
289  Curr = Curr->Next;
290  }
291 
292  if (!Curr)
293  return;
294 
295  if (Prev) {
296  Prev->Next = Curr->Next;
297  } else {
298  if (!Curr->Next) {
299  Curr->Val = nullptr;
300  Curr->BB = nullptr;
301  } else {
302  LeaderTableEntry *Next = Curr->Next;
303  Curr->Val = Next->Val;
304  Curr->BB = Next->BB;
305  Curr->Next = Next->Next;
306  }
307  }
308  }
309 
310  // List of critical edges to be split between iterations.
311  SmallVector<std::pair<Instruction *, unsigned>, 4> toSplit;
312 
313  // Helper functions of redundant load elimination
314  bool processLoad(LoadInst *L);
315  bool processNonLocalLoad(LoadInst *L);
316  bool processAssumeIntrinsic(AssumeInst *II);
317 
318  /// Given a local dependency (Def or Clobber) determine if a value is
319  /// available for the load. Returns true if an value is known to be
320  /// available and populates Res. Returns false otherwise.
321  bool AnalyzeLoadAvailability(LoadInst *Load, MemDepResult DepInfo,
322  Value *Address, gvn::AvailableValue &Res);
323 
324  /// Given a list of non-local dependencies, determine if a value is
325  /// available for the load in each specified block. If it is, add it to
326  /// ValuesPerBlock. If not, add it to UnavailableBlocks.
327  void AnalyzeLoadAvailability(LoadInst *Load, LoadDepVect &Deps,
328  AvailValInBlkVect &ValuesPerBlock,
329  UnavailBlkVect &UnavailableBlocks);
330 
331  bool PerformLoadPRE(LoadInst *Load, AvailValInBlkVect &ValuesPerBlock,
332  UnavailBlkVect &UnavailableBlocks);
333 
334  /// Try to replace a load which executes on each loop iteraiton with Phi
335  /// translation of load in preheader and load(s) in conditionally executed
336  /// paths.
337  bool performLoopLoadPRE(LoadInst *Load, AvailValInBlkVect &ValuesPerBlock,
338  UnavailBlkVect &UnavailableBlocks);
339 
340  /// Eliminates partially redundant \p Load, replacing it with \p
341  /// AvailableLoads (connected by Phis if needed).
342  void eliminatePartiallyRedundantLoad(
343  LoadInst *Load, AvailValInBlkVect &ValuesPerBlock,
344  MapVector<BasicBlock *, Value *> &AvailableLoads);
345 
346  // Other helper routines
347  bool processInstruction(Instruction *I);
348  bool processBlock(BasicBlock *BB);
349  void dump(DenseMap<uint32_t, Value *> &d) const;
350  bool iterateOnFunction(Function &F);
351  bool performPRE(Function &F);
352  bool performScalarPRE(Instruction *I);
353  bool performScalarPREInsertion(Instruction *Instr, BasicBlock *Pred,
354  BasicBlock *Curr, unsigned int ValNo);
355  Value *findLeader(const BasicBlock *BB, uint32_t num);
356  void cleanupGlobalSets();
357  void verifyRemoved(const Instruction *I) const;
358  bool splitCriticalEdges();
359  BasicBlock *splitCriticalEdges(BasicBlock *Pred, BasicBlock *Succ);
360  bool replaceOperandsForInBlockEquality(Instruction *I) const;
361  bool propagateEquality(Value *LHS, Value *RHS, const BasicBlockEdge &Root,
362  bool DominatesByEdge);
363  bool processFoldableCondBr(BranchInst *BI);
364  void addDeadBlock(BasicBlock *BB);
365  void assignValNumForDeadCode();
366  void assignBlockRPONumber(Function &F);
367 };
368 
369 /// Create a legacy GVN pass. This also allows parameterizing whether or not
370 /// MemDep is enabled.
371 FunctionPass *createGVNPass(bool NoMemDepAnalysis = false);
372 
373 /// A simple and fast domtree-based GVN pass to hoist common expressions
374 /// from sibling branches.
375 struct GVNHoistPass : PassInfoMixin<GVNHoistPass> {
376  /// Run the pass over the function.
378 };
379 
380 /// Uses an "inverted" value numbering to decide the similarity of
381 /// expressions and sinks similar expressions into successors.
382 struct GVNSinkPass : PassInfoMixin<GVNSinkPass> {
383  /// Run the pass over the function.
385 };
386 
387 } // end namespace llvm
388 
389 #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::ImplicitControlFlowTracking
This class allows to keep track on instructions with implicit control flow.
Definition: InstructionPrecedenceTracking.h:99
llvm
This is an optimization pass for GlobalISel generic memory operations.
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::GVNPass::ValueTable::clear
void clear()
Remove all entries from the ValueTable.
Definition: GVN.cpp:608
llvm::CmpInst::Predicate
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Definition: InstrTypes.h:721
llvm::PassInfoMixin
A CRTP mix-in to automatically provide informational APIs needed for passes.
Definition: PassManager.h:374
llvm::GVNPass::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:510
llvm::GVNHoistPass
A simple and fast domtree-based GVN pass to hoist common expressions from sibling branches.
Definition: GVN.h:375
llvm::GVNPass::ValueTable::exists
bool exists(Value *V) const
Returns true if a value number exists for the specified value.
Definition: GVN.cpp:504
llvm::Function
Definition: Function.h:62
llvm::GVNPass::ValueTable::lookup
uint32_t lookup(Value *V, bool Verify=true) const
Returns the value number of the specified value.
Definition: GVN.cpp:587
llvm::SmallVector< Instruction *, 8 >
llvm::GVNPass::run
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Run the pass over the function.
Definition: GVN.cpp:662
llvm::GVNOptions::AllowLoadInLoopPRE
Optional< bool > AllowLoadInLoopPRE
Definition: GVN.h:76
MapVector.h
Allocator.h
llvm::DominatorTree
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:151
llvm::GVNPass::ValueTable::setMemDep
void setMemDep(MemoryDependenceResults *M)
Definition: GVN.h:209
DenseMap.h
llvm::GVNOptions::setLoadInLoopPRE
GVNOptions & setLoadInLoopPRE(bool LoadInLoopPRE)
Definition: GVN.h:94
llvm::Optional< bool >
llvm::GVNPass::GVNPass
GVNPass(GVNOptions Options={})
Definition: GVN.h:122
llvm::createGVNPass
FunctionPass * createGVNPass(bool NoMemDepAnalysis=false)
Create a legacy GVN pass.
Definition: GVN.cpp:3118
RHS
Value * RHS
Definition: X86PartialReduction.cpp:74
llvm::GVNPass::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:2088
llvm::GVNPass::ValueTable::getAliasAnalysis
AAResults * getAliasAnalysis() const
Definition: GVN.h:208
llvm::gvn::GVNLegacyPass
Definition: GVN.cpp:3056
F
#define F(x, y, z)
Definition: MD5.cpp:55
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
Arg
amdgpu Simplify well known AMD library false FunctionCallee Value * Arg
Definition: AMDGPULibCalls.cpp:185
LHS
Value * LHS
Definition: X86PartialReduction.cpp:73
llvm::DenseMapInfo
An information struct used to provide DenseMap with the various necessary components for a given valu...
Definition: APInt.h:34
llvm::GVNPass::ValueTable::operator=
ValueTable & operator=(const ValueTable &Arg)
llvm::GVNPass::ValueTable::getNextUnusedValueNumber
uint32_t getNextUnusedValueNumber()
Definition: GVN.h:211
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::AAResults
Definition: AliasAnalysis.h:507
llvm::GVNPass::ValueTable::~ValueTable
~ValueTable()
llvm::GVNOptions::setLoadPRESplitBackedge
GVNOptions & setLoadPRESplitBackedge(bool LoadPRESplitBackedge)
Enables or disables PRE of loads in GVN.
Definition: GVN.h:100
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::GVNSinkPass
Uses an "inverted" value numbering to decide the similarity of expressions and sinks similar expressi...
Definition: GVN.h:382
llvm::Instruction
Definition: Instruction.h:45
llvm::GVNPass::isLoadInLoopPREEnabled
bool isLoadInLoopPREEnabled() const
Definition: GVN.cpp:649
Options
const char LLVMTargetMachineRef LLVMPassBuilderOptionsRef Options
Definition: PassBuilderBindings.cpp:48
llvm::GVNPass::getAliasAnalysis
AAResults * getAliasAnalysis() const
Definition: GVN.h:138
llvm::GVNPass::isPREEnabled
bool isPREEnabled() const
Definition: GVN.cpp:641
llvm::None
const NoneType None
Definition: None.h:23
llvm::GVNPass::ValueTable::add
void add(Value *V, uint32_t num)
add - Insert a value into the table with a specified value number.
Definition: GVN.cpp:394
llvm::SmallMapVector
A MapVector that performs no allocations if smaller than a certain size.
Definition: MapVector.h:233
llvm::GVNPass::printPipeline
void printPipeline(raw_ostream &OS, function_ref< StringRef(StringRef)> MapClassName2PassName)
Definition: GVN.cpp:690
llvm::PPC::Predicate
Predicate
Predicate - These are "(BI << 5) | BO" for various predicates.
Definition: PPCPredicates.h:26
llvm::GVNPass::isLoadPRESplitBackedgeEnabled
bool isLoadPRESplitBackedgeEnabled() const
Definition: GVN.cpp:653
llvm::GVNPass::getDominatorTree
DominatorTree & getDominatorTree() const
Definition: GVN.h:137
Verify
ppc ctr loops PowerPC CTR Loops Verify
Definition: PPCCTRLoops.cpp:77
llvm::GVNPass::getMemDep
MemoryDependenceResults & getMemDep() const
Definition: GVN.h:139
D
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
llvm::MemorySSAUpdater
Definition: MemorySSAUpdater.h:55
llvm::GVNPass::ValueTable::erase
void erase(Value *v)
Remove a value from the value numbering.
Definition: GVN.cpp:620
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:58
llvm::GVNPass::isMemDepEnabled
bool isMemDepEnabled() const
Definition: GVN.cpp:658
llvm::GVNPass::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:600
llvm::ISD::BasicBlock
@ BasicBlock
Various leaf nodes.
Definition: ISDOpcodes.h:71
llvm::GVNPass::ValueTable::ValueTable
ValueTable()
llvm::GVNPass::markInstructionForDeletion
void markInstructionForDeletion(Instruction *I)
This removes the specified instruction from our various maps and marks it for deletion.
Definition: GVN.h:132
llvm::GVNPass::isLoadPREEnabled
bool isLoadPREEnabled() const
Definition: GVN.cpp:645
llvm::LoopInfo
Definition: LoopInfo.h:1086
llvm::OptimizationRemarkEmitter
The optimization diagnostic interface.
Definition: OptimizationRemarkEmitter.h:33
llvm::AssumptionCache
A cache of @llvm.assume calls within a function.
Definition: AssumptionCache.h:42
llvm::GVNOptions::AllowPRE
Optional< bool > AllowPRE
Definition: GVN.h:74
llvm::GVNPass::ValueTable::verifyRemoved
void verifyRemoved(const Value *) const
verifyRemoved - Verify that the value is removed from all internal data structures.
Definition: GVN.cpp:630
uint32_t
Compiler.h
llvm::GVNOptions::AllowLoadPRE
Optional< bool > AllowLoadPRE
Definition: GVN.h:75
llvm::GVNPass::ValueTable
This class holds the mapping between values and value numbers.
Definition: GVN.h:150
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:135
Node
Definition: ItaniumDemangle.h:235
ValueHandle.h
llvm::MemoryDependenceResults
Provides a lazy, caching interface for making common memory aliasing information queries,...
Definition: MemoryDependenceAnalysis.h:264
llvm::GVNPass::ValueTable::setDomTree
void setDomTree(DominatorTree *D)
Definition: GVN.h:210
llvm::ExtractValueInst
This instruction extracts a struct member or array element value from an aggregate value.
Definition: Instructions.h:2404
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:221
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::GVNPass::ValueTable::setAliasAnalysis
void setAliasAnalysis(AAResults *A)
Definition: GVN.h:207
llvm::GVNOptions::AllowLoadPRESplitBackedge
Optional< bool > AllowLoadPRESplitBackedge
Definition: GVN.h:77
llvm::SPII::Load
@ Load
Definition: SparcInstrInfo.h:32
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
PostOrderIterator.h
SmallVector.h
llvm::FunctionAnalysisManager
AnalysisManager< Function > FunctionAnalysisManager
Convenience typedef for the Function analysis manager.
Definition: PassManager.h:921
Dominators.h
N
#define N
llvm::GVNHoistPass::run
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Run the pass over the function.
Definition: GVNHoist.cpp:1235
llvm::GVNPass::Expression
Definition: GVN.cpp:129
llvm::GVNPass::ValueTable::phiTranslate
uint32_t phiTranslate(const BasicBlock *BB, const BasicBlock *PhiBlock, uint32_t Num, GVNPass &Gvn)
Wrap phiTranslateImpl to provide caching functionality.
Definition: GVN.cpp:1984
llvm::GVNOptions::GVNOptions
GVNOptions()=default
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:44
llvm::CallInst
This class represents a function call, abstracting a target machine's calling convention.
Definition: Instructions.h:1478
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
llvm::GVNPass
The core GVN pass object.
Definition: GVN.h:116
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:1762
llvm::Value
LLVM Value Representation.
Definition: Value.h:74
llvm::codeview::PublicSymFlags::Function
@ Function
SetVector.h