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(NumFoldedUser, "Number of IV users folded into a constant");
39 STATISTIC(NumElimRem , "Number of IV remainder operations eliminated");
40 STATISTIC(
41  NumSimplifiedSDiv,
42  "Number of IV signed division operations converted to unsigned division");
43 STATISTIC(
44  NumSimplifiedSRem,
45  "Number of IV signed remainder operations converted to unsigned remainder");
46 STATISTIC(NumElimCmp , "Number of IV comparisons eliminated");
47 
48 namespace {
49  /// This is a utility for simplifying induction variables
50  /// based on ScalarEvolution. It is the primary instrument of the
51  /// IndvarSimplify pass, but it may also be directly invoked to cleanup after
52  /// other loop passes that preserve SCEV.
53  class SimplifyIndvar {
54  Loop *L;
55  LoopInfo *LI;
56  ScalarEvolution *SE;
57  DominatorTree *DT;
60 
61  bool Changed;
62 
63  public:
64  SimplifyIndvar(Loop *Loop, ScalarEvolution *SE, DominatorTree *DT,
65  LoopInfo *LI, SCEVExpander &Rewriter,
67  : L(Loop), LI(LI), SE(SE), DT(DT), Rewriter(Rewriter), DeadInsts(Dead),
68  Changed(false) {
69  assert(LI && "IV simplification requires LoopInfo");
70  }
71 
72  bool hasChanged() const { return Changed; }
73 
74  /// Iteratively perform simplification on a worklist of users of the
75  /// specified induction variable. This is the top-level driver that applies
76  /// all simplifications to users of an IV.
77  void simplifyUsers(PHINode *CurrIV, IVVisitor *V = nullptr);
78 
79  Value *foldIVUser(Instruction *UseInst, Instruction *IVOperand);
80 
81  bool eliminateIdentitySCEV(Instruction *UseInst, Instruction *IVOperand);
82  bool replaceIVUserWithLoopInvariant(Instruction *UseInst);
83 
84  bool eliminateOverflowIntrinsic(CallInst *CI);
85  bool eliminateIVUser(Instruction *UseInst, Instruction *IVOperand);
86  bool makeIVComparisonInvariant(ICmpInst *ICmp, Value *IVOperand);
87  void eliminateIVComparison(ICmpInst *ICmp, Value *IVOperand);
88  void simplifyIVRemainder(BinaryOperator *Rem, Value *IVOperand,
89  bool IsSigned);
90  void replaceRemWithNumerator(BinaryOperator *Rem);
91  void replaceRemWithNumeratorOrZero(BinaryOperator *Rem);
92  void replaceSRemWithURem(BinaryOperator *Rem);
93  bool eliminateSDiv(BinaryOperator *SDiv);
94  bool strengthenOverflowingOperation(BinaryOperator *OBO, Value *IVOperand);
95  bool strengthenRightShift(BinaryOperator *BO, Value *IVOperand);
96  };
97 }
98 
99 /// Fold an IV operand into its use. This removes increments of an
100 /// aligned IV when used by a instruction that ignores the low bits.
101 ///
102 /// IVOperand is guaranteed SCEVable, but UseInst may not be.
103 ///
104 /// Return the operand of IVOperand for this induction variable if IVOperand can
105 /// be folded (in case more folding opportunities have been exposed).
106 /// Otherwise return null.
107 Value *SimplifyIndvar::foldIVUser(Instruction *UseInst, Instruction *IVOperand) {
108  Value *IVSrc = nullptr;
109  unsigned OperIdx = 0;
110  const SCEV *FoldedExpr = nullptr;
111  switch (UseInst->getOpcode()) {
112  default:
113  return nullptr;
114  case Instruction::UDiv:
115  case Instruction::LShr:
116  // We're only interested in the case where we know something about
117  // the numerator and have a constant denominator.
118  if (IVOperand != UseInst->getOperand(OperIdx) ||
119  !isa<ConstantInt>(UseInst->getOperand(1)))
120  return nullptr;
121 
122  // Attempt to fold a binary operator with constant operand.
123  // e.g. ((I + 1) >> 2) => I >> 2
124  if (!isa<BinaryOperator>(IVOperand)
125  || !isa<ConstantInt>(IVOperand->getOperand(1)))
126  return nullptr;
127 
128  IVSrc = IVOperand->getOperand(0);
129  // IVSrc must be the (SCEVable) IV, since the other operand is const.
130  assert(SE->isSCEVable(IVSrc->getType()) && "Expect SCEVable IV operand");
131 
132  ConstantInt *D = cast<ConstantInt>(UseInst->getOperand(1));
133  if (UseInst->getOpcode() == Instruction::LShr) {
134  // Get a constant for the divisor. See createSCEV.
135  uint32_t BitWidth = cast<IntegerType>(UseInst->getType())->getBitWidth();
136  if (D->getValue().uge(BitWidth))
137  return nullptr;
138 
139  D = ConstantInt::get(UseInst->getContext(),
140  APInt::getOneBitSet(BitWidth, D->getZExtValue()));
141  }
142  FoldedExpr = SE->getUDivExpr(SE->getSCEV(IVSrc), SE->getSCEV(D));
143  }
144  // We have something that might fold it's operand. Compare SCEVs.
145  if (!SE->isSCEVable(UseInst->getType()))
146  return nullptr;
147 
148  // Bypass the operand if SCEV can prove it has no effect.
149  if (SE->getSCEV(UseInst) != FoldedExpr)
150  return nullptr;
151 
152  DEBUG(dbgs() << "INDVARS: Eliminated IV operand: " << *IVOperand
153  << " -> " << *UseInst << '\n');
154 
155  UseInst->setOperand(OperIdx, IVSrc);
156  assert(SE->getSCEV(UseInst) == FoldedExpr && "bad SCEV with folded oper");
157 
158  ++NumElimOperand;
159  Changed = true;
160  if (IVOperand->use_empty())
161  DeadInsts.emplace_back(IVOperand);
162  return IVSrc;
163 }
164 
165 bool SimplifyIndvar::makeIVComparisonInvariant(ICmpInst *ICmp,
166  Value *IVOperand) {
167  unsigned IVOperIdx = 0;
168  ICmpInst::Predicate Pred = ICmp->getPredicate();
169  if (IVOperand != ICmp->getOperand(0)) {
170  // Swapped
171  assert(IVOperand == ICmp->getOperand(1) && "Can't find IVOperand");
172  IVOperIdx = 1;
173  Pred = ICmpInst::getSwappedPredicate(Pred);
174  }
175 
176  // Get the SCEVs for the ICmp operands (in the specific context of the
177  // current loop)
178  const Loop *ICmpLoop = LI->getLoopFor(ICmp->getParent());
179  const SCEV *S = SE->getSCEVAtScope(ICmp->getOperand(IVOperIdx), ICmpLoop);
180  const SCEV *X = SE->getSCEVAtScope(ICmp->getOperand(1 - IVOperIdx), ICmpLoop);
181 
182  ICmpInst::Predicate InvariantPredicate;
183  const SCEV *InvariantLHS, *InvariantRHS;
184 
185  auto *PN = dyn_cast<PHINode>(IVOperand);
186  if (!PN)
187  return false;
188  if (!SE->isLoopInvariantPredicate(Pred, S, X, L, InvariantPredicate,
189  InvariantLHS, InvariantRHS))
190  return false;
191 
192  // Rewrite the comparison to a loop invariant comparison if it can be done
193  // cheaply, where cheaply means "we don't need to emit any new
194  // instructions".
195 
196  SmallDenseMap<const SCEV*, Value*> CheapExpansions;
197  CheapExpansions[S] = ICmp->getOperand(IVOperIdx);
198  CheapExpansions[X] = ICmp->getOperand(1 - IVOperIdx);
199 
200  // TODO: Support multiple entry loops? (We currently bail out of these in
201  // the IndVarSimplify pass)
202  if (auto *BB = L->getLoopPredecessor()) {
203  Value *Incoming = PN->getIncomingValueForBlock(BB);
204  const SCEV *IncomingS = SE->getSCEV(Incoming);
205  CheapExpansions[IncomingS] = Incoming;
206  }
207  Value *NewLHS = CheapExpansions[InvariantLHS];
208  Value *NewRHS = CheapExpansions[InvariantRHS];
209 
210  if (!NewLHS || !NewRHS)
211  // We could not find an existing value to replace either LHS or RHS.
212  // Generating new instructions has subtler tradeoffs, so avoid doing that
213  // for now.
214  return false;
215 
216  DEBUG(dbgs() << "INDVARS: Simplified comparison: " << *ICmp << '\n');
217  ICmp->setPredicate(InvariantPredicate);
218  ICmp->setOperand(0, NewLHS);
219  ICmp->setOperand(1, NewRHS);
220  return true;
221 }
222 
223 /// SimplifyIVUsers helper for eliminating useless
224 /// comparisons against an induction variable.
225 void SimplifyIndvar::eliminateIVComparison(ICmpInst *ICmp, Value *IVOperand) {
226  unsigned IVOperIdx = 0;
227  ICmpInst::Predicate Pred = ICmp->getPredicate();
228  ICmpInst::Predicate OriginalPred = Pred;
229  if (IVOperand != ICmp->getOperand(0)) {
230  // Swapped
231  assert(IVOperand == ICmp->getOperand(1) && "Can't find IVOperand");
232  IVOperIdx = 1;
233  Pred = ICmpInst::getSwappedPredicate(Pred);
234  }
235 
236  // Get the SCEVs for the ICmp operands (in the specific context of the
237  // current loop)
238  const Loop *ICmpLoop = LI->getLoopFor(ICmp->getParent());
239  const SCEV *S = SE->getSCEVAtScope(ICmp->getOperand(IVOperIdx), ICmpLoop);
240  const SCEV *X = SE->getSCEVAtScope(ICmp->getOperand(1 - IVOperIdx), ICmpLoop);
241 
242  // If the condition is always true or always false, replace it with
243  // a constant value.
244  if (SE->isKnownPredicate(Pred, S, X)) {
246  DeadInsts.emplace_back(ICmp);
247  DEBUG(dbgs() << "INDVARS: Eliminated comparison: " << *ICmp << '\n');
248  } else if (SE->isKnownPredicate(ICmpInst::getInversePredicate(Pred), S, X)) {
250  DeadInsts.emplace_back(ICmp);
251  DEBUG(dbgs() << "INDVARS: Eliminated comparison: " << *ICmp << '\n');
252  } else if (makeIVComparisonInvariant(ICmp, IVOperand)) {
253  // fallthrough to end of function
254  } else if (ICmpInst::isSigned(OriginalPred) &&
255  SE->isKnownNonNegative(S) && SE->isKnownNonNegative(X)) {
256  // If we were unable to make anything above, all we can is to canonicalize
257  // the comparison hoping that it will open the doors for other
258  // optimizations. If we find out that we compare two non-negative values,
259  // we turn the instruction's predicate to its unsigned version. Note that
260  // we cannot rely on Pred here unless we check if we have swapped it.
261  assert(ICmp->getPredicate() == OriginalPred && "Predicate changed?");
262  DEBUG(dbgs() << "INDVARS: Turn to unsigned comparison: " << *ICmp << '\n');
263  ICmp->setPredicate(ICmpInst::getUnsignedPredicate(OriginalPred));
264  } else
265  return;
266 
267  ++NumElimCmp;
268  Changed = true;
269 }
270 
271 bool SimplifyIndvar::eliminateSDiv(BinaryOperator *SDiv) {
272  // Get the SCEVs for the ICmp operands.
273  auto *N = SE->getSCEV(SDiv->getOperand(0));
274  auto *D = SE->getSCEV(SDiv->getOperand(1));
275 
276  // Simplify unnecessary loops away.
277  const Loop *L = LI->getLoopFor(SDiv->getParent());
278  N = SE->getSCEVAtScope(N, L);
279  D = SE->getSCEVAtScope(D, L);
280 
281  // Replace sdiv by udiv if both of the operands are non-negative
282  if (SE->isKnownNonNegative(N) && SE->isKnownNonNegative(D)) {
283  auto *UDiv = BinaryOperator::Create(
284  BinaryOperator::UDiv, SDiv->getOperand(0), SDiv->getOperand(1),
285  SDiv->getName() + ".udiv", SDiv);
286  UDiv->setIsExact(SDiv->isExact());
287  SDiv->replaceAllUsesWith(UDiv);
288  DEBUG(dbgs() << "INDVARS: Simplified sdiv: " << *SDiv << '\n');
289  ++NumSimplifiedSDiv;
290  Changed = true;
291  DeadInsts.push_back(SDiv);
292  return true;
293  }
294 
295  return false;
296 }
297 
298 // i %s n -> i %u n if i >= 0 and n >= 0
299 void SimplifyIndvar::replaceSRemWithURem(BinaryOperator *Rem) {
300  auto *N = Rem->getOperand(0), *D = Rem->getOperand(1);
301  auto *URem = BinaryOperator::Create(BinaryOperator::URem, N, D,
302  Rem->getName() + ".urem", Rem);
303  Rem->replaceAllUsesWith(URem);
304  DEBUG(dbgs() << "INDVARS: Simplified srem: " << *Rem << '\n');
305  ++NumSimplifiedSRem;
306  Changed = true;
307  DeadInsts.emplace_back(Rem);
308 }
309 
310 // i % n --> i if i is in [0,n).
311 void SimplifyIndvar::replaceRemWithNumerator(BinaryOperator *Rem) {
312  Rem->replaceAllUsesWith(Rem->getOperand(0));
313  DEBUG(dbgs() << "INDVARS: Simplified rem: " << *Rem << '\n');
314  ++NumElimRem;
315  Changed = true;
316  DeadInsts.emplace_back(Rem);
317 }
318 
319 // (i+1) % n --> (i+1)==n?0:(i+1) if i is in [0,n).
320 void SimplifyIndvar::replaceRemWithNumeratorOrZero(BinaryOperator *Rem) {
321  auto *T = Rem->getType();
322  auto *N = Rem->getOperand(0), *D = Rem->getOperand(1);
323  ICmpInst *ICmp = new ICmpInst(Rem, ICmpInst::ICMP_EQ, N, D);
324  SelectInst *Sel =
325  SelectInst::Create(ICmp, ConstantInt::get(T, 0), N, "iv.rem", Rem);
326  Rem->replaceAllUsesWith(Sel);
327  DEBUG(dbgs() << "INDVARS: Simplified rem: " << *Rem << '\n');
328  ++NumElimRem;
329  Changed = true;
330  DeadInsts.emplace_back(Rem);
331 }
332 
333 /// SimplifyIVUsers helper for eliminating useless remainder operations
334 /// operating on an induction variable or replacing srem by urem.
335 void SimplifyIndvar::simplifyIVRemainder(BinaryOperator *Rem, Value *IVOperand,
336  bool IsSigned) {
337  auto *NValue = Rem->getOperand(0);
338  auto *DValue = Rem->getOperand(1);
339  // We're only interested in the case where we know something about
340  // the numerator, unless it is a srem, because we want to replace srem by urem
341  // in general.
342  bool UsedAsNumerator = IVOperand == NValue;
343  if (!UsedAsNumerator && !IsSigned)
344  return;
345 
346  const SCEV *N = SE->getSCEV(NValue);
347 
348  // Simplify unnecessary loops away.
349  const Loop *ICmpLoop = LI->getLoopFor(Rem->getParent());
350  N = SE->getSCEVAtScope(N, ICmpLoop);
351 
352  bool IsNumeratorNonNegative = !IsSigned || SE->isKnownNonNegative(N);
353 
354  // Do not proceed if the Numerator may be negative
355  if (!IsNumeratorNonNegative)
356  return;
357 
358  const SCEV *D = SE->getSCEV(DValue);
359  D = SE->getSCEVAtScope(D, ICmpLoop);
360 
361  if (UsedAsNumerator) {
362  auto LT = IsSigned ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT;
363  if (SE->isKnownPredicate(LT, N, D)) {
364  replaceRemWithNumerator(Rem);
365  return;
366  }
367 
368  auto *T = Rem->getType();
369  const auto *NLessOne = SE->getMinusSCEV(N, SE->getOne(T));
370  if (SE->isKnownPredicate(LT, NLessOne, D)) {
371  replaceRemWithNumeratorOrZero(Rem);
372  return;
373  }
374  }
375 
376  // Try to replace SRem with URem, if both N and D are known non-negative.
377  // Since we had already check N, we only need to check D now
378  if (!IsSigned || !SE->isKnownNonNegative(D))
379  return;
380 
381  replaceSRemWithURem(Rem);
382 }
383 
384 bool SimplifyIndvar::eliminateOverflowIntrinsic(CallInst *CI) {
385  auto *F = CI->getCalledFunction();
386  if (!F)
387  return false;
388 
389  typedef const SCEV *(ScalarEvolution::*OperationFunctionTy)(
390  const SCEV *, const SCEV *, SCEV::NoWrapFlags, unsigned);
391  typedef const SCEV *(ScalarEvolution::*ExtensionFunctionTy)(
392  const SCEV *, Type *, unsigned);
393 
394  OperationFunctionTy Operation;
395  ExtensionFunctionTy Extension;
396 
398 
399  // We always have exactly one of nsw or nuw. If NoSignedOverflow is false, we
400  // have nuw.
401  bool NoSignedOverflow;
402 
403  switch (F->getIntrinsicID()) {
404  default:
405  return false;
406 
407  case Intrinsic::sadd_with_overflow:
408  Operation = &ScalarEvolution::getAddExpr;
410  RawOp = Instruction::Add;
411  NoSignedOverflow = true;
412  break;
413 
414  case Intrinsic::uadd_with_overflow:
415  Operation = &ScalarEvolution::getAddExpr;
417  RawOp = Instruction::Add;
418  NoSignedOverflow = false;
419  break;
420 
421  case Intrinsic::ssub_with_overflow:
422  Operation = &ScalarEvolution::getMinusSCEV;
424  RawOp = Instruction::Sub;
425  NoSignedOverflow = true;
426  break;
427 
428  case Intrinsic::usub_with_overflow:
429  Operation = &ScalarEvolution::getMinusSCEV;
431  RawOp = Instruction::Sub;
432  NoSignedOverflow = false;
433  break;
434  }
435 
436  const SCEV *LHS = SE->getSCEV(CI->getArgOperand(0));
437  const SCEV *RHS = SE->getSCEV(CI->getArgOperand(1));
438 
439  auto *NarrowTy = cast<IntegerType>(LHS->getType());
440  auto *WideTy =
441  IntegerType::get(NarrowTy->getContext(), NarrowTy->getBitWidth() * 2);
442 
443  const SCEV *A =
444  (SE->*Extension)((SE->*Operation)(LHS, RHS, SCEV::FlagAnyWrap, 0),
445  WideTy, 0);
446  const SCEV *B =
447  (SE->*Operation)((SE->*Extension)(LHS, WideTy, 0),
448  (SE->*Extension)(RHS, WideTy, 0), SCEV::FlagAnyWrap, 0);
449 
450  if (A != B)
451  return false;
452 
453  // Proved no overflow, nuke the overflow check and, if possible, the overflow
454  // intrinsic as well.
455 
457  RawOp, CI->getArgOperand(0), CI->getArgOperand(1), "", CI);
458 
459  if (NoSignedOverflow)
460  NewResult->setHasNoSignedWrap(true);
461  else
462  NewResult->setHasNoUnsignedWrap(true);
463 
465 
466  for (auto *U : CI->users()) {
467  if (auto *EVI = dyn_cast<ExtractValueInst>(U)) {
468  if (EVI->getIndices()[0] == 1)
469  EVI->replaceAllUsesWith(ConstantInt::getFalse(CI->getContext()));
470  else {
471  assert(EVI->getIndices()[0] == 0 && "Only two possibilities!");
472  EVI->replaceAllUsesWith(NewResult);
473  }
474  ToDelete.push_back(EVI);
475  }
476  }
477 
478  for (auto *EVI : ToDelete)
479  EVI->eraseFromParent();
480 
481  if (CI->use_empty())
482  CI->eraseFromParent();
483 
484  return true;
485 }
486 
487 /// Eliminate an operation that consumes a simple IV and has no observable
488 /// side-effect given the range of IV values. IVOperand is guaranteed SCEVable,
489 /// but UseInst may not be.
490 bool SimplifyIndvar::eliminateIVUser(Instruction *UseInst,
491  Instruction *IVOperand) {
492  if (ICmpInst *ICmp = dyn_cast<ICmpInst>(UseInst)) {
493  eliminateIVComparison(ICmp, IVOperand);
494  return true;
495  }
496  if (BinaryOperator *Bin = dyn_cast<BinaryOperator>(UseInst)) {
497  bool IsSRem = Bin->getOpcode() == Instruction::SRem;
498  if (IsSRem || Bin->getOpcode() == Instruction::URem) {
499  simplifyIVRemainder(Bin, IVOperand, IsSRem);
500  return true;
501  }
502 
503  if (Bin->getOpcode() == Instruction::SDiv)
504  return eliminateSDiv(Bin);
505  }
506 
507  if (auto *CI = dyn_cast<CallInst>(UseInst))
508  if (eliminateOverflowIntrinsic(CI))
509  return true;
510 
511  if (eliminateIdentitySCEV(UseInst, IVOperand))
512  return true;
513 
514  return false;
515 }
516 
518  if (auto *BB = L->getLoopPreheader())
519  return BB->getTerminator();
520 
521  return Hint;
522 }
523 
524 /// Replace the UseInst with a constant if possible.
525 bool SimplifyIndvar::replaceIVUserWithLoopInvariant(Instruction *I) {
526  if (!SE->isSCEVable(I->getType()))
527  return false;
528 
529  // Get the symbolic expression for this instruction.
530  const SCEV *S = SE->getSCEV(I);
531 
532  if (!SE->isLoopInvariant(S, L))
533  return false;
534 
535  // Do not generate something ridiculous even if S is loop invariant.
536  if (Rewriter.isHighCostExpansion(S, L, I))
537  return false;
538 
539  auto *IP = GetLoopInvariantInsertPosition(L, I);
540  auto *Invariant = Rewriter.expandCodeFor(S, I->getType(), IP);
541 
542  I->replaceAllUsesWith(Invariant);
543  DEBUG(dbgs() << "INDVARS: Replace IV user: " << *I
544  << " with loop invariant: " << *S << '\n');
545  ++NumFoldedUser;
546  Changed = true;
547  DeadInsts.emplace_back(I);
548  return true;
549 }
550 
551 /// Eliminate any operation that SCEV can prove is an identity function.
552 bool SimplifyIndvar::eliminateIdentitySCEV(Instruction *UseInst,
553  Instruction *IVOperand) {
554  if (!SE->isSCEVable(UseInst->getType()) ||
555  (UseInst->getType() != IVOperand->getType()) ||
556  (SE->getSCEV(UseInst) != SE->getSCEV(IVOperand)))
557  return false;
558 
559  // getSCEV(X) == getSCEV(Y) does not guarantee that X and Y are related in the
560  // dominator tree, even if X is an operand to Y. For instance, in
561  //
562  // %iv = phi i32 {0,+,1}
563  // br %cond, label %left, label %merge
564  //
565  // left:
566  // %X = add i32 %iv, 0
567  // br label %merge
568  //
569  // merge:
570  // %M = phi (%X, %iv)
571  //
572  // getSCEV(%M) == getSCEV(%X) == {0,+,1}, but %X does not dominate %M, and
573  // %M.replaceAllUsesWith(%X) would be incorrect.
574 
575  if (isa<PHINode>(UseInst))
576  // If UseInst is not a PHI node then we know that IVOperand dominates
577  // UseInst directly from the legality of SSA.
578  if (!DT || !DT->dominates(IVOperand, UseInst))
579  return false;
580 
581  if (!LI->replacementPreservesLCSSAForm(UseInst, IVOperand))
582  return false;
583 
584  DEBUG(dbgs() << "INDVARS: Eliminated identity: " << *UseInst << '\n');
585 
586  UseInst->replaceAllUsesWith(IVOperand);
587  ++NumElimIdentity;
588  Changed = true;
589  DeadInsts.emplace_back(UseInst);
590  return true;
591 }
592 
593 /// Annotate BO with nsw / nuw if it provably does not signed-overflow /
594 /// unsigned-overflow. Returns true if anything changed, false otherwise.
595 bool SimplifyIndvar::strengthenOverflowingOperation(BinaryOperator *BO,
596  Value *IVOperand) {
597 
598  // Fastpath: we don't have any work to do if `BO` is `nuw` and `nsw`.
599  if (BO->hasNoUnsignedWrap() && BO->hasNoSignedWrap())
600  return false;
601 
602  const SCEV *(ScalarEvolution::*GetExprForBO)(const SCEV *, const SCEV *,
603  SCEV::NoWrapFlags, unsigned);
604  switch (BO->getOpcode()) {
605  default:
606  return false;
607 
608  case Instruction::Add:
609  GetExprForBO = &ScalarEvolution::getAddExpr;
610  break;
611 
612  case Instruction::Sub:
613  GetExprForBO = &ScalarEvolution::getMinusSCEV;
614  break;
615 
616  case Instruction::Mul:
617  GetExprForBO = &ScalarEvolution::getMulExpr;
618  break;
619  }
620 
621  unsigned BitWidth = cast<IntegerType>(BO->getType())->getBitWidth();
622  Type *WideTy = IntegerType::get(BO->getContext(), BitWidth * 2);
623  const SCEV *LHS = SE->getSCEV(BO->getOperand(0));
624  const SCEV *RHS = SE->getSCEV(BO->getOperand(1));
625 
626  bool Changed = false;
627 
628  if (!BO->hasNoUnsignedWrap()) {
629  const SCEV *ExtendAfterOp = SE->getZeroExtendExpr(SE->getSCEV(BO), WideTy);
630  const SCEV *OpAfterExtend = (SE->*GetExprForBO)(
631  SE->getZeroExtendExpr(LHS, WideTy), SE->getZeroExtendExpr(RHS, WideTy),
632  SCEV::FlagAnyWrap, 0u);
633  if (ExtendAfterOp == OpAfterExtend) {
634  BO->setHasNoUnsignedWrap();
635  SE->forgetValue(BO);
636  Changed = true;
637  }
638  }
639 
640  if (!BO->hasNoSignedWrap()) {
641  const SCEV *ExtendAfterOp = SE->getSignExtendExpr(SE->getSCEV(BO), WideTy);
642  const SCEV *OpAfterExtend = (SE->*GetExprForBO)(
643  SE->getSignExtendExpr(LHS, WideTy), SE->getSignExtendExpr(RHS, WideTy),
644  SCEV::FlagAnyWrap, 0u);
645  if (ExtendAfterOp == OpAfterExtend) {
646  BO->setHasNoSignedWrap();
647  SE->forgetValue(BO);
648  Changed = true;
649  }
650  }
651 
652  return Changed;
653 }
654 
655 /// Annotate the Shr in (X << IVOperand) >> C as exact using the
656 /// information from the IV's range. Returns true if anything changed, false
657 /// otherwise.
658 bool SimplifyIndvar::strengthenRightShift(BinaryOperator *BO,
659  Value *IVOperand) {
660  using namespace llvm::PatternMatch;
661 
662  if (BO->getOpcode() == Instruction::Shl) {
663  bool Changed = false;
664  ConstantRange IVRange = SE->getUnsignedRange(SE->getSCEV(IVOperand));
665  for (auto *U : BO->users()) {
666  const APInt *C;
667  if (match(U,
668  m_AShr(m_Shl(m_Value(), m_Specific(IVOperand)), m_APInt(C))) ||
669  match(U,
670  m_LShr(m_Shl(m_Value(), m_Specific(IVOperand)), m_APInt(C)))) {
671  BinaryOperator *Shr = cast<BinaryOperator>(U);
672  if (!Shr->isExact() && IVRange.getUnsignedMin().uge(*C)) {
673  Shr->setIsExact(true);
674  Changed = true;
675  }
676  }
677  }
678  return Changed;
679  }
680 
681  return false;
682 }
683 
684 /// Add all uses of Def to the current IV's worklist.
685 static void pushIVUsers(
686  Instruction *Def, Loop *L,
688  SmallVectorImpl< std::pair<Instruction*,Instruction*> > &SimpleIVUsers) {
689 
690  for (User *U : Def->users()) {
691  Instruction *UI = cast<Instruction>(U);
692 
693  // Avoid infinite or exponential worklist processing.
694  // Also ensure unique worklist users.
695  // If Def is a LoopPhi, it may not be in the Simplified set, so check for
696  // self edges first.
697  if (UI == Def)
698  continue;
699 
700  // Only change the current Loop, do not change the other parts (e.g. other
701  // Loops).
702  if (!L->contains(UI))
703  continue;
704 
705  // Do not push the same instruction more than once.
706  if (!Simplified.insert(UI).second)
707  continue;
708 
709  SimpleIVUsers.push_back(std::make_pair(UI, Def));
710  }
711 }
712 
713 /// Return true if this instruction generates a simple SCEV
714 /// expression in terms of that IV.
715 ///
716 /// This is similar to IVUsers' isInteresting() but processes each instruction
717 /// non-recursively when the operand is already known to be a simpleIVUser.
718 ///
719 static bool isSimpleIVUser(Instruction *I, const Loop *L, ScalarEvolution *SE) {
720  if (!SE->isSCEVable(I->getType()))
721  return false;
722 
723  // Get the symbolic expression for this instruction.
724  const SCEV *S = SE->getSCEV(I);
725 
726  // Only consider affine recurrences.
727  const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(S);
728  if (AR && AR->getLoop() == L)
729  return true;
730 
731  return false;
732 }
733 
734 /// Iteratively perform simplification on a worklist of users
735 /// of the specified induction variable. Each successive simplification may push
736 /// more users which may themselves be candidates for simplification.
737 ///
738 /// This algorithm does not require IVUsers analysis. Instead, it simplifies
739 /// instructions in-place during analysis. Rather than rewriting induction
740 /// variables bottom-up from their users, it transforms a chain of IVUsers
741 /// top-down, updating the IR only when it encounters a clear optimization
742 /// opportunity.
743 ///
744 /// Once DisableIVRewrite is default, LSR will be the only client of IVUsers.
745 ///
746 void SimplifyIndvar::simplifyUsers(PHINode *CurrIV, IVVisitor *V) {
747  if (!SE->isSCEVable(CurrIV->getType()))
748  return;
749 
750  // Instructions processed by SimplifyIndvar for CurrIV.
752 
753  // Use-def pairs if IV users waiting to be processed for CurrIV.
755 
756  // Push users of the current LoopPhi. In rare cases, pushIVUsers may be
757  // called multiple times for the same LoopPhi. This is the proper thing to
758  // do for loop header phis that use each other.
759  pushIVUsers(CurrIV, L, Simplified, SimpleIVUsers);
760 
761  while (!SimpleIVUsers.empty()) {
762  std::pair<Instruction*, Instruction*> UseOper =
763  SimpleIVUsers.pop_back_val();
764  Instruction *UseInst = UseOper.first;
765 
766  // Bypass back edges to avoid extra work.
767  if (UseInst == CurrIV) continue;
768 
769  // Try to replace UseInst with a loop invariant before any other
770  // simplifications.
771  if (replaceIVUserWithLoopInvariant(UseInst))
772  continue;
773 
774  Instruction *IVOperand = UseOper.second;
775  for (unsigned N = 0; IVOperand; ++N) {
776  assert(N <= Simplified.size() && "runaway iteration");
777 
778  Value *NewOper = foldIVUser(UseOper.first, IVOperand);
779  if (!NewOper)
780  break; // done folding
781  IVOperand = dyn_cast<Instruction>(NewOper);
782  }
783  if (!IVOperand)
784  continue;
785 
786  if (eliminateIVUser(UseOper.first, IVOperand)) {
787  pushIVUsers(IVOperand, L, Simplified, SimpleIVUsers);
788  continue;
789  }
790 
791  if (BinaryOperator *BO = dyn_cast<BinaryOperator>(UseOper.first)) {
792  if ((isa<OverflowingBinaryOperator>(BO) &&
793  strengthenOverflowingOperation(BO, IVOperand)) ||
794  (isa<ShlOperator>(BO) && strengthenRightShift(BO, IVOperand))) {
795  // re-queue uses of the now modified binary operator and fall
796  // through to the checks that remain.
797  pushIVUsers(IVOperand, L, Simplified, SimpleIVUsers);
798  }
799  }
800 
801  CastInst *Cast = dyn_cast<CastInst>(UseOper.first);
802  if (V && Cast) {
803  V->visitCast(Cast);
804  continue;
805  }
806  if (isSimpleIVUser(UseOper.first, L, SE)) {
807  pushIVUsers(UseOper.first, L, Simplified, SimpleIVUsers);
808  }
809  }
810 }
811 
812 namespace llvm {
813 
815 
816 /// Simplify instructions that use this induction variable
817 /// by using ScalarEvolution to analyze the IV's recurrence.
821  SimplifyIndvar SIV(LI->getLoopFor(CurrIV->getParent()), SE, DT, LI, Rewriter,
822  Dead);
823  SIV.simplifyUsers(CurrIV, V);
824  return SIV.hasChanged();
825 }
826 
827 /// Simplify users of induction variables within this
828 /// loop. This does not actually change or add IVs.
831  SCEVExpander Rewriter(*SE, SE->getDataLayout(), "indvars");
832 #ifndef NDEBUG
833  Rewriter.setDebugType(DEBUG_TYPE);
834 #endif
835  bool Changed = false;
836  for (BasicBlock::iterator I = L->getHeader()->begin(); isa<PHINode>(I); ++I) {
837  Changed |= simplifyUsersOfIV(cast<PHINode>(I), SE, DT, LI, Dead, Rewriter);
838  }
839  return Changed;
840 }
841 
842 } // 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
The main scalar evolution driver.
This class represents a function call, abstracting a target machine&#39;s calling convention.
BlockT * getLoopPreheader() const
If there is a preheader for this loop, return it.
Definition: LoopInfoImpl.h:106
unsigned less than
Definition: InstrTypes.h:878
BinaryOp_match< LHS, RHS, Instruction::AShr > m_AShr(const LHS &L, const RHS &R)
Definition: PatternMatch.h:604
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:728
STATISTIC(NumFunctions, "Total number of functions")
F(f)
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:994
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:951
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
Definition: LoopInfo.h:678
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:100
void setIsExact(bool b=true)
Set or clear the exact flag on this instruction, which must be an operator which supports this flag...
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:245
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:125
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition: Value.cpp:430
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree...
Definition: Dominators.h:140
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:598
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
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
apint_match m_APInt(const APInt *&Res)
Match a ConstantInt or splatted ConstantVector, binding the specified pointer to the contained APInt...
Definition: PatternMatch.h:260
The instances of the Type class are immutable: once they are created, they are never changed...
Definition: Type.h:46
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:371
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:382
BinaryOp_match< LHS, RHS, Instruction::Shl > m_Shl(const LHS &L, const RHS &R)
Definition: PatternMatch.h:592
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:853
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...
bool contains(const LoopT *L) const
Return true if the specified loop is contained within in this loop.
Definition: LoopInfo.h:110
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:418
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.
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:864
static Instruction * GetLoopInvariantInsertPosition(Loop *L, Instruction *Hint)
This class represents a range of values.
Definition: ConstantRange.h:47
signed less than
Definition: InstrTypes.h:882
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:385
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
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:932
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:401
This class uses information about analyze scalars to rewrite expressions in canonical form...
const DataLayout & getDataLayout() const
Return the DataLayout associated with the module this SCEV instance is operating on.
Virtual Register Rewriter
Definition: VirtRegMap.cpp:221
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:927
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:439
#define DEBUG_TYPE
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:220
#define I(x, y, z)
Definition: MD5.cpp:58
#define N
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 simplifyUsersOfIV(PHINode *CurrIV, ScalarEvolution *SE, DominatorTree *DT, LoopInfo *LI, SmallVectorImpl< WeakTrackingVH > &Dead, SCEVExpander &Rewriter, IVVisitor *V=nullptr)
simplifyUsersOfIV - Simplify instructions that use this induction variable by using ScalarEvolution t...
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...
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:967
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:328
const SCEV * getSignExtendExpr(const SCEV *Op, Type *Ty, unsigned Depth=0)
const BasicBlock * getParent() const
Definition: Instruction.h:66
static void pushIVUsers(Instruction *Def, Loop *L, SmallPtrSet< Instruction *, 16 > &Simplified, SmallVectorImpl< std::pair< Instruction *, Instruction *> > &SimpleIVUsers)
Add all uses of Def to the current IV&#39;s worklist.