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/Transforms/Scalar/InductiveRangeCheckElimination.h"
47 #include "llvm/ADT/APInt.h"
48 #include "llvm/ADT/ArrayRef.h"
49 #include "llvm/ADT/None.h"
50 #include "llvm/ADT/Optional.h"
51 #include "llvm/ADT/SmallPtrSet.h"
52 #include "llvm/ADT/SmallVector.h"
53 #include "llvm/ADT/StringRef.h"
54 #include "llvm/ADT/Twine.h"
55 #include "llvm/Analysis/BranchProbabilityInfo.h"
56 #include "llvm/Analysis/LoopAnalysisManager.h"
57 #include "llvm/Analysis/LoopInfo.h"
58 #include "llvm/Analysis/LoopPass.h"
59 #include "llvm/Analysis/ScalarEvolution.h"
60 #include "llvm/Analysis/ScalarEvolutionExpander.h"
61 #include "llvm/Analysis/ScalarEvolutionExpressions.h"
62 #include "llvm/IR/BasicBlock.h"
63 #include "llvm/IR/CFG.h"
64 #include "llvm/IR/Constants.h"
65 #include "llvm/IR/DerivedTypes.h"
66 #include "llvm/IR/Dominators.h"
67 #include "llvm/IR/Function.h"
68 #include "llvm/IR/IRBuilder.h"
69 #include "llvm/IR/InstrTypes.h"
70 #include "llvm/IR/Instructions.h"
71 #include "llvm/IR/Metadata.h"
72 #include "llvm/IR/Module.h"
73 #include "llvm/IR/PatternMatch.h"
74 #include "llvm/IR/Type.h"
75 #include "llvm/IR/Use.h"
76 #include "llvm/IR/User.h"
77 #include "llvm/IR/Value.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 const char *ClonedLoopTag = "irce.loop.clone";
121 #define DEBUG_TYPE "irce"
125 /// An inductive range check is conditional branch in a loop with
127 /// 1. a very cold successor (i.e. the branch jumps to that successor very
132 /// 2. a condition that is provably true for some contiguous range of values
133 /// taken by the containing loop's induction variable.
135 class InductiveRangeCheck {
137 const SCEV *Begin = nullptr;
138 const SCEV *Step = nullptr;
139 const SCEV *End = nullptr;
140 Use *CheckUse = nullptr;
141 bool IsSigned = true;
143 static bool parseRangeCheckICmp(Loop *L, ICmpInst *ICI, ScalarEvolution &SE,
144 Value *&Index, Value *&Length,
148 extractRangeChecksFromCond(Loop *L, ScalarEvolution &SE, Use &ConditionUse,
149 SmallVectorImpl<InductiveRangeCheck> &Checks,
150 SmallPtrSetImpl<Value *> &Visited);
153 const SCEV *getBegin() const { return Begin; }
154 const SCEV *getStep() const { return Step; }
155 const SCEV *getEnd() const { return End; }
156 bool isSigned() const { return IsSigned; }
158 void print(raw_ostream &OS) const {
159 OS << "InductiveRangeCheck:\n";
166 OS << "\n CheckUse: ";
167 getCheckUse()->getUser()->print(OS);
168 OS << " Operand: " << getCheckUse()->getOperandNo() << "\n";
176 Use *getCheckUse() const { return CheckUse; }
178 /// Represents an signed integer range [Range.getBegin(), Range.getEnd()). If
179 /// R.getEnd() le R.getBegin(), then R denotes the empty range.
186 Range(const SCEV *Begin, const SCEV *End) : Begin(Begin), End(End) {
187 assert(Begin->getType() == End->getType() && "ill-typed range!");
190 Type *getType() const { return Begin->getType(); }
191 const SCEV *getBegin() const { return Begin; }
192 const SCEV *getEnd() const { return End; }
193 bool isEmpty(ScalarEvolution &SE, bool IsSigned) const {
197 return SE.isKnownPredicate(ICmpInst::ICMP_SGE, Begin, End);
199 return SE.isKnownPredicate(ICmpInst::ICMP_UGE, Begin, End);
203 /// This is the value the condition of the branch needs to evaluate to for the
204 /// branch to take the hot successor (see (1) above).
205 bool getPassingDirection() { return true; }
207 /// Computes a range for the induction variable (IndVar) in which the range
208 /// check is redundant and can be constant-folded away. The induction
209 /// variable is not required to be the canonical {0,+,1} induction variable.
210 Optional<Range> computeSafeIterationSpace(ScalarEvolution &SE,
211 const SCEVAddRecExpr *IndVar,
212 bool IsLatchSigned) const;
214 /// Parse out a set of inductive range checks from \p BI and append them to \p
217 /// NB! There may be conditions feeding into \p BI that aren't inductive range
218 /// checks, and hence don't end up in \p Checks.
220 extractRangeChecksFromBranch(BranchInst *BI, Loop *L, ScalarEvolution &SE,
221 BranchProbabilityInfo *BPI,
222 SmallVectorImpl<InductiveRangeCheck> &Checks);
225 class InductiveRangeCheckElimination {
227 BranchProbabilityInfo *BPI;
232 InductiveRangeCheckElimination(ScalarEvolution &SE,
233 BranchProbabilityInfo *BPI, DominatorTree &DT,
235 : SE(SE), BPI(BPI), DT(DT), LI(LI) {}
237 bool run(Loop *L, function_ref<void(Loop *, bool)> LPMAddNewLoop);
240 class IRCELegacyPass : public LoopPass {
244 IRCELegacyPass() : LoopPass(ID) {
245 initializeIRCELegacyPassPass(*PassRegistry::getPassRegistry());
248 void getAnalysisUsage(AnalysisUsage &AU) const override {
249 AU.addRequired<BranchProbabilityInfoWrapperPass>();
250 getLoopAnalysisUsage(AU);
253 bool runOnLoop(Loop *L, LPPassManager &LPM) override;
256 } // end anonymous namespace
258 char IRCELegacyPass::ID = 0;
260 INITIALIZE_PASS_BEGIN(IRCELegacyPass, "irce",
261 "Inductive range check elimination", false, false)
262 INITIALIZE_PASS_DEPENDENCY(BranchProbabilityInfoWrapperPass)
263 INITIALIZE_PASS_DEPENDENCY(LoopPass)
264 INITIALIZE_PASS_END(IRCELegacyPass, "irce", "Inductive range check elimination",
267 /// Parse a single ICmp instruction, `ICI`, into a range check. If `ICI` cannot
268 /// be interpreted as a range check, return false and set `Index` and `Length`
269 /// to `nullptr`. Otherwise set `Index` to the value being range checked, and
270 /// set `Length` to the upper limit `Index` is being range checked.
272 InductiveRangeCheck::parseRangeCheckICmp(Loop *L, ICmpInst *ICI,
273 ScalarEvolution &SE, Value *&Index,
274 Value *&Length, bool &IsSigned) {
275 auto IsLoopInvariant = [&SE, L](Value *V) {
276 return SE.isLoopInvariant(SE.getSCEV(V), L);
279 ICmpInst::Predicate Pred = ICI->getPredicate();
280 Value *LHS = ICI->getOperand(0);
281 Value *RHS = ICI->getOperand(1);
287 case ICmpInst::ICMP_SLE:
290 case ICmpInst::ICMP_SGE:
292 if (match(RHS, m_ConstantInt<0>())) {
294 return true; // Lower.
298 case ICmpInst::ICMP_SLT:
301 case ICmpInst::ICMP_SGT:
303 if (match(RHS, m_ConstantInt<-1>())) {
305 return true; // Lower.
308 if (IsLoopInvariant(LHS)) {
311 return true; // Upper.
315 case ICmpInst::ICMP_ULT:
318 case ICmpInst::ICMP_UGT:
320 if (IsLoopInvariant(LHS)) {
323 return true; // Both lower and upper.
328 llvm_unreachable("default clause returns!");
331 void InductiveRangeCheck::extractRangeChecksFromCond(
332 Loop *L, ScalarEvolution &SE, Use &ConditionUse,
333 SmallVectorImpl<InductiveRangeCheck> &Checks,
334 SmallPtrSetImpl<Value *> &Visited) {
335 Value *Condition = ConditionUse.get();
336 if (!Visited.insert(Condition).second)
339 // TODO: Do the same for OR, XOR, NOT etc?
340 if (match(Condition, m_And(m_Value(), m_Value()))) {
341 extractRangeChecksFromCond(L, SE, cast<User>(Condition)->getOperandUse(0),
343 extractRangeChecksFromCond(L, SE, cast<User>(Condition)->getOperandUse(1),
348 ICmpInst *ICI = dyn_cast<ICmpInst>(Condition);
352 Value *Length = nullptr, *Index;
354 if (!parseRangeCheckICmp(L, ICI, SE, Index, Length, IsSigned))
357 const auto *IndexAddRec = dyn_cast<SCEVAddRecExpr>(SE.getSCEV(Index));
359 IndexAddRec && (IndexAddRec->getLoop() == L) && IndexAddRec->isAffine();
364 const SCEV *End = nullptr;
365 // We strengthen "0 <= I" to "0 <= I < INT_SMAX" and "I < L" to "0 <= I < L".
366 // We can potentially do much better here.
368 End = SE.getSCEV(Length);
370 // So far we can only reach this point for Signed range check. This may
371 // change in future. In this case we will need to pick Unsigned max for the
372 // unsigned range check.
373 unsigned BitWidth = cast<IntegerType>(IndexAddRec->getType())->getBitWidth();
374 const SCEV *SIntMax = SE.getConstant(APInt::getSignedMaxValue(BitWidth));
378 InductiveRangeCheck IRC;
380 IRC.Begin = IndexAddRec->getStart();
381 IRC.Step = IndexAddRec->getStepRecurrence(SE);
382 IRC.CheckUse = &ConditionUse;
383 IRC.IsSigned = IsSigned;
384 Checks.push_back(IRC);
387 void InductiveRangeCheck::extractRangeChecksFromBranch(
388 BranchInst *BI, Loop *L, ScalarEvolution &SE, BranchProbabilityInfo *BPI,
389 SmallVectorImpl<InductiveRangeCheck> &Checks) {
390 if (BI->isUnconditional() || BI->getParent() == L->getLoopLatch())
393 BranchProbability LikelyTaken(15, 16);
395 if (!SkipProfitabilityChecks && BPI &&
396 BPI->getEdgeProbability(BI->getParent(), (unsigned)0) < LikelyTaken)
399 SmallPtrSet<Value *, 8> Visited;
400 InductiveRangeCheck::extractRangeChecksFromCond(L, SE, BI->getOperandUse(0),
404 // Add metadata to the loop L to disable loop optimizations. Callers need to
405 // confirm that optimizing loop L is not beneficial.
406 static void DisableAllLoopOptsOnLoop(Loop &L) {
407 // We do not care about any existing loopID related metadata for L, since we
408 // are setting all loop metadata to false.
409 LLVMContext &Context = L.getHeader()->getContext();
410 // Reserve first location for self reference to the LoopID metadata node.
411 MDNode *Dummy = MDNode::get(Context, {});
412 MDNode *DisableUnroll = MDNode::get(
413 Context, {MDString::get(Context, "llvm.loop.unroll.disable")});
415 ConstantAsMetadata::get(ConstantInt::get(Type::getInt1Ty(Context), 0));
416 MDNode *DisableVectorize = MDNode::get(
418 {MDString::get(Context, "llvm.loop.vectorize.enable"), FalseVal});
419 MDNode *DisableLICMVersioning = MDNode::get(
420 Context, {MDString::get(Context, "llvm.loop.licm_versioning.disable")});
421 MDNode *DisableDistribution= MDNode::get(
423 {MDString::get(Context, "llvm.loop.distribute.enable"), FalseVal});
425 MDNode::get(Context, {Dummy, DisableUnroll, DisableVectorize,
426 DisableLICMVersioning, DisableDistribution});
427 // Set operand 0 to refer to the loop id itself.
428 NewLoopID->replaceOperandWith(0, NewLoopID);
429 L.setLoopID(NewLoopID);
434 // Keeps track of the structure of a loop. This is similar to llvm::Loop,
435 // except that it is more lightweight and can track the state of a loop through
436 // changing and potentially invalid IR. This structure also formalizes the
437 // kinds of loops we can deal with -- ones that have a single latch that is also
438 // an exiting block *and* have a canonical induction variable.
439 struct LoopStructure {
440 const char *Tag = "";
442 BasicBlock *Header = nullptr;
443 BasicBlock *Latch = nullptr;
445 // `Latch's terminator instruction is `LatchBr', and it's `LatchBrExitIdx'th
446 // successor is `LatchExit', the exit block of the loop.
447 BranchInst *LatchBr = nullptr;
448 BasicBlock *LatchExit = nullptr;
449 unsigned LatchBrExitIdx = std::numeric_limits<unsigned>::max();
451 // The loop represented by this instance of LoopStructure is semantically
454 // intN_ty inc = IndVarIncreasing ? 1 : -1;
455 // pred_ty predicate = IndVarIncreasing ? ICMP_SLT : ICMP_SGT;
457 // for (intN_ty iv = IndVarStart; predicate(iv, LoopExitAt); iv = IndVarBase)
460 Value *IndVarBase = nullptr;
461 Value *IndVarStart = nullptr;
462 Value *IndVarStep = nullptr;
463 Value *LoopExitAt = nullptr;
464 bool IndVarIncreasing = false;
465 bool IsSignedPredicate = true;
467 LoopStructure() = default;
469 template <typename M> LoopStructure map(M Map) const {
470 LoopStructure Result;
472 Result.Header = cast<BasicBlock>(Map(Header));
473 Result.Latch = cast<BasicBlock>(Map(Latch));
474 Result.LatchBr = cast<BranchInst>(Map(LatchBr));
475 Result.LatchExit = cast<BasicBlock>(Map(LatchExit));
476 Result.LatchBrExitIdx = LatchBrExitIdx;
477 Result.IndVarBase = Map(IndVarBase);
478 Result.IndVarStart = Map(IndVarStart);
479 Result.IndVarStep = Map(IndVarStep);
480 Result.LoopExitAt = Map(LoopExitAt);
481 Result.IndVarIncreasing = IndVarIncreasing;
482 Result.IsSignedPredicate = IsSignedPredicate;
486 static Optional<LoopStructure> parseLoopStructure(ScalarEvolution &,
487 BranchProbabilityInfo *BPI,
488 Loop &, const char *&);
491 /// This class is used to constrain loops to run within a given iteration space.
492 /// The algorithm this class implements is given a Loop and a range [Begin,
493 /// End). The algorithm then tries to break out a "main loop" out of the loop
494 /// it is given in a way that the "main loop" runs with the induction variable
495 /// in a subset of [Begin, End). The algorithm emits appropriate pre and post
496 /// loops to run any remaining iterations. The pre loop runs any iterations in
497 /// which the induction variable is < Begin, and the post loop runs any
498 /// iterations in which the induction variable is >= End.
499 class LoopConstrainer {
500 // The representation of a clone of the original loop we started out with.
503 std::vector<BasicBlock *> Blocks;
505 // `Map` maps values in the clonee into values in the cloned version
506 ValueToValueMapTy Map;
508 // An instance of `LoopStructure` for the cloned loop
509 LoopStructure Structure;
512 // Result of rewriting the range of a loop. See changeIterationSpaceEnd for
513 // more details on what these fields mean.
514 struct RewrittenRangeInfo {
515 BasicBlock *PseudoExit = nullptr;
516 BasicBlock *ExitSelector = nullptr;
517 std::vector<PHINode *> PHIValuesAtPseudoExit;
518 PHINode *IndVarEnd = nullptr;
520 RewrittenRangeInfo() = default;
523 // Calculated subranges we restrict the iteration space of the main loop to.
524 // See the implementation of `calculateSubRanges' for more details on how
525 // these fields are computed. `LowLimit` is None if there is no restriction
526 // on low end of the restricted iteration space of the main loop. `HighLimit`
527 // is None if there is no restriction on high end of the restricted iteration
528 // space of the main loop.
531 Optional<const SCEV *> LowLimit;
532 Optional<const SCEV *> HighLimit;
535 // A utility function that does a `replaceUsesOfWith' on the incoming block
536 // set of a `PHINode' -- replaces instances of `Block' in the `PHINode's
537 // incoming block list with `ReplaceBy'.
538 static void replacePHIBlock(PHINode *PN, BasicBlock *Block,
539 BasicBlock *ReplaceBy);
541 // Compute a safe set of limits for the main loop to run in -- effectively the
542 // intersection of `Range' and the iteration space of the original loop.
543 // Return None if unable to compute the set of subranges.
544 Optional<SubRanges> calculateSubRanges(bool IsSignedPredicate) const;
546 // Clone `OriginalLoop' and return the result in CLResult. The IR after
547 // running `cloneLoop' is well formed except for the PHI nodes in CLResult --
548 // the PHI nodes say that there is an incoming edge from `OriginalPreheader`
549 // but there is no such edge.
550 void cloneLoop(ClonedLoop &CLResult, const char *Tag) const;
552 // Create the appropriate loop structure needed to describe a cloned copy of
553 // `Original`. The clone is described by `VM`.
554 Loop *createClonedLoopStructure(Loop *Original, Loop *Parent,
555 ValueToValueMapTy &VM, bool IsSubloop);
557 // Rewrite the iteration space of the loop denoted by (LS, Preheader). The
558 // iteration space of the rewritten loop ends at ExitLoopAt. The start of the
559 // iteration space is not changed. `ExitLoopAt' is assumed to be slt
560 // `OriginalHeaderCount'.
562 // If there are iterations left to execute, control is made to jump to
563 // `ContinuationBlock', otherwise they take the normal loop exit. The
564 // returned `RewrittenRangeInfo' object is populated as follows:
566 // .PseudoExit is a basic block that unconditionally branches to
567 // `ContinuationBlock'.
569 // .ExitSelector is a basic block that decides, on exit from the loop,
570 // whether to branch to the "true" exit or to `PseudoExit'.
572 // .PHIValuesAtPseudoExit are PHINodes in `PseudoExit' that compute the value
573 // for each PHINode in the loop header on taking the pseudo exit.
575 // After changeIterationSpaceEnd, `Preheader' is no longer a legitimate
576 // preheader because it is made to branch to the loop header only
579 changeIterationSpaceEnd(const LoopStructure &LS, BasicBlock *Preheader,
581 BasicBlock *ContinuationBlock) const;
583 // The loop denoted by `LS' has `OldPreheader' as its preheader. This
584 // function creates a new preheader for `LS' and returns it.
585 BasicBlock *createPreheader(const LoopStructure &LS, BasicBlock *OldPreheader,
586 const char *Tag) const;
588 // `ContinuationBlockAndPreheader' was the continuation block for some call to
589 // `changeIterationSpaceEnd' and is the preheader to the loop denoted by `LS'.
590 // This function rewrites the PHI nodes in `LS.Header' to start with the
592 void rewriteIncomingValuesForPHIs(
593 LoopStructure &LS, BasicBlock *ContinuationBlockAndPreheader,
594 const LoopConstrainer::RewrittenRangeInfo &RRI) const;
596 // Even though we do not preserve any passes at this time, we at least need to
597 // keep the parent loop structure consistent. The `LPPassManager' seems to
598 // verify this after running a loop pass. This function adds the list of
599 // blocks denoted by BBs to this loops parent loop if required.
600 void addToParentLoopIfNeeded(ArrayRef<BasicBlock *> BBs);
602 // Some global state.
608 function_ref<void(Loop *, bool)> LPMAddNewLoop;
610 // Information about the original loop we started out with.
613 const SCEV *LatchTakenCount = nullptr;
614 BasicBlock *OriginalPreheader = nullptr;
616 // The preheader of the main loop. This may or may not be different from
617 // `OriginalPreheader'.
618 BasicBlock *MainLoopPreheader = nullptr;
620 // The range we need to run the main loop in.
621 InductiveRangeCheck::Range Range;
623 // The structure of the main loop (see comment at the beginning of this class
625 LoopStructure MainLoopStructure;
628 LoopConstrainer(Loop &L, LoopInfo &LI,
629 function_ref<void(Loop *, bool)> LPMAddNewLoop,
630 const LoopStructure &LS, ScalarEvolution &SE,
631 DominatorTree &DT, InductiveRangeCheck::Range R)
632 : F(*L.getHeader()->getParent()), Ctx(L.getHeader()->getContext()),
633 SE(SE), DT(DT), LI(LI), LPMAddNewLoop(LPMAddNewLoop), OriginalLoop(L),
634 Range(R), MainLoopStructure(LS) {}
636 // Entry point for the algorithm. Returns true on success.
640 } // end anonymous namespace
642 void LoopConstrainer::replacePHIBlock(PHINode *PN, BasicBlock *Block,
643 BasicBlock *ReplaceBy) {
644 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
645 if (PN->getIncomingBlock(i) == Block)
646 PN->setIncomingBlock(i, ReplaceBy);
649 /// Given a loop with an deccreasing induction variable, is it possible to
650 /// safely calculate the bounds of a new loop using the given Predicate.
651 static bool isSafeDecreasingBound(const SCEV *Start,
652 const SCEV *BoundSCEV, const SCEV *Step,
653 ICmpInst::Predicate Pred,
654 unsigned LatchBrExitIdx,
655 Loop *L, ScalarEvolution &SE) {
656 if (Pred != ICmpInst::ICMP_SLT && Pred != ICmpInst::ICMP_SGT &&
657 Pred != ICmpInst::ICMP_ULT && Pred != ICmpInst::ICMP_UGT)
660 if (!SE.isAvailableAtLoopEntry(BoundSCEV, L))
663 assert(SE.isKnownNegative(Step) && "expecting negative step");
665 LLVM_DEBUG(dbgs() << "irce: isSafeDecreasingBound with:\n");
666 LLVM_DEBUG(dbgs() << "irce: Start: " << *Start << "\n");
667 LLVM_DEBUG(dbgs() << "irce: Step: " << *Step << "\n");
668 LLVM_DEBUG(dbgs() << "irce: BoundSCEV: " << *BoundSCEV << "\n");
669 LLVM_DEBUG(dbgs() << "irce: Pred: " << ICmpInst::getPredicateName(Pred)
671 LLVM_DEBUG(dbgs() << "irce: LatchExitBrIdx: " << LatchBrExitIdx << "\n");
673 bool IsSigned = ICmpInst::isSigned(Pred);
674 // The predicate that we need to check that the induction variable lies
676 ICmpInst::Predicate BoundPred =
677 IsSigned ? CmpInst::ICMP_SGT : CmpInst::ICMP_UGT;
679 if (LatchBrExitIdx == 1)
680 return SE.isLoopEntryGuardedByCond(L, BoundPred, Start, BoundSCEV);
682 assert(LatchBrExitIdx == 0 &&
683 "LatchBrExitIdx should be either 0 or 1");
685 const SCEV *StepPlusOne = SE.getAddExpr(Step, SE.getOne(Step->getType()));
686 unsigned BitWidth = cast<IntegerType>(BoundSCEV->getType())->getBitWidth();
687 APInt Min = IsSigned ? APInt::getSignedMinValue(BitWidth) :
688 APInt::getMinValue(BitWidth);
689 const SCEV *Limit = SE.getMinusSCEV(SE.getConstant(Min), StepPlusOne);
691 const SCEV *MinusOne =
692 SE.getMinusSCEV(BoundSCEV, SE.getOne(BoundSCEV->getType()));
694 return SE.isLoopEntryGuardedByCond(L, BoundPred, Start, MinusOne) &&
695 SE.isLoopEntryGuardedByCond(L, BoundPred, BoundSCEV, Limit);
699 /// Given a loop with an increasing induction variable, is it possible to
700 /// safely calculate the bounds of a new loop using the given Predicate.
701 static bool isSafeIncreasingBound(const SCEV *Start,
702 const SCEV *BoundSCEV, const SCEV *Step,
703 ICmpInst::Predicate Pred,
704 unsigned LatchBrExitIdx,
705 Loop *L, ScalarEvolution &SE) {
706 if (Pred != ICmpInst::ICMP_SLT && Pred != ICmpInst::ICMP_SGT &&
707 Pred != ICmpInst::ICMP_ULT && Pred != ICmpInst::ICMP_UGT)
710 if (!SE.isAvailableAtLoopEntry(BoundSCEV, L))
713 LLVM_DEBUG(dbgs() << "irce: isSafeIncreasingBound with:\n");
714 LLVM_DEBUG(dbgs() << "irce: Start: " << *Start << "\n");
715 LLVM_DEBUG(dbgs() << "irce: Step: " << *Step << "\n");
716 LLVM_DEBUG(dbgs() << "irce: BoundSCEV: " << *BoundSCEV << "\n");
717 LLVM_DEBUG(dbgs() << "irce: Pred: " << ICmpInst::getPredicateName(Pred)
719 LLVM_DEBUG(dbgs() << "irce: LatchExitBrIdx: " << LatchBrExitIdx << "\n");
721 bool IsSigned = ICmpInst::isSigned(Pred);
722 // The predicate that we need to check that the induction variable lies
724 ICmpInst::Predicate BoundPred =
725 IsSigned ? CmpInst::ICMP_SLT : CmpInst::ICMP_ULT;
727 if (LatchBrExitIdx == 1)
728 return SE.isLoopEntryGuardedByCond(L, BoundPred, Start, BoundSCEV);
730 assert(LatchBrExitIdx == 0 && "LatchBrExitIdx should be 0 or 1");
732 const SCEV *StepMinusOne =
733 SE.getMinusSCEV(Step, SE.getOne(Step->getType()));
734 unsigned BitWidth = cast<IntegerType>(BoundSCEV->getType())->getBitWidth();
735 APInt Max = IsSigned ? APInt::getSignedMaxValue(BitWidth) :
736 APInt::getMaxValue(BitWidth);
737 const SCEV *Limit = SE.getMinusSCEV(SE.getConstant(Max), StepMinusOne);
739 return (SE.isLoopEntryGuardedByCond(L, BoundPred, Start,
740 SE.getAddExpr(BoundSCEV, Step)) &&
741 SE.isLoopEntryGuardedByCond(L, BoundPred, BoundSCEV, Limit));
744 Optional<LoopStructure>
745 LoopStructure::parseLoopStructure(ScalarEvolution &SE,
746 BranchProbabilityInfo *BPI, Loop &L,
747 const char *&FailureReason) {
748 if (!L.isLoopSimplifyForm()) {
749 FailureReason = "loop not in LoopSimplify form";
753 BasicBlock *Latch = L.getLoopLatch();
754 assert(Latch && "Simplified loops only have one latch!");
756 if (Latch->getTerminator()->getMetadata(ClonedLoopTag)) {
757 FailureReason = "loop has already been cloned";
761 if (!L.isLoopExiting(Latch)) {
762 FailureReason = "no loop latch";
766 BasicBlock *Header = L.getHeader();
767 BasicBlock *Preheader = L.getLoopPreheader();
769 FailureReason = "no preheader";
773 BranchInst *LatchBr = dyn_cast<BranchInst>(Latch->getTerminator());
774 if (!LatchBr || LatchBr->isUnconditional()) {
775 FailureReason = "latch terminator not conditional branch";
779 unsigned LatchBrExitIdx = LatchBr->getSuccessor(0) == Header ? 1 : 0;
781 BranchProbability ExitProbability =
782 BPI ? BPI->getEdgeProbability(LatchBr->getParent(), LatchBrExitIdx)
783 : BranchProbability::getZero();
785 if (!SkipProfitabilityChecks &&
786 ExitProbability > BranchProbability(1, MaxExitProbReciprocal)) {
787 FailureReason = "short running loop, not profitable";
791 ICmpInst *ICI = dyn_cast<ICmpInst>(LatchBr->getCondition());
792 if (!ICI || !isa<IntegerType>(ICI->getOperand(0)->getType())) {
793 FailureReason = "latch terminator branch not conditional on integral icmp";
797 const SCEV *LatchCount = SE.getExitCount(&L, Latch);
798 if (isa<SCEVCouldNotCompute>(LatchCount)) {
799 FailureReason = "could not compute latch count";
803 ICmpInst::Predicate Pred = ICI->getPredicate();
804 Value *LeftValue = ICI->getOperand(0);
805 const SCEV *LeftSCEV = SE.getSCEV(LeftValue);
806 IntegerType *IndVarTy = cast<IntegerType>(LeftValue->getType());
808 Value *RightValue = ICI->getOperand(1);
809 const SCEV *RightSCEV = SE.getSCEV(RightValue);
811 // We canonicalize `ICI` such that `LeftSCEV` is an add recurrence.
812 if (!isa<SCEVAddRecExpr>(LeftSCEV)) {
813 if (isa<SCEVAddRecExpr>(RightSCEV)) {
814 std::swap(LeftSCEV, RightSCEV);
815 std::swap(LeftValue, RightValue);
816 Pred = ICmpInst::getSwappedPredicate(Pred);
818 FailureReason = "no add recurrences in the icmp";
823 auto HasNoSignedWrap = [&](const SCEVAddRecExpr *AR) {
824 if (AR->getNoWrapFlags(SCEV::FlagNSW))
827 IntegerType *Ty = cast<IntegerType>(AR->getType());
828 IntegerType *WideTy =
829 IntegerType::get(Ty->getContext(), Ty->getBitWidth() * 2);
831 const SCEVAddRecExpr *ExtendAfterOp =
832 dyn_cast<SCEVAddRecExpr>(SE.getSignExtendExpr(AR, WideTy));
834 const SCEV *ExtendedStart = SE.getSignExtendExpr(AR->getStart(), WideTy);
835 const SCEV *ExtendedStep =
836 SE.getSignExtendExpr(AR->getStepRecurrence(SE), WideTy);
838 bool NoSignedWrap = ExtendAfterOp->getStart() == ExtendedStart &&
839 ExtendAfterOp->getStepRecurrence(SE) == ExtendedStep;
845 // We may have proved this when computing the sign extension above.
846 return AR->getNoWrapFlags(SCEV::FlagNSW) != SCEV::FlagAnyWrap;
849 // `ICI` is interpreted as taking the backedge if the *next* value of the
850 // induction variable satisfies some constraint.
852 const SCEVAddRecExpr *IndVarBase = cast<SCEVAddRecExpr>(LeftSCEV);
853 if (!IndVarBase->isAffine()) {
854 FailureReason = "LHS in icmp not induction variable";
857 const SCEV* StepRec = IndVarBase->getStepRecurrence(SE);
858 if (!isa<SCEVConstant>(StepRec)) {
859 FailureReason = "LHS in icmp not induction variable";
862 ConstantInt *StepCI = cast<SCEVConstant>(StepRec)->getValue();
864 if (ICI->isEquality() && !HasNoSignedWrap(IndVarBase)) {
865 FailureReason = "LHS in icmp needs nsw for equality predicates";
869 assert(!StepCI->isZero() && "Zero step?");
870 bool IsIncreasing = !StepCI->isNegative();
871 bool IsSignedPredicate = ICmpInst::isSigned(Pred);
872 const SCEV *StartNext = IndVarBase->getStart();
873 const SCEV *Addend = SE.getNegativeSCEV(IndVarBase->getStepRecurrence(SE));
874 const SCEV *IndVarStart = SE.getAddExpr(StartNext, Addend);
875 const SCEV *Step = SE.getSCEV(StepCI);
877 ConstantInt *One = ConstantInt::get(IndVarTy, 1);
879 bool DecreasedRightValueByOne = false;
880 if (StepCI->isOne()) {
881 // Try to turn eq/ne predicates to those we can work with.
882 if (Pred == ICmpInst::ICMP_NE && LatchBrExitIdx == 1)
883 // while (++i != len) { while (++i < len) {
886 // If both parts are known non-negative, it is profitable to use
887 // unsigned comparison in increasing loop. This allows us to make the
888 // comparison check against "RightSCEV + 1" more optimistic.
889 if (isKnownNonNegativeInLoop(IndVarStart, &L, SE) &&
890 isKnownNonNegativeInLoop(RightSCEV, &L, SE))
891 Pred = ICmpInst::ICMP_ULT;
893 Pred = ICmpInst::ICMP_SLT;
894 else if (Pred == ICmpInst::ICMP_EQ && LatchBrExitIdx == 0) {
895 // while (true) { while (true) {
896 // if (++i == len) ---> if (++i > len - 1)
900 if (IndVarBase->getNoWrapFlags(SCEV::FlagNUW) &&
901 cannotBeMinInLoop(RightSCEV, &L, SE, /*Signed*/false)) {
902 Pred = ICmpInst::ICMP_UGT;
903 RightSCEV = SE.getMinusSCEV(RightSCEV,
904 SE.getOne(RightSCEV->getType()));
905 DecreasedRightValueByOne = true;
906 } else if (cannotBeMinInLoop(RightSCEV, &L, SE, /*Signed*/true)) {
907 Pred = ICmpInst::ICMP_SGT;
908 RightSCEV = SE.getMinusSCEV(RightSCEV,
909 SE.getOne(RightSCEV->getType()));
910 DecreasedRightValueByOne = true;
915 bool LTPred = (Pred == ICmpInst::ICMP_SLT || Pred == ICmpInst::ICMP_ULT);
916 bool GTPred = (Pred == ICmpInst::ICMP_SGT || Pred == ICmpInst::ICMP_UGT);
917 bool FoundExpectedPred =
918 (LTPred && LatchBrExitIdx == 1) || (GTPred && LatchBrExitIdx == 0);
920 if (!FoundExpectedPred) {
921 FailureReason = "expected icmp slt semantically, found something else";
925 IsSignedPredicate = ICmpInst::isSigned(Pred);
926 if (!IsSignedPredicate && !AllowUnsignedLatchCondition) {
927 FailureReason = "unsigned latch conditions are explicitly prohibited";
931 if (!isSafeIncreasingBound(IndVarStart, RightSCEV, Step, Pred,
932 LatchBrExitIdx, &L, SE)) {
933 FailureReason = "Unsafe loop bounds";
936 if (LatchBrExitIdx == 0) {
937 // We need to increase the right value unless we have already decreased
938 // it virtually when we replaced EQ with SGT.
939 if (!DecreasedRightValueByOne) {
940 IRBuilder<> B(Preheader->getTerminator());
941 RightValue = B.CreateAdd(RightValue, One);
944 assert(!DecreasedRightValueByOne &&
945 "Right value can be decreased only for LatchBrExitIdx == 0!");
948 bool IncreasedRightValueByOne = false;
949 if (StepCI->isMinusOne()) {
950 // Try to turn eq/ne predicates to those we can work with.
951 if (Pred == ICmpInst::ICMP_NE && LatchBrExitIdx == 1)
952 // while (--i != len) { while (--i > len) {
955 // We intentionally don't turn the predicate into UGT even if we know
956 // that both operands are non-negative, because it will only pessimize
957 // our check against "RightSCEV - 1".
958 Pred = ICmpInst::ICMP_SGT;
959 else if (Pred == ICmpInst::ICMP_EQ && LatchBrExitIdx == 0) {
960 // while (true) { while (true) {
961 // if (--i == len) ---> if (--i < len + 1)
965 if (IndVarBase->getNoWrapFlags(SCEV::FlagNUW) &&
966 cannotBeMaxInLoop(RightSCEV, &L, SE, /* Signed */ false)) {
967 Pred = ICmpInst::ICMP_ULT;
968 RightSCEV = SE.getAddExpr(RightSCEV, SE.getOne(RightSCEV->getType()));
969 IncreasedRightValueByOne = true;
970 } else if (cannotBeMaxInLoop(RightSCEV, &L, SE, /* Signed */ true)) {
971 Pred = ICmpInst::ICMP_SLT;
972 RightSCEV = SE.getAddExpr(RightSCEV, SE.getOne(RightSCEV->getType()));
973 IncreasedRightValueByOne = true;
978 bool LTPred = (Pred == ICmpInst::ICMP_SLT || Pred == ICmpInst::ICMP_ULT);
979 bool GTPred = (Pred == ICmpInst::ICMP_SGT || Pred == ICmpInst::ICMP_UGT);
981 bool FoundExpectedPred =
982 (GTPred && LatchBrExitIdx == 1) || (LTPred && LatchBrExitIdx == 0);
984 if (!FoundExpectedPred) {
985 FailureReason = "expected icmp sgt semantically, found something else";
990 Pred == ICmpInst::ICMP_SLT || Pred == ICmpInst::ICMP_SGT;
992 if (!IsSignedPredicate && !AllowUnsignedLatchCondition) {
993 FailureReason = "unsigned latch conditions are explicitly prohibited";
997 if (!isSafeDecreasingBound(IndVarStart, RightSCEV, Step, Pred,
998 LatchBrExitIdx, &L, SE)) {
999 FailureReason = "Unsafe bounds";
1003 if (LatchBrExitIdx == 0) {
1004 // We need to decrease the right value unless we have already increased
1005 // it virtually when we replaced EQ with SLT.
1006 if (!IncreasedRightValueByOne) {
1007 IRBuilder<> B(Preheader->getTerminator());
1008 RightValue = B.CreateSub(RightValue, One);
1011 assert(!IncreasedRightValueByOne &&
1012 "Right value can be increased only for LatchBrExitIdx == 0!");
1015 BasicBlock *LatchExit = LatchBr->getSuccessor(LatchBrExitIdx);
1017 assert(SE.getLoopDisposition(LatchCount, &L) ==
1018 ScalarEvolution::LoopInvariant &&
1019 "loop variant exit count doesn't make sense!");
1021 assert(!L.contains(LatchExit) && "expected an exit block!");
1022 const DataLayout &DL = Preheader->getModule()->getDataLayout();
1023 Value *IndVarStartV =
1024 SCEVExpander(SE, DL, "irce")
1025 .expandCodeFor(IndVarStart, IndVarTy, Preheader->getTerminator());
1026 IndVarStartV->setName("indvar.start");
1028 LoopStructure Result;
1030 Result.Tag = "main";
1031 Result.Header = Header;
1032 Result.Latch = Latch;
1033 Result.LatchBr = LatchBr;
1034 Result.LatchExit = LatchExit;
1035 Result.LatchBrExitIdx = LatchBrExitIdx;
1036 Result.IndVarStart = IndVarStartV;
1037 Result.IndVarStep = StepCI;
1038 Result.IndVarBase = LeftValue;
1039 Result.IndVarIncreasing = IsIncreasing;
1040 Result.LoopExitAt = RightValue;
1041 Result.IsSignedPredicate = IsSignedPredicate;
1043 FailureReason = nullptr;
1048 Optional<LoopConstrainer::SubRanges>
1049 LoopConstrainer::calculateSubRanges(bool IsSignedPredicate) const {
1050 IntegerType *Ty = cast<IntegerType>(LatchTakenCount->getType());
1052 if (Range.getType() != Ty)
1055 LoopConstrainer::SubRanges Result;
1057 // I think we can be more aggressive here and make this nuw / nsw if the
1058 // addition that feeds into the icmp for the latch's terminating branch is nuw
1059 // / nsw. In any case, a wrapping 2's complement addition is safe.
1060 const SCEV *Start = SE.getSCEV(MainLoopStructure.IndVarStart);
1061 const SCEV *End = SE.getSCEV(MainLoopStructure.LoopExitAt);
1063 bool Increasing = MainLoopStructure.IndVarIncreasing;
1065 // We compute `Smallest` and `Greatest` such that [Smallest, Greatest), or
1066 // [Smallest, GreatestSeen] is the range of values the induction variable
1069 const SCEV *Smallest = nullptr, *Greatest = nullptr, *GreatestSeen = nullptr;
1071 const SCEV *One = SE.getOne(Ty);
1075 // No overflow, because the range [Smallest, GreatestSeen] is not empty.
1076 GreatestSeen = SE.getMinusSCEV(End, One);
1078 // These two computations may sign-overflow. Here is why that is okay:
1080 // We know that the induction variable does not sign-overflow on any
1081 // iteration except the last one, and it starts at `Start` and ends at
1082 // `End`, decrementing by one every time.
1084 // * if `Smallest` sign-overflows we know `End` is `INT_SMAX`. Since the
1085 // induction variable is decreasing we know that that the smallest value
1086 // the loop body is actually executed with is `INT_SMIN` == `Smallest`.
1088 // * if `Greatest` sign-overflows, we know it can only be `INT_SMIN`. In
1089 // that case, `Clamp` will always return `Smallest` and
1090 // [`Result.LowLimit`, `Result.HighLimit`) = [`Smallest`, `Smallest`)
1091 // will be an empty range. Returning an empty range is always safe.
1093 Smallest = SE.getAddExpr(End, One);
1094 Greatest = SE.getAddExpr(Start, One);
1095 GreatestSeen = Start;
1098 auto Clamp = [this, Smallest, Greatest, IsSignedPredicate](const SCEV *S) {
1099 return IsSignedPredicate
1100 ? SE.getSMaxExpr(Smallest, SE.getSMinExpr(Greatest, S))
1101 : SE.getUMaxExpr(Smallest, SE.getUMinExpr(Greatest, S));
1104 // In some cases we can prove that we don't need a pre or post loop.
1105 ICmpInst::Predicate PredLE =
1106 IsSignedPredicate ? ICmpInst::ICMP_SLE : ICmpInst::ICMP_ULE;
1107 ICmpInst::Predicate PredLT =
1108 IsSignedPredicate ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT;
1110 bool ProvablyNoPreloop =
1111 SE.isKnownPredicate(PredLE, Range.getBegin(), Smallest);
1112 if (!ProvablyNoPreloop)
1113 Result.LowLimit = Clamp(Range.getBegin());
1115 bool ProvablyNoPostLoop =
1116 SE.isKnownPredicate(PredLT, GreatestSeen, Range.getEnd());
1117 if (!ProvablyNoPostLoop)
1118 Result.HighLimit = Clamp(Range.getEnd());
1123 void LoopConstrainer::cloneLoop(LoopConstrainer::ClonedLoop &Result,
1124 const char *Tag) const {
1125 for (BasicBlock *BB : OriginalLoop.getBlocks()) {
1126 BasicBlock *Clone = CloneBasicBlock(BB, Result.Map, Twine(".") + Tag, &F);
1127 Result.Blocks.push_back(Clone);
1128 Result.Map[BB] = Clone;
1131 auto GetClonedValue = [&Result](Value *V) {
1132 assert(V && "null values not in domain!");
1133 auto It = Result.Map.find(V);
1134 if (It == Result.Map.end())
1136 return static_cast<Value *>(It->second);
1140 cast<BasicBlock>(GetClonedValue(OriginalLoop.getLoopLatch()));
1141 ClonedLatch->getTerminator()->setMetadata(ClonedLoopTag,
1142 MDNode::get(Ctx, {}));
1144 Result.Structure = MainLoopStructure.map(GetClonedValue);
1145 Result.Structure.Tag = Tag;
1147 for (unsigned i = 0, e = Result.Blocks.size(); i != e; ++i) {
1148 BasicBlock *ClonedBB = Result.Blocks[i];
1149 BasicBlock *OriginalBB = OriginalLoop.getBlocks()[i];
1151 assert(Result.Map[OriginalBB] == ClonedBB && "invariant!");
1153 for (Instruction &I : *ClonedBB)
1154 RemapInstruction(&I, Result.Map,
1155 RF_NoModuleLevelChanges | RF_IgnoreMissingLocals);
1157 // Exit blocks will now have one more predecessor and their PHI nodes need
1158 // to be edited to reflect that. No phi nodes need to be introduced because
1159 // the loop is in LCSSA.
1161 for (auto *SBB : successors(OriginalBB)) {
1162 if (OriginalLoop.contains(SBB))
1163 continue; // not an exit block
1165 for (PHINode &PN : SBB->phis()) {
1166 Value *OldIncoming = PN.getIncomingValueForBlock(OriginalBB);
1167 PN.addIncoming(GetClonedValue(OldIncoming), ClonedBB);
1173 LoopConstrainer::RewrittenRangeInfo LoopConstrainer::changeIterationSpaceEnd(
1174 const LoopStructure &LS, BasicBlock *Preheader, Value *ExitSubloopAt,
1175 BasicBlock *ContinuationBlock) const {
1176 // We start with a loop with a single latch:
1178 // +--------------------+
1182 // +--------+-----------+
1183 // | ----------------\
1185 // +--------v----v------+ |
1189 // +--------------------+ |
1193 // +--------------------+ |
1195 // | latch >----------/
1197 // +-------v------------+
1200 // | +--------------------+
1202 // +---> original exit |
1204 // +--------------------+
1206 // We change the control flow to look like
1209 // +--------------------+
1211 // | preheader >-------------------------+
1213 // +--------v-----------+ |
1214 // | /-------------+ |
1216 // +--------v--v--------+ | |
1218 // | header | | +--------+ |
1220 // +--------------------+ | | +-----v-----v-----------+
1222 // | | | .pseudo.exit |
1224 // | | +-----------v-----------+
1227 // | | +--------v-------------+
1228 // +--------------------+ | | | |
1229 // | | | | | ContinuationBlock |
1230 // | latch >------+ | | |
1231 // | | | +----------------------+
1232 // +---------v----------+ |
1235 // | +---------------^-----+
1237 // +-----> .exit.selector |
1239 // +----------v----------+
1241 // +--------------------+ |
1243 // | original exit <----+
1245 // +--------------------+
1247 RewrittenRangeInfo RRI;
1249 BasicBlock *BBInsertLocation = LS.Latch->getNextNode();
1250 RRI.ExitSelector = BasicBlock::Create(Ctx, Twine(LS.Tag) + ".exit.selector",
1251 &F, BBInsertLocation);
1252 RRI.PseudoExit = BasicBlock::Create(Ctx, Twine(LS.Tag) + ".pseudo.exit", &F,
1255 BranchInst *PreheaderJump = cast<BranchInst>(Preheader->getTerminator());
1256 bool Increasing = LS.IndVarIncreasing;
1257 bool IsSignedPredicate = LS.IsSignedPredicate;
1259 IRBuilder<> B(PreheaderJump);
1261 // EnterLoopCond - is it okay to start executing this `LS'?
1262 Value *EnterLoopCond = nullptr;
1265 ? (IsSignedPredicate ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT)
1266 : (IsSignedPredicate ? ICmpInst::ICMP_SGT : ICmpInst::ICMP_UGT);
1267 EnterLoopCond = B.CreateICmp(Pred, LS.IndVarStart, ExitSubloopAt);
1269 B.CreateCondBr(EnterLoopCond, LS.Header, RRI.PseudoExit);
1270 PreheaderJump->eraseFromParent();
1272 LS.LatchBr->setSuccessor(LS.LatchBrExitIdx, RRI.ExitSelector);
1273 B.SetInsertPoint(LS.LatchBr);
1274 Value *TakeBackedgeLoopCond = B.CreateICmp(Pred, LS.IndVarBase,
1277 Value *CondForBranch = LS.LatchBrExitIdx == 1
1278 ? TakeBackedgeLoopCond
1279 : B.CreateNot(TakeBackedgeLoopCond);
1281 LS.LatchBr->setCondition(CondForBranch);
1283 B.SetInsertPoint(RRI.ExitSelector);
1285 // IterationsLeft - are there any more iterations left, given the original
1286 // upper bound on the induction variable? If not, we branch to the "real"
1288 Value *IterationsLeft = B.CreateICmp(Pred, LS.IndVarBase, LS.LoopExitAt);
1289 B.CreateCondBr(IterationsLeft, RRI.PseudoExit, LS.LatchExit);
1291 BranchInst *BranchToContinuation =
1292 BranchInst::Create(ContinuationBlock, RRI.PseudoExit);
1294 // We emit PHI nodes into `RRI.PseudoExit' that compute the "latest" value of
1295 // each of the PHI nodes in the loop header. This feeds into the initial
1296 // value of the same PHI nodes if/when we continue execution.
1297 for (PHINode &PN : LS.Header->phis()) {
1298 PHINode *NewPHI = PHINode::Create(PN.getType(), 2, PN.getName() + ".copy",
1299 BranchToContinuation);
1301 NewPHI->addIncoming(PN.getIncomingValueForBlock(Preheader), Preheader);
1302 NewPHI->addIncoming(PN.getIncomingValueForBlock(LS.Latch),
1304 RRI.PHIValuesAtPseudoExit.push_back(NewPHI);
1307 RRI.IndVarEnd = PHINode::Create(LS.IndVarBase->getType(), 2, "indvar.end",
1308 BranchToContinuation);
1309 RRI.IndVarEnd->addIncoming(LS.IndVarStart, Preheader);
1310 RRI.IndVarEnd->addIncoming(LS.IndVarBase, RRI.ExitSelector);
1312 // The latch exit now has a branch from `RRI.ExitSelector' instead of
1313 // `LS.Latch'. The PHI nodes need to be updated to reflect that.
1314 for (PHINode &PN : LS.LatchExit->phis())
1315 replacePHIBlock(&PN, LS.Latch, RRI.ExitSelector);
1320 void LoopConstrainer::rewriteIncomingValuesForPHIs(
1321 LoopStructure &LS, BasicBlock *ContinuationBlock,
1322 const LoopConstrainer::RewrittenRangeInfo &RRI) const {
1323 unsigned PHIIndex = 0;
1324 for (PHINode &PN : LS.Header->phis())
1325 for (unsigned i = 0, e = PN.getNumIncomingValues(); i < e; ++i)
1326 if (PN.getIncomingBlock(i) == ContinuationBlock)
1327 PN.setIncomingValue(i, RRI.PHIValuesAtPseudoExit[PHIIndex++]);
1329 LS.IndVarStart = RRI.IndVarEnd;
1332 BasicBlock *LoopConstrainer::createPreheader(const LoopStructure &LS,
1333 BasicBlock *OldPreheader,
1334 const char *Tag) const {
1335 BasicBlock *Preheader = BasicBlock::Create(Ctx, Tag, &F, LS.Header);
1336 BranchInst::Create(LS.Header, Preheader);
1338 for (PHINode &PN : LS.Header->phis())
1339 for (unsigned i = 0, e = PN.getNumIncomingValues(); i < e; ++i)
1340 replacePHIBlock(&PN, OldPreheader, Preheader);
1345 void LoopConstrainer::addToParentLoopIfNeeded(ArrayRef<BasicBlock *> BBs) {
1346 Loop *ParentLoop = OriginalLoop.getParentLoop();
1350 for (BasicBlock *BB : BBs)
1351 ParentLoop->addBasicBlockToLoop(BB, LI);
1354 Loop *LoopConstrainer::createClonedLoopStructure(Loop *Original, Loop *Parent,
1355 ValueToValueMapTy &VM,
1357 Loop &New = *LI.AllocateLoop();
1359 Parent->addChildLoop(&New);
1361 LI.addTopLevelLoop(&New);
1362 LPMAddNewLoop(&New, IsSubloop);
1364 // Add all of the blocks in Original to the new loop.
1365 for (auto *BB : Original->blocks())
1366 if (LI.getLoopFor(BB) == Original)
1367 New.addBasicBlockToLoop(cast<BasicBlock>(VM[BB]), LI);
1369 // Add all of the subloops to the new loop.
1370 for (Loop *SubLoop : *Original)
1371 createClonedLoopStructure(SubLoop, &New, VM, /* IsSubloop */ true);
1376 bool LoopConstrainer::run() {
1377 BasicBlock *Preheader = nullptr;
1378 LatchTakenCount = SE.getExitCount(&OriginalLoop, MainLoopStructure.Latch);
1379 Preheader = OriginalLoop.getLoopPreheader();
1380 assert(!isa<SCEVCouldNotCompute>(LatchTakenCount) && Preheader != nullptr &&
1383 OriginalPreheader = Preheader;
1384 MainLoopPreheader = Preheader;
1386 bool IsSignedPredicate = MainLoopStructure.IsSignedPredicate;
1387 Optional<SubRanges> MaybeSR = calculateSubRanges(IsSignedPredicate);
1388 if (!MaybeSR.hasValue()) {
1389 LLVM_DEBUG(dbgs() << "irce: could not compute subranges\n");
1393 SubRanges SR = MaybeSR.getValue();
1394 bool Increasing = MainLoopStructure.IndVarIncreasing;
1396 cast<IntegerType>(MainLoopStructure.IndVarBase->getType());
1398 SCEVExpander Expander(SE, F.getParent()->getDataLayout(), "irce");
1399 Instruction *InsertPt = OriginalPreheader->getTerminator();
1401 // It would have been better to make `PreLoop' and `PostLoop'
1402 // `Optional<ClonedLoop>'s, but `ValueToValueMapTy' does not have a copy
1404 ClonedLoop PreLoop, PostLoop;
1406 Increasing ? SR.LowLimit.hasValue() : SR.HighLimit.hasValue();
1407 bool NeedsPostLoop =
1408 Increasing ? SR.HighLimit.hasValue() : SR.LowLimit.hasValue();
1410 Value *ExitPreLoopAt = nullptr;
1411 Value *ExitMainLoopAt = nullptr;
1412 const SCEVConstant *MinusOneS =
1413 cast<SCEVConstant>(SE.getConstant(IVTy, -1, true /* isSigned */));
1416 const SCEV *ExitPreLoopAtSCEV = nullptr;
1419 ExitPreLoopAtSCEV = *SR.LowLimit;
1420 else if (cannotBeMinInLoop(*SR.HighLimit, &OriginalLoop, SE,
1422 ExitPreLoopAtSCEV = SE.getAddExpr(*SR.HighLimit, MinusOneS);
1424 LLVM_DEBUG(dbgs() << "irce: could not prove no-overflow when computing "
1425 << "preloop exit limit. HighLimit = "
1426 << *(*SR.HighLimit) << "\n");
1430 if (!isSafeToExpandAt(ExitPreLoopAtSCEV, InsertPt, SE)) {
1431 LLVM_DEBUG(dbgs() << "irce: could not prove that it is safe to expand the"
1432 << " preloop exit limit " << *ExitPreLoopAtSCEV
1433 << " at block " << InsertPt->getParent()->getName()
1438 ExitPreLoopAt = Expander.expandCodeFor(ExitPreLoopAtSCEV, IVTy, InsertPt);
1439 ExitPreLoopAt->setName("exit.preloop.at");
1442 if (NeedsPostLoop) {
1443 const SCEV *ExitMainLoopAtSCEV = nullptr;
1446 ExitMainLoopAtSCEV = *SR.HighLimit;
1447 else if (cannotBeMinInLoop(*SR.LowLimit, &OriginalLoop, SE,
1449 ExitMainLoopAtSCEV = SE.getAddExpr(*SR.LowLimit, MinusOneS);
1451 LLVM_DEBUG(dbgs() << "irce: could not prove no-overflow when computing "
1452 << "mainloop exit limit. LowLimit = "
1453 << *(*SR.LowLimit) << "\n");
1457 if (!isSafeToExpandAt(ExitMainLoopAtSCEV, InsertPt, SE)) {
1458 LLVM_DEBUG(dbgs() << "irce: could not prove that it is safe to expand the"
1459 << " main loop exit limit " << *ExitMainLoopAtSCEV
1460 << " at block " << InsertPt->getParent()->getName()
1465 ExitMainLoopAt = Expander.expandCodeFor(ExitMainLoopAtSCEV, IVTy, InsertPt);
1466 ExitMainLoopAt->setName("exit.mainloop.at");
1469 // We clone these ahead of time so that we don't have to deal with changing
1470 // and temporarily invalid IR as we transform the loops.
1472 cloneLoop(PreLoop, "preloop");
1474 cloneLoop(PostLoop, "postloop");
1476 RewrittenRangeInfo PreLoopRRI;
1479 Preheader->getTerminator()->replaceUsesOfWith(MainLoopStructure.Header,
1480 PreLoop.Structure.Header);
1483 createPreheader(MainLoopStructure, Preheader, "mainloop");
1484 PreLoopRRI = changeIterationSpaceEnd(PreLoop.Structure, Preheader,
1485 ExitPreLoopAt, MainLoopPreheader);
1486 rewriteIncomingValuesForPHIs(MainLoopStructure, MainLoopPreheader,
1490 BasicBlock *PostLoopPreheader = nullptr;
1491 RewrittenRangeInfo PostLoopRRI;
1493 if (NeedsPostLoop) {
1495 createPreheader(PostLoop.Structure, Preheader, "postloop");
1496 PostLoopRRI = changeIterationSpaceEnd(MainLoopStructure, MainLoopPreheader,
1497 ExitMainLoopAt, PostLoopPreheader);
1498 rewriteIncomingValuesForPHIs(PostLoop.Structure, PostLoopPreheader,
1502 BasicBlock *NewMainLoopPreheader =
1503 MainLoopPreheader != Preheader ? MainLoopPreheader : nullptr;
1504 BasicBlock *NewBlocks[] = {PostLoopPreheader, PreLoopRRI.PseudoExit,
1505 PreLoopRRI.ExitSelector, PostLoopRRI.PseudoExit,
1506 PostLoopRRI.ExitSelector, NewMainLoopPreheader};
1508 // Some of the above may be nullptr, filter them out before passing to
1509 // addToParentLoopIfNeeded.
1511 std::remove(std::begin(NewBlocks), std::end(NewBlocks), nullptr);
1513 addToParentLoopIfNeeded(makeArrayRef(std::begin(NewBlocks), NewBlocksEnd));
1517 // We need to first add all the pre and post loop blocks into the loop
1518 // structures (as part of createClonedLoopStructure), and then update the
1519 // LCSSA form and LoopSimplifyForm. This is necessary for correctly updating
1520 // LI when LoopSimplifyForm is generated.
1521 Loop *PreL = nullptr, *PostL = nullptr;
1522 if (!PreLoop.Blocks.empty()) {
1523 PreL = createClonedLoopStructure(&OriginalLoop,
1524 OriginalLoop.getParentLoop(), PreLoop.Map,
1525 /* IsSubLoop */ false);
1528 if (!PostLoop.Blocks.empty()) {
1530 createClonedLoopStructure(&OriginalLoop, OriginalLoop.getParentLoop(),
1531 PostLoop.Map, /* IsSubLoop */ false);
1534 // This function canonicalizes the loop into Loop-Simplify and LCSSA forms.
1535 auto CanonicalizeLoop = [&] (Loop *L, bool IsOriginalLoop) {
1536 formLCSSARecursively(*L, DT, &LI, &SE);
1537 simplifyLoop(L, &DT, &LI, &SE, nullptr, true);
1538 // Pre/post loops are slow paths, we do not need to perform any loop
1539 // optimizations on them.
1540 if (!IsOriginalLoop)
1541 DisableAllLoopOptsOnLoop(*L);
1544 CanonicalizeLoop(PreL, false);
1546 CanonicalizeLoop(PostL, false);
1547 CanonicalizeLoop(&OriginalLoop, true);
1552 /// Computes and returns a range of values for the induction variable (IndVar)
1553 /// in which the range check can be safely elided. If it cannot compute such a
1554 /// range, returns None.
1555 Optional<InductiveRangeCheck::Range>
1556 InductiveRangeCheck::computeSafeIterationSpace(
1557 ScalarEvolution &SE, const SCEVAddRecExpr *IndVar,
1558 bool IsLatchSigned) const {
1559 // IndVar is of the form "A + B * I" (where "I" is the canonical induction
1560 // variable, that may or may not exist as a real llvm::Value in the loop) and
1561 // this inductive range check is a range check on the "C + D * I" ("C" is
1562 // getBegin() and "D" is getStep()). We rewrite the value being range
1563 // checked to "M + N * IndVar" where "N" = "D * B^(-1)" and "M" = "C - NA".
1565 // The actual inequalities we solve are of the form
1567 // 0 <= M + 1 * IndVar < L given L >= 0 (i.e. N == 1)
1569 // Here L stands for upper limit of the safe iteration space.
1570 // The inequality is satisfied by (0 - M) <= IndVar < (L - M). To avoid
1571 // overflows when calculating (0 - M) and (L - M) we, depending on type of
1572 // IV's iteration space, limit the calculations by borders of the iteration
1573 // space. For example, if IndVar is unsigned, (0 - M) overflows for any M > 0.
1574 // If we figured out that "anything greater than (-M) is safe", we strengthen
1575 // this to "everything greater than 0 is safe", assuming that values between
1576 // -M and 0 just do not exist in unsigned iteration space, and we don't want
1577 // to deal with overflown values.
1579 if (!IndVar->isAffine())
1582 const SCEV *A = IndVar->getStart();
1583 const SCEVConstant *B = dyn_cast<SCEVConstant>(IndVar->getStepRecurrence(SE));
1586 assert(!B->isZero() && "Recurrence with zero step?");
1588 const SCEV *C = getBegin();
1589 const SCEVConstant *D = dyn_cast<SCEVConstant>(getStep());
1593 assert(!D->getValue()->isZero() && "Recurrence with zero step?");
1594 unsigned BitWidth = cast<IntegerType>(IndVar->getType())->getBitWidth();
1595 const SCEV *SIntMax = SE.getConstant(APInt::getSignedMaxValue(BitWidth));
1597 // Subtract Y from X so that it does not go through border of the IV
1598 // iteration space. Mathematically, it is equivalent to:
1600 // ClampedSubtract(X, Y) = min(max(X - Y, INT_MIN), INT_MAX). [1]
1602 // In [1], 'X - Y' is a mathematical subtraction (result is not bounded to
1603 // any width of bit grid). But after we take min/max, the result is
1604 // guaranteed to be within [INT_MIN, INT_MAX].
1606 // In [1], INT_MAX and INT_MIN are respectively signed and unsigned max/min
1607 // values, depending on type of latch condition that defines IV iteration
1609 auto ClampedSubtract = [&](const SCEV *X, const SCEV *Y) {
1610 // FIXME: The current implementation assumes that X is in [0, SINT_MAX].
1611 // This is required to ensure that SINT_MAX - X does not overflow signed and
1612 // that X - Y does not overflow unsigned if Y is negative. Can we lift this
1613 // restriction and make it work for negative X either?
1614 if (IsLatchSigned) {
1615 // X is a number from signed range, Y is interpreted as signed.
1616 // Even if Y is SINT_MAX, (X - Y) does not reach SINT_MIN. So the only
1617 // thing we should care about is that we didn't cross SINT_MAX.
1618 // So, if Y is positive, we subtract Y safely.
1619 // Rule 1: Y > 0 ---> Y.
1620 // If 0 <= -Y <= (SINT_MAX - X), we subtract Y safely.
1621 // Rule 2: Y >=s (X - SINT_MAX) ---> Y.
1622 // If 0 <= (SINT_MAX - X) < -Y, we can only subtract (X - SINT_MAX).
1623 // Rule 3: Y <s (X - SINT_MAX) ---> (X - SINT_MAX).
1624 // It gives us smax(Y, X - SINT_MAX) to subtract in all cases.
1625 const SCEV *XMinusSIntMax = SE.getMinusSCEV(X, SIntMax);
1626 return SE.getMinusSCEV(X, SE.getSMaxExpr(Y, XMinusSIntMax),
1629 // X is a number from unsigned range, Y is interpreted as signed.
1630 // Even if Y is SINT_MIN, (X - Y) does not reach UINT_MAX. So the only
1631 // thing we should care about is that we didn't cross zero.
1632 // So, if Y is negative, we subtract Y safely.
1633 // Rule 1: Y <s 0 ---> Y.
1634 // If 0 <= Y <= X, we subtract Y safely.
1635 // Rule 2: Y <=s X ---> Y.
1636 // If 0 <= X < Y, we should stop at 0 and can only subtract X.
1637 // Rule 3: Y >s X ---> X.
1638 // It gives us smin(X, Y) to subtract in all cases.
1639 return SE.getMinusSCEV(X, SE.getSMinExpr(X, Y), SCEV::FlagNUW);
1641 const SCEV *M = SE.getMinusSCEV(C, A);
1642 const SCEV *Zero = SE.getZero(M->getType());
1644 // This function returns SCEV equal to 1 if X is non-negative 0 otherwise.
1645 auto SCEVCheckNonNegative = [&](const SCEV *X) {
1646 const Loop *L = IndVar->getLoop();
1647 const SCEV *One = SE.getOne(X->getType());
1648 // Can we trivially prove that X is a non-negative or negative value?
1649 if (isKnownNonNegativeInLoop(X, L, SE))
1651 else if (isKnownNegativeInLoop(X, L, SE))
1653 // If not, we will have to figure it out during the execution.
1654 // Function smax(smin(X, 0), -1) + 1 equals to 1 if X >= 0 and 0 if X < 0.
1655 const SCEV *NegOne = SE.getNegativeSCEV(One);
1656 return SE.getAddExpr(SE.getSMaxExpr(SE.getSMinExpr(X, Zero), NegOne), One);
1658 // FIXME: Current implementation of ClampedSubtract implicitly assumes that
1659 // X is non-negative (in sense of a signed value). We need to re-implement
1660 // this function in a way that it will correctly handle negative X as well.
1661 // We use it twice: for X = 0 everything is fine, but for X = getEnd() we can
1662 // end up with a negative X and produce wrong results. So currently we ensure
1663 // that if getEnd() is negative then both ends of the safe range are zero.
1664 // Note that this may pessimize elimination of unsigned range checks against
1666 const SCEV *REnd = getEnd();
1667 const SCEV *EndIsNonNegative = SCEVCheckNonNegative(REnd);
1669 const SCEV *Begin = SE.getMulExpr(ClampedSubtract(Zero, M), EndIsNonNegative);
1670 const SCEV *End = SE.getMulExpr(ClampedSubtract(REnd, M), EndIsNonNegative);
1671 return InductiveRangeCheck::Range(Begin, End);
1674 static Optional<InductiveRangeCheck::Range>
1675 IntersectSignedRange(ScalarEvolution &SE,
1676 const Optional<InductiveRangeCheck::Range> &R1,
1677 const InductiveRangeCheck::Range &R2) {
1678 if (R2.isEmpty(SE, /* IsSigned */ true))
1682 auto &R1Value = R1.getValue();
1683 // We never return empty ranges from this function, and R1 is supposed to be
1684 // a result of intersection. Thus, R1 is never empty.
1685 assert(!R1Value.isEmpty(SE, /* IsSigned */ true) &&
1686 "We should never have empty R1!");
1688 // TODO: we could widen the smaller range and have this work; but for now we
1689 // bail out to keep things simple.
1690 if (R1Value.getType() != R2.getType())
1693 const SCEV *NewBegin = SE.getSMaxExpr(R1Value.getBegin(), R2.getBegin());
1694 const SCEV *NewEnd = SE.getSMinExpr(R1Value.getEnd(), R2.getEnd());
1696 // If the resulting range is empty, just return None.
1697 auto Ret = InductiveRangeCheck::Range(NewBegin, NewEnd);
1698 if (Ret.isEmpty(SE, /* IsSigned */ true))
1703 static Optional<InductiveRangeCheck::Range>
1704 IntersectUnsignedRange(ScalarEvolution &SE,
1705 const Optional<InductiveRangeCheck::Range> &R1,
1706 const InductiveRangeCheck::Range &R2) {
1707 if (R2.isEmpty(SE, /* IsSigned */ false))
1711 auto &R1Value = R1.getValue();
1712 // We never return empty ranges from this function, and R1 is supposed to be
1713 // a result of intersection. Thus, R1 is never empty.
1714 assert(!R1Value.isEmpty(SE, /* IsSigned */ false) &&
1715 "We should never have empty R1!");
1717 // TODO: we could widen the smaller range and have this work; but for now we
1718 // bail out to keep things simple.
1719 if (R1Value.getType() != R2.getType())
1722 const SCEV *NewBegin = SE.getUMaxExpr(R1Value.getBegin(), R2.getBegin());
1723 const SCEV *NewEnd = SE.getUMinExpr(R1Value.getEnd(), R2.getEnd());
1725 // If the resulting range is empty, just return None.
1726 auto Ret = InductiveRangeCheck::Range(NewBegin, NewEnd);
1727 if (Ret.isEmpty(SE, /* IsSigned */ false))
1732 PreservedAnalyses IRCEPass::run(Loop &L, LoopAnalysisManager &AM,
1733 LoopStandardAnalysisResults &AR,
1735 Function *F = L.getHeader()->getParent();
1737 AM.getResult<FunctionAnalysisManagerLoopProxy>(L, AR).getManager();
1738 auto *BPI = FAM.getCachedResult<BranchProbabilityAnalysis>(*F);
1739 InductiveRangeCheckElimination IRCE(AR.SE, BPI, AR.DT, AR.LI);
1740 auto LPMAddNewLoop = [&U](Loop *NL, bool IsSubloop) {
1742 U.addSiblingLoops(NL);
1744 bool Changed = IRCE.run(&L, LPMAddNewLoop);
1746 return PreservedAnalyses::all();
1748 return getLoopPassPreservedAnalyses();
1751 bool IRCELegacyPass::runOnLoop(Loop *L, LPPassManager &LPM) {
1755 ScalarEvolution &SE = getAnalysis<ScalarEvolutionWrapperPass>().getSE();
1756 BranchProbabilityInfo &BPI =
1757 getAnalysis<BranchProbabilityInfoWrapperPass>().getBPI();
1758 auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
1759 auto &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
1760 InductiveRangeCheckElimination IRCE(SE, &BPI, DT, LI);
1761 auto LPMAddNewLoop = [&LPM](Loop *NL, bool /* IsSubLoop */) {
1764 return IRCE.run(L, LPMAddNewLoop);
1767 bool InductiveRangeCheckElimination::run(
1768 Loop *L, function_ref<void(Loop *, bool)> LPMAddNewLoop) {
1769 if (L->getBlocks().size() >= LoopSizeCutoff) {
1770 LLVM_DEBUG(dbgs() << "irce: giving up constraining loop, too large\n");
1774 BasicBlock *Preheader = L->getLoopPreheader();
1776 LLVM_DEBUG(dbgs() << "irce: loop has no preheader, leaving\n");
1780 LLVMContext &Context = Preheader->getContext();
1781 SmallVector<InductiveRangeCheck, 16> RangeChecks;
1783 for (auto BBI : L->getBlocks())
1784 if (BranchInst *TBI = dyn_cast<BranchInst>(BBI->getTerminator()))
1785 InductiveRangeCheck::extractRangeChecksFromBranch(TBI, L, SE, BPI,
1788 if (RangeChecks.empty())
1791 auto PrintRecognizedRangeChecks = [&](raw_ostream &OS) {
1792 OS << "irce: looking at loop "; L->print(OS);
1793 OS << "irce: loop has " << RangeChecks.size()
1794 << " inductive range checks: \n";
1795 for (InductiveRangeCheck &IRC : RangeChecks)
1799 LLVM_DEBUG(PrintRecognizedRangeChecks(dbgs()));
1801 if (PrintRangeChecks)
1802 PrintRecognizedRangeChecks(errs());
1804 const char *FailureReason = nullptr;
1805 Optional<LoopStructure> MaybeLoopStructure =
1806 LoopStructure::parseLoopStructure(SE, BPI, *L, FailureReason);
1807 if (!MaybeLoopStructure.hasValue()) {
1808 LLVM_DEBUG(dbgs() << "irce: could not parse loop structure: "
1809 << FailureReason << "\n";);
1812 LoopStructure LS = MaybeLoopStructure.getValue();
1813 const SCEVAddRecExpr *IndVar =
1814 cast<SCEVAddRecExpr>(SE.getMinusSCEV(SE.getSCEV(LS.IndVarBase), SE.getSCEV(LS.IndVarStep)));
1816 Optional<InductiveRangeCheck::Range> SafeIterRange;
1817 Instruction *ExprInsertPt = Preheader->getTerminator();
1819 SmallVector<InductiveRangeCheck, 4> RangeChecksToEliminate;
1820 // Basing on the type of latch predicate, we interpret the IV iteration range
1821 // as signed or unsigned range. We use different min/max functions (signed or
1822 // unsigned) when intersecting this range with safe iteration ranges implied
1824 auto IntersectRange =
1825 LS.IsSignedPredicate ? IntersectSignedRange : IntersectUnsignedRange;
1827 IRBuilder<> B(ExprInsertPt);
1828 for (InductiveRangeCheck &IRC : RangeChecks) {
1829 auto Result = IRC.computeSafeIterationSpace(SE, IndVar,
1830 LS.IsSignedPredicate);
1831 if (Result.hasValue()) {
1832 auto MaybeSafeIterRange =
1833 IntersectRange(SE, SafeIterRange, Result.getValue());
1834 if (MaybeSafeIterRange.hasValue()) {
1836 !MaybeSafeIterRange.getValue().isEmpty(SE, LS.IsSignedPredicate) &&
1837 "We should never return empty ranges!");
1838 RangeChecksToEliminate.push_back(IRC);
1839 SafeIterRange = MaybeSafeIterRange.getValue();
1844 if (!SafeIterRange.hasValue())
1847 LoopConstrainer LC(*L, LI, LPMAddNewLoop, LS, SE, DT,
1848 SafeIterRange.getValue());
1849 bool Changed = LC.run();
1852 auto PrintConstrainedLoopInfo = [L]() {
1853 dbgs() << "irce: in function ";
1854 dbgs() << L->getHeader()->getParent()->getName() << ": ";
1855 dbgs() << "constrained ";
1859 LLVM_DEBUG(PrintConstrainedLoopInfo());
1861 if (PrintChangedLoops)
1862 PrintConstrainedLoopInfo();
1864 // Optimize away the now-redundant range checks.
1866 for (InductiveRangeCheck &IRC : RangeChecksToEliminate) {
1867 ConstantInt *FoldedRangeCheck = IRC.getPassingDirection()
1868 ? ConstantInt::getTrue(Context)
1869 : ConstantInt::getFalse(Context);
1870 IRC.getCheckUse()->set(FoldedRangeCheck);
1877 Pass *llvm::createInductiveRangeCheckEliminationPass() {
1878 return new IRCELegacyPass();