Re: [PATCH] Replace old AWK script (utilizing bc) with Python implementation

[Jan Hubicka <hubicka at ucw dot cz>]

> 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 <mliska@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  <mliska@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
>