[RFC] Add a simple soft-float class

I'm certainly not suggesting this would be better in general than IEEE 754.

But I think it's suitable for the sorts of places we currently use
hard-floats. I guess you (and Philip) are saying there are dragons here?

Numerical analysis is hard. Every numerics expert I have ever worked with considers trying to re-invent floating point a cardinal sin of numerical analysis. Just don’t do it. You will miss important considerations, and you will pay the price for it later. Plus, anyone in the future who wants to modify your code has to learn a new set of non-standard floating point numerics, and without a well-defined specification it’s not always clear what the correct semantics in a particular case are.

Although "making APFloat not suck" might be ideal, we don't have the code
written for that.

I don’t think we should let expedience get in the way of Doing The Right Thing. IMO, there are two real issues with APFloat today:

1) The interface is really clunky. We can fix this by fixing/extending the interface, or by adding a convenience wrapper.

2) It *may* be too slow for this use case. Assuming this is actually true, there’s a lot of room for improvement in APFloat’s performance by special-casing common paths (default rounding mode, normal formats). We could even conceivably detect if we’re compiled for a platform that has sane hard float support and fall back to that transparently.

None of these seem particularly difficult to me, and saves us from a future world of pain. I know Michael Gottesman has some WIP code for cleaning up APFloat. Perhaps he could share it with you?

—Owen

I don't think anyone is planning to use it to write climate models. Or
simulate airflow over a 787. Or even invert a near-singular matrix.

This is for jobs that *could* perfectly well be done with a simple integer
with an implied scale factor, if you could easily and reliably predict in
advance exactly what scale factor is appropriate for each value.

This simply keeps track of the scale factor for you, so you can't get it
wrong.

Perhaps the mistake is in calling it "software floating point" (which
carries a lot of baggage), rather than "automatic scaled integer"?

If you couldn’t get it wrong, we wouldn’t have had so much difficulty getting the current version to work.

—Owen

Non sequitur.

Statically analysing in advance the correct scale factor for all possible
situations and values is super hard.

Given two actual values to be added/multiplied etc, determining the correct
scale factor for that particular result is next to trivial.

I’m not advocating against using a floating point representation. I understand that it’s valuable for this use case. What I vehemently disagree with is the notion that we should design our own (approximation of) floating point. It turns out that that’s really hard, even when you’re not simulating a 787. It’s still important to be able to distinguish between the maximum value of your range and saturation. It’s still valuable to be able to detect when an invariant of the numeric model was violated and you should just throw away the results. It’s still valuable to avoid implicit bypassing of the rounded results so you don’t run into problems when values start to compound.

Making our existing soft float implementation (APFloat) more convenient and faster is a win-win. It solves this particular use case without introducing risk of defining the representation wrong, AND it makes it easier and more convenient to use for other clients within the compiler.

—Owen

Numerical analysis is hard. Every numerics expert I have ever worked with considers trying to re-invent floating point a cardinal sin of numerical analysis. Just don’t do it. You will miss important considerations, and you will pay the price for it later. Plus, anyone in the future who wants to modify your code has to learn a new set of non-standard floating point numerics, and without a well-defined specification it’s not always clear what the correct semantics in a particular case are.

Okay. To me this sounds like dogma, but I'll defer to your judgement.

I don’t think we should let expedience get in the way of Doing The Right Thing.

FWIW, we also balance idealism with pragmatism.

IMO, there are two real issues with APFloat today:

1) The interface is really clunky. We can fix this by fixing/extending the interface, or by adding a convenience wrapper.

2) It *may* be too slow for this use case. Assuming this is actually true, there’s a lot of room for improvement in APFloat’s performance by special-casing common paths (default rounding mode, normal formats). We could even conceivably detect if we’re compiled for a platform that has sane hard float support and fall back to that transparently.

None of these seem particularly difficult to me, and saves us from a future world of pain. I know Michael Gottesman has some WIP code for cleaning up APFloat. Perhaps he could share it with you?

When working on BFI, I considered (1). However, for that use case, I
needed simple saturation of unsigned quantities. The wrapper seemed to be
heading somewhere more bug prone than a simple hand-rolled implementation
(and with as many lines of code), so I switched gears.

You're saying that these semantics were wrong-headed from the get-go.
They were useful for modeling block frequency, but I'm not a numerics
expert.

Making our existing soft float implementation (APFloat) more convenient and faster is a win-win. It solves this particular use case without introducing risk of defining the representation wrong, AND it makes it easier and more convenient to use for other clients within the compiler.

Yup. That'd be good work to do even if UnsignedFloat *were* a good idea.
It's fairly tangential to cleaning up BFI, though, so I won't be tackling
it right now (anyone motivated should go ahead!).

I'll continue with the post-commit plan for BFI that Chandler, Andy and I
mapped out, which was/is something like this:

  - Model the "bias" metric.
  - Approximate loop scales by their lg (with a special case for 3) and
    reorganize calculations to avoid quantities less than 1/UINT64_MAX.
  - Factor out the useful parts of UnsignedFloat into helper functions
    that actually have tests in tree.
  - Replace uses of UnsignedFloat with helpers (and delete its shell).
  - Look at sharing float-like helper algorithms with APFloat.

-- dpnes

Is there any way we have this utility and just not claim that it is for use with a numerics package? The only claim we’re making is that it is a useful utility for writing compiler heuristics. We can do that without waking any Dragons, and Duncan’s design is quite straightforward.

I think calling it a “soft-float” implementation was a mistake (even though that’s what it is), and has completely derailed this thread.

The goal is to factor and reuse the code that we need to reinvent every time we need to extend the dynamic range of some of cost metric. The question here is whether that in itself a worthwhile goal, independent of how the compiler models language level floats. I have nothing against repurposing APFloat. After all, we only have a couple metrics in tree that need this new utility. But let’s be clear that APFloat’s purpose is completely different, so it’s not like we’re reinventing any existing utility.

I honestly think we should consider not calling this a Float at all just to avoid the obvious confusion. I’m fine calling it a ScaledNumber or something.

-Andy

Thanks Andy for refocusing the discussion.

This is not a float. This is not a replacement for a APFloat, and it is not a
numerics library (or the start of one). It's a number with a scale that has simple
integer-like semantics, useful for extending the dynamic range of cost metrics.

Owen and I talked off-line, and he's okay with this going in the tree with a couple
of conditions:

1. The name matters. The biggest danger here is that someone sees this and thinks
    it's appropriate for general numerics, or otherwise "bigger than it is".

    A couple of ideas are "UnsignedScalar" (too generic?) and "CostMetric" (too
    specific?).

2. Header docs should clearly describe the restricted problem domain appropriate
    to this class, and should forward those looking for a soft-float to `APFloat`.

For now I'm going with `CostMetric` in `include/llvm/Support/CostMetric.h` and
`lib/Support/CostMetric.cpp`. I'll start by extracting helper functions into the
same files in the `llvm::CostMetrics` namespace, and then eventually rename the class
to `llvm::CostMetric` and move it over.

*enable-bikeshed-mode* [All the names are wrong. Paint them?]

I don't really have a problem with the direction, but...

Is there any way we have this utility and just not claim that it is for use with a numerics package? The only claim we’re making is that it is a useful utility for writing compiler heuristics. We can do that without waking any Dragons, and Duncan’s design is quite straightforward.

I think calling it a “soft-float” implementation was a mistake (even though that’s what it is), and has completely derailed this thread.

The goal is to factor and reuse the code that we need to reinvent every time we need to extend the dynamic range of some of cost metric. The question here is whether that in itself a worthwhile goal, independent of how the compiler models language level floats. I have nothing *against* repurposing APFloat. After all, we only have a couple metrics in tree that need this new utility. But let’s be clear that APFloat's purpose is completely different, so it’s not like we’re reinventing any existing utility.

I honestly think we should consider not calling this a Float at all just to avoid the obvious confusion. I’m fine calling it a ScaledNumber or something.

Thanks Andy for refocusing the discussion.

This is not a float. This is not a replacement for a APFloat, and it is not a
numerics library (or the start of one). It's a number with a scale that has simple
integer-like semantics, useful for extending the dynamic range of cost metrics.

Owen and I talked off-line, and he's okay with this going in the tree with a couple
of conditions:

1. The name matters. The biggest danger here is that someone sees this and thinks
   it's appropriate for general numerics, or otherwise "bigger than it is".

   A couple of ideas are "UnsignedScalar" (too generic?) and "CostMetric" (too
   specific?).

2. Header docs should clearly describe the restricted problem domain appropriate
   to this class, and should forward those looking for a soft-float to `APFloat`.

For now I'm going with `CostMetric` in `include/llvm/Support/CostMetric.h` and
`lib/Support/CostMetric.cpp`. I'll start by extracting helper functions into the
same files in the `llvm::CostMetrics` namespace, and then eventually rename the class
to `llvm::CostMetric` and move it over.

I agree with taking a pragmatic approach on this. Making APFloat sucking less so we can eventually replacing this UnsignedFloat package should be a longer term goal. But it should not block short term progress.

Evan

>
> Is there any way we have this utility and just not claim that it is for
use with a numerics package? The only claim we’re making is that it is a
useful utility for writing compiler heuristics. We can do that without
waking any Dragons, and Duncan’s design is quite straightforward.
>
> I think calling it a “soft-float” implementation was a mistake (even
though that’s what it is), and has completely derailed this thread.
>
> The goal is to factor and reuse the code that we need to reinvent every
time we need to extend the dynamic range of some of cost metric. The
question here is whether that in itself a worthwhile goal, independent of
how the compiler models language level floats. I have nothing *against*
repurposing APFloat. After all, we only have a couple metrics in tree that
need this new utility. But let’s be clear that APFloat's purpose is
completely different, so it’s not like we’re reinventing any existing
utility.
>
> I honestly think we should consider not calling this a Float at all just
to avoid the obvious confusion. I’m fine calling it a ScaledNumber or
something.

Thanks Andy for refocusing the discussion.

This is not a float. This is not a replacement for a APFloat, and it is
not a
numerics library (or the start of one). It's a number with a scale that
has simple
integer-like semantics, useful for extending the dynamic range of cost
metrics.

Owen and I talked off-line, and he's okay with this going in the tree with
a couple
of conditions:

1. The name matters. The biggest danger here is that someone sees this
and thinks
    it's appropriate for general numerics, or otherwise "bigger than it
is".

    A couple of ideas are "UnsignedScalar" (too generic?) and "CostMetric"
(too
    specific?).

2. Header docs should clearly describe the restricted problem domain
appropriate
    to this class, and should forward those looking for a soft-float to
`APFloat`.

For now I'm going with `CostMetric` in `include/llvm/Support/CostMetric.h`
and
`lib/Support/CostMetric.cpp`. I'll start by extracting helper functions
into the
same files in the `llvm::CostMetrics` namespace, and then eventually
rename the class
to `llvm::CostMetric` and move it over.

*enable-bikeshed-mode* [All the names are wrong. Paint them?]

my 2c: describe it as "an approximate, high-dynamic-range unsigned integer".

That doesn't lend itself to something easy to type, but "ApproxHDRUint"
might be doable. Plus, it sounds sort of scary.

Having something in the name that suggests that it is an integer should
ward off any attempt to use it for numerics.

-- Sean Silva

I would suggest that "high-dynamic-range" is also the wrong word. It
is not actually providing any extra dynamic range.
Having something that can go from 0 to 20 in steps of 2 has no better
dynamic range as something that can go from 0 to 10 in steps of 1.
Simply calling it "scaled unsigned integer" is more accurate.
Or "unsigned integer with scale factor".

I think it would also be a good idea to explain what maths operations
you are likely to want to do.
For example, if the number is 20, with scale factor 2, and you add 1
with scale factor 1 to it, the answer is undefined.
If all you are going to do is somehow reach a value and then is won't
change, and the only operations you are going to do are "compare"
operations, then that is something that is easier to understand for
other programmers.

Just out of curiosity, what is the requirement or use case that is
driving a "scaled unsigned integer" instead of say just using an
integer with more bits.

James

Hello James, hello folks!

> Simply calling it "scaled unsigned integer" is more accurate.
> Or "unsigned integer with scale factor".

Stupid question: Why only unsigned?
Doesn't such a construct make also sense for signed numbers?
What about scaled floats?

Best regards
Jasper

>
>
> my 2c: describe it as "an approximate, high-dynamic-range unsigned
integer".
>
> That doesn't lend itself to something easy to type, but "ApproxHDRUint"
> might be doable. Plus, it sounds sort of scary.
>
> Having something in the name that suggests that it is an integer should
ward
> off any attempt to use it for numerics.
>
> -- Sean Silva
>

I would suggest that "high-dynamic-range" is also the wrong word. It
is not actually providing any extra dynamic range.

Dynamic range is the ratio between the largest and smallest representable
value (see http://en.wikipedia.org/wiki/Dynamic_range). So yes it does
provide more dynamic range; in fact, pretty much the entire purpose of
using floating point numbers is to extend the dynamic range (see
http://en.wikipedia.org/wiki/Floating_point).

What changes is the distribution of the numbers; they are no longer
uniformly distributed (see Knuth 4.2.4 "Distribution of Floating Point
Numbers" or google for "distribution of floating point numbers").

-- Sean Silva

From: llvmdev-bounces@cs.uiuc.edu [mailto:llvmdev-bounces@cs.uiuc.edu] On
Behalf Of James Courtier-Dutton

I think it would also be a good idea to explain what maths operations
you are likely to want to do.
For example, if the number is 20, with scale factor 2, and you add 1
with scale factor 1 to it, the answer is undefined.

"Undefined" is too strong a term here. Typically with scaled arithmetic
you'd do all operations in a sufficiently wide representation that you
compute the correct pure numerical result, and then possibly modify
that result as needed (may include rounding) to match the desired output
scale. You can do the operations with narrower representations if you
can prove that the scaled result would be unaffected.

That is: adding 10 to 0.1 and asking for an integer result is not an
undefined operation; it will yield the well-defined value 10.

Just out of curiosity, what is the requirement or use case that is
driving a "scaled unsigned integer" instead of say just using an
integer with more bits.

It's more compact, and often the low-order bits of a large result are
not particularly relevant.
--paulr