Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/Transforms/Scalar/LoopPredication.cpp
Line
Count
Source (jump to first uncovered line)
1
//===-- LoopPredication.cpp - Guard based loop predication pass -----------===//
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
// The LoopPredication pass tries to convert loop variant range checks to loop
10
// invariant by widening checks across loop iterations. For example, it will
11
// convert
12
//
13
//   for (i = 0; i < n; i++) {
14
//     guard(i < len);
15
//     ...
16
//   }
17
//
18
// to
19
//
20
//   for (i = 0; i < n; i++) {
21
//     guard(n - 1 < len);
22
//     ...
23
//   }
24
//
25
// After this transformation the condition of the guard is loop invariant, so
26
// loop-unswitch can later unswitch the loop by this condition which basically
27
// predicates the loop by the widened condition:
28
//
29
//   if (n - 1 < len)
30
//     for (i = 0; i < n; i++) {
31
//       ...
32
//     }
33
//   else
34
//     deoptimize
35
//
36
// It's tempting to rely on SCEV here, but it has proven to be problematic.
37
// Generally the facts SCEV provides about the increment step of add
38
// recurrences are true if the backedge of the loop is taken, which implicitly
39
// assumes that the guard doesn't fail. Using these facts to optimize the
40
// guard results in a circular logic where the guard is optimized under the
41
// assumption that it never fails.
42
//
43
// For example, in the loop below the induction variable will be marked as nuw
44
// basing on the guard. Basing on nuw the guard predicate will be considered
45
// monotonic. Given a monotonic condition it's tempting to replace the induction
46
// variable in the condition with its value on the last iteration. But this
47
// transformation is not correct, e.g. e = 4, b = 5 breaks the loop.
48
//
49
//   for (int i = b; i != e; i++)
50
//     guard(i u< len)
51
//
52
// One of the ways to reason about this problem is to use an inductive proof
53
// approach. Given the loop:
54
//
55
//   if (B(0)) {
56
//     do {
57
//       I = PHI(0, I.INC)
58
//       I.INC = I + Step
59
//       guard(G(I));
60
//     } while (B(I));
61
//   }
62
//
63
// where B(x) and G(x) are predicates that map integers to booleans, we want a
64
// loop invariant expression M such the following program has the same semantics
65
// as the above:
66
//
67
//   if (B(0)) {
68
//     do {
69
//       I = PHI(0, I.INC)
70
//       I.INC = I + Step
71
//       guard(G(0) && M);
72
//     } while (B(I));
73
//   }
74
//
75
// One solution for M is M = forall X . (G(X) && B(X)) => G(X + Step)
76
//
77
// Informal proof that the transformation above is correct:
78
//
79
//   By the definition of guards we can rewrite the guard condition to:
80
//     G(I) && G(0) && M
81
//
82
//   Let's prove that for each iteration of the loop:
83
//     G(0) && M => G(I)
84
//   And the condition above can be simplified to G(Start) && M.
85
//
86
//   Induction base.
87
//     G(0) && M => G(0)
88
//
89
//   Induction step. Assuming G(0) && M => G(I) on the subsequent
90
//   iteration:
91
//
92
//     B(I) is true because it's the backedge condition.
93
//     G(I) is true because the backedge is guarded by this condition.
94
//
95
//   So M = forall X . (G(X) && B(X)) => G(X + Step) implies G(I + Step).
96
//
97
// Note that we can use anything stronger than M, i.e. any condition which
98
// implies M.
99
//
100
// When S = 1 (i.e. forward iterating loop), the transformation is supported
101
// when:
102
//   * The loop has a single latch with the condition of the form:
103
//     B(X) = latchStart + X <pred> latchLimit,
104
//     where <pred> is u<, u<=, s<, or s<=.
105
//   * The guard condition is of the form
106
//     G(X) = guardStart + X u< guardLimit
107
//
108
//   For the ult latch comparison case M is:
109
//     forall X . guardStart + X u< guardLimit && latchStart + X <u latchLimit =>
110
//        guardStart + X + 1 u< guardLimit
111
//
112
//   The only way the antecedent can be true and the consequent can be false is
113
//   if
114
//     X == guardLimit - 1 - guardStart
115
//   (and guardLimit is non-zero, but we won't use this latter fact).
116
//   If X == guardLimit - 1 - guardStart then the second half of the antecedent is
117
//     latchStart + guardLimit - 1 - guardStart u< latchLimit
118
//   and its negation is
119
//     latchStart + guardLimit - 1 - guardStart u>= latchLimit
120
//
121
//   In other words, if
122
//     latchLimit u<= latchStart + guardLimit - 1 - guardStart
123
//   then:
124
//   (the ranges below are written in ConstantRange notation, where [A, B) is the
125
//   set for (I = A; I != B; I++ /*maywrap*/) yield(I);)
126
//
127
//      forall X . guardStart + X u< guardLimit &&
128
//                 latchStart + X u< latchLimit =>
129
//        guardStart + X + 1 u< guardLimit
130
//   == forall X . guardStart + X u< guardLimit &&
131
//                 latchStart + X u< latchStart + guardLimit - 1 - guardStart =>
132
//        guardStart + X + 1 u< guardLimit
133
//   == forall X . (guardStart + X) in [0, guardLimit) &&
134
//                 (latchStart + X) in [0, latchStart + guardLimit - 1 - guardStart) =>
135
//        (guardStart + X + 1) in [0, guardLimit)
136
//   == forall X . X in [-guardStart, guardLimit - guardStart) &&
137
//                 X in [-latchStart, guardLimit - 1 - guardStart) =>
138
//         X in [-guardStart - 1, guardLimit - guardStart - 1)
139
//   == true
140
//
141
//   So the widened condition is:
142
//     guardStart u< guardLimit &&
143
//     latchStart + guardLimit - 1 - guardStart u>= latchLimit
144
//   Similarly for ule condition the widened condition is:
145
//     guardStart u< guardLimit &&
146
//     latchStart + guardLimit - 1 - guardStart u> latchLimit
147
//   For slt condition the widened condition is:
148
//     guardStart u< guardLimit &&
149
//     latchStart + guardLimit - 1 - guardStart s>= latchLimit
150
//   For sle condition the widened condition is:
151
//     guardStart u< guardLimit &&
152
//     latchStart + guardLimit - 1 - guardStart s> latchLimit
153
//
154
// When S = -1 (i.e. reverse iterating loop), the transformation is supported
155
// when:
156
//   * The loop has a single latch with the condition of the form:
157
//     B(X) = X <pred> latchLimit, where <pred> is u>, u>=, s>, or s>=.
158
//   * The guard condition is of the form
159
//     G(X) = X - 1 u< guardLimit
160
//
161
//   For the ugt latch comparison case M is:
162
//     forall X. X-1 u< guardLimit and X u> latchLimit => X-2 u< guardLimit
163
//
164
//   The only way the antecedent can be true and the consequent can be false is if
165
//     X == 1.
166
//   If X == 1 then the second half of the antecedent is
167
//     1 u> latchLimit, and its negation is latchLimit u>= 1.
168
//
169
//   So the widened condition is:
170
//     guardStart u< guardLimit && latchLimit u>= 1.
171
//   Similarly for sgt condition the widened condition is:
172
//     guardStart u< guardLimit && latchLimit s>= 1.
173
//   For uge condition the widened condition is:
174
//     guardStart u< guardLimit && latchLimit u> 1.
175
//   For sge condition the widened condition is:
176
//     guardStart u< guardLimit && latchLimit s> 1.
177
//===----------------------------------------------------------------------===//
178
179
#include "llvm/Transforms/Scalar/LoopPredication.h"
180
#include "llvm/ADT/Statistic.h"
181
#include "llvm/Analysis/AliasAnalysis.h"
182
#include "llvm/Analysis/BranchProbabilityInfo.h"
183
#include "llvm/Analysis/GuardUtils.h"
184
#include "llvm/Analysis/LoopInfo.h"
185
#include "llvm/Analysis/LoopPass.h"
186
#include "llvm/Analysis/ScalarEvolution.h"
187
#include "llvm/Analysis/ScalarEvolutionExpander.h"
188
#include "llvm/Analysis/ScalarEvolutionExpressions.h"
189
#include "llvm/IR/Function.h"
190
#include "llvm/IR/GlobalValue.h"
191
#include "llvm/IR/IntrinsicInst.h"
192
#include "llvm/IR/Module.h"
193
#include "llvm/IR/PatternMatch.h"
194
#include "llvm/Pass.h"
195
#include "llvm/Support/Debug.h"
196
#include "llvm/Transforms/Scalar.h"
197
#include "llvm/Transforms/Utils/Local.h"
198
#include "llvm/Transforms/Utils/LoopUtils.h"
199
200
#define DEBUG_TYPE "loop-predication"
201
202
STATISTIC(TotalConsidered, "Number of guards considered");
203
STATISTIC(TotalWidened, "Number of checks widened");
204
205
using namespace llvm;
206
207
static cl::opt<bool> EnableIVTruncation("loop-predication-enable-iv-truncation",
208
                                        cl::Hidden, cl::init(true));
209
210
static cl::opt<bool> EnableCountDownLoop("loop-predication-enable-count-down-loop",
211
                                        cl::Hidden, cl::init(true));
212
213
static cl::opt<bool>
214
    SkipProfitabilityChecks("loop-predication-skip-profitability-checks",
215
                            cl::Hidden, cl::init(false));
216
217
// This is the scale factor for the latch probability. We use this during
218
// profitability analysis to find other exiting blocks that have a much higher
219
// probability of exiting the loop instead of loop exiting via latch.
220
// This value should be greater than 1 for a sane profitability check.
221
static cl::opt<float> LatchExitProbabilityScale(
222
    "loop-predication-latch-probability-scale", cl::Hidden, cl::init(2.0),
223
    cl::desc("scale factor for the latch probability. Value should be greater "
224
             "than 1. Lower values are ignored"));
225
226
static cl::opt<bool> PredicateWidenableBranchGuards(
227
    "loop-predication-predicate-widenable-branches-to-deopt", cl::Hidden,
228
    cl::desc("Whether or not we should predicate guards "
229
             "expressed as widenable branches to deoptimize blocks"),
230
    cl::init(true));
231
232
namespace {
233
/// Represents an induction variable check:
234
///   icmp Pred, <induction variable>, <loop invariant limit>
235
struct LoopICmp {
236
  ICmpInst::Predicate Pred;
237
  const SCEVAddRecExpr *IV;
238
  const SCEV *Limit;
239
  LoopICmp(ICmpInst::Predicate Pred, const SCEVAddRecExpr *IV,
240
           const SCEV *Limit)
241
420
    : Pred(Pred), IV(IV), Limit(Limit) {}
242
212
  LoopICmp() {}
243
0
  void dump() {
244
0
    dbgs() << "LoopICmp Pred = " << Pred << ", IV = " << *IV
245
0
           << ", Limit = " << *Limit << "\n";
246
0
  }
247
};
248
249
class LoopPredication {
250
  AliasAnalysis *AA;
251
  ScalarEvolution *SE;
252
  BranchProbabilityInfo *BPI;
253
254
  Loop *L;
255
  const DataLayout *DL;
256
  BasicBlock *Preheader;
257
  LoopICmp LatchCheck;
258
259
  bool isSupportedStep(const SCEV* Step);
260
  Optional<LoopICmp> parseLoopICmp(ICmpInst *ICI);
261
  Optional<LoopICmp> parseLoopLatchICmp();
262
263
  /// Return an insertion point suitable for inserting a safe to speculate
264
  /// instruction whose only user will be 'User' which has operands 'Ops'.  A
265
  /// trivial result would be the at the User itself, but we try to return a
266
  /// loop invariant location if possible.  
267
  Instruction *findInsertPt(Instruction *User, ArrayRef<Value*> Ops);
268
  /// Same as above, *except* that this uses the SCEV definition of invariant
269
  /// which is that an expression *can be made* invariant via SCEVExpander.
270
  /// Thus, this version is only suitable for finding an insert point to be be
271
  /// passed to SCEVExpander!
272
  Instruction *findInsertPt(Instruction *User, ArrayRef<const SCEV*> Ops);
273
274
  /// Return true if the value is known to produce a single fixed value across
275
  /// all iterations on which it executes.  Note that this does not imply
276
  /// speculation safety.  That must be established seperately.  
277
  bool isLoopInvariantValue(const SCEV* S);
278
279
  Value *expandCheck(SCEVExpander &Expander, Instruction *Guard,
280
                     ICmpInst::Predicate Pred, const SCEV *LHS,
281
                     const SCEV *RHS);
282
283
  Optional<Value *> widenICmpRangeCheck(ICmpInst *ICI, SCEVExpander &Expander,
284
                                        Instruction *Guard);
285
  Optional<Value *> widenICmpRangeCheckIncrementingLoop(LoopICmp LatchCheck,
286
                                                        LoopICmp RangeCheck,
287
                                                        SCEVExpander &Expander,
288
                                                        Instruction *Guard);
289
  Optional<Value *> widenICmpRangeCheckDecrementingLoop(LoopICmp LatchCheck,
290
                                                        LoopICmp RangeCheck,
291
                                                        SCEVExpander &Expander,
292
                                                        Instruction *Guard);
293
  unsigned collectChecks(SmallVectorImpl<Value *> &Checks, Value *Condition,
294
                         SCEVExpander &Expander, Instruction *Guard);
295
  bool widenGuardConditions(IntrinsicInst *II, SCEVExpander &Expander);
296
  bool widenWidenableBranchGuardConditions(BranchInst *Guard, SCEVExpander &Expander);
297
  // If the loop always exits through another block in the loop, we should not
298
  // predicate based on the latch check. For example, the latch check can be a
299
  // very coarse grained check and there can be more fine grained exit checks
300
  // within the loop. We identify such unprofitable loops through BPI.
301
  bool isLoopProfitableToPredicate();
302
303
public:
304
  LoopPredication(AliasAnalysis *AA, ScalarEvolution *SE,
305
                  BranchProbabilityInfo *BPI)
306
208
    : AA(AA), SE(SE), BPI(BPI){};
307
  bool runOnLoop(Loop *L);
308
};
309
310
class LoopPredicationLegacyPass : public LoopPass {
311
public:
312
  static char ID;
313
8
  LoopPredicationLegacyPass() : LoopPass(ID) {
314
8
    initializeLoopPredicationLegacyPassPass(*PassRegistry::getPassRegistry());
315
8
  }
316
317
8
  void getAnalysisUsage(AnalysisUsage &AU) const override {
318
8
    AU.addRequired<BranchProbabilityInfoWrapperPass>();
319
8
    getLoopAnalysisUsage(AU);
320
8
  }
321
322
92
  bool runOnLoop(Loop *L, LPPassManager &LPM) override {
323
92
    if (skipLoop(L))
324
0
      return false;
325
92
    auto *SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
326
92
    BranchProbabilityInfo &BPI =
327
92
        getAnalysis<BranchProbabilityInfoWrapperPass>().getBPI();
328
92
    auto *AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
329
92
    LoopPredication LP(AA, SE, &BPI);
330
92
    return LP.runOnLoop(L);
331
92
  }
332
};
333
334
char LoopPredicationLegacyPass::ID = 0;
335
} // end namespace llvm
336
337
36.0k
INITIALIZE_PASS_BEGIN(LoopPredicationLegacyPass, "loop-predication",
338
36.0k
                      "Loop predication", false, false)
339
36.0k
INITIALIZE_PASS_DEPENDENCY(BranchProbabilityInfoWrapperPass)
340
36.0k
INITIALIZE_PASS_DEPENDENCY(LoopPass)
341
36.0k
INITIALIZE_PASS_END(LoopPredicationLegacyPass, "loop-predication",
342
                    "Loop predication", false, false)
343
344
0
Pass *llvm::createLoopPredicationPass() {
345
0
  return new LoopPredicationLegacyPass();
346
0
}
347
348
PreservedAnalyses LoopPredicationPass::run(Loop &L, LoopAnalysisManager &AM,
349
                                           LoopStandardAnalysisResults &AR,
350
116
                                           LPMUpdater &U) {
351
116
  const auto &FAM =
352
116
      AM.getResult<FunctionAnalysisManagerLoopProxy>(L, AR).getManager();
353
116
  Function *F = L.getHeader()->getParent();
354
116
  auto *BPI = FAM.getCachedResult<BranchProbabilityAnalysis>(*F);
355
116
  LoopPredication LP(&AR.AA, &AR.SE, BPI);
356
116
  if (!LP.runOnLoop(&L))
357
39
    return PreservedAnalyses::all();
358
77
359
77
  return getLoopPassPreservedAnalyses();
360
77
}
361
362
Optional<LoopICmp>
363
435
LoopPredication::parseLoopICmp(ICmpInst *ICI) {
364
435
  auto Pred = ICI->getPredicate();
365
435
  auto *LHS = ICI->getOperand(0);
366
435
  auto *RHS = ICI->getOperand(1);
367
435
368
435
  const SCEV *LHSS = SE->getSCEV(LHS);
369
435
  if (isa<SCEVCouldNotCompute>(LHSS))
370
0
    return None;
371
435
  const SCEV *RHSS = SE->getSCEV(RHS);
372
435
  if (isa<SCEVCouldNotCompute>(RHSS))
373
0
    return None;
374
435
375
435
  // Canonicalize RHS to be loop invariant bound, LHS - a loop computable IV
376
435
  if (SE->isLoopInvariant(LHSS, L)) {
377
35
    std::swap(LHS, RHS);
378
35
    std::swap(LHSS, RHSS);
379
35
    Pred = ICmpInst::getSwappedPredicate(Pred);
380
35
  }
381
435
382
435
  const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(LHSS);
383
435
  if (!AR || 
AR->getLoop() != L422
)
384
15
    return None;
385
420
386
420
  return LoopICmp(Pred, AR, RHSS);
387
420
}
388
389
Value *LoopPredication::expandCheck(SCEVExpander &Expander,
390
                                    Instruction *Guard, 
391
                                    ICmpInst::Predicate Pred, const SCEV *LHS,
392
330
                                    const SCEV *RHS) {
393
330
  Type *Ty = LHS->getType();
394
330
  assert(Ty == RHS->getType() && "expandCheck operands have different types?");
395
330
396
330
  if (SE->isLoopInvariant(LHS, L) && SE->isLoopInvariant(RHS, L)) {
397
322
    IRBuilder<> Builder(Guard);
398
322
    if (SE->isLoopEntryGuardedByCond(L, Pred, LHS, RHS))
399
7
      return Builder.getTrue();
400
315
    if (SE->isLoopEntryGuardedByCond(L, ICmpInst::getInversePredicate(Pred),
401
315
                                     LHS, RHS))
402
6
      return Builder.getFalse();
403
317
  }
404
317
405
317
  Value *LHSV = Expander.expandCodeFor(LHS, Ty, findInsertPt(Guard, {LHS}));
406
317
  Value *RHSV = Expander.expandCodeFor(RHS, Ty, findInsertPt(Guard, {RHS}));
407
317
  IRBuilder<> Builder(findInsertPt(Guard, {LHSV, RHSV}));
408
317
  return Builder.CreateICmp(Pred, LHSV, RHSV);
409
317
}
410
411
412
// Returns true if its safe to truncate the IV to RangeCheckType.
413
// When the IV type is wider than the range operand type, we can still do loop
414
// predication, by generating SCEVs for the range and latch that are of the
415
// same type. We achieve this by generating a SCEV truncate expression for the
416
// latch IV. This is done iff truncation of the IV is a safe operation,
417
// without loss of information.
418
// Another way to achieve this is by generating a wider type SCEV for the
419
// range check operand, however, this needs a more involved check that
420
// operands do not overflow. This can lead to loss of information when the
421
// range operand is of the form: add i32 %offset, %iv. We need to prove that
422
// sext(x + y) is same as sext(x) + sext(y).
423
// This function returns true if we can safely represent the IV type in
424
// the RangeCheckType without loss of information.
425
static bool isSafeToTruncateWideIVType(const DataLayout &DL,
426
                                       ScalarEvolution &SE,
427
                                       const LoopICmp LatchCheck,
428
9
                                       Type *RangeCheckType) {
429
9
  if (!EnableIVTruncation)
430
0
    return false;
431
9
  assert(DL.getTypeSizeInBits(LatchCheck.IV->getType()) >
432
9
             DL.getTypeSizeInBits(RangeCheckType) &&
433
9
         "Expected latch check IV type to be larger than range check operand "
434
9
         "type!");
435
9
  // The start and end values of the IV should be known. This is to guarantee
436
9
  // that truncating the wide type will not lose information.
437
9
  auto *Limit = dyn_cast<SCEVConstant>(LatchCheck.Limit);
438
9
  auto *Start = dyn_cast<SCEVConstant>(LatchCheck.IV->getStart());
439
9
  if (!Limit || 
!Start4
)
440
5
    return false;
441
4
  // This check makes sure that the IV does not change sign during loop
442
4
  // iterations. Consider latchType = i64, LatchStart = 5, Pred = ICMP_SGE,
443
4
  // LatchEnd = 2, rangeCheckType = i32. If it's not a monotonic predicate, the
444
4
  // IV wraps around, and the truncation of the IV would lose the range of
445
4
  // iterations between 2^32 and 2^64.
446
4
  bool Increasing;
447
4
  if (!SE.isMonotonicPredicate(LatchCheck.IV, LatchCheck.Pred, Increasing))
448
0
    return false;
449
4
  // The active bits should be less than the bits in the RangeCheckType. This
450
4
  // guarantees that truncating the latch check to RangeCheckType is a safe
451
4
  // operation.
452
4
  auto RangeCheckTypeBitSize = DL.getTypeSizeInBits(RangeCheckType);
453
4
  return Start->getAPInt().getActiveBits() < RangeCheckTypeBitSize &&
454
4
         Limit->getAPInt().getActiveBits() < RangeCheckTypeBitSize;
455
4
}
456
457
458
// Return an LoopICmp describing a latch check equivlent to LatchCheck but with
459
// the requested type if safe to do so.  May involve the use of a new IV.
460
static Optional<LoopICmp> generateLoopLatchCheck(const DataLayout &DL,
461
                                                 ScalarEvolution &SE,
462
                                                 const LoopICmp LatchCheck,
463
187
                                                 Type *RangeCheckType) {
464
187
465
187
  auto *LatchType = LatchCheck.IV->getType();
466
187
  if (RangeCheckType == LatchType)
467
178
    return LatchCheck;
468
9
  // For now, bail out if latch type is narrower than range type.
469
9
  if (DL.getTypeSizeInBits(LatchType) < DL.getTypeSizeInBits(RangeCheckType))
470
0
    return None;
471
9
  if (!isSafeToTruncateWideIVType(DL, SE, LatchCheck, RangeCheckType))
472
5
    return None;
473
4
  // We can now safely identify the truncated version of the IV and limit for
474
4
  // RangeCheckType.
475
4
  LoopICmp NewLatchCheck;
476
4
  NewLatchCheck.Pred = LatchCheck.Pred;
477
4
  NewLatchCheck.IV = dyn_cast<SCEVAddRecExpr>(
478
4
      SE.getTruncateExpr(LatchCheck.IV, RangeCheckType));
479
4
  if (!NewLatchCheck.IV)
480
0
    return None;
481
4
  NewLatchCheck.Limit = SE.getTruncateExpr(LatchCheck.Limit, RangeCheckType);
482
4
  LLVM_DEBUG(dbgs() << "IV of type: " << *LatchType
483
4
                    << "can be represented as range check type:"
484
4
                    << *RangeCheckType << "\n");
485
4
  LLVM_DEBUG(dbgs() << "LatchCheck.IV: " << *NewLatchCheck.IV << "\n");
486
4
  LLVM_DEBUG(dbgs() << "LatchCheck.Limit: " << *NewLatchCheck.Limit << "\n");
487
4
  return NewLatchCheck;
488
4
}
489
490
398
bool LoopPredication::isSupportedStep(const SCEV* Step) {
491
398
  return Step->isOne() || 
(40
Step->isAllOnesValue()40
&&
EnableCountDownLoop26
);
492
398
}
493
494
Instruction *LoopPredication::findInsertPt(Instruction *Use,
495
629
                                           ArrayRef<Value*> Ops) {
496
629
  for (Value *Op : Ops)
497
1.17k
    if (!L->isLoopInvariant(Op))
498
102
      return Use;
499
629
  
return Preheader->getTerminator()527
;
500
629
}
501
502
Instruction *LoopPredication::findInsertPt(Instruction *Use,
503
634
                                           ArrayRef<const SCEV*> Ops) {
504
634
  // Subtlety: SCEV considers things to be invariant if the value produced is
505
634
  // the same across iterations.  This is not the same as being able to
506
634
  // evaluate outside the loop, which is what we actually need here.
507
634
  for (const SCEV *Op : Ops)
508
634
    if (!SE->isLoopInvariant(Op, L) ||
509
634
        
!isSafeToExpandAt(Op, Preheader->getTerminator(), *SE)626
)
510
18
      return Use;
511
634
  
return Preheader->getTerminator()616
;
512
634
}
513
514
702
bool LoopPredication::isLoopInvariantValue(const SCEV* S) { 
515
702
  // Handling expressions which produce invariant results, but *haven't* yet
516
702
  // been removed from the loop serves two important purposes.
517
702
  // 1) Most importantly, it resolves a pass ordering cycle which would
518
702
  // otherwise need us to iteration licm, loop-predication, and either
519
702
  // loop-unswitch or loop-peeling to make progress on examples with lots of
520
702
  // predicable range checks in a row.  (Since, in the general case,  we can't
521
702
  // hoist the length checks until the dominating checks have been discharged
522
702
  // as we can't prove doing so is safe.)
523
702
  // 2) As a nice side effect, this exposes the value of peeling or unswitching
524
702
  // much more obviously in the IR.  Otherwise, the cost modeling for other
525
702
  // transforms would end up needing to duplicate all of this logic to model a
526
702
  // check which becomes predictable based on a modeled peel or unswitch.
527
702
  // 
528
702
  // The cost of doing so in the worst case is an extra fill from the stack  in
529
702
  // the loop to materialize the loop invariant test value instead of checking
530
702
  // against the original IV which is presumable in a register inside the loop.
531
702
  // Such cases are presumably rare, and hint at missing oppurtunities for
532
702
  // other passes. 
533
702
534
702
  if (SE->isLoopInvariant(S, L))
535
685
    // Note: This the SCEV variant, so the original Value* may be within the
536
685
    // loop even though SCEV has proven it is loop invariant.
537
685
    return true;
538
17
539
17
  // Handle a particular important case which SCEV doesn't yet know about which
540
17
  // shows up in range checks on arrays with immutable lengths.  
541
17
  // TODO: This should be sunk inside SCEV.
542
17
  if (const SCEVUnknown *U = dyn_cast<SCEVUnknown>(S))
543
12
    if (const auto *LI = dyn_cast<LoadInst>(U->getValue()))
544
12
      if (LI->isUnordered() && L->hasLoopInvariantOperands(LI))
545
10
        if (AA->pointsToConstantMemory(LI->getOperand(0)) ||
546
10
            
LI->getMetadata(LLVMContext::MD_invariant_load) != nullptr8
)
547
8
          return true;
548
9
  return false;
549
9
}
550
551
Optional<Value *> LoopPredication::widenICmpRangeCheckIncrementingLoop(
552
    LoopICmp LatchCheck, LoopICmp RangeCheck,
553
168
    SCEVExpander &Expander, Instruction *Guard) {
554
168
  auto *Ty = RangeCheck.IV->getType();
555
168
  // Generate the widened condition for the forward loop:
556
168
  //   guardStart u< guardLimit &&
557
168
  //   latchLimit <pred> guardLimit - 1 - guardStart + latchStart
558
168
  // where <pred> depends on the latch condition predicate. See the file
559
168
  // header comment for the reasoning.
560
168
  // guardLimit - guardStart + latchStart - 1
561
168
  const SCEV *GuardStart = RangeCheck.IV->getStart();
562
168
  const SCEV *GuardLimit = RangeCheck.Limit;
563
168
  const SCEV *LatchStart = LatchCheck.IV->getStart();
564
168
  const SCEV *LatchLimit = LatchCheck.Limit;
565
168
  // Subtlety: We need all the values to be *invariant* across all iterations,
566
168
  // but we only need to check expansion safety for those which *aren't*
567
168
  // already guaranteed to dominate the guard.  
568
168
  if (!isLoopInvariantValue(GuardStart) ||
569
168
      !isLoopInvariantValue(GuardLimit) ||
570
168
      
!isLoopInvariantValue(LatchStart)159
||
571
168
      
!isLoopInvariantValue(LatchLimit)159
) {
572
9
    LLVM_DEBUG(dbgs() << "Can't expand limit check!\n");
573
9
    return None;
574
9
  }
575
159
  if (!isSafeToExpandAt(LatchStart, Guard, *SE) ||
576
159
      
!isSafeToExpandAt(LatchLimit, Guard, *SE)157
) {
577
6
    LLVM_DEBUG(dbgs() << "Can't expand limit check!\n");
578
6
    return None;
579
6
  }
580
153
581
153
  // guardLimit - guardStart + latchStart - 1
582
153
  const SCEV *RHS =
583
153
      SE->getAddExpr(SE->getMinusSCEV(GuardLimit, GuardStart),
584
153
                     SE->getMinusSCEV(LatchStart, SE->getOne(Ty)));
585
153
  auto LimitCheckPred =
586
153
      ICmpInst::getFlippedStrictnessPredicate(LatchCheck.Pred);
587
153
588
153
  LLVM_DEBUG(dbgs() << "LHS: " << *LatchLimit << "\n");
589
153
  LLVM_DEBUG(dbgs() << "RHS: " << *RHS << "\n");
590
153
  LLVM_DEBUG(dbgs() << "Pred: " << LimitCheckPred << "\n");
591
153
 
592
153
  auto *LimitCheck =
593
153
      expandCheck(Expander, Guard, LimitCheckPred, LatchLimit, RHS);
594
153
  auto *FirstIterationCheck = expandCheck(Expander, Guard, RangeCheck.Pred,
595
153
                                          GuardStart, GuardLimit);
596
153
  IRBuilder<> Builder(findInsertPt(Guard, {FirstIterationCheck, LimitCheck}));
597
153
  return Builder.CreateAnd(FirstIterationCheck, LimitCheck);
598
153
}
599
600
Optional<Value *> LoopPredication::widenICmpRangeCheckDecrementingLoop(
601
    LoopICmp LatchCheck, LoopICmp RangeCheck,
602
12
    SCEVExpander &Expander, Instruction *Guard) {
603
12
  auto *Ty = RangeCheck.IV->getType();
604
12
  const SCEV *GuardStart = RangeCheck.IV->getStart();
605
12
  const SCEV *GuardLimit = RangeCheck.Limit;
606
12
  const SCEV *LatchStart = LatchCheck.IV->getStart();
607
12
  const SCEV *LatchLimit = LatchCheck.Limit;
608
12
  // Subtlety: We need all the values to be *invariant* across all iterations,
609
12
  // but we only need to check expansion safety for those which *aren't*
610
12
  // already guaranteed to dominate the guard.  
611
12
  if (!isLoopInvariantValue(GuardStart) ||
612
12
      !isLoopInvariantValue(GuardLimit) ||
613
12
      !isLoopInvariantValue(LatchStart) ||
614
12
      !isLoopInvariantValue(LatchLimit)) {
615
0
    LLVM_DEBUG(dbgs() << "Can't expand limit check!\n");
616
0
    return None;
617
0
  }
618
12
  if (!isSafeToExpandAt(LatchStart, Guard, *SE) ||
619
12
      !isSafeToExpandAt(LatchLimit, Guard, *SE)) {
620
0
    LLVM_DEBUG(dbgs() << "Can't expand limit check!\n");
621
0
    return None;
622
0
  }
623
12
  // The decrement of the latch check IV should be the same as the
624
12
  // rangeCheckIV.
625
12
  auto *PostDecLatchCheckIV = LatchCheck.IV->getPostIncExpr(*SE);
626
12
  if (RangeCheck.IV != PostDecLatchCheckIV) {
627
0
    LLVM_DEBUG(dbgs() << "Not the same. PostDecLatchCheckIV: "
628
0
                      << *PostDecLatchCheckIV
629
0
                      << "  and RangeCheckIV: " << *RangeCheck.IV << "\n");
630
0
    return None;
631
0
  }
632
12
633
12
  // Generate the widened condition for CountDownLoop:
634
12
  // guardStart u< guardLimit &&
635
12
  // latchLimit <pred> 1.
636
12
  // See the header comment for reasoning of the checks.
637
12
  auto LimitCheckPred =
638
12
      ICmpInst::getFlippedStrictnessPredicate(LatchCheck.Pred);
639
12
  auto *FirstIterationCheck = expandCheck(Expander, Guard,
640
12
                                          ICmpInst::ICMP_ULT,
641
12
                                          GuardStart, GuardLimit);
642
12
  auto *LimitCheck = expandCheck(Expander, Guard, LimitCheckPred, LatchLimit,
643
12
                                 SE->getOne(Ty));
644
12
  IRBuilder<> Builder(findInsertPt(Guard, {FirstIterationCheck, LimitCheck}));
645
12
  return Builder.CreateAnd(FirstIterationCheck, LimitCheck);
646
12
}
647
648
static void normalizePredicate(ScalarEvolution *SE, Loop *L,
649
197
                               LoopICmp& RC) {
650
197
  // LFTR canonicalizes checks to the ICMP_NE/EQ form; normalize back to the
651
197
  // ULT/UGE form for ease of handling by our caller. 
652
197
  if (ICmpInst::isEquality(RC.Pred) &&
653
197
      
RC.IV->getStepRecurrence(*SE)->isOne()17
&&
654
197
      
SE->isKnownPredicate(ICmpInst::ICMP_ULE, RC.IV->getStart(), RC.Limit)17
)
655
8
    RC.Pred = RC.Pred == ICmpInst::ICMP_NE ?
656
8
      ICmpInst::ICMP_ULT : 
ICmpInst::ICMP_UGE0
;
657
197
}
658
659
660
/// If ICI can be widened to a loop invariant condition emits the loop
661
/// invariant condition in the loop preheader and return it, otherwise
662
/// returns None.
663
Optional<Value *> LoopPredication::widenICmpRangeCheck(ICmpInst *ICI,
664
                                                       SCEVExpander &Expander,
665
229
                                                       Instruction *Guard) {
666
229
  LLVM_DEBUG(dbgs() << "Analyzing ICmpInst condition:\n");
667
229
  LLVM_DEBUG(ICI->dump());
668
229
669
229
  // parseLoopStructure guarantees that the latch condition is:
670
229
  //   ++i <pred> latchLimit, where <pred> is u<, u<=, s<, or s<=.
671
229
  // We are looking for the range checks of the form:
672
229
  //   i u< guardLimit
673
229
  auto RangeCheck = parseLoopICmp(ICI);
674
229
  if (!RangeCheck) {
675
15
    LLVM_DEBUG(dbgs() << "Failed to parse the loop latch condition!\n");
676
15
    return None;
677
15
  }
678
214
  LLVM_DEBUG(dbgs() << "Guard check:\n");
679
214
  LLVM_DEBUG(RangeCheck->dump());
680
214
  if (RangeCheck->Pred != ICmpInst::ICMP_ULT) {
681
22
    LLVM_DEBUG(dbgs() << "Unsupported range check predicate("
682
22
                      << RangeCheck->Pred << ")!\n");
683
22
    return None;
684
22
  }
685
192
  auto *RangeCheckIV = RangeCheck->IV;
686
192
  if (!RangeCheckIV->isAffine()) {
687
0
    LLVM_DEBUG(dbgs() << "Range check IV is not affine!\n");
688
0
    return None;
689
0
  }
690
192
  auto *Step = RangeCheckIV->getStepRecurrence(*SE);
691
192
  // We cannot just compare with latch IV step because the latch and range IVs
692
192
  // may have different types.
693
192
  if (!isSupportedStep(Step)) {
694
5
    LLVM_DEBUG(dbgs() << "Range check and latch have IVs different steps!\n");
695
5
    return None;
696
5
  }
697
187
  auto *Ty = RangeCheckIV->getType();
698
187
  auto CurrLatchCheckOpt = generateLoopLatchCheck(*DL, *SE, LatchCheck, Ty);
699
187
  if (!CurrLatchCheckOpt) {
700
5
    LLVM_DEBUG(dbgs() << "Failed to generate a loop latch check "
701
5
                         "corresponding to range type: "
702
5
                      << *Ty << "\n");
703
5
    return None;
704
5
  }
705
182
706
182
  LoopICmp CurrLatchCheck = *CurrLatchCheckOpt;
707
182
  // At this point, the range and latch step should have the same type, but need
708
182
  // not have the same value (we support both 1 and -1 steps).
709
182
  assert(Step->getType() ==
710
182
             CurrLatchCheck.IV->getStepRecurrence(*SE)->getType() &&
711
182
         "Range and latch steps should be of same type!");
712
182
  if (Step != CurrLatchCheck.IV->getStepRecurrence(*SE)) {
713
2
    LLVM_DEBUG(dbgs() << "Range and latch have different step values!\n");
714
2
    return None;
715
2
  }
716
180
717
180
  if (Step->isOne())
718
168
    return widenICmpRangeCheckIncrementingLoop(CurrLatchCheck, *RangeCheck,
719
168
                                               Expander, Guard);
720
12
  else {
721
12
    assert(Step->isAllOnesValue() && "Step should be -1!");
722
12
    return widenICmpRangeCheckDecrementingLoop(CurrLatchCheck, *RangeCheck,
723
12
                                               Expander, Guard);
724
12
  }
725
180
}
726
727
unsigned LoopPredication::collectChecks(SmallVectorImpl<Value *> &Checks,
728
                                        Value *Condition,
729
                                        SCEVExpander &Expander,
730
204
                                        Instruction *Guard) {
731
204
  unsigned NumWidened = 0;
732
204
  // The guard condition is expected to be in form of:
733
204
  //   cond1 && cond2 && cond3 ...
734
204
  // Iterate over subconditions looking for icmp conditions which can be
735
204
  // widened across loop iterations. Widening these conditions remember the
736
204
  // resulting list of subconditions in Checks vector.
737
204
  SmallVector<Value *, 4> Worklist(1, Condition);
738
204
  SmallPtrSet<Value *, 4> Visited;
739
204
  Value *WideableCond = nullptr;
740
826
  do {
741
826
    Value *Condition = Worklist.pop_back_val();
742
826
    if (!Visited.insert(Condition).second)
743
194
      continue;
744
632
745
632
    Value *LHS, *RHS;
746
632
    using namespace llvm::PatternMatch;
747
632
    if (match(Condition, m_And(m_Value(LHS), m_Value(RHS)))) {
748
311
      Worklist.push_back(LHS);
749
311
      Worklist.push_back(RHS);
750
311
      continue;
751
311
    }
752
321
753
321
    if (match(Condition,
754
321
              m_Intrinsic<Intrinsic::experimental_widenable_condition>())) {
755
78
      // Pick any, we don't care which
756
78
      WideableCond = Condition;
757
78
      continue;
758
78
    }
759
243
760
243
    if (ICmpInst *ICI = dyn_cast<ICmpInst>(Condition)) {
761
229
      if (auto NewRangeCheck = widenICmpRangeCheck(ICI, Expander,
762
165
                                                   Guard)) {
763
165
        Checks.push_back(NewRangeCheck.getValue());
764
165
        NumWidened++;
765
165
        continue;
766
165
      }
767
78
    }
768
78
769
78
    // Save the condition as is if we can't widen it
770
78
    Checks.push_back(Condition);
771
826
  } while (!Worklist.empty());
772
204
  // At the moment, our matching logic for wideable conditions implicitly
773
204
  // assumes we preserve the form: (br (and Cond, WC())).  FIXME
774
204
  // Note that if there were multiple calls to wideable condition in the
775
204
  // traversal, we only need to keep one, and which one is arbitrary.
776
204
  if (WideableCond)
777
78
    Checks.push_back(WideableCond);
778
204
  return NumWidened;
779
204
}
780
781
bool LoopPredication::widenGuardConditions(IntrinsicInst *Guard,
782
126
                                           SCEVExpander &Expander) {
783
126
  LLVM_DEBUG(dbgs() << "Processing guard:\n");
784
126
  LLVM_DEBUG(Guard->dump());
785
126
786
126
  TotalConsidered++;
787
126
  SmallVector<Value *, 4> Checks;
788
126
  unsigned NumWidened = collectChecks(Checks, Guard->getOperand(0), Expander,
789
126
                                      Guard);
790
126
  if (NumWidened == 0)
791
42
    return false;
792
84
793
84
  TotalWidened += NumWidened;
794
84
795
84
  // Emit the new guard condition
796
84
  IRBuilder<> Builder(findInsertPt(Guard, Checks));
797
84
  Value *AllChecks = Builder.CreateAnd(Checks);
798
84
  auto *OldCond = Guard->getOperand(0);
799
84
  Guard->setOperand(0, AllChecks);
800
84
  RecursivelyDeleteTriviallyDeadInstructions(OldCond);
801
84
802
84
  LLVM_DEBUG(dbgs() << "Widened checks = " << NumWidened << "\n");
803
84
  return true;
804
84
}
805
806
bool LoopPredication::widenWidenableBranchGuardConditions(
807
78
    BranchInst *BI, SCEVExpander &Expander) {
808
78
  assert(isGuardAsWidenableBranch(BI) && "Must be!");
809
78
  LLVM_DEBUG(dbgs() << "Processing guard:\n");
810
78
  LLVM_DEBUG(BI->dump());
811
78
812
78
  TotalConsidered++;
813
78
  SmallVector<Value *, 4> Checks;
814
78
  unsigned NumWidened = collectChecks(Checks, BI->getCondition(),
815
78
                                      Expander, BI);
816
78
  if (NumWidened == 0)
817
15
    return false;
818
63
819
63
  TotalWidened += NumWidened;
820
63
821
63
  // Emit the new guard condition
822
63
  IRBuilder<> Builder(findInsertPt(BI, Checks));
823
63
  Value *AllChecks = Builder.CreateAnd(Checks);
824
63
  auto *OldCond = BI->getCondition();
825
63
  BI->setCondition(AllChecks);
826
63
  assert(isGuardAsWidenableBranch(BI) &&
827
63
         "Stopped being a guard after transform?");
828
63
  RecursivelyDeleteTriviallyDeadInstructions(OldCond);
829
63
830
63
  LLVM_DEBUG(dbgs() << "Widened checks = " << NumWidened << "\n");
831
63
  return true;
832
63
}
833
834
208
Optional<LoopICmp> LoopPredication::parseLoopLatchICmp() {
835
208
  using namespace PatternMatch;
836
208
837
208
  BasicBlock *LoopLatch = L->getLoopLatch();
838
208
  if (!LoopLatch) {
839
0
    LLVM_DEBUG(dbgs() << "The loop doesn't have a single latch!\n");
840
0
    return None;
841
0
  }
842
208
843
208
  auto *BI = dyn_cast<BranchInst>(LoopLatch->getTerminator());
844
208
  if (!BI || !BI->isConditional()) {
845
2
    LLVM_DEBUG(dbgs() << "Failed to match the latch terminator!\n");
846
2
    return None;
847
2
  }
848
206
  BasicBlock *TrueDest = BI->getSuccessor(0);
849
206
  assert(
850
206
      (TrueDest == L->getHeader() || BI->getSuccessor(1) == L->getHeader()) &&
851
206
      "One of the latch's destinations must be the header");
852
206
853
206
  auto *ICI = dyn_cast<ICmpInst>(BI->getCondition());
854
206
  if (!ICI) {
855
0
    LLVM_DEBUG(dbgs() << "Failed to match the latch condition!\n");
856
0
    return None;
857
0
  }
858
206
  auto Result = parseLoopICmp(ICI);
859
206
  if (!Result) {
860
0
    LLVM_DEBUG(dbgs() << "Failed to parse the loop latch condition!\n");
861
0
    return None;
862
0
  }
863
206
864
206
  if (TrueDest != L->getHeader())
865
7
    Result->Pred = ICmpInst::getInversePredicate(Result->Pred);
866
206
867
206
  // Check affine first, so if it's not we don't try to compute the step
868
206
  // recurrence.
869
206
  if (!Result->IV->isAffine()) {
870
0
    LLVM_DEBUG(dbgs() << "The induction variable is not affine!\n");
871
0
    return None;
872
0
  }
873
206
874
206
  auto *Step = Result->IV->getStepRecurrence(*SE);
875
206
  if (!isSupportedStep(Step)) {
876
9
    LLVM_DEBUG(dbgs() << "Unsupported loop stride(" << *Step << ")!\n");
877
9
    return None;
878
9
  }
879
197
880
197
  auto IsUnsupportedPredicate = [](const SCEV *Step, ICmpInst::Predicate Pred) {
881
197
    if (Step->isOne()) {
882
183
      return Pred != ICmpInst::ICMP_ULT && 
Pred != ICmpInst::ICMP_SLT103
&&
883
183
             
Pred != ICmpInst::ICMP_ULE35
&&
Pred != ICmpInst::ICMP_SLE30
;
884
183
    } else {
885
14
      assert(Step->isAllOnesValue() && "Step should be -1!");
886
14
      return Pred != ICmpInst::ICMP_UGT && 
Pred != ICmpInst::ICMP_SGT8
&&
887
14
             
Pred != ICmpInst::ICMP_UGE6
&&
Pred != ICmpInst::ICMP_SGE2
;
888
14
    }
889
197
  };
890
197
891
197
  normalizePredicate(SE, L, *Result);
892
197
  if (IsUnsupportedPredicate(Step, Result->Pred)) {
893
10
    LLVM_DEBUG(dbgs() << "Unsupported loop latch predicate(" << Result->Pred
894
10
                      << ")!\n");
895
10
    return None;
896
10
  }
897
187
898
187
  return Result;
899
187
}
900
901
902
187
bool LoopPredication::isLoopProfitableToPredicate() {
903
187
  if (SkipProfitabilityChecks || !BPI)
904
77
    return true;
905
110
906
110
  SmallVector<std::pair<BasicBlock *, BasicBlock *>, 8> ExitEdges;
907
110
  L->getExitEdges(ExitEdges);
908
110
  // If there is only one exiting edge in the loop, it is always profitable to
909
110
  // predicate the loop.
910
110
  if (ExitEdges.size() == 1)
911
54
    return true;
912
56
913
56
  // Calculate the exiting probabilities of all exiting edges from the loop,
914
56
  // starting with the LatchExitProbability.
915
56
  // Heuristic for profitability: If any of the exiting blocks' probability of
916
56
  // exiting the loop is larger than exiting through the latch block, it's not
917
56
  // profitable to predicate the loop.
918
56
  auto *LatchBlock = L->getLoopLatch();
919
56
  assert(LatchBlock && "Should have a single latch at this point!");
920
56
  auto *LatchTerm = LatchBlock->getTerminator();
921
56
  assert(LatchTerm->getNumSuccessors() == 2 &&
922
56
         "expected to be an exiting block with 2 succs!");
923
56
  unsigned LatchBrExitIdx =
924
56
      LatchTerm->getSuccessor(0) == L->getHeader() ? 
154
:
02
;
925
56
  BranchProbability LatchExitProbability =
926
56
      BPI->getEdgeProbability(LatchBlock, LatchBrExitIdx);
927
56
928
56
  // Protect against degenerate inputs provided by the user. Providing a value
929
56
  // less than one, can invert the definition of profitable loop predication.
930
56
  float ScaleFactor = LatchExitProbabilityScale;
931
56
  if (ScaleFactor < 1) {
932
0
    LLVM_DEBUG(
933
0
        dbgs()
934
0
        << "Ignored user setting for loop-predication-latch-probability-scale: "
935
0
        << LatchExitProbabilityScale << "\n");
936
0
    LLVM_DEBUG(dbgs() << "The value is set to 1.0\n");
937
0
    ScaleFactor = 1.0;
938
0
  }
939
56
  const auto LatchProbabilityThreshold =
940
56
      LatchExitProbability * ScaleFactor;
941
56
942
112
  for (const auto &ExitEdge : ExitEdges) {
943
112
    BranchProbability ExitingBlockProbability =
944
112
        BPI->getEdgeProbability(ExitEdge.first, ExitEdge.second);
945
112
    // Some exiting edge has higher probability than the latch exiting edge.
946
112
    // No longer profitable to predicate.
947
112
    if (ExitingBlockProbability > LatchProbabilityThreshold)
948
4
      return false;
949
112
  }
950
56
  // Using BPI, we have concluded that the most probable way to exit from the
951
56
  // loop is through the latch (or there's no profile information and all
952
56
  // exits are equally likely).
953
56
  
return true52
;
954
56
}
955
956
208
bool LoopPredication::runOnLoop(Loop *Loop) {
957
208
  L = Loop;
958
208
959
208
  LLVM_DEBUG(dbgs() << "Analyzing ");
960
208
  LLVM_DEBUG(L->dump());
961
208
962
208
  Module *M = L->getHeader()->getModule();
963
208
964
208
  // There is nothing to do if the module doesn't use guards
965
208
  auto *GuardDecl =
966
208
      M->getFunction(Intrinsic::getName(Intrinsic::experimental_guard));
967
208
  bool HasIntrinsicGuards = GuardDecl && !GuardDecl->use_empty();
968
208
  auto *WCDecl = M->getFunction(
969
208
      Intrinsic::getName(Intrinsic::experimental_widenable_condition));
970
208
  bool HasWidenableConditions =
971
208
      PredicateWidenableBranchGuards && WCDecl && 
!WCDecl->use_empty()81
;
972
208
  if (!HasIntrinsicGuards && 
!HasWidenableConditions81
)
973
0
    return false;
974
208
975
208
  DL = &M->getDataLayout();
976
208
977
208
  Preheader = L->getLoopPreheader();
978
208
  if (!Preheader)
979
0
    return false;
980
208
981
208
  auto LatchCheckOpt = parseLoopLatchICmp();
982
208
  if (!LatchCheckOpt)
983
21
    return false;
984
187
  LatchCheck = *LatchCheckOpt;
985
187
986
187
  LLVM_DEBUG(dbgs() << "Latch check:\n");
987
187
  LLVM_DEBUG(LatchCheck.dump());
988
187
989
187
  if (!isLoopProfitableToPredicate()) {
990
4
    LLVM_DEBUG(dbgs() << "Loop not profitable to predicate!\n");
991
4
    return false;
992
4
  }
993
183
  // Collect all the guards into a vector and process later, so as not
994
183
  // to invalidate the instruction iterator.
995
183
  SmallVector<IntrinsicInst *, 4> Guards;
996
183
  SmallVector<BranchInst *, 4> GuardsAsWidenableBranches;
997
298
  for (const auto BB : L->blocks()) {
998
298
    for (auto &I : *BB)
999
2.70k
      if (isGuard(&I))
1000
126
        Guards.push_back(cast<IntrinsicInst>(&I));
1001
298
    if (PredicateWidenableBranchGuards &&
1002
298
        isGuardAsWidenableBranch(BB->getTerminator()))
1003
78
      GuardsAsWidenableBranches.push_back(
1004
78
          cast<BranchInst>(BB->getTerminator()));
1005
298
  }
1006
183
1007
183
  if (Guards.empty() && 
GuardsAsWidenableBranches.empty()75
)
1008
3
    return false;
1009
180
1010
180
  SCEVExpander Expander(*SE, *DL, "loop-predication");
1011
180
1012
180
  bool Changed = false;
1013
180
  for (auto *Guard : Guards)
1014
126
    Changed |= widenGuardConditions(Guard, Expander);
1015
180
  for (auto *Guard : GuardsAsWidenableBranches)
1016
78
    Changed |= widenWidenableBranchGuardConditions(Guard, Expander);
1017
180
1018
180
  return Changed;
1019
180
}