<div dir="ltr"><br><div class="gmail_extra"><br><div class="gmail_quote">On Thu, Jun 2, 2016 at 3:45 PM, Sanjoy Das via llvm-dev <span dir="ltr"><<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex">Hi Elena,<br>
<br>
At this point we're really waiting on responses to the following three<br>
questions:<br>
<br>
# Why is it worth aggressively optimizing floating pointer induction variables?<br>
<br>
By "floating point induction variable" I'm referring to "for (float i<br>
= 0.0; i < F; i += 1.0)", not "for (int i = 0 to N) x += 5.0".  If<br>
you're mainly interested in the latter, IMO the SCEV changes are<br>
overkill -- we should just pattern match floating point reductions<br>
outside of SCEV.<br>
<br>
So far the only response I've seen is "ideally we'd like to vectorize<br>
even if the induction variable is in floating point", and while I<br>
agree with the sentiment (obviously, all else being equal, I'd like<br>
LLVM to be as effective as possible), to justify this large a change<br>
we'd need a compelling argument why such cases (loops with floating<br>
point controlling induction variables) are interesting optimization<br>
targets.  Are<br>
there real world program that have this kind of behavior?<br></blockquote><div><br></div><div>The cases that immediately come to mind for me are time step integration loops like:</div><div><br></div><div>T x = ...;</div><div>for (float t = 0; t < tmax; t += dt) {</div><div>  T dx = dt * fprime(x, t);</div><div>  x += dx;<br>}</div><div><br></div><div>But I'm not sure how much we expect to speed things up considering the loop-carried dependence on `x`.</div><div><br></div><div>-- Sean Silva<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex">
<br>
I also think you're underestimating how complex the change is.  It may<br>
look simple now, but this will add significant cognitive overhead<br>
moving forward, more so not because we're adding "one more" type, but<br>
because we're going from "only one type" to "two types".<br>
E.g. getRange() will be invalid over half the SCEV kinds, unless we<br>
add a new ConstantFPRange class.<br>
<br>
# How far can we get without teaching SCEV about floating point at all?<br>
<br>
If you do have a set of applications that do rely on floating point<br>
induction variables, how far can you push them by transforming the<br>
floating point induction variables to integer induction variables?<br>
This should have significantly less surface area than the FP-SCEV<br>
changes and if it is enough, then we should prefer it over FP-SCEV.<br>
<br>
OTOH if you have interesting use-cases that *cannot* be resolved by<br>
the transform above, then that's a good case for moving FP-SCEV<br>
forward.<br>
<br>
# What things are you depending on to have the SCEVs accurately<br>
represent FP semantics?<br>
<br>
I think you at least need associativity, to be able to use SCEV's<br>
canonicalization of N-ary expressions over the possible ordering of<br>
operands.  Given you want to do trip count computations, then you<br>
probably also need "A + X != X" for X != 0.0.<br>
<br>
Are fast-math flags enough for this?<br>
<br>
(I typed this in before reading<br>
<a href="https://llvm.org/bugs/show_bug.cgi?id=27894#c7" rel="noreferrer" target="_blank">https://llvm.org/bugs/show_bug.cgi?id=27894#c7</a> , Hal has answered the<br>
question there).<br>
<br>
And as Andy said, we'd need to circle in a floating point expert into<br>
the review.<br>
<br>
-- Sanjoy<br>
<div class=""><div class="h5"><br>
On Thu, Jun 2, 2016 at 7:56 AM, Sanjay Patel via llvm-dev<br>
<<a href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a>> wrote:<br>
> For reference, the case with a variable loop count is filed as PR27894:<br>
> <a href="https://llvm.org/bugs/show_bug.cgi?id=27894" rel="noreferrer" target="_blank">https://llvm.org/bugs/show_bug.cgi?id=27894</a><br>
><br>
> And the case with a constant loop count is filed as PR27899:<br>
> <a href="https://llvm.org/bugs/show_bug.cgi?id=27899" rel="noreferrer" target="_blank">https://llvm.org/bugs/show_bug.cgi?id=27899</a><br>
><br>
><br>
> On Thu, Jun 2, 2016 at 7:48 AM, Demikhovsky, Elena via llvm-dev<br>
> <<a href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a>> wrote:<br>
>><br>
>> I implemented IV simplification with FP SCEV and uploaded a new patch. The<br>
>> loop bellow is converted to “start+const*N”.<br>
>><br>
>> (You can see the diff between patches to see what was added).<br>
>><br>
>><br>
>><br>
>> -           Elena<br>
>><br>
>><br>
>><br>
>> From: <a href="mailto:atrick@apple.com">atrick@apple.com</a> [mailto:<a href="mailto:atrick@apple.com">atrick@apple.com</a>]<br>
>> Sent: Monday, May 30, 2016 21:40<br>
>> To: llvm-dev <<a href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a>><br>
>> Cc: Demikhovsky, Elena <<a href="mailto:elena.demikhovsky@intel.com">elena.demikhovsky@intel.com</a>>; Sanjoy Das<br>
>> <<a href="mailto:sanjoy@playingwithpointers.com">sanjoy@playingwithpointers.com</a>><br>
>> Subject: Floating Point SCEV Analysis<br>
>><br>
>><br>
>><br>
>> My response to this patch is below, but adding a floating-point feature to<br>
>> SCEV should really be hashed out on the llvm-dev list first. I would like to<br>
>> get the attention of floating-point experts on the design review.<br>
>><br>
>><br>
>><br>
>> I’d like to see a small design proposal justifying the feature and<br>
>> defending it’s soundness. My concern is that the approach may not be sound,<br>
>> but providing this core API would encourage llvm dev’s to use the feature<br>
>> without thinking.<br>
>><br>
>><br>
>><br>
>> I suggest starting with SCEV’s most basic functionality and proving the<br>
>> validity of increasingly complex cases. Can you defend SCEV’s ability to<br>
>> remove loops like this?<br>
>><br>
>><br>
>><br>
>> float fincby(float start, int N) {<br>
>><br>
>>   float result = start;<br>
>><br>
>>   for (int i = 0; i < N; ++i) {<br>
>><br>
>>     result += 1.0f;<br>
>><br>
>>   }<br>
>><br>
>>   return result;<br>
>><br>
>> }<br>
>><br>
>><br>
>><br>
>> -Andy<br>
>><br>
>><br>
>><br>
>> <a href="http://reviews.llvm.org/D20695" rel="noreferrer" target="_blank">http://reviews.llvm.org/D20695</a><br>
>><br>
>><br>
>><br>
>> Begin forwarded message:<br>
>><br>
>><br>
>><br>
>> From: Andrew Trick via llvm-commits <<a href="mailto:llvm-commits@lists.llvm.org">llvm-commits@lists.llvm.org</a>><br>
>><br>
>> Subject: Re: [PATCH] D20695: Floating Point SCEV Analysis<br>
>><br>
>> Date: May 30, 2016 at 11:05:35 AM PDT<br>
>><br>
>> To: <a href="mailto:reviews%2BD20695%2Bpublic%2Bfaa7820b5ed6aa91@reviews.llvm.org">reviews+D20695+public+faa7820b5ed6aa91@reviews.llvm.org</a><br>
>><br>
>> Cc: <a href="mailto:llvm-commits@lists.llvm.org">llvm-commits@lists.llvm.org</a>, <a href="mailto:mssimpso@codeaurora.org">mssimpso@codeaurora.org</a><br>
>><br>
>> Reply-To: Andrew Trick <<a href="mailto:atrick@apple.com">atrick@apple.com</a>><br>
>><br>
>><br>
>><br>
>><br>
>><br>
>> On May 30, 2016, at 12:02 AM, Sanjoy Das <<a href="mailto:sanjoy@playingwithpointers.com">sanjoy@playingwithpointers.com</a>><br>
>> wrote:<br>
>><br>
>><br>
>><br>
>> I have made some minor comments inline, but I still stand by my earlier<br>
>> comment that we should do something like this as a last resort.  As an<br>
>> initial step we should at least evaluate how far we can we can get on<br>
>> relevant workloads without teaching SCEV about floating point values at all.<br>
>><br>
>><br>
>><br>
>> Are there conceivable use cases for this infrastructure beyond vectorizing<br>
>> a small subcategory of loops of this form?<br>
>><br>
>><br>
>><br>
>> float x = init;<br>
>>  for (int i=0;i<N;i++){<br>
>>    A[i] = x;<br>
>>    x += fp_inc; // Loop invariant variable or constant<br>
>>  }<br>
>><br>
>><br>
>><br>
>> Can the vectorizer handle loops of this form without querying SCEV?<br>
>><br>
>><br>
>><br>
>> SCEV expressions have an inherent width. They are not infinite precision.<br>
>> This is the main challenge of working with SCEV expressions, as Sanjoy is<br>
>> well aware. What happens when incrementing a floating-point SCEV expression<br>
>> by a smaller amount than ULP. Eventually that will happen in a<br>
>> floating-point recurrence. Do we have to prove that floating-point<br>
>> recurrences behave a certain way before we can legally convert them to SCEV<br>
>> expressions?<br>
>><br>
>><br>
>><br>
>> Honestly, I’m not an expert in floating-point semantics, and I wouldn’t<br>
>> feel comfortable adding this to SCEV without buy-in from someone who is.<br>
>><br>
>><br>
>><br>
>> Andy<br>
>><br>
>> _______________________________________________<br>
>> llvm-commits mailing list<br>
>> <a href="mailto:llvm-commits@lists.llvm.org">llvm-commits@lists.llvm.org</a><br>
>> <a href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-commits" rel="noreferrer" target="_blank">http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-commits</a><br>
>><br>
>><br>
>><br>
>> ---------------------------------------------------------------------<br>
>> Intel Israel (74) Limited<br>
>><br>
>> This e-mail and any attachments may contain confidential material for<br>
>> the sole use of the intended recipient(s). Any review or distribution<br>
>> by others is strictly prohibited. If you are not the intended<br>
>> recipient, please contact the sender and delete all copies.<br>
>><br>
>><br>
>> _______________________________________________<br>
>> LLVM Developers mailing list<br>
>> <a href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a><br>
>> <a href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" rel="noreferrer" target="_blank">http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a><br>
>><br>
><br>
><br>
> _______________________________________________<br>
> LLVM Developers mailing list<br>
> <a href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a><br>
> <a href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" rel="noreferrer" target="_blank">http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a><br>
><br>
<br>
<br>
<br>
</div></div><span class=""><font color="#888888">--<br>
Sanjoy Das<br>
<a href="http://playingwithpointers.com" rel="noreferrer" target="_blank">http://playingwithpointers.com</a><br>
</font></span><div class=""><div class="h5">_______________________________________________<br>
LLVM Developers mailing list<br>
<a href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a><br>
<a href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" rel="noreferrer" target="_blank">http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a><br>
</div></div></blockquote></div><br></div></div>