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