]>
Commit | Line | Data |
---|---|---|
4877829b ML |
1 | #!/usr/bin/env python3 |
2 | # | |
3 | # Script to analyze results of our branch prediction heuristics | |
4 | # | |
5 | # This file is part of GCC. | |
6 | # | |
7 | # GCC is free software; you can redistribute it and/or modify it under | |
8 | # the terms of the GNU General Public License as published by the Free | |
9 | # Software Foundation; either version 3, or (at your option) any later | |
10 | # version. | |
11 | # | |
12 | # GCC is distributed in the hope that it will be useful, but WITHOUT ANY | |
13 | # WARRANTY; without even the implied warranty of MERCHANTABILITY or | |
14 | # FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License | |
15 | # for more details. | |
16 | # | |
17 | # You should have received a copy of the GNU General Public License | |
18 | # along with GCC; see the file COPYING3. If not see | |
19 | # <http://www.gnu.org/licenses/>. */ | |
20 | # | |
21 | # | |
22 | # | |
23 | # This script is used to calculate two basic properties of the branch prediction | |
24 | # heuristics - coverage and hitrate. Coverage is number of executions | |
25 | # of a given branch matched by the heuristics and hitrate is probability | |
26 | # that once branch is predicted as taken it is really taken. | |
27 | # | |
28 | # These values are useful to determine the quality of given heuristics. | |
29 | # Hitrate may be directly used in predict.def. | |
30 | # | |
31 | # Usage: | |
32 | # Step 1: Compile and profile your program. You need to use -fprofile-generate | |
33 | # flag to get the profiles. | |
34 | # Step 2: Make a reference run of the intrumented application. | |
35 | # Step 3: Compile the program with collected profile and dump IPA profiles | |
36 | # (-fprofile-use -fdump-ipa-profile-details) | |
37 | # Step 4: Collect all generated dump files: | |
38 | # find . -name '*.profile' | xargs cat > dump_file | |
39 | # Step 5: Run the script: | |
40 | # ./analyze_brprob.py dump_file | |
41 | # and read results. Basically the following table is printed: | |
42 | # | |
43 | # HEURISTICS BRANCHES (REL) HITRATE COVERAGE (REL) | |
44 | # early return (on trees) 3 0.2% 35.83% / 93.64% 66360 0.0% | |
45 | # guess loop iv compare 8 0.6% 53.35% / 53.73% 11183344 0.0% | |
46 | # call 18 1.4% 31.95% / 69.95% 51880179 0.2% | |
47 | # loop guard 23 1.8% 84.13% / 84.85% 13749065956 42.2% | |
48 | # opcode values positive (on trees) 42 3.3% 15.71% / 84.81% 6771097902 20.8% | |
49 | # opcode values nonequal (on trees) 226 17.6% 72.48% / 72.84% 844753864 2.6% | |
50 | # loop exit 231 18.0% 86.97% / 86.98% 8952666897 27.5% | |
51 | # loop iterations 239 18.6% 91.10% / 91.10% 3062707264 9.4% | |
52 | # DS theory 281 21.9% 82.08% / 83.39% 7787264075 23.9% | |
53 | # no prediction 293 22.9% 46.92% / 70.70% 2293267840 7.0% | |
54 | # guessed loop iterations 313 24.4% 76.41% / 76.41% 10782750177 33.1% | |
55 | # first match 708 55.2% 82.30% / 82.31% 22489588691 69.0% | |
56 | # combined 1282 100.0% 79.76% / 81.75% 32570120606 100.0% | |
57 | # | |
58 | # | |
59 | # The heuristics called "first match" is a heuristics used by GCC branch | |
60 | # prediction pass and it predicts 55.2% branches correctly. As you can, | |
61 | # the heuristics has very good covertage (69.05%). On the other hand, | |
62 | # "opcode values nonequal (on trees)" heuristics has good hirate, but poor | |
63 | # coverage. | |
64 | ||
65 | import sys | |
66 | import os | |
67 | import re | |
0d73e480 | 68 | import argparse |
4877829b | 69 | |
199b1891 ML |
70 | from math import * |
71 | ||
4877829b ML |
72 | def percentage(a, b): |
73 | return 100.0 * a / b | |
74 | ||
199b1891 ML |
75 | def average(values): |
76 | return 1.0 * sum(values) / len(values) | |
77 | ||
78 | def average_cutoff(values, cut): | |
79 | l = len(values) | |
80 | skip = floor(l * cut / 2) | |
81 | if skip > 0: | |
82 | values.sort() | |
83 | values = values[skip:-skip] | |
84 | return average(values) | |
85 | ||
86 | def median(values): | |
87 | values.sort() | |
88 | return values[int(len(values) / 2)] | |
89 | ||
4877829b ML |
90 | class Summary: |
91 | def __init__(self, name): | |
92 | self.name = name | |
93 | self.branches = 0 | |
94 | self.count = 0 | |
95 | self.hits = 0 | |
96 | self.fits = 0 | |
97 | ||
0d73e480 ML |
98 | def get_hitrate(self): |
99 | return self.hits / self.count | |
100 | ||
4877829b ML |
101 | def count_formatted(self): |
102 | v = self.count | |
103 | for unit in ['','K','M','G','T','P','E','Z']: | |
104 | if v < 1000: | |
105 | return "%3.2f%s" % (v, unit) | |
106 | v /= 1000.0 | |
107 | return "%.1f%s" % (v, 'Y') | |
108 | ||
109 | class Profile: | |
110 | def __init__(self, filename): | |
111 | self.filename = filename | |
112 | self.heuristics = {} | |
199b1891 | 113 | self.niter_vector = [] |
4877829b ML |
114 | |
115 | def add(self, name, prediction, count, hits): | |
116 | if not name in self.heuristics: | |
117 | self.heuristics[name] = Summary(name) | |
118 | ||
119 | s = self.heuristics[name] | |
120 | s.branches += 1 | |
121 | s.count += count | |
122 | if prediction < 50: | |
123 | hits = count - hits | |
124 | s.hits += hits | |
125 | s.fits += max(hits, count - hits) | |
126 | ||
199b1891 ML |
127 | def add_loop_niter(self, niter): |
128 | if niter > 0: | |
129 | self.niter_vector.append(niter) | |
130 | ||
4877829b ML |
131 | def branches_max(self): |
132 | return max([v.branches for k, v in self.heuristics.items()]) | |
133 | ||
134 | def count_max(self): | |
135 | return max([v.count for k, v in self.heuristics.items()]) | |
136 | ||
0d73e480 ML |
137 | def dump(self, sorting): |
138 | sorter = lambda x: x[1].branches | |
139 | if sorting == 'hitrate': | |
140 | sorter = lambda x: x[1].get_hitrate() | |
141 | elif sorting == 'coverage': | |
142 | sorter = lambda x: x[1].count | |
143 | ||
69071d86 | 144 | print('%-40s %8s %6s %-16s %14s %8s %6s' % ('HEURISTICS', 'BRANCHES', '(REL)', |
4877829b | 145 | 'HITRATE', 'COVERAGE', 'COVERAGE', '(REL)')) |
0d73e480 | 146 | for (k, v) in sorted(self.heuristics.items(), key = sorter): |
69071d86 | 147 | print('%-40s %8i %5.1f%% %6.2f%% / %6.2f%% %14i %8s %5.1f%%' % |
4877829b ML |
148 | (k, v.branches, percentage(v.branches, self.branches_max ()), |
149 | percentage(v.hits, v.count), percentage(v.fits, v.count), | |
150 | v.count, v.count_formatted(), percentage(v.count, self.count_max()) )) | |
151 | ||
88617fe4 ML |
152 | if len(self.niter_vector) > 0: |
153 | print ('\nLoop count: %d' % len(self.niter_vector)), | |
154 | print(' avg. # of iter: %.2f' % average(self.niter_vector)) | |
155 | print(' median # of iter: %.2f' % median(self.niter_vector)) | |
156 | for v in [1, 5, 10, 20, 30]: | |
157 | cut = 0.01 * v | |
158 | print(' avg. (%d%% cutoff) # of iter: %.2f' % (v, average_cutoff(self.niter_vector, cut))) | |
199b1891 | 159 | |
0d73e480 ML |
160 | parser = argparse.ArgumentParser() |
161 | parser.add_argument('dump_file', metavar = 'dump_file', help = 'IPA profile dump file') | |
162 | parser.add_argument('-s', '--sorting', dest = 'sorting', choices = ['branches', 'hitrate', 'coverage'], default = 'branches') | |
163 | ||
164 | args = parser.parse_args() | |
4877829b ML |
165 | |
166 | profile = Profile(sys.argv[1]) | |
e49efc14 | 167 | r = re.compile(' (.*) heuristics( of edge [0-9]*->[0-9]*)?( \\(.*\\))?: (.*)%.*exec ([0-9]*) hit ([0-9]*)') |
199b1891 | 168 | loop_niter_str = ';; profile-based iteration count: ' |
0d73e480 | 169 | for l in open(args.dump_file).readlines(): |
4877829b | 170 | m = r.match(l) |
e49efc14 | 171 | if m != None and m.group(3) == None: |
4877829b | 172 | name = m.group(1) |
e49efc14 ML |
173 | prediction = float(m.group(4)) |
174 | count = int(m.group(5)) | |
175 | hits = int(m.group(6)) | |
4877829b ML |
176 | |
177 | profile.add(name, prediction, count, hits) | |
199b1891 ML |
178 | elif l.startswith(loop_niter_str): |
179 | v = int(l[len(loop_niter_str):]) | |
180 | profile.add_loop_niter(v) | |
4877829b | 181 | |
0d73e480 | 182 | profile.dump(args.sorting) |