From patchwork Mon Jun 3 13:29:57 2019 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jan Hubicka X-Patchwork-Id: 1109273 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Authentication-Results: ozlabs.org; spf=pass (mailfrom) smtp.mailfrom=gcc.gnu.org (client-ip=209.132.180.131; helo=sourceware.org; envelope-from=gcc-patches-return-502207-incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=) Authentication-Results: ozlabs.org; dmarc=none (p=none dis=none) header.from=ucw.cz Received: from sourceware.org (server1.sourceware.org [209.132.180.131]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 45HbXW0YW8z9s4V for ; Mon, 3 Jun 2019 23:30:33 +1000 (AEST) DomainKey-Signature: a=rsa-sha1; c=nofws; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender:date :from:to:subject:message-id:mime-version:content-type; q=dns; s= default; b=REAtLJ3tw/eo8I7sACSr0m+RyS25KxvT59Vp1bRCm0c0kkCHDCcQQ 9sNgMlEvStvI2JyP8rKgxKDsEc2+t2CxS+Aioocg6lULeyjvrI/gLMVGzu8dva6Y Puepm7P+S18C0f8T9pZV/5Lcw5LjAj8oQVOkVbyYXutoi1UajQAEXQ= DKIM-Signature: v=1; a=rsa-sha1; c=relaxed; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender:date :from:to:subject:message-id:mime-version:content-type; s= default; bh=42mAyOkcLZqVrdhYQ7JleH0aPGA=; b=GmQsN6J/BRcc9UzCk7LN /Z2t+ZH8e+zKyMOdPtROYr6+UurrUI7Wp9JzseH6/fevs2u3abR7cNIxFGvT9x0H HHoVTMVgZ/wDbl6cMYQDq2C77+0ar2WvGr2lGB6Nf6zNNnbN6CHHckUhujkA/CdN +Mi9Lf/7Zguvd/7B7QkGmek= Received: (qmail 124418 invoked by alias); 3 Jun 2019 13:30:04 -0000 Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Unsubscribe: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Delivered-To: mailing list gcc-patches@gcc.gnu.org Received: (qmail 124396 invoked by uid 89); 3 Jun 2019 13:30:04 -0000 Authentication-Results: sourceware.org; auth=none X-Spam-SWARE-Status: No, score=-9.4 required=5.0 tests=AWL, BAYES_00, GIT_PATCH_2, GIT_PATCH_3, KAM_ASCII_DIVIDERS autolearn=ham version=3.3.1 spammy=TRUE, avail, apps, combined X-HELO: nikam.ms.mff.cuni.cz Received: from nikam.ms.mff.cuni.cz (HELO nikam.ms.mff.cuni.cz) (195.113.20.16) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Mon, 03 Jun 2019 13:29:59 +0000 Received: by nikam.ms.mff.cuni.cz (Postfix, from userid 16202) id 5B2B92804D4; Mon, 3 Jun 2019 15:29:57 +0200 (CEST) Date: Mon, 3 Jun 2019 15:29:57 +0200 From: Jan Hubicka To: gcc-patches@gcc.gnu.org, rguenther@suse.de, d@dcepelik.cz, mliska@suse.cz Subject: Use ODR for canonical types construction in LTO Message-ID: <20190603132957.w2vh5z3zu3h6z2ib@kam.mff.cuni.cz> MIME-Version: 1.0 Content-Disposition: inline User-Agent: NeoMutt/20170113 (1.7.2) Hi, this patch makes LTO to use ODR names when building canonical types. Theoretically this is easy task because every ODR type is unique and it is enough to fill in the hash with the ODR names and compare them. In reality we want to be more careful and detect situation when non-ODR type is structurally equivalent to ODR type so C++ code and non-C++ code can co-exist. I have implemented it as follows 1) at stream in time populate canonical type hash by non-ODR types only. Also register all ODR types into so we detect ODR violations. 2) once all streaming is done we process all ODR types, lookup each of them in the canonical type hash and if structurally compatible type is present default to normal canonical type calculation. Otherwise canonical type of ODR type is the prevailing ODR variant. Now the problem is that in C++ some structures can be non-ODR. For example struct A {int a;} a; struct {int b;} b; Here the second structure has no name and we have no way to tell if it is C++ or non-C++ code at LTO time. I tought that perhaps such conflicts would be rare, but in reality most of types conflicts this way (C++ FE seems to generate non-ODR types of same strucutre as ODR types and they do get streamed, I am looking into this). So more careful approach is needed. I extende extend step 1 to also postpone types that reffers to ODR types (those are known to originate from C++ translation units and do not need to be unified by structurally equivalent ODR types). This is tested by odr_or_derived_type_p which is kind of hack and perhaps we should get around streaming this info somehow (but i would preffer to do that incrementally) Step 2 remain same. Additional step 3 registers all odr derived types into canonical type hash. This requires canonical type hash to play well with ODR types (i.e. not consider them equivalent based on structural equivalety). The decision on whether given type has ODR based canonical type is stored in odr_based_tbaa_p and is used 1) by gimple_canonical_types_compatible_p so the comparsion is behaving well after ODR types are inserted into the hash 2) by alias.c to be build more precise alias sets - for ODR types it is not necessary to glob pointers into void *. There is no need to update canonical type hash since I simply insert hash codes of ODR names into canonical type hash cache. LTO linking cc1plus there are 3317 ODR types that gets their own canonical type and 876 which have conflict. For example: ODR and non-ODR type conflict: union ssa_name_info_type and union { const void * cv; void * v; } ODR and non-ODR type conflict: struct ht_identifier and struct { union byte_fail_stack_elt_t * stack; unsigned int size; unsigned int avail; } ODR and non-ODR type conflict: struct lang_hooks_for_tree_dump and struct { struct demangle_component * left; struct demangle_component * right; } ODR and non-ODR type conflict: struct call_site_record_d and struct { struct demangle_component * sub; int num; } etc. So mostly random conflict induced by the C compiled liberty and other bits. Clearly most common issue is globing of pointers and lack of field names which is needed primarily for Fortran and is easy to disable for translation units not having Fortran modules in them. Canonical type hash stats for cc1plus build: [WPA] GIMPLE canonical type table: size 16381, 1590 elements, 6797 searches, 88 collisions (ratio: 0.012947) [WPA] GIMPLE canonical type pointer-map: 1590 elements, 15494 searches to: [WPA] GIMPLE canonical type table: size 16381, 755 elements, 6311 searches, 57 collisions (ratio: 0.009032) [WPA] GIMPLE canonical type pointer-map: 755 elements, 15553 searches So without patch there are 1590 distinct canonical types, with the patch there are 755 non-ODR and 3317 odr types, about 2.5 times more. And alias oracle stats for -flto-partition=none cc1plus build: Alias oracle query stats: refs_may_alias_p: 39227004 disambiguations, 47344870 queries ref_maybe_used_by_call_p: 57815 disambiguations, 39808081 queries call_may_clobber_ref_p: 5511 disambiguations, 8287 queries aliasing_component_ref_p: 90654 disambiguations, 269895 queries TBAA oracle: 11130153 disambiguations 34368560 queries 14199938 are in alias set 0 5193428 queries asked about the same object 147 queries asked about the same alias set 0 access volatile 1665979 are dependent in the DAG 2178915 are aritificially in conflict with void * PTA query stats: pt_solution_includes: 464074 disambiguations, 7105649 queries pt_solutions_intersect: 355139 disambiguations, 6952492 queries Alias oracle query stats: refs_may_alias_p: 39682205 disambiguations, 47774305 queries ref_maybe_used_by_call_p: 58390 disambiguations, 40265537 queries call_may_clobber_ref_p: 5619 disambiguations, 8397 queries aliasing_component_ref_p: 61523 disambiguations, 240208 queries TBAA oracle: 11691755 disambiguations 34552651 queries 14233568 are in alias set 0 5230754 queries asked about the same object 147 queries asked about the same alias set 0 access volatile 2433081 are dependent in the DAG 963346 are aritificially in conflict with void * PTA query stats: pt_solution_includes: 457871 disambiguations, 7044729 queries pt_solutions_intersect: 367701 disambiguations, 6859208 queries So about 455k new disambiguations or 5% more TBAA ones. It is about half of what PTA oracle stats shows, so it seems reasibale improvement to me. The patch results in about 1% cc1plus code size increase. (mostly because of less ICF) For tramp3d the stats are: refs_may_alias_p: 3252729 disambiguations, 3587196 queries ref_maybe_used_by_call_p: 7018 disambiguations, 3280028 queries call_may_clobber_ref_p: 883 disambiguations, 883 queries aliasing_component_ref_p: 549 disambiguations, 17885 queries TBAA oracle: 1644568 disambiguations 3261681 queries 555812 are in alias set 0 680883 queries asked about the same object 0 queries asked about the same alias set 0 access volatile 248396 are dependent in the DAG 132022 are aritificially in conflict with void * PTA query stats: pt_solution_includes: 641563 disambiguations, 921034 queries pt_solutions_intersect: 115861 disambiguations, 501205 queries Alias oracle query stats: refs_may_alias_p: 3016277 disambiguations, 3316301 queries ref_maybe_used_by_call_p: 7134 disambiguations, 3042055 queries call_may_clobber_ref_p: 817 disambiguations, 817 queries aliasing_component_ref_p: 495 disambiguations, 14565 queries TBAA oracle: 1416803 disambiguations 2911585 queries 552489 are in alias set 0 567158 queries asked about the same object 0 queries asked about the same alias set 0 access volatile 259923 are dependent in the DAG 115212 are aritificially in conflict with void * PTA query stats: pt_solution_includes: 668779 disambiguations, 949986 queries pt_solutions_intersect: 96232 disambiguations, 436617 queries About 7% difference. I did Firefox stats with earlier variant of this patch and difference was about 12%. It takes about a day for lto1-ltrans with one partition to converge (and two days for for gas) so I did not re-run it with final version. Code size difference is about 4%. Notice also that access path oracle now suceeds less often since we less often mix up unrealted types. In general with more precist TBAA lookups the oracle should be bit cheaper by avoiding more complex tests. lto-bootstrapped/regtested x86_64-linux with all languages and also tested on few extra C++ apps. * alias.c (record_component_aliases): Honor odr_based_tbaa_p. * ipa-devirt.c (odr_type_d): Add tbaa_enabled field. (get_odr_type): Return NULL when odr_type_hash is NULL. (enable_odr_based_tbaa): New function. (odr_based_tbaa_p): New function. (set_type_canonical_for_odr_type): New function. * ipa-utils.h (enable_odr_based_tbaa, odr_based_tbaa_p, set_type_canonical_for_odr_type): Declare. * lto-common.c: Update copyright; include tree-pretty-print.h. (types_to_register): New static var. (iterative_hash_canonical_type): Add new parameter INSERT. (hash_canonical_type): Likewise. (lookup_canonical_type): New function. (lto_register_canonical_types_for_odr_types): New. (odr_or_derived_type_p): New function. (lto_read_decls): Deffer ODR and ODR derived types to later canonical type calculation. * tree.c (gimple_canonical_types_compatible_p): Honnor odr_based_tbaa_p. Index: alias.c =================================================================== --- alias.c (revision 271843) +++ alias.c (working copy) @@ -1202,47 +1202,52 @@ record_component_aliases (tree type) case RECORD_TYPE: case UNION_TYPE: case QUAL_UNION_TYPE: - for (field = TYPE_FIELDS (type); field != 0; field = DECL_CHAIN (field)) - if (TREE_CODE (field) == FIELD_DECL && !DECL_NONADDRESSABLE_P (field)) - { - /* LTO type merging does not make any difference between - component pointer types. We may have - - struct foo {int *a;}; - - as TYPE_CANONICAL of - - struct bar {float *a;}; - - Because accesses to int * and float * do not alias, we would get - false negative when accessing the same memory location by - float ** and bar *. We thus record the canonical type as: - - struct {void *a;}; - - void * is special cased and works as a universal pointer type. - Accesses to it conflicts with accesses to any other pointer - type. */ - tree t = TREE_TYPE (field); - if (in_lto_p) - { - /* VECTOR_TYPE and ARRAY_TYPE share the alias set with their - element type and that type has to be normalized to void *, - too, in the case it is a pointer. */ - while (!canonical_type_used_p (t) && !POINTER_TYPE_P (t)) - { - gcc_checking_assert (TYPE_STRUCTURAL_EQUALITY_P (t)); - t = TREE_TYPE (t); - } - if (POINTER_TYPE_P (t)) - t = ptr_type_node; - else if (flag_checking) - gcc_checking_assert (get_alias_set (t) - == get_alias_set (TREE_TYPE (field))); - } - - record_alias_subset (superset, get_alias_set (t)); - } + { + /* LTO non-ODR type merging does not make any difference between + component pointer types. We may have + + struct foo {int *a;}; + + as TYPE_CANONICAL of + + struct bar {float *a;}; + + Because accesses to int * and float * do not alias, we would get + false negative when accessing the same memory location by + float ** and bar *. We thus record the canonical type as: + + struct {void *a;}; + + void * is special cased and works as a universal pointer type. + Accesses to it conflicts with accesses to any other pointer + type. */ + bool void_pointers = in_lto_p + && (!odr_type_p (type) + || !odr_based_tbaa_p (type)); + for (field = TYPE_FIELDS (type); field != 0; field = DECL_CHAIN (field)) + if (TREE_CODE (field) == FIELD_DECL && !DECL_NONADDRESSABLE_P (field)) + { + tree t = TREE_TYPE (field); + if (void_pointers) + { + /* VECTOR_TYPE and ARRAY_TYPE share the alias set with their + element type and that type has to be normalized to void *, + too, in the case it is a pointer. */ + while (!canonical_type_used_p (t) && !POINTER_TYPE_P (t)) + { + gcc_checking_assert (TYPE_STRUCTURAL_EQUALITY_P (t)); + t = TREE_TYPE (t); + } + if (POINTER_TYPE_P (t)) + t = ptr_type_node; + else if (flag_checking) + gcc_checking_assert (get_alias_set (t) + == get_alias_set (TREE_TYPE (field))); + } + + record_alias_subset (superset, get_alias_set (t)); + } + } break; case COMPLEX_TYPE: Index: ipa-devirt.c =================================================================== --- ipa-devirt.c (revision 271843) +++ ipa-devirt.c (working copy) @@ -213,6 +213,8 @@ struct GTY(()) odr_type_d bool odr_violated; /* Set when virtual table without RTTI previaled table with. */ bool rtti_broken; + /* Set when we need to give up on ODR based TBAA info. */ + bool tbaa_enabled; }; /* Return TRUE if all derived types of T are known and thus @@ -2045,6 +2047,9 @@ get_odr_type (tree type, bool insert) if (!in_lto_p && !TYPE_STRUCTURAL_EQUALITY_P (type)) type = TYPE_CANONICAL (type); + if (!odr_hash) + return NULL; + gcc_checking_assert (can_be_name_hashed_p (type) || can_be_vtable_hashed_p (type)); @@ -2182,6 +2187,45 @@ prevailing_odr_type (tree type) return t->type; } +/* Set tbaa_enabled flag for TYPE. */ + +void +enable_odr_based_tbaa (tree type) +{ + odr_type t = get_odr_type (type, true); + t->tbaa_enabled = true; +} + +/* Return type that in ODR type hash prevailed TYPE. Be careful and punt + on ODR violations. */ + +bool +odr_based_tbaa_p (const_tree type) +{ + odr_type t = get_odr_type (const_cast (type), false); + if (!t || !t->tbaa_enabled) + return false; + return true; +} + +/* Set TYPE_CANONICAL of type and all its variants and duplicates + to CANONICAL. */ + +void +set_type_canonical_for_odr_type (tree type, tree canonical) +{ + odr_type t = get_odr_type (type, false); + unsigned int i; + tree tt; + + for (tree t2 = t->type; t2; t2 = TYPE_NEXT_VARIANT (t2)) + TYPE_CANONICAL (t2) = canonical; + if (t->types) + FOR_EACH_VEC_ELT (*t->types, i, tt) + for (tree t2 = tt; t2; t2 = TYPE_NEXT_VARIANT (t2)) + TYPE_CANONICAL (t2) = canonical; +} + /* Return true if we reported some ODR violation on TYPE. */ bool Index: ipa-utils.h =================================================================== --- ipa-utils.h (revision 271843) +++ ipa-utils.h (working copy) @@ -93,6 +93,9 @@ bool odr_or_derived_type_p (const_tree t bool odr_types_equivalent_p (tree type1, tree type2); bool odr_type_violation_reported_p (tree type); tree prevailing_odr_type (tree type); +void enable_odr_based_tbaa (tree type); +bool odr_based_tbaa_p (const_tree type); +void set_type_canonical_for_odr_type (tree type, tree canonical); /* Return vector containing possible targets of polymorphic call E. If COMPLETEP is non-NULL, store true if the list is complete. Index: lto/lto-common.c =================================================================== --- lto/lto-common.c (revision 271843) +++ lto/lto-common.c (working copy) @@ -1,5 +1,5 @@ /* Top-level LTO routines. - Copyright (C) 2009-2018 Free Software Foundation, Inc. + Copyright (C) 2009-2019 Free Software Foundation, Inc. Contributed by CodeSourcery, Inc. This file is part of GCC. @@ -56,6 +56,7 @@ along with GCC; see the file COPYING3. #include "attribs.h" #include "builtins.h" #include "lto-common.h" +#include "tree-pretty-print.h" GTY(()) tree first_personality_decl; @@ -212,22 +213,26 @@ lto_read_in_decl_state (struct data_in * /* Global canonical type table. */ +static GTY(()) vec *types_to_register = NULL; static htab_t gimple_canonical_types; static hash_map *canonical_type_hash_cache; static unsigned long num_canonical_type_hash_entries; static unsigned long num_canonical_type_hash_queries; -static void iterative_hash_canonical_type (tree type, inchash::hash &hstate); +static void iterative_hash_canonical_type (tree type, inchash::hash &hstate, bool); static hashval_t gimple_canonical_type_hash (const void *p); static void gimple_register_canonical_type_1 (tree t, hashval_t hash); /* Returning a hash value for gimple type TYPE. The hash value returned is equal for types considered compatible - by gimple_canonical_types_compatible_p. */ + by gimple_canonical_types_compatible_p. + + If INSERT is true, also populate canonical type hash by all + types TYPE is derived from. */ static hashval_t -hash_canonical_type (tree type) +hash_canonical_type (tree type, bool insert) { inchash::hash hstate; enum tree_code code; @@ -293,7 +298,7 @@ hash_canonical_type (tree type) if (TREE_CODE (type) == ARRAY_TYPE || TREE_CODE (type) == COMPLEX_TYPE || TREE_CODE (type) == VECTOR_TYPE) - iterative_hash_canonical_type (TREE_TYPE (type), hstate); + iterative_hash_canonical_type (TREE_TYPE (type), hstate, insert); /* Incorporate function return and argument types. */ if (TREE_CODE (type) == FUNCTION_TYPE || TREE_CODE (type) == METHOD_TYPE) @@ -301,11 +306,11 @@ hash_canonical_type (tree type) unsigned na; tree p; - iterative_hash_canonical_type (TREE_TYPE (type), hstate); + iterative_hash_canonical_type (TREE_TYPE (type), hstate, insert); for (p = TYPE_ARG_TYPES (type), na = 0; p; p = TREE_CHAIN (p)) { - iterative_hash_canonical_type (TREE_VALUE (p), hstate); + iterative_hash_canonical_type (TREE_VALUE (p), hstate, insert); na++; } @@ -322,7 +327,7 @@ hash_canonical_type (tree type) && (! DECL_SIZE (f) || ! integer_zerop (DECL_SIZE (f)))) { - iterative_hash_canonical_type (TREE_TYPE (f), hstate); + iterative_hash_canonical_type (TREE_TYPE (f), hstate, insert); nf++; } @@ -332,10 +337,11 @@ hash_canonical_type (tree type) return hstate.end(); } -/* Returning a hash value for gimple type TYPE combined with VAL. */ +/* Returning a hash value for gimple type TYPE combined with VAL. + If INSERT is true possibly insert TYPE to canonical type hash. */ static void -iterative_hash_canonical_type (tree type, inchash::hash &hstate) +iterative_hash_canonical_type (tree type, inchash::hash &hstate, bool insert) { hashval_t v; @@ -343,7 +349,7 @@ iterative_hash_canonical_type (tree type type = TYPE_MAIN_VARIANT (type); if (!canonical_type_used_p (type)) - v = hash_canonical_type (type); + v = hash_canonical_type (type, insert); /* An already processed type. */ else if (TYPE_CANONICAL (type)) { @@ -355,9 +361,11 @@ iterative_hash_canonical_type (tree type /* Canonical types should not be able to form SCCs by design, this recursion is just because we do not register canonical types in optimal order. To avoid quadratic behavior also register the - type here. */ - v = hash_canonical_type (type); - gimple_register_canonical_type_1 (type, v); + type here. Do not assign canonical types to ODR types - this + is done later using ODR name hash. */ + v = hash_canonical_type (type, insert); + if (insert) + gimple_register_canonical_type_1 (type, v); } hstate.add_int (v); } @@ -437,12 +445,26 @@ gimple_register_canonical_type (tree t) TYPE_CANONICAL (t) = TYPE_CANONICAL (TYPE_MAIN_VARIANT (t)); else { - hashval_t h = hash_canonical_type (TYPE_MAIN_VARIANT (t)); + hashval_t h = hash_canonical_type (TYPE_MAIN_VARIANT (t), true); gimple_register_canonical_type_1 (TYPE_MAIN_VARIANT (t), h); TYPE_CANONICAL (t) = TYPE_CANONICAL (TYPE_MAIN_VARIANT (t)); } } +/* See if structurally equivalent type to T is in the canonical type hash and + return it. Return NULL otherwise. + No changes to canonical hash are made during the lookup. */ + +static tree +lookup_canonical_type (tree t) +{ + hashval_t h = hash_canonical_type (TYPE_MAIN_VARIANT (t), false); + void **slot = htab_find_slot_with_hash (gimple_canonical_types, t, h, NO_INSERT); + if (!slot) + return NULL; + return (tree)(*slot); +} + /* Re-compute TYPE_CANONICAL for NODE and related types. */ static void @@ -464,6 +486,107 @@ lto_register_canonical_types (tree node, gimple_register_canonical_type (node); } +/* Finish canonical type calculation: after all units has been streamed in we + can check if given ODR type structurally conflicts with a non-ODR type. In + the first case we set type canonical according to the canonical type hash. + In the second case we use type names. */ + +static void +lto_register_canonical_types_for_odr_types () +{ + tree t; + unsigned int i; + + if (!types_to_register) + return; + + /* Be sure that no types derived from ODR types was + not inserted into the hash table. */ + if (flag_checking) + FOR_EACH_VEC_ELT (*types_to_register, i, t) + gcc_assert (!TYPE_CANONICAL (t)); + + FOR_EACH_VEC_ELT (*types_to_register, i, t) + if (odr_type_p (t) && !TYPE_CANONICAL (t)) + { + /* Punt on ODR violations - if there are structurally different + types of the same name we are better to not try too hard to + use TBAA. */ + if (odr_type_violation_reported_p (t)) + { + if (symtab->dump_file) + { + fprintf (symtab->dump_file, + "Disabling ODR TBAA because of ODR violation: "); + print_generic_expr (symtab->dump_file, t); + fprintf (symtab->dump_file, "\n"); + } + } + else + { + tree nonodr = type_in_anonymous_namespace_p (t) + ? NULL : lookup_canonical_type (t); + + /* If there is non-ODR type matching T, use its canonical + type. We can still propagate it to all variants of T + including incomplete ones. */ + if (nonodr) + { + gcc_checking_assert (!odr_type_p (nonodr)); + if (symtab->dump_file) + { + fprintf (symtab->dump_file, + "ODR and non-ODR type conflict: "); + print_generic_expr (symtab->dump_file, t); + fprintf (symtab->dump_file, " and "); + print_generic_expr (symtab->dump_file, nonodr); + fprintf (symtab->dump_file, "\n"); + } + set_type_canonical_for_odr_type (t, nonodr); + } + else + { + if (symtab->dump_file) + { + fprintf (symtab->dump_file, + "New canonical ODR type: "); + print_generic_expr (symtab->dump_file, t); + fprintf (symtab->dump_file, "\n"); + } + + tree prevail = prevailing_odr_type (t); + gcc_checking_assert (TYPE_CANONICAL (prevail) == NULL); + + /* Populate canonical type hash with type name. */ + bool existed = canonical_type_hash_cache->put + (prevail, + htab_hash_string + (IDENTIFIER_POINTER + (DECL_ASSEMBLER_NAME + (TYPE_NAME (prevail))))); + gcc_assert (!existed); + /* Set TYPE_CANONICAL for all variants and duplicates of T + including incompete ones. */ + set_type_canonical_for_odr_type (t, prevail); + /* And inform gimple_canonical_types_compatible_p that + it should rely on TYPE_CANONICAL compares only. */ + enable_odr_based_tbaa (t); + gcc_checking_assert (TYPE_CANONICAL (t) = prevail); + } + } + } + + /* Now compute canonical types for all ODR derived types. */ + FOR_EACH_VEC_ELT (*types_to_register, i, t) + if (!TYPE_CANONICAL (t)) + { + gimple_register_canonical_type (t); + /* We store only main variants; propagate info to all variants. */ + for (tree t2 = TYPE_NEXT_VARIANT (t); t2; t2 = TYPE_NEXT_VARIANT (t2)) + TYPE_CANONICAL (t2) = TYPE_CANONICAL (t); + } +} + /* Remember trees that contains references to declarations. */ vec *tree_with_vars; @@ -1655,6 +1778,33 @@ unify_scc (struct data_in *data_in, unsi } +/* TYPE is expected to be record or union. Figure out if it is an ODR + type or derived from it. This is intended to be used only from + stream in process and rely on fact that all types with TYPE_CANONICAL + set are not ODR derived. This reducts most of recursive lookups. */ + +static bool +odr_or_derived_type_p (tree type) +{ + if (TYPE_CANONICAL (type)) + return false; + if (odr_type_p (TYPE_MAIN_VARIANT (type)) + || (TYPE_CONTEXT (type) + && TYPE_P (TYPE_CONTEXT (type)) + && odr_type_p (TYPE_CONTEXT (type)))) + return true; + for (tree f = TYPE_FIELDS (type); f; f = TREE_CHAIN (f)) + { + tree t = TREE_TYPE (f); + while (TREE_CODE (t) == ARRAY_TYPE) + t = TREE_TYPE (t); + if (RECORD_OR_UNION_TYPE_P (t) + && odr_or_derived_type_p (t)) + return true; + } + return false; +} + /* Read all the symbols from buffer DATA, using descriptors in DECL_DATA. RESOLUTIONS is the set of symbols picked by the linker (read from the resolution file when the linker plugin is being used). */ @@ -1747,12 +1897,24 @@ lto_read_decls (struct lto_file_decl_dat num_prevailing_types++; lto_fixup_prevailing_type (t); - /* Compute the canonical type of all types. + /* Compute the canonical type of all non-ODR types. + Delay ODR types for the end of merging process - the canonical + type for those can be computed using the (unique) name however + we want to do this only if units in other languages do not + contain structurally equivalent type. + Because SCC components are streamed in random (hash) order we may have encountered the type before while registering type canonical of a derived type in the same SCC. */ if (!TYPE_CANONICAL (t)) - gimple_register_canonical_type (t); + { + if (!RECORD_OR_UNION_TYPE_P (t) + || !odr_or_derived_type_p (t)) + gimple_register_canonical_type (t); + else if (COMPLETE_TYPE_P (t) + && TYPE_MAIN_VARIANT (t) == t) + vec_safe_push (types_to_register, t); + } if (TYPE_MAIN_VARIANT (t) == t && odr_type_p (t)) register_odr_type (t); } @@ -2602,6 +2764,8 @@ read_cgraph_and_symbols (unsigned nfiles ggc_free(decl_data); real_file_decl_data = NULL; + lto_register_canonical_types_for_odr_types (); + if (resolution_file_name) fclose (resolution); Index: testsuite/g++.dg/lto/alias-2_0.C =================================================================== --- testsuite/g++.dg/lto/alias-2_0.C (nonexistent) +++ testsuite/g++.dg/lto/alias-2_0.C (working copy) @@ -0,0 +1,31 @@ +/* { dg-lto-do run } */ +/* { dg-lto-options { { -O2 -flto } } } */ + +/* With LTO we consider all pointers to incomplete types to be possibly + aliasing. This makes *bptr to alias with aptr. + For C++ ODR types we however can work out that they are actually + different. */ + +#include + +typedef int (*fnptr) (); + +__attribute__ ((used)) +struct a *aptr; + +__attribute__ ((used)) +struct b **bptr = (struct b**)&aptr; +extern void init (); +extern void inline_me_late (int); + + +int +main (int argc, char **argv) +{ + init (); + aptr = 0; + inline_me_late (argc); + if (!__builtin_constant_p (aptr == 0)) + __builtin_abort (); + return (size_t)aptr; +} Index: testsuite/g++.dg/lto/alias-2_1.C =================================================================== --- testsuite/g++.dg/lto/alias-2_1.C (nonexistent) +++ testsuite/g++.dg/lto/alias-2_1.C (working copy) @@ -0,0 +1,16 @@ +#include +struct a {int a;} a; +struct b {int b;} b; +extern struct b **bptr; +void +inline_me_late (int argc) +{ + if (argc == -1) + *bptr = (struct b *)(size_t)1; +} +void +init() +{ + a.a=1; + b.b=2; +} Index: tree.c =================================================================== --- tree.c (revision 271843) +++ tree.c (working copy) @@ -14083,6 +14083,7 @@ gimple_canonical_types_compatible_p (con gcc_assert (!trust_type_canonical || (type_with_alias_set_p (t1) && type_with_alias_set_p (t2))); + /* If the types have been previously registered and found equal they still are. */ @@ -14100,6 +14101,14 @@ gimple_canonical_types_compatible_p (con return TYPE_CANONICAL (t1) == TYPE_CANONICAL (t2); } + /* For types where we do ODR based TBAA the canonical type is always + set correctly, so we know that types are different if their + canonical types does not match. */ + if (trust_type_canonical + && (odr_type_p (t1) && odr_based_tbaa_p (t1)) + != (odr_type_p (t2) && odr_based_tbaa_p (t2))) + return false; + /* Can't be the same type if the types don't have the same code. */ enum tree_code code = tree_code_for_canonical_type_merging (TREE_CODE (t1)); if (code != tree_code_for_canonical_type_merging (TREE_CODE (t2)))