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"?
> + return false;
> + return true;
> +}
> +
> /* 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 +824,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 +837,88 @@ 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)
> + would be a common base for doing offset based disambiguation on.
> + This however only makes sense if type2 is big enough to hold type1. */
> + if (type_big_enough_for_type_p (type2, type1))
> {
> - 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))
> + 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. */
> + if (!type_big_enough_for_type_p (type1, TREE_TYPE (*refp)))
> + break;
> + /* If types may be of same size, see if we can decide about their
> + equality. */
> + if (type_big_enough_for_type_p (TREE_TYPE (*refp), type1))
> + {
> + 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)
> + if (type_big_enough_for_type_p (type1, type2))
> {
> - 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))
> + refp = &ref1;
> + while (true)
> {
> - ++alias_stats.aliasing_component_refs_p_may_alias;
> - return true;
> + if (!type_big_enough_for_type_p (type2, TREE_TYPE (*refp)))
> + break;
> + if (type_big_enough_for_type_p (TREE_TYPE (*refp), type2))
> + {
> + 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 +927,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 (type_big_enough_for_type_p (TREE_TYPE (ref2), type1)
> + && (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
> + && type_big_enough_for_type_p (TREE_TYPE (ref1), type2)
> + && (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;
>
--
Richard Biener <rguent...@suse.de>
SUSE Linux GmbH, Maxfeldstrasse 5, 90409 Nuernberg, Germany;
GF: Felix Imendörffer, Mary Higgins, Sri Rasiah; HRB 21284 (AG Nürnberg)
