llvm dev - May 2016 - Working on FP SCEV Analysis

Hi Escha,

via llvm-dev wrote:
> One thought I’ve had about this in the past —
>
> SCEV is useful for proving two expressions are equivalent (in general,
> not just specifically for loop induction variables). This gets a little
> bit trickier with fast-math; for example, suppose two expressions are
> equivalent, but *only* with reassociativity allowed?
This isn't too different from "sext(a + b) == sext(a) + sext(b) only
if the addition is nsw".

However, it wasn't clear to me from the lang-ref what the fastmath
flags really mean.  What is the semantics of a program that computes
((a +fast b) +fast c) when ((a + b) + c) != (a + (b + c))?  Does it
have UB (in which case we can't hoist fastmath arithmetic) or is it
more like poison?  Depending on the answer, for fastmath we can
considering doing what we do today for nuw/nsw (which has its own set
of issues, but at least wouldn't require us to start from scratch).

-- Sanjoy

----- Original Message -----
> From: "Sanjoy Das via llvm-dev" <llvm-dev at
lists.llvm.org>
> To: escha at apple.com
> Cc: "llvm-dev" <llvm-dev at lists.llvm.org>, "Michael
V Zolotukhin" <michael.v.zolotukhin at intel.com>
> Sent: Monday, May 16, 2016 7:31:20 PM
> Subject: Re: [llvm-dev] Working on FP SCEV Analysis
> 
> Hi Escha,
> 
> via llvm-dev wrote:
> > One thought I’ve had about this in the past —
> >
> > SCEV is useful for proving two expressions are equivalent (in
> > general,
> > not just specifically for loop induction variables). This gets a
> > little
> > bit trickier with fast-math; for example, suppose two expressions
> > are
> > equivalent, but *only* with reassociativity allowed?
> 
> This isn't too different from "sext(a + b) == sext(a) + sext(b)
only
> if the addition is nsw".
> 
> However, it wasn't clear to me from the lang-ref what the fastmath
> flags really mean.  What is the semantics of a program that computes
> ((a +fast b) +fast c) when ((a + b) + c) != (a + (b + c))?
This is often true, and it is neither UB nor poison. The user has given the
compiler the freedom to choose whatever the compiler decides will be
most-efficient to compute. "fast math" is an odd concept in that
sense. It is giving the compiler the freedom to change the program semantics to
some extent.

 -Hal
>  Does it
> have UB (in which case we can't hoist fastmath arithmetic) or is it
> more like poison?  Depending on the answer, for fastmath we can
> considering doing what we do today for nuw/nsw (which has its own set
> of issues, but at least wouldn't require us to start from scratch).
> 
> -- Sanjoy
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
> 
-- 
Hal Finkel
Assistant Computational Scientist
Leadership Computing Facility
Argonne National Laboratory

> On May 16, 2016, at 5:35 PM, Hal Finkel via llvm-dev <llvm-dev at
lists.llvm.org> wrote:
> 
> ----- Original Message -----
>> From: "Sanjoy Das via llvm-dev" <llvm-dev at
lists.llvm.org>
>> To: escha at apple.com
>> Cc: "llvm-dev" <llvm-dev at lists.llvm.org>,
"Michael V Zolotukhin" <michael.v.zolotukhin at intel.com>
>> Sent: Monday, May 16, 2016 7:31:20 PM
>> Subject: Re: [llvm-dev] Working on FP SCEV Analysis
>> 
>> Hi Escha,
>> 
>> via llvm-dev wrote:
>>> One thought I’ve had about this in the past —
>>> 
>>> SCEV is useful for proving two expressions are equivalent (in
>>> general,
>>> not just specifically for loop induction variables). This gets a
>>> little
>>> bit trickier with fast-math; for example, suppose two expressions
>>> are
>>> equivalent, but *only* with reassociativity allowed?
>> 
>> This isn't too different from "sext(a + b) == sext(a) +
sext(b) only
>> if the addition is nsw".
>> 
>> However, it wasn't clear to me from the lang-ref what the fastmath
>> flags really mean.  What is the semantics of a program that computes
>> ((a +fast b) +fast c) when ((a + b) + c) != (a + (b + c))?
> 
> This is often true, and it is neither UB nor poison. The user has given the
compiler the freedom to choose whatever the compiler decides will be
most-efficient to compute. "fast math" is an odd concept in that
sense. It is giving the compiler the freedom to change the program semantics to
some extent.
It’s possible to make an infinite loop finite with fast math if the primary IV
is float. Is it acceptable behavior too? What I mean is that if we have
for (float i = 0.0; i < HUGE_FLOAT_NUMBER; i += 0.5) {
 ...
}
we might never reach HUGE_FLOAT_NUMBER, as at some point i+1.0 = i in float (or
am I totally wrong here?). However, when analyzing this loop, we might find its
trip count to be exactly HUGE_FLOAT_NUMBER*2. There are all kinds of odd stuff
with floats in this area, but probably if ‘-ffast-math’ is provided, we’re fine.

I’m also very interested in specific cases we want to catch here. In the past
Tyler (CCed) looked into this problem, but as far as I remember we decided that
complexity/gains ratio was too low.  Basically, I anticipate that the code to
support this in SCEV will be at least as sophisticated as for integers, but in
contrast to integers FP induction variables are much rarer in real world
programs, at least to my impression.

Thanks,
Michael
> 
> -Hal
> 
>> Does it
>> have UB (in which case we can't hoist fastmath arithmetic) or is it
>> more like poison?  Depending on the answer, for fastmath we can
>> considering doing what we do today for nuw/nsw (which has its own set
>> of issues, but at least wouldn't require us to start from scratch).
>> 
>> -- Sanjoy
>> _______________________________________________
>> LLVM Developers mailing list
>> llvm-dev at lists.llvm.org <mailto:llvm-dev at lists.llvm.org>
>> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
<http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev>
>> 
> 
> -- 
> Hal Finkel
> Assistant Computational Scientist
> Leadership Computing Facility
> Argonne National Laboratory
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org <mailto:llvm-dev at lists.llvm.org>
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
<http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160516/62f030ea/attachment.html>