[PATCH] Add a simple fraction class

Richard Sandiford richard.sandiford@arm.com
Mon Aug 2 11:31:46 GMT 2021


Richard Biener <richard.guenther@gmail.com> writes:
> On Mon, Aug 2, 2021 at 12:43 PM Richard Sandiford
> <richard.sandiford@arm.com> wrote:
>>
>> Richard Biener via Gcc-patches <gcc-patches@gcc.gnu.org> writes:
>> > On Fri, Jul 30, 2021 at 5:59 PM Richard Sandiford via Gcc-patches
>> > <gcc-patches@gcc.gnu.org> wrote:
>> >>
>> >> This patch adds a simple class for holding A/B fractions.
>> >> As the comments in the patch say, the class isn't designed
>> >> to have nice numerial properties at the extremes.
>> >>
>> >> The motivating use case was some aarch64 costing work,
>> >> where being able to represent fractions was much easier
>> >> than using single integers and avoided the rounding errors
>> >> that would come with using floats.  (Unlike things like
>> >> COSTS_N_INSNS, there was no sensible constant base factor
>> >> that could be used.)
>> >>
>> >> Tested on aarch64-linux-gnu and x86_64-linux-gnu.  OK to install?
>> >
>> > Hmm, we use the sreal type for profiles.  I don't see any overflow/underflow
>> > handling in your class - I suppose you're going to use it on integer types
>> > given we're not allowed to use native FP?
>>
>> Yeah, I'm going to use it on integer types.  And it's not designed
>> to have nice properties at extremes, including handling underflow and
>> overflow.
>
> So maybe assert that it doesn't?  In particular nominator/denominator
> are prone to overflowing in fractional representations.
>
> There's the option to round or ICE.  Or rather than the only option
> is to round (or use a more expensive arbitrary precision representation).

Yeah, I guess we could do that, but it semes inconsistent to assert
for these costs and not do it for vector costs in general.  I think it's
difficult to guarantee that there is no user input for which the current
vector costs overflow.  And if we assert, we have to have a reason for
believing that no such user input exists (modulo bugs).

E.g. vect-inner-loop-cost-factor has an upper limit of 999999, so the
existing code only needs a cost of 2148 to overflow “int”.

> So the question is whether the fractional behavior is better in more
> cases than the sreal behavior (I can easily believe it is).
>
>> I want to use it in costing code, where we already happily multiply
>> and add “int”-sized costs without worrying about overflow.  I'll be
>> using uint64_t for the fractions though, just in case. :-)
>>
>> sreal doesn't help because it's still significand/exponent.  That matters
>> because…
>>
>> > I mean, how exactly does
>> > the class solve the problem of rounding errors?
>>
>> …I wanted something that represented the results exactly (barring any of
>> integer ops overflowing).  This makes it meaningful to compare costs for
>> equality.  It also means we can use ordered comparisons without having
>> to introduce a fudge factor to cope with one calculation having different
>> intermediate rounding from the other.
>
> I think you're underestimating how quickly your denominator will overflow?

Well, it depends on how you use it. :-)  I agree you have to go into
this knowing the risks of the representation (but then I'd argue that's
true for floats/sreals too, if you use them for costs).

> So I suppose all factors of all possible denominators are known, in fact
> whats your main source for the divisions?  The VF?

Yeah, the set of possible dominators is fixed at compile time and
relatively small, but not easily enumerable.  The VF is one source,
but we also have “number of X per cycle” values.  The problem with sreal
is that sometimes those “X per cycle” values are 3, and 1/3 is where the
rounding problems with floats/sreals start to come in.

I'm fairly sure that using a uint64_t fractional representation for
int costs and these set of denominator values is safe.  But if we
think that this is just too dangerous to advertise as a general
class within GCC, we could make it local to the aarch64 cost code
instead.  Would that be OK?

Thanks,
Richard


More information about the Gcc-patches mailing list