llvm dev - May 2016 - Working on FP SCEV Analysis

Hi,

I'm working now on extending SCEV Analysis and adding FP support.
At the beginning, I want to vectorize this loop:

float fp_inc;

  float x = init;
  for (int i=0;i<N;i++){
    A[i] = x;
    x += fp_inc; // Loop invariant variable or constant
  }

In this loop "x" is a FP induction variable. But it is not the
"primary" induction and loop trip count is still depends on integer
induction "i".

In the future, I plan to work on "primary" FP inductions.
Intel compiler vectorizes FP-induction loops, GCC does not.

I wanted to hear that community does not have any principal objections for this
work.
Thank you.

-        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/20160516/f480d862/attachment.html>

Adding Sanjoy Das as I think he will have lots of thoughts on this general
subject.

On Mon, May 16, 2016 at 6:29 AM Demikhovsky, Elena via llvm-dev <
llvm-dev at lists.llvm.org> wrote:
> Hi,
>
> I’m working now on extending SCEV Analysis and adding FP support.
> At the beginning, I want to vectorize this loop:
>
> float fp_inc;
>
>   float x = init;
>   for (int i=0;i<N;i++){
>     A[i] = x;
>     x += fp_inc; // Loop invariant variable or constant
>   }
>
> In this loop “x” is a FP induction variable. But it is not the “primary”
> induction and loop trip count is still depends on integer induction “i”.
>
> In the future, I plan to work on “primary” FP inductions.
> Intel compiler vectorizes FP-induction loops, GCC does not.
>
> I wanted to hear that community does not have any principal objections for
> this work.
> Thank you.
>
>
>    - * 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
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160516/e12ee6fe/attachment.html>

[+CC Andy]

Hi Elena,

I don't have any fundamental issues with teaching SCEV about floating
point types, but given this will be a major change, I think a high
level roadmap should be discussed on llvm-dev before we start
reviewing and committing changes.

Here are some issues that I think are worth discussing:

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

  - I presume you'll want SCEV expressions for `sitofp` and `uitofp`.
    (The most important question:) With these in the game, what is the
    canonical representation of SCEV expressions that can be expressed
    as, say, both `sitofp(A + B)` and `sitofp(A) + sitofp(B)`?

    Will we have a way to mark expressions (like we have `nsw` and
    `nuw` for `sext` and `zext`) which we can distribute `sitofp` and
    `uitofp` over?

    Same questions for `fptosi` and `fptoui`.

  - How will you partition the logic between floating and integer
    expressions in SCEV-land?  Will you have, say, `SCEVAddExpr` do
    different things based on type, or will you split it into
    `SCEVIAddExpr` and `SCEVFAddExpr`? [0]

    * There are likely to be similarities too -- e.g. the "inductive"
      or "control flow" aspect of `SCEVAddRecExpr` is likely to be
      common between floating point add recurrences[1], and integer add
      recurrences; and part of figuring out the partitioning is also
      figuring out how to re-use these bits of logic.
	

[0]: I'll prefer the latter since e.g. integer addition is
associative, but floating point addition isn't; and it is better to
force programmers to handle the two operations differently.

[1]: For instance, things like this:
https://github.com/llvm-mirror/llvm/blob/master/lib/Analysis/ScalarEvolution.cpp#L7564
are likely to stay common between floating point and integer add recs.

-- Sanjoy

One thought I’ve had about this in the past —

SCEV is useful for proving two expressions are equivalent (in general, not just
specifically for loop induction variables). This gets a little bit trickier with
fast-math; for example, suppose two expressions are equivalent, but *only* with
reassociativity allowed?

This would be useful to make N-ary reassociate or similar algorithms work with
float, as it currently uses SCEV to prove equivalence, but fast-math makes it
become much trickier (and without fast-math, there’s not much you can prove).

—escha
> On May 16, 2016, at 6:07 AM, Demikhovsky, Elena via llvm-dev <llvm-dev
at lists.llvm.org <mailto:llvm-dev at lists.llvm.org>> wrote:
> 
> Hi,
>  
> I’m working now on extending SCEV Analysis and adding FP support.
> At the beginning, I want to vectorize this loop:
>  
> float fp_inc;
>  
>   float x = init;
>   for (int i=0;i<N;i++){
>     A[i] = x;
>     x += fp_inc; // Loop invariant variable or constant
>   }
>  
> In this loop “x” is a FP induction variable. But it is not the “primary”
induction and loop trip count is still depends on integer induction “i”.
>  
> In the future, I plan to work on “primary” FP inductions.
> Intel compiler vectorizes FP-induction loops, GCC does not.
>  
> I wanted to hear that community does not have any principal objections for
this work.
> Thank you.
>  
> 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 <mailto:llvm-dev at lists.llvm.org>
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
<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/20160516/4ebd7516/attachment.html>

Hi Escha,

via llvm-dev wrote:
> One thought I’ve had about this in the past —
>
> SCEV is useful for proving two expressions are equivalent (in general,
> not just specifically for loop induction variables). This gets a little
> bit trickier with fast-math; for example, suppose two expressions are
> equivalent, but *only* with reassociativity allowed?
This isn't too different from "sext(a + b) == sext(a) + sext(b) only
if the addition is nsw".

However, it wasn't clear to me from the lang-ref what the fastmath
flags really mean.  What is the semantics of a program that computes
((a +fast b) +fast c) when ((a + b) + c) != (a + (b + c))?  Does it
have UB (in which case we can't hoist fastmath arithmetic) or is it
more like poison?  Depending on the answer, for fastmath we can
considering doing what we do today for nuw/nsw (which has its own set
of issues, but at least wouldn't require us to start from scratch).

-- Sanjoy