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>, u>=, s>, or s>=.
 159 //   * The guard condition is of the form
 160 //     G(X) = X - 1 u< guardLimit
 161 //
 162 //   For the ugt latch comparison case M is:
 163 //     forall X. X-1 u< guardLimit and X u> latchLimit => X-2 u< guardLimit
 164 //
 165 //   The only way the antecedent can be true and the consequent can be false is if
 166 //     X == 1.
 167 //   If X == 1 then the second half of the antecedent is
 168 //     1 u> latchLimit, and its negation is latchLimit u>= 1.
 169 //
 170 //   So the widened condition is:
 171 //     guardStart u< guardLimit && latchLimit u>= 1.
 172 //   Similarly for sgt condition the widened condition is:
 173 //     guardStart u< guardLimit && latchLimit s>= 1.
 174 //   For uge condition the widened condition is:
 175 //     guardStart u< guardLimit && latchLimit u> 1.
 176 //   For sge condition the widened condition is:
 177 //     guardStart u< guardLimit && latchLimit s> 1.
 178 //===----------------------------------------------------------------------===//
 179
 180 #include "llvm/Transforms/Scalar/LoopPredication.h"
 181 #include "llvm/Analysis/BranchProbabilityInfo.h"
 182 #include "llvm/Analysis/LoopInfo.h"
 183 #include "llvm/Analysis/LoopPass.h"
 184 #include "llvm/Analysis/ScalarEvolution.h"
 185 #include "llvm/Analysis/ScalarEvolutionExpander.h"
 186 #include "llvm/Analysis/ScalarEvolutionExpressions.h"
 187 #include "llvm/IR/Function.h"
 188 #include "llvm/IR/GlobalValue.h"
 189 #include "llvm/IR/IntrinsicInst.h"
 190 #include "llvm/IR/Module.h"
 191 #include "llvm/IR/PatternMatch.h"
 192 #include "llvm/Pass.h"
 193 #include "llvm/Support/Debug.h"
 194 #include "llvm/Transforms/Scalar.h"
 195 #include "llvm/Transforms/Utils/LoopUtils.h"
 196
 197 #define DEBUG_TYPE "loop-predication"
 198
 199 using namespace llvm;
 200
 201 static cl::opt<bool> EnableIVTruncation("loop-predication-enable-iv-truncation",
 202                                         cl::Hidden, cl::init(true));
 203
 204 static cl::opt<bool> EnableCountDownLoop("loop-predication-enable-count-down-loop",
 205                                         cl::Hidden, cl::init(true));
 206
 207 static cl::opt<bool>
 208     SkipProfitabilityChecks("loop-predication-skip-profitability-checks",
 209                             cl::Hidden, cl::init(false));
 210
 211 // This is the scale factor for the latch probability. We use this during
 212 // profitability analysis to find other exiting blocks that have a much higher
 213 // probability of exiting the loop instead of loop exiting via latch.
 214 // This value should be greater than 1 for a sane profitability check.
 215 static cl::opt<float> LatchExitProbabilityScale(
 216     "loop-predication-latch-probability-scale", cl::Hidden, cl::init(2.0),
 217     cl::desc("scale factor for the latch probability. Value should be greater "
 218              "than 1. Lower values are ignored"));
 219
 220 namespace {
 221 class LoopPredication {
 222   /// Represents an induction variable check:
 223   ///   icmp Pred, <induction variable>, <loop invariant limit>
 224   struct LoopICmp {
 225     ICmpInst::Predicate Pred;
 226     const SCEVAddRecExpr *IV;
 227     const SCEV *Limit;
 228     LoopICmp(ICmpInst::Predicate Pred, const SCEVAddRecExpr *IV,
 229              const SCEV *Limit)
 230         : Pred(Pred), IV(IV), Limit(Limit) {}
 231     LoopICmp() {}
 232     void dump() {
 233       dbgs() << "LoopICmp Pred = " << Pred << ", IV = " << *IV
 234              << ", Limit = " << *Limit << "\n";
 235     }
 236   };
 237
 238   ScalarEvolution *SE;
 239   BranchProbabilityInfo *BPI;
 240
 241   Loop *L;
 242   const DataLayout *DL;
 243   BasicBlock *Preheader;
 244   LoopICmp LatchCheck;
 245
 246   bool isSupportedStep(const SCEV* Step);
 247   Optional<LoopICmp> parseLoopICmp(ICmpInst *ICI) {
 248     return parseLoopICmp(ICI->getPredicate(), ICI->getOperand(0),
 249                          ICI->getOperand(1));
 250   }
 251   Optional<LoopICmp> parseLoopICmp(ICmpInst::Predicate Pred, Value *LHS,
 252                                    Value *RHS);
 253
 254   Optional<LoopICmp> parseLoopLatchICmp();
 255
 256   bool CanExpand(const SCEV* S);
 257   Value *expandCheck(SCEVExpander &Expander, IRBuilder<> &Builder,
 258                      ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS,
 259                      Instruction *InsertAt);
 260
 261   Optional<Value *> widenICmpRangeCheck(ICmpInst *ICI, SCEVExpander &Expander,
 262                                         IRBuilder<> &Builder);
 263   Optional<Value *> widenICmpRangeCheckIncrementingLoop(LoopICmp LatchCheck,
 264                                                         LoopICmp RangeCheck,
 265                                                         SCEVExpander &Expander,
 266                                                         IRBuilder<> &Builder);
 267   Optional<Value *> widenICmpRangeCheckDecrementingLoop(LoopICmp LatchCheck,
 268                                                         LoopICmp RangeCheck,
 269                                                         SCEVExpander &Expander,
 270                                                         IRBuilder<> &Builder);
 271   bool widenGuardConditions(IntrinsicInst *II, SCEVExpander &Expander);
 272
 273   // If the loop always exits through another block in the loop, we should not
 274   // predicate based on the latch check. For example, the latch check can be a
 275   // very coarse grained check and there can be more fine grained exit checks
 276   // within the loop. We identify such unprofitable loops through BPI.
 277   bool isLoopProfitableToPredicate();
 278
 279   // When the IV type is wider than the range operand type, we can still do loop
 280   // predication, by generating SCEVs for the range and latch that are of the
 281   // same type. We achieve this by generating a SCEV truncate expression for the
 282   // latch IV. This is done iff truncation of the IV is a safe operation,
 283   // without loss of information.
 284   // Another way to achieve this is by generating a wider type SCEV for the
 285   // range check operand, however, this needs a more involved check that
 286   // operands do not overflow. This can lead to loss of information when the
 287   // range operand is of the form: add i32 %offset, %iv. We need to prove that
 288   // sext(x + y) is same as sext(x) + sext(y).
 289   // This function returns true if we can safely represent the IV type in
 290   // the RangeCheckType without loss of information.
 291   bool isSafeToTruncateWideIVType(Type *RangeCheckType);
 292   // Return the loopLatchCheck corresponding to the RangeCheckType if safe to do
 293   // so.
 294   Optional<LoopICmp> generateLoopLatchCheck(Type *RangeCheckType);
 295
 296 public:
 297   LoopPredication(ScalarEvolution *SE, BranchProbabilityInfo *BPI)
 298       : SE(SE), BPI(BPI){};
 299   bool runOnLoop(Loop *L);
 300 };
 301
 302 class LoopPredicationLegacyPass : public LoopPass {
 303 public:
 304   static char ID;
 305   LoopPredicationLegacyPass() : LoopPass(ID) {
 306     initializeLoopPredicationLegacyPassPass(*PassRegistry::getPassRegistry());
 307   }
 308
 309   void getAnalysisUsage(AnalysisUsage &AU) const override {
 310     AU.addRequired<BranchProbabilityInfoWrapperPass>();
 311     getLoopAnalysisUsage(AU);
 312   }
 313
 314   bool runOnLoop(Loop *L, LPPassManager &LPM) override {
 315     if (skipLoop(L))
 316       return false;
 317     auto *SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
 318     BranchProbabilityInfo &BPI =
 319         getAnalysis<BranchProbabilityInfoWrapperPass>().getBPI();
 320     LoopPredication LP(SE, &BPI);
 321     return LP.runOnLoop(L);
 322   }
 323 };
 324
 325 char LoopPredicationLegacyPass::ID = 0;
 326 } // end namespace llvm
 327
 328 INITIALIZE_PASS_BEGIN(LoopPredicationLegacyPass, "loop-predication",
 329                       "Loop predication", false, false)
 330 INITIALIZE_PASS_DEPENDENCY(BranchProbabilityInfoWrapperPass)
 331 INITIALIZE_PASS_DEPENDENCY(LoopPass)
 332 INITIALIZE_PASS_END(LoopPredicationLegacyPass, "loop-predication",
 333                     "Loop predication", false, false)
 334
 335 Pass *llvm::createLoopPredicationPass() {
 336   return new LoopPredicationLegacyPass();
 337 }
 338
 339 PreservedAnalyses LoopPredicationPass::run(Loop &L, LoopAnalysisManager &AM,
 340                                            LoopStandardAnalysisResults &AR,
 341                                            LPMUpdater &U) {
 342   const auto &FAM =
 343       AM.getResult<FunctionAnalysisManagerLoopProxy>(L, AR).getManager();
 344   Function *F = L.getHeader()->getParent();
 345   auto *BPI = FAM.getCachedResult<BranchProbabilityAnalysis>(*F);
 346   LoopPredication LP(&AR.SE, BPI);
 347   if (!LP.runOnLoop(&L))
 348     return PreservedAnalyses::all();
 349
 350   return getLoopPassPreservedAnalyses();
 351 }
 352
 353 Optional<LoopPredication::LoopICmp>
 354 LoopPredication::parseLoopICmp(ICmpInst::Predicate Pred, Value *LHS,
 355                                Value *RHS) {
 356   const SCEV *LHSS = SE->getSCEV(LHS);
 357   if (isa<SCEVCouldNotCompute>(LHSS))
 358     return None;
 359   const SCEV *RHSS = SE->getSCEV(RHS);
 360   if (isa<SCEVCouldNotCompute>(RHSS))
 361     return None;
 362
 363   // Canonicalize RHS to be loop invariant bound, LHS - a loop computable IV
 364   if (SE->isLoopInvariant(LHSS, L)) {
 365     std::swap(LHS, RHS);
 366     std::swap(LHSS, RHSS);
 367     Pred = ICmpInst::getSwappedPredicate(Pred);
 368   }
 369
 370   const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(LHSS);
 371   if (!AR || AR->getLoop() != L)
 372     return None;
 373
 374   return LoopICmp(Pred, AR, RHSS);
 375 }
 376
 377 Value *LoopPredication::expandCheck(SCEVExpander &Expander,
 378                                     IRBuilder<> &Builder,
 379                                     ICmpInst::Predicate Pred, const SCEV *LHS,
 380                                     const SCEV *RHS, Instruction *InsertAt) {
 381   // TODO: we can check isLoopEntryGuardedByCond before emitting the check
 382
 383   Type *Ty = LHS->getType();
 384   assert(Ty == RHS->getType() && "expandCheck operands have different types?");
 385
 386   if (SE->isLoopEntryGuardedByCond(L, Pred, LHS, RHS))
 387     return Builder.getTrue();
 388
 389   Value *LHSV = Expander.expandCodeFor(LHS, Ty, InsertAt);
 390   Value *RHSV = Expander.expandCodeFor(RHS, Ty, InsertAt);
 391   return Builder.CreateICmp(Pred, LHSV, RHSV);
 392 }
 393
 394 Optional<LoopPredication::LoopICmp>
 395 LoopPredication::generateLoopLatchCheck(Type *RangeCheckType) {
 396
 397   auto *LatchType = LatchCheck.IV->getType();
 398   if (RangeCheckType == LatchType)
 399     return LatchCheck;
 400   // For now, bail out if latch type is narrower than range type.
 401   if (DL->getTypeSizeInBits(LatchType) < DL->getTypeSizeInBits(RangeCheckType))
 402     return None;
 403   if (!isSafeToTruncateWideIVType(RangeCheckType))
 404     return None;
 405   // We can now safely identify the truncated version of the IV and limit for
 406   // RangeCheckType.
 407   LoopICmp NewLatchCheck;
 408   NewLatchCheck.Pred = LatchCheck.Pred;
 409   NewLatchCheck.IV = dyn_cast<SCEVAddRecExpr>(
 410       SE->getTruncateExpr(LatchCheck.IV, RangeCheckType));
 411   if (!NewLatchCheck.IV)
 412     return None;
 413   NewLatchCheck.Limit = SE->getTruncateExpr(LatchCheck.Limit, RangeCheckType);
 414   LLVM_DEBUG(dbgs() << "IV of type: " << *LatchType
 415                     << "can be represented as range check type:"
 416                     << *RangeCheckType << "\n");
 417   LLVM_DEBUG(dbgs() << "LatchCheck.IV: " << *NewLatchCheck.IV << "\n");
 418   LLVM_DEBUG(dbgs() << "LatchCheck.Limit: " << *NewLatchCheck.Limit << "\n");
 419   return NewLatchCheck;
 420 }
 421
 422 bool LoopPredication::isSupportedStep(const SCEV* Step) {
 423   return Step->isOne() || (Step->isAllOnesValue() && EnableCountDownLoop);
 424 }
 425
 426 bool LoopPredication::CanExpand(const SCEV* S) {
 427   return SE->isLoopInvariant(S, L) && isSafeToExpand(S, *SE);
 428 }
 429
 430 Optional<Value *> LoopPredication::widenICmpRangeCheckIncrementingLoop(
 431     LoopPredication::LoopICmp LatchCheck, LoopPredication::LoopICmp RangeCheck,
 432     SCEVExpander &Expander, IRBuilder<> &Builder) {
 433   auto *Ty = RangeCheck.IV->getType();
 434   // Generate the widened condition for the forward loop:
 435   //   guardStart u< guardLimit &&
 436   //   latchLimit <pred> guardLimit - 1 - guardStart + latchStart
 437   // where <pred> depends on the latch condition predicate. See the file
 438   // header comment for the reasoning.
 439   // guardLimit - guardStart + latchStart - 1
 440   const SCEV *GuardStart = RangeCheck.IV->getStart();
 441   const SCEV *GuardLimit = RangeCheck.Limit;
 442   const SCEV *LatchStart = LatchCheck.IV->getStart();
 443   const SCEV *LatchLimit = LatchCheck.Limit;
 444
 445   // guardLimit - guardStart + latchStart - 1
 446   const SCEV *RHS =
 447       SE->getAddExpr(SE->getMinusSCEV(GuardLimit, GuardStart),
 448                      SE->getMinusSCEV(LatchStart, SE->getOne(Ty)));
 449   if (!CanExpand(GuardStart) || !CanExpand(GuardLimit) ||
 450       !CanExpand(LatchLimit) || !CanExpand(RHS)) {
 451     LLVM_DEBUG(dbgs() << "Can't expand limit check!\n");
 452     return None;
 453   }
 454   auto LimitCheckPred =
 455       ICmpInst::getFlippedStrictnessPredicate(LatchCheck.Pred);
 456
 457   LLVM_DEBUG(dbgs() << "LHS: " << *LatchLimit << "\n");
 458   LLVM_DEBUG(dbgs() << "RHS: " << *RHS << "\n");
 459   LLVM_DEBUG(dbgs() << "Pred: " << LimitCheckPred << "\n");
 460
 461   Instruction *InsertAt = Preheader->getTerminator();
 462   auto *LimitCheck =
 463       expandCheck(Expander, Builder, LimitCheckPred, LatchLimit, RHS, InsertAt);
 464   auto *FirstIterationCheck = expandCheck(Expander, Builder, RangeCheck.Pred,
 465                                           GuardStart, GuardLimit, InsertAt);
 466   return Builder.CreateAnd(FirstIterationCheck, LimitCheck);
 467 }
 468
 469 Optional<Value *> LoopPredication::widenICmpRangeCheckDecrementingLoop(
 470     LoopPredication::LoopICmp LatchCheck, LoopPredication::LoopICmp RangeCheck,
 471     SCEVExpander &Expander, IRBuilder<> &Builder) {
 472   auto *Ty = RangeCheck.IV->getType();
 473   const SCEV *GuardStart = RangeCheck.IV->getStart();
 474   const SCEV *GuardLimit = RangeCheck.Limit;
 475   const SCEV *LatchLimit = LatchCheck.Limit;
 476   if (!CanExpand(GuardStart) || !CanExpand(GuardLimit) ||
 477       !CanExpand(LatchLimit)) {
 478     LLVM_DEBUG(dbgs() << "Can't expand limit check!\n");
 479     return None;
 480   }
 481   // The decrement of the latch check IV should be the same as the
 482   // rangeCheckIV.
 483   auto *PostDecLatchCheckIV = LatchCheck.IV->getPostIncExpr(*SE);
 484   if (RangeCheck.IV != PostDecLatchCheckIV) {
 485     LLVM_DEBUG(dbgs() << "Not the same. PostDecLatchCheckIV: "
 486                       << *PostDecLatchCheckIV
 487                       << "  and RangeCheckIV: " << *RangeCheck.IV << "\n");
 488     return None;
 489   }
 490
 491   // Generate the widened condition for CountDownLoop:
 492   // guardStart u< guardLimit &&
 493   // latchLimit <pred> 1.
 494   // See the header comment for reasoning of the checks.
 495   Instruction *InsertAt = Preheader->getTerminator();
 496   auto LimitCheckPred =
 497       ICmpInst::getFlippedStrictnessPredicate(LatchCheck.Pred);
 498   auto *FirstIterationCheck = expandCheck(Expander, Builder, ICmpInst::ICMP_ULT,
 499                                           GuardStart, GuardLimit, InsertAt);
 500   auto *LimitCheck = expandCheck(Expander, Builder, LimitCheckPred, LatchLimit,
 501                                  SE->getOne(Ty), InsertAt);
 502   return Builder.CreateAnd(FirstIterationCheck, LimitCheck);
 503 }
 504
 505 /// If ICI can be widened to a loop invariant condition emits the loop
 506 /// invariant condition in the loop preheader and return it, otherwise
 507 /// returns None.
 508 Optional<Value *> LoopPredication::widenICmpRangeCheck(ICmpInst *ICI,
 509                                                        SCEVExpander &Expander,
 510                                                        IRBuilder<> &Builder) {
 511   LLVM_DEBUG(dbgs() << "Analyzing ICmpInst condition:\n");
 512   LLVM_DEBUG(ICI->dump());
 513
 514   // parseLoopStructure guarantees that the latch condition is:
 515   //   ++i <pred> latchLimit, where <pred> is u<, u<=, s<, or s<=.
 516   // We are looking for the range checks of the form:
 517   //   i u< guardLimit
 518   auto RangeCheck = parseLoopICmp(ICI);
 519   if (!RangeCheck) {
 520     LLVM_DEBUG(dbgs() << "Failed to parse the loop latch condition!\n");
 521     return None;
 522   }
 523   LLVM_DEBUG(dbgs() << "Guard check:\n");
 524   LLVM_DEBUG(RangeCheck->dump());
 525   if (RangeCheck->Pred != ICmpInst::ICMP_ULT) {
 526     LLVM_DEBUG(dbgs() << "Unsupported range check predicate("
 527                       << RangeCheck->Pred << ")!\n");
 528     return None;
 529   }
 530   auto *RangeCheckIV = RangeCheck->IV;
 531   if (!RangeCheckIV->isAffine()) {
 532     LLVM_DEBUG(dbgs() << "Range check IV is not affine!\n");
 533     return None;
 534   }
 535   auto *Step = RangeCheckIV->getStepRecurrence(*SE);
 536   // We cannot just compare with latch IV step because the latch and range IVs
 537   // may have different types.
 538   if (!isSupportedStep(Step)) {
 539     LLVM_DEBUG(dbgs() << "Range check and latch have IVs different steps!\n");
 540     return None;
 541   }
 542   auto *Ty = RangeCheckIV->getType();
 543   auto CurrLatchCheckOpt = generateLoopLatchCheck(Ty);
 544   if (!CurrLatchCheckOpt) {
 545     LLVM_DEBUG(dbgs() << "Failed to generate a loop latch check "
 546                          "corresponding to range type: "
 547                       << *Ty << "\n");
 548     return None;
 549   }
 550
 551   LoopICmp CurrLatchCheck = *CurrLatchCheckOpt;
 552   // At this point, the range and latch step should have the same type, but need
 553   // not have the same value (we support both 1 and -1 steps).
 554   assert(Step->getType() ==
 555              CurrLatchCheck.IV->getStepRecurrence(*SE)->getType() &&
 556          "Range and latch steps should be of same type!");
 557   if (Step != CurrLatchCheck.IV->getStepRecurrence(*SE)) {
 558     LLVM_DEBUG(dbgs() << "Range and latch have different step values!\n");
 559     return None;
 560   }
 561
 562   if (Step->isOne())
 563     return widenICmpRangeCheckIncrementingLoop(CurrLatchCheck, *RangeCheck,
 564                                                Expander, Builder);
 565   else {
 566     assert(Step->isAllOnesValue() && "Step should be -1!");
 567     return widenICmpRangeCheckDecrementingLoop(CurrLatchCheck, *RangeCheck,
 568                                                Expander, Builder);
 569   }
 570 }
 571
 572 bool LoopPredication::widenGuardConditions(IntrinsicInst *Guard,
 573                                            SCEVExpander &Expander) {
 574   LLVM_DEBUG(dbgs() << "Processing guard:\n");
 575   LLVM_DEBUG(Guard->dump());
 576
 577   IRBuilder<> Builder(cast<Instruction>(Preheader->getTerminator()));
 578
 579   // The guard condition is expected to be in form of:
 580   //   cond1 && cond2 && cond3 ...
 581   // Iterate over subconditions looking for icmp conditions which can be
 582   // widened across loop iterations. Widening these conditions remember the
 583   // resulting list of subconditions in Checks vector.
 584   SmallVector<Value *, 4> Worklist(1, Guard->getOperand(0));
 585   SmallPtrSet<Value *, 4> Visited;
 586
 587   SmallVector<Value *, 4> Checks;
 588
 589   unsigned NumWidened = 0;
 590   do {
 591     Value *Condition = Worklist.pop_back_val();
 592     if (!Visited.insert(Condition).second)
 593       continue;
 594
 595     Value *LHS, *RHS;
 596     using namespace llvm::PatternMatch;
 597     if (match(Condition, m_And(m_Value(LHS), m_Value(RHS)))) {
 598       Worklist.push_back(LHS);
 599       Worklist.push_back(RHS);
 600       continue;
 601     }
 602
 603     if (ICmpInst *ICI = dyn_cast<ICmpInst>(Condition)) {
 604       if (auto NewRangeCheck = widenICmpRangeCheck(ICI, Expander, Builder)) {
 605         Checks.push_back(NewRangeCheck.getValue());
 606         NumWidened++;
 607         continue;
 608       }
 609     }
 610
 611     // Save the condition as is if we can't widen it
 612     Checks.push_back(Condition);
 613   } while (Worklist.size() != 0);
 614
 615   if (NumWidened == 0)
 616     return false;
 617
 618   // Emit the new guard condition
 619   Builder.SetInsertPoint(Guard);
 620   Value *LastCheck = nullptr;
 621   for (auto *Check : Checks)
 622     if (!LastCheck)
 623       LastCheck = Check;
 624     else
 625       LastCheck = Builder.CreateAnd(LastCheck, Check);
 626   Guard->setOperand(0, LastCheck);
 627
 628   LLVM_DEBUG(dbgs() << "Widened checks = " << NumWidened << "\n");
 629   return true;
 630 }
 631
 632 Optional<LoopPredication::LoopICmp> LoopPredication::parseLoopLatchICmp() {
 633   using namespace PatternMatch;
 634
 635   BasicBlock *LoopLatch = L->getLoopLatch();
 636   if (!LoopLatch) {
 637     LLVM_DEBUG(dbgs() << "The loop doesn't have a single latch!\n");
 638     return None;
 639   }
 640
 641   ICmpInst::Predicate Pred;
 642   Value *LHS, *RHS;
 643   BasicBlock *TrueDest, *FalseDest;
 644
 645   if (!match(LoopLatch->getTerminator(),
 646              m_Br(m_ICmp(Pred, m_Value(LHS), m_Value(RHS)), TrueDest,
 647                   FalseDest))) {
 648     LLVM_DEBUG(dbgs() << "Failed to match the latch terminator!\n");
 649     return None;
 650   }
 651   assert((TrueDest == L->getHeader() || FalseDest == L->getHeader()) &&
 652          "One of the latch's destinations must be the header");
 653   if (TrueDest != L->getHeader())
 654     Pred = ICmpInst::getInversePredicate(Pred);
 655
 656   auto Result = parseLoopICmp(Pred, LHS, RHS);
 657   if (!Result) {
 658     LLVM_DEBUG(dbgs() << "Failed to parse the loop latch condition!\n");
 659     return None;
 660   }
 661
 662   // Check affine first, so if it's not we don't try to compute the step
 663   // recurrence.
 664   if (!Result->IV->isAffine()) {
 665     LLVM_DEBUG(dbgs() << "The induction variable is not affine!\n");
 666     return None;
 667   }
 668
 669   auto *Step = Result->IV->getStepRecurrence(*SE);
 670   if (!isSupportedStep(Step)) {
 671     LLVM_DEBUG(dbgs() << "Unsupported loop stride(" << *Step << ")!\n");
 672     return None;
 673   }
 674
 675   auto IsUnsupportedPredicate = [](const SCEV *Step, ICmpInst::Predicate Pred) {
 676     if (Step->isOne()) {
 677       return Pred != ICmpInst::ICMP_ULT && Pred != ICmpInst::ICMP_SLT &&
 678              Pred != ICmpInst::ICMP_ULE && Pred != ICmpInst::ICMP_SLE;
 679     } else {
 680       assert(Step->isAllOnesValue() && "Step should be -1!");
 681       return Pred != ICmpInst::ICMP_UGT && Pred != ICmpInst::ICMP_SGT &&
 682              Pred != ICmpInst::ICMP_UGE && Pred != ICmpInst::ICMP_SGE;
 683     }
 684   };
 685
 686   if (IsUnsupportedPredicate(Step, Result->Pred)) {
 687     LLVM_DEBUG(dbgs() << "Unsupported loop latch predicate(" << Result->Pred
 688                       << ")!\n");
 689     return None;
 690   }
 691   return Result;
 692 }
 693
 694 // Returns true if its safe to truncate the IV to RangeCheckType.
 695 bool LoopPredication::isSafeToTruncateWideIVType(Type *RangeCheckType) {
 696   if (!EnableIVTruncation)
 697     return false;
 698   assert(DL->getTypeSizeInBits(LatchCheck.IV->getType()) >
 699              DL->getTypeSizeInBits(RangeCheckType) &&
 700          "Expected latch check IV type to be larger than range check operand "
 701          "type!");
 702   // The start and end values of the IV should be known. This is to guarantee
 703   // that truncating the wide type will not lose information.
 704   auto *Limit = dyn_cast<SCEVConstant>(LatchCheck.Limit);
 705   auto *Start = dyn_cast<SCEVConstant>(LatchCheck.IV->getStart());
 706   if (!Limit || !Start)
 707     return false;
 708   // This check makes sure that the IV does not change sign during loop
 709   // iterations. Consider latchType = i64, LatchStart = 5, Pred = ICMP_SGE,
 710   // LatchEnd = 2, rangeCheckType = i32. If it's not a monotonic predicate, the
 711   // IV wraps around, and the truncation of the IV would lose the range of
 712   // iterations between 2^32 and 2^64.
 713   bool Increasing;
 714   if (!SE->isMonotonicPredicate(LatchCheck.IV, LatchCheck.Pred, Increasing))
 715     return false;
 716   // The active bits should be less than the bits in the RangeCheckType. This
 717   // guarantees that truncating the latch check to RangeCheckType is a safe
 718   // operation.
 719   auto RangeCheckTypeBitSize = DL->getTypeSizeInBits(RangeCheckType);
 720   return Start->getAPInt().getActiveBits() < RangeCheckTypeBitSize &&
 721          Limit->getAPInt().getActiveBits() < RangeCheckTypeBitSize;
 722 }
 723
 724 bool LoopPredication::isLoopProfitableToPredicate() {
 725   if (SkipProfitabilityChecks || !BPI)
 726     return true;
 727
 728   SmallVector<std::pair<const BasicBlock *, const BasicBlock *>, 8> ExitEdges;
 729   L->getExitEdges(ExitEdges);
 730   // If there is only one exiting edge in the loop, it is always profitable to
 731   // predicate the loop.
 732   if (ExitEdges.size() == 1)
 733     return true;
 734
 735   // Calculate the exiting probabilities of all exiting edges from the loop,
 736   // starting with the LatchExitProbability.
 737   // Heuristic for profitability: If any of the exiting blocks' probability of
 738   // exiting the loop is larger than exiting through the latch block, it's not
 739   // profitable to predicate the loop.
 740   auto *LatchBlock = L->getLoopLatch();
 741   assert(LatchBlock && "Should have a single latch at this point!");
 742   auto *LatchTerm = LatchBlock->getTerminator();
 743   assert(LatchTerm->getNumSuccessors() == 2 &&
 744          "expected to be an exiting block with 2 succs!");
 745   unsigned LatchBrExitIdx =
 746       LatchTerm->getSuccessor(0) == L->getHeader() ? 1 : 0;
 747   BranchProbability LatchExitProbability =
 748       BPI->getEdgeProbability(LatchBlock, LatchBrExitIdx);
 749
 750   // Protect against degenerate inputs provided by the user. Providing a value
 751   // less than one, can invert the definition of profitable loop predication.
 752   float ScaleFactor = LatchExitProbabilityScale;
 753   if (ScaleFactor < 1) {
 754     LLVM_DEBUG(
 755         dbgs()
 756         << "Ignored user setting for loop-predication-latch-probability-scale: "
 757         << LatchExitProbabilityScale << "\n");
 758     LLVM_DEBUG(dbgs() << "The value is set to 1.0\n");
 759     ScaleFactor = 1.0;
 760   }
 761   const auto LatchProbabilityThreshold =
 762       LatchExitProbability * ScaleFactor;
 763
 764   for (const auto &ExitEdge : ExitEdges) {
 765     BranchProbability ExitingBlockProbability =
 766         BPI->getEdgeProbability(ExitEdge.first, ExitEdge.second);
 767     // Some exiting edge has higher probability than the latch exiting edge.
 768     // No longer profitable to predicate.
 769     if (ExitingBlockProbability > LatchProbabilityThreshold)
 770       return false;
 771   }
 772   // Using BPI, we have concluded that the most probable way to exit from the
 773   // loop is through the latch (or there's no profile information and all
 774   // exits are equally likely).
 775   return true;
 776 }
 777
 778 bool LoopPredication::runOnLoop(Loop *Loop) {
 779   L = Loop;
 780
 781   LLVM_DEBUG(dbgs() << "Analyzing ");
 782   LLVM_DEBUG(L->dump());
 783
 784   Module *M = L->getHeader()->getModule();
 785
 786   // There is nothing to do if the module doesn't use guards
 787   auto *GuardDecl =
 788       M->getFunction(Intrinsic::getName(Intrinsic::experimental_guard));
 789   if (!GuardDecl || GuardDecl->use_empty())
 790     return false;
 791
 792   DL = &M->getDataLayout();
 793
 794   Preheader = L->getLoopPreheader();
 795   if (!Preheader)
 796     return false;
 797
 798   auto LatchCheckOpt = parseLoopLatchICmp();
 799   if (!LatchCheckOpt)
 800     return false;
 801   LatchCheck = *LatchCheckOpt;
 802
 803   LLVM_DEBUG(dbgs() << "Latch check:\n");
 804   LLVM_DEBUG(LatchCheck.dump());
 805
 806   if (!isLoopProfitableToPredicate()) {
 807     LLVM_DEBUG(dbgs() << "Loop not profitable to predicate!\n");
 808     return false;
 809   }
 810   // Collect all the guards into a vector and process later, so as not
 811   // to invalidate the instruction iterator.
 812   SmallVector<IntrinsicInst *, 4> Guards;
 813   for (const auto BB : L->blocks())
 814     for (auto &I : *BB)
 815       if (auto *II = dyn_cast<IntrinsicInst>(&I))
 816         if (II->getIntrinsicID() == Intrinsic::experimental_guard)
 817           Guards.push_back(II);
 818
 819   if (Guards.empty())
 820     return false;
 821
 822   SCEVExpander Expander(*SE, *DL, "loop-predication");
 823
 824   bool Changed = false;
 825   for (auto *Guard : Guards)
 826     Changed |= widenGuardConditions(Guard, Expander);
 827
 828   return Changed;
 829 }