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