Page MenuHomePhabricator

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

Authored by evstupac on Mar 2 2017, 1:19 AM.

Details

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).

Diff Detail

Repository
rL LLVM

Event Timeline

evstupac created this revision.Mar 2 2017, 1:19 AM
qcolombet added inline comments.Mar 7 2017, 4:00 PM
lib/Transforms/Scalar/LoopStrengthReduce.cpp
1113

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

1126

Add an assert D != 0

1131

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 added inline comments.Mar 7 2017, 4:48 PM
lib/Transforms/Scalar/LoopStrengthReduce.cpp
1113

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.

1126

ok.

1131

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 added a subscriber: scanon.Mar 8 2017, 8:35 AM

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

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.

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

qcolombet edited edge metadata.May 18 2017, 12:18 PM

Please follow @scanon recommendation.

evstupac updated this revision to Diff 99629.May 19 2017, 2:58 PM

Add fixed point instead of fraction.

sanjoy added a subscriber: sanjoy.May 21 2017, 10:02 PM

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

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).

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.

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.

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

evstupac updated this revision to Diff 143853.Apr 24 2018, 7:07 PM

Use APFloat instead of new class.

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

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

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 edited the summary of this revision. (Show Details)Jun 7 2018, 2:05 PM