Home | History | Annotate | Download | only in Utils 
      1 //===-- SimplifyIndVar.cpp - Induction variable simplification ------------===//
      2 //
      3 //                     The LLVM Compiler Infrastructure
      4 //
      5 // This file is distributed under the University of Illinois Open Source
      6 // License. See LICENSE.TXT for details.
      7 //
      8 //===----------------------------------------------------------------------===//
      9 //
     10 // This file implements induction variable simplification. It does
     11 // not define any actual pass or policy, but provides a single function to
     12 // simplify a loop's induction variables based on ScalarEvolution.
     13 //
     14 //===----------------------------------------------------------------------===//
     15 
     16 #include "llvm/Transforms/Utils/SimplifyIndVar.h"
     17 #include "llvm/ADT/STLExtras.h"
     18 #include "llvm/ADT/SmallVector.h"
     19 #include "llvm/ADT/Statistic.h"
     20 #include "llvm/Analysis/LoopInfo.h"
     21 #include "llvm/Analysis/LoopPass.h"
     22 #include "llvm/Analysis/ScalarEvolutionExpressions.h"
     23 #include "llvm/IR/DataLayout.h"
     24 #include "llvm/IR/Dominators.h"
     25 #include "llvm/IR/IRBuilder.h"
     26 #include "llvm/IR/Instructions.h"
     27 #include "llvm/IR/IntrinsicInst.h"
     28 #include "llvm/Support/CommandLine.h"
     29 #include "llvm/Support/Debug.h"
     30 #include "llvm/Support/raw_ostream.h"
     31 
     32 using namespace llvm;
     33 
     34 #define DEBUG_TYPE "indvars"
     35 
     36 STATISTIC(NumElimIdentity, "Number of IV identities eliminated");
     37 STATISTIC(NumElimOperand,  "Number of IV operands folded into a use");
     38 STATISTIC(NumElimRem     , "Number of IV remainder operations eliminated");
     39 STATISTIC(NumElimCmp     , "Number of IV comparisons eliminated");
     40 
     41 namespace {
     42   /// This is a utility for simplifying induction variables
     43   /// based on ScalarEvolution. It is the primary instrument of the
     44   /// IndvarSimplify pass, but it may also be directly invoked to cleanup after
     45   /// other loop passes that preserve SCEV.
     46   class SimplifyIndvar {
     47     Loop             *L;
     48     LoopInfo         *LI;
     49     ScalarEvolution  *SE;
     50     DominatorTree    *DT;
     51 
     52     SmallVectorImpl<WeakVH> &DeadInsts;
     53 
     54     bool Changed;
     55 
     56   public:
     57     SimplifyIndvar(Loop *Loop, ScalarEvolution *SE, DominatorTree *DT,
     58                    LoopInfo *LI,SmallVectorImpl<WeakVH> &Dead)
     59         : L(Loop), LI(LI), SE(SE), DT(DT), DeadInsts(Dead), Changed(false) {
     60       assert(LI && "IV simplification requires LoopInfo");
     61     }
     62 
     63     bool hasChanged() const { return Changed; }
     64 
     65     /// Iteratively perform simplification on a worklist of users of the
     66     /// specified induction variable. This is the top-level driver that applies
     67     /// all simplifications to users of an IV.
     68     void simplifyUsers(PHINode *CurrIV, IVVisitor *V = nullptr);
     69 
     70     Value *foldIVUser(Instruction *UseInst, Instruction *IVOperand);
     71 
     72     bool eliminateIdentitySCEV(Instruction *UseInst, Instruction *IVOperand);
     73 
     74     bool eliminateIVUser(Instruction *UseInst, Instruction *IVOperand);
     75     void eliminateIVComparison(ICmpInst *ICmp, Value *IVOperand);
     76     void eliminateIVRemainder(BinaryOperator *Rem, Value *IVOperand,
     77                               bool IsSigned);
     78     bool strengthenOverflowingOperation(BinaryOperator *OBO, Value *IVOperand);
     79 
     80     Instruction *splitOverflowIntrinsic(Instruction *IVUser,
     81                                         const DominatorTree *DT);
     82   };
     83 }
     84 
     85 /// Fold an IV operand into its use.  This removes increments of an
     86 /// aligned IV when used by a instruction that ignores the low bits.
     87 ///
     88 /// IVOperand is guaranteed SCEVable, but UseInst may not be.
     89 ///
     90 /// Return the operand of IVOperand for this induction variable if IVOperand can
     91 /// be folded (in case more folding opportunities have been exposed).
     92 /// Otherwise return null.
     93 Value *SimplifyIndvar::foldIVUser(Instruction *UseInst, Instruction *IVOperand) {
     94   Value *IVSrc = nullptr;
     95   unsigned OperIdx = 0;
     96   const SCEV *FoldedExpr = nullptr;
     97   switch (UseInst->getOpcode()) {
     98   default:
     99     return nullptr;
    100   case Instruction::UDiv:
    101   case Instruction::LShr:
    102     // We're only interested in the case where we know something about
    103     // the numerator and have a constant denominator.
    104     if (IVOperand != UseInst->getOperand(OperIdx) ||
    105         !isa<ConstantInt>(UseInst->getOperand(1)))
    106       return nullptr;
    107 
    108     // Attempt to fold a binary operator with constant operand.
    109     // e.g. ((I + 1) >> 2) => I >> 2
    110     if (!isa<BinaryOperator>(IVOperand)
    111         || !isa<ConstantInt>(IVOperand->getOperand(1)))
    112       return nullptr;
    113 
    114     IVSrc = IVOperand->getOperand(0);
    115     // IVSrc must be the (SCEVable) IV, since the other operand is const.
    116     assert(SE->isSCEVable(IVSrc->getType()) && "Expect SCEVable IV operand");
    117 
    118     ConstantInt *D = cast<ConstantInt>(UseInst->getOperand(1));
    119     if (UseInst->getOpcode() == Instruction::LShr) {
    120       // Get a constant for the divisor. See createSCEV.
    121       uint32_t BitWidth = cast<IntegerType>(UseInst->getType())->getBitWidth();
    122       if (D->getValue().uge(BitWidth))
    123         return nullptr;
    124 
    125       D = ConstantInt::get(UseInst->getContext(),
    126                            APInt::getOneBitSet(BitWidth, D->getZExtValue()));
    127     }
    128     FoldedExpr = SE->getUDivExpr(SE->getSCEV(IVSrc), SE->getSCEV(D));
    129   }
    130   // We have something that might fold it's operand. Compare SCEVs.
    131   if (!SE->isSCEVable(UseInst->getType()))
    132     return nullptr;
    133 
    134   // Bypass the operand if SCEV can prove it has no effect.
    135   if (SE->getSCEV(UseInst) != FoldedExpr)
    136     return nullptr;
    137 
    138   DEBUG(dbgs() << "INDVARS: Eliminated IV operand: " << *IVOperand
    139         << " -> " << *UseInst << '\n');
    140 
    141   UseInst->setOperand(OperIdx, IVSrc);
    142   assert(SE->getSCEV(UseInst) == FoldedExpr && "bad SCEV with folded oper");
    143 
    144   ++NumElimOperand;
    145   Changed = true;
    146   if (IVOperand->use_empty())
    147     DeadInsts.emplace_back(IVOperand);
    148   return IVSrc;
    149 }
    150 
    151 /// SimplifyIVUsers helper for eliminating useless
    152 /// comparisons against an induction variable.
    153 void SimplifyIndvar::eliminateIVComparison(ICmpInst *ICmp, Value *IVOperand) {
    154   unsigned IVOperIdx = 0;
    155   ICmpInst::Predicate Pred = ICmp->getPredicate();
    156   if (IVOperand != ICmp->getOperand(0)) {
    157     // Swapped
    158     assert(IVOperand == ICmp->getOperand(1) && "Can't find IVOperand");
    159     IVOperIdx = 1;
    160     Pred = ICmpInst::getSwappedPredicate(Pred);
    161   }
    162 
    163   // Get the SCEVs for the ICmp operands.
    164   const SCEV *S = SE->getSCEV(ICmp->getOperand(IVOperIdx));
    165   const SCEV *X = SE->getSCEV(ICmp->getOperand(1 - IVOperIdx));
    166 
    167   // Simplify unnecessary loops away.
    168   const Loop *ICmpLoop = LI->getLoopFor(ICmp->getParent());
    169   S = SE->getSCEVAtScope(S, ICmpLoop);
    170   X = SE->getSCEVAtScope(X, ICmpLoop);
    171 
    172   ICmpInst::Predicate InvariantPredicate;
    173   const SCEV *InvariantLHS, *InvariantRHS;
    174 
    175   // If the condition is always true or always false, replace it with
    176   // a constant value.
    177   if (SE->isKnownPredicate(Pred, S, X)) {
    178     ICmp->replaceAllUsesWith(ConstantInt::getTrue(ICmp->getContext()));
    179     DeadInsts.emplace_back(ICmp);
    180     DEBUG(dbgs() << "INDVARS: Eliminated comparison: " << *ICmp << '\n');
    181   } else if (SE->isKnownPredicate(ICmpInst::getInversePredicate(Pred), S, X)) {
    182     ICmp->replaceAllUsesWith(ConstantInt::getFalse(ICmp->getContext()));
    183     DeadInsts.emplace_back(ICmp);
    184     DEBUG(dbgs() << "INDVARS: Eliminated comparison: " << *ICmp << '\n');
    185   } else if (isa<PHINode>(IVOperand) &&
    186              SE->isLoopInvariantPredicate(Pred, S, X, ICmpLoop,
    187                                           InvariantPredicate, InvariantLHS,
    188                                           InvariantRHS)) {
    189 
    190     // Rewrite the comparison to a loop invariant comparison if it can be done
    191     // cheaply, where cheaply means "we don't need to emit any new
    192     // instructions".
    193 
    194     Value *NewLHS = nullptr, *NewRHS = nullptr;
    195 
    196     if (S == InvariantLHS || X == InvariantLHS)
    197       NewLHS =
    198           ICmp->getOperand(S == InvariantLHS ? IVOperIdx : (1 - IVOperIdx));
    199 
    200     if (S == InvariantRHS || X == InvariantRHS)
    201       NewRHS =
    202           ICmp->getOperand(S == InvariantRHS ? IVOperIdx : (1 - IVOperIdx));
    203 
    204     for (Value *Incoming : cast<PHINode>(IVOperand)->incoming_values()) {
    205       if (NewLHS && NewRHS)
    206         break;
    207 
    208       const SCEV *IncomingS = SE->getSCEV(Incoming);
    209 
    210       if (!NewLHS && IncomingS == InvariantLHS)
    211         NewLHS = Incoming;
    212       if (!NewRHS && IncomingS == InvariantRHS)
    213         NewRHS = Incoming;
    214     }
    215 
    216     if (!NewLHS || !NewRHS)
    217       // We could not find an existing value to replace either LHS or RHS.
    218       // Generating new instructions has subtler tradeoffs, so avoid doing that
    219       // for now.
    220       return;
    221 
    222     DEBUG(dbgs() << "INDVARS: Simplified comparison: " << *ICmp << '\n');
    223     ICmp->setPredicate(InvariantPredicate);
    224     ICmp->setOperand(0, NewLHS);
    225     ICmp->setOperand(1, NewRHS);
    226   } else
    227     return;
    228 
    229   ++NumElimCmp;
    230   Changed = true;
    231 }
    232 
    233 /// SimplifyIVUsers helper for eliminating useless
    234 /// remainder operations operating on an induction variable.
    235 void SimplifyIndvar::eliminateIVRemainder(BinaryOperator *Rem,
    236                                       Value *IVOperand,
    237                                       bool IsSigned) {
    238   // We're only interested in the case where we know something about
    239   // the numerator.
    240   if (IVOperand != Rem->getOperand(0))
    241     return;
    242 
    243   // Get the SCEVs for the ICmp operands.
    244   const SCEV *S = SE->getSCEV(Rem->getOperand(0));
    245   const SCEV *X = SE->getSCEV(Rem->getOperand(1));
    246 
    247   // Simplify unnecessary loops away.
    248   const Loop *ICmpLoop = LI->getLoopFor(Rem->getParent());
    249   S = SE->getSCEVAtScope(S, ICmpLoop);
    250   X = SE->getSCEVAtScope(X, ICmpLoop);
    251 
    252   // i % n  -->  i  if i is in [0,n).
    253   if ((!IsSigned || SE->isKnownNonNegative(S)) &&
    254       SE->isKnownPredicate(IsSigned ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT,
    255                            S, X))
    256     Rem->replaceAllUsesWith(Rem->getOperand(0));
    257   else {
    258     // (i+1) % n  -->  (i+1)==n?0:(i+1)  if i is in [0,n).
    259     const SCEV *LessOne = SE->getMinusSCEV(S, SE->getOne(S->getType()));
    260     if (IsSigned && !SE->isKnownNonNegative(LessOne))
    261       return;
    262 
    263     if (!SE->isKnownPredicate(IsSigned ?
    264                               ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT,
    265                               LessOne, X))
    266       return;
    267 
    268     ICmpInst *ICmp = new ICmpInst(Rem, ICmpInst::ICMP_EQ,
    269                                   Rem->getOperand(0), Rem->getOperand(1));
    270     SelectInst *Sel =
    271       SelectInst::Create(ICmp,
    272                          ConstantInt::get(Rem->getType(), 0),
    273                          Rem->getOperand(0), "tmp", Rem);
    274     Rem->replaceAllUsesWith(Sel);
    275   }
    276 
    277   DEBUG(dbgs() << "INDVARS: Simplified rem: " << *Rem << '\n');
    278   ++NumElimRem;
    279   Changed = true;
    280   DeadInsts.emplace_back(Rem);
    281 }
    282 
    283 /// Eliminate an operation that consumes a simple IV and has no observable
    284 /// side-effect given the range of IV values.  IVOperand is guaranteed SCEVable,
    285 /// but UseInst may not be.
    286 bool SimplifyIndvar::eliminateIVUser(Instruction *UseInst,
    287                                      Instruction *IVOperand) {
    288   if (ICmpInst *ICmp = dyn_cast<ICmpInst>(UseInst)) {
    289     eliminateIVComparison(ICmp, IVOperand);
    290     return true;
    291   }
    292   if (BinaryOperator *Rem = dyn_cast<BinaryOperator>(UseInst)) {
    293     bool IsSigned = Rem->getOpcode() == Instruction::SRem;
    294     if (IsSigned || Rem->getOpcode() == Instruction::URem) {
    295       eliminateIVRemainder(Rem, IVOperand, IsSigned);
    296       return true;
    297     }
    298   }
    299 
    300   if (eliminateIdentitySCEV(UseInst, IVOperand))
    301     return true;
    302 
    303   return false;
    304 }
    305 
    306 /// Eliminate any operation that SCEV can prove is an identity function.
    307 bool SimplifyIndvar::eliminateIdentitySCEV(Instruction *UseInst,
    308                                            Instruction *IVOperand) {
    309   if (!SE->isSCEVable(UseInst->getType()) ||
    310       (UseInst->getType() != IVOperand->getType()) ||
    311       (SE->getSCEV(UseInst) != SE->getSCEV(IVOperand)))
    312     return false;
    313 
    314   // getSCEV(X) == getSCEV(Y) does not guarantee that X and Y are related in the
    315   // dominator tree, even if X is an operand to Y.  For instance, in
    316   //
    317   //     %iv = phi i32 {0,+,1}
    318   //     br %cond, label %left, label %merge
    319   //
    320   //   left:
    321   //     %X = add i32 %iv, 0
    322   //     br label %merge
    323   //
    324   //   merge:
    325   //     %M = phi (%X, %iv)
    326   //
    327   // getSCEV(%M) == getSCEV(%X) == {0,+,1}, but %X does not dominate %M, and
    328   // %M.replaceAllUsesWith(%X) would be incorrect.
    329 
    330   if (isa<PHINode>(UseInst))
    331     // If UseInst is not a PHI node then we know that IVOperand dominates
    332     // UseInst directly from the legality of SSA.
    333     if (!DT || !DT->dominates(IVOperand, UseInst))
    334       return false;
    335 
    336   if (!LI->replacementPreservesLCSSAForm(UseInst, IVOperand))
    337     return false;
    338 
    339   DEBUG(dbgs() << "INDVARS: Eliminated identity: " << *UseInst << '\n');
    340 
    341   UseInst->replaceAllUsesWith(IVOperand);
    342   ++NumElimIdentity;
    343   Changed = true;
    344   DeadInsts.emplace_back(UseInst);
    345   return true;
    346 }
    347 
    348 /// Annotate BO with nsw / nuw if it provably does not signed-overflow /
    349 /// unsigned-overflow.  Returns true if anything changed, false otherwise.
    350 bool SimplifyIndvar::strengthenOverflowingOperation(BinaryOperator *BO,
    351                                                     Value *IVOperand) {
    352 
    353   // Fastpath: we don't have any work to do if `BO` is `nuw` and `nsw`.
    354   if (BO->hasNoUnsignedWrap() && BO->hasNoSignedWrap())
    355     return false;
    356 
    357   const SCEV *(ScalarEvolution::*GetExprForBO)(const SCEV *, const SCEV *,
    358                                                SCEV::NoWrapFlags);
    359 
    360   switch (BO->getOpcode()) {
    361   default:
    362     return false;
    363 
    364   case Instruction::Add:
    365     GetExprForBO = &ScalarEvolution::getAddExpr;
    366     break;
    367 
    368   case Instruction::Sub:
    369     GetExprForBO = &ScalarEvolution::getMinusSCEV;
    370     break;
    371 
    372   case Instruction::Mul:
    373     GetExprForBO = &ScalarEvolution::getMulExpr;
    374     break;
    375   }
    376 
    377   unsigned BitWidth = cast<IntegerType>(BO->getType())->getBitWidth();
    378   Type *WideTy = IntegerType::get(BO->getContext(), BitWidth * 2);
    379   const SCEV *LHS = SE->getSCEV(BO->getOperand(0));
    380   const SCEV *RHS = SE->getSCEV(BO->getOperand(1));
    381 
    382   bool Changed = false;
    383 
    384   if (!BO->hasNoUnsignedWrap()) {
    385     const SCEV *ExtendAfterOp = SE->getZeroExtendExpr(SE->getSCEV(BO), WideTy);
    386     const SCEV *OpAfterExtend = (SE->*GetExprForBO)(
    387       SE->getZeroExtendExpr(LHS, WideTy), SE->getZeroExtendExpr(RHS, WideTy),
    388       SCEV::FlagAnyWrap);
    389     if (ExtendAfterOp == OpAfterExtend) {
    390       BO->setHasNoUnsignedWrap();
    391       SE->forgetValue(BO);
    392       Changed = true;
    393     }
    394   }
    395 
    396   if (!BO->hasNoSignedWrap()) {
    397     const SCEV *ExtendAfterOp = SE->getSignExtendExpr(SE->getSCEV(BO), WideTy);
    398     const SCEV *OpAfterExtend = (SE->*GetExprForBO)(
    399       SE->getSignExtendExpr(LHS, WideTy), SE->getSignExtendExpr(RHS, WideTy),
    400       SCEV::FlagAnyWrap);
    401     if (ExtendAfterOp == OpAfterExtend) {
    402       BO->setHasNoSignedWrap();
    403       SE->forgetValue(BO);
    404       Changed = true;
    405     }
    406   }
    407 
    408   return Changed;
    409 }
    410 
    411 /// \brief Split sadd.with.overflow into add + sadd.with.overflow to allow
    412 /// analysis and optimization.
    413 ///
    414 /// \return A new value representing the non-overflowing add if possible,
    415 /// otherwise return the original value.
    416 Instruction *SimplifyIndvar::splitOverflowIntrinsic(Instruction *IVUser,
    417                                                     const DominatorTree *DT) {
    418   IntrinsicInst *II = dyn_cast<IntrinsicInst>(IVUser);
    419   if (!II || II->getIntrinsicID() != Intrinsic::sadd_with_overflow)
    420     return IVUser;
    421 
    422   // Find a branch guarded by the overflow check.
    423   BranchInst *Branch = nullptr;
    424   Instruction *AddVal = nullptr;
    425   for (User *U : II->users()) {
    426     if (ExtractValueInst *ExtractInst = dyn_cast<ExtractValueInst>(U)) {
    427       if (ExtractInst->getNumIndices() != 1)
    428         continue;
    429       if (ExtractInst->getIndices()[0] == 0)
    430         AddVal = ExtractInst;
    431       else if (ExtractInst->getIndices()[0] == 1 && ExtractInst->hasOneUse())
    432         Branch = dyn_cast<BranchInst>(ExtractInst->user_back());
    433     }
    434   }
    435   if (!AddVal || !Branch)
    436     return IVUser;
    437 
    438   BasicBlock *ContinueBB = Branch->getSuccessor(1);
    439   if (std::next(pred_begin(ContinueBB)) != pred_end(ContinueBB))
    440     return IVUser;
    441 
    442   // Check if all users of the add are provably NSW.
    443   bool AllNSW = true;
    444   for (Use &U : AddVal->uses()) {
    445     if (Instruction *UseInst = dyn_cast<Instruction>(U.getUser())) {
    446       BasicBlock *UseBB = UseInst->getParent();
    447       if (PHINode *PHI = dyn_cast<PHINode>(UseInst))
    448         UseBB = PHI->getIncomingBlock(U);
    449       if (!DT->dominates(ContinueBB, UseBB)) {
    450         AllNSW = false;
    451         break;
    452       }
    453     }
    454   }
    455   if (!AllNSW)
    456     return IVUser;
    457 
    458   // Go for it...
    459   IRBuilder<> Builder(IVUser);
    460   Instruction *AddInst = dyn_cast<Instruction>(
    461     Builder.CreateNSWAdd(II->getOperand(0), II->getOperand(1)));
    462 
    463   // The caller expects the new add to have the same form as the intrinsic. The
    464   // IV operand position must be the same.
    465   assert((AddInst->getOpcode() == Instruction::Add &&
    466           AddInst->getOperand(0) == II->getOperand(0)) &&
    467          "Bad add instruction created from overflow intrinsic.");
    468 
    469   AddVal->replaceAllUsesWith(AddInst);
    470   DeadInsts.emplace_back(AddVal);
    471   return AddInst;
    472 }
    473 
    474 /// Add all uses of Def to the current IV's worklist.
    475 static void pushIVUsers(
    476   Instruction *Def,
    477   SmallPtrSet<Instruction*,16> &Simplified,
    478   SmallVectorImpl< std::pair<Instruction*,Instruction*> > &SimpleIVUsers) {
    479 
    480   for (User *U : Def->users()) {
    481     Instruction *UI = cast<Instruction>(U);
    482 
    483     // Avoid infinite or exponential worklist processing.
    484     // Also ensure unique worklist users.
    485     // If Def is a LoopPhi, it may not be in the Simplified set, so check for
    486     // self edges first.
    487     if (UI != Def && Simplified.insert(UI).second)
    488       SimpleIVUsers.push_back(std::make_pair(UI, Def));
    489   }
    490 }
    491 
    492 /// Return true if this instruction generates a simple SCEV
    493 /// expression in terms of that IV.
    494 ///
    495 /// This is similar to IVUsers' isInteresting() but processes each instruction
    496 /// non-recursively when the operand is already known to be a simpleIVUser.
    497 ///
    498 static bool isSimpleIVUser(Instruction *I, const Loop *L, ScalarEvolution *SE) {
    499   if (!SE->isSCEVable(I->getType()))
    500     return false;
    501 
    502   // Get the symbolic expression for this instruction.
    503   const SCEV *S = SE->getSCEV(I);
    504 
    505   // Only consider affine recurrences.
    506   const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(S);
    507   if (AR && AR->getLoop() == L)
    508     return true;
    509 
    510   return false;
    511 }
    512 
    513 /// Iteratively perform simplification on a worklist of users
    514 /// of the specified induction variable. Each successive simplification may push
    515 /// more users which may themselves be candidates for simplification.
    516 ///
    517 /// This algorithm does not require IVUsers analysis. Instead, it simplifies
    518 /// instructions in-place during analysis. Rather than rewriting induction
    519 /// variables bottom-up from their users, it transforms a chain of IVUsers
    520 /// top-down, updating the IR only when it encounters a clear optimization
    521 /// opportunity.
    522 ///
    523 /// Once DisableIVRewrite is default, LSR will be the only client of IVUsers.
    524 ///
    525 void SimplifyIndvar::simplifyUsers(PHINode *CurrIV, IVVisitor *V) {
    526   if (!SE->isSCEVable(CurrIV->getType()))
    527     return;
    528 
    529   // Instructions processed by SimplifyIndvar for CurrIV.
    530   SmallPtrSet<Instruction*,16> Simplified;
    531 
    532   // Use-def pairs if IV users waiting to be processed for CurrIV.
    533   SmallVector<std::pair<Instruction*, Instruction*>, 8> SimpleIVUsers;
    534 
    535   // Push users of the current LoopPhi. In rare cases, pushIVUsers may be
    536   // called multiple times for the same LoopPhi. This is the proper thing to
    537   // do for loop header phis that use each other.
    538   pushIVUsers(CurrIV, Simplified, SimpleIVUsers);
    539 
    540   while (!SimpleIVUsers.empty()) {
    541     std::pair<Instruction*, Instruction*> UseOper =
    542       SimpleIVUsers.pop_back_val();
    543     Instruction *UseInst = UseOper.first;
    544 
    545     // Bypass back edges to avoid extra work.
    546     if (UseInst == CurrIV) continue;
    547 
    548     if (V && V->shouldSplitOverflowInstrinsics()) {
    549       UseInst = splitOverflowIntrinsic(UseInst, V->getDomTree());
    550       if (!UseInst)
    551         continue;
    552     }
    553 
    554     Instruction *IVOperand = UseOper.second;
    555     for (unsigned N = 0; IVOperand; ++N) {
    556       assert(N <= Simplified.size() && "runaway iteration");
    557 
    558       Value *NewOper = foldIVUser(UseOper.first, IVOperand);
    559       if (!NewOper)
    560         break; // done folding
    561       IVOperand = dyn_cast<Instruction>(NewOper);
    562     }
    563     if (!IVOperand)
    564       continue;
    565 
    566     if (eliminateIVUser(UseOper.first, IVOperand)) {
    567       pushIVUsers(IVOperand, Simplified, SimpleIVUsers);
    568       continue;
    569     }
    570 
    571     if (BinaryOperator *BO = dyn_cast<BinaryOperator>(UseOper.first)) {
    572       if (isa<OverflowingBinaryOperator>(BO) &&
    573           strengthenOverflowingOperation(BO, IVOperand)) {
    574         // re-queue uses of the now modified binary operator and fall
    575         // through to the checks that remain.
    576         pushIVUsers(IVOperand, Simplified, SimpleIVUsers);
    577       }
    578     }
    579 
    580     CastInst *Cast = dyn_cast<CastInst>(UseOper.first);
    581     if (V && Cast) {
    582       V->visitCast(Cast);
    583       continue;
    584     }
    585     if (isSimpleIVUser(UseOper.first, L, SE)) {
    586       pushIVUsers(UseOper.first, Simplified, SimpleIVUsers);
    587     }
    588   }
    589 }
    590 
    591 namespace llvm {
    592 
    593 void IVVisitor::anchor() { }
    594 
    595 /// Simplify instructions that use this induction variable
    596 /// by using ScalarEvolution to analyze the IV's recurrence.
    597 bool simplifyUsersOfIV(PHINode *CurrIV, ScalarEvolution *SE, DominatorTree *DT,
    598                        LoopInfo *LI, SmallVectorImpl<WeakVH> &Dead,
    599                        IVVisitor *V) {
    600   SimplifyIndvar SIV(LI->getLoopFor(CurrIV->getParent()), SE, DT, LI, Dead);
    601   SIV.simplifyUsers(CurrIV, V);
    602   return SIV.hasChanged();
    603 }
    604 
    605 /// Simplify users of induction variables within this
    606 /// loop. This does not actually change or add IVs.
    607 bool simplifyLoopIVs(Loop *L, ScalarEvolution *SE, DominatorTree *DT,
    608                      LoopInfo *LI, SmallVectorImpl<WeakVH> &Dead) {
    609   bool Changed = false;
    610   for (BasicBlock::iterator I = L->getHeader()->begin(); isa<PHINode>(I); ++I) {
    611     Changed |= simplifyUsersOfIV(cast<PHINode>(I), SE, DT, LI, Dead);
    612   }
    613   return Changed;
    614 }
    615 
    616 } // namespace llvm
    617