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