LLVM  10.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 /// Represents an induction variable check:
234 /// icmp Pred, <induction variable>, <loop invariant limit>
235 struct LoopICmp {
236  ICmpInst::Predicate Pred;
237  const SCEVAddRecExpr *IV;
238  const SCEV *Limit;
239  LoopICmp(ICmpInst::Predicate Pred, const SCEVAddRecExpr *IV,
240  const SCEV *Limit)
241  : Pred(Pred), IV(IV), Limit(Limit) {}
242  LoopICmp() {}
243  void dump() {
244  dbgs() << "LoopICmp Pred = " << Pred << ", IV = " << *IV
245  << ", Limit = " << *Limit << "\n";
246  }
247 };
248 
249 class LoopPredication {
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  Optional<LoopICmp> parseLoopLatchICmp();
262 
263  /// Return an insertion point suitable for inserting a safe to speculate
264  /// instruction whose only user will be 'User' which has operands 'Ops'. A
265  /// trivial result would be the at the User itself, but we try to return a
266  /// loop invariant location if possible.
267  Instruction *findInsertPt(Instruction *User, ArrayRef<Value*> Ops);
268  /// Same as above, *except* that this uses the SCEV definition of invariant
269  /// which is that an expression *can be made* invariant via SCEVExpander.
270  /// Thus, this version is only suitable for finding an insert point to be be
271  /// passed to SCEVExpander!
272  Instruction *findInsertPt(Instruction *User, ArrayRef<const SCEV*> Ops);
273 
274  /// Return true if the value is known to produce a single fixed value across
275  /// all iterations on which it executes. Note that this does not imply
276  /// speculation safety. That must be established seperately.
277  bool isLoopInvariantValue(const SCEV* S);
278 
279  Value *expandCheck(SCEVExpander &Expander, Instruction *Guard,
280  ICmpInst::Predicate Pred, const SCEV *LHS,
281  const SCEV *RHS);
282 
283  Optional<Value *> widenICmpRangeCheck(ICmpInst *ICI, SCEVExpander &Expander,
284  Instruction *Guard);
285  Optional<Value *> widenICmpRangeCheckIncrementingLoop(LoopICmp LatchCheck,
286  LoopICmp RangeCheck,
287  SCEVExpander &Expander,
288  Instruction *Guard);
289  Optional<Value *> widenICmpRangeCheckDecrementingLoop(LoopICmp LatchCheck,
290  LoopICmp RangeCheck,
291  SCEVExpander &Expander,
292  Instruction *Guard);
293  unsigned collectChecks(SmallVectorImpl<Value *> &Checks, Value *Condition,
294  SCEVExpander &Expander, Instruction *Guard);
295  bool widenGuardConditions(IntrinsicInst *II, SCEVExpander &Expander);
296  bool widenWidenableBranchGuardConditions(BranchInst *Guard, SCEVExpander &Expander);
297  // If the loop always exits through another block in the loop, we should not
298  // predicate based on the latch check. For example, the latch check can be a
299  // very coarse grained check and there can be more fine grained exit checks
300  // within the loop. We identify such unprofitable loops through BPI.
301  bool isLoopProfitableToPredicate();
302 
303 public:
304  LoopPredication(AliasAnalysis *AA, ScalarEvolution *SE,
306  : AA(AA), SE(SE), BPI(BPI){};
307  bool runOnLoop(Loop *L);
308 };
309 
310 class LoopPredicationLegacyPass : public LoopPass {
311 public:
312  static char ID;
313  LoopPredicationLegacyPass() : LoopPass(ID) {
315  }
316 
317  void getAnalysisUsage(AnalysisUsage &AU) const override {
320  }
321 
322  bool runOnLoop(Loop *L, LPPassManager &LPM) override {
323  if (skipLoop(L))
324  return false;
325  auto *SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
326  BranchProbabilityInfo &BPI =
327  getAnalysis<BranchProbabilityInfoWrapperPass>().getBPI();
328  auto *AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
329  LoopPredication LP(AA, SE, &BPI);
330  return LP.runOnLoop(L);
331  }
332 };
333 
335 } // end namespace llvm
336 
337 INITIALIZE_PASS_BEGIN(LoopPredicationLegacyPass, "loop-predication",
338  "Loop predication", false, false)
341 INITIALIZE_PASS_END(LoopPredicationLegacyPass, "loop-predication",
342  "Loop predication", false, false)
343 
345  return new LoopPredicationLegacyPass();
346 }
347 
350  LPMUpdater &U) {
351  const auto &FAM =
352  AM.getResult<FunctionAnalysisManagerLoopProxy>(L, AR).getManager();
353  Function *F = L.getHeader()->getParent();
354  auto *BPI = FAM.getCachedResult<BranchProbabilityAnalysis>(*F);
355  LoopPredication LP(&AR.AA, &AR.SE, BPI);
356  if (!LP.runOnLoop(&L))
357  return PreservedAnalyses::all();
358 
360 }
361 
363 LoopPredication::parseLoopICmp(ICmpInst *ICI) {
364  auto Pred = ICI->getPredicate();
365  auto *LHS = ICI->getOperand(0);
366  auto *RHS = ICI->getOperand(1);
367 
368  const SCEV *LHSS = SE->getSCEV(LHS);
369  if (isa<SCEVCouldNotCompute>(LHSS))
370  return None;
371  const SCEV *RHSS = SE->getSCEV(RHS);
372  if (isa<SCEVCouldNotCompute>(RHSS))
373  return None;
374 
375  // Canonicalize RHS to be loop invariant bound, LHS - a loop computable IV
376  if (SE->isLoopInvariant(LHSS, L)) {
377  std::swap(LHS, RHS);
378  std::swap(LHSS, RHSS);
379  Pred = ICmpInst::getSwappedPredicate(Pred);
380  }
381 
382  const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(LHSS);
383  if (!AR || AR->getLoop() != L)
384  return None;
385 
386  return LoopICmp(Pred, AR, RHSS);
387 }
388 
389 Value *LoopPredication::expandCheck(SCEVExpander &Expander,
390  Instruction *Guard,
391  ICmpInst::Predicate Pred, const SCEV *LHS,
392  const SCEV *RHS) {
393  Type *Ty = LHS->getType();
394  assert(Ty == RHS->getType() && "expandCheck operands have different types?");
395 
396  if (SE->isLoopInvariant(LHS, L) && SE->isLoopInvariant(RHS, L)) {
397  IRBuilder<> Builder(Guard);
398  if (SE->isLoopEntryGuardedByCond(L, Pred, LHS, RHS))
399  return Builder.getTrue();
400  if (SE->isLoopEntryGuardedByCond(L, ICmpInst::getInversePredicate(Pred),
401  LHS, RHS))
402  return Builder.getFalse();
403  }
404 
405  Value *LHSV = Expander.expandCodeFor(LHS, Ty, findInsertPt(Guard, {LHS}));
406  Value *RHSV = Expander.expandCodeFor(RHS, Ty, findInsertPt(Guard, {RHS}));
407  IRBuilder<> Builder(findInsertPt(Guard, {LHSV, RHSV}));
408  return Builder.CreateICmp(Pred, LHSV, RHSV);
409 }
410 
411 
412 // Returns true if its safe to truncate the IV to RangeCheckType.
413 // When the IV type is wider than the range operand type, we can still do loop
414 // predication, by generating SCEVs for the range and latch that are of the
415 // same type. We achieve this by generating a SCEV truncate expression for the
416 // latch IV. This is done iff truncation of the IV is a safe operation,
417 // without loss of information.
418 // Another way to achieve this is by generating a wider type SCEV for the
419 // range check operand, however, this needs a more involved check that
420 // operands do not overflow. This can lead to loss of information when the
421 // range operand is of the form: add i32 %offset, %iv. We need to prove that
422 // sext(x + y) is same as sext(x) + sext(y).
423 // This function returns true if we can safely represent the IV type in
424 // the RangeCheckType without loss of information.
426  ScalarEvolution &SE,
427  const LoopICmp LatchCheck,
428  Type *RangeCheckType) {
429  if (!EnableIVTruncation)
430  return false;
431  assert(DL.getTypeSizeInBits(LatchCheck.IV->getType()) >
432  DL.getTypeSizeInBits(RangeCheckType) &&
433  "Expected latch check IV type to be larger than range check operand "
434  "type!");
435  // The start and end values of the IV should be known. This is to guarantee
436  // that truncating the wide type will not lose information.
437  auto *Limit = dyn_cast<SCEVConstant>(LatchCheck.Limit);
438  auto *Start = dyn_cast<SCEVConstant>(LatchCheck.IV->getStart());
439  if (!Limit || !Start)
440  return false;
441  // This check makes sure that the IV does not change sign during loop
442  // iterations. Consider latchType = i64, LatchStart = 5, Pred = ICMP_SGE,
443  // LatchEnd = 2, rangeCheckType = i32. If it's not a monotonic predicate, the
444  // IV wraps around, and the truncation of the IV would lose the range of
445  // iterations between 2^32 and 2^64.
446  bool Increasing;
447  if (!SE.isMonotonicPredicate(LatchCheck.IV, LatchCheck.Pred, Increasing))
448  return false;
449  // The active bits should be less than the bits in the RangeCheckType. This
450  // guarantees that truncating the latch check to RangeCheckType is a safe
451  // operation.
452  auto RangeCheckTypeBitSize = DL.getTypeSizeInBits(RangeCheckType);
453  return Start->getAPInt().getActiveBits() < RangeCheckTypeBitSize &&
454  Limit->getAPInt().getActiveBits() < RangeCheckTypeBitSize;
455 }
456 
457 
458 // Return an LoopICmp describing a latch check equivlent to LatchCheck but with
459 // the requested type if safe to do so. May involve the use of a new IV.
461  ScalarEvolution &SE,
462  const LoopICmp LatchCheck,
463  Type *RangeCheckType) {
464 
465  auto *LatchType = LatchCheck.IV->getType();
466  if (RangeCheckType == LatchType)
467  return LatchCheck;
468  // For now, bail out if latch type is narrower than range type.
469  if (DL.getTypeSizeInBits(LatchType) < DL.getTypeSizeInBits(RangeCheckType))
470  return None;
471  if (!isSafeToTruncateWideIVType(DL, SE, LatchCheck, RangeCheckType))
472  return None;
473  // We can now safely identify the truncated version of the IV and limit for
474  // RangeCheckType.
475  LoopICmp NewLatchCheck;
476  NewLatchCheck.Pred = LatchCheck.Pred;
477  NewLatchCheck.IV = dyn_cast<SCEVAddRecExpr>(
478  SE.getTruncateExpr(LatchCheck.IV, RangeCheckType));
479  if (!NewLatchCheck.IV)
480  return None;
481  NewLatchCheck.Limit = SE.getTruncateExpr(LatchCheck.Limit, RangeCheckType);
482  LLVM_DEBUG(dbgs() << "IV of type: " << *LatchType
483  << "can be represented as range check type:"
484  << *RangeCheckType << "\n");
485  LLVM_DEBUG(dbgs() << "LatchCheck.IV: " << *NewLatchCheck.IV << "\n");
486  LLVM_DEBUG(dbgs() << "LatchCheck.Limit: " << *NewLatchCheck.Limit << "\n");
487  return NewLatchCheck;
488 }
489 
490 bool LoopPredication::isSupportedStep(const SCEV* Step) {
491  return Step->isOne() || (Step->isAllOnesValue() && EnableCountDownLoop);
492 }
493 
494 Instruction *LoopPredication::findInsertPt(Instruction *Use,
495  ArrayRef<Value*> Ops) {
496  for (Value *Op : Ops)
497  if (!L->isLoopInvariant(Op))
498  return Use;
499  return Preheader->getTerminator();
500 }
501 
502 Instruction *LoopPredication::findInsertPt(Instruction *Use,
503  ArrayRef<const SCEV*> Ops) {
504  // Subtlety: SCEV considers things to be invariant if the value produced is
505  // the same across iterations. This is not the same as being able to
506  // evaluate outside the loop, which is what we actually need here.
507  for (const SCEV *Op : Ops)
508  if (!SE->isLoopInvariant(Op, L) ||
509  !isSafeToExpandAt(Op, Preheader->getTerminator(), *SE))
510  return Use;
511  return Preheader->getTerminator();
512 }
513 
514 bool LoopPredication::isLoopInvariantValue(const SCEV* S) {
515  // Handling expressions which produce invariant results, but *haven't* yet
516  // been removed from the loop serves two important purposes.
517  // 1) Most importantly, it resolves a pass ordering cycle which would
518  // otherwise need us to iteration licm, loop-predication, and either
519  // loop-unswitch or loop-peeling to make progress on examples with lots of
520  // predicable range checks in a row. (Since, in the general case, we can't
521  // hoist the length checks until the dominating checks have been discharged
522  // as we can't prove doing so is safe.)
523  // 2) As a nice side effect, this exposes the value of peeling or unswitching
524  // much more obviously in the IR. Otherwise, the cost modeling for other
525  // transforms would end up needing to duplicate all of this logic to model a
526  // check which becomes predictable based on a modeled peel or unswitch.
527  //
528  // The cost of doing so in the worst case is an extra fill from the stack in
529  // the loop to materialize the loop invariant test value instead of checking
530  // against the original IV which is presumable in a register inside the loop.
531  // Such cases are presumably rare, and hint at missing oppurtunities for
532  // other passes.
533 
534  if (SE->isLoopInvariant(S, L))
535  // Note: This the SCEV variant, so the original Value* may be within the
536  // loop even though SCEV has proven it is loop invariant.
537  return true;
538 
539  // Handle a particular important case which SCEV doesn't yet know about which
540  // shows up in range checks on arrays with immutable lengths.
541  // TODO: This should be sunk inside SCEV.
542  if (const SCEVUnknown *U = dyn_cast<SCEVUnknown>(S))
543  if (const auto *LI = dyn_cast<LoadInst>(U->getValue()))
544  if (LI->isUnordered() && L->hasLoopInvariantOperands(LI))
545  if (AA->pointsToConstantMemory(LI->getOperand(0)) ||
546  LI->getMetadata(LLVMContext::MD_invariant_load) != nullptr)
547  return true;
548  return false;
549 }
550 
551 Optional<Value *> LoopPredication::widenICmpRangeCheckIncrementingLoop(
552  LoopICmp LatchCheck, LoopICmp RangeCheck,
553  SCEVExpander &Expander, Instruction *Guard) {
554  auto *Ty = RangeCheck.IV->getType();
555  // Generate the widened condition for the forward loop:
556  // guardStart u< guardLimit &&
557  // latchLimit <pred> guardLimit - 1 - guardStart + latchStart
558  // where <pred> depends on the latch condition predicate. See the file
559  // header comment for the reasoning.
560  // guardLimit - guardStart + latchStart - 1
561  const SCEV *GuardStart = RangeCheck.IV->getStart();
562  const SCEV *GuardLimit = RangeCheck.Limit;
563  const SCEV *LatchStart = LatchCheck.IV->getStart();
564  const SCEV *LatchLimit = LatchCheck.Limit;
565  // Subtlety: We need all the values to be *invariant* across all iterations,
566  // but we only need to check expansion safety for those which *aren't*
567  // already guaranteed to dominate the guard.
568  if (!isLoopInvariantValue(GuardStart) ||
569  !isLoopInvariantValue(GuardLimit) ||
570  !isLoopInvariantValue(LatchStart) ||
571  !isLoopInvariantValue(LatchLimit)) {
572  LLVM_DEBUG(dbgs() << "Can't expand limit check!\n");
573  return None;
574  }
575  if (!isSafeToExpandAt(LatchStart, Guard, *SE) ||
576  !isSafeToExpandAt(LatchLimit, Guard, *SE)) {
577  LLVM_DEBUG(dbgs() << "Can't expand limit check!\n");
578  return None;
579  }
580 
581  // guardLimit - guardStart + latchStart - 1
582  const SCEV *RHS =
583  SE->getAddExpr(SE->getMinusSCEV(GuardLimit, GuardStart),
584  SE->getMinusSCEV(LatchStart, SE->getOne(Ty)));
585  auto LimitCheckPred =
587 
588  LLVM_DEBUG(dbgs() << "LHS: " << *LatchLimit << "\n");
589  LLVM_DEBUG(dbgs() << "RHS: " << *RHS << "\n");
590  LLVM_DEBUG(dbgs() << "Pred: " << LimitCheckPred << "\n");
591 
592  auto *LimitCheck =
593  expandCheck(Expander, Guard, LimitCheckPred, LatchLimit, RHS);
594  auto *FirstIterationCheck = expandCheck(Expander, Guard, RangeCheck.Pred,
595  GuardStart, GuardLimit);
596  IRBuilder<> Builder(findInsertPt(Guard, {FirstIterationCheck, LimitCheck}));
597  return Builder.CreateAnd(FirstIterationCheck, LimitCheck);
598 }
599 
600 Optional<Value *> LoopPredication::widenICmpRangeCheckDecrementingLoop(
601  LoopICmp LatchCheck, LoopICmp RangeCheck,
602  SCEVExpander &Expander, Instruction *Guard) {
603  auto *Ty = RangeCheck.IV->getType();
604  const SCEV *GuardStart = RangeCheck.IV->getStart();
605  const SCEV *GuardLimit = RangeCheck.Limit;
606  const SCEV *LatchStart = LatchCheck.IV->getStart();
607  const SCEV *LatchLimit = LatchCheck.Limit;
608  // Subtlety: We need all the values to be *invariant* across all iterations,
609  // but we only need to check expansion safety for those which *aren't*
610  // already guaranteed to dominate the guard.
611  if (!isLoopInvariantValue(GuardStart) ||
612  !isLoopInvariantValue(GuardLimit) ||
613  !isLoopInvariantValue(LatchStart) ||
614  !isLoopInvariantValue(LatchLimit)) {
615  LLVM_DEBUG(dbgs() << "Can't expand limit check!\n");
616  return None;
617  }
618  if (!isSafeToExpandAt(LatchStart, Guard, *SE) ||
619  !isSafeToExpandAt(LatchLimit, Guard, *SE)) {
620  LLVM_DEBUG(dbgs() << "Can't expand limit check!\n");
621  return None;
622  }
623  // The decrement of the latch check IV should be the same as the
624  // rangeCheckIV.
625  auto *PostDecLatchCheckIV = LatchCheck.IV->getPostIncExpr(*SE);
626  if (RangeCheck.IV != PostDecLatchCheckIV) {
627  LLVM_DEBUG(dbgs() << "Not the same. PostDecLatchCheckIV: "
628  << *PostDecLatchCheckIV
629  << " and RangeCheckIV: " << *RangeCheck.IV << "\n");
630  return None;
631  }
632 
633  // Generate the widened condition for CountDownLoop:
634  // guardStart u< guardLimit &&
635  // latchLimit <pred> 1.
636  // See the header comment for reasoning of the checks.
637  auto LimitCheckPred =
639  auto *FirstIterationCheck = expandCheck(Expander, Guard,
641  GuardStart, GuardLimit);
642  auto *LimitCheck = expandCheck(Expander, Guard, LimitCheckPred, LatchLimit,
643  SE->getOne(Ty));
644  IRBuilder<> Builder(findInsertPt(Guard, {FirstIterationCheck, LimitCheck}));
645  return Builder.CreateAnd(FirstIterationCheck, LimitCheck);
646 }
647 
649  LoopICmp& RC) {
650  // LFTR canonicalizes checks to the ICMP_NE/EQ form; normalize back to the
651  // ULT/UGE form for ease of handling by our caller.
652  if (ICmpInst::isEquality(RC.Pred) &&
653  RC.IV->getStepRecurrence(*SE)->isOne() &&
654  SE->isKnownPredicate(ICmpInst::ICMP_ULE, RC.IV->getStart(), RC.Limit))
655  RC.Pred = RC.Pred == ICmpInst::ICMP_NE ?
657 }
658 
659 
660 /// If ICI can be widened to a loop invariant condition emits the loop
661 /// invariant condition in the loop preheader and return it, otherwise
662 /// returns None.
663 Optional<Value *> LoopPredication::widenICmpRangeCheck(ICmpInst *ICI,
664  SCEVExpander &Expander,
665  Instruction *Guard) {
666  LLVM_DEBUG(dbgs() << "Analyzing ICmpInst condition:\n");
667  LLVM_DEBUG(ICI->dump());
668 
669  // parseLoopStructure guarantees that the latch condition is:
670  // ++i <pred> latchLimit, where <pred> is u<, u<=, s<, or s<=.
671  // We are looking for the range checks of the form:
672  // i u< guardLimit
673  auto RangeCheck = parseLoopICmp(ICI);
674  if (!RangeCheck) {
675  LLVM_DEBUG(dbgs() << "Failed to parse the loop latch condition!\n");
676  return None;
677  }
678  LLVM_DEBUG(dbgs() << "Guard check:\n");
679  LLVM_DEBUG(RangeCheck->dump());
680  if (RangeCheck->Pred != ICmpInst::ICMP_ULT) {
681  LLVM_DEBUG(dbgs() << "Unsupported range check predicate("
682  << RangeCheck->Pred << ")!\n");
683  return None;
684  }
685  auto *RangeCheckIV = RangeCheck->IV;
686  if (!RangeCheckIV->isAffine()) {
687  LLVM_DEBUG(dbgs() << "Range check IV is not affine!\n");
688  return None;
689  }
690  auto *Step = RangeCheckIV->getStepRecurrence(*SE);
691  // We cannot just compare with latch IV step because the latch and range IVs
692  // may have different types.
693  if (!isSupportedStep(Step)) {
694  LLVM_DEBUG(dbgs() << "Range check and latch have IVs different steps!\n");
695  return None;
696  }
697  auto *Ty = RangeCheckIV->getType();
698  auto CurrLatchCheckOpt = generateLoopLatchCheck(*DL, *SE, LatchCheck, Ty);
699  if (!CurrLatchCheckOpt) {
700  LLVM_DEBUG(dbgs() << "Failed to generate a loop latch check "
701  "corresponding to range type: "
702  << *Ty << "\n");
703  return None;
704  }
705 
706  LoopICmp CurrLatchCheck = *CurrLatchCheckOpt;
707  // At this point, the range and latch step should have the same type, but need
708  // not have the same value (we support both 1 and -1 steps).
709  assert(Step->getType() ==
710  CurrLatchCheck.IV->getStepRecurrence(*SE)->getType() &&
711  "Range and latch steps should be of same type!");
712  if (Step != CurrLatchCheck.IV->getStepRecurrence(*SE)) {
713  LLVM_DEBUG(dbgs() << "Range and latch have different step values!\n");
714  return None;
715  }
716 
717  if (Step->isOne())
718  return widenICmpRangeCheckIncrementingLoop(CurrLatchCheck, *RangeCheck,
719  Expander, Guard);
720  else {
721  assert(Step->isAllOnesValue() && "Step should be -1!");
722  return widenICmpRangeCheckDecrementingLoop(CurrLatchCheck, *RangeCheck,
723  Expander, Guard);
724  }
725 }
726 
727 unsigned LoopPredication::collectChecks(SmallVectorImpl<Value *> &Checks,
728  Value *Condition,
729  SCEVExpander &Expander,
730  Instruction *Guard) {
731  unsigned NumWidened = 0;
732  // The guard condition is expected to be in form of:
733  // cond1 && cond2 && cond3 ...
734  // Iterate over subconditions looking for icmp conditions which can be
735  // widened across loop iterations. Widening these conditions remember the
736  // resulting list of subconditions in Checks vector.
737  SmallVector<Value *, 4> Worklist(1, Condition);
738  SmallPtrSet<Value *, 4> Visited;
739  Value *WideableCond = nullptr;
740  do {
741  Value *Condition = Worklist.pop_back_val();
742  if (!Visited.insert(Condition).second)
743  continue;
744 
745  Value *LHS, *RHS;
746  using namespace llvm::PatternMatch;
747  if (match(Condition, m_And(m_Value(LHS), m_Value(RHS)))) {
748  Worklist.push_back(LHS);
749  Worklist.push_back(RHS);
750  continue;
751  }
752 
753  if (match(Condition,
754  m_Intrinsic<Intrinsic::experimental_widenable_condition>())) {
755  // Pick any, we don't care which
756  WideableCond = Condition;
757  continue;
758  }
759 
760  if (ICmpInst *ICI = dyn_cast<ICmpInst>(Condition)) {
761  if (auto NewRangeCheck = widenICmpRangeCheck(ICI, Expander,
762  Guard)) {
763  Checks.push_back(NewRangeCheck.getValue());
764  NumWidened++;
765  continue;
766  }
767  }
768 
769  // Save the condition as is if we can't widen it
770  Checks.push_back(Condition);
771  } while (!Worklist.empty());
772  // At the moment, our matching logic for wideable conditions implicitly
773  // assumes we preserve the form: (br (and Cond, WC())). FIXME
774  // Note that if there were multiple calls to wideable condition in the
775  // traversal, we only need to keep one, and which one is arbitrary.
776  if (WideableCond)
777  Checks.push_back(WideableCond);
778  return NumWidened;
779 }
780 
781 bool LoopPredication::widenGuardConditions(IntrinsicInst *Guard,
782  SCEVExpander &Expander) {
783  LLVM_DEBUG(dbgs() << "Processing guard:\n");
784  LLVM_DEBUG(Guard->dump());
785 
786  TotalConsidered++;
788  unsigned NumWidened = collectChecks(Checks, Guard->getOperand(0), Expander,
789  Guard);
790  if (NumWidened == 0)
791  return false;
792 
793  TotalWidened += NumWidened;
794 
795  // Emit the new guard condition
796  IRBuilder<> Builder(findInsertPt(Guard, Checks));
797  Value *AllChecks = Builder.CreateAnd(Checks);
798  auto *OldCond = Guard->getOperand(0);
799  Guard->setOperand(0, AllChecks);
801 
802  LLVM_DEBUG(dbgs() << "Widened checks = " << NumWidened << "\n");
803  return true;
804 }
805 
806 bool LoopPredication::widenWidenableBranchGuardConditions(
807  BranchInst *BI, SCEVExpander &Expander) {
808  assert(isGuardAsWidenableBranch(BI) && "Must be!");
809  LLVM_DEBUG(dbgs() << "Processing guard:\n");
810  LLVM_DEBUG(BI->dump());
811 
812  TotalConsidered++;
814  unsigned NumWidened = collectChecks(Checks, BI->getCondition(),
815  Expander, BI);
816  if (NumWidened == 0)
817  return false;
818 
819  TotalWidened += NumWidened;
820 
821  // Emit the new guard condition
822  IRBuilder<> Builder(findInsertPt(BI, Checks));
823  Value *AllChecks = Builder.CreateAnd(Checks);
824  auto *OldCond = BI->getCondition();
825  BI->setCondition(AllChecks);
827  "Stopped being a guard after transform?");
829 
830  LLVM_DEBUG(dbgs() << "Widened checks = " << NumWidened << "\n");
831  return true;
832 }
833 
834 Optional<LoopICmp> LoopPredication::parseLoopLatchICmp() {
835  using namespace PatternMatch;
836 
837  BasicBlock *LoopLatch = L->getLoopLatch();
838  if (!LoopLatch) {
839  LLVM_DEBUG(dbgs() << "The loop doesn't have a single latch!\n");
840  return None;
841  }
842 
843  auto *BI = dyn_cast<BranchInst>(LoopLatch->getTerminator());
844  if (!BI || !BI->isConditional()) {
845  LLVM_DEBUG(dbgs() << "Failed to match the latch terminator!\n");
846  return None;
847  }
848  BasicBlock *TrueDest = BI->getSuccessor(0);
849  assert(
850  (TrueDest == L->getHeader() || BI->getSuccessor(1) == L->getHeader()) &&
851  "One of the latch's destinations must be the header");
852 
853  auto *ICI = dyn_cast<ICmpInst>(BI->getCondition());
854  if (!ICI) {
855  LLVM_DEBUG(dbgs() << "Failed to match the latch condition!\n");
856  return None;
857  }
858  auto Result = parseLoopICmp(ICI);
859  if (!Result) {
860  LLVM_DEBUG(dbgs() << "Failed to parse the loop latch condition!\n");
861  return None;
862  }
863 
864  if (TrueDest != L->getHeader())
865  Result->Pred = ICmpInst::getInversePredicate(Result->Pred);
866 
867  // Check affine first, so if it's not we don't try to compute the step
868  // recurrence.
869  if (!Result->IV->isAffine()) {
870  LLVM_DEBUG(dbgs() << "The induction variable is not affine!\n");
871  return None;
872  }
873 
874  auto *Step = Result->IV->getStepRecurrence(*SE);
875  if (!isSupportedStep(Step)) {
876  LLVM_DEBUG(dbgs() << "Unsupported loop stride(" << *Step << ")!\n");
877  return None;
878  }
879 
880  auto IsUnsupportedPredicate = [](const SCEV *Step, ICmpInst::Predicate Pred) {
881  if (Step->isOne()) {
882  return Pred != ICmpInst::ICMP_ULT && Pred != ICmpInst::ICMP_SLT &&
883  Pred != ICmpInst::ICMP_ULE && Pred != ICmpInst::ICMP_SLE;
884  } else {
885  assert(Step->isAllOnesValue() && "Step should be -1!");
886  return Pred != ICmpInst::ICMP_UGT && Pred != ICmpInst::ICMP_SGT &&
887  Pred != ICmpInst::ICMP_UGE && Pred != ICmpInst::ICMP_SGE;
888  }
889  };
890 
891  normalizePredicate(SE, L, *Result);
892  if (IsUnsupportedPredicate(Step, Result->Pred)) {
893  LLVM_DEBUG(dbgs() << "Unsupported loop latch predicate(" << Result->Pred
894  << ")!\n");
895  return None;
896  }
897 
898  return Result;
899 }
900 
901 
902 bool LoopPredication::isLoopProfitableToPredicate() {
903  if (SkipProfitabilityChecks || !BPI)
904  return true;
905 
907  L->getExitEdges(ExitEdges);
908  // If there is only one exiting edge in the loop, it is always profitable to
909  // predicate the loop.
910  if (ExitEdges.size() == 1)
911  return true;
912 
913  // Calculate the exiting probabilities of all exiting edges from the loop,
914  // starting with the LatchExitProbability.
915  // Heuristic for profitability: If any of the exiting blocks' probability of
916  // exiting the loop is larger than exiting through the latch block, it's not
917  // profitable to predicate the loop.
918  auto *LatchBlock = L->getLoopLatch();
919  assert(LatchBlock && "Should have a single latch at this point!");
920  auto *LatchTerm = LatchBlock->getTerminator();
921  assert(LatchTerm->getNumSuccessors() == 2 &&
922  "expected to be an exiting block with 2 succs!");
923  unsigned LatchBrExitIdx =
924  LatchTerm->getSuccessor(0) == L->getHeader() ? 1 : 0;
925  BranchProbability LatchExitProbability =
926  BPI->getEdgeProbability(LatchBlock, LatchBrExitIdx);
927 
928  // Protect against degenerate inputs provided by the user. Providing a value
929  // less than one, can invert the definition of profitable loop predication.
930  float ScaleFactor = LatchExitProbabilityScale;
931  if (ScaleFactor < 1) {
932  LLVM_DEBUG(
933  dbgs()
934  << "Ignored user setting for loop-predication-latch-probability-scale: "
935  << LatchExitProbabilityScale << "\n");
936  LLVM_DEBUG(dbgs() << "The value is set to 1.0\n");
937  ScaleFactor = 1.0;
938  }
939  const auto LatchProbabilityThreshold =
940  LatchExitProbability * ScaleFactor;
941 
942  for (const auto &ExitEdge : ExitEdges) {
943  BranchProbability ExitingBlockProbability =
944  BPI->getEdgeProbability(ExitEdge.first, ExitEdge.second);
945  // Some exiting edge has higher probability than the latch exiting edge.
946  // No longer profitable to predicate.
947  if (ExitingBlockProbability > LatchProbabilityThreshold)
948  return false;
949  }
950  // Using BPI, we have concluded that the most probable way to exit from the
951  // loop is through the latch (or there's no profile information and all
952  // exits are equally likely).
953  return true;
954 }
955 
956 bool LoopPredication::runOnLoop(Loop *Loop) {
957  L = Loop;
958 
959  LLVM_DEBUG(dbgs() << "Analyzing ");
960  LLVM_DEBUG(L->dump());
961 
962  Module *M = L->getHeader()->getModule();
963 
964  // There is nothing to do if the module doesn't use guards
965  auto *GuardDecl =
966  M->getFunction(Intrinsic::getName(Intrinsic::experimental_guard));
967  bool HasIntrinsicGuards = GuardDecl && !GuardDecl->use_empty();
968  auto *WCDecl = M->getFunction(
969  Intrinsic::getName(Intrinsic::experimental_widenable_condition));
970  bool HasWidenableConditions =
971  PredicateWidenableBranchGuards && WCDecl && !WCDecl->use_empty();
972  if (!HasIntrinsicGuards && !HasWidenableConditions)
973  return false;
974 
975  DL = &M->getDataLayout();
976 
977  Preheader = L->getLoopPreheader();
978  if (!Preheader)
979  return false;
980 
981  auto LatchCheckOpt = parseLoopLatchICmp();
982  if (!LatchCheckOpt)
983  return false;
984  LatchCheck = *LatchCheckOpt;
985 
986  LLVM_DEBUG(dbgs() << "Latch check:\n");
987  LLVM_DEBUG(LatchCheck.dump());
988 
989  if (!isLoopProfitableToPredicate()) {
990  LLVM_DEBUG(dbgs() << "Loop not profitable to predicate!\n");
991  return false;
992  }
993  // Collect all the guards into a vector and process later, so as not
994  // to invalidate the instruction iterator.
996  SmallVector<BranchInst *, 4> GuardsAsWidenableBranches;
997  for (const auto BB : L->blocks()) {
998  for (auto &I : *BB)
999  if (isGuard(&I))
1000  Guards.push_back(cast<IntrinsicInst>(&I));
1002  isGuardAsWidenableBranch(BB->getTerminator()))
1003  GuardsAsWidenableBranches.push_back(
1004  cast<BranchInst>(BB->getTerminator()));
1005  }
1006 
1007  if (Guards.empty() && GuardsAsWidenableBranches.empty())
1008  return false;
1009 
1010  SCEVExpander Expander(*SE, *DL, "loop-predication");
1011 
1012  bool Changed = false;
1013  for (auto *Guard : Guards)
1014  Changed |= widenGuardConditions(Guard, Expander);
1015  for (auto *Guard : GuardsAsWidenableBranches)
1016  Changed |= widenWidenableBranchGuardConditions(Guard, Expander);
1017 
1018  return Changed;
1019 }
Pass interface - Implemented by all &#39;passes&#39;.
Definition: Pass.h:80
BinaryOp_match< LHS, RHS, Instruction::And > m_And(const LHS &L, const RHS &R)
Definition: PatternMatch.h:796
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:2198
BlockT * getLoopLatch() const
If there is a single latch block for this loop, return it.
Definition: LoopInfoImpl.h:211
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:160
unsigned less or equal
Definition: InstrTypes.h:758
unsigned less than
Definition: InstrTypes.h:757
BasicBlock * getSuccessor(unsigned i) const
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:67
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:4424
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:637
Predicate getInversePredicate() const
For example, EQ -> NE, UGT -> ULE, SLT -> SGE, OEQ -> UNE, UGT -> OLE, OLT -> UGE, etc.
Definition: InstrTypes.h:831
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:779
BlockT * getHeader() const
Definition: LoopInfo.h:102
Analysis pass which computes BranchProbabilityInfo.
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...
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))
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
void dump() const
Definition: LoopInfo.cpp:608
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:323
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
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:732
Value * expandCodeFor(const SCEV *SH, Type *Ty, Instruction *I)
Insert code to directly compute the specified SCEV expression into the program.
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:440
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:159
size_t size() const
Definition: SmallVector.h:52
static void normalizePredicate(ScalarEvolution *SE, Loop *L, LoopICmp &RC)
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:61
signed greater than
Definition: InstrTypes.h:759
void getExitEdges(SmallVectorImpl< Edge > &ExitEdges) const
Return all pairs of (inside_block,outside_block).
Definition: LoopInfoImpl.h:141
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:837
Module.h This file contains the declarations for the Module class.
signed less than
Definition: InstrTypes.h:761
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:374
bool isConditional() const
Predicate getFlippedStrictnessPredicate() const
For predicate of kind "is X or equal to 0" returns the predicate "is X".
Definition: InstrTypes.h:862
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:762
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:328
static Optional< LoopICmp > generateLoopLatchCheck(const DataLayout &DL, ScalarEvolution &SE, const LoopICmp LatchCheck, Type *RangeCheckType)
uint64_t getTypeSizeInBits(Type *Ty) const
Size examples:
Definition: DataLayout.h:601
Predicate getPredicate() const
Return the predicate for this instruction.
Definition: InstrTypes.h:807
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:756
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:506
bool isEquality() const
Return true if this predicate is either EQ or NE.
#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:1268
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 * 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:755
Predicate getSwappedPredicate() const
For example, EQ->EQ, SLE->SGE, ULT->UGT, OEQ->OEQ, ULE->UGE, OLT->OGT, etc.
Definition: InstrTypes.h:847
A container for analyses that lazily runs them and caches their results.
static bool isSafeToTruncateWideIVType(const DataLayout &DL, ScalarEvolution &SE, const LoopICmp LatchCheck, Type *RangeCheckType)
#define LLVM_DEBUG(X)
Definition: Debug.h:122
iterator_range< block_iterator > blocks() const
Definition: LoopInfo.h:158
bool use_empty() const
Definition: Value.h:322
signed greater or equal
Definition: InstrTypes.h:760
A wrapper class for inspecting calls to intrinsic functions.
Definition: IntrinsicInst.h:43
This class represents a constant integer value.