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).