public inbox for gcc-cvs@sourceware.org
help / color / mirror / Atom feed
* [gcc(refs/users/kubaneko/heads/histogram)] maintaining histogram prototype
@ 2023-03-07 20:09 Ondrej Kubanek
0 siblings, 0 replies; only message in thread
From: Ondrej Kubanek @ 2023-03-07 20:09 UTC (permalink / raw)
To: gcc-cvs
https://gcc.gnu.org/g:18ffdd8c9ae664bf186de31febebf9bc5c78ec27
commit 18ffdd8c9ae664bf186de31febebf9bc5c78ec27
Author: kubaneko <kubanek0ondrej@gmail.com>
Date: Tue Mar 7 20:09:11 2023 +0000
maintaining histogram prototype
Diff:
---
gcc/cfgloop.cc | 73 ++++++++++++++++++++++++++++++++++++++
gcc/cfgloop.h | 83 ++++++++++++++++++++++++++++++++++++++------
gcc/loop-unroll.cc | 5 +++
gcc/tree-ssa-loop-ivcanon.cc | 4 ++-
gcc/tree-vect-loop.cc | 7 ++++
5 files changed, 160 insertions(+), 12 deletions(-)
diff --git a/gcc/cfgloop.cc b/gcc/cfgloop.cc
index 72673b1fbab..f5e229e18c1 100644
--- a/gcc/cfgloop.cc
+++ b/gcc/cfgloop.cc
@@ -2185,3 +2185,76 @@ loops_list::walk_loop_tree (class loop *root, unsigned flags)
this->to_visit.quick_push (root->num);
}
+void histogram_counters_minus_upper_bound (histogram_counters* hist_c, gcov_type_unsigned difference){
+ if (hist_c==NULL || difference==0)
+ return;
+ auto hist=*(hist_c->hist);
+ unsigned int lin_size=param_profile_histogram_size_lin;
+ unsigned int lin_pow2=floor_log2(lin_size-1);
+ unsigned int tot_size=param_profile_histogram_size;
+ gcov_type_unsigned log_diff=floor_log2(difference);
+ unsigned int i=1;
+ for(; i<lin_size-1 && i<tot_size-1; i++){
+ if (i<=difference){
+ hist[0]+=hist[i];
+ } else {
+ hist[i-difference]+=hist[i];
+ }
+ hist[i]=0;
+ }
+ // we try to restore some of the linear histogram
+ // for the last linear counter containing also lesser values then nearest pow2
+ // assumption is uniform
+ gcov_type_unsigned upper_bound_lin=(1<<(ceil_log2(lin_size)-1));
+ if (lin_size>2 && difference<upper_bound_lin && i<tot_size-1){
+ gcov_type_unsigned lin_size_val=hist[lin_size-1]/((upper_bound_lin-1)-(lin_size-2));
+ for (int j=int(i)-int(difference);j<gcov_type(upper_bound_lin)-gcov_type(difference)+1
+ && j<int(lin_size)-1;i++) {
+ if (j<0) {
+ hist[0]+=lin_size_val;
+ } else {
+ hist[j]+=lin_size_val;
+ }
+ hist[lin_size-1]-=lin_size_val;
+ }
+ i++;
+ }
+ // Index where difference would be placed
+ unsigned diff_index=log_diff+(lin_size-lin_pow2)-1;
+ for (; i<diff_index && difference<lin_size && i<tot_size-1;i++){
+ hist[0]+=hist[i];
+ hist[i]=0;
+ }
+ for (; i<tot_size-1 && (1<<(i-diff_index+2))<10000;i++){
+ // We assume uniform distribution
+ // tot_size -1 should not be touched We know little about it
+ gcov_type_unsigned share=hist[i]/(1<<(i-diff_index+2));
+ hist[i-1]+=share;
+ hist[i]-=share;
+ }
+}
+
+void histogram_counters_div_upper_bound (histogram_counters* hist_c, unsigned int divisor){
+ if (hist_c==NULL || divisor<2)
+ return;
+ auto hist=*(hist_c->hist);
+ unsigned int lin_size=param_profile_histogram_size_lin;
+ unsigned int tot_size=param_profile_histogram_size;
+ gcov_type_unsigned log_div=floor_log2(divisor);
+ unsigned int i=1;
+ for(; i<lin_size-1 && i<tot_size-1; i++){
+ hist[i/divisor]+=hist[i];
+ hist[i]=0;
+ }
+
+ for (;i<tot_size-1;i++){
+ gcov_type_unsigned upper_diff=((1<<(ceil_log2(lin_size)+i-lin_size))-1)/divisor;
+ if (upper_diff<lin_size-1 && lin_size>1){
+ hist[upper_diff==0 ? 1 : upper_diff]+=hist[i];
+ hist[i]=0;
+ } else {
+ hist[i-log_div>0?i-log_div : 1]+=hist[i];
+ hist[i]=0;
+ }
+ }
+}
diff --git a/gcc/cfgloop.h b/gcc/cfgloop.h
index 0c9c82c6ed3..48badc22648 100644
--- a/gcc/cfgloop.h
+++ b/gcc/cfgloop.h
@@ -99,20 +99,78 @@ struct GTY(()) histogram_counters{
vec<gcov_type, va_heap, vl_embed> * GTY((skip)) hist;
};
-// quantil function for the distribution
-// int quantil_asdf(float koef, histogram_counters* count){
-// gcc_assert(0<koef && koef<=1);
-// gcov_type quant=0;
-// int i=0;
-// for (;i<69;++i) {
-// if (quant+count->hist[i]<koef*count->sum) {
-// quant+=count->hist[i];
+// void histogram_counters_minus_upper_bound (histogram_counters* hist_c, gcov_type_unsigned difference){
+// if (hist_c==NULL || difference==0)
+// return;
+// auto hist=*(hist_c->hist);
+// unsigned int lin_size=param_profile_histogram_size_lin;
+// unsigned int lin_pow2=floor_log2(lin_size-1);
+// unsigned int tot_size=param_profile_histogram_size;
+// gcov_type_unsigned log_diff=floor_log2(difference);
+// unsigned int i=1;
+// for(; i<lin_size-1 && i<tot_size-1; i++){
+// if (i<=difference){
+// hist[0]+=hist[i];
// } else {
-// break;
+// hist[i-difference]+=hist[i];
// }
+// hist[i]=0;
// }
-// return i;
-// };
+// // we try to restore some of the linear histogram
+// // for the last linear counter containing also lesser values then nearest pow2
+// // assumption is uniform
+// gcov_type_unsigned upper_bound_lin=(1<<(ceil_log2(lin_size)-1));
+// if (lin_size>2 && difference<upper_bound_lin && i<tot_size-1){
+// gcov_type_unsigned lin_size_val=hist[lin_size-1]/((upper_bound_lin-1)-(lin_size-2));
+// for (int j=int(i)-int(difference);j<gcov_type(upper_bound_lin)-gcov_type(difference)+1 && j<int(lin_size)-1;i++) {
+// if (j<0) {
+// hist[0]+=lin_size_val;
+// } else {
+// hist[j]+=lin_size_val;
+// }
+// hist[lin_size-1]-=lin_size_val;
+// }
+// i++;
+// }
+// // Index where difference would be placed
+// unsigned diff_index=log_diff+(lin_size-lin_pow2)-1;
+// for (; i<diff_index && difference<lin_size && i<tot_size-1;i++){
+// hist[0]+=hist[i];
+// hist[i]=0;
+// }
+// for (; i<tot_size-1 && (1<<(i-diff_index+2))<10000;i++){
+// // We assume uniform distribution
+// // tot_size -1 should not be touched We know little about it
+// gcov_type_unsigned share=hist[i]/(1<<(i-diff_index+2));
+// hist[i-1]+=share;
+// hist[i]-=share;
+// }
+// }
+//
+// void histogram_counters_div_upper_bound (histogram_counters* hist_c, unsigned int divisor){
+// if (hist_c==NULL || divisor<2)
+// return;
+// auto hist=*(hist_c->hist);
+// unsigned int lin_size=param_profile_histogram_size_lin;
+// unsigned int tot_size=param_profile_histogram_size;
+// gcov_type_unsigned log_div=floor_log2(divisor);
+// unsigned int i=1;
+// for(; i<lin_size-1 && i<tot_size-1; i++){
+// hist[i/divisor]+=hist[i];
+// hist[i]=0;
+// }
+//
+// for (;i<tot_size-1;i++){
+// gcov_type_unsigned upper_diff=((1<<(ceil_log2(lin_size)+i-lin_size))-1)/divisor;
+// if (upper_diff<lin_size-1 && lin_size>1){
+// hist[upper_diff==0 ? 1 : upper_diff]+=hist[i];
+// hist[i]=0;
+// } else {
+// hist[i-log_div>0?i-log_div : 1]+=hist[i];
+// hist[i]=0;
+// }
+// }
+// }
typedef class loop *loop_p;
@@ -942,6 +1000,9 @@ extern bool get_estimated_loop_iterations (class loop *loop, widest_int *nit);
extern bool get_max_loop_iterations (const class loop *loop, widest_int *nit);
extern bool get_likely_max_loop_iterations (class loop *loop, widest_int *nit);
extern int bb_loop_depth (const_basic_block);
+extern void histogram_counters_minus_upper_bound
+ (histogram_counters* hist_c, gcov_type_unsigned difference);
+extern void histogram_counters_div_upper_bound (histogram_counters* hist_c, unsigned int divisor);
/* Converts VAL to widest_int. */
diff --git a/gcc/loop-unroll.cc b/gcc/loop-unroll.cc
index 93333d8ba11..eea18471775 100644
--- a/gcc/loop-unroll.cc
+++ b/gcc/loop-unroll.cc
@@ -533,6 +533,7 @@ unroll_loop_constant_iterations (class loop *loop)
desc->noloop_assumptions = NULL_RTX;
desc->niter -= exit_mod;
loop->nb_iterations_upper_bound -= exit_mod;
+ histogram_counters_minus_upper_bound(loop->counters,exit_mod);
if (loop->any_estimate
&& wi::leu_p (exit_mod, loop->nb_iterations_estimate))
loop->nb_iterations_estimate -= exit_mod;
@@ -578,6 +579,7 @@ unroll_loop_constant_iterations (class loop *loop)
desc->niter -= exit_mod + 1;
loop->nb_iterations_upper_bound -= exit_mod + 1;
+ histogram_counters_minus_upper_bound(loop->counters,exit_mod+1);
if (loop->any_estimate
&& wi::leu_p (exit_mod + 1, loop->nb_iterations_estimate))
loop->nb_iterations_estimate -= exit_mod + 1;
@@ -632,6 +634,7 @@ unroll_loop_constant_iterations (class loop *loop)
desc->niter /= max_unroll + 1;
loop->nb_iterations_upper_bound
= wi::udiv_trunc (loop->nb_iterations_upper_bound, max_unroll + 1);
+ histogram_counters_div_upper_bound(loop->counters,exit_mod);
if (loop->any_estimate)
loop->nb_iterations_estimate
= wi::udiv_trunc (loop->nb_iterations_estimate, max_unroll + 1);
@@ -1095,6 +1098,7 @@ unroll_loop_runtime_iterations (class loop *loop)
gen_int_mode (max_unroll + 1, desc->mode));
loop->nb_iterations_upper_bound
= wi::udiv_trunc (loop->nb_iterations_upper_bound, max_unroll + 1);
+ histogram_counters_div_upper_bound(loop->counters, max_unroll + 1);
if (loop->any_estimate)
loop->nb_iterations_estimate
= wi::udiv_trunc (loop->nb_iterations_estimate, max_unroll + 1);
@@ -1107,6 +1111,7 @@ unroll_loop_runtime_iterations (class loop *loop)
simplify_gen_binary (MINUS, desc->mode, desc->niter_expr, const1_rtx);
desc->noloop_assumptions = NULL_RTX;
--loop->nb_iterations_upper_bound;
+ histogram_counters_minus_upper_bound(loop->counters,1);
if (loop->any_estimate
&& loop->nb_iterations_estimate != 0)
--loop->nb_iterations_estimate;
diff --git a/gcc/tree-ssa-loop-ivcanon.cc b/gcc/tree-ssa-loop-ivcanon.cc
index 7ef2a3e2525..5d4957282d6 100644
--- a/gcc/tree-ssa-loop-ivcanon.cc
+++ b/gcc/tree-ssa-loop-ivcanon.cc
@@ -1047,7 +1047,8 @@ try_peel_loop (class loop *loop,
psum+=(*(loop->counters->hist))[i];
if ((100*psum)/sum>=param_profile_histogram_peel_prcnt)
{
- if (i==param_profile_histogram_size_lin-1 && i!=0){
+ if (i==param_profile_histogram_size_lin-1 && i!=0 &&
+ param_profile_histogram_size_lin!=param_profile_histogram_size){
// Last linear counter absorbs iterations smaller then next power of 2
npeel=(1<<floor_log2(param_profile_histogram_size_lin-1))-1;
} else {
@@ -1142,6 +1143,7 @@ try_peel_loop (class loop *loop,
}
if (loop->any_upper_bound)
{
+ histogram_counters_minus_upper_bound(loop->counters,npeel);
if (wi::ltu_p (npeel, loop->nb_iterations_upper_bound))
loop->nb_iterations_upper_bound -= npeel;
else
diff --git a/gcc/tree-vect-loop.cc b/gcc/tree-vect-loop.cc
index ab7af0ea3b8..74622aef0f9 100644
--- a/gcc/tree-vect-loop.cc
+++ b/gcc/tree-vect-loop.cc
@@ -11067,6 +11067,13 @@ vect_transform_loop (loop_vec_info loop_vinfo, gimple *loop_vectorized_call)
lowest_vf) - 1
: wi::udiv_floor (loop->nb_iterations_upper_bound + bias_for_lowest,
lowest_vf) - 1);
+ if (final_iter_may_be_partial){
+ histogram_counters_div_upper_bound(loop->counters,lowest_vf);
+ histogram_counters_minus_upper_bound(loop->counters,1);
+ } else {
+ histogram_counters_div_upper_bound(loop->counters,lowest_vf);
+ histogram_counters_minus_upper_bound(loop->counters,1);
+ }
if (main_vinfo
/* Both peeling for alignment and peeling for gaps can end up
with the scalar epilogue running for more than VF-1 iterations. */
^ permalink raw reply [flat|nested] only message in thread
only message in thread, other threads:[~2023-03-07 20:09 UTC | newest]
Thread overview: (only message) (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2023-03-07 20:09 [gcc(refs/users/kubaneko/heads/histogram)] maintaining histogram prototype Ondrej Kubanek
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).