[Bug tree-optimization/49513] New: introducing a product inhibit vectorization

[Bug tree-optimization/49513] New: introducing a product inhibit vectorization

[vincenzo.innocente at cern dot ch]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=49513

           Summary: introducing a product inhibit vectorization
           Product: gcc
           Version: 4.7.0
            Status: UNCONFIRMED
          Severity: major
          Priority: P3
         Component: tree-optimization
        AssignedTo: unassigned@gcc.gnu.org
        ReportedBy: vincenzo.innocente@cern.ch


in the simple example below the first loop vectorize, the second not
I'm using
gcc version 4.7.0 20110528 (experimental) (GCC) 

#include<cmath>
float __attribute__ ((aligned(16))) a[1024];
float __attribute__ ((aligned(16))) s[1024];
float __attribute__ ((aligned(16))) c[1024];


inline float bar(float y, float x ){
  float xx = fabs(x);
  float yy = fabs(y);

  float tmp =0.0f;
  if (yy>xx) {
    tmp = yy;
    yy=xx; xx=tmp;
  }
  float t=yy/xx;
  return t;
}

void foo1() {
  for (int i=0; i!=1024; ++i) {
    float z = i;
    a[i] = bar(s[i],c[i]);  
  }
}
void foo2() {
  for (int i=0; i!=1024; ++i) {
    float z = i;
    a[i] = bar(z*s[i],z*c[i]);  
 }
}



c++   -std=c++0x -Ofast -c vectBug.cc -ftree-vectorizer-verbose=7

vectBug.cc:21: note: vect_model_load_cost: aligned.
vectBug.cc:21: note: vect_get_data_access_cost: inside_cost = 1, outside_cost =
0.
vectBug.cc:21: note: vect_model_load_cost: aligned.
vectBug.cc:21: note: vect_get_data_access_cost: inside_cost = 2, outside_cost =
0.
vectBug.cc:21: note: vect_model_store_cost: aligned.
vectBug.cc:21: note: vect_get_data_access_cost: inside_cost = 3, outside_cost =
0.
vectBug.cc:21: note: vect_model_load_cost: aligned.
vectBug.cc:21: note: vect_model_load_cost: inside_cost = 1, outside_cost = 0 .
vectBug.cc:21: note: vect_model_load_cost: aligned.
vectBug.cc:21: note: vect_model_load_cost: inside_cost = 1, outside_cost = 0 .
vectBug.cc:21: note: vect_model_simple_cost: inside_cost = 1, outside_cost = 0
.
vectBug.cc:21: note: vect_model_simple_cost: inside_cost = 1, outside_cost = 0
.
vectBug.cc:21: note: vect_model_simple_cost: inside_cost = 1, outside_cost = 0
.
vectBug.cc:21: note: vect_model_store_cost: aligned.
vectBug.cc:21: note: vect_model_store_cost: inside_cost = 1, outside_cost = 0 .
vectBug.cc:21: note: Cost model analysis: 
  Vector inside of loop cost: 6
  Vector outside of loop cost: 0
  Scalar iteration cost: 8
  Scalar outside cost: 0
  prologue iterations: 0
  epilogue iterations: 0
  Calculated minimum iters for profitability: 1

vectBug.cc:21: note:   Profitability threshold = 3

vectBug.cc:21: note: LOOP VECTORIZED.
vectBug.cc:20: note: vectorized 1 loops in function.

vectBug.cc:27: note: not vectorized: control flow in loop.
vectBug.cc:26: note: vectorized 0 loops in function.

[Bug tree-optimization/49513] PRE inhibits if-conversion and vectorization

[rguenth at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=49513

Richard Guenther <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
           Keywords|                            |missed-optimization
   Last reconfirmed|                            |2011.06.23 11:55:09
                 CC|                            |rguenth at gcc dot gnu.org
     Ever Confirmed|0                           |1
            Summary|introducing a product       |PRE inhibits if-conversion
                   |inhibit vectorization       |and vectorization

--- Comment #1 from Richard Guenther <rguenth at gcc dot gnu.org> 2011-06-23 11:55:09 UTC ---
That is because PRE decided to optimize the first iteration where it knows
that z == 0 and thus z*s[i] and z*c[i] are 0 and thus a[i] will be 0.  Which
means we confuse if-conversion which in turn causes this missed vectorization.
IL before if-conversion:

<bb 2>:
  goto <bb 6>;

<bb 3>:
  z_3 = (float) i_9;
  D.3280_4 = c[i_9];
  D.3281_5 = D.3280_4 * z_3;
  D.3282_6 = s[i_9];
  D.3283_7 = D.3282_6 * z_3;
  yy_13 = ABS_EXPR <D.3281_5>;
  yy_14 = ABS_EXPR <D.3283_7>;
  if (yy_13 < yy_14)
    goto <bb 5>;
  else
    goto <bb 4>;

<bb 4>:

<bb 5>:
  # yy_28 = PHI <yy_13(4), yy_14(3)>
  # yy_29 = PHI <yy_14(4), yy_13(3)>

<bb 6>:
  # yy_16 = PHI <yy_28(5), 0.0(2)>
  # yy_15 = PHI <yy_29(5), 0.0(2)>
  # i_30 = PHI <i_9(5), 0(2)>
  # ivtmp.44_24 = PHI <ivtmp.44_10(5), 1024(2)>
  t_17 = yy_15 / yy_16;
  a[i_30] = t_17;
  i_9 = i_30 + 1;
  ivtmp.44_10 = ivtmp.44_24 - 1;
  if (ivtmp.44_10 != 0)
    goto <bb 3>;
  else
    goto <bb 7>;

<bb 7>:
  return;

The PHI nodes in bb 6 is what makes if-conversion fail (thus, the
irregular loop entry which really should be peeled off).

This situation commonly occurs when PRE can compute the first iterations
result.  Manually peeling off the iteration like the following is a
workaround:

void foo2() {
  a[0] = 0;
  for (int i=1; i!=1024; ++i) {
    float z = i;
    a[i] = bar(z*s[i],z*c[i]);
 }
}

Not sure if your original issue you derived this testcase from really
matches the above problem though.

[Bug tree-optimization/49513] PRE inhibits if-conversion and vectorization

[vincenzo.innocente at cern dot ch]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=49513

--- Comment #2 from vincenzo Innocente <vincenzo.innocente at cern dot ch> 2011-06-23 12:16:59 UTC ---
thanks for the fast analysis.

the code in question was there also to test what the vectorized code would do
for x=0 and y=0 (it is extracted from a simplified version of atan2f that gcc
can vectorize).
Being a test, I can workaround (I've to test extreme conditions explicitely
anyhow).

In any case I think that any peeling will ruin alignmement.

 hoping gcc can find ways to avoid PRE and vectorization to clash.

       vincenzo




On 23 Jun, 2011, at 1:55 PM, rguenth at gcc dot gnu.org wrote:

> http://gcc.gnu.org/bugzilla/show_bug.cgi?id=49513
> 
> Richard Guenther <rguenth at gcc dot gnu.org> changed:
> 
>           What    |Removed                     |Added
> ----------------------------------------------------------------------------
>             Status|UNCONFIRMED                 |NEW
>           Keywords|                            |missed-optimization
>   Last reconfirmed|                            |2011.06.23 11:55:09
>                 CC|                            |rguenth at gcc dot gnu.org
>     Ever Confirmed|0                           |1
>            Summary|introducing a product       |PRE inhibits if-conversion
>                   |inhibit vectorization       |and vectorization
> 
> --- Comment #1 from Richard Guenther <rguenth at gcc dot gnu.org> 2011-06-23 11:55:09 UTC ---
> That is because PRE decided to optimize the first iteration where it knows
> that z == 0 and thus z*s[i] and z*c[i] are 0 and thus a[i] will be 0.  Which
> means we confuse if-conversion which in turn causes this missed vectorization.
> IL before if-conversion:
> 
> <bb 2>:
>  goto <bb 6>;
> 
> <bb 3>:
>  z_3 = (float) i_9;
>  D.3280_4 = c[i_9];
>  D.3281_5 = D.3280_4 * z_3;
>  D.3282_6 = s[i_9];
>  D.3283_7 = D.3282_6 * z_3;
>  yy_13 = ABS_EXPR <D.3281_5>;
>  yy_14 = ABS_EXPR <D.3283_7>;
>  if (yy_13 < yy_14)
>    goto <bb 5>;
>  else
>    goto <bb 4>;
> 
> <bb 4>:
> 
> <bb 5>:
>  # yy_28 = PHI <yy_13(4), yy_14(3)>
>  # yy_29 = PHI <yy_14(4), yy_13(3)>
> 
> <bb 6>:
>  # yy_16 = PHI <yy_28(5), 0.0(2)>
>  # yy_15 = PHI <yy_29(5), 0.0(2)>
>  # i_30 = PHI <i_9(5), 0(2)>
>  # ivtmp.44_24 = PHI <ivtmp.44_10(5), 1024(2)>
>  t_17 = yy_15 / yy_16;
>  a[i_30] = t_17;
>  i_9 = i_30 + 1;
>  ivtmp.44_10 = ivtmp.44_24 - 1;
>  if (ivtmp.44_10 != 0)
>    goto <bb 3>;
>  else
>    goto <bb 7>;
> 
> <bb 7>:
>  return;
> 
> The PHI nodes in bb 6 is what makes if-conversion fail (thus, the
> irregular loop entry which really should be peeled off).
> 
> This situation commonly occurs when PRE can compute the first iterations
> result.  Manually peeling off the iteration like the following is a
> workaround:
> 
> void foo2() {
>  a[0] = 0;
>  for (int i=1; i!=1024; ++i) {
>    float z = i;
>    a[i] = bar(z*s[i],z*c[i]);
> }
> }
> 
> Not sure if your original issue you derived this testcase from really
> matches the above problem though.
> 
> -- 
> Configure bugmail: http://gcc.gnu.org/bugzilla/userprefs.cgi?tab=email
> ------- You are receiving this mail because: -------
> You reported the bug.

--
Il est bon de suivre sa pente, pourvu que ce soit en montant. 
A.G.
http://www.flickr.com/photos/vin60/1320965757/

[Bug tree-optimization/49513] DOM inhibits if-conversion and vectorization

[rguenth at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=49513

Richard Guenther <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |law at gcc dot gnu.org
            Summary|PRE inhibits if-conversion  |DOM inhibits if-conversion
                   |and vectorization           |and vectorization

--- Comment #3 from Richard Guenther <rguenth at gcc dot gnu.org> 2011-06-23 12:58:44 UTC ---
(In reply to comment #2)
> thanks for the fast analysis.
> 
> the code in question was there also to test what the vectorized code would do
> for x=0 and y=0 (it is extracted from a simplified version of atan2f that gcc
> can vectorize).
> Being a test, I can workaround (I've to test extreme conditions explicitely
> anyhow).
> 
> In any case I think that any peeling will ruin alignmement.
> 
>  hoping gcc can find ways to avoid PRE and vectorization to clash.

I had a closer look and it is DOM jump-threading which creates this
rotated loop.  CCin Jeff who was working in this area - PRE avoids
this kind of transformation.  Jeff - can we avoid threading through
the loop header somehow?

[Bug tree-optimization/49513] DOM inhibits if-conversion and vectorization

[law at redhat dot com]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=49513

Jeffrey A. Law <law at redhat dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |law at redhat dot com

--- Comment #4 from Jeffrey A. Law <law at redhat dot com> 2011-07-08 21:11:09 UTC ---
Prohibiting this in DOM would effectively prevent DOM from doing any loop
rotations.

I don't see a good way to solve this...  Ideally we'd have a way to know if a
particular IF is convertable and we could avoid threading through it.  

Jeff

[Bug tree-optimization/49513] DOM inhibits if-conversion and vectorization

[pinskia at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=49513

Andrew Pinski <pinskia at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
      Known to work|                            |10.1.0, 11.1.0, 12.1.0,
                   |                            |8.1.0, 9.1.0
      Known to fail|                            |7.1.0

--- Comment #5 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Looks like this was fixed in GCC 8.