[LLVMdev] Floating-point range checks

[Philip Reames]

With floating point, won't you need to model a partial order for the end 
points?  I thought there were pairs of floating point values which are 
incomparable.  Not sure if partial order is the right abstraction, but 
I'm pretty sure a total order isn't.

This may make implementing the range comparisons (which are themselves 
partially ordered) a bit tricky...

Philip
(Who knows just enough about floating point to know he doesn't really 
know what's he's talking about.)


On 01/08/2015 11:45 AM, Hal Finkel wrote:
> ----- Original Message -----
>> From: "Arch Robison" <arch.robison at intel.com>
>> To: "Hal Finkel" <hfinkel at anl.gov>
>> Cc: "Philip Reames" <listmail at philipreames.com>, llvmdev at cs.uiuc.edu
>> Sent: Thursday, January 8, 2015 1:26:41 PM
>> Subject: RE: [LLVMdev] Floating-point range checks
>>
>>> Checks against 1.0 are also common. Why not just add a FP range
>>> class, like our constant range, and go from there?
>> That's certainly another way to go.  My worry is that a more
>> complicated lattice gets us deeper into rounding-mode issues and
>> considerably more work for smaller gain.  I like the idea of
>> creating an FPRange class.  We could start with a simple one and
>> extend it as experience warrants.
> I worry about that too ;) -- I think creating a simple one and extending from there makes sense.
>
>   -Hal
>
>> - Arch
>>
>> -----Original Message-----
>> From: Hal Finkel [mailto:hfinkel at anl.gov]
>> Sent: Thursday, January 8, 2015 1:03 PM
>> To: Robison, Arch
>> Cc: Philip Reames; llvmdev at cs.uiuc.edu
>> Subject: Re: [LLVMdev] Floating-point range checks
>>
>> ----- Original Message -----
>>> From: "Arch Robison" <arch.robison at intel.com>
>>> To: "Philip Reames" <listmail at philipreames.com>,
>>> llvmdev at cs.uiuc.edu
>>> Sent: Thursday, January 8, 2015 12:54:32 PM
>>> Subject: Re: [LLVMdev] Floating-point range checks
>>>
>>>
>>> Thanks for the pointers. Looks like LazyValueInfo has the sort of
>>> infrastructure I had in mind. LVILatticeVal could be extended to
>>> floating point. (The comment “this can be made a lot more rich in
>>> the
>>> future” is an invitation :-). I’m thinking a simple lattice would
>>> address most cases of interest for floating-point checks. The
>>> lattice
>>> points for floating-point could be all subsets of the eight-element
>>> set:
>>>
>>> {-inf,<0,-0,+0,>0,+inf,-nan,+nan},
>>>
>>> where <0 and >0 denote finite negative/positive numbers
>>> respectively.
>>>
>> I'm not sure. Checks against 1.0 are also common. Why not just add a
>> FP range class, like our constant range, and go from there?
>>
>>   -Hal
>>
>>>
>>> - Arch
>>>
>>>
>>>
>>>
>>>
>>> From: Philip Reames [mailto:listmail at philipreames.com]
>>> Sent: Wednesday, January 7, 2015 6:03 PM
>>> To: Robison, Arch; llvmdev at cs.uiuc.edu
>>> Subject: Re: [LLVMdev] Floating-point range checks
>>>
>>>
>>>
>>> I don't believe we have much in this area currently.
>>>
>>> Generally, something like this would existing in InstCombine and
>>> ValueTracking.
>>>
>>> Take a look at ComputeSignBit in ValueTracking.cpp. This doesn't
>>> apply
>>> (?) to floating point numbers, but we'd need something equivalent
>>> for
>>> them. It looks like there may already be a start in the form of:
>>> CannotBeNegativeZero
>>>
>>> Other places to look would be SimplifyFAdd and
>>> InstCombine::visitFAdd.
>>>
>>> For this particular example, you're probably going to want a
>>> pattern
>>> in SimplifyFCmp of the form:
>>> matcher: sqrt_call( fadd(Value(X), SpecificValue(X)),
>>> fadd(Value(Y),
>>> SpecificValue(Y)))
>>> && CannotBeNegativeZero(X) && CannotBeNegativeZero(Y)
>>>
>>> You might also look at LazyValueInfo, but that's probably of
>>> secondary
>>> interest. It's purely in terms of constant integer ranges
>>> currently.
>>>
>>> Philip
>>>
>>>
>>>
>>>
>>>
>>> On 01/07/2015 02:13 PM, Robison, Arch wrote:
>>>
>>>
>>>
>>>
>>> The Julia language implements sqrt(x) with conditional branch taken
>>> if
>>> x<0. Alas this prevents vectorization of loops with sqrt. Often the
>>> argument can be proven to be non-negative. E.g., sqrt(x*x+y*y).
>>> Is there an existing LLVM pass or analysis that does floating-point
>>> range propagation to eliminate such unnecessary checks?
>>>
>>>
>>>
>>>
>>>
>>> Arch D. Robison
>>>
>>>
>>> Intel Corporation
>>>
>>>
>>>
>>>
>>>
>>>
>>>
>>>
>>>
>>>
>>>
>>>
>>>
>>> _______________________________________________ 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
>>>
>> --
>> Hal Finkel
>> Assistant Computational Scientist
>> Leadership Computing Facility
>> Argonne National Laboratory
>>