llvm dev - Jun 2014 - [LLVMdev] [RFC] Add a simple soft-float class

I'm currently working on stripping usage of `UnsignedFloat` out of
`-block-freq`.  Before I finish...

I propose adding a soft-float class to llvm/Support/ or llvm/Analysis/.

  - Portable (unlike hard-floats).
      - Well-defined for all platforms and safe to use in code.

  - Easy to use and reason about (unlike `APFloat`).
      - Uses operators.
      - No special numbers.
      - Every operation well-defined (even divide-by-zero).
      - No rounding modes.
      - Digits represented simply as a 32-bit or 64-bit integer.

  - Lowers barrier to entry for writing passes with weight-like logic
    (and other uses of numbers).
      - Mapping to `uint64_t` is often a hard problem in itself.
      - First iteration can focus on the pass logic; second iteration
        can remove the floats.

  - Already written and (mostly) tested.
      - There's currently one in `-block-freq` called `UnsignedFloat`.
        Tests are out of tree, though.

IIUC, the consensus here is:  hard-floats are worse than soft-floats,
and both are worse integers.  However, we have passes in the tree (e.g.,
spill placement) that use hard-floats anyway.

With a small amount of effort, I can finish testing `UnsignedFloat`
(and/or `SignedFloat`) and we can remove hard-floats entirely by using
these classes as drop-in replacements.  The long-term answer (for most
passes) is mapping to `uint64_t`, but this gets rid of undefined
behaviour *now*, and provides a simple and practical alternative to
hard-floats going forward.

Thoughts?

-- dpnes

On Jun 17, 2014, at 6:34 PM, Duncan P. N. Exon Smith <dexonsmith at
apple.com> wrote:
> I'm currently working on stripping usage of `UnsignedFloat` out of
> `-block-freq`.  Before I finish...
> 
> I propose adding a soft-float class to llvm/Support/ or llvm/Analysis/.
> 
>  - Portable (unlike hard-floats).
>      - Well-defined for all platforms and safe to use in code.
> 
>  - Easy to use and reason about (unlike `APFloat`).
>      - Uses operators.
>      - No special numbers.
>      - Every operation well-defined (even divide-by-zero).
>      - No rounding modes.
>      - Digits represented simply as a 32-bit or 64-bit integer.
> 
>  - Lowers barrier to entry for writing passes with weight-like logic
>    (and other uses of numbers).
>      - Mapping to `uint64_t` is often a hard problem in itself.
>      - First iteration can focus on the pass logic; second iteration
>        can remove the floats.
> 
>  - Already written and (mostly) tested.
>      - There's currently one in `-block-freq` called `UnsignedFloat`.
>        Tests are out of tree, though.
> 
> IIUC, the consensus here is:  hard-floats are worse than soft-floats,
> and both are worse integers.  However, we have passes in the tree (e.g.,
> spill placement) that use hard-floats anyway.
> 
> With a small amount of effort, I can finish testing `UnsignedFloat`
> (and/or `SignedFloat`) and we can remove hard-floats entirely by using
> these classes as drop-in replacements.  The long-term answer (for most
> passes) is mapping to `uint64_t`, but this gets rid of undefined
> behaviour *now*, and provides a simple and practical alternative to
> hard-floats going forward.
> 
> Thoughts?
I would just like to preemptively reject any argument that having a convenient
soft-float is bad because it discourages moving to a more efficient fixed-point
representation. The evidence shows otherwise. It took two years to get a working
fixed point representation for block frequency and still don’t have one for
spill weight. We should have been using a convenient and relatively efficient
soft-float, as you have implemented, all this time. In the case of block
frequency we would have been able to focus on design and fixing the algorithm
instead of representational problems from the beginning. In the case of spill
weight, I believe it would have made it more apparent and obvious that we still
need to develop a better representation, and we wouldn’t have wasted time
debugging buildbot unpredictability.

I think it should be easy to develop new passes incrementally without setting up
barriers. Your soft-float will help. Beyond that I have absolutely no opinion on
its naming or location.

-Andy

If we require the host to have sse2 or other IEEE 754 conformant 
implementation, would it be possible to use hardware float?

Sent from my iPhone
> On Jun 17, 2014, at 21:34, "Duncan P. N. Exon Smith"
<dexonsmith at apple.com> wrote:
> 
> I'm currently working on stripping usage of `UnsignedFloat` out of
> `-block-freq`.  Before I finish...
> 
> I propose adding a soft-float class to llvm/Support/ or llvm/Analysis/.
> 
>  - Portable (unlike hard-floats).
>      - Well-defined for all platforms and safe to use in code.
> 
>  - Easy to use and reason about (unlike `APFloat`).
>      - Uses operators.
>      - No special numbers.
>      - Every operation well-defined (even divide-by-zero).
>      - No rounding modes.
>      - Digits represented simply as a 32-bit or 64-bit integer.
> 
>  - Lowers barrier to entry for writing passes with weight-like logic
>    (and other uses of numbers).
>      - Mapping to `uint64_t` is often a hard problem in itself.
>      - First iteration can focus on the pass logic; second iteration
>        can remove the floats.
> 
>  - Already written and (mostly) tested.
>      - There's currently one in `-block-freq` called `UnsignedFloat`.
>        Tests are out of tree, though.
> 
> IIUC, the consensus here is:  hard-floats are worse than soft-floats,
> and both are worse integers.  However, we have passes in the tree (e.g.,
> spill placement) that use hard-floats anyway.
> 
> With a small amount of effort, I can finish testing `UnsignedFloat`
> (and/or `SignedFloat`) and we can remove hard-floats entirely by using
> these classes as drop-in replacements.  The long-term answer (for most
> passes) is mapping to `uint64_t`, but this gets rid of undefined
> behaviour *now*, and provides a simple and practical alternative to
> hard-floats going forward.
> 
> Thoughts?
> 
> -- dpnes
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

Hi Duncan,

Some of these don’t make a lot of sense:
>  - Easy to use and reason about (unlike `APFloat`).
>      - Uses operators.
>      - No special numbers.
What semantics do you propose to use instead?  At some point, people will hit
the boundaries of their range, and you need to do something sensible there.
>      - Every operation well-defined (even divide-by-zero).
Divide-by-zero is actually well-defined in IEEE 754:
	x / +0.0 == +Inf
	x / -0.0 == -Inf
	(-)0.0 / (-)0.0 ==  NaN
>      - No rounding modes.
You can’t implement a finite precision floating point representation without any
rounding.  I assume what you mean here is only one rounding mode, i.e.
round-nearest-ties-to-even.
>      - Digits represented simply as a 32-bit or 64-bit integer.

Isn’t this the same as the significand of an IEEE float?  If you go with 64-bit,
it sounds like you’re defining something very close to Intel’s FP80.

—Owen

-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20140617/3489d2a6/attachment.html>

As I see it:

- float is wanted because often it's too hard to correctly guess the range
of values in advance

- the uses are generally diagnostic or heuristic and the exact
characteristics of rounding in the LSB is unimportant

- it *is* valuable to have the same bit-accurate results (and subsequent
control flow based on it) on different platforms, regardless of whether or
what FP hardware they have.

- higher performance is better, but if you need software FP anywhere then
it's useful to make that software FP as fast as possible.

- if the software FP is fast enough (even if not fully IEEE754 conformant)
then the penalty for not using hardware FP is not all that large.

Therefore: if you're going to transparently use IEEE754 hardware where
available, then you also have to make the software implementation
bit-accurate to IEEE754 standards.

That puts a (perhaps unnecessary) performance penalty on the software FP.

It would be useful to have numbers for how much penalty.

In the presence of fast full result integer multiply, fast shifts by
variable amounts, and (possibly) count-leading-zeroes you can do a
non-IEEE754 software FP add in maybe a dozen clock cycles.


On Wed, Jun 18, 2014 at 4:11 PM, Rafael Avila de Espindola <
rafael.espindola at gmail.com> wrote:
> If we require the host to have sse2 or other IEEE 754 conformant
>  implementation, would it be possible to use hardware float?
>
> Sent from my iPhone
>
> > On Jun 17, 2014, at 21:34, "Duncan P. N. Exon Smith" <
> dexonsmith at apple.com> wrote:
> >
> > I'm currently working on stripping usage of `UnsignedFloat` out of
> > `-block-freq`.  Before I finish...
> >
> > I propose adding a soft-float class to llvm/Support/ or
llvm/Analysis/.
> >
> >  - Portable (unlike hard-floats).
> >      - Well-defined for all platforms and safe to use in code.
> >
> >  - Easy to use and reason about (unlike `APFloat`).
> >      - Uses operators.
> >      - No special numbers.
> >      - Every operation well-defined (even divide-by-zero).
> >      - No rounding modes.
> >      - Digits represented simply as a 32-bit or 64-bit integer.
> >
> >  - Lowers barrier to entry for writing passes with weight-like logic
> >    (and other uses of numbers).
> >      - Mapping to `uint64_t` is often a hard problem in itself.
> >      - First iteration can focus on the pass logic; second iteration
> >        can remove the floats.
> >
> >  - Already written and (mostly) tested.
> >      - There's currently one in `-block-freq` called
`UnsignedFloat`.
> >        Tests are out of tree, though.
> >
> > IIUC, the consensus here is:  hard-floats are worse than soft-floats,
> > and both are worse integers.  However, we have passes in the tree
(e.g.,
> > spill placement) that use hard-floats anyway.
> >
> > With a small amount of effort, I can finish testing `UnsignedFloat`
> > (and/or `SignedFloat`) and we can remove hard-floats entirely by using
> > these classes as drop-in replacements.  The long-term answer (for most
> > passes) is mapping to `uint64_t`, but this gets rid of undefined
> > behaviour *now*, and provides a simple and practical alternative to
> > hard-floats going forward.
> >
> > Thoughts?
> >
> > -- dpnes
> > _______________________________________________
> > LLVM Developers mailing list
> > LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20140618/5f66b9a9/attachment.html>

On Wed, Jun 18, 2014 at 4:59 PM, Owen Anderson <resistor at mac.com>
wrote:
>      - Digits represented simply as a 32-bit or 64-bit integer.
>
>
> Isn’t this the same as the significand of an IEEE float?  If you go with
> 64-bit, it sounds like you’re defining something very close to Intel’s
FP80.
>
Yes, that would be very similar in practical terms to x86/68k FP80, but
just without the necessity of spending time guaranteeing precisely the same
NaN or norm/denorm or LSB results as x87 hardware.

You'd have 9 or 11 more bits of mantissa than in standard IEEE too, which
is probably more useful than worrying about slight fuzziness in the LSB —
 especially as the results would be precisely the same everywhere.
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20140618/8b02a3bb/attachment.html>

> On 2014 Jun 17, at 21:11, Rafael Avila de Espindola <rafael.espindola at
gmail.com> wrote:
> 
> If we require the host to have sse2 or other IEEE 754 conformant 
implementation, would it be possible to use hardware float?
I'm not sure what's stopping us -- I just know they don't work well.

See responses to Andy's suggestion in March [1] and the ugly patch [2] I
committed in r206765 for some other context.

[1]:
http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20140317/209336.html
[2]:
http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20140421/213726.html

> On 2014 Jun 17, at 21:59, Owen Anderson <resistor at mac.com> wrote:
> 
> Hi Duncan,
> 
> Some of these don’t make a lot of sense:
Sorry -- I think I was assuming too much knowledge about what I committed as
part of the BlockFrequencyInfo rewrite.

What's committed there is a class called UnsignedFloat that wraps the
following with a bunch of API:

    template <class UIntT> struct UnsignedFloat {
        UIntT Digits;
        uint16_t Exponent;
    };

There are some static asserts to restrict UIntT to either `uint32_t` or
`uint64_t`.  I have tests that are out of tree.  The `uint32_t` version uses
64-bit math for divide and multiply while the `uint64_t` version uses long
division etc. -- otherwise they share implementation.  They both defer to
APFloat for non-trivial string conversion.

I don't think it will be much work to clean this up and create a SignedFloat
variant that adds a `bool` for the sign (and shares most of the impl).

I'll respond to your specific points inline.
> 
>>  - Easy to use and reason about (unlike `APFloat`).
>>      - Uses operators.
>>      - No special numbers.
> 
> What semantics do you propose to use instead?  At some point, people will
hit the boundaries of their range, and you need to do something sensible there.
Simple saturation.
>>      - Every operation well-defined (even divide-by-zero).
> 
> Divide-by-zero is actually well-defined in IEEE 754:
> 	x / +0.0 == +Inf
> 	x / -0.0 == -Inf
> 	(-)0.0 / (-)0.0 ==  NaN
Point taken!
>>      - No rounding modes.
> 
> You can’t implement a finite precision floating point representation
without any rounding.  I assume what you mean here is only one rounding mode,
i.e. round-nearest-ties-to-even.
Yes.  I was emphasizing that rounding modes aren't part of the API.
>>      - Digits represented simply as a 32-bit or 64-bit integer.
> 
> Isn’t this the same as the significand of an IEEE float?  If you go with
64-bit, it sounds like you’re defining something very close to Intel’s FP80.
Yup.  The `uint64_t` version is similar to a non-conforming and slow FP80
that's always in denormal mode, but the *same* non-conforming on every
platform.

This may be a stupid question, but I didn't see it addressed anywhere.

Why not just use APFloat? (maybe even APInt would be sufficient for the
desired semantics?)

Is it purely a performance concern? Because it seems like you (and Andy)
are supporting this as a suboptimal but convenient replacement for a proper
integer-based representation. On the other hand, if it's just a performance
optimization over APFloat/APInt, then this soft-float thing becomes quick
hack + optimization which is a combination that gives me a pretty bad gut
feeling (but may still be warranted, of course).

-- Sean Silva




On Tue, Jun 17, 2014 at 7:34 PM, Duncan P. N. Exon Smith <
dexonsmith at apple.com> wrote:
> I'm currently working on stripping usage of `UnsignedFloat` out of
> `-block-freq`.  Before I finish...
>
> I propose adding a soft-float class to llvm/Support/ or llvm/Analysis/.
>
>   - Portable (unlike hard-floats).
>       - Well-defined for all platforms and safe to use in code.
>
>   - Easy to use and reason about (unlike `APFloat`).
>       - Uses operators.
>       - No special numbers.
>       - Every operation well-defined (even divide-by-zero).
>       - No rounding modes.
>       - Digits represented simply as a 32-bit or 64-bit integer.
>
>   - Lowers barrier to entry for writing passes with weight-like logic
>     (and other uses of numbers).
>       - Mapping to `uint64_t` is often a hard problem in itself.
>       - First iteration can focus on the pass logic; second iteration
>         can remove the floats.
>
>   - Already written and (mostly) tested.
>       - There's currently one in `-block-freq` called `UnsignedFloat`.
>         Tests are out of tree, though.
>
> IIUC, the consensus here is:  hard-floats are worse than soft-floats,
> and both are worse integers.  However, we have passes in the tree (e.g.,
> spill placement) that use hard-floats anyway.
>
> With a small amount of effort, I can finish testing `UnsignedFloat`
> (and/or `SignedFloat`) and we can remove hard-floats entirely by using
> these classes as drop-in replacements.  The long-term answer (for most
> passes) is mapping to `uint64_t`, but this gets rid of undefined
> behaviour *now*, and provides a simple and practical alternative to
> hard-floats going forward.
>
> Thoughts?
>
> -- dpnes
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20140618/8769919e/attachment.html>

On Tue, Jun 17, 2014 at 10:11 PM, Rafael Avila de Espindola <
rafael.espindola at gmail.com> wrote:
> If we require the host to have sse2 or other IEEE 754 conformant
>  implementation, would it be possible to use hardware float?
>
I don't think that IEEE 754 actually guarantees bit-exact results in all
cases.

-- Sean Silva

>
> Sent from my iPhone
>
> > On Jun 17, 2014, at 21:34, "Duncan P. N. Exon Smith" <
> dexonsmith at apple.com> wrote:
> >
> > I'm currently working on stripping usage of `UnsignedFloat` out of
> > `-block-freq`.  Before I finish...
> >
> > I propose adding a soft-float class to llvm/Support/ or
llvm/Analysis/.
> >
> >  - Portable (unlike hard-floats).
> >      - Well-defined for all platforms and safe to use in code.
> >
> >  - Easy to use and reason about (unlike `APFloat`).
> >      - Uses operators.
> >      - No special numbers.
> >      - Every operation well-defined (even divide-by-zero).
> >      - No rounding modes.
> >      - Digits represented simply as a 32-bit or 64-bit integer.
> >
> >  - Lowers barrier to entry for writing passes with weight-like logic
> >    (and other uses of numbers).
> >      - Mapping to `uint64_t` is often a hard problem in itself.
> >      - First iteration can focus on the pass logic; second iteration
> >        can remove the floats.
> >
> >  - Already written and (mostly) tested.
> >      - There's currently one in `-block-freq` called
`UnsignedFloat`.
> >        Tests are out of tree, though.
> >
> > IIUC, the consensus here is:  hard-floats are worse than soft-floats,
> > and both are worse integers.  However, we have passes in the tree
(e.g.,
> > spill placement) that use hard-floats anyway.
> >
> > With a small amount of effort, I can finish testing `UnsignedFloat`
> > (and/or `SignedFloat`) and we can remove hard-floats entirely by using
> > these classes as drop-in replacements.  The long-term answer (for most
> > passes) is mapping to `uint64_t`, but this gets rid of undefined
> > behaviour *now*, and provides a simple and practical alternative to
> > hard-floats going forward.
> >
> > Thoughts?
> >
> > -- dpnes
> > _______________________________________________
> > LLVM Developers mailing list
> > LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20140618/8313737e/attachment.html>

> On 2014 Jun 18, at 09:29, Sean Silva <chisophugis at gmail.com>
wrote:
> 
> Why not just use APFloat? (maybe even APInt would be sufficient for the
desired semantics?)
APFloat's API is awkward to use when doing math -- it's designed for
compiling and optimizing code that uses floats, not for use as a simple
number representation.

It is possible to wrap APFloat though.
> Is it purely a performance concern?
Largely (assuming the other option is wrapping APFloat).

Also, wrapping APFloat to give similar semantics is a fair bit a work.

UnsignedFloat interoperates well with integers -- it's easy to compose out
of (and decompose into) exponent and digit parts.  Again, this is API that
could be added as a wrapper around APFloat.
> Because it seems like you (and Andy) are supporting this as a suboptimal
but convenient replacement for a proper integer-based representation.
In a way, but I think of it as a suboptimal but safe replacement for
hardware floats.  We currently use hardware floats as a suboptimal but
convenient replacement for proper integer-based representations -- I'd like
to swap in a soft-float instead.

For some problems, proper integer-based representations are really hard,
and can resemble a poor man's soft-float even when done right.
> On the other hand, if it's just a performance optimization over
APFloat/APInt, then this soft-float thing becomes quick hack + optimization
which is a combination that gives me a pretty bad gut feeling (but may still be
warranted, of course).
It's a performance optimization over: a heavily wrapped APFloat to give it
simple semantics.  Not sure if that gives you a better feeling...