LLVM  8.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"
30 
31 using namespace llvm;
32 
33 #define DEBUG_TYPE "indvars"
34 
35 STATISTIC(NumElimIdentity, "Number of IV identities eliminated");
36 STATISTIC(NumElimOperand, "Number of IV operands folded into a use");
37 STATISTIC(NumFoldedUser, "Number of IV users folded into a constant");
38 STATISTIC(NumElimRem , "Number of IV remainder operations eliminated");
39 STATISTIC(
40  NumSimplifiedSDiv,
41  "Number of IV signed division operations converted to unsigned division");
42 STATISTIC(
43  NumSimplifiedSRem,
44  "Number of IV signed remainder operations converted to unsigned remainder");
45 STATISTIC(NumElimCmp , "Number of IV comparisons eliminated");
46 
47 namespace {
48  /// This is a utility for simplifying induction variables
49  /// based on ScalarEvolution. It is the primary instrument of the
50  /// IndvarSimplify pass, but it may also be directly invoked to cleanup after
51  /// other loop passes that preserve SCEV.
52  class SimplifyIndvar {
53  Loop *L;
54  LoopInfo *LI;
55  ScalarEvolution *SE;
56  DominatorTree *DT;
59 
60  bool Changed;
61 
62  public:
63  SimplifyIndvar(Loop *Loop, ScalarEvolution *SE, DominatorTree *DT,
64  LoopInfo *LI, SCEVExpander &Rewriter,
66  : L(Loop), LI(LI), SE(SE), DT(DT), Rewriter(Rewriter), DeadInsts(Dead),
67  Changed(false) {
68  assert(LI && "IV simplification requires LoopInfo");
69  }
70 
71  bool hasChanged() const { return Changed; }
72 
73  /// Iteratively perform simplification on a worklist of users of the
74  /// specified induction variable. This is the top-level driver that applies
75  /// all simplifications to users of an IV.
76  void simplifyUsers(PHINode *CurrIV, IVVisitor *V = nullptr);
77 
78  Value *foldIVUser(Instruction *UseInst, Instruction *IVOperand);
79 
80  bool eliminateIdentitySCEV(Instruction *UseInst, Instruction *IVOperand);
81  bool replaceIVUserWithLoopInvariant(Instruction *UseInst);
82 
83  bool eliminateOverflowIntrinsic(CallInst *CI);
84  bool eliminateTrunc(TruncInst *TI);
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  LLVM_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  const int Idx = PN->getBasicBlockIndex(BB);
204  if (Idx >= 0) {
205  Value *Incoming = PN->getIncomingValue(Idx);
206  const SCEV *IncomingS = SE->getSCEV(Incoming);
207  CheapExpansions[IncomingS] = Incoming;
208  }
209  }
210  Value *NewLHS = CheapExpansions[InvariantLHS];
211  Value *NewRHS = CheapExpansions[InvariantRHS];
212 
213  if (!NewLHS)
214  if (auto *ConstLHS = dyn_cast<SCEVConstant>(InvariantLHS))
215  NewLHS = ConstLHS->getValue();
216  if (!NewRHS)
217  if (auto *ConstRHS = dyn_cast<SCEVConstant>(InvariantRHS))
218  NewRHS = ConstRHS->getValue();
219 
220  if (!NewLHS || !NewRHS)
221  // We could not find an existing value to replace either LHS or RHS.
222  // Generating new instructions has subtler tradeoffs, so avoid doing that
223  // for now.
224  return false;
225 
226  LLVM_DEBUG(dbgs() << "INDVARS: Simplified comparison: " << *ICmp << '\n');
227  ICmp->setPredicate(InvariantPredicate);
228  ICmp->setOperand(0, NewLHS);
229  ICmp->setOperand(1, NewRHS);
230  return true;
231 }
232 
233 /// SimplifyIVUsers helper for eliminating useless
234 /// comparisons against an induction variable.
235 void SimplifyIndvar::eliminateIVComparison(ICmpInst *ICmp, Value *IVOperand) {
236  unsigned IVOperIdx = 0;
237  ICmpInst::Predicate Pred = ICmp->getPredicate();
238  ICmpInst::Predicate OriginalPred = Pred;
239  if (IVOperand != ICmp->getOperand(0)) {
240  // Swapped
241  assert(IVOperand == ICmp->getOperand(1) && "Can't find IVOperand");
242  IVOperIdx = 1;
243  Pred = ICmpInst::getSwappedPredicate(Pred);
244  }
245 
246  // Get the SCEVs for the ICmp operands (in the specific context of the
247  // current loop)
248  const Loop *ICmpLoop = LI->getLoopFor(ICmp->getParent());
249  const SCEV *S = SE->getSCEVAtScope(ICmp->getOperand(IVOperIdx), ICmpLoop);
250  const SCEV *X = SE->getSCEVAtScope(ICmp->getOperand(1 - IVOperIdx), ICmpLoop);
251 
252  // If the condition is always true or always false, replace it with
253  // a constant value.
254  if (SE->isKnownPredicate(Pred, S, X)) {
256  DeadInsts.emplace_back(ICmp);
257  LLVM_DEBUG(dbgs() << "INDVARS: Eliminated comparison: " << *ICmp << '\n');
258  } else if (SE->isKnownPredicate(ICmpInst::getInversePredicate(Pred), S, X)) {
260  DeadInsts.emplace_back(ICmp);
261  LLVM_DEBUG(dbgs() << "INDVARS: Eliminated comparison: " << *ICmp << '\n');
262  } else if (makeIVComparisonInvariant(ICmp, IVOperand)) {
263  // fallthrough to end of function
264  } else if (ICmpInst::isSigned(OriginalPred) &&
265  SE->isKnownNonNegative(S) && SE->isKnownNonNegative(X)) {
266  // If we were unable to make anything above, all we can is to canonicalize
267  // the comparison hoping that it will open the doors for other
268  // optimizations. If we find out that we compare two non-negative values,
269  // we turn the instruction's predicate to its unsigned version. Note that
270  // we cannot rely on Pred here unless we check if we have swapped it.
271  assert(ICmp->getPredicate() == OriginalPred && "Predicate changed?");
272  LLVM_DEBUG(dbgs() << "INDVARS: Turn to unsigned comparison: " << *ICmp
273  << '\n');
274  ICmp->setPredicate(ICmpInst::getUnsignedPredicate(OriginalPred));
275  } else
276  return;
277 
278  ++NumElimCmp;
279  Changed = true;
280 }
281 
282 bool SimplifyIndvar::eliminateSDiv(BinaryOperator *SDiv) {
283  // Get the SCEVs for the ICmp operands.
284  auto *N = SE->getSCEV(SDiv->getOperand(0));
285  auto *D = SE->getSCEV(SDiv->getOperand(1));
286 
287  // Simplify unnecessary loops away.
288  const Loop *L = LI->getLoopFor(SDiv->getParent());
289  N = SE->getSCEVAtScope(N, L);
290  D = SE->getSCEVAtScope(D, L);
291 
292  // Replace sdiv by udiv if both of the operands are non-negative
293  if (SE->isKnownNonNegative(N) && SE->isKnownNonNegative(D)) {
294  auto *UDiv = BinaryOperator::Create(
295  BinaryOperator::UDiv, SDiv->getOperand(0), SDiv->getOperand(1),
296  SDiv->getName() + ".udiv", SDiv);
297  UDiv->setIsExact(SDiv->isExact());
298  SDiv->replaceAllUsesWith(UDiv);
299  LLVM_DEBUG(dbgs() << "INDVARS: Simplified sdiv: " << *SDiv << '\n');
300  ++NumSimplifiedSDiv;
301  Changed = true;
302  DeadInsts.push_back(SDiv);
303  return true;
304  }
305 
306  return false;
307 }
308 
309 // i %s n -> i %u n if i >= 0 and n >= 0
310 void SimplifyIndvar::replaceSRemWithURem(BinaryOperator *Rem) {
311  auto *N = Rem->getOperand(0), *D = Rem->getOperand(1);
312  auto *URem = BinaryOperator::Create(BinaryOperator::URem, N, D,
313  Rem->getName() + ".urem", Rem);
314  Rem->replaceAllUsesWith(URem);
315  LLVM_DEBUG(dbgs() << "INDVARS: Simplified srem: " << *Rem << '\n');
316  ++NumSimplifiedSRem;
317  Changed = true;
318  DeadInsts.emplace_back(Rem);
319 }
320 
321 // i % n --> i if i is in [0,n).
322 void SimplifyIndvar::replaceRemWithNumerator(BinaryOperator *Rem) {
323  Rem->replaceAllUsesWith(Rem->getOperand(0));
324  LLVM_DEBUG(dbgs() << "INDVARS: Simplified rem: " << *Rem << '\n');
325  ++NumElimRem;
326  Changed = true;
327  DeadInsts.emplace_back(Rem);
328 }
329 
330 // (i+1) % n --> (i+1)==n?0:(i+1) if i is in [0,n).
331 void SimplifyIndvar::replaceRemWithNumeratorOrZero(BinaryOperator *Rem) {
332  auto *T = Rem->getType();
333  auto *N = Rem->getOperand(0), *D = Rem->getOperand(1);
334  ICmpInst *ICmp = new ICmpInst(Rem, ICmpInst::ICMP_EQ, N, D);
335  SelectInst *Sel =
336  SelectInst::Create(ICmp, ConstantInt::get(T, 0), N, "iv.rem", Rem);
337  Rem->replaceAllUsesWith(Sel);
338  LLVM_DEBUG(dbgs() << "INDVARS: Simplified rem: " << *Rem << '\n');
339  ++NumElimRem;
340  Changed = true;
341  DeadInsts.emplace_back(Rem);
342 }
343 
344 /// SimplifyIVUsers helper for eliminating useless remainder operations
345 /// operating on an induction variable or replacing srem by urem.
346 void SimplifyIndvar::simplifyIVRemainder(BinaryOperator *Rem, Value *IVOperand,
347  bool IsSigned) {
348  auto *NValue = Rem->getOperand(0);
349  auto *DValue = Rem->getOperand(1);
350  // We're only interested in the case where we know something about
351  // the numerator, unless it is a srem, because we want to replace srem by urem
352  // in general.
353  bool UsedAsNumerator = IVOperand == NValue;
354  if (!UsedAsNumerator && !IsSigned)
355  return;
356 
357  const SCEV *N = SE->getSCEV(NValue);
358 
359  // Simplify unnecessary loops away.
360  const Loop *ICmpLoop = LI->getLoopFor(Rem->getParent());
361  N = SE->getSCEVAtScope(N, ICmpLoop);
362 
363  bool IsNumeratorNonNegative = !IsSigned || SE->isKnownNonNegative(N);
364 
365  // Do not proceed if the Numerator may be negative
366  if (!IsNumeratorNonNegative)
367  return;
368 
369  const SCEV *D = SE->getSCEV(DValue);
370  D = SE->getSCEVAtScope(D, ICmpLoop);
371 
372  if (UsedAsNumerator) {
373  auto LT = IsSigned ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT;
374  if (SE->isKnownPredicate(LT, N, D)) {
375  replaceRemWithNumerator(Rem);
376  return;
377  }
378 
379  auto *T = Rem->getType();
380  const auto *NLessOne = SE->getMinusSCEV(N, SE->getOne(T));
381  if (SE->isKnownPredicate(LT, NLessOne, D)) {
382  replaceRemWithNumeratorOrZero(Rem);
383  return;
384  }
385  }
386 
387  // Try to replace SRem with URem, if both N and D are known non-negative.
388  // Since we had already check N, we only need to check D now
389  if (!IsSigned || !SE->isKnownNonNegative(D))
390  return;
391 
392  replaceSRemWithURem(Rem);
393 }
394 
395 bool SimplifyIndvar::eliminateOverflowIntrinsic(CallInst *CI) {
396  auto *F = CI->getCalledFunction();
397  if (!F)
398  return false;
399 
400  typedef const SCEV *(ScalarEvolution::*OperationFunctionTy)(
401  const SCEV *, const SCEV *, SCEV::NoWrapFlags, unsigned);
402  typedef const SCEV *(ScalarEvolution::*ExtensionFunctionTy)(
403  const SCEV *, Type *, unsigned);
404 
405  OperationFunctionTy Operation;
406  ExtensionFunctionTy Extension;
407 
409 
410  // We always have exactly one of nsw or nuw. If NoSignedOverflow is false, we
411  // have nuw.
412  bool NoSignedOverflow;
413 
414  switch (F->getIntrinsicID()) {
415  default:
416  return false;
417 
418  case Intrinsic::sadd_with_overflow:
419  Operation = &ScalarEvolution::getAddExpr;
421  RawOp = Instruction::Add;
422  NoSignedOverflow = true;
423  break;
424 
425  case Intrinsic::uadd_with_overflow:
426  Operation = &ScalarEvolution::getAddExpr;
428  RawOp = Instruction::Add;
429  NoSignedOverflow = false;
430  break;
431 
432  case Intrinsic::ssub_with_overflow:
433  Operation = &ScalarEvolution::getMinusSCEV;
435  RawOp = Instruction::Sub;
436  NoSignedOverflow = true;
437  break;
438 
439  case Intrinsic::usub_with_overflow:
440  Operation = &ScalarEvolution::getMinusSCEV;
442  RawOp = Instruction::Sub;
443  NoSignedOverflow = false;
444  break;
445  }
446 
447  const SCEV *LHS = SE->getSCEV(CI->getArgOperand(0));
448  const SCEV *RHS = SE->getSCEV(CI->getArgOperand(1));
449 
450  auto *NarrowTy = cast<IntegerType>(LHS->getType());
451  auto *WideTy =
452  IntegerType::get(NarrowTy->getContext(), NarrowTy->getBitWidth() * 2);
453 
454  const SCEV *A =
455  (SE->*Extension)((SE->*Operation)(LHS, RHS, SCEV::FlagAnyWrap, 0),
456  WideTy, 0);
457  const SCEV *B =
458  (SE->*Operation)((SE->*Extension)(LHS, WideTy, 0),
459  (SE->*Extension)(RHS, WideTy, 0), SCEV::FlagAnyWrap, 0);
460 
461  if (A != B)
462  return false;
463 
464  // Proved no overflow, nuke the overflow check and, if possible, the overflow
465  // intrinsic as well.
466 
468  RawOp, CI->getArgOperand(0), CI->getArgOperand(1), "", CI);
469 
470  if (NoSignedOverflow)
471  NewResult->setHasNoSignedWrap(true);
472  else
473  NewResult->setHasNoUnsignedWrap(true);
474 
476 
477  for (auto *U : CI->users()) {
478  if (auto *EVI = dyn_cast<ExtractValueInst>(U)) {
479  if (EVI->getIndices()[0] == 1)
480  EVI->replaceAllUsesWith(ConstantInt::getFalse(CI->getContext()));
481  else {
482  assert(EVI->getIndices()[0] == 0 && "Only two possibilities!");
483  EVI->replaceAllUsesWith(NewResult);
484  }
485  ToDelete.push_back(EVI);
486  }
487  }
488 
489  for (auto *EVI : ToDelete)
490  EVI->eraseFromParent();
491 
492  if (CI->use_empty())
493  CI->eraseFromParent();
494 
495  return true;
496 }
497 
498 bool SimplifyIndvar::eliminateTrunc(TruncInst *TI) {
499  // It is always legal to replace
500  // icmp <pred> i32 trunc(iv), n
501  // with
502  // icmp <pred> i64 sext(trunc(iv)), sext(n), if pred is signed predicate.
503  // Or with
504  // icmp <pred> i64 zext(trunc(iv)), zext(n), if pred is unsigned predicate.
505  // Or with either of these if pred is an equality predicate.
506  //
507  // If we can prove that iv == sext(trunc(iv)) or iv == zext(trunc(iv)) for
508  // every comparison which uses trunc, it means that we can replace each of
509  // them with comparison of iv against sext/zext(n). We no longer need trunc
510  // after that.
511  //
512  // TODO: Should we do this if we can widen *some* comparisons, but not all
513  // of them? Sometimes it is enough to enable other optimizations, but the
514  // trunc instruction will stay in the loop.
515  Value *IV = TI->getOperand(0);
516  Type *IVTy = IV->getType();
517  const SCEV *IVSCEV = SE->getSCEV(IV);
518  const SCEV *TISCEV = SE->getSCEV(TI);
519 
520  // Check if iv == zext(trunc(iv)) and if iv == sext(trunc(iv)). If so, we can
521  // get rid of trunc
522  bool DoesSExtCollapse = false;
523  bool DoesZExtCollapse = false;
524  if (IVSCEV == SE->getSignExtendExpr(TISCEV, IVTy))
525  DoesSExtCollapse = true;
526  if (IVSCEV == SE->getZeroExtendExpr(TISCEV, IVTy))
527  DoesZExtCollapse = true;
528 
529  // If neither sext nor zext does collapse, it is not profitable to do any
530  // transform. Bail.
531  if (!DoesSExtCollapse && !DoesZExtCollapse)
532  return false;
533 
534  // Collect users of the trunc that look like comparisons against invariants.
535  // Bail if we find something different.
536  SmallVector<ICmpInst *, 4> ICmpUsers;
537  for (auto *U : TI->users()) {
538  // We don't care about users in unreachable blocks.
539  if (isa<Instruction>(U) &&
540  !DT->isReachableFromEntry(cast<Instruction>(U)->getParent()))
541  continue;
542  if (ICmpInst *ICI = dyn_cast<ICmpInst>(U)) {
543  if (ICI->getOperand(0) == TI && L->isLoopInvariant(ICI->getOperand(1))) {
544  assert(L->contains(ICI->getParent()) && "LCSSA form broken?");
545  // If we cannot get rid of trunc, bail.
546  if (ICI->isSigned() && !DoesSExtCollapse)
547  return false;
548  if (ICI->isUnsigned() && !DoesZExtCollapse)
549  return false;
550  // For equality, either signed or unsigned works.
551  ICmpUsers.push_back(ICI);
552  } else
553  return false;
554  } else
555  return false;
556  }
557 
558  auto CanUseZExt = [&](ICmpInst *ICI) {
559  // Unsigned comparison can be widened as unsigned.
560  if (ICI->isUnsigned())
561  return true;
562  // Is it profitable to do zext?
563  if (!DoesZExtCollapse)
564  return false;
565  // For equality, we can safely zext both parts.
566  if (ICI->isEquality())
567  return true;
568  // Otherwise we can only use zext when comparing two non-negative or two
569  // negative values. But in practice, we will never pass DoesZExtCollapse
570  // check for a negative value, because zext(trunc(x)) is non-negative. So
571  // it only make sense to check for non-negativity here.
572  const SCEV *SCEVOP1 = SE->getSCEV(ICI->getOperand(0));
573  const SCEV *SCEVOP2 = SE->getSCEV(ICI->getOperand(1));
574  return SE->isKnownNonNegative(SCEVOP1) && SE->isKnownNonNegative(SCEVOP2);
575  };
576  // Replace all comparisons against trunc with comparisons against IV.
577  for (auto *ICI : ICmpUsers) {
578  auto *Op1 = ICI->getOperand(1);
579  Instruction *Ext = nullptr;
580  // For signed/unsigned predicate, replace the old comparison with comparison
581  // of immediate IV against sext/zext of the invariant argument. If we can
582  // use either sext or zext (i.e. we are dealing with equality predicate),
583  // then prefer zext as a more canonical form.
584  // TODO: If we see a signed comparison which can be turned into unsigned,
585  // we can do it here for canonicalization purposes.
586  ICmpInst::Predicate Pred = ICI->getPredicate();
587  if (CanUseZExt(ICI)) {
588  assert(DoesZExtCollapse && "Unprofitable zext?");
589  Ext = new ZExtInst(Op1, IVTy, "zext", ICI);
590  Pred = ICmpInst::getUnsignedPredicate(Pred);
591  } else {
592  assert(DoesSExtCollapse && "Unprofitable sext?");
593  Ext = new SExtInst(Op1, IVTy, "sext", ICI);
594  assert(Pred == ICmpInst::getSignedPredicate(Pred) && "Must be signed!");
595  }
596  bool Changed;
597  L->makeLoopInvariant(Ext, Changed);
598  (void)Changed;
599  ICmpInst *NewICI = new ICmpInst(ICI, Pred, IV, Ext);
600  ICI->replaceAllUsesWith(NewICI);
601  DeadInsts.emplace_back(ICI);
602  }
603 
604  // Trunc no longer needed.
606  DeadInsts.emplace_back(TI);
607  return true;
608 }
609 
610 /// Eliminate an operation that consumes a simple IV and has no observable
611 /// side-effect given the range of IV values. IVOperand is guaranteed SCEVable,
612 /// but UseInst may not be.
613 bool SimplifyIndvar::eliminateIVUser(Instruction *UseInst,
614  Instruction *IVOperand) {
615  if (ICmpInst *ICmp = dyn_cast<ICmpInst>(UseInst)) {
616  eliminateIVComparison(ICmp, IVOperand);
617  return true;
618  }
619  if (BinaryOperator *Bin = dyn_cast<BinaryOperator>(UseInst)) {
620  bool IsSRem = Bin->getOpcode() == Instruction::SRem;
621  if (IsSRem || Bin->getOpcode() == Instruction::URem) {
622  simplifyIVRemainder(Bin, IVOperand, IsSRem);
623  return true;
624  }
625 
626  if (Bin->getOpcode() == Instruction::SDiv)
627  return eliminateSDiv(Bin);
628  }
629 
630  if (auto *CI = dyn_cast<CallInst>(UseInst))
631  if (eliminateOverflowIntrinsic(CI))
632  return true;
633 
634  if (auto *TI = dyn_cast<TruncInst>(UseInst))
635  if (eliminateTrunc(TI))
636  return true;
637 
638  if (eliminateIdentitySCEV(UseInst, IVOperand))
639  return true;
640 
641  return false;
642 }
643 
645  if (auto *BB = L->getLoopPreheader())
646  return BB->getTerminator();
647 
648  return Hint;
649 }
650 
651 /// Replace the UseInst with a constant if possible.
652 bool SimplifyIndvar::replaceIVUserWithLoopInvariant(Instruction *I) {
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  if (!SE->isLoopInvariant(S, L))
660  return false;
661 
662  // Do not generate something ridiculous even if S is loop invariant.
663  if (Rewriter.isHighCostExpansion(S, L, I))
664  return false;
665 
666  auto *IP = GetLoopInvariantInsertPosition(L, I);
667  auto *Invariant = Rewriter.expandCodeFor(S, I->getType(), IP);
668 
669  I->replaceAllUsesWith(Invariant);
670  LLVM_DEBUG(dbgs() << "INDVARS: Replace IV user: " << *I
671  << " with loop invariant: " << *S << '\n');
672  ++NumFoldedUser;
673  Changed = true;
674  DeadInsts.emplace_back(I);
675  return true;
676 }
677 
678 /// Eliminate any operation that SCEV can prove is an identity function.
679 bool SimplifyIndvar::eliminateIdentitySCEV(Instruction *UseInst,
680  Instruction *IVOperand) {
681  if (!SE->isSCEVable(UseInst->getType()) ||
682  (UseInst->getType() != IVOperand->getType()) ||
683  (SE->getSCEV(UseInst) != SE->getSCEV(IVOperand)))
684  return false;
685 
686  // getSCEV(X) == getSCEV(Y) does not guarantee that X and Y are related in the
687  // dominator tree, even if X is an operand to Y. For instance, in
688  //
689  // %iv = phi i32 {0,+,1}
690  // br %cond, label %left, label %merge
691  //
692  // left:
693  // %X = add i32 %iv, 0
694  // br label %merge
695  //
696  // merge:
697  // %M = phi (%X, %iv)
698  //
699  // getSCEV(%M) == getSCEV(%X) == {0,+,1}, but %X does not dominate %M, and
700  // %M.replaceAllUsesWith(%X) would be incorrect.
701 
702  if (isa<PHINode>(UseInst))
703  // If UseInst is not a PHI node then we know that IVOperand dominates
704  // UseInst directly from the legality of SSA.
705  if (!DT || !DT->dominates(IVOperand, UseInst))
706  return false;
707 
708  if (!LI->replacementPreservesLCSSAForm(UseInst, IVOperand))
709  return false;
710 
711  LLVM_DEBUG(dbgs() << "INDVARS: Eliminated identity: " << *UseInst << '\n');
712 
713  UseInst->replaceAllUsesWith(IVOperand);
714  ++NumElimIdentity;
715  Changed = true;
716  DeadInsts.emplace_back(UseInst);
717  return true;
718 }
719 
720 /// Annotate BO with nsw / nuw if it provably does not signed-overflow /
721 /// unsigned-overflow. Returns true if anything changed, false otherwise.
722 bool SimplifyIndvar::strengthenOverflowingOperation(BinaryOperator *BO,
723  Value *IVOperand) {
724 
725  // Fastpath: we don't have any work to do if `BO` is `nuw` and `nsw`.
726  if (BO->hasNoUnsignedWrap() && BO->hasNoSignedWrap())
727  return false;
728 
729  const SCEV *(ScalarEvolution::*GetExprForBO)(const SCEV *, const SCEV *,
730  SCEV::NoWrapFlags, unsigned);
731  switch (BO->getOpcode()) {
732  default:
733  return false;
734 
735  case Instruction::Add:
736  GetExprForBO = &ScalarEvolution::getAddExpr;
737  break;
738 
739  case Instruction::Sub:
740  GetExprForBO = &ScalarEvolution::getMinusSCEV;
741  break;
742 
743  case Instruction::Mul:
744  GetExprForBO = &ScalarEvolution::getMulExpr;
745  break;
746  }
747 
748  unsigned BitWidth = cast<IntegerType>(BO->getType())->getBitWidth();
749  Type *WideTy = IntegerType::get(BO->getContext(), BitWidth * 2);
750  const SCEV *LHS = SE->getSCEV(BO->getOperand(0));
751  const SCEV *RHS = SE->getSCEV(BO->getOperand(1));
752 
753  bool Changed = false;
754 
755  if (!BO->hasNoUnsignedWrap()) {
756  const SCEV *ExtendAfterOp = SE->getZeroExtendExpr(SE->getSCEV(BO), WideTy);
757  const SCEV *OpAfterExtend = (SE->*GetExprForBO)(
758  SE->getZeroExtendExpr(LHS, WideTy), SE->getZeroExtendExpr(RHS, WideTy),
759  SCEV::FlagAnyWrap, 0u);
760  if (ExtendAfterOp == OpAfterExtend) {
761  BO->setHasNoUnsignedWrap();
762  SE->forgetValue(BO);
763  Changed = true;
764  }
765  }
766 
767  if (!BO->hasNoSignedWrap()) {
768  const SCEV *ExtendAfterOp = SE->getSignExtendExpr(SE->getSCEV(BO), WideTy);
769  const SCEV *OpAfterExtend = (SE->*GetExprForBO)(
770  SE->getSignExtendExpr(LHS, WideTy), SE->getSignExtendExpr(RHS, WideTy),
771  SCEV::FlagAnyWrap, 0u);
772  if (ExtendAfterOp == OpAfterExtend) {
773  BO->setHasNoSignedWrap();
774  SE->forgetValue(BO);
775  Changed = true;
776  }
777  }
778 
779  return Changed;
780 }
781 
782 /// Annotate the Shr in (X << IVOperand) >> C as exact using the
783 /// information from the IV's range. Returns true if anything changed, false
784 /// otherwise.
785 bool SimplifyIndvar::strengthenRightShift(BinaryOperator *BO,
786  Value *IVOperand) {
787  using namespace llvm::PatternMatch;
788 
789  if (BO->getOpcode() == Instruction::Shl) {
790  bool Changed = false;
791  ConstantRange IVRange = SE->getUnsignedRange(SE->getSCEV(IVOperand));
792  for (auto *U : BO->users()) {
793  const APInt *C;
794  if (match(U,
795  m_AShr(m_Shl(m_Value(), m_Specific(IVOperand)), m_APInt(C))) ||
796  match(U,
797  m_LShr(m_Shl(m_Value(), m_Specific(IVOperand)), m_APInt(C)))) {
798  BinaryOperator *Shr = cast<BinaryOperator>(U);
799  if (!Shr->isExact() && IVRange.getUnsignedMin().uge(*C)) {
800  Shr->setIsExact(true);
801  Changed = true;
802  }
803  }
804  }
805  return Changed;
806  }
807 
808  return false;
809 }
810 
811 /// Add all uses of Def to the current IV's worklist.
812 static void pushIVUsers(
813  Instruction *Def, Loop *L,
815  SmallVectorImpl< std::pair<Instruction*,Instruction*> > &SimpleIVUsers) {
816 
817  for (User *U : Def->users()) {
818  Instruction *UI = cast<Instruction>(U);
819 
820  // Avoid infinite or exponential worklist processing.
821  // Also ensure unique worklist users.
822  // If Def is a LoopPhi, it may not be in the Simplified set, so check for
823  // self edges first.
824  if (UI == Def)
825  continue;
826 
827  // Only change the current Loop, do not change the other parts (e.g. other
828  // Loops).
829  if (!L->contains(UI))
830  continue;
831 
832  // Do not push the same instruction more than once.
833  if (!Simplified.insert(UI).second)
834  continue;
835 
836  SimpleIVUsers.push_back(std::make_pair(UI, Def));
837  }
838 }
839 
840 /// Return true if this instruction generates a simple SCEV
841 /// expression in terms of that IV.
842 ///
843 /// This is similar to IVUsers' isInteresting() but processes each instruction
844 /// non-recursively when the operand is already known to be a simpleIVUser.
845 ///
846 static bool isSimpleIVUser(Instruction *I, const Loop *L, ScalarEvolution *SE) {
847  if (!SE->isSCEVable(I->getType()))
848  return false;
849 
850  // Get the symbolic expression for this instruction.
851  const SCEV *S = SE->getSCEV(I);
852 
853  // Only consider affine recurrences.
854  const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(S);
855  if (AR && AR->getLoop() == L)
856  return true;
857 
858  return false;
859 }
860 
861 /// Iteratively perform simplification on a worklist of users
862 /// of the specified induction variable. Each successive simplification may push
863 /// more users which may themselves be candidates for simplification.
864 ///
865 /// This algorithm does not require IVUsers analysis. Instead, it simplifies
866 /// instructions in-place during analysis. Rather than rewriting induction
867 /// variables bottom-up from their users, it transforms a chain of IVUsers
868 /// top-down, updating the IR only when it encounters a clear optimization
869 /// opportunity.
870 ///
871 /// Once DisableIVRewrite is default, LSR will be the only client of IVUsers.
872 ///
873 void SimplifyIndvar::simplifyUsers(PHINode *CurrIV, IVVisitor *V) {
874  if (!SE->isSCEVable(CurrIV->getType()))
875  return;
876 
877  // Instructions processed by SimplifyIndvar for CurrIV.
879 
880  // Use-def pairs if IV users waiting to be processed for CurrIV.
882 
883  // Push users of the current LoopPhi. In rare cases, pushIVUsers may be
884  // called multiple times for the same LoopPhi. This is the proper thing to
885  // do for loop header phis that use each other.
886  pushIVUsers(CurrIV, L, Simplified, SimpleIVUsers);
887 
888  while (!SimpleIVUsers.empty()) {
889  std::pair<Instruction*, Instruction*> UseOper =
890  SimpleIVUsers.pop_back_val();
891  Instruction *UseInst = UseOper.first;
892 
893  // If a user of the IndVar is trivially dead, we prefer just to mark it dead
894  // rather than try to do some complex analysis or transformation (such as
895  // widening) basing on it.
896  // TODO: Propagate TLI and pass it here to handle more cases.
897  if (isInstructionTriviallyDead(UseInst, /* TLI */ nullptr)) {
898  DeadInsts.emplace_back(UseInst);
899  continue;
900  }
901 
902  // Bypass back edges to avoid extra work.
903  if (UseInst == CurrIV) continue;
904 
905  // Try to replace UseInst with a loop invariant before any other
906  // simplifications.
907  if (replaceIVUserWithLoopInvariant(UseInst))
908  continue;
909 
910  Instruction *IVOperand = UseOper.second;
911  for (unsigned N = 0; IVOperand; ++N) {
912  assert(N <= Simplified.size() && "runaway iteration");
913 
914  Value *NewOper = foldIVUser(UseInst, IVOperand);
915  if (!NewOper)
916  break; // done folding
917  IVOperand = dyn_cast<Instruction>(NewOper);
918  }
919  if (!IVOperand)
920  continue;
921 
922  if (eliminateIVUser(UseInst, IVOperand)) {
923  pushIVUsers(IVOperand, L, Simplified, SimpleIVUsers);
924  continue;
925  }
926 
927  if (BinaryOperator *BO = dyn_cast<BinaryOperator>(UseInst)) {
928  if ((isa<OverflowingBinaryOperator>(BO) &&
929  strengthenOverflowingOperation(BO, IVOperand)) ||
930  (isa<ShlOperator>(BO) && strengthenRightShift(BO, IVOperand))) {
931  // re-queue uses of the now modified binary operator and fall
932  // through to the checks that remain.
933  pushIVUsers(IVOperand, L, Simplified, SimpleIVUsers);
934  }
935  }
936 
937  CastInst *Cast = dyn_cast<CastInst>(UseInst);
938  if (V && Cast) {
939  V->visitCast(Cast);
940  continue;
941  }
942  if (isSimpleIVUser(UseInst, L, SE)) {
943  pushIVUsers(UseInst, L, Simplified, SimpleIVUsers);
944  }
945  }
946 }
947 
948 namespace llvm {
949 
951 
952 /// Simplify instructions that use this induction variable
953 /// by using ScalarEvolution to analyze the IV's recurrence.
957  SimplifyIndvar SIV(LI->getLoopFor(CurrIV->getParent()), SE, DT, LI, Rewriter,
958  Dead);
959  SIV.simplifyUsers(CurrIV, V);
960  return SIV.hasChanged();
961 }
962 
963 /// Simplify users of induction variables within this
964 /// loop. This does not actually change or add IVs.
967  SCEVExpander Rewriter(*SE, SE->getDataLayout(), "indvars");
968 #ifndef NDEBUG
969  Rewriter.setDebugType(DEBUG_TYPE);
970 #endif
971  bool Changed = false;
972  for (BasicBlock::iterator I = L->getHeader()->begin(); isa<PHINode>(I); ++I) {
973  Changed |= simplifyUsersOfIV(cast<PHINode>(I), SE, DT, LI, Dead, Rewriter);
974  }
975  return Changed;
976 }
977 
978 } // 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:68
static ConstantInt * getFalse(LLVMContext &Context)
Definition: Constants.cpp:584
Function * getCalledFunction() const
Return the function called, or null if this is an indirect function invocation.
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:355
This class represents zero extension of integer types.
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:174
unsigned less than
Definition: InstrTypes.h:710
BinaryOp_match< LHS, RHS, Instruction::AShr > m_AShr(const LHS &L, const RHS &R)
Definition: PatternMatch.h:748
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:714
bool makeLoopInvariant(Value *V, bool &Changed, Instruction *InsertPt=nullptr) const
If the given value is an instruction inside of the loop and it can be hoisted, do so to make it trivi...
Definition: LoopInfo.cpp:67
STATISTIC(NumFunctions, "Total number of functions")
F(f)
This class represents a sign extension of integer types.
bool hasNoSignedWrap() const
Determine whether the no signed wrap flag is set.
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:264
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
Definition: InstrTypes.h:854
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:783
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
Definition: LoopInfo.h:684
This is the base class for all instructions that perform data casts.
Definition: InstrTypes.h:392
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:145
APInt getUnsignedMin() const
Return the smallest unsigned value contained in the ConstantRange.
This class represents a truncation of integer types.
Value * getOperand(unsigned i) const
Definition: User.h:170
BinaryOp_match< LHS, RHS, Instruction::LShr > m_LShr(const LHS &L, const RHS &R)
Definition: PatternMatch.h:742
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:177
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:588
specificval_ty m_Specific(const Value *V)
Match if we have a specific specified value.
Definition: PatternMatch.h:499
BinaryOp_match< LHS, RHS, Instruction::Shl > m_Shl(const LHS &L, const RHS &R)
Definition: PatternMatch.h:736
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:685
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.
static UndefValue * get(Type *T)
Static factory methods - Return an &#39;undef&#39; object of the specified type.
Definition: Constants.cpp:1392
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.
bool isLoopInvariant(const Value *V) const
Return true if the specified value is loop invariant.
Definition: LoopInfo.cpp:57
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:847
static Instruction * GetLoopInvariantInsertPosition(Loop *L, Instruction *Hint)
This class represents a range of values.
Definition: ConstantRange.h:47
signed less than
Definition: InstrTypes.h:714
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:381
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:621
Predicate getSignedPredicate() const
For example, EQ->EQ, SLE->SLE, UGT->SGT, etc.
bool uge(const APInt &RHS) const
Unsigned greater or equal comparison.
Definition: APInt.h:1287
static ConstantInt * getTrue(LLVMContext &Context)
Definition: Constants.cpp:577
void setPredicate(Predicate P)
Set the predicate for this instruction to the specified value.
Definition: InstrTypes.h:764
void setOperand(unsigned i, Value *Val)
Definition: User.h:175
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:133
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:70
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:400
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:222
Predicate getPredicate() const
Return the predicate for this instruction.
Definition: InstrTypes.h:759
This class represents an analyzed expression in the program.
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:56
virtual void visitCast(CastInst *Cast)=0
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:459
#define DEBUG_TYPE
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 nuw flag on this instruction, which must be an operator which supports this flag...
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
Value * getArgOperand(unsigned i) const
getArgOperand/setArgOperand - Return/set the i-th call argument.
bool isInstructionTriviallyDead(Instruction *I, const TargetLibraryInfo *TLI=nullptr)
Return true if the result produced by the instruction is not used, and the instruction has no side ef...
Definition: Local.cpp:348
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.
static const Function * getParent(const Value *V)
Predicate getSwappedPredicate() const
For example, EQ->EQ, SLE->SGE, ULT->UGT, OEQ->OEQ, ULE->UGE, OLT->OGT, etc.
Definition: InstrTypes.h:799
#define LLVM_DEBUG(X)
Definition: Debug.h:123
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:323
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.