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

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