On Sun, 8 Nov 2015, Jan Hubicka wrote:
> 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);
POINTER_TYPE_P
>
> 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);
Hmm, here we'll miss registering canoncial types for the
pointed-to type. I believe this will miss FILE for example but also
some va_list types? Please drop this change.
> 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)
But TYPE_CANONICAL (t1) should be NULL_TREE for POINTER_TYPE_P?
> && 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;
No new LTO paths please, do the suggested change immediately.
> + }
> + 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));
The assert can trigger as
build_pointer_type_for_mode builds SET_TYPE_STRUCTURAL_EQUALITY pointer
types for SET_TYPE_STRUCTURAL_EQUALITY pointed-to types. Ah,
looking up more context reveals
if (TREE_CODE (p) == VOID_TYPE || TYPE_STRUCTURAL_EQUALITY_P (p))
set = get_alias_set (ptr_type_node);
Not sure why you adjust TYPE_CANONICAL here at all either.
Otherwise looks ok.
RIchard.
> }
> - 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
>
>
--
Richard Biener <rguent...@suse.de>
SUSE LINUX GmbH, GF: Felix Imendoerffer, Jane Smithard, Graham Norton, HRB
21284 (AG Nuernberg)
