> 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
----- 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 >-- Hal Finkel Assistant Computational Scientist Leadership Computing Facility Argonne National Laboratory
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 >>