llvm dev - Jul 2015 - [LLVMdev] Why can't comparisons with negative zero be simplified?

In InstCombineCompares.cpp, routine InstCombiner::FoldFCmp_IntToFP_Cst, there
are these lines:

  // Comparisons with zero are a special case where we know we won't lose
  // information.
  bool IsCmpZero = RHS.isPosZero();

  // If the conversion would lose info, don't hack on this.
  if ((int)InputSize > MantissaWidth && !IsCmpZero)
    return nullptr;

Why check for positive zero instead of checking for any kind of zero?  My
reading of IEEE 754-2008 is that floating-point comparison operations cannot
distinguish a negative zero from a positive zero.  Further supporting this is
that fact that http://llvm.org/docs/LangRef.html describes the difference
between "ordered" and "unordered" as pertaining to QNAN
operands,
with no mention of negative zero.

I tried fixing the issue, but then the following test in cast-int-fcmp-eq-0.ll
fails:

; CHECK-LABEL: @i32_cast_cmp_oeq_int_n0_uitofp(
; CHECK: uitofp
; CHECK: fcmp oeq
define i1 @i32_cast_cmp_oeq_int_n0_uitofp(i32 %i) {
  %f = uitofp i32 %i to float
  %cmp = fcmp oeq float %f, -0.0
  ret i1 %cmp
}

Is this test really justified, or is it just reinforcing an oversight?

- Arch D. Robison
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20150706/d575d72e/attachment.html>

+Matt who is the one that originally committed this (r225265).

-- Sean Silva

On Mon, Jul 6, 2015 at 2:13 PM, Robison, Arch <arch.robison at intel.com>
wrote:
>  In InstCombineCompares.cpp, routine InstCombiner::FoldFCmp_IntToFP_Cst,
> there are these lines:
>
>
>
>   // Comparisons with zero are a special case where we know we won't
lose
>
>   // information.
>
>   bool IsCmpZero = RHS.isPosZero();
>
>
>
>   // If the conversion would lose info, don't hack on this.
>
>   if ((int)InputSize > MantissaWidth && !IsCmpZero)
>
>     return nullptr;
>
>
>
> Why check for positive zero instead of checking for any kind of zero?  My
> reading of IEEE 754-2008 is that floating-point comparison operations
> cannot distinguish a negative zero from a positive zero.  Further
> supporting this is that fact that http://llvm.org/docs/LangRef.html
>
<https://urldefense.proofpoint.com/v2/url?u=http-3A__llvm.org_docs_LangRef.html&d=AwMFAg&c=8hUWFZcy2Z-Za5rBPlktOQ&r=Mfk2qtn1LTDThVkh6-oGglNfMADXfJdty4_bhmuhMHA&m=ZaWNNVon_US-YjLoXztqD5ve4xvIIhIXYdnk3Xqwz8w&s=xonYObEo1TXUyjK3RYC4Pg3kAaSvaYy_Lnvaiq5G1N0&e=>
> describes the difference between “ordered” and “unordered” as pertaining to
> QNAN operands,
>
> with no mention of negative zero.
>
>
>
> I tried fixing the issue, but then the following test in
> cast-int-fcmp-eq-0.ll fails:
>
>
>
> ; CHECK-LABEL: @i32_cast_cmp_oeq_int_n0_uitofp(
>
> ; CHECK: uitofp
>
> ; CHECK: fcmp oeq
>
> define i1 @i32_cast_cmp_oeq_int_n0_uitofp(i32 %i) {
>
>   %f = uitofp i32 %i to float
>
>   %cmp = fcmp oeq float %f, -0.0
>
>   ret i1 %cmp
>
> }
>
>
>
> Is this test really justified, or is it just reinforcing an oversight?
>
>
>
> - Arch D. Robison
>
> _______________________________________________
> 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/20150706/9b0c6074/attachment.html>

It seems like -0 should be fine.


-- Sean Silva

On Mon, Jul 6, 2015 at 2:13 PM, Robison, Arch <arch.robison at intel.com>
wrote:
>  In InstCombineCompares.cpp, routine InstCombiner::FoldFCmp_IntToFP_Cst,
> there are these lines:
>
>
>
>   // Comparisons with zero are a special case where we know we won't
lose
>
>   // information.
>
>   bool IsCmpZero = RHS.isPosZero();
>
>
>
>   // If the conversion would lose info, don't hack on this.
>
>   if ((int)InputSize > MantissaWidth && !IsCmpZero)
>
>     return nullptr;
>
>
>
> Why check for positive zero instead of checking for any kind of zero?  My
> reading of IEEE 754-2008 is that floating-point comparison operations
> cannot distinguish a negative zero from a positive zero.  Further
> supporting this is that fact that http://llvm.org/docs/LangRef.html
>
<https://urldefense.proofpoint.com/v2/url?u=http-3A__llvm.org_docs_LangRef.html&d=AwMFAg&c=8hUWFZcy2Z-Za5rBPlktOQ&r=Mfk2qtn1LTDThVkh6-oGglNfMADXfJdty4_bhmuhMHA&m=ZaWNNVon_US-YjLoXztqD5ve4xvIIhIXYdnk3Xqwz8w&s=xonYObEo1TXUyjK3RYC4Pg3kAaSvaYy_Lnvaiq5G1N0&e=>
> describes the difference between “ordered” and “unordered” as pertaining to
> QNAN operands,
>
> with no mention of negative zero.
>
>
>
> I tried fixing the issue, but then the following test in
> cast-int-fcmp-eq-0.ll fails:
>
>
>
> ; CHECK-LABEL: @i32_cast_cmp_oeq_int_n0_uitofp(
>
> ; CHECK: uitofp
>
> ; CHECK: fcmp oeq
>
> define i1 @i32_cast_cmp_oeq_int_n0_uitofp(i32 %i) {
>
>   %f = uitofp i32 %i to float
>
>   %cmp = fcmp oeq float %f, -0.0
>
>   ret i1 %cmp
>
> }
>
>
>
> Is this test really justified, or is it just reinforcing an oversight?
>
>
>
> - Arch D. Robison
>
> _______________________________________________
> 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/20150706/0aa7c74c/attachment.html>

On 07/06/2015 03:06 PM, Sean Silva wrote:
> +Matt who is the one that originally committed this (r225265).
>
> -- Sean Silva
I think it's fine, but I was being extremely conservative with what it 
allows. This really should work in a lot more cases. Before my patch, it 
only worked for smaller integer types instead of considering the values. 
When I was working on this, I had it checking if the constant being 
compared could be represented by the integer type (e.g. fcmp eq with a 
fractional value -> false and also allow the non-equality compares). I 
think it was just disturbingly hard to break and I was afraid of 
breaking some edge case when the only real world cases I really cared 
about was eq/ne 0.

-Matt

The way FoldFCmp_IntToFP_Cst works is confusing to me. What it is trying to
do basically boils down to taking the set of real numbers where fcmp(?,
Cst) is true, then finding the inverse image under the mapping [us]itofp of
that set (i.e. all the integers (of the relevant type) that can map to
values in that set under the operation [us]itofp). That inverse image is
guaranteed to be contiguous, so at most two integer comparisons suffice. If
the inverse image is just a single value, then a single equality comparison
suffices. If the inverse image includes the {maximal,minimal}
{signed,unsigned} integer, then a single integer order comparison suffices.

So e.g. consider
  fcmp oeq double (uitofp x) Cst
With Cst = 2^62 + ulp(2^62)), i.e. 2^62*(0b1.0000....1), where the final 1
is in the least significant bit.

Then the set of real numbers for which `fcmp oeq double
roundToFloat(realNumber) Cst` yields true is the open interval (a,b) where
a = 2^62 + .5*ulp(2^62)
b = 2^62 + 1.5*ulp(2^62)
i.e. the open interval bracketed by Cst +/- .5*ulp(Cst)
(assuming round to nearest ties to even rounding mode)
However, since ulp(Cst) = ulp(2^62) = 2^62 * 2^-52 = 2^10, this means that
this range covers
(2^62 + (1/2)*2^10, 2^62 + (3/2)*2^10) = [2^62 + (1/2)*2^10 + 1, 2^62 +
(3/2)*2^10 - 1] which contains 1022 integers, so a range comparison is
needed.
(note: for Cst = 2^62, the interval is only half as large on the low side
since Cst lies on the boundary where the exponent changes, i.e. the
interval is [Cst - .25*ulp(Cst), Cst + .5*ulp(Cst)]; the closed interval is
due to 2^62 being even)

This of course requires baking in a rounding mode, but we are already doing
that anyway.

-- Sean Silva

On Mon, Jul 6, 2015 at 2:13 PM, Robison, Arch <arch.robison at intel.com>
wrote:
>  In InstCombineCompares.cpp, routine InstCombiner::FoldFCmp_IntToFP_Cst,
> there are these lines:
>
>
>
>   // Comparisons with zero are a special case where we know we won't
lose
>
>   // information.
>
>   bool IsCmpZero = RHS.isPosZero();
>
>
>
>   // If the conversion would lose info, don't hack on this.
>
>   if ((int)InputSize > MantissaWidth && !IsCmpZero)
>
>     return nullptr;
>
>
>
> Why check for positive zero instead of checking for any kind of zero?  My
> reading of IEEE 754-2008 is that floating-point comparison operations
> cannot distinguish a negative zero from a positive zero.  Further
> supporting this is that fact that http://llvm.org/docs/LangRef.html
>
<https://urldefense.proofpoint.com/v2/url?u=http-3A__llvm.org_docs_LangRef.html&d=AwMFAg&c=8hUWFZcy2Z-Za5rBPlktOQ&r=Mfk2qtn1LTDThVkh6-oGglNfMADXfJdty4_bhmuhMHA&m=ZaWNNVon_US-YjLoXztqD5ve4xvIIhIXYdnk3Xqwz8w&s=xonYObEo1TXUyjK3RYC4Pg3kAaSvaYy_Lnvaiq5G1N0&e=>
> describes the difference between “ordered” and “unordered” as pertaining to
> QNAN operands,
>
> with no mention of negative zero.
>
>
>
> I tried fixing the issue, but then the following test in
> cast-int-fcmp-eq-0.ll fails:
>
>
>
> ; CHECK-LABEL: @i32_cast_cmp_oeq_int_n0_uitofp(
>
> ; CHECK: uitofp
>
> ; CHECK: fcmp oeq
>
> define i1 @i32_cast_cmp_oeq_int_n0_uitofp(i32 %i) {
>
>   %f = uitofp i32 %i to float
>
>   %cmp = fcmp oeq float %f, -0.0
>
>   ret i1 %cmp
>
> }
>
>
>
> Is this test really justified, or is it just reinforcing an oversight?
>
>
>
> - Arch D. Robison
>
> _______________________________________________
> 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/20150706/292ecc0c/attachment.html>

I concur with your analysis.

I was planning to just extend the applicability of the current transform by just
taking on more cases where the inverse image is a single value.  Though if
someone else wants to take on the general range case, I’m happy to step aside.
:-)

- Arch

From: Sean Silva [mailto:chisophugis at gmail.com]
Sent: Monday, July 6, 2015 6:10 PM
To: Robison, Arch
Cc: llvmdev at cs.uiuc.edu
Subject: Re: [LLVMdev] Why can't comparisons with negative zero be
simplified?

The way FoldFCmp_IntToFP_Cst works is confusing to me. What it is trying to do
basically boils down to taking the set of real numbers where fcmp(?, Cst) is
true, then finding the inverse image under the mapping [us]itofp of that set
(i.e. all the integers (of the relevant type) that can map to values in that set
under the operation [us]itofp). That inverse image is guaranteed to be
contiguous, so at most two integer comparisons suffice. If the inverse image is
just a single value, then a single equality comparison suffices. If the inverse
image includes the {maximal,minimal} {signed,unsigned} integer, then a single
integer order comparison suffices.

So e.g. consider
  fcmp oeq double (uitofp x) Cst
With Cst = 2^62 + ulp(2^62)), i.e. 2^62*(0b1.0000....1), where the final 1 is in
the least significant bit.

Then the set of real numbers for which `fcmp oeq double roundToFloat(realNumber)
Cst` yields true is the open interval (a,b) where
a = 2^62 + .5*ulp(2^62)
b = 2^62 + 1.5*ulp(2^62)
i.e. the open interval bracketed by Cst +/- .5*ulp(Cst)
(assuming round to nearest ties to even rounding mode)
However, since ulp(Cst) = ulp(2^62) = 2^62 * 2^-52 = 2^10, this means that this
range covers
(2^62 + (1/2)*2^10, 2^62 + (3/2)*2^10) = [2^62 + (1/2)*2^10 + 1, 2^62 +
(3/2)*2^10 - 1] which contains 1022 integers, so a range comparison is needed.
(note: for Cst = 2^62, the interval is only half as large on the low side since
Cst lies on the boundary where the exponent changes, i.e. the interval is [Cst -
.25*ulp(Cst), Cst + .5*ulp(Cst)]; the closed interval is due to 2^62 being even)

This of course requires baking in a rounding mode, but we are already doing that
anyway.

-- Sean Silva

On Mon, Jul 6, 2015 at 2:13 PM, Robison, Arch <arch.robison at
intel.com<mailto:arch.robison at intel.com>> wrote:
In InstCombineCompares.cpp, routine InstCombiner::FoldFCmp_IntToFP_Cst, there
are these lines:

  // Comparisons with zero are a special case where we know we won't lose
  // information.
  bool IsCmpZero = RHS.isPosZero();

  // If the conversion would lose info, don't hack on this.
  if ((int)InputSize > MantissaWidth && !IsCmpZero)
    return nullptr;

Why check for positive zero instead of checking for any kind of zero?  My
reading of IEEE 754-2008 is that floating-point comparison operations cannot
distinguish a negative zero from a positive zero.  Further supporting this is
that fact that
http://llvm.org/docs/LangRef.html<https://urldefense.proofpoint.com/v2/url?u=http-3A__llvm.org_docs_LangRef.html&d=AwMFAg&c=8hUWFZcy2Z-Za5rBPlktOQ&r=Mfk2qtn1LTDThVkh6-oGglNfMADXfJdty4_bhmuhMHA&m=ZaWNNVon_US-YjLoXztqD5ve4xvIIhIXYdnk3Xqwz8w&s=xonYObEo1TXUyjK3RYC4Pg3kAaSvaYy_Lnvaiq5G1N0&e=>
describes the difference between “ordered” and “unordered” as pertaining to QNAN
operands,
with no mention of negative zero.

I tried fixing the issue, but then the following test in cast-int-fcmp-eq-0.ll
fails:

; CHECK-LABEL: @i32_cast_cmp_oeq_int_n0_uitofp(
; CHECK: uitofp
; CHECK: fcmp oeq
define i1 @i32_cast_cmp_oeq_int_n0_uitofp(i32 %i) {
  %f = uitofp i32 %i to float
  %cmp = fcmp oeq float %f, -0.0
  ret i1 %cmp
}

Is this test really justified, or is it just reinforcing an oversight?

- Arch D. Robison

_______________________________________________
LLVM Developers mailing list
LLVMdev at cs.uiuc.edu<mailto: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/20150707/1857dd4c/attachment.html>