From patchwork Sun Dec 2 01:46:31 2012 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Lawrence Crowl X-Patchwork-Id: 203172 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]) by ozlabs.org (Postfix) with SMTP id 6088A2C00AC for ; Sun, 2 Dec 2012 12:46:45 +1100 (EST) Comment: DKIM? See http://www.dkim.org DKIM-Signature: v=1; a=rsa-sha1; c=relaxed/relaxed; d=gcc.gnu.org; s=default; x=1355017607; h=Comment: DomainKey-Signature:Received:Received:Received:Received: MIME-Version:Received:Received:Date:Message-ID:Subject:From:To: Cc:Content-Type:Content-Transfer-Encoding:Mailing-List: Precedence:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:Sender:Delivered-To; bh=ybRvVkUKqTCiiCwnuDAD6W6uUsU=; b=fjnDFxmKxhvJhfg+0kJJx1GiGRGv553OR7ctn7BOY0W2BQXqk6bMKEQuiMsPEZ kIHYQIBhFsbPElKbJntmb9x/3yL/eDr6rA9aT2ivtZRhEpEzf3DLPw9/ADUXMEeO /efkZyTUigmEW6rhJBMtQP3PSmHoxjvnFpX9uLk5Udjyk= Comment: DomainKeys? See http://antispam.yahoo.com/domainkeys DomainKey-Signature: a=rsa-sha1; q=dns; c=nofws; s=default; d=gcc.gnu.org; h=Received:Received:X-SWARE-Spam-Status:X-Spam-Check-By:Received:Received:X-Google-DKIM-Signature:MIME-Version:Received:Received:Date:Message-ID:Subject:From:To:Cc:Content-Type:Content-Transfer-Encoding:X-Gm-Message-State:X-IsSubscribed:Mailing-List:Precedence:List-Id:List-Unsubscribe:List-Archive:List-Post:List-Help:Sender:Delivered-To; b=iPVH/xG06YKi+GOvL1oT6a+l4j6pcCUMfm6QQ78hiCkrrtljIeSRBEuBtxQNvW cGqsxtp/Ir/0Vw3myTZM9GxgDMdZ/lQbYfPOATxQOKMxZEjxix6RLKhFbhuxEPm6 2twjfpvpKlZ3z0zfqDosqAbH1JmgUXuxUPgRelujPtePE=; Received: (qmail 21873 invoked by alias); 2 Dec 2012 01:46:40 -0000 Received: (qmail 21862 invoked by uid 22791); 2 Dec 2012 01:46:40 -0000 X-SWARE-Spam-Status: No, hits=-5.3 required=5.0 tests=AWL, BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, KHOP_RCVD_TRUST, RCVD_IN_DNSWL_LOW, RCVD_IN_HOSTKARMA_YE, RP_MATCHES_RCVD X-Spam-Check-By: sourceware.org Received: from mail-qa0-f47.google.com (HELO mail-qa0-f47.google.com) (209.85.216.47) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Sun, 02 Dec 2012 01:46:33 +0000 Received: by mail-qa0-f47.google.com with SMTP id a19so594988qad.20 for ; Sat, 01 Dec 2012 17:46:32 -0800 (PST) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20120113; h=mime-version:date:message-id:subject:from:to:cc:content-type :content-transfer-encoding:x-gm-message-state; bh=XDMK43/rhP0zEV3At7D/DxAT8J5TdvE6pIgztDyndr4=; b=mfUDfQWKSLLZWcimeIBqRBHvP15PrHHDG7HjaX3f3Tgxgln4VJ8atGviNUf6wlAcl5 Jm9mM72PI/vm8HuAuQnMSQntgBgr+OtC9fsZgHr1Agze1QTImDJPe9hRzeiLue+zdgVj SpOLLgrTaLnHHdcuUweYZSVKFUIzOf7QVHM7BghWFQ8QXEp1gPuusWY8qgxrrIp8rPsN lD/CbugrBTqivq5252LUzMs8svvMuziKataFF663ICSVaursCdWKjzc0fLB5aA9wwuSR J3CLuDNH3lR2dYXLuGmIpvovMMKeJDHFT1Rtacob2aUZTehi1Q4YZbdUngCRpJGSGo33 gQ0Q== MIME-Version: 1.0 Received: by 10.49.82.68 with SMTP id g4mr10799637qey.54.1354412792082; Sat, 01 Dec 2012 17:46:32 -0800 (PST) Received: by 10.229.136.199 with HTTP; Sat, 1 Dec 2012 17:46:31 -0800 (PST) Date: Sat, 1 Dec 2012 17:46:31 -0800 Message-ID: Subject: [cxx-conversion] ggc-common hash tables From: Lawrence Crowl To: gcc-patches List Cc: Diego Novillo X-Gm-Message-State: ALoCoQle0/7mG8CgDr68fFieE9Nd64NM/NkcGRhyN8OC4pwtJrCrHVOlHQ2K1m4OVSlVlgj5WvRYiBMDJ2PdkTBPl0T2LCBWwPOHTf0ZLDX38jccSzaCvSyUuJoYZ1Thjz0m7fpZ14jrGK8r908M1vtay50o2LBBZXRkATSdiiOgftPsQPbgUS4TBu9N2ZRlY80h62lENFgw X-IsSubscribed: yes 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 Change ggc-common hash tables from htab_t to hash_table: ggc-common.c loc_hash ggc-common.c ptr_hash Add a new hash_table method elements_with_deleted to meet the needs of gcc-common.c. Correct many methods with parameter types compare_type to the correct value_type. (Correct code was unlikely to notice the change, but incorrect code will.) Tested on x86-64. Okay for branch? $(RTL_H) $(TREE_H) \ Index: gcc/ChangeLog 2012-11-30 Lawrence Crowl * hash-table.h (class hash_table): Correct many methods with parameter types compare_type to the correct value_type. (Correct code was unlikely to notice the change.) (hash_table::elements_with_deleted) New. * ggc-common.c (htab_t saving_htab): Change type to hash_table. Update dependent calls and types. (htab_t loc_hash): Likewise. (htab_t ptr_hash): Likewise. (call_count): Rename ggc_call_count. (call_alloc): Rename ggc_call_alloc. (loc_descriptor): Rename make_loc_descriptor. (add_statistics): Rename ggc_add_statistics. * Makefile.in: Update to changes above. Index: gcc/hash-table.h =================================================================== --- gcc/hash-table.h (revision 193902) +++ gcc/hash-table.h (working copy) @@ -380,19 +380,19 @@ public: void create (size_t initial_slots); bool is_created (); void dispose (); - value_type *find (const compare_type *comparable); + value_type *find (const value_type *value); value_type *find_with_hash (const compare_type *comparable, hashval_t hash); - value_type **find_slot (const compare_type *comparable, - enum insert_option insert); + value_type **find_slot (const value_type *value, enum insert_option insert); value_type **find_slot_with_hash (const compare_type *comparable, hashval_t hash, enum insert_option insert); void empty (); void clear_slot (value_type **slot); - void remove_elt (const compare_type *comparable); + void remove_elt (const value_type *value); void remove_elt_with_hash (const compare_type *comparable, hashval_t hash); - size_t size(); - size_t elements(); - double collisions(); + size_t size (); + size_t elements (); + size_t elements_with_deleted (); + double collisions (); template @@ -431,9 +431,9 @@ hash_table ::is_c template class Allocator> inline typename Descriptor::value_type * -hash_table ::find (const compare_type *comparable) +hash_table ::find (const value_type *value) { - return find_with_hash (comparable, Descriptor::hash (comparable)); + return find_with_hash (value, Descriptor::hash (value)); } @@ -443,9 +443,9 @@ template class Allocator> inline typename Descriptor::value_type ** hash_table -::find_slot (const compare_type *comparable, enum insert_option insert) +::find_slot (const value_type *value, enum insert_option insert) { - return find_slot_with_hash (comparable, Descriptor::hash (comparable), insert); + return find_slot_with_hash (value, Descriptor::hash (value), insert); } @@ -454,9 +454,9 @@ hash_table template class Allocator> inline void -hash_table ::remove_elt (const compare_type *comparable) +hash_table ::remove_elt (const value_type *value) { - remove_elt_with_hash (comparable, Descriptor::hash (comparable)); + remove_elt_with_hash (value, Descriptor::hash (value)); } @@ -476,12 +476,23 @@ hash_table ::size template class Allocator> inline size_t -hash_table ::elements() +hash_table ::elements () { return htab->n_elements - htab->n_deleted; } +/* Return the current number of elements in this hash table. */ + +template class Allocator> +inline size_t +hash_table ::elements_with_deleted () +{ + return htab->n_elements; +} + + /* Return the fraction of fixed collisions during all work with given hash table. */ Index: gcc/ggc-common.c =================================================================== --- gcc/ggc-common.c (revision 193902) +++ gcc/ggc-common.c (working copy) @@ -24,7 +24,7 @@ along with GCC; see the file COPYING3. #include "config.h" #include "system.h" #include "coretypes.h" -#include "hashtab.h" +#include "hash-table.h" #include "ggc.h" #include "ggc-internal.h" #include "diagnostic-core.h" @@ -47,10 +47,6 @@ static ggc_statistics *ggc_stats; struct traversal_state; static int ggc_htab_delete (void **, void *); -static hashval_t saving_htab_hash (const void *); -static int saving_htab_eq (const void *, const void *); -static int call_count (void **, void *); -static int call_alloc (void **, void *); static int compare_ptr_data (const void *, const void *); static void relocate_ptrs (void *, void *); static void write_pch_globals (const struct ggc_root_tab * const *tab, @@ -291,8 +287,6 @@ ggc_print_common_statistics (FILE *strea /* Functions for saving and restoring GCable memory to disk. */ -static htab_t saving_htab; - struct ptr_data { void *obj; @@ -306,6 +300,30 @@ struct ptr_data #define POINTER_HASH(x) (hashval_t)((long)x >> 3) +/* Helper for hashing saving_htab. */ + +struct saving_hasher : typed_free_remove +{ + typedef ptr_data value_type; + typedef void compare_type; + static inline hashval_t hash (const value_type *); + static inline bool equal (const value_type *, const compare_type *); +}; + +inline hashval_t +saving_hasher::hash (const value_type *p) +{ + return POINTER_HASH (p->obj); +} + +inline bool +saving_hasher::equal (const value_type *p1, const compare_type *p2) +{ + return p1->obj == p2; +} + +static hash_table saving_htab; + /* Register an object in the hash table. */ int @@ -319,8 +337,7 @@ gt_pch_note_object (void *obj, void *not return 0; slot = (struct ptr_data **) - htab_find_slot_with_hash (saving_htab, obj, POINTER_HASH (obj), - INSERT); + saving_htab.find_slot_with_hash (obj, POINTER_HASH (obj), INSERT); if (*slot != NULL) { gcc_assert ((*slot)->note_ptr_fn == note_ptr_fn @@ -352,26 +369,12 @@ gt_pch_note_reorder (void *obj, void *no return; data = (struct ptr_data *) - htab_find_with_hash (saving_htab, obj, POINTER_HASH (obj)); + saving_htab.find_with_hash (obj, POINTER_HASH (obj)); gcc_assert (data && data->note_ptr_cookie == note_ptr_cookie); data->reorder_fn = reorder_fn; } -/* Hash and equality functions for saving_htab, callbacks for htab_create. */ - -static hashval_t -saving_htab_hash (const void *p) -{ - return POINTER_HASH (((const struct ptr_data *)p)->obj); -} - -static int -saving_htab_eq (const void *p1, const void *p2) -{ - return ((const struct ptr_data *)p1)->obj == p2; -} - /* Handy state for the traversal functions. */ struct traversal_state @@ -385,11 +388,10 @@ struct traversal_state /* Callbacks for htab_traverse. */ -static int -call_count (void **slot, void *state_p) +int +ggc_call_count (ptr_data **slot, traversal_state *state) { - struct ptr_data *d = (struct ptr_data *)*slot; - struct traversal_state *state = (struct traversal_state *)state_p; + struct ptr_data *d = *slot; ggc_pch_count_object (state->d, d->obj, d->size, d->note_ptr_fn == gt_pch_p_S, @@ -398,11 +400,10 @@ call_count (void **slot, void *state_p) return 1; } -static int -call_alloc (void **slot, void *state_p) +int +ggc_call_alloc (ptr_data **slot, traversal_state *state) { - struct ptr_data *d = (struct ptr_data *)*slot; - struct traversal_state *state = (struct traversal_state *)state_p; + struct ptr_data *d = *slot; d->new_addr = ggc_pch_alloc_object (state->d, d->obj, d->size, d->note_ptr_fn == gt_pch_p_S, @@ -436,7 +437,7 @@ relocate_ptrs (void *ptr_p, void *state_ return; result = (struct ptr_data *) - htab_find_with_hash (saving_htab, *ptr, POINTER_HASH (*ptr)); + saving_htab.find_with_hash (*ptr, POINTER_HASH (*ptr)); gcc_assert (result); *ptr = result->new_addr; } @@ -465,7 +466,7 @@ write_pch_globals (const struct ggc_root else { new_ptr = (struct ptr_data *) - htab_find_with_hash (saving_htab, ptr, POINTER_HASH (ptr)); + saving_htab.find_with_hash (ptr, POINTER_HASH (ptr)); if (fwrite (&new_ptr->new_addr, sizeof (void *), 1, state->f) != 1) fatal_error ("can%'t write PCH file: %m"); @@ -499,7 +500,7 @@ gt_pch_save (FILE *f) gt_pch_save_stringpool (); timevar_push (TV_PCH_PTR_REALLOC); - saving_htab = htab_create (50000, saving_htab_hash, saving_htab_eq, free); + saving_htab.create (50000); for (rt = gt_ggc_rtab; *rt; rt++) for (rti = *rt; rti->base != NULL; rti++) @@ -515,7 +516,7 @@ gt_pch_save (FILE *f) state.f = f; state.d = init_ggc_pch (); state.count = 0; - htab_traverse (saving_htab, call_count, &state); + saving_htab.traverse (&state); mmi.size = ggc_pch_total_size (state.d); @@ -531,7 +532,7 @@ gt_pch_save (FILE *f) state.ptrs = XNEWVEC (struct ptr_data *, state.count); state.ptrs_i = 0; - htab_traverse (saving_htab, call_alloc, &state); + saving_htab.traverse (&state); timevar_pop (TV_PCH_PTR_REALLOC); timevar_push (TV_PCH_PTR_SORT); @@ -594,7 +595,7 @@ gt_pch_save (FILE *f) gt_pch_fixup_stringpool (); free (state.ptrs); - htab_delete (saving_htab); + saving_htab.dispose (); } /* Read the state of the compiler back in from F. */ @@ -854,30 +855,32 @@ struct loc_descriptor size_t collected; }; -/* Hashtable used for statistics. */ -static htab_t loc_hash; +/* Hash table helper. */ -/* Hash table helpers functions. */ -static hashval_t -hash_descriptor (const void *p) +struct loc_desc_hasher : typed_noop_remove { - const struct loc_descriptor *const d = (const struct loc_descriptor *) p; + typedef loc_descriptor value_type; + typedef loc_descriptor compare_type; + static inline hashval_t hash (const value_type *); + static inline bool equal (const value_type *, const compare_type *); +}; +inline hashval_t +loc_desc_hasher::hash (const value_type *d) +{ return htab_hash_pointer (d->function) | d->line; } -static int -eq_descriptor (const void *p1, const void *p2) +inline bool +loc_desc_hasher::equal (const value_type *d, const compare_type *d2) { - const struct loc_descriptor *const d = (const struct loc_descriptor *) p1; - const struct loc_descriptor *const d2 = (const struct loc_descriptor *) p2; - return (d->file == d2->file && d->line == d2->line && d->function == d2->function); } -/* Hashtable converting address of allocated field to loc descriptor. */ -static htab_t ptr_hash; +/* Hashtable used for statistics. */ +static hash_table loc_hash; + struct ptr_hash_entry { void *ptr; @@ -885,26 +888,34 @@ struct ptr_hash_entry size_t size; }; -/* Hash table helpers functions. */ -static hashval_t -hash_ptr (const void *p) +/* Helper for ptr_hash table. */ + +struct ptr_hash_hasher : typed_noop_remove { - const struct ptr_hash_entry *const d = (const struct ptr_hash_entry *) p; + typedef ptr_hash_entry value_type; + typedef void compare_type; + static inline hashval_t hash (const value_type *); + static inline bool equal (const value_type *, const compare_type *); +}; +inline hashval_t +ptr_hash_hasher::hash (const value_type *d) +{ return htab_hash_pointer (d->ptr); } -static int -eq_ptr (const void *p1, const void *p2) +inline bool +ptr_hash_hasher::equal (const value_type *p, const compare_type *p2) { - const struct ptr_hash_entry *const p = (const struct ptr_hash_entry *) p1; - return (p->ptr == p2); } +/* Hashtable converting address of allocated field to loc descriptor. */ +static hash_table ptr_hash; + /* Return descriptor for given call site, create new one if needed. */ static struct loc_descriptor * -loc_descriptor (const char *name, int line, const char *function) +make_loc_descriptor (const char *name, int line, const char *function) { struct loc_descriptor loc; struct loc_descriptor **slot; @@ -912,10 +923,10 @@ loc_descriptor (const char *name, int li loc.file = name; loc.line = line; loc.function = function; - if (!loc_hash) - loc_hash = htab_create (10, hash_descriptor, eq_descriptor, NULL); + if (!loc_hash.is_created ()) + loc_hash.create (10); - slot = (struct loc_descriptor **) htab_find_slot (loc_hash, &loc, INSERT); + slot = loc_hash.find_slot (&loc, INSERT); if (*slot) return *slot; *slot = XCNEW (struct loc_descriptor); @@ -930,16 +941,16 @@ void ggc_record_overhead (size_t allocated, size_t overhead, void *ptr, const char *name, int line, const char *function) { - struct loc_descriptor *loc = loc_descriptor (name, line, function); + struct loc_descriptor *loc = make_loc_descriptor (name, line, function); struct ptr_hash_entry *p = XNEW (struct ptr_hash_entry); - PTR *slot; + ptr_hash_entry **slot; p->ptr = ptr; p->loc = loc; p->size = allocated + overhead; - if (!ptr_hash) - ptr_hash = htab_create (10, hash_ptr, eq_ptr, NULL); - slot = htab_find_slot_with_hash (ptr_hash, ptr, htab_hash_pointer (ptr), INSERT); + if (!ptr_hash.is_created ()) + ptr_hash.create (10); + slot = ptr_hash.find_slot_with_hash (ptr, htab_hash_pointer (ptr), INSERT); gcc_assert (!*slot); *slot = p; @@ -950,14 +961,14 @@ ggc_record_overhead (size_t allocated, s /* Helper function for prune_overhead_list. See if SLOT is still marked and remove it from hashtable if it is not. */ -static int -ggc_prune_ptr (void **slot, void *b ATTRIBUTE_UNUSED) +int +ggc_prune_ptr (ptr_hash_entry **slot, void *b ATTRIBUTE_UNUSED) { - struct ptr_hash_entry *p = (struct ptr_hash_entry *) *slot; + struct ptr_hash_entry *p = *slot; if (!ggc_marked_p (p->ptr)) { p->loc->collected += p->size; - htab_clear_slot (ptr_hash, slot); + ptr_hash.clear_slot (slot); free (p); } return 1; @@ -968,15 +979,15 @@ ggc_prune_ptr (void **slot, void *b ATTR void ggc_prune_overhead_list (void) { - htab_traverse (ptr_hash, ggc_prune_ptr, NULL); + ptr_hash.traverse (NULL); } /* Notice that the pointer has been freed. */ void ggc_free_overhead (void *ptr) { - PTR *slot = htab_find_slot_with_hash (ptr_hash, ptr, htab_hash_pointer (ptr), - NO_INSERT); + ptr_hash_entry **slot; + slot = ptr_hash.find_slot_with_hash (ptr, htab_hash_pointer (ptr), NO_INSERT); struct ptr_hash_entry *p; /* The pointer might be not found if a PCH read happened between allocation and ggc_free () call. FIXME: account memory properly in the presence of @@ -985,7 +996,7 @@ ggc_free_overhead (void *ptr) return; p = (struct ptr_hash_entry *) *slot; p->loc->freed += p->size; - htab_clear_slot (ptr_hash, slot); + ptr_hash.clear_slot (slot); free (p); } @@ -1024,11 +1035,10 @@ cmp_statistic (const void *loc1, const v /* Collect array of the descriptors from hashtable. */ static struct loc_descriptor **loc_array; -static int -add_statistics (void **slot, void *b) +int +ggc_add_statistics (loc_descriptor **slot, int *n) { - int *n = (int *)b; - loc_array[*n] = (struct loc_descriptor *) *slot; + loc_array[*n] = *slot; (*n)++; return 1; } @@ -1049,12 +1059,13 @@ dump_ggc_loc_statistics (bool final) ggc_force_collect = true; ggc_collect (); - loc_array = XCNEWVEC (struct loc_descriptor *, loc_hash->n_elements); + loc_array = XCNEWVEC (struct loc_descriptor *, + loc_hash.elements_with_deleted ()); fprintf (stderr, "-------------------------------------------------------\n"); fprintf (stderr, "\n%-48s %10s %10s %10s %10s %10s\n", "source location", "Garbage", "Freed", "Leak", "Overhead", "Times"); fprintf (stderr, "-------------------------------------------------------\n"); - htab_traverse (loc_hash, add_statistics, &nentries); + loc_hash.traverse (&nentries); qsort (loc_array, nentries, sizeof (*loc_array), final ? final_cmp_statistic : cmp_statistic); for (i = 0; i < nentries; i++) Index: gcc/Makefile.in =================================================================== --- gcc/Makefile.in (revision 193902) +++ gcc/Makefile.in (working copy) @@ -2108,7 +2108,7 @@ trans-mem.o : trans-mem.c $(CONFIG_H) $( gt-trans-mem.h ggc-common.o: ggc-common.c $(CONFIG_H) $(SYSTEM_H) coretypes.h \ - $(GGC_H) $(HASHTAB_H) $(DIAGNOSTIC_CORE_H) $(PARAMS_H) hosthooks.h \ + $(GGC_H) $(HASH_TABLE_H) $(DIAGNOSTIC_CORE_H) $(PARAMS_H) hosthooks.h \ $(HOSTHOOKS_DEF_H) $(VEC_H) $(PLUGIN_H) $(GGC_INTERNAL_H) $(TIMEVAR_H) ggc-page.o: ggc-page.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H)