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> 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 //===----------------------------------------------------------------------===//
175 
177 #include "llvm/Analysis/LoopInfo.h"
178 #include "llvm/Analysis/LoopPass.h"
182 #include "llvm/IR/Function.h"
183 #include "llvm/IR/GlobalValue.h"
184 #include "llvm/IR/IntrinsicInst.h"
185 #include "llvm/IR/Module.h"
186 #include "llvm/IR/PatternMatch.h"
187 #include "llvm/Pass.h"
188 #include "llvm/Support/Debug.h"
189 #include "llvm/Transforms/Scalar.h"
191 
192 #define DEBUG_TYPE "loop-predication"
193 
194 using namespace llvm;
195 
196 static cl::opt<bool> EnableIVTruncation("loop-predication-enable-iv-truncation",
197  cl::Hidden, cl::init(true));
198 
199 static cl::opt<bool> EnableCountDownLoop("loop-predication-enable-count-down-loop",
200  cl::Hidden, cl::init(true));
201 namespace {
202 class LoopPredication {
203  /// Represents an induction variable check:
204  /// icmp Pred, <induction variable>, <loop invariant limit>
205  struct LoopICmp {
206  ICmpInst::Predicate Pred;
207  const SCEVAddRecExpr *IV;
208  const SCEV *Limit;
209  LoopICmp(ICmpInst::Predicate Pred, const SCEVAddRecExpr *IV,
210  const SCEV *Limit)
211  : Pred(Pred), IV(IV), Limit(Limit) {}
212  LoopICmp() {}
213  void dump() {
214  dbgs() << "LoopICmp Pred = " << Pred << ", IV = " << *IV
215  << ", Limit = " << *Limit << "\n";
216  }
217  };
218 
219  ScalarEvolution *SE;
220 
221  Loop *L;
222  const DataLayout *DL;
223  BasicBlock *Preheader;
224  LoopICmp LatchCheck;
225 
226  bool isSupportedStep(const SCEV* Step);
227  Optional<LoopICmp> parseLoopICmp(ICmpInst *ICI) {
228  return parseLoopICmp(ICI->getPredicate(), ICI->getOperand(0),
229  ICI->getOperand(1));
230  }
231  Optional<LoopICmp> parseLoopICmp(ICmpInst::Predicate Pred, Value *LHS,
232  Value *RHS);
233 
234  Optional<LoopICmp> parseLoopLatchICmp();
235 
236  bool CanExpand(const SCEV* S);
237  Value *expandCheck(SCEVExpander &Expander, IRBuilder<> &Builder,
238  ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS,
239  Instruction *InsertAt);
240 
241  Optional<Value *> widenICmpRangeCheck(ICmpInst *ICI, SCEVExpander &Expander,
242  IRBuilder<> &Builder);
243  Optional<Value *> widenICmpRangeCheckIncrementingLoop(LoopICmp LatchCheck,
244  LoopICmp RangeCheck,
245  SCEVExpander &Expander,
246  IRBuilder<> &Builder);
247  Optional<Value *> widenICmpRangeCheckDecrementingLoop(LoopICmp LatchCheck,
248  LoopICmp RangeCheck,
249  SCEVExpander &Expander,
250  IRBuilder<> &Builder);
251  bool widenGuardConditions(IntrinsicInst *II, SCEVExpander &Expander);
252 
253  // When the IV type is wider than the range operand type, we can still do loop
254  // predication, by generating SCEVs for the range and latch that are of the
255  // same type. We achieve this by generating a SCEV truncate expression for the
256  // latch IV. This is done iff truncation of the IV is a safe operation,
257  // without loss of information.
258  // Another way to achieve this is by generating a wider type SCEV for the
259  // range check operand, however, this needs a more involved check that
260  // operands do not overflow. This can lead to loss of information when the
261  // range operand is of the form: add i32 %offset, %iv. We need to prove that
262  // sext(x + y) is same as sext(x) + sext(y).
263  // This function returns true if we can safely represent the IV type in
264  // the RangeCheckType without loss of information.
265  bool isSafeToTruncateWideIVType(Type *RangeCheckType);
266  // Return the loopLatchCheck corresponding to the RangeCheckType if safe to do
267  // so.
268  Optional<LoopICmp> generateLoopLatchCheck(Type *RangeCheckType);
269 public:
270  LoopPredication(ScalarEvolution *SE) : SE(SE){};
271  bool runOnLoop(Loop *L);
272 };
273 
274 class LoopPredicationLegacyPass : public LoopPass {
275 public:
276  static char ID;
277  LoopPredicationLegacyPass() : LoopPass(ID) {
279  }
280 
281  void getAnalysisUsage(AnalysisUsage &AU) const override {
283  }
284 
285  bool runOnLoop(Loop *L, LPPassManager &LPM) override {
286  if (skipLoop(L))
287  return false;
288  auto *SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
289  LoopPredication LP(SE);
290  return LP.runOnLoop(L);
291  }
292 };
293 
295 } // end namespace llvm
296 
297 INITIALIZE_PASS_BEGIN(LoopPredicationLegacyPass, "loop-predication",
298  "Loop predication", false, false)
300 INITIALIZE_PASS_END(LoopPredicationLegacyPass, "loop-predication",
301  "Loop predication", false, false)
302 
304  return new LoopPredicationLegacyPass();
305 }
306 
309  LPMUpdater &U) {
310  LoopPredication LP(&AR.SE);
311  if (!LP.runOnLoop(&L))
312  return PreservedAnalyses::all();
313 
315 }
316 
318 LoopPredication::parseLoopICmp(ICmpInst::Predicate Pred, Value *LHS,
319  Value *RHS) {
320  const SCEV *LHSS = SE->getSCEV(LHS);
321  if (isa<SCEVCouldNotCompute>(LHSS))
322  return None;
323  const SCEV *RHSS = SE->getSCEV(RHS);
324  if (isa<SCEVCouldNotCompute>(RHSS))
325  return None;
326 
327  // Canonicalize RHS to be loop invariant bound, LHS - a loop computable IV
328  if (SE->isLoopInvariant(LHSS, L)) {
329  std::swap(LHS, RHS);
330  std::swap(LHSS, RHSS);
331  Pred = ICmpInst::getSwappedPredicate(Pred);
332  }
333 
334  const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(LHSS);
335  if (!AR || AR->getLoop() != L)
336  return None;
337 
338  return LoopICmp(Pred, AR, RHSS);
339 }
340 
341 Value *LoopPredication::expandCheck(SCEVExpander &Expander,
342  IRBuilder<> &Builder,
343  ICmpInst::Predicate Pred, const SCEV *LHS,
344  const SCEV *RHS, Instruction *InsertAt) {
345  // TODO: we can check isLoopEntryGuardedByCond before emitting the check
346 
347  Type *Ty = LHS->getType();
348  assert(Ty == RHS->getType() && "expandCheck operands have different types?");
349 
350  if (SE->isLoopEntryGuardedByCond(L, Pred, LHS, RHS))
351  return Builder.getTrue();
352 
353  Value *LHSV = Expander.expandCodeFor(LHS, Ty, InsertAt);
354  Value *RHSV = Expander.expandCodeFor(RHS, Ty, InsertAt);
355  return Builder.CreateICmp(Pred, LHSV, RHSV);
356 }
357 
359 LoopPredication::generateLoopLatchCheck(Type *RangeCheckType) {
360 
361  auto *LatchType = LatchCheck.IV->getType();
362  if (RangeCheckType == LatchType)
363  return LatchCheck;
364  // For now, bail out if latch type is narrower than range type.
365  if (DL->getTypeSizeInBits(LatchType) < DL->getTypeSizeInBits(RangeCheckType))
366  return None;
367  if (!isSafeToTruncateWideIVType(RangeCheckType))
368  return None;
369  // We can now safely identify the truncated version of the IV and limit for
370  // RangeCheckType.
371  LoopICmp NewLatchCheck;
372  NewLatchCheck.Pred = LatchCheck.Pred;
373  NewLatchCheck.IV = dyn_cast<SCEVAddRecExpr>(
374  SE->getTruncateExpr(LatchCheck.IV, RangeCheckType));
375  if (!NewLatchCheck.IV)
376  return None;
377  NewLatchCheck.Limit = SE->getTruncateExpr(LatchCheck.Limit, RangeCheckType);
378  DEBUG(dbgs() << "IV of type: " << *LatchType
379  << "can be represented as range check type:" << *RangeCheckType
380  << "\n");
381  DEBUG(dbgs() << "LatchCheck.IV: " << *NewLatchCheck.IV << "\n");
382  DEBUG(dbgs() << "LatchCheck.Limit: " << *NewLatchCheck.Limit << "\n");
383  return NewLatchCheck;
384 }
385 
386 bool LoopPredication::isSupportedStep(const SCEV* Step) {
387  return Step->isOne() || (Step->isAllOnesValue() && EnableCountDownLoop);
388 }
389 
390 bool LoopPredication::CanExpand(const SCEV* S) {
391  return SE->isLoopInvariant(S, L) && isSafeToExpand(S, *SE);
392 }
393 
394 Optional<Value *> LoopPredication::widenICmpRangeCheckIncrementingLoop(
395  LoopPredication::LoopICmp LatchCheck, LoopPredication::LoopICmp RangeCheck,
396  SCEVExpander &Expander, IRBuilder<> &Builder) {
397  auto *Ty = RangeCheck.IV->getType();
398  // Generate the widened condition for the forward loop:
399  // guardStart u< guardLimit &&
400  // latchLimit <pred> guardLimit - 1 - guardStart + latchStart
401  // where <pred> depends on the latch condition predicate. See the file
402  // header comment for the reasoning.
403  // guardLimit - guardStart + latchStart - 1
404  const SCEV *GuardStart = RangeCheck.IV->getStart();
405  const SCEV *GuardLimit = RangeCheck.Limit;
406  const SCEV *LatchStart = LatchCheck.IV->getStart();
407  const SCEV *LatchLimit = LatchCheck.Limit;
408 
409  // guardLimit - guardStart + latchStart - 1
410  const SCEV *RHS =
411  SE->getAddExpr(SE->getMinusSCEV(GuardLimit, GuardStart),
412  SE->getMinusSCEV(LatchStart, SE->getOne(Ty)));
413  if (!CanExpand(GuardStart) || !CanExpand(GuardLimit) ||
414  !CanExpand(LatchLimit) || !CanExpand(RHS)) {
415  DEBUG(dbgs() << "Can't expand limit check!\n");
416  return None;
417  }
418  ICmpInst::Predicate LimitCheckPred;
419  switch (LatchCheck.Pred) {
420  case ICmpInst::ICMP_ULT:
421  LimitCheckPred = ICmpInst::ICMP_ULE;
422  break;
423  case ICmpInst::ICMP_ULE:
424  LimitCheckPred = ICmpInst::ICMP_ULT;
425  break;
426  case ICmpInst::ICMP_SLT:
427  LimitCheckPred = ICmpInst::ICMP_SLE;
428  break;
429  case ICmpInst::ICMP_SLE:
430  LimitCheckPred = ICmpInst::ICMP_SLT;
431  break;
432  default:
433  llvm_unreachable("Unsupported loop latch!");
434  }
435 
436  DEBUG(dbgs() << "LHS: " << *LatchLimit << "\n");
437  DEBUG(dbgs() << "RHS: " << *RHS << "\n");
438  DEBUG(dbgs() << "Pred: " << LimitCheckPred << "\n");
439 
440  Instruction *InsertAt = Preheader->getTerminator();
441  auto *LimitCheck =
442  expandCheck(Expander, Builder, LimitCheckPred, LatchLimit, RHS, InsertAt);
443  auto *FirstIterationCheck = expandCheck(Expander, Builder, RangeCheck.Pred,
444  GuardStart, GuardLimit, InsertAt);
445  return Builder.CreateAnd(FirstIterationCheck, LimitCheck);
446 }
447 
448 Optional<Value *> LoopPredication::widenICmpRangeCheckDecrementingLoop(
449  LoopPredication::LoopICmp LatchCheck, LoopPredication::LoopICmp RangeCheck,
450  SCEVExpander &Expander, IRBuilder<> &Builder) {
451  auto *Ty = RangeCheck.IV->getType();
452  const SCEV *GuardStart = RangeCheck.IV->getStart();
453  const SCEV *GuardLimit = RangeCheck.Limit;
454  const SCEV *LatchLimit = LatchCheck.Limit;
455  if (!CanExpand(GuardStart) || !CanExpand(GuardLimit) ||
456  !CanExpand(LatchLimit)) {
457  DEBUG(dbgs() << "Can't expand limit check!\n");
458  return None;
459  }
460  // The decrement of the latch check IV should be the same as the
461  // rangeCheckIV.
462  auto *PostDecLatchCheckIV = LatchCheck.IV->getPostIncExpr(*SE);
463  if (RangeCheck.IV != PostDecLatchCheckIV) {
464  DEBUG(dbgs() << "Not the same. PostDecLatchCheckIV: "
465  << *PostDecLatchCheckIV
466  << " and RangeCheckIV: " << *RangeCheck.IV << "\n");
467  return None;
468  }
469 
470  // Generate the widened condition for CountDownLoop:
471  // guardStart u< guardLimit &&
472  // latchLimit <pred> 1.
473  // See the header comment for reasoning of the checks.
474  Instruction *InsertAt = Preheader->getTerminator();
475  auto LimitCheckPred = ICmpInst::isSigned(LatchCheck.Pred)
478  auto *FirstIterationCheck = expandCheck(Expander, Builder, ICmpInst::ICMP_ULT,
479  GuardStart, GuardLimit, InsertAt);
480  auto *LimitCheck = expandCheck(Expander, Builder, LimitCheckPred, LatchLimit,
481  SE->getOne(Ty), InsertAt);
482  return Builder.CreateAnd(FirstIterationCheck, LimitCheck);
483 }
484 
485 /// If ICI can be widened to a loop invariant condition emits the loop
486 /// invariant condition in the loop preheader and return it, otherwise
487 /// returns None.
488 Optional<Value *> LoopPredication::widenICmpRangeCheck(ICmpInst *ICI,
489  SCEVExpander &Expander,
490  IRBuilder<> &Builder) {
491  DEBUG(dbgs() << "Analyzing ICmpInst condition:\n");
492  DEBUG(ICI->dump());
493 
494  // parseLoopStructure guarantees that the latch condition is:
495  // ++i <pred> latchLimit, where <pred> is u<, u<=, s<, or s<=.
496  // We are looking for the range checks of the form:
497  // i u< guardLimit
498  auto RangeCheck = parseLoopICmp(ICI);
499  if (!RangeCheck) {
500  DEBUG(dbgs() << "Failed to parse the loop latch condition!\n");
501  return None;
502  }
503  DEBUG(dbgs() << "Guard check:\n");
504  DEBUG(RangeCheck->dump());
505  if (RangeCheck->Pred != ICmpInst::ICMP_ULT) {
506  DEBUG(dbgs() << "Unsupported range check predicate(" << RangeCheck->Pred
507  << ")!\n");
508  return None;
509  }
510  auto *RangeCheckIV = RangeCheck->IV;
511  if (!RangeCheckIV->isAffine()) {
512  DEBUG(dbgs() << "Range check IV is not affine!\n");
513  return None;
514  }
515  auto *Step = RangeCheckIV->getStepRecurrence(*SE);
516  // We cannot just compare with latch IV step because the latch and range IVs
517  // may have different types.
518  if (!isSupportedStep(Step)) {
519  DEBUG(dbgs() << "Range check and latch have IVs different steps!\n");
520  return None;
521  }
522  auto *Ty = RangeCheckIV->getType();
523  auto CurrLatchCheckOpt = generateLoopLatchCheck(Ty);
524  if (!CurrLatchCheckOpt) {
525  DEBUG(dbgs() << "Failed to generate a loop latch check "
526  "corresponding to range type: "
527  << *Ty << "\n");
528  return None;
529  }
530 
531  LoopICmp CurrLatchCheck = *CurrLatchCheckOpt;
532  // At this point, the range and latch step should have the same type, but need
533  // not have the same value (we support both 1 and -1 steps).
534  assert(Step->getType() ==
535  CurrLatchCheck.IV->getStepRecurrence(*SE)->getType() &&
536  "Range and latch steps should be of same type!");
537  if (Step != CurrLatchCheck.IV->getStepRecurrence(*SE)) {
538  DEBUG(dbgs() << "Range and latch have different step values!\n");
539  return None;
540  }
541 
542  if (Step->isOne())
543  return widenICmpRangeCheckIncrementingLoop(CurrLatchCheck, *RangeCheck,
544  Expander, Builder);
545  else {
546  assert(Step->isAllOnesValue() && "Step should be -1!");
547  return widenICmpRangeCheckDecrementingLoop(CurrLatchCheck, *RangeCheck,
548  Expander, Builder);
549  }
550 }
551 
552 bool LoopPredication::widenGuardConditions(IntrinsicInst *Guard,
553  SCEVExpander &Expander) {
554  DEBUG(dbgs() << "Processing guard:\n");
555  DEBUG(Guard->dump());
556 
557  IRBuilder<> Builder(cast<Instruction>(Preheader->getTerminator()));
558 
559  // The guard condition is expected to be in form of:
560  // cond1 && cond2 && cond3 ...
561  // Iterate over subconditions looking for for icmp conditions which can be
562  // widened across loop iterations. Widening these conditions remember the
563  // resulting list of subconditions in Checks vector.
564  SmallVector<Value *, 4> Worklist(1, Guard->getOperand(0));
565  SmallPtrSet<Value *, 4> Visited;
566 
568 
569  unsigned NumWidened = 0;
570  do {
571  Value *Condition = Worklist.pop_back_val();
572  if (!Visited.insert(Condition).second)
573  continue;
574 
575  Value *LHS, *RHS;
576  using namespace llvm::PatternMatch;
577  if (match(Condition, m_And(m_Value(LHS), m_Value(RHS)))) {
578  Worklist.push_back(LHS);
579  Worklist.push_back(RHS);
580  continue;
581  }
582 
583  if (ICmpInst *ICI = dyn_cast<ICmpInst>(Condition)) {
584  if (auto NewRangeCheck = widenICmpRangeCheck(ICI, Expander, Builder)) {
585  Checks.push_back(NewRangeCheck.getValue());
586  NumWidened++;
587  continue;
588  }
589  }
590 
591  // Save the condition as is if we can't widen it
592  Checks.push_back(Condition);
593  } while (Worklist.size() != 0);
594 
595  if (NumWidened == 0)
596  return false;
597 
598  // Emit the new guard condition
599  Builder.SetInsertPoint(Guard);
600  Value *LastCheck = nullptr;
601  for (auto *Check : Checks)
602  if (!LastCheck)
603  LastCheck = Check;
604  else
605  LastCheck = Builder.CreateAnd(LastCheck, Check);
606  Guard->setOperand(0, LastCheck);
607 
608  DEBUG(dbgs() << "Widened checks = " << NumWidened << "\n");
609  return true;
610 }
611 
612 Optional<LoopPredication::LoopICmp> LoopPredication::parseLoopLatchICmp() {
613  using namespace PatternMatch;
614 
615  BasicBlock *LoopLatch = L->getLoopLatch();
616  if (!LoopLatch) {
617  DEBUG(dbgs() << "The loop doesn't have a single latch!\n");
618  return None;
619  }
620 
621  ICmpInst::Predicate Pred;
622  Value *LHS, *RHS;
623  BasicBlock *TrueDest, *FalseDest;
624 
625  if (!match(LoopLatch->getTerminator(),
626  m_Br(m_ICmp(Pred, m_Value(LHS), m_Value(RHS)), TrueDest,
627  FalseDest))) {
628  DEBUG(dbgs() << "Failed to match the latch terminator!\n");
629  return None;
630  }
631  assert((TrueDest == L->getHeader() || FalseDest == L->getHeader()) &&
632  "One of the latch's destinations must be the header");
633  if (TrueDest != L->getHeader())
634  Pred = ICmpInst::getInversePredicate(Pred);
635 
636  auto Result = parseLoopICmp(Pred, LHS, RHS);
637  if (!Result) {
638  DEBUG(dbgs() << "Failed to parse the loop latch condition!\n");
639  return None;
640  }
641 
642  // Check affine first, so if it's not we don't try to compute the step
643  // recurrence.
644  if (!Result->IV->isAffine()) {
645  DEBUG(dbgs() << "The induction variable is not affine!\n");
646  return None;
647  }
648 
649  auto *Step = Result->IV->getStepRecurrence(*SE);
650  if (!isSupportedStep(Step)) {
651  DEBUG(dbgs() << "Unsupported loop stride(" << *Step << ")!\n");
652  return None;
653  }
654 
655  auto IsUnsupportedPredicate = [](const SCEV *Step, ICmpInst::Predicate Pred) {
656  if (Step->isOne()) {
657  return Pred != ICmpInst::ICMP_ULT && Pred != ICmpInst::ICMP_SLT &&
658  Pred != ICmpInst::ICMP_ULE && Pred != ICmpInst::ICMP_SLE;
659  } else {
660  assert(Step->isAllOnesValue() && "Step should be -1!");
661  return Pred != ICmpInst::ICMP_UGT && Pred != ICmpInst::ICMP_SGT;
662  }
663  };
664 
665  if (IsUnsupportedPredicate(Step, Result->Pred)) {
666  DEBUG(dbgs() << "Unsupported loop latch predicate(" << Result->Pred
667  << ")!\n");
668  return None;
669  }
670  return Result;
671 }
672 
673 // Returns true if its safe to truncate the IV to RangeCheckType.
674 bool LoopPredication::isSafeToTruncateWideIVType(Type *RangeCheckType) {
675  if (!EnableIVTruncation)
676  return false;
677  assert(DL->getTypeSizeInBits(LatchCheck.IV->getType()) >
678  DL->getTypeSizeInBits(RangeCheckType) &&
679  "Expected latch check IV type to be larger than range check operand "
680  "type!");
681  // The start and end values of the IV should be known. This is to guarantee
682  // that truncating the wide type will not lose information.
683  auto *Limit = dyn_cast<SCEVConstant>(LatchCheck.Limit);
684  auto *Start = dyn_cast<SCEVConstant>(LatchCheck.IV->getStart());
685  if (!Limit || !Start)
686  return false;
687  // This check makes sure that the IV does not change sign during loop
688  // iterations. Consider latchType = i64, LatchStart = 5, Pred = ICMP_SGE,
689  // LatchEnd = 2, rangeCheckType = i32. If it's not a monotonic predicate, the
690  // IV wraps around, and the truncation of the IV would lose the range of
691  // iterations between 2^32 and 2^64.
692  bool Increasing;
693  if (!SE->isMonotonicPredicate(LatchCheck.IV, LatchCheck.Pred, Increasing))
694  return false;
695  // The active bits should be less than the bits in the RangeCheckType. This
696  // guarantees that truncating the latch check to RangeCheckType is a safe
697  // operation.
698  auto RangeCheckTypeBitSize = DL->getTypeSizeInBits(RangeCheckType);
699  return Start->getAPInt().getActiveBits() < RangeCheckTypeBitSize &&
700  Limit->getAPInt().getActiveBits() < RangeCheckTypeBitSize;
701 }
702 
703 bool LoopPredication::runOnLoop(Loop *Loop) {
704  L = Loop;
705 
706  DEBUG(dbgs() << "Analyzing ");
707  DEBUG(L->dump());
708 
709  Module *M = L->getHeader()->getModule();
710 
711  // There is nothing to do if the module doesn't use guards
712  auto *GuardDecl =
713  M->getFunction(Intrinsic::getName(Intrinsic::experimental_guard));
714  if (!GuardDecl || GuardDecl->use_empty())
715  return false;
716 
717  DL = &M->getDataLayout();
718 
719  Preheader = L->getLoopPreheader();
720  if (!Preheader)
721  return false;
722 
723  auto LatchCheckOpt = parseLoopLatchICmp();
724  if (!LatchCheckOpt)
725  return false;
726  LatchCheck = *LatchCheckOpt;
727 
728  DEBUG(dbgs() << "Latch check:\n");
729  DEBUG(LatchCheck.dump());
730 
731  // Collect all the guards into a vector and process later, so as not
732  // to invalidate the instruction iterator.
734  for (const auto BB : L->blocks())
735  for (auto &I : *BB)
736  if (auto *II = dyn_cast<IntrinsicInst>(&I))
737  if (II->getIntrinsicID() == Intrinsic::experimental_guard)
738  Guards.push_back(II);
739 
740  if (Guards.empty())
741  return false;
742 
743  SCEVExpander Expander(*SE, *DL, "loop-predication");
744 
745  bool Changed = false;
746  for (auto *Guard : Guards)
747  Changed |= widenGuardConditions(Guard, Expander);
748 
749  return Changed;
750 }
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:3646
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
bool isSigned() const
Determine if this instruction is using a signed comparison.
Definition: InstrTypes.h:994
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.
signed greater than
Definition: InstrTypes.h:880
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)
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: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
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:530
Predicate getPredicate() const
Return the predicate for this instruction.
Definition: InstrTypes.h:927
This class represents an analyzed expression in the program.
unsigned greater or equal
Definition: InstrTypes.h:877
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:1149
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
unsigned greater than
Definition: InstrTypes.h:876
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
signed greater or equal
Definition: InstrTypes.h:881
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