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/LoopInfo.h"
47 #include "llvm/Analysis/LoopPass.h"
48 #include "llvm/Analysis/ScalarEvolution.h"
49 #include "llvm/Analysis/ScalarEvolutionExpander.h"
50 #include "llvm/Analysis/ScalarEvolutionExpressions.h"
51 #include "llvm/IR/Dominators.h"
52 #include "llvm/IR/Function.h"
53 #include "llvm/IR/IRBuilder.h"
54 #include "llvm/IR/Instructions.h"
55 #include "llvm/IR/PatternMatch.h"
56 #include "llvm/Pass.h"
57 #include "llvm/Support/Debug.h"
58 #include "llvm/Support/raw_ostream.h"
59 #include "llvm/Transforms/Scalar.h"
60 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
61 #include "llvm/Transforms/Utils/Cloning.h"
62 #include "llvm/Transforms/Utils/LoopSimplify.h"
63 #include "llvm/Transforms/Utils/LoopUtils.h"
67 static cl::opt<unsigned> LoopSizeCutoff("irce-loop-size-cutoff", cl::Hidden,
70 static cl::opt<bool> PrintChangedLoops("irce-print-changed-loops", cl::Hidden,
73 static cl::opt<bool> PrintRangeChecks("irce-print-range-checks", cl::Hidden,
76 static cl::opt<int> MaxExitProbReciprocal("irce-max-exit-prob-reciprocal",
77 cl::Hidden, cl::init(10));
79 static cl::opt<bool> SkipProfitabilityChecks("irce-skip-profitability-checks",
80 cl::Hidden, cl::init(false));
82 static const char *ClonedLoopTag = "irce.loop.clone";
84 #define DEBUG_TYPE "irce"
88 /// An inductive range check is conditional branch in a loop with
90 /// 1. a very cold successor (i.e. the branch jumps to that successor very
95 /// 2. a condition that is provably true for some contiguous range of values
96 /// taken by the containing loop's induction variable.
98 class InductiveRangeCheck {
99 // Classifies a range check
100 enum RangeCheckKind : unsigned {
101 // Range check of the form "0 <= I".
102 RANGE_CHECK_LOWER = 1,
104 // Range check of the form "I < L" where L is known positive.
105 RANGE_CHECK_UPPER = 2,
107 // The logical and of the RANGE_CHECK_LOWER and RANGE_CHECK_UPPER
109 RANGE_CHECK_BOTH = RANGE_CHECK_LOWER | RANGE_CHECK_UPPER,
111 // Unrecognized range check condition.
112 RANGE_CHECK_UNKNOWN = (unsigned)-1
115 static StringRef rangeCheckKindToStr(RangeCheckKind);
117 const SCEV *Offset = nullptr;
118 const SCEV *Scale = nullptr;
119 Value *Length = nullptr;
120 Use *CheckUse = nullptr;
121 RangeCheckKind Kind = RANGE_CHECK_UNKNOWN;
123 static RangeCheckKind parseRangeCheckICmp(Loop *L, ICmpInst *ICI,
124 ScalarEvolution &SE, Value *&Index,
128 extractRangeChecksFromCond(Loop *L, ScalarEvolution &SE, Use &ConditionUse,
129 SmallVectorImpl<InductiveRangeCheck> &Checks,
130 SmallPtrSetImpl<Value *> &Visited);
133 const SCEV *getOffset() const { return Offset; }
134 const SCEV *getScale() const { return Scale; }
135 Value *getLength() const { return Length; }
137 void print(raw_ostream &OS) const {
138 OS << "InductiveRangeCheck:\n";
139 OS << " Kind: " << rangeCheckKindToStr(Kind) << "\n";
149 OS << "\n CheckUse: ";
150 getCheckUse()->getUser()->print(OS);
151 OS << " Operand: " << getCheckUse()->getOperandNo() << "\n";
159 Use *getCheckUse() const { return CheckUse; }
161 /// Represents an signed integer range [Range.getBegin(), Range.getEnd()). If
162 /// R.getEnd() sle R.getBegin(), then R denotes the empty range.
169 Range(const SCEV *Begin, const SCEV *End) : Begin(Begin), End(End) {
170 assert(Begin->getType() == End->getType() && "ill-typed range!");
173 Type *getType() const { return Begin->getType(); }
174 const SCEV *getBegin() const { return Begin; }
175 const SCEV *getEnd() const { return End; }
178 /// This is the value the condition of the branch needs to evaluate to for the
179 /// branch to take the hot successor (see (1) above).
180 bool getPassingDirection() { return true; }
182 /// Computes a range for the induction variable (IndVar) in which the range
183 /// check is redundant and can be constant-folded away. The induction
184 /// variable is not required to be the canonical {0,+,1} induction variable.
185 Optional<Range> computeSafeIterationSpace(ScalarEvolution &SE,
186 const SCEVAddRecExpr *IndVar) const;
188 /// Parse out a set of inductive range checks from \p BI and append them to \p
191 /// NB! There may be conditions feeding into \p BI that aren't inductive range
192 /// checks, and hence don't end up in \p Checks.
194 extractRangeChecksFromBranch(BranchInst *BI, Loop *L, ScalarEvolution &SE,
195 BranchProbabilityInfo &BPI,
196 SmallVectorImpl<InductiveRangeCheck> &Checks);
199 class InductiveRangeCheckElimination : public LoopPass {
202 InductiveRangeCheckElimination() : LoopPass(ID) {
203 initializeInductiveRangeCheckEliminationPass(
204 *PassRegistry::getPassRegistry());
207 void getAnalysisUsage(AnalysisUsage &AU) const override {
208 AU.addRequired<BranchProbabilityInfoWrapperPass>();
209 getLoopAnalysisUsage(AU);
212 bool runOnLoop(Loop *L, LPPassManager &LPM) override;
215 char InductiveRangeCheckElimination::ID = 0;
218 INITIALIZE_PASS_BEGIN(InductiveRangeCheckElimination, "irce",
219 "Inductive range check elimination", false, false)
220 INITIALIZE_PASS_DEPENDENCY(BranchProbabilityInfoWrapperPass)
221 INITIALIZE_PASS_DEPENDENCY(LoopPass)
222 INITIALIZE_PASS_END(InductiveRangeCheckElimination, "irce",
223 "Inductive range check elimination", false, false)
225 StringRef InductiveRangeCheck::rangeCheckKindToStr(
226 InductiveRangeCheck::RangeCheckKind RCK) {
228 case InductiveRangeCheck::RANGE_CHECK_UNKNOWN:
229 return "RANGE_CHECK_UNKNOWN";
231 case InductiveRangeCheck::RANGE_CHECK_UPPER:
232 return "RANGE_CHECK_UPPER";
234 case InductiveRangeCheck::RANGE_CHECK_LOWER:
235 return "RANGE_CHECK_LOWER";
237 case InductiveRangeCheck::RANGE_CHECK_BOTH:
238 return "RANGE_CHECK_BOTH";
241 llvm_unreachable("unknown range check type!");
244 /// Parse a single ICmp instruction, `ICI`, into a range check. If `ICI` cannot
245 /// be interpreted as a range check, return `RANGE_CHECK_UNKNOWN` and set
246 /// `Index` and `Length` to `nullptr`. Otherwise set `Index` to the value being
247 /// range checked, and set `Length` to the upper limit `Index` is being range
248 /// checked with if (and only if) the range check type is stronger or equal to
249 /// RANGE_CHECK_UPPER.
251 InductiveRangeCheck::RangeCheckKind
252 InductiveRangeCheck::parseRangeCheckICmp(Loop *L, ICmpInst *ICI,
253 ScalarEvolution &SE, Value *&Index,
256 auto IsNonNegativeAndNotLoopVarying = [&SE, L](Value *V) {
257 const SCEV *S = SE.getSCEV(V);
258 if (isa<SCEVCouldNotCompute>(S))
261 return SE.getLoopDisposition(S, L) == ScalarEvolution::LoopInvariant &&
262 SE.isKnownNonNegative(S);
265 using namespace llvm::PatternMatch;
267 ICmpInst::Predicate Pred = ICI->getPredicate();
268 Value *LHS = ICI->getOperand(0);
269 Value *RHS = ICI->getOperand(1);
273 return RANGE_CHECK_UNKNOWN;
275 case ICmpInst::ICMP_SLE:
278 case ICmpInst::ICMP_SGE:
279 if (match(RHS, m_ConstantInt<0>())) {
281 return RANGE_CHECK_LOWER;
283 return RANGE_CHECK_UNKNOWN;
285 case ICmpInst::ICMP_SLT:
288 case ICmpInst::ICMP_SGT:
289 if (match(RHS, m_ConstantInt<-1>())) {
291 return RANGE_CHECK_LOWER;
294 if (IsNonNegativeAndNotLoopVarying(LHS)) {
297 return RANGE_CHECK_UPPER;
299 return RANGE_CHECK_UNKNOWN;
301 case ICmpInst::ICMP_ULT:
304 case ICmpInst::ICMP_UGT:
305 if (IsNonNegativeAndNotLoopVarying(LHS)) {
308 return RANGE_CHECK_BOTH;
310 return RANGE_CHECK_UNKNOWN;
313 llvm_unreachable("default clause returns!");
316 void InductiveRangeCheck::extractRangeChecksFromCond(
317 Loop *L, ScalarEvolution &SE, Use &ConditionUse,
318 SmallVectorImpl<InductiveRangeCheck> &Checks,
319 SmallPtrSetImpl<Value *> &Visited) {
320 using namespace llvm::PatternMatch;
322 Value *Condition = ConditionUse.get();
323 if (!Visited.insert(Condition).second)
326 if (match(Condition, m_And(m_Value(), m_Value()))) {
327 SmallVector<InductiveRangeCheck, 8> SubChecks;
328 extractRangeChecksFromCond(L, SE, cast<User>(Condition)->getOperandUse(0),
330 extractRangeChecksFromCond(L, SE, cast<User>(Condition)->getOperandUse(1),
333 if (SubChecks.size() == 2) {
334 // Handle a special case where we know how to merge two checks separately
335 // checking the upper and lower bounds into a full range check.
336 const auto &RChkA = SubChecks[0];
337 const auto &RChkB = SubChecks[1];
338 if ((RChkA.Length == RChkB.Length || !RChkA.Length || !RChkB.Length) &&
339 RChkA.Offset == RChkB.Offset && RChkA.Scale == RChkB.Scale) {
341 // If RChkA.Kind == RChkB.Kind then we just found two identical checks.
342 // But if one of them is a RANGE_CHECK_LOWER and the other is a
343 // RANGE_CHECK_UPPER (only possibility if they're different) then
344 // together they form a RANGE_CHECK_BOTH.
346 (InductiveRangeCheck::RangeCheckKind)(RChkA.Kind | RChkB.Kind);
347 SubChecks[0].Length = RChkA.Length ? RChkA.Length : RChkB.Length;
348 SubChecks[0].CheckUse = &ConditionUse;
350 // We updated one of the checks in place, now erase the other.
351 SubChecks.pop_back();
355 Checks.insert(Checks.end(), SubChecks.begin(), SubChecks.end());
359 ICmpInst *ICI = dyn_cast<ICmpInst>(Condition);
363 Value *Length = nullptr, *Index;
364 auto RCKind = parseRangeCheckICmp(L, ICI, SE, Index, Length);
365 if (RCKind == InductiveRangeCheck::RANGE_CHECK_UNKNOWN)
368 const auto *IndexAddRec = dyn_cast<SCEVAddRecExpr>(SE.getSCEV(Index));
370 IndexAddRec && (IndexAddRec->getLoop() == L) && IndexAddRec->isAffine();
375 InductiveRangeCheck IRC;
377 IRC.Offset = IndexAddRec->getStart();
378 IRC.Scale = IndexAddRec->getStepRecurrence(SE);
379 IRC.CheckUse = &ConditionUse;
381 Checks.push_back(IRC);
384 void InductiveRangeCheck::extractRangeChecksFromBranch(
385 BranchInst *BI, Loop *L, ScalarEvolution &SE, BranchProbabilityInfo &BPI,
386 SmallVectorImpl<InductiveRangeCheck> &Checks) {
388 if (BI->isUnconditional() || BI->getParent() == L->getLoopLatch())
391 BranchProbability LikelyTaken(15, 16);
393 if (!SkipProfitabilityChecks &&
394 BPI.getEdgeProbability(BI->getParent(), (unsigned)0) < LikelyTaken)
397 SmallPtrSet<Value *, 8> Visited;
398 InductiveRangeCheck::extractRangeChecksFromCond(L, SE, BI->getOperandUse(0),
402 // Add metadata to the loop L to disable loop optimizations. Callers need to
403 // confirm that optimizing loop L is not beneficial.
404 static void DisableAllLoopOptsOnLoop(Loop &L) {
405 // We do not care about any existing loopID related metadata for L, since we
406 // are setting all loop metadata to false.
407 LLVMContext &Context = L.getHeader()->getContext();
408 // Reserve first location for self reference to the LoopID metadata node.
409 MDNode *Dummy = MDNode::get(Context, {});
410 MDNode *DisableUnroll = MDNode::get(
411 Context, {MDString::get(Context, "llvm.loop.unroll.disable")});
413 ConstantAsMetadata::get(ConstantInt::get(Type::getInt1Ty(Context), 0));
414 MDNode *DisableVectorize = MDNode::get(
416 {MDString::get(Context, "llvm.loop.vectorize.enable"), FalseVal});
417 MDNode *DisableLICMVersioning = MDNode::get(
418 Context, {MDString::get(Context, "llvm.loop.licm_versioning.disable")});
419 MDNode *DisableDistribution= MDNode::get(
421 {MDString::get(Context, "llvm.loop.distribute.enable"), FalseVal});
423 MDNode::get(Context, {Dummy, DisableUnroll, DisableVectorize,
424 DisableLICMVersioning, DisableDistribution});
425 // Set operand 0 to refer to the loop id itself.
426 NewLoopID->replaceOperandWith(0, NewLoopID);
427 L.setLoopID(NewLoopID);
432 // Keeps track of the structure of a loop. This is similar to llvm::Loop,
433 // except that it is more lightweight and can track the state of a loop through
434 // changing and potentially invalid IR. This structure also formalizes the
435 // kinds of loops we can deal with -- ones that have a single latch that is also
436 // an exiting block *and* have a canonical induction variable.
437 struct LoopStructure {
443 // `Latch's terminator instruction is `LatchBr', and it's `LatchBrExitIdx'th
444 // successor is `LatchExit', the exit block of the loop.
446 BasicBlock *LatchExit;
447 unsigned LatchBrExitIdx;
449 // The loop represented by this instance of LoopStructure is semantically
452 // intN_ty inc = IndVarIncreasing ? 1 : -1;
453 // pred_ty predicate = IndVarIncreasing ? ICMP_SLT : ICMP_SGT;
455 // for (intN_ty iv = IndVarStart; predicate(iv, LoopExitAt); iv = IndVarBase)
462 bool IndVarIncreasing;
463 bool IsSignedPredicate;
466 : Tag(""), Header(nullptr), Latch(nullptr), LatchBr(nullptr),
467 LatchExit(nullptr), LatchBrExitIdx(-1), IndVarBase(nullptr),
468 IndVarStart(nullptr), IndVarStep(nullptr), LoopExitAt(nullptr),
469 IndVarIncreasing(false), IsSignedPredicate(true) {}
471 template <typename M> LoopStructure map(M Map) const {
472 LoopStructure Result;
474 Result.Header = cast<BasicBlock>(Map(Header));
475 Result.Latch = cast<BasicBlock>(Map(Latch));
476 Result.LatchBr = cast<BranchInst>(Map(LatchBr));
477 Result.LatchExit = cast<BasicBlock>(Map(LatchExit));
478 Result.LatchBrExitIdx = LatchBrExitIdx;
479 Result.IndVarBase = Map(IndVarBase);
480 Result.IndVarStart = Map(IndVarStart);
481 Result.IndVarStep = Map(IndVarStep);
482 Result.LoopExitAt = Map(LoopExitAt);
483 Result.IndVarIncreasing = IndVarIncreasing;
484 Result.IsSignedPredicate = IsSignedPredicate;
488 static Optional<LoopStructure> parseLoopStructure(ScalarEvolution &,
489 BranchProbabilityInfo &BPI,
494 /// This class is used to constrain loops to run within a given iteration space.
495 /// The algorithm this class implements is given a Loop and a range [Begin,
496 /// End). The algorithm then tries to break out a "main loop" out of the loop
497 /// it is given in a way that the "main loop" runs with the induction variable
498 /// in a subset of [Begin, End). The algorithm emits appropriate pre and post
499 /// loops to run any remaining iterations. The pre loop runs any iterations in
500 /// which the induction variable is < Begin, and the post loop runs any
501 /// iterations in which the induction variable is >= End.
503 class LoopConstrainer {
504 // The representation of a clone of the original loop we started out with.
507 std::vector<BasicBlock *> Blocks;
509 // `Map` maps values in the clonee into values in the cloned version
510 ValueToValueMapTy Map;
512 // An instance of `LoopStructure` for the cloned loop
513 LoopStructure Structure;
516 // Result of rewriting the range of a loop. See changeIterationSpaceEnd for
517 // more details on what these fields mean.
518 struct RewrittenRangeInfo {
519 BasicBlock *PseudoExit;
520 BasicBlock *ExitSelector;
521 std::vector<PHINode *> PHIValuesAtPseudoExit;
525 : PseudoExit(nullptr), ExitSelector(nullptr), IndVarEnd(nullptr) {}
528 // Calculated subranges we restrict the iteration space of the main loop to.
529 // See the implementation of `calculateSubRanges' for more details on how
530 // these fields are computed. `LowLimit` is None if there is no restriction
531 // on low end of the restricted iteration space of the main loop. `HighLimit`
532 // is None if there is no restriction on high end of the restricted iteration
533 // space of the main loop.
536 Optional<const SCEV *> LowLimit;
537 Optional<const SCEV *> HighLimit;
540 // A utility function that does a `replaceUsesOfWith' on the incoming block
541 // set of a `PHINode' -- replaces instances of `Block' in the `PHINode's
542 // incoming block list with `ReplaceBy'.
543 static void replacePHIBlock(PHINode *PN, BasicBlock *Block,
544 BasicBlock *ReplaceBy);
546 // Compute a safe set of limits for the main loop to run in -- effectively the
547 // intersection of `Range' and the iteration space of the original loop.
548 // Return None if unable to compute the set of subranges.
550 Optional<SubRanges> calculateSubRanges(bool IsSignedPredicate) const;
552 // Clone `OriginalLoop' and return the result in CLResult. The IR after
553 // running `cloneLoop' is well formed except for the PHI nodes in CLResult --
554 // the PHI nodes say that there is an incoming edge from `OriginalPreheader`
555 // but there is no such edge.
557 void cloneLoop(ClonedLoop &CLResult, const char *Tag) const;
559 // Create the appropriate loop structure needed to describe a cloned copy of
560 // `Original`. The clone is described by `VM`.
561 Loop *createClonedLoopStructure(Loop *Original, Loop *Parent,
562 ValueToValueMapTy &VM);
564 // Rewrite the iteration space of the loop denoted by (LS, Preheader). The
565 // iteration space of the rewritten loop ends at ExitLoopAt. The start of the
566 // iteration space is not changed. `ExitLoopAt' is assumed to be slt
567 // `OriginalHeaderCount'.
569 // If there are iterations left to execute, control is made to jump to
570 // `ContinuationBlock', otherwise they take the normal loop exit. The
571 // returned `RewrittenRangeInfo' object is populated as follows:
573 // .PseudoExit is a basic block that unconditionally branches to
574 // `ContinuationBlock'.
576 // .ExitSelector is a basic block that decides, on exit from the loop,
577 // whether to branch to the "true" exit or to `PseudoExit'.
579 // .PHIValuesAtPseudoExit are PHINodes in `PseudoExit' that compute the value
580 // for each PHINode in the loop header on taking the pseudo exit.
582 // After changeIterationSpaceEnd, `Preheader' is no longer a legitimate
583 // preheader because it is made to branch to the loop header only
587 changeIterationSpaceEnd(const LoopStructure &LS, BasicBlock *Preheader,
589 BasicBlock *ContinuationBlock) const;
591 // The loop denoted by `LS' has `OldPreheader' as its preheader. This
592 // function creates a new preheader for `LS' and returns it.
594 BasicBlock *createPreheader(const LoopStructure &LS, BasicBlock *OldPreheader,
595 const char *Tag) const;
597 // `ContinuationBlockAndPreheader' was the continuation block for some call to
598 // `changeIterationSpaceEnd' and is the preheader to the loop denoted by `LS'.
599 // This function rewrites the PHI nodes in `LS.Header' to start with the
601 void rewriteIncomingValuesForPHIs(
602 LoopStructure &LS, BasicBlock *ContinuationBlockAndPreheader,
603 const LoopConstrainer::RewrittenRangeInfo &RRI) const;
605 // Even though we do not preserve any passes at this time, we at least need to
606 // keep the parent loop structure consistent. The `LPPassManager' seems to
607 // verify this after running a loop pass. This function adds the list of
608 // blocks denoted by BBs to this loops parent loop if required.
609 void addToParentLoopIfNeeded(ArrayRef<BasicBlock *> BBs);
611 // Some global state.
619 // Information about the original loop we started out with.
621 const SCEV *LatchTakenCount;
622 BasicBlock *OriginalPreheader;
624 // The preheader of the main loop. This may or may not be different from
625 // `OriginalPreheader'.
626 BasicBlock *MainLoopPreheader;
628 // The range we need to run the main loop in.
629 InductiveRangeCheck::Range Range;
631 // The structure of the main loop (see comment at the beginning of this class
633 LoopStructure MainLoopStructure;
636 LoopConstrainer(Loop &L, LoopInfo &LI, LPPassManager &LPM,
637 const LoopStructure &LS, ScalarEvolution &SE,
638 DominatorTree &DT, InductiveRangeCheck::Range R)
639 : F(*L.getHeader()->getParent()), Ctx(L.getHeader()->getContext()),
640 SE(SE), DT(DT), LPM(LPM), LI(LI), OriginalLoop(L),
641 LatchTakenCount(nullptr), OriginalPreheader(nullptr),
642 MainLoopPreheader(nullptr), Range(R), MainLoopStructure(LS) {}
644 // Entry point for the algorithm. Returns true on success.
650 void LoopConstrainer::replacePHIBlock(PHINode *PN, BasicBlock *Block,
651 BasicBlock *ReplaceBy) {
652 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
653 if (PN->getIncomingBlock(i) == Block)
654 PN->setIncomingBlock(i, ReplaceBy);
657 static bool CanBeMax(ScalarEvolution &SE, const SCEV *S, bool Signed) {
659 APInt::getSignedMaxValue(cast<IntegerType>(S->getType())->getBitWidth()) :
660 APInt::getMaxValue(cast<IntegerType>(S->getType())->getBitWidth());
661 return SE.getSignedRange(S).contains(Max) &&
662 SE.getUnsignedRange(S).contains(Max);
665 static bool SumCanReachMax(ScalarEvolution &SE, const SCEV *S1, const SCEV *S2,
667 // S1 < INT_MAX - S2 ===> S1 + S2 < INT_MAX.
668 assert(SE.isKnownNonNegative(S2) &&
669 "We expected the 2nd arg to be non-negative!");
670 const SCEV *Max = SE.getConstant(
671 Signed ? APInt::getSignedMaxValue(
672 cast<IntegerType>(S1->getType())->getBitWidth())
673 : APInt::getMaxValue(
674 cast<IntegerType>(S1->getType())->getBitWidth()));
675 const SCEV *CapForS1 = SE.getMinusSCEV(Max, S2);
676 return !SE.isKnownPredicate(Signed ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT,
680 static bool CanBeMin(ScalarEvolution &SE, const SCEV *S, bool Signed) {
682 APInt::getSignedMinValue(cast<IntegerType>(S->getType())->getBitWidth()) :
683 APInt::getMinValue(cast<IntegerType>(S->getType())->getBitWidth());
684 return SE.getSignedRange(S).contains(Min) &&
685 SE.getUnsignedRange(S).contains(Min);
688 static bool SumCanReachMin(ScalarEvolution &SE, const SCEV *S1, const SCEV *S2,
690 // S1 > INT_MIN - S2 ===> S1 + S2 > INT_MIN.
691 assert(SE.isKnownNonPositive(S2) &&
692 "We expected the 2nd arg to be non-positive!");
693 const SCEV *Max = SE.getConstant(
694 Signed ? APInt::getSignedMinValue(
695 cast<IntegerType>(S1->getType())->getBitWidth())
696 : APInt::getMinValue(
697 cast<IntegerType>(S1->getType())->getBitWidth()));
698 const SCEV *CapForS1 = SE.getMinusSCEV(Max, S2);
699 return !SE.isKnownPredicate(Signed ? ICmpInst::ICMP_SGT : ICmpInst::ICMP_UGT,
703 Optional<LoopStructure>
704 LoopStructure::parseLoopStructure(ScalarEvolution &SE,
705 BranchProbabilityInfo &BPI,
706 Loop &L, const char *&FailureReason) {
707 if (!L.isLoopSimplifyForm()) {
708 FailureReason = "loop not in LoopSimplify form";
712 BasicBlock *Latch = L.getLoopLatch();
713 assert(Latch && "Simplified loops only have one latch!");
715 if (Latch->getTerminator()->getMetadata(ClonedLoopTag)) {
716 FailureReason = "loop has already been cloned";
720 if (!L.isLoopExiting(Latch)) {
721 FailureReason = "no loop latch";
725 BasicBlock *Header = L.getHeader();
726 BasicBlock *Preheader = L.getLoopPreheader();
728 FailureReason = "no preheader";
732 BranchInst *LatchBr = dyn_cast<BranchInst>(Latch->getTerminator());
733 if (!LatchBr || LatchBr->isUnconditional()) {
734 FailureReason = "latch terminator not conditional branch";
738 unsigned LatchBrExitIdx = LatchBr->getSuccessor(0) == Header ? 1 : 0;
740 BranchProbability ExitProbability =
741 BPI.getEdgeProbability(LatchBr->getParent(), LatchBrExitIdx);
743 if (!SkipProfitabilityChecks &&
744 ExitProbability > BranchProbability(1, MaxExitProbReciprocal)) {
745 FailureReason = "short running loop, not profitable";
749 ICmpInst *ICI = dyn_cast<ICmpInst>(LatchBr->getCondition());
750 if (!ICI || !isa<IntegerType>(ICI->getOperand(0)->getType())) {
751 FailureReason = "latch terminator branch not conditional on integral icmp";
755 const SCEV *LatchCount = SE.getExitCount(&L, Latch);
756 if (isa<SCEVCouldNotCompute>(LatchCount)) {
757 FailureReason = "could not compute latch count";
761 ICmpInst::Predicate Pred = ICI->getPredicate();
762 Value *LeftValue = ICI->getOperand(0);
763 const SCEV *LeftSCEV = SE.getSCEV(LeftValue);
764 IntegerType *IndVarTy = cast<IntegerType>(LeftValue->getType());
766 Value *RightValue = ICI->getOperand(1);
767 const SCEV *RightSCEV = SE.getSCEV(RightValue);
769 // We canonicalize `ICI` such that `LeftSCEV` is an add recurrence.
770 if (!isa<SCEVAddRecExpr>(LeftSCEV)) {
771 if (isa<SCEVAddRecExpr>(RightSCEV)) {
772 std::swap(LeftSCEV, RightSCEV);
773 std::swap(LeftValue, RightValue);
774 Pred = ICmpInst::getSwappedPredicate(Pred);
776 FailureReason = "no add recurrences in the icmp";
781 auto HasNoSignedWrap = [&](const SCEVAddRecExpr *AR) {
782 if (AR->getNoWrapFlags(SCEV::FlagNSW))
785 IntegerType *Ty = cast<IntegerType>(AR->getType());
786 IntegerType *WideTy =
787 IntegerType::get(Ty->getContext(), Ty->getBitWidth() * 2);
789 const SCEVAddRecExpr *ExtendAfterOp =
790 dyn_cast<SCEVAddRecExpr>(SE.getSignExtendExpr(AR, WideTy));
792 const SCEV *ExtendedStart = SE.getSignExtendExpr(AR->getStart(), WideTy);
793 const SCEV *ExtendedStep =
794 SE.getSignExtendExpr(AR->getStepRecurrence(SE), WideTy);
796 bool NoSignedWrap = ExtendAfterOp->getStart() == ExtendedStart &&
797 ExtendAfterOp->getStepRecurrence(SE) == ExtendedStep;
803 // We may have proved this when computing the sign extension above.
804 return AR->getNoWrapFlags(SCEV::FlagNSW) != SCEV::FlagAnyWrap;
807 // Here we check whether the suggested AddRec is an induction variable that
808 // can be handled (i.e. with known constant step), and if yes, calculate its
809 // step and identify whether it is increasing or decreasing.
810 auto IsInductionVar = [&](const SCEVAddRecExpr *AR, bool &IsIncreasing,
811 ConstantInt *&StepCI) {
815 // Currently we only work with induction variables that have been proved to
816 // not wrap. This restriction can potentially be lifted in the future.
818 if (!HasNoSignedWrap(AR))
821 if (const SCEVConstant *StepExpr =
822 dyn_cast<SCEVConstant>(AR->getStepRecurrence(SE))) {
823 StepCI = StepExpr->getValue();
824 assert(!StepCI->isZero() && "Zero step?");
825 IsIncreasing = !StepCI->isNegative();
832 // `ICI` is interpreted as taking the backedge if the *next* value of the
833 // induction variable satisfies some constraint.
835 const SCEVAddRecExpr *IndVarBase = cast<SCEVAddRecExpr>(LeftSCEV);
836 bool IsIncreasing = false;
837 bool IsSignedPredicate = true;
839 if (!IsInductionVar(IndVarBase, IsIncreasing, StepCI)) {
840 FailureReason = "LHS in icmp not induction variable";
844 const SCEV *StartNext = IndVarBase->getStart();
845 const SCEV *Addend = SE.getNegativeSCEV(IndVarBase->getStepRecurrence(SE));
846 const SCEV *IndVarStart = SE.getAddExpr(StartNext, Addend);
847 const SCEV *Step = SE.getSCEV(StepCI);
849 ConstantInt *One = ConstantInt::get(IndVarTy, 1);
851 bool DecreasedRightValueByOne = false;
852 if (StepCI->isOne()) {
853 // Try to turn eq/ne predicates to those we can work with.
854 if (Pred == ICmpInst::ICMP_NE && LatchBrExitIdx == 1)
855 // while (++i != len) { while (++i < len) {
858 // If both parts are known non-negative, it is profitable to use
859 // unsigned comparison in increasing loop. This allows us to make the
860 // comparison check against "RightSCEV + 1" more optimistic.
861 if (SE.isKnownNonNegative(IndVarStart) &&
862 SE.isKnownNonNegative(RightSCEV))
863 Pred = ICmpInst::ICMP_ULT;
865 Pred = ICmpInst::ICMP_SLT;
866 else if (Pred == ICmpInst::ICMP_EQ && LatchBrExitIdx == 0 &&
867 !CanBeMin(SE, RightSCEV, /* IsSignedPredicate */ true)) {
868 // while (true) { while (true) {
869 // if (++i == len) ---> if (++i > len - 1)
873 // TODO: Insert ICMP_UGT if both are non-negative?
874 Pred = ICmpInst::ICMP_SGT;
875 RightSCEV = SE.getMinusSCEV(RightSCEV, SE.getOne(RightSCEV->getType()));
876 DecreasedRightValueByOne = true;
880 bool LTPred = (Pred == ICmpInst::ICMP_SLT || Pred == ICmpInst::ICMP_ULT);
881 bool GTPred = (Pred == ICmpInst::ICMP_SGT || Pred == ICmpInst::ICMP_UGT);
882 bool FoundExpectedPred =
883 (LTPred && LatchBrExitIdx == 1) || (GTPred && LatchBrExitIdx == 0);
885 if (!FoundExpectedPred) {
886 FailureReason = "expected icmp slt semantically, found something else";
891 Pred == ICmpInst::ICMP_SLT || Pred == ICmpInst::ICMP_SGT;
892 // The predicate that we need to check that the induction variable lies
894 ICmpInst::Predicate BoundPred =
895 IsSignedPredicate ? CmpInst::ICMP_SLT : CmpInst::ICMP_ULT;
897 if (LatchBrExitIdx == 0) {
898 const SCEV *StepMinusOne = SE.getMinusSCEV(Step,
899 SE.getOne(Step->getType()));
900 if (SumCanReachMax(SE, RightSCEV, StepMinusOne, IsSignedPredicate)) {
901 // TODO: this restriction is easily removable -- we just have to
902 // remember that the icmp was an slt and not an sle.
903 FailureReason = "limit may overflow when coercing le to lt";
907 if (!SE.isLoopEntryGuardedByCond(
908 &L, BoundPred, IndVarStart,
909 SE.getAddExpr(RightSCEV, Step))) {
910 FailureReason = "Induction variable start not bounded by upper limit";
914 // We need to increase the right value unless we have already decreased
915 // it virtually when we replaced EQ with SGT.
916 if (!DecreasedRightValueByOne) {
917 IRBuilder<> B(Preheader->getTerminator());
918 RightValue = B.CreateAdd(RightValue, One);
921 if (!SE.isLoopEntryGuardedByCond(&L, BoundPred, IndVarStart, RightSCEV)) {
922 FailureReason = "Induction variable start not bounded by upper limit";
925 assert(!DecreasedRightValueByOne &&
926 "Right value can be decreased only for LatchBrExitIdx == 0!");
929 bool IncreasedRightValueByOne = false;
930 if (StepCI->isMinusOne()) {
931 // Try to turn eq/ne predicates to those we can work with.
932 if (Pred == ICmpInst::ICMP_NE && LatchBrExitIdx == 1)
933 // while (--i != len) { while (--i > len) {
936 // We intentionally don't turn the predicate into UGT even if we know
937 // that both operands are non-negative, because it will only pessimize
938 // our check against "RightSCEV - 1".
939 Pred = ICmpInst::ICMP_SGT;
940 else if (Pred == ICmpInst::ICMP_EQ && LatchBrExitIdx == 0 &&
941 !CanBeMax(SE, RightSCEV, /* IsSignedPredicate */ true)) {
942 // while (true) { while (true) {
943 // if (--i == len) ---> if (--i < len + 1)
947 // TODO: Insert ICMP_ULT if both are non-negative?
948 Pred = ICmpInst::ICMP_SLT;
949 RightSCEV = SE.getAddExpr(RightSCEV, SE.getOne(RightSCEV->getType()));
950 IncreasedRightValueByOne = true;
954 bool LTPred = (Pred == ICmpInst::ICMP_SLT || Pred == ICmpInst::ICMP_ULT);
955 bool GTPred = (Pred == ICmpInst::ICMP_SGT || Pred == ICmpInst::ICMP_UGT);
957 bool FoundExpectedPred =
958 (GTPred && LatchBrExitIdx == 1) || (LTPred && LatchBrExitIdx == 0);
960 if (!FoundExpectedPred) {
961 FailureReason = "expected icmp sgt semantically, found something else";
966 Pred == ICmpInst::ICMP_SLT || Pred == ICmpInst::ICMP_SGT;
967 // The predicate that we need to check that the induction variable lies
969 ICmpInst::Predicate BoundPred =
970 IsSignedPredicate ? CmpInst::ICMP_SGT : CmpInst::ICMP_UGT;
972 if (LatchBrExitIdx == 0) {
973 const SCEV *StepPlusOne = SE.getAddExpr(Step, SE.getOne(Step->getType()));
974 if (SumCanReachMin(SE, RightSCEV, StepPlusOne, IsSignedPredicate)) {
975 // TODO: this restriction is easily removable -- we just have to
976 // remember that the icmp was an sgt and not an sge.
977 FailureReason = "limit may overflow when coercing ge to gt";
981 if (!SE.isLoopEntryGuardedByCond(
982 &L, BoundPred, IndVarStart,
983 SE.getMinusSCEV(RightSCEV, SE.getOne(RightSCEV->getType())))) {
984 FailureReason = "Induction variable start not bounded by lower limit";
988 // We need to decrease the right value unless we have already increased
989 // it virtually when we replaced EQ with SLT.
990 if (!IncreasedRightValueByOne) {
991 IRBuilder<> B(Preheader->getTerminator());
992 RightValue = B.CreateSub(RightValue, One);
995 if (!SE.isLoopEntryGuardedByCond(&L, BoundPred, IndVarStart, RightSCEV)) {
996 FailureReason = "Induction variable start not bounded by lower limit";
999 assert(!IncreasedRightValueByOne &&
1000 "Right value can be increased only for LatchBrExitIdx == 0!");
1003 BasicBlock *LatchExit = LatchBr->getSuccessor(LatchBrExitIdx);
1005 assert(SE.getLoopDisposition(LatchCount, &L) ==
1006 ScalarEvolution::LoopInvariant &&
1007 "loop variant exit count doesn't make sense!");
1009 assert(!L.contains(LatchExit) && "expected an exit block!");
1010 const DataLayout &DL = Preheader->getModule()->getDataLayout();
1011 Value *IndVarStartV =
1012 SCEVExpander(SE, DL, "irce")
1013 .expandCodeFor(IndVarStart, IndVarTy, Preheader->getTerminator());
1014 IndVarStartV->setName("indvar.start");
1016 LoopStructure Result;
1018 Result.Tag = "main";
1019 Result.Header = Header;
1020 Result.Latch = Latch;
1021 Result.LatchBr = LatchBr;
1022 Result.LatchExit = LatchExit;
1023 Result.LatchBrExitIdx = LatchBrExitIdx;
1024 Result.IndVarStart = IndVarStartV;
1025 Result.IndVarStep = StepCI;
1026 Result.IndVarBase = LeftValue;
1027 Result.IndVarIncreasing = IsIncreasing;
1028 Result.LoopExitAt = RightValue;
1029 Result.IsSignedPredicate = IsSignedPredicate;
1031 FailureReason = nullptr;
1036 Optional<LoopConstrainer::SubRanges>
1037 LoopConstrainer::calculateSubRanges(bool IsSignedPredicate) const {
1038 IntegerType *Ty = cast<IntegerType>(LatchTakenCount->getType());
1040 if (Range.getType() != Ty)
1043 LoopConstrainer::SubRanges Result;
1045 // I think we can be more aggressive here and make this nuw / nsw if the
1046 // addition that feeds into the icmp for the latch's terminating branch is nuw
1047 // / nsw. In any case, a wrapping 2's complement addition is safe.
1048 const SCEV *Start = SE.getSCEV(MainLoopStructure.IndVarStart);
1049 const SCEV *End = SE.getSCEV(MainLoopStructure.LoopExitAt);
1051 bool Increasing = MainLoopStructure.IndVarIncreasing;
1053 // We compute `Smallest` and `Greatest` such that [Smallest, Greatest), or
1054 // [Smallest, GreatestSeen] is the range of values the induction variable
1057 const SCEV *Smallest = nullptr, *Greatest = nullptr, *GreatestSeen = nullptr;
1059 const SCEV *One = SE.getOne(Ty);
1063 // No overflow, because the range [Smallest, GreatestSeen] is not empty.
1064 GreatestSeen = SE.getMinusSCEV(End, One);
1066 // These two computations may sign-overflow. Here is why that is okay:
1068 // We know that the induction variable does not sign-overflow on any
1069 // iteration except the last one, and it starts at `Start` and ends at
1070 // `End`, decrementing by one every time.
1072 // * if `Smallest` sign-overflows we know `End` is `INT_SMAX`. Since the
1073 // induction variable is decreasing we know that that the smallest value
1074 // the loop body is actually executed with is `INT_SMIN` == `Smallest`.
1076 // * if `Greatest` sign-overflows, we know it can only be `INT_SMIN`. In
1077 // that case, `Clamp` will always return `Smallest` and
1078 // [`Result.LowLimit`, `Result.HighLimit`) = [`Smallest`, `Smallest`)
1079 // will be an empty range. Returning an empty range is always safe.
1082 Smallest = SE.getAddExpr(End, One);
1083 Greatest = SE.getAddExpr(Start, One);
1084 GreatestSeen = Start;
1087 auto Clamp = [this, Smallest, Greatest, IsSignedPredicate](const SCEV *S) {
1088 bool MaybeNegativeValues = IsSignedPredicate || !SE.isKnownNonNegative(S);
1089 return MaybeNegativeValues
1090 ? SE.getSMaxExpr(Smallest, SE.getSMinExpr(Greatest, S))
1091 : SE.getUMaxExpr(Smallest, SE.getUMinExpr(Greatest, S));
1094 // In some cases we can prove that we don't need a pre or post loop.
1095 ICmpInst::Predicate PredLE =
1096 IsSignedPredicate ? ICmpInst::ICMP_SLE : ICmpInst::ICMP_ULE;
1097 ICmpInst::Predicate PredLT =
1098 IsSignedPredicate ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT;
1100 bool ProvablyNoPreloop =
1101 SE.isKnownPredicate(PredLE, Range.getBegin(), Smallest);
1102 if (!ProvablyNoPreloop)
1103 Result.LowLimit = Clamp(Range.getBegin());
1105 bool ProvablyNoPostLoop =
1106 SE.isKnownPredicate(PredLT, GreatestSeen, Range.getEnd());
1107 if (!ProvablyNoPostLoop)
1108 Result.HighLimit = Clamp(Range.getEnd());
1113 void LoopConstrainer::cloneLoop(LoopConstrainer::ClonedLoop &Result,
1114 const char *Tag) const {
1115 for (BasicBlock *BB : OriginalLoop.getBlocks()) {
1116 BasicBlock *Clone = CloneBasicBlock(BB, Result.Map, Twine(".") + Tag, &F);
1117 Result.Blocks.push_back(Clone);
1118 Result.Map[BB] = Clone;
1121 auto GetClonedValue = [&Result](Value *V) {
1122 assert(V && "null values not in domain!");
1123 auto It = Result.Map.find(V);
1124 if (It == Result.Map.end())
1126 return static_cast<Value *>(It->second);
1130 cast<BasicBlock>(GetClonedValue(OriginalLoop.getLoopLatch()));
1131 ClonedLatch->getTerminator()->setMetadata(ClonedLoopTag,
1132 MDNode::get(Ctx, {}));
1134 Result.Structure = MainLoopStructure.map(GetClonedValue);
1135 Result.Structure.Tag = Tag;
1137 for (unsigned i = 0, e = Result.Blocks.size(); i != e; ++i) {
1138 BasicBlock *ClonedBB = Result.Blocks[i];
1139 BasicBlock *OriginalBB = OriginalLoop.getBlocks()[i];
1141 assert(Result.Map[OriginalBB] == ClonedBB && "invariant!");
1143 for (Instruction &I : *ClonedBB)
1144 RemapInstruction(&I, Result.Map,
1145 RF_NoModuleLevelChanges | RF_IgnoreMissingLocals);
1147 // Exit blocks will now have one more predecessor and their PHI nodes need
1148 // to be edited to reflect that. No phi nodes need to be introduced because
1149 // the loop is in LCSSA.
1151 for (auto *SBB : successors(OriginalBB)) {
1152 if (OriginalLoop.contains(SBB))
1153 continue; // not an exit block
1155 for (Instruction &I : *SBB) {
1156 auto *PN = dyn_cast<PHINode>(&I);
1160 Value *OldIncoming = PN->getIncomingValueForBlock(OriginalBB);
1161 PN->addIncoming(GetClonedValue(OldIncoming), ClonedBB);
1167 LoopConstrainer::RewrittenRangeInfo LoopConstrainer::changeIterationSpaceEnd(
1168 const LoopStructure &LS, BasicBlock *Preheader, Value *ExitSubloopAt,
1169 BasicBlock *ContinuationBlock) const {
1171 // We start with a loop with a single latch:
1173 // +--------------------+
1177 // +--------+-----------+
1178 // | ----------------\
1180 // +--------v----v------+ |
1184 // +--------------------+ |
1188 // +--------------------+ |
1190 // | latch >----------/
1192 // +-------v------------+
1195 // | +--------------------+
1197 // +---> original exit |
1199 // +--------------------+
1201 // We change the control flow to look like
1204 // +--------------------+
1206 // | preheader >-------------------------+
1208 // +--------v-----------+ |
1209 // | /-------------+ |
1211 // +--------v--v--------+ | |
1213 // | header | | +--------+ |
1215 // +--------------------+ | | +-----v-----v-----------+
1217 // | | | .pseudo.exit |
1219 // | | +-----------v-----------+
1222 // | | +--------v-------------+
1223 // +--------------------+ | | | |
1224 // | | | | | ContinuationBlock |
1225 // | latch >------+ | | |
1226 // | | | +----------------------+
1227 // +---------v----------+ |
1230 // | +---------------^-----+
1232 // +-----> .exit.selector |
1234 // +----------v----------+
1236 // +--------------------+ |
1238 // | original exit <----+
1240 // +--------------------+
1243 RewrittenRangeInfo RRI;
1245 BasicBlock *BBInsertLocation = LS.Latch->getNextNode();
1246 RRI.ExitSelector = BasicBlock::Create(Ctx, Twine(LS.Tag) + ".exit.selector",
1247 &F, BBInsertLocation);
1248 RRI.PseudoExit = BasicBlock::Create(Ctx, Twine(LS.Tag) + ".pseudo.exit", &F,
1251 BranchInst *PreheaderJump = cast<BranchInst>(Preheader->getTerminator());
1252 bool Increasing = LS.IndVarIncreasing;
1253 bool IsSignedPredicate = LS.IsSignedPredicate;
1255 IRBuilder<> B(PreheaderJump);
1257 // EnterLoopCond - is it okay to start executing this `LS'?
1258 Value *EnterLoopCond = nullptr;
1260 EnterLoopCond = IsSignedPredicate
1261 ? B.CreateICmpSLT(LS.IndVarStart, ExitSubloopAt)
1262 : B.CreateICmpULT(LS.IndVarStart, ExitSubloopAt);
1264 EnterLoopCond = IsSignedPredicate
1265 ? B.CreateICmpSGT(LS.IndVarStart, ExitSubloopAt)
1266 : B.CreateICmpUGT(LS.IndVarStart, ExitSubloopAt);
1268 B.CreateCondBr(EnterLoopCond, LS.Header, RRI.PseudoExit);
1269 PreheaderJump->eraseFromParent();
1271 LS.LatchBr->setSuccessor(LS.LatchBrExitIdx, RRI.ExitSelector);
1272 B.SetInsertPoint(LS.LatchBr);
1273 Value *TakeBackedgeLoopCond = nullptr;
1275 TakeBackedgeLoopCond = IsSignedPredicate
1276 ? B.CreateICmpSLT(LS.IndVarBase, ExitSubloopAt)
1277 : B.CreateICmpULT(LS.IndVarBase, ExitSubloopAt);
1279 TakeBackedgeLoopCond = IsSignedPredicate
1280 ? B.CreateICmpSGT(LS.IndVarBase, ExitSubloopAt)
1281 : B.CreateICmpUGT(LS.IndVarBase, ExitSubloopAt);
1282 Value *CondForBranch = LS.LatchBrExitIdx == 1
1283 ? TakeBackedgeLoopCond
1284 : B.CreateNot(TakeBackedgeLoopCond);
1286 LS.LatchBr->setCondition(CondForBranch);
1288 B.SetInsertPoint(RRI.ExitSelector);
1290 // IterationsLeft - are there any more iterations left, given the original
1291 // upper bound on the induction variable? If not, we branch to the "real"
1293 Value *IterationsLeft = nullptr;
1295 IterationsLeft = IsSignedPredicate
1296 ? B.CreateICmpSLT(LS.IndVarBase, LS.LoopExitAt)
1297 : B.CreateICmpULT(LS.IndVarBase, LS.LoopExitAt);
1299 IterationsLeft = IsSignedPredicate
1300 ? B.CreateICmpSGT(LS.IndVarBase, LS.LoopExitAt)
1301 : B.CreateICmpUGT(LS.IndVarBase, LS.LoopExitAt);
1302 B.CreateCondBr(IterationsLeft, RRI.PseudoExit, LS.LatchExit);
1304 BranchInst *BranchToContinuation =
1305 BranchInst::Create(ContinuationBlock, RRI.PseudoExit);
1307 // We emit PHI nodes into `RRI.PseudoExit' that compute the "latest" value of
1308 // each of the PHI nodes in the loop header. This feeds into the initial
1309 // value of the same PHI nodes if/when we continue execution.
1310 for (Instruction &I : *LS.Header) {
1311 auto *PN = dyn_cast<PHINode>(&I);
1315 PHINode *NewPHI = PHINode::Create(PN->getType(), 2, PN->getName() + ".copy",
1316 BranchToContinuation);
1318 NewPHI->addIncoming(PN->getIncomingValueForBlock(Preheader), Preheader);
1319 NewPHI->addIncoming(PN->getIncomingValueForBlock(LS.Latch),
1321 RRI.PHIValuesAtPseudoExit.push_back(NewPHI);
1324 RRI.IndVarEnd = PHINode::Create(LS.IndVarBase->getType(), 2, "indvar.end",
1325 BranchToContinuation);
1326 RRI.IndVarEnd->addIncoming(LS.IndVarStart, Preheader);
1327 RRI.IndVarEnd->addIncoming(LS.IndVarBase, RRI.ExitSelector);
1329 // The latch exit now has a branch from `RRI.ExitSelector' instead of
1330 // `LS.Latch'. The PHI nodes need to be updated to reflect that.
1331 for (Instruction &I : *LS.LatchExit) {
1332 if (PHINode *PN = dyn_cast<PHINode>(&I))
1333 replacePHIBlock(PN, LS.Latch, RRI.ExitSelector);
1341 void LoopConstrainer::rewriteIncomingValuesForPHIs(
1342 LoopStructure &LS, BasicBlock *ContinuationBlock,
1343 const LoopConstrainer::RewrittenRangeInfo &RRI) const {
1345 unsigned PHIIndex = 0;
1346 for (Instruction &I : *LS.Header) {
1347 auto *PN = dyn_cast<PHINode>(&I);
1351 for (unsigned i = 0, e = PN->getNumIncomingValues(); i < e; ++i)
1352 if (PN->getIncomingBlock(i) == ContinuationBlock)
1353 PN->setIncomingValue(i, RRI.PHIValuesAtPseudoExit[PHIIndex++]);
1356 LS.IndVarStart = RRI.IndVarEnd;
1359 BasicBlock *LoopConstrainer::createPreheader(const LoopStructure &LS,
1360 BasicBlock *OldPreheader,
1361 const char *Tag) const {
1363 BasicBlock *Preheader = BasicBlock::Create(Ctx, Tag, &F, LS.Header);
1364 BranchInst::Create(LS.Header, Preheader);
1366 for (Instruction &I : *LS.Header) {
1367 auto *PN = dyn_cast<PHINode>(&I);
1371 for (unsigned i = 0, e = PN->getNumIncomingValues(); i < e; ++i)
1372 replacePHIBlock(PN, OldPreheader, Preheader);
1378 void LoopConstrainer::addToParentLoopIfNeeded(ArrayRef<BasicBlock *> BBs) {
1379 Loop *ParentLoop = OriginalLoop.getParentLoop();
1383 for (BasicBlock *BB : BBs)
1384 ParentLoop->addBasicBlockToLoop(BB, LI);
1387 Loop *LoopConstrainer::createClonedLoopStructure(Loop *Original, Loop *Parent,
1388 ValueToValueMapTy &VM) {
1389 Loop &New = *new Loop();
1391 Parent->addChildLoop(&New);
1393 LI.addTopLevelLoop(&New);
1396 // Add all of the blocks in Original to the new loop.
1397 for (auto *BB : Original->blocks())
1398 if (LI.getLoopFor(BB) == Original)
1399 New.addBasicBlockToLoop(cast<BasicBlock>(VM[BB]), LI);
1401 // Add all of the subloops to the new loop.
1402 for (Loop *SubLoop : *Original)
1403 createClonedLoopStructure(SubLoop, &New, VM);
1408 bool LoopConstrainer::run() {
1409 BasicBlock *Preheader = nullptr;
1410 LatchTakenCount = SE.getExitCount(&OriginalLoop, MainLoopStructure.Latch);
1411 Preheader = OriginalLoop.getLoopPreheader();
1412 assert(!isa<SCEVCouldNotCompute>(LatchTakenCount) && Preheader != nullptr &&
1415 OriginalPreheader = Preheader;
1416 MainLoopPreheader = Preheader;
1418 bool IsSignedPredicate = MainLoopStructure.IsSignedPredicate;
1419 Optional<SubRanges> MaybeSR = calculateSubRanges(IsSignedPredicate);
1420 if (!MaybeSR.hasValue()) {
1421 DEBUG(dbgs() << "irce: could not compute subranges\n");
1425 SubRanges SR = MaybeSR.getValue();
1426 bool Increasing = MainLoopStructure.IndVarIncreasing;
1428 cast<IntegerType>(MainLoopStructure.IndVarBase->getType());
1430 SCEVExpander Expander(SE, F.getParent()->getDataLayout(), "irce");
1431 Instruction *InsertPt = OriginalPreheader->getTerminator();
1433 // It would have been better to make `PreLoop' and `PostLoop'
1434 // `Optional<ClonedLoop>'s, but `ValueToValueMapTy' does not have a copy
1436 ClonedLoop PreLoop, PostLoop;
1438 Increasing ? SR.LowLimit.hasValue() : SR.HighLimit.hasValue();
1439 bool NeedsPostLoop =
1440 Increasing ? SR.HighLimit.hasValue() : SR.LowLimit.hasValue();
1442 Value *ExitPreLoopAt = nullptr;
1443 Value *ExitMainLoopAt = nullptr;
1444 const SCEVConstant *MinusOneS =
1445 cast<SCEVConstant>(SE.getConstant(IVTy, -1, true /* isSigned */));
1448 const SCEV *ExitPreLoopAtSCEV = nullptr;
1451 ExitPreLoopAtSCEV = *SR.LowLimit;
1453 if (CanBeMin(SE, *SR.HighLimit, IsSignedPredicate)) {
1454 DEBUG(dbgs() << "irce: could not prove no-overflow when computing "
1455 << "preloop exit limit. HighLimit = " << *(*SR.HighLimit)
1459 ExitPreLoopAtSCEV = SE.getAddExpr(*SR.HighLimit, MinusOneS);
1462 ExitPreLoopAt = Expander.expandCodeFor(ExitPreLoopAtSCEV, IVTy, InsertPt);
1463 ExitPreLoopAt->setName("exit.preloop.at");
1466 if (NeedsPostLoop) {
1467 const SCEV *ExitMainLoopAtSCEV = nullptr;
1470 ExitMainLoopAtSCEV = *SR.HighLimit;
1472 if (CanBeMin(SE, *SR.LowLimit, IsSignedPredicate)) {
1473 DEBUG(dbgs() << "irce: could not prove no-overflow when computing "
1474 << "mainloop exit limit. LowLimit = " << *(*SR.LowLimit)
1478 ExitMainLoopAtSCEV = SE.getAddExpr(*SR.LowLimit, MinusOneS);
1481 ExitMainLoopAt = Expander.expandCodeFor(ExitMainLoopAtSCEV, IVTy, InsertPt);
1482 ExitMainLoopAt->setName("exit.mainloop.at");
1485 // We clone these ahead of time so that we don't have to deal with changing
1486 // and temporarily invalid IR as we transform the loops.
1488 cloneLoop(PreLoop, "preloop");
1490 cloneLoop(PostLoop, "postloop");
1492 RewrittenRangeInfo PreLoopRRI;
1495 Preheader->getTerminator()->replaceUsesOfWith(MainLoopStructure.Header,
1496 PreLoop.Structure.Header);
1499 createPreheader(MainLoopStructure, Preheader, "mainloop");
1500 PreLoopRRI = changeIterationSpaceEnd(PreLoop.Structure, Preheader,
1501 ExitPreLoopAt, MainLoopPreheader);
1502 rewriteIncomingValuesForPHIs(MainLoopStructure, MainLoopPreheader,
1506 BasicBlock *PostLoopPreheader = nullptr;
1507 RewrittenRangeInfo PostLoopRRI;
1509 if (NeedsPostLoop) {
1511 createPreheader(PostLoop.Structure, Preheader, "postloop");
1512 PostLoopRRI = changeIterationSpaceEnd(MainLoopStructure, MainLoopPreheader,
1513 ExitMainLoopAt, PostLoopPreheader);
1514 rewriteIncomingValuesForPHIs(PostLoop.Structure, PostLoopPreheader,
1518 BasicBlock *NewMainLoopPreheader =
1519 MainLoopPreheader != Preheader ? MainLoopPreheader : nullptr;
1520 BasicBlock *NewBlocks[] = {PostLoopPreheader, PreLoopRRI.PseudoExit,
1521 PreLoopRRI.ExitSelector, PostLoopRRI.PseudoExit,
1522 PostLoopRRI.ExitSelector, NewMainLoopPreheader};
1524 // Some of the above may be nullptr, filter them out before passing to
1525 // addToParentLoopIfNeeded.
1527 std::remove(std::begin(NewBlocks), std::end(NewBlocks), nullptr);
1529 addToParentLoopIfNeeded(makeArrayRef(std::begin(NewBlocks), NewBlocksEnd));
1533 // We need to first add all the pre and post loop blocks into the loop
1534 // structures (as part of createClonedLoopStructure), and then update the
1535 // LCSSA form and LoopSimplifyForm. This is necessary for correctly updating
1536 // LI when LoopSimplifyForm is generated.
1537 Loop *PreL = nullptr, *PostL = nullptr;
1538 if (!PreLoop.Blocks.empty()) {
1539 PreL = createClonedLoopStructure(
1540 &OriginalLoop, OriginalLoop.getParentLoop(), PreLoop.Map);
1543 if (!PostLoop.Blocks.empty()) {
1544 PostL = createClonedLoopStructure(
1545 &OriginalLoop, OriginalLoop.getParentLoop(), PostLoop.Map);
1548 // This function canonicalizes the loop into Loop-Simplify and LCSSA forms.
1549 auto CanonicalizeLoop = [&] (Loop *L, bool IsOriginalLoop) {
1550 formLCSSARecursively(*L, DT, &LI, &SE);
1551 simplifyLoop(L, &DT, &LI, &SE, nullptr, true);
1552 // Pre/post loops are slow paths, we do not need to perform any loop
1553 // optimizations on them.
1554 if (!IsOriginalLoop)
1555 DisableAllLoopOptsOnLoop(*L);
1558 CanonicalizeLoop(PreL, false);
1560 CanonicalizeLoop(PostL, false);
1561 CanonicalizeLoop(&OriginalLoop, true);
1566 /// Computes and returns a range of values for the induction variable (IndVar)
1567 /// in which the range check can be safely elided. If it cannot compute such a
1568 /// range, returns None.
1569 Optional<InductiveRangeCheck::Range>
1570 InductiveRangeCheck::computeSafeIterationSpace(
1571 ScalarEvolution &SE, const SCEVAddRecExpr *IndVar) const {
1572 // IndVar is of the form "A + B * I" (where "I" is the canonical induction
1573 // variable, that may or may not exist as a real llvm::Value in the loop) and
1574 // this inductive range check is a range check on the "C + D * I" ("C" is
1575 // getOffset() and "D" is getScale()). We rewrite the value being range
1576 // checked to "M + N * IndVar" where "N" = "D * B^(-1)" and "M" = "C - NA".
1578 // The actual inequalities we solve are of the form
1580 // 0 <= M + 1 * IndVar < L given L >= 0 (i.e. N == 1)
1582 // The inequality is satisfied by -M <= IndVar < (L - M) [^1]. All additions
1583 // and subtractions are twos-complement wrapping and comparisons are signed.
1587 // If there exists IndVar such that -M <= IndVar < (L - M) then it follows
1588 // that -M <= (-M + L) [== Eq. 1]. Since L >= 0, if (-M + L) sign-overflows
1589 // then (-M + L) < (-M). Hence by [Eq. 1], (-M + L) could not have
1592 // This means IndVar = t + (-M) for t in [0, L). Hence (IndVar + M) = t.
1593 // Hence 0 <= (IndVar + M) < L
1595 // [^1]: Note that the solution does _not_ apply if L < 0; consider values M =
1596 // 127, IndVar = 126 and L = -2 in an i8 world.
1598 if (!IndVar->isAffine())
1601 const SCEV *A = IndVar->getStart();
1602 const SCEVConstant *B = dyn_cast<SCEVConstant>(IndVar->getStepRecurrence(SE));
1605 assert(!B->isZero() && "Recurrence with zero step?");
1607 const SCEV *C = getOffset();
1608 const SCEVConstant *D = dyn_cast<SCEVConstant>(getScale());
1612 assert(!D->getValue()->isZero() && "Recurrence with zero step?");
1614 const SCEV *M = SE.getMinusSCEV(C, A);
1615 const SCEV *Begin = SE.getNegativeSCEV(M);
1616 const SCEV *UpperLimit = nullptr;
1618 // We strengthen "0 <= I" to "0 <= I < INT_SMAX" and "I < L" to "0 <= I < L".
1619 // We can potentially do much better here.
1620 if (Value *V = getLength()) {
1621 UpperLimit = SE.getSCEV(V);
1623 assert(Kind == InductiveRangeCheck::RANGE_CHECK_LOWER && "invariant!");
1624 unsigned BitWidth = cast<IntegerType>(IndVar->getType())->getBitWidth();
1625 UpperLimit = SE.getConstant(APInt::getSignedMaxValue(BitWidth));
1628 const SCEV *End = SE.getMinusSCEV(UpperLimit, M);
1629 return InductiveRangeCheck::Range(Begin, End);
1632 static Optional<InductiveRangeCheck::Range>
1633 IntersectRange(ScalarEvolution &SE,
1634 const Optional<InductiveRangeCheck::Range> &R1,
1635 const InductiveRangeCheck::Range &R2) {
1638 auto &R1Value = R1.getValue();
1640 // TODO: we could widen the smaller range and have this work; but for now we
1641 // bail out to keep things simple.
1642 if (R1Value.getType() != R2.getType())
1645 const SCEV *NewBegin = SE.getSMaxExpr(R1Value.getBegin(), R2.getBegin());
1646 const SCEV *NewEnd = SE.getSMinExpr(R1Value.getEnd(), R2.getEnd());
1648 return InductiveRangeCheck::Range(NewBegin, NewEnd);
1651 bool InductiveRangeCheckElimination::runOnLoop(Loop *L, LPPassManager &LPM) {
1655 if (L->getBlocks().size() >= LoopSizeCutoff) {
1656 DEBUG(dbgs() << "irce: giving up constraining loop, too large\n";);
1660 BasicBlock *Preheader = L->getLoopPreheader();
1662 DEBUG(dbgs() << "irce: loop has no preheader, leaving\n");
1666 LLVMContext &Context = Preheader->getContext();
1667 SmallVector<InductiveRangeCheck, 16> RangeChecks;
1668 ScalarEvolution &SE = getAnalysis<ScalarEvolutionWrapperPass>().getSE();
1669 BranchProbabilityInfo &BPI =
1670 getAnalysis<BranchProbabilityInfoWrapperPass>().getBPI();
1672 for (auto BBI : L->getBlocks())
1673 if (BranchInst *TBI = dyn_cast<BranchInst>(BBI->getTerminator()))
1674 InductiveRangeCheck::extractRangeChecksFromBranch(TBI, L, SE, BPI,
1677 if (RangeChecks.empty())
1680 auto PrintRecognizedRangeChecks = [&](raw_ostream &OS) {
1681 OS << "irce: looking at loop "; L->print(OS);
1682 OS << "irce: loop has " << RangeChecks.size()
1683 << " inductive range checks: \n";
1684 for (InductiveRangeCheck &IRC : RangeChecks)
1688 DEBUG(PrintRecognizedRangeChecks(dbgs()));
1690 if (PrintRangeChecks)
1691 PrintRecognizedRangeChecks(errs());
1693 const char *FailureReason = nullptr;
1694 Optional<LoopStructure> MaybeLoopStructure =
1695 LoopStructure::parseLoopStructure(SE, BPI, *L, FailureReason);
1696 if (!MaybeLoopStructure.hasValue()) {
1697 DEBUG(dbgs() << "irce: could not parse loop structure: " << FailureReason
1701 LoopStructure LS = MaybeLoopStructure.getValue();
1702 const SCEVAddRecExpr *IndVar =
1703 cast<SCEVAddRecExpr>(SE.getMinusSCEV(SE.getSCEV(LS.IndVarBase), SE.getSCEV(LS.IndVarStep)));
1705 Optional<InductiveRangeCheck::Range> SafeIterRange;
1706 Instruction *ExprInsertPt = Preheader->getTerminator();
1708 SmallVector<InductiveRangeCheck, 4> RangeChecksToEliminate;
1710 IRBuilder<> B(ExprInsertPt);
1711 for (InductiveRangeCheck &IRC : RangeChecks) {
1712 auto Result = IRC.computeSafeIterationSpace(SE, IndVar);
1713 if (Result.hasValue()) {
1714 auto MaybeSafeIterRange =
1715 IntersectRange(SE, SafeIterRange, Result.getValue());
1716 if (MaybeSafeIterRange.hasValue()) {
1717 RangeChecksToEliminate.push_back(IRC);
1718 SafeIterRange = MaybeSafeIterRange.getValue();
1723 if (!SafeIterRange.hasValue())
1726 auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
1727 LoopConstrainer LC(*L, getAnalysis<LoopInfoWrapperPass>().getLoopInfo(), LPM,
1728 LS, SE, DT, SafeIterRange.getValue());
1729 bool Changed = LC.run();
1732 auto PrintConstrainedLoopInfo = [L]() {
1733 dbgs() << "irce: in function ";
1734 dbgs() << L->getHeader()->getParent()->getName() << ": ";
1735 dbgs() << "constrained ";
1739 DEBUG(PrintConstrainedLoopInfo());
1741 if (PrintChangedLoops)
1742 PrintConstrainedLoopInfo();
1744 // Optimize away the now-redundant range checks.
1746 for (InductiveRangeCheck &IRC : RangeChecksToEliminate) {
1747 ConstantInt *FoldedRangeCheck = IRC.getPassingDirection()
1748 ? ConstantInt::getTrue(Context)
1749 : ConstantInt::getFalse(Context);
1750 IRC.getCheckUse()->set(FoldedRangeCheck);
1757 Pass *llvm::createInductiveRangeCheckEliminationPass() {
1758 return new InductiveRangeCheckElimination;