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