From patchwork Thu Jun 5 19:45:10 2014 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Teresa Johnson X-Patchwork-Id: 356588 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 9A61D140087 for ; Fri, 6 Jun 2014 05:45:21 +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 :mime-version:date:message-id:subject:from:to:cc:content-type; q=dns; s=default; b=SQFzroqJSfS2HWd0ItFOTlIkOBxggZDzcxjM75hxag4 akiykHpm/q3E24BVyVLRHfudzgkUPio/fqHOE0JRXckXXCWQOdy9KHG53ci6Bfj9 lZJ0+hat9zPSTgc3Tno9gxll4AztJKJKrKjIOScYqe779N3uwAu9L20IdqDAYg4o = 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 :mime-version:date:message-id:subject:from:to:cc:content-type; s=default; bh=x7ja5/5RYHpwYup64eDnGgbZY6w=; b=pzKb/8bAcnmXZXhQh vGhl3wCWmAWWL0xMdIeSf6TJzxHj6Mw28yPr5wELJ7vc/gukkVX2hNAvb6nAKopM v9gTVQO2WVz1SW8eDbcW8TE3nB7pApC4CtLA6lQTvxEP1TTzd1fDHLjTvjj96EH6 2ahg2/PWW8jmCk/3RV1zJp9aYM= Received: (qmail 7411 invoked by alias); 5 Jun 2014 19:45:14 -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 7400 invoked by uid 89); 5 Jun 2014 19:45:14 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-2.9 required=5.0 tests=AWL, BAYES_00, RCVD_IN_DNSWL_NONE, RP_MATCHES_RCVD, SPF_PASS autolearn=ham version=3.3.2 X-HELO: mail-qg0-f45.google.com Received: from mail-qg0-f45.google.com (HELO mail-qg0-f45.google.com) (209.85.192.45) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with (AES128-SHA encrypted) ESMTPS; Thu, 05 Jun 2014 19:45:12 +0000 Received: by mail-qg0-f45.google.com with SMTP id z60so2364998qgd.4 for ; Thu, 05 Jun 2014 12:45:10 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:mime-version:date:message-id:subject:from:to:cc :content-type; bh=FG5TwlN+CmI02qwWkKSoEevrfXAqeBBla0ir5C2ct18=; b=bMRLx+KmKVS1Xj5a67Y2ZCn3dXNcQWmvGcH035UeK9wrH6JuipiRcmFbpydixHPhVi O2/StzGJAcm1ndF4TjxTNqcdviqAgkAO9bjIk15bHxYY7a8Rbs6dKYaPvAb4r6FwGBpX u7VrCM/VRJ3NgRQV6ug+xSXvHFexIOk7DEtxV2cKHWtpRfdaLy007d+Ag/zEMcfaYA4F hvo2xFS1QW5TtCH8bhTxMhtONVanCaov25RAIfHotUO14T2753okepqsRyZpm3Mt+Tj9 jf8KcCWHDAoBeVHiU0OipHX4K//zGTKF+knxdHtl8OV9D4XKnfLnxo5vbqHtHq9plcLl lXag== X-Gm-Message-State: ALoCoQmFBK1W/2iiJnues9y54EraUWm40Mw8NNx+kUqILPBE9eN18ojYZ/0V0zEOuOOY4AaJwsmu MIME-Version: 1.0 X-Received: by 10.224.165.148 with SMTP id i20mr21024644qay.41.1401997510266; Thu, 05 Jun 2014 12:45:10 -0700 (PDT) Received: by 10.229.208.67 with HTTP; Thu, 5 Jun 2014 12:45:10 -0700 (PDT) Date: Thu, 5 Jun 2014 12:45:10 -0700 Message-ID: Subject: [Google/4_8] Reduce memory overhead of LIPO COMDAT fixups From: Teresa Johnson To: "gcc-patches@gcc.gnu.org" , Rong Xu Cc: David Li , Dehao Chen , Easwaran Raman , Paul Pluzhnikov X-IsSubscribed: yes (cc'ing a few additional people to help with review as David is out and I'm not sure Rong is available) This patch greatly reduces the memory overhead of the new COMDAT fixup analysis, by changing the second level hash tables to linked lists. I found that almost none of the second level hash tables contained more than one entry, but each hash table required a lot of memory overhead. I also now query the fixup type before adding the checksums to the pointer sets during callgraph building, which would have enabled a workaround for the memory issue. Tested with regression tests and internal tests (see ref below for details). Google ref b/15415042. 2014-06-05 Teresa Johnson * dyn-ipa.c (struct lineno_checksum_alias): Replaced pointer set. (struct checksum_alias_info): Enabled linked list. (cfg_checksum_get_key): Removed. (find_cfg_checksum): New function. (cfg_checksum_insert): Operate on linked list. (checksum_set_insert): Ditto. (gcov_build_callgraph): Allow disabling checksum insertion. (gcov_find_new_ic_target): Operate on linked list. (gcov_fixup_counters_checksum): Ditto. (gcov_fixup_counters_lineno): Ditto. (__gcov_compute_module_groups): Compute fixup type earlier. } @@ -844,9 +853,10 @@ gcov_build_callgraph (void) total_arc_count += ci_ptr->values[arc]; if (total_arc_count != 0) the_dyn_call_graph.num_nodes_executed++; - checksum_set_insert (fi_ptr->lineno_checksum, - fi_ptr->cfg_checksum, caller->guid, - fi_ptr, total_arc_count == 0); + if (fixup_type) + checksum_set_insert (fi_ptr->lineno_checksum, + fi_ptr->cfg_checksum, caller->guid, + fi_ptr, total_arc_count == 0); } ci_ptr++; } @@ -2454,10 +2464,10 @@ gcov_find_new_ic_target (gcov_type caller_guid, gc struct lineno_checksum_alias **line_alias = (struct lineno_checksum_alias **) pointer_set_find_or_insert (p, callee_fi_ptr->lineno_checksum); gcc_assert (*line_alias); - struct checksum_alias_info **cfg_alias = (struct checksum_alias_info **) - pointer_set_find_or_insert ((*line_alias)->cfg_pointer_set, - callee_fi_ptr->cfg_checksum); - gcc_assert (*cfg_alias); + struct checksum_alias_info *cfg_alias + = find_cfg_checksum ((*line_alias)->cfg_checksum_list, + callee_fi_ptr->cfg_checksum); + gcc_assert (cfg_alias); /* Scan the list of checksum aliases for one that is located in caller's @@ -2465,7 +2475,7 @@ gcov_find_new_ic_target (gcov_type caller_guid, gc gcov_type new_guid = 0; unsigned caller_mod_id = get_module_ident_from_func_glob_uid (caller_guid); struct checksum_alias *alias; - for (alias = (*cfg_alias)->alias_list; alias; + for (alias = cfg_alias->alias_list; alias; alias = alias->next_alias) { if (get_module_ident_from_func_glob_uid (alias->guid) @@ -2901,24 +2911,18 @@ merge_ctrs (struct gcov_ctr_info *dest_ctrs, } /* Walks the set of functions that have the same lineno and cfg checksum, and - performs counter merging. VALUE contains the checksum_alias_info structure - for a given lineno and cfg checksum combination, and DATA1 contains a pointer + performs counter merging. INFO contains the checksum_alias_info structure + for a given lineno and cfg checksum combination. CHANGED points to a flag that should be set to 1 if any fixups were applied. */ static int -gcov_fixup_counters_checksum (const void *value, - void *data1, - void *data2 ATTRIBUTE_UNUSED, - void *data3 ATTRIBUTE_UNUSED) +gcov_fixup_counters_checksum (const struct checksum_alias_info *info, + int *changed) { - const struct checksum_alias_info *a - = (const struct checksum_alias_info*) value; - int *changed = (int *) data1; - /* See if there are any zero count functions to fix. */ int found = 0; struct checksum_alias *alias; - for (alias = a->alias_list; alias; + for (alias = info->alias_list; alias; alias = alias->next_alias) { if (alias->zero_counts) @@ -2933,7 +2937,7 @@ static int /* Walk the aliases and merge the non-zero counters into a dummy copy. */ struct gcov_ctr_info *merged_ctrs = init_merged_ctrs (); found = 0; - for (alias = a->alias_list; alias; + for (alias = info->alias_list; alias; alias = alias->next_alias) { if (alias->zero_counts) @@ -2951,7 +2955,7 @@ static int *changed = 1; /* Walk them again and copy the merged counters into 0-count copies. */ - for (alias = a->alias_list; alias; + for (alias = info->alias_list; alias; alias = alias->next_alias) { if (!alias->zero_counts) @@ -2977,9 +2981,11 @@ gcov_fixup_counters_lineno (const void *value, const struct lineno_checksum_alias *a = (const struct lineno_checksum_alias*) value; int *changed = (int *) data1; - pointer_set_traverse (a->cfg_pointer_set, - gcov_fixup_counters_checksum, - changed, 0, 0); + struct checksum_alias_info *cfg_alias_list = a->cfg_checksum_list; + for (; cfg_alias_list; cfg_alias_list = cfg_alias_list->next_cfg_checksum) + { + gcov_fixup_counters_checksum (cfg_alias_list, changed); + } return 1; } @@ -3046,6 +3052,12 @@ __gcov_compute_module_groups (void) return 0; } + const char *do_fixup = 0; + fixup_type = __gcov_lipo_comdat_algorithm; + do_fixup = getenv ("GCOV_DYN_DO_FIXUP"); + if (do_fixup) + fixup_type = atoi (do_fixup); + /* First compute dynamic call graph. */ gcov_build_callgraph (); @@ -3055,12 +3067,6 @@ __gcov_compute_module_groups (void) gcov_dump_callgraph (cut_off_count); - const char *do_fixup = 0; - int fixup_type = __gcov_lipo_comdat_algorithm; - do_fixup = getenv ("GCOV_DYN_DO_FIXUP"); - if (do_fixup) - fixup_type = atoi (do_fixup); - int changed = 0; if (fixup_type & 0x2) changed |= gcov_fixup_zero_counters (); Index: dyn-ipa.c =================================================================== --- dyn-ipa.c (revision 211288) +++ dyn-ipa.c (working copy) @@ -79,16 +79,15 @@ struct dyn_cgraph unsigned num_nodes_executed; /* used by new algorithm */ struct modu_node *modu_nodes; - /* Set indexed by lineno_checksum, returns another dyn_pointer_set*, - indexed by cfg_checksum. That returns a checksum_alias_info struct. */ + /* Set indexed by lineno_checksum, returns a linked list of + checksum_alias_info structs. */ struct dyn_pointer_set *lineno_pointer_sets; }; /* Struct holding information for functions with the same lineno_checksum. */ struct lineno_checksum_alias { - /* Set indexed by cfg_checksum, holding a checksum_alias_info struct. */ - struct dyn_pointer_set *cfg_pointer_set; + struct checksum_alias_info *cfg_checksum_list; unsigned lineno_checksum; }; @@ -96,6 +95,7 @@ struct lineno_checksum_alias checksums. */ struct checksum_alias_info { + struct checksum_alias_info *next_cfg_checksum; struct checksum_alias *alias_list; unsigned cfg_checksum; }; @@ -205,6 +205,7 @@ pointer_set_create (unsigned (*get_key) (const voi static struct dyn_cgraph the_dyn_call_graph; static int total_zero_count = 0; static int total_insane_count = 0; +static int fixup_type = 0; enum GROUPING_ALGORITHM { @@ -374,14 +375,6 @@ lineno_checksum_get_key (const void *p) return ((const struct lineno_checksum_alias *) p)->lineno_checksum; } -/* The cfg_checksum value in P is the key for a cfg_pointer_set. */ - -static inline unsigned -cfg_checksum_get_key (const void *p) -{ - return ((const struct checksum_alias_info *) p)->cfg_checksum; -} - /* Create a new checksum_alias struct for function with GUID, FI_PTR, and ZERO_COUNTS flag. Prepends to list NEXT and returns new struct. */ @@ -398,28 +391,44 @@ new_checksum_alias (gcov_type guid, const struct g return alias; } -/* Insert a new checksum_alias struct into pointer set P for function with +/* Locate the checksum_alias_info in LIST that matches CFG_CHECKSUM. */ + +static struct checksum_alias_info * +find_cfg_checksum (struct checksum_alias_info *list, unsigned cfg_checksum) +{ + for (; list; list = list->next_cfg_checksum) + { + if (list->cfg_checksum == cfg_checksum) + return list; + } + return NULL; +} + +/* Insert a new checksum_alias struct into LIST for function with CFG_CHECKSUM and associated GUID, FI_PTR, and ZERO_COUNTS flag. */ -static void -cfg_checksum_set_insert (struct dyn_pointer_set *p, unsigned cfg_checksum, - gcov_type guid, const struct gcov_fn_info *fi_ptr, - int zero_counts) +static struct checksum_alias_info * +cfg_checksum_insert (unsigned cfg_checksum, gcov_type guid, + const struct gcov_fn_info *fi_ptr, int zero_counts, + struct checksum_alias_info *list) { - struct checksum_alias_info **m = (struct checksum_alias_info **) - pointer_set_find_or_insert (p, cfg_checksum); - if (*m) + struct checksum_alias_info *alias_info; + alias_info = find_cfg_checksum (list, cfg_checksum); + if (alias_info) { - gcc_assert ((*m)->alias_list); - (*m)->alias_list = new_checksum_alias (guid, fi_ptr, zero_counts, - (*m)->alias_list); + gcc_assert (alias_info->alias_list); + alias_info->alias_list = new_checksum_alias (guid, fi_ptr, zero_counts, + alias_info->alias_list); + return list; } else { - *m = XNEW (struct checksum_alias_info); - (*m)->cfg_checksum = cfg_checksum; - (*m)->alias_list = new_checksum_alias (guid, fi_ptr, zero_counts, NULL); - p->n_elements++; + alias_info = XNEW (struct checksum_alias_info); + alias_info->next_cfg_checksum = list; + alias_info->cfg_checksum = cfg_checksum; + alias_info->alias_list = new_checksum_alias (guid, fi_ptr, zero_counts, + NULL); + return alias_info; } } @@ -440,16 +449,16 @@ checksum_set_insert (unsigned lineno_checksum, uns pointer_set_find_or_insert (p, lineno_checksum); if (*m) { - cfg_checksum_set_insert ((*m)->cfg_pointer_set, cfg_checksum, guid, - fi_ptr, zero_counts); + (*m)->cfg_checksum_list = cfg_checksum_insert (cfg_checksum, guid, + fi_ptr, zero_counts, + (*m)->cfg_checksum_list); } else { *m = XNEW (struct lineno_checksum_alias); (*m)->lineno_checksum = lineno_checksum; - (*m)->cfg_pointer_set = pointer_set_create (cfg_checksum_get_key); - cfg_checksum_set_insert ((*m)->cfg_pointer_set, cfg_checksum, guid, - fi_ptr, zero_counts); + (*m)->cfg_checksum_list = cfg_checksum_insert (cfg_checksum, guid, + fi_ptr, zero_counts, NULL); p->n_elements++; }