[gcc(refs/users/kubaneko/heads/histogram)] added histogram_counters structure

[Ondrej Kubanek]

https://gcc.gnu.org/g:1aa8abc66731f6256653ef54607eb0b759ce1467

commit 1aa8abc66731f6256653ef54607eb0b759ce1467
Author: kubaneko <kubanek0ondrej@gmail.com>
Date:   Tue Nov 8 15:27:20 2022 +0000

    added histogram_counters structure

Diff:
---
 gcc/cfgloop.cc |  2 ++
 gcc/cfgloop.h  | 52 ++++++++++++++++++++++++++++++++++++++++++++++++++--
 gcc/profile.cc |  6 +++++-
 3 files changed, 57 insertions(+), 3 deletions(-)

diff --git a/gcc/cfgloop.cc b/gcc/cfgloop.cc
index 8523c11fe95..201893f1624 100644
--- a/gcc/cfgloop.cc
+++ b/gcc/cfgloop.cc
@@ -1769,6 +1769,8 @@ loop_preheader_edge (const class loop *loop)
   edge e;
   edge_iterator ei;
 
+  // gcc_assert (loops_state_satisfies_p (LOOPS_HAVE_PREHEADERS)
+  //          && ! loops_state_satisfies_p (LOOPS_MAY_HAVE_MULTIPLE_LATCHES));
 
   FOR_EACH_EDGE (e, ei, loop->header->preds)
     if (e->src != loop->latch)
diff --git a/gcc/cfgloop.h b/gcc/cfgloop.h
index 63c75e8a0de..7b9a854f266 100644
--- a/gcc/cfgloop.h
+++ b/gcc/cfgloop.h
@@ -92,6 +92,55 @@ struct loop_exit_hasher : ggc_ptr_hash<loop_exit>
   static void remove (loop_exit *);
 };
 
+// Information about histogram of the loop from profiling
+
+struct histogram_counters{
+    gcov_type hist[69];
+    gcov_type sum;
+
+    // need to think about overflows
+    // quantil function for the distribution
+    // returns index under which is koef part of the distribution
+    int quantil(float koef){
+        gcc_assert(0<koef && koef<=1);
+        gcov_type quant=0;
+        int i=0;
+        for (;i<69;++i) {
+            if (quant+hist[i]<koef*sum) {
+                quant+=hist[i];
+            } else {
+                break;
+            }
+        }
+        return i;
+    };
+    // aproximate distribution mean value of the random variable to a power
+    float mean_value(int power){
+        gcov_type values=0;
+        for (int i=0;i<8;i++){
+            gcov_type val=1;
+            for (int j=1; j<=power;j++) {
+                val*=i;
+            }
+            values+=val*hist[i];
+        }
+        for (int i=8;i<69;i++){
+            gcov_type val=1;
+            for (int j=1; j<=power; j++) {
+                val*=1<<(i-5);
+            }
+            values+=val*hist[i];
+        }
+        return ((float)values)/sum;
+    };
+    // returns aproximate variance of the distribution
+    float variance(){
+        float one=mean_value(1);
+        return mean_value(2)-one*one;
+    };
+};
+
+
 typedef class loop *loop_p;
 
 /* An integer estimation of the number of iterations.  Estimate_state
@@ -275,8 +324,7 @@ public:
      reused.  */
   basic_block former_header;
 
-  // We store histogram values here
-  gcov_type hist[69];
+  histogram_counters* counters=NULL;
 };
 
 /* Set if the loop is known to be infinite.  */
diff --git a/gcc/profile.cc b/gcc/profile.cc
index 1ffc3e35210..675ad036e96 100644
--- a/gcc/profile.cc
+++ b/gcc/profile.cc
@@ -928,9 +928,13 @@ compute_value_histograms (histogram_values values, unsigned cfg_checksum,
       {
         auto lp = hist->hvalue.lp;
         if (act_count[t]){
+           lp->counters=(histogram_counters*) xcalloc (1, sizeof (histogram_counters));
+           gcov_type sum=0;
            for (int i=0;i<69;++i){
-               lp->hist[i]=act_count[t][i];
+               lp->counters->hist[i]=act_count[t][i];
+               sum+=act_count[t][i];
            }
+           lp->counters->sum=sum;
         }
         continue;
       }