From patchwork Mon Apr 6 08:03:59 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: =?utf-8?q?Martin_Li=C5=A1ka?= X-Patchwork-Id: 1266702 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Authentication-Results: ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=gcc.gnu.org (client-ip=2620:52:3:1:0:246e:9693:128c; helo=sourceware.org; envelope-from=gcc-patches-bounces@gcc.gnu.org; receiver=) Authentication-Results: ozlabs.org; dmarc=none (p=none dis=none) header.from=suse.cz Received: from sourceware.org (server2.sourceware.org [IPv6:2620:52:3:1:0:246e:9693:128c]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 48wjjk6Tfxz9sP7 for ; Mon, 6 Apr 2020 18:04:09 +1000 (AEST) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 26064385C019; Mon, 6 Apr 2020 08:04:05 +0000 (GMT) X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from mx2.suse.de (mx2.suse.de [195.135.220.15]) by sourceware.org (Postfix) with ESMTPS id 1597E385C019 for ; Mon, 6 Apr 2020 08:04:01 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.3.2 sourceware.org 1597E385C019 Authentication-Results: sourceware.org; dmarc=none (p=none dis=none) header.from=suse.cz Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=mliska@suse.cz X-Virus-Scanned: by amavisd-new at test-mx.suse.de Received: from relay2.suse.de (unknown [195.135.220.254]) by mx2.suse.de (Postfix) with ESMTP id 88BD3AD26; Mon, 6 Apr 2020 08:03:59 +0000 (UTC) From: =?utf-8?q?Martin_Li=C5=A1ka?= Subject: [stage1][PATCH] Make TOPN counter dynamically allocated. To: gcc-patches@gcc.gnu.org Message-ID: Date: Mon, 6 Apr 2020 10:03:59 +0200 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:68.0) Gecko/20100101 Thunderbird/68.6.0 MIME-Version: 1.0 Content-Language: en-US X-Spam-Status: No, score=-29.7 required=5.0 tests=BAYES_00, GIT_PATCH_0, GIT_PATCH_1, GIT_PATCH_2, GIT_PATCH_3, KAM_DMARC_STATUS, RCVD_IN_MSPIKE_H3, RCVD_IN_MSPIKE_WL, SPF_HELO_NONE, SPF_PASS, TXREP autolearn=ham autolearn_force=no version=3.4.2 X-Spam-Checker-Version: SpamAssassin 3.4.2 (2018-09-13) on server2.sourceware.org X-BeenThere: gcc-patches@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gcc-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Cc: Jan Hubicka Errors-To: gcc-patches-bounces@gcc.gnu.org Sender: "Gcc-patches" Hi. We've started discussion the patch with Honza when we started working on reproducibility of -fprofile-generate/use. The patch replaces pre-allocated TOP N counters with a dynamical linked list allocation that happens during profiling. The similar approach is used by Clang and it provides these benefits: 1) addition to linked list is being done atomically, we should not end up with corrupted profiles 2) we waste a pointer per each key-value-pair, but we reduce memory footprint for counters that are not used 3) the method provide better stability results, there are collected stats for GCC PGO build: Covered threshold: 0.25 == Stats for /home/marxin/Programming/gcc/objdir/gcc == stats for indirect_call: Total: 9240, total freq: 5999706513, covered freq: 4309848999 (71.83%), missing freq: 14248293 (0.24%) Total tuples: 8759 (size before: 9*N=83160, after: 2*N + (2*TUPLE_COUNT)=35998 Histogram: 0 tracked: 6278 (67.94%), >=0.25: 0 (cov. freq: 0 (0.00%)) 1 tracked: 1784 (19.31%), >=0.25: 1784 (cov. freq: 2276692405 (37.95%)) 2 tracked: 222 (2.40%), >=0.25: 300 (cov. freq: 575634854 (9.59%)) 3 tracked: 79 (0.85%), >=0.25: 143 (cov. freq: 220498760 (3.68%)) 4 tracked: 78 (0.84%), >=0.25: 135 (cov. freq: 160196399 (2.67%)) 5 tracked: 105 (1.14%), >=0.25: 162 (cov. freq: 48169245 (0.80%)) 6 tracked: 239 (2.59%), >=0.25: 369 (cov. freq: 115649188 (1.93%)) 7 tracked: 135 (1.46%), >=0.25: 210 (cov. freq: 11660200 (0.19%)) 8 tracked: 224 (2.42%), >=0.25: 260 (cov. freq: 313294659 (5.22%)) 9 tracked: 62 (0.67%), >=0.25: 50 (cov. freq: 222127899 (3.70%)) 10 tracked: 2 (0.02%), >=0.25: 3 (cov. freq: 334914 (0.01%)) 11 tracked: 2 (0.02%), >=0.25: 1 (cov. freq: 2454696 (0.04%)) 12 tracked: 2 (0.02%), >=0.25: 3 (cov. freq: 981658 (0.02%)) 13 tracked: 4 (0.04%), >=0.25: 3 (cov. freq: 23617640 (0.39%)) 14 tracked: 4 (0.04%), >=0.25: 4 (cov. freq: 9493736 (0.16%)) 17 tracked: 2 (0.02%), >=0.25: 3 (cov. freq: 8416719 (0.14%)) 20 tracked: 1 (0.01%), >=0.25: 1 (cov. freq: 5041813 (0.08%)) 21 tracked: 3 (0.03%), >=0.25: 4 (cov. freq: 23487922 (0.39%)) 27 tracked: 1 (0.01%), >=0.25: 1 (cov. freq: 99561333 (1.66%)) 28 tracked: 1 (0.01%), >=0.25: 2 (cov. freq: 64012144 (1.07%)) 30 tracked: 1 (0.01%), >=0.25: 1 (cov. freq: 114573384 (1.91%)) 32 tracked: 11 (0.12%), >=0.25: 8 (cov. freq: 13949431 (0.23%)) stats for topn: Total: 1519, total freq: 1660520369, covered freq: 767273373 (46.21%), missing freq: 84286328 (5.08%) Total tuples: 5365 (size before: 9*N=13671, after: 2*N + (2*TUPLE_COUNT)=13768 Histogram: 0 tracked: 1032 (67.94%), >=0.25: 0 (cov. freq: 0 (0.00%)) 1 tracked: 154 (10.14%), >=0.25: 154 (cov. freq: 240913892 (14.51%)) 2 tracked: 43 (2.83%), >=0.25: 62 (cov. freq: 28671331 (1.73%)) 3 tracked: 38 (2.50%), >=0.25: 56 (cov. freq: 72179614 (4.35%)) 4 tracked: 23 (1.51%), >=0.25: 38 (cov. freq: 9598177 (0.58%)) 5 tracked: 36 (2.37%), >=0.25: 48 (cov. freq: 89840680 (5.41%)) 6 tracked: 13 (0.86%), >=0.25: 17 (cov. freq: 4548625 (0.27%)) 7 tracked: 8 (0.53%), >=0.25: 10 (cov. freq: 23456524 (1.41%)) 8 tracked: 6 (0.39%), >=0.25: 6 (cov. freq: 357781 (0.02%)) 9 tracked: 2 (0.13%), >=0.25: 2 (cov. freq: 266881 (0.02%)) 10 tracked: 5 (0.33%), >=0.25: 5 (cov. freq: 68985 (0.00%)) 11 tracked: 6 (0.39%), >=0.25: 7 (cov. freq: 6216337 (0.37%)) 12 tracked: 1 (0.07%), >=0.25: 1 (cov. freq: 892 (0.00%)) 13 tracked: 11 (0.72%), >=0.25: 11 (cov. freq: 70639704 (4.25%)) 14 tracked: 3 (0.20%), >=0.25: 1 (cov. freq: 16524 (0.00%)) 15 tracked: 1 (0.07%), >=0.25: 0 (cov. freq: 0 (0.00%)) 16 tracked: 1 (0.07%), >=0.25: 1 (cov. freq: 106363 (0.01%)) 17 tracked: 1 (0.07%), >=0.25: 0 (cov. freq: 0 (0.00%)) 18 tracked: 2 (0.13%), >=0.25: 3 (cov. freq: 32033 (0.00%)) 20 tracked: 1 (0.07%), >=0.25: 0 (cov. freq: 0 (0.00%)) 21 tracked: 3 (0.20%), >=0.25: 2 (cov. freq: 355742 (0.02%)) 22 tracked: 1 (0.07%), >=0.25: 1 (cov. freq: 624 (0.00%)) 24 tracked: 3 (0.20%), >=0.25: 2 (cov. freq: 1684949 (0.10%)) 25 tracked: 1 (0.07%), >=0.25: 1 (cov. freq: 655 (0.00%)) 26 tracked: 2 (0.13%), >=0.25: 2 (cov. freq: 72971 (0.00%)) 27 tracked: 1 (0.07%), >=0.25: 0 (cov. freq: 0 (0.00%)) 28 tracked: 1 (0.07%), >=0.25: 1 (cov. freq: 14053 (0.00%)) 30 tracked: 3 (0.20%), >=0.25: 1 (cov. freq: 99046 (0.01%)) 31 tracked: 1 (0.07%), >=0.25: 2 (cov. freq: 2055 (0.00%)) 32 tracked: 116 (7.64%), >=0.25: 55 (cov. freq: 218128935 (13.14%)) Patch can bootstrap on x86_64-linux-gnu and survives regression tests. Ready to be installed in next stage1? Thanks, Martin gcc/ChangeLog: 2020-04-03 Martin Liska * coverage.c (get_coverage_counts): Skip sanity check for TOP N counters as they have variable number of counters. * gcov-dump.c (main): Add new option -r. (print_usage): Likewise. (tag_counters): All new raw format. * gcov-io.h (struct gcov_kvp): New. (GCOV_TOPN_VALUES): Remove. (GCOV_TOPN_VALUES_COUNTERS): Likewise. (GCOV_TOPN_MEM_COUNTERS): New. (GCOV_TOPN_DISK_COUNTERS): Likewise. (GCOV_TOPN_MAXIMUM_TRACKED_VALUES): Likewise. * ipa-profile.c (ipa_profile_generate_summary): Use GCOV_TOPN_MAXIMUM_TRACKED_VALUES. (ipa_profile_write_edge_summary): Likewise. (ipa_profile_read_edge_summary): Likewise. (ipa_profile): Remove usage of GCOV_TOPN_VALUES. * profile.c (sort_hist_values): Sort variable number of counters. (compute_value_histograms): Special case for TOP N counters that have dynamic number of key-value pairs. * value-prof.c (dump_histogram_value): Dump variable number of key-value pairs. (stream_in_histogram_value): Stream in variable number of key-value pairs for TOP N counter. (get_nth_most_common_value): Deal with variable number of key-value pairs. (dump_ic_profile): Use GCOV_TOPN_MAXIMUM_TRACKED_VALUES for loop iteration. (gimple_find_values_to_profile): Set GCOV_TOPN_MEM_COUNTERS to n_counters. * doc/gcov-dump.texi: Document new -r option. libgcc/ChangeLog: 2020-04-03 Martin Liska * libgcov-driver.c (prune_topn_counter): Remove. (prune_counters): Likewise. (merge_one_data): Special case TOP N counters as they have variable length. (write_top_counters): New. (write_one_data): Special case TOP N. (dump_one_gcov): Do not prune TOP N counters. * libgcov-merge.c (merge_topn_values_set): Remove. (__gcov_merge_topn): Use gcov_topn_add_value. * libgcov-profiler.c (__gcov_topn_values_profiler_body): Likewise here. * libgcov.h (gcov_counter_add): New. (gcov_counter_set_if_null): Likewise. (gcov_topn_add_value): New. --- gcc/coverage.c | 7 ++- gcc/doc/gcov-dump.texi | 5 ++ gcc/gcov-dump.c | 14 ++++- gcc/gcov-io.h | 22 ++++++-- gcc/ipa-profile.c | 11 ++-- gcc/profile.c | 70 +++++++++++++---------- gcc/value-prof.c | 59 ++++++++++++------- libgcc/libgcov-driver.c | 116 ++++++++++++++++++-------------------- libgcc/libgcov-merge.c | 103 +++++++-------------------------- libgcc/libgcov-profiler.c | 40 +------------ libgcc/libgcov.h | 87 ++++++++++++++++++++++++++++ 11 files changed, 285 insertions(+), 249 deletions(-) diff --git a/gcc/coverage.c b/gcc/coverage.c index 30ae84df90f..e56807399a4 100644 --- a/gcc/coverage.c +++ b/gcc/coverage.c @@ -344,8 +344,11 @@ get_coverage_counts (unsigned counter, unsigned cfg_checksum, can do about it. */ return NULL; } - - if (entry->cfg_checksum != cfg_checksum || entry->n_counts != n_counts) + + if (entry->cfg_checksum != cfg_checksum + || (counter != GCOV_COUNTER_V_INDIR + && counter != GCOV_COUNTER_V_TOPN + && entry->n_counts != n_counts)) { static int warned = 0; bool warning_printed = false; diff --git a/gcc/doc/gcov-dump.texi b/gcc/doc/gcov-dump.texi index 776c0d591a4..419df988df4 100644 --- a/gcc/doc/gcov-dump.texi +++ b/gcc/doc/gcov-dump.texi @@ -61,6 +61,7 @@ gcov-dump [@option{-v}|@option{--version}] [@option{-h}|@option{--help}] [@option{-l}|@option{--long}] [@option{-p}|@option{--positions}] + [@option{-r}|@option{--raw}] @var{gcovfiles} @c man end @end ignore @@ -80,6 +81,10 @@ Dump content of records. @itemx --positions Dump positions of records. +@item -r +@itemx --raw +Print content records in raw format. + @item -v @itemx --version Display the @command{gcov-dump} version number (on the standard output), diff --git a/gcc/gcov-dump.c b/gcc/gcov-dump.c index bd2ae223ac6..90cbd1ace52 100644 --- a/gcc/gcov-dump.c +++ b/gcc/gcov-dump.c @@ -49,6 +49,7 @@ typedef struct tag_format static int flag_dump_contents = 0; static int flag_dump_positions = 0; +static int flag_dump_raw = 0; static const struct option options[] = { @@ -95,7 +96,7 @@ main (int argc ATTRIBUTE_UNUSED, char **argv) diagnostic_initialize (global_dc, 0); - while ((opt = getopt_long (argc, argv, "hlpvw", options, NULL)) != -1) + while ((opt = getopt_long (argc, argv, "hlprvw", options, NULL)) != -1) { switch (opt) { @@ -111,6 +112,9 @@ main (int argc ATTRIBUTE_UNUSED, char **argv) case 'p': flag_dump_positions = 1; break; + case 'r': + flag_dump_raw = 1; + break; default: fprintf (stderr, "unknown flag `%c'\n", opt); } @@ -129,6 +133,7 @@ print_usage (void) printf (" -h, --help Print this help\n"); printf (" -l, --long Dump record contents too\n"); printf (" -p, --positions Dump record positions\n"); + printf (" -r, --raw Print content records in raw format\n"); printf (" -v, --version Print version number\n"); printf ("\nFor bug reporting instructions, please see:\n%s.\n", bug_report_url); @@ -441,7 +446,12 @@ tag_counters (const char *filename ATTRIBUTE_UNUSED, { gcov_type count; - if (!(ix & 7)) + if (flag_dump_raw) + { + if (ix == 0) + printf (": "); + } + else if (!(ix & 7)) { printf ("\n"); print_prefix (filename, depth, gcov_position ()); diff --git a/gcc/gcov-io.h b/gcc/gcov-io.h index d21a43c4c31..33c96db3d55 100644 --- a/gcc/gcov-io.h +++ b/gcc/gcov-io.h @@ -164,6 +164,17 @@ see the files COPYING3 and COPYING.RUNTIME respectively. If not, see #ifndef GCC_GCOV_IO_H #define GCC_GCOV_IO_H +/* GCOV key-value pair linked list type. */ + +struct gcov_kvp; + +struct gcov_kvp +{ + gcov_type value; + gcov_type count; + struct gcov_kvp *next; +}; + #ifndef IN_LIBGCOV /* About the host */ @@ -266,11 +277,14 @@ GCOV_COUNTERS #define GCOV_N_VALUE_COUNTERS \ (GCOV_LAST_VALUE_COUNTER - GCOV_FIRST_VALUE_COUNTER + 1) -/* Number of top N value histogram. */ -#define GCOV_TOPN_VALUES 4 +/* Number of top N counters when being in memory. */ +#define GCOV_TOPN_MEM_COUNTERS 3 + +/* Number of top N counters in disk representation. */ +#define GCOV_TOPN_DISK_COUNTERS 2 -/* Total number of single value counters. */ -#define GCOV_TOPN_VALUES_COUNTERS (2 * GCOV_TOPN_VALUES + 1) +/* Maximum number of tracked TOP N value profiles. */ +#define GCOV_TOPN_MAXIMUM_TRACKED_VALUES 32 /* Convert a counter index to a tag. */ #define GCOV_TAG_FOR_COUNTER(COUNT) \ diff --git a/gcc/ipa-profile.c b/gcc/ipa-profile.c index 9fbfa90e538..43e9b6bb4db 100644 --- a/gcc/ipa-profile.c +++ b/gcc/ipa-profile.c @@ -295,7 +295,8 @@ ipa_profile_generate_summary (void) speculative_call_summary *csum = call_sums->get_create (e); - for (unsigned j = 0; j < GCOV_TOPN_VALUES; j++) + for (unsigned j = 0; j < GCOV_TOPN_MAXIMUM_TRACKED_VALUES; + j++) { if (!get_nth_most_common_value (NULL, "indirect call", h, &val, &count, &all, @@ -342,7 +343,7 @@ ipa_profile_write_edge_summary (lto_simple_output_block *ob, len = csum->speculative_call_targets.length (); - gcc_assert (len <= GCOV_TOPN_VALUES); + gcc_assert (len <= GCOV_TOPN_MAXIMUM_TRACKED_VALUES); streamer_write_hwi_stream (ob->main_stream, len); @@ -448,8 +449,7 @@ ipa_profile_read_edge_summary (class lto_input_block *ib, cgraph_edge *edge) unsigned i, len; len = streamer_read_hwi (ib); - gcc_assert (len <= GCOV_TOPN_VALUES); - + gcc_assert (len <= GCOV_TOPN_MAXIMUM_TRACKED_VALUES); speculative_call_summary *csum = call_sums->get_create (edge); for (i = 0; i < len; i++) @@ -885,8 +885,7 @@ ipa_profile (void) item.target_probability / (float) REG_BR_PROB_BASE); } - if (item.target_probability - < REG_BR_PROB_BASE / GCOV_TOPN_VALUES / 2) + if (item.target_probability < REG_BR_PROB_BASE / 2) { nuseless++; if (dump_file) diff --git a/gcc/profile.c b/gcc/profile.c index cd754c4c66a..bd1eac123df 100644 --- a/gcc/profile.c +++ b/gcc/profile.c @@ -765,26 +765,22 @@ compute_branch_probabilities (unsigned cfg_checksum, unsigned lineno_checksum) static void sort_hist_values (histogram_value hist) { - /* counters[2] equal to -1 means that all counters are invalidated. */ - if (hist->hvalue.counters[2] == -1) - return; - gcc_assert (hist->type == HIST_TYPE_TOPN_VALUES || hist->type == HIST_TYPE_INDIR_CALL); - gcc_assert (hist->n_counters == GCOV_TOPN_VALUES_COUNTERS); - + int counters = hist->hvalue.counters[1]; + for (int i = 0; i < counters - 1; i++) /* Hist value is organized as: - [total_executions, value1, counter1, ..., value4, counter4] + [total_executions, N, counter1, ..., valueN, counterN] Use decrease bubble sort to rearrange it. The sort starts from and compares counter first. If counter is same, compares the value, exchange it if small to keep stable. */ - for (unsigned i = 0; i < GCOV_TOPN_VALUES - 1; i++) + { bool swapped = false; - for (unsigned j = 0; j < GCOV_TOPN_VALUES - 1 - i; j++) + for (int j = 0; j < counters - 1 - i; j++) { - gcov_type *p = &hist->hvalue.counters[2 * j + 1]; + gcov_type *p = &hist->hvalue.counters[2 * j + 2]; if (p[1] < p[3] || (p[1] == p[3] && p[0] < p[2])) { std::swap (p[0], p[2]); @@ -847,31 +843,43 @@ compute_value_histograms (histogram_values values, unsigned cfg_checksum, gimple *stmt = hist->hvalue.stmt; t = (int) hist->type; + bool topn_p = (hist->type == HIST_TYPE_TOPN_VALUES + || hist->type == HIST_TYPE_INDIR_CALL); - aact_count = act_count[t]; - - if (act_count[t]) - act_count[t] += hist->n_counters; - - gimple_add_histogram_value (cfun, stmt, hist); - hist->hvalue.counters = XNEWVEC (gcov_type, hist->n_counters); - for (j = 0; j < hist->n_counters; j++) - if (aact_count) - hist->hvalue.counters[j] = aact_count[j]; - else - hist->hvalue.counters[j] = 0; - - if (hist->type == HIST_TYPE_TOPN_VALUES - || hist->type == HIST_TYPE_INDIR_CALL) + /* TOP N counter uses variable number of counters. */ + if (topn_p) { - /* Each count value is multiplied by GCOV_TOPN_VALUES. */ - if (hist->hvalue.counters[2] != -1) - for (unsigned i = 0; i < GCOV_TOPN_VALUES; i++) - hist->hvalue.counters[2 * i + 2] - = RDIV (hist->hvalue.counters[2 * i + 2], GCOV_TOPN_VALUES); - + unsigned total_size; + if (act_count[t]) + total_size = 2 + 2 * act_count[t][1]; + else + total_size = 2; + gimple_add_histogram_value (cfun, stmt, hist); + hist->n_counters = total_size; + hist->hvalue.counters = XNEWVEC (gcov_type, hist->n_counters); + for (j = 0; j < hist->n_counters; j++) + if (act_count[t]) + hist->hvalue.counters[j] = act_count[t][j]; + else + hist->hvalue.counters[j] = 0; + act_count[t] += hist->n_counters; sort_hist_values (hist); } + else + { + aact_count = act_count[t]; + + if (act_count[t]) + act_count[t] += hist->n_counters; + + gimple_add_histogram_value (cfun, stmt, hist); + hist->hvalue.counters = XNEWVEC (gcov_type, hist->n_counters); + for (j = 0; j < hist->n_counters; j++) + if (aact_count) + hist->hvalue.counters[j] = aact_count[j]; + else + hist->hvalue.counters[j] = 0; + } /* Time profiler counter is not related to any statement, so that we have to read the counter and set the value to diff --git a/gcc/value-prof.c b/gcc/value-prof.c index 45677be46b1..ea1b1a8f98f 100644 --- a/gcc/value-prof.c +++ b/gcc/value-prof.c @@ -265,16 +265,15 @@ dump_histogram_value (FILE *dump_file, histogram_value hist) ? "Top N value counter" : "Indirect call counter")); if (hist->hvalue.counters) { - fprintf (dump_file, " all: %" PRId64 "%s, values: ", - (int64_t) abs_hwi (hist->hvalue.counters[0]), - hist->hvalue.counters[0] < 0 - ? " (values missing)": ""); - for (unsigned i = 0; i < GCOV_TOPN_VALUES; i++) + unsigned count = hist->hvalue.counters[1]; + fprintf (dump_file, " all: %" PRId64 ", %" PRId64 " values: ", + (int64_t) hist->hvalue.counters[0], (int64_t) count); + for (unsigned i = 0; i < count; i++) { fprintf (dump_file, "[%" PRId64 ":%" PRId64 "]", - (int64_t) hist->hvalue.counters[2 * i + 1], - (int64_t) hist->hvalue.counters[2 * i + 2]); - if (i != GCOV_TOPN_VALUES - 1) + (int64_t) hist->hvalue.counters[2 * i + 2], + (int64_t) hist->hvalue.counters[2 * i + 3]); + if (i != count - 1) fprintf (dump_file, ", "); } fprintf (dump_file, ".\n"); @@ -377,7 +376,6 @@ stream_in_histogram_value (class lto_input_block *ib, gimple *stmt) case HIST_TYPE_TOPN_VALUES: case HIST_TYPE_INDIR_CALL: - ncounters = GCOV_TOPN_VALUES_COUNTERS; break; case HIST_TYPE_IOR: @@ -388,12 +386,31 @@ stream_in_histogram_value (class lto_input_block *ib, gimple *stmt) default: gcc_unreachable (); } - new_val->hvalue.counters = XNEWVAR (gcov_type, - sizeof (*new_val->hvalue.counters) - * ncounters); - new_val->n_counters = ncounters; - for (i = 0; i < ncounters; i++) - new_val->hvalue.counters[i] = streamer_read_gcov_count (ib); + + /* TOP N counters have variable number of counters. */ + if (type == HIST_TYPE_INDIR_CALL || type == HIST_TYPE_TOPN_VALUES) + { + gcov_type total = streamer_read_gcov_count (ib); + gcov_type ncounters = streamer_read_gcov_count (ib); + new_val->hvalue.counters = XNEWVAR (gcov_type, + sizeof (*new_val->hvalue.counters) + * (2 + 2 * ncounters)); + new_val->hvalue.counters[0] = total; + new_val->hvalue.counters[1] = ncounters; + new_val->n_counters = 2 + 2 * ncounters; + for (i = 0; i < 2 * ncounters; i++) + new_val->hvalue.counters[2 + i] = streamer_read_gcov_count (ib); + } + else + { + new_val->hvalue.counters = XNEWVAR (gcov_type, + sizeof (*new_val->hvalue.counters) + * ncounters); + new_val->n_counters = ncounters; + for (i = 0; i < ncounters; i++) + new_val->hvalue.counters[i] = streamer_read_gcov_count (ib); + } + if (!next_p) gimple_add_histogram_value (cfun, stmt, new_val); else @@ -738,15 +755,17 @@ get_nth_most_common_value (gimple *stmt, const char *counter_type, histogram_value hist, gcov_type *value, gcov_type *count, gcov_type *all, unsigned n) { - gcc_assert (n < GCOV_TOPN_VALUES); + unsigned counters = hist->hvalue.counters[1]; + if (n >= counters) + return false; *count = 0; *value = 0; gcov_type read_all = abs_hwi (hist->hvalue.counters[0]); - gcov_type v = hist->hvalue.counters[2 * n + 1]; - gcov_type c = hist->hvalue.counters[2 * n + 2]; + gcov_type v = hist->hvalue.counters[2 * n + 2]; + gcov_type c = hist->hvalue.counters[2 * n + 3]; if (hist->hvalue.counters[0] < 0 && (flag_profile_reproducible == PROFILE_REPRODUCIBILITY_PARALLEL_RUNS @@ -1433,7 +1452,7 @@ dump_ic_profile (gimple_stmt_iterator *gsi) count = 0; all = histogram->hvalue.counters[0]; - for (unsigned j = 0; j < GCOV_TOPN_VALUES; j++) + for (unsigned j = 0; j < GCOV_TOPN_MAXIMUM_TRACKED_VALUES; j++) { if (!get_nth_most_common_value (NULL, "indirect call", histogram, &val, &count, &all, j)) @@ -1902,7 +1921,7 @@ gimple_find_values_to_profile (histogram_values *values) case HIST_TYPE_TOPN_VALUES: case HIST_TYPE_INDIR_CALL: - hist->n_counters = GCOV_TOPN_VALUES_COUNTERS; + hist->n_counters = GCOV_TOPN_MEM_COUNTERS; break; case HIST_TYPE_TIME_PROFILE: diff --git a/libgcc/libgcov-driver.c b/libgcc/libgcov-driver.c index fb320738e1e..8348d9f33ec 100644 --- a/libgcc/libgcov-driver.c +++ b/libgcc/libgcov-driver.c @@ -213,51 +213,6 @@ static struct gcov_fn_buffer *fn_buffer; /* Including system dependent components. */ #include "libgcov-driver-system.c" -/* Prune TOP N value COUNTERS. It's needed in order to preserve - reproducibility of builds. */ - -static void -prune_topn_counter (gcov_type *counters, gcov_type all) -{ - for (unsigned i = 0; i < GCOV_TOPN_VALUES; i++) - if (counters[2 * i + 1] < all) - { - counters[2 * i] = 0; - counters[2 * i + 1] = 0; - } -} - -/* Prune counters so that they are ready to store or merge. */ - -static void -prune_counters (struct gcov_info *gi) -{ - for (unsigned i = 0; i < gi->n_functions; i++) - { - const struct gcov_fn_info *gfi = gi->functions[i]; - const struct gcov_ctr_info *ci = gfi->ctrs; - - for (unsigned j = 0; j < GCOV_COUNTERS; j++) - { - if (gi->merge[j] == NULL) - continue; - - if (gi->merge[j] == __gcov_merge_topn) - { - gcc_assert (!(ci->num % GCOV_TOPN_VALUES_COUNTERS)); - for (unsigned k = 0; k < (ci->num / GCOV_TOPN_VALUES_COUNTERS); - k++) - { - gcov_type *counters - = ci->values + (k * GCOV_TOPN_VALUES_COUNTERS); - prune_topn_counter (counters + 1, *counters); - } - } - ci++; - } - } -} - /* This function merges counters in GI_PTR to an existing gcda file. Return 0 on success. Return -1 on error. In this case, caller will goto read_fatal. */ @@ -346,16 +301,18 @@ merge_one_data (const char *filename, if (!merge) continue; - tag = gcov_read_unsigned (); - length = gcov_read_unsigned (); - if (tag != GCOV_TAG_FOR_COUNTER (t_ix) - || length != GCOV_TAG_COUNTER_LENGTH (ci_ptr->num)) - goto read_mismatch; - (*merge) (ci_ptr->values, ci_ptr->num); - ci_ptr++; - } + tag = gcov_read_unsigned (); + length = gcov_read_unsigned (); + if (tag != GCOV_TAG_FOR_COUNTER (t_ix) + || (length != GCOV_TAG_COUNTER_LENGTH (ci_ptr->num) + && t_ix != GCOV_COUNTER_V_TOPN + && t_ix != GCOV_COUNTER_V_INDIR)) + goto read_mismatch; + (*merge) (ci_ptr->values, ci_ptr->num); + ci_ptr++; + } if ((error = gcov_is_error ())) - goto read_error; + goto read_error; } if (tag) @@ -374,6 +331,37 @@ read_error: return -1; } +/* Store all TOP N counters where each has a dynamic length. */ + +static void +write_top_counters (const struct gcov_ctr_info *ci_ptr, + unsigned t_ix, + gcov_unsigned_t n_counts) +{ + unsigned counters = n_counts / GCOV_TOPN_MEM_COUNTERS; + gcc_assert (n_counts % GCOV_TOPN_MEM_COUNTERS == 0); + unsigned pair_total = 0; + for (unsigned i = 0; i < counters; i++) + pair_total += ci_ptr->values[GCOV_TOPN_MEM_COUNTERS * i + 1]; + unsigned disk_size = GCOV_TOPN_DISK_COUNTERS * counters + 2 * pair_total; + gcov_write_tag_length (GCOV_TAG_FOR_COUNTER (t_ix), + GCOV_TAG_COUNTER_LENGTH (disk_size)); + + for (unsigned i = 0; i < counters; i++) + { + gcov_type pair_count = ci_ptr->values[GCOV_TOPN_MEM_COUNTERS * i + 1]; + gcov_write_counter (ci_ptr->values[GCOV_TOPN_MEM_COUNTERS * i]); + gcov_write_counter (pair_count); + for (struct gcov_kvp *node + = (struct gcov_kvp *)ci_ptr->values[GCOV_TOPN_MEM_COUNTERS * i + 2]; + node != NULL; node = node->next) + { + gcov_write_counter (node->value); + gcov_write_counter (node->count); + } + } +} + /* Write counters in GI_PTR and the summary in PRG to a gcda file. In the case of appending to an existing file, SUMMARY_POS will be non-zero. We will write the file starting from SUMMAY_POS. */ @@ -433,11 +421,18 @@ write_one_data (const struct gcov_info *gi_ptr, continue; n_counts = ci_ptr->num; - gcov_write_tag_length (GCOV_TAG_FOR_COUNTER (t_ix), - GCOV_TAG_COUNTER_LENGTH (n_counts)); - c_ptr = ci_ptr->values; - while (n_counts--) - gcov_write_counter (*c_ptr++); + + if (gi_ptr->merge[t_ix] == __gcov_merge_topn) + write_top_counters (ci_ptr, t_ix, n_counts); + else + { + gcov_write_tag_length (GCOV_TAG_FOR_COUNTER (t_ix), + GCOV_TAG_COUNTER_LENGTH (n_counts)); + c_ptr = ci_ptr->values; + while (n_counts--) + gcov_write_counter (*c_ptr++); + } + ci_ptr++; } if (buffered) @@ -476,9 +471,6 @@ dump_one_gcov (struct gcov_info *gi_ptr, struct gcov_filename *gf, gcov_unsigned_t tag; fn_buffer = 0; - /* Prune current counters before we merge them. */ - prune_counters (gi_ptr); - error = gcov_exit_open_gcda_file (gi_ptr, gf); if (error == -1) return; diff --git a/libgcc/libgcov-merge.c b/libgcc/libgcov-merge.c index c0785b0bf10..1acdaa0403e 100644 --- a/libgcc/libgcov-merge.c +++ b/libgcc/libgcov-merge.c @@ -86,86 +86,6 @@ __gcov_merge_time_profile (gcov_type *counters, unsigned n_counters) #ifdef L_gcov_merge_topn -/* To merging of TOPN profiles. - counters[0] is the number of executions - for i in 0 ... TOPN-1 - counters[2 * i + 1] is target - counters[2 * i + 2] is corresponding hitrate counter. - - Because we prune counters only those with probability >= 1/TOPN are - present now. - - We use sign of counters[0] to track whether the number of different - targets exceeds TOPN. */ - -static void -merge_topn_values_set (gcov_type *counters) -{ - /* First value is number of total executions of the profiler. */ - gcov_type all = gcov_get_counter (); - gcov_type *total = &counters[0]; - ++counters; - - /* Negative value means that counter is missing some of values. */ - if (all < 0) - *total = -(*total); - - *total += all; - - /* Read all part values. */ - gcov_type read_counters[2 * GCOV_TOPN_VALUES]; - for (unsigned i = 0; i < GCOV_TOPN_VALUES; i++) - { - read_counters[2 * i] = gcov_get_counter_target (); - read_counters[2 * i + 1] = gcov_get_counter_ignore_scaling (-1); - } - - for (unsigned i = 0; i < GCOV_TOPN_VALUES; i++) - { - if (read_counters[2 * i + 1] == 0) - continue; - - unsigned j; - int slot = 0; - - for (j = 0; j < GCOV_TOPN_VALUES; j++) - { - if (counters[2 * j] == read_counters[2 * i]) - { - counters[2 * j + 1] += read_counters[2 * i + 1]; - break; - } - else if (counters[2 * j + 1] < counters[2 * slot + 1]) - slot = j; - } - - if (j == GCOV_TOPN_VALUES) - { - gcov_type slot_count = counters[2 * slot + 1]; - /* We found an empty slot. */ - if (slot_count == 0) - { - /* If we found empty slot, add the value. */ - counters[2 * slot] = read_counters[2 * i]; - counters[2 * slot + 1] = read_counters[2 * i + 1]; - } - else - { - /* Here we are loosing some values. */ - if (*total >= 0) - *total = -(*total); - if (read_counters[2 * i + 1] > slot_count) - { - counters[2 * slot] = read_counters[2 * i]; - counters[2 * slot + 1] = read_counters[2 * i + 1]; - } - else - counters[2 * slot + 1] -= read_counters[2 * i + 1]; - } - } - } -} - /* The profile merging function for choosing the most common value. It is given an array COUNTERS of N_COUNTERS old counters and it reads the same number of counters from the gcov file. The counters @@ -175,13 +95,30 @@ merge_topn_values_set (gcov_type *counters) -- the stored candidate on the most common value of the measured entity -- counter */ + void __gcov_merge_topn (gcov_type *counters, unsigned n_counters) { - gcc_assert (!(n_counters % GCOV_TOPN_VALUES_COUNTERS)); + gcc_assert (!(n_counters % GCOV_TOPN_MEM_COUNTERS)); - for (unsigned i = 0; i < (n_counters / GCOV_TOPN_VALUES_COUNTERS); i++) - merge_topn_values_set (counters + (i * GCOV_TOPN_VALUES_COUNTERS)); + for (unsigned i = 0; i < (n_counters / GCOV_TOPN_MEM_COUNTERS); i++) + { + /* First value is number of total executions of the profiler. */ + gcov_type all = gcov_get_counter_ignore_scaling (-1); + gcov_type n = gcov_get_counter_ignore_scaling (-1); + + counters[GCOV_TOPN_MEM_COUNTERS * i] += all; + + for (unsigned j = 0; j < n; j++) + { + gcov_type value = gcov_get_counter_target (); + gcov_type count = gcov_get_counter_ignore_scaling (-1); + + // TODO: we should use atomic here + gcov_topn_add_value (counters + GCOV_TOPN_MEM_COUNTERS * i, value, + count, 0, 0); + } + } } #endif /* L_gcov_merge_topn */ diff --git a/libgcc/libgcov-profiler.c b/libgcc/libgcov-profiler.c index 6043ac4c7a1..7b171382a07 100644 --- a/libgcc/libgcov-profiler.c +++ b/libgcc/libgcov-profiler.c @@ -105,51 +105,13 @@ __gcov_pow2_profiler_atomic (gcov_type *counters, gcov_type value) } #endif - /* Tries to determine N most commons value among its inputs. */ static inline void __gcov_topn_values_profiler_body (gcov_type *counters, gcov_type value, int use_atomic) { - if (use_atomic) - __atomic_fetch_add (&counters[0], 1, __ATOMIC_RELAXED); - else - counters[0]++; - - ++counters; - - /* First try to find an existing value. */ - int empty_counter = -1; - - for (unsigned i = 0; i < GCOV_TOPN_VALUES; i++) - if (value == counters[2 * i]) - { - if (use_atomic) - __atomic_fetch_add (&counters[2 * i + 1], GCOV_TOPN_VALUES, - __ATOMIC_RELAXED); - else - counters[2 * i + 1] += GCOV_TOPN_VALUES; - return; - } - else if (counters[2 * i + 1] <= 0) - empty_counter = i; - - /* Find an empty slot for a new value. */ - if (empty_counter != -1) - { - counters[2 * empty_counter] = value; - counters[2 * empty_counter + 1] = GCOV_TOPN_VALUES; - return; - } - - /* We haven't found an empty slot, then decrement all - counter values by one. */ - for (unsigned i = 0; i < GCOV_TOPN_VALUES; i++) - if (use_atomic) - __atomic_fetch_sub (&counters[2 * i + 1], 1, __ATOMIC_RELAXED); - else - counters[2 * i + 1]--; + gcov_topn_add_value (counters, value, 1, use_atomic, 1); } #ifdef L_gcov_topn_values_profiler diff --git a/libgcc/libgcov.h b/libgcc/libgcov.h index 023293e05ec..a2a29257bd1 100644 --- a/libgcc/libgcov.h +++ b/libgcc/libgcov.h @@ -367,6 +367,93 @@ gcov_get_counter_target (void) #endif } +/* Add VALUE to *COUNTER and make it with atomic operation + if USE_ATOMIC is true. */ + +static inline void +gcov_counter_add (gcov_type *counter, gcov_type value, int use_atomic) +{ + if (use_atomic) + __atomic_fetch_add (counter, value, __ATOMIC_RELAXED); + else + *counter += value; +} + +/* Set NODE to memory location COUNTER and make it with atomic operation + if USE_ATOMIC is true. */ + +static inline int +gcov_counter_set_if_null (gcov_type *counter, struct gcov_kvp *node, + int use_atomic) +{ + if (use_atomic) + return !__sync_val_compare_and_swap (counter, NULL, (intptr_t)node); + else + { + *counter = (intptr_t)node; + return 1; + } +} + +/* Add key value pair VALUE:COUNT to a top N COUNTERS. When INCREMENT_TOTAL + is true, add COUNT to total of the TOP counter. If USE_ATOMIC is true, + do it in atomic way. */ + +static inline void +gcov_topn_add_value (gcov_type *counters, gcov_type value, gcov_type count, + int use_atomic, int increment_total) +{ + if (increment_total) + gcov_counter_add (&counters[0], 1, use_atomic); + + struct gcov_kvp *prev_node = NULL; + struct gcov_kvp *minimal_node = NULL; + struct gcov_kvp *current_node = (struct gcov_kvp *)counters[2]; + + while (current_node) + { + if (current_node->value == value) + { + gcov_counter_add (¤t_node->count, count, use_atomic); + return; + } + + if (minimal_node == NULL + || current_node->count < minimal_node->count) + minimal_node = current_node; + + prev_node = current_node; + current_node = current_node->next; + } + + if (counters[1] == GCOV_TOPN_MAXIMUM_TRACKED_VALUES) + { + if (--minimal_node->count < count) + { + minimal_node->value = value; + minimal_node->count = count; + } + } + else + { + struct gcov_kvp *new_node + = (struct gcov_kvp *)xcalloc (1, sizeof (struct gcov_kvp)); + new_node->value = value; + new_node->count = count; + + int success = 0; + if (!counters[2]) + success = gcov_counter_set_if_null (&counters[2], new_node, use_atomic); + else if (prev_node && !prev_node->next) + success = gcov_counter_set_if_null ((gcov_type *)&prev_node->next, + new_node, use_atomic); + + /* Increment number of nodes. */ + if (success) + gcov_counter_add (&counters[1], 1, use_atomic); + } +} + #endif /* !inhibit_libc */ #endif /* GCC_LIBGCOV_H */