[Bug c/43423] New: gcc should vectorize this loop through "iteration range splitting"

[Bug c/43423] New: gcc should vectorize this loop through "iteration range splitting"

[changpeng dot fang at amd dot com]

chfang@pathscale:~/gcc$ cat foo.c
int a[100], b[100], c[100];

void foo(int n, int mid)
{
  int i;
  for(i=0; i<n; i++)
    {
      if (i < mid)
        a[i] = a[i] + b[i];
      else
        a[i] = a[i] + c[i];
    }
}


chfang@pathscale:~/gcc$ gcc -O3 -ftree-vectorizer-verbose=7 -c foo.c

foo.c:6: note: not vectorized: control flow in loop.
foo.c:3: note: vectorized 0 loops in function.

This loop can be vectorized by icc.

For this case, I would expect to see two loops with iteration range
of [0, mid) and [mid, n). Then both loops can be vectorized.

I am not sure which pass in gcc should do this iteration range splitting.


-- 
           Summary: gcc should vectorize this loop through "iteration range
                    splitting"
           Product: gcc
           Version: 4.5.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: c
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: changpeng dot fang at amd dot com


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

[Bug c/43423] gcc should vectorize this loop through "iteration range splitting"

[amonakov at gcc dot gnu dot org]

------- Comment #1 from amonakov at gcc dot gnu dot org  2010-03-18 18:13 -------
Graphite is able to split the loop, but then the vectorizer punts anyway:

gcc -O3 -ftree-vectorizer-verbose=7 -fgraphite-identity -S t.c

t.c:11: note: not vectorized: number of iterations cannot be computed.
t.c:9: note: not vectorized: number of iterations cannot be computed.
t.c:3: note: vectorized 0 loops in function.


-- 

amonakov at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |amonakov at gcc dot gnu dot
                   |                            |org


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

[Bug tree-optimization/43423] gcc should vectorize this loop through "iteration range splitting"

[pinskia at gcc dot gnu dot org]

------- Comment #2 from pinskia at gcc dot gnu dot org  2010-03-18 18:22 -------
Well it could be vectorized even without range splitting.  The issue is the
"sinking" of the store to a[i].


-- 

pinskia at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
          Component|c                           |tree-optimization


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

[Bug tree-optimization/43423] gcc should vectorize this loop through "iteration range splitting"

[sebpop at gmail dot com]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain, Size: 414 bytes --]



------- Comment #3 from sebpop at gmail dot com  2010-03-18 18:33 -------
Subject: Re:  gcc should vectorize this loop 
        through "iteration range splitting"

> Well it could be vectorized even without range splitting.  The issue is the
> "sinking" of the store to a[i].

You mean that the problem is the if-conversion of the stores
"a[i] = ..."


-- 


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

Re: [Bug tree-optimization/43423] gcc should vectorize this loop through "iteration range splitting"

[Sebastian Pop]

> Well it could be vectorized even without range splitting.  The issue is the
> "sinking" of the store to a[i].

You mean that the problem is the if-conversion of the stores
"a[i] = ..."

[Bug tree-optimization/43423] gcc should vectorize this loop through "iteration range splitting"

[pinskia at gcc dot gnu dot org]

------- Comment #4 from pinskia at gcc dot gnu dot org  2010-03-18 18:38 -------
(In reply to comment #3)
> Subject: Re:  gcc should vectorize this loop 
>         through "iteration range splitting"
> You mean that the problem is the if-conversion of the stores
> "a[i] = ..."

If we rewrite the code like:
int a[100], b[100], c[100];

void foo(int n, int mid)
{
  int i;
  for(i=0; i<n; i++)
    {
      int t;
      int ai = a[i], bi = b[i], ci = c[i];
      if (i < mid)
        t = ai + bi;
      else
        t = ai + ci;
      a[i] = t;
    }
}

--- CUT ---
This gets vectorized as we produce an if-cvt first.


-- 

pinskia at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
     Ever Confirmed|0                           |1
           Keywords|                            |missed-optimization
   Last reconfirmed|0000-00-00 00:00:00         |2010-03-18 18:38:42
               date|                            |


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

[Bug tree-optimization/43423] gcc should vectorize this loop through "iteration range splitting"

[spop at gcc dot gnu dot org]

------- Comment #5 from spop at gcc dot gnu dot org  2010-03-18 18:51 -------
Yes,
I think we should improve if-conversion to handle more complex cases.


-- 


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

[Bug tree-optimization/43423] gcc should vectorize this loop through if-conversion

[spop at gcc dot gnu dot org]

------- Comment #6 from spop at gcc dot gnu dot org  2010-04-08 17:47 -------
I changed the title of this bug to match the comments in the PR:
we should vectorize this loop using if-conversion, and not "iteration
range splitting".

Also note that in general, by doing an "iteration range splitting" the data 
locality in the two loops could be worse than in the if-converted loop.


-- 

spop at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
            Summary|gcc should vectorize this   |gcc should vectorize this
                   |loop through "iteration     |loop through if-conversion
                   |range splitting"            |


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

[Bug tree-optimization/43423] gcc should vectorize this loop through if-conversion

[changpeng dot fang at amd dot com]

------- Comment #7 from changpeng dot fang at amd dot com  2010-05-07 21:41 -------
(In reply to comment #4)
> (In reply to comment #3)
> > Subject: Re:  gcc should vectorize this loop 
> >         through "iteration range splitting"
> > You mean that the problem is the if-conversion of the stores
> > "a[i] = ..."
> 
> If we rewrite the code like:
> int a[100], b[100], c[100];
> 
> void foo(int n, int mid)
> {
>   int i;
>   for(i=0; i<n; i++)
>     {
>       int t;
>       int ai = a[i], bi = b[i], ci = c[i];
>       if (i < mid)
>         t = ai + bi;
>       else
>         t = ai + ci;
>       a[i] = t;
>     }
> }
> 
> --- CUT ---
> This gets vectorized as we produce an if-cvt first.
> 

There are both correctness and performance issues in the re-written code.
b[i] or c[i] may not be executed in the original loop.


-- 


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

[Bug tree-optimization/43423] gcc should vectorize this loop through if-conversion

[spop at gcc dot gnu dot org]

------- Comment #8 from spop at gcc dot gnu dot org  2010-05-24 22:44 -------
-fgraphite-identity does iteration splitting for this case.


-- 


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

[Bug tree-optimization/43423] gcc should vectorize this loop through if-conversion

[changpeng dot fang at amd dot com]

------- Comment #9 from changpeng dot fang at amd dot com  2010-05-24 22:47 -------
(In reply to comment #8)
> -fgraphite-identity does iteration splitting for this case.

Do you know why it could not be vectorized after iteration 
range splitting?


-- 


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

[Bug tree-optimization/43423] gcc should vectorize this loop through if-conversion

[spop at gcc dot gnu dot org]

------- Comment #10 from spop at gcc dot gnu dot org  2010-05-24 23:02 -------
note: not vectorized: number of iterations cannot be computed.

Graphite has a problem with the generation of induction variables types
that makes the code harder to analyze after Graphite.  I will try to get this
fixed to make this loop vectorized with the iteration range splitting that
Graphite does by default. 

Sebastian


-- 


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

[Bug tree-optimization/43423] gcc should vectorize this loop through if-conversion

[spop at gcc dot gnu dot org]

------- Comment #11 from spop at gcc dot gnu dot org  2010-05-25 23:33 -------
This is not a IV type problem: the number of iterations may be zero when mid ==
0 or mid == n, so the number of iterations analysis has a condition under which
niter may_be_zero.

I sent out a patch that makes niter return a COND_EXPR
instead of a chrec_dont_know:
http://gcc.gnu.org/ml/gcc-patches/2010-05/msg01927.html

With that patch I now get 
  note: not vectorized: data ref analysis failed D.2726_51 = a[var.9_55];


-- 


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

[Bug tree-optimization/43423] gcc should vectorize this loop through if-conversion

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
         Resolution|---                         |FIXED
   Target Milestone|---                         |7.0
             Status|ASSIGNED                    |RESOLVED

--- Comment #14 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
So GCC 7 is able to optimize this loop fully and split it into two at -O3
(r7-3966) after my comment #12.

Also starting with GCC 7, we were able to vectorize the loop at -O2
-ftree-vectorize since tree-if-conv.c can do the ifconversion (I don't have the
revision).

So this is all fixed anyways.

[Bug tree-optimization/43423] gcc should vectorize this loop through if-conversion

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |ASSIGNED
           Severity|normal                      |enhancement
                 CC|                            |pinskia at gcc dot gnu.org

--- Comment #13 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
The improvement in comment #12 is something which I am working on.