Go to the documentation of this file.
39 #ifndef LLVM_ANALYSIS_DEPENDENCEANALYSIS_H
40 #define LLVM_ANALYSIS_DEPENDENCEANALYSIS_H
49 template <
typename T>
class ArrayRef;
52 class ScalarEvolution;
78 : Src(
Source), Dst(Destination) {}
200 const Dependence *NextPredecessor =
nullptr, *NextSuccessor =
nullptr;
260 unsigned short Levels;
261 bool LoopIndependent;
263 std::unique_ptr<DVEntry[]> DV;
273 :
AA(
AA), SE(SE), LI(LI),
F(
F) {}
287 bool PossiblyLoopIndependent);
345 enum ClassificationKind { ZIV, SIV, RDIV, MIV, NonLinear } Classification;
346 SmallBitVector
Loops;
347 SmallBitVector GroupLoops;
348 SmallBitVector Group;
351 struct CoefficientInfo {
355 const SCEV *Iterations;
359 const SCEV *Iterations;
360 const SCEV *
Upper[8];
361 const SCEV *
Lower[8];
363 unsigned char DirSet;
383 enum ConstraintKind {
Empty, Point, Distance, Line,
Any }
Kind;
388 const Loop *AssociatedLoop;
392 bool isEmpty()
const {
return Kind ==
Empty; }
395 bool isPoint()
const {
return Kind == Point; }
398 bool isDistance()
const {
return Kind == Distance; }
403 bool isLine()
const {
return Kind == Line ||
Kind == Distance; }
406 bool isAny()
const {
return Kind ==
Any; }
410 const SCEV *getX()
const;
414 const SCEV *getY()
const;
418 const SCEV *getA()
const;
422 const SCEV *getB()
const;
426 const SCEV *getC()
const;
430 const SCEV *getD()
const;
433 const Loop *getAssociatedLoop()
const;
436 void setPoint(
const SCEV *
X,
const SCEV *
Y,
const Loop *CurrentLoop);
439 void setLine(
const SCEV *A,
const SCEV *
B,
440 const SCEV *
C,
const Loop *CurrentLoop);
443 void setDistance(
const SCEV *
D,
const Loop *CurrentLoop);
449 void setAny(ScalarEvolution *SE);
453 void dump(raw_ostream &OS)
const;
506 void establishNestingLevels(
const Instruction *Src,
507 const Instruction *Dst);
509 unsigned CommonLevels, SrcLevels, MaxLevels;
513 unsigned mapSrcLoop(
const Loop *SrcLoop)
const;
517 unsigned mapDstLoop(
const Loop *DstLoop)
const;
521 bool isLoopInvariant(
const SCEV *Expression,
const Loop *LoopNest)
const;
527 void unifySubscriptType(ArrayRef<Subscript *> Pairs);
533 void removeMatchingExtensions(Subscript *Pair);
537 void collectCommonLoops(
const SCEV *Expression,
538 const Loop *LoopNest,
539 SmallBitVector &
Loops)
const;
543 bool checkSrcSubscript(
const SCEV *Src,
544 const Loop *LoopNest,
545 SmallBitVector &
Loops);
549 bool checkDstSubscript(
const SCEV *Dst,
550 const Loop *LoopNest,
551 SmallBitVector &
Loops);
559 const SCEV *
Y)
const;
565 bool isKnownLessThan(
const SCEV *
S,
const SCEV *Size)
const;
570 bool isKnownNonNegative(
const SCEV *
S,
const Value *Ptr)
const;
577 const SCEV *collectUpperBound(
const Loop *
l, Type *T)
const;
582 const SCEVConstant *collectConstantUpperBound(
const Loop *
l, Type *T)
const;
587 Subscript::ClassificationKind classifyPair(
const SCEV *Src,
588 const Loop *SrcLoopNest,
590 const Loop *DstLoopNest,
591 SmallBitVector &
Loops);
598 bool testZIV(
const SCEV *Src,
600 FullDependence &Result)
const;
612 bool testSIV(
const SCEV *Src,
615 FullDependence &Result,
616 Constraint &NewConstraint,
617 const SCEV *&SplitIter)
const;
628 bool testRDIV(
const SCEV *Src,
630 FullDependence &Result)
const;
635 bool testMIV(
const SCEV *Src,
637 const SmallBitVector &
Loops,
638 FullDependence &Result)
const;
648 bool strongSIVtest(
const SCEV *Coeff,
649 const SCEV *SrcConst,
650 const SCEV *DstConst,
651 const Loop *CurrentLoop,
653 FullDependence &Result,
654 Constraint &NewConstraint)
const;
666 bool weakCrossingSIVtest(
const SCEV *SrcCoeff,
667 const SCEV *SrcConst,
668 const SCEV *DstConst,
669 const Loop *CurrentLoop,
671 FullDependence &Result,
672 Constraint &NewConstraint,
673 const SCEV *&SplitIter)
const;
684 bool exactSIVtest(
const SCEV *SrcCoeff,
685 const SCEV *DstCoeff,
686 const SCEV *SrcConst,
687 const SCEV *DstConst,
688 const Loop *CurrentLoop,
690 FullDependence &Result,
691 Constraint &NewConstraint)
const;
703 bool weakZeroSrcSIVtest(
const SCEV *DstCoeff,
704 const SCEV *SrcConst,
705 const SCEV *DstConst,
706 const Loop *CurrentLoop,
708 FullDependence &Result,
709 Constraint &NewConstraint)
const;
721 bool weakZeroDstSIVtest(
const SCEV *SrcCoeff,
722 const SCEV *SrcConst,
723 const SCEV *DstConst,
724 const Loop *CurrentLoop,
726 FullDependence &Result,
727 Constraint &NewConstraint)
const;
737 bool exactRDIVtest(
const SCEV *SrcCoeff,
738 const SCEV *DstCoeff,
739 const SCEV *SrcConst,
740 const SCEV *DstConst,
743 FullDependence &Result)
const;
754 bool symbolicRDIVtest(
const SCEV *SrcCoeff,
755 const SCEV *DstCoeff,
756 const SCEV *SrcConst,
757 const SCEV *DstConst,
759 const Loop *DstLoop)
const;
767 bool gcdMIVtest(
const SCEV *Src,
769 FullDependence &Result)
const;
775 bool banerjeeMIVtest(
const SCEV *Src,
777 const SmallBitVector &
Loops,
778 FullDependence &Result)
const;
783 CoefficientInfo *collectCoeffInfo(
const SCEV *Subscript,
785 const SCEV *&Constant)
const;
789 const SCEV *getPositivePart(
const SCEV *
X)
const;
793 const SCEV *getNegativePart(
const SCEV *
X)
const;
798 const SCEV *getLowerBound(BoundInfo *Bound)
const;
803 const SCEV *getUpperBound(BoundInfo *Bound)
const;
810 unsigned exploreDirections(
unsigned Level,
814 const SmallBitVector &
Loops,
815 unsigned &DepthExpanded,
816 const SCEV *Delta)
const;
819 bool testBounds(
unsigned char DirKind,
822 const SCEV *Delta)
const;
826 void findBoundsALL(CoefficientInfo *A,
833 void findBoundsLT(CoefficientInfo *A,
840 void findBoundsGT(CoefficientInfo *A,
847 void findBoundsEQ(CoefficientInfo *A,
854 bool intersectConstraints(Constraint *
X,
855 const Constraint *
Y);
862 bool propagate(
const SCEV *&Src,
864 SmallBitVector &
Loops,
865 SmallVectorImpl<Constraint> &Constraints,
873 bool propagateDistance(
const SCEV *&Src,
875 Constraint &CurConstraint,
881 bool propagatePoint(
const SCEV *&Src,
883 Constraint &CurConstraint);
890 bool propagateLine(
const SCEV *&Src,
892 Constraint &CurConstraint,
900 const SCEV *findCoefficient(
const SCEV *Expr,
901 const Loop *TargetLoop)
const;
908 const SCEV *zeroCoefficient(
const SCEV *Expr,
909 const Loop *TargetLoop)
const;
916 const SCEV *addToCoefficient(
const SCEV *Expr,
917 const Loop *TargetLoop,
918 const SCEV *
Value)
const;
922 void updateDirection(Dependence::DVEntry &
Level,
923 const Constraint &CurConstraint)
const;
927 bool tryDelinearize(Instruction *Src, Instruction *Dst,
928 SmallVectorImpl<Subscript> &Pair);
933 bool tryDelinearizeFixedSize(Instruction *Src, Instruction *Dst,
934 const SCEV *SrcAccessFn,
935 const SCEV *DstAccessFn,
936 SmallVectorImpl<const SCEV *> &SrcSubscripts,
937 SmallVectorImpl<const SCEV *> &DstSubscripts);
942 bool tryDelinearizeParametricSize(
943 Instruction *Src, Instruction *Dst,
const SCEV *SrcAccessFn,
944 const SCEV *DstAccessFn, SmallVectorImpl<const SCEV *> &SrcSubscripts,
945 SmallVectorImpl<const SCEV *> &DstSubscripts);
949 bool checkSubscript(
const SCEV *Expr,
const Loop *LoopNest,
950 SmallBitVector &
Loops,
bool IsSrc);
988 std::unique_ptr<DependenceInfo> info;
A set of analyses that are preserved following a run of a transformation pass.
virtual bool isSplitable(unsigned Level) const
isSplitable - Returns true if splitting this loop will break the dependence.
bool isConfused() const override
isConfused - Returns true if this dependence is confused (the compiler understands nothing and makes ...
This is an optimization pass for GlobalISel generic memory operations.
virtual ~Dependence()=default
bool isFlow() const
isFlow - Returns true if this is a flow (aka true) dependence.
bool isConsistent() const override
isConsistent - Returns true if this dependence is consistent (occurs every time the source and destin...
void getAnalysisUsage(AnalysisUsage &) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
A CRTP mix-in to automatically provide informational APIs needed for passes.
Legacy pass manager pass to access dependence information.
virtual unsigned getLevels() const
getLevels - Returns the number of common loops surrounding the source and destination of the dependen...
void dump(raw_ostream &OS) const
dump - For debugging purposes, dumps a dependence to OS.
bool isSplitable(unsigned Level) const override
isSplitable - Returns true if splitting the loop will break the dependence.
Function * getFunction() const
DependenceInfo(Function *F, AAResults *AA, ScalarEvolution *SE, LoopInfo *LI)
The main scalar evolution driver.
Dependence - This class represents a dependence between two memory memory references in a function.
FunctionAnalysisManager FAM
bool isUnordered() const
isUnordered - Returns true if dependence is Input
DependenceInfo & getDI() const
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...
void print(raw_ostream &, const Module *=nullptr) const override
print - Print out the internal state of the pass.
void dump(const SparseBitVector< ElementSize > &LHS, raw_ostream &out)
bool isPeelFirst(unsigned Level) const override
isPeelFirst - Returns true if peeling the first iteration from this loop will break this dependence.
bool isScalar(unsigned Level) const override
isScalar - Returns true if a particular level is scalar; that is, if no subscript in the source or de...
bool isAnti() const
isAnti - Returns true if this is an anti dependence.
Dependence::DVEntry - Each level in the distance/direction vector has a direction (or perhaps a union...
void releaseMemory() override
releaseMemory() - This member can be implemented by a pass if it wants to be able to release its memo...
DependenceAnalysisWrapperPass()
FullDependence(Instruction *Src, Instruction *Dst, bool LoopIndependent, unsigned Levels)
Dependence(Instruction *Source, Instruction *Destination)
(vector float) vec_cmpeq(*A, *B) C
static GCMetadataPrinterRegistry::Add< OcamlGCMetadataPrinter > Y("ocaml", "ocaml 3.10-compatible collector")
FunctionPass * createDependenceAnalysisWrapperPass()
createDependenceAnalysisPass - This creates an instance of the DependenceAnalysis wrapper pass.
Represent the analysis usage information of a pass.
This requires reassociating to forms of expressions that are already something that reassoc doesn t think about yet These two functions should generate the same code on big endian int * l
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
virtual bool isConfused() const
isConfused - Returns true if this dependence is confused (the compiler understands nothing and makes ...
This class implements an extremely fast bulk output stream that can only output to a stream.
virtual const SCEV * getDistance(unsigned Level) const
getDistance - Returns the distance (or NULL) associated with a particular level.
API to communicate dependencies between analyses during invalidation.
bool invalidate(Function &F, const PreservedAnalyses &PA, FunctionAnalysisManager::Invalidator &Inv)
Handle transitive invalidation when the cached analysis results go away.
const SCEV * getSplitIteration(const Dependence &Dep, unsigned Level)
getSplitIteration - Give a dependence that's splittable at some particular level, return the iteratio...
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
bool isOutput() const
isOutput - Returns true if this is an output dependence.
Printer pass to dump DA results.
@ Lower
The operation itself must be expressed in terms of simpler actions on this target.
This class represents an analyzed expression in the program.
DependenceInfo - This class is the main dependence-analysis driver.
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
A special type used by analysis passes to provide an address that identifies that particular analysis...
virtual bool isPeelLast(unsigned Level) const
isPeelLast - Returns true if peeling the last iteration from this loop will break this dependence.
virtual bool isConsistent() const
isConsistent - Returns true if this dependence is consistent (occurs every time the source and destin...
Dependence & operator=(Dependence &&)=default
const SCEV * getDistance(unsigned Level) const override
getDistance - Returns the distance (or NULL) associated with a particular level.
A Module instance is used to store all the information related to an LLVM module.
virtual bool isPeelFirst(unsigned Level) const
isPeelFirst - Returns true if peeling the first iteration from this loop will break this dependence.
A CRTP mix-in that provides informational APIs needed for analysis passes.
Instruction * getDst() const
getDst - Returns the destination instruction for this dependence.
bool isInput() const
isInput - Returns true if this is an input dependence.
bool isPeelLast(unsigned Level) const override
isPeelLast - Returns true if peeling the last iteration from this loop will break this dependence.
AnalysisPass to compute dependence information in a function.
add sub stmia L5 ldr r0 bl L_printf $stub Instead of a and a wouldn t it be better to do three moves *Return an aggregate type is even return S
void setNextPredecessor(const Dependence *pred)
setNextPredecessor - Sets the value of the NextPredecessor field.
Result run(Function &F, FunctionAnalysisManager &FAM)
void setNextSuccessor(const Dependence *succ)
setNextSuccessor - Sets the value of the NextSuccessor field.
Loop::LoopBounds::Direction Direction
Dependence(Dependence &&)=default
std::unique_ptr< Dependence > depends(Instruction *Src, Instruction *Dst, bool PossiblyLoopIndependent)
depends - Tests for a dependence between the Src and Dst instructions.
virtual unsigned getDirection(unsigned Level) const
getDirection - Returns the direction associated with a particular level.
bool isOrdered() const
isOrdered - Returns true if dependence is Output, Flow, or Anti
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.
unsigned getDirection(unsigned Level) const override
getDirection - Returns the direction associated with a particular level.
A container for analyses that lazily runs them and caches their results.
FunctionPass class - This class is used to implement most global optimizations.
unsigned getLevels() const override
getLevels - Returns the number of common loops surrounding the source and destination of the dependen...
virtual bool isLoopIndependent() const
isLoopIndependent - Returns true if this is a loop-independent dependence.
DependenceAnalysisPrinterPass(raw_ostream &OS)
const Dependence * getNextSuccessor() const
getNextSuccessor - Returns the value of the NextSuccessor field.
PreservedAnalyses run(Function &F, FunctionAnalysisManager &FAM)
Instruction * getSrc() const
getSrc - Returns the source instruction for this dependence.
FullDependence - This class represents a dependence between two memory references in a function.
bool runOnFunction(Function &F) override
runOnFunction - Virtual method overriden by subclasses to do the per-function processing of the pass.