From patchwork Fri Jul 25 00:11:43 2014 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Andi Kleen X-Patchwork-Id: 373561 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 1188F1401A9 for ; Fri, 25 Jul 2014 10:13:43 +1000 (EST) DomainKey-Signature: a=rsa-sha1; c=nofws; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender:from :to:cc:subject:date:message-id:in-reply-to:references; q=dns; s= default; b=BOormlKuC2cUpTkx1y7z2Ggph+2nwvHkCMM70j7m5aLngwWTvDfUC NiRX98+n79iXVHKr7RttWm2qGd5fFquv3IW355b8sIh2dEO0T61Wq8MYzYYDtBcE 7jx9JiQ8Z/0QYz5/R4NTWvQahhYmD+4IIJzgHHulMUxP/E9A6wLx2o= 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:from :to:cc:subject:date:message-id:in-reply-to:references; s= default; bh=dMipugcp/BPZPV7i/7/JNfCOs6c=; b=eklL4NDZM40SaXhAXW0s lEPvSr18K2xBMwFdjzD1syKhgSJhXceqBImonPFbZP2L5QEAEH0iNind2bmYQX1F CpvSe0nEmnUAXqtF1uPd2cK6vbMJwzsQtM6beVh6JArwq9jXmHBMDX8M0R55OqsC pLqxNjO2W/ZTvtyiWENjSW0= Received: (qmail 32199 invoked by alias); 25 Jul 2014 00:12:47 -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 32088 invoked by uid 89); 25 Jul 2014 00:12:46 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-1.9 required=5.0 tests=AWL, BAYES_00, RP_MATCHES_RCVD autolearn=ham version=3.3.2 X-HELO: mga02.intel.com Received: from mga02.intel.com (HELO mga02.intel.com) (134.134.136.20) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Fri, 25 Jul 2014 00:12:43 +0000 Received: from orsmga001.jf.intel.com ([10.7.209.18]) by orsmga101.jf.intel.com with ESMTP; 24 Jul 2014 17:12:37 -0700 X-ExtLoop1: 1 Received: from laut.jf.intel.com (HELO localhost) ([10.23.232.55]) by orsmga001.jf.intel.com with ESMTP; 24 Jul 2014 17:12:37 -0700 Received: by localhost (Postfix, from userid 1000) id 0F9A3124AB5; Fri, 25 Jul 2014 02:11:48 +0200 (CEST) From: Andi Kleen To: gcc-patches@gcc.gnu.org Cc: Andi Kleen Subject: [PATCH 3/4] Convert the tree.c type hashing over to inchash Date: Fri, 25 Jul 2014 02:11:43 +0200 Message-Id: <1406247104-2889-4-git-send-email-andi@firstfloor.org> In-Reply-To: <1406247104-2889-1-git-send-email-andi@firstfloor.org> References: <1406247104-2889-1-git-send-email-andi@firstfloor.org> From: Andi Kleen v2: Use commutative interface. Be much nearer to the old code. gcc/: 2014-07-24 Andi Kleen * tree.c (build_type_attribute_qual_variant): Use inchash. (type_hash_list): Dito. (attribute_hash_list): Dito (iterative_hstate_expr): Dito. (iterative_hash_expr): Dito. (build_range_type_1): Dito. (build_array_type_1): Dito. (build_function_type): Dito. (build_method_type_directly): Dito. (build_offset_type): Dito. (build_complex_type): Dito. (make_vector_type): Dito. * tree.h (iterative_hash_expr): Add compat wrapper. (iterative_hstate_expr): Add. lto/: 2014-07-24 Andi Kleen * lto.c (hash_canonical_type): Call iterative_hstate_expr. --- gcc/lto/lto.c | 6 +- gcc/tree.c | 182 ++++++++++++++++++++++++++++------------------------------ gcc/tree.h | 13 ++++- 3 files changed, 102 insertions(+), 99 deletions(-) diff --git a/gcc/lto/lto.c b/gcc/lto/lto.c index 48fb78e..40bf2ea 100644 --- a/gcc/lto/lto.c +++ b/gcc/lto/lto.c @@ -327,11 +327,9 @@ hash_canonical_type (tree type) /* OMP lowering can introduce error_mark_node in place of random local decls in types. */ if (TYPE_MIN_VALUE (TYPE_DOMAIN (type)) != error_mark_node) - hstate.add_int (iterative_hash_expr (TYPE_MIN_VALUE ( - TYPE_DOMAIN (type)), 0)); + iterative_hstate_expr (TYPE_MIN_VALUE (TYPE_DOMAIN (type)), hstate); if (TYPE_MAX_VALUE (TYPE_DOMAIN (type)) != error_mark_node) - hstate.add_int (iterative_hash_expr (TYPE_MAX_VALUE ( - TYPE_DOMAIN (type)), 0)); + iterative_hstate_expr (TYPE_MAX_VALUE (TYPE_DOMAIN (type)), hstate); } /* Recurse for aggregates with a single element type. */ diff --git a/gcc/tree.c b/gcc/tree.c index e555546..e2b43bf 100644 --- a/gcc/tree.c +++ b/gcc/tree.c @@ -231,8 +231,8 @@ static void print_type_hash_statistics (void); static void print_debug_expr_statistics (void); static void print_value_expr_statistics (void); static int type_hash_marked_p (const void *); -static unsigned int type_hash_list (const_tree, hashval_t); -static unsigned int attribute_hash_list (const_tree, hashval_t); +static void type_hash_list (const_tree, inchash &); +static void attribute_hash_list (const_tree, inchash &); tree global_trees[TI_MAX]; tree integer_types[itk_none]; @@ -4593,7 +4593,7 @@ build_type_attribute_qual_variant (tree ttype, tree attribute, int quals) { if (! attribute_list_equal (TYPE_ATTRIBUTES (ttype), attribute)) { - hashval_t hashcode = 0; + inchash hstate; tree ntype; int i; tree t; @@ -4621,39 +4621,37 @@ build_type_attribute_qual_variant (tree ttype, tree attribute, int quals) TYPE_ATTRIBUTES (ntype) = attribute; - hashcode = iterative_hash_object (code, hashcode); + hstate.add_int (code); if (TREE_TYPE (ntype)) - hashcode = iterative_hash_object (TYPE_HASH (TREE_TYPE (ntype)), - hashcode); - hashcode = attribute_hash_list (attribute, hashcode); + hstate.add_object (TYPE_HASH (TREE_TYPE (ntype))); + attribute_hash_list (attribute, hstate); switch (TREE_CODE (ntype)) { case FUNCTION_TYPE: - hashcode = type_hash_list (TYPE_ARG_TYPES (ntype), hashcode); + type_hash_list (TYPE_ARG_TYPES (ntype), hstate); break; case ARRAY_TYPE: if (TYPE_DOMAIN (ntype)) - hashcode = iterative_hash_object (TYPE_HASH (TYPE_DOMAIN (ntype)), - hashcode); + 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++) - hashcode = iterative_hash_object (TREE_INT_CST_ELT (t, i), hashcode); + hstate.add_object (TREE_INT_CST_ELT (t, i)); break; case REAL_TYPE: case FIXED_POINT_TYPE: { unsigned int precision = TYPE_PRECISION (ntype); - hashcode = iterative_hash_object (precision, hashcode); + hstate.add_object (precision); } break; default: break; } - ntype = type_hash_canon (hashcode, ntype); + ntype = type_hash_canon (hstate.end(), ntype); /* If the target-dependent attributes make NTYPE different from its canonical type, we will need to use structural equality @@ -6632,17 +6630,14 @@ decl_debug_args_insert (tree from) with types in the TREE_VALUE slots), by adding the hash codes of the individual types. */ -static unsigned int -type_hash_list (const_tree list, hashval_t hashcode) +static void +type_hash_list (const_tree list, inchash &hstate) { const_tree tail; for (tail = list; tail; tail = TREE_CHAIN (tail)) if (TREE_VALUE (tail) != error_mark_node) - hashcode = iterative_hash_object (TYPE_HASH (TREE_VALUE (tail)), - hashcode); - - return hashcode; + hstate.add_object (TYPE_HASH (TREE_VALUE (tail))); } /* These are the Hashtable callback functions. */ @@ -6870,16 +6865,14 @@ print_type_hash_statistics (void) with names in the TREE_PURPOSE slots and args in the TREE_VALUE slots), by adding the hash codes of the individual attributes. */ -static unsigned int -attribute_hash_list (const_tree list, hashval_t hashcode) +static void +attribute_hash_list (const_tree list, inchash &hstate) { const_tree tail; for (tail = list; tail; tail = TREE_CHAIN (tail)) /* ??? Do we want to add in TREE_VALUE too? */ - hashcode = iterative_hash_object - (IDENTIFIER_HASH_VALUE (get_attribute_name (tail)), hashcode); - return hashcode; + hstate.add_object (IDENTIFIER_HASH_VALUE (get_attribute_name (tail))); } /* Given two lists of attributes, return true if list l2 is @@ -7392,20 +7385,22 @@ commutative_ternary_tree_code (enum tree_code code) } /* Generate a hash value for an expression. This can be used iteratively - by passing a previous result as the VAL argument. + by passing a previous result as the HSTATE argument. This function is intended to produce the same hash for expressions which would compare equal using operand_equal_p. */ - -hashval_t -iterative_hash_expr (const_tree t, hashval_t val) +void +iterative_hstate_expr (const_tree t, inchash &hstate) { int i; enum tree_code code; enum tree_code_class tclass; if (t == NULL_TREE) - return iterative_hash_hashval_t (0, val); + { + hstate.merge_hash (0); + return; + } code = TREE_CODE (t); @@ -7414,58 +7409,61 @@ iterative_hash_expr (const_tree t, hashval_t val) /* Alas, constants aren't shared, so we can't rely on pointer identity. */ case VOID_CST: - return iterative_hash_hashval_t (0, val); + hstate.merge_hash (0); + return; case INTEGER_CST: for (i = 0; i < TREE_INT_CST_NUNITS (t); i++) - val = iterative_hash_host_wide_int (TREE_INT_CST_ELT (t, i), val); - return val; + hstate.add_wide_int (TREE_INT_CST_ELT (t, i)); + return; case REAL_CST: { unsigned int val2 = real_hash (TREE_REAL_CST_PTR (t)); - - return iterative_hash_hashval_t (val2, val); + hstate.merge_hash (val2); + return; } case FIXED_CST: { unsigned int val2 = fixed_hash (TREE_FIXED_CST_PTR (t)); - - return iterative_hash_hashval_t (val2, val); + hstate.merge_hash (val2); + return; } case STRING_CST: - return iterative_hash (TREE_STRING_POINTER (t), - TREE_STRING_LENGTH (t), val); + hstate.add ((const void *) TREE_STRING_POINTER (t), TREE_STRING_LENGTH (t)); + return; case COMPLEX_CST: - val = iterative_hash_expr (TREE_REALPART (t), val); - return iterative_hash_expr (TREE_IMAGPART (t), val); + iterative_hstate_expr (TREE_REALPART (t), hstate); + iterative_hstate_expr (TREE_IMAGPART (t), hstate); + return; case VECTOR_CST: { unsigned i; for (i = 0; i < VECTOR_CST_NELTS (t); ++i) - val = iterative_hash_expr (VECTOR_CST_ELT (t, i), val); - return val; + iterative_hstate_expr (VECTOR_CST_ELT (t, i), hstate); + return; } case SSA_NAME: /* We can just compare by pointer. */ - return iterative_hash_host_wide_int (SSA_NAME_VERSION (t), val); + hstate.add_wide_int (SSA_NAME_VERSION (t)); + return; case PLACEHOLDER_EXPR: /* The node itself doesn't matter. */ - return val; + return; case TREE_LIST: /* A list of expressions, for a CALL_EXPR or as the elements of a VECTOR_CST. */ for (; t; t = TREE_CHAIN (t)) - val = iterative_hash_expr (TREE_VALUE (t), val); - return val; + iterative_hstate_expr (TREE_VALUE (t), hstate); + return; case CONSTRUCTOR: { unsigned HOST_WIDE_INT idx; tree field, value; FOR_EACH_CONSTRUCTOR_ELT (CONSTRUCTOR_ELTS (t), idx, field, value) { - val = iterative_hash_expr (field, val); - val = iterative_hash_expr (value, val); + iterative_hstate_expr (field, hstate); + iterative_hstate_expr (value, hstate); } - return val; + return; } case FUNCTION_DECL: /* When referring to a built-in FUNCTION_DECL, use the __builtin__ form. @@ -7486,13 +7484,13 @@ iterative_hash_expr (const_tree t, hashval_t val) if (tclass == tcc_declaration) { /* DECL's have a unique ID */ - val = iterative_hash_host_wide_int (DECL_UID (t), val); + hstate.add_wide_int (DECL_UID (t)); } else { gcc_assert (IS_EXPR_CODE_CLASS (tclass)); - val = iterative_hash_object (code, val); + hstate.add_object (code); /* Don't hash the type, that can lead to having nodes which compare equal according to operand_equal_p, but which @@ -7501,8 +7499,8 @@ iterative_hash_expr (const_tree t, hashval_t val) || code == NON_LVALUE_EXPR) { /* Make sure to include signness in the hash computation. */ - val += TYPE_UNSIGNED (TREE_TYPE (t)); - val = iterative_hash_expr (TREE_OPERAND (t, 0), val); + hstate.add_int (TYPE_UNSIGNED (TREE_TYPE (t))); + iterative_hstate_expr (TREE_OPERAND (t, 0), hstate); } else if (commutative_tree_code (code)) @@ -7511,21 +7509,16 @@ iterative_hash_expr (const_tree t, hashval_t val) however it appears. We do this by first hashing both operands and then rehashing based on the order of their independent hashes. */ - hashval_t one = iterative_hash_expr (TREE_OPERAND (t, 0), 0); - hashval_t two = iterative_hash_expr (TREE_OPERAND (t, 1), 0); - hashval_t t; - - if (one > two) - t = one, one = two, two = t; - - val = iterative_hash_hashval_t (one, val); - val = iterative_hash_hashval_t (two, val); + inchash one, two; + iterative_hstate_expr (TREE_OPERAND (t, 0), one); + iterative_hstate_expr (TREE_OPERAND (t, 1), two); + hstate.add_commutative (one, two); } else for (i = TREE_OPERAND_LENGTH (t) - 1; i >= 0; --i) - val = iterative_hash_expr (TREE_OPERAND (t, i), val); + iterative_hstate_expr (TREE_OPERAND (t, i), hstate); } - return val; + return; } } @@ -7718,7 +7711,7 @@ static tree build_range_type_1 (tree type, tree lowval, tree highval, bool shared) { tree itype = make_node (INTEGER_TYPE); - hashval_t hashcode = 0; + inchash hstate; TREE_TYPE (itype) = type; @@ -7746,10 +7739,10 @@ build_range_type_1 (tree type, tree lowval, tree highval, bool shared) return itype; } - hashcode = iterative_hash_expr (TYPE_MIN_VALUE (itype), hashcode); - hashcode = iterative_hash_expr (TYPE_MAX_VALUE (itype), hashcode); - hashcode = iterative_hash_hashval_t (TYPE_HASH (type), hashcode); - itype = type_hash_canon (hashcode, itype); + iterative_hstate_expr (TYPE_MIN_VALUE (itype), hstate); + iterative_hstate_expr (TYPE_MAX_VALUE (itype), hstate); + hstate.merge_hash (TYPE_HASH (type)); + itype = type_hash_canon (hstate.end (), itype); return itype; } @@ -7854,10 +7847,11 @@ build_array_type_1 (tree elt_type, tree index_type, bool shared) if (shared) { - hashval_t hashcode = iterative_hash_object (TYPE_HASH (elt_type), 0); + inchash hstate; + hstate.add_object (TYPE_HASH (elt_type)); if (index_type) - hashcode = iterative_hash_object (TYPE_HASH (index_type), hashcode); - t = type_hash_canon (hashcode, t); + hstate.add_object (TYPE_HASH (index_type)); + t = type_hash_canon (hstate.end (), t); } if (TYPE_CANONICAL (t) == t) @@ -7997,7 +7991,7 @@ tree build_function_type (tree value_type, tree arg_types) { tree t; - hashval_t hashcode = 0; + inchash hstate; bool any_structural_p, any_noncanonical_p; tree canon_argtypes; @@ -8013,9 +8007,9 @@ build_function_type (tree value_type, tree arg_types) TYPE_ARG_TYPES (t) = arg_types; /* If we already have such a type, use the old one. */ - hashcode = iterative_hash_object (TYPE_HASH (value_type), hashcode); - hashcode = type_hash_list (arg_types, hashcode); - t = type_hash_canon (hashcode, t); + hstate.add_object (TYPE_HASH (value_type)); + type_hash_list (arg_types, hstate); + t = type_hash_canon (hstate.end (), t); /* Set up the canonical type. */ any_structural_p = TYPE_STRUCTURAL_EQUALITY_P (value_type); @@ -8152,7 +8146,7 @@ build_method_type_directly (tree basetype, { tree t; tree ptype; - int hashcode = 0; + inchash hstate; bool any_structural_p, any_noncanonical_p; tree canon_argtypes; @@ -8169,10 +8163,10 @@ build_method_type_directly (tree basetype, TYPE_ARG_TYPES (t) = argtypes; /* If we already have such a type, use the old one. */ - hashcode = iterative_hash_object (TYPE_HASH (basetype), hashcode); - hashcode = iterative_hash_object (TYPE_HASH (rettype), hashcode); - hashcode = type_hash_list (argtypes, hashcode); - t = type_hash_canon (hashcode, t); + hstate.add_object (TYPE_HASH (basetype)); + hstate.add_object (TYPE_HASH (rettype)); + type_hash_list (argtypes, hstate); + t = type_hash_canon (hstate.end (), t); /* Set up the canonical type. */ any_structural_p @@ -8220,7 +8214,7 @@ tree build_offset_type (tree basetype, tree type) { tree t; - hashval_t hashcode = 0; + inchash hstate; /* Make a node of the sort we want. */ t = make_node (OFFSET_TYPE); @@ -8229,9 +8223,9 @@ build_offset_type (tree basetype, tree type) TREE_TYPE (t) = type; /* If we already have such a type, use the old one. */ - hashcode = iterative_hash_object (TYPE_HASH (basetype), hashcode); - hashcode = iterative_hash_object (TYPE_HASH (type), hashcode); - t = type_hash_canon (hashcode, t); + hstate.add_object (TYPE_HASH (basetype)); + hstate.add_object (TYPE_HASH (type)); + t = type_hash_canon (hstate.end (), t); if (!COMPLETE_TYPE_P (t)) layout_type (t); @@ -8257,7 +8251,7 @@ tree build_complex_type (tree component_type) { tree t; - hashval_t hashcode; + inchash hstate; gcc_assert (INTEGRAL_TYPE_P (component_type) || SCALAR_FLOAT_TYPE_P (component_type) @@ -8269,8 +8263,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. */ - hashcode = iterative_hash_object (TYPE_HASH (component_type), 0); - t = type_hash_canon (hashcode, t); + hstate.add_object (TYPE_HASH (component_type)); + t = type_hash_canon (hstate.end (), t); if (!COMPLETE_TYPE_P (t)) layout_type (t); @@ -9409,7 +9403,7 @@ static tree make_vector_type (tree innertype, int nunits, enum machine_mode mode) { tree t; - hashval_t hashcode = 0; + inchash hstate; t = make_node (VECTOR_TYPE); TREE_TYPE (t) = TYPE_MAIN_VARIANT (innertype); @@ -9425,11 +9419,11 @@ make_vector_type (tree innertype, int nunits, enum machine_mode mode) layout_type (t); - hashcode = iterative_hash_host_wide_int (VECTOR_TYPE, hashcode); - hashcode = iterative_hash_host_wide_int (nunits, hashcode); - hashcode = iterative_hash_host_wide_int (mode, hashcode); - hashcode = iterative_hash_object (TYPE_HASH (TREE_TYPE (t)), hashcode); - t = type_hash_canon (hashcode, 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); /* We have built a main variant, based on the main variant of the inner type. Use it to build the variant we return. */ diff --git a/gcc/tree.h b/gcc/tree.h index 190428a..2bb6d1f 100644 --- a/gcc/tree.h +++ b/gcc/tree.h @@ -22,6 +22,7 @@ along with GCC; see the file COPYING3. If not see #include "tree-core.h" #include "wide-int.h" +#include "inchash.h" /* These includes are required here because they provide declarations used by inline functions in this file. @@ -4283,7 +4284,17 @@ extern int tree_log2 (const_tree); extern int tree_floor_log2 (const_tree); extern unsigned int tree_ctz (const_tree); extern int simple_cst_equal (const_tree, const_tree); -extern hashval_t iterative_hash_expr (const_tree, hashval_t); +extern void iterative_hstate_expr (const_tree, inchash &); + +/* Compat version until all callers are converted. Return hash for + TREE with SEED. */ +static inline hashval_t iterative_hash_expr(const_tree tree, hashval_t seed) +{ + inchash hstate (seed); + iterative_hstate_expr (tree, hstate); + return hstate.end (); +} + extern int compare_tree_int (const_tree, unsigned HOST_WIDE_INT); extern int type_list_equal (const_tree, const_tree); extern int chain_member (const_tree, const_tree);