LLVM  6.0.0svn
SimplifyIndVar.cpp
Go to the documentation of this file.
1 //===-- SimplifyIndVar.cpp - Induction variable simplification ------------===//
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 induction variable simplification. It does
11 // not define any actual pass or policy, but provides a single function to
12 // simplify a loop's induction variables based on ScalarEvolution.
13 //
14 //===----------------------------------------------------------------------===//
15 
17 #include "llvm/ADT/STLExtras.h"
18 #include "llvm/ADT/SmallVector.h"
19 #include "llvm/ADT/Statistic.h"
20 #include "llvm/Analysis/LoopInfo.h"
21 #include "llvm/Analysis/LoopPass.h"
23 #include "llvm/IR/DataLayout.h"
24 #include "llvm/IR/Dominators.h"
25 #include "llvm/IR/IRBuilder.h"
26 #include "llvm/IR/Instructions.h"
27 #include "llvm/IR/IntrinsicInst.h"
28 #include "llvm/IR/PatternMatch.h"
29 #include "llvm/Support/Debug.h"
31 
32 using namespace llvm;
33 
34 #define DEBUG_TYPE "indvars"
35 
36 STATISTIC(NumElimIdentity, "Number of IV identities eliminated");
37 STATISTIC(NumElimOperand, "Number of IV operands folded into a use");
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(NumElimCmp , "Number of IV comparisons eliminated");
43 
44 namespace {
45  /// This is a utility for simplifying induction variables
46  /// based on ScalarEvolution. It is the primary instrument of the
47  /// IndvarSimplify pass, but it may also be directly invoked to cleanup after
48  /// other loop passes that preserve SCEV.
49  class SimplifyIndvar {
50  Loop *L;
51  LoopInfo *LI;
52  ScalarEvolution *SE;
53  DominatorTree *DT;
54 
56 
57  bool Changed;
58 
59  public:
60  SimplifyIndvar(Loop *Loop, ScalarEvolution *SE, DominatorTree *DT,
62  : L(Loop), LI(LI), SE(SE), DT(DT), DeadInsts(Dead), Changed(false) {
63  assert(LI && "IV simplification requires LoopInfo");
64  }
65 
66  bool hasChanged() const { return Changed; }
67 
68  /// Iteratively perform simplification on a worklist of users of the
69  /// specified induction variable. This is the top-level driver that applies
70  /// all simplifications to users of an IV.
71  void simplifyUsers(PHINode *CurrIV, IVVisitor *V = nullptr);
72 
73  Value *foldIVUser(Instruction *UseInst, Instruction *IVOperand);
74 
75  bool eliminateIdentitySCEV(Instruction *UseInst, Instruction *IVOperand);
76 
77  bool eliminateOverflowIntrinsic(CallInst *CI);
78  bool eliminateIVUser(Instruction *UseInst, Instruction *IVOperand);
79  void eliminateIVComparison(ICmpInst *ICmp, Value *IVOperand);
80  void eliminateIVRemainder(BinaryOperator *Rem, Value *IVOperand,
81  bool IsSigned);
82  bool eliminateSDiv(BinaryOperator *SDiv);
83  bool strengthenOverflowingOperation(BinaryOperator *OBO, Value *IVOperand);
84  bool strengthenRightShift(BinaryOperator *BO, Value *IVOperand);
85  };
86 }
87 
88 /// Fold an IV operand into its use. This removes increments of an
89 /// aligned IV when used by a instruction that ignores the low bits.
90 ///
91 /// IVOperand is guaranteed SCEVable, but UseInst may not be.
92 ///
93 /// Return the operand of IVOperand for this induction variable if IVOperand can
94 /// be folded (in case more folding opportunities have been exposed).
95 /// Otherwise return null.
96 Value *SimplifyIndvar::foldIVUser(Instruction *UseInst, Instruction *IVOperand) {
97  Value *IVSrc = nullptr;
98  unsigned OperIdx = 0;
99  const SCEV *FoldedExpr = nullptr;
100  switch (UseInst->getOpcode()) {
101  default:
102  return nullptr;
103  case Instruction::UDiv:
104  case Instruction::LShr:
105  // We're only interested in the case where we know something about
106  // the numerator and have a constant denominator.
107  if (IVOperand != UseInst->getOperand(OperIdx) ||
108  !isa<ConstantInt>(UseInst->getOperand(1)))
109  return nullptr;
110 
111  // Attempt to fold a binary operator with constant operand.
112  // e.g. ((I + 1) >> 2) => I >> 2
113  if (!isa<BinaryOperator>(IVOperand)
114  || !isa<ConstantInt>(IVOperand->getOperand(1)))
115  return nullptr;
116 
117  IVSrc = IVOperand->getOperand(0);
118  // IVSrc must be the (SCEVable) IV, since the other operand is const.
119  assert(SE->isSCEVable(IVSrc->getType()) && "Expect SCEVable IV operand");
120 
121  ConstantInt *D = cast<ConstantInt>(UseInst->getOperand(1));
122  if (UseInst->getOpcode() == Instruction::LShr) {
123  // Get a constant for the divisor. See createSCEV.
124  uint32_t BitWidth = cast<IntegerType>(UseInst->getType())->getBitWidth();
125  if (D->getValue().uge(BitWidth))
126  return nullptr;
127 
128  D = ConstantInt::get(UseInst->getContext(),
129  APInt::getOneBitSet(BitWidth, D->getZExtValue()));
130  }
131  FoldedExpr = SE->getUDivExpr(SE->getSCEV(IVSrc), SE->getSCEV(D));
132  }
133  // We have something that might fold it's operand. Compare SCEVs.
134  if (!SE->isSCEVable(UseInst->getType()))
135  return nullptr;
136 
137  // Bypass the operand if SCEV can prove it has no effect.
138  if (SE->getSCEV(UseInst) != FoldedExpr)
139  return nullptr;
140 
141  DEBUG(dbgs() << "INDVARS: Eliminated IV operand: " << *IVOperand
142  << " -> " << *UseInst << '\n');
143 
144  UseInst->setOperand(OperIdx, IVSrc);
145  assert(SE->getSCEV(UseInst) == FoldedExpr && "bad SCEV with folded oper");
146 
147  ++NumElimOperand;
148  Changed = true;
149  if (IVOperand->use_empty())
150  DeadInsts.emplace_back(IVOperand);
151  return IVSrc;
152 }
153 
154 /// SimplifyIVUsers helper for eliminating useless
155 /// comparisons against an induction variable.
156 void SimplifyIndvar::eliminateIVComparison(ICmpInst *ICmp, Value *IVOperand) {
157  unsigned IVOperIdx = 0;
158  ICmpInst::Predicate Pred = ICmp->getPredicate();
159  ICmpInst::Predicate OriginalPred = Pred;
160  if (IVOperand != ICmp->getOperand(0)) {
161  // Swapped
162  assert(IVOperand == ICmp->getOperand(1) && "Can't find IVOperand");
163  IVOperIdx = 1;
164  Pred = ICmpInst::getSwappedPredicate(Pred);
165  }
166 
167  // Get the SCEVs for the ICmp operands.
168  const SCEV *S = SE->getSCEV(ICmp->getOperand(IVOperIdx));
169  const SCEV *X = SE->getSCEV(ICmp->getOperand(1 - IVOperIdx));
170 
171  // Simplify unnecessary loops away.
172  const Loop *ICmpLoop = LI->getLoopFor(ICmp->getParent());
173  S = SE->getSCEVAtScope(S, ICmpLoop);
174  X = SE->getSCEVAtScope(X, ICmpLoop);
175 
176  ICmpInst::Predicate InvariantPredicate;
177  const SCEV *InvariantLHS, *InvariantRHS;
178 
179  // If the condition is always true or always false, replace it with
180  // a constant value.
181  if (SE->isKnownPredicate(Pred, S, X)) {
183  DeadInsts.emplace_back(ICmp);
184  DEBUG(dbgs() << "INDVARS: Eliminated comparison: " << *ICmp << '\n');
185  } else if (SE->isKnownPredicate(ICmpInst::getInversePredicate(Pred), S, X)) {
187  DeadInsts.emplace_back(ICmp);
188  DEBUG(dbgs() << "INDVARS: Eliminated comparison: " << *ICmp << '\n');
189  } else if (isa<PHINode>(IVOperand) &&
190  SE->isLoopInvariantPredicate(Pred, S, X, L, InvariantPredicate,
191  InvariantLHS, InvariantRHS)) {
192 
193  // Rewrite the comparison to a loop invariant comparison if it can be done
194  // cheaply, where cheaply means "we don't need to emit any new
195  // instructions".
196 
197  Value *NewLHS = nullptr, *NewRHS = nullptr;
198 
199  if (S == InvariantLHS || X == InvariantLHS)
200  NewLHS =
201  ICmp->getOperand(S == InvariantLHS ? IVOperIdx : (1 - IVOperIdx));
202 
203  if (S == InvariantRHS || X == InvariantRHS)
204  NewRHS =
205  ICmp->getOperand(S == InvariantRHS ? IVOperIdx : (1 - IVOperIdx));
206 
207  auto *PN = cast<PHINode>(IVOperand);
208  for (unsigned i = 0, e = PN->getNumIncomingValues();
209  i != e && (!NewLHS || !NewRHS);
210  ++i) {
211 
212  // If this is a value incoming from the backedge, then it cannot be a loop
213  // invariant value (since we know that IVOperand is an induction variable).
214  if (L->contains(PN->getIncomingBlock(i)))
215  continue;
216 
217  // NB! This following assert does not fundamentally have to be true, but
218  // it is true today given how SCEV analyzes induction variables.
219  // Specifically, today SCEV will *not* recognize %iv as an induction
220  // variable in the following case:
221  //
222  // define void @f(i32 %k) {
223  // entry:
224  // br i1 undef, label %r, label %l
225  //
226  // l:
227  // %k.inc.l = add i32 %k, 1
228  // br label %loop
229  //
230  // r:
231  // %k.inc.r = add i32 %k, 1
232  // br label %loop
233  //
234  // loop:
235  // %iv = phi i32 [ %k.inc.l, %l ], [ %k.inc.r, %r ], [ %iv.inc, %loop ]
236  // %iv.inc = add i32 %iv, 1
237  // br label %loop
238  // }
239  //
240  // but if it starts to, at some point, then the assertion below will have
241  // to be changed to a runtime check.
242 
243  Value *Incoming = PN->getIncomingValue(i);
244 
245 #ifndef NDEBUG
246  if (auto *I = dyn_cast<Instruction>(Incoming))
247  assert(DT->dominates(I, ICmp) && "Should be a unique loop dominating value!");
248 #endif
249 
250  const SCEV *IncomingS = SE->getSCEV(Incoming);
251 
252  if (!NewLHS && IncomingS == InvariantLHS)
253  NewLHS = Incoming;
254  if (!NewRHS && IncomingS == InvariantRHS)
255  NewRHS = Incoming;
256  }
257 
258  if (!NewLHS || !NewRHS)
259  // We could not find an existing value to replace either LHS or RHS.
260  // Generating new instructions has subtler tradeoffs, so avoid doing that
261  // for now.
262  return;
263 
264  DEBUG(dbgs() << "INDVARS: Simplified comparison: " << *ICmp << '\n');
265  ICmp->setPredicate(InvariantPredicate);
266  ICmp->setOperand(0, NewLHS);
267  ICmp->setOperand(1, NewRHS);
268  } else if (ICmpInst::isSigned(OriginalPred) &&
269  SE->isKnownNonNegative(S) && SE->isKnownNonNegative(X)) {
270  // If we were unable to make anything above, all we can is to canonicalize
271  // the comparison hoping that it will open the doors for other
272  // optimizations. If we find out that we compare two non-negative values,
273  // we turn the instruction's predicate to its unsigned version. Note that
274  // we cannot rely on Pred here unless we check if we have swapped it.
275  assert(ICmp->getPredicate() == OriginalPred && "Predicate changed?");
276  DEBUG(dbgs() << "INDVARS: Turn to unsigned comparison: " << *ICmp << '\n');
277  ICmp->setPredicate(ICmpInst::getUnsignedPredicate(OriginalPred));
278  } else
279  return;
280 
281  ++NumElimCmp;
282  Changed = true;
283 }
284 
285 bool SimplifyIndvar::eliminateSDiv(BinaryOperator *SDiv) {
286  // Get the SCEVs for the ICmp operands.
287  auto *N = SE->getSCEV(SDiv->getOperand(0));
288  auto *D = SE->getSCEV(SDiv->getOperand(1));
289 
290  // Simplify unnecessary loops away.
291  const Loop *L = LI->getLoopFor(SDiv->getParent());
292  N = SE->getSCEVAtScope(N, L);
293  D = SE->getSCEVAtScope(D, L);
294 
295  // Replace sdiv by udiv if both of the operands are non-negative
296  if (SE->isKnownNonNegative(N) && SE->isKnownNonNegative(D)) {
297  auto *UDiv = BinaryOperator::Create(
298  BinaryOperator::UDiv, SDiv->getOperand(0), SDiv->getOperand(1),
299  SDiv->getName() + ".udiv", SDiv);
300  UDiv->setIsExact(SDiv->isExact());
301  SDiv->replaceAllUsesWith(UDiv);
302  DEBUG(dbgs() << "INDVARS: Simplified sdiv: " << *SDiv << '\n');
303  ++NumSimplifiedSDiv;
304  Changed = true;
305  DeadInsts.push_back(SDiv);
306  return true;
307  }
308 
309  return false;
310 }
311 
312 /// SimplifyIVUsers helper for eliminating useless
313 /// remainder operations operating on an induction variable.
314 void SimplifyIndvar::eliminateIVRemainder(BinaryOperator *Rem,
315  Value *IVOperand,
316  bool IsSigned) {
317  // We're only interested in the case where we know something about
318  // the numerator.
319  if (IVOperand != Rem->getOperand(0))
320  return;
321 
322  // Get the SCEVs for the ICmp operands.
323  const SCEV *S = SE->getSCEV(Rem->getOperand(0));
324  const SCEV *X = SE->getSCEV(Rem->getOperand(1));
325 
326  // Simplify unnecessary loops away.
327  const Loop *ICmpLoop = LI->getLoopFor(Rem->getParent());
328  S = SE->getSCEVAtScope(S, ICmpLoop);
329  X = SE->getSCEVAtScope(X, ICmpLoop);
330 
331  // i % n --> i if i is in [0,n).
332  if ((!IsSigned || SE->isKnownNonNegative(S)) &&
333  SE->isKnownPredicate(IsSigned ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT,
334  S, X))
335  Rem->replaceAllUsesWith(Rem->getOperand(0));
336  else {
337  // (i+1) % n --> (i+1)==n?0:(i+1) if i is in [0,n).
338  const SCEV *LessOne = SE->getMinusSCEV(S, SE->getOne(S->getType()));
339  if (IsSigned && !SE->isKnownNonNegative(LessOne))
340  return;
341 
342  if (!SE->isKnownPredicate(IsSigned ?
343  ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT,
344  LessOne, X))
345  return;
346 
347  ICmpInst *ICmp = new ICmpInst(Rem, ICmpInst::ICMP_EQ,
348  Rem->getOperand(0), Rem->getOperand(1));
349  SelectInst *Sel =
350  SelectInst::Create(ICmp,
351  ConstantInt::get(Rem->getType(), 0),
352  Rem->getOperand(0), "tmp", Rem);
353  Rem->replaceAllUsesWith(Sel);
354  }
355 
356  DEBUG(dbgs() << "INDVARS: Simplified rem: " << *Rem << '\n');
357  ++NumElimRem;
358  Changed = true;
359  DeadInsts.emplace_back(Rem);
360 }
361 
362 bool SimplifyIndvar::eliminateOverflowIntrinsic(CallInst *CI) {
363  auto *F = CI->getCalledFunction();
364  if (!F)
365  return false;
366 
367  typedef const SCEV *(ScalarEvolution::*OperationFunctionTy)(
368  const SCEV *, const SCEV *, SCEV::NoWrapFlags, unsigned);
369  typedef const SCEV *(ScalarEvolution::*ExtensionFunctionTy)(
370  const SCEV *, Type *, unsigned);
371 
372  OperationFunctionTy Operation;
373  ExtensionFunctionTy Extension;
374 
376 
377  // We always have exactly one of nsw or nuw. If NoSignedOverflow is false, we
378  // have nuw.
379  bool NoSignedOverflow;
380 
381  switch (F->getIntrinsicID()) {
382  default:
383  return false;
384 
385  case Intrinsic::sadd_with_overflow:
386  Operation = &ScalarEvolution::getAddExpr;
388  RawOp = Instruction::Add;
389  NoSignedOverflow = true;
390  break;
391 
392  case Intrinsic::uadd_with_overflow:
393  Operation = &ScalarEvolution::getAddExpr;
395  RawOp = Instruction::Add;
396  NoSignedOverflow = false;
397  break;
398 
399  case Intrinsic::ssub_with_overflow:
400  Operation = &ScalarEvolution::getMinusSCEV;
402  RawOp = Instruction::Sub;
403  NoSignedOverflow = true;
404  break;
405 
406  case Intrinsic::usub_with_overflow:
407  Operation = &ScalarEvolution::getMinusSCEV;
409  RawOp = Instruction::Sub;
410  NoSignedOverflow = false;
411  break;
412  }
413 
414  const SCEV *LHS = SE->getSCEV(CI->getArgOperand(0));
415  const SCEV *RHS = SE->getSCEV(CI->getArgOperand(1));
416 
417  auto *NarrowTy = cast<IntegerType>(LHS->getType());
418  auto *WideTy =
419  IntegerType::get(NarrowTy->getContext(), NarrowTy->getBitWidth() * 2);
420 
421  const SCEV *A =
422  (SE->*Extension)((SE->*Operation)(LHS, RHS, SCEV::FlagAnyWrap, 0),
423  WideTy, 0);
424  const SCEV *B =
425  (SE->*Operation)((SE->*Extension)(LHS, WideTy, 0),
426  (SE->*Extension)(RHS, WideTy, 0), SCEV::FlagAnyWrap, 0);
427 
428  if (A != B)
429  return false;
430 
431  // Proved no overflow, nuke the overflow check and, if possible, the overflow
432  // intrinsic as well.
433 
435  RawOp, CI->getArgOperand(0), CI->getArgOperand(1), "", CI);
436 
437  if (NoSignedOverflow)
438  NewResult->setHasNoSignedWrap(true);
439  else
440  NewResult->setHasNoUnsignedWrap(true);
441 
443 
444  for (auto *U : CI->users()) {
445  if (auto *EVI = dyn_cast<ExtractValueInst>(U)) {
446  if (EVI->getIndices()[0] == 1)
447  EVI->replaceAllUsesWith(ConstantInt::getFalse(CI->getContext()));
448  else {
449  assert(EVI->getIndices()[0] == 0 && "Only two possibilities!");
450  EVI->replaceAllUsesWith(NewResult);
451  }
452  ToDelete.push_back(EVI);
453  }
454  }
455 
456  for (auto *EVI : ToDelete)
457  EVI->eraseFromParent();
458 
459  if (CI->use_empty())
460  CI->eraseFromParent();
461 
462  return true;
463 }
464 
465 /// Eliminate an operation that consumes a simple IV and has no observable
466 /// side-effect given the range of IV values. IVOperand is guaranteed SCEVable,
467 /// but UseInst may not be.
468 bool SimplifyIndvar::eliminateIVUser(Instruction *UseInst,
469  Instruction *IVOperand) {
470  if (ICmpInst *ICmp = dyn_cast<ICmpInst>(UseInst)) {
471  eliminateIVComparison(ICmp, IVOperand);
472  return true;
473  }
474  if (BinaryOperator *Bin = dyn_cast<BinaryOperator>(UseInst)) {
475  bool IsSRem = Bin->getOpcode() == Instruction::SRem;
476  if (IsSRem || Bin->getOpcode() == Instruction::URem) {
477  eliminateIVRemainder(Bin, IVOperand, IsSRem);
478  return true;
479  }
480 
481  if (Bin->getOpcode() == Instruction::SDiv)
482  return eliminateSDiv(Bin);
483  }
484 
485  if (auto *CI = dyn_cast<CallInst>(UseInst))
486  if (eliminateOverflowIntrinsic(CI))
487  return true;
488 
489  if (eliminateIdentitySCEV(UseInst, IVOperand))
490  return true;
491 
492  return false;
493 }
494 
495 /// Eliminate any operation that SCEV can prove is an identity function.
496 bool SimplifyIndvar::eliminateIdentitySCEV(Instruction *UseInst,
497  Instruction *IVOperand) {
498  if (!SE->isSCEVable(UseInst->getType()) ||
499  (UseInst->getType() != IVOperand->getType()) ||
500  (SE->getSCEV(UseInst) != SE->getSCEV(IVOperand)))
501  return false;
502 
503  // getSCEV(X) == getSCEV(Y) does not guarantee that X and Y are related in the
504  // dominator tree, even if X is an operand to Y. For instance, in
505  //
506  // %iv = phi i32 {0,+,1}
507  // br %cond, label %left, label %merge
508  //
509  // left:
510  // %X = add i32 %iv, 0
511  // br label %merge
512  //
513  // merge:
514  // %M = phi (%X, %iv)
515  //
516  // getSCEV(%M) == getSCEV(%X) == {0,+,1}, but %X does not dominate %M, and
517  // %M.replaceAllUsesWith(%X) would be incorrect.
518 
519  if (isa<PHINode>(UseInst))
520  // If UseInst is not a PHI node then we know that IVOperand dominates
521  // UseInst directly from the legality of SSA.
522  if (!DT || !DT->dominates(IVOperand, UseInst))
523  return false;
524 
525  if (!LI->replacementPreservesLCSSAForm(UseInst, IVOperand))
526  return false;
527 
528  DEBUG(dbgs() << "INDVARS: Eliminated identity: " << *UseInst << '\n');
529 
530  UseInst->replaceAllUsesWith(IVOperand);
531  ++NumElimIdentity;
532  Changed = true;
533  DeadInsts.emplace_back(UseInst);
534  return true;
535 }
536 
537 /// Annotate BO with nsw / nuw if it provably does not signed-overflow /
538 /// unsigned-overflow. Returns true if anything changed, false otherwise.
539 bool SimplifyIndvar::strengthenOverflowingOperation(BinaryOperator *BO,
540  Value *IVOperand) {
541 
542  // Fastpath: we don't have any work to do if `BO` is `nuw` and `nsw`.
543  if (BO->hasNoUnsignedWrap() && BO->hasNoSignedWrap())
544  return false;
545 
546  const SCEV *(ScalarEvolution::*GetExprForBO)(const SCEV *, const SCEV *,
547  SCEV::NoWrapFlags, unsigned);
548  switch (BO->getOpcode()) {
549  default:
550  return false;
551 
552  case Instruction::Add:
553  GetExprForBO = &ScalarEvolution::getAddExpr;
554  break;
555 
556  case Instruction::Sub:
557  GetExprForBO = &ScalarEvolution::getMinusSCEV;
558  break;
559 
560  case Instruction::Mul:
561  GetExprForBO = &ScalarEvolution::getMulExpr;
562  break;
563  }
564 
565  unsigned BitWidth = cast<IntegerType>(BO->getType())->getBitWidth();
566  Type *WideTy = IntegerType::get(BO->getContext(), BitWidth * 2);
567  const SCEV *LHS = SE->getSCEV(BO->getOperand(0));
568  const SCEV *RHS = SE->getSCEV(BO->getOperand(1));
569 
570  bool Changed = false;
571 
572  if (!BO->hasNoUnsignedWrap()) {
573  const SCEV *ExtendAfterOp = SE->getZeroExtendExpr(SE->getSCEV(BO), WideTy);
574  const SCEV *OpAfterExtend = (SE->*GetExprForBO)(
575  SE->getZeroExtendExpr(LHS, WideTy), SE->getZeroExtendExpr(RHS, WideTy),
576  SCEV::FlagAnyWrap, 0u);
577  if (ExtendAfterOp == OpAfterExtend) {
578  BO->setHasNoUnsignedWrap();
579  SE->forgetValue(BO);
580  Changed = true;
581  }
582  }
583 
584  if (!BO->hasNoSignedWrap()) {
585  const SCEV *ExtendAfterOp = SE->getSignExtendExpr(SE->getSCEV(BO), WideTy);
586  const SCEV *OpAfterExtend = (SE->*GetExprForBO)(
587  SE->getSignExtendExpr(LHS, WideTy), SE->getSignExtendExpr(RHS, WideTy),
588  SCEV::FlagAnyWrap, 0u);
589  if (ExtendAfterOp == OpAfterExtend) {
590  BO->setHasNoSignedWrap();
591  SE->forgetValue(BO);
592  Changed = true;
593  }
594  }
595 
596  return Changed;
597 }
598 
599 /// Annotate the Shr in (X << IVOperand) >> C as exact using the
600 /// information from the IV's range. Returns true if anything changed, false
601 /// otherwise.
602 bool SimplifyIndvar::strengthenRightShift(BinaryOperator *BO,
603  Value *IVOperand) {
604  using namespace llvm::PatternMatch;
605 
606  if (BO->getOpcode() == Instruction::Shl) {
607  bool Changed = false;
608  ConstantRange IVRange = SE->getUnsignedRange(SE->getSCEV(IVOperand));
609  for (auto *U : BO->users()) {
610  const APInt *C;
611  if (match(U,
612  m_AShr(m_Shl(m_Value(), m_Specific(IVOperand)), m_APInt(C))) ||
613  match(U,
614  m_LShr(m_Shl(m_Value(), m_Specific(IVOperand)), m_APInt(C)))) {
615  BinaryOperator *Shr = cast<BinaryOperator>(U);
616  if (!Shr->isExact() && IVRange.getUnsignedMin().uge(*C)) {
617  Shr->setIsExact(true);
618  Changed = true;
619  }
620  }
621  }
622  return Changed;
623  }
624 
625  return false;
626 }
627 
628 /// Add all uses of Def to the current IV's worklist.
629 static void pushIVUsers(
630  Instruction *Def,
632  SmallVectorImpl< std::pair<Instruction*,Instruction*> > &SimpleIVUsers) {
633 
634  for (User *U : Def->users()) {
635  Instruction *UI = cast<Instruction>(U);
636 
637  // Avoid infinite or exponential worklist processing.
638  // Also ensure unique worklist users.
639  // If Def is a LoopPhi, it may not be in the Simplified set, so check for
640  // self edges first.
641  if (UI != Def && Simplified.insert(UI).second)
642  SimpleIVUsers.push_back(std::make_pair(UI, Def));
643  }
644 }
645 
646 /// Return true if this instruction generates a simple SCEV
647 /// expression in terms of that IV.
648 ///
649 /// This is similar to IVUsers' isInteresting() but processes each instruction
650 /// non-recursively when the operand is already known to be a simpleIVUser.
651 ///
652 static bool isSimpleIVUser(Instruction *I, const Loop *L, ScalarEvolution *SE) {
653  if (!SE->isSCEVable(I->getType()))
654  return false;
655 
656  // Get the symbolic expression for this instruction.
657  const SCEV *S = SE->getSCEV(I);
658 
659  // Only consider affine recurrences.
660  const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(S);
661  if (AR && AR->getLoop() == L)
662  return true;
663 
664  return false;
665 }
666 
667 /// Iteratively perform simplification on a worklist of users
668 /// of the specified induction variable. Each successive simplification may push
669 /// more users which may themselves be candidates for simplification.
670 ///
671 /// This algorithm does not require IVUsers analysis. Instead, it simplifies
672 /// instructions in-place during analysis. Rather than rewriting induction
673 /// variables bottom-up from their users, it transforms a chain of IVUsers
674 /// top-down, updating the IR only when it encounters a clear optimization
675 /// opportunity.
676 ///
677 /// Once DisableIVRewrite is default, LSR will be the only client of IVUsers.
678 ///
679 void SimplifyIndvar::simplifyUsers(PHINode *CurrIV, IVVisitor *V) {
680  if (!SE->isSCEVable(CurrIV->getType()))
681  return;
682 
683  // Instructions processed by SimplifyIndvar for CurrIV.
685 
686  // Use-def pairs if IV users waiting to be processed for CurrIV.
688 
689  // Push users of the current LoopPhi. In rare cases, pushIVUsers may be
690  // called multiple times for the same LoopPhi. This is the proper thing to
691  // do for loop header phis that use each other.
692  pushIVUsers(CurrIV, Simplified, SimpleIVUsers);
693 
694  while (!SimpleIVUsers.empty()) {
695  std::pair<Instruction*, Instruction*> UseOper =
696  SimpleIVUsers.pop_back_val();
697  Instruction *UseInst = UseOper.first;
698 
699  // Bypass back edges to avoid extra work.
700  if (UseInst == CurrIV) continue;
701 
702  Instruction *IVOperand = UseOper.second;
703  for (unsigned N = 0; IVOperand; ++N) {
704  assert(N <= Simplified.size() && "runaway iteration");
705 
706  Value *NewOper = foldIVUser(UseOper.first, IVOperand);
707  if (!NewOper)
708  break; // done folding
709  IVOperand = dyn_cast<Instruction>(NewOper);
710  }
711  if (!IVOperand)
712  continue;
713 
714  if (eliminateIVUser(UseOper.first, IVOperand)) {
715  pushIVUsers(IVOperand, Simplified, SimpleIVUsers);
716  continue;
717  }
718 
719  if (BinaryOperator *BO = dyn_cast<BinaryOperator>(UseOper.first)) {
720  if ((isa<OverflowingBinaryOperator>(BO) &&
721  strengthenOverflowingOperation(BO, IVOperand)) ||
722  (isa<ShlOperator>(BO) && strengthenRightShift(BO, IVOperand))) {
723  // re-queue uses of the now modified binary operator and fall
724  // through to the checks that remain.
725  pushIVUsers(IVOperand, Simplified, SimpleIVUsers);
726  }
727  }
728 
729  CastInst *Cast = dyn_cast<CastInst>(UseOper.first);
730  if (V && Cast) {
731  V->visitCast(Cast);
732  continue;
733  }
734  if (isSimpleIVUser(UseOper.first, L, SE)) {
735  pushIVUsers(UseOper.first, Simplified, SimpleIVUsers);
736  }
737  }
738 }
739 
740 namespace llvm {
741 
743 
744 /// Simplify instructions that use this induction variable
745 /// by using ScalarEvolution to analyze the IV's recurrence.
748  IVVisitor *V) {
749  SimplifyIndvar SIV(LI->getLoopFor(CurrIV->getParent()), SE, DT, LI, Dead);
750  SIV.simplifyUsers(CurrIV, V);
751  return SIV.hasChanged();
752 }
753 
754 /// Simplify users of induction variables within this
755 /// loop. This does not actually change or add IVs.
758  bool Changed = false;
759  for (BasicBlock::iterator I = L->getHeader()->begin(); isa<PHINode>(I); ++I) {
760  Changed |= simplifyUsersOfIV(cast<PHINode>(I), SE, DT, LI, Dead);
761  }
762  return Changed;
763 }
764 
765 } // namespace llvm
static unsigned getBitWidth(Type *Ty, const DataLayout &DL)
Returns the bitwidth of the given scalar or pointer type.
uint64_t CallInst * C
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks &#39;this&#39; from the containing basic block and deletes it.
Definition: Instruction.cpp:69
static ConstantInt * getFalse(LLVMContext &Context)
Definition: Constants.cpp:523
class_match< Value > m_Value()
Match an arbitrary value and ignore it.
Definition: PatternMatch.h:72
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
BinaryOps getOpcode() const
Definition: InstrTypes.h:523
static void pushIVUsers(Instruction *Def, SmallPtrSet< Instruction *, 16 > &Simplified, SmallVectorImpl< std::pair< Instruction *, Instruction *> > &SimpleIVUsers)
Add all uses of Def to the current IV&#39;s worklist.
The main scalar evolution driver.
This class represents a function call, abstracting a target machine&#39;s calling convention.
unsigned less than
Definition: InstrTypes.h:885
BinaryOp_match< LHS, RHS, Instruction::AShr > m_AShr(const LHS &L, const RHS &R)
Definition: PatternMatch.h:580
virtual void anchor()
static SelectInst * Create(Value *C, Value *S1, Value *S2, const Twine &NameStr="", Instruction *InsertBefore=nullptr, Instruction *MDFrom=nullptr)
LLVMContext & getContext() const
All values hold a context through their type.
Definition: Value.cpp:697
STATISTIC(NumFunctions, "Total number of functions")
bool hasNoSignedWrap() const
Determine whether the no signed wrap flag is set.
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:252
bool match(Val *V, const Pattern &P)
Definition: PatternMatch.h:49
Interface for visiting interesting IV users that are recognized but not simplified by this utility...
bool isSigned() const
Determine if this instruction is using a signed comparison.
Definition: InstrTypes.h:1001
This class represents the LLVM &#39;select&#39; instruction.
Predicate getInversePredicate() const
For example, EQ -> NE, UGT -> ULE, SLT -> SGE, OEQ -> UNE, UGT -> OLE, OLT -> UGE, etc.
Definition: InstrTypes.h:958
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
Definition: LoopInfo.h:585
This is the base class for all instructions that perform data casts.
Definition: InstrTypes.h:560
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:42
BlockT * getHeader() const
Definition: LoopInfo.h:103
void setIsExact(bool b=true)
Set or clear the exact flag on this instruction, which must be an operator which supports this flag...
#define F(x, y, z)
Definition: MD5.cpp:55
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:245
bool simplifyUsersOfIV(PHINode *CurrIV, ScalarEvolution *SE, DominatorTree *DT, LoopInfo *LI, SmallVectorImpl< WeakTrackingVH > &Dead, IVVisitor *V=nullptr)
simplifyUsersOfIV - Simplify instructions that use this induction variable by using ScalarEvolution t...
This node represents a polynomial recurrence on the trip count of the specified loop.
bool simplifyLoopIVs(Loop *L, ScalarEvolution *SE, DominatorTree *DT, LoopInfo *LI, SmallVectorImpl< WeakTrackingVH > &Dead)
SimplifyLoopIVs - Simplify users of induction variables within this loop.
const APInt & getValue() const
Return the constant as an APInt value reference.
Definition: Constants.h:138
unsigned getOpcode() const
Returns a member of one of the enums like Instruction::Add.
Definition: Instruction.h:121
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition: Value.cpp:428
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree...
Definition: Dominators.h:134
APInt getUnsignedMin() const
Return the smallest unsigned value contained in the ConstantRange.
Value * getOperand(unsigned i) const
Definition: User.h:154
BinaryOp_match< LHS, RHS, Instruction::LShr > m_LShr(const LHS &L, const RHS &R)
Definition: PatternMatch.h:574
uint64_t getZExtValue() const
Return the constant as a 64-bit unsigned integer value after it has been zero extended as appropriate...
Definition: Constants.h:149
apint_match m_APInt(const APInt *&Res)
Match a ConstantInt or splatted ConstantVector, binding the specified pointer to the contained APInt...
Definition: PatternMatch.h:240
The instances of the Type class are immutable: once they are created, they are never changed...
Definition: Type.h:46
#define A
Definition: LargeTest.cpp:12
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:372
const SCEV * getAddExpr(SmallVectorImpl< const SCEV *> &Ops, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
Get a canonical add expression, or something simpler if possible.
static APInt getOneBitSet(unsigned numBits, unsigned BitNo)
Return an APInt with exactly one bit set in the result.
Definition: APInt.h:581
specificval_ty m_Specific(const Value *V)
Match if we have a specific specified value.
Definition: PatternMatch.h:358
BinaryOp_match< LHS, RHS, Instruction::Shl > m_Shl(const LHS &L, const RHS &R)
Definition: PatternMatch.h:568
This instruction compares its operands according to the predicate given to the constructor.
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Definition: InstrTypes.h:860
const SCEV * getMinusSCEV(const SCEV *LHS, const SCEV *RHS, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
Return LHS-RHS. Minus is represented in SCEV as A+B*-1.
bool isExact() const
Determine whether the exact flag is set.
const SCEV * getMulExpr(SmallVectorImpl< const SCEV *> &Ops, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
Get a canonical multiply expression, or something simpler if possible.
size_type size() const
Definition: SmallPtrSet.h:93
static IntegerType * get(LLVMContext &C, unsigned NumBits)
This static method is the primary way of constructing an IntegerType.
Definition: Type.cpp:240
void setHasNoSignedWrap(bool b=true)
Set or clear the nsw flag on this instruction, which must be an operator which supports this flag...
Iterator for intrusive lists based on ilist_node.
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements...
Definition: SmallPtrSet.h:423
This is the shared class of boolean and integer constants.
Definition: Constants.h:84
Type * getType() const
Return the LLVM type of this SCEV expression.
#define B
Definition: LargeTest.cpp:24
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:864
This class represents a range of values.
Definition: ConstantRange.h:47
signed less than
Definition: InstrTypes.h:889
const size_t N
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:385
static Constant * get(Type *Ty, uint64_t V, bool isSigned=false)
If Ty is a vector type, return a Constant with a splat of the given value.
Definition: Constants.cpp:560
bool uge(const APInt &RHS) const
Unsigned greater or equal comparison.
Definition: APInt.h:1272
static ConstantInt * getTrue(LLVMContext &Context)
Definition: Constants.cpp:516
void setPredicate(Predicate P)
Set the predicate for this instruction to the specified value.
Definition: InstrTypes.h:939
void setOperand(unsigned i, Value *Val)
Definition: User.h:159
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
static bool isSimpleIVUser(Instruction *I, const Loop *L, ScalarEvolution *SE)
Return true if this instruction generates a simple SCEV expression in terms of that IV...
Class for arbitrary precision integers.
Definition: APInt.h:69
static BinaryOperator * Create(BinaryOps Op, Value *S1, Value *S2, const Twine &Name=Twine(), Instruction *InsertBefore=nullptr)
Construct a binary instruction, given the opcode and the two operands.
iterator_range< user_iterator > users()
Definition: Value.h:395
Function * getCalledFunction() const
Return the function called, or null if this is an indirect function invocation.
Predicate getPredicate() const
Return the predicate for this instruction.
Definition: InstrTypes.h:934
This class represents an analyzed expression in the program.
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:61
virtual void visitCast(CastInst *Cast)=0
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:360
Value * getArgOperand(unsigned i) const
getArgOperand/setArgOperand - Return/set the i-th call argument.
StringRef getName() const
Return a constant reference to the value&#39;s name.
Definition: Value.cpp:218
#define I(x, y, z)
Definition: MD5.cpp:58
LLVM_NODISCARD std::enable_if<!is_simple_type< Y >::value, typename cast_retty< X, const Y >::ret_type >::type dyn_cast(const Y &Val)
Definition: Casting.h:323
bool hasNoUnsignedWrap() const
Determine whether the no unsigned wrap flag is set.
void setHasNoUnsignedWrap(bool b=true)
Set or clear the nsw flag on this instruction, which must be an operator which supports this flag...
Definition: Instruction.cpp:98
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
LLVM Value Representation.
Definition: Value.h:73
const SCEV * getSCEV(Value *V)
Return a SCEV expression for the full generality of the specified expression.
bool isSCEVable(Type *Ty) const
Test if values of the given type are analyzable within the SCEV framework.
#define DEBUG(X)
Definition: Debug.h:118
Predicate getSwappedPredicate() const
For example, EQ->EQ, SLE->SGE, ULT->UGT, OEQ->OEQ, ULE->UGE, OLT->OGT, etc.
Definition: InstrTypes.h:974
NoWrapFlags
NoWrapFlags are bitfield indices into SubclassData.
Predicate getUnsignedPredicate() const
For example, EQ->EQ, SLE->ULE, UGT->UGT, etc.
const SCEV * getZeroExtendExpr(const SCEV *Op, Type *Ty, unsigned Depth=0)
bool use_empty() const
Definition: Value.h:322
#define D
Definition: LargeTest.cpp:26
const SCEV * getSignExtendExpr(const SCEV *Op, Type *Ty, unsigned Depth=0)
const BasicBlock * getParent() const
Definition: Instruction.h:66