Index: lib/Transforms/Scalar/LoopStrengthReduce.cpp
===================================================================
--- lib/Transforms/Scalar/LoopStrengthReduce.cpp
+++ lib/Transforms/Scalar/LoopStrengthReduce.cpp
@@ -1074,10 +1074,10 @@
   /// An enum for a kind of use, indicating what types of scaled and immediate
   /// operands it might support.
   enum KindType {
-    Basic,   ///< A normal use, with no folding.
-    Special, ///< A special case of basic, allowing -1 scales.
-    Address, ///< An address use; folding according to TargetLowering
-    ICmpZero ///< An equality icmp with both operands folded into one.
+    Basic,    ///< A normal use, with no folding.
+    ICmpZero, ///< An equality icmp with both operands folded into one.
+    Special,  ///< A special case of basic, allowing -1 scales.
+    Address   ///< An address use; folding according to TargetLowering
     // TODO: Add a generic icmp too?
   };
 
@@ -1522,6 +1522,11 @@
 }
 #endif
 
+static bool LSRUseCompare (const LSRUse &U1, const LSRUse &U2) {
+  return (U1.Kind < U2.Kind) ||
+         (U1.Kind == U2.Kind && U1.Formulae.size() < U2.Formulae.size());
+}
+
 static bool isAMCompletelyFolded(const TargetTransformInfo &TTI,
                                  LSRUse::KindType Kind, MemAccessTy AccessTy,
                                  GlobalValue *BaseGV, int64_t BaseOffset,
@@ -4362,6 +4367,8 @@
   // We can skip them in calculations.
   SmallPtrSet<const SCEV *, 4> UniqRegs;
   DEBUG(dbgs() << "The search space is too complex.\n");
+  // It is ok to sort Uses as we'll choose a solution in the function.
+  std::sort (Uses.begin(), Uses.end(), LSRUseCompare);
 
   // Map each register to probability of not selecting
   DenseMap <const SCEV *, float> RegNumMap;
@@ -4394,6 +4401,7 @@
     // different results for different target builds.
     float FMinRegNum = LU.Formulae[0].getNumRegs();
     float FMinARegNum = LU.Formulae[0].getNumRegs();
+    unsigned FMinBaseAdd = LU.Formulae[0].getNumRegs();
     size_t MinIdx = 0;
     for (size_t i = 0, e = LU.Formulae.size(); i != e; ++i) {
       Formula &F = LU.Formulae[i];
@@ -4417,9 +4425,12 @@
         }
       }
       if (FMinRegNum > FRegNum ||
-          (FMinRegNum == FRegNum && FMinARegNum > FARegNum)) {
+          (FMinRegNum == FRegNum &&
+           (FMinARegNum > FARegNum ||
+            (FMinARegNum == FARegNum && FMinBaseAdd > F.getNumRegs())))) {
         FMinRegNum = FRegNum;
         FMinARegNum = FARegNum;
+        FMinBaseAdd = F.getNumRegs();
         MinIdx = i;
       }
     }
@@ -4432,7 +4443,6 @@
             dbgs() << '\n');
       LU.Formulae.pop_back();
     }
-    LU.RecomputeRegs(LUIdx, RegUses);
     assert(LU.Formulae.size() == 1 && "Should be exactly 1 min regs formula");
     Formula &F = LU.Formulae[0];
     DEBUG(dbgs() << "  Leaving only "; F.print(dbgs()); dbgs() << '\n');
Index: test/Transforms/LoopStrengthReduce/2013-01-14-ReuseCast.ll
===================================================================
--- test/Transforms/LoopStrengthReduce/2013-01-14-ReuseCast.ll
+++ test/Transforms/LoopStrengthReduce/2013-01-14-ReuseCast.ll
@@ -14,8 +14,8 @@
 ; current LSR cost model.
 ; CHECK-NOT: = ptrtoint i8* undef to i64
 ; CHECK: .lr.ph
-; CHECK: [[TMP:%[^ ]+]] = add i64 %4, 1
-; CHECK: sub i64 [[TMP]], %tmp6
+; CHECK: [[REG:%[^ ]+]] = add i64 %tmp6, -1
+; CHECK: sub i64 [[REG]], %tmp5
 ; CHECK: ret void
 define void @VerifyDiagnosticConsumerTest() unnamed_addr nounwind uwtable align 2 {
 bb: