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