Coverage Report

Created: 2019-07-24 05:18

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