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