LLVM  14.0.0git
LoopPredication.cpp
Go to the documentation of this file.
1 //===-- LoopPredication.cpp - Guard based loop predication pass -----------===//
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 LoopPredication pass tries to convert loop variant range checks to loop
10 // invariant by widening checks across loop iterations. For example, it will
11 // convert
12 //
13 // for (i = 0; i < n; i++) {
14 // guard(i < len);
15 // ...
16 // }
17 //
18 // to
19 //
20 // for (i = 0; i < n; i++) {
21 // guard(n - 1 < len);
22 // ...
23 // }
24 //
25 // After this transformation the condition of the guard is loop invariant, so
26 // loop-unswitch can later unswitch the loop by this condition which basically
27 // predicates the loop by the widened condition:
28 //
29 // if (n - 1 < len)
30 // for (i = 0; i < n; i++) {
31 // ...
32 // }
33 // else
34 // deoptimize
35 //
36 // It's tempting to rely on SCEV here, but it has proven to be problematic.
37 // Generally the facts SCEV provides about the increment step of add
38 // recurrences are true if the backedge of the loop is taken, which implicitly
39 // assumes that the guard doesn't fail. Using these facts to optimize the
40 // guard results in a circular logic where the guard is optimized under the
41 // assumption that it never fails.
42 //
43 // For example, in the loop below the induction variable will be marked as nuw
44 // basing on the guard. Basing on nuw the guard predicate will be considered
45 // monotonic. Given a monotonic condition it's tempting to replace the induction
46 // variable in the condition with its value on the last iteration. But this
47 // transformation is not correct, e.g. e = 4, b = 5 breaks the loop.
48 //
49 // for (int i = b; i != e; i++)
50 // guard(i u< len)
51 //
52 // One of the ways to reason about this problem is to use an inductive proof
53 // approach. Given the loop:
54 //
55 // if (B(0)) {
56 // do {
57 // I = PHI(0, I.INC)
58 // I.INC = I + Step
59 // guard(G(I));
60 // } while (B(I));
61 // }
62 //
63 // where B(x) and G(x) are predicates that map integers to booleans, we want a
64 // loop invariant expression M such the following program has the same semantics
65 // as the above:
66 //
67 // if (B(0)) {
68 // do {
69 // I = PHI(0, I.INC)
70 // I.INC = I + Step
71 // guard(G(0) && M);
72 // } while (B(I));
73 // }
74 //
75 // One solution for M is M = forall X . (G(X) && B(X)) => G(X + Step)
76 //
77 // Informal proof that the transformation above is correct:
78 //
79 // By the definition of guards we can rewrite the guard condition to:
80 // G(I) && G(0) && M
81 //
82 // Let's prove that for each iteration of the loop:
83 // G(0) && M => G(I)
84 // And the condition above can be simplified to G(Start) && M.
85 //
86 // Induction base.
87 // G(0) && M => G(0)
88 //
89 // Induction step. Assuming G(0) && M => G(I) on the subsequent
90 // iteration:
91 //
92 // B(I) is true because it's the backedge condition.
93 // G(I) is true because the backedge is guarded by this condition.
94 //
95 // So M = forall X . (G(X) && B(X)) => G(X + Step) implies G(I + Step).
96 //
97 // Note that we can use anything stronger than M, i.e. any condition which
98 // implies M.
99 //
100 // When S = 1 (i.e. forward iterating loop), the transformation is supported
101 // when:
102 // * The loop has a single latch with the condition of the form:
103 // B(X) = latchStart + X <pred> latchLimit,
104 // where <pred> is u<, u<=, s<, or s<=.
105 // * The guard condition is of the form
106 // G(X) = guardStart + X u< guardLimit
107 //
108 // For the ult latch comparison case M is:
109 // forall X . guardStart + X u< guardLimit && latchStart + X <u latchLimit =>
110 // guardStart + X + 1 u< guardLimit
111 //
112 // The only way the antecedent can be true and the consequent can be false is
113 // if
114 // X == guardLimit - 1 - guardStart
115 // (and guardLimit is non-zero, but we won't use this latter fact).
116 // If X == guardLimit - 1 - guardStart then the second half of the antecedent is
117 // latchStart + guardLimit - 1 - guardStart u< latchLimit
118 // and its negation is
119 // latchStart + guardLimit - 1 - guardStart u>= latchLimit
120 //
121 // In other words, if
122 // latchLimit u<= latchStart + guardLimit - 1 - guardStart
123 // then:
124 // (the ranges below are written in ConstantRange notation, where [A, B) is the
125 // set for (I = A; I != B; I++ /*maywrap*/) yield(I);)
126 //
127 // forall X . guardStart + X u< guardLimit &&
128 // latchStart + X u< latchLimit =>
129 // guardStart + X + 1 u< guardLimit
130 // == forall X . guardStart + X u< guardLimit &&
131 // latchStart + X u< latchStart + guardLimit - 1 - guardStart =>
132 // guardStart + X + 1 u< guardLimit
133 // == forall X . (guardStart + X) in [0, guardLimit) &&
134 // (latchStart + X) in [0, latchStart + guardLimit - 1 - guardStart) =>
135 // (guardStart + X + 1) in [0, guardLimit)
136 // == forall X . X in [-guardStart, guardLimit - guardStart) &&
137 // X in [-latchStart, guardLimit - 1 - guardStart) =>
138 // X in [-guardStart - 1, guardLimit - guardStart - 1)
139 // == true
140 //
141 // So the widened condition is:
142 // guardStart u< guardLimit &&
143 // latchStart + guardLimit - 1 - guardStart u>= latchLimit
144 // Similarly for ule condition the widened condition is:
145 // guardStart u< guardLimit &&
146 // latchStart + guardLimit - 1 - guardStart u> latchLimit
147 // For slt condition the widened condition is:
148 // guardStart u< guardLimit &&
149 // latchStart + guardLimit - 1 - guardStart s>= latchLimit
150 // For sle condition the widened condition is:
151 // guardStart u< guardLimit &&
152 // latchStart + guardLimit - 1 - guardStart s> latchLimit
153 //
154 // When S = -1 (i.e. reverse iterating loop), the transformation is supported
155 // when:
156 // * The loop has a single latch with the condition of the form:
157 // B(X) = X <pred> latchLimit, where <pred> is u>, u>=, s>, or s>=.
158 // * The guard condition is of the form
159 // G(X) = X - 1 u< guardLimit
160 //
161 // For the ugt latch comparison case M is:
162 // forall X. X-1 u< guardLimit and X u> latchLimit => X-2 u< guardLimit
163 //
164 // The only way the antecedent can be true and the consequent can be false is if
165 // X == 1.
166 // If X == 1 then the second half of the antecedent is
167 // 1 u> latchLimit, and its negation is latchLimit u>= 1.
168 //
169 // So the widened condition is:
170 // guardStart u< guardLimit && latchLimit u>= 1.
171 // Similarly for sgt condition the widened condition is:
172 // guardStart u< guardLimit && latchLimit s>= 1.
173 // For uge condition the widened condition is:
174 // guardStart u< guardLimit && latchLimit u> 1.
175 // For sge condition the widened condition is:
176 // guardStart u< guardLimit && latchLimit s> 1.
177 //===----------------------------------------------------------------------===//
178 
180 #include "llvm/ADT/Statistic.h"
184 #include "llvm/Analysis/LoopInfo.h"
185 #include "llvm/Analysis/LoopPass.h"
186 #include "llvm/Analysis/MemorySSA.h"
190 #include "llvm/IR/Function.h"
191 #include "llvm/IR/GlobalValue.h"
192 #include "llvm/IR/IntrinsicInst.h"
193 #include "llvm/IR/Module.h"
194 #include "llvm/IR/PatternMatch.h"
195 #include "llvm/InitializePasses.h"
196 #include "llvm/Pass.h"
198 #include "llvm/Support/Debug.h"
199 #include "llvm/Transforms/Scalar.h"
204 
205 #define DEBUG_TYPE "loop-predication"
206 
207 STATISTIC(TotalConsidered, "Number of guards considered");
208 STATISTIC(TotalWidened, "Number of checks widened");
209 
210 using namespace llvm;
211 
212 static cl::opt<bool> EnableIVTruncation("loop-predication-enable-iv-truncation",
213  cl::Hidden, cl::init(true));
214 
215 static cl::opt<bool> EnableCountDownLoop("loop-predication-enable-count-down-loop",
216  cl::Hidden, cl::init(true));
217 
218 static cl::opt<bool>
219  SkipProfitabilityChecks("loop-predication-skip-profitability-checks",
220  cl::Hidden, cl::init(false));
221 
222 // This is the scale factor for the latch probability. We use this during
223 // profitability analysis to find other exiting blocks that have a much higher
224 // probability of exiting the loop instead of loop exiting via latch.
225 // This value should be greater than 1 for a sane profitability check.
227  "loop-predication-latch-probability-scale", cl::Hidden, cl::init(2.0),
228  cl::desc("scale factor for the latch probability. Value should be greater "
229  "than 1. Lower values are ignored"));
230 
232  "loop-predication-predicate-widenable-branches-to-deopt", cl::Hidden,
233  cl::desc("Whether or not we should predicate guards "
234  "expressed as widenable branches to deoptimize blocks"),
235  cl::init(true));
236 
237 namespace {
238 /// Represents an induction variable check:
239 /// icmp Pred, <induction variable>, <loop invariant limit>
240 struct LoopICmp {
241  ICmpInst::Predicate Pred;
242  const SCEVAddRecExpr *IV;
243  const SCEV *Limit;
244  LoopICmp(ICmpInst::Predicate Pred, const SCEVAddRecExpr *IV,
245  const SCEV *Limit)
246  : Pred(Pred), IV(IV), Limit(Limit) {}
247  LoopICmp() {}
248  void dump() {
249  dbgs() << "LoopICmp Pred = " << Pred << ", IV = " << *IV
250  << ", Limit = " << *Limit << "\n";
251  }
252 };
253 
254 class LoopPredication {
255  AliasAnalysis *AA;
256  DominatorTree *DT;
257  ScalarEvolution *SE;
258  LoopInfo *LI;
260  MemorySSAUpdater *MSSAU;
261 
262  Loop *L;
263  const DataLayout *DL;
264  BasicBlock *Preheader;
265  LoopICmp LatchCheck;
266 
267  bool isSupportedStep(const SCEV* Step);
268  Optional<LoopICmp> parseLoopICmp(ICmpInst *ICI);
269  Optional<LoopICmp> parseLoopLatchICmp();
270 
271  /// Return an insertion point suitable for inserting a safe to speculate
272  /// instruction whose only user will be 'User' which has operands 'Ops'. A
273  /// trivial result would be the at the User itself, but we try to return a
274  /// loop invariant location if possible.
275  Instruction *findInsertPt(Instruction *User, ArrayRef<Value*> Ops);
276  /// Same as above, *except* that this uses the SCEV definition of invariant
277  /// which is that an expression *can be made* invariant via SCEVExpander.
278  /// Thus, this version is only suitable for finding an insert point to be be
279  /// passed to SCEVExpander!
280  Instruction *findInsertPt(Instruction *User, ArrayRef<const SCEV*> Ops);
281 
282  /// Return true if the value is known to produce a single fixed value across
283  /// all iterations on which it executes. Note that this does not imply
284  /// speculation safety. That must be established separately.
285  bool isLoopInvariantValue(const SCEV* S);
286 
287  Value *expandCheck(SCEVExpander &Expander, Instruction *Guard,
288  ICmpInst::Predicate Pred, const SCEV *LHS,
289  const SCEV *RHS);
290 
291  Optional<Value *> widenICmpRangeCheck(ICmpInst *ICI, SCEVExpander &Expander,
292  Instruction *Guard);
293  Optional<Value *> widenICmpRangeCheckIncrementingLoop(LoopICmp LatchCheck,
294  LoopICmp RangeCheck,
295  SCEVExpander &Expander,
296  Instruction *Guard);
297  Optional<Value *> widenICmpRangeCheckDecrementingLoop(LoopICmp LatchCheck,
298  LoopICmp RangeCheck,
299  SCEVExpander &Expander,
300  Instruction *Guard);
301  unsigned collectChecks(SmallVectorImpl<Value *> &Checks, Value *Condition,
302  SCEVExpander &Expander, Instruction *Guard);
303  bool widenGuardConditions(IntrinsicInst *II, SCEVExpander &Expander);
304  bool widenWidenableBranchGuardConditions(BranchInst *Guard, SCEVExpander &Expander);
305  // If the loop always exits through another block in the loop, we should not
306  // predicate based on the latch check. For example, the latch check can be a
307  // very coarse grained check and there can be more fine grained exit checks
308  // within the loop. We identify such unprofitable loops through BPI.
309  bool isLoopProfitableToPredicate();
310 
311  bool predicateLoopExits(Loop *L, SCEVExpander &Rewriter);
312 
313 public:
316  MemorySSAUpdater *MSSAU)
317  : AA(AA), DT(DT), SE(SE), LI(LI), BPI(BPI), MSSAU(MSSAU){};
318  bool runOnLoop(Loop *L);
319 };
320 
321 class LoopPredicationLegacyPass : public LoopPass {
322 public:
323  static char ID;
324  LoopPredicationLegacyPass() : LoopPass(ID) {
326  }
327 
328  void getAnalysisUsage(AnalysisUsage &AU) const override {
332  }
333 
334  bool runOnLoop(Loop *L, LPPassManager &LPM) override {
335  if (skipLoop(L))
336  return false;
337  auto *SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
338  auto *LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
339  auto *DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
340  auto *MSSAWP = getAnalysisIfAvailable<MemorySSAWrapperPass>();
341  std::unique_ptr<MemorySSAUpdater> MSSAU;
342  if (MSSAWP)
343  MSSAU = std::make_unique<MemorySSAUpdater>(&MSSAWP->getMSSA());
344  BranchProbabilityInfo &BPI =
345  getAnalysis<BranchProbabilityInfoWrapperPass>().getBPI();
346  auto *AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
347  LoopPredication LP(AA, DT, SE, LI, &BPI, MSSAU ? MSSAU.get() : nullptr);
348  return LP.runOnLoop(L);
349  }
350 };
351 
353 } // end namespace
354 
355 INITIALIZE_PASS_BEGIN(LoopPredicationLegacyPass, "loop-predication",
356  "Loop predication", false, false)
359 INITIALIZE_PASS_END(LoopPredicationLegacyPass, "loop-predication",
361 
363  return new LoopPredicationLegacyPass();
364 }
365 
368  LPMUpdater &U) {
369  Function *F = L.getHeader()->getParent();
370  // For the new PM, we also can't use BranchProbabilityInfo as an analysis
371  // pass. Function analyses need to be preserved across loop transformations
372  // but BPI is not preserved, hence a newly built one is needed.
373  BranchProbabilityInfo BPI(*F, AR.LI, &AR.TLI, &AR.DT, nullptr);
374  std::unique_ptr<MemorySSAUpdater> MSSAU;
375  if (AR.MSSA)
376  MSSAU = std::make_unique<MemorySSAUpdater>(AR.MSSA);
377  LoopPredication LP(&AR.AA, &AR.DT, &AR.SE, &AR.LI, &BPI,
378  MSSAU ? MSSAU.get() : nullptr);
379  if (!LP.runOnLoop(&L))
380  return PreservedAnalyses::all();
381 
382  auto PA = getLoopPassPreservedAnalyses();
383  if (AR.MSSA)
384  PA.preserve<MemorySSAAnalysis>();
385  return PA;
386 }
387 
389 LoopPredication::parseLoopICmp(ICmpInst *ICI) {
390  auto Pred = ICI->getPredicate();
391  auto *LHS = ICI->getOperand(0);
392  auto *RHS = ICI->getOperand(1);
393 
394  const SCEV *LHSS = SE->getSCEV(LHS);
395  if (isa<SCEVCouldNotCompute>(LHSS))
396  return None;
397  const SCEV *RHSS = SE->getSCEV(RHS);
398  if (isa<SCEVCouldNotCompute>(RHSS))
399  return None;
400 
401  // Canonicalize RHS to be loop invariant bound, LHS - a loop computable IV
402  if (SE->isLoopInvariant(LHSS, L)) {
403  std::swap(LHS, RHS);
404  std::swap(LHSS, RHSS);
405  Pred = ICmpInst::getSwappedPredicate(Pred);
406  }
407 
408  const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(LHSS);
409  if (!AR || AR->getLoop() != L)
410  return None;
411 
412  return LoopICmp(Pred, AR, RHSS);
413 }
414 
415 Value *LoopPredication::expandCheck(SCEVExpander &Expander,
416  Instruction *Guard,
417  ICmpInst::Predicate Pred, const SCEV *LHS,
418  const SCEV *RHS) {
419  Type *Ty = LHS->getType();
420  assert(Ty == RHS->getType() && "expandCheck operands have different types?");
421 
422  if (SE->isLoopInvariant(LHS, L) && SE->isLoopInvariant(RHS, L)) {
423  IRBuilder<> Builder(Guard);
424  if (SE->isLoopEntryGuardedByCond(L, Pred, LHS, RHS))
425  return Builder.getTrue();
426  if (SE->isLoopEntryGuardedByCond(L, ICmpInst::getInversePredicate(Pred),
427  LHS, RHS))
428  return Builder.getFalse();
429  }
430 
431  Value *LHSV = Expander.expandCodeFor(LHS, Ty, findInsertPt(Guard, {LHS}));
432  Value *RHSV = Expander.expandCodeFor(RHS, Ty, findInsertPt(Guard, {RHS}));
433  IRBuilder<> Builder(findInsertPt(Guard, {LHSV, RHSV}));
434  return Builder.CreateICmp(Pred, LHSV, RHSV);
435 }
436 
437 
438 // Returns true if its safe to truncate the IV to RangeCheckType.
439 // When the IV type is wider than the range operand type, we can still do loop
440 // predication, by generating SCEVs for the range and latch that are of the
441 // same type. We achieve this by generating a SCEV truncate expression for the
442 // latch IV. This is done iff truncation of the IV is a safe operation,
443 // without loss of information.
444 // Another way to achieve this is by generating a wider type SCEV for the
445 // range check operand, however, this needs a more involved check that
446 // operands do not overflow. This can lead to loss of information when the
447 // range operand is of the form: add i32 %offset, %iv. We need to prove that
448 // sext(x + y) is same as sext(x) + sext(y).
449 // This function returns true if we can safely represent the IV type in
450 // the RangeCheckType without loss of information.
452  ScalarEvolution &SE,
453  const LoopICmp LatchCheck,
454  Type *RangeCheckType) {
455  if (!EnableIVTruncation)
456  return false;
457  assert(DL.getTypeSizeInBits(LatchCheck.IV->getType()).getFixedSize() >
458  DL.getTypeSizeInBits(RangeCheckType).getFixedSize() &&
459  "Expected latch check IV type to be larger than range check operand "
460  "type!");
461  // The start and end values of the IV should be known. This is to guarantee
462  // that truncating the wide type will not lose information.
463  auto *Limit = dyn_cast<SCEVConstant>(LatchCheck.Limit);
464  auto *Start = dyn_cast<SCEVConstant>(LatchCheck.IV->getStart());
465  if (!Limit || !Start)
466  return false;
467  // This check makes sure that the IV does not change sign during loop
468  // iterations. Consider latchType = i64, LatchStart = 5, Pred = ICMP_SGE,
469  // LatchEnd = 2, rangeCheckType = i32. If it's not a monotonic predicate, the
470  // IV wraps around, and the truncation of the IV would lose the range of
471  // iterations between 2^32 and 2^64.
472  if (!SE.getMonotonicPredicateType(LatchCheck.IV, LatchCheck.Pred))
473  return false;
474  // The active bits should be less than the bits in the RangeCheckType. This
475  // guarantees that truncating the latch check to RangeCheckType is a safe
476  // operation.
477  auto RangeCheckTypeBitSize =
478  DL.getTypeSizeInBits(RangeCheckType).getFixedSize();
479  return Start->getAPInt().getActiveBits() < RangeCheckTypeBitSize &&
480  Limit->getAPInt().getActiveBits() < RangeCheckTypeBitSize;
481 }
482 
483 
484 // Return an LoopICmp describing a latch check equivlent to LatchCheck but with
485 // the requested type if safe to do so. May involve the use of a new IV.
487  ScalarEvolution &SE,
488  const LoopICmp LatchCheck,
489  Type *RangeCheckType) {
490 
491  auto *LatchType = LatchCheck.IV->getType();
492  if (RangeCheckType == LatchType)
493  return LatchCheck;
494  // For now, bail out if latch type is narrower than range type.
495  if (DL.getTypeSizeInBits(LatchType).getFixedSize() <
496  DL.getTypeSizeInBits(RangeCheckType).getFixedSize())
497  return None;
498  if (!isSafeToTruncateWideIVType(DL, SE, LatchCheck, RangeCheckType))
499  return None;
500  // We can now safely identify the truncated version of the IV and limit for
501  // RangeCheckType.
502  LoopICmp NewLatchCheck;
503  NewLatchCheck.Pred = LatchCheck.Pred;
504  NewLatchCheck.IV = dyn_cast<SCEVAddRecExpr>(
505  SE.getTruncateExpr(LatchCheck.IV, RangeCheckType));
506  if (!NewLatchCheck.IV)
507  return None;
508  NewLatchCheck.Limit = SE.getTruncateExpr(LatchCheck.Limit, RangeCheckType);
509  LLVM_DEBUG(dbgs() << "IV of type: " << *LatchType
510  << "can be represented as range check type:"
511  << *RangeCheckType << "\n");
512  LLVM_DEBUG(dbgs() << "LatchCheck.IV: " << *NewLatchCheck.IV << "\n");
513  LLVM_DEBUG(dbgs() << "LatchCheck.Limit: " << *NewLatchCheck.Limit << "\n");
514  return NewLatchCheck;
515 }
516 
517 bool LoopPredication::isSupportedStep(const SCEV* Step) {
518  return Step->isOne() || (Step->isAllOnesValue() && EnableCountDownLoop);
519 }
520 
521 Instruction *LoopPredication::findInsertPt(Instruction *Use,
522  ArrayRef<Value*> Ops) {
523  for (Value *Op : Ops)
524  if (!L->isLoopInvariant(Op))
525  return Use;
526  return Preheader->getTerminator();
527 }
528 
529 Instruction *LoopPredication::findInsertPt(Instruction *Use,
530  ArrayRef<const SCEV*> Ops) {
531  // Subtlety: SCEV considers things to be invariant if the value produced is
532  // the same across iterations. This is not the same as being able to
533  // evaluate outside the loop, which is what we actually need here.
534  for (const SCEV *Op : Ops)
535  if (!SE->isLoopInvariant(Op, L) ||
536  !isSafeToExpandAt(Op, Preheader->getTerminator(), *SE))
537  return Use;
538  return Preheader->getTerminator();
539 }
540 
541 bool LoopPredication::isLoopInvariantValue(const SCEV* S) {
542  // Handling expressions which produce invariant results, but *haven't* yet
543  // been removed from the loop serves two important purposes.
544  // 1) Most importantly, it resolves a pass ordering cycle which would
545  // otherwise need us to iteration licm, loop-predication, and either
546  // loop-unswitch or loop-peeling to make progress on examples with lots of
547  // predicable range checks in a row. (Since, in the general case, we can't
548  // hoist the length checks until the dominating checks have been discharged
549  // as we can't prove doing so is safe.)
550  // 2) As a nice side effect, this exposes the value of peeling or unswitching
551  // much more obviously in the IR. Otherwise, the cost modeling for other
552  // transforms would end up needing to duplicate all of this logic to model a
553  // check which becomes predictable based on a modeled peel or unswitch.
554  //
555  // The cost of doing so in the worst case is an extra fill from the stack in
556  // the loop to materialize the loop invariant test value instead of checking
557  // against the original IV which is presumable in a register inside the loop.
558  // Such cases are presumably rare, and hint at missing oppurtunities for
559  // other passes.
560 
561  if (SE->isLoopInvariant(S, L))
562  // Note: This the SCEV variant, so the original Value* may be within the
563  // loop even though SCEV has proven it is loop invariant.
564  return true;
565 
566  // Handle a particular important case which SCEV doesn't yet know about which
567  // shows up in range checks on arrays with immutable lengths.
568  // TODO: This should be sunk inside SCEV.
569  if (const SCEVUnknown *U = dyn_cast<SCEVUnknown>(S))
570  if (const auto *LI = dyn_cast<LoadInst>(U->getValue()))
571  if (LI->isUnordered() && L->hasLoopInvariantOperands(LI))
572  if (AA->pointsToConstantMemory(LI->getOperand(0)) ||
573  LI->hasMetadata(LLVMContext::MD_invariant_load))
574  return true;
575  return false;
576 }
577 
578 Optional<Value *> LoopPredication::widenICmpRangeCheckIncrementingLoop(
579  LoopICmp LatchCheck, LoopICmp RangeCheck,
580  SCEVExpander &Expander, Instruction *Guard) {
581  auto *Ty = RangeCheck.IV->getType();
582  // Generate the widened condition for the forward loop:
583  // guardStart u< guardLimit &&
584  // latchLimit <pred> guardLimit - 1 - guardStart + latchStart
585  // where <pred> depends on the latch condition predicate. See the file
586  // header comment for the reasoning.
587  // guardLimit - guardStart + latchStart - 1
588  const SCEV *GuardStart = RangeCheck.IV->getStart();
589  const SCEV *GuardLimit = RangeCheck.Limit;
590  const SCEV *LatchStart = LatchCheck.IV->getStart();
591  const SCEV *LatchLimit = LatchCheck.Limit;
592  // Subtlety: We need all the values to be *invariant* across all iterations,
593  // but we only need to check expansion safety for those which *aren't*
594  // already guaranteed to dominate the guard.
595  if (!isLoopInvariantValue(GuardStart) ||
596  !isLoopInvariantValue(GuardLimit) ||
597  !isLoopInvariantValue(LatchStart) ||
598  !isLoopInvariantValue(LatchLimit)) {
599  LLVM_DEBUG(dbgs() << "Can't expand limit check!\n");
600  return None;
601  }
602  if (!isSafeToExpandAt(LatchStart, Guard, *SE) ||
603  !isSafeToExpandAt(LatchLimit, Guard, *SE)) {
604  LLVM_DEBUG(dbgs() << "Can't expand limit check!\n");
605  return None;
606  }
607 
608  // guardLimit - guardStart + latchStart - 1
609  const SCEV *RHS =
610  SE->getAddExpr(SE->getMinusSCEV(GuardLimit, GuardStart),
611  SE->getMinusSCEV(LatchStart, SE->getOne(Ty)));
612  auto LimitCheckPred =
614 
615  LLVM_DEBUG(dbgs() << "LHS: " << *LatchLimit << "\n");
616  LLVM_DEBUG(dbgs() << "RHS: " << *RHS << "\n");
617  LLVM_DEBUG(dbgs() << "Pred: " << LimitCheckPred << "\n");
618 
619  auto *LimitCheck =
620  expandCheck(Expander, Guard, LimitCheckPred, LatchLimit, RHS);
621  auto *FirstIterationCheck = expandCheck(Expander, Guard, RangeCheck.Pred,
622  GuardStart, GuardLimit);
623  IRBuilder<> Builder(findInsertPt(Guard, {FirstIterationCheck, LimitCheck}));
624  return Builder.CreateAnd(FirstIterationCheck, LimitCheck);
625 }
626 
627 Optional<Value *> LoopPredication::widenICmpRangeCheckDecrementingLoop(
628  LoopICmp LatchCheck, LoopICmp RangeCheck,
629  SCEVExpander &Expander, Instruction *Guard) {
630  auto *Ty = RangeCheck.IV->getType();
631  const SCEV *GuardStart = RangeCheck.IV->getStart();
632  const SCEV *GuardLimit = RangeCheck.Limit;
633  const SCEV *LatchStart = LatchCheck.IV->getStart();
634  const SCEV *LatchLimit = LatchCheck.Limit;
635  // Subtlety: We need all the values to be *invariant* across all iterations,
636  // but we only need to check expansion safety for those which *aren't*
637  // already guaranteed to dominate the guard.
638  if (!isLoopInvariantValue(GuardStart) ||
639  !isLoopInvariantValue(GuardLimit) ||
640  !isLoopInvariantValue(LatchStart) ||
641  !isLoopInvariantValue(LatchLimit)) {
642  LLVM_DEBUG(dbgs() << "Can't expand limit check!\n");
643  return None;
644  }
645  if (!isSafeToExpandAt(LatchStart, Guard, *SE) ||
646  !isSafeToExpandAt(LatchLimit, Guard, *SE)) {
647  LLVM_DEBUG(dbgs() << "Can't expand limit check!\n");
648  return None;
649  }
650  // The decrement of the latch check IV should be the same as the
651  // rangeCheckIV.
652  auto *PostDecLatchCheckIV = LatchCheck.IV->getPostIncExpr(*SE);
653  if (RangeCheck.IV != PostDecLatchCheckIV) {
654  LLVM_DEBUG(dbgs() << "Not the same. PostDecLatchCheckIV: "
655  << *PostDecLatchCheckIV
656  << " and RangeCheckIV: " << *RangeCheck.IV << "\n");
657  return None;
658  }
659 
660  // Generate the widened condition for CountDownLoop:
661  // guardStart u< guardLimit &&
662  // latchLimit <pred> 1.
663  // See the header comment for reasoning of the checks.
664  auto LimitCheckPred =
666  auto *FirstIterationCheck = expandCheck(Expander, Guard,
668  GuardStart, GuardLimit);
669  auto *LimitCheck = expandCheck(Expander, Guard, LimitCheckPred, LatchLimit,
670  SE->getOne(Ty));
671  IRBuilder<> Builder(findInsertPt(Guard, {FirstIterationCheck, LimitCheck}));
672  return Builder.CreateAnd(FirstIterationCheck, LimitCheck);
673 }
674 
676  LoopICmp& RC) {
677  // LFTR canonicalizes checks to the ICMP_NE/EQ form; normalize back to the
678  // ULT/UGE form for ease of handling by our caller.
679  if (ICmpInst::isEquality(RC.Pred) &&
680  RC.IV->getStepRecurrence(*SE)->isOne() &&
681  SE->isKnownPredicate(ICmpInst::ICMP_ULE, RC.IV->getStart(), RC.Limit))
682  RC.Pred = RC.Pred == ICmpInst::ICMP_NE ?
684 }
685 
686 
687 /// If ICI can be widened to a loop invariant condition emits the loop
688 /// invariant condition in the loop preheader and return it, otherwise
689 /// returns None.
690 Optional<Value *> LoopPredication::widenICmpRangeCheck(ICmpInst *ICI,
691  SCEVExpander &Expander,
692  Instruction *Guard) {
693  LLVM_DEBUG(dbgs() << "Analyzing ICmpInst condition:\n");
694  LLVM_DEBUG(ICI->dump());
695 
696  // parseLoopStructure guarantees that the latch condition is:
697  // ++i <pred> latchLimit, where <pred> is u<, u<=, s<, or s<=.
698  // We are looking for the range checks of the form:
699  // i u< guardLimit
700  auto RangeCheck = parseLoopICmp(ICI);
701  if (!RangeCheck) {
702  LLVM_DEBUG(dbgs() << "Failed to parse the loop latch condition!\n");
703  return None;
704  }
705  LLVM_DEBUG(dbgs() << "Guard check:\n");
706  LLVM_DEBUG(RangeCheck->dump());
707  if (RangeCheck->Pred != ICmpInst::ICMP_ULT) {
708  LLVM_DEBUG(dbgs() << "Unsupported range check predicate("
709  << RangeCheck->Pred << ")!\n");
710  return None;
711  }
712  auto *RangeCheckIV = RangeCheck->IV;
713  if (!RangeCheckIV->isAffine()) {
714  LLVM_DEBUG(dbgs() << "Range check IV is not affine!\n");
715  return None;
716  }
717  auto *Step = RangeCheckIV->getStepRecurrence(*SE);
718  // We cannot just compare with latch IV step because the latch and range IVs
719  // may have different types.
720  if (!isSupportedStep(Step)) {
721  LLVM_DEBUG(dbgs() << "Range check and latch have IVs different steps!\n");
722  return None;
723  }
724  auto *Ty = RangeCheckIV->getType();
725  auto CurrLatchCheckOpt = generateLoopLatchCheck(*DL, *SE, LatchCheck, Ty);
726  if (!CurrLatchCheckOpt) {
727  LLVM_DEBUG(dbgs() << "Failed to generate a loop latch check "
728  "corresponding to range type: "
729  << *Ty << "\n");
730  return None;
731  }
732 
733  LoopICmp CurrLatchCheck = *CurrLatchCheckOpt;
734  // At this point, the range and latch step should have the same type, but need
735  // not have the same value (we support both 1 and -1 steps).
736  assert(Step->getType() ==
737  CurrLatchCheck.IV->getStepRecurrence(*SE)->getType() &&
738  "Range and latch steps should be of same type!");
739  if (Step != CurrLatchCheck.IV->getStepRecurrence(*SE)) {
740  LLVM_DEBUG(dbgs() << "Range and latch have different step values!\n");
741  return None;
742  }
743 
744  if (Step->isOne())
745  return widenICmpRangeCheckIncrementingLoop(CurrLatchCheck, *RangeCheck,
746  Expander, Guard);
747  else {
748  assert(Step->isAllOnesValue() && "Step should be -1!");
749  return widenICmpRangeCheckDecrementingLoop(CurrLatchCheck, *RangeCheck,
750  Expander, Guard);
751  }
752 }
753 
754 unsigned LoopPredication::collectChecks(SmallVectorImpl<Value *> &Checks,
755  Value *Condition,
756  SCEVExpander &Expander,
757  Instruction *Guard) {
758  unsigned NumWidened = 0;
759  // The guard condition is expected to be in form of:
760  // cond1 && cond2 && cond3 ...
761  // Iterate over subconditions looking for icmp conditions which can be
762  // widened across loop iterations. Widening these conditions remember the
763  // resulting list of subconditions in Checks vector.
764  SmallVector<Value *, 4> Worklist(1, Condition);
765  SmallPtrSet<Value *, 4> Visited;
766  Value *WideableCond = nullptr;
767  do {
768  Value *Condition = Worklist.pop_back_val();
769  if (!Visited.insert(Condition).second)
770  continue;
771 
772  Value *LHS, *RHS;
773  using namespace llvm::PatternMatch;
774  if (match(Condition, m_And(m_Value(LHS), m_Value(RHS)))) {
775  Worklist.push_back(LHS);
776  Worklist.push_back(RHS);
777  continue;
778  }
779 
780  if (match(Condition,
781  m_Intrinsic<Intrinsic::experimental_widenable_condition>())) {
782  // Pick any, we don't care which
783  WideableCond = Condition;
784  continue;
785  }
786 
787  if (ICmpInst *ICI = dyn_cast<ICmpInst>(Condition)) {
788  if (auto NewRangeCheck = widenICmpRangeCheck(ICI, Expander,
789  Guard)) {
790  Checks.push_back(NewRangeCheck.getValue());
791  NumWidened++;
792  continue;
793  }
794  }
795 
796  // Save the condition as is if we can't widen it
797  Checks.push_back(Condition);
798  } while (!Worklist.empty());
799  // At the moment, our matching logic for wideable conditions implicitly
800  // assumes we preserve the form: (br (and Cond, WC())). FIXME
801  // Note that if there were multiple calls to wideable condition in the
802  // traversal, we only need to keep one, and which one is arbitrary.
803  if (WideableCond)
804  Checks.push_back(WideableCond);
805  return NumWidened;
806 }
807 
808 bool LoopPredication::widenGuardConditions(IntrinsicInst *Guard,
809  SCEVExpander &Expander) {
810  LLVM_DEBUG(dbgs() << "Processing guard:\n");
811  LLVM_DEBUG(Guard->dump());
812 
813  TotalConsidered++;
815  unsigned NumWidened = collectChecks(Checks, Guard->getOperand(0), Expander,
816  Guard);
817  if (NumWidened == 0)
818  return false;
819 
820  TotalWidened += NumWidened;
821 
822  // Emit the new guard condition
823  IRBuilder<> Builder(findInsertPt(Guard, Checks));
824  Value *AllChecks = Builder.CreateAnd(Checks);
825  auto *OldCond = Guard->getOperand(0);
826  Guard->setOperand(0, AllChecks);
827  RecursivelyDeleteTriviallyDeadInstructions(OldCond, nullptr /* TLI */, MSSAU);
828 
829  LLVM_DEBUG(dbgs() << "Widened checks = " << NumWidened << "\n");
830  return true;
831 }
832 
833 bool LoopPredication::widenWidenableBranchGuardConditions(
834  BranchInst *BI, SCEVExpander &Expander) {
835  assert(isGuardAsWidenableBranch(BI) && "Must be!");
836  LLVM_DEBUG(dbgs() << "Processing guard:\n");
837  LLVM_DEBUG(BI->dump());
838 
839  TotalConsidered++;
841  unsigned NumWidened = collectChecks(Checks, BI->getCondition(),
842  Expander, BI);
843  if (NumWidened == 0)
844  return false;
845 
846  TotalWidened += NumWidened;
847 
848  // Emit the new guard condition
849  IRBuilder<> Builder(findInsertPt(BI, Checks));
850  Value *AllChecks = Builder.CreateAnd(Checks);
851  auto *OldCond = BI->getCondition();
852  BI->setCondition(AllChecks);
853  RecursivelyDeleteTriviallyDeadInstructions(OldCond, nullptr /* TLI */, MSSAU);
855  "Stopped being a guard after transform?");
856 
857  LLVM_DEBUG(dbgs() << "Widened checks = " << NumWidened << "\n");
858  return true;
859 }
860 
861 Optional<LoopICmp> LoopPredication::parseLoopLatchICmp() {
862  using namespace PatternMatch;
863 
864  BasicBlock *LoopLatch = L->getLoopLatch();
865  if (!LoopLatch) {
866  LLVM_DEBUG(dbgs() << "The loop doesn't have a single latch!\n");
867  return None;
868  }
869 
870  auto *BI = dyn_cast<BranchInst>(LoopLatch->getTerminator());
871  if (!BI || !BI->isConditional()) {
872  LLVM_DEBUG(dbgs() << "Failed to match the latch terminator!\n");
873  return None;
874  }
875  BasicBlock *TrueDest = BI->getSuccessor(0);
876  assert(
877  (TrueDest == L->getHeader() || BI->getSuccessor(1) == L->getHeader()) &&
878  "One of the latch's destinations must be the header");
879 
880  auto *ICI = dyn_cast<ICmpInst>(BI->getCondition());
881  if (!ICI) {
882  LLVM_DEBUG(dbgs() << "Failed to match the latch condition!\n");
883  return None;
884  }
885  auto Result = parseLoopICmp(ICI);
886  if (!Result) {
887  LLVM_DEBUG(dbgs() << "Failed to parse the loop latch condition!\n");
888  return None;
889  }
890 
891  if (TrueDest != L->getHeader())
893 
894  // Check affine first, so if it's not we don't try to compute the step
895  // recurrence.
896  if (!Result->IV->isAffine()) {
897  LLVM_DEBUG(dbgs() << "The induction variable is not affine!\n");
898  return None;
899  }
900 
901  auto *Step = Result->IV->getStepRecurrence(*SE);
902  if (!isSupportedStep(Step)) {
903  LLVM_DEBUG(dbgs() << "Unsupported loop stride(" << *Step << ")!\n");
904  return None;
905  }
906 
907  auto IsUnsupportedPredicate = [](const SCEV *Step, ICmpInst::Predicate Pred) {
908  if (Step->isOne()) {
909  return Pred != ICmpInst::ICMP_ULT && Pred != ICmpInst::ICMP_SLT &&
910  Pred != ICmpInst::ICMP_ULE && Pred != ICmpInst::ICMP_SLE;
911  } else {
912  assert(Step->isAllOnesValue() && "Step should be -1!");
913  return Pred != ICmpInst::ICMP_UGT && Pred != ICmpInst::ICMP_SGT &&
914  Pred != ICmpInst::ICMP_UGE && Pred != ICmpInst::ICMP_SGE;
915  }
916  };
917 
918  normalizePredicate(SE, L, *Result);
919  if (IsUnsupportedPredicate(Step, Result->Pred)) {
920  LLVM_DEBUG(dbgs() << "Unsupported loop latch predicate(" << Result->Pred
921  << ")!\n");
922  return None;
923  }
924 
925  return Result;
926 }
927 
928 
929 bool LoopPredication::isLoopProfitableToPredicate() {
930  if (SkipProfitabilityChecks || !BPI)
931  return true;
932 
934  L->getExitEdges(ExitEdges);
935  // If there is only one exiting edge in the loop, it is always profitable to
936  // predicate the loop.
937  if (ExitEdges.size() == 1)
938  return true;
939 
940  // Calculate the exiting probabilities of all exiting edges from the loop,
941  // starting with the LatchExitProbability.
942  // Heuristic for profitability: If any of the exiting blocks' probability of
943  // exiting the loop is larger than exiting through the latch block, it's not
944  // profitable to predicate the loop.
945  auto *LatchBlock = L->getLoopLatch();
946  assert(LatchBlock && "Should have a single latch at this point!");
947  auto *LatchTerm = LatchBlock->getTerminator();
948  assert(LatchTerm->getNumSuccessors() == 2 &&
949  "expected to be an exiting block with 2 succs!");
950  unsigned LatchBrExitIdx =
951  LatchTerm->getSuccessor(0) == L->getHeader() ? 1 : 0;
952  BranchProbability LatchExitProbability =
953  BPI->getEdgeProbability(LatchBlock, LatchBrExitIdx);
954 
955  // Protect against degenerate inputs provided by the user. Providing a value
956  // less than one, can invert the definition of profitable loop predication.
957  float ScaleFactor = LatchExitProbabilityScale;
958  if (ScaleFactor < 1) {
959  LLVM_DEBUG(
960  dbgs()
961  << "Ignored user setting for loop-predication-latch-probability-scale: "
962  << LatchExitProbabilityScale << "\n");
963  LLVM_DEBUG(dbgs() << "The value is set to 1.0\n");
964  ScaleFactor = 1.0;
965  }
966  const auto LatchProbabilityThreshold =
967  LatchExitProbability * ScaleFactor;
968 
969  for (const auto &ExitEdge : ExitEdges) {
970  BranchProbability ExitingBlockProbability =
971  BPI->getEdgeProbability(ExitEdge.first, ExitEdge.second);
972  // Some exiting edge has higher probability than the latch exiting edge.
973  // No longer profitable to predicate.
974  if (ExitingBlockProbability > LatchProbabilityThreshold)
975  return false;
976  }
977  // Using BPI, we have concluded that the most probable way to exit from the
978  // loop is through the latch (or there's no profile information and all
979  // exits are equally likely).
980  return true;
981 }
982 
983 /// If we can (cheaply) find a widenable branch which controls entry into the
984 /// loop, return it.
986  // Walk back through any unconditional executed blocks and see if we can find
987  // a widenable condition which seems to control execution of this loop. Note
988  // that we predict that maythrow calls are likely untaken and thus that it's
989  // profitable to widen a branch before a maythrow call with a condition
990  // afterwards even though that may cause the slow path to run in a case where
991  // it wouldn't have otherwise.
993  if (!BB)
994  return nullptr;
995  do {
996  if (BasicBlock *Pred = BB->getSinglePredecessor())
997  if (BB == Pred->getSingleSuccessor()) {
998  BB = Pred;
999  continue;
1000  }
1001  break;
1002  } while (true);
1003 
1004  if (BasicBlock *Pred = BB->getSinglePredecessor()) {
1005  auto *Term = Pred->getTerminator();
1006 
1007  Value *Cond, *WC;
1008  BasicBlock *IfTrueBB, *IfFalseBB;
1009  if (parseWidenableBranch(Term, Cond, WC, IfTrueBB, IfFalseBB) &&
1010  IfTrueBB == BB)
1011  return cast<BranchInst>(Term);
1012  }
1013  return nullptr;
1014 }
1015 
1016 /// Return the minimum of all analyzeable exit counts. This is an upper bound
1017 /// on the actual exit count. If there are not at least two analyzeable exits,
1018 /// returns SCEVCouldNotCompute.
1020  DominatorTree &DT,
1021  Loop *L) {
1022  SmallVector<BasicBlock *, 16> ExitingBlocks;
1023  L->getExitingBlocks(ExitingBlocks);
1024 
1025  SmallVector<const SCEV *, 4> ExitCounts;
1026  for (BasicBlock *ExitingBB : ExitingBlocks) {
1027  const SCEV *ExitCount = SE.getExitCount(L, ExitingBB);
1028  if (isa<SCEVCouldNotCompute>(ExitCount))
1029  continue;
1030  assert(DT.dominates(ExitingBB, L->getLoopLatch()) &&
1031  "We should only have known counts for exiting blocks that "
1032  "dominate latch!");
1033  ExitCounts.push_back(ExitCount);
1034  }
1035  if (ExitCounts.size() < 2)
1036  return SE.getCouldNotCompute();
1037  return SE.getUMinFromMismatchedTypes(ExitCounts);
1038 }
1039 
1040 /// This implements an analogous, but entirely distinct transform from the main
1041 /// loop predication transform. This one is phrased in terms of using a
1042 /// widenable branch *outside* the loop to allow us to simplify loop exits in a
1043 /// following loop. This is close in spirit to the IndVarSimplify transform
1044 /// of the same name, but is materially different widening loosens legality
1045 /// sharply.
1046 bool LoopPredication::predicateLoopExits(Loop *L, SCEVExpander &Rewriter) {
1047  // The transformation performed here aims to widen a widenable condition
1048  // above the loop such that all analyzeable exit leading to deopt are dead.
1049  // It assumes that the latch is the dominant exit for profitability and that
1050  // exits branching to deoptimizing blocks are rarely taken. It relies on the
1051  // semantics of widenable expressions for legality. (i.e. being able to fall
1052  // down the widenable path spuriously allows us to ignore exit order,
1053  // unanalyzeable exits, side effects, exceptional exits, and other challenges
1054  // which restrict the applicability of the non-WC based version of this
1055  // transform in IndVarSimplify.)
1056  //
1057  // NOTE ON POISON/UNDEF - We're hoisting an expression above guards which may
1058  // imply flags on the expression being hoisted and inserting new uses (flags
1059  // are only correct for current uses). The result is that we may be
1060  // inserting a branch on the value which can be either poison or undef. In
1061  // this case, the branch can legally go either way; we just need to avoid
1062  // introducing UB. This is achieved through the use of the freeze
1063  // instruction.
1064 
1065  SmallVector<BasicBlock *, 16> ExitingBlocks;
1066  L->getExitingBlocks(ExitingBlocks);
1067 
1068  if (ExitingBlocks.empty())
1069  return false; // Nothing to do.
1070 
1071  auto *Latch = L->getLoopLatch();
1072  if (!Latch)
1073  return false;
1074 
1075  auto *WidenableBR = FindWidenableTerminatorAboveLoop(L, *LI);
1076  if (!WidenableBR)
1077  return false;
1078 
1079  const SCEV *LatchEC = SE->getExitCount(L, Latch);
1080  if (isa<SCEVCouldNotCompute>(LatchEC))
1081  return false; // profitability - want hot exit in analyzeable set
1082 
1083  // At this point, we have found an analyzeable latch, and a widenable
1084  // condition above the loop. If we have a widenable exit within the loop
1085  // (for which we can't compute exit counts), drop the ability to further
1086  // widen so that we gain ability to analyze it's exit count and perform this
1087  // transform. TODO: It'd be nice to know for sure the exit became
1088  // analyzeable after dropping widenability.
1089  bool ChangedLoop = false;
1090 
1091  for (auto *ExitingBB : ExitingBlocks) {
1092  if (LI->getLoopFor(ExitingBB) != L)
1093  continue;
1094 
1095  auto *BI = dyn_cast<BranchInst>(ExitingBB->getTerminator());
1096  if (!BI)
1097  continue;
1098 
1099  Use *Cond, *WC;
1100  BasicBlock *IfTrueBB, *IfFalseBB;
1101  if (parseWidenableBranch(BI, Cond, WC, IfTrueBB, IfFalseBB) &&
1102  L->contains(IfTrueBB)) {
1103  WC->set(ConstantInt::getTrue(IfTrueBB->getContext()));
1104  ChangedLoop = true;
1105  }
1106  }
1107  if (ChangedLoop)
1108  SE->forgetLoop(L);
1109 
1110  // The use of umin(all analyzeable exits) instead of latch is subtle, but
1111  // important for profitability. We may have a loop which hasn't been fully
1112  // canonicalized just yet. If the exit we chose to widen is provably never
1113  // taken, we want the widened form to *also* be provably never taken. We
1114  // can't guarantee this as a current unanalyzeable exit may later become
1115  // analyzeable, but we can at least avoid the obvious cases.
1116  const SCEV *MinEC = getMinAnalyzeableBackedgeTakenCount(*SE, *DT, L);
1117  if (isa<SCEVCouldNotCompute>(MinEC) || MinEC->getType()->isPointerTy() ||
1118  !SE->isLoopInvariant(MinEC, L) ||
1119  !isSafeToExpandAt(MinEC, WidenableBR, *SE))
1120  return ChangedLoop;
1121 
1122  // Subtlety: We need to avoid inserting additional uses of the WC. We know
1123  // that it can only have one transitive use at the moment, and thus moving
1124  // that use to just before the branch and inserting code before it and then
1125  // modifying the operand is legal.
1126  auto *IP = cast<Instruction>(WidenableBR->getCondition());
1127  // Here we unconditionally modify the IR, so after this point we should return
1128  // only `true`!
1129  IP->moveBefore(WidenableBR);
1130  if (MSSAU)
1131  if (auto *MUD = MSSAU->getMemorySSA()->getMemoryAccess(IP))
1132  MSSAU->moveToPlace(MUD, WidenableBR->getParent(),
1134  Rewriter.setInsertPoint(IP);
1135  IRBuilder<> B(IP);
1136 
1137  bool InvalidateLoop = false;
1138  Value *MinECV = nullptr; // lazily generated if needed
1139  for (BasicBlock *ExitingBB : ExitingBlocks) {
1140  // If our exiting block exits multiple loops, we can only rewrite the
1141  // innermost one. Otherwise, we're changing how many times the innermost
1142  // loop runs before it exits.
1143  if (LI->getLoopFor(ExitingBB) != L)
1144  continue;
1145 
1146  // Can't rewrite non-branch yet.
1147  auto *BI = dyn_cast<BranchInst>(ExitingBB->getTerminator());
1148  if (!BI)
1149  continue;
1150 
1151  // If already constant, nothing to do.
1152  if (isa<Constant>(BI->getCondition()))
1153  continue;
1154 
1155  const SCEV *ExitCount = SE->getExitCount(L, ExitingBB);
1156  if (isa<SCEVCouldNotCompute>(ExitCount) ||
1157  ExitCount->getType()->isPointerTy() ||
1158  !isSafeToExpandAt(ExitCount, WidenableBR, *SE))
1159  continue;
1160 
1161  const bool ExitIfTrue = !L->contains(*succ_begin(ExitingBB));
1162  BasicBlock *ExitBB = BI->getSuccessor(ExitIfTrue ? 0 : 1);
1163  if (!ExitBB->getPostdominatingDeoptimizeCall())
1164  continue;
1165 
1166  /// Here we can be fairly sure that executing this exit will most likely
1167  /// lead to executing llvm.experimental.deoptimize.
1168  /// This is a profitability heuristic, not a legality constraint.
1169 
1170  // If we found a widenable exit condition, do two things:
1171  // 1) fold the widened exit test into the widenable condition
1172  // 2) fold the branch to untaken - avoids infinite looping
1173 
1174  Value *ECV = Rewriter.expandCodeFor(ExitCount);
1175  if (!MinECV)
1176  MinECV = Rewriter.expandCodeFor(MinEC);
1177  Value *RHS = MinECV;
1178  if (ECV->getType() != RHS->getType()) {
1179  Type *WiderTy = SE->getWiderType(ECV->getType(), RHS->getType());
1180  ECV = B.CreateZExt(ECV, WiderTy);
1181  RHS = B.CreateZExt(RHS, WiderTy);
1182  }
1183  assert(!Latch || DT->dominates(ExitingBB, Latch));
1184  Value *NewCond = B.CreateICmp(ICmpInst::ICMP_UGT, ECV, RHS);
1185  // Freeze poison or undef to an arbitrary bit pattern to ensure we can
1186  // branch without introducing UB. See NOTE ON POISON/UNDEF above for
1187  // context.
1188  NewCond = B.CreateFreeze(NewCond);
1189 
1190  widenWidenableBranch(WidenableBR, NewCond);
1191 
1192  Value *OldCond = BI->getCondition();
1193  BI->setCondition(ConstantInt::get(OldCond->getType(), !ExitIfTrue));
1194  InvalidateLoop = true;
1195  }
1196 
1197  if (InvalidateLoop)
1198  // We just mutated a bunch of loop exits changing there exit counts
1199  // widely. We need to force recomputation of the exit counts given these
1200  // changes. Note that all of the inserted exits are never taken, and
1201  // should be removed next time the CFG is modified.
1202  SE->forgetLoop(L);
1203 
1204  // Always return `true` since we have moved the WidenableBR's condition.
1205  return true;
1206 }
1207 
1208 bool LoopPredication::runOnLoop(Loop *Loop) {
1209  L = Loop;
1210 
1211  LLVM_DEBUG(dbgs() << "Analyzing ");
1212  LLVM_DEBUG(L->dump());
1213 
1214  Module *M = L->getHeader()->getModule();
1215 
1216  // There is nothing to do if the module doesn't use guards
1217  auto *GuardDecl =
1218  M->getFunction(Intrinsic::getName(Intrinsic::experimental_guard));
1219  bool HasIntrinsicGuards = GuardDecl && !GuardDecl->use_empty();
1220  auto *WCDecl = M->getFunction(
1221  Intrinsic::getName(Intrinsic::experimental_widenable_condition));
1222  bool HasWidenableConditions =
1223  PredicateWidenableBranchGuards && WCDecl && !WCDecl->use_empty();
1224  if (!HasIntrinsicGuards && !HasWidenableConditions)
1225  return false;
1226 
1227  DL = &M->getDataLayout();
1228 
1229  Preheader = L->getLoopPreheader();
1230  if (!Preheader)
1231  return false;
1232 
1233  auto LatchCheckOpt = parseLoopLatchICmp();
1234  if (!LatchCheckOpt)
1235  return false;
1236  LatchCheck = *LatchCheckOpt;
1237 
1238  LLVM_DEBUG(dbgs() << "Latch check:\n");
1239  LLVM_DEBUG(LatchCheck.dump());
1240 
1241  if (!isLoopProfitableToPredicate()) {
1242  LLVM_DEBUG(dbgs() << "Loop not profitable to predicate!\n");
1243  return false;
1244  }
1245  // Collect all the guards into a vector and process later, so as not
1246  // to invalidate the instruction iterator.
1248  SmallVector<BranchInst *, 4> GuardsAsWidenableBranches;
1249  for (const auto BB : L->blocks()) {
1250  for (auto &I : *BB)
1251  if (isGuard(&I))
1252  Guards.push_back(cast<IntrinsicInst>(&I));
1254  isGuardAsWidenableBranch(BB->getTerminator()))
1255  GuardsAsWidenableBranches.push_back(
1256  cast<BranchInst>(BB->getTerminator()));
1257  }
1258 
1259  SCEVExpander Expander(*SE, *DL, "loop-predication");
1260  bool Changed = false;
1261  for (auto *Guard : Guards)
1262  Changed |= widenGuardConditions(Guard, Expander);
1263  for (auto *Guard : GuardsAsWidenableBranches)
1264  Changed |= widenWidenableBranchGuardConditions(Guard, Expander);
1265  Changed |= predicateLoopExits(L, Expander);
1266 
1267  if (MSSAU && VerifyMemorySSA)
1268  MSSAU->getMemorySSA()->verifyMemorySSA();
1269  return Changed;
1270 }
llvm::PreservedAnalyses
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:155
llvm::RecursivelyDeleteTriviallyDeadInstructions
bool RecursivelyDeleteTriviallyDeadInstructions(Value *V, const TargetLibraryInfo *TLI=nullptr, MemorySSAUpdater *MSSAU=nullptr, std::function< void(Value *)> AboutToDeleteCallback=std::function< void(Value *)>())
If the specified value is a trivially dead instruction, delete it.
Definition: Local.cpp:511
llvm::Loop::isLoopInvariant
bool isLoopInvariant(const Value *V) const
Return true if the specified value is loop invariant.
Definition: LoopInfo.cpp:64
llvm::CmpInst::getSwappedPredicate
Predicate getSwappedPredicate() const
For example, EQ->EQ, SLE->SGE, ULT->UGT, OEQ->OEQ, ULE->UGE, OLT->OGT, etc.
Definition: InstrTypes.h:836
llvm
---------------------— PointerInfo ------------------------------------—
Definition: AllocatorList.h:23
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::DataLayout
A parsed version of the target data layout string in and methods for querying it.
Definition: DataLayout.h:112
generateLoopLatchCheck
static Optional< LoopICmp > generateLoopLatchCheck(const DataLayout &DL, ScalarEvolution &SE, const LoopICmp LatchCheck, Type *RangeCheckType)
Definition: LoopPredication.cpp:486
llvm::CmpInst::Predicate
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Definition: InstrTypes.h:720
llvm::BasicBlock::getParent
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:107
IntrinsicInst.h
llvm::Type::isPointerTy
bool isPointerTy() const
True if this is an instance of PointerType.
Definition: Type.h:228
llvm::SCEV::isAllOnesValue
bool isAllOnesValue() const
Return true if the expression is a constant all-ones value.
Definition: ScalarEvolution.cpp:421
ScalarEvolutionExpander.h
Scalar.h
MemorySSAUpdater.h
llvm::Function
Definition: Function.h:61
llvm::Loop
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:530
llvm::Value::dump
void dump() const
Support for debugging, callable in GDB: V->dump()
Definition: AsmWriter.cpp:4749
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::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1168
Statistic.h
llvm::Intrinsic::getName
StringRef getName(ID id)
Return the LLVM name for an intrinsic, such as "llvm.ppc.altivec.lvx".
Definition: Function.cpp:879
llvm::IRBuilder<>
llvm::ScalarEvolution
The main scalar evolution driver.
Definition: ScalarEvolution.h:461
llvm::CmpInst::ICMP_NE
@ ICMP_NE
not equal
Definition: InstrTypes.h:742
llvm::CmpInst::getInversePredicate
Predicate getInversePredicate() const
For example, EQ -> NE, UGT -> ULE, SLT -> SGE, OEQ -> UNE, UGT -> OLE, OLT -> UGE,...
Definition: InstrTypes.h:820
Local.h
llvm::DominatorTree
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:151
llvm::ScalarEvolution::getTruncateExpr
const SCEV * getTruncateExpr(const SCEV *Op, Type *Ty, unsigned Depth=0)
Definition: ScalarEvolution.cpp:1186
llvm::getLoopAnalysisUsage
void getLoopAnalysisUsage(AnalysisUsage &AU)
Helper to consistently add the set of standard passes to a loop pass's AnalysisUsage.
Definition: LoopUtils.cpp:149
llvm::SCEVExpander::expandCodeFor
Value * expandCodeFor(const SCEV *SH, Type *Ty, Instruction *I)
Insert code to directly compute the specified SCEV expression into the program.
Definition: ScalarEvolutionExpander.h:275
llvm::cl::Hidden
@ Hidden
Definition: CommandLine.h:143
llvm::CmpInst::getFlippedStrictnessPredicate
Predicate getFlippedStrictnessPredicate() const
For predicate of kind "is X or equal to 0" returns the predicate "is X".
Definition: InstrTypes.h:902
llvm::CmpInst::ICMP_SGT
@ ICMP_SGT
signed greater than
Definition: InstrTypes.h:747
ScalarEvolution.h
llvm::Type
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:45
llvm::ICmpInst::isEquality
bool isEquality() const
Return true if this predicate is either EQ or NE.
Definition: Instructions.h:1298
Module.h
llvm::LoopStandardAnalysisResults
The adaptor from a function pass to a loop pass computes these analyses and makes them available to t...
Definition: LoopAnalysisManager.h:52
llvm::LoopBase::getExitEdges
void getExitEdges(SmallVectorImpl< Edge > &ExitEdges) const
Return all pairs of (inside_block,outside_block).
Definition: LoopInfoImpl.h:148
llvm::Optional
Definition: APInt.h:33
llvm::SmallPtrSet< Value *, 4 >
llvm::CmpInst::ICMP_SLE
@ ICMP_SLE
signed less or equal
Definition: InstrTypes.h:750
getMinAnalyzeableBackedgeTakenCount
static const SCEV * getMinAnalyzeableBackedgeTakenCount(ScalarEvolution &SE, DominatorTree &DT, Loop *L)
Return the minimum of all analyzeable exit counts.
Definition: LoopPredication.cpp:1019
llvm::dump
void dump(const SparseBitVector< ElementSize > &LHS, raw_ostream &out)
Definition: SparseBitVector.h:876
llvm::LoopStandardAnalysisResults::DT
DominatorTree & DT
Definition: LoopAnalysisManager.h:55
llvm::LoopPredicationPass::run
PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM, LoopStandardAnalysisResults &AR, LPMUpdater &U)
Definition: LoopPredication.cpp:366
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:101
F
#define F(x, y, z)
Definition: MD5.cpp:56
loop
Analysis the ScalarEvolution expression for r is< loop > Outside the loop
Definition: README.txt:8
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
AliasAnalysis.h
llvm::isGuard
bool isGuard(const User *U)
Returns true iff U has semantics of a guard expressed in a form of call of llvm.experimental....
Definition: GuardUtils.cpp:18
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
llvm::DominatorTree::dominates
bool dominates(const BasicBlock *BB, const Use &U) const
Return true if the (end of the) basic block BB dominates the use U.
Definition: Dominators.cpp:115
CommandLine.h
llvm::initializeLoopPredicationLegacyPassPass
void initializeLoopPredicationLegacyPassPass(PassRegistry &)
GlobalValue.h
EnableIVTruncation
static cl::opt< bool > EnableIVTruncation("loop-predication-enable-iv-truncation", cl::Hidden, cl::init(true))
llvm::MemorySSAWrapperPass
Legacy analysis pass which computes MemorySSA.
Definition: MemorySSA.h:981
llvm::PassRegistry::getPassRegistry
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Definition: PassRegistry.cpp:31
Rewriter
Virtual Register Rewriter
Definition: VirtRegMap.cpp:237
llvm::PatternMatch::match
bool match(Val *V, const Pattern &P)
Definition: PatternMatch.h:49
llvm::AAResults
Definition: AliasAnalysis.h:508
llvm::BranchProbabilityInfoWrapperPass
Legacy analysis pass which computes BranchProbabilityInfo.
Definition: BranchProbabilityInfo.h:440
llvm::User
Definition: User.h:44
llvm::CmpInst::ICMP_ULE
@ ICMP_ULE
unsigned less or equal
Definition: InstrTypes.h:746
LoopPredication
static cl::opt< bool > LoopPredication("indvars-predicate-loops", cl::Hidden, cl::init(true), cl::desc("Predicate conditions in read only loops"))
GuardUtils.h
llvm::BranchProbabilityInfo
Analysis providing branch probability information.
Definition: BranchProbabilityInfo.h:115
llvm::ScalarEvolution::getUMinFromMismatchedTypes
const SCEV * getUMinFromMismatchedTypes(const SCEV *LHS, const SCEV *RHS)
Promote the operands to the wider of the types using zero-extension, and then perform a umin operatio...
Definition: ScalarEvolution.cpp:4334
llvm::AnalysisUsage
Represent the analysis usage information of a pass.
Definition: PassAnalysisSupport.h:47
llvm::ms_demangle::QualifierMangleMode::Result
@ Result
llvm::LoopBase::blocks
iterator_range< block_iterator > blocks() const
Definition: LoopInfo.h:178
IP
Definition: NVPTXLowerArgs.cpp:166
false
Definition: StackSlotColoring.cpp:142
B
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
SkipProfitabilityChecks
static cl::opt< bool > SkipProfitabilityChecks("loop-predication-skip-profitability-checks", cl::Hidden, cl::init(false))
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:9900
llvm::Instruction
Definition: Instruction.h:45
llvm::BranchInst::setCondition
void setCondition(Value *V)
Definition: Instructions.h:3154
llvm::LoopBase::getExitingBlocks
void getExitingBlocks(SmallVectorImpl< BlockT * > &ExitingBlocks) const
Return all blocks inside the loop that have successors outside of the loop.
Definition: LoopInfoImpl.h:34
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:900
LoopUtils.h
llvm::LPPassManager
Definition: LoopPass.h:75
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::None
const NoneType None
Definition: None.h:23
llvm::M68kBeads::Term
@ Term
Definition: M68kBaseInfo.h:71
llvm::BasicBlock::getPostdominatingDeoptimizeCall
const CallInst * getPostdominatingDeoptimizeCall() const
Returns the call instruction calling @llvm.experimental.deoptimize that is present either in current ...
Definition: BasicBlock.cpp:200
INITIALIZE_PASS_END
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:58
LoopInfo.h
llvm::BranchInst::getCondition
Value * getCondition() const
Definition: Instructions.h:3149
INITIALIZE_PASS_BEGIN
INITIALIZE_PASS_BEGIN(LoopPredicationLegacyPass, "loop-predication", "Loop predication", false, false) INITIALIZE_PASS_END(LoopPredicationLegacyPass
llvm::getLoopPassPreservedAnalyses
PreservedAnalyses getLoopPassPreservedAnalyses()
Returns the minimum set of Analyses that all loop passes must preserve.
Definition: LoopAnalysisManager.cpp:140
llvm::cl::opt< bool >
llvm::SCEV
This class represents an analyzed expression in the program.
Definition: ScalarEvolution.h:78
STATISTIC
STATISTIC(TotalConsidered, "Number of guards considered")
BranchProbabilityInfo.h
llvm::ICmpInst
This instruction compares its operands according to the predicate given to the constructor.
Definition: Instructions.h:1203
llvm::LoopPass
Definition: LoopPass.h:27
llvm::MemorySSAUpdater
Definition: MemorySSAUpdater.h:56
llvm::LPMUpdater
This class provides an interface for updating the loop pass manager based on mutations to the loop ne...
Definition: LoopPassManager.h:249
INITIALIZE_PASS_DEPENDENCY
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
I
#define I(x, y, z)
Definition: MD5.cpp:59
llvm::succ_begin
Interval::succ_iterator succ_begin(Interval *I)
succ_begin/succ_end - define methods so that Intervals may be used just like BasicBlocks can with the...
Definition: Interval.h:99
llvm::cl::init
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:443
llvm::LoopBase::getLoopPreheader
BlockT * getLoopPreheader() const
If there is a preheader for this loop, return it.
Definition: LoopInfoImpl.h:167
llvm::PatternMatch::m_And
BinaryOp_match< LHS, RHS, Instruction::And > m_And(const LHS &L, const RHS &R)
Definition: PatternMatch.h:1123
llvm::ScalarEvolution::getMonotonicPredicateType
Optional< MonotonicPredicateType > getMonotonicPredicateType(const SCEVAddRecExpr *LHS, ICmpInst::Predicate Pred)
If, for all loop invariant X, the predicate "LHS `Pred` X" is monotonically increasing or decreasing,...
Definition: ScalarEvolution.cpp:9959
llvm::LoopBase::getLoopLatch
BlockT * getLoopLatch() const
If there is a single latch block for this loop, return it.
Definition: LoopInfoImpl.h:216
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
std::swap
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:840
llvm::widenWidenableBranch
void widenWidenableBranch(BranchInst *WidenableBR, Value *NewCond)
Given a branch we know is widenable (defined per Analysis/GuardUtils.h), widen it such that condition...
Definition: GuardUtils.cpp:82
llvm::CmpInst::ICMP_UGE
@ ICMP_UGE
unsigned greater or equal
Definition: InstrTypes.h:744
llvm::Module
A Module instance is used to store all the information related to an LLVM module.
Definition: Module.h:67
predication
loop predication
Definition: LoopPredication.cpp:359
llvm::MemorySSAAnalysis
An analysis that produces MemorySSA for a function.
Definition: MemorySSA.h:931
Builder
assume Assume Builder
Definition: AssumeBundleBuilder.cpp:651
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:1113
llvm::User::setOperand
void setOperand(unsigned i, Value *Val)
Definition: User.h:174
llvm::CmpInst::ICMP_SLT
@ ICMP_SLT
signed less than
Definition: InstrTypes.h:749
llvm::ArrayRef
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: APInt.h:32
llvm::LoopInfo
Definition: LoopInfo.h:1083
llvm::parseWidenableBranch
bool parseWidenableBranch(const User *U, Value *&Condition, Value *&WidenableCondition, BasicBlock *&IfTrueBB, BasicBlock *&IfFalseBB)
If U is widenable branch looking like: cond = ...
Definition: GuardUtils.cpp:44
Cond
SmallVector< MachineOperand, 4 > Cond
Definition: BasicBlockSections.cpp:179
llvm::CmpInst::ICMP_ULT
@ ICMP_ULT
unsigned less than
Definition: InstrTypes.h:745
LoopPass.h
llvm::Value::getType
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:256
llvm::AnalysisUsage::addPreserved
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
Definition: PassAnalysisSupport.h:98
llvm::BranchProbability
Definition: BranchProbability.h:30
DL
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
Definition: AArch64SLSHardening.cpp:76
llvm::LoopStandardAnalysisResults::LI
LoopInfo & LI
Definition: LoopAnalysisManager.h:56
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
llvm::Loop::hasLoopInvariantOperands
bool hasLoopInvariantOperands(const Instruction *I) const
Return true if all the operands of the specified instruction are loop invariant.
Definition: LoopInfo.cpp:70
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
normalizePredicate
static void normalizePredicate(ScalarEvolution *SE, Loop *L, LoopICmp &RC)
Definition: LoopPredication.cpp:675
llvm::BasicBlock::getContext
LLVMContext & getContext() const
Get the context in which this basic block lives.
Definition: BasicBlock.cpp:32
llvm::SCEVAddRecExpr::getLoop
const Loop * getLoop() const
Definition: ScalarEvolutionExpressions.h:364
llvm::ConstantInt::getTrue
static ConstantInt * getTrue(LLVMContext &Context)
Definition: Constants.cpp:848
llvm::AMDGPU::SendMsg::Op
Op
Definition: SIDefines.h:321
llvm::PreservedAnalyses::all
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:161
llvm::isGuardAsWidenableBranch
bool isGuardAsWidenableBranch(const User *U)
Returns true iff U has semantics of a guard expressed in a form of a widenable conditional branch to ...
Definition: GuardUtils.cpp:29
llvm::MemorySSA::BeforeTerminator
@ BeforeTerminator
Definition: MemorySSA.h:793
llvm::SCEVAddRecExpr
This node represents a polynomial recurrence on the trip count of the specified loop.
Definition: ScalarEvolutionExpressions.h:352
Function.h
llvm::SCEVUnknown
This means that we are dealing with an entirely unknown SCEV value, and only represent it as its LLVM...
Definition: ScalarEvolutionExpressions.h:530
llvm::LoopBase::getHeader
BlockT * getHeader() const
Definition: LoopInfo.h:104
llvm::SCEV::isOne
bool isOne() const
Return true if the expression is a constant one.
Definition: ScalarEvolution.cpp:415
llvm::ScalarEvolution::getCouldNotCompute
const SCEV * getCouldNotCompute()
Definition: ScalarEvolution.cpp:3964
llvm::Loop::dump
void dump() const
Definition: LoopInfo.cpp:669
llvm::CmpInst::ICMP_SGE
@ ICMP_SGE
signed greater or equal
Definition: InstrTypes.h:748
llvm::LoopStandardAnalysisResults::SE
ScalarEvolution & SE
Definition: LoopAnalysisManager.h:57
llvm::LoopStandardAnalysisResults::AA
AAResults & AA
Definition: LoopAnalysisManager.h:53
llvm::IntrinsicInst
A wrapper class for inspecting calls to intrinsic functions.
Definition: IntrinsicInst.h:45
isSafeToTruncateWideIVType
static bool isSafeToTruncateWideIVType(const DataLayout &DL, ScalarEvolution &SE, const LoopICmp LatchCheck, Type *RangeCheckType)
Definition: LoopPredication.cpp:451
GuardUtils.h
ScalarEvolutionExpressions.h
llvm::Pass
Pass interface - Implemented by all 'passes'.
Definition: Pass.h:91
MemorySSA.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:2653
llvm::createLoopPredicationPass
Pass * createLoopPredicationPass()
Definition: LoopPredication.cpp:362
PredicateWidenableBranchGuards
static cl::opt< bool > PredicateWidenableBranchGuards("loop-predication-predicate-widenable-branches-to-deopt", cl::Hidden, cl::desc("Whether or not we should predicate guards " "expressed as widenable branches to deoptimize blocks"), cl::init(true))
llvm::CmpInst::ICMP_UGT
@ ICMP_UGT
unsigned greater than
Definition: InstrTypes.h:743
llvm::CmpInst::getPredicate
Predicate getPredicate() const
Return the predicate for this instruction.
Definition: InstrTypes.h:796
llvm::LoopStandardAnalysisResults::MSSA
MemorySSA * MSSA
Definition: LoopAnalysisManager.h:61
llvm::PatternMatch
Definition: PatternMatch.h:47
llvm::SmallVectorImpl< 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
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::VerifyMemorySSA
bool VerifyMemorySSA
Enables verification of MemorySSA.
Definition: MemorySSA.cpp:91
llvm::User::getOperand
Value * getOperand(unsigned i) const
Definition: User.h:169
llvm::cl::desc
Definition: CommandLine.h:414
llvm::BranchInst
Conditional or Unconditional Branch instruction.
Definition: Instructions.h:3068
LoopPredication.h
FindWidenableTerminatorAboveLoop
static BranchInst * FindWidenableTerminatorAboveLoop(Loop *L, LoopInfo &LI)
If we can (cheaply) find a widenable branch which controls entry into the loop, return it.
Definition: LoopPredication.cpp:985
llvm::LoopStandardAnalysisResults::TLI
TargetLibraryInfo & TLI
Definition: LoopAnalysisManager.h:58
InitializePasses.h
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:7260
Debug.h
LatchExitProbabilityScale
static cl::opt< float > LatchExitProbabilityScale("loop-predication-latch-probability-scale", cl::Hidden, cl::init(2.0), cl::desc("scale factor for the latch probability. Value should be greater " "than 1. Lower values are ignored"))
llvm::BranchInst::isConditional
bool isConditional() const
Definition: Instructions.h:3147
llvm::BranchInst::getSuccessor
BasicBlock * getSuccessor(unsigned i) const
Definition: Instructions.h:3161
EnableCountDownLoop
static cl::opt< bool > EnableCountDownLoop("loop-predication-enable-count-down-loop", cl::Hidden, cl::init(true))
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
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:37