39 #ifndef LLVM_ANALYSIS_DEPENDENCEANALYSIS_H 40 #define LLVM_ANALYSIS_DEPENDENCEANALYSIS_H 48 template <
typename T>
class ArrayRef;
51 class ScalarEvolution;
80 NextPredecessor(nullptr),
81 NextSuccessor(nullptr) {}
202 const Dependence *NextPredecessor, *NextSuccessor;
250 bool isPeelLast(
unsigned Level)
const override;
259 bool isScalar(
unsigned Level)
const override;
262 unsigned short Levels;
263 bool LoopIndependent;
265 std::unique_ptr<DVEntry[]> DV;
275 : AA(AA), SE(SE), LI(LI), F(F) {}
287 std::unique_ptr<Dependence> depends(
Instruction *Src,
289 bool PossiblyLoopIndependent);
347 enum ClassificationKind { ZIV, SIV, RDIV, MIV, NonLinear } Classification;
353 struct CoefficientInfo {
357 const SCEV *Iterations;
361 const SCEV *Iterations;
365 unsigned char DirSet;
390 const Loop *AssociatedLoop;
394 bool isEmpty()
const {
return Kind ==
Empty; }
397 bool isPoint()
const {
return Kind == Point; }
400 bool isDistance()
const {
return Kind ==
Distance; }
405 bool isLine()
const {
return Kind == Line || Kind ==
Distance; }
408 bool isAny()
const {
return Kind ==
Any; }
412 const SCEV *getX()
const;
416 const SCEV *getY()
const;
420 const SCEV *getA()
const;
424 const SCEV *getB()
const;
428 const SCEV *getC()
const;
432 const SCEV *getD()
const;
435 const Loop *getAssociatedLoop()
const;
438 void setPoint(
const SCEV *
X,
const SCEV *
Y,
const Loop *CurrentLoop);
441 void setLine(
const SCEV *A,
const SCEV *B,
442 const SCEV *C,
const Loop *CurrentLoop);
445 void setDistance(
const SCEV *
D,
const Loop *CurrentLoop);
508 void establishNestingLevels(
const Instruction *Src,
511 unsigned CommonLevels, SrcLevels, MaxLevels;
515 unsigned mapSrcLoop(
const Loop *SrcLoop)
const;
519 unsigned mapDstLoop(
const Loop *DstLoop)
const;
523 bool isLoopInvariant(
const SCEV *Expression,
const Loop *LoopNest)
const;
535 void removeMatchingExtensions(Subscript *Pair);
539 void collectCommonLoops(
const SCEV *Expression,
540 const Loop *LoopNest,
545 bool checkSrcSubscript(
const SCEV *Src,
546 const Loop *LoopNest,
551 bool checkDstSubscript(
const SCEV *Dst,
552 const Loop *LoopNest,
561 const SCEV *
Y)
const;
567 bool isKnownLessThan(
const SCEV *S,
const SCEV *
Size)
const;
589 Subscript::ClassificationKind classifyPair(
const SCEV *Src,
590 const Loop *SrcLoopNest,
592 const Loop *DstLoopNest,
600 bool testZIV(
const SCEV *Src,
614 bool testSIV(
const SCEV *Src,
618 Constraint &NewConstraint,
619 const SCEV *&SplitIter)
const;
630 bool testRDIV(
const SCEV *Src,
637 bool testMIV(
const SCEV *Src,
650 bool strongSIVtest(
const SCEV *Coeff,
651 const SCEV *SrcConst,
652 const SCEV *DstConst,
653 const Loop *CurrentLoop,
656 Constraint &NewConstraint)
const;
668 bool weakCrossingSIVtest(
const SCEV *SrcCoeff,
669 const SCEV *SrcConst,
670 const SCEV *DstConst,
671 const Loop *CurrentLoop,
674 Constraint &NewConstraint,
675 const SCEV *&SplitIter)
const;
686 bool exactSIVtest(
const SCEV *SrcCoeff,
687 const SCEV *DstCoeff,
688 const SCEV *SrcConst,
689 const SCEV *DstConst,
690 const Loop *CurrentLoop,
693 Constraint &NewConstraint)
const;
705 bool weakZeroSrcSIVtest(
const SCEV *DstCoeff,
706 const SCEV *SrcConst,
707 const SCEV *DstConst,
708 const Loop *CurrentLoop,
711 Constraint &NewConstraint)
const;
723 bool weakZeroDstSIVtest(
const SCEV *SrcCoeff,
724 const SCEV *SrcConst,
725 const SCEV *DstConst,
726 const Loop *CurrentLoop,
729 Constraint &NewConstraint)
const;
739 bool exactRDIVtest(
const SCEV *SrcCoeff,
740 const SCEV *DstCoeff,
741 const SCEV *SrcConst,
742 const SCEV *DstConst,
756 bool symbolicRDIVtest(
const SCEV *SrcCoeff,
757 const SCEV *DstCoeff,
758 const SCEV *SrcConst,
759 const SCEV *DstConst,
761 const Loop *DstLoop)
const;
769 bool gcdMIVtest(
const SCEV *Src,
777 bool banerjeeMIVtest(
const SCEV *Src,
785 CoefficientInfo *collectCoeffInfo(
const SCEV *Subscript,
791 const SCEV *getPositivePart(
const SCEV *X)
const;
795 const SCEV *getNegativePart(
const SCEV *X)
const;
800 const SCEV *getLowerBound(BoundInfo *Bound)
const;
805 const SCEV *getUpperBound(BoundInfo *Bound)
const;
812 unsigned exploreDirections(
unsigned Level,
817 unsigned &DepthExpanded,
818 const SCEV *Delta)
const;
821 bool testBounds(
unsigned char DirKind,
824 const SCEV *Delta)
const;
828 void findBoundsALL(CoefficientInfo *A,
835 void findBoundsLT(CoefficientInfo *A,
842 void findBoundsGT(CoefficientInfo *A,
849 void findBoundsEQ(CoefficientInfo *A,
856 bool intersectConstraints(Constraint *X,
857 const Constraint *Y);
875 bool propagateDistance(
const SCEV *&Src,
877 Constraint &CurConstraint,
883 bool propagatePoint(
const SCEV *&Src,
885 Constraint &CurConstraint);
892 bool propagateLine(
const SCEV *&Src,
894 Constraint &CurConstraint,
902 const SCEV *findCoefficient(
const SCEV *Expr,
903 const Loop *TargetLoop)
const;
910 const SCEV *zeroCoefficient(
const SCEV *Expr,
911 const Loop *TargetLoop)
const;
918 const SCEV *addToCoefficient(
const SCEV *Expr,
919 const Loop *TargetLoop,
925 const Constraint &CurConstraint)
const;
963 void releaseMemory()
override;
969 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
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.
Loop::LoopBounds::Direction Direction
API to communicate dependencies between analyses during invalidation.
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.