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();
180 auto *
F =
DA->getFunction();
183 if (SrcI->mayReadOrWriteMemory()) {
185 DstI != DstE; ++DstI) {
186 if (DstI->mayReadOrWriteMemory()) {
187 OS <<
"Src:" << *SrcI <<
" --> Dst:" << *DstI <<
"\n";
188 OS <<
" da analyze - ";
189 if (
auto D =
DA->depends(&*SrcI, &*DstI,
true)) {
192 if (
D->isSplitable(
Level)) {
193 OS <<
" da analyze - split level = " <<
Level;
194 OS <<
", iteration = " << *
DA->getSplitIteration(*
D,
Level);
214 OS <<
"'Dependence Analysis' for function '" <<
F.getName() <<
"':\n";
259 bool PossiblyLoopIndependent,
260 unsigned CommonLevels)
262 LoopIndependent(PossiblyLoopIndependent) {
265 DV = std::make_unique<DVEntry[]>(CommonLevels);
273 return DV[
Level - 1].Direction;
280 return DV[
Level - 1].Distance;
289 return DV[
Level - 1].Scalar;
297 return DV[
Level - 1].PeelFirst;
305 return DV[
Level - 1].PeelLast;
312 return DV[
Level - 1].Splitable;
321 const SCEV *DependenceInfo::Constraint::getX()
const {
322 assert(
Kind == Point &&
"Kind should be Point");
329 const SCEV *DependenceInfo::Constraint::getY()
const {
330 assert(
Kind == Point &&
"Kind should be Point");
337 const SCEV *DependenceInfo::Constraint::getA()
const {
339 "Kind should be Line (or Distance)");
346 const SCEV *DependenceInfo::Constraint::getB()
const {
348 "Kind should be Line (or Distance)");
355 const SCEV *DependenceInfo::Constraint::getC()
const {
357 "Kind should be Line (or Distance)");
364 const SCEV *DependenceInfo::Constraint::getD()
const {
365 assert(
Kind == Distance &&
"Kind should be Distance");
366 return SE->getNegativeSCEV(
C);
371 const Loop *DependenceInfo::Constraint::getAssociatedLoop()
const {
373 "Kind should be Distance, Line, or Point");
374 return AssociatedLoop;
377 void DependenceInfo::Constraint::setPoint(
const SCEV *
X,
const SCEV *
Y,
378 const Loop *CurLoop) {
382 AssociatedLoop = CurLoop;
385 void DependenceInfo::Constraint::setLine(
const SCEV *
AA,
const SCEV *
BB,
386 const SCEV *CC,
const Loop *CurLoop) {
391 AssociatedLoop = CurLoop;
394 void DependenceInfo::Constraint::setDistance(
const SCEV *
D,
395 const Loop *CurLoop) {
397 A = SE->getOne(
D->getType());
398 B = SE->getNegativeSCEV(A);
399 C = SE->getNegativeSCEV(
D);
400 AssociatedLoop = CurLoop;
403 void DependenceInfo::Constraint::setEmpty() {
Kind =
Empty; }
410 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
418 OS <<
" Point is <" << *getX() <<
", " << *getY() <<
">\n";
419 else if (isDistance())
420 OS <<
" Distance is " << *getD() <<
421 " (" << *getA() <<
"*X + " << *getB() <<
"*Y = " << *getC() <<
")\n";
423 OS <<
" Line is " << *getA() <<
"*X + " <<
424 *getB() <<
"*Y = " << *getC() <<
"\n";
438 bool DependenceInfo::intersectConstraints(Constraint *
X,
const Constraint *
Y) {
443 assert(!
Y->isPoint() &&
"Y must not be a Point");
457 if (
X->isDistance() &&
Y->isDistance()) {
468 if (isa<SCEVConstant>(
Y->getD())) {
481 assert(!(
X->isPoint() &&
Y->isPoint()) &&
482 "We shouldn't ever see X->isPoint() && Y->isPoint()");
484 if (
X->isLine() &&
Y->isLine()) {
519 if (!C1B2_C2B1 || !C1A2_C2A1 ||
520 !A1B2_A2B1 || !A2B1_A1B2)
536 if (Xr != 0 || Yr != 0) {
542 if (Xq.
slt(0) || Yq.
slt(0)) {
548 collectConstantUpperBound(
X->getAssociatedLoop(), Prod1->
getType())) {
549 const APInt &UpperBound = CUB->getAPInt();
551 if (Xq.
sgt(UpperBound) || Yq.
sgt(UpperBound)) {
559 X->getAssociatedLoop());
567 assert(!(
X->isLine() &&
Y->isPoint()) &&
"This case should never occur");
569 if (
X->isPoint() &&
Y->isLine()) {
594 bool Splitable =
false;
610 for (
unsigned II = 1; II <= Levels; ++II) {
662 if (
AA->isNoAlias(LocAS, LocBS))
688 if (
const LoadInst *LI = dyn_cast<LoadInst>(
I))
689 return LI->isUnordered();
691 return SI->isUnordered();
746 void DependenceInfo::establishNestingLevels(
const Instruction *Src,
748 const BasicBlock *SrcBlock = Src->getParent();
749 const BasicBlock *DstBlock = Dst->getParent();
754 SrcLevels = SrcLevel;
755 MaxLevels = SrcLevel + DstLevel;
756 while (SrcLevel > DstLevel) {
760 while (DstLevel > SrcLevel) {
764 while (SrcLoop != DstLoop) {
769 CommonLevels = SrcLevel;
770 MaxLevels -= CommonLevels;
776 unsigned DependenceInfo::mapSrcLoop(
const Loop *SrcLoop)
const {
783 unsigned DependenceInfo::mapDstLoop(
const Loop *DstLoop)
const {
785 if (
D > CommonLevels)
788 return D - CommonLevels + SrcLevels;
826 unsigned widestWidthSeen = 0;
831 for (Subscript *Pair : Pairs) {
832 const SCEV *Src = Pair->Src;
833 const SCEV *Dst = Pair->Dst;
834 IntegerType *SrcTy = dyn_cast<IntegerType>(Src->getType());
835 IntegerType *DstTy = dyn_cast<IntegerType>(Dst->getType());
836 if (SrcTy ==
nullptr || DstTy ==
nullptr) {
837 assert(SrcTy == DstTy &&
"This function only unify integer types and "
838 "expect Src and Dst share the same type "
853 assert(widestWidthSeen > 0);
856 for (Subscript *Pair : Pairs) {
857 const SCEV *Src = Pair->Src;
858 const SCEV *Dst = Pair->Dst;
859 IntegerType *SrcTy = dyn_cast<IntegerType>(Src->getType());
860 IntegerType *DstTy = dyn_cast<IntegerType>(Dst->getType());
861 if (SrcTy ==
nullptr || DstTy ==
nullptr) {
862 assert(SrcTy == DstTy &&
"This function only unify integer types and "
863 "expect Src and Dst share the same type "
881 void DependenceInfo::removeMatchingExtensions(Subscript *Pair) {
882 const SCEV *Src = Pair->Src;
883 const SCEV *Dst = Pair->Dst;
884 if ((isa<SCEVZeroExtendExpr>(Src) && isa<SCEVZeroExtendExpr>(Dst)) ||
885 (isa<SCEVSignExtendExpr>(Src) && isa<SCEVSignExtendExpr>(Dst))) {
891 Pair->Src = SrcCastOp;
892 Pair->Dst = DstCastOp;
903 return isLoopInvariant(Expr,
LoopNest);
911 while (L && AddRec->
getLoop() != L)
919 if (!isa<SCEVCouldNotCompute>(UB)) {
926 if (!isLoopInvariant(Step,
LoopNest))
937 bool DependenceInfo::checkSrcSubscript(
const SCEV *Src,
const Loop *
LoopNest,
944 bool DependenceInfo::checkDstSubscript(
const SCEV *Dst,
const Loop *
LoopNest,
953 DependenceInfo::Subscript::ClassificationKind
954 DependenceInfo::classifyPair(
const SCEV *Src,
const Loop *SrcLoopNest,
955 const SCEV *Dst,
const Loop *DstLoopNest,
959 if (!checkSrcSubscript(Src, SrcLoopNest, SrcLoops))
960 return Subscript::NonLinear;
961 if (!checkDstSubscript(Dst, DstLoopNest, DstLoops))
962 return Subscript::NonLinear;
965 unsigned N =
Loops.count();
967 return Subscript::ZIV;
969 return Subscript::SIV;
970 if (
N == 2 && (SrcLoops.count() == 0 ||
971 DstLoops.count() == 0 ||
972 (SrcLoops.count() == 1 && DstLoops.count() == 1)))
973 return Subscript::RDIV;
974 return Subscript::MIV;
989 const SCEV *
Y)
const {
992 if ((isa<SCEVSignExtendExpr>(
X) &&
993 isa<SCEVSignExtendExpr>(
Y)) ||
994 (isa<SCEVZeroExtendExpr>(
X) &&
995 isa<SCEVZeroExtendExpr>(
Y))) {
1035 bool DependenceInfo::isKnownLessThan(
const SCEV *
S,
const SCEV *Size)
const {
1037 auto *SType = dyn_cast<IntegerType>(
S->getType());
1038 auto *SizeType = dyn_cast<IntegerType>(
Size->getType());
1039 if (!SType || !SizeType)
1042 (SType->getBitWidth() >= SizeType->getBitWidth()) ? SType : SizeType;
1048 if (
const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(Bound)) {
1051 if (!isa<SCEVCouldNotCompute>(BECount)) {
1060 const SCEV *LimitedBound =
1065 bool DependenceInfo::isKnownNonNegative(
const SCEV *
S,
const Value *Ptr)
const {
1066 bool Inbounds =
false;
1067 if (
auto *SrcGEP = dyn_cast<GetElementPtrInst>(Ptr))
1068 Inbounds = SrcGEP->isInBounds();
1091 const SCEV *DependenceInfo::collectUpperBound(
const Loop *L,
Type *T)
const {
1102 const SCEVConstant *DependenceInfo::collectConstantUpperBound(
const Loop *L,
1104 if (
const SCEV *UB = collectUpperBound(L, T))
1105 return dyn_cast<SCEVConstant>(UB);
1120 bool DependenceInfo::testZIV(
const SCEV *Src,
const SCEV *Dst,
1135 Result.Consistent =
false;
1167 bool DependenceInfo::strongSIVtest(
const SCEV *Coeff,
const SCEV *SrcConst,
1168 const SCEV *DstConst,
const Loop *CurLoop,
1170 Constraint &NewConstraint)
const {
1178 ++StrongSIVapplications;
1187 if (
const SCEV *UpperBound = collectUpperBound(CurLoop, Delta->
getType())) {
1190 const SCEV *AbsDelta =
1192 const SCEV *AbsCoeff =
1197 ++StrongSIVindependence;
1198 ++StrongSIVsuccesses;
1204 if (isa<SCEVConstant>(Delta) && isa<SCEVConstant>(Coeff)) {
1205 APInt ConstDelta = cast<SCEVConstant>(Delta)->getAPInt();
1206 APInt ConstCoeff = cast<SCEVConstant>(Coeff)->getAPInt();
1207 APInt Distance = ConstDelta;
1208 APInt Remainder = ConstDelta;
1213 if (Remainder != 0) {
1215 ++StrongSIVindependence;
1216 ++StrongSIVsuccesses;
1220 NewConstraint.setDistance(SE->
getConstant(Distance), CurLoop);
1221 if (Distance.
sgt(0))
1223 else if (Distance.
slt(0))
1227 ++StrongSIVsuccesses;
1229 else if (Delta->
isZero()) {
1232 NewConstraint.setDistance(Delta, CurLoop);
1234 ++StrongSIVsuccesses;
1237 if (Coeff->
isOne()) {
1240 NewConstraint.setDistance(Delta, CurLoop);
1243 Result.Consistent =
false;
1244 NewConstraint.setLine(Coeff,
1259 if ((DeltaMaybePositive && CoeffMaybePositive) ||
1260 (DeltaMaybeNegative && CoeffMaybeNegative))
1264 if ((DeltaMaybeNegative && CoeffMaybePositive) ||
1265 (DeltaMaybePositive && CoeffMaybeNegative))
1268 ++StrongSIVsuccesses;
1303 bool DependenceInfo::weakCrossingSIVtest(
1304 const SCEV *Coeff,
const SCEV *SrcConst,
const SCEV *DstConst,
1306 Constraint &NewConstraint,
const SCEV *&SplitIter)
const {
1311 ++WeakCrossingSIVapplications;
1314 Result.Consistent =
false;
1317 NewConstraint.setLine(Coeff, Coeff, Delta, CurLoop);
1321 ++WeakCrossingSIVsuccesses;
1323 ++WeakCrossingSIVindependence;
1329 const SCEVConstant *ConstCoeff = dyn_cast<SCEVConstant>(Coeff);
1337 "dynamic cast of negative of ConstCoeff should yield constant");
1348 const SCEVConstant *ConstDelta = dyn_cast<SCEVConstant>(Delta);
1358 ++WeakCrossingSIVindependence;
1359 ++WeakCrossingSIVsuccesses;
1365 if (
const SCEV *UpperBound = collectUpperBound(CurLoop, Delta->
getType())) {
1373 ++WeakCrossingSIVindependence;
1374 ++WeakCrossingSIVsuccesses;
1381 ++WeakCrossingSIVsuccesses;
1383 ++WeakCrossingSIVindependence;
1395 APInt Distance = APDelta;
1396 APInt Remainder = APDelta;
1399 if (Remainder != 0) {
1401 ++WeakCrossingSIVindependence;
1402 ++WeakCrossingSIVsuccesses;
1409 Remainder = Distance.
srem(Two);
1411 if (Remainder != 0) {
1414 ++WeakCrossingSIVsuccesses;
1440 APInt A2 = A0 - Q*A1; A0 = A1; A1 = A2;
1447 X = AM.
slt(0) ? -A1 : A1;
1464 if ((A.sgt(0) &&
B.sgt(0)) ||
1465 (A.slt(0) &&
B.slt(0)))
1477 if ((A.sgt(0) &&
B.sgt(0)) ||
1478 (A.slt(0) &&
B.slt(0)))
1503 bool DependenceInfo::exactSIVtest(
const SCEV *SrcCoeff,
const SCEV *DstCoeff,
1504 const SCEV *SrcConst,
const SCEV *DstConst,
1507 Constraint &NewConstraint)
const {
1509 LLVM_DEBUG(
dbgs() <<
"\t SrcCoeff = " << *SrcCoeff <<
" = AM\n");
1510 LLVM_DEBUG(
dbgs() <<
"\t DstCoeff = " << *DstCoeff <<
" = BM\n");
1513 ++ExactSIVapplications;
1516 Result.Consistent =
false;
1521 const SCEVConstant *ConstDelta = dyn_cast<SCEVConstant>(Delta);
1522 const SCEVConstant *ConstSrcCoeff = dyn_cast<SCEVConstant>(SrcCoeff);
1523 const SCEVConstant *ConstDstCoeff = dyn_cast<SCEVConstant>(DstCoeff);
1524 if (!ConstDelta || !ConstSrcCoeff || !ConstDstCoeff)
1535 ++ExactSIVindependence;
1536 ++ExactSIVsuccesses;
1544 bool UMValid =
false;
1547 collectConstantUpperBound(CurLoop, Delta->
getType())) {
1548 UM = CUB->getAPInt();
1566 LLVM_DEBUG(
dbgs() <<
"\t Possible TL = " << TLVec.back() <<
"\n");
1570 LLVM_DEBUG(
dbgs() <<
"\t Possible TU = " << TUVec.back() <<
"\n");
1574 LLVM_DEBUG(
dbgs() <<
"\t Possible TU = " << TUVec.back() <<
"\n");
1578 LLVM_DEBUG(
dbgs() <<
"\t Possible TL = " << TLVec.back() <<
"\n");
1586 LLVM_DEBUG(
dbgs() <<
"\t Possible TU = " << TUVec.back() <<
"\n");
1590 LLVM_DEBUG(
dbgs() <<
"\t Possible TL = " << TLVec.back() <<
"\n");
1594 LLVM_DEBUG(
dbgs() <<
"\t Possible TL = " << TLVec.back() <<
"\n");
1598 LLVM_DEBUG(
dbgs() <<
"\t Possible TU = " << TUVec.back() <<
"\n");
1604 if (TLVec.empty() || TUVec.empty())
1612 ++ExactSIVindependence;
1613 ++ExactSIVsuccesses;
1619 APInt LowerDistance, UpperDistance;
1621 LowerDistance = (TY - TX) + (
TA -
TB) * TL;
1622 UpperDistance = (TY - TX) + (
TA -
TB) * TU;
1624 LowerDistance = (TY - TX) + (
TA -
TB) * TU;
1625 UpperDistance = (TY - TX) + (
TA -
TB) * TL;
1628 LLVM_DEBUG(
dbgs() <<
"\t LowerDistance = " << LowerDistance <<
"\n");
1629 LLVM_DEBUG(
dbgs() <<
"\t UpperDistance = " << UpperDistance <<
"\n");
1632 if (LowerDistance.
sle(Zero) && UpperDistance.
sge(Zero)) {
1634 ++ExactSIVsuccesses;
1636 if (LowerDistance.
slt(0)) {
1638 ++ExactSIVsuccesses;
1640 if (UpperDistance.
sgt(0)) {
1642 ++ExactSIVsuccesses;
1648 ++ExactSIVindependence;
1661 return ConstDividend.
srem(ConstDivisor) == 0;
1696 bool DependenceInfo::weakZeroSrcSIVtest(
const SCEV *DstCoeff,
1697 const SCEV *SrcConst,
1698 const SCEV *DstConst,
1701 Constraint &NewConstraint)
const {
1709 ++WeakZeroSIVapplications;
1712 Result.Consistent =
false;
1714 NewConstraint.setLine(SE->
getZero(Delta->
getType()), DstCoeff, Delta,
1718 if (
Level < CommonLevels) {
1721 ++WeakZeroSIVsuccesses;
1725 const SCEVConstant *ConstCoeff = dyn_cast<SCEVConstant>(DstCoeff);
1728 const SCEV *AbsCoeff =
1731 const SCEV *NewDelta =
1736 if (
const SCEV *UpperBound = collectUpperBound(CurLoop, Delta->
getType())) {
1740 ++WeakZeroSIVindependence;
1741 ++WeakZeroSIVsuccesses;
1746 if (
Level < CommonLevels) {
1749 ++WeakZeroSIVsuccesses;
1759 ++WeakZeroSIVindependence;
1760 ++WeakZeroSIVsuccesses;
1765 if (isa<SCEVConstant>(Delta) &&
1767 ++WeakZeroSIVindependence;
1768 ++WeakZeroSIVsuccesses;
1806 bool DependenceInfo::weakZeroDstSIVtest(
const SCEV *SrcCoeff,
1807 const SCEV *SrcConst,
1808 const SCEV *DstConst,
1811 Constraint &NewConstraint)
const {
1818 ++WeakZeroSIVapplications;
1821 Result.Consistent =
false;
1823 NewConstraint.setLine(SrcCoeff, SE->
getZero(Delta->
getType()), Delta,
1827 if (
Level < CommonLevels) {
1830 ++WeakZeroSIVsuccesses;
1834 const SCEVConstant *ConstCoeff = dyn_cast<SCEVConstant>(SrcCoeff);
1837 const SCEV *AbsCoeff =
1840 const SCEV *NewDelta =
1845 if (
const SCEV *UpperBound = collectUpperBound(CurLoop, Delta->
getType())) {
1849 ++WeakZeroSIVindependence;
1850 ++WeakZeroSIVsuccesses;
1855 if (
Level < CommonLevels) {
1858 ++WeakZeroSIVsuccesses;
1868 ++WeakZeroSIVindependence;
1869 ++WeakZeroSIVsuccesses;
1874 if (isa<SCEVConstant>(Delta) &&
1876 ++WeakZeroSIVindependence;
1877 ++WeakZeroSIVsuccesses;
1891 bool DependenceInfo::exactRDIVtest(
const SCEV *SrcCoeff,
const SCEV *DstCoeff,
1892 const SCEV *SrcConst,
const SCEV *DstConst,
1893 const Loop *SrcLoop,
const Loop *DstLoop,
1896 LLVM_DEBUG(
dbgs() <<
"\t SrcCoeff = " << *SrcCoeff <<
" = AM\n");
1897 LLVM_DEBUG(
dbgs() <<
"\t DstCoeff = " << *DstCoeff <<
" = BM\n");
1900 ++ExactRDIVapplications;
1901 Result.Consistent =
false;
1904 const SCEVConstant *ConstDelta = dyn_cast<SCEVConstant>(Delta);
1905 const SCEVConstant *ConstSrcCoeff = dyn_cast<SCEVConstant>(SrcCoeff);
1906 const SCEVConstant *ConstDstCoeff = dyn_cast<SCEVConstant>(DstCoeff);
1907 if (!ConstDelta || !ConstSrcCoeff || !ConstDstCoeff)
1918 ++ExactRDIVindependence;
1926 bool SrcUMvalid =
false;
1929 collectConstantUpperBound(SrcLoop, Delta->
getType())) {
1930 SrcUM = UpperBound->getAPInt();
1936 bool DstUMvalid =
false;
1939 collectConstantUpperBound(DstLoop, Delta->
getType())) {
1940 DstUM = UpperBound->getAPInt();
1958 LLVM_DEBUG(
dbgs() <<
"\t Possible TL = " << TLVec.back() <<
"\n");
1961 LLVM_DEBUG(
dbgs() <<
"\t Possible TU = " << TUVec.back() <<
"\n");
1965 LLVM_DEBUG(
dbgs() <<
"\t Possible TU = " << TUVec.back() <<
"\n");
1968 LLVM_DEBUG(
dbgs() <<
"\t Possible TL = " << TLVec.back() <<
"\n");
1975 LLVM_DEBUG(
dbgs() <<
"\t Possible TL = " << TLVec.back() <<
"\n");
1978 LLVM_DEBUG(
dbgs() <<
"\t Possible TU = " << TUVec.back() <<
"\n");
1982 LLVM_DEBUG(
dbgs() <<
"\t Possible TU = " << TUVec.back() <<
"\n");
1985 LLVM_DEBUG(
dbgs() <<
"\t Possible TL = " << TLVec.back() <<
"\n");
1989 if (TLVec.empty() || TUVec.empty())
2001 ++ExactRDIVindependence;
2048 bool DependenceInfo::symbolicRDIVtest(
const SCEV *A1,
const SCEV *A2,
2051 const Loop *Loop2)
const {
2052 ++SymbolicRDIVapplications;
2059 const SCEV *N1 = collectUpperBound(Loop1, A1->
getType());
2060 const SCEV *N2 = collectUpperBound(Loop2, A1->
getType());
2075 ++SymbolicRDIVindependence;
2084 ++SymbolicRDIVindependence;
2096 LLVM_DEBUG(
dbgs() <<
"\t A1*N1 - A2*N2 = " << *A1N1_A2N2 <<
"\n");
2098 ++SymbolicRDIVindependence;
2104 ++SymbolicRDIVindependence;
2117 LLVM_DEBUG(
dbgs() <<
"\t A1*N1 - A2*N2 = " << *A1N1_A2N2 <<
"\n");
2119 ++SymbolicRDIVindependence;
2125 ++SymbolicRDIVindependence;
2136 ++SymbolicRDIVindependence;
2145 ++SymbolicRDIVindependence;
2163 bool DependenceInfo::testSIV(
const SCEV *Src,
const SCEV *Dst,
unsigned &
Level,
2165 const SCEV *&SplitIter)
const {
2170 if (SrcAddRec && DstAddRec) {
2177 "both loops in SIV should be same");
2178 Level = mapSrcLoop(CurLoop);
2180 if (SrcCoeff == DstCoeff)
2181 disproven = strongSIVtest(SrcCoeff, SrcConst, DstConst, CurLoop,
2182 Level, Result, NewConstraint);
2184 disproven = weakCrossingSIVtest(SrcCoeff, SrcConst, DstConst, CurLoop,
2185 Level, Result, NewConstraint, SplitIter);
2187 disproven = exactSIVtest(SrcCoeff, DstCoeff, SrcConst, DstConst, CurLoop,
2188 Level, Result, NewConstraint);
2190 gcdMIVtest(Src, Dst, Result) ||
2191 symbolicRDIVtest(SrcCoeff, DstCoeff, SrcConst, DstConst, CurLoop, CurLoop);
2196 const SCEV *DstConst = Dst;
2198 Level = mapSrcLoop(CurLoop);
2199 return weakZeroDstSIVtest(SrcCoeff, SrcConst, DstConst, CurLoop,
2200 Level, Result, NewConstraint) ||
2201 gcdMIVtest(Src, Dst, Result);
2206 const SCEV *SrcConst = Src;
2208 Level = mapDstLoop(CurLoop);
2209 return weakZeroSrcSIVtest(DstCoeff, SrcConst, DstConst,
2210 CurLoop,
Level, Result, NewConstraint) ||
2211 gcdMIVtest(Src, Dst, Result);
2231 bool DependenceInfo::testRDIV(
const SCEV *Src,
const SCEV *Dst,
2239 const SCEV *SrcConst, *DstConst;
2240 const SCEV *SrcCoeff, *DstCoeff;
2241 const Loop *SrcLoop, *DstLoop;
2247 if (SrcAddRec && DstAddRec) {
2250 SrcLoop = SrcAddRec->
getLoop();
2253 DstLoop = DstAddRec->
getLoop();
2255 else if (SrcAddRec) {
2257 dyn_cast<SCEVAddRecExpr>(SrcAddRec->
getStart())) {
2258 SrcConst = tmpAddRec->getStart();
2259 SrcCoeff = tmpAddRec->getStepRecurrence(*SE);
2260 SrcLoop = tmpAddRec->getLoop();
2263 DstLoop = SrcAddRec->
getLoop();
2268 else if (DstAddRec) {
2270 dyn_cast<SCEVAddRecExpr>(DstAddRec->
getStart())) {
2271 DstConst = tmpAddRec->getStart();
2272 DstCoeff = tmpAddRec->getStepRecurrence(*SE);
2273 DstLoop = tmpAddRec->getLoop();
2276 SrcLoop = DstAddRec->
getLoop();
2283 return exactRDIVtest(SrcCoeff, DstCoeff,
2287 gcdMIVtest(Src, Dst, Result) ||
2288 symbolicRDIVtest(SrcCoeff, DstCoeff,
2297 bool DependenceInfo::testMIV(
const SCEV *Src,
const SCEV *Dst,
2302 Result.Consistent =
false;
2303 return gcdMIVtest(Src, Dst, Result) ||
2304 banerjeeMIVtest(Src, Dst,
Loops, Result);
2312 if (
const auto *
Constant = dyn_cast<SCEVConstant>(Expr))
2314 else if (
const auto *Product = dyn_cast<SCEVMulExpr>(Expr))
2315 if (
const auto *
Constant = dyn_cast<SCEVConstant>(Product->getOperand(0)))
2339 bool DependenceInfo::gcdMIVtest(
const SCEV *Src,
const SCEV *Dst,
2350 const SCEV *Coefficients = Src;
2352 dyn_cast<SCEVAddRecExpr>(Coefficients)) {
2363 const SCEV *SrcConst = Coefficients;
2371 dyn_cast<SCEVAddRecExpr>(Coefficients)) {
2382 const SCEV *DstConst = Coefficients;
2388 if (
const SCEVAddExpr *Sum = dyn_cast<SCEVAddExpr>(Delta)) {
2390 for (
unsigned Op = 0, Ops = Sum->getNumOperands();
Op < Ops;
Op++) {
2391 const SCEV *Operand = Sum->getOperand(
Op);
2392 if (isa<SCEVConstant>(Operand)) {
2394 Constant = cast<SCEVConstant>(Operand);
2396 else if (
const SCEVMulExpr *Product = dyn_cast<SCEVMulExpr>(Operand)) {
2404 ConstOpValue.
abs());
2414 if (ConstDelta == 0)
2418 APInt Remainder = ConstDelta.
srem(RunningGCD);
2419 if (Remainder != 0) {
2438 bool Improved =
false;
2441 dyn_cast<SCEVAddRecExpr>(Coefficients)) {
2444 RunningGCD = ExtraGCD;
2447 const SCEV *Inner = Src;
2448 while (RunningGCD != 1 && isa<SCEVAddRecExpr>(Inner)) {
2449 AddRec = cast<SCEVAddRecExpr>(Inner);
2451 if (CurLoop == AddRec->
getLoop())
2465 while (RunningGCD != 1 && isa<SCEVAddRecExpr>(Inner)) {
2466 AddRec = cast<SCEVAddRecExpr>(Inner);
2468 if (CurLoop == AddRec->
getLoop())
2492 if (RunningGCD != 0) {
2493 Remainder = ConstDelta.
srem(RunningGCD);
2495 if (Remainder != 0) {
2496 unsigned Level = mapSrcLoop(CurLoop);
2542 bool DependenceInfo::banerjeeMIVtest(
const SCEV *Src,
const SCEV *Dst,
2546 ++BanerjeeApplications;
2549 CoefficientInfo *
A = collectCoeffInfo(Src,
true, A0);
2552 CoefficientInfo *
B = collectCoeffInfo(Dst,
false, B0);
2553 BoundInfo *Bound =
new BoundInfo[MaxLevels + 1];
2559 for (
unsigned K = 1; K <= MaxLevels; ++K) {
2560 Bound[K].Iterations =
A[K].Iterations ?
A[K].Iterations :
B[K].Iterations;
2563 findBoundsALL(A,
B, Bound, K);
2578 bool Disproved =
false;
2581 unsigned DepthExpanded = 0;
2582 unsigned NewDeps = exploreDirections(1, A,
B, Bound,
2583 Loops, DepthExpanded, Delta);
2585 bool Improved =
false;
2586 for (
unsigned K = 1; K <= CommonLevels; ++K) {
2588 unsigned Old =
Result.DV[K - 1].Direction;
2589 Result.DV[K - 1].Direction = Old & Bound[K].DirSet;
2590 Improved |= Old !=
Result.DV[K - 1].Direction;
2591 if (!
Result.DV[K - 1].Direction) {
2599 ++BanerjeeSuccesses;
2602 ++BanerjeeIndependence;
2607 ++BanerjeeIndependence;
2622 unsigned DependenceInfo::exploreDirections(
unsigned Level, CoefficientInfo *A,
2623 CoefficientInfo *
B, BoundInfo *Bound,
2625 unsigned &DepthExpanded,
2626 const SCEV *Delta)
const {
2632 LLVM_DEBUG(
dbgs() <<
"Number of common levels exceeded the threshold. MIV "
2633 "direction exploration is terminated.\n");
2634 for (
unsigned K = 1; K <= CommonLevels; ++K)
2640 if (
Level > CommonLevels) {
2643 for (
unsigned K = 1; K <= CommonLevels; ++K) {
2645 Bound[K].DirSet |= Bound[K].Direction;
2670 if (
Level > DepthExpanded) {
2671 DepthExpanded =
Level;
2673 findBoundsLT(A,
B, Bound,
Level);
2674 findBoundsGT(A,
B, Bound,
Level);
2675 findBoundsEQ(A,
B, Bound,
Level);
2714 unsigned NewDeps = 0;
2718 NewDeps += exploreDirections(
Level + 1, A,
B, Bound,
2719 Loops, DepthExpanded, Delta);
2723 NewDeps += exploreDirections(
Level + 1, A,
B, Bound,
2724 Loops, DepthExpanded, Delta);
2728 NewDeps += exploreDirections(
Level + 1, A,
B, Bound,
2729 Loops, DepthExpanded, Delta);
2735 return exploreDirections(
Level + 1, A,
B, Bound,
Loops, DepthExpanded, Delta);
2740 bool DependenceInfo::testBounds(
unsigned char DirKind,
unsigned Level,
2741 BoundInfo *Bound,
const SCEV *Delta)
const {
2742 Bound[
Level].Direction = DirKind;
2743 if (
const SCEV *LowerBound = getLowerBound(Bound))
2746 if (
const SCEV *UpperBound = getUpperBound(Bound))
2768 void DependenceInfo::findBoundsALL(CoefficientInfo *A, CoefficientInfo *
B,
2769 BoundInfo *Bound,
unsigned K)
const {
2772 if (Bound[K].Iterations) {
2775 Bound[K].Iterations);
2778 Bound[K].Iterations);
2807 void DependenceInfo::findBoundsEQ(CoefficientInfo *A, CoefficientInfo *
B,
2808 BoundInfo *Bound,
unsigned K)
const {
2811 if (Bound[K].Iterations) {
2813 const SCEV *NegativePart = getNegativePart(Delta);
2815 SE->
getMulExpr(NegativePart, Bound[K].Iterations);
2816 const SCEV *PositivePart = getPositivePart(Delta);
2818 SE->
getMulExpr(PositivePart, Bound[K].Iterations);
2824 const SCEV *NegativePart = getNegativePart(Delta);
2825 if (NegativePart->
isZero())
2827 const SCEV *PositivePart = getPositivePart(Delta);
2828 if (PositivePart->
isZero())
2847 void DependenceInfo::findBoundsLT(CoefficientInfo *A, CoefficientInfo *
B,
2848 BoundInfo *Bound,
unsigned K)
const {
2851 if (Bound[K].Iterations) {
2853 Bound[K].Iterations, SE->
getOne(Bound[K].Iterations->getType()));
2854 const SCEV *NegPart =
2855 getNegativePart(SE->
getMinusSCEV(A[K].NegPart,
B[K].Coeff));
2858 const SCEV *PosPart =
2859 getPositivePart(SE->
getMinusSCEV(A[K].PosPart,
B[K].Coeff));
2866 const SCEV *NegPart =
2867 getNegativePart(SE->
getMinusSCEV(A[K].NegPart,
B[K].Coeff));
2870 const SCEV *PosPart =
2871 getPositivePart(SE->
getMinusSCEV(A[K].PosPart,
B[K].Coeff));
2891 void DependenceInfo::findBoundsGT(CoefficientInfo *A, CoefficientInfo *
B,
2892 BoundInfo *Bound,
unsigned K)
const {
2895 if (Bound[K].Iterations) {
2897 Bound[K].Iterations, SE->
getOne(Bound[K].Iterations->getType()));
2898 const SCEV *NegPart =
2899 getNegativePart(SE->
getMinusSCEV(A[K].Coeff,
B[K].PosPart));
2902 const SCEV *PosPart =
2903 getPositivePart(SE->
getMinusSCEV(A[K].Coeff,
B[K].NegPart));
2910 const SCEV *NegPart = getNegativePart(SE->
getMinusSCEV(A[K].Coeff,
B[K].PosPart));
2913 const SCEV *PosPart = getPositivePart(SE->
getMinusSCEV(A[K].Coeff,
B[K].NegPart));
2921 const SCEV *DependenceInfo::getPositivePart(
const SCEV *
X)
const {
2927 const SCEV *DependenceInfo::getNegativePart(
const SCEV *
X)
const {
2935 DependenceInfo::CoefficientInfo *
2936 DependenceInfo::collectCoeffInfo(
const SCEV *Subscript,
bool SrcFlag,
2939 CoefficientInfo *CI =
new CoefficientInfo[MaxLevels + 1];
2940 for (
unsigned K = 1; K <= MaxLevels; ++K) {
2942 CI[K].PosPart = Zero;
2943 CI[K].NegPart = Zero;
2944 CI[K].Iterations =
nullptr;
2946 while (
const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(Subscript)) {
2948 unsigned K = SrcFlag ? mapSrcLoop(L) : mapDstLoop(L);
2950 CI[K].PosPart = getPositivePart(CI[K].Coeff);
2951 CI[K].NegPart = getNegativePart(CI[K].Coeff);
2952 CI[K].Iterations = collectUpperBound(L, Subscript->
getType());
2958 for (
unsigned K = 1; K <= MaxLevels; ++K) {
2965 if (CI[K].Iterations)
2981 const SCEV *DependenceInfo::getLowerBound(BoundInfo *Bound)
const {
2982 const SCEV *Sum = Bound[1].Lower[Bound[1].Direction];
2983 for (
unsigned K = 2; Sum && K <= MaxLevels; ++K) {
2997 const SCEV *DependenceInfo::getUpperBound(BoundInfo *Bound)
const {
2998 const SCEV *Sum = Bound[1].Upper[Bound[1].Direction];
2999 for (
unsigned K = 2; Sum && K <= MaxLevels; ++K) {
3018 const SCEV *DependenceInfo::findCoefficient(
const SCEV *Expr,
3019 const Loop *TargetLoop)
const {
3023 if (AddRec->
getLoop() == TargetLoop)
3025 return findCoefficient(AddRec->
getStart(), TargetLoop);
3034 const SCEV *DependenceInfo::zeroCoefficient(
const SCEV *Expr,
3035 const Loop *TargetLoop)
const {
3039 if (AddRec->
getLoop() == TargetLoop)
3053 const SCEV *DependenceInfo::addToCoefficient(
const SCEV *Expr,
3054 const Loop *TargetLoop,
3062 if (AddRec->
getLoop() == TargetLoop) {
3090 bool DependenceInfo::propagate(
const SCEV *&Src,
const SCEV *&Dst,
3095 for (
unsigned LI :
Loops.set_bits()) {
3098 if (Constraints[LI].isDistance())
3099 Result |= propagateDistance(Src, Dst, Constraints[LI], Consistent);
3100 else if (Constraints[LI].isLine())
3101 Result |= propagateLine(Src, Dst, Constraints[LI], Consistent);
3102 else if (Constraints[LI].isPoint())
3103 Result |= propagatePoint(Src, Dst, Constraints[LI]);
3114 bool DependenceInfo::propagateDistance(
const SCEV *&Src,
const SCEV *&Dst,
3115 Constraint &CurConstraint,
3117 const Loop *CurLoop = CurConstraint.getAssociatedLoop();
3119 const SCEV *A_K = findCoefficient(Src, CurLoop);
3124 Src = zeroCoefficient(Src, CurLoop);
3129 if (!findCoefficient(Dst, CurLoop)->
isZero())
3140 bool DependenceInfo::propagateLine(
const SCEV *&Src,
const SCEV *&Dst,
3141 Constraint &CurConstraint,
3143 const Loop *CurLoop = CurConstraint.getAssociatedLoop();
3144 const SCEV *
A = CurConstraint.getA();
3145 const SCEV *
B = CurConstraint.getB();
3146 const SCEV *
C = CurConstraint.getC();
3154 if (!Bconst || !Cconst)
return false;
3158 assert(Charlie.
srem(Beta) == 0 &&
"C should be evenly divisible by B");
3159 const SCEV *AP_K = findCoefficient(Dst, CurLoop);
3162 Dst = zeroCoefficient(Dst, CurLoop);
3163 if (!findCoefficient(Src, CurLoop)->
isZero())
3166 else if (
B->isZero()) {
3167 const SCEVConstant *Aconst = dyn_cast<SCEVConstant>(A);
3169 if (!Aconst || !Cconst)
return false;
3173 assert(Charlie.
srem(Alpha) == 0 &&
"C should be evenly divisible by A");
3174 const SCEV *A_K = findCoefficient(Src, CurLoop);
3176 Src = zeroCoefficient(Src, CurLoop);
3177 if (!findCoefficient(Dst, CurLoop)->
isZero())
3181 const SCEVConstant *Aconst = dyn_cast<SCEVConstant>(A);
3183 if (!Aconst || !Cconst)
return false;
3187 assert(Charlie.
srem(Alpha) == 0 &&
"C should be evenly divisible by A");
3188 const SCEV *A_K = findCoefficient(Src, CurLoop);
3190 Src = zeroCoefficient(Src, CurLoop);
3191 Dst = addToCoefficient(Dst, CurLoop, A_K);
3192 if (!findCoefficient(Dst, CurLoop)->
isZero())
3197 const SCEV *A_K = findCoefficient(Src, CurLoop);
3201 Src = zeroCoefficient(Src, CurLoop);
3202 Dst = addToCoefficient(Dst, CurLoop, SE->
getMulExpr(A_K,
B));
3203 if (!findCoefficient(Dst, CurLoop)->
isZero())
3215 bool DependenceInfo::propagatePoint(
const SCEV *&Src,
const SCEV *&Dst,
3216 Constraint &CurConstraint) {
3217 const Loop *CurLoop = CurConstraint.getAssociatedLoop();
3218 const SCEV *A_K = findCoefficient(Src, CurLoop);
3219 const SCEV *AP_K = findCoefficient(Dst, CurLoop);
3224 Src = zeroCoefficient(Src, CurLoop);
3227 Dst = zeroCoefficient(Dst, CurLoop);
3235 const Constraint &CurConstraint)
const {
3238 if (CurConstraint.isAny())
3240 else if (CurConstraint.isDistance()) {
3242 Level.Scalar =
false;
3243 Level.Distance = CurConstraint.getD();
3251 Level.Direction &= NewDirection;
3253 else if (CurConstraint.isLine()) {
3254 Level.Scalar =
false;
3255 Level.Distance =
nullptr;
3258 else if (CurConstraint.isPoint()) {
3259 Level.Scalar =
false;
3260 Level.Distance =
nullptr;
3263 CurConstraint.getY(),
3264 CurConstraint.getX()))
3268 CurConstraint.getY(),
3269 CurConstraint.getX()))
3273 CurConstraint.getY(),
3274 CurConstraint.getX()))
3277 Level.Direction &= NewDirection;
3302 if (!SrcBase || !DstBase || SrcBase != DstBase)
3307 if (!tryDelinearizeFixedSize(Src, Dst, SrcAccessFn, DstAccessFn,
3308 SrcSubscripts, DstSubscripts) &&
3309 !tryDelinearizeParametricSize(Src, Dst, SrcAccessFn, DstAccessFn,
3310 SrcSubscripts, DstSubscripts))
3313 int Size = SrcSubscripts.size();
3315 dbgs() <<
"\nSrcSubscripts: ";
3316 for (
int I = 0;
I <
Size;
I++)
3317 dbgs() << *SrcSubscripts[
I];
3318 dbgs() <<
"\nDstSubscripts: ";
3319 for (
int I = 0;
I <
Size;
I++)
3320 dbgs() << *DstSubscripts[
I];
3328 for (
int I = 0;
I <
Size; ++
I) {
3329 Pair[
I].Src = SrcSubscripts[
I];
3330 Pair[
I].Dst = DstSubscripts[
I];
3331 unifySubscriptType(&Pair[
I]);
3340 bool DependenceInfo::tryDelinearizeFixedSize(
3349 assert(SrcBase && DstBase && SrcBase == DstBase &&
3350 "expected src and dst scev unknowns to be equal");
3363 if (SrcSizes.size() != DstSizes.size() ||
3364 !
std::equal(SrcSizes.begin(), SrcSizes.end(), DstSizes.begin())) {
3365 SrcSubscripts.
clear();
3366 DstSubscripts.
clear();
3370 assert(SrcSubscripts.size() == DstSubscripts.size() &&
3371 "Expected equal number of entries in the list of SrcSubscripts and "
3387 size_t SSize = Subscripts.size();
3388 for (
size_t I = 1;
I < SSize; ++
I) {
3389 const SCEV *
S = Subscripts[
I];
3390 if (!isKnownNonNegative(
S, Ptr))
3392 if (
auto *SType = dyn_cast<IntegerType>(
S->getType())) {
3395 if (!isKnownLessThan(
S, Range))
3402 if (!AllIndiciesInRange(SrcSizes, SrcSubscripts, SrcPtr) ||
3403 !AllIndiciesInRange(DstSizes, DstSubscripts, DstPtr)) {
3404 SrcSubscripts.
clear();
3405 DstSubscripts.
clear();
3410 dbgs() <<
"Delinearized subscripts of fixed-size array\n"
3411 <<
"SrcGEP:" << *SrcPtr <<
"\n"
3412 <<
"DstGEP:" << *DstPtr <<
"\n";
3417 bool DependenceInfo::tryDelinearizeParametricSize(
3428 assert(SrcBase && DstBase && SrcBase == DstBase &&
3429 "expected src and dst scev unknowns to be equal");
3457 if (SrcSubscripts.size() < 2 || DstSubscripts.size() < 2 ||
3458 SrcSubscripts.size() != DstSubscripts.size())
3461 size_t Size = SrcSubscripts.size();
3470 for (
size_t I = 1;
I <
Size; ++
I) {
3471 if (!isKnownNonNegative(SrcSubscripts[
I], SrcPtr))
3474 if (!isKnownLessThan(SrcSubscripts[
I], Sizes[
I - 1]))
3477 if (!isKnownNonNegative(DstSubscripts[
I], DstPtr))
3480 if (!isKnownLessThan(DstSubscripts[
I], Sizes[
I - 1]))
3526 std::unique_ptr<Dependence>
3528 bool PossiblyLoopIndependent) {
3530 PossiblyLoopIndependent =
false;
3532 if (!(Src->mayReadOrWriteMemory() && Dst->mayReadOrWriteMemory()))
3538 LLVM_DEBUG(
dbgs() <<
"can only handle simple loads and stores\n");
3539 return std::make_unique<Dependence>(Src, Dst);
3554 return std::make_unique<Dependence>(Src, Dst);
3564 establishNestingLevels(Src, Dst);
3565 LLVM_DEBUG(
dbgs() <<
" common nesting levels = " << CommonLevels <<
"\n");
3566 LLVM_DEBUG(
dbgs() <<
" maximum nesting levels = " << MaxLevels <<
"\n");
3568 FullDependence Result(Src, Dst, PossiblyLoopIndependent, CommonLevels);
3584 LLVM_DEBUG(
dbgs() <<
"can't analyze SCEV with different pointer base\n");
3585 return std::make_unique<Dependence>(Src, Dst);
3587 Pair[0].Src = SrcSCEV;
3588 Pair[0].Dst = DstSCEV;
3591 if (tryDelinearize(Src, Dst, Pair)) {
3593 Pairs = Pair.size();
3597 for (
unsigned P = 0;
P < Pairs; ++
P) {
3598 Pair[
P].Loops.
resize(MaxLevels + 1);
3599 Pair[
P].GroupLoops.
resize(MaxLevels + 1);
3601 removeMatchingExtensions(&Pair[
P]);
3602 Pair[
P].Classification =
3603 classifyPair(Pair[
P].Src, LI->
getLoopFor(Src->getParent()),
3606 Pair[
P].GroupLoops = Pair[
P].Loops;
3607 Pair[
P].Group.set(
P);
3676 for (
unsigned SI = 0;
SI < Pairs; ++
SI) {
3677 if (Pair[
SI].Classification == Subscript::NonLinear) {
3679 ++NonlinearSubscriptPairs;
3680 collectCommonLoops(Pair[
SI].Src,
3683 collectCommonLoops(Pair[
SI].Dst,
3686 Result.Consistent =
false;
3687 }
else if (Pair[
SI].Classification == Subscript::ZIV) {
3694 for (
unsigned SJ =
SI + 1; SJ < Pairs; ++SJ) {
3696 Intersection &= Pair[SJ].GroupLoops;
3697 if (Intersection.
any()) {
3699 Pair[SJ].GroupLoops |= Pair[
SI].GroupLoops;
3701 Pair[SJ].Group |= Pair[
SI].Group;
3706 if (Pair[
SI].Group.count() == 1) {
3708 ++SeparableSubscriptPairs;
3712 ++CoupledSubscriptPairs;
3723 Constraint NewConstraint;
3724 NewConstraint.setAny(SE);
3729 switch (Pair[
SI].Classification) {
3730 case Subscript::ZIV:
3732 if (testZIV(Pair[
SI].Src, Pair[
SI].Dst, Result))
3735 case Subscript::SIV: {
3738 const SCEV *SplitIter =
nullptr;
3739 if (testSIV(Pair[
SI].Src, Pair[
SI].Dst,
Level, Result, NewConstraint,
3744 case Subscript::RDIV:
3746 if (testRDIV(Pair[
SI].Src, Pair[
SI].Dst, Result))
3749 case Subscript::MIV:
3751 if (testMIV(Pair[
SI].Src, Pair[
SI].Dst, Pair[
SI].
Loops, Result))
3759 if (Coupled.
count()) {
3762 LLVM_DEBUG(
dbgs() <<
"MaxLevels + 1 = " << MaxLevels + 1 <<
"\n");
3764 for (
unsigned II = 0; II <= MaxLevels; ++II)
3765 Constraints[II].setAny(SE);
3773 for (
unsigned SJ : Group.
set_bits()) {
3775 if (Pair[SJ].Classification == Subscript::SIV)
3779 PairsInGroup.push_back(&Pair[SJ]);
3781 unifySubscriptType(PairsInGroup);
3783 while (Sivs.
any()) {
3784 bool Changed =
false;
3785 for (
unsigned SJ : Sivs.
set_bits()) {
3789 const SCEV *SplitIter =
nullptr;
3791 if (testSIV(Pair[SJ].Src, Pair[SJ].Dst,
Level, Result, NewConstraint,
3795 if (intersectConstraints(&Constraints[
Level], &NewConstraint)) {
3796 if (Constraints[
Level].isEmpty()) {
3797 ++DeltaIndependence;
3809 for (
unsigned SJ : Mivs.
set_bits()) {
3812 if (propagate(Pair[SJ].Src, Pair[SJ].Dst, Pair[SJ].
Loops,
3813 Constraints, Result.Consistent)) {
3815 ++DeltaPropagations;
3816 Pair[SJ].Classification =
3817 classifyPair(Pair[SJ].Src, LI->
getLoopFor(Src->getParent()),
3818 Pair[SJ].Dst, LI->
getLoopFor(Dst->getParent()),
3820 switch (Pair[SJ].Classification) {
3821 case Subscript::ZIV:
3823 if (testZIV(Pair[SJ].Src, Pair[SJ].Dst, Result))
3827 case Subscript::SIV:
3831 case Subscript::RDIV:
3832 case Subscript::MIV:
3843 for (
unsigned SJ : Mivs.
set_bits()) {
3844 if (Pair[SJ].Classification == Subscript::RDIV) {
3846 if (testRDIV(Pair[SJ].Src, Pair[SJ].Dst, Result))
3856 for (
unsigned SJ : Mivs.
set_bits()) {
3857 if (Pair[SJ].Classification == Subscript::MIV) {
3859 if (testMIV(Pair[SJ].Src, Pair[SJ].Dst, Pair[SJ].
Loops, Result))
3868 for (
unsigned SJ : ConstrainedLevels.
set_bits()) {
3869 if (SJ > CommonLevels)
3871 updateDirection(Result.DV[SJ - 1], Constraints[SJ]);
3880 for (
unsigned SI = 0;
SI < Pairs; ++
SI)
3881 CompleteLoops |= Pair[
SI].
Loops;
3882 for (
unsigned II = 1; II <= CommonLevels; ++II)
3883 if (CompleteLoops[II])
3884 Result.DV[II - 1].Scalar =
false;
3886 if (PossiblyLoopIndependent) {
3890 for (
unsigned II = 1; II <= CommonLevels; ++II) {
3892 Result.LoopIndependent =
false;
3900 bool AllEqual =
true;
3901 for (
unsigned II = 1; II <= CommonLevels; ++II) {
3911 return std::make_unique<FullDependence>(
std::move(Result));
3962 unsigned SplitLevel) {
3964 "Dep should be splitable at SplitLevel");
3967 assert(Src->mayReadFromMemory() || Src->mayWriteToMemory());
3968 assert(Dst->mayReadFromMemory() || Dst->mayWriteToMemory());
3978 establishNestingLevels(Src, Dst);
3986 Pair[0].Src = SrcSCEV;
3987 Pair[0].Dst = DstSCEV;
3990 if (tryDelinearize(Src, Dst, Pair)) {
3992 Pairs = Pair.size();
3996 for (
unsigned P = 0;
P < Pairs; ++
P) {
3997 Pair[
P].Loops.
resize(MaxLevels + 1);
3998 Pair[
P].GroupLoops.
resize(MaxLevels + 1);
4000 removeMatchingExtensions(&Pair[
P]);
4001 Pair[
P].Classification =
4002 classifyPair(Pair[
P].Src, LI->
getLoopFor(Src->getParent()),
4005 Pair[
P].GroupLoops = Pair[
P].Loops;
4006 Pair[
P].Group.set(
P);
4013 for (
unsigned SI = 0;
SI < Pairs; ++
SI) {
4014 if (Pair[
SI].Classification == Subscript::NonLinear) {
4016 collectCommonLoops(Pair[
SI].Src,
4019 collectCommonLoops(Pair[
SI].Dst,
4022 Result.Consistent =
false;
4024 else if (Pair[
SI].Classification == Subscript::ZIV)
4029 for (
unsigned SJ =
SI + 1; SJ < Pairs; ++SJ) {
4031 Intersection &= Pair[SJ].GroupLoops;
4032 if (Intersection.
any()) {
4034 Pair[SJ].GroupLoops |= Pair[
SI].GroupLoops;
4036 Pair[SJ].Group |= Pair[
SI].Group;
4041 if (Pair[
SI].Group.count() == 1)
4049 Constraint NewConstraint;
4050 NewConstraint.setAny(SE);
4054 switch (Pair[
SI].Classification) {
4055 case Subscript::SIV: {
4057 const SCEV *SplitIter =
nullptr;
4058 (void) testSIV(Pair[
SI].Src, Pair[
SI].Dst,
Level,
4059 Result, NewConstraint, SplitIter);
4060 if (
Level == SplitLevel) {
4061 assert(SplitIter !=
nullptr);
4066 case Subscript::ZIV:
4067 case Subscript::RDIV:
4068 case Subscript::MIV:
4075 if (Coupled.
count()) {
4078 for (
unsigned II = 0; II <= MaxLevels; ++II)
4079 Constraints[II].setAny(SE);
4085 for (
unsigned SJ : Group.
set_bits()) {
4086 if (Pair[SJ].Classification == Subscript::SIV)
4091 while (Sivs.
any()) {
4092 bool Changed =
false;
4093 for (
unsigned SJ : Sivs.
set_bits()) {
4096 const SCEV *SplitIter =
nullptr;
4097 (void) testSIV(Pair[SJ].Src, Pair[SJ].Dst,
Level,
4098 Result, NewConstraint, SplitIter);
4099 if (
Level == SplitLevel && SplitIter)
4102 if (intersectConstraints(&Constraints[
Level], &NewConstraint))
4108 for (
unsigned SJ : Mivs.
set_bits()) {
4110 if (propagate(Pair[SJ].Src, Pair[SJ].Dst,
4111 Pair[SJ].
Loops, Constraints, Result.Consistent)) {
4112 Pair[SJ].Classification =
4113 classifyPair(Pair[SJ].Src, LI->
getLoopFor(Src->getParent()),
4114 Pair[SJ].Dst, LI->
getLoopFor(Dst->getParent()),
4116 switch (Pair[SJ].Classification) {
4117 case Subscript::ZIV:
4120 case Subscript::SIV:
4124 case Subscript::RDIV:
4125 case Subscript::MIV: