Index: lib/Transforms/Scalar/LoopStrengthReduce.cpp
===================================================================
--- lib/Transforms/Scalar/LoopStrengthReduce.cpp
+++ lib/Transforms/Scalar/LoopStrengthReduce.cpp
@@ -1178,7 +1178,7 @@
   }
 
   bool HasFormulaWithSameRegs(const Formula &F) const;
-  float getNotSelectedProbability(const SCEV *Reg) const;
+  APFloat getNotSelectedProbability(const SCEV *Reg) const;
   bool InsertFormula(const Formula &F, const Loop &L);
   void DeleteFormula(Formula &F);
   void RecomputeRegs(size_t LUIdx, RegUseTracker &Reguses);
@@ -1484,12 +1484,17 @@
 }
 
 /// The function returns a probability of selecting formula without Reg.
-float LSRUse::getNotSelectedProbability(const SCEV *Reg) const {
+APFloat LSRUse::getNotSelectedProbability(const SCEV *Reg) const {
   unsigned FNum = 0;
   for (const Formula &F : Formulae)
     if (F.referencesReg(Reg))
       FNum++;
-  return ((float)(Formulae.size() - FNum)) / Formulae.size();
+  APFloat Ret(0.0), Div(0.0);
+  Ret.convertFromAPInt(APInt(64, Formulae.size() - FNum), false,
+                       APFloat::rmNearestTiesToEven);
+  Div.convertFromAPInt(APInt(64, Formulae.size()), false,
+                       APFloat::rmNearestTiesToEven);
+  return Ret / Div;
 }
 
 /// If the given formula has not yet been inserted, add it to the list, and
@@ -4584,17 +4589,17 @@
   DEBUG(dbgs() << "The search space is too complex.\n");
 
   // Map each register to probability of not selecting
-  DenseMap <const SCEV *, float> RegNumMap;
+  DenseMap <const SCEV *, APFloat> RegNumMap;
   for (const SCEV *Reg : RegUses) {
     if (UniqRegs.count(Reg))
       continue;
-    float PNotSel = 1;
+    APFloat PNotSel(1.0);
     for (const LSRUse &LU : Uses) {
       if (!LU.Regs.count(Reg))
         continue;
-      float P = LU.getNotSelectedProbability(Reg);
-      if (P != 0.0)
-        PNotSel *= P;
+      APFloat P = LU.getNotSelectedProbability(Reg);
+      if (P.isNonZero())
+        PNotSel = PNotSel * P;
       else
         UniqRegs.insert(Reg);
     }
@@ -4612,32 +4617,36 @@
     // This is temporary solution to test performance. Float should be
     // replaced with round independent type (based on integers) to avoid
     // different results for different target builds.
-    float FMinRegNum = LU.Formulae[0].getNumRegs();
-    float FMinARegNum = LU.Formulae[0].getNumRegs();
+    APFloat FMinRegNum(0.0), FMinARegNum(0.0);
+    FMinRegNum.convertFromAPInt(APInt(64, LU.Formulae[0].getNumRegs()), false,
+                                APFloatBase::rmNearestTiesToEven);
+    FMinARegNum = FMinRegNum;
     size_t MinIdx = 0;
     for (size_t i = 0, e = LU.Formulae.size(); i != e; ++i) {
       Formula &F = LU.Formulae[i];
-      float FRegNum = 0;
-      float FARegNum = 0;
+      APFloat FRegNum(0.0);
+      APFloat FARegNum(0.0);
       for (const SCEV *BaseReg : F.BaseRegs) {
         if (UniqRegs.count(BaseReg))
           continue;
-        FRegNum += RegNumMap[BaseReg] / LU.getNotSelectedProbability(BaseReg);
+        FRegNum = FRegNum + (RegNumMap.find(BaseReg)->second /
+                             LU.getNotSelectedProbability(BaseReg));
         if (isa<SCEVAddRecExpr>(BaseReg))
-          FARegNum +=
-              RegNumMap[BaseReg] / LU.getNotSelectedProbability(BaseReg);
+          FARegNum = FARegNum + (RegNumMap.find(BaseReg)->second /
+                                 LU.getNotSelectedProbability(BaseReg));
       }
       if (const SCEV *ScaledReg = F.ScaledReg) {
         if (!UniqRegs.count(ScaledReg)) {
-          FRegNum +=
-              RegNumMap[ScaledReg] / LU.getNotSelectedProbability(ScaledReg);
+          FRegNum = FRegNum + (RegNumMap.find(ScaledReg)->second /
+                               LU.getNotSelectedProbability(ScaledReg));
           if (isa<SCEVAddRecExpr>(ScaledReg))
-            FARegNum +=
-                RegNumMap[ScaledReg] / LU.getNotSelectedProbability(ScaledReg);
+            FARegNum = FARegNum + (RegNumMap.find(ScaledReg)->second /
+                                   LU.getNotSelectedProbability(ScaledReg));
         }
       }
-      if (FMinRegNum > FRegNum ||
-          (FMinRegNum == FRegNum && FMinARegNum > FARegNum)) {
+      if (FMinRegNum.compare(FRegNum) == APFloat::cmpGreaterThan ||
+          (FMinRegNum.compare(FRegNum) == APFloat::cmpEqual &&
+           FMinARegNum.compare(FARegNum) == APFloat::cmpGreaterThan)) {
         FMinRegNum = FRegNum;
         FMinARegNum = FARegNum;
         MinIdx = i;