GuardWidening.cpp revision 360784 
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
65using namespace llvm;
66
67#define DEBUG_TYPE "guard-widening"
68
69STATISTIC(GuardsEliminated, "Number of eliminated guards");
70STATISTIC(CondBranchEliminated, "Number of eliminated conditional branches");
71
72static 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
78namespace {
79
80// Get the condition of \p I. It can either be a guard or a conditional branch.
81static 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.
97static 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.
108static void eliminateGuard(Instruction *GuardInst) {
109  GuardInst->eraseFromParent();
110  ++GuardsEliminated;
111}
112
113class 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
271public:
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
284static 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
292bool 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
327bool 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
403GuardWideningImpl::WideningScore
404GuardWideningImpl::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
462bool 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
484void 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
498bool 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
580bool 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
652bool 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
752StringRef 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
768PreservedAnalyses 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
782PreservedAnalyses 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
798namespace {
799struct 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
826struct 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
858char GuardWideningLegacyPass::ID = 0;
859char LoopGuardWideningLegacyPass::ID = 0;
860
861INITIALIZE_PASS_BEGIN(GuardWideningLegacyPass, "guard-widening", "Widen guards",
862                      false, false)
863INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
864INITIALIZE_PASS_DEPENDENCY(PostDominatorTreeWrapperPass)
865INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
866INITIALIZE_PASS_END(GuardWideningLegacyPass, "guard-widening", "Widen guards",
867                    false, false)
868
869INITIALIZE_PASS_BEGIN(LoopGuardWideningLegacyPass, "loop-guard-widening",
870                      "Widen guards (within a single loop, as a loop pass)",
871                      false, false)
872INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
873INITIALIZE_PASS_DEPENDENCY(PostDominatorTreeWrapperPass)
874INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
875INITIALIZE_PASS_END(LoopGuardWideningLegacyPass, "loop-guard-widening",
876                    "Widen guards (within a single loop, as a loop pass)",
877                    false, false)
878
879FunctionPass *llvm::createGuardWideningPass() {
880  return new GuardWideningLegacyPass();
881}
882
883Pass *llvm::createLoopGuardWideningPass() {
884  return new LoopGuardWideningLegacyPass();
885}
886