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;
136 function_ref<StringRef(StringRef)> MapClassName2PassName);
169 std::vector<Expression> Expressions;
170 std::vector<uint32_t> ExprIdx;
196 std::pair<uint32_t, bool> assignExpNewValueNum(
Expression &exp);
251 struct LeaderListNode {
253 LeaderListNode *Next;
260 const LeaderListNode *Current;
271 assert(Current &&
"Dereferenced end of leader list!");
272 Current = Current->Next;
276 return Current ==
Other.Current;
279 return Current !=
Other.Current;
285 auto I = NumToLeaders.
find(
N);
286 if (
I == NumToLeaders.
end()) {
288 leader_iterator(
nullptr));
292 leader_iterator(
nullptr));
295 void insert(
uint32_t N, Value *V,
const BasicBlock *BB);
296 void erase(
uint32_t N, Instruction *
I,
const BasicBlock *BB);
297 void verifyRemoved(
const Value *Inst)
const;
299 NumToLeaders.
clear();
300 TableAllocator.
Reset();
303 LeaderMap LeaderTable;
308 SmallMapVector<Value *, Value *, 4> ReplaceOperandsWithMap;
309 SmallVector<Instruction *, 8> InstrsToErase;
313 DenseMap<AssertingVH<BasicBlock>,
uint32_t> BlockRPONumber;
318 bool InvalidBlockRPONumbers =
true;
320 using LoadDepVect = SmallVector<NonLocalDepResult, 64>;
321 using AvailValInBlkVect = SmallVector<gvn::AvailableValueInBlock, 64>;
322 using UnavailBlkVect = SmallVector<BasicBlock *, 64>;
324 bool runImpl(Function &
F, AssumptionCache &RunAC, DominatorTree &RunDT,
325 const TargetLibraryInfo &RunTLI, AAResults &RunAA,
326 MemoryDependenceResults *RunMD, LoopInfo &LI,
327 OptimizationRemarkEmitter *ORE, MemorySSA *MSSA =
nullptr);
330 SmallVector<std::pair<Instruction *, unsigned>, 4> toSplit;
333 bool processLoad(LoadInst *L);
334 bool processNonLocalLoad(LoadInst *L);
335 bool processAssumeIntrinsic(AssumeInst *
II);
339 std::optional<gvn::AvailableValue>
340 AnalyzeLoadAvailability(LoadInst *Load, MemDepResult DepInfo, Value *
Address);
345 void AnalyzeLoadAvailability(LoadInst *Load, LoadDepVect &Deps,
346 AvailValInBlkVect &ValuesPerBlock,
347 UnavailBlkVect &UnavailableBlocks);
351 LoadInst *findLoadToHoistIntoPred(BasicBlock *Pred, BasicBlock *LoadBB,
354 bool PerformLoadPRE(LoadInst *Load, AvailValInBlkVect &ValuesPerBlock,
355 UnavailBlkVect &UnavailableBlocks);
360 bool performLoopLoadPRE(LoadInst *Load, AvailValInBlkVect &ValuesPerBlock,
361 UnavailBlkVect &UnavailableBlocks);
365 void eliminatePartiallyRedundantLoad(
366 LoadInst *Load, AvailValInBlkVect &ValuesPerBlock,
367 MapVector<BasicBlock *, Value *> &AvailableLoads,
368 MapVector<BasicBlock *, LoadInst *> *CriticalEdgePredAndLoad);
371 bool processInstruction(Instruction *
I);
372 bool processBlock(BasicBlock *BB);
373 void dump(DenseMap<uint32_t, Value *> &d)
const;
374 bool iterateOnFunction(Function &
F);
375 bool performPRE(Function &
F);
376 bool performScalarPRE(Instruction *
I);
377 bool performScalarPREInsertion(Instruction *Instr, BasicBlock *Pred,
378 BasicBlock *Curr,
unsigned int ValNo);
380 void cleanupGlobalSets();
381 void removeInstruction(Instruction *
I);
382 void verifyRemoved(
const Instruction *
I)
const;
383 bool splitCriticalEdges();
384 BasicBlock *splitCriticalEdges(BasicBlock *Pred, BasicBlock *Succ);
385 bool replaceOperandsForInBlockEquality(Instruction *
I)
const;
386 bool propagateEquality(Value *
LHS, Value *
RHS,
const BasicBlockEdge &Root,
387 bool DominatesByEdge);
388 bool processFoldableCondBr(BranchInst *BI);
389 void addDeadBlock(BasicBlock *BB);
390 void assignValNumForDeadCode();
391 void assignBlockRPONumber(Function &
F);
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_NAMESPACE
This file defines the DenseMap class.
early cse Early CSE w MemorySSA
This header defines various interfaces for pass management in LLVM.
This file implements a map that provides insertion order iteration.
uint64_t IntrinsicInst * II
ppc ctr loops PowerPC CTR Loops Verify
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
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.
void Reset()
Deallocate all but the current slab and reset the current pointer to the beginning of it,...
This class represents a function call, abstracting a target machine's calling convention.
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
iterator find(const_arg_type_t< KeyT > Val)
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
std::forward_iterator_tag iterator_category
bool operator==(const leader_iterator &Other) const
bool operator!=(const leader_iterator &Other) const
leader_iterator(const LeaderListNode *C)
leader_iterator & operator++()
std::ptrdiff_t difference_type
reference operator*() const
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)
bool isMemorySSAEnabled() const
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,...
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)
Provides information about what library functions are available for the current target.
LLVM Value Representation.
A range adaptor for a pair of iterators.
@ 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()
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.
std::optional< bool > AllowMemorySSA
GVNOptions & setMemorySSA(bool MemSSA)
Enables or disables use of MemorySSA.
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.
Represents an AvailableValue which can be rematerialized at the end of the associated BasicBlock.
Represents a particular available value that we know how to materialize.