diff mbox series

[stage1] Make TOPN counter dynamically allocated.

Message ID c35155b9-574d-c9ff-8d4e-714b2ff7bc03@suse.cz
State New
Headers show
Series [stage1] Make TOPN counter dynamically allocated. | expand

Commit Message

Martin Liška April 6, 2020, 8:03 a.m. UTC 
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  <mliska@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  <mliska@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(-)

Comments

Martin Liška May 15, 2020, 9:57 a.m. UTC | #1 
We're in stage1: PING^1

On 4/6/20 10:03 AM, Martin Liška wrote:
> 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  <mliska@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  <mliska@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(-)
> 
>
Jan Hubicka May 15, 2020, 11:03 a.m. UTC | #2 
> We're in stage1: PING^1

I wonder, did we somehow solved the issue with Firefox breaking due to
malloc instrumentation?

Honza
> 
> On 4/6/20 10:03 AM, Martin Liška wrote:
> > 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  <mliska@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  <mliska@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(-)
> > 
> > 
>
Martin Liška May 15, 2020, 11:13 a.m. UTC | #3 
On 5/15/20 1:03 PM, Jan Hubicka wrote:
> I wonder, did we somehow solved the issue with Firefox breaking due to
> malloc instrumentation?

Yes, you proposed a patch:
https://hg.mozilla.org/try/rev/e1358ef2d82c035b12f8995712580c77bd9f8d43

Which I believe was sent to Firefox?

Martin
Martin Liška May 27, 2020, 10:26 a.m. UTC | #4 
PING^2

On 5/15/20 11:57 AM, Martin Liška wrote:
> We're in stage1: PING^
Jan Hubicka June 2, 2020, 8:27 a.m. UTC | #5 
> 
> 2020-04-03  Martin Liska  <mliska@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  <mliska@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(-)
> 
> 

The patch looks good (and is OK for mainline).  I am bit concerned about
two things.
 1) I think we should add support to pre-allocate memory pool so we hide
 the problem with instrumenting malloc (I think with big enough memory
 pool the Firefox malloc issue should disappear since we populate the
 counters used to profile malloc before we run out of it).
 I think this can be done by adding comdat symbol so one can specify
 size of the pool at compile time.
 2) This seems like bit too big hammer for profiling values for division
 etc.  We will see how perfromance will go - in worst case I guess we
 could put back the original counter TOPN counter and use it for those
 cases.

Thanks for working on this!
Honza
Martin Liška June 2, 2020, 1:19 p.m. UTC | #6 
On 6/2/20 10:27 AM, Jan Hubicka wrote:
> The patch looks good (and is OK for mainline).  I am bit concerned about
> two things.

Hello.

Thank you for the review!

>   1) I think we should add support to pre-allocate memory pool so we hide
>   the problem with instrumenting malloc (I think with big enough memory
>   pool the Firefox malloc issue should disappear since we populate the
>   counters used to profile malloc before we run out of it).
>   I think this can be done by adding comdat symbol so one can specify
>   size of the pool at compile time.

I'm suggesting to pre-allocate 16 gcov_kvp in the gcov run-time library.
Please take a look at the attached patch. I also added a test-case that
stresses that. I've just finished LTO PGO bootstrap of the GCC.

Ready for master?

>   2) This seems like bit too big hammer for profiling values for division
>   etc.  We will see how perfromance will go - in worst case I guess we
>   could put back the original counter TOPN counter and use it for those
>   cases.

We'll see about this and we can possibly reduce number of tracked values
for this kind of profiling.

Thanks,
Martin
Gerald Pfeifer June 3, 2020, 1:07 a.m. UTC | #7 
On Tue, 2 Jun 2020, Martin Liška wrote:
> Ready for master?

Before that, my nightly tester on i386-unknown-freebsd11 just ran into 
the following:

  /scratch/tmp/gerald/GCC-HEAD/gcc/../libgcc/libgcov.h:396:51: error: 
  cannot initialize a parameter of type 'gcov_type' (aka 'long long') 
  with an rvalue of type 'nullptr_t'
    return !__sync_val_compare_and_swap (counter, NULL, (intptr_t)node);
                                                  ^~~~
  /usr/include/sys/_null.h:35:14: note: expanded from macro 'NULL'
  #define NULL    nullptr
                  ^~~~~~~

That seems to have come in via 871e5ada6d53d5eb495cc9f323983f347487c1b2

  Author: Martin Liska <mliska@suse.cz>
  Date:   Fri Jan 31 13:10:14 2020 +0100

    Make TOPN counter dynamically allocated.
  
  :
            * libgcov.h (gcov_counter_add): New.
            (gcov_counter_set_if_null): Likewise.
            (gcov_topn_add_value): New.
  
which added the gcov_counter_set_if_null function.

(The data is quite misleading and appears to be when you first 
committed this locally?  Does git have a good way to show when 
something was pushed?)

Gerald
Martin Liška June 3, 2020, 6:08 a.m. UTC | #8 
On 6/3/20 3:07 AM, Gerald Pfeifer wrote:
> On Tue, 2 Jun 2020, Martin Liška wrote:
>> Ready for master?
> 
> Before that, my nightly tester on i386-unknown-freebsd11 just ran into
> the following:
> 
>    /scratch/tmp/gerald/GCC-HEAD/gcc/../libgcc/libgcov.h:396:51: error:
>    cannot initialize a parameter of type 'gcov_type' (aka 'long long')
>    with an rvalue of type 'nullptr_t'
>      return !__sync_val_compare_and_swap (counter, NULL, (intptr_t)node);
>                                                    ^~~~
>    /usr/include/sys/_null.h:35:14: note: expanded from macro 'NULL'
>    #define NULL    nullptr
>                    ^~~~~~~

Hello.

Sorry for the breakage. Can you please paste full build output for the problematic
.o file?

I bet it's a C file compilation, where we should use:

__sync_val_compare_and_swap (counter, 0, (intptr_t)node);

Can you please test it?

> 
> That seems to have come in via 871e5ada6d53d5eb495cc9f323983f347487c1b2
> 
>    Author: Martin Liska <mliska@suse.cz>
>    Date:   Fri Jan 31 13:10:14 2020 +0100
> 
>      Make TOPN counter dynamically allocated.
>    
>    :
>              * libgcov.h (gcov_counter_add): New.
>              (gcov_counter_set_if_null): Likewise.
>              (gcov_topn_add_value): New.
>    
> which added the gcov_counter_set_if_null function.
> 
> (The data is quite misleading and appears to be when you first
> committed this locally?  Does git have a good way to show when
> something was pushed?)

I would recommend:

$ git show --format=fuller 871e5ada6d53d5eb495cc9f323983f347487c1b2
...
commit 871e5ada6d53d5eb495cc9f323983f347487c1b2
Author:     Martin Liska <mliska@suse.cz>
AuthorDate: Fri Jan 31 13:10:14 2020 +0100
Commit:     Martin Liska <mliska@suse.cz>
CommitDate: Tue Jun 2 12:11:02 2020 +0200

Martin

> 
> Gerald
>
Martin Liška June 3, 2020, 6:28 a.m. UTC | #9 
On 6/2/20 3:19 PM, Martin Liška wrote:
> I'm suggesting to pre-allocate 16 gcov_kvp in the gcov run-time library.
> Please take a look at the attached patch. I also added a test-case that
> stresses that. I've just finished LTO PGO bootstrap of the GCC.
> 
> Ready for master?

There's V2 of the patch:

- guard __atomic_fetch_add in GCOV_SUPPORTS_ATOMIC

Martin
Gerald Pfeifer June 3, 2020, 11:44 p.m. UTC | #10 
On Wed, 3 Jun 2020, Martin Liška wrote:
> Sorry for the breakage. Can you please paste full build output for the 
> problematic .o file?
> 
> I bet it's a C file compilation, where we should use:
> 
> __sync_val_compare_and_swap (counter, 0, (intptr_t)node);
> 
> Can you please test it?

c++ -std=c++11 -fno-PIE -c -g -DIN_GCC -fno-strict-aliasing 
-fno-exceptions -fno-rtti -fasynchronous-unwind-tables -W -Wall 
-Wno-narrowing -Wwrite-strings -Wcast-qual -Wno-error=format-diag 
-Wno-format -Wmissing-format-attribute -Wove rloaded-virtual -pedantic 
-Wno-long-long -Wno-variadic-macros -Wno-overlength-st rings -fno-common 
-Wno-error -DHAVE_CONFIG_H -I. -I. -I/scratch/tmp/gerald/GCC-H EAD/gcc 
-I/scratch/tmp/gerald/GCC-HEAD/gcc/. 
-I/scratch/tmp/gerald/GCC-HEAD/gcc/../include -I./../intl 
-I/scratch/tmp/gerald/GCC-HEAD/gcc/../libcpp/include 
-I/home/gerald/11-i386/include 
-I/scratch/tmp/gerald/GCC-HEAD/gcc/../libdecnumber 
-I/scratch/tmp/gerald/GCC-HEAD/gcc/../libdecnumber/dpd -I../libdecnumber 
-I/scrat ch/tmp/gerald/GCC-HEAD/gcc/../libbacktrace -I. -I. 
-I/scratch/tmp/gerald/GCC-H EAD/gcc -I/scratch/tmp/gerald/GCC-HEAD/gcc/. 
-I/scratch/tmp/gerald/GCC-HEAD/gcc/ ../include -I./../intl 
-I/scratch/tmp/gerald/GCC-HEAD/gcc/../libcpp/include 
-I/home/gerald/11-i386/include 
-I/scratch/tmp/gerald/GCC-HEAD/gcc/../libdecnumber 
-I/scratch/tmp/gerald/GCC-HEAD/gcc/../libdecnumber/dpd -I../libdecnumber 
-I/scrat ch/tmp/gerald/GCC-HEAD/gcc/../libbacktrace \ -DIN_GCOV_TOOL=1
-o libgcov-merge-tool.o /scratch/tmp/gerald/GCC-HEAD/gcc/../libgcc/libgcov-merge.c

Alas in tonights build (and the one with JOBS=1 I run during the day)
this now did not fail any longer. On the very same system and with the
same invocation of the build.

No I'm wondering what might have fixed this. The git lob did not show
me something obvious.

> I would recommend:
> 
> $ git show --format=fuller 871e5ada6d53d5eb495cc9f323983f347487c1b2

Ah, cool.  Great to know, thank you!

Gerald
Martin Liška June 8, 2020, 11:07 a.m. UTC | #11 
On 6/4/20 1:44 AM, Gerald Pfeifer wrote:
> On Wed, 3 Jun 2020, Martin Liška wrote:
>> Sorry for the breakage. Can you please paste full build output for the
>> problematic .o file?
>>
>> I bet it's a C file compilation, where we should use:
>>
>> __sync_val_compare_and_swap (counter, 0, (intptr_t)node);
>>
>> Can you please test it?
> 
> c++ -std=c++11 -fno-PIE -c -g -DIN_GCC -fno-strict-aliasing
> -fno-exceptions -fno-rtti -fasynchronous-unwind-tables -W -Wall
> -Wno-narrowing -Wwrite-strings -Wcast-qual -Wno-error=format-diag
> -Wno-format -Wmissing-format-attribute -Wove rloaded-virtual -pedantic
> -Wno-long-long -Wno-variadic-macros -Wno-overlength-st rings -fno-common
> -Wno-error -DHAVE_CONFIG_H -I. -I. -I/scratch/tmp/gerald/GCC-H EAD/gcc
> -I/scratch/tmp/gerald/GCC-HEAD/gcc/.
> -I/scratch/tmp/gerald/GCC-HEAD/gcc/../include -I./../intl
> -I/scratch/tmp/gerald/GCC-HEAD/gcc/../libcpp/include
> -I/home/gerald/11-i386/include
> -I/scratch/tmp/gerald/GCC-HEAD/gcc/../libdecnumber
> -I/scratch/tmp/gerald/GCC-HEAD/gcc/../libdecnumber/dpd -I../libdecnumber
> -I/scrat ch/tmp/gerald/GCC-HEAD/gcc/../libbacktrace -I. -I.
> -I/scratch/tmp/gerald/GCC-H EAD/gcc -I/scratch/tmp/gerald/GCC-HEAD/gcc/.
> -I/scratch/tmp/gerald/GCC-HEAD/gcc/ ../include -I./../intl
> -I/scratch/tmp/gerald/GCC-HEAD/gcc/../libcpp/include
> -I/home/gerald/11-i386/include
> -I/scratch/tmp/gerald/GCC-HEAD/gcc/../libdecnumber
> -I/scratch/tmp/gerald/GCC-HEAD/gcc/../libdecnumber/dpd -I../libdecnumber
> -I/scrat ch/tmp/gerald/GCC-HEAD/gcc/../libbacktrace \ -DIN_GCOV_TOOL=1
> -o libgcov-merge-tool.o /scratch/tmp/gerald/GCC-HEAD/gcc/../libgcc/libgcov-merge.c
> 
> Alas in tonights build (and the one with JOBS=1 I run during the day)
> this now did not fail any longer. On the very same system and with the
> same invocation of the build.
> 
> No I'm wondering what might have fixed this. The git lob did not show
> me something obvious.
> 
>> I would recommend:
>>
>> $ git show --format=fuller 871e5ada6d53d5eb495cc9f323983f347487c1b2
> 
> Ah, cool.  Great to know, thank you!
> 
> Gerald
> 

Hello.

Can you please test the following patch candidate:

diff --git a/libgcc/libgcov.h b/libgcc/libgcov.h
index 1456100815d..accecfe8221 100644
--- a/libgcc/libgcov.h
+++ b/libgcc/libgcov.h
@@ -410,7 +410,7 @@ gcov_counter_set_if_null (gcov_type *counter, struct gcov_kvp *node,
  {
  #if GCOV_SUPPORTS_ATOMIC
    if (use_atomic)
-    return !__sync_val_compare_and_swap (counter, NULL, (intptr_t)node);
+    return !__sync_val_compare_and_swap (counter, 0, (intptr_t)node);
    else
  #endif
      {

Thanks,
Martin
Martin Liška June 9, 2020, 11:09 a.m. UTC | #12 
On 6/8/20 1:07 PM, Martin Liška wrote:
> Can you please test the following patch candidate:

I've just pushed 862b9b225fb which should fix that.
Can you please test the current master?

Thanks,
Martin
Martin Liška June 17, 2020, 6:38 a.m. UTC | #13 
PING^1

On 6/3/20 8:28 AM, Martin Liška wrote:
> On 6/2/20 3:19 PM, Martin Liška wrote:
>> I'm suggesting to pre-allocate 16 gcov_kvp in the gcov run-time library.
>> Please take a look at the attached patch. I also added a test-case that
>> stresses that. I've just finished LTO PGO bootstrap of the GCC.
>>
>> Ready for master?
> 
> There's V2 of the patch:
> 
> - guard __atomic_fetch_add in GCOV_SUPPORTS_ATOMIC
> 
> Martin
Martin Liška June 30, 2020, 10:13 a.m. UTC | #14 
PING^2

On 6/17/20 8:38 AM, Martin Liška wrote:
> PING^1
> 
> On 6/3/20 8:28 AM, Martin Liška wrote:
>> On 6/2/20 3:19 PM, Martin Liška wrote:
>>> I'm suggesting to pre-allocate 16 gcov_kvp in the gcov run-time library.
>>> Please take a look at the attached patch. I also added a test-case that
>>> stresses that. I've just finished LTO PGO bootstrap of the GCC.
>>>
>>> Ready for master?
>>
>> There's V2 of the patch:
>>
>> - guard __atomic_fetch_add in GCOV_SUPPORTS_ATOMIC
>>
>> Martin
>
Martin Liška July 31, 2020, 7:56 a.m. UTC | #15 
On 6/3/20 8:28 AM, Martin Liška wrote:
> On 6/2/20 3:19 PM, Martin Liška wrote:
>> I'm suggesting to pre-allocate 16 gcov_kvp in the gcov run-time library.
>> Please take a look at the attached patch. I also added a test-case that
>> stresses that. I've just finished LTO PGO bootstrap of the GCC.
>>
>> Ready for master?
> 
> There's V2 of the patch:
> 
> - guard __atomic_fetch_add in GCOV_SUPPORTS_ATOMIC
> 
> Martin

There's V3 of the patch:
- TLS is used for in_recursion variable
- when we run out of statically allocated buffers, do not bail out

Patch can bootstrap on x86_64-linux-gnu and survives regression tests.

Ready to be installed?
Thanks,
Martin
Jan Hubicka July 31, 2020, 8:47 a.m. UTC | #16 
> On 6/3/20 8:28 AM, Martin Liška wrote:
> > On 6/2/20 3:19 PM, Martin Liška wrote:
> > > I'm suggesting to pre-allocate 16 gcov_kvp in the gcov run-time library.
> > > Please take a look at the attached patch. I also added a test-case that
> > > stresses that. I've just finished LTO PGO bootstrap of the GCC.
> > > 
> > > Ready for master?
> > 
> > There's V2 of the patch:
> > 
> > - guard __atomic_fetch_add in GCOV_SUPPORTS_ATOMIC
> > 
> > Martin
> 
> There's V3 of the patch:
> - TLS is used for in_recursion variable
> - when we run out of statically allocated buffers, do not bail out
> 
> Patch can bootstrap on x86_64-linux-gnu and survives regression tests.
> 
> Ready to be installed?
> diff --git a/gcc/testsuite/gcc.dg/tree-prof/indir-call-prof-malloc.c b/gcc/testsuite/gcc.dg/tree-prof/indir-call-prof-malloc.c
> new file mode 100644
> index 00000000000..454e224c95f
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/tree-prof/indir-call-prof-malloc.c
> @@ -0,0 +1,49 @@
> +/* { dg-options "-O2 -ldl" } */

I think this needs to be restricted to targets that have dl library....
Otherwise the patch looks good to me.
We may try to add the testcase doing division by all possible integers
in two threads or so to stress the race conditions in link list
management.

Thank you,
Honza
> +
> +#define _GNU_SOURCE
> +#include <stdio.h>
> +#include <stdint.h>
> +#include <dlfcn.h>
> +
> +int global;
> +int global2;
> +
> +void report1 (size_t size)
> +{
> +  global++;
> +}
> +
> +void report2 (size_t size)
> +{
> +  global2++;
> +}
> +
> +typedef void (*tp) (size_t);
> +static tp fns[] = {report1, report2};
> +
> +void* malloc(size_t size)
> +{
> +  static void* (*real_malloc)(size_t) = NULL;
> +  if (!real_malloc)
> +      real_malloc = dlsym(RTLD_NEXT, "malloc");
> +
> +  void *p = real_malloc (size);
> +  fns[size % 2] (size);
> +  // fprintf(stderr, "malloc(%d) = %p\n", size, p);
> +  return p;
> +}
> +
> +void *calloc (size_t n, size_t size)
> +{
> +  void *ptr = malloc (n * size);
> +  __builtin_memset (ptr, 0, n * size);
> +  return ptr;
> +}
> +
> +void *ptr;
> +
> +int main()
> +{
> +  ptr = malloc (16);
> +  return 0;
> +}
> diff --git a/libgcc/libgcov-driver.c b/libgcc/libgcov-driver.c
> index 2590593a58a..58914268d4e 100644
> --- a/libgcc/libgcov-driver.c
> +++ b/libgcc/libgcov-driver.c
> @@ -588,6 +588,12 @@ struct gcov_root __gcov_root;
>  struct gcov_master __gcov_master = 
>    {GCOV_VERSION, 0};
>  
> +/* Pool of pre-allocated gcov_kvp strutures.  */
> +struct gcov_kvp __gcov_kvp_pool[GCOV_PREALLOCATED_KVP];
> +
> +/* Index to first free gcov_kvp in the pool.  */
> +unsigned __gcov_kvp_pool_index;
> +
>  void
>  __gcov_exit (void)
>  {
> diff --git a/libgcc/libgcov.h b/libgcc/libgcov.h
> index 81e18950a50..8be5bebcac0 100644
> --- a/libgcc/libgcov.h
> +++ b/libgcc/libgcov.h
> @@ -250,6 +250,8 @@ struct indirect_call_tuple
>    
>  /* Exactly one of these will be active in the process.  */
>  extern struct gcov_master __gcov_master;
> +extern struct gcov_kvp __gcov_kvp_pool[GCOV_PREALLOCATED_KVP];
> +extern unsigned __gcov_kvp_pool_index;
>  
>  /* Dump a set of gcov objects.  */
>  extern void __gcov_dump_one (struct gcov_root *) ATTRIBUTE_HIDDEN;
> @@ -402,6 +404,47 @@ gcov_counter_add (gcov_type *counter, gcov_type value,
>      *counter += value;
>  }
>  
> +/* Allocate gcov_kvp from heap.  If we are recursively called, then allocate
> +   it from a list of pre-allocated pool.  */
> +
> +static inline struct gcov_kvp *
> +allocate_gcov_kvp (void)
> +{
> +  struct gcov_kvp *new_node = NULL;
> +
> +  static
> +#if defined(HAVE_CC_TLS)
> +__thread
> +#endif
> +  volatile unsigned in_recursion ATTRIBUTE_UNUSED = 0;
> +
> +#if !defined(IN_GCOV_TOOL) && !defined(L_gcov_merge_topn)
> +  if (__builtin_expect (in_recursion, 0))
> +    {
> +      unsigned index;
> +#if GCOV_SUPPORTS_ATOMIC
> +      index
> +	= __atomic_fetch_add (&__gcov_kvp_pool_index, 1, __ATOMIC_RELAXED);
> +#else
> +      index = __gcov_kvp_pool_index++;
> +#endif
> +      if (index < GCOV_PREALLOCATED_KVP)
> +	new_node = &__gcov_kvp_pool[index];
> +      else
> +	/* Do not crash in the situation.  */
> +	return NULL;
> +    }
> +  else
> +#endif
> +    {
> +      in_recursion = 1;
> +      new_node = (struct gcov_kvp *)xcalloc (1, sizeof (struct gcov_kvp));
> +      in_recursion = 0;
> +    }
> +
> +  return new_node;
> +}
> +
>  /* 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.  */
> @@ -443,8 +486,10 @@ gcov_topn_add_value (gcov_type *counters, gcov_type value, gcov_type count,
>      }
>    else
>      {
> -      struct gcov_kvp *new_node
> -	= (struct gcov_kvp *)xcalloc (1, sizeof (struct gcov_kvp));
> +      struct gcov_kvp *new_node = allocate_gcov_kvp ();
> +      if (new_node == NULL)
> +	return;
> +
>        new_node->value = value;
>        new_node->count = count;
>  
> -- 
> 2.27.0
>
Martin Liška July 31, 2020, 8:57 a.m. UTC | #17 
On 7/31/20 10:47 AM, Jan Hubicka wrote:
> I think this needs to be restricted to targets that have dl library....

Hm, I can't find a dg-require that is used for similar test-cases.

Martin
Jan Hubicka July 31, 2020, 3:46 p.m. UTC | #18 
> On 7/31/20 10:47 AM, Jan Hubicka wrote:
> > I think this needs to be restricted to targets that have dl library....
> 
> Hm, I can't find a dg-require that is used for similar test-cases.
OK, lets get it in and see if it breaks :)

Honza
> 
> Martin
diff mbox series

Patch

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 (&current_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 */