1 //===-- InductiveRangeCheckElimination.cpp - ------------------------------===//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
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
12 // convert
13 //
14 //   len = < known positive >
15 //   for (i = 0; i < n; i++) {
16 //     if (0 <= i && i < len) {
17 //       do_something();
18 //     } else {
19 //       throw_out_of_bounds();
20 //     }
21 //   }
22 //
23 // to
24 //
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
30 //       do_something();
31 //     } else {
32 //       throw_out_of_bounds();
33 //     }
34 //   }
35 //   for (i = limit; i < n; i++) {
36 //     if (0 <= i && i < len) {
37 //       do_something();
38 //     } else {
39 //       throw_out_of_bounds();
40 //     }
41 //   }
42 //===----------------------------------------------------------------------===//
43 
44 #include "llvm/ADT/Optional.h"
45 #include "llvm/Analysis/BranchProbabilityInfo.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"
53 #include "llvm/IR/Dominators.h"
54 #include "llvm/IR/Function.h"
55 #include "llvm/IR/IRBuilder.h"
56 #include "llvm/IR/Instructions.h"
57 #include "llvm/IR/Module.h"
58 #include "llvm/IR/PatternMatch.h"
59 #include "llvm/IR/ValueHandle.h"
60 #include "llvm/IR/Verifier.h"
61 #include "llvm/Pass.h"
62 #include "llvm/Support/Debug.h"
63 #include "llvm/Support/raw_ostream.h"
64 #include "llvm/Transforms/Scalar.h"
65 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
66 #include "llvm/Transforms/Utils/Cloning.h"
67 #include "llvm/Transforms/Utils/LoopUtils.h"
68 #include "llvm/Transforms/Utils/SimplifyIndVar.h"
69 #include "llvm/Transforms/Utils/UnrollLoop.h"
70 #include <array>
71 
72 using namespace llvm;
73 
74 static cl::opt<unsigned> LoopSizeCutoff("irce-loop-size-cutoff", cl::Hidden,
75                                         cl::init(64));
76 
77 static cl::opt<bool> PrintChangedLoops("irce-print-changed-loops", cl::Hidden,
78                                        cl::init(false));
79 
80 static cl::opt<bool> PrintRangeChecks("irce-print-range-checks", cl::Hidden,
81                                       cl::init(false));
82 
83 static cl::opt<int> MaxExitProbReciprocal("irce-max-exit-prob-reciprocal",
84                                           cl::Hidden, cl::init(10));
85 
86 #define DEBUG_TYPE "irce"
87 
88 namespace {
89 
90 /// An inductive range check is conditional branch in a loop with
91 ///
92 ///  1. a very cold successor (i.e. the branch jumps to that successor very
93 ///     rarely)
94 ///
95 ///  and
96 ///
97 ///  2. a condition that is provably true for some contiguous range of values
98 ///     taken by the containing loop's induction variable.
99 ///
100 class InductiveRangeCheck {
101   // Classifies a range check
102   enum RangeCheckKind : unsigned {
103     // Range check of the form "0 <= I".
104     RANGE_CHECK_LOWER = 1,
105 
106     // Range check of the form "I < L" where L is known positive.
107     RANGE_CHECK_UPPER = 2,
108 
109     // The logical and of the RANGE_CHECK_LOWER and RANGE_CHECK_UPPER
110     // conditions.
111     RANGE_CHECK_BOTH = RANGE_CHECK_LOWER | RANGE_CHECK_UPPER,
112 
113     // Unrecognized range check condition.
114     RANGE_CHECK_UNKNOWN = (unsigned)-1
115   };
116 
117   static const char *rangeCheckKindToStr(RangeCheckKind);
118 
119   const SCEV *Offset;
120   const SCEV *Scale;
121   Value *Length;
122   BranchInst *Branch;
123   RangeCheckKind Kind;
124 
125   static RangeCheckKind parseRangeCheckICmp(Loop *L, ICmpInst *ICI,
126                                             ScalarEvolution &SE, Value *&Index,
127                                             Value *&Length);
128 
129   static InductiveRangeCheck::RangeCheckKind
130   parseRangeCheck(Loop *L, ScalarEvolution &SE, Value *Condition,
131                   const SCEV *&Index, Value *&UpperLimit);
132 
InductiveRangeCheck()133   InductiveRangeCheck() :
134     Offset(nullptr), Scale(nullptr), Length(nullptr), Branch(nullptr) { }
135 
136 public:
getOffset() const137   const SCEV *getOffset() const { return Offset; }
getScale() const138   const SCEV *getScale() const { return Scale; }
getLength() const139   Value *getLength() const { return Length; }
140 
print(raw_ostream & OS) const141   void print(raw_ostream &OS) const {
142     OS << "InductiveRangeCheck:\n";
143     OS << "  Kind: " << rangeCheckKindToStr(Kind) << "\n";
144     OS << "  Offset: ";
145     Offset->print(OS);
146     OS << "  Scale: ";
147     Scale->print(OS);
148     OS << "  Length: ";
149     if (Length)
150       Length->print(OS);
151     else
152       OS << "(null)";
153     OS << "\n  Branch: ";
154     getBranch()->print(OS);
155     OS << "\n";
156   }
157 
158 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
dump()159   void dump() {
160     print(dbgs());
161   }
162 #endif
163 
getBranch() const164   BranchInst *getBranch() const { return Branch; }
165 
166   /// Represents an signed integer range [Range.getBegin(), Range.getEnd()).  If
167   /// R.getEnd() sle R.getBegin(), then R denotes the empty range.
168 
169   class Range {
170     const SCEV *Begin;
171     const SCEV *End;
172 
173   public:
Range(const SCEV * Begin,const SCEV * End)174     Range(const SCEV *Begin, const SCEV *End) : Begin(Begin), End(End) {
175       assert(Begin->getType() == End->getType() && "ill-typed range!");
176     }
177 
getType() const178     Type *getType() const { return Begin->getType(); }
getBegin() const179     const SCEV *getBegin() const { return Begin; }
getEnd() const180     const SCEV *getEnd() const { return End; }
181   };
182 
183   typedef SpecificBumpPtrAllocator<InductiveRangeCheck> AllocatorTy;
184 
185   /// This is the value the condition of the branch needs to evaluate to for the
186   /// branch to take the hot successor (see (1) above).
getPassingDirection()187   bool getPassingDirection() { return true; }
188 
189   /// Computes a range for the induction variable (IndVar) in which the range
190   /// check is redundant and can be constant-folded away.  The induction
191   /// variable is not required to be the canonical {0,+,1} induction variable.
192   Optional<Range> computeSafeIterationSpace(ScalarEvolution &SE,
193                                             const SCEVAddRecExpr *IndVar,
194                                             IRBuilder<> &B) const;
195 
196   /// Create an inductive range check out of BI if possible, else return
197   /// nullptr.
198   static InductiveRangeCheck *create(AllocatorTy &Alloc, BranchInst *BI,
199                                      Loop *L, ScalarEvolution &SE,
200                                      BranchProbabilityInfo &BPI);
201 };
202 
203 class InductiveRangeCheckElimination : public LoopPass {
204   InductiveRangeCheck::AllocatorTy Allocator;
205 
206 public:
207   static char ID;
InductiveRangeCheckElimination()208   InductiveRangeCheckElimination() : LoopPass(ID) {
209     initializeInductiveRangeCheckEliminationPass(
210         *PassRegistry::getPassRegistry());
211   }
212 
getAnalysisUsage(AnalysisUsage & AU) const213   void getAnalysisUsage(AnalysisUsage &AU) const override {
214     AU.addRequired<LoopInfoWrapperPass>();
215     AU.addRequiredID(LoopSimplifyID);
216     AU.addRequiredID(LCSSAID);
217     AU.addRequired<ScalarEvolutionWrapperPass>();
218     AU.addRequired<BranchProbabilityInfoWrapperPass>();
219   }
220 
221   bool runOnLoop(Loop *L, LPPassManager &LPM) override;
222 };
223 
224 char InductiveRangeCheckElimination::ID = 0;
225 }
226 
227 INITIALIZE_PASS_BEGIN(InductiveRangeCheckElimination, "irce",
228                       "Inductive range check elimination", false, false)
INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)229 INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
230 INITIALIZE_PASS_DEPENDENCY(LoopSimplify)
231 INITIALIZE_PASS_DEPENDENCY(LCSSA)
232 INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass)
233 INITIALIZE_PASS_DEPENDENCY(BranchProbabilityInfoWrapperPass)
234 INITIALIZE_PASS_END(InductiveRangeCheckElimination, "irce",
235                     "Inductive range check elimination", false, false)
236 
237 const char *InductiveRangeCheck::rangeCheckKindToStr(
238     InductiveRangeCheck::RangeCheckKind RCK) {
239   switch (RCK) {
240   case InductiveRangeCheck::RANGE_CHECK_UNKNOWN:
241     return "RANGE_CHECK_UNKNOWN";
242 
243   case InductiveRangeCheck::RANGE_CHECK_UPPER:
244     return "RANGE_CHECK_UPPER";
245 
246   case InductiveRangeCheck::RANGE_CHECK_LOWER:
247     return "RANGE_CHECK_LOWER";
248 
249   case InductiveRangeCheck::RANGE_CHECK_BOTH:
250     return "RANGE_CHECK_BOTH";
251   }
252 
253   llvm_unreachable("unknown range check type!");
254 }
255 
256 /// Parse a single ICmp instruction, `ICI`, into a range check.  If `ICI`
257 /// cannot
258 /// be interpreted as a range check, return `RANGE_CHECK_UNKNOWN` and set
259 /// `Index` and `Length` to `nullptr`.  Otherwise set `Index` to the value
260 /// being
261 /// range checked, and set `Length` to the upper limit `Index` is being range
262 /// checked with if (and only if) the range check type is stronger or equal to
263 /// RANGE_CHECK_UPPER.
264 ///
265 InductiveRangeCheck::RangeCheckKind
parseRangeCheckICmp(Loop * L,ICmpInst * ICI,ScalarEvolution & SE,Value * & Index,Value * & Length)266 InductiveRangeCheck::parseRangeCheckICmp(Loop *L, ICmpInst *ICI,
267                                          ScalarEvolution &SE, Value *&Index,
268                                          Value *&Length) {
269 
270   auto IsNonNegativeAndNotLoopVarying = [&SE, L](Value *V) {
271     const SCEV *S = SE.getSCEV(V);
272     if (isa<SCEVCouldNotCompute>(S))
273       return false;
274 
275     return SE.getLoopDisposition(S, L) == ScalarEvolution::LoopInvariant &&
276            SE.isKnownNonNegative(S);
277   };
278 
279   using namespace llvm::PatternMatch;
280 
281   ICmpInst::Predicate Pred = ICI->getPredicate();
282   Value *LHS = ICI->getOperand(0);
283   Value *RHS = ICI->getOperand(1);
284 
285   switch (Pred) {
286   default:
287     return RANGE_CHECK_UNKNOWN;
288 
289   case ICmpInst::ICMP_SLE:
290     std::swap(LHS, RHS);
291   // fallthrough
292   case ICmpInst::ICMP_SGE:
293     if (match(RHS, m_ConstantInt<0>())) {
294       Index = LHS;
295       return RANGE_CHECK_LOWER;
296     }
297     return RANGE_CHECK_UNKNOWN;
298 
299   case ICmpInst::ICMP_SLT:
300     std::swap(LHS, RHS);
301   // fallthrough
302   case ICmpInst::ICMP_SGT:
303     if (match(RHS, m_ConstantInt<-1>())) {
304       Index = LHS;
305       return RANGE_CHECK_LOWER;
306     }
307 
308     if (IsNonNegativeAndNotLoopVarying(LHS)) {
309       Index = RHS;
310       Length = LHS;
311       return RANGE_CHECK_UPPER;
312     }
313     return RANGE_CHECK_UNKNOWN;
314 
315   case ICmpInst::ICMP_ULT:
316     std::swap(LHS, RHS);
317   // fallthrough
318   case ICmpInst::ICMP_UGT:
319     if (IsNonNegativeAndNotLoopVarying(LHS)) {
320       Index = RHS;
321       Length = LHS;
322       return RANGE_CHECK_BOTH;
323     }
324     return RANGE_CHECK_UNKNOWN;
325   }
326 
327   llvm_unreachable("default clause returns!");
328 }
329 
330 /// Parses an arbitrary condition into a range check.  `Length` is set only if
331 /// the range check is recognized to be `RANGE_CHECK_UPPER` or stronger.
332 InductiveRangeCheck::RangeCheckKind
parseRangeCheck(Loop * L,ScalarEvolution & SE,Value * Condition,const SCEV * & Index,Value * & Length)333 InductiveRangeCheck::parseRangeCheck(Loop *L, ScalarEvolution &SE,
334                                      Value *Condition, const SCEV *&Index,
335                                      Value *&Length) {
336   using namespace llvm::PatternMatch;
337 
338   Value *A = nullptr;
339   Value *B = nullptr;
340 
341   if (match(Condition, m_And(m_Value(A), m_Value(B)))) {
342     Value *IndexA = nullptr, *IndexB = nullptr;
343     Value *LengthA = nullptr, *LengthB = nullptr;
344     ICmpInst *ICmpA = dyn_cast<ICmpInst>(A), *ICmpB = dyn_cast<ICmpInst>(B);
345 
346     if (!ICmpA || !ICmpB)
347       return InductiveRangeCheck::RANGE_CHECK_UNKNOWN;
348 
349     auto RCKindA = parseRangeCheckICmp(L, ICmpA, SE, IndexA, LengthA);
350     auto RCKindB = parseRangeCheckICmp(L, ICmpB, SE, IndexB, LengthB);
351 
352     if (RCKindA == InductiveRangeCheck::RANGE_CHECK_UNKNOWN ||
353         RCKindB == InductiveRangeCheck::RANGE_CHECK_UNKNOWN)
354       return InductiveRangeCheck::RANGE_CHECK_UNKNOWN;
355 
356     if (IndexA != IndexB)
357       return InductiveRangeCheck::RANGE_CHECK_UNKNOWN;
358 
359     if (LengthA != nullptr && LengthB != nullptr && LengthA != LengthB)
360       return InductiveRangeCheck::RANGE_CHECK_UNKNOWN;
361 
362     Index = SE.getSCEV(IndexA);
363     if (isa<SCEVCouldNotCompute>(Index))
364       return InductiveRangeCheck::RANGE_CHECK_UNKNOWN;
365 
366     Length = LengthA == nullptr ? LengthB : LengthA;
367 
368     return (InductiveRangeCheck::RangeCheckKind)(RCKindA | RCKindB);
369   }
370 
371   if (ICmpInst *ICI = dyn_cast<ICmpInst>(Condition)) {
372     Value *IndexVal = nullptr;
373 
374     auto RCKind = parseRangeCheckICmp(L, ICI, SE, IndexVal, Length);
375 
376     if (RCKind == InductiveRangeCheck::RANGE_CHECK_UNKNOWN)
377       return InductiveRangeCheck::RANGE_CHECK_UNKNOWN;
378 
379     Index = SE.getSCEV(IndexVal);
380     if (isa<SCEVCouldNotCompute>(Index))
381       return InductiveRangeCheck::RANGE_CHECK_UNKNOWN;
382 
383     return RCKind;
384   }
385 
386   return InductiveRangeCheck::RANGE_CHECK_UNKNOWN;
387 }
388 
389 
390 InductiveRangeCheck *
create(InductiveRangeCheck::AllocatorTy & A,BranchInst * BI,Loop * L,ScalarEvolution & SE,BranchProbabilityInfo & BPI)391 InductiveRangeCheck::create(InductiveRangeCheck::AllocatorTy &A, BranchInst *BI,
392                             Loop *L, ScalarEvolution &SE,
393                             BranchProbabilityInfo &BPI) {
394 
395   if (BI->isUnconditional() || BI->getParent() == L->getLoopLatch())
396     return nullptr;
397 
398   BranchProbability LikelyTaken(15, 16);
399 
400   if (BPI.getEdgeProbability(BI->getParent(), (unsigned) 0) < LikelyTaken)
401     return nullptr;
402 
403   Value *Length = nullptr;
404   const SCEV *IndexSCEV = nullptr;
405 
406   auto RCKind = InductiveRangeCheck::parseRangeCheck(L, SE, BI->getCondition(),
407                                                      IndexSCEV, Length);
408 
409   if (RCKind == InductiveRangeCheck::RANGE_CHECK_UNKNOWN)
410     return nullptr;
411 
412   assert(IndexSCEV && "contract with SplitRangeCheckCondition!");
413   assert((!(RCKind & InductiveRangeCheck::RANGE_CHECK_UPPER) || Length) &&
414          "contract with SplitRangeCheckCondition!");
415 
416   const SCEVAddRecExpr *IndexAddRec = dyn_cast<SCEVAddRecExpr>(IndexSCEV);
417   bool IsAffineIndex =
418       IndexAddRec && (IndexAddRec->getLoop() == L) && IndexAddRec->isAffine();
419 
420   if (!IsAffineIndex)
421     return nullptr;
422 
423   InductiveRangeCheck *IRC = new (A.Allocate()) InductiveRangeCheck;
424   IRC->Length = Length;
425   IRC->Offset = IndexAddRec->getStart();
426   IRC->Scale = IndexAddRec->getStepRecurrence(SE);
427   IRC->Branch = BI;
428   IRC->Kind = RCKind;
429   return IRC;
430 }
431 
432 namespace {
433 
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;
441 
442   BasicBlock *Header;
443   BasicBlock *Latch;
444 
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;
448   BasicBlock *LatchExit;
449   unsigned LatchBrExitIdx;
450 
451   Value *IndVarNext;
452   Value *IndVarStart;
453   Value *LoopExitAt;
454   bool IndVarIncreasing;
455 
LoopStructure__anon764fa5440311::LoopStructure456   LoopStructure()
457       : Tag(""), Header(nullptr), Latch(nullptr), LatchBr(nullptr),
458         LatchExit(nullptr), LatchBrExitIdx(-1), IndVarNext(nullptr),
459         IndVarStart(nullptr), LoopExitAt(nullptr), IndVarIncreasing(false) {}
460 
map__anon764fa5440311::LoopStructure461   template <typename M> LoopStructure map(M Map) const {
462     LoopStructure Result;
463     Result.Tag = Tag;
464     Result.Header = cast<BasicBlock>(Map(Header));
465     Result.Latch = cast<BasicBlock>(Map(Latch));
466     Result.LatchBr = cast<BranchInst>(Map(LatchBr));
467     Result.LatchExit = cast<BasicBlock>(Map(LatchExit));
468     Result.LatchBrExitIdx = LatchBrExitIdx;
469     Result.IndVarNext = Map(IndVarNext);
470     Result.IndVarStart = Map(IndVarStart);
471     Result.LoopExitAt = Map(LoopExitAt);
472     Result.IndVarIncreasing = IndVarIncreasing;
473     return Result;
474   }
475 
476   static Optional<LoopStructure> parseLoopStructure(ScalarEvolution &,
477                                                     BranchProbabilityInfo &BPI,
478                                                     Loop &,
479                                                     const char *&);
480 };
481 
482 /// This class is used to constrain loops to run within a given iteration space.
483 /// The algorithm this class implements is given a Loop and a range [Begin,
484 /// End).  The algorithm then tries to break out a "main loop" out of the loop
485 /// it is given in a way that the "main loop" runs with the induction variable
486 /// in a subset of [Begin, End).  The algorithm emits appropriate pre and post
487 /// loops to run any remaining iterations.  The pre loop runs any iterations in
488 /// which the induction variable is < Begin, and the post loop runs any
489 /// iterations in which the induction variable is >= End.
490 ///
491 class LoopConstrainer {
492   // The representation of a clone of the original loop we started out with.
493   struct ClonedLoop {
494     // The cloned blocks
495     std::vector<BasicBlock *> Blocks;
496 
497     // `Map` maps values in the clonee into values in the cloned version
498     ValueToValueMapTy Map;
499 
500     // An instance of `LoopStructure` for the cloned loop
501     LoopStructure Structure;
502   };
503 
504   // Result of rewriting the range of a loop.  See changeIterationSpaceEnd for
505   // more details on what these fields mean.
506   struct RewrittenRangeInfo {
507     BasicBlock *PseudoExit;
508     BasicBlock *ExitSelector;
509     std::vector<PHINode *> PHIValuesAtPseudoExit;
510     PHINode *IndVarEnd;
511 
RewrittenRangeInfo__anon764fa5440311::LoopConstrainer::RewrittenRangeInfo512     RewrittenRangeInfo()
513         : PseudoExit(nullptr), ExitSelector(nullptr), IndVarEnd(nullptr) {}
514   };
515 
516   // Calculated subranges we restrict the iteration space of the main loop to.
517   // See the implementation of `calculateSubRanges' for more details on how
518   // these fields are computed.  `LowLimit` is None if there is no restriction
519   // on low end of the restricted iteration space of the main loop.  `HighLimit`
520   // is None if there is no restriction on high end of the restricted iteration
521   // space of the main loop.
522 
523   struct SubRanges {
524     Optional<const SCEV *> LowLimit;
525     Optional<const SCEV *> HighLimit;
526   };
527 
528   // A utility function that does a `replaceUsesOfWith' on the incoming block
529   // set of a `PHINode' -- replaces instances of `Block' in the `PHINode's
530   // incoming block list with `ReplaceBy'.
531   static void replacePHIBlock(PHINode *PN, BasicBlock *Block,
532                               BasicBlock *ReplaceBy);
533 
534   // Compute a safe set of limits for the main loop to run in -- effectively the
535   // intersection of `Range' and the iteration space of the original loop.
536   // Return None if unable to compute the set of subranges.
537   //
538   Optional<SubRanges> calculateSubRanges() const;
539 
540   // Clone `OriginalLoop' and return the result in CLResult.  The IR after
541   // running `cloneLoop' is well formed except for the PHI nodes in CLResult --
542   // the PHI nodes say that there is an incoming edge from `OriginalPreheader`
543   // but there is no such edge.
544   //
545   void cloneLoop(ClonedLoop &CLResult, const char *Tag) const;
546 
547   // Rewrite the iteration space of the loop denoted by (LS, Preheader). The
548   // iteration space of the rewritten loop ends at ExitLoopAt.  The start of the
549   // iteration space is not changed.  `ExitLoopAt' is assumed to be slt
550   // `OriginalHeaderCount'.
551   //
552   // If there are iterations left to execute, control is made to jump to
553   // `ContinuationBlock', otherwise they take the normal loop exit.  The
554   // returned `RewrittenRangeInfo' object is populated as follows:
555   //
556   //  .PseudoExit is a basic block that unconditionally branches to
557   //      `ContinuationBlock'.
558   //
559   //  .ExitSelector is a basic block that decides, on exit from the loop,
560   //      whether to branch to the "true" exit or to `PseudoExit'.
561   //
562   //  .PHIValuesAtPseudoExit are PHINodes in `PseudoExit' that compute the value
563   //      for each PHINode in the loop header on taking the pseudo exit.
564   //
565   // After changeIterationSpaceEnd, `Preheader' is no longer a legitimate
566   // preheader because it is made to branch to the loop header only
567   // conditionally.
568   //
569   RewrittenRangeInfo
570   changeIterationSpaceEnd(const LoopStructure &LS, BasicBlock *Preheader,
571                           Value *ExitLoopAt,
572                           BasicBlock *ContinuationBlock) const;
573 
574   // The loop denoted by `LS' has `OldPreheader' as its preheader.  This
575   // function creates a new preheader for `LS' and returns it.
576   //
577   BasicBlock *createPreheader(const LoopStructure &LS, BasicBlock *OldPreheader,
578                               const char *Tag) const;
579 
580   // `ContinuationBlockAndPreheader' was the continuation block for some call to
581   // `changeIterationSpaceEnd' and is the preheader to the loop denoted by `LS'.
582   // This function rewrites the PHI nodes in `LS.Header' to start with the
583   // correct value.
584   void rewriteIncomingValuesForPHIs(
585       LoopStructure &LS, BasicBlock *ContinuationBlockAndPreheader,
586       const LoopConstrainer::RewrittenRangeInfo &RRI) const;
587 
588   // Even though we do not preserve any passes at this time, we at least need to
589   // keep the parent loop structure consistent.  The `LPPassManager' seems to
590   // verify this after running a loop pass.  This function adds the list of
591   // blocks denoted by BBs to this loops parent loop if required.
592   void addToParentLoopIfNeeded(ArrayRef<BasicBlock *> BBs);
593 
594   // Some global state.
595   Function &F;
596   LLVMContext &Ctx;
597   ScalarEvolution &SE;
598 
599   // Information about the original loop we started out with.
600   Loop &OriginalLoop;
601   LoopInfo &OriginalLoopInfo;
602   const SCEV *LatchTakenCount;
603   BasicBlock *OriginalPreheader;
604 
605   // The preheader of the main loop.  This may or may not be different from
606   // `OriginalPreheader'.
607   BasicBlock *MainLoopPreheader;
608 
609   // The range we need to run the main loop in.
610   InductiveRangeCheck::Range Range;
611 
612   // The structure of the main loop (see comment at the beginning of this class
613   // for a definition)
614   LoopStructure MainLoopStructure;
615 
616 public:
LoopConstrainer(Loop & L,LoopInfo & LI,const LoopStructure & LS,ScalarEvolution & SE,InductiveRangeCheck::Range R)617   LoopConstrainer(Loop &L, LoopInfo &LI, const LoopStructure &LS,
618                   ScalarEvolution &SE, InductiveRangeCheck::Range R)
619       : F(*L.getHeader()->getParent()), Ctx(L.getHeader()->getContext()),
620         SE(SE), OriginalLoop(L), OriginalLoopInfo(LI), LatchTakenCount(nullptr),
621         OriginalPreheader(nullptr), MainLoopPreheader(nullptr), Range(R),
622         MainLoopStructure(LS) {}
623 
624   // Entry point for the algorithm.  Returns true on success.
625   bool run();
626 };
627 
628 }
629 
replacePHIBlock(PHINode * PN,BasicBlock * Block,BasicBlock * ReplaceBy)630 void LoopConstrainer::replacePHIBlock(PHINode *PN, BasicBlock *Block,
631                                       BasicBlock *ReplaceBy) {
632   for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
633     if (PN->getIncomingBlock(i) == Block)
634       PN->setIncomingBlock(i, ReplaceBy);
635 }
636 
CanBeSMax(ScalarEvolution & SE,const SCEV * S)637 static bool CanBeSMax(ScalarEvolution &SE, const SCEV *S) {
638   APInt SMax =
639       APInt::getSignedMaxValue(cast<IntegerType>(S->getType())->getBitWidth());
640   return SE.getSignedRange(S).contains(SMax) &&
641          SE.getUnsignedRange(S).contains(SMax);
642 }
643 
CanBeSMin(ScalarEvolution & SE,const SCEV * S)644 static bool CanBeSMin(ScalarEvolution &SE, const SCEV *S) {
645   APInt SMin =
646       APInt::getSignedMinValue(cast<IntegerType>(S->getType())->getBitWidth());
647   return SE.getSignedRange(S).contains(SMin) &&
648          SE.getUnsignedRange(S).contains(SMin);
649 }
650 
651 Optional<LoopStructure>
parseLoopStructure(ScalarEvolution & SE,BranchProbabilityInfo & BPI,Loop & L,const char * & FailureReason)652 LoopStructure::parseLoopStructure(ScalarEvolution &SE, BranchProbabilityInfo &BPI,
653                                   Loop &L, const char *&FailureReason) {
654   assert(L.isLoopSimplifyForm() && "should follow from addRequired<>");
655 
656   BasicBlock *Latch = L.getLoopLatch();
657   if (!L.isLoopExiting(Latch)) {
658     FailureReason = "no loop latch";
659     return None;
660   }
661 
662   BasicBlock *Header = L.getHeader();
663   BasicBlock *Preheader = L.getLoopPreheader();
664   if (!Preheader) {
665     FailureReason = "no preheader";
666     return None;
667   }
668 
669   BranchInst *LatchBr = dyn_cast<BranchInst>(&*Latch->rbegin());
670   if (!LatchBr || LatchBr->isUnconditional()) {
671     FailureReason = "latch terminator not conditional branch";
672     return None;
673   }
674 
675   unsigned LatchBrExitIdx = LatchBr->getSuccessor(0) == Header ? 1 : 0;
676 
677   BranchProbability ExitProbability =
678     BPI.getEdgeProbability(LatchBr->getParent(), LatchBrExitIdx);
679 
680   if (ExitProbability > BranchProbability(1, MaxExitProbReciprocal)) {
681     FailureReason = "short running loop, not profitable";
682     return None;
683   }
684 
685   ICmpInst *ICI = dyn_cast<ICmpInst>(LatchBr->getCondition());
686   if (!ICI || !isa<IntegerType>(ICI->getOperand(0)->getType())) {
687     FailureReason = "latch terminator branch not conditional on integral icmp";
688     return None;
689   }
690 
691   const SCEV *LatchCount = SE.getExitCount(&L, Latch);
692   if (isa<SCEVCouldNotCompute>(LatchCount)) {
693     FailureReason = "could not compute latch count";
694     return None;
695   }
696 
697   ICmpInst::Predicate Pred = ICI->getPredicate();
698   Value *LeftValue = ICI->getOperand(0);
699   const SCEV *LeftSCEV = SE.getSCEV(LeftValue);
700   IntegerType *IndVarTy = cast<IntegerType>(LeftValue->getType());
701 
702   Value *RightValue = ICI->getOperand(1);
703   const SCEV *RightSCEV = SE.getSCEV(RightValue);
704 
705   // We canonicalize `ICI` such that `LeftSCEV` is an add recurrence.
706   if (!isa<SCEVAddRecExpr>(LeftSCEV)) {
707     if (isa<SCEVAddRecExpr>(RightSCEV)) {
708       std::swap(LeftSCEV, RightSCEV);
709       std::swap(LeftValue, RightValue);
710       Pred = ICmpInst::getSwappedPredicate(Pred);
711     } else {
712       FailureReason = "no add recurrences in the icmp";
713       return None;
714     }
715   }
716 
717   auto HasNoSignedWrap = [&](const SCEVAddRecExpr *AR) {
718     if (AR->getNoWrapFlags(SCEV::FlagNSW))
719       return true;
720 
721     IntegerType *Ty = cast<IntegerType>(AR->getType());
722     IntegerType *WideTy =
723         IntegerType::get(Ty->getContext(), Ty->getBitWidth() * 2);
724 
725     const SCEVAddRecExpr *ExtendAfterOp =
726         dyn_cast<SCEVAddRecExpr>(SE.getSignExtendExpr(AR, WideTy));
727     if (ExtendAfterOp) {
728       const SCEV *ExtendedStart = SE.getSignExtendExpr(AR->getStart(), WideTy);
729       const SCEV *ExtendedStep =
730           SE.getSignExtendExpr(AR->getStepRecurrence(SE), WideTy);
731 
732       bool NoSignedWrap = ExtendAfterOp->getStart() == ExtendedStart &&
733                           ExtendAfterOp->getStepRecurrence(SE) == ExtendedStep;
734 
735       if (NoSignedWrap)
736         return true;
737     }
738 
739     // We may have proved this when computing the sign extension above.
740     return AR->getNoWrapFlags(SCEV::FlagNSW) != SCEV::FlagAnyWrap;
741   };
742 
743   auto IsInductionVar = [&](const SCEVAddRecExpr *AR, bool &IsIncreasing) {
744     if (!AR->isAffine())
745       return false;
746 
747     // Currently we only work with induction variables that have been proved to
748     // not wrap.  This restriction can potentially be lifted in the future.
749 
750     if (!HasNoSignedWrap(AR))
751       return false;
752 
753     if (const SCEVConstant *StepExpr =
754             dyn_cast<SCEVConstant>(AR->getStepRecurrence(SE))) {
755       ConstantInt *StepCI = StepExpr->getValue();
756       if (StepCI->isOne() || StepCI->isMinusOne()) {
757         IsIncreasing = StepCI->isOne();
758         return true;
759       }
760     }
761 
762     return false;
763   };
764 
765   // `ICI` is interpreted as taking the backedge if the *next* value of the
766   // induction variable satisfies some constraint.
767 
768   const SCEVAddRecExpr *IndVarNext = cast<SCEVAddRecExpr>(LeftSCEV);
769   bool IsIncreasing = false;
770   if (!IsInductionVar(IndVarNext, IsIncreasing)) {
771     FailureReason = "LHS in icmp not induction variable";
772     return None;
773   }
774 
775   ConstantInt *One = ConstantInt::get(IndVarTy, 1);
776   // TODO: generalize the predicates here to also match their unsigned variants.
777   if (IsIncreasing) {
778     bool FoundExpectedPred =
779         (Pred == ICmpInst::ICMP_SLT && LatchBrExitIdx == 1) ||
780         (Pred == ICmpInst::ICMP_SGT && LatchBrExitIdx == 0);
781 
782     if (!FoundExpectedPred) {
783       FailureReason = "expected icmp slt semantically, found something else";
784       return None;
785     }
786 
787     if (LatchBrExitIdx == 0) {
788       if (CanBeSMax(SE, RightSCEV)) {
789         // TODO: this restriction is easily removable -- we just have to
790         // remember that the icmp was an slt and not an sle.
791         FailureReason = "limit may overflow when coercing sle to slt";
792         return None;
793       }
794 
795       IRBuilder<> B(&*Preheader->rbegin());
796       RightValue = B.CreateAdd(RightValue, One);
797     }
798 
799   } else {
800     bool FoundExpectedPred =
801         (Pred == ICmpInst::ICMP_SGT && LatchBrExitIdx == 1) ||
802         (Pred == ICmpInst::ICMP_SLT && LatchBrExitIdx == 0);
803 
804     if (!FoundExpectedPred) {
805       FailureReason = "expected icmp sgt semantically, found something else";
806       return None;
807     }
808 
809     if (LatchBrExitIdx == 0) {
810       if (CanBeSMin(SE, RightSCEV)) {
811         // TODO: this restriction is easily removable -- we just have to
812         // remember that the icmp was an sgt and not an sge.
813         FailureReason = "limit may overflow when coercing sge to sgt";
814         return None;
815       }
816 
817       IRBuilder<> B(&*Preheader->rbegin());
818       RightValue = B.CreateSub(RightValue, One);
819     }
820   }
821 
822   const SCEV *StartNext = IndVarNext->getStart();
823   const SCEV *Addend = SE.getNegativeSCEV(IndVarNext->getStepRecurrence(SE));
824   const SCEV *IndVarStart = SE.getAddExpr(StartNext, Addend);
825 
826   BasicBlock *LatchExit = LatchBr->getSuccessor(LatchBrExitIdx);
827 
828   assert(SE.getLoopDisposition(LatchCount, &L) ==
829              ScalarEvolution::LoopInvariant &&
830          "loop variant exit count doesn't make sense!");
831 
832   assert(!L.contains(LatchExit) && "expected an exit block!");
833   const DataLayout &DL = Preheader->getModule()->getDataLayout();
834   Value *IndVarStartV =
835       SCEVExpander(SE, DL, "irce")
836           .expandCodeFor(IndVarStart, IndVarTy, &*Preheader->rbegin());
837   IndVarStartV->setName("indvar.start");
838 
839   LoopStructure Result;
840 
841   Result.Tag = "main";
842   Result.Header = Header;
843   Result.Latch = Latch;
844   Result.LatchBr = LatchBr;
845   Result.LatchExit = LatchExit;
846   Result.LatchBrExitIdx = LatchBrExitIdx;
847   Result.IndVarStart = IndVarStartV;
848   Result.IndVarNext = LeftValue;
849   Result.IndVarIncreasing = IsIncreasing;
850   Result.LoopExitAt = RightValue;
851 
852   FailureReason = nullptr;
853 
854   return Result;
855 }
856 
857 Optional<LoopConstrainer::SubRanges>
calculateSubRanges() const858 LoopConstrainer::calculateSubRanges() const {
859   IntegerType *Ty = cast<IntegerType>(LatchTakenCount->getType());
860 
861   if (Range.getType() != Ty)
862     return None;
863 
864   LoopConstrainer::SubRanges Result;
865 
866   // I think we can be more aggressive here and make this nuw / nsw if the
867   // addition that feeds into the icmp for the latch's terminating branch is nuw
868   // / nsw.  In any case, a wrapping 2's complement addition is safe.
869   ConstantInt *One = ConstantInt::get(Ty, 1);
870   const SCEV *Start = SE.getSCEV(MainLoopStructure.IndVarStart);
871   const SCEV *End = SE.getSCEV(MainLoopStructure.LoopExitAt);
872 
873   bool Increasing = MainLoopStructure.IndVarIncreasing;
874 
875   // We compute `Smallest` and `Greatest` such that [Smallest, Greatest) is the
876   // range of values the induction variable takes.
877 
878   const SCEV *Smallest = nullptr, *Greatest = nullptr;
879 
880   if (Increasing) {
881     Smallest = Start;
882     Greatest = End;
883   } else {
884     // These two computations may sign-overflow.  Here is why that is okay:
885     //
886     // We know that the induction variable does not sign-overflow on any
887     // iteration except the last one, and it starts at `Start` and ends at
888     // `End`, decrementing by one every time.
889     //
890     //  * if `Smallest` sign-overflows we know `End` is `INT_SMAX`. Since the
891     //    induction variable is decreasing we know that that the smallest value
892     //    the loop body is actually executed with is `INT_SMIN` == `Smallest`.
893     //
894     //  * if `Greatest` sign-overflows, we know it can only be `INT_SMIN`.  In
895     //    that case, `Clamp` will always return `Smallest` and
896     //    [`Result.LowLimit`, `Result.HighLimit`) = [`Smallest`, `Smallest`)
897     //    will be an empty range.  Returning an empty range is always safe.
898     //
899 
900     Smallest = SE.getAddExpr(End, SE.getSCEV(One));
901     Greatest = SE.getAddExpr(Start, SE.getSCEV(One));
902   }
903 
904   auto Clamp = [this, Smallest, Greatest](const SCEV *S) {
905     return SE.getSMaxExpr(Smallest, SE.getSMinExpr(Greatest, S));
906   };
907 
908   // In some cases we can prove that we don't need a pre or post loop
909 
910   bool ProvablyNoPreloop =
911       SE.isKnownPredicate(ICmpInst::ICMP_SLE, Range.getBegin(), Smallest);
912   if (!ProvablyNoPreloop)
913     Result.LowLimit = Clamp(Range.getBegin());
914 
915   bool ProvablyNoPostLoop =
916       SE.isKnownPredicate(ICmpInst::ICMP_SLE, Greatest, Range.getEnd());
917   if (!ProvablyNoPostLoop)
918     Result.HighLimit = Clamp(Range.getEnd());
919 
920   return Result;
921 }
922 
cloneLoop(LoopConstrainer::ClonedLoop & Result,const char * Tag) const923 void LoopConstrainer::cloneLoop(LoopConstrainer::ClonedLoop &Result,
924                                 const char *Tag) const {
925   for (BasicBlock *BB : OriginalLoop.getBlocks()) {
926     BasicBlock *Clone = CloneBasicBlock(BB, Result.Map, Twine(".") + Tag, &F);
927     Result.Blocks.push_back(Clone);
928     Result.Map[BB] = Clone;
929   }
930 
931   auto GetClonedValue = [&Result](Value *V) {
932     assert(V && "null values not in domain!");
933     auto It = Result.Map.find(V);
934     if (It == Result.Map.end())
935       return V;
936     return static_cast<Value *>(It->second);
937   };
938 
939   Result.Structure = MainLoopStructure.map(GetClonedValue);
940   Result.Structure.Tag = Tag;
941 
942   for (unsigned i = 0, e = Result.Blocks.size(); i != e; ++i) {
943     BasicBlock *ClonedBB = Result.Blocks[i];
944     BasicBlock *OriginalBB = OriginalLoop.getBlocks()[i];
945 
946     assert(Result.Map[OriginalBB] == ClonedBB && "invariant!");
947 
948     for (Instruction &I : *ClonedBB)
949       RemapInstruction(&I, Result.Map,
950                        RF_NoModuleLevelChanges | RF_IgnoreMissingEntries);
951 
952     // Exit blocks will now have one more predecessor and their PHI nodes need
953     // to be edited to reflect that.  No phi nodes need to be introduced because
954     // the loop is in LCSSA.
955 
956     for (auto SBBI = succ_begin(OriginalBB), SBBE = succ_end(OriginalBB);
957          SBBI != SBBE; ++SBBI) {
958 
959       if (OriginalLoop.contains(*SBBI))
960         continue; // not an exit block
961 
962       for (Instruction &I : **SBBI) {
963         if (!isa<PHINode>(&I))
964           break;
965 
966         PHINode *PN = cast<PHINode>(&I);
967         Value *OldIncoming = PN->getIncomingValueForBlock(OriginalBB);
968         PN->addIncoming(GetClonedValue(OldIncoming), ClonedBB);
969       }
970     }
971   }
972 }
973 
changeIterationSpaceEnd(const LoopStructure & LS,BasicBlock * Preheader,Value * ExitSubloopAt,BasicBlock * ContinuationBlock) const974 LoopConstrainer::RewrittenRangeInfo LoopConstrainer::changeIterationSpaceEnd(
975     const LoopStructure &LS, BasicBlock *Preheader, Value *ExitSubloopAt,
976     BasicBlock *ContinuationBlock) const {
977 
978   // We start with a loop with a single latch:
979   //
980   //    +--------------------+
981   //    |                    |
982   //    |     preheader      |
983   //    |                    |
984   //    +--------+-----------+
985   //             |      ----------------\
986   //             |     /                |
987   //    +--------v----v------+          |
988   //    |                    |          |
989   //    |      header        |          |
990   //    |                    |          |
991   //    +--------------------+          |
992   //                                    |
993   //            .....                   |
994   //                                    |
995   //    +--------------------+          |
996   //    |                    |          |
997   //    |       latch        >----------/
998   //    |                    |
999   //    +-------v------------+
1000   //            |
1001   //            |
1002   //            |   +--------------------+
1003   //            |   |                    |
1004   //            +--->   original exit    |
1005   //                |                    |
1006   //                +--------------------+
1007   //
1008   // We change the control flow to look like
1009   //
1010   //
1011   //    +--------------------+
1012   //    |                    |
1013   //    |     preheader      >-------------------------+
1014   //    |                    |                         |
1015   //    +--------v-----------+                         |
1016   //             |    /-------------+                  |
1017   //             |   /              |                  |
1018   //    +--------v--v--------+      |                  |
1019   //    |                    |      |                  |
1020   //    |      header        |      |   +--------+     |
1021   //    |                    |      |   |        |     |
1022   //    +--------------------+      |   |  +-----v-----v-----------+
1023   //                                |   |  |                       |
1024   //                                |   |  |     .pseudo.exit      |
1025   //                                |   |  |                       |
1026   //                                |   |  +-----------v-----------+
1027   //                                |   |              |
1028   //            .....               |   |              |
1029   //                                |   |     +--------v-------------+
1030   //    +--------------------+      |   |     |                      |
1031   //    |                    |      |   |     |   ContinuationBlock  |
1032   //    |       latch        >------+   |     |                      |
1033   //    |                    |          |     +----------------------+
1034   //    +---------v----------+          |
1035   //              |                     |
1036   //              |                     |
1037   //              |     +---------------^-----+
1038   //              |     |                     |
1039   //              +----->    .exit.selector   |
1040   //                    |                     |
1041   //                    +----------v----------+
1042   //                               |
1043   //     +--------------------+    |
1044   //     |                    |    |
1045   //     |   original exit    <----+
1046   //     |                    |
1047   //     +--------------------+
1048   //
1049 
1050   RewrittenRangeInfo RRI;
1051 
1052   auto BBInsertLocation = std::next(Function::iterator(LS.Latch));
1053   RRI.ExitSelector = BasicBlock::Create(Ctx, Twine(LS.Tag) + ".exit.selector",
1054                                         &F, &*BBInsertLocation);
1055   RRI.PseudoExit = BasicBlock::Create(Ctx, Twine(LS.Tag) + ".pseudo.exit", &F,
1056                                       &*BBInsertLocation);
1057 
1058   BranchInst *PreheaderJump = cast<BranchInst>(&*Preheader->rbegin());
1059   bool Increasing = LS.IndVarIncreasing;
1060 
1061   IRBuilder<> B(PreheaderJump);
1062 
1063   // EnterLoopCond - is it okay to start executing this `LS'?
1064   Value *EnterLoopCond = Increasing
1065                              ? B.CreateICmpSLT(LS.IndVarStart, ExitSubloopAt)
1066                              : B.CreateICmpSGT(LS.IndVarStart, ExitSubloopAt);
1067 
1068   B.CreateCondBr(EnterLoopCond, LS.Header, RRI.PseudoExit);
1069   PreheaderJump->eraseFromParent();
1070 
1071   LS.LatchBr->setSuccessor(LS.LatchBrExitIdx, RRI.ExitSelector);
1072   B.SetInsertPoint(LS.LatchBr);
1073   Value *TakeBackedgeLoopCond =
1074       Increasing ? B.CreateICmpSLT(LS.IndVarNext, ExitSubloopAt)
1075                  : B.CreateICmpSGT(LS.IndVarNext, ExitSubloopAt);
1076   Value *CondForBranch = LS.LatchBrExitIdx == 1
1077                              ? TakeBackedgeLoopCond
1078                              : B.CreateNot(TakeBackedgeLoopCond);
1079 
1080   LS.LatchBr->setCondition(CondForBranch);
1081 
1082   B.SetInsertPoint(RRI.ExitSelector);
1083 
1084   // IterationsLeft - are there any more iterations left, given the original
1085   // upper bound on the induction variable?  If not, we branch to the "real"
1086   // exit.
1087   Value *IterationsLeft = Increasing
1088                               ? B.CreateICmpSLT(LS.IndVarNext, LS.LoopExitAt)
1089                               : B.CreateICmpSGT(LS.IndVarNext, LS.LoopExitAt);
1090   B.CreateCondBr(IterationsLeft, RRI.PseudoExit, LS.LatchExit);
1091 
1092   BranchInst *BranchToContinuation =
1093       BranchInst::Create(ContinuationBlock, RRI.PseudoExit);
1094 
1095   // We emit PHI nodes into `RRI.PseudoExit' that compute the "latest" value of
1096   // each of the PHI nodes in the loop header.  This feeds into the initial
1097   // value of the same PHI nodes if/when we continue execution.
1098   for (Instruction &I : *LS.Header) {
1099     if (!isa<PHINode>(&I))
1100       break;
1101 
1102     PHINode *PN = cast<PHINode>(&I);
1103 
1104     PHINode *NewPHI = PHINode::Create(PN->getType(), 2, PN->getName() + ".copy",
1105                                       BranchToContinuation);
1106 
1107     NewPHI->addIncoming(PN->getIncomingValueForBlock(Preheader), Preheader);
1108     NewPHI->addIncoming(PN->getIncomingValueForBlock(LS.Latch),
1109                         RRI.ExitSelector);
1110     RRI.PHIValuesAtPseudoExit.push_back(NewPHI);
1111   }
1112 
1113   RRI.IndVarEnd = PHINode::Create(LS.IndVarNext->getType(), 2, "indvar.end",
1114                                   BranchToContinuation);
1115   RRI.IndVarEnd->addIncoming(LS.IndVarStart, Preheader);
1116   RRI.IndVarEnd->addIncoming(LS.IndVarNext, RRI.ExitSelector);
1117 
1118   // The latch exit now has a branch from `RRI.ExitSelector' instead of
1119   // `LS.Latch'.  The PHI nodes need to be updated to reflect that.
1120   for (Instruction &I : *LS.LatchExit) {
1121     if (PHINode *PN = dyn_cast<PHINode>(&I))
1122       replacePHIBlock(PN, LS.Latch, RRI.ExitSelector);
1123     else
1124       break;
1125   }
1126 
1127   return RRI;
1128 }
1129 
rewriteIncomingValuesForPHIs(LoopStructure & LS,BasicBlock * ContinuationBlock,const LoopConstrainer::RewrittenRangeInfo & RRI) const1130 void LoopConstrainer::rewriteIncomingValuesForPHIs(
1131     LoopStructure &LS, BasicBlock *ContinuationBlock,
1132     const LoopConstrainer::RewrittenRangeInfo &RRI) const {
1133 
1134   unsigned PHIIndex = 0;
1135   for (Instruction &I : *LS.Header) {
1136     if (!isa<PHINode>(&I))
1137       break;
1138 
1139     PHINode *PN = cast<PHINode>(&I);
1140 
1141     for (unsigned i = 0, e = PN->getNumIncomingValues(); i < e; ++i)
1142       if (PN->getIncomingBlock(i) == ContinuationBlock)
1143         PN->setIncomingValue(i, RRI.PHIValuesAtPseudoExit[PHIIndex++]);
1144   }
1145 
1146   LS.IndVarStart = RRI.IndVarEnd;
1147 }
1148 
createPreheader(const LoopStructure & LS,BasicBlock * OldPreheader,const char * Tag) const1149 BasicBlock *LoopConstrainer::createPreheader(const LoopStructure &LS,
1150                                              BasicBlock *OldPreheader,
1151                                              const char *Tag) const {
1152 
1153   BasicBlock *Preheader = BasicBlock::Create(Ctx, Tag, &F, LS.Header);
1154   BranchInst::Create(LS.Header, Preheader);
1155 
1156   for (Instruction &I : *LS.Header) {
1157     if (!isa<PHINode>(&I))
1158       break;
1159 
1160     PHINode *PN = cast<PHINode>(&I);
1161     for (unsigned i = 0, e = PN->getNumIncomingValues(); i < e; ++i)
1162       replacePHIBlock(PN, OldPreheader, Preheader);
1163   }
1164 
1165   return Preheader;
1166 }
1167 
addToParentLoopIfNeeded(ArrayRef<BasicBlock * > BBs)1168 void LoopConstrainer::addToParentLoopIfNeeded(ArrayRef<BasicBlock *> BBs) {
1169   Loop *ParentLoop = OriginalLoop.getParentLoop();
1170   if (!ParentLoop)
1171     return;
1172 
1173   for (BasicBlock *BB : BBs)
1174     ParentLoop->addBasicBlockToLoop(BB, OriginalLoopInfo);
1175 }
1176 
run()1177 bool LoopConstrainer::run() {
1178   BasicBlock *Preheader = nullptr;
1179   LatchTakenCount = SE.getExitCount(&OriginalLoop, MainLoopStructure.Latch);
1180   Preheader = OriginalLoop.getLoopPreheader();
1181   assert(!isa<SCEVCouldNotCompute>(LatchTakenCount) && Preheader != nullptr &&
1182          "preconditions!");
1183 
1184   OriginalPreheader = Preheader;
1185   MainLoopPreheader = Preheader;
1186 
1187   Optional<SubRanges> MaybeSR = calculateSubRanges();
1188   if (!MaybeSR.hasValue()) {
1189     DEBUG(dbgs() << "irce: could not compute subranges\n");
1190     return false;
1191   }
1192 
1193   SubRanges SR = MaybeSR.getValue();
1194   bool Increasing = MainLoopStructure.IndVarIncreasing;
1195   IntegerType *IVTy =
1196       cast<IntegerType>(MainLoopStructure.IndVarNext->getType());
1197 
1198   SCEVExpander Expander(SE, F.getParent()->getDataLayout(), "irce");
1199   Instruction *InsertPt = OriginalPreheader->getTerminator();
1200 
1201   // It would have been better to make `PreLoop' and `PostLoop'
1202   // `Optional<ClonedLoop>'s, but `ValueToValueMapTy' does not have a copy
1203   // constructor.
1204   ClonedLoop PreLoop, PostLoop;
1205   bool NeedsPreLoop =
1206       Increasing ? SR.LowLimit.hasValue() : SR.HighLimit.hasValue();
1207   bool NeedsPostLoop =
1208       Increasing ? SR.HighLimit.hasValue() : SR.LowLimit.hasValue();
1209 
1210   Value *ExitPreLoopAt = nullptr;
1211   Value *ExitMainLoopAt = nullptr;
1212   const SCEVConstant *MinusOneS =
1213       cast<SCEVConstant>(SE.getConstant(IVTy, -1, true /* isSigned */));
1214 
1215   if (NeedsPreLoop) {
1216     const SCEV *ExitPreLoopAtSCEV = nullptr;
1217 
1218     if (Increasing)
1219       ExitPreLoopAtSCEV = *SR.LowLimit;
1220     else {
1221       if (CanBeSMin(SE, *SR.HighLimit)) {
1222         DEBUG(dbgs() << "irce: could not prove no-overflow when computing "
1223                      << "preloop exit limit.  HighLimit = " << *(*SR.HighLimit)
1224                      << "\n");
1225         return false;
1226       }
1227       ExitPreLoopAtSCEV = SE.getAddExpr(*SR.HighLimit, MinusOneS);
1228     }
1229 
1230     ExitPreLoopAt = Expander.expandCodeFor(ExitPreLoopAtSCEV, IVTy, InsertPt);
1231     ExitPreLoopAt->setName("exit.preloop.at");
1232   }
1233 
1234   if (NeedsPostLoop) {
1235     const SCEV *ExitMainLoopAtSCEV = nullptr;
1236 
1237     if (Increasing)
1238       ExitMainLoopAtSCEV = *SR.HighLimit;
1239     else {
1240       if (CanBeSMin(SE, *SR.LowLimit)) {
1241         DEBUG(dbgs() << "irce: could not prove no-overflow when computing "
1242                      << "mainloop exit limit.  LowLimit = " << *(*SR.LowLimit)
1243                      << "\n");
1244         return false;
1245       }
1246       ExitMainLoopAtSCEV = SE.getAddExpr(*SR.LowLimit, MinusOneS);
1247     }
1248 
1249     ExitMainLoopAt = Expander.expandCodeFor(ExitMainLoopAtSCEV, IVTy, InsertPt);
1250     ExitMainLoopAt->setName("exit.mainloop.at");
1251   }
1252 
1253   // We clone these ahead of time so that we don't have to deal with changing
1254   // and temporarily invalid IR as we transform the loops.
1255   if (NeedsPreLoop)
1256     cloneLoop(PreLoop, "preloop");
1257   if (NeedsPostLoop)
1258     cloneLoop(PostLoop, "postloop");
1259 
1260   RewrittenRangeInfo PreLoopRRI;
1261 
1262   if (NeedsPreLoop) {
1263     Preheader->getTerminator()->replaceUsesOfWith(MainLoopStructure.Header,
1264                                                   PreLoop.Structure.Header);
1265 
1266     MainLoopPreheader =
1267         createPreheader(MainLoopStructure, Preheader, "mainloop");
1268     PreLoopRRI = changeIterationSpaceEnd(PreLoop.Structure, Preheader,
1269                                          ExitPreLoopAt, MainLoopPreheader);
1270     rewriteIncomingValuesForPHIs(MainLoopStructure, MainLoopPreheader,
1271                                  PreLoopRRI);
1272   }
1273 
1274   BasicBlock *PostLoopPreheader = nullptr;
1275   RewrittenRangeInfo PostLoopRRI;
1276 
1277   if (NeedsPostLoop) {
1278     PostLoopPreheader =
1279         createPreheader(PostLoop.Structure, Preheader, "postloop");
1280     PostLoopRRI = changeIterationSpaceEnd(MainLoopStructure, MainLoopPreheader,
1281                                           ExitMainLoopAt, PostLoopPreheader);
1282     rewriteIncomingValuesForPHIs(PostLoop.Structure, PostLoopPreheader,
1283                                  PostLoopRRI);
1284   }
1285 
1286   BasicBlock *NewMainLoopPreheader =
1287       MainLoopPreheader != Preheader ? MainLoopPreheader : nullptr;
1288   BasicBlock *NewBlocks[] = {PostLoopPreheader,        PreLoopRRI.PseudoExit,
1289                              PreLoopRRI.ExitSelector,  PostLoopRRI.PseudoExit,
1290                              PostLoopRRI.ExitSelector, NewMainLoopPreheader};
1291 
1292   // Some of the above may be nullptr, filter them out before passing to
1293   // addToParentLoopIfNeeded.
1294   auto NewBlocksEnd =
1295       std::remove(std::begin(NewBlocks), std::end(NewBlocks), nullptr);
1296 
1297   addToParentLoopIfNeeded(makeArrayRef(std::begin(NewBlocks), NewBlocksEnd));
1298   addToParentLoopIfNeeded(PreLoop.Blocks);
1299   addToParentLoopIfNeeded(PostLoop.Blocks);
1300 
1301   return true;
1302 }
1303 
1304 /// Computes and returns a range of values for the induction variable (IndVar)
1305 /// in which the range check can be safely elided.  If it cannot compute such a
1306 /// range, returns None.
1307 Optional<InductiveRangeCheck::Range>
computeSafeIterationSpace(ScalarEvolution & SE,const SCEVAddRecExpr * IndVar,IRBuilder<> &) const1308 InductiveRangeCheck::computeSafeIterationSpace(ScalarEvolution &SE,
1309                                                const SCEVAddRecExpr *IndVar,
1310                                                IRBuilder<> &) const {
1311   // IndVar is of the form "A + B * I" (where "I" is the canonical induction
1312   // variable, that may or may not exist as a real llvm::Value in the loop) and
1313   // this inductive range check is a range check on the "C + D * I" ("C" is
1314   // getOffset() and "D" is getScale()).  We rewrite the value being range
1315   // checked to "M + N * IndVar" where "N" = "D * B^(-1)" and "M" = "C - NA".
1316   // Currently we support this only for "B" = "D" = { 1 or -1 }, but the code
1317   // can be generalized as needed.
1318   //
1319   // The actual inequalities we solve are of the form
1320   //
1321   //   0 <= M + 1 * IndVar < L given L >= 0  (i.e. N == 1)
1322   //
1323   // The inequality is satisfied by -M <= IndVar < (L - M) [^1].  All additions
1324   // and subtractions are twos-complement wrapping and comparisons are signed.
1325   //
1326   // Proof:
1327   //
1328   //   If there exists IndVar such that -M <= IndVar < (L - M) then it follows
1329   //   that -M <= (-M + L) [== Eq. 1].  Since L >= 0, if (-M + L) sign-overflows
1330   //   then (-M + L) < (-M).  Hence by [Eq. 1], (-M + L) could not have
1331   //   overflown.
1332   //
1333   //   This means IndVar = t + (-M) for t in [0, L).  Hence (IndVar + M) = t.
1334   //   Hence 0 <= (IndVar + M) < L
1335 
1336   // [^1]: Note that the solution does _not_ apply if L < 0; consider values M =
1337   // 127, IndVar = 126 and L = -2 in an i8 world.
1338 
1339   if (!IndVar->isAffine())
1340     return None;
1341 
1342   const SCEV *A = IndVar->getStart();
1343   const SCEVConstant *B = dyn_cast<SCEVConstant>(IndVar->getStepRecurrence(SE));
1344   if (!B)
1345     return None;
1346 
1347   const SCEV *C = getOffset();
1348   const SCEVConstant *D = dyn_cast<SCEVConstant>(getScale());
1349   if (D != B)
1350     return None;
1351 
1352   ConstantInt *ConstD = D->getValue();
1353   if (!(ConstD->isMinusOne() || ConstD->isOne()))
1354     return None;
1355 
1356   const SCEV *M = SE.getMinusSCEV(C, A);
1357 
1358   const SCEV *Begin = SE.getNegativeSCEV(M);
1359   const SCEV *UpperLimit = nullptr;
1360 
1361   // We strengthen "0 <= I" to "0 <= I < INT_SMAX" and "I < L" to "0 <= I < L".
1362   // We can potentially do much better here.
1363   if (Value *V = getLength()) {
1364     UpperLimit = SE.getSCEV(V);
1365   } else {
1366     assert(Kind == InductiveRangeCheck::RANGE_CHECK_LOWER && "invariant!");
1367     unsigned BitWidth = cast<IntegerType>(IndVar->getType())->getBitWidth();
1368     UpperLimit = SE.getConstant(APInt::getSignedMaxValue(BitWidth));
1369   }
1370 
1371   const SCEV *End = SE.getMinusSCEV(UpperLimit, M);
1372   return InductiveRangeCheck::Range(Begin, End);
1373 }
1374 
1375 static Optional<InductiveRangeCheck::Range>
IntersectRange(ScalarEvolution & SE,const Optional<InductiveRangeCheck::Range> & R1,const InductiveRangeCheck::Range & R2,IRBuilder<> & B)1376 IntersectRange(ScalarEvolution &SE,
1377                const Optional<InductiveRangeCheck::Range> &R1,
1378                const InductiveRangeCheck::Range &R2, IRBuilder<> &B) {
1379   if (!R1.hasValue())
1380     return R2;
1381   auto &R1Value = R1.getValue();
1382 
1383   // TODO: we could widen the smaller range and have this work; but for now we
1384   // bail out to keep things simple.
1385   if (R1Value.getType() != R2.getType())
1386     return None;
1387 
1388   const SCEV *NewBegin = SE.getSMaxExpr(R1Value.getBegin(), R2.getBegin());
1389   const SCEV *NewEnd = SE.getSMinExpr(R1Value.getEnd(), R2.getEnd());
1390 
1391   return InductiveRangeCheck::Range(NewBegin, NewEnd);
1392 }
1393 
runOnLoop(Loop * L,LPPassManager & LPM)1394 bool InductiveRangeCheckElimination::runOnLoop(Loop *L, LPPassManager &LPM) {
1395   if (L->getBlocks().size() >= LoopSizeCutoff) {
1396     DEBUG(dbgs() << "irce: giving up constraining loop, too large\n";);
1397     return false;
1398   }
1399 
1400   BasicBlock *Preheader = L->getLoopPreheader();
1401   if (!Preheader) {
1402     DEBUG(dbgs() << "irce: loop has no preheader, leaving\n");
1403     return false;
1404   }
1405 
1406   LLVMContext &Context = Preheader->getContext();
1407   InductiveRangeCheck::AllocatorTy IRCAlloc;
1408   SmallVector<InductiveRangeCheck *, 16> RangeChecks;
1409   ScalarEvolution &SE = getAnalysis<ScalarEvolutionWrapperPass>().getSE();
1410   BranchProbabilityInfo &BPI =
1411       getAnalysis<BranchProbabilityInfoWrapperPass>().getBPI();
1412 
1413   for (auto BBI : L->getBlocks())
1414     if (BranchInst *TBI = dyn_cast<BranchInst>(BBI->getTerminator()))
1415       if (InductiveRangeCheck *IRC =
1416           InductiveRangeCheck::create(IRCAlloc, TBI, L, SE, BPI))
1417         RangeChecks.push_back(IRC);
1418 
1419   if (RangeChecks.empty())
1420     return false;
1421 
1422   auto PrintRecognizedRangeChecks = [&](raw_ostream &OS) {
1423     OS << "irce: looking at loop "; L->print(OS);
1424     OS << "irce: loop has " << RangeChecks.size()
1425        << " inductive range checks: \n";
1426     for (InductiveRangeCheck *IRC : RangeChecks)
1427       IRC->print(OS);
1428   };
1429 
1430   DEBUG(PrintRecognizedRangeChecks(dbgs()));
1431 
1432   if (PrintRangeChecks)
1433     PrintRecognizedRangeChecks(errs());
1434 
1435   const char *FailureReason = nullptr;
1436   Optional<LoopStructure> MaybeLoopStructure =
1437       LoopStructure::parseLoopStructure(SE, BPI, *L, FailureReason);
1438   if (!MaybeLoopStructure.hasValue()) {
1439     DEBUG(dbgs() << "irce: could not parse loop structure: " << FailureReason
1440                  << "\n";);
1441     return false;
1442   }
1443   LoopStructure LS = MaybeLoopStructure.getValue();
1444   bool Increasing = LS.IndVarIncreasing;
1445   const SCEV *MinusOne =
1446       SE.getConstant(LS.IndVarNext->getType(), Increasing ? -1 : 1, true);
1447   const SCEVAddRecExpr *IndVar =
1448       cast<SCEVAddRecExpr>(SE.getAddExpr(SE.getSCEV(LS.IndVarNext), MinusOne));
1449 
1450   Optional<InductiveRangeCheck::Range> SafeIterRange;
1451   Instruction *ExprInsertPt = Preheader->getTerminator();
1452 
1453   SmallVector<InductiveRangeCheck *, 4> RangeChecksToEliminate;
1454 
1455   IRBuilder<> B(ExprInsertPt);
1456   for (InductiveRangeCheck *IRC : RangeChecks) {
1457     auto Result = IRC->computeSafeIterationSpace(SE, IndVar, B);
1458     if (Result.hasValue()) {
1459       auto MaybeSafeIterRange =
1460         IntersectRange(SE, SafeIterRange, Result.getValue(), B);
1461       if (MaybeSafeIterRange.hasValue()) {
1462         RangeChecksToEliminate.push_back(IRC);
1463         SafeIterRange = MaybeSafeIterRange.getValue();
1464       }
1465     }
1466   }
1467 
1468   if (!SafeIterRange.hasValue())
1469     return false;
1470 
1471   LoopConstrainer LC(*L, getAnalysis<LoopInfoWrapperPass>().getLoopInfo(), LS,
1472                      SE, SafeIterRange.getValue());
1473   bool Changed = LC.run();
1474 
1475   if (Changed) {
1476     auto PrintConstrainedLoopInfo = [L]() {
1477       dbgs() << "irce: in function ";
1478       dbgs() << L->getHeader()->getParent()->getName() << ": ";
1479       dbgs() << "constrained ";
1480       L->print(dbgs());
1481     };
1482 
1483     DEBUG(PrintConstrainedLoopInfo());
1484 
1485     if (PrintChangedLoops)
1486       PrintConstrainedLoopInfo();
1487 
1488     // Optimize away the now-redundant range checks.
1489 
1490     for (InductiveRangeCheck *IRC : RangeChecksToEliminate) {
1491       ConstantInt *FoldedRangeCheck = IRC->getPassingDirection()
1492                                           ? ConstantInt::getTrue(Context)
1493                                           : ConstantInt::getFalse(Context);
1494       IRC->getBranch()->setCondition(FoldedRangeCheck);
1495     }
1496   }
1497 
1498   return Changed;
1499 }
1500 
createInductiveRangeCheckEliminationPass()1501 Pass *llvm::createInductiveRangeCheckEliminationPass() {
1502   return new InductiveRangeCheckElimination;
1503 }
1504