[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.
Related show

Commit Message

Martin Liška April 6, 2020, 8:03 a.m.
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. | #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. | #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. | #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. | #4
PING^2

On 5/15/20 11:57 AM, Martin Liška wrote:
> We're in stage1: PING^

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 */