From mboxrd@z Thu Jan  1 00:00:00 1970
Return-Path: <kubaneko@sourceware.org>
Received: by sourceware.org (Postfix, from userid 7880)
	id 5047B385C301; Thu, 16 Feb 2023 16:28:16 +0000 (GMT)
DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 5047B385C301
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org;
	s=default; t=1676564896;
	bh=H4dumZpfKUf0sexBYrrPmwu+k3HCaFCXbWmKzoFhzE0=;
	h=From:To:Subject:Date:From;
	b=ScpxOtUKv1QztyldE4f/jOFrY1OPR6PlrlLsu6a6Fn8dP9uxmPphJVnM909B5dgzX
	 Cx2hN0KEmQnQ4k6ztPWrLt3w4K/2rFgutUAK45uwWeZs6TPuS15FZ6EYUDBu2gduJg
	 n9fFt1iUNoYrAJXbFheBseV53Sx5sSpYe/a856VE=
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: d483867021b5a939c95a1e4da8ac322457ba800f
X-Git-Newrev: 22a55f0304297cb9579138efcb7985210f47304a
Message-Id: <20230216162816.5047B385C301@sourceware.org>
Date: Thu, 16 Feb 2023 16:28:16 +0000 (GMT)
List-Id: <gcc-cvs.sourceware.org>

https://gcc.gnu.org/g:22a55f0304297cb9579138efcb7985210f47304a

commit 22a55f0304297cb9579138efcb7985210f47304a
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 1fdcf2c35e0..6d5929b655a 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 a33d59177d0..8df82317c0f 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 02e292722fd..bb4eb7d1712 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;
       }