1 //===-- InductiveRangeCheckElimination.cpp - ------------------------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
9 // The InductiveRangeCheckElimination pass splits a loop's iteration space into
10 // three disjoint ranges. It does that in a way such that the loop running in
11 // the middle loop provably does not need range checks. As an example, it will
14 // len = < known positive >
15 // for (i = 0; i < n; i++) {
16 // if (0 <= i && i < len) {
19 // throw_out_of_bounds();
25 // len = < known positive >
26 // limit = smin(n, len)
27 // // no first segment
28 // for (i = 0; i < limit; i++) {
29 // if (0 <= i && i < len) { // this check is fully redundant
32 // throw_out_of_bounds();
35 // for (i = limit; i < n; i++) {
36 // if (0 <= i && i < len) {
39 // throw_out_of_bounds();
42 //===----------------------------------------------------------------------===//
44 #include "llvm/ADT/Optional.h"
46 #include "llvm/Analysis/InstructionSimplify.h"
47 #include "llvm/Analysis/LoopInfo.h"
48 #include "llvm/Analysis/LoopPass.h"
49 #include "llvm/Analysis/ScalarEvolution.h"
50 #include "llvm/Analysis/ScalarEvolutionExpander.h"
51 #include "llvm/Analysis/ScalarEvolutionExpressions.h"
52 #include "llvm/Analysis/ValueTracking.h"
54 #include "llvm/IR/Dominators.h"
55 #include "llvm/IR/Function.h"
56 #include "llvm/IR/Instructions.h"
57 #include "llvm/IR/IRBuilder.h"
58 #include "llvm/IR/Module.h"
59 #include "llvm/IR/PatternMatch.h"
60 #include "llvm/IR/ValueHandle.h"
61 #include "llvm/IR/Verifier.h"
63 #include "llvm/Support/Debug.h"
65 #include "llvm/Transforms/Scalar.h"
66 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
67 #include "llvm/Transforms/Utils/Cloning.h"
68 #include "llvm/Transforms/Utils/LoopUtils.h"
69 #include "llvm/Transforms/Utils/SimplifyIndVar.h"
70 #include "llvm/Transforms/Utils/UnrollLoop.h"
72 #include "llvm/Pass.h"
78 cl::opt<unsigned> LoopSizeCutoff("irce-loop-size-cutoff", cl::Hidden,
81 cl::opt<bool> PrintChangedLoops("irce-print-changed-loops", cl::Hidden,
84 #define DEBUG_TYPE "irce"
88 /// An inductive range check is conditional branch in a loop with
90 /// 1. a very cold successor (i.e. the branch jumps to that successor very
95 /// 2. a condition that is provably true for some range of values taken by the
96 /// containing loop's induction variable.
98 /// Currently all inductive range checks are branches conditional on an
99 /// expression of the form
101 /// 0 <= (Offset + Scale * I) < Length
103 /// where `I' is the canonical induction variable of a loop to which Offset and
104 /// Scale are loop invariant, and Length is >= 0. Currently the 'false' branch
105 /// is considered cold, looking at profiling data to verify that is a TODO.
107 class InductiveRangeCheck {
108 const SCEV *Offset = nullptr;
109 const SCEV *Scale = nullptr;
110 Value *Length = nullptr;
111 BranchInst *Branch = nullptr;
113 InductiveRangeCheck() {}
116 const SCEV *getOffset() const { return Offset; }
117 const SCEV *getScale() const { return Scale; }
118 Value *getLength() const { return Length; }
120 void print(raw_ostream &OS) const {
121 OS << "InductiveRangeCheck:\n";
129 getBranch()->print(OS);
132 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
138 BranchInst *getBranch() const { return Branch; }
140 /// Represents an integer range [Range.first, Range.second). If Range.second
141 /// < Range.first, then the value denotes the empty range.
142 typedef std::pair<Value *, Value *> Range;
143 typedef SpecificBumpPtrAllocator<InductiveRangeCheck> AllocatorTy;
145 /// This is the value the condition of the branch needs to evaluate to for the
146 /// branch to take the hot successor (see (1) above).
147 bool getPassingDirection() { return true; }
149 /// Computes a range for the induction variable in which the range check is
150 /// redundant and can be constant-folded away.
151 Optional<Range> computeSafeIterationSpace(ScalarEvolution &SE,
152 IRBuilder<> &B) const;
154 /// Create an inductive range check out of BI if possible, else return
156 static InductiveRangeCheck *create(AllocatorTy &Alloc, BranchInst *BI,
157 Loop *L, ScalarEvolution &SE);
160 class InductiveRangeCheckElimination : public LoopPass {
161 InductiveRangeCheck::AllocatorTy Allocator;
165 InductiveRangeCheckElimination() : LoopPass(ID) {
166 initializeInductiveRangeCheckEliminationPass(
167 *PassRegistry::getPassRegistry());
170 void getAnalysisUsage(AnalysisUsage &AU) const override {
171 AU.addRequired<LoopInfo>();
172 AU.addRequiredID(LoopSimplifyID);
173 AU.addRequiredID(LCSSAID);
174 AU.addRequired<ScalarEvolution>();
177 bool runOnLoop(Loop *L, LPPassManager &LPM) override;
180 char InductiveRangeCheckElimination::ID = 0;
183 INITIALIZE_PASS(InductiveRangeCheckElimination, "irce",
184 "Inductive range check elimination", false, false)
186 static bool IsLowerBoundCheck(Value *Check, Value *&IndexV) {
187 using namespace llvm::PatternMatch;
189 ICmpInst::Predicate Pred = ICmpInst::BAD_ICMP_PREDICATE;
190 Value *LHS = nullptr, *RHS = nullptr;
192 if (!match(Check, m_ICmp(Pred, m_Value(LHS), m_Value(RHS))))
199 case ICmpInst::ICMP_SLE:
202 case ICmpInst::ICMP_SGE:
203 if (!match(RHS, m_ConstantInt<0>()))
208 case ICmpInst::ICMP_SLT:
211 case ICmpInst::ICMP_SGT:
212 if (!match(RHS, m_ConstantInt<-1>()))
219 static bool IsUpperBoundCheck(Value *Check, Value *Index, Value *&UpperLimit) {
220 using namespace llvm::PatternMatch;
222 ICmpInst::Predicate Pred = ICmpInst::BAD_ICMP_PREDICATE;
223 Value *LHS = nullptr, *RHS = nullptr;
225 if (!match(Check, m_ICmp(Pred, m_Value(LHS), m_Value(RHS))))
232 case ICmpInst::ICMP_SGT:
235 case ICmpInst::ICMP_SLT:
241 case ICmpInst::ICMP_UGT:
244 case ICmpInst::ICMP_ULT:
252 /// Split a condition into something semantically equivalent to (0 <= I <
253 /// Limit), both comparisons signed and Len loop invariant on L and positive.
254 /// On success, return true and set Index to I and UpperLimit to Limit. Return
255 /// false on failure (we may still write to UpperLimit and Index on failure).
256 /// It does not try to interpret I as a loop index.
258 static bool SplitRangeCheckCondition(Loop *L, ScalarEvolution &SE,
259 Value *Condition, const SCEV *&Index,
260 Value *&UpperLimit) {
262 // TODO: currently this catches some silly cases like comparing "%idx slt 1".
263 // Our transformations are still correct, but less likely to be profitable in
264 // those cases. We have to come up with some heuristics that pick out the
265 // range checks that are more profitable to clone a loop for. This function
266 // in general can be made more robust.
268 using namespace llvm::PatternMatch;
272 ICmpInst::Predicate Pred = ICmpInst::BAD_ICMP_PREDICATE;
274 // In these early checks we assume that the matched UpperLimit is positive.
275 // We'll verify that fact later, before returning true.
277 if (match(Condition, m_And(m_Value(A), m_Value(B)))) {
278 Value *IndexV = nullptr;
279 Value *ExpectedUpperBoundCheck = nullptr;
281 if (IsLowerBoundCheck(A, IndexV))
282 ExpectedUpperBoundCheck = B;
283 else if (IsLowerBoundCheck(B, IndexV))
284 ExpectedUpperBoundCheck = A;
288 if (!IsUpperBoundCheck(ExpectedUpperBoundCheck, IndexV, UpperLimit))
291 Index = SE.getSCEV(IndexV);
293 if (isa<SCEVCouldNotCompute>(Index))
296 } else if (match(Condition, m_ICmp(Pred, m_Value(A), m_Value(B)))) {
301 case ICmpInst::ICMP_SGT:
304 case ICmpInst::ICMP_SLT:
306 Index = SE.getSCEV(A);
307 if (isa<SCEVCouldNotCompute>(Index) || !SE.isKnownNonNegative(Index))
311 case ICmpInst::ICMP_UGT:
314 case ICmpInst::ICMP_ULT:
316 Index = SE.getSCEV(A);
317 if (isa<SCEVCouldNotCompute>(Index))
325 const SCEV *UpperLimitSCEV = SE.getSCEV(UpperLimit);
326 if (isa<SCEVCouldNotCompute>(UpperLimitSCEV) ||
327 !SE.isKnownNonNegative(UpperLimitSCEV))
330 if (SE.getLoopDisposition(UpperLimitSCEV, L) !=
331 ScalarEvolution::LoopInvariant) {
332 DEBUG(dbgs() << " in function: " << L->getHeader()->getParent()->getName()
334 dbgs() << " UpperLimit is not loop invariant: "
335 << UpperLimit->getName() << "\n";);
342 InductiveRangeCheck *
343 InductiveRangeCheck::create(InductiveRangeCheck::AllocatorTy &A, BranchInst *BI,
344 Loop *L, ScalarEvolution &SE) {
346 if (BI->isUnconditional() || BI->getParent() == L->getLoopLatch())
349 Value *Length = nullptr;
350 const SCEV *IndexSCEV = nullptr;
352 if (!SplitRangeCheckCondition(L, SE, BI->getCondition(), IndexSCEV, Length))
355 assert(IndexSCEV && Length && "contract with SplitRangeCheckCondition!");
357 const SCEVAddRecExpr *IndexAddRec = dyn_cast<SCEVAddRecExpr>(IndexSCEV);
359 IndexAddRec && (IndexAddRec->getLoop() == L) && IndexAddRec->isAffine();
364 InductiveRangeCheck *IRC = new (A.Allocate()) InductiveRangeCheck;
365 IRC->Length = Length;
366 IRC->Offset = IndexAddRec->getStart();
367 IRC->Scale = IndexAddRec->getStepRecurrence(SE);
372 static Value *MaybeSimplify(Value *V) {
373 if (Instruction *I = dyn_cast<Instruction>(V))
374 if (Value *Simplified = SimplifyInstruction(I))
379 static Value *ConstructSMinOf(Value *X, Value *Y, IRBuilder<> &B) {
380 return MaybeSimplify(B.CreateSelect(B.CreateICmpSLT(X, Y), X, Y));
383 static Value *ConstructSMaxOf(Value *X, Value *Y, IRBuilder<> &B) {
384 return MaybeSimplify(B.CreateSelect(B.CreateICmpSGT(X, Y), X, Y));
389 /// This class is used to constrain loops to run within a given iteration space.
390 /// The algorithm this class implements is given a Loop and a range [Begin,
391 /// End). The algorithm then tries to break out a "main loop" out of the loop
392 /// it is given in a way that the "main loop" runs with the induction variable
393 /// in a subset of [Begin, End). The algorithm emits appropriate pre and post
394 /// loops to run any remaining iterations. The pre loop runs any iterations in
395 /// which the induction variable is < Begin, and the post loop runs any
396 /// iterations in which the induction variable is >= End.
398 class LoopConstrainer {
400 // Keeps track of the structure of a loop. This is similar to llvm::Loop,
401 // except that it is more lightweight and can track the state of a loop
402 // through changing and potentially invalid IR. This structure also
403 // formalizes the kinds of loops we can deal with -- ones that have a single
404 // latch that is also an exiting block *and* have a canonical induction
406 struct LoopStructure {
407 const char *Tag = "";
409 BasicBlock *Header = nullptr;
410 BasicBlock *Latch = nullptr;
412 // `Latch's terminator instruction is `LatchBr', and it's `LatchBrExitIdx'th
413 // successor is `LatchExit', the exit block of the loop.
414 BranchInst *LatchBr = nullptr;
415 BasicBlock *LatchExit = nullptr;
416 unsigned LatchBrExitIdx = -1;
418 // The canonical induction variable. It's value is `CIVStart` on the 0th
419 // itertion and `CIVNext` for all iterations after that.
420 PHINode *CIV = nullptr;
421 Value *CIVStart = nullptr;
422 Value *CIVNext = nullptr;
424 template <typename M> LoopStructure map(M Map) const {
425 LoopStructure Result;
427 Result.Header = cast<BasicBlock>(Map(Header));
428 Result.Latch = cast<BasicBlock>(Map(Latch));
429 Result.LatchBr = cast<BranchInst>(Map(LatchBr));
430 Result.LatchExit = cast<BasicBlock>(Map(LatchExit));
431 Result.LatchBrExitIdx = LatchBrExitIdx;
432 Result.CIV = cast<PHINode>(Map(CIV));
433 Result.CIVNext = Map(CIVNext);
434 Result.CIVStart = Map(CIVStart);
439 // The representation of a clone of the original loop we started out with.
442 std::vector<BasicBlock *> Blocks;
444 // `Map` maps values in the clonee into values in the cloned version
445 ValueToValueMapTy Map;
447 // An instance of `LoopStructure` for the cloned loop
448 LoopStructure Structure;
451 // Result of rewriting the range of a loop. See changeIterationSpaceEnd for
452 // more details on what these fields mean.
453 struct RewrittenRangeInfo {
454 BasicBlock *PseudoExit = nullptr;
455 BasicBlock *ExitSelector = nullptr;
456 std::vector<PHINode *> PHIValuesAtPseudoExit;
459 // Calculated subranges we restrict the iteration space of the main loop to.
460 // See the implementation of `calculateSubRanges' for more details on how
461 // these fields are computed. `ExitPreLoopAt' is `None' if we don't need a
462 // pre loop. `ExitMainLoopAt' is `None' if we don't need a post loop.
464 Optional<Value *> ExitPreLoopAt;
465 Optional<Value *> ExitMainLoopAt;
468 // Some global state.
469 Function *F = nullptr;
473 // Information about the original loop we started out with.
474 Loop *OriginalLoop = nullptr;
475 LoopInfo *OriginalLoopInfo = nullptr;
476 const SCEV *LatchTakenCount = nullptr;
477 BasicBlock *OriginalPreheader = nullptr;
478 Value *OriginalHeaderCount = nullptr;
480 // The range we need to run the main loop in.
481 InductiveRangeCheck::Range Range;
483 // The structure of the main loop (see comment at the beginning of this class
485 LoopStructure MainLoopStructure;
487 // The preheader of the main loop. This may or may not be different from
488 // `OriginalPreheader'.
489 BasicBlock *MainLoopPreheader = nullptr;
491 // A utility function that does a `replaceUsesOfWith' on the incoming block
492 // set of a `PHINode' -- replaces instances of `Block' in the `PHINode's
493 // incoming block list with `ReplaceBy'.
494 static void replacePHIBlock(PHINode *PN, BasicBlock *Block,
495 BasicBlock *ReplaceBy);
497 // Try to "parse" `OriginalLoop' and populate the various out parameters.
498 // Returns true on success, false on failure.
500 bool recognizeLoop(LoopStructure &LoopStructureOut,
501 const SCEV *&LatchCountOut, BasicBlock *&PreHeaderOut,
502 const char *&FailureReasonOut) const;
504 // Compute a safe set of limits for the main loop to run in -- effectively the
505 // intersection of `Range' and the iteration space of the original loop.
506 // Return the header count (1 + the latch taken count) in `HeaderCount'.
508 SubRanges calculateSubRanges(Value *&HeaderCount) const;
510 // Clone `OriginalLoop' and return the result in CLResult. The IR after
511 // running `cloneLoop' is well formed except for the PHI nodes in CLResult --
512 // the PHI nodes say that there is an incoming edge from `OriginalPreheader`
513 // but there is no such edge.
515 void cloneLoop(ClonedLoop &CLResult, const char *Tag) const;
517 // Rewrite the iteration space of the loop denoted by (LS, Preheader). The
518 // iteration space of the rewritten loop ends at ExitLoopAt. The start of the
519 // iteration space is not changed. `ExitLoopAt' is assumed to be slt
520 // `OriginalHeaderCount'.
522 // If there are iterations left to execute, control is made to jump to
523 // `ContinuationBlock', otherwise they take the normal loop exit. The
524 // returned `RewrittenRangeInfo' object is populated as follows:
526 // .PseudoExit is a basic block that unconditionally branches to
527 // `ContinuationBlock'.
529 // .ExitSelector is a basic block that decides, on exit from the loop,
530 // whether to branch to the "true" exit or to `PseudoExit'.
532 // .PHIValuesAtPseudoExit are PHINodes in `PseudoExit' that compute the value
533 // for each PHINode in the loop header on taking the pseudo exit.
535 // After changeIterationSpaceEnd, `Preheader' is no longer a legitimate
536 // preheader because it is made to branch to the loop header only
540 changeIterationSpaceEnd(const LoopStructure &LS, BasicBlock *Preheader,
542 BasicBlock *ContinuationBlock) const;
544 // The loop denoted by `LS' has `OldPreheader' as its preheader. This
545 // function creates a new preheader for `LS' and returns it.
547 BasicBlock *createPreheader(const LoopConstrainer::LoopStructure &LS,
548 BasicBlock *OldPreheader, const char *Tag) const;
550 // `ContinuationBlockAndPreheader' was the continuation block for some call to
551 // `changeIterationSpaceEnd' and is the preheader to the loop denoted by `LS'.
552 // This function rewrites the PHI nodes in `LS.Header' to start with the
554 void rewriteIncomingValuesForPHIs(
555 LoopConstrainer::LoopStructure &LS,
556 BasicBlock *ContinuationBlockAndPreheader,
557 const LoopConstrainer::RewrittenRangeInfo &RRI) const;
559 // Even though we do not preserve any passes at this time, we at least need to
560 // keep the parent loop structure consistent. The `LPPassManager' seems to
561 // verify this after running a loop pass. This function adds the list of
562 // blocks denoted by the iterator range [BlocksBegin, BlocksEnd) to this loops
563 // parent loop if required.
564 template<typename IteratorTy>
565 void addToParentLoopIfNeeded(IteratorTy BlocksBegin, IteratorTy BlocksEnd);
568 LoopConstrainer(Loop *L, LoopInfo *LI, ScalarEvolution &SE,
569 InductiveRangeCheck::Range R)
570 : F(L->getHeader()->getParent()), Ctx(F->getContext()), SE(SE),
571 OriginalLoop(L), OriginalLoopInfo(LI), Range(R) {}
573 // Entry point for the algorithm. Returns true on success.
578 void LoopConstrainer::replacePHIBlock(PHINode *PN, BasicBlock *Block,
579 BasicBlock *ReplaceBy) {
580 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
581 if (PN->getIncomingBlock(i) == Block)
582 PN->setIncomingBlock(i, ReplaceBy);
585 bool LoopConstrainer::recognizeLoop(LoopStructure &LoopStructureOut,
586 const SCEV *&LatchCountOut,
587 BasicBlock *&PreheaderOut,
588 const char *&FailureReason) const {
589 using namespace llvm::PatternMatch;
591 assert(OriginalLoop->isLoopSimplifyForm() &&
592 "should follow from addRequired<>");
594 BasicBlock *Latch = OriginalLoop->getLoopLatch();
595 if (!OriginalLoop->isLoopExiting(Latch)) {
596 FailureReason = "no loop latch";
600 PHINode *CIV = OriginalLoop->getCanonicalInductionVariable();
602 FailureReason = "no CIV";
606 BasicBlock *Header = OriginalLoop->getHeader();
607 BasicBlock *Preheader = OriginalLoop->getLoopPreheader();
609 FailureReason = "no preheader";
613 Value *CIVNext = CIV->getIncomingValueForBlock(Latch);
614 Value *CIVStart = CIV->getIncomingValueForBlock(Preheader);
616 const SCEV *LatchCount = SE.getExitCount(OriginalLoop, Latch);
617 if (isa<SCEVCouldNotCompute>(LatchCount)) {
618 FailureReason = "could not compute latch count";
622 // While SCEV does most of the analysis for us, we still have to
623 // modify the latch; and currently we can only deal with certain
624 // kinds of latches. This can be made more sophisticated as needed.
626 BranchInst *LatchBr = dyn_cast<BranchInst>(&*Latch->rbegin());
628 if (!LatchBr || LatchBr->isUnconditional()) {
629 FailureReason = "latch terminator not conditional branch";
633 // Currently we only support a latch condition of the form:
635 // %condition = icmp slt %civNext, %limit
636 // br i1 %condition, label %header, label %exit
638 if (LatchBr->getSuccessor(0) != Header) {
639 FailureReason = "unknown latch form (header not first successor)";
643 Value *CIVComparedTo = nullptr;
644 ICmpInst::Predicate Pred = ICmpInst::BAD_ICMP_PREDICATE;
645 if (!(match(LatchBr->getCondition(),
646 m_ICmp(Pred, m_Specific(CIVNext), m_Value(CIVComparedTo))) &&
647 Pred == ICmpInst::ICMP_SLT)) {
648 FailureReason = "unknown latch form (not slt)";
652 const SCEV *CIVComparedToSCEV = SE.getSCEV(CIVComparedTo);
653 if (isa<SCEVCouldNotCompute>(CIVComparedToSCEV)) {
654 FailureReason = "could not relate CIV to latch expression";
658 const SCEV *ShouldBeOne = SE.getMinusSCEV(CIVComparedToSCEV, LatchCount);
659 const SCEVConstant *SCEVOne = dyn_cast<SCEVConstant>(ShouldBeOne);
660 if (!SCEVOne || SCEVOne->getValue()->getValue() != 1) {
661 FailureReason = "unexpected header count in latch";
665 unsigned LatchBrExitIdx = 1;
666 BasicBlock *LatchExit = LatchBr->getSuccessor(LatchBrExitIdx);
668 assert(SE.getLoopDisposition(LatchCount, OriginalLoop) ==
669 ScalarEvolution::LoopInvariant &&
670 "loop variant exit count doesn't make sense!");
672 assert(!OriginalLoop->contains(LatchExit) && "expected an exit block!");
674 LoopStructureOut.Tag = "main";
675 LoopStructureOut.Header = Header;
676 LoopStructureOut.Latch = Latch;
677 LoopStructureOut.LatchBr = LatchBr;
678 LoopStructureOut.LatchExit = LatchExit;
679 LoopStructureOut.LatchBrExitIdx = LatchBrExitIdx;
680 LoopStructureOut.CIV = CIV;
681 LoopStructureOut.CIVNext = CIVNext;
682 LoopStructureOut.CIVStart = CIVStart;
684 LatchCountOut = LatchCount;
685 PreheaderOut = Preheader;
686 FailureReason = nullptr;
691 LoopConstrainer::SubRanges
692 LoopConstrainer::calculateSubRanges(Value *&HeaderCountOut) const {
693 IntegerType *Ty = cast<IntegerType>(LatchTakenCount->getType());
695 SCEVExpander Expander(SE, "irce");
696 Instruction *InsertPt = OriginalPreheader->getTerminator();
699 MaybeSimplify(Expander.expandCodeFor(LatchTakenCount, Ty, InsertPt));
701 IRBuilder<> B(InsertPt);
703 LoopConstrainer::SubRanges Result;
705 // I think we can be more aggressive here and make this nuw / nsw if the
706 // addition that feeds into the icmp for the latch's terminating branch is nuw
707 // / nsw. In any case, a wrapping 2's complement addition is safe.
708 ConstantInt *One = ConstantInt::get(Ty, 1);
709 HeaderCountOut = MaybeSimplify(B.CreateAdd(LatchCountV, One, "header.count"));
711 const SCEV *RangeBegin = SE.getSCEV(Range.first);
712 const SCEV *RangeEnd = SE.getSCEV(Range.second);
713 const SCEV *HeaderCountSCEV = SE.getSCEV(HeaderCountOut);
714 const SCEV *Zero = SE.getConstant(Ty, 0);
716 // In some cases we can prove that we don't need a pre or post loop
718 bool ProvablyNoPreloop =
719 SE.isKnownPredicate(ICmpInst::ICMP_SLE, RangeBegin, Zero);
720 if (!ProvablyNoPreloop)
721 Result.ExitPreLoopAt = ConstructSMinOf(HeaderCountOut, Range.first, B);
723 bool ProvablyNoPostLoop =
724 SE.isKnownPredicate(ICmpInst::ICMP_SLE, HeaderCountSCEV, RangeEnd);
725 if (!ProvablyNoPostLoop)
726 Result.ExitMainLoopAt = ConstructSMinOf(HeaderCountOut, Range.second, B);
731 void LoopConstrainer::cloneLoop(LoopConstrainer::ClonedLoop &Result,
732 const char *Tag) const {
733 for (BasicBlock *BB : OriginalLoop->getBlocks()) {
734 BasicBlock *Clone = CloneBasicBlock(BB, Result.Map, Twine(".") + Tag, F);
735 Result.Blocks.push_back(Clone);
736 Result.Map[BB] = Clone;
739 auto GetClonedValue = [&Result](Value *V) {
740 assert(V && "null values not in domain!");
741 auto It = Result.Map.find(V);
742 if (It == Result.Map.end())
744 return static_cast<Value *>(It->second);
747 Result.Structure = MainLoopStructure.map(GetClonedValue);
748 Result.Structure.Tag = Tag;
750 for (unsigned i = 0, e = Result.Blocks.size(); i != e; ++i) {
751 BasicBlock *ClonedBB = Result.Blocks[i];
752 BasicBlock *OriginalBB = OriginalLoop->getBlocks()[i];
754 assert(Result.Map[OriginalBB] == ClonedBB && "invariant!");
756 for (Instruction &I : *ClonedBB)
757 RemapInstruction(&I, Result.Map,
758 RF_NoModuleLevelChanges | RF_IgnoreMissingEntries);
760 // Exit blocks will now have one more predecessor and their PHI nodes need
761 // to be edited to reflect that. No phi nodes need to be introduced because
762 // the loop is in LCSSA.
764 for (auto SBBI = succ_begin(OriginalBB), SBBE = succ_end(OriginalBB);
765 SBBI != SBBE; ++SBBI) {
767 if (OriginalLoop->contains(*SBBI))
768 continue; // not an exit block
770 for (Instruction &I : **SBBI) {
771 if (!isa<PHINode>(&I))
774 PHINode *PN = cast<PHINode>(&I);
775 Value *OldIncoming = PN->getIncomingValueForBlock(OriginalBB);
776 PN->addIncoming(GetClonedValue(OldIncoming), ClonedBB);
782 LoopConstrainer::RewrittenRangeInfo LoopConstrainer::changeIterationSpaceEnd(
783 const LoopStructure &LS, BasicBlock *Preheader, Value *ExitLoopAt,
784 BasicBlock *ContinuationBlock) const {
786 // We start with a loop with a single latch:
788 // +--------------------+
792 // +--------+-----------+
793 // | ----------------\
795 // +--------v----v------+ |
799 // +--------------------+ |
803 // +--------------------+ |
805 // | latch >----------/
807 // +-------v------------+
810 // | +--------------------+
812 // +---> original exit |
814 // +--------------------+
816 // We change the control flow to look like
819 // +--------------------+
821 // | preheader >-------------------------+
823 // +--------v-----------+ |
824 // | /-------------+ |
826 // +--------v--v--------+ | |
828 // | header | | +--------+ |
830 // +--------------------+ | | +-----v-----v-----------+
832 // | | | .pseudo.exit |
834 // | | +-----------v-----------+
837 // | | +--------v-------------+
838 // +--------------------+ | | | |
839 // | | | | | ContinuationBlock |
840 // | latch >------+ | | |
841 // | | | +----------------------+
842 // +---------v----------+ |
845 // | +---------------^-----+
847 // +-----> .exit.selector |
849 // +----------v----------+
851 // +--------------------+ |
853 // | original exit <----+
855 // +--------------------+
858 RewrittenRangeInfo RRI;
860 auto BBInsertLocation = std::next(Function::iterator(LS.Latch));
861 RRI.ExitSelector = BasicBlock::Create(Ctx, Twine(LS.Tag) + ".exit.selector",
862 F, BBInsertLocation);
863 RRI.PseudoExit = BasicBlock::Create(Ctx, Twine(LS.Tag) + ".pseudo.exit", F,
866 BranchInst *PreheaderJump = cast<BranchInst>(&*Preheader->rbegin());
868 IRBuilder<> B(PreheaderJump);
870 // EnterLoopCond - is it okay to start executing this `LS'?
871 Value *EnterLoopCond = B.CreateICmpSLT(LS.CIVStart, ExitLoopAt);
872 B.CreateCondBr(EnterLoopCond, LS.Header, RRI.PseudoExit);
873 PreheaderJump->eraseFromParent();
875 assert(LS.LatchBrExitIdx == 1 && "generalize this as needed!");
877 B.SetInsertPoint(LS.LatchBr);
879 // ContinueCond - is it okay to execute the next iteration in `LS'?
880 Value *ContinueCond = B.CreateICmpSLT(LS.CIVNext, ExitLoopAt);
882 LS.LatchBr->setCondition(ContinueCond);
883 assert(LS.LatchBr->getSuccessor(LS.LatchBrExitIdx) == LS.LatchExit &&
885 LS.LatchBr->setSuccessor(LS.LatchBrExitIdx, RRI.ExitSelector);
887 B.SetInsertPoint(RRI.ExitSelector);
889 // IterationsLeft - are there any more iterations left, given the original
890 // upper bound on the induction variable? If not, we branch to the "real"
892 Value *IterationsLeft = B.CreateICmpSLT(LS.CIVNext, OriginalHeaderCount);
893 B.CreateCondBr(IterationsLeft, RRI.PseudoExit, LS.LatchExit);
895 BranchInst *BranchToContinuation =
896 BranchInst::Create(ContinuationBlock, RRI.PseudoExit);
898 // We emit PHI nodes into `RRI.PseudoExit' that compute the "latest" value of
899 // each of the PHI nodes in the loop header. This feeds into the initial
900 // value of the same PHI nodes if/when we continue execution.
901 for (Instruction &I : *LS.Header) {
902 if (!isa<PHINode>(&I))
905 PHINode *PN = cast<PHINode>(&I);
907 PHINode *NewPHI = PHINode::Create(PN->getType(), 2, PN->getName() + ".copy",
908 BranchToContinuation);
910 NewPHI->addIncoming(PN->getIncomingValueForBlock(Preheader), Preheader);
911 NewPHI->addIncoming(PN->getIncomingValueForBlock(LS.Latch),
913 RRI.PHIValuesAtPseudoExit.push_back(NewPHI);
916 // The latch exit now has a branch from `RRI.ExitSelector' instead of
917 // `LS.Latch'. The PHI nodes need to be updated to reflect that.
918 for (Instruction &I : *LS.LatchExit) {
919 if (PHINode *PN = dyn_cast<PHINode>(&I))
920 replacePHIBlock(PN, LS.Latch, RRI.ExitSelector);
928 void LoopConstrainer::rewriteIncomingValuesForPHIs(
929 LoopConstrainer::LoopStructure &LS, BasicBlock *ContinuationBlock,
930 const LoopConstrainer::RewrittenRangeInfo &RRI) const {
932 unsigned PHIIndex = 0;
933 for (Instruction &I : *LS.Header) {
934 if (!isa<PHINode>(&I))
937 PHINode *PN = cast<PHINode>(&I);
939 for (unsigned i = 0, e = PN->getNumIncomingValues(); i < e; ++i)
940 if (PN->getIncomingBlock(i) == ContinuationBlock)
941 PN->setIncomingValue(i, RRI.PHIValuesAtPseudoExit[PHIIndex++]);
944 LS.CIVStart = LS.CIV->getIncomingValueForBlock(ContinuationBlock);
948 LoopConstrainer::createPreheader(const LoopConstrainer::LoopStructure &LS,
949 BasicBlock *OldPreheader,
950 const char *Tag) const {
952 BasicBlock *Preheader = BasicBlock::Create(Ctx, Tag, F, LS.Header);
953 BranchInst::Create(LS.Header, Preheader);
955 for (Instruction &I : *LS.Header) {
956 if (!isa<PHINode>(&I))
959 PHINode *PN = cast<PHINode>(&I);
960 for (unsigned i = 0, e = PN->getNumIncomingValues(); i < e; ++i)
961 replacePHIBlock(PN, OldPreheader, Preheader);
967 template<typename IteratorTy>
968 void LoopConstrainer::addToParentLoopIfNeeded(IteratorTy Begin,
970 Loop *ParentLoop = OriginalLoop->getParentLoop();
974 auto &LoopInfoBase = OriginalLoopInfo->getBase();
975 for (; Begin != End; Begin++)
976 ParentLoop->addBasicBlockToLoop(*Begin, LoopInfoBase);
979 bool LoopConstrainer::run() {
980 BasicBlock *Preheader = nullptr;
981 const char *CouldNotProceedBecause = nullptr;
982 if (!recognizeLoop(MainLoopStructure, LatchTakenCount, Preheader,
983 CouldNotProceedBecause)) {
984 DEBUG(dbgs() << "irce: could not recognize loop, " << CouldNotProceedBecause
989 OriginalPreheader = Preheader;
990 MainLoopPreheader = Preheader;
992 SubRanges SR = calculateSubRanges(OriginalHeaderCount);
994 // It would have been better to make `PreLoop' and `PostLoop'
995 // `Optional<ClonedLoop>'s, but `ValueToValueMapTy' does not have a copy
997 ClonedLoop PreLoop, PostLoop;
998 bool NeedsPreLoop = SR.ExitPreLoopAt.hasValue();
999 bool NeedsPostLoop = SR.ExitMainLoopAt.hasValue();
1001 // We clone these ahead of time so that we don't have to deal with changing
1002 // and temporarily invalid IR as we transform the loops.
1004 cloneLoop(PreLoop, "preloop");
1006 cloneLoop(PostLoop, "postloop");
1008 RewrittenRangeInfo PreLoopRRI;
1011 Preheader->getTerminator()->replaceUsesOfWith(MainLoopStructure.Header,
1012 PreLoop.Structure.Header);
1015 createPreheader(MainLoopStructure, Preheader, "mainloop");
1017 changeIterationSpaceEnd(PreLoop.Structure, Preheader,
1018 SR.ExitPreLoopAt.getValue(), MainLoopPreheader);
1019 rewriteIncomingValuesForPHIs(MainLoopStructure, MainLoopPreheader,
1023 BasicBlock *PostLoopPreheader = nullptr;
1024 RewrittenRangeInfo PostLoopRRI;
1026 if (NeedsPostLoop) {
1028 createPreheader(PostLoop.Structure, Preheader, "postloop");
1029 PostLoopRRI = changeIterationSpaceEnd(MainLoopStructure, MainLoopPreheader,
1030 SR.ExitMainLoopAt.getValue(),
1032 rewriteIncomingValuesForPHIs(PostLoop.Structure, PostLoopPreheader,
1036 std::array<BasicBlock *, 6> NewBlocks { {PostLoopPreheader,
1037 PreLoopRRI.PseudoExit, PreLoopRRI.ExitSelector, PostLoopRRI.PseudoExit,
1038 PostLoopRRI.ExitSelector,
1039 MainLoopPreheader == Preheader ? nullptr : MainLoopPreheader } };
1040 // Some of the above may be nullptr, filter them out before passing to
1041 // addToParentLoopIfNeeded.
1042 auto NewBlocksEnd = std::remove(NewBlocks.begin(), NewBlocks.end(), nullptr);
1044 addToParentLoopIfNeeded(NewBlocks.begin(), NewBlocksEnd);
1045 addToParentLoopIfNeeded(PreLoop.Blocks.begin(), PreLoop.Blocks.end());
1046 addToParentLoopIfNeeded(PostLoop.Blocks.begin(), PostLoop.Blocks.end());
1051 /// Computes and returns a range of values for the induction variable in which
1052 /// the range check can be safely elided. If it cannot compute such a range,
1054 Optional<InductiveRangeCheck::Range>
1055 InductiveRangeCheck::computeSafeIterationSpace(ScalarEvolution &SE,
1056 IRBuilder<> &B) const {
1058 // Currently we support inequalities of the form:
1060 // 0 <= Offset + 1 * CIV < L given L >= 0
1062 // The inequality is satisfied by -Offset <= CIV < (L - Offset) [^1]. All
1063 // additions and subtractions are twos-complement wrapping and comparisons are
1068 // If there exists CIV such that -Offset <= CIV < (L - Offset) then it
1069 // follows that -Offset <= (-Offset + L) [== Eq. 1]. Since L >= 0, if
1070 // (-Offset + L) sign-overflows then (-Offset + L) < (-Offset). Hence by
1071 // [Eq. 1], (-Offset + L) could not have overflown.
1073 // This means CIV = t + (-Offset) for t in [0, L). Hence (CIV + Offset) =
1074 // t. Hence 0 <= (CIV + Offset) < L
1076 // [^1]: Note that the solution does _not_ apply if L < 0; consider values
1077 // Offset = 127, CIV = 126 and L = -2 in an i8 world.
1079 const SCEVConstant *ScaleC = dyn_cast<SCEVConstant>(getScale());
1080 if (!(ScaleC && ScaleC->getValue()->getValue() == 1)) {
1081 DEBUG(dbgs() << "irce: could not compute safe iteration space for:\n";
1086 Value *OffsetV = SCEVExpander(SE, "safe.itr.space").expandCodeFor(
1087 getOffset(), getOffset()->getType(), B.GetInsertPoint());
1088 OffsetV = MaybeSimplify(OffsetV);
1090 Value *Begin = MaybeSimplify(B.CreateNeg(OffsetV));
1091 Value *End = MaybeSimplify(B.CreateSub(getLength(), OffsetV));
1093 return std::make_pair(Begin, End);
1096 static InductiveRangeCheck::Range
1097 IntersectRange(const Optional<InductiveRangeCheck::Range> &R1,
1098 const InductiveRangeCheck::Range &R2, IRBuilder<> &B) {
1101 auto &R1Value = R1.getValue();
1103 Value *NewMin = ConstructSMaxOf(R1Value.first, R2.first, B);
1104 Value *NewMax = ConstructSMinOf(R1Value.second, R2.second, B);
1105 return std::make_pair(NewMin, NewMax);
1108 bool InductiveRangeCheckElimination::runOnLoop(Loop *L, LPPassManager &LPM) {
1109 if (L->getBlocks().size() >= LoopSizeCutoff) {
1110 DEBUG(dbgs() << "irce: giving up constraining loop, too large\n";);
1114 BasicBlock *Preheader = L->getLoopPreheader();
1116 DEBUG(dbgs() << "irce: loop has no preheader, leaving\n");
1120 LLVMContext &Context = Preheader->getContext();
1121 InductiveRangeCheck::AllocatorTy IRCAlloc;
1122 SmallVector<InductiveRangeCheck *, 16> RangeChecks;
1123 ScalarEvolution &SE = getAnalysis<ScalarEvolution>();
1125 for (auto BBI : L->getBlocks())
1126 if (BranchInst *TBI = dyn_cast<BranchInst>(BBI->getTerminator()))
1127 if (InductiveRangeCheck *IRC =
1128 InductiveRangeCheck::create(IRCAlloc, TBI, L, SE))
1129 RangeChecks.push_back(IRC);
1131 if (RangeChecks.empty())
1134 DEBUG(dbgs() << "irce: looking at loop "; L->print(dbgs());
1135 dbgs() << "irce: loop has " << RangeChecks.size()
1136 << " inductive range checks: \n";
1137 for (InductiveRangeCheck *IRC : RangeChecks)
1141 Optional<InductiveRangeCheck::Range> SafeIterRange;
1142 Instruction *ExprInsertPt = Preheader->getTerminator();
1144 SmallVector<InductiveRangeCheck *, 4> RangeChecksToEliminate;
1146 IRBuilder<> B(ExprInsertPt);
1147 for (InductiveRangeCheck *IRC : RangeChecks) {
1148 auto Result = IRC->computeSafeIterationSpace(SE, B);
1149 if (Result.hasValue()) {
1150 SafeIterRange = IntersectRange(SafeIterRange, Result.getValue(), B);
1151 RangeChecksToEliminate.push_back(IRC);
1155 if (!SafeIterRange.hasValue())
1158 LoopConstrainer LC(L, &getAnalysis<LoopInfo>(), SE, SafeIterRange.getValue());
1159 bool Changed = LC.run();
1162 auto PrintConstrainedLoopInfo = [L]() {
1163 dbgs() << "irce: in function ";
1164 dbgs() << L->getHeader()->getParent()->getName() << ": ";
1165 dbgs() << "constrained ";
1169 DEBUG(PrintConstrainedLoopInfo());
1171 if (PrintChangedLoops)
1172 PrintConstrainedLoopInfo();
1174 // Optimize away the now-redundant range checks.
1176 for (InductiveRangeCheck *IRC : RangeChecksToEliminate) {
1177 ConstantInt *FoldedRangeCheck = IRC->getPassingDirection()
1178 ? ConstantInt::getTrue(Context)
1179 : ConstantInt::getFalse(Context);
1180 IRC->getBranch()->setCondition(FoldedRangeCheck);
1187 Pass *llvm::createInductiveRangeCheckEliminationPass() {
1188 return new InductiveRangeCheckElimination;