70#define DEBUG_TYPE "da"
76STATISTIC(SeparableSubscriptPairs,
"Separable subscript pairs");
77STATISTIC(CoupledSubscriptPairs,
"Coupled subscript pairs");
78STATISTIC(NonlinearSubscriptPairs,
"Nonlinear subscript pairs");
81STATISTIC(StrongSIVapplications,
"Strong SIV applications");
82STATISTIC(StrongSIVsuccesses,
"Strong SIV successes");
83STATISTIC(StrongSIVindependence,
"Strong SIV independence");
84STATISTIC(WeakCrossingSIVapplications,
"Weak-Crossing SIV applications");
85STATISTIC(WeakCrossingSIVsuccesses,
"Weak-Crossing SIV successes");
86STATISTIC(WeakCrossingSIVindependence,
"Weak-Crossing SIV independence");
87STATISTIC(ExactSIVapplications,
"Exact SIV applications");
89STATISTIC(ExactSIVindependence,
"Exact SIV independence");
90STATISTIC(WeakZeroSIVapplications,
"Weak-Zero SIV applications");
91STATISTIC(WeakZeroSIVsuccesses,
"Weak-Zero SIV successes");
92STATISTIC(WeakZeroSIVindependence,
"Weak-Zero SIV independence");
93STATISTIC(ExactRDIVapplications,
"Exact RDIV applications");
94STATISTIC(ExactRDIVindependence,
"Exact RDIV independence");
95STATISTIC(SymbolicRDIVapplications,
"Symbolic RDIV applications");
96STATISTIC(SymbolicRDIVindependence,
"Symbolic RDIV independence");
104STATISTIC(BanerjeeApplications,
"Banerjee applications");
105STATISTIC(BanerjeeIndependence,
"Banerjee independence");
107STATISTIC(SameSDLoopsCount,
"Loops with Same iteration Space and Depth");
111 cl::desc(
"Try to delinearize array references."));
113 "da-disable-delinearization-checks",
cl::Hidden,
115 "Disable checks that try to statically verify validity of "
116 "delinearized subscripts. Enabling this option may result in incorrect "
117 "dependence vectors for languages that allow the subscript of one "
118 "dimension to underflow or overflow into another dimension."));
122 cl::desc(
"Maximum depth allowed for the recursive algorithm used to "
123 "explore MIV direction vectors."));
128enum class DependenceTestType {
143 "da-enable-dependence-test",
cl::init(DependenceTestType::All),
145 cl::desc(
"Run only specified dependence test routine and disable others. "
146 "The purpose is mainly to exclude the influence of other "
147 "dependence test routines in regression tests. If set to All, all "
148 "dependence test routines are enabled."),
150 "Enable all dependence test routines."),
151 clEnumValN(DependenceTestType::StrongSIV,
"strong-siv",
152 "Enable only Strong SIV test."),
153 clEnumValN(DependenceTestType::WeakCrossingSIV,
155 "Enable only Weak-Crossing SIV test."),
156 clEnumValN(DependenceTestType::ExactSIV,
"exact-siv",
157 "Enable only Exact SIV test."),
158 clEnumValN(DependenceTestType::WeakZeroSIV,
"weak-zero-siv",
159 "Enable only Weak-Zero SIV test."),
160 clEnumValN(DependenceTestType::ExactRDIV,
"exact-rdiv",
161 "Enable only Exact RDIV test."),
162 clEnumValN(DependenceTestType::SymbolicRDIV,
"symbolic-rdiv",
163 "Enable only Symbolic RDIV test."),
164 clEnumValN(DependenceTestType::GCDMIV,
"gcd-miv",
165 "Enable only GCD MIV test."),
166 clEnumValN(DependenceTestType::BanerjeeMIV,
"banerjee-miv",
167 "Enable only Banerjee MIV test.")));
173 cl::desc(
"Check if the subscripts are monotonic. If it's not, dependence "
174 "is reported as unknown."));
179 "When printing analysis, dump the results of monotonicity checks."));
195 "Dependence Analysis",
true,
true)
268enum class SCEVMonotonicityType {
280 MultivariateSignedMonotonic,
283struct SCEVMonotonicity {
284 SCEVMonotonicity(SCEVMonotonicityType
Type,
285 const SCEV *FailurePoint =
nullptr);
287 SCEVMonotonicityType
getType()
const {
return Type; }
289 const SCEV *getFailurePoint()
const {
return FailurePoint; }
291 bool isUnknown()
const {
return Type == SCEVMonotonicityType::Unknown; }
293 void print(raw_ostream &OS,
unsigned Depth)
const;
296 SCEVMonotonicityType
Type;
299 const SCEV *FailurePoint;
306struct SCEVMonotonicityChecker
307 :
public SCEVVisitor<SCEVMonotonicityChecker, SCEVMonotonicity> {
309 SCEVMonotonicityChecker(ScalarEvolution *SE) : SE(SE) {}
314 SCEVMonotonicity checkMonotonicity(
const SCEV *Expr,
315 const Loop *OutermostLoop);
321 const Loop *OutermostLoop;
324 SCEVMonotonicity invariantOrUnknown(
const SCEV *Expr);
328 bool isLoopInvariant(
const SCEV *Expr)
const;
331 SCEVMonotonicity createUnknown(
const SCEV *FailurePoint) {
332 return SCEVMonotonicity(SCEVMonotonicityType::Unknown, FailurePoint);
335 SCEVMonotonicity visitAddRecExpr(
const SCEVAddRecExpr *Expr);
337 SCEVMonotonicity visitConstant(
const SCEVConstant *) {
338 return SCEVMonotonicity(SCEVMonotonicityType::Invariant);
340 SCEVMonotonicity visitVScale(
const SCEVVScale *) {
341 return SCEVMonotonicity(SCEVMonotonicityType::Invariant);
345 SCEVMonotonicity visitZeroExtendExpr(
const SCEVZeroExtendExpr *Expr) {
346 return invariantOrUnknown(Expr);
348 SCEVMonotonicity visitSignExtendExpr(
const SCEVSignExtendExpr *Expr) {
349 return invariantOrUnknown(Expr);
351 SCEVMonotonicity visitAddExpr(
const SCEVAddExpr *Expr) {
352 return invariantOrUnknown(Expr);
354 SCEVMonotonicity visitMulExpr(
const SCEVMulExpr *Expr) {
355 return invariantOrUnknown(Expr);
357 SCEVMonotonicity visitPtrToIntExpr(
const SCEVPtrToIntExpr *Expr) {
358 return invariantOrUnknown(Expr);
360 SCEVMonotonicity visitTruncateExpr(
const SCEVTruncateExpr *Expr) {
361 return invariantOrUnknown(Expr);
363 SCEVMonotonicity visitUDivExpr(
const SCEVUDivExpr *Expr) {
364 return invariantOrUnknown(Expr);
366 SCEVMonotonicity visitSMaxExpr(
const SCEVSMaxExpr *Expr) {
367 return invariantOrUnknown(Expr);
369 SCEVMonotonicity visitUMaxExpr(
const SCEVUMaxExpr *Expr) {
370 return invariantOrUnknown(Expr);
372 SCEVMonotonicity visitSMinExpr(
const SCEVSMinExpr *Expr) {
373 return invariantOrUnknown(Expr);
375 SCEVMonotonicity visitUMinExpr(
const SCEVUMinExpr *Expr) {
376 return invariantOrUnknown(Expr);
378 SCEVMonotonicity visitSequentialUMinExpr(
const SCEVSequentialUMinExpr *Expr) {
379 return invariantOrUnknown(Expr);
381 SCEVMonotonicity visitUnknown(
const SCEVUnknown *Expr) {
382 return invariantOrUnknown(Expr);
384 SCEVMonotonicity visitCouldNotCompute(
const SCEVCouldNotCompute *Expr) {
385 return invariantOrUnknown(Expr);
388 friend struct SCEVVisitor<SCEVMonotonicityChecker, SCEVMonotonicity>;
399 bool NormalizeResults) {
400 auto *
F = DA->getFunction();
403 SCEVMonotonicityChecker Checker(&SE);
404 OS <<
"Monotonicity check:\n";
412 SCEVMonotonicity Mon = Checker.checkMonotonicity(AccessFn, L);
413 OS.
indent(2) <<
"Inst: " << Inst <<
"\n";
414 OS.
indent(4) <<
"Expr: " << *AccessFn <<
"\n";
422 if (SrcI->mayReadOrWriteMemory()) {
425 if (DstI->mayReadOrWriteMemory()) {
426 OS <<
"Src:" << *SrcI <<
" --> Dst:" << *DstI <<
"\n";
427 OS <<
" da analyze - ";
428 if (
auto D = DA->depends(&*SrcI, &*DstI,
434 for (
unsigned Level = 1; Level <=
D->getLevels(); Level++) {
435 const SCEV *Distance =
D->getDistance(Level);
436 bool IsDistanceZero = Distance && Distance->
isZero();
439 assert(IsDistanceZero == IsDirectionEQ &&
440 "Inconsistent distance and direction.");
445 if (NormalizeResults &&
D->normalize(&SE))
446 OS <<
"normalized - ";
448 for (
unsigned Level = 1; Level <=
D->getLevels(); Level++) {
449 if (
D->isSplitable(Level)) {
450 OS <<
" da analyze - split level = " << Level;
451 OS <<
", iteration = " << *DA->getSplitIteration(*
D, Level);
463 OS <<
"Runtime Assumptions:\n";
464 Assumptions.
print(OS, 0);
477 OS <<
"Printing analysis 'Dependence Analysis' for function '" <<
F.getName()
490 return Src->mayReadFromMemory() &&
Dst->mayReadFromMemory();
495 return Src->mayWriteToMemory() &&
Dst->mayWriteToMemory();
500 return Src->mayWriteToMemory() &&
Dst->mayReadFromMemory();
505 return Src->mayReadFromMemory() &&
Dst->mayWriteToMemory();
519 bool PossiblyLoopIndependent,
520 unsigned CommonLevels)
521 :
Dependence(Source, Destination, Assumes), Levels(CommonLevels),
522 LoopIndependent(PossiblyLoopIndependent) {
526 DV = std::make_unique<
DVEntry[]>(CommonLevels);
545 for (
unsigned Level = 1; Level <= Levels; ++Level) {
546 unsigned char Direction = DV[Level - 1].Direction;
561 LLVM_DEBUG(
dbgs() <<
"Before normalizing negative direction vectors:\n";
564 for (
unsigned Level = 1; Level <= Levels; ++Level) {
565 unsigned char Direction = DV[Level - 1].Direction;
573 DV[Level - 1].Direction = RevDirection;
575 if (DV[Level - 1].Distance !=
nullptr)
579 LLVM_DEBUG(
dbgs() <<
"After normalizing negative direction vectors:\n";
626 assert(0 < Level && Level <=
static_cast<unsigned>(Levels) + SameSDLevels &&
627 "Level out of range");
628 return Level > Levels;
636const SCEV *DependenceInfo::Constraint::getX()
const {
637 assert(Kind == Point &&
"Kind should be Point");
643const SCEV *DependenceInfo::Constraint::getY()
const {
644 assert(Kind == Point &&
"Kind should be Point");
650const SCEV *DependenceInfo::Constraint::getA()
const {
651 assert((Kind == Line || Kind == Distance) &&
652 "Kind should be Line (or Distance)");
658const SCEV *DependenceInfo::Constraint::getB()
const {
659 assert((Kind == Line || Kind == Distance) &&
660 "Kind should be Line (or Distance)");
666const SCEV *DependenceInfo::Constraint::getC()
const {
667 assert((Kind == Line || Kind == Distance) &&
668 "Kind should be Line (or Distance)");
674const SCEV *DependenceInfo::Constraint::getD()
const {
675 assert(Kind == Distance &&
"Kind should be Distance");
676 return SE->getNegativeSCEV(
C);
680const Loop *DependenceInfo::Constraint::getAssociatedSrcLoop()
const {
681 assert((Kind == Distance || Kind == Line || Kind == Point) &&
682 "Kind should be Distance, Line, or Point");
683 return AssociatedSrcLoop;
687const Loop *DependenceInfo::Constraint::getAssociatedDstLoop()
const {
688 assert((Kind == Distance || Kind == Line || Kind == Point) &&
689 "Kind should be Distance, Line, or Point");
690 return AssociatedDstLoop;
693void DependenceInfo::Constraint::setPoint(
const SCEV *
X,
const SCEV *
Y,
694 const Loop *CurSrcLoop,
695 const Loop *CurDstLoop) {
699 AssociatedSrcLoop = CurSrcLoop;
700 AssociatedDstLoop = CurDstLoop;
703void DependenceInfo::Constraint::setLine(
const SCEV *AA,
const SCEV *BB,
704 const SCEV *CC,
const Loop *CurSrcLoop,
705 const Loop *CurDstLoop) {
710 AssociatedSrcLoop = CurSrcLoop;
711 AssociatedDstLoop = CurDstLoop;
714void DependenceInfo::Constraint::setDistance(
const SCEV *
D,
715 const Loop *CurSrcLoop,
716 const Loop *CurDstLoop) {
718 A = SE->getOne(
D->getType());
719 B = SE->getNegativeSCEV(
A);
720 C = SE->getNegativeSCEV(
D);
721 AssociatedSrcLoop = CurSrcLoop;
722 AssociatedDstLoop = CurDstLoop;
725void DependenceInfo::Constraint::setEmpty() {
Kind =
Empty; }
727void DependenceInfo::Constraint::setAny(ScalarEvolution *NewSE) {
732#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
734LLVM_DUMP_METHOD void DependenceInfo::Constraint::dump(raw_ostream &OS)
const {
740 OS <<
" Point is <" << *getX() <<
", " << *getY() <<
">\n";
741 else if (isDistance())
742 OS <<
" Distance is " << *getD() <<
" (" << *getA() <<
"*X + " << *getB()
743 <<
"*Y = " << *getC() <<
")\n";
745 OS <<
" Line is " << *getA() <<
"*X + " << *getB() <<
"*Y = " << *getC()
759bool DependenceInfo::intersectConstraints(Constraint *
X,
const Constraint *
Y) {
764 assert(!
Y->isPoint() &&
"Y must not be a Point");
778 if (
X->isDistance() &&
Y->isDistance()) {
802 assert(!(
X->isPoint() &&
Y->isPoint()) &&
803 "We shouldn't ever see X->isPoint() && Y->isPoint()");
805 if (
X->isLine() &&
Y->isLine()) {
807 const SCEV *Prod1 = SE->getMulExpr(
X->getA(),
Y->getB());
808 const SCEV *Prod2 = SE->getMulExpr(
X->getB(),
Y->getA());
812 Prod1 = SE->getMulExpr(
X->getC(),
Y->getB());
813 Prod2 = SE->getMulExpr(
X->getB(),
Y->getC());
826 const SCEV *C1B2 = SE->getMulExpr(
X->getC(),
Y->getB());
827 const SCEV *C1A2 = SE->getMulExpr(
X->getC(),
Y->getA());
828 const SCEV *C2B1 = SE->getMulExpr(
Y->getC(),
X->getB());
829 const SCEV *C2A1 = SE->getMulExpr(
Y->getC(),
X->getA());
830 const SCEV *A1B2 = SE->getMulExpr(
X->getA(),
Y->getB());
831 const SCEV *A2B1 = SE->getMulExpr(
Y->getA(),
X->getB());
832 const SCEVConstant *C1A2_C2A1 =
834 const SCEVConstant *C1B2_C2B1 =
836 const SCEVConstant *A1B2_A2B1 =
838 const SCEVConstant *A2B1_A1B2 =
840 if (!C1B2_C2B1 || !C1A2_C2A1 || !A1B2_A2B1 || !A2B1_A1B2)
856 if (Xr != 0 || Yr != 0) {
862 if (Xq.
slt(0) || Yq.
slt(0)) {
867 if (
const SCEVConstant *CUB = collectConstantUpperBound(
868 X->getAssociatedSrcLoop(), Prod1->
getType())) {
869 const APInt &UpperBound = CUB->getAPInt();
871 if (Xq.
sgt(UpperBound) || Yq.
sgt(UpperBound)) {
877 X->setPoint(SE->getConstant(Xq), SE->getConstant(Yq),
878 X->getAssociatedSrcLoop(),
X->getAssociatedDstLoop());
886 assert(!(
X->isLine() &&
Y->isPoint()) &&
"This case should never occur");
888 if (
X->isPoint() &&
Y->isLine()) {
890 const SCEV *A1X1 = SE->getMulExpr(
Y->getA(),
X->getX());
891 const SCEV *B1Y1 = SE->getMulExpr(
Y->getB(),
X->getY());
892 const SCEV *Sum = SE->getAddExpr(A1X1, B1Y1);
910SCEVMonotonicity::SCEVMonotonicity(SCEVMonotonicityType
Type,
911 const SCEV *FailurePoint)
912 :
Type(
Type), FailurePoint(FailurePoint) {
914 ((
Type == SCEVMonotonicityType::Unknown) == (FailurePoint !=
nullptr)) &&
915 "FailurePoint must be provided iff Type is Unknown");
921 case SCEVMonotonicityType::Unknown:
922 assert(FailurePoint &&
"FailurePoint must be provided for Unknown");
924 OS.
indent(
Depth) <<
"Reason: " << *FailurePoint <<
"\n";
926 case SCEVMonotonicityType::Invariant:
929 case SCEVMonotonicityType::MultivariateSignedMonotonic:
930 OS <<
"MultivariateSignedMonotonic\n";
935bool SCEVMonotonicityChecker::isLoopInvariant(
const SCEV *Expr)
const {
936 return !OutermostLoop || SE->isLoopInvariant(Expr, OutermostLoop);
939SCEVMonotonicity SCEVMonotonicityChecker::invariantOrUnknown(
const SCEV *Expr) {
940 if (isLoopInvariant(Expr))
941 return SCEVMonotonicity(SCEVMonotonicityType::Invariant);
942 return createUnknown(Expr);
946SCEVMonotonicityChecker::checkMonotonicity(
const SCEV *Expr,
947 const Loop *OutermostLoop) {
949 this->OutermostLoop = OutermostLoop;
965SCEVMonotonicityChecker::visitAddRecExpr(
const SCEVAddRecExpr *Expr) {
967 return createUnknown(Expr);
972 SCEVMonotonicity StartMon =
visit(Start);
973 if (StartMon.isUnknown())
976 if (!isLoopInvariant(Step))
977 return createUnknown(Expr);
979 return SCEVMonotonicity(SCEVMonotonicityType::MultivariateSignedMonotonic);
1002 if (SameSDLevels > 0) {
1003 OS <<
" / assuming " << SameSDLevels <<
" loop level(s) fused: ";
1010 if (!Assumptions.isAlwaysTrue()) {
1011 OS <<
" Runtime Assumptions:\n";
1012 Assumptions.print(OS, 2);
1019 bool Splitable =
false;
1022 bool OnSameSD =
false;
1023 unsigned LevelNum = Levels;
1025 LevelNum += SameSDLevels;
1027 for (
unsigned II = 1;
II <= LevelNum; ++
II) {
1106 return LI->isUnordered();
1108 return SI->isUnordered();
1116bool DependenceInfo::haveSameSD(
const Loop *SrcLoop,
1117 const Loop *DstLoop)
const {
1118 if (SrcLoop == DstLoop)
1124 if (!SrcLoop || !SrcLoop->
getLoopLatch() || !DstLoop ||
1128 const SCEV *SrcUB =
nullptr, *DstUP =
nullptr;
1129 if (SE->hasLoopInvariantBackedgeTakenCount(SrcLoop))
1130 SrcUB = SE->getBackedgeTakenCount(SrcLoop);
1131 if (SE->hasLoopInvariantBackedgeTakenCount(DstLoop))
1132 DstUP = SE->getBackedgeTakenCount(DstLoop);
1134 if (SrcUB !=
nullptr && DstUP !=
nullptr &&
1203void DependenceInfo::establishNestingLevels(
const Instruction *Src,
1205 const BasicBlock *SrcBlock = Src->getParent();
1206 const BasicBlock *DstBlock = Dst->getParent();
1207 unsigned SrcLevel = LI->getLoopDepth(SrcBlock);
1208 unsigned DstLevel = LI->getLoopDepth(DstBlock);
1209 const Loop *SrcLoop = LI->getLoopFor(SrcBlock);
1210 const Loop *DstLoop = LI->getLoopFor(DstBlock);
1211 SrcLevels = SrcLevel;
1212 MaxLevels = SrcLevel + DstLevel;
1214 while (SrcLevel > DstLevel) {
1218 while (DstLevel > SrcLevel) {
1224 while (SrcLoop != DstLoop) {
1226 if (!haveSameSD(SrcLoop, DstLoop))
1232 CommonLevels = SrcLevel;
1233 MaxLevels -= CommonLevels;
1238unsigned DependenceInfo::mapSrcLoop(
const Loop *SrcLoop)
const {
1244unsigned DependenceInfo::mapDstLoop(
const Loop *DstLoop)
const {
1246 if (
D > CommonLevels)
1249 return D - CommonLevels + SrcLevels;
1276 if (Level <= CommonLevels && !SE->isLoopInvariant(Expression, LoopNest))
1284 unsigned widestWidthSeen = 0;
1289 for (Subscript *Pair : Pairs) {
1290 const SCEV *Src = Pair->Src;
1291 const SCEV *Dst = Pair->Dst;
1294 if (SrcTy ==
nullptr || DstTy ==
nullptr) {
1296 "This function only unify integer types and "
1297 "expect Src and Dst share the same type otherwise.");
1310 assert(widestWidthSeen > 0);
1313 for (Subscript *Pair : Pairs) {
1314 const SCEV *Src = Pair->Src;
1315 const SCEV *Dst = Pair->Dst;
1318 if (SrcTy ==
nullptr || DstTy ==
nullptr) {
1320 "This function only unify integer types and "
1321 "expect Src and Dst share the same type otherwise.");
1326 Pair->Src = SE->getSignExtendExpr(Src, widestType);
1329 Pair->Dst = SE->getSignExtendExpr(Dst, widestType);
1338void DependenceInfo::removeMatchingExtensions(Subscript *Pair) {
1339 const SCEV *Src = Pair->Src;
1340 const SCEV *Dst = Pair->Dst;
1345 const SCEV *SrcCastOp = SrcCast->
getOperand();
1346 const SCEV *DstCastOp = DstCast->
getOperand();
1348 Pair->Src = SrcCastOp;
1349 Pair->Dst = DstCastOp;
1360 return isLoopInvariant(Expr, LoopNest);
1367 const Loop *
L = LoopNest;
1368 while (L && AddRec->
getLoop() != L)
1369 L =
L->getParentLoop();
1375 if (!isLoopInvariant(Step, LoopNest))
1381 return checkSubscript(Start, LoopNest,
Loops, IsSrc);
1386bool DependenceInfo::checkSrcSubscript(
const SCEV *Src,
const Loop *
LoopNest,
1388 return checkSubscript(Src, LoopNest,
Loops,
true);
1393bool DependenceInfo::checkDstSubscript(
const SCEV *Dst,
const Loop *
LoopNest,
1395 return checkSubscript(Dst, LoopNest,
Loops,
false);
1401DependenceInfo::Subscript::ClassificationKind
1402DependenceInfo::classifyPair(
const SCEV *Src,
const Loop *SrcLoopNest,
1403 const SCEV *Dst,
const Loop *DstLoopNest,
1405 SmallBitVector SrcLoops(MaxLevels + 1);
1406 SmallBitVector DstLoops(MaxLevels + 1);
1407 if (!checkSrcSubscript(Src, SrcLoopNest, SrcLoops))
1408 return Subscript::NonLinear;
1409 if (!checkDstSubscript(Dst, DstLoopNest, DstLoops))
1410 return Subscript::NonLinear;
1413 unsigned N =
Loops.count();
1415 return Subscript::ZIV;
1417 return Subscript::SIV;
1418 if (
N == 2 && (SrcLoops.count() == 0 || DstLoops.count() == 0 ||
1419 (SrcLoops.count() == 1 && DstLoops.count() == 1)))
1420 return Subscript::RDIV;
1421 return Subscript::MIV;
1435 const SCEV *
Y)
const {
1449 if (SE->isKnownPredicate(Pred,
X,
Y))
1456 const SCEV *Delta = SE->getMinusSCEV(
X,
Y);
1461 return SE->isKnownNonZero(Delta);
1463 return SE->isKnownNonNegative(Delta);
1465 return SE->isKnownNonPositive(Delta);
1467 return SE->isKnownPositive(Delta);
1469 return SE->isKnownNegative(Delta);
1481bool DependenceInfo::isKnownLessThan(
const SCEV *S,
const SCEV *
Size)
const {
1485 if (!SType || !SizeType)
1488 (SType->getBitWidth() >= SizeType->getBitWidth()) ? SType : SizeType;
1489 S = SE->getTruncateOrZeroExtend(S, MaxType);
1490 Size = SE->getTruncateOrZeroExtend(
Size, MaxType);
1492 auto CheckAddRecBECount = [&]() {
1496 const SCEV *BECount = collectUpperBound(AddRec->
getLoop(), MaxType);
1503 const SCEV *Diff0 = SE->getMinusSCEV(Start,
Size);
1504 const SCEV *Diff1 = SE->getMinusSCEV(End,
Size);
1509 if (SE->isKnownNonNegative(Step) && SE->isKnownNegative(Diff1))
1514 if (SE->isKnownNonPositive(Step) && SE->isKnownNegative(Diff0))
1519 if (SE->isKnownNegative(Diff0) && SE->isKnownNegative(Diff1))
1525 if (CheckAddRecBECount())
1529 const SCEV *LimitedBound = SE->getMinusSCEV(S,
Size);
1530 return SE->isKnownNegative(LimitedBound);
1533bool DependenceInfo::isKnownNonNegative(
const SCEV *S,
const Value *
Ptr)
const {
1534 bool Inbounds =
false;
1536 Inbounds = SrcGEP->isInBounds();
1542 if (SE->isKnownNonNegative(AddRec->
getStart()) &&
1543 SE->isKnownNonNegative(AddRec->
getOperand(1)))
1549 return SE->isKnownNonNegative(S);
1559const SCEV *DependenceInfo::collectUpperBound(
const Loop *L,
Type *
T)
const {
1560 if (SE->hasLoopInvariantBackedgeTakenCount(L)) {
1561 const SCEV *UB = SE->getBackedgeTakenCount(L);
1562 return SE->getTruncateOrZeroExtend(UB,
T);
1569const SCEVConstant *DependenceInfo::collectConstantUpperBound(
const Loop *L,
1571 if (
const SCEV *UB = collectUpperBound(L,
T))
1602bool DependenceInfo::testZIV(
const SCEV *Src,
const SCEV *Dst,
1617 Result.Consistent =
false;
1648bool DependenceInfo::strongSIVtest(
const SCEV *Coeff,
const SCEV *SrcConst,
1649 const SCEV *DstConst,
const Loop *CurSrcLoop,
1650 const Loop *CurDstLoop,
unsigned Level,
1652 Constraint &NewConstraint)
const {
1663 ++StrongSIVapplications;
1664 assert(0 < Level && Level <= CommonLevels &&
"level out of range");
1667 const SCEV *Delta = SE->getMinusSCEV(SrcConst, DstConst);
1672 if (
const SCEV *UpperBound =
1673 collectUpperBound(CurSrcLoop, Delta->
getType())) {
1676 const SCEV *AbsDelta =
1677 SE->isKnownNonNegative(Delta) ? Delta : SE->getNegativeSCEV(Delta);
1678 const SCEV *AbsCoeff =
1679 SE->isKnownNonNegative(Coeff) ? Coeff : SE->getNegativeSCEV(Coeff);
1680 const SCEV *Product = SE->getMulExpr(UpperBound, AbsCoeff);
1683 ++StrongSIVindependence;
1684 ++StrongSIVsuccesses;
1693 APInt Distance = ConstDelta;
1694 APInt Remainder = ConstDelta;
1699 if (Remainder != 0) {
1701 ++StrongSIVindependence;
1702 ++StrongSIVsuccesses;
1705 Result.DV[
Level].Distance = SE->getConstant(Distance);
1706 NewConstraint.setDistance(SE->getConstant(Distance), CurSrcLoop,
1708 if (Distance.
sgt(0))
1710 else if (Distance.
slt(0))
1714 ++StrongSIVsuccesses;
1715 }
else if (Delta->
isZero()) {
1718 NewConstraint.setDistance(Delta, CurSrcLoop, CurDstLoop);
1720 ++StrongSIVsuccesses;
1722 if (Coeff->
isOne()) {
1725 NewConstraint.setDistance(Delta, CurSrcLoop, CurDstLoop);
1727 Result.Consistent =
false;
1728 NewConstraint.setLine(Coeff, SE->getNegativeSCEV(Coeff),
1729 SE->getNegativeSCEV(Delta), CurSrcLoop, CurDstLoop);
1733 bool DeltaMaybeZero = !SE->isKnownNonZero(Delta);
1734 bool DeltaMaybePositive = !SE->isKnownNonPositive(Delta);
1735 bool DeltaMaybeNegative = !SE->isKnownNonNegative(Delta);
1736 bool CoeffMaybePositive = !SE->isKnownNonPositive(Coeff);
1737 bool CoeffMaybeNegative = !SE->isKnownNonNegative(Coeff);
1742 if ((DeltaMaybePositive && CoeffMaybePositive) ||
1743 (DeltaMaybeNegative && CoeffMaybeNegative))
1747 if ((DeltaMaybeNegative && CoeffMaybePositive) ||
1748 (DeltaMaybePositive && CoeffMaybeNegative))
1750 if (NewDirection <
Result.DV[Level].Direction)
1751 ++StrongSIVsuccesses;
1785bool DependenceInfo::weakCrossingSIVtest(
1786 const SCEV *Coeff,
const SCEV *SrcConst,
const SCEV *DstConst,
1787 const Loop *CurSrcLoop,
const Loop *CurDstLoop,
unsigned Level,
1789 const SCEV *&SplitIter)
const {
1797 ++WeakCrossingSIVapplications;
1798 assert(0 < Level && Level <= CommonLevels &&
"Level out of range");
1800 Result.Consistent =
false;
1801 const SCEV *Delta = SE->getMinusSCEV(DstConst, SrcConst);
1803 NewConstraint.setLine(Coeff, Coeff, Delta, CurSrcLoop, CurDstLoop);
1805 Result.DV[
Level].Direction &= ~Dependence::DVEntry::LT;
1806 Result.DV[
Level].Direction &= ~Dependence::DVEntry::GT;
1807 ++WeakCrossingSIVsuccesses;
1808 if (!
Result.DV[Level].Direction) {
1809 ++WeakCrossingSIVindependence;
1820 if (SE->isKnownNegative(ConstCoeff)) {
1823 "dynamic cast of negative of ConstCoeff should yield constant");
1824 Delta = SE->getNegativeSCEV(Delta);
1826 assert(SE->isKnownPositive(ConstCoeff) &&
"ConstCoeff should be positive");
1829 SplitIter = SE->getUDivExpr(
1830 SE->getSMaxExpr(SE->getZero(Delta->
getType()), Delta),
1831 SE->getMulExpr(SE->getConstant(Delta->
getType(), 2), ConstCoeff));
1842 if (SE->isKnownNegative(Delta)) {
1844 ++WeakCrossingSIVindependence;
1845 ++WeakCrossingSIVsuccesses;
1851 if (
const SCEV *UpperBound =
1852 collectUpperBound(CurSrcLoop, Delta->
getType())) {
1854 const SCEV *ConstantTwo = SE->getConstant(UpperBound->getType(), 2);
1856 SE->getMulExpr(SE->getMulExpr(ConstCoeff, UpperBound), ConstantTwo);
1860 ++WeakCrossingSIVindependence;
1861 ++WeakCrossingSIVsuccesses;
1866 Result.DV[
Level].Direction &= ~Dependence::DVEntry::LT;
1867 Result.DV[
Level].Direction &= ~Dependence::DVEntry::GT;
1868 ++WeakCrossingSIVsuccesses;
1869 if (!
Result.DV[Level].Direction) {
1870 ++WeakCrossingSIVindependence;
1880 APInt APDelta = ConstDelta->
getAPInt();
1881 APInt APCoeff = ConstCoeff->
getAPInt();
1882 APInt Distance = APDelta;
1883 APInt Remainder = APDelta;
1886 if (Remainder != 0) {
1888 ++WeakCrossingSIVindependence;
1889 ++WeakCrossingSIVsuccesses;
1895 APInt Two = APInt(Distance.
getBitWidth(), 2,
true);
1896 Remainder = Distance.
srem(Two);
1898 if (Remainder != 0) {
1900 Result.DV[
Level].Direction &= ~Dependence::DVEntry::EQ;
1901 ++WeakCrossingSIVsuccesses;
1918 APInt A0(Bits, 1,
true), A1(Bits, 0,
true);
1919 APInt B0(Bits, 0,
true), B1(Bits, 1,
true);
1927 APInt A2 = A0 - Q*A1; A0 = A1; A1 = A2;
1928 APInt B2 = B0 - Q*B1; B0 = B1; B1 = B2;
1935 X = AM.
slt(0) ? -A1 : A1;
1936 Y = BM.
slt(0) ? B1 : -B1;
1952 if ((
A.sgt(0) &&
B.sgt(0)) || (
A.slt(0) &&
B.slt(0)))
1964 if ((
A.sgt(0) &&
B.sgt(0)) || (
A.slt(0) &&
B.slt(0)))
1999static std::pair<std::optional<APInt>, std::optional<APInt>>
2001 const std::optional<APInt> &UB) {
2002 assert(
A != 0 &&
"A must be non-zero");
2003 std::optional<APInt> TL, TU;
2023 return std::make_pair(TL, TU);
2045bool DependenceInfo::exactSIVtest(
const SCEV *SrcCoeff,
const SCEV *DstCoeff,
2046 const SCEV *SrcConst,
const SCEV *DstConst,
2047 const Loop *CurSrcLoop,
2048 const Loop *CurDstLoop,
unsigned Level,
2050 Constraint &NewConstraint)
const {
2055 LLVM_DEBUG(
dbgs() <<
"\t SrcCoeff = " << *SrcCoeff <<
" = AM\n");
2056 LLVM_DEBUG(
dbgs() <<
"\t DstCoeff = " << *DstCoeff <<
" = BM\n");
2059 ++ExactSIVapplications;
2060 assert(0 < Level && Level <= CommonLevels &&
"Level out of range");
2062 Result.Consistent =
false;
2067 NewConstraint.setLine(SrcCoeff, SE->getNegativeSCEV(DstCoeff), Delta,
2068 CurSrcLoop, CurDstLoop);
2072 if (!ConstDelta || !ConstSrcCoeff || !ConstDstCoeff)
2077 APInt AM = ConstSrcCoeff->
getAPInt();
2078 APInt BM = ConstDstCoeff->
getAPInt();
2083 ++ExactSIVindependence;
2084 ++ExactSIVsuccesses;
2091 std::optional<APInt> UM;
2093 if (
const SCEVConstant *CUB =
2094 collectConstantUpperBound(CurSrcLoop, Delta->
getType())) {
2095 UM = CUB->getAPInt();
2101 APInt TC = CM.
sdiv(
G);
2123 auto CreateVec = [](
const std::optional<APInt> &V0,
2124 const std::optional<APInt> &V1) {
2147 ++ExactSIVindependence;
2148 ++ExactSIVsuccesses;
2154 APInt LowerDistance, UpperDistance;
2157 LowerDistance = (TY - TX) + (TA - TB) * TL;
2158 UpperDistance = (TY - TX) + (TA - TB) * TU;
2160 LowerDistance = (TY - TX) + (TA - TB) * TU;
2161 UpperDistance = (TY - TX) + (TA - TB) * TL;
2164 LLVM_DEBUG(
dbgs() <<
"\t LowerDistance = " << LowerDistance <<
"\n");
2165 LLVM_DEBUG(
dbgs() <<
"\t UpperDistance = " << UpperDistance <<
"\n");
2167 APInt
Zero(Bits, 0,
true);
2168 if (LowerDistance.
sle(Zero) && UpperDistance.
sge(Zero)) {
2170 ++ExactSIVsuccesses;
2172 if (LowerDistance.
slt(0)) {
2174 ++ExactSIVsuccesses;
2176 if (UpperDistance.
sgt(0)) {
2178 ++ExactSIVsuccesses;
2184 ++ExactSIVindependence;
2195 return ConstDividend.
srem(ConstDivisor) == 0;
2229bool DependenceInfo::weakZeroSrcSIVtest(
2230 const SCEV *DstCoeff,
const SCEV *SrcConst,
const SCEV *DstConst,
2231 const Loop *CurSrcLoop,
const Loop *CurDstLoop,
unsigned Level,
2243 ++WeakZeroSIVapplications;
2244 assert(0 < Level && Level <= MaxLevels &&
"Level out of range");
2246 Result.Consistent =
false;
2247 const SCEV *Delta = SE->getMinusSCEV(SrcConst, DstConst);
2248 NewConstraint.setLine(SE->getZero(Delta->
getType()), DstCoeff, Delta,
2249 CurSrcLoop, CurDstLoop);
2252 if (Level < CommonLevels) {
2255 ++WeakZeroSIVsuccesses;
2262 const SCEV *AbsCoeff = SE->isKnownNegative(ConstCoeff)
2263 ? SE->getNegativeSCEV(ConstCoeff)
2265 const SCEV *NewDelta =
2266 SE->isKnownNegative(ConstCoeff) ? SE->getNegativeSCEV(Delta) : Delta;
2270 if (
const SCEV *UpperBound =
2271 collectUpperBound(CurSrcLoop, Delta->
getType())) {
2273 const SCEV *Product = SE->getMulExpr(AbsCoeff, UpperBound);
2275 ++WeakZeroSIVindependence;
2276 ++WeakZeroSIVsuccesses;
2281 if (Level < CommonLevels) {
2284 ++WeakZeroSIVsuccesses;
2292 if (SE->isKnownNegative(NewDelta)) {
2294 ++WeakZeroSIVindependence;
2295 ++WeakZeroSIVsuccesses;
2302 ++WeakZeroSIVindependence;
2303 ++WeakZeroSIVsuccesses;
2340bool DependenceInfo::weakZeroDstSIVtest(
2341 const SCEV *SrcCoeff,
const SCEV *SrcConst,
const SCEV *DstConst,
2342 const Loop *CurSrcLoop,
const Loop *CurDstLoop,
unsigned Level,
2353 ++WeakZeroSIVapplications;
2354 assert(0 < Level && Level <= SrcLevels &&
"Level out of range");
2356 Result.Consistent =
false;
2357 const SCEV *Delta = SE->getMinusSCEV(DstConst, SrcConst);
2358 NewConstraint.setLine(SrcCoeff, SE->getZero(Delta->
getType()), Delta,
2359 CurSrcLoop, CurDstLoop);
2362 if (Level < CommonLevels) {
2365 ++WeakZeroSIVsuccesses;
2372 const SCEV *AbsCoeff = SE->isKnownNegative(ConstCoeff)
2373 ? SE->getNegativeSCEV(ConstCoeff)
2375 const SCEV *NewDelta =
2376 SE->isKnownNegative(ConstCoeff) ? SE->getNegativeSCEV(Delta) : Delta;
2380 if (
const SCEV *UpperBound =
2381 collectUpperBound(CurSrcLoop, Delta->
getType())) {
2383 const SCEV *Product = SE->getMulExpr(AbsCoeff, UpperBound);
2385 ++WeakZeroSIVindependence;
2386 ++WeakZeroSIVsuccesses;
2391 if (Level < CommonLevels) {
2394 ++WeakZeroSIVsuccesses;
2402 if (SE->isKnownNegative(NewDelta)) {
2404 ++WeakZeroSIVindependence;
2405 ++WeakZeroSIVsuccesses;
2412 ++WeakZeroSIVindependence;
2413 ++WeakZeroSIVsuccesses;
2426bool DependenceInfo::exactRDIVtest(
const SCEV *SrcCoeff,
const SCEV *DstCoeff,
2427 const SCEV *SrcConst,
const SCEV *DstConst,
2428 const Loop *SrcLoop,
const Loop *DstLoop,
2434 LLVM_DEBUG(
dbgs() <<
"\t SrcCoeff = " << *SrcCoeff <<
" = AM\n");
2435 LLVM_DEBUG(
dbgs() <<
"\t DstCoeff = " << *DstCoeff <<
" = BM\n");
2438 ++ExactRDIVapplications;
2439 Result.Consistent =
false;
2440 const SCEV *Delta = SE->getMinusSCEV(DstConst, SrcConst);
2445 if (!ConstDelta || !ConstSrcCoeff || !ConstDstCoeff)
2450 APInt AM = ConstSrcCoeff->
getAPInt();
2451 APInt BM = ConstDstCoeff->
getAPInt();
2456 ++ExactRDIVindependence;
2463 std::optional<APInt> SrcUM;
2465 if (
const SCEVConstant *UpperBound =
2466 collectConstantUpperBound(SrcLoop, Delta->
getType())) {
2467 SrcUM = UpperBound->getAPInt();
2471 std::optional<APInt> DstUM;
2473 if (
const SCEVConstant *UpperBound =
2474 collectConstantUpperBound(DstLoop, Delta->
getType())) {
2475 DstUM = UpperBound->getAPInt();
2481 APInt TC = CM.
sdiv(
G);
2506 auto CreateVec = [](
const std::optional<APInt> &V0,
2507 const std::optional<APInt> &V1) {
2527 ++ExactRDIVindependence;
2573bool DependenceInfo::symbolicRDIVtest(
const SCEV *A1,
const SCEV *A2,
2576 const Loop *Loop2)
const {
2580 ++SymbolicRDIVapplications;
2587 const SCEV *N1 = collectUpperBound(Loop1, A1->
getType());
2588 const SCEV *N2 = collectUpperBound(Loop2, A1->
getType());
2591 const SCEV *C2_C1 = SE->getMinusSCEV(C2, C1);
2592 const SCEV *C1_C2 = SE->getMinusSCEV(C1, C2);
2595 if (SE->isKnownNonNegative(A1)) {
2596 if (SE->isKnownNonNegative(A2)) {
2600 const SCEV *A1N1 = SE->getMulExpr(A1, N1);
2603 ++SymbolicRDIVindependence;
2609 const SCEV *A2N2 = SE->getMulExpr(A2, N2);
2612 ++SymbolicRDIVindependence;
2616 }
else if (SE->isKnownNonPositive(A2)) {
2620 const SCEV *A1N1 = SE->getMulExpr(A1, N1);
2621 const SCEV *A2N2 = SE->getMulExpr(A2, N2);
2622 const SCEV *A1N1_A2N2 = SE->getMinusSCEV(A1N1, A2N2);
2623 LLVM_DEBUG(
dbgs() <<
"\t A1*N1 - A2*N2 = " << *A1N1_A2N2 <<
"\n");
2625 ++SymbolicRDIVindependence;
2630 if (SE->isKnownNegative(C2_C1)) {
2631 ++SymbolicRDIVindependence;
2635 }
else if (SE->isKnownNonPositive(A1)) {
2636 if (SE->isKnownNonNegative(A2)) {
2640 const SCEV *A1N1 = SE->getMulExpr(A1, N1);
2641 const SCEV *A2N2 = SE->getMulExpr(A2, N2);
2642 const SCEV *A1N1_A2N2 = SE->getMinusSCEV(A1N1, A2N2);
2643 LLVM_DEBUG(
dbgs() <<
"\t A1*N1 - A2*N2 = " << *A1N1_A2N2 <<
"\n");
2645 ++SymbolicRDIVindependence;
2650 if (SE->isKnownPositive(C2_C1)) {
2651 ++SymbolicRDIVindependence;
2654 }
else if (SE->isKnownNonPositive(A2)) {
2658 const SCEV *A1N1 = SE->getMulExpr(A1, N1);
2661 ++SymbolicRDIVindependence;
2667 const SCEV *A2N2 = SE->getMulExpr(A2, N2);
2670 ++SymbolicRDIVindependence;
2687bool DependenceInfo::testSIV(
const SCEV *Src,
const SCEV *Dst,
unsigned &Level,
2689 const SCEV *&SplitIter)
const {
2694 if (SrcAddRec && DstAddRec) {
2695 const SCEV *SrcConst = SrcAddRec->
getStart();
2696 const SCEV *DstConst = DstAddRec->
getStart();
2699 const Loop *CurSrcLoop = SrcAddRec->
getLoop();
2700 const Loop *CurDstLoop = DstAddRec->
getLoop();
2701 assert(haveSameSD(CurSrcLoop, CurDstLoop) &&
2702 "Loops in the SIV test should have the same iteration space and "
2704 Level = mapSrcLoop(CurSrcLoop);
2706 if (SrcCoeff == DstCoeff)
2707 disproven = strongSIVtest(SrcCoeff, SrcConst, DstConst, CurSrcLoop,
2708 CurDstLoop, Level, Result, NewConstraint);
2709 else if (SrcCoeff == SE->getNegativeSCEV(DstCoeff))
2710 disproven = weakCrossingSIVtest(SrcCoeff, SrcConst, DstConst, CurSrcLoop,
2711 CurDstLoop, Level, Result, NewConstraint,
2715 exactSIVtest(SrcCoeff, DstCoeff, SrcConst, DstConst, CurSrcLoop,
2716 CurDstLoop, Level, Result, NewConstraint);
2717 return disproven || gcdMIVtest(Src, Dst, Result) ||
2718 symbolicRDIVtest(SrcCoeff, DstCoeff, SrcConst, DstConst, CurSrcLoop,
2722 const SCEV *SrcConst = SrcAddRec->
getStart();
2724 const SCEV *DstConst = Dst;
2725 const Loop *CurSrcLoop = SrcAddRec->
getLoop();
2726 Level = mapSrcLoop(CurSrcLoop);
2727 return weakZeroDstSIVtest(SrcCoeff, SrcConst, DstConst, CurSrcLoop,
2728 CurSrcLoop, Level, Result, NewConstraint) ||
2729 gcdMIVtest(Src, Dst, Result);
2732 const SCEV *DstConst = DstAddRec->
getStart();
2734 const SCEV *SrcConst = Src;
2735 const Loop *CurDstLoop = DstAddRec->
getLoop();
2736 Level = mapDstLoop(CurDstLoop);
2737 return weakZeroSrcSIVtest(DstCoeff, SrcConst, DstConst, CurDstLoop,
2738 CurDstLoop, Level, Result, NewConstraint) ||
2739 gcdMIVtest(Src, Dst, Result);
2758bool DependenceInfo::testRDIV(
const SCEV *Src,
const SCEV *Dst,
2766 const SCEV *SrcConst, *DstConst;
2767 const SCEV *SrcCoeff, *DstCoeff;
2768 const Loop *SrcLoop, *DstLoop;
2774 if (SrcAddRec && DstAddRec) {
2777 SrcLoop = SrcAddRec->
getLoop();
2780 DstLoop = DstAddRec->
getLoop();
2781 }
else if (SrcAddRec) {
2782 if (
const SCEVAddRecExpr *tmpAddRec =
2784 SrcConst = tmpAddRec->getStart();
2785 SrcCoeff = tmpAddRec->getStepRecurrence(*SE);
2786 SrcLoop = tmpAddRec->getLoop();
2789 DstLoop = SrcAddRec->
getLoop();
2792 }
else if (DstAddRec) {
2793 if (
const SCEVAddRecExpr *tmpAddRec =
2795 DstConst = tmpAddRec->getStart();
2796 DstCoeff = tmpAddRec->getStepRecurrence(*SE);
2797 DstLoop = tmpAddRec->getLoop();
2800 SrcLoop = DstAddRec->
getLoop();
2805 return exactRDIVtest(SrcCoeff, DstCoeff, SrcConst, DstConst, SrcLoop, DstLoop,
2807 gcdMIVtest(Src, Dst, Result) ||
2808 symbolicRDIVtest(SrcCoeff, DstCoeff, SrcConst, DstConst, SrcLoop,
2815bool DependenceInfo::testMIV(
const SCEV *Src,
const SCEV *Dst,
2820 Result.Consistent =
false;
2821 return gcdMIVtest(Src, Dst, Result) ||
2822 banerjeeMIVtest(Src, Dst,
Loops, Result);
2833 return std::nullopt;
2836bool DependenceInfo::accumulateCoefficientsGCD(
const SCEV *Expr,
2837 const Loop *CurLoop,
2838 const SCEV *&CurLoopCoeff,
2839 APInt &RunningGCD)
const {
2842 if (RunningGCD == 1)
2847 assert(isLoopInvariant(Expr, CurLoop) &&
2848 "Expected loop invariant expression");
2855 if (AddRec->
getLoop() == CurLoop) {
2856 CurLoopCoeff = Step;
2870 return accumulateCoefficientsGCD(Start, CurLoop, CurLoopCoeff, RunningGCD);
2891bool DependenceInfo::gcdMIVtest(
const SCEV *Src,
const SCEV *Dst,
2898 unsigned BitWidth = SE->getTypeSizeInBits(Src->getType());
2905 const SCEV *Coefficients = Src;
2906 while (
const SCEVAddRecExpr *AddRec =
2917 const SCEV *SrcConst = Coefficients;
2924 while (
const SCEVAddRecExpr *AddRec =
2935 const SCEV *DstConst = Coefficients;
2938 const SCEV *Delta = SE->getMinusSCEV(DstConst, SrcConst);
2943 for (
const SCEV *Operand : Sum->
operands()) {
2945 assert(!Constant &&
"Surprised to find multiple constants");
2962 if (ConstDelta == 0)
2966 APInt Remainder = ConstDelta.
srem(RunningGCD);
2967 if (Remainder != 0) {
2986 bool Improved =
false;
2988 while (
const SCEVAddRecExpr *AddRec =
2991 const Loop *CurLoop = AddRec->
getLoop();
2992 RunningGCD = ExtraGCD;
2994 const SCEV *DstCoeff = SE->getMinusSCEV(SrcCoeff, SrcCoeff);
2996 if (!accumulateCoefficientsGCD(Src, CurLoop, SrcCoeff, RunningGCD) ||
2997 !accumulateCoefficientsGCD(Dst, CurLoop, DstCoeff, RunningGCD))
3000 Delta = SE->getMinusSCEV(SrcCoeff, DstCoeff);
3010 if (RunningGCD != 0) {
3011 Remainder = ConstDelta.
srem(RunningGCD);
3013 if (Remainder != 0) {
3014 unsigned Level = mapSrcLoop(CurLoop);
3015 Result.DV[
Level - 1].Direction &= ~Dependence::DVEntry::EQ;
3059bool DependenceInfo::banerjeeMIVtest(
const SCEV *Src,
const SCEV *Dst,
3066 ++BanerjeeApplications;
3069 CoefficientInfo *
A = collectCoeffInfo(Src,
true, A0);
3072 CoefficientInfo *
B = collectCoeffInfo(Dst,
false, B0);
3073 BoundInfo *Bound =
new BoundInfo[MaxLevels + 1];
3074 const SCEV *Delta = SE->getMinusSCEV(B0, A0);
3079 for (
unsigned K = 1;
K <= MaxLevels; ++
K) {
3080 Bound[
K].Iterations =
A[
K].Iterations ?
A[
K].Iterations :
B[
K].Iterations;
3083 findBoundsALL(
A,
B, Bound, K);
3098 bool Disproved =
false;
3101 unsigned DepthExpanded = 0;
3103 exploreDirections(1,
A,
B, Bound,
Loops, DepthExpanded, Delta);
3105 bool Improved =
false;
3106 for (
unsigned K = 1;
K <= CommonLevels; ++
K) {
3108 unsigned Old =
Result.DV[
K - 1].Direction;
3109 Result.DV[
K - 1].Direction = Old & Bound[
K].DirSet;
3110 Improved |= Old !=
Result.DV[
K - 1].Direction;
3111 if (!
Result.DV[K - 1].Direction) {
3119 ++BanerjeeSuccesses;
3121 ++BanerjeeIndependence;
3125 ++BanerjeeIndependence;
3139unsigned DependenceInfo::exploreDirections(
unsigned Level, CoefficientInfo *
A,
3140 CoefficientInfo *
B, BoundInfo *Bound,
3142 unsigned &DepthExpanded,
3143 const SCEV *Delta)
const {
3149 LLVM_DEBUG(
dbgs() <<
"Number of common levels exceeded the threshold. MIV "
3150 "direction exploration is terminated.\n");
3151 for (
unsigned K = 1;
K <= CommonLevels; ++
K)
3157 if (Level > CommonLevels) {
3160 for (
unsigned K = 1;
K <= CommonLevels; ++
K) {
3162 Bound[
K].DirSet |= Bound[
K].Direction;
3187 if (Level > DepthExpanded) {
3188 DepthExpanded =
Level;
3190 findBoundsLT(
A,
B, Bound, Level);
3191 findBoundsGT(
A,
B, Bound, Level);
3192 findBoundsEQ(
A,
B, Bound, Level);
3231 unsigned NewDeps = 0;
3235 NewDeps += exploreDirections(Level + 1,
A,
B, Bound,
Loops, DepthExpanded,
3240 NewDeps += exploreDirections(Level + 1,
A,
B, Bound,
Loops, DepthExpanded,
3245 NewDeps += exploreDirections(Level + 1,
A,
B, Bound,
Loops, DepthExpanded,
3251 return exploreDirections(Level + 1,
A,
B, Bound,
Loops, DepthExpanded,
3256bool DependenceInfo::testBounds(
unsigned char DirKind,
unsigned Level,
3257 BoundInfo *Bound,
const SCEV *Delta)
const {
3258 Bound[
Level].Direction = DirKind;
3259 if (
const SCEV *LowerBound = getLowerBound(Bound))
3262 if (
const SCEV *UpperBound = getUpperBound(Bound))
3283void DependenceInfo::findBoundsALL(CoefficientInfo *
A, CoefficientInfo *
B,
3284 BoundInfo *Bound,
unsigned K)
const {
3289 if (Bound[K].Iterations) {
3291 SE->getMinusSCEV(
A[K].NegPart,
B[K].PosPart), Bound[K].Iterations);
3293 SE->getMinusSCEV(
A[K].PosPart,
B[K].NegPart), Bound[K].Iterations);
3298 SE->getZero(
A[K].Coeff->
getType());
3301 SE->getZero(
A[K].Coeff->
getType());
3320void DependenceInfo::findBoundsEQ(CoefficientInfo *
A, CoefficientInfo *
B,
3321 BoundInfo *Bound,
unsigned K)
const {
3326 if (Bound[K].Iterations) {
3327 const SCEV *Delta = SE->getMinusSCEV(
A[K].Coeff,
B[K].Coeff);
3328 const SCEV *NegativePart = getNegativePart(Delta);
3330 SE->getMulExpr(NegativePart, Bound[K].Iterations);
3331 const SCEV *PositivePart = getPositivePart(Delta);
3333 SE->getMulExpr(PositivePart, Bound[K].Iterations);
3337 const SCEV *Delta = SE->getMinusSCEV(
A[K].Coeff,
B[K].Coeff);
3338 const SCEV *NegativePart = getNegativePart(Delta);
3339 if (NegativePart->
isZero())
3341 const SCEV *PositivePart = getPositivePart(Delta);
3342 if (PositivePart->
isZero())
3360void DependenceInfo::findBoundsLT(CoefficientInfo *
A, CoefficientInfo *
B,
3361 BoundInfo *Bound,
unsigned K)
const {
3366 if (Bound[K].Iterations) {
3367 const SCEV *Iter_1 = SE->getMinusSCEV(
3368 Bound[K].Iterations, SE->getOne(Bound[K].Iterations->getType()));
3369 const SCEV *NegPart =
3370 getNegativePart(SE->getMinusSCEV(
A[K].NegPart,
B[K].Coeff));
3372 SE->getMinusSCEV(SE->getMulExpr(NegPart, Iter_1),
B[K].Coeff);
3373 const SCEV *PosPart =
3374 getPositivePart(SE->getMinusSCEV(
A[K].PosPart,
B[K].Coeff));
3376 SE->getMinusSCEV(SE->getMulExpr(PosPart, Iter_1),
B[K].Coeff);
3380 const SCEV *NegPart =
3381 getNegativePart(SE->getMinusSCEV(
A[K].NegPart,
B[K].Coeff));
3384 const SCEV *PosPart =
3385 getPositivePart(SE->getMinusSCEV(
A[K].PosPart,
B[K].Coeff));
3404void DependenceInfo::findBoundsGT(CoefficientInfo *
A, CoefficientInfo *
B,
3405 BoundInfo *Bound,
unsigned K)
const {
3410 if (Bound[K].Iterations) {
3411 const SCEV *Iter_1 = SE->getMinusSCEV(
3412 Bound[K].Iterations, SE->getOne(Bound[K].Iterations->getType()));
3413 const SCEV *NegPart =
3414 getNegativePart(SE->getMinusSCEV(
A[K].Coeff,
B[K].PosPart));
3416 SE->getAddExpr(SE->getMulExpr(NegPart, Iter_1),
A[K].Coeff);
3417 const SCEV *PosPart =
3418 getPositivePart(SE->getMinusSCEV(
A[K].Coeff,
B[K].NegPart));
3420 SE->getAddExpr(SE->getMulExpr(PosPart, Iter_1),
A[K].Coeff);
3424 const SCEV *NegPart =
3425 getNegativePart(SE->getMinusSCEV(
A[K].Coeff,
B[K].PosPart));
3428 const SCEV *PosPart =
3429 getPositivePart(SE->getMinusSCEV(
A[K].Coeff,
B[K].NegPart));
3436const SCEV *DependenceInfo::getPositivePart(
const SCEV *
X)
const {
3437 return SE->getSMaxExpr(
X, SE->getZero(
X->getType()));
3441const SCEV *DependenceInfo::getNegativePart(
const SCEV *
X)
const {
3442 return SE->getSMinExpr(
X, SE->getZero(
X->getType()));
3448DependenceInfo::CoefficientInfo *
3449DependenceInfo::collectCoeffInfo(
const SCEV *Subscript,
bool SrcFlag,
3451 const SCEV *
Zero = SE->getZero(Subscript->getType());
3452 CoefficientInfo *CI =
new CoefficientInfo[MaxLevels + 1];
3453 for (
unsigned K = 1;
K <= MaxLevels; ++
K) {
3455 CI[
K].PosPart =
Zero;
3456 CI[
K].NegPart =
Zero;
3457 CI[
K].Iterations =
nullptr;
3461 unsigned K = SrcFlag ? mapSrcLoop(L) : mapDstLoop(
L);
3463 CI[
K].PosPart = getPositivePart(CI[K].Coeff);
3464 CI[
K].NegPart = getNegativePart(CI[K].Coeff);
3465 CI[
K].Iterations = collectUpperBound(L, Subscript->getType());
3471 for (
unsigned K = 1;
K <= MaxLevels; ++
K) {
3478 if (CI[K].Iterations)
3493const SCEV *DependenceInfo::getLowerBound(BoundInfo *Bound)
const {
3494 const SCEV *Sum = Bound[1].Lower[Bound[1].Direction];
3495 for (
unsigned K = 2; Sum &&
K <= MaxLevels; ++
K) {
3508const SCEV *DependenceInfo::getUpperBound(BoundInfo *Bound)
const {
3509 const SCEV *Sum = Bound[1].Upper[Bound[1].Direction];
3510 for (
unsigned K = 2; Sum &&
K <= MaxLevels; ++
K) {
3528const SCEV *DependenceInfo::findCoefficient(
const SCEV *Expr,
3529 const Loop *TargetLoop)
const {
3532 return SE->getZero(Expr->
getType());
3533 if (AddRec->
getLoop() == TargetLoop)
3535 return findCoefficient(AddRec->
getStart(), TargetLoop);
3543const SCEV *DependenceInfo::zeroCoefficient(
const SCEV *Expr,
3544 const Loop *TargetLoop)
const {
3548 if (AddRec->
getLoop() == TargetLoop)
3550 return SE->getAddRecExpr(zeroCoefficient(AddRec->
getStart(), TargetLoop),
3560const SCEV *DependenceInfo::addToCoefficient(
const SCEV *Expr,
3561 const Loop *TargetLoop,
3565 return SE->getAddRecExpr(Expr,
Value, TargetLoop,
3567 if (AddRec->
getLoop() == TargetLoop) {
3574 if (SE->isLoopInvariant(AddRec, TargetLoop))
3576 return SE->getAddRecExpr(
3592bool DependenceInfo::propagate(
const SCEV *&Src,
const SCEV *&Dst,
3597 for (
unsigned LI :
Loops.set_bits()) {
3600 if (Constraints[LI].isDistance())
3601 Result |= propagateDistance(Src, Dst, Constraints[LI], Consistent);
3602 else if (Constraints[LI].isLine())
3603 Result |= propagateLine(Src, Dst, Constraints[LI], Consistent);
3604 else if (Constraints[LI].isPoint())
3605 Result |= propagatePoint(Src, Dst, Constraints[LI]);
3615bool DependenceInfo::propagateDistance(
const SCEV *&Src,
const SCEV *&Dst,
3616 Constraint &CurConstraint,
3618 const Loop *CurSrcLoop = CurConstraint.getAssociatedSrcLoop();
3619 const Loop *CurDstLoop = CurConstraint.getAssociatedDstLoop();
3621 const SCEV *A_K = findCoefficient(Src, CurSrcLoop);
3624 const SCEV *DA_K = SE->getMulExpr(A_K, CurConstraint.getD());
3625 Src = SE->getMinusSCEV(Src, DA_K);
3626 Src = zeroCoefficient(Src, CurSrcLoop);
3629 Dst = addToCoefficient(Dst, CurDstLoop, SE->getNegativeSCEV(A_K));
3631 if (!findCoefficient(Dst, CurDstLoop)->
isZero())
3641bool DependenceInfo::propagateLine(
const SCEV *&Src,
const SCEV *&Dst,
3642 Constraint &CurConstraint,
3644 const Loop *CurSrcLoop = CurConstraint.getAssociatedSrcLoop();
3645 const Loop *CurDstLoop = CurConstraint.getAssociatedDstLoop();
3646 const SCEV *
A = CurConstraint.getA();
3647 const SCEV *
B = CurConstraint.getB();
3648 const SCEV *
C = CurConstraint.getC();
3656 if (!Bconst || !Cconst)
3659 APInt Charlie = Cconst->
getAPInt();
3660 APInt CdivB = Charlie.
sdiv(Beta);
3661 assert(Charlie.
srem(Beta) == 0 &&
"C should be evenly divisible by B");
3662 const SCEV *AP_K = findCoefficient(Dst, CurDstLoop);
3663 Src = SE->getMinusSCEV(Src, SE->getMulExpr(AP_K, SE->getConstant(CdivB)));
3664 Dst = zeroCoefficient(Dst, CurDstLoop);
3665 if (!findCoefficient(Src, CurSrcLoop)->
isZero())
3667 }
else if (
B->isZero()) {
3670 if (!Aconst || !Cconst)
3673 APInt Charlie = Cconst->
getAPInt();
3674 APInt CdivA = Charlie.
sdiv(Alpha);
3675 assert(Charlie.
srem(Alpha) == 0 &&
"C should be evenly divisible by A");
3676 const SCEV *A_K = findCoefficient(Src, CurSrcLoop);
3677 Src = SE->getAddExpr(Src, SE->getMulExpr(A_K, SE->getConstant(CdivA)));
3678 Src = zeroCoefficient(Src, CurSrcLoop);
3679 if (!findCoefficient(Dst, CurDstLoop)->
isZero())
3684 if (!Aconst || !Cconst)
3687 APInt Charlie = Cconst->
getAPInt();
3688 APInt CdivA = Charlie.
sdiv(Alpha);
3689 assert(Charlie.
srem(Alpha) == 0 &&
"C should be evenly divisible by A");
3690 const SCEV *A_K = findCoefficient(Src, CurSrcLoop);
3691 Src = SE->getAddExpr(Src, SE->getMulExpr(A_K, SE->getConstant(CdivA)));
3692 Src = zeroCoefficient(Src, CurSrcLoop);
3693 Dst = addToCoefficient(Dst, CurDstLoop, A_K);
3694 if (!findCoefficient(Dst, CurDstLoop)->
isZero())
3698 const SCEV *A_K = findCoefficient(Src, CurSrcLoop);
3699 Src = SE->getMulExpr(Src,
A);
3700 Dst = SE->getMulExpr(Dst,
A);
3701 Src = SE->getAddExpr(Src, SE->getMulExpr(A_K,
C));
3702 Src = zeroCoefficient(Src, CurSrcLoop);
3703 Dst = addToCoefficient(Dst, CurDstLoop, SE->getMulExpr(A_K,
B));
3704 if (!findCoefficient(Dst, CurDstLoop)->
isZero())
3715bool DependenceInfo::propagatePoint(
const SCEV *&Src,
const SCEV *&Dst,
3716 Constraint &CurConstraint) {
3717 const Loop *CurSrcLoop = CurConstraint.getAssociatedSrcLoop();
3718 const Loop *CurDstLoop = CurConstraint.getAssociatedDstLoop();
3719 const SCEV *A_K = findCoefficient(Src, CurSrcLoop);
3720 const SCEV *AP_K = findCoefficient(Dst, CurDstLoop);
3721 const SCEV *XA_K = SE->getMulExpr(A_K, CurConstraint.getX());
3722 const SCEV *YAP_K = SE->getMulExpr(AP_K, CurConstraint.getY());
3724 Src = SE->getAddExpr(Src, SE->getMinusSCEV(XA_K, YAP_K));
3725 Src = zeroCoefficient(Src, CurSrcLoop);
3728 Dst = zeroCoefficient(Dst, CurDstLoop);
3735 const Constraint &CurConstraint)
const {
3738 if (CurConstraint.isAny())
3740 else if (CurConstraint.isDistance()) {
3742 Level.Scalar =
false;
3743 Level.Distance = CurConstraint.getD();
3745 if (!SE->isKnownNonZero(
Level.Distance))
3747 if (!SE->isKnownNonPositive(
Level.Distance))
3749 if (!SE->isKnownNonNegative(
Level.Distance))
3751 Level.Direction &= NewDirection;
3752 }
else if (CurConstraint.isLine()) {
3753 Level.Scalar =
false;
3754 Level.Distance =
nullptr;
3756 }
else if (CurConstraint.isPoint()) {
3757 Level.Scalar =
false;
3758 Level.Distance =
nullptr;
3761 CurConstraint.getX()))
3765 CurConstraint.getX()))
3769 CurConstraint.getX()))
3772 Level.Direction &= NewDirection;
3787 Loop *SrcLoop = LI->getLoopFor(Src->getParent());
3788 Loop *DstLoop = LI->getLoopFor(Dst->getParent());
3789 const SCEV *SrcAccessFn = SE->getSCEVAtScope(SrcPtr, SrcLoop);
3790 const SCEV *DstAccessFn = SE->getSCEVAtScope(DstPtr, DstLoop);
3791 const SCEVUnknown *SrcBase =
3793 const SCEVUnknown *DstBase =
3796 if (!SrcBase || !DstBase || SrcBase != DstBase)
3801 if (!tryDelinearizeFixedSize(Src, Dst, SrcAccessFn, DstAccessFn,
3802 SrcSubscripts, DstSubscripts) &&
3803 !tryDelinearizeParametricSize(Src, Dst, SrcAccessFn, DstAccessFn,
3804 SrcSubscripts, DstSubscripts))
3807 assert(isLoopInvariant(SrcBase, SrcLoop) &&
3808 isLoopInvariant(DstBase, DstLoop) &&
3809 "Expected SrcBase and DstBase to be loop invariant");
3813 dbgs() <<
"\nSrcSubscripts: ";
3814 for (
int I = 0;
I <
Size;
I++)
3815 dbgs() << *SrcSubscripts[
I];
3816 dbgs() <<
"\nDstSubscripts: ";
3817 for (
int I = 0;
I <
Size;
I++)
3818 dbgs() << *DstSubscripts[
I];
3826 SCEVMonotonicityChecker MonChecker(SE);
3827 const Loop *OutermostLoop = SrcLoop ? SrcLoop->
getOutermostLoop() :
nullptr;
3828 for (
int I = 0;
I <
Size; ++
I) {
3829 Pair[
I].Src = SrcSubscripts[
I];
3830 Pair[
I].Dst = DstSubscripts[
I];
3831 unifySubscriptType(&Pair[
I]);
3834 if (MonChecker.checkMonotonicity(Pair[
I].Src, OutermostLoop).isUnknown())
3836 if (MonChecker.checkMonotonicity(Pair[
I].Dst, OutermostLoop).isUnknown())
3847bool DependenceInfo::tryDelinearizeFixedSize(
3852 const SCEVUnknown *SrcBase =
3854 const SCEVUnknown *DstBase =
3856 assert(SrcBase && DstBase && SrcBase == DstBase &&
3857 "expected src and dst scev unknowns to be equal");
3860 SmallVector<int, 4> SrcSizes;
3861 SmallVector<int, 4> DstSizes;
3870 if (SrcSizes.size() != DstSizes.
size() ||
3871 !std::equal(SrcSizes.begin(), SrcSizes.end(), DstSizes.
begin())) {
3872 SrcSubscripts.
clear();
3873 DstSubscripts.
clear();
3878 "Expected equal number of entries in the list of SrcSubscripts and "
3891 auto AllIndicesInRange = [&](SmallVector<int, 4> &DimensionSizes,
3892 SmallVectorImpl<const SCEV *> &Subscripts,
3894 size_t SSize = Subscripts.
size();
3895 for (
size_t I = 1;
I < SSize; ++
I) {
3896 const SCEV *S = Subscripts[
I];
3899 dbgs() <<
"Check failed: !isKnownNonNegative(S, Ptr)\n";
3900 dbgs() <<
" S: " << *S <<
"\n" <<
" Ptr: " << *
Ptr <<
"\n";
3905 const SCEV *
Range = SE->getConstant(
3906 ConstantInt::get(SType, DimensionSizes[
I - 1],
false));
3907 if (!isKnownLessThan(S,
Range)) {
3909 dbgs() <<
"Check failed: !isKnownLessThan(S, Range)\n";
3910 dbgs() <<
" S: " << *S <<
"\n"
3911 <<
" Range: " << *
Range <<
"\n";
3920 if (!AllIndicesInRange(SrcSizes, SrcSubscripts, SrcPtr) ||
3921 !AllIndicesInRange(DstSizes, DstSubscripts, DstPtr)) {
3923 SrcSubscripts.
clear();
3924 DstSubscripts.
clear();
3929 dbgs() <<
"Delinearized subscripts of fixed-size array\n"
3930 <<
"SrcGEP:" << *SrcPtr <<
"\n"
3931 <<
"DstGEP:" << *DstPtr <<
"\n";
3936bool DependenceInfo::tryDelinearizeParametricSize(
3943 const SCEVUnknown *SrcBase =
3945 const SCEVUnknown *DstBase =
3947 assert(SrcBase && DstBase && SrcBase == DstBase &&
3948 "expected src and dst scev unknowns to be equal");
3950 const SCEV *ElementSize = SE->getElementSize(Src);
3951 if (ElementSize != SE->getElementSize(Dst))
3954 const SCEV *SrcSCEV = SE->getMinusSCEV(SrcAccessFn, SrcBase);
3955 const SCEV *DstSCEV = SE->getMinusSCEV(DstAccessFn, DstBase);
3976 if (SrcSubscripts.
size() < 2 || DstSubscripts.
size() < 2 ||
3977 SrcSubscripts.
size() != DstSubscripts.
size())
3980 size_t Size = SrcSubscripts.
size();
3989 for (
size_t I = 1;
I <
Size; ++
I) {
3992 bool SLT = isKnownLessThan(SrcSubscripts[
I], Sizes[
I - 1]);
3993 bool DLT = isKnownLessThan(DstSubscripts[
I], Sizes[
I - 1]);
3994 if (SNN && DNN && SLT && DLT)
3998 dbgs() <<
"Delinearization checks failed: can't prove the following\n";
4000 dbgs() <<
" isKnownNonNegative(" << *SrcSubscripts[
I] <<
")\n";
4002 dbgs() <<
" isKnownNonNegative(" << *DstSubscripts[
I] <<
")\n";
4004 dbgs() <<
" isKnownLessThan(" << *SrcSubscripts[
I] <<
", "
4005 << *
Sizes[
I - 1] <<
")\n";
4007 dbgs() <<
" isKnownLessThan(" << *DstSubscripts[
I] <<
", "
4008 << *
Sizes[
I - 1] <<
")\n";
4022 for (
unsigned VI : BV.
set_bits()) {
4032 FunctionAnalysisManager::Invalidator &Inv) {
4039 return Inv.invalidate<
AAManager>(F, PA) ||
4059std::unique_ptr<Dependence>
4061 bool UnderRuntimeAssumptions) {
4063 bool PossiblyLoopIndependent =
true;
4065 PossiblyLoopIndependent =
false;
4067 if (!(Src->mayReadOrWriteMemory() && Dst->mayReadOrWriteMemory()))
4073 LLVM_DEBUG(
dbgs() <<
"can only handle simple loads and stores\n");
4074 return std::make_unique<Dependence>(Src, Dst,
4086 return std::make_unique<Dependence>(Src, Dst,
4100 LLVM_DEBUG(
dbgs() <<
"can't analyze must alias with different sizes\n");
4101 return std::make_unique<Dependence>(Src, Dst,
4107 const SCEV *SrcSCEV = SE->getSCEV(SrcPtr);
4108 const SCEV *DstSCEV = SE->getSCEV(DstPtr);
4111 const SCEV *SrcBase = SE->getPointerBase(SrcSCEV);
4112 const SCEV *DstBase = SE->getPointerBase(DstSCEV);
4113 if (SrcBase != DstBase) {
4120 LLVM_DEBUG(
dbgs() <<
"can't analyze SCEV with different pointer base\n");
4121 return std::make_unique<Dependence>(Src, Dst,
4129 Loop *SrcLoop = LI->getLoopFor(Src->getParent());
4130 Loop *DstLoop = LI->getLoopFor(Dst->getParent());
4131 if (!isLoopInvariant(SrcBase, SrcLoop) ||
4132 !isLoopInvariant(DstBase, DstLoop)) {
4133 LLVM_DEBUG(
dbgs() <<
"The base pointer is not loop invariant.\n");
4134 return std::make_unique<Dependence>(Src, Dst,
4139 const SCEV *SrcEv = SE->getMinusSCEV(SrcSCEV, SrcBase);
4140 const SCEV *DstEv = SE->getMinusSCEV(DstSCEV, DstBase);
4143 if (!SE->isKnownMultipleOf(SrcEv, EltSize, Assume) ||
4144 !SE->isKnownMultipleOf(DstEv, EltSize, Assume)) {
4145 LLVM_DEBUG(
dbgs() <<
"can't analyze SCEV with different offsets\n");
4146 return std::make_unique<Dependence>(Src, Dst,
4150 if (!Assume.empty()) {
4151 if (!UnderRuntimeAssumptions)
4152 return std::make_unique<Dependence>(Src, Dst,
4155 unsigned N = Assumptions.size();
4157 bool Implied =
false;
4158 for (
unsigned I = 0;
I !=
N && !Implied;
I++)
4159 if (Assumptions[
I]->implies(
P, *SE))
4162 Assumptions.push_back(
P);
4168 Pair[0].Src = SrcEv;
4169 Pair[0].Dst = DstEv;
4171 SCEVMonotonicityChecker MonChecker(SE);
4174 if (MonChecker.checkMonotonicity(Pair[0].Src, OutermostLoop).isUnknown() ||
4175 MonChecker.checkMonotonicity(Pair[0].Dst, OutermostLoop).isUnknown())
4176 return std::make_unique<Dependence>(Src, Dst,
4180 if (tryDelinearize(Src, Dst, Pair)) {
4182 Pairs = Pair.
size();
4187 establishNestingLevels(Src, Dst);
4189 LLVM_DEBUG(
dbgs() <<
" common nesting levels = " << CommonLevels <<
"\n");
4190 LLVM_DEBUG(
dbgs() <<
" maximum nesting levels = " << MaxLevels <<
"\n");
4191 LLVM_DEBUG(
dbgs() <<
" SameSD nesting levels = " << SameSDLevels <<
"\n");
4194 CommonLevels += SameSDLevels;
4195 MaxLevels -= SameSDLevels;
4196 if (SameSDLevels > 0) {
4199 for (
unsigned P = 0;
P < Pairs; ++
P) {
4201 Subscript::ClassificationKind TestClass =
4202 classifyPair(Pair[
P].Src, LI->getLoopFor(Src->getParent()),
4203 Pair[
P].Dst, LI->getLoopFor(Dst->getParent()),
Loops);
4205 if (TestClass != Subscript::ZIV && TestClass != Subscript::SIV &&
4206 TestClass != Subscript::RDIV) {
4208 CommonLevels -= SameSDLevels;
4209 MaxLevels += SameSDLevels;
4216 if (SameSDLevels > 0)
4220 PossiblyLoopIndependent, CommonLevels);
4223 for (
unsigned P = 0;
P < Pairs; ++
P) {
4224 assert(Pair[
P].Src->getType()->isIntegerTy() &&
"Src must be an integer");
4225 assert(Pair[
P].Dst->getType()->isIntegerTy() &&
"Dst must be an integer");
4226 Pair[
P].Loops.
resize(MaxLevels + 1);
4227 Pair[
P].GroupLoops.
resize(MaxLevels + 1);
4229 removeMatchingExtensions(&Pair[
P]);
4230 Pair[
P].Classification =
4231 classifyPair(Pair[
P].Src, LI->getLoopFor(Src->getParent()), Pair[
P].Dst,
4232 LI->getLoopFor(Dst->getParent()), Pair[
P].Loops);
4233 Pair[
P].GroupLoops = Pair[
P].Loops;
4234 Pair[
P].Group.set(
P);
4303 for (
unsigned SI = 0;
SI < Pairs; ++
SI) {
4304 if (Pair[
SI].Classification == Subscript::NonLinear) {
4306 ++NonlinearSubscriptPairs;
4307 collectCommonLoops(Pair[
SI].Src, LI->getLoopFor(Src->getParent()),
4309 collectCommonLoops(Pair[
SI].Dst, LI->getLoopFor(Dst->getParent()),
4311 Result.Consistent =
false;
4312 }
else if (Pair[
SI].Classification == Subscript::ZIV) {
4318 for (
unsigned SJ =
SI + 1; SJ < Pairs; ++SJ) {
4320 Intersection &= Pair[SJ].GroupLoops;
4321 if (Intersection.
any()) {
4323 Pair[SJ].GroupLoops |= Pair[
SI].GroupLoops;
4325 Pair[SJ].Group |= Pair[
SI].Group;
4330 if (Pair[
SI].Group.count() == 1) {
4332 ++SeparableSubscriptPairs;
4335 ++CoupledSubscriptPairs;
4346 Constraint NewConstraint;
4347 NewConstraint.setAny(SE);
4352 switch (Pair[
SI].Classification) {
4353 case Subscript::ZIV:
4355 if (testZIV(Pair[
SI].Src, Pair[
SI].Dst, Result))
4358 case Subscript::SIV: {
4361 const SCEV *SplitIter =
nullptr;
4362 if (testSIV(Pair[
SI].Src, Pair[
SI].Dst, Level, Result, NewConstraint,
4367 case Subscript::RDIV:
4369 if (testRDIV(Pair[
SI].Src, Pair[
SI].Dst, Result))
4372 case Subscript::MIV:
4374 if (testMIV(Pair[
SI].Src, Pair[
SI].Dst, Pair[
SI].
Loops, Result))
4382 if (Coupled.
count()) {
4385 LLVM_DEBUG(
dbgs() <<
"MaxLevels + 1 = " << MaxLevels + 1 <<
"\n");
4387 for (
unsigned II = 0;
II <= MaxLevels; ++
II)
4388 Constraints[
II].setAny(SE);
4396 for (
unsigned SJ : Group.set_bits()) {
4398 if (Pair[SJ].Classification == Subscript::SIV)
4404 unifySubscriptType(PairsInGroup);
4406 while (Sivs.
any()) {
4408 for (
unsigned SJ : Sivs.
set_bits()) {
4412 const SCEV *SplitIter =
nullptr;
4414 if (testSIV(Pair[SJ].Src, Pair[SJ].Dst, Level, Result, NewConstraint,
4417 ConstrainedLevels.
set(Level);
4418 if (intersectConstraints(&Constraints[Level], &NewConstraint)) {
4419 if (Constraints[Level].isEmpty()) {
4420 ++DeltaIndependence;
4432 for (
unsigned SJ : Mivs.
set_bits()) {
4435 if (propagate(Pair[SJ].Src, Pair[SJ].Dst, Pair[SJ].
Loops,
4436 Constraints, Result.Consistent)) {
4438 ++DeltaPropagations;
4439 Pair[SJ].Classification = classifyPair(
4440 Pair[SJ].Src, LI->getLoopFor(Src->getParent()), Pair[SJ].Dst,
4441 LI->getLoopFor(Dst->getParent()), Pair[SJ].Loops);
4442 switch (Pair[SJ].Classification) {
4443 case Subscript::ZIV:
4445 if (testZIV(Pair[SJ].Src, Pair[SJ].Dst, Result))
4449 case Subscript::SIV:
4453 case Subscript::RDIV:
4454 case Subscript::MIV:
4465 for (
unsigned SJ : Mivs.
set_bits()) {
4466 if (Pair[SJ].Classification == Subscript::RDIV) {
4468 if (testRDIV(Pair[SJ].Src, Pair[SJ].Dst, Result))
4478 for (
unsigned SJ : Mivs.
set_bits()) {
4479 if (Pair[SJ].Classification == Subscript::MIV) {
4481 if (testMIV(Pair[SJ].Src, Pair[SJ].Dst, Pair[SJ].
Loops, Result))
4489 for (
unsigned SJ : ConstrainedLevels.
set_bits()) {
4490 if (SJ > CommonLevels)
4492 updateDirection(Result.DV[SJ - 1], Constraints[SJ]);
4501 for (
unsigned SI = 0;
SI < Pairs; ++
SI)
4502 CompleteLoops |= Pair[
SI].
Loops;
4503 for (
unsigned II = 1;
II <= CommonLevels; ++
II)
4504 if (CompleteLoops[
II])
4505 Result.DV[
II - 1].Scalar =
false;
4510 for (
unsigned II = 1;
II <= Result.getLevels(); ++
II) {
4512 if (Result.DV[
II - 1].Distance ==
nullptr)
4513 Result.DV[
II - 1].Distance = SE->getZero(SrcSCEV->
getType());
4515 assert(Result.DV[
II - 1].Distance->isZero() &&
4516 "Inconsistency between distance and direction");
4522 const SCEV *Distance = Result.getDistance(
II);
4523 if (Distance && Distance->
isZero())
4525 "Distance is zero, but direction is not EQ");
4529 if (SameSDLevels > 0) {
4532 assert(CommonLevels >= SameSDLevels);
4533 CommonLevels -= SameSDLevels;
4534 MaxLevels += SameSDLevels;
4535 std::unique_ptr<FullDependence::DVEntry[]> DV, DVSameSD;
4536 DV = std::make_unique<FullDependence::DVEntry[]>(CommonLevels);
4537 DVSameSD = std::make_unique<FullDependence::DVEntry[]>(SameSDLevels);
4538 for (
unsigned Level = 0; Level < CommonLevels; ++Level)
4539 DV[Level] = Result.DV[Level];
4540 for (
unsigned Level = 0; Level < SameSDLevels; ++Level)
4541 DVSameSD[Level] = Result.DV[CommonLevels + Level];
4542 Result.DV = std::move(DV);
4543 Result.DVSameSD = std::move(DVSameSD);
4544 Result.Levels = CommonLevels;
4545 Result.SameSDLevels = SameSDLevels;
4547 Result.Consistent =
false;
4550 if (PossiblyLoopIndependent) {
4554 for (
unsigned II = 1;
II <= CommonLevels; ++
II) {
4556 Result.LoopIndependent =
false;
4563 bool AllEqual =
true;
4564 for (
unsigned II = 1;
II <= CommonLevels; ++
II) {
4574 return std::make_unique<FullDependence>(std::move(Result));
4625 unsigned SplitLevel) {
4627 "Dep should be splitable at SplitLevel");
4630 assert(Src->mayReadFromMemory() || Src->mayWriteToMemory());
4631 assert(Dst->mayReadFromMemory() || Dst->mayWriteToMemory());
4641 establishNestingLevels(Src, Dst);
4643 FullDependence Result(Src, Dst, Dep.Assumptions,
false, CommonLevels);
4647 const SCEV *SrcSCEV = SE->getSCEV(SrcPtr);
4648 const SCEV *DstSCEV = SE->getSCEV(DstPtr);
4649 Pair[0].Src = SE->removePointerBase(SrcSCEV);
4650 Pair[0].Dst = SE->removePointerBase(DstSCEV);
4653 if (tryDelinearize(Src, Dst, Pair)) {
4655 Pairs = Pair.
size();
4659 for (
unsigned P = 0;
P < Pairs; ++
P) {
4660 assert(Pair[
P].Src->getType()->isIntegerTy() &&
"Src must be an integer");
4661 assert(Pair[
P].Dst->getType()->isIntegerTy() &&
"Dst must be an integer");
4662 Pair[
P].Loops.
resize(MaxLevels + 1);
4663 Pair[
P].GroupLoops.
resize(MaxLevels + 1);
4665 removeMatchingExtensions(&Pair[
P]);
4666 Pair[
P].Classification =
4667 classifyPair(Pair[
P].Src, LI->getLoopFor(Src->getParent()), Pair[
P].Dst,
4668 LI->getLoopFor(Dst->getParent()), Pair[
P].Loops);
4669 Pair[
P].GroupLoops = Pair[
P].Loops;
4670 Pair[
P].Group.set(
P);
4677 for (
unsigned SI = 0;
SI < Pairs; ++
SI) {
4678 if (Pair[
SI].Classification == Subscript::NonLinear) {
4680 collectCommonLoops(Pair[
SI].Src, LI->getLoopFor(Src->getParent()),
4682 collectCommonLoops(Pair[
SI].Dst, LI->getLoopFor(Dst->getParent()),
4684 Result.Consistent =
false;
4685 }
else if (Pair[
SI].Classification == Subscript::ZIV)
4690 for (
unsigned SJ =
SI + 1; SJ < Pairs; ++SJ) {
4692 Intersection &= Pair[SJ].GroupLoops;
4693 if (Intersection.
any()) {
4695 Pair[SJ].GroupLoops |= Pair[
SI].GroupLoops;
4697 Pair[SJ].Group |= Pair[
SI].Group;
4702 if (Pair[
SI].Group.count() == 1)
4710 Constraint NewConstraint;
4711 NewConstraint.setAny(SE);
4715 switch (Pair[
SI].Classification) {
4716 case Subscript::SIV: {
4718 const SCEV *SplitIter =
nullptr;
4719 (void)testSIV(Pair[
SI].Src, Pair[
SI].Dst, Level, Result, NewConstraint,
4721 if (Level == SplitLevel) {
4722 assert(SplitIter !=
nullptr);
4727 case Subscript::ZIV:
4728 case Subscript::RDIV:
4729 case Subscript::MIV:
4736 assert(!Coupled.
empty() &&
"coupled expected non-empty");
4740 for (
unsigned II = 0;
II <= MaxLevels; ++
II)
4741 Constraints[
II].setAny(SE);
4747 for (
unsigned SJ : Group.set_bits()) {
4748 if (Pair[SJ].Classification == Subscript::SIV)
4753 while (Sivs.
any()) {
4755 for (
unsigned SJ : Sivs.
set_bits()) {
4758 const SCEV *SplitIter =
nullptr;
4759 (void)testSIV(Pair[SJ].Src, Pair[SJ].Dst, Level, Result, NewConstraint,
4761 if (Level == SplitLevel && SplitIter)
4763 ConstrainedLevels.
set(Level);
4764 if (intersectConstraints(&Constraints[Level], &NewConstraint))
4771 for (
unsigned SJ : Mivs.
set_bits()) {
4773 if (!propagate(Pair[SJ].Src, Pair[SJ].Dst, Pair[SJ].
Loops, Constraints,
4776 Pair[SJ].Classification = classifyPair(
4777 Pair[SJ].Src, LI->getLoopFor(Src->getParent()), Pair[SJ].Dst,
4778 LI->getLoopFor(Dst->getParent()), Pair[SJ].Loops);
4779 switch (Pair[SJ].Classification) {
4780 case Subscript::ZIV:
4783 case Subscript::SIV:
4787 case Subscript::RDIV:
4788 case Subscript::MIV:
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
static void print(raw_ostream &Out, object::Archive::Kind Kind, T Val)
Expand Atomic instructions
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
#define clEnumValN(ENUMVAL, FLAGNAME, DESC)
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds.
static cl::opt< DependenceTestType > EnableDependenceTest("da-enable-dependence-test", cl::init(DependenceTestType::All), cl::ReallyHidden, cl::desc("Run only specified dependence test routine and disable others. " "The purpose is mainly to exclude the influence of other " "dependence test routines in regression tests. If set to All, all " "dependence test routines are enabled."), cl::values(clEnumValN(DependenceTestType::All, "all", "Enable all dependence test routines."), clEnumValN(DependenceTestType::StrongSIV, "strong-siv", "Enable only Strong SIV test."), clEnumValN(DependenceTestType::WeakCrossingSIV, "weak-crossing-siv", "Enable only Weak-Crossing SIV test."), clEnumValN(DependenceTestType::ExactSIV, "exact-siv", "Enable only Exact SIV test."), clEnumValN(DependenceTestType::WeakZeroSIV, "weak-zero-siv", "Enable only Weak-Zero SIV test."), clEnumValN(DependenceTestType::ExactRDIV, "exact-rdiv", "Enable only Exact RDIV test."), clEnumValN(DependenceTestType::SymbolicRDIV, "symbolic-rdiv", "Enable only Symbolic RDIV test."), clEnumValN(DependenceTestType::GCDMIV, "gcd-miv", "Enable only GCD MIV test."), clEnumValN(DependenceTestType::BanerjeeMIV, "banerjee-miv", "Enable only Banerjee MIV test.")))
static bool isLoadOrStore(const Instruction *I)
static void dumpExampleDependence(raw_ostream &OS, DependenceInfo *DA, ScalarEvolution &SE, LoopInfo &LI, bool NormalizeResults)
static bool isDependenceTestEnabled(DependenceTestType Test)
Returns true iff Test is enabled.
static bool findGCD(unsigned Bits, const APInt &AM, const APInt &BM, const APInt &Delta, APInt &G, APInt &X, APInt &Y)
static void dumpSmallBitVector(SmallBitVector &BV)
static APInt ceilingOfQuotient(const APInt &A, const APInt &B)
static APInt floorOfQuotient(const APInt &A, const APInt &B)
static const SCEV * minusSCEVNoSignedOverflow(const SCEV *A, const SCEV *B, ScalarEvolution &SE)
Returns A - B if it guaranteed not to signed wrap.
static AliasResult underlyingObjectsAlias(AAResults *AA, const DataLayout &DL, const MemoryLocation &LocA, const MemoryLocation &LocB)
static std::pair< std::optional< APInt >, std::optional< APInt > > inferDomainOfAffine(const APInt &A, const APInt &B, const std::optional< APInt > &UB)
Given an affine expression of the form A*k + B, where k is an arbitrary integer, infer the possible r...
static std::optional< APInt > getConstantPart(const SCEV *Expr)
static bool isRemainderZero(const SCEVConstant *Dividend, const SCEVConstant *Divisor)
static cl::opt< bool > Delinearize("da-delinearize", cl::init(true), cl::Hidden, cl::desc("Try to delinearize array references."))
static cl::opt< bool > EnableMonotonicityCheck("da-enable-monotonicity-check", cl::init(false), cl::Hidden, cl::desc("Check if the subscripts are monotonic. If it's not, dependence " "is reported as unknown."))
static cl::opt< bool > DumpMonotonicityReport("da-dump-monotonicity-report", cl::init(false), cl::Hidden, cl::desc("When printing analysis, dump the results of monotonicity checks."))
static cl::opt< unsigned > MIVMaxLevelThreshold("da-miv-max-level-threshold", cl::init(7), cl::Hidden, cl::desc("Maximum depth allowed for the recursive algorithm used to " "explore MIV direction vectors."))
static cl::opt< bool > DisableDelinearizationChecks("da-disable-delinearization-checks", cl::Hidden, cl::desc("Disable checks that try to statically verify validity of " "delinearized subscripts. Enabling this option may result in incorrect " "dependence vectors for languages that allow the subscript of one " "dimension to underflow or overflow into another dimension."))
Module.h This file contains the declarations for the Module class.
static bool isZero(Value *V, const DataLayout &DL, DominatorTree *DT, AssumptionCache *AC)
Loop::LoopBounds::Direction Direction
ConstantRange Range(APInt(BitWidth, Low), APInt(BitWidth, High))
uint64_t IntrinsicInst * II
FunctionAnalysisManager FAM
#define INITIALIZE_PASS_DEPENDENCY(depName)
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
void visit(MachineFunction &MF, MachineBasicBlock &Start, std::function< void(MachineBasicBlock *)> op)
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
static TableGen::Emitter::Opt Y("gen-skeleton-entry", EmitSkeleton, "Generate example skeleton entry")
static TableGen::Emitter::OptClass< SkeletonEmitter > X("gen-skeleton-class", "Generate example skeleton class")
static SymbolRef::Type getType(const Symbol *Sym)
LocallyHashedType DenseMapInfo< LocallyHashedType >::Empty
A manager for alias analyses.
A wrapper pass to provide the legacy pass manager access to a suitably prepared AAResults object.
Class for arbitrary precision integers.
static LLVM_ABI void sdivrem(const APInt &LHS, const APInt &RHS, APInt &Quotient, APInt &Remainder)
APInt abs() const
Get the absolute value.
bool sgt(const APInt &RHS) const
Signed greater than comparison.
unsigned getBitWidth() const
Return the number of bits in the APInt.
static APInt getSignedMaxValue(unsigned numBits)
Gets maximum signed value of APInt for a specific bit width.
LLVM_ABI APInt sdiv(const APInt &RHS) const
Signed division function for APInt.
bool sle(const APInt &RHS) const
Signed less or equal comparison.
static APInt getSignedMinValue(unsigned numBits)
Gets minimum signed value of APInt for a specific bit width.
LLVM_ABI APInt srem(const APInt &RHS) const
Function for signed remainder operation.
bool slt(const APInt &RHS) const
Signed less than comparison.
static APInt getZero(unsigned numBits)
Get the '0' value for the specified bit-width.
bool sge(const APInt &RHS) const
Signed greater or equal comparison.
The possible results of an alias query.
@ MayAlias
The two locations may or may not alias.
@ NoAlias
The two locations do not alias at all.
@ PartialAlias
The two locations alias, but only due to a partial overlap.
@ MustAlias
The two locations precisely alias each other.
This templated class represents "all analyses that operate over <aparticular IR unit>" (e....
Represent the analysis usage information of a pass.
void setPreservesAll()
Set by analyses that do not transform their input at all.
AnalysisUsage & addRequiredTransitive()
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
This class is a wrapper over an AAResults, and it is intended to be used only when there are no IR ch...
void enableCrossIterationMode()
Assume that values may come from different cycle iterations.
bool isNoAlias(const MemoryLocation &LocA, const MemoryLocation &LocB)
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
@ ICMP_SLT
signed less than
@ ICMP_SLE
signed less or equal
@ ICMP_SGT
signed greater than
@ ICMP_SGE
signed greater or equal
This is an important base class in LLVM.
A parsed version of the target data layout string in and methods for querying it.
Legacy pass manager pass to access dependence information.
void getAnalysisUsage(AnalysisUsage &) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
bool runOnFunction(Function &F) override
runOnFunction - Virtual method overriden by subclasses to do the per-function processing of the pass.
void print(raw_ostream &, const Module *=nullptr) const override
print - Print out the internal state of the pass.
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.
LLVM_ABI const SCEV * getSplitIteration(const Dependence &Dep, unsigned Level)
getSplitIteration - Give a dependence that's splittable at some particular level, return the iteratio...
LLVM_ABI SCEVUnionPredicate getRuntimeAssumptions() const
getRuntimeAssumptions - Returns all the runtime assumptions under which the dependence test is valid.
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.
Dependence - This class represents a dependence between two memory memory references in a function.
Instruction * getDst() const
getDst - Returns the destination instruction for this dependence.
void dumpImp(raw_ostream &OS, bool IsSameSD=false) const
dumpImp - For debugging purposes.
Dependence(Dependence &&)=default
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 bool isPeelLast(unsigned Level, bool SameSD=false) const
isPeelLast - Returns true if peeling the last iteration from this regular or SameSD loop level will b...
virtual bool isConsistent() const
isConsistent - Returns true if this dependence is consistent (occurs every time the source and destin...
virtual unsigned getLevels() const
getLevels - Returns the number of common loops surrounding the source and destination of the dependen...
virtual unsigned getDirection(unsigned Level, bool SameSD=false) const
getDirection - Returns the direction associated with a particular common or SameSD level.
virtual bool isScalar(unsigned Level, bool SameSD=false) const
isScalar - Returns true if a particular regular or SameSD level is scalar; that is,...
bool isFlow() const
isFlow - Returns true if this is a flow (aka true) dependence.
virtual bool isPeelFirst(unsigned Level, bool SameSD=false) const
isPeelFirst - Returns true if peeling the first iteration from this regular or SameSD loop level will...
bool isInput() const
isInput - Returns true if this is an input dependence.
bool isAnti() const
isAnti - Returns true if this is an anti dependence.
virtual bool isSplitable(unsigned Level, bool SameSD=false) const
isSplitable - Returns true if splitting the loop will break the dependence.
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 dump(raw_ostream &OS) const
dump - For debugging purposes, dumps a dependence to OS.
virtual bool inSameSDLoops(unsigned Level) const
inSameSDLoops - Returns true if this level is an SameSD level, i.e., performed across two separate lo...
Class representing an expression and its matching format.
FullDependence - This class represents a dependence between two memory references in a function.
FullDependence(Instruction *Source, Instruction *Destination, const SCEVUnionPredicate &Assumes, bool PossiblyLoopIndependent, unsigned Levels)
unsigned getDirection(unsigned Level, bool SameSD=false) const override
getDirection - Returns the direction associated with a particular common or SameSD level.
bool isScalar(unsigned Level, bool SameSD=false) const override
isScalar - Returns true if a particular regular or SameSD level is scalar; that is,...
bool isDirectionNegative() const override
Check if the direction vector is negative.
const SCEV * getDistance(unsigned Level, bool SameSD=false) const override
getDistance - Returns the distance (or NULL) associated with a particular common or SameSD level.
DVEntry getDVEntry(unsigned Level, bool IsSameSD) const
getDVEntry - Returns the DV entry associated with a regular or a SameSD level.
bool isSplitable(unsigned Level, bool SameSD=false) const override
isSplitable - Returns true if splitting the loop will break the dependence.
bool isPeelLast(unsigned Level, bool SameSD=false) const override
isPeelLast - Returns true if peeling the last iteration from this regular or SameSD loop level will b...
bool isPeelFirst(unsigned Level, bool SameSD=false) const override
isPeelFirst - Returns true if peeling the first iteration from this regular or SameSD loop level will...
bool inSameSDLoops(unsigned Level) const override
inSameSDLoops - Returns true if this level is an SameSD level, i.e., performed across two separate lo...
bool normalize(ScalarEvolution *SE) override
If the direction vector is negative, normalize the direction vector to make it non-negative.
FunctionPass class - This class is used to implement most global optimizations.
unsigned getBitWidth() const
Get the number of bits in this IntegerType.
An instruction for reading from memory.
Analysis pass that exposes the LoopInfo for a function.
BlockT * getLoopLatch() const
If there is a single latch block for this loop, return it.
const LoopT * getOutermostLoop() const
Get the outermost loop in which this loop is contained.
unsigned getLoopDepth() const
Return the nesting level of this loop.
LoopT * getParentLoop() const
Return the parent loop if it exists or nullptr for top level loops.
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
The legacy pass manager's analysis pass to compute loop information.
This class represents a loop nest and can be used to query its properties.
Represents a single loop in the control flow graph.
Representation for a specific memory location.
static LLVM_ABI MemoryLocation get(const LoadInst *LI)
Return a location with information about the memory reference by the given instruction.
LocationSize Size
The maximum size of the location, in address-units, or UnknownSize if the size is not known.
static MemoryLocation getBeforeOrAfter(const Value *Ptr, const AAMDNodes &AATags=AAMDNodes())
Return a location that may access any location before or after Ptr, while remaining within the underl...
AAMDNodes AATags
The metadata nodes which describes the aliasing of the location (each member is null if that kind of ...
const Value * Ptr
The address of the start of the location.
A Module instance is used to store all the information related to an LLVM module.
AnalysisType & getAnalysis() const
getAnalysis<AnalysisType>() - This function is used by subclasses to get to the analysis information ...
A set of analyses that are preserved following a run of a transformation pass.
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
PreservedAnalysisChecker getChecker() const
Build a checker for this PreservedAnalyses and the specified analysis type.
This node represents a polynomial recurrence on the trip count of the specified loop.
const SCEV * getStart() const
LLVM_ABI const SCEV * evaluateAtIteration(const SCEV *It, ScalarEvolution &SE) const
Return the value of this chain of recurrences at the specified iteration number.
const SCEV * getStepRecurrence(ScalarEvolution &SE) const
Constructs and returns the recurrence indicating how much this expression steps by.
bool isAffine() const
Return true if this represents an expression A + B*x where A and B are loop invariant values.
const Loop * getLoop() const
const SCEV * getOperand() const
This class represents a constant integer value.
const APInt & getAPInt() const
bool hasNoSignedWrap() const
NoWrapFlags getNoWrapFlags(NoWrapFlags Mask=NoWrapMask) const
const SCEV * getOperand(unsigned i) const
This class represents an assumption made using SCEV expressions which can be checked at run-time.
This class represents a composition of other SCEV predicates, and is the class that most clients will...
void print(raw_ostream &OS, unsigned Depth) const override
Prints a textual representation of this predicate with an indentation of Depth.
bool isAlwaysTrue() const override
Implementation of the SCEVPredicate interface.
This class represents an analyzed expression in the program.
LLVM_ABI ArrayRef< const SCEV * > operands() const
Return operands of this SCEV expression.
LLVM_ABI bool isOne() const
Return true if the expression is a constant one.
LLVM_ABI bool isZero() const
Return true if the expression is a constant zero.
LLVM_ABI Type * getType() const
Return the LLVM type of this SCEV expression.
Analysis pass that exposes the ScalarEvolution for a function.
The main scalar evolution driver.
LLVM_ABI const SCEV * getNegativeSCEV(const SCEV *V, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap)
Return the SCEV object corresponding to -V.
LLVM_ABI const SCEV * removePointerBase(const SCEV *S)
Compute an expression equivalent to S - getPointerBase(S).
LLVM_ABI const SCEV * getSCEVAtScope(const SCEV *S, const Loop *L)
Return a SCEV expression for the specified value at the specified scope in the program.
LLVM_ABI bool willNotOverflow(Instruction::BinaryOps BinOp, bool Signed, const SCEV *LHS, const SCEV *RHS, const Instruction *CtxI=nullptr)
Is operation BinOp between LHS and RHS provably does not have a signed/unsigned overflow (Signed)?
LLVM_ABI const SCEV * getMinusSCEV(const SCEV *LHS, const SCEV *RHS, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
Return LHS-RHS.
This is a 'bitvector' (really, a variable-sized bit array), optimized for the case when the array is ...
iterator_range< const_set_bits_iterator > set_bits() const
int find_next(unsigned Prev) const
Returns the index of the next set bit following the "Prev" bit.
bool any() const
Returns true if any bit is set.
bool empty() const
Tests whether there are no bits in this bitvector.
size_type count() const
Returns the number of bits which are set.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
An instruction for storing to memory.
The instances of the Type class are immutable: once they are created, they are never changed.
bool isIntegerTy() const
True if this is an instance of IntegerType.
LLVM Value Representation.
This class implements an extremely fast bulk output stream that can only output to a stream.
raw_ostream & indent(unsigned NumSpaces)
indent - Insert 'NumSpaces' spaces.
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
Abstract Attribute helper functions.
const APInt & smin(const APInt &A, const APInt &B)
Determine the smaller of two APInts considered to be signed.
const APInt & smax(const APInt &A, const APInt &B)
Determine the larger of two APInts considered to be signed.
LLVM_ABI APInt GreatestCommonDivisor(APInt A, APInt B)
Compute GCD of two unsigned APInt values.
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
@ C
The default llvm calling convention, compatible with C.
@ BasicBlock
Various leaf nodes.
@ TB
TB - TwoByte - Set if this instruction has a two byte opcode, which starts with a 0x0F byte before th...
ValuesClass values(OptsTy... Options)
Helper to build a ValuesClass by forwarding a variable number of arguments as an initializer list to ...
initializer< Ty > init(const Ty &Val)
This is an optimization pass for GlobalISel generic memory operations.
void dump(const SparseBitVector< ElementSize > &LHS, raw_ostream &out)
FunctionAddr VTableAddr Value
InstIterator< SymbolTableList< BasicBlock >, Function::iterator, BasicBlock::iterator, Instruction > inst_iterator
void collectParametricTerms(ScalarEvolution &SE, const SCEV *Expr, SmallVectorImpl< const SCEV * > &Terms)
Collect parametric terms occurring in step expressions (first step of delinearization).
void findArrayDimensions(ScalarEvolution &SE, SmallVectorImpl< const SCEV * > &Terms, SmallVectorImpl< const SCEV * > &Sizes, const SCEV *ElementSize)
Compute the array dimensions Sizes from the set of Terms extracted from the memory access function of...
decltype(auto) dyn_cast(const From &Val)
dyn_cast<X> - Return the argument parameter cast to the specified type.
const Value * getLoadStorePointerOperand(const Value *V)
A helper function that returns the pointer operand of a load or store instruction.
inst_iterator inst_begin(Function *F)
void computeAccessFunctions(ScalarEvolution &SE, const SCEV *Expr, SmallVectorImpl< const SCEV * > &Subscripts, SmallVectorImpl< const SCEV * > &Sizes)
Return in Subscripts the access functions for each dimension in Sizes (third step of delinearization)...
LLVM_ABI raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
class LLVM_GSL_OWNER SmallVector
Forward declaration of SmallVector so that calculateSmallVectorDefaultInlinedElements can reference s...
bool isa(const From &Val)
isa<X> - Return true if the parameter to the template is an instance of one of the template type argu...
inst_iterator inst_end(Function *F)
bool tryDelinearizeFixedSizeImpl(ScalarEvolution *SE, Instruction *Inst, const SCEV *AccessFn, SmallVectorImpl< const SCEV * > &Subscripts, SmallVectorImpl< int > &Sizes)
Implementation of fixed size array delinearization.
constexpr unsigned BitWidth
decltype(auto) cast(const From &Val)
cast<X> - Return the argument parameter cast to the specified type.
AnalysisManager< Function > FunctionAnalysisManager
Convenience typedef for the Function analysis manager.
LLVM_ABI const Value * getUnderlyingObject(const Value *V, unsigned MaxLookup=MaxLookupSearchDepth)
This method strips off any GEP address adjustments, pointer casts or llvm.threadlocal....
LLVM_ABI bool isKnownNonNegative(const Value *V, const SimplifyQuery &SQ, unsigned Depth=0)
Returns true if the give value is known to be non-negative.
LLVM_ABI bool isIdentifiedObject(const Value *V)
Return true if this pointer refers to a distinct and identifiable object.
LLVM_ABI FunctionPass * createDependenceAnalysisWrapperPass()
createDependenceAnalysisPass - This creates an instance of the DependenceAnalysis wrapper pass.
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
A special type used by analysis passes to provide an address that identifies that particular analysis...
LLVM_ABI PreservedAnalyses run(Function &F, FunctionAnalysisManager &FAM)
Dependence::DVEntry - Each level in the distance/direction vector has a direction (or perhaps a union...
This class defines a simple visitor class that may be used for various SCEV analysis purposes.