From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: by sourceware.org (Postfix, from userid 7880) id 6156A3858C5E; Tue, 25 Apr 2023 08:10:11 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 6156A3858C5E DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1682410211; bh=PTWmWcRNQ5TBDIqVCk2upq993eus8av7VzRqEi2keK0=; h=From:To:Subject:Date:From; b=aoOcExot8OYQy1sxh6fx0jA+DTNMAuEgM2eZqApi4RSsmye1ZOdwwgg9PUwUdBm0h HvtxToZYBgN6I5E4zsSGRwO8WROb2mhvZHwO/dTGFLR9tHBoWn01E6Z2cO2cHDi15D biqUtN8an+2pYPRgZH26an1lPuRmxeHi084D+Ov8= Content-Type: text/plain; charset="us-ascii" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit From: Ondrej Kubanek To: gcc-cvs@gcc.gnu.org Subject: [gcc(refs/users/kubaneko/heads/histogram)] added modulo histogram and improved garbage collection X-Act-Checkin: gcc X-Git-Author: kubaneko X-Git-Refname: refs/users/kubaneko/heads/histogram X-Git-Oldrev: 9a22679c15e02516b80d632401d46a8af2f1a865 X-Git-Newrev: 3b7b26109c35d562ef60fc0cee279039fcbf4749 Message-Id: <20230425081011.6156A3858C5E@sourceware.org> Date: Tue, 25 Apr 2023 08:10:11 +0000 (GMT) List-Id: https://gcc.gnu.org/g:3b7b26109c35d562ef60fc0cee279039fcbf4749 commit 3b7b26109c35d562ef60fc0cee279039fcbf4749 Author: kubaneko Date: Tue Apr 25 08:09:35 2023 +0000 added modulo histogram and improved garbage collection Diff: --- gcc/cfgloop.cc | 33 +++++++++++++++++++++++++++++++-- gcc/cfgloop.h | 1 + gcc/cfgloopmanip.cc | 2 ++ gcc/lto-streamer-in.cc | 17 ++++++++++++++--- gcc/lto-streamer-out.cc | 13 +++++++++++-- gcc/profile.cc | 22 ++++++++++++++++------ gcc/tree-profile.cc | 3 ++- gcc/value-prof.cc | 16 ++++++++++++++-- libgcc/libgcov-profiler.c | 25 ++++++++++++++++++------- 9 files changed, 109 insertions(+), 23 deletions(-) diff --git a/gcc/cfgloop.cc b/gcc/cfgloop.cc index e2c1bab996f..0f5121117ca 100644 --- a/gcc/cfgloop.cc +++ b/gcc/cfgloop.cc @@ -201,6 +201,9 @@ flow_loop_free (class loop *loop) ggc_free (loop->exits); if (loop->counters) { + va_heap::release (loop->counters->hist); + if (loop->counters->mod) + va_heap::release (loop->counters->mod); ggc_free (loop->counters); } ggc_free (loop); @@ -2219,7 +2222,7 @@ histogram_counters_minus_upper_bound (histogram_counters *&hist_c, { if (difference == 0 || !hist_c) return; - if (hist_c->sum == 0) + if (hist_c->sum == 0 && !hist_c->mod) { va_heap::release (hist_c->hist); ggc_free (hist_c); @@ -2259,7 +2262,7 @@ histogram_counters_minus_upper_bound (histogram_counters *&hist_c, pow2 = pow2 << 1; } // if there are no more iterations we do not care - if (hist_c->sum == 0) + if (hist_c->sum == 0 && !hist_c->mod) { va_heap::release (hist_c->hist); ggc_free (hist_c); @@ -2287,6 +2290,21 @@ histogram_counters_minus_upper_bound (histogram_counters *&hist_c, hist[i] -= diff; pow2 <<= 1; } + if (hist_c->mod) + { + auto &mod_h = *(hist_c->mod); + unsigned int mod_size = param_profile_histogram_size_mod; + // rotate the values by the difference + auto_vec temp; + for (unsigned int j = 0; j < mod_size; ++j) + { + temp.safe_push (mod_h[j]); + } + for (unsigned int j = 0; j < mod_size; ++j) + { + mod_h[j] = temp[(mod_size + j - (difference % mod_size)) % mod_size]; + } + } } void @@ -2298,6 +2316,8 @@ histogram_counters_div_upper_bound (histogram_counters *&hist_c, if (hist_c->sum == 0) { va_heap::release (hist_c->hist); + if (hist_c->mod) + va_heap::release (hist_c->mod); ggc_free (hist_c); hist_c = NULL; return; @@ -2325,6 +2345,15 @@ histogram_counters_div_upper_bound (histogram_counters *&hist_c, hist[ind] += hist[MIN (1, i)]; hist[i] = 0; } + // we do not try to maintain modulo info when dividing since it is often + // impossible + // TODO we can sometimes save this if the divisor and the mod_size are + // co-prime + if (hist_c->mod) + { + va_heap::release (hist_c->mod); + hist_c->mod = NULL; + } } // adjust estimates after peeling npeel times diff --git a/gcc/cfgloop.h b/gcc/cfgloop.h index f9e20f95f4e..2c3eee123dc 100644 --- a/gcc/cfgloop.h +++ b/gcc/cfgloop.h @@ -99,6 +99,7 @@ struct GTY (()) histogram_counters bool adjusted; gcov_type sum; vec *GTY ((skip)) hist; + vec *GTY ((skip)) mod; }; typedef class loop *loop_p; diff --git a/gcc/cfgloopmanip.cc b/gcc/cfgloopmanip.cc index 1ff9b1f5524..42ce1a529b3 100644 --- a/gcc/cfgloopmanip.cc +++ b/gcc/cfgloopmanip.cc @@ -965,6 +965,8 @@ copy_loop_info (class loop *loop, class loop *target) target->counters->sum = loop->counters->sum; target->counters->adjusted = loop->counters->adjusted; target->counters->hist = vec_safe_copy (loop->counters->hist); + if (loop->counters->mod) + target->counters->mod = vec_safe_copy (loop->counters->mod); } } diff --git a/gcc/lto-streamer-in.cc b/gcc/lto-streamer-in.cc index b08053d7ec3..ccaf10c3e55 100644 --- a/gcc/lto-streamer-in.cc +++ b/gcc/lto-streamer-in.cc @@ -1132,15 +1132,26 @@ input_cfg (class lto_input_block *ib, class data_in *data_in, loop->counters = ggc_alloc (); loop->counters->sum = streamer_read_gcov_count (ib); loop->counters->hist = NULL; - vec_safe_grow_cleared (loop->counters->hist, - param_profile_histogram_size_lin - + param_profile_histogram_size_exp); + loop->counters->mod = NULL; + vec_safe_grow (loop->counters->hist, + param_profile_histogram_size_lin + + param_profile_histogram_size_exp); for (int i = 0; i < param_profile_histogram_size_lin + param_profile_histogram_size_exp; ++i) { (*loop->counters->hist)[i] = streamer_read_gcov_count (ib); } + // do we have modulos + if (streamer_read_hwi (ib)) + { + vec_safe_grow (loop->counters->mod, + param_profile_histogram_size_mod); + for (int i = 0; i < param_profile_histogram_size_mod; ++i) + { + (*loop->counters->mod)[i] = streamer_read_gcov_count (ib); + } + } } /* Read OMP SIMD related info. */ diff --git a/gcc/lto-streamer-out.cc b/gcc/lto-streamer-out.cc index e6079c62af0..657129080ec 100644 --- a/gcc/lto-streamer-out.cc +++ b/gcc/lto-streamer-out.cc @@ -2186,12 +2186,21 @@ output_cfg (struct output_block *ob, struct function *fn) { streamer_write_gcov_count (ob, loop->counters->sum); for (unsigned int i = 0; - i < (unsigned int) param_profile_histogram_size_lin - + param_profile_histogram_size_exp; + i < (unsigned int) (param_profile_histogram_size_lin + + param_profile_histogram_size_exp); ++i) { streamer_write_gcov_count (ob, (*loop->counters->hist)[i]); } + streamer_write_hwi (ob, loop->counters->mod != NULL); + if (loop->counters->mod) + { + for (unsigned int i = 0; + i < (unsigned int) param_profile_histogram_size_mod; ++i) + { + streamer_write_gcov_count (ob, (*loop->counters->mod)[i]); + } + } } /* Write OMP SIMD related info. */ diff --git a/gcc/profile.cc b/gcc/profile.cc index 8199ed6350b..d2b8dfcadc1 100644 --- a/gcc/profile.cc +++ b/gcc/profile.cc @@ -930,23 +930,33 @@ compute_value_histograms (histogram_values values, unsigned cfg_checksum, { lp->counters = ggc_alloc (); gcov_type sum = 0; + unsigned int tot_size = param_profile_histogram_size_lin + + param_profile_histogram_size_exp; lp->counters->adjusted = false; lp->counters->hist = NULL; - vec_safe_grow_cleared (lp->counters->hist, - param_profile_histogram_size_lin - + param_profile_histogram_size_exp); - for (int i = 0; i < param_profile_histogram_size_lin - + param_profile_histogram_size_exp; - ++i) + // iteration vector + vec_safe_grow_cleared (lp->counters->hist, tot_size); + for (int i = 0; i < (int) tot_size; ++i) { auto hst = lp->counters->hist; (*hst)[i] = act_count[t][i]; sum += act_count[t][i]; } lp->counters->sum = sum; + + // modular vector + lp->counters->mod = NULL; + vec_safe_grow_cleared (lp->counters->mod, + param_profile_histogram_size_mod); + for (int j = 0; j < param_profile_histogram_size_mod; ++j) + { + auto mod = lp->counters->mod; + (*mod)[j] = act_count[t][j + tot_size]; + } if (sum == 0) { va_heap::release (lp->counters->hist); + va_heap::release (lp->counters->mod); ggc_free (lp->counters); lp->counters = NULL; } diff --git a/gcc/tree-profile.cc b/gcc/tree-profile.cc index a4ed11f2219..24102320620 100644 --- a/gcc/tree-profile.cc +++ b/gcc/tree-profile.cc @@ -367,7 +367,8 @@ gimple_gen_histogram_profiler (histogram_value value, tree ref_ptr = tree_coverage_counter_addr (tag, 0); tree hist_size = build_int_cst_type ( gcov_type_node, param_profile_histogram_size_lin - | (gcov_type (param_profile_histogram_size_exp) << 32)); + | (gcov_type (param_profile_histogram_size_exp) << 10) + | (gcov_type (param_profile_histogram_size_mod) << 20)); gcall *call; auto_vec exits = get_loop_exit_edges (lp); for (auto exit : exits) diff --git a/gcc/value-prof.cc b/gcc/value-prof.cc index d7d7cd18ce8..5e029c811e2 100644 --- a/gcc/value-prof.cc +++ b/gcc/value-prof.cc @@ -283,6 +283,16 @@ dump_histogram_value (FILE *dump_file, histogram_value hist) (int64_t) hist->hvalue .counters[(param_profile_histogram_size_lin - lin2_log) + i]); } + for (int i = 0; i < param_profile_histogram_size_mod; ++i) + { + fprintf (dump_file, + "Histogram counter histogram%" PRId64 " mod:%" PRId64 + ".\n", + (int64_t) i, + (int64_t) hist->hvalue + .counters[i + param_profile_histogram_size_lin + + param_profile_histogram_size_exp]); + } } break; @@ -404,7 +414,8 @@ stream_in_histogram_value (class lto_input_block *ib, gimple *stmt) case HIST_TYPE_HISTOGRAM: ncounters = param_profile_histogram_size_lin - + param_profile_histogram_size_exp; + + param_profile_histogram_size_exp + + param_profile_histogram_size_mod; break; case HIST_TYPE_POW2: case HIST_TYPE_AVERAGE: @@ -2010,7 +2021,8 @@ gimple_find_values_to_profile (histogram_values *values) case HIST_TYPE_HISTOGRAM: hist->n_counters = param_profile_histogram_size_lin - + param_profile_histogram_size_exp; + + param_profile_histogram_size_exp + + param_profile_histogram_size_mod; break; default: diff --git a/libgcc/libgcov-profiler.c b/libgcc/libgcov-profiler.c index 7063af3579f..65427534e91 100644 --- a/libgcc/libgcov-profiler.c +++ b/libgcc/libgcov-profiler.c @@ -62,10 +62,13 @@ void __gcov_histogram_profiler(gcov_type *counters, gcov_type value, gcc_assert(hist_sizes >= 0 && value >= 0); gcov_type_unsigned hist_size = hist_sizes; gcov_type_unsigned u_value = value; - gcov_type_unsigned exp_size = hist_size >> 32; - gcov_type_unsigned lin_size = - hist_size & ((((gcov_type_unsigned)1) << 32) - 1); + // uncode section sizes + gcov_type_unsigned mask = (((gcov_type_unsigned)1) << 10) - 1; + gcov_type_unsigned lin_size = hist_size & mask; + gcov_type_unsigned exp_size = (hist_size >> 10) & mask; + gcov_type_unsigned mod_size = hist_size >> 20; gcov_type_unsigned tot_size = exp_size + lin_size; + // add to the regular histogram if (u_value < lin_size) { counters[value]++; } else { @@ -81,6 +84,8 @@ void __gcov_histogram_profiler(gcov_type *counters, gcov_type value, } } } + // add to the modular histogram + counters[tot_size + (u_value % mod_size)]++; } #endif @@ -92,10 +97,13 @@ void __gcov_histogram_profiler_atomic(gcov_type *counters, gcov_type value, gcc_assert(hist_sizes >= 0 && value >= 0); gcov_type_unsigned hist_size = hist_sizes; gcov_type_unsigned u_value = value; - gcov_type_unsigned exp_size = hist_size >> 32; - gcov_type_unsigned lin_size = - hist_size & ((((gcov_type_unsigned)1) << 32) - 1); - gcov_type_unsigned tot_size = lin_size + tot_size; + // uncode section sizes + gcov_type_unsigned mask = (((gcov_type_unsigned)1) << 10) - 1; + gcov_type_unsigned lin_size = hist_size & mask; + gcov_type_unsigned exp_size = (hist_size >> 10) & mask; + gcov_type_unsigned mod_size = hist_size >> 20; + gcov_type_unsigned tot_size = exp_size + lin_size; + // add to the regular histogram if (u_value < lin_size) { __atomic_fetch_add(&counters[value], 1, __ATOMIC_RELAXED); } else { @@ -108,6 +116,9 @@ void __gcov_histogram_profiler_atomic(gcov_type *counters, gcov_type value, __atomic_fetch_add(&counters[tot_size - 1], 1, __ATOMIC_RELAXED); } } + // add to the modular histogram + __atomic_fetch_add(&counters[tot_size + (u_value % mod_size)], 1, + __ATOMIC_RELAXED); } #endif