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