Re: Teach same_types_for_tbaa to structurally compare arrays, pointers and vectors

[Martin Jambor <mjambor@suse.cz>]

Hi,

On Wed, May 29 2019, Jan Hubicka wrote:
>> > but we do not optimize it. I.e. optimized dump has:
>> >
>> > test ()
>> > {
>> >   struct bar * barptr.0_1;
>> >   struct foo * fooptr.1_2;
>> >   int _6;
>> >
>> >   <bb 2> [local count: 1073741824]:
>> >   barptr.0_1 = barptr;
>> >   barptr.0_1->val2 = 1;
>> >   fooptr.1_2 = fooptr;
>> >   MEM[(struct foo *)fooptr.1_2] = 0;
>> >   _6 = barptr.0_1->val2;
>> >   return _6;
>> > }
>> >
>> > I see no reason why we should not constant propagate the return value.
>> 
>> Indeed a good example.  Make it work and add it to the testsuite ;)
>
> I think Martin Jambor is working on it.  One needs -fno-tree-sra to
> get this optimized :)
> Othewise we punt on the check that both types in MEM_REF are the same.
>

I'd like to fix this with the following patch which passes bootstrap but
I have just found that it makes the following three tests fail:

 gcc.dg/tree-ssa/ssa-dse-26.c scan-tree-dump-times dse1 "Deleted dead store: x = " 1
 gcc.dg/tree-ssa/ssa-dse-26.c scan-tree-dump-times dse1 "Deleted dead store: y = " 1
 gnat.dg/opt39.adb scan-tree-dump-times optimized "MEM" 1

Hopefully all require only adjusting the testcase somehow, but it's
still something I need to look at tomorrow.  The patch can then be
incrementally improved to also work with one-element arrays which are
however indexed with an SSA_NAME.

As far as alias oracle statistics are concerned, the patch (on top of
r271763) improves from:

Alias oracle query stats:
  refs_may_alias_p: 3792598 disambiguations, 4181030 queries
  ref_maybe_used_by_call_p: 8291 disambiguations, 3829922 queries
  call_may_clobber_ref_p: 1092 disambiguations, 1092 queries
  aliasing_component_ref_p: 192 disambiguations, 18684 queries
  TBAA oracle: 1820750 disambiguations 3584527 queries
               778806 are in alias set 0
               723538 queries asked about the same object
               0 queries asked about the same alias set
               0 access volatile
               261267 are dependent in the DAG
               166 are aritificially in conflict with void *

to:

Alias oracle query stats:
  refs_may_alias_p: 3786679 disambiguations, 4174429 queries
  ref_maybe_used_by_call_p: 8285 disambiguations, 3824058 queries
  call_may_clobber_ref_p: 1092 disambiguations, 1092 queries
  aliasing_component_ref_p: 362 disambiguations, 19215 queries
  TBAA oracle: 1822975 disambiguations 3579314 queries
               775069 are in alias set 0
               727061 queries asked about the same object
               0 queries asked about the same alias set
               0 access volatile
               254043 are dependent in the DAG
               166 are aritificially in conflict with void *


Martin


Subject: [PATCH] Make SRA re-construct orginal memory accesses when easy

2019-05-30  Martin Jambor  <mjambor@suse.cz>

	* tree-sra.c (struct access): New field grp_same_access_path.
	(dump_access): Dump it.
	(build_reconstructed_reference): New function.
	(build_ref_for_model): Use it if possible.
	(path_comparable_for_same_access): New function.
	(same_access_path_p): Likewise.
	(sort_and_splice_var_accesses): Set the new flag.
	(analyze_access_subtree): Likewise.
	(propagate_subaccesses_across_link): Propagate zero value of the new
	flag down the access tree.

	testsuite/
	* gcc.dg/tree-ssa/alias-access-path-1.c: Remove -fno-tree-sra option.
---
 .../gcc.dg/tree-ssa/alias-access-path-1.c     |   2 +-
 gcc/tree-sra.c                                | 197 +++++++++++++++++-
 2 files changed, 190 insertions(+), 9 deletions(-)

diff --git a/gcc/testsuite/gcc.dg/tree-ssa/alias-access-path-1.c b/gcc/testsuite/gcc.dg/tree-ssa/alias-access-path-1.c
index 264f72aff0a..ba90b56fe5c 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/alias-access-path-1.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/alias-access-path-1.c
@@ -1,5 +1,5 @@
 /* { dg-do compile } */
-/* { dg-options "-O2 -fdump-tree-fre3 -fno-tree-sra" } */
+/* { dg-options "-O2 -fdump-tree-fre3" } */
 struct foo
 {
   int val;
diff --git a/gcc/tree-sra.c b/gcc/tree-sra.c
index fd51a3d0323..dc2a776d66c 100644
--- a/gcc/tree-sra.c
+++ b/gcc/tree-sra.c
@@ -242,6 +242,10 @@ struct access
      access tree.  */
   unsigned grp_unscalarized_data : 1;
 
+  /* Set if all accesses in the group consist of the same chain of
+     COMPONENT_REFs and ARRAY_REFs.  */
+  unsigned grp_same_access_path : 1;
+
   /* Does this access and/or group contain a write access through a
      BIT_FIELD_REF?  */
   unsigned grp_partial_lhs : 1;
@@ -443,16 +447,18 @@ dump_access (FILE *f, struct access *access, bool grp)
 	     "grp_scalar_write = %d, grp_total_scalarization = %d, "
 	     "grp_hint = %d, grp_covered = %d, "
 	     "grp_unscalarizable_region = %d, grp_unscalarized_data = %d, "
-	     "grp_partial_lhs = %d, grp_to_be_replaced = %d, "
-	     "grp_to_be_debug_replaced = %d, grp_maybe_modified = %d, "
+	     "grp_same_access_path = %d, grp_partial_lhs = %d, "
+	     "grp_to_be_replaced = %d, grp_to_be_debug_replaced = %d, "
+	     "grp_maybe_modified = %d, "
 	     "grp_not_necessarilly_dereferenced = %d\n",
 	     access->grp_read, access->grp_write, access->grp_assignment_read,
 	     access->grp_assignment_write, access->grp_scalar_read,
 	     access->grp_scalar_write, access->grp_total_scalarization,
 	     access->grp_hint, access->grp_covered,
 	     access->grp_unscalarizable_region, access->grp_unscalarized_data,
-	     access->grp_partial_lhs, access->grp_to_be_replaced,
-	     access->grp_to_be_debug_replaced, access->grp_maybe_modified,
+	     access->grp_same_access_path, access->grp_partial_lhs,
+	     access->grp_to_be_replaced, access->grp_to_be_debug_replaced,
+	     access->grp_maybe_modified,
 	     access->grp_not_necessarilly_dereferenced);
   else
     fprintf (f, ", write = %d, grp_total_scalarization = %d, "
@@ -1795,6 +1801,41 @@ build_ref_for_offset (location_t loc, tree base, poly_int64 offset,
   return mem_ref;
 }
 
+/* Construct and return a memory reference that is equal to a portion of
+   MODEL->expr but is based on BASE.  If this cannot be done, return NULL.  */
+
+static tree
+build_reconstructed_reference (location_t loc, tree base, struct access *model)
+{
+  auto_vec <tree, 8> model_comps;
+  tree expr = model->expr;
+  while (!types_compatible_p (TREE_TYPE (expr), TREE_TYPE (base)))
+    {
+      if (TREE_CODE (expr) != COMPONENT_REF
+	  && TREE_CODE (expr) != ARRAY_REF)
+	return NULL;
+      model_comps.safe_push (expr);
+      expr = TREE_OPERAND (expr, 0);
+    }
+
+  tree ref = unshare_expr (base);
+  while (!model_comps.is_empty ())
+    {
+      tree t = model_comps.pop ();
+      if (TREE_CODE (t) == COMPONENT_REF)
+	ref = build3_loc (loc, COMPONENT_REF, TREE_TYPE (t), ref,
+			  TREE_OPERAND (t, 1), TREE_OPERAND (t, 2));
+      else if (TREE_CODE (t) == ARRAY_REF)
+	ref = build4_loc (loc, ARRAY_REF, TREE_TYPE (t), ref,
+			  TREE_OPERAND (t, 1), TREE_OPERAND (t, 2),
+			  TREE_OPERAND (t, 3));
+      else
+	gcc_unreachable ();
+    }
+
+  return ref;
+}
+
 /* Construct a memory reference to a part of an aggregate BASE at the given
    OFFSET and of the same type as MODEL.  In case this is a reference to a
    bit-field, the function will replicate the last component_ref of model's
@@ -1822,9 +1863,19 @@ build_ref_for_model (location_t loc, tree base, HOST_WIDE_INT offset,
 			      NULL_TREE);
     }
   else
-    return
-      build_ref_for_offset (loc, base, offset, model->reverse, model->type,
-			    gsi, insert_after);
+    {
+      tree res;
+      if (model->grp_same_access_path
+	  && offset <= model->offset
+	  && get_object_alignment (base) >= TYPE_ALIGN (TREE_TYPE (base))
+	  /* build_reconstructed_reference can still fail if we have already
+	     massaged BASE because of another type incompatibility.  */
+	  && (res = build_reconstructed_reference (loc, base, model)))
+	return res;
+      else
+	return build_ref_for_offset (loc, base, offset, model->reverse,
+				     model->type, gsi, insert_after);
+    }
 }
 
 /* Attempt to build a memory reference that we could but into a gimple
@@ -2076,6 +2127,121 @@ find_var_candidates (void)
   return ret;
 }
 
+/* Return true if EXP is a reference chain of COMPONENT_REFs and AREAY_REFs
+   ending either with a DECL or a MEM_REF with zero offset.  */
+
+static bool
+path_comparable_for_same_access (tree expr)
+{
+  while (handled_component_p (expr))
+    {
+      if (TREE_CODE (expr) == ARRAY_REF)
+	{
+	  /* SSA name indices can occur here too when the array is of sie one.
+	     But we cannot just re-use array_refs with SSA names elsewhere in
+	     the function, so disallow non-constant indices.  TODO: Remove this
+	     limitation after teaching build_reconstructed_reference to replace
+	     the index with the index type lower bound.  */
+	  if (TREE_CODE (TREE_OPERAND (expr, 1)) != INTEGER_CST)
+	    return false;
+	}
+      else if (TREE_CODE (expr) != COMPONENT_REF)
+	return false;
+
+      expr = TREE_OPERAND (expr, 0);
+    }
+
+  if (TREE_CODE (expr) == MEM_REF)
+    {
+      if (!zerop (TREE_OPERAND (expr, 1)))
+	return false;
+    }
+  else
+    gcc_assert (DECL_P (expr));
+
+  return true;
+}
+
+/* Assuming that EXP1 consists of only COMPONENT_REFs and ARRAY_REFs, return
+   true if the chain of these handled components are exactly the same as EXP2
+   and the expression under them is the same DECL or an equivalent MEM_REF.
+   The reference picked by compare_access_positions must go to EXP1.  */
+
+static bool
+same_access_path_p (tree exp1, tree exp2)
+{
+  while (handled_component_p (exp1))
+    {
+      if (TREE_CODE (exp1) != TREE_CODE (exp2))
+	{
+	  /* Special case single-field structures loaded sometimes as the field
+	     and sometimes as the structure.  If the field is of a scalar type,
+	     compare_access_positions will put it into exp1.
+
+	     TODO: The gimple register type condition can be removed if teach
+	     compare_access_positions to put inner types first.  */
+	  if (is_gimple_reg_type (TREE_TYPE (exp1))
+	      && TREE_CODE (exp1) == COMPONENT_REF
+	      && (TYPE_MAIN_VARIANT (TREE_TYPE (TREE_OPERAND (exp1, 0)))
+		  == TYPE_MAIN_VARIANT (TREE_TYPE (exp2))))
+	    {
+	      exp1 = TREE_OPERAND (exp1, 0);
+	      continue;
+	    }
+	  return false;
+	}
+
+      if (TREE_CODE (exp1) == COMPONENT_REF)
+	{
+	  if (TREE_OPERAND (exp1, 1) != TREE_OPERAND (exp2, 1)
+	      || !tree_int_cst_equal (TREE_OPERAND (exp1, 2),
+				      TREE_OPERAND (exp2, 2)))
+	    return false;
+	}
+      else if (TREE_CODE (exp1) == ARRAY_REF)
+	{
+	  if (!tree_int_cst_equal (TREE_OPERAND (exp1, 1),
+				   TREE_OPERAND (exp2, 1))
+	      || !tree_int_cst_equal (array_ref_low_bound (exp1),
+				      array_ref_low_bound (exp2))
+	      || !tree_int_cst_equal (array_ref_element_size (exp1),
+				      array_ref_element_size (exp2)))
+	    return false;
+	}
+      else
+	gcc_unreachable ();
+
+      exp1 = TREE_OPERAND (exp1, 0);
+      exp2 = TREE_OPERAND (exp2, 0);
+    }
+
+  if (TREE_CODE (exp1) != TREE_CODE (exp2))
+    return false;
+
+  if (DECL_P (exp1))
+    {
+      gcc_assert (exp1 == exp2);
+      return true;
+    }
+  else if (TREE_CODE (exp1) == MEM_REF)
+    {
+      gcc_assert (TREE_CODE (TREE_OPERAND (exp1, 0)) == ADDR_EXPR
+		  && TREE_CODE (TREE_OPERAND (exp2, 0)) == ADDR_EXPR
+		  && DECL_P (TREE_OPERAND (TREE_OPERAND (exp1, 0), 0))
+		  && (TREE_OPERAND (TREE_OPERAND (exp1, 0), 0)
+		      == TREE_OPERAND (TREE_OPERAND (exp1, 0), 0))
+		  && tree_int_cst_equal (TREE_OPERAND (exp1, 1),
+					 TREE_OPERAND (exp2, 1)));
+
+      return ((TYPE_MAIN_VARIANT (TREE_TYPE (exp1))
+	       == TYPE_MAIN_VARIANT (TREE_TYPE (exp2)))
+	      && (TYPE_MAIN_VARIANT (reference_alias_ptr_type (exp1))
+		  == TYPE_MAIN_VARIANT (reference_alias_ptr_type (exp2))));
+    }
+  else
+    return false;
+}
+
 /* Sort all accesses for the given variable, check for partial overlaps and
    return NULL if there are any.  If there are none, pick a representative for
    each combination of offset and size and create a linked list out of them.
@@ -2116,6 +2282,7 @@ sort_and_splice_var_accesses (tree var)
       bool grp_partial_lhs = access->grp_partial_lhs;
       bool first_scalar = is_gimple_reg_type (access->type);
       bool unscalarizable_region = access->grp_unscalarizable_region;
+      bool grp_same_access_path = true;
       bool bf_non_full_precision
 	= (INTEGRAL_TYPE_P (access->type)
 	   && TYPE_PRECISION (access->type) != access->size
@@ -2134,6 +2301,8 @@ sort_and_splice_var_accesses (tree var)
 	gcc_assert (access->offset >= low
 		    && access->offset + access->size <= high);
 
+      grp_same_access_path = path_comparable_for_same_access (access->expr);
+
       j = i + 1;
       while (j < access_count)
 	{
@@ -2184,6 +2353,11 @@ sort_and_splice_var_accesses (tree var)
 		}
 	      unscalarizable_region = true;
 	    }
+
+	  if (grp_same_access_path
+	      && !same_access_path_p (access->expr, ac2->expr))
+	    grp_same_access_path = false;
+
 	  ac2->group_representative = access;
 	  j++;
 	}
@@ -2202,6 +2376,7 @@ sort_and_splice_var_accesses (tree var)
       access->grp_total_scalarization = total_scalarization;
       access->grp_partial_lhs = grp_partial_lhs;
       access->grp_unscalarizable_region = unscalarizable_region;
+      access->grp_same_access_path = grp_same_access_path;
 
       *prev_acc_ptr = access;
       prev_acc_ptr = &access->next_grp;
@@ -2471,6 +2646,8 @@ analyze_access_subtree (struct access *root, struct access *parent,
 	root->grp_assignment_write = 1;
       if (parent->grp_total_scalarization)
 	root->grp_total_scalarization = 1;
+      if (!parent->grp_same_access_path)
+	root->grp_same_access_path = 0;
     }
 
   if (root->grp_unscalarizable_region)
@@ -2721,13 +2898,17 @@ propagate_subaccesses_across_link (struct access *lacc, struct access *racc)
 	  lacc->type = racc->type;
 	  if (build_user_friendly_ref_for_offset (&t, TREE_TYPE (t),
 						  lacc->offset, racc->type))
-	    lacc->expr = t;
+	    {
+	      lacc->expr = t;
+	      lacc->grp_same_access_path = true;
+	    }
 	  else
 	    {
 	      lacc->expr = build_ref_for_model (EXPR_LOCATION (lacc->base),
 						lacc->base, lacc->offset,
 						racc, NULL, false);
 	      lacc->grp_no_warning = true;
+	      lacc->grp_same_access_path = false;
 	    }
 	}
       return ret;
-- 
2.21.0