contrib/llvm/lib/Transforms/Scalar/LoopPredication.cpp

   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
 176 #include "llvm/Transforms/Scalar/LoopPredication.h"
 177 #include "llvm/Analysis/LoopInfo.h"
 178 #include "llvm/Analysis/LoopPass.h"
 179 #include "llvm/Analysis/ScalarEvolution.h"
 180 #include "llvm/Analysis/ScalarEvolutionExpander.h"
 181 #include "llvm/Analysis/ScalarEvolutionExpressions.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"
 190 #include "llvm/Transforms/Utils/LoopUtils.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) {
 278     initializeLoopPredicationLegacyPassPass(*PassRegistry::getPassRegistry());
 279   }
 280
 281   void getAnalysisUsage(AnalysisUsage &AU) const override {
 282     getLoopAnalysisUsage(AU);
 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
 294 char LoopPredicationLegacyPass::ID = 0;
 295 } // end namespace llvm
 296
 297 INITIALIZE_PASS_BEGIN(LoopPredicationLegacyPass, "loop-predication",
 298                       "Loop predication", false, false)
 299 INITIALIZE_PASS_DEPENDENCY(LoopPass)
 300 INITIALIZE_PASS_END(LoopPredicationLegacyPass, "loop-predication",
 301                     "Loop predication", false, false)
 302
 303 Pass *llvm::createLoopPredicationPass() {
 304   return new LoopPredicationLegacyPass();
 305 }
 306
 307 PreservedAnalyses LoopPredicationPass::run(Loop &L, LoopAnalysisManager &AM,
 308                                            LoopStandardAnalysisResults &AR,
 309                                            LPMUpdater &U) {
 310   LoopPredication LP(&AR.SE);
 311   if (!LP.runOnLoop(&L))
 312     return PreservedAnalyses::all();
 313
 314   return getLoopPassPreservedAnalyses();
 315 }
 316
 317 Optional<LoopPredication::LoopICmp>
 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
 358 Optional<LoopPredication::LoopICmp>
 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)
 476                             ? ICmpInst::ICMP_SGE
 477                             : ICmpInst::ICMP_UGE;
 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
 567   SmallVector<Value *, 4> Checks;
 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.
 733   SmallVector<IntrinsicInst *, 4> Guards;
 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 }