70 #define DEBUG_TYPE "da"
75 STATISTIC(TotalArrayPairs,
"Array pairs tested");
76 STATISTIC(SeparableSubscriptPairs,
"Separable subscript pairs");
77 STATISTIC(CoupledSubscriptPairs,
"Coupled subscript pairs");
78 STATISTIC(NonlinearSubscriptPairs,
"Nonlinear subscript pairs");
79 STATISTIC(ZIVapplications,
"ZIV applications");
80 STATISTIC(ZIVindependence,
"ZIV independence");
81 STATISTIC(StrongSIVapplications,
"Strong SIV applications");
82 STATISTIC(StrongSIVsuccesses,
"Strong SIV successes");
83 STATISTIC(StrongSIVindependence,
"Strong SIV independence");
84 STATISTIC(WeakCrossingSIVapplications,
"Weak-Crossing SIV applications");
85 STATISTIC(WeakCrossingSIVsuccesses,
"Weak-Crossing SIV successes");
86 STATISTIC(WeakCrossingSIVindependence,
"Weak-Crossing SIV independence");
87 STATISTIC(ExactSIVapplications,
"Exact SIV applications");
88 STATISTIC(ExactSIVsuccesses,
"Exact SIV successes");
89 STATISTIC(ExactSIVindependence,
"Exact SIV independence");
90 STATISTIC(WeakZeroSIVapplications,
"Weak-Zero SIV applications");
91 STATISTIC(WeakZeroSIVsuccesses,
"Weak-Zero SIV successes");
92 STATISTIC(WeakZeroSIVindependence,
"Weak-Zero SIV independence");
93 STATISTIC(ExactRDIVapplications,
"Exact RDIV applications");
94 STATISTIC(ExactRDIVindependence,
"Exact RDIV independence");
95 STATISTIC(SymbolicRDIVapplications,
"Symbolic RDIV applications");
96 STATISTIC(SymbolicRDIVindependence,
"Symbolic RDIV independence");
97 STATISTIC(DeltaApplications,
"Delta applications");
98 STATISTIC(DeltaSuccesses,
"Delta successes");
99 STATISTIC(DeltaIndependence,
"Delta independence");
100 STATISTIC(DeltaPropagations,
"Delta propagations");
101 STATISTIC(GCDapplications,
"GCD applications");
102 STATISTIC(GCDsuccesses,
"GCD successes");
103 STATISTIC(GCDindependence,
"GCD independence");
104 STATISTIC(BanerjeeApplications,
"Banerjee applications");
105 STATISTIC(BanerjeeIndependence,
"Banerjee independence");
106 STATISTIC(BanerjeeSuccesses,
"Banerjee successes");
110 cl::desc(
"Try to delinearize array references."));
112 "da-disable-delinearization-checks",
cl::Hidden,
114 "Disable checks that try to statically verify validity of "
115 "delinearized subscripts. Enabling this option may result in incorrect "
116 "dependence vectors for languages that allow the subscript of one "
117 "dimension to underflow or overflow into another dimension."));
121 cl::desc(
"Maximum depth allowed for the recursive algorithm used to "
122 "explore MIV direction vectors."));
138 "Dependence Analysis",
true,
true)
157 auto &AA = getAnalysis<AAResultsWrapperPass>().getAAResults();
158 auto &SE = getAnalysis<ScalarEvolutionWrapperPass>().getSE();
159 auto &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
181 auto *
F =
DA->getFunction();
184 if (SrcI->mayReadOrWriteMemory()) {
186 DstI != DstE; ++DstI) {
187 if (DstI->mayReadOrWriteMemory()) {
188 OS <<
"Src:" << *SrcI <<
" --> Dst:" << *DstI <<
"\n";
189 OS <<
" da analyze - ";
190 if (
auto D =
DA->depends(&*SrcI, &*DstI,
true)) {
192 if (NormalizeResults &&
D->normalize(&SE))
193 OS <<
"normalized - ";
195 for (
unsigned Level = 1; Level <=
D->getLevels(); Level++) {
196 if (
D->isSplitable(Level)) {
197 OS <<
" da analyze - split level = " << Level;
198 OS <<
", iteration = " << *
DA->getSplitIteration(*
D, Level);
214 getAnalysis<ScalarEvolutionWrapperPass>().getSE(),
false);
219 OS <<
"'Dependence Analysis' for function '" <<
F.getName() <<
"':\n";
266 bool PossiblyLoopIndependent,
267 unsigned CommonLevels)
269 LoopIndependent(PossiblyLoopIndependent) {
272 DV = std::make_unique<DVEntry[]>(CommonLevels);
291 for (
unsigned Level = 1; Level <= Levels; ++Level) {
292 unsigned char Direction = DV[Level - 1].Direction;
307 LLVM_DEBUG(
dbgs() <<
"Before normalizing negative direction vectors:\n";
310 for (
unsigned Level = 1; Level <= Levels; ++Level) {
311 unsigned char Direction = DV[Level - 1].Direction;
319 DV[Level - 1].Direction = RevDirection;
321 if (DV[Level - 1].Distance !=
nullptr)
322 DV[Level - 1].Distance =
326 LLVM_DEBUG(
dbgs() <<
"After normalizing negative direction vectors:\n";
335 assert(0 < Level && Level <= Levels &&
"Level out of range");
336 return DV[Level - 1].Direction;
342 assert(0 < Level && Level <= Levels &&
"Level out of range");
343 return DV[Level - 1].Distance;
351 assert(0 < Level && Level <= Levels &&
"Level out of range");
352 return DV[Level - 1].Scalar;
359 assert(0 < Level && Level <= Levels &&
"Level out of range");
360 return DV[Level - 1].PeelFirst;
367 assert(0 < Level && Level <= Levels &&
"Level out of range");
368 return DV[Level - 1].PeelLast;
374 assert(0 < Level && Level <= Levels &&
"Level out of range");
375 return DV[Level - 1].Splitable;
384 const SCEV *DependenceInfo::Constraint::getX()
const {
385 assert(Kind == Point &&
"Kind should be Point");
392 const SCEV *DependenceInfo::Constraint::getY()
const {
393 assert(Kind == Point &&
"Kind should be Point");
400 const SCEV *DependenceInfo::Constraint::getA()
const {
401 assert((Kind == Line || Kind == Distance) &&
402 "Kind should be Line (or Distance)");
409 const SCEV *DependenceInfo::Constraint::getB()
const {
410 assert((Kind == Line || Kind == Distance) &&
411 "Kind should be Line (or Distance)");
418 const SCEV *DependenceInfo::Constraint::getC()
const {
419 assert((Kind == Line || Kind == Distance) &&
420 "Kind should be Line (or Distance)");
427 const SCEV *DependenceInfo::Constraint::getD()
const {
428 assert(Kind == Distance &&
"Kind should be Distance");
429 return SE->getNegativeSCEV(
C);
434 const Loop *DependenceInfo::Constraint::getAssociatedLoop()
const {
435 assert((Kind == Distance || Kind == Line || Kind == Point) &&
436 "Kind should be Distance, Line, or Point");
437 return AssociatedLoop;
440 void DependenceInfo::Constraint::setPoint(
const SCEV *
X,
const SCEV *
Y,
441 const Loop *CurLoop) {
445 AssociatedLoop = CurLoop;
448 void DependenceInfo::Constraint::setLine(
const SCEV *AA,
const SCEV *
BB,
454 AssociatedLoop = CurLoop;
457 void DependenceInfo::Constraint::setDistance(
const SCEV *
D,
458 const Loop *CurLoop) {
460 A = SE->getOne(
D->getType());
461 B = SE->getNegativeSCEV(A);
462 C = SE->getNegativeSCEV(
D);
463 AssociatedLoop = CurLoop;
466 void DependenceInfo::Constraint::setEmpty() {
Kind =
Empty; }
473 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
481 OS <<
" Point is <" << *getX() <<
", " << *getY() <<
">\n";
482 else if (isDistance())
483 OS <<
" Distance is " << *getD() <<
484 " (" << *getA() <<
"*X + " << *getB() <<
"*Y = " << *getC() <<
")\n";
486 OS <<
" Line is " << *getA() <<
"*X + " <<
487 *getB() <<
"*Y = " << *getC() <<
"\n";
501 bool DependenceInfo::intersectConstraints(Constraint *
X,
const Constraint *
Y) {
506 assert(!
Y->isPoint() &&
"Y must not be a Point");
520 if (
X->isDistance() &&
Y->isDistance()) {
531 if (isa<SCEVConstant>(
Y->getD())) {
544 assert(!(
X->isPoint() &&
Y->isPoint()) &&
545 "We shouldn't ever see X->isPoint() && Y->isPoint()");
547 if (
X->isLine() &&
Y->isLine()) {
582 if (!C1B2_C2B1 || !C1A2_C2A1 ||
583 !A1B2_A2B1 || !A2B1_A1B2)
599 if (Xr != 0 || Yr != 0) {
605 if (Xq.
slt(0) || Yq.
slt(0)) {
611 collectConstantUpperBound(
X->getAssociatedLoop(), Prod1->
getType())) {
612 const APInt &UpperBound = CUB->getAPInt();
614 if (Xq.
sgt(UpperBound) || Yq.
sgt(UpperBound)) {
622 X->getAssociatedLoop());
630 assert(!(
X->isLine() &&
Y->isPoint()) &&
"This case should never occur");
632 if (
X->isPoint() &&
Y->isLine()) {
657 bool Splitable =
false;
673 for (
unsigned II = 1; II <= Levels; ++II) {
751 if (
const LoadInst *LI = dyn_cast<LoadInst>(
I))
752 return LI->isUnordered();
754 return SI->isUnordered();
809 void DependenceInfo::establishNestingLevels(
const Instruction *Src,
811 const BasicBlock *SrcBlock = Src->getParent();
812 const BasicBlock *DstBlock = Dst->getParent();
817 SrcLevels = SrcLevel;
818 MaxLevels = SrcLevel + DstLevel;
819 while (SrcLevel > DstLevel) {
823 while (DstLevel > SrcLevel) {
827 while (SrcLoop != DstLoop) {
832 CommonLevels = SrcLevel;
833 MaxLevels -= CommonLevels;
839 unsigned DependenceInfo::mapSrcLoop(
const Loop *SrcLoop)
const {
846 unsigned DependenceInfo::mapDstLoop(
const Loop *DstLoop)
const {
848 if (
D > CommonLevels)
851 return D - CommonLevels + SrcLevels;
889 unsigned widestWidthSeen = 0;
894 for (Subscript *Pair : Pairs) {
895 const SCEV *Src = Pair->Src;
896 const SCEV *Dst = Pair->Dst;
897 IntegerType *SrcTy = dyn_cast<IntegerType>(Src->getType());
898 IntegerType *DstTy = dyn_cast<IntegerType>(Dst->getType());
899 if (SrcTy ==
nullptr || DstTy ==
nullptr) {
900 assert(SrcTy == DstTy &&
"This function only unify integer types and "
901 "expect Src and Dst share the same type "
916 assert(widestWidthSeen > 0);
919 for (Subscript *Pair : Pairs) {
920 const SCEV *Src = Pair->Src;
921 const SCEV *Dst = Pair->Dst;
922 IntegerType *SrcTy = dyn_cast<IntegerType>(Src->getType());
923 IntegerType *DstTy = dyn_cast<IntegerType>(Dst->getType());
924 if (SrcTy ==
nullptr || DstTy ==
nullptr) {
925 assert(SrcTy == DstTy &&
"This function only unify integer types and "
926 "expect Src and Dst share the same type "
944 void DependenceInfo::removeMatchingExtensions(Subscript *Pair) {
945 const SCEV *Src = Pair->Src;
946 const SCEV *Dst = Pair->Dst;
947 if ((isa<SCEVZeroExtendExpr>(Src) && isa<SCEVZeroExtendExpr>(Dst)) ||
948 (isa<SCEVSignExtendExpr>(Src) && isa<SCEVSignExtendExpr>(Dst))) {
954 Pair->Src = SrcCastOp;
955 Pair->Dst = DstCastOp;
966 return isLoopInvariant(Expr,
LoopNest);
974 while (L && AddRec->
getLoop() != L)
982 if (!isa<SCEVCouldNotCompute>(UB)) {
989 if (!isLoopInvariant(Step,
LoopNest))
1000 bool DependenceInfo::checkSrcSubscript(
const SCEV *Src,
const Loop *
LoopNest,
1007 bool DependenceInfo::checkDstSubscript(
const SCEV *Dst,
const Loop *
LoopNest,
1016 DependenceInfo::Subscript::ClassificationKind
1017 DependenceInfo::classifyPair(
const SCEV *Src,
const Loop *SrcLoopNest,
1018 const SCEV *Dst,
const Loop *DstLoopNest,
1022 if (!checkSrcSubscript(Src, SrcLoopNest, SrcLoops))
1023 return Subscript::NonLinear;
1024 if (!checkDstSubscript(Dst, DstLoopNest, DstLoops))
1025 return Subscript::NonLinear;
1028 unsigned N =
Loops.count();
1030 return Subscript::ZIV;
1032 return Subscript::SIV;
1033 if (
N == 2 && (SrcLoops.count() == 0 ||
1034 DstLoops.count() == 0 ||
1035 (SrcLoops.count() == 1 && DstLoops.count() == 1)))
1036 return Subscript::RDIV;
1037 return Subscript::MIV;
1052 const SCEV *
Y)
const {
1055 if ((isa<SCEVSignExtendExpr>(
X) &&
1056 isa<SCEVSignExtendExpr>(
Y)) ||
1057 (isa<SCEVZeroExtendExpr>(
X) &&
1058 isa<SCEVZeroExtendExpr>(
Y))) {
1098 bool DependenceInfo::isKnownLessThan(
const SCEV *
S,
const SCEV *Size)
const {
1100 auto *SType = dyn_cast<IntegerType>(
S->getType());
1101 auto *SizeType = dyn_cast<IntegerType>(
Size->getType());
1102 if (!SType || !SizeType)
1105 (SType->getBitWidth() >= SizeType->getBitWidth()) ? SType : SizeType;
1111 if (
const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(Bound)) {
1114 if (!isa<SCEVCouldNotCompute>(BECount)) {
1123 const SCEV *LimitedBound =
1128 bool DependenceInfo::isKnownNonNegative(
const SCEV *
S,
const Value *
Ptr)
const {
1129 bool Inbounds =
false;
1130 if (
auto *SrcGEP = dyn_cast<GetElementPtrInst>(
Ptr))
1131 Inbounds = SrcGEP->isInBounds();
1154 const SCEV *DependenceInfo::collectUpperBound(
const Loop *L,
Type *
T)
const {
1165 const SCEVConstant *DependenceInfo::collectConstantUpperBound(
const Loop *L,
1167 if (
const SCEV *UB = collectUpperBound(L,
T))
1168 return dyn_cast<SCEVConstant>(UB);
1183 bool DependenceInfo::testZIV(
const SCEV *Src,
const SCEV *Dst,
1198 Result.Consistent =
false;
1230 bool DependenceInfo::strongSIVtest(
const SCEV *Coeff,
const SCEV *SrcConst,
1231 const SCEV *DstConst,
const Loop *CurLoop,
1233 Constraint &NewConstraint)
const {
1241 ++StrongSIVapplications;
1242 assert(0 < Level && Level <= CommonLevels &&
"level out of range");
1250 if (
const SCEV *UpperBound = collectUpperBound(CurLoop, Delta->
getType())) {
1253 const SCEV *AbsDelta =
1255 const SCEV *AbsCoeff =
1260 ++StrongSIVindependence;
1261 ++StrongSIVsuccesses;
1267 if (isa<SCEVConstant>(Delta) && isa<SCEVConstant>(Coeff)) {
1268 APInt ConstDelta = cast<SCEVConstant>(Delta)->getAPInt();
1269 APInt ConstCoeff = cast<SCEVConstant>(Coeff)->getAPInt();
1270 APInt Distance = ConstDelta;
1271 APInt Remainder = ConstDelta;
1276 if (Remainder != 0) {
1278 ++StrongSIVindependence;
1279 ++StrongSIVsuccesses;
1283 NewConstraint.setDistance(SE->
getConstant(Distance), CurLoop);
1284 if (Distance.
sgt(0))
1286 else if (Distance.
slt(0))
1290 ++StrongSIVsuccesses;
1292 else if (Delta->
isZero()) {
1295 NewConstraint.setDistance(Delta, CurLoop);
1297 ++StrongSIVsuccesses;
1300 if (Coeff->
isOne()) {
1303 NewConstraint.setDistance(Delta, CurLoop);
1306 Result.Consistent =
false;
1307 NewConstraint.setLine(Coeff,
1322 if ((DeltaMaybePositive && CoeffMaybePositive) ||
1323 (DeltaMaybeNegative && CoeffMaybeNegative))
1327 if ((DeltaMaybeNegative && CoeffMaybePositive) ||
1328 (DeltaMaybePositive && CoeffMaybeNegative))
1330 if (NewDirection <
Result.DV[Level].Direction)
1331 ++StrongSIVsuccesses;
1366 bool DependenceInfo::weakCrossingSIVtest(
1367 const SCEV *Coeff,
const SCEV *SrcConst,
const SCEV *DstConst,
1369 Constraint &NewConstraint,
const SCEV *&SplitIter)
const {
1374 ++WeakCrossingSIVapplications;
1375 assert(0 < Level && Level <= CommonLevels &&
"Level out of range");
1377 Result.Consistent =
false;
1380 NewConstraint.setLine(Coeff, Coeff, Delta, CurLoop);
1384 ++WeakCrossingSIVsuccesses;
1385 if (!
Result.DV[Level].Direction) {
1386 ++WeakCrossingSIVindependence;
1392 const SCEVConstant *ConstCoeff = dyn_cast<SCEVConstant>(Coeff);
1400 "dynamic cast of negative of ConstCoeff should yield constant");
1411 const SCEVConstant *ConstDelta = dyn_cast<SCEVConstant>(Delta);
1421 ++WeakCrossingSIVindependence;
1422 ++WeakCrossingSIVsuccesses;
1428 if (
const SCEV *UpperBound = collectUpperBound(CurLoop, Delta->
getType())) {
1436 ++WeakCrossingSIVindependence;
1437 ++WeakCrossingSIVsuccesses;
1444 ++WeakCrossingSIVsuccesses;
1445 if (!
Result.DV[Level].Direction) {
1446 ++WeakCrossingSIVindependence;
1458 APInt Distance = APDelta;
1459 APInt Remainder = APDelta;
1462 if (Remainder != 0) {
1464 ++WeakCrossingSIVindependence;
1465 ++WeakCrossingSIVsuccesses;
1472 Remainder = Distance.
srem(Two);
1474 if (Remainder != 0) {
1477 ++WeakCrossingSIVsuccesses;
1503 APInt A2 = A0 - Q*A1; A0 = A1; A1 = A2;
1504 APInt B2 = B0 - Q*B1; B0 = B1; B1 = B2;
1510 X = AM.
slt(0) ? -A1 : A1;
1511 Y = BM.
slt(0) ? B1 : -B1;
1527 if ((A.sgt(0) &&
B.sgt(0)) ||
1528 (A.slt(0) &&
B.slt(0)))
1540 if ((A.sgt(0) &&
B.sgt(0)) ||
1541 (A.slt(0) &&
B.slt(0)))
1566 bool DependenceInfo::exactSIVtest(
const SCEV *SrcCoeff,
const SCEV *DstCoeff,
1567 const SCEV *SrcConst,
const SCEV *DstConst,
1568 const Loop *CurLoop,
unsigned Level,
1570 Constraint &NewConstraint)
const {
1572 LLVM_DEBUG(
dbgs() <<
"\t SrcCoeff = " << *SrcCoeff <<
" = AM\n");
1573 LLVM_DEBUG(
dbgs() <<
"\t DstCoeff = " << *DstCoeff <<
" = BM\n");
1576 ++ExactSIVapplications;
1577 assert(0 < Level && Level <= CommonLevels &&
"Level out of range");
1579 Result.Consistent =
false;
1584 const SCEVConstant *ConstDelta = dyn_cast<SCEVConstant>(Delta);
1585 const SCEVConstant *ConstSrcCoeff = dyn_cast<SCEVConstant>(SrcCoeff);
1586 const SCEVConstant *ConstDstCoeff = dyn_cast<SCEVConstant>(DstCoeff);
1587 if (!ConstDelta || !ConstSrcCoeff || !ConstDstCoeff)
1598 ++ExactSIVindependence;
1599 ++ExactSIVsuccesses;
1607 bool UMValid =
false;
1610 collectConstantUpperBound(CurLoop, Delta->
getType())) {
1611 UM = CUB->getAPInt();
1629 LLVM_DEBUG(
dbgs() <<
"\t Possible TL = " << TLVec.back() <<
"\n");
1633 LLVM_DEBUG(
dbgs() <<
"\t Possible TU = " << TUVec.back() <<
"\n");
1637 LLVM_DEBUG(
dbgs() <<
"\t Possible TU = " << TUVec.back() <<
"\n");
1641 LLVM_DEBUG(
dbgs() <<
"\t Possible TL = " << TLVec.back() <<
"\n");
1649 LLVM_DEBUG(
dbgs() <<
"\t Possible TU = " << TUVec.back() <<
"\n");
1653 LLVM_DEBUG(
dbgs() <<
"\t Possible TL = " << TLVec.back() <<
"\n");
1657 LLVM_DEBUG(
dbgs() <<
"\t Possible TL = " << TLVec.back() <<
"\n");
1661 LLVM_DEBUG(
dbgs() <<
"\t Possible TU = " << TUVec.back() <<
"\n");
1667 if (TLVec.empty() || TUVec.empty())
1675 ++ExactSIVindependence;
1676 ++ExactSIVsuccesses;
1682 APInt LowerDistance, UpperDistance;
1684 LowerDistance = (TY - TX) + (
TA -
TB) * TL;
1685 UpperDistance = (TY - TX) + (
TA -
TB) * TU;
1687 LowerDistance = (TY - TX) + (
TA -
TB) * TU;
1688 UpperDistance = (TY - TX) + (
TA -
TB) * TL;
1691 LLVM_DEBUG(
dbgs() <<
"\t LowerDistance = " << LowerDistance <<
"\n");
1692 LLVM_DEBUG(
dbgs() <<
"\t UpperDistance = " << UpperDistance <<
"\n");
1695 if (LowerDistance.
sle(Zero) && UpperDistance.
sge(Zero)) {
1697 ++ExactSIVsuccesses;
1699 if (LowerDistance.
slt(0)) {
1701 ++ExactSIVsuccesses;
1703 if (UpperDistance.
sgt(0)) {
1705 ++ExactSIVsuccesses;
1711 ++ExactSIVindependence;
1724 return ConstDividend.
srem(ConstDivisor) == 0;
1759 bool DependenceInfo::weakZeroSrcSIVtest(
const SCEV *DstCoeff,
1760 const SCEV *SrcConst,
1761 const SCEV *DstConst,
1762 const Loop *CurLoop,
unsigned Level,
1764 Constraint &NewConstraint)
const {
1772 ++WeakZeroSIVapplications;
1773 assert(0 < Level && Level <= MaxLevels &&
"Level out of range");
1775 Result.Consistent =
false;
1777 NewConstraint.setLine(SE->
getZero(Delta->
getType()), DstCoeff, Delta,
1781 if (Level < CommonLevels) {
1784 ++WeakZeroSIVsuccesses;
1788 const SCEVConstant *ConstCoeff = dyn_cast<SCEVConstant>(DstCoeff);
1791 const SCEV *AbsCoeff =
1794 const SCEV *NewDelta =
1799 if (
const SCEV *UpperBound = collectUpperBound(CurLoop, Delta->
getType())) {
1803 ++WeakZeroSIVindependence;
1804 ++WeakZeroSIVsuccesses;
1809 if (Level < CommonLevels) {
1812 ++WeakZeroSIVsuccesses;
1822 ++WeakZeroSIVindependence;
1823 ++WeakZeroSIVsuccesses;
1828 if (isa<SCEVConstant>(Delta) &&
1830 ++WeakZeroSIVindependence;
1831 ++WeakZeroSIVsuccesses;
1869 bool DependenceInfo::weakZeroDstSIVtest(
const SCEV *SrcCoeff,
1870 const SCEV *SrcConst,
1871 const SCEV *DstConst,
1872 const Loop *CurLoop,
unsigned Level,
1874 Constraint &NewConstraint)
const {
1881 ++WeakZeroSIVapplications;
1882 assert(0 < Level && Level <= SrcLevels &&
"Level out of range");
1884 Result.Consistent =
false;
1886 NewConstraint.setLine(SrcCoeff, SE->
getZero(Delta->
getType()), Delta,
1890 if (Level < CommonLevels) {
1893 ++WeakZeroSIVsuccesses;
1897 const SCEVConstant *ConstCoeff = dyn_cast<SCEVConstant>(SrcCoeff);
1900 const SCEV *AbsCoeff =
1903 const SCEV *NewDelta =
1908 if (
const SCEV *UpperBound = collectUpperBound(CurLoop, Delta->
getType())) {
1912 ++WeakZeroSIVindependence;
1913 ++WeakZeroSIVsuccesses;
1918 if (Level < CommonLevels) {
1921 ++WeakZeroSIVsuccesses;
1931 ++WeakZeroSIVindependence;
1932 ++WeakZeroSIVsuccesses;
1937 if (isa<SCEVConstant>(Delta) &&
1939 ++WeakZeroSIVindependence;
1940 ++WeakZeroSIVsuccesses;
1954 bool DependenceInfo::exactRDIVtest(
const SCEV *SrcCoeff,
const SCEV *DstCoeff,
1955 const SCEV *SrcConst,
const SCEV *DstConst,
1956 const Loop *SrcLoop,
const Loop *DstLoop,
1959 LLVM_DEBUG(
dbgs() <<
"\t SrcCoeff = " << *SrcCoeff <<
" = AM\n");
1960 LLVM_DEBUG(
dbgs() <<
"\t DstCoeff = " << *DstCoeff <<
" = BM\n");
1963 ++ExactRDIVapplications;
1964 Result.Consistent =
false;
1967 const SCEVConstant *ConstDelta = dyn_cast<SCEVConstant>(Delta);
1968 const SCEVConstant *ConstSrcCoeff = dyn_cast<SCEVConstant>(SrcCoeff);
1969 const SCEVConstant *ConstDstCoeff = dyn_cast<SCEVConstant>(DstCoeff);
1970 if (!ConstDelta || !ConstSrcCoeff || !ConstDstCoeff)
1981 ++ExactRDIVindependence;
1989 bool SrcUMvalid =
false;
1992 collectConstantUpperBound(SrcLoop, Delta->
getType())) {
1993 SrcUM = UpperBound->getAPInt();
1999 bool DstUMvalid =
false;
2002 collectConstantUpperBound(DstLoop, Delta->
getType())) {
2003 DstUM = UpperBound->getAPInt();
2021 LLVM_DEBUG(
dbgs() <<
"\t Possible TL = " << TLVec.back() <<
"\n");
2024 LLVM_DEBUG(
dbgs() <<
"\t Possible TU = " << TUVec.back() <<
"\n");
2028 LLVM_DEBUG(
dbgs() <<
"\t Possible TU = " << TUVec.back() <<
"\n");
2031 LLVM_DEBUG(
dbgs() <<
"\t Possible TL = " << TLVec.back() <<
"\n");
2038 LLVM_DEBUG(
dbgs() <<
"\t Possible TL = " << TLVec.back() <<
"\n");
2041 LLVM_DEBUG(
dbgs() <<
"\t Possible TU = " << TUVec.back() <<
"\n");
2045 LLVM_DEBUG(
dbgs() <<
"\t Possible TU = " << TUVec.back() <<
"\n");
2048 LLVM_DEBUG(
dbgs() <<
"\t Possible TL = " << TLVec.back() <<
"\n");
2052 if (TLVec.empty() || TUVec.empty())
2064 ++ExactRDIVindependence;
2111 bool DependenceInfo::symbolicRDIVtest(
const SCEV *A1,
const SCEV *A2,
2114 const Loop *Loop2)
const {
2115 ++SymbolicRDIVapplications;
2122 const SCEV *N1 = collectUpperBound(Loop1, A1->
getType());
2123 const SCEV *N2 = collectUpperBound(Loop2, A1->
getType());
2138 ++SymbolicRDIVindependence;
2147 ++SymbolicRDIVindependence;
2159 LLVM_DEBUG(
dbgs() <<
"\t A1*N1 - A2*N2 = " << *A1N1_A2N2 <<
"\n");
2161 ++SymbolicRDIVindependence;
2167 ++SymbolicRDIVindependence;
2180 LLVM_DEBUG(
dbgs() <<
"\t A1*N1 - A2*N2 = " << *A1N1_A2N2 <<
"\n");
2182 ++SymbolicRDIVindependence;
2188 ++SymbolicRDIVindependence;
2199 ++SymbolicRDIVindependence;
2208 ++SymbolicRDIVindependence;
2226 bool DependenceInfo::testSIV(
const SCEV *Src,
const SCEV *Dst,
unsigned &Level,
2228 const SCEV *&SplitIter)
const {
2233 if (SrcAddRec && DstAddRec) {
2240 "both loops in SIV should be same");
2241 Level = mapSrcLoop(CurLoop);
2243 if (SrcCoeff == DstCoeff)
2244 disproven = strongSIVtest(SrcCoeff, SrcConst, DstConst, CurLoop,
2245 Level, Result, NewConstraint);
2247 disproven = weakCrossingSIVtest(SrcCoeff, SrcConst, DstConst, CurLoop,
2248 Level, Result, NewConstraint, SplitIter);
2250 disproven = exactSIVtest(SrcCoeff, DstCoeff, SrcConst, DstConst, CurLoop,
2251 Level, Result, NewConstraint);
2253 gcdMIVtest(Src, Dst, Result) ||
2254 symbolicRDIVtest(SrcCoeff, DstCoeff, SrcConst, DstConst, CurLoop, CurLoop);
2259 const SCEV *DstConst = Dst;
2261 Level = mapSrcLoop(CurLoop);
2262 return weakZeroDstSIVtest(SrcCoeff, SrcConst, DstConst, CurLoop,
2263 Level, Result, NewConstraint) ||
2264 gcdMIVtest(Src, Dst, Result);
2269 const SCEV *SrcConst = Src;
2271 Level = mapDstLoop(CurLoop);
2272 return weakZeroSrcSIVtest(DstCoeff, SrcConst, DstConst,
2273 CurLoop, Level, Result, NewConstraint) ||
2274 gcdMIVtest(Src, Dst, Result);
2294 bool DependenceInfo::testRDIV(
const SCEV *Src,
const SCEV *Dst,
2302 const SCEV *SrcConst, *DstConst;
2303 const SCEV *SrcCoeff, *DstCoeff;
2304 const Loop *SrcLoop, *DstLoop;
2310 if (SrcAddRec && DstAddRec) {
2313 SrcLoop = SrcAddRec->
getLoop();
2316 DstLoop = DstAddRec->
getLoop();
2318 else if (SrcAddRec) {
2320 dyn_cast<SCEVAddRecExpr>(SrcAddRec->
getStart())) {
2321 SrcConst = tmpAddRec->getStart();
2322 SrcCoeff = tmpAddRec->getStepRecurrence(*SE);
2323 SrcLoop = tmpAddRec->getLoop();
2326 DstLoop = SrcAddRec->
getLoop();
2331 else if (DstAddRec) {
2333 dyn_cast<SCEVAddRecExpr>(DstAddRec->
getStart())) {
2334 DstConst = tmpAddRec->getStart();
2335 DstCoeff = tmpAddRec->getStepRecurrence(*SE);
2336 DstLoop = tmpAddRec->getLoop();
2339 SrcLoop = DstAddRec->
getLoop();
2346 return exactRDIVtest(SrcCoeff, DstCoeff,
2350 gcdMIVtest(Src, Dst, Result) ||
2351 symbolicRDIVtest(SrcCoeff, DstCoeff,
2360 bool DependenceInfo::testMIV(
const SCEV *Src,
const SCEV *Dst,
2365 Result.Consistent =
false;
2366 return gcdMIVtest(Src, Dst, Result) ||
2367 banerjeeMIVtest(Src, Dst,
Loops, Result);
2375 if (
const auto *
Constant = dyn_cast<SCEVConstant>(Expr))
2377 else if (
const auto *Product = dyn_cast<SCEVMulExpr>(Expr))
2378 if (
const auto *
Constant = dyn_cast<SCEVConstant>(Product->getOperand(0)))
2402 bool DependenceInfo::gcdMIVtest(
const SCEV *Src,
const SCEV *Dst,
2413 const SCEV *Coefficients = Src;
2415 dyn_cast<SCEVAddRecExpr>(Coefficients)) {
2426 const SCEV *SrcConst = Coefficients;
2434 dyn_cast<SCEVAddRecExpr>(Coefficients)) {
2445 const SCEV *DstConst = Coefficients;
2451 if (
const SCEVAddExpr *Sum = dyn_cast<SCEVAddExpr>(Delta)) {
2453 for (
unsigned Op = 0, Ops = Sum->getNumOperands();
Op < Ops;
Op++) {
2454 const SCEV *Operand = Sum->getOperand(
Op);
2455 if (isa<SCEVConstant>(Operand)) {
2457 Constant = cast<SCEVConstant>(Operand);
2459 else if (
const SCEVMulExpr *Product = dyn_cast<SCEVMulExpr>(Operand)) {
2467 ConstOpValue.
abs());
2477 if (ConstDelta == 0)
2481 APInt Remainder = ConstDelta.
srem(RunningGCD);
2482 if (Remainder != 0) {
2501 bool Improved =
false;
2504 dyn_cast<SCEVAddRecExpr>(Coefficients)) {
2507 RunningGCD = ExtraGCD;
2510 const SCEV *Inner = Src;
2511 while (RunningGCD != 1 && isa<SCEVAddRecExpr>(Inner)) {
2512 AddRec = cast<SCEVAddRecExpr>(Inner);
2514 if (CurLoop == AddRec->
getLoop())
2528 while (RunningGCD != 1 && isa<SCEVAddRecExpr>(Inner)) {
2529 AddRec = cast<SCEVAddRecExpr>(Inner);
2531 if (CurLoop == AddRec->
getLoop())
2555 if (RunningGCD != 0) {
2556 Remainder = ConstDelta.
srem(RunningGCD);
2558 if (Remainder != 0) {
2559 unsigned Level = mapSrcLoop(CurLoop);
2605 bool DependenceInfo::banerjeeMIVtest(
const SCEV *Src,
const SCEV *Dst,
2609 ++BanerjeeApplications;
2612 CoefficientInfo *
A = collectCoeffInfo(Src,
true, A0);
2615 CoefficientInfo *
B = collectCoeffInfo(Dst,
false, B0);
2616 BoundInfo *Bound =
new BoundInfo[MaxLevels + 1];
2622 for (
unsigned K = 1; K <= MaxLevels; ++K) {
2623 Bound[K].Iterations =
A[K].Iterations ?
A[K].Iterations :
B[K].Iterations;
2626 findBoundsALL(A,
B, Bound, K);
2641 bool Disproved =
false;
2644 unsigned DepthExpanded = 0;
2645 unsigned NewDeps = exploreDirections(1, A,
B, Bound,
2646 Loops, DepthExpanded, Delta);
2648 bool Improved =
false;
2649 for (
unsigned K = 1; K <= CommonLevels; ++K) {
2651 unsigned Old =
Result.DV[K - 1].Direction;
2652 Result.DV[K - 1].Direction = Old & Bound[K].DirSet;
2653 Improved |= Old !=
Result.DV[K - 1].Direction;
2654 if (!
Result.DV[K - 1].Direction) {
2662 ++BanerjeeSuccesses;
2665 ++BanerjeeIndependence;
2670 ++BanerjeeIndependence;
2685 unsigned DependenceInfo::exploreDirections(
unsigned Level, CoefficientInfo *A,
2686 CoefficientInfo *
B, BoundInfo *Bound,
2688 unsigned &DepthExpanded,
2689 const SCEV *Delta)
const {
2695 LLVM_DEBUG(
dbgs() <<
"Number of common levels exceeded the threshold. MIV "
2696 "direction exploration is terminated.\n");
2697 for (
unsigned K = 1; K <= CommonLevels; ++K)
2703 if (Level > CommonLevels) {
2706 for (
unsigned K = 1; K <= CommonLevels; ++K) {
2708 Bound[K].DirSet |= Bound[K].Direction;
2733 if (Level > DepthExpanded) {
2734 DepthExpanded =
Level;
2736 findBoundsLT(A,
B, Bound, Level);
2737 findBoundsGT(A,
B, Bound, Level);
2738 findBoundsEQ(A,
B, Bound, Level);
2777 unsigned NewDeps = 0;
2781 NewDeps += exploreDirections(Level + 1, A,
B, Bound,
2782 Loops, DepthExpanded, Delta);
2786 NewDeps += exploreDirections(Level + 1, A,
B, Bound,
2787 Loops, DepthExpanded, Delta);
2791 NewDeps += exploreDirections(Level + 1, A,
B, Bound,
2792 Loops, DepthExpanded, Delta);
2798 return exploreDirections(Level + 1, A,
B, Bound,
Loops, DepthExpanded, Delta);
2803 bool DependenceInfo::testBounds(
unsigned char DirKind,
unsigned Level,
2804 BoundInfo *Bound,
const SCEV *Delta)
const {
2805 Bound[
Level].Direction = DirKind;
2806 if (
const SCEV *LowerBound = getLowerBound(Bound))
2809 if (
const SCEV *UpperBound = getUpperBound(Bound))
2831 void DependenceInfo::findBoundsALL(CoefficientInfo *A, CoefficientInfo *
B,
2832 BoundInfo *Bound,
unsigned K)
const {
2835 if (Bound[K].Iterations) {
2838 Bound[K].Iterations);
2841 Bound[K].Iterations);
2870 void DependenceInfo::findBoundsEQ(CoefficientInfo *A, CoefficientInfo *
B,
2871 BoundInfo *Bound,
unsigned K)
const {
2874 if (Bound[K].Iterations) {
2876 const SCEV *NegativePart = getNegativePart(Delta);
2878 SE->
getMulExpr(NegativePart, Bound[K].Iterations);
2879 const SCEV *PositivePart = getPositivePart(Delta);
2881 SE->
getMulExpr(PositivePart, Bound[K].Iterations);
2887 const SCEV *NegativePart = getNegativePart(Delta);
2888 if (NegativePart->
isZero())
2890 const SCEV *PositivePart = getPositivePart(Delta);
2891 if (PositivePart->
isZero())
2910 void DependenceInfo::findBoundsLT(CoefficientInfo *A, CoefficientInfo *
B,
2911 BoundInfo *Bound,
unsigned K)
const {
2914 if (Bound[K].Iterations) {
2916 Bound[K].Iterations, SE->
getOne(Bound[K].Iterations->getType()));
2917 const SCEV *NegPart =
2918 getNegativePart(SE->
getMinusSCEV(A[K].NegPart,
B[K].Coeff));
2921 const SCEV *PosPart =
2922 getPositivePart(SE->
getMinusSCEV(A[K].PosPart,
B[K].Coeff));
2929 const SCEV *NegPart =
2930 getNegativePart(SE->
getMinusSCEV(A[K].NegPart,
B[K].Coeff));
2933 const SCEV *PosPart =
2934 getPositivePart(SE->
getMinusSCEV(A[K].PosPart,
B[K].Coeff));
2954 void DependenceInfo::findBoundsGT(CoefficientInfo *A, CoefficientInfo *
B,
2955 BoundInfo *Bound,
unsigned K)
const {
2958 if (Bound[K].Iterations) {
2960 Bound[K].Iterations, SE->
getOne(Bound[K].Iterations->getType()));
2961 const SCEV *NegPart =
2962 getNegativePart(SE->
getMinusSCEV(A[K].Coeff,
B[K].PosPart));
2965 const SCEV *PosPart =
2966 getPositivePart(SE->
getMinusSCEV(A[K].Coeff,
B[K].NegPart));
2973 const SCEV *NegPart = getNegativePart(SE->
getMinusSCEV(A[K].Coeff,
B[K].PosPart));
2976 const SCEV *PosPart = getPositivePart(SE->
getMinusSCEV(A[K].Coeff,
B[K].NegPart));
2984 const SCEV *DependenceInfo::getPositivePart(
const SCEV *
X)
const {
2990 const SCEV *DependenceInfo::getNegativePart(
const SCEV *
X)
const {
2998 DependenceInfo::CoefficientInfo *
2999 DependenceInfo::collectCoeffInfo(
const SCEV *Subscript,
bool SrcFlag,
3002 CoefficientInfo *CI =
new CoefficientInfo[MaxLevels + 1];
3003 for (
unsigned K = 1; K <= MaxLevels; ++K) {
3005 CI[K].PosPart =
Zero;
3006 CI[K].NegPart =
Zero;
3007 CI[K].Iterations =
nullptr;
3009 while (
const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(Subscript)) {
3011 unsigned K = SrcFlag ? mapSrcLoop(L) : mapDstLoop(L);
3013 CI[K].PosPart = getPositivePart(CI[K].Coeff);
3014 CI[K].NegPart = getNegativePart(CI[K].Coeff);
3015 CI[K].Iterations = collectUpperBound(L, Subscript->
getType());
3021 for (
unsigned K = 1; K <= MaxLevels; ++K) {
3028 if (CI[K].Iterations)
3044 const SCEV *DependenceInfo::getLowerBound(BoundInfo *Bound)
const {
3045 const SCEV *Sum = Bound[1].Lower[Bound[1].Direction];
3046 for (
unsigned K = 2; Sum && K <= MaxLevels; ++K) {
3060 const SCEV *DependenceInfo::getUpperBound(BoundInfo *Bound)
const {
3061 const SCEV *Sum = Bound[1].Upper[Bound[1].Direction];
3062 for (
unsigned K = 2; Sum && K <= MaxLevels; ++K) {
3081 const SCEV *DependenceInfo::findCoefficient(
const SCEV *Expr,
3082 const Loop *TargetLoop)
const {
3086 if (AddRec->
getLoop() == TargetLoop)
3088 return findCoefficient(AddRec->
getStart(), TargetLoop);
3097 const SCEV *DependenceInfo::zeroCoefficient(
const SCEV *Expr,
3098 const Loop *TargetLoop)
const {
3102 if (AddRec->
getLoop() == TargetLoop)
3116 const SCEV *DependenceInfo::addToCoefficient(
const SCEV *Expr,
3117 const Loop *TargetLoop,
3125 if (AddRec->
getLoop() == TargetLoop) {
3153 bool DependenceInfo::propagate(
const SCEV *&Src,
const SCEV *&Dst,
3158 for (
unsigned LI :
Loops.set_bits()) {
3161 if (Constraints[LI].isDistance())
3162 Result |= propagateDistance(Src, Dst, Constraints[LI], Consistent);
3163 else if (Constraints[LI].isLine())
3164 Result |= propagateLine(Src, Dst, Constraints[LI], Consistent);
3165 else if (Constraints[LI].isPoint())
3166 Result |= propagatePoint(Src, Dst, Constraints[LI]);
3177 bool DependenceInfo::propagateDistance(
const SCEV *&Src,
const SCEV *&Dst,
3178 Constraint &CurConstraint,
3180 const Loop *CurLoop = CurConstraint.getAssociatedLoop();
3182 const SCEV *A_K = findCoefficient(Src, CurLoop);
3187 Src = zeroCoefficient(Src, CurLoop);
3192 if (!findCoefficient(Dst, CurLoop)->
isZero())
3203 bool DependenceInfo::propagateLine(
const SCEV *&Src,
const SCEV *&Dst,
3204 Constraint &CurConstraint,
3206 const Loop *CurLoop = CurConstraint.getAssociatedLoop();
3207 const SCEV *
A = CurConstraint.getA();
3208 const SCEV *
B = CurConstraint.getB();
3209 const SCEV *
C = CurConstraint.getC();
3217 if (!Bconst || !Cconst)
return false;
3221 assert(Charlie.
srem(Beta) == 0 &&
"C should be evenly divisible by B");
3222 const SCEV *AP_K = findCoefficient(Dst, CurLoop);
3225 Dst = zeroCoefficient(Dst, CurLoop);
3226 if (!findCoefficient(Src, CurLoop)->
isZero())
3229 else if (
B->isZero()) {
3230 const SCEVConstant *Aconst = dyn_cast<SCEVConstant>(A);
3232 if (!Aconst || !Cconst)
return false;
3236 assert(Charlie.
srem(Alpha) == 0 &&
"C should be evenly divisible by A");
3237 const SCEV *A_K = findCoefficient(Src, CurLoop);
3239 Src = zeroCoefficient(Src, CurLoop);
3240 if (!findCoefficient(Dst, CurLoop)->
isZero())
3244 const SCEVConstant *Aconst = dyn_cast<SCEVConstant>(A);
3246 if (!Aconst || !Cconst)
return false;
3250 assert(Charlie.
srem(Alpha) == 0 &&
"C should be evenly divisible by A");
3251 const SCEV *A_K = findCoefficient(Src, CurLoop);
3253 Src = zeroCoefficient(Src, CurLoop);
3254 Dst = addToCoefficient(Dst, CurLoop, A_K);
3255 if (!findCoefficient(Dst, CurLoop)->
isZero())
3260 const SCEV *A_K = findCoefficient(Src, CurLoop);
3264 Src = zeroCoefficient(Src, CurLoop);
3265 Dst = addToCoefficient(Dst, CurLoop, SE->
getMulExpr(A_K,
B));
3266 if (!findCoefficient(Dst, CurLoop)->
isZero())
3278 bool DependenceInfo::propagatePoint(
const SCEV *&Src,
const SCEV *&Dst,
3279 Constraint &CurConstraint) {
3280 const Loop *CurLoop = CurConstraint.getAssociatedLoop();
3281 const SCEV *A_K = findCoefficient(Src, CurLoop);
3282 const SCEV *AP_K = findCoefficient(Dst, CurLoop);
3287 Src = zeroCoefficient(Src, CurLoop);
3290 Dst = zeroCoefficient(Dst, CurLoop);
3298 const Constraint &CurConstraint)
const {
3301 if (CurConstraint.isAny())
3303 else if (CurConstraint.isDistance()) {
3305 Level.Scalar =
false;
3306 Level.Distance = CurConstraint.getD();
3314 Level.Direction &= NewDirection;
3316 else if (CurConstraint.isLine()) {
3317 Level.Scalar =
false;
3318 Level.Distance =
nullptr;
3321 else if (CurConstraint.isPoint()) {
3322 Level.Scalar =
false;
3323 Level.Distance =
nullptr;
3326 CurConstraint.getY(),
3327 CurConstraint.getX()))
3331 CurConstraint.getY(),
3332 CurConstraint.getX()))
3336 CurConstraint.getY(),
3337 CurConstraint.getX()))
3340 Level.Direction &= NewDirection;
3365 if (!SrcBase || !DstBase || SrcBase != DstBase)
3370 if (!tryDelinearizeFixedSize(Src, Dst, SrcAccessFn, DstAccessFn,
3371 SrcSubscripts, DstSubscripts) &&
3372 !tryDelinearizeParametricSize(Src, Dst, SrcAccessFn, DstAccessFn,
3373 SrcSubscripts, DstSubscripts))
3376 int Size = SrcSubscripts.size();
3378 dbgs() <<
"\nSrcSubscripts: ";
3379 for (
int I = 0;
I <
Size;
I++)
3380 dbgs() << *SrcSubscripts[
I];
3381 dbgs() <<
"\nDstSubscripts: ";
3382 for (
int I = 0;
I <
Size;
I++)
3383 dbgs() << *DstSubscripts[
I];
3391 for (
int I = 0;
I <
Size; ++
I) {
3392 Pair[
I].Src = SrcSubscripts[
I];
3393 Pair[
I].Dst = DstSubscripts[
I];
3394 unifySubscriptType(&Pair[
I]);
3403 bool DependenceInfo::tryDelinearizeFixedSize(
3412 assert(SrcBase && DstBase && SrcBase == DstBase &&
3413 "expected src and dst scev unknowns to be equal");
3426 if (SrcSizes.size() != DstSizes.size() ||
3427 !
std::equal(SrcSizes.begin(), SrcSizes.end(), DstSizes.begin())) {
3428 SrcSubscripts.
clear();
3429 DstSubscripts.
clear();
3433 assert(SrcSubscripts.size() == DstSubscripts.size() &&
3434 "Expected equal number of entries in the list of SrcSubscripts and "
3450 size_t SSize = Subscripts.size();
3451 for (
size_t I = 1;
I < SSize; ++
I) {
3452 const SCEV *
S = Subscripts[
I];
3453 if (!isKnownNonNegative(
S,
Ptr))
3455 if (
auto *SType = dyn_cast<IntegerType>(
S->getType())) {
3458 if (!isKnownLessThan(
S, Range))
3465 if (!AllIndiciesInRange(SrcSizes, SrcSubscripts, SrcPtr) ||
3466 !AllIndiciesInRange(DstSizes, DstSubscripts, DstPtr)) {
3467 SrcSubscripts.
clear();
3468 DstSubscripts.
clear();
3473 dbgs() <<
"Delinearized subscripts of fixed-size array\n"
3474 <<
"SrcGEP:" << *SrcPtr <<
"\n"
3475 <<
"DstGEP:" << *DstPtr <<
"\n";
3480 bool DependenceInfo::tryDelinearizeParametricSize(
3491 assert(SrcBase && DstBase && SrcBase == DstBase &&
3492 "expected src and dst scev unknowns to be equal");
3520 if (SrcSubscripts.size() < 2 || DstSubscripts.size() < 2 ||
3521 SrcSubscripts.size() != DstSubscripts.size())
3524 size_t Size = SrcSubscripts.size();
3533 for (
size_t I = 1;
I <
Size; ++
I) {
3534 if (!isKnownNonNegative(SrcSubscripts[
I], SrcPtr))
3537 if (!isKnownLessThan(SrcSubscripts[
I], Sizes[
I - 1]))
3540 if (!isKnownNonNegative(DstSubscripts[
I], DstPtr))
3543 if (!isKnownLessThan(DstSubscripts[
I], Sizes[
I - 1]))
3589 std::unique_ptr<Dependence>
3591 bool PossiblyLoopIndependent) {
3593 PossiblyLoopIndependent =
false;
3595 if (!(Src->mayReadOrWriteMemory() && Dst->mayReadOrWriteMemory()))
3601 LLVM_DEBUG(
dbgs() <<
"can only handle simple loads and stores\n");
3602 return std::make_unique<Dependence>(Src, Dst);
3617 return std::make_unique<Dependence>(Src, Dst);
3627 establishNestingLevels(Src, Dst);
3628 LLVM_DEBUG(
dbgs() <<
" common nesting levels = " << CommonLevels <<
"\n");
3629 LLVM_DEBUG(
dbgs() <<
" maximum nesting levels = " << MaxLevels <<
"\n");
3631 FullDependence Result(Src, Dst, PossiblyLoopIndependent, CommonLevels);
3647 LLVM_DEBUG(
dbgs() <<
"can't analyze SCEV with different pointer base\n");
3648 return std::make_unique<Dependence>(Src, Dst);
3650 Pair[0].Src = SrcSCEV;
3651 Pair[0].Dst = DstSCEV;
3654 if (tryDelinearize(Src, Dst, Pair)) {
3656 Pairs = Pair.size();
3660 for (
unsigned P = 0;
P < Pairs; ++
P) {
3661 Pair[
P].Loops.
resize(MaxLevels + 1);
3662 Pair[
P].GroupLoops.
resize(MaxLevels + 1);
3664 removeMatchingExtensions(&Pair[
P]);
3665 Pair[
P].Classification =
3666 classifyPair(Pair[
P].Src, LI->
getLoopFor(Src->getParent()),
3669 Pair[
P].GroupLoops = Pair[
P].Loops;
3670 Pair[
P].Group.set(
P);
3739 for (
unsigned SI = 0;
SI < Pairs; ++
SI) {
3740 if (Pair[
SI].Classification == Subscript::NonLinear) {
3742 ++NonlinearSubscriptPairs;
3743 collectCommonLoops(Pair[
SI].Src,
3746 collectCommonLoops(Pair[
SI].Dst,
3749 Result.Consistent =
false;
3750 }
else if (Pair[
SI].Classification == Subscript::ZIV) {
3757 for (
unsigned SJ =
SI + 1; SJ < Pairs; ++SJ) {
3759 Intersection &= Pair[SJ].GroupLoops;
3760 if (Intersection.
any()) {
3762 Pair[SJ].GroupLoops |= Pair[
SI].GroupLoops;
3764 Pair[SJ].Group |= Pair[
SI].Group;
3769 if (Pair[
SI].Group.count() == 1) {
3771 ++SeparableSubscriptPairs;
3775 ++CoupledSubscriptPairs;
3786 Constraint NewConstraint;
3787 NewConstraint.setAny(SE);
3792 switch (Pair[
SI].Classification) {
3793 case Subscript::ZIV:
3795 if (testZIV(Pair[
SI].Src, Pair[
SI].Dst, Result))
3798 case Subscript::SIV: {
3801 const SCEV *SplitIter =
nullptr;
3802 if (testSIV(Pair[
SI].Src, Pair[
SI].Dst, Level, Result, NewConstraint,
3807 case Subscript::RDIV:
3809 if (testRDIV(Pair[
SI].Src, Pair[
SI].Dst, Result))
3812 case Subscript::MIV:
3814 if (testMIV(Pair[
SI].Src, Pair[
SI].Dst, Pair[
SI].
Loops, Result))
3822 if (Coupled.
count()) {
3825 LLVM_DEBUG(
dbgs() <<
"MaxLevels + 1 = " << MaxLevels + 1 <<
"\n");
3827 for (
unsigned II = 0; II <= MaxLevels; ++II)
3828 Constraints[II].setAny(SE);
3836 for (
unsigned SJ : Group.
set_bits()) {
3838 if (Pair[SJ].Classification == Subscript::SIV)
3842 PairsInGroup.push_back(&Pair[SJ]);
3844 unifySubscriptType(PairsInGroup);
3846 while (Sivs.
any()) {
3847 bool Changed =
false;
3848 for (
unsigned SJ : Sivs.
set_bits()) {
3852 const SCEV *SplitIter =
nullptr;
3854 if (testSIV(Pair[SJ].Src, Pair[SJ].Dst, Level, Result, NewConstraint,
3857 ConstrainedLevels.
set(Level);
3858 if (intersectConstraints(&Constraints[Level], &NewConstraint)) {
3859 if (Constraints[Level].isEmpty()) {
3860 ++DeltaIndependence;
3872 for (
unsigned SJ : Mivs.
set_bits()) {
3875 if (propagate(Pair[SJ].Src, Pair[SJ].Dst, Pair[SJ].
Loops,
3876 Constraints, Result.Consistent)) {
3878 ++DeltaPropagations;
3879 Pair[SJ].Classification =
3880 classifyPair(Pair[SJ].Src, LI->
getLoopFor(Src->getParent()),
3881 Pair[SJ].Dst, LI->
getLoopFor(Dst->getParent()),
3883 switch (Pair[SJ].Classification) {
3884 case Subscript::ZIV:
3886 if (testZIV(Pair[SJ].Src, Pair[SJ].Dst, Result))
3890 case Subscript::SIV:
3894 case Subscript::RDIV:
3895 case Subscript::MIV:
3906 for (
unsigned SJ : Mivs.
set_bits()) {
3907 if (Pair[SJ].Classification == Subscript::RDIV) {
3909 if (testRDIV(Pair[SJ].Src, Pair[SJ].Dst, Result))
3919 for (
unsigned SJ : Mivs.
set_bits()) {
3920 if (Pair[SJ].Classification == Subscript::MIV) {
3922 if (testMIV(Pair[SJ].Src, Pair[SJ].Dst, Pair[SJ].
Loops, Result))
3931 for (
unsigned SJ : ConstrainedLevels.
set_bits()) {
3932 if (SJ > CommonLevels)
3934 updateDirection(Result.DV[SJ - 1], Constraints[SJ]);
3943 for (
unsigned SI = 0;
SI < Pairs; ++
SI)
3944 CompleteLoops |= Pair[
SI].
Loops;
3945 for (
unsigned II = 1; II <= CommonLevels; ++II)
3946 if (CompleteLoops[II])
3947 Result.DV[II - 1].Scalar =
false;
3949 if (PossiblyLoopIndependent) {
3953 for (
unsigned II = 1; II <= CommonLevels; ++II) {
3955 Result.LoopIndependent =
false;
3963 bool AllEqual =
true;
3964 for (
unsigned II = 1; II <= CommonLevels; ++II) {
3974 return std::make_unique<FullDependence>(
std::move(Result));
4025 unsigned SplitLevel) {
4027 "Dep should be splitable at SplitLevel");
4030 assert(Src->mayReadFromMemory() || Src->mayWriteToMemory());
4031 assert(Dst->mayReadFromMemory() || Dst->mayWriteToMemory());
4041 establishNestingLevels(Src, Dst);
4049 Pair[0].Src = SrcSCEV;
4050 Pair[0].Dst = DstSCEV;
4053 if (tryDelinearize(Src, Dst, Pair)) {
4055 Pairs = Pair.size();
4059 for (
unsigned P = 0;
P < Pairs; ++
P) {
4060 Pair[
P].Loops.
resize(MaxLevels + 1);
4061 Pair[
P].GroupLoops.
resize(MaxLevels + 1);
4063 removeMatchingExtensions(&Pair[
P]);
4064 Pair[
P].Classification =
4065 classifyPair(Pair[
P].Src, LI->
getLoopFor(Src->getParent()),
4068 Pair[
P].GroupLoops = Pair[
P].Loops;
4069 Pair[
P].Group.set(
P);
4076 for (
unsigned SI = 0;
SI < Pairs; ++
SI) {
4077 if (Pair[
SI].Classification == Subscript::NonLinear) {
4079 collectCommonLoops(Pair[
SI].Src,
4082 collectCommonLoops(Pair[
SI].Dst,
4085 Result.Consistent =
false;
4087 else if (Pair[
SI].Classification == Subscript::ZIV)
4092 for (
unsigned SJ =
SI + 1; SJ < Pairs; ++SJ) {
4094 Intersection &= Pair[SJ].GroupLoops;
4095 if (Intersection.
any()) {
4097 Pair[SJ].GroupLoops |= Pair[
SI].GroupLoops;
4099 Pair[SJ].Group |= Pair[
SI].Group;
4104 if (Pair[
SI].Group.count() == 1)
4112 Constraint NewConstraint;
4113 NewConstraint.setAny(SE);
4117 switch (Pair[
SI].Classification) {
4118 case Subscript::SIV: {
4120 const SCEV *SplitIter =
nullptr;
4121 (void) testSIV(Pair[
SI].Src, Pair[
SI].Dst, Level,
4122 Result, NewConstraint, SplitIter);
4123 if (Level == SplitLevel) {
4124 assert(SplitIter !=
nullptr);
4129 case Subscript::ZIV:
4130 case Subscript::RDIV:
4131 case Subscript::MIV:
4138 if (Coupled.
count()) {
4141 for (
unsigned II = 0; II <= MaxLevels; ++II)
4142 Constraints[II].setAny(SE);
4148 for (
unsigned SJ : Group.
set_bits()) {
4149 if (Pair[SJ].Classification == Subscript::SIV)
4154 while (Sivs.
any()) {
4155 bool Changed =
false;
4156 for (
unsigned SJ : Sivs.
set_bits()) {
4159 const SCEV *SplitIter =
nullptr;
4160 (void) testSIV(Pair[SJ].Src, Pair[SJ].Dst, Level,
4161 Result, NewConstraint, SplitIter);
4162 if (Level == SplitLevel && SplitIter)
4164 ConstrainedLevels.
set(Level);
4165 if (intersectConstraints(&Constraints[Level], &NewConstraint))
4171 for (
unsigned SJ : Mivs.
set_bits()) {
4173 if (propagate(Pair[SJ].Src, Pair[SJ].Dst,
4174 Pair[SJ].
Loops, Constraints, Result.Consistent)) {
4175 Pair[SJ].Classification =
4176 classifyPair(Pair[SJ].Src, LI->
getLoopFor(Src->getParent()),
4177 Pair[SJ].Dst, LI->
getLoopFor(Dst->getParent()),
4179 switch (Pair[SJ].Classification) {
4180 case Subscript::ZIV:
4183 case Subscript::SIV:
4187 case Subscript::RDIV:
4188 case Subscript::MIV: