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