LLVM  14.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,
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 /// Find a point in code which dominates all given instructions. We can safely
103 /// assume that, whatever fact we can prove at the found point, this fact is
104 /// also true for each of the given instructions.
106  DominatorTree &DT) {
107  Instruction *CommonDom = nullptr;
108  for (auto *Insn : Instructions)
109  if (!CommonDom || DT.dominates(Insn, CommonDom))
110  CommonDom = Insn;
111  else if (!DT.dominates(CommonDom, Insn))
112  // If there is no dominance relation, use common dominator.
113  CommonDom =
114  DT.findNearestCommonDominator(CommonDom->getParent(),
115  Insn->getParent())->getTerminator();
116  assert(CommonDom && "Common dominator not found?");
117  return CommonDom;
118 }
119 
120 /// Fold an IV operand into its use. This removes increments of an
121 /// aligned IV when used by a instruction that ignores the low bits.
122 ///
123 /// IVOperand is guaranteed SCEVable, but UseInst may not be.
124 ///
125 /// Return the operand of IVOperand for this induction variable if IVOperand can
126 /// be folded (in case more folding opportunities have been exposed).
127 /// Otherwise return null.
128 Value *SimplifyIndvar::foldIVUser(Instruction *UseInst, Instruction *IVOperand) {
129  Value *IVSrc = nullptr;
130  const unsigned OperIdx = 0;
131  const SCEV *FoldedExpr = nullptr;
132  bool MustDropExactFlag = false;
133  switch (UseInst->getOpcode()) {
134  default:
135  return nullptr;
136  case Instruction::UDiv:
137  case Instruction::LShr:
138  // We're only interested in the case where we know something about
139  // the numerator and have a constant denominator.
140  if (IVOperand != UseInst->getOperand(OperIdx) ||
141  !isa<ConstantInt>(UseInst->getOperand(1)))
142  return nullptr;
143 
144  // Attempt to fold a binary operator with constant operand.
145  // e.g. ((I + 1) >> 2) => I >> 2
146  if (!isa<BinaryOperator>(IVOperand)
147  || !isa<ConstantInt>(IVOperand->getOperand(1)))
148  return nullptr;
149 
150  IVSrc = IVOperand->getOperand(0);
151  // IVSrc must be the (SCEVable) IV, since the other operand is const.
152  assert(SE->isSCEVable(IVSrc->getType()) && "Expect SCEVable IV operand");
153 
154  ConstantInt *D = cast<ConstantInt>(UseInst->getOperand(1));
155  if (UseInst->getOpcode() == Instruction::LShr) {
156  // Get a constant for the divisor. See createSCEV.
157  uint32_t BitWidth = cast<IntegerType>(UseInst->getType())->getBitWidth();
158  if (D->getValue().uge(BitWidth))
159  return nullptr;
160 
161  D = ConstantInt::get(UseInst->getContext(),
162  APInt::getOneBitSet(BitWidth, D->getZExtValue()));
163  }
164  FoldedExpr = SE->getUDivExpr(SE->getSCEV(IVSrc), SE->getSCEV(D));
165  // We might have 'exact' flag set at this point which will no longer be
166  // correct after we make the replacement.
167  if (UseInst->isExact() &&
168  SE->getSCEV(IVSrc) != SE->getMulExpr(FoldedExpr, SE->getSCEV(D)))
169  MustDropExactFlag = true;
170  }
171  // We have something that might fold it's operand. Compare SCEVs.
172  if (!SE->isSCEVable(UseInst->getType()))
173  return nullptr;
174 
175  // Bypass the operand if SCEV can prove it has no effect.
176  if (SE->getSCEV(UseInst) != FoldedExpr)
177  return nullptr;
178 
179  LLVM_DEBUG(dbgs() << "INDVARS: Eliminated IV operand: " << *IVOperand
180  << " -> " << *UseInst << '\n');
181 
182  UseInst->setOperand(OperIdx, IVSrc);
183  assert(SE->getSCEV(UseInst) == FoldedExpr && "bad SCEV with folded oper");
184 
185  if (MustDropExactFlag)
186  UseInst->dropPoisonGeneratingFlags();
187 
188  ++NumElimOperand;
189  Changed = true;
190  if (IVOperand->use_empty())
191  DeadInsts.emplace_back(IVOperand);
192  return IVSrc;
193 }
194 
195 bool SimplifyIndvar::makeIVComparisonInvariant(ICmpInst *ICmp,
196  Value *IVOperand) {
197  unsigned IVOperIdx = 0;
198  ICmpInst::Predicate Pred = ICmp->getPredicate();
199  if (IVOperand != ICmp->getOperand(0)) {
200  // Swapped
201  assert(IVOperand == ICmp->getOperand(1) && "Can't find IVOperand");
202  IVOperIdx = 1;
203  Pred = ICmpInst::getSwappedPredicate(Pred);
204  }
205 
206  // Get the SCEVs for the ICmp operands (in the specific context of the
207  // current loop)
208  const Loop *ICmpLoop = LI->getLoopFor(ICmp->getParent());
209  const SCEV *S = SE->getSCEVAtScope(ICmp->getOperand(IVOperIdx), ICmpLoop);
210  const SCEV *X = SE->getSCEVAtScope(ICmp->getOperand(1 - IVOperIdx), ICmpLoop);
211 
212  auto *PN = dyn_cast<PHINode>(IVOperand);
213  if (!PN)
214  return false;
215  auto LIP = SE->getLoopInvariantPredicate(Pred, S, X, L);
216  if (!LIP)
217  return false;
218  ICmpInst::Predicate InvariantPredicate = LIP->Pred;
219  const SCEV *InvariantLHS = LIP->LHS;
220  const SCEV *InvariantRHS = LIP->RHS;
221 
222  // Rewrite the comparison to a loop invariant comparison if it can be done
223  // cheaply, where cheaply means "we don't need to emit any new
224  // instructions".
225 
226  SmallDenseMap<const SCEV*, Value*> CheapExpansions;
227  CheapExpansions[S] = ICmp->getOperand(IVOperIdx);
228  CheapExpansions[X] = ICmp->getOperand(1 - IVOperIdx);
229 
230  // TODO: Support multiple entry loops? (We currently bail out of these in
231  // the IndVarSimplify pass)
232  if (auto *BB = L->getLoopPredecessor()) {
233  const int Idx = PN->getBasicBlockIndex(BB);
234  if (Idx >= 0) {
235  Value *Incoming = PN->getIncomingValue(Idx);
236  const SCEV *IncomingS = SE->getSCEV(Incoming);
237  CheapExpansions[IncomingS] = Incoming;
238  }
239  }
240  Value *NewLHS = CheapExpansions[InvariantLHS];
241  Value *NewRHS = CheapExpansions[InvariantRHS];
242 
243  if (!NewLHS)
244  if (auto *ConstLHS = dyn_cast<SCEVConstant>(InvariantLHS))
245  NewLHS = ConstLHS->getValue();
246  if (!NewRHS)
247  if (auto *ConstRHS = dyn_cast<SCEVConstant>(InvariantRHS))
248  NewRHS = ConstRHS->getValue();
249 
250  if (!NewLHS || !NewRHS)
251  // We could not find an existing value to replace either LHS or RHS.
252  // Generating new instructions has subtler tradeoffs, so avoid doing that
253  // for now.
254  return false;
255 
256  LLVM_DEBUG(dbgs() << "INDVARS: Simplified comparison: " << *ICmp << '\n');
257  ICmp->setPredicate(InvariantPredicate);
258  ICmp->setOperand(0, NewLHS);
259  ICmp->setOperand(1, NewRHS);
260  return true;
261 }
262 
263 /// SimplifyIVUsers helper for eliminating useless
264 /// comparisons against an induction variable.
265 void SimplifyIndvar::eliminateIVComparison(ICmpInst *ICmp, Value *IVOperand) {
266  unsigned IVOperIdx = 0;
267  ICmpInst::Predicate Pred = ICmp->getPredicate();
268  ICmpInst::Predicate OriginalPred = Pred;
269  if (IVOperand != ICmp->getOperand(0)) {
270  // Swapped
271  assert(IVOperand == ICmp->getOperand(1) && "Can't find IVOperand");
272  IVOperIdx = 1;
273  Pred = ICmpInst::getSwappedPredicate(Pred);
274  }
275 
276  // Get the SCEVs for the ICmp operands (in the specific context of the
277  // current loop)
278  const Loop *ICmpLoop = LI->getLoopFor(ICmp->getParent());
279  const SCEV *S = SE->getSCEVAtScope(ICmp->getOperand(IVOperIdx), ICmpLoop);
280  const SCEV *X = SE->getSCEVAtScope(ICmp->getOperand(1 - IVOperIdx), ICmpLoop);
281 
282  // If the condition is always true or always false in the given context,
283  // replace it with a constant value.
285  for (auto *U : ICmp->users())
286  Users.push_back(cast<Instruction>(U));
287  const Instruction *CtxI = findCommonDominator(Users, *DT);
288  if (auto Ev = SE->evaluatePredicateAt(Pred, S, X, CtxI)) {
290  DeadInsts.emplace_back(ICmp);
291  LLVM_DEBUG(dbgs() << "INDVARS: Eliminated comparison: " << *ICmp << '\n');
292  } else if (makeIVComparisonInvariant(ICmp, IVOperand)) {
293  // fallthrough to end of function
294  } else if (ICmpInst::isSigned(OriginalPred) &&
295  SE->isKnownNonNegative(S) && SE->isKnownNonNegative(X)) {
296  // If we were unable to make anything above, all we can is to canonicalize
297  // the comparison hoping that it will open the doors for other
298  // optimizations. If we find out that we compare two non-negative values,
299  // we turn the instruction's predicate to its unsigned version. Note that
300  // we cannot rely on Pred here unless we check if we have swapped it.
301  assert(ICmp->getPredicate() == OriginalPred && "Predicate changed?");
302  LLVM_DEBUG(dbgs() << "INDVARS: Turn to unsigned comparison: " << *ICmp
303  << '\n');
304  ICmp->setPredicate(ICmpInst::getUnsignedPredicate(OriginalPred));
305  } else
306  return;
307 
308  ++NumElimCmp;
309  Changed = true;
310 }
311 
312 bool SimplifyIndvar::eliminateSDiv(BinaryOperator *SDiv) {
313  // Get the SCEVs for the ICmp operands.
314  auto *N = SE->getSCEV(SDiv->getOperand(0));
315  auto *D = SE->getSCEV(SDiv->getOperand(1));
316 
317  // Simplify unnecessary loops away.
318  const Loop *L = LI->getLoopFor(SDiv->getParent());
319  N = SE->getSCEVAtScope(N, L);
320  D = SE->getSCEVAtScope(D, L);
321 
322  // Replace sdiv by udiv if both of the operands are non-negative
323  if (SE->isKnownNonNegative(N) && SE->isKnownNonNegative(D)) {
324  auto *UDiv = BinaryOperator::Create(
325  BinaryOperator::UDiv, SDiv->getOperand(0), SDiv->getOperand(1),
326  SDiv->getName() + ".udiv", SDiv);
327  UDiv->setIsExact(SDiv->isExact());
328  SDiv->replaceAllUsesWith(UDiv);
329  LLVM_DEBUG(dbgs() << "INDVARS: Simplified sdiv: " << *SDiv << '\n');
330  ++NumSimplifiedSDiv;
331  Changed = true;
332  DeadInsts.push_back(SDiv);
333  return true;
334  }
335 
336  return false;
337 }
338 
339 // i %s n -> i %u n if i >= 0 and n >= 0
340 void SimplifyIndvar::replaceSRemWithURem(BinaryOperator *Rem) {
341  auto *N = Rem->getOperand(0), *D = Rem->getOperand(1);
342  auto *URem = BinaryOperator::Create(BinaryOperator::URem, N, D,
343  Rem->getName() + ".urem", Rem);
344  Rem->replaceAllUsesWith(URem);
345  LLVM_DEBUG(dbgs() << "INDVARS: Simplified srem: " << *Rem << '\n');
346  ++NumSimplifiedSRem;
347  Changed = true;
348  DeadInsts.emplace_back(Rem);
349 }
350 
351 // i % n --> i if i is in [0,n).
352 void SimplifyIndvar::replaceRemWithNumerator(BinaryOperator *Rem) {
353  Rem->replaceAllUsesWith(Rem->getOperand(0));
354  LLVM_DEBUG(dbgs() << "INDVARS: Simplified rem: " << *Rem << '\n');
355  ++NumElimRem;
356  Changed = true;
357  DeadInsts.emplace_back(Rem);
358 }
359 
360 // (i+1) % n --> (i+1)==n?0:(i+1) if i is in [0,n).
361 void SimplifyIndvar::replaceRemWithNumeratorOrZero(BinaryOperator *Rem) {
362  auto *T = Rem->getType();
363  auto *N = Rem->getOperand(0), *D = Rem->getOperand(1);
364  ICmpInst *ICmp = new ICmpInst(Rem, ICmpInst::ICMP_EQ, N, D);
365  SelectInst *Sel =
366  SelectInst::Create(ICmp, ConstantInt::get(T, 0), N, "iv.rem", Rem);
367  Rem->replaceAllUsesWith(Sel);
368  LLVM_DEBUG(dbgs() << "INDVARS: Simplified rem: " << *Rem << '\n');
369  ++NumElimRem;
370  Changed = true;
371  DeadInsts.emplace_back(Rem);
372 }
373 
374 /// SimplifyIVUsers helper for eliminating useless remainder operations
375 /// operating on an induction variable or replacing srem by urem.
376 void SimplifyIndvar::simplifyIVRemainder(BinaryOperator *Rem, Value *IVOperand,
377  bool IsSigned) {
378  auto *NValue = Rem->getOperand(0);
379  auto *DValue = Rem->getOperand(1);
380  // We're only interested in the case where we know something about
381  // the numerator, unless it is a srem, because we want to replace srem by urem
382  // in general.
383  bool UsedAsNumerator = IVOperand == NValue;
384  if (!UsedAsNumerator && !IsSigned)
385  return;
386 
387  const SCEV *N = SE->getSCEV(NValue);
388 
389  // Simplify unnecessary loops away.
390  const Loop *ICmpLoop = LI->getLoopFor(Rem->getParent());
391  N = SE->getSCEVAtScope(N, ICmpLoop);
392 
393  bool IsNumeratorNonNegative = !IsSigned || SE->isKnownNonNegative(N);
394 
395  // Do not proceed if the Numerator may be negative
396  if (!IsNumeratorNonNegative)
397  return;
398 
399  const SCEV *D = SE->getSCEV(DValue);
400  D = SE->getSCEVAtScope(D, ICmpLoop);
401 
402  if (UsedAsNumerator) {
403  auto LT = IsSigned ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT;
404  if (SE->isKnownPredicate(LT, N, D)) {
405  replaceRemWithNumerator(Rem);
406  return;
407  }
408 
409  auto *T = Rem->getType();
410  const auto *NLessOne = SE->getMinusSCEV(N, SE->getOne(T));
411  if (SE->isKnownPredicate(LT, NLessOne, D)) {
412  replaceRemWithNumeratorOrZero(Rem);
413  return;
414  }
415  }
416 
417  // Try to replace SRem with URem, if both N and D are known non-negative.
418  // Since we had already check N, we only need to check D now
419  if (!IsSigned || !SE->isKnownNonNegative(D))
420  return;
421 
422  replaceSRemWithURem(Rem);
423 }
424 
425 bool SimplifyIndvar::eliminateOverflowIntrinsic(WithOverflowInst *WO) {
426  const SCEV *LHS = SE->getSCEV(WO->getLHS());
427  const SCEV *RHS = SE->getSCEV(WO->getRHS());
428  if (!SE->willNotOverflow(WO->getBinaryOp(), WO->isSigned(), LHS, RHS))
429  return false;
430 
431  // Proved no overflow, nuke the overflow check and, if possible, the overflow
432  // intrinsic as well.
433 
435  WO->getBinaryOp(), WO->getLHS(), WO->getRHS(), "", WO);
436 
437  if (WO->isSigned())
438  NewResult->setHasNoSignedWrap(true);
439  else
440  NewResult->setHasNoUnsignedWrap(true);
441 
443 
444  for (auto *U : WO->users()) {
445  if (auto *EVI = dyn_cast<ExtractValueInst>(U)) {
446  if (EVI->getIndices()[0] == 1)
447  EVI->replaceAllUsesWith(ConstantInt::getFalse(WO->getContext()));
448  else {
449  assert(EVI->getIndices()[0] == 0 && "Only two possibilities!");
450  EVI->replaceAllUsesWith(NewResult);
451  }
452  ToDelete.push_back(EVI);
453  }
454  }
455 
456  for (auto *EVI : ToDelete)
457  EVI->eraseFromParent();
458 
459  if (WO->use_empty())
460  WO->eraseFromParent();
461 
462  Changed = true;
463  return true;
464 }
465 
466 bool SimplifyIndvar::eliminateSaturatingIntrinsic(SaturatingInst *SI) {
467  const SCEV *LHS = SE->getSCEV(SI->getLHS());
468  const SCEV *RHS = SE->getSCEV(SI->getRHS());
469  if (!SE->willNotOverflow(SI->getBinaryOp(), SI->isSigned(), LHS, RHS))
470  return false;
471 
473  SI->getBinaryOp(), SI->getLHS(), SI->getRHS(), SI->getName(), SI);
474  if (SI->isSigned())
475  BO->setHasNoSignedWrap();
476  else
477  BO->setHasNoUnsignedWrap();
478 
479  SI->replaceAllUsesWith(BO);
480  DeadInsts.emplace_back(SI);
481  Changed = true;
482  return true;
483 }
484 
485 bool SimplifyIndvar::eliminateTrunc(TruncInst *TI) {
486  // It is always legal to replace
487  // icmp <pred> i32 trunc(iv), n
488  // with
489  // icmp <pred> i64 sext(trunc(iv)), sext(n), if pred is signed predicate.
490  // Or with
491  // icmp <pred> i64 zext(trunc(iv)), zext(n), if pred is unsigned predicate.
492  // Or with either of these if pred is an equality predicate.
493  //
494  // If we can prove that iv == sext(trunc(iv)) or iv == zext(trunc(iv)) for
495  // every comparison which uses trunc, it means that we can replace each of
496  // them with comparison of iv against sext/zext(n). We no longer need trunc
497  // after that.
498  //
499  // TODO: Should we do this if we can widen *some* comparisons, but not all
500  // of them? Sometimes it is enough to enable other optimizations, but the
501  // trunc instruction will stay in the loop.
502  Value *IV = TI->getOperand(0);
503  Type *IVTy = IV->getType();
504  const SCEV *IVSCEV = SE->getSCEV(IV);
505  const SCEV *TISCEV = SE->getSCEV(TI);
506 
507  // Check if iv == zext(trunc(iv)) and if iv == sext(trunc(iv)). If so, we can
508  // get rid of trunc
509  bool DoesSExtCollapse = false;
510  bool DoesZExtCollapse = false;
511  if (IVSCEV == SE->getSignExtendExpr(TISCEV, IVTy))
512  DoesSExtCollapse = true;
513  if (IVSCEV == SE->getZeroExtendExpr(TISCEV, IVTy))
514  DoesZExtCollapse = true;
515 
516  // If neither sext nor zext does collapse, it is not profitable to do any
517  // transform. Bail.
518  if (!DoesSExtCollapse && !DoesZExtCollapse)
519  return false;
520 
521  // Collect users of the trunc that look like comparisons against invariants.
522  // Bail if we find something different.
523  SmallVector<ICmpInst *, 4> ICmpUsers;
524  for (auto *U : TI->users()) {
525  // We don't care about users in unreachable blocks.
526  if (isa<Instruction>(U) &&
527  !DT->isReachableFromEntry(cast<Instruction>(U)->getParent()))
528  continue;
529  ICmpInst *ICI = dyn_cast<ICmpInst>(U);
530  if (!ICI) return false;
531  assert(L->contains(ICI->getParent()) && "LCSSA form broken?");
532  if (!(ICI->getOperand(0) == TI && L->isLoopInvariant(ICI->getOperand(1))) &&
533  !(ICI->getOperand(1) == TI && L->isLoopInvariant(ICI->getOperand(0))))
534  return false;
535  // If we cannot get rid of trunc, bail.
536  if (ICI->isSigned() && !DoesSExtCollapse)
537  return false;
538  if (ICI->isUnsigned() && !DoesZExtCollapse)
539  return false;
540  // For equality, either signed or unsigned works.
541  ICmpUsers.push_back(ICI);
542  }
543 
544  auto CanUseZExt = [&](ICmpInst *ICI) {
545  // Unsigned comparison can be widened as unsigned.
546  if (ICI->isUnsigned())
547  return true;
548  // Is it profitable to do zext?
549  if (!DoesZExtCollapse)
550  return false;
551  // For equality, we can safely zext both parts.
552  if (ICI->isEquality())
553  return true;
554  // Otherwise we can only use zext when comparing two non-negative or two
555  // negative values. But in practice, we will never pass DoesZExtCollapse
556  // check for a negative value, because zext(trunc(x)) is non-negative. So
557  // it only make sense to check for non-negativity here.
558  const SCEV *SCEVOP1 = SE->getSCEV(ICI->getOperand(0));
559  const SCEV *SCEVOP2 = SE->getSCEV(ICI->getOperand(1));
560  return SE->isKnownNonNegative(SCEVOP1) && SE->isKnownNonNegative(SCEVOP2);
561  };
562  // Replace all comparisons against trunc with comparisons against IV.
563  for (auto *ICI : ICmpUsers) {
564  bool IsSwapped = L->isLoopInvariant(ICI->getOperand(0));
565  auto *Op1 = IsSwapped ? ICI->getOperand(0) : ICI->getOperand(1);
566  Instruction *Ext = nullptr;
567  // For signed/unsigned predicate, replace the old comparison with comparison
568  // of immediate IV against sext/zext of the invariant argument. If we can
569  // use either sext or zext (i.e. we are dealing with equality predicate),
570  // then prefer zext as a more canonical form.
571  // TODO: If we see a signed comparison which can be turned into unsigned,
572  // we can do it here for canonicalization purposes.
573  ICmpInst::Predicate Pred = ICI->getPredicate();
574  if (IsSwapped) Pred = ICmpInst::getSwappedPredicate(Pred);
575  if (CanUseZExt(ICI)) {
576  assert(DoesZExtCollapse && "Unprofitable zext?");
577  Ext = new ZExtInst(Op1, IVTy, "zext", ICI);
578  Pred = ICmpInst::getUnsignedPredicate(Pred);
579  } else {
580  assert(DoesSExtCollapse && "Unprofitable sext?");
581  Ext = new SExtInst(Op1, IVTy, "sext", ICI);
582  assert(Pred == ICmpInst::getSignedPredicate(Pred) && "Must be signed!");
583  }
584  bool Changed;
585  L->makeLoopInvariant(Ext, Changed);
586  (void)Changed;
587  ICmpInst *NewICI = new ICmpInst(ICI, Pred, IV, Ext);
588  ICI->replaceAllUsesWith(NewICI);
589  DeadInsts.emplace_back(ICI);
590  }
591 
592  // Trunc no longer needed.
594  DeadInsts.emplace_back(TI);
595  return true;
596 }
597 
598 /// Eliminate an operation that consumes a simple IV and has no observable
599 /// side-effect given the range of IV values. IVOperand is guaranteed SCEVable,
600 /// but UseInst may not be.
601 bool SimplifyIndvar::eliminateIVUser(Instruction *UseInst,
602  Instruction *IVOperand) {
603  if (ICmpInst *ICmp = dyn_cast<ICmpInst>(UseInst)) {
604  eliminateIVComparison(ICmp, IVOperand);
605  return true;
606  }
607  if (BinaryOperator *Bin = dyn_cast<BinaryOperator>(UseInst)) {
608  bool IsSRem = Bin->getOpcode() == Instruction::SRem;
609  if (IsSRem || Bin->getOpcode() == Instruction::URem) {
610  simplifyIVRemainder(Bin, IVOperand, IsSRem);
611  return true;
612  }
613 
614  if (Bin->getOpcode() == Instruction::SDiv)
615  return eliminateSDiv(Bin);
616  }
617 
618  if (auto *WO = dyn_cast<WithOverflowInst>(UseInst))
619  if (eliminateOverflowIntrinsic(WO))
620  return true;
621 
622  if (auto *SI = dyn_cast<SaturatingInst>(UseInst))
623  if (eliminateSaturatingIntrinsic(SI))
624  return true;
625 
626  if (auto *TI = dyn_cast<TruncInst>(UseInst))
627  if (eliminateTrunc(TI))
628  return true;
629 
630  if (eliminateIdentitySCEV(UseInst, IVOperand))
631  return true;
632 
633  return false;
634 }
635 
637  if (auto *BB = L->getLoopPreheader())
638  return BB->getTerminator();
639 
640  return Hint;
641 }
642 
643 /// Replace the UseInst with a loop invariant expression if it is safe.
644 bool SimplifyIndvar::replaceIVUserWithLoopInvariant(Instruction *I) {
645  if (!SE->isSCEVable(I->getType()))
646  return false;
647 
648  // Get the symbolic expression for this instruction.
649  const SCEV *S = SE->getSCEV(I);
650 
651  if (!SE->isLoopInvariant(S, L))
652  return false;
653 
654  // Do not generate something ridiculous even if S is loop invariant.
655  if (Rewriter.isHighCostExpansion(S, L, SCEVCheapExpansionBudget, TTI, I))
656  return false;
657 
658  auto *IP = GetLoopInvariantInsertPosition(L, I);
659 
660  if (!isSafeToExpandAt(S, IP, *SE)) {
661  LLVM_DEBUG(dbgs() << "INDVARS: Can not replace IV user: " << *I
662  << " with non-speculable loop invariant: " << *S << '\n');
663  return false;
664  }
665 
666  auto *Invariant = Rewriter.expandCodeFor(S, I->getType(), IP);
667 
668  I->replaceAllUsesWith(Invariant);
669  LLVM_DEBUG(dbgs() << "INDVARS: Replace IV user: " << *I
670  << " with loop invariant: " << *S << '\n');
671  ++NumFoldedUser;
672  Changed = true;
673  DeadInsts.emplace_back(I);
674  return true;
675 }
676 
677 /// Eliminate any operation that SCEV can prove is an identity function.
678 bool SimplifyIndvar::eliminateIdentitySCEV(Instruction *UseInst,
679  Instruction *IVOperand) {
680  if (!SE->isSCEVable(UseInst->getType()) ||
681  (UseInst->getType() != IVOperand->getType()) ||
682  (SE->getSCEV(UseInst) != SE->getSCEV(IVOperand)))
683  return false;
684 
685  // getSCEV(X) == getSCEV(Y) does not guarantee that X and Y are related in the
686  // dominator tree, even if X is an operand to Y. For instance, in
687  //
688  // %iv = phi i32 {0,+,1}
689  // br %cond, label %left, label %merge
690  //
691  // left:
692  // %X = add i32 %iv, 0
693  // br label %merge
694  //
695  // merge:
696  // %M = phi (%X, %iv)
697  //
698  // getSCEV(%M) == getSCEV(%X) == {0,+,1}, but %X does not dominate %M, and
699  // %M.replaceAllUsesWith(%X) would be incorrect.
700 
701  if (isa<PHINode>(UseInst))
702  // If UseInst is not a PHI node then we know that IVOperand dominates
703  // UseInst directly from the legality of SSA.
704  if (!DT || !DT->dominates(IVOperand, UseInst))
705  return false;
706 
707  if (!LI->replacementPreservesLCSSAForm(UseInst, IVOperand))
708  return false;
709 
710  LLVM_DEBUG(dbgs() << "INDVARS: Eliminated identity: " << *UseInst << '\n');
711 
712  UseInst->replaceAllUsesWith(IVOperand);
713  ++NumElimIdentity;
714  Changed = true;
715  DeadInsts.emplace_back(UseInst);
716  return true;
717 }
718 
719 /// Annotate BO with nsw / nuw if it provably does not signed-overflow /
720 /// unsigned-overflow. Returns true if anything changed, false otherwise.
721 bool SimplifyIndvar::strengthenOverflowingOperation(BinaryOperator *BO,
722  Value *IVOperand) {
723  SCEV::NoWrapFlags Flags;
724  bool Deduced;
725  std::tie(Flags, Deduced) = SE->getStrengthenedNoWrapFlagsFromBinOp(
726  cast<OverflowingBinaryOperator>(BO));
727 
728  if (!Deduced)
729  return Deduced;
730 
732  SCEV::FlagNUW);
734  SCEV::FlagNSW);
735 
736  // The getStrengthenedNoWrapFlagsFromBinOp() check inferred additional nowrap
737  // flags on addrecs while performing zero/sign extensions. We could call
738  // forgetValue() here to make sure those flags also propagate to any other
739  // SCEV expressions based on the addrec. However, this can have pathological
740  // compile-time impact, see https://bugs.llvm.org/show_bug.cgi?id=50384.
741  return Deduced;
742 }
743 
744 /// Annotate the Shr in (X << IVOperand) >> C as exact using the
745 /// information from the IV's range. Returns true if anything changed, false
746 /// otherwise.
747 bool SimplifyIndvar::strengthenRightShift(BinaryOperator *BO,
748  Value *IVOperand) {
749  using namespace llvm::PatternMatch;
750 
751  if (BO->getOpcode() == Instruction::Shl) {
752  bool Changed = false;
753  ConstantRange IVRange = SE->getUnsignedRange(SE->getSCEV(IVOperand));
754  for (auto *U : BO->users()) {
755  const APInt *C;
756  if (match(U,
757  m_AShr(m_Shl(m_Value(), m_Specific(IVOperand)), m_APInt(C))) ||
758  match(U,
759  m_LShr(m_Shl(m_Value(), m_Specific(IVOperand)), m_APInt(C)))) {
760  BinaryOperator *Shr = cast<BinaryOperator>(U);
761  if (!Shr->isExact() && IVRange.getUnsignedMin().uge(*C)) {
762  Shr->setIsExact(true);
763  Changed = true;
764  }
765  }
766  }
767  return Changed;
768  }
769 
770  return false;
771 }
772 
773 /// Add all uses of Def to the current IV's worklist.
774 static void pushIVUsers(
775  Instruction *Def, Loop *L,
777  SmallVectorImpl< std::pair<Instruction*,Instruction*> > &SimpleIVUsers) {
778 
779  for (User *U : Def->users()) {
780  Instruction *UI = cast<Instruction>(U);
781 
782  // Avoid infinite or exponential worklist processing.
783  // Also ensure unique worklist users.
784  // If Def is a LoopPhi, it may not be in the Simplified set, so check for
785  // self edges first.
786  if (UI == Def)
787  continue;
788 
789  // Only change the current Loop, do not change the other parts (e.g. other
790  // Loops).
791  if (!L->contains(UI))
792  continue;
793 
794  // Do not push the same instruction more than once.
795  if (!Simplified.insert(UI).second)
796  continue;
797 
798  SimpleIVUsers.push_back(std::make_pair(UI, Def));
799  }
800 }
801 
802 /// Return true if this instruction generates a simple SCEV
803 /// expression in terms of that IV.
804 ///
805 /// This is similar to IVUsers' isInteresting() but processes each instruction
806 /// non-recursively when the operand is already known to be a simpleIVUser.
807 ///
808 static bool isSimpleIVUser(Instruction *I, const Loop *L, ScalarEvolution *SE) {
809  if (!SE->isSCEVable(I->getType()))
810  return false;
811 
812  // Get the symbolic expression for this instruction.
813  const SCEV *S = SE->getSCEV(I);
814 
815  // Only consider affine recurrences.
816  const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(S);
817  if (AR && AR->getLoop() == L)
818  return true;
819 
820  return false;
821 }
822 
823 /// Iteratively perform simplification on a worklist of users
824 /// of the specified induction variable. Each successive simplification may push
825 /// more users which may themselves be candidates for simplification.
826 ///
827 /// This algorithm does not require IVUsers analysis. Instead, it simplifies
828 /// instructions in-place during analysis. Rather than rewriting induction
829 /// variables bottom-up from their users, it transforms a chain of IVUsers
830 /// top-down, updating the IR only when it encounters a clear optimization
831 /// opportunity.
832 ///
833 /// Once DisableIVRewrite is default, LSR will be the only client of IVUsers.
834 ///
835 void SimplifyIndvar::simplifyUsers(PHINode *CurrIV, IVVisitor *V) {
836  if (!SE->isSCEVable(CurrIV->getType()))
837  return;
838 
839  // Instructions processed by SimplifyIndvar for CurrIV.
841 
842  // Use-def pairs if IV users waiting to be processed for CurrIV.
844 
845  // Push users of the current LoopPhi. In rare cases, pushIVUsers may be
846  // called multiple times for the same LoopPhi. This is the proper thing to
847  // do for loop header phis that use each other.
848  pushIVUsers(CurrIV, L, Simplified, SimpleIVUsers);
849 
850  while (!SimpleIVUsers.empty()) {
851  std::pair<Instruction*, Instruction*> UseOper =
852  SimpleIVUsers.pop_back_val();
853  Instruction *UseInst = UseOper.first;
854 
855  // If a user of the IndVar is trivially dead, we prefer just to mark it dead
856  // rather than try to do some complex analysis or transformation (such as
857  // widening) basing on it.
858  // TODO: Propagate TLI and pass it here to handle more cases.
859  if (isInstructionTriviallyDead(UseInst, /* TLI */ nullptr)) {
860  DeadInsts.emplace_back(UseInst);
861  continue;
862  }
863 
864  // Bypass back edges to avoid extra work.
865  if (UseInst == CurrIV) continue;
866 
867  // Try to replace UseInst with a loop invariant before any other
868  // simplifications.
869  if (replaceIVUserWithLoopInvariant(UseInst))
870  continue;
871 
872  Instruction *IVOperand = UseOper.second;
873  for (unsigned N = 0; IVOperand; ++N) {
874  assert(N <= Simplified.size() && "runaway iteration");
875 
876  Value *NewOper = foldIVUser(UseInst, IVOperand);
877  if (!NewOper)
878  break; // done folding
879  IVOperand = dyn_cast<Instruction>(NewOper);
880  }
881  if (!IVOperand)
882  continue;
883 
884  if (eliminateIVUser(UseInst, IVOperand)) {
885  pushIVUsers(IVOperand, L, Simplified, SimpleIVUsers);
886  continue;
887  }
888 
889  if (BinaryOperator *BO = dyn_cast<BinaryOperator>(UseInst)) {
890  if ((isa<OverflowingBinaryOperator>(BO) &&
891  strengthenOverflowingOperation(BO, IVOperand)) ||
892  (isa<ShlOperator>(BO) && strengthenRightShift(BO, IVOperand))) {
893  // re-queue uses of the now modified binary operator and fall
894  // through to the checks that remain.
895  pushIVUsers(IVOperand, L, Simplified, SimpleIVUsers);
896  }
897  }
898 
899  CastInst *Cast = dyn_cast<CastInst>(UseInst);
900  if (V && Cast) {
901  V->visitCast(Cast);
902  continue;
903  }
904  if (isSimpleIVUser(UseInst, L, SE)) {
905  pushIVUsers(UseInst, L, Simplified, SimpleIVUsers);
906  }
907  }
908 }
909 
910 namespace llvm {
911 
913 
914 /// Simplify instructions that use this induction variable
915 /// by using ScalarEvolution to analyze the IV's recurrence.
917  LoopInfo *LI, const TargetTransformInfo *TTI,
920  SimplifyIndvar SIV(LI->getLoopFor(CurrIV->getParent()), SE, DT, LI, TTI,
921  Rewriter, Dead);
922  SIV.simplifyUsers(CurrIV, V);
923  return SIV.hasChanged();
924 }
925 
926 /// Simplify users of induction variables within this
927 /// loop. This does not actually change or add IVs.
929  LoopInfo *LI, const TargetTransformInfo *TTI,
931  SCEVExpander Rewriter(*SE, SE->getDataLayout(), "indvars");
932 #ifndef NDEBUG
933  Rewriter.setDebugType(DEBUG_TYPE);
934 #endif
935  bool Changed = false;
936  for (BasicBlock::iterator I = L->getHeader()->begin(); isa<PHINode>(I); ++I) {
937  Changed |=
938  simplifyUsersOfIV(cast<PHINode>(I), SE, DT, LI, TTI, Dead, Rewriter);
939  }
940  return Changed;
941 }
942 
943 } // namespace llvm
944 
945 //===----------------------------------------------------------------------===//
946 // Widen Induction Variables - Extend the width of an IV to cover its
947 // widest uses.
948 //===----------------------------------------------------------------------===//
949 
950 class WidenIV {
951  // Parameters
952  PHINode *OrigPhi;
953  Type *WideType;
954 
955  // Context
956  LoopInfo *LI;
957  Loop *L;
958  ScalarEvolution *SE;
959  DominatorTree *DT;
960 
961  // Does the module have any calls to the llvm.experimental.guard intrinsic
962  // at all? If not we can avoid scanning instructions looking for guards.
963  bool HasGuards;
964 
965  bool UsePostIncrementRanges;
966 
967  // Statistics
968  unsigned NumElimExt = 0;
969  unsigned NumWidened = 0;
970 
971  // Result
972  PHINode *WidePhi = nullptr;
973  Instruction *WideInc = nullptr;
974  const SCEV *WideIncExpr = nullptr;
976 
978 
979  enum ExtendKind { ZeroExtended, SignExtended, Unknown };
980 
981  // A map tracking the kind of extension used to widen each narrow IV
982  // and narrow IV user.
983  // Key: pointer to a narrow IV or IV user.
984  // Value: the kind of extension used to widen this Instruction.
985  DenseMap<AssertingVH<Instruction>, ExtendKind> ExtendKindMap;
986 
987  using DefUserPair = std::pair<AssertingVH<Value>, AssertingVH<Instruction>>;
988 
989  // A map with control-dependent ranges for post increment IV uses. The key is
990  // a pair of IV def and a use of this def denoting the context. The value is
991  // a ConstantRange representing possible values of the def at the given
992  // context.
993  DenseMap<DefUserPair, ConstantRange> PostIncRangeInfos;
994 
995  Optional<ConstantRange> getPostIncRangeInfo(Value *Def,
996  Instruction *UseI) {
997  DefUserPair Key(Def, UseI);
998  auto It = PostIncRangeInfos.find(Key);
999  return It == PostIncRangeInfos.end()
1001  : Optional<ConstantRange>(It->second);
1002  }
1003 
1004  void calculatePostIncRanges(PHINode *OrigPhi);
1005  void calculatePostIncRange(Instruction *NarrowDef, Instruction *NarrowUser);
1006 
1007  void updatePostIncRangeInfo(Value *Def, Instruction *UseI, ConstantRange R) {
1008  DefUserPair Key(Def, UseI);
1009  auto It = PostIncRangeInfos.find(Key);
1010  if (It == PostIncRangeInfos.end())
1011  PostIncRangeInfos.insert({Key, R});
1012  else
1013  It->second = R.intersectWith(It->second);
1014  }
1015 
1016 public:
1017  /// Record a link in the Narrow IV def-use chain along with the WideIV that
1018  /// computes the same value as the Narrow IV def. This avoids caching Use*
1019  /// pointers.
1023  Instruction *WideDef = nullptr;
1024 
1025  // True if the narrow def is never negative. Tracking this information lets
1026  // us use a sign extension instead of a zero extension or vice versa, when
1027  // profitable and legal.
1028  bool NeverNegative = false;
1029 
1031  bool NeverNegative)
1032  : NarrowDef(ND), NarrowUse(NU), WideDef(WD),
1034  };
1035 
1036  WidenIV(const WideIVInfo &WI, LoopInfo *LInfo, ScalarEvolution *SEv,
1038  bool HasGuards, bool UsePostIncrementRanges = true);
1039 
1041 
1042  unsigned getNumElimExt() { return NumElimExt; };
1043  unsigned getNumWidened() { return NumWidened; };
1044 
1045 protected:
1046  Value *createExtendInst(Value *NarrowOper, Type *WideType, bool IsSigned,
1047  Instruction *Use);
1048 
1049  Instruction *cloneIVUser(NarrowIVDefUse DU, const SCEVAddRecExpr *WideAR);
1050  Instruction *cloneArithmeticIVUser(NarrowIVDefUse DU,
1051  const SCEVAddRecExpr *WideAR);
1052  Instruction *cloneBitwiseIVUser(NarrowIVDefUse DU);
1053 
1054  ExtendKind getExtendKind(Instruction *I);
1055 
1056  using WidenedRecTy = std::pair<const SCEVAddRecExpr *, ExtendKind>;
1057 
1059 
1061 
1062  const SCEV *getSCEVByOpCode(const SCEV *LHS, const SCEV *RHS,
1063  unsigned OpCode) const;
1064 
1066 
1069 
1070  void pushNarrowIVUsers(Instruction *NarrowDef, Instruction *WideDef);
1071 
1072 private:
1073  SmallVector<NarrowIVDefUse, 8> NarrowIVUsers;
1074 };
1075 
1076 
1077 /// Determine the insertion point for this user. By default, insert immediately
1078 /// before the user. SCEVExpander or LICM will hoist loop invariants out of the
1079 /// loop. For PHI nodes, there may be multiple uses, so compute the nearest
1080 /// common dominator for the incoming blocks. A nullptr can be returned if no
1081 /// viable location is found: it may happen if User is a PHI and Def only comes
1082 /// to this PHI from unreachable blocks.
1084  DominatorTree *DT, LoopInfo *LI) {
1085  PHINode *PHI = dyn_cast<PHINode>(User);
1086  if (!PHI)
1087  return User;
1088 
1089  Instruction *InsertPt = nullptr;
1090  for (unsigned i = 0, e = PHI->getNumIncomingValues(); i != e; ++i) {
1091  if (PHI->getIncomingValue(i) != Def)
1092  continue;
1093 
1094  BasicBlock *InsertBB = PHI->getIncomingBlock(i);
1095 
1096  if (!DT->isReachableFromEntry(InsertBB))
1097  continue;
1098 
1099  if (!InsertPt) {
1100  InsertPt = InsertBB->getTerminator();
1101  continue;
1102  }
1103  InsertBB = DT->findNearestCommonDominator(InsertPt->getParent(), InsertBB);
1104  InsertPt = InsertBB->getTerminator();
1105  }
1106 
1107  // If we have skipped all inputs, it means that Def only comes to Phi from
1108  // unreachable blocks.
1109  if (!InsertPt)
1110  return nullptr;
1111 
1112  auto *DefI = dyn_cast<Instruction>(Def);
1113  if (!DefI)
1114  return InsertPt;
1115 
1116  assert(DT->dominates(DefI, InsertPt) && "def does not dominate all uses");
1117 
1118  auto *L = LI->getLoopFor(DefI->getParent());
1119  assert(!L || L->contains(LI->getLoopFor(InsertPt->getParent())));
1120 
1121  for (auto *DTN = (*DT)[InsertPt->getParent()]; DTN; DTN = DTN->getIDom())
1122  if (LI->getLoopFor(DTN->getBlock()) == L)
1123  return DTN->getBlock()->getTerminator();
1124 
1125  llvm_unreachable("DefI dominates InsertPt!");
1126 }
1127 
1130  bool HasGuards, bool UsePostIncrementRanges)
1131  : OrigPhi(WI.NarrowIV), WideType(WI.WidestNativeType), LI(LInfo),
1132  L(LI->getLoopFor(OrigPhi->getParent())), SE(SEv), DT(DTree),
1133  HasGuards(HasGuards), UsePostIncrementRanges(UsePostIncrementRanges),
1134  DeadInsts(DI) {
1135  assert(L->getHeader() == OrigPhi->getParent() && "Phi must be an IV");
1136  ExtendKindMap[OrigPhi] = WI.IsSigned ? SignExtended : ZeroExtended;
1137 }
1138 
1139 Value *WidenIV::createExtendInst(Value *NarrowOper, Type *WideType,
1140  bool IsSigned, Instruction *Use) {
1141  // Set the debug location and conservative insertion point.
1143  // Hoist the insertion point into loop preheaders as far as possible.
1144  for (const Loop *L = LI->getLoopFor(Use->getParent());
1145  L && L->getLoopPreheader() && L->isLoopInvariant(NarrowOper);
1146  L = L->getParentLoop())
1147  Builder.SetInsertPoint(L->getLoopPreheader()->getTerminator());
1148 
1149  return IsSigned ? Builder.CreateSExt(NarrowOper, WideType) :
1150  Builder.CreateZExt(NarrowOper, WideType);
1151 }
1152 
1153 /// Instantiate a wide operation to replace a narrow operation. This only needs
1154 /// to handle operations that can evaluation to SCEVAddRec. It can safely return
1155 /// 0 for any operation we decide not to clone.
1157  const SCEVAddRecExpr *WideAR) {
1158  unsigned Opcode = DU.NarrowUse->getOpcode();
1159  switch (Opcode) {
1160  default:
1161  return nullptr;
1162  case Instruction::Add:
1163  case Instruction::Mul:
1164  case Instruction::UDiv:
1165  case Instruction::Sub:
1166  return cloneArithmeticIVUser(DU, WideAR);
1167 
1168  case Instruction::And:
1169  case Instruction::Or:
1170  case Instruction::Xor:
1171  case Instruction::Shl:
1172  case Instruction::LShr:
1173  case Instruction::AShr:
1174  return cloneBitwiseIVUser(DU);
1175  }
1176 }
1177 
1179  Instruction *NarrowUse = DU.NarrowUse;
1180  Instruction *NarrowDef = DU.NarrowDef;
1181  Instruction *WideDef = DU.WideDef;
1182 
1183  LLVM_DEBUG(dbgs() << "Cloning bitwise IVUser: " << *NarrowUse << "\n");
1184 
1185  // Replace NarrowDef operands with WideDef. Otherwise, we don't know anything
1186  // about the narrow operand yet so must insert a [sz]ext. It is probably loop
1187  // invariant and will be folded or hoisted. If it actually comes from a
1188  // widened IV, it should be removed during a future call to widenIVUse.
1189  bool IsSigned = getExtendKind(NarrowDef) == SignExtended;
1190  Value *LHS = (NarrowUse->getOperand(0) == NarrowDef)
1191  ? WideDef
1192  : createExtendInst(NarrowUse->getOperand(0), WideType,
1193  IsSigned, NarrowUse);
1194  Value *RHS = (NarrowUse->getOperand(1) == NarrowDef)
1195  ? WideDef
1196  : createExtendInst(NarrowUse->getOperand(1), WideType,
1197  IsSigned, NarrowUse);
1198 
1199  auto *NarrowBO = cast<BinaryOperator>(NarrowUse);
1200  auto *WideBO = BinaryOperator::Create(NarrowBO->getOpcode(), LHS, RHS,
1201  NarrowBO->getName());
1202  IRBuilder<> Builder(NarrowUse);
1203  Builder.Insert(WideBO);
1204  WideBO->copyIRFlags(NarrowBO);
1205  return WideBO;
1206 }
1207 
1209  const SCEVAddRecExpr *WideAR) {
1210  Instruction *NarrowUse = DU.NarrowUse;
1211  Instruction *NarrowDef = DU.NarrowDef;
1212  Instruction *WideDef = DU.WideDef;
1213 
1214  LLVM_DEBUG(dbgs() << "Cloning arithmetic IVUser: " << *NarrowUse << "\n");
1215 
1216  unsigned IVOpIdx = (NarrowUse->getOperand(0) == NarrowDef) ? 0 : 1;
1217 
1218  // We're trying to find X such that
1219  //
1220  // Widen(NarrowDef `op` NonIVNarrowDef) == WideAR == WideDef `op.wide` X
1221  //
1222  // We guess two solutions to X, sext(NonIVNarrowDef) and zext(NonIVNarrowDef),
1223  // and check using SCEV if any of them are correct.
1224 
1225  // Returns true if extending NonIVNarrowDef according to `SignExt` is a
1226  // correct solution to X.
1227  auto GuessNonIVOperand = [&](bool SignExt) {
1228  const SCEV *WideLHS;
1229  const SCEV *WideRHS;
1230 
1231  auto GetExtend = [this, SignExt](const SCEV *S, Type *Ty) {
1232  if (SignExt)
1233  return SE->getSignExtendExpr(S, Ty);
1234  return SE->getZeroExtendExpr(S, Ty);
1235  };
1236 
1237  if (IVOpIdx == 0) {
1238  WideLHS = SE->getSCEV(WideDef);
1239  const SCEV *NarrowRHS = SE->getSCEV(NarrowUse->getOperand(1));
1240  WideRHS = GetExtend(NarrowRHS, WideType);
1241  } else {
1242  const SCEV *NarrowLHS = SE->getSCEV(NarrowUse->getOperand(0));
1243  WideLHS = GetExtend(NarrowLHS, WideType);
1244  WideRHS = SE->getSCEV(WideDef);
1245  }
1246 
1247  // WideUse is "WideDef `op.wide` X" as described in the comment.
1248  const SCEV *WideUse =
1249  getSCEVByOpCode(WideLHS, WideRHS, NarrowUse->getOpcode());
1250 
1251  return WideUse == WideAR;
1252  };
1253 
1254  bool SignExtend = getExtendKind(NarrowDef) == SignExtended;
1255  if (!GuessNonIVOperand(SignExtend)) {
1256  SignExtend = !SignExtend;
1257  if (!GuessNonIVOperand(SignExtend))
1258  return nullptr;
1259  }
1260 
1261  Value *LHS = (NarrowUse->getOperand(0) == NarrowDef)
1262  ? WideDef
1263  : createExtendInst(NarrowUse->getOperand(0), WideType,
1264  SignExtend, NarrowUse);
1265  Value *RHS = (NarrowUse->getOperand(1) == NarrowDef)
1266  ? WideDef
1267  : createExtendInst(NarrowUse->getOperand(1), WideType,
1268  SignExtend, NarrowUse);
1269 
1270  auto *NarrowBO = cast<BinaryOperator>(NarrowUse);
1271  auto *WideBO = BinaryOperator::Create(NarrowBO->getOpcode(), LHS, RHS,
1272  NarrowBO->getName());
1273 
1274  IRBuilder<> Builder(NarrowUse);
1275  Builder.Insert(WideBO);
1276  WideBO->copyIRFlags(NarrowBO);
1277  return WideBO;
1278 }
1279 
1280 WidenIV::ExtendKind WidenIV::getExtendKind(Instruction *I) {
1281  auto It = ExtendKindMap.find(I);
1282  assert(It != ExtendKindMap.end() && "Instruction not yet extended!");
1283  return It->second;
1284 }
1285 
1286 const SCEV *WidenIV::getSCEVByOpCode(const SCEV *LHS, const SCEV *RHS,
1287  unsigned OpCode) const {
1288  switch (OpCode) {
1289  case Instruction::Add:
1290  return SE->getAddExpr(LHS, RHS);
1291  case Instruction::Sub:
1292  return SE->getMinusSCEV(LHS, RHS);
1293  case Instruction::Mul:
1294  return SE->getMulExpr(LHS, RHS);
1295  case Instruction::UDiv:
1296  return SE->getUDivExpr(LHS, RHS);
1297  default:
1298  llvm_unreachable("Unsupported opcode.");
1299  };
1300 }
1301 
1302 /// No-wrap operations can transfer sign extension of their result to their
1303 /// operands. Generate the SCEV value for the widened operation without
1304 /// actually modifying the IR yet. If the expression after extending the
1305 /// operands is an AddRec for this loop, return the AddRec and the kind of
1306 /// extension used.
1309  // Handle the common case of add<nsw/nuw>
1310  const unsigned OpCode = DU.NarrowUse->getOpcode();
1311  // Only Add/Sub/Mul instructions supported yet.
1312  if (OpCode != Instruction::Add && OpCode != Instruction::Sub &&
1313  OpCode != Instruction::Mul)
1314  return {nullptr, Unknown};
1315 
1316  // One operand (NarrowDef) has already been extended to WideDef. Now determine
1317  // if extending the other will lead to a recurrence.
1318  const unsigned ExtendOperIdx =
1319  DU.NarrowUse->getOperand(0) == DU.NarrowDef ? 1 : 0;
1320  assert(DU.NarrowUse->getOperand(1-ExtendOperIdx) == DU.NarrowDef && "bad DU");
1321 
1322  const SCEV *ExtendOperExpr = nullptr;
1323  const OverflowingBinaryOperator *OBO =
1324  cast<OverflowingBinaryOperator>(DU.NarrowUse);
1325  ExtendKind ExtKind = getExtendKind(DU.NarrowDef);
1326  if (ExtKind == SignExtended && OBO->hasNoSignedWrap())
1327  ExtendOperExpr = SE->getSignExtendExpr(
1328  SE->getSCEV(DU.NarrowUse->getOperand(ExtendOperIdx)), WideType);
1329  else if(ExtKind == ZeroExtended && OBO->hasNoUnsignedWrap())
1330  ExtendOperExpr = SE->getZeroExtendExpr(
1331  SE->getSCEV(DU.NarrowUse->getOperand(ExtendOperIdx)), WideType);
1332  else
1333  return {nullptr, Unknown};
1334 
1335  // When creating this SCEV expr, don't apply the current operations NSW or NUW
1336  // flags. This instruction may be guarded by control flow that the no-wrap
1337  // behavior depends on. Non-control-equivalent instructions can be mapped to
1338  // the same SCEV expression, and it would be incorrect to transfer NSW/NUW
1339  // semantics to those operations.
1340  const SCEV *lhs = SE->getSCEV(DU.WideDef);
1341  const SCEV *rhs = ExtendOperExpr;
1342 
1343  // Let's swap operands to the initial order for the case of non-commutative
1344  // operations, like SUB. See PR21014.
1345  if (ExtendOperIdx == 0)
1346  std::swap(lhs, rhs);
1347  const SCEVAddRecExpr *AddRec =
1348  dyn_cast<SCEVAddRecExpr>(getSCEVByOpCode(lhs, rhs, OpCode));
1349 
1350  if (!AddRec || AddRec->getLoop() != L)
1351  return {nullptr, Unknown};
1352 
1353  return {AddRec, ExtKind};
1354 }
1355 
1356 /// Is this instruction potentially interesting for further simplification after
1357 /// widening it's type? In other words, can the extend be safely hoisted out of
1358 /// the loop with SCEV reducing the value to a recurrence on the same loop. If
1359 /// so, return the extended recurrence and the kind of extension used. Otherwise
1360 /// return {nullptr, Unknown}.
1362  if (!DU.NarrowUse->getType()->isIntegerTy())
1363  return {nullptr, Unknown};
1364 
1365  const SCEV *NarrowExpr = SE->getSCEV(DU.NarrowUse);
1366  if (SE->getTypeSizeInBits(NarrowExpr->getType()) >=
1367  SE->getTypeSizeInBits(WideType)) {
1368  // NarrowUse implicitly widens its operand. e.g. a gep with a narrow
1369  // index. So don't follow this use.
1370  return {nullptr, Unknown};
1371  }
1372 
1373  const SCEV *WideExpr;
1374  ExtendKind ExtKind;
1375  if (DU.NeverNegative) {
1376  WideExpr = SE->getSignExtendExpr(NarrowExpr, WideType);
1377  if (isa<SCEVAddRecExpr>(WideExpr))
1378  ExtKind = SignExtended;
1379  else {
1380  WideExpr = SE->getZeroExtendExpr(NarrowExpr, WideType);
1381  ExtKind = ZeroExtended;
1382  }
1383  } else if (getExtendKind(DU.NarrowDef) == SignExtended) {
1384  WideExpr = SE->getSignExtendExpr(NarrowExpr, WideType);
1385  ExtKind = SignExtended;
1386  } else {
1387  WideExpr = SE->getZeroExtendExpr(NarrowExpr, WideType);
1388  ExtKind = ZeroExtended;
1389  }
1390  const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(WideExpr);
1391  if (!AddRec || AddRec->getLoop() != L)
1392  return {nullptr, Unknown};
1393  return {AddRec, ExtKind};
1394 }
1395 
1396 /// This IV user cannot be widened. Replace this use of the original narrow IV
1397 /// with a truncation of the new wide IV to isolate and eliminate the narrow IV.
1399  LoopInfo *LI) {
1400  auto *InsertPt = getInsertPointForUses(DU.NarrowUse, DU.NarrowDef, DT, LI);
1401  if (!InsertPt)
1402  return;
1403  LLVM_DEBUG(dbgs() << "INDVARS: Truncate IV " << *DU.WideDef << " for user "
1404  << *DU.NarrowUse << "\n");
1405  IRBuilder<> Builder(InsertPt);
1406  Value *Trunc = Builder.CreateTrunc(DU.WideDef, DU.NarrowDef->getType());
1407  DU.NarrowUse->replaceUsesOfWith(DU.NarrowDef, Trunc);
1408 }
1409 
1410 /// If the narrow use is a compare instruction, then widen the compare
1411 // (and possibly the other operand). The extend operation is hoisted into the
1412 // loop preheader as far as possible.
1414  ICmpInst *Cmp = dyn_cast<ICmpInst>(DU.NarrowUse);
1415  if (!Cmp)
1416  return false;
1417 
1418  // We can legally widen the comparison in the following two cases:
1419  //
1420  // - The signedness of the IV extension and comparison match
1421  //
1422  // - The narrow IV is always positive (and thus its sign extension is equal
1423  // to its zero extension). For instance, let's say we're zero extending
1424  // %narrow for the following use
1425  //
1426  // icmp slt i32 %narrow, %val ... (A)
1427  //
1428  // and %narrow is always positive. Then
1429  //
1430  // (A) == icmp slt i32 sext(%narrow), sext(%val)
1431  // == icmp slt i32 zext(%narrow), sext(%val)
1432  bool IsSigned = getExtendKind(DU.NarrowDef) == SignExtended;
1433  if (!(DU.NeverNegative || IsSigned == Cmp->isSigned()))
1434  return false;
1435 
1436  Value *Op = Cmp->getOperand(Cmp->getOperand(0) == DU.NarrowDef ? 1 : 0);
1437  unsigned CastWidth = SE->getTypeSizeInBits(Op->getType());
1438  unsigned IVWidth = SE->getTypeSizeInBits(WideType);
1439  assert(CastWidth <= IVWidth && "Unexpected width while widening compare.");
1440 
1441  // Widen the compare instruction.
1442  auto *InsertPt = getInsertPointForUses(DU.NarrowUse, DU.NarrowDef, DT, LI);
1443  if (!InsertPt)
1444  return false;
1445  IRBuilder<> Builder(InsertPt);
1447 
1448  // Widen the other operand of the compare, if necessary.
1449  if (CastWidth < IVWidth) {
1450  Value *ExtOp = createExtendInst(Op, WideType, Cmp->isSigned(), Cmp);
1451  DU.NarrowUse->replaceUsesOfWith(Op, ExtOp);
1452  }
1453  return true;
1454 }
1455 
1456 // The widenIVUse avoids generating trunc by evaluating the use as AddRec, this
1457 // will not work when:
1458 // 1) SCEV traces back to an instruction inside the loop that SCEV can not
1459 // expand, eg. add %indvar, (load %addr)
1460 // 2) SCEV finds a loop variant, eg. add %indvar, %loopvariant
1461 // While SCEV fails to avoid trunc, we can still try to use instruction
1462 // combining approach to prove trunc is not required. This can be further
1463 // extended with other instruction combining checks, but for now we handle the
1464 // following case (sub can be "add" and "mul", "nsw + sext" can be "nus + zext")
1465 //
1466 // Src:
1467 // %c = sub nsw %b, %indvar
1468 // %d = sext %c to i64
1469 // Dst:
1470 // %indvar.ext1 = sext %indvar to i64
1471 // %m = sext %b to i64
1472 // %d = sub nsw i64 %m, %indvar.ext1
1473 // Therefore, as long as the result of add/sub/mul is extended to wide type, no
1474 // trunc is required regardless of how %b is generated. This pattern is common
1475 // when calculating address in 64 bit architecture
1477  Instruction *NarrowUse = DU.NarrowUse;
1478  Instruction *NarrowDef = DU.NarrowDef;
1479  Instruction *WideDef = DU.WideDef;
1480 
1481  // Handle the common case of add<nsw/nuw>
1482  const unsigned OpCode = NarrowUse->getOpcode();
1483  // Only Add/Sub/Mul instructions are supported.
1484  if (OpCode != Instruction::Add && OpCode != Instruction::Sub &&
1485  OpCode != Instruction::Mul)
1486  return false;
1487 
1488  // The operand that is not defined by NarrowDef of DU. Let's call it the
1489  // other operand.
1490  assert((NarrowUse->getOperand(0) == NarrowDef ||
1491  NarrowUse->getOperand(1) == NarrowDef) &&
1492  "bad DU");
1493 
1494  const OverflowingBinaryOperator *OBO =
1495  cast<OverflowingBinaryOperator>(NarrowUse);
1496  ExtendKind ExtKind = getExtendKind(NarrowDef);
1497  bool CanSignExtend = ExtKind == SignExtended && OBO->hasNoSignedWrap();
1498  bool CanZeroExtend = ExtKind == ZeroExtended && OBO->hasNoUnsignedWrap();
1499  auto AnotherOpExtKind = ExtKind;
1500 
1501  // Check that all uses are either:
1502  // - narrow def (in case of we are widening the IV increment);
1503  // - single-input LCSSA Phis;
1504  // - comparison of the chosen type;
1505  // - extend of the chosen type (raison d'etre).
1507  SmallVector<PHINode *, 4> LCSSAPhiUsers;
1508  SmallVector<ICmpInst *, 4> ICmpUsers;
1509  for (Use &U : NarrowUse->uses()) {
1510  Instruction *User = cast<Instruction>(U.getUser());
1511  if (User == NarrowDef)
1512  continue;
1513  if (!L->contains(User)) {
1514  auto *LCSSAPhi = cast<PHINode>(User);
1515  // Make sure there is only 1 input, so that we don't have to split
1516  // critical edges.
1517  if (LCSSAPhi->getNumOperands() != 1)
1518  return false;
1519  LCSSAPhiUsers.push_back(LCSSAPhi);
1520  continue;
1521  }
1522  if (auto *ICmp = dyn_cast<ICmpInst>(User)) {
1523  auto Pred = ICmp->getPredicate();
1524  // We have 3 types of predicates: signed, unsigned and equality
1525  // predicates. For equality, it's legal to widen icmp for either sign and
1526  // zero extend. For sign extend, we can also do so for signed predicates,
1527  // likeweise for zero extend we can widen icmp for unsigned predicates.
1528  if (ExtKind == ZeroExtended && ICmpInst::isSigned(Pred))
1529  return false;
1530  if (ExtKind == SignExtended && ICmpInst::isUnsigned(Pred))
1531  return false;
1532  ICmpUsers.push_back(ICmp);
1533  continue;
1534  }
1535  if (ExtKind == SignExtended)
1536  User = dyn_cast<SExtInst>(User);
1537  else
1538  User = dyn_cast<ZExtInst>(User);
1539  if (!User || User->getType() != WideType)
1540  return false;
1541  ExtUsers.push_back(User);
1542  }
1543  if (ExtUsers.empty()) {
1544  DeadInsts.emplace_back(NarrowUse);
1545  return true;
1546  }
1547 
1548  // We'll prove some facts that should be true in the context of ext users. If
1549  // there is no users, we are done now. If there are some, pick their common
1550  // dominator as context.
1551  const Instruction *CtxI = findCommonDominator(ExtUsers, *DT);
1552 
1553  if (!CanSignExtend && !CanZeroExtend) {
1554  // Because InstCombine turns 'sub nuw' to 'add' losing the no-wrap flag, we
1555  // will most likely not see it. Let's try to prove it.
1556  if (OpCode != Instruction::Add)
1557  return false;
1558  if (ExtKind != ZeroExtended)
1559  return false;
1560  const SCEV *LHS = SE->getSCEV(OBO->getOperand(0));
1561  const SCEV *RHS = SE->getSCEV(OBO->getOperand(1));
1562  // TODO: Support case for NarrowDef = NarrowUse->getOperand(1).
1563  if (NarrowUse->getOperand(0) != NarrowDef)
1564  return false;
1565  if (!SE->isKnownNegative(RHS))
1566  return false;
1567  bool ProvedSubNUW = SE->isKnownPredicateAt(ICmpInst::ICMP_UGE, LHS,
1568  SE->getNegativeSCEV(RHS), CtxI);
1569  if (!ProvedSubNUW)
1570  return false;
1571  // In fact, our 'add' is 'sub nuw'. We will need to widen the 2nd operand as
1572  // neg(zext(neg(op))), which is basically sext(op).
1573  AnotherOpExtKind = SignExtended;
1574  }
1575 
1576  // Verifying that Defining operand is an AddRec
1577  const SCEV *Op1 = SE->getSCEV(WideDef);
1578  const SCEVAddRecExpr *AddRecOp1 = dyn_cast<SCEVAddRecExpr>(Op1);
1579  if (!AddRecOp1 || AddRecOp1->getLoop() != L)
1580  return false;
1581 
1582  LLVM_DEBUG(dbgs() << "Cloning arithmetic IVUser: " << *NarrowUse << "\n");
1583 
1584  // Generating a widening use instruction.
1585  Value *LHS = (NarrowUse->getOperand(0) == NarrowDef)
1586  ? WideDef
1587  : createExtendInst(NarrowUse->getOperand(0), WideType,
1588  AnotherOpExtKind, NarrowUse);
1589  Value *RHS = (NarrowUse->getOperand(1) == NarrowDef)
1590  ? WideDef
1591  : createExtendInst(NarrowUse->getOperand(1), WideType,
1592  AnotherOpExtKind, NarrowUse);
1593 
1594  auto *NarrowBO = cast<BinaryOperator>(NarrowUse);
1595  auto *WideBO = BinaryOperator::Create(NarrowBO->getOpcode(), LHS, RHS,
1596  NarrowBO->getName());
1597  IRBuilder<> Builder(NarrowUse);
1598  Builder.Insert(WideBO);
1599  WideBO->copyIRFlags(NarrowBO);
1600  ExtendKindMap[NarrowUse] = ExtKind;
1601 
1602  for (Instruction *User : ExtUsers) {
1603  assert(User->getType() == WideType && "Checked before!");
1604  LLVM_DEBUG(dbgs() << "INDVARS: eliminating " << *User << " replaced by "
1605  << *WideBO << "\n");
1606  ++NumElimExt;
1607  User->replaceAllUsesWith(WideBO);
1608  DeadInsts.emplace_back(User);
1609  }
1610 
1611  for (PHINode *User : LCSSAPhiUsers) {
1612  assert(User->getNumOperands() == 1 && "Checked before!");
1613  Builder.SetInsertPoint(User);
1614  auto *WidePN =
1615  Builder.CreatePHI(WideBO->getType(), 1, User->getName() + ".wide");
1616  BasicBlock *LoopExitingBlock = User->getParent()->getSinglePredecessor();
1617  assert(LoopExitingBlock && L->contains(LoopExitingBlock) &&
1618  "Not a LCSSA Phi?");
1619  WidePN->addIncoming(WideBO, LoopExitingBlock);
1620  Builder.SetInsertPoint(&*User->getParent()->getFirstInsertionPt());
1621  auto *TruncPN = Builder.CreateTrunc(WidePN, User->getType());
1622  User->replaceAllUsesWith(TruncPN);
1623  DeadInsts.emplace_back(User);
1624  }
1625 
1626  for (ICmpInst *User : ICmpUsers) {
1627  Builder.SetInsertPoint(User);
1628  auto ExtendedOp = [&](Value * V)->Value * {
1629  if (V == NarrowUse)
1630  return WideBO;
1631  if (ExtKind == ZeroExtended)
1632  return Builder.CreateZExt(V, WideBO->getType());
1633  else
1634  return Builder.CreateSExt(V, WideBO->getType());
1635  };
1636  auto Pred = User->getPredicate();
1637  auto *LHS = ExtendedOp(User->getOperand(0));
1638  auto *RHS = ExtendedOp(User->getOperand(1));
1639  auto *WideCmp =
1640  Builder.CreateICmp(Pred, LHS, RHS, User->getName() + ".wide");
1641  User->replaceAllUsesWith(WideCmp);
1642  DeadInsts.emplace_back(User);
1643  }
1644 
1645  return true;
1646 }
1647 
1648 /// Determine whether an individual user of the narrow IV can be widened. If so,
1649 /// return the wide clone of the user.
1651  assert(ExtendKindMap.count(DU.NarrowDef) &&
1652  "Should already know the kind of extension used to widen NarrowDef");
1653 
1654  // Stop traversing the def-use chain at inner-loop phis or post-loop phis.
1655  if (PHINode *UsePhi = dyn_cast<PHINode>(DU.NarrowUse)) {
1656  if (LI->getLoopFor(UsePhi->getParent()) != L) {
1657  // For LCSSA phis, sink the truncate outside the loop.
1658  // After SimplifyCFG most loop exit targets have a single predecessor.
1659  // Otherwise fall back to a truncate within the loop.
1660  if (UsePhi->getNumOperands() != 1)
1661  truncateIVUse(DU, DT, LI);
1662  else {
1663  // Widening the PHI requires us to insert a trunc. The logical place
1664  // for this trunc is in the same BB as the PHI. This is not possible if
1665  // the BB is terminated by a catchswitch.
1666  if (isa<CatchSwitchInst>(UsePhi->getParent()->getTerminator()))
1667  return nullptr;
1668 
1669  PHINode *WidePhi =
1670  PHINode::Create(DU.WideDef->getType(), 1, UsePhi->getName() + ".wide",
1671  UsePhi);
1672  WidePhi->addIncoming(DU.WideDef, UsePhi->getIncomingBlock(0));
1674  Value *Trunc = Builder.CreateTrunc(WidePhi, DU.NarrowDef->getType());
1675  UsePhi->replaceAllUsesWith(Trunc);
1676  DeadInsts.emplace_back(UsePhi);
1677  LLVM_DEBUG(dbgs() << "INDVARS: Widen lcssa phi " << *UsePhi << " to "
1678  << *WidePhi << "\n");
1679  }
1680  return nullptr;
1681  }
1682  }
1683 
1684  // This narrow use can be widened by a sext if it's non-negative or its narrow
1685  // def was widended by a sext. Same for zext.
1686  auto canWidenBySExt = [&]() {
1687  return DU.NeverNegative || getExtendKind(DU.NarrowDef) == SignExtended;
1688  };
1689  auto canWidenByZExt = [&]() {
1690  return DU.NeverNegative || getExtendKind(DU.NarrowDef) == ZeroExtended;
1691  };
1692 
1693  // Our raison d'etre! Eliminate sign and zero extension.
1694  if ((isa<SExtInst>(DU.NarrowUse) && canWidenBySExt()) ||
1695  (isa<ZExtInst>(DU.NarrowUse) && canWidenByZExt())) {
1696  Value *NewDef = DU.WideDef;
1697  if (DU.NarrowUse->getType() != WideType) {
1698  unsigned CastWidth = SE->getTypeSizeInBits(DU.NarrowUse->getType());
1699  unsigned IVWidth = SE->getTypeSizeInBits(WideType);
1700  if (CastWidth < IVWidth) {
1701  // The cast isn't as wide as the IV, so insert a Trunc.
1703  NewDef = Builder.CreateTrunc(DU.WideDef, DU.NarrowUse->getType());
1704  }
1705  else {
1706  // A wider extend was hidden behind a narrower one. This may induce
1707  // another round of IV widening in which the intermediate IV becomes
1708  // dead. It should be very rare.
1709  LLVM_DEBUG(dbgs() << "INDVARS: New IV " << *WidePhi
1710  << " not wide enough to subsume " << *DU.NarrowUse
1711  << "\n");
1713  NewDef = DU.NarrowUse;
1714  }
1715  }
1716  if (NewDef != DU.NarrowUse) {
1717  LLVM_DEBUG(dbgs() << "INDVARS: eliminating " << *DU.NarrowUse
1718  << " replaced by " << *DU.WideDef << "\n");
1719  ++NumElimExt;
1720  DU.NarrowUse->replaceAllUsesWith(NewDef);
1721  DeadInsts.emplace_back(DU.NarrowUse);
1722  }
1723  // Now that the extend is gone, we want to expose it's uses for potential
1724  // further simplification. We don't need to directly inform SimplifyIVUsers
1725  // of the new users, because their parent IV will be processed later as a
1726  // new loop phi. If we preserved IVUsers analysis, we would also want to
1727  // push the uses of WideDef here.
1728 
1729  // No further widening is needed. The deceased [sz]ext had done it for us.
1730  return nullptr;
1731  }
1732 
1733  // Does this user itself evaluate to a recurrence after widening?
1734  WidenedRecTy WideAddRec = getExtendedOperandRecurrence(DU);
1735  if (!WideAddRec.first)
1736  WideAddRec = getWideRecurrence(DU);
1737 
1738  assert((WideAddRec.first == nullptr) == (WideAddRec.second == Unknown));
1739  if (!WideAddRec.first) {
1740  // If use is a loop condition, try to promote the condition instead of
1741  // truncating the IV first.
1742  if (widenLoopCompare(DU))
1743  return nullptr;
1744 
1745  // We are here about to generate a truncate instruction that may hurt
1746  // performance because the scalar evolution expression computed earlier
1747  // in WideAddRec.first does not indicate a polynomial induction expression.
1748  // In that case, look at the operands of the use instruction to determine
1749  // if we can still widen the use instead of truncating its operand.
1750  if (widenWithVariantUse(DU))
1751  return nullptr;
1752 
1753  // This user does not evaluate to a recurrence after widening, so don't
1754  // follow it. Instead insert a Trunc to kill off the original use,
1755  // eventually isolating the original narrow IV so it can be removed.
1756  truncateIVUse(DU, DT, LI);
1757  return nullptr;
1758  }
1759  // Assume block terminators cannot evaluate to a recurrence. We can't to
1760  // insert a Trunc after a terminator if there happens to be a critical edge.
1762  "SCEV is not expected to evaluate a block terminator");
1763 
1764  // Reuse the IV increment that SCEVExpander created as long as it dominates
1765  // NarrowUse.
1766  Instruction *WideUse = nullptr;
1767  if (WideAddRec.first == WideIncExpr &&
1768  Rewriter.hoistIVInc(WideInc, DU.NarrowUse))
1769  WideUse = WideInc;
1770  else {
1771  WideUse = cloneIVUser(DU, WideAddRec.first);
1772  if (!WideUse)
1773  return nullptr;
1774  }
1775  // Evaluation of WideAddRec ensured that the narrow expression could be
1776  // extended outside the loop without overflow. This suggests that the wide use
1777  // evaluates to the same expression as the extended narrow use, but doesn't
1778  // absolutely guarantee it. Hence the following failsafe check. In rare cases
1779  // where it fails, we simply throw away the newly created wide use.
1780  if (WideAddRec.first != SE->getSCEV(WideUse)) {
1781  LLVM_DEBUG(dbgs() << "Wide use expression mismatch: " << *WideUse << ": "
1782  << *SE->getSCEV(WideUse) << " != " << *WideAddRec.first
1783  << "\n");
1784  DeadInsts.emplace_back(WideUse);
1785  return nullptr;
1786  }
1787 
1788  // if we reached this point then we are going to replace
1789  // DU.NarrowUse with WideUse. Reattach DbgValue then.
1790  replaceAllDbgUsesWith(*DU.NarrowUse, *WideUse, *WideUse, *DT);
1791 
1792  ExtendKindMap[DU.NarrowUse] = WideAddRec.second;
1793  // Returning WideUse pushes it on the worklist.
1794  return WideUse;
1795 }
1796 
1797 /// Add eligible users of NarrowDef to NarrowIVUsers.
1799  const SCEV *NarrowSCEV = SE->getSCEV(NarrowDef);
1800  bool NonNegativeDef =
1801  SE->isKnownPredicate(ICmpInst::ICMP_SGE, NarrowSCEV,
1802  SE->getZero(NarrowSCEV->getType()));
1803  for (User *U : NarrowDef->users()) {
1804  Instruction *NarrowUser = cast<Instruction>(U);
1805 
1806  // Handle data flow merges and bizarre phi cycles.
1807  if (!Widened.insert(NarrowUser).second)
1808  continue;
1809 
1810  bool NonNegativeUse = false;
1811  if (!NonNegativeDef) {
1812  // We might have a control-dependent range information for this context.
1813  if (auto RangeInfo = getPostIncRangeInfo(NarrowDef, NarrowUser))
1814  NonNegativeUse = RangeInfo->getSignedMin().isNonNegative();
1815  }
1816 
1817  NarrowIVUsers.emplace_back(NarrowDef, NarrowUser, WideDef,
1818  NonNegativeDef || NonNegativeUse);
1819  }
1820 }
1821 
1822 /// Process a single induction variable. First use the SCEVExpander to create a
1823 /// wide induction variable that evaluates to the same recurrence as the
1824 /// original narrow IV. Then use a worklist to forward traverse the narrow IV's
1825 /// def-use chain. After widenIVUse has processed all interesting IV users, the
1826 /// narrow IV will be isolated for removal by DeleteDeadPHIs.
1827 ///
1828 /// It would be simpler to delete uses as they are processed, but we must avoid
1829 /// invalidating SCEV expressions.
1831  // Is this phi an induction variable?
1832  const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(SE->getSCEV(OrigPhi));
1833  if (!AddRec)
1834  return nullptr;
1835 
1836  // Widen the induction variable expression.
1837  const SCEV *WideIVExpr = getExtendKind(OrigPhi) == SignExtended
1838  ? SE->getSignExtendExpr(AddRec, WideType)
1839  : SE->getZeroExtendExpr(AddRec, WideType);
1840 
1841  assert(SE->getEffectiveSCEVType(WideIVExpr->getType()) == WideType &&
1842  "Expect the new IV expression to preserve its type");
1843 
1844  // Can the IV be extended outside the loop without overflow?
1845  AddRec = dyn_cast<SCEVAddRecExpr>(WideIVExpr);
1846  if (!AddRec || AddRec->getLoop() != L)
1847  return nullptr;
1848 
1849  // An AddRec must have loop-invariant operands. Since this AddRec is
1850  // materialized by a loop header phi, the expression cannot have any post-loop
1851  // operands, so they must dominate the loop header.
1852  assert(
1853  SE->properlyDominates(AddRec->getStart(), L->getHeader()) &&
1854  SE->properlyDominates(AddRec->getStepRecurrence(*SE), L->getHeader()) &&
1855  "Loop header phi recurrence inputs do not dominate the loop");
1856 
1857  // Iterate over IV uses (including transitive ones) looking for IV increments
1858  // of the form 'add nsw %iv, <const>'. For each increment and each use of
1859  // the increment calculate control-dependent range information basing on
1860  // dominating conditions inside of the loop (e.g. a range check inside of the
1861  // loop). Calculated ranges are stored in PostIncRangeInfos map.
1862  //
1863  // Control-dependent range information is later used to prove that a narrow
1864  // definition is not negative (see pushNarrowIVUsers). It's difficult to do
1865  // this on demand because when pushNarrowIVUsers needs this information some
1866  // of the dominating conditions might be already widened.
1867  if (UsePostIncrementRanges)
1868  calculatePostIncRanges(OrigPhi);
1869 
1870  // The rewriter provides a value for the desired IV expression. This may
1871  // either find an existing phi or materialize a new one. Either way, we
1872  // expect a well-formed cyclic phi-with-increments. i.e. any operand not part
1873  // of the phi-SCC dominates the loop entry.
1874  Instruction *InsertPt = &*L->getHeader()->getFirstInsertionPt();
1875  Value *ExpandInst = Rewriter.expandCodeFor(AddRec, WideType, InsertPt);
1876  // If the wide phi is not a phi node, for example a cast node, like bitcast,
1877  // inttoptr, ptrtoint, just skip for now.
1878  if (!(WidePhi = dyn_cast<PHINode>(ExpandInst))) {
1879  // if the cast node is an inserted instruction without any user, we should
1880  // remove it to make sure the pass don't touch the function as we can not
1881  // wide the phi.
1882  if (ExpandInst->hasNUses(0) &&
1883  Rewriter.isInsertedInstruction(cast<Instruction>(ExpandInst)))
1884  DeadInsts.emplace_back(ExpandInst);
1885  return nullptr;
1886  }
1887 
1888  // Remembering the WideIV increment generated by SCEVExpander allows
1889  // widenIVUse to reuse it when widening the narrow IV's increment. We don't
1890  // employ a general reuse mechanism because the call above is the only call to
1891  // SCEVExpander. Henceforth, we produce 1-to-1 narrow to wide uses.
1892  if (BasicBlock *LatchBlock = L->getLoopLatch()) {
1893  WideInc =
1894  cast<Instruction>(WidePhi->getIncomingValueForBlock(LatchBlock));
1895  WideIncExpr = SE->getSCEV(WideInc);
1896  // Propagate the debug location associated with the original loop increment
1897  // to the new (widened) increment.
1898  auto *OrigInc =
1899  cast<Instruction>(OrigPhi->getIncomingValueForBlock(LatchBlock));
1900  WideInc->setDebugLoc(OrigInc->getDebugLoc());
1901  }
1902 
1903  LLVM_DEBUG(dbgs() << "Wide IV: " << *WidePhi << "\n");
1904  ++NumWidened;
1905 
1906  // Traverse the def-use chain using a worklist starting at the original IV.
1907  assert(Widened.empty() && NarrowIVUsers.empty() && "expect initial state" );
1908 
1909  Widened.insert(OrigPhi);
1910  pushNarrowIVUsers(OrigPhi, WidePhi);
1911 
1912  while (!NarrowIVUsers.empty()) {
1913  WidenIV::NarrowIVDefUse DU = NarrowIVUsers.pop_back_val();
1914 
1915  // Process a def-use edge. This may replace the use, so don't hold a
1916  // use_iterator across it.
1917  Instruction *WideUse = widenIVUse(DU, Rewriter);
1918 
1919  // Follow all def-use edges from the previous narrow use.
1920  if (WideUse)
1921  pushNarrowIVUsers(DU.NarrowUse, WideUse);
1922 
1923  // widenIVUse may have removed the def-use edge.
1924  if (DU.NarrowDef->use_empty())
1925  DeadInsts.emplace_back(DU.NarrowDef);
1926  }
1927 
1928  // Attach any debug information to the new PHI.
1929  replaceAllDbgUsesWith(*OrigPhi, *WidePhi, *WidePhi, *DT);
1930 
1931  return WidePhi;
1932 }
1933 
1934 /// Calculates control-dependent range for the given def at the given context
1935 /// by looking at dominating conditions inside of the loop
1936 void WidenIV::calculatePostIncRange(Instruction *NarrowDef,
1937  Instruction *NarrowUser) {
1938  using namespace llvm::PatternMatch;
1939 
1940  Value *NarrowDefLHS;
1941  const APInt *NarrowDefRHS;
1942  if (!match(NarrowDef, m_NSWAdd(m_Value(NarrowDefLHS),
1943  m_APInt(NarrowDefRHS))) ||
1944  !NarrowDefRHS->isNonNegative())
1945  return;
1946 
1947  auto UpdateRangeFromCondition = [&] (Value *Condition,
1948  bool TrueDest) {
1949  CmpInst::Predicate Pred;
1950  Value *CmpRHS;
1951  if (!match(Condition, m_ICmp(Pred, m_Specific(NarrowDefLHS),
1952  m_Value(CmpRHS))))
1953  return;
1954 
1956  TrueDest ? Pred : CmpInst::getInversePredicate(Pred);
1957 
1958  auto CmpRHSRange = SE->getSignedRange(SE->getSCEV(CmpRHS));
1959  auto CmpConstrainedLHSRange =
1960  ConstantRange::makeAllowedICmpRegion(P, CmpRHSRange);
1961  auto NarrowDefRange = CmpConstrainedLHSRange.addWithNoWrap(
1962  *NarrowDefRHS, OverflowingBinaryOperator::NoSignedWrap);
1963 
1964  updatePostIncRangeInfo(NarrowDef, NarrowUser, NarrowDefRange);
1965  };
1966 
1967  auto UpdateRangeFromGuards = [&](Instruction *Ctx) {
1968  if (!HasGuards)
1969  return;
1970 
1971  for (Instruction &I : make_range(Ctx->getIterator().getReverse(),
1972  Ctx->getParent()->rend())) {
1973  Value *C = nullptr;
1974  if (match(&I, m_Intrinsic<Intrinsic::experimental_guard>(m_Value(C))))
1975  UpdateRangeFromCondition(C, /*TrueDest=*/true);
1976  }
1977  };
1978 
1979  UpdateRangeFromGuards(NarrowUser);
1980 
1981  BasicBlock *NarrowUserBB = NarrowUser->getParent();
1982  // If NarrowUserBB is statically unreachable asking dominator queries may
1983  // yield surprising results. (e.g. the block may not have a dom tree node)
1984  if (!DT->isReachableFromEntry(NarrowUserBB))
1985  return;
1986 
1987  for (auto *DTB = (*DT)[NarrowUserBB]->getIDom();
1988  L->contains(DTB->getBlock());
1989  DTB = DTB->getIDom()) {
1990  auto *BB = DTB->getBlock();
1991  auto *TI = BB->getTerminator();
1992  UpdateRangeFromGuards(TI);
1993 
1994  auto *BI = dyn_cast<BranchInst>(TI);
1995  if (!BI || !BI->isConditional())
1996  continue;
1997 
1998  auto *TrueSuccessor = BI->getSuccessor(0);
1999  auto *FalseSuccessor = BI->getSuccessor(1);
2000 
2001  auto DominatesNarrowUser = [this, NarrowUser] (BasicBlockEdge BBE) {
2002  return BBE.isSingleEdge() &&
2003  DT->dominates(BBE, NarrowUser->getParent());
2004  };
2005 
2006  if (DominatesNarrowUser(BasicBlockEdge(BB, TrueSuccessor)))
2007  UpdateRangeFromCondition(BI->getCondition(), /*TrueDest=*/true);
2008 
2009  if (DominatesNarrowUser(BasicBlockEdge(BB, FalseSuccessor)))
2010  UpdateRangeFromCondition(BI->getCondition(), /*TrueDest=*/false);
2011  }
2012 }
2013 
2014 /// Calculates PostIncRangeInfos map for the given IV
2015 void WidenIV::calculatePostIncRanges(PHINode *OrigPhi) {
2018  Worklist.push_back(OrigPhi);
2019  Visited.insert(OrigPhi);
2020 
2021  while (!Worklist.empty()) {
2022  Instruction *NarrowDef = Worklist.pop_back_val();
2023 
2024  for (Use &U : NarrowDef->uses()) {
2025  auto *NarrowUser = cast<Instruction>(U.getUser());
2026 
2027  // Don't go looking outside the current loop.
2028  auto *NarrowUserLoop = (*LI)[NarrowUser->getParent()];
2029  if (!NarrowUserLoop || !L->contains(NarrowUserLoop))
2030  continue;
2031 
2032  if (!Visited.insert(NarrowUser).second)
2033  continue;
2034 
2035  Worklist.push_back(NarrowUser);
2036 
2037  calculatePostIncRange(NarrowDef, NarrowUser);
2038  }
2039  }
2040 }
2041 
2045  unsigned &NumElimExt, unsigned &NumWidened,
2046  bool HasGuards, bool UsePostIncrementRanges) {
2047  WidenIV Widener(WI, LI, SE, DT, DeadInsts, HasGuards, UsePostIncrementRanges);
2048  PHINode *WidePHI = Widener.createWideIV(Rewriter);
2049  NumElimExt = Widener.getNumElimExt();
2050  NumWidened = Widener.getNumWidened();
2051  return WidePHI;
2052 }
i
i
Definition: README.txt:29
llvm::BinaryOpIntrinsic::getBinaryOp
Instruction::BinaryOps getBinaryOp() const
Returns the binary operation underlying the intrinsic.
Definition: IntrinsicInst.cpp:558
llvm::ScalarEvolution::isKnownPredicateAt
bool isKnownPredicateAt(ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS, const Instruction *Context)
Test if the given expression is known to satisfy the condition described by Pred, LHS,...
Definition: ScalarEvolution.cpp:9930
llvm::Loop::isLoopInvariant
bool isLoopInvariant(const Value *V) const
Return true if the specified value is loop invariant.
Definition: LoopInfo.cpp:64
llvm::CmpInst::getSwappedPredicate
Predicate getSwappedPredicate() const
For example, EQ->EQ, SLE->SGE, ULT->UGT, OEQ->OEQ, ULE->UGE, OLT->OGT, etc.
Definition: InstrTypes.h:836
llvm::ScalarEvolution::getNegativeSCEV
const SCEV * getNegativeSCEV(const SCEV *V, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap)
Return the SCEV object corresponding to -V.
Definition: ScalarEvolution.cpp:4113
llvm
---------------------— PointerInfo ------------------------------------—
Definition: AllocatorList.h:23
llvm::DominatorTreeBase::findNearestCommonDominator
NodeT * findNearestCommonDominator(NodeT *A, NodeT *B) const
Find nearest common dominator basic block for basic block A and B.
Definition: GenericDomTree.h:468
llvm::createWideIV
PHINode * createWideIV(const WideIVInfo &WI, LoopInfo *LI, ScalarEvolution *SE, SCEVExpander &Rewriter, DominatorTree *DT, SmallVectorImpl< WeakTrackingVH > &DeadInsts, unsigned &NumElimExt, unsigned &NumWidened, bool HasGuards, bool UsePostIncrementRanges)
Widen Induction Variables - Extend the width of an IV to cover its widest uses.
Definition: SimplifyIndVar.cpp:2042
llvm::tgtok::Def
@ Def
Definition: TGLexer.h:50
llvm::CmpInst::ICMP_EQ
@ ICMP_EQ
equal
Definition: InstrTypes.h:741
llvm::IVVisitor::visitCast
virtual void visitCast(CastInst *Cast)=0
llvm::make_range
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
Definition: iterator_range.h:53
llvm::ScalarEvolution::getEffectiveSCEVType
Type * getEffectiveSCEVType(Type *Ty) const
Return a type with the same bitwidth as the given type and which represents how SCEV will treat the g...
Definition: ScalarEvolution.cpp:3949
llvm::CmpInst::Predicate
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Definition: InstrTypes.h:720
llvm::BasicBlock::iterator
InstListType::iterator iterator
Instruction iterators...
Definition: BasicBlock.h:90
WidenIV::getNumWidened
unsigned getNumWidened()
Definition: SimplifyIndVar.cpp:1043
findCommonDominator
static Instruction * findCommonDominator(ArrayRef< Instruction * > Instructions, DominatorTree &DT)
Find a point in code which dominates all given instructions.
Definition: SimplifyIndVar.cpp:105
WidenIV::getExtendKind
ExtendKind getExtendKind(Instruction *I)
Definition: SimplifyIndVar.cpp:1280
llvm::BasicBlock::getParent
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:107
IntrinsicInst.h
ScalarEvolutionExpander.h
llvm::SCEVAddRecExpr::getStart
const SCEV * getStart() const
Definition: ScalarEvolutionExpressions.h:363
WidenIV::NarrowIVDefUse::NarrowDef
Instruction * NarrowDef
Definition: SimplifyIndVar.cpp:1021
WidenIV::cloneBitwiseIVUser
Instruction * cloneBitwiseIVUser(NarrowIVDefUse DU)
Definition: SimplifyIndVar.cpp:1178
llvm::Loop
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:530
P
This currently compiles esp xmm0 movsd esp eax eax esp ret We should use not the dag combiner This is because dagcombine2 needs to be able to see through the X86ISD::Wrapper which DAGCombine can t really do The code for turning x load into a single vector load is target independent and should be moved to the dag combiner The code for turning x load into a vector load can only handle a direct load from a global or a direct load from the stack It should be generalized to handle any load from P
Definition: README-SSE.txt:411
llvm::LoopBase::contains
bool contains(const LoopT *L) const
Return true if the specified loop is contained within in this loop.
Definition: LoopInfo.h:122
llvm::PatternMatch::m_LShr
BinaryOp_match< LHS, RHS, Instruction::LShr > m_LShr(const LHS &L, const RHS &R)
Definition: PatternMatch.h:1147
llvm::SCEVExpander
This class uses information about analyze scalars to rewrite expressions in canonical form.
Definition: ScalarEvolutionExpander.h:63
llvm::BinaryOpIntrinsic::getRHS
Value * getRHS() const
Definition: IntrinsicInst.h:576
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1168
truncateIVUse
static void truncateIVUse(WidenIV::NarrowIVDefUse DU, DominatorTree *DT, LoopInfo *LI)
This IV user cannot be widened.
Definition: SimplifyIndVar.cpp:1398
Statistic.h
llvm::BinaryOpIntrinsic::getLHS
Value * getLHS() const
Definition: IntrinsicInst.h:575
llvm::TargetTransformInfo
This pass provides access to the codegen interfaces that are needed for IR-level transformations.
Definition: TargetTransformInfo.h:168
llvm::IRBuilder<>
llvm::SmallDenseMap
Definition: DenseMap.h:880
llvm::ScalarEvolution
The main scalar evolution driver.
Definition: ScalarEvolution.h:461
Local.h
llvm::DominatorTree
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:151
llvm::ScalarEvolution::getTypeSizeInBits
uint64_t getTypeSizeInBits(Type *Ty) const
Return the size in bits of the specified type, for which isSCEVable must return true.
Definition: ScalarEvolution.cpp:3939
llvm::ICmpInst::getSignedPredicate
Predicate getSignedPredicate() const
For example, EQ->EQ, SLE->SLE, UGT->SGT, etc.
Definition: Instructions.h:1270
WidenIV::NarrowIVDefUse::NeverNegative
bool NeverNegative
Definition: SimplifyIndVar.cpp:1028
llvm::Type
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:45
Instructions
Code Generation Notes for reduce the size of the ISel and reduce repetition in the implementation In a small number of this can cause even when no optimisation has taken place Instructions
Definition: MSA.txt:11
llvm::ScalarEvolution::maskFlags
static LLVM_NODISCARD SCEV::NoWrapFlags maskFlags(SCEV::NoWrapFlags Flags, int Mask)
Convenient NoWrapFlags manipulation that hides enum casts and is visible in the ScalarEvolution name ...
Definition: ScalarEvolution.h:481
llvm::BasicBlockEdge
Definition: Dominators.h:83
llvm::Instruction::setHasNoUnsignedWrap
void setHasNoUnsignedWrap(bool b=true)
Set or clear the nuw flag on this instruction, which must be an operator which supports this flag.
Definition: Instruction.cpp:124
llvm::Optional
Definition: APInt.h:33
llvm::DenseMapBase::count
size_type count(const_arg_type_t< KeyT > Val) const
Return 1 if the specified key is in the map, 0 otherwise.
Definition: DenseMap.h:145
T
#define T
Definition: Mips16ISelLowering.cpp:341
llvm::SmallPtrSet< Instruction *, 16 >
llvm::PatternMatch::m_AShr
BinaryOp_match< LHS, RHS, Instruction::AShr > m_AShr(const LHS &L, const RHS &R)
Definition: PatternMatch.h:1153
STLExtras.h
llvm::SmallVectorImpl::pop_back_val
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:635
llvm::OverflowingBinaryOperator::hasNoUnsignedWrap
bool hasNoUnsignedWrap() const
Test whether this operation is known to never undergo unsigned overflow, aka the nuw property.
Definition: Operator.h:91
llvm::Instruction::setIsExact
void setIsExact(bool b=true)
Set or clear the exact flag on this instruction, which must be an operator which supports this flag.
Definition: Instruction.cpp:132
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:101
WidenIV::pushNarrowIVUsers
void pushNarrowIVUsers(Instruction *NarrowDef, Instruction *WideDef)
Add eligible users of NarrowDef to NarrowIVUsers.
Definition: SimplifyIndVar.cpp:1798
llvm::WideIVInfo
Collect information about induction variables that are used by sign/zero extend operations.
Definition: SimplifyIndVar.h:65
llvm::RISCVFenceField::R
@ R
Definition: RISCVBaseInfo.h:193
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
WidenIV::widenWithVariantUse
bool widenWithVariantUse(NarrowIVDefUse DU)
Definition: SimplifyIndVar.cpp:1476
llvm::AArch64CC::LT
@ LT
Definition: AArch64BaseInfo.h:266
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
llvm::ScalarEvolution::getMulExpr
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.
Definition: ScalarEvolution.cpp:2986
llvm::DominatorTree::dominates
bool dominates(const BasicBlock *BB, const Use &U) const
Return true if the (end of the) basic block BB dominates the use U.
Definition: Dominators.cpp:115
llvm::ScalarEvolution::properlyDominates
bool properlyDominates(const SCEV *S, const BasicBlock *BB)
Return true if elements that makes up the given SCEV properly dominate the specified basic block.
Definition: ScalarEvolution.cpp:12710
llvm::PatternMatch::m_APInt
apint_match m_APInt(const APInt *&Res)
Match a ConstantInt or splatted ConstantVector, binding the specified pointer to the contained APInt.
Definition: PatternMatch.h:270
llvm::APInt::uge
bool uge(const APInt &RHS) const
Unsigned greater or equal comparison.
Definition: APInt.h:1145
llvm::ConstantInt
This is the shared class of boolean and integer constants.
Definition: Constants.h:79
llvm::LoopBase::getParentLoop
LoopT * getParentLoop() const
Return the parent loop if it exists or nullptr for top level loops.
Definition: LoopInfo.h:113
llvm::Instruction::getOpcode
unsigned getOpcode() const
Returns a member of one of the enums like Instruction::Add.
Definition: Instruction.h:160
llvm::APInt::isNonNegative
bool isNonNegative() const
Determine if this APInt Value is non-negative (>= 0)
Definition: APInt.h:319
llvm::SelectInst::Create
static SelectInst * Create(Value *C, Value *S1, Value *S2, const Twine &NameStr="", Instruction *InsertBefore=nullptr, Instruction *MDFrom=nullptr)
Definition: Instructions.h:1769
Rewriter
Virtual Register Rewriter
Definition: VirtRegMap.cpp:237
llvm::PatternMatch::match
bool match(Val *V, const Pattern &P)
Definition: PatternMatch.h:49
WidenIV::getExtendedOperandRecurrence
WidenedRecTy getExtendedOperandRecurrence(NarrowIVDefUse DU)
No-wrap operations can transfer sign extension of their result to their operands.
Definition: SimplifyIndVar.cpp:1308
llvm::PHINode::getIncomingValue
Value * getIncomingValue(unsigned i) const
Return incoming value number x.
Definition: Instructions.h:2721
llvm::Instruction::setHasNoSignedWrap
void setHasNoSignedWrap(bool b=true)
Set or clear the nsw flag on this instruction, which must be an operator which supports this flag.
Definition: Instruction.cpp:128
WidenIV::createExtendInst
Value * createExtendInst(Value *NarrowOper, Type *WideType, bool IsSigned, Instruction *Use)
Definition: SimplifyIndVar.cpp:1139
llvm::User
Definition: User.h:44
llvm::ConstantRange::getUnsignedMin
APInt getUnsignedMin() const
Return the smallest unsigned value contained in the ConstantRange.
Definition: ConstantRange.cpp:375
C
(vector float) vec_cmpeq(*A, *B) C
Definition: README_ALTIVEC.txt:86
llvm::BasicBlock::begin
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:296
llvm::JumpTable::Simplified
@ Simplified
Definition: TargetOptions.h:47
llvm::ScalarEvolution::getUDivExpr
const SCEV * getUDivExpr(const SCEV *LHS, const SCEV *RHS)
Get a canonical unsigned division expression, or something simpler if possible.
Definition: ScalarEvolution.cpp:3280
llvm::AMDGPU::PALMD::Key
Key
PAL metadata keys.
Definition: AMDGPUMetadata.h:481
IP
Definition: NVPTXLowerArgs.cpp:166
llvm::Value::uses
iterator_range< use_iterator > uses()
Definition: Value.h:377
llvm::BasicBlock::getFirstInsertionPt
const_iterator getFirstInsertionPt() const
Returns an iterator to the first instruction in this block that is suitable for inserting a non-PHI i...
Definition: BasicBlock.cpp:249
false
Definition: StackSlotColoring.cpp:142
llvm::PHINode::getIncomingValueForBlock
Value * getIncomingValueForBlock(const BasicBlock *BB) const
Definition: Instructions.h:2810
llvm::SaturatingInst
Represents a saturating add/sub intrinsic.
Definition: IntrinsicInst.h:610
llvm::BinaryOperator::getOpcode
BinaryOps getOpcode() const
Definition: InstrTypes.h:393
llvm::ScalarEvolution::isKnownPredicate
bool isKnownPredicate(ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS)
Test if the given expression is known to satisfy the condition described by Pred, LHS,...
Definition: ScalarEvolution.cpp:9905
llvm::Instruction
Definition: Instruction.h:45
WidenIV::WidenIV
WidenIV(const WideIVInfo &WI, LoopInfo *LInfo, ScalarEvolution *SEv, DominatorTree *DTree, SmallVectorImpl< WeakTrackingVH > &DI, bool HasGuards, bool UsePostIncrementRanges=true)
Definition: SimplifyIndVar.cpp:1128
llvm::WideIVInfo::IsSigned
bool IsSigned
Definition: SimplifyIndVar.h:72
llvm::STATISTIC
STATISTIC(NumFunctions, "Total number of functions")
llvm::UndefValue::get
static UndefValue * get(Type *T)
Static factory methods - Return an 'undef' object of the specified type.
Definition: Constants.cpp:1771
llvm::ConstantInt::get
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:900
DebugLocVerifyLevel::None
@ None
WidenIV::widenLoopCompare
bool widenLoopCompare(NarrowIVDefUse DU)
If the narrow use is a compare instruction, then widen the compare.
Definition: SimplifyIndVar.cpp:1413
PatternMatch.h
llvm::PHINode::getNumIncomingValues
unsigned getNumIncomingValues() const
Return the number of incoming edges.
Definition: Instructions.h:2717
llvm::Value::use_empty
bool use_empty() const
Definition: Value.h:345
X
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
LoopInfo.h
llvm::PatternMatch::m_NSWAdd
OverflowingBinaryOp_match< LHS, RHS, Instruction::Add, OverflowingBinaryOperator::NoSignedWrap > m_NSWAdd(const LHS &L, const RHS &R)
Definition: PatternMatch.h:1186
llvm::ScalarEvolution::getSCEV
const SCEV * getSCEV(Value *V)
Return a SCEV expression for the full generality of the specified expression.
Definition: ScalarEvolution.cpp:4066
llvm::simplifyUsersOfIV
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...
Definition: SimplifyIndVar.cpp:916
llvm::Type::isIntegerTy
bool isIntegerTy() const
True if this is an instance of IntegerType.
Definition: Type.h:201
llvm::APInt::getOneBitSet
static APInt getOneBitSet(unsigned numBits, unsigned BitNo)
Return an APInt with exactly one bit set in the result.
Definition: APInt.h:224
llvm::SCEV
This class represents an analyzed expression in the program.
Definition: ScalarEvolution.h:78
llvm::ICmpInst::getUnsignedPredicate
Predicate getUnsignedPredicate() const
For example, EQ->EQ, SLE->ULE, UGT->UGT, etc.
Definition: Instructions.h:1282
llvm::MipsISD::Ext
@ Ext
Definition: MipsISelLowering.h:156
pushIVUsers
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's worklist.
Definition: SimplifyIndVar.cpp:774
llvm::Instruction::eraseFromParent
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
Definition: Instruction.cpp:78
llvm::ICmpInst
This instruction compares its operands according to the predicate given to the constructor.
Definition: Instructions.h:1203
llvm::BinaryOpIntrinsic::isSigned
bool isSigned() const
Whether the intrinsic is signed or unsigned.
Definition: IntrinsicInst.cpp:578
D
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
llvm::TruncInst
This class represents a truncation of integer types.
Definition: Instructions.h:4747
llvm::PHINode::addIncoming
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
Definition: Instructions.h:2775
llvm::numbers::e
constexpr double e
Definition: MathExtras.h:57
llvm::DenseMap
Definition: DenseMap.h:714
llvm::SCEV::FlagNSW
@ FlagNSW
Definition: ScalarEvolution.h:137
llvm::LoopInfoBase::getLoopFor
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
Definition: LoopInfo.h:967
I
#define I(x, y, z)
Definition: MD5.cpp:59
llvm::SCEVCheapExpansionBudget
cl::opt< unsigned > SCEVCheapExpansionBudget
llvm::LoopBase::getLoopPreheader
BlockT * getLoopPreheader() const
If there is a preheader for this loop, return it.
Definition: LoopInfoImpl.h:167
llvm::IVVisitor
Interface for visiting interesting IV users that are recognized but not simplified by this utility.
Definition: SimplifyIndVar.h:35
llvm::ICmpInst::isEquality
static bool isEquality(Predicate P)
Return true if this predicate is either EQ or NE.
Definition: Instructions.h:1292
llvm::Instruction::setDebugLoc
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
Definition: Instruction.h:367
llvm::LoopBase::getLoopLatch
BlockT * getLoopLatch() const
If there is a single latch block for this loop, return it.
Definition: LoopInfoImpl.h:216
llvm::DenseMapBase::find
iterator find(const_arg_type_t< KeyT > Val)
Definition: DenseMap.h:150
IRBuilder.h
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
std::swap
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:840
WidenIV::WidenedRecTy
std::pair< const SCEVAddRecExpr *, ExtendKind > WidenedRecTy
Definition: SimplifyIndVar.cpp:1056
SI
StandardInstrumentations SI(Debug, VerifyEach)
llvm::User::replaceUsesOfWith
void replaceUsesOfWith(Value *From, Value *To)
Replace uses of one Value with another.
Definition: User.cpp:21
llvm::DominatorTree::isReachableFromEntry
bool isReachableFromEntry(const Use &U) const
Provide an overload for a Use.
Definition: Dominators.cpp:328
llvm::SelectInst
This class represents the LLVM 'select' instruction.
Definition: Instructions.h:1738
llvm::TTI
TargetTransformInfo TTI
Definition: TargetTransformInfo.h:163
WidenIV::getNumElimExt
unsigned getNumElimExt()
Definition: SimplifyIndVar.cpp:1042
llvm::replaceAllDbgUsesWith
bool replaceAllDbgUsesWith(Instruction &From, Value &To, Instruction &DomPoint, DominatorTree &DT)
Point debug users of From to To or salvage them.
Definition: Local.cpp:2022
llvm::ScalarEvolution::getDataLayout
const DataLayout & getDataLayout() const
Return the DataLayout associated with the module this SCEV instance is operating on.
Definition: ScalarEvolution.h:1127
Builder
assume Assume Builder
Definition: AssumeBundleBuilder.cpp:650
llvm::PatternMatch::m_Value
class_match< Value > m_Value()
Match an arbitrary value and ignore it.
Definition: PatternMatch.h:76
llvm::APInt
Class for arbitrary precision integers.
Definition: APInt.h:75
llvm::ZExtInst
This class represents zero extension of integer types.
Definition: Instructions.h:4786
llvm::User::setOperand
void setOperand(unsigned i, Value *Val)
Definition: User.h:174
llvm::CmpInst::ICMP_SLT
@ ICMP_SLT
signed less than
Definition: InstrTypes.h:749
llvm::ArrayRef
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: APInt.h:32
llvm::isInstructionTriviallyDead
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:398
llvm::LoopInfo
Definition: LoopInfo.h:1083
WidenIV::cloneIVUser
Instruction * cloneIVUser(NarrowIVDefUse DU, const SCEVAddRecExpr *WideAR)
Instantiate a wide operation to replace a narrow operation.
Definition: SimplifyIndVar.cpp:1156
llvm::BinaryOperator
Definition: InstrTypes.h:189
llvm::ScalarEvolution::getSignExtendExpr
const SCEV * getSignExtendExpr(const SCEV *Op, Type *Ty, unsigned Depth=0)
Definition: ScalarEvolution.cpp:1880
DataLayout.h
getInsertPointForUses
static Instruction * getInsertPointForUses(Instruction *User, Value *Def, DominatorTree *DT, LoopInfo *LI)
Determine the insertion point for this user.
Definition: SimplifyIndVar.cpp:1083
llvm::Loop::makeLoopInvariant
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:74
llvm::CmpInst::ICMP_ULT
@ ICMP_ULT
unsigned less than
Definition: InstrTypes.h:745
isSimpleIVUser
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.
Definition: SimplifyIndVar.cpp:808
llvm_unreachable
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
Definition: ErrorHandling.h:136
llvm::Value::getType
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:256
llvm::Value::replaceAllUsesWith
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition: Value.cpp:520
getParent
static const Function * getParent(const Value *V)
Definition: BasicAliasAnalysis.cpp:776
uint32_t
llvm::Value::getContext
LLVMContext & getContext() const
All values hold a context through their type.
Definition: Value.cpp:978
llvm::SCEV::FlagNUW
@ FlagNUW
Definition: ScalarEvolution.h:136
llvm::Instruction::isExact
bool isExact() const
Determine whether the exact flag is set.
Definition: Instruction.cpp:186
S
add sub stmia L5 ldr r0 bl L_printf $stub Instead of a and a wouldn t it be better to do three moves *Return an aggregate type is even return S
Definition: README.txt:210
llvm::OverflowingBinaryOperator
Utility class for integer operators which may exhibit overflow - Add, Sub, Mul, and Shl.
Definition: Operator.h:67
llvm::CastInst
This is the base class for all instructions that perform data casts.
Definition: InstrTypes.h:430
llvm::WithOverflowInst
Represents an op.with.overflow intrinsic.
Definition: IntrinsicInst.h:589
llvm::SExtInst
This class represents a sign extension of integer types.
Definition: Instructions.h:4825
llvm::Value::getName
StringRef getName() const
Return a constant reference to the value's name.
Definition: Value.cpp:297
llvm::DenseMapBase::insert
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Definition: DenseMap.h:207
llvm::BasicBlock::getTerminator
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
Definition: BasicBlock.cpp:148
llvm::ConstantInt::getFalse
static ConstantInt * getFalse(LLVMContext &Context)
Definition: Constants.cpp:855
GetLoopInvariantInsertPosition
static Instruction * GetLoopInvariantInsertPosition(Loop *L, Instruction *Hint)
Definition: SimplifyIndVar.cpp:636
llvm::SCEV::NoWrapFlags
NoWrapFlags
NoWrapFlags are bitfield indices into SubclassData.
Definition: ScalarEvolution.h:133
WidenIV::NarrowIVDefUse::NarrowUse
Instruction * NarrowUse
Definition: SimplifyIndVar.cpp:1022
WidenIV::cloneArithmeticIVUser
Instruction * cloneArithmeticIVUser(NarrowIVDefUse DU, const SCEVAddRecExpr *WideAR)
Definition: SimplifyIndVar.cpp:1208
llvm::SCEVAddRecExpr::getLoop
const Loop * getLoop() const
Definition: ScalarEvolutionExpressions.h:364
llvm::OverflowingBinaryOperator::hasNoSignedWrap
bool hasNoSignedWrap() const
Test whether this operation is known to never undergo signed overflow, aka the nsw property.
Definition: Operator.h:97
llvm::ScalarEvolution::getMinusSCEV
const SCEV * getMinusSCEV(const SCEV *LHS, const SCEV *RHS, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
Return LHS-RHS.
Definition: ScalarEvolution.cpp:4199
DEBUG_TYPE
#define DEBUG_TYPE
Definition: SimplifyIndVar.cpp:33
llvm::DenseMapBase::end
iterator end()
Definition: DenseMap.h:83
llvm::AMDGPU::SendMsg::Op
Op
Definition: SIDefines.h:321
llvm::simplifyLoopIVs
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.
Definition: SimplifyIndVar.cpp:928
llvm::ConstantInt::getBool
static ConstantInt * getBool(LLVMContext &Context, bool V)
Definition: Constants.cpp:862
llvm::CmpInst::isUnsigned
bool isUnsigned() const
Definition: InstrTypes.h:940
llvm::SCEVAddRecExpr
This node represents a polynomial recurrence on the trip count of the specified loop.
Definition: ScalarEvolutionExpressions.h:352
WidenIV::NarrowIVDefUse::WideDef
Instruction * WideDef
Definition: SimplifyIndVar.cpp:1023
llvm::Value::hasNUses
bool hasNUses(unsigned N) const
Return true if this Value has exactly N uses.
Definition: Value.cpp:149
llvm::BitWidth
constexpr unsigned BitWidth
Definition: BitmaskEnum.h:147
llvm::LoopBase::getHeader
BlockT * getHeader() const
Definition: LoopInfo.h:104
llvm::ScalarEvolution::isSCEVable
bool isSCEVable(Type *Ty) const
Test if values of the given type are analyzable within the SCEV framework.
Definition: ScalarEvolution.cpp:3932
llvm::CmpInst::isSigned
bool isSigned() const
Definition: InstrTypes.h:934
llvm::IVVisitor::anchor
virtual void anchor()
Definition: SimplifyIndVar.cpp:912
llvm::MCID::Add
@ Add
Definition: MCInstrDesc.h:183
llvm::CmpInst::setPredicate
void setPredicate(Predicate P)
Set the predicate for this instruction to the specified value.
Definition: InstrTypes.h:799
llvm::ConstantRange
This class represents a range of values.
Definition: ConstantRange.h:47
llvm::RegState::Dead
@ Dead
Unused definition.
Definition: MachineInstrBuilder.h:50
WidenIV
Definition: SimplifyIndVar.cpp:950
llvm::ScalarEvolution::getZeroExtendExpr
const SCEV * getZeroExtendExpr(const SCEV *Op, Type *Ty, unsigned Depth=0)
Definition: ScalarEvolution.cpp:1577
Instructions.h
llvm::isSafeToExpandAt
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...
Definition: ScalarEvolutionExpander.cpp:2653
llvm::User::getNumOperands
unsigned getNumOperands() const
Definition: User.h:191
SmallVector.h
llvm::PatternMatch::m_Specific
specificval_ty m_Specific(const Value *V)
Match if we have a specific specified value.
Definition: PatternMatch.h:802
WidenIV::widenIVUse
Instruction * widenIVUse(NarrowIVDefUse DU, SCEVExpander &Rewriter)
Determine whether an individual user of the narrow IV can be widened.
Definition: SimplifyIndVar.cpp:1650
llvm::PatternMatch::m_ICmp
CmpClass_match< LHS, RHS, ICmpInst, ICmpInst::Predicate > m_ICmp(ICmpInst::Predicate &Pred, const LHS &L, const RHS &R)
Definition: PatternMatch.h:1404
Dominators.h
llvm::SmallPtrSetImplBase::empty
LLVM_NODISCARD bool empty() const
Definition: SmallPtrSet.h:91
N
#define N
llvm::AssertingVH
Value handle that asserts if the Value is deleted.
Definition: ValueHandle.h:260
llvm::Instruction::getParent
const BasicBlock * getParent() const
Definition: Instruction.h:94
llvm::CmpInst::getPredicate
Predicate getPredicate() const
Return the predicate for this instruction.
Definition: InstrTypes.h:796
llvm::PHINode::getIncomingBlock
BasicBlock * getIncomingBlock(unsigned i) const
Return incoming basic block number i.
Definition: Instructions.h:2741
llvm::ScalarEvolution::getZero
const SCEV * getZero(Type *Ty)
Return a SCEV for the constant 0 of a specific type.
Definition: ScalarEvolution.h:626
Users
iv Induction Variable Users
Definition: IVUsers.cpp:52
llvm::PHINode
Definition: Instructions.h:2625
llvm::PatternMatch
Definition: PatternMatch.h:47
llvm::SmallVectorImpl< WeakTrackingVH >
WidenIV::getSCEVByOpCode
const SCEV * getSCEVByOpCode(const SCEV *LHS, const SCEV *RHS, unsigned OpCode) const
Definition: SimplifyIndVar.cpp:1286
llvm::SCEV::getType
Type * getType() const
Return the LLVM type of this SCEV expression.
Definition: ScalarEvolution.cpp:379
llvm::ScalarEvolution::getAddExpr
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.
Definition: ScalarEvolution.cpp:2419
BB
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
Definition: README.txt:39
WidenIV::createWideIV
PHINode * createWideIV(SCEVExpander &Rewriter)
Process a single induction variable.
Definition: SimplifyIndVar.cpp:1830
WidenIV::NarrowIVDefUse
Record a link in the Narrow IV def-use chain along with the WideIV that computes the same value as th...
Definition: SimplifyIndVar.cpp:1020
llvm::User::getOperand
Value * getOperand(unsigned i) const
Definition: User.h:169
raw_ostream.h
llvm::BinaryOperator::Create
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.
Definition: Instructions.cpp:2636
llvm::ScalarEvolution::isKnownNegative
bool isKnownNegative(const SCEV *S)
Test if the given expression is known to be negative.
Definition: ScalarEvolution.cpp:9822
llvm::Value
LLVM Value Representation.
Definition: Value.h:75
llvm::PatternMatch::m_Shl
BinaryOp_match< LHS, RHS, Instruction::Shl > m_Shl(const LHS &L, const RHS &R)
Definition: PatternMatch.h:1141
Debug.h
llvm::Value::users
iterator_range< user_iterator > users()
Definition: Value.h:422
llvm::Instruction::dropPoisonGeneratingFlags
void dropPoisonGeneratingFlags()
Drops flags that may cause this instruction to evaluate to poison despite having non-poison inputs.
Definition: Instruction.cpp:144
WidenIV::NarrowIVDefUse::NarrowIVDefUse
NarrowIVDefUse(Instruction *ND, Instruction *NU, Instruction *WD, bool NeverNegative)
Definition: SimplifyIndVar.cpp:1030
llvm::SCEVAddRecExpr::getStepRecurrence
const SCEV * getStepRecurrence(ScalarEvolution &SE) const
Constructs and returns the recurrence indicating how much this expression steps by.
Definition: ScalarEvolutionExpressions.h:370
SimplifyIndVar.h
WidenIV::getWideRecurrence
WidenedRecTy getWideRecurrence(NarrowIVDefUse DU)
Is this instruction potentially interesting for further simplification after widening it's type?...
Definition: SimplifyIndVar.cpp:1361
llvm::Use
A Use represents the edge between a Value definition and its users.
Definition: Use.h:44
UsePostIncrementRanges
static cl::opt< bool > UsePostIncrementRanges("indvars-post-increment-ranges", cl::Hidden, cl::desc("Use post increment control-dependent ranges in IndVarSimplify"), cl::init(true))
llvm::SmallVectorImpl::emplace_back
reference emplace_back(ArgTypes &&... Args)
Definition: SmallVector.h:908
llvm::SmallPtrSetImpl::insert
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