This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[PATCH][alias-improvements] More type-based disambiguation
- From: Richard Guenther <rguenther at suse dot de>
- To: gcc-patches at gcc dot gnu dot org
- Date: Sat, 17 Jan 2009 17:00:57 +0100 (CET)
- Subject: [PATCH][alias-improvements] More type-based disambiguation
This fixes type-based disambiguation to also consider canonical types
and eventual structual comparisons. I believe this allows us to enable
a positive fallback for disjunct access paths. It fixes the long-standing
PR13146 and a deficiency compared to RTL alias analysis (PR38895), but
without the cost of a quadratic loop.
Bootstrapped and tested on x86_64-unknown-linux-gnu, applied to the
branch.
Richard.
2009-01-17 Richard Guenther <rguenther@suse.de>
PR middle-end/13146
PR tree-optimization/38895
* tree-ssa-alias.c (same_type_for_tbaa): New helper function.
(refs_may_alias_p): Use it. Extend access path based disambiguation.
* gcc.dg/tree-ssa/pr13146.c: New testcase.
* gcc.dg/tree-ssa/pr38895.c: Likewise.
* g++.dg/tree-ssa/pr13146.C: Likewise.
Index: gcc/testsuite/gcc.dg/tree-ssa/pr13146.c
===================================================================
*** /dev/null 1970-01-01 00:00:00.000000000 +0000
--- gcc/testsuite/gcc.dg/tree-ssa/pr13146.c 2009-01-17 16:50:58.000000000 +0100
***************
*** 0 ****
--- 1,22 ----
+ /* { dg-do compile } */
+ /* { dg-options "-O -fstrict-aliasing -fdump-tree-optimized" } */
+
+ struct A
+ {
+ int i;
+ };
+ struct B
+ {
+ struct A a;
+ int j;
+ };
+
+ int foo (struct A *p, struct B *q)
+ {
+ p->i = 0;
+ q->j = 1;
+ return p->i;
+ }
+
+ /* { dg-final { scan-tree-dump "return 0;" "optimized" } } */
+ /* { dg-final { cleanup-tree-dump "optimized" } } */
Index: gcc/testsuite/gcc.dg/tree-ssa/pr38895.c
===================================================================
*** /dev/null 1970-01-01 00:00:00.000000000 +0000
--- gcc/testsuite/gcc.dg/tree-ssa/pr38895.c 2009-01-17 16:50:58.000000000 +0100
***************
*** 0 ****
--- 1,24 ----
+ /* { dg-do compile } */
+ /* { dg-options "-O -fstrict-aliasing -fdump-tree-optimized" } */
+
+ struct A {
+ int i;
+ int j;
+ };
+ struct B {
+ struct A a1;
+ struct A a2;
+ };
+ struct C {
+ struct A a1;
+ struct B b;
+ };
+ int foo(struct C *c, struct B *b)
+ {
+ c->a1.i = 1;
+ b->a1.j = 0;
+ return c->a1.i;
+ }
+
+ /* { dg-final { scan-tree-dump "return 1;" "optimized" } } */
+ /* { dg-final { cleanup-tree-dump "optimized" } } */
Index: gcc/tree-ssa-alias.c
===================================================================
*** gcc/tree-ssa-alias.c.orig 2009-01-17 16:50:25.000000000 +0100
--- gcc/tree-ssa-alias.c 2009-01-17 16:50:58.000000000 +0100
*************** debug_points_to_info_for (tree var)
*** 357,362 ****
--- 357,380 ----
dump_points_to_info_for (stderr, var);
}
+ /* Return 1 if TYPE1 and TYPE2 are to be considered equivalent for the
+ purpose of TBAA. Return 0 if they are distinct and -1 if we cannot
+ decide. */
+
+ static inline int
+ same_type_for_tbaa (tree type1, tree type2)
+ {
+ type1 = TYPE_MAIN_VARIANT (type1);
+ type2 = TYPE_MAIN_VARIANT (type2);
+
+ /* If we would have to do structural comparison bail out. */
+ if (TYPE_STRUCTURAL_EQUALITY_P (type1)
+ || TYPE_STRUCTURAL_EQUALITY_P (type2))
+ return -1;
+
+ /* Compare the canonical types. */
+ return (TYPE_CANONICAL (type1) == TYPE_CANONICAL (type2)) ? 1 : 0;
+ }
/* Return true, if the two memory references REF1 and REF2 may alias. */
*************** refs_may_alias_p (tree ref1, tree ref2)
*** 468,475 ****
/* If both references are through the same type, they do not alias
if the accesses do not overlap. This does extra disambiguation
for mixed/pointer accesses but requires strict aliasing. */
! if (TYPE_MAIN_VARIANT (TREE_TYPE (base1))
! == TYPE_MAIN_VARIANT (TREE_TYPE (base2)))
return ranges_overlap_p (offset1, max_size1, offset2, max_size2);
/* The only way to access a variable is through a pointer dereference
--- 486,492 ----
/* If both references are through the same type, they do not alias
if the accesses do not overlap. This does extra disambiguation
for mixed/pointer accesses but requires strict aliasing. */
! if (same_type_for_tbaa (TREE_TYPE (base1), TREE_TYPE (base2)) == 1)
return ranges_overlap_p (offset1, max_size1, offset2, max_size2);
/* The only way to access a variable is through a pointer dereference
*************** refs_may_alias_p (tree ref1, tree ref2)
*** 500,536 ****
&& handled_component_p (ref2))
{
tree *refp;
/* Now search for the type of base1 in the access path of ref2. This
would be a common base for doing offset based disambiguation on. */
refp = &ref2;
while (handled_component_p (*refp)
! /* Note that the following is only conservative if there are
! never copies of types appearing as sub-structures. */
! && (TYPE_MAIN_VARIANT (TREE_TYPE (*refp))
! != TYPE_MAIN_VARIANT (TREE_TYPE (base1))))
refp = &TREE_OPERAND (*refp, 0);
! if (TYPE_MAIN_VARIANT (TREE_TYPE (*refp))
! == TYPE_MAIN_VARIANT (TREE_TYPE (base1)))
{
HOST_WIDE_INT offadj, sztmp, msztmp;
get_ref_base_and_extent (*refp, &offadj, &sztmp, &msztmp);
offset2 -= offadj;
return ranges_overlap_p (offset1, max_size1, offset2, max_size2);
}
! /* The other way around. */
refp = &ref1;
while (handled_component_p (*refp)
! && (TYPE_MAIN_VARIANT (TREE_TYPE (*refp))
! != TYPE_MAIN_VARIANT (TREE_TYPE (base2))))
refp = &TREE_OPERAND (*refp, 0);
! if (TYPE_MAIN_VARIANT (TREE_TYPE (*refp))
! == TYPE_MAIN_VARIANT (TREE_TYPE (base2)))
{
HOST_WIDE_INT offadj, sztmp, msztmp;
get_ref_base_and_extent (*refp, &offadj, &sztmp, &msztmp);
offset1 -= offadj;
return ranges_overlap_p (offset1, max_size1, offset2, max_size2);
}
}
return true;
--- 517,561 ----
&& handled_component_p (ref2))
{
tree *refp;
+ int same_p;
/* Now search for the type of base1 in the access path of ref2. This
would be a common base for doing offset based disambiguation on. */
refp = &ref2;
while (handled_component_p (*refp)
! && same_type_for_tbaa (TREE_TYPE (*refp),
! TREE_TYPE (base1)) == 0)
refp = &TREE_OPERAND (*refp, 0);
! same_p = same_type_for_tbaa (TREE_TYPE (*refp), TREE_TYPE (base1));
! /* If we couldn't compare types we have to bail out. */
! if (same_p == -1)
! return true;
! else if (same_p == 1)
{
HOST_WIDE_INT offadj, sztmp, msztmp;
get_ref_base_and_extent (*refp, &offadj, &sztmp, &msztmp);
offset2 -= offadj;
return ranges_overlap_p (offset1, max_size1, offset2, max_size2);
}
! /* If we didn't find a common base, try the other way around. */
refp = &ref1;
while (handled_component_p (*refp)
! && same_type_for_tbaa (TREE_TYPE (*refp),
! TREE_TYPE (base2)) == 0)
refp = &TREE_OPERAND (*refp, 0);
! same_p = same_type_for_tbaa (TREE_TYPE (*refp), TREE_TYPE (base2));
! /* If we couldn't compare types we have to bail out. */
! if (same_p == -1)
! return true;
! else if (same_p == 1)
{
HOST_WIDE_INT offadj, sztmp, msztmp;
get_ref_base_and_extent (*refp, &offadj, &sztmp, &msztmp);
offset1 -= offadj;
return ranges_overlap_p (offset1, max_size1, offset2, max_size2);
}
+ /* If we have two type access paths B1.path1 and B2.path2 they may
+ only alias if either B1 is in B2.path2 or B2 is in B1.path1. */
+ return false;
}
return true;
Index: gcc/testsuite/g++.dg/tree-ssa/pr13146.C
===================================================================
*** /dev/null 1970-01-01 00:00:00.000000000 +0000
--- gcc/testsuite/g++.dg/tree-ssa/pr13146.C 2009-01-17 16:51:53.000000000 +0100
***************
*** 0 ****
--- 1,74 ----
+ /* { dg-do link } */
+ /* { dg-options "-O -fstrict-aliasing" } */
+
+ class first
+ {
+ public:
+ double d;
+ int f1;
+ };
+
+ class middle : public first
+ {
+ };
+
+ class second : public middle
+ {
+ public:
+ int f2;
+ short a;
+ };
+
+ class third
+ {
+ public:
+ char a;
+ char b;
+ };
+
+ class multi: public third, public second
+ {
+ public:
+ short s;
+ char f3;
+ };
+
+ extern void link_error ();
+
+ void
+ foo (first *s1, second *s2)
+ {
+ s1->f1 = 0;
+ s2->f2 = 0;
+ s1->f1++;
+ s2->f2++;
+ s1->f1++;
+ s2->f2++;
+ if (s1->f1 != 2)
+ link_error ();
+ }
+
+ void
+ bar (first *s1, multi *s3)
+ {
+ s1->f1 = 0;
+ s3->f3 = 0;
+ s1->f1++;
+ s3->f3++;
+ s1->f1++;
+ s3->f3++;
+ if (s1->f1 != 2)
+ link_error ();
+ }
+
+
+ int
+ main()
+ {
+ first a;
+ second b;
+ multi c;
+ foo (&a, &b);
+ bar (&a, &c);
+ return 0;
+ }