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