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 "llvm/Pass.h"
  44 #include "llvm/ADT/DenseMap.h"
  45 #include "llvm/ADT/DepthFirstIterator.h"
  46 #include "llvm/Analysis/LoopInfo.h"
  47 #include "llvm/Analysis/PostDominators.h"
  48 #include "llvm/Analysis/ValueTracking.h"
  49 #include "llvm/IR/ConstantRange.h"
  50 #include "llvm/IR/Dominators.h"
  51 #include "llvm/IR/IntrinsicInst.h"
  52 #include "llvm/IR/PatternMatch.h"
  53 #include "llvm/Support/Debug.h"
  54 #include "llvm/Transforms/Scalar.h"
  55
  56 using namespace llvm;
  57
  58 #define DEBUG_TYPE "guard-widening"
  59
  60 namespace {
  61
  62 class GuardWideningImpl {
  63   DominatorTree &DT;
  64   PostDominatorTree &PDT;
  65   LoopInfo &LI;
  66
  67   /// The set of guards whose conditions have been widened into dominating
  68   /// guards.
  69   SmallVector<IntrinsicInst *, 16> EliminatedGuards;
  70
  71   /// The set of guards which have been widened to include conditions to other
  72   /// guards.
  73   DenseSet<IntrinsicInst *> WidenedGuards;
  74
  75   /// Try to eliminate guard \p Guard by widening it into an earlier dominating
  76   /// guard.  \p DFSI is the DFS iterator on the dominator tree that is
  77   /// currently visiting the block containing \p Guard, and \p GuardsPerBlock
  78   /// maps BasicBlocks to the set of guards seen in that block.
  79   bool eliminateGuardViaWidening(
  80       IntrinsicInst *Guard, const df_iterator<DomTreeNode *> &DFSI,
  81       const DenseMap<BasicBlock *, SmallVector<IntrinsicInst *, 8>> &
  82           GuardsPerBlock);
  83
  84   /// Used to keep track of which widening potential is more effective.
  85   enum WideningScore {
  86     /// Don't widen.
  87     WS_IllegalOrNegative,
  88
  89     /// Widening is performance neutral as far as the cycles spent in check
  90     /// conditions goes (but can still help, e.g., code layout, having less
  91     /// deopt state).
  92     WS_Neutral,
  93
  94     /// Widening is profitable.
  95     WS_Positive,
  96
  97     /// Widening is very profitable.  Not significantly different from \c
  98     /// WS_Positive, except by the order.
  99     WS_VeryPositive
 100   };
 101
 102   static StringRef scoreTypeToString(WideningScore WS);
 103
 104   /// Compute the score for widening the condition in \p DominatedGuard
 105   /// (contained in \p DominatedGuardLoop) into \p DominatingGuard (contained in
 106   /// \p DominatingGuardLoop).
 107   WideningScore computeWideningScore(IntrinsicInst *DominatedGuard,
 108                                      Loop *DominatedGuardLoop,
 109                                      IntrinsicInst *DominatingGuard,
 110                                      Loop *DominatingGuardLoop);
 111
 112   /// Helper to check if \p V can be hoisted to \p InsertPos.
 113   bool isAvailableAt(Value *V, Instruction *InsertPos) {
 114     SmallPtrSet<Instruction *, 8> Visited;
 115     return isAvailableAt(V, InsertPos, Visited);
 116   }
 117
 118   bool isAvailableAt(Value *V, Instruction *InsertPos,
 119                      SmallPtrSetImpl<Instruction *> &Visited);
 120
 121   /// Helper to hoist \p V to \p InsertPos.  Guaranteed to succeed if \c
 122   /// isAvailableAt returned true.
 123   void makeAvailableAt(Value *V, Instruction *InsertPos);
 124
 125   /// Common helper used by \c widenGuard and \c isWideningCondProfitable.  Try
 126   /// to generate an expression computing the logical AND of \p Cond0 and \p
 127   /// Cond1.  Return true if the expression computing the AND is only as
 128   /// expensive as computing one of the two. If \p InsertPt is true then
 129   /// actually generate the resulting expression, make it available at \p
 130   /// InsertPt and return it in \p Result (else no change to the IR is made).
 131   bool widenCondCommon(Value *Cond0, Value *Cond1, Instruction *InsertPt,
 132                        Value *&Result);
 133
 134   /// Represents a range check of the form \c Base + \c Offset u< \c Length,
 135   /// with the constraint that \c Length is not negative.  \c CheckInst is the
 136   /// pre-existing instruction in the IR that computes the result of this range
 137   /// check.
 138   class RangeCheck {
 139     Value *Base;
 140     ConstantInt *Offset;
 141     Value *Length;
 142     ICmpInst *CheckInst;
 143
 144   public:
 145     explicit RangeCheck(Value *Base, ConstantInt *Offset, Value *Length,
 146                         ICmpInst *CheckInst)
 147         : Base(Base), Offset(Offset), Length(Length), CheckInst(CheckInst) {}
 148
 149     void setBase(Value *NewBase) { Base = NewBase; }
 150     void setOffset(ConstantInt *NewOffset) { Offset = NewOffset; }
 151
 152     Value *getBase() const { return Base; }
 153     ConstantInt *getOffset() const { return Offset; }
 154     const APInt &getOffsetValue() const { return getOffset()->getValue(); }
 155     Value *getLength() const { return Length; };
 156     ICmpInst *getCheckInst() const { return CheckInst; }
 157
 158     void print(raw_ostream &OS, bool PrintTypes = false) {
 159       OS << "Base: ";
 160       Base->printAsOperand(OS, PrintTypes);
 161       OS << " Offset: ";
 162       Offset->printAsOperand(OS, PrintTypes);
 163       OS << " Length: ";
 164       Length->printAsOperand(OS, PrintTypes);
 165     }
 166
 167     LLVM_DUMP_METHOD void dump() {
 168       print(dbgs());
 169       dbgs() << "\n";
 170     }
 171   };
 172
 173   /// Parse \p CheckCond into a conjunction (logical-and) of range checks; and
 174   /// append them to \p Checks.  Returns true on success, may clobber \c Checks
 175   /// on failure.
 176   bool parseRangeChecks(Value *CheckCond, SmallVectorImpl<RangeCheck> &Checks) {
 177     SmallPtrSet<Value *, 8> Visited;
 178     return parseRangeChecks(CheckCond, Checks, Visited);
 179   }
 180
 181   bool parseRangeChecks(Value *CheckCond, SmallVectorImpl<RangeCheck> &Checks,
 182                         SmallPtrSetImpl<Value *> &Visited);
 183
 184   /// Combine the checks in \p Checks into a smaller set of checks and append
 185   /// them into \p CombinedChecks.  Return true on success (i.e. all of checks
 186   /// in \p Checks were combined into \p CombinedChecks).  Clobbers \p Checks
 187   /// and \p CombinedChecks on success and on failure.
 188   bool combineRangeChecks(SmallVectorImpl<RangeCheck> &Checks,
 189                           SmallVectorImpl<RangeCheck> &CombinedChecks);
 190
 191   /// Can we compute the logical AND of \p Cond0 and \p Cond1 for the price of
 192   /// computing only one of the two expressions?
 193   bool isWideningCondProfitable(Value *Cond0, Value *Cond1) {
 194     Value *ResultUnused;
 195     return widenCondCommon(Cond0, Cond1, /*InsertPt=*/nullptr, ResultUnused);
 196   }
 197
 198   /// Widen \p ToWiden to fail if \p NewCondition is false (in addition to
 199   /// whatever it is already checking).
 200   void widenGuard(IntrinsicInst *ToWiden, Value *NewCondition) {
 201     Value *Result;
 202     widenCondCommon(ToWiden->getArgOperand(0), NewCondition, ToWiden, Result);
 203     ToWiden->setArgOperand(0, Result);
 204   }
 205
 206 public:
 207   explicit GuardWideningImpl(DominatorTree &DT, PostDominatorTree &PDT,
 208                              LoopInfo &LI)
 209       : DT(DT), PDT(PDT), LI(LI) {}
 210
 211   /// The entry point for this pass.
 212   bool run();
 213 };
 214
 215 struct GuardWideningLegacyPass : public FunctionPass {
 216   static char ID;
 217   GuardWideningPass Impl;
 218
 219   GuardWideningLegacyPass() : FunctionPass(ID) {
 220     initializeGuardWideningLegacyPassPass(*PassRegistry::getPassRegistry());
 221   }
 222
 223   bool runOnFunction(Function &F) override {
 224     if (skipFunction(F))
 225       return false;
 226     return GuardWideningImpl(
 227                getAnalysis<DominatorTreeWrapperPass>().getDomTree(),
 228                getAnalysis<PostDominatorTreeWrapperPass>().getPostDomTree(),
 229                getAnalysis<LoopInfoWrapperPass>().getLoopInfo()).run();
 230   }
 231
 232   void getAnalysisUsage(AnalysisUsage &AU) const override {
 233     AU.setPreservesCFG();
 234     AU.addRequired<DominatorTreeWrapperPass>();
 235     AU.addRequired<PostDominatorTreeWrapperPass>();
 236     AU.addRequired<LoopInfoWrapperPass>();
 237   }
 238 };
 239
 240 }
 241
 242 bool GuardWideningImpl::run() {
 243   using namespace llvm::PatternMatch;
 244
 245   DenseMap<BasicBlock *, SmallVector<IntrinsicInst *, 8>> GuardsInBlock;
 246   bool Changed = false;
 247
 248   for (auto DFI = df_begin(DT.getRootNode()), DFE = df_end(DT.getRootNode());
 249        DFI != DFE; ++DFI) {
 250     auto *BB = (*DFI)->getBlock();
 251     auto &CurrentList = GuardsInBlock[BB];
 252
 253     for (auto &I : *BB)
 254       if (match(&I, m_Intrinsic<Intrinsic::experimental_guard>()))
 255         CurrentList.push_back(cast<IntrinsicInst>(&I));
 256
 257     for (auto *II : CurrentList)
 258       Changed |= eliminateGuardViaWidening(II, DFI, GuardsInBlock);
 259   }
 260
 261   for (auto *II : EliminatedGuards)
 262     if (!WidenedGuards.count(II))
 263       II->eraseFromParent();
 264
 265   return Changed;
 266 }
 267
 268 bool GuardWideningImpl::eliminateGuardViaWidening(
 269     IntrinsicInst *GuardInst, const df_iterator<DomTreeNode *> &DFSI,
 270     const DenseMap<BasicBlock *, SmallVector<IntrinsicInst *, 8>> &
 271         GuardsInBlock) {
 272   IntrinsicInst *BestSoFar = nullptr;
 273   auto BestScoreSoFar = WS_IllegalOrNegative;
 274   auto *GuardInstLoop = LI.getLoopFor(GuardInst->getParent());
 275
 276   // In the set of dominating guards, find the one we can merge GuardInst with
 277   // for the most profit.
 278   for (unsigned i = 0, e = DFSI.getPathLength(); i != e; ++i) {
 279     auto *CurBB = DFSI.getPath(i)->getBlock();
 280     auto *CurLoop = LI.getLoopFor(CurBB);
 281     assert(GuardsInBlock.count(CurBB) && "Must have been populated by now!");
 282     const auto &GuardsInCurBB = GuardsInBlock.find(CurBB)->second;
 283
 284     auto I = GuardsInCurBB.begin();
 285     auto E = GuardsInCurBB.end();
 286
 287 #ifndef NDEBUG
 288     {
 289       unsigned Index = 0;
 290       for (auto &I : *CurBB) {
 291         if (Index == GuardsInCurBB.size())
 292           break;
 293         if (GuardsInCurBB[Index] == &I)
 294           Index++;
 295       }
 296       assert(Index == GuardsInCurBB.size() &&
 297              "Guards expected to be in order!");
 298     }
 299 #endif
 300
 301     assert((i == (e - 1)) == (GuardInst->getParent() == CurBB) && "Bad DFS?");
 302
 303     if (i == (e - 1)) {
 304       // Corner case: make sure we're only looking at guards strictly dominating
 305       // GuardInst when visiting GuardInst->getParent().
 306       auto NewEnd = std::find(I, E, GuardInst);
 307       assert(NewEnd != E && "GuardInst not in its own block?");
 308       E = NewEnd;
 309     }
 310
 311     for (auto *Candidate : make_range(I, E)) {
 312       auto Score =
 313           computeWideningScore(GuardInst, GuardInstLoop, Candidate, CurLoop);
 314       DEBUG(dbgs() << "Score between " << *GuardInst->getArgOperand(0)
 315                    << " and " << *Candidate->getArgOperand(0) << " is "
 316                    << scoreTypeToString(Score) << "\n");
 317       if (Score > BestScoreSoFar) {
 318         BestScoreSoFar = Score;
 319         BestSoFar = Candidate;
 320       }
 321     }
 322   }
 323
 324   if (BestScoreSoFar == WS_IllegalOrNegative) {
 325     DEBUG(dbgs() << "Did not eliminate guard " << *GuardInst << "\n");
 326     return false;
 327   }
 328
 329   assert(BestSoFar != GuardInst && "Should have never visited same guard!");
 330   assert(DT.dominates(BestSoFar, GuardInst) && "Should be!");
 331
 332   DEBUG(dbgs() << "Widening " << *GuardInst << " into " << *BestSoFar
 333                << " with score " << scoreTypeToString(BestScoreSoFar) << "\n");
 334   widenGuard(BestSoFar, GuardInst->getArgOperand(0));
 335   GuardInst->setArgOperand(0, ConstantInt::getTrue(GuardInst->getContext()));
 336   EliminatedGuards.push_back(GuardInst);
 337   WidenedGuards.insert(BestSoFar);
 338   return true;
 339 }
 340
 341 GuardWideningImpl::WideningScore GuardWideningImpl::computeWideningScore(
 342     IntrinsicInst *DominatedGuard, Loop *DominatedGuardLoop,
 343     IntrinsicInst *DominatingGuard, Loop *DominatingGuardLoop) {
 344   bool HoistingOutOfLoop = false;
 345
 346   if (DominatingGuardLoop != DominatedGuardLoop) {
 347     if (DominatingGuardLoop &&
 348         !DominatingGuardLoop->contains(DominatedGuardLoop))
 349       return WS_IllegalOrNegative;
 350
 351     HoistingOutOfLoop = true;
 352   }
 353
 354   if (!isAvailableAt(DominatedGuard->getArgOperand(0), DominatingGuard))
 355     return WS_IllegalOrNegative;
 356
 357   bool HoistingOutOfIf =
 358       !PDT.dominates(DominatedGuard->getParent(), DominatingGuard->getParent());
 359
 360   if (isWideningCondProfitable(DominatedGuard->getArgOperand(0),
 361                                DominatingGuard->getArgOperand(0)))
 362     return HoistingOutOfLoop ? WS_VeryPositive : WS_Positive;
 363
 364   if (HoistingOutOfLoop)
 365     return WS_Positive;
 366
 367   return HoistingOutOfIf ? WS_IllegalOrNegative : WS_Neutral;
 368 }
 369
 370 bool GuardWideningImpl::isAvailableAt(Value *V, Instruction *Loc,
 371                                       SmallPtrSetImpl<Instruction *> &Visited) {
 372   auto *Inst = dyn_cast<Instruction>(V);
 373   if (!Inst || DT.dominates(Inst, Loc) || Visited.count(Inst))
 374     return true;
 375
 376   if (!isSafeToSpeculativelyExecute(Inst, Loc, &DT) ||
 377       Inst->mayReadFromMemory())
 378     return false;
 379
 380   Visited.insert(Inst);
 381
 382   // We only want to go _up_ the dominance chain when recursing.
 383   assert(!isa<PHINode>(Loc) &&
 384          "PHIs should return false for isSafeToSpeculativelyExecute");
 385   assert(DT.isReachableFromEntry(Inst->getParent()) &&
 386          "We did a DFS from the block entry!");
 387   return all_of(Inst->operands(),
 388                 [&](Value *Op) { return isAvailableAt(Op, Loc, Visited); });
 389 }
 390
 391 void GuardWideningImpl::makeAvailableAt(Value *V, Instruction *Loc) {
 392   auto *Inst = dyn_cast<Instruction>(V);
 393   if (!Inst || DT.dominates(Inst, Loc))
 394     return;
 395
 396   assert(isSafeToSpeculativelyExecute(Inst, Loc, &DT) &&
 397          !Inst->mayReadFromMemory() && "Should've checked with isAvailableAt!");
 398
 399   for (Value *Op : Inst->operands())
 400     makeAvailableAt(Op, Loc);
 401
 402   Inst->moveBefore(Loc);
 403 }
 404
 405 bool GuardWideningImpl::widenCondCommon(Value *Cond0, Value *Cond1,
 406                                         Instruction *InsertPt, Value *&Result) {
 407   using namespace llvm::PatternMatch;
 408
 409   {
 410     // L >u C0 && L >u C1  ->  L >u max(C0, C1)
 411     ConstantInt *RHS0, *RHS1;
 412     Value *LHS;
 413     ICmpInst::Predicate Pred0, Pred1;
 414     if (match(Cond0, m_ICmp(Pred0, m_Value(LHS), m_ConstantInt(RHS0))) &&
 415         match(Cond1, m_ICmp(Pred1, m_Specific(LHS), m_ConstantInt(RHS1)))) {
 416
 417       ConstantRange CR0 =
 418           ConstantRange::makeExactICmpRegion(Pred0, RHS0->getValue());
 419       ConstantRange CR1 =
 420           ConstantRange::makeExactICmpRegion(Pred1, RHS1->getValue());
 421
 422       // SubsetIntersect is a subset of the actual mathematical intersection of
 423       // CR0 and CR1, while SupersetIntersect is a superset of the actual
 424       // mathematical intersection.  If these two ConstantRanges are equal, then
 425       // we know we were able to represent the actual mathematical intersection
 426       // of CR0 and CR1, and can use the same to generate an icmp instruction.
 427       //
 428       // Given what we're doing here and the semantics of guards, it would
 429       // actually be correct to just use SubsetIntersect, but that may be too
 430       // aggressive in cases we care about.
 431       auto SubsetIntersect = CR0.inverse().unionWith(CR1.inverse()).inverse();
 432       auto SupersetIntersect = CR0.intersectWith(CR1);
 433
 434       APInt NewRHSAP;
 435       CmpInst::Predicate Pred;
 436       if (SubsetIntersect == SupersetIntersect &&
 437           SubsetIntersect.getEquivalentICmp(Pred, NewRHSAP)) {
 438         if (InsertPt) {
 439           ConstantInt *NewRHS = ConstantInt::get(Cond0->getContext(), NewRHSAP);
 440           Result = new ICmpInst(InsertPt, Pred, LHS, NewRHS, "wide.chk");
 441         }
 442         return true;
 443       }
 444     }
 445   }
 446
 447   {
 448     SmallVector<GuardWideningImpl::RangeCheck, 4> Checks, CombinedChecks;
 449     if (parseRangeChecks(Cond0, Checks) && parseRangeChecks(Cond1, Checks) &&
 450         combineRangeChecks(Checks, CombinedChecks)) {
 451       if (InsertPt) {
 452         Result = nullptr;
 453         for (auto &RC : CombinedChecks) {
 454           makeAvailableAt(RC.getCheckInst(), InsertPt);
 455           if (Result)
 456             Result = BinaryOperator::CreateAnd(RC.getCheckInst(), Result, "",
 457                                                InsertPt);
 458           else
 459             Result = RC.getCheckInst();
 460         }
 461
 462         Result->setName("wide.chk");
 463       }
 464       return true;
 465     }
 466   }
 467
 468   // Base case -- just logical-and the two conditions together.
 469
 470   if (InsertPt) {
 471     makeAvailableAt(Cond0, InsertPt);
 472     makeAvailableAt(Cond1, InsertPt);
 473
 474     Result = BinaryOperator::CreateAnd(Cond0, Cond1, "wide.chk", InsertPt);
 475   }
 476
 477   // We were not able to compute Cond0 AND Cond1 for the price of one.
 478   return false;
 479 }
 480
 481 bool GuardWideningImpl::parseRangeChecks(
 482     Value *CheckCond, SmallVectorImpl<GuardWideningImpl::RangeCheck> &Checks,
 483     SmallPtrSetImpl<Value *> &Visited) {
 484   if (!Visited.insert(CheckCond).second)
 485     return true;
 486
 487   using namespace llvm::PatternMatch;
 488
 489   {
 490     Value *AndLHS, *AndRHS;
 491     if (match(CheckCond, m_And(m_Value(AndLHS), m_Value(AndRHS))))
 492       return parseRangeChecks(AndLHS, Checks) &&
 493              parseRangeChecks(AndRHS, Checks);
 494   }
 495
 496   auto *IC = dyn_cast<ICmpInst>(CheckCond);
 497   if (!IC || !IC->getOperand(0)->getType()->isIntegerTy() ||
 498       (IC->getPredicate() != ICmpInst::ICMP_ULT &&
 499        IC->getPredicate() != ICmpInst::ICMP_UGT))
 500     return false;
 501
 502   Value *CmpLHS = IC->getOperand(0), *CmpRHS = IC->getOperand(1);
 503   if (IC->getPredicate() == ICmpInst::ICMP_UGT)
 504     std::swap(CmpLHS, CmpRHS);
 505
 506   auto &DL = IC->getModule()->getDataLayout();
 507
 508   GuardWideningImpl::RangeCheck Check(
 509       CmpLHS, cast<ConstantInt>(ConstantInt::getNullValue(CmpRHS->getType())),
 510       CmpRHS, IC);
 511
 512   if (!isKnownNonNegative(Check.getLength(), DL))
 513     return false;
 514
 515   // What we have in \c Check now is a correct interpretation of \p CheckCond.
 516   // Try to see if we can move some constant offsets into the \c Offset field.
 517
 518   bool Changed;
 519   auto &Ctx = CheckCond->getContext();
 520
 521   do {
 522     Value *OpLHS;
 523     ConstantInt *OpRHS;
 524     Changed = false;
 525
 526 #ifndef NDEBUG
 527     auto *BaseInst = dyn_cast<Instruction>(Check.getBase());
 528     assert((!BaseInst || DT.isReachableFromEntry(BaseInst->getParent())) &&
 529            "Unreachable instruction?");
 530 #endif
 531
 532     if (match(Check.getBase(), m_Add(m_Value(OpLHS), m_ConstantInt(OpRHS)))) {
 533       Check.setBase(OpLHS);
 534       APInt NewOffset = Check.getOffsetValue() + OpRHS->getValue();
 535       Check.setOffset(ConstantInt::get(Ctx, NewOffset));
 536       Changed = true;
 537     } else if (match(Check.getBase(),
 538                      m_Or(m_Value(OpLHS), m_ConstantInt(OpRHS)))) {
 539       unsigned BitWidth = OpLHS->getType()->getScalarSizeInBits();
 540       APInt KnownZero(BitWidth, 0), KnownOne(BitWidth, 0);
 541       computeKnownBits(OpLHS, KnownZero, KnownOne, DL);
 542       if ((OpRHS->getValue() & KnownZero) == OpRHS->getValue()) {
 543         Check.setBase(OpLHS);
 544         APInt NewOffset = Check.getOffsetValue() + OpRHS->getValue();
 545         Check.setOffset(ConstantInt::get(Ctx, NewOffset));
 546         Changed = true;
 547       }
 548     }
 549   } while (Changed);
 550
 551   Checks.push_back(Check);
 552   return true;
 553 }
 554
 555 bool GuardWideningImpl::combineRangeChecks(
 556     SmallVectorImpl<GuardWideningImpl::RangeCheck> &Checks,
 557     SmallVectorImpl<GuardWideningImpl::RangeCheck> &RangeChecksOut) {
 558   unsigned OldCount = Checks.size();
 559   while (!Checks.empty()) {
 560     // Pick all of the range checks with a specific base and length, and try to
 561     // merge them.
 562     Value *CurrentBase = Checks.front().getBase();
 563     Value *CurrentLength = Checks.front().getLength();
 564
 565     SmallVector<GuardWideningImpl::RangeCheck, 3> CurrentChecks;
 566
 567     auto IsCurrentCheck = [&](GuardWideningImpl::RangeCheck &RC) {
 568       return RC.getBase() == CurrentBase && RC.getLength() == CurrentLength;
 569     };
 570
 571     std::copy_if(Checks.begin(), Checks.end(),
 572                  std::back_inserter(CurrentChecks), IsCurrentCheck);
 573     Checks.erase(remove_if(Checks, IsCurrentCheck), Checks.end());
 574
 575     assert(CurrentChecks.size() != 0 && "We know we have at least one!");
 576
 577     if (CurrentChecks.size() < 3) {
 578       RangeChecksOut.insert(RangeChecksOut.end(), CurrentChecks.begin(),
 579                             CurrentChecks.end());
 580       continue;
 581     }
 582
 583     // CurrentChecks.size() will typically be 3 here, but so far there has been
 584     // no need to hard-code that fact.
 585
 586     std::sort(CurrentChecks.begin(), CurrentChecks.end(),
 587               [&](const GuardWideningImpl::RangeCheck &LHS,
 588                   const GuardWideningImpl::RangeCheck &RHS) {
 589       return LHS.getOffsetValue().slt(RHS.getOffsetValue());
 590     });
 591
 592     // Note: std::sort should not invalidate the ChecksStart iterator.
 593
 594     ConstantInt *MinOffset = CurrentChecks.front().getOffset(),
 595                 *MaxOffset = CurrentChecks.back().getOffset();
 596
 597     unsigned BitWidth = MaxOffset->getValue().getBitWidth();
 598     if ((MaxOffset->getValue() - MinOffset->getValue())
 599             .ugt(APInt::getSignedMinValue(BitWidth)))
 600       return false;
 601
 602     APInt MaxDiff = MaxOffset->getValue() - MinOffset->getValue();
 603     const APInt &HighOffset = MaxOffset->getValue();
 604     auto OffsetOK = [&](const GuardWideningImpl::RangeCheck &RC) {
 605       return (HighOffset - RC.getOffsetValue()).ult(MaxDiff);
 606     };
 607
 608     if (MaxDiff.isMinValue() ||
 609         !std::all_of(std::next(CurrentChecks.begin()), CurrentChecks.end(),
 610                      OffsetOK))
 611       return false;
 612
 613     // We have a series of f+1 checks as:
 614     //
 615     //   I+k_0 u< L   ... Chk_0
 616     //   I_k_1 u< L   ... Chk_1
 617     //   ...
 618     //   I_k_f u< L   ... Chk_(f+1)
 619     //
 620     //     with forall i in [0,f): k_f-k_i u< k_f-k_0  ... Precond_0
 621     //          k_f-k_0 u< INT_MIN+k_f                 ... Precond_1
 622     //          k_f != k_0                             ... Precond_2
 623     //
 624     // Claim:
 625     //   Chk_0 AND Chk_(f+1)  implies all the other checks
 626     //
 627     // Informal proof sketch:
 628     //
 629     // We will show that the integer range [I+k_0,I+k_f] does not unsigned-wrap
 630     // (i.e. going from I+k_0 to I+k_f does not cross the -1,0 boundary) and
 631     // thus I+k_f is the greatest unsigned value in that range.
 632     //
 633     // This combined with Ckh_(f+1) shows that everything in that range is u< L.
 634     // Via Precond_0 we know that all of the indices in Chk_0 through Chk_(f+1)
 635     // lie in [I+k_0,I+k_f], this proving our claim.
 636     //
 637     // To see that [I+k_0,I+k_f] is not a wrapping range, note that there are
 638     // two possibilities: I+k_0 u< I+k_f or I+k_0 >u I+k_f (they can't be equal
 639     // since k_0 != k_f).  In the former case, [I+k_0,I+k_f] is not a wrapping
 640     // range by definition, and the latter case is impossible:
 641     //
 642     //   0-----I+k_f---I+k_0----L---INT_MAX,INT_MIN------------------(-1)
 643     //   xxxxxx             xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
 644     //
 645     // For Chk_0 to succeed, we'd have to have k_f-k_0 (the range highlighted
 646     // with 'x' above) to be at least >u INT_MIN.
 647
 648     RangeChecksOut.emplace_back(CurrentChecks.front());
 649     RangeChecksOut.emplace_back(CurrentChecks.back());
 650   }
 651
 652   assert(RangeChecksOut.size() <= OldCount && "We pessimized!");
 653   return RangeChecksOut.size() != OldCount;
 654 }
 655
 656 PreservedAnalyses GuardWideningPass::run(Function &F,
 657                                          FunctionAnalysisManager &AM) {
 658   auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
 659   auto &LI = AM.getResult<LoopAnalysis>(F);
 660   auto &PDT = AM.getResult<PostDominatorTreeAnalysis>(F);
 661   bool Changed = GuardWideningImpl(DT, PDT, LI).run();
 662   return Changed ? PreservedAnalyses::none() : PreservedAnalyses::all();
 663 }
 664
 665 StringRef GuardWideningImpl::scoreTypeToString(WideningScore WS) {
 666   switch (WS) {
 667   case WS_IllegalOrNegative:
 668     return "IllegalOrNegative";
 669   case WS_Neutral:
 670     return "Neutral";
 671   case WS_Positive:
 672     return "Positive";
 673   case WS_VeryPositive:
 674     return "VeryPositive";
 675   }
 676
 677   llvm_unreachable("Fully covered switch above!");
 678 }
 679
 680 char GuardWideningLegacyPass::ID = 0;
 681
 682 INITIALIZE_PASS_BEGIN(GuardWideningLegacyPass, "guard-widening", "Widen guards",
 683                       false, false)
 684 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
 685 INITIALIZE_PASS_DEPENDENCY(PostDominatorTreeWrapperPass)
 686 INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
 687 INITIALIZE_PASS_END(GuardWideningLegacyPass, "guard-widening", "Widen guards",
 688                     false, false)
 689
 690 FunctionPass *llvm::createGuardWideningPass() {
 691   return new GuardWideningLegacyPass();
 692 }