From patchwork Tue May 2 13:50:03 2017 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Nathan Sidwell X-Patchwork-Id: 757614 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 3wHN331B9Nz9s7B for ; Tue, 2 May 2017 23:50:20 +1000 (AEST) Authentication-Results: ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.b="syJ7szc6"; 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:to :from:subject:message-id:date:mime-version:content-type; q=dns; s=default; b=JuaJ7XG/vscPINTjrEbfD1uH2A4Pz/Gkm9nfkmIsRvuHF62vDP rHSgVuVg/gaGhsDLU5jgwJ/RtxW6eyHe0W3skCqgin3rE5PKy9EpAu+QSPFdNuxz PCyG8+B8mAPw+5tKPIeEtORCBemEGQm6AjYcOMqsUVFTr2saWT3pVzJNY= 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:to :from:subject:message-id:date:mime-version:content-type; s= default; bh=H9g90e4s/3geVlvLqx3eOwCPRvc=; b=syJ7szc6MGf0/Y2V2g5q WckcPxPy1Q18c090hyNzMZMS7oFqVHAPZb3HP9MwvOQ8y7ESZ0eHtwt5ley6visZ ITrQBN04lHuaDoz+5HQJiX17Y7C2iBQxtA6PkoMFCA+vqq9vKL4IPGNtkZAFJcX+ 6nQ/B/q7HByaeUfUZ4XCdgg= Received: (qmail 104764 invoked by alias); 2 May 2017 13:50:07 -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 104741 invoked by uid 89); 2 May 2017 13:50:07 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-10.6 required=5.0 tests=BAYES_00, FREEMAIL_FROM, GIT_PATCH_2, GIT_PATCH_3, KAM_ASCII_DIVIDERS, RCVD_IN_DNSWL_NONE, RCVD_IN_SORBS_SPAM, SPF_PASS autolearn=ham version=3.3.2 spammy=adequate, hiding, H*RU:200, Hx-spam-relays-external:200 X-HELO: mail-yb0-f178.google.com Received: from mail-yb0-f178.google.com (HELO mail-yb0-f178.google.com) (209.85.213.178) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Tue, 02 May 2017 13:50:04 +0000 Received: by mail-yb0-f178.google.com with SMTP id j17so8305263ybj.0 for ; Tue, 02 May 2017 06:50:06 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:sender:to:from:subject:message-id:date :user-agent:mime-version:content-language; bh=PVY7sIyPGBqfgN7m9d7ImAPorMnYkmcfY/4QrYwA9l8=; b=Tiweuk1MwN4TmWKfkT0SvHEE72yjbxsqOtmxrBgHnAW9d1cxa+sKW5sBGcEPrqLvZz 72xPv7TeHZyBLbPqQdypkuRF2/qSlWo9penZd2gvBnCVmtvgAs0JPt0U0b9/TTUQn/RY ALe/ehv0J2dGEPOUrCbM4hFKs5h5afchFWVkhCkJ++v9eJb9J5llATHkt0zZFui7ZJNx jQB0o49yyHHBA/eFW5wXC90qgE2B4APFVJMVMw66GaN258efpNeEsYwc9+D6bbi9b0Kz CM6c6cufe3ei820u04gGFaPMV0ZxZ8ymnB/15yVFj821lhGYLbYzoT0izwVWhzxzCDuh do+w== X-Gm-Message-State: AN3rC/5ly5yGnN5DZWsXTPTdE2jjh0OUiEYAxvFx5R8nT8nJ32DIfHik c/K3U3VbD8q5OQ== X-Received: by 10.37.196.69 with SMTP id u66mr25277897ybf.11.1493733005197; Tue, 02 May 2017 06:50:05 -0700 (PDT) Received: from ?IPv6:2620:10d:c0a3:20fb:f6d0:5ac5:64cd:f102? ([2620:10d:c091:200::6:c2a4]) by smtp.googlemail.com with ESMTPSA id b204sm7649476ywh.36.2017.05.02.06.50.04 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Tue, 02 May 2017 06:50:04 -0700 (PDT) To: GCC Patches From: Nathan Sidwell Subject: [PATCH] canonical type hashing Message-ID: <8086ef34-79d4-1fff-8f89-bd4b2444473b@acm.org> Date: Tue, 2 May 2017 09:50:03 -0400 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:52.0) Gecko/20100101 Thunderbird/52.0 MIME-Version: 1.0 On the modules branch, I need rematerialize canonical types and the like from a read-in serialized tree. I discovered the canonical-type hash table is fed a bespoke hash value by each type creator. There was no generic type hasher :( The rationale appears to allow each type constuctor to just specialize its needs. Excitingly, a generic type hasher is hiding inside build_type_attribute_qual_variant. So I broke it out of there and generalized it a bit more. The type hashers had diverged from the attribute-variant hasher. This is not an error, because the attribute variant version was creating variants with non-null attributes, so guaranteed different But it was confusing. This generic hasher is slightly different to the bespoke hashers in a few places. One place of note was the vector type hasher, which mixed {elt-type, num-elts, vector-mode}, but vector-mode is entirely determined by the first two object, so mixing it in doesn't add any entropy. I dropped the mode. I still kept generating the hashvalue separate to the type_hash_canon call itself. Perhaps a future patch could change that, but I didn't want to much churn in this patch. I've included Jakub's recent TYPE_TYPELESS_STORAGE changes. (And notice that the attribute-type hasher wasn't dealing with it.) booted and tested on x86_64-linux-gnu, ok? nathan 2017-05-02 Nathan Sidwell Canonicalize canonical type hashing gcc/ * tree.h (type_hash_default): Declare. * tree.c (type_hash_list, attribute_hash_list): Move into type_hash_default. (build_type_attribute_qual_variant): Break out hash code calc into type_hash_default. (type_hash_default): New. Generic type hash computation. (build_range_type_1, build_array_type_1, build_function_type, build_method_type_directly, build_offset_type, build_complex_type, make_vector_type): Call it. gcc/c-family/ * c-common.c (complete_array_type): Use type_hash_default. Index: c-family/c-common.c =================================================================== --- c-family/c-common.c (revision 247485) +++ c-family/c-common.c (working copy) @@ -6368,12 +6368,8 @@ complete_array_type (tree *ptype, tree i layout_type (main_type); /* Make sure we have the canonical MAIN_TYPE. */ - inchash::hash hstate; - hstate.add_object (TYPE_HASH (unqual_elt)); - hstate.add_object (TYPE_HASH (TYPE_DOMAIN (main_type))); - if (!AGGREGATE_TYPE_P (unqual_elt)) - hstate.add_flag (TYPE_TYPELESS_STORAGE (main_type)); - main_type = type_hash_canon (hstate.end (), main_type); + hashval_t hashcode = type_hash_default (main_type); + main_type = type_hash_canon (hashcode, main_type); /* Fix the canonical type. */ if (TYPE_STRUCTURAL_EQUALITY_P (TREE_TYPE (main_type)) Index: tree.c =================================================================== --- tree.c (revision 247485) +++ tree.c (working copy) @@ -248,8 +248,6 @@ static void set_type_quals (tree, int); static void print_type_hash_statistics (void); static void print_debug_expr_statistics (void); static void print_value_expr_statistics (void); -static void type_hash_list (const_tree, inchash::hash &); -static void attribute_hash_list (const_tree, inchash::hash &); tree global_trees[TI_MAX]; tree integer_types[itk_none]; @@ -4828,11 +4826,7 @@ build_type_attribute_qual_variant (tree { if (! attribute_list_equal (TYPE_ATTRIBUTES (ttype), attribute)) { - inchash::hash hstate; tree ntype; - int i; - tree t; - enum tree_code code = TREE_CODE (ttype); /* Building a distinct copy of a tagged type is inappropriate; it causes breakage in code that expects there to be a one-to-one @@ -4856,37 +4850,8 @@ build_type_attribute_qual_variant (tree TYPE_ATTRIBUTES (ntype) = attribute; - hstate.add_int (code); - if (TREE_TYPE (ntype)) - hstate.add_object (TYPE_HASH (TREE_TYPE (ntype))); - attribute_hash_list (attribute, hstate); - - switch (TREE_CODE (ntype)) - { - case FUNCTION_TYPE: - type_hash_list (TYPE_ARG_TYPES (ntype), hstate); - break; - case ARRAY_TYPE: - if (TYPE_DOMAIN (ntype)) - hstate.add_object (TYPE_HASH (TYPE_DOMAIN (ntype))); - break; - case INTEGER_TYPE: - t = TYPE_MAX_VALUE (ntype); - for (i = 0; i < TREE_INT_CST_NUNITS (t); i++) - hstate.add_object (TREE_INT_CST_ELT (t, i)); - break; - case REAL_TYPE: - case FIXED_POINT_TYPE: - { - unsigned int precision = TYPE_PRECISION (ntype); - hstate.add_object (precision); - } - break; - default: - break; - } - - ntype = type_hash_canon (hstate.end(), ntype); + hashval_t hash = type_hash_default (ntype); + ntype = type_hash_canon (hash, ntype); /* If the target-dependent attributes make NTYPE different from its canonical type, we will need to use structural equality @@ -6994,18 +6959,80 @@ decl_debug_args_insert (tree from) /* Hashing of types so that we don't make duplicates. The entry point is `type_hash_canon'. */ -/* Compute a hash code for a list of types (chain of TREE_LIST nodes - with types in the TREE_VALUE slots), by adding the hash codes - of the individual types. */ +/* Generate the default hash code for TYPE. This is designed for + speed, rather than maximum entropy. */ -static void -type_hash_list (const_tree list, inchash::hash &hstate) +hashval_t +type_hash_default (tree type) { - const_tree tail; + inchash::hash hstate; + + hstate.add_int (TREE_CODE (type)); + + if (TREE_TYPE (type)) + hstate.add_object (TYPE_HASH (TREE_TYPE (type))); + + for (tree t = TYPE_ATTRIBUTES (type); t; t = TREE_CHAIN (t)) + /* Just the identifier is adequate to distinguish. */ + hstate.add_object (IDENTIFIER_HASH_VALUE (get_attribute_name (t))); + + switch (TREE_CODE (type)) + { + case METHOD_TYPE: + hstate.add_object (TYPE_HASH (TYPE_METHOD_BASETYPE (type))); + /* FALLTHROUGH. */ + case FUNCTION_TYPE: + for (tree t = TYPE_ARG_TYPES (type); t; t = TREE_CHAIN (t)) + if (TREE_VALUE (t) != error_mark_node) + hstate.add_object (TYPE_HASH (TREE_VALUE (t))); + break; + + case OFFSET_TYPE: + hstate.add_object (TYPE_HASH (TYPE_OFFSET_BASETYPE (type))); + break; + + case ARRAY_TYPE: + { + if (TYPE_DOMAIN (type)) + hstate.add_object (TYPE_HASH (TYPE_DOMAIN (type))); + if (!AGGREGATE_TYPE_P (TREE_TYPE (type))) + { + unsigned typeless = TYPE_TYPELESS_STORAGE (type); + hstate.add_object (typeless); + } + } + break; - for (tail = list; tail; tail = TREE_CHAIN (tail)) - if (TREE_VALUE (tail) != error_mark_node) - hstate.add_object (TYPE_HASH (TREE_VALUE (tail))); + case INTEGER_TYPE: + { + tree t = TYPE_MAX_VALUE (type); + if (!t) + t = TYPE_MIN_VALUE (type); + for (int i = 0; i < TREE_INT_CST_NUNITS (t); i++) + hstate.add_object (TREE_INT_CST_ELT (t, i)); + break; + } + + case REAL_TYPE: + case FIXED_POINT_TYPE: + { + unsigned prec = TYPE_PRECISION (type); + hstate.add_object (prec); + break; + } + + case VECTOR_TYPE: + { + unsigned nunits = TYPE_VECTOR_SUBPARTS (type); + hstate.add_object (nunits); + break; + } + + default: + break; + } + + return hstate.end (); } /* These are the Hashtable callback functions. */ @@ -7186,20 +7213,6 @@ print_type_hash_statistics (void) type_hash_table->collisions ()); } -/* Compute a hash code for a list of attributes (chain of TREE_LIST nodes - with names in the TREE_PURPOSE slots and args in the TREE_VALUE slots), - by adding the hash codes of the individual attributes. */ - -static void -attribute_hash_list (const_tree list, inchash::hash &hstate) -{ - const_tree tail; - - for (tail = list; tail; tail = TREE_CHAIN (tail)) - /* ??? Do we want to add in TREE_VALUE too? */ - hstate.add_object (IDENTIFIER_HASH_VALUE (get_attribute_name (tail))); -} - /* Given two lists of attributes, return true if list l2 is equivalent to l1. */ @@ -8264,7 +8277,6 @@ static tree build_range_type_1 (tree type, tree lowval, tree highval, bool shared) { tree itype = make_node (INTEGER_TYPE); - inchash::hash hstate; TREE_TYPE (itype) = type; @@ -8292,10 +8304,8 @@ build_range_type_1 (tree type, tree lowv return itype; } - inchash::add_expr (TYPE_MIN_VALUE (itype), hstate); - inchash::add_expr (TYPE_MAX_VALUE (itype), hstate); - hstate.merge_hash (TYPE_HASH (type)); - itype = type_hash_canon (hstate.end (), itype); + hashval_t hash = type_hash_default (itype); + itype = type_hash_canon (hash, itype); return itype; } @@ -8403,13 +8413,8 @@ build_array_type_1 (tree elt_type, tree if (shared) { - inchash::hash hstate; - hstate.add_object (TYPE_HASH (elt_type)); - if (index_type) - hstate.add_object (TYPE_HASH (index_type)); - if (!AGGREGATE_TYPE_P (elt_type)) - hstate.add_flag (TYPE_TYPELESS_STORAGE (t)); - t = type_hash_canon (hstate.end (), t); + hashval_t hash = type_hash_default (t); + t = type_hash_canon (hash, t); } if (TYPE_CANONICAL (t) == t) @@ -8566,9 +8571,8 @@ build_function_type (tree value_type, tr TYPE_ARG_TYPES (t) = arg_types; /* If we already have such a type, use the old one. */ - hstate.add_object (TYPE_HASH (value_type)); - type_hash_list (arg_types, hstate); - t = type_hash_canon (hstate.end (), t); + hashval_t hash = type_hash_default (t); + t = type_hash_canon (hash, t); /* Set up the canonical type. */ any_structural_p = TYPE_STRUCTURAL_EQUALITY_P (value_type); @@ -8705,7 +8709,6 @@ build_method_type_directly (tree basetyp { tree t; tree ptype; - inchash::hash hstate; bool any_structural_p, any_noncanonical_p; tree canon_argtypes; @@ -8722,10 +8725,8 @@ build_method_type_directly (tree basetyp TYPE_ARG_TYPES (t) = argtypes; /* If we already have such a type, use the old one. */ - hstate.add_object (TYPE_HASH (basetype)); - hstate.add_object (TYPE_HASH (rettype)); - type_hash_list (argtypes, hstate); - t = type_hash_canon (hstate.end (), t); + hashval_t hash = type_hash_default (t); + t = type_hash_canon (hash, t); /* Set up the canonical type. */ any_structural_p @@ -8773,7 +8774,6 @@ tree build_offset_type (tree basetype, tree type) { tree t; - inchash::hash hstate; /* Make a node of the sort we want. */ t = make_node (OFFSET_TYPE); @@ -8782,9 +8782,8 @@ build_offset_type (tree basetype, tree t TREE_TYPE (t) = type; /* If we already have such a type, use the old one. */ - hstate.add_object (TYPE_HASH (basetype)); - hstate.add_object (TYPE_HASH (type)); - t = type_hash_canon (hstate.end (), t); + hashval_t hash = type_hash_default (t); + t = type_hash_canon (hash, t); if (!COMPLETE_TYPE_P (t)) layout_type (t); @@ -8815,7 +8814,6 @@ tree build_complex_type (tree component_type, bool named) { tree t; - inchash::hash hstate; gcc_assert (INTEGRAL_TYPE_P (component_type) || SCALAR_FLOAT_TYPE_P (component_type) @@ -8827,8 +8825,8 @@ build_complex_type (tree component_type, TREE_TYPE (t) = TYPE_MAIN_VARIANT (component_type); /* If we already have such a type, use the old one. */ - hstate.add_object (TYPE_HASH (component_type)); - t = type_hash_canon (hstate.end (), t); + hashval_t hash = type_hash_default (t); + t = type_hash_canon (hash, t); if (!COMPLETE_TYPE_P (t)) layout_type (t); @@ -10083,7 +10081,6 @@ static tree make_vector_type (tree innertype, int nunits, machine_mode mode) { tree t; - inchash::hash hstate; tree mv_innertype = TYPE_MAIN_VARIANT (innertype); t = make_node (VECTOR_TYPE); @@ -10101,11 +10098,8 @@ make_vector_type (tree innertype, int nu layout_type (t); - hstate.add_wide_int (VECTOR_TYPE); - hstate.add_wide_int (nunits); - hstate.add_wide_int (mode); - hstate.add_object (TYPE_HASH (TREE_TYPE (t))); - t = type_hash_canon (hstate.end (), t); + hashval_t hash = type_hash_default (t); + t = type_hash_canon (hash, t); /* We have built a main variant, based on the main variant of the inner type. Use it to build the variant we return. */ Index: tree.h =================================================================== --- tree.h (revision 247485) +++ tree.h (working copy) @@ -4303,6 +4303,7 @@ extern tree build_variant_type_copy (tre How the hash code is computed is up to the caller, as long as any two callers that could hash identical-looking type nodes agree. */ +extern hashval_t type_hash_default (tree); extern tree type_hash_canon (unsigned int, tree); extern tree convert (tree, tree);