Lines Matching +full:upper +full:- +full:bound +full:- +full:check
1 //===-- DependenceAnalysis.cpp - DA Implementation --------------*- C++ -*-===//
8 //===----------------------------------------------------------------------===//
20 // or a more-or-less detailed description of the dependence between them.
23 // coupled RDIV subscripts and lacks a multi-subscript MIV test.
29 // analysis is using SCEV->delinearize to recover the representation of multiple
31 // delinearization is controlled by the flag -da-delinearize.
37 // Some non-linear subscript pairs can be handled by the GCD test
48 //===----------------------------------------------------------------------===//
50 // In memory of Ken Kennedy, 1945 - 2007 //
52 //===----------------------------------------------------------------------===//
74 //===----------------------------------------------------------------------===//
86 STATISTIC(WeakCrossingSIVapplications, "Weak-Crossing SIV applications");
87 STATISTIC(WeakCrossingSIVsuccesses, "Weak-Crossing SIV successes");
88 STATISTIC(WeakCrossingSIVindependence, "Weak-Crossing SIV independence");
92 STATISTIC(WeakZeroSIVapplications, "Weak-Zero SIV applications");
93 STATISTIC(WeakZeroSIVsuccesses, "Weak-Zero SIV successes");
94 STATISTIC(WeakZeroSIVindependence, "Weak-Zero SIV independence");
111 Delinearize("da-delinearize", cl::init(false), cl::Hidden, cl::ZeroOrMore,
114 //===----------------------------------------------------------------------===//
166 auto *F = DA->getFunction(); in dumpExampleDependence()
173 OS << "da analyze - "; in dumpExampleDependence()
174 if (auto D = DA->depends(&*SrcI, &*DstI, true)) { in dumpExampleDependence()
175 D->dump(OS); in dumpExampleDependence()
176 for (unsigned Level = 1; Level <= D->getLevels(); Level++) { in dumpExampleDependence()
177 if (D->isSplitable(Level)) { in dumpExampleDependence()
178 OS << "da analyze - split level = " << Level; in dumpExampleDependence()
179 OS << ", iteration = " << *DA->getSplitIteration(*D, Level); in dumpExampleDependence()
197 //===----------------------------------------------------------------------===//
202 return Src->mayReadFromMemory() && Dst->mayReadFromMemory(); in isInput()
208 return Src->mayWriteToMemory() && Dst->mayWriteToMemory(); in isOutput()
214 return Src->mayWriteToMemory() && Dst->mayReadFromMemory(); in isFlow()
220 return Src->mayReadFromMemory() && Dst->mayWriteToMemory(); in isAnti()
233 //===----------------------------------------------------------------------===//
248 // getDirection - Returns the direction associated with a particular level.
251 return DV[Level - 1].Direction; in getDirection()
258 return DV[Level - 1].Distance; in getDistance()
267 return DV[Level - 1].Scalar; in isScalar()
275 return DV[Level - 1].PeelFirst; in isPeelFirst()
283 return DV[Level - 1].PeelLast; in isPeelLast()
290 return DV[Level - 1].Splitable; in isSplitable()
294 //===----------------------------------------------------------------------===//
344 return SE->getNegativeSCEV(C); in getD()
375 A = SE->getOne(D->getType()); in setDistance()
376 B = SE->getNegativeSCEV(A); in setDistance()
377 C = SE->getNegativeSCEV(D); in setDistance()
418 DEBUG(dbgs() << "\t X ="; X->dump(dbgs())); in intersectConstraints()
419 DEBUG(dbgs() << "\t Y ="; Y->dump(dbgs())); in intersectConstraints()
420 assert(!Y->isPoint() && "Y must not be a Point"); in intersectConstraints()
421 if (X->isAny()) { in intersectConstraints()
422 if (Y->isAny()) in intersectConstraints()
427 if (X->isEmpty()) in intersectConstraints()
429 if (Y->isEmpty()) { in intersectConstraints()
430 X->setEmpty(); in intersectConstraints()
434 if (X->isDistance() && Y->isDistance()) { in intersectConstraints()
436 if (isKnownPredicate(CmpInst::ICMP_EQ, X->getD(), Y->getD())) in intersectConstraints()
438 if (isKnownPredicate(CmpInst::ICMP_NE, X->getD(), Y->getD())) { in intersectConstraints()
439 X->setEmpty(); in intersectConstraints()
445 if (isa<SCEVConstant>(Y->getD())) { in intersectConstraints()
452 // At this point, the pseudo-code in Figure 4 of the paper in intersectConstraints()
453 // checks if (X->isPoint() && Y->isPoint()). in intersectConstraints()
456 // two Line constraints, and the right-hand value, Y, is never in intersectConstraints()
458 assert(!(X->isPoint() && Y->isPoint()) && in intersectConstraints()
459 "We shouldn't ever see X->isPoint() && Y->isPoint()"); in intersectConstraints()
461 if (X->isLine() && Y->isLine()) { in intersectConstraints()
463 const SCEV *Prod1 = SE->getMulExpr(X->getA(), Y->getB()); in intersectConstraints()
464 const SCEV *Prod2 = SE->getMulExpr(X->getB(), Y->getA()); in intersectConstraints()
468 Prod1 = SE->getMulExpr(X->getC(), Y->getB()); in intersectConstraints()
469 Prod2 = SE->getMulExpr(X->getB(), Y->getC()); in intersectConstraints()
473 X->setEmpty(); in intersectConstraints()
482 const SCEV *C1B2 = SE->getMulExpr(X->getC(), Y->getB()); in intersectConstraints()
483 const SCEV *C1A2 = SE->getMulExpr(X->getC(), Y->getA()); in intersectConstraints()
484 const SCEV *C2B1 = SE->getMulExpr(Y->getC(), X->getB()); in intersectConstraints()
485 const SCEV *C2A1 = SE->getMulExpr(Y->getC(), X->getA()); in intersectConstraints()
486 const SCEV *A1B2 = SE->getMulExpr(X->getA(), Y->getB()); in intersectConstraints()
487 const SCEV *A2B1 = SE->getMulExpr(Y->getA(), X->getB()); in intersectConstraints()
489 dyn_cast<SCEVConstant>(SE->getMinusSCEV(C1A2, C2A1)); in intersectConstraints()
491 dyn_cast<SCEVConstant>(SE->getMinusSCEV(C1B2, C2B1)); in intersectConstraints()
493 dyn_cast<SCEVConstant>(SE->getMinusSCEV(A1B2, A2B1)); in intersectConstraints()
495 dyn_cast<SCEVConstant>(SE->getMinusSCEV(A2B1, A1B2)); in intersectConstraints()
499 APInt Xtop = C1B2_C2B1->getAPInt(); in intersectConstraints()
500 APInt Xbot = A1B2_A2B1->getAPInt(); in intersectConstraints()
501 APInt Ytop = C1A2_C2A1->getAPInt(); in intersectConstraints()
502 APInt Ybot = A2B1_A1B2->getAPInt(); in intersectConstraints()
514 X->setEmpty(); in intersectConstraints()
520 X->setEmpty(); in intersectConstraints()
525 collectConstantUpperBound(X->getAssociatedLoop(), Prod1->getType())) { in intersectConstraints()
526 const APInt &UpperBound = CUB->getAPInt(); in intersectConstraints()
527 DEBUG(dbgs() << "\t\tupper bound = " << UpperBound << "\n"); in intersectConstraints()
529 X->setEmpty(); in intersectConstraints()
534 X->setPoint(SE->getConstant(Xq), in intersectConstraints()
535 SE->getConstant(Yq), in intersectConstraints()
536 X->getAssociatedLoop()); in intersectConstraints()
543 // if (X->isLine() && Y->isPoint()) This case can't occur. in intersectConstraints()
544 assert(!(X->isLine() && Y->isPoint()) && "This case should never occur"); in intersectConstraints()
546 if (X->isPoint() && Y->isLine()) { in intersectConstraints()
548 const SCEV *A1X1 = SE->getMulExpr(Y->getA(), X->getX()); in intersectConstraints()
549 const SCEV *B1Y1 = SE->getMulExpr(Y->getB(), X->getY()); in intersectConstraints()
550 const SCEV *Sum = SE->getAddExpr(A1X1, B1Y1); in intersectConstraints()
551 if (isKnownPredicate(CmpInst::ICMP_EQ, Sum, Y->getC())) in intersectConstraints()
553 if (isKnownPredicate(CmpInst::ICMP_NE, Sum, Y->getC())) { in intersectConstraints()
554 X->setEmpty(); in intersectConstraints()
566 //===----------------------------------------------------------------------===//
629 return AA->alias(AObj, DL.getTypeStoreSize(AObj->getType()), in underlyingObjectsAlias()
630 BObj, DL.getTypeStoreSize(BObj->getType())); in underlyingObjectsAlias()
639 return LI->isUnordered(); in isLoadOrStore()
641 return SI->isUnordered(); in isLoadOrStore()
649 return LI->getPointerOperand(); in getPointerOperand()
651 return SI->getPointerOperand(); in getPointerOperand()
670 // 0 - unused
671 // 1 - outermost common loop
672 // ... - other common loops
673 // CommonLevels - innermost common loop
674 // ... - loops containing Src but not Dst
675 // SrcLevels - innermost loop containing Src but not Dst
676 // ... - loops containing Dst but not Src
677 // MaxLevels - innermost loops containing Dst but not Src
700 // a - 1
701 // b - 2 = CommonLevels
702 // c - 3
703 // d - 4 = SrcLevels
704 // e - 5
705 // f - 6
706 // g - 7 = MaxLevels
709 const BasicBlock *SrcBlock = Src->getParent(); in establishNestingLevels()
710 const BasicBlock *DstBlock = Dst->getParent(); in establishNestingLevels()
711 unsigned SrcLevel = LI->getLoopDepth(SrcBlock); in establishNestingLevels()
712 unsigned DstLevel = LI->getLoopDepth(DstBlock); in establishNestingLevels()
713 const Loop *SrcLoop = LI->getLoopFor(SrcBlock); in establishNestingLevels()
714 const Loop *DstLoop = LI->getLoopFor(DstBlock); in establishNestingLevels()
718 SrcLoop = SrcLoop->getParentLoop(); in establishNestingLevels()
719 SrcLevel--; in establishNestingLevels()
722 DstLoop = DstLoop->getParentLoop(); in establishNestingLevels()
723 DstLevel--; in establishNestingLevels()
726 SrcLoop = SrcLoop->getParentLoop(); in establishNestingLevels()
727 DstLoop = DstLoop->getParentLoop(); in establishNestingLevels()
728 SrcLevel--; in establishNestingLevels()
731 MaxLevels -= CommonLevels; in establishNestingLevels()
738 return SrcLoop->getLoopDepth(); in mapSrcLoop()
745 unsigned D = DstLoop->getLoopDepth(); in mapDstLoop()
747 return D - CommonLevels + SrcLevels; in mapDstLoop()
758 return SE->isLoopInvariant(Expression, LoopNest) && in isLoopInvariant()
759 isLoopInvariant(Expression, LoopNest->getParentLoop()); in isLoopInvariant()
770 unsigned Level = LoopNest->getLoopDepth(); in collectCommonLoops()
771 if (Level <= CommonLevels && !SE->isLoopInvariant(Expression, LoopNest)) in collectCommonLoops()
773 LoopNest = LoopNest->getParentLoop(); in collectCommonLoops()
785 const SCEV *Src = Pair->Src; in unifySubscriptType()
786 const SCEV *Dst = Pair->Dst; in unifySubscriptType()
787 IntegerType *SrcTy = dyn_cast<IntegerType>(Src->getType()); in unifySubscriptType()
788 IntegerType *DstTy = dyn_cast<IntegerType>(Dst->getType()); in unifySubscriptType()
795 if (SrcTy->getBitWidth() > widestWidthSeen) { in unifySubscriptType()
796 widestWidthSeen = SrcTy->getBitWidth(); in unifySubscriptType()
799 if (DstTy->getBitWidth() > widestWidthSeen) { in unifySubscriptType()
800 widestWidthSeen = DstTy->getBitWidth(); in unifySubscriptType()
810 const SCEV *Src = Pair->Src; in unifySubscriptType()
811 const SCEV *Dst = Pair->Dst; in unifySubscriptType()
812 IntegerType *SrcTy = dyn_cast<IntegerType>(Src->getType()); in unifySubscriptType()
813 IntegerType *DstTy = dyn_cast<IntegerType>(Dst->getType()); in unifySubscriptType()
820 if (SrcTy->getBitWidth() < widestWidthSeen) in unifySubscriptType()
821 // Sign-extend Src to widestType in unifySubscriptType()
822 Pair->Src = SE->getSignExtendExpr(Src, widestType); in unifySubscriptType()
823 if (DstTy->getBitWidth() < widestWidthSeen) { in unifySubscriptType()
824 // Sign-extend Dst to widestType in unifySubscriptType()
825 Pair->Dst = SE->getSignExtendExpr(Dst, widestType); in unifySubscriptType()
830 // removeMatchingExtensions - Examines a subscript pair.
835 const SCEV *Src = Pair->Src; in removeMatchingExtensions()
836 const SCEV *Dst = Pair->Dst; in removeMatchingExtensions()
841 const SCEV *SrcCastOp = SrcCast->getOperand(); in removeMatchingExtensions()
842 const SCEV *DstCastOp = DstCast->getOperand(); in removeMatchingExtensions()
843 if (SrcCastOp->getType() == DstCastOp->getType()) { in removeMatchingExtensions()
844 Pair->Src = SrcCastOp; in removeMatchingExtensions()
845 Pair->Dst = DstCastOp; in removeMatchingExtensions()
858 const SCEV *Start = AddRec->getStart(); in checkSrcSubscript()
859 const SCEV *Step = AddRec->getStepRecurrence(*SE); in checkSrcSubscript()
860 const SCEV *UB = SE->getBackedgeTakenCount(AddRec->getLoop()); in checkSrcSubscript()
862 if (SE->getTypeSizeInBits(Start->getType()) < in checkSrcSubscript()
863 SE->getTypeSizeInBits(UB->getType())) { in checkSrcSubscript()
864 if (!AddRec->getNoWrapFlags()) in checkSrcSubscript()
870 Loops.set(mapSrcLoop(AddRec->getLoop())); in checkSrcSubscript()
883 const SCEV *Start = AddRec->getStart(); in checkDstSubscript()
884 const SCEV *Step = AddRec->getStepRecurrence(*SE); in checkDstSubscript()
885 const SCEV *UB = SE->getBackedgeTakenCount(AddRec->getLoop()); in checkDstSubscript()
887 if (SE->getTypeSizeInBits(Start->getType()) < in checkDstSubscript()
888 SE->getTypeSizeInBits(UB->getType())) { in checkDstSubscript()
889 if (!AddRec->getNoWrapFlags()) in checkDstSubscript()
895 Loops.set(mapDstLoop(AddRec->getLoop())); in checkDstSubscript()
948 const SCEV *Xop = CX->getOperand(); in isKnownPredicate()
949 const SCEV *Yop = CY->getOperand(); in isKnownPredicate()
950 if (Xop->getType() == Yop->getType()) { in isKnownPredicate()
956 if (SE->isKnownPredicate(Pred, X, Y)) in isKnownPredicate()
958 // If SE->isKnownPredicate can't prove the condition, in isKnownPredicate()
959 // we try the brute-force approach of subtracting in isKnownPredicate()
961 // By testing with SE->isKnownPredicate first, we avoid in isKnownPredicate()
963 const SCEV *Delta = SE->getMinusSCEV(X, Y); in isKnownPredicate()
966 return Delta->isZero(); in isKnownPredicate()
968 return SE->isKnownNonZero(Delta); in isKnownPredicate()
970 return SE->isKnownNonNegative(Delta); in isKnownPredicate()
972 return SE->isKnownNonPositive(Delta); in isKnownPredicate()
974 return SE->isKnownPositive(Delta); in isKnownPredicate()
976 return SE->isKnownNegative(Delta); in isKnownPredicate()
984 // Loop bound may be smaller (e.g., a char).
985 // Should zero extend loop bound, since it's always >= 0.
986 // This routine collects upper bound and extends or truncates if needed.
989 // Return null if no bound available.
991 if (SE->hasLoopInvariantBackedgeTakenCount(L)) { in collectUpperBound()
992 const SCEV *UB = SE->getBackedgeTakenCount(L); in collectUpperBound()
993 return SE->getTruncateOrZeroExtend(UB, T); in collectUpperBound()
1009 // testZIV -
1039 // strongSIVtest -
1055 // d = i' - i = (c1 - c2)/a
1058 // loop's upper bound. If a dependence exists, the dependence direction is
1072 DEBUG(dbgs() << ", " << *Coeff->getType() << "\n"); in strongSIVtest()
1074 DEBUG(dbgs() << ", " << *SrcConst->getType() << "\n"); in strongSIVtest()
1076 DEBUG(dbgs() << ", " << *DstConst->getType() << "\n"); in strongSIVtest()
1079 Level--; in strongSIVtest()
1081 const SCEV *Delta = SE->getMinusSCEV(SrcConst, DstConst); in strongSIVtest()
1083 DEBUG(dbgs() << ", " << *Delta->getType() << "\n"); in strongSIVtest()
1085 // check that |Delta| < iteration count in strongSIVtest()
1086 if (const SCEV *UpperBound = collectUpperBound(CurLoop, Delta->getType())) { in strongSIVtest()
1088 DEBUG(dbgs() << ", " << *UpperBound->getType() << "\n"); in strongSIVtest()
1090 SE->isKnownNonNegative(Delta) ? Delta : SE->getNegativeSCEV(Delta); in strongSIVtest()
1092 SE->isKnownNonNegative(Coeff) ? Coeff : SE->getNegativeSCEV(Coeff); in strongSIVtest()
1093 const SCEV *Product = SE->getMulExpr(UpperBound, AbsCoeff); in strongSIVtest()
1095 // Distance greater than trip count - no dependence in strongSIVtest()
1104 APInt ConstDelta = cast<SCEVConstant>(Delta)->getAPInt(); in strongSIVtest()
1105 APInt ConstCoeff = cast<SCEVConstant>(Coeff)->getAPInt(); in strongSIVtest()
1118 Result.DV[Level].Distance = SE->getConstant(Distance); in strongSIVtest()
1119 NewConstraint.setDistance(SE->getConstant(Distance), CurLoop); in strongSIVtest()
1128 else if (Delta->isZero()) { in strongSIVtest()
1136 if (Coeff->isOne()) { in strongSIVtest()
1144 SE->getNegativeSCEV(Coeff), in strongSIVtest()
1145 SE->getNegativeSCEV(Delta), CurLoop); in strongSIVtest()
1149 bool DeltaMaybeZero = !SE->isKnownNonZero(Delta); in strongSIVtest()
1150 bool DeltaMaybePositive = !SE->isKnownNonPositive(Delta); in strongSIVtest()
1151 bool DeltaMaybeNegative = !SE->isKnownNonNegative(Delta); in strongSIVtest()
1152 bool CoeffMaybePositive = !SE->isKnownNonPositive(Coeff); in strongSIVtest()
1153 bool CoeffMaybeNegative = !SE->isKnownNonNegative(Coeff); in strongSIVtest()
1155 // It helps to read !SE->isKnownNonZero(Delta) in strongSIVtest()
1174 // weakCrossingSIVtest -
1177 // When we have a pair of subscripts of the form [c1 + a*i] and [c2 - a*i],
1180 // Weak-Crossing SIV test.
1182 // Given c1 + a*i = c2 - a*i', we can look for the intersection of
1185 // c1 + a*i = c2 - a*i
1186 // 2a*i = c2 - c1
1187 // i = (c2 - c1)/2a
1194 // If the non-integer part = 1/2, there's a dependence (<> directions).
1206 DEBUG(dbgs() << "\tWeak-Crossing SIV test\n"); in weakCrossingSIVtest()
1212 Level--; in weakCrossingSIVtest()
1214 const SCEV *Delta = SE->getMinusSCEV(DstConst, SrcConst); in weakCrossingSIVtest()
1217 if (Delta->isZero()) { in weakCrossingSIVtest()
1233 if (SE->isKnownNegative(ConstCoeff)) { in weakCrossingSIVtest()
1234 ConstCoeff = dyn_cast<SCEVConstant>(SE->getNegativeSCEV(ConstCoeff)); in weakCrossingSIVtest()
1237 Delta = SE->getNegativeSCEV(Delta); in weakCrossingSIVtest()
1239 assert(SE->isKnownPositive(ConstCoeff) && "ConstCoeff should be positive"); in weakCrossingSIVtest()
1242 SplitIter = SE->getUDivExpr( in weakCrossingSIVtest()
1243 SE->getSMaxExpr(SE->getZero(Delta->getType()), Delta), in weakCrossingSIVtest()
1244 SE->getMulExpr(SE->getConstant(Delta->getType(), 2), ConstCoeff)); in weakCrossingSIVtest()
1255 if (SE->isKnownNegative(Delta)) { in weakCrossingSIVtest()
1263 // Check Delta/(2*ConstCoeff) against upper loop bound in weakCrossingSIVtest()
1264 if (const SCEV *UpperBound = collectUpperBound(CurLoop, Delta->getType())) { in weakCrossingSIVtest()
1266 const SCEV *ConstantTwo = SE->getConstant(UpperBound->getType(), 2); in weakCrossingSIVtest()
1267 const SCEV *ML = SE->getMulExpr(SE->getMulExpr(ConstCoeff, UpperBound), in weakCrossingSIVtest()
1286 Result.DV[Level].Distance = SE->getZero(Delta->getType()); in weakCrossingSIVtest()
1291 // check that Coeff divides Delta in weakCrossingSIVtest()
1292 APInt APDelta = ConstDelta->getAPInt(); in weakCrossingSIVtest()
1293 APInt APCoeff = ConstCoeff->getAPInt(); in weakCrossingSIVtest()
1327 // Also finds a solution to the equation ax - by = gcd(a, b).
1339 APInt A2 = A0 - Q*A1; A0 = A1; A1 = A2; in findGCD()
1340 APInt B2 = B0 - Q*B1; B0 = B1; B1 = B2; in findGCD()
1346 X = AM.slt(0) ? -A1 : A1; in findGCD()
1347 Y = BM.slt(0) ? B1 : -B1; in findGCD()
1369 return Q - 1; in floorOfQuotient()
1398 // exactSIVtest -
1408 // It's slower than the specialized tests (strong SIV, weak-zero SIV, etc),
1425 Level--; in exactSIVtest()
1427 const SCEV *Delta = SE->getMinusSCEV(DstConst, SrcConst); in exactSIVtest()
1429 NewConstraint.setLine(SrcCoeff, SE->getNegativeSCEV(DstCoeff), in exactSIVtest()
1439 APInt AM = ConstSrcCoeff->getAPInt(); in exactSIVtest()
1440 APInt BM = ConstDstCoeff->getAPInt(); in exactSIVtest()
1442 if (findGCD(Bits, AM, BM, ConstDelta->getAPInt(), G, X, Y)) { in exactSIVtest()
1454 // UM is perhaps unavailable, let's check in exactSIVtest()
1456 collectConstantUpperBound(CurLoop, Delta->getType())) { in exactSIVtest()
1457 UM = CUB->getAPInt(); in exactSIVtest()
1465 // test(BM/G, LM-X) and test(-BM/G, X-UM) in exactSIVtest()
1468 TL = maxAPInt(TL, ceilingOfQuotient(-X, TMUL)); in exactSIVtest()
1471 TU = minAPInt(TU, floorOfQuotient(UM - X, TMUL)); in exactSIVtest()
1476 TU = minAPInt(TU, floorOfQuotient(-X, TMUL)); in exactSIVtest()
1479 TL = maxAPInt(TL, ceilingOfQuotient(UM - X, TMUL)); in exactSIVtest()
1484 // test(AM/G, LM-Y) and test(-AM/G, Y-UM) in exactSIVtest()
1487 TL = maxAPInt(TL, ceilingOfQuotient(-Y, TMUL)); in exactSIVtest()
1490 TU = minAPInt(TU, floorOfQuotient(UM - Y, TMUL)); in exactSIVtest()
1495 TU = minAPInt(TU, floorOfQuotient(-Y, TMUL)); in exactSIVtest()
1498 TL = maxAPInt(TL, ceilingOfQuotient(UM - Y, TMUL)); in exactSIVtest()
1515 TMUL = AM - BM; in exactSIVtest()
1517 TL = maxAPInt(TL, ceilingOfQuotient(X - Y + 1, TMUL)); in exactSIVtest()
1521 TU = minAPInt(TU, floorOfQuotient(X - Y + 1, TMUL)); in exactSIVtest()
1534 TL = maxAPInt(TL, ceilingOfQuotient(X - Y, TMUL)); in exactSIVtest()
1538 TU = minAPInt(TU, floorOfQuotient(X - Y, TMUL)); in exactSIVtest()
1541 TMUL = BM - AM; in exactSIVtest()
1543 TL = maxAPInt(TL, ceilingOfQuotient(Y - X, TMUL)); in exactSIVtest()
1547 TU = minAPInt(TU, floorOfQuotient(Y - X, TMUL)); in exactSIVtest()
1560 TL = maxAPInt(TL, ceilingOfQuotient(Y - X + 1, TMUL)); in exactSIVtest()
1564 TU = minAPInt(TU, floorOfQuotient(Y - X + 1, TMUL)); in exactSIVtest()
1585 const APInt &ConstDividend = Dividend->getAPInt(); in isRemainderZero()
1586 const APInt &ConstDivisor = Divisor->getAPInt(); in isRemainderZero()
1591 // weakZeroSrcSIVtest -
1597 // Weak-Zero SIV test.
1605 // (c1 - c2)/a = i
1631 DEBUG(dbgs() << "\tWeak-Zero (src) SIV test\n"); in weakZeroSrcSIVtest()
1637 Level--; in weakZeroSrcSIVtest()
1639 const SCEV *Delta = SE->getMinusSCEV(SrcConst, DstConst); in weakZeroSrcSIVtest()
1640 NewConstraint.setLine(SE->getZero(Delta->getType()), DstCoeff, Delta, in weakZeroSrcSIVtest()
1655 SE->isKnownNegative(ConstCoeff) ? in weakZeroSrcSIVtest()
1656 SE->getNegativeSCEV(ConstCoeff) : ConstCoeff; in weakZeroSrcSIVtest()
1658 SE->isKnownNegative(ConstCoeff) ? SE->getNegativeSCEV(Delta) : Delta; in weakZeroSrcSIVtest()
1660 // check that Delta/SrcCoeff < iteration count in weakZeroSrcSIVtest()
1661 // really check NewDelta < count*AbsCoeff in weakZeroSrcSIVtest()
1662 if (const SCEV *UpperBound = collectUpperBound(CurLoop, Delta->getType())) { in weakZeroSrcSIVtest()
1664 const SCEV *Product = SE->getMulExpr(AbsCoeff, UpperBound); in weakZeroSrcSIVtest()
1681 // check that Delta/SrcCoeff >= 0 in weakZeroSrcSIVtest()
1682 // really check that NewDelta >= 0 in weakZeroSrcSIVtest()
1683 if (SE->isKnownNegative(NewDelta)) { in weakZeroSrcSIVtest()
1701 // weakZeroDstSIVtest -
1707 // Weak-Zero SIV test.
1715 // i = (c2 - c1)/a
1740 DEBUG(dbgs() << "\tWeak-Zero (dst) SIV test\n"); in weakZeroDstSIVtest()
1746 Level--; in weakZeroDstSIVtest()
1748 const SCEV *Delta = SE->getMinusSCEV(DstConst, SrcConst); in weakZeroDstSIVtest()
1749 NewConstraint.setLine(SrcCoeff, SE->getZero(Delta->getType()), Delta, in weakZeroDstSIVtest()
1764 SE->isKnownNegative(ConstCoeff) ? in weakZeroDstSIVtest()
1765 SE->getNegativeSCEV(ConstCoeff) : ConstCoeff; in weakZeroDstSIVtest()
1767 SE->isKnownNegative(ConstCoeff) ? SE->getNegativeSCEV(Delta) : Delta; in weakZeroDstSIVtest()
1769 // check that Delta/SrcCoeff < iteration count in weakZeroDstSIVtest()
1770 // really check NewDelta < count*AbsCoeff in weakZeroDstSIVtest()
1771 if (const SCEV *UpperBound = collectUpperBound(CurLoop, Delta->getType())) { in weakZeroDstSIVtest()
1773 const SCEV *Product = SE->getMulExpr(AbsCoeff, UpperBound); in weakZeroDstSIVtest()
1790 // check that Delta/SrcCoeff >= 0 in weakZeroDstSIVtest()
1791 // really check that NewDelta >= 0 in weakZeroDstSIVtest()
1792 if (SE->isKnownNegative(NewDelta)) { in weakZeroDstSIVtest()
1810 // exactRDIVtest - Tests the RDIV subscript pair for dependence.
1828 const SCEV *Delta = SE->getMinusSCEV(DstConst, SrcConst); in exactRDIVtest()
1838 APInt AM = ConstSrcCoeff->getAPInt(); in exactRDIVtest()
1839 APInt BM = ConstDstCoeff->getAPInt(); in exactRDIVtest()
1841 if (findGCD(Bits, AM, BM, ConstDelta->getAPInt(), G, X, Y)) { in exactRDIVtest()
1852 // SrcUM is perhaps unavailable, let's check in exactRDIVtest()
1854 collectConstantUpperBound(SrcLoop, Delta->getType())) { in exactRDIVtest()
1855 SrcUM = UpperBound->getAPInt(); in exactRDIVtest()
1862 // UM is perhaps unavailable, let's check in exactRDIVtest()
1864 collectConstantUpperBound(DstLoop, Delta->getType())) { in exactRDIVtest()
1865 DstUM = UpperBound->getAPInt(); in exactRDIVtest()
1873 // test(BM/G, LM-X) and test(-BM/G, X-UM) in exactRDIVtest()
1876 TL = maxAPInt(TL, ceilingOfQuotient(-X, TMUL)); in exactRDIVtest()
1879 TU = minAPInt(TU, floorOfQuotient(SrcUM - X, TMUL)); in exactRDIVtest()
1884 TU = minAPInt(TU, floorOfQuotient(-X, TMUL)); in exactRDIVtest()
1887 TL = maxAPInt(TL, ceilingOfQuotient(SrcUM - X, TMUL)); in exactRDIVtest()
1892 // test(AM/G, LM-Y) and test(-AM/G, Y-UM) in exactRDIVtest()
1895 TL = maxAPInt(TL, ceilingOfQuotient(-Y, TMUL)); in exactRDIVtest()
1898 TU = minAPInt(TU, floorOfQuotient(DstUM - Y, TMUL)); in exactRDIVtest()
1903 TU = minAPInt(TU, floorOfQuotient(-Y, TMUL)); in exactRDIVtest()
1906 TL = maxAPInt(TL, ceilingOfQuotient(DstUM - Y, TMUL)); in exactRDIVtest()
1916 // symbolicRDIVtest -
1919 // Extreme-Value Test) that can handle some of the SIV and RDIV cases,
1935 // a1*i - a2*j = c2 - c1
1937 // To test for a dependence, we compute c2 - c1 and make sure it's in the
1938 // range of the maximum and minimum possible values of a1*i - a2*j.
1942 // a1*0 - a2*N2 <= c2 - c1 <= a1*N1 - a2*0
1943 // -a2*N2 <= c2 - c1 <= a1*N1
1946 // a1*0 - a2*0 <= c2 - c1 <= a1*N1 - a2*N2
1947 // 0 <= c2 - c1 <= a1*N1 - a2*N2
1950 // a1*N1 - a2*N2 <= c2 - c1 <= a1*0 - a2*0
1951 // a1*N1 - a2*N2 <= c2 - c1 <= 0
1954 // a1*N1 - a2*0 <= c2 - c1 <= a1*0 - a2*N2
1955 // a1*N1 <= c2 - c1 <= -a2*N2
1965 DEBUG(dbgs() << ", type = " << *A1->getType() << "\n"); in symbolicRDIVtest()
1969 const SCEV *N1 = collectUpperBound(Loop1, A1->getType()); in symbolicRDIVtest()
1970 const SCEV *N2 = collectUpperBound(Loop2, A1->getType()); in symbolicRDIVtest()
1973 const SCEV *C2_C1 = SE->getMinusSCEV(C2, C1); in symbolicRDIVtest()
1974 const SCEV *C1_C2 = SE->getMinusSCEV(C1, C2); in symbolicRDIVtest()
1975 DEBUG(dbgs() << "\t C2 - C1 = " << *C2_C1 << "\n"); in symbolicRDIVtest()
1976 DEBUG(dbgs() << "\t C1 - C2 = " << *C1_C2 << "\n"); in symbolicRDIVtest()
1977 if (SE->isKnownNonNegative(A1)) { in symbolicRDIVtest()
1978 if (SE->isKnownNonNegative(A2)) { in symbolicRDIVtest()
1981 // make sure that c2 - c1 <= a1*N1 in symbolicRDIVtest()
1982 const SCEV *A1N1 = SE->getMulExpr(A1, N1); in symbolicRDIVtest()
1990 // make sure that -a2*N2 <= c2 - c1, or a2*N2 >= c1 - c2 in symbolicRDIVtest()
1991 const SCEV *A2N2 = SE->getMulExpr(A2, N2); in symbolicRDIVtest()
1999 else if (SE->isKnownNonPositive(A2)) { in symbolicRDIVtest()
2002 // make sure that c2 - c1 <= a1*N1 - a2*N2 in symbolicRDIVtest()
2003 const SCEV *A1N1 = SE->getMulExpr(A1, N1); in symbolicRDIVtest()
2004 const SCEV *A2N2 = SE->getMulExpr(A2, N2); in symbolicRDIVtest()
2005 const SCEV *A1N1_A2N2 = SE->getMinusSCEV(A1N1, A2N2); in symbolicRDIVtest()
2006 DEBUG(dbgs() << "\t A1*N1 - A2*N2 = " << *A1N1_A2N2 << "\n"); in symbolicRDIVtest()
2012 // make sure that 0 <= c2 - c1 in symbolicRDIVtest()
2013 if (SE->isKnownNegative(C2_C1)) { in symbolicRDIVtest()
2019 else if (SE->isKnownNonPositive(A1)) { in symbolicRDIVtest()
2020 if (SE->isKnownNonNegative(A2)) { in symbolicRDIVtest()
2023 // make sure that a1*N1 - a2*N2 <= c2 - c1 in symbolicRDIVtest()
2024 const SCEV *A1N1 = SE->getMulExpr(A1, N1); in symbolicRDIVtest()
2025 const SCEV *A2N2 = SE->getMulExpr(A2, N2); in symbolicRDIVtest()
2026 const SCEV *A1N1_A2N2 = SE->getMinusSCEV(A1N1, A2N2); in symbolicRDIVtest()
2027 DEBUG(dbgs() << "\t A1*N1 - A2*N2 = " << *A1N1_A2N2 << "\n"); in symbolicRDIVtest()
2033 // make sure that c2 - c1 <= 0 in symbolicRDIVtest()
2034 if (SE->isKnownPositive(C2_C1)) { in symbolicRDIVtest()
2039 else if (SE->isKnownNonPositive(A2)) { in symbolicRDIVtest()
2042 // make sure that a1*N1 <= c2 - c1 in symbolicRDIVtest()
2043 const SCEV *A1N1 = SE->getMulExpr(A1, N1); in symbolicRDIVtest()
2051 // make sure that c2 - c1 <= -a2*N2, or c1 - c2 >= a2*N2 in symbolicRDIVtest()
2052 const SCEV *A2N2 = SE->getMulExpr(A2, N2); in symbolicRDIVtest()
2065 // testSIV -
2066 // When we have a pair of subscripts of the form [c1 + a1*i] and [c2 - a2*i]
2081 const SCEV *SrcConst = SrcAddRec->getStart(); in testSIV()
2082 const SCEV *DstConst = DstAddRec->getStart(); in testSIV()
2083 const SCEV *SrcCoeff = SrcAddRec->getStepRecurrence(*SE); in testSIV()
2084 const SCEV *DstCoeff = DstAddRec->getStepRecurrence(*SE); in testSIV()
2085 const Loop *CurLoop = SrcAddRec->getLoop(); in testSIV()
2086 assert(CurLoop == DstAddRec->getLoop() && in testSIV()
2093 else if (SrcCoeff == SE->getNegativeSCEV(DstCoeff)) in testSIV()
2104 const SCEV *SrcConst = SrcAddRec->getStart(); in testSIV()
2105 const SCEV *SrcCoeff = SrcAddRec->getStepRecurrence(*SE); in testSIV()
2107 const Loop *CurLoop = SrcAddRec->getLoop(); in testSIV()
2114 const SCEV *DstConst = DstAddRec->getStart(); in testSIV()
2115 const SCEV *DstCoeff = DstAddRec->getStepRecurrence(*SE); in testSIV()
2117 const Loop *CurLoop = DstAddRec->getLoop(); in testSIV()
2128 // testRDIV -
2135 // the Weak-crossing SIV test.
2158 SrcConst = SrcAddRec->getStart(); in testRDIV()
2159 SrcCoeff = SrcAddRec->getStepRecurrence(*SE); in testRDIV()
2160 SrcLoop = SrcAddRec->getLoop(); in testRDIV()
2161 DstConst = DstAddRec->getStart(); in testRDIV()
2162 DstCoeff = DstAddRec->getStepRecurrence(*SE); in testRDIV()
2163 DstLoop = DstAddRec->getLoop(); in testRDIV()
2167 dyn_cast<SCEVAddRecExpr>(SrcAddRec->getStart())) { in testRDIV()
2168 SrcConst = tmpAddRec->getStart(); in testRDIV()
2169 SrcCoeff = tmpAddRec->getStepRecurrence(*SE); in testRDIV()
2170 SrcLoop = tmpAddRec->getLoop(); in testRDIV()
2172 DstCoeff = SE->getNegativeSCEV(SrcAddRec->getStepRecurrence(*SE)); in testRDIV()
2173 DstLoop = SrcAddRec->getLoop(); in testRDIV()
2180 dyn_cast<SCEVAddRecExpr>(DstAddRec->getStart())) { in testRDIV()
2181 DstConst = tmpAddRec->getStart(); in testRDIV()
2182 DstCoeff = tmpAddRec->getStepRecurrence(*SE); in testRDIV()
2183 DstLoop = tmpAddRec->getLoop(); in testRDIV()
2185 SrcCoeff = SE->getNegativeSCEV(DstAddRec->getStepRecurrence(*SE)); in testRDIV()
2186 SrcLoop = DstAddRec->getLoop(); in testRDIV()
2204 // Tests the single-subscript MIV pair (Src and Dst) for dependence.
2225 if (const auto *Constant = dyn_cast<SCEVConstant>(Product->getOperand(0))) in getConstantPart()
2231 //===----------------------------------------------------------------------===//
2232 // gcdMIVtest -
2242 // but M and N are just loop-invariant variables.
2246 // It occurs to me that the presence of loop-invariant variables
2253 unsigned BitWidth = SE->getTypeSizeInBits(Src->getType()); in gcdMIVtest()
2263 const SCEV *Coeff = AddRec->getStepRecurrence(*SE); in gcdMIVtest()
2269 APInt ConstCoeff = Constant->getAPInt(); in gcdMIVtest()
2271 Coefficients = AddRec->getStart(); in gcdMIVtest()
2282 const SCEV *Coeff = AddRec->getStepRecurrence(*SE); in gcdMIVtest()
2288 APInt ConstCoeff = Constant->getAPInt(); in gcdMIVtest()
2290 Coefficients = AddRec->getStart(); in gcdMIVtest()
2295 const SCEV *Delta = SE->getMinusSCEV(DstConst, SrcConst); in gcdMIVtest()
2300 for (unsigned Op = 0, Ops = Sum->getNumOperands(); Op < Ops; Op++) { in gcdMIVtest()
2301 const SCEV *Operand = Sum->getOperand(Op); in gcdMIVtest()
2312 APInt ConstOpValue = ConstOp->getAPInt(); in gcdMIVtest()
2322 APInt ConstDelta = cast<SCEVConstant>(Constant)->getAPInt(); in gcdMIVtest()
2335 // For example, given a subscript pair [3*i + 2*j] and [i' + 2*j' - 1], in gcdMIVtest()
2338 // If i = i', we can simplify the subscript to [2*i + 2*j] and [2*j' - 1], in gcdMIVtest()
2343 // Given A[5*i + 10*j*M + 9*M*N] and A[15*i + 20*j*M - 21*N*M + 5], in gcdMIVtest()
2352 Coefficients = AddRec->getStart(); in gcdMIVtest()
2353 const Loop *CurLoop = AddRec->getLoop(); in gcdMIVtest()
2355 const SCEV *SrcCoeff = AddRec->getStepRecurrence(*SE); in gcdMIVtest()
2356 const SCEV *DstCoeff = SE->getMinusSCEV(SrcCoeff, SrcCoeff); in gcdMIVtest()
2360 const SCEV *Coeff = AddRec->getStepRecurrence(*SE); in gcdMIVtest()
2361 if (CurLoop == AddRec->getLoop()) in gcdMIVtest()
2369 APInt ConstCoeff = Constant->getAPInt(); in gcdMIVtest()
2372 Inner = AddRec->getStart(); in gcdMIVtest()
2377 const SCEV *Coeff = AddRec->getStepRecurrence(*SE); in gcdMIVtest()
2378 if (CurLoop == AddRec->getLoop()) in gcdMIVtest()
2386 APInt ConstCoeff = Constant->getAPInt(); in gcdMIVtest()
2389 Inner = AddRec->getStart(); in gcdMIVtest()
2391 Delta = SE->getMinusSCEV(SrcCoeff, DstCoeff); in gcdMIVtest()
2399 APInt ConstCoeff = Constant->getAPInt(); in gcdMIVtest()
2407 Result.DV[Level - 1].Direction &= unsigned(~Dependence::DVEntry::EQ); in gcdMIVtest()
2419 //===----------------------------------------------------------------------===//
2420 // banerjeeMIVtest -
2422 // (Wolfe, in the race-car book, calls this the Extreme Value Test.)
2429 // normalized so that the lower bound is always 0 and the stride is always 1.
2432 // LB^<_k = (A^-_k - B_k)^- (U_k - L_k - N_k) + (A_k - B_k)L_k - B_k N_k
2436 // U_k is the upper bound of the kth index, L_k is the lower bound of the Kth
2441 // LB^<_k = (A^-_k - B_k)^- (U_k - 0 - 1) + (A_k - B_k)0 - B_k 1
2442 // = (A^-_k - B_k)^- (U_k - 1) - B_k
2448 // When computing the upper bound, NULL denotes +inf;
2449 // for the lower bound, NULL denotes -inf.
2463 BoundInfo *Bound = new BoundInfo[MaxLevels + 1]; in banerjeeMIVtest() local
2464 const SCEV *Delta = SE->getMinusSCEV(B0, A0); in banerjeeMIVtest()
2470 Bound[K].Iterations = A[K].Iterations ? A[K].Iterations : B[K].Iterations; in banerjeeMIVtest()
2471 Bound[K].Direction = Dependence::DVEntry::ALL; in banerjeeMIVtest()
2472 Bound[K].DirSet = Dependence::DVEntry::NONE; in banerjeeMIVtest()
2473 findBoundsALL(A, B, Bound, K); in banerjeeMIVtest()
2476 if (Bound[K].Lower[Dependence::DVEntry::ALL]) in banerjeeMIVtest()
2477 DEBUG(dbgs() << *Bound[K].Lower[Dependence::DVEntry::ALL] << '\t'); in banerjeeMIVtest()
2479 DEBUG(dbgs() << "-inf\t"); in banerjeeMIVtest()
2480 if (Bound[K].Upper[Dependence::DVEntry::ALL]) in banerjeeMIVtest()
2481 DEBUG(dbgs() << *Bound[K].Upper[Dependence::DVEntry::ALL] << '\n'); in banerjeeMIVtest()
2489 if (testBounds(Dependence::DVEntry::ALL, 0, Bound, Delta)) { in banerjeeMIVtest()
2492 unsigned NewDeps = exploreDirections(1, A, B, Bound, in banerjeeMIVtest()
2498 unsigned Old = Result.DV[K - 1].Direction; in banerjeeMIVtest()
2499 Result.DV[K - 1].Direction = Old & Bound[K].DirSet; in banerjeeMIVtest()
2500 Improved |= Old != Result.DV[K - 1].Direction; in banerjeeMIVtest()
2501 if (!Result.DV[K - 1].Direction) { in banerjeeMIVtest()
2520 delete [] Bound; in banerjeeMIVtest()
2529 // in the DirSet field of Bound. Returns the number of distinct
2533 CoefficientInfo *B, BoundInfo *Bound, in exploreDirections() argument
2542 Bound[K].DirSet |= Bound[K].Direction; in exploreDirections()
2544 switch (Bound[K].Direction) { in exploreDirections()
2558 llvm_unreachable("unexpected Bound[K].Direction"); in exploreDirections()
2570 findBoundsLT(A, B, Bound, Level); in exploreDirections()
2571 findBoundsGT(A, B, Bound, Level); in exploreDirections()
2572 findBoundsEQ(A, B, Bound, Level); in exploreDirections()
2576 if (Bound[Level].Lower[Dependence::DVEntry::LT]) in exploreDirections()
2577 DEBUG(dbgs() << *Bound[Level].Lower[Dependence::DVEntry::LT] << '\t'); in exploreDirections()
2579 DEBUG(dbgs() << "-inf\t"); in exploreDirections()
2580 if (Bound[Level].Upper[Dependence::DVEntry::LT]) in exploreDirections()
2581 DEBUG(dbgs() << *Bound[Level].Upper[Dependence::DVEntry::LT] << '\n'); in exploreDirections()
2585 if (Bound[Level].Lower[Dependence::DVEntry::EQ]) in exploreDirections()
2586 DEBUG(dbgs() << *Bound[Level].Lower[Dependence::DVEntry::EQ] << '\t'); in exploreDirections()
2588 DEBUG(dbgs() << "-inf\t"); in exploreDirections()
2589 if (Bound[Level].Upper[Dependence::DVEntry::EQ]) in exploreDirections()
2590 DEBUG(dbgs() << *Bound[Level].Upper[Dependence::DVEntry::EQ] << '\n'); in exploreDirections()
2594 if (Bound[Level].Lower[Dependence::DVEntry::GT]) in exploreDirections()
2595 DEBUG(dbgs() << *Bound[Level].Lower[Dependence::DVEntry::GT] << '\t'); in exploreDirections()
2597 DEBUG(dbgs() << "-inf\t"); in exploreDirections()
2598 if (Bound[Level].Upper[Dependence::DVEntry::GT]) in exploreDirections()
2599 DEBUG(dbgs() << *Bound[Level].Upper[Dependence::DVEntry::GT] << '\n'); in exploreDirections()
2608 if (testBounds(Dependence::DVEntry::LT, Level, Bound, Delta)) in exploreDirections()
2609 NewDeps += exploreDirections(Level + 1, A, B, Bound, in exploreDirections()
2613 if (testBounds(Dependence::DVEntry::EQ, Level, Bound, Delta)) in exploreDirections()
2614 NewDeps += exploreDirections(Level + 1, A, B, Bound, in exploreDirections()
2618 if (testBounds(Dependence::DVEntry::GT, Level, Bound, Delta)) in exploreDirections()
2619 NewDeps += exploreDirections(Level + 1, A, B, Bound, in exploreDirections()
2622 Bound[Level].Direction = Dependence::DVEntry::ALL; in exploreDirections()
2626 return exploreDirections(Level + 1, A, B, Bound, Loops, DepthExpanded, Delta); in exploreDirections()
2632 BoundInfo *Bound, const SCEV *Delta) const { in testBounds() argument
2633 Bound[Level].Direction = DirKind; in testBounds()
2634 if (const SCEV *LowerBound = getLowerBound(Bound)) in testBounds()
2637 if (const SCEV *UpperBound = getUpperBound(Bound)) in testBounds()
2644 // Computes the upper and lower bounds for level K
2645 // using the * direction. Records them in Bound.
2648 // LB^*_k = (A^-_k - B^+_k)(U_k - L_k) + (A_k - B_k)L_k
2649 // UB^*_k = (A^+_k - B^-_k)(U_k - L_k) + (A_k - B_k)L_k
2653 // LB^*_k = (A^-_k - B^+_k)U_k
2654 // UB^*_k = (A^+_k - B^-_k)U_k
2656 // We must be careful to handle the case where the upper bound is unknown.
2657 // Note that the lower bound is always <= 0
2658 // and the upper bound is always >= 0.
2660 BoundInfo *Bound, unsigned K) const { in findBoundsALL() argument
2661 Bound[K].Lower[Dependence::DVEntry::ALL] = nullptr; // Default value = -infinity. in findBoundsALL()
2662 Bound[K].Upper[Dependence::DVEntry::ALL] = nullptr; // Default value = +infinity. in findBoundsALL()
2663 if (Bound[K].Iterations) { in findBoundsALL()
2664 Bound[K].Lower[Dependence::DVEntry::ALL] = in findBoundsALL()
2665 SE->getMulExpr(SE->getMinusSCEV(A[K].NegPart, B[K].PosPart), in findBoundsALL()
2666 Bound[K].Iterations); in findBoundsALL()
2667 Bound[K].Upper[Dependence::DVEntry::ALL] = in findBoundsALL()
2668 SE->getMulExpr(SE->getMinusSCEV(A[K].PosPart, B[K].NegPart), in findBoundsALL()
2669 Bound[K].Iterations); in findBoundsALL()
2674 Bound[K].Lower[Dependence::DVEntry::ALL] = in findBoundsALL()
2675 SE->getZero(A[K].Coeff->getType()); in findBoundsALL()
2677 Bound[K].Upper[Dependence::DVEntry::ALL] = in findBoundsALL()
2678 SE->getZero(A[K].Coeff->getType()); in findBoundsALL()
2683 // Computes the upper and lower bounds for level K
2684 // using the = direction. Records them in Bound.
2687 // LB^=_k = (A_k - B_k)^- (U_k - L_k) + (A_k - B_k)L_k
2688 // UB^=_k = (A_k - B_k)^+ (U_k - L_k) + (A_k - B_k)L_k
2692 // LB^=_k = (A_k - B_k)^- U_k
2693 // UB^=_k = (A_k - B_k)^+ U_k
2695 // We must be careful to handle the case where the upper bound is unknown.
2696 // Note that the lower bound is always <= 0
2697 // and the upper bound is always >= 0.
2699 BoundInfo *Bound, unsigned K) const { in findBoundsEQ() argument
2700 Bound[K].Lower[Dependence::DVEntry::EQ] = nullptr; // Default value = -infinity. in findBoundsEQ()
2701 Bound[K].Upper[Dependence::DVEntry::EQ] = nullptr; // Default value = +infinity. in findBoundsEQ()
2702 if (Bound[K].Iterations) { in findBoundsEQ()
2703 const SCEV *Delta = SE->getMinusSCEV(A[K].Coeff, B[K].Coeff); in findBoundsEQ()
2705 Bound[K].Lower[Dependence::DVEntry::EQ] = in findBoundsEQ()
2706 SE->getMulExpr(NegativePart, Bound[K].Iterations); in findBoundsEQ()
2708 Bound[K].Upper[Dependence::DVEntry::EQ] = in findBoundsEQ()
2709 SE->getMulExpr(PositivePart, Bound[K].Iterations); in findBoundsEQ()
2714 const SCEV *Delta = SE->getMinusSCEV(A[K].Coeff, B[K].Coeff); in findBoundsEQ()
2716 if (NegativePart->isZero()) in findBoundsEQ()
2717 Bound[K].Lower[Dependence::DVEntry::EQ] = NegativePart; // Zero in findBoundsEQ()
2719 if (PositivePart->isZero()) in findBoundsEQ()
2720 Bound[K].Upper[Dependence::DVEntry::EQ] = PositivePart; // Zero in findBoundsEQ()
2725 // Computes the upper and lower bounds for level K
2726 // using the < direction. Records them in Bound.
2729 // LB^<_k = (A^-_k - B_k)^- (U_k - L_k - N_k) + (A_k - B_k)L_k - B_k N_k
2730 // UB^<_k = (A^+_k - B_k)^+ (U_k - L_k - N_k) + (A_k - B_k)L_k - B_k N_k
2734 // LB^<_k = (A^-_k - B_k)^- (U_k - 1) - B_k
2735 // UB^<_k = (A^+_k - B_k)^+ (U_k - 1) - B_k
2737 // We must be careful to handle the case where the upper bound is unknown.
2739 BoundInfo *Bound, unsigned K) const { in findBoundsLT() argument
2740 Bound[K].Lower[Dependence::DVEntry::LT] = nullptr; // Default value = -infinity. in findBoundsLT()
2741 Bound[K].Upper[Dependence::DVEntry::LT] = nullptr; // Default value = +infinity. in findBoundsLT()
2742 if (Bound[K].Iterations) { in findBoundsLT()
2743 const SCEV *Iter_1 = SE->getMinusSCEV( in findBoundsLT()
2744 Bound[K].Iterations, SE->getOne(Bound[K].Iterations->getType())); in findBoundsLT()
2746 getNegativePart(SE->getMinusSCEV(A[K].NegPart, B[K].Coeff)); in findBoundsLT()
2747 Bound[K].Lower[Dependence::DVEntry::LT] = in findBoundsLT()
2748 SE->getMinusSCEV(SE->getMulExpr(NegPart, Iter_1), B[K].Coeff); in findBoundsLT()
2750 getPositivePart(SE->getMinusSCEV(A[K].PosPart, B[K].Coeff)); in findBoundsLT()
2751 Bound[K].Upper[Dependence::DVEntry::LT] = in findBoundsLT()
2752 SE->getMinusSCEV(SE->getMulExpr(PosPart, Iter_1), B[K].Coeff); in findBoundsLT()
2758 getNegativePart(SE->getMinusSCEV(A[K].NegPart, B[K].Coeff)); in findBoundsLT()
2759 if (NegPart->isZero()) in findBoundsLT()
2760 Bound[K].Lower[Dependence::DVEntry::LT] = SE->getNegativeSCEV(B[K].Coeff); in findBoundsLT()
2762 getPositivePart(SE->getMinusSCEV(A[K].PosPart, B[K].Coeff)); in findBoundsLT()
2763 if (PosPart->isZero()) in findBoundsLT()
2764 Bound[K].Upper[Dependence::DVEntry::LT] = SE->getNegativeSCEV(B[K].Coeff); in findBoundsLT()
2769 // Computes the upper and lower bounds for level K
2770 // using the > direction. Records them in Bound.
2773 // LB^>_k = (A_k - B^+_k)^- (U_k - L_k - N_k) + (A_k - B_k)L_k + A_k N_k
2774 // UB^>_k = (A_k - B^-_k)^+ (U_k - L_k - N_k) + (A_k - B_k)L_k + A_k N_k
2778 // LB^>_k = (A_k - B^+_k)^- (U_k - 1) + A_k
2779 // UB^>_k = (A_k - B^-_k)^+ (U_k - 1) + A_k
2781 // We must be careful to handle the case where the upper bound is unknown.
2783 BoundInfo *Bound, unsigned K) const { in findBoundsGT() argument
2784 Bound[K].Lower[Dependence::DVEntry::GT] = nullptr; // Default value = -infinity. in findBoundsGT()
2785 Bound[K].Upper[Dependence::DVEntry::GT] = nullptr; // Default value = +infinity. in findBoundsGT()
2786 if (Bound[K].Iterations) { in findBoundsGT()
2787 const SCEV *Iter_1 = SE->getMinusSCEV( in findBoundsGT()
2788 Bound[K].Iterations, SE->getOne(Bound[K].Iterations->getType())); in findBoundsGT()
2790 getNegativePart(SE->getMinusSCEV(A[K].Coeff, B[K].PosPart)); in findBoundsGT()
2791 Bound[K].Lower[Dependence::DVEntry::GT] = in findBoundsGT()
2792 SE->getAddExpr(SE->getMulExpr(NegPart, Iter_1), A[K].Coeff); in findBoundsGT()
2794 getPositivePart(SE->getMinusSCEV(A[K].Coeff, B[K].NegPart)); in findBoundsGT()
2795 Bound[K].Upper[Dependence::DVEntry::GT] = in findBoundsGT()
2796 SE->getAddExpr(SE->getMulExpr(PosPart, Iter_1), A[K].Coeff); in findBoundsGT()
2801 const SCEV *NegPart = getNegativePart(SE->getMinusSCEV(A[K].Coeff, B[K].PosPart)); in findBoundsGT()
2802 if (NegPart->isZero()) in findBoundsGT()
2803 Bound[K].Lower[Dependence::DVEntry::GT] = A[K].Coeff; in findBoundsGT()
2804 const SCEV *PosPart = getPositivePart(SE->getMinusSCEV(A[K].Coeff, B[K].NegPart)); in findBoundsGT()
2805 if (PosPart->isZero()) in findBoundsGT()
2806 Bound[K].Upper[Dependence::DVEntry::GT] = A[K].Coeff; in findBoundsGT()
2813 return SE->getSMaxExpr(X, SE->getZero(X->getType())); in getPositivePart()
2817 // X^- = min(X, 0)
2819 return SE->getSMinExpr(X, SE->getZero(X->getType())); in getNegativePart()
2829 const SCEV *Zero = SE->getZero(Subscript->getType()); in collectCoeffInfo()
2838 const Loop *L = AddRec->getLoop(); in collectCoeffInfo()
2840 CI[K].Coeff = AddRec->getStepRecurrence(*SE); in collectCoeffInfo()
2843 CI[K].Iterations = collectUpperBound(L, Subscript->getType()); in collectCoeffInfo()
2844 Subscript = AddRec->getStart(); in collectCoeffInfo()
2855 DEBUG(dbgs() << "\tUpper Bound = "); in collectCoeffInfo()
2869 // computes the lower bound given the current direction settings
2870 // at each level. If the lower bound for any level is -inf,
2871 // the result is -inf.
2872 const SCEV *DependenceInfo::getLowerBound(BoundInfo *Bound) const { in getLowerBound()
2873 const SCEV *Sum = Bound[1].Lower[Bound[1].Direction]; in getLowerBound()
2875 if (Bound[K].Lower[Bound[K].Direction]) in getLowerBound()
2876 Sum = SE->getAddExpr(Sum, Bound[K].Lower[Bound[K].Direction]); in getLowerBound()
2885 // computes the upper bound given the current direction settings
2886 // at each level. If the upper bound at any level is +inf,
2888 const SCEV *DependenceInfo::getUpperBound(BoundInfo *Bound) const { in getUpperBound()
2889 const SCEV *Sum = Bound[1].Upper[Bound[1].Direction]; in getUpperBound()
2891 if (Bound[K].Upper[Bound[K].Direction]) in getUpperBound()
2892 Sum = SE->getAddExpr(Sum, Bound[K].Upper[Bound[K].Direction]); in getUpperBound()
2900 //===----------------------------------------------------------------------===//
2913 return SE->getZero(Expr->getType()); in findCoefficient()
2914 if (AddRec->getLoop() == TargetLoop) in findCoefficient()
2915 return AddRec->getStepRecurrence(*SE); in findCoefficient()
2916 return findCoefficient(AddRec->getStart(), TargetLoop); in findCoefficient()
2930 if (AddRec->getLoop() == TargetLoop) in zeroCoefficient()
2931 return AddRec->getStart(); in zeroCoefficient()
2932 return SE->getAddRecExpr(zeroCoefficient(AddRec->getStart(), TargetLoop), in zeroCoefficient()
2933 AddRec->getStepRecurrence(*SE), in zeroCoefficient()
2934 AddRec->getLoop(), in zeroCoefficient()
2935 AddRec->getNoWrapFlags()); in zeroCoefficient()
2949 return SE->getAddRecExpr(Expr, in addToCoefficient()
2953 if (AddRec->getLoop() == TargetLoop) { in addToCoefficient()
2954 const SCEV *Sum = SE->getAddExpr(AddRec->getStepRecurrence(*SE), Value); in addToCoefficient()
2955 if (Sum->isZero()) in addToCoefficient()
2956 return AddRec->getStart(); in addToCoefficient()
2957 return SE->getAddRecExpr(AddRec->getStart(), in addToCoefficient()
2959 AddRec->getLoop(), in addToCoefficient()
2960 AddRec->getNoWrapFlags()); in addToCoefficient()
2962 if (SE->isLoopInvariant(AddRec, TargetLoop)) in addToCoefficient()
2963 return SE->getAddRecExpr(AddRec, Value, TargetLoop, SCEV::FlagAnyWrap); in addToCoefficient()
2964 return SE->getAddRecExpr( in addToCoefficient()
2965 addToCoefficient(AddRec->getStart(), TargetLoop, Value), in addToCoefficient()
2966 AddRec->getStepRecurrence(*SE), AddRec->getLoop(), in addToCoefficient()
2967 AddRec->getNoWrapFlags()); in addToCoefficient()
3011 if (A_K->isZero()) in propagateDistance()
3013 const SCEV *DA_K = SE->getMulExpr(A_K, CurConstraint.getD()); in propagateDistance()
3014 Src = SE->getMinusSCEV(Src, DA_K); in propagateDistance()
3018 Dst = addToCoefficient(Dst, CurLoop, SE->getNegativeSCEV(A_K)); in propagateDistance()
3020 if (!findCoefficient(Dst, CurLoop)->isZero()) in propagateDistance()
3041 if (A->isZero()) { in propagateLine()
3045 APInt Beta = Bconst->getAPInt(); in propagateLine()
3046 APInt Charlie = Cconst->getAPInt(); in propagateLine()
3050 // Src = SE->getAddExpr(Src, SE->getMulExpr(AP_K, SE->getConstant(CdivB))); in propagateLine()
3051 Src = SE->getMinusSCEV(Src, SE->getMulExpr(AP_K, SE->getConstant(CdivB))); in propagateLine()
3053 if (!findCoefficient(Src, CurLoop)->isZero()) in propagateLine()
3056 else if (B->isZero()) { in propagateLine()
3060 APInt Alpha = Aconst->getAPInt(); in propagateLine()
3061 APInt Charlie = Cconst->getAPInt(); in propagateLine()
3065 Src = SE->getAddExpr(Src, SE->getMulExpr(A_K, SE->getConstant(CdivA))); in propagateLine()
3067 if (!findCoefficient(Dst, CurLoop)->isZero()) in propagateLine()
3074 APInt Alpha = Aconst->getAPInt(); in propagateLine()
3075 APInt Charlie = Cconst->getAPInt(); in propagateLine()
3079 Src = SE->getAddExpr(Src, SE->getMulExpr(A_K, SE->getConstant(CdivA))); in propagateLine()
3082 if (!findCoefficient(Dst, CurLoop)->isZero()) in propagateLine()
3088 Src = SE->getMulExpr(Src, A); in propagateLine()
3089 Dst = SE->getMulExpr(Dst, A); in propagateLine()
3090 Src = SE->getAddExpr(Src, SE->getMulExpr(A_K, C)); in propagateLine()
3092 Dst = addToCoefficient(Dst, CurLoop, SE->getMulExpr(A_K, B)); in propagateLine()
3093 if (!findCoefficient(Dst, CurLoop)->isZero()) in propagateLine()
3110 const SCEV *XA_K = SE->getMulExpr(A_K, CurConstraint.getX()); in propagatePoint()
3111 const SCEV *YAP_K = SE->getMulExpr(AP_K, CurConstraint.getY()); in propagatePoint()
3113 Src = SE->getAddExpr(Src, SE->getMinusSCEV(XA_K, YAP_K)); in propagatePoint()
3135 if (!SE->isKnownNonZero(Level.Distance)) // if may be zero in updateDirection()
3137 if (!SE->isKnownNonPositive(Level.Distance)) // if may be positive in updateDirection()
3139 if (!SE->isKnownNonNegative(Level.Distance)) // if may be negative in updateDirection()
3173 /// Check if we can delinearize the subscripts. If the SCEVs representing the
3182 Loop *SrcLoop = LI->getLoopFor(Src->getParent()); in tryDelinearize()
3183 Loop *DstLoop = LI->getLoopFor(Dst->getParent()); in tryDelinearize()
3187 SE->getSCEVAtScope(SrcPtr, SrcLoop); in tryDelinearize()
3189 SE->getSCEVAtScope(DstPtr, DstLoop); in tryDelinearize()
3192 dyn_cast<SCEVUnknown>(SE->getPointerBase(SrcAccessFn)); in tryDelinearize()
3194 dyn_cast<SCEVUnknown>(SE->getPointerBase(DstAccessFn)); in tryDelinearize()
3199 const SCEV *ElementSize = SE->getElementSize(Src); in tryDelinearize()
3200 if (ElementSize != SE->getElementSize(Dst)) in tryDelinearize()
3203 const SCEV *SrcSCEV = SE->getMinusSCEV(SrcAccessFn, SrcBase); in tryDelinearize()
3204 const SCEV *DstSCEV = SE->getMinusSCEV(DstAccessFn, DstBase); in tryDelinearize()
3208 if (!SrcAR || !DstAR || !SrcAR->isAffine() || !DstAR->isAffine()) in tryDelinearize()
3213 SE->collectParametricTerms(SrcAR, Terms); in tryDelinearize()
3214 SE->collectParametricTerms(DstAR, Terms); in tryDelinearize()
3218 SE->findArrayDimensions(Terms, Sizes, ElementSize); in tryDelinearize()
3222 SE->computeAccessFunctions(SrcAR, SrcSubscripts, Sizes); in tryDelinearize()
3223 SE->computeAccessFunctions(DstAR, DstSubscripts, Sizes); in tryDelinearize()
3241 // The delinearization transforms a single-subscript MIV dependence test into in tryDelinearize()
3242 // a multi-subscript SIV dependence test that is easier to compute. So we in tryDelinearize()
3253 // check to avoid memory accesses overflow from one dimension into another. in tryDelinearize()
3262 //===----------------------------------------------------------------------===//
3277 // depends -
3294 if ((!Src->mayReadFromMemory() && !Src->mayWriteToMemory()) || in depends()
3295 (!Dst->mayReadFromMemory() && !Dst->mayWriteToMemory())) in depends()
3308 switch (underlyingObjectsAlias(AA, F->getParent()->getDataLayout(), DstPtr, in depends()
3336 SrcGEP->getPointerOperandType() == DstGEP->getPointerOperandType()) { in depends()
3337 const SCEV *SrcPtrSCEV = SE->getSCEV(SrcGEP->getPointerOperand()); in depends()
3338 const SCEV *DstPtrSCEV = SE->getSCEV(DstGEP->getPointerOperand()); in depends()
3342 UsefulGEP = isLoopInvariant(SrcPtrSCEV, LI->getLoopFor(Src->getParent())) && in depends()
3343 isLoopInvariant(DstPtrSCEV, LI->getLoopFor(Dst->getParent())) && in depends()
3344 (SrcGEP->getNumOperands() == DstGEP->getNumOperands()); in depends()
3346 unsigned Pairs = UsefulGEP ? SrcGEP->idx_end() - SrcGEP->idx_begin() : 1; in depends()
3351 for (GEPOperator::const_op_iterator SrcIdx = SrcGEP->idx_begin(), in depends()
3352 SrcEnd = SrcGEP->idx_end(), in depends()
3353 DstIdx = DstGEP->idx_begin(); in depends()
3356 Pair[P].Src = SE->getSCEV(*SrcIdx); in depends()
3357 Pair[P].Dst = SE->getSCEV(*DstIdx); in depends()
3363 const SCEV *SrcSCEV = SE->getSCEV(SrcPtr); in depends()
3364 const SCEV *DstSCEV = SE->getSCEV(DstPtr); in depends()
3384 classifyPair(Pair[P].Src, LI->getLoopFor(Src->getParent()), in depends()
3385 Pair[P].Dst, LI->getLoopFor(Dst->getParent()), in depends()
3400 // Partition subscripts into separable and minimally-coupled groups in depends()
3402 // this may be faster in practice. Check someday. in depends()
3462 LI->getLoopFor(Src->getParent()), in depends()
3465 LI->getLoopFor(Dst->getParent()), in depends()
3473 // SIV, RDIV, or MIV, so check for coupled group in depends()
3598 classifyPair(Pair[SJ].Src, LI->getLoopFor(Src->getParent()), in depends()
3599 Pair[SJ].Dst, LI->getLoopFor(Dst->getParent()), in depends()
3653 updateDirection(Result.DV[SJ - 1], Constraints[SJ]); in depends()
3654 if (Result.DV[SJ - 1].Direction == Dependence::DVEntry::NONE) in depends()
3666 Result.DV[II - 1].Scalar = false; in depends()
3671 // loop-independent dependence is possible. in depends()
3681 // loop-independent dependence possible, then no dependence exists. in depends()
3698 //===----------------------------------------------------------------------===//
3699 // getSplitIteration -
3700 // Rather than spend rarely-used space recording the splitting iteration
3701 // during the Weak-Crossing SIV test, we re-compute it on demand.
3702 // The re-computation is basically a repeat of the entire dependence test,
3728 // ... = A[11 - i]
3730 // There's a loop-carried flow dependence from the store to the load,
3731 // found by the weak-crossing SIV test. The dependence will have a flag,
3738 // ... = A[11 - i]
3741 // ... = A[11 - i]
3751 assert(Src->mayReadFromMemory() || Src->mayWriteToMemory()); in getSplitIteration()
3752 assert(Dst->mayReadFromMemory() || Dst->mayWriteToMemory()); in getSplitIteration()
3757 assert(underlyingObjectsAlias(AA, F->getParent()->getDataLayout(), DstPtr, in getSplitIteration()
3770 SrcGEP->getPointerOperandType() == DstGEP->getPointerOperandType()) { in getSplitIteration()
3771 const SCEV *SrcPtrSCEV = SE->getSCEV(SrcGEP->getPointerOperand()); in getSplitIteration()
3772 const SCEV *DstPtrSCEV = SE->getSCEV(DstGEP->getPointerOperand()); in getSplitIteration()
3773 UsefulGEP = isLoopInvariant(SrcPtrSCEV, LI->getLoopFor(Src->getParent())) && in getSplitIteration()
3774 isLoopInvariant(DstPtrSCEV, LI->getLoopFor(Dst->getParent())) && in getSplitIteration()
3775 (SrcGEP->getNumOperands() == DstGEP->getNumOperands()); in getSplitIteration()
3777 unsigned Pairs = UsefulGEP ? SrcGEP->idx_end() - SrcGEP->idx_begin() : 1; in getSplitIteration()
3781 for (GEPOperator::const_op_iterator SrcIdx = SrcGEP->idx_begin(), in getSplitIteration()
3782 SrcEnd = SrcGEP->idx_end(), in getSplitIteration()
3783 DstIdx = DstGEP->idx_begin(); in getSplitIteration()
3786 Pair[P].Src = SE->getSCEV(*SrcIdx); in getSplitIteration()
3787 Pair[P].Dst = SE->getSCEV(*DstIdx); in getSplitIteration()
3791 const SCEV *SrcSCEV = SE->getSCEV(SrcPtr); in getSplitIteration()
3792 const SCEV *DstSCEV = SE->getSCEV(DstPtr); in getSplitIteration()
3810 classifyPair(Pair[P].Src, LI->getLoopFor(Src->getParent()), in getSplitIteration()
3811 Pair[P].Dst, LI->getLoopFor(Dst->getParent()), in getSplitIteration()
3820 // partition subscripts into separable and minimally-coupled groups in getSplitIteration()
3825 LI->getLoopFor(Src->getParent()), in getSplitIteration()
3828 LI->getLoopFor(Dst->getParent()), in getSplitIteration()
3835 // SIV, RDIV, or MIV, so check for coupled group in getSplitIteration()
3921 classifyPair(Pair[SJ].Src, LI->getLoopFor(Src->getParent()), in getSplitIteration()
3922 Pair[SJ].Dst, LI->getLoopFor(Dst->getParent()), in getSplitIteration()