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