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

   1 //===- GuardWidening.cpp - ---- Guard widening ----------------------------===//
   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 // This file implements the guard widening pass.  The semantics of the
  11 // @llvm.experimental.guard intrinsic lets LLVM transform it so that it fails
  12 // more often that it did before the transform.  This optimization is called
  13 // "widening" and can be used hoist and common runtime checks in situations like
  14 // these:
  15 //
  16 //    %cmp0 = 7 u< Length
  17 //    call @llvm.experimental.guard(i1 %cmp0) [ "deopt"(...) ]
  18 //    call @unknown_side_effects()
  19 //    %cmp1 = 9 u< Length
  20 //    call @llvm.experimental.guard(i1 %cmp1) [ "deopt"(...) ]
  21 //    ...
  22 //
  23 // =>
  24 //
  25 //    %cmp0 = 9 u< Length
  26 //    call @llvm.experimental.guard(i1 %cmp0) [ "deopt"(...) ]
  27 //    call @unknown_side_effects()
  28 //    ...
  29 //
  30 // If %cmp0 is false, @llvm.experimental.guard will "deoptimize" back to a
  31 // generic implementation of the same function, which will have the correct
  32 // semantics from that point onward.  It is always _legal_ to deoptimize (so
  33 // replacing %cmp0 with false is "correct"), though it may not always be
  34 // profitable to do so.
  35 //
  36 // NB! This pass is a work in progress.  It hasn't been tuned to be "production
  37 // ready" yet.  It is known to have quadriatic running time and will not scale
  38 // to large numbers of guards
  39 //
  40 //===----------------------------------------------------------------------===//
  41
  42 #include "llvm/Transforms/Scalar/GuardWidening.h"
  43 #include <functional>
  44 #include "llvm/ADT/DenseMap.h"
  45 #include "llvm/ADT/DepthFirstIterator.h"
  46 #include "llvm/ADT/Statistic.h"
  47 #include "llvm/Analysis/LoopInfo.h"
  48 #include "llvm/Analysis/LoopPass.h"
  49 #include "llvm/Analysis/PostDominators.h"
  50 #include "llvm/Analysis/ValueTracking.h"
  51 #include "llvm/IR/ConstantRange.h"
  52 #include "llvm/IR/Dominators.h"
  53 #include "llvm/IR/IntrinsicInst.h"
  54 #include "llvm/IR/PatternMatch.h"
  55 #include "llvm/Pass.h"
  56 #include "llvm/Support/Debug.h"
  57 #include "llvm/Support/KnownBits.h"
  58 #include "llvm/Transforms/Scalar.h"
  59 #include "llvm/Transforms/Utils/LoopUtils.h"
  60
  61 using namespace llvm;
  62
  63 #define DEBUG_TYPE "guard-widening"
  64
  65 STATISTIC(GuardsEliminated, "Number of eliminated guards");
  66
  67 namespace {
  68
  69 class GuardWideningImpl {
  70   DominatorTree &DT;
  71   PostDominatorTree *PDT;
  72   LoopInfo &LI;
  73
  74   /// Together, these describe the region of interest.  This might be all of
  75   /// the blocks within a function, or only a given loop's blocks and preheader.
  76   DomTreeNode *Root;
  77   std::function<bool(BasicBlock*)> BlockFilter;
  78
  79   /// The set of guards whose conditions have been widened into dominating
  80   /// guards.
  81   SmallVector<Instruction *, 16> EliminatedGuards;
  82
  83   /// The set of guards which have been widened to include conditions to other
  84   /// guards.
  85   DenseSet<Instruction *> WidenedGuards;
  86
  87   /// Try to eliminate guard \p Guard by widening it into an earlier dominating
  88   /// guard.  \p DFSI is the DFS iterator on the dominator tree that is
  89   /// currently visiting the block containing \p Guard, and \p GuardsPerBlock
  90   /// maps BasicBlocks to the set of guards seen in that block.
  91   bool eliminateGuardViaWidening(
  92       Instruction *Guard, const df_iterator<DomTreeNode *> &DFSI,
  93       const DenseMap<BasicBlock *, SmallVector<Instruction *, 8>> &
  94           GuardsPerBlock);
  95
  96   // Get the condition from \p GuardInst.
  97   Value *getGuardCondition(Instruction *GuardInst);
  98
  99   // Set the condition for \p GuardInst.
 100   void setGuardCondition(Instruction *GuardInst, Value *NewCond);
 101
 102   // Whether or not the particular instruction is a guard.
 103   bool isGuard(const Instruction *I);
 104
 105   // Eliminates the guard instruction properly.
 106   void eliminateGuard(Instruction *GuardInst);
 107
 108   /// Used to keep track of which widening potential is more effective.
 109   enum WideningScore {
 110     /// Don't widen.
 111     WS_IllegalOrNegative,
 112
 113     /// Widening is performance neutral as far as the cycles spent in check
 114     /// conditions goes (but can still help, e.g., code layout, having less
 115     /// deopt state).
 116     WS_Neutral,
 117
 118     /// Widening is profitable.
 119     WS_Positive,
 120
 121     /// Widening is very profitable.  Not significantly different from \c
 122     /// WS_Positive, except by the order.
 123     WS_VeryPositive
 124   };
 125
 126   static StringRef scoreTypeToString(WideningScore WS);
 127
 128   /// Compute the score for widening the condition in \p DominatedGuard
 129   /// (contained in \p DominatedGuardLoop) into \p DominatingGuard (contained in
 130   /// \p DominatingGuardLoop).
 131   WideningScore computeWideningScore(Instruction *DominatedGuard,
 132                                      Loop *DominatedGuardLoop,
 133                                      Instruction *DominatingGuard,
 134                                      Loop *DominatingGuardLoop);
 135
 136   /// Helper to check if \p V can be hoisted to \p InsertPos.
 137   bool isAvailableAt(Value *V, Instruction *InsertPos) {
 138     SmallPtrSet<Instruction *, 8> Visited;
 139     return isAvailableAt(V, InsertPos, Visited);
 140   }
 141
 142   bool isAvailableAt(Value *V, Instruction *InsertPos,
 143                      SmallPtrSetImpl<Instruction *> &Visited);
 144
 145   /// Helper to hoist \p V to \p InsertPos.  Guaranteed to succeed if \c
 146   /// isAvailableAt returned true.
 147   void makeAvailableAt(Value *V, Instruction *InsertPos);
 148
 149   /// Common helper used by \c widenGuard and \c isWideningCondProfitable.  Try
 150   /// to generate an expression computing the logical AND of \p Cond0 and \p
 151   /// Cond1.  Return true if the expression computing the AND is only as
 152   /// expensive as computing one of the two. If \p InsertPt is true then
 153   /// actually generate the resulting expression, make it available at \p
 154   /// InsertPt and return it in \p Result (else no change to the IR is made).
 155   bool widenCondCommon(Value *Cond0, Value *Cond1, Instruction *InsertPt,
 156                        Value *&Result);
 157
 158   /// Represents a range check of the form \c Base + \c Offset u< \c Length,
 159   /// with the constraint that \c Length is not negative.  \c CheckInst is the
 160   /// pre-existing instruction in the IR that computes the result of this range
 161   /// check.
 162   class RangeCheck {
 163     Value *Base;
 164     ConstantInt *Offset;
 165     Value *Length;
 166     ICmpInst *CheckInst;
 167
 168   public:
 169     explicit RangeCheck(Value *Base, ConstantInt *Offset, Value *Length,
 170                         ICmpInst *CheckInst)
 171         : Base(Base), Offset(Offset), Length(Length), CheckInst(CheckInst) {}
 172
 173     void setBase(Value *NewBase) { Base = NewBase; }
 174     void setOffset(ConstantInt *NewOffset) { Offset = NewOffset; }
 175
 176     Value *getBase() const { return Base; }
 177     ConstantInt *getOffset() const { return Offset; }
 178     const APInt &getOffsetValue() const { return getOffset()->getValue(); }
 179     Value *getLength() const { return Length; };
 180     ICmpInst *getCheckInst() const { return CheckInst; }
 181
 182     void print(raw_ostream &OS, bool PrintTypes = false) {
 183       OS << "Base: ";
 184       Base->printAsOperand(OS, PrintTypes);
 185       OS << " Offset: ";
 186       Offset->printAsOperand(OS, PrintTypes);
 187       OS << " Length: ";
 188       Length->printAsOperand(OS, PrintTypes);
 189     }
 190
 191     LLVM_DUMP_METHOD void dump() {
 192       print(dbgs());
 193       dbgs() << "\n";
 194     }
 195   };
 196
 197   /// Parse \p CheckCond into a conjunction (logical-and) of range checks; and
 198   /// append them to \p Checks.  Returns true on success, may clobber \c Checks
 199   /// on failure.
 200   bool parseRangeChecks(Value *CheckCond, SmallVectorImpl<RangeCheck> &Checks) {
 201     SmallPtrSet<Value *, 8> Visited;
 202     return parseRangeChecks(CheckCond, Checks, Visited);
 203   }
 204
 205   bool parseRangeChecks(Value *CheckCond, SmallVectorImpl<RangeCheck> &Checks,
 206                         SmallPtrSetImpl<Value *> &Visited);
 207
 208   /// Combine the checks in \p Checks into a smaller set of checks and append
 209   /// them into \p CombinedChecks.  Return true on success (i.e. all of checks
 210   /// in \p Checks were combined into \p CombinedChecks).  Clobbers \p Checks
 211   /// and \p CombinedChecks on success and on failure.
 212   bool combineRangeChecks(SmallVectorImpl<RangeCheck> &Checks,
 213                           SmallVectorImpl<RangeCheck> &CombinedChecks);
 214
 215   /// Can we compute the logical AND of \p Cond0 and \p Cond1 for the price of
 216   /// computing only one of the two expressions?
 217   bool isWideningCondProfitable(Value *Cond0, Value *Cond1) {
 218     Value *ResultUnused;
 219     return widenCondCommon(Cond0, Cond1, /*InsertPt=*/nullptr, ResultUnused);
 220   }
 221
 222   /// Widen \p ToWiden to fail if \p NewCondition is false (in addition to
 223   /// whatever it is already checking).
 224   void widenGuard(Instruction *ToWiden, Value *NewCondition) {
 225     Value *Result;
 226     widenCondCommon(ToWiden->getOperand(0), NewCondition, ToWiden, Result);
 227     setGuardCondition(ToWiden, Result);
 228   }
 229
 230 public:
 231
 232   explicit GuardWideningImpl(DominatorTree &DT, PostDominatorTree *PDT,
 233                              LoopInfo &LI, DomTreeNode *Root,
 234                              std::function<bool(BasicBlock*)> BlockFilter)
 235     : DT(DT), PDT(PDT), LI(LI), Root(Root), BlockFilter(BlockFilter) {}
 236
 237   /// The entry point for this pass.
 238   bool run();
 239 };
 240 }
 241
 242 bool GuardWideningImpl::run() {
 243   DenseMap<BasicBlock *, SmallVector<Instruction *, 8>> GuardsInBlock;
 244   bool Changed = false;
 245
 246   for (auto DFI = df_begin(Root), DFE = df_end(Root);
 247        DFI != DFE; ++DFI) {
 248     auto *BB = (*DFI)->getBlock();
 249     if (!BlockFilter(BB))
 250       continue;
 251
 252     auto &CurrentList = GuardsInBlock[BB];
 253
 254     for (auto &I : *BB)
 255       if (isGuard(&I))
 256         CurrentList.push_back(cast<Instruction>(&I));
 257
 258     for (auto *II : CurrentList)
 259       Changed |= eliminateGuardViaWidening(II, DFI, GuardsInBlock);
 260   }
 261
 262   assert(EliminatedGuards.empty() || Changed);
 263   for (auto *II : EliminatedGuards)
 264     if (!WidenedGuards.count(II))
 265       eliminateGuard(II);
 266
 267   return Changed;
 268 }
 269
 270 bool GuardWideningImpl::eliminateGuardViaWidening(
 271     Instruction *GuardInst, const df_iterator<DomTreeNode *> &DFSI,
 272     const DenseMap<BasicBlock *, SmallVector<Instruction *, 8>> &
 273         GuardsInBlock) {
 274   Instruction *BestSoFar = nullptr;
 275   auto BestScoreSoFar = WS_IllegalOrNegative;
 276   auto *GuardInstLoop = LI.getLoopFor(GuardInst->getParent());
 277
 278   // In the set of dominating guards, find the one we can merge GuardInst with
 279   // for the most profit.
 280   for (unsigned i = 0, e = DFSI.getPathLength(); i != e; ++i) {
 281     auto *CurBB = DFSI.getPath(i)->getBlock();
 282     if (!BlockFilter(CurBB))
 283       break;
 284     auto *CurLoop = LI.getLoopFor(CurBB);
 285     assert(GuardsInBlock.count(CurBB) && "Must have been populated by now!");
 286     const auto &GuardsInCurBB = GuardsInBlock.find(CurBB)->second;
 287
 288     auto I = GuardsInCurBB.begin();
 289     auto E = GuardsInCurBB.end();
 290
 291 #ifndef NDEBUG
 292     {
 293       unsigned Index = 0;
 294       for (auto &I : *CurBB) {
 295         if (Index == GuardsInCurBB.size())
 296           break;
 297         if (GuardsInCurBB[Index] == &I)
 298           Index++;
 299       }
 300       assert(Index == GuardsInCurBB.size() &&
 301              "Guards expected to be in order!");
 302     }
 303 #endif
 304
 305     assert((i == (e - 1)) == (GuardInst->getParent() == CurBB) && "Bad DFS?");
 306
 307     if (i == (e - 1)) {
 308       // Corner case: make sure we're only looking at guards strictly dominating
 309       // GuardInst when visiting GuardInst->getParent().
 310       auto NewEnd = std::find(I, E, GuardInst);
 311       assert(NewEnd != E && "GuardInst not in its own block?");
 312       E = NewEnd;
 313     }
 314
 315     for (auto *Candidate : make_range(I, E)) {
 316       auto Score =
 317           computeWideningScore(GuardInst, GuardInstLoop, Candidate, CurLoop);
 318       LLVM_DEBUG(dbgs() << "Score between " << *getGuardCondition(GuardInst)
 319                         << " and " << *getGuardCondition(Candidate) << " is "
 320                         << scoreTypeToString(Score) << "\n");
 321       if (Score > BestScoreSoFar) {
 322         BestScoreSoFar = Score;
 323         BestSoFar = Candidate;
 324       }
 325     }
 326   }
 327
 328   if (BestScoreSoFar == WS_IllegalOrNegative) {
 329     LLVM_DEBUG(dbgs() << "Did not eliminate guard " << *GuardInst << "\n");
 330     return false;
 331   }
 332
 333   assert(BestSoFar != GuardInst && "Should have never visited same guard!");
 334   assert(DT.dominates(BestSoFar, GuardInst) && "Should be!");
 335
 336   LLVM_DEBUG(dbgs() << "Widening " << *GuardInst << " into " << *BestSoFar
 337                     << " with score " << scoreTypeToString(BestScoreSoFar)
 338                     << "\n");
 339   widenGuard(BestSoFar, getGuardCondition(GuardInst));
 340   setGuardCondition(GuardInst, ConstantInt::getTrue(GuardInst->getContext()));
 341   EliminatedGuards.push_back(GuardInst);
 342   WidenedGuards.insert(BestSoFar);
 343   return true;
 344 }
 345
 346 Value *GuardWideningImpl::getGuardCondition(Instruction *GuardInst) {
 347   IntrinsicInst *GI = cast<IntrinsicInst>(GuardInst);
 348   assert(GI->getIntrinsicID() == Intrinsic::experimental_guard &&
 349          "Bad guard intrinsic?");
 350   return GI->getArgOperand(0);
 351 }
 352
 353 void GuardWideningImpl::setGuardCondition(Instruction *GuardInst,
 354                                           Value *NewCond) {
 355   IntrinsicInst *GI = cast<IntrinsicInst>(GuardInst);
 356   assert(GI->getIntrinsicID() == Intrinsic::experimental_guard &&
 357          "Bad guard intrinsic?");
 358   GI->setArgOperand(0, NewCond);
 359 }
 360
 361 bool GuardWideningImpl::isGuard(const Instruction* I) {
 362   using namespace llvm::PatternMatch;
 363   return match(I, m_Intrinsic<Intrinsic::experimental_guard>());
 364 }
 365
 366 void GuardWideningImpl::eliminateGuard(Instruction *GuardInst) {
 367   GuardInst->eraseFromParent();
 368   ++GuardsEliminated;
 369 }
 370
 371 GuardWideningImpl::WideningScore GuardWideningImpl::computeWideningScore(
 372     Instruction *DominatedGuard, Loop *DominatedGuardLoop,
 373     Instruction *DominatingGuard, Loop *DominatingGuardLoop) {
 374   bool HoistingOutOfLoop = false;
 375
 376   if (DominatingGuardLoop != DominatedGuardLoop) {
 377     // Be conservative and don't widen into a sibling loop.  TODO: If the
 378     // sibling is colder, we should consider allowing this.
 379     if (DominatingGuardLoop &&
 380         !DominatingGuardLoop->contains(DominatedGuardLoop))
 381       return WS_IllegalOrNegative;
 382
 383     HoistingOutOfLoop = true;
 384   }
 385
 386   if (!isAvailableAt(getGuardCondition(DominatedGuard), DominatingGuard))
 387     return WS_IllegalOrNegative;
 388
 389   // If the guard was conditional executed, it may never be reached
 390   // dynamically.  There are two potential downsides to hoisting it out of the
 391   // conditionally executed region: 1) we may spuriously deopt without need and
 392   // 2) we have the extra cost of computing the guard condition in the common
 393   // case.  At the moment, we really only consider the second in our heuristic
 394   // here.  TODO: evaluate cost model for spurious deopt
 395   // NOTE: As written, this also lets us hoist right over another guard which
 396   // is essentially just another spelling for control flow.
 397   if (isWideningCondProfitable(getGuardCondition(DominatedGuard),
 398                                getGuardCondition(DominatingGuard)))
 399     return HoistingOutOfLoop ? WS_VeryPositive : WS_Positive;
 400
 401   if (HoistingOutOfLoop)
 402     return WS_Positive;
 403
 404   // Returns true if we might be hoisting above explicit control flow.  Note
 405   // that this completely ignores implicit control flow (guards, calls which
 406   // throw, etc...).  That choice appears arbitrary.
 407   auto MaybeHoistingOutOfIf = [&]() {
 408     auto *DominatingBlock = DominatingGuard->getParent();
 409     auto *DominatedBlock = DominatedGuard->getParent();
 410
 411     // Same Block?
 412     if (DominatedBlock == DominatingBlock)
 413       return false;
 414     // Obvious successor (common loop header/preheader case)
 415     if (DominatedBlock == DominatingBlock->getUniqueSuccessor())
 416       return false;
 417     // TODO: diamond, triangle cases
 418     if (!PDT) return true;
 419     return !PDT->dominates(DominatedGuard->getParent(),
 420                            DominatingGuard->getParent());
 421   };
 422
 423   return MaybeHoistingOutOfIf() ? WS_IllegalOrNegative : WS_Neutral;
 424 }
 425
 426 bool GuardWideningImpl::isAvailableAt(Value *V, Instruction *Loc,
 427                                       SmallPtrSetImpl<Instruction *> &Visited) {
 428   auto *Inst = dyn_cast<Instruction>(V);
 429   if (!Inst || DT.dominates(Inst, Loc) || Visited.count(Inst))
 430     return true;
 431
 432   if (!isSafeToSpeculativelyExecute(Inst, Loc, &DT) ||
 433       Inst->mayReadFromMemory())
 434     return false;
 435
 436   Visited.insert(Inst);
 437
 438   // We only want to go _up_ the dominance chain when recursing.
 439   assert(!isa<PHINode>(Loc) &&
 440          "PHIs should return false for isSafeToSpeculativelyExecute");
 441   assert(DT.isReachableFromEntry(Inst->getParent()) &&
 442          "We did a DFS from the block entry!");
 443   return all_of(Inst->operands(),
 444                 [&](Value *Op) { return isAvailableAt(Op, Loc, Visited); });
 445 }
 446
 447 void GuardWideningImpl::makeAvailableAt(Value *V, Instruction *Loc) {
 448   auto *Inst = dyn_cast<Instruction>(V);
 449   if (!Inst || DT.dominates(Inst, Loc))
 450     return;
 451
 452   assert(isSafeToSpeculativelyExecute(Inst, Loc, &DT) &&
 453          !Inst->mayReadFromMemory() && "Should've checked with isAvailableAt!");
 454
 455   for (Value *Op : Inst->operands())
 456     makeAvailableAt(Op, Loc);
 457
 458   Inst->moveBefore(Loc);
 459 }
 460
 461 bool GuardWideningImpl::widenCondCommon(Value *Cond0, Value *Cond1,
 462                                         Instruction *InsertPt, Value *&Result) {
 463   using namespace llvm::PatternMatch;
 464
 465   {
 466     // L >u C0 && L >u C1  ->  L >u max(C0, C1)
 467     ConstantInt *RHS0, *RHS1;
 468     Value *LHS;
 469     ICmpInst::Predicate Pred0, Pred1;
 470     if (match(Cond0, m_ICmp(Pred0, m_Value(LHS), m_ConstantInt(RHS0))) &&
 471         match(Cond1, m_ICmp(Pred1, m_Specific(LHS), m_ConstantInt(RHS1)))) {
 472
 473       ConstantRange CR0 =
 474           ConstantRange::makeExactICmpRegion(Pred0, RHS0->getValue());
 475       ConstantRange CR1 =
 476           ConstantRange::makeExactICmpRegion(Pred1, RHS1->getValue());
 477
 478       // SubsetIntersect is a subset of the actual mathematical intersection of
 479       // CR0 and CR1, while SupersetIntersect is a superset of the actual
 480       // mathematical intersection.  If these two ConstantRanges are equal, then
 481       // we know we were able to represent the actual mathematical intersection
 482       // of CR0 and CR1, and can use the same to generate an icmp instruction.
 483       //
 484       // Given what we're doing here and the semantics of guards, it would
 485       // actually be correct to just use SubsetIntersect, but that may be too
 486       // aggressive in cases we care about.
 487       auto SubsetIntersect = CR0.inverse().unionWith(CR1.inverse()).inverse();
 488       auto SupersetIntersect = CR0.intersectWith(CR1);
 489
 490       APInt NewRHSAP;
 491       CmpInst::Predicate Pred;
 492       if (SubsetIntersect == SupersetIntersect &&
 493           SubsetIntersect.getEquivalentICmp(Pred, NewRHSAP)) {
 494         if (InsertPt) {
 495           ConstantInt *NewRHS = ConstantInt::get(Cond0->getContext(), NewRHSAP);
 496           Result = new ICmpInst(InsertPt, Pred, LHS, NewRHS, "wide.chk");
 497         }
 498         return true;
 499       }
 500     }
 501   }
 502
 503   {
 504     SmallVector<GuardWideningImpl::RangeCheck, 4> Checks, CombinedChecks;
 505     if (parseRangeChecks(Cond0, Checks) && parseRangeChecks(Cond1, Checks) &&
 506         combineRangeChecks(Checks, CombinedChecks)) {
 507       if (InsertPt) {
 508         Result = nullptr;
 509         for (auto &RC : CombinedChecks) {
 510           makeAvailableAt(RC.getCheckInst(), InsertPt);
 511           if (Result)
 512             Result = BinaryOperator::CreateAnd(RC.getCheckInst(), Result, "",
 513                                                InsertPt);
 514           else
 515             Result = RC.getCheckInst();
 516         }
 517
 518         Result->setName("wide.chk");
 519       }
 520       return true;
 521     }
 522   }
 523
 524   // Base case -- just logical-and the two conditions together.
 525
 526   if (InsertPt) {
 527     makeAvailableAt(Cond0, InsertPt);
 528     makeAvailableAt(Cond1, InsertPt);
 529
 530     Result = BinaryOperator::CreateAnd(Cond0, Cond1, "wide.chk", InsertPt);
 531   }
 532
 533   // We were not able to compute Cond0 AND Cond1 for the price of one.
 534   return false;
 535 }
 536
 537 bool GuardWideningImpl::parseRangeChecks(
 538     Value *CheckCond, SmallVectorImpl<GuardWideningImpl::RangeCheck> &Checks,
 539     SmallPtrSetImpl<Value *> &Visited) {
 540   if (!Visited.insert(CheckCond).second)
 541     return true;
 542
 543   using namespace llvm::PatternMatch;
 544
 545   {
 546     Value *AndLHS, *AndRHS;
 547     if (match(CheckCond, m_And(m_Value(AndLHS), m_Value(AndRHS))))
 548       return parseRangeChecks(AndLHS, Checks) &&
 549              parseRangeChecks(AndRHS, Checks);
 550   }
 551
 552   auto *IC = dyn_cast<ICmpInst>(CheckCond);
 553   if (!IC || !IC->getOperand(0)->getType()->isIntegerTy() ||
 554       (IC->getPredicate() != ICmpInst::ICMP_ULT &&
 555        IC->getPredicate() != ICmpInst::ICMP_UGT))
 556     return false;
 557
 558   Value *CmpLHS = IC->getOperand(0), *CmpRHS = IC->getOperand(1);
 559   if (IC->getPredicate() == ICmpInst::ICMP_UGT)
 560     std::swap(CmpLHS, CmpRHS);
 561
 562   auto &DL = IC->getModule()->getDataLayout();
 563
 564   GuardWideningImpl::RangeCheck Check(
 565       CmpLHS, cast<ConstantInt>(ConstantInt::getNullValue(CmpRHS->getType())),
 566       CmpRHS, IC);
 567
 568   if (!isKnownNonNegative(Check.getLength(), DL))
 569     return false;
 570
 571   // What we have in \c Check now is a correct interpretation of \p CheckCond.
 572   // Try to see if we can move some constant offsets into the \c Offset field.
 573
 574   bool Changed;
 575   auto &Ctx = CheckCond->getContext();
 576
 577   do {
 578     Value *OpLHS;
 579     ConstantInt *OpRHS;
 580     Changed = false;
 581
 582 #ifndef NDEBUG
 583     auto *BaseInst = dyn_cast<Instruction>(Check.getBase());
 584     assert((!BaseInst || DT.isReachableFromEntry(BaseInst->getParent())) &&
 585            "Unreachable instruction?");
 586 #endif
 587
 588     if (match(Check.getBase(), m_Add(m_Value(OpLHS), m_ConstantInt(OpRHS)))) {
 589       Check.setBase(OpLHS);
 590       APInt NewOffset = Check.getOffsetValue() + OpRHS->getValue();
 591       Check.setOffset(ConstantInt::get(Ctx, NewOffset));
 592       Changed = true;
 593     } else if (match(Check.getBase(),
 594                      m_Or(m_Value(OpLHS), m_ConstantInt(OpRHS)))) {
 595       KnownBits Known = computeKnownBits(OpLHS, DL);
 596       if ((OpRHS->getValue() & Known.Zero) == OpRHS->getValue()) {
 597         Check.setBase(OpLHS);
 598         APInt NewOffset = Check.getOffsetValue() + OpRHS->getValue();
 599         Check.setOffset(ConstantInt::get(Ctx, NewOffset));
 600         Changed = true;
 601       }
 602     }
 603   } while (Changed);
 604
 605   Checks.push_back(Check);
 606   return true;
 607 }
 608
 609 bool GuardWideningImpl::combineRangeChecks(
 610     SmallVectorImpl<GuardWideningImpl::RangeCheck> &Checks,
 611     SmallVectorImpl<GuardWideningImpl::RangeCheck> &RangeChecksOut) {
 612   unsigned OldCount = Checks.size();
 613   while (!Checks.empty()) {
 614     // Pick all of the range checks with a specific base and length, and try to
 615     // merge them.
 616     Value *CurrentBase = Checks.front().getBase();
 617     Value *CurrentLength = Checks.front().getLength();
 618
 619     SmallVector<GuardWideningImpl::RangeCheck, 3> CurrentChecks;
 620
 621     auto IsCurrentCheck = [&](GuardWideningImpl::RangeCheck &RC) {
 622       return RC.getBase() == CurrentBase && RC.getLength() == CurrentLength;
 623     };
 624
 625     copy_if(Checks, std::back_inserter(CurrentChecks), IsCurrentCheck);
 626     Checks.erase(remove_if(Checks, IsCurrentCheck), Checks.end());
 627
 628     assert(CurrentChecks.size() != 0 && "We know we have at least one!");
 629
 630     if (CurrentChecks.size() < 3) {
 631       RangeChecksOut.insert(RangeChecksOut.end(), CurrentChecks.begin(),
 632                             CurrentChecks.end());
 633       continue;
 634     }
 635
 636     // CurrentChecks.size() will typically be 3 here, but so far there has been
 637     // no need to hard-code that fact.
 638
 639     llvm::sort(CurrentChecks.begin(), CurrentChecks.end(),
 640                [&](const GuardWideningImpl::RangeCheck &LHS,
 641                    const GuardWideningImpl::RangeCheck &RHS) {
 642       return LHS.getOffsetValue().slt(RHS.getOffsetValue());
 643     });
 644
 645     // Note: std::sort should not invalidate the ChecksStart iterator.
 646
 647     ConstantInt *MinOffset = CurrentChecks.front().getOffset(),
 648                 *MaxOffset = CurrentChecks.back().getOffset();
 649
 650     unsigned BitWidth = MaxOffset->getValue().getBitWidth();
 651     if ((MaxOffset->getValue() - MinOffset->getValue())
 652             .ugt(APInt::getSignedMinValue(BitWidth)))
 653       return false;
 654
 655     APInt MaxDiff = MaxOffset->getValue() - MinOffset->getValue();
 656     const APInt &HighOffset = MaxOffset->getValue();
 657     auto OffsetOK = [&](const GuardWideningImpl::RangeCheck &RC) {
 658       return (HighOffset - RC.getOffsetValue()).ult(MaxDiff);
 659     };
 660
 661     if (MaxDiff.isMinValue() ||
 662         !std::all_of(std::next(CurrentChecks.begin()), CurrentChecks.end(),
 663                      OffsetOK))
 664       return false;
 665
 666     // We have a series of f+1 checks as:
 667     //
 668     //   I+k_0 u< L   ... Chk_0
 669     //   I+k_1 u< L   ... Chk_1
 670     //   ...
 671     //   I+k_f u< L   ... Chk_f
 672     //
 673     //     with forall i in [0,f]: k_f-k_i u< k_f-k_0  ... Precond_0
 674     //          k_f-k_0 u< INT_MIN+k_f                 ... Precond_1
 675     //          k_f != k_0                             ... Precond_2
 676     //
 677     // Claim:
 678     //   Chk_0 AND Chk_f  implies all the other checks
 679     //
 680     // Informal proof sketch:
 681     //
 682     // We will show that the integer range [I+k_0,I+k_f] does not unsigned-wrap
 683     // (i.e. going from I+k_0 to I+k_f does not cross the -1,0 boundary) and
 684     // thus I+k_f is the greatest unsigned value in that range.
 685     //
 686     // This combined with Ckh_(f+1) shows that everything in that range is u< L.
 687     // Via Precond_0 we know that all of the indices in Chk_0 through Chk_(f+1)
 688     // lie in [I+k_0,I+k_f], this proving our claim.
 689     //
 690     // To see that [I+k_0,I+k_f] is not a wrapping range, note that there are
 691     // two possibilities: I+k_0 u< I+k_f or I+k_0 >u I+k_f (they can't be equal
 692     // since k_0 != k_f).  In the former case, [I+k_0,I+k_f] is not a wrapping
 693     // range by definition, and the latter case is impossible:
 694     //
 695     //   0-----I+k_f---I+k_0----L---INT_MAX,INT_MIN------------------(-1)
 696     //   xxxxxx             xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
 697     //
 698     // For Chk_0 to succeed, we'd have to have k_f-k_0 (the range highlighted
 699     // with 'x' above) to be at least >u INT_MIN.
 700
 701     RangeChecksOut.emplace_back(CurrentChecks.front());
 702     RangeChecksOut.emplace_back(CurrentChecks.back());
 703   }
 704
 705   assert(RangeChecksOut.size() <= OldCount && "We pessimized!");
 706   return RangeChecksOut.size() != OldCount;
 707 }
 708
 709 #ifndef NDEBUG
 710 StringRef GuardWideningImpl::scoreTypeToString(WideningScore WS) {
 711   switch (WS) {
 712   case WS_IllegalOrNegative:
 713     return "IllegalOrNegative";
 714   case WS_Neutral:
 715     return "Neutral";
 716   case WS_Positive:
 717     return "Positive";
 718   case WS_VeryPositive:
 719     return "VeryPositive";
 720   }
 721
 722   llvm_unreachable("Fully covered switch above!");
 723 }
 724 #endif
 725
 726 PreservedAnalyses GuardWideningPass::run(Function &F,
 727                                          FunctionAnalysisManager &AM) {
 728   auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
 729   auto &LI = AM.getResult<LoopAnalysis>(F);
 730   auto &PDT = AM.getResult<PostDominatorTreeAnalysis>(F);
 731   if (!GuardWideningImpl(DT, &PDT, LI, DT.getRootNode(),
 732                          [](BasicBlock*) { return true; } ).run())
 733     return PreservedAnalyses::all();
 734
 735   PreservedAnalyses PA;
 736   PA.preserveSet<CFGAnalyses>();
 737   return PA;
 738 }
 739
 740 namespace {
 741 struct GuardWideningLegacyPass : public FunctionPass {
 742   static char ID;
 743
 744   GuardWideningLegacyPass() : FunctionPass(ID) {
 745     initializeGuardWideningLegacyPassPass(*PassRegistry::getPassRegistry());
 746   }
 747
 748   bool runOnFunction(Function &F) override {
 749     if (skipFunction(F))
 750       return false;
 751     auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
 752     auto &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
 753     auto &PDT = getAnalysis<PostDominatorTreeWrapperPass>().getPostDomTree();
 754     return GuardWideningImpl(DT, &PDT, LI, DT.getRootNode(),
 755                          [](BasicBlock*) { return true; } ).run();
 756   }
 757
 758   void getAnalysisUsage(AnalysisUsage &AU) const override {
 759     AU.setPreservesCFG();
 760     AU.addRequired<DominatorTreeWrapperPass>();
 761     AU.addRequired<PostDominatorTreeWrapperPass>();
 762     AU.addRequired<LoopInfoWrapperPass>();
 763   }
 764 };
 765
 766 /// Same as above, but restricted to a single loop at a time.  Can be
 767 /// scheduled with other loop passes w/o breaking out of LPM
 768 struct LoopGuardWideningLegacyPass : public LoopPass {
 769   static char ID;
 770
 771   LoopGuardWideningLegacyPass() : LoopPass(ID) {
 772     initializeLoopGuardWideningLegacyPassPass(*PassRegistry::getPassRegistry());
 773   }
 774
 775   bool runOnLoop(Loop *L, LPPassManager &LPM) override {
 776     if (skipLoop(L))
 777       return false;
 778     auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
 779     auto &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
 780     auto *PDTWP = getAnalysisIfAvailable<PostDominatorTreeWrapperPass>();
 781     auto *PDT = PDTWP ? &PDTWP->getPostDomTree() : nullptr;
 782     BasicBlock *RootBB = L->getLoopPredecessor();
 783     if (!RootBB)
 784       RootBB = L->getHeader();
 785     auto BlockFilter = [&](BasicBlock *BB) {
 786       return BB == RootBB || L->contains(BB);
 787     };
 788     return GuardWideningImpl(DT, PDT, LI,
 789                              DT.getNode(RootBB), BlockFilter).run();
 790   }
 791
 792   void getAnalysisUsage(AnalysisUsage &AU) const override {
 793     AU.setPreservesCFG();
 794     getLoopAnalysisUsage(AU);
 795     AU.addPreserved<PostDominatorTreeWrapperPass>();
 796   }
 797 };
 798 }
 799
 800 char GuardWideningLegacyPass::ID = 0;
 801 char LoopGuardWideningLegacyPass::ID = 0;
 802
 803 INITIALIZE_PASS_BEGIN(GuardWideningLegacyPass, "guard-widening", "Widen guards",
 804                       false, false)
 805 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
 806 INITIALIZE_PASS_DEPENDENCY(PostDominatorTreeWrapperPass)
 807 INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
 808 INITIALIZE_PASS_END(GuardWideningLegacyPass, "guard-widening", "Widen guards",
 809                     false, false)
 810
 811 INITIALIZE_PASS_BEGIN(LoopGuardWideningLegacyPass, "loop-guard-widening",
 812                       "Widen guards (within a single loop, as a loop pass)",
 813                       false, false)
 814 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
 815 INITIALIZE_PASS_DEPENDENCY(PostDominatorTreeWrapperPass)
 816 INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
 817 INITIALIZE_PASS_END(LoopGuardWideningLegacyPass, "loop-guard-widening",
 818                     "Widen guards (within a single loop, as a loop pass)",
 819                     false, false)
 820
 821 FunctionPass *llvm::createGuardWideningPass() {
 822   return new GuardWideningLegacyPass();
 823 }
 824
 825 Pass *llvm::createLoopGuardWideningPass() {
 826   return new LoopGuardWideningLegacyPass();
 827 }