LLVM  9.0.0svn
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"
189 #include "llvm/IR/Function.h"
190 #include "llvm/IR/GlobalValue.h"
191 #include "llvm/IR/IntrinsicInst.h"
192 #include "llvm/IR/Module.h"
193 #include "llvm/IR/PatternMatch.h"
194 #include "llvm/Pass.h"
195 #include "llvm/Support/Debug.h"
196 #include "llvm/Transforms/Scalar.h"
199 
200 #define DEBUG_TYPE "loop-predication"
201 
202 STATISTIC(TotalConsidered, "Number of guards considered");
203 STATISTIC(TotalWidened, "Number of checks widened");
204 
205 using namespace llvm;
206 
207 static cl::opt<bool> EnableIVTruncation("loop-predication-enable-iv-truncation",
208  cl::Hidden, cl::init(true));
209 
210 static cl::opt<bool> EnableCountDownLoop("loop-predication-enable-count-down-loop",
211  cl::Hidden, cl::init(true));
212 
213 static cl::opt<bool>
214  SkipProfitabilityChecks("loop-predication-skip-profitability-checks",
215  cl::Hidden, cl::init(false));
216 
217 // This is the scale factor for the latch probability. We use this during
218 // profitability analysis to find other exiting blocks that have a much higher
219 // probability of exiting the loop instead of loop exiting via latch.
220 // This value should be greater than 1 for a sane profitability check.
222  "loop-predication-latch-probability-scale", cl::Hidden, cl::init(2.0),
223  cl::desc("scale factor for the latch probability. Value should be greater "
224  "than 1. Lower values are ignored"));
225 
227  "loop-predication-predicate-widenable-branches-to-deopt", cl::Hidden,
228  cl::desc("Whether or not we should predicate guards "
229  "expressed as widenable branches to deoptimize blocks"),
230  cl::init(true));
231 
232 namespace {
233 class LoopPredication {
234  /// Represents an induction variable check:
235  /// icmp Pred, <induction variable>, <loop invariant limit>
236  struct LoopICmp {
237  ICmpInst::Predicate Pred;
238  const SCEVAddRecExpr *IV;
239  const SCEV *Limit;
240  LoopICmp(ICmpInst::Predicate Pred, const SCEVAddRecExpr *IV,
241  const SCEV *Limit)
242  : Pred(Pred), IV(IV), Limit(Limit) {}
243  LoopICmp() {}
244  void dump() {
245  dbgs() << "LoopICmp Pred = " << Pred << ", IV = " << *IV
246  << ", Limit = " << *Limit << "\n";
247  }
248  };
249 
250  AliasAnalysis *AA;
251  ScalarEvolution *SE;
253 
254  Loop *L;
255  const DataLayout *DL;
256  BasicBlock *Preheader;
257  LoopICmp LatchCheck;
258 
259  bool isSupportedStep(const SCEV* Step);
260  Optional<LoopICmp> parseLoopICmp(ICmpInst *ICI) {
261  return parseLoopICmp(ICI->getPredicate(), ICI->getOperand(0),
262  ICI->getOperand(1));
263  }
264  Optional<LoopICmp> parseLoopICmp(ICmpInst::Predicate Pred, Value *LHS,
265  Value *RHS);
266 
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 seperately.
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. We identify such unprofitable loops through BPI.
307  bool isLoopProfitableToPredicate();
308 
309  // When the IV type is wider than the range operand type, we can still do loop
310  // predication, by generating SCEVs for the range and latch that are of the
311  // same type. We achieve this by generating a SCEV truncate expression for the
312  // latch IV. This is done iff truncation of the IV is a safe operation,
313  // without loss of information.
314  // Another way to achieve this is by generating a wider type SCEV for the
315  // range check operand, however, this needs a more involved check that
316  // operands do not overflow. This can lead to loss of information when the
317  // range operand is of the form: add i32 %offset, %iv. We need to prove that
318  // sext(x + y) is same as sext(x) + sext(y).
319  // This function returns true if we can safely represent the IV type in
320  // the RangeCheckType without loss of information.
321  bool isSafeToTruncateWideIVType(Type *RangeCheckType);
322  // Return the loopLatchCheck corresponding to the RangeCheckType if safe to do
323  // so.
324  Optional<LoopICmp> generateLoopLatchCheck(Type *RangeCheckType);
325 
326 public:
327  LoopPredication(AliasAnalysis *AA, ScalarEvolution *SE,
329  : AA(AA), SE(SE), BPI(BPI){};
330  bool runOnLoop(Loop *L);
331 };
332 
333 class LoopPredicationLegacyPass : public LoopPass {
334 public:
335  static char ID;
336  LoopPredicationLegacyPass() : LoopPass(ID) {
338  }
339 
340  void getAnalysisUsage(AnalysisUsage &AU) const override {
343  }
344 
345  bool runOnLoop(Loop *L, LPPassManager &LPM) override {
346  if (skipLoop(L))
347  return false;
348  auto *SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
349  BranchProbabilityInfo &BPI =
350  getAnalysis<BranchProbabilityInfoWrapperPass>().getBPI();
351  auto *AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
352  LoopPredication LP(AA, SE, &BPI);
353  return LP.runOnLoop(L);
354  }
355 };
356 
358 } // end namespace llvm
359 
360 INITIALIZE_PASS_BEGIN(LoopPredicationLegacyPass, "loop-predication",
361  "Loop predication", false, false)
364 INITIALIZE_PASS_END(LoopPredicationLegacyPass, "loop-predication",
365  "Loop predication", false, false)
366 
368  return new LoopPredicationLegacyPass();
369 }
370 
373  LPMUpdater &U) {
374  const auto &FAM =
375  AM.getResult<FunctionAnalysisManagerLoopProxy>(L, AR).getManager();
376  Function *F = L.getHeader()->getParent();
377  auto *BPI = FAM.getCachedResult<BranchProbabilityAnalysis>(*F);
378  LoopPredication LP(&AR.AA, &AR.SE, BPI);
379  if (!LP.runOnLoop(&L))
380  return PreservedAnalyses::all();
381 
383 }
384 
386 LoopPredication::parseLoopICmp(ICmpInst::Predicate Pred, Value *LHS,
387  Value *RHS) {
388  const SCEV *LHSS = SE->getSCEV(LHS);
389  if (isa<SCEVCouldNotCompute>(LHSS))
390  return None;
391  const SCEV *RHSS = SE->getSCEV(RHS);
392  if (isa<SCEVCouldNotCompute>(RHSS))
393  return None;
394 
395  // Canonicalize RHS to be loop invariant bound, LHS - a loop computable IV
396  if (SE->isLoopInvariant(LHSS, L)) {
397  std::swap(LHS, RHS);
398  std::swap(LHSS, RHSS);
399  Pred = ICmpInst::getSwappedPredicate(Pred);
400  }
401 
402  const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(LHSS);
403  if (!AR || AR->getLoop() != L)
404  return None;
405 
406  return LoopICmp(Pred, AR, RHSS);
407 }
408 
409 Value *LoopPredication::expandCheck(SCEVExpander &Expander,
410  Instruction *Guard,
411  ICmpInst::Predicate Pred, const SCEV *LHS,
412  const SCEV *RHS) {
413  Type *Ty = LHS->getType();
414  assert(Ty == RHS->getType() && "expandCheck operands have different types?");
415 
416  if (SE->isLoopInvariant(LHS, L) && SE->isLoopInvariant(RHS, L)) {
417  IRBuilder<> Builder(Guard);
418  if (SE->isLoopEntryGuardedByCond(L, Pred, LHS, RHS))
419  return Builder.getTrue();
421  LHS, RHS))
422  return Builder.getFalse();
423  }
424 
425  Value *LHSV = Expander.expandCodeFor(LHS, Ty, findInsertPt(Guard, {LHS}));
426  Value *RHSV = Expander.expandCodeFor(RHS, Ty, findInsertPt(Guard, {RHS}));
427  IRBuilder<> Builder(findInsertPt(Guard, {LHSV, RHSV}));
428  return Builder.CreateICmp(Pred, LHSV, RHSV);
429 }
430 
432 LoopPredication::generateLoopLatchCheck(Type *RangeCheckType) {
433 
434  auto *LatchType = LatchCheck.IV->getType();
435  if (RangeCheckType == LatchType)
436  return LatchCheck;
437  // For now, bail out if latch type is narrower than range type.
438  if (DL->getTypeSizeInBits(LatchType) < DL->getTypeSizeInBits(RangeCheckType))
439  return None;
440  if (!isSafeToTruncateWideIVType(RangeCheckType))
441  return None;
442  // We can now safely identify the truncated version of the IV and limit for
443  // RangeCheckType.
444  LoopICmp NewLatchCheck;
445  NewLatchCheck.Pred = LatchCheck.Pred;
446  NewLatchCheck.IV = dyn_cast<SCEVAddRecExpr>(
447  SE->getTruncateExpr(LatchCheck.IV, RangeCheckType));
448  if (!NewLatchCheck.IV)
449  return None;
450  NewLatchCheck.Limit = SE->getTruncateExpr(LatchCheck.Limit, RangeCheckType);
451  LLVM_DEBUG(dbgs() << "IV of type: " << *LatchType
452  << "can be represented as range check type:"
453  << *RangeCheckType << "\n");
454  LLVM_DEBUG(dbgs() << "LatchCheck.IV: " << *NewLatchCheck.IV << "\n");
455  LLVM_DEBUG(dbgs() << "LatchCheck.Limit: " << *NewLatchCheck.Limit << "\n");
456  return NewLatchCheck;
457 }
458 
459 bool LoopPredication::isSupportedStep(const SCEV* Step) {
460  return Step->isOne() || (Step->isAllOnesValue() && EnableCountDownLoop);
461 }
462 
463 Instruction *LoopPredication::findInsertPt(Instruction *Use,
464  ArrayRef<Value*> Ops) {
465  for (Value *Op : Ops)
466  if (!L->isLoopInvariant(Op))
467  return Use;
468  return Preheader->getTerminator();
469 }
470 
471 Instruction *LoopPredication::findInsertPt(Instruction *Use,
472  ArrayRef<const SCEV*> Ops) {
473  // Subtlety: SCEV considers things to be invariant if the value produced is
474  // the same across iterations. This is not the same as being able to
475  // evaluate outside the loop, which is what we actually need here.
476  for (const SCEV *Op : Ops)
477  if (!SE->isLoopInvariant(Op, L) ||
478  !isSafeToExpandAt(Op, Preheader->getTerminator(), *SE))
479  return Use;
480  return Preheader->getTerminator();
481 }
482 
483 bool LoopPredication::isLoopInvariantValue(const SCEV* S) {
484  // Handling expressions which produce invariant results, but *haven't* yet
485  // been removed from the loop serves two important purposes.
486  // 1) Most importantly, it resolves a pass ordering cycle which would
487  // otherwise need us to iteration licm, loop-predication, and either
488  // loop-unswitch or loop-peeling to make progress on examples with lots of
489  // predicable range checks in a row. (Since, in the general case, we can't
490  // hoist the length checks until the dominating checks have been discharged
491  // as we can't prove doing so is safe.)
492  // 2) As a nice side effect, this exposes the value of peeling or unswitching
493  // much more obviously in the IR. Otherwise, the cost modeling for other
494  // transforms would end up needing to duplicate all of this logic to model a
495  // check which becomes predictable based on a modeled peel or unswitch.
496  //
497  // The cost of doing so in the worst case is an extra fill from the stack in
498  // the loop to materialize the loop invariant test value instead of checking
499  // against the original IV which is presumable in a register inside the loop.
500  // Such cases are presumably rare, and hint at missing oppurtunities for
501  // other passes.
502 
503  if (SE->isLoopInvariant(S, L))
504  // Note: This the SCEV variant, so the original Value* may be within the
505  // loop even though SCEV has proven it is loop invariant.
506  return true;
507 
508  // Handle a particular important case which SCEV doesn't yet know about which
509  // shows up in range checks on arrays with immutable lengths.
510  // TODO: This should be sunk inside SCEV.
511  if (const SCEVUnknown *U = dyn_cast<SCEVUnknown>(S))
512  if (const auto *LI = dyn_cast<LoadInst>(U->getValue()))
513  if (LI->isUnordered() && L->hasLoopInvariantOperands(LI))
514  if (AA->pointsToConstantMemory(LI->getOperand(0)) ||
515  LI->getMetadata(LLVMContext::MD_invariant_load) != nullptr)
516  return true;
517  return false;
518 }
519 
520 Optional<Value *> LoopPredication::widenICmpRangeCheckIncrementingLoop(
521  LoopPredication::LoopICmp LatchCheck, LoopPredication::LoopICmp RangeCheck,
522  SCEVExpander &Expander, Instruction *Guard) {
523  auto *Ty = RangeCheck.IV->getType();
524  // Generate the widened condition for the forward loop:
525  // guardStart u< guardLimit &&
526  // latchLimit <pred> guardLimit - 1 - guardStart + latchStart
527  // where <pred> depends on the latch condition predicate. See the file
528  // header comment for the reasoning.
529  // guardLimit - guardStart + latchStart - 1
530  const SCEV *GuardStart = RangeCheck.IV->getStart();
531  const SCEV *GuardLimit = RangeCheck.Limit;
532  const SCEV *LatchStart = LatchCheck.IV->getStart();
533  const SCEV *LatchLimit = LatchCheck.Limit;
534  // Subtlety: We need all the values to be *invariant* across all iterations,
535  // but we only need to check expansion safety for those which *aren't*
536  // already guaranteed to dominate the guard.
537  if (!isLoopInvariantValue(GuardStart) ||
538  !isLoopInvariantValue(GuardLimit) ||
539  !isLoopInvariantValue(LatchStart) ||
540  !isLoopInvariantValue(LatchLimit)) {
541  LLVM_DEBUG(dbgs() << "Can't expand limit check!\n");
542  return None;
543  }
544  if (!isSafeToExpandAt(LatchStart, Guard, *SE) ||
545  !isSafeToExpandAt(LatchLimit, Guard, *SE)) {
546  LLVM_DEBUG(dbgs() << "Can't expand limit check!\n");
547  return None;
548  }
549 
550  // guardLimit - guardStart + latchStart - 1
551  const SCEV *RHS =
552  SE->getAddExpr(SE->getMinusSCEV(GuardLimit, GuardStart),
553  SE->getMinusSCEV(LatchStart, SE->getOne(Ty)));
554  auto LimitCheckPred =
556 
557  LLVM_DEBUG(dbgs() << "LHS: " << *LatchLimit << "\n");
558  LLVM_DEBUG(dbgs() << "RHS: " << *RHS << "\n");
559  LLVM_DEBUG(dbgs() << "Pred: " << LimitCheckPred << "\n");
560 
561  auto *LimitCheck =
562  expandCheck(Expander, Guard, LimitCheckPred, LatchLimit, RHS);
563  auto *FirstIterationCheck = expandCheck(Expander, Guard, RangeCheck.Pred,
564  GuardStart, GuardLimit);
565  IRBuilder<> Builder(findInsertPt(Guard, {FirstIterationCheck, LimitCheck}));
566  return Builder.CreateAnd(FirstIterationCheck, LimitCheck);
567 }
568 
569 Optional<Value *> LoopPredication::widenICmpRangeCheckDecrementingLoop(
570  LoopPredication::LoopICmp LatchCheck, LoopPredication::LoopICmp RangeCheck,
571  SCEVExpander &Expander, Instruction *Guard) {
572  auto *Ty = RangeCheck.IV->getType();
573  const SCEV *GuardStart = RangeCheck.IV->getStart();
574  const SCEV *GuardLimit = RangeCheck.Limit;
575  const SCEV *LatchStart = LatchCheck.IV->getStart();
576  const SCEV *LatchLimit = LatchCheck.Limit;
577  // Subtlety: We need all the values to be *invariant* across all iterations,
578  // but we only need to check expansion safety for those which *aren't*
579  // already guaranteed to dominate the guard.
580  if (!isLoopInvariantValue(GuardStart) ||
581  !isLoopInvariantValue(GuardLimit) ||
582  !isLoopInvariantValue(LatchStart) ||
583  !isLoopInvariantValue(LatchLimit)) {
584  LLVM_DEBUG(dbgs() << "Can't expand limit check!\n");
585  return None;
586  }
587  if (!isSafeToExpandAt(LatchStart, Guard, *SE) ||
588  !isSafeToExpandAt(LatchLimit, Guard, *SE)) {
589  LLVM_DEBUG(dbgs() << "Can't expand limit check!\n");
590  return None;
591  }
592  // The decrement of the latch check IV should be the same as the
593  // rangeCheckIV.
594  auto *PostDecLatchCheckIV = LatchCheck.IV->getPostIncExpr(*SE);
595  if (RangeCheck.IV != PostDecLatchCheckIV) {
596  LLVM_DEBUG(dbgs() << "Not the same. PostDecLatchCheckIV: "
597  << *PostDecLatchCheckIV
598  << " and RangeCheckIV: " << *RangeCheck.IV << "\n");
599  return None;
600  }
601 
602  // Generate the widened condition for CountDownLoop:
603  // guardStart u< guardLimit &&
604  // latchLimit <pred> 1.
605  // See the header comment for reasoning of the checks.
606  auto LimitCheckPred =
608  auto *FirstIterationCheck = expandCheck(Expander, Guard,
610  GuardStart, GuardLimit);
611  auto *LimitCheck = expandCheck(Expander, Guard, LimitCheckPred, LatchLimit,
612  SE->getOne(Ty));
613  IRBuilder<> Builder(findInsertPt(Guard, {FirstIterationCheck, LimitCheck}));
614  return Builder.CreateAnd(FirstIterationCheck, LimitCheck);
615 }
616 
617 /// If ICI can be widened to a loop invariant condition emits the loop
618 /// invariant condition in the loop preheader and return it, otherwise
619 /// returns None.
620 Optional<Value *> LoopPredication::widenICmpRangeCheck(ICmpInst *ICI,
621  SCEVExpander &Expander,
622  Instruction *Guard) {
623  LLVM_DEBUG(dbgs() << "Analyzing ICmpInst condition:\n");
624  LLVM_DEBUG(ICI->dump());
625 
626  // parseLoopStructure guarantees that the latch condition is:
627  // ++i <pred> latchLimit, where <pred> is u<, u<=, s<, or s<=.
628  // We are looking for the range checks of the form:
629  // i u< guardLimit
630  auto RangeCheck = parseLoopICmp(ICI);
631  if (!RangeCheck) {
632  LLVM_DEBUG(dbgs() << "Failed to parse the loop latch condition!\n");
633  return None;
634  }
635  LLVM_DEBUG(dbgs() << "Guard check:\n");
636  LLVM_DEBUG(RangeCheck->dump());
637  if (RangeCheck->Pred != ICmpInst::ICMP_ULT) {
638  LLVM_DEBUG(dbgs() << "Unsupported range check predicate("
639  << RangeCheck->Pred << ")!\n");
640  return None;
641  }
642  auto *RangeCheckIV = RangeCheck->IV;
643  if (!RangeCheckIV->isAffine()) {
644  LLVM_DEBUG(dbgs() << "Range check IV is not affine!\n");
645  return None;
646  }
647  auto *Step = RangeCheckIV->getStepRecurrence(*SE);
648  // We cannot just compare with latch IV step because the latch and range IVs
649  // may have different types.
650  if (!isSupportedStep(Step)) {
651  LLVM_DEBUG(dbgs() << "Range check and latch have IVs different steps!\n");
652  return None;
653  }
654  auto *Ty = RangeCheckIV->getType();
655  auto CurrLatchCheckOpt = generateLoopLatchCheck(Ty);
656  if (!CurrLatchCheckOpt) {
657  LLVM_DEBUG(dbgs() << "Failed to generate a loop latch check "
658  "corresponding to range type: "
659  << *Ty << "\n");
660  return None;
661  }
662 
663  LoopICmp CurrLatchCheck = *CurrLatchCheckOpt;
664  // At this point, the range and latch step should have the same type, but need
665  // not have the same value (we support both 1 and -1 steps).
666  assert(Step->getType() ==
667  CurrLatchCheck.IV->getStepRecurrence(*SE)->getType() &&
668  "Range and latch steps should be of same type!");
669  if (Step != CurrLatchCheck.IV->getStepRecurrence(*SE)) {
670  LLVM_DEBUG(dbgs() << "Range and latch have different step values!\n");
671  return None;
672  }
673 
674  if (Step->isOne())
675  return widenICmpRangeCheckIncrementingLoop(CurrLatchCheck, *RangeCheck,
676  Expander, Guard);
677  else {
678  assert(Step->isAllOnesValue() && "Step should be -1!");
679  return widenICmpRangeCheckDecrementingLoop(CurrLatchCheck, *RangeCheck,
680  Expander, Guard);
681  }
682 }
683 
684 unsigned LoopPredication::collectChecks(SmallVectorImpl<Value *> &Checks,
685  Value *Condition,
686  SCEVExpander &Expander,
687  Instruction *Guard) {
688  unsigned NumWidened = 0;
689  // The guard condition is expected to be in form of:
690  // cond1 && cond2 && cond3 ...
691  // Iterate over subconditions looking for icmp conditions which can be
692  // widened across loop iterations. Widening these conditions remember the
693  // resulting list of subconditions in Checks vector.
694  SmallVector<Value *, 4> Worklist(1, Condition);
695  SmallPtrSet<Value *, 4> Visited;
696  Value *WideableCond = nullptr;
697  do {
698  Value *Condition = Worklist.pop_back_val();
699  if (!Visited.insert(Condition).second)
700  continue;
701 
702  Value *LHS, *RHS;
703  using namespace llvm::PatternMatch;
704  if (match(Condition, m_And(m_Value(LHS), m_Value(RHS)))) {
705  Worklist.push_back(LHS);
706  Worklist.push_back(RHS);
707  continue;
708  }
709 
710  if (match(Condition,
711  m_Intrinsic<Intrinsic::experimental_widenable_condition>())) {
712  // Pick any, we don't care which
713  WideableCond = Condition;
714  continue;
715  }
716 
717  if (ICmpInst *ICI = dyn_cast<ICmpInst>(Condition)) {
718  if (auto NewRangeCheck = widenICmpRangeCheck(ICI, Expander,
719  Guard)) {
720  Checks.push_back(NewRangeCheck.getValue());
721  NumWidened++;
722  continue;
723  }
724  }
725 
726  // Save the condition as is if we can't widen it
727  Checks.push_back(Condition);
728  } while (!Worklist.empty());
729  // At the moment, our matching logic for wideable conditions implicitly
730  // assumes we preserve the form: (br (and Cond, WC())). FIXME
731  // Note that if there were multiple calls to wideable condition in the
732  // traversal, we only need to keep one, and which one is arbitrary.
733  if (WideableCond)
734  Checks.push_back(WideableCond);
735  return NumWidened;
736 }
737 
738 bool LoopPredication::widenGuardConditions(IntrinsicInst *Guard,
739  SCEVExpander &Expander) {
740  LLVM_DEBUG(dbgs() << "Processing guard:\n");
741  LLVM_DEBUG(Guard->dump());
742 
743  TotalConsidered++;
745  unsigned NumWidened = collectChecks(Checks, Guard->getOperand(0), Expander,
746  Guard);
747  if (NumWidened == 0)
748  return false;
749 
750  TotalWidened += NumWidened;
751 
752  // Emit the new guard condition
753  IRBuilder<> Builder(findInsertPt(Guard, Checks));
754  Value *LastCheck = nullptr;
755  for (auto *Check : Checks)
756  if (!LastCheck)
757  LastCheck = Check;
758  else
759  LastCheck = Builder.CreateAnd(LastCheck, Check);
760  auto *OldCond = Guard->getOperand(0);
761  Guard->setOperand(0, LastCheck);
763 
764  LLVM_DEBUG(dbgs() << "Widened checks = " << NumWidened << "\n");
765  return true;
766 }
767 
768 bool LoopPredication::widenWidenableBranchGuardConditions(
769  BranchInst *BI, SCEVExpander &Expander) {
770  assert(isGuardAsWidenableBranch(BI) && "Must be!");
771  LLVM_DEBUG(dbgs() << "Processing guard:\n");
772  LLVM_DEBUG(BI->dump());
773 
774  TotalConsidered++;
776  unsigned NumWidened = collectChecks(Checks, BI->getCondition(),
777  Expander, BI);
778  if (NumWidened == 0)
779  return false;
780 
781  TotalWidened += NumWidened;
782 
783  // Emit the new guard condition
784  IRBuilder<> Builder(findInsertPt(BI, Checks));
785  Value *LastCheck = nullptr;
786  for (auto *Check : Checks)
787  if (!LastCheck)
788  LastCheck = Check;
789  else
790  LastCheck = Builder.CreateAnd(LastCheck, Check);
791  auto *OldCond = BI->getCondition();
792  BI->setCondition(LastCheck);
794  "Stopped being a guard after transform?");
796 
797  LLVM_DEBUG(dbgs() << "Widened checks = " << NumWidened << "\n");
798  return true;
799 }
800 
801 Optional<LoopPredication::LoopICmp> LoopPredication::parseLoopLatchICmp() {
802  using namespace PatternMatch;
803 
804  BasicBlock *LoopLatch = L->getLoopLatch();
805  if (!LoopLatch) {
806  LLVM_DEBUG(dbgs() << "The loop doesn't have a single latch!\n");
807  return None;
808  }
809 
810  ICmpInst::Predicate Pred;
811  Value *LHS, *RHS;
812  BasicBlock *TrueDest, *FalseDest;
813 
814  if (!match(LoopLatch->getTerminator(),
815  m_Br(m_ICmp(Pred, m_Value(LHS), m_Value(RHS)), TrueDest,
816  FalseDest))) {
817  LLVM_DEBUG(dbgs() << "Failed to match the latch terminator!\n");
818  return None;
819  }
820  assert((TrueDest == L->getHeader() || FalseDest == L->getHeader()) &&
821  "One of the latch's destinations must be the header");
822  if (TrueDest != L->getHeader())
823  Pred = ICmpInst::getInversePredicate(Pred);
824 
825  auto Result = parseLoopICmp(Pred, LHS, RHS);
826  if (!Result) {
827  LLVM_DEBUG(dbgs() << "Failed to parse the loop latch condition!\n");
828  return None;
829  }
830 
831  // Check affine first, so if it's not we don't try to compute the step
832  // recurrence.
833  if (!Result->IV->isAffine()) {
834  LLVM_DEBUG(dbgs() << "The induction variable is not affine!\n");
835  return None;
836  }
837 
838  auto *Step = Result->IV->getStepRecurrence(*SE);
839  if (!isSupportedStep(Step)) {
840  LLVM_DEBUG(dbgs() << "Unsupported loop stride(" << *Step << ")!\n");
841  return None;
842  }
843 
844  auto IsUnsupportedPredicate = [](const SCEV *Step, ICmpInst::Predicate Pred) {
845  if (Step->isOne()) {
846  return Pred != ICmpInst::ICMP_ULT && Pred != ICmpInst::ICMP_SLT &&
847  Pred != ICmpInst::ICMP_ULE && Pred != ICmpInst::ICMP_SLE;
848  } else {
849  assert(Step->isAllOnesValue() && "Step should be -1!");
850  return Pred != ICmpInst::ICMP_UGT && Pred != ICmpInst::ICMP_SGT &&
851  Pred != ICmpInst::ICMP_UGE && Pred != ICmpInst::ICMP_SGE;
852  }
853  };
854 
855  if (IsUnsupportedPredicate(Step, Result->Pred)) {
856  LLVM_DEBUG(dbgs() << "Unsupported loop latch predicate(" << Result->Pred
857  << ")!\n");
858  return None;
859  }
860  return Result;
861 }
862 
863 // Returns true if its safe to truncate the IV to RangeCheckType.
864 bool LoopPredication::isSafeToTruncateWideIVType(Type *RangeCheckType) {
865  if (!EnableIVTruncation)
866  return false;
867  assert(DL->getTypeSizeInBits(LatchCheck.IV->getType()) >
868  DL->getTypeSizeInBits(RangeCheckType) &&
869  "Expected latch check IV type to be larger than range check operand "
870  "type!");
871  // The start and end values of the IV should be known. This is to guarantee
872  // that truncating the wide type will not lose information.
873  auto *Limit = dyn_cast<SCEVConstant>(LatchCheck.Limit);
874  auto *Start = dyn_cast<SCEVConstant>(LatchCheck.IV->getStart());
875  if (!Limit || !Start)
876  return false;
877  // This check makes sure that the IV does not change sign during loop
878  // iterations. Consider latchType = i64, LatchStart = 5, Pred = ICMP_SGE,
879  // LatchEnd = 2, rangeCheckType = i32. If it's not a monotonic predicate, the
880  // IV wraps around, and the truncation of the IV would lose the range of
881  // iterations between 2^32 and 2^64.
882  bool Increasing;
883  if (!SE->isMonotonicPredicate(LatchCheck.IV, LatchCheck.Pred, Increasing))
884  return false;
885  // The active bits should be less than the bits in the RangeCheckType. This
886  // guarantees that truncating the latch check to RangeCheckType is a safe
887  // operation.
888  auto RangeCheckTypeBitSize = DL->getTypeSizeInBits(RangeCheckType);
889  return Start->getAPInt().getActiveBits() < RangeCheckTypeBitSize &&
890  Limit->getAPInt().getActiveBits() < RangeCheckTypeBitSize;
891 }
892 
893 bool LoopPredication::isLoopProfitableToPredicate() {
894  if (SkipProfitabilityChecks || !BPI)
895  return true;
896 
898  L->getExitEdges(ExitEdges);
899  // If there is only one exiting edge in the loop, it is always profitable to
900  // predicate the loop.
901  if (ExitEdges.size() == 1)
902  return true;
903 
904  // Calculate the exiting probabilities of all exiting edges from the loop,
905  // starting with the LatchExitProbability.
906  // Heuristic for profitability: If any of the exiting blocks' probability of
907  // exiting the loop is larger than exiting through the latch block, it's not
908  // profitable to predicate the loop.
909  auto *LatchBlock = L->getLoopLatch();
910  assert(LatchBlock && "Should have a single latch at this point!");
911  auto *LatchTerm = LatchBlock->getTerminator();
912  assert(LatchTerm->getNumSuccessors() == 2 &&
913  "expected to be an exiting block with 2 succs!");
914  unsigned LatchBrExitIdx =
915  LatchTerm->getSuccessor(0) == L->getHeader() ? 1 : 0;
916  BranchProbability LatchExitProbability =
917  BPI->getEdgeProbability(LatchBlock, LatchBrExitIdx);
918 
919  // Protect against degenerate inputs provided by the user. Providing a value
920  // less than one, can invert the definition of profitable loop predication.
921  float ScaleFactor = LatchExitProbabilityScale;
922  if (ScaleFactor < 1) {
923  LLVM_DEBUG(
924  dbgs()
925  << "Ignored user setting for loop-predication-latch-probability-scale: "
926  << LatchExitProbabilityScale << "\n");
927  LLVM_DEBUG(dbgs() << "The value is set to 1.0\n");
928  ScaleFactor = 1.0;
929  }
930  const auto LatchProbabilityThreshold =
931  LatchExitProbability * ScaleFactor;
932 
933  for (const auto &ExitEdge : ExitEdges) {
934  BranchProbability ExitingBlockProbability =
935  BPI->getEdgeProbability(ExitEdge.first, ExitEdge.second);
936  // Some exiting edge has higher probability than the latch exiting edge.
937  // No longer profitable to predicate.
938  if (ExitingBlockProbability > LatchProbabilityThreshold)
939  return false;
940  }
941  // Using BPI, we have concluded that the most probable way to exit from the
942  // loop is through the latch (or there's no profile information and all
943  // exits are equally likely).
944  return true;
945 }
946 
947 bool LoopPredication::runOnLoop(Loop *Loop) {
948  L = Loop;
949 
950  LLVM_DEBUG(dbgs() << "Analyzing ");
951  LLVM_DEBUG(L->dump());
952 
953  Module *M = L->getHeader()->getModule();
954 
955  // There is nothing to do if the module doesn't use guards
956  auto *GuardDecl =
957  M->getFunction(Intrinsic::getName(Intrinsic::experimental_guard));
958  bool HasIntrinsicGuards = GuardDecl && !GuardDecl->use_empty();
959  auto *WCDecl = M->getFunction(
960  Intrinsic::getName(Intrinsic::experimental_widenable_condition));
961  bool HasWidenableConditions =
962  PredicateWidenableBranchGuards && WCDecl && !WCDecl->use_empty();
963  if (!HasIntrinsicGuards && !HasWidenableConditions)
964  return false;
965 
966  DL = &M->getDataLayout();
967 
968  Preheader = L->getLoopPreheader();
969  if (!Preheader)
970  return false;
971 
972  auto LatchCheckOpt = parseLoopLatchICmp();
973  if (!LatchCheckOpt)
974  return false;
975  LatchCheck = *LatchCheckOpt;
976 
977  LLVM_DEBUG(dbgs() << "Latch check:\n");
978  LLVM_DEBUG(LatchCheck.dump());
979 
980  if (!isLoopProfitableToPredicate()) {
981  LLVM_DEBUG(dbgs() << "Loop not profitable to predicate!\n");
982  return false;
983  }
984  // Collect all the guards into a vector and process later, so as not
985  // to invalidate the instruction iterator.
987  SmallVector<BranchInst *, 4> GuardsAsWidenableBranches;
988  for (const auto BB : L->blocks()) {
989  for (auto &I : *BB)
990  if (isGuard(&I))
991  Guards.push_back(cast<IntrinsicInst>(&I));
993  isGuardAsWidenableBranch(BB->getTerminator()))
994  GuardsAsWidenableBranches.push_back(
995  cast<BranchInst>(BB->getTerminator()));
996  }
997 
998  if (Guards.empty() && GuardsAsWidenableBranches.empty())
999  return false;
1000 
1001  SCEVExpander Expander(*SE, *DL, "loop-predication");
1002 
1003  bool Changed = false;
1004  for (auto *Guard : Guards)
1005  Changed |= widenGuardConditions(Guard, Expander);
1006  for (auto *Guard : GuardsAsWidenableBranches)
1007  Changed |= widenWidenableBranchGuardConditions(Guard, Expander);
1008 
1009  return Changed;
1010 }
Pass interface - Implemented by all &#39;passes&#39;.
Definition: Pass.h:80
static bool Check(DecodeStatus &Out, DecodeStatus In)
BinaryOp_match< LHS, RHS, Instruction::And > m_And(const LHS &L, const RHS &R)
Definition: PatternMatch.h:756
A parsed version of the target data layout string in and methods for querying it. ...
Definition: DataLayout.h:110
class_match< Value > m_Value()
Match an arbitrary value and ignore it.
Definition: PatternMatch.h:70
Value * CreateICmp(CmpInst::Predicate P, Value *LHS, Value *RHS, const Twine &Name="")
Definition: IRBuilder.h:1984
BlockT * getLoopLatch() const
If there is a single latch block for this loop, return it.
Definition: LoopInfoImpl.h:224
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
PreservedAnalyses getLoopPassPreservedAnalyses()
Returns the minimum set of Analyses that all loop passes must preserve.
STATISTIC(TotalConsidered, "Number of guards considered")
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:776
This class represents lattice values for constants.
Definition: AllocatorList.h:23
loop predication
A Module instance is used to store all the information related to an LLVM module. ...
Definition: Module.h:65
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...
The main scalar evolution driver.
BlockT * getLoopPreheader() const
If there is a preheader for this loop, return it.
Definition: LoopInfoImpl.h:173
unsigned less or equal
Definition: InstrTypes.h:735
unsigned less than
Definition: InstrTypes.h:734
bool isLoopInvariant(const SCEV *S, const Loop *L)
Return true if the value of the given SCEV is unchanging in the specified loop.
bool isMonotonicPredicate(const SCEVAddRecExpr *LHS, ICmpInst::Predicate Pred, bool &Increasing)
Return true if, for all loop invariant X, the predicate "LHS `Pred` X" is monotonically increasing or...
The adaptor from a function pass to a loop pass computes these analyses and makes them available to t...
F(f)
Value * getCondition() const
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:137
bool hasLoopInvariantOperands(const Instruction *I) const
Return true if all the operands of the specified instruction are loop invariant.
Definition: LoopInfo.cpp:65
INITIALIZE_PASS_BEGIN(LoopPredicationLegacyPass, "loop-predication", "Loop predication", false, false) INITIALIZE_PASS_END(LoopPredicationLegacyPass
void dump() const
Support for debugging, callable in GDB: V->dump()
Definition: AsmWriter.cpp:4362
bool match(Val *V, const Pattern &P)
Definition: PatternMatch.h:47
AnalysisUsage & addRequired()
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:133
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:50
StringRef getName(ID id)
Return the LLVM name for an intrinsic, such as "llvm.ppc.altivec.lvx".
Definition: Function.cpp:629
Predicate getInversePredicate() const
For example, EQ -> NE, UGT -> ULE, SLT -> SGE, OEQ -> UNE, UGT -> OLE, OLT -> UGE, etc.
Definition: InstrTypes.h:808
A Use represents the edge between a Value definition and its users.
Definition: Use.h:55
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"))
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
Definition: IRBuilder.h:742
BlockT * getHeader() const
Definition: LoopInfo.h:100
Analysis pass which computes BranchProbabilityInfo.
This node represents a polynomial recurrence on the trip count of the specified loop.
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory)...
Definition: APInt.h:32
Legacy analysis pass which computes BranchProbabilityInfo.
Value * getOperand(unsigned i) const
Definition: User.h:169
static cl::opt< bool > EnableIVTruncation("loop-predication-enable-iv-truncation", cl::Hidden, cl::init(true))
bool isLoopEntryGuardedByCond(const Loop *L, ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS)
Test whether entry to the loop is protected by a conditional between LHS and RHS. ...
bool pointsToConstantMemory(const MemoryLocation &Loc, bool OrLocal=false)
Checks whether the given location points to constant memory, or if OrLocal is true whether it points ...
This means that we are dealing with an entirely unknown SCEV value, and only represent it as its LLVM...
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:432
void dump(const SparseBitVector< ElementSize > &LHS, raw_ostream &out)
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:153
const SCEV * getOne(Type *Ty)
Return a SCEV for the constant 1 of a specific type.
void dump() const
Definition: LoopInfo.cpp:391
LLVM Basic Block Representation.
Definition: BasicBlock.h:57
The instances of the Type class are immutable: once they are created, they are never changed...
Definition: Type.h:45
ConstantInt * getTrue()
Get the constant value for i1 true.
Definition: IRBuilder.h:286
Conditional or Unconditional Branch instruction.
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:370
const SCEV * getAddExpr(SmallVectorImpl< const SCEV *> &Ops, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
Get a canonical add expression, or something simpler if possible.
brc_match< Cond_t > m_Br(const Cond_t &C, BasicBlock *&T, BasicBlock *&F)
Represent the analysis usage information of a pass.
Pass * createLoopPredicationPass()
This instruction compares its operands according to the predicate given to the constructor.
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Definition: InstrTypes.h:709
Value * expandCodeFor(const SCEV *SH, Type *Ty, Instruction *I)
Insert code to directly compute the specified SCEV expression into the program.
const SCEV * getMinusSCEV(const SCEV *LHS, const SCEV *RHS, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
Return LHS-RHS. Minus is represented in SCEV as A+B*-1.
bool RecursivelyDeleteTriviallyDeadInstructions(Value *V, const TargetLibraryInfo *TLI=nullptr, MemorySSAUpdater *MSSAU=nullptr)
If the specified value is a trivially dead instruction, delete it.
Definition: Local.cpp:434
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:159
size_t size() const
Definition: SmallVector.h:52
INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false) RegBankSelect
bool isLoopInvariant(const Value *V) const
Return true if the specified value is loop invariant.
Definition: LoopInfo.cpp:59
signed greater than
Definition: InstrTypes.h:736
BranchProbability getEdgeProbability(const BasicBlock *Src, unsigned IndexInSuccessors) const
Get an edge&#39;s probability, relative to other out-edges of the Src.
void getExitEdges(SmallVectorImpl< Edge > &ExitEdges) const
Return all pairs of (inside_block,outside_block).
Definition: LoopInfoImpl.h:154
This class provides an interface for updating the loop pass manager based on mutations to the loop ne...
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements...
Definition: SmallPtrSet.h:417
bool isAllOnesValue() const
Return true if the expression is a constant all-ones value.
Type * getType() const
Return the LLVM type of this SCEV expression.
An analysis over an "inner" IR unit that provides access to an analysis manager over a "outer" IR uni...
Definition: PassManager.h:1160
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:841
Module.h This file contains the declarations for the Module class.
signed less than
Definition: InstrTypes.h:738
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:374
Predicate getFlippedStrictnessPredicate() const
For predicate of kind "is X or equal to 0" returns the predicate "is X".
Definition: InstrTypes.h:839
bool isGuard(const User *U)
Returns true iff U has semantics of a guard expressed in a form of call of llvm.experimental.guard intrinsic.
Definition: GuardUtils.cpp:17
void setOperand(unsigned i, Value *Val)
Definition: User.h:174
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
Function * getFunction(StringRef Name) const
Look up the specified function in the module symbol table.
Definition: Module.cpp:174
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:940
signed less or equal
Definition: InstrTypes.h:739
static cl::opt< bool > EnableCountDownLoop("loop-predication-enable-count-down-loop", cl::Hidden, cl::init(true))
This class uses information about analyze scalars to rewrite expressions in canonical form...
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))
ConstantInt * getFalse()
Get the constant value for i1 false.
Definition: IRBuilder.h:291
uint64_t getTypeSizeInBits(Type *Ty) const
Size examples:
Definition: DataLayout.h:593
Predicate getPredicate() const
Return the predicate for this instruction.
Definition: InstrTypes.h:784
Analysis providing branch probability information.
This class represents an analyzed expression in the program.
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:55
unsigned greater or equal
Definition: InstrTypes.h:733
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:465
#define I(x, y, z)
Definition: MD5.cpp:58
void getLoopAnalysisUsage(AnalysisUsage &AU)
Helper to consistently add the set of standard passes to a loop pass&#39;s AnalysisUsage.
Definition: LoopUtils.cpp:136
LLVM_NODISCARD std::enable_if<!is_simple_type< Y >::value, typename cast_retty< X, const Y >::ret_type >::type dyn_cast(const Y &Val)
Definition: Casting.h:332
static cl::opt< bool > SkipProfitabilityChecks("loop-predication-skip-profitability-checks", cl::Hidden, cl::init(false))
Value * CreateAnd(Value *LHS, Value *RHS, const Twine &Name="")
Definition: IRBuilder.h:1199
void setCondition(Value *V)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
void initializeLoopPredicationLegacyPassPass(PassRegistry &)
PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM, LoopStandardAnalysisResults &AR, LPMUpdater &U)
bool isOne() const
Return true if the expression is a constant one.
LLVM Value Representation.
Definition: Value.h:72
const SCEV * getSCEV(Value *V)
Return a SCEV expression for the full generality of the specified expression.
const SCEV * getTruncateExpr(const SCEV *Op, Type *Ty, unsigned Depth=0)
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:22
unsigned greater than
Definition: InstrTypes.h:732
Predicate getSwappedPredicate() const
For example, EQ->EQ, SLE->SGE, ULT->UGT, OEQ->OEQ, ULE->UGE, OLT->OGT, etc.
Definition: InstrTypes.h:824
A container for analyses that lazily runs them and caches their results.
#define LLVM_DEBUG(X)
Definition: Debug.h:122
iterator_range< block_iterator > blocks() const
Definition: LoopInfo.h:156
bool use_empty() const
Definition: Value.h:322
signed greater or equal
Definition: InstrTypes.h:737
A wrapper class for inspecting calls to intrinsic functions.
Definition: IntrinsicInst.h:43
This class represents a constant integer value.
CmpClass_match< LHS, RHS, ICmpInst, ICmpInst::Predicate > m_ICmp(ICmpInst::Predicate &Pred, const LHS &L, const RHS &R)