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