> On 04/25/2016 09:01 PM, Matthias Klose wrote:
> > please could you make the shebang python3? Not sure if it's good to replace
> > one old implementation with a soon to become old implementation.
> >
> > Matthias
>
> Sure, thanks for pointing out.
>
> Attaching v2, where I changed:
> + switched from python2 to python3
> + added a new column with better readable coverage values:
>
> HEURISTICS BRANCHES (REL) HITRATE
> COVERAGE COVERAGE (REL)
> loop iv compare 70 0.1% 59.31% / 71.45%
> 391732444 391.73M 0.0%
> unconditional jump 252 0.2% 100.00% / 100.00%
> 62269 62.27K 0.0%
> guess loop iv compare 362 0.3% 89.02% / 90.08%
> 2703184164 2.70G 0.2%
> ...
>
> As I've just tested the patch, I runs significantly faster for SPEC2006
> profile dumps:
> real 0m1.162s vs. real 0m17.962s
Hehe, my awk-fu was not intended to be extremely effective ;)
The patch is OK. We could make it to respond to --help rather than
having explanation in comments, but I do not care much as long as it gets the
data.
Honza
>
> Martin
> >From 38ee7451629e5fe7d9d2468bf24e1929193be2a6 Mon Sep 17 00:00:00 2001
> From: marxin <mli...@suse.cz>
> Date: Mon, 25 Apr 2016 16:42:42 +0200
> Subject: [PATCH] Replace AWK script with the python script.
>
> contrib/ChangeLog:
>
> 2016-04-25 Martin Liska <mli...@suse.cz>
>
> * analyze_brprob: Remove.
> * analyze_brprob.py: New file.
> ---
> contrib/analyze_brprob | 147
> ----------------------------------------------
> contrib/analyze_brprob.py | 136 ++++++++++++++++++++++++++++++++++++++++++
> 2 files changed, 136 insertions(+), 147 deletions(-)
> delete mode 100755 contrib/analyze_brprob
> create mode 100755 contrib/analyze_brprob.py
>
> diff --git a/contrib/analyze_brprob b/contrib/analyze_brprob
> deleted file mode 100755
> index 5702834..0000000
> --- a/contrib/analyze_brprob
> +++ /dev/null
> @@ -1,147 +0,0 @@
> -#!/usr/bin/awk -f
> -# Script to analyze experimental results of our branch prediction heuristics
> -# Contributed by Jan Hubicka, SuSE Inc.
> -# Copyright (C) 2001, 2003 Free Software Foundation, Inc.
> -#
> -# This file is part of GCC.
> -#
> -# GCC is free software; you can redistribute it and/or modify
> -# it under the terms of the GNU General Public License as published by
> -# the Free Software Foundation; either version 3, or (at your option)
> -# any later version.
> -#
> -# GCC is distributed in the hope that it will be useful,
> -# but WITHOUT ANY WARRANTY; without even the implied warranty of
> -# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
> -# GNU General Public License for more details.
> -#
> -# You should have received a copy of the GNU General Public License
> -# along with GCC; see the file COPYING. If not, write to
> -# the Free Software Foundation, 51 Franklin Street, Fifth Floor,
> -# Boston, MA 02110-1301, USA.
> -#
> -#
> -# This script is used to calculate two basic properties of the branch
> prediction
> -# heuristics - coverage and hitrate. Coverage is number of executions of a
> given
> -# branch matched by the heuristics and hitrate is probability that once
> branch is
> -# predicted as taken it is really taken.
> -#
> -# These values are useful to determine the quality of given heuristics.
> Hitrate
> -# may be directly used in predict.c.
> -#
> -# Usage:
> -# Step 1: Compile and profile your program. You need to use -fprofile-arcs
> -# flag to get the profiles
> -# Step 2: Generate log files. The information about given heuristics are
> -# saved into ipa-profile dumps. You need to pass the -fdimp-ipa-profile
> switch
> -# to the compiler as well
> -# as -fbranch-probabilities to get the results of profiling noted in the
> dumps.
> -# Ensure that there are no "Arc profiling: some edge counts were bad."
> warnings.
> -# Step 3: Run this script to concatenate all *.profile files:
> -# analyze_brprob `find . -name *.profile`
> -# the information is collected and print once all files are parsed. This
> -# may take a while.
> -# Note that the script does use bc to perform long arithmetic.
> -# Step 4: Read the results. Basically the following table is printed:
> -# (this is just an example from a very early stage of branch prediction pass
> -# development, so please don't take these numbers seriously)
> -#
> -#HEURISTICS BRANCHES (REL) HITRATE COVERAGE
> (REL)
> -#opcode 2889 83.7% 94.96%/ 97.62% 7516383
> 75.3%
> -#pointer 246 7.1% 99.69%/ 99.86% 118791
> 1.2%
> -#loop header 449 13.0% 98.32%/ 99.07% 43553
> 0.4%
> -#first match 3450 100.0% 89.92%/ 97.27% 9979782
> 100.0%
> -#loop exit 924 26.8% 88.95%/ 95.58% 9026266
> 90.4%
> -#error return 150 4.3% 64.48%/ 86.81% 453542
> 4.5%
> -#call 803 23.3% 51.66%/ 98.61% 3614037
> 36.2%
> -#loop branch 51 1.5% 99.26%/ 99.27% 26854
> 0.3%
> -#noreturn call 951 27.6% 100.00%/100.00% 1759809
> 17.6%
> -#
> -# The heuristic called "first match" is a heuristic used by GCC branch
> -# prediction pass and it predicts 89.92% branches correctly.
> -#
> -# The quality of heuristics can be rated using both, coverage and hitrate
> -# parameters. For example "loop branch" heuristics (predicting loopback
> edge
> -# as taken) have both very high hitrate and coverage, so it is very useful.
> -# On the other hand, "exit block" heuristics (predicting exit edges as not
> -# taken) have good hitrate, but poor coverage, so only 3 branches have been
> -# predicted. The "loop header" heuristic has problems, since it tends to
> -# misspredict.
> -#
> -# The implementation of this script is somewhat brute force. My awk skills
> -# are limited.
> -
> -function longeval(e)
> -{
> - e = "echo \"scale = 2 ;"e"\" | bc"
> - e | getline res
> - close (e)
> - return res
> -}
> -
> -BEGIN {nnames = 0}
> -
> -/^ .* heuristics: .*.$/ {
> - name=$0
> - sub (/^ /,"",name)
> - sub (/ heuristics: .*.$/,"",name)
> - if (!(name in branches))
> - {
> - names[nnames] = name
> - branches[name]=0
> - counts[name]=0
> - hits[name]=0
> - phits[name]=0
> - nnames++
> - }
> - branches[name]+=1
> - }
> -
> -/^ .* heuristics: .*. exec [0-9]* hit [0-9]* (.*.)$/ {
> - name=$0
> - sub (/^ /,"",name)
> - sub (/ heuristics: .*. exec [0-9]* hit [0-9]* (.*.)$/,"",name)
> - pred=$0
> - sub (/^ .* heuristics: /,"",pred)
> - sub (/. exec [0-9]* hit [0-9]* (.*.)$/,"",pred)
> - count=$0
> - sub (/^ .* heuristics: .*. exec /,"",count)
> - sub (/ hit [0-9]* (.*.)$/,"",count)
> - hit=$0
> - sub (/^ .* heuristics: .*. exec [0-9]* hit /,"",hit)
> - sub (/ (.*.)$/,"",hit)
> -
> - if (int(pred) < 50.0)
> - {
> - hit = count"-"hit;
> - }
> - counts[name]=counts[name] "+" count
> - hits[name]=hits[name] "+" hit
> - phits[name]=phits[name]
> "+(("hit")<"count"/2)*("count"-("hit"))+(("hit")>="count"/2)*("hit")"
> -
> - #BC crashes on long strings. Irritating.
> - if (length(counts[name]) > 2000)
> - counts[name] = longeval(counts[name])
> - if (length(hits[name]) > 2000)
> - hits[name] = longeval(hits[name])
> - if (length(phits[name]) > 2000)
> - phits[name] = longeval(phits[name])
> - }
> -END {
> - # Heuristics called combined predicts just everything.
> - maxcounts = longeval(counts["combined"])
> - maxbranches = branches["combined"]
> - max = names["combined"]
> - printf("HEURISTICS BRANCHES (REL) HITRATE
> COVERAGE (REL)\n")
> - for (i = 0; i < nnames ; i++)
> - {
> - name = names[i]
> - counts[name] = longeval(counts[name])
> - printf ("%-26s %8i %5.1f%% %6s%% / %6s%% %12s %5.1f%%\n",
> - name,
> - branches[name], branches[name] * 100 / maxbranches,
> - longeval("("hits[name]") * 100 /(" counts[name]"-0.00001)"),
> - longeval("("phits[name]") * 100 /(" counts[name]"-0.00001)"),
> - counts[name], longeval(counts[name]" * 100 /
> ("maxcounts"-0.00001)"))
> - }
> -}
> diff --git a/contrib/analyze_brprob.py b/contrib/analyze_brprob.py
> new file mode 100755
> index 0000000..36371ff
> --- /dev/null
> +++ b/contrib/analyze_brprob.py
> @@ -0,0 +1,136 @@
> +#!/usr/bin/env python3
> +#
> +# Script to analyze results of our branch prediction heuristics
> +#
> +# This file is part of GCC.
> +#
> +# GCC is free software; you can redistribute it and/or modify it under
> +# the terms of the GNU General Public License as published by the Free
> +# Software Foundation; either version 3, or (at your option) any later
> +# version.
> +#
> +# GCC is distributed in the hope that it will be useful, but WITHOUT ANY
> +# WARRANTY; without even the implied warranty of MERCHANTABILITY or
> +# FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
> +# for more details.
> +#
> +# You should have received a copy of the GNU General Public License
> +# along with GCC; see the file COPYING3. If not see
> +# <http://www.gnu.org/licenses/>. */
> +#
> +#
> +#
> +# This script is used to calculate two basic properties of the branch
> prediction
> +# heuristics - coverage and hitrate. Coverage is number of executions
> +# of a given branch matched by the heuristics and hitrate is probability
> +# that once branch is predicted as taken it is really taken.
> +#
> +# These values are useful to determine the quality of given heuristics.
> +# Hitrate may be directly used in predict.def.
> +#
> +# Usage:
> +# Step 1: Compile and profile your program. You need to use
> -fprofile-generate
> +# flag to get the profiles.
> +# Step 2: Make a reference run of the intrumented application.
> +# Step 3: Compile the program with collected profile and dump IPA profiles
> +# (-fprofile-use -fdump-ipa-profile-details)
> +# Step 4: Collect all generated dump files:
> +# find . -name '*.profile' | xargs cat > dump_file
> +# Step 5: Run the script:
> +# ./analyze_brprob.py dump_file
> +# and read results. Basically the following table is printed:
> +#
> +# HEURISTICS BRANCHES (REL) HITRATE
> COVERAGE (REL)
> +# early return (on trees) 3 0.2% 35.83% / 93.64%
> 66360 0.0%
> +# guess loop iv compare 8 0.6% 53.35% / 53.73%
> 11183344 0.0%
> +# call 18 1.4% 31.95% / 69.95%
> 51880179 0.2%
> +# loop guard 23 1.8% 84.13% / 84.85%
> 13749065956 42.2%
> +# opcode values positive (on trees) 42 3.3% 15.71% / 84.81%
> 6771097902 20.8%
> +# opcode values nonequal (on trees) 226 17.6% 72.48% / 72.84%
> 844753864 2.6%
> +# loop exit 231 18.0% 86.97% / 86.98%
> 8952666897 27.5%
> +# loop iterations 239 18.6% 91.10% / 91.10%
> 3062707264 9.4%
> +# DS theory 281 21.9% 82.08% / 83.39%
> 7787264075 23.9%
> +# no prediction 293 22.9% 46.92% / 70.70%
> 2293267840 7.0%
> +# guessed loop iterations 313 24.4% 76.41% / 76.41%
> 10782750177 33.1%
> +# first match 708 55.2% 82.30% / 82.31%
> 22489588691 69.0%
> +# combined 1282 100.0% 79.76% / 81.75%
> 32570120606 100.0%
> +#
> +#
> +# The heuristics called "first match" is a heuristics used by GCC branch
> +# prediction pass and it predicts 55.2% branches correctly. As you can,
> +# the heuristics has very good covertage (69.05%). On the other hand,
> +# "opcode values nonequal (on trees)" heuristics has good hirate, but poor
> +# coverage.
> +
> +import sys
> +import os
> +import re
> +
> +def percentage(a, b):
> + return 100.0 * a / b
> +
> +class Summary:
> + def __init__(self, name):
> + self.name = name
> + self.branches = 0
> + self.count = 0
> + self.hits = 0
> + self.fits = 0
> +
> + def count_formatted(self):
> + v = self.count
> + for unit in ['','K','M','G','T','P','E','Z']:
> + if v < 1000:
> + return "%3.2f%s" % (v, unit)
> + v /= 1000.0
> + return "%.1f%s" % (v, 'Y')
> +
> +class Profile:
> + def __init__(self, filename):
> + self.filename = filename
> + self.heuristics = {}
> +
> + def add(self, name, prediction, count, hits):
> + if not name in self.heuristics:
> + self.heuristics[name] = Summary(name)
> +
> + s = self.heuristics[name]
> + s.branches += 1
> + s.count += count
> + if prediction < 50:
> + hits = count - hits
> + s.hits += hits
> + s.fits += max(hits, count - hits)
> +
> + def branches_max(self):
> + return max([v.branches for k, v in self.heuristics.items()])
> +
> + def count_max(self):
> + return max([v.count for k, v in self.heuristics.items()])
> +
> + def dump(self):
> + print('%-36s %8s %6s %-16s %14s %8s %6s' % ('HEURISTICS',
> 'BRANCHES', '(REL)',
> + 'HITRATE', 'COVERAGE', 'COVERAGE', '(REL)'))
> + for (k, v) in sorted(self.heuristics.items(), key = lambda x:
> x[1].branches):
> + print('%-36s %8i %5.1f%% %6.2f%% / %6.2f%% %14i %8s %5.1f%%' %
> + (k, v.branches, percentage(v.branches, self.branches_max ()),
> + percentage(v.hits, v.count), percentage(v.fits, v.count),
> + v.count, v.count_formatted(), percentage(v.count,
> self.count_max()) ))
> +
> +if len(sys.argv) != 2:
> + print('Usage: ./analyze_brprob.py dump_file')
> + exit(1)
> +
> +profile = Profile(sys.argv[1])
> +r = re.compile(' (.*) heuristics: (.*)%.*exec ([0-9]*) hit ([0-9]*)')
> +for l in open(profile.filename).readlines():
> + m = r.match(l)
> + if m != None:
> + name = m.group(1)
> + prediction = float(m.group(2))
> + count = int(m.group(3))
> + hits = int(m.group(4))
> +
> + profile.add(name, prediction, count, hits)
> +
> +profile.dump()
> --
> 2.8.1
>
