Lines Matching +full:eq +full:- +full:level
1 //===-- DependenceAnalysis.cpp - DA Implementation --------------*- C++ -*-===//
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7 //===----------------------------------------------------------------------===//
19 // or a more-or-less detailed description of the dependence between them.
22 // coupled RDIV subscripts and lacks a multi-subscript MIV test.
27 // analysis is using SCEV->delinearize to recover the representation of multiple
29 // delinearization is controlled by the flag -da-delinearize.
35 // Some non-linear subscript pairs can be handled by the GCD test
46 //===----------------------------------------------------------------------===//
48 // In memory of Ken Kennedy, 1945 - 2007 //
50 //===----------------------------------------------------------------------===//
72 //===----------------------------------------------------------------------===//
84 STATISTIC(WeakCrossingSIVapplications, "Weak-Crossing SIV applications");
85 STATISTIC(WeakCrossingSIVsuccesses, "Weak-Crossing SIV successes");
86 STATISTIC(WeakCrossingSIVindependence, "Weak-Crossing SIV independence");
90 STATISTIC(WeakZeroSIVapplications, "Weak-Zero SIV applications");
91 STATISTIC(WeakZeroSIVsuccesses, "Weak-Zero SIV successes");
92 STATISTIC(WeakZeroSIVindependence, "Weak-Zero SIV independence");
109 Delinearize("da-delinearize", cl::init(true), cl::Hidden,
112 "da-disable-delinearization-checks", cl::Hidden,
120 "da-miv-max-level-threshold", cl::init(7), cl::Hidden,
124 //===----------------------------------------------------------------------===//
181 auto *F = DA->getFunction(); in dumpExampleDependence()
184 if (SrcI->mayReadOrWriteMemory()) { in dumpExampleDependence()
187 if (DstI->mayReadOrWriteMemory()) { in dumpExampleDependence()
188 OS << "Src:" << *SrcI << " --> Dst:" << *DstI << "\n"; in dumpExampleDependence()
189 OS << " da analyze - "; in dumpExampleDependence()
190 if (auto D = DA->depends(&*SrcI, &*DstI, true)) { in dumpExampleDependence()
192 if (NormalizeResults && D->normalize(&SE)) in dumpExampleDependence()
193 OS << "normalized - "; in dumpExampleDependence()
194 D->dump(OS); in dumpExampleDependence()
195 for (unsigned Level = 1; Level <= D->getLevels(); Level++) { in dumpExampleDependence() local
196 if (D->isSplitable(Level)) { in dumpExampleDependence()
197 OS << " da analyze - split level = " << Level; in dumpExampleDependence()
198 OS << ", iteration = " << *DA->getSplitIteration(*D, Level); in dumpExampleDependence()
226 //===----------------------------------------------------------------------===//
231 return Src->mayReadFromMemory() && Dst->mayReadFromMemory(); in isInput()
237 return Src->mayWriteToMemory() && Dst->mayWriteToMemory(); in isOutput()
243 return Src->mayWriteToMemory() && Dst->mayReadFromMemory(); in isFlow()
249 return Src->mayReadFromMemory() && Dst->mayWriteToMemory(); in isAnti()
253 // Returns true if a particular level is scalar; that is,
255 // variable associated with the loop at this level.
257 bool Dependence::isScalar(unsigned level) const { in isScalar()
262 //===----------------------------------------------------------------------===//
279 // Dst: use(A[31 - i]);
282 // flow { Src[i] -> Dst[31 - i] : when i >= 16 } and
283 // anti { Dst[i] -> Src[31 - i] : when i < 16 },
284 // -- hence a [<>].
291 for (unsigned Level = 1; Level <= Levels; ++Level) { in isDirectionNegative() local
292 unsigned char Direction = DV[Level - 1].Direction; in isDirectionNegative()
293 if (Direction == Dependence::DVEntry::EQ) in isDirectionNegative()
310 for (unsigned Level = 1; Level <= Levels; ++Level) { in normalize() local
311 unsigned char Direction = DV[Level - 1].Direction; in normalize()
314 unsigned char RevDirection = Direction & Dependence::DVEntry::EQ; in normalize()
319 DV[Level - 1].Direction = RevDirection; in normalize()
321 if (DV[Level - 1].Distance != nullptr) in normalize()
322 DV[Level - 1].Distance = in normalize()
323 SE->getNegativeSCEV(DV[Level - 1].Distance); in normalize()
333 // getDirection - Returns the direction associated with a particular level.
334 unsigned FullDependence::getDirection(unsigned Level) const { in getDirection()
335 assert(0 < Level && Level <= Levels && "Level out of range"); in getDirection()
336 return DV[Level - 1].Direction; in getDirection()
340 // Returns the distance (or NULL) associated with a particular level.
341 const SCEV *FullDependence::getDistance(unsigned Level) const { in getDistance()
342 assert(0 < Level && Level <= Levels && "Level out of range"); in getDistance()
343 return DV[Level - 1].Distance; in getDistance()
347 // Returns true if a particular level is scalar; that is,
349 // variable associated with the loop at this level.
350 bool FullDependence::isScalar(unsigned Level) const { in isScalar()
351 assert(0 < Level && Level <= Levels && "Level out of range"); in isScalar()
352 return DV[Level - 1].Scalar; in isScalar()
358 bool FullDependence::isPeelFirst(unsigned Level) const { in isPeelFirst()
359 assert(0 < Level && Level <= Levels && "Level out of range"); in isPeelFirst()
360 return DV[Level - 1].PeelFirst; in isPeelFirst()
366 bool FullDependence::isPeelLast(unsigned Level) const { in isPeelLast()
367 assert(0 < Level && Level <= Levels && "Level out of range"); in isPeelLast()
368 return DV[Level - 1].PeelLast; in isPeelLast()
373 bool FullDependence::isSplitable(unsigned Level) const { in isSplitable()
374 assert(0 < Level && Level <= Levels && "Level out of range"); in isSplitable()
375 return DV[Level - 1].Splitable; in isSplitable()
379 //===----------------------------------------------------------------------===//
429 return SE->getNegativeSCEV(C); in getD()
460 A = SE->getOne(D->getType()); in setDistance()
461 B = SE->getNegativeSCEV(A); in setDistance()
462 C = SE->getNegativeSCEV(D); in setDistance()
504 LLVM_DEBUG(dbgs() << "\t X ="; X->dump(dbgs())); in intersectConstraints()
505 LLVM_DEBUG(dbgs() << "\t Y ="; Y->dump(dbgs())); in intersectConstraints()
506 assert(!Y->isPoint() && "Y must not be a Point"); in intersectConstraints()
507 if (X->isAny()) { in intersectConstraints()
508 if (Y->isAny()) in intersectConstraints()
513 if (X->isEmpty()) in intersectConstraints()
515 if (Y->isEmpty()) { in intersectConstraints()
516 X->setEmpty(); in intersectConstraints()
520 if (X->isDistance() && Y->isDistance()) { in intersectConstraints()
522 if (isKnownPredicate(CmpInst::ICMP_EQ, X->getD(), Y->getD())) in intersectConstraints()
524 if (isKnownPredicate(CmpInst::ICMP_NE, X->getD(), Y->getD())) { in intersectConstraints()
525 X->setEmpty(); in intersectConstraints()
531 if (isa<SCEVConstant>(Y->getD())) { in intersectConstraints()
538 // At this point, the pseudo-code in Figure 4 of the paper in intersectConstraints()
539 // checks if (X->isPoint() && Y->isPoint()). in intersectConstraints()
542 // two Line constraints, and the right-hand value, Y, is never in intersectConstraints()
544 assert(!(X->isPoint() && Y->isPoint()) && in intersectConstraints()
545 "We shouldn't ever see X->isPoint() && Y->isPoint()"); in intersectConstraints()
547 if (X->isLine() && Y->isLine()) { in intersectConstraints()
549 const SCEV *Prod1 = SE->getMulExpr(X->getA(), Y->getB()); in intersectConstraints()
550 const SCEV *Prod2 = SE->getMulExpr(X->getB(), Y->getA()); in intersectConstraints()
554 Prod1 = SE->getMulExpr(X->getC(), Y->getB()); in intersectConstraints()
555 Prod2 = SE->getMulExpr(X->getB(), Y->getC()); in intersectConstraints()
559 X->setEmpty(); in intersectConstraints()
568 const SCEV *C1B2 = SE->getMulExpr(X->getC(), Y->getB()); in intersectConstraints()
569 const SCEV *C1A2 = SE->getMulExpr(X->getC(), Y->getA()); in intersectConstraints()
570 const SCEV *C2B1 = SE->getMulExpr(Y->getC(), X->getB()); in intersectConstraints()
571 const SCEV *C2A1 = SE->getMulExpr(Y->getC(), X->getA()); in intersectConstraints()
572 const SCEV *A1B2 = SE->getMulExpr(X->getA(), Y->getB()); in intersectConstraints()
573 const SCEV *A2B1 = SE->getMulExpr(Y->getA(), X->getB()); in intersectConstraints()
575 dyn_cast<SCEVConstant>(SE->getMinusSCEV(C1A2, C2A1)); in intersectConstraints()
577 dyn_cast<SCEVConstant>(SE->getMinusSCEV(C1B2, C2B1)); in intersectConstraints()
579 dyn_cast<SCEVConstant>(SE->getMinusSCEV(A1B2, A2B1)); in intersectConstraints()
581 dyn_cast<SCEVConstant>(SE->getMinusSCEV(A2B1, A1B2)); in intersectConstraints()
585 APInt Xtop = C1B2_C2B1->getAPInt(); in intersectConstraints()
586 APInt Xbot = A1B2_A2B1->getAPInt(); in intersectConstraints()
587 APInt Ytop = C1A2_C2A1->getAPInt(); in intersectConstraints()
588 APInt Ybot = A2B1_A1B2->getAPInt(); in intersectConstraints()
600 X->setEmpty(); in intersectConstraints()
606 X->setEmpty(); in intersectConstraints()
611 collectConstantUpperBound(X->getAssociatedLoop(), Prod1->getType())) { in intersectConstraints()
612 const APInt &UpperBound = CUB->getAPInt(); in intersectConstraints()
615 X->setEmpty(); in intersectConstraints()
620 X->setPoint(SE->getConstant(Xq), in intersectConstraints()
621 SE->getConstant(Yq), in intersectConstraints()
622 X->getAssociatedLoop()); in intersectConstraints()
629 // if (X->isLine() && Y->isPoint()) This case can't occur. in intersectConstraints()
630 assert(!(X->isLine() && Y->isPoint()) && "This case should never occur"); in intersectConstraints()
632 if (X->isPoint() && Y->isLine()) { in intersectConstraints()
634 const SCEV *A1X1 = SE->getMulExpr(Y->getA(), X->getX()); in intersectConstraints()
635 const SCEV *B1Y1 = SE->getMulExpr(Y->getB(), X->getY()); in intersectConstraints()
636 const SCEV *Sum = SE->getAddExpr(A1X1, B1Y1); in intersectConstraints()
637 if (isKnownPredicate(CmpInst::ICMP_EQ, Sum, Y->getC())) in intersectConstraints()
639 if (isKnownPredicate(CmpInst::ICMP_NE, Sum, Y->getC())) { in intersectConstraints()
640 X->setEmpty(); in intersectConstraints()
652 //===----------------------------------------------------------------------===//
690 if (Direction & DVEntry::EQ) in dump()
712 // tbaa, non-overlapping regions etc), then it is known there is no dependecy.
725 if (AA->isNoAlias(LocAS, LocBS)) in underlyingObjectsAlias()
752 return LI->isUnordered(); in isLoadOrStore()
754 return SI->isUnordered(); in isLoadOrStore()
763 // loop. The routine establishNestingLevels finds the level of most deeply
765 // not contained in a loop is at level = 0. MaxLevels is equal to the level
766 // of the source plus the level of the destination, minus CommonLevels.
772 // 0 - unused
773 // 1 - outermost common loop
774 // ... - other common loops
775 // CommonLevels - innermost common loop
776 // ... - loops containing Src but not Dst
777 // SrcLevels - innermost loop containing Src but not Dst
778 // ... - loops containing Dst but not Src
779 // MaxLevels - innermost loops containing Dst but not Src
802 // a - 1
803 // b - 2 = CommonLevels
804 // c - 3
805 // d - 4 = SrcLevels
806 // e - 5
807 // f - 6
808 // g - 7 = MaxLevels
811 const BasicBlock *SrcBlock = Src->getParent(); in establishNestingLevels()
812 const BasicBlock *DstBlock = Dst->getParent(); in establishNestingLevels()
813 unsigned SrcLevel = LI->getLoopDepth(SrcBlock); in establishNestingLevels()
814 unsigned DstLevel = LI->getLoopDepth(DstBlock); in establishNestingLevels()
815 const Loop *SrcLoop = LI->getLoopFor(SrcBlock); in establishNestingLevels()
816 const Loop *DstLoop = LI->getLoopFor(DstBlock); in establishNestingLevels()
820 SrcLoop = SrcLoop->getParentLoop(); in establishNestingLevels()
821 SrcLevel--; in establishNestingLevels()
824 DstLoop = DstLoop->getParentLoop(); in establishNestingLevels()
825 DstLevel--; in establishNestingLevels()
828 SrcLoop = SrcLoop->getParentLoop(); in establishNestingLevels()
829 DstLoop = DstLoop->getParentLoop(); in establishNestingLevels()
830 SrcLevel--; in establishNestingLevels()
833 MaxLevels -= CommonLevels; in establishNestingLevels()
838 // its level index in our numbering scheme.
840 return SrcLoop->getLoopDepth(); in mapSrcLoop()
845 // return its level index in our numbering scheme.
847 unsigned D = DstLoop->getLoopDepth(); in mapDstLoop()
851 return D - CommonLevels + SrcLevels; in mapDstLoop()
869 return SE->isLoopInvariant(Expression, LoopNest->getOutermostLoop()); in isLoopInvariant()
875 // have a level <= CommonLevels and are referred to by the SCEV Expression.
880 unsigned Level = LoopNest->getLoopDepth(); in collectCommonLoops() local
881 if (Level <= CommonLevels && !SE->isLoopInvariant(Expression, LoopNest)) in collectCommonLoops()
882 Loops.set(Level); in collectCommonLoops()
883 LoopNest = LoopNest->getParentLoop(); in collectCommonLoops()
895 const SCEV *Src = Pair->Src; in unifySubscriptType()
896 const SCEV *Dst = Pair->Dst; in unifySubscriptType()
897 IntegerType *SrcTy = dyn_cast<IntegerType>(Src->getType()); in unifySubscriptType()
898 IntegerType *DstTy = dyn_cast<IntegerType>(Dst->getType()); in unifySubscriptType()
905 if (SrcTy->getBitWidth() > widestWidthSeen) { in unifySubscriptType()
906 widestWidthSeen = SrcTy->getBitWidth(); in unifySubscriptType()
909 if (DstTy->getBitWidth() > widestWidthSeen) { in unifySubscriptType()
910 widestWidthSeen = DstTy->getBitWidth(); in unifySubscriptType()
920 const SCEV *Src = Pair->Src; in unifySubscriptType()
921 const SCEV *Dst = Pair->Dst; in unifySubscriptType()
922 IntegerType *SrcTy = dyn_cast<IntegerType>(Src->getType()); in unifySubscriptType()
923 IntegerType *DstTy = dyn_cast<IntegerType>(Dst->getType()); in unifySubscriptType()
930 if (SrcTy->getBitWidth() < widestWidthSeen) in unifySubscriptType()
931 // Sign-extend Src to widestType in unifySubscriptType()
932 Pair->Src = SE->getSignExtendExpr(Src, widestType); in unifySubscriptType()
933 if (DstTy->getBitWidth() < widestWidthSeen) { in unifySubscriptType()
934 // Sign-extend Dst to widestType in unifySubscriptType()
935 Pair->Dst = SE->getSignExtendExpr(Dst, widestType); in unifySubscriptType()
940 // removeMatchingExtensions - Examines a subscript pair.
945 const SCEV *Src = Pair->Src; in removeMatchingExtensions()
946 const SCEV *Dst = Pair->Dst; in removeMatchingExtensions()
951 const SCEV *SrcCastOp = SrcCast->getOperand(); in removeMatchingExtensions()
952 const SCEV *DstCastOp = DstCast->getOperand(); in removeMatchingExtensions()
953 if (SrcCastOp->getType() == DstCastOp->getType()) { in removeMatchingExtensions()
954 Pair->Src = SrcCastOp; in removeMatchingExtensions()
955 Pair->Dst = DstCastOp; in removeMatchingExtensions()
974 while (L && AddRec->getLoop() != L) in checkSubscript()
975 L = L->getParentLoop(); in checkSubscript()
979 const SCEV *Start = AddRec->getStart(); in checkSubscript()
980 const SCEV *Step = AddRec->getStepRecurrence(*SE); in checkSubscript()
981 const SCEV *UB = SE->getBackedgeTakenCount(AddRec->getLoop()); in checkSubscript()
983 if (SE->getTypeSizeInBits(Start->getType()) < in checkSubscript()
984 SE->getTypeSizeInBits(UB->getType())) { in checkSubscript()
985 if (!AddRec->getNoWrapFlags()) in checkSubscript()
992 Loops.set(mapSrcLoop(AddRec->getLoop())); in checkSubscript()
994 Loops.set(mapDstLoop(AddRec->getLoop())); in checkSubscript()
1061 const SCEV *Xop = CX->getOperand(); in isKnownPredicate()
1062 const SCEV *Yop = CY->getOperand(); in isKnownPredicate()
1063 if (Xop->getType() == Yop->getType()) { in isKnownPredicate()
1069 if (SE->isKnownPredicate(Pred, X, Y)) in isKnownPredicate()
1071 // If SE->isKnownPredicate can't prove the condition, in isKnownPredicate()
1072 // we try the brute-force approach of subtracting in isKnownPredicate()
1074 // By testing with SE->isKnownPredicate first, we avoid in isKnownPredicate()
1076 const SCEV *Delta = SE->getMinusSCEV(X, Y); in isKnownPredicate()
1079 return Delta->isZero(); in isKnownPredicate()
1081 return SE->isKnownNonZero(Delta); in isKnownPredicate()
1083 return SE->isKnownNonNegative(Delta); in isKnownPredicate()
1085 return SE->isKnownNonPositive(Delta); in isKnownPredicate()
1087 return SE->isKnownPositive(Delta); in isKnownPredicate()
1089 return SE->isKnownNegative(Delta); in isKnownPredicate()
1095 /// Compare to see if S is less than Size, using isKnownNegative(S - max(Size, 1))
1096 /// with some extra checking if S is an AddRec and we can prove less-than using
1100 auto *SType = dyn_cast<IntegerType>(S->getType()); in isKnownLessThan()
1101 auto *SizeType = dyn_cast<IntegerType>(Size->getType()); in isKnownLessThan()
1105 (SType->getBitWidth() >= SizeType->getBitWidth()) ? SType : SizeType; in isKnownLessThan()
1106 S = SE->getTruncateOrZeroExtend(S, MaxType); in isKnownLessThan()
1107 Size = SE->getTruncateOrZeroExtend(Size, MaxType); in isKnownLessThan()
1110 const SCEV *Bound = SE->getMinusSCEV(S, Size); in isKnownLessThan()
1112 if (AddRec->isAffine()) { in isKnownLessThan()
1113 const SCEV *BECount = SE->getBackedgeTakenCount(AddRec->getLoop()); in isKnownLessThan()
1115 const SCEV *Limit = AddRec->evaluateAtIteration(BECount, *SE); in isKnownLessThan()
1116 if (SE->isKnownNegative(Limit)) in isKnownLessThan()
1124 SE->getMinusSCEV(S, SE->getSMaxExpr(Size, SE->getOne(Size->getType()))); in isKnownLessThan()
1125 return SE->isKnownNegative(LimitedBound); in isKnownLessThan()
1131 Inbounds = SrcGEP->isInBounds(); in isKnownNonNegative()
1134 if (AddRec->isAffine()) { in isKnownNonNegative()
1137 if (SE->isKnownNonNegative(AddRec->getStart()) && in isKnownNonNegative()
1138 SE->isKnownNonNegative(AddRec->getOperand(1))) in isKnownNonNegative()
1144 return SE->isKnownNonNegative(S); in isKnownNonNegative()
1155 if (SE->hasLoopInvariantBackedgeTakenCount(L)) { in collectUpperBound()
1156 const SCEV *UB = SE->getBackedgeTakenCount(L); in collectUpperBound()
1157 return SE->getTruncateOrZeroExtend(UB, T); in collectUpperBound()
1173 // testZIV -
1203 // strongSIVtest -
1219 // d = i' - i = (c1 - c2)/a
1232 unsigned Level, FullDependence &Result, in strongSIVtest() argument
1236 LLVM_DEBUG(dbgs() << ", " << *Coeff->getType() << "\n"); in strongSIVtest()
1238 LLVM_DEBUG(dbgs() << ", " << *SrcConst->getType() << "\n"); in strongSIVtest()
1240 LLVM_DEBUG(dbgs() << ", " << *DstConst->getType() << "\n"); in strongSIVtest()
1242 assert(0 < Level && Level <= CommonLevels && "level out of range"); in strongSIVtest()
1243 Level--; in strongSIVtest()
1245 const SCEV *Delta = SE->getMinusSCEV(SrcConst, DstConst); in strongSIVtest()
1247 LLVM_DEBUG(dbgs() << ", " << *Delta->getType() << "\n"); in strongSIVtest()
1250 if (const SCEV *UpperBound = collectUpperBound(CurLoop, Delta->getType())) { in strongSIVtest()
1252 LLVM_DEBUG(dbgs() << ", " << *UpperBound->getType() << "\n"); in strongSIVtest()
1254 SE->isKnownNonNegative(Delta) ? Delta : SE->getNegativeSCEV(Delta); in strongSIVtest()
1256 SE->isKnownNonNegative(Coeff) ? Coeff : SE->getNegativeSCEV(Coeff); in strongSIVtest()
1257 const SCEV *Product = SE->getMulExpr(UpperBound, AbsCoeff); in strongSIVtest()
1259 // Distance greater than trip count - no dependence in strongSIVtest()
1268 APInt ConstDelta = cast<SCEVConstant>(Delta)->getAPInt(); in strongSIVtest()
1269 APInt ConstCoeff = cast<SCEVConstant>(Coeff)->getAPInt(); in strongSIVtest()
1282 Result.DV[Level].Distance = SE->getConstant(Distance); in strongSIVtest()
1283 NewConstraint.setDistance(SE->getConstant(Distance), CurLoop); in strongSIVtest()
1285 Result.DV[Level].Direction &= Dependence::DVEntry::LT; in strongSIVtest()
1287 Result.DV[Level].Direction &= Dependence::DVEntry::GT; in strongSIVtest()
1289 Result.DV[Level].Direction &= Dependence::DVEntry::EQ; in strongSIVtest()
1292 else if (Delta->isZero()) { in strongSIVtest()
1294 Result.DV[Level].Distance = Delta; in strongSIVtest()
1296 Result.DV[Level].Direction &= Dependence::DVEntry::EQ; in strongSIVtest()
1300 if (Coeff->isOne()) { in strongSIVtest()
1302 Result.DV[Level].Distance = Delta; // since X/1 == X in strongSIVtest()
1308 SE->getNegativeSCEV(Coeff), in strongSIVtest()
1309 SE->getNegativeSCEV(Delta), CurLoop); in strongSIVtest()
1313 bool DeltaMaybeZero = !SE->isKnownNonZero(Delta); in strongSIVtest()
1314 bool DeltaMaybePositive = !SE->isKnownNonPositive(Delta); in strongSIVtest()
1315 bool DeltaMaybeNegative = !SE->isKnownNonNegative(Delta); in strongSIVtest()
1316 bool CoeffMaybePositive = !SE->isKnownNonPositive(Coeff); in strongSIVtest()
1317 bool CoeffMaybeNegative = !SE->isKnownNonNegative(Coeff); in strongSIVtest()
1319 // It helps to read !SE->isKnownNonZero(Delta) in strongSIVtest()
1326 NewDirection |= Dependence::DVEntry::EQ; in strongSIVtest()
1330 if (NewDirection < Result.DV[Level].Direction) in strongSIVtest()
1332 Result.DV[Level].Direction &= NewDirection; in strongSIVtest()
1338 // weakCrossingSIVtest -
1341 // When we have a pair of subscripts of the form [c1 + a*i] and [c2 - a*i],
1344 // Weak-Crossing SIV test.
1346 // Given c1 + a*i = c2 - a*i', we can look for the intersection of
1349 // c1 + a*i = c2 - a*i
1350 // 2a*i = c2 - c1
1351 // i = (c2 - c1)/2a
1358 // If the non-integer part = 1/2, there's a dependence (<> directions).
1368 const Loop *CurLoop, unsigned Level, FullDependence &Result, in weakCrossingSIVtest() argument
1370 LLVM_DEBUG(dbgs() << "\tWeak-Crossing SIV test\n"); in weakCrossingSIVtest()
1375 assert(0 < Level && Level <= CommonLevels && "Level out of range"); in weakCrossingSIVtest()
1376 Level--; in weakCrossingSIVtest()
1378 const SCEV *Delta = SE->getMinusSCEV(DstConst, SrcConst); in weakCrossingSIVtest()
1381 if (Delta->isZero()) { in weakCrossingSIVtest()
1382 Result.DV[Level].Direction &= ~Dependence::DVEntry::LT; in weakCrossingSIVtest()
1383 Result.DV[Level].Direction &= ~Dependence::DVEntry::GT; in weakCrossingSIVtest()
1385 if (!Result.DV[Level].Direction) { in weakCrossingSIVtest()
1389 Result.DV[Level].Distance = Delta; // = 0 in weakCrossingSIVtest()
1396 Result.DV[Level].Splitable = true; in weakCrossingSIVtest()
1397 if (SE->isKnownNegative(ConstCoeff)) { in weakCrossingSIVtest()
1398 ConstCoeff = dyn_cast<SCEVConstant>(SE->getNegativeSCEV(ConstCoeff)); in weakCrossingSIVtest()
1401 Delta = SE->getNegativeSCEV(Delta); in weakCrossingSIVtest()
1403 assert(SE->isKnownPositive(ConstCoeff) && "ConstCoeff should be positive"); in weakCrossingSIVtest()
1406 SplitIter = SE->getUDivExpr( in weakCrossingSIVtest()
1407 SE->getSMaxExpr(SE->getZero(Delta->getType()), Delta), in weakCrossingSIVtest()
1408 SE->getMulExpr(SE->getConstant(Delta->getType(), 2), ConstCoeff)); in weakCrossingSIVtest()
1419 if (SE->isKnownNegative(Delta)) { in weakCrossingSIVtest()
1428 if (const SCEV *UpperBound = collectUpperBound(CurLoop, Delta->getType())) { in weakCrossingSIVtest()
1430 const SCEV *ConstantTwo = SE->getConstant(UpperBound->getType(), 2); in weakCrossingSIVtest()
1431 const SCEV *ML = SE->getMulExpr(SE->getMulExpr(ConstCoeff, UpperBound), in weakCrossingSIVtest()
1442 Result.DV[Level].Direction &= ~Dependence::DVEntry::LT; in weakCrossingSIVtest()
1443 Result.DV[Level].Direction &= ~Dependence::DVEntry::GT; in weakCrossingSIVtest()
1445 if (!Result.DV[Level].Direction) { in weakCrossingSIVtest()
1449 Result.DV[Level].Splitable = false; in weakCrossingSIVtest()
1450 Result.DV[Level].Distance = SE->getZero(Delta->getType()); in weakCrossingSIVtest()
1456 APInt APDelta = ConstDelta->getAPInt(); in weakCrossingSIVtest()
1457 APInt APCoeff = ConstCoeff->getAPInt(); in weakCrossingSIVtest()
1476 Result.DV[Level].Direction &= ~Dependence::DVEntry::EQ; in weakCrossingSIVtest()
1491 // Also finds a solution to the equation ax - by = gcd(a, b).
1503 APInt A2 = A0 - Q*A1; A0 = A1; A1 = A2; in findGCD()
1504 APInt B2 = B0 - Q*B1; B0 = B1; B1 = B2; in findGCD()
1510 X = AM.slt(0) ? -A1 : A1; in findGCD()
1511 Y = BM.slt(0) ? B1 : -B1; in findGCD()
1531 return Q - 1; in floorOfQuotient()
1547 // exactSIVtest -
1557 // It's slower than the specialized tests (strong SIV, weak-zero SIV, etc),
1568 const Loop *CurLoop, unsigned Level, in exactSIVtest() argument
1577 assert(0 < Level && Level <= CommonLevels && "Level out of range"); in exactSIVtest()
1578 Level--; in exactSIVtest()
1580 const SCEV *Delta = SE->getMinusSCEV(DstConst, SrcConst); in exactSIVtest()
1582 NewConstraint.setLine(SrcCoeff, SE->getNegativeSCEV(DstCoeff), Delta, in exactSIVtest()
1592 APInt AM = ConstSrcCoeff->getAPInt(); in exactSIVtest()
1593 APInt BM = ConstDstCoeff->getAPInt(); in exactSIVtest()
1594 APInt CM = ConstDelta->getAPInt(); in exactSIVtest()
1610 collectConstantUpperBound(CurLoop, Delta->getType())) { in exactSIVtest()
1611 UM = CUB->getAPInt(); in exactSIVtest()
1628 TLVec.push_back(ceilingOfQuotient(-TX, TB)); in exactSIVtest()
1630 // New bound check - modification to Banerjee's e3 check in exactSIVtest()
1632 TUVec.push_back(floorOfQuotient(UM - TX, TB)); in exactSIVtest()
1636 TUVec.push_back(floorOfQuotient(-TX, TB)); in exactSIVtest()
1638 // New bound check - modification to Banerjee's e3 check in exactSIVtest()
1640 TLVec.push_back(ceilingOfQuotient(UM - TX, TB)); in exactSIVtest()
1648 TUVec.push_back(floorOfQuotient(UM - TY, TA)); in exactSIVtest()
1651 // New bound check - modification to Banerjee's e3 check in exactSIVtest()
1652 TLVec.push_back(ceilingOfQuotient(-TY, TA)); in exactSIVtest()
1656 TLVec.push_back(ceilingOfQuotient(UM - TY, TA)); in exactSIVtest()
1659 // New bound check - modification to Banerjee's e3 check in exactSIVtest()
1660 TUVec.push_back(floorOfQuotient(-TY, TA)); in exactSIVtest()
1684 LowerDistance = (TY - TX) + (TA - TB) * TL; in exactSIVtest()
1685 UpperDistance = (TY - TX) + (TA - TB) * TU; in exactSIVtest()
1687 LowerDistance = (TY - TX) + (TA - TB) * TU; in exactSIVtest()
1688 UpperDistance = (TY - TX) + (TA - TB) * TL; in exactSIVtest()
1696 NewDirection |= Dependence::DVEntry::EQ; in exactSIVtest()
1709 Result.DV[Level].Direction &= NewDirection; in exactSIVtest()
1710 if (Result.DV[Level].Direction == Dependence::DVEntry::NONE) in exactSIVtest()
1714 return Result.DV[Level].Direction == Dependence::DVEntry::NONE; in exactSIVtest()
1722 const APInt &ConstDividend = Dividend->getAPInt(); in isRemainderZero()
1723 const APInt &ConstDivisor = Divisor->getAPInt(); in isRemainderZero()
1728 // weakZeroSrcSIVtest -
1734 // Weak-Zero SIV test.
1742 // (c1 - c2)/a = i
1762 const Loop *CurLoop, unsigned Level, in weakZeroSrcSIVtest() argument
1768 LLVM_DEBUG(dbgs() << "\tWeak-Zero (src) SIV test\n"); in weakZeroSrcSIVtest()
1773 assert(0 < Level && Level <= MaxLevels && "Level out of range"); in weakZeroSrcSIVtest()
1774 Level--; in weakZeroSrcSIVtest()
1776 const SCEV *Delta = SE->getMinusSCEV(SrcConst, DstConst); in weakZeroSrcSIVtest()
1777 NewConstraint.setLine(SE->getZero(Delta->getType()), DstCoeff, Delta, in weakZeroSrcSIVtest()
1781 if (Level < CommonLevels) { in weakZeroSrcSIVtest()
1782 Result.DV[Level].Direction &= Dependence::DVEntry::GE; in weakZeroSrcSIVtest()
1783 Result.DV[Level].PeelFirst = true; in weakZeroSrcSIVtest()
1792 SE->isKnownNegative(ConstCoeff) ? in weakZeroSrcSIVtest()
1793 SE->getNegativeSCEV(ConstCoeff) : ConstCoeff; in weakZeroSrcSIVtest()
1795 SE->isKnownNegative(ConstCoeff) ? SE->getNegativeSCEV(Delta) : Delta; in weakZeroSrcSIVtest()
1799 if (const SCEV *UpperBound = collectUpperBound(CurLoop, Delta->getType())) { in weakZeroSrcSIVtest()
1801 const SCEV *Product = SE->getMulExpr(AbsCoeff, UpperBound); in weakZeroSrcSIVtest()
1809 if (Level < CommonLevels) { in weakZeroSrcSIVtest()
1810 Result.DV[Level].Direction &= Dependence::DVEntry::LE; in weakZeroSrcSIVtest()
1811 Result.DV[Level].PeelLast = true; in weakZeroSrcSIVtest()
1820 if (SE->isKnownNegative(NewDelta)) { in weakZeroSrcSIVtest()
1838 // weakZeroDstSIVtest -
1844 // Weak-Zero SIV test.
1852 // i = (c2 - c1)/a
1872 const Loop *CurLoop, unsigned Level, in weakZeroDstSIVtest() argument
1877 LLVM_DEBUG(dbgs() << "\tWeak-Zero (dst) SIV test\n"); in weakZeroDstSIVtest()
1882 assert(0 < Level && Level <= SrcLevels && "Level out of range"); in weakZeroDstSIVtest()
1883 Level--; in weakZeroDstSIVtest()
1885 const SCEV *Delta = SE->getMinusSCEV(DstConst, SrcConst); in weakZeroDstSIVtest()
1886 NewConstraint.setLine(SrcCoeff, SE->getZero(Delta->getType()), Delta, in weakZeroDstSIVtest()
1890 if (Level < CommonLevels) { in weakZeroDstSIVtest()
1891 Result.DV[Level].Direction &= Dependence::DVEntry::LE; in weakZeroDstSIVtest()
1892 Result.DV[Level].PeelFirst = true; in weakZeroDstSIVtest()
1901 SE->isKnownNegative(ConstCoeff) ? in weakZeroDstSIVtest()
1902 SE->getNegativeSCEV(ConstCoeff) : ConstCoeff; in weakZeroDstSIVtest()
1904 SE->isKnownNegative(ConstCoeff) ? SE->getNegativeSCEV(Delta) : Delta; in weakZeroDstSIVtest()
1908 if (const SCEV *UpperBound = collectUpperBound(CurLoop, Delta->getType())) { in weakZeroDstSIVtest()
1910 const SCEV *Product = SE->getMulExpr(AbsCoeff, UpperBound); in weakZeroDstSIVtest()
1918 if (Level < CommonLevels) { in weakZeroDstSIVtest()
1919 Result.DV[Level].Direction &= Dependence::DVEntry::GE; in weakZeroDstSIVtest()
1920 Result.DV[Level].PeelLast = true; in weakZeroDstSIVtest()
1929 if (SE->isKnownNegative(NewDelta)) { in weakZeroDstSIVtest()
1947 // exactRDIVtest - Tests the RDIV subscript pair for dependence.
1965 const SCEV *Delta = SE->getMinusSCEV(DstConst, SrcConst); in exactRDIVtest()
1975 APInt AM = ConstSrcCoeff->getAPInt(); in exactRDIVtest()
1976 APInt BM = ConstDstCoeff->getAPInt(); in exactRDIVtest()
1977 APInt CM = ConstDelta->getAPInt(); in exactRDIVtest()
1992 collectConstantUpperBound(SrcLoop, Delta->getType())) { in exactRDIVtest()
1993 SrcUM = UpperBound->getAPInt(); in exactRDIVtest()
2002 collectConstantUpperBound(DstLoop, Delta->getType())) { in exactRDIVtest()
2003 DstUM = UpperBound->getAPInt(); in exactRDIVtest()
2020 TLVec.push_back(ceilingOfQuotient(-TX, TB)); in exactRDIVtest()
2023 TUVec.push_back(floorOfQuotient(SrcUM - TX, TB)); in exactRDIVtest()
2027 TUVec.push_back(floorOfQuotient(-TX, TB)); in exactRDIVtest()
2030 TLVec.push_back(ceilingOfQuotient(SrcUM - TX, TB)); in exactRDIVtest()
2037 TLVec.push_back(ceilingOfQuotient(-TY, TA)); in exactRDIVtest()
2040 TUVec.push_back(floorOfQuotient(DstUM - TY, TA)); in exactRDIVtest()
2044 TUVec.push_back(floorOfQuotient(-TY, TA)); in exactRDIVtest()
2047 TLVec.push_back(ceilingOfQuotient(DstUM - TY, TA)); in exactRDIVtest()
2069 // symbolicRDIVtest -
2072 // Extreme-Value Test) that can handle some of the SIV and RDIV cases,
2088 // a1*i - a2*j = c2 - c1
2090 // To test for a dependence, we compute c2 - c1 and make sure it's in the
2091 // range of the maximum and minimum possible values of a1*i - a2*j.
2095 // a1*0 - a2*N2 <= c2 - c1 <= a1*N1 - a2*0
2096 // -a2*N2 <= c2 - c1 <= a1*N1
2099 // a1*0 - a2*0 <= c2 - c1 <= a1*N1 - a2*N2
2100 // 0 <= c2 - c1 <= a1*N1 - a2*N2
2103 // a1*N1 - a2*N2 <= c2 - c1 <= a1*0 - a2*0
2104 // a1*N1 - a2*N2 <= c2 - c1 <= 0
2107 // a1*N1 - a2*0 <= c2 - c1 <= a1*0 - a2*N2
2108 // a1*N1 <= c2 - c1 <= -a2*N2
2118 LLVM_DEBUG(dbgs() << ", type = " << *A1->getType() << "\n"); in symbolicRDIVtest()
2122 const SCEV *N1 = collectUpperBound(Loop1, A1->getType()); in symbolicRDIVtest()
2123 const SCEV *N2 = collectUpperBound(Loop2, A1->getType()); in symbolicRDIVtest()
2126 const SCEV *C2_C1 = SE->getMinusSCEV(C2, C1); in symbolicRDIVtest()
2127 const SCEV *C1_C2 = SE->getMinusSCEV(C1, C2); in symbolicRDIVtest()
2128 LLVM_DEBUG(dbgs() << "\t C2 - C1 = " << *C2_C1 << "\n"); in symbolicRDIVtest()
2129 LLVM_DEBUG(dbgs() << "\t C1 - C2 = " << *C1_C2 << "\n"); in symbolicRDIVtest()
2130 if (SE->isKnownNonNegative(A1)) { in symbolicRDIVtest()
2131 if (SE->isKnownNonNegative(A2)) { in symbolicRDIVtest()
2134 // make sure that c2 - c1 <= a1*N1 in symbolicRDIVtest()
2135 const SCEV *A1N1 = SE->getMulExpr(A1, N1); in symbolicRDIVtest()
2143 // make sure that -a2*N2 <= c2 - c1, or a2*N2 >= c1 - c2 in symbolicRDIVtest()
2144 const SCEV *A2N2 = SE->getMulExpr(A2, N2); in symbolicRDIVtest()
2152 else if (SE->isKnownNonPositive(A2)) { in symbolicRDIVtest()
2155 // make sure that c2 - c1 <= a1*N1 - a2*N2 in symbolicRDIVtest()
2156 const SCEV *A1N1 = SE->getMulExpr(A1, N1); in symbolicRDIVtest()
2157 const SCEV *A2N2 = SE->getMulExpr(A2, N2); in symbolicRDIVtest()
2158 const SCEV *A1N1_A2N2 = SE->getMinusSCEV(A1N1, A2N2); in symbolicRDIVtest()
2159 LLVM_DEBUG(dbgs() << "\t A1*N1 - A2*N2 = " << *A1N1_A2N2 << "\n"); in symbolicRDIVtest()
2165 // make sure that 0 <= c2 - c1 in symbolicRDIVtest()
2166 if (SE->isKnownNegative(C2_C1)) { in symbolicRDIVtest()
2172 else if (SE->isKnownNonPositive(A1)) { in symbolicRDIVtest()
2173 if (SE->isKnownNonNegative(A2)) { in symbolicRDIVtest()
2176 // make sure that a1*N1 - a2*N2 <= c2 - c1 in symbolicRDIVtest()
2177 const SCEV *A1N1 = SE->getMulExpr(A1, N1); in symbolicRDIVtest()
2178 const SCEV *A2N2 = SE->getMulExpr(A2, N2); in symbolicRDIVtest()
2179 const SCEV *A1N1_A2N2 = SE->getMinusSCEV(A1N1, A2N2); in symbolicRDIVtest()
2180 LLVM_DEBUG(dbgs() << "\t A1*N1 - A2*N2 = " << *A1N1_A2N2 << "\n"); in symbolicRDIVtest()
2186 // make sure that c2 - c1 <= 0 in symbolicRDIVtest()
2187 if (SE->isKnownPositive(C2_C1)) { in symbolicRDIVtest()
2192 else if (SE->isKnownNonPositive(A2)) { in symbolicRDIVtest()
2195 // make sure that a1*N1 <= c2 - c1 in symbolicRDIVtest()
2196 const SCEV *A1N1 = SE->getMulExpr(A1, N1); in symbolicRDIVtest()
2204 // make sure that c2 - c1 <= -a2*N2, or c1 - c2 >= a2*N2 in symbolicRDIVtest()
2205 const SCEV *A2N2 = SE->getMulExpr(A2, N2); in symbolicRDIVtest()
2218 // testSIV -
2219 // When we have a pair of subscripts of the form [c1 + a1*i] and [c2 - a2*i]
2226 bool DependenceInfo::testSIV(const SCEV *Src, const SCEV *Dst, unsigned &Level, in testSIV() argument
2234 const SCEV *SrcConst = SrcAddRec->getStart(); in testSIV()
2235 const SCEV *DstConst = DstAddRec->getStart(); in testSIV()
2236 const SCEV *SrcCoeff = SrcAddRec->getStepRecurrence(*SE); in testSIV()
2237 const SCEV *DstCoeff = DstAddRec->getStepRecurrence(*SE); in testSIV()
2238 const Loop *CurLoop = SrcAddRec->getLoop(); in testSIV()
2239 assert(CurLoop == DstAddRec->getLoop() && in testSIV()
2241 Level = mapSrcLoop(CurLoop); in testSIV()
2245 Level, Result, NewConstraint); in testSIV()
2246 else if (SrcCoeff == SE->getNegativeSCEV(DstCoeff)) in testSIV()
2248 Level, Result, NewConstraint, SplitIter); in testSIV()
2251 Level, Result, NewConstraint); in testSIV()
2257 const SCEV *SrcConst = SrcAddRec->getStart(); in testSIV()
2258 const SCEV *SrcCoeff = SrcAddRec->getStepRecurrence(*SE); in testSIV()
2260 const Loop *CurLoop = SrcAddRec->getLoop(); in testSIV()
2261 Level = mapSrcLoop(CurLoop); in testSIV()
2263 Level, Result, NewConstraint) || in testSIV()
2267 const SCEV *DstConst = DstAddRec->getStart(); in testSIV()
2268 const SCEV *DstCoeff = DstAddRec->getStepRecurrence(*SE); in testSIV()
2270 const Loop *CurLoop = DstAddRec->getLoop(); in testSIV()
2271 Level = mapDstLoop(CurLoop); in testSIV()
2273 CurLoop, Level, Result, NewConstraint) || in testSIV()
2281 // testRDIV -
2288 // the Weak-crossing SIV test.
2311 SrcConst = SrcAddRec->getStart(); in testRDIV()
2312 SrcCoeff = SrcAddRec->getStepRecurrence(*SE); in testRDIV()
2313 SrcLoop = SrcAddRec->getLoop(); in testRDIV()
2314 DstConst = DstAddRec->getStart(); in testRDIV()
2315 DstCoeff = DstAddRec->getStepRecurrence(*SE); in testRDIV()
2316 DstLoop = DstAddRec->getLoop(); in testRDIV()
2320 dyn_cast<SCEVAddRecExpr>(SrcAddRec->getStart())) { in testRDIV()
2321 SrcConst = tmpAddRec->getStart(); in testRDIV()
2322 SrcCoeff = tmpAddRec->getStepRecurrence(*SE); in testRDIV()
2323 SrcLoop = tmpAddRec->getLoop(); in testRDIV()
2325 DstCoeff = SE->getNegativeSCEV(SrcAddRec->getStepRecurrence(*SE)); in testRDIV()
2326 DstLoop = SrcAddRec->getLoop(); in testRDIV()
2333 dyn_cast<SCEVAddRecExpr>(DstAddRec->getStart())) { in testRDIV()
2334 DstConst = tmpAddRec->getStart(); in testRDIV()
2335 DstCoeff = tmpAddRec->getStepRecurrence(*SE); in testRDIV()
2336 DstLoop = tmpAddRec->getLoop(); in testRDIV()
2338 SrcCoeff = SE->getNegativeSCEV(DstAddRec->getStepRecurrence(*SE)); in testRDIV()
2339 SrcLoop = DstAddRec->getLoop(); in testRDIV()
2357 // Tests the single-subscript MIV pair (Src and Dst) for dependence.
2378 if (const auto *Constant = dyn_cast<SCEVConstant>(Product->getOperand(0))) in getConstantPart()
2384 //===----------------------------------------------------------------------===//
2385 // gcdMIVtest -
2395 // but M and N are just loop-invariant variables.
2399 // It occurs to me that the presence of loop-invariant variables
2406 unsigned BitWidth = SE->getTypeSizeInBits(Src->getType()); in gcdMIVtest()
2416 const SCEV *Coeff = AddRec->getStepRecurrence(*SE); in gcdMIVtest()
2422 APInt ConstCoeff = Constant->getAPInt(); in gcdMIVtest()
2424 Coefficients = AddRec->getStart(); in gcdMIVtest()
2435 const SCEV *Coeff = AddRec->getStepRecurrence(*SE); in gcdMIVtest()
2441 APInt ConstCoeff = Constant->getAPInt(); in gcdMIVtest()
2443 Coefficients = AddRec->getStart(); in gcdMIVtest()
2448 const SCEV *Delta = SE->getMinusSCEV(DstConst, SrcConst); in gcdMIVtest()
2453 for (unsigned Op = 0, Ops = Sum->getNumOperands(); Op < Ops; Op++) { in gcdMIVtest()
2454 const SCEV *Operand = Sum->getOperand(Op); in gcdMIVtest()
2465 APInt ConstOpValue = ConstOp->getAPInt(); in gcdMIVtest()
2475 APInt ConstDelta = cast<SCEVConstant>(Constant)->getAPInt(); in gcdMIVtest()
2488 // For example, given a subscript pair [3*i + 2*j] and [i' + 2*j' - 1], in gcdMIVtest()
2491 // If i = i', we can simplify the subscript to [2*i + 2*j] and [2*j' - 1], in gcdMIVtest()
2492 // which is infeasible, so we can disallow the = direction for the i level. in gcdMIVtest()
2496 // Given A[5*i + 10*j*M + 9*M*N] and A[15*i + 20*j*M - 21*N*M + 5], in gcdMIVtest()
2505 Coefficients = AddRec->getStart(); in gcdMIVtest()
2506 const Loop *CurLoop = AddRec->getLoop(); in gcdMIVtest()
2508 const SCEV *SrcCoeff = AddRec->getStepRecurrence(*SE); in gcdMIVtest()
2509 const SCEV *DstCoeff = SE->getMinusSCEV(SrcCoeff, SrcCoeff); in gcdMIVtest()
2513 const SCEV *Coeff = AddRec->getStepRecurrence(*SE); in gcdMIVtest()
2514 if (CurLoop == AddRec->getLoop()) in gcdMIVtest()
2522 APInt ConstCoeff = Constant->getAPInt(); in gcdMIVtest()
2525 Inner = AddRec->getStart(); in gcdMIVtest()
2530 const SCEV *Coeff = AddRec->getStepRecurrence(*SE); in gcdMIVtest()
2531 if (CurLoop == AddRec->getLoop()) in gcdMIVtest()
2539 APInt ConstCoeff = Constant->getAPInt(); in gcdMIVtest()
2542 Inner = AddRec->getStart(); in gcdMIVtest()
2544 Delta = SE->getMinusSCEV(SrcCoeff, DstCoeff); in gcdMIVtest()
2552 APInt ConstCoeff = Constant->getAPInt(); in gcdMIVtest()
2559 unsigned Level = mapSrcLoop(CurLoop); in gcdMIVtest() local
2560 Result.DV[Level - 1].Direction &= ~Dependence::DVEntry::EQ; in gcdMIVtest()
2572 //===----------------------------------------------------------------------===//
2573 // banerjeeMIVtest -
2575 // (Wolfe, in the race-car book, calls this the Extreme Value Test.)
2585 // LB^<_k = (A^-_k - B_k)^- (U_k - L_k - N_k) + (A_k - B_k)L_k - B_k N_k
2594 // LB^<_k = (A^-_k - B_k)^- (U_k - 0 - 1) + (A_k - B_k)0 - B_k 1
2595 // = (A^-_k - B_k)^- (U_k - 1) - B_k
2602 // for the lower bound, NULL denotes -inf.
2617 const SCEV *Delta = SE->getMinusSCEV(B0, A0); in banerjeeMIVtest()
2632 LLVM_DEBUG(dbgs() << "-inf\t"); in banerjeeMIVtest()
2651 unsigned Old = Result.DV[K - 1].Direction; in banerjeeMIVtest()
2652 Result.DV[K - 1].Direction = Old & Bound[K].DirSet; in banerjeeMIVtest()
2653 Improved |= Old != Result.DV[K - 1].Direction; in banerjeeMIVtest()
2654 if (!Result.DV[K - 1].Direction) { in banerjeeMIVtest()
2685 unsigned DependenceInfo::exploreDirections(unsigned Level, CoefficientInfo *A, in exploreDirections() argument
2691 // of common loop levels. To avoid excessive compile-time, pessimize all the in exploreDirections()
2703 if (Level > CommonLevels) { in exploreDirections()
2714 case Dependence::DVEntry::EQ: in exploreDirections()
2732 if (Loops[Level]) { in exploreDirections()
2733 if (Level > DepthExpanded) { in exploreDirections()
2734 DepthExpanded = Level; in exploreDirections()
2735 // compute bounds for <, =, > at current level in exploreDirections()
2736 findBoundsLT(A, B, Bound, Level); in exploreDirections()
2737 findBoundsGT(A, B, Bound, Level); in exploreDirections()
2738 findBoundsEQ(A, B, Bound, Level); in exploreDirections()
2740 LLVM_DEBUG(dbgs() << "\tBound for level = " << Level << '\n'); in exploreDirections()
2742 if (Bound[Level].Lower[Dependence::DVEntry::LT]) in exploreDirections()
2743 LLVM_DEBUG(dbgs() << *Bound[Level].Lower[Dependence::DVEntry::LT] in exploreDirections()
2746 LLVM_DEBUG(dbgs() << "-inf\t"); in exploreDirections()
2747 if (Bound[Level].Upper[Dependence::DVEntry::LT]) in exploreDirections()
2748 LLVM_DEBUG(dbgs() << *Bound[Level].Upper[Dependence::DVEntry::LT] in exploreDirections()
2753 if (Bound[Level].Lower[Dependence::DVEntry::EQ]) in exploreDirections()
2754 LLVM_DEBUG(dbgs() << *Bound[Level].Lower[Dependence::DVEntry::EQ] in exploreDirections()
2757 LLVM_DEBUG(dbgs() << "-inf\t"); in exploreDirections()
2758 if (Bound[Level].Upper[Dependence::DVEntry::EQ]) in exploreDirections()
2759 LLVM_DEBUG(dbgs() << *Bound[Level].Upper[Dependence::DVEntry::EQ] in exploreDirections()
2764 if (Bound[Level].Lower[Dependence::DVEntry::GT]) in exploreDirections()
2765 LLVM_DEBUG(dbgs() << *Bound[Level].Lower[Dependence::DVEntry::GT] in exploreDirections()
2768 LLVM_DEBUG(dbgs() << "-inf\t"); in exploreDirections()
2769 if (Bound[Level].Upper[Dependence::DVEntry::GT]) in exploreDirections()
2770 LLVM_DEBUG(dbgs() << *Bound[Level].Upper[Dependence::DVEntry::GT] in exploreDirections()
2780 if (testBounds(Dependence::DVEntry::LT, Level, Bound, Delta)) in exploreDirections()
2781 NewDeps += exploreDirections(Level + 1, A, B, Bound, in exploreDirections()
2785 if (testBounds(Dependence::DVEntry::EQ, Level, Bound, Delta)) in exploreDirections()
2786 NewDeps += exploreDirections(Level + 1, A, B, Bound, in exploreDirections()
2790 if (testBounds(Dependence::DVEntry::GT, Level, Bound, Delta)) in exploreDirections()
2791 NewDeps += exploreDirections(Level + 1, A, B, Bound, in exploreDirections()
2794 Bound[Level].Direction = Dependence::DVEntry::ALL; in exploreDirections()
2798 return exploreDirections(Level + 1, A, B, Bound, Loops, DepthExpanded, Delta); in exploreDirections()
2803 bool DependenceInfo::testBounds(unsigned char DirKind, unsigned Level, in testBounds() argument
2805 Bound[Level].Direction = DirKind; in testBounds()
2816 // Computes the upper and lower bounds for level K
2820 // LB^*_k = (A^-_k - B^+_k)(U_k - L_k) + (A_k - B_k)L_k
2821 // UB^*_k = (A^+_k - B^-_k)(U_k - L_k) + (A_k - B_k)L_k
2825 // LB^*_k = (A^-_k - B^+_k)U_k
2826 // UB^*_k = (A^+_k - B^-_k)U_k
2833 Bound[K].Lower[Dependence::DVEntry::ALL] = nullptr; // Default value = -infinity. in findBoundsALL()
2837 SE->getMulExpr(SE->getMinusSCEV(A[K].NegPart, B[K].PosPart), in findBoundsALL()
2840 SE->getMulExpr(SE->getMinusSCEV(A[K].PosPart, B[K].NegPart), in findBoundsALL()
2847 SE->getZero(A[K].Coeff->getType()); in findBoundsALL()
2850 SE->getZero(A[K].Coeff->getType()); in findBoundsALL()
2855 // Computes the upper and lower bounds for level K
2859 // LB^=_k = (A_k - B_k)^- (U_k - L_k) + (A_k - B_k)L_k
2860 // UB^=_k = (A_k - B_k)^+ (U_k - L_k) + (A_k - B_k)L_k
2864 // LB^=_k = (A_k - B_k)^- U_k
2865 // UB^=_k = (A_k - B_k)^+ U_k
2872 Bound[K].Lower[Dependence::DVEntry::EQ] = nullptr; // Default value = -infinity. in findBoundsEQ()
2873 Bound[K].Upper[Dependence::DVEntry::EQ] = nullptr; // Default value = +infinity. in findBoundsEQ()
2875 const SCEV *Delta = SE->getMinusSCEV(A[K].Coeff, B[K].Coeff); in findBoundsEQ()
2877 Bound[K].Lower[Dependence::DVEntry::EQ] = in findBoundsEQ()
2878 SE->getMulExpr(NegativePart, Bound[K].Iterations); in findBoundsEQ()
2880 Bound[K].Upper[Dependence::DVEntry::EQ] = in findBoundsEQ()
2881 SE->getMulExpr(PositivePart, Bound[K].Iterations); in findBoundsEQ()
2886 const SCEV *Delta = SE->getMinusSCEV(A[K].Coeff, B[K].Coeff); in findBoundsEQ()
2888 if (NegativePart->isZero()) in findBoundsEQ()
2889 Bound[K].Lower[Dependence::DVEntry::EQ] = NegativePart; // Zero in findBoundsEQ()
2891 if (PositivePart->isZero()) in findBoundsEQ()
2892 Bound[K].Upper[Dependence::DVEntry::EQ] = PositivePart; // Zero in findBoundsEQ()
2897 // Computes the upper and lower bounds for level K
2901 // LB^<_k = (A^-_k - B_k)^- (U_k - L_k - N_k) + (A_k - B_k)L_k - B_k N_k
2902 // UB^<_k = (A^+_k - B_k)^+ (U_k - L_k - N_k) + (A_k - B_k)L_k - B_k N_k
2906 // LB^<_k = (A^-_k - B_k)^- (U_k - 1) - B_k
2907 // UB^<_k = (A^+_k - B_k)^+ (U_k - 1) - B_k
2912 Bound[K].Lower[Dependence::DVEntry::LT] = nullptr; // Default value = -infinity. in findBoundsLT()
2915 const SCEV *Iter_1 = SE->getMinusSCEV( in findBoundsLT()
2916 Bound[K].Iterations, SE->getOne(Bound[K].Iterations->getType())); in findBoundsLT()
2918 getNegativePart(SE->getMinusSCEV(A[K].NegPart, B[K].Coeff)); in findBoundsLT()
2920 SE->getMinusSCEV(SE->getMulExpr(NegPart, Iter_1), B[K].Coeff); in findBoundsLT()
2922 getPositivePart(SE->getMinusSCEV(A[K].PosPart, B[K].Coeff)); in findBoundsLT()
2924 SE->getMinusSCEV(SE->getMulExpr(PosPart, Iter_1), B[K].Coeff); in findBoundsLT()
2930 getNegativePart(SE->getMinusSCEV(A[K].NegPart, B[K].Coeff)); in findBoundsLT()
2931 if (NegPart->isZero()) in findBoundsLT()
2932 Bound[K].Lower[Dependence::DVEntry::LT] = SE->getNegativeSCEV(B[K].Coeff); in findBoundsLT()
2934 getPositivePart(SE->getMinusSCEV(A[K].PosPart, B[K].Coeff)); in findBoundsLT()
2935 if (PosPart->isZero()) in findBoundsLT()
2936 Bound[K].Upper[Dependence::DVEntry::LT] = SE->getNegativeSCEV(B[K].Coeff); in findBoundsLT()
2941 // Computes the upper and lower bounds for level K
2945 // LB^>_k = (A_k - B^+_k)^- (U_k - L_k - N_k) + (A_k - B_k)L_k + A_k N_k
2946 // UB^>_k = (A_k - B^-_k)^+ (U_k - L_k - N_k) + (A_k - B_k)L_k + A_k N_k
2950 // LB^>_k = (A_k - B^+_k)^- (U_k - 1) + A_k
2951 // UB^>_k = (A_k - B^-_k)^+ (U_k - 1) + A_k
2956 Bound[K].Lower[Dependence::DVEntry::GT] = nullptr; // Default value = -infinity. in findBoundsGT()
2959 const SCEV *Iter_1 = SE->getMinusSCEV( in findBoundsGT()
2960 Bound[K].Iterations, SE->getOne(Bound[K].Iterations->getType())); in findBoundsGT()
2962 getNegativePart(SE->getMinusSCEV(A[K].Coeff, B[K].PosPart)); in findBoundsGT()
2964 SE->getAddExpr(SE->getMulExpr(NegPart, Iter_1), A[K].Coeff); in findBoundsGT()
2966 getPositivePart(SE->getMinusSCEV(A[K].Coeff, B[K].NegPart)); in findBoundsGT()
2968 SE->getAddExpr(SE->getMulExpr(PosPart, Iter_1), A[K].Coeff); in findBoundsGT()
2973 const SCEV *NegPart = getNegativePart(SE->getMinusSCEV(A[K].Coeff, B[K].PosPart)); in findBoundsGT()
2974 if (NegPart->isZero()) in findBoundsGT()
2976 const SCEV *PosPart = getPositivePart(SE->getMinusSCEV(A[K].Coeff, B[K].NegPart)); in findBoundsGT()
2977 if (PosPart->isZero()) in findBoundsGT()
2985 return SE->getSMaxExpr(X, SE->getZero(X->getType())); in getPositivePart()
2989 // X^- = min(X, 0)
2991 return SE->getSMinExpr(X, SE->getZero(X->getType())); in getNegativePart()
3001 const SCEV *Zero = SE->getZero(Subscript->getType()); in collectCoeffInfo()
3010 const Loop *L = AddRec->getLoop(); in collectCoeffInfo()
3012 CI[K].Coeff = AddRec->getStepRecurrence(*SE); in collectCoeffInfo()
3015 CI[K].Iterations = collectUpperBound(L, Subscript->getType()); in collectCoeffInfo()
3016 Subscript = AddRec->getStart(); in collectCoeffInfo()
3042 // at each level. If the lower bound for any level is -inf,
3043 // the result is -inf.
3048 Sum = SE->getAddExpr(Sum, Bound[K].Lower[Bound[K].Direction]); in getLowerBound()
3058 // at each level. If the upper bound at any level is +inf,
3064 Sum = SE->getAddExpr(Sum, Bound[K].Upper[Bound[K].Direction]); in getUpperBound()
3072 //===----------------------------------------------------------------------===//
3085 return SE->getZero(Expr->getType()); in findCoefficient()
3086 if (AddRec->getLoop() == TargetLoop) in findCoefficient()
3087 return AddRec->getStepRecurrence(*SE); in findCoefficient()
3088 return findCoefficient(AddRec->getStart(), TargetLoop); in findCoefficient()
3102 if (AddRec->getLoop() == TargetLoop) in zeroCoefficient()
3103 return AddRec->getStart(); in zeroCoefficient()
3104 return SE->getAddRecExpr(zeroCoefficient(AddRec->getStart(), TargetLoop), in zeroCoefficient()
3105 AddRec->getStepRecurrence(*SE), in zeroCoefficient()
3106 AddRec->getLoop(), in zeroCoefficient()
3107 AddRec->getNoWrapFlags()); in zeroCoefficient()
3121 return SE->getAddRecExpr(Expr, in addToCoefficient()
3125 if (AddRec->getLoop() == TargetLoop) { in addToCoefficient()
3126 const SCEV *Sum = SE->getAddExpr(AddRec->getStepRecurrence(*SE), Value); in addToCoefficient()
3127 if (Sum->isZero()) in addToCoefficient()
3128 return AddRec->getStart(); in addToCoefficient()
3129 return SE->getAddRecExpr(AddRec->getStart(), in addToCoefficient()
3131 AddRec->getLoop(), in addToCoefficient()
3132 AddRec->getNoWrapFlags()); in addToCoefficient()
3134 if (SE->isLoopInvariant(AddRec, TargetLoop)) in addToCoefficient()
3135 return SE->getAddRecExpr(AddRec, Value, TargetLoop, SCEV::FlagAnyWrap); in addToCoefficient()
3136 return SE->getAddRecExpr( in addToCoefficient()
3137 addToCoefficient(AddRec->getStart(), TargetLoop, Value), in addToCoefficient()
3138 AddRec->getStepRecurrence(*SE), AddRec->getLoop(), in addToCoefficient()
3139 AddRec->getNoWrapFlags()); in addToCoefficient()
3183 if (A_K->isZero()) in propagateDistance()
3185 const SCEV *DA_K = SE->getMulExpr(A_K, CurConstraint.getD()); in propagateDistance()
3186 Src = SE->getMinusSCEV(Src, DA_K); in propagateDistance()
3190 Dst = addToCoefficient(Dst, CurLoop, SE->getNegativeSCEV(A_K)); in propagateDistance()
3192 if (!findCoefficient(Dst, CurLoop)->isZero()) in propagateDistance()
3214 if (A->isZero()) { in propagateLine()
3218 APInt Beta = Bconst->getAPInt(); in propagateLine()
3219 APInt Charlie = Cconst->getAPInt(); in propagateLine()
3223 // Src = SE->getAddExpr(Src, SE->getMulExpr(AP_K, SE->getConstant(CdivB))); in propagateLine()
3224 Src = SE->getMinusSCEV(Src, SE->getMulExpr(AP_K, SE->getConstant(CdivB))); in propagateLine()
3226 if (!findCoefficient(Src, CurLoop)->isZero()) in propagateLine()
3229 else if (B->isZero()) { in propagateLine()
3233 APInt Alpha = Aconst->getAPInt(); in propagateLine()
3234 APInt Charlie = Cconst->getAPInt(); in propagateLine()
3238 Src = SE->getAddExpr(Src, SE->getMulExpr(A_K, SE->getConstant(CdivA))); in propagateLine()
3240 if (!findCoefficient(Dst, CurLoop)->isZero()) in propagateLine()
3247 APInt Alpha = Aconst->getAPInt(); in propagateLine()
3248 APInt Charlie = Cconst->getAPInt(); in propagateLine()
3252 Src = SE->getAddExpr(Src, SE->getMulExpr(A_K, SE->getConstant(CdivA))); in propagateLine()
3255 if (!findCoefficient(Dst, CurLoop)->isZero()) in propagateLine()
3261 Src = SE->getMulExpr(Src, A); in propagateLine()
3262 Dst = SE->getMulExpr(Dst, A); in propagateLine()
3263 Src = SE->getAddExpr(Src, SE->getMulExpr(A_K, C)); in propagateLine()
3265 Dst = addToCoefficient(Dst, CurLoop, SE->getMulExpr(A_K, B)); in propagateLine()
3266 if (!findCoefficient(Dst, CurLoop)->isZero()) in propagateLine()
3283 const SCEV *XA_K = SE->getMulExpr(A_K, CurConstraint.getX()); in propagatePoint()
3284 const SCEV *YAP_K = SE->getMulExpr(AP_K, CurConstraint.getY()); in propagatePoint()
3286 Src = SE->getAddExpr(Src, SE->getMinusSCEV(XA_K, YAP_K)); in propagatePoint()
3297 void DependenceInfo::updateDirection(Dependence::DVEntry &Level, in updateDirection() argument
3305 Level.Scalar = false; in updateDirection()
3306 Level.Distance = CurConstraint.getD(); in updateDirection()
3308 if (!SE->isKnownNonZero(Level.Distance)) // if may be zero in updateDirection()
3309 NewDirection = Dependence::DVEntry::EQ; in updateDirection()
3310 if (!SE->isKnownNonPositive(Level.Distance)) // if may be positive in updateDirection()
3312 if (!SE->isKnownNonNegative(Level.Distance)) // if may be negative in updateDirection()
3314 Level.Direction &= NewDirection; in updateDirection()
3317 Level.Scalar = false; in updateDirection()
3318 Level.Distance = nullptr; in updateDirection()
3322 Level.Scalar = false; in updateDirection()
3323 Level.Distance = nullptr; in updateDirection()
3329 NewDirection |= Dependence::DVEntry::EQ; in updateDirection()
3340 Level.Direction &= NewDirection; in updateDirection()
3349 /// for each loop level.
3356 Loop *SrcLoop = LI->getLoopFor(Src->getParent()); in tryDelinearize()
3357 Loop *DstLoop = LI->getLoopFor(Dst->getParent()); in tryDelinearize()
3358 const SCEV *SrcAccessFn = SE->getSCEVAtScope(SrcPtr, SrcLoop); in tryDelinearize()
3359 const SCEV *DstAccessFn = SE->getSCEVAtScope(DstPtr, DstLoop); in tryDelinearize()
3361 dyn_cast<SCEVUnknown>(SE->getPointerBase(SrcAccessFn)); in tryDelinearize()
3363 dyn_cast<SCEVUnknown>(SE->getPointerBase(DstAccessFn)); in tryDelinearize()
3386 // The delinearization transforms a single-subscript MIV dependence test into in tryDelinearize()
3387 // a multi-subscript SIV dependence test that is easier to compute. So we in tryDelinearize()
3401 /// arrays accessed are fixed-size arrays. Return true if delinearization was
3409 dyn_cast<SCEVUnknown>(SE->getPointerBase(SrcAccessFn)); in tryDelinearizeFixedSize()
3411 dyn_cast<SCEVUnknown>(SE->getPointerBase(DstAccessFn)); in tryDelinearizeFixedSize()
3424 // Check that the two size arrays are non-empty and equal in length and in tryDelinearizeFixedSize()
3443 // impossible to verify this at compile-time. As such we can only delinearize in tryDelinearizeFixedSize()
3455 if (auto *SType = dyn_cast<IntegerType>(S->getType())) { in tryDelinearizeFixedSize()
3456 const SCEV *Range = SE->getConstant( in tryDelinearizeFixedSize()
3457 ConstantInt::get(SType, DimensionSizes[I - 1], false)); in tryDelinearizeFixedSize()
3473 dbgs() << "Delinearized subscripts of fixed-size array\n" in tryDelinearizeFixedSize()
3488 dyn_cast<SCEVUnknown>(SE->getPointerBase(SrcAccessFn)); in tryDelinearizeParametricSize()
3490 dyn_cast<SCEVUnknown>(SE->getPointerBase(DstAccessFn)); in tryDelinearizeParametricSize()
3494 const SCEV *ElementSize = SE->getElementSize(Src); in tryDelinearizeParametricSize()
3495 if (ElementSize != SE->getElementSize(Dst)) in tryDelinearizeParametricSize()
3498 const SCEV *SrcSCEV = SE->getMinusSCEV(SrcAccessFn, SrcBase); in tryDelinearizeParametricSize()
3499 const SCEV *DstSCEV = SE->getMinusSCEV(DstAccessFn, DstBase); in tryDelinearizeParametricSize()
3503 if (!SrcAR || !DstAR || !SrcAR->isAffine() || !DstAR->isAffine()) in tryDelinearizeParametricSize()
3526 // Statically check that the array bounds are in-range. The first subscript we in tryDelinearizeParametricSize()
3537 if (!isKnownLessThan(SrcSubscripts[I], Sizes[I - 1])) in tryDelinearizeParametricSize()
3543 if (!isKnownLessThan(DstSubscripts[I], Sizes[I - 1])) in tryDelinearizeParametricSize()
3550 //===----------------------------------------------------------------------===//
3578 // depends -
3595 if (!(Src->mayReadOrWriteMemory() && Dst->mayReadOrWriteMemory())) in depends()
3610 switch (underlyingObjectsAlias(AA, F->getDataLayout(), in depends()
3636 const SCEV *SrcSCEV = SE->getSCEV(SrcPtr); in depends()
3637 const SCEV *DstSCEV = SE->getSCEV(DstPtr); in depends()
3640 if (SE->getPointerBase(SrcSCEV) != SE->getPointerBase(DstSCEV)) { in depends()
3666 classifyPair(Pair[P].Src, LI->getLoopFor(Src->getParent()), in depends()
3667 Pair[P].Dst, LI->getLoopFor(Dst->getParent()), in depends()
3682 // Partition subscripts into separable and minimally-coupled groups in depends()
3744 LI->getLoopFor(Src->getParent()), in depends()
3747 LI->getLoopFor(Dst->getParent()), in depends()
3800 unsigned Level; in depends() local
3802 if (testSIV(Pair[SI].Src, Pair[SI].Dst, Level, Result, NewConstraint, in depends()
3851 unsigned Level; in depends() local
3854 if (testSIV(Pair[SJ].Src, Pair[SJ].Dst, Level, Result, NewConstraint, in depends()
3857 ConstrainedLevels.set(Level); in depends()
3858 if (intersectConstraints(&Constraints[Level], &NewConstraint)) { in depends()
3859 if (Constraints[Level].isEmpty()) { in depends()
3880 classifyPair(Pair[SJ].Src, LI->getLoopFor(Src->getParent()), in depends()
3881 Pair[SJ].Dst, LI->getLoopFor(Dst->getParent()), in depends()
3934 updateDirection(Result.DV[SJ - 1], Constraints[SJ]); in depends()
3935 if (Result.DV[SJ - 1].Direction == Dependence::DVEntry::NONE) in depends()
3947 Result.DV[II - 1].Scalar = false; in depends()
3952 // loop-independent dependence is possible. in depends()
3954 if (!(Result.getDirection(II) & Dependence::DVEntry::EQ)) { in depends()
3962 // loop-independent dependence possible, then no dependence exists. in depends()
3965 if (Result.getDirection(II) != Dependence::DVEntry::EQ) { in depends()
3977 //===----------------------------------------------------------------------===//
3978 // getSplitIteration -
3979 // Rather than spend rarely-used space recording the splitting iteration
3980 // during the Weak-Crossing SIV test, we re-compute it on demand.
3981 // The re-computation is basically a repeat of the entire dependence test,
4007 // ... = A[11 - i]
4009 // There's a loop-carried flow dependence from the store to the load,
4010 // found by the weak-crossing SIV test. The dependence will have a flag,
4017 // ... = A[11 - i]
4020 // ... = A[11 - i]
4030 assert(Src->mayReadFromMemory() || Src->mayWriteToMemory()); in getSplitIteration()
4031 assert(Dst->mayReadFromMemory() || Dst->mayWriteToMemory()); in getSplitIteration()
4037 AA, F->getDataLayout(), MemoryLocation::get(Dst), in getSplitIteration()
4047 const SCEV *SrcSCEV = SE->getSCEV(SrcPtr); in getSplitIteration()
4048 const SCEV *DstSCEV = SE->getSCEV(DstPtr); in getSplitIteration()
4065 classifyPair(Pair[P].Src, LI->getLoopFor(Src->getParent()), in getSplitIteration()
4066 Pair[P].Dst, LI->getLoopFor(Dst->getParent()), in getSplitIteration()
4075 // partition subscripts into separable and minimally-coupled groups in getSplitIteration()
4080 LI->getLoopFor(Src->getParent()), in getSplitIteration()
4083 LI->getLoopFor(Dst->getParent()), in getSplitIteration()
4119 unsigned Level; in getSplitIteration() local
4121 (void) testSIV(Pair[SI].Src, Pair[SI].Dst, Level, in getSplitIteration()
4123 if (Level == SplitLevel) { in getSplitIteration()
4158 unsigned Level; in getSplitIteration() local
4160 (void) testSIV(Pair[SJ].Src, Pair[SJ].Dst, Level, in getSplitIteration()
4162 if (Level == SplitLevel && SplitIter) in getSplitIteration()
4164 ConstrainedLevels.set(Level); in getSplitIteration()
4165 if (intersectConstraints(&Constraints[Level], &NewConstraint)) in getSplitIteration()
4176 classifyPair(Pair[SJ].Src, LI->getLoopFor(Src->getParent()), in getSplitIteration()
4177 Pair[SJ].Dst, LI->getLoopFor(Dst->getParent()), in getSplitIteration()