Replacing float with new class Fraction for LSR alternative way of resolving complex solution

[evstupac]

Summary

With floating point we potentially get different results on different CPUs). This patch helps to avoid this.
The change is follow up for https://reviews.llvm.org/D29862.
It should be NFC (at least on all CPUs I have in my pool).

[qcolombet]

lib/Transforms/Scalar/LoopStrengthReduce.cpp

1069

Could you add a comment explaining how the optimization work?
The reduction does not look right to me, but my math class are way behind me :P

1082

Add an assert D != 0

1087

I am confused about the meaning of this operator.
For divide, I would have expected something like:
return operator*(Fraction(Divider.Denominator, Divider.Numerator));

[evstupac]

lib/Transforms/Scalar/LoopStrengthReduce.cpp

1069

I suppose Numerator and Denominator will be in 31 bits for most cases. However if one of them exceed 31 bits, then operator+ could overflow.
To avoid this we need to optimize a fraction.
Converting N/D to (N/2)/(D/2) will potentially loose precision, but it is much faster than searching for common dividers. The precision we loose is not higher than ABS(N/D - (N/2)/(D/2)), which is not higher than max(D/2,N/2)/(D*D/2). Since we are working with probability N <= D. So it should be less than 1/D each step. That means precision loss is less than 1/(2^31), as D > 2^31. Which is acceptable.
I'll add the comment to sources.

1082

ok.

1087

Well, this is specific for our case: probability of not selecting (PoNS) for reg R.
PoNS at all is multiplication of PoNS for each use: PAll = P1*P2*...*PK (this is counted once). Suppose we want to get PoNS for particular register use - Use2. It will be PAll / P2. Numerator in PAll fraction has multiplier P2 Numerator. The same about Denominator. That way we don't need optimization.

[scanon]

What's the rationale for using rationals here instead of a (simpler) fixed-point representation, if we want to get rid of float?

[evstupac]

What's the rationale for using rationals here instead of a (simpler) fixed-point representation, if we want to get rid of float?

No specific reason. Actually it is a kind of. I've looked into LLVM support classes and have not found appropriate.

[evstupac]

PING.
Should I rewrite this using fixed point float?
Or newly implemented fraction class is acceptable?

[evstupac]

PING.

[qcolombet]

Please follow @scanon recommendation.

[evstupac]

Add fixed point instead of fraction.

[sanjoy]

Drive by comment: how about putting the FixedPoint64 in ADT and adding one or two unit tests?

[evstupac]

In D30527#760563, @sanjoy wrote:

Drive by comment: how about putting the FixedPoint64 in ADT and adding one or two unit tests?

The class supports only unsigned values and misses some general operators. However I'm ok with adding it to ADT (and maybe supporting more later).
As for tests, this change should not change anything. The behavior should be the same. (float are replaced with fixed point to avoid potential different results on different CPUs).

[sanjoy]

In D30527#762673, @evstupac wrote:

As for tests, this change should not change anything. The behavior should be the same. (float are replaced with fixed point to avoid potential different results on different CPUs).

I think that's contradictory -- you're saying that this change must be NFC; but it will avoid potential different results on different CPUs?

In any case, by "test" I meant testing the FixedPoint64 class itself.

[evstupac]

I think that's contradictory -- you're saying that this change must be NFC; but it will avoid potential different results on different CPUs?

I don't have a case in my mind. However I agreed with Quentin, that floats "can introduce subtle difference from one target to other". That comes from D29826.

In any case, by "test" I meant testing the FixedPoint64 class itself.

Ok. I'll add such.

[qcolombet]

I like @sanjoy's suggestion.
@scanon Could you do the review? I would prefer if an expert can look at it.
Thanks

[evstupac]

Use APFloat instead of new class.

[scanon]

@gottesmm can you take a look at this? You're more familiar with the APFloat API than I am.

[evstupac]

PING.

[evstupac]

PING

[evstupac]

PING

[evstupac]

PING.

[lebedev.ri]

I think it might help if the motivational part would be specified in the differential's description.

Why is this wanted?
With what does this help?
Does this change affect anything?
Can the change be tested?
etc

[evstupac]

In D30527#1125545, @lebedev.ri wrote:

I think it might help if the motivational part would be specified in the differential's description.

Why is this wanted?

It was requested by Quentin in https://reviews.llvm.org/D29862

With what does this help?

It potentially helps to avoid different results on different CPUs due to use of floating point arithmetic.

Does this change affect anything?

No. It is NFC on all CPUs I have in my pool.

Can the change be tested?

I don't see how.

etc

[evstupac]

PING

[evstupac]

PING

[eopXD]

This patch looks good to me.
I think we can rebase and land this?

lib/Transforms/Scalar/LoopStrengthReduce.cpp

struct UniquifierDenseMapInfo {
   }
 
   static bool isEqual(const SmallVector<const SCEV *, 4> &LHS,
                       const SmallVector<const SCEV *, 4> &RHS) {
     return LHS == RHS;
   }
 };
 
+/// 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
 /// information about how the use may be satisfied.  TODO: Represent multiple
 /// users of the same expression in common?
 class LSRUse {
   DenseSet<SmallVector<const SCEV *, 4>, UniquifierDenseMapInfo> Uniquifier;
 
void pushFixup(LSRFixup &f) {
     Fixups.push_back(f);
     if (f.Offset > MaxOffset)
       MaxOffset = f.Offset;
     if (f.Offset < MinOffset)
       MinOffset = f.Offset;
   }
   
   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);
 
   void print(raw_ostream &OS) const;
   void dump() const;
 };
 
bool LSRUse::HasFormulaWithSameRegs(const Formula &F) const {
   SmallVector<const SCEV *, 4> Key = F.BaseRegs;
   if (F.ScaledReg) Key.push_back(F.ScaledReg);
   // Unstable sort by host order ok, because this is only used for uniquifying.
   std::sort(Key.begin(), Key.end());
   return Uniquifier.count(Key);
 }
 
 /// 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
 /// return true. Return false otherwise.  The formula must be in canonical form.
 bool LSRUse::InsertFormula(const Formula &F, const Loop &L) {
   assert(F.isCanonical(L) && "Invalid canonical representation");
 
   if (!Formulae.empty() && RigidFormula)
void LSRInstance::NarrowSearchSpaceByDeletingCostlyFormulas() {
 
   // Set of Regs wich will be 100% used in final solution.
   // Used in each formula of a solution (in example above this is reg(c)).
   // We can skip them in calculations.
   SmallPtrSet<const SCEV *, 4> UniqRegs;
   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);
     }
     RegNumMap.insert(std::make_pair(Reg, PNotSel));
   }
 
   DEBUG(dbgs() << "Narrowing the search space by deleting costly formulas\n");
 
   // Delete formulas where registers number expectation is high.
   for (size_t LUIdx = 0, NumUses = Uses.size(); LUIdx != NumUses; ++LUIdx) {
     LSRUse &LU = Uses[LUIdx];
     // If nothing to delete - continue.
     if (LU.Formulae.size() < 2)
       continue;
     // 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);
         }
       }
       if (FMinRegNum > FRegNum ||
           (FMinRegNum == FRegNum && FMinARegNum > FARegNum)) {
         FMinRegNum = FRegNum;
         FMinARegNum = FARegNum;
         MinIdx = i;
       }
     }
     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) {
       DEBUG(dbgs() << "  Deleting "; LU.Formulae.back().print(dbgs());
             dbgs() << '\n');
       LU.Formulae.pop_back();
     }
     LU.RecomputeRegs(LUIdx, RegUses);