public inbox for gcc-cvs@sourceware.org
help / color / mirror / Atom feed
* [gcc(refs/users/marxin/heads/gcov-topn-dynamic)] Make TOPN counter dynamically allocated.
@ 2020-01-31 12:10 Martin Liska
0 siblings, 0 replies; 2+ messages in thread
From: Martin Liska @ 2020-01-31 12:10 UTC (permalink / raw)
To: gcc-cvs
https://gcc.gnu.org/g:a6a34d7bc6b199c93860a1daa6edbfc55b813b5e
commit a6a34d7bc6b199c93860a1daa6edbfc55b813b5e
Author: Martin Liska <mliska@suse.cz>
Date: Fri Jan 31 13:10:14 2020 +0100
Make TOPN counter dynamically allocated.
Diff:
---
gcc/gcov-dump.c | 2 +-
gcc/gcov-io.h | 11 ++++-
libgcc/libgcov-driver.c | 109 +++++++++++++++++++++-------------------------
libgcc/libgcov-merge.c | 99 +++++++++++++++++------------------------
libgcc/libgcov-profiler.c | 60 +++++++++++--------------
5 files changed, 124 insertions(+), 157 deletions(-)
diff --git a/gcc/gcov-dump.c b/gcc/gcov-dump.c
index bd2ae22..0a64e8b 100644
--- a/gcc/gcov-dump.c
+++ b/gcc/gcov-dump.c
@@ -441,7 +441,7 @@ tag_counters (const char *filename ATTRIBUTE_UNUSED,
{
gcov_type count;
- if (!(ix & 7))
+ if (ix == 0)
{
printf ("\n");
print_prefix (filename, depth, gcov_position ());
diff --git a/gcc/gcov-io.h b/gcc/gcov-io.h
index d21a43c..e491e8f 100644
--- a/gcc/gcov-io.h
+++ b/gcc/gcov-io.h
@@ -164,6 +164,15 @@ see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
#ifndef GCC_GCOV_IO_H
#define GCC_GCOV_IO_H
+struct gcov_kvp;
+
+struct gcov_kvp
+{
+ gcov_type value;
+ gcov_type count;
+ struct gcov_kvp *next;
+};
+
#ifndef IN_LIBGCOV
/* About the host */
@@ -270,7 +279,7 @@ GCOV_COUNTERS
#define GCOV_TOPN_VALUES 4
/* Total number of single value counters. */
-#define GCOV_TOPN_VALUES_COUNTERS (2 * GCOV_TOPN_VALUES + 1)
+#define GCOV_TOPN_VALUES_COUNTERS 3
/* Convert a counter index to a tag. */
#define GCOV_TAG_FOR_COUNTER(COUNT) \
diff --git a/libgcc/libgcov-driver.c b/libgcc/libgcov-driver.c
index fb32073..47ed658 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,13 +301,26 @@ 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++;
+ if (merge == __gcov_merge_topn)
+ for (unsigned i = 0; i < ci_ptr->num / GCOV_TOPN_VALUES_COUNTERS;
+ i++)
+ {
+ tag = gcov_read_unsigned ();
+ length = gcov_read_unsigned ();
+ if (tag != GCOV_TAG_FOR_COUNTER (t_ix))
+ goto read_mismatch;
+ (*merge) (ci_ptr->values + i * GCOV_TOPN_VALUES_COUNTERS, GCOV_TOPN_VALUES_COUNTERS);
+ }
+ else
+ {
+ 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++;
}
if ((error = gcov_is_error ()))
goto read_error;
@@ -433,11 +401,35 @@ 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)
+ {
+ // TODO
+ gcc_assert (n_counts % 3 == 0);
+ for (unsigned i = 0; i < (n_counts / 3); i++)
+ {
+ gcov_type pair_count = ci_ptr->values[3 * i + 1];
+ gcov_write_tag_length (GCOV_TAG_FOR_COUNTER (t_ix),
+ GCOV_TAG_COUNTER_LENGTH (2 + 2 * pair_count));
+ gcov_write_counter (ci_ptr->values[3 * i]);
+ gcov_write_counter (pair_count);
+ for (struct gcov_kvp *node = (struct gcov_kvp *)ci_ptr->values[3 * i + 2];
+ node != NULL; node = node->next)
+ {
+ gcov_write_counter (node->value);
+ gcov_write_counter (node->count);
+ }
+ }
+ }
+ 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 +468,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 19b8ee7..39f0fea 100644
--- a/libgcc/libgcov-merge.c
+++ b/libgcc/libgcov-merge.c
@@ -86,82 +86,61 @@ __gcov_merge_time_profile (gcov_type *counters, unsigned n_counters)
#ifdef L_gcov_merge_topn
-static void
-merge_topn_values_set (gcov_type *counters)
+/* 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
+ are split into pairs where the members of the tuple have
+ meanings:
+
+ -- 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);
+
/* First value is number of total executions of the profiler. */
gcov_type all = gcov_get_counter_ignore_scaling (-1);
- counters[0] += all;
- ++counters;
+ gcov_type n = gcov_get_counter_ignore_scaling (-1);
- /* 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);
- }
-
- if (read_counters[1] == -1)
- {
- counters[1] = -1;
- return;
- }
+ counters[0] += all;
- for (unsigned i = 0; i < GCOV_TOPN_VALUES; i++)
+ struct gcov_kvp *root = (struct gcov_kvp *)counters[2];
+ for (unsigned i = 0; i < n; i++)
{
- if (read_counters[2 * i + 1] == 0)
- continue;
+ gcov_type value = gcov_get_counter_target ();
+ gcov_type count = gcov_get_counter_ignore_scaling (-1);
- unsigned j;
- int slot = -1;
-
- for (j = 0; j < GCOV_TOPN_VALUES; j++)
+ int done = 0;
+ struct gcov_kvp *prev = NULL;
+ for (struct gcov_kvp *node = root; node != NULL; node = node->next)
{
- if (counters[2 * j] == read_counters[2 * i])
+ if (node->value == value)
{
- counters[2 * j + 1] += read_counters[2 * i + 1];
+ node->count += count;
+ done = 1;
break;
}
- else if (counters[2 * j + 1] == 0)
- slot = j;
+ prev = node;
}
- if (j == GCOV_TOPN_VALUES)
- {
- if (slot > 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
- {
- /* We haven't found a slot, bail out. */
- counters[1] = -1;
- return;
- }
- }
- }
-}
+ if (done)
+ continue;
-/* 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
- are split into pairs where the members of the tuple have
- meanings:
+ counters[1]++;
- -- 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));
+ struct gcov_kvp *new_node
+ = (struct gcov_kvp *)xcalloc (1, sizeof (struct gcov_kvp));
+ new_node->value = value;
+ new_node->count = count;
- for (unsigned i = 0; i < (n_counters / GCOV_TOPN_VALUES_COUNTERS); i++)
- merge_topn_values_set (counters + (i * GCOV_TOPN_VALUES_COUNTERS));
+ if (!counters[2])
+ counters[2] = (intptr_t)new_node;
+ else if (prev && !prev->next)
+ prev->next = new_node;
+ }
}
#endif /* L_gcov_merge_topn */
diff --git a/libgcc/libgcov-profiler.c b/libgcc/libgcov-profiler.c
index 6043ac4..c70f88b 100644
--- a/libgcc/libgcov-profiler.c
+++ b/libgcc/libgcov-profiler.c
@@ -105,51 +105,41 @@ __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[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)
+ struct gcov_kvp *prev_node = NULL;
+ struct gcov_kvp *current_node = (struct gcov_kvp *)counters[2];
+
+ while (current_node)
{
- counters[2 * empty_counter] = value;
- counters[2 * empty_counter + 1] = GCOV_TOPN_VALUES;
- return;
+ if (current_node->value == value)
+ {
+ current_node->count += 1;
+ return;
+ }
+
+ prev_node = current_node;
+ current_node = current_node->next;
}
- /* 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]--;
+ /* Increment number of nodes. */
+ counters[1]++;
+
+ struct gcov_kvp *new_node
+ = (struct gcov_kvp *)xcalloc (1, sizeof (struct gcov_kvp));
+ new_node->value = value;
+ new_node->count = 1;
+
+ if (!counters[2])
+ counters[2] = (intptr_t)new_node;
+ else if (prev_node && !prev_node->next)
+ prev_node->next = new_node;
}
#ifdef L_gcov_topn_values_profiler
^ permalink raw reply [flat|nested] 2+ messages in thread
* [gcc(refs/users/marxin/heads/gcov-topn-dynamic)] Make TOPN counter dynamically allocated.
@ 2020-01-31 12:47 Martin Liska
0 siblings, 0 replies; 2+ messages in thread
From: Martin Liska @ 2020-01-31 12:47 UTC (permalink / raw)
To: gcc-cvs
https://gcc.gnu.org/g:afd618d1fb30b68d2acf38363e4a3e2f7ed681ff
commit afd618d1fb30b68d2acf38363e4a3e2f7ed681ff
Author: Martin Liska <mliska@suse.cz>
Date: Fri Jan 31 13:10:14 2020 +0100
Make TOPN counter dynamically allocated.
Diff:
---
gcc/gcov-dump.c | 2 +-
gcc/gcov-io.h | 11 ++++-
libgcc/libgcov-driver.c | 109 +++++++++++++++++++++-------------------------
libgcc/libgcov-merge.c | 102 ++++++++++++++++++-------------------------
libgcc/libgcov-profiler.c | 60 +++++++++++--------------
5 files changed, 127 insertions(+), 157 deletions(-)
diff --git a/gcc/gcov-dump.c b/gcc/gcov-dump.c
index bd2ae22..0a64e8b 100644
--- a/gcc/gcov-dump.c
+++ b/gcc/gcov-dump.c
@@ -441,7 +441,7 @@ tag_counters (const char *filename ATTRIBUTE_UNUSED,
{
gcov_type count;
- if (!(ix & 7))
+ if (ix == 0)
{
printf ("\n");
print_prefix (filename, depth, gcov_position ());
diff --git a/gcc/gcov-io.h b/gcc/gcov-io.h
index d21a43c..e491e8f 100644
--- a/gcc/gcov-io.h
+++ b/gcc/gcov-io.h
@@ -164,6 +164,15 @@ see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
#ifndef GCC_GCOV_IO_H
#define GCC_GCOV_IO_H
+struct gcov_kvp;
+
+struct gcov_kvp
+{
+ gcov_type value;
+ gcov_type count;
+ struct gcov_kvp *next;
+};
+
#ifndef IN_LIBGCOV
/* About the host */
@@ -270,7 +279,7 @@ GCOV_COUNTERS
#define GCOV_TOPN_VALUES 4
/* Total number of single value counters. */
-#define GCOV_TOPN_VALUES_COUNTERS (2 * GCOV_TOPN_VALUES + 1)
+#define GCOV_TOPN_VALUES_COUNTERS 3
/* Convert a counter index to a tag. */
#define GCOV_TAG_FOR_COUNTER(COUNT) \
diff --git a/libgcc/libgcov-driver.c b/libgcc/libgcov-driver.c
index fb32073..47ed658 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,13 +301,26 @@ 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++;
+ if (merge == __gcov_merge_topn)
+ for (unsigned i = 0; i < ci_ptr->num / GCOV_TOPN_VALUES_COUNTERS;
+ i++)
+ {
+ tag = gcov_read_unsigned ();
+ length = gcov_read_unsigned ();
+ if (tag != GCOV_TAG_FOR_COUNTER (t_ix))
+ goto read_mismatch;
+ (*merge) (ci_ptr->values + i * GCOV_TOPN_VALUES_COUNTERS, GCOV_TOPN_VALUES_COUNTERS);
+ }
+ else
+ {
+ 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++;
}
if ((error = gcov_is_error ()))
goto read_error;
@@ -433,11 +401,35 @@ 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)
+ {
+ // TODO
+ gcc_assert (n_counts % 3 == 0);
+ for (unsigned i = 0; i < (n_counts / 3); i++)
+ {
+ gcov_type pair_count = ci_ptr->values[3 * i + 1];
+ gcov_write_tag_length (GCOV_TAG_FOR_COUNTER (t_ix),
+ GCOV_TAG_COUNTER_LENGTH (2 + 2 * pair_count));
+ gcov_write_counter (ci_ptr->values[3 * i]);
+ gcov_write_counter (pair_count);
+ for (struct gcov_kvp *node = (struct gcov_kvp *)ci_ptr->values[3 * i + 2];
+ node != NULL; node = node->next)
+ {
+ gcov_write_counter (node->value);
+ gcov_write_counter (node->count);
+ }
+ }
+ }
+ 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 +468,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 19b8ee7..f51d0bb 100644
--- a/libgcc/libgcov-merge.c
+++ b/libgcc/libgcov-merge.c
@@ -86,82 +86,64 @@ __gcov_merge_time_profile (gcov_type *counters, unsigned n_counters)
#ifdef L_gcov_merge_topn
-static void
-merge_topn_values_set (gcov_type *counters)
+/* 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
+ are split into pairs where the members of the tuple have
+ meanings:
+
+ -- 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);
+
/* 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];
-
- 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);
- }
+ gcov_type n = gcov_get_counter_ignore_scaling (-1);
- if (read_counters[1] == -1)
- {
- counters[1] = -1;
- return;
- }
+ counters[0] += all;
- for (unsigned i = 0; i < GCOV_TOPN_VALUES; i++)
+ struct gcov_kvp *root = (struct gcov_kvp *)counters[2];
+ for (unsigned i = 0; i < n; i++)
{
- if (read_counters[2 * i + 1] == 0)
- continue;
-
- unsigned j;
- int slot = -1;
+ gcov_type value = gcov_get_counter_target ();
+ gcov_type count = gcov_get_counter_ignore_scaling (-1);
- for (j = 0; j < GCOV_TOPN_VALUES; j++)
+ int done = 0;
+ struct gcov_kvp *prev = NULL;
+ for (struct gcov_kvp *node = root; node != NULL; node = node->next)
{
- if (counters[2 * j] == read_counters[2 * i])
+ if (node->value == value)
{
- counters[2 * j + 1] += read_counters[2 * i + 1];
+ node->count += count;
+ done = 1;
break;
}
- else if (counters[2 * j + 1] == 0)
- slot = j;
+ prev = node;
}
- if (j == GCOV_TOPN_VALUES)
- {
- if (slot > 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
- {
- /* We haven't found a slot, bail out. */
- counters[1] = -1;
- return;
- }
- }
- }
-}
+ if (done)
+ continue;
-/* 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
- are split into pairs where the members of the tuple have
- meanings:
+ counters[1]++;
- -- 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));
+ struct gcov_kvp *new_node
+ = (struct gcov_kvp *)xcalloc (1, sizeof (struct gcov_kvp));
+ new_node->value = value;
+ new_node->count = count;
- for (unsigned i = 0; i < (n_counters / GCOV_TOPN_VALUES_COUNTERS); i++)
- merge_topn_values_set (counters + (i * GCOV_TOPN_VALUES_COUNTERS));
+ if (!counters[2])
+ {
+ counters[2] = (intptr_t)new_node;
+ root = new_node;
+ }
+ else if (prev && !prev->next)
+ prev->next = new_node;
+ }
}
#endif /* L_gcov_merge_topn */
diff --git a/libgcc/libgcov-profiler.c b/libgcc/libgcov-profiler.c
index 6043ac4..c70f88b 100644
--- a/libgcc/libgcov-profiler.c
+++ b/libgcc/libgcov-profiler.c
@@ -105,51 +105,41 @@ __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[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)
+ struct gcov_kvp *prev_node = NULL;
+ struct gcov_kvp *current_node = (struct gcov_kvp *)counters[2];
+
+ while (current_node)
{
- counters[2 * empty_counter] = value;
- counters[2 * empty_counter + 1] = GCOV_TOPN_VALUES;
- return;
+ if (current_node->value == value)
+ {
+ current_node->count += 1;
+ return;
+ }
+
+ prev_node = current_node;
+ current_node = current_node->next;
}
- /* 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]--;
+ /* Increment number of nodes. */
+ counters[1]++;
+
+ struct gcov_kvp *new_node
+ = (struct gcov_kvp *)xcalloc (1, sizeof (struct gcov_kvp));
+ new_node->value = value;
+ new_node->count = 1;
+
+ if (!counters[2])
+ counters[2] = (intptr_t)new_node;
+ else if (prev_node && !prev_node->next)
+ prev_node->next = new_node;
}
#ifdef L_gcov_topn_values_profiler
^ permalink raw reply [flat|nested] 2+ messages in thread
end of thread, other threads:[~2020-01-31 12:47 UTC | newest]
Thread overview: 2+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2020-01-31 12:10 [gcc(refs/users/marxin/heads/gcov-topn-dynamic)] Make TOPN counter dynamically allocated Martin Liska
2020-01-31 12:47 Martin Liska
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).