thr3ads.net - llvm dev - [llvm-dev] Floating Point SCEV Analysis [Jun 2016]

If this information is useful, please help other people find it:
Share via:

Andrew Trick via llvm-dev

2016-May-30 18:40 UTC

[llvm-dev] 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 <mailto: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
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160530/911a5e2e/attachment.html>

Amara Emerson via llvm-dev

2016-May-30 22:31 UTC

head link

[llvm-dev] Floating Point SCEV Analysis

I mentioned this before, adding FP support to SCEV is not necessary
for vectorizing FP recurrences if enough intelligence is added to the
isInductionPHI. I have a patch but it's a bit of a hassle for me to
separate it out from some other functionality at the moment. If the
vectorizer is the only place that FP SCEV awareness is needed I also
share the doubts about this approach. I'm happy to stand corrected if
the analytical power of FP-SCEV would give other benefits though.

Amara

On 30 May 2016 at 19:40, Andrew Trick via llvm-dev
<llvm-dev at lists.llvm.org> wrote:> 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
>
>
>
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>

Demikhovsky, Elena via llvm-dev

2016-Jun-02 13:48 UTC

head link

[llvm-dev] Floating Point SCEV Analysis

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<mailto: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<mailto:reviews+D20695+public+faa7820b5ed6aa91 at
reviews.llvm.org>
Cc: llvm-commits at lists.llvm.org<mailto:llvm-commits at lists.llvm.org>,
mssimpso at codeaurora.org<mailto:mssimpso at codeaurora.org>
Reply-To: Andrew Trick <atrick at apple.com<mailto:atrick at
apple.com>>

On May 30, 2016, at 12:02 AM, Sanjoy Das <sanjoy at
playingwithpointers.com<mailto: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<mailto: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.
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160602/5ce9fc33/attachment-0001.html>

Sanjay Patel via llvm-dev

2016-Jun-02 14:56 UTC

head link

[llvm-dev] Floating Point SCEV Analysis

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
>
>-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160602/1534ae73/attachment.html>

Reasonably Related Threads

Search for more apparently analagous threads

llvm dev - Jun 2016 - Floating Point SCEV Analysis

[llvm-dev] Floating Point SCEV Analysis

[llvm-dev] Floating Point SCEV Analysis

[llvm-dev] Floating Point SCEV Analysis

[llvm-dev] Floating Point SCEV Analysis

Reasonably Related Threads