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