LLVM  7.0.0svn
LoopPredication.cpp
Go to the documentation of this file.
1 //===-- LoopPredication.cpp - Guard based loop predication pass -----------===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // The LoopPredication pass tries to convert loop variant range checks to loop
11 // invariant by widening checks across loop iterations. For example, it will
12 // convert
13 //
14 // for (i = 0; i < n; i++) {
15 // guard(i < len);
16 // ...
17 // }
18 //
19 // to
20 //
21 // for (i = 0; i < n; i++) {
22 // guard(n - 1 < len);
23 // ...
24 // }
25 //
26 // After this transformation the condition of the guard is loop invariant, so
27 // loop-unswitch can later unswitch the loop by this condition which basically
28 // predicates the loop by the widened condition:
29 //
30 // if (n - 1 < len)
31 // for (i = 0; i < n; i++) {
32 // ...
33 // }
34 // else
35 // deoptimize
36 //
37 // It's tempting to rely on SCEV here, but it has proven to be problematic.
38 // Generally the facts SCEV provides about the increment step of add
39 // recurrences are true if the backedge of the loop is taken, which implicitly
40 // assumes that the guard doesn't fail. Using these facts to optimize the
41 // guard results in a circular logic where the guard is optimized under the
42 // assumption that it never fails.
43 //
44 // For example, in the loop below the induction variable will be marked as nuw
45 // basing on the guard. Basing on nuw the guard predicate will be considered
46 // monotonic. Given a monotonic condition it's tempting to replace the induction
47 // variable in the condition with its value on the last iteration. But this
48 // transformation is not correct, e.g. e = 4, b = 5 breaks the loop.
49 //
50 // for (int i = b; i != e; i++)
51 // guard(i u< len)
52 //
53 // One of the ways to reason about this problem is to use an inductive proof
54 // approach. Given the loop:
55 //
56 // if (B(0)) {
57 // do {
58 // I = PHI(0, I.INC)
59 // I.INC = I + Step
60 // guard(G(I));
61 // } while (B(I));
62 // }
63 //
64 // where B(x) and G(x) are predicates that map integers to booleans, we want a
65 // loop invariant expression M such the following program has the same semantics
66 // as the above:
67 //
68 // if (B(0)) {
69 // do {
70 // I = PHI(0, I.INC)
71 // I.INC = I + Step
72 // guard(G(0) && M);
73 // } while (B(I));
74 // }
75 //
76 // One solution for M is M = forall X . (G(X) && B(X)) => G(X + Step)
77 //
78 // Informal proof that the transformation above is correct:
79 //
80 // By the definition of guards we can rewrite the guard condition to:
81 // G(I) && G(0) && M
82 //
83 // Let's prove that for each iteration of the loop:
84 // G(0) && M => G(I)
85 // And the condition above can be simplified to G(Start) && M.
86 //
87 // Induction base.
88 // G(0) && M => G(0)
89 //
90 // Induction step. Assuming G(0) && M => G(I) on the subsequent
91 // iteration:
92 //
93 // B(I) is true because it's the backedge condition.
94 // G(I) is true because the backedge is guarded by this condition.
95 //
96 // So M = forall X . (G(X) && B(X)) => G(X + Step) implies G(I + Step).
97 //
98 // Note that we can use anything stronger than M, i.e. any condition which
99 // implies M.
100 //
101 // When S = 1 (i.e. forward iterating loop), the transformation is supported
102 // when:
103 // * The loop has a single latch with the condition of the form:
104 // B(X) = latchStart + X <pred> latchLimit,
105 // where <pred> is u<, u<=, s<, or s<=.
106 // * The guard condition is of the form
107 // G(X) = guardStart + X u< guardLimit
108 //
109 // For the ult latch comparison case M is:
110 // forall X . guardStart + X u< guardLimit && latchStart + X <u latchLimit =>
111 // guardStart + X + 1 u< guardLimit
112 //
113 // The only way the antecedent can be true and the consequent can be false is
114 // if
115 // X == guardLimit - 1 - guardStart
116 // (and guardLimit is non-zero, but we won't use this latter fact).
117 // If X == guardLimit - 1 - guardStart then the second half of the antecedent is
118 // latchStart + guardLimit - 1 - guardStart u< latchLimit
119 // and its negation is
120 // latchStart + guardLimit - 1 - guardStart u>= latchLimit
121 //
122 // In other words, if
123 // latchLimit u<= latchStart + guardLimit - 1 - guardStart
124 // then:
125 // (the ranges below are written in ConstantRange notation, where [A, B) is the
126 // set for (I = A; I != B; I++ /*maywrap*/) yield(I);)
127 //
128 // forall X . guardStart + X u< guardLimit &&
129 // latchStart + X u< latchLimit =>
130 // guardStart + X + 1 u< guardLimit
131 // == forall X . guardStart + X u< guardLimit &&
132 // latchStart + X u< latchStart + guardLimit - 1 - guardStart =>
133 // guardStart + X + 1 u< guardLimit
134 // == forall X . (guardStart + X) in [0, guardLimit) &&
135 // (latchStart + X) in [0, latchStart + guardLimit - 1 - guardStart) =>
136 // (guardStart + X + 1) in [0, guardLimit)
137 // == forall X . X in [-guardStart, guardLimit - guardStart) &&
138 // X in [-latchStart, guardLimit - 1 - guardStart) =>
139 // X in [-guardStart - 1, guardLimit - guardStart - 1)
140 // == true
141 //
142 // So the widened condition is:
143 // guardStart u< guardLimit &&
144 // latchStart + guardLimit - 1 - guardStart u>= latchLimit
145 // Similarly for ule condition the widened condition is:
146 // guardStart u< guardLimit &&
147 // latchStart + guardLimit - 1 - guardStart u> latchLimit
148 // For slt condition the widened condition is:
149 // guardStart u< guardLimit &&
150 // latchStart + guardLimit - 1 - guardStart s>= latchLimit
151 // For sle condition the widened condition is:
152 // guardStart u< guardLimit &&
153 // latchStart + guardLimit - 1 - guardStart s> latchLimit
154 //
155 // When S = -1 (i.e. reverse iterating loop), the transformation is supported
156 // when:
157 // * The loop has a single latch with the condition of the form:
158 // B(X) = X <pred> latchLimit, where <pred> is u>, u>=, s>, or s>=.
159 // * The guard condition is of the form
160 // G(X) = X - 1 u< guardLimit
161 //
162 // For the ugt latch comparison case M is:
163 // forall X. X-1 u< guardLimit and X u> latchLimit => X-2 u< guardLimit
164 //
165 // The only way the antecedent can be true and the consequent can be false is if
166 // X == 1.
167 // If X == 1 then the second half of the antecedent is
168 // 1 u> latchLimit, and its negation is latchLimit u>= 1.
169 //
170 // So the widened condition is:
171 // guardStart u< guardLimit && latchLimit u>= 1.
172 // Similarly for sgt condition the widened condition is:
173 // guardStart u< guardLimit && latchLimit s>= 1.
174 // For uge condition the widened condition is:
175 // guardStart u< guardLimit && latchLimit u> 1.
176 // For sge condition the widened condition is:
177 // guardStart u< guardLimit && latchLimit s> 1.
178 //===----------------------------------------------------------------------===//
179 
182 #include "llvm/Analysis/LoopInfo.h"
183 #include "llvm/Analysis/LoopPass.h"
187 #include "llvm/IR/Function.h"
188 #include "llvm/IR/GlobalValue.h"
189 #include "llvm/IR/IntrinsicInst.h"
190 #include "llvm/IR/Module.h"
191 #include "llvm/IR/PatternMatch.h"
192 #include "llvm/Pass.h"
193 #include "llvm/Support/Debug.h"
194 #include "llvm/Transforms/Scalar.h"
196 
197 #define DEBUG_TYPE "loop-predication"
198 
199 using namespace llvm;
200 
201 static cl::opt<bool> EnableIVTruncation("loop-predication-enable-iv-truncation",
202  cl::Hidden, cl::init(true));
203 
204 static cl::opt<bool> EnableCountDownLoop("loop-predication-enable-count-down-loop",
205  cl::Hidden, cl::init(true));
206 
207 static cl::opt<bool>
208  SkipProfitabilityChecks("loop-predication-skip-profitability-checks",
209  cl::Hidden, cl::init(false));
210 
211 // This is the scale factor for the latch probability. We use this during
212 // profitability analysis to find other exiting blocks that have a much higher
213 // probability of exiting the loop instead of loop exiting via latch.
214 // This value should be greater than 1 for a sane profitability check.
216  "loop-predication-latch-probability-scale", cl::Hidden, cl::init(2.0),
217  cl::desc("scale factor for the latch probability. Value should be greater "
218  "than 1. Lower values are ignored"));
219 
220 namespace {
221 class LoopPredication {
222  /// Represents an induction variable check:
223  /// icmp Pred, <induction variable>, <loop invariant limit>
224  struct LoopICmp {
225  ICmpInst::Predicate Pred;
226  const SCEVAddRecExpr *IV;
227  const SCEV *Limit;
228  LoopICmp(ICmpInst::Predicate Pred, const SCEVAddRecExpr *IV,
229  const SCEV *Limit)
230  : Pred(Pred), IV(IV), Limit(Limit) {}
231  LoopICmp() {}
232  void dump() {
233  dbgs() << "LoopICmp Pred = " << Pred << ", IV = " << *IV
234  << ", Limit = " << *Limit << "\n";
235  }
236  };
237 
238  ScalarEvolution *SE;
240 
241  Loop *L;
242  const DataLayout *DL;
243  BasicBlock *Preheader;
244  LoopICmp LatchCheck;
245 
246  bool isSupportedStep(const SCEV* Step);
247  Optional<LoopICmp> parseLoopICmp(ICmpInst *ICI) {
248  return parseLoopICmp(ICI->getPredicate(), ICI->getOperand(0),
249  ICI->getOperand(1));
250  }
251  Optional<LoopICmp> parseLoopICmp(ICmpInst::Predicate Pred, Value *LHS,
252  Value *RHS);
253 
254  Optional<LoopICmp> parseLoopLatchICmp();
255 
256  bool CanExpand(const SCEV* S);
257  Value *expandCheck(SCEVExpander &Expander, IRBuilder<> &Builder,
258  ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS,
259  Instruction *InsertAt);
260 
261  Optional<Value *> widenICmpRangeCheck(ICmpInst *ICI, SCEVExpander &Expander,
262  IRBuilder<> &Builder);
263  Optional<Value *> widenICmpRangeCheckIncrementingLoop(LoopICmp LatchCheck,
264  LoopICmp RangeCheck,
265  SCEVExpander &Expander,
266  IRBuilder<> &Builder);
267  Optional<Value *> widenICmpRangeCheckDecrementingLoop(LoopICmp LatchCheck,
268  LoopICmp RangeCheck,
269  SCEVExpander &Expander,
270  IRBuilder<> &Builder);
271  bool widenGuardConditions(IntrinsicInst *II, SCEVExpander &Expander);
272 
273  // If the loop always exits through another block in the loop, we should not
274  // predicate based on the latch check. For example, the latch check can be a
275  // very coarse grained check and there can be more fine grained exit checks
276  // within the loop. We identify such unprofitable loops through BPI.
277  bool isLoopProfitableToPredicate();
278 
279  // When the IV type is wider than the range operand type, we can still do loop
280  // predication, by generating SCEVs for the range and latch that are of the
281  // same type. We achieve this by generating a SCEV truncate expression for the
282  // latch IV. This is done iff truncation of the IV is a safe operation,
283  // without loss of information.
284  // Another way to achieve this is by generating a wider type SCEV for the
285  // range check operand, however, this needs a more involved check that
286  // operands do not overflow. This can lead to loss of information when the
287  // range operand is of the form: add i32 %offset, %iv. We need to prove that
288  // sext(x + y) is same as sext(x) + sext(y).
289  // This function returns true if we can safely represent the IV type in
290  // the RangeCheckType without loss of information.
291  bool isSafeToTruncateWideIVType(Type *RangeCheckType);
292  // Return the loopLatchCheck corresponding to the RangeCheckType if safe to do
293  // so.
294  Optional<LoopICmp> generateLoopLatchCheck(Type *RangeCheckType);
295 
296 public:
297  LoopPredication(ScalarEvolution *SE, BranchProbabilityInfo *BPI)
298  : SE(SE), BPI(BPI){};
299  bool runOnLoop(Loop *L);
300 };
301 
302 class LoopPredicationLegacyPass : public LoopPass {
303 public:
304  static char ID;
305  LoopPredicationLegacyPass() : LoopPass(ID) {
307  }
308 
309  void getAnalysisUsage(AnalysisUsage &AU) const override {
312  }
313 
314  bool runOnLoop(Loop *L, LPPassManager &LPM) override {
315  if (skipLoop(L))
316  return false;
317  auto *SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
318  BranchProbabilityInfo &BPI =
319  getAnalysis<BranchProbabilityInfoWrapperPass>().getBPI();
320  LoopPredication LP(SE, &BPI);
321  return LP.runOnLoop(L);
322  }
323 };
324 
326 } // end namespace llvm
327 
328 INITIALIZE_PASS_BEGIN(LoopPredicationLegacyPass, "loop-predication",
329  "Loop predication", false, false)
332 INITIALIZE_PASS_END(LoopPredicationLegacyPass, "loop-predication",
333  "Loop predication", false, false)
334 
336  return new LoopPredicationLegacyPass();
337 }
338 
341  LPMUpdater &U) {
342  const auto &FAM =
343  AM.getResult<FunctionAnalysisManagerLoopProxy>(L, AR).getManager();
344  Function *F = L.getHeader()->getParent();
345  auto *BPI = FAM.getCachedResult<BranchProbabilityAnalysis>(*F);
346  LoopPredication LP(&AR.SE, BPI);
347  if (!LP.runOnLoop(&L))
348  return PreservedAnalyses::all();
349 
351 }
352 
354 LoopPredication::parseLoopICmp(ICmpInst::Predicate Pred, Value *LHS,
355  Value *RHS) {
356  const SCEV *LHSS = SE->getSCEV(LHS);
357  if (isa<SCEVCouldNotCompute>(LHSS))
358  return None;
359  const SCEV *RHSS = SE->getSCEV(RHS);
360  if (isa<SCEVCouldNotCompute>(RHSS))
361  return None;
362 
363  // Canonicalize RHS to be loop invariant bound, LHS - a loop computable IV
364  if (SE->isLoopInvariant(LHSS, L)) {
365  std::swap(LHS, RHS);
366  std::swap(LHSS, RHSS);
367  Pred = ICmpInst::getSwappedPredicate(Pred);
368  }
369 
370  const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(LHSS);
371  if (!AR || AR->getLoop() != L)
372  return None;
373 
374  return LoopICmp(Pred, AR, RHSS);
375 }
376 
377 Value *LoopPredication::expandCheck(SCEVExpander &Expander,
378  IRBuilder<> &Builder,
379  ICmpInst::Predicate Pred, const SCEV *LHS,
380  const SCEV *RHS, Instruction *InsertAt) {
381  // TODO: we can check isLoopEntryGuardedByCond before emitting the check
382 
383  Type *Ty = LHS->getType();
384  assert(Ty == RHS->getType() && "expandCheck operands have different types?");
385 
386  if (SE->isLoopEntryGuardedByCond(L, Pred, LHS, RHS))
387  return Builder.getTrue();
388 
389  Value *LHSV = Expander.expandCodeFor(LHS, Ty, InsertAt);
390  Value *RHSV = Expander.expandCodeFor(RHS, Ty, InsertAt);
391  return Builder.CreateICmp(Pred, LHSV, RHSV);
392 }
393 
395 LoopPredication::generateLoopLatchCheck(Type *RangeCheckType) {
396 
397  auto *LatchType = LatchCheck.IV->getType();
398  if (RangeCheckType == LatchType)
399  return LatchCheck;
400  // For now, bail out if latch type is narrower than range type.
401  if (DL->getTypeSizeInBits(LatchType) < DL->getTypeSizeInBits(RangeCheckType))
402  return None;
403  if (!isSafeToTruncateWideIVType(RangeCheckType))
404  return None;
405  // We can now safely identify the truncated version of the IV and limit for
406  // RangeCheckType.
407  LoopICmp NewLatchCheck;
408  NewLatchCheck.Pred = LatchCheck.Pred;
409  NewLatchCheck.IV = dyn_cast<SCEVAddRecExpr>(
410  SE->getTruncateExpr(LatchCheck.IV, RangeCheckType));
411  if (!NewLatchCheck.IV)
412  return None;
413  NewLatchCheck.Limit = SE->getTruncateExpr(LatchCheck.Limit, RangeCheckType);
414  DEBUG(dbgs() << "IV of type: " << *LatchType
415  << "can be represented as range check type:" << *RangeCheckType
416  << "\n");
417  DEBUG(dbgs() << "LatchCheck.IV: " << *NewLatchCheck.IV << "\n");
418  DEBUG(dbgs() << "LatchCheck.Limit: " << *NewLatchCheck.Limit << "\n");
419  return NewLatchCheck;
420 }
421 
422 bool LoopPredication::isSupportedStep(const SCEV* Step) {
423  return Step->isOne() || (Step->isAllOnesValue() && EnableCountDownLoop);
424 }
425 
426 bool LoopPredication::CanExpand(const SCEV* S) {
427  return SE->isLoopInvariant(S, L) && isSafeToExpand(S, *SE);
428 }
429 
430 Optional<Value *> LoopPredication::widenICmpRangeCheckIncrementingLoop(
431  LoopPredication::LoopICmp LatchCheck, LoopPredication::LoopICmp RangeCheck,
432  SCEVExpander &Expander, IRBuilder<> &Builder) {
433  auto *Ty = RangeCheck.IV->getType();
434  // Generate the widened condition for the forward loop:
435  // guardStart u< guardLimit &&
436  // latchLimit <pred> guardLimit - 1 - guardStart + latchStart
437  // where <pred> depends on the latch condition predicate. See the file
438  // header comment for the reasoning.
439  // guardLimit - guardStart + latchStart - 1
440  const SCEV *GuardStart = RangeCheck.IV->getStart();
441  const SCEV *GuardLimit = RangeCheck.Limit;
442  const SCEV *LatchStart = LatchCheck.IV->getStart();
443  const SCEV *LatchLimit = LatchCheck.Limit;
444 
445  // guardLimit - guardStart + latchStart - 1
446  const SCEV *RHS =
447  SE->getAddExpr(SE->getMinusSCEV(GuardLimit, GuardStart),
448  SE->getMinusSCEV(LatchStart, SE->getOne(Ty)));
449  if (!CanExpand(GuardStart) || !CanExpand(GuardLimit) ||
450  !CanExpand(LatchLimit) || !CanExpand(RHS)) {
451  DEBUG(dbgs() << "Can't expand limit check!\n");
452  return None;
453  }
454  auto LimitCheckPred =
456 
457  DEBUG(dbgs() << "LHS: " << *LatchLimit << "\n");
458  DEBUG(dbgs() << "RHS: " << *RHS << "\n");
459  DEBUG(dbgs() << "Pred: " << LimitCheckPred << "\n");
460 
461  Instruction *InsertAt = Preheader->getTerminator();
462  auto *LimitCheck =
463  expandCheck(Expander, Builder, LimitCheckPred, LatchLimit, RHS, InsertAt);
464  auto *FirstIterationCheck = expandCheck(Expander, Builder, RangeCheck.Pred,
465  GuardStart, GuardLimit, InsertAt);
466  return Builder.CreateAnd(FirstIterationCheck, LimitCheck);
467 }
468 
469 Optional<Value *> LoopPredication::widenICmpRangeCheckDecrementingLoop(
470  LoopPredication::LoopICmp LatchCheck, LoopPredication::LoopICmp RangeCheck,
471  SCEVExpander &Expander, IRBuilder<> &Builder) {
472  auto *Ty = RangeCheck.IV->getType();
473  const SCEV *GuardStart = RangeCheck.IV->getStart();
474  const SCEV *GuardLimit = RangeCheck.Limit;
475  const SCEV *LatchLimit = LatchCheck.Limit;
476  if (!CanExpand(GuardStart) || !CanExpand(GuardLimit) ||
477  !CanExpand(LatchLimit)) {
478  DEBUG(dbgs() << "Can't expand limit check!\n");
479  return None;
480  }
481  // The decrement of the latch check IV should be the same as the
482  // rangeCheckIV.
483  auto *PostDecLatchCheckIV = LatchCheck.IV->getPostIncExpr(*SE);
484  if (RangeCheck.IV != PostDecLatchCheckIV) {
485  DEBUG(dbgs() << "Not the same. PostDecLatchCheckIV: "
486  << *PostDecLatchCheckIV
487  << " and RangeCheckIV: " << *RangeCheck.IV << "\n");
488  return None;
489  }
490 
491  // Generate the widened condition for CountDownLoop:
492  // guardStart u< guardLimit &&
493  // latchLimit <pred> 1.
494  // See the header comment for reasoning of the checks.
495  Instruction *InsertAt = Preheader->getTerminator();
496  auto LimitCheckPred =
498  auto *FirstIterationCheck = expandCheck(Expander, Builder, ICmpInst::ICMP_ULT,
499  GuardStart, GuardLimit, InsertAt);
500  auto *LimitCheck = expandCheck(Expander, Builder, LimitCheckPred, LatchLimit,
501  SE->getOne(Ty), InsertAt);
502  return Builder.CreateAnd(FirstIterationCheck, LimitCheck);
503 }
504 
505 /// If ICI can be widened to a loop invariant condition emits the loop
506 /// invariant condition in the loop preheader and return it, otherwise
507 /// returns None.
508 Optional<Value *> LoopPredication::widenICmpRangeCheck(ICmpInst *ICI,
509  SCEVExpander &Expander,
510  IRBuilder<> &Builder) {
511  DEBUG(dbgs() << "Analyzing ICmpInst condition:\n");
512  DEBUG(ICI->dump());
513 
514  // parseLoopStructure guarantees that the latch condition is:
515  // ++i <pred> latchLimit, where <pred> is u<, u<=, s<, or s<=.
516  // We are looking for the range checks of the form:
517  // i u< guardLimit
518  auto RangeCheck = parseLoopICmp(ICI);
519  if (!RangeCheck) {
520  DEBUG(dbgs() << "Failed to parse the loop latch condition!\n");
521  return None;
522  }
523  DEBUG(dbgs() << "Guard check:\n");
524  DEBUG(RangeCheck->dump());
525  if (RangeCheck->Pred != ICmpInst::ICMP_ULT) {
526  DEBUG(dbgs() << "Unsupported range check predicate(" << RangeCheck->Pred
527  << ")!\n");
528  return None;
529  }
530  auto *RangeCheckIV = RangeCheck->IV;
531  if (!RangeCheckIV->isAffine()) {
532  DEBUG(dbgs() << "Range check IV is not affine!\n");
533  return None;
534  }
535  auto *Step = RangeCheckIV->getStepRecurrence(*SE);
536  // We cannot just compare with latch IV step because the latch and range IVs
537  // may have different types.
538  if (!isSupportedStep(Step)) {
539  DEBUG(dbgs() << "Range check and latch have IVs different steps!\n");
540  return None;
541  }
542  auto *Ty = RangeCheckIV->getType();
543  auto CurrLatchCheckOpt = generateLoopLatchCheck(Ty);
544  if (!CurrLatchCheckOpt) {
545  DEBUG(dbgs() << "Failed to generate a loop latch check "
546  "corresponding to range type: "
547  << *Ty << "\n");
548  return None;
549  }
550 
551  LoopICmp CurrLatchCheck = *CurrLatchCheckOpt;
552  // At this point, the range and latch step should have the same type, but need
553  // not have the same value (we support both 1 and -1 steps).
554  assert(Step->getType() ==
555  CurrLatchCheck.IV->getStepRecurrence(*SE)->getType() &&
556  "Range and latch steps should be of same type!");
557  if (Step != CurrLatchCheck.IV->getStepRecurrence(*SE)) {
558  DEBUG(dbgs() << "Range and latch have different step values!\n");
559  return None;
560  }
561 
562  if (Step->isOne())
563  return widenICmpRangeCheckIncrementingLoop(CurrLatchCheck, *RangeCheck,
564  Expander, Builder);
565  else {
566  assert(Step->isAllOnesValue() && "Step should be -1!");
567  return widenICmpRangeCheckDecrementingLoop(CurrLatchCheck, *RangeCheck,
568  Expander, Builder);
569  }
570 }
571 
572 bool LoopPredication::widenGuardConditions(IntrinsicInst *Guard,
573  SCEVExpander &Expander) {
574  DEBUG(dbgs() << "Processing guard:\n");
575  DEBUG(Guard->dump());
576 
577  IRBuilder<> Builder(cast<Instruction>(Preheader->getTerminator()));
578 
579  // The guard condition is expected to be in form of:
580  // cond1 && cond2 && cond3 ...
581  // Iterate over subconditions looking for icmp conditions which can be
582  // widened across loop iterations. Widening these conditions remember the
583  // resulting list of subconditions in Checks vector.
584  SmallVector<Value *, 4> Worklist(1, Guard->getOperand(0));
585  SmallPtrSet<Value *, 4> Visited;
586 
588 
589  unsigned NumWidened = 0;
590  do {
591  Value *Condition = Worklist.pop_back_val();
592  if (!Visited.insert(Condition).second)
593  continue;
594 
595  Value *LHS, *RHS;
596  using namespace llvm::PatternMatch;
597  if (match(Condition, m_And(m_Value(LHS), m_Value(RHS)))) {
598  Worklist.push_back(LHS);
599  Worklist.push_back(RHS);
600  continue;
601  }
602 
603  if (ICmpInst *ICI = dyn_cast<ICmpInst>(Condition)) {
604  if (auto NewRangeCheck = widenICmpRangeCheck(ICI, Expander, Builder)) {
605  Checks.push_back(NewRangeCheck.getValue());
606  NumWidened++;
607  continue;
608  }
609  }
610 
611  // Save the condition as is if we can't widen it
612  Checks.push_back(Condition);
613  } while (Worklist.size() != 0);
614 
615  if (NumWidened == 0)
616  return false;
617 
618  // Emit the new guard condition
619  Builder.SetInsertPoint(Guard);
620  Value *LastCheck = nullptr;
621  for (auto *Check : Checks)
622  if (!LastCheck)
623  LastCheck = Check;
624  else
625  LastCheck = Builder.CreateAnd(LastCheck, Check);
626  Guard->setOperand(0, LastCheck);
627 
628  DEBUG(dbgs() << "Widened checks = " << NumWidened << "\n");
629  return true;
630 }
631 
632 Optional<LoopPredication::LoopICmp> LoopPredication::parseLoopLatchICmp() {
633  using namespace PatternMatch;
634 
635  BasicBlock *LoopLatch = L->getLoopLatch();
636  if (!LoopLatch) {
637  DEBUG(dbgs() << "The loop doesn't have a single latch!\n");
638  return None;
639  }
640 
641  ICmpInst::Predicate Pred;
642  Value *LHS, *RHS;
643  BasicBlock *TrueDest, *FalseDest;
644 
645  if (!match(LoopLatch->getTerminator(),
646  m_Br(m_ICmp(Pred, m_Value(LHS), m_Value(RHS)), TrueDest,
647  FalseDest))) {
648  DEBUG(dbgs() << "Failed to match the latch terminator!\n");
649  return None;
650  }
651  assert((TrueDest == L->getHeader() || FalseDest == L->getHeader()) &&
652  "One of the latch's destinations must be the header");
653  if (TrueDest != L->getHeader())
654  Pred = ICmpInst::getInversePredicate(Pred);
655 
656  auto Result = parseLoopICmp(Pred, LHS, RHS);
657  if (!Result) {
658  DEBUG(dbgs() << "Failed to parse the loop latch condition!\n");
659  return None;
660  }
661 
662  // Check affine first, so if it's not we don't try to compute the step
663  // recurrence.
664  if (!Result->IV->isAffine()) {
665  DEBUG(dbgs() << "The induction variable is not affine!\n");
666  return None;
667  }
668 
669  auto *Step = Result->IV->getStepRecurrence(*SE);
670  if (!isSupportedStep(Step)) {
671  DEBUG(dbgs() << "Unsupported loop stride(" << *Step << ")!\n");
672  return None;
673  }
674 
675  auto IsUnsupportedPredicate = [](const SCEV *Step, ICmpInst::Predicate Pred) {
676  if (Step->isOne()) {
677  return Pred != ICmpInst::ICMP_ULT && Pred != ICmpInst::ICMP_SLT &&
678  Pred != ICmpInst::ICMP_ULE && Pred != ICmpInst::ICMP_SLE;
679  } else {
680  assert(Step->isAllOnesValue() && "Step should be -1!");
681  return Pred != ICmpInst::ICMP_UGT && Pred != ICmpInst::ICMP_SGT &&
682  Pred != ICmpInst::ICMP_UGE && Pred != ICmpInst::ICMP_SGE;
683  }
684  };
685 
686  if (IsUnsupportedPredicate(Step, Result->Pred)) {
687  DEBUG(dbgs() << "Unsupported loop latch predicate(" << Result->Pred
688  << ")!\n");
689  return None;
690  }
691  return Result;
692 }
693 
694 // Returns true if its safe to truncate the IV to RangeCheckType.
695 bool LoopPredication::isSafeToTruncateWideIVType(Type *RangeCheckType) {
696  if (!EnableIVTruncation)
697  return false;
698  assert(DL->getTypeSizeInBits(LatchCheck.IV->getType()) >
699  DL->getTypeSizeInBits(RangeCheckType) &&
700  "Expected latch check IV type to be larger than range check operand "
701  "type!");
702  // The start and end values of the IV should be known. This is to guarantee
703  // that truncating the wide type will not lose information.
704  auto *Limit = dyn_cast<SCEVConstant>(LatchCheck.Limit);
705  auto *Start = dyn_cast<SCEVConstant>(LatchCheck.IV->getStart());
706  if (!Limit || !Start)
707  return false;
708  // This check makes sure that the IV does not change sign during loop
709  // iterations. Consider latchType = i64, LatchStart = 5, Pred = ICMP_SGE,
710  // LatchEnd = 2, rangeCheckType = i32. If it's not a monotonic predicate, the
711  // IV wraps around, and the truncation of the IV would lose the range of
712  // iterations between 2^32 and 2^64.
713  bool Increasing;
714  if (!SE->isMonotonicPredicate(LatchCheck.IV, LatchCheck.Pred, Increasing))
715  return false;
716  // The active bits should be less than the bits in the RangeCheckType. This
717  // guarantees that truncating the latch check to RangeCheckType is a safe
718  // operation.
719  auto RangeCheckTypeBitSize = DL->getTypeSizeInBits(RangeCheckType);
720  return Start->getAPInt().getActiveBits() < RangeCheckTypeBitSize &&
721  Limit->getAPInt().getActiveBits() < RangeCheckTypeBitSize;
722 }
723 
724 bool LoopPredication::isLoopProfitableToPredicate() {
725  if (SkipProfitabilityChecks || !BPI)
726  return true;
727 
729  L->getExitEdges(ExitEdges);
730  // If there is only one exiting edge in the loop, it is always profitable to
731  // predicate the loop.
732  if (ExitEdges.size() == 1)
733  return true;
734 
735  // Calculate the exiting probabilities of all exiting edges from the loop,
736  // starting with the LatchExitProbability.
737  // Heuristic for profitability: If any of the exiting blocks' probability of
738  // exiting the loop is larger than exiting through the latch block, it's not
739  // profitable to predicate the loop.
740  auto *LatchBlock = L->getLoopLatch();
741  assert(LatchBlock && "Should have a single latch at this point!");
742  auto *LatchTerm = LatchBlock->getTerminator();
743  assert(LatchTerm->getNumSuccessors() == 2 &&
744  "expected to be an exiting block with 2 succs!");
745  unsigned LatchBrExitIdx =
746  LatchTerm->getSuccessor(0) == L->getHeader() ? 1 : 0;
747  BranchProbability LatchExitProbability =
748  BPI->getEdgeProbability(LatchBlock, LatchBrExitIdx);
749 
750  // Protect against degenerate inputs provided by the user. Providing a value
751  // less than one, can invert the definition of profitable loop predication.
752  float ScaleFactor = LatchExitProbabilityScale;
753  if (ScaleFactor < 1) {
754  DEBUG(
755  dbgs()
756  << "Ignored user setting for loop-predication-latch-probability-scale: "
757  << LatchExitProbabilityScale << "\n");
758  DEBUG(dbgs() << "The value is set to 1.0\n");
759  ScaleFactor = 1.0;
760  }
761  const auto LatchProbabilityThreshold =
762  LatchExitProbability * ScaleFactor;
763 
764  for (const auto &ExitEdge : ExitEdges) {
765  BranchProbability ExitingBlockProbability =
766  BPI->getEdgeProbability(ExitEdge.first, ExitEdge.second);
767  // Some exiting edge has higher probability than the latch exiting edge.
768  // No longer profitable to predicate.
769  if (ExitingBlockProbability > LatchProbabilityThreshold)
770  return false;
771  }
772  // Using BPI, we have concluded that the most probable way to exit from the
773  // loop is through the latch (or there's no profile information and all
774  // exits are equally likely).
775  return true;
776 }
777 
778 bool LoopPredication::runOnLoop(Loop *Loop) {
779  L = Loop;
780 
781  DEBUG(dbgs() << "Analyzing ");
782  DEBUG(L->dump());
783 
784  Module *M = L->getHeader()->getModule();
785 
786  // There is nothing to do if the module doesn't use guards
787  auto *GuardDecl =
788  M->getFunction(Intrinsic::getName(Intrinsic::experimental_guard));
789  if (!GuardDecl || GuardDecl->use_empty())
790  return false;
791 
792  DL = &M->getDataLayout();
793 
794  Preheader = L->getLoopPreheader();
795  if (!Preheader)
796  return false;
797 
798  auto LatchCheckOpt = parseLoopLatchICmp();
799  if (!LatchCheckOpt)
800  return false;
801  LatchCheck = *LatchCheckOpt;
802 
803  DEBUG(dbgs() << "Latch check:\n");
804  DEBUG(LatchCheck.dump());
805 
806  if (!isLoopProfitableToPredicate()) {
807  DEBUG(dbgs()<< "Loop not profitable to predicate!\n");
808  return false;
809  }
810  // Collect all the guards into a vector and process later, so as not
811  // to invalidate the instruction iterator.
813  for (const auto BB : L->blocks())
814  for (auto &I : *BB)
815  if (auto *II = dyn_cast<IntrinsicInst>(&I))
816  if (II->getIntrinsicID() == Intrinsic::experimental_guard)
817  Guards.push_back(II);
818 
819  if (Guards.empty())
820  return false;
821 
822  SCEVExpander Expander(*SE, *DL, "loop-predication");
823 
824  bool Changed = false;
825  for (auto *Guard : Guards)
826  Changed |= widenGuardConditions(Guard, Expander);
827 
828  return Changed;
829 }
Pass interface - Implemented by all &#39;passes&#39;.
Definition: Pass.h:81
static bool Check(DecodeStatus &Out, DecodeStatus In)
BinaryOp_match< LHS, RHS, Instruction::And > m_And(const LHS &L, const RHS &R)
Definition: PatternMatch.h:680
A parsed version of the target data layout string in and methods for querying it. ...
Definition: DataLayout.h:111
class_match< Value > m_Value()
Match an arbitrary value and ignore it.
Definition: PatternMatch.h:72
Value * CreateICmp(CmpInst::Predicate P, Value *LHS, Value *RHS, const Twine &Name="")
Definition: IRBuilder.h:1787
BlockT * getLoopLatch() const
If there is a single latch block for this loop, return it.
Definition: LoopInfoImpl.h:157
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.
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:687
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
loop predication
A Module instance is used to store all the information related to an LLVM module. ...
Definition: Module.h:63
LLVM_ATTRIBUTE_ALWAYS_INLINE size_type size() const
Definition: SmallVector.h:136
The main scalar evolution driver.
BlockT * getLoopPreheader() const
If there is a preheader for this loop, return it.
Definition: LoopInfoImpl.h:106
unsigned less or equal
Definition: InstrTypes.h:911
unsigned less than
Definition: InstrTypes.h:910
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)
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:3682
bool match(Val *V, const Pattern &P)
Definition: PatternMatch.h:49
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:134
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:51
StringRef getName(ID id)
Return the LLVM name for an intrinsic, such as "llvm.ppc.altivec.lvx".
Definition: Function.cpp:604
Predicate getInversePredicate() const
For example, EQ -> NE, UGT -> ULE, SLT -> SGE, OEQ -> UNE, UGT -> OLE, OLT -> UGE, etc.
Definition: InstrTypes.h:983
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:677
BlockT * getHeader() const
Definition: LoopInfo.h:100
Analysis pass which computes BranchProbabilityInfo.
This node represents a polynomial recurrence on the trip count of the specified loop.
Legacy analysis pass which computes BranchProbabilityInfo.
Value * getOperand(unsigned i) const
Definition: User.h:170
Value * getOperand(unsigned i_nocapture) const
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:406
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:444
LLVM Basic Block Representation.
Definition: BasicBlock.h:59
The instances of the Type class are immutable: once they are created, they are never changed...
Definition: Type.h:46
ConstantInt * getTrue()
Get the constant value for i1 true.
Definition: IRBuilder.h:287
const SCEV * getAddExpr(SmallVectorImpl< const SCEV *> &Ops, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
Get a canonical add expression, or something simpler if possible.
brc_match< Cond_t > m_Br(const Cond_t &C, BasicBlock *&T, BasicBlock *&F)
Represent the analysis usage information of a pass.
Pass * createLoopPredicationPass()
This instruction compares its operands according to the predicate given to the constructor.
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Definition: InstrTypes.h:885
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
INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false) RegBankSelect
signed greater than
Definition: InstrTypes.h:912
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:87
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:418
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.
const SCEV * getTruncateExpr(const SCEV *Op, Type *Ty)
An analysis over an "inner" IR unit that provides access to an analysis manager over a "outer" IR uni...
Definition: PassManager.h:1062
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:862
Module.h This file contains the declarations for the Module class.
signed less than
Definition: InstrTypes.h:914
Predicate getFlippedStrictnessPredicate() const
For predicate of kind "is X or equal to 0" returns the predicate "is X".
Definition: InstrTypes.h:1014
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:172
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:924
signed less or equal
Definition: InstrTypes.h:915
void setOperand(unsigned i_nocapture, Value *Val_nocapture)
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...
iterator insert(iterator I, T &&Elt)
Definition: SmallVector.h:480
uint64_t getTypeSizeInBits(Type *Ty) const
Size examples:
Definition: DataLayout.h:560
Predicate getPredicate() const
Return the predicate for this instruction.
Definition: InstrTypes.h:959
Analysis providing branch probability information.
This class represents an analyzed expression in the program.
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:61
unsigned greater or equal
Definition: InstrTypes.h:909
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:439
#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:1223
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:323
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:1058
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:73
const SCEV * getSCEV(Value *V)
Return a SCEV expression for the full generality of the specified expression.
#define DEBUG(X)
Definition: Debug.h:118
unsigned greater than
Definition: InstrTypes.h:908
Predicate getSwappedPredicate() const
For example, EQ->EQ, SLE->SGE, ULT->UGT, OEQ->OEQ, ULE->UGE, OLT->OGT, etc.
Definition: InstrTypes.h:999
A container for analyses that lazily runs them and caches their results.
const TerminatorInst * 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:138
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:156
signed greater or equal
Definition: InstrTypes.h:913
A wrapper class for inspecting calls to intrinsic functions.
Definition: IntrinsicInst.h:44
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)
Definition: PatternMatch.h:943