Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/Transforms/Utils/SimplifyIndVar.cpp
Line
Count
Source (jump to first uncovered line)
1
//===-- SimplifyIndVar.cpp - Induction variable simplification ------------===//
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 induction variable simplification. It does
10
// not define any actual pass or policy, but provides a single function to
11
// simplify a loop's induction variables based on ScalarEvolution.
12
//
13
//===----------------------------------------------------------------------===//
14
15
#include "llvm/Transforms/Utils/SimplifyIndVar.h"
16
#include "llvm/ADT/STLExtras.h"
17
#include "llvm/ADT/SmallVector.h"
18
#include "llvm/ADT/Statistic.h"
19
#include "llvm/Analysis/LoopInfo.h"
20
#include "llvm/Analysis/ScalarEvolutionExpander.h"
21
#include "llvm/IR/DataLayout.h"
22
#include "llvm/IR/Dominators.h"
23
#include "llvm/IR/IRBuilder.h"
24
#include "llvm/IR/Instructions.h"
25
#include "llvm/IR/IntrinsicInst.h"
26
#include "llvm/IR/PatternMatch.h"
27
#include "llvm/Support/Debug.h"
28
#include "llvm/Support/raw_ostream.h"
29
#include "llvm/Transforms/Utils/Local.h"
30
31
using namespace llvm;
32
33
#define DEBUG_TYPE "indvars"
34
35
STATISTIC(NumElimIdentity, "Number of IV identities eliminated");
36
STATISTIC(NumElimOperand,  "Number of IV operands folded into a use");
37
STATISTIC(NumFoldedUser, "Number of IV users folded into a constant");
38
STATISTIC(NumElimRem     , "Number of IV remainder operations eliminated");
39
STATISTIC(
40
    NumSimplifiedSDiv,
41
    "Number of IV signed division operations converted to unsigned division");
42
STATISTIC(
43
    NumSimplifiedSRem,
44
    "Number of IV signed remainder operations converted to unsigned remainder");
45
STATISTIC(NumElimCmp     , "Number of IV comparisons eliminated");
46
47
namespace {
48
  /// This is a utility for simplifying induction variables
49
  /// based on ScalarEvolution. It is the primary instrument of the
50
  /// IndvarSimplify pass, but it may also be directly invoked to cleanup after
51
  /// other loop passes that preserve SCEV.
52
  class SimplifyIndvar {
53
    Loop             *L;
54
    LoopInfo         *LI;
55
    ScalarEvolution  *SE;
56
    DominatorTree    *DT;
57
    SCEVExpander     &Rewriter;
58
    SmallVectorImpl<WeakTrackingVH> &DeadInsts;
59
60
    bool Changed;
61
62
  public:
63
    SimplifyIndvar(Loop *Loop, ScalarEvolution *SE, DominatorTree *DT,
64
                   LoopInfo *LI, SCEVExpander &Rewriter,
65
                   SmallVectorImpl<WeakTrackingVH> &Dead)
66
        : L(Loop), LI(LI), SE(SE), DT(DT), Rewriter(Rewriter), DeadInsts(Dead),
67
326k
          Changed(false) {
68
326k
      assert(LI && "IV simplification requires LoopInfo");
69
326k
    }
70
71
326k
    bool hasChanged() const { return Changed; }
72
73
    /// Iteratively perform simplification on a worklist of users of the
74
    /// specified induction variable. This is the top-level driver that applies
75
    /// all simplifications to users of an IV.
76
    void simplifyUsers(PHINode *CurrIV, IVVisitor *V = nullptr);
77
78
    Value *foldIVUser(Instruction *UseInst, Instruction *IVOperand);
79
80
    bool eliminateIdentitySCEV(Instruction *UseInst, Instruction *IVOperand);
81
    bool replaceIVUserWithLoopInvariant(Instruction *UseInst);
82
83
    bool eliminateOverflowIntrinsic(WithOverflowInst *WO);
84
    bool eliminateSaturatingIntrinsic(SaturatingInst *SI);
85
    bool eliminateTrunc(TruncInst *TI);
86
    bool eliminateIVUser(Instruction *UseInst, Instruction *IVOperand);
87
    bool makeIVComparisonInvariant(ICmpInst *ICmp, Value *IVOperand);
88
    void eliminateIVComparison(ICmpInst *ICmp, Value *IVOperand);
89
    void simplifyIVRemainder(BinaryOperator *Rem, Value *IVOperand,
90
                             bool IsSigned);
91
    void replaceRemWithNumerator(BinaryOperator *Rem);
92
    void replaceRemWithNumeratorOrZero(BinaryOperator *Rem);
93
    void replaceSRemWithURem(BinaryOperator *Rem);
94
    bool eliminateSDiv(BinaryOperator *SDiv);
95
    bool strengthenOverflowingOperation(BinaryOperator *OBO, Value *IVOperand);
96
    bool strengthenRightShift(BinaryOperator *BO, Value *IVOperand);
97
  };
98
}
99
100
/// Fold an IV operand into its use.  This removes increments of an
101
/// aligned IV when used by a instruction that ignores the low bits.
102
///
103
/// IVOperand is guaranteed SCEVable, but UseInst may not be.
104
///
105
/// Return the operand of IVOperand for this induction variable if IVOperand can
106
/// be folded (in case more folding opportunities have been exposed).
107
/// Otherwise return null.
108
1.33M
Value *SimplifyIndvar::foldIVUser(Instruction *UseInst, Instruction *IVOperand) {
109
1.33M
  Value *IVSrc = nullptr;
110
1.33M
  const unsigned OperIdx = 0;
111
1.33M
  const SCEV *FoldedExpr = nullptr;
112
1.33M
  bool MustDropExactFlag = false;
113
1.33M
  switch (UseInst->getOpcode()) {
114
1.33M
  default:
115
1.32M
    return nullptr;
116
1.33M
  case Instruction::UDiv:
117
5.17k
  case Instruction::LShr:
118
5.17k
    // We're only interested in the case where we know something about
119
5.17k
    // the numerator and have a constant denominator.
120
5.17k
    if (IVOperand != UseInst->getOperand(OperIdx) ||
121
5.17k
        
!isa<ConstantInt>(UseInst->getOperand(1))5.03k
)
122
373
      return nullptr;
123
4.80k
124
4.80k
    // Attempt to fold a binary operator with constant operand.
125
4.80k
    // e.g. ((I + 1) >> 2) => I >> 2
126
4.80k
    if (!isa<BinaryOperator>(IVOperand)
127
4.80k
        || 
!isa<ConstantInt>(IVOperand->getOperand(1))283
)
128
4.55k
      return nullptr;
129
244
130
244
    IVSrc = IVOperand->getOperand(0);
131
244
    // IVSrc must be the (SCEVable) IV, since the other operand is const.
132
244
    assert(SE->isSCEVable(IVSrc->getType()) && "Expect SCEVable IV operand");
133
244
134
244
    ConstantInt *D = cast<ConstantInt>(UseInst->getOperand(1));
135
244
    if (UseInst->getOpcode() == Instruction::LShr) {
136
240
      // Get a constant for the divisor. See createSCEV.
137
240
      uint32_t BitWidth = cast<IntegerType>(UseInst->getType())->getBitWidth();
138
240
      if (D->getValue().uge(BitWidth))
139
0
        return nullptr;
140
240
141
240
      D = ConstantInt::get(UseInst->getContext(),
142
240
                           APInt::getOneBitSet(BitWidth, D->getZExtValue()));
143
240
    }
144
244
    FoldedExpr = SE->getUDivExpr(SE->getSCEV(IVSrc), SE->getSCEV(D));
145
244
    // We might have 'exact' flag set at this point which will no longer be
146
244
    // correct after we make the replacement.
147
244
    if (UseInst->isExact() &&
148
244
        
SE->getSCEV(IVSrc) != SE->getMulExpr(FoldedExpr, SE->getSCEV(D))7
)
149
7
      MustDropExactFlag = true;
150
1.33M
  }
151
1.33M
  // We have something that might fold it's operand. Compare SCEVs.
152
1.33M
  
if (244
!SE->isSCEVable(UseInst->getType())244
)
153
0
    return nullptr;
154
244
155
244
  // Bypass the operand if SCEV can prove it has no effect.
156
244
  if (SE->getSCEV(UseInst) != FoldedExpr)
157
231
    return nullptr;
158
13
159
13
  LLVM_DEBUG(dbgs() << "INDVARS: Eliminated IV operand: " << *IVOperand
160
13
                    << " -> " << *UseInst << '\n');
161
13
162
13
  UseInst->setOperand(OperIdx, IVSrc);
163
13
  assert(SE->getSCEV(UseInst) == FoldedExpr && "bad SCEV with folded oper");
164
13
165
13
  if (MustDropExactFlag)
166
1
    UseInst->dropPoisonGeneratingFlags();
167
13
168
13
  ++NumElimOperand;
169
13
  Changed = true;
170
13
  if (IVOperand->use_empty())
171
1
    DeadInsts.emplace_back(IVOperand);
172
13
  return IVSrc;
173
13
}
174
175
bool SimplifyIndvar::makeIVComparisonInvariant(ICmpInst *ICmp,
176
206k
                                               Value *IVOperand) {
177
206k
  unsigned IVOperIdx = 0;
178
206k
  ICmpInst::Predicate Pred = ICmp->getPredicate();
179
206k
  if (IVOperand != ICmp->getOperand(0)) {
180
14.0k
    // Swapped
181
14.0k
    assert(IVOperand == ICmp->getOperand(1) && "Can't find IVOperand");
182
14.0k
    IVOperIdx = 1;
183
14.0k
    Pred = ICmpInst::getSwappedPredicate(Pred);
184
14.0k
  }
185
206k
186
206k
  // Get the SCEVs for the ICmp operands (in the specific context of the
187
206k
  // current loop)
188
206k
  const Loop *ICmpLoop = LI->getLoopFor(ICmp->getParent());
189
206k
  const SCEV *S = SE->getSCEVAtScope(ICmp->getOperand(IVOperIdx), ICmpLoop);
190
206k
  const SCEV *X = SE->getSCEVAtScope(ICmp->getOperand(1 - IVOperIdx), ICmpLoop);
191
206k
192
206k
  ICmpInst::Predicate InvariantPredicate;
193
206k
  const SCEV *InvariantLHS, *InvariantRHS;
194
206k
195
206k
  auto *PN = dyn_cast<PHINode>(IVOperand);
196
206k
  if (!PN)
197
156k
    return false;
198
50.3k
  if (!SE->isLoopInvariantPredicate(Pred, S, X, L, InvariantPredicate,
199
50.3k
                                    InvariantLHS, InvariantRHS))
200
50.2k
    return false;
201
20
202
20
  // Rewrite the comparison to a loop invariant comparison if it can be done
203
20
  // cheaply, where cheaply means "we don't need to emit any new
204
20
  // instructions".
205
20
206
20
  SmallDenseMap<const SCEV*, Value*> CheapExpansions;
207
20
  CheapExpansions[S] = ICmp->getOperand(IVOperIdx);
208
20
  CheapExpansions[X] = ICmp->getOperand(1 - IVOperIdx);
209
20
210
20
  // TODO: Support multiple entry loops?  (We currently bail out of these in
211
20
  // the IndVarSimplify pass)
212
20
  if (auto *BB = L->getLoopPredecessor()) {
213
20
    const int Idx = PN->getBasicBlockIndex(BB);
214
20
    if (Idx >= 0) {
215
19
      Value *Incoming = PN->getIncomingValue(Idx);
216
19
      const SCEV *IncomingS = SE->getSCEV(Incoming);
217
19
      CheapExpansions[IncomingS] = Incoming;
218
19
    }
219
20
  }
220
20
  Value *NewLHS = CheapExpansions[InvariantLHS];
221
20
  Value *NewRHS = CheapExpansions[InvariantRHS];
222
20
223
20
  if (!NewLHS)
224
1
    if (auto *ConstLHS = dyn_cast<SCEVConstant>(InvariantLHS))
225
1
      NewLHS = ConstLHS->getValue();
226
20
  if (!NewRHS)
227
0
    if (auto *ConstRHS = dyn_cast<SCEVConstant>(InvariantRHS))
228
0
      NewRHS = ConstRHS->getValue();
229
20
230
20
  if (!NewLHS || !NewRHS)
231
0
    // We could not find an existing value to replace either LHS or RHS.
232
0
    // Generating new instructions has subtler tradeoffs, so avoid doing that
233
0
    // for now.
234
0
    return false;
235
20
236
20
  LLVM_DEBUG(dbgs() << "INDVARS: Simplified comparison: " << *ICmp << '\n');
237
20
  ICmp->setPredicate(InvariantPredicate);
238
20
  ICmp->setOperand(0, NewLHS);
239
20
  ICmp->setOperand(1, NewRHS);
240
20
  return true;
241
20
}
242
243
/// SimplifyIVUsers helper for eliminating useless
244
/// comparisons against an induction variable.
245
207k
void SimplifyIndvar::eliminateIVComparison(ICmpInst *ICmp, Value *IVOperand) {
246
207k
  unsigned IVOperIdx = 0;
247
207k
  ICmpInst::Predicate Pred = ICmp->getPredicate();
248
207k
  ICmpInst::Predicate OriginalPred = Pred;
249
207k
  if (IVOperand != ICmp->getOperand(0)) {
250
14.1k
    // Swapped
251
14.1k
    assert(IVOperand == ICmp->getOperand(1) && "Can't find IVOperand");
252
14.1k
    IVOperIdx = 1;
253
14.1k
    Pred = ICmpInst::getSwappedPredicate(Pred);
254
14.1k
  }
255
207k
256
207k
  // Get the SCEVs for the ICmp operands (in the specific context of the
257
207k
  // current loop)
258
207k
  const Loop *ICmpLoop = LI->getLoopFor(ICmp->getParent());
259
207k
  const SCEV *S = SE->getSCEVAtScope(ICmp->getOperand(IVOperIdx), ICmpLoop);
260
207k
  const SCEV *X = SE->getSCEVAtScope(ICmp->getOperand(1 - IVOperIdx), ICmpLoop);
261
207k
262
207k
  // If the condition is always true or always false, replace it with
263
207k
  // a constant value.
264
207k
  if (SE->isKnownPredicate(Pred, S, X)) {
265
397
    ICmp->replaceAllUsesWith(ConstantInt::getTrue(ICmp->getContext()));
266
397
    DeadInsts.emplace_back(ICmp);
267
397
    LLVM_DEBUG(dbgs() << "INDVARS: Eliminated comparison: " << *ICmp << '\n');
268
207k
  } else if (SE->isKnownPredicate(ICmpInst::getInversePredicate(Pred), S, X)) {
269
518
    ICmp->replaceAllUsesWith(ConstantInt::getFalse(ICmp->getContext()));
270
518
    DeadInsts.emplace_back(ICmp);
271
518
    LLVM_DEBUG(dbgs() << "INDVARS: Eliminated comparison: " << *ICmp << '\n');
272
206k
  } else if (makeIVComparisonInvariant(ICmp, IVOperand)) {
273
20
    // fallthrough to end of function
274
206k
  } else if (ICmpInst::isSigned(OriginalPred) &&
275
206k
             
SE->isKnownNonNegative(S)56.6k
&&
SE->isKnownNonNegative(X)40.7k
) {
276
6.10k
    // If we were unable to make anything above, all we can is to canonicalize
277
6.10k
    // the comparison hoping that it will open the doors for other
278
6.10k
    // optimizations. If we find out that we compare two non-negative values,
279
6.10k
    // we turn the instruction's predicate to its unsigned version. Note that
280
6.10k
    // we cannot rely on Pred here unless we check if we have swapped it.
281
6.10k
    assert(ICmp->getPredicate() == OriginalPred && "Predicate changed?");
282
6.10k
    LLVM_DEBUG(dbgs() << "INDVARS: Turn to unsigned comparison: " << *ICmp
283
6.10k
                      << '\n');
284
6.10k
    ICmp->setPredicate(ICmpInst::getUnsignedPredicate(OriginalPred));
285
6.10k
  } else
286
200k
    return;
287
7.03k
288
7.03k
  ++NumElimCmp;
289
7.03k
  Changed = true;
290
7.03k
}
291
292
304
bool SimplifyIndvar::eliminateSDiv(BinaryOperator *SDiv) {
293
304
  // Get the SCEVs for the ICmp operands.
294
304
  auto *N = SE->getSCEV(SDiv->getOperand(0));
295
304
  auto *D = SE->getSCEV(SDiv->getOperand(1));
296
304
297
304
  // Simplify unnecessary loops away.
298
304
  const Loop *L = LI->getLoopFor(SDiv->getParent());
299
304
  N = SE->getSCEVAtScope(N, L);
300
304
  D = SE->getSCEVAtScope(D, L);
301
304
302
304
  // Replace sdiv by udiv if both of the operands are non-negative
303
304
  if (SE->isKnownNonNegative(N) && 
SE->isKnownNonNegative(D)16
) {
304
9
    auto *UDiv = BinaryOperator::Create(
305
9
        BinaryOperator::UDiv, SDiv->getOperand(0), SDiv->getOperand(1),
306
9
        SDiv->getName() + ".udiv", SDiv);
307
9
    UDiv->setIsExact(SDiv->isExact());
308
9
    SDiv->replaceAllUsesWith(UDiv);
309
9
    LLVM_DEBUG(dbgs() << "INDVARS: Simplified sdiv: " << *SDiv << '\n');
310
9
    ++NumSimplifiedSDiv;
311
9
    Changed = true;
312
9
    DeadInsts.push_back(SDiv);
313
9
    return true;
314
9
  }
315
295
316
295
  return false;
317
295
}
318
319
// i %s n -> i %u n if i >= 0 and n >= 0
320
6
void SimplifyIndvar::replaceSRemWithURem(BinaryOperator *Rem) {
321
6
  auto *N = Rem->getOperand(0), *D = Rem->getOperand(1);
322
6
  auto *URem = BinaryOperator::Create(BinaryOperator::URem, N, D,
323
6
                                      Rem->getName() + ".urem", Rem);
324
6
  Rem->replaceAllUsesWith(URem);
325
6
  LLVM_DEBUG(dbgs() << "INDVARS: Simplified srem: " << *Rem << '\n');
326
6
  ++NumSimplifiedSRem;
327
6
  Changed = true;
328
6
  DeadInsts.emplace_back(Rem);
329
6
}
330
331
// i % n  -->  i  if i is in [0,n).
332
1
void SimplifyIndvar::replaceRemWithNumerator(BinaryOperator *Rem) {
333
1
  Rem->replaceAllUsesWith(Rem->getOperand(0));
334
1
  LLVM_DEBUG(dbgs() << "INDVARS: Simplified rem: " << *Rem << '\n');
335
1
  ++NumElimRem;
336
1
  Changed = true;
337
1
  DeadInsts.emplace_back(Rem);
338
1
}
339
340
// (i+1) % n  -->  (i+1)==n?0:(i+1)  if i is in [0,n).
341
26
void SimplifyIndvar::replaceRemWithNumeratorOrZero(BinaryOperator *Rem) {
342
26
  auto *T = Rem->getType();
343
26
  auto *N = Rem->getOperand(0), *D = Rem->getOperand(1);
344
26
  ICmpInst *ICmp = new ICmpInst(Rem, ICmpInst::ICMP_EQ, N, D);
345
26
  SelectInst *Sel =
346
26
      SelectInst::Create(ICmp, ConstantInt::get(T, 0), N, "iv.rem", Rem);
347
26
  Rem->replaceAllUsesWith(Sel);
348
26
  LLVM_DEBUG(dbgs() << "INDVARS: Simplified rem: " << *Rem << '\n');
349
26
  ++NumElimRem;
350
26
  Changed = true;
351
26
  DeadInsts.emplace_back(Rem);
352
26
}
353
354
/// SimplifyIVUsers helper for eliminating useless remainder operations
355
/// operating on an induction variable or replacing srem by urem.
356
void SimplifyIndvar::simplifyIVRemainder(BinaryOperator *Rem, Value *IVOperand,
357
593
                                         bool IsSigned) {
358
593
  auto *NValue = Rem->getOperand(0);
359
593
  auto *DValue = Rem->getOperand(1);
360
593
  // We're only interested in the case where we know something about
361
593
  // the numerator, unless it is a srem, because we want to replace srem by urem
362
593
  // in general.
363
593
  bool UsedAsNumerator = IVOperand == NValue;
364
593
  if (!UsedAsNumerator && 
!IsSigned74
)
365
11
    return;
366
582
367
582
  const SCEV *N = SE->getSCEV(NValue);
368
582
369
582
  // Simplify unnecessary loops away.
370
582
  const Loop *ICmpLoop = LI->getLoopFor(Rem->getParent());
371
582
  N = SE->getSCEVAtScope(N, ICmpLoop);
372
582
373
582
  bool IsNumeratorNonNegative = !IsSigned || 
SE->isKnownNonNegative(N)232
;
374
582
375
582
  // Do not proceed if the Numerator may be negative
376
582
  if (!IsNumeratorNonNegative)
377
217
    return;
378
365
379
365
  const SCEV *D = SE->getSCEV(DValue);
380
365
  D = SE->getSCEVAtScope(D, ICmpLoop);
381
365
382
365
  if (UsedAsNumerator) {
383
364
    auto LT = IsSigned ? 
ICmpInst::ICMP_SLT14
:
ICmpInst::ICMP_ULT350
;
384
364
    if (SE->isKnownPredicate(LT, N, D)) {
385
1
      replaceRemWithNumerator(Rem);
386
1
      return;
387
1
    }
388
363
389
363
    auto *T = Rem->getType();
390
363
    const auto *NLessOne = SE->getMinusSCEV(N, SE->getOne(T));
391
363
    if (SE->isKnownPredicate(LT, NLessOne, D)) {
392
26
      replaceRemWithNumeratorOrZero(Rem);
393
26
      return;
394
26
    }
395
338
  }
396
338
397
338
  // Try to replace SRem with URem, if both N and D are known non-negative.
398
338
  // Since we had already check N, we only need to check D now
399
338
  if (!IsSigned || 
!SE->isKnownNonNegative(D)13
)
400
332
    return;
401
6
402
6
  replaceSRemWithURem(Rem);
403
6
}
404
405
static bool willNotOverflow(ScalarEvolution *SE, Instruction::BinaryOps BinOp,
406
154k
                            bool Signed, const SCEV *LHS, const SCEV *RHS) {
407
154k
  const SCEV *(ScalarEvolution::*Operation)(const SCEV *, const SCEV *,
408
154k
                                            SCEV::NoWrapFlags, unsigned);
409
154k
  switch (BinOp) {
410
154k
  default:
411
0
    llvm_unreachable("Unsupported binary op");
412
154k
  case Instruction::Add:
413
125k
    Operation = &ScalarEvolution::getAddExpr;
414
125k
    break;
415
154k
  case Instruction::Sub:
416
20.2k
    Operation = &ScalarEvolution::getMinusSCEV;
417
20.2k
    break;
418
154k
  case Instruction::Mul:
419
8.66k
    Operation = &ScalarEvolution::getMulExpr;
420
8.66k
    break;
421
154k
  }
422
154k
423
154k
  const SCEV *(ScalarEvolution::*Extension)(const SCEV *, Type *, unsigned) =
424
154k
      Signed ? 
&ScalarEvolution::getSignExtendExpr63.8k
425
154k
             : 
&ScalarEvolution::getZeroExtendExpr90.7k
;
426
154k
427
154k
  // Check ext(LHS op RHS) == ext(LHS) op ext(RHS)
428
154k
  auto *NarrowTy = cast<IntegerType>(LHS->getType());
429
154k
  auto *WideTy =
430
154k
    IntegerType::get(NarrowTy->getContext(), NarrowTy->getBitWidth() * 2);
431
154k
432
154k
  const SCEV *A =
433
154k
      (SE->*Extension)((SE->*Operation)(LHS, RHS, SCEV::FlagAnyWrap, 0),
434
154k
                       WideTy, 0);
435
154k
  const SCEV *B =
436
154k
      (SE->*Operation)((SE->*Extension)(LHS, WideTy, 0),
437
154k
                       (SE->*Extension)(RHS, WideTy, 0), SCEV::FlagAnyWrap, 0);
438
154k
  return A == B;
439
154k
}
440
441
6
bool SimplifyIndvar::eliminateOverflowIntrinsic(WithOverflowInst *WO) {
442
6
  const SCEV *LHS = SE->getSCEV(WO->getLHS());
443
6
  const SCEV *RHS = SE->getSCEV(WO->getRHS());
444
6
  if (!willNotOverflow(SE, WO->getBinaryOp(), WO->isSigned(), LHS, RHS))
445
3
    return false;
446
3
447
3
  // Proved no overflow, nuke the overflow check and, if possible, the overflow
448
3
  // intrinsic as well.
449
3
450
3
  BinaryOperator *NewResult = BinaryOperator::Create(
451
3
      WO->getBinaryOp(), WO->getLHS(), WO->getRHS(), "", WO);
452
3
453
3
  if (WO->isSigned())
454
2
    NewResult->setHasNoSignedWrap(true);
455
1
  else
456
1
    NewResult->setHasNoUnsignedWrap(true);
457
3
458
3
  SmallVector<ExtractValueInst *, 4> ToDelete;
459
3
460
6
  for (auto *U : WO->users()) {
461
6
    if (auto *EVI = dyn_cast<ExtractValueInst>(U)) {
462
6
      if (EVI->getIndices()[0] == 1)
463
3
        EVI->replaceAllUsesWith(ConstantInt::getFalse(WO->getContext()));
464
3
      else {
465
3
        assert(EVI->getIndices()[0] == 0 && "Only two possibilities!");
466
3
        EVI->replaceAllUsesWith(NewResult);
467
3
      }
468
6
      ToDelete.push_back(EVI);
469
6
    }
470
6
  }
471
3
472
3
  for (auto *EVI : ToDelete)
473
6
    EVI->eraseFromParent();
474
3
475
3
  if (WO->use_empty())
476
3
    WO->eraseFromParent();
477
3
478
3
  return true;
479
3
}
480
481
7
bool SimplifyIndvar::eliminateSaturatingIntrinsic(SaturatingInst *SI) {
482
7
  const SCEV *LHS = SE->getSCEV(SI->getLHS());
483
7
  const SCEV *RHS = SE->getSCEV(SI->getRHS());
484
7
  if (!willNotOverflow(SE, SI->getBinaryOp(), SI->isSigned(), LHS, RHS))
485
3
    return false;
486
4
487
4
  BinaryOperator *BO = BinaryOperator::Create(
488
4
      SI->getBinaryOp(), SI->getLHS(), SI->getRHS(), SI->getName(), SI);
489
4
  if (SI->isSigned())
490
2
    BO->setHasNoSignedWrap();
491
2
  else
492
2
    BO->setHasNoUnsignedWrap();
493
4
494
4
  SI->replaceAllUsesWith(BO);
495
4
  DeadInsts.emplace_back(SI);
496
4
  Changed = true;
497
4
  return true;
498
4
}
499
500
37.7k
bool SimplifyIndvar::eliminateTrunc(TruncInst *TI) {
501
37.7k
  // It is always legal to replace
502
37.7k
  //   icmp <pred> i32 trunc(iv), n
503
37.7k
  // with
504
37.7k
  //   icmp <pred> i64 sext(trunc(iv)), sext(n), if pred is signed predicate.
505
37.7k
  // Or with
506
37.7k
  //   icmp <pred> i64 zext(trunc(iv)), zext(n), if pred is unsigned predicate.
507
37.7k
  // Or with either of these if pred is an equality predicate.
508
37.7k
  //
509
37.7k
  // If we can prove that iv == sext(trunc(iv)) or iv == zext(trunc(iv)) for
510
37.7k
  // every comparison which uses trunc, it means that we can replace each of
511
37.7k
  // them with comparison of iv against sext/zext(n). We no longer need trunc
512
37.7k
  // after that.
513
37.7k
  //
514
37.7k
  // TODO: Should we do this if we can widen *some* comparisons, but not all
515
37.7k
  // of them? Sometimes it is enough to enable other optimizations, but the
516
37.7k
  // trunc instruction will stay in the loop.
517
37.7k
  Value *IV = TI->getOperand(0);
518
37.7k
  Type *IVTy = IV->getType();
519
37.7k
  const SCEV *IVSCEV = SE->getSCEV(IV);
520
37.7k
  const SCEV *TISCEV = SE->getSCEV(TI);
521
37.7k
522
37.7k
  // Check if iv == zext(trunc(iv)) and if iv == sext(trunc(iv)). If so, we can
523
37.7k
  // get rid of trunc
524
37.7k
  bool DoesSExtCollapse = false;
525
37.7k
  bool DoesZExtCollapse = false;
526
37.7k
  if (IVSCEV == SE->getSignExtendExpr(TISCEV, IVTy))
527
20.7k
    DoesSExtCollapse = true;
528
37.7k
  if (IVSCEV == SE->getZeroExtendExpr(TISCEV, IVTy))
529
32.5k
    DoesZExtCollapse = true;
530
37.7k
531
37.7k
  // If neither sext nor zext does collapse, it is not profitable to do any
532
37.7k
  // transform. Bail.
533
37.7k
  if (!DoesSExtCollapse && 
!DoesZExtCollapse17.0k
)
534
3.64k
    return false;
535
34.1k
536
34.1k
  // Collect users of the trunc that look like comparisons against invariants.
537
34.1k
  // Bail if we find something different.
538
34.1k
  SmallVector<ICmpInst *, 4> ICmpUsers;
539
34.1k
  for (auto *U : TI->users()) {
540
34.1k
    // We don't care about users in unreachable blocks.
541
34.1k
    if (isa<Instruction>(U) &&
542
34.1k
        !DT->isReachableFromEntry(cast<Instruction>(U)->getParent()))
543
1
      continue;
544
34.1k
    ICmpInst *ICI = dyn_cast<ICmpInst>(U);
545
34.1k
    if (!ICI) 
return false20.8k
;
546
13.2k
    assert(L->contains(ICI->getParent()) && "LCSSA form broken?");
547
13.2k
    if (!(ICI->getOperand(0) == TI && 
L->isLoopInvariant(ICI->getOperand(1))13.2k
) &&
548
13.2k
        
!(64
ICI->getOperand(1) == TI64
&&
L->isLoopInvariant(ICI->getOperand(0))27
))
549
46
      return false;
550
13.2k
    // If we cannot get rid of trunc, bail.
551
13.2k
    if (ICI->isSigned() && 
!DoesSExtCollapse231
)
552
193
      return false;
553
13.0k
    if (ICI->isUnsigned() && 
!DoesZExtCollapse15
)
554
5
      return false;
555
13.0k
    // For equality, either signed or unsigned works.
556
13.0k
    ICmpUsers.push_back(ICI);
557
13.0k
  }
558
34.1k
559
34.1k
  
auto CanUseZExt = [&](ICmpInst *ICI) 13.0k
{
560
13.0k
    // Unsigned comparison can be widened as unsigned.
561
13.0k
    if (ICI->isUnsigned())
562
9
      return true;
563
12.9k
    // Is it profitable to do zext?
564
12.9k
    if (!DoesZExtCollapse)
565
512
      return false;
566
12.4k
    // For equality, we can safely zext both parts.
567
12.4k
    if (ICI->isEquality())
568
12.4k
      return true;
569
34
    // Otherwise we can only use zext when comparing two non-negative or two
570
34
    // negative values. But in practice, we will never pass DoesZExtCollapse
571
34
    // check for a negative value, because zext(trunc(x)) is non-negative. So
572
34
    // it only make sense to check for non-negativity here.
573
34
    const SCEV *SCEVOP1 = SE->getSCEV(ICI->getOperand(0));
574
34
    const SCEV *SCEVOP2 = SE->getSCEV(ICI->getOperand(1));
575
34
    return SE->isKnownNonNegative(SCEVOP1) && 
SE->isKnownNonNegative(SCEVOP2)7
;
576
34
  };
577
13.0k
  // Replace all comparisons against trunc with comparisons against IV.
578
13.0k
  for (auto *ICI : ICmpUsers) {
579
13.0k
    bool IsSwapped = L->isLoopInvariant(ICI->getOperand(0));
580
13.0k
    auto *Op1 = IsSwapped ? 
ICI->getOperand(0)16
:
ICI->getOperand(1)12.9k
;
581
13.0k
    Instruction *Ext = nullptr;
582
13.0k
    // For signed/unsigned predicate, replace the old comparison with comparison
583
13.0k
    // of immediate IV against sext/zext of the invariant argument. If we can
584
13.0k
    // use either sext or zext (i.e. we are dealing with equality predicate),
585
13.0k
    // then prefer zext as a more canonical form.
586
13.0k
    // TODO: If we see a signed comparison which can be turned into unsigned,
587
13.0k
    // we can do it here for canonicalization purposes.
588
13.0k
    ICmpInst::Predicate Pred = ICI->getPredicate();
589
13.0k
    if (IsSwapped) 
Pred = ICmpInst::getSwappedPredicate(Pred)16
;
590
13.0k
    if (CanUseZExt(ICI)) {
591
12.4k
      assert(DoesZExtCollapse && "Unprofitable zext?");
592
12.4k
      Ext = new ZExtInst(Op1, IVTy, "zext", ICI);
593
12.4k
      Pred = ICmpInst::getUnsignedPredicate(Pred);
594
12.4k
    } else {
595
543
      assert(DoesSExtCollapse && "Unprofitable sext?");
596
543
      Ext = new SExtInst(Op1, IVTy, "sext", ICI);
597
543
      assert(Pred == ICmpInst::getSignedPredicate(Pred) && "Must be signed!");
598
543
    }
599
13.0k
    bool Changed;
600
13.0k
    L->makeLoopInvariant(Ext, Changed);
601
13.0k
    (void)Changed;
602
13.0k
    ICmpInst *NewICI = new ICmpInst(ICI, Pred, IV, Ext);
603
13.0k
    ICI->replaceAllUsesWith(NewICI);
604
13.0k
    DeadInsts.emplace_back(ICI);
605
13.0k
  }
606
13.0k
607
13.0k
  // Trunc no longer needed.
608
13.0k
  TI->replaceAllUsesWith(UndefValue::get(TI->getType()));
609
13.0k
  DeadInsts.emplace_back(TI);
610
13.0k
  return true;
611
34.1k
}
612
613
/// Eliminate an operation that consumes a simple IV and has no observable
614
/// side-effect given the range of IV values.  IVOperand is guaranteed SCEVable,
615
/// but UseInst may not be.
616
bool SimplifyIndvar::eliminateIVUser(Instruction *UseInst,
617
1.33M
                                     Instruction *IVOperand) {
618
1.33M
  if (ICmpInst *ICmp = dyn_cast<ICmpInst>(UseInst)) {
619
207k
    eliminateIVComparison(ICmp, IVOperand);
620
207k
    return true;
621
207k
  }
622
1.12M
  if (BinaryOperator *Bin = dyn_cast<BinaryOperator>(UseInst)) {
623
255k
    bool IsSRem = Bin->getOpcode() == Instruction::SRem;
624
255k
    if (IsSRem || 
Bin->getOpcode() == Instruction::URem255k
) {
625
593
      simplifyIVRemainder(Bin, IVOperand, IsSRem);
626
593
      return true;
627
593
    }
628
255k
629
255k
    if (Bin->getOpcode() == Instruction::SDiv)
630
304
      return eliminateSDiv(Bin);
631
1.12M
  }
632
1.12M
633
1.12M
  if (auto *WO = dyn_cast<WithOverflowInst>(UseInst))
634
6
    if (eliminateOverflowIntrinsic(WO))
635
3
      return true;
636
1.12M
637
1.12M
  if (auto *SI = dyn_cast<SaturatingInst>(UseInst))
638
7
    if (eliminateSaturatingIntrinsic(SI))
639
4
      return true;
640
1.12M
641
1.12M
  if (auto *TI = dyn_cast<TruncInst>(UseInst))
642
37.7k
    if (eliminateTrunc(TI))
643
13.0k
      return true;
644
1.11M
645
1.11M
  if (eliminateIdentitySCEV(UseInst, IVOperand))
646
317
    return true;
647
1.10M
648
1.10M
  return false;
649
1.10M
}
650
651
177
static Instruction *GetLoopInvariantInsertPosition(Loop *L, Instruction *Hint) {
652
177
  if (auto *BB = L->getLoopPreheader())
653
177
    return BB->getTerminator();
654
0
655
0
  return Hint;
656
0
}
657
658
/// Replace the UseInst with a constant if possible.
659
1.33M
bool SimplifyIndvar::replaceIVUserWithLoopInvariant(Instruction *I) {
660
1.33M
  if (!SE->isSCEVable(I->getType()))
661
126k
    return false;
662
1.20M
663
1.20M
  // Get the symbolic expression for this instruction.
664
1.20M
  const SCEV *S = SE->getSCEV(I);
665
1.20M
666
1.20M
  if (!SE->isLoopInvariant(S, L))
667
1.20M
    return false;
668
177
669
177
  // Do not generate something ridiculous even if S is loop invariant.
670
177
  if (Rewriter.isHighCostExpansion(S, L, I))
671
0
    return false;
672
177
673
177
  auto *IP = GetLoopInvariantInsertPosition(L, I);
674
177
  auto *Invariant = Rewriter.expandCodeFor(S, I->getType(), IP);
675
177
676
177
  I->replaceAllUsesWith(Invariant);
677
177
  LLVM_DEBUG(dbgs() << "INDVARS: Replace IV user: " << *I
678
177
                    << " with loop invariant: " << *S << '\n');
679
177
  ++NumFoldedUser;
680
177
  Changed = true;
681
177
  DeadInsts.emplace_back(I);
682
177
  return true;
683
177
}
684
685
/// Eliminate any operation that SCEV can prove is an identity function.
686
bool SimplifyIndvar::eliminateIdentitySCEV(Instruction *UseInst,
687
1.11M
                                           Instruction *IVOperand) {
688
1.11M
  if (!SE->isSCEVable(UseInst->getType()) ||
689
1.11M
      
(UseInst->getType() != IVOperand->getType())983k
||
690
1.11M
      
(SE->getSCEV(UseInst) != SE->getSCEV(IVOperand))406k
)
691
1.10M
    return false;
692
317
693
317
  // getSCEV(X) == getSCEV(Y) does not guarantee that X and Y are related in the
694
317
  // dominator tree, even if X is an operand to Y.  For instance, in
695
317
  //
696
317
  //     %iv = phi i32 {0,+,1}
697
317
  //     br %cond, label %left, label %merge
698
317
  //
699
317
  //   left:
700
317
  //     %X = add i32 %iv, 0
701
317
  //     br label %merge
702
317
  //
703
317
  //   merge:
704
317
  //     %M = phi (%X, %iv)
705
317
  //
706
317
  // getSCEV(%M) == getSCEV(%X) == {0,+,1}, but %X does not dominate %M, and
707
317
  // %M.replaceAllUsesWith(%X) would be incorrect.
708
317
709
317
  if (isa<PHINode>(UseInst))
710
15
    // If UseInst is not a PHI node then we know that IVOperand dominates
711
15
    // UseInst directly from the legality of SSA.
712
15
    if (!DT || !DT->dominates(IVOperand, UseInst))
713
0
      return false;
714
317
715
317
  if (!LI->replacementPreservesLCSSAForm(UseInst, IVOperand))
716
0
    return false;
717
317
718
317
  LLVM_DEBUG(dbgs() << "INDVARS: Eliminated identity: " << *UseInst << '\n');
719
317
720
317
  UseInst->replaceAllUsesWith(IVOperand);
721
317
  ++NumElimIdentity;
722
317
  Changed = true;
723
317
  DeadInsts.emplace_back(UseInst);
724
317
  return true;
725
317
}
726
727
/// Annotate BO with nsw / nuw if it provably does not signed-overflow /
728
/// unsigned-overflow.  Returns true if anything changed, false otherwise.
729
bool SimplifyIndvar::strengthenOverflowingOperation(BinaryOperator *BO,
730
240k
                                                    Value *IVOperand) {
731
240k
  // Fastpath: we don't have any work to do if `BO` is `nuw` and `nsw`.
732
240k
  if (BO->hasNoUnsignedWrap() && 
BO->hasNoSignedWrap()141k
)
733
123k
    return false;
734
116k
735
116k
  if (BO->getOpcode() != Instruction::Add &&
736
116k
      
BO->getOpcode() != Instruction::Sub25.7k
&&
737
116k
      
BO->getOpcode() != Instruction::Mul14.2k
)
738
7.97k
    return false;
739
108k
740
108k
  const SCEV *LHS = SE->getSCEV(BO->getOperand(0));
741
108k
  const SCEV *RHS = SE->getSCEV(BO->getOperand(1));
742
108k
  bool Changed = false;
743
108k
744
108k
  if (!BO->hasNoUnsignedWrap() &&
745
108k
      
willNotOverflow(SE, BO->getOpcode(), /* Signed */ false, LHS, RHS)90.7k
) {
746
5.03k
    BO->setHasNoUnsignedWrap();
747
5.03k
    SE->forgetValue(BO);
748
5.03k
    Changed = true;
749
5.03k
  }
750
108k
751
108k
  if (!BO->hasNoSignedWrap() &&
752
108k
      
willNotOverflow(SE, BO->getOpcode(), /* Signed */ true, LHS, RHS)63.8k
) {
753
6.96k
    BO->setHasNoSignedWrap();
754
6.96k
    SE->forgetValue(BO);
755
6.96k
    Changed = true;
756
6.96k
  }
757
108k
758
108k
  return Changed;
759
108k
}
760
761
/// Annotate the Shr in (X << IVOperand) >> C as exact using the
762
/// information from the IV's range. Returns true if anything changed, false
763
/// otherwise.
764
bool SimplifyIndvar::strengthenRightShift(BinaryOperator *BO,
765
8.56k
                                          Value *IVOperand) {
766
8.56k
  using namespace llvm::PatternMatch;
767
8.56k
768
8.56k
  if (BO->getOpcode() == Instruction::Shl) {
769
8.56k
    bool Changed = false;
770
8.56k
    ConstantRange IVRange = SE->getUnsignedRange(SE->getSCEV(IVOperand));
771
10.4k
    for (auto *U : BO->users()) {
772
10.4k
      const APInt *C;
773
10.4k
      if (match(U,
774
10.4k
                m_AShr(m_Shl(m_Value(), m_Specific(IVOperand)), m_APInt(C))) ||
775
10.4k
          match(U,
776
10.4k
                m_LShr(m_Shl(m_Value(), m_Specific(IVOperand)), m_APInt(C)))) {
777
9
        BinaryOperator *Shr = cast<BinaryOperator>(U);
778
9
        if (!Shr->isExact() && IVRange.getUnsignedMin().uge(*C)) {
779
7
          Shr->setIsExact(true);
780
7
          Changed = true;
781
7
        }
782
9
      }
783
10.4k
    }
784
8.56k
    return Changed;
785
8.56k
  }
786
0
787
0
  return false;
788
0
}
789
790
/// Add all uses of Def to the current IV's worklist.
791
static void pushIVUsers(
792
  Instruction *Def, Loop *L,
793
  SmallPtrSet<Instruction*,16> &Simplified,
794
1.00M
  SmallVectorImpl< std::pair<Instruction*,Instruction*> > &SimpleIVUsers) {
795
1.00M
796
2.37M
  for (User *U : Def->users()) {
797
2.37M
    Instruction *UI = cast<Instruction>(U);
798
2.37M
799
2.37M
    // Avoid infinite or exponential worklist processing.
800
2.37M
    // Also ensure unique worklist users.
801
2.37M
    // If Def is a LoopPhi, it may not be in the Simplified set, so check for
802
2.37M
    // self edges first.
803
2.37M
    if (UI == Def)
804
12
      continue;
805
2.37M
806
2.37M
    // Only change the current Loop, do not change the other parts (e.g. other
807
2.37M
    // Loops).
808
2.37M
    if (!L->contains(UI))
809
74.8k
      continue;
810
2.30M
811
2.30M
    // Do not push the same instruction more than once.
812
2.30M
    if (!Simplified.insert(UI).second)
813
755k
      continue;
814
1.54M
815
1.54M
    SimpleIVUsers.push_back(std::make_pair(UI, Def));
816
1.54M
  }
817
1.00M
}
818
819
/// Return true if this instruction generates a simple SCEV
820
/// expression in terms of that IV.
821
///
822
/// This is similar to IVUsers' isInteresting() but processes each instruction
823
/// non-recursively when the operand is already known to be a simpleIVUser.
824
///
825
983k
static bool isSimpleIVUser(Instruction *I, const Loop *L, ScalarEvolution *SE) {
826
983k
  if (!SE->isSCEVable(I->getType()))
827
125k
    return false;
828
858k
829
858k
  // Get the symbolic expression for this instruction.
830
858k
  const SCEV *S = SE->getSCEV(I);
831
858k
832
858k
  // Only consider affine recurrences.
833
858k
  const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(S);
834
858k
  if (AR && 
AR->getLoop() == L471k
)
835
459k
    return true;
836
399k
837
399k
  return false;
838
399k
}
839
840
/// Iteratively perform simplification on a worklist of users
841
/// of the specified induction variable. Each successive simplification may push
842
/// more users which may themselves be candidates for simplification.
843
///
844
/// This algorithm does not require IVUsers analysis. Instead, it simplifies
845
/// instructions in-place during analysis. Rather than rewriting induction
846
/// variables bottom-up from their users, it transforms a chain of IVUsers
847
/// top-down, updating the IR only when it encounters a clear optimization
848
/// opportunity.
849
///
850
/// Once DisableIVRewrite is default, LSR will be the only client of IVUsers.
851
///
852
326k
void SimplifyIndvar::simplifyUsers(PHINode *CurrIV, IVVisitor *V) {
853
326k
  if (!SE->isSCEVable(CurrIV->getType()))
854
8.60k
    return;
855
317k
856
317k
  // Instructions processed by SimplifyIndvar for CurrIV.
857
317k
  SmallPtrSet<Instruction*,16> Simplified;
858
317k
859
317k
  // Use-def pairs if IV users waiting to be processed for CurrIV.
860
317k
  SmallVector<std::pair<Instruction*, Instruction*>, 8> SimpleIVUsers;
861
317k
862
317k
  // Push users of the current LoopPhi. In rare cases, pushIVUsers may be
863
317k
  // called multiple times for the same LoopPhi. This is the proper thing to
864
317k
  // do for loop header phis that use each other.
865
317k
  pushIVUsers(CurrIV, L, Simplified, SimpleIVUsers);
866
317k
867
1.86M
  while (!SimpleIVUsers.empty()) {
868
1.54M
    std::pair<Instruction*, Instruction*> UseOper =
869
1.54M
      SimpleIVUsers.pop_back_val();
870
1.54M
    Instruction *UseInst = UseOper.first;
871
1.54M
872
1.54M
    // If a user of the IndVar is trivially dead, we prefer just to mark it dead
873
1.54M
    // rather than try to do some complex analysis or transformation (such as
874
1.54M
    // widening) basing on it.
875
1.54M
    // TODO: Propagate TLI and pass it here to handle more cases.
876
1.54M
    if (isInstructionTriviallyDead(UseInst, /* TLI */ nullptr)) {
877
11.1k
      DeadInsts.emplace_back(UseInst);
878
11.1k
      continue;
879
11.1k
    }
880
1.53M
881
1.53M
    // Bypass back edges to avoid extra work.
882
1.53M
    if (UseInst == CurrIV) 
continue202k
;
883
1.33M
884
1.33M
    // Try to replace UseInst with a loop invariant before any other
885
1.33M
    // simplifications.
886
1.33M
    if (replaceIVUserWithLoopInvariant(UseInst))
887
177
      continue;
888
1.33M
889
1.33M
    Instruction *IVOperand = UseOper.second;
890
1.33M
    for (unsigned N = 0; IVOperand; 
++N13
) {
891
1.33M
      assert(N <= Simplified.size() && "runaway iteration");
892
1.33M
893
1.33M
      Value *NewOper = foldIVUser(UseInst, IVOperand);
894
1.33M
      if (!NewOper)
895
1.33M
        break; // done folding
896
13
      IVOperand = dyn_cast<Instruction>(NewOper);
897
13
    }
898
1.33M
    if (!IVOperand)
899
0
      continue;
900
1.33M
901
1.33M
    if (eliminateIVUser(UseInst, IVOperand)) {
902
221k
      pushIVUsers(IVOperand, L, Simplified, SimpleIVUsers);
903
221k
      continue;
904
221k
    }
905
1.11M
906
1.11M
    if (BinaryOperator *BO = dyn_cast<BinaryOperator>(UseInst)) {
907
255k
      if ((isa<OverflowingBinaryOperator>(BO) &&
908
255k
           
strengthenOverflowingOperation(BO, IVOperand)240k
) ||
909
255k
          
(246k
isa<ShlOperator>(BO)246k
&&
strengthenRightShift(BO, IVOperand)8.56k
)) {
910
8.71k
        // re-queue uses of the now modified binary operator and fall
911
8.71k
        // through to the checks that remain.
912
8.71k
        pushIVUsers(IVOperand, L, Simplified, SimpleIVUsers);
913
8.71k
      }
914
255k
    }
915
1.11M
916
1.11M
    CastInst *Cast = dyn_cast<CastInst>(UseInst);
917
1.11M
    if (V && 
Cast1.04M
) {
918
126k
      V->visitCast(Cast);
919
126k
      continue;
920
126k
    }
921
983k
    if (isSimpleIVUser(UseInst, L, SE)) {
922
459k
      pushIVUsers(UseInst, L, Simplified, SimpleIVUsers);
923
459k
    }
924
983k
  }
925
317k
}
926
927
namespace llvm {
928
929
0
void IVVisitor::anchor() { }
930
931
/// Simplify instructions that use this induction variable
932
/// by using ScalarEvolution to analyze the IV's recurrence.
933
bool simplifyUsersOfIV(PHINode *CurrIV, ScalarEvolution *SE, DominatorTree *DT,
934
                       LoopInfo *LI, SmallVectorImpl<WeakTrackingVH> &Dead,
935
326k
                       SCEVExpander &Rewriter, IVVisitor *V) {
936
326k
  SimplifyIndvar SIV(LI->getLoopFor(CurrIV->getParent()), SE, DT, LI, Rewriter,
937
326k
                     Dead);
938
326k
  SIV.simplifyUsers(CurrIV, V);
939
326k
  return SIV.hasChanged();
940
326k
}
941
942
/// Simplify users of induction variables within this
943
/// loop. This does not actually change or add IVs.
944
bool simplifyLoopIVs(Loop *L, ScalarEvolution *SE, DominatorTree *DT,
945
1.82k
                     LoopInfo *LI, SmallVectorImpl<WeakTrackingVH> &Dead) {
946
1.82k
  SCEVExpander Rewriter(*SE, SE->getDataLayout(), "indvars");
947
#ifndef NDEBUG
948
  Rewriter.setDebugType(DEBUG_TYPE);
949
#endif
950
  bool Changed = false;
951
5.84k
  for (BasicBlock::iterator I = L->getHeader()->begin(); isa<PHINode>(I); 
++I4.01k
) {
952
4.01k
    Changed |= simplifyUsersOfIV(cast<PHINode>(I), SE, DT, LI, Dead, Rewriter);
953
4.01k
  }
954
1.82k
  return Changed;
955
1.82k
}
956
957
} // namespace llvm