Factor the code for collecting IV users out of LSR into an IVUsers class,

and generalize it so that it can be used by IndVarSimplify. Implement the
base IndVarSimplify transformation code using IVUsers. This removes
TestOrigIVForWrap and associated code, as ScalarEvolution now has enough
builtin overflow detection and folding logic to handle all the same cases,
and more. Run "opt -iv-users -analyze -disable-output" on your favorite
loop for an example of what IVUsers does.

This lets IndVarSimplify eliminate IV casts and compute trip counts in
more cases. Also, this happens to finally fix the remaining testcases
in PR1301.

Now that IndVarSimplify is being more aggressive, it occasionally runs
into the problem where ScalarEvolutionExpander's code for avoiding
duplicate expansions makes it difficult to ensure that all expanded
instructions dominate all the instructions that will use them. As a
temporary measure, IndVarSimplify now uses a FixUsesBeforeDefs function
to fix up instructions inserted by SCEVExpander. Fortunately, this code
is contained, and can be easily removed once a more comprehensive
solution is available.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@71535 91177308-0d34-0410-b5e6-96231b3b80d8

1 files changed, 369 insertions, 566 deletions

diff --git a/lib/Transforms/Scalar/IndVarSimplify.cpp b/lib/Transforms/Scalar/IndVarSimplify.cpp
index 3d9017d..80d34f6 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();
 
-  SmallPtrSet<Instruction*, 16> DeadInsts;
-  for (BasicBlock::iterator I = Header->begin(); isa<PHINode>(I); ++I) {
-    PHINode *PN = cast<PHINode>(I);
-    HandleFloatingPointIV(L, PN, DeadInsts);
-  }
+  SmallVector<WeakVH, 8> PHIs;
+  for (BasicBlock::iterator I = Header->begin();
+       PHINode *PN = dyn_cast<PHINode>(I); ++I)
+    PHIs.push_back(PN);
+
+  for (unsigned i = 0, e = PHIs.size(); i != e; ++i)
+    if (PHINode *PN = dyn_cast_or_null<PHINode>(PHIs[i]))
+      HandleFloatingPointIV(L, PN);
 
   // If the loop previously had floating-point IV, ScalarEvolution
   // may not have been able to compute a trip count. Now that we've done some
   // re-writing, the trip count may be computable.
   if (Changed)
     SE->forgetLoopBackedgeTakenCount(L);
-
-  if (!DeadInsts.empty())
-    DeleteTriviallyDeadInstructions(DeadInsts);
-}
-
-/// getEffectiveIndvarType - Determine the widest type that the
-/// induction-variable PHINode Phi is cast to.
-///
-static const Type *getEffectiveIndvarType(const PHINode *Phi,
-                                          const ScalarEvolution *SE) {
-  const Type *Ty = Phi->getType();
-
-  for (Value::use_const_iterator UI = Phi->use_begin(), UE = Phi->use_end();
-       UI != UE; ++UI) {
-    const Type *CandidateType = NULL;
-    if (const ZExtInst *ZI = dyn_cast<ZExtInst>(UI))
-      CandidateType = ZI->getDestTy();
-    else if (const SExtInst *SI = dyn_cast<SExtInst>(UI))
-      CandidateType = SI->getDestTy();
-    else if (const IntToPtrInst *IP = dyn_cast<IntToPtrInst>(UI))
-      CandidateType = IP->getDestTy();
-    else if (const PtrToIntInst *PI = dyn_cast<PtrToIntInst>(UI))
-      CandidateType = PI->getDestTy();
-    if (CandidateType &&
-        SE->isSCEVable(CandidateType) &&
-        SE->getTypeSizeInBits(CandidateType) > SE->getTypeSizeInBits(Ty))
-      Ty = CandidateType;
-  }
-
-  return Ty;
-}
-
-/// TestOrigIVForWrap - Analyze the original induction variable that
-/// controls the loop's iteration to determine whether it would ever
-/// undergo signed or unsigned overflow.
-///
-/// In addition to setting the NoSignedWrap and NoUnsignedWrap
-/// variables to true when appropriate (they are not set to false here),
-/// return the PHI for this induction variable.  Also record the initial
-/// and final values and the increment; these are not meaningful unless
-/// either NoSignedWrap or NoUnsignedWrap is true, and are always meaningful
-/// in that case, although the final value may be 0 indicating a nonconstant.
-///
-/// TODO: This duplicates a fair amount of ScalarEvolution logic.
-/// Perhaps this can be merged with
-/// ScalarEvolution::getBackedgeTakenCount
-/// and/or ScalarEvolution::get{Sign,Zero}ExtendExpr.
-///
-static const PHINode *TestOrigIVForWrap(const Loop *L,
-                                        const BranchInst *BI,
-                                        const Instruction *OrigCond,
-                                        const ScalarEvolution &SE,
-                                        bool &NoSignedWrap,
-                                        bool &NoUnsignedWrap,
-                                        const ConstantInt* &InitialVal,
-                                        const ConstantInt* &IncrVal,
-                                        const ConstantInt* &LimitVal) {
-  // Verify that the loop is sane and find the exit condition.
-  const ICmpInst *Cmp = dyn_cast<ICmpInst>(OrigCond);
-  if (!Cmp) return 0;
-
-  const Value *CmpLHS = Cmp->getOperand(0);
-  const Value *CmpRHS = Cmp->getOperand(1);
-  const BasicBlock *TrueBB = BI->getSuccessor(0);
-  const BasicBlock *FalseBB = BI->getSuccessor(1);
-  ICmpInst::Predicate Pred = Cmp->getPredicate();
-
-  // Canonicalize a constant to the RHS.
-  if (isa<ConstantInt>(CmpLHS)) {
-    Pred = ICmpInst::getSwappedPredicate(Pred);
-    std::swap(CmpLHS, CmpRHS);
-  }
-  // Canonicalize SLE to SLT.
-  if (Pred == ICmpInst::ICMP_SLE)
-    if (const ConstantInt *CI = dyn_cast<ConstantInt>(CmpRHS))
-      if (!CI->getValue().isMaxSignedValue()) {
-        CmpRHS = ConstantInt::get(CI->getValue() + 1);
-        Pred = ICmpInst::ICMP_SLT;
-      }
-  // Canonicalize SGT to SGE.
-  if (Pred == ICmpInst::ICMP_SGT)
-    if (const ConstantInt *CI = dyn_cast<ConstantInt>(CmpRHS))
-      if (!CI->getValue().isMaxSignedValue()) {
-        CmpRHS = ConstantInt::get(CI->getValue() + 1);
-        Pred = ICmpInst::ICMP_SGE;
-      }
-  // Canonicalize SGE to SLT.
-  if (Pred == ICmpInst::ICMP_SGE) {
-    std::swap(TrueBB, FalseBB);
-    Pred = ICmpInst::ICMP_SLT;
-  }
-  // Canonicalize ULE to ULT.
-  if (Pred == ICmpInst::ICMP_ULE)
-    if (const ConstantInt *CI = dyn_cast<ConstantInt>(CmpRHS))
-      if (!CI->getValue().isMaxValue()) {
-        CmpRHS = ConstantInt::get(CI->getValue() + 1);
-        Pred = ICmpInst::ICMP_ULT;
-      }
-  // Canonicalize UGT to UGE.
-  if (Pred == ICmpInst::ICMP_UGT)
-    if (const ConstantInt *CI = dyn_cast<ConstantInt>(CmpRHS))
-      if (!CI->getValue().isMaxValue()) {
-        CmpRHS = ConstantInt::get(CI->getValue() + 1);
-        Pred = ICmpInst::ICMP_UGE;
-      }
-  // Canonicalize UGE to ULT.
-  if (Pred == ICmpInst::ICMP_UGE) {
-    std::swap(TrueBB, FalseBB);
-    Pred = ICmpInst::ICMP_ULT;
-  }
-  // For now, analyze only LT loops for signed overflow.
-  if (Pred != ICmpInst::ICMP_SLT && Pred != ICmpInst::ICMP_ULT)
-    return 0;
-
-  bool isSigned = Pred == ICmpInst::ICMP_SLT;
-
-  // Get the increment instruction. Look past casts if we will
-  // be able to prove that the original induction variable doesn't
-  // undergo signed or unsigned overflow, respectively.
-  const Value *IncrInst = CmpLHS;
-  if (isSigned) {
-    if (const SExtInst *SI = dyn_cast<SExtInst>(CmpLHS)) {
-      if (!isa<ConstantInt>(CmpRHS) ||
-          !cast<ConstantInt>(CmpRHS)->getValue()
-            .isSignedIntN(SE.getTypeSizeInBits(IncrInst->getType())))
-        return 0;
-      IncrInst = SI->getOperand(0);
-    }
-  } else {
-    if (const ZExtInst *ZI = dyn_cast<ZExtInst>(CmpLHS)) {
-      if (!isa<ConstantInt>(CmpRHS) ||
-          !cast<ConstantInt>(CmpRHS)->getValue()
-            .isIntN(SE.getTypeSizeInBits(IncrInst->getType())))
-        return 0;
-      IncrInst = ZI->getOperand(0);
-    }
-  }
-
-  // For now, only analyze induction variables that have simple increments.
-  const BinaryOperator *IncrOp = dyn_cast<BinaryOperator>(IncrInst);
-  if (!IncrOp || IncrOp->getOpcode() != Instruction::Add)
-    return 0;
-  IncrVal = dyn_cast<ConstantInt>(IncrOp->getOperand(1));
-  if (!IncrVal)
-    return 0;
-
-  // Make sure the PHI looks like a normal IV.
-  const PHINode *PN = dyn_cast<PHINode>(IncrOp->getOperand(0));
-  if (!PN || PN->getNumIncomingValues() != 2)
-    return 0;
-  unsigned IncomingEdge = L->contains(PN->getIncomingBlock(0));
-  unsigned BackEdge = !IncomingEdge;
-  if (!L->contains(PN->getIncomingBlock(BackEdge)) ||
-      PN->getIncomingValue(BackEdge) != IncrOp)
-    return 0;
-  if (!L->contains(TrueBB))
-    return 0;
-
-  // For now, only analyze loops with a constant start value, so that
-  // we can easily determine if the start value is not a maximum value
-  // which would wrap on the first iteration.
-  InitialVal = dyn_cast<ConstantInt>(PN->getIncomingValue(IncomingEdge));
-  if (!InitialVal)
-    return 0;
-
-  // The upper limit need not be a constant; we'll check later.
-  LimitVal = dyn_cast<ConstantInt>(CmpRHS);
-
-  // We detect the impossibility of wrapping in two cases, both of
-  // which require starting with a non-max value:
-  // - The IV counts up by one, and the loop iterates only while it remains
-  // less than a limiting value (any) in the same type.
-  // - The IV counts up by a positive increment other than 1, and the
-  // constant limiting value + the increment is less than the max value
-  // (computed as max-increment to avoid overflow)
-  if (isSigned && !InitialVal->getValue().isMaxSignedValue()) {
-    if (IncrVal->equalsInt(1))
-      NoSignedWrap = true;    // LimitVal need not be constant
-    else if (LimitVal) {
-      uint64_t numBits = LimitVal->getValue().getBitWidth();
-      if (IncrVal->getValue().sgt(APInt::getNullValue(numBits)) &&
-          (APInt::getSignedMaxValue(numBits) - IncrVal->getValue())
-            .sgt(LimitVal->getValue()))
-        NoSignedWrap = true;
-    }
-  } else if (!isSigned && !InitialVal->getValue().isMaxValue()) {
-    if (IncrVal->equalsInt(1))
-      NoUnsignedWrap = true;  // LimitVal need not be constant
-    else if (LimitVal) {
-      uint64_t numBits = LimitVal->getValue().getBitWidth();
-      if (IncrVal->getValue().ugt(APInt::getNullValue(numBits)) &&
-          (APInt::getMaxValue(numBits) - IncrVal->getValue())
-            .ugt(LimitVal->getValue()))
-        NoUnsignedWrap = true;
-    }
-  }
-  return PN;
-}
-
-static Value *getSignExtendedTruncVar(const SCEVAddRecExpr *AR,
-                                      ScalarEvolution *SE,
-                                      const Type *LargestType, Loop *L, 
-                                      const Type *myType,
-                                      SCEVExpander &Rewriter) {
-  SCEVHandle ExtendedStart =
-    SE->getSignExtendExpr(AR->getStart(), LargestType);
-  SCEVHandle ExtendedStep =
-    SE->getSignExtendExpr(AR->getStepRecurrence(*SE), LargestType);
-  SCEVHandle ExtendedAddRec =
-    SE->getAddRecExpr(ExtendedStart, ExtendedStep, L);
-  if (LargestType != myType)
-    ExtendedAddRec = SE->getTruncateExpr(ExtendedAddRec, myType);
-  return Rewriter.expandCodeFor(ExtendedAddRec, myType);
-}
-
-static Value *getZeroExtendedTruncVar(const SCEVAddRecExpr *AR,
-                                      ScalarEvolution *SE,
-                                      const Type *LargestType, Loop *L, 
-                                      const Type *myType,
-                                      SCEVExpander &Rewriter) {
-  SCEVHandle ExtendedStart =
-    SE->getZeroExtendExpr(AR->getStart(), LargestType);
-  SCEVHandle ExtendedStep =
-    SE->getZeroExtendExpr(AR->getStepRecurrence(*SE), LargestType);
-  SCEVHandle ExtendedAddRec =
-    SE->getAddRecExpr(ExtendedStart, ExtendedStep, L);
-  if (LargestType != myType)
-    ExtendedAddRec = SE->getTruncateExpr(ExtendedAddRec, myType);
-  return Rewriter.expandCodeFor(ExtendedAddRec, myType);
-}
-
-/// allUsesAreSameTyped - See whether all Uses of I are instructions
-/// with the same Opcode and the same type.
-static bool allUsesAreSameTyped(unsigned int Opcode, Instruction *I) {
-  const Type* firstType = NULL;
-  for (Value::use_iterator UI = I->use_begin(), UE = I->use_end();
-       UI != UE; ++UI) {
-    Instruction *II = dyn_cast<Instruction>(*UI);
-    if (!II || II->getOpcode() != Opcode)
-      return false;
-    if (!firstType)
-      firstType = II->getType();
-    else if (firstType != II->getType())
-      return false;
-  }
-  return true;
 }
 
 bool IndVarSimplify::runOnLoop(Loop *L, LPPassManager &LPM) {
+  IU = &getAnalysis<IVUsers>();
   LI = &getAnalysis<LoopInfo>();
   SE = &getAnalysis<ScalarEvolution>();
   Changed = false;
@@ -594,11 +344,8 @@ bool IndVarSimplify::runOnLoop(Loop *L, LPPassManager &LPM) {
   RewriteNonIntegerIVs(L);
 
   BasicBlock *Header       = L->getHeader();
-  BasicBlock *ExitingBlock = L->getExitingBlock();
-  SmallPtrSet<Instruction*, 16> DeadInsts;
-
-  // Verify the input to the pass in already in LCSSA form.
-  assert(L->isLCSSAForm());
+  BasicBlock *ExitingBlock = L->getExitingBlock(); // may be null
+  SCEVHandle BackedgeTakenCount = SE->getBackedgeTakenCount(L);
 
   // Check to see if this loop has a computable loop-invariant execution count.
   // If so, this means that we can compute the final value of any expressions
@@ -606,59 +353,45 @@ bool IndVarSimplify::runOnLoop(Loop *L, LPPassManager &LPM) {
   // loop into any instructions outside of the loop that use the final values of
   // the current expressions.
   //
-  SCEVHandle BackedgeTakenCount = SE->getBackedgeTakenCount(L);
   if (!isa<SCEVCouldNotCompute>(BackedgeTakenCount))
     RewriteLoopExitValues(L, BackedgeTakenCount);
 
-  // Next, analyze all of the induction variables in the loop, canonicalizing
-  // auxillary induction variables.
-  std::vector<std::pair<PHINode*, SCEVHandle> > IndVars;
-
-  for (BasicBlock::iterator I = Header->begin(); isa<PHINode>(I); ++I) {
-    PHINode *PN = cast<PHINode>(I);
-    if (SE->isSCEVable(PN->getType())) {
-      SCEVHandle SCEV = SE->getSCEV(PN);
-      // 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
-      // currently can only reduce affine polynomials.  For now just disable
-      // indvar subst on anything more complex than an affine addrec.
-      if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(SCEV))
-        if (AR->getLoop() == L && AR->isAffine())
-          IndVars.push_back(std::make_pair(PN, SCEV));
-    }
-  }
-
-  // Compute the type of the largest recurrence expression, and collect
-  // the set of the types of the other recurrence expressions.
+  // Compute the type of the largest recurrence expression, and decide whether
+  // a canonical induction variable should be inserted.
   const Type *LargestType = 0;
-  SmallSetVector<const Type *, 4> SizesToInsert;
+  bool NeedCannIV = false;
   if (!isa<SCEVCouldNotCompute>(BackedgeTakenCount)) {
     LargestType = BackedgeTakenCount->getType();
     LargestType = SE->getEffectiveSCEVType(LargestType);
-    SizesToInsert.insert(LargestType);
+    // If we have a known trip count and a single exit block, we'll be
+    // rewriting the loop exit test condition below, which requires a
+    // canonical induction variable.
+    if (ExitingBlock)
+      NeedCannIV = true;
   }
-  for (unsigned i = 0, e = IndVars.size(); i != e; ++i) {
-    const PHINode *PN = IndVars[i].first;
-    const Type *PNTy = PN->getType();
-    PNTy = SE->getEffectiveSCEVType(PNTy);
-    SizesToInsert.insert(PNTy);
-    const Type *EffTy = getEffectiveIndvarType(PN, SE);
-    EffTy = SE->getEffectiveSCEVType(EffTy);
-    SizesToInsert.insert(EffTy);
+  for (unsigned i = 0, e = IU->StrideOrder.size(); i != e; ++i) {
+    SCEVHandle Stride = IU->StrideOrder[i];
+    const Type *Ty = SE->getEffectiveSCEVType(Stride->getType());
     if (!LargestType ||
-        SE->getTypeSizeInBits(EffTy) >
+        SE->getTypeSizeInBits(Ty) >
           SE->getTypeSizeInBits(LargestType))
-      LargestType = EffTy;
+      LargestType = Ty;
+
+    std::map<SCEVHandle, IVUsersOfOneStride *>::iterator SI =
+      IU->IVUsesByStride.find(IU->StrideOrder[i]);
+    assert(SI != IU->IVUsesByStride.end() && "Stride doesn't exist!");
+
+    if (!SI->second->Users.empty())
+      NeedCannIV = true;
   }
 
   // Create a rewriter object which we'll use to transform the code with.
   SCEVExpander Rewriter(*SE, *LI);
 
-  // Now that we know the largest of of the induction variables in this loop,
-  // insert a canonical induction variable of the largest size.
+  // Now that we know the largest of of the induction variable expressions
+  // in this loop, insert a canonical induction variable of the largest size.
   Value *IndVar = 0;
-  if (!SizesToInsert.empty()) {
+  if (NeedCannIV) {
     IndVar = Rewriter.getOrInsertCanonicalInductionVariable(L,LargestType);
     ++NumInserted;
     Changed = true;
@@ -667,229 +400,291 @@ bool IndVarSimplify::runOnLoop(Loop *L, LPPassManager &LPM) {
 
   // If we have a trip count expression, rewrite the loop's exit condition
   // using it.  We can currently only handle loops with a single exit.
-  bool NoSignedWrap = false;
-  bool NoUnsignedWrap = false;
-  const ConstantInt* InitialVal, * IncrVal, * LimitVal;
-  const PHINode *OrigControllingPHI = 0;
-  if (!isa<SCEVCouldNotCompute>(BackedgeTakenCount) && ExitingBlock)
+  ICmpInst *NewICmp = 0;
+  if (!isa<SCEVCouldNotCompute>(BackedgeTakenCount) && ExitingBlock) {
+    assert(NeedCannIV &&
+           "LinearFunctionTestReplace requires a canonical induction variable");
     // Can't rewrite non-branch yet.
-    if (BranchInst *BI = dyn_cast<BranchInst>(ExitingBlock->getTerminator())) {
-      if (Instruction *OrigCond = dyn_cast<Instruction>(BI->getCondition())) {
-        // Determine if the OrigIV will ever undergo overflow.
-        OrigControllingPHI =
-          TestOrigIVForWrap(L, BI, OrigCond, *SE,
-                            NoSignedWrap, NoUnsignedWrap,
-                            InitialVal, IncrVal, LimitVal);
-
-        // We'll be replacing the original condition, so it'll be dead.
-        DeadInsts.insert(OrigCond);
-      }
+    if (BranchInst *BI = dyn_cast<BranchInst>(ExitingBlock->getTerminator()))
+      NewICmp = LinearFunctionTestReplace(L, BackedgeTakenCount, IndVar,
+                                          ExitingBlock, BI, Rewriter);
+  }
 
-      LinearFunctionTestReplace(L, BackedgeTakenCount, IndVar,
-                                ExitingBlock, BI, Rewriter);
-    }
+  Rewriter.setInsertionPoint(Header->getFirstNonPHI());
 
-  // Now that we have a canonical induction variable, we can rewrite any
-  // recurrences in terms of the induction variable.  Start with the auxillary
-  // induction variables, and recursively rewrite any of their uses.
-  BasicBlock::iterator InsertPt = Header->getFirstNonPHI();
-  Rewriter.setInsertionPoint(InsertPt);
-
-  // If there were induction variables of other sizes, cast the primary
-  // induction variable to the right size for them, avoiding the need for the
-  // code evaluation methods to insert induction variables of different sizes.
-  for (unsigned i = 0, e = SizesToInsert.size(); i != e; ++i) {
-    const Type *Ty = SizesToInsert[i];
-    if (Ty != LargestType) {
-      Instruction *New = new TruncInst(IndVar, Ty, "indvar", InsertPt);
-      Rewriter.addInsertedValue(New, SE->getSCEV(New));
-      DOUT << "INDVARS: Made trunc IV for type " << *Ty << ": "
-           << *New << "\n";
-    }
-  }
+  // Rewrite IV-derived expressions.
+  RewriteIVExpressions(L, LargestType, Rewriter);
 
-  // Rewrite all induction variables in terms of the canonical induction
-  // variable.
-  while (!IndVars.empty()) {
-    PHINode *PN = IndVars.back().first;
-    const SCEVAddRecExpr *AR = cast<SCEVAddRecExpr>(IndVars.back().second);
-    Value *NewVal = Rewriter.expandCodeFor(AR, PN->getType());
-    DOUT << "INDVARS: Rewrote IV '" << *AR << "' " << *PN
-         << "   into = " << *NewVal << "\n";
-    NewVal->takeName(PN);
-
-    /// If the new canonical induction variable is wider than the original,
-    /// and the original has uses that are casts to wider types, see if the
-    /// truncate and extend can be omitted.
-    if (PN == OrigControllingPHI && PN->getType() != LargestType)
-      for (Value::use_iterator UI = PN->use_begin(), UE = PN->use_end();
-           UI != UE; ++UI) {
-        Instruction *UInst = dyn_cast<Instruction>(*UI);
-        if (UInst && isa<SExtInst>(UInst) && NoSignedWrap) {
-          Value *TruncIndVar = getSignExtendedTruncVar(AR, SE, LargestType, L, 
-                                         UInst->getType(), Rewriter);
-          UInst->replaceAllUsesWith(TruncIndVar);
-          DeadInsts.insert(UInst);
-        }
-        // See if we can figure out sext(i+constant) doesn't wrap, so we can
-        // use a larger add.  This is common in subscripting.
-        if (UInst && UInst->getOpcode()==Instruction::Add &&
-            !UInst->use_empty() &&
-            allUsesAreSameTyped(Instruction::SExt, UInst) &&
-            isa<ConstantInt>(UInst->getOperand(1)) &&
-            NoSignedWrap && LimitVal) {
-          uint64_t oldBitSize = LimitVal->getValue().getBitWidth();
-          uint64_t newBitSize = LargestType->getPrimitiveSizeInBits();
-          ConstantInt* AddRHS = dyn_cast<ConstantInt>(UInst->getOperand(1));
-          if (((APInt::getSignedMaxValue(oldBitSize) - IncrVal->getValue()) -
-                AddRHS->getValue()).sgt(LimitVal->getValue())) {
-            // We've determined this is (i+constant) and it won't overflow.
-            if (isa<SExtInst>(UInst->use_begin())) {
-              SExtInst* oldSext = dyn_cast<SExtInst>(UInst->use_begin());
-              uint64_t truncSize = oldSext->getType()->getPrimitiveSizeInBits();
-              Value *TruncIndVar = getSignExtendedTruncVar(AR, SE, LargestType,
-                                                L, oldSext->getType(), Rewriter);
-              APInt APnewAddRHS = APInt(AddRHS->getValue()).sext(newBitSize);
-              if (newBitSize > truncSize)
-                APnewAddRHS = APnewAddRHS.trunc(truncSize);
-              ConstantInt* newAddRHS =ConstantInt::get(APnewAddRHS);
-              Value *NewAdd = 
-                    BinaryOperator::CreateAdd(TruncIndVar, newAddRHS,
-                                              UInst->getName()+".nosex", UInst);
-              for (Value::use_iterator UI2 = UInst->use_begin(), 
-                    UE2 = UInst->use_end(); UI2 != UE2; ++UI2) {
-                Instruction *II = dyn_cast<Instruction>(UI2);
-                II->replaceAllUsesWith(NewAdd);
-                DeadInsts.insert(II);
-              }
-              DeadInsts.insert(UInst);
-            }
-          }
-        }
-        // Try for sext(i | constant).  This is safe as long as the
-        // high bit of the constant is not set.
-        if (UInst && UInst->getOpcode()==Instruction::Or &&
-            !UInst->use_empty() &&
-            allUsesAreSameTyped(Instruction::SExt, UInst) && NoSignedWrap &&
-            isa<ConstantInt>(UInst->getOperand(1))) {
-          ConstantInt* RHS = dyn_cast<ConstantInt>(UInst->getOperand(1));
-          if (!RHS->getValue().isNegative()) {
-            uint64_t newBitSize = LargestType->getPrimitiveSizeInBits();
-            SExtInst* oldSext = dyn_cast<SExtInst>(UInst->use_begin());
-            uint64_t truncSize = oldSext->getType()->getPrimitiveSizeInBits();
-            Value *TruncIndVar = getSignExtendedTruncVar(AR, SE, LargestType,
-                                              L, oldSext->getType(), Rewriter);
-            APInt APnewOrRHS = APInt(RHS->getValue()).sext(newBitSize);
-            if (newBitSize > truncSize)
-              APnewOrRHS = APnewOrRHS.trunc(truncSize);
-            ConstantInt* newOrRHS =ConstantInt::get(APnewOrRHS);
-            Value *NewOr = 
-                  BinaryOperator::CreateOr(TruncIndVar, newOrRHS,
-                                            UInst->getName()+".nosex", UInst);
-            for (Value::use_iterator UI2 = UInst->use_begin(), 
-                  UE2 = UInst->use_end(); UI2 != UE2; ++UI2) {
-              Instruction *II = dyn_cast<Instruction>(UI2);
-              II->replaceAllUsesWith(NewOr);
-              DeadInsts.insert(II);
-            }
-            DeadInsts.insert(UInst);
-          }
-        }
-        // A zext of a signed variable known not to overflow is still safe.
-        if (UInst && isa<ZExtInst>(UInst) && (NoUnsignedWrap || NoSignedWrap)) {
-          Value *TruncIndVar = getZeroExtendedTruncVar(AR, SE, LargestType, L, 
-                                         UInst->getType(), Rewriter);
-          UInst->replaceAllUsesWith(TruncIndVar);
-          DeadInsts.insert(UInst);
-        }
-        // If we have zext(i&constant), it's always safe to use the larger
-        // variable.  This is not common but is a bottleneck in Openssl.
-        // (RHS doesn't have to be constant.  There should be a better approach
-        // than bottom-up pattern matching for this...)
-        if (UInst && UInst->getOpcode()==Instruction::And &&
-            !UInst->use_empty() &&
-            allUsesAreSameTyped(Instruction::ZExt, UInst) &&
-            isa<ConstantInt>(UInst->getOperand(1))) {
-          uint64_t newBitSize = LargestType->getPrimitiveSizeInBits();
-          ConstantInt* AndRHS = dyn_cast<ConstantInt>(UInst->getOperand(1));
-          ZExtInst* oldZext = dyn_cast<ZExtInst>(UInst->use_begin());
-          uint64_t truncSize = oldZext->getType()->getPrimitiveSizeInBits();
-          Value *TruncIndVar = getSignExtendedTruncVar(AR, SE, LargestType,
-                                  L, oldZext->getType(), Rewriter);
-          APInt APnewAndRHS = APInt(AndRHS->getValue()).zext(newBitSize);
-          if (newBitSize > truncSize)
-            APnewAndRHS = APnewAndRHS.trunc(truncSize);
-          ConstantInt* newAndRHS = ConstantInt::get(APnewAndRHS);
-          Value *NewAnd = 
-                BinaryOperator::CreateAnd(TruncIndVar, newAndRHS,
-                                          UInst->getName()+".nozex", UInst);
-          for (Value::use_iterator UI2 = UInst->use_begin(), 
-                UE2 = UInst->use_end(); UI2 != UE2; ++UI2) {
-            Instruction *II = dyn_cast<Instruction>(UI2);
-            II->replaceAllUsesWith(NewAnd);
-            DeadInsts.insert(II);
+  // Loop-invariant instructions in the preheader that aren't used in the
+  // loop may be sunk below the loop to reduce register pressure.
+  SinkUnusedInvariants(L, Rewriter);
+
+  // Reorder instructions to avoid use-before-def conditions.
+  FixUsesBeforeDefs(L, Rewriter);
+
+  // For completeness, inform IVUsers of the IV use in the newly-created
+  // loop exit test instruction.
+  if (NewICmp)
+    IU->AddUsersIfInteresting(cast<Instruction>(NewICmp->getOperand(0)));
+
+  // Clean up dead instructions.
+  DeleteDeadPHIs(L->getHeader());
+  // Check a post-condition.
+  assert(L->isLCSSAForm() && "Indvars did not leave the loop in lcssa form!");
+  return Changed;
+}
+
+void IndVarSimplify::RewriteIVExpressions(Loop *L, const Type *LargestType,
+                                          SCEVExpander &Rewriter) {
+  SmallVector<WeakVH, 16> DeadInsts;
+
+  // Rewrite all induction variable expressions in terms of the canonical
+  // induction variable.
+  //
+  // If there were induction variables of other sizes or offsets, manually
+  // add the offsets to the primary induction variable and cast, avoiding
+  // the need for the code evaluation methods to insert induction variables
+  // of different sizes.
+  for (unsigned i = 0, e = IU->StrideOrder.size(); i != e; ++i) {
+    SCEVHandle Stride = IU->StrideOrder[i];
+
+    std::map<SCEVHandle, IVUsersOfOneStride *>::iterator SI =
+      IU->IVUsesByStride.find(IU->StrideOrder[i]);
+    assert(SI != IU->IVUsesByStride.end() && "Stride doesn't exist!");
+    ilist<IVStrideUse> &List = SI->second->Users;
+    for (ilist<IVStrideUse>::iterator UI = List.begin(),
+         E = List.end(); UI != E; ++UI) {
+      SCEVHandle Offset = UI->getOffset();
+      Value *Op = UI->getOperandValToReplace();
+      Instruction *User = UI->getUser();
+      bool isSigned = UI->isSigned();
+
+      // Compute the final addrec to expand into code.
+      SCEVHandle AR = IU->getReplacementExpr(*UI);
+
+      // 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
+      // currently can only reduce affine polynomials.  For now just disable
+      // indvar subst on anything more complex than an affine addrec, unless
+      // it can be expanded to a trivial value.
+      if (!Stride->isLoopInvariant(L) &&
+          !isa<SCEVConstant>(AR) &&
+          L->contains(User->getParent()))
+        continue;
+
+      Value *NewVal = 0;
+      if (AR->isLoopInvariant(L)) {
+        BasicBlock::iterator I = Rewriter.getInsertionPoint();
+        // Expand loop-invariant values in the loop preheader. They will
+        // be sunk to the exit block later, if possible.
+          NewVal =
+          Rewriter.expandCodeFor(AR, LargestType,
+                                 L->getLoopPreheader()->getTerminator());
+        Rewriter.setInsertionPoint(I);
+        ++NumReplaced;
+      } else {
+        const Type *IVTy = Offset->getType();
+        const Type *UseTy = Op->getType();
+
+        // Promote the Offset and Stride up to the canonical induction
+        // variable's bit width.
+        SCEVHandle PromotedOffset = Offset;
+        SCEVHandle PromotedStride = Stride;
+        if (SE->getTypeSizeInBits(IVTy) != SE->getTypeSizeInBits(LargestType)) {
+          // It doesn't matter for correctness whether zero or sign extension
+          // is used here, since the value is truncated away below, but if the
+          // value is signed, sign extension is more likely to be folded.
+          if (isSigned) {
+            PromotedOffset = SE->getSignExtendExpr(PromotedOffset, LargestType);
+            PromotedStride = SE->getSignExtendExpr(PromotedStride, LargestType);
+          } else {
+            PromotedOffset = SE->getZeroExtendExpr(PromotedOffset, LargestType);
+            // If the stride is obviously negative, use sign extension to
+            // produce things like x-1 instead of x+255.
+            if (isa<SCEVConstant>(PromotedStride) &&
+                cast<SCEVConstant>(PromotedStride)
+                  ->getValue()->getValue().isNegative())
+              PromotedStride = SE->getSignExtendExpr(PromotedStride,
+                                                     LargestType);
+            else
+              PromotedStride = SE->getZeroExtendExpr(PromotedStride,
+                                                     LargestType);
           }
-          DeadInsts.insert(UInst);
         }
-        // If we have zext((i+constant)&constant), we can use the larger
-        // variable even if the add does overflow.  This works whenever the
-        // constant being ANDed is the same size as i, which it presumably is.
-        // We don't need to restrict the expression being and'ed to i+const,
-        // but we have to promote everything in it, so it's convenient.
-        // zext((i | constant)&constant) is also valid and accepted here.
-        if (UInst && (UInst->getOpcode()==Instruction::Add ||
-                      UInst->getOpcode()==Instruction::Or) &&
-            UInst->hasOneUse() &&
-            isa<ConstantInt>(UInst->getOperand(1))) {
-          uint64_t newBitSize = LargestType->getPrimitiveSizeInBits();
-          ConstantInt* AddRHS = dyn_cast<ConstantInt>(UInst->getOperand(1));
-          Instruction *UInst2 = dyn_cast<Instruction>(UInst->use_begin());
-          if (UInst2 && UInst2->getOpcode() == Instruction::And &&
-              !UInst2->use_empty() &&
-              allUsesAreSameTyped(Instruction::ZExt, UInst2) &&
-              isa<ConstantInt>(UInst2->getOperand(1))) {
-            ZExtInst* oldZext = dyn_cast<ZExtInst>(UInst2->use_begin());
-            uint64_t truncSize = oldZext->getType()->getPrimitiveSizeInBits();
-            Value *TruncIndVar = getSignExtendedTruncVar(AR, SE, LargestType,
-                                    L, oldZext->getType(), Rewriter);
-            ConstantInt* AndRHS = dyn_cast<ConstantInt>(UInst2->getOperand(1));
-            APInt APnewAddRHS = APInt(AddRHS->getValue()).zext(newBitSize);
-            if (newBitSize > truncSize)
-              APnewAddRHS = APnewAddRHS.trunc(truncSize);
-            ConstantInt* newAddRHS = ConstantInt::get(APnewAddRHS);
-            Value *NewAdd = ((UInst->getOpcode()==Instruction::Add) ?
-                  BinaryOperator::CreateAdd(TruncIndVar, newAddRHS,
-                                            UInst->getName()+".nozex", UInst2) :
-                  BinaryOperator::CreateOr(TruncIndVar, newAddRHS,
-                                            UInst->getName()+".nozex", UInst2));
-            APInt APcopy2 = APInt(AndRHS->getValue());
-            ConstantInt* newAndRHS = ConstantInt::get(APcopy2.zext(newBitSize));
-            Value *NewAnd = 
-                  BinaryOperator::CreateAnd(NewAdd, newAndRHS,
-                                            UInst->getName()+".nozex", UInst2);
-            for (Value::use_iterator UI2 = UInst2->use_begin(), 
-                  UE2 = UInst2->use_end(); UI2 != UE2; ++UI2) {
-              Instruction *II = dyn_cast<Instruction>(UI2);
-              II->replaceAllUsesWith(NewAnd);
-              DeadInsts.insert(II);
-            }
-            DeadInsts.insert(UInst);
-            DeadInsts.insert(UInst2);
+
+        // Create the SCEV representing the offset from the canonical
+        // induction variable, still in the canonical induction variable's
+        // type, so that all expanded arithmetic is done in the same type.
+        SCEVHandle NewAR = SE->getAddRecExpr(SE->getIntegerSCEV(0, LargestType),
+                                           PromotedStride, L);
+        // Add the PromotedOffset as a separate step, because it may not be
+        // loop-invariant.
+        NewAR = SE->getAddExpr(NewAR, PromotedOffset);
+
+        // Expand the addrec into instructions.
+        Value *V = Rewriter.expandCodeFor(NewAR, LargestType);
+
+        // Insert an explicit cast if necessary to truncate the value
+        // down to the original stride type. This is done outside of
+        // SCEVExpander because in SCEV expressions, a truncate of an
+        // addrec is always folded.
+        if (LargestType != IVTy) {
+          if (SE->getTypeSizeInBits(IVTy) != SE->getTypeSizeInBits(LargestType))
+            NewAR = SE->getTruncateExpr(NewAR, IVTy);
+          if (Rewriter.isInsertedExpression(NewAR))
+            V = Rewriter.expandCodeFor(NewAR, IVTy);
+          else {
+            V = Rewriter.InsertCastOfTo(CastInst::getCastOpcode(V, false,
+                                                                IVTy, false),
+                                        V, IVTy);
+            assert(!isa<SExtInst>(V) && !isa<ZExtInst>(V) &&
+                   "LargestType wasn't actually the largest type!");
+            // Force the rewriter to use this trunc whenever this addrec
+            // appears so that it doesn't insert new phi nodes or
+            // arithmetic in a different type.
+            Rewriter.addInsertedValue(V, NewAR);
           }
         }
+
+        DOUT << "INDVARS: Made offset-and-trunc IV for offset "
+             << *IVTy << " " << *Offset << ": ";
+        DEBUG(WriteAsOperand(*DOUT, V, false));
+        DOUT << "\n";
+
+        // Now expand it into actual Instructions and patch it into place.
+        NewVal = Rewriter.expandCodeFor(AR, UseTy);
       }
 
-    // Replace the old PHI Node with the inserted computation.
-    PN->replaceAllUsesWith(NewVal);
-    DeadInsts.insert(PN);
-    IndVars.pop_back();
-    ++NumRemoved;
-    Changed = true;
+      // Patch the new value into place.
+      if (Op->hasName())
+        NewVal->takeName(Op);
+      User->replaceUsesOfWith(Op, NewVal);
+      UI->setOperandValToReplace(NewVal);
+      DOUT << "INDVARS: Rewrote IV '" << *AR << "' " << *Op
+           << "   into = " << *NewVal << "\n";
+      ++NumRemoved;
+      Changed = true;
+
+      // The old value may be dead now.
+      DeadInsts.push_back(Op);
+    }
   }
 
-  DeleteTriviallyDeadInstructions(DeadInsts);
-  assert(L->isLCSSAForm());
-  return Changed;
+  // Now that we're done iterating through lists, clean up any instructions
+  // which are now dead.
+  while (!DeadInsts.empty()) {
+    Instruction *Inst = dyn_cast_or_null<Instruction>(DeadInsts.pop_back_val());
+    if (Inst)
+      RecursivelyDeleteTriviallyDeadInstructions(Inst);
+  }
+}
+
+/// If there's a single exit block, sink any loop-invariant values that
+/// were defined in the preheader but not used inside the loop into the
+/// exit block to reduce register pressure in the loop.
+void IndVarSimplify::SinkUnusedInvariants(Loop *L, SCEVExpander &Rewriter) {
+  BasicBlock *ExitBlock = L->getExitBlock();
+  if (!ExitBlock) return;
+
+  Instruction *NonPHI = ExitBlock->getFirstNonPHI();
+  BasicBlock *Preheader = L->getLoopPreheader();
+  BasicBlock::iterator I = Preheader->getTerminator();
+  while (I != Preheader->begin()) {
+    --I;
+    // New instructions were inserted at the end of the preheader. Only
+    // consider those new instructions.
+    if (!Rewriter.isInsertedInstruction(I))
+      break;
+    // Determine if there is a use in or before the loop (direct or
+    // otherwise).
+    bool UsedInLoop = false;
+    for (Value::use_iterator UI = I->use_begin(), UE = I->use_end();
+         UI != UE; ++UI) {
+      BasicBlock *UseBB = cast<Instruction>(UI)->getParent();
+      if (PHINode *P = dyn_cast<PHINode>(UI)) {
+        unsigned i =
+          PHINode::getIncomingValueNumForOperand(UI.getOperandNo());
+        UseBB = P->getIncomingBlock(i);
+      }
+      if (UseBB == Preheader || L->contains(UseBB)) {
+        UsedInLoop = true;
+        break;
+      }
+    }
+    // If there is, the def must remain in the preheader.
+    if (UsedInLoop)
+      continue;
+    // Otherwise, sink it to the exit block.
+    Instruction *ToMove = I;
+    bool Done = false;
+    if (I != Preheader->begin())
+      --I;
+    else
+      Done = true;
+    ToMove->moveBefore(NonPHI);
+    if (Done)
+      break;
+  }
+}
+
+/// Re-schedule the inserted instructions to put defs before uses. This
+/// fixes problems that arrise when SCEV expressions contain loop-variant
+/// values unrelated to the induction variable which are defined inside the
+/// loop. FIXME: It would be better to insert instructions in the right
+/// place so that this step isn't needed.
+void IndVarSimplify::FixUsesBeforeDefs(Loop *L, SCEVExpander &Rewriter) {
+  // Visit all the blocks in the loop in pre-order dom-tree dfs order.
+  DominatorTree *DT = &getAnalysis<DominatorTree>();
+  std::map<Instruction *, unsigned> NumPredsLeft;
+  SmallVector<DomTreeNode *, 16> Worklist;
+  Worklist.push_back(DT->getNode(L->getHeader()));
+  do {
+    DomTreeNode *Node = Worklist.pop_back_val();
+    for (DomTreeNode::iterator I = Node->begin(), E = Node->end(); I != E; ++I)
+      if (L->contains((*I)->getBlock()))
+        Worklist.push_back(*I);
+    BasicBlock *BB = Node->getBlock();
+    // Visit all the instructions in the block top down.
+    for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) {
+      // Count the number of operands that aren't properly dominating.
+      unsigned NumPreds = 0;
+      if (Rewriter.isInsertedInstruction(I) && !isa<PHINode>(I))
+        for (User::op_iterator OI = I->op_begin(), OE = I->op_end();
+             OI != OE; ++OI)
+          if (Instruction *Inst = dyn_cast<Instruction>(OI))
+            if (L->contains(Inst->getParent()) && !NumPredsLeft.count(Inst))
+              ++NumPreds;
+      NumPredsLeft[I] = NumPreds;
+      // Notify uses of the position of this instruction, and move the
+      // users (and their dependents, recursively) into place after this
+      // instruction if it is their last outstanding operand.
+      for (Value::use_iterator UI = I->use_begin(), UE = I->use_end();
+           UI != UE; ++UI) {
+        Instruction *Inst = cast<Instruction>(UI);
+        std::map<Instruction *, unsigned>::iterator Z = NumPredsLeft.find(Inst);
+        if (Z != NumPredsLeft.end() && Z->second != 0 && --Z->second == 0) {
+          SmallVector<Instruction *, 4> UseWorkList;
+          UseWorkList.push_back(Inst);
+          BasicBlock::iterator InsertPt = next(I);
+          while (isa<PHINode>(InsertPt)) ++InsertPt;
+          do {
+            Instruction *Use = UseWorkList.pop_back_val();
+            Use->moveBefore(InsertPt);
+            NumPredsLeft.erase(Use);
+            for (Value::use_iterator IUI = Use->use_begin(),
+                 IUE = Use->use_end(); IUI != IUE; ++IUI) {
+              Instruction *IUIInst = cast<Instruction>(IUI);
+              if (L->contains(IUIInst->getParent()) &&
+                  Rewriter.isInsertedInstruction(IUIInst) &&
+                  !isa<PHINode>(IUIInst))
+                UseWorkList.push_back(IUIInst);
+            }
+          } while (!UseWorkList.empty());
+        }
+      }
+    }
+  } while (!Worklist.empty());
 }
 
 /// Return true if it is OK to use SIToFPInst for an inducation variable
@@ -933,8 +728,7 @@ static bool convertToInt(const APFloat &APF, uint64_t *intVal) {
 /// for(int i = 0; i < 10000; ++i)
 ///   bar((double)i);
 ///
-void IndVarSimplify::HandleFloatingPointIV(Loop *L, PHINode *PH,
-                                   SmallPtrSet<Instruction*, 16> &DeadInsts) {
+void IndVarSimplify::HandleFloatingPointIV(Loop *L, PHINode *PH) {
 
   unsigned IncomingEdge = L->contains(PH->getIncomingBlock(0));
   unsigned BackEdge     = IncomingEdge^1;
@@ -1041,25 +835,34 @@ void IndVarSimplify::HandleFloatingPointIV(Loop *L, PHINode *PH,
   ICmpInst *NewEC = new ICmpInst(NewPred, LHS, RHS, EC->getNameStart(),
                                  EC->getParent()->getTerminator());
 
+  // In the following deltions, PH may become dead and may be deleted.
+  // Use a WeakVH to observe whether this happens.
+  WeakVH WeakPH = PH;
+
   // Delete old, floating point, exit comparision instruction.
   EC->replaceAllUsesWith(NewEC);
-  DeadInsts.insert(EC);
+  RecursivelyDeleteTriviallyDeadInstructions(EC);
 
   // Delete old, floating point, increment instruction.
   Incr->replaceAllUsesWith(UndefValue::get(Incr->getType()));
-  DeadInsts.insert(Incr);
-
-  // Replace floating induction variable. Give SIToFPInst preference over
-  // UIToFPInst because it is faster on platforms that are widely used.
-  if (useSIToFPInst(*InitValue, *EV, newInitValue, intEV)) {
-    SIToFPInst *Conv = new SIToFPInst(NewPHI, PH->getType(), "indvar.conv",
-                                      PH->getParent()->getFirstNonPHI());
-    PH->replaceAllUsesWith(Conv);
-  } else {
-    UIToFPInst *Conv = new UIToFPInst(NewPHI, PH->getType(), "indvar.conv",
-                                      PH->getParent()->getFirstNonPHI());
-    PH->replaceAllUsesWith(Conv);
+  RecursivelyDeleteTriviallyDeadInstructions(Incr);
+
+  // Replace floating induction variable, if it isn't already deleted.
+  // Give SIToFPInst preference over UIToFPInst because it is faster on
+  // platforms that are widely used.
+  if (WeakPH && !PH->use_empty()) {
+    if (useSIToFPInst(*InitValue, *EV, newInitValue, intEV)) {
+      SIToFPInst *Conv = new SIToFPInst(NewPHI, PH->getType(), "indvar.conv",
+                                        PH->getParent()->getFirstNonPHI());
+      PH->replaceAllUsesWith(Conv);
+    } else {
+      UIToFPInst *Conv = new UIToFPInst(NewPHI, PH->getType(), "indvar.conv",
+                                        PH->getParent()->getFirstNonPHI());
+      PH->replaceAllUsesWith(Conv);
+    }
+    RecursivelyDeleteTriviallyDeadInstructions(PH);
   }
-  DeadInsts.insert(PH);
-}
 
+  // Add a new IVUsers entry for the newly-created integer PHI.
+  IU->AddUsersIfInteresting(NewPHI);
+}