[llvm-dev] Floating Point SCEV Analysis

Mon Jun 6 14:53:46 PDT 2016

On Thu, Jun 2, 2016 at 3:45 PM, Sanjoy Das via llvm-dev <
llvm-dev at lists.llvm.org> wrote:

> 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?
>

The cases that immediately come to mind for me are time step integration
loops like:

T x = ...;
for (float t = 0; t < tmax; t += dt) {
  T dx = dt * fprime(x, t);
  x += dx;
}

But I'm not sure how much we expect to speed things up considering the
loop-carried dependence on `x`.

-- Sean Silva

>
> 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
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> 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/20160606/ec80d9d8/attachment-0001.html>