[Bug tree-optimization/64365] New: Predictive commoning after loop vectorization produces incorrect code.

[Bug tree-optimization/64365] New: Predictive commoning after loop vectorization produces incorrect code.

[congh at google dot com]

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

            Bug ID: 64365
           Summary: Predictive commoning after loop vectorization produces
                    incorrect code.
           Product: gcc
           Version: 5.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: tree-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: congh at google dot com

Compiling the following loop with -O3 on x86-64 produces incorrect code:


void foo(int *in) {
  for (int i = 14; i >= 10; i--) {
    in[i - 8] -= in[i];
    in[i - 5] += in[i] * 2;
    in[i - 4] += in[i];
  }
}


The incorrect code appears starting from pcom pass. Note that after this loop
is vectorized there exists read-after-write data dependence between the second
and third statements in the loop. The correct way to get the vector from in[i -
4] in the third statement is reading the memory after the write from the second
statement. However, in pcom pass, that vector is actually preloaded before the
loop. I think pcom ignores the aliasing between the memory addresses of vector
types (in this case MEM[&{in[i-3] : in[i-0]}] and MEM[&{in[i-5] : in[i-1]}].

[Bug tree-optimization/64365] Predictive commoning after loop vectorization produces incorrect code.

[congh at google dot com]

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

--- Comment #1 from Cong Hou <congh at google dot com> ---
Ping on this bug.

[Bug tree-optimization/64365] Predictive commoning after loop vectorization produces incorrect code.

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|                            |wrong-code
             Status|UNCONFIRMED                 |ASSIGNED
   Last reconfirmed|                            |2015-01-14
           Assignee|unassigned at gcc dot gnu.org      |rguenth at gcc dot gnu.org
     Ever confirmed|0                           |1

--- Comment #2 from Richard Biener <rguenth at gcc dot gnu.org> ---
Can you provide an executable testcase that abort()s when miscompiled and
terminates successfully if not?  Thus something suitable for the testsuite?
That also makes it possible to bisect to a commit that broke this.

A hint may be

   <bb 6>:
+  _6 = MEM[(int *)in_7(D) + 24B(OVF)];
   goto <bb 4>;

that appears in the pcom dump.

[Bug tree-optimization/64365] Predictive commoning after loop vectorization produces incorrect code.

[rguenth at gcc dot gnu.org]

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

--- Comment #3 from Richard Biener <rguenth at gcc dot gnu.org> ---
extern void abort (void);
extern int memcmp (const void * , const void *, __SIZE_TYPE__);

void __attribute__((noinline,noclone))
foo(int *in)
{
    for (int i = 14; i >= 10; i--) {
        in[i - 8] -= in[i];
        in[i - 5] += in[i] * 2;
        in[i - 4] += in[i];
    }
}

int main()
{    
  int x[16];
  int y[16] = { 0, 1, -22, -8, -8, 40, 38, 42, 46, 50, 24, 11, 12, 13, 14, 15
};
  int i;

  for (i = 0; i < 16; ++i)
    {
      x[i] = i;
      __asm__ volatile ("");
    }

  foo (x);

  if (memcmp (x, y, sizeof (x)) != 0)
    abort ();

  return 0;
}

[Bug tree-optimization/64365] [5 Regression] Predictive commoning after loop vectorization produces incorrect code.

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Priority|P3                          |P1
      Known to work|                            |4.9.2
   Target Milestone|---                         |5.0
            Summary|Predictive commoning after  |[5 Regression] Predictive
                   |loop vectorization produces |commoning after loop
                   |incorrect code.             |vectorization produces
                   |                            |incorrect code.
      Known to fail|                            |5.0

[Bug tree-optimization/64365] [5 Regression] Predictive commoning after loop vectorization produces incorrect code.

[jakub at gcc dot gnu.org]

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

Jakub Jelinek <jakub at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |jakub at gcc dot gnu.org

--- Comment #4 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Started with r214678.

[Bug tree-optimization/64365] [4.9/5 Regression] Predictive commoning after loop vectorization produces incorrect code.

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
      Known to work|4.9.2                       |4.8.3
            Summary|[5 Regression] Predictive   |[4.9/5 Regression]
                   |commoning after loop        |Predictive commoning after
                   |vectorization produces      |loop vectorization produces
                   |incorrect code.             |incorrect code.
      Known to fail|                            |4.9.2

--- Comment #5 from Richard Biener <rguenth at gcc dot gnu.org> ---
Testcase that also fails on the 4.9 branch:

extern void abort (void);
extern int memcmp (const void * , const void *, __SIZE_TYPE__);

void __attribute__((noinline,noclone))
foo(int *in)
{
  int i;
  for (i = 62; i >= 10; i--)
    {
      in[i - 8] -= in[i];
      in[i - 5] += in[i] * 2;
      in[i - 4] += in[i];
    }
}

int main()
{
  int x[64];
  int y[64] = { 0, 1, -2380134, -1065336, -1026376, 3264240, 3113534, 2328130,
3632054, 3839634, 2380136, 1065339, 1026380, 1496037, 1397286, 789976, 386408,
450984, 597112, 497464, 262008, 149184, 194768, 231519, 173984, 87753, 60712,
82042, 87502, 60014, 30050, 25550, 33570, 32386, 20464, 10675, 10868, 13329,
11794, 6892, 3988, 4564, 5148, 4228, 2284, 1568, 1848, 1943, 1472, 741, 628,
702, 714, 474, 230, 234, 238, 242, 120, 59, 60, 61, 62, 63 };
  int i;

  for (i = 0; i < 64; ++i)
    {
      x[i] = i;
      __asm__ volatile ("");
    }

  foo (x);

  if (memcmp (x, y, sizeof (x)) != 0)
    abort ();

  return 0;
}

[Bug tree-optimization/64365] [4.9/5 Regression] Predictive commoning after loop vectorization produces incorrect code.

[rguenth at gcc dot gnu.org]

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

--- Comment #6 from Richard Biener <rguenth at gcc dot gnu.org> ---
ICK.  Data-ref analysis issue with respect to how we handle pointer IVs
in dr_analyze_indices.  This results in

(compute_affine_dependence
  stmt_a: MEM[(int *)vectp_in.21_137] = vect__12.23_139;
  stmt_b: vect__16.26_145 = MEM[(int *)vectp_in.24_143];
(analyze_overlapping_iterations
  (chrec_a = {204B(OVF), +, 18446744073709551600}_1)
  (chrec_b = {216B(OVF), +, 18446744073709551600}_1)
(analyze_siv_subscript
(analyze_subscript_affine_affine
  (overlaps_a = no dependence)
  (overlaps_b = no dependence))
)
  (overlap_iterations_a = no dependence)
  (overlap_iterations_b = no dependence))
) -> no dependence

but this is only because 216 + n * (-16) never aliases index-wise.  That is,
data-ref analysis doesn't know about access sizes and in this case we have
partly overlapping vector accesses (it would treat exact overlaps correctly).
Unfortunately with partial overlaps being possible there is no way to
reduce a [ offset, size ] range down to a single index (even if all sizes
are equal).  In this special case we may see that the initial condition
is a constant and thus somehow gracefully "fail" (and for non-constant
initial condition hope we can't compute the dependence distance).

The pragmatic solution is to simply make possibly overlapping accesses
have distinct bases by adjusting CHREC_LEFT to be a multiple of the
access size.

Index: gcc/tree-data-ref.c
===================================================================
--- gcc/tree-data-ref.c (revision 219592)
+++ gcc/tree-data-ref.c (working copy)
@@ -883,6 +883,8 @@ dr_analyze_innermost (struct data_refere
@@ -970,7 +972,8 @@ dr_analyze_indices (struct data_referenc

   /* If the address operand of a MEM_REF base has an evolution in the
      analyzed nest, add it as an additional independent access-function.  */
-  if (TREE_CODE (ref) == MEM_REF)
+  if (TREE_CODE (ref) == MEM_REF
+      && TREE_CODE (TYPE_SIZE_UNIT (TREE_TYPE (ref))) == INTEGER_CST)
     {
       op = TREE_OPERAND (ref, 0);
       access_fn = analyze_scalar_evolution (loop, op);
@@ -992,6 +995,15 @@ dr_analyze_indices (struct data_referenc
                                fold_convert (ssizetype, memoff));
              memoff = build_int_cst (TREE_TYPE (memoff), 0);
            }
+         /* Adjust the offset so it is a multiple of the access type
+            size and thus we separate bases that can possibly be used
+            to produce partial overlaps (which the access_fn machinery
+            cannot handle).  */
+         wide_int rem
+           = wi::mod_trunc (off, TYPE_SIZE_UNIT (TREE_TYPE (ref)), SIGNED);
+         off = wide_int_to_tree (ssizetype, wi::sub (off, rem));
+         memoff = wide_int_to_tree (TREE_TYPE (memoff), rem);
+         /* And finally replace the initial condition.  */
          access_fn = chrec_replace_initial_condition
              (access_fn, fold_convert (orig_type, off));
          /* ???  This is still not a suitable base object for

[Bug tree-optimization/64365] [4.9/5 Regression] Predictive commoning after loop vectorization produces incorrect code.

[rguenth at gcc dot gnu.org]

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

--- Comment #7 from Richard Biener <rguenth at gcc dot gnu.org> ---
Author: rguenth
Date: Thu Jan 15 08:41:08 2015
New Revision: 219634

URL: https://gcc.gnu.org/viewcvs?rev=219634&root=gcc&view=rev
Log:
2015-01-15  Richard Biener  <rguenther@suse.de>

    PR middle-end/64365
    * tree-data-ref.c (dr_analyze_indices): Make sure that accesses
    for MEM_REF access functions with the same base can never partially
    overlap.

    * gcc.dg/torture/pr64365.c: New testcase.

Added:
    trunk/gcc/testsuite/gcc.dg/torture/pr64365.c
Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/testsuite/ChangeLog
    trunk/gcc/tree-data-ref.c

[Bug tree-optimization/64365] [4.9 Regression] Predictive commoning after loop vectorization produces incorrect code.

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
      Known to work|                            |5.0
            Summary|[4.9/5 Regression]          |[4.9 Regression] Predictive
                   |Predictive commoning after  |commoning after loop
                   |loop vectorization produces |vectorization produces
                   |incorrect code.             |incorrect code.
      Known to fail|5.0                         |

--- Comment #8 from Richard Biener <rguenth at gcc dot gnu.org> ---
Fixed on trunk sofar (surely latent on the 4.8 branch as well).

[Bug tree-optimization/64365] [4.9 Regression] Predictive commoning after loop vectorization produces incorrect code.

[congh at google dot com]

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

--- Comment #9 from Cong Hou <congh at google dot com> ---
Thanks for the fix, Richard!

[Bug tree-optimization/64365] [4.9 Regression] Predictive commoning after loop vectorization produces incorrect code.

[brooks at gcc dot gnu.org]

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

Brooks Moses <brooks at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |brooks at gcc dot gnu.org

--- Comment #10 from Brooks Moses <brooks at gcc dot gnu.org> ---
Richard, are you expecting to backport this to the 4.9 branch as well?

Thanks!

[Bug tree-optimization/64365] [4.9 Regression] Predictive commoning after loop vectorization produces incorrect code.

[rguenther at suse dot de]

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

--- Comment #11 from rguenther at suse dot de <rguenther at suse dot de> ---
On Thu, 22 Jan 2015, brooks at gcc dot gnu.org wrote:

> https://gcc.gnu.org/bugzilla/show_bug.cgi?id=64365
> 
> Brooks Moses <brooks at gcc dot gnu.org> changed:
> 
>            What    |Removed                     |Added
> ----------------------------------------------------------------------------
>                  CC|                            |brooks at gcc dot gnu.org
> 
> --- Comment #10 from Brooks Moses <brooks at gcc dot gnu.org> ---
> Richard, are you expecting to backport this to the 4.9 branch as well?

Yes, I will do that after I'm sure there isn't any fallout (that
is, it will make the next release at least)

[Bug tree-optimization/64365] [4.9 Regression] Predictive commoning after loop vectorization produces incorrect code.

[brooks at gcc dot gnu.org]

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

--- Comment #12 from Brooks Moses <brooks at gcc dot gnu.org> ---
Thanks, Richard!  It looks like I'll need to backport this to our
google/gcc-4_9 branch before that happens; any chance you already have a
version of this patch that works with 4.9?  The wide_int pieces don't exist in
4.9 AFAICT.

[Bug tree-optimization/64365] [4.9 Regression] Predictive commoning after loop vectorization produces incorrect code.

[brooks at gcc dot gnu.org]

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

--- Comment #13 from Brooks Moses <brooks at gcc dot gnu.org> ---
FWIW, if you haven't done the 4.9 backport yet, this is what I ended up with. 
I'm not sure it's optimal, but it seems to work.


Index: gcc/tree-data-ref.c
===================================================================
--- gcc/tree-data-ref.c (revision 220259)
+++ gcc/tree-data-ref.c (working copy)
@@ -973,6 +973,24 @@
                                fold_convert (ssizetype, memoff));
              memoff = build_int_cst (TREE_TYPE (memoff), 0);
            }
+         /* Adjust the offset so it is a multiple of the access type
+            size and thus we separate bases that can possibly be used
+            to produce partial overlaps (which the access_fn machinery
+            cannot handle).  */
+         double_int rem;
+         if (TYPE_SIZE_UNIT (TREE_TYPE (ref))
+             && TREE_CODE (TYPE_SIZE_UNIT (TREE_TYPE (ref))) == INTEGER_CST
+             && !integer_zerop (TYPE_SIZE_UNIT (TREE_TYPE (ref))))
+           rem = tree_to_double_int (off).mod
+                (tree_to_double_int (TYPE_SIZE_UNIT (TREE_TYPE (ref))), false,
+                 TRUNC_MOD_EXPR);
+         else
+           /* If we can't compute the remainder simply force the initial
+              condition to zero.  */
+           rem = tree_to_double_int (off);
+         off = double_int_to_tree (ssizetype, tree_to_double_int (off) - rem);
+         memoff = double_int_to_tree (TREE_TYPE (memoff), rem);
+         /* And finally replace the initial condition.  */
          access_fn = chrec_replace_initial_condition
              (access_fn, fold_convert (orig_type, off));
          /* ???  This is still not a suitable base object for

[Bug tree-optimization/64365] [4.9 Regression] Predictive commoning after loop vectorization produces incorrect code.

[rguenth at gcc dot gnu.org]

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

--- Comment #15 from Richard Biener <rguenth at gcc dot gnu.org> ---
Author: rguenth
Date: Thu Feb 19 14:13:16 2015
New Revision: 220815

URL: https://gcc.gnu.org/viewcvs?rev=220815&root=gcc&view=rev
Log:
2015-02-19  Richard Biener  <rguenther@suse.de>

    Backport from mainline
    2014-12-09  Richard Biener  <rguenther@suse.de>

    PR middle-end/64199
    * fold-const.c (fold_binary_loc): Use TREE_OVERFLOW_P.

    * gcc.dg/torture/pr64199.c: New testcase.

    2015-01-14  Richard Biener  <rguenther@suse.de>

    PR tree-optimization/64493
    PR tree-optimization/64495
    * tree-vect-loop.c (vect_finalize_reduction): For double-reductions
    assign the proper vectorized PHI to the inner loop exit PHIs.

    * gcc.dg/vect/pr64493.c: New testcase.
    * gcc.dg/vect/pr64495.c: Likewise.

    2015-01-27  Richard Biener  <rguenther@suse.de>

    PR tree-optimization/56273
    PR tree-optimization/59124
    PR tree-optimization/64277
    * tree-vrp.c (vrp_finalize): Emit array-bound warnings only
    from the first VRP pass.

    * g++.dg/warn/Warray-bounds-6.C: New testcase.
    * gcc.dg/Warray-bounds-12.c: Likewise.
    * gcc.dg/Warray-bounds-13.c: Likewise.

    2015-02-19  Richard Biener  <rguenther@suse.de>

    Backport from mainline
    2015-01-15  Richard Biener  <rguenther@suse.de>

    PR middle-end/64365
    * tree-data-ref.c (dr_analyze_indices): Make sure that accesses
    for MEM_REF access functions with the same base can never partially
    overlap.

    * gcc.dg/torture/pr64365.c: New testcase.

Added:
    branches/gcc-4_9-branch/gcc/testsuite/g++.dg/warn/Warray-bounds-6.C
    branches/gcc-4_9-branch/gcc/testsuite/gcc.dg/Warray-bounds-12.c
    branches/gcc-4_9-branch/gcc/testsuite/gcc.dg/Warray-bounds-13.c
    branches/gcc-4_9-branch/gcc/testsuite/gcc.dg/torture/pr64199.c
    branches/gcc-4_9-branch/gcc/testsuite/gcc.dg/torture/pr64365.c
    branches/gcc-4_9-branch/gcc/testsuite/gcc.dg/vect/pr64493.c
    branches/gcc-4_9-branch/gcc/testsuite/gcc.dg/vect/pr64495.c
Modified:
    branches/gcc-4_9-branch/gcc/ChangeLog
    branches/gcc-4_9-branch/gcc/fold-const.c
    branches/gcc-4_9-branch/gcc/testsuite/ChangeLog
    branches/gcc-4_9-branch/gcc/tree-data-ref.c
    branches/gcc-4_9-branch/gcc/tree-vect-loop.c
    branches/gcc-4_9-branch/gcc/tree-vrp.c

[Bug tree-optimization/64365] [4.9 Regression] Predictive commoning after loop vectorization produces incorrect code.

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|ASSIGNED                    |RESOLVED
      Known to work|                            |4.9.3
         Resolution|---                         |FIXED
   Target Milestone|5.0                         |4.9.3

--- Comment #16 from Richard Biener <rguenth at gcc dot gnu.org> ---
Fixed.