121 cl::desc(
"If set to true, IRCE may eliminate wide range checks in loops "
122 "with narrow latch condition."));
126#define DEBUG_TYPE "irce"
140class InductiveRangeCheck {
142 const SCEV *Begin =
nullptr;
143 const SCEV *Step =
nullptr;
144 const SCEV *End =
nullptr;
145 Use *CheckUse =
nullptr;
157 const SCEV *getBegin()
const {
return Begin; }
158 const SCEV *getStep()
const {
return Step; }
159 const SCEV *getEnd()
const {
return End; }
162 OS <<
"InductiveRangeCheck:\n";
169 OS <<
"\n CheckUse: ";
170 getCheckUse()->getUser()->print(
OS);
171 OS <<
" Operand: " << getCheckUse()->getOperandNo() <<
"\n";
179 Use *getCheckUse()
const {
return CheckUse; }
189 Range(
const SCEV *Begin,
const SCEV *End) : Begin(Begin), End(End) {
190 assert(Begin->
getType() == End->getType() &&
"ill-typed range!");
194 const SCEV *getBegin()
const {
return Begin; }
195 const SCEV *getEnd()
const {
return End; }
208 bool getPassingDirection() {
return true; }
215 bool IsLatchSigned)
const;
230class InductiveRangeCheckElimination {
247 LoopInfo &LI, GetBFIFunc GetBFI = std::nullopt)
248 : SE(SE), BPI(BPI), DT(DT), LI(LI), GetBFI(GetBFI) {}
276char IRCELegacyPass::ID = 0;
279 "Inductive range check elimination",
false,
false)
292InductiveRangeCheck::parseRangeCheckICmp(
Loop *L,
ICmpInst *ICI,
295 auto IsLoopInvariant = [&SE, L](
Value *V) {
296 return SE.isLoopInvariant(SE.getSCEV(V), L);
307 case ICmpInst::ICMP_SLE:
310 case ICmpInst::ICMP_SGE:
312 if (
match(
RHS, m_ConstantInt<0>())) {
318 case ICmpInst::ICMP_SLT:
321 case ICmpInst::ICMP_SGT:
323 if (
match(
RHS, m_ConstantInt<-1>())) {
328 if (IsLoopInvariant(
LHS)) {
335 case ICmpInst::ICMP_ULT:
338 case ICmpInst::ICMP_UGT:
340 if (IsLoopInvariant(
LHS)) {
351void InductiveRangeCheck::extractRangeChecksFromCond(
355 Value *Condition = ConditionUse.
get();
356 if (!Visited.
insert(Condition).second)
361 extractRangeChecksFromCond(L, SE, cast<User>(Condition)->getOperandUse(0),
363 extractRangeChecksFromCond(L, SE, cast<User>(Condition)->getOperandUse(1),
368 ICmpInst *ICI = dyn_cast<ICmpInst>(Condition);
374 if (!parseRangeCheckICmp(L, ICI, SE,
Index,
Length, IsSigned))
377 const auto *IndexAddRec = dyn_cast<SCEVAddRecExpr>(SE.
getSCEV(
Index));
379 IndexAddRec && (IndexAddRec->getLoop() ==
L) && IndexAddRec->isAffine();
384 const SCEV *End =
nullptr;
393 unsigned BitWidth = cast<IntegerType>(IndexAddRec->getType())->getBitWidth();
398 InductiveRangeCheck IRC;
400 IRC.Begin = IndexAddRec->getStart();
401 IRC.Step = IndexAddRec->getStepRecurrence(SE);
402 IRC.CheckUse = &ConditionUse;
406void InductiveRangeCheck::extractRangeChecksFromBranch(
419 InductiveRangeCheck::extractRangeChecksFromCond(L, SE, BI->
getOperandUse(0),
445 DisableLICMVersioning, DisableDistribution});
448 L.setLoopID(NewLoopID);
458struct LoopStructure {
459 const char *
Tag =
"";
468 unsigned LatchBrExitIdx = std::numeric_limits<unsigned>::max();
479 Value *IndVarBase =
nullptr;
480 Value *IndVarStart =
nullptr;
481 Value *IndVarStep =
nullptr;
482 Value *LoopExitAt =
nullptr;
483 bool IndVarIncreasing =
false;
484 bool IsSignedPredicate =
true;
486 LoopStructure() =
default;
488 template <
typename M> LoopStructure map(M Map)
const {
491 Result.Header = cast<BasicBlock>(
Map(Header));
492 Result.Latch = cast<BasicBlock>(
Map(Latch));
493 Result.LatchBr = cast<BranchInst>(
Map(LatchBr));
494 Result.LatchExit = cast<BasicBlock>(
Map(LatchExit));
495 Result.LatchBrExitIdx = LatchBrExitIdx;
500 Result.IndVarIncreasing = IndVarIncreasing;
501 Result.IsSignedPredicate = IsSignedPredicate;
505 static std::optional<LoopStructure> parseLoopStructure(
ScalarEvolution &,
506 Loop &,
const char *&);
517class LoopConstrainer {
521 std::vector<BasicBlock *> Blocks;
527 LoopStructure Structure;
532 struct RewrittenRangeInfo {
535 std::vector<PHINode *> PHIValuesAtPseudoExit;
538 RewrittenRangeInfo() =
default;
549 std::optional<const SCEV *> LowLimit;
550 std::optional<const SCEV *> HighLimit;
556 std::optional<SubRanges> calculateSubRanges(
bool IsSignedPredicate)
const;
562 void cloneLoop(ClonedLoop &CLResult,
const char *
Tag)
const;
566 Loop *createClonedLoopStructure(
Loop *Original,
Loop *Parent,
591 changeIterationSpaceEnd(
const LoopStructure &LS,
BasicBlock *Preheader,
598 const char *
Tag)
const;
604 void rewriteIncomingValuesForPHIs(
605 LoopStructure &LS,
BasicBlock *ContinuationBlockAndPreheader,
606 const LoopConstrainer::RewrittenRangeInfo &RRI)
const;
625 const SCEV *LatchTakenCount =
nullptr;
633 InductiveRangeCheck::Range
Range;
637 LoopStructure MainLoopStructure;
644 :
F(*
L.getHeader()->
getParent()), Ctx(
L.getHeader()->getContext()),
645 SE(SE), DT(DT), LI(LI), LPMAddNewLoop(LPMAddNewLoop), OriginalLoop(
L),
657 const SCEV *BoundSCEV,
const SCEV *Step,
659 unsigned LatchBrExitIdx,
661 if (Pred != ICmpInst::ICMP_SLT && Pred != ICmpInst::ICMP_SGT &&
662 Pred != ICmpInst::ICMP_ULT && Pred != ICmpInst::ICMP_UGT)
675 LLVM_DEBUG(
dbgs() <<
"irce: LatchExitBrIdx: " << LatchBrExitIdx <<
"\n");
677 bool IsSigned = ICmpInst::isSigned(Pred);
683 if (LatchBrExitIdx == 1)
686 assert(LatchBrExitIdx == 0 &&
687 "LatchBrExitIdx should be either 0 or 1");
690 unsigned BitWidth = cast<IntegerType>(BoundSCEV->
getType())->getBitWidth();
695 const SCEV *MinusOne =
706 const SCEV *BoundSCEV,
const SCEV *Step,
708 unsigned LatchBrExitIdx,
710 if (Pred != ICmpInst::ICMP_SLT && Pred != ICmpInst::ICMP_SGT &&
711 Pred != ICmpInst::ICMP_ULT && Pred != ICmpInst::ICMP_UGT)
722 LLVM_DEBUG(
dbgs() <<
"irce: LatchExitBrIdx: " << LatchBrExitIdx <<
"\n");
724 bool IsSigned = ICmpInst::isSigned(Pred);
730 if (LatchBrExitIdx == 1)
733 assert(LatchBrExitIdx == 0 &&
"LatchBrExitIdx should be 0 or 1");
735 const SCEV *StepMinusOne =
737 unsigned BitWidth = cast<IntegerType>(BoundSCEV->
getType())->getBitWidth();
747std::optional<LoopStructure>
749 const char *&FailureReason) {
750 if (!
L.isLoopSimplifyForm()) {
751 FailureReason =
"loop not in LoopSimplify form";
756 assert(Latch &&
"Simplified loops only have one latch!");
759 FailureReason =
"loop has already been cloned";
763 if (!
L.isLoopExiting(Latch)) {
764 FailureReason =
"no loop latch";
771 FailureReason =
"no preheader";
777 FailureReason =
"latch terminator not conditional branch";
781 unsigned LatchBrExitIdx = LatchBr->
getSuccessor(0) == Header ? 1 : 0;
785 FailureReason =
"latch terminator branch not conditional on integral icmp";
790 if (isa<SCEVCouldNotCompute>(LatchCount)) {
791 FailureReason =
"could not compute latch count";
804 if (!isa<SCEVAddRecExpr>(LeftSCEV)) {
805 if (isa<SCEVAddRecExpr>(RightSCEV)) {
808 Pred = ICmpInst::getSwappedPredicate(Pred);
810 FailureReason =
"no add recurrences in the icmp";
819 IntegerType *Ty = cast<IntegerType>(AR->getType());
827 const SCEV *ExtendedStep =
830 bool NoSignedWrap = ExtendAfterOp->
getStart() == ExtendedStart &&
844 const SCEVAddRecExpr *IndVarBase = cast<SCEVAddRecExpr>(LeftSCEV);
845 if (IndVarBase->
getLoop() != &L) {
846 FailureReason =
"LHS in cmp is not an AddRec for this loop";
850 FailureReason =
"LHS in icmp not induction variable";
854 if (!isa<SCEVConstant>(StepRec)) {
855 FailureReason =
"LHS in icmp not induction variable";
860 if (ICI->
isEquality() && !HasNoSignedWrap(IndVarBase)) {
861 FailureReason =
"LHS in icmp needs nsw for equality predicates";
867 bool IsSignedPredicate;
873 const SCEV *FixedRightSCEV =
nullptr;
877 if (
auto *
I = dyn_cast<Instruction>(RightValue))
878 if (
L.contains(
I->getParent()))
879 FixedRightSCEV = RightSCEV;
882 bool DecreasedRightValueByOne =
false;
883 if (StepCI->
isOne()) {
885 if (Pred == ICmpInst::ICMP_NE && LatchBrExitIdx == 1)
894 Pred = ICmpInst::ICMP_ULT;
896 Pred = ICmpInst::ICMP_SLT;
897 else if (Pred == ICmpInst::ICMP_EQ && LatchBrExitIdx == 0) {
905 Pred = ICmpInst::ICMP_UGT;
908 DecreasedRightValueByOne =
true;
910 Pred = ICmpInst::ICMP_SGT;
913 DecreasedRightValueByOne =
true;
918 bool LTPred = (Pred == ICmpInst::ICMP_SLT || Pred == ICmpInst::ICMP_ULT);
919 bool GTPred = (Pred == ICmpInst::ICMP_SGT || Pred == ICmpInst::ICMP_UGT);
920 bool FoundExpectedPred =
921 (LTPred && LatchBrExitIdx == 1) || (GTPred && LatchBrExitIdx == 0);
923 if (!FoundExpectedPred) {
924 FailureReason =
"expected icmp slt semantically, found something else";
928 IsSignedPredicate = ICmpInst::isSigned(Pred);
930 FailureReason =
"unsigned latch conditions are explicitly prohibited";
935 LatchBrExitIdx, &L, SE)) {
936 FailureReason =
"Unsafe loop bounds";
939 if (LatchBrExitIdx == 0) {
942 if (!DecreasedRightValueByOne)
946 assert(!DecreasedRightValueByOne &&
947 "Right value can be decreased only for LatchBrExitIdx == 0!");
950 bool IncreasedRightValueByOne =
false;
953 if (Pred == ICmpInst::ICMP_NE && LatchBrExitIdx == 1)
960 Pred = ICmpInst::ICMP_SGT;
961 else if (Pred == ICmpInst::ICMP_EQ && LatchBrExitIdx == 0) {
969 Pred = ICmpInst::ICMP_ULT;
971 IncreasedRightValueByOne =
true;
973 Pred = ICmpInst::ICMP_SLT;
975 IncreasedRightValueByOne =
true;
980 bool LTPred = (Pred == ICmpInst::ICMP_SLT || Pred == ICmpInst::ICMP_ULT);
981 bool GTPred = (Pred == ICmpInst::ICMP_SGT || Pred == ICmpInst::ICMP_UGT);
983 bool FoundExpectedPred =
984 (GTPred && LatchBrExitIdx == 1) || (LTPred && LatchBrExitIdx == 0);
986 if (!FoundExpectedPred) {
987 FailureReason =
"expected icmp sgt semantically, found something else";
992 Pred == ICmpInst::ICMP_SLT || Pred == ICmpInst::ICMP_SGT;
995 FailureReason =
"unsigned latch conditions are explicitly prohibited";
1000 LatchBrExitIdx, &L, SE)) {
1001 FailureReason =
"Unsafe bounds";
1002 return std::nullopt;
1005 if (LatchBrExitIdx == 0) {
1008 if (!IncreasedRightValueByOne)
1012 assert(!IncreasedRightValueByOne &&
1013 "Right value can be increased only for LatchBrExitIdx == 0!");
1020 "loop variant exit count doesn't make sense!");
1022 assert(!
L.contains(LatchExit) &&
"expected an exit block!");
1029 Expander.expandCodeFor(FixedRightSCEV, FixedRightSCEV->
getType(), Ins);
1031 Value *IndVarStartV = Expander.expandCodeFor(IndVarStart, IndVarTy, Ins);
1032 IndVarStartV->
setName(
"indvar.start");
1039 Result.LatchBr = LatchBr;
1040 Result.LatchExit = LatchExit;
1041 Result.LatchBrExitIdx = LatchBrExitIdx;
1042 Result.IndVarStart = IndVarStartV;
1043 Result.IndVarStep = StepCI;
1044 Result.IndVarBase = LeftValue;
1045 Result.IndVarIncreasing = IsIncreasing;
1046 Result.LoopExitAt = RightValue;
1047 Result.IsSignedPredicate = IsSignedPredicate;
1049 FailureReason =
nullptr;
1061std::optional<LoopConstrainer::SubRanges>
1062LoopConstrainer::calculateSubRanges(
bool IsSignedPredicate)
const {
1063 IntegerType *Ty = cast<IntegerType>(LatchTakenCount->getType());
1065 auto *RTy = cast<IntegerType>(
Range.getType());
1069 return std::nullopt;
1071 return std::nullopt;
1073 LoopConstrainer::SubRanges
Result;
1079 RTy, SE, IsSignedPredicate);
1081 SE, IsSignedPredicate);
1083 bool Increasing = MainLoopStructure.IndVarIncreasing;
1089 const SCEV *Smallest =
nullptr, *Greatest =
nullptr, *GreatestSeen =
nullptr;
1115 GreatestSeen = Start;
1118 auto Clamp = [
this, Smallest, Greatest, IsSignedPredicate](
const SCEV *S) {
1119 return IsSignedPredicate
1126 IsSignedPredicate ? ICmpInst::ICMP_SLE : ICmpInst::ICMP_ULE;
1128 IsSignedPredicate ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT;
1130 bool ProvablyNoPreloop =
1132 if (!ProvablyNoPreloop)
1135 bool ProvablyNoPostLoop =
1137 if (!ProvablyNoPostLoop)
1143void LoopConstrainer::cloneLoop(LoopConstrainer::ClonedLoop &Result,
1144 const char *
Tag)
const {
1145 for (
BasicBlock *BB : OriginalLoop.getBlocks()) {
1147 Result.Blocks.push_back(Clone);
1152 assert(V &&
"null values not in domain!");
1153 auto It =
Result.Map.find(V);
1154 if (It ==
Result.Map.end())
1156 return static_cast<Value *
>(It->second);
1160 cast<BasicBlock>(GetClonedValue(OriginalLoop.getLoopLatch()));
1164 Result.Structure = MainLoopStructure.map(GetClonedValue);
1167 for (
unsigned i = 0, e =
Result.Blocks.size(); i != e; ++i) {
1169 BasicBlock *OriginalBB = OriginalLoop.getBlocks()[i];
1171 assert(
Result.Map[OriginalBB] == ClonedBB &&
"invariant!");
1182 if (OriginalLoop.contains(SBB))
1186 Value *OldIncoming = PN.getIncomingValueForBlock(OriginalBB);
1187 PN.addIncoming(GetClonedValue(OldIncoming), ClonedBB);
1194LoopConstrainer::RewrittenRangeInfo LoopConstrainer::changeIterationSpaceEnd(
1268 RewrittenRangeInfo RRI;
1270 BasicBlock *BBInsertLocation =
LS.Latch->getNextNode();
1272 &
F, BBInsertLocation);
1277 bool Increasing =
LS.IndVarIncreasing;
1278 bool IsSignedPredicate =
LS.IsSignedPredicate;
1281 auto *RangeTy =
Range.getBegin()->getType();
1282 auto NoopOrExt = [&](
Value *
V) {
1283 if (
V->getType() == RangeTy)
1285 return IsSignedPredicate ?
B.CreateSExt(V, RangeTy,
"wide." +
V->getName())
1286 :
B.CreateZExt(V, RangeTy,
"wide." +
V->getName());
1290 Value *EnterLoopCond =
nullptr;
1293 ? (IsSignedPredicate ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT)
1294 : (IsSignedPredicate ? ICmpInst::ICMP_SGT : ICmpInst::ICMP_UGT);
1295 Value *IndVarStart = NoopOrExt(
LS.IndVarStart);
1296 EnterLoopCond =
B.CreateICmp(Pred, IndVarStart, ExitSubloopAt);
1298 B.CreateCondBr(EnterLoopCond,
LS.Header, RRI.PseudoExit);
1301 LS.LatchBr->setSuccessor(
LS.LatchBrExitIdx, RRI.ExitSelector);
1302 B.SetInsertPoint(
LS.LatchBr);
1303 Value *IndVarBase = NoopOrExt(
LS.IndVarBase);
1304 Value *TakeBackedgeLoopCond =
B.CreateICmp(Pred, IndVarBase, ExitSubloopAt);
1306 Value *CondForBranch =
LS.LatchBrExitIdx == 1
1307 ? TakeBackedgeLoopCond
1308 :
B.CreateNot(TakeBackedgeLoopCond);
1310 LS.LatchBr->setCondition(CondForBranch);
1312 B.SetInsertPoint(RRI.ExitSelector);
1317 Value *LoopExitAt = NoopOrExt(
LS.LoopExitAt);
1318 Value *IterationsLeft =
B.CreateICmp(Pred, IndVarBase, LoopExitAt);
1319 B.CreateCondBr(IterationsLeft, RRI.PseudoExit,
LS.LatchExit);
1329 BranchToContinuation);
1331 NewPHI->
addIncoming(PN.getIncomingValueForBlock(Preheader), Preheader);
1334 RRI.PHIValuesAtPseudoExit.push_back(NewPHI);
1338 BranchToContinuation);
1339 RRI.IndVarEnd->addIncoming(IndVarStart, Preheader);
1340 RRI.IndVarEnd->addIncoming(IndVarBase, RRI.ExitSelector);
1344 LS.LatchExit->replacePhiUsesWith(
LS.Latch, RRI.ExitSelector);
1349void LoopConstrainer::rewriteIncomingValuesForPHIs(
1350 LoopStructure &LS,
BasicBlock *ContinuationBlock,
1351 const LoopConstrainer::RewrittenRangeInfo &RRI)
const {
1352 unsigned PHIIndex = 0;
1354 PN.setIncomingValueForBlock(ContinuationBlock,
1355 RRI.PHIValuesAtPseudoExit[PHIIndex++]);
1357 LS.IndVarStart = RRI.IndVarEnd;
1360BasicBlock *LoopConstrainer::createPreheader(
const LoopStructure &LS,
1362 const char *
Tag)
const {
1366 LS.Header->replacePhiUsesWith(OldPreheader, Preheader);
1380Loop *LoopConstrainer::createClonedLoopStructure(
Loop *Original,
Loop *Parent,
1383 Loop &
New = *LI.AllocateLoop();
1387 LI.addTopLevelLoop(&New);
1388 LPMAddNewLoop(&New, IsSubloop);
1391 for (
auto *BB : Original->
blocks())
1392 if (LI.getLoopFor(BB) == Original)
1393 New.addBasicBlockToLoop(cast<BasicBlock>(VM[BB]), LI);
1396 for (
Loop *SubLoop : *Original)
1397 createClonedLoopStructure(SubLoop, &New, VM,
true);
1402bool LoopConstrainer::run() {
1404 LatchTakenCount = SE.
getExitCount(&OriginalLoop, MainLoopStructure.Latch);
1405 Preheader = OriginalLoop.getLoopPreheader();
1406 assert(!isa<SCEVCouldNotCompute>(LatchTakenCount) && Preheader !=
nullptr &&
1409 OriginalPreheader = Preheader;
1410 MainLoopPreheader = Preheader;
1412 bool IsSignedPredicate = MainLoopStructure.IsSignedPredicate;
1413 std::optional<SubRanges> MaybeSR = calculateSubRanges(IsSignedPredicate);
1419 SubRanges SR = *MaybeSR;
1420 bool Increasing = MainLoopStructure.IndVarIncreasing;
1422 cast<IntegerType>(
Range.getBegin()->getType());
1424 SCEVExpander Expander(SE,
F.getParent()->getDataLayout(),
"irce");
1425 Instruction *InsertPt = OriginalPreheader->getTerminator();
1430 ClonedLoop PreLoop, PostLoop;
1432 Increasing ? SR.LowLimit.has_value() : SR.HighLimit.has_value();
1433 bool NeedsPostLoop =
1434 Increasing ? SR.HighLimit.has_value() : SR.LowLimit.has_value();
1436 Value *ExitPreLoopAt =
nullptr;
1437 Value *ExitMainLoopAt =
nullptr;
1439 cast<SCEVConstant>(SE.
getConstant(IVTy, -1,
true ));
1442 const SCEV *ExitPreLoopAtSCEV =
nullptr;
1445 ExitPreLoopAtSCEV = *SR.LowLimit;
1448 ExitPreLoopAtSCEV = SE.
getAddExpr(*SR.HighLimit, MinusOneS);
1450 LLVM_DEBUG(
dbgs() <<
"irce: could not prove no-overflow when computing "
1451 <<
"preloop exit limit. HighLimit = "
1452 << *(*SR.HighLimit) <<
"\n");
1456 if (!Expander.isSafeToExpandAt(ExitPreLoopAtSCEV, InsertPt)) {
1457 LLVM_DEBUG(
dbgs() <<
"irce: could not prove that it is safe to expand the"
1458 <<
" preloop exit limit " << *ExitPreLoopAtSCEV
1464 ExitPreLoopAt = Expander.expandCodeFor(ExitPreLoopAtSCEV, IVTy, InsertPt);
1465 ExitPreLoopAt->
setName(
"exit.preloop.at");
1468 if (NeedsPostLoop) {
1469 const SCEV *ExitMainLoopAtSCEV =
nullptr;
1472 ExitMainLoopAtSCEV = *SR.HighLimit;
1475 ExitMainLoopAtSCEV = SE.
getAddExpr(*SR.LowLimit, MinusOneS);
1477 LLVM_DEBUG(
dbgs() <<
"irce: could not prove no-overflow when computing "
1478 <<
"mainloop exit limit. LowLimit = "
1479 << *(*SR.LowLimit) <<
"\n");
1483 if (!Expander.isSafeToExpandAt(ExitMainLoopAtSCEV, InsertPt)) {
1484 LLVM_DEBUG(
dbgs() <<
"irce: could not prove that it is safe to expand the"
1485 <<
" main loop exit limit " << *ExitMainLoopAtSCEV
1491 ExitMainLoopAt = Expander.expandCodeFor(ExitMainLoopAtSCEV, IVTy, InsertPt);
1492 ExitMainLoopAt->
setName(
"exit.mainloop.at");
1502 RewrittenRangeInfo PreLoopRRI;
1506 PreLoop.Structure.Header);
1509 createPreheader(MainLoopStructure, Preheader,
"mainloop");
1510 PreLoopRRI = changeIterationSpaceEnd(PreLoop.Structure, Preheader,
1511 ExitPreLoopAt, MainLoopPreheader);
1512 rewriteIncomingValuesForPHIs(MainLoopStructure, MainLoopPreheader,
1517 RewrittenRangeInfo PostLoopRRI;
1519 if (NeedsPostLoop) {
1521 createPreheader(PostLoop.Structure, Preheader,
"postloop");
1522 PostLoopRRI = changeIterationSpaceEnd(MainLoopStructure, MainLoopPreheader,
1523 ExitMainLoopAt, PostLoopPreheader);
1524 rewriteIncomingValuesForPHIs(PostLoop.Structure, PostLoopPreheader,
1529 MainLoopPreheader != Preheader ? MainLoopPreheader :
nullptr;
1530 BasicBlock *NewBlocks[] = {PostLoopPreheader, PreLoopRRI.PseudoExit,
1531 PreLoopRRI.ExitSelector, PostLoopRRI.PseudoExit,
1532 PostLoopRRI.ExitSelector, NewMainLoopPreheader};
1537 std::remove(std::begin(NewBlocks), std::end(NewBlocks),
nullptr);
1539 addToParentLoopIfNeeded(
ArrayRef(std::begin(NewBlocks), NewBlocksEnd));
1547 Loop *PreL =
nullptr, *PostL =
nullptr;
1548 if (!PreLoop.Blocks.empty()) {
1549 PreL = createClonedLoopStructure(&OriginalLoop,
1550 OriginalLoop.getParentLoop(), PreLoop.Map,
1554 if (!PostLoop.Blocks.empty()) {
1556 createClonedLoopStructure(&OriginalLoop, OriginalLoop.getParentLoop(),
1557 PostLoop.Map,
false);
1561 auto CanonicalizeLoop = [&] (
Loop *
L,
bool IsOriginalLoop) {
1563 simplifyLoop(L, &DT, &LI, &SE,
nullptr,
nullptr,
true);
1566 if (!IsOriginalLoop)
1570 CanonicalizeLoop(PreL,
false);
1572 CanonicalizeLoop(PostL,
false);
1573 CanonicalizeLoop(&OriginalLoop,
true);
1581std::optional<InductiveRangeCheck::Range>
1584 bool IsLatchSigned)
const {
1587 auto *IVType = dyn_cast<IntegerType>(IndVar->
getType());
1588 auto *RCType = dyn_cast<IntegerType>(getBegin()->
getType());
1590 if (!IVType || !RCType)
1591 return std::nullopt;
1592 if (IVType->getBitWidth() > RCType->getBitWidth())
1593 return std::nullopt;
1615 return std::nullopt;
1621 return std::nullopt;
1622 assert(!
B->isZero() &&
"Recurrence with zero step?");
1624 const SCEV *
C = getBegin();
1627 return std::nullopt;
1629 assert(!
D->getValue()->isZero() &&
"Recurrence with zero step?");
1630 unsigned BitWidth = RCType->getBitWidth();
1645 auto ClampedSubtract = [&](
const SCEV *
X,
const SCEV *
Y) {
1650 if (IsLatchSigned) {
1681 auto SCEVCheckNonNegative = [&](
const SCEV *
X) {
1702 const SCEV *REnd = getEnd();
1703 const SCEV *EndIsNonNegative = SCEVCheckNonNegative(REnd);
1705 const SCEV *Begin = SE.
getMulExpr(ClampedSubtract(Zero, M), EndIsNonNegative);
1706 const SCEV *End = SE.
getMulExpr(ClampedSubtract(REnd, M), EndIsNonNegative);
1707 return InductiveRangeCheck::Range(Begin, End);
1710static std::optional<InductiveRangeCheck::Range>
1712 const std::optional<InductiveRangeCheck::Range> &R1,
1713 const InductiveRangeCheck::Range &
R2) {
1714 if (
R2.isEmpty(SE,
true))
1715 return std::nullopt;
1718 auto &R1Value = *R1;
1721 assert(!R1Value.isEmpty(SE,
true) &&
1722 "We should never have empty R1!");
1726 if (R1Value.getType() !=
R2.getType())
1727 return std::nullopt;
1733 auto Ret = InductiveRangeCheck::Range(NewBegin, NewEnd);
1734 if (Ret.isEmpty(SE,
true))
1735 return std::nullopt;
1739static std::optional<InductiveRangeCheck::Range>
1741 const std::optional<InductiveRangeCheck::Range> &R1,
1742 const InductiveRangeCheck::Range &
R2) {
1743 if (
R2.isEmpty(SE,
false))
1744 return std::nullopt;
1747 auto &R1Value = *R1;
1750 assert(!R1Value.isEmpty(SE,
false) &&
1751 "We should never have empty R1!");
1755 if (R1Value.getType() !=
R2.getType())
1756 return std::nullopt;
1762 auto Ret = InductiveRangeCheck::Range(NewBegin, NewEnd);
1763 if (Ret.isEmpty(SE,
false))
1764 return std::nullopt;
1783 InductiveRangeCheckElimination IRCE(SE, &BPI, DT, LI, { getBFI });
1785 bool Changed =
false;
1787 bool CFGChanged =
false;
1788 for (
const auto &L : LI) {
1789 CFGChanged |=
simplifyLoop(L, &DT, &LI, &SE,
nullptr,
nullptr,
1793 Changed |= CFGChanged;
1804 auto LPMAddNewLoop = [&Worklist](
Loop *
NL,
bool IsSubloop) {
1809 while (!Worklist.
empty()) {
1811 if (IRCE.run(L, LPMAddNewLoop)) {
1826bool IRCELegacyPass::runOnFunction(
Function &
F) {
1827 if (skipFunction(
F))
1830 ScalarEvolution &SE = getAnalysis<ScalarEvolutionWrapperPass>().getSE();
1832 getAnalysis<BranchProbabilityInfoWrapperPass>().getBPI();
1833 auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
1834 auto &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
1835 InductiveRangeCheckElimination IRCE(SE, &BPI, DT, LI);
1837 bool Changed =
false;
1839 for (
const auto &L : LI) {
1840 Changed |=
simplifyLoop(L, &DT, &LI, &SE,
nullptr,
nullptr,
1847 auto LPMAddNewLoop = [&](
Loop *
NL,
bool IsSubloop) {
1852 while (!Worklist.
empty()) {
1854 Changed |= IRCE.run(L, LPMAddNewLoop);
1860InductiveRangeCheckElimination::isProfitableToTransform(
const Loop &L,
1861 LoopStructure &LS) {
1866 uint64_t hFreq =
BFI.getBlockFreq(
LS.Header).getFrequency();
1867 uint64_t phFreq =
BFI.getBlockFreq(
L.getLoopPreheader()).getFrequency();
1870 <<
"the estimated number of iterations basing on "
1871 "frequency info is " << (hFreq / phFreq) <<
"\n";);
1883 <<
"the exit probability is too big " << ExitProbability
1890bool InductiveRangeCheckElimination::run(
1893 LLVM_DEBUG(
dbgs() <<
"irce: giving up constraining loop, too large\n");
1906 for (
auto *BBI :
L->getBlocks())
1907 if (
BranchInst *TBI = dyn_cast<BranchInst>(BBI->getTerminator()))
1908 InductiveRangeCheck::extractRangeChecksFromBranch(TBI, L, SE, BPI,
1911 if (RangeChecks.
empty())
1915 OS <<
"irce: looking at loop ";
L->print(
OS);
1916 OS <<
"irce: loop has " << RangeChecks.
size()
1917 <<
" inductive range checks: \n";
1918 for (InductiveRangeCheck &IRC : RangeChecks)
1925 PrintRecognizedRangeChecks(
errs());
1927 const char *FailureReason =
nullptr;
1928 std::optional<LoopStructure> MaybeLoopStructure =
1929 LoopStructure::parseLoopStructure(SE, *L, FailureReason);
1930 if (!MaybeLoopStructure) {
1932 << FailureReason <<
"\n";);
1935 LoopStructure
LS = *MaybeLoopStructure;
1941 std::optional<InductiveRangeCheck::Range> SafeIterRange;
1949 auto IntersectRange =
1953 for (InductiveRangeCheck &IRC : RangeChecks) {
1954 auto Result = IRC.computeSafeIterationSpace(SE, IndVar,
1955 LS.IsSignedPredicate);
1957 auto MaybeSafeIterRange = IntersectRange(SE, SafeIterRange, *Result);
1958 if (MaybeSafeIterRange) {
1959 assert(!MaybeSafeIterRange->isEmpty(SE,
LS.IsSignedPredicate) &&
1960 "We should never return empty ranges!");
1962 SafeIterRange = *MaybeSafeIterRange;
1970 LoopConstrainer LC(*L, LI, LPMAddNewLoop, LS, SE, DT, *SafeIterRange);
1971 bool Changed = LC.run();
1974 auto PrintConstrainedLoopInfo = [
L]() {
1975 dbgs() <<
"irce: in function ";
1976 dbgs() <<
L->getHeader()->getParent()->getName() <<
": ";
1977 dbgs() <<
"constrained ";
1984 PrintConstrainedLoopInfo();
1988 for (InductiveRangeCheck &IRC : RangeChecksToEliminate) {
1989 ConstantInt *FoldedRangeCheck = IRC.getPassingDirection()
1992 IRC.getCheckUse()->set(FoldedRangeCheck);
2000 return new IRCELegacyPass();
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
This file implements a class to represent arbitrary precision integral constant values and operations...
static void print(raw_ostream &Out, object::Archive::Kind Kind, T Val)
static const Function * getParent(const Value *V)
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds.
This file contains the declarations for the subclasses of Constant, which represent the different fla...
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
This file provides various utilities for inspecting and working with the control flow graph in LLVM I...
static const SCEV * NoopOrExtend(const SCEV *S, Type *Ty, ScalarEvolution &SE, bool Signed)
If the type of S matches with Ty, return S.
static cl::opt< bool > PrintRangeChecks("irce-print-range-checks", cl::Hidden, cl::init(false))
static cl::opt< bool > AllowUnsignedLatchCondition("irce-allow-unsigned-latch", cl::Hidden, cl::init(true))
static const char * ClonedLoopTag
static cl::opt< unsigned > MinRuntimeIterations("irce-min-runtime-iterations", cl::Hidden, cl::init(10))
static cl::opt< unsigned > LoopSizeCutoff("irce-loop-size-cutoff", cl::Hidden, cl::init(64))
static std::optional< InductiveRangeCheck::Range > IntersectSignedRange(ScalarEvolution &SE, const std::optional< InductiveRangeCheck::Range > &R1, const InductiveRangeCheck::Range &R2)
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."))
Inductive range check elimination
static cl::opt< bool > PrintChangedLoops("irce-print-changed-loops", cl::Hidden, cl::init(false))
static std::optional< InductiveRangeCheck::Range > IntersectUnsignedRange(ScalarEvolution &SE, const std::optional< InductiveRangeCheck::Range > &R1, const InductiveRangeCheck::Range &R2)
static cl::opt< bool > SkipProfitabilityChecks("irce-skip-profitability-checks", cl::Hidden, cl::init(false))
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...
static void DisableAllLoopOptsOnLoop(Loop &L)
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 ...
static Constant * getFalse(Type *Ty)
For a boolean type or a vector of boolean type, return false or a vector with every element false.
This header provides classes for managing per-loop analyses.
Module.h This file contains the declarations for the Module class.
static GCMetadataPrinterRegistry::Add< OcamlGCMetadataPrinter > Y("ocaml", "ocaml 3.10-compatible collector")
#define INITIALIZE_PASS_DEPENDENCY(depName)
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
This file provides a priority worklist.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file defines the SmallPtrSet class.
This file defines the SmallVector class.
static SymbolRef::Type getType(const Symbol *Sym)
This defines the Use class.
Class for arbitrary precision integers.
static APInt getMaxValue(unsigned numBits)
Gets maximum unsigned value of APInt for specific bit width.
static APInt getSignedMaxValue(unsigned numBits)
Gets maximum signed value of APInt for a specific bit width.
static APInt getMinValue(unsigned numBits)
Gets minimum unsigned value of APInt for a specific bit width.
static APInt getSignedMinValue(unsigned numBits)
Gets minimum signed value of APInt for a specific bit width.
A container for analyses that lazily runs them and caches their results.
void invalidate(IRUnitT &IR, const PreservedAnalyses &PA)
Invalidate cached analyses for an IR unit.
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Represent the analysis usage information of a pass.
AnalysisUsage & addRequired()
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
LLVM Basic Block Representation.
static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)
Creates a new BasicBlock.
LLVMContext & getContext() const
Get the context in which this basic block lives.
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...
const Module * getModule() const
Return the module owning the function this basic block belongs to, or nullptr if the function does no...
Analysis pass which computes BlockFrequencyInfo.
BlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate IR basic block frequen...
Conditional or Unconditional Branch instruction.
static BranchInst * Create(BasicBlock *IfTrue, Instruction *InsertBefore=nullptr)
BasicBlock * getSuccessor(unsigned i) const
bool isUnconditional() const
Value * getCondition() const
Analysis pass which computes BranchProbabilityInfo.
Legacy analysis pass which computes BranchProbabilityInfo.
Analysis providing branch probability information.
BranchProbability getEdgeProbability(const BasicBlock *Src, unsigned IndexInSuccessors) const
Get an edge's probability, relative to other out-edges of the Src.
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
@ ICMP_SLT
signed less than
@ ICMP_UGT
unsigned greater than
@ ICMP_SGT
signed greater than
@ ICMP_ULT
unsigned less than
Predicate getPredicate() const
Return the predicate for this instruction.
This is the shared class of boolean and integer constants.
bool isMinusOne() const
This function will return true iff every bit in this constant is set to true.
bool isOne() const
This is just a convenience method to make client code smaller for a common case.
static ConstantInt * getTrue(LLVMContext &Context)
bool isZero() const
This is just a convenience method to make client code smaller for a common code.
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.
const APInt & getValue() const
Return the constant as an APInt value reference.
A parsed version of the target data layout string in and methods for querying it.
Analysis pass which computes a DominatorTree.
Legacy analysis pass which computes a DominatorTree.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
FunctionPass class - This class is used to implement most global optimizations.
virtual bool runOnFunction(Function &F)=0
runOnFunction - Virtual method overriden by subclasses to do the per-function processing of the pass.
This instruction compares its operands according to the predicate given to the constructor.
static bool isEquality(Predicate P)
Return true if this predicate is either EQ or NE.
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
const BasicBlock * getParent() const
MDNode * getMetadata(unsigned KindID) const
Get the metadata of given kind attached to this Instruction.
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
Class to represent integer types.
static IntegerType * get(LLVMContext &C, unsigned NumBits)
This static method is the primary way of constructing an IntegerType.
unsigned getBitWidth() const
Get the number of bits in this IntegerType.
This is an important class for using LLVM in a threaded context.
Analysis pass that exposes the LoopInfo for a function.
void addBasicBlockToLoop(BlockT *NewBB, LoopInfoBase< BlockT, LoopT > &LI)
This method is used by other analyses to update loop information.
iterator_range< block_iterator > blocks() const
void addChildLoop(LoopT *NewChild)
Add the specified loop to be a child of this loop.
LoopT * getParentLoop() const
Return the parent loop if it exists or nullptr for top level loops.
The legacy pass manager's analysis pass to compute loop information.
Represents a single loop in the control flow graph.
void replaceOperandWith(unsigned I, Metadata *New)
Replace a specific operand.
static MDTuple * get(LLVMContext &Context, ArrayRef< Metadata * > MDs)
static MDString * get(LLVMContext &Context, StringRef Str)
const DataLayout & getDataLayout() const
Get the data layout for the module's target platform.
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
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...
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Pass interface - Implemented by all 'passes'.
virtual void getAnalysisUsage(AnalysisUsage &) const
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
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.
void abandon()
Mark an analysis as abandoned.
bool empty() const
Determine if the PriorityWorklist is empty or not.
This node represents a polynomial recurrence on the trip count of the specified loop.
const SCEV * getStart() const
const SCEV * getStepRecurrence(ScalarEvolution &SE) const
Constructs and returns the recurrence indicating how much this expression steps by.
bool isAffine() const
Return true if this represents an expression A + B*x where A and B are loop invariant values.
const Loop * getLoop() const
This class represents a constant integer value.
This class uses information about analyze scalars to rewrite expressions in canonical form.
NoWrapFlags getNoWrapFlags(NoWrapFlags Mask=NoWrapMask) const
This class represents an analyzed expression in the program.
void print(raw_ostream &OS) const
Print out the internal representation of this scalar to the specified stream.
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.
const SCEV * getNegativeSCEV(const SCEV *V, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap)
Return the SCEV object corresponding to -V.
const SCEV * getSMaxExpr(const SCEV *LHS, const SCEV *RHS)
bool isKnownNegative(const SCEV *S)
Test if the given expression is known to be negative.
const SCEV * getSMinExpr(const SCEV *LHS, const SCEV *RHS)
const SCEV * getUMaxExpr(const SCEV *LHS, const SCEV *RHS)
const SCEV * getZero(Type *Ty)
Return a SCEV for the constant 0 of a specific type.
const SCEV * getConstant(ConstantInt *V)
const SCEV * getSCEV(Value *V)
Return a SCEV expression for the full generality of the specified expression.
const SCEV * getNoopOrSignExtend(const SCEV *V, Type *Ty)
Return a SCEV corresponding to a conversion of the input value to the specified type.
const SCEV * getOne(Type *Ty)
Return a SCEV for the constant 1 of a specific type.
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,...
LoopDisposition getLoopDisposition(const SCEV *S, const Loop *L)
Return the "disposition" of the given SCEV with respect to the given loop.
const SCEV * getUMinExpr(const SCEV *LHS, const SCEV *RHS, bool Sequential=false)
void forgetValue(Value *V)
This method should be called by the client when it has changed a value in a way that may effect its v...
const SCEV * getMinusSCEV(const SCEV *LHS, const SCEV *RHS, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
Return LHS-RHS.
const SCEV * getNoopOrZeroExtend(const SCEV *V, Type *Ty)
Return a SCEV corresponding to a conversion of the input value to the specified type.
@ LoopInvariant
The SCEV is loop-invariant.
bool isAvailableAtLoopEntry(const SCEV *S, const Loop *L)
Determine if the SCEV can be evaluated at loop's entry.
const SCEV * getExitCount(const Loop *L, const BasicBlock *ExitingBlock, ExitCountKind Kind=Exact)
Return the number of times the backedge executes before the given exit would be taken; if not exactly...
const SCEV * getSignExtendExpr(const SCEV *Op, Type *Ty, unsigned Depth=0)
const SCEV * getMulExpr(SmallVectorImpl< const SCEV * > &Ops, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
Get a canonical multiply expression, or something simpler if possible.
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.
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.
A version of PriorityWorklist that selects small size optimized data structures for the vector and ma...
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
The instances of the Type class are immutable: once they are created, they are never changed.
static IntegerType * getInt1Ty(LLVMContext &C)
LLVMContext & getContext() const
Return the LLVMContext in which this type was uniqued.
A Use represents the edge between a Value definition and its users.
bool replaceUsesOfWith(Value *From, Value *To)
Replace uses of one Value with another.
const Use & getOperandUse(unsigned i) const
Value * getOperand(unsigned i) const
LLVM Value Representation.
Type * getType() const
All values are typed, get the type of this value.
void setName(const Twine &Name)
Change the name of the value.
StringRef getName() const
Return a constant reference to the value's name.
An efficient, type-erasing, non-owning reference to a callable.
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.
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
@ C
The default llvm calling convention, compatible with C.
bool match(Val *V, const Pattern &P)
class_match< Value > m_Value()
Match an arbitrary value and ignore it.
auto m_LogicalAnd()
Matches L && R where L and R are arbitrary values.
initializer< Ty > init(const Ty &Val)
PointerTypeMap run(const Module &M)
Compute the PointerTypeMap for the module M.
This is an optimization pass for GlobalISel generic memory operations.
bool simplifyLoop(Loop *L, DominatorTree *DT, LoopInfo *LI, ScalarEvolution *SE, AssumptionCache *AC, MemorySSAUpdater *MSSAU, bool PreserveLCSSA)
Simplify each loop in a loop nest recursively.
void dump(const SparseBitVector< ElementSize > &LHS, raw_ostream &out)
Pass * createInductiveRangeCheckEliminationPass()
auto successors(const MachineBasicBlock *BB)
bool formLCSSARecursively(Loop &L, const DominatorTree &DT, const LoopInfo *LI, ScalarEvolution *SE)
Put a loop nest into LCSSA form.
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.
void initializeIRCELegacyPassPass(PassRegistry &)
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...
@ RF_IgnoreMissingLocals
If this flag is set, the remapper ignores missing function-local entries (Argument,...
@ RF_NoModuleLevelChanges
If this flag is set, the remapper knows that only local values within a function (such as an instruct...
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
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.
raw_fd_ostream & errs()
This returns a reference to a raw_ostream for standard error.
void appendLoopsToWorklist(RangeT &&, SmallPriorityWorklist< Loop *, 4 > &)
Utility that implements appending of loops onto a worklist given a range.
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.
constexpr unsigned BitWidth
PreservedAnalyses getLoopPassPreservedAnalyses()
Returns the minimum set of Analyses that all loop passes must preserve.
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.
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.
static bool isProfitableToTransform(const Loop &L, const BranchInst *BI)
Loop * cloneLoop(Loop *L, Loop *PL, ValueToValueMapTy &VM, LoopInfo *LI, LPPassManager *LPM)
Recursively clone the specified loop and all of its children, mapping the blocks with the specified m...
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.