13 files changed, 1376 insertions, 944 deletions

diff --git a/include/llvm/Analysis/IVUsers.h b/include/llvm/Analysis/IVUsers.h
new file mode 100644
index 0000000000..36ff07b678
--- /dev/null
+++ b/include/llvm/Analysis/IVUsers.h
@@ -0,0 +1,235 @@
+//===- llvm/Analysis/IVUsers.h - Induction Variable Users -------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file implements bookkeeping for "interesting" users of expressions
+// computed from induction variables.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ANALYSIS_IVUSERS_H
+#define LLVM_ANALYSIS_IVUSERS_H
+
+#include "llvm/Analysis/LoopPass.h"
+#include "llvm/Analysis/ScalarEvolution.h"
+#include <llvm/ADT/SmallVector.h>
+#include <map>
+
+namespace llvm {
+
+class DominatorTree;
+class Instruction;
+class Value;
+class IVUsersOfOneStride;
+
+/// IVStrideUse - Keep track of one use of a strided induction variable, where
+/// the stride is stored externally.  The Offset member keeps track of the
+/// offset from the IV, User is the actual user of the operand, and
+/// 'OperandValToReplace' is the operand of the User that is the use.
+class IVStrideUse : public CallbackVH, public ilist_node<IVStrideUse> {
+public:
+  IVStrideUse(IVUsersOfOneStride *parent,
+              const SCEVHandle &offset,
+              Instruction* U, Value *O, bool issigned)
+    : CallbackVH(U), Parent(parent), Offset(offset),
+      OperandValToReplace(O), IsSigned(issigned),
+      IsUseOfPostIncrementedValue(false) {
+  }
+
+  /// getUser - Return the user instruction for this use.
+  Instruction *getUser() const {
+    return cast<Instruction>(getValPtr());
+  }
+
+  /// setUser - Assign a new user instruction for this use.
+  void setUser(Instruction *NewUser) {
+    setValPtr(NewUser);
+  }
+
+  /// getParent - Return a pointer to the IVUsersOfOneStride that owns
+  /// this IVStrideUse.
+  IVUsersOfOneStride *getParent() const { return Parent; }
+
+  /// getOffset - Return the offset to add to a theoeretical induction
+  /// variable that starts at zero and counts up by the stride to compute
+  /// the value for the use. This always has the same type as the stride,
+  /// which may need to be casted to match the type of the use.
+  SCEVHandle getOffset() const { return Offset; }
+
+  /// setOffset - Assign a new offset to this use.
+  void setOffset(SCEVHandle Val) {
+    Offset = Val;
+  }
+
+  /// getOperandValToReplace - Return the Value of the operand in the user
+  /// instruction that this IVStrideUse is representing.
+  Value *getOperandValToReplace() const {
+    return OperandValToReplace;
+  }
+
+  /// setOperandValToReplace - Assign a new Value as the operand value
+  /// to replace.
+  void setOperandValToReplace(Value *Op) {
+    OperandValToReplace = Op;
+  }
+
+  /// isSigned - The stride (and thus also the Offset) of this use may be in
+  /// a narrower type than the use itself (OperandValToReplace->getType()).
+  /// When this is the case, isSigned() indicates whether the IV expression
+  /// should be signed-extended instead of zero-extended to fit the type of
+  /// the use.
+  bool isSigned() const { return IsSigned; }
+
+  /// isUseOfPostIncrementedValue - True if this should use the
+  /// post-incremented version of this IV, not the preincremented version.
+  /// This can only be set in special cases, such as the terminating setcc
+  /// instruction for a loop or uses dominated by the loop.
+  bool isUseOfPostIncrementedValue() const {
+    return IsUseOfPostIncrementedValue;
+  }
+
+  /// setIsUseOfPostIncrmentedValue - set the flag that indicates whether
+  /// this is a post-increment use.
+  void setIsUseOfPostIncrementedValue(bool Val) {
+    IsUseOfPostIncrementedValue = Val;
+  }
+
+private:
+  /// Parent - a pointer to the IVUsersOfOneStride that owns this IVStrideUse.
+  IVUsersOfOneStride *Parent;
+
+  /// Offset - The offset to add to the base induction expression.
+  SCEVHandle Offset;
+
+  /// OperandValToReplace - The Value of the operand in the user instruction
+  /// that this IVStrideUse is representing.
+  WeakVH OperandValToReplace;
+
+  /// IsSigned - Determines whether the replacement value is sign or
+  /// zero extended to the type of the use.
+  bool IsSigned;
+
+  /// IsUseOfPostIncrementedValue - True if this should use the
+  /// post-incremented version of this IV, not the preincremented version.
+  bool IsUseOfPostIncrementedValue;
+
+  /// Deleted - Implementation of CallbackVH virtual function to
+  /// recieve notification when the User is deleted.
+  virtual void deleted();
+};
+
+template<> struct ilist_traits<IVStrideUse>
+  : public ilist_default_traits<IVStrideUse> {
+  // createSentinel is used to get hold of a node that marks the end of
+  // the list...
+  // The sentinel is relative to this instance, so we use a non-static
+  // method.
+  IVStrideUse *createSentinel() const {
+    // since i(p)lists always publicly derive from the corresponding
+    // traits, placing a data member in this class will augment i(p)list.
+    // But since the NodeTy is expected to publicly derive from
+    // ilist_node<NodeTy>, there is a legal viable downcast from it
+    // to NodeTy. We use this trick to superpose i(p)list with a "ghostly"
+    // NodeTy, which becomes the sentinel. Dereferencing the sentinel is
+    // forbidden (save the ilist_node<NodeTy>) so no one will ever notice
+    // the superposition.
+    return static_cast<IVStrideUse*>(&Sentinel);
+  }
+  static void destroySentinel(IVStrideUse*) {}
+
+  IVStrideUse *provideInitialHead() const { return createSentinel(); }
+  IVStrideUse *ensureHead(IVStrideUse*) const { return createSentinel(); }
+  static void noteHead(IVStrideUse*, IVStrideUse*) {}
+
+private:
+  mutable ilist_node<IVStrideUse> Sentinel;
+};
+
+/// IVUsersOfOneStride - This structure keeps track of all instructions that
+/// have an operand that is based on the trip count multiplied by some stride.
+struct IVUsersOfOneStride : public ilist_node<IVUsersOfOneStride> {
+private:
+  IVUsersOfOneStride(const IVUsersOfOneStride &I); // do not implement
+  void operator=(const IVUsersOfOneStride &I);     // do not implement
+
+public:
+  IVUsersOfOneStride() : Stride(0) {}
+
+  explicit IVUsersOfOneStride(const SCEV *stride) : Stride(stride) {}
+
+  /// Stride - The stride for all the contained IVStrideUses. This is
+  /// a constant for affine strides.
+  const SCEV *Stride;
+
+  /// Users - Keep track of all of the users of this stride as well as the
+  /// initial value and the operand that uses the IV.
+  ilist<IVStrideUse> Users;
+
+  void addUser(const SCEVHandle &Offset,Instruction *User, Value *Operand,
+               bool isSigned) {
+    Users.push_back(new IVStrideUse(this, Offset, User, Operand, isSigned));
+  }
+};
+
+class IVUsers : public LoopPass {
+  friend class IVStrideUserVH;
+  Loop *L;
+  LoopInfo *LI;
+  DominatorTree *DT;
+  ScalarEvolution *SE;
+  SmallPtrSet<Instruction*,16> Processed;
+
+public:
+  /// IVUses - A list of all tracked IV uses of induction variable expressions
+  /// we are interested in.
+  ilist<IVUsersOfOneStride> IVUses;
+
+  /// IVUsesByStride - A mapping from the strides in StrideOrder to the
+  /// uses in IVUses.
+  std::map<SCEVHandle, IVUsersOfOneStride*> IVUsesByStride;
+
+  /// StrideOrder - An ordering of the keys in IVUsesByStride that is stable:
+  /// We use this to iterate over the IVUsesByStride collection without being
+  /// dependent on random ordering of pointers in the process.
+  SmallVector<SCEVHandle, 16> StrideOrder;
+
+private:
+  virtual void getAnalysisUsage(AnalysisUsage &AU) const;
+
+  virtual bool runOnLoop(Loop *L, LPPassManager &LPM);
+
+  virtual void releaseMemory();
+
+public:
+  static char ID; // Pass ID, replacement for typeid
+  IVUsers();
+
+  /// AddUsersIfInteresting - Inspect the specified Instruction.  If it is a
+  /// reducible SCEV, recursively add its users to the IVUsesByStride set and
+  /// return true.  Otherwise, return false.
+  bool AddUsersIfInteresting(Instruction *I);
+
+  /// getReplacementExpr - Return a SCEV expression which computes the
+  /// value of the OperandValToReplace of the given IVStrideUse.
+  SCEVHandle getReplacementExpr(const IVStrideUse &U) const;
+
+  void print(raw_ostream &OS, const Module* = 0) const;
+  virtual void print(std::ostream &OS, const Module* = 0) const;
+  void print(std::ostream *OS, const Module* M = 0) const {
+    if (OS) print(*OS, M);
+  }
+
+  /// dump - This method is used for debugging.
+  void dump() const;
+};
+
+Pass *createIVUsersPass();
+
+}
+
+#endif
diff --git a/lib/Analysis/IVUsers.cpp b/lib/Analysis/IVUsers.cpp
new file mode 100644
index 0000000000..9ec9cacbbb
--- /dev/null
+++ b/lib/Analysis/IVUsers.cpp
@@ -0,0 +1,391 @@
+//===- IVUsers.cpp - Induction Variable Users -------------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file implements bookkeeping for "interesting" users of expressions
+// computed from induction variables.
+//
+//===----------------------------------------------------------------------===//
+
+#define DEBUG_TYPE "iv-users"
+#include "llvm/Analysis/IVUsers.h"
+#include "llvm/Constants.h"
+#include "llvm/Instructions.h"
+#include "llvm/Type.h"
+#include "llvm/DerivedTypes.h"
+#include "llvm/Analysis/Dominators.h"
+#include "llvm/Analysis/LoopInfo.h"
+#include "llvm/Analysis/LoopPass.h"
+#include "llvm/Analysis/ScalarEvolutionExpressions.h"
+#include "llvm/ADT/STLExtras.h"
+#include "llvm/Support/Debug.h"
+#include "llvm/Support/raw_ostream.h"
+#include <algorithm>
+using namespace llvm;
+
+char IVUsers::ID = 0;
+static RegisterPass<IVUsers>
+X("iv-users", "Induction Variable Users", false, true);
+
+Pass *llvm::createIVUsersPass() {
+  return new IVUsers();
+}
+
+/// containsAddRecFromDifferentLoop - Determine whether expression S involves a
+/// subexpression that is an AddRec from a loop other than L.  An outer loop
+/// of L is OK, but not an inner loop nor a disjoint loop.
+static bool containsAddRecFromDifferentLoop(SCEVHandle S, Loop *L) {
+  // This is very common, put it first.
+  if (isa<SCEVConstant>(S))
+    return false;
+  if (const SCEVCommutativeExpr *AE = dyn_cast<SCEVCommutativeExpr>(S)) {
+    for (unsigned int i=0; i< AE->getNumOperands(); i++)
+      if (containsAddRecFromDifferentLoop(AE->getOperand(i), L))
+        return true;
+    return false;
+  }
+  if (const SCEVAddRecExpr *AE = dyn_cast<SCEVAddRecExpr>(S)) {
+    if (const Loop *newLoop = AE->getLoop()) {
+      if (newLoop == L)
+        return false;
+      // if newLoop is an outer loop of L, this is OK.
+      if (!LoopInfoBase<BasicBlock>::isNotAlreadyContainedIn(L, newLoop))
+        return false;
+    }
+    return true;
+  }
+  if (const SCEVUDivExpr *DE = dyn_cast<SCEVUDivExpr>(S))
+    return containsAddRecFromDifferentLoop(DE->getLHS(), L) ||
+           containsAddRecFromDifferentLoop(DE->getRHS(), L);
+#if 0
+  // SCEVSDivExpr has been backed out temporarily, but will be back; we'll
+  // need this when it is.
+  if (const SCEVSDivExpr *DE = dyn_cast<SCEVSDivExpr>(S))
+    return containsAddRecFromDifferentLoop(DE->getLHS(), L) ||
+           containsAddRecFromDifferentLoop(DE->getRHS(), L);
+#endif
+  if (const SCEVCastExpr *CE = dyn_cast<SCEVCastExpr>(S))
+    return containsAddRecFromDifferentLoop(CE->getOperand(), L);
+  return false;
+}
+
+/// getSCEVStartAndStride - Compute the start and stride of this expression,
+/// returning false if the expression is not a start/stride pair, or true if it
+/// is.  The stride must be a loop invariant expression, but the start may be
+/// a mix of loop invariant and loop variant expressions.  The start cannot,
+/// however, contain an AddRec from a different loop, unless that loop is an
+/// outer loop of the current loop.
+static bool getSCEVStartAndStride(const SCEVHandle &SH, Loop *L, Loop *UseLoop,
+                                  SCEVHandle &Start, SCEVHandle &Stride,
+                                  bool &isSigned,
+                                  ScalarEvolution *SE, DominatorTree *DT) {
+  SCEVHandle TheAddRec = Start;   // Initialize to zero.
+  bool isSExt = false;
+  bool isZExt = false;
+
+  // If the outer level is an AddExpr, the operands are all start values except
+  // for a nested AddRecExpr.
+  if (const SCEVAddExpr *AE = dyn_cast<SCEVAddExpr>(SH)) {
+    for (unsigned i = 0, e = AE->getNumOperands(); i != e; ++i)
+      if (const SCEVAddRecExpr *AddRec =
+             dyn_cast<SCEVAddRecExpr>(AE->getOperand(i))) {
+        if (AddRec->getLoop() == L)
+          TheAddRec = SE->getAddExpr(AddRec, TheAddRec);
+        else
+          return false;  // Nested IV of some sort?
+      } else {
+        Start = SE->getAddExpr(Start, AE->getOperand(i));
+      }
+
+  } else if (const SCEVZeroExtendExpr *Z = dyn_cast<SCEVZeroExtendExpr>(SH)) {
+    TheAddRec = Z->getOperand();
+    isZExt = true;
+  } else if (const SCEVSignExtendExpr *S = dyn_cast<SCEVSignExtendExpr>(SH)) {
+    TheAddRec = S->getOperand();
+    isSExt = true;
+  } else if (isa<SCEVAddRecExpr>(SH)) {
+    TheAddRec = SH;
+  } else {
+    return false;  // not analyzable.
+  }
+
+  const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(TheAddRec);
+  if (!AddRec || AddRec->getLoop() != L) return false;
+
+  // Use getSCEVAtScope to attempt to simplify other loops out of
+  // the picture.
+  SCEVHandle AddRecStart = AddRec->getStart();
+  SCEVHandle BetterAddRecStart = SE->getSCEVAtScope(AddRecStart, UseLoop);
+  if (!isa<SCEVCouldNotCompute>(BetterAddRecStart))
+    AddRecStart = BetterAddRecStart;
+
+  // FIXME: If Start contains an SCEVAddRecExpr from a different loop, other
+  // than an outer loop of the current loop, reject it.  LSR has no concept of
+  // operating on more than one loop at a time so don't confuse it with such
+  // expressions.
+  if (containsAddRecFromDifferentLoop(AddRecStart, L))
+    return false;
+
+  if (isSExt || isZExt)
+    Start = SE->getTruncateExpr(Start, AddRec->getType());
+
+  Start = SE->getAddExpr(Start, AddRecStart);
+
+  if (!isa<SCEVConstant>(AddRec->getStepRecurrence(*SE))) {
+    // If stride is an instruction, make sure it dominates the loop preheader.
+    // Otherwise we could end up with a use before def situation.
+    BasicBlock *Preheader = L->getLoopPreheader();
+    if (!AddRec->getStepRecurrence(*SE)->dominates(Preheader, DT))
+      return false;
+
+    DOUT << "[" << L->getHeader()->getName()
+         << "] Variable stride: " << *AddRec << "\n";
+  }
+
+  Stride = AddRec->getStepRecurrence(*SE);
+  isSigned = isSExt;
+  return true;
+}
+
+/// IVUseShouldUsePostIncValue - We have discovered a "User" of an IV expression
+/// and now we need to decide whether the user should use the preinc or post-inc
+/// value.  If this user should use the post-inc version of the IV, return true.
+///
+/// Choosing wrong here can break dominance properties (if we choose to use the
+/// post-inc value when we cannot) or it can end up adding extra live-ranges to
+/// the loop, resulting in reg-reg copies (if we use the pre-inc value when we
+/// should use the post-inc value).
+static bool IVUseShouldUsePostIncValue(Instruction *User, Instruction *IV,
+                                       Loop *L, LoopInfo *LI, DominatorTree *DT,
+                                       Pass *P) {
+  // If the user is in the loop, use the preinc value.
+  if (L->contains(User->getParent())) return false;
+
+  BasicBlock *LatchBlock = L->getLoopLatch();
+
+  // Ok, the user is outside of the loop.  If it is dominated by the latch
+  // block, use the post-inc value.
+  if (DT->dominates(LatchBlock, User->getParent()))
+    return true;
+
+  // There is one case we have to be careful of: PHI nodes.  These little guys
+  // can live in blocks that are not dominated by the latch block, but (since
+  // their uses occur in the predecessor block, not the block the PHI lives in)
+  // should still use the post-inc value.  Check for this case now.
+  PHINode *PN = dyn_cast<PHINode>(User);
+  if (!PN) return false;  // not a phi, not dominated by latch block.
+
+  // Look at all of the uses of IV by the PHI node.  If any use corresponds to
+  // a block that is not dominated by the latch block, give up and use the
+  // preincremented value.
+  unsigned NumUses = 0;
+  for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
+    if (PN->getIncomingValue(i) == IV) {
+      ++NumUses;
+      if (!DT->dominates(LatchBlock, PN->getIncomingBlock(i)))
+        return false;
+    }
+
+  // Okay, all uses of IV by PN are in predecessor blocks that really are
+  // dominated by the latch block.  Use the post-incremented value.
+  return true;
+}
+
+/// AddUsersIfInteresting - Inspect the specified instruction.  If it is a
+/// reducible SCEV, recursively add its users to the IVUsesByStride set and
+/// return true.  Otherwise, return false.
+bool IVUsers::AddUsersIfInteresting(Instruction *I) {
+  if (!SE->isSCEVable(I->getType()))
+    return false;   // Void and FP expressions cannot be reduced.
+
+  // LSR is not APInt clean, do not touch integers bigger than 64-bits.
+  if (SE->getTypeSizeInBits(I->getType()) > 64)
+    return false;
+
+  if (!Processed.insert(I))
+    return true;    // Instruction already handled.
+
+  // Get the symbolic expression for this instruction.
+  SCEVHandle ISE = SE->getSCEV(I);
+  if (isa<SCEVCouldNotCompute>(ISE)) return false;
+
+  // Get the start and stride for this expression.
+  Loop *UseLoop = LI->getLoopFor(I->getParent());
+  SCEVHandle Start = SE->getIntegerSCEV(0, ISE->getType());
+  SCEVHandle Stride = Start;
+  bool isSigned;
+
+  if (!getSCEVStartAndStride(ISE, L, UseLoop, Start, Stride, isSigned, SE, DT))
+    return false;  // Non-reducible symbolic expression, bail out.
+
+  SmallPtrSet<Instruction *, 4> UniqueUsers;
+  for (Value::use_iterator UI = I->use_begin(), E = I->use_end();
+       UI != E; ++UI) {
+    Instruction *User = cast<Instruction>(*UI);
+    if (!UniqueUsers.insert(User))
+      continue;
+
+    // Do not infinitely recurse on PHI nodes.
+    if (isa<PHINode>(User) && Processed.count(User))
+      continue;
+
+    // Descend recursively, but not into PHI nodes outside the current loop.
+    // It's important to see the entire expression outside the loop to get
+    // choices that depend on addressing mode use right, although we won't
+    // consider references ouside the loop in all cases.
+    // If User is already in Processed, we don't want to recurse into it again,
+    // but do want to record a second reference in the same instruction.
+    bool AddUserToIVUsers = false;
+    if (LI->getLoopFor(User->getParent()) != L) {
+      if (isa<PHINode>(User) || Processed.count(User) ||
+          !AddUsersIfInteresting(User)) {
+        DOUT << "FOUND USER in other loop: " << *User
+             << "   OF SCEV: " << *ISE << "\n";
+        AddUserToIVUsers = true;
+      }
+    } else if (Processed.count(User) ||
+               !AddUsersIfInteresting(User)) {
+      DOUT << "FOUND USER: " << *User
+           << "   OF SCEV: " << *ISE << "\n";
+      AddUserToIVUsers = true;
+    }
+
+    if (AddUserToIVUsers) {
+      IVUsersOfOneStride *StrideUses = IVUsesByStride[Stride];
+      if (!StrideUses) {    // First occurrence of this stride?
+        StrideOrder.push_back(Stride);
+        StrideUses = new IVUsersOfOneStride(Stride);
+        IVUses.push_back(StrideUses);
+        IVUsesByStride[Stride] = StrideUses;
+      }
+
+      // Okay, we found a user that we cannot reduce.  Analyze the instruction
+      // and decide what to do with it.  If we are a use inside of the loop, use
+      // the value before incrementation, otherwise use it after incrementation.
+      if (IVUseShouldUsePostIncValue(User, I, L, LI, DT, this)) {
+        // The value used will be incremented by the stride more than we are
+        // expecting, so subtract this off.
+        SCEVHandle NewStart = SE->getMinusSCEV(Start, Stride);
+        StrideUses->addUser(NewStart, User, I, isSigned);
+        StrideUses->Users.back().setIsUseOfPostIncrementedValue(true);
+        DOUT << "   USING POSTINC SCEV, START=" << *NewStart<< "\n";
+      } else {
+        StrideUses->addUser(Start, User, I, isSigned);
+      }
+    }
+  }
+  return true;
+}
+
+IVUsers::IVUsers()
+ : LoopPass(&ID) {
+}
+
+void IVUsers::getAnalysisUsage(AnalysisUsage &AU) const {
+  AU.addRequired<LoopInfo>();
+  AU.addRequired<DominatorTree>();
+  AU.addRequired<ScalarEvolution>();
+  AU.setPreservesAll();
+}
+
+bool IVUsers::runOnLoop(Loop *l, LPPassManager &LPM) {
+
+  L = l;
+  LI = &getAnalysis<LoopInfo>();
+  DT = &getAnalysis<DominatorTree>();
+  SE = &getAnalysis<ScalarEvolution>();
+
+  // Find all uses of induction variables in this loop, and categorize
+  // them by stride.  Start by finding all of the PHI nodes in the header for
+  // this loop.  If they are induction variables, inspect their uses.
+  for (BasicBlock::iterator I = L->getHeader()->begin(); isa<PHINode>(I); ++I)
+    AddUsersIfInteresting(I);
+
+  return false;
+}
+
+/// getReplacementExpr - Return a SCEV expression which computes the
+/// value of the OperandValToReplace of the given IVStrideUse.
+SCEVHandle IVUsers::getReplacementExpr(const IVStrideUse &U) const {
+  const Type *UseTy = U.getOperandValToReplace()->getType();
+  // Start with zero.
+  SCEVHandle RetVal = SE->getIntegerSCEV(0, U.getParent()->Stride->getType());
+  // Create the basic add recurrence.
+  RetVal = SE->getAddRecExpr(RetVal, U.getParent()->Stride, L);
+  // Add the offset in a separate step, because it may be loop-variant.
+  RetVal = SE->getAddExpr(RetVal, U.getOffset());
+  // For uses of post-incremented values, add an extra stride to compute
+  // the actual replacement value.
+  if (U.isUseOfPostIncrementedValue())
+    RetVal = SE->getAddExpr(RetVal, U.getParent()->Stride);
+  // Evaluate the expression out of the loop, if possible.
+  if (!L->contains(U.getUser()->getParent())) {
+    SCEVHandle ExitVal = SE->getSCEVAtScope(RetVal, L->getParentLoop());
+    if (!isa<SCEVCouldNotCompute>(ExitVal) && ExitVal->isLoopInvariant(L))
+      RetVal = ExitVal;
+  }
+  // Promote the result to the type of the use.
+  if (SE->getTypeSizeInBits(RetVal->getType()) !=
+      SE->getTypeSizeInBits(UseTy)) {
+    if (U.isSigned())
+      RetVal = SE->getSignExtendExpr(RetVal, UseTy);
+    else
+      RetVal = SE->getZeroExtendExpr(RetVal, UseTy);
+  }
+  return RetVal;
+}
+
+void IVUsers::print(raw_ostream &OS, const Module *M) const {
+  OS << "IV Users for loop ";
+  WriteAsOperand(OS, L->getHeader(), false);
+  if (SE->hasLoopInvariantBackedgeTakenCount(L)) {
+    OS << " with backedge-taken count "
+       << *SE->getBackedgeTakenCount(L);
+  }
+  OS << ":\n";
+
+  for (unsigned Stride = 0, e = StrideOrder.size(); Stride != e; ++Stride) {
+    std::map<SCEVHandle, IVUsersOfOneStride*>::const_iterator SI =
+      IVUsesByStride.find(StrideOrder[Stride]);
+    assert(SI != IVUsesByStride.end() && "Stride doesn't exist!");
+    OS << "  Stride " << *SI->first->getType() << " " << *SI->first << ":\n";
+
+    for (ilist<IVStrideUse>::const_iterator UI = SI->second->Users.begin(),
+         E = SI->second->Users.end(); UI != E; ++UI) {
+      OS << "    ";
+      WriteAsOperand(OS, UI->getOperandValToReplace(), false);
+      OS << " = ";
+      OS << *getReplacementExpr(*UI);
+      if (UI->isUseOfPostIncrementedValue())
+        OS << " (post-inc)";
+      OS << " in ";
+      UI->getUser()->print(OS);
+    }
+  }
+}
+
+void IVUsers::print(std::ostream &o, const Module *M) const {
+  raw_os_ostream OS(o);
+  print(OS, M);
+}
+
+void IVUsers::dump() const {
+  print(errs());
+}
+
+void IVUsers::releaseMemory() {
+  IVUsesByStride.clear();
+  StrideOrder.clear();
+  Processed.clear();
+}
+
+void IVStrideUse::deleted() {
+  // Remove this user from the list.
+  Parent->Users.erase(this);
+  // this now dangles!
+}
diff --git a/lib/Target/README.txt b/lib/Target/README.txt
index 538d1371a1..f68cf0e40d 100644
--- a/lib/Target/README.txt
+++ b/lib/Target/README.txt
@@ -749,16 +749,6 @@ be done safely if "b" isn't modified between the strlen and memcpy of course.
 
 //===---------------------------------------------------------------------===//
 
-We should be able to evaluate this loop:
-
-int test(int x_offs) {
-  while (x_offs > 4)
-     x_offs -= 4;
-  return x_offs;
-}
-
-//===---------------------------------------------------------------------===//
-
 Reassociate should turn things like:
 
 int factorial(int X) {
diff --git a/lib/Transforms/Scalar/IndVarSimplify.cpp b/lib/Transforms/Scalar/IndVarSimplify.cpp
index 3d9017d17e..80d34f6f16 100644
--- a/lib/Transforms/Scalar/IndVarSimplify.cpp
+++ b/lib/Transforms/Scalar/IndVarSimplify.cpp
@@ -43,6 +43,8 @@
 #include "llvm/Constants.h"
 #include "llvm/Instructions.h"
 #include "llvm/Type.h"
+#include "llvm/Analysis/Dominators.h"
+#include "llvm/Analysis/IVUsers.h"
 #include "llvm/Analysis/ScalarEvolutionExpander.h"
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Analysis/LoopPass.h"
@@ -51,11 +53,12 @@
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/GetElementPtrTypeIterator.h"
 #include "llvm/Transforms/Utils/Local.h"
+#include "llvm/Transforms/Utils/BasicBlockUtils.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/SetVector.h"
-#include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/Statistic.h"
+#include "llvm/ADT/STLExtras.h"
 using namespace llvm;
 
 STATISTIC(NumRemoved , "Number of aux indvars removed");
@@ -65,6 +68,7 @@ STATISTIC(NumLFTR    , "Number of loop exit tests replaced");
 
 namespace {
   class VISIBILITY_HIDDEN IndVarSimplify : public LoopPass {
+    IVUsers         *IU;
     LoopInfo        *LI;
     ScalarEvolution *SE;
     bool Changed;
@@ -76,12 +80,15 @@ namespace {
    virtual bool runOnLoop(Loop *L, LPPassManager &LPM);
 
    virtual void getAnalysisUsage(AnalysisUsage &AU) const {
+     AU.addRequired<DominatorTree>();
      AU.addRequired<ScalarEvolution>();
      AU.addRequiredID(LCSSAID);
      AU.addRequiredID(LoopSimplifyID);
      AU.addRequired<LoopInfo>();
+     AU.addRequired<IVUsers>();
      AU.addPreserved<ScalarEvolution>();
      AU.addPreservedID(LoopSimplifyID);
+     AU.addPreserved<IVUsers>();
      AU.addPreservedID(LCSSAID);
      AU.setPreservesCFG();
    }
@@ -90,17 +97,21 @@ namespace {
 
     void RewriteNonIntegerIVs(Loop *L);
 
-    void LinearFunctionTestReplace(Loop *L, SCEVHandle BackedgeTakenCount,
+    ICmpInst *LinearFunctionTestReplace(Loop *L, SCEVHandle BackedgeTakenCount,
                                    Value *IndVar,
                                    BasicBlock *ExitingBlock,
                                    BranchInst *BI,
                                    SCEVExpander &Rewriter);
     void RewriteLoopExitValues(Loop *L, const SCEV *BackedgeTakenCount);
 
-    void DeleteTriviallyDeadInstructions(SmallPtrSet<Instruction*, 16> &Insts);
+    void RewriteIVExpressions(Loop *L, const Type *LargestType,
+                              SCEVExpander &Rewriter);
 
-    void HandleFloatingPointIV(Loop *L, PHINode *PH,
-                               SmallPtrSet<Instruction*, 16> &DeadInsts);
+    void SinkUnusedInvariants(Loop *L, SCEVExpander &Rewriter);
+
+    void FixUsesBeforeDefs(Loop *L, SCEVExpander &Rewriter);
+
+    void HandleFloatingPointIV(Loop *L, PHINode *PH);
   };
 }
 
@@ -112,31 +123,12 @@ Pass *llvm::createIndVarSimplifyPass() {
   return new IndVarSimplify();
 }
 
-/// DeleteTriviallyDeadInstructions - If any of the instructions is the
-/// specified set are trivially dead, delete them and see if this makes any of
-/// their operands subsequently dead.
-void IndVarSimplify::
-DeleteTriviallyDeadInstructions(SmallPtrSet<Instruction*, 16> &Insts) {
-  while (!Insts.empty()) {
-    Instruction *I = *Insts.begin();
-    Insts.erase(I);
-    if (isInstructionTriviallyDead(I)) {
-      for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i)
-        if (Instruction *U = dyn_cast<Instruction>(I->getOperand(i)))
-          Insts.insert(U);
-      DOUT << "INDVARS: Deleting: " << *I;
-      I->eraseFromParent();
-      Changed = true;
-    }
-  }
-}
-
 /// LinearFunctionTestReplace - This method rewrites the exit condition of the
 /// loop to be a canonical != comparison against the incremented loop induction
 /// variable.  This pass is able to rewrite the exit tests of any loop where the
 /// SCEV analysis can determine a loop-invariant trip count of the loop, which
 /// is actually a much broader range than just linear tests.
-void IndVarSimplify::LinearFunctionTestReplace(Loop *L,
+ICmpInst *IndVarSimplify::LinearFunctionTestReplace(Loop *L,
                                    SCEVHandle BackedgeTakenCount,
                                    Value *IndVar,
                                    BasicBlock *ExitingBlock,
@@ -196,10 +188,15 @@ void IndVarSimplify::LinearFunctionTestReplace(Loop *L,
        << (Opcode == ICmpInst::ICMP_NE ? "!=" : "==") << "\n"
        << "      RHS:\t" << *RHS << "\n";
 
-  Value *Cond = new ICmpInst(Opcode, CmpIndVar, ExitCnt, "exitcond", BI);
-  BI->setCondition(Cond);
+  ICmpInst *Cond = new ICmpInst(Opcode, CmpIndVar, ExitCnt, "exitcond", BI);
+
+  Instruction *OrigCond = cast<Instruction>(BI->getCondition());
+  OrigCond->replaceAllUsesWith(Cond);
+  RecursivelyDeleteTriviallyDeadInstructions(OrigCond);
+
   ++NumLFTR;
   Changed = true;
+  return Cond;
 }
 
 /// RewriteLoopExitValues - Check to see if this loop has a computable
@@ -207,8 +204,16 @@ void IndVarSimplify::LinearFunctionTestReplace(Loop *L,
 /// final value of any expressions that are recurrent in the loop, and
 /// substitute the exit values from the loop into any instructions outside of
 /// the loop that use the final values of the current expressions.
+///
+/// This is mostly redundant with the regular IndVarSimplify activities that
+/// happen later, except that it's more powerful in some cases, because it's
+/// able to brute-force evaluate arbitrary instructions as long as they have
+/// constant operands at the beginning of the loop.
 void IndVarSimplify::RewriteLoopExitValues(Loop *L,
                                            const SCEV *BackedgeTakenCount) {
+  // Verify the input to the pass in already in LCSSA form.
+  assert(L->isLCSSAForm());
+
   BasicBlock *Preheader = L->getLoopPreheader();
 
   // Scan all of the instructions in the loop, looking at those that have
@@ -226,9 +231,6 @@ void IndVarSimplify::RewriteLoopExitValues(Loop *L,
     BlockToInsertInto = Preheader;
   BasicBlock::iterator InsertPt = BlockToInsertInto->getFirstNonPHI();
 
-  bool HasConstantItCount = isa<SCEVConstant>(BackedgeTakenCount);
-
-  SmallPtrSet<Instruction*, 16> InstructionsToDelete;
   std::map<Instruction*, Value*> ExitValues;
 
   // Find all values that are computed inside the loop, but used outside of it.
@@ -268,18 +270,11 @@ void IndVarSimplify::RewriteLoopExitValues(Loop *L,
         if (!L->contains(Inst->getParent()))
           continue;
 
-        // We require that this value either have a computable evolution or that
-        // the loop have a constant iteration count.  In the case where the loop
-        // has a constant iteration count, we can sometimes force evaluation of
-        // the exit value through brute force.
-        SCEVHandle SH = SE->getSCEV(Inst);
-        if (!SH->hasComputableLoopEvolution(L) && !HasConstantItCount)
-          continue;          // Cannot get exit evolution for the loop value.
-
         // Okay, this instruction has a user outside of the current loop
         // and varies predictably *inside* the loop.  Evaluate the value it
         // contains when the loop exits, if possible.
-        SCEVHandle ExitValue = SE->getSCEVAtScope(Inst, L->getParentLoop());
+        SCEVHandle SH = SE->getSCEV(Inst);
+        SCEVHandle ExitValue = SE->getSCEVAtScope(SH, L->getParentLoop());
         if (isa<SCEVCouldNotCompute>(ExitValue) ||
             !ExitValue->isLoopInvariant(L))
           continue;
@@ -298,9 +293,8 @@ void IndVarSimplify::RewriteLoopExitValues(Loop *L,
 
         PN->setIncomingValue(i, ExitVal);
 
-        // If this instruction is dead now, schedule it to be removed.
-        if (Inst->use_empty())
-          InstructionsToDelete.insert(Inst);
+        // If this instruction is dead now, delete it.
+        RecursivelyDeleteTriviallyDeadInstructions(Inst);
 
         // See if this is a single-entry LCSSA PHI node.  If so, we can (and
         // have to) remove
@@ -308,14 +302,12 @@ void IndVarSimplify::RewriteLoopExitValues(Loop *L,
         // in the loop, so we don't need an LCSSA phi node anymore.
         if (NumPreds == 1) {
           PN->replaceAllUsesWith(ExitVal);
-          PN->eraseFromParent();
+          RecursivelyDeleteTriviallyDeadInstructions(PN);
           break;
         }
       }
     }
   }
-
-  DeleteTriviallyDeadInstructions(InstructionsToDelete);
 }
 
 void IndVarSimplify::RewriteNonIntegerIVs(Loop *L) {
@@ -325,266 +317,24 @@ void IndVarSimplify::RewriteNonIntegerIVs(Loop *L) {
   //
   BasicBlock *Header    = L->getHeader();