From patchwork Thu Aug 29 13:28:17 2013 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Marek Polacek X-Patchwork-Id: 270825 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 348462C00A9 for ; Thu, 29 Aug 2013 23:28:31 +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:references:mime-version :content-type:in-reply-to; q=dns; s=default; b=M0IKus40NPA6m+PHe u0V8d58StZQR3K7HaR9oUC4wR6cL1wyUOS4gf6puF6PdjvH/Zong+VmXZo+UmnvL 8fVCXfBLQjRxa33OkKfJQgA4W6JDIqrkEV/5AfoKoigLYjTzVKgfp27owxgW8lbF I6JPKTAoaOVvACMeey0H69fsVU= 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:references:mime-version :content-type:in-reply-to; s=default; bh=2mulaUJ1o2x1ODnkVhgoY8q WMH4=; b=VjB3G/q/hyRhgqtOmdbbI9TPFQaxy5DRf32sDChktwJXEMajcQOOrMm yypa0dMbn98eZRBgpegSRC6fdgPIn/HeCKTsAMf9ry4xjqmadbi/XmT2CzUYVA7e ju1jtOei3L56Fd8JQ151ozQa/WFCWlatqSYEULbFP115H98EID1g= Received: (qmail 13119 invoked by alias); 29 Aug 2013 13:28:24 -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 13107 invoked by uid 89); 29 Aug 2013 13:28:24 -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; Thu, 29 Aug 2013 13:28:24 +0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-4.3 required=5.0 tests=AWL, BAYES_00, RP_MATCHES_RCVD autolearn=ham version=3.3.2 X-HELO: mx1.redhat.com Received: from int-mx12.intmail.prod.int.phx2.redhat.com (int-mx12.intmail.prod.int.phx2.redhat.com [10.5.11.25]) by mx1.redhat.com (8.14.4/8.14.4) with ESMTP id r7TDSL0L025075 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=OK); Thu, 29 Aug 2013 09:28:21 -0400 Received: from redhat.com (ovpn-116-91.ams2.redhat.com [10.36.116.91]) by int-mx12.intmail.prod.int.phx2.redhat.com (8.14.4/8.14.4) with ESMTP id r7TDSHrf031194 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES128-SHA bits=128 verify=NO); Thu, 29 Aug 2013 09:28:20 -0400 Date: Thu, 29 Aug 2013 15:28:17 +0200 From: Marek Polacek To: Jakub Jelinek Cc: Richard Biener , GCC Patches Subject: Re: [ubsan] Use pointer map instead of hash table. Message-ID: <20130829132817.GB23899@redhat.com> References: <20130827123338.GA574@redhat.com> <20130828121543.GD574@redhat.com> <20130828125701.GF574@redhat.com> <20130828130537.GV21876@tucnak.zalov.cz> <20130828133046.GG574@redhat.com> <20130828133731.GW21876@tucnak.zalov.cz> <20130829125658.GA23899@redhat.com> <20130829130559.GD21876@tucnak.zalov.cz> MIME-Version: 1.0 Content-Disposition: inline In-Reply-To: <20130829130559.GD21876@tucnak.zalov.cz> User-Agent: Mutt/1.5.20 (2009-06-14) On Thu, Aug 29, 2013 at 03:05:59PM +0200, Jakub Jelinek wrote: > On Thu, Aug 29, 2013 at 02:56:58PM +0200, Marek Polacek wrote: > > --- gcc/Makefile.in.mp 2013-08-29 14:24:49.839578625 +0200 > > +++ gcc/Makefile.in 2013-08-29 14:54:39.354258737 +0200 > > @@ -2273,7 +2273,7 @@ tsan.o : $(CONFIG_H) $(SYSTEM_H) $(TREE_ > > intl.h cfghooks.h output.h options.h $(C_COMMON_H) tsan.h asan.h \ > > tree-ssa-propagate.h > > ubsan.o : ubsan.c ubsan.h $(CONFIG_H) $(SYSTEM_H) $(GIMPLE_H) \ > > - output.h coretypes.h $(TREE_H) $(CGRAPH_H) pointer-set.h \ > > + output.h coretypes.h $(TREE_H) $(CGRAPH_H) $(HASH_TABLE_H) gt-ubsan.h \ > > toplev.h $(C_COMMON_H) > > tree-ssa-tail-merge.o: tree-ssa-tail-merge.c \ > > $(SYSTEM_H) $(CONFIG_H) coretypes.h $(TM_H) $(BITMAP_H) \ > > --- gcc/ubsan.c.mp 2013-08-29 14:24:49.840578629 +0200 > > +++ gcc/ubsan.c 2013-08-29 14:24:54.848597440 +0200 > > @@ -24,39 +24,71 @@ along with GCC; see the file COPYING3. > > #include "tree.h" > > #include "cgraph.h" > > #include "gimple.h" > > +#include "hash-table.h" > > Why not #include "hashtab.h" instead (and corresponding change in > Makefile.in ? Fixed. > > #include "pointer-set.h" > > #include "output.h" > > #include "toplev.h" > > #include "ubsan.h" > > #include "c-family/c-common.h" > > > > -/* Map a TYPE to an ubsan type descriptor VAR_DECL for that type. */ > > -static pointer_map *typedesc_map; > > +/* Map from a tree to a VAR_DECL tree. */ > > > > -/* Insert DECL as the VAR_DECL for TYPE in the TYPEDESC_MAP. */ > > +struct GTY(()) tree_type_map { > > + struct tree_map_base type; > > + unsigned int hash; > > You use TYPE_UID as hash, and never use hash field, so why you are adding > it? Removed the hash field. > > +#define tree_type_map_eq tree_map_base_eq > > +#define tree_type_map_marked_p tree_map_base_marked_p > > + > > +static GTY ((if_marked ("tree_type_map_marked_p"), param_is (struct tree_type_map))) > > + htab_t decl_tree_for_type; > > + > > +/* Initialize the hash table. */ > > > > static void > > -insert_decl_for_type (tree decl, tree type) > > +init_hash_table (void) > > { > > - *typedesc_map->insert (type) = decl; > > + decl_tree_for_type = htab_create_ggc (512, tree_decl_map_hash, > > + tree_decl_map_eq, 0); > > tree_type_map_hash and tree_type_map_eq here, right? Yeah. Fixed. > You could also just manually inline init_hash_table into the single caller, after > all, it is just one statement. Done. > 512 might be too much, how many types we put there typically? 10, 20? Of course, 10 should be enough. > > -/* 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. */ > > +/* Lookup a VAR_DECL for TYPE, and return it if we find one. */ > > > > -static tree > > -lookup_decl_for_type (tree type) > > +tree > > +decl_for_type_lookup (tree type) > > Why are you dropping the static here? :( No clue. Fixed. > > +/* Insert a mapping TYPE->DECL in the VAR_DECL for type hashtable. */ > > + > > +void > > +decl_for_type_insert (tree type, tree decl) > > Again, can't this be static? Fixed. > Otherwise looks good. Thanks, will give it another bootstrap-ubsan round and if that's fine, I'll commit the following. 2013-08-29 Marek Polacek * Makefile.in (ubsan.o): Add HASHAB_H and gt-ubsan.h dependencies. Remove pointer-set.h dependency. * ubsan.c: Convert to C style hash table. Marek --- gcc/Makefile.in.mp 2013-08-29 14:24:49.839578625 +0200 +++ gcc/Makefile.in 2013-08-29 15:13:16.538323950 +0200 @@ -2273,7 +2273,7 @@ tsan.o : $(CONFIG_H) $(SYSTEM_H) $(TREE_ intl.h cfghooks.h output.h options.h $(C_COMMON_H) tsan.h asan.h \ tree-ssa-propagate.h ubsan.o : ubsan.c ubsan.h $(CONFIG_H) $(SYSTEM_H) $(GIMPLE_H) \ - output.h coretypes.h $(TREE_H) $(CGRAPH_H) pointer-set.h \ + output.h coretypes.h $(TREE_H) $(CGRAPH_H) $(HASHTAB_H) gt-ubsan.h \ toplev.h $(C_COMMON_H) tree-ssa-tail-merge.o: tree-ssa-tail-merge.c \ $(SYSTEM_H) $(CONFIG_H) coretypes.h $(TM_H) $(BITMAP_H) \ --- gcc/ubsan.c.mp 2013-08-29 14:24:49.840578629 +0200 +++ gcc/ubsan.c 2013-08-29 15:22:42.368445186 +0200 @@ -24,39 +24,63 @@ along with GCC; see the file COPYING3. #include "tree.h" #include "cgraph.h" #include "gimple.h" +#include "hashtab.h" #include "pointer-set.h" #include "output.h" #include "toplev.h" #include "ubsan.h" #include "c-family/c-common.h" -/* Map a TYPE to an ubsan type descriptor VAR_DECL for that type. */ -static pointer_map *typedesc_map; +/* Map from a tree to a VAR_DECL tree. */ -/* Insert DECL as the VAR_DECL for TYPE in the TYPEDESC_MAP. */ +struct GTY(()) tree_type_map { + struct tree_map_base type; + tree decl; +}; -static void -insert_decl_for_type (tree decl, tree type) -{ - *typedesc_map->insert (type) = decl; -} +#define tree_type_map_eq tree_map_base_eq +#define tree_type_map_hash tree_map_base_hash +#define tree_type_map_marked_p tree_map_base_marked_p + +static GTY ((if_marked ("tree_type_map_marked_p"), param_is (struct tree_type_map))) + htab_t decl_tree_for_type; -/* 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. */ +/* Lookup a VAR_DECL for TYPE, and return it if we find one. */ static tree -lookup_decl_for_type (tree type) +decl_for_type_lookup (tree type) { - /* If the pointer map is not initialized yet, create it now. */ - if (typedesc_map == NULL) + /* If the hash table is not initialized yet, create it now. */ + if (decl_tree_for_type == NULL) { - typedesc_map = new pointer_map; + decl_tree_for_type = htab_create_ggc (10, tree_type_map_hash, + tree_type_map_eq, 0); /* That also means we don't have to bother with the lookup. */ return NULL_TREE; } - tree *t = typedesc_map->contains (type); - return t ? *t : NULL_TREE; + + struct tree_type_map *h, in; + in.type.from = type; + + h = (struct tree_type_map *) + htab_find_with_hash (decl_tree_for_type, &in, TYPE_UID (type)); + return h ? h->decl : NULL_TREE; +} + +/* Insert a mapping TYPE->DECL in the VAR_DECL for type hashtable. */ + +static void +decl_for_type_insert (tree type, tree decl) +{ + struct tree_type_map *h; + void **slot; + + h = ggc_alloc_tree_type_map (); + h->type.from = type; + h->decl = decl; + slot = htab_find_slot_with_hash (decl_tree_for_type, h, TYPE_UID (type), + INSERT); + *(struct tree_type_map **) slot = h; } /* Helper routine, which encodes a value in the pointer_sized_int_node. @@ -226,7 +250,7 @@ ubsan_type_descriptor (tree type) /* See through any typedefs. */ type = TYPE_MAIN_VARIANT (type); - tree decl = lookup_decl_for_type (type); + tree decl = decl_for_type_lookup (type); if (decl != NULL_TREE) return decl; @@ -282,7 +306,7 @@ ubsan_type_descriptor (tree type) /* Save the address of the VAR_DECL into the pointer map. */ decl = build_fold_addr_expr (decl); - insert_decl_for_type (decl, type); + decl_for_type_insert (type, decl); return decl; } @@ -388,3 +412,5 @@ is_ubsan_builtin_p (tree t) return strncmp (IDENTIFIER_POINTER (DECL_NAME (t)), "__builtin___ubsan_", 18) == 0; } + +#include "gt-ubsan.h"