LLVM  6.0.0svn
InductiveRangeCheckElimination.cpp
Go to the documentation of this file.
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"
46 #include "llvm/Analysis/LoopInfo.h"
47 #include "llvm/Analysis/LoopPass.h"
51 #include "llvm/IR/Dominators.h"
52 #include "llvm/IR/Function.h"
53 #include "llvm/IR/IRBuilder.h"
54 #include "llvm/IR/Instructions.h"
55 #include "llvm/IR/PatternMatch.h"
56 #include "llvm/Pass.h"
57 #include "llvm/Support/Debug.h"
59 #include "llvm/Transforms/Scalar.h"
64 
65 using namespace llvm;
66 
67 static cl::opt<unsigned> LoopSizeCutoff("irce-loop-size-cutoff", cl::Hidden,
68  cl::init(64));
69 
70 static cl::opt<bool> PrintChangedLoops("irce-print-changed-loops", cl::Hidden,
71  cl::init(false));
72 
73 static cl::opt<bool> PrintRangeChecks("irce-print-range-checks", cl::Hidden,
74  cl::init(false));
75 
76 static cl::opt<int> MaxExitProbReciprocal("irce-max-exit-prob-reciprocal",
77  cl::Hidden, cl::init(10));
78 
79 static cl::opt<bool> SkipProfitabilityChecks("irce-skip-profitability-checks",
80  cl::Hidden, cl::init(false));
81 
82 static cl::opt<bool> AllowUnsignedLatchCondition("irce-allow-unsigned-latch",
83  cl::Hidden, cl::init(false));
84 
85 static const char *ClonedLoopTag = "irce.loop.clone";
86 
87 #define DEBUG_TYPE "irce"
88 
89 namespace {
90 
91 /// An inductive range check is conditional branch in a loop with
92 ///
93 /// 1. a very cold successor (i.e. the branch jumps to that successor very
94 /// rarely)
95 ///
96 /// and
97 ///
98 /// 2. a condition that is provably true for some contiguous range of values
99 /// taken by the containing loop's induction variable.
100 ///
101 class InductiveRangeCheck {
102  // Classifies a range check
103  enum RangeCheckKind : unsigned {
104  // Range check of the form "0 <= I".
105  RANGE_CHECK_LOWER = 1,
106 
107  // Range check of the form "I < L" where L is known positive.
108  RANGE_CHECK_UPPER = 2,
109 
110  // The logical and of the RANGE_CHECK_LOWER and RANGE_CHECK_UPPER
111  // conditions.
112  RANGE_CHECK_BOTH = RANGE_CHECK_LOWER | RANGE_CHECK_UPPER,
113 
114  // Unrecognized range check condition.
115  RANGE_CHECK_UNKNOWN = (unsigned)-1
116  };
117 
118  static StringRef rangeCheckKindToStr(RangeCheckKind);
119 
120  const SCEV *Offset = nullptr;
121  const SCEV *Scale = nullptr;
122  Value *Length = nullptr;
123  Use *CheckUse = nullptr;
124  RangeCheckKind Kind = RANGE_CHECK_UNKNOWN;
125 
126  static RangeCheckKind parseRangeCheckICmp(Loop *L, ICmpInst *ICI,
127  ScalarEvolution &SE, Value *&Index,
128  Value *&Length);
129 
130  static void
131  extractRangeChecksFromCond(Loop *L, ScalarEvolution &SE, Use &ConditionUse,
133  SmallPtrSetImpl<Value *> &Visited);
134 
135 public:
136  const SCEV *getOffset() const { return Offset; }
137  const SCEV *getScale() const { return Scale; }
138  Value *getLength() const { return Length; }
139 
140  void print(raw_ostream &OS) const {
141  OS << "InductiveRangeCheck:\n";
142  OS << " Kind: " << rangeCheckKindToStr(Kind) << "\n";
143  OS << " Offset: ";
144  Offset->print(OS);
145  OS << " Scale: ";
146  Scale->print(OS);
147  OS << " Length: ";
148  if (Length)
149  Length->print(OS);
150  else
151  OS << "(null)";
152  OS << "\n CheckUse: ";
153  getCheckUse()->getUser()->print(OS);
154  OS << " Operand: " << getCheckUse()->getOperandNo() << "\n";
155  }
156 
158  void dump() {
159  print(dbgs());
160  }
161 
162  Use *getCheckUse() const { return CheckUse; }
163 
164  /// Represents an signed integer range [Range.getBegin(), Range.getEnd()). If
165  /// R.getEnd() sle R.getBegin(), then R denotes the empty range.
166 
167  class Range {
168  const SCEV *Begin;
169  const SCEV *End;
170 
171  public:
172  Range(const SCEV *Begin, const SCEV *End) : Begin(Begin), End(End) {
173  assert(Begin->getType() == End->getType() && "ill-typed range!");
174  }
175 
176  Type *getType() const { return Begin->getType(); }
177  const SCEV *getBegin() const { return Begin; }
178  const SCEV *getEnd() const { return End; }
179  bool isEmpty() const { return Begin == End; }
180  };
181 
182  /// This is the value the condition of the branch needs to evaluate to for the
183  /// branch to take the hot successor (see (1) above).
184  bool getPassingDirection() { return true; }
185 
186  /// Computes a range for the induction variable (IndVar) in which the range
187  /// check is redundant and can be constant-folded away. The induction
188  /// variable is not required to be the canonical {0,+,1} induction variable.
189  Optional<Range> computeSafeIterationSpace(ScalarEvolution &SE,
190  const SCEVAddRecExpr *IndVar) const;
191 
192  /// Parse out a set of inductive range checks from \p BI and append them to \p
193  /// Checks.
194  ///
195  /// NB! There may be conditions feeding into \p BI that aren't inductive range
196  /// checks, and hence don't end up in \p Checks.
197  static void
198  extractRangeChecksFromBranch(BranchInst *BI, Loop *L, ScalarEvolution &SE,
201 };
202 
203 class InductiveRangeCheckElimination : public LoopPass {
204 public:
205  static char ID;
206  InductiveRangeCheckElimination() : LoopPass(ID) {
209  }
210 
211  void getAnalysisUsage(AnalysisUsage &AU) const override {
214  }
215 
216  bool runOnLoop(Loop *L, LPPassManager &LPM) override;
217 };
218 
220 }
221 
222 INITIALIZE_PASS_BEGIN(InductiveRangeCheckElimination, "irce",
223  "Inductive range check elimination", false, false)
226 INITIALIZE_PASS_END(InductiveRangeCheckElimination, "irce",
227  "Inductive range check elimination", false, false)
228 
229 StringRef InductiveRangeCheck::rangeCheckKindToStr(
230  InductiveRangeCheck::RangeCheckKind RCK) {
231  switch (RCK) {
232  case InductiveRangeCheck::RANGE_CHECK_UNKNOWN:
233  return "RANGE_CHECK_UNKNOWN";
234 
235  case InductiveRangeCheck::RANGE_CHECK_UPPER:
236  return "RANGE_CHECK_UPPER";
237 
238  case InductiveRangeCheck::RANGE_CHECK_LOWER:
239  return "RANGE_CHECK_LOWER";
240 
241  case InductiveRangeCheck::RANGE_CHECK_BOTH:
242  return "RANGE_CHECK_BOTH";
243  }
244 
245  llvm_unreachable("unknown range check type!");
246 }
247 
248 /// Parse a single ICmp instruction, `ICI`, into a range check. If `ICI` cannot
249 /// be interpreted as a range check, return `RANGE_CHECK_UNKNOWN` and set
250 /// `Index` and `Length` to `nullptr`. Otherwise set `Index` to the value being
251 /// range checked, and set `Length` to the upper limit `Index` is being range
252 /// checked with if (and only if) the range check type is stronger or equal to
253 /// RANGE_CHECK_UPPER.
254 ///
255 InductiveRangeCheck::RangeCheckKind
256 InductiveRangeCheck::parseRangeCheckICmp(Loop *L, ICmpInst *ICI,
257  ScalarEvolution &SE, Value *&Index,
258  Value *&Length) {
259 
260  auto IsNonNegativeAndNotLoopVarying = [&SE, L](Value *V) {
261  const SCEV *S = SE.getSCEV(V);
262  if (isa<SCEVCouldNotCompute>(S))
263  return false;
264 
266  SE.isKnownNonNegative(S);
267  };
268 
269  using namespace llvm::PatternMatch;
270 
271  ICmpInst::Predicate Pred = ICI->getPredicate();
272  Value *LHS = ICI->getOperand(0);
273  Value *RHS = ICI->getOperand(1);
274 
275  switch (Pred) {
276  default:
277  return RANGE_CHECK_UNKNOWN;
278 
279  case ICmpInst::ICMP_SLE:
280  std::swap(LHS, RHS);
282  case ICmpInst::ICMP_SGE:
283  if (match(RHS, m_ConstantInt<0>())) {
284  Index = LHS;
285  return RANGE_CHECK_LOWER;
286  }
287  return RANGE_CHECK_UNKNOWN;
288 
289  case ICmpInst::ICMP_SLT:
290  std::swap(LHS, RHS);
292  case ICmpInst::ICMP_SGT:
293  if (match(RHS, m_ConstantInt<-1>())) {
294  Index = LHS;
295  return RANGE_CHECK_LOWER;
296  }
297 
298  if (IsNonNegativeAndNotLoopVarying(LHS)) {
299  Index = RHS;
300  Length = LHS;
301  return RANGE_CHECK_UPPER;
302  }
303  return RANGE_CHECK_UNKNOWN;
304 
305  case ICmpInst::ICMP_ULT:
306  std::swap(LHS, RHS);
308  case ICmpInst::ICMP_UGT:
309  if (IsNonNegativeAndNotLoopVarying(LHS)) {
310  Index = RHS;
311  Length = LHS;
312  return RANGE_CHECK_BOTH;
313  }
314  return RANGE_CHECK_UNKNOWN;
315  }
316 
317  llvm_unreachable("default clause returns!");
318 }
319 
320 void InductiveRangeCheck::extractRangeChecksFromCond(
321  Loop *L, ScalarEvolution &SE, Use &ConditionUse,
323  SmallPtrSetImpl<Value *> &Visited) {
324  using namespace llvm::PatternMatch;
325 
326  Value *Condition = ConditionUse.get();
327  if (!Visited.insert(Condition).second)
328  return;
329 
330  if (match(Condition, m_And(m_Value(), m_Value()))) {
332  extractRangeChecksFromCond(L, SE, cast<User>(Condition)->getOperandUse(0),
333  SubChecks, Visited);
334  extractRangeChecksFromCond(L, SE, cast<User>(Condition)->getOperandUse(1),
335  SubChecks, Visited);
336 
337  if (SubChecks.size() == 2) {
338  // Handle a special case where we know how to merge two checks separately
339  // checking the upper and lower bounds into a full range check.
340  const auto &RChkA = SubChecks[0];
341  const auto &RChkB = SubChecks[1];
342  if ((RChkA.Length == RChkB.Length || !RChkA.Length || !RChkB.Length) &&
343  RChkA.Offset == RChkB.Offset && RChkA.Scale == RChkB.Scale) {
344 
345  // If RChkA.Kind == RChkB.Kind then we just found two identical checks.
346  // But if one of them is a RANGE_CHECK_LOWER and the other is a
347  // RANGE_CHECK_UPPER (only possibility if they're different) then
348  // together they form a RANGE_CHECK_BOTH.
349  SubChecks[0].Kind =
350  (InductiveRangeCheck::RangeCheckKind)(RChkA.Kind | RChkB.Kind);
351  SubChecks[0].Length = RChkA.Length ? RChkA.Length : RChkB.Length;
352  SubChecks[0].CheckUse = &ConditionUse;
353 
354  // We updated one of the checks in place, now erase the other.
355  SubChecks.pop_back();
356  }
357  }
358 
359  Checks.insert(Checks.end(), SubChecks.begin(), SubChecks.end());
360  return;
361  }
362 
363  ICmpInst *ICI = dyn_cast<ICmpInst>(Condition);
364  if (!ICI)
365  return;
366 
367  Value *Length = nullptr, *Index;
368  auto RCKind = parseRangeCheckICmp(L, ICI, SE, Index, Length);
369  if (RCKind == InductiveRangeCheck::RANGE_CHECK_UNKNOWN)
370  return;
371 
372  const auto *IndexAddRec = dyn_cast<SCEVAddRecExpr>(SE.getSCEV(Index));
373  bool IsAffineIndex =
374  IndexAddRec && (IndexAddRec->getLoop() == L) && IndexAddRec->isAffine();
375 
376  if (!IsAffineIndex)
377  return;
378 
379  InductiveRangeCheck IRC;
380  IRC.Length = Length;
381  IRC.Offset = IndexAddRec->getStart();
382  IRC.Scale = IndexAddRec->getStepRecurrence(SE);
383  IRC.CheckUse = &ConditionUse;
384  IRC.Kind = RCKind;
385  Checks.push_back(IRC);
386 }
387 
388 void InductiveRangeCheck::extractRangeChecksFromBranch(
391 
392  if (BI->isUnconditional() || BI->getParent() == L->getLoopLatch())
393  return;
394 
395  BranchProbability LikelyTaken(15, 16);
396 
398  BPI.getEdgeProbability(BI->getParent(), (unsigned)0) < LikelyTaken)
399  return;
400 
401  SmallPtrSet<Value *, 8> Visited;
402  InductiveRangeCheck::extractRangeChecksFromCond(L, SE, BI->getOperandUse(0),
403  Checks, Visited);
404 }
405 
406 // Add metadata to the loop L to disable loop optimizations. Callers need to
407 // confirm that optimizing loop L is not beneficial.
409  // We do not care about any existing loopID related metadata for L, since we
410  // are setting all loop metadata to false.
412  // Reserve first location for self reference to the LoopID metadata node.
413  MDNode *Dummy = MDNode::get(Context, {});
414  MDNode *DisableUnroll = MDNode::get(
415  Context, {MDString::get(Context, "llvm.loop.unroll.disable")});
416  Metadata *FalseVal =
418  MDNode *DisableVectorize = MDNode::get(
419  Context,
420  {MDString::get(Context, "llvm.loop.vectorize.enable"), FalseVal});
421  MDNode *DisableLICMVersioning = MDNode::get(
422  Context, {MDString::get(Context, "llvm.loop.licm_versioning.disable")});
423  MDNode *DisableDistribution= MDNode::get(
424  Context,
425  {MDString::get(Context, "llvm.loop.distribute.enable"), FalseVal});
426  MDNode *NewLoopID =
427  MDNode::get(Context, {Dummy, DisableUnroll, DisableVectorize,
428  DisableLICMVersioning, DisableDistribution});
429  // Set operand 0 to refer to the loop id itself.
430  NewLoopID->replaceOperandWith(0, NewLoopID);
431  L.setLoopID(NewLoopID);
432 }
433 
434 namespace {
435 
436 // Keeps track of the structure of a loop. This is similar to llvm::Loop,
437 // except that it is more lightweight and can track the state of a loop through
438 // changing and potentially invalid IR. This structure also formalizes the
439 // kinds of loops we can deal with -- ones that have a single latch that is also
440 // an exiting block *and* have a canonical induction variable.
441 struct LoopStructure {
442  const char *Tag;
443 
444  BasicBlock *Header;
445  BasicBlock *Latch;
446 
447  // `Latch's terminator instruction is `LatchBr', and it's `LatchBrExitIdx'th
448  // successor is `LatchExit', the exit block of the loop.
449  BranchInst *LatchBr;
450  BasicBlock *LatchExit;
451  unsigned LatchBrExitIdx;
452 
453  // The loop represented by this instance of LoopStructure is semantically
454  // equivalent to:
455  //
456  // intN_ty inc = IndVarIncreasing ? 1 : -1;
457  // pred_ty predicate = IndVarIncreasing ? ICMP_SLT : ICMP_SGT;
458  //
459  // for (intN_ty iv = IndVarStart; predicate(iv, LoopExitAt); iv = IndVarBase)
460  // ... body ...
461 
462  Value *IndVarBase;
463  Value *IndVarStart;
464  Value *IndVarStep;
465  Value *LoopExitAt;
466  bool IndVarIncreasing;
467  bool IsSignedPredicate;
468 
469  LoopStructure()
470  : Tag(""), Header(nullptr), Latch(nullptr), LatchBr(nullptr),
471  LatchExit(nullptr), LatchBrExitIdx(-1), IndVarBase(nullptr),
472  IndVarStart(nullptr), IndVarStep(nullptr), LoopExitAt(nullptr),
473  IndVarIncreasing(false), IsSignedPredicate(true) {}
474 
475  template <typename M> LoopStructure map(M Map) const {
476  LoopStructure Result;
477  Result.Tag = Tag;
478  Result.Header = cast<BasicBlock>(Map(Header));
479  Result.Latch = cast<BasicBlock>(Map(Latch));
480  Result.LatchBr = cast<BranchInst>(Map(LatchBr));
481  Result.LatchExit = cast<BasicBlock>(Map(LatchExit));
482  Result.LatchBrExitIdx = LatchBrExitIdx;
483  Result.IndVarBase = Map(IndVarBase);
484  Result.IndVarStart = Map(IndVarStart);
485  Result.IndVarStep = Map(IndVarStep);
486  Result.LoopExitAt = Map(LoopExitAt);
487  Result.IndVarIncreasing = IndVarIncreasing;
488  Result.IsSignedPredicate = IsSignedPredicate;
489  return Result;
490  }
491 
492  static Optional<LoopStructure> parseLoopStructure(ScalarEvolution &,
494  Loop &,
495  const char *&);
496 };
497 
498 /// This class is used to constrain loops to run within a given iteration space.
499 /// The algorithm this class implements is given a Loop and a range [Begin,
500 /// End). The algorithm then tries to break out a "main loop" out of the loop
501 /// it is given in a way that the "main loop" runs with the induction variable
502 /// in a subset of [Begin, End). The algorithm emits appropriate pre and post
503 /// loops to run any remaining iterations. The pre loop runs any iterations in
504 /// which the induction variable is < Begin, and the post loop runs any
505 /// iterations in which the induction variable is >= End.
506 ///
507 class LoopConstrainer {
508  // The representation of a clone of the original loop we started out with.
509  struct ClonedLoop {
510  // The cloned blocks
511  std::vector<BasicBlock *> Blocks;
512 
513  // `Map` maps values in the clonee into values in the cloned version
514  ValueToValueMapTy Map;
515 
516  // An instance of `LoopStructure` for the cloned loop
517  LoopStructure Structure;
518  };
519 
520  // Result of rewriting the range of a loop. See changeIterationSpaceEnd for
521  // more details on what these fields mean.
522  struct RewrittenRangeInfo {
523  BasicBlock *PseudoExit;
524  BasicBlock *ExitSelector;
525  std::vector<PHINode *> PHIValuesAtPseudoExit;
526  PHINode *IndVarEnd;
527 
528  RewrittenRangeInfo()
529  : PseudoExit(nullptr), ExitSelector(nullptr), IndVarEnd(nullptr) {}
530  };
531 
532  // Calculated subranges we restrict the iteration space of the main loop to.
533  // See the implementation of `calculateSubRanges' for more details on how
534  // these fields are computed. `LowLimit` is None if there is no restriction
535  // on low end of the restricted iteration space of the main loop. `HighLimit`
536  // is None if there is no restriction on high end of the restricted iteration
537  // space of the main loop.
538 
539  struct SubRanges {
540  Optional<const SCEV *> LowLimit;
541  Optional<const SCEV *> HighLimit;
542  };
543 
544  // A utility function that does a `replaceUsesOfWith' on the incoming block
545  // set of a `PHINode' -- replaces instances of `Block' in the `PHINode's
546  // incoming block list with `ReplaceBy'.
547  static void replacePHIBlock(PHINode *PN, BasicBlock *Block,
548  BasicBlock *ReplaceBy);
549 
550  // Compute a safe set of limits for the main loop to run in -- effectively the
551  // intersection of `Range' and the iteration space of the original loop.
552  // Return None if unable to compute the set of subranges.
553  //
554  Optional<SubRanges> calculateSubRanges(bool IsSignedPredicate) const;
555 
556  // Clone `OriginalLoop' and return the result in CLResult. The IR after
557  // running `cloneLoop' is well formed except for the PHI nodes in CLResult --
558  // the PHI nodes say that there is an incoming edge from `OriginalPreheader`
559  // but there is no such edge.
560  //
561  void cloneLoop(ClonedLoop &CLResult, const char *Tag) const;
562 
563  // Create the appropriate loop structure needed to describe a cloned copy of
564  // `Original`. The clone is described by `VM`.
565  Loop *createClonedLoopStructure(Loop *Original, Loop *Parent,
566  ValueToValueMapTy &VM);
567 
568  // Rewrite the iteration space of the loop denoted by (LS, Preheader). The
569  // iteration space of the rewritten loop ends at ExitLoopAt. The start of the
570  // iteration space is not changed. `ExitLoopAt' is assumed to be slt
571  // `OriginalHeaderCount'.
572  //
573  // If there are iterations left to execute, control is made to jump to
574  // `ContinuationBlock', otherwise they take the normal loop exit. The
575  // returned `RewrittenRangeInfo' object is populated as follows:
576  //
577  // .PseudoExit is a basic block that unconditionally branches to
578  // `ContinuationBlock'.
579  //
580  // .ExitSelector is a basic block that decides, on exit from the loop,
581  // whether to branch to the "true" exit or to `PseudoExit'.
582  //
583  // .PHIValuesAtPseudoExit are PHINodes in `PseudoExit' that compute the value
584  // for each PHINode in the loop header on taking the pseudo exit.
585  //
586  // After changeIterationSpaceEnd, `Preheader' is no longer a legitimate
587  // preheader because it is made to branch to the loop header only
588  // conditionally.
589  //
590  RewrittenRangeInfo
591  changeIterationSpaceEnd(const LoopStructure &LS, BasicBlock *Preheader,
592  Value *ExitLoopAt,
593  BasicBlock *ContinuationBlock) const;
594 
595  // The loop denoted by `LS' has `OldPreheader' as its preheader. This
596  // function creates a new preheader for `LS' and returns it.
597  //
598  BasicBlock *createPreheader(const LoopStructure &LS, BasicBlock *OldPreheader,
599  const char *Tag) const;
600 
601  // `ContinuationBlockAndPreheader' was the continuation block for some call to
602  // `changeIterationSpaceEnd' and is the preheader to the loop denoted by `LS'.
603  // This function rewrites the PHI nodes in `LS.Header' to start with the
604  // correct value.
605  void rewriteIncomingValuesForPHIs(
606  LoopStructure &LS, BasicBlock *ContinuationBlockAndPreheader,
607  const LoopConstrainer::RewrittenRangeInfo &RRI) const;
608 
609  // Even though we do not preserve any passes at this time, we at least need to
610  // keep the parent loop structure consistent. The `LPPassManager' seems to
611  // verify this after running a loop pass. This function adds the list of
612  // blocks denoted by BBs to this loops parent loop if required.
613  void addToParentLoopIfNeeded(ArrayRef<BasicBlock *> BBs);
614 
615  // Some global state.
616  Function &F;
617  LLVMContext &Ctx;
618  ScalarEvolution &SE;
619  DominatorTree &DT;
620  LPPassManager &LPM;
621  LoopInfo &LI;
622 
623  // Information about the original loop we started out with.
624  Loop &OriginalLoop;
625  const SCEV *LatchTakenCount;
626  BasicBlock *OriginalPreheader;
627 
628  // The preheader of the main loop. This may or may not be different from
629  // `OriginalPreheader'.
630  BasicBlock *MainLoopPreheader;
631 
632  // The range we need to run the main loop in.
633  InductiveRangeCheck::Range Range;
634 
635  // The structure of the main loop (see comment at the beginning of this class
636  // for a definition)
637  LoopStructure MainLoopStructure;
638 
639 public:
640  LoopConstrainer(Loop &L, LoopInfo &LI, LPPassManager &LPM,
641  const LoopStructure &LS, ScalarEvolution &SE,
642  DominatorTree &DT, InductiveRangeCheck::Range R)
643  : F(*L.getHeader()->getParent()), Ctx(L.getHeader()->getContext()),
644  SE(SE), DT(DT), LPM(LPM), LI(LI), OriginalLoop(L),
645  LatchTakenCount(nullptr), OriginalPreheader(nullptr),
646  MainLoopPreheader(nullptr), Range(R), MainLoopStructure(LS) {}
647 
648  // Entry point for the algorithm. Returns true on success.
649  bool run();
650 };
651 
652 }
653 
654 void LoopConstrainer::replacePHIBlock(PHINode *PN, BasicBlock *Block,
655  BasicBlock *ReplaceBy) {
656  for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
657  if (PN->getIncomingBlock(i) == Block)
658  PN->setIncomingBlock(i, ReplaceBy);
659 }
660 
661 static bool CanBeMax(ScalarEvolution &SE, const SCEV *S, bool Signed) {
662  APInt Max = Signed ?
663  APInt::getSignedMaxValue(cast<IntegerType>(S->getType())->getBitWidth()) :
664  APInt::getMaxValue(cast<IntegerType>(S->getType())->getBitWidth());
665  return SE.getSignedRange(S).contains(Max) &&
666  SE.getUnsignedRange(S).contains(Max);
667 }
668 
669 static bool SumCanReachMax(ScalarEvolution &SE, const SCEV *S1, const SCEV *S2,
670  bool Signed) {
671  // S1 < INT_MAX - S2 ===> S1 + S2 < INT_MAX.
672  assert(SE.isKnownNonNegative(S2) &&
673  "We expected the 2nd arg to be non-negative!");
674  const SCEV *Max = SE.getConstant(
675  Signed ? APInt::getSignedMaxValue(
676  cast<IntegerType>(S1->getType())->getBitWidth())
678  cast<IntegerType>(S1->getType())->getBitWidth()));
679  const SCEV *CapForS1 = SE.getMinusSCEV(Max, S2);
681  S1, CapForS1);
682 }
683 
684 static bool CanBeMin(ScalarEvolution &SE, const SCEV *S, bool Signed) {
685  APInt Min = Signed ?
686  APInt::getSignedMinValue(cast<IntegerType>(S->getType())->getBitWidth()) :
687  APInt::getMinValue(cast<IntegerType>(S->getType())->getBitWidth());
688  return SE.getSignedRange(S).contains(Min) &&
689  SE.getUnsignedRange(S).contains(Min);
690 }
691 
692 static bool SumCanReachMin(ScalarEvolution &SE, const SCEV *S1, const SCEV *S2,
693  bool Signed) {
694  // S1 > INT_MIN - S2 ===> S1 + S2 > INT_MIN.
695  assert(SE.isKnownNonPositive(S2) &&
696  "We expected the 2nd arg to be non-positive!");
697  const SCEV *Max = SE.getConstant(
698  Signed ? APInt::getSignedMinValue(
699  cast<IntegerType>(S1->getType())->getBitWidth())
701  cast<IntegerType>(S1->getType())->getBitWidth()));
702  const SCEV *CapForS1 = SE.getMinusSCEV(Max, S2);
704  S1, CapForS1);
705 }
706 
708 LoopStructure::parseLoopStructure(ScalarEvolution &SE,
710  Loop &L, const char *&FailureReason) {
711  if (!L.isLoopSimplifyForm()) {
712  FailureReason = "loop not in LoopSimplify form";
713  return None;
714  }
715 
716  BasicBlock *Latch = L.getLoopLatch();
717  assert(Latch && "Simplified loops only have one latch!");
718 
719  if (Latch->getTerminator()->getMetadata(ClonedLoopTag)) {
720  FailureReason = "loop has already been cloned";
721  return None;
722  }
723 
724  if (!L.isLoopExiting(Latch)) {
725  FailureReason = "no loop latch";
726  return None;
727  }
728 
729  BasicBlock *Header = L.getHeader();
730  BasicBlock *Preheader = L.getLoopPreheader();
731  if (!Preheader) {
732  FailureReason = "no preheader";
733  return None;
734  }
735 
736  BranchInst *LatchBr = dyn_cast<BranchInst>(Latch->getTerminator());
737  if (!LatchBr || LatchBr->isUnconditional()) {
738  FailureReason = "latch terminator not conditional branch";
739  return None;
740  }
741 
742  unsigned LatchBrExitIdx = LatchBr->getSuccessor(0) == Header ? 1 : 0;
743 
744  BranchProbability ExitProbability =
745  BPI.getEdgeProbability(LatchBr->getParent(), LatchBrExitIdx);
746 
748  ExitProbability > BranchProbability(1, MaxExitProbReciprocal)) {
749  FailureReason = "short running loop, not profitable";
750  return None;
751  }
752 
753  ICmpInst *ICI = dyn_cast<ICmpInst>(LatchBr->getCondition());
754  if (!ICI || !isa<IntegerType>(ICI->getOperand(0)->getType())) {
755  FailureReason = "latch terminator branch not conditional on integral icmp";
756  return None;
757  }
758 
759  const SCEV *LatchCount = SE.getExitCount(&L, Latch);
760  if (isa<SCEVCouldNotCompute>(LatchCount)) {
761  FailureReason = "could not compute latch count";
762  return None;
763  }
764 
765  ICmpInst::Predicate Pred = ICI->getPredicate();
766  Value *LeftValue = ICI->getOperand(0);
767  const SCEV *LeftSCEV = SE.getSCEV(LeftValue);
768  IntegerType *IndVarTy = cast<IntegerType>(LeftValue->getType());
769 
770  Value *RightValue = ICI->getOperand(1);
771  const SCEV *RightSCEV = SE.getSCEV(RightValue);
772 
773  // We canonicalize `ICI` such that `LeftSCEV` is an add recurrence.
774  if (!isa<SCEVAddRecExpr>(LeftSCEV)) {
775  if (isa<SCEVAddRecExpr>(RightSCEV)) {
776  std::swap(LeftSCEV, RightSCEV);
777  std::swap(LeftValue, RightValue);
778  Pred = ICmpInst::getSwappedPredicate(Pred);
779  } else {
780  FailureReason = "no add recurrences in the icmp";
781  return None;
782  }
783  }
784 
785  auto HasNoSignedWrap = [&](const SCEVAddRecExpr *AR) {
786  if (AR->getNoWrapFlags(SCEV::FlagNSW))
787  return true;
788 
789  IntegerType *Ty = cast<IntegerType>(AR->getType());
790  IntegerType *WideTy =
791  IntegerType::get(Ty->getContext(), Ty->getBitWidth() * 2);
792 
793  const SCEVAddRecExpr *ExtendAfterOp =
794  dyn_cast<SCEVAddRecExpr>(SE.getSignExtendExpr(AR, WideTy));
795  if (ExtendAfterOp) {
796  const SCEV *ExtendedStart = SE.getSignExtendExpr(AR->getStart(), WideTy);
797  const SCEV *ExtendedStep =
798  SE.getSignExtendExpr(AR->getStepRecurrence(SE), WideTy);
799 
800  bool NoSignedWrap = ExtendAfterOp->getStart() == ExtendedStart &&
801  ExtendAfterOp->getStepRecurrence(SE) == ExtendedStep;
802 
803  if (NoSignedWrap)
804  return true;
805  }
806 
807  // We may have proved this when computing the sign extension above.
808  return AR->getNoWrapFlags(SCEV::FlagNSW) != SCEV::FlagAnyWrap;
809  };
810 
811  // Here we check whether the suggested AddRec is an induction variable that
812  // can be handled (i.e. with known constant step), and if yes, calculate its
813  // step and identify whether it is increasing or decreasing.
814  auto IsInductionVar = [&](const SCEVAddRecExpr *AR, bool &IsIncreasing,
815  ConstantInt *&StepCI) {
816  if (!AR->isAffine())
817  return false;
818 
819  // Currently we only work with induction variables that have been proved to
820  // not wrap. This restriction can potentially be lifted in the future.
821 
822  if (!HasNoSignedWrap(AR))
823  return false;
824 
825  if (const SCEVConstant *StepExpr =
826  dyn_cast<SCEVConstant>(AR->getStepRecurrence(SE))) {
827  StepCI = StepExpr->getValue();
828  assert(!StepCI->isZero() && "Zero step?");
829  IsIncreasing = !StepCI->isNegative();
830  return true;
831  }
832 
833  return false;
834  };
835 
836  // `ICI` is interpreted as taking the backedge if the *next* value of the
837  // induction variable satisfies some constraint.
838 
839  const SCEVAddRecExpr *IndVarBase = cast<SCEVAddRecExpr>(LeftSCEV);
840  bool IsIncreasing = false;
841  bool IsSignedPredicate = true;
842  ConstantInt *StepCI;
843  if (!IsInductionVar(IndVarBase, IsIncreasing, StepCI)) {
844  FailureReason = "LHS in icmp not induction variable";
845  return None;
846  }
847 
848  const SCEV *StartNext = IndVarBase->getStart();
849  const SCEV *Addend = SE.getNegativeSCEV(IndVarBase->getStepRecurrence(SE));
850  const SCEV *IndVarStart = SE.getAddExpr(StartNext, Addend);
851  const SCEV *Step = SE.getSCEV(StepCI);
852 
853  ConstantInt *One = ConstantInt::get(IndVarTy, 1);
854  if (IsIncreasing) {
855  bool DecreasedRightValueByOne = false;
856  if (StepCI->isOne()) {
857  // Try to turn eq/ne predicates to those we can work with.
858  if (Pred == ICmpInst::ICMP_NE && LatchBrExitIdx == 1)
859  // while (++i != len) { while (++i < len) {
860  // ... ---> ...
861  // } }
862  // If both parts are known non-negative, it is profitable to use
863  // unsigned comparison in increasing loop. This allows us to make the
864  // comparison check against "RightSCEV + 1" more optimistic.
865  if (SE.isKnownNonNegative(IndVarStart) &&
866  SE.isKnownNonNegative(RightSCEV))
867  Pred = ICmpInst::ICMP_ULT;
868  else
869  Pred = ICmpInst::ICMP_SLT;
870  else if (Pred == ICmpInst::ICMP_EQ && LatchBrExitIdx == 0 &&
871  !CanBeMin(SE, RightSCEV, /* IsSignedPredicate */ true)) {
872  // while (true) { while (true) {
873  // if (++i == len) ---> if (++i > len - 1)
874  // break; break;
875  // ... ...
876  // } }
877  // TODO: Insert ICMP_UGT if both are non-negative?
878  Pred = ICmpInst::ICMP_SGT;
879  RightSCEV = SE.getMinusSCEV(RightSCEV, SE.getOne(RightSCEV->getType()));
880  DecreasedRightValueByOne = true;
881  }
882  }
883 
884  bool LTPred = (Pred == ICmpInst::ICMP_SLT || Pred == ICmpInst::ICMP_ULT);
885  bool GTPred = (Pred == ICmpInst::ICMP_SGT || Pred == ICmpInst::ICMP_UGT);
886  bool FoundExpectedPred =
887  (LTPred && LatchBrExitIdx == 1) || (GTPred && LatchBrExitIdx == 0);
888 
889  if (!FoundExpectedPred) {
890  FailureReason = "expected icmp slt semantically, found something else";
891  return None;
892  }
893 
894  IsSignedPredicate =
895  Pred == ICmpInst::ICMP_SLT || Pred == ICmpInst::ICMP_SGT;
896 
897  // FIXME: We temporarily disable unsigned latch conditions by default
898  // because of found problems with intersecting signed and unsigned ranges.
899  // We are going to turn it on once the problems are fixed.
900  if (!IsSignedPredicate && !AllowUnsignedLatchCondition) {
901  FailureReason = "unsigned latch conditions are explicitly prohibited";
902  return None;
903  }
904 
905  // The predicate that we need to check that the induction variable lies
906  // within bounds.
907  ICmpInst::Predicate BoundPred =
908  IsSignedPredicate ? CmpInst::ICMP_SLT : CmpInst::ICMP_ULT;
909 
910  if (LatchBrExitIdx == 0) {
911  const SCEV *StepMinusOne = SE.getMinusSCEV(Step,
912  SE.getOne(Step->getType()));
913  if (SumCanReachMax(SE, RightSCEV, StepMinusOne, IsSignedPredicate)) {
914  // TODO: this restriction is easily removable -- we just have to
915  // remember that the icmp was an slt and not an sle.
916  FailureReason = "limit may overflow when coercing le to lt";
917  return None;
918  }
919 
920  if (!SE.isLoopEntryGuardedByCond(
921  &L, BoundPred, IndVarStart,
922  SE.getAddExpr(RightSCEV, Step))) {
923  FailureReason = "Induction variable start not bounded by upper limit";
924  return None;
925  }
926 
927  // We need to increase the right value unless we have already decreased
928  // it virtually when we replaced EQ with SGT.
929  if (!DecreasedRightValueByOne) {
930  IRBuilder<> B(Preheader->getTerminator());
931  RightValue = B.CreateAdd(RightValue, One);
932  }
933  } else {
934  if (!SE.isLoopEntryGuardedByCond(&L, BoundPred, IndVarStart, RightSCEV)) {
935  FailureReason = "Induction variable start not bounded by upper limit";
936  return None;
937  }
938  assert(!DecreasedRightValueByOne &&
939  "Right value can be decreased only for LatchBrExitIdx == 0!");
940  }
941  } else {
942  bool IncreasedRightValueByOne = false;
943  if (StepCI->isMinusOne()) {
944  // Try to turn eq/ne predicates to those we can work with.
945  if (Pred == ICmpInst::ICMP_NE && LatchBrExitIdx == 1)
946  // while (--i != len) { while (--i > len) {
947  // ... ---> ...
948  // } }
949  // We intentionally don't turn the predicate into UGT even if we know
950  // that both operands are non-negative, because it will only pessimize
951  // our check against "RightSCEV - 1".
952  Pred = ICmpInst::ICMP_SGT;
953  else if (Pred == ICmpInst::ICMP_EQ && LatchBrExitIdx == 0 &&
954  !CanBeMax(SE, RightSCEV, /* IsSignedPredicate */ true)) {
955  // while (true) { while (true) {
956  // if (--i == len) ---> if (--i < len + 1)
957  // break; break;
958  // ... ...
959  // } }
960  // TODO: Insert ICMP_ULT if both are non-negative?
961  Pred = ICmpInst::ICMP_SLT;
962  RightSCEV = SE.getAddExpr(RightSCEV, SE.getOne(RightSCEV->getType()));
963  IncreasedRightValueByOne = true;
964  }
965  }
966 
967  bool LTPred = (Pred == ICmpInst::ICMP_SLT || Pred == ICmpInst::ICMP_ULT);
968  bool GTPred = (Pred == ICmpInst::ICMP_SGT || Pred == ICmpInst::ICMP_UGT);
969 
970  bool FoundExpectedPred =
971  (GTPred && LatchBrExitIdx == 1) || (LTPred && LatchBrExitIdx == 0);
972 
973  if (!FoundExpectedPred) {
974  FailureReason = "expected icmp sgt semantically, found something else";
975  return None;
976  }
977 
978  IsSignedPredicate =
979  Pred == ICmpInst::ICMP_SLT || Pred == ICmpInst::ICMP_SGT;
980 
981  // FIXME: We temporarily disable unsigned latch conditions by default
982  // because of found problems with intersecting signed and unsigned ranges.
983  // We are going to turn it on once the problems are fixed.
984  if (!IsSignedPredicate && !AllowUnsignedLatchCondition) {
985  FailureReason = "unsigned latch conditions are explicitly prohibited";
986  return None;
987  }
988 
989  // The predicate that we need to check that the induction variable lies
990  // within bounds.
991  ICmpInst::Predicate BoundPred =
992  IsSignedPredicate ? CmpInst::ICMP_SGT : CmpInst::ICMP_UGT;
993 
994  if (LatchBrExitIdx == 0) {
995  const SCEV *StepPlusOne = SE.getAddExpr(Step, SE.getOne(Step->getType()));
996  if (SumCanReachMin(SE, RightSCEV, StepPlusOne, IsSignedPredicate)) {
997  // TODO: this restriction is easily removable -- we just have to
998  // remember that the icmp was an sgt and not an sge.
999  FailureReason = "limit may overflow when coercing ge to gt";
1000  return None;
1001  }
1002 
1003  if (!SE.isLoopEntryGuardedByCond(
1004  &L, BoundPred, IndVarStart,
1005  SE.getMinusSCEV(RightSCEV, SE.getOne(RightSCEV->getType())))) {
1006  FailureReason = "Induction variable start not bounded by lower limit";
1007  return None;
1008  }
1009 
1010  // We need to decrease the right value unless we have already increased
1011  // it virtually when we replaced EQ with SLT.
1012  if (!IncreasedRightValueByOne) {
1013  IRBuilder<> B(Preheader->getTerminator());
1014  RightValue = B.CreateSub(RightValue, One);
1015  }
1016  } else {
1017  if (!SE.isLoopEntryGuardedByCond(&L, BoundPred, IndVarStart, RightSCEV)) {
1018  FailureReason = "Induction variable start not bounded by lower limit";
1019  return None;
1020  }
1021  assert(!IncreasedRightValueByOne &&
1022  "Right value can be increased only for LatchBrExitIdx == 0!");
1023  }
1024  }
1025  BasicBlock *LatchExit = LatchBr->getSuccessor(LatchBrExitIdx);
1026 
1027  assert(SE.getLoopDisposition(LatchCount, &L) ==
1029  "loop variant exit count doesn't make sense!");
1030 
1031  assert(!L.contains(LatchExit) && "expected an exit block!");
1032  const DataLayout &DL = Preheader->getModule()->getDataLayout();
1033  Value *IndVarStartV =
1034  SCEVExpander(SE, DL, "irce")
1035  .expandCodeFor(IndVarStart, IndVarTy, Preheader->getTerminator());
1036  IndVarStartV->setName("indvar.start");
1037 
1038  LoopStructure Result;
1039 
1040  Result.Tag = "main";
1041  Result.Header = Header;
1042  Result.Latch = Latch;
1043  Result.LatchBr = LatchBr;
1044  Result.LatchExit = LatchExit;
1045  Result.LatchBrExitIdx = LatchBrExitIdx;
1046  Result.IndVarStart = IndVarStartV;
1047  Result.IndVarStep = StepCI;
1048  Result.IndVarBase = LeftValue;
1049  Result.IndVarIncreasing = IsIncreasing;
1050  Result.LoopExitAt = RightValue;
1051  Result.IsSignedPredicate = IsSignedPredicate;
1052 
1053  FailureReason = nullptr;
1054 
1055  return Result;
1056 }
1057 
1059 LoopConstrainer::calculateSubRanges(bool IsSignedPredicate) const {
1060  IntegerType *Ty = cast<IntegerType>(LatchTakenCount->getType());
1061 
1062  if (Range.getType() != Ty)
1063  return None;
1064 
1065  LoopConstrainer::SubRanges Result;
1066 
1067  // I think we can be more aggressive here and make this nuw / nsw if the
1068  // addition that feeds into the icmp for the latch's terminating branch is nuw
1069  // / nsw. In any case, a wrapping 2's complement addition is safe.
1070  const SCEV *Start = SE.getSCEV(MainLoopStructure.IndVarStart);
1071  const SCEV *End = SE.getSCEV(MainLoopStructure.LoopExitAt);
1072 
1073  bool Increasing = MainLoopStructure.IndVarIncreasing;
1074 
1075  // We compute `Smallest` and `Greatest` such that [Smallest, Greatest), or
1076  // [Smallest, GreatestSeen] is the range of values the induction variable
1077  // takes.
1078 
1079  const SCEV *Smallest = nullptr, *Greatest = nullptr, *GreatestSeen = nullptr;
1080 
1081  const SCEV *One = SE.getOne(Ty);
1082  if (Increasing) {
1083  Smallest = Start;
1084  Greatest = End;
1085  // No overflow, because the range [Smallest, GreatestSeen] is not empty.
1086  GreatestSeen = SE.getMinusSCEV(End, One);
1087  } else {
1088  // These two computations may sign-overflow. Here is why that is okay:
1089  //
1090  // We know that the induction variable does not sign-overflow on any
1091  // iteration except the last one, and it starts at `Start` and ends at
1092  // `End`, decrementing by one every time.
1093  //
1094  // * if `Smallest` sign-overflows we know `End` is `INT_SMAX`. Since the
1095  // induction variable is decreasing we know that that the smallest value
1096  // the loop body is actually executed with is `INT_SMIN` == `Smallest`.
1097  //
1098  // * if `Greatest` sign-overflows, we know it can only be `INT_SMIN`. In
1099  // that case, `Clamp` will always return `Smallest` and
1100  // [`Result.LowLimit`, `Result.HighLimit`) = [`Smallest`, `Smallest`)
1101  // will be an empty range. Returning an empty range is always safe.
1102  //
1103 
1104  Smallest = SE.getAddExpr(End, One);
1105  Greatest = SE.getAddExpr(Start, One);
1106  GreatestSeen = Start;
1107  }
1108 
1109  auto Clamp = [this, Smallest, Greatest, IsSignedPredicate](const SCEV *S) {
1110  bool MaybeNegativeValues = IsSignedPredicate || !SE.isKnownNonNegative(S);
1111  return MaybeNegativeValues
1112  ? SE.getSMaxExpr(Smallest, SE.getSMinExpr(Greatest, S))
1113  : SE.getUMaxExpr(Smallest, SE.getUMinExpr(Greatest, S));
1114  };
1115 
1116  // In some cases we can prove that we don't need a pre or post loop.
1117  ICmpInst::Predicate PredLE =
1118  IsSignedPredicate ? ICmpInst::ICMP_SLE : ICmpInst::ICMP_ULE;
1119  ICmpInst::Predicate PredLT =
1120  IsSignedPredicate ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT;
1121 
1122  bool ProvablyNoPreloop =
1123  SE.isKnownPredicate(PredLE, Range.getBegin(), Smallest);
1124  if (!ProvablyNoPreloop)
1125  Result.LowLimit = Clamp(Range.getBegin());
1126 
1127  bool ProvablyNoPostLoop =
1128  SE.isKnownPredicate(PredLT, GreatestSeen, Range.getEnd());
1129  if (!ProvablyNoPostLoop)
1130  Result.HighLimit = Clamp(Range.getEnd());
1131 
1132  return Result;
1133 }
1134 
1135 void LoopConstrainer::cloneLoop(LoopConstrainer::ClonedLoop &Result,
1136  const char *Tag) const {
1137  for (BasicBlock *BB : OriginalLoop.getBlocks()) {
1138  BasicBlock *Clone = CloneBasicBlock(BB, Result.Map, Twine(".") + Tag, &F);
1139  Result.Blocks.push_back(Clone);
1140  Result.Map[BB] = Clone;
1141  }
1142 
1143  auto GetClonedValue = [&Result](Value *V) {
1144  assert(V && "null values not in domain!");
1145  auto It = Result.Map.find(V);
1146  if (It == Result.Map.end())
1147  return V;
1148  return static_cast<Value *>(It->second);
1149  };
1150 
1151  auto *ClonedLatch =
1152  cast<BasicBlock>(GetClonedValue(OriginalLoop.getLoopLatch()));
1153  ClonedLatch->getTerminator()->setMetadata(ClonedLoopTag,
1154  MDNode::get(Ctx, {}));
1155 
1156  Result.Structure = MainLoopStructure.map(GetClonedValue);
1157  Result.Structure.Tag = Tag;
1158 
1159  for (unsigned i = 0, e = Result.Blocks.size(); i != e; ++i) {
1160  BasicBlock *ClonedBB = Result.Blocks[i];
1161  BasicBlock *OriginalBB = OriginalLoop.getBlocks()[i];
1162 
1163  assert(Result.Map[OriginalBB] == ClonedBB && "invariant!");
1164 
1165  for (Instruction &I : *ClonedBB)
1166  RemapInstruction(&I, Result.Map,
1168 
1169  // Exit blocks will now have one more predecessor and their PHI nodes need
1170  // to be edited to reflect that. No phi nodes need to be introduced because
1171  // the loop is in LCSSA.
1172 
1173  for (auto *SBB : successors(OriginalBB)) {
1174  if (OriginalLoop.contains(SBB))
1175  continue; // not an exit block
1176 
1177  for (Instruction &I : *SBB) {
1178  auto *PN = dyn_cast<PHINode>(&I);
1179  if (!PN)
1180  break;
1181 
1182  Value *OldIncoming = PN->getIncomingValueForBlock(OriginalBB);
1183  PN->addIncoming(GetClonedValue(OldIncoming), ClonedBB);
1184  }
1185  }
1186  }
1187 }
1188 
1189 LoopConstrainer::RewrittenRangeInfo LoopConstrainer::changeIterationSpaceEnd(
1190  const LoopStructure &LS, BasicBlock *Preheader, Value *ExitSubloopAt,
1191  BasicBlock *ContinuationBlock) const {
1192 
1193  // We start with a loop with a single latch:
1194  //
1195  // +--------------------+
1196  // | |
1197  // | preheader |
1198  // | |
1199  // +--------+-----------+
1200  // | ----------------\
1201  // | / |
1202  // +--------v----v------+ |
1203  // | | |
1204  // | header | |
1205  // | | |
1206  // +--------------------+ |
1207  // |
1208  // ..... |
1209  // |
1210  // +--------------------+ |
1211  // | | |
1212  // | latch >----------/
1213  // | |
1214  // +-------v------------+
1215  // |
1216  // |
1217  // | +--------------------+
1218  // | | |
1219  // +---> original exit |
1220  // | |
1221  // +--------------------+
1222  //
1223  // We change the control flow to look like
1224  //
1225  //
1226  // +--------------------+
1227  // | |
1228  // | preheader >-------------------------+
1229  // | | |
1230  // +--------v-----------+ |
1231  // | /-------------+ |
1232  // | / | |
1233  // +--------v--v--------+ | |
1234  // | | | |
1235  // | header | | +--------+ |
1236  // | | | | | |
1237  // +--------------------+ | | +-----v-----v-----------+
1238  // | | | |
1239  // | | | .pseudo.exit |
1240  // | | | |
1241  // | | +-----------v-----------+
1242  // | | |
1243  // ..... | | |
1244  // | | +--------v-------------+
1245  // +--------------------+ | | | |
1246  // | | | | | ContinuationBlock |
1247  // | latch >------+ | | |
1248  // | | | +----------------------+
1249  // +---------v----------+ |
1250  // | |
1251  // | |
1252  // | +---------------^-----+
1253  // | | |
1254  // +-----> .exit.selector |
1255  // | |
1256  // +----------v----------+
1257  // |
1258  // +--------------------+ |
1259  // | | |
1260  // | original exit <----+
1261  // | |
1262  // +--------------------+
1263  //
1264 
1265  RewrittenRangeInfo RRI;
1266 
1267  BasicBlock *BBInsertLocation = LS.Latch->getNextNode();
1268  RRI.ExitSelector = BasicBlock::Create(Ctx, Twine(LS.Tag) + ".exit.selector",
1269  &F, BBInsertLocation);
1270  RRI.PseudoExit = BasicBlock::Create(Ctx, Twine(LS.Tag) + ".pseudo.exit", &F,
1271  BBInsertLocation);
1272 
1273  BranchInst *PreheaderJump = cast<BranchInst>(Preheader->getTerminator());
1274  bool Increasing = LS.IndVarIncreasing;
1275  bool IsSignedPredicate = LS.IsSignedPredicate;
1276 
1277  IRBuilder<> B(PreheaderJump);
1278 
1279  // EnterLoopCond - is it okay to start executing this `LS'?
1280  Value *EnterLoopCond = nullptr;
1281  if (Increasing)
1282  EnterLoopCond = IsSignedPredicate
1283  ? B.CreateICmpSLT(LS.IndVarStart, ExitSubloopAt)
1284  : B.CreateICmpULT(LS.IndVarStart, ExitSubloopAt);
1285  else
1286  EnterLoopCond = IsSignedPredicate
1287  ? B.CreateICmpSGT(LS.IndVarStart, ExitSubloopAt)
1288  : B.CreateICmpUGT(LS.IndVarStart, ExitSubloopAt);
1289 
1290  B.CreateCondBr(EnterLoopCond, LS.Header, RRI.PseudoExit);
1291  PreheaderJump->eraseFromParent();
1292 
1293  LS.LatchBr->setSuccessor(LS.LatchBrExitIdx, RRI.ExitSelector);
1294  B.SetInsertPoint(LS.LatchBr);
1295  Value *TakeBackedgeLoopCond = nullptr;
1296  if (Increasing)
1297  TakeBackedgeLoopCond = IsSignedPredicate
1298  ? B.CreateICmpSLT(LS.IndVarBase, ExitSubloopAt)
1299  : B.CreateICmpULT(LS.IndVarBase, ExitSubloopAt);
1300  else
1301  TakeBackedgeLoopCond = IsSignedPredicate
1302  ? B.CreateICmpSGT(LS.IndVarBase, ExitSubloopAt)
1303  : B.CreateICmpUGT(LS.IndVarBase, ExitSubloopAt);
1304  Value *CondForBranch = LS.LatchBrExitIdx == 1
1305  ? TakeBackedgeLoopCond
1306  : B.CreateNot(TakeBackedgeLoopCond);
1307 
1308  LS.LatchBr->setCondition(CondForBranch);
1309 
1310  B.SetInsertPoint(RRI.ExitSelector);
1311 
1312  // IterationsLeft - are there any more iterations left, given the original
1313  // upper bound on the induction variable? If not, we branch to the "real"
1314  // exit.
1315  Value *IterationsLeft = nullptr;
1316  if (Increasing)
1317  IterationsLeft = IsSignedPredicate
1318  ? B.CreateICmpSLT(LS.IndVarBase, LS.LoopExitAt)
1319  : B.CreateICmpULT(LS.IndVarBase, LS.LoopExitAt);
1320  else
1321  IterationsLeft = IsSignedPredicate
1322  ? B.CreateICmpSGT(LS.IndVarBase, LS.LoopExitAt)
1323  : B.CreateICmpUGT(LS.IndVarBase, LS.LoopExitAt);
1324  B.CreateCondBr(IterationsLeft, RRI.PseudoExit, LS.LatchExit);
1325 
1326  BranchInst *BranchToContinuation =
1327  BranchInst::Create(ContinuationBlock, RRI.PseudoExit);
1328 
1329  // We emit PHI nodes into `RRI.PseudoExit' that compute the "latest" value of
1330  // each of the PHI nodes in the loop header. This feeds into the initial
1331  // value of the same PHI nodes if/when we continue execution.
1332  for (Instruction &I : *LS.Header) {
1333  auto *PN = dyn_cast<PHINode>(&I);
1334  if (!PN)
1335  break;
1336 
1337  PHINode *NewPHI = PHINode::Create(PN->getType(), 2, PN->getName() + ".copy",
1338  BranchToContinuation);
1339 
1340  NewPHI->addIncoming(PN->getIncomingValueForBlock(Preheader), Preheader);
1341  NewPHI->addIncoming(PN->getIncomingValueForBlock(LS.Latch),
1342  RRI.ExitSelector);
1343  RRI.PHIValuesAtPseudoExit.push_back(NewPHI);
1344  }
1345 
1346  RRI.IndVarEnd = PHINode::Create(LS.IndVarBase->getType(), 2, "indvar.end",
1347  BranchToContinuation);
1348  RRI.IndVarEnd->addIncoming(LS.IndVarStart, Preheader);
1349  RRI.IndVarEnd->addIncoming(LS.IndVarBase, RRI.ExitSelector);
1350 
1351  // The latch exit now has a branch from `RRI.ExitSelector' instead of
1352  // `LS.Latch'. The PHI nodes need to be updated to reflect that.
1353  for (Instruction &I : *LS.LatchExit) {
1354  if (PHINode *PN = dyn_cast<PHINode>(&I))
1355  replacePHIBlock(PN, LS.Latch, RRI.ExitSelector);
1356  else
1357  break;
1358  }
1359 
1360  return RRI;
1361 }
1362 
1363 void LoopConstrainer::rewriteIncomingValuesForPHIs(
1364  LoopStructure &LS, BasicBlock *ContinuationBlock,
1365  const LoopConstrainer::RewrittenRangeInfo &RRI) const {
1366 
1367  unsigned PHIIndex = 0;
1368  for (Instruction &I : *LS.Header) {
1369  auto *PN = dyn_cast<PHINode>(&I);
1370  if (!PN)
1371  break;
1372 
1373  for (unsigned i = 0, e = PN->getNumIncomingValues(); i < e; ++i)
1374  if (PN->getIncomingBlock(i) == ContinuationBlock)
1375  PN->setIncomingValue(i, RRI.PHIValuesAtPseudoExit[PHIIndex++]);
1376  }
1377 
1378  LS.IndVarStart = RRI.IndVarEnd;
1379 }
1380 
1381 BasicBlock *LoopConstrainer::createPreheader(const LoopStructure &LS,
1382  BasicBlock *OldPreheader,
1383  const char *Tag) const {
1384 
1385  BasicBlock *Preheader = BasicBlock::Create(Ctx, Tag, &F, LS.Header);
1386  BranchInst::Create(LS.Header, Preheader);
1387 
1388  for (Instruction &I : *LS.Header) {
1389  auto *PN = dyn_cast<PHINode>(&I);
1390  if (!PN)
1391  break;
1392 
1393  for (unsigned i = 0, e = PN->getNumIncomingValues(); i < e; ++i)
1394  replacePHIBlock(PN, OldPreheader, Preheader);
1395  }
1396 
1397  return Preheader;
1398 }
1399 
1400 void LoopConstrainer::addToParentLoopIfNeeded(ArrayRef<BasicBlock *> BBs) {
1401  Loop *ParentLoop = OriginalLoop.getParentLoop();
1402  if (!ParentLoop)
1403  return;
1404 
1405  for (BasicBlock *BB : BBs)
1406  ParentLoop->addBasicBlockToLoop(BB, LI);
1407 }
1408 
1409 Loop *LoopConstrainer::createClonedLoopStructure(Loop *Original, Loop *Parent,
1410  ValueToValueMapTy &VM) {
1411  Loop &New = *LI.AllocateLoop();
1412  if (Parent)
1413  Parent->addChildLoop(&New);
1414  else
1415  LI.addTopLevelLoop(&New);
1416  LPM.addLoop(New);
1417 
1418  // Add all of the blocks in Original to the new loop.
1419  for (auto *BB : Original->blocks())
1420  if (LI.getLoopFor(BB) == Original)
1421  New.addBasicBlockToLoop(cast<BasicBlock>(VM[BB]), LI);
1422 
1423  // Add all of the subloops to the new loop.
1424  for (Loop *SubLoop : *Original)
1425  createClonedLoopStructure(SubLoop, &New, VM);
1426 
1427  return &New;
1428 }
1429 
1430 bool LoopConstrainer::run() {
1431  BasicBlock *Preheader = nullptr;
1432  LatchTakenCount = SE.getExitCount(&OriginalLoop, MainLoopStructure.Latch);
1433  Preheader = OriginalLoop.getLoopPreheader();
1434  assert(!isa<SCEVCouldNotCompute>(LatchTakenCount) && Preheader != nullptr &&
1435  "preconditions!");
1436 
1437  OriginalPreheader = Preheader;
1438  MainLoopPreheader = Preheader;
1439 
1440  bool IsSignedPredicate = MainLoopStructure.IsSignedPredicate;
1441  Optional<SubRanges> MaybeSR = calculateSubRanges(IsSignedPredicate);
1442  if (!MaybeSR.hasValue()) {
1443  DEBUG(dbgs() << "irce: could not compute subranges\n");
1444  return false;
1445  }
1446 
1447  SubRanges SR = MaybeSR.getValue();
1448  bool Increasing = MainLoopStructure.IndVarIncreasing;
1449  IntegerType *IVTy =
1450  cast<IntegerType>(MainLoopStructure.IndVarBase->getType());
1451 
1452  SCEVExpander Expander(SE, F.getParent()->getDataLayout(), "irce");
1453  Instruction *InsertPt = OriginalPreheader->getTerminator();
1454 
1455  // It would have been better to make `PreLoop' and `PostLoop'
1456  // `Optional<ClonedLoop>'s, but `ValueToValueMapTy' does not have a copy
1457  // constructor.
1458  ClonedLoop PreLoop, PostLoop;
1459  bool NeedsPreLoop =
1460  Increasing ? SR.LowLimit.hasValue() : SR.HighLimit.hasValue();
1461  bool NeedsPostLoop =
1462  Increasing ? SR.HighLimit.hasValue() : SR.LowLimit.hasValue();
1463 
1464  Value *ExitPreLoopAt = nullptr;
1465  Value *ExitMainLoopAt = nullptr;
1466  const SCEVConstant *MinusOneS =
1467  cast<SCEVConstant>(SE.getConstant(IVTy, -1, true /* isSigned */));
1468 
1469  if (NeedsPreLoop) {
1470  const SCEV *ExitPreLoopAtSCEV = nullptr;
1471 
1472  if (Increasing)
1473  ExitPreLoopAtSCEV = *SR.LowLimit;
1474  else {
1475  if (CanBeMin(SE, *SR.HighLimit, IsSignedPredicate)) {
1476  DEBUG(dbgs() << "irce: could not prove no-overflow when computing "
1477  << "preloop exit limit. HighLimit = " << *(*SR.HighLimit)
1478  << "\n");
1479  return false;
1480  }
1481  ExitPreLoopAtSCEV = SE.getAddExpr(*SR.HighLimit, MinusOneS);
1482  }
1483 
1484  ExitPreLoopAt = Expander.expandCodeFor(ExitPreLoopAtSCEV, IVTy, InsertPt);
1485  ExitPreLoopAt->setName("exit.preloop.at");
1486  }
1487 
1488  if (NeedsPostLoop) {
1489  const SCEV *ExitMainLoopAtSCEV = nullptr;
1490 
1491  if (Increasing)
1492  ExitMainLoopAtSCEV = *SR.HighLimit;
1493  else {
1494  if (CanBeMin(SE, *SR.LowLimit, IsSignedPredicate)) {
1495  DEBUG(dbgs() << "irce: could not prove no-overflow when computing "
1496  << "mainloop exit limit. LowLimit = " << *(*SR.LowLimit)
1497  << "\n");
1498  return false;
1499  }
1500  ExitMainLoopAtSCEV = SE.getAddExpr(*SR.LowLimit, MinusOneS);
1501  }
1502 
1503  ExitMainLoopAt = Expander.expandCodeFor(ExitMainLoopAtSCEV, IVTy, InsertPt);
1504  ExitMainLoopAt->setName("exit.mainloop.at");
1505  }
1506 
1507  // We clone these ahead of time so that we don't have to deal with changing
1508  // and temporarily invalid IR as we transform the loops.
1509  if (NeedsPreLoop)
1510  cloneLoop(PreLoop, "preloop");
1511  if (NeedsPostLoop)
1512  cloneLoop(PostLoop, "postloop");
1513 
1514  RewrittenRangeInfo PreLoopRRI;
1515 
1516  if (NeedsPreLoop) {
1517  Preheader->getTerminator()->replaceUsesOfWith(MainLoopStructure.Header,
1518  PreLoop.Structure.Header);
1519 
1520  MainLoopPreheader =
1521  createPreheader(MainLoopStructure, Preheader, "mainloop");
1522  PreLoopRRI = changeIterationSpaceEnd(PreLoop.Structure, Preheader,
1523  ExitPreLoopAt, MainLoopPreheader);
1524  rewriteIncomingValuesForPHIs(MainLoopStructure, MainLoopPreheader,
1525  PreLoopRRI);
1526  }
1527 
1528  BasicBlock *PostLoopPreheader = nullptr;
1529  RewrittenRangeInfo PostLoopRRI;
1530 
1531  if (NeedsPostLoop) {
1532  PostLoopPreheader =
1533  createPreheader(PostLoop.Structure, Preheader, "postloop");
1534  PostLoopRRI = changeIterationSpaceEnd(MainLoopStructure, MainLoopPreheader,
1535  ExitMainLoopAt, PostLoopPreheader);
1536  rewriteIncomingValuesForPHIs(PostLoop.Structure, PostLoopPreheader,
1537  PostLoopRRI);
1538  }
1539 
1540  BasicBlock *NewMainLoopPreheader =
1541  MainLoopPreheader != Preheader ? MainLoopPreheader : nullptr;
1542  BasicBlock *NewBlocks[] = {PostLoopPreheader, PreLoopRRI.PseudoExit,
1543  PreLoopRRI.ExitSelector, PostLoopRRI.PseudoExit,
1544  PostLoopRRI.ExitSelector, NewMainLoopPreheader};
1545 
1546  // Some of the above may be nullptr, filter them out before passing to
1547  // addToParentLoopIfNeeded.
1548  auto NewBlocksEnd =
1549  std::remove(std::begin(NewBlocks), std::end(NewBlocks), nullptr);
1550 
1551  addToParentLoopIfNeeded(makeArrayRef(std::begin(NewBlocks), NewBlocksEnd));
1552 
1553  DT.recalculate(F);
1554 
1555  // We need to first add all the pre and post loop blocks into the loop
1556  // structures (as part of createClonedLoopStructure), and then update the
1557  // LCSSA form and LoopSimplifyForm. This is necessary for correctly updating
1558  // LI when LoopSimplifyForm is generated.
1559  Loop *PreL = nullptr, *PostL = nullptr;
1560  if (!PreLoop.Blocks.empty()) {
1561  PreL = createClonedLoopStructure(
1562  &OriginalLoop, OriginalLoop.getParentLoop(), PreLoop.Map);
1563  }
1564 
1565  if (!PostLoop.Blocks.empty()) {
1566  PostL = createClonedLoopStructure(
1567  &OriginalLoop, OriginalLoop.getParentLoop(), PostLoop.Map);
1568  }
1569 
1570  // This function canonicalizes the loop into Loop-Simplify and LCSSA forms.
1571  auto CanonicalizeLoop = [&] (Loop *L, bool IsOriginalLoop) {
1572  formLCSSARecursively(*L, DT, &LI, &SE);
1573  simplifyLoop(L, &DT, &LI, &SE, nullptr, true);
1574  // Pre/post loops are slow paths, we do not need to perform any loop
1575  // optimizations on them.
1576  if (!IsOriginalLoop)
1578  };
1579  if (PreL)
1580  CanonicalizeLoop(PreL, false);
1581  if (PostL)
1582  CanonicalizeLoop(PostL, false);
1583  CanonicalizeLoop(&OriginalLoop, true);
1584 
1585  return true;
1586 }
1587 
1588 /// Computes and returns a range of values for the induction variable (IndVar)
1589 /// in which the range check can be safely elided. If it cannot compute such a
1590 /// range, returns None.
1592 InductiveRangeCheck::computeSafeIterationSpace(
1593  ScalarEvolution &SE, const SCEVAddRecExpr *IndVar) const {
1594  // IndVar is of the form "A + B * I" (where "I" is the canonical induction
1595  // variable, that may or may not exist as a real llvm::Value in the loop) and
1596  // this inductive range check is a range check on the "C + D * I" ("C" is
1597  // getOffset() and "D" is getScale()). We rewrite the value being range
1598  // checked to "M + N * IndVar" where "N" = "D * B^(-1)" and "M" = "C - NA".
1599  //
1600  // The actual inequalities we solve are of the form
1601  //
1602  // 0 <= M + 1 * IndVar < L given L >= 0 (i.e. N == 1)
1603  //
1604  // The inequality is satisfied by -M <= IndVar < (L - M) [^1]. All additions
1605  // and subtractions are twos-complement wrapping and comparisons are signed.
1606  //
1607  // Proof:
1608  //
1609  // If there exists IndVar such that -M <= IndVar < (L - M) then it follows
1610  // that -M <= (-M + L) [== Eq. 1]. Since L >= 0, if (-M + L) sign-overflows
1611  // then (-M + L) < (-M). Hence by [Eq. 1], (-M + L) could not have
1612  // overflown.
1613  //
1614  // This means IndVar = t + (-M) for t in [0, L). Hence (IndVar + M) = t.
1615  // Hence 0 <= (IndVar + M) < L
1616 
1617  // [^1]: Note that the solution does _not_ apply if L < 0; consider values M =
1618  // 127, IndVar = 126 and L = -2 in an i8 world.
1619 
1620  if (!IndVar->isAffine())
1621  return None;
1622 
1623  const SCEV *A = IndVar->getStart();
1624  const SCEVConstant *B = dyn_cast<SCEVConstant>(IndVar->getStepRecurrence(SE));
1625  if (!B)
1626  return None;
1627  assert(!B->isZero() && "Recurrence with zero step?");
1628 
1629  const SCEV *C = getOffset();
1630  const SCEVConstant *D = dyn_cast<SCEVConstant>(getScale());
1631  if (D != B)
1632  return None;
1633 
1634  assert(!D->getValue()->isZero() && "Recurrence with zero step?");
1635 
1636  const SCEV *M = SE.getMinusSCEV(C, A);
1637  const SCEV *Begin = SE.getNegativeSCEV(M);
1638  const SCEV *UpperLimit = nullptr;
1639 
1640  // We strengthen "0 <= I" to "0 <= I < INT_SMAX" and "I < L" to "0 <= I < L".
1641  // We can potentially do much better here.
1642  if (Value *V = getLength()) {
1643  UpperLimit = SE.getSCEV(V);
1644  } else {
1645  assert(Kind == InductiveRangeCheck::RANGE_CHECK_LOWER && "invariant!");
1646  unsigned BitWidth = cast<IntegerType>(IndVar->getType())->getBitWidth();
1647  UpperLimit = SE.getConstant(APInt::getSignedMaxValue(BitWidth));
1648  }
1649 
1650  const SCEV *End = SE.getMinusSCEV(UpperLimit, M);
1651  return InductiveRangeCheck::Range(Begin, End);
1652 }
1653 
1657  const InductiveRangeCheck::Range &R2) {
1658  if (R2.isEmpty())
1659  return None;
1660  if (!R1.hasValue())
1661  return R2;
1662  auto &R1Value = R1.getValue();
1663  // We never return empty ranges from this function, and R1 is supposed to be
1664  // a result of intersection. Thus, R1 is never empty.
1665  assert(!R1Value.isEmpty() && "We should never have empty R1!");
1666 
1667  // TODO: we could widen the smaller range and have this work; but for now we
1668  // bail out to keep things simple.
1669  if (R1Value.getType() != R2.getType())
1670  return None;
1671 
1672  const SCEV *NewBegin = SE.getSMaxExpr(R1Value.getBegin(), R2.getBegin());
1673  const SCEV *NewEnd = SE.getSMinExpr(R1Value.getEnd(), R2.getEnd());
1674 
1675  // If the resulting range is empty, just return None.
1676  auto Ret = InductiveRangeCheck::Range(NewBegin, NewEnd);
1677  if (Ret.isEmpty())
1678  return None;
1679  return Ret;
1680 }
1681 
1682 bool InductiveRangeCheckElimination::runOnLoop(Loop *L, LPPassManager &LPM) {
1683  if (skipLoop(L))
1684  return false;
1685 
1686  if (L->getBlocks().size() >= LoopSizeCutoff) {
1687  DEBUG(dbgs() << "irce: giving up constraining loop, too large\n";);
1688  return false;
1689  }
1690 
1691  BasicBlock *Preheader = L->getLoopPreheader();
1692  if (!Preheader) {
1693  DEBUG(dbgs() << "irce: loop has no preheader, leaving\n");
1694  return false;
1695  }
1696 
1697  LLVMContext &Context = Preheader->getContext();
1699  ScalarEvolution &SE = getAnalysis<ScalarEvolutionWrapperPass>().getSE();
1700  BranchProbabilityInfo &BPI =
1701  getAnalysis<BranchProbabilityInfoWrapperPass>().getBPI();
1702 
1703  for (auto BBI : L->getBlocks())
1704  if (BranchInst *TBI = dyn_cast<BranchInst>(BBI->getTerminator()))
1705  InductiveRangeCheck::extractRangeChecksFromBranch(TBI, L, SE, BPI,
1706  RangeChecks);
1707 
1708  if (RangeChecks.empty())
1709  return false;
1710 
1711  auto PrintRecognizedRangeChecks = [&](raw_ostream &OS) {
1712  OS << "irce: looking at loop "; L->print(OS);
1713  OS << "irce: loop has " << RangeChecks.size()
1714  << " inductive range checks: \n";
1715  for (InductiveRangeCheck &IRC : RangeChecks)
1716  IRC.print(OS);
1717  };
1718 
1719  DEBUG(PrintRecognizedRangeChecks(dbgs()));
1720 
1721  if (PrintRangeChecks)
1722  PrintRecognizedRangeChecks(errs());
1723 
1724  const char *FailureReason = nullptr;
1725  Optional<LoopStructure> MaybeLoopStructure =
1726  LoopStructure::parseLoopStructure(SE, BPI, *L, FailureReason);
1727  if (!MaybeLoopStructure.hasValue()) {
1728  DEBUG(dbgs() << "irce: could not parse loop structure: " << FailureReason
1729  << "\n";);
1730  return false;
1731  }
1732  LoopStructure LS = MaybeLoopStructure.getValue();
1733  const SCEVAddRecExpr *IndVar =
1734  cast<SCEVAddRecExpr>(SE.getMinusSCEV(SE.getSCEV(LS.IndVarBase), SE.getSCEV(LS.IndVarStep)));
1735 
1737  Instruction *ExprInsertPt = Preheader->getTerminator();
1738 
1739  SmallVector<InductiveRangeCheck, 4> RangeChecksToEliminate;
1740 
1741  IRBuilder<> B(ExprInsertPt);
1742  for (InductiveRangeCheck &IRC : RangeChecks) {
1743  auto Result = IRC.computeSafeIterationSpace(SE, IndVar);
1744  if (Result.hasValue()) {
1745  auto MaybeSafeIterRange =
1746  IntersectRange(SE, SafeIterRange, Result.getValue());
1747  if (MaybeSafeIterRange.hasValue()) {
1748  assert(!MaybeSafeIterRange.getValue().isEmpty() &&
1749  "We should never return empty ranges!");
1750  RangeChecksToEliminate.push_back(IRC);
1751  SafeIterRange = MaybeSafeIterRange.getValue();
1752  }
1753  }
1754  }
1755 
1756  if (!SafeIterRange.hasValue())
1757  return false;
1758 
1759  auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
1760  LoopConstrainer LC(*L, getAnalysis<LoopInfoWrapperPass>().getLoopInfo(), LPM,
1761  LS, SE, DT, SafeIterRange.getValue());
1762  bool Changed = LC.run();
1763 
1764  if (Changed) {
1765  auto PrintConstrainedLoopInfo = [L]() {
1766  dbgs() << "irce: in function ";
1767  dbgs() << L->getHeader()->getParent()->getName() << ": ";
1768  dbgs() << "constrained ";
1769  L->print(dbgs());
1770  };
1771 
1772  DEBUG(PrintConstrainedLoopInfo());
1773 
1774  if (PrintChangedLoops)
1775  PrintConstrainedLoopInfo();
1776 
1777  // Optimize away the now-redundant range checks.
1778 
1779  for (InductiveRangeCheck &IRC : RangeChecksToEliminate) {
1780  ConstantInt *FoldedRangeCheck = IRC.getPassingDirection()
1781  ? ConstantInt::getTrue(Context)
1782  : ConstantInt::getFalse(Context);
1783  IRC.getCheckUse()->set(FoldedRangeCheck);
1784  }
1785  }
1786 
1787  return Changed;
1788 }
1789 
1791  return new InductiveRangeCheckElimination;
1792 }
static bool SumCanReachMin(ScalarEvolution &SE, const SCEV *S1, const SCEV *S2, bool Signed)
static unsigned getBitWidth(Type *Ty, const DataLayout &DL)
Returns the bitwidth of the given scalar or pointer type.
Pass interface - Implemented by all &#39;passes&#39;.
Definition: Pass.h:81
BinaryOp_match< LHS, RHS, Instruction::And > m_And(const LHS &L, const RHS &R)
Definition: PatternMatch.h:574
uint64_t CallInst * C
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks &#39;this&#39; from the containing basic block and deletes it.
Definition: Instruction.cpp:69
A parsed version of the target data layout string in and methods for querying it. ...
Definition: DataLayout.h:109
const_iterator end(StringRef path)
Get end iterator over path.
Definition: Path.cpp:243
static ConstantInt * getFalse(LLVMContext &Context)
Definition: Constants.cpp:523
BranchInst * CreateCondBr(Value *Cond, BasicBlock *True, BasicBlock *False, MDNode *BranchWeights=nullptr, MDNode *Unpredictable=nullptr)
Create a conditional &#39;br Cond, TrueDest, FalseDest&#39; instruction.
Definition: IRBuilder.h:775
class_match< Value > m_Value()
Match an arbitrary value and ignore it.
Definition: PatternMatch.h:72
raw_ostream & errs()
This returns a reference to a raw_ostream for standard error.
static IntegerType * getInt1Ty(LLVMContext &C)
Definition: Type.cpp:173
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
BlockT * getLoopLatch() const
If there is a single latch block for this loop, return it.
Definition: LoopInfoImpl.h:157
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
LLVMContext & Context
const_iterator begin(StringRef path, Style style=Style::native)
Get begin iterator over path.
Definition: Path.cpp:234
const SCEV * getConstant(ConstantInt *V)
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds...
Definition: Compiler.h:449
Value * CreateICmpULT(Value *LHS, Value *RHS, const Twine &Name="")
Definition: IRBuilder.h:1558
LLVM_ATTRIBUTE_ALWAYS_INLINE size_type size() const
Definition: SmallVector.h:136
void replaceOperandWith(unsigned I, Metadata *New)
Replace a specific operand.
Definition: Metadata.cpp:851
static cl::opt< bool > AllowUnsignedLatchCondition("irce-allow-unsigned-latch", cl::Hidden, cl::init(false))
static MDString * get(LLVMContext &Context, StringRef Str)
Definition: Metadata.cpp:446
std::error_code remove(const Twine &path, bool IgnoreNonExisting=true)
Remove path.
The main scalar evolution driver.
Value * CreateICmpSLT(Value *LHS, Value *RHS, const Twine &Name="")
Definition: IRBuilder.h:1570
bool isZero() const
Return true if the expression is a constant zero.
BlockT * getLoopPreheader() const
If there is a preheader for this loop, return it.
Definition: LoopInfoImpl.h:106
bool isKnownNonNegative(const SCEV *S)
Test if the given expression is known to be non-negative.
unsigned less or equal
Definition: InstrTypes.h:879
unsigned less than
Definition: InstrTypes.h:878
const Use & getOperandUse(unsigned i) const
Definition: User.h:167
BasicBlock * getSuccessor(unsigned i) const
static bool CanBeMax(ScalarEvolution &SE, const SCEV *S, bool Signed)
Metadata node.
Definition: Metadata.h:862
F(f)
#define R2(n)
Value * getCondition() const
static cl::opt< bool > PrintRangeChecks("irce-print-range-checks", cl::Hidden, cl::init(false))
LLVMContext & getContext() const
Get the context in which this basic block lives.
Definition: BasicBlock.cpp:33
static APInt getSignedMaxValue(unsigned numBits)
Gets maximum signed value of APInt for a specific bit width.
Definition: APInt.h:528
Value * get() const
Definition: Use.h:108
LLVMContext & getContext() const
Return the LLVMContext in which this type was uniqued.
Definition: Type.h:130
void print(raw_ostream &OS, unsigned Depth=0, bool Verbose=false) const
Print loop with all the BBs inside it.
Definition: LoopInfoImpl.h:325
Value * CreateNot(Value *V, const Twine &Name="")
Definition: IRBuilder.h:1142
bool isKnownNonPositive(const SCEV *S)
Test if the given expression is known to be non-positive.
bool formLCSSARecursively(Loop &L, DominatorTree &DT, LoopInfo *LI, ScalarEvolution *SE)
Put a loop nest into LCSSA form.
Definition: LCSSA.cpp:332
The SCEV is loop-invariant.
bool match(Val *V, const Pattern &P)
Definition: PatternMatch.h:49
AnalysisUsage & addRequired()
const Module * getModule() const
Return the module owning the function this basic block belongs to, or nullptr it the function does no...
Definition: BasicBlock.cpp:116
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:51
const DataLayout & getDataLayout() const
Get the data layout for the module&#39;s target platform.
Definition: Module.cpp:361
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
Definition: Twine.h:81
bool simplifyLoop(Loop *L, DominatorTree *DT, LoopInfo *LI, ScalarEvolution *SE, AssumptionCache *AC, bool PreserveLCSSA)
Simplify each loop in a loop nest recursively.
ArrayRef< T > makeArrayRef(const T &OneElt)
Construct an ArrayRef from a single element.
Definition: ArrayRef.h:451
A Use represents the edge between a Value definition and its users.
Definition: Use.h:56
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:42
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
Definition: IRBuilder.h:664
void setName(const Twine &Name)
Change the name of the value.
Definition: Value.cpp:284
static bool SumCanReachMax(ScalarEvolution &SE, const SCEV *S1, const SCEV *S2, bool Signed)
Value * CreateICmpSGT(Value *LHS, Value *RHS, const Twine &Name="")
Definition: IRBuilder.h:1564
static cl::opt< int > MaxExitProbReciprocal("irce-max-exit-prob-reciprocal", cl::Hidden, cl::init(10))
bool contains(const APInt &Val) const
Return true if the specified value is in the set.
BlockT * getHeader() const
Definition: LoopInfo.h:100
ConstantInt * getValue() const
bool isOne() const
This is just a convenience method to make client code smaller for a common case.
Definition: Constants.h:201
bool isKnownPredicate(ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS)
Test if the given expression is known to satisfy the condition described by Pred, LHS...
static void DisableAllLoopOptsOnLoop(Loop &L)
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:245
ConstantRange getSignedRange(const SCEV *S)
Determine the signed range for a particular SCEV.
void addBasicBlockToLoop(BlockT *NewBB, LoopInfoBase< BlockT, LoopT > &LI)
This method is used by other analyses to update loop information.
Definition: LoopInfoImpl.h:183
This node represents a polynomial recurrence on the trip count of the specified loop.
static const char * ClonedLoopTag
Value * CreateICmpUGT(Value *LHS, Value *RHS, const Twine &Name="")
Definition: IRBuilder.h:1552
void setLoopID(MDNode *LoopID) const
Set the llvm.loop loop id metadata for this loop.
Definition: LoopInfo.cpp:249
const T & getValue() const LLVM_LVALUE_FUNCTION
Definition: Optional.h:129
Inductive range check elimination
INITIALIZE_PASS_BEGIN(InductiveRangeCheckElimination, "irce", "Inductive range check elimination", false, false) INITIALIZE_PASS_END(InductiveRangeCheckElimination
MDNode * getMetadata(unsigned KindID) const
Get the metadata of given kind attached to this Instruction.
Definition: Instruction.h:194
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory)...
Definition: APInt.h:33
bool isMinusOne() const
This function will return true iff every bit in this constant is set to true.
Definition: Constants.h:209
static Error getOffset(const SymbolRef &Sym, SectionRef Sec, uint64_t &Result)
const SCEV * getStepRecurrence(ScalarEvolution &SE) const
Constructs and returns the recurrence indicating how much this expression steps by.
unsigned getBitWidth() const
Get the number of bits in this IntegerType.
Definition: DerivedTypes.h:66
static ConstantAsMetadata * get(Constant *C)
Definition: Metadata.h:408
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree...
Definition: Dominators.h:140
void SetInsertPoint(BasicBlock *TheBB)
This specifies that created instructions should be appended to the end of the specified block...
Definition: IRBuilder.h:128
static Optional< InductiveRangeCheck::Range > IntersectRange(ScalarEvolution &SE, const Optional< InductiveRangeCheck::Range > &R1, const InductiveRangeCheck::Range &R2)
Legacy analysis pass which computes BranchProbabilityInfo.
Value * getOperand(unsigned i) const
Definition: User.h:154
If this flag is set, the remapper knows that only local values within a function (such as an instruct...
Definition: ValueMapper.h:65
void replaceUsesOfWith(Value *From, Value *To)
Replace uses of one Value with another.
Definition: User.cpp:22
bool isLoopEntryGuardedByCond(const Loop *L, ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS)
Test whether entry to the loop is protected by a conditional between LHS and RHS. ...
static MDTuple * get(LLVMContext &Context, ArrayRef< Metadata *> MDs)
Definition: Metadata.h:1164
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:406
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
void dump(const SparseBitVector< ElementSize > &LHS, raw_ostream &out)
const SCEV * getOne(Type *Ty)
Return a SCEV for the constant 1 of a specific type.
LLVM Basic Block Representation.
Definition: BasicBlock.h:59
bool isLoopExiting(const BlockT *BB) const
True if terminator in the block can branch to another block that is outside of the current loop...
Definition: LoopInfo.h:184
The instances of the Type class are immutable: once they are created, they are never changed...
Definition: Type.h:46
This is an important class for using LLVM in a threaded context.
Definition: LLVMContext.h:69
LoopDisposition getLoopDisposition(const SCEV *S, const Loop *L)
Return the "disposition" of the given SCEV with respect to the given loop.
Conditional or Unconditional Branch instruction.
void initializeInductiveRangeCheckEliminationPass(PassRegistry &)
LLVM_ATTRIBUTE_ALWAYS_INLINE iterator begin()
Definition: SmallVector.h:116
Value * getIncomingValueForBlock(const BasicBlock *BB) const
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:371
const SCEV * getAddExpr(SmallVectorImpl< const SCEV *> &Ops, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
Get a canonical add expression, or something simpler if possible.
const std::vector< BlockT * > & getBlocks() const
Get a list of the basic blocks which make up this loop.
Definition: LoopInfo.h:149
const SCEV * getSMaxExpr(const SCEV *LHS, const SCEV *RHS)
Represent the analysis usage information of a pass.
This instruction compares its operands according to the predicate given to the constructor.
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Definition: InstrTypes.h:853
void print(raw_ostream &O, bool IsForDebug=false) const
Implement operator<< on Value.
Definition: AsmWriter.cpp:3482
Value * expandCodeFor(const SCEV *SH, Type *Ty, Instruction *I)
Insert code to directly compute the specified SCEV expression into the program.
static const unsigned End
bool isAffine() const
Return true if this represents an expression A + B*x where A and B are loop invariant values...
static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)
Creates a new BasicBlock.
Definition: BasicBlock.h:101
Class to represent integer types.
Definition: DerivedTypes.h:40
const SCEV * getMinusSCEV(const SCEV *LHS, const SCEV *RHS, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
Return LHS-RHS. Minus is represented in SCEV as A+B*-1.
static wasm::ValType getType(const TargetRegisterClass *RC)
INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false) RegBankSelect
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
signed greater than
Definition: InstrTypes.h:880
BranchProbability getEdgeProbability(const BasicBlock *Src, unsigned IndexInSuccessors) const
Get an edge&#39;s probability, relative to other out-edges of the Src.
const SCEV * getSMinExpr(const SCEV *LHS, const SCEV *RHS)
void print(raw_ostream &OS) const
Print out the internal representation of this scalar to the specified stream.
static IntegerType * get(LLVMContext &C, unsigned NumBits)
This static method is the primary way of constructing an IntegerType.
Definition: Type.cpp:240
bool contains(const LoopT *L) const
Return true if the specified loop is contained within in this loop.
Definition: LoopInfo.h:110
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements...
Definition: SmallPtrSet.h:418
static cl::opt< bool > SkipProfitabilityChecks("irce-skip-profitability-checks", cl::Hidden, cl::init(false))
This is the shared class of boolean and integer constants.
Definition: Constants.h:84
Type * getType() const
Return the LLVM type of this SCEV expression.
void setIncomingBlock(unsigned i, BasicBlock *BB)
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:864
signed less than
Definition: InstrTypes.h:882
static APInt getMinValue(unsigned numBits)
Gets minimum unsigned value of APInt for a specific bit width.
Definition: APInt.h:535
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
static Constant * get(Type *Ty, uint64_t V, bool isSigned=false)
If Ty is a vector type, return a Constant with a splat of the given value.
Definition: Constants.cpp:560
static BranchInst * Create(BasicBlock *IfTrue, Instruction *InsertBefore=nullptr)
static PHINode * Create(Type *Ty, unsigned NumReservedValues, const Twine &NameStr="", Instruction *InsertBefore=nullptr)
Constructors - NumReservedValues is a hint for the number of incoming edges that this phi node will h...
const SCEV * getUMaxExpr(const SCEV *LHS, const SCEV *RHS)
unsigned getNumIncomingValues() const
Return the number of incoming edges.
static ConstantInt * getTrue(LLVMContext &Context)
Definition: Constants.cpp:516
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:923
signed less or equal
Definition: InstrTypes.h:883
Class for arbitrary precision integers.
Definition: APInt.h:69
BasicBlock * CloneBasicBlock(const BasicBlock *BB, ValueToValueMapTy &VMap, const Twine &NameSuffix="", Function *F=nullptr, ClonedCodeInfo *CodeInfo=nullptr, DebugInfoFinder *DIFinder=nullptr)
CloneBasicBlock - Return a copy of the specified basic block, but without embedding the block into a ...
static bool CanBeMin(ScalarEvolution &SE, const SCEV *S, bool Signed)
void RemapInstruction(Instruction *I, ValueToValueMapTy &VM, RemapFlags Flags=RF_None, ValueMapTypeRemapper *TypeMapper=nullptr, ValueMaterializer *Materializer=nullptr)
Convert the instruction operands from referencing the current values into those specified by VM...
Definition: ValueMapper.h:243
This class uses information about analyze scalars to rewrite expressions in canonical form...
iterator insert(iterator I, T &&Elt)
Definition: SmallVector.h:482
static APInt getMaxValue(unsigned numBits)
Gets maximum unsigned value of APInt for specific bit width.
Definition: APInt.h:523
If this flag is set, the remapper ignores missing function-local entries (Argument, Instruction, BasicBlock) that are not in the value map.
Definition: ValueMapper.h:83
LoopT * getParentLoop() const
Definition: LoopInfo.h:101
Predicate getPredicate() const
Return the predicate for this instruction.
Definition: InstrTypes.h:927
bool hasValue() const
Definition: Optional.h:133
bool isLoopSimplifyForm() const
Return true if the Loop is in the form that the LoopSimplify form transforms loops to...
Definition: LoopInfo.cpp:191
LLVM_ATTRIBUTE_ALWAYS_INLINE iterator end()
Definition: SmallVector.h:120
Analysis providing branch probability information.
This class represents an analyzed expression in the program.
void addChildLoop(LoopT *NewChild)
Add the specified loop to be a child of this loop.
Definition: LoopInfo.h:298
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:61
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:420
StringRef getName() const
Return a constant reference to the value&#39;s name.
Definition: Value.cpp:218
BasicBlock * getIncomingBlock(unsigned i) const
Return incoming basic block number i.
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:108
#define I(x, y, z)
Definition: MD5.cpp:58
bool isZero() const
This is just a convenience method to make client code smaller for a common code.
Definition: Constants.h:193
void getLoopAnalysisUsage(AnalysisUsage &AU)
Helper to consistently add the set of standard passes to a loop pass&#39;s AnalysisUsage.
Definition: LoopUtils.cpp:1023
LLVM_NODISCARD std::enable_if<!is_simple_type< Y >::value, typename cast_retty< X, const Y >::ret_type >::type dyn_cast(const Y &Val)
Definition: Casting.h:323
static cl::opt< unsigned > LoopSizeCutoff("irce-loop-size-cutoff", cl::Hidden, cl::init(64))
bool isUnconditional() const
ConstantRange getUnsignedRange(const SCEV *S)
Determine the unsigned range for a particular SCEV.
const unsigned Kind
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
static APInt getSignedMinValue(unsigned numBits)
Gets minimum signed value of APInt for a specific bit width.
Definition: APInt.h:538
static cl::opt< bool > PrintChangedLoops("irce-print-changed-loops", cl::Hidden, cl::init(false))
const SCEV * getUMinExpr(const SCEV *LHS, const SCEV *RHS)
const SCEV * getNegativeSCEV(const SCEV *V, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap)
Return the SCEV object corresponding to -V.
LLVM Value Representation.
Definition: Value.h:73
succ_range successors(BasicBlock *BB)
Definition: CFG.h:143
const SCEV * getSCEV(Value *V)
Return a SCEV expression for the full generality of the specified expression.
#define LLVM_FALLTHROUGH
LLVM_FALLTHROUGH - Mark fallthrough cases in switch statements.
Definition: Compiler.h:235
This class implements an extremely fast bulk output stream that can only output to a stream...
Definition: raw_ostream.h:44
#define DEBUG(X)
Definition: Debug.h:118
unsigned greater than
Definition: InstrTypes.h:876
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:49
Predicate getSwappedPredicate() const
For example, EQ->EQ, SLE->SGE, ULT->UGT, OEQ->OEQ, ULE->UGE, OLT->OGT, etc.
Definition: InstrTypes.h:967
const SCEV * getExitCount(const Loop *L, BasicBlock *ExitingBlock)
Get the expression for the number of loop iterations for which this loop is guaranteed not to exit vi...
const TerminatorInst * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
Definition: BasicBlock.cpp:120
void setIncomingValue(unsigned i, Value *V)
iterator_range< block_iterator > blocks() const
Definition: LoopInfo.h:156
Root of the metadata hierarchy.
Definition: Metadata.h:58
Pass * createInductiveRangeCheckEliminationPass()
signed greater or equal
Definition: InstrTypes.h:881
const SCEV * getSignExtendExpr(const SCEV *Op, Type *Ty, unsigned Depth=0)
const BasicBlock * getParent() const
Definition: Instruction.h:66
This class represents a constant integer value.