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