1 /* Calculate branch probabilities, and basic block execution counts.
2 Copyright (C) 1990, 1991, 1992, 1993, 1994, 1996, 1997, 1998, 1999,
3 2000, 2001, 2002, 2003, 2004, 2005 Free Software Foundation, Inc.
4 Contributed by James E. Wilson, UC Berkeley/Cygnus Support;
5 based on some ideas from Dain Samples of UC Berkeley.
6 Further mangling by Bob Manson, Cygnus Support.
7
8 This file is part of GCC.
9
10 GCC is free software; you can redistribute it and/or modify it under
11 the terms of the GNU General Public License as published by the Free
12 Software Foundation; either version 2, or (at your option) any later
13 version.
14
15 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
16 WARRANTY; without even the implied warranty of MERCHANTABILITY or
17 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
18 for more details.
19
20 You should have received a copy of the GNU General Public License
21 along with GCC; see the file COPYING. If not, write to the Free
22 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
23 02110-1301, USA. */
24
25 /* Generate basic block profile instrumentation and auxiliary files.
26 Profile generation is optimized, so that not all arcs in the basic
27 block graph need instrumenting. First, the BB graph is closed with
28 one entry (function start), and one exit (function exit). Any
29 ABNORMAL_EDGE cannot be instrumented (because there is no control
30 path to place the code). We close the graph by inserting fake
31 EDGE_FAKE edges to the EXIT_BLOCK, from the sources of abnormal
32 edges that do not go to the exit_block. We ignore such abnormal
33 edges. Naturally these fake edges are never directly traversed,
34 and so *cannot* be directly instrumented. Some other graph
35 massaging is done. To optimize the instrumentation we generate the
36 BB minimal span tree, only edges that are not on the span tree
37 (plus the entry point) need instrumenting. From that information
38 all other edge counts can be deduced. By construction all fake
39 edges must be on the spanning tree. We also attempt to place
40 EDGE_CRITICAL edges on the spanning tree.
41
42 The auxiliary files generated are <dumpbase>.gcno (at compile time)
43 and <dumpbase>.gcda (at run time). The format is
44 described in full in gcov-io.h. */
45
46 /* ??? Register allocation should use basic block execution counts to
47 give preference to the most commonly executed blocks. */
48
49 /* ??? Should calculate branch probabilities before instrumenting code, since
50 then we can use arc counts to help decide which arcs to instrument. */
51
52 #include "config.h"
53 #include "system.h"
54 #include "coretypes.h"
55 #include "tm.h"
56 #include "rtl.h"
57 #include "flags.h"
58 #include "output.h"
59 #include "regs.h"
60 #include "expr.h"
61 #include "function.h"
62 #include "toplev.h"
63 #include "coverage.h"
64 #include "value-prof.h"
65 #include "tree.h"
66 #include "cfghooks.h"
67 #include "tree-flow.h"
68 #include "timevar.h"
69 #include "cfgloop.h"
70 #include "tree-pass.h"
71
72 /* Hooks for profiling. */
73 static struct profile_hooks* profile_hooks;
74
75 /* Additional information about the edges we need. */
76 struct edge_info {
77 unsigned int count_valid : 1;
78
79 /* Is on the spanning tree. */
80 unsigned int on_tree : 1;
81
82 /* Pretend this edge does not exist (it is abnormal and we've
83 inserted a fake to compensate). */
84 unsigned int ignore : 1;
85 };
86
87 struct bb_info {
88 unsigned int count_valid : 1;
89
90 /* Number of successor and predecessor edges. */
91 gcov_type succ_count;
92 gcov_type pred_count;
93 };
94
95 #define EDGE_INFO(e) ((struct edge_info *) (e)->aux)
96 #define BB_INFO(b) ((struct bb_info *) (b)->aux)
97
98 /* Counter summary from the last set of coverage counts read. */
99
100 const struct gcov_ctr_summary *profile_info;
101
102 /* Collect statistics on the performance of this pass for the entire source
103 file. */
104
105 static int total_num_blocks;
106 static int total_num_edges;
107 static int total_num_edges_ignored;
108 static int total_num_edges_instrumented;
109 static int total_num_blocks_created;
110 static int total_num_passes;
111 static int total_num_times_called;
112 static int total_hist_br_prob[20];
113 static int total_num_never_executed;
114 static int total_num_branches;
115
116 /* Forward declarations. */
117 static void find_spanning_tree (struct edge_list *);
118 static unsigned instrument_edges (struct edge_list *);
119 static void instrument_values (histogram_values);
120 static void compute_branch_probabilities (void);
121 static void compute_value_histograms (histogram_values);
122 static gcov_type * get_exec_counts (void);
123 static basic_block find_group (basic_block);
124 static void union_groups (basic_block, basic_block);
125
126
127 /* Add edge instrumentation code to the entire insn chain.
128
129 F is the first insn of the chain.
130 NUM_BLOCKS is the number of basic blocks found in F. */
131
132 static unsigned
instrument_edges(struct edge_list * el)133 instrument_edges (struct edge_list *el)
134 {
135 unsigned num_instr_edges = 0;
136 int num_edges = NUM_EDGES (el);
137 basic_block bb;
138
139 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
140 {
141 edge e;
142 edge_iterator ei;
143
144 FOR_EACH_EDGE (e, ei, bb->succs)
145 {
146 struct edge_info *inf = EDGE_INFO (e);
147
148 if (!inf->ignore && !inf->on_tree)
149 {
150 gcc_assert (!(e->flags & EDGE_ABNORMAL));
151 if (dump_file)
152 fprintf (dump_file, "Edge %d to %d instrumented%s\n",
153 e->src->index, e->dest->index,
154 EDGE_CRITICAL_P (e) ? " (and split)" : "");
155 (profile_hooks->gen_edge_profiler) (num_instr_edges++, e);
156 }
157 }
158 }
159
160 total_num_blocks_created += num_edges;
161 if (dump_file)
162 fprintf (dump_file, "%d edges instrumented\n", num_instr_edges);
163 return num_instr_edges;
164 }
165
166 /* Add code to measure histograms for values in list VALUES. */
167 static void
instrument_values(histogram_values values)168 instrument_values (histogram_values values)
169 {
170 unsigned i, t;
171
172 /* Emit code to generate the histograms before the insns. */
173
174 for (i = 0; i < VEC_length (histogram_value, values); i++)
175 {
176 histogram_value hist = VEC_index (histogram_value, values, i);
177 switch (hist->type)
178 {
179 case HIST_TYPE_INTERVAL:
180 t = GCOV_COUNTER_V_INTERVAL;
181 break;
182
183 case HIST_TYPE_POW2:
184 t = GCOV_COUNTER_V_POW2;
185 break;
186
187 case HIST_TYPE_SINGLE_VALUE:
188 t = GCOV_COUNTER_V_SINGLE;
189 break;
190
191 case HIST_TYPE_CONST_DELTA:
192 t = GCOV_COUNTER_V_DELTA;
193 break;
194
195 default:
196 gcc_unreachable ();
197 }
198 if (!coverage_counter_alloc (t, hist->n_counters))
199 continue;
200
201 switch (hist->type)
202 {
203 case HIST_TYPE_INTERVAL:
204 (profile_hooks->gen_interval_profiler) (hist, t, 0);
205 break;
206
207 case HIST_TYPE_POW2:
208 (profile_hooks->gen_pow2_profiler) (hist, t, 0);
209 break;
210
211 case HIST_TYPE_SINGLE_VALUE:
212 (profile_hooks->gen_one_value_profiler) (hist, t, 0);
213 break;
214
215 case HIST_TYPE_CONST_DELTA:
216 (profile_hooks->gen_const_delta_profiler) (hist, t, 0);
217 break;
218
219 default:
220 gcc_unreachable ();
221 }
222 }
223 }
224
225
226 /* Computes hybrid profile for all matching entries in da_file. */
227
228 static gcov_type *
get_exec_counts(void)229 get_exec_counts (void)
230 {
231 unsigned num_edges = 0;
232 basic_block bb;
233 gcov_type *counts;
234
235 /* Count the edges to be (possibly) instrumented. */
236 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
237 {
238 edge e;
239 edge_iterator ei;
240
241 FOR_EACH_EDGE (e, ei, bb->succs)
242 if (!EDGE_INFO (e)->ignore && !EDGE_INFO (e)->on_tree)
243 num_edges++;
244 }
245
246 counts = get_coverage_counts (GCOV_COUNTER_ARCS, num_edges, &profile_info);
247 if (!counts)
248 return NULL;
249
250 if (dump_file && profile_info)
251 fprintf(dump_file, "Merged %u profiles with maximal count %u.\n",
252 profile_info->runs, (unsigned) profile_info->sum_max);
253
254 return counts;
255 }
256
257
258 /* Compute the branch probabilities for the various branches.
259 Annotate them accordingly. */
260
261 static void
compute_branch_probabilities(void)262 compute_branch_probabilities (void)
263 {
264 basic_block bb;
265 int i;
266 int num_edges = 0;
267 int changes;
268 int passes;
269 int hist_br_prob[20];
270 int num_never_executed;
271 int num_branches;
272 gcov_type *exec_counts = get_exec_counts ();
273 int exec_counts_pos = 0;
274
275 /* Very simple sanity checks so we catch bugs in our profiling code. */
276 if (profile_info)
277 {
278 if (profile_info->run_max * profile_info->runs < profile_info->sum_max)
279 {
280 error ("corrupted profile info: run_max * runs < sum_max");
281 exec_counts = NULL;
282 }
283
284 if (profile_info->sum_all < profile_info->sum_max)
285 {
286 error ("corrupted profile info: sum_all is smaller than sum_max");
287 exec_counts = NULL;
288 }
289 }
290
291 /* Attach extra info block to each bb. */
292
293 alloc_aux_for_blocks (sizeof (struct bb_info));
294 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
295 {
296 edge e;
297 edge_iterator ei;
298
299 FOR_EACH_EDGE (e, ei, bb->succs)
300 if (!EDGE_INFO (e)->ignore)
301 BB_INFO (bb)->succ_count++;
302 FOR_EACH_EDGE (e, ei, bb->preds)
303 if (!EDGE_INFO (e)->ignore)
304 BB_INFO (bb)->pred_count++;
305 }
306
307 /* Avoid predicting entry on exit nodes. */
308 BB_INFO (EXIT_BLOCK_PTR)->succ_count = 2;
309 BB_INFO (ENTRY_BLOCK_PTR)->pred_count = 2;
310
311 /* For each edge not on the spanning tree, set its execution count from
312 the .da file. */
313
314 /* The first count in the .da file is the number of times that the function
315 was entered. This is the exec_count for block zero. */
316
317 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
318 {
319 edge e;
320 edge_iterator ei;
321
322 FOR_EACH_EDGE (e, ei, bb->succs)
323 if (!EDGE_INFO (e)->ignore && !EDGE_INFO (e)->on_tree)
324 {
325 num_edges++;
326 if (exec_counts)
327 {
328 e->count = exec_counts[exec_counts_pos++];
329 if (e->count > profile_info->sum_max)
330 {
331 error ("corrupted profile info: edge from %i to %i exceeds maximal count",
332 bb->index, e->dest->index);
333 }
334 }
335 else
336 e->count = 0;
337
338 EDGE_INFO (e)->count_valid = 1;
339 BB_INFO (bb)->succ_count--;
340 BB_INFO (e->dest)->pred_count--;
341 if (dump_file)
342 {
343 fprintf (dump_file, "\nRead edge from %i to %i, count:",
344 bb->index, e->dest->index);
345 fprintf (dump_file, HOST_WIDEST_INT_PRINT_DEC,
346 (HOST_WIDEST_INT) e->count);
347 }
348 }
349 }
350
351 if (dump_file)
352 fprintf (dump_file, "\n%d edge counts read\n", num_edges);
353
354 /* For every block in the file,
355 - if every exit/entrance edge has a known count, then set the block count
356 - if the block count is known, and every exit/entrance edge but one has
357 a known execution count, then set the count of the remaining edge
358
359 As edge counts are set, decrement the succ/pred count, but don't delete
360 the edge, that way we can easily tell when all edges are known, or only
361 one edge is unknown. */
362
363 /* The order that the basic blocks are iterated through is important.
364 Since the code that finds spanning trees starts with block 0, low numbered
365 edges are put on the spanning tree in preference to high numbered edges.
366 Hence, most instrumented edges are at the end. Graph solving works much
367 faster if we propagate numbers from the end to the start.
368
369 This takes an average of slightly more than 3 passes. */
370
371 changes = 1;
372 passes = 0;
373 while (changes)
374 {
375 passes++;
376 changes = 0;
377 FOR_BB_BETWEEN (bb, EXIT_BLOCK_PTR, NULL, prev_bb)
378 {
379 struct bb_info *bi = BB_INFO (bb);
380 if (! bi->count_valid)
381 {
382 if (bi->succ_count == 0)
383 {
384 edge e;
385 edge_iterator ei;
386 gcov_type total = 0;
387
388 FOR_EACH_EDGE (e, ei, bb->succs)
389 total += e->count;
390 bb->count = total;
391 bi->count_valid = 1;
392 changes = 1;
393 }
394 else if (bi->pred_count == 0)
395 {
396 edge e;
397 edge_iterator ei;
398 gcov_type total = 0;
399
400 FOR_EACH_EDGE (e, ei, bb->preds)
401 total += e->count;
402 bb->count = total;
403 bi->count_valid = 1;
404 changes = 1;
405 }
406 }
407 if (bi->count_valid)
408 {
409 if (bi->succ_count == 1)
410 {
411 edge e;
412 edge_iterator ei;
413 gcov_type total = 0;
414
415 /* One of the counts will be invalid, but it is zero,
416 so adding it in also doesn't hurt. */
417 FOR_EACH_EDGE (e, ei, bb->succs)
418 total += e->count;
419
420 /* Seedgeh for the invalid edge, and set its count. */
421 FOR_EACH_EDGE (e, ei, bb->succs)
422 if (! EDGE_INFO (e)->count_valid && ! EDGE_INFO (e)->ignore)
423 break;
424
425 /* Calculate count for remaining edge by conservation. */
426 total = bb->count - total;
427
428 gcc_assert (e);
429 EDGE_INFO (e)->count_valid = 1;
430 e->count = total;
431 bi->succ_count--;
432
433 BB_INFO (e->dest)->pred_count--;
434 changes = 1;
435 }
436 if (bi->pred_count == 1)
437 {
438 edge e;
439 edge_iterator ei;
440 gcov_type total = 0;
441
442 /* One of the counts will be invalid, but it is zero,
443 so adding it in also doesn't hurt. */
444 FOR_EACH_EDGE (e, ei, bb->preds)
445 total += e->count;
446
447 /* Search for the invalid edge, and set its count. */
448 FOR_EACH_EDGE (e, ei, bb->preds)
449 if (!EDGE_INFO (e)->count_valid && !EDGE_INFO (e)->ignore)
450 break;
451
452 /* Calculate count for remaining edge by conservation. */
453 total = bb->count - total + e->count;
454
455 gcc_assert (e);
456 EDGE_INFO (e)->count_valid = 1;
457 e->count = total;
458 bi->pred_count--;
459
460 BB_INFO (e->src)->succ_count--;
461 changes = 1;
462 }
463 }
464 }
465 }
466 if (dump_file)
467 dump_flow_info (dump_file, dump_flags);
468
469 total_num_passes += passes;
470 if (dump_file)
471 fprintf (dump_file, "Graph solving took %d passes.\n\n", passes);
472
473 /* If the graph has been correctly solved, every block will have a
474 succ and pred count of zero. */
475 FOR_EACH_BB (bb)
476 {
477 gcc_assert (!BB_INFO (bb)->succ_count && !BB_INFO (bb)->pred_count);
478 }
479
480 /* For every edge, calculate its branch probability and add a reg_note
481 to the branch insn to indicate this. */
482
483 for (i = 0; i < 20; i++)
484 hist_br_prob[i] = 0;
485 num_never_executed = 0;
486 num_branches = 0;
487
488 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
489 {
490 edge e;
491 edge_iterator ei;
492
493 if (bb->count < 0)
494 {
495 error ("corrupted profile info: number of iterations for basic block %d thought to be %i",
496 bb->index, (int)bb->count);
497 bb->count = 0;
498 }
499 FOR_EACH_EDGE (e, ei, bb->succs)
500 {
501 /* Function may return twice in the cased the called function is
502 setjmp or calls fork, but we can't represent this by extra
503 edge from the entry, since extra edge from the exit is
504 already present. We get negative frequency from the entry
505 point. */
506 if ((e->count < 0
507 && e->dest == EXIT_BLOCK_PTR)
508 || (e->count > bb->count
509 && e->dest != EXIT_BLOCK_PTR))
510 {
511 if (block_ends_with_call_p (bb))
512 e->count = e->count < 0 ? 0 : bb->count;
513 }
514 if (e->count < 0 || e->count > bb->count)
515 {
516 error ("corrupted profile info: number of executions for edge %d-%d thought to be %i",
517 e->src->index, e->dest->index,
518 (int)e->count);
519 e->count = bb->count / 2;
520 }
521 }
522 if (bb->count)
523 {
524 FOR_EACH_EDGE (e, ei, bb->succs)
525 e->probability = (e->count * REG_BR_PROB_BASE + bb->count / 2) / bb->count;
526 if (bb->index >= NUM_FIXED_BLOCKS
527 && block_ends_with_condjump_p (bb)
528 && EDGE_COUNT (bb->succs) >= 2)
529 {
530 int prob;
531 edge e;
532 int index;
533
534 /* Find the branch edge. It is possible that we do have fake
535 edges here. */
536 FOR_EACH_EDGE (e, ei, bb->succs)
537 if (!(e->flags & (EDGE_FAKE | EDGE_FALLTHRU)))
538 break;
539
540 prob = e->probability;
541 index = prob * 20 / REG_BR_PROB_BASE;
542
543 if (index == 20)
544 index = 19;
545 hist_br_prob[index]++;
546
547 num_branches++;
548 }
549 }
550 /* As a last resort, distribute the probabilities evenly.
551 Use simple heuristics that if there are normal edges,
552 give all abnormals frequency of 0, otherwise distribute the
553 frequency over abnormals (this is the case of noreturn
554 calls). */
555 else if (profile_status == PROFILE_ABSENT)
556 {
557 int total = 0;
558
559 FOR_EACH_EDGE (e, ei, bb->succs)
560 if (!(e->flags & (EDGE_COMPLEX | EDGE_FAKE)))
561 total ++;
562 if (total)
563 {
564 FOR_EACH_EDGE (e, ei, bb->succs)
565 if (!(e->flags & (EDGE_COMPLEX | EDGE_FAKE)))
566 e->probability = REG_BR_PROB_BASE / total;
567 else
568 e->probability = 0;
569 }
570 else
571 {
572 total += EDGE_COUNT (bb->succs);
573 FOR_EACH_EDGE (e, ei, bb->succs)
574 e->probability = REG_BR_PROB_BASE / total;
575 }
576 if (bb->index >= NUM_FIXED_BLOCKS
577 && block_ends_with_condjump_p (bb)
578 && EDGE_COUNT (bb->succs) >= 2)
579 num_branches++, num_never_executed;
580 }
581 }
582 counts_to_freqs ();
583
584 if (dump_file)
585 {
586 fprintf (dump_file, "%d branches\n", num_branches);
587 fprintf (dump_file, "%d branches never executed\n",
588 num_never_executed);
589 if (num_branches)
590 for (i = 0; i < 10; i++)
591 fprintf (dump_file, "%d%% branches in range %d-%d%%\n",
592 (hist_br_prob[i] + hist_br_prob[19-i]) * 100 / num_branches,
593 5 * i, 5 * i + 5);
594
595 total_num_branches += num_branches;
596 total_num_never_executed += num_never_executed;
597 for (i = 0; i < 20; i++)
598 total_hist_br_prob[i] += hist_br_prob[i];
599
600 fputc ('\n', dump_file);
601 fputc ('\n', dump_file);
602 }
603
604 free_aux_for_blocks ();
605 }
606
607 /* Load value histograms values whose description is stored in VALUES array
608 from .gcda file. */
609
610 static void
compute_value_histograms(histogram_values values)611 compute_value_histograms (histogram_values values)
612 {
613 unsigned i, j, t, any;
614 unsigned n_histogram_counters[GCOV_N_VALUE_COUNTERS];
615 gcov_type *histogram_counts[GCOV_N_VALUE_COUNTERS];
616 gcov_type *act_count[GCOV_N_VALUE_COUNTERS];
617 gcov_type *aact_count;
618
619 for (t = 0; t < GCOV_N_VALUE_COUNTERS; t++)
620 n_histogram_counters[t] = 0;
621
622 for (i = 0; i < VEC_length (histogram_value, values); i++)
623 {
624 histogram_value hist = VEC_index (histogram_value, values, i);
625 n_histogram_counters[(int) hist->type] += hist->n_counters;
626 }
627
628 any = 0;
629 for (t = 0; t < GCOV_N_VALUE_COUNTERS; t++)
630 {
631 if (!n_histogram_counters[t])
632 {
633 histogram_counts[t] = NULL;
634 continue;
635 }
636
637 histogram_counts[t] =
638 get_coverage_counts (COUNTER_FOR_HIST_TYPE (t),
639 n_histogram_counters[t], NULL);
640 if (histogram_counts[t])
641 any = 1;
642 act_count[t] = histogram_counts[t];
643 }
644 if (!any)
645 return;
646
647 for (i = 0; i < VEC_length (histogram_value, values); i++)
648 {
649 histogram_value hist = VEC_index (histogram_value, values, i);
650 tree stmt = hist->hvalue.stmt;
651 stmt_ann_t ann = get_stmt_ann (stmt);
652
653 t = (int) hist->type;
654
655 aact_count = act_count[t];
656 act_count[t] += hist->n_counters;
657
658 hist->hvalue.next = ann->histograms;
659 ann->histograms = hist;
660 hist->hvalue.counters = XNEWVEC (gcov_type, hist->n_counters);
661 for (j = 0; j < hist->n_counters; j++)
662 hist->hvalue.counters[j] = aact_count[j];
663 }
664
665 for (t = 0; t < GCOV_N_VALUE_COUNTERS; t++)
666 if (histogram_counts[t])
667 free (histogram_counts[t]);
668 }
669
670 /* The entry basic block will be moved around so that it has index=1,
671 there is nothing at index 0 and the exit is at n_basic_block. */
672 #define BB_TO_GCOV_INDEX(bb) ((bb)->index - 1)
673 /* When passed NULL as file_name, initialize.
674 When passed something else, output the necessary commands to change
675 line to LINE and offset to FILE_NAME. */
676 static void
output_location(char const * file_name,int line,gcov_position_t * offset,basic_block bb)677 output_location (char const *file_name, int line,
678 gcov_position_t *offset, basic_block bb)
679 {
680 static char const *prev_file_name;
681 static int prev_line;
682 bool name_differs, line_differs;
683
684 if (!file_name)
685 {
686 prev_file_name = NULL;
687 prev_line = -1;
688 return;
689 }
690
691 name_differs = !prev_file_name || strcmp (file_name, prev_file_name);
692 line_differs = prev_line != line;
693
694 if (name_differs || line_differs)
695 {
696 if (!*offset)
697 {
698 *offset = gcov_write_tag (GCOV_TAG_LINES);
699 gcov_write_unsigned (BB_TO_GCOV_INDEX (bb));
700 name_differs = line_differs=true;
701 }
702
703 /* If this is a new source file, then output the
704 file's name to the .bb file. */
705 if (name_differs)
706 {
707 prev_file_name = file_name;
708 gcov_write_unsigned (0);
709 gcov_write_string (prev_file_name);
710 }
711 if (line_differs)
712 {
713 gcov_write_unsigned (line);
714 prev_line = line;
715 }
716 }
717 }
718
719 /* Instrument and/or analyze program behavior based on program flow graph.
720 In either case, this function builds a flow graph for the function being
721 compiled. The flow graph is stored in BB_GRAPH.
722
723 When FLAG_PROFILE_ARCS is nonzero, this function instruments the edges in
724 the flow graph that are needed to reconstruct the dynamic behavior of the
725 flow graph.
726
727 When FLAG_BRANCH_PROBABILITIES is nonzero, this function reads auxiliary
728 information from a data file containing edge count information from previous
729 executions of the function being compiled. In this case, the flow graph is
730 annotated with actual execution counts, which are later propagated into the
731 rtl for optimization purposes.
732
733 Main entry point of this file. */
734
735 void
branch_prob(void)736 branch_prob (void)
737 {
738 basic_block bb;
739 unsigned i;
740 unsigned num_edges, ignored_edges;
741 unsigned num_instrumented;
742 struct edge_list *el;
743 histogram_values values = NULL;
744
745 total_num_times_called++;
746
747 flow_call_edges_add (NULL);
748 add_noreturn_fake_exit_edges ();
749
750 /* We can't handle cyclic regions constructed using abnormal edges.
751 To avoid these we replace every source of abnormal edge by a fake
752 edge from entry node and every destination by fake edge to exit.
753 This keeps graph acyclic and our calculation exact for all normal
754 edges except for exit and entrance ones.
755
756 We also add fake exit edges for each call and asm statement in the
757 basic, since it may not return. */
758
759 FOR_EACH_BB (bb)
760 {
761 int need_exit_edge = 0, need_entry_edge = 0;
762 int have_exit_edge = 0, have_entry_edge = 0;
763 edge e;
764 edge_iterator ei;
765
766 /* Functions returning multiple times are not handled by extra edges.
767 Instead we simply allow negative counts on edges from exit to the
768 block past call and corresponding probabilities. We can't go
769 with the extra edges because that would result in flowgraph that
770 needs to have fake edges outside the spanning tree. */
771
772 FOR_EACH_EDGE (e, ei, bb->succs)
773 {
774 block_stmt_iterator bsi;
775 tree last = NULL;
776
777 /* It may happen that there are compiler generated statements
778 without a locus at all. Go through the basic block from the
779 last to the first statement looking for a locus. */
780 for (bsi = bsi_last (bb); !bsi_end_p (bsi); bsi_prev (&bsi))
781 {
782 last = bsi_stmt (bsi);
783 if (EXPR_LOCUS (last))
784 break;
785 }
786
787 /* Edge with goto locus might get wrong coverage info unless
788 it is the only edge out of BB.
789 Don't do that when the locuses match, so
790 if (blah) goto something;
791 is not computed twice. */
792 if (last && EXPR_LOCUS (last)
793 && e->goto_locus
794 && !single_succ_p (bb)
795 #ifdef USE_MAPPED_LOCATION
796 && (LOCATION_FILE (e->goto_locus)
797 != LOCATION_FILE (EXPR_LOCATION (last))
798 || (LOCATION_LINE (e->goto_locus)
799 != LOCATION_LINE (EXPR_LOCATION (last)))))
800 #else
801 && (e->goto_locus->file != EXPR_LOCUS (last)->file
802 || (e->goto_locus->line != EXPR_LOCUS (last)->line)))
803 #endif
804 {
805 basic_block new = split_edge (e);
806 single_succ_edge (new)->goto_locus = e->goto_locus;
807 }
808 if ((e->flags & (EDGE_ABNORMAL | EDGE_ABNORMAL_CALL))
809 && e->dest != EXIT_BLOCK_PTR)
810 need_exit_edge = 1;
811 if (e->dest == EXIT_BLOCK_PTR)
812 have_exit_edge = 1;
813 }
814 FOR_EACH_EDGE (e, ei, bb->preds)
815 {
816 if ((e->flags & (EDGE_ABNORMAL | EDGE_ABNORMAL_CALL))
817 && e->src != ENTRY_BLOCK_PTR)
818 need_entry_edge = 1;
819 if (e->src == ENTRY_BLOCK_PTR)
820 have_entry_edge = 1;
821 }
822
823 if (need_exit_edge && !have_exit_edge)
824 {
825 if (dump_file)
826 fprintf (dump_file, "Adding fake exit edge to bb %i\n",
827 bb->index);
828 make_edge (bb, EXIT_BLOCK_PTR, EDGE_FAKE);
829 }
830 if (need_entry_edge && !have_entry_edge)
831 {
832 if (dump_file)
833 fprintf (dump_file, "Adding fake entry edge to bb %i\n",
834 bb->index);
835 make_edge (ENTRY_BLOCK_PTR, bb, EDGE_FAKE);
836 }
837 }
838
839 el = create_edge_list ();
840 num_edges = NUM_EDGES (el);
841 alloc_aux_for_edges (sizeof (struct edge_info));
842
843 /* The basic blocks are expected to be numbered sequentially. */
844 compact_blocks ();
845
846 ignored_edges = 0;
847 for (i = 0 ; i < num_edges ; i++)
848 {
849 edge e = INDEX_EDGE (el, i);
850 e->count = 0;
851
852 /* Mark edges we've replaced by fake edges above as ignored. */
853 if ((e->flags & (EDGE_ABNORMAL | EDGE_ABNORMAL_CALL))
854 && e->src != ENTRY_BLOCK_PTR && e->dest != EXIT_BLOCK_PTR)
855 {
856 EDGE_INFO (e)->ignore = 1;
857 ignored_edges++;
858 }
859 }
860
861 /* Create spanning tree from basic block graph, mark each edge that is
862 on the spanning tree. We insert as many abnormal and critical edges
863 as possible to minimize number of edge splits necessary. */
864
865 find_spanning_tree (el);
866
867 /* Fake edges that are not on the tree will not be instrumented, so
868 mark them ignored. */
869 for (num_instrumented = i = 0; i < num_edges; i++)
870 {
871 edge e = INDEX_EDGE (el, i);
872 struct edge_info *inf = EDGE_INFO (e);
873
874 if (inf->ignore || inf->on_tree)
875 /*NOP*/;
876 else if (e->flags & EDGE_FAKE)
877 {
878 inf->ignore = 1;
879 ignored_edges++;
880 }
881 else
882 num_instrumented++;
883 }
884
885 total_num_blocks += n_basic_blocks;
886 if (dump_file)
887 fprintf (dump_file, "%d basic blocks\n", n_basic_blocks);
888
889 total_num_edges += num_edges;
890 if (dump_file)
891 fprintf (dump_file, "%d edges\n", num_edges);
892
893 total_num_edges_ignored += ignored_edges;
894 if (dump_file)
895 fprintf (dump_file, "%d ignored edges\n", ignored_edges);
896
897 /* Write the data from which gcov can reconstruct the basic block
898 graph. */
899
900 /* Basic block flags */
901 if (coverage_begin_output ())
902 {
903 gcov_position_t offset;
904
905 offset = gcov_write_tag (GCOV_TAG_BLOCKS);
906 for (i = 0; i != (unsigned) (n_basic_blocks); i++)
907 gcov_write_unsigned (0);
908 gcov_write_length (offset);
909 }
910
911 /* Keep all basic block indexes nonnegative in the gcov output.
912 Index 0 is used for entry block, last index is for exit block.
913 */
914 ENTRY_BLOCK_PTR->index = 1;
915 EXIT_BLOCK_PTR->index = last_basic_block;
916
917 /* Arcs */
918 if (coverage_begin_output ())
919 {
920 gcov_position_t offset;
921
922 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
923 {
924 edge e;
925 edge_iterator ei;
926
927 offset = gcov_write_tag (GCOV_TAG_ARCS);
928 gcov_write_unsigned (BB_TO_GCOV_INDEX (bb));
929
930 FOR_EACH_EDGE (e, ei, bb->succs)
931 {
932 struct edge_info *i = EDGE_INFO (e);
933 if (!i->ignore)
934 {
935 unsigned flag_bits = 0;
936
937 if (i->on_tree)
938 flag_bits |= GCOV_ARC_ON_TREE;
939 if (e->flags & EDGE_FAKE)
940 flag_bits |= GCOV_ARC_FAKE;
941 if (e->flags & EDGE_FALLTHRU)
942 flag_bits |= GCOV_ARC_FALLTHROUGH;
943 /* On trees we don't have fallthru flags, but we can
944 recompute them from CFG shape. */
945 if (e->flags & (EDGE_TRUE_VALUE | EDGE_FALSE_VALUE)
946 && e->src->next_bb == e->dest)
947 flag_bits |= GCOV_ARC_FALLTHROUGH;
948
949 gcov_write_unsigned (BB_TO_GCOV_INDEX (e->dest));
950 gcov_write_unsigned (flag_bits);
951 }
952 }
953
954 gcov_write_length (offset);
955 }
956 }
957
958 /* Line numbers. */
959 if (coverage_begin_output ())
960 {
961 gcov_position_t offset;
962
963 /* Initialize the output. */
964 output_location (NULL, 0, NULL, NULL);
965
966 FOR_EACH_BB (bb)
967 {
968 block_stmt_iterator bsi;
969
970 offset = 0;
971
972 if (bb == ENTRY_BLOCK_PTR->next_bb)
973 {
974 expanded_location curr_location =
975 expand_location (DECL_SOURCE_LOCATION (current_function_decl));
976 output_location (curr_location.file, curr_location.line,
977 &offset, bb);
978 }
979
980 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
981 {
982 tree stmt = bsi_stmt (bsi);
983 if (EXPR_HAS_LOCATION (stmt))
984 output_location (EXPR_FILENAME (stmt), EXPR_LINENO (stmt),
985 &offset, bb);
986 }
987
988 /* Notice GOTO expressions we eliminated while constructing the
989 CFG. */
990 if (single_succ_p (bb) && single_succ_edge (bb)->goto_locus)
991 {
992 /* ??? source_locus type is marked deprecated in input.h. */
993 source_locus curr_location = single_succ_edge (bb)->goto_locus;
994 /* ??? The FILE/LINE API is inconsistent for these cases. */
995 #ifdef USE_MAPPED_LOCATION
996 output_location (LOCATION_FILE (curr_location),
997 LOCATION_LINE (curr_location), &offset, bb);
998 #else
999 output_location (curr_location->file, curr_location->line,
1000 &offset, bb);
1001 #endif
1002 }
1003
1004 if (offset)
1005 {
1006 /* A file of NULL indicates the end of run. */
1007 gcov_write_unsigned (0);
1008 gcov_write_string (NULL);
1009 gcov_write_length (offset);
1010 }
1011 }
1012 }
1013
1014 ENTRY_BLOCK_PTR->index = ENTRY_BLOCK;
1015 EXIT_BLOCK_PTR->index = EXIT_BLOCK;
1016 #undef BB_TO_GCOV_INDEX
1017
1018 if (flag_profile_values)
1019 find_values_to_profile (&values);
1020
1021 if (flag_branch_probabilities)
1022 {
1023 compute_branch_probabilities ();
1024 if (flag_profile_values)
1025 compute_value_histograms (values);
1026 }
1027
1028 remove_fake_edges ();
1029
1030 /* For each edge not on the spanning tree, add counting code. */
1031 if (profile_arc_flag
1032 && coverage_counter_alloc (GCOV_COUNTER_ARCS, num_instrumented))
1033 {
1034 unsigned n_instrumented;
1035
1036 profile_hooks->init_edge_profiler ();
1037
1038 n_instrumented = instrument_edges (el);
1039
1040 gcc_assert (n_instrumented == num_instrumented);
1041
1042 if (flag_profile_values)
1043 instrument_values (values);
1044
1045 /* Commit changes done by instrumentation. */
1046 bsi_commit_edge_inserts ();
1047 }
1048
1049 free_aux_for_edges ();
1050
1051 VEC_free (histogram_value, heap, values);
1052 free_edge_list (el);
1053 if (flag_branch_probabilities)
1054 profile_status = PROFILE_READ;
1055 coverage_end_function ();
1056 }
1057
1058 /* Union find algorithm implementation for the basic blocks using
1059 aux fields. */
1060
1061 static basic_block
find_group(basic_block bb)1062 find_group (basic_block bb)
1063 {
1064 basic_block group = bb, bb1;
1065
1066 while ((basic_block) group->aux != group)
1067 group = (basic_block) group->aux;
1068
1069 /* Compress path. */
1070 while ((basic_block) bb->aux != group)
1071 {
1072 bb1 = (basic_block) bb->aux;
1073 bb->aux = (void *) group;
1074 bb = bb1;
1075 }
1076 return group;
1077 }
1078
1079 static void
union_groups(basic_block bb1,basic_block bb2)1080 union_groups (basic_block bb1, basic_block bb2)
1081 {
1082 basic_block bb1g = find_group (bb1);
1083 basic_block bb2g = find_group (bb2);
1084
1085 /* ??? I don't have a place for the rank field. OK. Lets go w/o it,
1086 this code is unlikely going to be performance problem anyway. */
1087 gcc_assert (bb1g != bb2g);
1088
1089 bb1g->aux = bb2g;
1090 }
1091
1092 /* This function searches all of the edges in the program flow graph, and puts
1093 as many bad edges as possible onto the spanning tree. Bad edges include
1094 abnormals edges, which can't be instrumented at the moment. Since it is
1095 possible for fake edges to form a cycle, we will have to develop some
1096 better way in the future. Also put critical edges to the tree, since they
1097 are more expensive to instrument. */
1098
1099 static void
find_spanning_tree(struct edge_list * el)1100 find_spanning_tree (struct edge_list *el)
1101 {
1102 int i;
1103 int num_edges = NUM_EDGES (el);
1104 basic_block bb;
1105
1106 /* We use aux field for standard union-find algorithm. */
1107 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
1108 bb->aux = bb;
1109
1110 /* Add fake edge exit to entry we can't instrument. */
1111 union_groups (EXIT_BLOCK_PTR, ENTRY_BLOCK_PTR);
1112
1113 /* First add all abnormal edges to the tree unless they form a cycle. Also
1114 add all edges to EXIT_BLOCK_PTR to avoid inserting profiling code behind
1115 setting return value from function. */
1116 for (i = 0; i < num_edges; i++)
1117 {
1118 edge e = INDEX_EDGE (el, i);
1119 if (((e->flags & (EDGE_ABNORMAL | EDGE_ABNORMAL_CALL | EDGE_FAKE))
1120 || e->dest == EXIT_BLOCK_PTR)
1121 && !EDGE_INFO (e)->ignore
1122 && (find_group (e->src) != find_group (e->dest)))
1123 {
1124 if (dump_file)
1125 fprintf (dump_file, "Abnormal edge %d to %d put to tree\n",
1126 e->src->index, e->dest->index);
1127 EDGE_INFO (e)->on_tree = 1;
1128 union_groups (e->src, e->dest);
1129 }
1130 }
1131
1132 /* Now insert all critical edges to the tree unless they form a cycle. */
1133 for (i = 0; i < num_edges; i++)
1134 {
1135 edge e = INDEX_EDGE (el, i);
1136 if (EDGE_CRITICAL_P (e) && !EDGE_INFO (e)->ignore
1137 && find_group (e->src) != find_group (e->dest))
1138 {
1139 if (dump_file)
1140 fprintf (dump_file, "Critical edge %d to %d put to tree\n",
1141 e->src->index, e->dest->index);
1142 EDGE_INFO (e)->on_tree = 1;
1143 union_groups (e->src, e->dest);
1144 }
1145 }
1146
1147 /* And now the rest. */
1148 for (i = 0; i < num_edges; i++)
1149 {
1150 edge e = INDEX_EDGE (el, i);
1151 if (!EDGE_INFO (e)->ignore
1152 && find_group (e->src) != find_group (e->dest))
1153 {
1154 if (dump_file)
1155 fprintf (dump_file, "Normal edge %d to %d put to tree\n",
1156 e->src->index, e->dest->index);
1157 EDGE_INFO (e)->on_tree = 1;
1158 union_groups (e->src, e->dest);
1159 }
1160 }
1161
1162 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
1163 bb->aux = NULL;
1164 }
1165
1166 /* Perform file-level initialization for branch-prob processing. */
1167
1168 void
init_branch_prob(void)1169 init_branch_prob (void)
1170 {
1171 int i;
1172
1173 total_num_blocks = 0;
1174 total_num_edges = 0;
1175 total_num_edges_ignored = 0;
1176 total_num_edges_instrumented = 0;
1177 total_num_blocks_created = 0;
1178 total_num_passes = 0;
1179 total_num_times_called = 0;
1180 total_num_branches = 0;
1181 total_num_never_executed = 0;
1182 for (i = 0; i < 20; i++)
1183 total_hist_br_prob[i] = 0;
1184 }
1185
1186 /* Performs file-level cleanup after branch-prob processing
1187 is completed. */
1188
1189 void
end_branch_prob(void)1190 end_branch_prob (void)
1191 {
1192 if (dump_file)
1193 {
1194 fprintf (dump_file, "\n");
1195 fprintf (dump_file, "Total number of blocks: %d\n",
1196 total_num_blocks);
1197 fprintf (dump_file, "Total number of edges: %d\n", total_num_edges);
1198 fprintf (dump_file, "Total number of ignored edges: %d\n",
1199 total_num_edges_ignored);
1200 fprintf (dump_file, "Total number of instrumented edges: %d\n",
1201 total_num_edges_instrumented);
1202 fprintf (dump_file, "Total number of blocks created: %d\n",
1203 total_num_blocks_created);
1204 fprintf (dump_file, "Total number of graph solution passes: %d\n",
1205 total_num_passes);
1206 if (total_num_times_called != 0)
1207 fprintf (dump_file, "Average number of graph solution passes: %d\n",
1208 (total_num_passes + (total_num_times_called >> 1))
1209 / total_num_times_called);
1210 fprintf (dump_file, "Total number of branches: %d\n",
1211 total_num_branches);
1212 fprintf (dump_file, "Total number of branches never executed: %d\n",
1213 total_num_never_executed);
1214 if (total_num_branches)
1215 {
1216 int i;
1217
1218 for (i = 0; i < 10; i++)
1219 fprintf (dump_file, "%d%% branches in range %d-%d%%\n",
1220 (total_hist_br_prob[i] + total_hist_br_prob[19-i]) * 100
1221 / total_num_branches, 5*i, 5*i+5);
1222 }
1223 }
1224 }
1225
1226 /* Set up hooks to enable tree-based profiling. */
1227
1228 void
tree_register_profile_hooks(void)1229 tree_register_profile_hooks (void)
1230 {
1231 gcc_assert (ir_type ());
1232 profile_hooks = &tree_profile_hooks;
1233 }
1234
1235