From patchwork Sun Nov 8 20:46:18 2015 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jan Hubicka X-Patchwork-Id: 541491 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org 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 E88531402D0 for ; Mon, 9 Nov 2015 07:46:33 +1100 (AEDT) Authentication-Results: ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.b=w98SnM8V; dkim-atps=neutral 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=X1o/QfZgT0xI5KOwk73vV7rsW8sbEsoOrv/StJWNxl8JVmV0S5Uig ScOtusFbVe5zXTR9JYXSLAkuGw5STF4t3LiU594r+ZgKN8gY1KRhNmPd/UIp6enr tPwnOQYbEfDP5XhXn7affbUXudfq1lV1IQ+vMVlQTBFAPfszZ55FBE= 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=cs8IUsKB8CYuq1FstDvusYpMNhI=; b=w98SnM8V4DFV8z8I/wtj EP2xdJhqRfMemEdfaGc8JcYCfL0Gm4o79huILumHsWU+lkUB05Y1nOYg4vhzu/pC uEbNVISENKiUzsoUpJtr+GNoDnBgpCh0DbAFdBg6xqqTm+zwhe+w/jseCky+R6Hn 5bCM7r+Qv/R4sWLLIqgby+0= Received: (qmail 90346 invoked by alias); 8 Nov 2015 20:46:25 -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 90324 invoked by uid 89); 8 Nov 2015 20:46:24 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=0.5 required=5.0 tests=AWL, BAYES_50, KAM_ASCII_DIVIDERS, KAM_LAZY_DOMAIN_SECURITY, T_RP_MATCHES_RCVD autolearn=no version=3.3.2 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 (AES256-GCM-SHA384 encrypted) ESMTPS; Sun, 08 Nov 2015 20:46:22 +0000 Received: by nikam.ms.mff.cuni.cz (Postfix, from userid 16202) id D0D735411CE; Sun, 8 Nov 2015 21:46:18 +0100 (CET) Date: Sun, 8 Nov 2015 21:46:18 +0100 From: Jan Hubicka To: gcc-patches@gcc.gnu.org, rguenther@suse.de Subject: Enable pointer TBAA for LTO Message-ID: <20151108204618.GA68715@kam.mff.cuni.cz> MIME-Version: 1.0 Content-Disposition: inline User-Agent: Mutt/1.5.21 (2010-09-15) 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 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