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>
----- 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
> 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. - 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
http://llvm.org/bugs/show_bug.cgi?id=17713 shows another case where some kind of FP value tracking would be useful. gcc can transform this division into multiplication by reciprocal: if (y == 2.0) return x/y; On Thu, Jan 8, 2015 at 12:02 PM, Hal Finkel <hfinkel at anl.gov> wrote:> ----- 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 > > _______________________________________________ > 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/20150108/b512bb4b/attachment.html>