40 #ifndef LLVM_ANALYSIS_DEPENDENCEANALYSIS_H 41 #define LLVM_ANALYSIS_DEPENDENCEANALYSIS_H 49 template <
typename T>
class ArrayRef;
52 class ScalarEvolution;
81 NextPredecessor(nullptr),
82 NextSuccessor(nullptr) {}
203 const Dependence *NextPredecessor, *NextSuccessor;
251 bool isPeelLast(
unsigned Level)
const override;
260 bool isScalar(
unsigned Level)
const override;
263 unsigned short Levels;
264 bool LoopIndependent;
266 std::unique_ptr<DVEntry[]> DV;
276 : AA(AA), SE(SE), LI(LI), F(F) {}
284 std::unique_ptr<Dependence> depends(
Instruction *Src,
286 bool PossiblyLoopIndependent);
344 enum ClassificationKind { ZIV, SIV, RDIV, MIV, NonLinear } Classification;
350 struct CoefficientInfo {
354 const SCEV *Iterations;
358 const SCEV *Iterations;
362 unsigned char DirSet;
387 const Loop *AssociatedLoop;
391 bool isEmpty()
const {
return Kind ==
Empty; }
394 bool isPoint()
const {
return Kind == Point; }
397 bool isDistance()
const {
return Kind ==
Distance; }
402 bool isLine()
const {
return Kind == Line || Kind ==
Distance; }
405 bool isAny()
const {
return Kind ==
Any; }
409 const SCEV *getX()
const;
413 const SCEV *getY()
const;
417 const SCEV *getA()
const;
421 const SCEV *getB()
const;
425 const SCEV *getC()
const;
429 const SCEV *getD()
const;
432 const Loop *getAssociatedLoop()
const;
435 void setPoint(
const SCEV *
X,
const SCEV *
Y,
const Loop *CurrentLoop);
438 void setLine(
const SCEV *A,
const SCEV *B,
439 const SCEV *C,
const Loop *CurrentLoop);
442 void setDistance(
const SCEV *
D,
const Loop *CurrentLoop);
505 void establishNestingLevels(
const Instruction *Src,
508 unsigned CommonLevels, SrcLevels, MaxLevels;
512 unsigned mapSrcLoop(
const Loop *SrcLoop)
const;
516 unsigned mapDstLoop(
const Loop *DstLoop)
const;
532 void removeMatchingExtensions(Subscript *Pair);
536 void collectCommonLoops(
const SCEV *Expression,
537 const Loop *LoopNest,
542 bool checkSrcSubscript(
const SCEV *Src,
543 const Loop *LoopNest,
548 bool checkDstSubscript(
const SCEV *Dst,
549 const Loop *LoopNest,
558 const SCEV *
Y)
const;
564 bool isKnownLessThan(
const SCEV *S,
const SCEV *
Size)
const;
586 Subscript::ClassificationKind classifyPair(
const SCEV *Src,
587 const Loop *SrcLoopNest,
589 const Loop *DstLoopNest,
597 bool testZIV(
const SCEV *Src,
611 bool testSIV(
const SCEV *Src,
615 Constraint &NewConstraint,
616 const SCEV *&SplitIter)
const;
627 bool testRDIV(
const SCEV *Src,
634 bool testMIV(
const SCEV *Src,
647 bool strongSIVtest(
const SCEV *Coeff,
648 const SCEV *SrcConst,
649 const SCEV *DstConst,
650 const Loop *CurrentLoop,
653 Constraint &NewConstraint)
const;
665 bool weakCrossingSIVtest(
const SCEV *SrcCoeff,
666 const SCEV *SrcConst,
667 const SCEV *DstConst,
668 const Loop *CurrentLoop,
671 Constraint &NewConstraint,
672 const SCEV *&SplitIter)
const;
683 bool exactSIVtest(
const SCEV *SrcCoeff,
684 const SCEV *DstCoeff,
685 const SCEV *SrcConst,
686 const SCEV *DstConst,
687 const Loop *CurrentLoop,
690 Constraint &NewConstraint)
const;
702 bool weakZeroSrcSIVtest(
const SCEV *DstCoeff,
703 const SCEV *SrcConst,
704 const SCEV *DstConst,
705 const Loop *CurrentLoop,
708 Constraint &NewConstraint)
const;
720 bool weakZeroDstSIVtest(
const SCEV *SrcCoeff,
721 const SCEV *SrcConst,
722 const SCEV *DstConst,
723 const Loop *CurrentLoop,
726 Constraint &NewConstraint)
const;
736 bool exactRDIVtest(
const SCEV *SrcCoeff,
737 const SCEV *DstCoeff,
738 const SCEV *SrcConst,
739 const SCEV *DstConst,
753 bool symbolicRDIVtest(
const SCEV *SrcCoeff,
754 const SCEV *DstCoeff,
755 const SCEV *SrcConst,
756 const SCEV *DstConst,
758 const Loop *DstLoop)
const;
766 bool gcdMIVtest(
const SCEV *Src,
774 bool banerjeeMIVtest(
const SCEV *Src,
782 CoefficientInfo *collectCoeffInfo(
const SCEV *Subscript,
788 const SCEV *getPositivePart(
const SCEV *X)
const;
792 const SCEV *getNegativePart(
const SCEV *X)
const;
797 const SCEV *getLowerBound(BoundInfo *Bound)
const;
802 const SCEV *getUpperBound(BoundInfo *Bound)
const;
809 unsigned exploreDirections(
unsigned Level,
814 unsigned &DepthExpanded,
815 const SCEV *Delta)
const;
818 bool testBounds(
unsigned char DirKind,
821 const SCEV *Delta)
const;
825 void findBoundsALL(CoefficientInfo *A,
832 void findBoundsLT(CoefficientInfo *A,
839 void findBoundsGT(CoefficientInfo *A,
846 void findBoundsEQ(CoefficientInfo *A,
853 bool intersectConstraints(Constraint *X,
854 const Constraint *Y);
872 bool propagateDistance(
const SCEV *&Src,
874 Constraint &CurConstraint,
880 bool propagatePoint(
const SCEV *&Src,
882 Constraint &CurConstraint);
889 bool propagateLine(
const SCEV *&Src,
891 Constraint &CurConstraint,
899 const SCEV *findCoefficient(
const SCEV *Expr,
900 const Loop *TargetLoop)
const;
907 const SCEV *zeroCoefficient(
const SCEV *Expr,
908 const Loop *TargetLoop)
const;
915 const SCEV *addToCoefficient(
const SCEV *Expr,
916 const Loop *TargetLoop,
922 const Constraint &CurConstraint)
const;
960 void releaseMemory()
override;
966 std::unique_ptr<DependenceInfo>
info;
Dependence(Dependence &&)=default
DependenceInfo(Function *F, AliasAnalysis *AA, ScalarEvolution *SE, LoopInfo *LI)
FunctionPass * createDependenceAnalysisWrapperPass()
createDependenceAnalysisPass - This creates an instance of the DependenceAnalysis wrapper pass...
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
bool isUnordered() const
isUnordered - Returns true if dependence is Input
static bool isLoopInvariant(Value *V, const Loop *L, const DominatorTree *DT)
Perform a quick domtree based check for loop invariance assuming that V is used within the loop...
This is a 'bitvector' (really, a variable-sized bit array), optimized for the case when the array is ...
virtual const SCEV * getDistance(unsigned Level) const
getDistance - Returns the distance (or NULL) associated with a particular level.
AnalysisPass to compute dependence information in a function.
This class represents lattice values for constants.
DependenceAnalysisWrapperPass()
A Module instance is used to store all the information related to an LLVM module. ...
Legacy pass manager pass to access dependence information.
virtual bool isConsistent() const
isConsistent - Returns true if this dependence is consistent (occurs every time the source and destin...
The main scalar evolution driver.
virtual bool isConfused() const
isConfused - Returns true if this dependence is confused (the compiler understands nothing and makes ...
block Block Frequency true
DependenceInfo - This class is the main dependence-analysis driver.
void dump(raw_ostream &OS) const
dump - For debugging purposes, dumps a dependence to OS.
const Dependence * getNextSuccessor() const
getNextSuccessor - Returns the value of the NextSuccessor field.
bool isConsistent() const override
isConsistent - Returns true if this dependence is consistent (occurs every time the source and destin...
static GCMetadataPrinterRegistry::Add< OcamlGCMetadataPrinter > Y("ocaml", "ocaml 3.10-compatible collector")
virtual bool isScalar(unsigned Level) const
isScalar - Returns true if a particular level is scalar; that is, if no subscript in the source or de...
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
void initializeDependenceAnalysisWrapperPassPass(PassRegistry &)
bool isFlow() const
isFlow - Returns true if this is a flow (aka true) dependence.
A CRTP mix-in to automatically provide informational APIs needed for passes.
Instruction * getSrc() const
getSrc - Returns the source instruction for this dependence.
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory)...
unsigned getLevels() const override
getLevels - Returns the number of common loops surrounding the source and destination of the dependen...
bool isKnownNonNegative(const Value *V, const DataLayout &DL, unsigned Depth=0, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, bool UseInstrInfo=true)
Returns true if the give value is known to be non-negative.
const Dependence * getNextPredecessor() const
getNextPredecessor - Returns the value of the NextPredecessor field.
bool isLoopIndependent() const override
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.
DependenceAnalysisPrinterPass(raw_ostream &OS)
static bool runOnFunction(Function &F, bool PostInlining)
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
A set of analyses that are preserved following a run of a transformation pass.
The instances of the Type class are immutable: once they are created, they are never changed...
This is an important base class in LLVM.
bool isConfused() const override
isConfused - Returns true if this dependence is confused (the compiler understands nothing and makes ...
A CRTP mix-in that provides informational APIs needed for analysis passes.
Printer pass to dump DA results.
Represent the analysis usage information of a pass.
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
FunctionPass class - This class is used to implement most global optimizations.
virtual bool isPeelLast(unsigned Level) const
isPeelLast - Returns true if peeling the last iteration from this loop will break this dependence...
static void print(raw_ostream &Out, object::Archive::Kind Kind, T Val)
Dependence & operator=(Dependence &&)=default
virtual unsigned getLevels() const
getLevels - Returns the number of common loops surrounding the source and destination of the dependen...
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
virtual unsigned getDirection(unsigned Level) const
getDirection - Returns the direction associated with a particular level.
Dependence(Instruction *Source, Instruction *Destination)
bool isOrdered() const
isOrdered - Returns true if dependence is Output, Flow, or Anti
static void propagate(InstantiatedValue From, InstantiatedValue To, MatchState State, ReachabilitySet &ReachSet, std::vector< WorkListItem > &WorkList)
virtual bool isLoopIndependent() const
isLoopIndependent - Returns true if this is a loop-independent dependence.
Function * getFunction() const
bool isAnti() const
isAnti - Returns true if this is an anti dependence.
This class represents an analyzed expression in the program.
Represents a single loop in the control flow graph.
virtual bool isSplitable(unsigned Level) const
isSplitable - Returns true if splitting this loop will break the dependence.
FullDependence - This class represents a dependence between two memory references in a function...
Dependence::DVEntry - Each level in the distance/direction vector has a direction (or perhaps a union...
Instruction * getDst() const
getDst - Returns the destination instruction for this dependence.
bool isInput() const
isInput - Returns true if this is an input dependence.
LLVM Value Representation.
This class implements an extremely fast bulk output stream that can only output to a stream...
A container for analyses that lazily runs them and caches their results.
Dependence - This class represents a dependence between two memory memory references in a function...
void setNextSuccessor(const Dependence *succ)
setNextSuccessor - Sets the value of the NextSuccessor field.
virtual bool isPeelFirst(unsigned Level) const
isPeelFirst - Returns true if peeling the first iteration from this loop will break this dependence...
A special type used by analysis passes to provide an address that identifies that particular analysis...
This class represents a constant integer value.