LLVM  8.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 //
10 // The InductiveRangeCheckElimination pass splits a loop's iteration space into
11 // three disjoint ranges. It does that in a way such that the loop running in
12 // the middle loop provably does not need range checks. As an example, it will
13 // convert
14 //
15 // len = < known positive >
16 // for (i = 0; i < n; i++) {
17 // if (0 <= i && i < len) {
18 // do_something();
19 // } else {
20 // throw_out_of_bounds();
21 // }
22 // }
23 //
24 // to
25 //
26 // len = < known positive >
27 // limit = smin(n, len)
28 // // no first segment
29 // for (i = 0; i < limit; i++) {
30 // if (0 <= i && i < len) { // this check is fully redundant
31 // do_something();
32 // } else {
33 // throw_out_of_bounds();
34 // }
35 // }
36 // for (i = limit; i < n; i++) {
37 // if (0 <= i && i < len) {
38 // do_something();
39 // } else {
40 // throw_out_of_bounds();
41 // }
42 // }
43 //
44 //===----------------------------------------------------------------------===//
45 
47 #include "llvm/ADT/APInt.h"
48 #include "llvm/ADT/ArrayRef.h"
49 #include "llvm/ADT/None.h"
50 #include "llvm/ADT/Optional.h"
51 #include "llvm/ADT/SmallPtrSet.h"
52 #include "llvm/ADT/SmallVector.h"
53 #include "llvm/ADT/StringRef.h"
54 #include "llvm/ADT/Twine.h"
57 #include "llvm/Analysis/LoopInfo.h"
58 #include "llvm/Analysis/LoopPass.h"
62 #include "llvm/IR/BasicBlock.h"
63 #include "llvm/IR/CFG.h"
64 #include "llvm/IR/Constants.h"
65 #include "llvm/IR/DerivedTypes.h"
66 #include "llvm/IR/Dominators.h"
67 #include "llvm/IR/Function.h"
68 #include "llvm/IR/IRBuilder.h"
69 #include "llvm/IR/InstrTypes.h"
70 #include "llvm/IR/Instructions.h"
71 #include "llvm/IR/Metadata.h"
72 #include "llvm/IR/Module.h"
73 #include "llvm/IR/PatternMatch.h"
74 #include "llvm/IR/Type.h"
75 #include "llvm/IR/Use.h"
76 #include "llvm/IR/User.h"
77 #include "llvm/IR/Value.h"
78 #include "llvm/Pass.h"
80 #include "llvm/Support/Casting.h"
82 #include "llvm/Support/Compiler.h"
83 #include "llvm/Support/Debug.h"
86 #include "llvm/Transforms/Scalar.h"
91 #include <algorithm>
92 #include <cassert>
93 #include <iterator>
94 #include <limits>
95 #include <utility>
96 #include <vector>
97 
98 using namespace llvm;
99 using namespace llvm::PatternMatch;
100 
101 static cl::opt<unsigned> LoopSizeCutoff("irce-loop-size-cutoff", cl::Hidden,
102  cl::init(64));
103 
104 static cl::opt<bool> PrintChangedLoops("irce-print-changed-loops", cl::Hidden,
105  cl::init(false));
106 
107 static cl::opt<bool> PrintRangeChecks("irce-print-range-checks", cl::Hidden,
108  cl::init(false));
109 
110 static cl::opt<int> MaxExitProbReciprocal("irce-max-exit-prob-reciprocal",
111  cl::Hidden, cl::init(10));
112 
113 static cl::opt<bool> SkipProfitabilityChecks("irce-skip-profitability-checks",
114  cl::Hidden, cl::init(false));
115 
116 static cl::opt<bool> AllowUnsignedLatchCondition("irce-allow-unsigned-latch",
117  cl::Hidden, cl::init(true));
118 
119 static const char *ClonedLoopTag = "irce.loop.clone";
120 
121 #define DEBUG_TYPE "irce"
122 
123 namespace {
124 
125 /// An inductive range check is conditional branch in a loop with
126 ///
127 /// 1. a very cold successor (i.e. the branch jumps to that successor very
128 /// rarely)
129 ///
130 /// and
131 ///
132 /// 2. a condition that is provably true for some contiguous range of values
133 /// taken by the containing loop's induction variable.
134 ///
135 class InductiveRangeCheck {
136  // Classifies a range check
137  enum RangeCheckKind : unsigned {
138  // Range check of the form "0 <= I".
139  RANGE_CHECK_LOWER = 1,
140 
141  // Range check of the form "I < L" where L is known positive.
142  RANGE_CHECK_UPPER = 2,
143 
144  // The logical and of the RANGE_CHECK_LOWER and RANGE_CHECK_UPPER
145  // conditions.
146  RANGE_CHECK_BOTH = RANGE_CHECK_LOWER | RANGE_CHECK_UPPER,
147 
148  // Unrecognized range check condition.
149  RANGE_CHECK_UNKNOWN = (unsigned)-1
150  };
151 
152  static StringRef rangeCheckKindToStr(RangeCheckKind);
153 
154  const SCEV *Begin = nullptr;
155  const SCEV *Step = nullptr;
156  const SCEV *End = nullptr;
157  Use *CheckUse = nullptr;
158  RangeCheckKind Kind = RANGE_CHECK_UNKNOWN;
159  bool IsSigned = true;
160 
161  static RangeCheckKind parseRangeCheckICmp(Loop *L, ICmpInst *ICI,
162  ScalarEvolution &SE, Value *&Index,
163  Value *&Length, bool &IsSigned);
164 
165  static void
166  extractRangeChecksFromCond(Loop *L, ScalarEvolution &SE, Use &ConditionUse,
168  SmallPtrSetImpl<Value *> &Visited);
169 
170 public:
171  const SCEV *getBegin() const { return Begin; }
172  const SCEV *getStep() const { return Step; }
173  const SCEV *getEnd() const { return End; }
174  bool isSigned() const { return IsSigned; }
175 
176  void print(raw_ostream &OS) const {
177  OS << "InductiveRangeCheck:\n";
178  OS << " Kind: " << rangeCheckKindToStr(Kind) << "\n";
179  OS << " Begin: ";
180  Begin->print(OS);
181  OS << " Step: ";
182  Step->print(OS);
183  OS << " End: ";
184  End->print(OS);
185  OS << "\n CheckUse: ";
186  getCheckUse()->getUser()->print(OS);
187  OS << " Operand: " << getCheckUse()->getOperandNo() << "\n";
188  }
189 
191  void dump() {
192  print(dbgs());
193  }
194 
195  Use *getCheckUse() const { return CheckUse; }
196 
197  /// Represents an signed integer range [Range.getBegin(), Range.getEnd()). If
198  /// R.getEnd() le R.getBegin(), then R denotes the empty range.
199 
200  class Range {
201  const SCEV *Begin;
202  const SCEV *End;
203 
204  public:
205  Range(const SCEV *Begin, const SCEV *End) : Begin(Begin), End(End) {
206  assert(Begin->getType() == End->getType() && "ill-typed range!");
207  }
208 
209  Type *getType() const { return Begin->getType(); }
210  const SCEV *getBegin() const { return Begin; }
211  const SCEV *getEnd() const { return End; }
212  bool isEmpty(ScalarEvolution &SE, bool IsSigned) const {
213  if (Begin == End)
214  return true;
215  if (IsSigned)
216  return SE.isKnownPredicate(ICmpInst::ICMP_SGE, Begin, End);
217  else
218  return SE.isKnownPredicate(ICmpInst::ICMP_UGE, Begin, End);
219  }
220  };
221 
222  /// This is the value the condition of the branch needs to evaluate to for the
223  /// branch to take the hot successor (see (1) above).
224  bool getPassingDirection() { return true; }
225 
226  /// Computes a range for the induction variable (IndVar) in which the range
227  /// check is redundant and can be constant-folded away. The induction
228  /// variable is not required to be the canonical {0,+,1} induction variable.
229  Optional<Range> computeSafeIterationSpace(ScalarEvolution &SE,
230  const SCEVAddRecExpr *IndVar,
231  bool IsLatchSigned) const;
232 
233  /// Parse out a set of inductive range checks from \p BI and append them to \p
234  /// Checks.
235  ///
236  /// NB! There may be conditions feeding into \p BI that aren't inductive range
237  /// checks, and hence don't end up in \p Checks.
238  static void
239  extractRangeChecksFromBranch(BranchInst *BI, Loop *L, ScalarEvolution &SE,
242 };
243 
244 class InductiveRangeCheckElimination {
245  ScalarEvolution &SE;
247  DominatorTree &DT;
248  LoopInfo &LI;
249 
250 public:
251  InductiveRangeCheckElimination(ScalarEvolution &SE,
253  LoopInfo &LI)
254  : SE(SE), BPI(BPI), DT(DT), LI(LI) {}
255 
256  bool run(Loop *L, function_ref<void(Loop *, bool)> LPMAddNewLoop);
257 };
258 
259 class IRCELegacyPass : public LoopPass {
260 public:
261  static char ID;
262 
263  IRCELegacyPass() : LoopPass(ID) {
265  }
266 
267  void getAnalysisUsage(AnalysisUsage &AU) const override {
270  }
271 
272  bool runOnLoop(Loop *L, LPPassManager &LPM) override;
273 };
274 
275 } // end anonymous namespace
276 
277 char IRCELegacyPass::ID = 0;
278 
279 INITIALIZE_PASS_BEGIN(IRCELegacyPass, "irce",
280  "Inductive range check elimination", false, false)
283 INITIALIZE_PASS_END(IRCELegacyPass, "irce", "Inductive range check elimination",
284  false, false)
285 
286 StringRef InductiveRangeCheck::rangeCheckKindToStr(
287  InductiveRangeCheck::RangeCheckKind RCK) {
288  switch (RCK) {
289  case InductiveRangeCheck::RANGE_CHECK_UNKNOWN:
290  return "RANGE_CHECK_UNKNOWN";
291 
292  case InductiveRangeCheck::RANGE_CHECK_UPPER:
293  return "RANGE_CHECK_UPPER";
294 
295  case InductiveRangeCheck::RANGE_CHECK_LOWER:
296  return "RANGE_CHECK_LOWER";
297 
298  case InductiveRangeCheck::RANGE_CHECK_BOTH:
299  return "RANGE_CHECK_BOTH";
300  }
301 
302  llvm_unreachable("unknown range check type!");
303 }
304 
305 /// Parse a single ICmp instruction, `ICI`, into a range check. If `ICI` cannot
306 /// be interpreted as a range check, return `RANGE_CHECK_UNKNOWN` and set
307 /// `Index` and `Length` to `nullptr`. Otherwise set `Index` to the value being
308 /// range checked, and set `Length` to the upper limit `Index` is being range
309 /// checked with if (and only if) the range check type is stronger or equal to
310 /// RANGE_CHECK_UPPER.
311 InductiveRangeCheck::RangeCheckKind
312 InductiveRangeCheck::parseRangeCheckICmp(Loop *L, ICmpInst *ICI,
313  ScalarEvolution &SE, Value *&Index,
314  Value *&Length, bool &IsSigned) {
315  auto IsLoopInvariant = [&SE, L](Value *V) {
316  return SE.isLoopInvariant(SE.getSCEV(V), L);
317  };
318 
319  ICmpInst::Predicate Pred = ICI->getPredicate();
320  Value *LHS = ICI->getOperand(0);
321  Value *RHS = ICI->getOperand(1);
322 
323  switch (Pred) {
324  default:
325  return RANGE_CHECK_UNKNOWN;
326 
327  case ICmpInst::ICMP_SLE:
328  std::swap(LHS, RHS);
330  case ICmpInst::ICMP_SGE:
331  IsSigned = true;
332  if (match(RHS, m_ConstantInt<0>())) {
333  Index = LHS;
334  return RANGE_CHECK_LOWER;
335  }
336  return RANGE_CHECK_UNKNOWN;
337 
338  case ICmpInst::ICMP_SLT:
339  std::swap(LHS, RHS);
341  case ICmpInst::ICMP_SGT:
342  IsSigned = true;
343  if (match(RHS, m_ConstantInt<-1>())) {
344  Index = LHS;
345  return RANGE_CHECK_LOWER;
346  }
347 
348  if (IsLoopInvariant(LHS)) {
349  Index = RHS;
350  Length = LHS;
351  return RANGE_CHECK_UPPER;
352  }
353  return RANGE_CHECK_UNKNOWN;
354 
355  case ICmpInst::ICMP_ULT:
356  std::swap(LHS, RHS);
358  case ICmpInst::ICMP_UGT:
359  IsSigned = false;
360  if (IsLoopInvariant(LHS)) {
361  Index = RHS;
362  Length = LHS;
363  return RANGE_CHECK_BOTH;
364  }
365  return RANGE_CHECK_UNKNOWN;
366  }
367 
368  llvm_unreachable("default clause returns!");
369 }
370 
371 void InductiveRangeCheck::extractRangeChecksFromCond(
372  Loop *L, ScalarEvolution &SE, Use &ConditionUse,
374  SmallPtrSetImpl<Value *> &Visited) {
375  Value *Condition = ConditionUse.get();
376  if (!Visited.insert(Condition).second)
377  return;
378 
379  // TODO: Do the same for OR, XOR, NOT etc?
380  if (match(Condition, m_And(m_Value(), m_Value()))) {
381  extractRangeChecksFromCond(L, SE, cast<User>(Condition)->getOperandUse(0),
382  Checks, Visited);
383  extractRangeChecksFromCond(L, SE, cast<User>(Condition)->getOperandUse(1),
384  Checks, Visited);
385  return;
386  }
387 
388  ICmpInst *ICI = dyn_cast<ICmpInst>(Condition);
389  if (!ICI)
390  return;
391 
392  Value *Length = nullptr, *Index;
393  bool IsSigned;
394  auto RCKind = parseRangeCheckICmp(L, ICI, SE, Index, Length, IsSigned);
395  if (RCKind == InductiveRangeCheck::RANGE_CHECK_UNKNOWN)
396  return;
397 
398  const auto *IndexAddRec = dyn_cast<SCEVAddRecExpr>(SE.getSCEV(Index));
399  bool IsAffineIndex =
400  IndexAddRec && (IndexAddRec->getLoop() == L) && IndexAddRec->isAffine();
401 
402  if (!IsAffineIndex)
403  return;
404 
405  const SCEV *End = nullptr;
406  // We strengthen "0 <= I" to "0 <= I < INT_SMAX" and "I < L" to "0 <= I < L".
407  // We can potentially do much better here.
408  if (Length)
409  End = SE.getSCEV(Length);
410  else {
411  assert(RCKind == InductiveRangeCheck::RANGE_CHECK_LOWER && "invariant!");
412  // So far we can only reach this point for Signed range check. This may
413  // change in future. In this case we will need to pick Unsigned max for the
414  // unsigned range check.
415  unsigned BitWidth = cast<IntegerType>(IndexAddRec->getType())->getBitWidth();
416  const SCEV *SIntMax = SE.getConstant(APInt::getSignedMaxValue(BitWidth));
417  End = SIntMax;
418  }
419 
420  InductiveRangeCheck IRC;
421  IRC.End = End;
422  IRC.Begin = IndexAddRec->getStart();
423  IRC.Step = IndexAddRec->getStepRecurrence(SE);
424  IRC.CheckUse = &ConditionUse;
425  IRC.Kind = RCKind;
426  IRC.IsSigned = IsSigned;
427  Checks.push_back(IRC);
428 }
429 
430 void InductiveRangeCheck::extractRangeChecksFromBranch(
433  if (BI->isUnconditional() || BI->getParent() == L->getLoopLatch())
434  return;
435 
436  BranchProbability LikelyTaken(15, 16);
437 
438  if (!SkipProfitabilityChecks && BPI &&
439  BPI->getEdgeProbability(BI->getParent(), (unsigned)0) < LikelyTaken)
440  return;
441 
442  SmallPtrSet<Value *, 8> Visited;
443  InductiveRangeCheck::extractRangeChecksFromCond(L, SE, BI->getOperandUse(0),
444  Checks, Visited);
445 }
446 
447 // Add metadata to the loop L to disable loop optimizations. Callers need to
448 // confirm that optimizing loop L is not beneficial.
450  // We do not care about any existing loopID related metadata for L, since we
451  // are setting all loop metadata to false.
453  // Reserve first location for self reference to the LoopID metadata node.
454  MDNode *Dummy = MDNode::get(Context, {});
455  MDNode *DisableUnroll = MDNode::get(
456  Context, {MDString::get(Context, "llvm.loop.unroll.disable")});
457  Metadata *FalseVal =
459  MDNode *DisableVectorize = MDNode::get(
460  Context,
461  {MDString::get(Context, "llvm.loop.vectorize.enable"), FalseVal});
462  MDNode *DisableLICMVersioning = MDNode::get(
463  Context, {MDString::get(Context, "llvm.loop.licm_versioning.disable")});
464  MDNode *DisableDistribution= MDNode::get(
465  Context,
466  {MDString::get(Context, "llvm.loop.distribute.enable"), FalseVal});
467  MDNode *NewLoopID =
468  MDNode::get(Context, {Dummy, DisableUnroll, DisableVectorize,
469  DisableLICMVersioning, DisableDistribution});
470  // Set operand 0 to refer to the loop id itself.
471  NewLoopID->replaceOperandWith(0, NewLoopID);
472  L.setLoopID(NewLoopID);
473 }
474 
475 namespace {
476 
477 // Keeps track of the structure of a loop. This is similar to llvm::Loop,
478 // except that it is more lightweight and can track the state of a loop through
479 // changing and potentially invalid IR. This structure also formalizes the
480 // kinds of loops we can deal with -- ones that have a single latch that is also
481 // an exiting block *and* have a canonical induction variable.
482 struct LoopStructure {
483  const char *Tag = "";
484 
485  BasicBlock *Header = nullptr;
486  BasicBlock *Latch = nullptr;
487 
488  // `Latch's terminator instruction is `LatchBr', and it's `LatchBrExitIdx'th
489  // successor is `LatchExit', the exit block of the loop.
490  BranchInst *LatchBr = nullptr;
491  BasicBlock *LatchExit = nullptr;
492  unsigned LatchBrExitIdx = std::numeric_limits<unsigned>::max();
493 
494  // The loop represented by this instance of LoopStructure is semantically
495  // equivalent to:
496  //
497  // intN_ty inc = IndVarIncreasing ? 1 : -1;
498  // pred_ty predicate = IndVarIncreasing ? ICMP_SLT : ICMP_SGT;
499  //
500  // for (intN_ty iv = IndVarStart; predicate(iv, LoopExitAt); iv = IndVarBase)
501  // ... body ...
502 
503  Value *IndVarBase = nullptr;
504  Value *IndVarStart = nullptr;
505  Value *IndVarStep = nullptr;
506  Value *LoopExitAt = nullptr;
507  bool IndVarIncreasing = false;
508  bool IsSignedPredicate = true;
509 
510  LoopStructure() = default;
511 
512  template <typename M> LoopStructure map(M Map) const {
513  LoopStructure Result;
514  Result.Tag = Tag;
515  Result.Header = cast<BasicBlock>(Map(Header));
516  Result.Latch = cast<BasicBlock>(Map(Latch));
517  Result.LatchBr = cast<BranchInst>(Map(LatchBr));
518  Result.LatchExit = cast<BasicBlock>(Map(LatchExit));
519  Result.LatchBrExitIdx = LatchBrExitIdx;
520  Result.IndVarBase = Map(IndVarBase);
521  Result.IndVarStart = Map(IndVarStart);
522  Result.IndVarStep = Map(IndVarStep);
523  Result.LoopExitAt = Map(LoopExitAt);
524  Result.IndVarIncreasing = IndVarIncreasing;
525  Result.IsSignedPredicate = IsSignedPredicate;
526  return Result;
527  }
528 
529  static Optional<LoopStructure> parseLoopStructure(ScalarEvolution &,
531  Loop &, const char *&);
532 };
533 
534 /// This class is used to constrain loops to run within a given iteration space.
535 /// The algorithm this class implements is given a Loop and a range [Begin,
536 /// End). The algorithm then tries to break out a "main loop" out of the loop
537 /// it is given in a way that the "main loop" runs with the induction variable
538 /// in a subset of [Begin, End). The algorithm emits appropriate pre and post
539 /// loops to run any remaining iterations. The pre loop runs any iterations in
540 /// which the induction variable is < Begin, and the post loop runs any
541 /// iterations in which the induction variable is >= End.
542 class LoopConstrainer {
543  // The representation of a clone of the original loop we started out with.
544  struct ClonedLoop {
545  // The cloned blocks
546  std::vector<BasicBlock *> Blocks;
547 
548  // `Map` maps values in the clonee into values in the cloned version
549  ValueToValueMapTy Map;
550 
551  // An instance of `LoopStructure` for the cloned loop
552  LoopStructure Structure;
553  };
554 
555  // Result of rewriting the range of a loop. See changeIterationSpaceEnd for
556  // more details on what these fields mean.
557  struct RewrittenRangeInfo {
558  BasicBlock *PseudoExit = nullptr;
559  BasicBlock *ExitSelector = nullptr;
560  std::vector<PHINode *> PHIValuesAtPseudoExit;
561  PHINode *IndVarEnd = nullptr;
562 
563  RewrittenRangeInfo() = default;
564  };
565 
566  // Calculated subranges we restrict the iteration space of the main loop to.
567  // See the implementation of `calculateSubRanges' for more details on how
568  // these fields are computed. `LowLimit` is None if there is no restriction
569  // on low end of the restricted iteration space of the main loop. `HighLimit`
570  // is None if there is no restriction on high end of the restricted iteration
571  // space of the main loop.
572 
573  struct SubRanges {
574  Optional<const SCEV *> LowLimit;
575  Optional<const SCEV *> HighLimit;
576  };
577 
578  // A utility function that does a `replaceUsesOfWith' on the incoming block
579  // set of a `PHINode' -- replaces instances of `Block' in the `PHINode's
580  // incoming block list with `ReplaceBy'.
581  static void replacePHIBlock(PHINode *PN, BasicBlock *Block,
582  BasicBlock *ReplaceBy);
583 
584  // Compute a safe set of limits for the main loop to run in -- effectively the
585  // intersection of `Range' and the iteration space of the original loop.
586  // Return None if unable to compute the set of subranges.
587  Optional<SubRanges> calculateSubRanges(bool IsSignedPredicate) const;
588 
589  // Clone `OriginalLoop' and return the result in CLResult. The IR after
590  // running `cloneLoop' is well formed except for the PHI nodes in CLResult --
591  // the PHI nodes say that there is an incoming edge from `OriginalPreheader`
592  // but there is no such edge.
593  void cloneLoop(ClonedLoop &CLResult, const char *Tag) const;
594 
595  // Create the appropriate loop structure needed to describe a cloned copy of
596  // `Original`. The clone is described by `VM`.
597  Loop *createClonedLoopStructure(Loop *Original, Loop *Parent,
598  ValueToValueMapTy &VM, bool IsSubloop);
599 
600  // Rewrite the iteration space of the loop denoted by (LS, Preheader). The
601  // iteration space of the rewritten loop ends at ExitLoopAt. The start of the
602  // iteration space is not changed. `ExitLoopAt' is assumed to be slt
603  // `OriginalHeaderCount'.
604  //
605  // If there are iterations left to execute, control is made to jump to
606  // `ContinuationBlock', otherwise they take the normal loop exit. The
607  // returned `RewrittenRangeInfo' object is populated as follows:
608  //
609  // .PseudoExit is a basic block that unconditionally branches to
610  // `ContinuationBlock'.
611  //
612  // .ExitSelector is a basic block that decides, on exit from the loop,
613  // whether to branch to the "true" exit or to `PseudoExit'.
614  //
615  // .PHIValuesAtPseudoExit are PHINodes in `PseudoExit' that compute the value
616  // for each PHINode in the loop header on taking the pseudo exit.
617  //
618  // After changeIterationSpaceEnd, `Preheader' is no longer a legitimate
619  // preheader because it is made to branch to the loop header only
620  // conditionally.
621  RewrittenRangeInfo
622  changeIterationSpaceEnd(const LoopStructure &LS, BasicBlock *Preheader,
623  Value *ExitLoopAt,
624  BasicBlock *ContinuationBlock) const;
625 
626  // The loop denoted by `LS' has `OldPreheader' as its preheader. This
627  // function creates a new preheader for `LS' and returns it.
628  BasicBlock *createPreheader(const LoopStructure &LS, BasicBlock *OldPreheader,
629  const char *Tag) const;
630 
631  // `ContinuationBlockAndPreheader' was the continuation block for some call to
632  // `changeIterationSpaceEnd' and is the preheader to the loop denoted by `LS'.
633  // This function rewrites the PHI nodes in `LS.Header' to start with the
634  // correct value.
635  void rewriteIncomingValuesForPHIs(
636  LoopStructure &LS, BasicBlock *ContinuationBlockAndPreheader,
637  const LoopConstrainer::RewrittenRangeInfo &RRI) const;
638 
639  // Even though we do not preserve any passes at this time, we at least need to
640  // keep the parent loop structure consistent. The `LPPassManager' seems to
641  // verify this after running a loop pass. This function adds the list of
642  // blocks denoted by BBs to this loops parent loop if required.
643  void addToParentLoopIfNeeded(ArrayRef<BasicBlock *> BBs);
644 
645  // Some global state.
646  Function &F;
647  LLVMContext &Ctx;
648  ScalarEvolution &SE;
649  DominatorTree &DT;
650  LoopInfo &LI;
651  function_ref<void(Loop *, bool)> LPMAddNewLoop;
652 
653  // Information about the original loop we started out with.
654  Loop &OriginalLoop;
655 
656  const SCEV *LatchTakenCount = nullptr;
657  BasicBlock *OriginalPreheader = nullptr;
658 
659  // The preheader of the main loop. This may or may not be different from
660  // `OriginalPreheader'.
661  BasicBlock *MainLoopPreheader = nullptr;
662 
663  // The range we need to run the main loop in.
664  InductiveRangeCheck::Range Range;
665 
666  // The structure of the main loop (see comment at the beginning of this class
667  // for a definition)
668  LoopStructure MainLoopStructure;
669 
670 public:
671  LoopConstrainer(Loop &L, LoopInfo &LI,
672  function_ref<void(Loop *, bool)> LPMAddNewLoop,
673  const LoopStructure &LS, ScalarEvolution &SE,
674  DominatorTree &DT, InductiveRangeCheck::Range R)
675  : F(*L.getHeader()->getParent()), Ctx(L.getHeader()->getContext()),
676  SE(SE), DT(DT), LI(LI), LPMAddNewLoop(LPMAddNewLoop), OriginalLoop(L),
677  Range(R), MainLoopStructure(LS) {}
678 
679  // Entry point for the algorithm. Returns true on success.
680  bool run();
681 };
682 
683 } // end anonymous namespace
684 
685 void LoopConstrainer::replacePHIBlock(PHINode *PN, BasicBlock *Block,
686  BasicBlock *ReplaceBy) {
687  for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
688  if (PN->getIncomingBlock(i) == Block)
689  PN->setIncomingBlock(i, ReplaceBy);
690 }
691 
692 static bool CannotBeMaxInLoop(const SCEV *BoundSCEV, Loop *L,
693  ScalarEvolution &SE, bool Signed) {
694  unsigned BitWidth = cast<IntegerType>(BoundSCEV->getType())->getBitWidth();
695  APInt Max = Signed ? APInt::getSignedMaxValue(BitWidth) :
696  APInt::getMaxValue(BitWidth);
698  return SE.isAvailableAtLoopEntry(BoundSCEV, L) &&
699  SE.isLoopEntryGuardedByCond(L, Predicate, BoundSCEV,
700  SE.getConstant(Max));
701 }
702 
703 /// Given a loop with an deccreasing induction variable, is it possible to
704 /// safely calculate the bounds of a new loop using the given Predicate.
705 static bool isSafeDecreasingBound(const SCEV *Start,
706  const SCEV *BoundSCEV, const SCEV *Step,
707  ICmpInst::Predicate Pred,
708  unsigned LatchBrExitIdx,
709  Loop *L, ScalarEvolution &SE) {
710  if (Pred != ICmpInst::ICMP_SLT && Pred != ICmpInst::ICMP_SGT &&
711  Pred != ICmpInst::ICMP_ULT && Pred != ICmpInst::ICMP_UGT)
712  return false;
713 
714  if (!SE.isAvailableAtLoopEntry(BoundSCEV, L))
715  return false;
716 
717  assert(SE.isKnownNegative(Step) && "expecting negative step");
718 
719  LLVM_DEBUG(dbgs() << "irce: isSafeDecreasingBound with:\n");
720  LLVM_DEBUG(dbgs() << "irce: Start: " << *Start << "\n");
721  LLVM_DEBUG(dbgs() << "irce: Step: " << *Step << "\n");
722  LLVM_DEBUG(dbgs() << "irce: BoundSCEV: " << *BoundSCEV << "\n");
723  LLVM_DEBUG(dbgs() << "irce: Pred: " << ICmpInst::getPredicateName(Pred)
724  << "\n");
725  LLVM_DEBUG(dbgs() << "irce: LatchExitBrIdx: " << LatchBrExitIdx << "\n");
726 
727  bool IsSigned = ICmpInst::isSigned(Pred);
728  // The predicate that we need to check that the induction variable lies
729  // within bounds.
730  ICmpInst::Predicate BoundPred =
732 
733  if (LatchBrExitIdx == 1)
734  return SE.isLoopEntryGuardedByCond(L, BoundPred, Start, BoundSCEV);
735 
736  assert(LatchBrExitIdx == 0 &&
737  "LatchBrExitIdx should be either 0 or 1");
738 
739  const SCEV *StepPlusOne = SE.getAddExpr(Step, SE.getOne(Step->getType()));
740  unsigned BitWidth = cast<IntegerType>(BoundSCEV->getType())->getBitWidth();
741  APInt Min = IsSigned ? APInt::getSignedMinValue(BitWidth) :
742  APInt::getMinValue(BitWidth);
743  const SCEV *Limit = SE.getMinusSCEV(SE.getConstant(Min), StepPlusOne);
744 
745  const SCEV *MinusOne =
746  SE.getMinusSCEV(BoundSCEV, SE.getOne(BoundSCEV->getType()));
747 
748  return SE.isLoopEntryGuardedByCond(L, BoundPred, Start, MinusOne) &&
749  SE.isLoopEntryGuardedByCond(L, BoundPred, BoundSCEV, Limit);
750 
751 }
752 
753 /// Given a loop with an increasing induction variable, is it possible to
754 /// safely calculate the bounds of a new loop using the given Predicate.
755 static bool isSafeIncreasingBound(const SCEV *Start,
756  const SCEV *BoundSCEV, const SCEV *Step,
757  ICmpInst::Predicate Pred,
758  unsigned LatchBrExitIdx,
759  Loop *L, ScalarEvolution &SE) {
760  if (Pred != ICmpInst::ICMP_SLT && Pred != ICmpInst::ICMP_SGT &&
761  Pred != ICmpInst::ICMP_ULT && Pred != ICmpInst::ICMP_UGT)
762  return false;
763 
764  if (!SE.isAvailableAtLoopEntry(BoundSCEV, L))
765  return false;
766 
767  LLVM_DEBUG(dbgs() << "irce: isSafeIncreasingBound with:\n");
768  LLVM_DEBUG(dbgs() << "irce: Start: " << *Start << "\n");
769  LLVM_DEBUG(dbgs() << "irce: Step: " << *Step << "\n");
770  LLVM_DEBUG(dbgs() << "irce: BoundSCEV: " << *BoundSCEV << "\n");
771  LLVM_DEBUG(dbgs() << "irce: Pred: " << ICmpInst::getPredicateName(Pred)
772  << "\n");
773  LLVM_DEBUG(dbgs() << "irce: LatchExitBrIdx: " << LatchBrExitIdx << "\n");
774 
775  bool IsSigned = ICmpInst::isSigned(Pred);
776  // The predicate that we need to check that the induction variable lies
777  // within bounds.
778  ICmpInst::Predicate BoundPred =
780 
781  if (LatchBrExitIdx == 1)
782  return SE.isLoopEntryGuardedByCond(L, BoundPred, Start, BoundSCEV);
783 
784  assert(LatchBrExitIdx == 0 && "LatchBrExitIdx should be 0 or 1");
785 
786  const SCEV *StepMinusOne =
787  SE.getMinusSCEV(Step, SE.getOne(Step->getType()));
788  unsigned BitWidth = cast<IntegerType>(BoundSCEV->getType())->getBitWidth();
789  APInt Max = IsSigned ? APInt::getSignedMaxValue(BitWidth) :
790  APInt::getMaxValue(BitWidth);
791  const SCEV *Limit = SE.getMinusSCEV(SE.getConstant(Max), StepMinusOne);
792 
793  return (SE.isLoopEntryGuardedByCond(L, BoundPred, Start,
794  SE.getAddExpr(BoundSCEV, Step)) &&
795  SE.isLoopEntryGuardedByCond(L, BoundPred, BoundSCEV, Limit));
796 }
797 
798 static bool CannotBeMinInLoop(const SCEV *BoundSCEV, Loop *L,
799  ScalarEvolution &SE, bool Signed) {
800  unsigned BitWidth = cast<IntegerType>(BoundSCEV->getType())->getBitWidth();
801  APInt Min = Signed ? APInt::getSignedMinValue(BitWidth) :
802  APInt::getMinValue(BitWidth);
804  return SE.isAvailableAtLoopEntry(BoundSCEV, L) &&
805  SE.isLoopEntryGuardedByCond(L, Predicate, BoundSCEV,
806  SE.getConstant(Min));
807 }
808 
809 static bool isKnownNonNegativeInLoop(const SCEV *BoundSCEV, const Loop *L,
810  ScalarEvolution &SE) {
811  const SCEV *Zero = SE.getZero(BoundSCEV->getType());
812  return SE.isAvailableAtLoopEntry(BoundSCEV, L) &&
813  SE.isLoopEntryGuardedByCond(L, ICmpInst::ICMP_SGE, BoundSCEV, Zero);
814 }
815 
816 static bool isKnownNegativeInLoop(const SCEV *BoundSCEV, const Loop *L,
817  ScalarEvolution &SE) {
818  const SCEV *Zero = SE.getZero(BoundSCEV->getType());
819  return SE.isAvailableAtLoopEntry(BoundSCEV, L) &&
820  SE.isLoopEntryGuardedByCond(L, ICmpInst::ICMP_SLT, BoundSCEV, Zero);
821 }
822 
824 LoopStructure::parseLoopStructure(ScalarEvolution &SE,
825  BranchProbabilityInfo *BPI, Loop &L,
826  const char *&FailureReason) {
827  if (!L.isLoopSimplifyForm()) {
828  FailureReason = "loop not in LoopSimplify form";
829  return None;
830  }
831 
832  BasicBlock *Latch = L.getLoopLatch();
833  assert(Latch && "Simplified loops only have one latch!");
834 
835  if (Latch->getTerminator()->getMetadata(ClonedLoopTag)) {
836  FailureReason = "loop has already been cloned";
837  return None;
838  }
839 
840  if (!L.isLoopExiting(Latch)) {
841  FailureReason = "no loop latch";
842  return None;
843  }
844 
845  BasicBlock *Header = L.getHeader();
846  BasicBlock *Preheader = L.getLoopPreheader();
847  if (!Preheader) {
848  FailureReason = "no preheader";
849  return None;
850  }
851 
852  BranchInst *LatchBr = dyn_cast<BranchInst>(Latch->getTerminator());
853  if (!LatchBr || LatchBr->isUnconditional()) {
854  FailureReason = "latch terminator not conditional branch";
855  return None;
856  }
857 
858  unsigned LatchBrExitIdx = LatchBr->getSuccessor(0) == Header ? 1 : 0;
859 
860  BranchProbability ExitProbability =
861  BPI ? BPI->getEdgeProbability(LatchBr->getParent(), LatchBrExitIdx)
863 
865  ExitProbability > BranchProbability(1, MaxExitProbReciprocal)) {
866  FailureReason = "short running loop, not profitable";
867  return None;
868  }
869 
870  ICmpInst *ICI = dyn_cast<ICmpInst>(LatchBr->getCondition());
871  if (!ICI || !isa<IntegerType>(ICI->getOperand(0)->getType())) {
872  FailureReason = "latch terminator branch not conditional on integral icmp";
873  return None;
874  }
875 
876  const SCEV *LatchCount = SE.getExitCount(&L, Latch);
877  if (isa<SCEVCouldNotCompute>(LatchCount)) {
878  FailureReason = "could not compute latch count";
879  return None;
880  }
881 
882  ICmpInst::Predicate Pred = ICI->getPredicate();
883  Value *LeftValue = ICI->getOperand(0);
884  const SCEV *LeftSCEV = SE.getSCEV(LeftValue);
885  IntegerType *IndVarTy = cast<IntegerType>(LeftValue->getType());
886 
887  Value *RightValue = ICI->getOperand(1);
888  const SCEV *RightSCEV = SE.getSCEV(RightValue);
889 
890  // We canonicalize `ICI` such that `LeftSCEV` is an add recurrence.
891  if (!isa<SCEVAddRecExpr>(LeftSCEV)) {
892  if (isa<SCEVAddRecExpr>(RightSCEV)) {
893  std::swap(LeftSCEV, RightSCEV);
894  std::swap(LeftValue, RightValue);
895  Pred = ICmpInst::getSwappedPredicate(Pred);
896  } else {
897  FailureReason = "no add recurrences in the icmp";
898  return None;
899  }
900  }
901 
902  auto HasNoSignedWrap = [&](const SCEVAddRecExpr *AR) {
903  if (AR->getNoWrapFlags(SCEV::FlagNSW))
904  return true;
905 
906  IntegerType *Ty = cast<IntegerType>(AR->getType());
907  IntegerType *WideTy =
908  IntegerType::get(Ty->getContext(), Ty->getBitWidth() * 2);
909 
910  const SCEVAddRecExpr *ExtendAfterOp =
911  dyn_cast<SCEVAddRecExpr>(SE.getSignExtendExpr(AR, WideTy));
912  if (ExtendAfterOp) {
913  const SCEV *ExtendedStart = SE.getSignExtendExpr(AR->getStart(), WideTy);
914  const SCEV *ExtendedStep =
915  SE.getSignExtendExpr(AR->getStepRecurrence(SE), WideTy);
916 
917  bool NoSignedWrap = ExtendAfterOp->getStart() == ExtendedStart &&
918  ExtendAfterOp->getStepRecurrence(SE) == ExtendedStep;
919 
920  if (NoSignedWrap)
921  return true;
922  }
923 
924  // We may have proved this when computing the sign extension above.
925  return AR->getNoWrapFlags(SCEV::FlagNSW) != SCEV::FlagAnyWrap;
926  };
927 
928  // `ICI` is interpreted as taking the backedge if the *next* value of the
929  // induction variable satisfies some constraint.
930 
931  const SCEVAddRecExpr *IndVarBase = cast<SCEVAddRecExpr>(LeftSCEV);
932  if (!IndVarBase->isAffine()) {
933  FailureReason = "LHS in icmp not induction variable";
934  return None;
935  }
936  const SCEV* StepRec = IndVarBase->getStepRecurrence(SE);
937  if (!isa<SCEVConstant>(StepRec)) {
938  FailureReason = "LHS in icmp not induction variable";
939  return None;
940  }
941  ConstantInt *StepCI = cast<SCEVConstant>(StepRec)->getValue();
942 
943  if (ICI->isEquality() && !HasNoSignedWrap(IndVarBase)) {
944  FailureReason = "LHS in icmp needs nsw for equality predicates";
945  return None;
946  }
947 
948  assert(!StepCI->isZero() && "Zero step?");
949  bool IsIncreasing = !StepCI->isNegative();
950  bool IsSignedPredicate = ICmpInst::isSigned(Pred);
951  const SCEV *StartNext = IndVarBase->getStart();
952  const SCEV *Addend = SE.getNegativeSCEV(IndVarBase->getStepRecurrence(SE));
953  const SCEV *IndVarStart = SE.getAddExpr(StartNext, Addend);
954  const SCEV *Step = SE.getSCEV(StepCI);
955 
956  ConstantInt *One = ConstantInt::get(IndVarTy, 1);
957  if (IsIncreasing) {
958  bool DecreasedRightValueByOne = false;
959  if (StepCI->isOne()) {
960  // Try to turn eq/ne predicates to those we can work with.
961  if (Pred == ICmpInst::ICMP_NE && LatchBrExitIdx == 1)
962  // while (++i != len) { while (++i < len) {
963  // ... ---> ...
964  // } }
965  // If both parts are known non-negative, it is profitable to use
966  // unsigned comparison in increasing loop. This allows us to make the
967  // comparison check against "RightSCEV + 1" more optimistic.
968  if (isKnownNonNegativeInLoop(IndVarStart, &L, SE) &&
969  isKnownNonNegativeInLoop(RightSCEV, &L, SE))
970  Pred = ICmpInst::ICMP_ULT;
971  else
972  Pred = ICmpInst::ICMP_SLT;
973  else if (Pred == ICmpInst::ICMP_EQ && LatchBrExitIdx == 0) {
974  // while (true) { while (true) {
975  // if (++i == len) ---> if (++i > len - 1)
976  // break; break;
977  // ... ...
978  // } }
979  if (IndVarBase->getNoWrapFlags(SCEV::FlagNUW) &&
980  CannotBeMinInLoop(RightSCEV, &L, SE, /*Signed*/false)) {
981  Pred = ICmpInst::ICMP_UGT;
982  RightSCEV = SE.getMinusSCEV(RightSCEV,
983  SE.getOne(RightSCEV->getType()));
984  DecreasedRightValueByOne = true;
985  } else if (CannotBeMinInLoop(RightSCEV, &L, SE, /*Signed*/true)) {
986  Pred = ICmpInst::ICMP_SGT;
987  RightSCEV = SE.getMinusSCEV(RightSCEV,
988  SE.getOne(RightSCEV->getType()));
989  DecreasedRightValueByOne = true;
990  }
991  }
992  }
993 
994  bool LTPred = (Pred == ICmpInst::ICMP_SLT || Pred == ICmpInst::ICMP_ULT);
995  bool GTPred = (Pred == ICmpInst::ICMP_SGT || Pred == ICmpInst::ICMP_UGT);
996  bool FoundExpectedPred =
997  (LTPred && LatchBrExitIdx == 1) || (GTPred && LatchBrExitIdx == 0);
998 
999  if (!FoundExpectedPred) {
1000  FailureReason = "expected icmp slt semantically, found something else";
1001  return None;
1002  }
1003 
1004  IsSignedPredicate = ICmpInst::isSigned(Pred);
1005  if (!IsSignedPredicate && !AllowUnsignedLatchCondition) {
1006  FailureReason = "unsigned latch conditions are explicitly prohibited";
1007  return None;
1008  }
1009 
1010  if (!isSafeIncreasingBound(IndVarStart, RightSCEV, Step, Pred,
1011  LatchBrExitIdx, &L, SE)) {
1012  FailureReason = "Unsafe loop bounds";
1013  return None;
1014  }
1015  if (LatchBrExitIdx == 0) {
1016  // We need to increase the right value unless we have already decreased
1017  // it virtually when we replaced EQ with SGT.
1018  if (!DecreasedRightValueByOne) {
1019  IRBuilder<> B(Preheader->getTerminator());
1020  RightValue = B.CreateAdd(RightValue, One);
1021  }
1022  } else {
1023  assert(!DecreasedRightValueByOne &&
1024  "Right value can be decreased only for LatchBrExitIdx == 0!");
1025  }
1026  } else {
1027  bool IncreasedRightValueByOne = false;
1028  if (StepCI->isMinusOne()) {
1029  // Try to turn eq/ne predicates to those we can work with.
1030  if (Pred == ICmpInst::ICMP_NE && LatchBrExitIdx == 1)
1031  // while (--i != len) { while (--i > len) {
1032  // ... ---> ...
1033  // } }
1034  // We intentionally don't turn the predicate into UGT even if we know
1035  // that both operands are non-negative, because it will only pessimize
1036  // our check against "RightSCEV - 1".
1037  Pred = ICmpInst::ICMP_SGT;
1038  else if (Pred == ICmpInst::ICMP_EQ && LatchBrExitIdx == 0) {
1039  // while (true) { while (true) {
1040  // if (--i == len) ---> if (--i < len + 1)
1041  // break; break;
1042  // ... ...
1043  // } }
1044  if (IndVarBase->getNoWrapFlags(SCEV::FlagNUW) &&
1045  CannotBeMaxInLoop(RightSCEV, &L, SE, /* Signed */ false)) {
1046  Pred = ICmpInst::ICMP_ULT;
1047  RightSCEV = SE.getAddExpr(RightSCEV, SE.getOne(RightSCEV->getType()));
1048  IncreasedRightValueByOne = true;
1049  } else if (CannotBeMaxInLoop(RightSCEV, &L, SE, /* Signed */ true)) {
1050  Pred = ICmpInst::ICMP_SLT;
1051  RightSCEV = SE.getAddExpr(RightSCEV, SE.getOne(RightSCEV->getType()));
1052  IncreasedRightValueByOne = true;
1053  }
1054  }
1055  }
1056 
1057  bool LTPred = (Pred == ICmpInst::ICMP_SLT || Pred == ICmpInst::ICMP_ULT);
1058  bool GTPred = (Pred == ICmpInst::ICMP_SGT || Pred == ICmpInst::ICMP_UGT);
1059 
1060  bool FoundExpectedPred =
1061  (GTPred && LatchBrExitIdx == 1) || (LTPred && LatchBrExitIdx == 0);
1062 
1063  if (!FoundExpectedPred) {
1064  FailureReason = "expected icmp sgt semantically, found something else";
1065  return None;
1066  }
1067 
1068  IsSignedPredicate =
1069  Pred == ICmpInst::ICMP_SLT || Pred == ICmpInst::ICMP_SGT;
1070 
1071  if (!IsSignedPredicate && !AllowUnsignedLatchCondition) {
1072  FailureReason = "unsigned latch conditions are explicitly prohibited";
1073  return None;
1074  }
1075 
1076  if (!isSafeDecreasingBound(IndVarStart, RightSCEV, Step, Pred,
1077  LatchBrExitIdx, &L, SE)) {
1078  FailureReason = "Unsafe bounds";
1079  return None;
1080  }
1081 
1082  if (LatchBrExitIdx == 0) {
1083  // We need to decrease the right value unless we have already increased
1084  // it virtually when we replaced EQ with SLT.
1085  if (!IncreasedRightValueByOne) {
1086  IRBuilder<> B(Preheader->getTerminator());
1087  RightValue = B.CreateSub(RightValue, One);
1088  }
1089  } else {
1090  assert(!IncreasedRightValueByOne &&
1091  "Right value can be increased only for LatchBrExitIdx == 0!");
1092  }
1093  }
1094  BasicBlock *LatchExit = LatchBr->getSuccessor(LatchBrExitIdx);
1095 
1096  assert(SE.getLoopDisposition(LatchCount, &L) ==
1098  "loop variant exit count doesn't make sense!");
1099 
1100  assert(!L.contains(LatchExit) && "expected an exit block!");
1101  const DataLayout &DL = Preheader->getModule()->getDataLayout();
1102  Value *IndVarStartV =
1103  SCEVExpander(SE, DL, "irce")
1104  .expandCodeFor(IndVarStart, IndVarTy, Preheader->getTerminator());
1105  IndVarStartV->setName("indvar.start");
1106 
1107  LoopStructure Result;
1108 
1109  Result.Tag = "main";
1110  Result.Header = Header;
1111  Result.Latch = Latch;
1112  Result.LatchBr = LatchBr;
1113  Result.LatchExit = LatchExit;
1114  Result.LatchBrExitIdx = LatchBrExitIdx;
1115  Result.IndVarStart = IndVarStartV;
1116  Result.IndVarStep = StepCI;
1117  Result.IndVarBase = LeftValue;
1118  Result.IndVarIncreasing = IsIncreasing;
1119  Result.LoopExitAt = RightValue;
1120  Result.IsSignedPredicate = IsSignedPredicate;
1121 
1122  FailureReason = nullptr;
1123 
1124  return Result;
1125 }
1126 
1128 LoopConstrainer::calculateSubRanges(bool IsSignedPredicate) const {
1129  IntegerType *Ty = cast<IntegerType>(LatchTakenCount->getType());
1130 
1131  if (Range.getType() != Ty)
1132  return None;
1133 
1134  LoopConstrainer::SubRanges Result;
1135 
1136  // I think we can be more aggressive here and make this nuw / nsw if the
1137  // addition that feeds into the icmp for the latch's terminating branch is nuw
1138  // / nsw. In any case, a wrapping 2's complement addition is safe.
1139  const SCEV *Start = SE.getSCEV(MainLoopStructure.IndVarStart);
1140  const SCEV *End = SE.getSCEV(MainLoopStructure.LoopExitAt);
1141 
1142  bool Increasing = MainLoopStructure.IndVarIncreasing;
1143 
1144  // We compute `Smallest` and `Greatest` such that [Smallest, Greatest), or
1145  // [Smallest, GreatestSeen] is the range of values the induction variable
1146  // takes.
1147 
1148  const SCEV *Smallest = nullptr, *Greatest = nullptr, *GreatestSeen = nullptr;
1149 
1150  const SCEV *One = SE.getOne(Ty);
1151  if (Increasing) {
1152  Smallest = Start;
1153  Greatest = End;
1154  // No overflow, because the range [Smallest, GreatestSeen] is not empty.
1155  GreatestSeen = SE.getMinusSCEV(End, One);
1156  } else {
1157  // These two computations may sign-overflow. Here is why that is okay:
1158  //
1159  // We know that the induction variable does not sign-overflow on any
1160  // iteration except the last one, and it starts at `Start` and ends at
1161  // `End`, decrementing by one every time.
1162  //
1163  // * if `Smallest` sign-overflows we know `End` is `INT_SMAX`. Since the
1164  // induction variable is decreasing we know that that the smallest value
1165  // the loop body is actually executed with is `INT_SMIN` == `Smallest`.
1166  //
1167  // * if `Greatest` sign-overflows, we know it can only be `INT_SMIN`. In
1168  // that case, `Clamp` will always return `Smallest` and
1169  // [`Result.LowLimit`, `Result.HighLimit`) = [`Smallest`, `Smallest`)
1170  // will be an empty range. Returning an empty range is always safe.
1171 
1172  Smallest = SE.getAddExpr(End, One);
1173  Greatest = SE.getAddExpr(Start, One);
1174  GreatestSeen = Start;
1175  }
1176 
1177  auto Clamp = [this, Smallest, Greatest, IsSignedPredicate](const SCEV *S) {
1178  return IsSignedPredicate
1179  ? SE.getSMaxExpr(Smallest, SE.getSMinExpr(Greatest, S))
1180  : SE.getUMaxExpr(Smallest, SE.getUMinExpr(Greatest, S));
1181  };
1182 
1183  // In some cases we can prove that we don't need a pre or post loop.
1184  ICmpInst::Predicate PredLE =
1185  IsSignedPredicate ? ICmpInst::ICMP_SLE : ICmpInst::ICMP_ULE;
1186  ICmpInst::Predicate PredLT =
1187  IsSignedPredicate ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT;
1188 
1189  bool ProvablyNoPreloop =
1190  SE.isKnownPredicate(PredLE, Range.getBegin(), Smallest);
1191  if (!ProvablyNoPreloop)
1192  Result.LowLimit = Clamp(Range.getBegin());
1193 
1194  bool ProvablyNoPostLoop =
1195  SE.isKnownPredicate(PredLT, GreatestSeen, Range.getEnd());
1196  if (!ProvablyNoPostLoop)
1197  Result.HighLimit = Clamp(Range.getEnd());
1198 
1199  return Result;
1200 }
1201 
1202 void LoopConstrainer::cloneLoop(LoopConstrainer::ClonedLoop &Result,
1203  const char *Tag) const {
1204  for (BasicBlock *BB : OriginalLoop.getBlocks()) {
1205  BasicBlock *Clone = CloneBasicBlock(BB, Result.Map, Twine(".") + Tag, &F);
1206  Result.Blocks.push_back(Clone);
1207  Result.Map[BB] = Clone;
1208  }
1209 
1210  auto GetClonedValue = [&Result](Value *V) {
1211  assert(V && "null values not in domain!");
1212  auto It = Result.Map.find(V);
1213  if (It == Result.Map.end())
1214  return V;
1215  return static_cast<Value *>(It->second);
1216  };
1217 
1218  auto *ClonedLatch =
1219  cast<BasicBlock>(GetClonedValue(OriginalLoop.getLoopLatch()));
1220  ClonedLatch->getTerminator()->setMetadata(ClonedLoopTag,
1221  MDNode::get(Ctx, {}));
1222 
1223  Result.Structure = MainLoopStructure.map(GetClonedValue);
1224  Result.Structure.Tag = Tag;
1225 
1226  for (unsigned i = 0, e = Result.Blocks.size(); i != e; ++i) {
1227  BasicBlock *ClonedBB = Result.Blocks[i];
1228  BasicBlock *OriginalBB = OriginalLoop.getBlocks()[i];
1229 
1230  assert(Result.Map[OriginalBB] == ClonedBB && "invariant!");
1231 
1232  for (Instruction &I : *ClonedBB)
1233  RemapInstruction(&I, Result.Map,
1235 
1236  // Exit blocks will now have one more predecessor and their PHI nodes need
1237  // to be edited to reflect that. No phi nodes need to be introduced because
1238  // the loop is in LCSSA.
1239 
1240  for (auto *SBB : successors(OriginalBB)) {
1241  if (OriginalLoop.contains(SBB))
1242  continue; // not an exit block
1243 
1244  for (PHINode &PN : SBB->phis()) {
1245  Value *OldIncoming = PN.getIncomingValueForBlock(OriginalBB);
1246  PN.addIncoming(GetClonedValue(OldIncoming), ClonedBB);
1247  }
1248  }
1249  }
1250 }
1251 
1252 LoopConstrainer::RewrittenRangeInfo LoopConstrainer::changeIterationSpaceEnd(
1253  const LoopStructure &LS, BasicBlock *Preheader, Value *ExitSubloopAt,
1254  BasicBlock *ContinuationBlock) const {
1255  // We start with a loop with a single latch:
1256  //
1257  // +--------------------+
1258  // | |
1259  // | preheader |
1260  // | |
1261  // +--------+-----------+
1262  // | ----------------\
1263  // | / |
1264  // +--------v----v------+ |
1265  // | | |
1266  // | header | |
1267  // | | |
1268  // +--------------------+ |
1269  // |
1270  // ..... |
1271  // |
1272  // +--------------------+ |
1273  // | | |
1274  // | latch >----------/
1275  // | |
1276  // +-------v------------+
1277  // |
1278  // |
1279  // | +--------------------+
1280  // | | |
1281  // +---> original exit |
1282  // | |
1283  // +--------------------+
1284  //
1285  // We change the control flow to look like
1286  //
1287  //
1288  // +--------------------+
1289  // | |
1290  // | preheader >-------------------------+
1291  // | | |
1292  // +--------v-----------+ |
1293  // | /-------------+ |
1294  // | / | |
1295  // +--------v--v--------+ | |
1296  // | | | |
1297  // | header | | +--------+ |
1298  // | | | | | |
1299  // +--------------------+ | | +-----v-----v-----------+
1300  // | | | |
1301  // | | | .pseudo.exit |
1302  // | | | |
1303  // | | +-----------v-----------+
1304  // | | |
1305  // ..... | | |
1306  // | | +--------v-------------+
1307  // +--------------------+ | | | |
1308  // | | | | | ContinuationBlock |
1309  // | latch >------+ | | |
1310  // | | | +----------------------+
1311  // +---------v----------+ |
1312  // | |
1313  // | |
1314  // | +---------------^-----+
1315  // | | |
1316  // +-----> .exit.selector |
1317  // | |
1318  // +----------v----------+
1319  // |
1320  // +--------------------+ |
1321  // | | |
1322  // | original exit <----+
1323  // | |
1324  // +--------------------+
1325 
1326  RewrittenRangeInfo RRI;
1327 
1328  BasicBlock *BBInsertLocation = LS.Latch->getNextNode();
1329  RRI.ExitSelector = BasicBlock::Create(Ctx, Twine(LS.Tag) + ".exit.selector",
1330  &F, BBInsertLocation);
1331  RRI.PseudoExit = BasicBlock::Create(Ctx, Twine(LS.Tag) + ".pseudo.exit", &F,
1332  BBInsertLocation);
1333 
1334  BranchInst *PreheaderJump = cast<BranchInst>(Preheader->getTerminator());
1335  bool Increasing = LS.IndVarIncreasing;
1336  bool IsSignedPredicate = LS.IsSignedPredicate;
1337 
1338  IRBuilder<> B(PreheaderJump);
1339 
1340  // EnterLoopCond - is it okay to start executing this `LS'?
1341  Value *EnterLoopCond = nullptr;
1342  if (Increasing)
1343  EnterLoopCond = IsSignedPredicate
1344  ? B.CreateICmpSLT(LS.IndVarStart, ExitSubloopAt)
1345  : B.CreateICmpULT(LS.IndVarStart, ExitSubloopAt);
1346  else
1347  EnterLoopCond = IsSignedPredicate
1348  ? B.CreateICmpSGT(LS.IndVarStart, ExitSubloopAt)
1349  : B.CreateICmpUGT(LS.IndVarStart, ExitSubloopAt);
1350 
1351  B.CreateCondBr(EnterLoopCond, LS.Header, RRI.PseudoExit);
1352  PreheaderJump->eraseFromParent();
1353 
1354  LS.LatchBr->setSuccessor(LS.LatchBrExitIdx, RRI.ExitSelector);
1355  B.SetInsertPoint(LS.LatchBr);
1356  Value *TakeBackedgeLoopCond = nullptr;
1357  if (Increasing)
1358  TakeBackedgeLoopCond = IsSignedPredicate
1359  ? B.CreateICmpSLT(LS.IndVarBase, ExitSubloopAt)
1360  : B.CreateICmpULT(LS.IndVarBase, ExitSubloopAt);
1361  else
1362  TakeBackedgeLoopCond = IsSignedPredicate
1363  ? B.CreateICmpSGT(LS.IndVarBase, ExitSubloopAt)
1364  : B.CreateICmpUGT(LS.IndVarBase, ExitSubloopAt);
1365  Value *CondForBranch = LS.LatchBrExitIdx == 1
1366  ? TakeBackedgeLoopCond
1367  : B.CreateNot(TakeBackedgeLoopCond);
1368 
1369  LS.LatchBr->setCondition(CondForBranch);
1370 
1371  B.SetInsertPoint(RRI.ExitSelector);
1372 
1373  // IterationsLeft - are there any more iterations left, given the original
1374  // upper bound on the induction variable? If not, we branch to the "real"
1375  // exit.
1376  Value *IterationsLeft = nullptr;
1377  if (Increasing)
1378  IterationsLeft = IsSignedPredicate
1379  ? B.CreateICmpSLT(LS.IndVarBase, LS.LoopExitAt)
1380  : B.CreateICmpULT(LS.IndVarBase, LS.LoopExitAt);
1381  else
1382  IterationsLeft = IsSignedPredicate
1383  ? B.CreateICmpSGT(LS.IndVarBase, LS.LoopExitAt)
1384  : B.CreateICmpUGT(LS.IndVarBase, LS.LoopExitAt);
1385  B.CreateCondBr(IterationsLeft, RRI.PseudoExit, LS.LatchExit);
1386 
1387  BranchInst *BranchToContinuation =
1388  BranchInst::Create(ContinuationBlock, RRI.PseudoExit);
1389 
1390  // We emit PHI nodes into `RRI.PseudoExit' that compute the "latest" value of
1391  // each of the PHI nodes in the loop header. This feeds into the initial
1392  // value of the same PHI nodes if/when we continue execution.
1393  for (PHINode &PN : LS.Header->phis()) {
1394  PHINode *NewPHI = PHINode::Create(PN.getType(), 2, PN.getName() + ".copy",
1395  BranchToContinuation);
1396 
1397  NewPHI->addIncoming(PN.getIncomingValueForBlock(Preheader), Preheader);
1398  NewPHI->addIncoming(PN.getIncomingValueForBlock(LS.Latch),
1399  RRI.ExitSelector);
1400  RRI.PHIValuesAtPseudoExit.push_back(NewPHI);
1401  }
1402 
1403  RRI.IndVarEnd = PHINode::Create(LS.IndVarBase->getType(), 2, "indvar.end",
1404  BranchToContinuation);
1405  RRI.IndVarEnd->addIncoming(LS.IndVarStart, Preheader);
1406  RRI.IndVarEnd->addIncoming(LS.IndVarBase, RRI.ExitSelector);
1407 
1408  // The latch exit now has a branch from `RRI.ExitSelector' instead of
1409  // `LS.Latch'. The PHI nodes need to be updated to reflect that.
1410  for (PHINode &PN : LS.LatchExit->phis())
1411  replacePHIBlock(&PN, LS.Latch, RRI.ExitSelector);
1412 
1413  return RRI;
1414 }
1415 
1416 void LoopConstrainer::rewriteIncomingValuesForPHIs(
1417  LoopStructure &LS, BasicBlock *ContinuationBlock,
1418  const LoopConstrainer::RewrittenRangeInfo &RRI) const {
1419  unsigned PHIIndex = 0;
1420  for (PHINode &PN : LS.Header->phis())
1421  for (unsigned i = 0, e = PN.getNumIncomingValues(); i < e; ++i)
1422  if (PN.getIncomingBlock(i) == ContinuationBlock)
1423  PN.setIncomingValue(i, RRI.PHIValuesAtPseudoExit[PHIIndex++]);
1424 
1425  LS.IndVarStart = RRI.IndVarEnd;
1426 }
1427 
1428 BasicBlock *LoopConstrainer::createPreheader(const LoopStructure &LS,
1429  BasicBlock *OldPreheader,
1430  const char *Tag) const {
1431  BasicBlock *Preheader = BasicBlock::Create(Ctx, Tag, &F, LS.Header);
1432  BranchInst::Create(LS.Header, Preheader);
1433 
1434  for (PHINode &PN : LS.Header->phis())
1435  for (unsigned i = 0, e = PN.getNumIncomingValues(); i < e; ++i)
1436  replacePHIBlock(&PN, OldPreheader, Preheader);
1437 
1438  return Preheader;
1439 }
1440 
1441 void LoopConstrainer::addToParentLoopIfNeeded(ArrayRef<BasicBlock *> BBs) {
1442  Loop *ParentLoop = OriginalLoop.getParentLoop();
1443  if (!ParentLoop)
1444  return;
1445 
1446  for (BasicBlock *BB : BBs)
1447  ParentLoop->addBasicBlockToLoop(BB, LI);
1448 }
1449 
1450 Loop *LoopConstrainer::createClonedLoopStructure(Loop *Original, Loop *Parent,
1451  ValueToValueMapTy &VM,
1452  bool IsSubloop) {
1453  Loop &New = *LI.AllocateLoop();
1454  if (Parent)
1455  Parent->addChildLoop(&New);
1456  else
1457  LI.addTopLevelLoop(&New);
1458  LPMAddNewLoop(&New, IsSubloop);
1459 
1460  // Add all of the blocks in Original to the new loop.
1461  for (auto *BB : Original->blocks())
1462  if (LI.getLoopFor(BB) == Original)
1463  New.addBasicBlockToLoop(cast<BasicBlock>(VM[BB]), LI);
1464 
1465  // Add all of the subloops to the new loop.
1466  for (Loop *SubLoop : *Original)
1467  createClonedLoopStructure(SubLoop, &New, VM, /* IsSubloop */ true);
1468 
1469  return &New;
1470 }
1471 
1472 bool LoopConstrainer::run() {
1473  BasicBlock *Preheader = nullptr;
1474  LatchTakenCount = SE.getExitCount(&OriginalLoop, MainLoopStructure.Latch);
1475  Preheader = OriginalLoop.getLoopPreheader();
1476  assert(!isa<SCEVCouldNotCompute>(LatchTakenCount) && Preheader != nullptr &&
1477  "preconditions!");
1478 
1479  OriginalPreheader = Preheader;
1480  MainLoopPreheader = Preheader;
1481 
1482  bool IsSignedPredicate = MainLoopStructure.IsSignedPredicate;
1483  Optional<SubRanges> MaybeSR = calculateSubRanges(IsSignedPredicate);
1484  if (!MaybeSR.hasValue()) {
1485  LLVM_DEBUG(dbgs() << "irce: could not compute subranges\n");
1486  return false;
1487  }
1488 
1489  SubRanges SR = MaybeSR.getValue();
1490  bool Increasing = MainLoopStructure.IndVarIncreasing;
1491  IntegerType *IVTy =
1492  cast<IntegerType>(MainLoopStructure.IndVarBase->getType());
1493 
1494  SCEVExpander Expander(SE, F.getParent()->getDataLayout(), "irce");
1495  Instruction *InsertPt = OriginalPreheader->getTerminator();
1496 
1497  // It would have been better to make `PreLoop' and `PostLoop'
1498  // `Optional<ClonedLoop>'s, but `ValueToValueMapTy' does not have a copy
1499  // constructor.
1500  ClonedLoop PreLoop, PostLoop;
1501  bool NeedsPreLoop =
1502  Increasing ? SR.LowLimit.hasValue() : SR.HighLimit.hasValue();
1503  bool NeedsPostLoop =
1504  Increasing ? SR.HighLimit.hasValue() : SR.LowLimit.hasValue();
1505 
1506  Value *ExitPreLoopAt = nullptr;
1507  Value *ExitMainLoopAt = nullptr;
1508  const SCEVConstant *MinusOneS =
1509  cast<SCEVConstant>(SE.getConstant(IVTy, -1, true /* isSigned */));
1510 
1511  if (NeedsPreLoop) {
1512  const SCEV *ExitPreLoopAtSCEV = nullptr;
1513 
1514  if (Increasing)
1515  ExitPreLoopAtSCEV = *SR.LowLimit;
1516  else {
1517  if (CannotBeMinInLoop(*SR.HighLimit, &OriginalLoop, SE,
1518  IsSignedPredicate))
1519  ExitPreLoopAtSCEV = SE.getAddExpr(*SR.HighLimit, MinusOneS);
1520  else {
1521  LLVM_DEBUG(dbgs() << "irce: could not prove no-overflow when computing "
1522  << "preloop exit limit. HighLimit = "
1523  << *(*SR.HighLimit) << "\n");
1524  return false;
1525  }
1526  }
1527 
1528  if (!isSafeToExpandAt(ExitPreLoopAtSCEV, InsertPt, SE)) {
1529  LLVM_DEBUG(dbgs() << "irce: could not prove that it is safe to expand the"
1530  << " preloop exit limit " << *ExitPreLoopAtSCEV
1531  << " at block " << InsertPt->getParent()->getName()
1532  << "\n");
1533  return false;
1534  }
1535 
1536  ExitPreLoopAt = Expander.expandCodeFor(ExitPreLoopAtSCEV, IVTy, InsertPt);
1537  ExitPreLoopAt->setName("exit.preloop.at");
1538  }
1539 
1540  if (NeedsPostLoop) {
1541  const SCEV *ExitMainLoopAtSCEV = nullptr;
1542 
1543  if (Increasing)
1544  ExitMainLoopAtSCEV = *SR.HighLimit;
1545  else {
1546  if (CannotBeMinInLoop(*SR.LowLimit, &OriginalLoop, SE,
1547  IsSignedPredicate))
1548  ExitMainLoopAtSCEV = SE.getAddExpr(*SR.LowLimit, MinusOneS);
1549  else {
1550  LLVM_DEBUG(dbgs() << "irce: could not prove no-overflow when computing "
1551  << "mainloop exit limit. LowLimit = "
1552  << *(*SR.LowLimit) << "\n");
1553  return false;
1554  }
1555  }
1556 
1557  if (!isSafeToExpandAt(ExitMainLoopAtSCEV, InsertPt, SE)) {
1558  LLVM_DEBUG(dbgs() << "irce: could not prove that it is safe to expand the"
1559  << " main loop exit limit " << *ExitMainLoopAtSCEV
1560  << " at block " << InsertPt->getParent()->getName()
1561  << "\n");
1562  return false;
1563  }
1564 
1565  ExitMainLoopAt = Expander.expandCodeFor(ExitMainLoopAtSCEV, IVTy, InsertPt);
1566  ExitMainLoopAt->setName("exit.mainloop.at");
1567  }
1568 
1569  // We clone these ahead of time so that we don't have to deal with changing
1570  // and temporarily invalid IR as we transform the loops.
1571  if (NeedsPreLoop)
1572  cloneLoop(PreLoop, "preloop");
1573  if (NeedsPostLoop)
1574  cloneLoop(PostLoop, "postloop");
1575 
1576  RewrittenRangeInfo PreLoopRRI;
1577 
1578  if (NeedsPreLoop) {
1579  Preheader->getTerminator()->replaceUsesOfWith(MainLoopStructure.Header,
1580  PreLoop.Structure.Header);
1581 
1582  MainLoopPreheader =
1583  createPreheader(MainLoopStructure, Preheader, "mainloop");
1584  PreLoopRRI = changeIterationSpaceEnd(PreLoop.Structure, Preheader,
1585  ExitPreLoopAt, MainLoopPreheader);
1586  rewriteIncomingValuesForPHIs(MainLoopStructure, MainLoopPreheader,
1587  PreLoopRRI);
1588  }
1589 
1590  BasicBlock *PostLoopPreheader = nullptr;
1591  RewrittenRangeInfo PostLoopRRI;
1592 
1593  if (NeedsPostLoop) {
1594  PostLoopPreheader =
1595  createPreheader(PostLoop.Structure, Preheader, "postloop");
1596  PostLoopRRI = changeIterationSpaceEnd(MainLoopStructure, MainLoopPreheader,
1597  ExitMainLoopAt, PostLoopPreheader);
1598  rewriteIncomingValuesForPHIs(PostLoop.Structure, PostLoopPreheader,
1599  PostLoopRRI);
1600  }
1601 
1602  BasicBlock *NewMainLoopPreheader =
1603  MainLoopPreheader != Preheader ? MainLoopPreheader : nullptr;
1604  BasicBlock *NewBlocks[] = {PostLoopPreheader, PreLoopRRI.PseudoExit,
1605  PreLoopRRI.ExitSelector, PostLoopRRI.PseudoExit,
1606  PostLoopRRI.ExitSelector, NewMainLoopPreheader};
1607 
1608  // Some of the above may be nullptr, filter them out before passing to
1609  // addToParentLoopIfNeeded.
1610  auto NewBlocksEnd =
1611  std::remove(std::begin(NewBlocks), std::end(NewBlocks), nullptr);
1612 
1613  addToParentLoopIfNeeded(makeArrayRef(std::begin(NewBlocks), NewBlocksEnd));
1614 
1615  DT.recalculate(F);
1616 
1617  // We need to first add all the pre and post loop blocks into the loop
1618  // structures (as part of createClonedLoopStructure), and then update the
1619  // LCSSA form and LoopSimplifyForm. This is necessary for correctly updating
1620  // LI when LoopSimplifyForm is generated.
1621  Loop *PreL = nullptr, *PostL = nullptr;
1622  if (!PreLoop.Blocks.empty()) {
1623  PreL = createClonedLoopStructure(&OriginalLoop,
1624  OriginalLoop.getParentLoop(), PreLoop.Map,
1625  /* IsSubLoop */ false);
1626  }
1627 
1628  if (!PostLoop.Blocks.empty()) {
1629  PostL =
1630  createClonedLoopStructure(&OriginalLoop, OriginalLoop.getParentLoop(),
1631  PostLoop.Map, /* IsSubLoop */ false);
1632  }
1633 
1634  // This function canonicalizes the loop into Loop-Simplify and LCSSA forms.
1635  auto CanonicalizeLoop = [&] (Loop *L, bool IsOriginalLoop) {
1636  formLCSSARecursively(*L, DT, &LI, &SE);
1637  simplifyLoop(L, &DT, &LI, &SE, nullptr, true);
1638  // Pre/post loops are slow paths, we do not need to perform any loop
1639  // optimizations on them.
1640  if (!IsOriginalLoop)
1642  };
1643  if (PreL)
1644  CanonicalizeLoop(PreL, false);
1645  if (PostL)
1646  CanonicalizeLoop(PostL, false);
1647  CanonicalizeLoop(&OriginalLoop, true);
1648 
1649  return true;
1650 }
1651 
1652 /// Computes and returns a range of values for the induction variable (IndVar)
1653 /// in which the range check can be safely elided. If it cannot compute such a
1654 /// range, returns None.
1656 InductiveRangeCheck::computeSafeIterationSpace(
1657  ScalarEvolution &SE, const SCEVAddRecExpr *IndVar,
1658  bool IsLatchSigned) const {
1659  // IndVar is of the form "A + B * I" (where "I" is the canonical induction
1660  // variable, that may or may not exist as a real llvm::Value in the loop) and
1661  // this inductive range check is a range check on the "C + D * I" ("C" is
1662  // getBegin() and "D" is getStep()). We rewrite the value being range
1663  // checked to "M + N * IndVar" where "N" = "D * B^(-1)" and "M" = "C - NA".
1664  //
1665  // The actual inequalities we solve are of the form
1666  //
1667  // 0 <= M + 1 * IndVar < L given L >= 0 (i.e. N == 1)
1668  //
1669  // Here L stands for upper limit of the safe iteration space.
1670  // The inequality is satisfied by (0 - M) <= IndVar < (L - M). To avoid
1671  // overflows when calculating (0 - M) and (L - M) we, depending on type of
1672  // IV's iteration space, limit the calculations by borders of the iteration
1673  // space. For example, if IndVar is unsigned, (0 - M) overflows for any M > 0.
1674  // If we figured out that "anything greater than (-M) is safe", we strengthen
1675  // this to "everything greater than 0 is safe", assuming that values between
1676  // -M and 0 just do not exist in unsigned iteration space, and we don't want
1677  // to deal with overflown values.
1678 
1679  if (!IndVar->isAffine())
1680  return None;
1681 
1682  const SCEV *A = IndVar->getStart();
1683  const SCEVConstant *B = dyn_cast<SCEVConstant>(IndVar->getStepRecurrence(SE));
1684  if (!B)
1685  return None;
1686  assert(!B->isZero() && "Recurrence with zero step?");
1687 
1688  const SCEV *C = getBegin();
1689  const SCEVConstant *D = dyn_cast<SCEVConstant>(getStep());
1690  if (D != B)
1691  return None;
1692 
1693  assert(!D->getValue()->isZero() && "Recurrence with zero step?");
1694  unsigned BitWidth = cast<IntegerType>(IndVar->getType())->getBitWidth();
1695  const SCEV *SIntMax = SE.getConstant(APInt::getSignedMaxValue(BitWidth));
1696 
1697  // Subtract Y from X so that it does not go through border of the IV
1698  // iteration space. Mathematically, it is equivalent to:
1699  //
1700  // ClampedSubtract(X, Y) = min(max(X - Y, INT_MIN), INT_MAX). [1]
1701  //
1702  // In [1], 'X - Y' is a mathematical subtraction (result is not bounded to
1703  // any width of bit grid). But after we take min/max, the result is
1704  // guaranteed to be within [INT_MIN, INT_MAX].
1705  //
1706  // In [1], INT_MAX and INT_MIN are respectively signed and unsigned max/min
1707  // values, depending on type of latch condition that defines IV iteration
1708  // space.
1709  auto ClampedSubtract = [&](const SCEV *X, const SCEV *Y) {
1710  // FIXME: The current implementation assumes that X is in [0, SINT_MAX].
1711  // This is required to ensure that SINT_MAX - X does not overflow signed and
1712  // that X - Y does not overflow unsigned if Y is negative. Can we lift this
1713  // restriction and make it work for negative X either?
1714  if (IsLatchSigned) {
1715  // X is a number from signed range, Y is interpreted as signed.
1716  // Even if Y is SINT_MAX, (X - Y) does not reach SINT_MIN. So the only
1717  // thing we should care about is that we didn't cross SINT_MAX.
1718  // So, if Y is positive, we subtract Y safely.
1719  // Rule 1: Y > 0 ---> Y.
1720  // If 0 <= -Y <= (SINT_MAX - X), we subtract Y safely.
1721  // Rule 2: Y >=s (X - SINT_MAX) ---> Y.
1722  // If 0 <= (SINT_MAX - X) < -Y, we can only subtract (X - SINT_MAX).
1723  // Rule 3: Y <s (X - SINT_MAX) ---> (X - SINT_MAX).
1724  // It gives us smax(Y, X - SINT_MAX) to subtract in all cases.
1725  const SCEV *XMinusSIntMax = SE.getMinusSCEV(X, SIntMax);
1726  return SE.getMinusSCEV(X, SE.getSMaxExpr(Y, XMinusSIntMax),
1727  SCEV::FlagNSW);
1728  } else
1729  // X is a number from unsigned range, Y is interpreted as signed.
1730  // Even if Y is SINT_MIN, (X - Y) does not reach UINT_MAX. So the only
1731  // thing we should care about is that we didn't cross zero.
1732  // So, if Y is negative, we subtract Y safely.
1733  // Rule 1: Y <s 0 ---> Y.
1734  // If 0 <= Y <= X, we subtract Y safely.
1735  // Rule 2: Y <=s X ---> Y.
1736  // If 0 <= X < Y, we should stop at 0 and can only subtract X.
1737  // Rule 3: Y >s X ---> X.
1738  // It gives us smin(X, Y) to subtract in all cases.
1739  return SE.getMinusSCEV(X, SE.getSMinExpr(X, Y), SCEV::FlagNUW);
1740  };
1741  const SCEV *M = SE.getMinusSCEV(C, A);
1742  const SCEV *Zero = SE.getZero(M->getType());
1743 
1744  // This function returns SCEV equal to 1 if X is non-negative 0 otherwise.
1745  auto SCEVCheckNonNegative = [&](const SCEV *X) {
1746  const Loop *L = IndVar->getLoop();
1747  const SCEV *One = SE.getOne(X->getType());
1748  // Can we trivially prove that X is a non-negative or negative value?
1749  if (isKnownNonNegativeInLoop(X, L, SE))
1750  return One;
1751  else if (isKnownNegativeInLoop(X, L, SE))
1752  return Zero;
1753  // If not, we will have to figure it out during the execution.
1754  // Function smax(smin(X, 0), -1) + 1 equals to 1 if X >= 0 and 0 if X < 0.
1755  const SCEV *NegOne = SE.getNegativeSCEV(One);
1756  return SE.getAddExpr(SE.getSMaxExpr(SE.getSMinExpr(X, Zero), NegOne), One);
1757  };
1758  // FIXME: Current implementation of ClampedSubtract implicitly assumes that
1759  // X is non-negative (in sense of a signed value). We need to re-implement
1760  // this function in a way that it will correctly handle negative X as well.
1761  // We use it twice: for X = 0 everything is fine, but for X = getEnd() we can
1762  // end up with a negative X and produce wrong results. So currently we ensure
1763  // that if getEnd() is negative then both ends of the safe range are zero.
1764  // Note that this may pessimize elimination of unsigned range checks against
1765  // negative values.
1766  const SCEV *REnd = getEnd();
1767  const SCEV *EndIsNonNegative = SCEVCheckNonNegative(REnd);
1768 
1769  const SCEV *Begin = SE.getMulExpr(ClampedSubtract(Zero, M), EndIsNonNegative);
1770  const SCEV *End = SE.getMulExpr(ClampedSubtract(REnd, M), EndIsNonNegative);
1771  return InductiveRangeCheck::Range(Begin, End);
1772 }
1773 
1777  const InductiveRangeCheck::Range &R2) {
1778  if (R2.isEmpty(SE, /* IsSigned */ true))
1779  return None;
1780  if (!R1.hasValue())
1781  return R2;
1782  auto &R1Value = R1.getValue();
1783  // We never return empty ranges from this function, and R1 is supposed to be
1784  // a result of intersection. Thus, R1 is never empty.
1785  assert(!R1Value.isEmpty(SE, /* IsSigned */ true) &&
1786  "We should never have empty R1!");
1787 
1788  // TODO: we could widen the smaller range and have this work; but for now we
1789  // bail out to keep things simple.
1790  if (R1Value.getType() != R2.getType())
1791  return None;
1792 
1793  const SCEV *NewBegin = SE.getSMaxExpr(R1Value.getBegin(), R2.getBegin());
1794  const SCEV *NewEnd = SE.getSMinExpr(R1Value.getEnd(), R2.getEnd());
1795 
1796  // If the resulting range is empty, just return None.
1797  auto Ret = InductiveRangeCheck::Range(NewBegin, NewEnd);
1798  if (Ret.isEmpty(SE, /* IsSigned */ true))
1799  return None;
1800  return Ret;
1801 }
1802 
1806  const InductiveRangeCheck::Range &R2) {
1807  if (R2.isEmpty(SE, /* IsSigned */ false))
1808  return None;
1809  if (!R1.hasValue())
1810  return R2;
1811  auto &R1Value = R1.getValue();
1812  // We never return empty ranges from this function, and R1 is supposed to be
1813  // a result of intersection. Thus, R1 is never empty.
1814  assert(!R1Value.isEmpty(SE, /* IsSigned */ false) &&
1815  "We should never have empty R1!");
1816 
1817  // TODO: we could widen the smaller range and have this work; but for now we
1818  // bail out to keep things simple.
1819  if (R1Value.getType() != R2.getType())
1820  return None;
1821 
1822  const SCEV *NewBegin = SE.getUMaxExpr(R1Value.getBegin(), R2.getBegin());
1823  const SCEV *NewEnd = SE.getUMinExpr(R1Value.getEnd(), R2.getEnd());
1824 
1825  // If the resulting range is empty, just return None.
1826  auto Ret = InductiveRangeCheck::Range(NewBegin, NewEnd);
1827  if (Ret.isEmpty(SE, /* IsSigned */ false))
1828  return None;
1829  return Ret;
1830 }
1831 
1834  LPMUpdater &U) {
1835  Function *F = L.getHeader()->getParent();
1836  const auto &FAM =
1837  AM.getResult<FunctionAnalysisManagerLoopProxy>(L, AR).getManager();
1838  auto *BPI = FAM.getCachedResult<BranchProbabilityAnalysis>(*F);
1839  InductiveRangeCheckElimination IRCE(AR.SE, BPI, AR.DT, AR.LI);
1840  auto LPMAddNewLoop = [&U](Loop *NL, bool IsSubloop) {
1841  if (!IsSubloop)
1842  U.addSiblingLoops(NL);
1843  };
1844  bool Changed = IRCE.run(&L, LPMAddNewLoop);
1845  if (!Changed)
1846  return PreservedAnalyses::all();
1847 
1849 }
1850 
1851 bool IRCELegacyPass::runOnLoop(Loop *L, LPPassManager &LPM) {
1852  if (skipLoop(L))
1853  return false;
1854 
1855  ScalarEvolution &SE = getAnalysis<ScalarEvolutionWrapperPass>().getSE();
1856  BranchProbabilityInfo &BPI =
1857  getAnalysis<BranchProbabilityInfoWrapperPass>().getBPI();
1858  auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
1859  auto &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
1860  InductiveRangeCheckElimination IRCE(SE, &BPI, DT, LI);
1861  auto LPMAddNewLoop = [&LPM](Loop *NL, bool /* IsSubLoop */) {
1862  LPM.addLoop(*NL);
1863  };
1864  return IRCE.run(L, LPMAddNewLoop);
1865 }
1866 
1867 bool InductiveRangeCheckElimination::run(
1868  Loop *L, function_ref<void(Loop *, bool)> LPMAddNewLoop) {
1869  if (L->getBlocks().size() >= LoopSizeCutoff) {
1870  LLVM_DEBUG(dbgs() << "irce: giving up constraining loop, too large\n");
1871  return false;
1872  }
1873 
1874  BasicBlock *Preheader = L->getLoopPreheader();
1875  if (!Preheader) {
1876  LLVM_DEBUG(dbgs() << "irce: loop has no preheader, leaving\n");
1877  return false;
1878  }
1879 
1880  LLVMContext &Context = Preheader->getContext();
1882 
1883  for (auto BBI : L->getBlocks())
1884  if (BranchInst *TBI = dyn_cast<BranchInst>(BBI->getTerminator()))
1885  InductiveRangeCheck::extractRangeChecksFromBranch(TBI, L, SE, BPI,
1886  RangeChecks);
1887 
1888  if (RangeChecks.empty())
1889  return false;
1890 
1891  auto PrintRecognizedRangeChecks = [&](raw_ostream &OS) {
1892  OS << "irce: looking at loop "; L->print(OS);
1893  OS << "irce: loop has " << RangeChecks.size()
1894  << " inductive range checks: \n";
1895  for (InductiveRangeCheck &IRC : RangeChecks)
1896  IRC.print(OS);
1897  };
1898 
1899  LLVM_DEBUG(PrintRecognizedRangeChecks(dbgs()));
1900 
1901  if (PrintRangeChecks)
1902  PrintRecognizedRangeChecks(errs());
1903 
1904  const char *FailureReason = nullptr;
1905  Optional<LoopStructure> MaybeLoopStructure =
1906  LoopStructure::parseLoopStructure(SE, BPI, *L, FailureReason);
1907  if (!MaybeLoopStructure.hasValue()) {
1908  LLVM_DEBUG(dbgs() << "irce: could not parse loop structure: "
1909  << FailureReason << "\n";);
1910  return false;
1911  }
1912  LoopStructure LS = MaybeLoopStructure.getValue();
1913  const SCEVAddRecExpr *IndVar =
1914  cast<SCEVAddRecExpr>(SE.getMinusSCEV(SE.getSCEV(LS.IndVarBase), SE.getSCEV(LS.IndVarStep)));
1915 
1917  Instruction *ExprInsertPt = Preheader->getTerminator();
1918 
1919  SmallVector<InductiveRangeCheck, 4> RangeChecksToEliminate;
1920  // Basing on the type of latch predicate, we interpret the IV iteration range
1921  // as signed or unsigned range. We use different min/max functions (signed or
1922  // unsigned) when intersecting this range with safe iteration ranges implied
1923  // by range checks.
1924  auto IntersectRange =
1925  LS.IsSignedPredicate ? IntersectSignedRange : IntersectUnsignedRange;
1926 
1927  IRBuilder<> B(ExprInsertPt);
1928  for (InductiveRangeCheck &IRC : RangeChecks) {
1929  auto Result = IRC.computeSafeIterationSpace(SE, IndVar,
1930  LS.IsSignedPredicate);
1931  if (Result.hasValue()) {
1932  auto MaybeSafeIterRange =
1933  IntersectRange(SE, SafeIterRange, Result.getValue());
1934  if (MaybeSafeIterRange.hasValue()) {
1935  assert(
1936  !MaybeSafeIterRange.getValue().isEmpty(SE, LS.IsSignedPredicate) &&
1937  "We should never return empty ranges!");
1938  RangeChecksToEliminate.push_back(IRC);
1939  SafeIterRange = MaybeSafeIterRange.getValue();
1940  }
1941  }
1942  }
1943 
1944  if (!SafeIterRange.hasValue())
1945  return false;
1946 
1947  LoopConstrainer LC(*L, LI, LPMAddNewLoop, LS, SE, DT,
1948  SafeIterRange.getValue());
1949  bool Changed = LC.run();
1950 
1951  if (Changed) {
1952  auto PrintConstrainedLoopInfo = [L]() {
1953  dbgs() << "irce: in function ";
1954  dbgs() << L->getHeader()->getParent()->getName() << ": ";
1955  dbgs() << "constrained ";
1956  L->print(dbgs());
1957  };
1958 
1959  LLVM_DEBUG(PrintConstrainedLoopInfo());
1960 
1961  if (PrintChangedLoops)
1962  PrintConstrainedLoopInfo();
1963 
1964  // Optimize away the now-redundant range checks.
1965 
1966  for (InductiveRangeCheck &IRC : RangeChecksToEliminate) {
1967  ConstantInt *FoldedRangeCheck = IRC.getPassingDirection()
1968  ? ConstantInt::getTrue(Context)
1969  : ConstantInt::getFalse(Context);
1970  IRC.getCheckUse()->set(FoldedRangeCheck);
1971  }
1972  }
1973 
1974  return Changed;
1975 }
1976 
1978  return new IRCELegacyPass();
1979 }
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
const NoneType None
Definition: None.h:24
BinaryOp_match< LHS, RHS, Instruction::And > m_And(const LHS &L, const RHS &R)
Definition: PatternMatch.h:718
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:68
A parsed version of the target data layout string in and methods for querying it. ...
Definition: DataLayout.h:111
const_iterator end(StringRef path)
Get end iterator over path.
Definition: Path.cpp:259
static ConstantInt * getFalse(LLVMContext &Context)
Definition: Constants.cpp:584
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:842
class_match< Value > m_Value()
Match an arbitrary value and ignore it.
Definition: PatternMatch.h:72
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
static bool CannotBeMinInLoop(const SCEV *BoundSCEV, Loop *L, ScalarEvolution &SE, bool Signed)
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:225
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
GCNRegPressure max(const GCNRegPressure &P1, const GCNRegPressure &P2)
LLVMContext & Context
PreservedAnalyses getLoopPassPreservedAnalyses()
Returns the minimum set of Analyses that all loop passes must preserve.
const_iterator begin(StringRef path, Style style=Style::native)
Get begin iterator over path.
Definition: Path.cpp:250
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:687
const SCEV * getConstant(ConstantInt *V)
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
Value * CreateICmpULT(Value *LHS, Value *RHS, const Twine &Name="")
Definition: IRBuilder.h:1752
bool isSafeToExpandAt(const SCEV *S, const Instruction *InsertionPoint, ScalarEvolution &SE)
Return true if the given expression is safe to expand in the sense that all materialized values are d...
void replaceOperandWith(unsigned I, Metadata *New)
Replace a specific operand.
Definition: Metadata.cpp:859
static MDString * get(LLVMContext &Context, StringRef Str)
Definition: Metadata.cpp:454
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:1768
bool isZero() const
Return true if the expression is a constant zero.
This file contains the declarations for metadata subclasses.
BlockT * getLoopPreheader() const
If there is a preheader for this loop, return it.
Definition: LoopInfoImpl.h:174
unsigned less or equal
Definition: InstrTypes.h:911
static cl::opt< bool > AllowUnsignedLatchCondition("irce-allow-unsigned-latch", cl::Hidden, cl::init(true))
unsigned less than
Definition: InstrTypes.h:910
static Optional< InductiveRangeCheck::Range > IntersectSignedRange(ScalarEvolution &SE, const Optional< InductiveRangeCheck::Range > &R1, const InductiveRangeCheck::Range &R2)
bool isAvailableAtLoopEntry(const SCEV *S, const Loop *L)
Determine if the SCEV can be evaluated at loop&#39;s entry.
An efficient, type-erasing, non-owning reference to a callable.
Definition: STLExtras.h:107
const Use & getOperandUse(unsigned i) const
Definition: User.h:183
bool isLoopInvariant(const SCEV *S, const Loop *L)
Return true if the value of the given SCEV is unchanging in the specified loop.
static bool isEquality(Predicate P)
Return true if this predicate is either EQ or NE.
BasicBlock * getSuccessor(unsigned i) const
Metadata node.
Definition: Metadata.h:862
The adaptor from a function pass to a loop pass computes these analyses and makes them available to t...
F(f)
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds...
Definition: Compiler.h:452
#define R2(n)
Value * getCondition() const
This defines the Use class.
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:535
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:393
Value * CreateNot(Value *V, const Twine &Name="")
Definition: IRBuilder.h:1282
const SCEV * getZero(Type *Ty)
Return a SCEV for the constant 0 of a specific type.
bool formLCSSARecursively(Loop &L, DominatorTree &DT, LoopInfo *LI, ScalarEvolution *SE)
Put a loop nest into LCSSA form.
Definition: LCSSA.cpp:344
The SCEV is loop-invariant.
static GCMetadataPrinterRegistry::Add< OcamlGCMetadataPrinter > Y("ocaml", "ocaml 3.10-compatible collector")
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 if the function does no...
Definition: BasicBlock.cpp:134
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:51
bool isSigned() const
Definition: InstrTypes.h:1054
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
INITIALIZE_PASS_BEGIN(IRCELegacyPass, "irce", "Inductive range check elimination", false, false) INITIALIZE_PASS_END(IRCELegacyPass
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:731
void setName(const Twine &Name)
Change the name of the value.
Definition: Value.cpp:295
Value * CreateICmpSGT(Value *LHS, Value *RHS, const Twine &Name="")
Definition: IRBuilder.h:1760
static cl::opt< int > MaxExitProbReciprocal("irce-max-exit-prob-reciprocal", cl::Hidden, cl::init(10))
This file implements a class to represent arbitrary precision integral constant values and operations...
BlockT * getHeader() const
Definition: LoopInfo.h:100
Analysis pass which computes BranchProbabilityInfo.
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 bool CannotBeMaxInLoop(const SCEV *BoundSCEV, Loop *L, ScalarEvolution &SE, bool Signed)
static void DisableAllLoopOptsOnLoop(Loop &L)
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:245
void addBasicBlockToLoop(BlockT *NewBB, LoopInfoBase< BlockT, LoopT > &LI)
This method is used by other analyses to update loop information.
Definition: LoopInfoImpl.h:251
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:1744
void setLoopID(MDNode *LoopID) const
Set the llvm.loop loop id metadata for this loop.
Definition: LoopInfo.cpp:250
const T & getValue() const LLVM_LVALUE_FUNCTION
Definition: Optional.h:179
Inductive range check elimination
This header provides classes for managing per-loop analyses.
MDNode * getMetadata(unsigned KindID) const
Get the metadata of given kind attached to this Instruction.
Definition: Instruction.h:200
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
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:145
void SetInsertPoint(BasicBlock *TheBB)
This specifies that created instructions should be appended to the end of the specified block...
Definition: IRBuilder.h:127
Legacy analysis pass which computes BranchProbabilityInfo.
Value * getOperand(unsigned i) const
Definition: User.h:170
If this flag is set, the remapper knows that only local values within a function (such as an instruct...
Definition: ValueMapper.h:73
void replaceUsesOfWith(Value *From, Value *To)
Replace uses of one Value with another.
Definition: User.cpp:21
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:410
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
void dump(const SparseBitVector< ElementSize > &LHS, raw_ostream &out)
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:153
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:203
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.
static StringRef getPredicateName(Predicate P)
Value * getIncomingValueForBlock(const BasicBlock *BB) const
This file contains the declarations for the subclasses of Constant, which represent the different fla...
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 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:885
Value * expandCodeFor(const SCEV *SH, Type *Ty, Instruction *I)
Insert code to directly compute the specified SCEV expression into the program.
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
static void print(raw_ostream &Out, object::Archive::Kind Kind, T Val)
Class to represent integer types.
Definition: DerivedTypes.h:40
bool isKnownNegative(const SCEV *S)
Test if the given expression is known to be negative.
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.
void addSiblingLoops(ArrayRef< Loop *> NewSibLoops)
Loop passes should use this method to indicate they have added new sibling loops to the current loop...
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:159
static bool isKnownNegativeInLoop(const SCEV *BoundSCEV, const Loop *L, ScalarEvolution &SE)
size_t size() const
Definition: SmallVector.h:53
static wasm::ValType getType(const TargetRegisterClass *RC)
const SCEV * getMulExpr(SmallVectorImpl< const SCEV *> &Ops, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
Get a canonical multiply expression, or something simpler if possible.
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:912
BranchProbability getEdgeProbability(const BasicBlock *Src, unsigned IndexInSuccessors) const
Get an edge&#39;s probability, relative to other out-edges of the Src.
static bool isSafeIncreasingBound(const SCEV *Start, const SCEV *BoundSCEV, const SCEV *Step, ICmpInst::Predicate Pred, unsigned LatchBrExitIdx, Loop *L, ScalarEvolution &SE)
Given a loop with an increasing induction variable, is it possible to safely calculate the bounds of ...
bool isNegative() const
Definition: Constants.h:188
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.
This class provides an interface for updating the loop pass manager based on mutations to the loop ne...
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)
An analysis over an "inner" IR unit that provides access to an analysis manager over a "outer" IR uni...
Definition: PassManager.h:1062
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:847
Module.h This file contains the declarations for the Module class.
signed less than
Definition: InstrTypes.h:914
static APInt getMinValue(unsigned numBits)
Gets minimum unsigned value of APInt for a specific bit width.
Definition: APInt.h:542
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:621
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:577
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:133
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:924
signed less or equal
Definition: InstrTypes.h:915
Class for arbitrary precision integers.
Definition: APInt.h:70
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 ...
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:251
This class uses information about analyze scalars to rewrite expressions in canonical form...
static APInt getMaxValue(unsigned numBits)
Gets maximum unsigned value of APInt for specific bit width.
Definition: APInt.h:530
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:91
LoopT * getParentLoop() const
Definition: LoopInfo.h:101
Predicate getPredicate() const
Return the predicate for this instruction.
Definition: InstrTypes.h:959
bool hasValue() const
Definition: Optional.h:183
bool isLoopSimplifyForm() const
Return true if the Loop is in the form that the LoopSimplify form transforms loops to...
Definition: LoopInfo.cpp:192
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:331
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:56
unsigned greater or equal
Definition: InstrTypes.h:909
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:459
ArrayRef< BlockT * > getBlocks() const
Get a list of the basic blocks which make up this loop.
Definition: LoopInfo.h:149
StringRef getName() const
Return a constant reference to the value&#39;s name.
Definition: Value.cpp:224
static bool isSigned(Value *V)
Can the given value generate sign bits.
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
void addLoop(Loop &L)
Definition: LoopPass.cpp:76
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:1227
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
static bool isSafeDecreasingBound(const SCEV *Start, const SCEV *BoundSCEV, const SCEV *Step, ICmpInst::Predicate Pred, unsigned LatchBrExitIdx, Loop *L, ScalarEvolution &SE)
Given a loop with an deccreasing induction variable, is it possible to safely calculate the bounds of...
void initializeIRCELegacyPassPass(PassRegistry &)
const unsigned Kind
static Optional< InductiveRangeCheck::Range > IntersectUnsignedRange(ScalarEvolution &SE, const Optional< InductiveRangeCheck::Range > &R1, const InductiveRangeCheck::Range &R2)
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:545
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:149
const SCEV * getSCEV(Value *V)
Return a SCEV expression for the full generality of the specified expression.
This class implements an extremely fast bulk output stream that can only output to a stream...
Definition: raw_ostream.h:46
#define LLVM_FALLTHROUGH
LLVM_FALLTHROUGH - Mark fallthrough cases in switch statements.
Definition: Compiler.h:238
unsigned greater than
Definition: InstrTypes.h:908
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:999
A container for analyses that lazily runs them and caches their results.
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...
static BranchProbability getZero()
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:138
PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM, LoopStandardAnalysisResults &AR, LPMUpdater &U)
void setIncomingValue(unsigned i, Value *V)
#define LLVM_DEBUG(X)
Definition: Debug.h:123
static bool isKnownNonNegativeInLoop(const SCEV *BoundSCEV, const Loop *L, ScalarEvolution &SE)
iterator_range< block_iterator > blocks() const
Definition: LoopInfo.h:156
NoWrapFlags getNoWrapFlags(NoWrapFlags Mask=NoWrapMask) const
Root of the metadata hierarchy.
Definition: Metadata.h:58
Pass * createInductiveRangeCheckEliminationPass()
signed greater or equal
Definition: InstrTypes.h:913
const SCEV * getSignExtendExpr(const SCEV *Op, Type *Ty, unsigned Depth=0)
const BasicBlock * getParent() const
Definition: Instruction.h:67
This class represents a constant integer value.