Coverage Report

Created: 2017-10-03 07:32

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