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 //===----------------------------------------------------------------------===//
10 // The InductiveRangeCheckElimination pass splits a loop's iteration space into
11 // three disjoint ranges. It does that in a way such that the loop running in
12 // the middle loop provably does not need range checks. As an example, it will
15 // len = < known positive >
16 // for (i = 0; i < n; i++) {
17 // if (0 <= i && i < len) {
20 // throw_out_of_bounds();
26 // len = < known positive >
27 // limit = smin(n, len)
28 // // no first segment
29 // for (i = 0; i < limit; i++) {
30 // if (0 <= i && i < len) { // this check is fully redundant
33 // throw_out_of_bounds();
36 // for (i = limit; i < n; i++) {
37 // if (0 <= i && i < len) {
40 // throw_out_of_bounds();
44 //===----------------------------------------------------------------------===//
46 #include "llvm/ADT/APInt.h"
47 #include "llvm/ADT/ArrayRef.h"
48 #include "llvm/ADT/None.h"
49 #include "llvm/ADT/Optional.h"
50 #include "llvm/ADT/SmallPtrSet.h"
51 #include "llvm/ADT/SmallVector.h"
52 #include "llvm/ADT/StringRef.h"
53 #include "llvm/ADT/Twine.h"
54 #include "llvm/Analysis/BranchProbabilityInfo.h"
55 #include "llvm/Analysis/LoopInfo.h"
56 #include "llvm/Analysis/LoopPass.h"
57 #include "llvm/Analysis/ScalarEvolution.h"
58 #include "llvm/Analysis/ScalarEvolutionExpander.h"
59 #include "llvm/Analysis/ScalarEvolutionExpressions.h"
60 #include "llvm/IR/BasicBlock.h"
61 #include "llvm/IR/CFG.h"
62 #include "llvm/IR/Constants.h"
63 #include "llvm/IR/DerivedTypes.h"
64 #include "llvm/IR/Dominators.h"
65 #include "llvm/IR/Function.h"
66 #include "llvm/IR/IRBuilder.h"
67 #include "llvm/IR/InstrTypes.h"
68 #include "llvm/IR/Instructions.h"
69 #include "llvm/IR/Metadata.h"
70 #include "llvm/IR/Module.h"
71 #include "llvm/IR/PatternMatch.h"
72 #include "llvm/IR/Type.h"
73 #include "llvm/IR/Use.h"
74 #include "llvm/IR/User.h"
75 #include "llvm/IR/Value.h"
76 #include "llvm/Pass.h"
77 #include "llvm/Support/BranchProbability.h"
78 #include "llvm/Support/Casting.h"
79 #include "llvm/Support/CommandLine.h"
80 #include "llvm/Support/Compiler.h"
81 #include "llvm/Support/Debug.h"
82 #include "llvm/Support/ErrorHandling.h"
83 #include "llvm/Support/raw_ostream.h"
84 #include "llvm/Transforms/Scalar.h"
85 #include "llvm/Transforms/Utils/Cloning.h"
86 #include "llvm/Transforms/Utils/LoopSimplify.h"
87 #include "llvm/Transforms/Utils/LoopUtils.h"
88 #include "llvm/Transforms/Utils/ValueMapper.h"
97 using namespace llvm::PatternMatch;
99 static cl::opt<unsigned> LoopSizeCutoff("irce-loop-size-cutoff", cl::Hidden,
102 static cl::opt<bool> PrintChangedLoops("irce-print-changed-loops", cl::Hidden,
105 static cl::opt<bool> PrintRangeChecks("irce-print-range-checks", cl::Hidden,
108 static cl::opt<int> MaxExitProbReciprocal("irce-max-exit-prob-reciprocal",
109 cl::Hidden, cl::init(10));
111 static cl::opt<bool> SkipProfitabilityChecks("irce-skip-profitability-checks",
112 cl::Hidden, cl::init(false));
114 static cl::opt<bool> AllowUnsignedLatchCondition("irce-allow-unsigned-latch",
115 cl::Hidden, cl::init(true));
117 static const char *ClonedLoopTag = "irce.loop.clone";
119 #define DEBUG_TYPE "irce"
123 /// An inductive range check is conditional branch in a loop with
125 /// 1. a very cold successor (i.e. the branch jumps to that successor very
130 /// 2. a condition that is provably true for some contiguous range of values
131 /// taken by the containing loop's induction variable.
133 class InductiveRangeCheck {
134 // Classifies a range check
135 enum RangeCheckKind : unsigned {
136 // Range check of the form "0 <= I".
137 RANGE_CHECK_LOWER = 1,
139 // Range check of the form "I < L" where L is known positive.
140 RANGE_CHECK_UPPER = 2,
142 // The logical and of the RANGE_CHECK_LOWER and RANGE_CHECK_UPPER
144 RANGE_CHECK_BOTH = RANGE_CHECK_LOWER | RANGE_CHECK_UPPER,
146 // Unrecognized range check condition.
147 RANGE_CHECK_UNKNOWN = (unsigned)-1
150 static StringRef rangeCheckKindToStr(RangeCheckKind);
152 const SCEV *Begin = nullptr;
153 const SCEV *Step = nullptr;
154 const SCEV *End = nullptr;
155 Use *CheckUse = nullptr;
156 RangeCheckKind Kind = RANGE_CHECK_UNKNOWN;
157 bool IsSigned = true;
159 static RangeCheckKind parseRangeCheckICmp(Loop *L, ICmpInst *ICI,
160 ScalarEvolution &SE, Value *&Index,
161 Value *&Length, bool &IsSigned);
164 extractRangeChecksFromCond(Loop *L, ScalarEvolution &SE, Use &ConditionUse,
165 SmallVectorImpl<InductiveRangeCheck> &Checks,
166 SmallPtrSetImpl<Value *> &Visited);
169 const SCEV *getBegin() const { return Begin; }
170 const SCEV *getStep() const { return Step; }
171 const SCEV *getEnd() const { return End; }
172 bool isSigned() const { return IsSigned; }
174 void print(raw_ostream &OS) const {
175 OS << "InductiveRangeCheck:\n";
176 OS << " Kind: " << rangeCheckKindToStr(Kind) << "\n";
186 OS << "\n CheckUse: ";
187 getCheckUse()->getUser()->print(OS);
188 OS << " Operand: " << getCheckUse()->getOperandNo() << "\n";
196 Use *getCheckUse() const { return CheckUse; }
198 /// Represents an signed integer range [Range.getBegin(), Range.getEnd()). If
199 /// R.getEnd() sle R.getBegin(), then R denotes the empty range.
206 Range(const SCEV *Begin, const SCEV *End) : Begin(Begin), End(End) {
207 assert(Begin->getType() == End->getType() && "ill-typed range!");
210 Type *getType() const { return Begin->getType(); }
211 const SCEV *getBegin() const { return Begin; }
212 const SCEV *getEnd() const { return End; }
213 bool isEmpty(ScalarEvolution &SE, bool IsSigned) const {
217 return SE.isKnownPredicate(ICmpInst::ICMP_SGE, Begin, End);
219 return SE.isKnownPredicate(ICmpInst::ICMP_UGE, Begin, End);
223 /// This is the value the condition of the branch needs to evaluate to for the
224 /// branch to take the hot successor (see (1) above).
225 bool getPassingDirection() { return true; }
227 /// Computes a range for the induction variable (IndVar) in which the range
228 /// check is redundant and can be constant-folded away. The induction
229 /// variable is not required to be the canonical {0,+,1} induction variable.
230 Optional<Range> computeSafeIterationSpace(ScalarEvolution &SE,
231 const SCEVAddRecExpr *IndVar,
232 bool IsLatchSigned) const;
234 /// Parse out a set of inductive range checks from \p BI and append them to \p
237 /// NB! There may be conditions feeding into \p BI that aren't inductive range
238 /// checks, and hence don't end up in \p Checks.
240 extractRangeChecksFromBranch(BranchInst *BI, Loop *L, ScalarEvolution &SE,
241 BranchProbabilityInfo &BPI,
242 SmallVectorImpl<InductiveRangeCheck> &Checks);
245 class InductiveRangeCheckElimination : public LoopPass {
249 InductiveRangeCheckElimination() : LoopPass(ID) {
250 initializeInductiveRangeCheckEliminationPass(
251 *PassRegistry::getPassRegistry());
254 void getAnalysisUsage(AnalysisUsage &AU) const override {
255 AU.addRequired<BranchProbabilityInfoWrapperPass>();
256 getLoopAnalysisUsage(AU);
259 bool runOnLoop(Loop *L, LPPassManager &LPM) override;
262 } // end anonymous namespace
264 char InductiveRangeCheckElimination::ID = 0;
266 INITIALIZE_PASS_BEGIN(InductiveRangeCheckElimination, "irce",
267 "Inductive range check elimination", false, false)
268 INITIALIZE_PASS_DEPENDENCY(BranchProbabilityInfoWrapperPass)
269 INITIALIZE_PASS_DEPENDENCY(LoopPass)
270 INITIALIZE_PASS_END(InductiveRangeCheckElimination, "irce",
271 "Inductive range check elimination", false, false)
273 StringRef InductiveRangeCheck::rangeCheckKindToStr(
274 InductiveRangeCheck::RangeCheckKind RCK) {
276 case InductiveRangeCheck::RANGE_CHECK_UNKNOWN:
277 return "RANGE_CHECK_UNKNOWN";
279 case InductiveRangeCheck::RANGE_CHECK_UPPER:
280 return "RANGE_CHECK_UPPER";
282 case InductiveRangeCheck::RANGE_CHECK_LOWER:
283 return "RANGE_CHECK_LOWER";
285 case InductiveRangeCheck::RANGE_CHECK_BOTH:
286 return "RANGE_CHECK_BOTH";
289 llvm_unreachable("unknown range check type!");
292 /// Parse a single ICmp instruction, `ICI`, into a range check. If `ICI` cannot
293 /// be interpreted as a range check, return `RANGE_CHECK_UNKNOWN` and set
294 /// `Index` and `Length` to `nullptr`. Otherwise set `Index` to the value being
295 /// range checked, and set `Length` to the upper limit `Index` is being range
296 /// checked with if (and only if) the range check type is stronger or equal to
297 /// RANGE_CHECK_UPPER.
298 InductiveRangeCheck::RangeCheckKind
299 InductiveRangeCheck::parseRangeCheckICmp(Loop *L, ICmpInst *ICI,
300 ScalarEvolution &SE, Value *&Index,
301 Value *&Length, bool &IsSigned) {
302 auto IsNonNegativeAndNotLoopVarying = [&SE, L](Value *V) {
303 const SCEV *S = SE.getSCEV(V);
304 if (isa<SCEVCouldNotCompute>(S))
307 return SE.getLoopDisposition(S, L) == ScalarEvolution::LoopInvariant &&
308 SE.isKnownNonNegative(S);
311 ICmpInst::Predicate Pred = ICI->getPredicate();
312 Value *LHS = ICI->getOperand(0);
313 Value *RHS = ICI->getOperand(1);
317 return RANGE_CHECK_UNKNOWN;
319 case ICmpInst::ICMP_SLE:
322 case ICmpInst::ICMP_SGE:
324 if (match(RHS, m_ConstantInt<0>())) {
326 return RANGE_CHECK_LOWER;
328 return RANGE_CHECK_UNKNOWN;
330 case ICmpInst::ICMP_SLT:
333 case ICmpInst::ICMP_SGT:
335 if (match(RHS, m_ConstantInt<-1>())) {
337 return RANGE_CHECK_LOWER;
340 if (IsNonNegativeAndNotLoopVarying(LHS)) {
343 return RANGE_CHECK_UPPER;
345 return RANGE_CHECK_UNKNOWN;
347 case ICmpInst::ICMP_ULT:
350 case ICmpInst::ICMP_UGT:
352 if (IsNonNegativeAndNotLoopVarying(LHS)) {
355 return RANGE_CHECK_BOTH;
357 return RANGE_CHECK_UNKNOWN;
360 llvm_unreachable("default clause returns!");
363 void InductiveRangeCheck::extractRangeChecksFromCond(
364 Loop *L, ScalarEvolution &SE, Use &ConditionUse,
365 SmallVectorImpl<InductiveRangeCheck> &Checks,
366 SmallPtrSetImpl<Value *> &Visited) {
367 Value *Condition = ConditionUse.get();
368 if (!Visited.insert(Condition).second)
371 // TODO: Do the same for OR, XOR, NOT etc?
372 if (match(Condition, m_And(m_Value(), m_Value()))) {
373 extractRangeChecksFromCond(L, SE, cast<User>(Condition)->getOperandUse(0),
375 extractRangeChecksFromCond(L, SE, cast<User>(Condition)->getOperandUse(1),
380 ICmpInst *ICI = dyn_cast<ICmpInst>(Condition);
384 Value *Length = nullptr, *Index;
386 auto RCKind = parseRangeCheckICmp(L, ICI, SE, Index, Length, IsSigned);
387 if (RCKind == InductiveRangeCheck::RANGE_CHECK_UNKNOWN)
390 const auto *IndexAddRec = dyn_cast<SCEVAddRecExpr>(SE.getSCEV(Index));
392 IndexAddRec && (IndexAddRec->getLoop() == L) && IndexAddRec->isAffine();
397 InductiveRangeCheck IRC;
398 IRC.End = Length ? SE.getSCEV(Length) : nullptr;
399 IRC.Begin = IndexAddRec->getStart();
400 IRC.Step = IndexAddRec->getStepRecurrence(SE);
401 IRC.CheckUse = &ConditionUse;
403 IRC.IsSigned = IsSigned;
404 Checks.push_back(IRC);
407 void InductiveRangeCheck::extractRangeChecksFromBranch(
408 BranchInst *BI, Loop *L, ScalarEvolution &SE, BranchProbabilityInfo &BPI,
409 SmallVectorImpl<InductiveRangeCheck> &Checks) {
410 if (BI->isUnconditional() || BI->getParent() == L->getLoopLatch())
413 BranchProbability LikelyTaken(15, 16);
415 if (!SkipProfitabilityChecks &&
416 BPI.getEdgeProbability(BI->getParent(), (unsigned)0) < LikelyTaken)
419 SmallPtrSet<Value *, 8> Visited;
420 InductiveRangeCheck::extractRangeChecksFromCond(L, SE, BI->getOperandUse(0),
424 // Add metadata to the loop L to disable loop optimizations. Callers need to
425 // confirm that optimizing loop L is not beneficial.
426 static void DisableAllLoopOptsOnLoop(Loop &L) {
427 // We do not care about any existing loopID related metadata for L, since we
428 // are setting all loop metadata to false.
429 LLVMContext &Context = L.getHeader()->getContext();
430 // Reserve first location for self reference to the LoopID metadata node.
431 MDNode *Dummy = MDNode::get(Context, {});
432 MDNode *DisableUnroll = MDNode::get(
433 Context, {MDString::get(Context, "llvm.loop.unroll.disable")});
435 ConstantAsMetadata::get(ConstantInt::get(Type::getInt1Ty(Context), 0));
436 MDNode *DisableVectorize = MDNode::get(
438 {MDString::get(Context, "llvm.loop.vectorize.enable"), FalseVal});
439 MDNode *DisableLICMVersioning = MDNode::get(
440 Context, {MDString::get(Context, "llvm.loop.licm_versioning.disable")});
441 MDNode *DisableDistribution= MDNode::get(
443 {MDString::get(Context, "llvm.loop.distribute.enable"), FalseVal});
445 MDNode::get(Context, {Dummy, DisableUnroll, DisableVectorize,
446 DisableLICMVersioning, DisableDistribution});
447 // Set operand 0 to refer to the loop id itself.
448 NewLoopID->replaceOperandWith(0, NewLoopID);
449 L.setLoopID(NewLoopID);
454 // Keeps track of the structure of a loop. This is similar to llvm::Loop,
455 // except that it is more lightweight and can track the state of a loop through
456 // changing and potentially invalid IR. This structure also formalizes the
457 // kinds of loops we can deal with -- ones that have a single latch that is also
458 // an exiting block *and* have a canonical induction variable.
459 struct LoopStructure {
460 const char *Tag = "";
462 BasicBlock *Header = nullptr;
463 BasicBlock *Latch = nullptr;
465 // `Latch's terminator instruction is `LatchBr', and it's `LatchBrExitIdx'th
466 // successor is `LatchExit', the exit block of the loop.
467 BranchInst *LatchBr = nullptr;
468 BasicBlock *LatchExit = nullptr;
469 unsigned LatchBrExitIdx = std::numeric_limits<unsigned>::max();
471 // The loop represented by this instance of LoopStructure is semantically
474 // intN_ty inc = IndVarIncreasing ? 1 : -1;
475 // pred_ty predicate = IndVarIncreasing ? ICMP_SLT : ICMP_SGT;
477 // for (intN_ty iv = IndVarStart; predicate(iv, LoopExitAt); iv = IndVarBase)
480 Value *IndVarBase = nullptr;
481 Value *IndVarStart = nullptr;
482 Value *IndVarStep = nullptr;
483 Value *LoopExitAt = nullptr;
484 bool IndVarIncreasing = false;
485 bool IsSignedPredicate = true;
487 LoopStructure() = default;
489 template <typename M> LoopStructure map(M Map) const {
490 LoopStructure Result;
492 Result.Header = cast<BasicBlock>(Map(Header));
493 Result.Latch = cast<BasicBlock>(Map(Latch));
494 Result.LatchBr = cast<BranchInst>(Map(LatchBr));
495 Result.LatchExit = cast<BasicBlock>(Map(LatchExit));
496 Result.LatchBrExitIdx = LatchBrExitIdx;
497 Result.IndVarBase = Map(IndVarBase);
498 Result.IndVarStart = Map(IndVarStart);
499 Result.IndVarStep = Map(IndVarStep);
500 Result.LoopExitAt = Map(LoopExitAt);
501 Result.IndVarIncreasing = IndVarIncreasing;
502 Result.IsSignedPredicate = IsSignedPredicate;
506 static Optional<LoopStructure> parseLoopStructure(ScalarEvolution &,
507 BranchProbabilityInfo &BPI,
512 /// This class is used to constrain loops to run within a given iteration space.
513 /// The algorithm this class implements is given a Loop and a range [Begin,
514 /// End). The algorithm then tries to break out a "main loop" out of the loop
515 /// it is given in a way that the "main loop" runs with the induction variable
516 /// in a subset of [Begin, End). The algorithm emits appropriate pre and post
517 /// loops to run any remaining iterations. The pre loop runs any iterations in
518 /// which the induction variable is < Begin, and the post loop runs any
519 /// iterations in which the induction variable is >= End.
520 class LoopConstrainer {
521 // The representation of a clone of the original loop we started out with.
524 std::vector<BasicBlock *> Blocks;
526 // `Map` maps values in the clonee into values in the cloned version
527 ValueToValueMapTy Map;
529 // An instance of `LoopStructure` for the cloned loop
530 LoopStructure Structure;
533 // Result of rewriting the range of a loop. See changeIterationSpaceEnd for
534 // more details on what these fields mean.
535 struct RewrittenRangeInfo {
536 BasicBlock *PseudoExit = nullptr;
537 BasicBlock *ExitSelector = nullptr;
538 std::vector<PHINode *> PHIValuesAtPseudoExit;
539 PHINode *IndVarEnd = nullptr;
541 RewrittenRangeInfo() = default;
544 // Calculated subranges we restrict the iteration space of the main loop to.
545 // See the implementation of `calculateSubRanges' for more details on how
546 // these fields are computed. `LowLimit` is None if there is no restriction
547 // on low end of the restricted iteration space of the main loop. `HighLimit`
548 // is None if there is no restriction on high end of the restricted iteration
549 // space of the main loop.
552 Optional<const SCEV *> LowLimit;
553 Optional<const SCEV *> HighLimit;
556 // A utility function that does a `replaceUsesOfWith' on the incoming block
557 // set of a `PHINode' -- replaces instances of `Block' in the `PHINode's
558 // incoming block list with `ReplaceBy'.
559 static void replacePHIBlock(PHINode *PN, BasicBlock *Block,
560 BasicBlock *ReplaceBy);
562 // Compute a safe set of limits for the main loop to run in -- effectively the
563 // intersection of `Range' and the iteration space of the original loop.
564 // Return None if unable to compute the set of subranges.
565 Optional<SubRanges> calculateSubRanges(bool IsSignedPredicate) const;
567 // Clone `OriginalLoop' and return the result in CLResult. The IR after
568 // running `cloneLoop' is well formed except for the PHI nodes in CLResult --
569 // the PHI nodes say that there is an incoming edge from `OriginalPreheader`
570 // but there is no such edge.
571 void cloneLoop(ClonedLoop &CLResult, const char *Tag) const;
573 // Create the appropriate loop structure needed to describe a cloned copy of
574 // `Original`. The clone is described by `VM`.
575 Loop *createClonedLoopStructure(Loop *Original, Loop *Parent,
576 ValueToValueMapTy &VM);
578 // Rewrite the iteration space of the loop denoted by (LS, Preheader). The
579 // iteration space of the rewritten loop ends at ExitLoopAt. The start of the
580 // iteration space is not changed. `ExitLoopAt' is assumed to be slt
581 // `OriginalHeaderCount'.
583 // If there are iterations left to execute, control is made to jump to
584 // `ContinuationBlock', otherwise they take the normal loop exit. The
585 // returned `RewrittenRangeInfo' object is populated as follows:
587 // .PseudoExit is a basic block that unconditionally branches to
588 // `ContinuationBlock'.
590 // .ExitSelector is a basic block that decides, on exit from the loop,
591 // whether to branch to the "true" exit or to `PseudoExit'.
593 // .PHIValuesAtPseudoExit are PHINodes in `PseudoExit' that compute the value
594 // for each PHINode in the loop header on taking the pseudo exit.
596 // After changeIterationSpaceEnd, `Preheader' is no longer a legitimate
597 // preheader because it is made to branch to the loop header only
600 changeIterationSpaceEnd(const LoopStructure &LS, BasicBlock *Preheader,
602 BasicBlock *ContinuationBlock) const;
604 // The loop denoted by `LS' has `OldPreheader' as its preheader. This
605 // function creates a new preheader for `LS' and returns it.
606 BasicBlock *createPreheader(const LoopStructure &LS, BasicBlock *OldPreheader,
607 const char *Tag) const;
609 // `ContinuationBlockAndPreheader' was the continuation block for some call to
610 // `changeIterationSpaceEnd' and is the preheader to the loop denoted by `LS'.
611 // This function rewrites the PHI nodes in `LS.Header' to start with the
613 void rewriteIncomingValuesForPHIs(
614 LoopStructure &LS, BasicBlock *ContinuationBlockAndPreheader,
615 const LoopConstrainer::RewrittenRangeInfo &RRI) const;
617 // Even though we do not preserve any passes at this time, we at least need to
618 // keep the parent loop structure consistent. The `LPPassManager' seems to
619 // verify this after running a loop pass. This function adds the list of
620 // blocks denoted by BBs to this loops parent loop if required.
621 void addToParentLoopIfNeeded(ArrayRef<BasicBlock *> BBs);
623 // Some global state.
631 // Information about the original loop we started out with.
634 const SCEV *LatchTakenCount = nullptr;
635 BasicBlock *OriginalPreheader = nullptr;
637 // The preheader of the main loop. This may or may not be different from
638 // `OriginalPreheader'.
639 BasicBlock *MainLoopPreheader = nullptr;
641 // The range we need to run the main loop in.
642 InductiveRangeCheck::Range Range;
644 // The structure of the main loop (see comment at the beginning of this class
646 LoopStructure MainLoopStructure;
649 LoopConstrainer(Loop &L, LoopInfo &LI, LPPassManager &LPM,
650 const LoopStructure &LS, ScalarEvolution &SE,
651 DominatorTree &DT, InductiveRangeCheck::Range R)
652 : F(*L.getHeader()->getParent()), Ctx(L.getHeader()->getContext()),
653 SE(SE), DT(DT), LPM(LPM), LI(LI), OriginalLoop(L), Range(R),
654 MainLoopStructure(LS) {}
656 // Entry point for the algorithm. Returns true on success.
660 } // end anonymous namespace
662 void LoopConstrainer::replacePHIBlock(PHINode *PN, BasicBlock *Block,
663 BasicBlock *ReplaceBy) {
664 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
665 if (PN->getIncomingBlock(i) == Block)
666 PN->setIncomingBlock(i, ReplaceBy);
669 static bool CanBeMax(ScalarEvolution &SE, const SCEV *S, bool Signed) {
671 APInt::getSignedMaxValue(cast<IntegerType>(S->getType())->getBitWidth()) :
672 APInt::getMaxValue(cast<IntegerType>(S->getType())->getBitWidth());
673 return SE.getSignedRange(S).contains(Max) &&
674 SE.getUnsignedRange(S).contains(Max);
677 static bool SumCanReachMax(ScalarEvolution &SE, const SCEV *S1, const SCEV *S2,
679 // S1 < INT_MAX - S2 ===> S1 + S2 < INT_MAX.
680 assert(SE.isKnownNonNegative(S2) &&
681 "We expected the 2nd arg to be non-negative!");
682 const SCEV *Max = SE.getConstant(
683 Signed ? APInt::getSignedMaxValue(
684 cast<IntegerType>(S1->getType())->getBitWidth())
685 : APInt::getMaxValue(
686 cast<IntegerType>(S1->getType())->getBitWidth()));
687 const SCEV *CapForS1 = SE.getMinusSCEV(Max, S2);
688 return !SE.isKnownPredicate(Signed ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT,
692 static bool CanBeMin(ScalarEvolution &SE, const SCEV *S, bool Signed) {
694 APInt::getSignedMinValue(cast<IntegerType>(S->getType())->getBitWidth()) :
695 APInt::getMinValue(cast<IntegerType>(S->getType())->getBitWidth());
696 return SE.getSignedRange(S).contains(Min) &&
697 SE.getUnsignedRange(S).contains(Min);
700 static bool SumCanReachMin(ScalarEvolution &SE, const SCEV *S1, const SCEV *S2,
702 // S1 > INT_MIN - S2 ===> S1 + S2 > INT_MIN.
703 assert(SE.isKnownNonPositive(S2) &&
704 "We expected the 2nd arg to be non-positive!");
705 const SCEV *Max = SE.getConstant(
706 Signed ? APInt::getSignedMinValue(
707 cast<IntegerType>(S1->getType())->getBitWidth())
708 : APInt::getMinValue(
709 cast<IntegerType>(S1->getType())->getBitWidth()));
710 const SCEV *CapForS1 = SE.getMinusSCEV(Max, S2);
711 return !SE.isKnownPredicate(Signed ? ICmpInst::ICMP_SGT : ICmpInst::ICMP_UGT,
715 Optional<LoopStructure>
716 LoopStructure::parseLoopStructure(ScalarEvolution &SE,
717 BranchProbabilityInfo &BPI,
718 Loop &L, const char *&FailureReason) {
719 if (!L.isLoopSimplifyForm()) {
720 FailureReason = "loop not in LoopSimplify form";
724 BasicBlock *Latch = L.getLoopLatch();
725 assert(Latch && "Simplified loops only have one latch!");
727 if (Latch->getTerminator()->getMetadata(ClonedLoopTag)) {
728 FailureReason = "loop has already been cloned";
732 if (!L.isLoopExiting(Latch)) {
733 FailureReason = "no loop latch";
737 BasicBlock *Header = L.getHeader();
738 BasicBlock *Preheader = L.getLoopPreheader();
740 FailureReason = "no preheader";
744 BranchInst *LatchBr = dyn_cast<BranchInst>(Latch->getTerminator());
745 if (!LatchBr || LatchBr->isUnconditional()) {
746 FailureReason = "latch terminator not conditional branch";
750 unsigned LatchBrExitIdx = LatchBr->getSuccessor(0) == Header ? 1 : 0;
752 BranchProbability ExitProbability =
753 BPI.getEdgeProbability(LatchBr->getParent(), LatchBrExitIdx);
755 if (!SkipProfitabilityChecks &&
756 ExitProbability > BranchProbability(1, MaxExitProbReciprocal)) {
757 FailureReason = "short running loop, not profitable";
761 ICmpInst *ICI = dyn_cast<ICmpInst>(LatchBr->getCondition());
762 if (!ICI || !isa<IntegerType>(ICI->getOperand(0)->getType())) {
763 FailureReason = "latch terminator branch not conditional on integral icmp";
767 const SCEV *LatchCount = SE.getExitCount(&L, Latch);
768 if (isa<SCEVCouldNotCompute>(LatchCount)) {
769 FailureReason = "could not compute latch count";
773 ICmpInst::Predicate Pred = ICI->getPredicate();
774 Value *LeftValue = ICI->getOperand(0);
775 const SCEV *LeftSCEV = SE.getSCEV(LeftValue);
776 IntegerType *IndVarTy = cast<IntegerType>(LeftValue->getType());
778 Value *RightValue = ICI->getOperand(1);
779 const SCEV *RightSCEV = SE.getSCEV(RightValue);
781 // We canonicalize `ICI` such that `LeftSCEV` is an add recurrence.
782 if (!isa<SCEVAddRecExpr>(LeftSCEV)) {
783 if (isa<SCEVAddRecExpr>(RightSCEV)) {
784 std::swap(LeftSCEV, RightSCEV);
785 std::swap(LeftValue, RightValue);
786 Pred = ICmpInst::getSwappedPredicate(Pred);
788 FailureReason = "no add recurrences in the icmp";
793 auto HasNoSignedWrap = [&](const SCEVAddRecExpr *AR) {
794 if (AR->getNoWrapFlags(SCEV::FlagNSW))
797 IntegerType *Ty = cast<IntegerType>(AR->getType());
798 IntegerType *WideTy =
799 IntegerType::get(Ty->getContext(), Ty->getBitWidth() * 2);
801 const SCEVAddRecExpr *ExtendAfterOp =
802 dyn_cast<SCEVAddRecExpr>(SE.getSignExtendExpr(AR, WideTy));
804 const SCEV *ExtendedStart = SE.getSignExtendExpr(AR->getStart(), WideTy);
805 const SCEV *ExtendedStep =
806 SE.getSignExtendExpr(AR->getStepRecurrence(SE), WideTy);
808 bool NoSignedWrap = ExtendAfterOp->getStart() == ExtendedStart &&
809 ExtendAfterOp->getStepRecurrence(SE) == ExtendedStep;
815 // We may have proved this when computing the sign extension above.
816 return AR->getNoWrapFlags(SCEV::FlagNSW) != SCEV::FlagAnyWrap;
819 // Here we check whether the suggested AddRec is an induction variable that
820 // can be handled (i.e. with known constant step), and if yes, calculate its
821 // step and identify whether it is increasing or decreasing.
822 auto IsInductionVar = [&](const SCEVAddRecExpr *AR, bool &IsIncreasing,
823 ConstantInt *&StepCI) {
827 // Currently we only work with induction variables that have been proved to
828 // not wrap. This restriction can potentially be lifted in the future.
830 if (!HasNoSignedWrap(AR))
833 if (const SCEVConstant *StepExpr =
834 dyn_cast<SCEVConstant>(AR->getStepRecurrence(SE))) {
835 StepCI = StepExpr->getValue();
836 assert(!StepCI->isZero() && "Zero step?");
837 IsIncreasing = !StepCI->isNegative();
844 // `ICI` is interpreted as taking the backedge if the *next* value of the
845 // induction variable satisfies some constraint.
847 const SCEVAddRecExpr *IndVarBase = cast<SCEVAddRecExpr>(LeftSCEV);
848 bool IsIncreasing = false;
849 bool IsSignedPredicate = true;
851 if (!IsInductionVar(IndVarBase, IsIncreasing, StepCI)) {
852 FailureReason = "LHS in icmp not induction variable";
856 const SCEV *StartNext = IndVarBase->getStart();
857 const SCEV *Addend = SE.getNegativeSCEV(IndVarBase->getStepRecurrence(SE));
858 const SCEV *IndVarStart = SE.getAddExpr(StartNext, Addend);
859 const SCEV *Step = SE.getSCEV(StepCI);
861 ConstantInt *One = ConstantInt::get(IndVarTy, 1);
863 bool DecreasedRightValueByOne = false;
864 if (StepCI->isOne()) {
865 // Try to turn eq/ne predicates to those we can work with.
866 if (Pred == ICmpInst::ICMP_NE && LatchBrExitIdx == 1)
867 // while (++i != len) { while (++i < len) {
870 // If both parts are known non-negative, it is profitable to use
871 // unsigned comparison in increasing loop. This allows us to make the
872 // comparison check against "RightSCEV + 1" more optimistic.
873 if (SE.isKnownNonNegative(IndVarStart) &&
874 SE.isKnownNonNegative(RightSCEV))
875 Pred = ICmpInst::ICMP_ULT;
877 Pred = ICmpInst::ICMP_SLT;
878 else if (Pred == ICmpInst::ICMP_EQ && LatchBrExitIdx == 0 &&
879 !CanBeMin(SE, RightSCEV, /* IsSignedPredicate */ true)) {
880 // while (true) { while (true) {
881 // if (++i == len) ---> if (++i > len - 1)
885 // TODO: Insert ICMP_UGT if both are non-negative?
886 Pred = ICmpInst::ICMP_SGT;
887 RightSCEV = SE.getMinusSCEV(RightSCEV, SE.getOne(RightSCEV->getType()));
888 DecreasedRightValueByOne = true;
892 bool LTPred = (Pred == ICmpInst::ICMP_SLT || Pred == ICmpInst::ICMP_ULT);
893 bool GTPred = (Pred == ICmpInst::ICMP_SGT || Pred == ICmpInst::ICMP_UGT);
894 bool FoundExpectedPred =
895 (LTPred && LatchBrExitIdx == 1) || (GTPred && LatchBrExitIdx == 0);
897 if (!FoundExpectedPred) {
898 FailureReason = "expected icmp slt semantically, found something else";
903 Pred == ICmpInst::ICMP_SLT || Pred == ICmpInst::ICMP_SGT;
905 if (!IsSignedPredicate && !AllowUnsignedLatchCondition) {
906 FailureReason = "unsigned latch conditions are explicitly prohibited";
910 // The predicate that we need to check that the induction variable lies
912 ICmpInst::Predicate BoundPred =
913 IsSignedPredicate ? CmpInst::ICMP_SLT : CmpInst::ICMP_ULT;
915 if (LatchBrExitIdx == 0) {
916 const SCEV *StepMinusOne = SE.getMinusSCEV(Step,
917 SE.getOne(Step->getType()));
918 if (SumCanReachMax(SE, RightSCEV, StepMinusOne, IsSignedPredicate)) {
919 // TODO: this restriction is easily removable -- we just have to
920 // remember that the icmp was an slt and not an sle.
921 FailureReason = "limit may overflow when coercing le to lt";
925 if (!SE.isLoopEntryGuardedByCond(
926 &L, BoundPred, IndVarStart,
927 SE.getAddExpr(RightSCEV, Step))) {
928 FailureReason = "Induction variable start not bounded by upper limit";
932 // We need to increase the right value unless we have already decreased
933 // it virtually when we replaced EQ with SGT.
934 if (!DecreasedRightValueByOne) {
935 IRBuilder<> B(Preheader->getTerminator());
936 RightValue = B.CreateAdd(RightValue, One);
939 if (!SE.isLoopEntryGuardedByCond(&L, BoundPred, IndVarStart, RightSCEV)) {
940 FailureReason = "Induction variable start not bounded by upper limit";
943 assert(!DecreasedRightValueByOne &&
944 "Right value can be decreased only for LatchBrExitIdx == 0!");
947 bool IncreasedRightValueByOne = false;
948 if (StepCI->isMinusOne()) {
949 // Try to turn eq/ne predicates to those we can work with.
950 if (Pred == ICmpInst::ICMP_NE && LatchBrExitIdx == 1)
951 // while (--i != len) { while (--i > len) {
954 // We intentionally don't turn the predicate into UGT even if we know
955 // that both operands are non-negative, because it will only pessimize
956 // our check against "RightSCEV - 1".
957 Pred = ICmpInst::ICMP_SGT;
958 else if (Pred == ICmpInst::ICMP_EQ && LatchBrExitIdx == 0 &&
959 !CanBeMax(SE, RightSCEV, /* IsSignedPredicate */ true)) {
960 // while (true) { while (true) {
961 // if (--i == len) ---> if (--i < len + 1)
965 // TODO: Insert ICMP_ULT if both are non-negative?
966 Pred = ICmpInst::ICMP_SLT;
967 RightSCEV = SE.getAddExpr(RightSCEV, SE.getOne(RightSCEV->getType()));
968 IncreasedRightValueByOne = true;
972 bool LTPred = (Pred == ICmpInst::ICMP_SLT || Pred == ICmpInst::ICMP_ULT);
973 bool GTPred = (Pred == ICmpInst::ICMP_SGT || Pred == ICmpInst::ICMP_UGT);
975 bool FoundExpectedPred =
976 (GTPred && LatchBrExitIdx == 1) || (LTPred && LatchBrExitIdx == 0);
978 if (!FoundExpectedPred) {
979 FailureReason = "expected icmp sgt semantically, found something else";
984 Pred == ICmpInst::ICMP_SLT || Pred == ICmpInst::ICMP_SGT;
986 if (!IsSignedPredicate && !AllowUnsignedLatchCondition) {
987 FailureReason = "unsigned latch conditions are explicitly prohibited";
991 // The predicate that we need to check that the induction variable lies
993 ICmpInst::Predicate BoundPred =
994 IsSignedPredicate ? CmpInst::ICMP_SGT : CmpInst::ICMP_UGT;
996 if (LatchBrExitIdx == 0) {
997 const SCEV *StepPlusOne = SE.getAddExpr(Step, SE.getOne(Step->getType()));
998 if (SumCanReachMin(SE, RightSCEV, StepPlusOne, IsSignedPredicate)) {
999 // TODO: this restriction is easily removable -- we just have to
1000 // remember that the icmp was an sgt and not an sge.
1001 FailureReason = "limit may overflow when coercing ge to gt";
1005 if (!SE.isLoopEntryGuardedByCond(
1006 &L, BoundPred, IndVarStart,
1007 SE.getMinusSCEV(RightSCEV, SE.getOne(RightSCEV->getType())))) {
1008 FailureReason = "Induction variable start not bounded by lower limit";
1012 // We need to decrease the right value unless we have already increased
1013 // it virtually when we replaced EQ with SLT.
1014 if (!IncreasedRightValueByOne) {
1015 IRBuilder<> B(Preheader->getTerminator());
1016 RightValue = B.CreateSub(RightValue, One);
1019 if (!SE.isLoopEntryGuardedByCond(&L, BoundPred, IndVarStart, RightSCEV)) {
1020 FailureReason = "Induction variable start not bounded by lower limit";
1023 assert(!IncreasedRightValueByOne &&
1024 "Right value can be increased only for LatchBrExitIdx == 0!");
1027 BasicBlock *LatchExit = LatchBr->getSuccessor(LatchBrExitIdx);
1029 assert(SE.getLoopDisposition(LatchCount, &L) ==
1030 ScalarEvolution::LoopInvariant &&
1031 "loop variant exit count doesn't make sense!");
1033 assert(!L.contains(LatchExit) && "expected an exit block!");
1034 const DataLayout &DL = Preheader->getModule()->getDataLayout();
1035 Value *IndVarStartV =
1036 SCEVExpander(SE, DL, "irce")
1037 .expandCodeFor(IndVarStart, IndVarTy, Preheader->getTerminator());
1038 IndVarStartV->setName("indvar.start");
1040 LoopStructure Result;
1042 Result.Tag = "main";
1043 Result.Header = Header;
1044 Result.Latch = Latch;
1045 Result.LatchBr = LatchBr;
1046 Result.LatchExit = LatchExit;
1047 Result.LatchBrExitIdx = LatchBrExitIdx;
1048 Result.IndVarStart = IndVarStartV;
1049 Result.IndVarStep = StepCI;
1050 Result.IndVarBase = LeftValue;
1051 Result.IndVarIncreasing = IsIncreasing;
1052 Result.LoopExitAt = RightValue;
1053 Result.IsSignedPredicate = IsSignedPredicate;
1055 FailureReason = nullptr;
1060 Optional<LoopConstrainer::SubRanges>
1061 LoopConstrainer::calculateSubRanges(bool IsSignedPredicate) const {
1062 IntegerType *Ty = cast<IntegerType>(LatchTakenCount->getType());
1064 if (Range.getType() != Ty)
1067 LoopConstrainer::SubRanges Result;
1069 // I think we can be more aggressive here and make this nuw / nsw if the
1070 // addition that feeds into the icmp for the latch's terminating branch is nuw
1071 // / nsw. In any case, a wrapping 2's complement addition is safe.
1072 const SCEV *Start = SE.getSCEV(MainLoopStructure.IndVarStart);
1073 const SCEV *End = SE.getSCEV(MainLoopStructure.LoopExitAt);
1075 bool Increasing = MainLoopStructure.IndVarIncreasing;
1077 // We compute `Smallest` and `Greatest` such that [Smallest, Greatest), or
1078 // [Smallest, GreatestSeen] is the range of values the induction variable
1081 const SCEV *Smallest = nullptr, *Greatest = nullptr, *GreatestSeen = nullptr;
1083 const SCEV *One = SE.getOne(Ty);
1087 // No overflow, because the range [Smallest, GreatestSeen] is not empty.
1088 GreatestSeen = SE.getMinusSCEV(End, One);
1090 // These two computations may sign-overflow. Here is why that is okay:
1092 // We know that the induction variable does not sign-overflow on any
1093 // iteration except the last one, and it starts at `Start` and ends at
1094 // `End`, decrementing by one every time.
1096 // * if `Smallest` sign-overflows we know `End` is `INT_SMAX`. Since the
1097 // induction variable is decreasing we know that that the smallest value
1098 // the loop body is actually executed with is `INT_SMIN` == `Smallest`.
1100 // * if `Greatest` sign-overflows, we know it can only be `INT_SMIN`. In
1101 // that case, `Clamp` will always return `Smallest` and
1102 // [`Result.LowLimit`, `Result.HighLimit`) = [`Smallest`, `Smallest`)
1103 // will be an empty range. Returning an empty range is always safe.
1105 Smallest = SE.getAddExpr(End, One);
1106 Greatest = SE.getAddExpr(Start, One);
1107 GreatestSeen = Start;
1110 auto Clamp = [this, Smallest, Greatest, IsSignedPredicate](const SCEV *S) {
1111 return IsSignedPredicate
1112 ? SE.getSMaxExpr(Smallest, SE.getSMinExpr(Greatest, S))
1113 : SE.getUMaxExpr(Smallest, SE.getUMinExpr(Greatest, S));
1116 // In some cases we can prove that we don't need a pre or post loop.
1117 ICmpInst::Predicate PredLE =
1118 IsSignedPredicate ? ICmpInst::ICMP_SLE : ICmpInst::ICMP_ULE;
1119 ICmpInst::Predicate PredLT =
1120 IsSignedPredicate ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT;
1122 bool ProvablyNoPreloop =
1123 SE.isKnownPredicate(PredLE, Range.getBegin(), Smallest);
1124 if (!ProvablyNoPreloop)
1125 Result.LowLimit = Clamp(Range.getBegin());
1127 bool ProvablyNoPostLoop =
1128 SE.isKnownPredicate(PredLT, GreatestSeen, Range.getEnd());
1129 if (!ProvablyNoPostLoop)
1130 Result.HighLimit = Clamp(Range.getEnd());
1135 void LoopConstrainer::cloneLoop(LoopConstrainer::ClonedLoop &Result,
1136 const char *Tag) const {
1137 for (BasicBlock *BB : OriginalLoop.getBlocks()) {
1138 BasicBlock *Clone = CloneBasicBlock(BB, Result.Map, Twine(".") + Tag, &F);
1139 Result.Blocks.push_back(Clone);
1140 Result.Map[BB] = Clone;
1143 auto GetClonedValue = [&Result](Value *V) {
1144 assert(V && "null values not in domain!");
1145 auto It = Result.Map.find(V);
1146 if (It == Result.Map.end())
1148 return static_cast<Value *>(It->second);
1152 cast<BasicBlock>(GetClonedValue(OriginalLoop.getLoopLatch()));
1153 ClonedLatch->getTerminator()->setMetadata(ClonedLoopTag,
1154 MDNode::get(Ctx, {}));
1156 Result.Structure = MainLoopStructure.map(GetClonedValue);
1157 Result.Structure.Tag = Tag;
1159 for (unsigned i = 0, e = Result.Blocks.size(); i != e; ++i) {
1160 BasicBlock *ClonedBB = Result.Blocks[i];
1161 BasicBlock *OriginalBB = OriginalLoop.getBlocks()[i];
1163 assert(Result.Map[OriginalBB] == ClonedBB && "invariant!");
1165 for (Instruction &I : *ClonedBB)
1166 RemapInstruction(&I, Result.Map,
1167 RF_NoModuleLevelChanges | RF_IgnoreMissingLocals);
1169 // Exit blocks will now have one more predecessor and their PHI nodes need
1170 // to be edited to reflect that. No phi nodes need to be introduced because
1171 // the loop is in LCSSA.
1173 for (auto *SBB : successors(OriginalBB)) {
1174 if (OriginalLoop.contains(SBB))
1175 continue; // not an exit block
1177 for (PHINode &PN : SBB->phis()) {
1178 Value *OldIncoming = PN.getIncomingValueForBlock(OriginalBB);
1179 PN.addIncoming(GetClonedValue(OldIncoming), ClonedBB);
1185 LoopConstrainer::RewrittenRangeInfo LoopConstrainer::changeIterationSpaceEnd(
1186 const LoopStructure &LS, BasicBlock *Preheader, Value *ExitSubloopAt,
1187 BasicBlock *ContinuationBlock) const {
1188 // We start with a loop with a single latch:
1190 // +--------------------+
1194 // +--------+-----------+
1195 // | ----------------\
1197 // +--------v----v------+ |
1201 // +--------------------+ |
1205 // +--------------------+ |
1207 // | latch >----------/
1209 // +-------v------------+
1212 // | +--------------------+
1214 // +---> original exit |
1216 // +--------------------+
1218 // We change the control flow to look like
1221 // +--------------------+
1223 // | preheader >-------------------------+
1225 // +--------v-----------+ |
1226 // | /-------------+ |
1228 // +--------v--v--------+ | |
1230 // | header | | +--------+ |
1232 // +--------------------+ | | +-----v-----v-----------+
1234 // | | | .pseudo.exit |
1236 // | | +-----------v-----------+
1239 // | | +--------v-------------+
1240 // +--------------------+ | | | |
1241 // | | | | | ContinuationBlock |
1242 // | latch >------+ | | |
1243 // | | | +----------------------+
1244 // +---------v----------+ |
1247 // | +---------------^-----+
1249 // +-----> .exit.selector |
1251 // +----------v----------+
1253 // +--------------------+ |
1255 // | original exit <----+
1257 // +--------------------+
1259 RewrittenRangeInfo RRI;
1261 BasicBlock *BBInsertLocation = LS.Latch->getNextNode();
1262 RRI.ExitSelector = BasicBlock::Create(Ctx, Twine(LS.Tag) + ".exit.selector",
1263 &F, BBInsertLocation);
1264 RRI.PseudoExit = BasicBlock::Create(Ctx, Twine(LS.Tag) + ".pseudo.exit", &F,
1267 BranchInst *PreheaderJump = cast<BranchInst>(Preheader->getTerminator());
1268 bool Increasing = LS.IndVarIncreasing;
1269 bool IsSignedPredicate = LS.IsSignedPredicate;
1271 IRBuilder<> B(PreheaderJump);
1273 // EnterLoopCond - is it okay to start executing this `LS'?
1274 Value *EnterLoopCond = nullptr;
1276 EnterLoopCond = IsSignedPredicate
1277 ? B.CreateICmpSLT(LS.IndVarStart, ExitSubloopAt)
1278 : B.CreateICmpULT(LS.IndVarStart, ExitSubloopAt);
1280 EnterLoopCond = IsSignedPredicate
1281 ? B.CreateICmpSGT(LS.IndVarStart, ExitSubloopAt)
1282 : B.CreateICmpUGT(LS.IndVarStart, ExitSubloopAt);
1284 B.CreateCondBr(EnterLoopCond, LS.Header, RRI.PseudoExit);
1285 PreheaderJump->eraseFromParent();
1287 LS.LatchBr->setSuccessor(LS.LatchBrExitIdx, RRI.ExitSelector);
1288 B.SetInsertPoint(LS.LatchBr);
1289 Value *TakeBackedgeLoopCond = nullptr;
1291 TakeBackedgeLoopCond = IsSignedPredicate
1292 ? B.CreateICmpSLT(LS.IndVarBase, ExitSubloopAt)
1293 : B.CreateICmpULT(LS.IndVarBase, ExitSubloopAt);
1295 TakeBackedgeLoopCond = IsSignedPredicate
1296 ? B.CreateICmpSGT(LS.IndVarBase, ExitSubloopAt)
1297 : B.CreateICmpUGT(LS.IndVarBase, ExitSubloopAt);
1298 Value *CondForBranch = LS.LatchBrExitIdx == 1
1299 ? TakeBackedgeLoopCond
1300 : B.CreateNot(TakeBackedgeLoopCond);
1302 LS.LatchBr->setCondition(CondForBranch);
1304 B.SetInsertPoint(RRI.ExitSelector);
1306 // IterationsLeft - are there any more iterations left, given the original
1307 // upper bound on the induction variable? If not, we branch to the "real"
1309 Value *IterationsLeft = nullptr;
1311 IterationsLeft = IsSignedPredicate
1312 ? B.CreateICmpSLT(LS.IndVarBase, LS.LoopExitAt)
1313 : B.CreateICmpULT(LS.IndVarBase, LS.LoopExitAt);
1315 IterationsLeft = IsSignedPredicate
1316 ? B.CreateICmpSGT(LS.IndVarBase, LS.LoopExitAt)
1317 : B.CreateICmpUGT(LS.IndVarBase, LS.LoopExitAt);
1318 B.CreateCondBr(IterationsLeft, RRI.PseudoExit, LS.LatchExit);
1320 BranchInst *BranchToContinuation =
1321 BranchInst::Create(ContinuationBlock, RRI.PseudoExit);
1323 // We emit PHI nodes into `RRI.PseudoExit' that compute the "latest" value of
1324 // each of the PHI nodes in the loop header. This feeds into the initial
1325 // value of the same PHI nodes if/when we continue execution.
1326 for (PHINode &PN : LS.Header->phis()) {
1327 PHINode *NewPHI = PHINode::Create(PN.getType(), 2, PN.getName() + ".copy",
1328 BranchToContinuation);
1330 NewPHI->addIncoming(PN.getIncomingValueForBlock(Preheader), Preheader);
1331 NewPHI->addIncoming(PN.getIncomingValueForBlock(LS.Latch),
1333 RRI.PHIValuesAtPseudoExit.push_back(NewPHI);
1336 RRI.IndVarEnd = PHINode::Create(LS.IndVarBase->getType(), 2, "indvar.end",
1337 BranchToContinuation);
1338 RRI.IndVarEnd->addIncoming(LS.IndVarStart, Preheader);
1339 RRI.IndVarEnd->addIncoming(LS.IndVarBase, RRI.ExitSelector);
1341 // The latch exit now has a branch from `RRI.ExitSelector' instead of
1342 // `LS.Latch'. The PHI nodes need to be updated to reflect that.
1343 for (PHINode &PN : LS.LatchExit->phis())
1344 replacePHIBlock(&PN, LS.Latch, RRI.ExitSelector);
1349 void LoopConstrainer::rewriteIncomingValuesForPHIs(
1350 LoopStructure &LS, BasicBlock *ContinuationBlock,
1351 const LoopConstrainer::RewrittenRangeInfo &RRI) const {
1352 unsigned PHIIndex = 0;
1353 for (PHINode &PN : LS.Header->phis())
1354 for (unsigned i = 0, e = PN.getNumIncomingValues(); i < e; ++i)
1355 if (PN.getIncomingBlock(i) == ContinuationBlock)
1356 PN.setIncomingValue(i, RRI.PHIValuesAtPseudoExit[PHIIndex++]);
1358 LS.IndVarStart = RRI.IndVarEnd;
1361 BasicBlock *LoopConstrainer::createPreheader(const LoopStructure &LS,
1362 BasicBlock *OldPreheader,
1363 const char *Tag) const {
1364 BasicBlock *Preheader = BasicBlock::Create(Ctx, Tag, &F, LS.Header);
1365 BranchInst::Create(LS.Header, Preheader);
1367 for (PHINode &PN : LS.Header->phis())
1368 for (unsigned i = 0, e = PN.getNumIncomingValues(); i < e; ++i)
1369 replacePHIBlock(&PN, OldPreheader, Preheader);
1374 void LoopConstrainer::addToParentLoopIfNeeded(ArrayRef<BasicBlock *> BBs) {
1375 Loop *ParentLoop = OriginalLoop.getParentLoop();
1379 for (BasicBlock *BB : BBs)
1380 ParentLoop->addBasicBlockToLoop(BB, LI);
1383 Loop *LoopConstrainer::createClonedLoopStructure(Loop *Original, Loop *Parent,
1384 ValueToValueMapTy &VM) {
1385 Loop &New = *LI.AllocateLoop();
1387 Parent->addChildLoop(&New);
1389 LI.addTopLevelLoop(&New);
1392 // Add all of the blocks in Original to the new loop.
1393 for (auto *BB : Original->blocks())
1394 if (LI.getLoopFor(BB) == Original)
1395 New.addBasicBlockToLoop(cast<BasicBlock>(VM[BB]), LI);
1397 // Add all of the subloops to the new loop.
1398 for (Loop *SubLoop : *Original)
1399 createClonedLoopStructure(SubLoop, &New, VM);
1404 bool LoopConstrainer::run() {
1405 BasicBlock *Preheader = nullptr;
1406 LatchTakenCount = SE.getExitCount(&OriginalLoop, MainLoopStructure.Latch);
1407 Preheader = OriginalLoop.getLoopPreheader();
1408 assert(!isa<SCEVCouldNotCompute>(LatchTakenCount) && Preheader != nullptr &&
1411 OriginalPreheader = Preheader;
1412 MainLoopPreheader = Preheader;
1414 bool IsSignedPredicate = MainLoopStructure.IsSignedPredicate;
1415 Optional<SubRanges> MaybeSR = calculateSubRanges(IsSignedPredicate);
1416 if (!MaybeSR.hasValue()) {
1417 DEBUG(dbgs() << "irce: could not compute subranges\n");
1421 SubRanges SR = MaybeSR.getValue();
1422 bool Increasing = MainLoopStructure.IndVarIncreasing;
1424 cast<IntegerType>(MainLoopStructure.IndVarBase->getType());
1426 SCEVExpander Expander(SE, F.getParent()->getDataLayout(), "irce");
1427 Instruction *InsertPt = OriginalPreheader->getTerminator();
1429 // It would have been better to make `PreLoop' and `PostLoop'
1430 // `Optional<ClonedLoop>'s, but `ValueToValueMapTy' does not have a copy
1432 ClonedLoop PreLoop, PostLoop;
1434 Increasing ? SR.LowLimit.hasValue() : SR.HighLimit.hasValue();
1435 bool NeedsPostLoop =
1436 Increasing ? SR.HighLimit.hasValue() : SR.LowLimit.hasValue();
1438 Value *ExitPreLoopAt = nullptr;
1439 Value *ExitMainLoopAt = nullptr;
1440 const SCEVConstant *MinusOneS =
1441 cast<SCEVConstant>(SE.getConstant(IVTy, -1, true /* isSigned */));
1444 const SCEV *ExitPreLoopAtSCEV = nullptr;
1447 ExitPreLoopAtSCEV = *SR.LowLimit;
1449 if (CanBeMin(SE, *SR.HighLimit, IsSignedPredicate)) {
1450 DEBUG(dbgs() << "irce: could not prove no-overflow when computing "
1451 << "preloop exit limit. HighLimit = " << *(*SR.HighLimit)
1455 ExitPreLoopAtSCEV = SE.getAddExpr(*SR.HighLimit, MinusOneS);
1458 if (!isSafeToExpandAt(ExitPreLoopAtSCEV, InsertPt, SE)) {
1459 DEBUG(dbgs() << "irce: could not prove that it is safe to expand the"
1460 << " preloop exit limit " << *ExitPreLoopAtSCEV
1461 << " at block " << InsertPt->getParent()->getName() << "\n");
1465 ExitPreLoopAt = Expander.expandCodeFor(ExitPreLoopAtSCEV, IVTy, InsertPt);
1466 ExitPreLoopAt->setName("exit.preloop.at");
1469 if (NeedsPostLoop) {
1470 const SCEV *ExitMainLoopAtSCEV = nullptr;
1473 ExitMainLoopAtSCEV = *SR.HighLimit;
1475 if (CanBeMin(SE, *SR.LowLimit, IsSignedPredicate)) {
1476 DEBUG(dbgs() << "irce: could not prove no-overflow when computing "
1477 << "mainloop exit limit. LowLimit = " << *(*SR.LowLimit)
1481 ExitMainLoopAtSCEV = SE.getAddExpr(*SR.LowLimit, MinusOneS);
1484 if (!isSafeToExpandAt(ExitMainLoopAtSCEV, InsertPt, SE)) {
1485 DEBUG(dbgs() << "irce: could not prove that it is safe to expand the"
1486 << " main loop exit limit " << *ExitMainLoopAtSCEV
1487 << " at block " << InsertPt->getParent()->getName() << "\n");
1491 ExitMainLoopAt = Expander.expandCodeFor(ExitMainLoopAtSCEV, IVTy, InsertPt);
1492 ExitMainLoopAt->setName("exit.mainloop.at");
1495 // We clone these ahead of time so that we don't have to deal with changing
1496 // and temporarily invalid IR as we transform the loops.
1498 cloneLoop(PreLoop, "preloop");
1500 cloneLoop(PostLoop, "postloop");
1502 RewrittenRangeInfo PreLoopRRI;
1505 Preheader->getTerminator()->replaceUsesOfWith(MainLoopStructure.Header,
1506 PreLoop.Structure.Header);
1509 createPreheader(MainLoopStructure, Preheader, "mainloop");
1510 PreLoopRRI = changeIterationSpaceEnd(PreLoop.Structure, Preheader,
1511 ExitPreLoopAt, MainLoopPreheader);
1512 rewriteIncomingValuesForPHIs(MainLoopStructure, MainLoopPreheader,
1516 BasicBlock *PostLoopPreheader = nullptr;
1517 RewrittenRangeInfo PostLoopRRI;
1519 if (NeedsPostLoop) {
1521 createPreheader(PostLoop.Structure, Preheader, "postloop");
1522 PostLoopRRI = changeIterationSpaceEnd(MainLoopStructure, MainLoopPreheader,
1523 ExitMainLoopAt, PostLoopPreheader);
1524 rewriteIncomingValuesForPHIs(PostLoop.Structure, PostLoopPreheader,
1528 BasicBlock *NewMainLoopPreheader =
1529 MainLoopPreheader != Preheader ? MainLoopPreheader : nullptr;
1530 BasicBlock *NewBlocks[] = {PostLoopPreheader, PreLoopRRI.PseudoExit,
1531 PreLoopRRI.ExitSelector, PostLoopRRI.PseudoExit,
1532 PostLoopRRI.ExitSelector, NewMainLoopPreheader};
1534 // Some of the above may be nullptr, filter them out before passing to
1535 // addToParentLoopIfNeeded.
1537 std::remove(std::begin(NewBlocks), std::end(NewBlocks), nullptr);
1539 addToParentLoopIfNeeded(makeArrayRef(std::begin(NewBlocks), NewBlocksEnd));
1543 // We need to first add all the pre and post loop blocks into the loop
1544 // structures (as part of createClonedLoopStructure), and then update the
1545 // LCSSA form and LoopSimplifyForm. This is necessary for correctly updating
1546 // LI when LoopSimplifyForm is generated.
1547 Loop *PreL = nullptr, *PostL = nullptr;
1548 if (!PreLoop.Blocks.empty()) {
1549 PreL = createClonedLoopStructure(
1550 &OriginalLoop, OriginalLoop.getParentLoop(), PreLoop.Map);
1553 if (!PostLoop.Blocks.empty()) {
1554 PostL = createClonedLoopStructure(
1555 &OriginalLoop, OriginalLoop.getParentLoop(), PostLoop.Map);
1558 // This function canonicalizes the loop into Loop-Simplify and LCSSA forms.
1559 auto CanonicalizeLoop = [&] (Loop *L, bool IsOriginalLoop) {
1560 formLCSSARecursively(*L, DT, &LI, &SE);
1561 simplifyLoop(L, &DT, &LI, &SE, nullptr, true);
1562 // Pre/post loops are slow paths, we do not need to perform any loop
1563 // optimizations on them.
1564 if (!IsOriginalLoop)
1565 DisableAllLoopOptsOnLoop(*L);
1568 CanonicalizeLoop(PreL, false);
1570 CanonicalizeLoop(PostL, false);
1571 CanonicalizeLoop(&OriginalLoop, true);
1576 /// Computes and returns a range of values for the induction variable (IndVar)
1577 /// in which the range check can be safely elided. If it cannot compute such a
1578 /// range, returns None.
1579 Optional<InductiveRangeCheck::Range>
1580 InductiveRangeCheck::computeSafeIterationSpace(
1581 ScalarEvolution &SE, const SCEVAddRecExpr *IndVar,
1582 bool IsLatchSigned) const {
1583 // IndVar is of the form "A + B * I" (where "I" is the canonical induction
1584 // variable, that may or may not exist as a real llvm::Value in the loop) and
1585 // this inductive range check is a range check on the "C + D * I" ("C" is
1586 // getBegin() and "D" is getStep()). We rewrite the value being range
1587 // checked to "M + N * IndVar" where "N" = "D * B^(-1)" and "M" = "C - NA".
1589 // The actual inequalities we solve are of the form
1591 // 0 <= M + 1 * IndVar < L given L >= 0 (i.e. N == 1)
1593 // Here L stands for upper limit of the safe iteration space.
1594 // The inequality is satisfied by (0 - M) <= IndVar < (L - M). To avoid
1595 // overflows when calculating (0 - M) and (L - M) we, depending on type of
1596 // IV's iteration space, limit the calculations by borders of the iteration
1597 // space. For example, if IndVar is unsigned, (0 - M) overflows for any M > 0.
1598 // If we figured out that "anything greater than (-M) is safe", we strengthen
1599 // this to "everything greater than 0 is safe", assuming that values between
1600 // -M and 0 just do not exist in unsigned iteration space, and we don't want
1601 // to deal with overflown values.
1603 if (!IndVar->isAffine())
1606 const SCEV *A = IndVar->getStart();
1607 const SCEVConstant *B = dyn_cast<SCEVConstant>(IndVar->getStepRecurrence(SE));
1610 assert(!B->isZero() && "Recurrence with zero step?");
1612 const SCEV *C = getBegin();
1613 const SCEVConstant *D = dyn_cast<SCEVConstant>(getStep());
1617 assert(!D->getValue()->isZero() && "Recurrence with zero step?");
1618 unsigned BitWidth = cast<IntegerType>(IndVar->getType())->getBitWidth();
1619 const SCEV *SIntMax = SE.getConstant(APInt::getSignedMaxValue(BitWidth));
1621 // Substract Y from X so that it does not go through border of the IV
1622 // iteration space. Mathematically, it is equivalent to:
1624 // ClampedSubstract(X, Y) = min(max(X - Y, INT_MIN), INT_MAX). [1]
1626 // In [1], 'X - Y' is a mathematical substraction (result is not bounded to
1627 // any width of bit grid). But after we take min/max, the result is
1628 // guaranteed to be within [INT_MIN, INT_MAX].
1630 // In [1], INT_MAX and INT_MIN are respectively signed and unsigned max/min
1631 // values, depending on type of latch condition that defines IV iteration
1633 auto ClampedSubstract = [&](const SCEV *X, const SCEV *Y) {
1634 assert(SE.isKnownNonNegative(X) &&
1635 "We can only substract from values in [0; SINT_MAX]!");
1636 if (IsLatchSigned) {
1637 // X is a number from signed range, Y is interpreted as signed.
1638 // Even if Y is SINT_MAX, (X - Y) does not reach SINT_MIN. So the only
1639 // thing we should care about is that we didn't cross SINT_MAX.
1640 // So, if Y is positive, we substract Y safely.
1641 // Rule 1: Y > 0 ---> Y.
1642 // If 0 <= -Y <= (SINT_MAX - X), we substract Y safely.
1643 // Rule 2: Y >=s (X - SINT_MAX) ---> Y.
1644 // If 0 <= (SINT_MAX - X) < -Y, we can only substract (X - SINT_MAX).
1645 // Rule 3: Y <s (X - SINT_MAX) ---> (X - SINT_MAX).
1646 // It gives us smax(Y, X - SINT_MAX) to substract in all cases.
1647 const SCEV *XMinusSIntMax = SE.getMinusSCEV(X, SIntMax);
1648 return SE.getMinusSCEV(X, SE.getSMaxExpr(Y, XMinusSIntMax),
1651 // X is a number from unsigned range, Y is interpreted as signed.
1652 // Even if Y is SINT_MIN, (X - Y) does not reach UINT_MAX. So the only
1653 // thing we should care about is that we didn't cross zero.
1654 // So, if Y is negative, we substract Y safely.
1655 // Rule 1: Y <s 0 ---> Y.
1656 // If 0 <= Y <= X, we substract Y safely.
1657 // Rule 2: Y <=s X ---> Y.
1658 // If 0 <= X < Y, we should stop at 0 and can only substract X.
1659 // Rule 3: Y >s X ---> X.
1660 // It gives us smin(X, Y) to substract in all cases.
1661 return SE.getMinusSCEV(X, SE.getSMinExpr(X, Y), SCEV::FlagNUW);
1663 const SCEV *M = SE.getMinusSCEV(C, A);
1664 const SCEV *Zero = SE.getZero(M->getType());
1665 const SCEV *Begin = ClampedSubstract(Zero, M);
1666 const SCEV *L = nullptr;
1668 // We strengthen "0 <= I" to "0 <= I < INT_SMAX" and "I < L" to "0 <= I < L".
1669 // We can potentially do much better here.
1670 if (const SCEV *EndLimit = getEnd())
1673 assert(Kind == InductiveRangeCheck::RANGE_CHECK_LOWER && "invariant!");
1676 const SCEV *End = ClampedSubstract(L, M);
1677 return InductiveRangeCheck::Range(Begin, End);
1680 static Optional<InductiveRangeCheck::Range>
1681 IntersectSignedRange(ScalarEvolution &SE,
1682 const Optional<InductiveRangeCheck::Range> &R1,
1683 const InductiveRangeCheck::Range &R2) {
1684 if (R2.isEmpty(SE, /* IsSigned */ true))
1688 auto &R1Value = R1.getValue();
1689 // We never return empty ranges from this function, and R1 is supposed to be
1690 // a result of intersection. Thus, R1 is never empty.
1691 assert(!R1Value.isEmpty(SE, /* IsSigned */ true) &&
1692 "We should never have empty R1!");
1694 // TODO: we could widen the smaller range and have this work; but for now we
1695 // bail out to keep things simple.
1696 if (R1Value.getType() != R2.getType())
1699 const SCEV *NewBegin = SE.getSMaxExpr(R1Value.getBegin(), R2.getBegin());
1700 const SCEV *NewEnd = SE.getSMinExpr(R1Value.getEnd(), R2.getEnd());
1702 // If the resulting range is empty, just return None.
1703 auto Ret = InductiveRangeCheck::Range(NewBegin, NewEnd);
1704 if (Ret.isEmpty(SE, /* IsSigned */ true))
1709 static Optional<InductiveRangeCheck::Range>
1710 IntersectUnsignedRange(ScalarEvolution &SE,
1711 const Optional<InductiveRangeCheck::Range> &R1,
1712 const InductiveRangeCheck::Range &R2) {
1713 if (R2.isEmpty(SE, /* IsSigned */ false))
1717 auto &R1Value = R1.getValue();
1718 // We never return empty ranges from this function, and R1 is supposed to be
1719 // a result of intersection. Thus, R1 is never empty.
1720 assert(!R1Value.isEmpty(SE, /* IsSigned */ false) &&
1721 "We should never have empty R1!");
1723 // TODO: we could widen the smaller range and have this work; but for now we
1724 // bail out to keep things simple.
1725 if (R1Value.getType() != R2.getType())
1728 const SCEV *NewBegin = SE.getUMaxExpr(R1Value.getBegin(), R2.getBegin());
1729 const SCEV *NewEnd = SE.getUMinExpr(R1Value.getEnd(), R2.getEnd());
1731 // If the resulting range is empty, just return None.
1732 auto Ret = InductiveRangeCheck::Range(NewBegin, NewEnd);
1733 if (Ret.isEmpty(SE, /* IsSigned */ false))
1738 bool InductiveRangeCheckElimination::runOnLoop(Loop *L, LPPassManager &LPM) {
1742 if (L->getBlocks().size() >= LoopSizeCutoff) {
1743 DEBUG(dbgs() << "irce: giving up constraining loop, too large\n";);
1747 BasicBlock *Preheader = L->getLoopPreheader();
1749 DEBUG(dbgs() << "irce: loop has no preheader, leaving\n");
1753 LLVMContext &Context = Preheader->getContext();
1754 SmallVector<InductiveRangeCheck, 16> RangeChecks;
1755 ScalarEvolution &SE = getAnalysis<ScalarEvolutionWrapperPass>().getSE();
1756 BranchProbabilityInfo &BPI =
1757 getAnalysis<BranchProbabilityInfoWrapperPass>().getBPI();
1759 for (auto BBI : L->getBlocks())
1760 if (BranchInst *TBI = dyn_cast<BranchInst>(BBI->getTerminator()))
1761 InductiveRangeCheck::extractRangeChecksFromBranch(TBI, L, SE, BPI,
1764 if (RangeChecks.empty())
1767 auto PrintRecognizedRangeChecks = [&](raw_ostream &OS) {
1768 OS << "irce: looking at loop "; L->print(OS);
1769 OS << "irce: loop has " << RangeChecks.size()
1770 << " inductive range checks: \n";
1771 for (InductiveRangeCheck &IRC : RangeChecks)
1775 DEBUG(PrintRecognizedRangeChecks(dbgs()));
1777 if (PrintRangeChecks)
1778 PrintRecognizedRangeChecks(errs());
1780 const char *FailureReason = nullptr;
1781 Optional<LoopStructure> MaybeLoopStructure =
1782 LoopStructure::parseLoopStructure(SE, BPI, *L, FailureReason);
1783 if (!MaybeLoopStructure.hasValue()) {
1784 DEBUG(dbgs() << "irce: could not parse loop structure: " << FailureReason
1788 LoopStructure LS = MaybeLoopStructure.getValue();
1789 const SCEVAddRecExpr *IndVar =
1790 cast<SCEVAddRecExpr>(SE.getMinusSCEV(SE.getSCEV(LS.IndVarBase), SE.getSCEV(LS.IndVarStep)));
1792 Optional<InductiveRangeCheck::Range> SafeIterRange;
1793 Instruction *ExprInsertPt = Preheader->getTerminator();
1795 SmallVector<InductiveRangeCheck, 4> RangeChecksToEliminate;
1796 // Basing on the type of latch predicate, we interpret the IV iteration range
1797 // as signed or unsigned range. We use different min/max functions (signed or
1798 // unsigned) when intersecting this range with safe iteration ranges implied
1800 auto IntersectRange =
1801 LS.IsSignedPredicate ? IntersectSignedRange : IntersectUnsignedRange;
1803 IRBuilder<> B(ExprInsertPt);
1804 for (InductiveRangeCheck &IRC : RangeChecks) {
1805 auto Result = IRC.computeSafeIterationSpace(SE, IndVar,
1806 LS.IsSignedPredicate);
1807 if (Result.hasValue()) {
1808 auto MaybeSafeIterRange =
1809 IntersectRange(SE, SafeIterRange, Result.getValue());
1810 if (MaybeSafeIterRange.hasValue()) {
1812 !MaybeSafeIterRange.getValue().isEmpty(SE, LS.IsSignedPredicate) &&
1813 "We should never return empty ranges!");
1814 RangeChecksToEliminate.push_back(IRC);
1815 SafeIterRange = MaybeSafeIterRange.getValue();
1820 if (!SafeIterRange.hasValue())
1823 auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
1824 LoopConstrainer LC(*L, getAnalysis<LoopInfoWrapperPass>().getLoopInfo(), LPM,
1825 LS, SE, DT, SafeIterRange.getValue());
1826 bool Changed = LC.run();
1829 auto PrintConstrainedLoopInfo = [L]() {
1830 dbgs() << "irce: in function ";
1831 dbgs() << L->getHeader()->getParent()->getName() << ": ";
1832 dbgs() << "constrained ";
1836 DEBUG(PrintConstrainedLoopInfo());
1838 if (PrintChangedLoops)
1839 PrintConstrainedLoopInfo();
1841 // Optimize away the now-redundant range checks.
1843 for (InductiveRangeCheck &IRC : RangeChecksToEliminate) {
1844 ConstantInt *FoldedRangeCheck = IRC.getPassingDirection()
1845 ? ConstantInt::getTrue(Context)
1846 : ConstantInt::getFalse(Context);
1847 IRC.getCheckUse()->set(FoldedRangeCheck);
1854 Pass *llvm::createInductiveRangeCheckEliminationPass() {
1855 return new InductiveRangeCheckElimination;