15#ifndef LLVM_TRANSFORMS_SCALAR_GVN_H
16#define LLVM_TRANSFORMS_SCALAR_GVN_H
41class ExtractValueInst;
44class GetElementPtrInst;
45class ImplicitControlFlowTracking;
49class MemoryDependenceResults;
51class MemorySSAUpdater;
52class NonLocalDepResult;
53class OptimizationRemarkEmitter;
55class TargetLibraryInfo;
62struct AvailableValueInBlock;
129 function_ref<StringRef(StringRef)> MapClassName2PassName);
161 std::vector<Expression> Expressions;
162 std::vector<uint32_t> ExprIdx;
188 std::pair<uint32_t, bool> assignExpNewValueNum(
Expression &exp);
235 struct LeaderTableEntry {
238 LeaderTableEntry *Next;
256 bool InvalidBlockRPONumbers =
true;
269 LeaderTableEntry &Curr = LeaderTable[
N];
276 LeaderTableEntry *
Node = TableAllocator.
Allocate<LeaderTableEntry>();
279 Node->Next = Curr.Next;
285 void removeFromLeaderTable(
uint32_t N, Instruction *
I, BasicBlock *BB) {
286 LeaderTableEntry *Prev =
nullptr;
287 LeaderTableEntry *Curr = &LeaderTable[
N];
289 while (Curr && (Curr->Val !=
I || Curr->BB != BB)) {
298 Prev->Next = Curr->Next;
304 LeaderTableEntry *Next = Curr->Next;
305 Curr->Val = Next->Val;
307 Curr->Next = Next->Next;
313 SmallVector<std::pair<Instruction *, unsigned>, 4> toSplit;
316 bool processLoad(LoadInst *L);
317 bool processNonLocalLoad(LoadInst *L);
318 bool processAssumeIntrinsic(AssumeInst *II);
322 std::optional<gvn::AvailableValue>
323 AnalyzeLoadAvailability(LoadInst *Load, MemDepResult DepInfo, Value *
Address);
328 void AnalyzeLoadAvailability(LoadInst *Load, LoadDepVect &Deps,
329 AvailValInBlkVect &ValuesPerBlock,
330 UnavailBlkVect &UnavailableBlocks);
332 bool PerformLoadPRE(LoadInst *Load, AvailValInBlkVect &ValuesPerBlock,
333 UnavailBlkVect &UnavailableBlocks);
338 bool performLoopLoadPRE(LoadInst *Load, AvailValInBlkVect &ValuesPerBlock,
339 UnavailBlkVect &UnavailableBlocks);
343 void eliminatePartiallyRedundantLoad(
344 LoadInst *Load, AvailValInBlkVect &ValuesPerBlock,
345 MapVector<BasicBlock *, Value *> &AvailableLoads);
348 bool processInstruction(Instruction *
I);
349 bool processBlock(BasicBlock *BB);
350 void dump(DenseMap<uint32_t, Value *> &d)
const;
351 bool iterateOnFunction(Function &
F);
352 bool performPRE(Function &
F);
353 bool performScalarPRE(Instruction *
I);
354 bool performScalarPREInsertion(Instruction *Instr, BasicBlock *Pred,
355 BasicBlock *Curr,
unsigned int ValNo);
357 void cleanupGlobalSets();
358 void verifyRemoved(
const Instruction *
I)
const;
359 bool splitCriticalEdges();
360 BasicBlock *splitCriticalEdges(BasicBlock *Pred, BasicBlock *Succ);
361 bool replaceOperandsForInBlockEquality(Instruction *
I)
const;
362 bool propagateEquality(Value *
LHS, Value *
RHS,
const BasicBlockEdge &Root,
363 bool DominatesByEdge);
364 bool processFoldableCondBr(BranchInst *BI);
365 void addDeadBlock(BasicBlock *BB);
366 void assignValNumForDeadCode();
367 void assignBlockRPONumber(Function &
F);
amdgpu Simplify well known AMD library false FunctionCallee Value * Arg
This file defines the BumpPtrAllocator interface.
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
#define LLVM_LIBRARY_VISIBILITY
LLVM_LIBRARY_VISIBILITY - If a class marked with this attribute is linked into a shared library,...
This file defines the DenseMap class.
early cse Early CSE w MemorySSA
This file implements a map that provides insertion order iteration.
ppc ctr loops PowerPC CTR Loops Verify
This header defines various interfaces for pass management in LLVM.
This file implements a set that has insertion order iteration characteristics.
This file defines the SmallVector class.
A container for analyses that lazily runs them and caches their results.
A cache of @llvm.assume calls within a function.
LLVM Basic Block Representation.
Allocate memory in an ever growing pool, as if by bump-pointer.
LLVM_ATTRIBUTE_RETURNS_NONNULL void * Allocate(size_t Size, Align Alignment)
Allocate space at the specified alignment.
This class represents a function call, abstracting a target machine's calling convention.
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
This class holds the mapping between values and value numbers.
ValueTable(ValueTable &&Arg)
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...
uint32_t getNextUnusedValueNumber()
uint32_t lookupOrAdd(Value *V)
lookup_or_add - Returns the value number for the specified value, assigning it a new number if it did...
uint32_t lookup(Value *V, bool Verify=true) const
Returns the value number of the specified value.
ValueTable & operator=(const ValueTable &Arg)
void setAliasAnalysis(AAResults *A)
void clear()
Remove all entries from the ValueTable.
bool exists(Value *V) const
Returns true if a value number exists for the specified value.
ValueTable(const ValueTable &Arg)
AAResults * getAliasAnalysis() const
uint32_t phiTranslate(const BasicBlock *BB, const BasicBlock *PhiBlock, uint32_t Num, GVNPass &Gvn)
Wrap phiTranslateImpl to provide caching functionality.
void setMemDep(MemoryDependenceResults *M)
void erase(Value *v)
Remove a value from the value numbering.
void add(Value *V, uint32_t num)
add - Insert a value into the table with a specified value number.
void setDomTree(DominatorTree *D)
void eraseTranslateCacheEntry(uint32_t Num, const BasicBlock &CurrBlock)
Erase stale entry from phiTranslate cache so phiTranslate can be computed again.
void verifyRemoved(const Value *) const
verifyRemoved - Verify that the value is removed from all internal data structures.
The core GVN pass object.
bool isPREEnabled() const
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Run the pass over the function.
AAResults * getAliasAnalysis() const
bool isLoadPREEnabled() const
GVNPass(GVNOptions Options={})
void printPipeline(raw_ostream &OS, function_ref< StringRef(StringRef)> MapClassName2PassName)
DominatorTree & getDominatorTree() const
bool isLoadInLoopPREEnabled() const
bool isLoadPRESplitBackedgeEnabled() const
void markInstructionForDeletion(Instruction *I)
This removes the specified instruction from our various maps and marks it for deletion.
bool isMemDepEnabled() const
MemoryDependenceResults & getMemDep() const
an instruction for type-safe pointer arithmetic to access elements of arrays and structs
This class allows to keep track on instructions with implicit control flow.
Provides a lazy, caching interface for making common memory aliasing information queries,...
Encapsulates MemorySSA, including all data associated with memory accesses.
A set of analyses that are preserved following a run of a transformation pass.
A vector that has set insertion semantics.
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Provides information about what library functions are available for the current target.
LLVM Value Representation.
@ C
The default llvm calling convention, compatible with C.
@ BasicBlock
Various leaf nodes.
This is an optimization pass for GlobalISel generic memory operations.
AnalysisManager< Function > FunctionAnalysisManager
Convenience typedef for the Function analysis manager.
FunctionPass * createGVNPass(bool NoMemDepAnalysis=false)
Create a legacy GVN pass.
An information struct used to provide DenseMap with the various necessary components for a given valu...
A simple and fast domtree-based GVN pass to hoist common expressions from sibling branches.
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Run the pass over the function.
A set of parameters to control various transforms performed by GVN pass.
GVNOptions & setLoadPRE(bool LoadPRE)
Enables or disables PRE of loads in GVN.
std::optional< bool > AllowLoadPRESplitBackedge
GVNOptions & setPRE(bool PRE)
Enables or disables PRE in GVN.
GVNOptions & setLoadInLoopPRE(bool LoadInLoopPRE)
std::optional< bool > AllowPRE
std::optional< bool > AllowLoadInLoopPRE
std::optional< bool > AllowMemDep
GVNOptions & setMemDep(bool MemDep)
Enables or disables use of MemDepAnalysis.
std::optional< bool > AllowLoadPRE
GVNOptions & setLoadPRESplitBackedge(bool LoadPRESplitBackedge)
Enables or disables PRE of loads in GVN.
Uses an "inverted" value numbering to decide the similarity of expressions and sinks similar expressi...
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Run the pass over the function.
A CRTP mix-in to automatically provide informational APIs needed for passes.
A MapVector that performs no allocations if smaller than a certain size.