1 /* Calculate branch probabilities, and basic block execution counts.
2 Copyright (C) 1990-2020 Free Software Foundation, Inc.
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"
53 #include "backend.h"
54 #include "rtl.h"
55 #include "tree.h"
56 #include "gimple.h"
57 #include "cfghooks.h"
58 #include "cgraph.h"
59 #include "coverage.h"
60 #include "diagnostic-core.h"
61 #include "cfganal.h"
62 #include "value-prof.h"
63 #include "gimple-iterator.h"
64 #include "tree-cfg.h"
65 #include "dumpfile.h"
66 #include "cfgloop.h"
67
68 #include "profile.h"
69
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 {
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
82 #define BB_INFO(b) ((struct bb_profile_info *) (b)->aux)
83
84
85 /* Counter summary from the last set of coverage counts read. */
86
87 gcov_summary *profile_info;
88
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
instrument_edges(struct edge_list * el)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
117 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun), NULL, next_bb)
118 {
119 edge e;
120 edge_iterator ei;
121
122 FOR_EACH_EDGE (e, ei, bb->succs)
123 {
124 struct edge_profile_info *inf = EDGE_INFO (e);
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)" : "");
133 gimple_gen_edge_profiler (num_instr_edges++, e);
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
instrument_values(histogram_values values)146 instrument_values (histogram_values values)
147 {
148 unsigned i;
149
150 /* Emit code to generate the histograms before the insns. */
151
152 for (i = 0; i < values.length (); i++)
153 {
154 histogram_value hist = values[i];
155 unsigned t = COUNTER_FOR_HIST_TYPE (hist->type);
156
157 if (!coverage_counter_alloc (t, hist->n_counters))
158 continue;
159
160 switch (hist->type)
161 {
162 case HIST_TYPE_INTERVAL:
163 gimple_gen_interval_profiler (hist, t);
164 break;
165
166 case HIST_TYPE_POW2:
167 gimple_gen_pow2_profiler (hist, t);
168 break;
169
170 case HIST_TYPE_TOPN_VALUES:
171 gimple_gen_topn_values_profiler (hist, t);
172 break;
173
174 case HIST_TYPE_INDIR_CALL:
175 gimple_gen_ic_profiler (hist, t);
176 break;
177
178 case HIST_TYPE_AVERAGE:
179 gimple_gen_average_profiler (hist, t);
180 break;
181
182 case HIST_TYPE_IOR:
183 gimple_gen_ior_profiler (hist, t);
184 break;
185
186 case HIST_TYPE_TIME_PROFILE:
187 gimple_gen_time_profiler (t);
188 break;
189
190 default:
191 gcc_unreachable ();
192 }
193 }
194 }
195
196
197 /* Computes hybrid profile for all matching entries in da_file.
198
199 CFG_CHECKSUM is the precomputed checksum for the CFG. */
200
201 static gcov_type *
get_exec_counts(unsigned cfg_checksum,unsigned lineno_checksum)202 get_exec_counts (unsigned cfg_checksum, unsigned lineno_checksum)
203 {
204 unsigned num_edges = 0;
205 basic_block bb;
206 gcov_type *counts;
207
208 /* Count the edges to be (possibly) instrumented. */
209 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun), NULL, next_bb)
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
219 counts = get_coverage_counts (GCOV_COUNTER_ARCS, cfg_checksum,
220 lineno_checksum, num_edges);
221 if (!counts)
222 return NULL;
223
224 return counts;
225 }
226
227 static bool
is_edge_inconsistent(vec<edge,va_gc> * edges)228 is_edge_inconsistent (vec<edge, va_gc> *edges)
229 {
230 edge e;
231 edge_iterator ei;
232 FOR_EACH_EDGE (e, ei, edges)
233 {
234 if (!EDGE_INFO (e)->ignore)
235 {
236 if (edge_gcov_count (e) < 0
237 && (!(e->flags & EDGE_FAKE)
238 || !block_ends_with_call_p (e->src)))
239 {
240 if (dump_file)
241 {
242 fprintf (dump_file,
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);
247 }
248 return true;
249 }
250 }
251 }
252 return false;
253 }
254
255 static void
correct_negative_edge_counts(void)256 correct_negative_edge_counts (void)
257 {
258 basic_block bb;
259 edge e;
260 edge_iterator ei;
261
262 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun), NULL, next_bb)
263 {
264 FOR_EACH_EDGE (e, ei, bb->succs)
265 {
266 if (edge_gcov_count (e) < 0)
267 edge_gcov_count (e) = 0;
268 }
269 }
270 }
271
272 /* Check consistency.
273 Return true if inconsistency is found. */
274 static bool
is_inconsistent(void)275 is_inconsistent (void)
276 {
277 basic_block bb;
278 bool inconsistent = false;
279 FOR_EACH_BB_FN (bb, cfun)
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;
287 if (bb_gcov_count (bb) < 0)
288 {
289 if (dump_file)
290 {
291 fprintf (dump_file, "BB %i count is negative "
292 "%" PRId64,
293 bb->index,
294 bb_gcov_count (bb));
295 dump_bb (dump_file, bb, 0, TDF_DETAILS);
296 }
297 inconsistent = true;
298 }
299 if (bb_gcov_count (bb) != sum_edge_counts (bb->preds))
300 {
301 if (dump_file)
302 {
303 fprintf (dump_file, "BB %i count does not match sum of incoming edges "
304 "%" PRId64" should be %" PRId64,
305 bb->index,
306 bb_gcov_count (bb),
307 sum_edge_counts (bb->preds));
308 dump_bb (dump_file, bb, 0, TDF_DETAILS);
309 }
310 inconsistent = true;
311 }
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)))
315 {
316 if (dump_file)
317 {
318 fprintf (dump_file, "BB %i count does not match sum of outgoing edges "
319 "%" PRId64" should be %" PRId64,
320 bb->index,
321 bb_gcov_count (bb),
322 sum_edge_counts (bb->succs));
323 dump_bb (dump_file, bb, 0, TDF_DETAILS);
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
set_bb_counts(void)336 set_bb_counts (void)
337 {
338 basic_block bb;
339 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun), NULL, next_bb)
340 {
341 bb_gcov_count (bb) = sum_edge_counts (bb->succs);
342 gcc_assert (bb_gcov_count (bb) >= 0);
343 }
344 }
345
346 /* Reads profile data and returns total number of edge counts read */
347 static int
read_profile_edge_counts(gcov_type * exec_counts)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
358 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun), NULL, next_bb)
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)
368 edge_gcov_count (e) = exec_counts[exec_counts_pos++];
369 else
370 edge_gcov_count (e) = 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);
379 fprintf (dump_file, "%" PRId64,
380 (int64_t) edge_gcov_count (e));
381 }
382 }
383 }
384
385 return num_edges;
386 }
387
388
389 /* Compute the branch probabilities for the various branches.
390 Annotate them accordingly.
391
392 CFG_CHECKSUM is the precomputed checksum for the CFG. */
393
394 static void
compute_branch_probabilities(unsigned cfg_checksum,unsigned lineno_checksum)395 compute_branch_probabilities (unsigned cfg_checksum, unsigned lineno_checksum)
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;
404 gcov_type *exec_counts = get_exec_counts (cfg_checksum, lineno_checksum);
405 int inconsistent = 0;
406
407 /* Very simple sanity checks so we catch bugs in our profiling code. */
408 if (!profile_info)
409 {
410 if (dump_file)
411 fprintf (dump_file, "Profile info is missing; giving up\n");
412 return;
413 }
414
415 bb_gcov_counts.safe_grow_cleared (last_basic_block_for_fn (cfun));
416 edge_gcov_counts = new hash_map<edge,gcov_type>;
417
418 /* Attach extra info block to each bb. */
419 alloc_aux_for_blocks (sizeof (struct bb_profile_info));
420 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun), NULL, next_bb)
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. */
434 BB_INFO (EXIT_BLOCK_PTR_FOR_FN (cfun))->succ_count = 2;
435 BB_INFO (ENTRY_BLOCK_PTR_FOR_FN (cfun))->pred_count = 2;
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;
465 FOR_BB_BETWEEN (bb, EXIT_BLOCK_PTR_FOR_FN (cfun), NULL, prev_bb)
466 {
467 struct bb_profile_info *bi = BB_INFO (bb);
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)
477 total += edge_gcov_count (e);
478 bb_gcov_count (bb) = total;
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)
489 total += edge_gcov_count (e);
490 bb_gcov_count (bb) = total;
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)
506 total += edge_gcov_count (e);
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. */
514 total = bb_gcov_count (bb) - total;
515
516 gcc_assert (e);
517 EDGE_INFO (e)->count_valid = 1;
518 edge_gcov_count (e) = total;
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)
533 total += edge_gcov_count (e);
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. */
541 total = bb_gcov_count (bb) - total + edge_gcov_count (e);
542
543 gcc_assert (e);
544 EDGE_INFO (e)->count_valid = 1;
545 edge_gcov_count (e) = total;
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. */
561 FOR_EACH_BB_FN (bb, cfun)
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;
575 if (dump_enabled_p () && informed == 0)
576 {
577 informed = 1;
578 dump_printf_loc (MSG_NOTE,
579 dump_user_location_t::from_location_t (input_location),
580 "correcting inconsistent profile data\n");
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
600 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun), NULL, next_bb)
601 {
602 edge e;
603 edge_iterator ei;
604
605 if (bb_gcov_count (bb) < 0)
606 {
607 error ("corrupted profile info: number of iterations for basic block %d thought to be %i",
608 bb->index, (int)bb_gcov_count (bb));
609 bb_gcov_count (bb) = 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. */
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)))
622 {
623 if (block_ends_with_call_p (bb))
624 edge_gcov_count (e) = edge_gcov_count (e) < 0
625 ? 0 : bb_gcov_count (bb);
626 }
627 if (edge_gcov_count (e) < 0
628 || edge_gcov_count (e) > bb_gcov_count (bb))
629 {
630 error ("corrupted profile info: number of executions for edge %d-%d thought to be %i",
631 e->src->index, e->dest->index,
632 (int)edge_gcov_count (e));
633 edge_gcov_count (e) = bb_gcov_count (bb) / 2;
634 }
635 }
636 if (bb_gcov_count (bb))
637 {
638 bool set_to_guessed = false;
639 FOR_EACH_EDGE (e, ei, bb->succs)
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 ();
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
666 prob = e->probability.to_reg_br_prob_base ();
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). */
681 else if (profile_status_for_fn (cfun) == PROFILE_ABSENT)
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)))
692 e->probability
693 = profile_probability::guessed_always ().apply_scale (1, total);
694 else
695 e->probability = profile_probability::never ();
696 }
697 else
698 {
699 total += EDGE_COUNT (bb->succs);
700 FOR_EACH_EDGE (e, ei, bb->succs)
701 e->probability
702 = profile_probability::guessed_always ().apply_scale (1, total);
703 }
704 if (bb->index >= NUM_FIXED_BLOCKS
705 && block_ends_with_condjump_p (bb)
706 && EDGE_COUNT (bb->succs) >= 2)
707 num_branches++;
708 }
709 }
710
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
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)
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 ();
724 /* If function was not trained, preserve local estimates including statically
725 determined zero counts. */
726 else if (profile_status_for_fn (cfun) == PROFILE_READ
727 && !flag_profile_partial_training)
728 FOR_ALL_BB_FN (bb, cfun)
729 if (!(bb->count == profile_count::zero ()))
730 bb->count = bb->count.global0 ();
731
732 bb_gcov_counts.release ();
733 delete edge_gcov_counts;
734 edge_gcov_counts = NULL;
735
736 update_max_bb_count ();
737
738 if (dump_file)
739 {
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
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
763 /* Sort the histogram value and count for TOPN and INDIR_CALL type. */
764
765 static void
sort_hist_values(histogram_value hist)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 }
799 /* Load value histograms values whose description is stored in VALUES array
800 from .gcda file.
801
802 CFG_CHECKSUM is the precomputed checksum for the CFG. */
803
804 static void
compute_value_histograms(histogram_values values,unsigned cfg_checksum,unsigned lineno_checksum)805 compute_value_histograms (histogram_values values, unsigned cfg_checksum,
806 unsigned lineno_checksum)
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;
813 struct cgraph_node *node;
814
815 for (t = 0; t < GCOV_N_VALUE_COUNTERS; t++)
816 n_histogram_counters[t] = 0;
817
818 for (i = 0; i < values.length (); i++)
819 {
820 histogram_value hist = values[i];
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
833 histogram_counts[t] = get_coverage_counts (COUNTER_FOR_HIST_TYPE (t),
834 cfg_checksum,
835 lineno_checksum,
836 n_histogram_counters[t]);
837 if (histogram_counts[t])
838 any = 1;
839 act_count[t] = histogram_counts[t];
840 }
841 if (!any)
842 return;
843
844 for (i = 0; i < values.length (); i++)
845 {
846 histogram_value hist = values[i];
847 gimple *stmt = hist->hvalue.stmt;
848
849 t = (int) hist->type;
850
851 aact_count = act_count[t];
852
853 if (act_count[t])
854 act_count[t] += hist->n_counters;
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++)
859 if (aact_count)
860 hist->hvalue.counters[j] = aact_count[j];
861 else
862 hist->hvalue.counters[j] = 0;
863
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
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);
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 }
891
892 if (dump_file)
893 fprintf (dump_file, "Read tp_first_run: %d\n", node->tp_first_run);
894 }
895 }
896
897 for (t = 0; t < GCOV_N_VALUE_COUNTERS; t++)
898 free (histogram_counts[t]);
899 }
900
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
hashlocation_triplet_hash917 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
equallocation_triplet_hash928 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
mark_deletedlocation_triplet_hash938 mark_deleted (location_triplet &ref)
939 {
940 ref.lineno = -1;
941 }
942
943 static const bool empty_zero_p = false;
944
945 static void
mark_emptylocation_triplet_hash946 mark_empty (location_triplet &ref)
947 {
948 ref.lineno = -2;
949 }
950
951 static bool
is_deletedlocation_triplet_hash952 is_deleted (const location_triplet &ref)
953 {
954 return ref.lineno == -1;
955 }
956
957 static bool
is_emptylocation_triplet_hash958 is_empty (const location_triplet &ref)
959 {
960 return ref.lineno == -2;
961 }
962 };
963
964
965
966
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
output_location(hash_set<location_triplet_hash> * streamed_locations,char const * file_name,int line,gcov_position_t * offset,basic_block bb)971 output_location (hash_set<location_triplet_hash> *streamed_locations,
972 char const *file_name, int line,
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
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
987 if (!file_name)
988 {
989 prev_file_name = NULL;
990 prev_line = -1;
991 return;
992 }
993
994 name_differs = !prev_file_name || filename_cmp (file_name, prev_file_name);
995 line_differs = prev_line != line;
996
997 if (!*offset)
998 {
999 *offset = gcov_write_tag (GCOV_TAG_LINES);
1000 gcov_write_unsigned (bb->index);
1001 name_differs = line_differs = true;
1002 }
1003
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 }
1017 }
1018
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
compare_freqs(const void * p1,const void * p2)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
1040 /* Only read execution count for thunks. */
1041
1042 void
read_thunk_profile(struct cgraph_node * node)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
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.
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
1068 flow graph. This data is written to the gcno file for gcov.
1069
1070 When FLAG_BRANCH_PROBABILITIES is nonzero, this function reads auxiliary
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().
1075
1076 Main entry point of this file. */
1077
1078 void
branch_prob(bool thunk)1079 branch_prob (bool thunk)
1080 {
1081 basic_block bb;
1082 unsigned i;
1083 unsigned num_edges, ignored_edges;
1084 unsigned num_instrumented;
1085 struct edge_list *el;
1086 histogram_values values = histogram_values ();
1087 unsigned cfg_checksum, lineno_checksum;
1088
1089 total_num_times_called++;
1090
1091 flow_call_edges_add (NULL);
1092 add_noreturn_fake_exit_edges ();
1093
1094 hash_set <location_triplet_hash> streamed_locations;
1095
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. */
1106
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;
1113
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;
1124
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 }
1136
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)
1162 {
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;
1168 }
1169
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)
1178 {
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;
1190
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;
1205
1206 if (dump_file)
1207 fprintf (dump_file, "Splitting bb %i after labels\n",
1208 bb->index);
1209 split_block_after_labels (bb);
1210 }
1211 }
1212 }
1213 }
1214
1215 el = create_edge_list ();
1216 num_edges = NUM_EDGES (el);
1217 qsort (el->index_to_edge, num_edges, sizeof (edge), compare_freqs);
1218 alloc_aux_for_edges (sizeof (struct edge_profile_info));
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))
1230 && e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun)
1231 && e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
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
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
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);
1260 struct edge_profile_info *inf = EDGE_INFO (e);
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
1273 total_num_blocks += n_basic_blocks_for_fn (cfun);
1274 if (dump_file)
1275 fprintf (dump_file, "%d basic blocks\n", n_basic_blocks_for_fn (cfun));
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
1285 total_num_edges_instrumented += num_instrumented;
1286 if (dump_file)
1287 fprintf (dump_file, "%d instrumentation edges\n", num_instrumented);
1288
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. */
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 }
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))
1308 {
1309 gcov_position_t offset;
1310
1311 /* Basic block flags */
1312 offset = gcov_write_tag (GCOV_TAG_BLOCKS);
1313 gcov_write_unsigned (n_basic_blocks_for_fn (cfun));
1314 gcov_write_length (offset);
1315
1316 /* Arcs */
1317 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun),
1318 EXIT_BLOCK_PTR_FOR_FN (cfun), next_bb)
1319 {
1320 edge e;
1321 edge_iterator ei;
1322
1323 offset = gcov_write_tag (GCOV_TAG_ARCS);
1324 gcov_write_unsigned (bb->index);
1325
1326 FOR_EACH_EDGE (e, ei, bb->succs)
1327 {
1328 struct edge_profile_info *i = EDGE_INFO (e);
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
1345 gcov_write_unsigned (e->dest->index);
1346 gcov_write_unsigned (flag_bits);
1347 }
1348 }
1349
1350 gcov_write_length (offset);
1351 }
1352
1353 /* Line numbers. */
1354 /* Initialize the output. */
1355 output_location (&streamed_locations, NULL, 0, NULL, NULL);
1356
1357 hash_set<int_hash <location_t, 0, 2> > seen_locations;
1358
1359 FOR_EACH_BB_FN (bb, cfun)
1360 {
1361 gimple_stmt_iterator gsi;
1362 gcov_position_t offset = 0;
1363
1364 if (bb == ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb)
1365 {
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 MAX (1, curr_location.line), &offset, bb);
1371 }
1372
1373 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1374 {
1375 gimple *stmt = gsi_stmt (gsi);
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 MAX (1, gimple_lineno (stmt)), &offset, bb);
1382 }
1383 }
1384
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;
1389 if (single_succ_p (bb)
1390 && (loc = single_succ_edge (bb)->goto_locus)
1391 && !RESERVED_LOCATION_P (loc)
1392 && !seen_locations.contains (loc))
1393 {
1394 expanded_location curr_location = expand_location (loc);
1395 output_location (&streamed_locations, curr_location.file,
1396 MAX (1, curr_location.line), &offset, bb);
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)
1410 gimple_find_values_to_profile (&values);
1411
1412 if (flag_branch_probabilities)
1413 {
1414 compute_branch_probabilities (cfg_checksum, lineno_checksum);
1415 if (flag_profile_values)
1416 compute_value_histograms (values, cfg_checksum, lineno_checksum);
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
1427 gimple_init_gcov_profiler ();
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
1442 values.release ();
1443 free_edge_list (el);
1444 coverage_end_function (lineno_checksum, cfg_checksum);
1445 if (flag_branch_probabilities
1446 && (profile_status_for_fn (cfun) == PROFILE_READ))
1447 {
1448 class loop *loop;
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)
1455 if (loop->header->count > 0 && loop->header->count.reliable_p ())
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 }
1464 }
1465
1466 /* Union find algorithm implementation for the basic blocks using
1467 aux fields. */
1468
1469 static basic_block
find_group(basic_block bb)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
union_groups(basic_block bb1,basic_block bb2)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
find_spanning_tree(struct edge_list * el)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. */
1515 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun), NULL, next_bb)
1516 bb->aux = bb;
1517
1518 /* Add fake edge exit to entry we can't instrument. */
1519 union_groups (EXIT_BLOCK_PTR_FOR_FN (cfun), ENTRY_BLOCK_PTR_FOR_FN (cfun));
1520
1521 /* First add all abnormal edges to the tree unless they form a cycle. Also
1522 add all edges to the exit block to avoid inserting profiling code behind
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))
1528 || e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
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
1540 /* And now the rest. Edge list is sorted according to frequencies and
1541 thus we will produce minimal spanning tree. */
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
1556 clear_aux_for_blocks ();
1557 }
1558
1559 /* Perform file-level initialization for branch-prob processing. */
1560
1561 void
init_branch_prob(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
end_branch_prob(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 }
1615