On Thu, 23 May 2019, Bernhard Reutner-Fischer wrote: > 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,
Whoops, didn't notice that. Indeed - Honza please fix. Richard. > >> + > >> + 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) > >> > > -- 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)