1 files changed, 48 insertions, 328 deletions

diff --git a/lib/Transforms/Scalar/IndVarSimplify.cpp b/lib/Transforms/Scalar/IndVarSimplify.cpp
index e40d72979e..14f995bec2 100644
--- a/lib/Transforms/Scalar/IndVarSimplify.cpp
+++ b/lib/Transforms/Scalar/IndVarSimplify.cpp
@@ -11,8 +11,8 @@
 // computations derived from them) into simpler forms suitable for subsequent
 // analysis and transformation.
 //
-// This transformation makes the following changes to each loop with an
-// identifiable induction variable:
+// Additionally, unless -disable-iv-rewrite is on, this transformation makes the
+// following changes to each loop with an identifiable induction variable:
 //   1. All loops are transformed to have a SINGLE canonical induction variable
 //      which starts at zero and steps by one.
 //   2. The canonical induction variable is guaranteed to be the first PHI node
@@ -57,11 +57,11 @@
 #include "llvm/Support/raw_ostream.h"
 #include "llvm/Transforms/Utils/Local.h"
 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
+#include "llvm/Transforms/Utils/SimplifyIndVar.h"
 #include "llvm/Target/TargetData.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/Statistic.h"
-#include "llvm/ADT/STLExtras.h"
 using namespace llvm;
 
 STATISTIC(NumRemoved     , "Number of aux indvars removed");
@@ -69,16 +69,14 @@ STATISTIC(NumWidened     , "Number of indvars widened");
 STATISTIC(NumInserted    , "Number of canonical indvars added");
 STATISTIC(NumReplaced    , "Number of exit values replaced");
 STATISTIC(NumLFTR        , "Number of loop exit tests replaced");
-STATISTIC(NumElimIdentity, "Number of IV identities eliminated");
-STATISTIC(NumElimOperand,  "Number of IV operands folded into a use");
 STATISTIC(NumElimExt     , "Number of IV sign/zero extends eliminated");
-STATISTIC(NumElimRem     , "Number of IV remainder operations eliminated");
-STATISTIC(NumElimCmp     , "Number of IV comparisons eliminated");
 STATISTIC(NumElimIV      , "Number of congruent IVs eliminated");
 
-static cl::opt<bool> DisableIVRewrite(
-  "disable-iv-rewrite", cl::Hidden,
-  cl::desc("Disable canonical induction variable rewriting"));
+namespace llvm {
+  cl::opt<bool> DisableIVRewrite(
+    "disable-iv-rewrite", cl::Hidden,
+    cl::desc("Disable canonical induction variable rewriting"));
+}
 
 // Temporary flag for use with -disable-iv-rewrite to force a canonical IV for
 // LFTR purposes.
@@ -132,21 +130,12 @@ namespace {
     void HandleFloatingPointIV(Loop *L, PHINode *PH);
     void RewriteNonIntegerIVs(Loop *L);
 
-    void RewriteLoopExitValues(Loop *L, SCEVExpander &Rewriter);
-
-    void SimplifyIVUsers(SCEVExpander &Rewriter);
-    void SimplifyIVUsersNoRewrite(Loop *L, SCEVExpander &Rewriter);
-
-    bool EliminateIVUser(Instruction *UseInst, Instruction *IVOperand);
-    void EliminateIVComparison(ICmpInst *ICmp, Value *IVOperand);
-    void EliminateIVRemainder(BinaryOperator *Rem,
-                              Value *IVOperand,
-                              bool IsSigned);
-
-    bool FoldIVUser(Instruction *UseInst, Instruction *IVOperand);
+    void SimplifyAndExtend(Loop *L, SCEVExpander &Rewriter, LPPassManager &LPM);
 
     void SimplifyCongruentIVs(Loop *L);
 
+    void RewriteLoopExitValues(Loop *L, SCEVExpander &Rewriter);
+
     void RewriteIVExpressions(Loop *L, SCEVExpander &Rewriter);
 
     Value *LinearFunctionTestReplace(Loop *L, const SCEV *BackedgeTakenCount,
@@ -475,6 +464,8 @@ void IndVarSimplify::HandleFloatingPointIV(Loop *L, PHINode *PN) {
   // Add a new IVUsers entry for the newly-created integer PHI.
   if (IU)
     IU->AddUsersIfInteresting(NewPHI);
+
+  Changed = true;
 }
 
 void IndVarSimplify::RewriteNonIntegerIVs(Loop *L) {
@@ -623,36 +614,6 @@ void IndVarSimplify::RewriteLoopExitValues(Loop *L, SCEVExpander &Rewriter) {
 //  To be replaced by -disable-iv-rewrite.
 //===----------------------------------------------------------------------===//
 
-/// SimplifyIVUsers - Iteratively perform simplification on IVUsers within this
-/// loop. IVUsers is treated as a worklist. Each successive simplification may
-/// push more users which may themselves be candidates for simplification.
-///
-/// This is the old approach to IV simplification to be replaced by
-/// SimplifyIVUsersNoRewrite.
-///
-void IndVarSimplify::SimplifyIVUsers(SCEVExpander &Rewriter) {
-  // Each round of simplification involves a round of eliminating operations
-  // followed by a round of widening IVs. A single IVUsers worklist is used
-  // across all rounds. The inner loop advances the user. If widening exposes
-  // more uses, then another pass through the outer loop is triggered.
-  for (IVUsers::iterator I = IU->begin(); I != IU->end(); ++I) {
-    Instruction *UseInst = I->getUser();
-    Value *IVOperand = I->getOperandValToReplace();
-
-    if (ICmpInst *ICmp = dyn_cast<ICmpInst>(UseInst)) {
-      EliminateIVComparison(ICmp, IVOperand);
-      continue;
-    }
-    if (BinaryOperator *Rem = dyn_cast<BinaryOperator>(UseInst)) {
-      bool IsSigned = Rem->getOpcode() == Instruction::SRem;
-      if (IsSigned || Rem->getOpcode() == Instruction::URem) {
-        EliminateIVRemainder(Rem, IVOperand, IsSigned);
-        continue;
-      }
-    }
-  }
-}
-
 // FIXME: It is an extremely bad idea to indvar substitute anything more
 // complex than affine induction variables.  Doing so will put expensive
 // polynomial evaluations inside of the loop, and the str reduction pass
@@ -775,17 +736,34 @@ namespace {
   // provides the input to WidenIV.
   struct WideIVInfo {
     Type *WidestNativeType; // Widest integer type created [sz]ext
-    bool IsSigned;                // Was an sext user seen before a zext?
+    bool IsSigned;          // Was an sext user seen before a zext?
 
     WideIVInfo() : WidestNativeType(0), IsSigned(false) {}
   };
+
+  class WideIVVisitor : public IVVisitor {
+    ScalarEvolution *SE;
+    const TargetData *TD;
+
+  public:
+    WideIVInfo WI;
+
+    WideIVVisitor(ScalarEvolution *SCEV, const TargetData *TData) :
+      SE(SCEV), TD(TData) {}
+
+    // Implement the interface used by simplifyUsersOfIV.
+    virtual void visitCast(CastInst *Cast);
+  };
 }
 
-/// CollectExtend - Update information about the induction variable that is
+/// visitCast - Update information about the induction variable that is
 /// extended by this sign or zero extend operation. This is used to determine
 /// the final width of the IV before actually widening it.
-static void CollectExtend(CastInst *Cast, bool IsSigned, WideIVInfo &WI,
-                          ScalarEvolution *SE, const TargetData *TD) {
+void WideIVVisitor::visitCast(CastInst *Cast) {
+  bool IsSigned = Cast->getOpcode() == Instruction::SExt;
+  if (!IsSigned && Cast->getOpcode() != Instruction::ZExt)
+    return;
+
   Type *Ty = Cast->getType();
   uint64_t Width = SE->getTypeSizeInBits(Ty);
   if (TD && !TD->isLegalInteger(Width))
@@ -1181,242 +1159,16 @@ PHINode *WidenIV::CreateWideIV(SCEVExpander &Rewriter) {
 //  Simplification of IV users based on SCEV evaluation.
 //===----------------------------------------------------------------------===//
 
-void IndVarSimplify::EliminateIVComparison(ICmpInst *ICmp, Value *IVOperand) {
-  unsigned IVOperIdx = 0;
-  ICmpInst::Predicate Pred = ICmp->getPredicate();
-  if (IVOperand != ICmp->getOperand(0)) {
-    // Swapped
-    assert(IVOperand == ICmp->getOperand(1) && "Can't find IVOperand");
-    IVOperIdx = 1;
-    Pred = ICmpInst::getSwappedPredicate(Pred);
-  }
-
-  // Get the SCEVs for the ICmp operands.
-  const SCEV *S = SE->getSCEV(ICmp->getOperand(IVOperIdx));
-  const SCEV *X = SE->getSCEV(ICmp->getOperand(1 - IVOperIdx));
-
-  // Simplify unnecessary loops away.
-  const Loop *ICmpLoop = LI->getLoopFor(ICmp->getParent());
-  S = SE->getSCEVAtScope(S, ICmpLoop);
-  X = SE->getSCEVAtScope(X, ICmpLoop);
-
-  // If the condition is always true or always false, replace it with
-  // a constant value.
-  if (SE->isKnownPredicate(Pred, S, X))
-    ICmp->replaceAllUsesWith(ConstantInt::getTrue(ICmp->getContext()));
-  else if (SE->isKnownPredicate(ICmpInst::getInversePredicate(Pred), S, X))
-    ICmp->replaceAllUsesWith(ConstantInt::getFalse(ICmp->getContext()));
-  else
-    return;
-
-  DEBUG(dbgs() << "INDVARS: Eliminated comparison: " << *ICmp << '\n');
-  ++NumElimCmp;
-  Changed = true;
-  DeadInsts.push_back(ICmp);
-}
-
-void IndVarSimplify::EliminateIVRemainder(BinaryOperator *Rem,
-                                          Value *IVOperand,
-                                          bool IsSigned) {
-  // We're only interested in the case where we know something about
-  // the numerator.
-  if (IVOperand != Rem->getOperand(0))
-    return;
-
-  // Get the SCEVs for the ICmp operands.
-  const SCEV *S = SE->getSCEV(Rem->getOperand(0));
-  const SCEV *X = SE->getSCEV(Rem->getOperand(1));
-
-  // Simplify unnecessary loops away.
-  const Loop *ICmpLoop = LI->getLoopFor(Rem->getParent());
-  S = SE->getSCEVAtScope(S, ICmpLoop);
-  X = SE->getSCEVAtScope(X, ICmpLoop);
-
-  // i % n  -->  i  if i is in [0,n).
-  if ((!IsSigned || SE->isKnownNonNegative(S)) &&
-      SE->isKnownPredicate(IsSigned ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT,
-                           S, X))
-    Rem->replaceAllUsesWith(Rem->getOperand(0));
-  else {
-    // (i+1) % n  -->  (i+1)==n?0:(i+1)  if i is in [0,n).
-    const SCEV *LessOne =
-      SE->getMinusSCEV(S, SE->getConstant(S->getType(), 1));
-    if (IsSigned && !SE->isKnownNonNegative(LessOne))
-      return;
-
-    if (!SE->isKnownPredicate(IsSigned ?
-                              ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT,
-                              LessOne, X))
-      return;
-
-    ICmpInst *ICmp = new ICmpInst(Rem, ICmpInst::ICMP_EQ,
-                                  Rem->getOperand(0), Rem->getOperand(1),
-                                  "tmp");
-    SelectInst *Sel =
-      SelectInst::Create(ICmp,
-                         ConstantInt::get(Rem->getType(), 0),
-                         Rem->getOperand(0), "tmp", Rem);
-    Rem->replaceAllUsesWith(Sel);
-  }
-
-  // Inform IVUsers about the new users.
-  if (IU) {
-    if (Instruction *I = dyn_cast<Instruction>(Rem->getOperand(0)))
-      IU->AddUsersIfInteresting(I);
-  }
-  DEBUG(dbgs() << "INDVARS: Simplified rem: " << *Rem << '\n');
-  ++NumElimRem;
-  Changed = true;
-  DeadInsts.push_back(Rem);
-}
-
-/// EliminateIVUser - Eliminate an operation that consumes a simple IV and has
-/// no observable side-effect given the range of IV values.
-bool IndVarSimplify::EliminateIVUser(Instruction *UseInst,
-                                     Instruction *IVOperand) {
-  if (ICmpInst *ICmp = dyn_cast<ICmpInst>(UseInst)) {
-    EliminateIVComparison(ICmp, IVOperand);
-    return true;
-  }
-  if (BinaryOperator *Rem = dyn_cast<BinaryOperator>(UseInst)) {
-    bool IsSigned = Rem->getOpcode() == Instruction::SRem;
-    if (IsSigned || Rem->getOpcode() == Instruction::URem) {
-      EliminateIVRemainder(Rem, IVOperand, IsSigned);
-      return true;
-    }
-  }
-
-  // Eliminate any operation that SCEV can prove is an identity function.
-  if (!SE->isSCEVable(UseInst->getType()) ||
-      (UseInst->getType() != IVOperand->getType()) ||
-      (SE->getSCEV(UseInst) != SE->getSCEV(IVOperand)))
-    return false;
-
-  DEBUG(dbgs() << "INDVARS: Eliminated identity: " << *UseInst << '\n');
-
-  UseInst->replaceAllUsesWith(IVOperand);
-  ++NumElimIdentity;
-  Changed = true;
-  DeadInsts.push_back(UseInst);
-  return true;
-}
-
-/// FoldIVUser - Fold an IV operand into its use.  This removes increments of an
-/// aligned IV when used by a instruction that ignores the low bits.
-bool IndVarSimplify::FoldIVUser(Instruction *UseInst, Instruction *IVOperand) {
-  Value *IVSrc = 0;
-  unsigned OperIdx = 0;
-  const SCEV *FoldedExpr = 0;
-  switch (UseInst->getOpcode()) {
-  default:
-    return false;
-  case Instruction::UDiv:
-  case Instruction::LShr:
-    // We're only interested in the case where we know something about
-    // the numerator and have a constant denominator.
-    if (IVOperand != UseInst->getOperand(OperIdx) ||
-        !isa<ConstantInt>(UseInst->getOperand(1)))
-      return false;
-
-    // Attempt to fold a binary operator with constant operand.
-    // e.g. ((I + 1) >> 2) => I >> 2
-    if (IVOperand->getNumOperands() != 2 ||
-        !isa<ConstantInt>(IVOperand->getOperand(1)))
-      return false;
-
-    IVSrc = IVOperand->getOperand(0);
-    // IVSrc must be the (SCEVable) IV, since the other operand is const.
-    assert(SE->isSCEVable(IVSrc->getType()) && "Expect SCEVable IV operand");
-
-    ConstantInt *D = cast<ConstantInt>(UseInst->getOperand(1));
-    if (UseInst->getOpcode() == Instruction::LShr) {
-      // Get a constant for the divisor. See createSCEV.
-      uint32_t BitWidth = cast<IntegerType>(UseInst->getType())->getBitWidth();
-      if (D->getValue().uge(BitWidth))
-        return false;
-
-      D = ConstantInt::get(UseInst->getContext(),
-                           APInt(BitWidth, 1).shl(D->getZExtValue()));
-    }
-    FoldedExpr = SE->getUDivExpr(SE->getSCEV(IVSrc), SE->getSCEV(D));
-  }
-  // We have something that might fold it's operand. Compare SCEVs.
-  if (!SE->isSCEVable(UseInst->getType()))
-    return false;
-
-  // Bypass the operand if SCEV can prove it has no effect.
-  if (SE->getSCEV(UseInst) != FoldedExpr)
-    return false;
-
-  DEBUG(dbgs() << "INDVARS: Eliminated IV operand: " << *IVOperand
-        << " -> " << *UseInst << '\n');
 
-  UseInst->setOperand(OperIdx, IVSrc);
-  assert(SE->getSCEV(UseInst) == FoldedExpr && "bad SCEV with folded oper");
-
-  ++NumElimOperand;
-  Changed = true;
-  if (IVOperand->use_empty())
-    DeadInsts.push_back(IVOperand);
-  return true;
-}
-
-/// pushIVUsers - Add all uses of Def to the current IV's worklist.
-///
-static void pushIVUsers(
-  Instruction *Def,
-  SmallPtrSet<Instruction*,16> &Simplified,
-  SmallVectorImpl< std::pair<Instruction*,Instruction*> > &SimpleIVUsers) {
-
-  for (Value::use_iterator UI = Def->use_begin(), E = Def->use_end();
-       UI != E; ++UI) {
-    Instruction *User = cast<Instruction>(*UI);
-
-    // Avoid infinite or exponential worklist processing.
-    // Also ensure unique worklist users.
-    // If Def is a LoopPhi, it may not be in the Simplified set, so check for
-    // self edges first.
-    if (User != Def && Simplified.insert(User))
-      SimpleIVUsers.push_back(std::make_pair(User, Def));
-  }
-}
-
-/// isSimpleIVUser - Return true if this instruction generates a simple SCEV
-/// expression in terms of that IV.
-///
-/// This is similar to IVUsers' isInsteresting() but processes each instruction
-/// non-recursively when the operand is already known to be a simpleIVUser.
-///
-static bool isSimpleIVUser(Instruction *I, const Loop *L, ScalarEvolution *SE) {
-  if (!SE->isSCEVable(I->getType()))
-    return false;
-
-  // Get the symbolic expression for this instruction.
-  const SCEV *S = SE->getSCEV(I);
-
-  // Only consider affine recurrences.
-  const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(S);
-  if (AR && AR->getLoop() == L)
-    return true;
-
-  return false;
-}
-
-/// SimplifyIVUsersNoRewrite - Iteratively perform simplification on a worklist
-/// of IV users. Each successive simplification may push more users which may
+/// SimplifyAndExtend - Iteratively perform simplification on a worklist of IV
+/// users. Each successive simplification may push more users which may
 /// themselves be candidates for simplification.
 ///
-/// The "NoRewrite" algorithm does not require IVUsers analysis. Instead, it
-/// simplifies instructions in-place during analysis. Rather than rewriting
-/// induction variables bottom-up from their users, it transforms a chain of
-/// IVUsers top-down, updating the IR only when it encouters a clear
-/// optimization opportunitiy. A SCEVExpander "Rewriter" instance is still
-/// needed, but only used to generate a new IV (phi) of wider type for sign/zero
-/// extend elimination.
+/// Sign/Zero extend elimination is interleaved with IV simplification.
 ///
-/// Once DisableIVRewrite is default, LSR will be the only client of IVUsers.
-///
-void IndVarSimplify::SimplifyIVUsersNoRewrite(Loop *L, SCEVExpander &Rewriter) {
+void IndVarSimplify::SimplifyAndExtend(Loop *L,
+                                       SCEVExpander &Rewriter,
+                                       LPPassManager &LPM) {
   std::map<PHINode *, WideIVInfo> WideIVMap;
 
   SmallVector<PHINode*, 8> LoopPhis;
@@ -1433,49 +1185,17 @@ void IndVarSimplify::SimplifyIVUsersNoRewrite(Loop *L, SCEVExpander &Rewriter) {
     // extension. The first time SCEV attempts to normalize sign/zero extension,
     // the result becomes final. So for the most predictable results, we delay
     // evaluation of sign/zero extend evaluation until needed, and avoid running
-    // other SCEV based analysis prior to SimplifyIVUsersNoRewrite.
+    // other SCEV based analysis prior to SimplifyAndExtend.
     do {
       PHINode *CurrIV = LoopPhis.pop_back_val();
 
       // Information about sign/zero extensions of CurrIV.
-      WideIVInfo WI;
-
-      // Instructions processed by SimplifyIVUsers for CurrIV.
-      SmallPtrSet<Instruction*,16> Simplified;
-
-      // Use-def pairs if IV users waiting to be processed for CurrIV.
-      SmallVector<std::pair<Instruction*, Instruction*>, 8> SimpleIVUsers;
-
-      // Push users of the current LoopPhi. In rare cases, pushIVUsers may be
-      // called multiple times for the same LoopPhi. This is the proper thing to
-      // do for loop header phis that use each other.
-      pushIVUsers(CurrIV, Simplified, SimpleIVUsers);
-
-      while (!SimpleIVUsers.empty()) {
-        std::pair<Instruction*, Instruction*> UseOper =
-          SimpleIVUsers.pop_back_val();
-        // Bypass back edges to avoid extra work.
-        if (UseOper.first == CurrIV) continue;
+      WideIVVisitor WIV(SE, TD);
 
-        FoldIVUser(UseOper.first, UseOper.second);
+      Changed |= simplifyUsersOfIV(CurrIV, &LPM, DeadInsts, &WIV);
 
-        if (EliminateIVUser(UseOper.first, UseOper.second)) {
-          pushIVUsers(UseOper.second, Simplified, SimpleIVUsers);
-          continue;
-        }
-        if (CastInst *Cast = dyn_cast<CastInst>(UseOper.first)) {
-          bool IsSigned = Cast->getOpcode() == Instruction::SExt;
-          if (IsSigned || Cast->getOpcode() == Instruction::ZExt) {
-            CollectExtend(Cast, IsSigned, WI, SE, TD);
-          }
-          continue;
-        }
-        if (isSimpleIVUser(UseOper.first, L, SE)) {
-          pushIVUsers(UseOper.first, Simplified, SimpleIVUsers);
-        }
-      }
-      if (WI.WidestNativeType) {
-        WideIVMap[CurrIV] = WI;
+      if (WIV.WI.WidestNativeType) {
+        WideIVMap[CurrIV] = WIV.WI;
       }
     } while(!LoopPhis.empty());
 
@@ -1492,7 +1212,7 @@ void IndVarSimplify::SimplifyIVUsersNoRewrite(Loop *L, SCEVExpander &Rewriter) {
 }
 
 /// SimplifyCongruentIVs - Check for congruent phis in this loop header and
-/// populate ExprToIVMap for use later.
+/// replace them with their chosen representative.
 ///
 void IndVarSimplify::SimplifyCongruentIVs(Loop *L) {
   DenseMap<const SCEV *, PHINode *> ExprToIVMap;
@@ -2097,7 +1817,7 @@ bool IndVarSimplify::runOnLoop(Loop *L, LPPassManager &LPM) {
   // set no-wrap flags before normalizing sign/zero extension.
   if (DisableIVRewrite) {
     Rewriter.disableCanonicalMode();
-    SimplifyIVUsersNoRewrite(L, Rewriter);
+    SimplifyAndExtend(L, Rewriter, LPM);
   }
 
   // Check to see if this loop has a computable loop-invariant execution count.
@@ -2111,7 +1831,7 @@ bool IndVarSimplify::runOnLoop(Loop *L, LPPassManager &LPM) {
 
   // Eliminate redundant IV users.
   if (!DisableIVRewrite)
-    SimplifyIVUsers(Rewriter);
+    Changed |= simplifyIVUsers(IU, &LPM, DeadInsts);
 
   // Eliminate redundant IV cycles.
   if (DisableIVRewrite)