Mercurial > hg > CbC > CbC_gcc
comparison contrib/analyze_brprob.py @ 111:04ced10e8804
gcc 7
author | kono |
---|---|
date | Fri, 27 Oct 2017 22:46:09 +0900 |
parents | |
children | 84e7813d76e9 |
comparison
equal
deleted
inserted
replaced
68:561a7518be6b | 111:04ced10e8804 |
---|---|
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 | |
68 import argparse | |
69 | |
70 from math import * | |
71 | |
72 counter_aggregates = set(['combined', 'first match', 'DS theory', | |
73 'no prediction']) | |
74 | |
75 def percentage(a, b): | |
76 return 100.0 * a / b | |
77 | |
78 def average(values): | |
79 return 1.0 * sum(values) / len(values) | |
80 | |
81 def average_cutoff(values, cut): | |
82 l = len(values) | |
83 skip = floor(l * cut / 2) | |
84 if skip > 0: | |
85 values.sort() | |
86 values = values[skip:-skip] | |
87 return average(values) | |
88 | |
89 def median(values): | |
90 values.sort() | |
91 return values[int(len(values) / 2)] | |
92 | |
93 class PredictDefFile: | |
94 def __init__(self, path): | |
95 self.path = path | |
96 self.predictors = {} | |
97 | |
98 def parse_and_modify(self, heuristics, write_def_file): | |
99 lines = [x.rstrip() for x in open(self.path).readlines()] | |
100 | |
101 p = None | |
102 modified_lines = [] | |
103 for l in lines: | |
104 if l.startswith('DEF_PREDICTOR'): | |
105 m = re.match('.*"(.*)".*', l) | |
106 p = m.group(1) | |
107 elif l == '': | |
108 p = None | |
109 | |
110 if p != None: | |
111 heuristic = [x for x in heuristics if x.name == p] | |
112 heuristic = heuristic[0] if len(heuristic) == 1 else None | |
113 | |
114 m = re.match('.*HITRATE \(([^)]*)\).*', l) | |
115 if (m != None): | |
116 self.predictors[p] = int(m.group(1)) | |
117 | |
118 # modify the line | |
119 if heuristic != None: | |
120 new_line = (l[:m.start(1)] | |
121 + str(round(heuristic.get_hitrate())) | |
122 + l[m.end(1):]) | |
123 l = new_line | |
124 p = None | |
125 elif 'PROB_VERY_LIKELY' in l: | |
126 self.predictors[p] = 100 | |
127 modified_lines.append(l) | |
128 | |
129 # save the file | |
130 if write_def_file: | |
131 with open(self.path, 'w+') as f: | |
132 for l in modified_lines: | |
133 f.write(l + '\n') | |
134 | |
135 class Summary: | |
136 def __init__(self, name): | |
137 self.name = name | |
138 self.branches = 0 | |
139 self.successfull_branches = 0 | |
140 self.count = 0 | |
141 self.hits = 0 | |
142 self.fits = 0 | |
143 | |
144 def get_hitrate(self): | |
145 return 100.0 * self.hits / self.count | |
146 | |
147 def get_branch_hitrate(self): | |
148 return 100.0 * self.successfull_branches / self.branches | |
149 | |
150 def count_formatted(self): | |
151 v = self.count | |
152 for unit in ['','K','M','G','T','P','E','Z']: | |
153 if v < 1000: | |
154 return "%3.2f%s" % (v, unit) | |
155 v /= 1000.0 | |
156 return "%.1f%s" % (v, 'Y') | |
157 | |
158 def print(self, branches_max, count_max, predict_def): | |
159 predicted_as = None | |
160 if predict_def != None and self.name in predict_def.predictors: | |
161 predicted_as = predict_def.predictors[self.name] | |
162 | |
163 print('%-40s %8i %5.1f%% %11.2f%% %7.2f%% / %6.2f%% %14i %8s %5.1f%%' % | |
164 (self.name, self.branches, | |
165 percentage(self.branches, branches_max), | |
166 self.get_branch_hitrate(), | |
167 self.get_hitrate(), | |
168 percentage(self.fits, self.count), | |
169 self.count, self.count_formatted(), | |
170 percentage(self.count, count_max)), end = '') | |
171 | |
172 if predicted_as != None: | |
173 print('%12i%% %5.1f%%' % (predicted_as, | |
174 self.get_hitrate() - predicted_as), end = '') | |
175 print() | |
176 | |
177 class Profile: | |
178 def __init__(self, filename): | |
179 self.filename = filename | |
180 self.heuristics = {} | |
181 self.niter_vector = [] | |
182 | |
183 def add(self, name, prediction, count, hits): | |
184 if not name in self.heuristics: | |
185 self.heuristics[name] = Summary(name) | |
186 | |
187 s = self.heuristics[name] | |
188 s.branches += 1 | |
189 | |
190 s.count += count | |
191 if prediction < 50: | |
192 hits = count - hits | |
193 remaining = count - hits | |
194 if hits >= remaining: | |
195 s.successfull_branches += 1 | |
196 | |
197 s.hits += hits | |
198 s.fits += max(hits, remaining) | |
199 | |
200 def add_loop_niter(self, niter): | |
201 if niter > 0: | |
202 self.niter_vector.append(niter) | |
203 | |
204 def branches_max(self): | |
205 return max([v.branches for k, v in self.heuristics.items()]) | |
206 | |
207 def count_max(self): | |
208 return max([v.count for k, v in self.heuristics.items()]) | |
209 | |
210 def print_group(self, sorting, group_name, heuristics, predict_def): | |
211 count_max = self.count_max() | |
212 branches_max = self.branches_max() | |
213 | |
214 sorter = lambda x: x.branches | |
215 if sorting == 'branch-hitrate': | |
216 sorter = lambda x: x.get_branch_hitrate() | |
217 elif sorting == 'hitrate': | |
218 sorter = lambda x: x.get_hitrate() | |
219 elif sorting == 'coverage': | |
220 sorter = lambda x: x.count | |
221 elif sorting == 'name': | |
222 sorter = lambda x: x.name.lower() | |
223 | |
224 print('%-40s %8s %6s %12s %18s %14s %8s %6s %12s %6s' % | |
225 ('HEURISTICS', 'BRANCHES', '(REL)', | |
226 'BR. HITRATE', 'HITRATE', 'COVERAGE', 'COVERAGE', '(REL)', | |
227 'predict.def', '(REL)')) | |
228 for h in sorted(heuristics, key = sorter): | |
229 h.print(branches_max, count_max, predict_def) | |
230 | |
231 def dump(self, sorting): | |
232 heuristics = self.heuristics.values() | |
233 if len(heuristics) == 0: | |
234 print('No heuristics available') | |
235 return | |
236 | |
237 predict_def = None | |
238 if args.def_file != None: | |
239 predict_def = PredictDefFile(args.def_file) | |
240 predict_def.parse_and_modify(heuristics, args.write_def_file) | |
241 | |
242 special = list(filter(lambda x: x.name in counter_aggregates, | |
243 heuristics)) | |
244 normal = list(filter(lambda x: x.name not in counter_aggregates, | |
245 heuristics)) | |
246 | |
247 self.print_group(sorting, 'HEURISTICS', normal, predict_def) | |
248 print() | |
249 self.print_group(sorting, 'HEURISTIC AGGREGATES', special, predict_def) | |
250 | |
251 if len(self.niter_vector) > 0: | |
252 print ('\nLoop count: %d' % len(self.niter_vector)), | |
253 print(' avg. # of iter: %.2f' % average(self.niter_vector)) | |
254 print(' median # of iter: %.2f' % median(self.niter_vector)) | |
255 for v in [1, 5, 10, 20, 30]: | |
256 cut = 0.01 * v | |
257 print(' avg. (%d%% cutoff) # of iter: %.2f' | |
258 % (v, average_cutoff(self.niter_vector, cut))) | |
259 | |
260 parser = argparse.ArgumentParser() | |
261 parser.add_argument('dump_file', metavar = 'dump_file', | |
262 help = 'IPA profile dump file') | |
263 parser.add_argument('-s', '--sorting', dest = 'sorting', | |
264 choices = ['branches', 'branch-hitrate', 'hitrate', 'coverage', 'name'], | |
265 default = 'branches') | |
266 parser.add_argument('-d', '--def-file', help = 'path to predict.def') | |
267 parser.add_argument('-w', '--write-def-file', action = 'store_true', | |
268 help = 'Modify predict.def file in order to set new numbers') | |
269 | |
270 args = parser.parse_args() | |
271 | |
272 profile = Profile(args.dump_file) | |
273 r = re.compile(' (.*) heuristics( of edge [0-9]*->[0-9]*)?( \\(.*\\))?: (.*)%.*exec ([0-9]*) hit ([0-9]*)') | |
274 loop_niter_str = ';; profile-based iteration count: ' | |
275 for l in open(args.dump_file): | |
276 m = r.match(l) | |
277 if m != None and m.group(3) == None: | |
278 name = m.group(1) | |
279 prediction = float(m.group(4)) | |
280 count = int(m.group(5)) | |
281 hits = int(m.group(6)) | |
282 | |
283 profile.add(name, prediction, count, hits) | |
284 elif l.startswith(loop_niter_str): | |
285 v = int(l[len(loop_niter_str):]) | |
286 profile.add_loop_niter(v) | |
287 | |
288 profile.dump(args.sorting) |