1 //===- InductiveRangeCheckElimination.cpp - -------------------------------===//
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7 //===----------------------------------------------------------------------===//
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();
43 //===----------------------------------------------------------------------===//
45 #include "llvm/Transforms/Scalar/InductiveRangeCheckElimination.h"
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/LoopAnalysisManager.h"
56 #include "llvm/Analysis/LoopInfo.h"
57 #include "llvm/Analysis/LoopPass.h"
58 #include "llvm/Analysis/ScalarEvolution.h"
59 #include "llvm/Analysis/ScalarEvolutionExpander.h"
60 #include "llvm/Analysis/ScalarEvolutionExpressions.h"
61 #include "llvm/IR/BasicBlock.h"
62 #include "llvm/IR/CFG.h"
63 #include "llvm/IR/Constants.h"
64 #include "llvm/IR/DerivedTypes.h"
65 #include "llvm/IR/Dominators.h"
66 #include "llvm/IR/Function.h"
67 #include "llvm/IR/IRBuilder.h"
68 #include "llvm/IR/InstrTypes.h"
69 #include "llvm/IR/Instructions.h"
70 #include "llvm/IR/Metadata.h"
71 #include "llvm/IR/Module.h"
72 #include "llvm/IR/PatternMatch.h"
73 #include "llvm/IR/Type.h"
74 #include "llvm/IR/Use.h"
75 #include "llvm/IR/User.h"
76 #include "llvm/IR/Value.h"
77 #include "llvm/InitializePasses.h"
78 #include "llvm/Pass.h"
79 #include "llvm/Support/BranchProbability.h"
80 #include "llvm/Support/Casting.h"
81 #include "llvm/Support/CommandLine.h"
82 #include "llvm/Support/Compiler.h"
83 #include "llvm/Support/Debug.h"
84 #include "llvm/Support/ErrorHandling.h"
85 #include "llvm/Support/raw_ostream.h"
86 #include "llvm/Transforms/Scalar.h"
87 #include "llvm/Transforms/Utils/Cloning.h"
88 #include "llvm/Transforms/Utils/LoopSimplify.h"
89 #include "llvm/Transforms/Utils/LoopUtils.h"
90 #include "llvm/Transforms/Utils/ValueMapper.h"
99 using namespace llvm::PatternMatch;
101 static cl::opt<unsigned> LoopSizeCutoff("irce-loop-size-cutoff", cl::Hidden,
104 static cl::opt<bool> PrintChangedLoops("irce-print-changed-loops", cl::Hidden,
107 static cl::opt<bool> PrintRangeChecks("irce-print-range-checks", cl::Hidden,
110 static cl::opt<int> MaxExitProbReciprocal("irce-max-exit-prob-reciprocal",
111 cl::Hidden, cl::init(10));
113 static cl::opt<bool> SkipProfitabilityChecks("irce-skip-profitability-checks",
114 cl::Hidden, cl::init(false));
116 static cl::opt<bool> AllowUnsignedLatchCondition("irce-allow-unsigned-latch",
117 cl::Hidden, cl::init(true));
119 static cl::opt<bool> AllowNarrowLatchCondition(
120 "irce-allow-narrow-latch", cl::Hidden, cl::init(true),
121 cl::desc("If set to true, IRCE may eliminate wide range checks in loops "
122 "with narrow latch condition."));
124 static const char *ClonedLoopTag = "irce.loop.clone";
126 #define DEBUG_TYPE "irce"
130 /// An inductive range check is conditional branch in a loop with
132 /// 1. a very cold successor (i.e. the branch jumps to that successor very
137 /// 2. a condition that is provably true for some contiguous range of values
138 /// taken by the containing loop's induction variable.
140 class InductiveRangeCheck {
142 const SCEV *Begin = nullptr;
143 const SCEV *Step = nullptr;
144 const SCEV *End = nullptr;
145 Use *CheckUse = nullptr;
146 bool IsSigned = true;
148 static bool parseRangeCheckICmp(Loop *L, ICmpInst *ICI, ScalarEvolution &SE,
149 Value *&Index, Value *&Length,
153 extractRangeChecksFromCond(Loop *L, ScalarEvolution &SE, Use &ConditionUse,
154 SmallVectorImpl<InductiveRangeCheck> &Checks,
155 SmallPtrSetImpl<Value *> &Visited);
158 const SCEV *getBegin() const { return Begin; }
159 const SCEV *getStep() const { return Step; }
160 const SCEV *getEnd() const { return End; }
161 bool isSigned() const { return IsSigned; }
163 void print(raw_ostream &OS) const {
164 OS << "InductiveRangeCheck:\n";
171 OS << "\n CheckUse: ";
172 getCheckUse()->getUser()->print(OS);
173 OS << " Operand: " << getCheckUse()->getOperandNo() << "\n";
181 Use *getCheckUse() const { return CheckUse; }
183 /// Represents an signed integer range [Range.getBegin(), Range.getEnd()). If
184 /// R.getEnd() le R.getBegin(), then R denotes the empty range.
191 Range(const SCEV *Begin, const SCEV *End) : Begin(Begin), End(End) {
192 assert(Begin->getType() == End->getType() && "ill-typed range!");
195 Type *getType() const { return Begin->getType(); }
196 const SCEV *getBegin() const { return Begin; }
197 const SCEV *getEnd() const { return End; }
198 bool isEmpty(ScalarEvolution &SE, bool IsSigned) const {
202 return SE.isKnownPredicate(ICmpInst::ICMP_SGE, Begin, End);
204 return SE.isKnownPredicate(ICmpInst::ICMP_UGE, Begin, End);
208 /// This is the value the condition of the branch needs to evaluate to for the
209 /// branch to take the hot successor (see (1) above).
210 bool getPassingDirection() { return true; }
212 /// Computes a range for the induction variable (IndVar) in which the range
213 /// check is redundant and can be constant-folded away. The induction
214 /// variable is not required to be the canonical {0,+,1} induction variable.
215 Optional<Range> computeSafeIterationSpace(ScalarEvolution &SE,
216 const SCEVAddRecExpr *IndVar,
217 bool IsLatchSigned) const;
219 /// Parse out a set of inductive range checks from \p BI and append them to \p
222 /// NB! There may be conditions feeding into \p BI that aren't inductive range
223 /// checks, and hence don't end up in \p Checks.
225 extractRangeChecksFromBranch(BranchInst *BI, Loop *L, ScalarEvolution &SE,
226 BranchProbabilityInfo *BPI,
227 SmallVectorImpl<InductiveRangeCheck> &Checks);
230 class InductiveRangeCheckElimination {
232 BranchProbabilityInfo *BPI;
237 InductiveRangeCheckElimination(ScalarEvolution &SE,
238 BranchProbabilityInfo *BPI, DominatorTree &DT,
240 : SE(SE), BPI(BPI), DT(DT), LI(LI) {}
242 bool run(Loop *L, function_ref<void(Loop *, bool)> LPMAddNewLoop);
245 class IRCELegacyPass : public LoopPass {
249 IRCELegacyPass() : LoopPass(ID) {
250 initializeIRCELegacyPassPass(*PassRegistry::getPassRegistry());
253 void getAnalysisUsage(AnalysisUsage &AU) const override {
254 AU.addRequired<BranchProbabilityInfoWrapperPass>();
255 getLoopAnalysisUsage(AU);
258 bool runOnLoop(Loop *L, LPPassManager &LPM) override;
261 } // end anonymous namespace
263 char IRCELegacyPass::ID = 0;
265 INITIALIZE_PASS_BEGIN(IRCELegacyPass, "irce",
266 "Inductive range check elimination", false, false)
267 INITIALIZE_PASS_DEPENDENCY(BranchProbabilityInfoWrapperPass)
268 INITIALIZE_PASS_DEPENDENCY(LoopPass)
269 INITIALIZE_PASS_END(IRCELegacyPass, "irce", "Inductive range check elimination",
272 /// Parse a single ICmp instruction, `ICI`, into a range check. If `ICI` cannot
273 /// be interpreted as a range check, return false and set `Index` and `Length`
274 /// to `nullptr`. Otherwise set `Index` to the value being range checked, and
275 /// set `Length` to the upper limit `Index` is being range checked.
277 InductiveRangeCheck::parseRangeCheckICmp(Loop *L, ICmpInst *ICI,
278 ScalarEvolution &SE, Value *&Index,
279 Value *&Length, bool &IsSigned) {
280 auto IsLoopInvariant = [&SE, L](Value *V) {
281 return SE.isLoopInvariant(SE.getSCEV(V), L);
284 ICmpInst::Predicate Pred = ICI->getPredicate();
285 Value *LHS = ICI->getOperand(0);
286 Value *RHS = ICI->getOperand(1);
292 case ICmpInst::ICMP_SLE:
295 case ICmpInst::ICMP_SGE:
297 if (match(RHS, m_ConstantInt<0>())) {
299 return true; // Lower.
303 case ICmpInst::ICMP_SLT:
306 case ICmpInst::ICMP_SGT:
308 if (match(RHS, m_ConstantInt<-1>())) {
310 return true; // Lower.
313 if (IsLoopInvariant(LHS)) {
316 return true; // Upper.
320 case ICmpInst::ICMP_ULT:
323 case ICmpInst::ICMP_UGT:
325 if (IsLoopInvariant(LHS)) {
328 return true; // Both lower and upper.
333 llvm_unreachable("default clause returns!");
336 void InductiveRangeCheck::extractRangeChecksFromCond(
337 Loop *L, ScalarEvolution &SE, Use &ConditionUse,
338 SmallVectorImpl<InductiveRangeCheck> &Checks,
339 SmallPtrSetImpl<Value *> &Visited) {
340 Value *Condition = ConditionUse.get();
341 if (!Visited.insert(Condition).second)
344 // TODO: Do the same for OR, XOR, NOT etc?
345 if (match(Condition, m_And(m_Value(), m_Value()))) {
346 extractRangeChecksFromCond(L, SE, cast<User>(Condition)->getOperandUse(0),
348 extractRangeChecksFromCond(L, SE, cast<User>(Condition)->getOperandUse(1),
353 ICmpInst *ICI = dyn_cast<ICmpInst>(Condition);
357 Value *Length = nullptr, *Index;
359 if (!parseRangeCheckICmp(L, ICI, SE, Index, Length, IsSigned))
362 const auto *IndexAddRec = dyn_cast<SCEVAddRecExpr>(SE.getSCEV(Index));
364 IndexAddRec && (IndexAddRec->getLoop() == L) && IndexAddRec->isAffine();
369 const SCEV *End = nullptr;
370 // We strengthen "0 <= I" to "0 <= I < INT_SMAX" and "I < L" to "0 <= I < L".
371 // We can potentially do much better here.
373 End = SE.getSCEV(Length);
375 // So far we can only reach this point for Signed range check. This may
376 // change in future. In this case we will need to pick Unsigned max for the
377 // unsigned range check.
378 unsigned BitWidth = cast<IntegerType>(IndexAddRec->getType())->getBitWidth();
379 const SCEV *SIntMax = SE.getConstant(APInt::getSignedMaxValue(BitWidth));
383 InductiveRangeCheck IRC;
385 IRC.Begin = IndexAddRec->getStart();
386 IRC.Step = IndexAddRec->getStepRecurrence(SE);
387 IRC.CheckUse = &ConditionUse;
388 IRC.IsSigned = IsSigned;
389 Checks.push_back(IRC);
392 void InductiveRangeCheck::extractRangeChecksFromBranch(
393 BranchInst *BI, Loop *L, ScalarEvolution &SE, BranchProbabilityInfo *BPI,
394 SmallVectorImpl<InductiveRangeCheck> &Checks) {
395 if (BI->isUnconditional() || BI->getParent() == L->getLoopLatch())
398 BranchProbability LikelyTaken(15, 16);
400 if (!SkipProfitabilityChecks && BPI &&
401 BPI->getEdgeProbability(BI->getParent(), (unsigned)0) < LikelyTaken)
404 SmallPtrSet<Value *, 8> Visited;
405 InductiveRangeCheck::extractRangeChecksFromCond(L, SE, BI->getOperandUse(0),
409 // Add metadata to the loop L to disable loop optimizations. Callers need to
410 // confirm that optimizing loop L is not beneficial.
411 static void DisableAllLoopOptsOnLoop(Loop &L) {
412 // We do not care about any existing loopID related metadata for L, since we
413 // are setting all loop metadata to false.
414 LLVMContext &Context = L.getHeader()->getContext();
415 // Reserve first location for self reference to the LoopID metadata node.
416 MDNode *Dummy = MDNode::get(Context, {});
417 MDNode *DisableUnroll = MDNode::get(
418 Context, {MDString::get(Context, "llvm.loop.unroll.disable")});
420 ConstantAsMetadata::get(ConstantInt::get(Type::getInt1Ty(Context), 0));
421 MDNode *DisableVectorize = MDNode::get(
423 {MDString::get(Context, "llvm.loop.vectorize.enable"), FalseVal});
424 MDNode *DisableLICMVersioning = MDNode::get(
425 Context, {MDString::get(Context, "llvm.loop.licm_versioning.disable")});
426 MDNode *DisableDistribution= MDNode::get(
428 {MDString::get(Context, "llvm.loop.distribute.enable"), FalseVal});
430 MDNode::get(Context, {Dummy, DisableUnroll, DisableVectorize,
431 DisableLICMVersioning, DisableDistribution});
432 // Set operand 0 to refer to the loop id itself.
433 NewLoopID->replaceOperandWith(0, NewLoopID);
434 L.setLoopID(NewLoopID);
439 // Keeps track of the structure of a loop. This is similar to llvm::Loop,
440 // except that it is more lightweight and can track the state of a loop through
441 // changing and potentially invalid IR. This structure also formalizes the
442 // kinds of loops we can deal with -- ones that have a single latch that is also
443 // an exiting block *and* have a canonical induction variable.
444 struct LoopStructure {
445 const char *Tag = "";
447 BasicBlock *Header = nullptr;
448 BasicBlock *Latch = nullptr;
450 // `Latch's terminator instruction is `LatchBr', and it's `LatchBrExitIdx'th
451 // successor is `LatchExit', the exit block of the loop.
452 BranchInst *LatchBr = nullptr;
453 BasicBlock *LatchExit = nullptr;
454 unsigned LatchBrExitIdx = std::numeric_limits<unsigned>::max();
456 // The loop represented by this instance of LoopStructure is semantically
459 // intN_ty inc = IndVarIncreasing ? 1 : -1;
460 // pred_ty predicate = IndVarIncreasing ? ICMP_SLT : ICMP_SGT;
462 // for (intN_ty iv = IndVarStart; predicate(iv, LoopExitAt); iv = IndVarBase)
465 Value *IndVarBase = nullptr;
466 Value *IndVarStart = nullptr;
467 Value *IndVarStep = nullptr;
468 Value *LoopExitAt = nullptr;
469 bool IndVarIncreasing = false;
470 bool IsSignedPredicate = true;
472 LoopStructure() = default;
474 template <typename M> LoopStructure map(M Map) const {
475 LoopStructure Result;
477 Result.Header = cast<BasicBlock>(Map(Header));
478 Result.Latch = cast<BasicBlock>(Map(Latch));
479 Result.LatchBr = cast<BranchInst>(Map(LatchBr));
480 Result.LatchExit = cast<BasicBlock>(Map(LatchExit));
481 Result.LatchBrExitIdx = LatchBrExitIdx;
482 Result.IndVarBase = Map(IndVarBase);
483 Result.IndVarStart = Map(IndVarStart);
484 Result.IndVarStep = Map(IndVarStep);
485 Result.LoopExitAt = Map(LoopExitAt);
486 Result.IndVarIncreasing = IndVarIncreasing;
487 Result.IsSignedPredicate = IsSignedPredicate;
491 static Optional<LoopStructure> parseLoopStructure(ScalarEvolution &,
492 BranchProbabilityInfo *BPI,
493 Loop &, const char *&);
496 /// This class is used to constrain loops to run within a given iteration space.
497 /// The algorithm this class implements is given a Loop and a range [Begin,
498 /// End). The algorithm then tries to break out a "main loop" out of the loop
499 /// it is given in a way that the "main loop" runs with the induction variable
500 /// in a subset of [Begin, End). The algorithm emits appropriate pre and post
501 /// loops to run any remaining iterations. The pre loop runs any iterations in
502 /// which the induction variable is < Begin, and the post loop runs any
503 /// iterations in which the induction variable is >= End.
504 class LoopConstrainer {
505 // The representation of a clone of the original loop we started out with.
508 std::vector<BasicBlock *> Blocks;
510 // `Map` maps values in the clonee into values in the cloned version
511 ValueToValueMapTy Map;
513 // An instance of `LoopStructure` for the cloned loop
514 LoopStructure Structure;
517 // Result of rewriting the range of a loop. See changeIterationSpaceEnd for
518 // more details on what these fields mean.
519 struct RewrittenRangeInfo {
520 BasicBlock *PseudoExit = nullptr;
521 BasicBlock *ExitSelector = nullptr;
522 std::vector<PHINode *> PHIValuesAtPseudoExit;
523 PHINode *IndVarEnd = nullptr;
525 RewrittenRangeInfo() = default;
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 // Compute a safe set of limits for the main loop to run in -- effectively the
541 // intersection of `Range' and the iteration space of the original loop.
542 // Return None if unable to compute the set of subranges.
543 Optional<SubRanges> calculateSubRanges(bool IsSignedPredicate) const;
545 // Clone `OriginalLoop' and return the result in CLResult. The IR after
546 // running `cloneLoop' is well formed except for the PHI nodes in CLResult --
547 // the PHI nodes say that there is an incoming edge from `OriginalPreheader`
548 // but there is no such edge.
549 void cloneLoop(ClonedLoop &CLResult, const char *Tag) const;
551 // Create the appropriate loop structure needed to describe a cloned copy of
552 // `Original`. The clone is described by `VM`.
553 Loop *createClonedLoopStructure(Loop *Original, Loop *Parent,
554 ValueToValueMapTy &VM, bool IsSubloop);
556 // Rewrite the iteration space of the loop denoted by (LS, Preheader). The
557 // iteration space of the rewritten loop ends at ExitLoopAt. The start of the
558 // iteration space is not changed. `ExitLoopAt' is assumed to be slt
559 // `OriginalHeaderCount'.
561 // If there are iterations left to execute, control is made to jump to
562 // `ContinuationBlock', otherwise they take the normal loop exit. The
563 // returned `RewrittenRangeInfo' object is populated as follows:
565 // .PseudoExit is a basic block that unconditionally branches to
566 // `ContinuationBlock'.
568 // .ExitSelector is a basic block that decides, on exit from the loop,
569 // whether to branch to the "true" exit or to `PseudoExit'.
571 // .PHIValuesAtPseudoExit are PHINodes in `PseudoExit' that compute the value
572 // for each PHINode in the loop header on taking the pseudo exit.
574 // After changeIterationSpaceEnd, `Preheader' is no longer a legitimate
575 // preheader because it is made to branch to the loop header only
578 changeIterationSpaceEnd(const LoopStructure &LS, BasicBlock *Preheader,
580 BasicBlock *ContinuationBlock) const;
582 // The loop denoted by `LS' has `OldPreheader' as its preheader. This
583 // function creates a new preheader for `LS' and returns it.
584 BasicBlock *createPreheader(const LoopStructure &LS, BasicBlock *OldPreheader,
585 const char *Tag) const;
587 // `ContinuationBlockAndPreheader' was the continuation block for some call to
588 // `changeIterationSpaceEnd' and is the preheader to the loop denoted by `LS'.
589 // This function rewrites the PHI nodes in `LS.Header' to start with the
591 void rewriteIncomingValuesForPHIs(
592 LoopStructure &LS, BasicBlock *ContinuationBlockAndPreheader,
593 const LoopConstrainer::RewrittenRangeInfo &RRI) const;
595 // Even though we do not preserve any passes at this time, we at least need to
596 // keep the parent loop structure consistent. The `LPPassManager' seems to
597 // verify this after running a loop pass. This function adds the list of
598 // blocks denoted by BBs to this loops parent loop if required.
599 void addToParentLoopIfNeeded(ArrayRef<BasicBlock *> BBs);
601 // Some global state.
607 function_ref<void(Loop *, bool)> LPMAddNewLoop;
609 // Information about the original loop we started out with.
612 const SCEV *LatchTakenCount = nullptr;
613 BasicBlock *OriginalPreheader = nullptr;
615 // The preheader of the main loop. This may or may not be different from
616 // `OriginalPreheader'.
617 BasicBlock *MainLoopPreheader = nullptr;
619 // The range we need to run the main loop in.
620 InductiveRangeCheck::Range Range;
622 // The structure of the main loop (see comment at the beginning of this class
624 LoopStructure MainLoopStructure;
627 LoopConstrainer(Loop &L, LoopInfo &LI,
628 function_ref<void(Loop *, bool)> LPMAddNewLoop,
629 const LoopStructure &LS, ScalarEvolution &SE,
630 DominatorTree &DT, InductiveRangeCheck::Range R)
631 : F(*L.getHeader()->getParent()), Ctx(L.getHeader()->getContext()),
632 SE(SE), DT(DT), LI(LI), LPMAddNewLoop(LPMAddNewLoop), OriginalLoop(L),
633 Range(R), MainLoopStructure(LS) {}
635 // Entry point for the algorithm. Returns true on success.
639 } // end anonymous namespace
641 /// Given a loop with an deccreasing induction variable, is it possible to
642 /// safely calculate the bounds of a new loop using the given Predicate.
643 static bool isSafeDecreasingBound(const SCEV *Start,
644 const SCEV *BoundSCEV, const SCEV *Step,
645 ICmpInst::Predicate Pred,
646 unsigned LatchBrExitIdx,
647 Loop *L, ScalarEvolution &SE) {
648 if (Pred != ICmpInst::ICMP_SLT && Pred != ICmpInst::ICMP_SGT &&
649 Pred != ICmpInst::ICMP_ULT && Pred != ICmpInst::ICMP_UGT)
652 if (!SE.isAvailableAtLoopEntry(BoundSCEV, L))
655 assert(SE.isKnownNegative(Step) && "expecting negative step");
657 LLVM_DEBUG(dbgs() << "irce: isSafeDecreasingBound with:\n");
658 LLVM_DEBUG(dbgs() << "irce: Start: " << *Start << "\n");
659 LLVM_DEBUG(dbgs() << "irce: Step: " << *Step << "\n");
660 LLVM_DEBUG(dbgs() << "irce: BoundSCEV: " << *BoundSCEV << "\n");
661 LLVM_DEBUG(dbgs() << "irce: Pred: " << ICmpInst::getPredicateName(Pred)
663 LLVM_DEBUG(dbgs() << "irce: LatchExitBrIdx: " << LatchBrExitIdx << "\n");
665 bool IsSigned = ICmpInst::isSigned(Pred);
666 // The predicate that we need to check that the induction variable lies
668 ICmpInst::Predicate BoundPred =
669 IsSigned ? CmpInst::ICMP_SGT : CmpInst::ICMP_UGT;
671 if (LatchBrExitIdx == 1)
672 return SE.isLoopEntryGuardedByCond(L, BoundPred, Start, BoundSCEV);
674 assert(LatchBrExitIdx == 0 &&
675 "LatchBrExitIdx should be either 0 or 1");
677 const SCEV *StepPlusOne = SE.getAddExpr(Step, SE.getOne(Step->getType()));
678 unsigned BitWidth = cast<IntegerType>(BoundSCEV->getType())->getBitWidth();
679 APInt Min = IsSigned ? APInt::getSignedMinValue(BitWidth) :
680 APInt::getMinValue(BitWidth);
681 const SCEV *Limit = SE.getMinusSCEV(SE.getConstant(Min), StepPlusOne);
683 const SCEV *MinusOne =
684 SE.getMinusSCEV(BoundSCEV, SE.getOne(BoundSCEV->getType()));
686 return SE.isLoopEntryGuardedByCond(L, BoundPred, Start, MinusOne) &&
687 SE.isLoopEntryGuardedByCond(L, BoundPred, BoundSCEV, Limit);
691 /// Given a loop with an increasing induction variable, is it possible to
692 /// safely calculate the bounds of a new loop using the given Predicate.
693 static bool isSafeIncreasingBound(const SCEV *Start,
694 const SCEV *BoundSCEV, const SCEV *Step,
695 ICmpInst::Predicate Pred,
696 unsigned LatchBrExitIdx,
697 Loop *L, ScalarEvolution &SE) {
698 if (Pred != ICmpInst::ICMP_SLT && Pred != ICmpInst::ICMP_SGT &&
699 Pred != ICmpInst::ICMP_ULT && Pred != ICmpInst::ICMP_UGT)
702 if (!SE.isAvailableAtLoopEntry(BoundSCEV, L))
705 LLVM_DEBUG(dbgs() << "irce: isSafeIncreasingBound with:\n");
706 LLVM_DEBUG(dbgs() << "irce: Start: " << *Start << "\n");
707 LLVM_DEBUG(dbgs() << "irce: Step: " << *Step << "\n");
708 LLVM_DEBUG(dbgs() << "irce: BoundSCEV: " << *BoundSCEV << "\n");
709 LLVM_DEBUG(dbgs() << "irce: Pred: " << ICmpInst::getPredicateName(Pred)
711 LLVM_DEBUG(dbgs() << "irce: LatchExitBrIdx: " << LatchBrExitIdx << "\n");
713 bool IsSigned = ICmpInst::isSigned(Pred);
714 // The predicate that we need to check that the induction variable lies
716 ICmpInst::Predicate BoundPred =
717 IsSigned ? CmpInst::ICMP_SLT : CmpInst::ICMP_ULT;
719 if (LatchBrExitIdx == 1)
720 return SE.isLoopEntryGuardedByCond(L, BoundPred, Start, BoundSCEV);
722 assert(LatchBrExitIdx == 0 && "LatchBrExitIdx should be 0 or 1");
724 const SCEV *StepMinusOne =
725 SE.getMinusSCEV(Step, SE.getOne(Step->getType()));
726 unsigned BitWidth = cast<IntegerType>(BoundSCEV->getType())->getBitWidth();
727 APInt Max = IsSigned ? APInt::getSignedMaxValue(BitWidth) :
728 APInt::getMaxValue(BitWidth);
729 const SCEV *Limit = SE.getMinusSCEV(SE.getConstant(Max), StepMinusOne);
731 return (SE.isLoopEntryGuardedByCond(L, BoundPred, Start,
732 SE.getAddExpr(BoundSCEV, Step)) &&
733 SE.isLoopEntryGuardedByCond(L, BoundPred, BoundSCEV, Limit));
736 Optional<LoopStructure>
737 LoopStructure::parseLoopStructure(ScalarEvolution &SE,
738 BranchProbabilityInfo *BPI, Loop &L,
739 const char *&FailureReason) {
740 if (!L.isLoopSimplifyForm()) {
741 FailureReason = "loop not in LoopSimplify form";
745 BasicBlock *Latch = L.getLoopLatch();
746 assert(Latch && "Simplified loops only have one latch!");
748 if (Latch->getTerminator()->getMetadata(ClonedLoopTag)) {
749 FailureReason = "loop has already been cloned";
753 if (!L.isLoopExiting(Latch)) {
754 FailureReason = "no loop latch";
758 BasicBlock *Header = L.getHeader();
759 BasicBlock *Preheader = L.getLoopPreheader();
761 FailureReason = "no preheader";
765 BranchInst *LatchBr = dyn_cast<BranchInst>(Latch->getTerminator());
766 if (!LatchBr || LatchBr->isUnconditional()) {
767 FailureReason = "latch terminator not conditional branch";
771 unsigned LatchBrExitIdx = LatchBr->getSuccessor(0) == Header ? 1 : 0;
773 BranchProbability ExitProbability =
774 BPI ? BPI->getEdgeProbability(LatchBr->getParent(), LatchBrExitIdx)
775 : BranchProbability::getZero();
777 if (!SkipProfitabilityChecks &&
778 ExitProbability > BranchProbability(1, MaxExitProbReciprocal)) {
779 FailureReason = "short running loop, not profitable";
783 ICmpInst *ICI = dyn_cast<ICmpInst>(LatchBr->getCondition());
784 if (!ICI || !isa<IntegerType>(ICI->getOperand(0)->getType())) {
785 FailureReason = "latch terminator branch not conditional on integral icmp";
789 const SCEV *LatchCount = SE.getExitCount(&L, Latch);
790 if (isa<SCEVCouldNotCompute>(LatchCount)) {
791 FailureReason = "could not compute latch count";
795 ICmpInst::Predicate Pred = ICI->getPredicate();
796 Value *LeftValue = ICI->getOperand(0);
797 const SCEV *LeftSCEV = SE.getSCEV(LeftValue);
798 IntegerType *IndVarTy = cast<IntegerType>(LeftValue->getType());
800 Value *RightValue = ICI->getOperand(1);
801 const SCEV *RightSCEV = SE.getSCEV(RightValue);
803 // We canonicalize `ICI` such that `LeftSCEV` is an add recurrence.
804 if (!isa<SCEVAddRecExpr>(LeftSCEV)) {
805 if (isa<SCEVAddRecExpr>(RightSCEV)) {
806 std::swap(LeftSCEV, RightSCEV);
807 std::swap(LeftValue, RightValue);
808 Pred = ICmpInst::getSwappedPredicate(Pred);
810 FailureReason = "no add recurrences in the icmp";
815 auto HasNoSignedWrap = [&](const SCEVAddRecExpr *AR) {
816 if (AR->getNoWrapFlags(SCEV::FlagNSW))
819 IntegerType *Ty = cast<IntegerType>(AR->getType());
820 IntegerType *WideTy =
821 IntegerType::get(Ty->getContext(), Ty->getBitWidth() * 2);
823 const SCEVAddRecExpr *ExtendAfterOp =
824 dyn_cast<SCEVAddRecExpr>(SE.getSignExtendExpr(AR, WideTy));
826 const SCEV *ExtendedStart = SE.getSignExtendExpr(AR->getStart(), WideTy);
827 const SCEV *ExtendedStep =
828 SE.getSignExtendExpr(AR->getStepRecurrence(SE), WideTy);
830 bool NoSignedWrap = ExtendAfterOp->getStart() == ExtendedStart &&
831 ExtendAfterOp->getStepRecurrence(SE) == ExtendedStep;
837 // We may have proved this when computing the sign extension above.
838 return AR->getNoWrapFlags(SCEV::FlagNSW) != SCEV::FlagAnyWrap;
841 // `ICI` is interpreted as taking the backedge if the *next* value of the
842 // induction variable satisfies some constraint.
844 const SCEVAddRecExpr *IndVarBase = cast<SCEVAddRecExpr>(LeftSCEV);
845 if (!IndVarBase->isAffine()) {
846 FailureReason = "LHS in icmp not induction variable";
849 const SCEV* StepRec = IndVarBase->getStepRecurrence(SE);
850 if (!isa<SCEVConstant>(StepRec)) {
851 FailureReason = "LHS in icmp not induction variable";
854 ConstantInt *StepCI = cast<SCEVConstant>(StepRec)->getValue();
856 if (ICI->isEquality() && !HasNoSignedWrap(IndVarBase)) {
857 FailureReason = "LHS in icmp needs nsw for equality predicates";
861 assert(!StepCI->isZero() && "Zero step?");
862 bool IsIncreasing = !StepCI->isNegative();
863 bool IsSignedPredicate;
864 const SCEV *StartNext = IndVarBase->getStart();
865 const SCEV *Addend = SE.getNegativeSCEV(IndVarBase->getStepRecurrence(SE));
866 const SCEV *IndVarStart = SE.getAddExpr(StartNext, Addend);
867 const SCEV *Step = SE.getSCEV(StepCI);
869 ConstantInt *One = ConstantInt::get(IndVarTy, 1);
871 bool DecreasedRightValueByOne = false;
872 if (StepCI->isOne()) {
873 // Try to turn eq/ne predicates to those we can work with.
874 if (Pred == ICmpInst::ICMP_NE && LatchBrExitIdx == 1)
875 // while (++i != len) { while (++i < len) {
878 // If both parts are known non-negative, it is profitable to use
879 // unsigned comparison in increasing loop. This allows us to make the
880 // comparison check against "RightSCEV + 1" more optimistic.
881 if (isKnownNonNegativeInLoop(IndVarStart, &L, SE) &&
882 isKnownNonNegativeInLoop(RightSCEV, &L, SE))
883 Pred = ICmpInst::ICMP_ULT;
885 Pred = ICmpInst::ICMP_SLT;
886 else if (Pred == ICmpInst::ICMP_EQ && LatchBrExitIdx == 0) {
887 // while (true) { while (true) {
888 // if (++i == len) ---> if (++i > len - 1)
892 if (IndVarBase->getNoWrapFlags(SCEV::FlagNUW) &&
893 cannotBeMinInLoop(RightSCEV, &L, SE, /*Signed*/false)) {
894 Pred = ICmpInst::ICMP_UGT;
895 RightSCEV = SE.getMinusSCEV(RightSCEV,
896 SE.getOne(RightSCEV->getType()));
897 DecreasedRightValueByOne = true;
898 } else if (cannotBeMinInLoop(RightSCEV, &L, SE, /*Signed*/true)) {
899 Pred = ICmpInst::ICMP_SGT;
900 RightSCEV = SE.getMinusSCEV(RightSCEV,
901 SE.getOne(RightSCEV->getType()));
902 DecreasedRightValueByOne = true;
907 bool LTPred = (Pred == ICmpInst::ICMP_SLT || Pred == ICmpInst::ICMP_ULT);
908 bool GTPred = (Pred == ICmpInst::ICMP_SGT || Pred == ICmpInst::ICMP_UGT);
909 bool FoundExpectedPred =
910 (LTPred && LatchBrExitIdx == 1) || (GTPred && LatchBrExitIdx == 0);
912 if (!FoundExpectedPred) {
913 FailureReason = "expected icmp slt semantically, found something else";
917 IsSignedPredicate = ICmpInst::isSigned(Pred);
918 if (!IsSignedPredicate && !AllowUnsignedLatchCondition) {
919 FailureReason = "unsigned latch conditions are explicitly prohibited";
923 if (!isSafeIncreasingBound(IndVarStart, RightSCEV, Step, Pred,
924 LatchBrExitIdx, &L, SE)) {
925 FailureReason = "Unsafe loop bounds";
928 if (LatchBrExitIdx == 0) {
929 // We need to increase the right value unless we have already decreased
930 // it virtually when we replaced EQ with SGT.
931 if (!DecreasedRightValueByOne) {
932 IRBuilder<> B(Preheader->getTerminator());
933 RightValue = B.CreateAdd(RightValue, One);
936 assert(!DecreasedRightValueByOne &&
937 "Right value can be decreased only for LatchBrExitIdx == 0!");
940 bool IncreasedRightValueByOne = false;
941 if (StepCI->isMinusOne()) {
942 // Try to turn eq/ne predicates to those we can work with.
943 if (Pred == ICmpInst::ICMP_NE && LatchBrExitIdx == 1)
944 // while (--i != len) { while (--i > len) {
947 // We intentionally don't turn the predicate into UGT even if we know
948 // that both operands are non-negative, because it will only pessimize
949 // our check against "RightSCEV - 1".
950 Pred = ICmpInst::ICMP_SGT;
951 else if (Pred == ICmpInst::ICMP_EQ && LatchBrExitIdx == 0) {
952 // while (true) { while (true) {
953 // if (--i == len) ---> if (--i < len + 1)
957 if (IndVarBase->getNoWrapFlags(SCEV::FlagNUW) &&
958 cannotBeMaxInLoop(RightSCEV, &L, SE, /* Signed */ false)) {
959 Pred = ICmpInst::ICMP_ULT;
960 RightSCEV = SE.getAddExpr(RightSCEV, SE.getOne(RightSCEV->getType()));
961 IncreasedRightValueByOne = true;
962 } else if (cannotBeMaxInLoop(RightSCEV, &L, SE, /* Signed */ true)) {
963 Pred = ICmpInst::ICMP_SLT;
964 RightSCEV = SE.getAddExpr(RightSCEV, SE.getOne(RightSCEV->getType()));
965 IncreasedRightValueByOne = true;
970 bool LTPred = (Pred == ICmpInst::ICMP_SLT || Pred == ICmpInst::ICMP_ULT);
971 bool GTPred = (Pred == ICmpInst::ICMP_SGT || Pred == ICmpInst::ICMP_UGT);
973 bool FoundExpectedPred =
974 (GTPred && LatchBrExitIdx == 1) || (LTPred && LatchBrExitIdx == 0);
976 if (!FoundExpectedPred) {
977 FailureReason = "expected icmp sgt semantically, found something else";
982 Pred == ICmpInst::ICMP_SLT || Pred == ICmpInst::ICMP_SGT;
984 if (!IsSignedPredicate && !AllowUnsignedLatchCondition) {
985 FailureReason = "unsigned latch conditions are explicitly prohibited";
989 if (!isSafeDecreasingBound(IndVarStart, RightSCEV, Step, Pred,
990 LatchBrExitIdx, &L, SE)) {
991 FailureReason = "Unsafe bounds";
995 if (LatchBrExitIdx == 0) {
996 // We need to decrease the right value unless we have already increased
997 // it virtually when we replaced EQ with SLT.
998 if (!IncreasedRightValueByOne) {
999 IRBuilder<> B(Preheader->getTerminator());
1000 RightValue = B.CreateSub(RightValue, One);
1003 assert(!IncreasedRightValueByOne &&
1004 "Right value can be increased only for LatchBrExitIdx == 0!");
1007 BasicBlock *LatchExit = LatchBr->getSuccessor(LatchBrExitIdx);
1009 assert(SE.getLoopDisposition(LatchCount, &L) ==
1010 ScalarEvolution::LoopInvariant &&
1011 "loop variant exit count doesn't make sense!");
1013 assert(!L.contains(LatchExit) && "expected an exit block!");
1014 const DataLayout &DL = Preheader->getModule()->getDataLayout();
1015 Value *IndVarStartV =
1016 SCEVExpander(SE, DL, "irce")
1017 .expandCodeFor(IndVarStart, IndVarTy, Preheader->getTerminator());
1018 IndVarStartV->setName("indvar.start");
1020 LoopStructure Result;
1022 Result.Tag = "main";
1023 Result.Header = Header;
1024 Result.Latch = Latch;
1025 Result.LatchBr = LatchBr;
1026 Result.LatchExit = LatchExit;
1027 Result.LatchBrExitIdx = LatchBrExitIdx;
1028 Result.IndVarStart = IndVarStartV;
1029 Result.IndVarStep = StepCI;
1030 Result.IndVarBase = LeftValue;
1031 Result.IndVarIncreasing = IsIncreasing;
1032 Result.LoopExitAt = RightValue;
1033 Result.IsSignedPredicate = IsSignedPredicate;
1035 FailureReason = nullptr;
1040 /// If the type of \p S matches with \p Ty, return \p S. Otherwise, return
1041 /// signed or unsigned extension of \p S to type \p Ty.
1042 static const SCEV *NoopOrExtend(const SCEV *S, Type *Ty, ScalarEvolution &SE,
1044 return Signed ? SE.getNoopOrSignExtend(S, Ty) : SE.getNoopOrZeroExtend(S, Ty);
1047 Optional<LoopConstrainer::SubRanges>
1048 LoopConstrainer::calculateSubRanges(bool IsSignedPredicate) const {
1049 IntegerType *Ty = cast<IntegerType>(LatchTakenCount->getType());
1051 auto *RTy = cast<IntegerType>(Range.getType());
1053 // We only support wide range checks and narrow latches.
1054 if (!AllowNarrowLatchCondition && RTy != Ty)
1056 if (RTy->getBitWidth() < Ty->getBitWidth())
1059 LoopConstrainer::SubRanges Result;
1061 // I think we can be more aggressive here and make this nuw / nsw if the
1062 // addition that feeds into the icmp for the latch's terminating branch is nuw
1063 // / nsw. In any case, a wrapping 2's complement addition is safe.
1064 const SCEV *Start = NoopOrExtend(SE.getSCEV(MainLoopStructure.IndVarStart),
1065 RTy, SE, IsSignedPredicate);
1066 const SCEV *End = NoopOrExtend(SE.getSCEV(MainLoopStructure.LoopExitAt), RTy,
1067 SE, IsSignedPredicate);
1069 bool Increasing = MainLoopStructure.IndVarIncreasing;
1071 // We compute `Smallest` and `Greatest` such that [Smallest, Greatest), or
1072 // [Smallest, GreatestSeen] is the range of values the induction variable
1075 const SCEV *Smallest = nullptr, *Greatest = nullptr, *GreatestSeen = nullptr;
1077 const SCEV *One = SE.getOne(RTy);
1081 // No overflow, because the range [Smallest, GreatestSeen] is not empty.
1082 GreatestSeen = SE.getMinusSCEV(End, One);
1084 // These two computations may sign-overflow. Here is why that is okay:
1086 // We know that the induction variable does not sign-overflow on any
1087 // iteration except the last one, and it starts at `Start` and ends at
1088 // `End`, decrementing by one every time.
1090 // * if `Smallest` sign-overflows we know `End` is `INT_SMAX`. Since the
1091 // induction variable is decreasing we know that that the smallest value
1092 // the loop body is actually executed with is `INT_SMIN` == `Smallest`.
1094 // * if `Greatest` sign-overflows, we know it can only be `INT_SMIN`. In
1095 // that case, `Clamp` will always return `Smallest` and
1096 // [`Result.LowLimit`, `Result.HighLimit`) = [`Smallest`, `Smallest`)
1097 // will be an empty range. Returning an empty range is always safe.
1099 Smallest = SE.getAddExpr(End, One);
1100 Greatest = SE.getAddExpr(Start, One);
1101 GreatestSeen = Start;
1104 auto Clamp = [this, Smallest, Greatest, IsSignedPredicate](const SCEV *S) {
1105 return IsSignedPredicate
1106 ? SE.getSMaxExpr(Smallest, SE.getSMinExpr(Greatest, S))
1107 : SE.getUMaxExpr(Smallest, SE.getUMinExpr(Greatest, S));
1110 // In some cases we can prove that we don't need a pre or post loop.
1111 ICmpInst::Predicate PredLE =
1112 IsSignedPredicate ? ICmpInst::ICMP_SLE : ICmpInst::ICMP_ULE;
1113 ICmpInst::Predicate PredLT =
1114 IsSignedPredicate ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT;
1116 bool ProvablyNoPreloop =
1117 SE.isKnownPredicate(PredLE, Range.getBegin(), Smallest);
1118 if (!ProvablyNoPreloop)
1119 Result.LowLimit = Clamp(Range.getBegin());
1121 bool ProvablyNoPostLoop =
1122 SE.isKnownPredicate(PredLT, GreatestSeen, Range.getEnd());
1123 if (!ProvablyNoPostLoop)
1124 Result.HighLimit = Clamp(Range.getEnd());
1129 void LoopConstrainer::cloneLoop(LoopConstrainer::ClonedLoop &Result,
1130 const char *Tag) const {
1131 for (BasicBlock *BB : OriginalLoop.getBlocks()) {
1132 BasicBlock *Clone = CloneBasicBlock(BB, Result.Map, Twine(".") + Tag, &F);
1133 Result.Blocks.push_back(Clone);
1134 Result.Map[BB] = Clone;
1137 auto GetClonedValue = [&Result](Value *V) {
1138 assert(V && "null values not in domain!");
1139 auto It = Result.Map.find(V);
1140 if (It == Result.Map.end())
1142 return static_cast<Value *>(It->second);
1146 cast<BasicBlock>(GetClonedValue(OriginalLoop.getLoopLatch()));
1147 ClonedLatch->getTerminator()->setMetadata(ClonedLoopTag,
1148 MDNode::get(Ctx, {}));
1150 Result.Structure = MainLoopStructure.map(GetClonedValue);
1151 Result.Structure.Tag = Tag;
1153 for (unsigned i = 0, e = Result.Blocks.size(); i != e; ++i) {
1154 BasicBlock *ClonedBB = Result.Blocks[i];
1155 BasicBlock *OriginalBB = OriginalLoop.getBlocks()[i];
1157 assert(Result.Map[OriginalBB] == ClonedBB && "invariant!");
1159 for (Instruction &I : *ClonedBB)
1160 RemapInstruction(&I, Result.Map,
1161 RF_NoModuleLevelChanges | RF_IgnoreMissingLocals);
1163 // Exit blocks will now have one more predecessor and their PHI nodes need
1164 // to be edited to reflect that. No phi nodes need to be introduced because
1165 // the loop is in LCSSA.
1167 for (auto *SBB : successors(OriginalBB)) {
1168 if (OriginalLoop.contains(SBB))
1169 continue; // not an exit block
1171 for (PHINode &PN : SBB->phis()) {
1172 Value *OldIncoming = PN.getIncomingValueForBlock(OriginalBB);
1173 PN.addIncoming(GetClonedValue(OldIncoming), ClonedBB);
1179 LoopConstrainer::RewrittenRangeInfo LoopConstrainer::changeIterationSpaceEnd(
1180 const LoopStructure &LS, BasicBlock *Preheader, Value *ExitSubloopAt,
1181 BasicBlock *ContinuationBlock) const {
1182 // We start with a loop with a single latch:
1184 // +--------------------+
1188 // +--------+-----------+
1189 // | ----------------\
1191 // +--------v----v------+ |
1195 // +--------------------+ |
1199 // +--------------------+ |
1201 // | latch >----------/
1203 // +-------v------------+
1206 // | +--------------------+
1208 // +---> original exit |
1210 // +--------------------+
1212 // We change the control flow to look like
1215 // +--------------------+
1217 // | preheader >-------------------------+
1219 // +--------v-----------+ |
1220 // | /-------------+ |
1222 // +--------v--v--------+ | |
1224 // | header | | +--------+ |
1226 // +--------------------+ | | +-----v-----v-----------+
1228 // | | | .pseudo.exit |
1230 // | | +-----------v-----------+
1233 // | | +--------v-------------+
1234 // +--------------------+ | | | |
1235 // | | | | | ContinuationBlock |
1236 // | latch >------+ | | |
1237 // | | | +----------------------+
1238 // +---------v----------+ |
1241 // | +---------------^-----+
1243 // +-----> .exit.selector |
1245 // +----------v----------+
1247 // +--------------------+ |
1249 // | original exit <----+
1251 // +--------------------+
1253 RewrittenRangeInfo RRI;
1255 BasicBlock *BBInsertLocation = LS.Latch->getNextNode();
1256 RRI.ExitSelector = BasicBlock::Create(Ctx, Twine(LS.Tag) + ".exit.selector",
1257 &F, BBInsertLocation);
1258 RRI.PseudoExit = BasicBlock::Create(Ctx, Twine(LS.Tag) + ".pseudo.exit", &F,
1261 BranchInst *PreheaderJump = cast<BranchInst>(Preheader->getTerminator());
1262 bool Increasing = LS.IndVarIncreasing;
1263 bool IsSignedPredicate = LS.IsSignedPredicate;
1265 IRBuilder<> B(PreheaderJump);
1266 auto *RangeTy = Range.getBegin()->getType();
1267 auto NoopOrExt = [&](Value *V) {
1268 if (V->getType() == RangeTy)
1270 return IsSignedPredicate ? B.CreateSExt(V, RangeTy, "wide." + V->getName())
1271 : B.CreateZExt(V, RangeTy, "wide." + V->getName());
1274 // EnterLoopCond - is it okay to start executing this `LS'?
1275 Value *EnterLoopCond = nullptr;
1278 ? (IsSignedPredicate ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT)
1279 : (IsSignedPredicate ? ICmpInst::ICMP_SGT : ICmpInst::ICMP_UGT);
1280 Value *IndVarStart = NoopOrExt(LS.IndVarStart);
1281 EnterLoopCond = B.CreateICmp(Pred, IndVarStart, ExitSubloopAt);
1283 B.CreateCondBr(EnterLoopCond, LS.Header, RRI.PseudoExit);
1284 PreheaderJump->eraseFromParent();
1286 LS.LatchBr->setSuccessor(LS.LatchBrExitIdx, RRI.ExitSelector);
1287 B.SetInsertPoint(LS.LatchBr);
1288 Value *IndVarBase = NoopOrExt(LS.IndVarBase);
1289 Value *TakeBackedgeLoopCond = B.CreateICmp(Pred, IndVarBase, ExitSubloopAt);
1291 Value *CondForBranch = LS.LatchBrExitIdx == 1
1292 ? TakeBackedgeLoopCond
1293 : B.CreateNot(TakeBackedgeLoopCond);
1295 LS.LatchBr->setCondition(CondForBranch);
1297 B.SetInsertPoint(RRI.ExitSelector);
1299 // IterationsLeft - are there any more iterations left, given the original
1300 // upper bound on the induction variable? If not, we branch to the "real"
1302 Value *LoopExitAt = NoopOrExt(LS.LoopExitAt);
1303 Value *IterationsLeft = B.CreateICmp(Pred, IndVarBase, LoopExitAt);
1304 B.CreateCondBr(IterationsLeft, RRI.PseudoExit, LS.LatchExit);
1306 BranchInst *BranchToContinuation =
1307 BranchInst::Create(ContinuationBlock, RRI.PseudoExit);
1309 // We emit PHI nodes into `RRI.PseudoExit' that compute the "latest" value of
1310 // each of the PHI nodes in the loop header. This feeds into the initial
1311 // value of the same PHI nodes if/when we continue execution.
1312 for (PHINode &PN : LS.Header->phis()) {
1313 PHINode *NewPHI = PHINode::Create(PN.getType(), 2, PN.getName() + ".copy",
1314 BranchToContinuation);
1316 NewPHI->addIncoming(PN.getIncomingValueForBlock(Preheader), Preheader);
1317 NewPHI->addIncoming(PN.getIncomingValueForBlock(LS.Latch),
1319 RRI.PHIValuesAtPseudoExit.push_back(NewPHI);
1322 RRI.IndVarEnd = PHINode::Create(IndVarBase->getType(), 2, "indvar.end",
1323 BranchToContinuation);
1324 RRI.IndVarEnd->addIncoming(IndVarStart, Preheader);
1325 RRI.IndVarEnd->addIncoming(IndVarBase, RRI.ExitSelector);
1327 // The latch exit now has a branch from `RRI.ExitSelector' instead of
1328 // `LS.Latch'. The PHI nodes need to be updated to reflect that.
1329 LS.LatchExit->replacePhiUsesWith(LS.Latch, RRI.ExitSelector);
1334 void LoopConstrainer::rewriteIncomingValuesForPHIs(
1335 LoopStructure &LS, BasicBlock *ContinuationBlock,
1336 const LoopConstrainer::RewrittenRangeInfo &RRI) const {
1337 unsigned PHIIndex = 0;
1338 for (PHINode &PN : LS.Header->phis())
1339 PN.setIncomingValueForBlock(ContinuationBlock,
1340 RRI.PHIValuesAtPseudoExit[PHIIndex++]);
1342 LS.IndVarStart = RRI.IndVarEnd;
1345 BasicBlock *LoopConstrainer::createPreheader(const LoopStructure &LS,
1346 BasicBlock *OldPreheader,
1347 const char *Tag) const {
1348 BasicBlock *Preheader = BasicBlock::Create(Ctx, Tag, &F, LS.Header);
1349 BranchInst::Create(LS.Header, Preheader);
1351 LS.Header->replacePhiUsesWith(OldPreheader, Preheader);
1356 void LoopConstrainer::addToParentLoopIfNeeded(ArrayRef<BasicBlock *> BBs) {
1357 Loop *ParentLoop = OriginalLoop.getParentLoop();
1361 for (BasicBlock *BB : BBs)
1362 ParentLoop->addBasicBlockToLoop(BB, LI);
1365 Loop *LoopConstrainer::createClonedLoopStructure(Loop *Original, Loop *Parent,
1366 ValueToValueMapTy &VM,
1368 Loop &New = *LI.AllocateLoop();
1370 Parent->addChildLoop(&New);
1372 LI.addTopLevelLoop(&New);
1373 LPMAddNewLoop(&New, IsSubloop);
1375 // Add all of the blocks in Original to the new loop.
1376 for (auto *BB : Original->blocks())
1377 if (LI.getLoopFor(BB) == Original)
1378 New.addBasicBlockToLoop(cast<BasicBlock>(VM[BB]), LI);
1380 // Add all of the subloops to the new loop.
1381 for (Loop *SubLoop : *Original)
1382 createClonedLoopStructure(SubLoop, &New, VM, /* IsSubloop */ true);
1387 bool LoopConstrainer::run() {
1388 BasicBlock *Preheader = nullptr;
1389 LatchTakenCount = SE.getExitCount(&OriginalLoop, MainLoopStructure.Latch);
1390 Preheader = OriginalLoop.getLoopPreheader();
1391 assert(!isa<SCEVCouldNotCompute>(LatchTakenCount) && Preheader != nullptr &&
1394 OriginalPreheader = Preheader;
1395 MainLoopPreheader = Preheader;
1397 bool IsSignedPredicate = MainLoopStructure.IsSignedPredicate;
1398 Optional<SubRanges> MaybeSR = calculateSubRanges(IsSignedPredicate);
1399 if (!MaybeSR.hasValue()) {
1400 LLVM_DEBUG(dbgs() << "irce: could not compute subranges\n");
1404 SubRanges SR = MaybeSR.getValue();
1405 bool Increasing = MainLoopStructure.IndVarIncreasing;
1407 cast<IntegerType>(Range.getBegin()->getType());
1409 SCEVExpander Expander(SE, F.getParent()->getDataLayout(), "irce");
1410 Instruction *InsertPt = OriginalPreheader->getTerminator();
1412 // It would have been better to make `PreLoop' and `PostLoop'
1413 // `Optional<ClonedLoop>'s, but `ValueToValueMapTy' does not have a copy
1415 ClonedLoop PreLoop, PostLoop;
1417 Increasing ? SR.LowLimit.hasValue() : SR.HighLimit.hasValue();
1418 bool NeedsPostLoop =
1419 Increasing ? SR.HighLimit.hasValue() : SR.LowLimit.hasValue();
1421 Value *ExitPreLoopAt = nullptr;
1422 Value *ExitMainLoopAt = nullptr;
1423 const SCEVConstant *MinusOneS =
1424 cast<SCEVConstant>(SE.getConstant(IVTy, -1, true /* isSigned */));
1427 const SCEV *ExitPreLoopAtSCEV = nullptr;
1430 ExitPreLoopAtSCEV = *SR.LowLimit;
1431 else if (cannotBeMinInLoop(*SR.HighLimit, &OriginalLoop, SE,
1433 ExitPreLoopAtSCEV = SE.getAddExpr(*SR.HighLimit, MinusOneS);
1435 LLVM_DEBUG(dbgs() << "irce: could not prove no-overflow when computing "
1436 << "preloop exit limit. HighLimit = "
1437 << *(*SR.HighLimit) << "\n");
1441 if (!isSafeToExpandAt(ExitPreLoopAtSCEV, InsertPt, SE)) {
1442 LLVM_DEBUG(dbgs() << "irce: could not prove that it is safe to expand the"
1443 << " preloop exit limit " << *ExitPreLoopAtSCEV
1444 << " at block " << InsertPt->getParent()->getName()
1449 ExitPreLoopAt = Expander.expandCodeFor(ExitPreLoopAtSCEV, IVTy, InsertPt);
1450 ExitPreLoopAt->setName("exit.preloop.at");
1453 if (NeedsPostLoop) {
1454 const SCEV *ExitMainLoopAtSCEV = nullptr;
1457 ExitMainLoopAtSCEV = *SR.HighLimit;
1458 else if (cannotBeMinInLoop(*SR.LowLimit, &OriginalLoop, SE,
1460 ExitMainLoopAtSCEV = SE.getAddExpr(*SR.LowLimit, MinusOneS);
1462 LLVM_DEBUG(dbgs() << "irce: could not prove no-overflow when computing "
1463 << "mainloop exit limit. LowLimit = "
1464 << *(*SR.LowLimit) << "\n");
1468 if (!isSafeToExpandAt(ExitMainLoopAtSCEV, InsertPt, SE)) {
1469 LLVM_DEBUG(dbgs() << "irce: could not prove that it is safe to expand the"
1470 << " main loop exit limit " << *ExitMainLoopAtSCEV
1471 << " at block " << InsertPt->getParent()->getName()
1476 ExitMainLoopAt = Expander.expandCodeFor(ExitMainLoopAtSCEV, IVTy, InsertPt);
1477 ExitMainLoopAt->setName("exit.mainloop.at");
1480 // We clone these ahead of time so that we don't have to deal with changing
1481 // and temporarily invalid IR as we transform the loops.
1483 cloneLoop(PreLoop, "preloop");
1485 cloneLoop(PostLoop, "postloop");
1487 RewrittenRangeInfo PreLoopRRI;
1490 Preheader->getTerminator()->replaceUsesOfWith(MainLoopStructure.Header,
1491 PreLoop.Structure.Header);
1494 createPreheader(MainLoopStructure, Preheader, "mainloop");
1495 PreLoopRRI = changeIterationSpaceEnd(PreLoop.Structure, Preheader,
1496 ExitPreLoopAt, MainLoopPreheader);
1497 rewriteIncomingValuesForPHIs(MainLoopStructure, MainLoopPreheader,
1501 BasicBlock *PostLoopPreheader = nullptr;
1502 RewrittenRangeInfo PostLoopRRI;
1504 if (NeedsPostLoop) {
1506 createPreheader(PostLoop.Structure, Preheader, "postloop");
1507 PostLoopRRI = changeIterationSpaceEnd(MainLoopStructure, MainLoopPreheader,
1508 ExitMainLoopAt, PostLoopPreheader);
1509 rewriteIncomingValuesForPHIs(PostLoop.Structure, PostLoopPreheader,
1513 BasicBlock *NewMainLoopPreheader =
1514 MainLoopPreheader != Preheader ? MainLoopPreheader : nullptr;
1515 BasicBlock *NewBlocks[] = {PostLoopPreheader, PreLoopRRI.PseudoExit,
1516 PreLoopRRI.ExitSelector, PostLoopRRI.PseudoExit,
1517 PostLoopRRI.ExitSelector, NewMainLoopPreheader};
1519 // Some of the above may be nullptr, filter them out before passing to
1520 // addToParentLoopIfNeeded.
1522 std::remove(std::begin(NewBlocks), std::end(NewBlocks), nullptr);
1524 addToParentLoopIfNeeded(makeArrayRef(std::begin(NewBlocks), NewBlocksEnd));
1528 // We need to first add all the pre and post loop blocks into the loop
1529 // structures (as part of createClonedLoopStructure), and then update the
1530 // LCSSA form and LoopSimplifyForm. This is necessary for correctly updating
1531 // LI when LoopSimplifyForm is generated.
1532 Loop *PreL = nullptr, *PostL = nullptr;
1533 if (!PreLoop.Blocks.empty()) {
1534 PreL = createClonedLoopStructure(&OriginalLoop,
1535 OriginalLoop.getParentLoop(), PreLoop.Map,
1536 /* IsSubLoop */ false);
1539 if (!PostLoop.Blocks.empty()) {
1541 createClonedLoopStructure(&OriginalLoop, OriginalLoop.getParentLoop(),
1542 PostLoop.Map, /* IsSubLoop */ false);
1545 // This function canonicalizes the loop into Loop-Simplify and LCSSA forms.
1546 auto CanonicalizeLoop = [&] (Loop *L, bool IsOriginalLoop) {
1547 formLCSSARecursively(*L, DT, &LI, &SE);
1548 simplifyLoop(L, &DT, &LI, &SE, nullptr, nullptr, true);
1549 // Pre/post loops are slow paths, we do not need to perform any loop
1550 // optimizations on them.
1551 if (!IsOriginalLoop)
1552 DisableAllLoopOptsOnLoop(*L);
1555 CanonicalizeLoop(PreL, false);
1557 CanonicalizeLoop(PostL, false);
1558 CanonicalizeLoop(&OriginalLoop, true);
1563 /// Computes and returns a range of values for the induction variable (IndVar)
1564 /// in which the range check can be safely elided. If it cannot compute such a
1565 /// range, returns None.
1566 Optional<InductiveRangeCheck::Range>
1567 InductiveRangeCheck::computeSafeIterationSpace(
1568 ScalarEvolution &SE, const SCEVAddRecExpr *IndVar,
1569 bool IsLatchSigned) const {
1570 // We can deal when types of latch check and range checks don't match in case
1571 // if latch check is more narrow.
1572 auto *IVType = cast<IntegerType>(IndVar->getType());
1573 auto *RCType = cast<IntegerType>(getBegin()->getType());
1574 if (IVType->getBitWidth() > RCType->getBitWidth())
1576 // IndVar is of the form "A + B * I" (where "I" is the canonical induction
1577 // variable, that may or may not exist as a real llvm::Value in the loop) and
1578 // this inductive range check is a range check on the "C + D * I" ("C" is
1579 // getBegin() and "D" is getStep()). We rewrite the value being range
1580 // checked to "M + N * IndVar" where "N" = "D * B^(-1)" and "M" = "C - NA".
1582 // The actual inequalities we solve are of the form
1584 // 0 <= M + 1 * IndVar < L given L >= 0 (i.e. N == 1)
1586 // Here L stands for upper limit of the safe iteration space.
1587 // The inequality is satisfied by (0 - M) <= IndVar < (L - M). To avoid
1588 // overflows when calculating (0 - M) and (L - M) we, depending on type of
1589 // IV's iteration space, limit the calculations by borders of the iteration
1590 // space. For example, if IndVar is unsigned, (0 - M) overflows for any M > 0.
1591 // If we figured out that "anything greater than (-M) is safe", we strengthen
1592 // this to "everything greater than 0 is safe", assuming that values between
1593 // -M and 0 just do not exist in unsigned iteration space, and we don't want
1594 // to deal with overflown values.
1596 if (!IndVar->isAffine())
1599 const SCEV *A = NoopOrExtend(IndVar->getStart(), RCType, SE, IsLatchSigned);
1600 const SCEVConstant *B = dyn_cast<SCEVConstant>(
1601 NoopOrExtend(IndVar->getStepRecurrence(SE), RCType, SE, IsLatchSigned));
1604 assert(!B->isZero() && "Recurrence with zero step?");
1606 const SCEV *C = getBegin();
1607 const SCEVConstant *D = dyn_cast<SCEVConstant>(getStep());
1611 assert(!D->getValue()->isZero() && "Recurrence with zero step?");
1612 unsigned BitWidth = RCType->getBitWidth();
1613 const SCEV *SIntMax = SE.getConstant(APInt::getSignedMaxValue(BitWidth));
1615 // Subtract Y from X so that it does not go through border of the IV
1616 // iteration space. Mathematically, it is equivalent to:
1618 // ClampedSubtract(X, Y) = min(max(X - Y, INT_MIN), INT_MAX). [1]
1620 // In [1], 'X - Y' is a mathematical subtraction (result is not bounded to
1621 // any width of bit grid). But after we take min/max, the result is
1622 // guaranteed to be within [INT_MIN, INT_MAX].
1624 // In [1], INT_MAX and INT_MIN are respectively signed and unsigned max/min
1625 // values, depending on type of latch condition that defines IV iteration
1627 auto ClampedSubtract = [&](const SCEV *X, const SCEV *Y) {
1628 // FIXME: The current implementation assumes that X is in [0, SINT_MAX].
1629 // This is required to ensure that SINT_MAX - X does not overflow signed and
1630 // that X - Y does not overflow unsigned if Y is negative. Can we lift this
1631 // restriction and make it work for negative X either?
1632 if (IsLatchSigned) {
1633 // X is a number from signed range, Y is interpreted as signed.
1634 // Even if Y is SINT_MAX, (X - Y) does not reach SINT_MIN. So the only
1635 // thing we should care about is that we didn't cross SINT_MAX.
1636 // So, if Y is positive, we subtract Y safely.
1637 // Rule 1: Y > 0 ---> Y.
1638 // If 0 <= -Y <= (SINT_MAX - X), we subtract Y safely.
1639 // Rule 2: Y >=s (X - SINT_MAX) ---> Y.
1640 // If 0 <= (SINT_MAX - X) < -Y, we can only subtract (X - SINT_MAX).
1641 // Rule 3: Y <s (X - SINT_MAX) ---> (X - SINT_MAX).
1642 // It gives us smax(Y, X - SINT_MAX) to subtract in all cases.
1643 const SCEV *XMinusSIntMax = SE.getMinusSCEV(X, SIntMax);
1644 return SE.getMinusSCEV(X, SE.getSMaxExpr(Y, XMinusSIntMax),
1647 // X is a number from unsigned range, Y is interpreted as signed.
1648 // Even if Y is SINT_MIN, (X - Y) does not reach UINT_MAX. So the only
1649 // thing we should care about is that we didn't cross zero.
1650 // So, if Y is negative, we subtract Y safely.
1651 // Rule 1: Y <s 0 ---> Y.
1652 // If 0 <= Y <= X, we subtract Y safely.
1653 // Rule 2: Y <=s X ---> Y.
1654 // If 0 <= X < Y, we should stop at 0 and can only subtract X.
1655 // Rule 3: Y >s X ---> X.
1656 // It gives us smin(X, Y) to subtract in all cases.
1657 return SE.getMinusSCEV(X, SE.getSMinExpr(X, Y), SCEV::FlagNUW);
1659 const SCEV *M = SE.getMinusSCEV(C, A);
1660 const SCEV *Zero = SE.getZero(M->getType());
1662 // This function returns SCEV equal to 1 if X is non-negative 0 otherwise.
1663 auto SCEVCheckNonNegative = [&](const SCEV *X) {
1664 const Loop *L = IndVar->getLoop();
1665 const SCEV *One = SE.getOne(X->getType());
1666 // Can we trivially prove that X is a non-negative or negative value?
1667 if (isKnownNonNegativeInLoop(X, L, SE))
1669 else if (isKnownNegativeInLoop(X, L, SE))
1671 // If not, we will have to figure it out during the execution.
1672 // Function smax(smin(X, 0), -1) + 1 equals to 1 if X >= 0 and 0 if X < 0.
1673 const SCEV *NegOne = SE.getNegativeSCEV(One);
1674 return SE.getAddExpr(SE.getSMaxExpr(SE.getSMinExpr(X, Zero), NegOne), One);
1676 // FIXME: Current implementation of ClampedSubtract implicitly assumes that
1677 // X is non-negative (in sense of a signed value). We need to re-implement
1678 // this function in a way that it will correctly handle negative X as well.
1679 // We use it twice: for X = 0 everything is fine, but for X = getEnd() we can
1680 // end up with a negative X and produce wrong results. So currently we ensure
1681 // that if getEnd() is negative then both ends of the safe range are zero.
1682 // Note that this may pessimize elimination of unsigned range checks against
1684 const SCEV *REnd = getEnd();
1685 const SCEV *EndIsNonNegative = SCEVCheckNonNegative(REnd);
1687 const SCEV *Begin = SE.getMulExpr(ClampedSubtract(Zero, M), EndIsNonNegative);
1688 const SCEV *End = SE.getMulExpr(ClampedSubtract(REnd, M), EndIsNonNegative);
1689 return InductiveRangeCheck::Range(Begin, End);
1692 static Optional<InductiveRangeCheck::Range>
1693 IntersectSignedRange(ScalarEvolution &SE,
1694 const Optional<InductiveRangeCheck::Range> &R1,
1695 const InductiveRangeCheck::Range &R2) {
1696 if (R2.isEmpty(SE, /* IsSigned */ true))
1700 auto &R1Value = R1.getValue();
1701 // We never return empty ranges from this function, and R1 is supposed to be
1702 // a result of intersection. Thus, R1 is never empty.
1703 assert(!R1Value.isEmpty(SE, /* IsSigned */ true) &&
1704 "We should never have empty R1!");
1706 // TODO: we could widen the smaller range and have this work; but for now we
1707 // bail out to keep things simple.
1708 if (R1Value.getType() != R2.getType())
1711 const SCEV *NewBegin = SE.getSMaxExpr(R1Value.getBegin(), R2.getBegin());
1712 const SCEV *NewEnd = SE.getSMinExpr(R1Value.getEnd(), R2.getEnd());
1714 // If the resulting range is empty, just return None.
1715 auto Ret = InductiveRangeCheck::Range(NewBegin, NewEnd);
1716 if (Ret.isEmpty(SE, /* IsSigned */ true))
1721 static Optional<InductiveRangeCheck::Range>
1722 IntersectUnsignedRange(ScalarEvolution &SE,
1723 const Optional<InductiveRangeCheck::Range> &R1,
1724 const InductiveRangeCheck::Range &R2) {
1725 if (R2.isEmpty(SE, /* IsSigned */ false))
1729 auto &R1Value = R1.getValue();
1730 // We never return empty ranges from this function, and R1 is supposed to be
1731 // a result of intersection. Thus, R1 is never empty.
1732 assert(!R1Value.isEmpty(SE, /* IsSigned */ false) &&
1733 "We should never have empty R1!");
1735 // TODO: we could widen the smaller range and have this work; but for now we
1736 // bail out to keep things simple.
1737 if (R1Value.getType() != R2.getType())
1740 const SCEV *NewBegin = SE.getUMaxExpr(R1Value.getBegin(), R2.getBegin());
1741 const SCEV *NewEnd = SE.getUMinExpr(R1Value.getEnd(), R2.getEnd());
1743 // If the resulting range is empty, just return None.
1744 auto Ret = InductiveRangeCheck::Range(NewBegin, NewEnd);
1745 if (Ret.isEmpty(SE, /* IsSigned */ false))
1750 PreservedAnalyses IRCEPass::run(Loop &L, LoopAnalysisManager &AM,
1751 LoopStandardAnalysisResults &AR,
1753 Function *F = L.getHeader()->getParent();
1755 AM.getResult<FunctionAnalysisManagerLoopProxy>(L, AR).getManager();
1756 auto *BPI = FAM.getCachedResult<BranchProbabilityAnalysis>(*F);
1757 InductiveRangeCheckElimination IRCE(AR.SE, BPI, AR.DT, AR.LI);
1758 auto LPMAddNewLoop = [&U](Loop *NL, bool IsSubloop) {
1760 U.addSiblingLoops(NL);
1762 bool Changed = IRCE.run(&L, LPMAddNewLoop);
1764 return PreservedAnalyses::all();
1766 return getLoopPassPreservedAnalyses();
1769 bool IRCELegacyPass::runOnLoop(Loop *L, LPPassManager &LPM) {
1773 ScalarEvolution &SE = getAnalysis<ScalarEvolutionWrapperPass>().getSE();
1774 BranchProbabilityInfo &BPI =
1775 getAnalysis<BranchProbabilityInfoWrapperPass>().getBPI();
1776 auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
1777 auto &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
1778 InductiveRangeCheckElimination IRCE(SE, &BPI, DT, LI);
1779 auto LPMAddNewLoop = [&LPM](Loop *NL, bool /* IsSubLoop */) {
1782 return IRCE.run(L, LPMAddNewLoop);
1785 bool InductiveRangeCheckElimination::run(
1786 Loop *L, function_ref<void(Loop *, bool)> LPMAddNewLoop) {
1787 if (L->getBlocks().size() >= LoopSizeCutoff) {
1788 LLVM_DEBUG(dbgs() << "irce: giving up constraining loop, too large\n");
1792 BasicBlock *Preheader = L->getLoopPreheader();
1794 LLVM_DEBUG(dbgs() << "irce: loop has no preheader, leaving\n");
1798 LLVMContext &Context = Preheader->getContext();
1799 SmallVector<InductiveRangeCheck, 16> RangeChecks;
1801 for (auto BBI : L->getBlocks())
1802 if (BranchInst *TBI = dyn_cast<BranchInst>(BBI->getTerminator()))
1803 InductiveRangeCheck::extractRangeChecksFromBranch(TBI, L, SE, BPI,
1806 if (RangeChecks.empty())
1809 auto PrintRecognizedRangeChecks = [&](raw_ostream &OS) {
1810 OS << "irce: looking at loop "; L->print(OS);
1811 OS << "irce: loop has " << RangeChecks.size()
1812 << " inductive range checks: \n";
1813 for (InductiveRangeCheck &IRC : RangeChecks)
1817 LLVM_DEBUG(PrintRecognizedRangeChecks(dbgs()));
1819 if (PrintRangeChecks)
1820 PrintRecognizedRangeChecks(errs());
1822 const char *FailureReason = nullptr;
1823 Optional<LoopStructure> MaybeLoopStructure =
1824 LoopStructure::parseLoopStructure(SE, BPI, *L, FailureReason);
1825 if (!MaybeLoopStructure.hasValue()) {
1826 LLVM_DEBUG(dbgs() << "irce: could not parse loop structure: "
1827 << FailureReason << "\n";);
1830 LoopStructure LS = MaybeLoopStructure.getValue();
1831 const SCEVAddRecExpr *IndVar =
1832 cast<SCEVAddRecExpr>(SE.getMinusSCEV(SE.getSCEV(LS.IndVarBase), SE.getSCEV(LS.IndVarStep)));
1834 Optional<InductiveRangeCheck::Range> SafeIterRange;
1835 Instruction *ExprInsertPt = Preheader->getTerminator();
1837 SmallVector<InductiveRangeCheck, 4> RangeChecksToEliminate;
1838 // Basing on the type of latch predicate, we interpret the IV iteration range
1839 // as signed or unsigned range. We use different min/max functions (signed or
1840 // unsigned) when intersecting this range with safe iteration ranges implied
1842 auto IntersectRange =
1843 LS.IsSignedPredicate ? IntersectSignedRange : IntersectUnsignedRange;
1845 IRBuilder<> B(ExprInsertPt);
1846 for (InductiveRangeCheck &IRC : RangeChecks) {
1847 auto Result = IRC.computeSafeIterationSpace(SE, IndVar,
1848 LS.IsSignedPredicate);
1849 if (Result.hasValue()) {
1850 auto MaybeSafeIterRange =
1851 IntersectRange(SE, SafeIterRange, Result.getValue());
1852 if (MaybeSafeIterRange.hasValue()) {
1854 !MaybeSafeIterRange.getValue().isEmpty(SE, LS.IsSignedPredicate) &&
1855 "We should never return empty ranges!");
1856 RangeChecksToEliminate.push_back(IRC);
1857 SafeIterRange = MaybeSafeIterRange.getValue();
1862 if (!SafeIterRange.hasValue())
1865 LoopConstrainer LC(*L, LI, LPMAddNewLoop, LS, SE, DT,
1866 SafeIterRange.getValue());
1867 bool Changed = LC.run();
1870 auto PrintConstrainedLoopInfo = [L]() {
1871 dbgs() << "irce: in function ";
1872 dbgs() << L->getHeader()->getParent()->getName() << ": ";
1873 dbgs() << "constrained ";
1877 LLVM_DEBUG(PrintConstrainedLoopInfo());
1879 if (PrintChangedLoops)
1880 PrintConstrainedLoopInfo();
1882 // Optimize away the now-redundant range checks.
1884 for (InductiveRangeCheck &IRC : RangeChecksToEliminate) {
1885 ConstantInt *FoldedRangeCheck = IRC.getPassingDirection()
1886 ? ConstantInt::getTrue(Context)
1887 : ConstantInt::getFalse(Context);
1888 IRC.getCheckUse()->set(FoldedRangeCheck);
1895 Pass *llvm::createInductiveRangeCheckEliminationPass() {
1896 return new IRCELegacyPass();