> On Fri, 17 May 2019, Jan Hubicka wrote:
>
> > Hi,
> > this patch cuts walks in aliasing_component_refs_p if the type we look for
> > can not fit into a given type by comparing their sizes. Similar logic
> > already exists in indirect_ref_may_alias_decl_p.
> >
> > When we walk reference a.b.c.d.e looking for type x we only need to do
> > it if sizeof(a)>=sizeof(x) and continue woking from e until
> > sizeof(e)<=sizeof(x). We do not need to compare types where sizes are
> > known to be different.
> >
> > This saves some work (by not walking refs and not comparing their types
> > if they can not match) but also increases number of disambiguations
> > quite noticably. This is because same_type_for_tbaa often returns -1 and
> > makes aliasing_compinent_refs_p to give up. Using the simple size check
> > prevents hitting such problematic type pairs in many common cases.
> >
> > Stats on tramp3d lto build change From:
> >
> > Alias oracle query stats:
> > refs_may_alias_p: 0 disambiguations, 0 queries
> > ref_maybe_used_by_call_p: 6451 disambiguations, 25578 queries
> > call_may_clobber_ref_p: 817 disambiguations, 817 queries
> > aliasing_component_ref_p: 14 disambiguations, 12528 queries
> > TBAA oracle: 1468347 disambiguations 3010562 queries
> > 550690 are in alias set 0
> > 614235 queries asked about the same object
> > 0 queries asked about the same alias set
> > 0 access volatile
> > 260937 are dependent in the DAG
> > 116353 are aritificially in conflict with void *
> >
> > to:
> >
> > Alias oracle query stats:
> > refs_may_alias_p: 0 disambiguations, 0 queries
> > ref_maybe_used_by_call_p: 6451 disambiguations, 25580 queries
> > call_may_clobber_ref_p: 817 disambiguations, 817 queries
> > aliasing_component_ref_p: 118 disambiguations, 12552 queries
> > TBAA oracle: 1468413 disambiguations 3010714 queries
> > 550719 are in alias set 0
> > 614247 queries asked about the same object
> > 0 queries asked about the same alias set
> > 0 access volatile
> > 260970 are dependent in the DAG
> > 116365 are aritificially in conflict with void *
> >
> > So disambiguations are up from 14 to 118 which is still quite low.
> >
> > A followup patch making types_same_for_tbaa to not give up for
> > TYPE_STRUCTURAL_EQUALITY pointers and arrays improves hitrate to 2723.
> >
> > Bootstrapped/regtested x86_64-linux, OK?
> >
> > * tree-ssa-alias.c (type_big_enough_for_type_p): New function.
> > (aliasing_component_refs_p): Use it.
> > Index: tree-ssa-alias.c
> > ===================================================================
> > --- tree-ssa-alias.c (revision 271292)
> > +++ tree-ssa-alias.c (working copy)
> > @@ -735,6 +735,27 @@ ao_ref_init_from_ptr_and_size (ao_ref *r
> > ref->volatile_p = false;
> > }
> >
> > +/* Return true if TYPE1 may contain TYPE2 by its size. */
> > +
> > +static bool
> > +type_big_enough_for_type_p (tree type1, tree type2)
> > +{
> > + if (!TYPE_SIZE (type1) || !TYPE_SIZE (type2))
> > + return true;
> > + /* Be conservative for arrays and vectors. We want to support partial
> > + overlap on int[3] and int[3] as tested in gcc.dg/torture/alias-2.c.
> > */
> > + while (TREE_CODE (type2) == ARRAY_TYPE
> > + || TREE_CODE (type2) == VECTOR_TYPE)
> > + type2 = TREE_TYPE (type2);
>
> Eww ;) I guess this means same-type can never return true for
> array or vectors?
>
> > + if (!poly_int_tree_p (TYPE_SIZE (type1))
> > + || !poly_int_tree_p (TYPE_SIZE (type2)))
> > + return true;
>
> Use
>
> poly_uint64 size1;
> if (!poly_int_tree_p (TYPE_SIZE (type1), &size1)
> ...
>
> > + if (known_lt (wi::to_poly_widest (TYPE_SIZE (type1)),
> > + wi::to_poly_widest (TYPE_SIZE (type2))))
>
> and
>
> if (known_lt (size1, size2))
>
> I wonder if you can compute whether type1 fits in type2 and
> the other way around at the same time, saving seemingly
> redundant work since you test both ways most of the time below.
> So sth like type_size_compare_for_fitting () returning
> -1, 0, 1 and use zero for "don't know"?
Hi,
this patch implements the three way compare and also merges the code
with same logic in indirect_ref_may_alias_decl_p.
We end up doing more known_lt calls than necessary because sometimes we
do not care about the three way outcome, but I asusme that this should
be relatively cheap once we pass the earlier test and tree to poly_int
conversion.
Bootstrapped/regtested x86_64-linux, OK?
* tree-ssa-alias.c (compare_sizes): New function.
(sompare_type_sizes): New function
(aliasing_component_refs_p): Use it.
(indirect_ref_may_alias_decl_p): Likewise.
Index: tree-ssa-alias.c
===================================================================
--- tree-ssa-alias.c (revision 271379)
+++ tree-ssa-alias.c (working copy)
@@ -735,6 +735,48 @@ ao_ref_init_from_ptr_and_size (ao_ref *r
ref->volatile_p = false;
}
+/* S1 and S2 are TYPE_SIZE or DECL_SIZE. Compare them:
+ Return -1 if S1 < S2
+ Return 1 if S1 > S2
+ Return 0 if equal or incoparable. */
+
+static int
+compare_sizes (tree s1, tree s2)
+{
+ if (!s1 || !s2)
+ return 0;
+
+ poly_uint64 size1 = poly_int_tree_p (s1, &size1);
+ poly_uint64 size2 = poly_int_tree_p (s2, &size2);
+
+ if (!poly_int_tree_p (s1, &size1) || !poly_int_tree_p (s2, &size2))
+ return 0;
+ if (known_lt (size1, size2))
+ return -1;
+ if (known_lt (size2, size1))
+ return 1;
+ return 0;
+}
+
+/* Compare TYPE1 and TYPE2 by its size.
+ Return -1 if size of TYPE1 < size of TYPE2
+ Return 1 if size of TYPE1 > size of TYPE2
+ Return 0 if types are of equal sizes or we can not compare them. */
+
+static int
+compare_type_sizes (tree type1, tree type2)
+{
+ /* Be conservative for arrays and vectors. We want to support partial
+ overlap on int[3] and int[3] as tested in gcc.dg/torture/alias-2.c. */
+ while (TREE_CODE (type1) == ARRAY_TYPE
+ || TREE_CODE (type1) == VECTOR_TYPE)
+ type1 = TREE_TYPE (type1);
+ while (TREE_CODE (type2) == ARRAY_TYPE
+ || TREE_CODE (type2) == VECTOR_TYPE)
+ type2 = TREE_TYPE (type2);
+ return compare_sizes (TYPE_SIZE (type1), TYPE_SIZE (type2));
+}
+
/* 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. */
@@ -803,7 +845,7 @@ aliasing_component_refs_p (tree ref1,
tree base1, base2;
tree type1, type2;
tree *refp;
- int same_p, same_p2;
+ int same_p1 = 0, same_p2 = 0;
/* Choose bases and base types to search for. */
base1 = ref1;
@@ -816,65 +858,93 @@ aliasing_component_refs_p (tree ref1,
type2 = TREE_TYPE (base2);
/* Now search for the type1 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), type1) == 0)
- refp = &TREE_OPERAND (*refp, 0);
- same_p = same_type_for_tbaa (TREE_TYPE (*refp), type1);
- if (same_p == 1)
- {
- poly_int64 offadj, sztmp, msztmp;
- bool reverse;
- get_ref_base_and_extent (*refp, &offadj, &sztmp, &msztmp, &reverse);
- offset2 -= offadj;
- get_ref_base_and_extent (base1, &offadj, &sztmp, &msztmp, &reverse);
- offset1 -= offadj;
- if (ranges_maybe_overlap_p (offset1, max_size1, offset2, max_size2))
+ would be a common base for doing offset based disambiguation on.
+ This however only makes sense if type2 is big enough to hold type1. */
+ int cmp_outer = compare_type_sizes (type2, type1);
+ if (cmp_outer >= 0)
+ {
+ refp = &ref2;
+ while (true)
{
- ++alias_stats.aliasing_component_refs_p_may_alias;
- return true;
+ /* We walk from inner type to the outer types. If type we see is
+ already too large to be part of type1, terminate the search. */
+ int cmp = compare_type_sizes (type1, TREE_TYPE (*refp));
+ if (cmp < 0)
+ break;
+ /* If types may be of same size, see if we can decide about their
+ equality. */
+ if (cmp >= 0)
+ {
+ same_p2 = same_type_for_tbaa (TREE_TYPE (*refp), type1);
+ if (same_p2 != 0)
+ break;
+ }
+ if (!handled_component_p (*refp))
+ break;
+ refp = &TREE_OPERAND (*refp, 0);
}
- else
+ if (same_p2 == 1)
{
- ++alias_stats.aliasing_component_refs_p_no_alias;
- return false;
+ poly_int64 offadj, sztmp, msztmp;
+ bool reverse;
+ get_ref_base_and_extent (*refp, &offadj, &sztmp, &msztmp, &reverse);
+ offset2 -= offadj;
+ get_ref_base_and_extent (base1, &offadj, &sztmp, &msztmp, &reverse);
+ offset1 -= offadj;
+ if (ranges_maybe_overlap_p (offset1, max_size1, offset2, max_size2))
+ {
+ ++alias_stats.aliasing_component_refs_p_may_alias;
+ return true;
+ }
+ else
+ {
+ ++alias_stats.aliasing_component_refs_p_no_alias;
+ return false;
+ }
}
}
/* 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), type2) == 0)
- refp = &TREE_OPERAND (*refp, 0);
- same_p2 = same_type_for_tbaa (TREE_TYPE (*refp), type2);
- if (same_p2 == 1)
- {
- poly_int64 offadj, sztmp, msztmp;
- bool reverse;
-
- get_ref_base_and_extent (*refp, &offadj, &sztmp, &msztmp, &reverse);
- offset1 -= offadj;
- get_ref_base_and_extent (base2, &offadj, &sztmp, &msztmp, &reverse);
- offset2 -= offadj;
- if (ranges_maybe_overlap_p (offset1, max_size1, offset2, max_size2))
+ if (cmp_outer <= 0)
+ {
+ refp = &ref1;
+ while (true)
{
- ++alias_stats.aliasing_component_refs_p_may_alias;
- return true;
+ int cmp = compare_type_sizes (type2, TREE_TYPE (*refp));
+ if (cmp < 0)
+ break;
+ /* If types may be of same size, see if we can decide about their
+ equality. */
+ if (cmp >= 0)
+ {
+ same_p1 = same_type_for_tbaa (TREE_TYPE (*refp), type2);
+ if (same_p1 != 0)
+ break;
+ }
+ if (!handled_component_p (*refp))
+ break;
+ refp = &TREE_OPERAND (*refp, 0);
}
- else
+ if (same_p1 == 1)
{
- ++alias_stats.aliasing_component_refs_p_no_alias;
- return false;
- }
- }
+ poly_int64 offadj, sztmp, msztmp;
+ bool reverse;
- /* In the remaining test we assume that there is no overlapping type
- at all. So if we are unsure, we need to give up. */
- if (same_p == -1 || same_p2 == -1)
- {
- ++alias_stats.aliasing_component_refs_p_may_alias;
- return true;
+ get_ref_base_and_extent (*refp, &offadj, &sztmp, &msztmp, &reverse);
+ offset1 -= offadj;
+ get_ref_base_and_extent (base2, &offadj, &sztmp, &msztmp, &reverse);
+ offset2 -= offadj;
+ if (ranges_maybe_overlap_p (offset1, max_size1, offset2, max_size2))
+ {
+ ++alias_stats.aliasing_component_refs_p_may_alias;
+ return true;
+ }
+ else
+ {
+ ++alias_stats.aliasing_component_refs_p_no_alias;
+ return false;
+ }
+ }
}
/* If we have two type access paths B1.path1 and B2.path2 they may
@@ -883,15 +953,19 @@ aliasing_component_refs_p (tree ref1,
a part that we do not see. So we can only disambiguate now
if there is no B2 in the tail of path1 and no B1 on the
tail of path2. */
- if (base1_alias_set == ref2_alias_set
- || alias_set_subset_of (base1_alias_set, ref2_alias_set))
+ if (compare_type_sizes (TREE_TYPE (ref2), type1) >= 0
+ && (same_p2 == -1
+ || base1_alias_set == ref2_alias_set
+ || alias_set_subset_of (base1_alias_set, ref2_alias_set)))
{
++alias_stats.aliasing_component_refs_p_may_alias;
return true;
}
/* If this is ptr vs. decl then we know there is no ptr ... decl path. */
if (!ref2_is_decl
- && (base2_alias_set == ref1_alias_set
+ && compare_type_sizes (TREE_TYPE (ref1), type2) >= 0
+ && (same_p1 == -1
+ || base2_alias_set == ref1_alias_set
|| alias_set_subset_of (base2_alias_set, ref1_alias_set)))
{
++alias_stats.aliasing_component_refs_p_may_alias;
@@ -1221,16 +1295,13 @@ indirect_ref_may_alias_decl_p (tree ref1
/* If the size of the access relevant for TBAA through the pointer
is bigger than the size of the decl we can't possibly access the
decl via that pointer. */
- if (DECL_SIZE (base2) && COMPLETE_TYPE_P (TREE_TYPE (ptrtype1))
- && poly_int_tree_p (DECL_SIZE (base2))
- && poly_int_tree_p (TYPE_SIZE (TREE_TYPE (ptrtype1)))
- /* ??? This in turn may run afoul when a decl of type T which is
+ if (/* ??? This in turn may run afoul when a decl of type T which is
a member of union type U is accessed through a pointer to
type U and sizeof T is smaller than sizeof U. */
- && TREE_CODE (TREE_TYPE (ptrtype1)) != UNION_TYPE
+ TREE_CODE (TREE_TYPE (ptrtype1)) != UNION_TYPE
&& TREE_CODE (TREE_TYPE (ptrtype1)) != QUAL_UNION_TYPE
- && known_lt (wi::to_poly_widest (DECL_SIZE (base2)),
- wi::to_poly_widest (TYPE_SIZE (TREE_TYPE (ptrtype1)))))
+ && compare_sizes (DECL_SIZE (base2),
+ TYPE_SIZE (TREE_TYPE (ptrtype1))) < 0)
return false;
if (!ref2)
