llvm dev - Jan 2015 - [LLVMdev] Floating-point range checks

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



-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20150107/89b401ea/attachment.html>

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
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20150107/aa643b48/attachment.html>

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.

- 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<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/20150108/ef9678f9/attachment.html>