llvm dev - May 2016 - Working on FP SCEV Analysis

On Tue, May 17, 2016 at 8:49 PM Owen Anderson <resistor at mac.com> wrote:
>
> On May 16, 2016, at 2:42 PM, Sanjoy Das via llvm-dev <
> llvm-dev at lists.llvm.org> wrote:
>
> - Core motivation: why do we even care about optimizing floating
>   point induction variables?  What situations are they common in?  Do
>   programmers _expect_ compilers to optimize them well?  (I haven't
>   worked on our vectorizers so pardon the possibly stupid question)
>   in the example you gave, why do you need SCEV to analyze the
>   increment to vectorize the loop (i.e how does it help)?  What are
>   some other concrete cases you'll want to optimize?
>
>
> Graphics shading languages like GLSL or HLSL have floating point types as
> the “default” types.  Integers weren’t even added until later revisions of
> GLSL.  In that world, it’s not especially strange to imagine a loop counter
> written in floating point.
>
But most of those are convertible to integer IVs which as Andy pointed out
up the thread is something IndVarSimplify tries to do.

A potential way to show a motivating use case is what Andy already
outlined: cases where non-integer values are fundamentally used as part of
the IV.

Even then, I'd personally want to see further evidence of why the correct
solution is to model the floating point IV in SCEV rather than find a more
powerful way of converting the IV to an integer that models the non-integer
values taken on by the IV. As an example, if the use case is the following
code with appropriate flags to relax IEEE semantics so this looks like
normal algabra etc:

  for (float f = 0.01f; f < 1.0f; f += 0.01f)
    ...

I'd rather see us cleverly turn it into:

  float f = 0.01f;
  for (int i = 1; i < 100; i += 1, f += 0.01f)
    ...

(or whatever the transform would be, I've not spent lots of time thinking
about the exact way to map this onto a synthetic "adding that value N times
crosses threshold, so let's replace IV with a counter to N")

-Chandler
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160518/7814064d/attachment.html>

> Even then, I'd personally want to see further evidence of why the
correct solution is to model the floating point IV in SCEV rather than find a
more powerful way of converting the IV to an integer that models > the
non-integer values taken on by the IV. As an example, if the use case is the
following code with appropriate flags to relax IEEE semantics so this looks like
normal algabra etc:
>   for (float f = 0.01f; f < 1.0f; f += 0.01f)  <== *A*
    ...
> I'd rather see us cleverly turn it into:
>   float f = 0.01f;
>   for (int i = 1; i < 100; i += 1, f += 0.01f) <== *B*
I can later try to enhance IndVarSimplify::handleFloatingPointIV() in order to
convert *A* to *B*.
But *B* is exactly the case I’m starting from. The main IV “i” is integer. The
variable “f” is also considered as IV in this loop.
And this loop is not vectorized because “f” is floating point.
I don’t think that the case *B* is uncommon.


-           Elena
---------------------------------------------------------------------
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/20160518/dd4b5239/attachment.html>

----- Original Message -----
> From: "Elena via llvm-dev Demikhovsky" <llvm-dev at
lists.llvm.org>
> To: "Chandler Carruth" <chandlerc at google.com>,
"Owen Anderson"
> <resistor at mac.com>, "Sanjoy Das" <sanjoy at
playingwithpointers.com>
> Cc: "llvm-dev" <llvm-dev at lists.llvm.org>, "Hideki
Saito"
> <hideki.saito at intel.com>
> Sent: Wednesday, May 18, 2016 8:25:28 AM
> Subject: Re: [llvm-dev] Working on FP SCEV Analysis
> > Even then, I'd personally want to see further evidence of why the
> > correct solution is to model the floating point IV in SCEV rather
> > than find a more powerful way of converting the IV to an integer
> > that models > the non-integer values taken on by the IV. As an
> > example, if the use case is the following code with appropriate
> > flags to relax IEEE semantics so this looks like normal algabra
> > etc:
> > for (float f = 0.01f; f < 1.0f; f += 0.01f) ç * A *
> ...
> > I'd rather see us cleverly turn it into:
> > float f = 0.01f;
> > for (int i = 1; i < 100; i += 1, f += 0.01f) ç * B *
> I can later try to enhance IndVarSimplify ::handleFloatingPointIV ()
> in order to convert * A * to * B *.
> But * B * is exactly the case I’m starting from. The main IV “i” is
> integer. The variable “f” is also considered as IV in this loop.
> And this loop is not vectorized because “f” is floating point.
> I don’t think that the case * B * is uncommon.
I agree. The *B* case is not uncommon. 

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

Hal Finkel 
Assistant Computational Scientist 
Leadership Computing Facility 
Argonne National Laboratory 
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160518/7b60c808/attachment.html>

Demikhovsky, Elena wrote:
>  > Even then, I'd personally want to see further evidence of why the
> correct solution is to model the floating point IV in SCEV rather than
> find a more powerful way of converting the IV to an integer that models
>  > the non-integer values taken on by the IV. As an example, if the use
> case is the following code with appropriate flags to relax IEEE
> semantics so this looks like normal algabra etc:
>
>  > for (float f = 0.01f; f < 1.0f; f += 0.01f) ç **A**
>
> ...
>
>  > I'd rather see us cleverly turn it into:
>
>  > float f = 0.01f;
>
>  > for (int i = 1; i < 100; i += 1, f += 0.01f) ç **B**
>
> I can later try to enhance IndVarSimplify::handleFloatingPointIV() in
> order to convert**A** to **B**.
>
> But **B** is exactly the case I’m starting from. The main IV “i” is
> integer. The variable “f” is also considered as IV in this loop.
>
> And this loop is not vectorized because “f” is floating point.
>
> I don’t think that the case **B** is uncommon.
If B is the case we actually care about, I'd say changing SCEV to work 
with floating points is an overkill.  How would you expect an 
SCEVFAddExpr to help vectorize B, other than tell you what the initial 
value and the increment is (and these can be found with a simple value 
analysis)?

If we're interested in handling complex variants of A directly: 
computing trip counts, proving away predicates etc. without translating 
the loops to use integer IVs (perhaps because we can't legally do so), 
then I can see FP-SCEV as a reasonable implementation strategy, but it 
looks like the general consensus is that such cases are rare and 
generally not worth optimizing?

-- Sanjoy
>
> -*/Elena/*
>
> ---------------------------------------------------------------------
> 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.
>

> On May 18, 2016, at 6:25 AM, Demikhovsky, Elena via llvm-dev <llvm-dev
at lists.llvm.org> wrote:
> 
> > Even then, I'd personally want to see further evidence of why the
correct solution is to model the floating point IV in SCEV rather than find a
more powerful way of converting the IV to an integer that models > the
non-integer values taken on by the IV. As an example, if the use case is the
following code with appropriate flags to relax IEEE semantics so this looks like
normal algabra etc:
>  
> >   for (float f = 0.01f; f < 1.0f; f += 0.01f)  ç *A*
>     ...
>  
> > I'd rather see us cleverly turn it into:
>  
> >   float f = 0.01f;
> >   for (int i = 1; i < 100; i += 1, f += 0.01f) ç *B*
>  
> I can later try to enhance IndVarSimplify::handleFloatingPointIV() in order
to convert *A* to *B*.
> But *B* is exactly the case I’m starting from. The main IV “i” is integer.
The variable “f” is also considered as IV in this loop.
> And this loop is not vectorized because “f” is floating point.
> I don’t think that the case *B* is uncommon.
>  
I’m not sure what terminology to use (help), but we should make a fundamental
distinction between these cases (copying from Hideki):

void foo(TTT *a, int N, TTT x, TTT y){
    int i;
    for (i=0;i<N;i++){
        x+=y;
    }
}

…where we have a pure reduction.

void foo(TTT *a, int N, TTT x, TTT y){
    int i;
    for (i=0;i<N;i++){
        A[i] = x;
        x+=y;
    }
}

…where we have a FP induction variable (such that all intermediate values need
to be computed).

I pretty much agree with everything Danny, Sanjoy, and Hideki said.

-Andy