LLVM  6.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 // For now the transformation is limited to the following case:
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 step of the IV used in the latch condition is 1.
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 //===----------------------------------------------------------------------===//
156 
158 #include "llvm/Analysis/LoopInfo.h"
159 #include "llvm/Analysis/LoopPass.h"
163 #include "llvm/IR/Function.h"
164 #include "llvm/IR/GlobalValue.h"
165 #include "llvm/IR/IntrinsicInst.h"
166 #include "llvm/IR/Module.h"
167 #include "llvm/IR/PatternMatch.h"
168 #include "llvm/Pass.h"
169 #include "llvm/Support/Debug.h"
170 #include "llvm/Transforms/Scalar.h"
172 
173 #define DEBUG_TYPE "loop-predication"
174 
175 using namespace llvm;
176 
177 static cl::opt<bool> EnableIVTruncation("loop-predication-enable-iv-truncation",
178  cl::Hidden, cl::init(true));
179 
180 namespace {
181 class LoopPredication {
182  /// Represents an induction variable check:
183  /// icmp Pred, <induction variable>, <loop invariant limit>
184  struct LoopICmp {
185  ICmpInst::Predicate Pred;
186  const SCEVAddRecExpr *IV;
187  const SCEV *Limit;
188  LoopICmp(ICmpInst::Predicate Pred, const SCEVAddRecExpr *IV,
189  const SCEV *Limit)
190  : Pred(Pred), IV(IV), Limit(Limit) {}
191  LoopICmp() {}
192  void dump() {
193  dbgs() << "LoopICmp Pred = " << Pred << ", IV = " << *IV
194  << ", Limit = " << *Limit << "\n";
195  }
196  };
197 
198  ScalarEvolution *SE;
199 
200  Loop *L;
201  const DataLayout *DL;
202  BasicBlock *Preheader;
203  LoopICmp LatchCheck;
204 
205  bool isSupportedStep(const SCEV* Step);
206  Optional<LoopICmp> parseLoopICmp(ICmpInst *ICI) {
207  return parseLoopICmp(ICI->getPredicate(), ICI->getOperand(0),
208  ICI->getOperand(1));
209  }
210  Optional<LoopICmp> parseLoopICmp(ICmpInst::Predicate Pred, Value *LHS,
211  Value *RHS);
212 
213  Optional<LoopICmp> parseLoopLatchICmp();
214 
215  bool CanExpand(const SCEV* S);
216  Value *expandCheck(SCEVExpander &Expander, IRBuilder<> &Builder,
217  ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS,
218  Instruction *InsertAt);
219 
220  Optional<Value *> widenICmpRangeCheck(ICmpInst *ICI, SCEVExpander &Expander,
221  IRBuilder<> &Builder);
222  Optional<Value *> widenICmpRangeCheckIncrementingLoop(LoopICmp LatchCheck,
223  LoopICmp RangeCheck,
224  SCEVExpander &Expander,
225  IRBuilder<> &Builder);
226 
227  bool widenGuardConditions(IntrinsicInst *II, SCEVExpander &Expander);
228 
229  // When the IV type is wider than the range operand type, we can still do loop
230  // predication, by generating SCEVs for the range and latch that are of the
231  // same type. We achieve this by generating a SCEV truncate expression for the
232  // latch IV. This is done iff truncation of the IV is a safe operation,
233  // without loss of information.
234  // Another way to achieve this is by generating a wider type SCEV for the
235  // range check operand, however, this needs a more involved check that
236  // operands do not overflow. This can lead to loss of information when the
237  // range operand is of the form: add i32 %offset, %iv. We need to prove that
238  // sext(x + y) is same as sext(x) + sext(y).
239  // This function returns true if we can safely represent the IV type in
240  // the RangeCheckType without loss of information.
241  bool isSafeToTruncateWideIVType(Type *RangeCheckType);
242  // Return the loopLatchCheck corresponding to the RangeCheckType if safe to do
243  // so.
244  Optional<LoopICmp> generateLoopLatchCheck(Type *RangeCheckType);
245 public:
246  LoopPredication(ScalarEvolution *SE) : SE(SE){};
247  bool runOnLoop(Loop *L);
248 };
249 
250 class LoopPredicationLegacyPass : public LoopPass {
251 public:
252  static char ID;
253  LoopPredicationLegacyPass() : LoopPass(ID) {
255  }
256 
257  void getAnalysisUsage(AnalysisUsage &AU) const override {
259  }
260 
261  bool runOnLoop(Loop *L, LPPassManager &LPM) override {
262  if (skipLoop(L))
263  return false;
264  auto *SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
265  LoopPredication LP(SE);
266  return LP.runOnLoop(L);
267  }
268 };
269 
271 } // end namespace llvm
272 
273 INITIALIZE_PASS_BEGIN(LoopPredicationLegacyPass, "loop-predication",
274  "Loop predication", false, false)
276 INITIALIZE_PASS_END(LoopPredicationLegacyPass, "loop-predication",
277  "Loop predication", false, false)
278 
280  return new LoopPredicationLegacyPass();
281 }
282 
285  LPMUpdater &U) {
286  LoopPredication LP(&AR.SE);
287  if (!LP.runOnLoop(&L))
288  return PreservedAnalyses::all();
289 
291 }
292 
294 LoopPredication::parseLoopICmp(ICmpInst::Predicate Pred, Value *LHS,
295  Value *RHS) {
296  const SCEV *LHSS = SE->getSCEV(LHS);
297  if (isa<SCEVCouldNotCompute>(LHSS))
298  return None;
299  const SCEV *RHSS = SE->getSCEV(RHS);
300  if (isa<SCEVCouldNotCompute>(RHSS))
301  return None;
302 
303  // Canonicalize RHS to be loop invariant bound, LHS - a loop computable IV
304  if (SE->isLoopInvariant(LHSS, L)) {
305  std::swap(LHS, RHS);
306  std::swap(LHSS, RHSS);
307  Pred = ICmpInst::getSwappedPredicate(Pred);
308  }
309 
310  const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(LHSS);
311  if (!AR || AR->getLoop() != L)
312  return None;
313 
314  return LoopICmp(Pred, AR, RHSS);
315 }
316 
317 Value *LoopPredication::expandCheck(SCEVExpander &Expander,
318  IRBuilder<> &Builder,
319  ICmpInst::Predicate Pred, const SCEV *LHS,
320  const SCEV *RHS, Instruction *InsertAt) {
321  // TODO: we can check isLoopEntryGuardedByCond before emitting the check
322 
323  Type *Ty = LHS->getType();
324  assert(Ty == RHS->getType() && "expandCheck operands have different types?");
325 
326  if (SE->isLoopEntryGuardedByCond(L, Pred, LHS, RHS))
327  return Builder.getTrue();
328 
329  Value *LHSV = Expander.expandCodeFor(LHS, Ty, InsertAt);
330  Value *RHSV = Expander.expandCodeFor(RHS, Ty, InsertAt);
331  return Builder.CreateICmp(Pred, LHSV, RHSV);
332 }
333 
335 LoopPredication::generateLoopLatchCheck(Type *RangeCheckType) {
336 
337  auto *LatchType = LatchCheck.IV->getType();
338  if (RangeCheckType == LatchType)
339  return LatchCheck;
340  // For now, bail out if latch type is narrower than range type.
341  if (DL->getTypeSizeInBits(LatchType) < DL->getTypeSizeInBits(RangeCheckType))
342  return None;
343  if (!isSafeToTruncateWideIVType(RangeCheckType))
344  return None;
345  // We can now safely identify the truncated version of the IV and limit for
346  // RangeCheckType.
347  LoopICmp NewLatchCheck;
348  NewLatchCheck.Pred = LatchCheck.Pred;
349  NewLatchCheck.IV = dyn_cast<SCEVAddRecExpr>(
350  SE->getTruncateExpr(LatchCheck.IV, RangeCheckType));
351  if (!NewLatchCheck.IV)
352  return None;
353  NewLatchCheck.Limit = SE->getTruncateExpr(LatchCheck.Limit, RangeCheckType);
354  DEBUG(dbgs() << "IV of type: " << *LatchType
355  << "can be represented as range check type:" << *RangeCheckType
356  << "\n");
357  DEBUG(dbgs() << "LatchCheck.IV: " << *NewLatchCheck.IV << "\n");
358  DEBUG(dbgs() << "LatchCheck.Limit: " << *NewLatchCheck.Limit << "\n");
359  return NewLatchCheck;
360 }
361 
362 bool LoopPredication::isSupportedStep(const SCEV* Step) {
363  return Step->isOne();
364 }
365 
366 bool LoopPredication::CanExpand(const SCEV* S) {
367  return SE->isLoopInvariant(S, L) && isSafeToExpand(S, *SE);
368 }
369 
370 Optional<Value *> LoopPredication::widenICmpRangeCheckIncrementingLoop(
371  LoopPredication::LoopICmp LatchCheck, LoopPredication::LoopICmp RangeCheck,
372  SCEVExpander &Expander, IRBuilder<> &Builder) {
373  auto *Ty = RangeCheck.IV->getType();
374  // Generate the widened condition for the forward loop:
375  // guardStart u< guardLimit &&
376  // latchLimit <pred> guardLimit - 1 - guardStart + latchStart
377  // where <pred> depends on the latch condition predicate. See the file
378  // header comment for the reasoning.
379  // guardLimit - guardStart + latchStart - 1
380  const SCEV *GuardStart = RangeCheck.IV->getStart();
381  const SCEV *GuardLimit = RangeCheck.Limit;
382  const SCEV *LatchStart = LatchCheck.IV->getStart();
383  const SCEV *LatchLimit = LatchCheck.Limit;
384 
385  // guardLimit - guardStart + latchStart - 1
386  const SCEV *RHS =
387  SE->getAddExpr(SE->getMinusSCEV(GuardLimit, GuardStart),
388  SE->getMinusSCEV(LatchStart, SE->getOne(Ty)));
389  if (!CanExpand(GuardStart) || !CanExpand(GuardLimit) ||
390  !CanExpand(LatchLimit) || !CanExpand(RHS)) {
391  DEBUG(dbgs() << "Can't expand limit check!\n");
392  return None;
393  }
394  ICmpInst::Predicate LimitCheckPred;
395  switch (LatchCheck.Pred) {
396  case ICmpInst::ICMP_ULT:
397  LimitCheckPred = ICmpInst::ICMP_ULE;
398  break;
399  case ICmpInst::ICMP_ULE:
400  LimitCheckPred = ICmpInst::ICMP_ULT;
401  break;
402  case ICmpInst::ICMP_SLT:
403  LimitCheckPred = ICmpInst::ICMP_SLE;
404  break;
405  case ICmpInst::ICMP_SLE:
406  LimitCheckPred = ICmpInst::ICMP_SLT;
407  break;
408  default:
409  llvm_unreachable("Unsupported loop latch!");
410  }
411 
412  DEBUG(dbgs() << "LHS: " << *LatchLimit << "\n");
413  DEBUG(dbgs() << "RHS: " << *RHS << "\n");
414  DEBUG(dbgs() << "Pred: " << LimitCheckPred << "\n");
415 
416  Instruction *InsertAt = Preheader->getTerminator();
417  auto *LimitCheck =
418  expandCheck(Expander, Builder, LimitCheckPred, LatchLimit, RHS, InsertAt);
419  auto *FirstIterationCheck = expandCheck(Expander, Builder, RangeCheck.Pred,
420  GuardStart, GuardLimit, InsertAt);
421  return Builder.CreateAnd(FirstIterationCheck, LimitCheck);
422 }
423 /// If ICI can be widened to a loop invariant condition emits the loop
424 /// invariant condition in the loop preheader and return it, otherwise
425 /// returns None.
426 Optional<Value *> LoopPredication::widenICmpRangeCheck(ICmpInst *ICI,
427  SCEVExpander &Expander,
428  IRBuilder<> &Builder) {
429  DEBUG(dbgs() << "Analyzing ICmpInst condition:\n");
430  DEBUG(ICI->dump());
431 
432  // parseLoopStructure guarantees that the latch condition is:
433  // ++i <pred> latchLimit, where <pred> is u<, u<=, s<, or s<=.
434  // We are looking for the range checks of the form:
435  // i u< guardLimit
436  auto RangeCheck = parseLoopICmp(ICI);
437  if (!RangeCheck) {
438  DEBUG(dbgs() << "Failed to parse the loop latch condition!\n");
439  return None;
440  }
441  DEBUG(dbgs() << "Guard check:\n");
442  DEBUG(RangeCheck->dump());
443  if (RangeCheck->Pred != ICmpInst::ICMP_ULT) {
444  DEBUG(dbgs() << "Unsupported range check predicate(" << RangeCheck->Pred
445  << ")!\n");
446  return None;
447  }
448  auto *RangeCheckIV = RangeCheck->IV;
449  if (!RangeCheckIV->isAffine()) {
450  DEBUG(dbgs() << "Range check IV is not affine!\n");
451  return None;
452  }
453  auto *Step = RangeCheckIV->getStepRecurrence(*SE);
454  // We cannot just compare with latch IV step because the latch and range IVs
455  // may have different types.
456  if (!isSupportedStep(Step)) {
457  DEBUG(dbgs() << "Range check and latch have IVs different steps!\n");
458  return None;
459  }
460  auto *Ty = RangeCheckIV->getType();
461  auto CurrLatchCheckOpt = generateLoopLatchCheck(Ty);
462  if (!CurrLatchCheckOpt) {
463  DEBUG(dbgs() << "Failed to generate a loop latch check "
464  "corresponding to range type: "
465  << *Ty << "\n");
466  return None;
467  }
468 
469  LoopICmp CurrLatchCheck = *CurrLatchCheckOpt;
470  // At this point the range check step and latch step should have the same
471  // value and type.
472  assert(Step == CurrLatchCheck.IV->getStepRecurrence(*SE) &&
473  "Range and latch should have same step recurrence!");
474 
475  return widenICmpRangeCheckIncrementingLoop(CurrLatchCheck, *RangeCheck,
476  Expander, Builder);
477 }
478 
479 bool LoopPredication::widenGuardConditions(IntrinsicInst *Guard,
480  SCEVExpander &Expander) {
481  DEBUG(dbgs() << "Processing guard:\n");
482  DEBUG(Guard->dump());
483 
484  IRBuilder<> Builder(cast<Instruction>(Preheader->getTerminator()));
485 
486  // The guard condition is expected to be in form of:
487  // cond1 && cond2 && cond3 ...
488  // Iterate over subconditions looking for for icmp conditions which can be
489  // widened across loop iterations. Widening these conditions remember the
490  // resulting list of subconditions in Checks vector.
491  SmallVector<Value *, 4> Worklist(1, Guard->getOperand(0));
492  SmallPtrSet<Value *, 4> Visited;
493 
495 
496  unsigned NumWidened = 0;
497  do {
498  Value *Condition = Worklist.pop_back_val();
499  if (!Visited.insert(Condition).second)
500  continue;
501 
502  Value *LHS, *RHS;
503  using namespace llvm::PatternMatch;
504  if (match(Condition, m_And(m_Value(LHS), m_Value(RHS)))) {
505  Worklist.push_back(LHS);
506  Worklist.push_back(RHS);
507  continue;
508  }
509 
510  if (ICmpInst *ICI = dyn_cast<ICmpInst>(Condition)) {
511  if (auto NewRangeCheck = widenICmpRangeCheck(ICI, Expander, Builder)) {
512  Checks.push_back(NewRangeCheck.getValue());
513  NumWidened++;
514  continue;
515  }
516  }
517 
518  // Save the condition as is if we can't widen it
519  Checks.push_back(Condition);
520  } while (Worklist.size() != 0);
521 
522  if (NumWidened == 0)
523  return false;
524 
525  // Emit the new guard condition
526  Builder.SetInsertPoint(Guard);
527  Value *LastCheck = nullptr;
528  for (auto *Check : Checks)
529  if (!LastCheck)
530  LastCheck = Check;
531  else
532  LastCheck = Builder.CreateAnd(LastCheck, Check);
533  Guard->setOperand(0, LastCheck);
534 
535  DEBUG(dbgs() << "Widened checks = " << NumWidened << "\n");
536  return true;
537 }
538 
539 Optional<LoopPredication::LoopICmp> LoopPredication::parseLoopLatchICmp() {
540  using namespace PatternMatch;
541 
542  BasicBlock *LoopLatch = L->getLoopLatch();
543  if (!LoopLatch) {
544  DEBUG(dbgs() << "The loop doesn't have a single latch!\n");
545  return None;
546  }
547 
548  ICmpInst::Predicate Pred;
549  Value *LHS, *RHS;
550  BasicBlock *TrueDest, *FalseDest;
551 
552  if (!match(LoopLatch->getTerminator(),
553  m_Br(m_ICmp(Pred, m_Value(LHS), m_Value(RHS)), TrueDest,
554  FalseDest))) {
555  DEBUG(dbgs() << "Failed to match the latch terminator!\n");
556  return None;
557  }
558  assert((TrueDest == L->getHeader() || FalseDest == L->getHeader()) &&
559  "One of the latch's destinations must be the header");
560  if (TrueDest != L->getHeader())
561  Pred = ICmpInst::getInversePredicate(Pred);
562 
563  auto Result = parseLoopICmp(Pred, LHS, RHS);
564  if (!Result) {
565  DEBUG(dbgs() << "Failed to parse the loop latch condition!\n");
566  return None;
567  }
568 
569  // Check affine first, so if it's not we don't try to compute the step
570  // recurrence.
571  if (!Result->IV->isAffine()) {
572  DEBUG(dbgs() << "The induction variable is not affine!\n");
573  return None;
574  }
575 
576  auto *Step = Result->IV->getStepRecurrence(*SE);
577  if (!isSupportedStep(Step)) {
578  DEBUG(dbgs() << "Unsupported loop stride(" << *Step << ")!\n");
579  return None;
580  }
581 
582  auto IsUnsupportedPredicate = [](const SCEV *Step, ICmpInst::Predicate Pred) {
583  assert(Step->isOne() && "expected Step to be one!");
584  return Pred != ICmpInst::ICMP_ULT && Pred != ICmpInst::ICMP_SLT &&
585  Pred != ICmpInst::ICMP_ULE && Pred != ICmpInst::ICMP_SLE;
586  };
587 
588  if (IsUnsupportedPredicate(Step, Result->Pred)) {
589  DEBUG(dbgs() << "Unsupported loop latch predicate(" << Result->Pred
590  << ")!\n");
591  return None;
592  }
593  return Result;
594 }
595 
596 // Returns true if its safe to truncate the IV to RangeCheckType.
597 bool LoopPredication::isSafeToTruncateWideIVType(Type *RangeCheckType) {
598  if (!EnableIVTruncation)
599  return false;
600  assert(DL->getTypeSizeInBits(LatchCheck.IV->getType()) >
601  DL->getTypeSizeInBits(RangeCheckType) &&
602  "Expected latch check IV type to be larger than range check operand "
603  "type!");
604  // The start and end values of the IV should be known. This is to guarantee
605  // that truncating the wide type will not lose information.
606  auto *Limit = dyn_cast<SCEVConstant>(LatchCheck.Limit);
607  auto *Start = dyn_cast<SCEVConstant>(LatchCheck.IV->getStart());
608  if (!Limit || !Start)
609  return false;
610  // This check makes sure that the IV does not change sign during loop
611  // iterations. Consider latchType = i64, LatchStart = 5, Pred = ICMP_SGE,
612  // LatchEnd = 2, rangeCheckType = i32. If it's not a monotonic predicate, the
613  // IV wraps around, and the truncation of the IV would lose the range of
614  // iterations between 2^32 and 2^64.
615  bool Increasing;
616  if (!SE->isMonotonicPredicate(LatchCheck.IV, LatchCheck.Pred, Increasing))
617  return false;
618  // The active bits should be less than the bits in the RangeCheckType. This
619  // guarantees that truncating the latch check to RangeCheckType is a safe
620  // operation.
621  auto RangeCheckTypeBitSize = DL->getTypeSizeInBits(RangeCheckType);
622  return Start->getAPInt().getActiveBits() < RangeCheckTypeBitSize &&
623  Limit->getAPInt().getActiveBits() < RangeCheckTypeBitSize;
624 }
625 
626 bool LoopPredication::runOnLoop(Loop *Loop) {
627  L = Loop;
628 
629  DEBUG(dbgs() << "Analyzing ");
630  DEBUG(L->dump());
631 
632  Module *M = L->getHeader()->getModule();
633 
634  // There is nothing to do if the module doesn't use guards
635  auto *GuardDecl =
636  M->getFunction(Intrinsic::getName(Intrinsic::experimental_guard));
637  if (!GuardDecl || GuardDecl->use_empty())
638  return false;
639 
640  DL = &M->getDataLayout();
641 
642  Preheader = L->getLoopPreheader();
643  if (!Preheader)
644  return false;
645 
646  auto LatchCheckOpt = parseLoopLatchICmp();
647  if (!LatchCheckOpt)
648  return false;
649  LatchCheck = *LatchCheckOpt;
650 
651  DEBUG(dbgs() << "Latch check:\n");
652  DEBUG(LatchCheck.dump());
653 
654  // Collect all the guards into a vector and process later, so as not
655  // to invalidate the instruction iterator.
657  for (const auto BB : L->blocks())
658  for (auto &I : *BB)
659  if (auto *II = dyn_cast<IntrinsicInst>(&I))
660  if (II->getIntrinsicID() == Intrinsic::experimental_guard)
661  Guards.push_back(II);
662 
663  if (Guards.empty())
664  return false;
665 
666  SCEVExpander Expander(*SE, *DL, "loop-predication");
667 
668  bool Changed = false;
669  for (auto *Guard : Guards)
670  Changed |= widenGuardConditions(Guard, Expander);
671 
672  return Changed;
673 }
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:574
A parsed version of the target data layout string in and methods for querying it. ...
Definition: DataLayout.h:109
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:1638
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.
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
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:879
unsigned less than
Definition: InstrTypes.h:878
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...
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:3641
bool match(Val *V, const Pattern &P)
Definition: PatternMatch.h:49
const Module * getModule() const
Return the module owning the function this basic block belongs to, or nullptr it the function does no...
Definition: BasicBlock.cpp:116
#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:591
Predicate getInversePredicate() const
For example, EQ -> NE, UGT -> ULE, SLT -> SGE, OEQ -> UNE, UGT -> OLE, OLT -> UGE, etc.
Definition: InstrTypes.h:951
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
Definition: IRBuilder.h:668
BlockT * getHeader() const
Definition: LoopInfo.h:100
This node represents a polynomial recurrence on the trip count of the specified loop.
Value * getOperand(unsigned i) const
Definition: User.h:154
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:288
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:853
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
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
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
Type * getType() const
Return the LLVM type of this SCEV expression.
const SCEV * getTruncateExpr(const SCEV *Op, Type *Ty)
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:864
Module.h This file contains the declarations for the Module class.
signed less than
Definition: InstrTypes.h:882
void setOperand(unsigned i, Value *Val)
Definition: User.h:159
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:923
signed less or equal
Definition: InstrTypes.h:883
This class uses information about analyze scalars to rewrite expressions in canonical form...
iterator insert(iterator I, T &&Elt)
Definition: SmallVector.h:482
uint64_t getTypeSizeInBits(Type *Ty) const
Size examples:
Definition: DataLayout.h:530
Predicate getPredicate() const
Return the predicate for this instruction.
Definition: InstrTypes.h:927
This class represents an analyzed expression in the program.
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:1023
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
Value * CreateAnd(Value *LHS, Value *RHS, const Twine &Name="")
Definition: IRBuilder.h:1067
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
Predicate getSwappedPredicate() const
For example, EQ->EQ, SLE->SGE, ULT->UGT, OEQ->OEQ, ULE->UGE, OLT->OGT, etc.
Definition: InstrTypes.h:967
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:120
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
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:837