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