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 <mli...@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 <mli...@suse.cz>
* analyze_brprob.py: Parse and display average number
of loop iterations.
gcc/ChangeLog:
2016-06-21 Martin Liska <mli...@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
