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