From patchwork Tue Jun 23 14:51:59 2015 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Richard Sandiford X-Patchwork-Id: 487671 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 BE8D714010F for ; Wed, 24 Jun 2015 00:52:12 +1000 (AEST) Authentication-Results: ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.b=rh9+5LeZ; 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:from :to:subject:references:date:in-reply-to:message-id:mime-version :content-type:content-transfer-encoding; q=dns; s=default; b=jrm QEgy7sd4YwOw6c2a5L5USXTpYToV6mKR0IoVExQeLrddIIyHa6Vhng9VzexJMDg8 m0O0CmpTYab/AuFS5Jd06v4/l9oYjZ5iLoB+7ayu4IBtLUZkHbM2omMH3pTX71xg QSXFQZ1hbiSqARUNM0DDNYlPug1l0YBHQqEMrqE4= 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:subject:references:date:in-reply-to:message-id:mime-version :content-type:content-transfer-encoding; s=default; bh=x4hZOT9D+ nygnxhH81riLBVa0q0=; b=rh9+5LeZlTijenv/R4PmkdsBrtU1N7mfgTUYs4y3M PynLjbYIL3+5dCq8XmwOIuZxHmziuNgQ7xX6IMmRIKiLLHsN2zPbl4gzKbVf3Vey aAdT6QS65BYWkxdhhbteNk9QQUeCIuUpBO5EtT/V+mTXoatJlD6y3bGX9qNe1IX+ uo= Received: (qmail 42462 invoked by alias); 23 Jun 2015 14:52: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 42453 invoked by uid 89); 23 Jun 2015 14:52:04 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-1.1 required=5.0 tests=AWL, BAYES_00, KAM_ASCII_DIVIDERS, SPF_PASS autolearn=no version=3.3.2 X-HELO: eu-smtp-delivery-143.mimecast.com Received: from eu-smtp-delivery-143.mimecast.com (HELO eu-smtp-delivery-143.mimecast.com) (207.82.80.143) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Tue, 23 Jun 2015 14:52:02 +0000 Received: from cam-owa1.Emea.Arm.com (fw-tnat.cambridge.arm.com [217.140.96.140]) by eu-smtp-1.mimecast.com with ESMTP id uk-mta-10-_IblWUgFRFqJERB18cF1YA-1 Received: from localhost ([10.1.2.79]) by cam-owa1.Emea.Arm.com with Microsoft SMTPSVC(6.0.3790.3959); Tue, 23 Jun 2015 15:51:59 +0100 From: Richard Sandiford To: gcc-patches@gcc.gnu.org Mail-Followup-To: gcc-patches@gcc.gnu.org, richard.sandiford@arm.com Subject: [08/12] Add common traits for integer hash keys References: <87egl2bicm.fsf@e105548-lin.cambridge.arm.com> Date: Tue, 23 Jun 2015 15:51:59 +0100 In-Reply-To: <87egl2bicm.fsf@e105548-lin.cambridge.arm.com> (Richard Sandiford's message of "Tue, 23 Jun 2015 15:38:17 +0100") Message-ID: <87bng6a35c.fsf@e105548-lin.cambridge.arm.com> User-Agent: Gnus/5.130012 (Ma Gnus v0.12) Emacs/24.3 (gnu/linux) MIME-Version: 1.0 X-MC-Unique: _IblWUgFRFqJERB18cF1YA-1 Several places define hash traits for integers, using particular integer values as "empty" and "deleted" markers. This patch defines them in terms of a single int_hash class. I also needed to extend gengtype to accept "+" in template arguments. gcc/ * gengtype-parse.c (require_template_declaration): Allow '+' in template parameters. Consolidate cases. * hash-traits.h (int_hash): New class. * alias.c (alias_set_hash): New structure. (alias_set_traits): Use it. * symbol-summary.h (function_summary::map_hash): New class. (function_summary::summary_hashmap_traits): Use it. * tree-inline.h (dependence_hash): New class. (dependence_hasher): Use it. * tree-ssa-reassoc.c (oecount_hasher): Use int_hash. * value-prof.c (profile_id_hash): New class. (profile_id_traits): Use it. Index: gcc/gengtype-parse.c =================================================================== --- gcc/gengtype-parse.c 2015-06-23 15:50:56.686110247 +0100 +++ gcc/gengtype-parse.c 2015-06-23 15:50:56.678110339 +0100 @@ -274,17 +274,13 @@ require_template_declaration (const char str = concat (str, "enum ", (char *) 0); continue; } - if (token () == NUM) + if (token () == NUM + || token () == ':' + || token () == '+') { str = concat (str, advance (), (char *) 0); continue; } - if (token () == ':') - { - advance (); - str = concat (str, ":", (char *) 0); - continue; - } if (token () == '<') { advance (); Index: gcc/hash-traits.h =================================================================== --- gcc/hash-traits.h 2015-06-23 15:50:56.686110247 +0100 +++ gcc/hash-traits.h 2015-06-23 15:50:56.674110387 +0100 @@ -57,6 +57,68 @@ typed_noop_remove ::remove (Type & } +/* Hasher for integer type Type in which Empty is a spare value that can be + used to mark empty slots. If Deleted != Empty then Deleted is another + spare value that can be used for deleted slots; if Deleted == Empty then + hash table entries cannot be deleted. */ + +template +struct int_hash : typed_noop_remove +{ + typedef Type value_type; + typedef Type compare_type; + + static inline hashval_t hash (value_type); + static inline bool equal (value_type existing, value_type candidate); + static inline void mark_deleted (Type &); + static inline void mark_empty (Type &); + static inline bool is_deleted (Type); + static inline bool is_empty (Type); +}; + +template +inline hashval_t +int_hash ::hash (value_type x) +{ + return x; +} + +template +inline bool +int_hash ::equal (value_type x, value_type y) +{ + return x == y; +} + +template +inline void +int_hash ::mark_deleted (Type &x) +{ + gcc_assert (Empty != Deleted); + x = Deleted; +} + +template +inline void +int_hash ::mark_empty (Type &x) +{ + x = Empty; +} + +template +inline bool +int_hash ::is_deleted (Type x) +{ + return Empty != Deleted && x == Deleted; +} + +template +inline bool +int_hash ::is_empty (Type x) +{ + return x == Empty; +} + /* Pointer hasher based on pointer equality. Other types of pointer hash can inherit this and override the hash and equal functions with some other form of equality (such as string equality). */ Index: gcc/alias.c =================================================================== --- gcc/alias.c 2015-06-23 15:50:56.686110247 +0100 +++ gcc/alias.c 2015-06-23 15:50:56.678110339 +0100 @@ -143,31 +143,8 @@ Software Foundation; either version 3, o However, this is no actual entry for alias set zero. It is an error to attempt to explicitly construct a subset of zero. */ -struct alias_set_traits : default_hashmap_traits -{ - template - static bool - is_empty (T &e) - { - return e.m_key == INT_MIN; - } - - template - static bool - is_deleted (T &e) - { - return e.m_key == (INT_MIN + 1); - } - - template static void mark_empty (T &e) { e.m_key = INT_MIN; } - - template - static void - mark_deleted (T &e) - { - e.m_key = INT_MIN + 1; - } -}; +struct alias_set_hash : int_hash {}; +struct alias_set_traits : simple_hashmap_traits {}; struct GTY(()) alias_set_entry_d { /* The alias set number, as stored in MEM_ALIAS_SET. */ Index: gcc/symbol-summary.h =================================================================== --- gcc/symbol-summary.h 2015-06-23 15:50:56.686110247 +0100 +++ gcc/symbol-summary.h 2015-06-23 15:50:56.678110339 +0100 @@ -200,45 +200,8 @@ class GTY((user)) function_summary bool m_ggc; private: - struct summary_hashmap_traits: default_hashmap_traits - { - static const int deleted_value = -1; - static const int empty_value = 0; - - static hashval_t - hash (const int v) - { - return (hashval_t)v; - } - - template - static bool - is_deleted (Type &e) - { - return e.m_key == deleted_value; - } - - template - static bool - is_empty (Type &e) - { - return e.m_key == empty_value; - } - - template - static void - mark_deleted (Type &e) - { - e.m_key = deleted_value; - } - - template - static void - mark_empty (Type &e) - { - e.m_key = empty_value; - } - }; + typedef int_hash map_hash; + typedef simple_hashmap_traits summary_hashmap_traits; /* Getter for summary callgraph ID. */ T* get (int uid) Index: gcc/tree-inline.h =================================================================== --- gcc/tree-inline.h 2015-06-23 15:50:56.686110247 +0100 +++ gcc/tree-inline.h 2015-06-23 15:50:56.678110339 +0100 @@ -35,25 +35,8 @@ enum copy_body_cge_which CB_CGE_MOVE_CLONES }; -struct dependence_hasher : default_hashmap_traits -{ - template - static void - mark_deleted (T &e) - { gcc_unreachable (); } - - template - static void - mark_empty (T &e) - { e.m_key = 0; } - - template - static bool - is_deleted (T &) - { return false; } - - template static bool is_empty (T &e) { return e.m_key == 0; } -}; +typedef int_hash dependence_hash; +typedef simple_hashmap_traits dependence_hasher; /* Data required for function body duplication. */ Index: gcc/tree-ssa-reassoc.c =================================================================== --- gcc/tree-ssa-reassoc.c 2015-06-23 15:50:56.686110247 +0100 +++ gcc/tree-ssa-reassoc.c 2015-06-23 15:50:56.678110339 +0100 @@ -1019,23 +1019,16 @@ typedef struct oecount_s { /* Oecount hashtable helpers. */ -struct oecount_hasher +struct oecount_hasher : int_hash { - typedef int value_type; - typedef int compare_type; - static inline hashval_t hash (const value_type &); - static inline bool equal (const value_type &, const compare_type &); - static bool is_deleted (int &v) { return v == 1; } - static void mark_deleted (int &e) { e = 1; } - static bool is_empty (int &v) { return v == 0; } - static void mark_empty (int &e) { e = 0; } - static void remove (int &) {} + static inline hashval_t hash (int); + static inline bool equal (int, int); }; /* Hash function for oecount. */ inline hashval_t -oecount_hasher::hash (const value_type &p) +oecount_hasher::hash (int p) { const oecount *c = &cvec[p - 42]; return htab_hash_pointer (c->op) ^ (hashval_t)c->oecode; @@ -1044,7 +1037,7 @@ oecount_hasher::hash (const value_type & /* Comparison function for oecount. */ inline bool -oecount_hasher::equal (const value_type &p1, const compare_type &p2) +oecount_hasher::equal (int p1, int p2) { const oecount *c1 = &cvec[p1 - 42]; const oecount *c2 = &cvec[p2 - 42]; Index: gcc/value-prof.c =================================================================== --- gcc/value-prof.c 2015-06-23 15:50:56.686110247 +0100 +++ gcc/value-prof.c 2015-06-23 15:50:56.682110292 +0100 @@ -1250,19 +1250,8 @@ gimple_mod_subtract_transform (gimple_st return true; } -struct profile_id_traits : default_hashmap_traits -{ - template - static bool - is_deleted (T &e) - { - return e.m_key == UINT_MAX; - } - - template static bool is_empty (T &e) { return e.m_key == 0; } - template static void mark_deleted (T &e) { e.m_key = UINT_MAX; } - template static void mark_empty (T &e) { e.m_key = 0; } -}; +typedef int_hash profile_id_hash; +typedef simple_hashmap_traits profile_id_traits; static hash_map * cgraph_node_map = 0;