1 //===-- InductiveRangeCheckElimination.cpp - ------------------------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
9 // The InductiveRangeCheckElimination pass splits a loop's iteration space into
10 // three disjoint ranges. It does that in a way such that the loop running in
11 // the middle loop provably does not need range checks. As an example, it will
14 // len = < known positive >
15 // for (i = 0; i < n; i++) {
16 // if (0 <= i && i < len) {
19 // throw_out_of_bounds();
25 // len = < known positive >
26 // limit = smin(n, len)
27 // // no first segment
28 // for (i = 0; i < limit; i++) {
29 // if (0 <= i && i < len) { // this check is fully redundant
32 // throw_out_of_bounds();
35 // for (i = limit; i < n; i++) {
36 // if (0 <= i && i < len) {
39 // throw_out_of_bounds();
42 //===----------------------------------------------------------------------===//
44 #include "llvm/ADT/Optional.h"
45 #include "llvm/Analysis/BranchProbabilityInfo.h"
46 #include "llvm/Analysis/InstructionSimplify.h"
47 #include "llvm/Analysis/LoopInfo.h"
48 #include "llvm/Analysis/LoopPass.h"
49 #include "llvm/Analysis/ScalarEvolution.h"
50 #include "llvm/Analysis/ScalarEvolutionExpander.h"
51 #include "llvm/Analysis/ScalarEvolutionExpressions.h"
52 #include "llvm/Analysis/ValueTracking.h"
53 #include "llvm/IR/Dominators.h"
54 #include "llvm/IR/Function.h"
55 #include "llvm/IR/IRBuilder.h"
56 #include "llvm/IR/Instructions.h"
57 #include "llvm/IR/Module.h"
58 #include "llvm/IR/PatternMatch.h"
59 #include "llvm/IR/ValueHandle.h"
60 #include "llvm/IR/Verifier.h"
61 #include "llvm/Pass.h"
62 #include "llvm/Support/Debug.h"
63 #include "llvm/Support/raw_ostream.h"
64 #include "llvm/Transforms/Scalar.h"
65 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
66 #include "llvm/Transforms/Utils/Cloning.h"
67 #include "llvm/Transforms/Utils/LoopUtils.h"
68 #include "llvm/Transforms/Utils/SimplifyIndVar.h"
69 #include "llvm/Transforms/Utils/UnrollLoop.h"
74 static cl::opt<unsigned> LoopSizeCutoff("irce-loop-size-cutoff", cl::Hidden,
77 static cl::opt<bool> PrintChangedLoops("irce-print-changed-loops", cl::Hidden,
80 static cl::opt<bool> PrintRangeChecks("irce-print-range-checks", cl::Hidden,
83 static cl::opt<int> MaxExitProbReciprocal("irce-max-exit-prob-reciprocal",
84 cl::Hidden, cl::init(10));
86 #define DEBUG_TYPE "irce"
90 /// An inductive range check is conditional branch in a loop with
92 /// 1. a very cold successor (i.e. the branch jumps to that successor very
97 /// 2. a condition that is provably true for some contiguous range of values
98 /// taken by the containing loop's induction variable.
100 class InductiveRangeCheck {
101 // Classifies a range check
102 enum RangeCheckKind : unsigned {
103 // Range check of the form "0 <= I".
104 RANGE_CHECK_LOWER = 1,
106 // Range check of the form "I < L" where L is known positive.
107 RANGE_CHECK_UPPER = 2,
109 // The logical and of the RANGE_CHECK_LOWER and RANGE_CHECK_UPPER
111 RANGE_CHECK_BOTH = RANGE_CHECK_LOWER | RANGE_CHECK_UPPER,
113 // Unrecognized range check condition.
114 RANGE_CHECK_UNKNOWN = (unsigned)-1
117 static const char *rangeCheckKindToStr(RangeCheckKind);
125 static RangeCheckKind parseRangeCheckICmp(Loop *L, ICmpInst *ICI,
126 ScalarEvolution &SE, Value *&Index,
129 static InductiveRangeCheck::RangeCheckKind
130 parseRangeCheck(Loop *L, ScalarEvolution &SE, Value *Condition,
131 const SCEV *&Index, Value *&UpperLimit);
133 InductiveRangeCheck() :
134 Offset(nullptr), Scale(nullptr), Length(nullptr), Branch(nullptr) { }
137 const SCEV *getOffset() const { return Offset; }
138 const SCEV *getScale() const { return Scale; }
139 Value *getLength() const { return Length; }
141 void print(raw_ostream &OS) const {
142 OS << "InductiveRangeCheck:\n";
143 OS << " Kind: " << rangeCheckKindToStr(Kind) << "\n";
154 getBranch()->print(OS);
158 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
164 BranchInst *getBranch() const { return Branch; }
166 /// Represents an signed integer range [Range.getBegin(), Range.getEnd()). If
167 /// R.getEnd() sle R.getBegin(), then R denotes the empty range.
174 Range(const SCEV *Begin, const SCEV *End) : Begin(Begin), End(End) {
175 assert(Begin->getType() == End->getType() && "ill-typed range!");
178 Type *getType() const { return Begin->getType(); }
179 const SCEV *getBegin() const { return Begin; }
180 const SCEV *getEnd() const { return End; }
183 typedef SpecificBumpPtrAllocator<InductiveRangeCheck> AllocatorTy;
185 /// This is the value the condition of the branch needs to evaluate to for the
186 /// branch to take the hot successor (see (1) above).
187 bool getPassingDirection() { return true; }
189 /// Computes a range for the induction variable (IndVar) in which the range
190 /// check is redundant and can be constant-folded away. The induction
191 /// variable is not required to be the canonical {0,+,1} induction variable.
192 Optional<Range> computeSafeIterationSpace(ScalarEvolution &SE,
193 const SCEVAddRecExpr *IndVar,
194 IRBuilder<> &B) const;
196 /// Create an inductive range check out of BI if possible, else return
198 static InductiveRangeCheck *create(AllocatorTy &Alloc, BranchInst *BI,
199 Loop *L, ScalarEvolution &SE,
200 BranchProbabilityInfo &BPI);
203 class InductiveRangeCheckElimination : public LoopPass {
204 InductiveRangeCheck::AllocatorTy Allocator;
208 InductiveRangeCheckElimination() : LoopPass(ID) {
209 initializeInductiveRangeCheckEliminationPass(
210 *PassRegistry::getPassRegistry());
213 void getAnalysisUsage(AnalysisUsage &AU) const override {
214 AU.addRequired<LoopInfoWrapperPass>();
215 AU.addRequiredID(LoopSimplifyID);
216 AU.addRequiredID(LCSSAID);
217 AU.addRequired<ScalarEvolution>();
218 AU.addRequired<BranchProbabilityInfoWrapperPass>();
221 bool runOnLoop(Loop *L, LPPassManager &LPM) override;
224 char InductiveRangeCheckElimination::ID = 0;
227 INITIALIZE_PASS(InductiveRangeCheckElimination, "irce",
228 "Inductive range check elimination", false, false)
230 const char *InductiveRangeCheck::rangeCheckKindToStr(
231 InductiveRangeCheck::RangeCheckKind RCK) {
233 case InductiveRangeCheck::RANGE_CHECK_UNKNOWN:
234 return "RANGE_CHECK_UNKNOWN";
236 case InductiveRangeCheck::RANGE_CHECK_UPPER:
237 return "RANGE_CHECK_UPPER";
239 case InductiveRangeCheck::RANGE_CHECK_LOWER:
240 return "RANGE_CHECK_LOWER";
242 case InductiveRangeCheck::RANGE_CHECK_BOTH:
243 return "RANGE_CHECK_BOTH";
246 llvm_unreachable("unknown range check type!");
249 /// Parse a single ICmp instruction, `ICI`, into a range check. If `ICI`
251 /// be interpreted as a range check, return `RANGE_CHECK_UNKNOWN` and set
252 /// `Index` and `Length` to `nullptr`. Otherwise set `Index` to the value
254 /// range checked, and set `Length` to the upper limit `Index` is being range
255 /// checked with if (and only if) the range check type is stronger or equal to
256 /// RANGE_CHECK_UPPER.
258 InductiveRangeCheck::RangeCheckKind
259 InductiveRangeCheck::parseRangeCheckICmp(Loop *L, ICmpInst *ICI,
260 ScalarEvolution &SE, Value *&Index,
263 auto IsNonNegativeAndNotLoopVarying = [&SE, L](Value *V) {
264 const SCEV *S = SE.getSCEV(V);
265 if (isa<SCEVCouldNotCompute>(S))
268 return SE.getLoopDisposition(S, L) == ScalarEvolution::LoopInvariant &&
269 SE.isKnownNonNegative(S);
272 using namespace llvm::PatternMatch;
274 ICmpInst::Predicate Pred = ICI->getPredicate();
275 Value *LHS = ICI->getOperand(0);
276 Value *RHS = ICI->getOperand(1);
280 return RANGE_CHECK_UNKNOWN;
282 case ICmpInst::ICMP_SLE:
285 case ICmpInst::ICMP_SGE:
286 if (match(RHS, m_ConstantInt<0>())) {
288 return RANGE_CHECK_LOWER;
290 return RANGE_CHECK_UNKNOWN;
292 case ICmpInst::ICMP_SLT:
295 case ICmpInst::ICMP_SGT:
296 if (match(RHS, m_ConstantInt<-1>())) {
298 return RANGE_CHECK_LOWER;
301 if (IsNonNegativeAndNotLoopVarying(LHS)) {
304 return RANGE_CHECK_UPPER;
306 return RANGE_CHECK_UNKNOWN;
308 case ICmpInst::ICMP_ULT:
311 case ICmpInst::ICMP_UGT:
312 if (IsNonNegativeAndNotLoopVarying(LHS)) {
315 return RANGE_CHECK_BOTH;
317 return RANGE_CHECK_UNKNOWN;
320 llvm_unreachable("default clause returns!");
323 /// Parses an arbitrary condition into a range check. `Length` is set only if
324 /// the range check is recognized to be `RANGE_CHECK_UPPER` or stronger.
325 InductiveRangeCheck::RangeCheckKind
326 InductiveRangeCheck::parseRangeCheck(Loop *L, ScalarEvolution &SE,
327 Value *Condition, const SCEV *&Index,
329 using namespace llvm::PatternMatch;
334 if (match(Condition, m_And(m_Value(A), m_Value(B)))) {
335 Value *IndexA = nullptr, *IndexB = nullptr;
336 Value *LengthA = nullptr, *LengthB = nullptr;
337 ICmpInst *ICmpA = dyn_cast<ICmpInst>(A), *ICmpB = dyn_cast<ICmpInst>(B);
339 if (!ICmpA || !ICmpB)
340 return InductiveRangeCheck::RANGE_CHECK_UNKNOWN;
342 auto RCKindA = parseRangeCheckICmp(L, ICmpA, SE, IndexA, LengthA);
343 auto RCKindB = parseRangeCheckICmp(L, ICmpB, SE, IndexB, LengthB);
345 if (RCKindA == InductiveRangeCheck::RANGE_CHECK_UNKNOWN ||
346 RCKindB == InductiveRangeCheck::RANGE_CHECK_UNKNOWN)
347 return InductiveRangeCheck::RANGE_CHECK_UNKNOWN;
349 if (IndexA != IndexB)
350 return InductiveRangeCheck::RANGE_CHECK_UNKNOWN;
352 if (LengthA != nullptr && LengthB != nullptr && LengthA != LengthB)
353 return InductiveRangeCheck::RANGE_CHECK_UNKNOWN;
355 Index = SE.getSCEV(IndexA);
356 if (isa<SCEVCouldNotCompute>(Index))
357 return InductiveRangeCheck::RANGE_CHECK_UNKNOWN;
359 Length = LengthA == nullptr ? LengthB : LengthA;
361 return (InductiveRangeCheck::RangeCheckKind)(RCKindA | RCKindB);
364 if (ICmpInst *ICI = dyn_cast<ICmpInst>(Condition)) {
365 Value *IndexVal = nullptr;
367 auto RCKind = parseRangeCheckICmp(L, ICI, SE, IndexVal, Length);
369 if (RCKind == InductiveRangeCheck::RANGE_CHECK_UNKNOWN)
370 return InductiveRangeCheck::RANGE_CHECK_UNKNOWN;
372 Index = SE.getSCEV(IndexVal);
373 if (isa<SCEVCouldNotCompute>(Index))
374 return InductiveRangeCheck::RANGE_CHECK_UNKNOWN;
379 return InductiveRangeCheck::RANGE_CHECK_UNKNOWN;
383 InductiveRangeCheck *
384 InductiveRangeCheck::create(InductiveRangeCheck::AllocatorTy &A, BranchInst *BI,
385 Loop *L, ScalarEvolution &SE,
386 BranchProbabilityInfo &BPI) {
388 if (BI->isUnconditional() || BI->getParent() == L->getLoopLatch())
391 BranchProbability LikelyTaken(15, 16);
393 if (BPI.getEdgeProbability(BI->getParent(), (unsigned) 0) < LikelyTaken)
396 Value *Length = nullptr;
397 const SCEV *IndexSCEV = nullptr;
399 auto RCKind = InductiveRangeCheck::parseRangeCheck(L, SE, BI->getCondition(),
402 if (RCKind == InductiveRangeCheck::RANGE_CHECK_UNKNOWN)
405 assert(IndexSCEV && "contract with SplitRangeCheckCondition!");
406 assert((!(RCKind & InductiveRangeCheck::RANGE_CHECK_UPPER) || Length) &&
407 "contract with SplitRangeCheckCondition!");
409 const SCEVAddRecExpr *IndexAddRec = dyn_cast<SCEVAddRecExpr>(IndexSCEV);
411 IndexAddRec && (IndexAddRec->getLoop() == L) && IndexAddRec->isAffine();
416 InductiveRangeCheck *IRC = new (A.Allocate()) InductiveRangeCheck;
417 IRC->Length = Length;
418 IRC->Offset = IndexAddRec->getStart();
419 IRC->Scale = IndexAddRec->getStepRecurrence(SE);
427 // Keeps track of the structure of a loop. This is similar to llvm::Loop,
428 // except that it is more lightweight and can track the state of a loop through
429 // changing and potentially invalid IR. This structure also formalizes the
430 // kinds of loops we can deal with -- ones that have a single latch that is also
431 // an exiting block *and* have a canonical induction variable.
432 struct LoopStructure {
438 // `Latch's terminator instruction is `LatchBr', and it's `LatchBrExitIdx'th
439 // successor is `LatchExit', the exit block of the loop.
441 BasicBlock *LatchExit;
442 unsigned LatchBrExitIdx;
447 bool IndVarIncreasing;
450 : Tag(""), Header(nullptr), Latch(nullptr), LatchBr(nullptr),
451 LatchExit(nullptr), LatchBrExitIdx(-1), IndVarNext(nullptr),
452 IndVarStart(nullptr), LoopExitAt(nullptr), IndVarIncreasing(false) {}
454 template <typename M> LoopStructure map(M Map) const {
455 LoopStructure Result;
457 Result.Header = cast<BasicBlock>(Map(Header));
458 Result.Latch = cast<BasicBlock>(Map(Latch));
459 Result.LatchBr = cast<BranchInst>(Map(LatchBr));
460 Result.LatchExit = cast<BasicBlock>(Map(LatchExit));
461 Result.LatchBrExitIdx = LatchBrExitIdx;
462 Result.IndVarNext = Map(IndVarNext);
463 Result.IndVarStart = Map(IndVarStart);
464 Result.LoopExitAt = Map(LoopExitAt);
465 Result.IndVarIncreasing = IndVarIncreasing;
469 static Optional<LoopStructure> parseLoopStructure(ScalarEvolution &,
470 BranchProbabilityInfo &BPI,
475 /// This class is used to constrain loops to run within a given iteration space.
476 /// The algorithm this class implements is given a Loop and a range [Begin,
477 /// End). The algorithm then tries to break out a "main loop" out of the loop
478 /// it is given in a way that the "main loop" runs with the induction variable
479 /// in a subset of [Begin, End). The algorithm emits appropriate pre and post
480 /// loops to run any remaining iterations. The pre loop runs any iterations in
481 /// which the induction variable is < Begin, and the post loop runs any
482 /// iterations in which the induction variable is >= End.
484 class LoopConstrainer {
485 // The representation of a clone of the original loop we started out with.
488 std::vector<BasicBlock *> Blocks;
490 // `Map` maps values in the clonee into values in the cloned version
491 ValueToValueMapTy Map;
493 // An instance of `LoopStructure` for the cloned loop
494 LoopStructure Structure;
497 // Result of rewriting the range of a loop. See changeIterationSpaceEnd for
498 // more details on what these fields mean.
499 struct RewrittenRangeInfo {
500 BasicBlock *PseudoExit;
501 BasicBlock *ExitSelector;
502 std::vector<PHINode *> PHIValuesAtPseudoExit;
506 : PseudoExit(nullptr), ExitSelector(nullptr), IndVarEnd(nullptr) {}
509 // Calculated subranges we restrict the iteration space of the main loop to.
510 // See the implementation of `calculateSubRanges' for more details on how
511 // these fields are computed. `LowLimit` is None if there is no restriction
512 // on low end of the restricted iteration space of the main loop. `HighLimit`
513 // is None if there is no restriction on high end of the restricted iteration
514 // space of the main loop.
517 Optional<const SCEV *> LowLimit;
518 Optional<const SCEV *> HighLimit;
521 // A utility function that does a `replaceUsesOfWith' on the incoming block
522 // set of a `PHINode' -- replaces instances of `Block' in the `PHINode's
523 // incoming block list with `ReplaceBy'.
524 static void replacePHIBlock(PHINode *PN, BasicBlock *Block,
525 BasicBlock *ReplaceBy);
527 // Compute a safe set of limits for the main loop to run in -- effectively the
528 // intersection of `Range' and the iteration space of the original loop.
529 // Return None if unable to compute the set of subranges.
531 Optional<SubRanges> calculateSubRanges() const;
533 // Clone `OriginalLoop' and return the result in CLResult. The IR after
534 // running `cloneLoop' is well formed except for the PHI nodes in CLResult --
535 // the PHI nodes say that there is an incoming edge from `OriginalPreheader`
536 // but there is no such edge.
538 void cloneLoop(ClonedLoop &CLResult, const char *Tag) const;
540 // Rewrite the iteration space of the loop denoted by (LS, Preheader). The
541 // iteration space of the rewritten loop ends at ExitLoopAt. The start of the
542 // iteration space is not changed. `ExitLoopAt' is assumed to be slt
543 // `OriginalHeaderCount'.
545 // If there are iterations left to execute, control is made to jump to
546 // `ContinuationBlock', otherwise they take the normal loop exit. The
547 // returned `RewrittenRangeInfo' object is populated as follows:
549 // .PseudoExit is a basic block that unconditionally branches to
550 // `ContinuationBlock'.
552 // .ExitSelector is a basic block that decides, on exit from the loop,
553 // whether to branch to the "true" exit or to `PseudoExit'.
555 // .PHIValuesAtPseudoExit are PHINodes in `PseudoExit' that compute the value
556 // for each PHINode in the loop header on taking the pseudo exit.
558 // After changeIterationSpaceEnd, `Preheader' is no longer a legitimate
559 // preheader because it is made to branch to the loop header only
563 changeIterationSpaceEnd(const LoopStructure &LS, BasicBlock *Preheader,
565 BasicBlock *ContinuationBlock) const;
567 // The loop denoted by `LS' has `OldPreheader' as its preheader. This
568 // function creates a new preheader for `LS' and returns it.
570 BasicBlock *createPreheader(const LoopStructure &LS, BasicBlock *OldPreheader,
571 const char *Tag) const;
573 // `ContinuationBlockAndPreheader' was the continuation block for some call to
574 // `changeIterationSpaceEnd' and is the preheader to the loop denoted by `LS'.
575 // This function rewrites the PHI nodes in `LS.Header' to start with the
577 void rewriteIncomingValuesForPHIs(
578 LoopStructure &LS, BasicBlock *ContinuationBlockAndPreheader,
579 const LoopConstrainer::RewrittenRangeInfo &RRI) const;
581 // Even though we do not preserve any passes at this time, we at least need to
582 // keep the parent loop structure consistent. The `LPPassManager' seems to
583 // verify this after running a loop pass. This function adds the list of
584 // blocks denoted by BBs to this loops parent loop if required.
585 void addToParentLoopIfNeeded(ArrayRef<BasicBlock *> BBs);
587 // Some global state.
592 // Information about the original loop we started out with.
594 LoopInfo &OriginalLoopInfo;
595 const SCEV *LatchTakenCount;
596 BasicBlock *OriginalPreheader;
598 // The preheader of the main loop. This may or may not be different from
599 // `OriginalPreheader'.
600 BasicBlock *MainLoopPreheader;
602 // The range we need to run the main loop in.
603 InductiveRangeCheck::Range Range;
605 // The structure of the main loop (see comment at the beginning of this class
607 LoopStructure MainLoopStructure;
610 LoopConstrainer(Loop &L, LoopInfo &LI, const LoopStructure &LS,
611 ScalarEvolution &SE, InductiveRangeCheck::Range R)
612 : F(*L.getHeader()->getParent()), Ctx(L.getHeader()->getContext()),
613 SE(SE), OriginalLoop(L), OriginalLoopInfo(LI), LatchTakenCount(nullptr),
614 OriginalPreheader(nullptr), MainLoopPreheader(nullptr), Range(R),
615 MainLoopStructure(LS) {}
617 // Entry point for the algorithm. Returns true on success.
623 void LoopConstrainer::replacePHIBlock(PHINode *PN, BasicBlock *Block,
624 BasicBlock *ReplaceBy) {
625 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
626 if (PN->getIncomingBlock(i) == Block)
627 PN->setIncomingBlock(i, ReplaceBy);
630 static bool CanBeSMax(ScalarEvolution &SE, const SCEV *S) {
632 APInt::getSignedMaxValue(cast<IntegerType>(S->getType())->getBitWidth());
633 return SE.getSignedRange(S).contains(SMax) &&
634 SE.getUnsignedRange(S).contains(SMax);
637 static bool CanBeSMin(ScalarEvolution &SE, const SCEV *S) {
639 APInt::getSignedMinValue(cast<IntegerType>(S->getType())->getBitWidth());
640 return SE.getSignedRange(S).contains(SMin) &&
641 SE.getUnsignedRange(S).contains(SMin);
644 Optional<LoopStructure>
645 LoopStructure::parseLoopStructure(ScalarEvolution &SE, BranchProbabilityInfo &BPI,
646 Loop &L, const char *&FailureReason) {
647 assert(L.isLoopSimplifyForm() && "should follow from addRequired<>");
649 BasicBlock *Latch = L.getLoopLatch();
650 if (!L.isLoopExiting(Latch)) {
651 FailureReason = "no loop latch";
655 BasicBlock *Header = L.getHeader();
656 BasicBlock *Preheader = L.getLoopPreheader();
658 FailureReason = "no preheader";
662 BranchInst *LatchBr = dyn_cast<BranchInst>(&*Latch->rbegin());
663 if (!LatchBr || LatchBr->isUnconditional()) {
664 FailureReason = "latch terminator not conditional branch";
668 unsigned LatchBrExitIdx = LatchBr->getSuccessor(0) == Header ? 1 : 0;
670 BranchProbability ExitProbability =
671 BPI.getEdgeProbability(LatchBr->getParent(), LatchBrExitIdx);
673 if (ExitProbability > BranchProbability(1, MaxExitProbReciprocal)) {
674 FailureReason = "short running loop, not profitable";
678 ICmpInst *ICI = dyn_cast<ICmpInst>(LatchBr->getCondition());
679 if (!ICI || !isa<IntegerType>(ICI->getOperand(0)->getType())) {
680 FailureReason = "latch terminator branch not conditional on integral icmp";
684 const SCEV *LatchCount = SE.getExitCount(&L, Latch);
685 if (isa<SCEVCouldNotCompute>(LatchCount)) {
686 FailureReason = "could not compute latch count";
690 ICmpInst::Predicate Pred = ICI->getPredicate();
691 Value *LeftValue = ICI->getOperand(0);
692 const SCEV *LeftSCEV = SE.getSCEV(LeftValue);
693 IntegerType *IndVarTy = cast<IntegerType>(LeftValue->getType());
695 Value *RightValue = ICI->getOperand(1);
696 const SCEV *RightSCEV = SE.getSCEV(RightValue);
698 // We canonicalize `ICI` such that `LeftSCEV` is an add recurrence.
699 if (!isa<SCEVAddRecExpr>(LeftSCEV)) {
700 if (isa<SCEVAddRecExpr>(RightSCEV)) {
701 std::swap(LeftSCEV, RightSCEV);
702 std::swap(LeftValue, RightValue);
703 Pred = ICmpInst::getSwappedPredicate(Pred);
705 FailureReason = "no add recurrences in the icmp";
710 auto HasNoSignedWrap = [&](const SCEVAddRecExpr *AR) {
711 if (AR->getNoWrapFlags(SCEV::FlagNSW))
714 IntegerType *Ty = cast<IntegerType>(AR->getType());
715 IntegerType *WideTy =
716 IntegerType::get(Ty->getContext(), Ty->getBitWidth() * 2);
718 const SCEVAddRecExpr *ExtendAfterOp =
719 dyn_cast<SCEVAddRecExpr>(SE.getSignExtendExpr(AR, WideTy));
721 const SCEV *ExtendedStart = SE.getSignExtendExpr(AR->getStart(), WideTy);
722 const SCEV *ExtendedStep =
723 SE.getSignExtendExpr(AR->getStepRecurrence(SE), WideTy);
725 bool NoSignedWrap = ExtendAfterOp->getStart() == ExtendedStart &&
726 ExtendAfterOp->getStepRecurrence(SE) == ExtendedStep;
732 // We may have proved this when computing the sign extension above.
733 return AR->getNoWrapFlags(SCEV::FlagNSW) != SCEV::FlagAnyWrap;
736 auto IsInductionVar = [&](const SCEVAddRecExpr *AR, bool &IsIncreasing) {
740 // Currently we only work with induction variables that have been proved to
741 // not wrap. This restriction can potentially be lifted in the future.
743 if (!HasNoSignedWrap(AR))
746 if (const SCEVConstant *StepExpr =
747 dyn_cast<SCEVConstant>(AR->getStepRecurrence(SE))) {
748 ConstantInt *StepCI = StepExpr->getValue();
749 if (StepCI->isOne() || StepCI->isMinusOne()) {
750 IsIncreasing = StepCI->isOne();
758 // `ICI` is interpreted as taking the backedge if the *next* value of the
759 // induction variable satisfies some constraint.
761 const SCEVAddRecExpr *IndVarNext = cast<SCEVAddRecExpr>(LeftSCEV);
762 bool IsIncreasing = false;
763 if (!IsInductionVar(IndVarNext, IsIncreasing)) {
764 FailureReason = "LHS in icmp not induction variable";
768 ConstantInt *One = ConstantInt::get(IndVarTy, 1);
769 // TODO: generalize the predicates here to also match their unsigned variants.
771 bool FoundExpectedPred =
772 (Pred == ICmpInst::ICMP_SLT && LatchBrExitIdx == 1) ||
773 (Pred == ICmpInst::ICMP_SGT && LatchBrExitIdx == 0);
775 if (!FoundExpectedPred) {
776 FailureReason = "expected icmp slt semantically, found something else";
780 if (LatchBrExitIdx == 0) {
781 if (CanBeSMax(SE, RightSCEV)) {
782 // TODO: this restriction is easily removable -- we just have to
783 // remember that the icmp was an slt and not an sle.
784 FailureReason = "limit may overflow when coercing sle to slt";
788 IRBuilder<> B(&*Preheader->rbegin());
789 RightValue = B.CreateAdd(RightValue, One);
793 bool FoundExpectedPred =
794 (Pred == ICmpInst::ICMP_SGT && LatchBrExitIdx == 1) ||
795 (Pred == ICmpInst::ICMP_SLT && LatchBrExitIdx == 0);
797 if (!FoundExpectedPred) {
798 FailureReason = "expected icmp sgt semantically, found something else";
802 if (LatchBrExitIdx == 0) {
803 if (CanBeSMin(SE, RightSCEV)) {
804 // TODO: this restriction is easily removable -- we just have to
805 // remember that the icmp was an sgt and not an sge.
806 FailureReason = "limit may overflow when coercing sge to sgt";
810 IRBuilder<> B(&*Preheader->rbegin());
811 RightValue = B.CreateSub(RightValue, One);
815 const SCEV *StartNext = IndVarNext->getStart();
816 const SCEV *Addend = SE.getNegativeSCEV(IndVarNext->getStepRecurrence(SE));
817 const SCEV *IndVarStart = SE.getAddExpr(StartNext, Addend);
819 BasicBlock *LatchExit = LatchBr->getSuccessor(LatchBrExitIdx);
821 assert(SE.getLoopDisposition(LatchCount, &L) ==
822 ScalarEvolution::LoopInvariant &&
823 "loop variant exit count doesn't make sense!");
825 assert(!L.contains(LatchExit) && "expected an exit block!");
826 const DataLayout &DL = Preheader->getModule()->getDataLayout();
827 Value *IndVarStartV =
828 SCEVExpander(SE, DL, "irce")
829 .expandCodeFor(IndVarStart, IndVarTy, &*Preheader->rbegin());
830 IndVarStartV->setName("indvar.start");
832 LoopStructure Result;
835 Result.Header = Header;
836 Result.Latch = Latch;
837 Result.LatchBr = LatchBr;
838 Result.LatchExit = LatchExit;
839 Result.LatchBrExitIdx = LatchBrExitIdx;
840 Result.IndVarStart = IndVarStartV;
841 Result.IndVarNext = LeftValue;
842 Result.IndVarIncreasing = IsIncreasing;
843 Result.LoopExitAt = RightValue;
845 FailureReason = nullptr;
850 Optional<LoopConstrainer::SubRanges>
851 LoopConstrainer::calculateSubRanges() const {
852 IntegerType *Ty = cast<IntegerType>(LatchTakenCount->getType());
854 if (Range.getType() != Ty)
857 LoopConstrainer::SubRanges Result;
859 // I think we can be more aggressive here and make this nuw / nsw if the
860 // addition that feeds into the icmp for the latch's terminating branch is nuw
861 // / nsw. In any case, a wrapping 2's complement addition is safe.
862 ConstantInt *One = ConstantInt::get(Ty, 1);
863 const SCEV *Start = SE.getSCEV(MainLoopStructure.IndVarStart);
864 const SCEV *End = SE.getSCEV(MainLoopStructure.LoopExitAt);
866 bool Increasing = MainLoopStructure.IndVarIncreasing;
868 // We compute `Smallest` and `Greatest` such that [Smallest, Greatest) is the
869 // range of values the induction variable takes.
871 const SCEV *Smallest = nullptr, *Greatest = nullptr;
877 // These two computations may sign-overflow. Here is why that is okay:
879 // We know that the induction variable does not sign-overflow on any
880 // iteration except the last one, and it starts at `Start` and ends at
881 // `End`, decrementing by one every time.
883 // * if `Smallest` sign-overflows we know `End` is `INT_SMAX`. Since the
884 // induction variable is decreasing we know that that the smallest value
885 // the loop body is actually executed with is `INT_SMIN` == `Smallest`.
887 // * if `Greatest` sign-overflows, we know it can only be `INT_SMIN`. In
888 // that case, `Clamp` will always return `Smallest` and
889 // [`Result.LowLimit`, `Result.HighLimit`) = [`Smallest`, `Smallest`)
890 // will be an empty range. Returning an empty range is always safe.
893 Smallest = SE.getAddExpr(End, SE.getSCEV(One));
894 Greatest = SE.getAddExpr(Start, SE.getSCEV(One));
897 auto Clamp = [this, Smallest, Greatest](const SCEV *S) {
898 return SE.getSMaxExpr(Smallest, SE.getSMinExpr(Greatest, S));
901 // In some cases we can prove that we don't need a pre or post loop
903 bool ProvablyNoPreloop =
904 SE.isKnownPredicate(ICmpInst::ICMP_SLE, Range.getBegin(), Smallest);
905 if (!ProvablyNoPreloop)
906 Result.LowLimit = Clamp(Range.getBegin());
908 bool ProvablyNoPostLoop =
909 SE.isKnownPredicate(ICmpInst::ICMP_SLE, Greatest, Range.getEnd());
910 if (!ProvablyNoPostLoop)
911 Result.HighLimit = Clamp(Range.getEnd());
916 void LoopConstrainer::cloneLoop(LoopConstrainer::ClonedLoop &Result,
917 const char *Tag) const {
918 for (BasicBlock *BB : OriginalLoop.getBlocks()) {
919 BasicBlock *Clone = CloneBasicBlock(BB, Result.Map, Twine(".") + Tag, &F);
920 Result.Blocks.push_back(Clone);
921 Result.Map[BB] = Clone;
924 auto GetClonedValue = [&Result](Value *V) {
925 assert(V && "null values not in domain!");
926 auto It = Result.Map.find(V);
927 if (It == Result.Map.end())
929 return static_cast<Value *>(It->second);
932 Result.Structure = MainLoopStructure.map(GetClonedValue);
933 Result.Structure.Tag = Tag;
935 for (unsigned i = 0, e = Result.Blocks.size(); i != e; ++i) {
936 BasicBlock *ClonedBB = Result.Blocks[i];
937 BasicBlock *OriginalBB = OriginalLoop.getBlocks()[i];
939 assert(Result.Map[OriginalBB] == ClonedBB && "invariant!");
941 for (Instruction &I : *ClonedBB)
942 RemapInstruction(&I, Result.Map,
943 RF_NoModuleLevelChanges | RF_IgnoreMissingEntries);
945 // Exit blocks will now have one more predecessor and their PHI nodes need
946 // to be edited to reflect that. No phi nodes need to be introduced because
947 // the loop is in LCSSA.
949 for (auto SBBI = succ_begin(OriginalBB), SBBE = succ_end(OriginalBB);
950 SBBI != SBBE; ++SBBI) {
952 if (OriginalLoop.contains(*SBBI))
953 continue; // not an exit block
955 for (Instruction &I : **SBBI) {
956 if (!isa<PHINode>(&I))
959 PHINode *PN = cast<PHINode>(&I);
960 Value *OldIncoming = PN->getIncomingValueForBlock(OriginalBB);
961 PN->addIncoming(GetClonedValue(OldIncoming), ClonedBB);
967 LoopConstrainer::RewrittenRangeInfo LoopConstrainer::changeIterationSpaceEnd(
968 const LoopStructure &LS, BasicBlock *Preheader, Value *ExitSubloopAt,
969 BasicBlock *ContinuationBlock) const {
971 // We start with a loop with a single latch:
973 // +--------------------+
977 // +--------+-----------+
978 // | ----------------\
980 // +--------v----v------+ |
984 // +--------------------+ |
988 // +--------------------+ |
990 // | latch >----------/
992 // +-------v------------+
995 // | +--------------------+
997 // +---> original exit |
999 // +--------------------+
1001 // We change the control flow to look like
1004 // +--------------------+
1006 // | preheader >-------------------------+
1008 // +--------v-----------+ |
1009 // | /-------------+ |
1011 // +--------v--v--------+ | |
1013 // | header | | +--------+ |
1015 // +--------------------+ | | +-----v-----v-----------+
1017 // | | | .pseudo.exit |
1019 // | | +-----------v-----------+
1022 // | | +--------v-------------+
1023 // +--------------------+ | | | |
1024 // | | | | | ContinuationBlock |
1025 // | latch >------+ | | |
1026 // | | | +----------------------+
1027 // +---------v----------+ |
1030 // | +---------------^-----+
1032 // +-----> .exit.selector |
1034 // +----------v----------+
1036 // +--------------------+ |
1038 // | original exit <----+
1040 // +--------------------+
1043 RewrittenRangeInfo RRI;
1045 auto BBInsertLocation = std::next(Function::iterator(LS.Latch));
1046 RRI.ExitSelector = BasicBlock::Create(Ctx, Twine(LS.Tag) + ".exit.selector",
1047 &F, BBInsertLocation);
1048 RRI.PseudoExit = BasicBlock::Create(Ctx, Twine(LS.Tag) + ".pseudo.exit", &F,
1051 BranchInst *PreheaderJump = cast<BranchInst>(&*Preheader->rbegin());
1052 bool Increasing = LS.IndVarIncreasing;
1054 IRBuilder<> B(PreheaderJump);
1056 // EnterLoopCond - is it okay to start executing this `LS'?
1057 Value *EnterLoopCond = Increasing
1058 ? B.CreateICmpSLT(LS.IndVarStart, ExitSubloopAt)
1059 : B.CreateICmpSGT(LS.IndVarStart, ExitSubloopAt);
1061 B.CreateCondBr(EnterLoopCond, LS.Header, RRI.PseudoExit);
1062 PreheaderJump->eraseFromParent();
1064 LS.LatchBr->setSuccessor(LS.LatchBrExitIdx, RRI.ExitSelector);
1065 B.SetInsertPoint(LS.LatchBr);
1066 Value *TakeBackedgeLoopCond =
1067 Increasing ? B.CreateICmpSLT(LS.IndVarNext, ExitSubloopAt)
1068 : B.CreateICmpSGT(LS.IndVarNext, ExitSubloopAt);
1069 Value *CondForBranch = LS.LatchBrExitIdx == 1
1070 ? TakeBackedgeLoopCond
1071 : B.CreateNot(TakeBackedgeLoopCond);
1073 LS.LatchBr->setCondition(CondForBranch);
1075 B.SetInsertPoint(RRI.ExitSelector);
1077 // IterationsLeft - are there any more iterations left, given the original
1078 // upper bound on the induction variable? If not, we branch to the "real"
1080 Value *IterationsLeft = Increasing
1081 ? B.CreateICmpSLT(LS.IndVarNext, LS.LoopExitAt)
1082 : B.CreateICmpSGT(LS.IndVarNext, LS.LoopExitAt);
1083 B.CreateCondBr(IterationsLeft, RRI.PseudoExit, LS.LatchExit);
1085 BranchInst *BranchToContinuation =
1086 BranchInst::Create(ContinuationBlock, RRI.PseudoExit);
1088 // We emit PHI nodes into `RRI.PseudoExit' that compute the "latest" value of
1089 // each of the PHI nodes in the loop header. This feeds into the initial
1090 // value of the same PHI nodes if/when we continue execution.
1091 for (Instruction &I : *LS.Header) {
1092 if (!isa<PHINode>(&I))
1095 PHINode *PN = cast<PHINode>(&I);
1097 PHINode *NewPHI = PHINode::Create(PN->getType(), 2, PN->getName() + ".copy",
1098 BranchToContinuation);
1100 NewPHI->addIncoming(PN->getIncomingValueForBlock(Preheader), Preheader);
1101 NewPHI->addIncoming(PN->getIncomingValueForBlock(LS.Latch),
1103 RRI.PHIValuesAtPseudoExit.push_back(NewPHI);
1106 RRI.IndVarEnd = PHINode::Create(LS.IndVarNext->getType(), 2, "indvar.end",
1107 BranchToContinuation);
1108 RRI.IndVarEnd->addIncoming(LS.IndVarStart, Preheader);
1109 RRI.IndVarEnd->addIncoming(LS.IndVarNext, RRI.ExitSelector);
1111 // The latch exit now has a branch from `RRI.ExitSelector' instead of
1112 // `LS.Latch'. The PHI nodes need to be updated to reflect that.
1113 for (Instruction &I : *LS.LatchExit) {
1114 if (PHINode *PN = dyn_cast<PHINode>(&I))
1115 replacePHIBlock(PN, LS.Latch, RRI.ExitSelector);
1123 void LoopConstrainer::rewriteIncomingValuesForPHIs(
1124 LoopStructure &LS, BasicBlock *ContinuationBlock,
1125 const LoopConstrainer::RewrittenRangeInfo &RRI) const {
1127 unsigned PHIIndex = 0;
1128 for (Instruction &I : *LS.Header) {
1129 if (!isa<PHINode>(&I))
1132 PHINode *PN = cast<PHINode>(&I);
1134 for (unsigned i = 0, e = PN->getNumIncomingValues(); i < e; ++i)
1135 if (PN->getIncomingBlock(i) == ContinuationBlock)
1136 PN->setIncomingValue(i, RRI.PHIValuesAtPseudoExit[PHIIndex++]);
1139 LS.IndVarStart = RRI.IndVarEnd;
1142 BasicBlock *LoopConstrainer::createPreheader(const LoopStructure &LS,
1143 BasicBlock *OldPreheader,
1144 const char *Tag) const {
1146 BasicBlock *Preheader = BasicBlock::Create(Ctx, Tag, &F, LS.Header);
1147 BranchInst::Create(LS.Header, Preheader);
1149 for (Instruction &I : *LS.Header) {
1150 if (!isa<PHINode>(&I))
1153 PHINode *PN = cast<PHINode>(&I);
1154 for (unsigned i = 0, e = PN->getNumIncomingValues(); i < e; ++i)
1155 replacePHIBlock(PN, OldPreheader, Preheader);
1161 void LoopConstrainer::addToParentLoopIfNeeded(ArrayRef<BasicBlock *> BBs) {
1162 Loop *ParentLoop = OriginalLoop.getParentLoop();
1166 for (BasicBlock *BB : BBs)
1167 ParentLoop->addBasicBlockToLoop(BB, OriginalLoopInfo);
1170 bool LoopConstrainer::run() {
1171 BasicBlock *Preheader = nullptr;
1172 LatchTakenCount = SE.getExitCount(&OriginalLoop, MainLoopStructure.Latch);
1173 Preheader = OriginalLoop.getLoopPreheader();
1174 assert(!isa<SCEVCouldNotCompute>(LatchTakenCount) && Preheader != nullptr &&
1177 OriginalPreheader = Preheader;
1178 MainLoopPreheader = Preheader;
1180 Optional<SubRanges> MaybeSR = calculateSubRanges();
1181 if (!MaybeSR.hasValue()) {
1182 DEBUG(dbgs() << "irce: could not compute subranges\n");
1186 SubRanges SR = MaybeSR.getValue();
1187 bool Increasing = MainLoopStructure.IndVarIncreasing;
1189 cast<IntegerType>(MainLoopStructure.IndVarNext->getType());
1191 SCEVExpander Expander(SE, F.getParent()->getDataLayout(), "irce");
1192 Instruction *InsertPt = OriginalPreheader->getTerminator();
1194 // It would have been better to make `PreLoop' and `PostLoop'
1195 // `Optional<ClonedLoop>'s, but `ValueToValueMapTy' does not have a copy
1197 ClonedLoop PreLoop, PostLoop;
1199 Increasing ? SR.LowLimit.hasValue() : SR.HighLimit.hasValue();
1200 bool NeedsPostLoop =
1201 Increasing ? SR.HighLimit.hasValue() : SR.LowLimit.hasValue();
1203 Value *ExitPreLoopAt = nullptr;
1204 Value *ExitMainLoopAt = nullptr;
1205 const SCEVConstant *MinusOneS =
1206 cast<SCEVConstant>(SE.getConstant(IVTy, -1, true /* isSigned */));
1209 const SCEV *ExitPreLoopAtSCEV = nullptr;
1212 ExitPreLoopAtSCEV = *SR.LowLimit;
1214 if (CanBeSMin(SE, *SR.HighLimit)) {
1215 DEBUG(dbgs() << "irce: could not prove no-overflow when computing "
1216 << "preloop exit limit. HighLimit = " << *(*SR.HighLimit)
1220 ExitPreLoopAtSCEV = SE.getAddExpr(*SR.HighLimit, MinusOneS);
1223 ExitPreLoopAt = Expander.expandCodeFor(ExitPreLoopAtSCEV, IVTy, InsertPt);
1224 ExitPreLoopAt->setName("exit.preloop.at");
1227 if (NeedsPostLoop) {
1228 const SCEV *ExitMainLoopAtSCEV = nullptr;
1231 ExitMainLoopAtSCEV = *SR.HighLimit;
1233 if (CanBeSMin(SE, *SR.LowLimit)) {
1234 DEBUG(dbgs() << "irce: could not prove no-overflow when computing "
1235 << "mainloop exit limit. LowLimit = " << *(*SR.LowLimit)
1239 ExitMainLoopAtSCEV = SE.getAddExpr(*SR.LowLimit, MinusOneS);
1242 ExitMainLoopAt = Expander.expandCodeFor(ExitMainLoopAtSCEV, IVTy, InsertPt);
1243 ExitMainLoopAt->setName("exit.mainloop.at");
1246 // We clone these ahead of time so that we don't have to deal with changing
1247 // and temporarily invalid IR as we transform the loops.
1249 cloneLoop(PreLoop, "preloop");
1251 cloneLoop(PostLoop, "postloop");
1253 RewrittenRangeInfo PreLoopRRI;
1256 Preheader->getTerminator()->replaceUsesOfWith(MainLoopStructure.Header,
1257 PreLoop.Structure.Header);
1260 createPreheader(MainLoopStructure, Preheader, "mainloop");
1261 PreLoopRRI = changeIterationSpaceEnd(PreLoop.Structure, Preheader,
1262 ExitPreLoopAt, MainLoopPreheader);
1263 rewriteIncomingValuesForPHIs(MainLoopStructure, MainLoopPreheader,
1267 BasicBlock *PostLoopPreheader = nullptr;
1268 RewrittenRangeInfo PostLoopRRI;
1270 if (NeedsPostLoop) {
1272 createPreheader(PostLoop.Structure, Preheader, "postloop");
1273 PostLoopRRI = changeIterationSpaceEnd(MainLoopStructure, MainLoopPreheader,
1274 ExitMainLoopAt, PostLoopPreheader);
1275 rewriteIncomingValuesForPHIs(PostLoop.Structure, PostLoopPreheader,
1279 BasicBlock *NewMainLoopPreheader =
1280 MainLoopPreheader != Preheader ? MainLoopPreheader : nullptr;
1281 BasicBlock *NewBlocks[] = {PostLoopPreheader, PreLoopRRI.PseudoExit,
1282 PreLoopRRI.ExitSelector, PostLoopRRI.PseudoExit,
1283 PostLoopRRI.ExitSelector, NewMainLoopPreheader};
1285 // Some of the above may be nullptr, filter them out before passing to
1286 // addToParentLoopIfNeeded.
1288 std::remove(std::begin(NewBlocks), std::end(NewBlocks), nullptr);
1290 addToParentLoopIfNeeded(makeArrayRef(std::begin(NewBlocks), NewBlocksEnd));
1291 addToParentLoopIfNeeded(PreLoop.Blocks);
1292 addToParentLoopIfNeeded(PostLoop.Blocks);
1297 /// Computes and returns a range of values for the induction variable (IndVar)
1298 /// in which the range check can be safely elided. If it cannot compute such a
1299 /// range, returns None.
1300 Optional<InductiveRangeCheck::Range>
1301 InductiveRangeCheck::computeSafeIterationSpace(ScalarEvolution &SE,
1302 const SCEVAddRecExpr *IndVar,
1303 IRBuilder<> &) const {
1304 // IndVar is of the form "A + B * I" (where "I" is the canonical induction
1305 // variable, that may or may not exist as a real llvm::Value in the loop) and
1306 // this inductive range check is a range check on the "C + D * I" ("C" is
1307 // getOffset() and "D" is getScale()). We rewrite the value being range
1308 // checked to "M + N * IndVar" where "N" = "D * B^(-1)" and "M" = "C - NA".
1309 // Currently we support this only for "B" = "D" = { 1 or -1 }, but the code
1310 // can be generalized as needed.
1312 // The actual inequalities we solve are of the form
1314 // 0 <= M + 1 * IndVar < L given L >= 0 (i.e. N == 1)
1316 // The inequality is satisfied by -M <= IndVar < (L - M) [^1]. All additions
1317 // and subtractions are twos-complement wrapping and comparisons are signed.
1321 // If there exists IndVar such that -M <= IndVar < (L - M) then it follows
1322 // that -M <= (-M + L) [== Eq. 1]. Since L >= 0, if (-M + L) sign-overflows
1323 // then (-M + L) < (-M). Hence by [Eq. 1], (-M + L) could not have
1326 // This means IndVar = t + (-M) for t in [0, L). Hence (IndVar + M) = t.
1327 // Hence 0 <= (IndVar + M) < L
1329 // [^1]: Note that the solution does _not_ apply if L < 0; consider values M =
1330 // 127, IndVar = 126 and L = -2 in an i8 world.
1332 if (!IndVar->isAffine())
1335 const SCEV *A = IndVar->getStart();
1336 const SCEVConstant *B = dyn_cast<SCEVConstant>(IndVar->getStepRecurrence(SE));
1340 const SCEV *C = getOffset();
1341 const SCEVConstant *D = dyn_cast<SCEVConstant>(getScale());
1345 ConstantInt *ConstD = D->getValue();
1346 if (!(ConstD->isMinusOne() || ConstD->isOne()))
1349 const SCEV *M = SE.getMinusSCEV(C, A);
1351 const SCEV *Begin = SE.getNegativeSCEV(M);
1352 const SCEV *UpperLimit = nullptr;
1354 // We strengthen "0 <= I" to "0 <= I < INT_SMAX" and "I < L" to "0 <= I < L".
1355 // We can potentially do much better here.
1356 if (Value *V = getLength()) {
1357 UpperLimit = SE.getSCEV(V);
1359 assert(Kind == InductiveRangeCheck::RANGE_CHECK_LOWER && "invariant!");
1360 unsigned BitWidth = cast<IntegerType>(IndVar->getType())->getBitWidth();
1361 UpperLimit = SE.getConstant(APInt::getSignedMaxValue(BitWidth));
1364 const SCEV *End = SE.getMinusSCEV(UpperLimit, M);
1365 return InductiveRangeCheck::Range(Begin, End);
1368 static Optional<InductiveRangeCheck::Range>
1369 IntersectRange(ScalarEvolution &SE,
1370 const Optional<InductiveRangeCheck::Range> &R1,
1371 const InductiveRangeCheck::Range &R2, IRBuilder<> &B) {
1374 auto &R1Value = R1.getValue();
1376 // TODO: we could widen the smaller range and have this work; but for now we
1377 // bail out to keep things simple.
1378 if (R1Value.getType() != R2.getType())
1381 const SCEV *NewBegin = SE.getSMaxExpr(R1Value.getBegin(), R2.getBegin());
1382 const SCEV *NewEnd = SE.getSMinExpr(R1Value.getEnd(), R2.getEnd());
1384 return InductiveRangeCheck::Range(NewBegin, NewEnd);
1387 bool InductiveRangeCheckElimination::runOnLoop(Loop *L, LPPassManager &LPM) {
1388 if (L->getBlocks().size() >= LoopSizeCutoff) {
1389 DEBUG(dbgs() << "irce: giving up constraining loop, too large\n";);
1393 BasicBlock *Preheader = L->getLoopPreheader();
1395 DEBUG(dbgs() << "irce: loop has no preheader, leaving\n");
1399 LLVMContext &Context = Preheader->getContext();
1400 InductiveRangeCheck::AllocatorTy IRCAlloc;
1401 SmallVector<InductiveRangeCheck *, 16> RangeChecks;
1402 ScalarEvolution &SE = getAnalysis<ScalarEvolution>();
1403 BranchProbabilityInfo &BPI =
1404 getAnalysis<BranchProbabilityInfoWrapperPass>().getBPI();
1406 for (auto BBI : L->getBlocks())
1407 if (BranchInst *TBI = dyn_cast<BranchInst>(BBI->getTerminator()))
1408 if (InductiveRangeCheck *IRC =
1409 InductiveRangeCheck::create(IRCAlloc, TBI, L, SE, BPI))
1410 RangeChecks.push_back(IRC);
1412 if (RangeChecks.empty())
1415 auto PrintRecognizedRangeChecks = [&](raw_ostream &OS) {
1416 OS << "irce: looking at loop "; L->print(OS);
1417 OS << "irce: loop has " << RangeChecks.size()
1418 << " inductive range checks: \n";
1419 for (InductiveRangeCheck *IRC : RangeChecks)
1423 DEBUG(PrintRecognizedRangeChecks(dbgs()));
1425 if (PrintRangeChecks)
1426 PrintRecognizedRangeChecks(errs());
1428 const char *FailureReason = nullptr;
1429 Optional<LoopStructure> MaybeLoopStructure =
1430 LoopStructure::parseLoopStructure(SE, BPI, *L, FailureReason);
1431 if (!MaybeLoopStructure.hasValue()) {
1432 DEBUG(dbgs() << "irce: could not parse loop structure: " << FailureReason
1436 LoopStructure LS = MaybeLoopStructure.getValue();
1437 bool Increasing = LS.IndVarIncreasing;
1438 const SCEV *MinusOne =
1439 SE.getConstant(LS.IndVarNext->getType(), Increasing ? -1 : 1, true);
1440 const SCEVAddRecExpr *IndVar =
1441 cast<SCEVAddRecExpr>(SE.getAddExpr(SE.getSCEV(LS.IndVarNext), MinusOne));
1443 Optional<InductiveRangeCheck::Range> SafeIterRange;
1444 Instruction *ExprInsertPt = Preheader->getTerminator();
1446 SmallVector<InductiveRangeCheck *, 4> RangeChecksToEliminate;
1448 IRBuilder<> B(ExprInsertPt);
1449 for (InductiveRangeCheck *IRC : RangeChecks) {
1450 auto Result = IRC->computeSafeIterationSpace(SE, IndVar, B);
1451 if (Result.hasValue()) {
1452 auto MaybeSafeIterRange =
1453 IntersectRange(SE, SafeIterRange, Result.getValue(), B);
1454 if (MaybeSafeIterRange.hasValue()) {
1455 RangeChecksToEliminate.push_back(IRC);
1456 SafeIterRange = MaybeSafeIterRange.getValue();
1461 if (!SafeIterRange.hasValue())
1464 LoopConstrainer LC(*L, getAnalysis<LoopInfoWrapperPass>().getLoopInfo(), LS,
1465 SE, SafeIterRange.getValue());
1466 bool Changed = LC.run();
1469 auto PrintConstrainedLoopInfo = [L]() {
1470 dbgs() << "irce: in function ";
1471 dbgs() << L->getHeader()->getParent()->getName() << ": ";
1472 dbgs() << "constrained ";
1476 DEBUG(PrintConstrainedLoopInfo());
1478 if (PrintChangedLoops)
1479 PrintConstrainedLoopInfo();
1481 // Optimize away the now-redundant range checks.
1483 for (InductiveRangeCheck *IRC : RangeChecksToEliminate) {
1484 ConstantInt *FoldedRangeCheck = IRC->getPassingDirection()
1485 ? ConstantInt::getTrue(Context)
1486 : ConstantInt::getFalse(Context);
1487 IRC->getBranch()->setCondition(FoldedRangeCheck);
1494 Pass *llvm::createInductiveRangeCheckEliminationPass() {
1495 return new InductiveRangeCheckElimination;