[llvm-dev] Floating Point SCEV Analysis

Thu Jun 2 15:45:50 PDT 2016

Hi Elena,

At this point we're really waiting on responses to the following three
questions:

# Why is it worth aggressively optimizing floating pointer induction variables?

By "floating point induction variable" I'm referring to "for (float i
= 0.0; i < F; i += 1.0)", not "for (int i = 0 to N) x += 5.0".  If
you're mainly interested in the latter, IMO the SCEV changes are
overkill -- we should just pattern match floating point reductions
outside of SCEV.

So far the only response I've seen is "ideally we'd like to vectorize
even if the induction variable is in floating point", and while I
agree with the sentiment (obviously, all else being equal, I'd like
LLVM to be as effective as possible), to justify this large a change
we'd need a compelling argument why such cases (loops with floating
point controlling induction variables) are interesting optimization
targets.  Are
there real world program that have this kind of behavior?

I also think you're underestimating how complex the change is.  It may
look simple now, but this will add significant cognitive overhead
moving forward, more so not because we're adding "one more" type, but
because we're going from "only one type" to "two types".
E.g. getRange() will be invalid over half the SCEV kinds, unless we
add a new ConstantFPRange class.

# How far can we get without teaching SCEV about floating point at all?

If you do have a set of applications that do rely on floating point
induction variables, how far can you push them by transforming the
floating point induction variables to integer induction variables?
This should have significantly less surface area than the FP-SCEV
changes and if it is enough, then we should prefer it over FP-SCEV.

OTOH if you have interesting use-cases that *cannot* be resolved by
the transform above, then that's a good case for moving FP-SCEV
forward.

# What things are you depending on to have the SCEVs accurately
represent FP semantics?

I think you at least need associativity, to be able to use SCEV's
canonicalization of N-ary expressions over the possible ordering of
operands.  Given you want to do trip count computations, then you
probably also need "A + X != X" for X != 0.0.

Are fast-math flags enough for this?

(I typed this in before reading
https://llvm.org/bugs/show_bug.cgi?id=27894#c7 , Hal has answered the
question there).

And as Andy said, we'd need to circle in a floating point expert into
the review.

-- Sanjoy

On Thu, Jun 2, 2016 at 7:56 AM, Sanjay Patel via llvm-dev
<llvm-dev at lists.llvm.org> wrote:
> For reference, the case with a variable loop count is filed as PR27894:
> https://llvm.org/bugs/show_bug.cgi?id=27894
>
> And the case with a constant loop count is filed as PR27899:
> https://llvm.org/bugs/show_bug.cgi?id=27899
>
>
> On Thu, Jun 2, 2016 at 7:48 AM, Demikhovsky, Elena via llvm-dev
> <llvm-dev at lists.llvm.org> wrote:
>>
>> I implemented IV simplification with FP SCEV and uploaded a new patch. The
>> loop bellow is converted to “start+const*N”.
>>
>> (You can see the diff between patches to see what was added).
>>
>>
>>
>> -           Elena
>>
>>
>>
>> From: atrick at apple.com [mailto:atrick at apple.com]
>> Sent: Monday, May 30, 2016 21:40
>> To: llvm-dev <llvm-dev at lists.llvm.org>
>> Cc: Demikhovsky, Elena <elena.demikhovsky at intel.com>; Sanjoy Das
>> <sanjoy at playingwithpointers.com>
>> Subject: Floating Point SCEV Analysis
>>
>>
>>
>> My response to this patch is below, but adding a floating-point feature to
>> SCEV should really be hashed out on the llvm-dev list first. I would like to
>> get the attention of floating-point experts on the design review.
>>
>>
>>
>> I’d like to see a small design proposal justifying the feature and
>> defending it’s soundness. My concern is that the approach may not be sound,
>> but providing this core API would encourage llvm dev’s to use the feature
>> without thinking.
>>
>>
>>
>> I suggest starting with SCEV’s most basic functionality and proving the
>> validity of increasingly complex cases. Can you defend SCEV’s ability to
>> remove loops like this?
>>
>>
>>
>> float fincby(float start, int N) {
>>
>>   float result = start;
>>
>>   for (int i = 0; i < N; ++i) {
>>
>>     result += 1.0f;
>>
>>   }
>>
>>   return result;
>>
>> }
>>
>>
>>
>> -Andy
>>
>>
>>
>> http://reviews.llvm.org/D20695
>>
>>
>>
>> Begin forwarded message:
>>
>>
>>
>> From: Andrew Trick via llvm-commits <llvm-commits at lists.llvm.org>
>>
>> Subject: Re: [PATCH] D20695: Floating Point SCEV Analysis
>>
>> Date: May 30, 2016 at 11:05:35 AM PDT
>>
>> To: reviews+D20695+public+faa7820b5ed6aa91 at reviews.llvm.org
>>
>> Cc: llvm-commits at lists.llvm.org, mssimpso at codeaurora.org
>>
>> Reply-To: Andrew Trick <atrick at apple.com>
>>
>>
>>
>>
>>
>> On May 30, 2016, at 12:02 AM, Sanjoy Das <sanjoy at playingwithpointers.com>
>> wrote:
>>
>>
>>
>> I have made some minor comments inline, but I still stand by my earlier
>> comment that we should do something like this as a last resort.  As an
>> initial step we should at least evaluate how far we can we can get on
>> relevant workloads without teaching SCEV about floating point values at all.
>>
>>
>>
>> Are there conceivable use cases for this infrastructure beyond vectorizing
>> a small subcategory of loops of this form?
>>
>>
>>
>> float x = init;
>>  for (int i=0;i<N;i++){
>>    A[i] = x;
>>    x += fp_inc; // Loop invariant variable or constant
>>  }
>>
>>
>>
>> Can the vectorizer handle loops of this form without querying SCEV?
>>
>>
>>
>> SCEV expressions have an inherent width. They are not infinite precision.
>> This is the main challenge of working with SCEV expressions, as Sanjoy is
>> well aware. What happens when incrementing a floating-point SCEV expression
>> by a smaller amount than ULP. Eventually that will happen in a
>> floating-point recurrence. Do we have to prove that floating-point
>> recurrences behave a certain way before we can legally convert them to SCEV
>> expressions?
>>
>>
>>
>> Honestly, I’m not an expert in floating-point semantics, and I wouldn’t
>> feel comfortable adding this to SCEV without buy-in from someone who is.
>>
>>
>>
>> Andy
>>
>> _______________________________________________
>> llvm-commits mailing list
>> llvm-commits at lists.llvm.org
>> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-commits
>>
>>
>>
>> ---------------------------------------------------------------------
>> Intel Israel (74) Limited
>>
>> This e-mail and any attachments may contain confidential material for
>> the sole use of the intended recipient(s). Any review or distribution
>> by others is strictly prohibited. If you are not the intended
>> recipient, please contact the sender and delete all copies.
>>
>>
>> _______________________________________________
>> LLVM Developers mailing list
>> llvm-dev at lists.llvm.org
>> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>>
>
>
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>

-- 
Sanjoy Das
http://playingwithpointers.com