66#define DEBUG_TYPE "da"
72STATISTIC(NonlinearSubscriptPairs,
"Nonlinear subscript pairs");
75STATISTIC(StrongSIVapplications,
"Strong SIV applications");
76STATISTIC(StrongSIVsuccesses,
"Strong SIV successes");
77STATISTIC(StrongSIVindependence,
"Strong SIV independence");
78STATISTIC(WeakCrossingSIVapplications,
"Weak-Crossing SIV applications");
79STATISTIC(WeakCrossingSIVsuccesses,
"Weak-Crossing SIV successes");
80STATISTIC(WeakCrossingSIVindependence,
"Weak-Crossing SIV independence");
81STATISTIC(ExactSIVapplications,
"Exact SIV applications");
83STATISTIC(ExactSIVindependence,
"Exact SIV independence");
84STATISTIC(WeakZeroSIVapplications,
"Weak-Zero SIV applications");
85STATISTIC(WeakZeroSIVsuccesses,
"Weak-Zero SIV successes");
86STATISTIC(WeakZeroSIVindependence,
"Weak-Zero SIV independence");
87STATISTIC(ExactRDIVapplications,
"Exact RDIV applications");
88STATISTIC(ExactRDIVindependence,
"Exact RDIV independence");
92STATISTIC(BanerjeeApplications,
"Banerjee applications");
93STATISTIC(BanerjeeIndependence,
"Banerjee independence");
95STATISTIC(SameSDLoopsCount,
"Loops with Same iteration Space and Depth");
115 "Dependence Analysis",
true,
true)
160struct OverflowSafeSignedAPInt {
161 OverflowSafeSignedAPInt() :
Value(
std::nullopt) {}
163 OverflowSafeSignedAPInt(
const std::optional<APInt> &
V) :
Value(
V) {}
165 OverflowSafeSignedAPInt
operator+(
const OverflowSafeSignedAPInt &
RHS)
const {
167 return OverflowSafeSignedAPInt();
171 return OverflowSafeSignedAPInt();
172 return OverflowSafeSignedAPInt(Result);
177 return OverflowSafeSignedAPInt();
178 return *
this + fromInt(
RHS);
181 OverflowSafeSignedAPInt
operator-(
const OverflowSafeSignedAPInt &
RHS)
const {
183 return OverflowSafeSignedAPInt();
187 return OverflowSafeSignedAPInt();
188 return OverflowSafeSignedAPInt(Result);
193 return OverflowSafeSignedAPInt();
194 return *
this - fromInt(
RHS);
197 OverflowSafeSignedAPInt
operator*(
const OverflowSafeSignedAPInt &
RHS)
const {
199 return OverflowSafeSignedAPInt();
203 return OverflowSafeSignedAPInt();
204 return OverflowSafeSignedAPInt(Result);
207 OverflowSafeSignedAPInt
operator-()
const {
209 return OverflowSafeSignedAPInt();
210 if (
Value->isMinSignedValue())
211 return OverflowSafeSignedAPInt();
212 return OverflowSafeSignedAPInt(-*
Value);
215 operator bool()
const {
return Value.has_value(); }
224 const APInt *operator->()
const {
232 std::optional<APInt>
Value;
234 OverflowSafeSignedAPInt fromInt(
uint64_t V)
const {
236 return OverflowSafeSignedAPInt(
237 APInt(
Value->getBitWidth(),
V,
true));
249 bool NormalizeResults) {
250 auto *
F = DA->getFunction();
254 if (SrcI->mayReadOrWriteMemory()) {
257 if (DstI->mayReadOrWriteMemory()) {
258 OS <<
"Src:" << *SrcI <<
" --> Dst:" << *DstI <<
"\n";
259 OS <<
" da analyze - ";
260 if (
auto D = DA->depends(&*SrcI, &*DstI,
266 for (
unsigned Level = 1; Level <=
D->getLevels(); Level++) {
267 const SCEV *Distance =
D->getDistance(Level);
268 bool IsDistanceZero = Distance && Distance->
isZero();
271 assert(IsDistanceZero == IsDirectionEQ &&
272 "Inconsistent distance and direction.");
277 if (NormalizeResults &&
D->normalize(&SE))
278 OS <<
"normalized - ";
297 OS <<
"Printing analysis 'Dependence Analysis' for function '" <<
F.getName()
310 return Src->mayReadFromMemory() &&
Dst->mayReadFromMemory();
315 return Src->mayWriteToMemory() &&
Dst->mayWriteToMemory();
320 return Src->mayWriteToMemory() &&
Dst->mayReadFromMemory();
325 return Src->mayReadFromMemory() &&
Dst->mayWriteToMemory();
339 bool PossiblyLoopIndependent,
340 unsigned CommonLevels)
341 :
Dependence(Source, Destination, Assumes), Levels(CommonLevels),
342 LoopIndependent(PossiblyLoopIndependent) {
345 DV = std::make_unique<
DVEntry[]>(CommonLevels);
364 for (
unsigned Level = 1; Level <= Levels; ++Level) {
365 unsigned char Direction = DV[Level - 1].Direction;
378 for (
unsigned Level = 1; Level <= Levels; ++Level) {
379 unsigned char Direction = DV[Level - 1].Direction;
387 DV[Level - 1].Direction = RevDirection;
389 if (DV[Level - 1].Distance !=
nullptr)
398 LLVM_DEBUG(
dbgs() <<
"Before normalizing negative direction vectors:\n";
401 LLVM_DEBUG(
dbgs() <<
"After normalizing negative direction vectors:\n";
431 assert(0 < Level && Level <=
static_cast<unsigned>(Levels) + SameSDLevels &&
432 "Level out of range");
433 return Level > Levels;
454 if (SameSDLevels > 0) {
455 OS <<
" / assuming " << SameSDLevels <<
" loop level(s) fused: ";
462 if (!Assumptions.isAlwaysTrue()) {
463 OS <<
" Runtime Assumptions:\n";
464 Assumptions.print(OS, 2);
473 bool OnSameSD =
false;
474 unsigned LevelNum = Levels;
476 LevelNum += SameSDLevels;
478 for (
unsigned II = 1;
II <= LevelNum; ++
II) {
511 if (!ScopeList || LoopAliasScopes.
empty())
517 return LoopAliasScopes.contains(cast<MDNode>(Scope));
577 return LI->isUnordered();
579 return SI->isUnordered();
587bool DependenceInfo::haveSameSD(
const Loop *SrcLoop,
588 const Loop *DstLoop)
const {
589 if (SrcLoop == DstLoop)
599 const SCEV *SrcUB = SE->getBackedgeTakenCount(SrcLoop);
600 const SCEV *DstUB = SE->getBackedgeTakenCount(DstLoop);
605 SrcUB = SE->getNoopOrZeroExtend(SrcUB, WiderType);
606 DstUB = SE->getNoopOrZeroExtend(DstUB, WiderType);
678void DependenceInfo::establishNestingLevels(
const Instruction *Src,
680 const BasicBlock *SrcBlock = Src->getParent();
681 const BasicBlock *DstBlock = Dst->getParent();
682 unsigned SrcLevel = LI->getLoopDepth(SrcBlock);
683 unsigned DstLevel = LI->getLoopDepth(DstBlock);
684 const Loop *SrcLoop = LI->getLoopFor(SrcBlock);
685 const Loop *DstLoop = LI->getLoopFor(DstBlock);
686 SrcLevels = SrcLevel;
687 MaxLevels = SrcLevel + DstLevel;
689 while (SrcLevel > DstLevel) {
693 while (DstLevel > SrcLevel) {
698 const Loop *SrcUncommonFrontier =
nullptr, *DstUncommonFrontier =
nullptr;
701 while (SrcLoop != DstLoop) {
702 SrcUncommonFrontier = SrcLoop;
703 DstUncommonFrontier = DstLoop;
708 if (SrcUncommonFrontier && DstUncommonFrontier &&
709 haveSameSD(SrcUncommonFrontier, DstUncommonFrontier))
711 CommonLevels = SrcLevel;
712 MaxLevels -= CommonLevels;
717unsigned DependenceInfo::mapSrcLoop(
const Loop *SrcLoop)
const {
723unsigned DependenceInfo::mapDstLoop(
const Loop *DstLoop)
const {
725 if (
D > CommonLevels)
728 return D - CommonLevels + SrcLevels;
755 if (Level <= CommonLevels && !SE->isLoopInvariant(Expression, LoopNest))
767 return isLoopInvariant(Expr, LoopNest);
774 const Loop *
L = LoopNest;
775 while (L && AddRec->
getLoop() != L)
776 L =
L->getParentLoop();
785 if (!isLoopInvariant(Step, LoopNest))
791 return checkSubscript(Start, LoopNest,
Loops, IsSrc);
796bool DependenceInfo::checkSrcSubscript(
const SCEV *Src,
const Loop *
LoopNest,
798 return checkSubscript(Src, LoopNest,
Loops,
true);
803bool DependenceInfo::checkDstSubscript(
const SCEV *Dst,
const Loop *
LoopNest,
805 return checkSubscript(Dst, LoopNest,
Loops,
false);
811DependenceInfo::Subscript::ClassificationKind
812DependenceInfo::classifyPair(
const SCEV *Src,
const Loop *SrcLoopNest,
813 const SCEV *Dst,
const Loop *DstLoopNest,
815 SmallBitVector SrcLoops(MaxLevels + 1);
816 SmallBitVector DstLoops(MaxLevels + 1);
817 if (!checkSrcSubscript(Src, SrcLoopNest, SrcLoops))
818 return Subscript::NonLinear;
819 if (!checkDstSubscript(Dst, DstLoopNest, DstLoops))
820 return Subscript::NonLinear;
823 unsigned N =
Loops.count();
825 return Subscript::ZIV;
827 return Subscript::SIV;
828 if (
N == 2 && SrcLoops.count() == 1 && DstLoops.count() == 1)
829 return Subscript::RDIV;
830 return Subscript::MIV;
840const SCEV *DependenceInfo::collectUpperBound(
const Loop *L,
Type *
T)
const {
841 if (SE->hasLoopInvariantBackedgeTakenCount(L)) {
842 const SCEV *UB = SE->getBackedgeTakenCount(L);
843 return SE->getTruncateOrZeroExtend(UB,
T);
851DependenceInfo::collectNonNegativeConstantUpperBound(
const Loop *L,
853 if (
const SCEV *UB = collectUpperBound(L,
T))
855 APInt Res =
C->getAPInt();
881 return Opts.da_enable_dependence_test ==
Test;
894bool DependenceInfo::testZIV(
const SCEV *Src,
const SCEV *Dst,
942 bool UnderRuntimeAssumptions) {
946 const SCEV *Coeff = Src->getStepRecurrence(*SE);
947 assert(Coeff == Dst->getStepRecurrence(*SE) &&
948 "Expecting same coefficient in Strong SIV test");
949 const SCEV *SrcConst = Src->getStart();
950 const SCEV *DstConst = Dst->getStart();
958 ++StrongSIVapplications;
959 assert(0 < Level && Level <= CommonLevels &&
"level out of range");
972 APInt Distance = ConstDelta;
973 APInt Remainder = ConstDelta;
978 if (Remainder != 0) {
980 ++StrongSIVindependence;
981 ++StrongSIVsuccesses;
984 Result.DV[
Level].Distance = SE->getConstant(Distance);
987 else if (Distance.
slt(0))
991 ++StrongSIVsuccesses;
992 }
else if (Delta->
isZero()) {
996 if (SE->isKnownNonZero(Coeff)) {
998 dbgs() <<
"\t Coefficient proven non-zero by SCEV analysis\n");
1001 if (UnderRuntimeAssumptions) {
1002 const SCEVPredicate *
Pred = SE->getComparePredicate(
1010 LLVM_DEBUG(
dbgs() <<
"\t Would need runtime assumption " << *Coeff
1011 <<
" != 0, but not allowed. Failing this test.\n");
1018 ++StrongSIVsuccesses;
1020 if (Coeff->
isOne()) {
1026 bool DeltaMaybeZero = !SE->isKnownNonZero(Delta);
1027 bool DeltaMaybePositive = !SE->isKnownNonPositive(Delta);
1028 bool DeltaMaybeNegative = !SE->isKnownNonNegative(Delta);
1029 bool CoeffMaybePositive = !SE->isKnownNonPositive(Coeff);
1030 bool CoeffMaybeNegative = !SE->isKnownNonNegative(Coeff);
1035 if ((DeltaMaybePositive && CoeffMaybePositive) ||
1036 (DeltaMaybeNegative && CoeffMaybeNegative))
1040 if ((DeltaMaybeNegative && CoeffMaybePositive) ||
1041 (DeltaMaybePositive && CoeffMaybeNegative))
1043 if (NewDirection <
Result.DV[Level].Direction)
1044 ++StrongSIVsuccesses;
1078bool DependenceInfo::weakCrossingSIVtest(
const SCEVAddRecExpr *Src,
1085 const SCEV *Coeff = Src->getStepRecurrence(*SE);
1086 const SCEV *SrcConst = Src->getStart();
1087 const SCEV *DstConst = Dst->getStart();
1089 assert(Coeff == SE->getNegativeSCEV(Dst->getStepRecurrence(*SE)) &&
1090 "Unexpected input for weakCrossingSIVtest");
1096 ++WeakCrossingSIVapplications;
1097 assert(0 < Level && Level <= CommonLevels &&
"Level out of range");
1112 ConstantRange SrcRange = SE->getSignedRange(Src);
1113 ConstantRange DstRange = SE->getSignedRange(Dst);
1118 Result.DV[
Level].Direction &= ~Dependence::DVEntry::LT;
1119 Result.DV[
Level].Direction &= ~Dependence::DVEntry::GT;
1120 ++WeakCrossingSIVsuccesses;
1121 if (!
Result.DV[Level].Direction) {
1122 ++WeakCrossingSIVindependence;
1130 APInt APDelta = ConstDelta->
getAPInt();
1131 APInt APCoeff = ConstCoeff->
getAPInt();
1132 APInt Distance = APDelta;
1133 APInt Remainder = APDelta;
1136 if (Remainder != 0) {
1138 ++WeakCrossingSIVindependence;
1139 ++WeakCrossingSIVsuccesses;
1147 Result.DV[
Level].Direction &= ~Dependence::DVEntry::EQ;
1148 ++WeakCrossingSIVsuccesses;
1172 APInt A0(Bits, 1,
true), A1(Bits, 0,
true);
1173 APInt B0(Bits, 0,
true), B1(Bits, 1,
true);
1177 return std::nullopt;
1186 APInt A2 = A0 - Q*A1; A0 = A1; A1 = A2;
1187 APInt B2 = B0 - Q*B1; B0 = B1; B1 = B2;
1194 X = AM.
slt(0) ? -A1 : A1;
1195 Y = BM.
slt(0) ? B1 : -B1;
1205static OverflowSafeSignedAPInt
1207 const OverflowSafeSignedAPInt &OB) {
1209 return OverflowSafeSignedAPInt();
1218 if ((
A.sgt(0) &&
B.sgt(0)) || (
A.slt(0) &&
B.slt(0)))
1220 return OverflowSafeSignedAPInt(Q) - 1;
1223static OverflowSafeSignedAPInt
1225 const OverflowSafeSignedAPInt &OB) {
1227 return OverflowSafeSignedAPInt();
1236 if ((
A.sgt(0) &&
B.sgt(0)) || (
A.slt(0) &&
B.slt(0)))
1237 return OverflowSafeSignedAPInt(Q) + 1;
1271static std::pair<OverflowSafeSignedAPInt, OverflowSafeSignedAPInt>
1273 OverflowSafeSignedAPInt UB) {
1274 assert(
A &&
B &&
"A and B must be available");
1275 assert(*
A != 0 &&
"A must be non-zero");
1276 assert((!UB || UB->isNonNegative()) &&
"UB must be non-negative");
1277 OverflowSafeSignedAPInt TL, TU;
1280 LLVM_DEBUG(
if (TL)
dbgs() <<
"\t Possible TL = " << *TL <<
"\n");
1284 LLVM_DEBUG(
if (TU)
dbgs() <<
"\t Possible TU = " << *TU <<
"\n");
1287 LLVM_DEBUG(
if (TU)
dbgs() <<
"\t Possible TU = " << *TU <<
"\n");
1291 LLVM_DEBUG(
if (TL)
dbgs() <<
"\t Possible TL = " << *TL <<
"\n");
1293 return std::make_pair(TL, TU);
1322 ++ExactSIVapplications;
1323 assert(0 < Level && Level <= CommonLevels &&
"Level out of range");
1325 bool Res = exactTestImpl(Src, Dst, Result, Level);
1327 ++ExactSIVsuccesses;
1328 ++ExactSIVindependence;
1338 return ConstDividend.
srem(ConstDivisor) == 0;
1341bool DependenceInfo::weakZeroSIVtestImpl(
const SCEVAddRecExpr *AR,
1342 const SCEV *Const,
unsigned Level,
1345 const SCEV *ARConst = AR->
getStart();
1347 if (Const == ARConst && SE->isKnownNonZero(ARCoeff)) {
1348 if (Level < CommonLevels) {
1350 ++WeakZeroSIVsuccesses;
1362 if (
const SCEV *UpperBound =
1365 bool OverlapAtLast = [&] {
1366 if (!SE->isKnownNonZero(ConstCoeff))
1371 if (OverlapAtLast) {
1373 if (Level < CommonLevels) {
1375 ++WeakZeroSIVsuccesses;
1384 ++WeakZeroSIVindependence;
1385 ++WeakZeroSIVsuccesses;
1420bool DependenceInfo::weakZeroSrcSIVtest(
const SCEV *SrcConst,
1430 [[maybe_unused]]
const SCEV *DstCoeff = Dst->getStepRecurrence(*SE);
1431 [[maybe_unused]]
const SCEV *DstConst = Dst->getStart();
1436 ++WeakZeroSIVapplications;
1437 assert(0 < Level && Level <= MaxLevels &&
"Level out of range");
1446 bool Res = weakZeroSIVtestImpl(Dst, SrcConst, Level, Result);
1480bool DependenceInfo::weakZeroDstSIVtest(
const SCEVAddRecExpr *Src,
1481 const SCEV *DstConst,
unsigned Level,
1488 [[maybe_unused]]
const SCEV *SrcCoeff = Src->getStepRecurrence(*SE);
1489 [[maybe_unused]]
const SCEV *SrcConst = Src->getStart();
1494 ++WeakZeroSIVapplications;
1495 assert(0 < Level && Level <= SrcLevels &&
"Level out of range");
1498 return weakZeroSIVtestImpl(Src, DstConst, Level, Result);
1514 ++ExactRDIVapplications;
1515 bool Res = exactTestImpl(Src, Dst, Result, std::nullopt);
1517 ++ExactRDIVindependence;
1524 std::optional<unsigned> Level)
const {
1525 const SCEV *SrcCoeff = Src->getStepRecurrence(*SE);
1526 const SCEV *SrcConst = Src->getStart();
1527 const SCEV *DstCoeff = Dst->getStepRecurrence(*SE);
1528 const SCEV *DstConst = Dst->getStart();
1541 if (!ConstDelta || !ConstSrcCoeff || !ConstDstCoeff)
1546 APInt AM = ConstSrcCoeff->
getAPInt();
1547 APInt BM = ConstDstCoeff->
getAPInt();
1550 std::optional<bool> GCDRes =
findGCD(Bits, AM, BM, CM,
G,
X,
Y);
1563 std::optional<APInt> SrcUM =
1564 collectNonNegativeConstantUpperBound(Src->getLoop(), Delta->
getType());
1568 std::optional<APInt> DstUM =
1569 collectNonNegativeConstantUpperBound(Dst->getLoop(), Delta->
getType());
1573 OverflowSafeSignedAPInt TC = CM.
sdiv(
G);
1574 OverflowSafeSignedAPInt TX = OverflowSafeSignedAPInt(
X) * TC;
1575 OverflowSafeSignedAPInt TY = OverflowSafeSignedAPInt(
Y) * TC;
1576 if (!TC || !TX || !TY)
1600 auto GetMaxOrMin = [](
const OverflowSafeSignedAPInt &
V0,
1601 const OverflowSafeSignedAPInt &
V1,
1602 bool IsMin) -> std::optional<APInt> {
1609 return std::nullopt;
1612 std::optional<APInt> OptTL = GetMaxOrMin(TL0, TL1,
false);
1613 std::optional<APInt> OptTU = GetMaxOrMin(TU0, TU1,
true);
1614 if (!OptTL || !OptTU)
1617 APInt TL = std::move(*OptTL);
1618 APInt TU = std::move(*OptTU);
1627 assert(SrcUM == DstUM &&
"Expecting same upper bound for Src and Dst");
1631 OverflowSafeSignedAPInt LowerDistance, UpperDistance;
1632 OverflowSafeSignedAPInt OTY(TY), OTX(TX), OTA(TA), OTB(TB), OTL(TL), OTU(TU);
1636 LowerDistance = (OTY - OTX) + (OTA - OTB) * OTL;
1637 UpperDistance = (OTY - OTX) + (OTA - OTB) * OTU;
1639 LowerDistance = (OTY - OTX) + (OTA - OTB) * OTU;
1640 UpperDistance = (OTY - OTX) + (OTA - OTB) * OTL;
1643 if (!LowerDistance || !UpperDistance)
1646 LLVM_DEBUG(
dbgs() <<
"\t LowerDistance = " << *LowerDistance <<
"\n");
1647 LLVM_DEBUG(
dbgs() <<
"\t UpperDistance = " << *UpperDistance <<
"\n");
1649 if (LowerDistance->sle(0) && UpperDistance->sge(0))
1651 if (LowerDistance->slt(0))
1653 if (UpperDistance->sgt(0))
1671bool DependenceInfo::testSIV(
const SCEV *Src,
const SCEV *Dst,
unsigned &Level,
1673 bool UnderRuntimeAssumptions) {
1678 if (SrcAddRec && DstAddRec) {
1682 [[maybe_unused]]
const Loop *CurDstLoop = DstAddRec->
getLoop();
1683 assert(haveSameSD(CurSrcLoop, CurDstLoop) &&
1684 "Loops in the SIV test should have the same iteration space and "
1686 Level = mapSrcLoop(CurSrcLoop);
1687 bool disproven =
false;
1688 if (SrcCoeff == DstCoeff)
1689 disproven = strongSIVtest(SrcAddRec, DstAddRec, Level, Result,
1690 UnderRuntimeAssumptions);
1691 else if (SrcCoeff == SE->getNegativeSCEV(DstCoeff))
1692 disproven = weakCrossingSIVtest(SrcAddRec, DstAddRec, Level, Result);
1693 return disproven || exactSIVtest(SrcAddRec, DstAddRec, Level, Result);
1697 Level = mapSrcLoop(CurSrcLoop);
1698 return weakZeroDstSIVtest(SrcAddRec, Dst, Level, Result);
1702 Level = mapDstLoop(CurDstLoop);
1703 return weakZeroSrcSIVtest(Src, DstAddRec, Level, Result);
1719bool DependenceInfo::testRDIV(
const SCEV *Src,
const SCEV *Dst,
1725 assert(SrcAddRec && DstAddRec &&
"Unexpected non-addrec input");
1726 return exactRDIVtest(SrcAddRec, DstAddRec, Result) ||
1727 gcdMIVtest(Src, Dst, Result);
1733bool DependenceInfo::testMIV(
const SCEV *Src,
const SCEV *Dst,
1738 return gcdMIVtest(Src, Dst, Result) ||
1739 banerjeeMIVtest(Src, Dst,
Loops, Result);
1752 if (Product->hasNoSignedWrap())
1754 return std::nullopt;
1757const SCEV *DependenceInfo::accumulateCoefficientsGCD(
const SCEV *Expr,
1758 const Loop *CurLoop,
1759 const SCEV *&CurLoopCoeff,
1760 APInt &RunningGCD)
const {
1763 assert(isLoopInvariant(Expr, CurLoop) &&
1764 "Expected loop invariant expression");
1771 if (AddRec->
getLoop() == CurLoop) {
1772 CurLoopCoeff = Step;
1786 return accumulateCoefficientsGCD(Start, CurLoop, CurLoopCoeff, RunningGCD);
1806bool DependenceInfo::gcdMIVtest(
const SCEV *Src,
const SCEV *Dst,
1813 unsigned BitWidth = SE->getTypeSizeInBits(Src->getType());
1816 const SCEV *Dummy =
nullptr;
1817 const SCEV *SrcConst =
1818 accumulateCoefficientsGCD(Src,
nullptr, Dummy, RunningGCD);
1821 const SCEV *DstConst =
1822 accumulateCoefficientsGCD(Dst,
nullptr, Dummy, RunningGCD);
1833 APInt ConstDelta =
Constant->getAPInt();
1835 if (ConstDelta == 0)
1838 APInt Remainder = ConstDelta.
srem(RunningGCD);
1839 if (Remainder != 0) {
1853 bool Improved =
false;
1854 const SCEV *Coefficients = Src;
1855 while (
const SCEVAddRecExpr *AddRec =
1861 const SCEV *DstCoeff = SE->getZero(SrcCoeff->
getType());
1863 if (!accumulateCoefficientsGCD(Src, CurLoop, SrcCoeff, RunningGCD) ||
1864 !accumulateCoefficientsGCD(Dst, CurLoop, DstCoeff, RunningGCD))
1879 if (RunningGCD != 0) {
1880 Remainder = ConstDelta.
srem(RunningGCD);
1882 if (Remainder != 0) {
1883 unsigned Level = mapSrcLoop(CurLoop);
1884 Result.DV[
Level - 1].Direction &= ~Dependence::DVEntry::EQ;
1903struct BanerjeeInterval {
1907 BanerjeeInterval(
const SCEV *
Lower,
const SCEV *
Upper)
1910 bool isEmpty(ScalarEvolution &SE)
const {
1920 const BanerjeeInterval &
B,
1924 if (
A.Lower &&
B.Lower)
1926 if (
A.Upper &&
B.Upper)
1935 const BanerjeeInterval &
B,
1948 return BanerjeeInterval(
C,
C);
1966 return BanerjeeInterval(SE.
getSMinExpr(LowerValue, UpperValue),
1979 return BanerjeeInterval(
nullptr,
Zero);
1981 return BanerjeeInterval(
Zero,
nullptr);
1982 return BanerjeeInterval(
nullptr,
nullptr);
2043 assert(!
Values.empty() &&
"expected at least one value");
2067 for (
const SCEV *Subscript : {Src, Dst}) {
2095bool DependenceInfo::banerjeeMIVtest(
const SCEV *Src,
const SCEV *Dst,
2102 ++BanerjeeApplications;
2105 unsigned BaseBits = SE->getTypeSizeInBits(
BaseType);
2115 unsigned WideBits = 2 * BaseBits + MaxLevels + 1;
2117 const SCEV *
Zero = SE->getZero(WideType);
2119 CoefficientInfo EmptyCoeff{
Zero,
Zero,
nullptr};
2121 assert(
Loops.size() > MaxLevels &&
"loop bit vector is too small");
2123 "direction vector is too small for common levels");
2125 const SCEV *A0 = collectCoeffInfo(Src,
true, WideType, CI);
2126 const SCEV *
B0 = collectCoeffInfo(Dst,
false, WideType, CI);
2127 const SCEV *Delta = SE->getMinusSCEV(B0, A0);
2131 for (
unsigned K = 0;
K <= MaxLevels; ++
K) {
2135 for (
unsigned K = 1;
K <= MaxLevels; ++
K) {
2136 findBoundsALL(CI, Bound, K);
2137 findBoundsLT(CI, Bound, K);
2138 findBoundsEQ(CI, Bound, K);
2139 findBoundsGT(CI, Bound, K);
2143 ++BanerjeeIndependence;
2147 unsigned NewDeps = exploreDirections(1, Bound,
Loops, Delta, Result);
2149 ++BanerjeeIndependence;
2153 bool Improved =
false;
2154 for (
unsigned K = 1;
K <= CommonLevels; ++
K) {
2157 unsigned Old =
Result.DV[
K - 1].Direction;
2158 Result.DV[
K - 1].Direction = Old & Bound[
K].DirSet;
2159 Improved |= Old !=
Result.DV[
K - 1].Direction;
2160 if (!
Result.DV[K - 1].Direction) {
2161 ++BanerjeeIndependence;
2167 ++BanerjeeSuccesses;
2176DependenceInfo::collectCoeffInfo(
const SCEV *Subscript,
bool SrcFlag,
2179 SmallBitVector SeenLevels(MaxLevels + 1);
2182 SrcFlag ? mapSrcLoop(AddRec->
getLoop()) : mapDstLoop(AddRec->getLoop());
2183 assert(K > 0 && K <= MaxLevels &&
"invalid mapped loop level");
2184 assert(!SeenLevels[K] &&
"duplicate recurrence for loop level");
2188 const SCEV *&Coeff = SrcFlag ? CI[
K].SrcCoeff : CI[
K].DstCoeff;
2189 Coeff = SE->getNoopOrSignExtend(Step, WideType);
2191 const SCEV *MaxIterIndex = SE->getBackedgeTakenCount(AddRec->
getLoop());
2197 CI[
K].MaxIterIndex =
2198 SE->isKnownNonNegative(MaxIterIndex)
2199 ? SE->getNoopOrSignExtend(MaxIterIndex, WideType)
2200 : SE->getNoopOrZeroExtend(MaxIterIndex, WideType);
2205 return SE->getNoopOrSignExtend(Subscript, WideType);
2210 const SCEV *Sum = Bound[1].Lower[Bound[1].Direction];
2211 for (
unsigned K = 2; Sum &&
K <= MaxLevels; ++
K) {
2221 const SCEV *Sum = Bound[1].Upper[Bound[1].Direction];
2222 for (
unsigned K = 2; Sum &&
K <= MaxLevels; ++
K) {
2232bool DependenceInfo::testBounds(
unsigned char DirKind,
unsigned Level,
2234 const SCEV *Delta)
const {
2235 Bound[
Level].Direction = DirKind;
2236 for (
unsigned K = 1;
K <= MaxLevels; ++
K) {
2237 unsigned char Direction = Bound[
K].Direction;
2243 if (
const SCEV *
Lower = getLowerBound(Bound))
2246 if (
const SCEV *
Upper = getUpperBound(Bound))
2253unsigned DependenceInfo::exploreDirections(
unsigned Level,
2258 if (CommonLevels > Opts.da_miv_max_level_threshold) {
2259 LLVM_DEBUG(
dbgs() <<
"Number of common levels exceeded the threshold. MIV "
2260 "direction exploration is terminated.\n");
2261 for (
unsigned K = 1;
K <= CommonLevels; ++
K)
2267 if (Level > CommonLevels) {
2268 for (
unsigned K = 1;
K <= CommonLevels; ++
K)
2270 Bound[
K].DirSet |= Bound[
K].Direction;
2275 return exploreDirections(Level + 1, Bound,
Loops, Delta, Result);
2277 unsigned NewDeps = 0;
2278 unsigned OldDirections =
Result.DV[
Level - 1].Direction;
2281 if (!(OldDirections & Dir))
2283 if (testBounds(Dir, Level, Bound, Delta))
2284 NewDeps += exploreDirections(Level + 1, Bound,
Loops, Delta, Result);
2308 BanerjeeInterval SrcInterval =
2311 SE->getNegativeSCEV(CI[K].DstCoeff), CI[K].MaxIterIndex, *SE);
2330 CI[K].MaxIterIndex, *SE);
2351 const SCEV *ACoeff = CI[
K].SrcCoeff;
2352 const SCEV *BCoeff = CI[
K].DstCoeff;
2353 const SCEV *MaxIterIndex = CI[
K].MaxIterIndex;
2357 if (MaxIterIndex && MaxIterIndex->
isZero()) {
2359 }
else if (MaxIterIndex) {
2360 const SCEV *
Zero = SE->getZero(ACoeff->
getType());
2361 const SCEV *One = SE->getOne(ACoeff->
getType());
2362 const SCEV *MaxMinusOne = SE->getMinusSCEV(MaxIterIndex, One);
2369 MaxIterIndex, *SE));
2393 const SCEV *ACoeff = CI[
K].SrcCoeff;
2394 const SCEV *BCoeff = CI[
K].DstCoeff;
2395 const SCEV *MaxIterIndex = CI[
K].MaxIterIndex;
2399 if (MaxIterIndex && MaxIterIndex->
isZero()) {
2401 }
else if (MaxIterIndex) {
2402 const SCEV *
Zero = SE->getZero(ACoeff->
getType());
2403 const SCEV *One = SE->getOne(ACoeff->
getType());
2404 const SCEV *MaxMinusOne = SE->getMinusSCEV(MaxIterIndex, One);
2429 Loop *SrcLoop = LI->getLoopFor(Src->getParent());
2430 Loop *DstLoop = LI->getLoopFor(Dst->getParent());
2431 const SCEV *SrcAccessFn = SE->getSCEVAtScope(SrcPtr, SrcLoop);
2432 const SCEV *DstAccessFn = SE->getSCEVAtScope(DstPtr, DstLoop);
2433 const SCEVUnknown *SrcBase =
2435 const SCEVUnknown *DstBase =
2438 if (!SrcBase || !DstBase || SrcBase != DstBase)
2443 if (!tryDelinearizeFixedSize(Src, Dst, SrcAccessFn, DstAccessFn,
2444 SrcSubscripts, DstSubscripts) &&
2445 !tryDelinearizeParametricSize(Src, Dst, SrcAccessFn, DstAccessFn,
2446 SrcSubscripts, DstSubscripts))
2449 assert(isLoopInvariant(SrcBase, SrcLoop) &&
2450 isLoopInvariant(DstBase, DstLoop) &&
2451 "Expected SrcBase and DstBase to be loop invariant");
2455 dbgs() <<
"\nSrcSubscripts: ";
2456 for (
int I = 0;
I <
Size;
I++)
2457 dbgs() << *SrcSubscripts[
I];
2458 dbgs() <<
"\nDstSubscripts: ";
2459 for (
int I = 0;
I <
Size;
I++)
2460 dbgs() << *DstSubscripts[
I];
2469 for (
int I = 0;
I <
Size; ++
I) {
2470 Pair[
I].Src = SrcSubscripts[
I];
2471 Pair[
I].Dst = DstSubscripts[
I];
2473 assert(Pair[
I].Src->getType() == Pair[
I].Dst->getType() &&
2474 "Unexpected different types for the subscripts");
2483bool DependenceInfo::tryDelinearizeFixedSize(
2488 const SCEVUnknown *SrcBase =
2490 const SCEVUnknown *DstBase =
2492 assert(SrcBase && DstBase && SrcBase == DstBase &&
2493 "expected src and dst scev unknowns to be equal");
2496 const SCEV *ElemSize = SE->getElementSize(Src);
2497 assert(ElemSize == SE->getElementSize(Dst) &&
"Different element sizes");
2500 SrcSubscripts, SrcSizes, ElemSize) ||
2502 DstSubscripts, DstSizes, ElemSize))
2507 if (SrcSizes.
size() != DstSizes.
size() ||
2508 !std::equal(SrcSizes.
begin(), SrcSizes.
end(), DstSizes.
begin())) {
2509 SrcSubscripts.
clear();
2510 DstSubscripts.
clear();
2515 "Expected equal number of entries in the list of SrcSubscripts and "
2524 if (Opts.da_delinearization_checks) {
2527 SrcSubscripts.
clear();
2528 DstSubscripts.
clear();
2533 dbgs() <<
"Delinearized subscripts of fixed-size array\n"
2540bool DependenceInfo::tryDelinearizeParametricSize(
2545 const SCEVUnknown *SrcBase =
2547 const SCEVUnknown *DstBase =
2549 assert(SrcBase && DstBase && SrcBase == DstBase &&
2550 "expected src and dst scev unknowns to be equal");
2552 const SCEV *ElementSize = SE->getElementSize(Src);
2553 if (ElementSize != SE->getElementSize(Dst))
2556 const SCEV *SrcSCEV = SE->getMinusSCEV(SrcAccessFn, SrcBase);
2557 const SCEV *DstSCEV = SE->getMinusSCEV(DstAccessFn, DstBase);
2578 if (SrcSubscripts.
size() < 2 || DstSubscripts.
size() < 2 ||
2579 SrcSubscripts.
size() != DstSubscripts.
size())
2588 if (Opts.da_delinearization_checks)
2602 for (
unsigned VI : BV.
set_bits()) {
2612 FunctionAnalysisManager::Invalidator &Inv) {
2619 return Inv.invalidate<
AAManager>(F, PA) ||
2624void DependenceInfo::updateLoopAliasScopes(
const Loop *L) {
2625 if (!L || !AlreadyCheckedLoops.insert(L).second)
2630 Intrinsic::experimental_noalias_scope_decl))
2643 for (
Metadata *
Op : Decl->getScopeList()->operands())
2648 updateLoopAliasScopes(
L->getParentLoop());
2660std::unique_ptr<Dependence>
2662 bool UnderRuntimeAssumptions) {
2664 bool PossiblyLoopIndependent =
true;
2666 PossiblyLoopIndependent =
false;
2668 if (!(Src->mayReadOrWriteMemory() && Dst->mayReadOrWriteMemory()))
2674 LLVM_DEBUG(
dbgs() <<
"can only handle simple loads and stores\n");
2675 return std::make_unique<Dependence>(Src, Dst,
2682 updateLoopAliasScopes(LI->getLoopFor(Src->getParent()));
2683 updateLoopAliasScopes(LI->getLoopFor(Dst->getParent()));
2691 return std::make_unique<Dependence>(Src, Dst,
2705 LLVM_DEBUG(
dbgs() <<
"can't analyze must alias with different sizes\n");
2706 return std::make_unique<Dependence>(Src, Dst,
2712 const SCEV *SrcSCEV = SE->getSCEV(SrcPtr);
2713 const SCEV *DstSCEV = SE->getSCEV(DstPtr);
2716 const SCEV *SrcBase = SE->getPointerBase(SrcSCEV);
2717 const SCEV *DstBase = SE->getPointerBase(DstSCEV);
2718 if (SrcBase != DstBase) {
2725 LLVM_DEBUG(
dbgs() <<
"can't analyze SCEV with different pointer base\n");
2726 return std::make_unique<Dependence>(Src, Dst,
2734 Loop *SrcLoop = LI->getLoopFor(Src->getParent());
2735 Loop *DstLoop = LI->getLoopFor(Dst->getParent());
2736 if (!isLoopInvariant(SrcBase, SrcLoop) ||
2737 !isLoopInvariant(DstBase, DstLoop)) {
2738 LLVM_DEBUG(
dbgs() <<
"The base pointer is not loop invariant.\n");
2739 return std::make_unique<Dependence>(Src, Dst,
2744 const SCEV *SrcEv = SE->getMinusSCEV(SrcSCEV, SrcBase);
2745 const SCEV *DstEv = SE->getMinusSCEV(DstSCEV, DstBase);
2749 if (!SE->isKnownMultipleOf(SrcEv, EltSize,
2750 UnderRuntimeAssumptions ? &Assume :
nullptr) ||
2751 !SE->isKnownMultipleOf(DstEv, EltSize,
2752 UnderRuntimeAssumptions ? &Assume :
nullptr)) {
2753 LLVM_DEBUG(
dbgs() <<
"can't analyze SCEV with different offsets\n");
2754 return std::make_unique<Dependence>(Src, Dst,
2760 Pair[0].Src = SrcEv;
2761 Pair[0].Dst = DstEv;
2762 if (Opts.da_delinearize) {
2763 if (tryDelinearize(Src, Dst, Pair)) {
2765 Pairs = Pair.
size();
2770 establishNestingLevels(Src, Dst);
2772 LLVM_DEBUG(
dbgs() <<
" common nesting levels = " << CommonLevels <<
"\n");
2773 LLVM_DEBUG(
dbgs() <<
" maximum nesting levels = " << MaxLevels <<
"\n");
2774 LLVM_DEBUG(
dbgs() <<
" SameSD nesting levels = " << SameSDLevels <<
"\n");
2777 CommonLevels += SameSDLevels;
2778 MaxLevels -= SameSDLevels;
2779 if (SameSDLevels > 0) {
2782 for (
unsigned P = 0;
P < Pairs; ++
P) {
2784 Subscript::ClassificationKind TestClass =
2785 classifyPair(Pair[
P].Src, SrcLoop, Pair[
P].Dst, DstLoop,
Loops);
2787 if (TestClass != Subscript::ZIV && TestClass != Subscript::SIV &&
2788 TestClass != Subscript::RDIV) {
2790 CommonLevels -= SameSDLevels;
2791 MaxLevels += SameSDLevels;
2798 if (SameSDLevels > 0)
2802 PossiblyLoopIndependent, CommonLevels);
2805 for (
unsigned P = 0;
P < Pairs; ++
P) {
2806 assert(Pair[
P].Src->getType()->isIntegerTy() &&
"Src must be an integer");
2807 assert(Pair[
P].Dst->getType()->isIntegerTy() &&
"Dst must be an integer");
2808 Pair[
P].Loops.
resize(MaxLevels + 1);
2809 Pair[
P].Classification =
2810 classifyPair(Pair[
P].Src, SrcLoop, Pair[
P].Dst, DstLoop, Pair[
P].
Loops);
2820 for (
unsigned SI = 0;
SI < Pairs; ++
SI) {
2829 switch (Pair[
SI].Classification) {
2830 case Subscript::NonLinear:
2832 ++NonlinearSubscriptPairs;
2833 collectCommonLoops(Pair[
SI].Src, SrcLoop, Pair[
SI].
Loops);
2834 collectCommonLoops(Pair[
SI].Dst, DstLoop, Pair[
SI].
Loops);
2836 case Subscript::ZIV:
2838 if (testZIV(Pair[
SI].Src, Pair[
SI].Dst, Result))
2841 case Subscript::SIV: {
2844 if (testSIV(Pair[
SI].Src, Pair[
SI].Dst, Level, Result,
2845 UnderRuntimeAssumptions))
2849 case Subscript::RDIV:
2851 if (testRDIV(Pair[
SI].Src, Pair[
SI].Dst, Result))
2854 case Subscript::MIV:
2856 if (testMIV(Pair[
SI].Src, Pair[
SI].Dst, Pair[
SI].
Loops, Result))
2864 for (
unsigned SI = 0;
SI < Pairs; ++
SI)
2865 CompleteLoops |= Pair[
SI].
Loops;
2866 for (
unsigned II = 1;
II <= CommonLevels; ++
II)
2867 if (CompleteLoops[
II])
2868 Result.DV[
II - 1].Scalar =
false;
2873 for (
unsigned II = 1;
II <= Result.getLevels(); ++
II) {
2875 if (Result.DV[
II - 1].Distance ==
nullptr)
2876 Result.DV[
II - 1].Distance = SE->getZero(SrcSCEV->
getType());
2878 assert(Result.DV[
II - 1].Distance->isZero() &&
2879 "Inconsistency between distance and direction");
2885 const SCEV *Distance = Result.getDistance(
II);
2886 if (Distance && Distance->
isZero())
2888 "Distance is zero, but direction is not EQ");
2892 if (SameSDLevels > 0) {
2895 assert(CommonLevels >= SameSDLevels);
2896 CommonLevels -= SameSDLevels;
2897 MaxLevels += SameSDLevels;
2898 std::unique_ptr<FullDependence::DVEntry[]> DV, DVSameSD;
2899 DV = std::make_unique<FullDependence::DVEntry[]>(CommonLevels);
2900 DVSameSD = std::make_unique<FullDependence::DVEntry[]>(SameSDLevels);
2901 for (
unsigned Level = 0; Level < CommonLevels; ++Level)
2902 DV[Level] = Result.DV[Level];
2903 for (
unsigned Level = 0; Level < SameSDLevels; ++Level)
2904 DVSameSD[Level] = Result.DV[CommonLevels + Level];
2905 Result.DV = std::move(DV);
2906 Result.DVSameSD = std::move(DVSameSD);
2907 Result.Levels = CommonLevels;
2908 Result.SameSDLevels = SameSDLevels;
2911 if (PossiblyLoopIndependent) {
2915 for (
unsigned II = 1;
II <= CommonLevels; ++
II) {
2917 Result.LoopIndependent =
false;
2925 bool AllEqual =
true;
2926 for (
unsigned II = 1;
II <= CommonLevels; ++
II) {
2932 if (AllEqual && Result.Assumptions.getPredicates().empty())
2936 return std::make_unique<FullDependence>(std::move(Result));
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
bpf unwind BPF Unwind Lower
static GCRegistry::Add< ShadowStackGC > C("shadow-stack", "Very portable GC for uncooperative code generators")
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static bool isLoadOrStore(const Instruction *I)
static std::optional< bool > findGCD(unsigned Bits, const APInt &AM, const APInt &BM, const APInt &Delta, APInt &G, APInt &X, APInt &Y)
static OverflowSafeSignedAPInt floorOfQuotient(const OverflowSafeSignedAPInt &OA, const OverflowSafeSignedAPInt &OB)
static void dumpExampleDependence(raw_ostream &OS, DependenceInfo *DA, ScalarEvolution &SE, LoopInfo &LI, bool NormalizeResults)
static OverflowSafeSignedAPInt ceilingOfQuotient(const OverflowSafeSignedAPInt &OA, const OverflowSafeSignedAPInt &OB)
static void dumpSmallBitVector(SmallBitVector &BV)
static BanerjeeInterval emptyInterval(Type *Ty, ScalarEvolution &SE)
Return the canonical empty interval [1, 0].
static std::pair< OverflowSafeSignedAPInt, OverflowSafeSignedAPInt > inferDomainOfAffine(OverflowSafeSignedAPInt A, OverflowSafeSignedAPInt B, OverflowSafeSignedAPInt UB)
Given an affine expression of the form A*k + B, where k is an arbitrary integer, infer the possible r...
static MDNode * adjustAliasScopeList(MDNode *ScopeList, const SmallPtrSetImpl< const MDNode * > &LoopAliasScopes)
Drop alias scopes that are only valid within a single loop iteration.
static const SCEV * minusSCEVNoSignedOverflow(const SCEV *A, const SCEV *B, ScalarEvolution &SE)
Returns A - B if it guaranteed not to signed wrap.
static AliasResult underlyingObjectsAlias(AAResults *AA, const DataLayout &DL, const MemoryLocation &LocA, const MemoryLocation &LocB, const SmallPtrSetImpl< const MDNode * > &LoopAliasScopes)
static BanerjeeInterval constantInterval(const SCEV *C)
Return the singleton interval containing C.
static Type * getBanerjeeBaseType(const SCEV *Src, const SCEV *Dst, ScalarEvolution &SE)
Return the widest type used by a subscript or by an exact backedge-taken count of one of its recurren...
static BanerjeeInterval variableInterval(const SCEV *Coeff, const SCEV *Upper, ScalarEvolution &SE)
Compute the range of Coeff * X for 0 <= X <= Upper.
static std::optional< APInt > getConstantCoefficient(const SCEV *Expr)
Given a SCEVMulExpr, returns its first operand if its first operand is a constant and the product doe...
static BanerjeeInterval strictDirectionIntervalWithUnknownUpperBound(const SCEV *ACoeff, const SCEV *BCoeff, unsigned char Direction, ScalarEvolution &SE)
Compute any finite one-sided bound on.
static const SCEV * evaluateSubscriptDifference(const SCEV *A, const SCEV *SrcIndex, const SCEV *B, const SCEV *DstIndex, ScalarEvolution &SE)
Evaluate one loop level's contribution A * SrcIndex - B * DstIndex to the complete source-minus-desti...
static bool isRemainderZero(const SCEVConstant *Dividend, const SCEVConstant *Divisor)
static BanerjeeInterval signedRangeInterval(const SCEV *Coeff, const SCEV *Lower, const SCEV *Upper, ScalarEvolution &SE)
Compute the range of Coeff * X for Lower <=s X <=s Upper.
static BanerjeeInterval intervalFromValues(ArrayRef< const SCEV * > Values, ScalarEvolution &SE)
Return the smallest closed interval containing Values.
static bool isDependenceTestEnabled(const AnalysisOptions &Opts, DependenceTestType Test)
Returns true iff Test is enabled.
static BanerjeeInterval addIntervals(const BanerjeeInterval &A, const BanerjeeInterval &B, ScalarEvolution &SE)
Add two intervals.
static BanerjeeInterval intersectIntervals(const BanerjeeInterval &A, const BanerjeeInterval &B, ScalarEvolution &SE)
Intersect two intervals.
static MemoryLocation adjustLoc(MemoryLocation Loc, const SmallPtrSetImpl< const MDNode * > &LoopAliasScopes)
Module.h This file contains the declarations for the Module class.
Loop::LoopBounds::Direction Direction
std::pair< uint64_t, uint64_t > Interval
uint64_t IntrinsicInst * II
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)
BaseType
A given derived pointer can have multiple base pointers through phi/selects.
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
static TableGen::Emitter::Opt Y("gen-skeleton-entry", EmitSkeleton, "Generate example skeleton entry")
A manager for alias analyses.
A wrapper pass to provide the legacy pass manager access to a suitably prepared AAResults object.
Class for arbitrary precision integers.
bool isMinSignedValue() const
Determine if this is the smallest signed value.
static LLVM_ABI 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.
LLVM_ABI APInt sdiv(const APInt &RHS) const
Signed division function for APInt.
LLVM_ABI APInt srem(const APInt &RHS) const
Function for signed remainder operation.
bool isNonNegative() const
Determine if this APInt Value is non-negative (>= 0)
bool slt(const APInt &RHS) const
Signed less than comparison.
static APInt getZero(unsigned numBits)
Get the '0' value for the specified bit-width.
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 <aparticular IR unit>" (e....
Represent the analysis usage information of a pass.
void setPreservesAll()
Set by analyses that do not transform their input at all.
AnalysisUsage & addRequiredTransitive()
Represent a constant reference to an array (0 or more elements consecutively in memory),...
LLVM Basic Block Representation.
This class is a wrapper over an AAResults, and it is intended to be used only when there are no IR ch...
void enableCrossIterationMode()
Assume that values may come from different cycle iterations.
bool isNoAlias(const MemoryLocation &LocA, const MemoryLocation &LocB)
@ ICMP_SGT
signed greater than
This class represents a range of values.
LLVM_ABI bool isEmptySet() const
Return true if this set contains no members.
bool isSingleElement() const
Return true if this set contains exactly one member.
LLVM_ABI ConstantRange intersectWith(const ConstantRange &CR, PreferredRangeType Type=Smallest) const
Return the range that results from the intersection of this range with another range.
This is an important base class in LLVM.
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
DependenceAnalysisWrapperPass()
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.
LLVM_ABI Result run(Function &F, FunctionAnalysisManager &FAM)
DependenceInfo - This class is the main dependence-analysis driver.
LLVM_ABI bool invalidate(Function &F, const PreservedAnalyses &PA, FunctionAnalysisManager::Invalidator &Inv)
Handle transitive invalidation when the cached analysis results go away.
LLVM_ABI DependenceInfo(Function *F, AAResults *AA, ScalarEvolution *SE, LoopInfo *LI)
LLVM_ABI std::unique_ptr< Dependence > depends(Instruction *Src, Instruction *Dst, bool UnderRuntimeAssumptions=false)
depends - Tests for a dependence between the Src and Dst instructions.
void dumpImp(raw_ostream &OS, bool IsSameSD=false) const
dumpImp - For debugging purposes.
Dependence(Dependence &&)=default
SCEVUnionPredicate getRuntimeAssumptions() const
getRuntimeAssumptions - Returns the runtime assumptions under which this Dependence relation is valid...
virtual bool isConfused() const
isConfused - Returns true if this dependence is confused (the compiler understands nothing and makes ...
virtual unsigned getSameSDLevels() const
getSameSDLevels - Returns the number of separate SameSD loops surrounding the source and destination ...
virtual const SCEV * getDistance(unsigned Level, bool SameSD=false) const
getDistance - Returns the distance (or NULL) associated with a particular common or SameSD level.
virtual unsigned getLevels() const
getLevels - Returns the number of common loops surrounding the source and destination of the dependen...
virtual unsigned getDirection(unsigned Level, bool SameSD=false) const
getDirection - Returns the direction associated with a particular common or SameSD level.
virtual bool isScalar(unsigned Level, bool SameSD=false) const
isScalar - Returns true if a particular regular or SameSD level is scalar; that is,...
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.
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.
virtual bool inSameSDLoops(unsigned Level) const
inSameSDLoops - Returns true if this level is an SameSD level, i.e., performed across two separate lo...
Class representing an expression and its matching format.
FullDependence - This class represents a dependence between two memory references in a function.
FullDependence(Instruction *Source, Instruction *Destination, const SCEVUnionPredicate &Assumes, bool PossiblyLoopIndependent, unsigned Levels)
unsigned getDirection(unsigned Level, bool SameSD=false) const override
getDirection - Returns the direction associated with a particular common or SameSD level.
bool isScalar(unsigned Level, bool SameSD=false) const override
isScalar - Returns true if a particular regular or SameSD level is scalar; that is,...
bool isDirectionNegative() const override
Check if the direction vector is negative.
void negate(ScalarEvolution &SE) override
Negate the dependence by swapping the source and destination, and reversing the direction and distanc...
const SCEV * getDistance(unsigned Level, bool SameSD=false) const override
getDistance - Returns the distance (or NULL) associated with a particular common or SameSD level.
DVEntry getDVEntry(unsigned Level, bool IsSameSD) const
getDVEntry - Returns the DV entry associated with a regular or a SameSD level.
bool inSameSDLoops(unsigned Level) const override
inSameSDLoops - Returns true if this level is an SameSD level, i.e., performed across two separate lo...
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.
static LLVM_ABI IntegerType * get(LLVMContext &C, unsigned NumBits)
This static method is the primary way of constructing an IntegerType.
An instruction for reading from memory.
Analysis pass that exposes the LoopInfo for a function.
BlockT * getLoopLatch() const
If there is a single latch block for this loop, return it.
const LoopT * getOutermostLoop() const
Get the outermost loop in which this loop is contained.
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.
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.
Represents a single loop in the control flow graph.
ArrayRef< MDOperand > operands() const
Representation for a specific memory location.
static LLVM_ABI MemoryLocation get(const LoadInst *LI)
Return a location with information about the memory reference by the given instruction.
LocationSize Size
The maximum size of the location, in address-units, or UnknownSize if the size is not known.
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.
Represent a mutable reference to an array (0 or more elements consecutively in memory),...
AnalysisType & getAnalysis() const
getAnalysis<AnalysisType>() - This function is used by subclasses to get to the analysis information ...
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 a polynomial recurrence on the trip count of the specified loop.
LLVM_ABI const SCEV * evaluateAtIteration(const SCEV *It, ScalarEvolution &SE) const
Return the value of this chain of recurrences at the specified iteration number.
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
SCEVUse getStepRecurrence(ScalarEvolution &SE) const
Constructs and returns the recurrence indicating how much this expression steps by.
This class represents a constant integer value.
const APInt & getAPInt() const
bool hasNoSignedWrap() const
This class represents a composition of other SCEV predicates, and is the class that most clients will...
This class represents an analyzed expression in the program.
LLVM_ABI bool isOne() const
Return true if the expression is a constant one.
LLVM_ABI 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.
LLVM_ABI bool isKnownNonNegative(const SCEV *S)
Test if the given expression is known to be non-negative.
LLVM_ABI Type * getWiderType(Type *Ty1, Type *Ty2) const
LLVM_ABI bool isKnownNonPositive(const SCEV *S)
Test if the given expression is known to be non-positive.
LLVM_ABI bool isKnownNegative(const SCEV *S)
Test if the given expression is known to be negative.
LLVM_ABI 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...
LLVM_ABI const SCEV * getSMinExpr(SCEVUse LHS, SCEVUse RHS)
const SCEV * getZero(Type *Ty)
Return a SCEV for the constant 0 of a specific type.
LLVM_ABI bool willNotOverflow(Instruction::BinaryOps BinOp, bool Signed, const SCEV *LHS, const SCEV *RHS, const Instruction *CtxI=nullptr)
Is operation BinOp between LHS and RHS provably does not have a signed/unsigned overflow (Signed)?
LLVM_ABI const SCEV * getMinusSCEV(SCEVUse LHS, SCEVUse RHS, SCEVFlags Flags=SCEV::FlagNone, unsigned Depth=0)
Return LHS-RHS.
const SCEV * getOne(Type *Ty)
Return a SCEV for the constant 1 of a specific type.
LLVM_ABI SCEVUse getAddExpr(SmallVectorImpl< SCEVUse > &Ops, SCEVFlagsPair Flags={}, unsigned Depth=0)
Get a canonical add expression, or something simpler if possible.
LLVM_ABI SCEVUse getMulExpr(SmallVectorImpl< SCEVUse > &Ops, SCEVFlagsPair Flags={}, unsigned Depth=0)
Get a canonical multiply expression, or something simpler if possible.
LLVM_ABI bool isKnownPredicate(CmpPredicate Pred, SCEVUse LHS, SCEVUse RHS)
Test if the given expression is known to satisfy the condition described by Pred, LHS,...
LLVM_ABI const SCEV * getSMaxExpr(SCEVUse LHS, SCEVUse RHS)
LLVM_ABI const SCEV * getNegativeSCEV(const SCEV *V, SCEVFlags Flags=SCEV::FlagNone)
Return the SCEV object corresponding to -V.
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.
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
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.
LLVM_ABI Value(Type *Ty, unsigned scid)
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.
Abstract Attribute helper functions.
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.
LLVM_ABI APInt GreatestCommonDivisor(APInt A, APInt B, bool IsSigned=false)
Compute GCD of two APInt values.
constexpr bool operator!(E Val)
@ BasicBlock
Various leaf nodes.
LLVM_ABI StringRef getName(ID id)
Return the LLVM name for an intrinsic, such as "llvm.ppc.altivec.lvx".
@ TB
TB - TwoByte - Set if this instruction has a two byte opcode, which starts with a 0x0F byte before th...
This is an optimization pass for GlobalISel generic memory operations.
InstIterator< SymbolTableList< BasicBlock >, Function::iterator, BasicBlock::iterator, Instruction > inst_iterator
LLVM_ABI void collectParametricTerms(ScalarEvolution &SE, const SCEV *Expr, SmallVectorImpl< const SCEV * > &Terms)
Collect parametric terms occurring in step expressions (first step of delinearization).
LLVM_ABI void findArrayDimensions(ScalarEvolution &SE, SmallVectorImpl< const SCEV * > &Terms, SmallVectorImpl< const SCEV * > &Sizes, const SCEV *ElementSize)
Compute the array dimensions Sizes from the set of Terms extracted from the memory access function of...
RelativeUniformCounterPtr Values
decltype(auto) dyn_cast(const From &Val)
dyn_cast<X> - Return the argument parameter cast to the specified type.
APInt operator*(APInt a, uint64_t RHS)
const Value * getLoadStorePointerOperand(const Value *V)
A helper function that returns the pointer operand of a load or store instruction.
inst_iterator inst_begin(Function *F)
LLVM_ABI bool validateDelinearizationResult(ScalarEvolution &SE, ArrayRef< const SCEV * > Sizes, ArrayRef< const SCEV * > Subscripts)
Check that each subscript in Subscripts is within the corresponding size in Sizes.
RelativeUniformCounterPtr ValuesPtrExpr VTableAddr Value
const AnalysisOptions & getAnalysisOptions(const LLVMContext &C)
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
LLVM_ABI void computeAccessFunctions(ScalarEvolution &SE, const SCEV *Expr, SmallVectorImpl< const SCEV * > &Subscripts, SmallVectorImpl< const SCEV * > &Sizes)
Return in Subscripts the access functions for each dimension in Sizes (third step of delinearization)...
LLVM_ABI bool delinearizeFixedSizeArray(ScalarEvolution &SE, const SCEV *Expr, SmallVectorImpl< const SCEV * > &Subscripts, SmallVectorImpl< const SCEV * > &Sizes, const SCEV *ElementSize)
Split this SCEVAddRecExpr into two vectors of SCEVs representing the subscripts and sizes of an acces...
LLVM_ABI raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
class LLVM_GSL_OWNER SmallVector
Forward declaration of SmallVector so that calculateSmallVectorDefaultInlinedElements can reference s...
LLVM_ABI const Value * getUnderlyingObject(const Value *V, unsigned MaxLookup=MaxLookupSearchDepth, bool MustPreserveProvenance=false)
This method strips off any GEP address adjustments, pointer casts or llvm.threadlocal....
bool isa(const From &Val)
isa<X> - Return true if the parameter to the template is an instance of one of the template type argu...
inst_iterator inst_end(Function *F)
DWARFExpression::Operation Op
constexpr unsigned BitWidth
decltype(auto) cast(const From &Val)
cast<X> - Return the argument parameter cast to the specified type.
APInt operator+(APInt a, const APInt &b)
AnalysisManager< Function > FunctionAnalysisManager
Convenience typedef for the Function analysis manager.
LLVM_ABI bool isIdentifiedObject(const Value *V)
Return true if this pointer refers to a distinct and identifiable object.
LLVM_ABI FunctionPass * createDependenceAnalysisWrapperPass()
createDependenceAnalysisPass - This creates an instance of the DependenceAnalysis wrapper pass.
Implement std::hash so that hash_code can be used in STL containers.
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
MDNode * Scope
The tag for alias scope specification (used with noalias).
MDNode * NoAlias
The tag specifying the noalias scope.
A special type used by analysis passes to provide an address that identifies that particular analysis...
LLVM_ABI PreservedAnalyses run(Function &F, FunctionAnalysisManager &FAM)
Dependence::DVEntry - Each level in the distance/direction vector has a direction (or perhaps a union...