LLVM  mainline
SimplifyIndVar.cpp
Go to the documentation of this file.
00001 //===-- SimplifyIndVar.cpp - Induction variable simplification ------------===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file is distributed under the University of Illinois Open Source
00006 // License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // This file implements induction variable simplification. It does
00011 // not define any actual pass or policy, but provides a single function to
00012 // simplify a loop's induction variables based on ScalarEvolution.
00013 //
00014 //===----------------------------------------------------------------------===//
00015 
00016 #include "llvm/Transforms/Utils/SimplifyIndVar.h"
00017 #include "llvm/ADT/STLExtras.h"
00018 #include "llvm/ADT/SmallVector.h"
00019 #include "llvm/ADT/Statistic.h"
00020 #include "llvm/Analysis/LoopInfo.h"
00021 #include "llvm/Analysis/LoopPass.h"
00022 #include "llvm/Analysis/ScalarEvolutionExpressions.h"
00023 #include "llvm/IR/DataLayout.h"
00024 #include "llvm/IR/Dominators.h"
00025 #include "llvm/IR/IRBuilder.h"
00026 #include "llvm/IR/Instructions.h"
00027 #include "llvm/IR/IntrinsicInst.h"
00028 #include "llvm/Support/CommandLine.h"
00029 #include "llvm/Support/Debug.h"
00030 #include "llvm/Support/raw_ostream.h"
00031 
00032 using namespace llvm;
00033 
00034 #define DEBUG_TYPE "indvars"
00035 
00036 STATISTIC(NumElimIdentity, "Number of IV identities eliminated");
00037 STATISTIC(NumElimOperand,  "Number of IV operands folded into a use");
00038 STATISTIC(NumElimRem     , "Number of IV remainder operations eliminated");
00039 STATISTIC(NumElimCmp     , "Number of IV comparisons eliminated");
00040 
00041 namespace {
00042   /// This is a utility for simplifying induction variables
00043   /// based on ScalarEvolution. It is the primary instrument of the
00044   /// IndvarSimplify pass, but it may also be directly invoked to cleanup after
00045   /// other loop passes that preserve SCEV.
00046   class SimplifyIndvar {
00047     Loop             *L;
00048     LoopInfo         *LI;
00049     ScalarEvolution  *SE;
00050     DominatorTree    *DT;
00051 
00052     SmallVectorImpl<WeakVH> &DeadInsts;
00053 
00054     bool Changed;
00055 
00056   public:
00057     SimplifyIndvar(Loop *Loop, ScalarEvolution *SE, DominatorTree *DT,
00058                    LoopInfo *LI,SmallVectorImpl<WeakVH> &Dead)
00059         : L(Loop), LI(LI), SE(SE), DT(DT), DeadInsts(Dead), Changed(false) {
00060       assert(LI && "IV simplification requires LoopInfo");
00061     }
00062 
00063     bool hasChanged() const { return Changed; }
00064 
00065     /// Iteratively perform simplification on a worklist of users of the
00066     /// specified induction variable. This is the top-level driver that applies
00067     /// all simplifications to users of an IV.
00068     void simplifyUsers(PHINode *CurrIV, IVVisitor *V = nullptr);
00069 
00070     Value *foldIVUser(Instruction *UseInst, Instruction *IVOperand);
00071 
00072     bool eliminateIdentitySCEV(Instruction *UseInst, Instruction *IVOperand);
00073 
00074     bool eliminateIVUser(Instruction *UseInst, Instruction *IVOperand);
00075     void eliminateIVComparison(ICmpInst *ICmp, Value *IVOperand);
00076     void eliminateIVRemainder(BinaryOperator *Rem, Value *IVOperand,
00077                               bool IsSigned);
00078     bool strengthenOverflowingOperation(BinaryOperator *OBO, Value *IVOperand);
00079 
00080     Instruction *splitOverflowIntrinsic(Instruction *IVUser,
00081                                         const DominatorTree *DT);
00082   };
00083 }
00084 
00085 /// Fold an IV operand into its use.  This removes increments of an
00086 /// aligned IV when used by a instruction that ignores the low bits.
00087 ///
00088 /// IVOperand is guaranteed SCEVable, but UseInst may not be.
00089 ///
00090 /// Return the operand of IVOperand for this induction variable if IVOperand can
00091 /// be folded (in case more folding opportunities have been exposed).
00092 /// Otherwise return null.
00093 Value *SimplifyIndvar::foldIVUser(Instruction *UseInst, Instruction *IVOperand) {
00094   Value *IVSrc = nullptr;
00095   unsigned OperIdx = 0;
00096   const SCEV *FoldedExpr = nullptr;
00097   switch (UseInst->getOpcode()) {
00098   default:
00099     return nullptr;
00100   case Instruction::UDiv:
00101   case Instruction::LShr:
00102     // We're only interested in the case where we know something about
00103     // the numerator and have a constant denominator.
00104     if (IVOperand != UseInst->getOperand(OperIdx) ||
00105         !isa<ConstantInt>(UseInst->getOperand(1)))
00106       return nullptr;
00107 
00108     // Attempt to fold a binary operator with constant operand.
00109     // e.g. ((I + 1) >> 2) => I >> 2
00110     if (!isa<BinaryOperator>(IVOperand)
00111         || !isa<ConstantInt>(IVOperand->getOperand(1)))
00112       return nullptr;
00113 
00114     IVSrc = IVOperand->getOperand(0);
00115     // IVSrc must be the (SCEVable) IV, since the other operand is const.
00116     assert(SE->isSCEVable(IVSrc->getType()) && "Expect SCEVable IV operand");
00117 
00118     ConstantInt *D = cast<ConstantInt>(UseInst->getOperand(1));
00119     if (UseInst->getOpcode() == Instruction::LShr) {
00120       // Get a constant for the divisor. See createSCEV.
00121       uint32_t BitWidth = cast<IntegerType>(UseInst->getType())->getBitWidth();
00122       if (D->getValue().uge(BitWidth))
00123         return nullptr;
00124 
00125       D = ConstantInt::get(UseInst->getContext(),
00126                            APInt::getOneBitSet(BitWidth, D->getZExtValue()));
00127     }
00128     FoldedExpr = SE->getUDivExpr(SE->getSCEV(IVSrc), SE->getSCEV(D));
00129   }
00130   // We have something that might fold it's operand. Compare SCEVs.
00131   if (!SE->isSCEVable(UseInst->getType()))
00132     return nullptr;
00133 
00134   // Bypass the operand if SCEV can prove it has no effect.
00135   if (SE->getSCEV(UseInst) != FoldedExpr)
00136     return nullptr;
00137 
00138   DEBUG(dbgs() << "INDVARS: Eliminated IV operand: " << *IVOperand
00139         << " -> " << *UseInst << '\n');
00140 
00141   UseInst->setOperand(OperIdx, IVSrc);
00142   assert(SE->getSCEV(UseInst) == FoldedExpr && "bad SCEV with folded oper");
00143 
00144   ++NumElimOperand;
00145   Changed = true;
00146   if (IVOperand->use_empty())
00147     DeadInsts.emplace_back(IVOperand);
00148   return IVSrc;
00149 }
00150 
00151 /// SimplifyIVUsers helper for eliminating useless
00152 /// comparisons against an induction variable.
00153 void SimplifyIndvar::eliminateIVComparison(ICmpInst *ICmp, Value *IVOperand) {
00154   unsigned IVOperIdx = 0;
00155   ICmpInst::Predicate Pred = ICmp->getPredicate();
00156   if (IVOperand != ICmp->getOperand(0)) {
00157     // Swapped
00158     assert(IVOperand == ICmp->getOperand(1) && "Can't find IVOperand");
00159     IVOperIdx = 1;
00160     Pred = ICmpInst::getSwappedPredicate(Pred);
00161   }
00162 
00163   // Get the SCEVs for the ICmp operands.
00164   const SCEV *S = SE->getSCEV(ICmp->getOperand(IVOperIdx));
00165   const SCEV *X = SE->getSCEV(ICmp->getOperand(1 - IVOperIdx));
00166 
00167   // Simplify unnecessary loops away.
00168   const Loop *ICmpLoop = LI->getLoopFor(ICmp->getParent());
00169   S = SE->getSCEVAtScope(S, ICmpLoop);
00170   X = SE->getSCEVAtScope(X, ICmpLoop);
00171 
00172   ICmpInst::Predicate InvariantPredicate;
00173   const SCEV *InvariantLHS, *InvariantRHS;
00174 
00175   // If the condition is always true or always false, replace it with
00176   // a constant value.
00177   if (SE->isKnownPredicate(Pred, S, X)) {
00178     ICmp->replaceAllUsesWith(ConstantInt::getTrue(ICmp->getContext()));
00179     DeadInsts.emplace_back(ICmp);
00180     DEBUG(dbgs() << "INDVARS: Eliminated comparison: " << *ICmp << '\n');
00181   } else if (SE->isKnownPredicate(ICmpInst::getInversePredicate(Pred), S, X)) {
00182     ICmp->replaceAllUsesWith(ConstantInt::getFalse(ICmp->getContext()));
00183     DeadInsts.emplace_back(ICmp);
00184     DEBUG(dbgs() << "INDVARS: Eliminated comparison: " << *ICmp << '\n');
00185   } else if (isa<PHINode>(IVOperand) &&
00186              SE->isLoopInvariantPredicate(Pred, S, X, ICmpLoop,
00187                                           InvariantPredicate, InvariantLHS,
00188                                           InvariantRHS)) {
00189 
00190     // Rewrite the comparison to a loop invariant comparison if it can be done
00191     // cheaply, where cheaply means "we don't need to emit any new
00192     // instructions".
00193 
00194     Value *NewLHS = nullptr, *NewRHS = nullptr;
00195 
00196     if (S == InvariantLHS || X == InvariantLHS)
00197       NewLHS =
00198           ICmp->getOperand(S == InvariantLHS ? IVOperIdx : (1 - IVOperIdx));
00199 
00200     if (S == InvariantRHS || X == InvariantRHS)
00201       NewRHS =
00202           ICmp->getOperand(S == InvariantRHS ? IVOperIdx : (1 - IVOperIdx));
00203 
00204     for (Value *Incoming : cast<PHINode>(IVOperand)->incoming_values()) {
00205       if (NewLHS && NewRHS)
00206         break;
00207 
00208       const SCEV *IncomingS = SE->getSCEV(Incoming);
00209 
00210       if (!NewLHS && IncomingS == InvariantLHS)
00211         NewLHS = Incoming;
00212       if (!NewRHS && IncomingS == InvariantRHS)
00213         NewRHS = Incoming;
00214     }
00215 
00216     if (!NewLHS || !NewRHS)
00217       // We could not find an existing value to replace either LHS or RHS.
00218       // Generating new instructions has subtler tradeoffs, so avoid doing that
00219       // for now.
00220       return;
00221 
00222     DEBUG(dbgs() << "INDVARS: Simplified comparison: " << *ICmp << '\n');
00223     ICmp->setPredicate(InvariantPredicate);
00224     ICmp->setOperand(0, NewLHS);
00225     ICmp->setOperand(1, NewRHS);
00226   } else
00227     return;
00228 
00229   ++NumElimCmp;
00230   Changed = true;
00231 }
00232 
00233 /// SimplifyIVUsers helper for eliminating useless
00234 /// remainder operations operating on an induction variable.
00235 void SimplifyIndvar::eliminateIVRemainder(BinaryOperator *Rem,
00236                                       Value *IVOperand,
00237                                       bool IsSigned) {
00238   // We're only interested in the case where we know something about
00239   // the numerator.
00240   if (IVOperand != Rem->getOperand(0))
00241     return;
00242 
00243   // Get the SCEVs for the ICmp operands.
00244   const SCEV *S = SE->getSCEV(Rem->getOperand(0));
00245   const SCEV *X = SE->getSCEV(Rem->getOperand(1));
00246 
00247   // Simplify unnecessary loops away.
00248   const Loop *ICmpLoop = LI->getLoopFor(Rem->getParent());
00249   S = SE->getSCEVAtScope(S, ICmpLoop);
00250   X = SE->getSCEVAtScope(X, ICmpLoop);
00251 
00252   // i % n  -->  i  if i is in [0,n).
00253   if ((!IsSigned || SE->isKnownNonNegative(S)) &&
00254       SE->isKnownPredicate(IsSigned ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT,
00255                            S, X))
00256     Rem->replaceAllUsesWith(Rem->getOperand(0));
00257   else {
00258     // (i+1) % n  -->  (i+1)==n?0:(i+1)  if i is in [0,n).
00259     const SCEV *LessOne = SE->getMinusSCEV(S, SE->getOne(S->getType()));
00260     if (IsSigned && !SE->isKnownNonNegative(LessOne))
00261       return;
00262 
00263     if (!SE->isKnownPredicate(IsSigned ?
00264                               ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT,
00265                               LessOne, X))
00266       return;
00267 
00268     ICmpInst *ICmp = new ICmpInst(Rem, ICmpInst::ICMP_EQ,
00269                                   Rem->getOperand(0), Rem->getOperand(1));
00270     SelectInst *Sel =
00271       SelectInst::Create(ICmp,
00272                          ConstantInt::get(Rem->getType(), 0),
00273                          Rem->getOperand(0), "tmp", Rem);
00274     Rem->replaceAllUsesWith(Sel);
00275   }
00276 
00277   DEBUG(dbgs() << "INDVARS: Simplified rem: " << *Rem << '\n');
00278   ++NumElimRem;
00279   Changed = true;
00280   DeadInsts.emplace_back(Rem);
00281 }
00282 
00283 /// Eliminate an operation that consumes a simple IV and has no observable
00284 /// side-effect given the range of IV values.  IVOperand is guaranteed SCEVable,
00285 /// but UseInst may not be.
00286 bool SimplifyIndvar::eliminateIVUser(Instruction *UseInst,
00287                                      Instruction *IVOperand) {
00288   if (ICmpInst *ICmp = dyn_cast<ICmpInst>(UseInst)) {
00289     eliminateIVComparison(ICmp, IVOperand);
00290     return true;
00291   }
00292   if (BinaryOperator *Rem = dyn_cast<BinaryOperator>(UseInst)) {
00293     bool IsSigned = Rem->getOpcode() == Instruction::SRem;
00294     if (IsSigned || Rem->getOpcode() == Instruction::URem) {
00295       eliminateIVRemainder(Rem, IVOperand, IsSigned);
00296       return true;
00297     }
00298   }
00299 
00300   if (eliminateIdentitySCEV(UseInst, IVOperand))
00301     return true;
00302 
00303   return false;
00304 }
00305 
00306 /// Eliminate any operation that SCEV can prove is an identity function.
00307 bool SimplifyIndvar::eliminateIdentitySCEV(Instruction *UseInst,
00308                                            Instruction *IVOperand) {
00309   if (!SE->isSCEVable(UseInst->getType()) ||
00310       (UseInst->getType() != IVOperand->getType()) ||
00311       (SE->getSCEV(UseInst) != SE->getSCEV(IVOperand)))
00312     return false;
00313 
00314   // getSCEV(X) == getSCEV(Y) does not guarantee that X and Y are related in the
00315   // dominator tree, even if X is an operand to Y.  For instance, in
00316   //
00317   //     %iv = phi i32 {0,+,1}
00318   //     br %cond, label %left, label %merge
00319   //
00320   //   left:
00321   //     %X = add i32 %iv, 0
00322   //     br label %merge
00323   //
00324   //   merge:
00325   //     %M = phi (%X, %iv)
00326   //
00327   // getSCEV(%M) == getSCEV(%X) == {0,+,1}, but %X does not dominate %M, and
00328   // %M.replaceAllUsesWith(%X) would be incorrect.
00329 
00330   if (isa<PHINode>(UseInst))
00331     // If UseInst is not a PHI node then we know that IVOperand dominates
00332     // UseInst directly from the legality of SSA.
00333     if (!DT || !DT->dominates(IVOperand, UseInst))
00334       return false;
00335 
00336   if (!LI->replacementPreservesLCSSAForm(UseInst, IVOperand))
00337     return false;
00338 
00339   DEBUG(dbgs() << "INDVARS: Eliminated identity: " << *UseInst << '\n');
00340 
00341   UseInst->replaceAllUsesWith(IVOperand);
00342   ++NumElimIdentity;
00343   Changed = true;
00344   DeadInsts.emplace_back(UseInst);
00345   return true;
00346 }
00347 
00348 /// Annotate BO with nsw / nuw if it provably does not signed-overflow /
00349 /// unsigned-overflow.  Returns true if anything changed, false otherwise.
00350 bool SimplifyIndvar::strengthenOverflowingOperation(BinaryOperator *BO,
00351                                                     Value *IVOperand) {
00352 
00353   // Fastpath: we don't have any work to do if `BO` is `nuw` and `nsw`.
00354   if (BO->hasNoUnsignedWrap() && BO->hasNoSignedWrap())
00355     return false;
00356 
00357   const SCEV *(ScalarEvolution::*GetExprForBO)(const SCEV *, const SCEV *,
00358                                                SCEV::NoWrapFlags);
00359 
00360   switch (BO->getOpcode()) {
00361   default:
00362     return false;
00363 
00364   case Instruction::Add:
00365     GetExprForBO = &ScalarEvolution::getAddExpr;
00366     break;
00367 
00368   case Instruction::Sub:
00369     GetExprForBO = &ScalarEvolution::getMinusSCEV;
00370     break;
00371 
00372   case Instruction::Mul:
00373     GetExprForBO = &ScalarEvolution::getMulExpr;
00374     break;
00375   }
00376 
00377   unsigned BitWidth = cast<IntegerType>(BO->getType())->getBitWidth();
00378   Type *WideTy = IntegerType::get(BO->getContext(), BitWidth * 2);
00379   const SCEV *LHS = SE->getSCEV(BO->getOperand(0));
00380   const SCEV *RHS = SE->getSCEV(BO->getOperand(1));
00381 
00382   bool Changed = false;
00383 
00384   if (!BO->hasNoUnsignedWrap()) {
00385     const SCEV *ExtendAfterOp = SE->getZeroExtendExpr(SE->getSCEV(BO), WideTy);
00386     const SCEV *OpAfterExtend = (SE->*GetExprForBO)(
00387       SE->getZeroExtendExpr(LHS, WideTy), SE->getZeroExtendExpr(RHS, WideTy),
00388       SCEV::FlagAnyWrap);
00389     if (ExtendAfterOp == OpAfterExtend) {
00390       BO->setHasNoUnsignedWrap();
00391       SE->forgetValue(BO);
00392       Changed = true;
00393     }
00394   }
00395 
00396   if (!BO->hasNoSignedWrap()) {
00397     const SCEV *ExtendAfterOp = SE->getSignExtendExpr(SE->getSCEV(BO), WideTy);
00398     const SCEV *OpAfterExtend = (SE->*GetExprForBO)(
00399       SE->getSignExtendExpr(LHS, WideTy), SE->getSignExtendExpr(RHS, WideTy),
00400       SCEV::FlagAnyWrap);
00401     if (ExtendAfterOp == OpAfterExtend) {
00402       BO->setHasNoSignedWrap();
00403       SE->forgetValue(BO);
00404       Changed = true;
00405     }
00406   }
00407 
00408   return Changed;
00409 }
00410 
00411 /// \brief Split sadd.with.overflow into add + sadd.with.overflow to allow
00412 /// analysis and optimization.
00413 ///
00414 /// \return A new value representing the non-overflowing add if possible,
00415 /// otherwise return the original value.
00416 Instruction *SimplifyIndvar::splitOverflowIntrinsic(Instruction *IVUser,
00417                                                     const DominatorTree *DT) {
00418   IntrinsicInst *II = dyn_cast<IntrinsicInst>(IVUser);
00419   if (!II || II->getIntrinsicID() != Intrinsic::sadd_with_overflow)
00420     return IVUser;
00421 
00422   // Find a branch guarded by the overflow check.
00423   BranchInst *Branch = nullptr;
00424   Instruction *AddVal = nullptr;
00425   for (User *U : II->users()) {
00426     if (ExtractValueInst *ExtractInst = dyn_cast<ExtractValueInst>(U)) {
00427       if (ExtractInst->getNumIndices() != 1)
00428         continue;
00429       if (ExtractInst->getIndices()[0] == 0)
00430         AddVal = ExtractInst;
00431       else if (ExtractInst->getIndices()[0] == 1 && ExtractInst->hasOneUse())
00432         Branch = dyn_cast<BranchInst>(ExtractInst->user_back());
00433     }
00434   }
00435   if (!AddVal || !Branch)
00436     return IVUser;
00437 
00438   BasicBlock *ContinueBB = Branch->getSuccessor(1);
00439   if (std::next(pred_begin(ContinueBB)) != pred_end(ContinueBB))
00440     return IVUser;
00441 
00442   // Check if all users of the add are provably NSW.
00443   bool AllNSW = true;
00444   for (Use &U : AddVal->uses()) {
00445     if (Instruction *UseInst = dyn_cast<Instruction>(U.getUser())) {
00446       BasicBlock *UseBB = UseInst->getParent();
00447       if (PHINode *PHI = dyn_cast<PHINode>(UseInst))
00448         UseBB = PHI->getIncomingBlock(U);
00449       if (!DT->dominates(ContinueBB, UseBB)) {
00450         AllNSW = false;
00451         break;
00452       }
00453     }
00454   }
00455   if (!AllNSW)
00456     return IVUser;
00457 
00458   // Go for it...
00459   IRBuilder<> Builder(IVUser);
00460   Instruction *AddInst = dyn_cast<Instruction>(
00461     Builder.CreateNSWAdd(II->getOperand(0), II->getOperand(1)));
00462 
00463   // The caller expects the new add to have the same form as the intrinsic. The
00464   // IV operand position must be the same.
00465   assert((AddInst->getOpcode() == Instruction::Add &&
00466           AddInst->getOperand(0) == II->getOperand(0)) &&
00467          "Bad add instruction created from overflow intrinsic.");
00468 
00469   AddVal->replaceAllUsesWith(AddInst);
00470   DeadInsts.emplace_back(AddVal);
00471   return AddInst;
00472 }
00473 
00474 /// Add all uses of Def to the current IV's worklist.
00475 static void pushIVUsers(
00476   Instruction *Def,
00477   SmallPtrSet<Instruction*,16> &Simplified,
00478   SmallVectorImpl< std::pair<Instruction*,Instruction*> > &SimpleIVUsers) {
00479 
00480   for (User *U : Def->users()) {
00481     Instruction *UI = cast<Instruction>(U);
00482 
00483     // Avoid infinite or exponential worklist processing.
00484     // Also ensure unique worklist users.
00485     // If Def is a LoopPhi, it may not be in the Simplified set, so check for
00486     // self edges first.
00487     if (UI != Def && Simplified.insert(UI).second)
00488       SimpleIVUsers.push_back(std::make_pair(UI, Def));
00489   }
00490 }
00491 
00492 /// Return true if this instruction generates a simple SCEV
00493 /// expression in terms of that IV.
00494 ///
00495 /// This is similar to IVUsers' isInteresting() but processes each instruction
00496 /// non-recursively when the operand is already known to be a simpleIVUser.
00497 ///
00498 static bool isSimpleIVUser(Instruction *I, const Loop *L, ScalarEvolution *SE) {
00499   if (!SE->isSCEVable(I->getType()))
00500     return false;
00501 
00502   // Get the symbolic expression for this instruction.
00503   const SCEV *S = SE->getSCEV(I);
00504 
00505   // Only consider affine recurrences.
00506   const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(S);
00507   if (AR && AR->getLoop() == L)
00508     return true;
00509 
00510   return false;
00511 }
00512 
00513 /// Iteratively perform simplification on a worklist of users
00514 /// of the specified induction variable. Each successive simplification may push
00515 /// more users which may themselves be candidates for simplification.
00516 ///
00517 /// This algorithm does not require IVUsers analysis. Instead, it simplifies
00518 /// instructions in-place during analysis. Rather than rewriting induction
00519 /// variables bottom-up from their users, it transforms a chain of IVUsers
00520 /// top-down, updating the IR only when it encounters a clear optimization
00521 /// opportunity.
00522 ///
00523 /// Once DisableIVRewrite is default, LSR will be the only client of IVUsers.
00524 ///
00525 void SimplifyIndvar::simplifyUsers(PHINode *CurrIV, IVVisitor *V) {
00526   if (!SE->isSCEVable(CurrIV->getType()))
00527     return;
00528 
00529   // Instructions processed by SimplifyIndvar for CurrIV.
00530   SmallPtrSet<Instruction*,16> Simplified;
00531 
00532   // Use-def pairs if IV users waiting to be processed for CurrIV.
00533   SmallVector<std::pair<Instruction*, Instruction*>, 8> SimpleIVUsers;
00534 
00535   // Push users of the current LoopPhi. In rare cases, pushIVUsers may be
00536   // called multiple times for the same LoopPhi. This is the proper thing to
00537   // do for loop header phis that use each other.
00538   pushIVUsers(CurrIV, Simplified, SimpleIVUsers);
00539 
00540   while (!SimpleIVUsers.empty()) {
00541     std::pair<Instruction*, Instruction*> UseOper =
00542       SimpleIVUsers.pop_back_val();
00543     Instruction *UseInst = UseOper.first;
00544 
00545     // Bypass back edges to avoid extra work.
00546     if (UseInst == CurrIV) continue;
00547 
00548     if (V && V->shouldSplitOverflowInstrinsics()) {
00549       UseInst = splitOverflowIntrinsic(UseInst, V->getDomTree());
00550       if (!UseInst)
00551         continue;
00552     }
00553 
00554     Instruction *IVOperand = UseOper.second;
00555     for (unsigned N = 0; IVOperand; ++N) {
00556       assert(N <= Simplified.size() && "runaway iteration");
00557 
00558       Value *NewOper = foldIVUser(UseOper.first, IVOperand);
00559       if (!NewOper)
00560         break; // done folding
00561       IVOperand = dyn_cast<Instruction>(NewOper);
00562     }
00563     if (!IVOperand)
00564       continue;
00565 
00566     if (eliminateIVUser(UseOper.first, IVOperand)) {
00567       pushIVUsers(IVOperand, Simplified, SimpleIVUsers);
00568       continue;
00569     }
00570 
00571     if (BinaryOperator *BO = dyn_cast<BinaryOperator>(UseOper.first)) {
00572       if (isa<OverflowingBinaryOperator>(BO) &&
00573           strengthenOverflowingOperation(BO, IVOperand)) {
00574         // re-queue uses of the now modified binary operator and fall
00575         // through to the checks that remain.
00576         pushIVUsers(IVOperand, Simplified, SimpleIVUsers);
00577       }
00578     }
00579 
00580     CastInst *Cast = dyn_cast<CastInst>(UseOper.first);
00581     if (V && Cast) {
00582       V->visitCast(Cast);
00583       continue;
00584     }
00585     if (isSimpleIVUser(UseOper.first, L, SE)) {
00586       pushIVUsers(UseOper.first, Simplified, SimpleIVUsers);
00587     }
00588   }
00589 }
00590 
00591 namespace llvm {
00592 
00593 void IVVisitor::anchor() { }
00594 
00595 /// Simplify instructions that use this induction variable
00596 /// by using ScalarEvolution to analyze the IV's recurrence.
00597 bool simplifyUsersOfIV(PHINode *CurrIV, ScalarEvolution *SE, DominatorTree *DT,
00598                        LoopInfo *LI, SmallVectorImpl<WeakVH> &Dead,
00599                        IVVisitor *V) {
00600   SimplifyIndvar SIV(LI->getLoopFor(CurrIV->getParent()), SE, DT, LI, Dead);
00601   SIV.simplifyUsers(CurrIV, V);
00602   return SIV.hasChanged();
00603 }
00604 
00605 /// Simplify users of induction variables within this
00606 /// loop. This does not actually change or add IVs.
00607 bool simplifyLoopIVs(Loop *L, ScalarEvolution *SE, DominatorTree *DT,
00608                      LoopInfo *LI, SmallVectorImpl<WeakVH> &Dead) {
00609   bool Changed = false;
00610   for (BasicBlock::iterator I = L->getHeader()->begin(); isa<PHINode>(I); ++I) {
00611     Changed |= simplifyUsersOfIV(cast<PHINode>(I), SE, DT, LI, Dead);
00612   }
00613   return Changed;
00614 }
00615 
00616 } // namespace llvm