39#ifndef LLVM_ANALYSIS_DEPENDENCEANALYSIS_H
40#define LLVM_ANALYSIS_DEPENDENCEANALYSIS_H
52struct AnalysisOptions;
82 :
Src(Source),
Dst(Destination), Assumptions(
A) {}
99 enum :
unsigned char {
125 bool isOutput()
const;
157 virtual unsigned getDirection(
unsigned Level,
bool SameSD =
false)
const {
189 virtual bool isScalar(
unsigned Level,
bool SameSD =
false)
const;
213 void dumpImp(
raw_ostream &OS,
bool IsSameSD =
false)
const;
220 const Dependence *NextPredecessor =
nullptr, *NextSuccessor =
nullptr;
236 bool PossiblyLoopIndependent,
unsigned Levels);
259 assert(0 < Level && Level <= Levels &&
"Level out of range");
260 return DV[Level - 1];
263 Level <=
static_cast<unsigned>(Levels) + SameSDLevels &&
264 "isSameSD level out of range");
265 return DVSameSD[Level - Levels - 1];
271 unsigned getDirection(
unsigned Level,
bool SameSD =
false)
const override;
275 const SCEV *getDistance(
unsigned Level,
bool SameSD =
false)
const override;
279 bool isDirectionNegative()
const override;
292 bool inSameSDLoops(
unsigned Level)
const override;
297 bool isScalar(
unsigned Level,
bool SameSD =
false)
const override;
300 unsigned short Levels;
301 unsigned short SameSDLevels;
302 bool LoopIndependent;
303 std::unique_ptr<DVEntry[]> DV;
304 std::unique_ptr<DVEntry[]> DVSameSD;
316 FunctionAnalysisManager::Invalidator &Inv);
325 LLVM_ABI std::unique_ptr<Dependence>
327 bool UnderRuntimeAssumptions =
false);
332 const AnalysisOptions &Opts;
341 void updateLoopAliasScopes(
const Loop *L);
349 enum ClassificationKind { ZIV, SIV, RDIV, MIV, NonLinear } Classification;
350 SmallBitVector
Loops;
353 struct CoefficientInfo {
354 const SCEV *SrcCoeff;
355 const SCEV *DstCoeff;
356 const SCEV *MaxIterIndex;
360 const SCEV *Upper[8];
361 const SCEV *Lower[8];
362 unsigned char Direction;
363 unsigned char DirSet;
370 bool haveSameSD(
const Loop *SrcLoop,
const Loop *DstLoop)
const;
434 void establishNestingLevels(
const Instruction *Src,
const Instruction *Dst);
436 unsigned CommonLevels, SrcLevels, MaxLevels, SameSDLevels;
440 unsigned mapSrcLoop(
const Loop *SrcLoop)
const;
444 unsigned mapDstLoop(
const Loop *DstLoop)
const;
448 bool isLoopInvariant(
const SCEV *Expression,
const Loop *LoopNest)
const;
452 void collectCommonLoops(
const SCEV *Expression,
const Loop *LoopNest,
453 SmallBitVector &
Loops)
const;
457 bool checkSrcSubscript(
const SCEV *Src,
const Loop *LoopNest,
458 SmallBitVector &
Loops);
462 bool checkDstSubscript(
const SCEV *Dst,
const Loop *LoopNest,
463 SmallBitVector &
Loops);
470 const SCEV *collectUpperBound(
const Loop *l,
Type *
T)
const;
475 std::optional<APInt> collectNonNegativeConstantUpperBound(
const Loop *L,
481 Subscript::ClassificationKind
482 classifyPair(
const SCEV *Src,
const Loop *SrcLoopNest,
const SCEV *Dst,
483 const Loop *DstLoopNest, SmallBitVector &
Loops);
489 bool testZIV(
const SCEV *Src,
const SCEV *Dst, FullDependence &Result)
const;
500 bool testSIV(
const SCEV *Src,
const SCEV *Dst,
unsigned &Level,
501 FullDependence &Result,
bool UnderRuntimeAssumptions);
511 bool testRDIV(
const SCEV *Src,
const SCEV *Dst, FullDependence &Result)
const;
516 bool testMIV(
const SCEV *Src,
const SCEV *Dst,
const SmallBitVector &
Loops,
517 FullDependence &Result)
const;
527 bool strongSIVtest(
const SCEVAddRecExpr *Src,
const SCEVAddRecExpr *Dst,
528 unsigned Level, FullDependence &Result,
529 bool UnderRuntimeAssumptions);
539 bool weakCrossingSIVtest(
const SCEVAddRecExpr *Src,
const SCEVAddRecExpr *Dst,
540 unsigned Level, FullDependence &Result)
const;
550 bool exactSIVtest(
const SCEVAddRecExpr *Src,
const SCEVAddRecExpr *Dst,
551 unsigned Level, FullDependence &Result)
const;
555 bool weakZeroSIVtestImpl(
const SCEVAddRecExpr *AR,
const SCEV *Const,
556 unsigned Level, FullDependence &Result)
const;
566 bool weakZeroSrcSIVtest(
const SCEV *SrcConst,
const SCEVAddRecExpr *Dst,
567 unsigned Level, FullDependence &Result)
const;
577 bool weakZeroDstSIVtest(
const SCEVAddRecExpr *Src,
const SCEV *DstConst,
578 unsigned Level, FullDependence &Result)
const;
587 bool exactRDIVtest(
const SCEVAddRecExpr *Src,
const SCEVAddRecExpr *Dst,
588 FullDependence &Result)
const;
594 bool exactTestImpl(
const SCEVAddRecExpr *Src,
const SCEVAddRecExpr *Dst,
595 FullDependence &Result,
596 std::optional<unsigned> Level)
const;
603 bool gcdMIVtest(
const SCEV *Src,
const SCEV *Dst,
604 FullDependence &Result)
const;
609 bool banerjeeMIVtest(
const SCEV *Src,
const SCEV *Dst,
610 const SmallBitVector &
Loops,
611 FullDependence &Result)
const;
616 const SCEV *collectCoeffInfo(
const SCEV *Subscript,
bool SrcFlag,
635 const SCEV *accumulateCoefficientsGCD(
const SCEV *Expr,
const Loop *CurLoop,
636 const SCEV *&CurLoopCoeff,
637 APInt &RunningGCD)
const;
655 const SmallBitVector &
Loops,
const SCEV *Delta,
656 const FullDependence &Result)
const;
660 bool testBounds(
unsigned char DirKind,
unsigned Level,
685 bool tryDelinearize(Instruction *Src, Instruction *Dst,
686 SmallVectorImpl<Subscript> &Pair);
691 bool tryDelinearizeFixedSize(Instruction *Src, Instruction *Dst,
692 const SCEV *SrcAccessFn,
const SCEV *DstAccessFn,
693 SmallVectorImpl<const SCEV *> &SrcSubscripts,
694 SmallVectorImpl<const SCEV *> &DstSubscripts);
700 tryDelinearizeParametricSize(Instruction *Src, Instruction *Dst,
701 const SCEV *SrcAccessFn,
const SCEV *DstAccessFn,
702 SmallVectorImpl<const SCEV *> &SrcSubscripts,
703 SmallVectorImpl<const SCEV *> &DstSubscripts);
707 bool checkSubscript(
const SCEV *Expr,
const Loop *LoopNest,
708 SmallBitVector &
Loops,
bool IsSrc);
726 : OS(OS), NormalizeResults(NormalizeResults) {}
732 bool NormalizeResults;
748 std::unique_ptr<DependenceInfo> info;
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
static void print(raw_ostream &Out, object::Archive::Kind Kind, T Val)
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
static bool runOnFunction(Function &F, bool PostInlining)
This header defines various interfaces for pass management in LLVM.
static bool isInput(const ArrayRef< StringRef > &Prefixes, StringRef Arg)
FunctionAnalysisManager FAM
This file implements the SmallBitVector class.
This file defines the SmallPtrSet class.
Represent the analysis usage information of a pass.
Represent a constant reference to an array (0 or more elements consecutively in memory),...
void getAnalysisUsage(AnalysisUsage &) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
DependenceInfo & getDI() const
DependenceAnalysisWrapperPass()
void releaseMemory() override
releaseMemory() - This member can be implemented by a pass if it wants to be able to release its memo...
AnalysisPass to compute dependence information in a function.
LLVM_ABI Result run(Function &F, FunctionAnalysisManager &FAM)
DependenceInfo - This class is the main dependence-analysis driver.
LLVM_ABI bool invalidate(Function &F, const PreservedAnalyses &PA, FunctionAnalysisManager::Invalidator &Inv)
Handle transitive invalidation when the cached analysis results go away.
Function * getFunction() const
LLVM_ABI DependenceInfo(Function *F, AAResults *AA, ScalarEvolution *SE, LoopInfo *LI)
LLVM_ABI std::unique_ptr< Dependence > depends(Instruction *Src, Instruction *Dst, bool UnderRuntimeAssumptions=false)
depends - Tests for a dependence between the Src and Dst instructions.
Instruction * getDst() const
getDst - Returns the destination instruction for this dependence.
Dependence & operator=(Dependence &&)=default
bool isOrdered() const
isOrdered - Returns true if dependence is Output, Flow, or Anti
void setNextSuccessor(const Dependence *succ)
setNextSuccessor - Sets the value of the NextSuccessor field.
friend class DependenceInfo
Dependence(Instruction *Source, Instruction *Destination, const SCEVUnionPredicate &A)
Dependence(Dependence &&)=default
bool isUnordered() const
isUnordered - Returns true if dependence is Input
SCEVUnionPredicate getRuntimeAssumptions() const
getRuntimeAssumptions - Returns the runtime assumptions under which this Dependence relation is valid...
virtual bool isConfused() const
isConfused - Returns true if this dependence is confused (the compiler understands nothing and makes ...
virtual unsigned getSameSDLevels() const
getSameSDLevels - Returns the number of separate SameSD loops surrounding the source and destination ...
virtual const SCEV * getDistance(unsigned Level, bool SameSD=false) const
getDistance - Returns the distance (or NULL) associated with a particular common or SameSD level.
virtual void negate(ScalarEvolution &SE)
Negate the dependence by swapping the source and destination, and reversing the direction and distanc...
virtual unsigned getLevels() const
getLevels - Returns the number of common loops surrounding the source and destination of the dependen...
const Dependence * getNextPredecessor() const
getNextPredecessor - Returns the value of the NextPredecessor field.
virtual unsigned getDirection(unsigned Level, bool SameSD=false) const
getDirection - Returns the direction associated with a particular common or SameSD level.
bool isFlow() const
isFlow - Returns true if this is a flow (aka true) dependence.
virtual ~Dependence()=default
virtual bool normalize(ScalarEvolution *SE)
If the direction vector is negative, normalize the direction vector to make it non-negative.
bool isAnti() const
isAnti - Returns true if this is an anti dependence.
const Dependence * getNextSuccessor() const
getNextSuccessor - Returns the value of the NextSuccessor field.
virtual bool isDirectionNegative() const
Check if the direction vector is negative.
Instruction * getSrc() const
getSrc - Returns the source instruction for this dependence.
virtual bool isLoopIndependent() const
isLoopIndependent - Returns true if this is a loop-independent dependence.
bool isOutput() const
isOutput - Returns true if this is an output dependence.
void setNextPredecessor(const Dependence *pred)
setNextPredecessor - Sets the value of the NextPredecessor field.
virtual bool inSameSDLoops(unsigned Level) const
inSameSDLoops - Returns true if this level is an SameSD level, i.e., performed across two separate lo...
FullDependence(Instruction *Source, Instruction *Destination, const SCEVUnionPredicate &Assumes, bool PossiblyLoopIndependent, unsigned Levels)
bool isConfused() const override
isConfused - Returns true if this dependence is confused (the compiler understands nothing and makes ...
friend class DependenceInfo
DVEntry getDVEntry(unsigned Level, bool IsSameSD) const
getDVEntry - Returns the DV entry associated with a regular or a SameSD level.
bool isLoopIndependent() const override
isLoopIndependent - Returns true if this is a loop-independent dependence.
unsigned getSameSDLevels() const override
getSameSDLevels - Returns the number of separate SameSD loops surrounding the source and destination ...
unsigned getLevels() const override
getLevels - Returns the number of common loops surrounding the source and destination of the dependen...
FunctionPass class - This class is used to implement most global optimizations.
Represents a single loop in the control flow graph.
A Module instance is used to store all the information related to an LLVM module.
A set of analyses that are preserved following a run of a transformation pass.
This class represents a constant integer value.
This class represents a composition of other SCEV predicates, and is the class that most clients will...
This class represents an analyzed expression in the program.
The main scalar evolution driver.
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
This class implements an extremely fast bulk output stream that can only output to a stream.
Abstract Attribute helper functions.
This is an optimization pass for GlobalISel generic memory operations.
void dump(const SparseBitVector< ElementSize > &LHS, raw_ostream &out)
MutableArrayRef(T &OneElt) -> MutableArrayRef< T >
ArrayRef(const T &OneElt) -> ArrayRef< T >
AnalysisManager< Function > FunctionAnalysisManager
Convenience typedef for the Function analysis manager.
LLVM_ABI FunctionPass * createDependenceAnalysisWrapperPass()
createDependenceAnalysisPass - This creates an instance of the DependenceAnalysis wrapper pass.
A CRTP mix-in that provides informational APIs needed for analysis passes.
A special type used by analysis passes to provide an address that identifies that particular analysis...
DependenceAnalysisPrinterPass(raw_ostream &OS, bool NormalizeResults=false)
LLVM_ABI PreservedAnalyses run(Function &F, FunctionAnalysisManager &FAM)
Dependence::DVEntry - Each level in the distance/direction vector has a direction (or perhaps a union...
A CRTP mix-in for passes that should not be skipped.