Bug 35229

Summary: Vectorizer doesn't support dependence created by predictive commoning or PRE
Product: gcc Reporter: Ira Rosen <irar>
Component: tree-optimizationAssignee: Not yet assigned to anyone <unassigned>
Status: NEW ---    
Severity: enhancement CC: aldot, changpeng.fang, gaoyunzhong, gcc-bugs, rguenth, spop
Priority: P3 Keywords: missed-optimization
Version: 4.3.0   
Target Milestone: ---   
Host: Target:
Build: Known to work:
Known to fail: Last reconfirmed: 2009-02-25 14:12:51
Bug Depends on:    
Bug Blocks: 53947, 39300    

Description Ira Rosen 2008-02-17 09:25:02 UTC
The following type of dependence, similar to such that would be created by predictive commoning (or even PRE), is not supported by the vectorizer: 

 for (i = 1; i <= i_2; ++i)
   {
     a[i] = (b[i] + x) * .5f;
     x = b[i];
   }
Comment 1 Richard Biener 2009-02-25 14:12:51 UTC
Indeed.  Proper testcase:

float res[1024], data[1024];

void foo(void)
{
  int i;
  float tmp = data[0];
  for (i = 1; i < 1024; ++i)
    {
      float tmp2 = data[i];
      res[i] = tmp + tmp2;
      tmp = tmp2;
    }
}

manually "optimized" from

      res[i] = data[i] + data[i-1];
Comment 2 Richard Biener 2009-02-25 14:33:18 UTC
Or like the following, which is just a bunch of reductions of two elements

float data[1024];

void foo(void)
{
  int i;
  for (i = 1; i < 1024; ++i)
    data[i] = data[i] + data[i-1];
}
Comment 3 Ira Rosen 2009-03-17 13:33:59 UTC
(In reply to comment #2)
> Or like the following, which is just a bunch of reductions of two elements
> float data[1024];
> void foo(void)
> {
>   int i;
>   for (i = 1; i < 1024; ++i)
>     data[i] = data[i] + data[i-1];
> }

Actually, this loop is not vectorizable. res and data have to be different arrays, otherwise we get read after write dependence with distance 1.

Ira
Comment 4 Michael Matz 2009-07-22 15:31:10 UTC
Subject: Bug 35229

Author: matz
Date: Wed Jul 22 15:30:50 2009
New Revision: 149942

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=149942
Log:
        PR tree-optimization/35229
        PR tree-optimization/39300

        * tree-ssa-pre.c (includes): Include tree-scalar-evolution.h.
        (inhibit_phi_insertion): New function.
        (insert_into_preds_of_block): Call it for REFERENCEs.
        (init_pre): Initialize and finalize scalar evolutions.
        * Makefile.in (tree-ssa-pre.o): Depend on tree-scalar-evolution.h .

testsuite/
        * gcc.dg/vect/vect-pre-interact.c: New test.

Added:
    trunk/gcc/testsuite/gcc.dg/vect/vect-pre-interact.c
Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/testsuite/ChangeLog
    trunk/gcc/tree-ssa-pre.c

Comment 5 Richard Biener 2012-07-19 11:28:19 UTC
*** Bug 43425 has been marked as a duplicate of this bug. ***
Comment 6 Richard Biener 2013-09-26 14:57:19 UTC
*** Bug 57223 has been marked as a duplicate of this bug. ***
Comment 7 Richard Biener 2013-09-26 14:57:45 UTC
*** Bug 56595 has been marked as a duplicate of this bug. ***
Comment 8 Richard Biener 2013-09-26 15:07:07 UTC
Still happens for partially loop invariant loads (partially loop invariant as
in blocked by a following aliasing store in the loop body).  Like seen in
PR57223.