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"
183 #include "llvm/Analysis/LoopInfo.h"
184 #include "llvm/Analysis/LoopPass.h"
188 #include "llvm/IR/Function.h"
189 #include "llvm/IR/GlobalValue.h"
190 #include "llvm/IR/IntrinsicInst.h"
191 #include "llvm/IR/Module.h"
192 #include "llvm/IR/PatternMatch.h"
193 #include "llvm/Pass.h"
194 #include "llvm/Support/Debug.h"
195 #include "llvm/Transforms/Scalar.h"
197 
198 #define DEBUG_TYPE "loop-predication"
199 
200 STATISTIC(TotalConsidered, "Number of guards considered");
201 STATISTIC(TotalWidened, "Number of checks widened");
202 
203 using namespace llvm;
204 
205 static cl::opt<bool> EnableIVTruncation("loop-predication-enable-iv-truncation",
206  cl::Hidden, cl::init(true));
207 
208 static cl::opt<bool> EnableCountDownLoop("loop-predication-enable-count-down-loop",
209  cl::Hidden, cl::init(true));
210 
211 static cl::opt<bool>
212  SkipProfitabilityChecks("loop-predication-skip-profitability-checks",
213  cl::Hidden, cl::init(false));
214 
215 // This is the scale factor for the latch probability. We use this during
216 // profitability analysis to find other exiting blocks that have a much higher
217 // probability of exiting the loop instead of loop exiting via latch.
218 // This value should be greater than 1 for a sane profitability check.
220  "loop-predication-latch-probability-scale", cl::Hidden, cl::init(2.0),
221  cl::desc("scale factor for the latch probability. Value should be greater "
222  "than 1. Lower values are ignored"));
223 
225  "loop-predication-predicate-widenable-branches-to-deopt", cl::Hidden,
226  cl::desc("Whether or not we should predicate guards "
227  "expressed as widenable branches to deoptimize blocks"),
228  cl::init(true));
229 
230 namespace {
231 class LoopPredication {
232  /// Represents an induction variable check:
233  /// icmp Pred, <induction variable>, <loop invariant limit>
234  struct LoopICmp {
235  ICmpInst::Predicate Pred;
236  const SCEVAddRecExpr *IV;
237  const SCEV *Limit;
238  LoopICmp(ICmpInst::Predicate Pred, const SCEVAddRecExpr *IV,
239  const SCEV *Limit)
240  : Pred(Pred), IV(IV), Limit(Limit) {}
241  LoopICmp() {}
242  void dump() {
243  dbgs() << "LoopICmp Pred = " << Pred << ", IV = " << *IV
244  << ", Limit = " << *Limit << "\n";
245  }
246  };
247 
248  ScalarEvolution *SE;
250 
251  Loop *L;
252  const DataLayout *DL;
253  BasicBlock *Preheader;
254  LoopICmp LatchCheck;
255 
256  bool isSupportedStep(const SCEV* Step);
257  Optional<LoopICmp> parseLoopICmp(ICmpInst *ICI) {
258  return parseLoopICmp(ICI->getPredicate(), ICI->getOperand(0),
259  ICI->getOperand(1));
260  }
261  Optional<LoopICmp> parseLoopICmp(ICmpInst::Predicate Pred, Value *LHS,
262  Value *RHS);
263 
264  Optional<LoopICmp> parseLoopLatchICmp();
265 
266  bool CanExpand(const SCEV* S);
267  Value *expandCheck(SCEVExpander &Expander, IRBuilder<> &Builder,
268  ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS,
269  Instruction *InsertAt);
270 
271  Optional<Value *> widenICmpRangeCheck(ICmpInst *ICI, SCEVExpander &Expander,
272  IRBuilder<> &Builder);
273  Optional<Value *> widenICmpRangeCheckIncrementingLoop(LoopICmp LatchCheck,
274  LoopICmp RangeCheck,
275  SCEVExpander &Expander,
276  IRBuilder<> &Builder);
277  Optional<Value *> widenICmpRangeCheckDecrementingLoop(LoopICmp LatchCheck,
278  LoopICmp RangeCheck,
279  SCEVExpander &Expander,
280  IRBuilder<> &Builder);
281  unsigned collectChecks(SmallVectorImpl<Value *> &Checks, Value *Condition,
282  SCEVExpander &Expander, IRBuilder<> &Builder);
283  bool widenGuardConditions(IntrinsicInst *II, SCEVExpander &Expander);
284  bool widenWidenableBranchGuardConditions(BranchInst *Guard, SCEVExpander &Expander);
285  // If the loop always exits through another block in the loop, we should not
286  // predicate based on the latch check. For example, the latch check can be a
287  // very coarse grained check and there can be more fine grained exit checks
288  // within the loop. We identify such unprofitable loops through BPI.
289  bool isLoopProfitableToPredicate();
290 
291  // When the IV type is wider than the range operand type, we can still do loop
292  // predication, by generating SCEVs for the range and latch that are of the
293  // same type. We achieve this by generating a SCEV truncate expression for the
294  // latch IV. This is done iff truncation of the IV is a safe operation,
295  // without loss of information.
296  // Another way to achieve this is by generating a wider type SCEV for the
297  // range check operand, however, this needs a more involved check that
298  // operands do not overflow. This can lead to loss of information when the
299  // range operand is of the form: add i32 %offset, %iv. We need to prove that
300  // sext(x + y) is same as sext(x) + sext(y).
301  // This function returns true if we can safely represent the IV type in
302  // the RangeCheckType without loss of information.
303  bool isSafeToTruncateWideIVType(Type *RangeCheckType);
304  // Return the loopLatchCheck corresponding to the RangeCheckType if safe to do
305  // so.
306  Optional<LoopICmp> generateLoopLatchCheck(Type *RangeCheckType);
307 
308 public:
309  LoopPredication(ScalarEvolution *SE, BranchProbabilityInfo *BPI)
310  : SE(SE), BPI(BPI){};
311  bool runOnLoop(Loop *L);
312 };
313 
314 class LoopPredicationLegacyPass : public LoopPass {
315 public:
316  static char ID;
317  LoopPredicationLegacyPass() : LoopPass(ID) {
319  }
320 
321  void getAnalysisUsage(AnalysisUsage &AU) const override {
324  }
325 
326  bool runOnLoop(Loop *L, LPPassManager &LPM) override {
327  if (skipLoop(L))
328  return false;
329  auto *SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
330  BranchProbabilityInfo &BPI =
331  getAnalysis<BranchProbabilityInfoWrapperPass>().getBPI();
332  LoopPredication LP(SE, &BPI);
333  return LP.runOnLoop(L);
334  }
335 };
336 
338 } // end namespace llvm
339 
340 INITIALIZE_PASS_BEGIN(LoopPredicationLegacyPass, "loop-predication",
341  "Loop predication", false, false)
344 INITIALIZE_PASS_END(LoopPredicationLegacyPass, "loop-predication",
345  "Loop predication", false, false)
346 
348  return new LoopPredicationLegacyPass();
349 }
350 
353  LPMUpdater &U) {
354  const auto &FAM =
355  AM.getResult<FunctionAnalysisManagerLoopProxy>(L, AR).getManager();
356  Function *F = L.getHeader()->getParent();
357  auto *BPI = FAM.getCachedResult<BranchProbabilityAnalysis>(*F);
358  LoopPredication LP(&AR.SE, BPI);
359  if (!LP.runOnLoop(&L))
360  return PreservedAnalyses::all();
361 
363 }
364 
366 LoopPredication::parseLoopICmp(ICmpInst::Predicate Pred, Value *LHS,
367  Value *RHS) {
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  IRBuilder<> &Builder,
391  ICmpInst::Predicate Pred, const SCEV *LHS,
392  const SCEV *RHS, Instruction *InsertAt) {
393  // TODO: we can check isLoopEntryGuardedByCond before emitting the check
394 
395  Type *Ty = LHS->getType();
396  assert(Ty == RHS->getType() && "expandCheck operands have different types?");
397 
398  if (SE->isLoopEntryGuardedByCond(L, Pred, LHS, RHS))
399  return Builder.getTrue();
400 
401  Value *LHSV = Expander.expandCodeFor(LHS, Ty, InsertAt);
402  Value *RHSV = Expander.expandCodeFor(RHS, Ty, InsertAt);
403  return Builder.CreateICmp(Pred, LHSV, RHSV);
404 }
405 
407 LoopPredication::generateLoopLatchCheck(Type *RangeCheckType) {
408 
409  auto *LatchType = LatchCheck.IV->getType();
410  if (RangeCheckType == LatchType)
411  return LatchCheck;
412  // For now, bail out if latch type is narrower than range type.
413  if (DL->getTypeSizeInBits(LatchType) < DL->getTypeSizeInBits(RangeCheckType))
414  return None;
415  if (!isSafeToTruncateWideIVType(RangeCheckType))
416  return None;
417  // We can now safely identify the truncated version of the IV and limit for
418  // RangeCheckType.
419  LoopICmp NewLatchCheck;
420  NewLatchCheck.Pred = LatchCheck.Pred;
421  NewLatchCheck.IV = dyn_cast<SCEVAddRecExpr>(
422  SE->getTruncateExpr(LatchCheck.IV, RangeCheckType));
423  if (!NewLatchCheck.IV)
424  return None;
425  NewLatchCheck.Limit = SE->getTruncateExpr(LatchCheck.Limit, RangeCheckType);
426  LLVM_DEBUG(dbgs() << "IV of type: " << *LatchType
427  << "can be represented as range check type:"
428  << *RangeCheckType << "\n");
429  LLVM_DEBUG(dbgs() << "LatchCheck.IV: " << *NewLatchCheck.IV << "\n");
430  LLVM_DEBUG(dbgs() << "LatchCheck.Limit: " << *NewLatchCheck.Limit << "\n");
431  return NewLatchCheck;
432 }
433 
434 bool LoopPredication::isSupportedStep(const SCEV* Step) {
435  return Step->isOne() || (Step->isAllOnesValue() && EnableCountDownLoop);
436 }
437 
438 bool LoopPredication::CanExpand(const SCEV* S) {
439  return SE->isLoopInvariant(S, L) && isSafeToExpand(S, *SE);
440 }
441 
442 Optional<Value *> LoopPredication::widenICmpRangeCheckIncrementingLoop(
443  LoopPredication::LoopICmp LatchCheck, LoopPredication::LoopICmp RangeCheck,
444  SCEVExpander &Expander, IRBuilder<> &Builder) {
445  auto *Ty = RangeCheck.IV->getType();
446  // Generate the widened condition for the forward loop:
447  // guardStart u< guardLimit &&
448  // latchLimit <pred> guardLimit - 1 - guardStart + latchStart
449  // where <pred> depends on the latch condition predicate. See the file
450  // header comment for the reasoning.
451  // guardLimit - guardStart + latchStart - 1
452  const SCEV *GuardStart = RangeCheck.IV->getStart();
453  const SCEV *GuardLimit = RangeCheck.Limit;
454  const SCEV *LatchStart = LatchCheck.IV->getStart();
455  const SCEV *LatchLimit = LatchCheck.Limit;
456 
457  // guardLimit - guardStart + latchStart - 1
458  const SCEV *RHS =
459  SE->getAddExpr(SE->getMinusSCEV(GuardLimit, GuardStart),
460  SE->getMinusSCEV(LatchStart, SE->getOne(Ty)));
461  if (!CanExpand(GuardStart) || !CanExpand(GuardLimit) ||
462  !CanExpand(LatchLimit) || !CanExpand(RHS)) {
463  LLVM_DEBUG(dbgs() << "Can't expand limit check!\n");
464  return None;
465  }
466  auto LimitCheckPred =
468 
469  LLVM_DEBUG(dbgs() << "LHS: " << *LatchLimit << "\n");
470  LLVM_DEBUG(dbgs() << "RHS: " << *RHS << "\n");
471  LLVM_DEBUG(dbgs() << "Pred: " << LimitCheckPred << "\n");
472 
473  Instruction *InsertAt = Preheader->getTerminator();
474  auto *LimitCheck =
475  expandCheck(Expander, Builder, LimitCheckPred, LatchLimit, RHS, InsertAt);
476  auto *FirstIterationCheck = expandCheck(Expander, Builder, RangeCheck.Pred,
477  GuardStart, GuardLimit, InsertAt);
478  return Builder.CreateAnd(FirstIterationCheck, LimitCheck);
479 }
480 
481 Optional<Value *> LoopPredication::widenICmpRangeCheckDecrementingLoop(
482  LoopPredication::LoopICmp LatchCheck, LoopPredication::LoopICmp RangeCheck,
483  SCEVExpander &Expander, IRBuilder<> &Builder) {
484  auto *Ty = RangeCheck.IV->getType();
485  const SCEV *GuardStart = RangeCheck.IV->getStart();
486  const SCEV *GuardLimit = RangeCheck.Limit;
487  const SCEV *LatchLimit = LatchCheck.Limit;
488  if (!CanExpand(GuardStart) || !CanExpand(GuardLimit) ||
489  !CanExpand(LatchLimit)) {
490  LLVM_DEBUG(dbgs() << "Can't expand limit check!\n");
491  return None;
492  }
493  // The decrement of the latch check IV should be the same as the
494  // rangeCheckIV.
495  auto *PostDecLatchCheckIV = LatchCheck.IV->getPostIncExpr(*SE);
496  if (RangeCheck.IV != PostDecLatchCheckIV) {
497  LLVM_DEBUG(dbgs() << "Not the same. PostDecLatchCheckIV: "
498  << *PostDecLatchCheckIV
499  << " and RangeCheckIV: " << *RangeCheck.IV << "\n");
500  return None;
501  }
502 
503  // Generate the widened condition for CountDownLoop:
504  // guardStart u< guardLimit &&
505  // latchLimit <pred> 1.
506  // See the header comment for reasoning of the checks.
507  Instruction *InsertAt = Preheader->getTerminator();
508  auto LimitCheckPred =
510  auto *FirstIterationCheck = expandCheck(Expander, Builder, ICmpInst::ICMP_ULT,
511  GuardStart, GuardLimit, InsertAt);
512  auto *LimitCheck = expandCheck(Expander, Builder, LimitCheckPred, LatchLimit,
513  SE->getOne(Ty), InsertAt);
514  return Builder.CreateAnd(FirstIterationCheck, LimitCheck);
515 }
516 
517 /// If ICI can be widened to a loop invariant condition emits the loop
518 /// invariant condition in the loop preheader and return it, otherwise
519 /// returns None.
520 Optional<Value *> LoopPredication::widenICmpRangeCheck(ICmpInst *ICI,
521  SCEVExpander &Expander,
522  IRBuilder<> &Builder) {
523  LLVM_DEBUG(dbgs() << "Analyzing ICmpInst condition:\n");
524  LLVM_DEBUG(ICI->dump());
525 
526  // parseLoopStructure guarantees that the latch condition is:
527  // ++i <pred> latchLimit, where <pred> is u<, u<=, s<, or s<=.
528  // We are looking for the range checks of the form:
529  // i u< guardLimit
530  auto RangeCheck = parseLoopICmp(ICI);
531  if (!RangeCheck) {
532  LLVM_DEBUG(dbgs() << "Failed to parse the loop latch condition!\n");
533  return None;
534  }
535  LLVM_DEBUG(dbgs() << "Guard check:\n");
536  LLVM_DEBUG(RangeCheck->dump());
537  if (RangeCheck->Pred != ICmpInst::ICMP_ULT) {
538  LLVM_DEBUG(dbgs() << "Unsupported range check predicate("
539  << RangeCheck->Pred << ")!\n");
540  return None;
541  }
542  auto *RangeCheckIV = RangeCheck->IV;
543  if (!RangeCheckIV->isAffine()) {
544  LLVM_DEBUG(dbgs() << "Range check IV is not affine!\n");
545  return None;
546  }
547  auto *Step = RangeCheckIV->getStepRecurrence(*SE);
548  // We cannot just compare with latch IV step because the latch and range IVs
549  // may have different types.
550  if (!isSupportedStep(Step)) {
551  LLVM_DEBUG(dbgs() << "Range check and latch have IVs different steps!\n");
552  return None;
553  }
554  auto *Ty = RangeCheckIV->getType();
555  auto CurrLatchCheckOpt = generateLoopLatchCheck(Ty);
556  if (!CurrLatchCheckOpt) {
557  LLVM_DEBUG(dbgs() << "Failed to generate a loop latch check "
558  "corresponding to range type: "
559  << *Ty << "\n");
560  return None;
561  }
562 
563  LoopICmp CurrLatchCheck = *CurrLatchCheckOpt;
564  // At this point, the range and latch step should have the same type, but need
565  // not have the same value (we support both 1 and -1 steps).
566  assert(Step->getType() ==
567  CurrLatchCheck.IV->getStepRecurrence(*SE)->getType() &&
568  "Range and latch steps should be of same type!");
569  if (Step != CurrLatchCheck.IV->getStepRecurrence(*SE)) {
570  LLVM_DEBUG(dbgs() << "Range and latch have different step values!\n");
571  return None;
572  }
573 
574  if (Step->isOne())
575  return widenICmpRangeCheckIncrementingLoop(CurrLatchCheck, *RangeCheck,
576  Expander, Builder);
577  else {
578  assert(Step->isAllOnesValue() && "Step should be -1!");
579  return widenICmpRangeCheckDecrementingLoop(CurrLatchCheck, *RangeCheck,
580  Expander, Builder);
581  }
582 }
583 
584 unsigned LoopPredication::collectChecks(SmallVectorImpl<Value *> &Checks,
585  Value *Condition,
586  SCEVExpander &Expander,
587  IRBuilder<> &Builder) {
588  unsigned NumWidened = 0;
589  // The guard condition is expected to be in form of:
590  // cond1 && cond2 && cond3 ...
591  // Iterate over subconditions looking for icmp conditions which can be
592  // widened across loop iterations. Widening these conditions remember the
593  // resulting list of subconditions in Checks vector.
594  SmallVector<Value *, 4> Worklist(1, Condition);
595  SmallPtrSet<Value *, 4> Visited;
596  do {
597  Value *Condition = Worklist.pop_back_val();
598  if (!Visited.insert(Condition).second)
599  continue;
600 
601  Value *LHS, *RHS;
602  using namespace llvm::PatternMatch;
603  if (match(Condition, m_And(m_Value(LHS), m_Value(RHS)))) {
604  Worklist.push_back(LHS);
605  Worklist.push_back(RHS);
606  continue;
607  }
608 
609  if (ICmpInst *ICI = dyn_cast<ICmpInst>(Condition)) {
610  if (auto NewRangeCheck = widenICmpRangeCheck(ICI, Expander, Builder)) {
611  Checks.push_back(NewRangeCheck.getValue());
612  NumWidened++;
613  continue;
614  }
615  }
616 
617  // Save the condition as is if we can't widen it
618  Checks.push_back(Condition);
619  } while (!Worklist.empty());
620  return NumWidened;
621 }
622 
623 bool LoopPredication::widenGuardConditions(IntrinsicInst *Guard,
624  SCEVExpander &Expander) {
625  LLVM_DEBUG(dbgs() << "Processing guard:\n");
626  LLVM_DEBUG(Guard->dump());
627 
628  TotalConsidered++;
630  IRBuilder<> Builder(cast<Instruction>(Preheader->getTerminator()));
631  unsigned NumWidened = collectChecks(Checks, Guard->getOperand(0), Expander,
632  Builder);
633  if (NumWidened == 0)
634  return false;
635 
636  TotalWidened += NumWidened;
637 
638  // Emit the new guard condition
639  Builder.SetInsertPoint(Guard);
640  Value *LastCheck = nullptr;
641  for (auto *Check : Checks)
642  if (!LastCheck)
643  LastCheck = Check;
644  else
645  LastCheck = Builder.CreateAnd(LastCheck, Check);
646  Guard->setOperand(0, LastCheck);
647 
648  LLVM_DEBUG(dbgs() << "Widened checks = " << NumWidened << "\n");
649  return true;
650 }
651 
652 bool LoopPredication::widenWidenableBranchGuardConditions(
653  BranchInst *Guard, SCEVExpander &Expander) {
654  assert(isGuardAsWidenableBranch(Guard) && "Must be!");
655  LLVM_DEBUG(dbgs() << "Processing guard:\n");
656  LLVM_DEBUG(Guard->dump());
657 
658  TotalConsidered++;
660  IRBuilder<> Builder(cast<Instruction>(Preheader->getTerminator()));
661  Value *Condition = nullptr, *WidenableCondition = nullptr;
662  BasicBlock *GBB = nullptr, *DBB = nullptr;
663  parseWidenableBranch(Guard, Condition, WidenableCondition, GBB, DBB);
664  unsigned NumWidened = collectChecks(Checks, Condition, Expander, Builder);
665  if (NumWidened == 0)
666  return false;
667 
668  TotalWidened += NumWidened;
669 
670  // Emit the new guard condition
671  Builder.SetInsertPoint(Guard);
672  Value *LastCheck = nullptr;
673  for (auto *Check : Checks)
674  if (!LastCheck)
675  LastCheck = Check;
676  else
677  LastCheck = Builder.CreateAnd(LastCheck, Check);
678  // Make sure that the check contains widenable condition and therefore can be
679  // further widened.
680  LastCheck = Builder.CreateAnd(LastCheck, WidenableCondition);
681  Guard->setOperand(0, LastCheck);
683  "Stopped being a guard after transform?");
684 
685  LLVM_DEBUG(dbgs() << "Widened checks = " << NumWidened << "\n");
686  return true;
687 }
688 
689 Optional<LoopPredication::LoopICmp> LoopPredication::parseLoopLatchICmp() {
690  using namespace PatternMatch;
691 
692  BasicBlock *LoopLatch = L->getLoopLatch();
693  if (!LoopLatch) {
694  LLVM_DEBUG(dbgs() << "The loop doesn't have a single latch!\n");
695  return None;
696  }
697 
698  ICmpInst::Predicate Pred;
699  Value *LHS, *RHS;
700  BasicBlock *TrueDest, *FalseDest;
701 
702  if (!match(LoopLatch->getTerminator(),
703  m_Br(m_ICmp(Pred, m_Value(LHS), m_Value(RHS)), TrueDest,
704  FalseDest))) {
705  LLVM_DEBUG(dbgs() << "Failed to match the latch terminator!\n");
706  return None;
707  }
708  assert((TrueDest == L->getHeader() || FalseDest == L->getHeader()) &&
709  "One of the latch's destinations must be the header");
710  if (TrueDest != L->getHeader())
711  Pred = ICmpInst::getInversePredicate(Pred);
712 
713  auto Result = parseLoopICmp(Pred, LHS, RHS);
714  if (!Result) {
715  LLVM_DEBUG(dbgs() << "Failed to parse the loop latch condition!\n");
716  return None;
717  }
718 
719  // Check affine first, so if it's not we don't try to compute the step
720  // recurrence.
721  if (!Result->IV->isAffine()) {
722  LLVM_DEBUG(dbgs() << "The induction variable is not affine!\n");
723  return None;
724  }
725 
726  auto *Step = Result->IV->getStepRecurrence(*SE);
727  if (!isSupportedStep(Step)) {
728  LLVM_DEBUG(dbgs() << "Unsupported loop stride(" << *Step << ")!\n");
729  return None;
730  }
731 
732  auto IsUnsupportedPredicate = [](const SCEV *Step, ICmpInst::Predicate Pred) {
733  if (Step->isOne()) {
734  return Pred != ICmpInst::ICMP_ULT && Pred != ICmpInst::ICMP_SLT &&
735  Pred != ICmpInst::ICMP_ULE && Pred != ICmpInst::ICMP_SLE;
736  } else {
737  assert(Step->isAllOnesValue() && "Step should be -1!");
738  return Pred != ICmpInst::ICMP_UGT && Pred != ICmpInst::ICMP_SGT &&
739  Pred != ICmpInst::ICMP_UGE && Pred != ICmpInst::ICMP_SGE;
740  }
741  };
742 
743  if (IsUnsupportedPredicate(Step, Result->Pred)) {
744  LLVM_DEBUG(dbgs() << "Unsupported loop latch predicate(" << Result->Pred
745  << ")!\n");
746  return None;
747  }
748  return Result;
749 }
750 
751 // Returns true if its safe to truncate the IV to RangeCheckType.
752 bool LoopPredication::isSafeToTruncateWideIVType(Type *RangeCheckType) {
753  if (!EnableIVTruncation)
754  return false;
755  assert(DL->getTypeSizeInBits(LatchCheck.IV->getType()) >
756  DL->getTypeSizeInBits(RangeCheckType) &&
757  "Expected latch check IV type to be larger than range check operand "
758  "type!");
759  // The start and end values of the IV should be known. This is to guarantee
760  // that truncating the wide type will not lose information.
761  auto *Limit = dyn_cast<SCEVConstant>(LatchCheck.Limit);
762  auto *Start = dyn_cast<SCEVConstant>(LatchCheck.IV->getStart());
763  if (!Limit || !Start)
764  return false;
765  // This check makes sure that the IV does not change sign during loop
766  // iterations. Consider latchType = i64, LatchStart = 5, Pred = ICMP_SGE,
767  // LatchEnd = 2, rangeCheckType = i32. If it's not a monotonic predicate, the
768  // IV wraps around, and the truncation of the IV would lose the range of
769  // iterations between 2^32 and 2^64.
770  bool Increasing;
771  if (!SE->isMonotonicPredicate(LatchCheck.IV, LatchCheck.Pred, Increasing))
772  return false;
773  // The active bits should be less than the bits in the RangeCheckType. This
774  // guarantees that truncating the latch check to RangeCheckType is a safe
775  // operation.
776  auto RangeCheckTypeBitSize = DL->getTypeSizeInBits(RangeCheckType);
777  return Start->getAPInt().getActiveBits() < RangeCheckTypeBitSize &&
778  Limit->getAPInt().getActiveBits() < RangeCheckTypeBitSize;
779 }
780 
781 bool LoopPredication::isLoopProfitableToPredicate() {
782  if (SkipProfitabilityChecks || !BPI)
783  return true;
784 
786  L->getExitEdges(ExitEdges);
787  // If there is only one exiting edge in the loop, it is always profitable to
788  // predicate the loop.
789  if (ExitEdges.size() == 1)
790  return true;
791 
792  // Calculate the exiting probabilities of all exiting edges from the loop,
793  // starting with the LatchExitProbability.
794  // Heuristic for profitability: If any of the exiting blocks' probability of
795  // exiting the loop is larger than exiting through the latch block, it's not
796  // profitable to predicate the loop.
797  auto *LatchBlock = L->getLoopLatch();
798  assert(LatchBlock && "Should have a single latch at this point!");
799  auto *LatchTerm = LatchBlock->getTerminator();
800  assert(LatchTerm->getNumSuccessors() == 2 &&
801  "expected to be an exiting block with 2 succs!");
802  unsigned LatchBrExitIdx =
803  LatchTerm->getSuccessor(0) == L->getHeader() ? 1 : 0;
804  BranchProbability LatchExitProbability =
805  BPI->getEdgeProbability(LatchBlock, LatchBrExitIdx);
806 
807  // Protect against degenerate inputs provided by the user. Providing a value
808  // less than one, can invert the definition of profitable loop predication.
809  float ScaleFactor = LatchExitProbabilityScale;
810  if (ScaleFactor < 1) {
811  LLVM_DEBUG(
812  dbgs()
813  << "Ignored user setting for loop-predication-latch-probability-scale: "
814  << LatchExitProbabilityScale << "\n");
815  LLVM_DEBUG(dbgs() << "The value is set to 1.0\n");
816  ScaleFactor = 1.0;
817  }
818  const auto LatchProbabilityThreshold =
819  LatchExitProbability * ScaleFactor;
820 
821  for (const auto &ExitEdge : ExitEdges) {
822  BranchProbability ExitingBlockProbability =
823  BPI->getEdgeProbability(ExitEdge.first, ExitEdge.second);
824  // Some exiting edge has higher probability than the latch exiting edge.
825  // No longer profitable to predicate.
826  if (ExitingBlockProbability > LatchProbabilityThreshold)
827  return false;
828  }
829  // Using BPI, we have concluded that the most probable way to exit from the
830  // loop is through the latch (or there's no profile information and all
831  // exits are equally likely).
832  return true;
833 }
834 
835 bool LoopPredication::runOnLoop(Loop *Loop) {
836  L = Loop;
837 
838  LLVM_DEBUG(dbgs() << "Analyzing ");
839  LLVM_DEBUG(L->dump());
840 
841  Module *M = L->getHeader()->getModule();
842 
843  // There is nothing to do if the module doesn't use guards
844  auto *GuardDecl =
845  M->getFunction(Intrinsic::getName(Intrinsic::experimental_guard));
846  bool HasIntrinsicGuards = GuardDecl && !GuardDecl->use_empty();
847  auto *WCDecl = M->getFunction(
848  Intrinsic::getName(Intrinsic::experimental_widenable_condition));
849  bool HasWidenableConditions =
850  PredicateWidenableBranchGuards && WCDecl && !WCDecl->use_empty();
851  if (!HasIntrinsicGuards && !HasWidenableConditions)
852  return false;
853 
854  DL = &M->getDataLayout();
855 
856  Preheader = L->getLoopPreheader();
857  if (!Preheader)
858  return false;
859 
860  auto LatchCheckOpt = parseLoopLatchICmp();
861  if (!LatchCheckOpt)
862  return false;
863  LatchCheck = *LatchCheckOpt;
864 
865  LLVM_DEBUG(dbgs() << "Latch check:\n");
866  LLVM_DEBUG(LatchCheck.dump());
867 
868  if (!isLoopProfitableToPredicate()) {
869  LLVM_DEBUG(dbgs() << "Loop not profitable to predicate!\n");
870  return false;
871  }
872  // Collect all the guards into a vector and process later, so as not
873  // to invalidate the instruction iterator.
875  SmallVector<BranchInst *, 4> GuardsAsWidenableBranches;
876  for (const auto BB : L->blocks()) {
877  for (auto &I : *BB)
878  if (isGuard(&I))
879  Guards.push_back(cast<IntrinsicInst>(&I));
881  isGuardAsWidenableBranch(BB->getTerminator()))
882  GuardsAsWidenableBranches.push_back(
883  cast<BranchInst>(BB->getTerminator()));
884  }
885 
886  if (Guards.empty() && GuardsAsWidenableBranches.empty())
887  return false;
888 
889  SCEVExpander Expander(*SE, *DL, "loop-predication");
890 
891  bool Changed = false;
892  for (auto *Guard : Guards)
893  Changed |= widenGuardConditions(Guard, Expander);
894  for (auto *Guard : GuardsAsWidenableBranches)
895  Changed |= widenWidenableBranchGuardConditions(Guard, Expander);
896 
897  return Changed;
898 }
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:748
A parsed version of the target data layout string in and methods for querying it. ...
Definition: DataLayout.h:110
class_match< Value > m_Value()
Match an arbitrary value and ignore it.
Definition: PatternMatch.h:70
Value * CreateICmp(CmpInst::Predicate P, Value *LHS, Value *RHS, const Twine &Name="")
Definition: IRBuilder.h:1984
BlockT * getLoopLatch() const
If there is a single latch block for this loop, return it.
Definition: LoopInfoImpl.h:224
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
PreservedAnalyses getLoopPassPreservedAnalyses()
Returns the minimum set of Analyses that all loop passes must preserve.
STATISTIC(TotalConsidered, "Number of guards considered")
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:769
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
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:672
unsigned less than
Definition: InstrTypes.h:671
bool isLoopInvariant(const SCEV *S, const Loop *L)
Return true if the value of the given SCEV is unchanging in the specified loop.
bool isMonotonicPredicate(const SCEVAddRecExpr *LHS, ICmpInst::Predicate Pred, bool &Increasing)
Return true if, for all loop invariant X, the predicate "LHS `Pred` X" is monotonically increasing or...
The adaptor from a function pass to a loop pass computes these analyses and makes them available to t...
F(f)
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
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:4342
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:625
Predicate getInversePredicate() const
For example, EQ -> NE, UGT -> ULE, SLT -> SGE, OEQ -> UNE, UGT -> OLE, OLT -> UGE, etc.
Definition: InstrTypes.h:745
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:99
Analysis pass which computes BranchProbabilityInfo.
This node represents a polynomial recurrence on the trip count of the specified loop.
void SetInsertPoint(BasicBlock *TheBB)
This specifies that created instructions should be appended to the end of the specified block...
Definition: IRBuilder.h:126
Legacy analysis pass which computes BranchProbabilityInfo.
Value * getOperand(unsigned i) const
Definition: User.h:169
static cl::opt< bool > EnableIVTruncation("loop-predication-enable-iv-truncation", cl::Hidden, cl::init(true))
bool isLoopEntryGuardedByCond(const Loop *L, ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS)
Test whether entry to the loop is protected by a conditional between LHS and RHS. ...
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:423
void dump(const SparseBitVector< ElementSize > &LHS, raw_ostream &out)
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:153
const SCEV * getOne(Type *Ty)
Return a SCEV for the constant 1 of a specific type.
void dump() const
Definition: LoopInfo.cpp:378
LLVM Basic Block Representation.
Definition: BasicBlock.h:57
The instances of the Type class are immutable: once they are created, they are never changed...
Definition: Type.h:45
ConstantInt * getTrue()
Get the constant value for i1 true.
Definition: IRBuilder.h:286
Conditional or Unconditional Branch instruction.
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:370
const SCEV * getAddExpr(SmallVectorImpl< const SCEV *> &Ops, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
Get a canonical add expression, or something simpler if possible.
brc_match< Cond_t > m_Br(const Cond_t &C, BasicBlock *&T, BasicBlock *&F)
Represent the analysis usage information of a pass.
bool parseWidenableBranch(const User *U, Value *&Condition, Value *&WidenableCondition, BasicBlock *&IfTrueBB, BasicBlock *&IfFalseBB)
If U is widenable branch looking like: cond = ...
Definition: GuardUtils.cpp:38
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:646
Value * expandCodeFor(const SCEV *SH, Type *Ty, Instruction *I)
Insert code to directly compute the specified SCEV expression into the program.
const SCEV * getMinusSCEV(const SCEV *LHS, const SCEV *RHS, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
Return LHS-RHS. Minus is represented in SCEV as A+B*-1.
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:159
size_t size() const
Definition: SmallVector.h:52
INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false) RegBankSelect
signed greater than
Definition: InstrTypes.h:673
BranchProbability getEdgeProbability(const BasicBlock *Src, unsigned IndexInSuccessors) const
Get an edge&#39;s probability, relative to other out-edges of the Src.
void getExitEdges(SmallVectorImpl< Edge > &ExitEdges) const
Return all pairs of (inside_block,outside_block).
Definition: LoopInfoImpl.h:154
This class provides an interface for updating the loop pass manager based on mutations to the loop ne...
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements...
Definition: SmallPtrSet.h:417
bool isAllOnesValue() const
Return true if the expression is a constant all-ones value.
Type * getType() const
Return the LLVM type of this SCEV expression.
An analysis over an "inner" IR unit that provides access to an analysis manager over a "outer" IR uni...
Definition: PassManager.h:1153
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:841
Module.h This file contains the declarations for the Module class.
signed less than
Definition: InstrTypes.h:675
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:374
Predicate getFlippedStrictnessPredicate() const
For predicate of kind "is X or equal to 0" returns the predicate "is X".
Definition: InstrTypes.h:776
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:676
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))
uint64_t getTypeSizeInBits(Type *Ty) const
Size examples:
Definition: DataLayout.h:593
Predicate getPredicate() const
Return the predicate for this instruction.
Definition: InstrTypes.h:721
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:670
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:464
#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:322
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
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
void initializeLoopPredicationLegacyPassPass(PassRegistry &)
PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM, LoopStandardAnalysisResults &AR, LPMUpdater &U)
bool isOne() const
Return true if the expression is a constant one.
LLVM Value Representation.
Definition: Value.h:72
const SCEV * getSCEV(Value *V)
Return a SCEV expression for the full generality of the specified expression.
const SCEV * getTruncateExpr(const SCEV *Op, Type *Ty, unsigned Depth=0)
bool isGuardAsWidenableBranch(const User *U)
Returns true iff U has semantics of a guard expressed in a form of a widenable conditional branch to ...
Definition: GuardUtils.cpp:22
unsigned greater than
Definition: InstrTypes.h:669
Predicate getSwappedPredicate() const
For example, EQ->EQ, SLE->SGE, ULT->UGT, OEQ->OEQ, ULE->UGE, OLT->OGT, etc.
Definition: InstrTypes.h:761
A container for analyses that lazily runs them and caches their results.
#define LLVM_DEBUG(X)
Definition: Debug.h:122
bool isSafeToExpand(const SCEV *S, ScalarEvolution &SE)
Return true if the given expression is safe to expand in the sense that all materialized values are s...
iterator_range< block_iterator > blocks() const
Definition: LoopInfo.h:155
bool use_empty() const
Definition: Value.h:322
signed greater or equal
Definition: InstrTypes.h:674
A wrapper class for inspecting calls to intrinsic functions.
Definition: IntrinsicInst.h:43
This class represents a constant integer value.
CmpClass_match< LHS, RHS, ICmpInst, ICmpInst::Predicate > m_ICmp(ICmpInst::Predicate &Pred, const LHS &L, const RHS &R)