This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Enable nonoverallping_component_refs even after the base pointers are equivalent


Hi,
this patch adds the shortcut for must aliases discussed earlier and enables
access path even if bases are proved to be equivalent - it could still do
useful job for arrays etc.

tramp3d stats go from:

Alias oracle query stats:
  refs_may_alias_p: 4421560 disambiguations, 4781790 queries
  ref_maybe_used_by_call_p: 6790 disambiguations, 4447962 queries
  call_may_clobber_ref_p: 883 disambiguations, 883 queries
  nonoverlapping_component_refs_p: 0 disambiguations, 9272 queries
  nonoverlapping_component_refs_since_match_p: 31 disambiguations, 39391 queries
  aliasing_component_refs_p: 918 disambiguations, 30889 queries
  TBAA oracle: 1924468 disambiguations 3851145 queries
               774336 are in alias set 0
               714019 queries asked about the same object
               0 queries asked about the same alias set
               0 access volatile
               282546 are dependent in the DAG
               155776 are aritificially in conflict with void *

to

Alias oracle query stats:
  refs_may_alias_p: 4421611 disambiguations, 4781828 queries
  ref_maybe_used_by_call_p: 6790 disambiguations, 4448013 queries
  call_may_clobber_ref_p: 883 disambiguations, 883 queries
  nonoverlapping_component_refs_p: 0 disambiguations, 8964 queries
  nonoverlapping_component_refs_since_match_p: 66 disambiguations, 18470 queries
  aliasing_component_refs_p: 918 disambiguations, 30371 queries
  TBAA oracle: 1924492 disambiguations 3849967 queries
               774336 are in alias set 0
               714095 queries asked about the same object
               0 queries asked about the same alias set
               0 access volatile
               281268 are dependent in the DAG
               155776 are aritificially in conflict with void *

PTA query stats:
  pt_solution_includes: 906632 disambiguations, 1214744 queries
  pt_solutions_intersect: 121330 disambiguations, 553172 queries

So twice as many nonoverlapping_component_refs_since_match_p disambiguations,
half of querries.

We can miss some of disambiguations where addresses are same but types
are different, but I think those are not useful - this is the case where
memory type was dynamically changed.  If we walk with TBAA enabled and
see the prevoius use, we got kind of lost anyway and propagating even
older values seems to have no use.

Note that i tried to implement ranges_must_overlap_p predicate which could
save us from more tests but got lost in polyints and I think it is not worth
the effort since these cases are quite borderline.

Similar test would make sense in aliasing_component_refs_p but I think
it may make more sense to reorder the tests there. Right now we do:

  get_ref_base_and_extent (match2, &offadj, &sztmp, &msztmp, &reverse);
  offset2 -= offadj;
  get_ref_base_and_extent (match1, &offadj, &sztmp, &msztmp, &reverse);
  offset1 -= offadj;
  if (!ranges_maybe_overlap_p (offset1, max_size1, offset2, max_size2))

First I think that one get_ref_base_and_extent is always redundant since either
match1 or match2 is base so we could pass it down.

However it seems to me that perhaps doing
nonoverlapping_component_refs_since_match_p would be cheaper and one can do the
range check only after this one returns -1 saving quite many
get_ref_base_and_extent calls.

Bootstrapped/regtested x86_64-linux, OK?

Honza

Index: testsuite/gcc.dg/tree-ssa/alias-access-path-3.c
===================================================================
--- testsuite/gcc.dg/tree-ssa/alias-access-path-3.c	(nonexistent)
+++ testsuite/gcc.dg/tree-ssa/alias-access-path-3.c	(working copy)
@@ -0,0 +1,22 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-fre1" } */
+struct a {int v1;
+	  int v2;};
+struct b {struct a a[0];};
+
+int
+test (struct b *bptr1, struct b *bptr2, int i, int j)
+{
+  bptr1->a[i].v1=123;
+  bptr2->a[j].v2=1;
+  return bptr1->a[i].v1;
+}
+int
+test2 (struct b *bptr1, struct b *bptr2, int i, int j)
+{
+  bptr1->a[i].v1=123;
+  bptr2->a[j].v1=1;
+  return bptr1->a[i].v1;
+}
+/* test should be optimized, while test2 should not.  */
+/* { dg-final { scan-tree-dump-times "return 123" 1 "fre1"} } */
Index: testsuite/gcc.dg/tree-ssa/alias-access-path-8.c
===================================================================
--- testsuite/gcc.dg/tree-ssa/alias-access-path-8.c	(nonexistent)
+++ testsuite/gcc.dg/tree-ssa/alias-access-path-8.c	(working copy)
@@ -0,0 +1,21 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-fre3" } */
+struct a {
+  int val;
+};
+struct b {
+  struct a a[10],a2[10];
+};
+struct c {
+  struct b b[10];
+} *cptr,*cptr2;
+
+
+int
+test (int i, int j, int k, int l)
+{
+  cptr->b[i].a[j].val=123;
+  cptr2->b[k].a2[l].val=2;
+  return cptr->b[i].a[j].val;
+}
+/* { dg-final { scan-tree-dump-times "return 123" 1 "fre3"} } */
Index: tree-ssa-alias.c
===================================================================
--- tree-ssa-alias.c	(revision 272927)
+++ tree-ssa-alias.c	(working copy)
@@ -1452,8 +1452,10 @@ nonoverlapping_component_refs_p (const_t
 static bool
 decl_refs_may_alias_p (tree ref1, tree base1,
 		       poly_int64 offset1, poly_int64 max_size1,
+		       poly_int64 size1,
 		       tree ref2, tree base2,
-		       poly_int64 offset2, poly_int64 max_size2)
+		       poly_int64 offset2, poly_int64 max_size2,
+		       poly_int64 size2)
 {
   gcc_checking_assert (DECL_P (base1) && DECL_P (base2));
 
@@ -1466,6 +1468,10 @@ decl_refs_may_alias_p (tree ref1, tree b
   if (!ranges_maybe_overlap_p (offset1, max_size1, offset2, max_size2))
     return false;
 
+  /* If there is must alias, there is no use disambiguating further.  */
+  if (known_eq (size1, max_size1) && known_eq (size2, max_size2))
+    return true;
+
   /* For components with variable position, the above test isn't sufficient,
      so we disambiguate component references manually.  */
   if (ref1 && ref2
@@ -1487,10 +1493,12 @@ decl_refs_may_alias_p (tree ref1, tree b
 static bool
 indirect_ref_may_alias_decl_p (tree ref1 ATTRIBUTE_UNUSED, tree base1,
 			       poly_int64 offset1, poly_int64 max_size1,
+			       poly_int64 size1,
 			       alias_set_type ref1_alias_set,
 			       alias_set_type base1_alias_set,
 			       tree ref2 ATTRIBUTE_UNUSED, tree base2,
 			       poly_int64 offset2, poly_int64 max_size2,
+			       poly_int64 size2,
 			       alias_set_type ref2_alias_set,
 			       alias_set_type base2_alias_set, bool tbaa_p)
 {
@@ -1598,7 +1606,19 @@ indirect_ref_may_alias_decl_p (tree ref1
       && (TREE_CODE (TREE_TYPE (base1)) != ARRAY_TYPE
 	  || (TYPE_SIZE (TREE_TYPE (base1))
 	      && TREE_CODE (TYPE_SIZE (TREE_TYPE (base1))) == INTEGER_CST)))
-    return ranges_maybe_overlap_p (doffset1, max_size1, doffset2, max_size2);
+    {
+      if (!ranges_maybe_overlap_p (doffset1, max_size1, doffset2, max_size2))
+	return false;
+      if (!ref1 || !ref2
+	  /* If there is must alias, there is no use disambiguating further.  */
+	  || (known_eq (size1, max_size1) && known_eq (size2, max_size2)))
+	return true;
+      int res = nonoverlapping_component_refs_since_match_p (base1, ref1,
+							     base2, ref2);
+      if (res == -1)
+	return !nonoverlapping_component_refs_p (ref1, ref2);
+      return !res;
+    }
 
   /* Do access-path based disambiguation.  */
   if (ref1 && ref2
@@ -1623,10 +1643,12 @@ indirect_ref_may_alias_decl_p (tree ref1
 static bool
 indirect_refs_may_alias_p (tree ref1 ATTRIBUTE_UNUSED, tree base1,
 			   poly_int64 offset1, poly_int64 max_size1,
+			   poly_int64 size1,
 			   alias_set_type ref1_alias_set,
 			   alias_set_type base1_alias_set,
 			   tree ref2 ATTRIBUTE_UNUSED, tree base2,
 			   poly_int64 offset2, poly_int64 max_size2,
+			   poly_int64 size2,
 			   alias_set_type ref2_alias_set,
 			   alias_set_type base2_alias_set, bool tbaa_p)
 {
@@ -1671,6 +1693,9 @@ indirect_refs_may_alias_p (tree ref1 ATT
       if (!ranges_maybe_overlap_p (offset1 + moff1, max_size1,
 				   offset2 + moff2, max_size2))
 	return false;
+      /* If there is must alias, there is no use disambiguating further.  */
+      if (known_eq (size1, max_size1) && known_eq (size2, max_size2))
+	return true;
       if (ref1 && ref2)
 	{
 	  int res = nonoverlapping_component_refs_since_match_p (NULL, ref1,
@@ -1717,7 +1742,18 @@ indirect_refs_may_alias_p (tree ref1 ATT
          can overlap by an exact multiple of their element size.
          See gcc.dg/torture/alias-2.c.  */
       && TREE_CODE (TREE_TYPE (ptrtype1)) != ARRAY_TYPE)
-    return ranges_maybe_overlap_p (offset1, max_size1, offset2, max_size2);
+    {
+      if (!ranges_maybe_overlap_p (offset1, max_size1, offset2, max_size2))
+	return false;
+      if (!ref1 || !ref2
+	  || (known_eq (size1, max_size1) && known_eq (size2, max_size2)))
+	return true;
+      int res = nonoverlapping_component_refs_since_match_p (base1, ref1,
+							     base2, ref2);
+      if (res == -1)
+	return !nonoverlapping_component_refs_p (ref1, ref2);
+      return !res;
+    }
 
   /* Do access-path based disambiguation.  */
   if (ref1 && ref2
@@ -1802,7 +1838,9 @@ refs_may_alias_p_2 (ao_ref *ref1, ao_ref
   var2_p = DECL_P (base2);
   if (var1_p && var2_p)
     return decl_refs_may_alias_p (ref1->ref, base1, offset1, max_size1,
-				  ref2->ref, base2, offset2, max_size2);
+				  ref1->size,
+				  ref2->ref, base2, offset2, max_size2,
+				  ref2->size);
 
   /* Handle restrict based accesses.
      ???  ao_ref_base strips inner MEM_REF [&decl], recover from that
@@ -1870,21 +1908,21 @@ refs_may_alias_p_2 (ao_ref *ref1, ao_ref
   /* Dispatch to the pointer-vs-decl or pointer-vs-pointer disambiguators.  */
   if (var1_p && ind2_p)
     return indirect_ref_may_alias_decl_p (ref2->ref, base2,
-					  offset2, max_size2,
+					  offset2, max_size2, ref2->size,
 					  ao_ref_alias_set (ref2),
 					  ao_ref_base_alias_set (ref2),
 					  ref1->ref, base1,
-					  offset1, max_size1,
+					  offset1, max_size1, ref1->size,
 					  ao_ref_alias_set (ref1),
 					  ao_ref_base_alias_set (ref1),
 					  tbaa_p);
   else if (ind1_p && ind2_p)
     return indirect_refs_may_alias_p (ref1->ref, base1,
-				      offset1, max_size1,
+				      offset1, max_size1, ref1->size,
 				      ao_ref_alias_set (ref1),
 				      ao_ref_base_alias_set (ref1),
 				      ref2->ref, base2,
-				      offset2, max_size2,
+				      offset2, max_size2, ref2->size,
 				      ao_ref_alias_set (ref2),
 				      ao_ref_base_alias_set (ref2),
 				      tbaa_p);


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]