LLVM  16.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"
20 #include "llvm/ADT/SetVector.h"
21 #include "llvm/ADT/SmallVector.h"
22 #include "llvm/IR/Dominators.h"
23 #include "llvm/IR/InstrTypes.h"
24 #include "llvm/IR/PassManager.h"
25 #include "llvm/IR/ValueHandle.h"
26 #include "llvm/Support/Allocator.h"
27 #include "llvm/Support/Compiler.h"
28 #include <cstdint>
29 #include <optional>
30 #include <utility>
31 #include <vector>
32 
33 namespace llvm {
34 
35 class AAResults;
36 class AssumeInst;
37 class AssumptionCache;
38 class BasicBlock;
39 class BranchInst;
40 class CallInst;
41 class ExtractValueInst;
42 class Function;
43 class FunctionPass;
44 class GetElementPtrInst;
45 class ImplicitControlFlowTracking;
46 class LoadInst;
47 class LoopInfo;
48 class MemDepResult;
49 class MemoryDependenceResults;
50 class MemorySSA;
51 class MemorySSAUpdater;
52 class NonLocalDepResult;
53 class OptimizationRemarkEmitter;
54 class PHINode;
55 class TargetLibraryInfo;
56 class Value;
57 /// A private "module" namespace for types and utilities used by GVN. These
58 /// are implementation details and should not be used by clients.
59 namespace gvn LLVM_LIBRARY_VISIBILITY {
60 
61 struct AvailableValue;
62 struct AvailableValueInBlock;
63 class GVNLegacyPass;
64 
65 } // end namespace gvn
66 
67 /// A set of parameters to control various transforms performed by GVN pass.
68 // Each of the optional boolean parameters can be set to:
69 /// true - enabling the transformation.
70 /// false - disabling the transformation.
71 /// None - relying on a global default.
72 /// Intended use is to create a default object, modify parameters with
73 /// additional setters and then pass it to GVN.
74 struct GVNOptions {
75  std::optional<bool> AllowPRE = None;
76  std::optional<bool> AllowLoadPRE = None;
77  std::optional<bool> AllowLoadInLoopPRE = None;
78  std::optional<bool> AllowLoadPRESplitBackedge = None;
79  std::optional<bool> AllowMemDep = None;
80 
81  GVNOptions() = default;
82 
83  /// Enables or disables PRE in GVN.
84  GVNOptions &setPRE(bool PRE) {
85  AllowPRE = PRE;
86  return *this;
87  }
88 
89  /// Enables or disables PRE of loads in GVN.
90  GVNOptions &setLoadPRE(bool LoadPRE) {
91  AllowLoadPRE = LoadPRE;
92  return *this;
93  }
94 
95  GVNOptions &setLoadInLoopPRE(bool LoadInLoopPRE) {
96  AllowLoadInLoopPRE = LoadInLoopPRE;
97  return *this;
98  }
99 
100  /// Enables or disables PRE of loads in GVN.
101  GVNOptions &setLoadPRESplitBackedge(bool LoadPRESplitBackedge) {
102  AllowLoadPRESplitBackedge = LoadPRESplitBackedge;
103  return *this;
104  }
105 
106  /// Enables or disables use of MemDepAnalysis.
107  GVNOptions &setMemDep(bool MemDep) {
108  AllowMemDep = MemDep;
109  return *this;
110  }
111 };
112 
113 /// The core GVN pass object.
114 ///
115 /// FIXME: We should have a good summary of the GVN algorithm implemented by
116 /// this particular pass here.
117 class GVNPass : public PassInfoMixin<GVNPass> {
118  GVNOptions Options;
119 
120 public:
121  struct Expression;
122 
124 
125  /// Run the pass over the function.
126  PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
127 
128  void printPipeline(raw_ostream &OS,
129  function_ref<StringRef(StringRef)> MapClassName2PassName);
130 
131  /// This removes the specified instruction from
132  /// our various maps and marks it for deletion.
134  VN.erase(I);
135  InstrsToErase.push_back(I);
136  }
137 
138  DominatorTree &getDominatorTree() const { return *DT; }
139  AAResults *getAliasAnalysis() const { return VN.getAliasAnalysis(); }
140  MemoryDependenceResults &getMemDep() const { return *MD; }
141 
142  bool isPREEnabled() const;
143  bool isLoadPREEnabled() const;
144  bool isLoadInLoopPREEnabled() const;
145  bool isLoadPRESplitBackedgeEnabled() const;
146  bool isMemDepEnabled() const;
147 
148  /// This class holds the mapping between values and value numbers. It is used
149  /// as an efficient mechanism to determine the expression-wise equivalence of
150  /// two values.
151  class ValueTable {
152  DenseMap<Value *, uint32_t> valueNumbering;
153  DenseMap<Expression, uint32_t> expressionNumbering;
154 
155  // Expressions is the vector of Expression. ExprIdx is the mapping from
156  // value number to the index of Expression in Expressions. We use it
157  // instead of a DenseMap because filling such mapping is faster than
158  // filling a DenseMap and the compile time is a little better.
159  uint32_t nextExprNumber = 0;
160 
161  std::vector<Expression> Expressions;
162  std::vector<uint32_t> ExprIdx;
163 
164  // Value number to PHINode mapping. Used for phi-translate in scalarpre.
165  DenseMap<uint32_t, PHINode *> NumberingPhi;
166 
167  // Cache for phi-translate in scalarpre.
168  using PhiTranslateMap =
170  PhiTranslateMap PhiTranslateTable;
171 
172  AAResults *AA = nullptr;
173  MemoryDependenceResults *MD = nullptr;
174  DominatorTree *DT = nullptr;
175 
176  uint32_t nextValueNumber = 1;
177 
178  Expression createExpr(Instruction *I);
179  Expression createCmpExpr(unsigned Opcode, CmpInst::Predicate Predicate,
180  Value *LHS, Value *RHS);
181  Expression createExtractvalueExpr(ExtractValueInst *EI);
182  Expression createGEPExpr(GetElementPtrInst *GEP);
183  uint32_t lookupOrAddCall(CallInst *C);
184  uint32_t phiTranslateImpl(const BasicBlock *BB, const BasicBlock *PhiBlock,
185  uint32_t Num, GVNPass &Gvn);
186  bool areCallValsEqual(uint32_t Num, uint32_t NewNum, const BasicBlock *Pred,
187  const BasicBlock *PhiBlock, GVNPass &Gvn);
188  std::pair<uint32_t, bool> assignExpNewValueNum(Expression &exp);
189  bool areAllValsInBB(uint32_t num, const BasicBlock *BB, GVNPass &Gvn);
190 
191  public:
192  ValueTable();
193  ValueTable(const ValueTable &Arg);
195  ~ValueTable();
197 
199  uint32_t lookup(Value *V, bool Verify = true) const;
200  uint32_t lookupOrAddCmp(unsigned Opcode, CmpInst::Predicate Pred,
201  Value *LHS, Value *RHS);
202  uint32_t phiTranslate(const BasicBlock *BB, const BasicBlock *PhiBlock,
203  uint32_t Num, GVNPass &Gvn);
204  void eraseTranslateCacheEntry(uint32_t Num, const BasicBlock &CurrBlock);
205  bool exists(Value *V) const;
206  void add(Value *V, uint32_t num);
207  void clear();
208  void erase(Value *v);
209  void setAliasAnalysis(AAResults *A) { AA = A; }
210  AAResults *getAliasAnalysis() const { return AA; }
212  void setDomTree(DominatorTree *D) { DT = D; }
213  uint32_t getNextUnusedValueNumber() { return nextValueNumber; }
214  void verifyRemoved(const Value *) const;
215  };
216 
217 private:
218  friend class gvn::GVNLegacyPass;
219  friend struct DenseMapInfo<Expression>;
220 
221  MemoryDependenceResults *MD = nullptr;
222  DominatorTree *DT = nullptr;
223  const TargetLibraryInfo *TLI = nullptr;
224  AssumptionCache *AC = nullptr;
225  SetVector<BasicBlock *> DeadBlocks;
226  OptimizationRemarkEmitter *ORE = nullptr;
227  ImplicitControlFlowTracking *ICF = nullptr;
228  LoopInfo *LI = nullptr;
229  MemorySSAUpdater *MSSAU = nullptr;
230 
231  ValueTable VN;
232 
233  /// A mapping from value numbers to lists of Value*'s that
234  /// have that value number. Use findLeader to query it.
235  struct LeaderTableEntry {
236  Value *Val;
237  const BasicBlock *BB;
238  LeaderTableEntry *Next;
239  };
241  BumpPtrAllocator TableAllocator;
242 
243  // Block-local map of equivalent values to their leader, does not
244  // propagate to any successors. Entries added mid-block are applied
245  // to the remaining instructions in the block.
246  SmallMapVector<Value *, Value *, 4> ReplaceOperandsWithMap;
247  SmallVector<Instruction *, 8> InstrsToErase;
248 
249  // Map the block to reversed postorder traversal number. It is used to
250  // find back edge easily.
252 
253  // This is set 'true' initially and also when new blocks have been added to
254  // the function being analyzed. This boolean is used to control the updating
255  // of BlockRPONumber prior to accessing the contents of BlockRPONumber.
256  bool InvalidBlockRPONumbers = true;
257 
258  using LoadDepVect = SmallVector<NonLocalDepResult, 64>;
259  using AvailValInBlkVect = SmallVector<gvn::AvailableValueInBlock, 64>;
260  using UnavailBlkVect = SmallVector<BasicBlock *, 64>;
261 
262  bool runImpl(Function &F, AssumptionCache &RunAC, DominatorTree &RunDT,
263  const TargetLibraryInfo &RunTLI, AAResults &RunAA,
264  MemoryDependenceResults *RunMD, LoopInfo *LI,
265  OptimizationRemarkEmitter *ORE, MemorySSA *MSSA = nullptr);
266 
267  /// Push a new Value to the LeaderTable onto the list for its value number.
268  void addToLeaderTable(uint32_t N, Value *V, const BasicBlock *BB) {
269  LeaderTableEntry &Curr = LeaderTable[N];
270  if (!Curr.Val) {
271  Curr.Val = V;
272  Curr.BB = BB;
273  return;
274  }
275 
276  LeaderTableEntry *Node = TableAllocator.Allocate<LeaderTableEntry>();
277  Node->Val = V;
278  Node->BB = BB;
279  Node->Next = Curr.Next;
280  Curr.Next = Node;
281  }
282 
283  /// Scan the list of values corresponding to a given
284  /// value number, and remove the given instruction if encountered.
285  void removeFromLeaderTable(uint32_t N, Instruction *I, BasicBlock *BB) {
286  LeaderTableEntry *Prev = nullptr;
287  LeaderTableEntry *Curr = &LeaderTable[N];
288 
289  while (Curr && (Curr->Val != I || Curr->BB != BB)) {
290  Prev = Curr;
291  Curr = Curr->Next;
292  }
293 
294  if (!Curr)
295  return;
296 
297  if (Prev) {
298  Prev->Next = Curr->Next;
299  } else {
300  if (!Curr->Next) {
301  Curr->Val = nullptr;
302  Curr->BB = nullptr;
303  } else {
304  LeaderTableEntry *Next = Curr->Next;
305  Curr->Val = Next->Val;
306  Curr->BB = Next->BB;
307  Curr->Next = Next->Next;
308  }
309  }
310  }
311 
312  // List of critical edges to be split between iterations.
313  SmallVector<std::pair<Instruction *, unsigned>, 4> toSplit;
314 
315  // Helper functions of redundant load elimination
316  bool processLoad(LoadInst *L);
317  bool processNonLocalLoad(LoadInst *L);
318  bool processAssumeIntrinsic(AssumeInst *II);
319 
320  /// Given a local dependency (Def or Clobber) determine if a value is
321  /// available for the load. Returns true if an value is known to be
322  /// available and populates Res. Returns false otherwise.
323  bool AnalyzeLoadAvailability(LoadInst *Load, MemDepResult DepInfo,
324  Value *Address, gvn::AvailableValue &Res);
325 
326  /// Given a list of non-local dependencies, determine if a value is
327  /// available for the load in each specified block. If it is, add it to
328  /// ValuesPerBlock. If not, add it to UnavailableBlocks.
329  void AnalyzeLoadAvailability(LoadInst *Load, LoadDepVect &Deps,
330  AvailValInBlkVect &ValuesPerBlock,
331  UnavailBlkVect &UnavailableBlocks);
332 
333  bool PerformLoadPRE(LoadInst *Load, AvailValInBlkVect &ValuesPerBlock,
334  UnavailBlkVect &UnavailableBlocks);
335 
336  /// Try to replace a load which executes on each loop iteraiton with Phi
337  /// translation of load in preheader and load(s) in conditionally executed
338  /// paths.
339  bool performLoopLoadPRE(LoadInst *Load, AvailValInBlkVect &ValuesPerBlock,
340  UnavailBlkVect &UnavailableBlocks);
341 
342  /// Eliminates partially redundant \p Load, replacing it with \p
343  /// AvailableLoads (connected by Phis if needed).
344  void eliminatePartiallyRedundantLoad(
345  LoadInst *Load, AvailValInBlkVect &ValuesPerBlock,
346  MapVector<BasicBlock *, Value *> &AvailableLoads);
347 
348  // Other helper routines
349  bool processInstruction(Instruction *I);
350  bool processBlock(BasicBlock *BB);
351  void dump(DenseMap<uint32_t, Value *> &d) const;
352  bool iterateOnFunction(Function &F);
353  bool performPRE(Function &F);
354  bool performScalarPRE(Instruction *I);
355  bool performScalarPREInsertion(Instruction *Instr, BasicBlock *Pred,
356  BasicBlock *Curr, unsigned int ValNo);
357  Value *findLeader(const BasicBlock *BB, uint32_t num);
358  void cleanupGlobalSets();
359  void verifyRemoved(const Instruction *I) const;
360  bool splitCriticalEdges();
361  BasicBlock *splitCriticalEdges(BasicBlock *Pred, BasicBlock *Succ);
362  bool replaceOperandsForInBlockEquality(Instruction *I) const;
363  bool propagateEquality(Value *LHS, Value *RHS, const BasicBlockEdge &Root,
364  bool DominatesByEdge);
365  bool processFoldableCondBr(BranchInst *BI);
366  void addDeadBlock(BasicBlock *BB);
367  void assignValNumForDeadCode();
368  void assignBlockRPONumber(Function &F);
369 };
370 
371 /// Create a legacy GVN pass. This also allows parameterizing whether or not
372 /// MemDep is enabled.
373 FunctionPass *createGVNPass(bool NoMemDepAnalysis = false);
374 
375 /// A simple and fast domtree-based GVN pass to hoist common expressions
376 /// from sibling branches.
377 struct GVNHoistPass : PassInfoMixin<GVNHoistPass> {
378  /// Run the pass over the function.
380 };
381 
382 /// Uses an "inverted" value numbering to decide the similarity of
383 /// expressions and sinks similar expressions into successors.
384 struct GVNSinkPass : PassInfoMixin<GVNSinkPass> {
385  /// Run the pass over the function.
387 };
388 
389 } // end namespace llvm
390 
391 #endif // LLVM_TRANSFORMS_SCALAR_GVN_H
llvm::GVNOptions
A set of parameters to control various transforms performed by GVN pass.
Definition: GVN.h:74
llvm::PreservedAnalyses
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:152
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: AddressRanges.h:18
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:678
llvm::CmpInst::Predicate
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Definition: InstrTypes.h:720
llvm::PassInfoMixin
A CRTP mix-in to automatically provide informational APIs needed for passes.
Definition: PassManager.h:371
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:578
llvm::GVNHoistPass
A simple and fast domtree-based GVN pass to hoist common expressions from sibling branches.
Definition: GVN.h:377
llvm::GVNPass::ValueTable::exists
bool exists(Value *V) const
Returns true if a value number exists for the specified value.
Definition: GVN.cpp:572
llvm::Function
Definition: Function.h:60
llvm::GVNPass::ValueTable::lookup
uint32_t lookup(Value *V, bool Verify=true) const
Returns the value number of the specified value.
Definition: GVN.cpp:657
llvm::SmallVector< Instruction *, 8 >
llvm::GVNOptions::AllowLoadPRESplitBackedge
std::optional< bool > AllowLoadPRESplitBackedge
Definition: GVN.h:78
llvm::GVNPass::run
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Run the pass over the function.
Definition: GVN.cpp:732
MapVector.h
Allocator.h
llvm::DominatorTree
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:166
llvm::GVNOptions::AllowPRE
std::optional< bool > AllowPRE
Definition: GVN.h:75
llvm::GVNPass::ValueTable::setMemDep
void setMemDep(MemoryDependenceResults *M)
Definition: GVN.h:211
DenseMap.h
llvm::GVNOptions::setLoadInLoopPRE
GVNOptions & setLoadInLoopPRE(bool LoadInLoopPRE)
Definition: GVN.h:95
llvm::GVNPass::GVNPass
GVNPass(GVNOptions Options={})
Definition: GVN.h:123
llvm::createGVNPass
FunctionPass * createGVNPass(bool NoMemDepAnalysis=false)
Create a legacy GVN pass.
Definition: GVN.cpp:3244
RHS
Value * RHS
Definition: X86PartialReduction.cpp:76
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:2225
llvm::GVNPass::ValueTable::getAliasAnalysis
AAResults * getAliasAnalysis() const
Definition: GVN.h:210
llvm::gvn::GVNLegacyPass
Definition: GVN.cpp:3182
F
#define F(x, y, z)
Definition: MD5.cpp:55
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:55
Verify
ppc ctr loops PowerPC CTR Loops Verify
Definition: PPCCTRLoopsVerify.cpp:77
Arg
amdgpu Simplify well known AMD library false FunctionCallee Value * Arg
Definition: AMDGPULibCalls.cpp:187
LHS
Value * LHS
Definition: X86PartialReduction.cpp:75
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:213
llvm::AAResults
Definition: AliasAnalysis.h:294
llvm::GVNPass::ValueTable::~ValueTable
~ValueTable()
llvm::GVNOptions::setLoadPRESplitBackedge
GVNOptions & setLoadPRESplitBackedge(bool LoadPRESplitBackedge)
Enables or disables PRE of loads in GVN.
Definition: GVN.h:101
llvm::GVNOptions::AllowMemDep
std::optional< bool > AllowMemDep
Definition: GVN.h:79
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:107
InstrTypes.h
llvm::GVNSinkPass
Uses an "inverted" value numbering to decide the similarity of expressions and sinks similar expressi...
Definition: GVN.h:384
llvm::Instruction
Definition: Instruction.h:42
llvm::GVNPass::isLoadInLoopPREEnabled
bool isLoadInLoopPREEnabled() const
Definition: GVN.cpp:719
Options
const char LLVMTargetMachineRef LLVMPassBuilderOptionsRef Options
Definition: PassBuilderBindings.cpp:48
llvm::GVNPass::getAliasAnalysis
AAResults * getAliasAnalysis() const
Definition: GVN.h:139
llvm::GVNPass::isPREEnabled
bool isPREEnabled() const
Definition: GVN.cpp:711
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:447
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:760
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:723
llvm::GVNPass::getDominatorTree
DominatorTree & getDominatorTree() const
Definition: GVN.h:138
llvm::GVNPass::getMemDep
MemoryDependenceResults & getMemDep() const
Definition: GVN.h:140
D
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
llvm::MemorySSAUpdater
Definition: MemorySSAUpdater.h:54
llvm::GVNPass::ValueTable::erase
void erase(Value *v)
Remove a value from the value numbering.
Definition: GVN.cpp:690
llvm::BumpPtrAllocatorImpl
Allocate memory in an ever growing pool, as if by bump-pointer.
Definition: Allocator.h:63
llvm::DenseMap
Definition: DenseMap.h:714
llvm::MemorySSA
Encapsulates MemorySSA, including all data associated with memory accesses.
Definition: MemorySSA.h:700
I
#define I(x, y, z)
Definition: MD5.cpp:58
llvm::GetElementPtrInst
an instruction for type-safe pointer arithmetic to access elements of arrays and structs
Definition: Instructions.h:929
llvm::GVNPass::isMemDepEnabled
bool isMemDepEnabled() const
Definition: GVN.cpp:728
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:670
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:133
llvm::GVNPass::isLoadPREEnabled
bool isLoadPREEnabled() const
Definition: GVN.cpp:715
llvm::LoopInfo
Definition: LoopInfo.h:1108
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::GVNPass::ValueTable::verifyRemoved
void verifyRemoved(const Value *) const
verifyRemoved - Verify that the value is removed from all internal data structures.
Definition: GVN.cpp:700
uint32_t
Compiler.h
llvm::GVNPass::ValueTable
This class holds the mapping between values and value numbers.
Definition: GVN.h:151
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:126
Node
Definition: ItaniumDemangle.h:156
ValueHandle.h
llvm::MemoryDependenceResults
Provides a lazy, caching interface for making common memory aliasing information queries,...
Definition: MemoryDependenceAnalysis.h:266
llvm::None
constexpr std::nullopt_t None
Definition: None.h:27
llvm::SPII::Load
@ Load
Definition: SparcInstrInfo.h:32
llvm::GVNPass::ValueTable::setDomTree
void setDomTree(DominatorTree *D)
Definition: GVN.h:212
llvm::BumpPtrAllocatorImpl::Allocate
LLVM_ATTRIBUTE_RETURNS_NONNULL void * Allocate(size_t Size, Align Alignment)
Allocate space at the specified alignment.
Definition: Allocator.h:148
llvm::ExtractValueInst
This instruction extracts a struct member or array element value from an aggregate value.
Definition: Instructions.h:2446
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:226
llvm::GVNOptions::setLoadPRE
GVNOptions & setLoadPRE(bool LoadPRE)
Enables or disables PRE of loads in GVN.
Definition: GVN.h:90
llvm::GVNSinkPass::run
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Run the pass over the function.
Definition: GVNSink.cpp:913
llvm::GVNPass::ValueTable::setAliasAnalysis
void setAliasAnalysis(AAResults *A)
Definition: GVN.h:209
llvm::GVNOptions::setPRE
GVNOptions & setPRE(bool PRE)
Enables or disables PRE in GVN.
Definition: GVN.h:84
SmallVector.h
llvm::FunctionAnalysisManager
AnalysisManager< Function > FunctionAnalysisManager
Convenience typedef for the Function analysis manager.
Definition: PassManager.h:912
Dominators.h
N
#define N
llvm::GVNHoistPass::run
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Run the pass over the function.
Definition: GVNHoist.cpp:1239
llvm::GVNPass::Expression
Definition: GVN.cpp:125
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:2121
llvm::GVNOptions::GVNOptions
GVNOptions()=default
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:42
llvm::CallInst
This class represents a function call, abstracting a target machine's calling convention.
Definition: Instructions.h:1474
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
GEP
Hexagon Common GEP
Definition: HexagonCommonGEP.cpp:171
llvm::GVNPass
The core GVN pass object.
Definition: GVN.h:117
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:1806
llvm::GVNOptions::AllowLoadPRE
std::optional< bool > AllowLoadPRE
Definition: GVN.h:76
llvm::Value
LLVM Value Representation.
Definition: Value.h:74
llvm::GVNOptions::AllowLoadInLoopPRE
std::optional< bool > AllowLoadInLoopPRE
Definition: GVN.h:77
llvm::codeview::PublicSymFlags::Function
@ Function
SetVector.h