[llvm-dev] Floating Point SCEV Analysis

Thu Jun 2 15:55:50 PDT 2016

----- Original Message -----
> From: "Sanjoy Das via llvm-dev" <llvm-dev at lists.llvm.org>
> To: "Sanjay Patel" <spatel at rotateright.com>
> Cc: "llvm-dev" <llvm-dev at lists.llvm.org>
> Sent: Thursday, June 2, 2016 5:45:50 PM
> Subject: Re: [llvm-dev] Floating Point SCEV Analysis
> 
> 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).

I'd say that I proposed an answer there. ;) -- We should probably move this part of the discussion to llvm-dev/cfe-dev.

 -Hal

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

-- 
Hal Finkel
Assistant Computational Scientist
Leadership Computing Facility
Argonne National Laboratory