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