Mercurial > hg > CbC > CbC_gcc
annotate gcc/profile.c @ 120:f93fa5091070
fix conv1.c
author | mir3636 |
---|---|
date | Thu, 08 Mar 2018 14:53:42 +0900 |
parents | 04ced10e8804 |
children | 84e7813d76e9 |
rev | line source |
---|---|
0 | 1 /* Calculate branch probabilities, and basic block execution counts. |
111 | 2 Copyright (C) 1990-2017 Free Software Foundation, Inc. |
0 | 3 Contributed by James E. Wilson, UC Berkeley/Cygnus Support; |
4 based on some ideas from Dain Samples of UC Berkeley. | |
5 Further mangling by Bob Manson, Cygnus Support. | |
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 /* Generate basic block profile instrumentation and auxiliary files. | |
24 Profile generation is optimized, so that not all arcs in the basic | |
25 block graph need instrumenting. First, the BB graph is closed with | |
26 one entry (function start), and one exit (function exit). Any | |
27 ABNORMAL_EDGE cannot be instrumented (because there is no control | |
28 path to place the code). We close the graph by inserting fake | |
29 EDGE_FAKE edges to the EXIT_BLOCK, from the sources of abnormal | |
30 edges that do not go to the exit_block. We ignore such abnormal | |
31 edges. Naturally these fake edges are never directly traversed, | |
32 and so *cannot* be directly instrumented. Some other graph | |
33 massaging is done. To optimize the instrumentation we generate the | |
34 BB minimal span tree, only edges that are not on the span tree | |
35 (plus the entry point) need instrumenting. From that information | |
36 all other edge counts can be deduced. By construction all fake | |
37 edges must be on the spanning tree. We also attempt to place | |
38 EDGE_CRITICAL edges on the spanning tree. | |
39 | |
40 The auxiliary files generated are <dumpbase>.gcno (at compile time) | |
41 and <dumpbase>.gcda (at run time). The format is | |
42 described in full in gcov-io.h. */ | |
43 | |
44 /* ??? Register allocation should use basic block execution counts to | |
45 give preference to the most commonly executed blocks. */ | |
46 | |
47 /* ??? Should calculate branch probabilities before instrumenting code, since | |
48 then we can use arc counts to help decide which arcs to instrument. */ | |
49 | |
50 #include "config.h" | |
51 #include "system.h" | |
52 #include "coretypes.h" | |
111 | 53 #include "backend.h" |
0 | 54 #include "rtl.h" |
111 | 55 #include "tree.h" |
56 #include "gimple.h" | |
57 #include "cfghooks.h" | |
58 #include "cgraph.h" | |
59 #include "coverage.h" | |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
60 #include "diagnostic-core.h" |
111 | 61 #include "cfganal.h" |
0 | 62 #include "value-prof.h" |
111 | 63 #include "gimple-iterator.h" |
64 #include "tree-cfg.h" | |
65 #include "dumpfile.h" | |
0 | 66 #include "cfgloop.h" |
67 | |
68 #include "profile.h" | |
69 | |
111 | 70 /* Map from BBs/edges to gcov counters. */ |
71 vec<gcov_type> bb_gcov_counts; | |
72 hash_map<edge,gcov_type> *edge_gcov_counts; | |
73 | |
74 struct bb_profile_info { | |
0 | 75 unsigned int count_valid : 1; |
76 | |
77 /* Number of successor and predecessor edges. */ | |
78 gcov_type succ_count; | |
79 gcov_type pred_count; | |
80 }; | |
81 | |
111 | 82 #define BB_INFO(b) ((struct bb_profile_info *) (b)->aux) |
0 | 83 |
84 | |
85 /* Counter summary from the last set of coverage counts read. */ | |
86 | |
87 const struct gcov_ctr_summary *profile_info; | |
88 | |
111 | 89 /* Counter working set information computed from the current counter |
90 summary. Not initialized unless profile_info summary is non-NULL. */ | |
91 static gcov_working_set_t gcov_working_sets[NUM_GCOV_WORKING_SETS]; | |
92 | |
0 | 93 /* Collect statistics on the performance of this pass for the entire source |
94 file. */ | |
95 | |
96 static int total_num_blocks; | |
97 static int total_num_edges; | |
98 static int total_num_edges_ignored; | |
99 static int total_num_edges_instrumented; | |
100 static int total_num_blocks_created; | |
101 static int total_num_passes; | |
102 static int total_num_times_called; | |
103 static int total_hist_br_prob[20]; | |
104 static int total_num_branches; | |
105 | |
111 | 106 /* Helper function to update gcov_working_sets. */ |
107 | |
108 void add_working_set (gcov_working_set_t *set) { | |
109 int i = 0; | |
110 for (; i < NUM_GCOV_WORKING_SETS; i++) | |
111 gcov_working_sets[i] = set[i]; | |
112 } | |
113 | |
0 | 114 /* Forward declarations. */ |
115 static void find_spanning_tree (struct edge_list *); | |
116 | |
117 /* Add edge instrumentation code to the entire insn chain. | |
118 | |
119 F is the first insn of the chain. | |
120 NUM_BLOCKS is the number of basic blocks found in F. */ | |
121 | |
122 static unsigned | |
123 instrument_edges (struct edge_list *el) | |
124 { | |
125 unsigned num_instr_edges = 0; | |
126 int num_edges = NUM_EDGES (el); | |
127 basic_block bb; | |
128 | |
111 | 129 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun), NULL, next_bb) |
0 | 130 { |
131 edge e; | |
132 edge_iterator ei; | |
133 | |
134 FOR_EACH_EDGE (e, ei, bb->succs) | |
135 { | |
111 | 136 struct edge_profile_info *inf = EDGE_INFO (e); |
0 | 137 |
138 if (!inf->ignore && !inf->on_tree) | |
139 { | |
140 gcc_assert (!(e->flags & EDGE_ABNORMAL)); | |
141 if (dump_file) | |
142 fprintf (dump_file, "Edge %d to %d instrumented%s\n", | |
143 e->src->index, e->dest->index, | |
144 EDGE_CRITICAL_P (e) ? " (and split)" : ""); | |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
145 gimple_gen_edge_profiler (num_instr_edges++, e); |
0 | 146 } |
147 } | |
148 } | |
149 | |
150 total_num_blocks_created += num_edges; | |
151 if (dump_file) | |
152 fprintf (dump_file, "%d edges instrumented\n", num_instr_edges); | |
153 return num_instr_edges; | |
154 } | |
155 | |
156 /* Add code to measure histograms for values in list VALUES. */ | |
157 static void | |
158 instrument_values (histogram_values values) | |
159 { | |
111 | 160 unsigned i; |
0 | 161 |
162 /* Emit code to generate the histograms before the insns. */ | |
163 | |
111 | 164 for (i = 0; i < values.length (); i++) |
0 | 165 { |
111 | 166 histogram_value hist = values[i]; |
167 unsigned t = COUNTER_FOR_HIST_TYPE (hist->type); | |
0 | 168 |
169 if (!coverage_counter_alloc (t, hist->n_counters)) | |
170 continue; | |
171 | |
172 switch (hist->type) | |
173 { | |
174 case HIST_TYPE_INTERVAL: | |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
175 gimple_gen_interval_profiler (hist, t, 0); |
0 | 176 break; |
177 | |
178 case HIST_TYPE_POW2: | |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
179 gimple_gen_pow2_profiler (hist, t, 0); |
0 | 180 break; |
181 | |
182 case HIST_TYPE_SINGLE_VALUE: | |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
183 gimple_gen_one_value_profiler (hist, t, 0); |
0 | 184 break; |
185 | |
186 case HIST_TYPE_INDIR_CALL: | |
111 | 187 case HIST_TYPE_INDIR_CALL_TOPN: |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
188 gimple_gen_ic_profiler (hist, t, 0); |
0 | 189 break; |
190 | |
191 case HIST_TYPE_AVERAGE: | |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
192 gimple_gen_average_profiler (hist, t, 0); |
0 | 193 break; |
194 | |
195 case HIST_TYPE_IOR: | |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
196 gimple_gen_ior_profiler (hist, t, 0); |
0 | 197 break; |
198 | |
111 | 199 case HIST_TYPE_TIME_PROFILE: |
200 gimple_gen_time_profiler (t, 0); | |
201 break; | |
202 | |
0 | 203 default: |
204 gcc_unreachable (); | |
205 } | |
206 } | |
207 } | |
208 | |
209 | |
111 | 210 /* Fill the working set information into the profile_info structure. */ |
211 | |
212 void | |
213 get_working_sets (void) | |
214 { | |
215 unsigned ws_ix, pctinc, pct; | |
216 gcov_working_set_t *ws_info; | |
217 | |
218 if (!profile_info) | |
219 return; | |
220 | |
221 compute_working_sets (profile_info, gcov_working_sets); | |
222 | |
223 if (dump_file) | |
224 { | |
225 fprintf (dump_file, "Counter working sets:\n"); | |
226 /* Multiply the percentage by 100 to avoid float. */ | |
227 pctinc = 100 * 100 / NUM_GCOV_WORKING_SETS; | |
228 for (ws_ix = 0, pct = pctinc; ws_ix < NUM_GCOV_WORKING_SETS; | |
229 ws_ix++, pct += pctinc) | |
230 { | |
231 if (ws_ix == NUM_GCOV_WORKING_SETS - 1) | |
232 pct = 9990; | |
233 ws_info = &gcov_working_sets[ws_ix]; | |
234 /* Print out the percentage using int arithmatic to avoid float. */ | |
235 fprintf (dump_file, "\t\t%u.%02u%%: num counts=%u, min counter=" | |
236 "%" PRId64 "\n", | |
237 pct / 100, pct - (pct / 100 * 100), | |
238 ws_info->num_counters, | |
239 (int64_t)ws_info->min_counter); | |
240 } | |
241 } | |
242 } | |
243 | |
244 /* Given a the desired percentage of the full profile (sum_all from the | |
245 summary), multiplied by 10 to avoid float in PCT_TIMES_10, returns | |
246 the corresponding working set information. If an exact match for | |
247 the percentage isn't found, the closest value is used. */ | |
248 | |
249 gcov_working_set_t * | |
250 find_working_set (unsigned pct_times_10) | |
251 { | |
252 unsigned i; | |
253 if (!profile_info) | |
254 return NULL; | |
255 gcc_assert (pct_times_10 <= 1000); | |
256 if (pct_times_10 >= 999) | |
257 return &gcov_working_sets[NUM_GCOV_WORKING_SETS - 1]; | |
258 i = pct_times_10 * NUM_GCOV_WORKING_SETS / 1000; | |
259 if (!i) | |
260 return &gcov_working_sets[0]; | |
261 return &gcov_working_sets[i - 1]; | |
262 } | |
263 | |
264 /* Computes hybrid profile for all matching entries in da_file. | |
265 | |
266 CFG_CHECKSUM is the precomputed checksum for the CFG. */ | |
0 | 267 |
268 static gcov_type * | |
111 | 269 get_exec_counts (unsigned cfg_checksum, unsigned lineno_checksum) |
0 | 270 { |
271 unsigned num_edges = 0; | |
272 basic_block bb; | |
273 gcov_type *counts; | |
274 | |
275 /* Count the edges to be (possibly) instrumented. */ | |
111 | 276 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun), NULL, next_bb) |
0 | 277 { |
278 edge e; | |
279 edge_iterator ei; | |
280 | |
281 FOR_EACH_EDGE (e, ei, bb->succs) | |
282 if (!EDGE_INFO (e)->ignore && !EDGE_INFO (e)->on_tree) | |
283 num_edges++; | |
284 } | |
285 | |
111 | 286 counts = get_coverage_counts (GCOV_COUNTER_ARCS, num_edges, cfg_checksum, |
287 lineno_checksum, &profile_info); | |
0 | 288 if (!counts) |
289 return NULL; | |
290 | |
111 | 291 get_working_sets (); |
292 | |
0 | 293 if (dump_file && profile_info) |
111 | 294 fprintf (dump_file, "Merged %u profiles with maximal count %u.\n", |
295 profile_info->runs, (unsigned) profile_info->sum_max); | |
0 | 296 |
297 return counts; | |
298 } | |
299 | |
300 | |
301 static bool | |
111 | 302 is_edge_inconsistent (vec<edge, va_gc> *edges) |
0 | 303 { |
304 edge e; | |
305 edge_iterator ei; | |
306 FOR_EACH_EDGE (e, ei, edges) | |
307 { | |
308 if (!EDGE_INFO (e)->ignore) | |
309 { | |
111 | 310 if (edge_gcov_count (e) < 0 |
0 | 311 && (!(e->flags & EDGE_FAKE) |
312 || !block_ends_with_call_p (e->src))) | |
313 { | |
314 if (dump_file) | |
315 { | |
316 fprintf (dump_file, | |
111 | 317 "Edge %i->%i is inconsistent, count%" PRId64, |
318 e->src->index, e->dest->index, edge_gcov_count (e)); | |
319 dump_bb (dump_file, e->src, 0, TDF_DETAILS); | |
320 dump_bb (dump_file, e->dest, 0, TDF_DETAILS); | |
0 | 321 } |
322 return true; | |
323 } | |
324 } | |
325 } | |
326 return false; | |
327 } | |
328 | |
329 static void | |
330 correct_negative_edge_counts (void) | |
331 { | |
332 basic_block bb; | |
333 edge e; | |
334 edge_iterator ei; | |
335 | |
111 | 336 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun), NULL, next_bb) |
0 | 337 { |
338 FOR_EACH_EDGE (e, ei, bb->succs) | |
339 { | |
111 | 340 if (edge_gcov_count (e) < 0) |
341 edge_gcov_count (e) = 0; | |
0 | 342 } |
343 } | |
344 } | |
345 | |
346 /* Check consistency. | |
347 Return true if inconsistency is found. */ | |
348 static bool | |
349 is_inconsistent (void) | |
350 { | |
351 basic_block bb; | |
352 bool inconsistent = false; | |
111 | 353 FOR_EACH_BB_FN (bb, cfun) |
0 | 354 { |
355 inconsistent |= is_edge_inconsistent (bb->preds); | |
356 if (!dump_file && inconsistent) | |
357 return true; | |
358 inconsistent |= is_edge_inconsistent (bb->succs); | |
359 if (!dump_file && inconsistent) | |
360 return true; | |
111 | 361 if (bb_gcov_count (bb) < 0) |
0 | 362 { |
363 if (dump_file) | |
364 { | |
365 fprintf (dump_file, "BB %i count is negative " | |
111 | 366 "%" PRId64, |
0 | 367 bb->index, |
111 | 368 bb_gcov_count (bb)); |
369 dump_bb (dump_file, bb, 0, TDF_DETAILS); | |
0 | 370 } |
371 inconsistent = true; | |
372 } | |
111 | 373 if (bb_gcov_count (bb) != sum_edge_counts (bb->preds)) |
0 | 374 { |
375 if (dump_file) | |
376 { | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
377 fprintf (dump_file, "BB %i count does not match sum of incoming edges " |
111 | 378 "%" PRId64" should be %" PRId64, |
0 | 379 bb->index, |
111 | 380 bb_gcov_count (bb), |
0 | 381 sum_edge_counts (bb->preds)); |
111 | 382 dump_bb (dump_file, bb, 0, TDF_DETAILS); |
0 | 383 } |
384 inconsistent = true; | |
385 } | |
111 | 386 if (bb_gcov_count (bb) != sum_edge_counts (bb->succs) && |
387 ! (find_edge (bb, EXIT_BLOCK_PTR_FOR_FN (cfun)) != NULL | |
388 && block_ends_with_call_p (bb))) | |
0 | 389 { |
390 if (dump_file) | |
391 { | |
392 fprintf (dump_file, "BB %i count does not match sum of outgoing edges " | |
111 | 393 "%" PRId64" should be %" PRId64, |
0 | 394 bb->index, |
111 | 395 bb_gcov_count (bb), |
0 | 396 sum_edge_counts (bb->succs)); |
111 | 397 dump_bb (dump_file, bb, 0, TDF_DETAILS); |
0 | 398 } |
399 inconsistent = true; | |
400 } | |
401 if (!dump_file && inconsistent) | |
402 return true; | |
403 } | |
404 | |
405 return inconsistent; | |
406 } | |
407 | |
408 /* Set each basic block count to the sum of its outgoing edge counts */ | |
409 static void | |
410 set_bb_counts (void) | |
411 { | |
412 basic_block bb; | |
111 | 413 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun), NULL, next_bb) |
0 | 414 { |
111 | 415 bb_gcov_count (bb) = sum_edge_counts (bb->succs); |
416 gcc_assert (bb_gcov_count (bb) >= 0); | |
0 | 417 } |
418 } | |
419 | |
420 /* Reads profile data and returns total number of edge counts read */ | |
421 static int | |
422 read_profile_edge_counts (gcov_type *exec_counts) | |
423 { | |
424 basic_block bb; | |
425 int num_edges = 0; | |
426 int exec_counts_pos = 0; | |
427 /* For each edge not on the spanning tree, set its execution count from | |
428 the .da file. */ | |
429 /* The first count in the .da file is the number of times that the function | |
430 was entered. This is the exec_count for block zero. */ | |
431 | |
111 | 432 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun), NULL, next_bb) |
0 | 433 { |
434 edge e; | |
435 edge_iterator ei; | |
436 | |
437 FOR_EACH_EDGE (e, ei, bb->succs) | |
438 if (!EDGE_INFO (e)->ignore && !EDGE_INFO (e)->on_tree) | |
439 { | |
440 num_edges++; | |
441 if (exec_counts) | |
442 { | |
111 | 443 edge_gcov_count (e) = exec_counts[exec_counts_pos++]; |
444 if (edge_gcov_count (e) > profile_info->sum_max) | |
0 | 445 { |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
446 if (flag_profile_correction) |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
447 { |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
448 static bool informed = 0; |
111 | 449 if (dump_enabled_p () && !informed) |
450 dump_printf_loc (MSG_NOTE, input_location, | |
451 "corrupted profile info: edge count" | |
452 " exceeds maximal count\n"); | |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
453 informed = 1; |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
454 } |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
455 else |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
456 error ("corrupted profile info: edge from %i to %i exceeds maximal count", |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
457 bb->index, e->dest->index); |
0 | 458 } |
459 } | |
460 else | |
111 | 461 edge_gcov_count (e) = 0; |
0 | 462 |
463 EDGE_INFO (e)->count_valid = 1; | |
464 BB_INFO (bb)->succ_count--; | |
465 BB_INFO (e->dest)->pred_count--; | |
466 if (dump_file) | |
467 { | |
468 fprintf (dump_file, "\nRead edge from %i to %i, count:", | |
469 bb->index, e->dest->index); | |
111 | 470 fprintf (dump_file, "%" PRId64, |
471 (int64_t) edge_gcov_count (e)); | |
0 | 472 } |
473 } | |
474 } | |
475 | |
476 return num_edges; | |
477 } | |
478 | |
111 | 479 #define OVERLAP_BASE 10000 |
480 | |
481 /* Compare the static estimated profile to the actual profile, and | |
482 return the "degree of overlap" measure between them. | |
483 | |
484 Degree of overlap is a number between 0 and OVERLAP_BASE. It is | |
485 the sum of each basic block's minimum relative weights between | |
486 two profiles. And overlap of OVERLAP_BASE means two profiles are | |
487 identical. */ | |
488 | |
489 static int | |
490 compute_frequency_overlap (void) | |
491 { | |
492 gcov_type count_total = 0, freq_total = 0; | |
493 int overlap = 0; | |
494 basic_block bb; | |
495 | |
496 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun), NULL, next_bb) | |
497 { | |
498 count_total += bb_gcov_count (bb); | |
499 freq_total += bb->frequency; | |
500 } | |
501 | |
502 if (count_total == 0 || freq_total == 0) | |
503 return 0; | |
504 | |
505 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun), NULL, next_bb) | |
506 overlap += MIN (bb_gcov_count (bb) * OVERLAP_BASE / count_total, | |
507 bb->frequency * OVERLAP_BASE / freq_total); | |
508 | |
509 return overlap; | |
510 } | |
511 | |
0 | 512 /* Compute the branch probabilities for the various branches. |
111 | 513 Annotate them accordingly. |
514 | |
515 CFG_CHECKSUM is the precomputed checksum for the CFG. */ | |
0 | 516 |
517 static void | |
111 | 518 compute_branch_probabilities (unsigned cfg_checksum, unsigned lineno_checksum) |
0 | 519 { |
520 basic_block bb; | |
521 int i; | |
522 int num_edges = 0; | |
523 int changes; | |
524 int passes; | |
525 int hist_br_prob[20]; | |
526 int num_branches; | |
111 | 527 gcov_type *exec_counts = get_exec_counts (cfg_checksum, lineno_checksum); |
0 | 528 int inconsistent = 0; |
529 | |
530 /* Very simple sanity checks so we catch bugs in our profiling code. */ | |
531 if (!profile_info) | |
532 return; | |
111 | 533 |
534 bb_gcov_counts.safe_grow_cleared (last_basic_block_for_fn (cfun)); | |
535 edge_gcov_counts = new hash_map<edge,gcov_type>; | |
0 | 536 |
537 if (profile_info->sum_all < profile_info->sum_max) | |
538 { | |
539 error ("corrupted profile info: sum_all is smaller than sum_max"); | |
540 exec_counts = NULL; | |
541 } | |
542 | |
543 /* Attach extra info block to each bb. */ | |
111 | 544 alloc_aux_for_blocks (sizeof (struct bb_profile_info)); |
545 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun), NULL, next_bb) | |
0 | 546 { |
547 edge e; | |
548 edge_iterator ei; | |
549 | |
550 FOR_EACH_EDGE (e, ei, bb->succs) | |
551 if (!EDGE_INFO (e)->ignore) | |
552 BB_INFO (bb)->succ_count++; | |
553 FOR_EACH_EDGE (e, ei, bb->preds) | |
554 if (!EDGE_INFO (e)->ignore) | |
555 BB_INFO (bb)->pred_count++; | |
556 } | |
557 | |
558 /* Avoid predicting entry on exit nodes. */ | |
111 | 559 BB_INFO (EXIT_BLOCK_PTR_FOR_FN (cfun))->succ_count = 2; |
560 BB_INFO (ENTRY_BLOCK_PTR_FOR_FN (cfun))->pred_count = 2; | |
0 | 561 |
562 num_edges = read_profile_edge_counts (exec_counts); | |
563 | |
564 if (dump_file) | |
565 fprintf (dump_file, "\n%d edge counts read\n", num_edges); | |
566 | |
567 /* For every block in the file, | |
568 - if every exit/entrance edge has a known count, then set the block count | |
569 - if the block count is known, and every exit/entrance edge but one has | |
570 a known execution count, then set the count of the remaining edge | |
571 | |
572 As edge counts are set, decrement the succ/pred count, but don't delete | |
573 the edge, that way we can easily tell when all edges are known, or only | |
574 one edge is unknown. */ | |
575 | |
576 /* The order that the basic blocks are iterated through is important. | |
577 Since the code that finds spanning trees starts with block 0, low numbered | |
578 edges are put on the spanning tree in preference to high numbered edges. | |
579 Hence, most instrumented edges are at the end. Graph solving works much | |
580 faster if we propagate numbers from the end to the start. | |
581 | |
582 This takes an average of slightly more than 3 passes. */ | |
583 | |
584 changes = 1; | |
585 passes = 0; | |
586 while (changes) | |
587 { | |
588 passes++; | |
589 changes = 0; | |
111 | 590 FOR_BB_BETWEEN (bb, EXIT_BLOCK_PTR_FOR_FN (cfun), NULL, prev_bb) |
0 | 591 { |
111 | 592 struct bb_profile_info *bi = BB_INFO (bb); |
0 | 593 if (! bi->count_valid) |
594 { | |
595 if (bi->succ_count == 0) | |
596 { | |
597 edge e; | |
598 edge_iterator ei; | |
599 gcov_type total = 0; | |
600 | |
601 FOR_EACH_EDGE (e, ei, bb->succs) | |
111 | 602 total += edge_gcov_count (e); |
603 bb_gcov_count (bb) = total; | |
0 | 604 bi->count_valid = 1; |
605 changes = 1; | |
606 } | |
607 else if (bi->pred_count == 0) | |
608 { | |
609 edge e; | |
610 edge_iterator ei; | |
611 gcov_type total = 0; | |
612 | |
613 FOR_EACH_EDGE (e, ei, bb->preds) | |
111 | 614 total += edge_gcov_count (e); |
615 bb_gcov_count (bb) = total; | |
0 | 616 bi->count_valid = 1; |
617 changes = 1; | |
618 } | |
619 } | |
620 if (bi->count_valid) | |
621 { | |
622 if (bi->succ_count == 1) | |
623 { | |
624 edge e; | |
625 edge_iterator ei; | |
626 gcov_type total = 0; | |
627 | |
628 /* One of the counts will be invalid, but it is zero, | |
629 so adding it in also doesn't hurt. */ | |
630 FOR_EACH_EDGE (e, ei, bb->succs) | |
111 | 631 total += edge_gcov_count (e); |
0 | 632 |
633 /* Search for the invalid edge, and set its count. */ | |
634 FOR_EACH_EDGE (e, ei, bb->succs) | |
635 if (! EDGE_INFO (e)->count_valid && ! EDGE_INFO (e)->ignore) | |
636 break; | |
637 | |
638 /* Calculate count for remaining edge by conservation. */ | |
111 | 639 total = bb_gcov_count (bb) - total; |
0 | 640 |
641 gcc_assert (e); | |
642 EDGE_INFO (e)->count_valid = 1; | |
111 | 643 edge_gcov_count (e) = total; |
0 | 644 bi->succ_count--; |
645 | |
646 BB_INFO (e->dest)->pred_count--; | |
647 changes = 1; | |
648 } | |
649 if (bi->pred_count == 1) | |
650 { | |
651 edge e; | |
652 edge_iterator ei; | |
653 gcov_type total = 0; | |
654 | |
655 /* One of the counts will be invalid, but it is zero, | |
656 so adding it in also doesn't hurt. */ | |
657 FOR_EACH_EDGE (e, ei, bb->preds) | |
111 | 658 total += edge_gcov_count (e); |
0 | 659 |
660 /* Search for the invalid edge, and set its count. */ | |
661 FOR_EACH_EDGE (e, ei, bb->preds) | |
662 if (!EDGE_INFO (e)->count_valid && !EDGE_INFO (e)->ignore) | |
663 break; | |
664 | |
665 /* Calculate count for remaining edge by conservation. */ | |
111 | 666 total = bb_gcov_count (bb) - total + edge_gcov_count (e); |
0 | 667 |
668 gcc_assert (e); | |
669 EDGE_INFO (e)->count_valid = 1; | |
111 | 670 edge_gcov_count (e) = total; |
0 | 671 bi->pred_count--; |
672 | |
673 BB_INFO (e->src)->succ_count--; | |
674 changes = 1; | |
675 } | |
676 } | |
677 } | |
678 } | |
679 if (dump_file) | |
111 | 680 { |
681 int overlap = compute_frequency_overlap (); | |
682 gimple_dump_cfg (dump_file, dump_flags); | |
683 fprintf (dump_file, "Static profile overlap: %d.%d%%\n", | |
684 overlap / (OVERLAP_BASE / 100), | |
685 overlap % (OVERLAP_BASE / 100)); | |
686 } | |
0 | 687 |
688 total_num_passes += passes; | |
689 if (dump_file) | |
690 fprintf (dump_file, "Graph solving took %d passes.\n\n", passes); | |
691 | |
692 /* If the graph has been correctly solved, every block will have a | |
693 succ and pred count of zero. */ | |
111 | 694 FOR_EACH_BB_FN (bb, cfun) |
0 | 695 { |
696 gcc_assert (!BB_INFO (bb)->succ_count && !BB_INFO (bb)->pred_count); | |
697 } | |
698 | |
699 /* Check for inconsistent basic block counts */ | |
700 inconsistent = is_inconsistent (); | |
701 | |
702 if (inconsistent) | |
703 { | |
704 if (flag_profile_correction) | |
705 { | |
706 /* Inconsistency detected. Make it flow-consistent. */ | |
707 static int informed = 0; | |
111 | 708 if (dump_enabled_p () && informed == 0) |
0 | 709 { |
710 informed = 1; | |
111 | 711 dump_printf_loc (MSG_NOTE, input_location, |
712 "correcting inconsistent profile data\n"); | |
0 | 713 } |
714 correct_negative_edge_counts (); | |
715 /* Set bb counts to the sum of the outgoing edge counts */ | |
716 set_bb_counts (); | |
717 if (dump_file) | |
718 fprintf (dump_file, "\nCalling mcf_smooth_cfg\n"); | |
719 mcf_smooth_cfg (); | |
720 } | |
721 else | |
722 error ("corrupted profile info: profile data is not flow-consistent"); | |
723 } | |
724 | |
725 /* For every edge, calculate its branch probability and add a reg_note | |
726 to the branch insn to indicate this. */ | |
727 | |
728 for (i = 0; i < 20; i++) | |
729 hist_br_prob[i] = 0; | |
730 num_branches = 0; | |
731 | |
111 | 732 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun), NULL, next_bb) |
0 | 733 { |
734 edge e; | |
735 edge_iterator ei; | |
736 | |
111 | 737 if (bb_gcov_count (bb) < 0) |
0 | 738 { |
739 error ("corrupted profile info: number of iterations for basic block %d thought to be %i", | |
111 | 740 bb->index, (int)bb_gcov_count (bb)); |
741 bb_gcov_count (bb) = 0; | |
0 | 742 } |
743 FOR_EACH_EDGE (e, ei, bb->succs) | |
744 { | |
745 /* Function may return twice in the cased the called function is | |
746 setjmp or calls fork, but we can't represent this by extra | |
747 edge from the entry, since extra edge from the exit is | |
748 already present. We get negative frequency from the entry | |
749 point. */ | |
111 | 750 if ((edge_gcov_count (e) < 0 |
751 && e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun)) | |
752 || (edge_gcov_count (e) > bb_gcov_count (bb) | |
753 && e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun))) | |
0 | 754 { |
755 if (block_ends_with_call_p (bb)) | |
111 | 756 edge_gcov_count (e) = edge_gcov_count (e) < 0 |
757 ? 0 : bb_gcov_count (bb); | |
0 | 758 } |
111 | 759 if (edge_gcov_count (e) < 0 |
760 || edge_gcov_count (e) > bb_gcov_count (bb)) | |
0 | 761 { |
762 error ("corrupted profile info: number of executions for edge %d-%d thought to be %i", | |
763 e->src->index, e->dest->index, | |
111 | 764 (int)edge_gcov_count (e)); |
765 edge_gcov_count (e) = bb_gcov_count (bb) / 2; | |
0 | 766 } |
767 } | |
111 | 768 if (bb_gcov_count (bb)) |
0 | 769 { |
770 FOR_EACH_EDGE (e, ei, bb->succs) | |
111 | 771 e->probability = profile_probability::probability_in_gcov_type |
772 (edge_gcov_count (e), bb_gcov_count (bb)); | |
0 | 773 if (bb->index >= NUM_FIXED_BLOCKS |
774 && block_ends_with_condjump_p (bb) | |
775 && EDGE_COUNT (bb->succs) >= 2) | |
776 { | |
777 int prob; | |
778 edge e; | |
779 int index; | |
780 | |
781 /* Find the branch edge. It is possible that we do have fake | |
782 edges here. */ | |
783 FOR_EACH_EDGE (e, ei, bb->succs) | |
784 if (!(e->flags & (EDGE_FAKE | EDGE_FALLTHRU))) | |
785 break; | |
786 | |
111 | 787 prob = e->probability.to_reg_br_prob_base (); |
0 | 788 index = prob * 20 / REG_BR_PROB_BASE; |
789 | |
790 if (index == 20) | |
791 index = 19; | |
792 hist_br_prob[index]++; | |
793 | |
794 num_branches++; | |
795 } | |
796 } | |
797 /* As a last resort, distribute the probabilities evenly. | |
798 Use simple heuristics that if there are normal edges, | |
799 give all abnormals frequency of 0, otherwise distribute the | |
800 frequency over abnormals (this is the case of noreturn | |
801 calls). */ | |
111 | 802 else if (profile_status_for_fn (cfun) == PROFILE_ABSENT) |
0 | 803 { |
804 int total = 0; | |
805 | |
806 FOR_EACH_EDGE (e, ei, bb->succs) | |
807 if (!(e->flags & (EDGE_COMPLEX | EDGE_FAKE))) | |
808 total ++; | |
809 if (total) | |
810 { | |
811 FOR_EACH_EDGE (e, ei, bb->succs) | |
812 if (!(e->flags & (EDGE_COMPLEX | EDGE_FAKE))) | |
111 | 813 e->probability |
814 = profile_probability::guessed_always ().apply_scale (1, total); | |
0 | 815 else |
111 | 816 e->probability = profile_probability::never (); |
0 | 817 } |
818 else | |
819 { | |
820 total += EDGE_COUNT (bb->succs); | |
821 FOR_EACH_EDGE (e, ei, bb->succs) | |
111 | 822 e->probability |
823 = profile_probability::guessed_always ().apply_scale (1, total); | |
0 | 824 } |
825 if (bb->index >= NUM_FIXED_BLOCKS | |
826 && block_ends_with_condjump_p (bb) | |
827 && EDGE_COUNT (bb->succs) >= 2) | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
828 num_branches++; |
0 | 829 } |
830 } | |
111 | 831 |
832 FOR_ALL_BB_FN (bb, cfun) | |
833 { | |
834 bb->count = profile_count::from_gcov_type (bb_gcov_count (bb)); | |
835 } | |
836 bb_gcov_counts.release (); | |
837 delete edge_gcov_counts; | |
838 edge_gcov_counts = NULL; | |
839 | |
0 | 840 counts_to_freqs (); |
841 | |
842 if (dump_file) | |
843 { | |
844 fprintf (dump_file, "%d branches\n", num_branches); | |
845 if (num_branches) | |
846 for (i = 0; i < 10; i++) | |
847 fprintf (dump_file, "%d%% branches in range %d-%d%%\n", | |
848 (hist_br_prob[i] + hist_br_prob[19-i]) * 100 / num_branches, | |
849 5 * i, 5 * i + 5); | |
850 | |
851 total_num_branches += num_branches; | |
852 for (i = 0; i < 20; i++) | |
853 total_hist_br_prob[i] += hist_br_prob[i]; | |
854 | |
855 fputc ('\n', dump_file); | |
856 fputc ('\n', dump_file); | |
857 } | |
858 | |
859 free_aux_for_blocks (); | |
860 } | |
861 | |
862 /* Load value histograms values whose description is stored in VALUES array | |
111 | 863 from .gcda file. |
864 | |
865 CFG_CHECKSUM is the precomputed checksum for the CFG. */ | |
0 | 866 |
867 static void | |
111 | 868 compute_value_histograms (histogram_values values, unsigned cfg_checksum, |
869 unsigned lineno_checksum) | |
0 | 870 { |
871 unsigned i, j, t, any; | |
872 unsigned n_histogram_counters[GCOV_N_VALUE_COUNTERS]; | |
873 gcov_type *histogram_counts[GCOV_N_VALUE_COUNTERS]; | |
874 gcov_type *act_count[GCOV_N_VALUE_COUNTERS]; | |
875 gcov_type *aact_count; | |
111 | 876 struct cgraph_node *node; |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
877 |
0 | 878 for (t = 0; t < GCOV_N_VALUE_COUNTERS; t++) |
879 n_histogram_counters[t] = 0; | |
880 | |
111 | 881 for (i = 0; i < values.length (); i++) |
0 | 882 { |
111 | 883 histogram_value hist = values[i]; |
0 | 884 n_histogram_counters[(int) hist->type] += hist->n_counters; |
885 } | |
886 | |
887 any = 0; | |
888 for (t = 0; t < GCOV_N_VALUE_COUNTERS; t++) | |
889 { | |
890 if (!n_histogram_counters[t]) | |
891 { | |
892 histogram_counts[t] = NULL; | |
893 continue; | |
894 } | |
895 | |
896 histogram_counts[t] = | |
897 get_coverage_counts (COUNTER_FOR_HIST_TYPE (t), | |
111 | 898 n_histogram_counters[t], cfg_checksum, |
899 lineno_checksum, NULL); | |
0 | 900 if (histogram_counts[t]) |
901 any = 1; | |
902 act_count[t] = histogram_counts[t]; | |
903 } | |
904 if (!any) | |
905 return; | |
906 | |
111 | 907 for (i = 0; i < values.length (); i++) |
0 | 908 { |
111 | 909 histogram_value hist = values[i]; |
910 gimple *stmt = hist->hvalue.stmt; | |
0 | 911 |
912 t = (int) hist->type; | |
913 | |
914 aact_count = act_count[t]; | |
111 | 915 |
916 if (act_count[t]) | |
917 act_count[t] += hist->n_counters; | |
0 | 918 |
919 gimple_add_histogram_value (cfun, stmt, hist); | |
920 hist->hvalue.counters = XNEWVEC (gcov_type, hist->n_counters); | |
921 for (j = 0; j < hist->n_counters; j++) | |
111 | 922 if (aact_count) |
923 hist->hvalue.counters[j] = aact_count[j]; | |
924 else | |
925 hist->hvalue.counters[j] = 0; | |
926 | |
927 /* Time profiler counter is not related to any statement, | |
928 so that we have to read the counter and set the value to | |
929 the corresponding call graph node. */ | |
930 if (hist->type == HIST_TYPE_TIME_PROFILE) | |
931 { | |
932 node = cgraph_node::get (hist->fun->decl); | |
933 node->tp_first_run = hist->hvalue.counters[0]; | |
934 | |
935 if (dump_file) | |
936 fprintf (dump_file, "Read tp_first_run: %d\n", node->tp_first_run); | |
937 } | |
0 | 938 } |
939 | |
940 for (t = 0; t < GCOV_N_VALUE_COUNTERS; t++) | |
111 | 941 free (histogram_counts[t]); |
0 | 942 } |
943 | |
944 /* When passed NULL as file_name, initialize. | |
945 When passed something else, output the necessary commands to change | |
946 line to LINE and offset to FILE_NAME. */ | |
947 static void | |
948 output_location (char const *file_name, int line, | |
949 gcov_position_t *offset, basic_block bb) | |
950 { | |
951 static char const *prev_file_name; | |
952 static int prev_line; | |
953 bool name_differs, line_differs; | |
954 | |
955 if (!file_name) | |
956 { | |
957 prev_file_name = NULL; | |
958 prev_line = -1; | |
959 return; | |
960 } | |
961 | |
111 | 962 name_differs = !prev_file_name || filename_cmp (file_name, prev_file_name); |
0 | 963 line_differs = prev_line != line; |
964 | |
111 | 965 if (!*offset) |
0 | 966 { |
111 | 967 *offset = gcov_write_tag (GCOV_TAG_LINES); |
968 gcov_write_unsigned (bb->index); | |
969 name_differs = line_differs = true; | |
970 } | |
0 | 971 |
111 | 972 /* If this is a new source file, then output the |
973 file's name to the .bb file. */ | |
974 if (name_differs) | |
975 { | |
976 prev_file_name = file_name; | |
977 gcov_write_unsigned (0); | |
978 gcov_write_filename (prev_file_name); | |
979 } | |
980 if (line_differs) | |
981 { | |
982 gcov_write_unsigned (line); | |
983 prev_line = line; | |
984 } | |
0 | 985 } |
986 | |
111 | 987 /* Helper for qsort so edges get sorted from highest frequency to smallest. |
988 This controls the weight for minimal spanning tree algorithm */ | |
989 static int | |
990 compare_freqs (const void *p1, const void *p2) | |
991 { | |
992 const_edge e1 = *(const const_edge *)p1; | |
993 const_edge e2 = *(const const_edge *)p2; | |
994 | |
995 /* Critical edges needs to be split which introduce extra control flow. | |
996 Make them more heavy. */ | |
997 int m1 = EDGE_CRITICAL_P (e1) ? 2 : 1; | |
998 int m2 = EDGE_CRITICAL_P (e2) ? 2 : 1; | |
999 | |
1000 if (EDGE_FREQUENCY (e1) * m1 + m1 != EDGE_FREQUENCY (e2) * m2 + m2) | |
1001 return EDGE_FREQUENCY (e2) * m2 + m2 - EDGE_FREQUENCY (e1) * m1 - m1; | |
1002 /* Stabilize sort. */ | |
1003 if (e1->src->index != e2->src->index) | |
1004 return e2->src->index - e1->src->index; | |
1005 return e2->dest->index - e1->dest->index; | |
1006 } | |
1007 | |
1008 /* Instrument and/or analyze program behavior based on program the CFG. | |
1009 | |
1010 This function creates a representation of the control flow graph (of | |
1011 the function being compiled) that is suitable for the instrumentation | |
1012 of edges and/or converting measured edge counts to counts on the | |
1013 complete CFG. | |
0 | 1014 |
1015 When FLAG_PROFILE_ARCS is nonzero, this function instruments the edges in | |
1016 the flow graph that are needed to reconstruct the dynamic behavior of the | |
111 | 1017 flow graph. This data is written to the gcno file for gcov. |
0 | 1018 |
1019 When FLAG_BRANCH_PROBABILITIES is nonzero, this function reads auxiliary | |
111 | 1020 information from the gcda file containing edge count information from |
1021 previous executions of the function being compiled. In this case, the | |
1022 control flow graph is annotated with actual execution counts by | |
1023 compute_branch_probabilities(). | |
0 | 1024 |
1025 Main entry point of this file. */ | |
1026 | |
1027 void | |
1028 branch_prob (void) | |
1029 { | |
1030 basic_block bb; | |
1031 unsigned i; | |
1032 unsigned num_edges, ignored_edges; | |
1033 unsigned num_instrumented; | |
1034 struct edge_list *el; | |
111 | 1035 histogram_values values = histogram_values (); |
1036 unsigned cfg_checksum, lineno_checksum; | |
0 | 1037 |
1038 total_num_times_called++; | |
1039 | |
1040 flow_call_edges_add (NULL); | |
1041 add_noreturn_fake_exit_edges (); | |
1042 | |
1043 /* We can't handle cyclic regions constructed using abnormal edges. | |
1044 To avoid these we replace every source of abnormal edge by a fake | |
1045 edge from entry node and every destination by fake edge to exit. | |
1046 This keeps graph acyclic and our calculation exact for all normal | |
1047 edges except for exit and entrance ones. | |
1048 | |
1049 We also add fake exit edges for each call and asm statement in the | |
1050 basic, since it may not return. */ | |
1051 | |
111 | 1052 FOR_EACH_BB_FN (bb, cfun) |
0 | 1053 { |
1054 int need_exit_edge = 0, need_entry_edge = 0; | |
1055 int have_exit_edge = 0, have_entry_edge = 0; | |
1056 edge e; | |
1057 edge_iterator ei; | |
1058 | |
1059 /* Functions returning multiple times are not handled by extra edges. | |
1060 Instead we simply allow negative counts on edges from exit to the | |
1061 block past call and corresponding probabilities. We can't go | |
1062 with the extra edges because that would result in flowgraph that | |
1063 needs to have fake edges outside the spanning tree. */ | |
1064 | |
1065 FOR_EACH_EDGE (e, ei, bb->succs) | |
1066 { | |
1067 gimple_stmt_iterator gsi; | |
111 | 1068 gimple *last = NULL; |
0 | 1069 |
1070 /* It may happen that there are compiler generated statements | |
1071 without a locus at all. Go through the basic block from the | |
1072 last to the first statement looking for a locus. */ | |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
1073 for (gsi = gsi_last_nondebug_bb (bb); |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
1074 !gsi_end_p (gsi); |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
1075 gsi_prev_nondebug (&gsi)) |
0 | 1076 { |
1077 last = gsi_stmt (gsi); | |
111 | 1078 if (!RESERVED_LOCATION_P (gimple_location (last))) |
0 | 1079 break; |
1080 } | |
1081 | |
1082 /* Edge with goto locus might get wrong coverage info unless | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
1083 it is the only edge out of BB. |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
1084 Don't do that when the locuses match, so |
0 | 1085 if (blah) goto something; |
1086 is not computed twice. */ | |
1087 if (last | |
1088 && gimple_has_location (last) | |
111 | 1089 && !RESERVED_LOCATION_P (e->goto_locus) |
0 | 1090 && !single_succ_p (bb) |
1091 && (LOCATION_FILE (e->goto_locus) | |
1092 != LOCATION_FILE (gimple_location (last)) | |
1093 || (LOCATION_LINE (e->goto_locus) | |
1094 != LOCATION_LINE (gimple_location (last))))) | |
1095 { | |
1096 basic_block new_bb = split_edge (e); | |
1097 edge ne = single_succ_edge (new_bb); | |
1098 ne->goto_locus = e->goto_locus; | |
1099 } | |
1100 if ((e->flags & (EDGE_ABNORMAL | EDGE_ABNORMAL_CALL)) | |
111 | 1101 && e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun)) |
0 | 1102 need_exit_edge = 1; |
111 | 1103 if (e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun)) |
0 | 1104 have_exit_edge = 1; |
1105 } | |
1106 FOR_EACH_EDGE (e, ei, bb->preds) | |
1107 { | |
1108 if ((e->flags & (EDGE_ABNORMAL | EDGE_ABNORMAL_CALL)) | |
111 | 1109 && e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun)) |
0 | 1110 need_entry_edge = 1; |
111 | 1111 if (e->src == ENTRY_BLOCK_PTR_FOR_FN (cfun)) |
0 | 1112 have_entry_edge = 1; |
1113 } | |
1114 | |
1115 if (need_exit_edge && !have_exit_edge) | |
1116 { | |
1117 if (dump_file) | |
1118 fprintf (dump_file, "Adding fake exit edge to bb %i\n", | |
1119 bb->index); | |
111 | 1120 make_edge (bb, EXIT_BLOCK_PTR_FOR_FN (cfun), EDGE_FAKE); |
0 | 1121 } |
1122 if (need_entry_edge && !have_entry_edge) | |
1123 { | |
1124 if (dump_file) | |
1125 fprintf (dump_file, "Adding fake entry edge to bb %i\n", | |
1126 bb->index); | |
111 | 1127 make_edge (ENTRY_BLOCK_PTR_FOR_FN (cfun), bb, EDGE_FAKE); |
1128 /* Avoid bbs that have both fake entry edge and also some | |
1129 exit edge. One of those edges wouldn't be added to the | |
1130 spanning tree, but we can't instrument any of them. */ | |
1131 if (have_exit_edge || need_exit_edge) | |
1132 { | |
1133 gimple_stmt_iterator gsi; | |
1134 gimple *first; | |
1135 | |
1136 gsi = gsi_start_nondebug_after_labels_bb (bb); | |
1137 gcc_checking_assert (!gsi_end_p (gsi)); | |
1138 first = gsi_stmt (gsi); | |
1139 /* Don't split the bbs containing __builtin_setjmp_receiver | |
1140 or ABNORMAL_DISPATCHER calls. These are very | |
1141 special and don't expect anything to be inserted before | |
1142 them. */ | |
1143 if (is_gimple_call (first) | |
1144 && (gimple_call_builtin_p (first, BUILT_IN_SETJMP_RECEIVER) | |
1145 || (gimple_call_flags (first) & ECF_RETURNS_TWICE) | |
1146 || (gimple_call_internal_p (first) | |
1147 && (gimple_call_internal_fn (first) | |
1148 == IFN_ABNORMAL_DISPATCHER)))) | |
1149 continue; | |
1150 | |
1151 if (dump_file) | |
1152 fprintf (dump_file, "Splitting bb %i after labels\n", | |
1153 bb->index); | |
1154 split_block_after_labels (bb); | |
1155 } | |
0 | 1156 } |
1157 } | |
1158 | |
1159 el = create_edge_list (); | |
1160 num_edges = NUM_EDGES (el); | |
111 | 1161 qsort (el->index_to_edge, num_edges, sizeof (edge), compare_freqs); |
1162 alloc_aux_for_edges (sizeof (struct edge_profile_info)); | |
0 | 1163 |
1164 /* The basic blocks are expected to be numbered sequentially. */ | |
1165 compact_blocks (); | |
1166 | |
1167 ignored_edges = 0; | |
1168 for (i = 0 ; i < num_edges ; i++) | |
1169 { | |
1170 edge e = INDEX_EDGE (el, i); | |
1171 | |
1172 /* Mark edges we've replaced by fake edges above as ignored. */ | |
1173 if ((e->flags & (EDGE_ABNORMAL | EDGE_ABNORMAL_CALL)) | |
111 | 1174 && e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun) |
1175 && e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun)) | |
0 | 1176 { |
1177 EDGE_INFO (e)->ignore = 1; | |
1178 ignored_edges++; | |
1179 } | |
1180 } | |
1181 | |
1182 /* Create spanning tree from basic block graph, mark each edge that is | |
1183 on the spanning tree. We insert as many abnormal and critical edges | |
1184 as possible to minimize number of edge splits necessary. */ | |
1185 | |
1186 find_spanning_tree (el); | |
1187 | |
1188 /* Fake edges that are not on the tree will not be instrumented, so | |
1189 mark them ignored. */ | |
1190 for (num_instrumented = i = 0; i < num_edges; i++) | |
1191 { | |
1192 edge e = INDEX_EDGE (el, i); | |
111 | 1193 struct edge_profile_info *inf = EDGE_INFO (e); |
0 | 1194 |
1195 if (inf->ignore || inf->on_tree) | |
1196 /*NOP*/; | |
1197 else if (e->flags & EDGE_FAKE) | |
1198 { | |
1199 inf->ignore = 1; | |
1200 ignored_edges++; | |
1201 } | |
1202 else | |
1203 num_instrumented++; | |
1204 } | |
1205 | |
111 | 1206 total_num_blocks += n_basic_blocks_for_fn (cfun); |
0 | 1207 if (dump_file) |
111 | 1208 fprintf (dump_file, "%d basic blocks\n", n_basic_blocks_for_fn (cfun)); |
0 | 1209 |
1210 total_num_edges += num_edges; | |
1211 if (dump_file) | |
1212 fprintf (dump_file, "%d edges\n", num_edges); | |
1213 | |
1214 total_num_edges_ignored += ignored_edges; | |
1215 if (dump_file) | |
1216 fprintf (dump_file, "%d ignored edges\n", ignored_edges); | |
1217 | |
111 | 1218 total_num_edges_instrumented += num_instrumented; |
1219 if (dump_file) | |
1220 fprintf (dump_file, "%d instrumentation edges\n", num_instrumented); | |
0 | 1221 |
111 | 1222 /* Compute two different checksums. Note that we want to compute |
1223 the checksum in only once place, since it depends on the shape | |
1224 of the control flow which can change during | |
1225 various transformations. */ | |
1226 cfg_checksum = coverage_compute_cfg_checksum (cfun); | |
1227 lineno_checksum = coverage_compute_lineno_checksum (); | |
1228 | |
1229 /* Write the data from which gcov can reconstruct the basic block | |
1230 graph and function line numbers (the gcno file). */ | |
1231 if (coverage_begin_function (lineno_checksum, cfg_checksum)) | |
0 | 1232 { |
1233 gcov_position_t offset; | |
1234 | |
111 | 1235 /* Basic block flags */ |
0 | 1236 offset = gcov_write_tag (GCOV_TAG_BLOCKS); |
111 | 1237 gcov_write_unsigned (n_basic_blocks_for_fn (cfun)); |
0 | 1238 gcov_write_length (offset); |
1239 | |
111 | 1240 /* Arcs */ |
1241 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun), | |
1242 EXIT_BLOCK_PTR_FOR_FN (cfun), next_bb) | |
0 | 1243 { |
1244 edge e; | |
1245 edge_iterator ei; | |
1246 | |
1247 offset = gcov_write_tag (GCOV_TAG_ARCS); | |
111 | 1248 gcov_write_unsigned (bb->index); |
0 | 1249 |
1250 FOR_EACH_EDGE (e, ei, bb->succs) | |
1251 { | |
111 | 1252 struct edge_profile_info *i = EDGE_INFO (e); |
0 | 1253 if (!i->ignore) |
1254 { | |
1255 unsigned flag_bits = 0; | |
1256 | |
1257 if (i->on_tree) | |
1258 flag_bits |= GCOV_ARC_ON_TREE; | |
1259 if (e->flags & EDGE_FAKE) | |
1260 flag_bits |= GCOV_ARC_FAKE; | |
1261 if (e->flags & EDGE_FALLTHRU) | |
1262 flag_bits |= GCOV_ARC_FALLTHROUGH; | |
1263 /* On trees we don't have fallthru flags, but we can | |
1264 recompute them from CFG shape. */ | |
1265 if (e->flags & (EDGE_TRUE_VALUE | EDGE_FALSE_VALUE) | |
1266 && e->src->next_bb == e->dest) | |
1267 flag_bits |= GCOV_ARC_FALLTHROUGH; | |
1268 | |
111 | 1269 gcov_write_unsigned (e->dest->index); |
0 | 1270 gcov_write_unsigned (flag_bits); |
1271 } | |
1272 } | |
1273 | |
1274 gcov_write_length (offset); | |
1275 } | |
1276 | |
111 | 1277 /* Line numbers. */ |
0 | 1278 /* Initialize the output. */ |
1279 output_location (NULL, 0, NULL, NULL); | |
1280 | |
111 | 1281 FOR_EACH_BB_FN (bb, cfun) |
0 | 1282 { |
1283 gimple_stmt_iterator gsi; | |
111 | 1284 gcov_position_t offset = 0; |
0 | 1285 |
111 | 1286 if (bb == ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb) |
0 | 1287 { |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
1288 expanded_location curr_location = |
0 | 1289 expand_location (DECL_SOURCE_LOCATION (current_function_decl)); |
1290 output_location (curr_location.file, curr_location.line, | |
1291 &offset, bb); | |
1292 } | |
1293 | |
1294 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) | |
1295 { | |
111 | 1296 gimple *stmt = gsi_stmt (gsi); |
1297 if (!RESERVED_LOCATION_P (gimple_location (stmt))) | |
0 | 1298 output_location (gimple_filename (stmt), gimple_lineno (stmt), |
1299 &offset, bb); | |
1300 } | |
1301 | |
111 | 1302 /* Notice GOTO expressions eliminated while constructing the CFG. */ |
0 | 1303 if (single_succ_p (bb) |
111 | 1304 && !RESERVED_LOCATION_P (single_succ_edge (bb)->goto_locus)) |
0 | 1305 { |
111 | 1306 expanded_location curr_location |
1307 = expand_location (single_succ_edge (bb)->goto_locus); | |
1308 output_location (curr_location.file, curr_location.line, | |
1309 &offset, bb); | |
0 | 1310 } |
1311 | |
1312 if (offset) | |
1313 { | |
1314 /* A file of NULL indicates the end of run. */ | |
1315 gcov_write_unsigned (0); | |
1316 gcov_write_string (NULL); | |
1317 gcov_write_length (offset); | |
1318 } | |
1319 } | |
1320 } | |
1321 | |
1322 if (flag_profile_values) | |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
1323 gimple_find_values_to_profile (&values); |
0 | 1324 |
1325 if (flag_branch_probabilities) | |
1326 { | |
111 | 1327 compute_branch_probabilities (cfg_checksum, lineno_checksum); |
0 | 1328 if (flag_profile_values) |
111 | 1329 compute_value_histograms (values, cfg_checksum, lineno_checksum); |
0 | 1330 } |
1331 | |
1332 remove_fake_edges (); | |
1333 | |
1334 /* For each edge not on the spanning tree, add counting code. */ | |
1335 if (profile_arc_flag | |
1336 && coverage_counter_alloc (GCOV_COUNTER_ARCS, num_instrumented)) | |
1337 { | |
1338 unsigned n_instrumented; | |
1339 | |
111 | 1340 gimple_init_gcov_profiler (); |
0 | 1341 |
1342 n_instrumented = instrument_edges (el); | |
1343 | |
1344 gcc_assert (n_instrumented == num_instrumented); | |
1345 | |
1346 if (flag_profile_values) | |
1347 instrument_values (values); | |
1348 | |
1349 /* Commit changes done by instrumentation. */ | |
1350 gsi_commit_edge_inserts (); | |
1351 } | |
1352 | |
1353 free_aux_for_edges (); | |
1354 | |
111 | 1355 values.release (); |
0 | 1356 free_edge_list (el); |
111 | 1357 coverage_end_function (lineno_checksum, cfg_checksum); |
1358 if (flag_branch_probabilities && profile_info) | |
1359 { | |
1360 struct loop *loop; | |
1361 if (dump_file && (dump_flags & TDF_DETAILS)) | |
1362 report_predictor_hitrates (); | |
1363 profile_status_for_fn (cfun) = PROFILE_READ; | |
1364 | |
1365 /* At this moment we have precise loop iteration count estimates. | |
1366 Record them to loop structure before the profile gets out of date. */ | |
1367 FOR_EACH_LOOP (loop, 0) | |
1368 if (loop->header->count > 0) | |
1369 { | |
1370 gcov_type nit = expected_loop_iterations_unbounded (loop); | |
1371 widest_int bound = gcov_type_to_wide_int (nit); | |
1372 loop->any_estimate = false; | |
1373 record_niter_bound (loop, bound, true, false); | |
1374 } | |
1375 compute_function_frequency (); | |
1376 } | |
0 | 1377 } |
1378 | |
1379 /* Union find algorithm implementation for the basic blocks using | |
1380 aux fields. */ | |
1381 | |
1382 static basic_block | |
1383 find_group (basic_block bb) | |
1384 { | |
1385 basic_block group = bb, bb1; | |
1386 | |
1387 while ((basic_block) group->aux != group) | |
1388 group = (basic_block) group->aux; | |
1389 | |
1390 /* Compress path. */ | |
1391 while ((basic_block) bb->aux != group) | |
1392 { | |
1393 bb1 = (basic_block) bb->aux; | |
1394 bb->aux = (void *) group; | |
1395 bb = bb1; | |
1396 } | |
1397 return group; | |
1398 } | |
1399 | |
1400 static void | |
1401 union_groups (basic_block bb1, basic_block bb2) | |
1402 { | |
1403 basic_block bb1g = find_group (bb1); | |
1404 basic_block bb2g = find_group (bb2); | |
1405 | |
1406 /* ??? I don't have a place for the rank field. OK. Lets go w/o it, | |
1407 this code is unlikely going to be performance problem anyway. */ | |
1408 gcc_assert (bb1g != bb2g); | |
1409 | |
1410 bb1g->aux = bb2g; | |
1411 } | |
1412 | |
1413 /* This function searches all of the edges in the program flow graph, and puts | |
1414 as many bad edges as possible onto the spanning tree. Bad edges include | |
1415 abnormals edges, which can't be instrumented at the moment. Since it is | |
1416 possible for fake edges to form a cycle, we will have to develop some | |
1417 better way in the future. Also put critical edges to the tree, since they | |
1418 are more expensive to instrument. */ | |
1419 | |
1420 static void | |
1421 find_spanning_tree (struct edge_list *el) | |
1422 { | |
1423 int i; | |
1424 int num_edges = NUM_EDGES (el); | |
1425 basic_block bb; | |
1426 | |
1427 /* We use aux field for standard union-find algorithm. */ | |
111 | 1428 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun), NULL, next_bb) |
0 | 1429 bb->aux = bb; |
1430 | |
1431 /* Add fake edge exit to entry we can't instrument. */ | |
111 | 1432 union_groups (EXIT_BLOCK_PTR_FOR_FN (cfun), ENTRY_BLOCK_PTR_FOR_FN (cfun)); |
0 | 1433 |
1434 /* First add all abnormal edges to the tree unless they form a cycle. Also | |
111 | 1435 add all edges to the exit block to avoid inserting profiling code behind |
0 | 1436 setting return value from function. */ |
1437 for (i = 0; i < num_edges; i++) | |
1438 { | |
1439 edge e = INDEX_EDGE (el, i); | |
1440 if (((e->flags & (EDGE_ABNORMAL | EDGE_ABNORMAL_CALL | EDGE_FAKE)) | |
111 | 1441 || e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun)) |
0 | 1442 && !EDGE_INFO (e)->ignore |
1443 && (find_group (e->src) != find_group (e->dest))) | |
1444 { | |
1445 if (dump_file) | |
1446 fprintf (dump_file, "Abnormal edge %d to %d put to tree\n", | |
1447 e->src->index, e->dest->index); | |
1448 EDGE_INFO (e)->on_tree = 1; | |
1449 union_groups (e->src, e->dest); | |
1450 } | |
1451 } | |
1452 | |
111 | 1453 /* And now the rest. Edge list is sorted according to frequencies and |
1454 thus we will produce minimal spanning tree. */ | |
0 | 1455 for (i = 0; i < num_edges; i++) |
1456 { | |
1457 edge e = INDEX_EDGE (el, i); | |
1458 if (!EDGE_INFO (e)->ignore | |
1459 && find_group (e->src) != find_group (e->dest)) | |
1460 { | |
1461 if (dump_file) | |
1462 fprintf (dump_file, "Normal edge %d to %d put to tree\n", | |
1463 e->src->index, e->dest->index); | |
1464 EDGE_INFO (e)->on_tree = 1; | |
1465 union_groups (e->src, e->dest); | |
1466 } | |
1467 } | |
1468 | |
111 | 1469 clear_aux_for_blocks (); |
0 | 1470 } |
1471 | |
1472 /* Perform file-level initialization for branch-prob processing. */ | |
1473 | |
1474 void | |
1475 init_branch_prob (void) | |
1476 { | |
1477 int i; | |
1478 | |
1479 total_num_blocks = 0; | |
1480 total_num_edges = 0; | |
1481 total_num_edges_ignored = 0; | |
1482 total_num_edges_instrumented = 0; | |
1483 total_num_blocks_created = 0; | |
1484 total_num_passes = 0; | |
1485 total_num_times_called = 0; | |
1486 total_num_branches = 0; | |
1487 for (i = 0; i < 20; i++) | |
1488 total_hist_br_prob[i] = 0; | |
1489 } | |
1490 | |
1491 /* Performs file-level cleanup after branch-prob processing | |
1492 is completed. */ | |
1493 | |
1494 void | |
1495 end_branch_prob (void) | |
1496 { | |
1497 if (dump_file) | |
1498 { | |
1499 fprintf (dump_file, "\n"); | |
1500 fprintf (dump_file, "Total number of blocks: %d\n", | |
1501 total_num_blocks); | |
1502 fprintf (dump_file, "Total number of edges: %d\n", total_num_edges); | |
1503 fprintf (dump_file, "Total number of ignored edges: %d\n", | |
1504 total_num_edges_ignored); | |
1505 fprintf (dump_file, "Total number of instrumented edges: %d\n", | |
1506 total_num_edges_instrumented); | |
1507 fprintf (dump_file, "Total number of blocks created: %d\n", | |
1508 total_num_blocks_created); | |
1509 fprintf (dump_file, "Total number of graph solution passes: %d\n", | |
1510 total_num_passes); | |
1511 if (total_num_times_called != 0) | |
1512 fprintf (dump_file, "Average number of graph solution passes: %d\n", | |
1513 (total_num_passes + (total_num_times_called >> 1)) | |
1514 / total_num_times_called); | |
1515 fprintf (dump_file, "Total number of branches: %d\n", | |
1516 total_num_branches); | |
1517 if (total_num_branches) | |
1518 { | |
1519 int i; | |
1520 | |
1521 for (i = 0; i < 10; i++) | |
1522 fprintf (dump_file, "%d%% branches in range %d-%d%%\n", | |
1523 (total_hist_br_prob[i] + total_hist_br_prob[19-i]) * 100 | |
1524 / total_num_branches, 5*i, 5*i+5); | |
1525 } | |
1526 } | |
1527 } |