60 #include "llvm/Config/llvm-config.h" 71 #define DEBUG_TYPE "da" 76 STATISTIC(TotalArrayPairs,
"Array pairs tested");
77 STATISTIC(SeparableSubscriptPairs,
"Separable subscript pairs");
78 STATISTIC(CoupledSubscriptPairs,
"Coupled subscript pairs");
79 STATISTIC(NonlinearSubscriptPairs,
"Nonlinear subscript pairs");
80 STATISTIC(ZIVapplications,
"ZIV applications");
81 STATISTIC(ZIVindependence,
"ZIV independence");
82 STATISTIC(StrongSIVapplications,
"Strong SIV applications");
83 STATISTIC(StrongSIVsuccesses,
"Strong SIV successes");
84 STATISTIC(StrongSIVindependence,
"Strong SIV independence");
85 STATISTIC(WeakCrossingSIVapplications,
"Weak-Crossing SIV applications");
86 STATISTIC(WeakCrossingSIVsuccesses,
"Weak-Crossing SIV successes");
87 STATISTIC(WeakCrossingSIVindependence,
"Weak-Crossing SIV independence");
88 STATISTIC(ExactSIVapplications,
"Exact SIV applications");
89 STATISTIC(ExactSIVsuccesses,
"Exact SIV successes");
90 STATISTIC(ExactSIVindependence,
"Exact SIV independence");
91 STATISTIC(WeakZeroSIVapplications,
"Weak-Zero SIV applications");
92 STATISTIC(WeakZeroSIVsuccesses,
"Weak-Zero SIV successes");
93 STATISTIC(WeakZeroSIVindependence,
"Weak-Zero SIV independence");
94 STATISTIC(ExactRDIVapplications,
"Exact RDIV applications");
95 STATISTIC(ExactRDIVindependence,
"Exact RDIV independence");
96 STATISTIC(SymbolicRDIVapplications,
"Symbolic RDIV applications");
97 STATISTIC(SymbolicRDIVindependence,
"Symbolic RDIV independence");
98 STATISTIC(DeltaApplications,
"Delta applications");
99 STATISTIC(DeltaSuccesses,
"Delta successes");
100 STATISTIC(DeltaIndependence,
"Delta independence");
101 STATISTIC(DeltaPropagations,
"Delta propagations");
102 STATISTIC(GCDapplications,
"GCD applications");
103 STATISTIC(GCDsuccesses,
"GCD successes");
104 STATISTIC(GCDindependence,
"GCD independence");
105 STATISTIC(BanerjeeApplications,
"Banerjee applications");
106 STATISTIC(BanerjeeIndependence,
"Banerjee independence");
107 STATISTIC(BanerjeeSuccesses,
"Banerjee successes");
111 cl::desc(
"Try to delinearize array references."));
116 "Disable checks that try to statically verify validity of " 117 "delinearized subscripts. Enabling this option may result in incorrect " 118 "dependence vectors for languages that allow the subscript of one " 119 "dimension to underflow or overflow into another dimension."));
135 "Dependence Analysis",
true,
true)
142 char DependenceAnalysisWrapperPass::
ID = 0;
145 return new DependenceAnalysisWrapperPass();
149 auto &AA = getAnalysis<AAResultsWrapperPass>().getAAResults();
150 auto &SE = getAnalysis<ScalarEvolutionWrapperPass>().getSE();
151 auto &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
176 if (isa<StoreInst>(*SrcI) || isa<LoadInst>(*SrcI)) {
178 DstI != DstE; ++DstI) {
179 if (isa<StoreInst>(*DstI) || isa<LoadInst>(*DstI)) {
180 OS <<
"da analyze - ";
181 if (
auto D = DA->
depends(&*SrcI, &*DstI,
true)) {
184 if (
D->isSplitable(
Level)) {
185 OS <<
"da analyze - split level = " <<
Level;
206 OS <<
"'Dependence Analysis' for function '" << F.
getName() <<
"':\n";
216 return Src->mayReadFromMemory() && Dst->mayReadFromMemory();
222 return Src->mayWriteToMemory() && Dst->mayWriteToMemory();
228 return Src->mayWriteToMemory() && Dst->mayReadFromMemory();
234 return Src->mayReadFromMemory() && Dst->mayWriteToMemory();
251 bool PossiblyLoopIndependent,
252 unsigned CommonLevels)
253 :
Dependence(Source, Destination), Levels(CommonLevels),
254 LoopIndependent(PossiblyLoopIndependent) {
257 DV = std::make_unique<DVEntry[]>(CommonLevels);
264 assert(0 < Level && Level <= Levels &&
"Level out of range");
265 return DV[Level - 1].Direction;
271 assert(0 < Level && Level <= Levels &&
"Level out of range");
272 return DV[Level - 1].Distance;
280 assert(0 < Level && Level <= Levels &&
"Level out of range");
281 return DV[Level - 1].Scalar;
288 assert(0 < Level && Level <= Levels &&
"Level out of range");
289 return DV[Level - 1].PeelFirst;
296 assert(0 < Level && Level <= Levels &&
"Level out of range");
297 return DV[Level - 1].PeelLast;
303 assert(0 < Level && Level <= Levels &&
"Level out of range");
304 return DV[Level - 1].Splitable;
313 const SCEV *DependenceInfo::Constraint::getX()
const {
314 assert(
Kind == Point &&
"Kind should be Point");
321 const SCEV *DependenceInfo::Constraint::getY()
const {
322 assert(
Kind == Point &&
"Kind should be Point");
329 const SCEV *DependenceInfo::Constraint::getA()
const {
331 "Kind should be Line (or Distance)");
338 const SCEV *DependenceInfo::Constraint::getB()
const {
340 "Kind should be Line (or Distance)");
347 const SCEV *DependenceInfo::Constraint::getC()
const {
349 "Kind should be Line (or Distance)");
356 const SCEV *DependenceInfo::Constraint::getD()
const {
357 assert(
Kind == Distance &&
"Kind should be Distance");
358 return SE->getNegativeSCEV(
C);
363 const Loop *DependenceInfo::Constraint::getAssociatedLoop()
const {
365 "Kind should be Distance, Line, or Point");
366 return AssociatedLoop;
369 void DependenceInfo::Constraint::setPoint(
const SCEV *
X,
const SCEV *
Y,
370 const Loop *CurLoop) {
374 AssociatedLoop = CurLoop;
377 void DependenceInfo::Constraint::setLine(
const SCEV *AA,
const SCEV *BB,
378 const SCEV *CC,
const Loop *CurLoop) {
383 AssociatedLoop = CurLoop;
386 void DependenceInfo::Constraint::setDistance(
const SCEV *
D,
387 const Loop *CurLoop) {
390 B = SE->getNegativeSCEV(A);
391 C = SE->getNegativeSCEV(D);
392 AssociatedLoop = CurLoop;
395 void DependenceInfo::Constraint::setEmpty() {
Kind =
Empty; }
402 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 410 OS <<
" Point is <" << *getX() <<
", " << *getY() <<
">\n";
411 else if (isDistance())
412 OS <<
" Distance is " << *getD() <<
413 " (" << *getA() <<
"*X + " << *getB() <<
"*Y = " << *getC() <<
")\n";
415 OS <<
" Line is " << *getA() <<
"*X + " <<
416 *getB() <<
"*Y = " << *getC() <<
"\n";
430 bool DependenceInfo::intersectConstraints(Constraint *X,
const Constraint *Y) {
435 assert(!Y->isPoint() &&
"Y must not be a Point");
449 if (X->isDistance() && Y->isDistance()) {
460 if (isa<SCEVConstant>(Y->getD())) {
473 assert(!(X->isPoint() && Y->isPoint()) &&
474 "We shouldn't ever see X->isPoint() && Y->isPoint()");
476 if (X->isLine() && Y->isLine()) {
478 const SCEV *Prod1 = SE->getMulExpr(X->getA(), Y->getB());
479 const SCEV *Prod2 = SE->getMulExpr(X->getB(), Y->getA());
483 Prod1 = SE->getMulExpr(X->getC(), Y->getB());
484 Prod2 = SE->getMulExpr(X->getB(), Y->getC());
497 const SCEV *C1B2 = SE->getMulExpr(X->getC(), Y->getB());
498 const SCEV *C1A2 = SE->getMulExpr(X->getC(), Y->getA());
499 const SCEV *C2B1 = SE->getMulExpr(Y->getC(), X->getB());
500 const SCEV *C2A1 = SE->getMulExpr(Y->getC(), X->getA());
501 const SCEV *A1B2 = SE->getMulExpr(X->getA(), Y->getB());
502 const SCEV *A2B1 = SE->getMulExpr(Y->getA(), X->getB());
511 if (!C1B2_C2B1 || !C1A2_C2A1 ||
512 !A1B2_A2B1 || !A2B1_A1B2)
514 APInt Xtop = C1B2_C2B1->getAPInt();
515 APInt Xbot = A1B2_A2B1->getAPInt();
517 APInt Ybot = A2B1_A1B2->getAPInt();
528 if (Xr != 0 || Yr != 0) {
534 if (Xq.
slt(0) || Yq.
slt(0)) {
540 collectConstantUpperBound(X->getAssociatedLoop(), Prod1->
getType())) {
541 const APInt &UpperBound = CUB->getAPInt();
543 if (Xq.
sgt(UpperBound) || Yq.
sgt(UpperBound)) {
549 X->setPoint(SE->getConstant(Xq),
551 X->getAssociatedLoop());
559 assert(!(X->isLine() && Y->isPoint()) &&
"This case should never occur");
561 if (X->isPoint() && Y->isLine()) {
563 const SCEV *A1X1 = SE->getMulExpr(Y->getA(), X->getX());
564 const SCEV *B1Y1 = SE->getMulExpr(Y->getB(), X->getY());
565 const SCEV *Sum = SE->getAddExpr(A1X1, B1Y1);
586 bool Splitable =
false;
602 for (
unsigned II = 1; II <= Levels; ++II) {
678 if (
const LoadInst *LI = dyn_cast<LoadInst>(I))
679 return LI->isUnordered();
680 else if (
const StoreInst *
SI = dyn_cast<StoreInst>(I))
681 return SI->isUnordered();
736 void DependenceInfo::establishNestingLevels(
const Instruction *Src,
740 unsigned SrcLevel = LI->getLoopDepth(SrcBlock);
741 unsigned DstLevel = LI->getLoopDepth(DstBlock);
742 const Loop *SrcLoop = LI->getLoopFor(SrcBlock);
743 const Loop *DstLoop = LI->getLoopFor(DstBlock);
744 SrcLevels = SrcLevel;
745 MaxLevels = SrcLevel + DstLevel;
746 while (SrcLevel > DstLevel) {
750 while (DstLevel > SrcLevel) {
754 while (SrcLoop != DstLoop) {
759 CommonLevels = SrcLevel;
760 MaxLevels -= CommonLevels;
766 unsigned DependenceInfo::mapSrcLoop(
const Loop *SrcLoop)
const {
773 unsigned DependenceInfo::mapDstLoop(
const Loop *DstLoop)
const {
775 if (D > CommonLevels)
776 return D - CommonLevels + SrcLevels;
783 bool DependenceInfo::isLoopInvariant(
const SCEV *Expression,
784 const Loop *LoopNest)
const {
787 return SE->isLoopInvariant(Expression, LoopNest) &&
795 void DependenceInfo::collectCommonLoops(
const SCEV *Expression,
796 const Loop *LoopNest,
800 if (Level <= CommonLevels && !SE->isLoopInvariant(Expression, LoopNest))
808 unsigned widestWidthSeen = 0;
813 for (Subscript *Pair : Pairs) {
814 const SCEV *Src = Pair->Src;
815 const SCEV *Dst = Pair->Dst;
818 if (SrcTy ==
nullptr || DstTy ==
nullptr) {
819 assert(SrcTy == DstTy &&
"This function only unify integer types and " 820 "expect Src and Dst share the same type " 828 if (DstTy->getBitWidth() > widestWidthSeen) {
829 widestWidthSeen = DstTy->getBitWidth();
835 assert(widestWidthSeen > 0);
838 for (Subscript *Pair : Pairs) {
839 const SCEV *Src = Pair->Src;
840 const SCEV *Dst = Pair->Dst;
843 if (SrcTy ==
nullptr || DstTy ==
nullptr) {
844 assert(SrcTy == DstTy &&
"This function only unify integer types and " 845 "expect Src and Dst share the same type " 851 Pair->Src = SE->getSignExtendExpr(Src, widestType);
852 if (DstTy->getBitWidth() < widestWidthSeen) {
854 Pair->Dst = SE->getSignExtendExpr(Dst, widestType);
863 void DependenceInfo::removeMatchingExtensions(Subscript *Pair) {
864 const SCEV *Src = Pair->Src;
865 const SCEV *Dst = Pair->Dst;
866 if ((isa<SCEVZeroExtendExpr>(Src) && isa<SCEVZeroExtendExpr>(Dst)) ||
867 (isa<SCEVSignExtendExpr>(Src) && isa<SCEVSignExtendExpr>(Dst))) {
871 const SCEV *DstCastOp = DstCast->getOperand();
872 if (SrcCastOp->getType() == DstCastOp->
getType()) {
873 Pair->Src = SrcCastOp;
874 Pair->Dst = DstCastOp;
882 bool DependenceInfo::checkSrcSubscript(
const SCEV *Src,
const Loop *LoopNest,
886 return isLoopInvariant(Src, LoopNest);
889 const SCEV *UB = SE->getBackedgeTakenCount(AddRec->
getLoop());
890 if (!isa<SCEVCouldNotCompute>(UB)) {
891 if (SE->getTypeSizeInBits(Start->
getType()) <
892 SE->getTypeSizeInBits(UB->
getType())) {
897 if (!isLoopInvariant(Step, LoopNest))
900 return checkSrcSubscript(Start, LoopNest, Loops);
907 bool DependenceInfo::checkDstSubscript(
const SCEV *Dst,
const Loop *LoopNest,
911 return isLoopInvariant(Dst, LoopNest);
914 const SCEV *UB = SE->getBackedgeTakenCount(AddRec->
getLoop());
915 if (!isa<SCEVCouldNotCompute>(UB)) {
916 if (SE->getTypeSizeInBits(Start->
getType()) <
917 SE->getTypeSizeInBits(UB->
getType())) {
922 if (!isLoopInvariant(Step, LoopNest))
925 return checkDstSubscript(Start, LoopNest, Loops);
932 DependenceInfo::Subscript::ClassificationKind
933 DependenceInfo::classifyPair(
const SCEV *Src,
const Loop *SrcLoopNest,
934 const SCEV *Dst,
const Loop *DstLoopNest,
938 if (!checkSrcSubscript(Src, SrcLoopNest, SrcLoops))
939 return Subscript::NonLinear;
940 if (!checkDstSubscript(Dst, DstLoopNest, DstLoops))
941 return Subscript::NonLinear;
944 unsigned N = Loops.
count();
946 return Subscript::ZIV;
948 return Subscript::SIV;
949 if (N == 2 && (SrcLoops.
count() == 0 ||
950 DstLoops.
count() == 0 ||
951 (SrcLoops.
count() == 1 && DstLoops.
count() == 1)))
952 return Subscript::RDIV;
953 return Subscript::MIV;
968 const SCEV *Y)
const {
971 if ((isa<SCEVSignExtendExpr>(X) &&
972 isa<SCEVSignExtendExpr>(Y)) ||
973 (isa<SCEVZeroExtendExpr>(X) &&
974 isa<SCEVZeroExtendExpr>(Y))) {
978 const SCEV *Yop = CY->getOperand();
979 if (Xop->getType() == Yop->
getType()) {
985 if (SE->isKnownPredicate(Pred, X, Y))
992 const SCEV *Delta = SE->getMinusSCEV(X, Y);
997 return SE->isKnownNonZero(Delta);
999 return SE->isKnownNonNegative(Delta);
1001 return SE->isKnownNonPositive(Delta);
1003 return SE->isKnownPositive(Delta);
1005 return SE->isKnownNegative(Delta);
1014 bool DependenceInfo::isKnownLessThan(
const SCEV *S,
const SCEV *
Size)
const {
1018 if (!SType || !SizeType)
1021 (SType->getBitWidth() >= SizeType->getBitWidth()) ? SType : SizeType;
1022 S = SE->getTruncateOrZeroExtend(S, MaxType);
1023 Size = SE->getTruncateOrZeroExtend(Size, MaxType);
1026 const SCEV *Bound = SE->getMinusSCEV(S, Size);
1027 if (
const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(Bound)) {
1028 if (AddRec->isAffine()) {
1029 const SCEV *BECount = SE->getBackedgeTakenCount(AddRec->getLoop());
1030 if (!isa<SCEVCouldNotCompute>(BECount)) {
1031 const SCEV *Limit = AddRec->evaluateAtIteration(BECount, *SE);
1032 if (SE->isKnownNegative(Limit))
1039 const SCEV *LimitedBound =
1040 SE->getMinusSCEV(S, SE->getSMaxExpr(Size, SE->getOne(Size->
getType())));
1041 return SE->isKnownNegative(LimitedBound);
1044 bool DependenceInfo::isKnownNonNegative(
const SCEV *S,
const Value *Ptr)
const {
1045 bool Inbounds =
false;
1046 if (
auto *SrcGEP = dyn_cast<GetElementPtrInst>(Ptr))
1047 Inbounds = SrcGEP->isInBounds();
1049 if (
const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(S)) {
1050 if (AddRec->isAffine()) {
1053 if (SE->isKnownNonNegative(AddRec->getStart()) &&
1054 SE->isKnownNonNegative(AddRec->getOperand(1)))
1060 return SE->isKnownNonNegative(S);
1070 const SCEV *DependenceInfo::collectUpperBound(
const Loop *L,
Type *
T)
const {
1071 if (SE->hasLoopInvariantBackedgeTakenCount(L)) {
1072 const SCEV *UB = SE->getBackedgeTakenCount(L);
1073 return SE->getTruncateOrZeroExtend(UB, T);
1081 const SCEVConstant *DependenceInfo::collectConstantUpperBound(
const Loop *L,
1083 if (
const SCEV *UB = collectUpperBound(L, T))
1099 bool DependenceInfo::testZIV(
const SCEV *Src,
const SCEV *Dst,
1114 Result.Consistent =
false;
1146 bool DependenceInfo::strongSIVtest(
const SCEV *Coeff,
const SCEV *SrcConst,
1147 const SCEV *DstConst,
const Loop *CurLoop,
1149 Constraint &NewConstraint)
const {
1157 ++StrongSIVapplications;
1158 assert(0 < Level && Level <= CommonLevels &&
"level out of range");
1161 const SCEV *Delta = SE->getMinusSCEV(SrcConst, DstConst);
1166 if (
const SCEV *UpperBound = collectUpperBound(CurLoop, Delta->
getType())) {
1169 const SCEV *AbsDelta =
1170 SE->isKnownNonNegative(Delta) ? Delta : SE->getNegativeSCEV(Delta);
1171 const SCEV *AbsCoeff =
1172 SE->isKnownNonNegative(Coeff) ? Coeff : SE->getNegativeSCEV(Coeff);
1173 const SCEV *Product = SE->getMulExpr(UpperBound, AbsCoeff);
1176 ++StrongSIVindependence;
1177 ++StrongSIVsuccesses;
1183 if (isa<SCEVConstant>(Delta) && isa<SCEVConstant>(Coeff)) {
1184 APInt ConstDelta = cast<SCEVConstant>(Delta)->getAPInt();
1185 APInt ConstCoeff = cast<SCEVConstant>(Coeff)->getAPInt();
1186 APInt Distance = ConstDelta;
1187 APInt Remainder = ConstDelta;
1192 if (Remainder != 0) {
1194 ++StrongSIVindependence;
1195 ++StrongSIVsuccesses;
1198 Result.DV[
Level].Distance = SE->getConstant(Distance);
1199 NewConstraint.setDistance(SE->getConstant(Distance), CurLoop);
1200 if (Distance.
sgt(0))
1202 else if (Distance.
slt(0))
1206 ++StrongSIVsuccesses;
1208 else if (Delta->
isZero()) {
1210 Result.DV[
Level].Distance = Delta;
1211 NewConstraint.setDistance(Delta, CurLoop);
1213 ++StrongSIVsuccesses;
1216 if (Coeff->
isOne()) {
1218 Result.DV[
Level].Distance = Delta;
1219 NewConstraint.setDistance(Delta, CurLoop);
1222 Result.Consistent =
false;
1223 NewConstraint.setLine(Coeff,
1224 SE->getNegativeSCEV(Coeff),
1225 SE->getNegativeSCEV(Delta), CurLoop);
1229 bool DeltaMaybeZero = !SE->isKnownNonZero(Delta);
1230 bool DeltaMaybePositive = !SE->isKnownNonPositive(Delta);
1231 bool DeltaMaybeNegative = !SE->isKnownNonNegative(Delta);
1232 bool CoeffMaybePositive = !SE->isKnownNonPositive(Coeff);
1233 bool CoeffMaybeNegative = !SE->isKnownNonNegative(Coeff);
1238 if ((DeltaMaybePositive && CoeffMaybePositive) ||
1239 (DeltaMaybeNegative && CoeffMaybeNegative))
1243 if ((DeltaMaybeNegative && CoeffMaybePositive) ||
1244 (DeltaMaybePositive && CoeffMaybeNegative))
1246 if (NewDirection < Result.DV[Level].Direction)
1247 ++StrongSIVsuccesses;
1248 Result.DV[
Level].Direction &= NewDirection;
1282 bool DependenceInfo::weakCrossingSIVtest(
1283 const SCEV *Coeff,
const SCEV *SrcConst,
const SCEV *DstConst,
1285 Constraint &NewConstraint,
const SCEV *&SplitIter)
const {
1290 ++WeakCrossingSIVapplications;
1291 assert(0 < Level && Level <= CommonLevels &&
"Level out of range");
1293 Result.Consistent =
false;
1294 const SCEV *Delta = SE->getMinusSCEV(DstConst, SrcConst);
1296 NewConstraint.setLine(Coeff, Coeff, Delta, CurLoop);
1300 ++WeakCrossingSIVsuccesses;
1301 if (!Result.DV[Level].Direction) {
1302 ++WeakCrossingSIVindependence;
1305 Result.DV[
Level].Distance = Delta;
1312 Result.DV[
Level].Splitable =
true;
1313 if (SE->isKnownNegative(ConstCoeff)) {
1316 "dynamic cast of negative of ConstCoeff should yield constant");
1317 Delta = SE->getNegativeSCEV(Delta);
1319 assert(SE->isKnownPositive(ConstCoeff) &&
"ConstCoeff should be positive");
1322 SplitIter = SE->getUDivExpr(
1323 SE->getSMaxExpr(SE->getZero(Delta->
getType()), Delta),
1324 SE->getMulExpr(SE->getConstant(Delta->
getType(), 2), ConstCoeff));
1335 if (SE->isKnownNegative(Delta)) {
1337 ++WeakCrossingSIVindependence;
1338 ++WeakCrossingSIVsuccesses;
1344 if (
const SCEV *UpperBound = collectUpperBound(CurLoop, Delta->
getType())) {
1346 const SCEV *ConstantTwo = SE->getConstant(UpperBound->getType(), 2);
1347 const SCEV *ML = SE->getMulExpr(SE->getMulExpr(ConstCoeff, UpperBound),
1352 ++WeakCrossingSIVindependence;
1353 ++WeakCrossingSIVsuccesses;
1360 ++WeakCrossingSIVsuccesses;
1361 if (!Result.DV[Level].Direction) {
1362 ++WeakCrossingSIVindependence;
1365 Result.DV[
Level].Splitable =
false;
1366 Result.DV[
Level].Distance = SE->getZero(Delta->
getType());
1374 APInt Distance = APDelta;
1375 APInt Remainder = APDelta;
1378 if (Remainder != 0) {
1380 ++WeakCrossingSIVindependence;
1381 ++WeakCrossingSIVsuccesses;
1388 Remainder = Distance.
srem(Two);
1390 if (Remainder != 0) {
1393 ++WeakCrossingSIVsuccesses;
1411 APInt A0(Bits, 1,
true), A1(Bits, 0,
true);
1412 APInt B0(Bits, 0,
true),
B1(Bits, 1,
true);
1419 APInt A2 = A0 - Q*A1; A0 = A1; A1 = A2;
1420 APInt B2 = B0 - Q*B1; B0 = B1; B1 = B2;
1426 X = AM.
slt(0) ? -A1 : A1;
1427 Y = BM.
slt(0) ? B1 : -B1;
1445 if ((A.
sgt(0) && B.
sgt(0)) ||
1458 if ((A.
sgt(0) && B.
sgt(0)) ||
1468 return A.
sgt(B) ? A :
B;
1474 return A.
slt(B) ? A :
B;
1493 bool DependenceInfo::exactSIVtest(
const SCEV *SrcCoeff,
const SCEV *DstCoeff,
1494 const SCEV *SrcConst,
const SCEV *DstConst,
1495 const Loop *CurLoop,
unsigned Level,
1497 Constraint &NewConstraint)
const {
1499 LLVM_DEBUG(
dbgs() <<
"\t SrcCoeff = " << *SrcCoeff <<
" = AM\n");
1500 LLVM_DEBUG(
dbgs() <<
"\t DstCoeff = " << *DstCoeff <<
" = BM\n");
1503 ++ExactSIVapplications;
1504 assert(0 < Level && Level <= CommonLevels &&
"Level out of range");
1506 Result.Consistent =
false;
1507 const SCEV *Delta = SE->getMinusSCEV(DstConst, SrcConst);
1509 NewConstraint.setLine(SrcCoeff, SE->getNegativeSCEV(DstCoeff),
1514 if (!ConstDelta || !ConstSrcCoeff || !ConstDstCoeff)
1519 APInt AM = ConstSrcCoeff->getAPInt();
1520 APInt BM = ConstDstCoeff->getAPInt();
1524 ++ExactSIVindependence;
1525 ++ExactSIVsuccesses;
1532 APInt UM(Bits, 1,
true);
1533 bool UMvalid =
false;
1536 collectConstantUpperBound(CurLoop, Delta->
getType())) {
1537 UM = CUB->getAPInt();
1583 ++ExactSIVindependence;
1584 ++ExactSIVsuccesses;
1606 ++ExactSIVsuccesses;
1632 ++ExactSIVsuccesses;
1649 ++ExactSIVsuccesses;
1653 Result.DV[
Level].Direction &= NewDirection;
1655 ++ExactSIVindependence;
1667 return ConstDividend.
srem(ConstDivisor) == 0;
1702 bool DependenceInfo::weakZeroSrcSIVtest(
const SCEV *DstCoeff,
1703 const SCEV *SrcConst,
1704 const SCEV *DstConst,
1705 const Loop *CurLoop,
unsigned Level,
1707 Constraint &NewConstraint)
const {
1715 ++WeakZeroSIVapplications;
1716 assert(0 < Level && Level <= MaxLevels &&
"Level out of range");
1718 Result.Consistent =
false;
1719 const SCEV *Delta = SE->getMinusSCEV(SrcConst, DstConst);
1720 NewConstraint.setLine(SE->getZero(Delta->
getType()), DstCoeff, Delta,
1724 if (Level < CommonLevels) {
1726 Result.DV[
Level].PeelFirst =
true;
1727 ++WeakZeroSIVsuccesses;
1734 const SCEV *AbsCoeff =
1735 SE->isKnownNegative(ConstCoeff) ?
1736 SE->getNegativeSCEV(ConstCoeff) : ConstCoeff;
1737 const SCEV *NewDelta =
1738 SE->isKnownNegative(ConstCoeff) ? SE->getNegativeSCEV(Delta) : Delta;
1742 if (
const SCEV *UpperBound = collectUpperBound(CurLoop, Delta->
getType())) {
1744 const SCEV *Product = SE->getMulExpr(AbsCoeff, UpperBound);
1746 ++WeakZeroSIVindependence;
1747 ++WeakZeroSIVsuccesses;
1752 if (Level < CommonLevels) {
1754 Result.DV[
Level].PeelLast =
true;
1755 ++WeakZeroSIVsuccesses;
1763 if (SE->isKnownNegative(NewDelta)) {
1765 ++WeakZeroSIVindependence;
1766 ++WeakZeroSIVsuccesses;
1771 if (isa<SCEVConstant>(Delta) &&
1773 ++WeakZeroSIVindependence;
1774 ++WeakZeroSIVsuccesses;
1812 bool DependenceInfo::weakZeroDstSIVtest(
const SCEV *SrcCoeff,
1813 const SCEV *SrcConst,
1814 const SCEV *DstConst,
1815 const Loop *CurLoop,
unsigned Level,
1817 Constraint &NewConstraint)
const {
1824 ++WeakZeroSIVapplications;
1825 assert(0 < Level && Level <= SrcLevels &&
"Level out of range");
1827 Result.Consistent =
false;
1828 const SCEV *Delta = SE->getMinusSCEV(DstConst, SrcConst);
1829 NewConstraint.setLine(SrcCoeff, SE->getZero(Delta->
getType()), Delta,
1833 if (Level < CommonLevels) {
1835 Result.DV[
Level].PeelFirst =
true;
1836 ++WeakZeroSIVsuccesses;
1843 const SCEV *AbsCoeff =
1844 SE->isKnownNegative(ConstCoeff) ?
1845 SE->getNegativeSCEV(ConstCoeff) : ConstCoeff;
1846 const SCEV *NewDelta =
1847 SE->isKnownNegative(ConstCoeff) ? SE->getNegativeSCEV(Delta) : Delta;
1851 if (
const SCEV *UpperBound = collectUpperBound(CurLoop, Delta->
getType())) {
1853 const SCEV *Product = SE->getMulExpr(AbsCoeff, UpperBound);
1855 ++WeakZeroSIVindependence;
1856 ++WeakZeroSIVsuccesses;
1861 if (Level < CommonLevels) {
1863 Result.DV[
Level].PeelLast =
true;
1864 ++WeakZeroSIVsuccesses;
1872 if (SE->isKnownNegative(NewDelta)) {
1874 ++WeakZeroSIVindependence;
1875 ++WeakZeroSIVsuccesses;
1880 if (isa<SCEVConstant>(Delta) &&
1882 ++WeakZeroSIVindependence;
1883 ++WeakZeroSIVsuccesses;
1897 bool DependenceInfo::exactRDIVtest(
const SCEV *SrcCoeff,
const SCEV *DstCoeff,
1898 const SCEV *SrcConst,
const SCEV *DstConst,
1899 const Loop *SrcLoop,
const Loop *DstLoop,
1902 LLVM_DEBUG(
dbgs() <<
"\t SrcCoeff = " << *SrcCoeff <<
" = AM\n");
1903 LLVM_DEBUG(
dbgs() <<
"\t DstCoeff = " << *DstCoeff <<
" = BM\n");
1906 ++ExactRDIVapplications;
1907 Result.Consistent =
false;
1908 const SCEV *Delta = SE->getMinusSCEV(DstConst, SrcConst);
1913 if (!ConstDelta || !ConstSrcCoeff || !ConstDstCoeff)
1918 APInt AM = ConstSrcCoeff->getAPInt();
1919 APInt BM = ConstDstCoeff->getAPInt();
1923 ++ExactRDIVindependence;
1930 APInt SrcUM(Bits, 1,
true);
1931 bool SrcUMvalid =
false;
1934 collectConstantUpperBound(SrcLoop, Delta->
getType())) {
1935 SrcUM = UpperBound->getAPInt();
1940 APInt DstUM(Bits, 1,
true);
1941 bool DstUMvalid =
false;
1944 collectConstantUpperBound(DstLoop, Delta->
getType())) {
1945 DstUM = UpperBound->getAPInt();
1991 ++ExactRDIVindependence;
2038 bool DependenceInfo::symbolicRDIVtest(
const SCEV *A1,
const SCEV *A2,
2041 const Loop *Loop2)
const {
2042 ++SymbolicRDIVapplications;
2049 const SCEV *N1 = collectUpperBound(Loop1, A1->
getType());
2050 const SCEV *N2 = collectUpperBound(Loop2, A1->
getType());
2053 const SCEV *C2_C1 = SE->getMinusSCEV(C2, C1);
2054 const SCEV *C1_C2 = SE->getMinusSCEV(C1, C2);
2057 if (SE->isKnownNonNegative(A1)) {
2058 if (SE->isKnownNonNegative(A2)) {
2062 const SCEV *A1N1 = SE->getMulExpr(A1, N1);
2065 ++SymbolicRDIVindependence;
2071 const SCEV *A2N2 = SE->getMulExpr(A2, N2);
2074 ++SymbolicRDIVindependence;
2079 else if (SE->isKnownNonPositive(A2)) {
2083 const SCEV *A1N1 = SE->getMulExpr(A1, N1);
2084 const SCEV *A2N2 = SE->getMulExpr(A2, N2);
2085 const SCEV *A1N1_A2N2 = SE->getMinusSCEV(A1N1, A2N2);
2086 LLVM_DEBUG(
dbgs() <<
"\t A1*N1 - A2*N2 = " << *A1N1_A2N2 <<
"\n");
2088 ++SymbolicRDIVindependence;
2093 if (SE->isKnownNegative(C2_C1)) {
2094 ++SymbolicRDIVindependence;
2099 else if (SE->isKnownNonPositive(A1)) {
2100 if (SE->isKnownNonNegative(A2)) {
2104 const SCEV *A1N1 = SE->getMulExpr(A1, N1);
2105 const SCEV *A2N2 = SE->getMulExpr(A2, N2);
2106 const SCEV *A1N1_A2N2 = SE->getMinusSCEV(A1N1, A2N2);
2107 LLVM_DEBUG(
dbgs() <<
"\t A1*N1 - A2*N2 = " << *A1N1_A2N2 <<
"\n");
2109 ++SymbolicRDIVindependence;
2114 if (SE->isKnownPositive(C2_C1)) {
2115 ++SymbolicRDIVindependence;
2119 else if (SE->isKnownNonPositive(A2)) {
2123 const SCEV *A1N1 = SE->getMulExpr(A1, N1);
2126 ++SymbolicRDIVindependence;
2132 const SCEV *A2N2 = SE->getMulExpr(A2, N2);
2135 ++SymbolicRDIVindependence;
2153 bool DependenceInfo::testSIV(
const SCEV *Src,
const SCEV *Dst,
unsigned &Level,
2155 const SCEV *&SplitIter)
const {
2160 if (SrcAddRec && DstAddRec) {
2162 const SCEV *DstConst = DstAddRec->getStart();
2164 const SCEV *DstCoeff = DstAddRec->getStepRecurrence(*SE);
2166 assert(CurLoop == DstAddRec->getLoop() &&
2167 "both loops in SIV should be same");
2168 Level = mapSrcLoop(CurLoop);
2170 if (SrcCoeff == DstCoeff)
2171 disproven = strongSIVtest(SrcCoeff, SrcConst, DstConst, CurLoop,
2172 Level, Result, NewConstraint);
2173 else if (SrcCoeff == SE->getNegativeSCEV(DstCoeff))
2174 disproven = weakCrossingSIVtest(SrcCoeff, SrcConst, DstConst, CurLoop,
2175 Level, Result, NewConstraint, SplitIter);
2177 disproven = exactSIVtest(SrcCoeff, DstCoeff, SrcConst, DstConst, CurLoop,
2178 Level, Result, NewConstraint);
2180 gcdMIVtest(Src, Dst, Result) ||
2181 symbolicRDIVtest(SrcCoeff, DstCoeff, SrcConst, DstConst, CurLoop, CurLoop);
2186 const SCEV *DstConst = Dst;
2188 Level = mapSrcLoop(CurLoop);
2189 return weakZeroDstSIVtest(SrcCoeff, SrcConst, DstConst, CurLoop,
2190 Level, Result, NewConstraint) ||
2191 gcdMIVtest(Src, Dst, Result);
2194 const SCEV *DstConst = DstAddRec->getStart();
2195 const SCEV *DstCoeff = DstAddRec->getStepRecurrence(*SE);
2196 const SCEV *SrcConst = Src;
2197 const Loop *CurLoop = DstAddRec->getLoop();
2198 Level = mapDstLoop(CurLoop);
2199 return weakZeroSrcSIVtest(DstCoeff, SrcConst, DstConst,
2200 CurLoop, Level, Result, NewConstraint) ||
2201 gcdMIVtest(Src, Dst, Result);
2221 bool DependenceInfo::testRDIV(
const SCEV *Src,
const SCEV *Dst,
2229 const SCEV *SrcConst, *DstConst;
2230 const SCEV *SrcCoeff, *DstCoeff;
2231 const Loop *SrcLoop, *DstLoop;
2237 if (SrcAddRec && DstAddRec) {
2240 SrcLoop = SrcAddRec->
getLoop();
2241 DstConst = DstAddRec->getStart();
2242 DstCoeff = DstAddRec->getStepRecurrence(*SE);
2243 DstLoop = DstAddRec->getLoop();
2245 else if (SrcAddRec) {
2247 dyn_cast<SCEVAddRecExpr>(SrcAddRec->
getStart())) {
2248 SrcConst = tmpAddRec->getStart();
2249 SrcCoeff = tmpAddRec->getStepRecurrence(*SE);
2250 SrcLoop = tmpAddRec->getLoop();
2253 DstLoop = SrcAddRec->
getLoop();
2258 else if (DstAddRec) {
2260 dyn_cast<SCEVAddRecExpr>(DstAddRec->getStart())) {
2261 DstConst = tmpAddRec->getStart();
2262 DstCoeff = tmpAddRec->getStepRecurrence(*SE);
2263 DstLoop = tmpAddRec->getLoop();
2265 SrcCoeff = SE->getNegativeSCEV(DstAddRec->getStepRecurrence(*SE));
2266 SrcLoop = DstAddRec->getLoop();
2273 return exactRDIVtest(SrcCoeff, DstCoeff,
2277 gcdMIVtest(Src, Dst, Result) ||
2278 symbolicRDIVtest(SrcCoeff, DstCoeff,
2287 bool DependenceInfo::testMIV(
const SCEV *Src,
const SCEV *Dst,
2292 Result.Consistent =
false;
2293 return gcdMIVtest(Src, Dst, Result) ||
2294 banerjeeMIVtest(Src, Dst, Loops, Result);
2302 if (
const auto *
Constant = dyn_cast<SCEVConstant>(Expr))
2304 else if (
const auto *Product = dyn_cast<SCEVMulExpr>(Expr))
2305 if (
const auto *
Constant = dyn_cast<SCEVConstant>(Product->getOperand(0)))
2329 bool DependenceInfo::gcdMIVtest(
const SCEV *Src,
const SCEV *Dst,
2333 unsigned BitWidth = SE->getTypeSizeInBits(Src->
getType());
2340 const SCEV *Coefficients = Src;
2342 dyn_cast<SCEVAddRecExpr>(Coefficients)) {
2343 const SCEV *Coeff = AddRec->getStepRecurrence(*SE);
2351 Coefficients = AddRec->getStart();
2353 const SCEV *SrcConst = Coefficients;
2361 dyn_cast<SCEVAddRecExpr>(Coefficients)) {
2362 const SCEV *Coeff = AddRec->getStepRecurrence(*SE);
2370 Coefficients = AddRec->getStart();
2372 const SCEV *DstConst = Coefficients;
2375 const SCEV *Delta = SE->getMinusSCEV(DstConst, SrcConst);
2378 if (
const SCEVAddExpr *Sum = dyn_cast<SCEVAddExpr>(Delta)) {
2380 for (
unsigned Op = 0, Ops = Sum->getNumOperands();
Op < Ops;
Op++) {
2381 const SCEV *Operand = Sum->getOperand(
Op);
2382 if (isa<SCEVConstant>(Operand)) {
2383 assert(!Constant &&
"Surprised to find multiple constants");
2384 Constant = cast<SCEVConstant>(Operand);
2386 else if (
const SCEVMulExpr *Product = dyn_cast<SCEVMulExpr>(Operand)) {
2394 ConstOpValue.
abs());
2402 APInt ConstDelta = cast<SCEVConstant>(Constant)->getAPInt();
2404 if (ConstDelta == 0)
2408 APInt Remainder = ConstDelta.
srem(RunningGCD);
2409 if (Remainder != 0) {
2428 bool Improved =
false;
2431 dyn_cast<SCEVAddRecExpr>(Coefficients)) {
2432 Coefficients = AddRec->getStart();
2433 const Loop *CurLoop = AddRec->getLoop();
2434 RunningGCD = ExtraGCD;
2435 const SCEV *SrcCoeff = AddRec->getStepRecurrence(*SE);
2436 const SCEV *DstCoeff = SE->getMinusSCEV(SrcCoeff, SrcCoeff);
2437 const SCEV *Inner = Src;
2438 while (RunningGCD != 1 && isa<SCEVAddRecExpr>(Inner)) {
2439 AddRec = cast<SCEVAddRecExpr>(Inner);
2440 const SCEV *Coeff = AddRec->getStepRecurrence(*SE);
2441 if (CurLoop == AddRec->getLoop())
2452 Inner = AddRec->getStart();
2455 while (RunningGCD != 1 && isa<SCEVAddRecExpr>(Inner)) {
2456 AddRec = cast<SCEVAddRecExpr>(Inner);
2457 const SCEV *Coeff = AddRec->getStepRecurrence(*SE);
2458 if (CurLoop == AddRec->getLoop())
2469 Inner = AddRec->getStart();
2471 Delta = SE->getMinusSCEV(SrcCoeff, DstCoeff);
2482 if (RunningGCD != 0) {
2483 Remainder = ConstDelta.
srem(RunningGCD);
2485 if (Remainder != 0) {
2486 unsigned Level = mapSrcLoop(CurLoop);
2532 bool DependenceInfo::banerjeeMIVtest(
const SCEV *Src,
const SCEV *Dst,
2536 ++BanerjeeApplications;
2539 CoefficientInfo *A = collectCoeffInfo(Src,
true, A0);
2542 CoefficientInfo *
B = collectCoeffInfo(Dst,
false, B0);
2543 BoundInfo *Bound =
new BoundInfo[MaxLevels + 1];
2544 const SCEV *Delta = SE->getMinusSCEV(B0, A0);
2549 for (
unsigned K = 1; K <= MaxLevels; ++K) {
2550 Bound[K].Iterations = A[K].Iterations ? A[K].Iterations : B[K].Iterations;
2553 findBoundsALL(A, B, Bound, K);
2560 if (Bound[K].
Upper[Dependence::DVEntry::ALL])
2568 bool Disproved =
false;
2571 unsigned DepthExpanded = 0;
2572 unsigned NewDeps = exploreDirections(1, A, B, Bound,
2573 Loops, DepthExpanded, Delta);
2575 bool Improved =
false;
2576 for (
unsigned K = 1; K <= CommonLevels; ++K) {
2578 unsigned Old = Result.DV[K - 1].Direction;
2579 Result.DV[K - 1].Direction = Old & Bound[K].DirSet;
2580 Improved |= Old != Result.DV[K - 1].Direction;
2581 if (!Result.DV[K - 1].Direction) {
2589 ++BanerjeeSuccesses;
2592 ++BanerjeeIndependence;
2597 ++BanerjeeIndependence;
2612 unsigned DependenceInfo::exploreDirections(
unsigned Level, CoefficientInfo *A,
2613 CoefficientInfo *
B, BoundInfo *Bound,
2615 unsigned &DepthExpanded,
2616 const SCEV *Delta)
const {
2617 if (Level > CommonLevels) {
2620 for (
unsigned K = 1; K <= CommonLevels; ++K) {
2622 Bound[K].DirSet |= Bound[K].Direction;
2647 if (Level > DepthExpanded) {
2648 DepthExpanded =
Level;
2650 findBoundsLT(A, B, Bound, Level);
2651 findBoundsGT(A, B, Bound, Level);
2652 findBoundsEQ(A, B, Bound, Level);
2661 if (Bound[Level].
Upper[Dependence::DVEntry::LT])
2672 if (Bound[Level].
Upper[Dependence::DVEntry::EQ])
2683 if (Bound[Level].
Upper[Dependence::DVEntry::GT])
2691 unsigned NewDeps = 0;
2695 NewDeps += exploreDirections(Level + 1, A, B, Bound,
2696 Loops, DepthExpanded, Delta);
2700 NewDeps += exploreDirections(Level + 1, A, B, Bound,
2701 Loops, DepthExpanded, Delta);
2705 NewDeps += exploreDirections(Level + 1, A, B, Bound,
2706 Loops, DepthExpanded, Delta);
2712 return exploreDirections(Level + 1, A, B, Bound, Loops, DepthExpanded, Delta);
2717 bool DependenceInfo::testBounds(
unsigned char DirKind,
unsigned Level,
2718 BoundInfo *Bound,
const SCEV *Delta)
const {
2719 Bound[
Level].Direction = DirKind;
2720 if (
const SCEV *LowerBound = getLowerBound(Bound))
2723 if (
const SCEV *UpperBound = getUpperBound(Bound))
2745 void DependenceInfo::findBoundsALL(CoefficientInfo *A, CoefficientInfo *B,
2746 BoundInfo *Bound,
unsigned K)
const {
2749 if (Bound[K].Iterations) {
2751 SE->getMulExpr(SE->getMinusSCEV(A[K].NegPart, B[K].PosPart),
2752 Bound[K].Iterations);
2754 SE->getMulExpr(SE->getMinusSCEV(A[K].PosPart, B[K].NegPart),
2755 Bound[K].Iterations);
2761 SE->getZero(A[K].Coeff->getType());
2764 SE->getZero(A[K].Coeff->getType());
2784 void DependenceInfo::findBoundsEQ(CoefficientInfo *A, CoefficientInfo *B,
2785 BoundInfo *Bound,
unsigned K)
const {
2788 if (Bound[K].Iterations) {
2789 const SCEV *Delta = SE->getMinusSCEV(A[K].Coeff, B[K].Coeff);
2790 const SCEV *NegativePart = getNegativePart(Delta);
2792 SE->getMulExpr(NegativePart, Bound[K].Iterations);
2793 const SCEV *PositivePart = getPositivePart(Delta);
2795 SE->getMulExpr(PositivePart, Bound[K].Iterations);
2800 const SCEV *Delta = SE->getMinusSCEV(A[K].Coeff, B[K].Coeff);
2801 const SCEV *NegativePart = getNegativePart(Delta);
2802 if (NegativePart->
isZero())
2804 const SCEV *PositivePart = getPositivePart(Delta);
2805 if (PositivePart->
isZero())
2824 void DependenceInfo::findBoundsLT(CoefficientInfo *A, CoefficientInfo *B,
2825 BoundInfo *Bound,
unsigned K)
const {
2828 if (Bound[K].Iterations) {
2829 const SCEV *Iter_1 = SE->getMinusSCEV(
2830 Bound[K].Iterations, SE->getOne(Bound[K].Iterations->getType()));
2831 const SCEV *NegPart =
2832 getNegativePart(SE->getMinusSCEV(A[K].NegPart, B[K].Coeff));
2834 SE->getMinusSCEV(SE->getMulExpr(NegPart, Iter_1), B[K].Coeff);
2835 const SCEV *PosPart =
2836 getPositivePart(SE->getMinusSCEV(A[K].PosPart, B[K].Coeff));
2838 SE->getMinusSCEV(SE->getMulExpr(PosPart, Iter_1), B[K].Coeff);
2843 const SCEV *NegPart =
2844 getNegativePart(SE->getMinusSCEV(A[K].NegPart, B[K].Coeff));
2847 const SCEV *PosPart =
2848 getPositivePart(SE->getMinusSCEV(A[K].PosPart, B[K].Coeff));
2868 void DependenceInfo::findBoundsGT(CoefficientInfo *A, CoefficientInfo *B,
2869 BoundInfo *Bound,
unsigned K)
const {
2872 if (Bound[K].Iterations) {
2873 const SCEV *Iter_1 = SE->getMinusSCEV(
2874 Bound[K].Iterations, SE->getOne(Bound[K].Iterations->getType()));
2875 const SCEV *NegPart =
2876 getNegativePart(SE->getMinusSCEV(A[K].Coeff, B[K].PosPart));
2878 SE->getAddExpr(SE->getMulExpr(NegPart, Iter_1), A[K].Coeff);
2879 const SCEV *PosPart =
2880 getPositivePart(SE->getMinusSCEV(A[K].Coeff, B[K].NegPart));
2882 SE->getAddExpr(SE->getMulExpr(PosPart, Iter_1), A[K].Coeff);
2887 const SCEV *NegPart = getNegativePart(SE->getMinusSCEV(A[K].Coeff, B[K].PosPart));
2890 const SCEV *PosPart = getPositivePart(SE->getMinusSCEV(A[K].Coeff, B[K].NegPart));
2898 const SCEV *DependenceInfo::getPositivePart(
const SCEV *X)
const {
2899 return SE->getSMaxExpr(X, SE->getZero(X->
getType()));
2904 const SCEV *DependenceInfo::getNegativePart(
const SCEV *X)
const {
2905 return SE->getSMinExpr(X, SE->getZero(X->
getType()));
2912 DependenceInfo::CoefficientInfo *
2913 DependenceInfo::collectCoeffInfo(
const SCEV *Subscript,
bool SrcFlag,
2915 const SCEV *Zero = SE->getZero(Subscript->
getType());
2916 CoefficientInfo *CI =
new CoefficientInfo[MaxLevels + 1];
2917 for (
unsigned K = 1; K <= MaxLevels; ++K) {
2919 CI[K].PosPart = Zero;
2920 CI[K].NegPart = Zero;
2921 CI[K].Iterations =
nullptr;
2923 while (
const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(Subscript)) {
2924 const Loop *L = AddRec->getLoop();
2925 unsigned K = SrcFlag ? mapSrcLoop(L) : mapDstLoop(L);
2926 CI[K].Coeff = AddRec->getStepRecurrence(*SE);
2927 CI[K].PosPart = getPositivePart(CI[K].Coeff);
2928 CI[K].NegPart = getNegativePart(CI[K].Coeff);
2929 CI[K].Iterations = collectUpperBound(L, Subscript->
getType());
2930 Subscript = AddRec->getStart();
2932 Constant = Subscript;
2935 for (
unsigned K = 1; K <= MaxLevels; ++K) {
2942 if (CI[K].Iterations)
2958 const SCEV *DependenceInfo::getLowerBound(BoundInfo *Bound)
const {
2959 const SCEV *Sum = Bound[1].Lower[Bound[1].Direction];
2960 for (
unsigned K = 2; Sum && K <= MaxLevels; ++K) {
2962 Sum = SE->getAddExpr(Sum, Bound[K].
Lower[Bound[K].Direction]);
2974 const SCEV *DependenceInfo::getUpperBound(BoundInfo *Bound)
const {
2975 const SCEV *Sum = Bound[1].Upper[Bound[1].Direction];
2976 for (
unsigned K = 2; Sum && K <= MaxLevels; ++K) {
2978 Sum = SE->getAddExpr(Sum, Bound[K].
Upper[Bound[K].Direction]);
2995 const SCEV *DependenceInfo::findCoefficient(
const SCEV *Expr,
2996 const Loop *TargetLoop)
const {
2999 return SE->getZero(Expr->
getType());
3000 if (AddRec->
getLoop() == TargetLoop)
3002 return findCoefficient(AddRec->
getStart(), TargetLoop);
3011 const SCEV *DependenceInfo::zeroCoefficient(
const SCEV *Expr,
3012 const Loop *TargetLoop)
const {
3016 if (AddRec->
getLoop() == TargetLoop)
3018 return SE->getAddRecExpr(zeroCoefficient(AddRec->
getStart(), TargetLoop),
3030 const SCEV *DependenceInfo::addToCoefficient(
const SCEV *Expr,
3031 const Loop *TargetLoop,
3035 return SE->getAddRecExpr(Expr,
3039 if (AddRec->
getLoop() == TargetLoop) {
3043 return SE->getAddRecExpr(AddRec->
getStart(),
3048 if (SE->isLoopInvariant(AddRec, TargetLoop))
3050 return SE->getAddRecExpr(
3067 bool DependenceInfo::propagate(
const SCEV *&Src,
const SCEV *&Dst,
3071 bool Result =
false;
3072 for (
unsigned LI : Loops.
set_bits()) {
3075 if (Constraints[LI].isDistance())
3076 Result |= propagateDistance(Src, Dst, Constraints[LI], Consistent);
3077 else if (Constraints[LI].isLine())
3078 Result |= propagateLine(Src, Dst, Constraints[LI], Consistent);
3079 else if (Constraints[LI].isPoint())
3080 Result |= propagatePoint(Src, Dst, Constraints[LI]);
3091 bool DependenceInfo::propagateDistance(
const SCEV *&Src,
const SCEV *&Dst,
3092 Constraint &CurConstraint,
3094 const Loop *CurLoop = CurConstraint.getAssociatedLoop();
3096 const SCEV *A_K = findCoefficient(Src, CurLoop);
3099 const SCEV *DA_K = SE->getMulExpr(A_K, CurConstraint.getD());
3100 Src = SE->getMinusSCEV(Src, DA_K);
3101 Src = zeroCoefficient(Src, CurLoop);
3104 Dst = addToCoefficient(Dst, CurLoop, SE->getNegativeSCEV(A_K));
3106 if (!findCoefficient(Dst, CurLoop)->
isZero())
3117 bool DependenceInfo::propagateLine(
const SCEV *&Src,
const SCEV *&Dst,
3118 Constraint &CurConstraint,
3120 const Loop *CurLoop = CurConstraint.getAssociatedLoop();
3121 const SCEV *A = CurConstraint.getA();
3122 const SCEV *B = CurConstraint.getB();
3123 const SCEV *
C = CurConstraint.getC();
3124 LLVM_DEBUG(
dbgs() <<
"\t\tA = " << *A <<
", B = " << *B <<
", C = " << *C
3131 if (!Bconst || !Cconst)
return false;
3133 APInt Charlie = Cconst->getAPInt();
3135 assert(Charlie.
srem(Beta) == 0 &&
"C should be evenly divisible by B");
3136 const SCEV *AP_K = findCoefficient(Dst, CurLoop);
3138 Src = SE->getMinusSCEV(Src, SE->getMulExpr(AP_K, SE->getConstant(CdivB)));
3139 Dst = zeroCoefficient(Dst, CurLoop);
3140 if (!findCoefficient(Src, CurLoop)->
isZero())
3146 if (!Aconst || !Cconst)
return false;
3148 APInt Charlie = Cconst->getAPInt();
3150 assert(Charlie.
srem(Alpha) == 0 &&
"C should be evenly divisible by A");
3151 const SCEV *A_K = findCoefficient(Src, CurLoop);
3152 Src = SE->getAddExpr(Src, SE->getMulExpr(A_K, SE->getConstant(CdivA)));
3153 Src = zeroCoefficient(Src, CurLoop);
3154 if (!findCoefficient(Dst, CurLoop)->
isZero())
3160 if (!Aconst || !Cconst)
return false;
3162 APInt Charlie = Cconst->getAPInt();
3164 assert(Charlie.
srem(Alpha) == 0 &&
"C should be evenly divisible by A");
3165 const SCEV *A_K = findCoefficient(Src, CurLoop);
3166 Src = SE->getAddExpr(Src, SE->getMulExpr(A_K, SE->getConstant(CdivA)));
3167 Src = zeroCoefficient(Src, CurLoop);
3168 Dst = addToCoefficient(Dst, CurLoop, A_K);
3169 if (!findCoefficient(Dst, CurLoop)->
isZero())
3174 const SCEV *A_K = findCoefficient(Src, CurLoop);
3175 Src = SE->getMulExpr(Src, A);
3176 Dst = SE->getMulExpr(Dst, A);
3177 Src = SE->getAddExpr(Src, SE->getMulExpr(A_K, C));
3178 Src = zeroCoefficient(Src, CurLoop);
3179 Dst = addToCoefficient(Dst, CurLoop, SE->getMulExpr(A_K, B));
3180 if (!findCoefficient(Dst, CurLoop)->isZero())
3192 bool DependenceInfo::propagatePoint(
const SCEV *&Src,
const SCEV *&Dst,
3193 Constraint &CurConstraint) {
3194 const Loop *CurLoop = CurConstraint.getAssociatedLoop();
3195 const SCEV *A_K = findCoefficient(Src, CurLoop);
3196 const SCEV *AP_K = findCoefficient(Dst, CurLoop);
3197 const SCEV *XA_K = SE->getMulExpr(A_K, CurConstraint.getX());
3198 const SCEV *YAP_K = SE->getMulExpr(AP_K, CurConstraint.getY());
3200 Src = SE->getAddExpr(Src, SE->getMinusSCEV(XA_K, YAP_K));
3201 Src = zeroCoefficient(Src, CurLoop);
3204 Dst = zeroCoefficient(Dst, CurLoop);
3212 const Constraint &CurConstraint)
const {
3215 if (CurConstraint.isAny())
3217 else if (CurConstraint.isDistance()) {
3220 Level.
Distance = CurConstraint.getD();
3222 if (!SE->isKnownNonZero(Level.
Distance))
3224 if (!SE->isKnownNonPositive(Level.
Distance))
3226 if (!SE->isKnownNonNegative(Level.
Distance))
3230 else if (CurConstraint.isLine()) {
3235 else if (CurConstraint.isPoint()) {
3240 CurConstraint.getY(),
3241 CurConstraint.getX()))
3245 CurConstraint.getY(),
3246 CurConstraint.getX()))
3250 CurConstraint.getY(),
3251 CurConstraint.getX()))
3275 const SCEV *SrcAccessFn =
3276 SE->getSCEVAtScope(SrcPtr, SrcLoop);
3277 const SCEV *DstAccessFn =
3278 SE->getSCEVAtScope(DstPtr, DstLoop);
3285 if (!SrcBase || !DstBase || SrcBase != DstBase)
3288 const SCEV *ElementSize = SE->getElementSize(Src);
3289 if (ElementSize != SE->getElementSize(Dst))
3292 const SCEV *SrcSCEV = SE->getMinusSCEV(SrcAccessFn, SrcBase);
3293 const SCEV *DstSCEV = SE->getMinusSCEV(DstAccessFn, DstBase);
3297 if (!SrcAR || !DstAR || !SrcAR->
isAffine() || !DstAR->isAffine())
3302 SE->collectParametricTerms(SrcAR, Terms);
3303 SE->collectParametricTerms(DstAR, Terms);
3307 SE->findArrayDimensions(Terms, Sizes, ElementSize);
3311 SE->computeAccessFunctions(SrcAR, SrcSubscripts, Sizes);
3312 SE->computeAccessFunctions(DstAR, DstSubscripts, Sizes);
3315 if (SrcSubscripts.
size() < 2 || DstSubscripts.
size() < 2 ||
3316 SrcSubscripts.
size() != DstSubscripts.
size())
3328 for (
int i = 1; i <
size; ++i) {
3332 if (!isKnownLessThan(SrcSubscripts[i], Sizes[i - 1]))
3338 if (!isKnownLessThan(DstSubscripts[i], Sizes[i - 1]))
3343 dbgs() <<
"\nSrcSubscripts: ";
3344 for (
int i = 0; i <
size; i++)
3345 dbgs() << *SrcSubscripts[i];
3346 dbgs() <<
"\nDstSubscripts: ";
3347 for (
int i = 0; i <
size; i++)
3348 dbgs() << *DstSubscripts[i];
3356 for (
int i = 0; i <
size; ++i) {
3357 Pair[i].Src = SrcSubscripts[i];
3358 Pair[i].Dst = DstSubscripts[i];
3359 unifySubscriptType(&Pair[i]);
3404 std::unique_ptr<Dependence>
3406 bool PossiblyLoopIndependent) {
3408 PossiblyLoopIndependent =
false;
3417 LLVM_DEBUG(
dbgs() <<
"can only handle simple loads and stores\n");
3418 return std::make_unique<Dependence>(Src, Dst);
3433 return std::make_unique<Dependence>(Src, Dst);
3443 establishNestingLevels(Src, Dst);
3444 LLVM_DEBUG(
dbgs() <<
" common nesting levels = " << CommonLevels <<
"\n");
3445 LLVM_DEBUG(
dbgs() <<
" maximum nesting levels = " << MaxLevels <<
"\n");
3447 FullDependence Result(Src, Dst, PossiblyLoopIndependent, CommonLevels);
3452 const SCEV *SrcSCEV = SE->getSCEV(SrcPtr);
3453 const SCEV *DstSCEV = SE->getSCEV(DstPtr);
3456 Pair[0].Src = SrcSCEV;
3457 Pair[0].Dst = DstSCEV;
3460 if (tryDelinearize(Src, Dst, Pair)) {
3462 Pairs = Pair.
size();
3466 for (
unsigned P = 0;
P < Pairs; ++
P) {
3467 Pair[
P].Loops.
resize(MaxLevels + 1);
3468 Pair[
P].GroupLoops.
resize(MaxLevels + 1);
3470 removeMatchingExtensions(&Pair[
P]);
3471 Pair[
P].Classification =
3472 classifyPair(Pair[P].Src, LI->getLoopFor(Src->getParent()),
3473 Pair[P].Dst, LI->getLoopFor(Dst->getParent()),
3475 Pair[
P].GroupLoops = Pair[
P].Loops;
3476 Pair[
P].Group.set(P);
3480 LLVM_DEBUG(
dbgs() <<
"\tclass = " << Pair[P].Classification <<
"\n");
3545 for (
unsigned SI = 0;
SI < Pairs; ++
SI) {
3546 if (Pair[
SI].Classification == Subscript::NonLinear) {
3548 ++NonlinearSubscriptPairs;
3549 collectCommonLoops(Pair[
SI].Src,
3550 LI->getLoopFor(Src->getParent()),
3552 collectCommonLoops(Pair[
SI].Dst,
3553 LI->getLoopFor(Dst->getParent()),
3555 Result.Consistent =
false;
3556 }
else if (Pair[
SI].Classification == Subscript::ZIV) {
3563 for (
unsigned SJ =
SI + 1; SJ < Pairs; ++SJ) {
3565 Intersection &= Pair[SJ].GroupLoops;
3566 if (Intersection.
any()) {
3568 Pair[SJ].GroupLoops |= Pair[
SI].GroupLoops;
3570 Pair[SJ].Group |= Pair[
SI].Group;
3575 if (Pair[
SI].Group.count() == 1) {
3577 ++SeparableSubscriptPairs;
3581 ++CoupledSubscriptPairs;
3592 Constraint NewConstraint;
3593 NewConstraint.setAny(SE);
3598 switch (Pair[
SI].Classification) {
3599 case Subscript::ZIV:
3601 if (testZIV(Pair[
SI].Src, Pair[
SI].Dst, Result))
3604 case Subscript::SIV: {
3607 const SCEV *SplitIter =
nullptr;
3608 if (testSIV(Pair[
SI].Src, Pair[
SI].Dst, Level, Result, NewConstraint,
3613 case Subscript::RDIV:
3615 if (testRDIV(Pair[
SI].Src, Pair[
SI].Dst, Result))
3618 case Subscript::MIV:
3620 if (testMIV(Pair[
SI].Src, Pair[
SI].Dst, Pair[
SI].Loops, Result))
3628 if (Coupled.
count()) {
3631 LLVM_DEBUG(
dbgs() <<
"MaxLevels + 1 = " << MaxLevels + 1 <<
"\n");
3633 for (
unsigned II = 0; II <= MaxLevels; ++II)
3634 Constraints[II].setAny(SE);
3642 for (
unsigned SJ : Group.
set_bits()) {
3644 if (Pair[SJ].Classification == Subscript::SIV)
3650 unifySubscriptType(PairsInGroup);
3652 while (Sivs.
any()) {
3653 bool Changed =
false;
3654 for (
unsigned SJ : Sivs.
set_bits()) {
3658 const SCEV *SplitIter =
nullptr;
3660 if (testSIV(Pair[SJ].Src, Pair[SJ].Dst, Level, Result, NewConstraint,
3663 ConstrainedLevels.
set(Level);
3664 if (intersectConstraints(&Constraints[Level], &NewConstraint)) {
3665 if (Constraints[Level].isEmpty()) {
3666 ++DeltaIndependence;
3678 for (
unsigned SJ : Mivs.
set_bits()) {
3681 if (
propagate(Pair[SJ].Src, Pair[SJ].Dst, Pair[SJ].Loops,
3682 Constraints, Result.Consistent)) {
3684 ++DeltaPropagations;
3685 Pair[SJ].Classification =
3686 classifyPair(Pair[SJ].Src, LI->getLoopFor(Src->getParent()),
3687 Pair[SJ].Dst, LI->getLoopFor(Dst->getParent()),
3689 switch (Pair[SJ].Classification) {
3690 case Subscript::ZIV:
3692 if (testZIV(Pair[SJ].Src, Pair[SJ].Dst, Result))
3696 case Subscript::SIV:
3700 case Subscript::RDIV:
3701 case Subscript::MIV:
3712 for (
unsigned SJ : Mivs.
set_bits()) {
3713 if (Pair[SJ].Classification == Subscript::RDIV) {
3715 if (testRDIV(Pair[SJ].Src, Pair[SJ].Dst, Result))
3725 for (
unsigned SJ : Mivs.
set_bits()) {
3726 if (Pair[SJ].Classification == Subscript::MIV) {
3728 if (testMIV(Pair[SJ].Src, Pair[SJ].Dst, Pair[SJ].Loops, Result))
3737 for (
unsigned SJ : ConstrainedLevels.
set_bits()) {
3738 if (SJ > CommonLevels)
3740 updateDirection(Result.DV[SJ - 1], Constraints[SJ]);
3749 for (
unsigned SI = 0;
SI < Pairs; ++
SI)
3750 CompleteLoops |= Pair[
SI].Loops;
3751 for (
unsigned II = 1; II <= CommonLevels; ++II)
3752 if (CompleteLoops[II])
3753 Result.DV[II - 1].Scalar =
false;
3755 if (PossiblyLoopIndependent) {
3759 for (
unsigned II = 1; II <= CommonLevels; ++II) {
3761 Result.LoopIndependent =
false;
3769 bool AllEqual =
true;
3770 for (
unsigned II = 1; II <= CommonLevels; ++II) {
3780 return std::make_unique<FullDependence>(std::move(Result));
3833 unsigned SplitLevel) {
3835 "Dep should be splitable at SplitLevel");
3838 assert(Src->mayReadFromMemory() || Src->mayWriteToMemory());
3849 establishNestingLevels(Src, Dst);
3855 const SCEV *SrcSCEV = SE->getSCEV(SrcPtr);
3856 const SCEV *DstSCEV = SE->getSCEV(DstPtr);
3857 Pair[0].Src = SrcSCEV;
3858 Pair[0].Dst = DstSCEV;
3861 if (tryDelinearize(Src, Dst, Pair)) {
3863 Pairs = Pair.
size();
3867 for (
unsigned P = 0;
P < Pairs; ++
P) {
3868 Pair[
P].Loops.
resize(MaxLevels + 1);
3869 Pair[
P].GroupLoops.
resize(MaxLevels + 1);
3871 removeMatchingExtensions(&Pair[
P]);
3872 Pair[
P].Classification =
3873 classifyPair(Pair[P].Src, LI->getLoopFor(Src->getParent()),
3874 Pair[P].Dst, LI->getLoopFor(Dst->getParent()),
3876 Pair[
P].GroupLoops = Pair[
P].Loops;
3877 Pair[
P].Group.set(P);
3884 for (
unsigned SI = 0;
SI < Pairs; ++
SI) {
3885 if (Pair[
SI].Classification == Subscript::NonLinear) {
3887 collectCommonLoops(Pair[
SI].Src,
3888 LI->getLoopFor(Src->getParent()),
3890 collectCommonLoops(Pair[
SI].Dst,
3891 LI->getLoopFor(Dst->getParent()),
3893 Result.Consistent =
false;
3895 else if (Pair[
SI].Classification == Subscript::ZIV)
3900 for (
unsigned SJ =
SI + 1; SJ < Pairs; ++SJ) {
3902 Intersection &= Pair[SJ].GroupLoops;
3903 if (Intersection.
any()) {
3905 Pair[SJ].GroupLoops |= Pair[
SI].GroupLoops;
3907 Pair[SJ].Group |= Pair[
SI].Group;
3912 if (Pair[
SI].Group.count() == 1)
3920 Constraint NewConstraint;
3921 NewConstraint.setAny(SE);
3925 switch (Pair[
SI].Classification) {
3926 case Subscript::SIV: {
3928 const SCEV *SplitIter =
nullptr;
3929 (void) testSIV(Pair[
SI].Src, Pair[
SI].Dst, Level,
3930 Result, NewConstraint, SplitIter);
3931 if (Level == SplitLevel) {
3932 assert(SplitIter !=
nullptr);
3937 case Subscript::ZIV:
3938 case Subscript::RDIV:
3939 case Subscript::MIV:
3946 if (Coupled.
count()) {
3949 for (
unsigned II = 0; II <= MaxLevels; ++II)
3950 Constraints[II].setAny(SE);
3956 for (
unsigned SJ : Group.
set_bits()) {
3957 if (Pair[SJ].Classification == Subscript::SIV)
3962 while (Sivs.
any()) {
3963 bool Changed =
false;
3964 for (
unsigned SJ : Sivs.
set_bits()) {
3967 const SCEV *SplitIter =
nullptr;
3968 (void) testSIV(Pair[SJ].Src, Pair[SJ].Dst, Level,
3969 Result, NewConstraint, SplitIter);
3970 if (Level == SplitLevel && SplitIter)
3972 ConstrainedLevels.
set(Level);
3973 if (intersectConstraints(&Constraints[Level], &NewConstraint))
3979 for (
unsigned SJ : Mivs.
set_bits()) {
3981 if (
propagate(Pair[SJ].Src, Pair[SJ].Dst,
3982 Pair[SJ].Loops, Constraints, Result.Consistent)) {
3983 Pair[SJ].Classification =
3984 classifyPair(Pair[SJ].Src, LI->getLoopFor(Src->getParent()),
3985 Pair[SJ].Dst, LI->getLoopFor(Dst->getParent()),
3987 switch (Pair[SJ].Classification) {
3988 case Subscript::ZIV:
3991 case Subscript::SIV:
3995 case Subscript::RDIV:
3996 case Subscript::MIV:
bool runOnFunction(Function &F) override
runOnFunction - Virtual method overriden by subclasses to do the per-function processing of the pass...
APInt abs() const
Get the absolute value;.
const SCEV * getDistance(unsigned Level) const override
getDistance - Returns the distance (or NULL) associated with a particular level.
A parsed version of the target data layout string in and methods for querying it. ...
FunctionPass * createDependenceAnalysisWrapperPass()
createDependenceAnalysisPass - This creates an instance of the DependenceAnalysis wrapper pass...
bool invalidate(IRUnitT &IR, const PreservedAnalyses &PA)
Trigger the invalidation of some other analysis pass if not already handled and return whether it was...
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
This is a 'bitvector' (really, a variable-sized bit array), optimized for the case when the array is ...
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
AnalysisPass to compute dependence information in a function.
This class represents lattice values for constants.
const SCEV * getSplitIteration(const Dependence &Dep, unsigned Level)
getSplitIteration - Give a dependence that's splittable at some particular level, return the iteratio...
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds...
A Module instance is used to store all the information related to an LLVM module. ...
APInt sdiv(const APInt &RHS) const
Signed division function for APInt.
static cl::opt< bool > Delinearize("da-delinearize", cl::init(true), cl::Hidden, cl::ZeroOrMore, cl::desc("Try to delinearize array references."))
static constexpr LocationSize unknown()
Legacy pass manager pass to access dependence information.
unsigned getLoopDepth() const
Return the nesting level of this loop.
void push_back(const T &Elt)
The main scalar evolution driver.
bool slt(const APInt &RHS) const
Signed less than comparison.
bool isZero() const
Return true if the expression is a constant zero.
bool mayWriteToMemory() const
Return true if this instruction may modify memory.
The two locations do not alias at all.
static void sdivrem(const APInt &LHS, const APInt &RHS, APInt &Quotient, APInt &Remainder)
static void dumpSmallBitVector(SmallBitVector &BV)
bool sgt(const APInt &RHS) const
Signed greather than comparison.
static void dump(StringRef Title, SpillInfo const &Spills)
STATISTIC(NumFunctions, "Total number of functions")
An instruction for reading from memory.
const SCEV * getOperand() const
static AliasResult underlyingObjectsAlias(AliasAnalysis *AA, const DataLayout &DL, const MemoryLocation &LocA, const MemoryLocation &LocB)
DependenceInfo - This class is the main dependence-analysis driver.
bool sle(const APInt &RHS) const
Signed less or equal comparison.
void dump(raw_ostream &OS) const
dump - For debugging purposes, dumps a dependence to OS.
APInt GreatestCommonDivisor(APInt A, APInt B)
Compute GCD of two unsigned APInt values.
static APInt getSignedMaxValue(unsigned numBits)
Gets maximum signed value of APInt for a specific bit width.
This is the base class for unary cast operator classes.
unsigned getBitWidth() const
Return the number of bits in the APInt.
bool isConsistent() const override
isConsistent - Returns true if this dependence is consistent (occurs every time the source and destin...
static const SCEVConstant * getConstantPart(const SCEV *Expr)
PreservedAnalysisChecker getChecker() const
Build a checker for this PreservedAnalyses and the specified analysis type.
static GCMetadataPrinterRegistry::Add< OcamlGCMetadataPrinter > Y("ocaml", "ocaml 3.10-compatible collector")
AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB)
The main low level interface to the alias analysis implementation.
const Value * getLoadStorePointerOperand(const Value *V)
A helper function that returns the pointer operand of a load or store instruction.
#define INITIALIZE_PASS_DEPENDENCY(depName)
void getAnalysisUsage(AnalysisUsage &) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
inst_iterator inst_begin(Function *F)
const Loop * getLoop() const
bool isPeelLast(unsigned Level) const override
isPeelLast - Returns true if peeling the last iteration from this loop will break this dependence...
static AnalysisKey * ID()
Returns an opaque, unique ID for this analysis type.
virtual bool isScalar(unsigned Level) const
isScalar - Returns true if a particular level is scalar; that is, if no subscript in the source or de...
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Direction
An enum for the direction of the loop.
Analysis pass that exposes the LoopInfo for a function.
bool isFlow() const
isFlow - Returns true if this is a flow (aka true) dependence.
This node represents multiplication of some number of SCEVs.
const APInt & getAPInt() const
bool isIdentifiedObject(const Value *V)
Return true if this pointer refers to a distinct and identifiable object.
INITIALIZE_PASS_BEGIN(DependenceAnalysisWrapperPass, "da", "Dependence Analysis", true, true) INITIALIZE_PASS_END(DependenceAnalysisWrapperPass
This node represents a polynomial recurrence on the trip count of the specified loop.
iterator_range< const_set_bits_iterator > set_bits() const
Instruction * getSrc() const
getSrc - Returns the source instruction for this dependence.
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory)...
static APInt ceilingOfQuotient(const APInt &A, const APInt &B)
An instruction for storing to memory.
unsigned getLevels() const override
getLevels - Returns the number of common loops surrounding the source and destination of the dependen...
bool isKnownNonNegative(const Value *V, const DataLayout &DL, unsigned Depth=0, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, bool UseInstrInfo=true)
Returns true if the give value is known to be non-negative.
bool isLoopIndependent() const override
isLoopIndependent - Returns true if this is a loop-independent dependence.
const SCEV * getStepRecurrence(ScalarEvolution &SE) const
Constructs and returns the recurrence indicating how much this expression steps by.
unsigned getBitWidth() const
Get the number of bits in this IntegerType.
bool isOutput() const
isOutput - Returns true if this is an output dependence.
AliasResult
The possible results of an alias query.
unsigned getDirection(unsigned Level) const override
getDirection - Returns the direction associated with a particular level.
static MemoryLocation get(const LoadInst *LI)
Return a location with information about the memory reference by the given instruction.
This means that we are dealing with an entirely unknown SCEV value, and only represent it as its LLVM...
initializer< Ty > init(const Ty &Val)
std::unique_ptr< Dependence > depends(Instruction *Src, Instruction *Dst, bool PossiblyLoopIndependent)
depends - Tests for a dependence between the Src and Dst instructions.
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
A set of analyses that are preserved following a run of a transformation pass.
* if(!EatIfPresent(lltok::kw_thread_local)) return false
ParseOptionalThreadLocal := /*empty.
LLVM Basic Block Representation.
The instances of the Type class are immutable: once they are created, they are never changed...
This is an important base class in LLVM.
static bool isLoadOrStore(const Instruction *I)
A manager for alias analyses.
bool isConfused() const override
isConfused - Returns true if this dependence is confused (the compiler understands nothing and makes ...
bool isSplitable(unsigned Level) const override
isSplitable - Returns true if splitting the loop will break the dependence.
Represent the analysis usage information of a pass.
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
FunctionPass class - This class is used to implement most global optimizations.
bool isAffine() const
Return true if this represents an expression A + B*x where A and B are loop invariant values...
bool isPeelFirst(unsigned Level) const override
isPeelFirst - Returns true if peeling the first iteration from this loop will break this dependence...
const SCEV * getStart() const
Class to represent integer types.
static APInt minAPInt(APInt A, APInt B)
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Value * GetUnderlyingObject(Value *V, const DataLayout &DL, unsigned MaxLookup=6)
This method strips off any GEP address adjustments and pointer casts from the specified value...
INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false) RegBankSelect
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
The two locations may or may not alias. This is the least precise result.
const Value * Ptr
The address of the start of the location.
Representation for a specific memory location.
The two locations precisely alias each other.
static bool findGCD(unsigned Bits, const APInt &AM, const APInt &BM, const APInt &Delta, APInt &G, APInt &X, APInt &Y)
auto size(R &&Range, typename std::enable_if< std::is_same< typename std::iterator_traits< decltype(Range.begin())>::iterator_category, std::random_access_iterator_tag >::value, void >::type *=nullptr) -> decltype(std::distance(Range.begin(), Range.end()))
Get the size of a range.
Type * getType() const
Return the LLVM type of this SCEV expression.
static void dumpExampleDependence(raw_ostream &OS, DependenceInfo *DA)
static APInt floorOfQuotient(const APInt &A, const APInt &B)
void print(raw_ostream &, const Module *=nullptr) const override
print - Print out the internal state of the pass.
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small...
Module.h This file contains the declarations for the Module class.
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
int find_next(unsigned Prev) const
Returns the index of the next set bit following the "Prev" bit.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Class for arbitrary precision integers.
This node represents an addition of some number of SCEVs.
FullDependence(Instruction *Src, Instruction *Dst, bool LoopIndependent, unsigned Levels)
void setPreservesAll()
Set by analyses that do not transform their input at all.
PreservedAnalyses run(Function &F, FunctionAnalysisManager &FAM)
static void propagate(InstantiatedValue From, InstantiatedValue To, MatchState State, ReachabilitySet &ReachSet, std::vector< WorkListItem > &WorkList)
bool isScalar(unsigned Level) const override
isScalar - Returns true if a particular level is scalar; that is, if no subscript in the source or de...
Analysis pass that exposes the ScalarEvolution for a function.
Function * getFunction() const
bool isAnti() const
isAnti - Returns true if this is an anti dependence.
LoopT * getParentLoop() const
static bool isZero(Value *V, const DataLayout &DL, DominatorTree *DT, AssumptionCache *AC)
AAMDNodes AATags
The metadata nodes which describes the aliasing of the location (each member is null if that kind of ...
This class represents an analyzed expression in the program.
Represents a single loop in the control flow graph.
virtual bool isSplitable(unsigned Level) const
isSplitable - Returns true if splitting this loop will break the dependence.
APInt srem(const APInt &RHS) const
Function for signed remainder operation.
StringRef getName() const
Return a constant reference to the value's name.
bool mayReadFromMemory() const
Return true if this instruction may read memory.
LLVM_NODISCARD std::enable_if<!is_simple_type< Y >::value, typename cast_retty< X, const Y >::ret_type >::type dyn_cast(const Y &Val)
FullDependence - This class represents a dependence between two memory references in a function...
static bool isRemainderZero(const SCEVConstant *Dividend, const SCEVConstant *Divisor)
AnalysisUsage & addRequiredTransitive()
Dependence::DVEntry - Each level in the distance/direction vector has a direction (or perhaps a union...
Instruction * getDst() const
getDst - Returns the destination instruction for this dependence.
static APInt maxAPInt(APInt A, APInt B)
API to communicate dependencies between analyses during invalidation.
bool isInput() const
isInput - Returns true if this is an input dependence.
Result run(Function &F, FunctionAnalysisManager &FAM)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This templated class represents "all analyses that operate over <a particular IR unit>" (e...
static APInt getSignedMinValue(unsigned numBits)
Gets minimum signed value of APInt for a specific bit width.
bool isOne() const
Return true if the expression is a constant one.
LLVM Value Representation.
bool invalidate(Function &F, const PreservedAnalyses &PA, FunctionAnalysisManager::Invalidator &Inv)
Handle transitive invalidation when the cached analysis results go away.
bool any() const
Returns true if any bit is set.
This class implements an extremely fast bulk output stream that can only output to a stream...
The legacy pass manager's analysis pass to compute loop information.
void releaseMemory() override
releaseMemory() - This member can be implemented by a pass if it wants to be able to release its memo...
inst_iterator inst_end(Function *F)
A container for analyses that lazily runs them and caches their results.
static APInt getNullValue(unsigned numBits)
Get the '0' value.
A wrapper pass to provide the legacy pass manager access to a suitably prepared AAResults object...
DependenceInfo & getDI() const
The two locations alias, but only due to a partial overlap.
Dependence - This class represents a dependence between two memory memory references in a function...
NoWrapFlags getNoWrapFlags(NoWrapFlags Mask=NoWrapMask) const
A special type used by analysis passes to provide an address that identifies that particular analysis...
static cl::opt< bool > DisableDelinearizationChecks("da-disable-delinearization-checks", cl::init(false), cl::Hidden, cl::ZeroOrMore, cl::desc("Disable checks that try to statically verify validity of " "delinearized subscripts. Enabling this option may result in incorrect " "dependence vectors for languages that allow the subscript of one " "dimension to underflow or overflow into another dimension."))
size_type count() const
Returns the number of bits which are set.
const BasicBlock * getParent() const
This class represents a constant integer value.