[PATCH, PR 44258] Detect partially overlapping SRA accesses reliably

[Martin Jambor]

Hi,

this is an embarrassing bug.  I don't know what I was thinking when I
wrote the code detecting partially overlapping accesses but just
looking the neighboring accesses in the sorted vector clearly isn't
enough and we must check for this property also when building the
access tree.

Bootstrapped and tested on x86_64-linux, OK for trunk and for 4.5 as
well, after a while?

Thanks,

Martin


2010-06-10  Martin Jambor  <mjambor@suse.cz>

	PR tree-optimization/44258
	* tree-sra.c (build_access_subtree): Return false iff there is a
	partial overlap.
	(build_access_trees): Likewise.
	(analyze_all_variable_accesses): Disqualify candidates if
	build_access_trees returns true for them.

	* testsuite/gcc.dg/tree-ssa/pr44258.c: New test.

Index: mine/gcc/testsuite/gcc.dg/tree-ssa/pr44258.c
===================================================================
--- /dev/null
+++ mine/gcc/testsuite/gcc.dg/tree-ssa/pr44258.c
@@ -0,0 +1,43 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-esra-details" } */
+
+struct blah
+{
+  char a[4];
+};
+
+struct str
+{
+  struct blah b1;
+  char x;
+};
+
+struct val
+{
+  char y;
+  struct blah b2;
+};
+
+union U
+{
+  struct str str;
+  struct val val;
+};
+
+
+extern struct blah e_b1, e_b2;
+extern union U *e_u;
+
+int foo (int b)
+{
+  union U u;
+
+  u.str.b1 = e_b1;
+  u.val.b2 = e_b2;
+  u.str.b1.a[3] = 0;
+
+  *e_u = u;
+}
+
+/* { dg-final { scan-tree-dump-times "Created a replacement" 0 "esra"} } */
+/* { dg-final { cleanup-tree-dump "esra" } } */
Index: mine/gcc/tree-sra.c
===================================================================
--- mine.orig/gcc/tree-sra.c
+++ mine/gcc/tree-sra.c
@@ -1689,9 +1689,10 @@ get_unrenamed_access_replacement (struct
 
 /* Build a subtree of accesses rooted in *ACCESS, and move the pointer in the
    linked list along the way.  Stop when *ACCESS is NULL or the access pointed
-   to it is not "within" the root.  */
+   to it is not "within" the root.  Return false iff some accesses partially
+   overlap.  */
 
-static void
+static bool
 build_access_subtree (struct access **access)
 {
   struct access *root = *access, *last_child = NULL;
@@ -1706,24 +1707,32 @@ build_access_subtree (struct access **ac
 	last_child->next_sibling = *access;
       last_child = *access;
 
-      build_access_subtree (access);
+      if (!build_access_subtree (access))
+	return false;
     }
+
+  if (*access && (*access)->offset < limit)
+    return false;
+
+  return true;
 }
 
 /* Build a tree of access representatives, ACCESS is the pointer to the first
-   one, others are linked in a list by the next_grp field.  Decide about scalar
-   replacements on the way, return true iff any are to be created.  */
+   one, others are linked in a list by the next_grp field.  Return false iff
+   some accesses partially overlap.  */
 
-static void
+static bool
 build_access_trees (struct access *access)
 {
   while (access)
     {
       struct access *root = access;
 
-      build_access_subtree (&access);
+      if (!build_access_subtree (&access))
+	return false;
       root->next_grp = access;
     }
+  return true;
 }
 
 /* Return true if expr contains some ARRAY_REFs into a variable bounded
@@ -2062,9 +2071,7 @@ analyze_all_variable_accesses (void)
       struct access *access;
 
       access = sort_and_splice_var_accesses (var);
-      if (access)
-	build_access_trees (access);
-      else
+      if (!access || !build_access_trees (access))
 	disqualify_candidate (var,
 			      "No or inhibitingly overlapping accesses.");
     }