120 cl::desc(
"If set to true, IRCE may eliminate wide range checks in loops " 121 "with narrow latch condition."));
125 #define DEBUG_TYPE "irce" 139 class InductiveRangeCheck {
141 const SCEV *Begin =
nullptr;
142 const SCEV *Step =
nullptr;
143 const SCEV *End =
nullptr;
144 Use *CheckUse =
nullptr;
145 bool IsSigned =
true;
157 const SCEV *getBegin()
const {
return Begin; }
158 const SCEV *getStep()
const {
return Step; }
159 const SCEV *getEnd()
const {
return End; }
160 bool isSigned()
const {
return IsSigned; }
163 OS <<
"InductiveRangeCheck:\n";
170 OS <<
"\n CheckUse: ";
171 getCheckUse()->getUser()->print(OS);
172 OS <<
" Operand: " << getCheckUse()->getOperandNo() <<
"\n";
180 Use *getCheckUse()
const {
return CheckUse; }
190 Range(
const SCEV *Begin,
const SCEV *End) : Begin(Begin), End(End) {
195 const SCEV *getBegin()
const {
return Begin; }
196 const SCEV *getEnd()
const {
return End; }
209 bool getPassingDirection() {
return true; }
216 bool IsLatchSigned)
const;
229 class InductiveRangeCheckElimination {
239 : SE(SE), BPI(BPI), DT(DT), LI(LI) {}
244 class IRCELegacyPass :
public LoopPass {
265 "Inductive range check elimination",
false,
false)
276 InductiveRangeCheck::parseRangeCheckICmp(
Loop *L,
ICmpInst *ICI,
278 Value *&Length,
bool &IsSigned) {
279 auto IsLoopInvariant = [&SE, L](
Value *V) {
280 return SE.isLoopInvariant(SE.getSCEV(V), L);
284 Value *LHS = ICI->getOperand(0);
285 Value *RHS = ICI->getOperand(1);
296 if (
match(RHS, m_ConstantInt<0>())) {
307 if (
match(RHS, m_ConstantInt<-1>())) {
312 if (IsLoopInvariant(LHS)) {
324 if (IsLoopInvariant(LHS)) {
335 void InductiveRangeCheck::extractRangeChecksFromCond(
339 Value *Condition = ConditionUse.
get();
340 if (!Visited.
insert(Condition).second)
345 extractRangeChecksFromCond(L, SE, cast<User>(Condition)->getOperandUse(0),
347 extractRangeChecksFromCond(L, SE, cast<User>(Condition)->getOperandUse(1),
358 if (!parseRangeCheckICmp(L, ICI, SE,
Index, Length, IsSigned))
363 IndexAddRec && (IndexAddRec->getLoop() == L) && IndexAddRec->
isAffine();
368 const SCEV *End =
nullptr;
377 unsigned BitWidth = cast<IntegerType>(IndexAddRec->getType())->
getBitWidth();
382 InductiveRangeCheck IRC;
384 IRC.Begin = IndexAddRec->getStart();
385 IRC.Step = IndexAddRec->getStepRecurrence(SE);
386 IRC.CheckUse = &ConditionUse;
387 IRC.IsSigned = IsSigned;
391 void InductiveRangeCheck::extractRangeChecksFromBranch(
404 InductiveRangeCheck::extractRangeChecksFromCond(L, SE, BI->
getOperandUse(0),
417 Context, {
MDString::get(Context,
"llvm.loop.unroll.disable")});
422 {
MDString::get(Context,
"llvm.loop.vectorize.enable"), FalseVal});
424 Context, {
MDString::get(Context,
"llvm.loop.licm_versioning.disable")});
427 {
MDString::get(Context,
"llvm.loop.distribute.enable"), FalseVal});
430 DisableLICMVersioning, DisableDistribution});
443 struct LoopStructure {
444 const char *Tag =
"";
464 Value *IndVarBase =
nullptr;
465 Value *IndVarStart =
nullptr;
466 Value *IndVarStep =
nullptr;
467 Value *LoopExitAt =
nullptr;
468 bool IndVarIncreasing =
false;
469 bool IsSignedPredicate =
true;
471 LoopStructure() =
default;
473 template <
typename M> LoopStructure map(M Map)
const {
474 LoopStructure Result;
476 Result.Header = cast<BasicBlock>(Map(Header));
477 Result.Latch = cast<BasicBlock>(Map(Latch));
478 Result.LatchBr = cast<BranchInst>(Map(LatchBr));
479 Result.LatchExit = cast<BasicBlock>(Map(LatchExit));
480 Result.LatchBrExitIdx = LatchBrExitIdx;
481 Result.IndVarBase = Map(IndVarBase);
482 Result.IndVarStart = Map(IndVarStart);
483 Result.IndVarStep = Map(IndVarStep);
484 Result.LoopExitAt = Map(LoopExitAt);
485 Result.IndVarIncreasing = IndVarIncreasing;
486 Result.IsSignedPredicate = IsSignedPredicate;
492 Loop &,
const char *&);
503 class LoopConstrainer {
507 std::vector<BasicBlock *> Blocks;
513 LoopStructure Structure;
518 struct RewrittenRangeInfo {
521 std::vector<PHINode *> PHIValuesAtPseudoExit;
524 RewrittenRangeInfo() =
default;
554 void cloneLoop(ClonedLoop &CLResult,
const char *Tag)
const;
558 Loop *createClonedLoopStructure(
Loop *Original,
Loop *Parent,
583 changeIterationSpaceEnd(
const LoopStructure &
LS,
BasicBlock *Preheader,
590 const char *Tag)
const;
596 void rewriteIncomingValuesForPHIs(
597 LoopStructure &LS,
BasicBlock *ContinuationBlockAndPreheader,
598 const LoopConstrainer::RewrittenRangeInfo &RRI)
const;
617 const SCEV *LatchTakenCount =
nullptr;
625 InductiveRangeCheck::Range Range;
629 LoopStructure MainLoopStructure;
637 SE(SE), DT(DT), LI(LI), LPMAddNewLoop(LPMAddNewLoop), OriginalLoop(L),
638 Range(R), MainLoopStructure(LS) {}
656 const SCEV *BoundSCEV,
const SCEV *Step,
658 unsigned LatchBrExitIdx,
675 LLVM_DEBUG(
dbgs() <<
"irce: LatchExitBrIdx: " << LatchBrExitIdx <<
"\n");
683 if (LatchBrExitIdx == 1)
686 assert(LatchBrExitIdx == 0 &&
687 "LatchBrExitIdx should be either 0 or 1");
695 const SCEV *MinusOne =
706 const SCEV *BoundSCEV,
const SCEV *Step,
708 unsigned LatchBrExitIdx,
723 LLVM_DEBUG(
dbgs() <<
"irce: LatchExitBrIdx: " << LatchBrExitIdx <<
"\n");
731 if (LatchBrExitIdx == 1)
734 assert(LatchBrExitIdx == 0 &&
"LatchBrExitIdx should be 0 or 1");
736 const SCEV *StepMinusOne =
751 const char *&FailureReason) {
753 FailureReason =
"loop not in LoopSimplify form";
758 assert(Latch &&
"Simplified loops only have one latch!");
761 FailureReason =
"loop has already been cloned";
766 FailureReason =
"no loop latch";
773 FailureReason =
"no preheader";
779 FailureReason =
"latch terminator not conditional branch";
783 unsigned LatchBrExitIdx = LatchBr->
getSuccessor(0) == Header ? 1 : 0;
791 FailureReason =
"short running loop, not profitable";
797 FailureReason =
"latch terminator branch not conditional on integral icmp";
802 if (isa<SCEVCouldNotCompute>(LatchCount)) {
803 FailureReason =
"could not compute latch count";
816 if (!isa<SCEVAddRecExpr>(LeftSCEV)) {
817 if (isa<SCEVAddRecExpr>(RightSCEV)) {
822 FailureReason =
"no add recurrences in the icmp";
831 IntegerType *Ty = cast<IntegerType>(AR->getType());
839 const SCEV *ExtendedStep =
842 bool NoSignedWrap = ExtendAfterOp->getStart() == ExtendedStart &&
843 ExtendAfterOp->getStepRecurrence(SE) == ExtendedStep;
856 const SCEVAddRecExpr *IndVarBase = cast<SCEVAddRecExpr>(LeftSCEV);
858 FailureReason =
"LHS in icmp not induction variable";
862 if (!isa<SCEVConstant>(StepRec)) {
863 FailureReason =
"LHS in icmp not induction variable";
866 ConstantInt *StepCI = cast<SCEVConstant>(StepRec)->getValue();
868 if (ICI->
isEquality() && !HasNoSignedWrap(IndVarBase)) {
869 FailureReason =
"LHS in icmp needs nsw for equality predicates";
883 bool DecreasedRightValueByOne =
false;
884 if (StepCI->
isOne()) {
909 DecreasedRightValueByOne =
true;
914 DecreasedRightValueByOne =
true;
921 bool FoundExpectedPred =
922 (LTPred && LatchBrExitIdx == 1) || (GTPred && LatchBrExitIdx == 0);
924 if (!FoundExpectedPred) {
925 FailureReason =
"expected icmp slt semantically, found something else";
931 FailureReason =
"unsigned latch conditions are explicitly prohibited";
936 LatchBrExitIdx, &L, SE)) {
937 FailureReason =
"Unsafe loop bounds";
940 if (LatchBrExitIdx == 0) {
943 if (!DecreasedRightValueByOne) {
945 RightValue =
B.CreateAdd(RightValue, One);
948 assert(!DecreasedRightValueByOne &&
949 "Right value can be decreased only for LatchBrExitIdx == 0!");
952 bool IncreasedRightValueByOne =
false;
973 IncreasedRightValueByOne =
true;
977 IncreasedRightValueByOne =
true;
985 bool FoundExpectedPred =
986 (GTPred && LatchBrExitIdx == 1) || (LTPred && LatchBrExitIdx == 0);
988 if (!FoundExpectedPred) {
989 FailureReason =
"expected icmp sgt semantically, found something else";
997 FailureReason =
"unsigned latch conditions are explicitly prohibited";
1002 LatchBrExitIdx, &L, SE)) {
1003 FailureReason =
"Unsafe bounds";
1007 if (LatchBrExitIdx == 0) {
1010 if (!IncreasedRightValueByOne) {
1012 RightValue =
B.CreateSub(RightValue, One);
1015 assert(!IncreasedRightValueByOne &&
1016 "Right value can be increased only for LatchBrExitIdx == 0!");
1023 "loop variant exit count doesn't make sense!");
1027 Value *IndVarStartV =
1030 IndVarStartV->
setName(
"indvar.start");
1032 LoopStructure Result;
1034 Result.Tag =
"main";
1035 Result.Header = Header;
1036 Result.Latch = Latch;
1037 Result.LatchBr = LatchBr;
1038 Result.LatchExit = LatchExit;
1039 Result.LatchBrExitIdx = LatchBrExitIdx;
1040 Result.IndVarStart = IndVarStartV;
1041 Result.IndVarStep = StepCI;
1042 Result.IndVarBase = LeftValue;
1043 Result.IndVarIncreasing = IsIncreasing;
1044 Result.LoopExitAt = RightValue;
1045 Result.IsSignedPredicate = IsSignedPredicate;
1047 FailureReason =
nullptr;
1060 LoopConstrainer::calculateSubRanges(
bool IsSignedPredicate)
const {
1061 IntegerType *Ty = cast<IntegerType>(LatchTakenCount->getType());
1063 auto *RTy = cast<IntegerType>(Range.getType());
1071 LoopConstrainer::SubRanges Result;
1077 RTy, SE, IsSignedPredicate);
1078 const SCEV *End =
NoopOrExtend(SE.getSCEV(MainLoopStructure.LoopExitAt), RTy,
1079 SE, IsSignedPredicate);
1081 bool Increasing = MainLoopStructure.IndVarIncreasing;
1087 const SCEV *Smallest =
nullptr, *Greatest =
nullptr, *GreatestSeen =
nullptr;
1089 const SCEV *One = SE.getOne(RTy);
1094 GreatestSeen = SE.getMinusSCEV(End, One);
1111 Smallest = SE.getAddExpr(End, One);
1112 Greatest = SE.getAddExpr(Start, One);
1113 GreatestSeen = Start;
1116 auto Clamp = [
this, Smallest, Greatest, IsSignedPredicate](
const SCEV *S) {
1117 return IsSignedPredicate
1118 ? SE.getSMaxExpr(Smallest, SE.getSMinExpr(Greatest, S))
1119 : SE.getUMaxExpr(Smallest, SE.getUMinExpr(Greatest, S));
1128 bool ProvablyNoPreloop =
1129 SE.isKnownPredicate(PredLE, Range.getBegin(), Smallest);
1130 if (!ProvablyNoPreloop)
1131 Result.LowLimit = Clamp(Range.getBegin());
1133 bool ProvablyNoPostLoop =
1134 SE.isKnownPredicate(PredLT, GreatestSeen, Range.getEnd());
1135 if (!ProvablyNoPostLoop)
1136 Result.HighLimit = Clamp(Range.getEnd());
1141 void LoopConstrainer::cloneLoop(LoopConstrainer::ClonedLoop &Result,
1142 const char *Tag)
const {
1143 for (
BasicBlock *BB : OriginalLoop.getBlocks()) {
1145 Result.Blocks.push_back(Clone);
1146 Result.Map[BB] = Clone;
1149 auto GetClonedValue = [&Result](
Value *V) {
1150 assert(V &&
"null values not in domain!");
1151 auto It = Result.Map.find(V);
1152 if (It == Result.Map.end())
1154 return static_cast<Value *
>(It->second);
1158 cast<BasicBlock>(GetClonedValue(OriginalLoop.getLoopLatch()));
1162 Result.Structure = MainLoopStructure.map(GetClonedValue);
1163 Result.Structure.Tag = Tag;
1165 for (
unsigned i = 0, e = Result.Blocks.size(); i != e; ++i) {
1167 BasicBlock *OriginalBB = OriginalLoop.getBlocks()[i];
1169 assert(Result.Map[OriginalBB] == ClonedBB &&
"invariant!");
1180 if (OriginalLoop.contains(
SBB))
1185 PN.
addIncoming(GetClonedValue(OldIncoming), ClonedBB);
1191 LoopConstrainer::RewrittenRangeInfo LoopConstrainer::changeIterationSpaceEnd(
1265 RewrittenRangeInfo RRI;
1267 BasicBlock *BBInsertLocation = LS.Latch->getNextNode();
1269 &
F, BBInsertLocation);
1274 bool Increasing = LS.IndVarIncreasing;
1275 bool IsSignedPredicate = LS.IsSignedPredicate;
1278 auto *RangeTy = Range.getBegin()->getType();
1279 auto NoopOrExt = [&](
Value *V) {
1280 if (V->getType() == RangeTy)
1282 return IsSignedPredicate ? B.
CreateSExt(V, RangeTy,
"wide." + V->getName())
1283 : B.
CreateZExt(V, RangeTy,
"wide." + V->getName());
1287 Value *EnterLoopCond =
nullptr;
1292 Value *IndVarStart = NoopOrExt(LS.IndVarStart);
1293 EnterLoopCond = B.
CreateICmp(Pred, IndVarStart, ExitSubloopAt);
1295 B.
CreateCondBr(EnterLoopCond, LS.Header, RRI.PseudoExit);
1298 LS.LatchBr->setSuccessor(LS.LatchBrExitIdx, RRI.ExitSelector);
1300 Value *IndVarBase = NoopOrExt(LS.IndVarBase);
1301 Value *TakeBackedgeLoopCond = B.
CreateICmp(Pred, IndVarBase, ExitSubloopAt);
1303 Value *CondForBranch = LS.LatchBrExitIdx == 1
1304 ? TakeBackedgeLoopCond
1307 LS.LatchBr->setCondition(CondForBranch);
1314 Value *LoopExitAt = NoopOrExt(LS.LoopExitAt);
1316 B.
CreateCondBr(IterationsLeft, RRI.PseudoExit, LS.LatchExit);
1324 for (
PHINode &PN : LS.Header->phis()) {
1326 BranchToContinuation);
1331 RRI.PHIValuesAtPseudoExit.push_back(NewPHI);
1335 BranchToContinuation);
1336 RRI.IndVarEnd->addIncoming(IndVarStart, Preheader);
1337 RRI.IndVarEnd->addIncoming(IndVarBase, RRI.ExitSelector);
1341 for (
PHINode &PN : LS.LatchExit->phis())
1342 replacePHIBlock(&PN, LS.Latch, RRI.ExitSelector);
1347 void LoopConstrainer::rewriteIncomingValuesForPHIs(
1348 LoopStructure &LS,
BasicBlock *ContinuationBlock,
1349 const LoopConstrainer::RewrittenRangeInfo &RRI)
const {
1350 unsigned PHIIndex = 0;
1351 for (
PHINode &PN : LS.Header->phis())
1356 LS.IndVarStart = RRI.IndVarEnd;
1359 BasicBlock *LoopConstrainer::createPreheader(
const LoopStructure &LS,
1361 const char *Tag)
const {
1365 for (
PHINode &PN : LS.Header->phis())
1367 replacePHIBlock(&PN, OldPreheader, Preheader);
1381 Loop *LoopConstrainer::createClonedLoopStructure(
Loop *Original,
Loop *Parent,
1384 Loop &New = *LI.AllocateLoop();
1388 LI.addTopLevelLoop(&New);
1389 LPMAddNewLoop(&New, IsSubloop);
1392 for (
auto *BB : Original->
blocks())
1393 if (LI.getLoopFor(BB) == Original)
1397 for (
Loop *SubLoop : *Original)
1398 createClonedLoopStructure(SubLoop, &New, VM,
true);
1403 bool LoopConstrainer::run() {
1405 LatchTakenCount = SE.
getExitCount(&OriginalLoop, MainLoopStructure.Latch);
1406 Preheader = OriginalLoop.getLoopPreheader();
1407 assert(!isa<SCEVCouldNotCompute>(LatchTakenCount) && Preheader !=
nullptr &&
1410 OriginalPreheader = Preheader;
1411 MainLoopPreheader = Preheader;
1413 bool IsSignedPredicate = MainLoopStructure.IsSignedPredicate;
1421 bool Increasing = MainLoopStructure.IndVarIncreasing;
1423 cast<IntegerType>(Range.getBegin()->getType());
1425 SCEVExpander Expander(SE,
F.getParent()->getDataLayout(),
"irce");
1426 Instruction *InsertPt = OriginalPreheader->getTerminator();
1431 ClonedLoop PreLoop, PostLoop;
1433 Increasing ? SR.LowLimit.hasValue() : SR.HighLimit.hasValue();
1434 bool NeedsPostLoop =
1435 Increasing ? SR.HighLimit.hasValue() : SR.LowLimit.hasValue();
1437 Value *ExitPreLoopAt =
nullptr;
1438 Value *ExitMainLoopAt =
nullptr;
1440 cast<SCEVConstant>(SE.
getConstant(IVTy, -1,
true ));
1443 const SCEV *ExitPreLoopAtSCEV =
nullptr;
1446 ExitPreLoopAtSCEV = *SR.LowLimit;
1449 ExitPreLoopAtSCEV = SE.
getAddExpr(*SR.HighLimit, MinusOneS);
1451 LLVM_DEBUG(
dbgs() <<
"irce: could not prove no-overflow when computing " 1452 <<
"preloop exit limit. HighLimit = " 1453 << *(*SR.HighLimit) <<
"\n");
1458 LLVM_DEBUG(
dbgs() <<
"irce: could not prove that it is safe to expand the" 1459 <<
" preloop exit limit " << *ExitPreLoopAtSCEV
1460 <<
" at block " << InsertPt->getParent()->getName()
1465 ExitPreLoopAt = Expander.expandCodeFor(ExitPreLoopAtSCEV, IVTy, InsertPt);
1466 ExitPreLoopAt->
setName(
"exit.preloop.at");
1469 if (NeedsPostLoop) {
1470 const SCEV *ExitMainLoopAtSCEV =
nullptr;
1473 ExitMainLoopAtSCEV = *SR.HighLimit;
1476 ExitMainLoopAtSCEV = SE.
getAddExpr(*SR.LowLimit, MinusOneS);
1478 LLVM_DEBUG(
dbgs() <<
"irce: could not prove no-overflow when computing " 1479 <<
"mainloop exit limit. LowLimit = " 1480 << *(*SR.LowLimit) <<
"\n");
1485 LLVM_DEBUG(
dbgs() <<
"irce: could not prove that it is safe to expand the" 1486 <<
" main loop exit limit " << *ExitMainLoopAtSCEV
1487 <<
" at block " << InsertPt->getParent()->getName()
1492 ExitMainLoopAt = Expander.expandCodeFor(ExitMainLoopAtSCEV, IVTy, InsertPt);
1493 ExitMainLoopAt->
setName(
"exit.mainloop.at");
1499 cloneLoop(PreLoop,
"preloop");
1501 cloneLoop(PostLoop,
"postloop");
1503 RewrittenRangeInfo PreLoopRRI;
1507 PreLoop.Structure.Header);
1510 createPreheader(MainLoopStructure, Preheader,
"mainloop");
1511 PreLoopRRI = changeIterationSpaceEnd(PreLoop.Structure, Preheader,
1512 ExitPreLoopAt, MainLoopPreheader);
1513 rewriteIncomingValuesForPHIs(MainLoopStructure, MainLoopPreheader,
1518 RewrittenRangeInfo PostLoopRRI;
1520 if (NeedsPostLoop) {
1522 createPreheader(PostLoop.Structure, Preheader,
"postloop");
1523 PostLoopRRI = changeIterationSpaceEnd(MainLoopStructure, MainLoopPreheader,
1524 ExitMainLoopAt, PostLoopPreheader);
1525 rewriteIncomingValuesForPHIs(PostLoop.Structure, PostLoopPreheader,
1530 MainLoopPreheader != Preheader ? MainLoopPreheader :
nullptr;
1531 BasicBlock *NewBlocks[] = {PostLoopPreheader, PreLoopRRI.PseudoExit,
1532 PreLoopRRI.ExitSelector, PostLoopRRI.PseudoExit,
1533 PostLoopRRI.ExitSelector, NewMainLoopPreheader};
1548 Loop *PreL =
nullptr, *PostL =
nullptr;
1549 if (!PreLoop.Blocks.empty()) {
1550 PreL = createClonedLoopStructure(&OriginalLoop,
1551 OriginalLoop.getParentLoop(), PreLoop.Map,
1555 if (!PostLoop.Blocks.empty()) {
1557 createClonedLoopStructure(&OriginalLoop, OriginalLoop.getParentLoop(),
1558 PostLoop.Map,
false);
1562 auto CanonicalizeLoop = [&] (
Loop *L,
bool IsOriginalLoop) {
1567 if (!IsOriginalLoop)
1571 CanonicalizeLoop(PreL,
false);
1573 CanonicalizeLoop(PostL,
false);
1574 CanonicalizeLoop(&OriginalLoop,
true);
1583 InductiveRangeCheck::computeSafeIterationSpace(
1585 bool IsLatchSigned)
const {
1588 auto *IVType = cast<IntegerType>(IndVar->
getType());
1589 auto *RCType = cast<IntegerType>(getBegin()->getType());
1590 if (IVType->getBitWidth() > RCType->getBitWidth())
1620 assert(!B->isZero() &&
"Recurrence with zero step?");
1622 const SCEV *
C = getBegin();
1623 const SCEVConstant *
D =
dyn_cast<SCEVConstant>(getStep());
1628 unsigned BitWidth = RCType->getBitWidth();
1643 auto ClampedSubtract = [&](
const SCEV *
X,
const SCEV *
Y) {
1648 if (IsLatchSigned) {
1659 const SCEV *XMinusSIntMax = SE.getMinusSCEV(X, SIntMax);
1660 return SE.getMinusSCEV(X, SE.getSMaxExpr(
Y, XMinusSIntMax),
1675 const SCEV *M = SE.getMinusSCEV(C, A);
1679 auto SCEVCheckNonNegative = [&](
const SCEV *
X) {
1689 const SCEV *NegOne = SE.getNegativeSCEV(One);
1690 return SE.getAddExpr(SE.getSMaxExpr(SE.getSMinExpr(X, Zero), NegOne), One);
1700 const SCEV *REnd = getEnd();
1701 const SCEV *EndIsNonNegative = SCEVCheckNonNegative(REnd);
1703 const SCEV *Begin = SE.getMulExpr(ClampedSubtract(Zero, M), EndIsNonNegative);
1704 const SCEV *End = SE.getMulExpr(ClampedSubtract(REnd, M), EndIsNonNegative);
1705 return InductiveRangeCheck::Range(Begin, End);
1711 const InductiveRangeCheck::Range &
R2) {
1712 if (R2.isEmpty(SE,
true))
1719 assert(!R1Value.isEmpty(SE,
true) &&
1720 "We should never have empty R1!");
1724 if (R1Value.getType() != R2.getType())
1727 const SCEV *NewBegin = SE.
getSMaxExpr(R1Value.getBegin(), R2.getBegin());
1731 auto Ret = InductiveRangeCheck::Range(NewBegin, NewEnd);
1732 if (
Ret.isEmpty(SE,
true))
1740 const InductiveRangeCheck::Range &
R2) {
1741 if (R2.isEmpty(SE,
false))
1748 assert(!R1Value.isEmpty(SE,
false) &&
1749 "We should never have empty R1!");
1753 if (R1Value.getType() != R2.getType())
1756 const SCEV *NewBegin = SE.
getUMaxExpr(R1Value.getBegin(), R2.getBegin());
1760 auto Ret = InductiveRangeCheck::Range(NewBegin, NewEnd);
1761 if (
Ret.isEmpty(SE,
false))
1773 InductiveRangeCheckElimination IRCE(AR.
SE, BPI, AR.
DT, AR.
LI);
1774 auto LPMAddNewLoop = [&U](
Loop *NL,
bool IsSubloop) {
1778 bool Changed = IRCE.run(&L, LPMAddNewLoop);
1789 ScalarEvolution &SE = getAnalysis<ScalarEvolutionWrapperPass>().getSE();
1791 getAnalysis<BranchProbabilityInfoWrapperPass>().getBPI();
1792 auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
1793 auto &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
1794 InductiveRangeCheckElimination IRCE(SE, &BPI, DT, LI);
1795 auto LPMAddNewLoop = [&LPM](
Loop *NL,
bool ) {
1798 return IRCE.run(L, LPMAddNewLoop);
1801 bool InductiveRangeCheckElimination::run(
1804 LLVM_DEBUG(
dbgs() <<
"irce: giving up constraining loop, too large\n");
1818 if (
BranchInst *TBI = dyn_cast<BranchInst>(BBI->getTerminator()))
1819 InductiveRangeCheck::extractRangeChecksFromBranch(TBI, L, SE, BPI,
1822 if (RangeChecks.
empty())
1825 auto PrintRecognizedRangeChecks = [&](
raw_ostream &OS) {
1826 OS <<
"irce: looking at loop "; L->
print(OS);
1827 OS <<
"irce: loop has " << RangeChecks.
size()
1828 <<
" inductive range checks: \n";
1829 for (InductiveRangeCheck &IRC : RangeChecks)
1836 PrintRecognizedRangeChecks(
errs());
1838 const char *FailureReason =
nullptr;
1840 LoopStructure::parseLoopStructure(SE, BPI, *L, FailureReason);
1841 if (!MaybeLoopStructure.
hasValue()) {
1843 << FailureReason <<
"\n";);
1846 LoopStructure LS = MaybeLoopStructure.
getValue();
1858 auto IntersectRange =
1862 for (InductiveRangeCheck &IRC : RangeChecks) {
1863 auto Result = IRC.computeSafeIterationSpace(SE, IndVar,
1864 LS.IsSignedPredicate);
1865 if (Result.hasValue()) {
1866 auto MaybeSafeIterRange =
1867 IntersectRange(SE, SafeIterRange, Result.
getValue());
1868 if (MaybeSafeIterRange.hasValue()) {
1870 !MaybeSafeIterRange.getValue().isEmpty(SE, LS.IsSignedPredicate) &&
1871 "We should never return empty ranges!");
1873 SafeIterRange = MaybeSafeIterRange.
getValue();
1881 LoopConstrainer LC(*L, LI, LPMAddNewLoop, LS, SE, DT,
1883 bool Changed = LC.run();
1886 auto PrintConstrainedLoopInfo = [L]() {
1887 dbgs() <<
"irce: in function ";
1889 dbgs() <<
"constrained ";
1896 PrintConstrainedLoopInfo();
1900 for (InductiveRangeCheck &IRC : RangeChecksToEliminate) {
1901 ConstantInt *FoldedRangeCheck = IRC.getPassingDirection()
1904 IRC.getCheckUse()->set(FoldedRangeCheck);
1912 return new IRCELegacyPass();
static unsigned getBitWidth(Type *Ty, const DataLayout &DL)
Returns the bitwidth of the given scalar or pointer type.
static cl::opt< bool > AllowNarrowLatchCondition("irce-allow-narrow-latch", cl::Hidden, cl::init(true), cl::desc("If set to true, IRCE may eliminate wide range checks in loops " "with narrow latch condition."))
Pass interface - Implemented by all 'passes'.
BinaryOp_match< LHS, RHS, Instruction::And > m_And(const LHS &L, const RHS &R)
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
A parsed version of the target data layout string in and methods for querying it. ...
const_iterator end(StringRef path)
Get end iterator over path.
static ConstantInt * getFalse(LLVMContext &Context)
BranchInst * CreateCondBr(Value *Cond, BasicBlock *True, BasicBlock *False, MDNode *BranchWeights=nullptr, MDNode *Unpredictable=nullptr)
Create a conditional 'br Cond, TrueDest, FalseDest' instruction.
class_match< Value > m_Value()
Match an arbitrary value and ignore it.
Value * CreateICmp(CmpInst::Predicate P, Value *LHS, Value *RHS, const Twine &Name="")
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
raw_ostream & errs()
This returns a reference to a raw_ostream for standard error.
static IntegerType * getInt1Ty(LLVMContext &C)
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
BlockT * getLoopLatch() const
If there is a single latch block for this loop, return it.
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
GCNRegPressure max(const GCNRegPressure &P1, const GCNRegPressure &P2)
PreservedAnalyses getLoopPassPreservedAnalyses()
Returns the minimum set of Analyses that all loop passes must preserve.
const_iterator begin(StringRef path, Style style=Style::native)
Get begin iterator over path.
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
const SCEV * getConstant(ConstantInt *V)
This class represents lattice values for constants.
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds...
bool isSafeToExpandAt(const SCEV *S, const Instruction *InsertionPoint, ScalarEvolution &SE)
Return true if the given expression is safe to expand in the sense that all materialized values are d...
void replaceOperandWith(unsigned I, Metadata *New)
Replace a specific operand.
static MDString * get(LLVMContext &Context, StringRef Str)
std::error_code remove(const Twine &path, bool IgnoreNonExisting=true)
Remove path.
void push_back(const T &Elt)
bool cannotBeMinInLoop(const SCEV *S, const Loop *L, ScalarEvolution &SE, bool Signed)
Returns true if S is defined and never is equal to signed/unsigned min.
The main scalar evolution driver.
bool isKnownNonNegativeInLoop(const SCEV *S, const Loop *L, ScalarEvolution &SE)
Returns true if we can prove that S is defined and always non-negative in loop L. ...
BlockT * getLoopPreheader() const
If there is a preheader for this loop, return it.
static cl::opt< bool > AllowUnsignedLatchCondition("irce-allow-unsigned-latch", cl::Hidden, cl::init(true))
static Optional< InductiveRangeCheck::Range > IntersectSignedRange(ScalarEvolution &SE, const Optional< InductiveRangeCheck::Range > &R1, const InductiveRangeCheck::Range &R2)
bool isAvailableAtLoopEntry(const SCEV *S, const Loop *L)
Determine if the SCEV can be evaluated at loop's entry.
An efficient, type-erasing, non-owning reference to a callable.
const Use & getOperandUse(unsigned i) const
static bool isEquality(Predicate P)
Return true if this predicate is either EQ or NE.
BasicBlock * getSuccessor(unsigned i) const
Value * CreateSExt(Value *V, Type *DestTy, const Twine &Name="")
The adaptor from a function pass to a loop pass computes these analyses and makes them available to t...
Value * getCondition() const
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
This defines the Use class.
static cl::opt< bool > PrintRangeChecks("irce-print-range-checks", cl::Hidden, cl::init(false))
LLVMContext & getContext() const
Get the context in which this basic block lives.
bool isKnownNegativeInLoop(const SCEV *S, const Loop *L, ScalarEvolution &SE)
Returns true if we can prove that S is defined and always negative in loop L.
static APInt getSignedMaxValue(unsigned numBits)
Gets maximum signed value of APInt for a specific bit width.
LLVMContext & getContext() const
Return the LLVMContext in which this type was uniqued.
void print(raw_ostream &OS, unsigned Depth=0, bool Verbose=false) const
Print loop with all the BBs inside it.
Value * CreateNot(Value *V, const Twine &Name="")
bool formLCSSARecursively(Loop &L, DominatorTree &DT, LoopInfo *LI, ScalarEvolution *SE)
Put a loop nest into LCSSA form.
The SCEV is loop-invariant.
static GCMetadataPrinterRegistry::Add< OcamlGCMetadataPrinter > Y("ocaml", "ocaml 3.10-compatible collector")
bool match(Val *V, const Pattern &P)
AnalysisUsage & addRequired()
const Module * getModule() const
Return the module owning the function this basic block belongs to, or nullptr if the function does no...
#define INITIALIZE_PASS_DEPENDENCY(depName)
const Loop * getLoop() const
const DataLayout & getDataLayout() const
Get the data layout for the module's target platform.
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
bool simplifyLoop(Loop *L, DominatorTree *DT, LoopInfo *LI, ScalarEvolution *SE, AssumptionCache *AC, bool PreserveLCSSA)
Simplify each loop in a loop nest recursively.
ArrayRef< T > makeArrayRef(const T &OneElt)
Construct an ArrayRef from a single element.
INITIALIZE_PASS_BEGIN(IRCELegacyPass, "irce", "Inductive range check elimination", false, false) INITIALIZE_PASS_END(IRCELegacyPass
A Use represents the edge between a Value definition and its users.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
void setName(const Twine &Name)
Change the name of the value.
static cl::opt< int > MaxExitProbReciprocal("irce-max-exit-prob-reciprocal", cl::Hidden, cl::init(10))
This file implements a class to represent arbitrary precision integral constant values and operations...
BlockT * getHeader() const
Analysis pass which computes BranchProbabilityInfo.
ConstantInt * getValue() const
bool isOne() const
This is just a convenience method to make client code smaller for a common case.
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...
static void DisableAllLoopOptsOnLoop(Loop &L)
Type * getType() const
All values are typed, get the type of this value.
void addBasicBlockToLoop(BlockT *NewBB, LoopInfoBase< BlockT, LoopT > &LI)
This method is used by other analyses to update loop information.
This node represents a polynomial recurrence on the trip count of the specified loop.
static const char * ClonedLoopTag
void setLoopID(MDNode *LoopID) const
Set the llvm.loop loop id metadata for this loop.
const T & getValue() const LLVM_LVALUE_FUNCTION
Inductive range check elimination
This header provides classes for managing per-loop analyses.
MDNode * getMetadata(unsigned KindID) const
Get the metadata of given kind attached to this Instruction.
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory)...
bool isMinusOne() const
This function will return true iff every bit in this constant is set to true.
Value * CreateZExt(Value *V, Type *DestTy, const Twine &Name="")
const SCEV * getStepRecurrence(ScalarEvolution &SE) const
Constructs and returns the recurrence indicating how much this expression steps by.
unsigned getBitWidth() const
Get the number of bits in this IntegerType.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree...
void SetInsertPoint(BasicBlock *TheBB)
This specifies that created instructions should be appended to the end of the specified block...
Legacy analysis pass which computes BranchProbabilityInfo.
Value * getOperand(unsigned i) const
If this flag is set, the remapper knows that only local values within a function (such as an instruct...
void replaceUsesOfWith(Value *From, Value *To)
Replace uses of one Value with another.
bool isLoopEntryGuardedByCond(const Loop *L, ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS)
Test whether entry to the loop is protected by a conditional between LHS and RHS. ...
static MDTuple * get(LLVMContext &Context, ArrayRef< Metadata *> MDs)
initializer< Ty > init(const Ty &Val)
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
void dump(const SparseBitVector< ElementSize > &LHS, raw_ostream &out)
A set of analyses that are preserved following a run of a transformation pass.
const SCEV * getOne(Type *Ty)
Return a SCEV for the constant 1 of a specific type.
LLVM Basic Block Representation.
bool isLoopExiting(const BlockT *BB) const
True if terminator in the block can branch to another block that is outside of the current loop...
The instances of the Type class are immutable: once they are created, they are never changed...
This is an important class for using LLVM in a threaded context.
LoopDisposition getLoopDisposition(const SCEV *S, const Loop *L)
Return the "disposition" of the given SCEV with respect to the given loop.
Conditional or Unconditional Branch instruction.
static StringRef getPredicateName(Predicate P)
Value * getIncomingValueForBlock(const BasicBlock *BB) const
This file contains the declarations for the subclasses of Constant, which represent the different fla...
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
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.
const SCEV * getSMaxExpr(const SCEV *LHS, const SCEV *RHS)
Represent the analysis usage information of a pass.
This instruction compares its operands according to the predicate given to the constructor.
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Value * expandCodeFor(const SCEV *SH, Type *Ty, Instruction *I)
Insert code to directly compute the specified SCEV expression into the program.
bool isAffine() const
Return true if this represents an expression A + B*x where A and B are loop invariant values...
static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)
Creates a new BasicBlock.
static void print(raw_ostream &Out, object::Archive::Kind Kind, T Val)
const SCEV * getStart() const
Class to represent integer types.
bool isKnownNegative(const SCEV *S)
Test if the given expression is known to be negative.
const SCEV * getMinusSCEV(const SCEV *LHS, const SCEV *RHS, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
Return LHS-RHS. Minus is represented in SCEV as A+B*-1.
void addSiblingLoops(ArrayRef< Loop *> NewSibLoops)
Loop passes should use this method to indicate they have added new sibling loops to the current loop...
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
static wasm::ValType getType(const TargetRegisterClass *RC)
const SCEV * getNoopOrZeroExtend(const SCEV *V, Type *Ty)
Return a SCEV corresponding to a conversion of the input value to the specified type.
INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false) RegBankSelect
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
BranchProbability getEdgeProbability(const BasicBlock *Src, unsigned IndexInSuccessors) const
Get an edge's probability, relative to other out-edges of the Src.
static bool isSafeIncreasingBound(const SCEV *Start, const SCEV *BoundSCEV, const SCEV *Step, ICmpInst::Predicate Pred, unsigned LatchBrExitIdx, Loop *L, ScalarEvolution &SE)
Given a loop with an increasing induction variable, is it possible to safely calculate the bounds of ...
const SCEV * getSMinExpr(const SCEV *LHS, const SCEV *RHS)
void print(raw_ostream &OS) const
Print out the internal representation of this scalar to the specified stream.
This class provides an interface for updating the loop pass manager based on mutations to the loop ne...
static IntegerType * get(LLVMContext &C, unsigned NumBits)
This static method is the primary way of constructing an IntegerType.
bool contains(const LoopT *L) const
Return true if the specified loop is contained within in this loop.
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements...
static cl::opt< bool > SkipProfitabilityChecks("irce-skip-profitability-checks", cl::Hidden, cl::init(false))
This is the shared class of boolean and integer constants.
Type * getType() const
Return the LLVM type of this SCEV expression.
void setIncomingBlock(unsigned i, BasicBlock *BB)
An analysis over an "inner" IR unit that provides access to an analysis manager over a "outer" IR uni...
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small...
Module.h This file contains the declarations for the Module class.
static const SCEV * NoopOrExtend(const SCEV *S, Type *Ty, ScalarEvolution &SE, bool Signed)
If the type of S matches with Ty, return S.
const SCEV * getNoopOrSignExtend(const SCEV *V, Type *Ty)
Return a SCEV corresponding to a conversion of the input value to the specified type.
static APInt getMinValue(unsigned numBits)
Gets minimum unsigned value of APInt for a specific bit width.
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
static Constant * get(Type *Ty, uint64_t V, bool isSigned=false)
If Ty is a vector type, return a Constant with a splat of the given value.
static BranchInst * Create(BasicBlock *IfTrue, Instruction *InsertBefore=nullptr)
static PHINode * Create(Type *Ty, unsigned NumReservedValues, const Twine &NameStr="", Instruction *InsertBefore=nullptr)
Constructors - NumReservedValues is a hint for the number of incoming edges that this phi node will h...
const SCEV * getUMaxExpr(const SCEV *LHS, const SCEV *RHS)
unsigned getNumIncomingValues() const
Return the number of incoming edges.
static ConstantInt * getTrue(LLVMContext &Context)
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Class for arbitrary precision integers.
BasicBlock * CloneBasicBlock(const BasicBlock *BB, ValueToValueMapTy &VMap, const Twine &NameSuffix="", Function *F=nullptr, ClonedCodeInfo *CodeInfo=nullptr, DebugInfoFinder *DIFinder=nullptr)
Return a copy of the specified basic block, but without embedding the block into a particular functio...
void RemapInstruction(Instruction *I, ValueToValueMapTy &VM, RemapFlags Flags=RF_None, ValueMapTypeRemapper *TypeMapper=nullptr, ValueMaterializer *Materializer=nullptr)
Convert the instruction operands from referencing the current values into those specified by VM...
This class uses information about analyze scalars to rewrite expressions in canonical form...
static APInt getMaxValue(unsigned numBits)
Gets maximum unsigned value of APInt for specific bit width.
If this flag is set, the remapper ignores missing function-local entries (Argument, Instruction, BasicBlock) that are not in the value map.
LoopT * getParentLoop() const
Predicate getPredicate() const
Return the predicate for this instruction.
This file provides various utilities for inspecting and working with the control flow graph in LLVM I...
bool isLoopSimplifyForm() const
Return true if the Loop is in the form that the LoopSimplify form transforms loops to...
Analysis providing branch probability information.
This class represents an analyzed expression in the program.
void addChildLoop(LoopT *NewChild)
Add the specified loop to be a child of this loop.
LLVM_NODISCARD bool empty() const
unsigned greater or equal
Represents a single loop in the control flow graph.
ArrayRef< BlockT * > getBlocks() const
Get a list of the basic blocks which make up this loop.
StringRef getName() const
Return a constant reference to the value's name.
BasicBlock * getIncomingBlock(unsigned i) const
Return incoming basic block number i.
const Function * getParent() const
Return the enclosing method, or null if none.
bool isZero() const
This is just a convenience method to make client code smaller for a common code.
void getLoopAnalysisUsage(AnalysisUsage &AU)
Helper to consistently add the set of standard passes to a loop pass's AnalysisUsage.
LLVM_NODISCARD std::enable_if<!is_simple_type< Y >::value, typename cast_retty< X, const Y >::ret_type >::type dyn_cast(const Y &Val)
static cl::opt< unsigned > LoopSizeCutoff("irce-loop-size-cutoff", cl::Hidden, cl::init(64))
bool isUnconditional() const
static bool isSafeDecreasingBound(const SCEV *Start, const SCEV *BoundSCEV, const SCEV *Step, ICmpInst::Predicate Pred, unsigned LatchBrExitIdx, Loop *L, ScalarEvolution &SE)
Given a loop with an deccreasing induction variable, is it possible to safely calculate the bounds of...
void initializeIRCELegacyPassPass(PassRegistry &)
static Optional< InductiveRangeCheck::Range > IntersectUnsignedRange(ScalarEvolution &SE, const Optional< InductiveRangeCheck::Range > &R1, const InductiveRangeCheck::Range &R2)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
static APInt getSignedMinValue(unsigned numBits)
Gets minimum signed value of APInt for a specific bit width.
static cl::opt< bool > PrintChangedLoops("irce-print-changed-loops", cl::Hidden, cl::init(false))
const SCEV * getUMinExpr(const SCEV *LHS, const SCEV *RHS)
const SCEV * getNegativeSCEV(const SCEV *V, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap)
Return the SCEV object corresponding to -V.
LLVM Value Representation.
const SCEV * getSCEV(Value *V)
Return a SCEV expression for the full generality of the specified expression.
succ_range successors(Instruction *I)
#define LLVM_FALLTHROUGH
LLVM_FALLTHROUGH - Mark fallthrough cases in switch statements.
This class implements an extremely fast bulk output stream that can only output to a stream...
Predicate getSwappedPredicate() const
For example, EQ->EQ, SLE->SGE, ULT->UGT, OEQ->OEQ, ULE->UGE, OLT->OGT, etc.
A container for analyses that lazily runs them and caches their results.
const SCEV * getExitCount(const Loop *L, BasicBlock *ExitingBlock)
Get the expression for the number of loop iterations for which this loop is guaranteed not to exit vi...
static BranchProbability getZero()
bool cannotBeMaxInLoop(const SCEV *S, const Loop *L, ScalarEvolution &SE, bool Signed)
Returns true if S is defined and never is equal to signed/unsigned max.
PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM, LoopStandardAnalysisResults &AR, LPMUpdater &U)
void setIncomingValue(unsigned i, Value *V)
iterator_range< block_iterator > blocks() const
NoWrapFlags getNoWrapFlags(NoWrapFlags Mask=NoWrapMask) const
Pass * createInductiveRangeCheckEliminationPass()
const SCEV * getSignExtendExpr(const SCEV *Op, Type *Ty, unsigned Depth=0)
const BasicBlock * getParent() const
This class represents a constant integer value.