From mboxrd@z Thu Jan  1 00:00:00 1970
Return-Path: <kubaneko@sourceware.org>
Received: by sourceware.org (Postfix, from userid 7880)
	id 79FAC385B50D; Thu, 23 Feb 2023 23:22:07 +0000 (GMT)
DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 79FAC385B50D
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org;
	s=default; t=1677194527;
	bh=B8wCt2sEV9qsJceGm3wiFlKbOg0+bmizrf6rOkK0wl4=;
	h=From:To:Subject:Date:From;
	b=PklDzqT8VmyWoEzNa70tssFD3wMOkPPS7pui8AHlTmgrtTFJ4DJue2kqjH98TYdEQ
	 jH85/RwxoDnySeYWWr93WhTfloSHJ/jqUuH+IkQspt8zZhRbFEiHb8+7RHigo0jRcU
	 HcJ38CDSxwT61aN7P4nEdEsK84kNhDRbsDNYEyHs=
Content-Type: text/plain; charset="us-ascii"
MIME-Version: 1.0
Content-Transfer-Encoding: 7bit
From: Ondrej Kubanek <kubaneko@gcc.gnu.org>
To: gcc-cvs@gcc.gnu.org
Subject: [gcc(refs/users/kubaneko/heads/histogram)] added histogram_counters
 structure
X-Act-Checkin: gcc
X-Git-Author: kubaneko <kubanek0ondrej@gmail.com>
X-Git-Refname: refs/users/kubaneko/heads/histogram
X-Git-Oldrev: ef357765f596c358b223b7374f4a1574b7483a64
X-Git-Newrev: 1aa8abc66731f6256653ef54607eb0b759ce1467
Message-Id: <20230223232207.79FAC385B50D@sourceware.org>
Date: Thu, 23 Feb 2023 23:22:07 +0000 (GMT)
List-Id: <gcc-cvs.sourceware.org>

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;
       }