Hi,
this patch adds basic TBAA for pointers to LTO. The basic scheme is simple;
because TYPE_CANONICAL is not really needed by get_alias_set, we completely
drop the caluclation of these (which also saves about 50% canonical type hash
searches) and update get_alias_set to not punt on pointers with
TYPE_STRUCTURAL_EQUALITY.
The patch makes quite nice improvements (32%) on number of disambiguations on
dealII (that is my random C++ testbed):
Before:
[WPA] GIMPLE canonical type table: size 16381, 817 elements, 35453 searches, 91
collisions (ratio: 0.002567)
[WPA] GIMPLE canonical type pointer-map: 817 elements, 15570 searches
after:
[WPA] GIMPLE canonical type table: size 16381, 822 elements, 14863 searches,
114 collisions (ratio: 0.007670)
[WPA] GIMPLE canonical type pointer-map: 822 elements, 12663 searches
The number of disambiguations goes 1713472->2331078 (32%)
and number of queries goes 3387753->3669698 (8%)
We get code size growth 677527->701782 (3%)
Also a query is disambiguated 63% of the time instead of 50% we had before.
Clearly there are many areas for improvements (since functions are
TYPE_STRUCTURAL_EQUALITY in LTO we ptr_type_node alias set on them), but that
M
can wait for next stage1.
lto-bootstrapped/regtested x86_64-linux and also used it in my tree for quite
a while, so the patch was tested on Firefox and other applications.
OK?
Honza
* alias.c (get_alias_set): Do structural equality for pointer types;
drop LTO specific path.
* lto.c (iterative_hash_canonical_type): Do not compute TYPE_CANONICAL
for pointer types.
(gimple_register_canonical_type_1): Likewise.
(gimple_register_canonical_type): Likewise.
(lto_register_canonical_types): Do not clear canonical types of pointer
types.
Index: lto/lto.c
===================================================================
--- lto/lto.c (revision 229968)
+++ lto/lto.c (working copy)
@@ -396,8 +396,13 @@ iterative_hash_canonical_type (tree type
/* All type variants have same TYPE_CANONICAL. */
type = TYPE_MAIN_VARIANT (type);
+
+ /* We do not compute TYPE_CANONICAl of POINTER_TYPE becuase the aliasing
+ code never use it anyway. */
+ if (POINTER_TYPE_P (type))
+ v = hash_canonical_type (type);
/* An already processed type. */
- if (TYPE_CANONICAL (type))
+ else if (TYPE_CANONICAL (type))
{
type = TYPE_CANONICAL (type);
v = gimple_canonical_type_hash (type);
@@ -445,7 +450,9 @@ gimple_register_canonical_type_1 (tree t
{
void **slot;
- gcc_checking_assert (TYPE_P (t) && !TYPE_CANONICAL (t));
+ gcc_checking_assert (TYPE_P (t) && !TYPE_CANONICAL (t)
+ && type_with_alias_set_p (t)
+ && TREE_CODE (t) != POINTER_TYPE);
slot = htab_find_slot_with_hash (gimple_canonical_types, t, hash, INSERT);
if (*slot)
@@ -478,7 +485,7 @@ gimple_register_canonical_type_1 (tree t
static void
gimple_register_canonical_type (tree t)
{
- if (TYPE_CANONICAL (t) || !type_with_alias_set_p (t))
+ if (TYPE_CANONICAL (t) || !type_with_alias_set_p (t) || POINTER_TYPE_P (t))
return;
/* Canonical types are same among all complete variants. */
@@ -498,14 +505,13 @@ static void
lto_register_canonical_types (tree node, bool first_p)
{
if (!node
- || !TYPE_P (node))
+ || !TYPE_P (node) || POINTER_TYPE_P (node))
return;
if (first_p)
TYPE_CANONICAL (node) = NULL_TREE;
- if (POINTER_TYPE_P (node)
- || TREE_CODE (node) == COMPLEX_TYPE
+ if (TREE_CODE (node) == COMPLEX_TYPE
|| TREE_CODE (node) == ARRAY_TYPE)
lto_register_canonical_types (TREE_TYPE (node), first_p);
Index: tree.c
===================================================================
--- tree.c (revision 229968)
+++ tree.c (working copy)
@@ -13198,6 +13198,7 @@ gimple_canonical_types_compatible_p (con
/* If the types have been previously registered and found equal
they still are. */
if (TYPE_CANONICAL (t1) && TYPE_CANONICAL (t2)
+ && !POINTER_TYPE_P (t1) && !POINTER_TYPE_P (t2)
&& trust_type_canonical)
return TYPE_CANONICAL (t1) == TYPE_CANONICAL (t2);
Index: alias.c
===================================================================
--- alias.c (revision 229968)
+++ alias.c (working copy)
@@ -869,13 +874,19 @@ get_alias_set (tree t)
set = lang_hooks.get_alias_set (t);
if (set != -1)
return set;
- return 0;
+ /* LTO frontend does not assign canonical types to pointers (which we
+ ignore anyway) and we compute them. The following path may be
+ probably enabled for non-LTO, too, and it may improve TBAA for
+ pointers to types with structural equality. */
+ if (!in_lto_p || !POINTER_TYPE_P (t))
+ return 0;
+ }
+ else
+ {
+ t = TYPE_CANONICAL (t);
+ /* The canonical type should not require structural equality checks. */
+ gcc_checking_assert (!TYPE_STRUCTURAL_EQUALITY_P (t));
}
-
- t = TYPE_CANONICAL (t);
-
- /* The canonical type should not require structural equality checks. */
- gcc_checking_assert (!TYPE_STRUCTURAL_EQUALITY_P (t));
/* If this is a type with a known alias set, return it. */
if (TYPE_ALIAS_SET_KNOWN_P (t))
@@ -952,20 +963,23 @@ get_alias_set (tree t)
ptr_type_node but that is a bad idea, because it prevents disabiguations
in between pointers. For Firefox this accounts about 20% of all
disambiguations in the program. */
- else if (POINTER_TYPE_P (t) && t != ptr_type_node && !in_lto_p)
+ else if (POINTER_TYPE_P (t) && t != ptr_type_node)
{
tree p;
auto_vec <bool, 8> reference;
/* Unnest all pointers and references.
- We also want to make pointer to array equivalent to pointer to its
- element. So skip all array types, too. */
+ We also want to make pointer to array/vector equivalent to pointer to
+ its element (see the reasoning above). Skip all those types, too. */
for (p = t; POINTER_TYPE_P (p)
- || (TREE_CODE (p) == ARRAY_TYPE && !TYPE_NONALIASED_COMPONENT (p));
+ || (TREE_CODE (p) == ARRAY_TYPE && !TYPE_NONALIASED_COMPONENT (p))
+ || TREE_CODE (p) == VECTOR_TYPE;
p = TREE_TYPE (p))
{
if (TREE_CODE (p) == REFERENCE_TYPE)
- reference.safe_push (true);
+ /* In LTO we want languages that use references to be compatible
+ with languages that use pointers. */
+ reference.safe_push (true && !in_lto_p);
if (TREE_CODE (p) == POINTER_TYPE)
reference.safe_push (false);
}
@@ -998,9 +1012,23 @@ get_alias_set (tree t)
p = build_reference_type (p);
else
p = build_pointer_type (p);
- p = TYPE_CANONICAL (TYPE_MAIN_VARIANT (p));
+ p = TYPE_MAIN_VARIANT (p);
+ /* Normally all pointer types are built by
+ build_pointer_type_for_mode which ensures they have canonical
+ type unless they point to type with structural equality.
+ LTO frontend produce pointer types without TYPE_CANONICAL
+ that are then added to TYPE_POINTER_TO lists and
+ build_pointer_type_for_mode will end up picking one for us.
+ Declare it the canonical one. This is the same as
+ build_pointer_type_for_mode would do. */
+ if (!TYPE_CANONICAL (p))
+ {
+ TYPE_CANONICAL (p) = p;
+ gcc_checking_assert (in_lto_p);
+ }
+ else
+ gcc_checking_assert (p == TYPE_CANONICAL (p));
}
- gcc_checking_assert (TYPE_CANONICAL (p) == p);
/* Assign the alias set to both p and t.
We can not call get_alias_set (p) here as that would trigger
@@ -1015,11 +1043,6 @@ get_alias_set (tree t)
}
}
}
- /* In LTO the rules above needs to be part of canonical type machinery.
- For now just punt. */
- else if (POINTER_TYPE_P (t)
- && t != TYPE_CANONICAL (ptr_type_node) && in_lto_p)
- set = get_alias_set (TYPE_CANONICAL (ptr_type_node));
/* Otherwise make a new alias set for this type. */
else
