llvm dev - Apr 2016 - Implementing a proposed InstCombine optimization

> I am not entirely sure this is safe. Transforming this to an fsub could
change the value stored on platforms that implement negates using arithmetic
instead of with bitmath (such as ours)
I think it's probably safe for IEEE754-2008 conformant platforms because
negation was clarified to be a non-arithmetic bit flip that cannot cause
exceptions in that specification. However, I'm sure it's unsafe for some
IEEE754-1985 platforms because it introduces exceptions when given a NaN.

On MIPS, the semantics for negation depend on a configuration bit (ABS2008) but
in practice the majority of MIPS environments use arithmetic negation and
trigger exceptions when negating a NaN. That said, the most recently published
MIPS specifications require non-arithmetic negation and drop support for the
IEEE754-1985 standard.
> This could introduce new FP exceptions. It's also likely to be much
worse on platforms with no FPU like early MIPS.
Quite a few modern implementations too. MIPS is often used in domains where
having an FPU would be wasteful.

From: llvm-dev [mailto:llvm-dev-bounces at lists.llvm.org] On Behalf Of Alex
Rosenberg via llvm-dev
Sent: 09 April 2016 02:44
To: escha at apple.com
Cc: Carlos Liam; llvm-dev
Subject: Re: [llvm-dev] Implementing a proposed InstCombine optimization

This doesn't seem like a good idea to me. There are many architectures where
those bitcasts are free operations and the xor will be executed in a shorter
pipe than any FP op would. Cell SPU, for example.

This could introduce new FP exceptions. It's also likely to be much worse on
platforms with no FPU like early MIPS.

Alex

On Apr 7, 2016, at 9:43 AM, via llvm-dev <llvm-dev at
lists.llvm.org<mailto:llvm-dev at lists.llvm.org>> wrote:
I am not entirely sure this is safe. Transforming this to an fsub could change
the value stored on platforms that implement negates using arithmetic instead of
with bitmath (such as ours) and either canonicalize NaNs or don’t support
denormals. This is actually important because this kind of bitmath on floats is
very commonly used as part of algorithms for complex math functions that need to
get precise bit patterns from the source (similarly for the transformation of
masking off the sign bit -> fabs). It’s also important because if the float
happens to “really” be an integer, it’s highly likely we’ll end up zero-flushing
it and losing the data.

Example:

a = load float
b = bitcast a to int
c = xor b, signbit
d = bitcast c to float
store d

Personally I would feel this is safe if and only if the float is coming from an
arithmetic operation — in that case, we know that doing another arithmetic
operation on it should be safe, since it’s already canonalized and can’t be a
denorm [if the platform doesn’t support them].

I say this coming only a few weeks after our team spent literally dozens of
human-hours tracking down an extremely obscure bug involving a GL conformance
test in which ints were casted to floats, manipulated with float instructions,
then sent back to int, resulting in the ints being flushed to zero and the test
failing.

—escha

On Apr 7, 2016, at 9:09 AM, Sanjay Patel via llvm-dev <llvm-dev at
lists.llvm.org<mailto:llvm-dev at lists.llvm.org>> wrote:

Hi Carlos -
That sounds like a good patch.
Warning - following the link below may remove some of the educational joy for
the immediate task at hand:
http://reviews.llvm.org/D13076
...but I wouldn't worry too much, there's plenty more opportunity where
that came from. :)

Feel free to post follow-up questions here or via a patch review on Phabricator:
http://llvm.org/docs/Phabricator.html


On Thu, Apr 7, 2016 at 7:17 AM, Carlos Liam via llvm-dev <llvm-dev at
lists.llvm.org<mailto:llvm-dev at lists.llvm.org>> wrote:
Hi,

I'm interested in implementing an InstCombine optimization that I discovered
and verified with Alive-NJ (with the help of the authors of Alive-NJ). The
optimization is described in Alive-NJ format as follows:

Name: xor->fsub
Pre: isSignBit(C)
%x = bitcast %A
%y = xor %x, C
%z = bitcast %y
=>
%z = fsub -0.0, %A

Effectively the optimization targets code that casts a float to an int with the
same width, XORs the sign bit, and casts back to float, and replaces it with a
subtraction from -0.0.

I am not very familiar with C++ or the LLVM codebase so I would greatly
appreciate some help in writing a patch adding this optimization.

Thanks in advance.

 - CL

_______________________________________________
LLVM Developers mailing list
llvm-dev at lists.llvm.org<mailto:llvm-dev at lists.llvm.org>
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev

_______________________________________________
LLVM Developers mailing list
llvm-dev at lists.llvm.org<mailto:llvm-dev at lists.llvm.org>
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev

_______________________________________________
LLVM Developers mailing list
llvm-dev at lists.llvm.org<mailto:llvm-dev at lists.llvm.org>
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160411/6cb54f37/attachment.html>

> On Apr 11, 2016, at 4:23 AM, Daniel Sanders <Daniel.Sanders at
imgtec.com> wrote:
> 
> > I am not entirely sure this is safe. Transforming this to an fsub
could change the value stored on platforms that implement negates using
arithmetic instead of with bitmath (such as ours)
>  
> I think it's probably safe for IEEE754-2008 conformant platforms
because negation was clarified to be a non-arithmetic bit flip that cannot cause
exceptions in that specification.

I did some digging into IEEE-754 and it seems like this is actually not even
safe on fully conformant IEEE-754-2008 platforms.

5.5.1 Sign bit operations
5.5.1.0 Implementations shall provide the following homogeneous
quiet-computational sign bit operations for all supported arithmetic formats;
they only affect the sign bit. The operations treat floating-point numbers and
NaNs alike, and signal no exception. These operations may propagate
non-canonical encodings.

copy(x) copies a floating-point operand x to a destination in the same format,
with no change to the sign bit.
negate(x) copies a floating-point operand x to a destination in the same format,
reversing the sign bit. negate(x) is not the same as subtraction(0, x) (see
6.3).

Note the MAY. fneg is required to flip the top bit even if the input is a NaN.
But fneg is not required to maintain the other bits. If the input is a
non-canonical NaN, the fneg MAY canonicalize it. In fact, even the ‘copy’ MAY
canonicalize it. (it also MAY choose to not canonicalize it)

Thus, if the integer being fneg’d is a non-canonical NaN, fneg MAY modify bits
other than the top bit.

—escha
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160411/f7072b22/attachment.html>

I just wanted to stress this for future discussions: One important goal of the
intermediate representation is to normalize the program.
If something can be represented by two equivalent IR constructs then in general
we should try to choose one variant as normal form and transform to that!

If it turns out that it is the wrong variant for the target, we can still
transform into the other direction during code selection. Of course this rule
cannot universally be applied if reversing the operation in the backend is
unreasonable.

(and of course for this specific case we have to decide first whether the two
patterns are equivalent anyway given existing llvm backends)

- Matthias
> On Apr 11, 2016, at 12:55 PM, via llvm-dev <llvm-dev at
lists.llvm.org> wrote:
> 
> 
>> On Apr 11, 2016, at 4:23 AM, Daniel Sanders <Daniel.Sanders at
imgtec.com <mailto:Daniel.Sanders at imgtec.com>> wrote:
>> 
>> > I am not entirely sure this is safe. Transforming this to an fsub
could change the value stored on platforms that implement negates using
arithmetic instead of with bitmath (such as ours)
>>  
>> I think it's probably safe for IEEE754-2008 conformant platforms
because negation was clarified to be a non-arithmetic bit flip that cannot cause
exceptions in that specification.
> 
> 
> I did some digging into IEEE-754 and it seems like this is actually not
even safe on fully conformant IEEE-754-2008 platforms.
> 
> 5.5.1 Sign bit operations
> 5.5.1.0 Implementations shall provide the following homogeneous
quiet-computational sign bit operations for all supported arithmetic formats;
they only affect the sign bit. The operations treat floating-point numbers and
NaNs alike, and signal no exception. These operations may propagate
non-canonical encodings.
> 
> copy(x) copies a floating-point operand x to a destination in the same
format, with no change to the sign bit.
> negate(x) copies a floating-point operand x to a destination in the same
format, reversing the sign bit. negate(x) is not the same as subtraction(0, x)
(see 6.3).
> 
> Note the MAY. fneg is required to flip the top bit even if the input is a
NaN. But fneg is not required to maintain the other bits. If the input is a
non-canonical NaN, the fneg MAY canonicalize it. In fact, even the ‘copy’ MAY
canonicalize it. (it also MAY choose to not canonicalize it)
> 
> Thus, if the integer being fneg’d is a non-canonical NaN, fneg MAY modify
bits other than the top bit.
> 
> —escha
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160411/8d973122/attachment.html>

> On Apr 11, 2016, at 12:55 PM, via llvm-dev <llvm-dev at
lists.llvm.org> wrote:
> 
> 
>> On Apr 11, 2016, at 4:23 AM, Daniel Sanders <Daniel.Sanders at
imgtec.com <mailto:Daniel.Sanders at imgtec.com>> wrote:
>> 
>> > I am not entirely sure this is safe. Transforming this to an fsub
could change the value stored on platforms that implement negates using
arithmetic instead of with bitmath (such as ours)
>>  
>> I think it's probably safe for IEEE754-2008 conformant platforms
because negation was clarified to be a non-arithmetic bit flip that cannot cause
exceptions in that specification.
> 
> 
> I did some digging into IEEE-754 and it seems like this is actually not
even safe on fully conformant IEEE-754-2008 platforms.
> 
> 5.5.1 Sign bit operations
> 5.5.1.0 Implementations shall provide the following homogeneous
quiet-computational sign bit operations for all supported arithmetic formats;
they only affect the sign bit. The operations treat floating-point numbers and
NaNs alike, and signal no exception. These operations may propagate
non-canonical encodings.
> 
> copy(x) copies a floating-point operand x to a destination in the same
format, with no change to the sign bit.
> negate(x) copies a floating-point operand x to a destination in the same
format, reversing the sign bit. negate(x) is not the same as subtraction(0, x)
(see 6.3).
> 
> Note the MAY. fneg is required to flip the top bit even if the input is a
NaN. But fneg is not required to maintain the other bits. If the input is a
non-canonical NaN, the fneg MAY canonicalize it. In fact, even the ‘copy’ MAY
canonicalize it. (it also MAY choose to not canonicalize it)
> 
> Thus, if the integer being fneg’d is a non-canonical NaN, fneg MAY modify
bits other than the top bit.
> 
> —eschar
[The language frontend plus runtime plus] LLVM is the "implementation”. 
LLVM can define fneg to be a pure signbit operation if we choose to do so.

Also, there are no non-canonical encodings in binary16, binary32, or binary64,
which I believe are what is under discussion on that thread.

– Steve
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160411/55390240/attachment.html>

Good point. The same argument seems to apply to copy() too so I suppose it
depends how strict we want to be about it.

From: fglaser at apple.com [mailto:fglaser at apple.com] On Behalf Of escha at
apple.com
Sent: 11 April 2016 20:55
To: Daniel Sanders
Cc: Alex Rosenberg; llvm-dev at lists.llvm.org; Carlos Liam
Subject: Re: [llvm-dev] Implementing a proposed InstCombine optimization


On Apr 11, 2016, at 4:23 AM, Daniel Sanders <Daniel.Sanders at
imgtec.com<mailto:Daniel.Sanders at imgtec.com>> wrote:
> I am not entirely sure this is safe. Transforming this to an fsub could
change the value stored on platforms that implement negates using arithmetic
instead of with bitmath (such as ours)
I think it's probably safe for IEEE754-2008 conformant platforms because
negation was clarified to be a non-arithmetic bit flip that cannot cause
exceptions in that specification.

I did some digging into IEEE-754 and it seems like this is actually not even
safe on fully conformant IEEE-754-2008 platforms.

5.5.1 Sign bit operations
5.5.1.0 Implementations shall provide the following homogeneous
quiet-computational sign bit operations for all supported arithmetic formats;
they only affect the sign bit. The operations treat floating-point numbers and
NaNs alike, and signal no exception. These operations may propagate
non-canonical encodings.

copy(x) copies a floating-point operand x to a destination in the same format,
with no change to the sign bit.
negate(x) copies a floating-point operand x to a destination in the same format,
reversing the sign bit. negate(x) is not the same as subtraction(0, x) (see
6.3).

Note the MAY. fneg is required to flip the top bit even if the input is a NaN.
But fneg is not required to maintain the other bits. If the input is a
non-canonical NaN, the fneg MAY canonicalize it. In fact, even the ‘copy’ MAY
canonicalize it. (it also MAY choose to not canonicalize it)

Thus, if the integer being fneg’d is a non-canonical NaN, fneg MAY modify bits
other than the top bit.

—escha
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160412/9df355b9/attachment.html>