On 20 May 2019 11:40:17 CEST, Richard Biener <rguent...@suse.de> wrote:
>On Sun, 19 May 2019, Jan Hubicka wrote:
>
>> > 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. */
>
>incomparable.
>
>OK with that fix.
Really? See below.
>
>Richard.
>
>> +
>> +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);
Doesn't poly_into_tree_p return a bool?
I think we want to omit these two initializers.
thanks,
>> +
>> + 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)
>>
