From patchwork Tue Aug 27 12:33:38 2013 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Marek Polacek X-Patchwork-Id: 270099 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 with cipher DHE-RSA-AES256-SHA (256/256 bits)) (Client CN "www.sourceware.org", Issuer "StartCom Class 1 Primary Intermediate Server CA" (not verified)) by ozlabs.org (Postfix) with ESMTPS id 654382C00DA for ; Tue, 27 Aug 2013 22:33:55 +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:date :from:to:cc:subject:message-id:mime-version:content-type; q=dns; s=default; b=JF/Ha05PCw7XEVAbtffNugE0CBXWYYiDDcz8DtX2zUr7/i0ACm lZhBwT6id0P+b4ysM3CbSmp/MkmimUxQZDH9nRfUW2KzOmsDApPCIQC5FuD2PG0Y lJXAAI+qadrg5CvDqrugzsrtRS5CfvuDxRu/pWgK/VDr9i+1HO6vV3iW0= 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:cc:subject:message-id:mime-version:content-type; s= default; bh=uEN4ZSfxX2QrFNFybRv2hKH2yOI=; b=hO+2WoEauL6j262IfAYj XdW7WGJqxeS5gmv/OGvyEVeyXknDOFs/EHJOTnROGwbNnH10nxUuvGEYbjWsKx4U 3D16AoQ9K9BO4g0El2Fe5mu42TahKKjYnvJVKMI74FKM+Vu2HnEOkpgjhj1k6W5Y 5sGTXN5AeKgK45z6YCjFKm8= Received: (qmail 22250 invoked by alias); 27 Aug 2013 12:33:46 -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 22240 invoked by uid 89); 27 Aug 2013 12:33:46 -0000 Received: from mx1.redhat.com (HELO mx1.redhat.com) (209.132.183.28) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Tue, 27 Aug 2013 12:33:46 +0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-4.0 required=5.0 tests=AWL, BAYES_00, RP_MATCHES_RCVD autolearn=ham version=3.3.2 X-HELO: mx1.redhat.com Received: from int-mx09.intmail.prod.int.phx2.redhat.com (int-mx09.intmail.prod.int.phx2.redhat.com [10.5.11.22]) by mx1.redhat.com (8.14.4/8.14.4) with ESMTP id r7RCXhgq010350 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=OK) for ; Tue, 27 Aug 2013 08:33:43 -0400 Received: from redhat.com (ovpn-116-91.ams2.redhat.com [10.36.116.91]) by int-mx09.intmail.prod.int.phx2.redhat.com (8.14.4/8.14.4) with ESMTP id r7RCXd2L001742 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES128-SHA bits=128 verify=NO); Tue, 27 Aug 2013 08:33:42 -0400 Date: Tue, 27 Aug 2013 14:33:38 +0200 From: Marek Polacek To: GCC Patches Cc: Jakub Jelinek Subject: [ubsan] Use pointer map instead of hash table. Message-ID: <20130827123338.GA574@redhat.com> MIME-Version: 1.0 Content-Disposition: inline User-Agent: Mutt/1.5.20 (2009-06-14) It turned out that for tree -> tree mapping we don't need the hash table at all; pointer map is much more convenient. So this patch weeds out the hash table out of ubsan and introduces pointer map instead. Quite a lot of code could go away--no need to set the alloc pools up etc. Regtested, ran bootstrap-ubsan on x86_64-linux. Applying to the ubsan branch. 2013-08-27 Marek Polacek * ubsan.c: Use pointer map instead of hash table. Marek --- gcc/ubsan.c.mp 2013-08-27 12:31:04.136213922 +0200 +++ gcc/ubsan.c 2013-08-27 12:31:10.361236456 +0200 @@ -22,109 +22,42 @@ along with GCC; see the file COPYING3. #include "system.h" #include "coretypes.h" #include "tree.h" -#include "alloc-pool.h" #include "cgraph.h" #include "gimple.h" -#include "hash-table.h" +#include "pointer-set.h" #include "output.h" #include "toplev.h" #include "ubsan.h" #include "c-family/c-common.h" -/* This type represents an entry in the hash table; this hash table - maps from a TYPE to a ubsan type descriptor VAR_DECL for that type. */ -struct ubsan_typedesc -{ - /* This represents the type of a variable. */ - tree type; - - /* This is the VAR_DECL of the type. */ - tree decl; -}; - -static alloc_pool ubsan_typedesc_alloc_pool; - -/* Hash table for type descriptors. */ -struct ubsan_typedesc_hasher - : typed_noop_remove -{ - typedef ubsan_typedesc value_type; - typedef ubsan_typedesc compare_type; - - static inline hashval_t hash (const value_type *); - static inline bool equal (const value_type *, const compare_type *); -}; - -/* Hash a memory reference. */ - -inline hashval_t -ubsan_typedesc_hasher::hash (const ubsan_typedesc *data) -{ - return iterative_hash_object (TYPE_UID (data->type), 0); -} - -/* Compare two data types. */ - -inline bool -ubsan_typedesc_hasher::equal (const ubsan_typedesc *d1, - const ubsan_typedesc *d2) -{ - /* Here, the types should have identical __typekind, - __typeinfo and __typename. */ - return d1->type == d2->type; -} - -static hash_table ubsan_typedesc_ht; +/* Map a TYPE to an ubsan type descriptor VAR_DECL for that type. */ +static pointer_map_t *typedesc_map; -/* Initializes an instance of ubsan_typedesc. */ +/* Insert DECL as the VAR_DECL for TYPE in the TYPEDESC_MAP. */ static void -ubsan_typedesc_init (ubsan_typedesc *data, tree type, tree decl) +insert_decl_for_type (tree decl, tree type) { - data->type = type; - data->decl = decl; + void **slot = pointer_map_insert (typedesc_map, type); + gcc_assert (*slot == NULL); + *slot = decl; } -/* This creates the alloc pool used to store the instances of - ubsan_typedesc that are stored in the hash table ubsan_typedesc_ht. */ +/* Find the VAR_DECL for TYPE in TYPEDESC_MAP. If TYPE does not + exist in the map, return NULL_TREE, otherwise, return the VAR_DECL + we found. */ -static alloc_pool -ubsan_typedesc_get_alloc_pool () -{ - if (ubsan_typedesc_alloc_pool == NULL) - ubsan_typedesc_alloc_pool = create_alloc_pool ("ubsan_typedesc", - sizeof (ubsan_typedesc), - 10); - return ubsan_typedesc_alloc_pool; -} - -/* Returns a reference to the hash table containing data type. - This function ensures that the hash table is created. */ - -static hash_table & -get_typedesc_hash_table () -{ - if (!ubsan_typedesc_ht.is_created ()) - ubsan_typedesc_ht.create (10); - - return ubsan_typedesc_ht; -} - -/* Allocates memory for an instance of ubsan_typedesc into the memory - pool returned by ubsan_typedesc_get_alloc_pool and initialize it. - TYPE describes a particular type, DECL is its VAR_DECL. */ - -static ubsan_typedesc * -ubsan_typedesc_new (tree type, tree decl) +static tree +lookup_decl_for_type (tree type) { - ubsan_typedesc *desc = - (ubsan_typedesc *) pool_alloc (ubsan_typedesc_get_alloc_pool ()); - - ubsan_typedesc_init (desc, type, decl); - return desc; + /* If the pointer map is not initialized yet, create it now. */ + if (typedesc_map == NULL) + typedesc_map = pointer_map_create (); + void **slot = pointer_map_contains (typedesc_map, type); + return slot ? (tree) *slot : NULL_TREE; } -/* Helper routine, which encodes a value in the uptr type. +/* Helper routine, which encodes a value in the pointer_sized_int_node. Arguments with precision <= POINTER_SIZE are passed directly, the rest is passed by reference. T is a value we are to encode. */ @@ -281,24 +214,19 @@ get_ubsan_type_info_for_type (tree type) } /* Helper routine that returns ADDR_EXPR of a VAR_DECL of a type - descriptor. It first looks into the hash table; if not found, - create the VAR_DECL, put it into the hash table and return the + descriptor. It first looks into the pointer map; if not found, + create the VAR_DECL, put it into the pointer map and return the ADDR_EXPR of it. TYPE describes a particular type. */ tree ubsan_type_descriptor (tree type) { - hash_table ht = get_typedesc_hash_table (); - ubsan_typedesc d; - /* See through any typedefs. */ type = TYPE_MAIN_VARIANT (type); - ubsan_typedesc_init (&d, type, NULL); - ubsan_typedesc **slot = ht.find_slot (&d, INSERT); - if (*slot != NULL) - /* We have the VAR_DECL in the table. Return it. */ - return (*slot)->decl; + tree decl = lookup_decl_for_type (type); + if (decl != NULL_TREE) + return decl; tree dtype = ubsan_type_descriptor_type (); const char *tname; @@ -326,7 +254,7 @@ ubsan_type_descriptor (tree type) char tmp_name[32]; static unsigned int type_var_id_num; ASM_GENERATE_INTERNAL_LABEL (tmp_name, "Lubsan_type", type_var_id_num++); - tree decl = build_decl (UNKNOWN_LOCATION, VAR_DECL, get_identifier (tmp_name), + decl = build_decl (UNKNOWN_LOCATION, VAR_DECL, get_identifier (tmp_name), dtype); TREE_STATIC (decl) = 1; TREE_PUBLIC (decl) = 0; @@ -350,9 +278,9 @@ ubsan_type_descriptor (tree type) DECL_INITIAL (decl) = ctor; rest_of_decl_compilation (decl, 1, 0); - /* Save the address of the VAR_DECL into the hash table. */ + /* Save the address of the VAR_DECL into the pointer map. */ decl = build_fold_addr_expr (decl); - *slot = ubsan_typedesc_new (type, decl); + insert_decl_for_type (decl, type); return decl; }