contrib/llvm-project/llvm/lib/Transforms/Utils/SimplifyIndVar.cpp

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