[PATCH] Dump profile-based number of iterations

[Martin LiÅka <mliska at suse dot cz>]

Hello

Following patch dumps # of iterations for loops that iterates with unknown number
of iterations and profile is available. The same support is added to contrib/analyze_brprob.py
script.

Sample output of the script:

Loop count: 918
  avg. # of iter: 6.29
  median # of iter: 8.00
  avg. (1% cutoff) # of iter: 6.30
  avg. (5% cutoff) # of iter: 6.35
  avg. (10% cutoff) # of iter: 6.39
  avg. (20% cutoff) # of iter: 6.51
  avg. (30% cutoff) # of iter: 6.60

Patch can bootstrap and there's no regression spotted on x86_64-linux-gnu.
It's pre-approved by Honza.

Installed as r237762.

Martin

>From e1b17819ff31b671b6971b5f624958622d841848 Mon Sep 17 00:00:00 2001
From: marxin <mliska@suse.cz>
Date: Tue, 21 Jun 2016 17:48:14 +0200
Subject: [PATCH 3/4] Dump profile-based number of iterations

contrib/ChangeLog:

2016-06-21  Martin Liska  <mliska@suse.cz>

	* analyze_brprob.py: Parse and display average number
	of loop iterations.

gcc/ChangeLog:

2016-06-21  Martin Liska  <mliska@suse.cz>

	* cfgloop.c (flow_loop_dump): Dump average number of loop iterations.
	* cfgloop.h: Change 'struct loop' to 'const struct loop' for a
	few functions.
	* cfgloopanal.c (expected_loop_iterations_unbounded): Set a new
	argument to true if the expected number of iterations is
	loop-based.
---
 contrib/analyze_brprob.py | 33 +++++++++++++++++++++++++++++++++
 gcc/cfgloop.c             | 12 ++++++++++--
 gcc/cfgloop.h             |  7 ++++---
 gcc/cfgloopanal.c         | 11 +++++++++--
 4 files changed, 56 insertions(+), 7 deletions(-)

diff --git a/contrib/analyze_brprob.py b/contrib/analyze_brprob.py
index 2526623..c276d81 100755
--- a/contrib/analyze_brprob.py
+++ b/contrib/analyze_brprob.py
@@ -67,9 +67,26 @@ import os
 import re
 import argparse
 
+from math import *
+
 def percentage(a, b):
     return 100.0 * a / b
 
+def average(values):
+    return 1.0 * sum(values) / len(values)
+
+def average_cutoff(values, cut):
+    l = len(values)
+    skip = floor(l * cut / 2)
+    if skip > 0:
+        values.sort()
+        values = values[skip:-skip]
+    return average(values)
+
+def median(values):
+    values.sort()
+    return values[int(len(values) / 2)]
+
 class Summary:
     def __init__(self, name):
         self.name = name
@@ -93,6 +110,7 @@ class Profile:
     def __init__(self, filename):
         self.filename = filename
         self.heuristics = {}
+        self.niter_vector = []
 
     def add(self, name, prediction, count, hits):
         if not name in self.heuristics:
@@ -106,6 +124,10 @@ class Profile:
         s.hits += hits
         s.fits += max(hits, count - hits)
 
+    def add_loop_niter(self, niter):
+        if niter > 0:
+            self.niter_vector.append(niter)
+
     def branches_max(self):
         return max([v.branches for k, v in self.heuristics.items()])
 
@@ -127,6 +149,13 @@ class Profile:
              percentage(v.hits, v.count), percentage(v.fits, v.count),
              v.count, v.count_formatted(), percentage(v.count, self.count_max()) ))
 
+        print ('\nLoop count: %d' % len(self.niter_vector)),
+        print('  avg. # of iter: %.2f' % average(self.niter_vector))
+        print('  median # of iter: %.2f' % median(self.niter_vector))
+        for v in [1, 5, 10, 20, 30]:
+            cut = 0.01 * v
+            print('  avg. (%d%% cutoff) # of iter: %.2f' % (v, average_cutoff(self.niter_vector, cut)))
+
 parser = argparse.ArgumentParser()
 parser.add_argument('dump_file', metavar = 'dump_file', help = 'IPA profile dump file')
 parser.add_argument('-s', '--sorting', dest = 'sorting', choices = ['branches', 'hitrate', 'coverage'], default = 'branches')
@@ -135,6 +164,7 @@ args = parser.parse_args()
 
 profile = Profile(sys.argv[1])
 r = re.compile('  (.*) heuristics( of edge [0-9]*->[0-9]*)?( \\(.*\\))?: (.*)%.*exec ([0-9]*) hit ([0-9]*)')
+loop_niter_str = ';;  profile-based iteration count: '
 for l in open(args.dump_file).readlines():
     m = r.match(l)
     if m != None and m.group(3) == None:
@@ -144,5 +174,8 @@ for l in open(args.dump_file).readlines():
         hits = int(m.group(6))
 
         profile.add(name, prediction, count, hits)
+    elif l.startswith(loop_niter_str):
+        v = int(l[len(loop_niter_str):])
+        profile.add_loop_niter(v)
 
 profile.dump(args.sorting)
diff --git a/gcc/cfgloop.c b/gcc/cfgloop.c
index 5650f0d..e6174bd 100644
--- a/gcc/cfgloop.c
+++ b/gcc/cfgloop.c
@@ -136,6 +136,14 @@ flow_loop_dump (const struct loop *loop, FILE *file,
 	   loop_depth (loop), (long) (loop_outer (loop)
 				      ? loop_outer (loop)->num : -1));
 
+  if (loop->latch)
+    {
+      bool read_profile_p;
+      gcov_type nit = expected_loop_iterations_unbounded (loop, &read_profile_p);
+      if (read_profile_p && !loop->any_estimate)
+	fprintf (file, ";;  profile-based iteration count: %lu\n", nit);
+    }
+
   fprintf (file, ";;  nodes:");
   bbs = get_loop_body (loop);
   for (i = 0; i < loop->num_nodes; i++)
@@ -1913,7 +1921,7 @@ get_estimated_loop_iterations (struct loop *loop, widest_int *nit)
    false, otherwise returns true.  */
 
 bool
-get_max_loop_iterations (struct loop *loop, widest_int *nit)
+get_max_loop_iterations (const struct loop *loop, widest_int *nit)
 {
   if (!loop->any_upper_bound)
     return false;
@@ -1927,7 +1935,7 @@ get_max_loop_iterations (struct loop *loop, widest_int *nit)
    on the number of iterations of LOOP could not be derived, returns -1.  */
 
 HOST_WIDE_INT
-get_max_loop_iterations_int (struct loop *loop)
+get_max_loop_iterations_int (const struct loop *loop)
 {
   widest_int nit;
   HOST_WIDE_INT hwi_nit;
diff --git a/gcc/cfgloop.h b/gcc/cfgloop.h
index aba2988..dfc7525 100644
--- a/gcc/cfgloop.h
+++ b/gcc/cfgloop.h
@@ -319,7 +319,8 @@ extern void verify_loop_structure (void);
 
 /* Loop analysis.  */
 extern bool just_once_each_iteration_p (const struct loop *, const_basic_block);
-gcov_type expected_loop_iterations_unbounded (struct loop *);
+gcov_type expected_loop_iterations_unbounded (const struct loop *,
+					      bool *read_profile_p = NULL);
 extern unsigned expected_loop_iterations (struct loop *);
 extern rtx doloop_condition_get (rtx);
 
@@ -778,10 +779,10 @@ loop_outermost (struct loop *loop)
 
 extern void record_niter_bound (struct loop *, const widest_int &, bool, bool);
 extern HOST_WIDE_INT get_estimated_loop_iterations_int (struct loop *);
-extern HOST_WIDE_INT get_max_loop_iterations_int (struct loop *);
+extern HOST_WIDE_INT get_max_loop_iterations_int (const struct loop *);
 extern HOST_WIDE_INT get_likely_max_loop_iterations_int (struct loop *);
 extern bool get_estimated_loop_iterations (struct loop *loop, widest_int *nit);
-extern bool get_max_loop_iterations (struct loop *loop, widest_int *nit);
+extern bool get_max_loop_iterations (const struct loop *loop, widest_int *nit);
 extern bool get_likely_max_loop_iterations (struct loop *loop, widest_int *nit);
 extern int bb_loop_depth (const_basic_block);
 
diff --git a/gcc/cfgloopanal.c b/gcc/cfgloopanal.c
index 67c661f..2739f44 100644
--- a/gcc/cfgloopanal.c
+++ b/gcc/cfgloopanal.c
@@ -231,12 +231,15 @@ average_num_loop_insns (const struct loop *loop)
    value.  */
 
 gcov_type
-expected_loop_iterations_unbounded (struct loop *loop)
+expected_loop_iterations_unbounded (const struct loop *loop,
+				    bool *read_profile_p)
 {
   edge e;
   edge_iterator ei;
   gcov_type expected;
   
+  if (read_profile_p)
+    *read_profile_p = false;
 
   /* If we have no profile at all, use AVG_LOOP_NITER.  */
   if (profile_status_for_fn (cfun) == PROFILE_ABSENT)
@@ -257,7 +260,11 @@ expected_loop_iterations_unbounded (struct loop *loop)
       if (count_in == 0)
 	expected = count_latch * 2;
       else
-	expected = (count_latch + count_in - 1) / count_in;
+	{
+	  expected = (count_latch + count_in - 1) / count_in;
+	  if (read_profile_p)
+	    *read_profile_p = true;
+	}
     }
   else
     {
-- 
2.8.4