[PATCH] Fix PR64365

[PATCH] Fix PR64365

[Richard Biener]

This fixes an issue in dependence analysis and how we make pointer
dereferences visible to it.  Basically dependence analysis works
on indices (assuming we deal with arrays) and thus never needs
sth like an access size (because indices are non-sparse and
different index means a different memory area).  Dereferences
breaks this because we present dependence analysis with a
sparse index space.  Thus to rule out partially overlapping
accesses we have to make sure to separate bases (only equal
bases get treated this way).

The following ensures this by making the indices multiples of
the access size (and shifting the byte offset modulo the access
size to the base object).

Bootstrap and regtest running on x86_64-unknown-linux-gnu.

Richard.

2015-01-14  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.

Index: gcc/tree-data-ref.c
===================================================================
--- gcc/tree-data-ref.c	(revision 219592)
+++ gcc/tree-data-ref.c	(working copy)
@@ -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
Index: gcc/testsuite/gcc.dg/torture/pr64365.c
===================================================================
--- gcc/testsuite/gcc.dg/torture/pr64365.c	(revision 0)
+++ gcc/testsuite/gcc.dg/torture/pr64365.c	(working copy)
@@ -0,0 +1,37 @@
+/* { dg-do run } */
+/* { dg-require-effective-target int32plus } */
+
+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;
+}

Re: [PATCH] Fix PR64365

[Richard Biener]

On Wed, 14 Jan 2015, Richard Biener wrote:

> 
> This fixes an issue in dependence analysis and how we make pointer
> dereferences visible to it.  Basically dependence analysis works
> on indices (assuming we deal with arrays) and thus never needs
> sth like an access size (because indices are non-sparse and
> different index means a different memory area).  Dereferences
> breaks this because we present dependence analysis with a
> sparse index space.  Thus to rule out partially overlapping
> accesses we have to make sure to separate bases (only equal
> bases get treated this way).
> 
> The following ensures this by making the indices multiples of
> the access size (and shifting the byte offset modulo the access
> size to the base object).
> 
> Bootstrap and regtest running on x86_64-unknown-linux-gnu.

I have applied the following variant which also handles NULL
TYPE_SIZE_UNIT and treats those cases less conservative by
simply forcing the index to be always zero.

Bootstrapped and tested on x86_64-unknown-linux-gnu, applied to trunk
sofar.

Richard.

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.

Index: gcc/tree-data-ref.c
===================================================================
--- gcc/tree-data-ref.c	(revision 219603)
+++ gcc/tree-data-ref.c	(working copy)
@@ -992,6 +994,22 @@ 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;
+	  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 = wi::mod_trunc (off, TYPE_SIZE_UNIT (TREE_TYPE (ref)), SIGNED);
+	  else
+	    /* If we can't compute the remainder simply force the initial
+	       condition to zero.  */
+	    rem = off;
+	  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

Index: gcc/testsuite/gcc.dg/torture/pr64365.c
===================================================================
--- gcc/testsuite/gcc.dg/torture/pr64365.c	(revision 0)
+++ gcc/testsuite/gcc.dg/torture/pr64365.c	(working copy)
@@ -0,0 +1,37 @@
+/* { dg-do run } */
+/* { dg-require-effective-target int32plus } */
+
+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;
+}