Index: lib/Transforms/Scalar/LoopStrengthReduce.cpp
===================================================================
--- lib/Transforms/Scalar/LoopStrengthReduce.cpp
+++ lib/Transforms/Scalar/LoopStrengthReduce.cpp
@@ -1062,6 +1062,56 @@
   }
 };
 
+/// Helper class to count probability as a fraction instead of float.
+class Fraction {
+  uint64_t Numerator;
+  uint64_t Denominator;
+  Fraction &Optimize() {
+    while (Numerator > UINT32_MAX / 2 || Denominator > UINT32_MAX / 2) {
+      Numerator >>= 1;
+      Denominator >>= 1;
+    }
+    if (Denominator == 0) {
+      Denominator = 1;
+      Numerator = UINT32_MAX / 2;
+    }
+    return *this;
+  }
+public:
+  Fraction() : Numerator(0), Denominator(1) {}
+  Fraction(unsigned N, unsigned D) : Numerator(N), Denominator(D) {}
+  Fraction operator/(const Fraction &Divider) const {
+    Fraction Res;
+    Res.Numerator = Numerator / Divider.Numerator;
+    Res.Denominator = Denominator / Divider.Denominator;
+    return Res;
+  }
+  float getFloat() {
+    return (float)Numerator / Denominator;
+  }
+  Fraction operator*(const Fraction Multiplier) const {
+    Fraction Res;
+    Res.Numerator = Numerator * Multiplier.Numerator;
+    Res.Denominator = Denominator * Multiplier.Denominator;
+    return Res.Optimize();
+  }
+  Fraction operator+(const Fraction Add) const {
+    Fraction Res;
+    Res.Numerator = Numerator * Add.Denominator + Denominator * Add.Numerator;
+    Res.Denominator *= Add.Denominator;
+    return Res.Optimize();
+  }
+  bool operator>(const Fraction Right) const {
+    return Numerator * Right.Denominator > Denominator * Right.Numerator;
+  }
+  bool operator!=(const Fraction Right) const {
+    return Numerator * Right.Denominator != Denominator * Right.Numerator;
+  }
+  bool operator==(const Fraction Right) const {
+    return Numerator * Right.Denominator == Denominator * Right.Numerator;
+  }
+};
+
 /// This class holds the state that LSR keeps for each use in IVUsers, as well
 /// as uses invented by LSR itself. It includes information about what kinds of
 /// things can be folded into the user, information about the user itself, and
@@ -1137,7 +1187,7 @@
   }
   
   bool HasFormulaWithSameRegs(const Formula &F) const;
-  float getNotSelectedProbability(const SCEV *Reg) const;
+  Fraction getNotSelectedProbability(const SCEV *Reg) const;
   bool InsertFormula(const Formula &F, const Loop &L);
   void DeleteFormula(Formula &F);
   void RecomputeRegs(size_t LUIdx, RegUseTracker &Reguses);
@@ -1417,12 +1467,12 @@
 }
 
 /// The function returns a probability of selecting formula without Reg.
-float LSRUse::getNotSelectedProbability(const SCEV *Reg) const {
+Fraction 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();
+  return Fraction (Formulae.size() - FNum, Formulae.size());
 }
 
 /// If the given formula has not yet been inserted, add it to the list, and
@@ -4364,17 +4414,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 *, Fraction> RegNumMap;
   for (const SCEV *Reg : RegUses) {
     if (UniqRegs.count(Reg))
       continue;
-    float PNotSel = 1;
+    Fraction PNotSel(1, 1);
     for (const LSRUse &LU : Uses) {
       if (!LU.Regs.count(Reg))
         continue;
-      float P = LU.getNotSelectedProbability(Reg);
-      if (P != 0.0)
-        PNotSel *= P;
+      Fraction P = LU.getNotSelectedProbability(Reg);
+      if (P != Fraction(0, 1))
+        PNotSel = PNotSel * P;
       else
         UniqRegs.insert(Reg);
     }
@@ -4392,27 +4442,28 @@
     // 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();
+    Fraction FMinRegNum(LU.Formulae[0].getNumRegs(), 1);
+    Fraction FMinARegNum(LU.Formulae[0].getNumRegs(), 1);
     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;
+      Fraction FRegNum;
+      Fraction FARegNum;
       for (const SCEV *BaseReg : F.BaseRegs) {
         if (UniqRegs.count(BaseReg))
           continue;
-        FRegNum += RegNumMap[BaseReg] / LU.getNotSelectedProbability(BaseReg);
+        FRegNum = FRegNum +
+            RegNumMap[BaseReg] / LU.getNotSelectedProbability(BaseReg);
         if (isa<SCEVAddRecExpr>(BaseReg))
-          FARegNum +=
+          FARegNum = FARegNum +
               RegNumMap[BaseReg] / LU.getNotSelectedProbability(BaseReg);
       }
       if (const SCEV *ScaledReg = F.ScaledReg) {
         if (!UniqRegs.count(ScaledReg)) {
-          FRegNum +=
+          FRegNum = FRegNum +
               RegNumMap[ScaledReg] / LU.getNotSelectedProbability(ScaledReg);
           if (isa<SCEVAddRecExpr>(ScaledReg))
-            FARegNum +=
+            FARegNum = FARegNum +
                 RegNumMap[ScaledReg] / LU.getNotSelectedProbability(ScaledReg);
         }
       }
@@ -4424,7 +4475,7 @@
       }
     }
     DEBUG(dbgs() << "  The formula "; LU.Formulae[MinIdx].print(dbgs());
-          dbgs() << " with min reg num " << FMinRegNum << '\n');
+          dbgs() << " with min reg num " << FMinRegNum.getFloat() << '\n');
     if (MinIdx != 0)
       std::swap(LU.Formulae[MinIdx], LU.Formulae[0]);
     while (LU.Formulae.size() != 1) {