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 <mli...@suse.cz>
* 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 <mli...@suse.cz>
* 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 <value1,
counter1> 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 */
