Hi,
this patch implements more careful merging of topn values (tracking regression
we got by the reproducible profiling work). Instead of giving up on the
counter on the overflow we use sign bits to track
1) if there are some vlaues lost
2) if given target was not having probability at least 1/TOPN in some run.
This makes it possible to trust more profiled values and also consumer can
decide whether he wants reproducibility at all.
Bootstrapped/regtested x86_64-linux. The patch makes small improvement to
profile precision but it will make it easy to implement command line option
turning off the profile reproducibility. It turns out that it reduces
the precision of profile info quite a lot in practice. In particular with
nonreproducible profiling we speculatively inline 26% more indirect calls
that without in cc1plus.
Martin, I welcome your opinion on the patch :)
lto-profile-bootstrapped/regtested x86_64-linux. I am going to test
this on Firefox and clang and gather updated logs.
2020-01-30 Jan Hubicka <hubi...@ucw.cz>
PR ipa/92924
* value-prof.c (dump_histogram_value): Update dumping.
(stream_out_histogram_value): Do not check that values are positive for
TOPN
(get_nth_most_common_value): Update comment and handling of sign bits.
libgcc/ChangeLog:
2020-01-30 Jan Hubicka <hubi...@ucw.cz>
PR ipa/92924
* libgcov-merge.c (merge_topn_values_set): Do not invalidate whole
counter when it is too full, but track info in signs of counts.
diff --git a/gcc/value-prof.c b/gcc/value-prof.c
index f0456c8e93d..e906bd49848 100644
--- a/gcc/value-prof.c
+++ b/gcc/value-prof.c
@@ -265,13 +265,17 @@ 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 ", values: ",
- (int64_t) hist->hvalue.counters[0]);
+ fprintf (dump_file, " all: %" PRId64 "%s, values: ",
+ abs ((int64_t) hist->hvalue.counters[0]),
+ hist->hvalue.counters[0] < 0
+ ? " (values missing)": "");
for (unsigned i = 0; i < GCOV_TOPN_VALUES; i++)
{
- fprintf (dump_file, "[%" PRId64 ":%" PRId64 "]",
+ fprintf (dump_file, "[%" PRId64 ":%" PRId64 "%s]",
(int64_t) hist->hvalue.counters[2 * i + 1],
- (int64_t) hist->hvalue.counters[2 * i + 2]);
+ (int64_t) abs (hist->hvalue.counters[2 * i + 2]),
+ hist->hvalue.counters[2 * i + 2] < 0
+ ? " (unreproducible)" : "");
if (i != GCOV_TOPN_VALUES - 1)
fprintf (dump_file, ", ");
}
@@ -330,7 +334,7 @@ stream_out_histogram_value (struct output_block *ob,
histogram_value hist)
/* When user uses an unsigned type with a big value, constant converted
to gcov_type (a signed type) can be negative. */
gcov_type value = hist->hvalue.counters[i];
- if (hist->type == HIST_TYPE_TOPN_VALUES && i > 0)
+ if (hist->type == HIST_TYPE_TOPN_VALUES)
;
else
gcc_assert (value >= 0);
@@ -719,26 +723,47 @@ gimple_divmod_fixed_value (gassign *stmt, tree value,
profile_probability prob,
/* Return the n-th value count of TOPN_VALUE histogram. If
there's a value, return true and set VALUE and COUNT
- arguments. */
+ arguments.
+
+ Counters have the following meanings.
+
+ abs (counters[0]) is the number of executions
+ for i in 0 ... TOPN-1
+ counters[2 * i + 1] is target
+ abs (counters[2 * i + 2]) is corresponding hitrate counter.
+
+ Value of counters[0] negative when counter became
+ full during merging and some values are lost.
+
+ Value of counters[2 * i + 2] is negative if there was run when the
+ corresponding targt was not having probability 1/4.
+
+ If both counters[0] and counters[2 * i + 2] are negatie we do not know the
+ precise hitrate count of the target in case order of merges is not fixed
+ (as with parallel profiledbootstrap).
+ */
bool
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)
{
- if (hist->hvalue.counters[2] == -1)
- return false;
-
gcc_assert (n < GCOV_TOPN_VALUES);
*count = 0;
*value = 0;
- gcov_type read_all = hist->hvalue.counters[0];
+ gcov_type read_all = abs (hist->hvalue.counters[0]);
gcov_type v = hist->hvalue.counters[2 * n + 1];
gcov_type c = hist->hvalue.counters[2 * n + 2];
+ /* Negative value marks that target is not necessarily reproducible
+ for parallel merging. */
+ if (c < 0 && hist->hvalue.counters[0] < 0)
+ return false;
+ c = abs (c);
+
/* Indirect calls can't be verified. */
if (stmt
&& check_counter (stmt, counter_type, &c, &read_all,
diff --git a/libgcc/libgcov-merge.c b/libgcc/libgcov-merge.c
index 19b8ee72ae9..2cf6ebf04ea 100644
--- a/libgcc/libgcov-merge.c
+++ b/libgcc/libgcov-merge.c
@@ -86,64 +86,110 @@ __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 and sign of counters[2 * i + 2] to track whether given
+ value was having probability at least 1/TOPN in each run. */
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_ignore_scaling (-1);
- counters[0] += all;
- ++counters;
-
- /* Read all part values. */
- gcov_type read_counters[2 * GCOV_TOPN_VALUES];
+ gcov_type all = gcov_get_counter ();
- for (unsigned i = 0; i < GCOV_TOPN_VALUES; i++)
+ /* Early returns (needed for logic tracking sign bits below).
+ If there is nothing to merge in, return early. */
+ if (all == 0)
{
- 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++)
+ {
+ gcov_get_counter_target ();
+ gcov_get_counter ();
+ }
+ return;
}
- if (read_counters[1] == -1)
+ /* Counter is not trained at all; copy data. */
+ if (!counters[0])
{
- counters[1] = -1;
+ counters[0] = all;
+ ++counters;
+ for (unsigned i = 0; i < GCOV_TOPN_VALUES; i++)
+ {
+ counters[2 * i] = gcov_get_counter_target ();
+ counters[2 * i + 1] = gcov_get_counter ();
+ }
return;
}
+ /* Negative value mans that counters is missing some of values. */
+ if (all < 0)
+ counters[0] = -counters[0];
+ counters[0] += all;
+ ++counters;
+
+ char updated[GCOV_TOPN_VALUES];
+ for (unsigned i = 0; i < GCOV_TOPN_VALUES; i++)
+ updated[i] = 0;
+
for (unsigned i = 0; i < GCOV_TOPN_VALUES; i++)
{
- if (read_counters[2 * i + 1] == 0)
+ gcov_type read_value = gcov_get_counter_target ();
+ gcov_type read_cnt = gcov_get_counter ();
+
+ if (read_cnt == 0)
continue;
unsigned j;
- int slot = -1;
+ int slot = 0;
for (j = 0; j < GCOV_TOPN_VALUES; j++)
{
- if (counters[2 * j] == read_counters[2 * i])
+ if (counters[2 * j] == read_value)
{
- counters[2 * j + 1] += read_counters[2 * i + 1];
+ /* Negative value means that counter was not present in every
+ run. */
+ if (read_cnt < 0)
+ counters[2 * j + 1] = -counters[2 * j + 1];
+ counters[2 * j + 1] += read_cnt;
+ updated[j] = 1;
break;
}
- else if (counters[2 * j + 1] == 0)
+ /* Look for least probable counter. At this moment already some
+ of counters may be negative. */
+ if (abs (counters[2 * j + 1]) < abs (counters[2 * slot + 1]))
slot = j;
}
if (j == GCOV_TOPN_VALUES)
{
- if (slot > 0)
+ /* Counter is full. Throw away least frequent values but
+ mark that some values gone missing. */
+ if (counters[2 * slot + 1] && counters[-1] > 0)
+ counters[-1] = -counters[-1];
+ if (abs (counters[2 * slot + 1]) < abs (read_cnt))
{
- /* 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
- {
- /* We haven't found a slot, bail out. */
- counters[1] = -1;
- return;
+ counters[2 * slot] = read_value;
+ counters[2 * slot + 1] = read_cnt;
+ /* Mark that the value was not present in every run. */
+ if (counters[2 * slot + 1] > 0)
+ counters[2 * slot + 1] = -counters[2 * slot + 1];
}
}
}
+ /* Finally all values which was not present in read counters must be
+ marked as not present in all runs. */
+ for (unsigned i = 0; i < GCOV_TOPN_VALUES; i++)
+ if (!updated[i] && counters[2 * i + 1] > 0)
+ counters[2 * i + 1] = -counters[2 * i + 1];
}
/* The profile merging function for choosing the most common value.
