70#define DEBUG_TYPE "da"
76STATISTIC(SeparableSubscriptPairs,
"Separable subscript pairs");
77STATISTIC(CoupledSubscriptPairs,
"Coupled subscript pairs");
78STATISTIC(NonlinearSubscriptPairs,
"Nonlinear subscript pairs");
81STATISTIC(StrongSIVapplications,
"Strong SIV applications");
82STATISTIC(StrongSIVsuccesses,
"Strong SIV successes");
83STATISTIC(StrongSIVindependence,
"Strong SIV independence");
84STATISTIC(WeakCrossingSIVapplications,
"Weak-Crossing SIV applications");
85STATISTIC(WeakCrossingSIVsuccesses,
"Weak-Crossing SIV successes");
86STATISTIC(WeakCrossingSIVindependence,
"Weak-Crossing SIV independence");
87STATISTIC(ExactSIVapplications,
"Exact SIV applications");
89STATISTIC(ExactSIVindependence,
"Exact SIV independence");
90STATISTIC(WeakZeroSIVapplications,
"Weak-Zero SIV applications");
91STATISTIC(WeakZeroSIVsuccesses,
"Weak-Zero SIV successes");
92STATISTIC(WeakZeroSIVindependence,
"Weak-Zero SIV independence");
93STATISTIC(ExactRDIVapplications,
"Exact RDIV applications");
94STATISTIC(ExactRDIVindependence,
"Exact RDIV independence");
95STATISTIC(SymbolicRDIVapplications,
"Symbolic RDIV applications");
96STATISTIC(SymbolicRDIVindependence,
"Symbolic RDIV independence");
104STATISTIC(BanerjeeApplications,
"Banerjee applications");
105STATISTIC(BanerjeeIndependence,
"Banerjee independence");
110 cl::desc(
"Try to delinearize array references."));
112 "da-disable-delinearization-checks",
cl::Hidden,
114 "Disable checks that try to statically verify validity of "
115 "delinearized subscripts. Enabling this option may result in incorrect "
116 "dependence vectors for languages that allow the subscript of one "
117 "dimension to underflow or overflow into another dimension."));
121 cl::desc(
"Maximum depth allowed for the recursive algorithm used to "
122 "explore MIV direction vectors."));
138 "Dependence Analysis",
true,
true)
157 auto &AA = getAnalysis<AAResultsWrapperPass>().getAAResults();
158 auto &SE = getAnalysis<ScalarEvolutionWrapperPass>().getSE();
159 auto &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
181 auto *
F = DA->getFunction();
184 if (SrcI->mayReadOrWriteMemory()) {
186 DstI != DstE; ++DstI) {
187 if (DstI->mayReadOrWriteMemory()) {
188 OS <<
"Src:" << *SrcI <<
" --> Dst:" << *DstI <<
"\n";
189 OS <<
" da analyze - ";
190 if (
auto D = DA->depends(&*SrcI, &*DstI,
true)) {
192 if (NormalizeResults &&
D->normalize(&SE))
193 OS <<
"normalized - ";
195 for (
unsigned Level = 1; Level <=
D->getLevels(); Level++) {
196 if (
D->isSplitable(Level)) {
197 OS <<
" da analyze - split level = " << Level;
198 OS <<
", iteration = " << *DA->getSplitIteration(*
D, Level);
214 getAnalysis<ScalarEvolutionWrapperPass>().getSE(),
false);
219 OS <<
"'Dependence Analysis' for function '" <<
F.getName() <<
"':\n";
266 bool PossiblyLoopIndependent,
267 unsigned CommonLevels)
268 :
Dependence(Source, Destination), Levels(CommonLevels),
269 LoopIndependent(PossiblyLoopIndependent) {
272 DV = std::make_unique<DVEntry[]>(CommonLevels);
291 for (
unsigned Level = 1; Level <= Levels; ++Level) {
292 unsigned char Direction = DV[Level - 1].Direction;
307 LLVM_DEBUG(
dbgs() <<
"Before normalizing negative direction vectors:\n";
310 for (
unsigned Level = 1; Level <= Levels; ++Level) {
311 unsigned char Direction = DV[Level - 1].Direction;
319 DV[Level - 1].Direction = RevDirection;
321 if (DV[Level - 1].Distance !=
nullptr)
322 DV[Level - 1].Distance =
326 LLVM_DEBUG(
dbgs() <<
"After normalizing negative direction vectors:\n";
335 assert(0 < Level && Level <= Levels &&
"Level out of range");
336 return DV[Level - 1].Direction;
342 assert(0 < Level && Level <= Levels &&
"Level out of range");
343 return DV[Level - 1].Distance;
351 assert(0 < Level && Level <= Levels &&
"Level out of range");
352 return DV[Level - 1].Scalar;
359 assert(0 < Level && Level <= Levels &&
"Level out of range");
360 return DV[Level - 1].PeelFirst;
367 assert(0 < Level && Level <= Levels &&
"Level out of range");
368 return DV[Level - 1].PeelLast;
374 assert(0 < Level && Level <= Levels &&
"Level out of range");
375 return DV[Level - 1].Splitable;
384const SCEV *DependenceInfo::Constraint::getX()
const {
385 assert(Kind == Point &&
"Kind should be Point");
392const SCEV *DependenceInfo::Constraint::getY()
const {
393 assert(Kind == Point &&
"Kind should be Point");
400const SCEV *DependenceInfo::Constraint::getA()
const {
401 assert((Kind == Line || Kind == Distance) &&
402 "Kind should be Line (or Distance)");
409const SCEV *DependenceInfo::Constraint::getB()
const {
410 assert((Kind == Line || Kind == Distance) &&
411 "Kind should be Line (or Distance)");
418const SCEV *DependenceInfo::Constraint::getC()
const {
419 assert((Kind == Line || Kind == Distance) &&
420 "Kind should be Line (or Distance)");
427const SCEV *DependenceInfo::Constraint::getD()
const {
428 assert(Kind == Distance &&
"Kind should be Distance");
429 return SE->getNegativeSCEV(
C);
434const Loop *DependenceInfo::Constraint::getAssociatedLoop()
const {
435 assert((Kind == Distance || Kind == Line || Kind == Point) &&
436 "Kind should be Distance, Line, or Point");
437 return AssociatedLoop;
440void DependenceInfo::Constraint::setPoint(
const SCEV *
X,
const SCEV *
Y,
441 const Loop *CurLoop) {
445 AssociatedLoop = CurLoop;
448void DependenceInfo::Constraint::setLine(
const SCEV *AA,
const SCEV *BB,
454 AssociatedLoop = CurLoop;
457void DependenceInfo::Constraint::setDistance(
const SCEV *
D,
458 const Loop *CurLoop) {
460 A = SE->getOne(
D->getType());
461 B = SE->getNegativeSCEV(
A);
462 C = SE->getNegativeSCEV(
D);
463 AssociatedLoop = CurLoop;
466void DependenceInfo::Constraint::setEmpty() {
Kind =
Empty; }
473#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
481 OS <<
" Point is <" << *getX() <<
", " << *getY() <<
">\n";
482 else if (isDistance())
483 OS <<
" Distance is " << *getD() <<
484 " (" << *getA() <<
"*X + " << *getB() <<
"*Y = " << *getC() <<
")\n";
486 OS <<
" Line is " << *getA() <<
"*X + " <<
487 *getB() <<
"*Y = " << *getC() <<
"\n";
501bool DependenceInfo::intersectConstraints(Constraint *
X,
const Constraint *
Y) {
506 assert(!
Y->isPoint() &&
"Y must not be a Point");
520 if (
X->isDistance() &&
Y->isDistance()) {
531 if (isa<SCEVConstant>(
Y->getD())) {
544 assert(!(
X->isPoint() &&
Y->isPoint()) &&
545 "We shouldn't ever see X->isPoint() && Y->isPoint()");
547 if (
X->isLine() &&
Y->isLine()) {
582 if (!C1B2_C2B1 || !C1A2_C2A1 ||
583 !A1B2_A2B1 || !A2B1_A1B2)
599 if (Xr != 0 || Yr != 0) {
605 if (Xq.
slt(0) || Yq.
slt(0)) {
611 collectConstantUpperBound(
X->getAssociatedLoop(), Prod1->
getType())) {
612 const APInt &UpperBound = CUB->getAPInt();
614 if (Xq.
sgt(UpperBound) || Yq.
sgt(UpperBound)) {
622 X->getAssociatedLoop());
630 assert(!(
X->isLine() &&
Y->isPoint()) &&
"This case should never occur");
632 if (
X->isPoint() &&
Y->isLine()) {
657 bool Splitable =
false;
673 for (
unsigned II = 1;
II <= Levels; ++
II) {
751 if (
const LoadInst *LI = dyn_cast<LoadInst>(
I))
752 return LI->isUnordered();
753 else if (
const StoreInst *SI = dyn_cast<StoreInst>(
I))
754 return SI->isUnordered();
809void DependenceInfo::establishNestingLevels(
const Instruction *Src,
811 const BasicBlock *SrcBlock = Src->getParent();
812 const BasicBlock *DstBlock = Dst->getParent();
817 SrcLevels = SrcLevel;
818 MaxLevels = SrcLevel + DstLevel;
819 while (SrcLevel > DstLevel) {
823 while (DstLevel > SrcLevel) {
827 while (SrcLoop != DstLoop) {
832 CommonLevels = SrcLevel;
833 MaxLevels -= CommonLevels;
839unsigned DependenceInfo::mapSrcLoop(
const Loop *SrcLoop)
const {
846unsigned DependenceInfo::mapDstLoop(
const Loop *DstLoop)
const {
848 if (
D > CommonLevels)
851 return D - CommonLevels + SrcLevels;
880 unsigned Level =
LoopNest->getLoopDepth();
889 unsigned widestWidthSeen = 0;
894 for (Subscript *Pair : Pairs) {
895 const SCEV *Src = Pair->Src;
896 const SCEV *Dst = Pair->Dst;
897 IntegerType *SrcTy = dyn_cast<IntegerType>(Src->getType());
898 IntegerType *DstTy = dyn_cast<IntegerType>(Dst->getType());
899 if (SrcTy ==
nullptr || DstTy ==
nullptr) {
900 assert(SrcTy == DstTy &&
"This function only unify integer types and "
901 "expect Src and Dst share the same type "
916 assert(widestWidthSeen > 0);
919 for (Subscript *Pair : Pairs) {
920 const SCEV *Src = Pair->Src;
921 const SCEV *Dst = Pair->Dst;
922 IntegerType *SrcTy = dyn_cast<IntegerType>(Src->getType());
923 IntegerType *DstTy = dyn_cast<IntegerType>(Dst->getType());
924 if (SrcTy ==
nullptr || DstTy ==
nullptr) {
925 assert(SrcTy == DstTy &&
"This function only unify integer types and "
926 "expect Src and Dst share the same type "
944void DependenceInfo::removeMatchingExtensions(Subscript *Pair) {
945 const SCEV *Src = Pair->Src;
946 const SCEV *Dst = Pair->Dst;
947 if ((isa<SCEVZeroExtendExpr>(Src) && isa<SCEVZeroExtendExpr>(Dst)) ||
948 (isa<SCEVSignExtendExpr>(Src) && isa<SCEVSignExtendExpr>(Dst))) {
954 Pair->Src = SrcCastOp;
955 Pair->Dst = DstCastOp;
966 return isLoopInvariant(Expr,
LoopNest);
974 while (L && AddRec->
getLoop() != L)
975 L =
L->getParentLoop();
982 if (!isa<SCEVCouldNotCompute>(UB)) {
989 if (!isLoopInvariant(Step,
LoopNest))
1000bool DependenceInfo::checkSrcSubscript(
const SCEV *Src,
const Loop *
LoopNest,
1007bool DependenceInfo::checkDstSubscript(
const SCEV *Dst,
const Loop *
LoopNest,
1016DependenceInfo::Subscript::ClassificationKind
1017DependenceInfo::classifyPair(
const SCEV *Src,
const Loop *SrcLoopNest,
1018 const SCEV *Dst,
const Loop *DstLoopNest,
1022 if (!checkSrcSubscript(Src, SrcLoopNest, SrcLoops))
1023 return Subscript::NonLinear;
1024 if (!checkDstSubscript(Dst, DstLoopNest, DstLoops))
1025 return Subscript::NonLinear;
1028 unsigned N =
Loops.count();
1030 return Subscript::ZIV;
1032 return Subscript::SIV;
1033 if (
N == 2 && (SrcLoops.count() == 0 ||
1034 DstLoops.count() == 0 ||
1035 (SrcLoops.count() == 1 && DstLoops.count() == 1)))
1036 return Subscript::RDIV;
1037 return Subscript::MIV;
1052 const SCEV *
Y)
const {
1055 if ((isa<SCEVSignExtendExpr>(
X) &&
1056 isa<SCEVSignExtendExpr>(
Y)) ||
1057 (isa<SCEVZeroExtendExpr>(
X) &&
1058 isa<SCEVZeroExtendExpr>(
Y))) {
1098bool DependenceInfo::isKnownLessThan(
const SCEV *S,
const SCEV *
Size)
const {
1100 auto *SType = dyn_cast<IntegerType>(S->
getType());
1101 auto *SizeType = dyn_cast<IntegerType>(
Size->getType());
1102 if (!SType || !SizeType)
1105 (SType->getBitWidth() >= SizeType->getBitWidth()) ? SType : SizeType;
1111 if (
const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(Bound)) {
1114 if (!isa<SCEVCouldNotCompute>(BECount)) {
1123 const SCEV *LimitedBound =
1128bool DependenceInfo::isKnownNonNegative(
const SCEV *S,
const Value *
Ptr)
const {
1129 bool Inbounds =
false;
1130 if (
auto *SrcGEP = dyn_cast<GetElementPtrInst>(
Ptr))
1131 Inbounds = SrcGEP->isInBounds();
1133 if (
const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(S)) {
1154const SCEV *DependenceInfo::collectUpperBound(
const Loop *L,
Type *
T)
const {
1165const SCEVConstant *DependenceInfo::collectConstantUpperBound(
const Loop *L,
1167 if (
const SCEV *UB = collectUpperBound(L,
T))
1168 return dyn_cast<SCEVConstant>(UB);
1183bool DependenceInfo::testZIV(
const SCEV *Src,
const SCEV *Dst,
1198 Result.Consistent =
false;
1230bool DependenceInfo::strongSIVtest(
const SCEV *Coeff,
const SCEV *SrcConst,
1231 const SCEV *DstConst,
const Loop *CurLoop,
1233 Constraint &NewConstraint)
const {
1241 ++StrongSIVapplications;
1242 assert(0 < Level && Level <= CommonLevels &&
"level out of range");
1250 if (
const SCEV *UpperBound = collectUpperBound(CurLoop, Delta->
getType())) {
1253 const SCEV *AbsDelta =
1255 const SCEV *AbsCoeff =
1260 ++StrongSIVindependence;
1261 ++StrongSIVsuccesses;
1267 if (isa<SCEVConstant>(Delta) && isa<SCEVConstant>(Coeff)) {
1268 APInt ConstDelta = cast<SCEVConstant>(Delta)->getAPInt();
1269 APInt ConstCoeff = cast<SCEVConstant>(Coeff)->getAPInt();
1270 APInt Distance = ConstDelta;
1271 APInt Remainder = ConstDelta;
1276 if (Remainder != 0) {
1278 ++StrongSIVindependence;
1279 ++StrongSIVsuccesses;
1283 NewConstraint.setDistance(SE->
getConstant(Distance), CurLoop);
1284 if (Distance.
sgt(0))
1286 else if (Distance.
slt(0))
1290 ++StrongSIVsuccesses;
1292 else if (Delta->
isZero()) {
1294 Result.DV[Level].Distance = Delta;
1295 NewConstraint.setDistance(Delta, CurLoop);
1297 ++StrongSIVsuccesses;
1300 if (Coeff->
isOne()) {
1302 Result.DV[Level].Distance = Delta;
1303 NewConstraint.setDistance(Delta, CurLoop);
1306 Result.Consistent =
false;
1307 NewConstraint.setLine(Coeff,
1322 if ((DeltaMaybePositive && CoeffMaybePositive) ||
1323 (DeltaMaybeNegative && CoeffMaybeNegative))
1327 if ((DeltaMaybeNegative && CoeffMaybePositive) ||
1328 (DeltaMaybePositive && CoeffMaybeNegative))
1330 if (NewDirection <
Result.DV[Level].Direction)
1331 ++StrongSIVsuccesses;
1332 Result.DV[Level].Direction &= NewDirection;
1366bool DependenceInfo::weakCrossingSIVtest(
1367 const SCEV *Coeff,
const SCEV *SrcConst,
const SCEV *DstConst,
1369 Constraint &NewConstraint,
const SCEV *&SplitIter)
const {
1374 ++WeakCrossingSIVapplications;
1375 assert(0 < Level && Level <= CommonLevels &&
"Level out of range");
1377 Result.Consistent =
false;
1380 NewConstraint.setLine(Coeff, Coeff, Delta, CurLoop);
1384 ++WeakCrossingSIVsuccesses;
1385 if (!
Result.DV[Level].Direction) {
1386 ++WeakCrossingSIVindependence;
1389 Result.DV[Level].Distance = Delta;
1392 const SCEVConstant *ConstCoeff = dyn_cast<SCEVConstant>(Coeff);
1396 Result.DV[Level].Splitable =
true;
1400 "dynamic cast of negative of ConstCoeff should yield constant");
1411 const SCEVConstant *ConstDelta = dyn_cast<SCEVConstant>(Delta);
1421 ++WeakCrossingSIVindependence;
1422 ++WeakCrossingSIVsuccesses;
1428 if (
const SCEV *UpperBound = collectUpperBound(CurLoop, Delta->
getType())) {
1436 ++WeakCrossingSIVindependence;
1437 ++WeakCrossingSIVsuccesses;
1444 ++WeakCrossingSIVsuccesses;
1445 if (!
Result.DV[Level].Direction) {
1446 ++WeakCrossingSIVindependence;
1449 Result.DV[Level].Splitable =
false;
1458 APInt Distance = APDelta;
1459 APInt Remainder = APDelta;
1462 if (Remainder != 0) {
1464 ++WeakCrossingSIVindependence;
1465 ++WeakCrossingSIVsuccesses;
1472 Remainder = Distance.
srem(Two);
1474 if (Remainder != 0) {
1477 ++WeakCrossingSIVsuccesses;
1495 APInt A0(Bits, 1,
true), A1(Bits, 0,
true);
1496 APInt B0(Bits, 0,
true), B1(Bits, 1,
true);
1503 APInt A2 = A0 - Q*A1; A0 = A1; A1 = A2;
1504 APInt B2 = B0 - Q*B1; B0 = B1; B1 = B2;
1510 X = AM.
slt(0) ? -A1 : A1;
1511 Y = BM.
slt(0) ? B1 : -B1;
1527 if ((
A.sgt(0) &&
B.sgt(0)) ||
1528 (
A.slt(0) &&
B.slt(0)))
1540 if ((
A.sgt(0) &&
B.sgt(0)) ||
1541 (
A.slt(0) &&
B.slt(0)))
1566bool DependenceInfo::exactSIVtest(
const SCEV *SrcCoeff,
const SCEV *DstCoeff,
1567 const SCEV *SrcConst,
const SCEV *DstConst,
1568 const Loop *CurLoop,
unsigned Level,
1570 Constraint &NewConstraint)
const {
1572 LLVM_DEBUG(
dbgs() <<
"\t SrcCoeff = " << *SrcCoeff <<
" = AM\n");
1573 LLVM_DEBUG(
dbgs() <<
"\t DstCoeff = " << *DstCoeff <<
" = BM\n");
1576 ++ExactSIVapplications;
1577 assert(0 < Level && Level <= CommonLevels &&
"Level out of range");
1579 Result.Consistent =
false;
1584 const SCEVConstant *ConstDelta = dyn_cast<SCEVConstant>(Delta);
1585 const SCEVConstant *ConstSrcCoeff = dyn_cast<SCEVConstant>(SrcCoeff);
1586 const SCEVConstant *ConstDstCoeff = dyn_cast<SCEVConstant>(DstCoeff);
1587 if (!ConstDelta || !ConstSrcCoeff || !ConstDstCoeff)
1598 ++ExactSIVindependence;
1599 ++ExactSIVsuccesses;
1606 APInt UM(Bits, 1,
true);
1607 bool UMValid =
false;
1610 collectConstantUpperBound(CurLoop, Delta->
getType())) {
1611 UM = CUB->getAPInt();
1675 ++ExactSIVindependence;
1676 ++ExactSIVsuccesses;
1682 APInt LowerDistance, UpperDistance;
1684 LowerDistance = (TY - TX) + (TA - TB) * TL;
1685 UpperDistance = (TY - TX) + (TA - TB) * TU;
1687 LowerDistance = (TY - TX) + (TA - TB) * TU;
1688 UpperDistance = (TY - TX) + (TA - TB) * TL;
1691 LLVM_DEBUG(
dbgs() <<
"\t LowerDistance = " << LowerDistance <<
"\n");
1692 LLVM_DEBUG(
dbgs() <<
"\t UpperDistance = " << UpperDistance <<
"\n");
1695 if (LowerDistance.
sle(Zero) && UpperDistance.
sge(Zero)) {
1697 ++ExactSIVsuccesses;
1699 if (LowerDistance.
slt(0)) {
1701 ++ExactSIVsuccesses;
1703 if (UpperDistance.
sgt(0)) {
1705 ++ExactSIVsuccesses;
1709 Result.DV[Level].Direction &= NewDirection;
1711 ++ExactSIVindependence;
1724 return ConstDividend.
srem(ConstDivisor) == 0;
1759bool DependenceInfo::weakZeroSrcSIVtest(
const SCEV *DstCoeff,
1760 const SCEV *SrcConst,
1761 const SCEV *DstConst,
1762 const Loop *CurLoop,
unsigned Level,
1764 Constraint &NewConstraint)
const {
1772 ++WeakZeroSIVapplications;
1773 assert(0 < Level && Level <= MaxLevels &&
"Level out of range");
1775 Result.Consistent =
false;
1777 NewConstraint.setLine(SE->
getZero(Delta->
getType()), DstCoeff, Delta,
1781 if (Level < CommonLevels) {
1783 Result.DV[Level].PeelFirst =
true;
1784 ++WeakZeroSIVsuccesses;
1788 const SCEVConstant *ConstCoeff = dyn_cast<SCEVConstant>(DstCoeff);
1791 const SCEV *AbsCoeff =
1794 const SCEV *NewDelta =
1799 if (
const SCEV *UpperBound = collectUpperBound(CurLoop, Delta->
getType())) {
1803 ++WeakZeroSIVindependence;
1804 ++WeakZeroSIVsuccesses;
1809 if (Level < CommonLevels) {
1811 Result.DV[Level].PeelLast =
true;
1812 ++WeakZeroSIVsuccesses;
1822 ++WeakZeroSIVindependence;
1823 ++WeakZeroSIVsuccesses;
1828 if (isa<SCEVConstant>(Delta) &&
1830 ++WeakZeroSIVindependence;
1831 ++WeakZeroSIVsuccesses;
1869bool DependenceInfo::weakZeroDstSIVtest(
const SCEV *SrcCoeff,
1870 const SCEV *SrcConst,
1871 const SCEV *DstConst,
1872 const Loop *CurLoop,
unsigned Level,
1874 Constraint &NewConstraint)
const {
1881 ++WeakZeroSIVapplications;
1882 assert(0 < Level && Level <= SrcLevels &&
"Level out of range");
1884 Result.Consistent =
false;
1886 NewConstraint.setLine(SrcCoeff, SE->
getZero(Delta->
getType()), Delta,
1890 if (Level < CommonLevels) {
1892 Result.DV[Level].PeelFirst =
true;
1893 ++WeakZeroSIVsuccesses;
1897 const SCEVConstant *ConstCoeff = dyn_cast<SCEVConstant>(SrcCoeff);
1900 const SCEV *AbsCoeff =
1903 const SCEV *NewDelta =
1908 if (
const SCEV *UpperBound = collectUpperBound(CurLoop, Delta->
getType())) {
1912 ++WeakZeroSIVindependence;
1913 ++WeakZeroSIVsuccesses;
1918 if (Level < CommonLevels) {
1920 Result.DV[Level].PeelLast =
true;
1921 ++WeakZeroSIVsuccesses;
1931 ++WeakZeroSIVindependence;
1932 ++WeakZeroSIVsuccesses;
1937 if (isa<SCEVConstant>(Delta) &&
1939 ++WeakZeroSIVindependence;
1940 ++WeakZeroSIVsuccesses;
1954bool DependenceInfo::exactRDIVtest(
const SCEV *SrcCoeff,
const SCEV *DstCoeff,
1955 const SCEV *SrcConst,
const SCEV *DstConst,
1956 const Loop *SrcLoop,
const Loop *DstLoop,
1959 LLVM_DEBUG(
dbgs() <<
"\t SrcCoeff = " << *SrcCoeff <<
" = AM\n");
1960 LLVM_DEBUG(
dbgs() <<
"\t DstCoeff = " << *DstCoeff <<
" = BM\n");
1963 ++ExactRDIVapplications;
1964 Result.Consistent =
false;
1967 const SCEVConstant *ConstDelta = dyn_cast<SCEVConstant>(Delta);
1968 const SCEVConstant *ConstSrcCoeff = dyn_cast<SCEVConstant>(SrcCoeff);
1969 const SCEVConstant *ConstDstCoeff = dyn_cast<SCEVConstant>(DstCoeff);
1970 if (!ConstDelta || !ConstSrcCoeff || !ConstDstCoeff)
1981 ++ExactRDIVindependence;
1988 APInt SrcUM(Bits, 1,
true);
1989 bool SrcUMvalid =
false;
1992 collectConstantUpperBound(SrcLoop, Delta->
getType())) {
1993 SrcUM = UpperBound->getAPInt();
1998 APInt DstUM(Bits, 1,
true);
1999 bool DstUMvalid =
false;
2002 collectConstantUpperBound(DstLoop, Delta->
getType())) {
2003 DstUM = UpperBound->getAPInt();
2064 ++ExactRDIVindependence;
2111bool DependenceInfo::symbolicRDIVtest(
const SCEV *A1,
const SCEV *A2,
2114 const Loop *Loop2)
const {
2115 ++SymbolicRDIVapplications;
2122 const SCEV *N1 = collectUpperBound(Loop1, A1->
getType());
2123 const SCEV *N2 = collectUpperBound(Loop2, A1->
getType());
2138 ++SymbolicRDIVindependence;
2147 ++SymbolicRDIVindependence;
2159 LLVM_DEBUG(
dbgs() <<
"\t A1*N1 - A2*N2 = " << *A1N1_A2N2 <<
"\n");
2161 ++SymbolicRDIVindependence;
2167 ++SymbolicRDIVindependence;
2180 LLVM_DEBUG(
dbgs() <<
"\t A1*N1 - A2*N2 = " << *A1N1_A2N2 <<
"\n");
2182 ++SymbolicRDIVindependence;
2188 ++SymbolicRDIVindependence;
2199 ++SymbolicRDIVindependence;
2208 ++SymbolicRDIVindependence;
2226bool DependenceInfo::testSIV(
const SCEV *Src,
const SCEV *Dst,
unsigned &Level,
2228 const SCEV *&SplitIter)
const {
2233 if (SrcAddRec && DstAddRec) {
2240 "both loops in SIV should be same");
2241 Level = mapSrcLoop(CurLoop);
2243 if (SrcCoeff == DstCoeff)
2244 disproven = strongSIVtest(SrcCoeff, SrcConst, DstConst, CurLoop,
2245 Level, Result, NewConstraint);
2247 disproven = weakCrossingSIVtest(SrcCoeff, SrcConst, DstConst, CurLoop,
2248 Level, Result, NewConstraint, SplitIter);
2250 disproven = exactSIVtest(SrcCoeff, DstCoeff, SrcConst, DstConst, CurLoop,
2251 Level, Result, NewConstraint);
2253 gcdMIVtest(Src, Dst, Result) ||
2254 symbolicRDIVtest(SrcCoeff, DstCoeff, SrcConst, DstConst, CurLoop, CurLoop);
2259 const SCEV *DstConst = Dst;
2261 Level = mapSrcLoop(CurLoop);
2262 return weakZeroDstSIVtest(SrcCoeff, SrcConst, DstConst, CurLoop,
2263 Level, Result, NewConstraint) ||
2264 gcdMIVtest(Src, Dst, Result);
2269 const SCEV *SrcConst = Src;
2271 Level = mapDstLoop(CurLoop);
2272 return weakZeroSrcSIVtest(DstCoeff, SrcConst, DstConst,
2273 CurLoop, Level, Result, NewConstraint) ||
2274 gcdMIVtest(Src, Dst, Result);
2294bool DependenceInfo::testRDIV(
const SCEV *Src,
const SCEV *Dst,
2302 const SCEV *SrcConst, *DstConst;
2303 const SCEV *SrcCoeff, *DstCoeff;
2304 const Loop *SrcLoop, *DstLoop;
2310 if (SrcAddRec && DstAddRec) {
2313 SrcLoop = SrcAddRec->
getLoop();
2316 DstLoop = DstAddRec->
getLoop();
2318 else if (SrcAddRec) {
2320 dyn_cast<SCEVAddRecExpr>(SrcAddRec->
getStart())) {
2321 SrcConst = tmpAddRec->getStart();
2322 SrcCoeff = tmpAddRec->getStepRecurrence(*SE);
2323 SrcLoop = tmpAddRec->getLoop();
2326 DstLoop = SrcAddRec->
getLoop();
2331 else if (DstAddRec) {
2333 dyn_cast<SCEVAddRecExpr>(DstAddRec->
getStart())) {
2334 DstConst = tmpAddRec->getStart();
2335 DstCoeff = tmpAddRec->getStepRecurrence(*SE);
2336 DstLoop = tmpAddRec->getLoop();
2339 SrcLoop = DstAddRec->
getLoop();
2346 return exactRDIVtest(SrcCoeff, DstCoeff,
2350 gcdMIVtest(Src, Dst, Result) ||
2351 symbolicRDIVtest(SrcCoeff, DstCoeff,
2360bool DependenceInfo::testMIV(
const SCEV *Src,
const SCEV *Dst,
2365 Result.Consistent =
false;
2366 return gcdMIVtest(Src, Dst, Result) ||
2367 banerjeeMIVtest(Src, Dst,
Loops, Result);
2375 if (
const auto *
Constant = dyn_cast<SCEVConstant>(Expr))
2377 else if (
const auto *Product = dyn_cast<SCEVMulExpr>(Expr))
2378 if (
const auto *
Constant = dyn_cast<SCEVConstant>(Product->getOperand(0)))
2402bool DependenceInfo::gcdMIVtest(
const SCEV *Src,
const SCEV *Dst,
2413 const SCEV *Coefficients = Src;
2415 dyn_cast<SCEVAddRecExpr>(Coefficients)) {
2426 const SCEV *SrcConst = Coefficients;
2434 dyn_cast<SCEVAddRecExpr>(Coefficients)) {
2445 const SCEV *DstConst = Coefficients;
2451 if (
const SCEVAddExpr *Sum = dyn_cast<SCEVAddExpr>(Delta)) {
2453 for (
unsigned Op = 0, Ops = Sum->getNumOperands();
Op < Ops;
Op++) {
2454 const SCEV *Operand = Sum->getOperand(
Op);
2455 if (isa<SCEVConstant>(Operand)) {
2457 Constant = cast<SCEVConstant>(Operand);
2459 else if (
const SCEVMulExpr *Product = dyn_cast<SCEVMulExpr>(Operand)) {
2467 ConstOpValue.
abs());
2477 if (ConstDelta == 0)
2481 APInt Remainder = ConstDelta.
srem(RunningGCD);
2482 if (Remainder != 0) {
2501 bool Improved =
false;
2504 dyn_cast<SCEVAddRecExpr>(Coefficients)) {
2507 RunningGCD = ExtraGCD;
2510 const SCEV *Inner = Src;
2511 while (RunningGCD != 1 && isa<SCEVAddRecExpr>(Inner)) {
2512 AddRec = cast<SCEVAddRecExpr>(Inner);
2514 if (CurLoop == AddRec->
getLoop())
2528 while (RunningGCD != 1 && isa<SCEVAddRecExpr>(Inner)) {
2529 AddRec = cast<SCEVAddRecExpr>(Inner);
2531 if (CurLoop == AddRec->
getLoop())
2555 if (RunningGCD != 0) {
2556 Remainder = ConstDelta.
srem(RunningGCD);
2558 if (Remainder != 0) {
2559 unsigned Level = mapSrcLoop(CurLoop);
2605bool DependenceInfo::banerjeeMIVtest(
const SCEV *Src,
const SCEV *Dst,
2609 ++BanerjeeApplications;
2612 CoefficientInfo *
A = collectCoeffInfo(Src,
true, A0);
2615 CoefficientInfo *
B = collectCoeffInfo(Dst,
false, B0);
2616 BoundInfo *Bound =
new BoundInfo[MaxLevels + 1];
2622 for (
unsigned K = 1;
K <= MaxLevels; ++
K) {
2623 Bound[
K].Iterations =
A[
K].Iterations ?
A[
K].Iterations :
B[
K].Iterations;
2626 findBoundsALL(
A,
B, Bound, K);
2641 bool Disproved =
false;
2644 unsigned DepthExpanded = 0;
2645 unsigned NewDeps = exploreDirections(1,
A,
B, Bound,
2646 Loops, DepthExpanded, Delta);
2648 bool Improved =
false;
2649 for (
unsigned K = 1;
K <= CommonLevels; ++
K) {
2651 unsigned Old =
Result.DV[
K - 1].Direction;
2652 Result.DV[
K - 1].Direction = Old & Bound[
K].DirSet;
2653 Improved |= Old !=
Result.DV[
K - 1].Direction;
2654 if (!
Result.DV[K - 1].Direction) {
2662 ++BanerjeeSuccesses;
2665 ++BanerjeeIndependence;
2670 ++BanerjeeIndependence;
2685unsigned DependenceInfo::exploreDirections(
unsigned Level, CoefficientInfo *
A,
2686 CoefficientInfo *
B, BoundInfo *Bound,
2688 unsigned &DepthExpanded,
2689 const SCEV *Delta)
const {
2695 LLVM_DEBUG(
dbgs() <<
"Number of common levels exceeded the threshold. MIV "
2696 "direction exploration is terminated.\n");
2697 for (
unsigned K = 1;
K <= CommonLevels; ++
K)
2703 if (Level > CommonLevels) {
2706 for (
unsigned K = 1;
K <= CommonLevels; ++
K) {
2708 Bound[
K].DirSet |= Bound[
K].Direction;
2733 if (Level > DepthExpanded) {
2734 DepthExpanded = Level;
2736 findBoundsLT(
A,
B, Bound, Level);
2737 findBoundsGT(
A,
B, Bound, Level);
2738 findBoundsEQ(
A,
B, Bound, Level);
2777 unsigned NewDeps = 0;
2781 NewDeps += exploreDirections(Level + 1,
A,
B, Bound,
2782 Loops, DepthExpanded, Delta);
2786 NewDeps += exploreDirections(Level + 1,
A,
B, Bound,
2787 Loops, DepthExpanded, Delta);
2791 NewDeps += exploreDirections(Level + 1,
A,
B, Bound,
2792 Loops, DepthExpanded, Delta);
2798 return exploreDirections(Level + 1,
A,
B, Bound,
Loops, DepthExpanded, Delta);
2803bool DependenceInfo::testBounds(
unsigned char DirKind,
unsigned Level,
2804 BoundInfo *Bound,
const SCEV *Delta)
const {
2805 Bound[Level].Direction = DirKind;
2806 if (
const SCEV *LowerBound = getLowerBound(Bound))
2809 if (
const SCEV *UpperBound = getUpperBound(Bound))
2831void DependenceInfo::findBoundsALL(CoefficientInfo *
A, CoefficientInfo *
B,
2832 BoundInfo *Bound,
unsigned K)
const {
2835 if (Bound[K].Iterations) {
2838 Bound[K].Iterations);
2841 Bound[K].Iterations);
2870void DependenceInfo::findBoundsEQ(CoefficientInfo *
A, CoefficientInfo *
B,
2871 BoundInfo *Bound,
unsigned K)
const {
2874 if (Bound[K].Iterations) {
2876 const SCEV *NegativePart = getNegativePart(Delta);
2878 SE->
getMulExpr(NegativePart, Bound[K].Iterations);
2879 const SCEV *PositivePart = getPositivePart(Delta);
2881 SE->
getMulExpr(PositivePart, Bound[K].Iterations);
2887 const SCEV *NegativePart = getNegativePart(Delta);
2888 if (NegativePart->
isZero())
2890 const SCEV *PositivePart = getPositivePart(Delta);
2891 if (PositivePart->
isZero())
2910void DependenceInfo::findBoundsLT(CoefficientInfo *
A, CoefficientInfo *
B,
2911 BoundInfo *Bound,
unsigned K)
const {
2914 if (Bound[K].Iterations) {
2916 Bound[K].Iterations, SE->
getOne(Bound[K].Iterations->getType()));
2917 const SCEV *NegPart =
2921 const SCEV *PosPart =
2929 const SCEV *NegPart =
2933 const SCEV *PosPart =
2954void DependenceInfo::findBoundsGT(CoefficientInfo *
A, CoefficientInfo *
B,
2955 BoundInfo *Bound,
unsigned K)
const {
2958 if (Bound[K].Iterations) {
2960 Bound[K].Iterations, SE->
getOne(Bound[K].Iterations->getType()));
2961 const SCEV *NegPart =
2965 const SCEV *PosPart =
2984const SCEV *DependenceInfo::getPositivePart(
const SCEV *
X)
const {
2990const SCEV *DependenceInfo::getNegativePart(
const SCEV *
X)
const {
2998DependenceInfo::CoefficientInfo *
2999DependenceInfo::collectCoeffInfo(
const SCEV *Subscript,
bool SrcFlag,
3002 CoefficientInfo *CI =
new CoefficientInfo[MaxLevels + 1];
3003 for (
unsigned K = 1;
K <= MaxLevels; ++
K) {
3005 CI[
K].PosPart =
Zero;
3006 CI[
K].NegPart =
Zero;
3007 CI[
K].Iterations =
nullptr;
3009 while (
const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(Subscript)) {
3011 unsigned K = SrcFlag ? mapSrcLoop(L) : mapDstLoop(
L);
3013 CI[
K].PosPart = getPositivePart(CI[K].Coeff);
3014 CI[
K].NegPart = getNegativePart(CI[K].Coeff);
3015 CI[
K].Iterations = collectUpperBound(L, Subscript->
getType());
3021 for (
unsigned K = 1;
K <= MaxLevels; ++
K) {
3028 if (CI[K].Iterations)
3044const SCEV *DependenceInfo::getLowerBound(BoundInfo *Bound)
const {
3045 const SCEV *Sum = Bound[1].Lower[Bound[1].Direction];
3046 for (
unsigned K = 2; Sum &&
K <= MaxLevels; ++
K) {
3060const SCEV *DependenceInfo::getUpperBound(BoundInfo *Bound)
const {
3061 const SCEV *Sum = Bound[1].Upper[Bound[1].Direction];
3062 for (
unsigned K = 2; Sum &&
K <= MaxLevels; ++
K) {
3081const SCEV *DependenceInfo::findCoefficient(
const SCEV *Expr,
3082 const Loop *TargetLoop)
const {
3086 if (AddRec->
getLoop() == TargetLoop)
3088 return findCoefficient(AddRec->
getStart(), TargetLoop);
3097const SCEV *DependenceInfo::zeroCoefficient(
const SCEV *Expr,
3098 const Loop *TargetLoop)
const {
3102 if (AddRec->
getLoop() == TargetLoop)
3116const SCEV *DependenceInfo::addToCoefficient(
const SCEV *Expr,
3117 const Loop *TargetLoop,
3125 if (AddRec->
getLoop() == TargetLoop) {
3153bool DependenceInfo::propagate(
const SCEV *&Src,
const SCEV *&Dst,
3158 for (
unsigned LI :
Loops.set_bits()) {
3161 if (Constraints[LI].isDistance())
3162 Result |= propagateDistance(Src, Dst, Constraints[LI], Consistent);
3163 else if (Constraints[LI].isLine())
3164 Result |= propagateLine(Src, Dst, Constraints[LI], Consistent);
3165 else if (Constraints[LI].isPoint())
3166 Result |= propagatePoint(Src, Dst, Constraints[LI]);
3177bool DependenceInfo::propagateDistance(
const SCEV *&Src,
const SCEV *&Dst,
3178 Constraint &CurConstraint,
3180 const Loop *CurLoop = CurConstraint.getAssociatedLoop();
3182 const SCEV *A_K = findCoefficient(Src, CurLoop);
3187 Src = zeroCoefficient(Src, CurLoop);
3192 if (!findCoefficient(Dst, CurLoop)->
isZero())
3203bool DependenceInfo::propagateLine(
const SCEV *&Src,
const SCEV *&Dst,
3204 Constraint &CurConstraint,
3206 const Loop *CurLoop = CurConstraint.getAssociatedLoop();
3207 const SCEV *
A = CurConstraint.getA();
3208 const SCEV *
B = CurConstraint.getB();
3209 const SCEV *
C = CurConstraint.getC();
3217 if (!Bconst || !Cconst)
return false;
3221 assert(Charlie.
srem(Beta) == 0 &&
"C should be evenly divisible by B");
3222 const SCEV *AP_K = findCoefficient(Dst, CurLoop);
3225 Dst = zeroCoefficient(Dst, CurLoop);
3226 if (!findCoefficient(Src, CurLoop)->
isZero())
3229 else if (
B->isZero()) {
3232 if (!Aconst || !Cconst)
return false;
3236 assert(Charlie.
srem(Alpha) == 0 &&
"C should be evenly divisible by A");
3237 const SCEV *A_K = findCoefficient(Src, CurLoop);
3239 Src = zeroCoefficient(Src, CurLoop);
3240 if (!findCoefficient(Dst, CurLoop)->
isZero())
3246 if (!Aconst || !Cconst)
return false;
3250 assert(Charlie.
srem(Alpha) == 0 &&
"C should be evenly divisible by A");
3251 const SCEV *A_K = findCoefficient(Src, CurLoop);
3253 Src = zeroCoefficient(Src, CurLoop);
3254 Dst = addToCoefficient(Dst, CurLoop, A_K);
3255 if (!findCoefficient(Dst, CurLoop)->
isZero())
3260 const SCEV *A_K = findCoefficient(Src, CurLoop);
3264 Src = zeroCoefficient(Src, CurLoop);
3265 Dst = addToCoefficient(Dst, CurLoop, SE->
getMulExpr(A_K,
B));
3266 if (!findCoefficient(Dst, CurLoop)->
isZero())
3278bool DependenceInfo::propagatePoint(
const SCEV *&Src,
const SCEV *&Dst,
3279 Constraint &CurConstraint) {
3280 const Loop *CurLoop = CurConstraint.getAssociatedLoop();
3281 const SCEV *A_K = findCoefficient(Src, CurLoop);
3282 const SCEV *AP_K = findCoefficient(Dst, CurLoop);
3287 Src = zeroCoefficient(Src, CurLoop);
3290 Dst = zeroCoefficient(Dst, CurLoop);
3298 const Constraint &CurConstraint)
const {
3301 if (CurConstraint.isAny())
3303 else if (CurConstraint.isDistance()) {
3305 Level.Scalar =
false;
3306 Level.Distance = CurConstraint.getD();
3314 Level.Direction &= NewDirection;
3316 else if (CurConstraint.isLine()) {
3317 Level.Scalar =
false;
3318 Level.Distance =
nullptr;
3321 else if (CurConstraint.isPoint()) {
3322 Level.Scalar =
false;
3323 Level.Distance =
nullptr;
3326 CurConstraint.getY(),
3327 CurConstraint.getX()))
3331 CurConstraint.getY(),
3332 CurConstraint.getX()))
3336 CurConstraint.getY(),
3337 CurConstraint.getX()))
3340 Level.Direction &= NewDirection;
3365 if (!SrcBase || !DstBase || SrcBase != DstBase)
3370 if (!tryDelinearizeFixedSize(Src, Dst, SrcAccessFn, DstAccessFn,
3371 SrcSubscripts, DstSubscripts) &&
3372 !tryDelinearizeParametricSize(Src, Dst, SrcAccessFn, DstAccessFn,
3373 SrcSubscripts, DstSubscripts))
3378 dbgs() <<
"\nSrcSubscripts: ";
3379 for (
int I = 0;
I <
Size;
I++)
3380 dbgs() << *SrcSubscripts[
I];
3381 dbgs() <<
"\nDstSubscripts: ";
3382 for (
int I = 0;
I <
Size;
I++)
3383 dbgs() << *DstSubscripts[
I];
3391 for (
int I = 0;
I <
Size; ++
I) {
3392 Pair[
I].Src = SrcSubscripts[
I];
3393 Pair[
I].Dst = DstSubscripts[
I];
3394 unifySubscriptType(&Pair[
I]);
3403bool DependenceInfo::tryDelinearizeFixedSize(
3412 assert(SrcBase && DstBase && SrcBase == DstBase &&
3413 "expected src and dst scev unknowns to be equal");
3426 if (SrcSizes.size() != DstSizes.
size() ||
3427 !std::equal(SrcSizes.begin(), SrcSizes.end(), DstSizes.
begin())) {
3428 SrcSubscripts.
clear();
3429 DstSubscripts.
clear();
3434 "Expected equal number of entries in the list of SrcSubscripts and "
3450 size_t SSize = Subscripts.
size();
3451 for (
size_t I = 1;
I < SSize; ++
I) {
3452 const SCEV *S = Subscripts[
I];
3453 if (!isKnownNonNegative(S,
Ptr))
3455 if (
auto *SType = dyn_cast<IntegerType>(S->
getType())) {
3457 ConstantInt::get(SType, DimensionSizes[
I - 1],
false));
3458 if (!isKnownLessThan(S,
Range))
3465 if (!AllIndicesInRange(SrcSizes, SrcSubscripts, SrcPtr) ||
3466 !AllIndicesInRange(DstSizes, DstSubscripts, DstPtr)) {
3467 SrcSubscripts.
clear();
3468 DstSubscripts.
clear();
3473 dbgs() <<
"Delinearized subscripts of fixed-size array\n"
3474 <<
"SrcGEP:" << *SrcPtr <<
"\n"
3475 <<
"DstGEP:" << *DstPtr <<
"\n";
3480bool DependenceInfo::tryDelinearizeParametricSize(
3491 assert(SrcBase && DstBase && SrcBase == DstBase &&
3492 "expected src and dst scev unknowns to be equal");
3520 if (SrcSubscripts.
size() < 2 || DstSubscripts.
size() < 2 ||
3521 SrcSubscripts.
size() != DstSubscripts.
size())
3524 size_t Size = SrcSubscripts.
size();
3533 for (
size_t I = 1;
I <
Size; ++
I) {
3534 if (!isKnownNonNegative(SrcSubscripts[
I], SrcPtr))
3537 if (!isKnownLessThan(SrcSubscripts[
I], Sizes[
I - 1]))
3540 if (!isKnownNonNegative(DstSubscripts[
I], DstPtr))
3543 if (!isKnownLessThan(DstSubscripts[
I], Sizes[
I - 1]))
3556 for (
unsigned VI : BV.
set_bits()) {
3589std::unique_ptr<Dependence>
3591 bool PossiblyLoopIndependent) {
3593 PossiblyLoopIndependent =
false;
3595 if (!(Src->mayReadOrWriteMemory() && Dst->mayReadOrWriteMemory()))
3601 LLVM_DEBUG(
dbgs() <<
"can only handle simple loads and stores\n");
3602 return std::make_unique<Dependence>(Src, Dst);
3617 return std::make_unique<Dependence>(Src, Dst);
3627 establishNestingLevels(Src, Dst);
3628 LLVM_DEBUG(
dbgs() <<
" common nesting levels = " << CommonLevels <<
"\n");
3629 LLVM_DEBUG(
dbgs() <<
" maximum nesting levels = " << MaxLevels <<
"\n");
3631 FullDependence Result(Src, Dst, PossiblyLoopIndependent, CommonLevels);
3647 LLVM_DEBUG(
dbgs() <<
"can't analyze SCEV with different pointer base\n");
3648 return std::make_unique<Dependence>(Src, Dst);
3650 Pair[0].Src = SrcSCEV;
3651 Pair[0].Dst = DstSCEV;
3654 if (tryDelinearize(Src, Dst, Pair)) {
3656 Pairs = Pair.
size();
3660 for (
unsigned P = 0;
P < Pairs; ++
P) {
3661 Pair[
P].Loops.
resize(MaxLevels + 1);
3662 Pair[
P].GroupLoops.
resize(MaxLevels + 1);
3664 removeMatchingExtensions(&Pair[
P]);
3665 Pair[
P].Classification =
3666 classifyPair(Pair[
P].Src, LI->
getLoopFor(Src->getParent()),
3669 Pair[
P].GroupLoops = Pair[
P].Loops;
3670 Pair[
P].Group.set(
P);
3739 for (
unsigned SI = 0; SI < Pairs; ++SI) {
3740 if (Pair[SI].Classification == Subscript::NonLinear) {
3742 ++NonlinearSubscriptPairs;
3743 collectCommonLoops(Pair[SI].Src,
3746 collectCommonLoops(Pair[SI].Dst,
3749 Result.Consistent =
false;
3750 }
else if (Pair[SI].Classification == Subscript::ZIV) {
3757 for (
unsigned SJ = SI + 1; SJ < Pairs; ++SJ) {
3759 Intersection &= Pair[SJ].GroupLoops;
3760 if (Intersection.
any()) {
3762 Pair[SJ].GroupLoops |= Pair[SI].GroupLoops;
3764 Pair[SJ].Group |= Pair[SI].Group;
3769 if (Pair[SI].Group.count() == 1) {
3771 ++SeparableSubscriptPairs;
3775 ++CoupledSubscriptPairs;
3786 Constraint NewConstraint;
3787 NewConstraint.setAny(SE);
3790 for (
unsigned SI : Separable.
set_bits()) {
3792 switch (Pair[SI].Classification) {
3793 case Subscript::ZIV:
3795 if (testZIV(Pair[SI].Src, Pair[SI].Dst, Result))
3798 case Subscript::SIV: {
3801 const SCEV *SplitIter =
nullptr;
3802 if (testSIV(Pair[SI].Src, Pair[SI].Dst, Level, Result, NewConstraint,
3807 case Subscript::RDIV:
3809 if (testRDIV(Pair[SI].Src, Pair[SI].Dst, Result))
3812 case Subscript::MIV:
3814 if (testMIV(Pair[SI].Src, Pair[SI].Dst, Pair[SI].
Loops, Result))
3822 if (Coupled.
count()) {
3825 LLVM_DEBUG(
dbgs() <<
"MaxLevels + 1 = " << MaxLevels + 1 <<
"\n");
3827 for (
unsigned II = 0;
II <= MaxLevels; ++
II)
3828 Constraints[
II].setAny(SE);
3829 for (
unsigned SI : Coupled.
set_bits()) {
3836 for (
unsigned SJ : Group.set_bits()) {
3838 if (Pair[SJ].Classification == Subscript::SIV)
3844 unifySubscriptType(PairsInGroup);
3846 while (Sivs.
any()) {
3847 bool Changed =
false;
3848 for (
unsigned SJ : Sivs.
set_bits()) {
3852 const SCEV *SplitIter =
nullptr;
3854 if (testSIV(Pair[SJ].Src, Pair[SJ].Dst, Level, Result, NewConstraint,
3857 ConstrainedLevels.
set(Level);
3858 if (intersectConstraints(&Constraints[Level], &NewConstraint)) {
3859 if (Constraints[Level].isEmpty()) {
3860 ++DeltaIndependence;
3872 for (
unsigned SJ : Mivs.
set_bits()) {
3875 if (propagate(Pair[SJ].Src, Pair[SJ].Dst, Pair[SJ].
Loops,
3876 Constraints, Result.Consistent)) {
3878 ++DeltaPropagations;
3879 Pair[SJ].Classification =
3880 classifyPair(Pair[SJ].Src, LI->
getLoopFor(Src->getParent()),
3881 Pair[SJ].Dst, LI->
getLoopFor(Dst->getParent()),
3883 switch (Pair[SJ].Classification) {
3884 case Subscript::ZIV:
3886 if (testZIV(Pair[SJ].Src, Pair[SJ].Dst, Result))
3890 case Subscript::SIV:
3894 case Subscript::RDIV:
3895 case Subscript::MIV:
3906 for (
unsigned SJ : Mivs.
set_bits()) {
3907 if (Pair[SJ].Classification == Subscript::RDIV) {
3909 if (testRDIV(Pair[SJ].Src, Pair[SJ].Dst, Result))
3919 for (
unsigned SJ : Mivs.
set_bits()) {
3920 if (Pair[SJ].Classification == Subscript::MIV) {
3922 if (testMIV(Pair[SJ].Src, Pair[SJ].Dst, Pair[SJ].
Loops, Result))
3931 for (
unsigned SJ : ConstrainedLevels.
set_bits()) {
3932 if (SJ > CommonLevels)
3934 updateDirection(Result.DV[SJ - 1], Constraints[SJ]);
3943 for (
unsigned SI = 0; SI < Pairs; ++SI)
3944 CompleteLoops |= Pair[SI].
Loops;
3945 for (
unsigned II = 1;
II <= CommonLevels; ++
II)
3946 if (CompleteLoops[
II])
3947 Result.DV[
II - 1].Scalar =
false;
3949 if (PossiblyLoopIndependent) {
3953 for (
unsigned II = 1;
II <= CommonLevels; ++
II) {
3955 Result.LoopIndependent =
false;
3963 bool AllEqual =
true;
3964 for (
unsigned II = 1;
II <= CommonLevels; ++
II) {
3974 return std::make_unique<FullDependence>(std::move(Result));
4025 unsigned SplitLevel) {
4027 "Dep should be splitable at SplitLevel");
4030 assert(Src->mayReadFromMemory() || Src->mayWriteToMemory());
4031 assert(Dst->mayReadFromMemory() || Dst->mayWriteToMemory());
4041 establishNestingLevels(Src, Dst);
4049 Pair[0].Src = SrcSCEV;
4050 Pair[0].Dst = DstSCEV;
4053 if (tryDelinearize(Src, Dst, Pair)) {
4055 Pairs = Pair.
size();
4059 for (
unsigned P = 0;
P < Pairs; ++
P) {
4060 Pair[
P].Loops.
resize(MaxLevels + 1);
4061 Pair[
P].GroupLoops.
resize(MaxLevels + 1);
4063 removeMatchingExtensions(&Pair[
P]);
4064 Pair[
P].Classification =
4065 classifyPair(Pair[
P].Src, LI->
getLoopFor(Src->getParent()),
4068 Pair[
P].GroupLoops = Pair[
P].Loops;
4069 Pair[
P].Group.set(
P);
4076 for (
unsigned SI = 0; SI < Pairs; ++SI) {
4077 if (Pair[SI].Classification == Subscript::NonLinear) {
4079 collectCommonLoops(Pair[SI].Src,
4082 collectCommonLoops(Pair[SI].Dst,
4085 Result.Consistent =
false;
4087 else if (Pair[SI].Classification == Subscript::ZIV)
4092 for (
unsigned SJ = SI + 1; SJ < Pairs; ++SJ) {
4094 Intersection &= Pair[SJ].GroupLoops;
4095 if (Intersection.
any()) {
4097 Pair[SJ].GroupLoops |= Pair[SI].GroupLoops;
4099 Pair[SJ].Group |= Pair[SI].Group;
4104 if (Pair[SI].Group.count() == 1)
4112 Constraint NewConstraint;
4113 NewConstraint.setAny(SE);
4116 for (
unsigned SI : Separable.
set_bits()) {
4117 switch (Pair[SI].Classification) {
4118 case Subscript::SIV: {
4120 const SCEV *SplitIter =
nullptr;
4121 (void) testSIV(Pair[SI].Src, Pair[SI].Dst, Level,
4122 Result, NewConstraint, SplitIter);
4123 if (Level == SplitLevel) {
4124 assert(SplitIter !=
nullptr);
4129 case Subscript::ZIV:
4130 case Subscript::RDIV:
4131 case Subscript::MIV:
4138 if (Coupled.
count()) {
4141 for (
unsigned II = 0;
II <= MaxLevels; ++
II)
4142 Constraints[
II].setAny(SE);
4143 for (
unsigned SI : Coupled.
set_bits()) {
4148 for (
unsigned SJ : Group.set_bits()) {
4149 if (Pair[SJ].Classification == Subscript::SIV)
4154 while (Sivs.
any()) {
4155 bool Changed =
false;
4156 for (
unsigned SJ : Sivs.
set_bits()) {
4159 const SCEV *SplitIter =
nullptr;
4160 (void) testSIV(Pair[SJ].Src, Pair[SJ].Dst, Level,
4161 Result, NewConstraint, SplitIter);
4162 if (Level == SplitLevel && SplitIter)
4164 ConstrainedLevels.
set(Level);
4165 if (intersectConstraints(&Constraints[Level], &NewConstraint))
4171 for (
unsigned SJ : Mivs.
set_bits()) {
4173 if (propagate(Pair[SJ].Src, Pair[SJ].Dst,
4174 Pair[SJ].
Loops, Constraints, Result.Consistent)) {
4175 Pair[SJ].Classification =
4176 classifyPair(Pair[SJ].Src, LI->
getLoopFor(Src->getParent()),
4177 Pair[SJ].Dst, LI->
getLoopFor(Dst->getParent()),
4179 switch (Pair[SJ].Classification) {
4180 case Subscript::ZIV:
4183 case Subscript::SIV:
4187 case Subscript::RDIV:
4188 case Subscript::MIV:
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
block Block Frequency Analysis
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds.
static bool isLoadOrStore(const Instruction *I)
static bool findGCD(unsigned Bits, const APInt &AM, const APInt &BM, const APInt &Delta, APInt &G, APInt &X, APInt &Y)
static void dumpSmallBitVector(SmallBitVector &BV)
static const SCEVConstant * getConstantPart(const SCEV *Expr)
static APInt ceilingOfQuotient(const APInt &A, const APInt &B)
static APInt floorOfQuotient(const APInt &A, const APInt &B)
static AliasResult underlyingObjectsAlias(AAResults *AA, const DataLayout &DL, const MemoryLocation &LocA, const MemoryLocation &LocB)
static bool isRemainderZero(const SCEVConstant *Dividend, const SCEVConstant *Divisor)
static cl::opt< bool > Delinearize("da-delinearize", cl::init(true), cl::Hidden, cl::desc("Try to delinearize array references."))
static void dumpExampleDependence(raw_ostream &OS, DependenceInfo *DA, ScalarEvolution &SE, bool NormalizeResults)
static cl::opt< unsigned > MIVMaxLevelThreshold("da-miv-max-level-threshold", cl::init(7), cl::Hidden, cl::desc("Maximum depth allowed for the recursive algorithm used to " "explore MIV direction vectors."))
static cl::opt< bool > DisableDelinearizationChecks("da-disable-delinearization-checks", cl::Hidden, 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."))
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
static bool isZero(Value *V, const DataLayout &DL, DominatorTree *DT, AssumptionCache *AC)
Module.h This file contains the declarations for the Module class.
ConstantRange Range(APInt(BitWidth, Low), APInt(BitWidth, High))
uint64_t IntrinsicInst * II
static GCMetadataPrinterRegistry::Add< OcamlGCMetadataPrinter > Y("ocaml", "ocaml 3.10-compatible collector")
FunctionAnalysisManager FAM
#define INITIALIZE_PASS_DEPENDENCY(depName)
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
A manager for alias analyses.
A wrapper pass to provide the legacy pass manager access to a suitably prepared AAResults object.
bool isNoAlias(const MemoryLocation &LocA, const MemoryLocation &LocB)
A trivial helper function to check to see if the specified pointers are no-alias.
Class for arbitrary precision integers.
static void sdivrem(const APInt &LHS, const APInt &RHS, APInt &Quotient, APInt &Remainder)
APInt abs() const
Get the absolute value.
bool sgt(const APInt &RHS) const
Signed greater than comparison.
unsigned getBitWidth() const
Return the number of bits in the APInt.
static APInt getSignedMaxValue(unsigned numBits)
Gets maximum signed value of APInt for a specific bit width.
APInt sdiv(const APInt &RHS) const
Signed division function for APInt.
bool sle(const APInt &RHS) const
Signed less or equal comparison.
static APInt getSignedMinValue(unsigned numBits)
Gets minimum signed value of APInt for a specific bit width.
APInt srem(const APInt &RHS) const
Function for signed remainder operation.
bool slt(const APInt &RHS) const
Signed less than comparison.
static APInt getZero(unsigned numBits)
Get the '0' value for the specified bit-width.
bool sge(const APInt &RHS) const
Signed greater or equal comparison.
The possible results of an alias query.
@ MayAlias
The two locations may or may not alias.
@ NoAlias
The two locations do not alias at all.
@ PartialAlias
The two locations alias, but only due to a partial overlap.
@ MustAlias
The two locations precisely alias each other.
This templated class represents "all analyses that operate over <a particular IR unit>" (e....
API to communicate dependencies between analyses during invalidation.
bool invalidate(IRUnitT &IR, const PreservedAnalyses &PA)
Trigger the invalidation of some other analysis pass if not already handled and return whether it was...
A container for analyses that lazily runs them and caches their results.
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Represent the analysis usage information of a pass.
void setPreservesAll()
Set by analyses that do not transform their input at all.
AnalysisUsage & addRequiredTransitive()
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
LLVM Basic Block Representation.
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
@ ICMP_SLT
signed less than
@ ICMP_SLE
signed less or equal
@ ICMP_SGT
signed greater than
@ ICMP_SGE
signed greater or equal
This is an important base class in LLVM.
This class represents an Operation in the Expression.
A parsed version of the target data layout string in and methods for querying it.
Legacy pass manager pass to access dependence information.
void getAnalysisUsage(AnalysisUsage &) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
bool runOnFunction(Function &F) override
runOnFunction - Virtual method overriden by subclasses to do the per-function processing of the pass.
void print(raw_ostream &, const Module *=nullptr) const override
print - Print out the internal state of the pass.
DependenceInfo & getDI() const
void releaseMemory() override
releaseMemory() - This member can be implemented by a pass if it wants to be able to release its memo...
AnalysisPass to compute dependence information in a function.
Result run(Function &F, FunctionAnalysisManager &FAM)
DependenceInfo - This class is the main dependence-analysis driver.
bool invalidate(Function &F, const PreservedAnalyses &PA, FunctionAnalysisManager::Invalidator &Inv)
Handle transitive invalidation when the cached analysis results go away.
const SCEV * getSplitIteration(const Dependence &Dep, unsigned Level)
getSplitIteration - Give a dependence that's splittable at some particular level, return the iteratio...
std::unique_ptr< Dependence > depends(Instruction *Src, Instruction *Dst, bool PossiblyLoopIndependent)
depends - Tests for a dependence between the Src and Dst instructions.
Dependence - This class represents a dependence between two memory memory references in a function.
virtual unsigned getDirection(unsigned Level) const
getDirection - Returns the direction associated with a particular level.
virtual bool isPeelFirst(unsigned Level) const
isPeelFirst - Returns true if peeling the first iteration from this loop will break this dependence.
Instruction * getDst() const
getDst - Returns the destination instruction for this dependence.
virtual bool isConfused() const
isConfused - Returns true if this dependence is confused (the compiler understands nothing and makes ...
virtual bool isSplitable(unsigned Level) const
isSplitable - Returns true if splitting this loop will break the dependence.
virtual const SCEV * getDistance(unsigned Level) const
getDistance - Returns the distance (or NULL) associated with a particular level.
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...
virtual bool isConsistent() const
isConsistent - Returns true if this dependence is consistent (occurs every time the source and destin...
virtual bool isPeelLast(unsigned Level) const
isPeelLast - Returns true if peeling the last iteration from this loop will break this dependence.
virtual unsigned getLevels() const
getLevels - Returns the number of common loops surrounding the source and destination of the dependen...
bool isFlow() const
isFlow - Returns true if this is a flow (aka true) dependence.
bool isInput() const
isInput - Returns true if this is an input dependence.
bool isAnti() const
isAnti - Returns true if this is an anti dependence.
Instruction * getSrc() const
getSrc - Returns the source instruction for this dependence.
virtual bool isLoopIndependent() const
isLoopIndependent - Returns true if this is a loop-independent dependence.
bool isOutput() const
isOutput - Returns true if this is an output dependence.
void dump(raw_ostream &OS) const
dump - For debugging purposes, dumps a dependence to OS.
Class representing an expression and its matching format.
FullDependence - This class represents a dependence between two memory references in a function.
unsigned getDirection(unsigned Level) const override
getDirection - Returns the direction associated with a particular level.
const SCEV * getDistance(unsigned Level) const override
getDistance - Returns the distance (or NULL) associated with a particular level.
bool isDirectionNegative() const override
Check if the direction vector is negative.
bool isSplitable(unsigned Level) const override
isSplitable - Returns true if splitting the loop will break the dependence.
FullDependence(Instruction *Src, Instruction *Dst, bool LoopIndependent, unsigned Levels)
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...
bool isPeelLast(unsigned Level) const override
isPeelLast - Returns true if peeling the last iteration from this loop will break this dependence.
bool isPeelFirst(unsigned Level) const override
isPeelFirst - Returns true if peeling the first iteration from this loop will break this dependence.
bool normalize(ScalarEvolution *SE) override
If the direction vector is negative, normalize the direction vector to make it non-negative.
FunctionPass class - This class is used to implement most global optimizations.
const DataLayout & getDataLayout() const
Get the data layout of the module this function belongs to.
bool mayWriteToMemory() const LLVM_READONLY
Return true if this instruction may modify memory.
bool mayReadFromMemory() const LLVM_READONLY
Return true if this instruction may read memory.
Class to represent integer types.
unsigned getBitWidth() const
Get the number of bits in this IntegerType.
An instruction for reading from memory.
Analysis pass that exposes the LoopInfo for a function.
unsigned getLoopDepth() const
Return the nesting level of this loop.
LoopT * getParentLoop() const
Return the parent loop if it exists or nullptr for top level loops.
unsigned getLoopDepth(const BlockT *BB) const
Return the loop nesting level of the specified block.
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
The legacy pass manager's analysis pass to compute loop information.
This class represents a loop nest and can be used to query its properties.
Loop & getOutermostLoop() const
Return the outermost loop in the loop nest.
Represents a single loop in the control flow graph.
Representation for a specific memory location.
static MemoryLocation get(const LoadInst *LI)
Return a location with information about the memory reference by the given instruction.
static MemoryLocation getBeforeOrAfter(const Value *Ptr, const AAMDNodes &AATags=AAMDNodes())
Return a location that may access any location before or after Ptr, while remaining within the underl...
AAMDNodes AATags
The metadata nodes which describes the aliasing of the location (each member is null if that kind of ...
const Value * Ptr
The address of the start of the location.
A Module instance is used to store all the information related to an LLVM module.
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
A set of analyses that are preserved following a run of a transformation pass.
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
PreservedAnalysisChecker getChecker() const
Build a checker for this PreservedAnalyses and the specified analysis type.
This node represents an addition of some number of SCEVs.
This node represents a polynomial recurrence on the trip count of the specified loop.
const SCEV * getStart() const
const SCEV * evaluateAtIteration(const SCEV *It, ScalarEvolution &SE) const
Return the value of this chain of recurrences at the specified iteration number.
const SCEV * getStepRecurrence(ScalarEvolution &SE) const
Constructs and returns the recurrence indicating how much this expression steps by.
bool isAffine() const
Return true if this represents an expression A + B*x where A and B are loop invariant values.
const Loop * getLoop() const
const SCEV * getOperand() const
This class represents a constant integer value.
const APInt & getAPInt() const
This is the base class for unary integral cast operator classes.
This node represents multiplication of some number of SCEVs.
NoWrapFlags getNoWrapFlags(NoWrapFlags Mask=NoWrapMask) const
const SCEV * getOperand(unsigned i) const
This means that we are dealing with an entirely unknown SCEV value, and only represent it as its LLVM...
This class represents an analyzed expression in the program.
bool isOne() const
Return true if the expression is a constant one.
bool isZero() const
Return true if the expression is a constant zero.
Type * getType() const
Return the LLVM type of this SCEV expression.
Analysis pass that exposes the ScalarEvolution for a function.
The main scalar evolution driver.
bool isKnownNonNegative(const SCEV *S)
Test if the given expression is known to be non-negative.
const SCEV * getNegativeSCEV(const SCEV *V, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap)
Return the SCEV object corresponding to -V.
const SCEV * getSMaxExpr(const SCEV *LHS, const SCEV *RHS)
bool isKnownNonPositive(const SCEV *S)
Test if the given expression is known to be non-positive.
bool isKnownNegative(const SCEV *S)
Test if the given expression is known to be negative.
bool isKnownNonZero(const SCEV *S)
Test if the given expression is known to be non-zero.
const SCEV * getSCEVAtScope(const SCEV *S, const Loop *L)
Return a SCEV expression for the specified value at the specified scope in the program.
const SCEV * getSMinExpr(const SCEV *LHS, const SCEV *RHS)
const SCEV * getBackedgeTakenCount(const Loop *L, ExitCountKind Kind=Exact)
If the specified loop has a predictable backedge-taken count, return it, otherwise return a SCEVCould...
const SCEV * getZero(Type *Ty)
Return a SCEV for the constant 0 of a specific type.
uint64_t getTypeSizeInBits(Type *Ty) const
Return the size in bits of the specified type, for which isSCEVable must return true.
const SCEV * getConstant(ConstantInt *V)
const SCEV * getSCEV(Value *V)
Return a SCEV expression for the full generality of the specified expression.
const SCEV * getOne(Type *Ty)
Return a SCEV for the constant 1 of a specific type.
bool isLoopInvariant(const SCEV *S, const Loop *L)
Return true if the value of the given SCEV is unchanging in the specified loop.
bool isKnownPositive(const SCEV *S)
Test if the given expression is known to be positive.
bool isKnownPredicate(ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS)
Test if the given expression is known to satisfy the condition described by Pred, LHS,...
const SCEV * getAddRecExpr(const SCEV *Start, const SCEV *Step, const Loop *L, SCEV::NoWrapFlags Flags)
Get an add recurrence expression for the specified loop.
const SCEV * getUDivExpr(const SCEV *LHS, const SCEV *RHS)
Get a canonical unsigned division expression, or something simpler if possible.
const SCEV * getMinusSCEV(const SCEV *LHS, const SCEV *RHS, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
Return LHS-RHS.
bool hasLoopInvariantBackedgeTakenCount(const Loop *L)
Return true if the specified loop has an analyzable loop-invariant backedge-taken count.
const SCEV * getSignExtendExpr(const SCEV *Op, Type *Ty, unsigned Depth=0)
const SCEV * getPointerBase(const SCEV *V)
Transitively follow the chain of pointer-type operands until reaching a SCEV that does not have a sin...
const SCEV * getMulExpr(SmallVectorImpl< const SCEV * > &Ops, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
Get a canonical multiply expression, or something simpler if possible.
const SCEV * getElementSize(Instruction *Inst)
Return the size of an element read or written by Inst.
const SCEV * getTruncateOrZeroExtend(const SCEV *V, Type *Ty, unsigned Depth=0)
Return a SCEV corresponding to a conversion of the input value to the specified type.
const SCEV * getAddExpr(SmallVectorImpl< const SCEV * > &Ops, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
Get a canonical add expression, or something simpler if possible.
This is a 'bitvector' (really, a variable-sized bit array), optimized for the case when the array is ...
iterator_range< const_set_bits_iterator > set_bits() const
int find_next(unsigned Prev) const
Returns the index of the next set bit following the "Prev" bit.
bool any() const
Returns true if any bit is set.
size_type count() const
Returns the number of bits which are set.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
An instruction for storing to memory.
The instances of the Type class are immutable: once they are created, they are never changed.
LLVM Value Representation.
This class implements an extremely fast bulk output stream that can only output to a stream.
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
const APInt & smin(const APInt &A, const APInt &B)
Determine the smaller of two APInts considered to be signed.
const APInt & smax(const APInt &A, const APInt &B)
Determine the larger of two APInts considered to be signed.
APInt GreatestCommonDivisor(APInt A, APInt B)
Compute GCD of two unsigned APInt values.
@ C
The default llvm calling convention, compatible with C.
@ TB
TB - TwoByte - Set if this instruction has a two byte opcode, which starts with a 0x0F byte before th...
initializer< Ty > init(const Ty &Val)
This is an optimization pass for GlobalISel generic memory operations.
void dump(const SparseBitVector< ElementSize > &LHS, raw_ostream &out)
void collectParametricTerms(ScalarEvolution &SE, const SCEV *Expr, SmallVectorImpl< const SCEV * > &Terms)
Collect parametric terms occurring in step expressions (first step of delinearization).