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 /// 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 form instead of an ULT/SLT form.
651  // Normalize back to the ULT/SLT form for ease of handling.
652  if (RC.Pred == ICmpInst::ICMP_NE &&
653  RC.IV->getStepRecurrence(*SE)->isOne() &&
654  SE->isKnownPredicate(ICmpInst::ICMP_ULE, RC.IV->getStart(), RC.Limit))
655  RC.Pred = ICmpInst::ICMP_ULT;
656 }
657 
658 
659 /// If ICI can be widened to a loop invariant condition emits the loop
660 /// invariant condition in the loop preheader and return it, otherwise
661 /// returns None.
662 Optional<Value *> LoopPredication::widenICmpRangeCheck(ICmpInst *ICI,
663  SCEVExpander &Expander,
664  Instruction *Guard) {
665  LLVM_DEBUG(dbgs() << "Analyzing ICmpInst condition:\n");
666  LLVM_DEBUG(ICI->dump());
667 
668  // parseLoopStructure guarantees that the latch condition is:
669  // ++i <pred> latchLimit, where <pred> is u<, u<=, s<, or s<=.
670  // We are looking for the range checks of the form:
671  // i u< guardLimit
672  auto RangeCheck = parseLoopICmp(ICI);
673  if (!RangeCheck) {
674  LLVM_DEBUG(dbgs() << "Failed to parse the loop latch condition!\n");
675  return None;
676  }
677  LLVM_DEBUG(dbgs() << "Guard check:\n");
678  LLVM_DEBUG(RangeCheck->dump());
679  if (RangeCheck->Pred != ICmpInst::ICMP_ULT) {
680  LLVM_DEBUG(dbgs() << "Unsupported range check predicate("
681  << RangeCheck->Pred << ")!\n");
682  return None;
683  }
684  auto *RangeCheckIV = RangeCheck->IV;
685  if (!RangeCheckIV->isAffine()) {
686  LLVM_DEBUG(dbgs() << "Range check IV is not affine!\n");
687  return None;
688  }
689  auto *Step = RangeCheckIV->getStepRecurrence(*SE);
690  // We cannot just compare with latch IV step because the latch and range IVs
691  // may have different types.
692  if (!isSupportedStep(Step)) {
693  LLVM_DEBUG(dbgs() << "Range check and latch have IVs different steps!\n");
694  return None;
695  }
696  auto *Ty = RangeCheckIV->getType();
697  auto CurrLatchCheckOpt = generateLoopLatchCheck(*DL, *SE, LatchCheck, Ty);
698  if (!CurrLatchCheckOpt) {
699  LLVM_DEBUG(dbgs() << "Failed to generate a loop latch check "
700  "corresponding to range type: "
701  << *Ty << "\n");
702  return None;
703  }
704 
705  LoopICmp CurrLatchCheck = *CurrLatchCheckOpt;
706  // At this point, the range and latch step should have the same type, but need
707  // not have the same value (we support both 1 and -1 steps).
708  assert(Step->getType() ==
709  CurrLatchCheck.IV->getStepRecurrence(*SE)->getType() &&
710  "Range and latch steps should be of same type!");
711  if (Step != CurrLatchCheck.IV->getStepRecurrence(*SE)) {
712  LLVM_DEBUG(dbgs() << "Range and latch have different step values!\n");
713  return None;
714  }
715 
716  if (Step->isOne())
717  return widenICmpRangeCheckIncrementingLoop(CurrLatchCheck, *RangeCheck,
718  Expander, Guard);
719  else {
720  assert(Step->isAllOnesValue() && "Step should be -1!");
721  return widenICmpRangeCheckDecrementingLoop(CurrLatchCheck, *RangeCheck,
722  Expander, Guard);
723  }
724 }
725 
726 unsigned LoopPredication::collectChecks(SmallVectorImpl<Value *> &Checks,
727  Value *Condition,
728  SCEVExpander &Expander,
729  Instruction *Guard) {
730  unsigned NumWidened = 0;
731  // The guard condition is expected to be in form of:
732  // cond1 && cond2 && cond3 ...
733  // Iterate over subconditions looking for icmp conditions which can be
734  // widened across loop iterations. Widening these conditions remember the
735  // resulting list of subconditions in Checks vector.
736  SmallVector<Value *, 4> Worklist(1, Condition);
737  SmallPtrSet<Value *, 4> Visited;
738  Value *WideableCond = nullptr;
739  do {
740  Value *Condition = Worklist.pop_back_val();
741  if (!Visited.insert(Condition).second)
742  continue;
743 
744  Value *LHS, *RHS;
745  using namespace llvm::PatternMatch;
746  if (match(Condition, m_And(m_Value(LHS), m_Value(RHS)))) {
747  Worklist.push_back(LHS);
748  Worklist.push_back(RHS);
749  continue;
750  }
751 
752  if (match(Condition,
753  m_Intrinsic<Intrinsic::experimental_widenable_condition>())) {
754  // Pick any, we don't care which
755  WideableCond = Condition;
756  continue;
757  }
758 
759  if (ICmpInst *ICI = dyn_cast<ICmpInst>(Condition)) {
760  if (auto NewRangeCheck = widenICmpRangeCheck(ICI, Expander,
761  Guard)) {
762  Checks.push_back(NewRangeCheck.getValue());
763  NumWidened++;
764  continue;
765  }
766  }
767 
768  // Save the condition as is if we can't widen it
769  Checks.push_back(Condition);
770  } while (!Worklist.empty());
771  // At the moment, our matching logic for wideable conditions implicitly
772  // assumes we preserve the form: (br (and Cond, WC())). FIXME
773  // Note that if there were multiple calls to wideable condition in the
774  // traversal, we only need to keep one, and which one is arbitrary.
775  if (WideableCond)
776  Checks.push_back(WideableCond);
777  return NumWidened;
778 }
779 
780 bool LoopPredication::widenGuardConditions(IntrinsicInst *Guard,
781  SCEVExpander &Expander) {
782  LLVM_DEBUG(dbgs() << "Processing guard:\n");
783  LLVM_DEBUG(Guard->dump());
784 
785  TotalConsidered++;
787  unsigned NumWidened = collectChecks(Checks, Guard->getOperand(0), Expander,
788  Guard);
789  if (NumWidened == 0)
790  return false;
791 
792  TotalWidened += NumWidened;
793 
794  // Emit the new guard condition
795  IRBuilder<> Builder(findInsertPt(Guard, Checks));
796  Value *LastCheck = nullptr;
797  for (auto *Check : Checks)
798  if (!LastCheck)
799  LastCheck = Check;
800  else
801  LastCheck = Builder.CreateAnd(LastCheck, Check);
802  auto *OldCond = Guard->getOperand(0);
803  Guard->setOperand(0, LastCheck);
805 
806  LLVM_DEBUG(dbgs() << "Widened checks = " << NumWidened << "\n");
807  return true;
808 }
809 
810 bool LoopPredication::widenWidenableBranchGuardConditions(
811  BranchInst *BI, SCEVExpander &Expander) {
812  assert(isGuardAsWidenableBranch(BI) && "Must be!");
813  LLVM_DEBUG(dbgs() << "Processing guard:\n");
814  LLVM_DEBUG(BI->dump());
815 
816  TotalConsidered++;
818  unsigned NumWidened = collectChecks(Checks, BI->getCondition(),
819  Expander, BI);
820  if (NumWidened == 0)
821  return false;
822 
823  TotalWidened += NumWidened;
824 
825  // Emit the new guard condition
826  IRBuilder<> Builder(findInsertPt(BI, Checks));
827  Value *LastCheck = nullptr;
828  for (auto *Check : Checks)
829  if (!LastCheck)
830  LastCheck = Check;
831  else
832  LastCheck = Builder.CreateAnd(LastCheck, Check);
833  auto *OldCond = BI->getCondition();
834  BI->setCondition(LastCheck);
836  "Stopped being a guard after transform?");
838 
839  LLVM_DEBUG(dbgs() << "Widened checks = " << NumWidened << "\n");
840  return true;
841 }
842 
843 Optional<LoopICmp> LoopPredication::parseLoopLatchICmp() {
844  using namespace PatternMatch;
845 
846  BasicBlock *LoopLatch = L->getLoopLatch();
847  if (!LoopLatch) {
848  LLVM_DEBUG(dbgs() << "The loop doesn't have a single latch!\n");
849  return None;
850  }
851 
852  auto *BI = dyn_cast<BranchInst>(LoopLatch->getTerminator());
853  if (!BI || !BI->isConditional()) {
854  LLVM_DEBUG(dbgs() << "Failed to match the latch terminator!\n");
855  return None;
856  }
857  BasicBlock *TrueDest = BI->getSuccessor(0);
858  assert(
859  (TrueDest == L->getHeader() || BI->getSuccessor(1) == L->getHeader()) &&
860  "One of the latch's destinations must be the header");
861 
862  auto *ICI = dyn_cast<ICmpInst>(BI->getCondition());
863  if (!ICI) {
864  LLVM_DEBUG(dbgs() << "Failed to match the latch condition!\n");
865  return None;
866  }
867  auto Result = parseLoopICmp(ICI);
868  if (!Result) {
869  LLVM_DEBUG(dbgs() << "Failed to parse the loop latch condition!\n");
870  return None;
871  }
872 
873  if (TrueDest != L->getHeader())
874  Result->Pred = ICmpInst::getInversePredicate(Result->Pred);
875 
876  // Check affine first, so if it's not we don't try to compute the step
877  // recurrence.
878  if (!Result->IV->isAffine()) {
879  LLVM_DEBUG(dbgs() << "The induction variable is not affine!\n");
880  return None;
881  }
882 
883  auto *Step = Result->IV->getStepRecurrence(*SE);
884  if (!isSupportedStep(Step)) {
885  LLVM_DEBUG(dbgs() << "Unsupported loop stride(" << *Step << ")!\n");
886  return None;
887  }
888 
889  auto IsUnsupportedPredicate = [](const SCEV *Step, ICmpInst::Predicate Pred) {
890  if (Step->isOne()) {
891  return Pred != ICmpInst::ICMP_ULT && Pred != ICmpInst::ICMP_SLT &&
892  Pred != ICmpInst::ICMP_ULE && Pred != ICmpInst::ICMP_SLE;
893  } else {
894  assert(Step->isAllOnesValue() && "Step should be -1!");
895  return Pred != ICmpInst::ICMP_UGT && Pred != ICmpInst::ICMP_SGT &&
896  Pred != ICmpInst::ICMP_UGE && Pred != ICmpInst::ICMP_SGE;
897  }
898  };
899 
900  normalizePredicate(SE, L, *Result);
901  if (IsUnsupportedPredicate(Step, Result->Pred)) {
902  LLVM_DEBUG(dbgs() << "Unsupported loop latch predicate(" << Result->Pred
903  << ")!\n");
904  return None;
905  }
906 
907  return Result;
908 }
909 
910 
911 bool LoopPredication::isLoopProfitableToPredicate() {
912  if (SkipProfitabilityChecks || !BPI)
913  return true;
914 
916  L->getExitEdges(ExitEdges);
917  // If there is only one exiting edge in the loop, it is always profitable to
918  // predicate the loop.
919  if (ExitEdges.size() == 1)
920  return true;
921 
922  // Calculate the exiting probabilities of all exiting edges from the loop,
923  // starting with the LatchExitProbability.
924  // Heuristic for profitability: If any of the exiting blocks' probability of
925  // exiting the loop is larger than exiting through the latch block, it's not
926  // profitable to predicate the loop.
927  auto *LatchBlock = L->getLoopLatch();
928  assert(LatchBlock && "Should have a single latch at this point!");
929  auto *LatchTerm = LatchBlock->getTerminator();
930  assert(LatchTerm->getNumSuccessors() == 2 &&
931  "expected to be an exiting block with 2 succs!");
932  unsigned LatchBrExitIdx =
933  LatchTerm->getSuccessor(0) == L->getHeader() ? 1 : 0;
934  BranchProbability LatchExitProbability =
935  BPI->getEdgeProbability(LatchBlock, LatchBrExitIdx);
936 
937  // Protect against degenerate inputs provided by the user. Providing a value
938  // less than one, can invert the definition of profitable loop predication.
939  float ScaleFactor = LatchExitProbabilityScale;
940  if (ScaleFactor < 1) {
941  LLVM_DEBUG(
942  dbgs()
943  << "Ignored user setting for loop-predication-latch-probability-scale: "
944  << LatchExitProbabilityScale << "\n");
945  LLVM_DEBUG(dbgs() << "The value is set to 1.0\n");
946  ScaleFactor = 1.0;
947  }
948  const auto LatchProbabilityThreshold =
949  LatchExitProbability * ScaleFactor;
950 
951  for (const auto &ExitEdge : ExitEdges) {
952  BranchProbability ExitingBlockProbability =
953  BPI->getEdgeProbability(ExitEdge.first, ExitEdge.second);
954  // Some exiting edge has higher probability than the latch exiting edge.
955  // No longer profitable to predicate.
956  if (ExitingBlockProbability > LatchProbabilityThreshold)
957  return false;
958  }
959  // Using BPI, we have concluded that the most probable way to exit from the
960  // loop is through the latch (or there's no profile information and all
961  // exits are equally likely).
962  return true;
963 }
964 
965 bool LoopPredication::runOnLoop(Loop *Loop) {
966  L = Loop;
967 
968  LLVM_DEBUG(dbgs() << "Analyzing ");
969  LLVM_DEBUG(L->dump());
970 
971  Module *M = L->getHeader()->getModule();
972 
973  // There is nothing to do if the module doesn't use guards
974  auto *GuardDecl =
975  M->getFunction(Intrinsic::getName(Intrinsic::experimental_guard));
976  bool HasIntrinsicGuards = GuardDecl && !GuardDecl->use_empty();
977  auto *WCDecl = M->getFunction(
978  Intrinsic::getName(Intrinsic::experimental_widenable_condition));
979  bool HasWidenableConditions =
980  PredicateWidenableBranchGuards && WCDecl && !WCDecl->use_empty();
981  if (!HasIntrinsicGuards && !HasWidenableConditions)
982  return false;
983 
984  DL = &M->getDataLayout();
985 
986  Preheader = L->getLoopPreheader();
987  if (!Preheader)
988  return false;
989 
990  auto LatchCheckOpt = parseLoopLatchICmp();
991  if (!LatchCheckOpt)
992  return false;
993  LatchCheck = *LatchCheckOpt;
994 
995  LLVM_DEBUG(dbgs() << "Latch check:\n");
996  LLVM_DEBUG(LatchCheck.dump());
997 
998  if (!isLoopProfitableToPredicate()) {
999  LLVM_DEBUG(dbgs() << "Loop not profitable to predicate!\n");
1000  return false;
1001  }
1002  // Collect all the guards into a vector and process later, so as not
1003  // to invalidate the instruction iterator.
1005  SmallVector<BranchInst *, 4> GuardsAsWidenableBranches;
1006  for (const auto BB : L->blocks()) {
1007  for (auto &I : *BB)
1008  if (isGuard(&I))
1009  Guards.push_back(cast<IntrinsicInst>(&I));
1011  isGuardAsWidenableBranch(BB->getTerminator()))
1012  GuardsAsWidenableBranches.push_back(
1013  cast<BranchInst>(BB->getTerminator()));
1014  }
1015 
1016  if (Guards.empty() && GuardsAsWidenableBranches.empty())
1017  return false;
1018 
1019  SCEVExpander Expander(*SE, *DL, "loop-predication");
1020 
1021  bool Changed = false;
1022  for (auto *Guard : Guards)
1023  Changed |= widenGuardConditions(Guard, Expander);
1024  for (auto *Guard : GuardsAsWidenableBranches)
1025  Changed |= widenWidenableBranchGuardConditions(Guard, Expander);
1026 
1027  return Changed;
1028 }
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:2026
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: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:4382
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:638
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:742
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:605
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
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: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
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: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: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:291
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:467
#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 * 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.