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