]>
Commit | Line | Data |
---|---|---|
4877829b | 1 | #!/usr/bin/env python3 |
81f86cb9 | 2 | |
83ffe9cd | 3 | # Copyright (C) 2016-2023 Free Software Foundation, Inc. |
4877829b ML |
4 | # |
5 | # Script to analyze results of our branch prediction heuristics | |
6 | # | |
7 | # This file is part of GCC. | |
8 | # | |
9 | # GCC is free software; you can redistribute it and/or modify it under | |
10 | # the terms of the GNU General Public License as published by the Free | |
11 | # Software Foundation; either version 3, or (at your option) any later | |
12 | # version. | |
13 | # | |
14 | # GCC is distributed in the hope that it will be useful, but WITHOUT ANY | |
15 | # WARRANTY; without even the implied warranty of MERCHANTABILITY or | |
16 | # FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License | |
17 | # for more details. | |
18 | # | |
19 | # You should have received a copy of the GNU General Public License | |
20 | # along with GCC; see the file COPYING3. If not see | |
21 | # <http://www.gnu.org/licenses/>. */ | |
22 | # | |
23 | # | |
24 | # | |
25 | # This script is used to calculate two basic properties of the branch prediction | |
26 | # heuristics - coverage and hitrate. Coverage is number of executions | |
27 | # of a given branch matched by the heuristics and hitrate is probability | |
28 | # that once branch is predicted as taken it is really taken. | |
29 | # | |
30 | # These values are useful to determine the quality of given heuristics. | |
31 | # Hitrate may be directly used in predict.def. | |
32 | # | |
33 | # Usage: | |
34 | # Step 1: Compile and profile your program. You need to use -fprofile-generate | |
35 | # flag to get the profiles. | |
36 | # Step 2: Make a reference run of the intrumented application. | |
37 | # Step 3: Compile the program with collected profile and dump IPA profiles | |
38 | # (-fprofile-use -fdump-ipa-profile-details) | |
39 | # Step 4: Collect all generated dump files: | |
40 | # find . -name '*.profile' | xargs cat > dump_file | |
41 | # Step 5: Run the script: | |
42 | # ./analyze_brprob.py dump_file | |
43 | # and read results. Basically the following table is printed: | |
44 | # | |
45 | # HEURISTICS BRANCHES (REL) HITRATE COVERAGE (REL) | |
46 | # early return (on trees) 3 0.2% 35.83% / 93.64% 66360 0.0% | |
47 | # guess loop iv compare 8 0.6% 53.35% / 53.73% 11183344 0.0% | |
48 | # call 18 1.4% 31.95% / 69.95% 51880179 0.2% | |
49 | # loop guard 23 1.8% 84.13% / 84.85% 13749065956 42.2% | |
50 | # opcode values positive (on trees) 42 3.3% 15.71% / 84.81% 6771097902 20.8% | |
51 | # opcode values nonequal (on trees) 226 17.6% 72.48% / 72.84% 844753864 2.6% | |
52 | # loop exit 231 18.0% 86.97% / 86.98% 8952666897 27.5% | |
53 | # loop iterations 239 18.6% 91.10% / 91.10% 3062707264 9.4% | |
54 | # DS theory 281 21.9% 82.08% / 83.39% 7787264075 23.9% | |
55 | # no prediction 293 22.9% 46.92% / 70.70% 2293267840 7.0% | |
56 | # guessed loop iterations 313 24.4% 76.41% / 76.41% 10782750177 33.1% | |
57 | # first match 708 55.2% 82.30% / 82.31% 22489588691 69.0% | |
58 | # combined 1282 100.0% 79.76% / 81.75% 32570120606 100.0% | |
59 | # | |
60 | # | |
61 | # The heuristics called "first match" is a heuristics used by GCC branch | |
62 | # prediction pass and it predicts 55.2% branches correctly. As you can, | |
63 | # the heuristics has very good covertage (69.05%). On the other hand, | |
64 | # "opcode values nonequal (on trees)" heuristics has good hirate, but poor | |
65 | # coverage. | |
66 | ||
67 | import sys | |
68 | import os | |
69 | import re | |
0d73e480 | 70 | import argparse |
4877829b | 71 | |
199b1891 ML |
72 | from math import * |
73 | ||
ca3b6071 ML |
74 | counter_aggregates = set(['combined', 'first match', 'DS theory', |
75 | 'no prediction']) | |
d1b9a572 | 76 | hot_threshold = 10 |
ca3b6071 | 77 | |
4877829b ML |
78 | def percentage(a, b): |
79 | return 100.0 * a / b | |
80 | ||
199b1891 ML |
81 | def average(values): |
82 | return 1.0 * sum(values) / len(values) | |
83 | ||
84 | def average_cutoff(values, cut): | |
85 | l = len(values) | |
86 | skip = floor(l * cut / 2) | |
87 | if skip > 0: | |
88 | values.sort() | |
89 | values = values[skip:-skip] | |
90 | return average(values) | |
91 | ||
92 | def median(values): | |
93 | values.sort() | |
94 | return values[int(len(values) / 2)] | |
95 | ||
59075bc8 ML |
96 | class PredictDefFile: |
97 | def __init__(self, path): | |
98 | self.path = path | |
99 | self.predictors = {} | |
100 | ||
101 | def parse_and_modify(self, heuristics, write_def_file): | |
102 | lines = [x.rstrip() for x in open(self.path).readlines()] | |
103 | ||
104 | p = None | |
105 | modified_lines = [] | |
31ab99f7 | 106 | for i, l in enumerate(lines): |
59075bc8 | 107 | if l.startswith('DEF_PREDICTOR'): |
31ab99f7 ML |
108 | next_line = lines[i + 1] |
109 | if l.endswith(','): | |
110 | l += next_line | |
59075bc8 ML |
111 | m = re.match('.*"(.*)".*', l) |
112 | p = m.group(1) | |
113 | elif l == '': | |
114 | p = None | |
115 | ||
116 | if p != None: | |
117 | heuristic = [x for x in heuristics if x.name == p] | |
118 | heuristic = heuristic[0] if len(heuristic) == 1 else None | |
119 | ||
120 | m = re.match('.*HITRATE \(([^)]*)\).*', l) | |
121 | if (m != None): | |
122 | self.predictors[p] = int(m.group(1)) | |
123 | ||
124 | # modify the line | |
125 | if heuristic != None: | |
126 | new_line = (l[:m.start(1)] | |
127 | + str(round(heuristic.get_hitrate())) | |
128 | + l[m.end(1):]) | |
129 | l = new_line | |
130 | p = None | |
131 | elif 'PROB_VERY_LIKELY' in l: | |
132 | self.predictors[p] = 100 | |
133 | modified_lines.append(l) | |
134 | ||
135 | # save the file | |
136 | if write_def_file: | |
137 | with open(self.path, 'w+') as f: | |
138 | for l in modified_lines: | |
139 | f.write(l + '\n') | |
d1b9a572 ML |
140 | class Heuristics: |
141 | def __init__(self, count, hits, fits): | |
142 | self.count = count | |
143 | self.hits = hits | |
144 | self.fits = fits | |
59075bc8 | 145 | |
4877829b ML |
146 | class Summary: |
147 | def __init__(self, name): | |
148 | self.name = name | |
d1b9a572 ML |
149 | self.edges= [] |
150 | ||
151 | def branches(self): | |
152 | return len(self.edges) | |
153 | ||
154 | def hits(self): | |
155 | return sum([x.hits for x in self.edges]) | |
156 | ||
157 | def fits(self): | |
158 | return sum([x.fits for x in self.edges]) | |
159 | ||
160 | def count(self): | |
161 | return sum([x.count for x in self.edges]) | |
162 | ||
163 | def successfull_branches(self): | |
164 | return len([x for x in self.edges if 2 * x.hits >= x.count]) | |
4877829b | 165 | |
0d73e480 | 166 | def get_hitrate(self): |
d1b9a572 | 167 | return 100.0 * self.hits() / self.count() |
ca3b6071 ML |
168 | |
169 | def get_branch_hitrate(self): | |
d1b9a572 | 170 | return 100.0 * self.successfull_branches() / self.branches() |
0d73e480 | 171 | |
4877829b | 172 | def count_formatted(self): |
d1b9a572 | 173 | v = self.count() |
caba2b36 | 174 | for unit in ['', 'k', 'M', 'G', 'T', 'P', 'E', 'Z', 'Y']: |
4877829b ML |
175 | if v < 1000: |
176 | return "%3.2f%s" % (v, unit) | |
177 | v /= 1000.0 | |
178 | return "%.1f%s" % (v, 'Y') | |
179 | ||
d1b9a572 ML |
180 | def count(self): |
181 | return sum([x.count for x in self.edges]) | |
182 | ||
59075bc8 | 183 | def print(self, branches_max, count_max, predict_def): |
d1b9a572 ML |
184 | # filter out most hot edges (if requested) |
185 | self.edges = sorted(self.edges, reverse = True, key = lambda x: x.count) | |
186 | if args.coverage_threshold != None: | |
187 | threshold = args.coverage_threshold * self.count() / 100 | |
188 | edges = [x for x in self.edges if x.count < threshold] | |
189 | if len(edges) != 0: | |
190 | self.edges = edges | |
191 | ||
59075bc8 ML |
192 | predicted_as = None |
193 | if predict_def != None and self.name in predict_def.predictors: | |
194 | predicted_as = predict_def.predictors[self.name] | |
195 | ||
ca3b6071 | 196 | print('%-40s %8i %5.1f%% %11.2f%% %7.2f%% / %6.2f%% %14i %8s %5.1f%%' % |
d1b9a572 ML |
197 | (self.name, self.branches(), |
198 | percentage(self.branches(), branches_max), | |
ca3b6071 ML |
199 | self.get_branch_hitrate(), |
200 | self.get_hitrate(), | |
d1b9a572 ML |
201 | percentage(self.fits(), self.count()), |
202 | self.count(), self.count_formatted(), | |
203 | percentage(self.count(), count_max)), end = '') | |
59075bc8 ML |
204 | |
205 | if predicted_as != None: | |
206 | print('%12i%% %5.1f%%' % (predicted_as, | |
207 | self.get_hitrate() - predicted_as), end = '') | |
d1b9a572 ML |
208 | else: |
209 | print(' ' * 20, end = '') | |
210 | ||
211 | # print details about the most important edges | |
212 | if args.coverage_threshold == None: | |
213 | edges = [x for x in self.edges[:100] if x.count * hot_threshold > self.count()] | |
214 | if args.verbose: | |
215 | for c in edges: | |
216 | r = 100.0 * c.count / self.count() | |
217 | print(' %.0f%%:%d' % (r, c.count), end = '') | |
218 | elif len(edges) > 0: | |
219 | print(' %0.0f%%:%d' % (100.0 * sum([x.count for x in edges]) / self.count(), len(edges)), end = '') | |
220 | ||
59075bc8 | 221 | print() |
ca3b6071 | 222 | |
4877829b ML |
223 | class Profile: |
224 | def __init__(self, filename): | |
225 | self.filename = filename | |
226 | self.heuristics = {} | |
199b1891 | 227 | self.niter_vector = [] |
4877829b ML |
228 | |
229 | def add(self, name, prediction, count, hits): | |
230 | if not name in self.heuristics: | |
231 | self.heuristics[name] = Summary(name) | |
232 | ||
233 | s = self.heuristics[name] | |
ca3b6071 | 234 | |
4877829b ML |
235 | if prediction < 50: |
236 | hits = count - hits | |
ca3b6071 | 237 | remaining = count - hits |
d1b9a572 | 238 | fits = max(hits, remaining) |
ca3b6071 | 239 | |
d1b9a572 | 240 | s.edges.append(Heuristics(count, hits, fits)) |
4877829b | 241 | |
199b1891 ML |
242 | def add_loop_niter(self, niter): |
243 | if niter > 0: | |
244 | self.niter_vector.append(niter) | |
245 | ||
4877829b | 246 | def branches_max(self): |
d1b9a572 | 247 | return max([v.branches() for k, v in self.heuristics.items()]) |
4877829b ML |
248 | |
249 | def count_max(self): | |
d1b9a572 | 250 | return max([v.count() for k, v in self.heuristics.items()]) |
4877829b | 251 | |
59075bc8 | 252 | def print_group(self, sorting, group_name, heuristics, predict_def): |
ca3b6071 ML |
253 | count_max = self.count_max() |
254 | branches_max = self.branches_max() | |
255 | ||
d1b9a572 | 256 | sorter = lambda x: x.branches() |
ca3b6071 ML |
257 | if sorting == 'branch-hitrate': |
258 | sorter = lambda x: x.get_branch_hitrate() | |
259 | elif sorting == 'hitrate': | |
260 | sorter = lambda x: x.get_hitrate() | |
0d73e480 | 261 | elif sorting == 'coverage': |
ca3b6071 ML |
262 | sorter = lambda x: x.count |
263 | elif sorting == 'name': | |
264 | sorter = lambda x: x.name.lower() | |
265 | ||
d1b9a572 | 266 | print('%-40s %8s %6s %12s %18s %14s %8s %6s %12s %6s %s' % |
ca3b6071 | 267 | ('HEURISTICS', 'BRANCHES', '(REL)', |
59075bc8 | 268 | 'BR. HITRATE', 'HITRATE', 'COVERAGE', 'COVERAGE', '(REL)', |
d1b9a572 | 269 | 'predict.def', '(REL)', 'HOT branches (>%d%%)' % hot_threshold)) |
ca3b6071 | 270 | for h in sorted(heuristics, key = sorter): |
59075bc8 | 271 | h.print(branches_max, count_max, predict_def) |
ca3b6071 ML |
272 | |
273 | def dump(self, sorting): | |
274 | heuristics = self.heuristics.values() | |
275 | if len(heuristics) == 0: | |
276 | print('No heuristics available') | |
277 | return | |
278 | ||
59075bc8 ML |
279 | predict_def = None |
280 | if args.def_file != None: | |
281 | predict_def = PredictDefFile(args.def_file) | |
282 | predict_def.parse_and_modify(heuristics, args.write_def_file) | |
283 | ||
ca3b6071 ML |
284 | special = list(filter(lambda x: x.name in counter_aggregates, |
285 | heuristics)) | |
286 | normal = list(filter(lambda x: x.name not in counter_aggregates, | |
287 | heuristics)) | |
0d73e480 | 288 | |
59075bc8 | 289 | self.print_group(sorting, 'HEURISTICS', normal, predict_def) |
ca3b6071 | 290 | print() |
59075bc8 | 291 | self.print_group(sorting, 'HEURISTIC AGGREGATES', special, predict_def) |
4877829b | 292 | |
88617fe4 ML |
293 | if len(self.niter_vector) > 0: |
294 | print ('\nLoop count: %d' % len(self.niter_vector)), | |
295 | print(' avg. # of iter: %.2f' % average(self.niter_vector)) | |
296 | print(' median # of iter: %.2f' % median(self.niter_vector)) | |
297 | for v in [1, 5, 10, 20, 30]: | |
298 | cut = 0.01 * v | |
ca3b6071 ML |
299 | print(' avg. (%d%% cutoff) # of iter: %.2f' |
300 | % (v, average_cutoff(self.niter_vector, cut))) | |
199b1891 | 301 | |
0d73e480 | 302 | parser = argparse.ArgumentParser() |
ca3b6071 ML |
303 | parser.add_argument('dump_file', metavar = 'dump_file', |
304 | help = 'IPA profile dump file') | |
305 | parser.add_argument('-s', '--sorting', dest = 'sorting', | |
306 | choices = ['branches', 'branch-hitrate', 'hitrate', 'coverage', 'name'], | |
307 | default = 'branches') | |
59075bc8 ML |
308 | parser.add_argument('-d', '--def-file', help = 'path to predict.def') |
309 | parser.add_argument('-w', '--write-def-file', action = 'store_true', | |
310 | help = 'Modify predict.def file in order to set new numbers') | |
d1b9a572 ML |
311 | parser.add_argument('-c', '--coverage-threshold', type = int, |
312 | help = 'Ignore edges that have percentage coverage >= coverage-threshold') | |
313 | parser.add_argument('-v', '--verbose', action = 'store_true', help = 'Print verbose informations') | |
0d73e480 ML |
314 | |
315 | args = parser.parse_args() | |
4877829b | 316 | |
59075bc8 | 317 | profile = Profile(args.dump_file) |
199b1891 | 318 | loop_niter_str = ';; profile-based iteration count: ' |
d1b9a572 | 319 | |
59075bc8 | 320 | for l in open(args.dump_file): |
d1b9a572 ML |
321 | if l.startswith(';;heuristics;'): |
322 | parts = l.strip().split(';') | |
323 | assert len(parts) == 8 | |
324 | name = parts[3] | |
325 | prediction = float(parts[6]) | |
326 | count = int(parts[4]) | |
327 | hits = int(parts[5]) | |
4877829b ML |
328 | |
329 | profile.add(name, prediction, count, hits) | |
199b1891 ML |
330 | elif l.startswith(loop_niter_str): |
331 | v = int(l[len(loop_niter_str):]) | |
332 | profile.add_loop_niter(v) | |
4877829b | 333 | |
0d73e480 | 334 | profile.dump(args.sorting) |