| Message ID | 20190517053840.l545ideou2lzelkd@kam.mff.cuni.cz |
|---|---|
| State | New |
| Headers | show |
| Series | Strenghten aliasing_component_refs_p | expand |
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; >
> 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? It can still return 0. Current implementation is bit questionable: 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. */ if (TYPE_CANONICAL (type1) == TYPE_CANONICAL (type2)) return 1; /* ??? Array types are not properly unified in all cases as we have spurious changes in the index types for example. Removing this causes all sorts of problems with the Fortran frontend. */ if (TREE_CODE (type1) == ARRAY_TYPE && TREE_CODE (type2) == ARRAY_TYPE) return -1; I plan to check what testcases breaks if that conditional goes away. The aforementioned testcase dues :) > > > + 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"? We also want "equivalent" (which is a common case). I would expect this to inline & optimize relatively well? aliasing_component_refs is already bit awkward to read. Honza
> 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)
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. 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); > + > + 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) >
On 20 May 2019 11:40:17 CEST, Richard Biener <rguenther@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) >>
On Thu, 23 May 2019, Bernhard Reutner-Fischer wrote: > On 20 May 2019 11:40:17 CEST, Richard Biener <rguenther@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) > >> > >
> On Thu, 23 May 2019, Bernhard Reutner-Fischer wrote: > > > On 20 May 2019 11:40:17 CEST, Richard Biener <rguenther@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. Sorry for that - too much cut&paste I assume. I am testing fix (the bug is harmless, we just do the conversion twice) and looking into the soplex issue. Honza
> > Whoops, didn't notice that. > > Indeed - Honza please fix. > Thanks to Martin's reduction, hunting down the soplex issue was easy. There was two thinkos I managed to introduce while converting the patch to three way compare. First we only need to call same_types_for_tbaa if the sizes actually looks same (in soplex we try to compare pointer with record and get -1 because in LTO pointers have no canonical types) but if we fail to match some types we can not dispatch to the logic trying to disprove that one patch can be continuation of the other. We still improve the situation here because we compare only types that may match based on the size observations. This is what I am testing and plan to commmit if it passes to prevent others from running into this issue. The number of disambiguation on tramp3d seems unaffected by this patch aliasing_component_ref_p: 154 disambiguations, 12523 queries As a followup strenghtening, I think we may want to continue looking for matching type even if we hit first -1 (and just remember that we can not do the lest test), but I suppose fixing same_types_for_tbaa for LTO makes more sense (and I have patch for it next). After that I will try to see if this improves the situation at all. Honza Jan Hubicka <jh@suse.cz> Martin Liska <mliska@suse.cz> PR tree-optimization/90576 * tree-ssa-alias.c (compare_sizes): Remove dead calls to poly_int_tree_p. (aliasing_component_refs_p): Fix three way size compare conditional; give up earlier in case we can not decide on equivalence. Index: tree-ssa-alias.c =================================================================== --- tree-ssa-alias.c (revision 271511) +++ tree-ssa-alias.c (working copy) @@ -746,8 +746,8 @@ 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); + poly_uint64 size1; + poly_uint64 size2; if (!poly_int_tree_p (s1, &size1) || !poly_int_tree_p (s2, &size2)) return 0; @@ -873,7 +873,7 @@ aliasing_component_refs_p (tree ref1, break; /* If types may be of same size, see if we can decide about their equality. */ - if (cmp >= 0) + if (cmp == 0) { same_p2 = same_type_for_tbaa (TREE_TYPE (*refp), type1); if (same_p2 != 0) @@ -915,7 +915,7 @@ aliasing_component_refs_p (tree ref1, break; /* If types may be of same size, see if we can decide about their equality. */ - if (cmp >= 0) + if (cmp == 0) { same_p1 = same_type_for_tbaa (TREE_TYPE (*refp), type2); if (same_p1 != 0) @@ -947,6 +947,13 @@ aliasing_component_refs_p (tree ref1, } } + /* In the following code we make an assumption that the types in access + paths do not overlap and thus accesses alias only if one path can be + continuation of another. If we was not able to decide about equivalence, + we need to give up. */ + if (same_p1 == -1 || same_p2 == -1) + return true; + /* 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. But we can still have a path that goes B1.path1...B2.path2 with @@ -954,8 +961,7 @@ aliasing_component_refs_p (tree ref1, if there is no B2 in the tail of path1 and no B1 on the tail of path2. */ if (compare_type_sizes (TREE_TYPE (ref2), type1) >= 0 - && (same_p2 == -1 - || base1_alias_set == ref2_alias_set + && (base1_alias_set == ref2_alias_set || alias_set_subset_of (base1_alias_set, ref2_alias_set))) { ++alias_stats.aliasing_component_refs_p_may_alias; @@ -964,8 +970,7 @@ aliasing_component_refs_p (tree ref1, /* If this is ptr vs. decl then we know there is no ptr ... decl path. */ if (!ref2_is_decl && compare_type_sizes (TREE_TYPE (ref1), type2) >= 0 - && (same_p1 == -1 - || base2_alias_set == ref1_alias_set + && (base2_alias_set == ref1_alias_set || alias_set_subset_of (base2_alias_set, ref1_alias_set))) { ++alias_stats.aliasing_component_refs_p_may_alias;
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); + if (!poly_int_tree_p (TYPE_SIZE (type1)) + || !poly_int_tree_p (TYPE_SIZE (type2))) + return true; + if (known_lt (wi::to_poly_widest (TYPE_SIZE (type1)), + wi::to_poly_widest (TYPE_SIZE (type2)))) + 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;
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.