Strenghten aliasing_component_refs_p
Jan Hubicka
hubicka@ucw.cz
Fri May 17 05:38:00 GMT 2019
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);
+ 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;
More information about the Gcc-patches
mailing list