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