2010-11-27 François Dumont <francois.cppdevs@free.fr>
[official-gcc.git] / gcc / profile.c
blobb8a43de3463ec32452a196fe12c1093532fcfed2
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, 2007, 2008, 2009
4 Free Software Foundation, Inc.
5 Contributed by James E. Wilson, UC Berkeley/Cygnus Support;
6 based on some ideas from Dain Samples of UC Berkeley.
7 Further mangling by Bob Manson, Cygnus Support.
9 This file is part of GCC.
11 GCC is free software; you can redistribute it and/or modify it under
12 the terms of the GNU General Public License as published by the Free
13 Software Foundation; either version 3, or (at your option) any later
14 version.
16 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
17 WARRANTY; without even the implied warranty of MERCHANTABILITY or
18 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
19 for more details.
21 You should have received a copy of the GNU General Public License
22 along with GCC; see the file COPYING3. If not see
23 <http://www.gnu.org/licenses/>. */
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.
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. */
46 /* ??? Register allocation should use basic block execution counts to
47 give preference to the most commonly executed blocks. */
49 /* ??? Should calculate branch probabilities before instrumenting code, since
50 then we can use arc counts to help decide which arcs to instrument. */
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 "basic-block.h"
63 #include "diagnostic-core.h"
64 #include "toplev.h"
65 #include "coverage.h"
66 #include "value-prof.h"
67 #include "tree.h"
68 #include "cfghooks.h"
69 #include "tree-flow.h"
70 #include "timevar.h"
71 #include "cfgloop.h"
72 #include "tree-pass.h"
74 #include "profile.h"
76 /* Hooks for profiling. */
77 static struct profile_hooks* profile_hooks;
79 struct bb_info {
80 unsigned int count_valid : 1;
82 /* Number of successor and predecessor edges. */
83 gcov_type succ_count;
84 gcov_type pred_count;
87 #define BB_INFO(b) ((struct bb_info *) (b)->aux)
90 /* Counter summary from the last set of coverage counts read. */
92 const struct gcov_ctr_summary *profile_info;
94 /* Collect statistics on the performance of this pass for the entire source
95 file. */
97 static int total_num_blocks;
98 static int total_num_edges;
99 static int total_num_edges_ignored;
100 static int total_num_edges_instrumented;
101 static int total_num_blocks_created;
102 static int total_num_passes;
103 static int total_num_times_called;
104 static int total_hist_br_prob[20];
105 static int total_num_branches;
107 /* Forward declarations. */
108 static void find_spanning_tree (struct edge_list *);
109 static unsigned instrument_edges (struct edge_list *);
110 static void instrument_values (histogram_values);
111 static void compute_branch_probabilities (void);
112 static void compute_value_histograms (histogram_values);
113 static gcov_type * get_exec_counts (void);
114 static basic_block find_group (basic_block);
115 static void union_groups (basic_block, basic_block);
117 /* Add edge instrumentation code to the entire insn chain.
119 F is the first insn of the chain.
120 NUM_BLOCKS is the number of basic blocks found in F. */
122 static unsigned
123 instrument_edges (struct edge_list *el)
125 unsigned num_instr_edges = 0;
126 int num_edges = NUM_EDGES (el);
127 basic_block bb;
129 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
131 edge e;
132 edge_iterator ei;
134 FOR_EACH_EDGE (e, ei, bb->succs)
136 struct edge_info *inf = EDGE_INFO (e);
138 if (!inf->ignore && !inf->on_tree)
140 gcc_assert (!(e->flags & EDGE_ABNORMAL));
141 if (dump_file)
142 fprintf (dump_file, "Edge %d to %d instrumented%s\n",
143 e->src->index, e->dest->index,
144 EDGE_CRITICAL_P (e) ? " (and split)" : "");
145 (profile_hooks->gen_edge_profiler) (num_instr_edges++, e);
150 total_num_blocks_created += num_edges;
151 if (dump_file)
152 fprintf (dump_file, "%d edges instrumented\n", num_instr_edges);
153 return num_instr_edges;
156 /* Add code to measure histograms for values in list VALUES. */
157 static void
158 instrument_values (histogram_values values)
160 unsigned i, t;
162 /* Emit code to generate the histograms before the insns. */
164 for (i = 0; i < VEC_length (histogram_value, values); i++)
166 histogram_value hist = VEC_index (histogram_value, values, i);
167 switch (hist->type)
169 case HIST_TYPE_INTERVAL:
170 t = GCOV_COUNTER_V_INTERVAL;
171 break;
173 case HIST_TYPE_POW2:
174 t = GCOV_COUNTER_V_POW2;
175 break;
177 case HIST_TYPE_SINGLE_VALUE:
178 t = GCOV_COUNTER_V_SINGLE;
179 break;
181 case HIST_TYPE_CONST_DELTA:
182 t = GCOV_COUNTER_V_DELTA;
183 break;
185 case HIST_TYPE_INDIR_CALL:
186 t = GCOV_COUNTER_V_INDIR;
187 break;
189 case HIST_TYPE_AVERAGE:
190 t = GCOV_COUNTER_AVERAGE;
191 break;
193 case HIST_TYPE_IOR:
194 t = GCOV_COUNTER_IOR;
195 break;
197 default:
198 gcc_unreachable ();
200 if (!coverage_counter_alloc (t, hist->n_counters))
201 continue;
203 switch (hist->type)
205 case HIST_TYPE_INTERVAL:
206 (profile_hooks->gen_interval_profiler) (hist, t, 0);
207 break;
209 case HIST_TYPE_POW2:
210 (profile_hooks->gen_pow2_profiler) (hist, t, 0);
211 break;
213 case HIST_TYPE_SINGLE_VALUE:
214 (profile_hooks->gen_one_value_profiler) (hist, t, 0);
215 break;
217 case HIST_TYPE_CONST_DELTA:
218 (profile_hooks->gen_const_delta_profiler) (hist, t, 0);
219 break;
221 case HIST_TYPE_INDIR_CALL:
222 (profile_hooks->gen_ic_profiler) (hist, t, 0);
223 break;
225 case HIST_TYPE_AVERAGE:
226 (profile_hooks->gen_average_profiler) (hist, t, 0);
227 break;
229 case HIST_TYPE_IOR:
230 (profile_hooks->gen_ior_profiler) (hist, t, 0);
231 break;
233 default:
234 gcc_unreachable ();
240 /* Computes hybrid profile for all matching entries in da_file. */
242 static gcov_type *
243 get_exec_counts (void)
245 unsigned num_edges = 0;
246 basic_block bb;
247 gcov_type *counts;
249 /* Count the edges to be (possibly) instrumented. */
250 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
252 edge e;
253 edge_iterator ei;
255 FOR_EACH_EDGE (e, ei, bb->succs)
256 if (!EDGE_INFO (e)->ignore && !EDGE_INFO (e)->on_tree)
257 num_edges++;
260 counts = get_coverage_counts (GCOV_COUNTER_ARCS, num_edges, &profile_info);
261 if (!counts)
262 return NULL;
264 if (dump_file && profile_info)
265 fprintf(dump_file, "Merged %u profiles with maximal count %u.\n",
266 profile_info->runs, (unsigned) profile_info->sum_max);
268 return counts;
272 static bool
273 is_edge_inconsistent (VEC(edge,gc) *edges)
275 edge e;
276 edge_iterator ei;
277 FOR_EACH_EDGE (e, ei, edges)
279 if (!EDGE_INFO (e)->ignore)
281 if (e->count < 0
282 && (!(e->flags & EDGE_FAKE)
283 || !block_ends_with_call_p (e->src)))
285 if (dump_file)
287 fprintf (dump_file,
288 "Edge %i->%i is inconsistent, count"HOST_WIDEST_INT_PRINT_DEC,
289 e->src->index, e->dest->index, e->count);
290 dump_bb (e->src, dump_file, 0);
291 dump_bb (e->dest, dump_file, 0);
293 return true;
297 return false;
300 static void
301 correct_negative_edge_counts (void)
303 basic_block bb;
304 edge e;
305 edge_iterator ei;
307 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
309 FOR_EACH_EDGE (e, ei, bb->succs)
311 if (e->count < 0)
312 e->count = 0;
317 /* Check consistency.
318 Return true if inconsistency is found. */
319 static bool
320 is_inconsistent (void)
322 basic_block bb;
323 bool inconsistent = false;
324 FOR_EACH_BB (bb)
326 inconsistent |= is_edge_inconsistent (bb->preds);
327 if (!dump_file && inconsistent)
328 return true;
329 inconsistent |= is_edge_inconsistent (bb->succs);
330 if (!dump_file && inconsistent)
331 return true;
332 if (bb->count < 0)
334 if (dump_file)
336 fprintf (dump_file, "BB %i count is negative "
337 HOST_WIDEST_INT_PRINT_DEC,
338 bb->index,
339 bb->count);
340 dump_bb (bb, dump_file, 0);
342 inconsistent = true;
344 if (bb->count != sum_edge_counts (bb->preds))
346 if (dump_file)
348 fprintf (dump_file, "BB %i count does not match sum of incoming edges "
349 HOST_WIDEST_INT_PRINT_DEC" should be " HOST_WIDEST_INT_PRINT_DEC,
350 bb->index,
351 bb->count,
352 sum_edge_counts (bb->preds));
353 dump_bb (bb, dump_file, 0);
355 inconsistent = true;
357 if (bb->count != sum_edge_counts (bb->succs) &&
358 ! (find_edge (bb, EXIT_BLOCK_PTR) != NULL && block_ends_with_call_p (bb)))
360 if (dump_file)
362 fprintf (dump_file, "BB %i count does not match sum of outgoing edges "
363 HOST_WIDEST_INT_PRINT_DEC" should be " HOST_WIDEST_INT_PRINT_DEC,
364 bb->index,
365 bb->count,
366 sum_edge_counts (bb->succs));
367 dump_bb (bb, dump_file, 0);
369 inconsistent = true;
371 if (!dump_file && inconsistent)
372 return true;
375 return inconsistent;
378 /* Set each basic block count to the sum of its outgoing edge counts */
379 static void
380 set_bb_counts (void)
382 basic_block bb;
383 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
385 bb->count = sum_edge_counts (bb->succs);
386 gcc_assert (bb->count >= 0);
390 /* Reads profile data and returns total number of edge counts read */
391 static int
392 read_profile_edge_counts (gcov_type *exec_counts)
394 basic_block bb;
395 int num_edges = 0;
396 int exec_counts_pos = 0;
397 /* For each edge not on the spanning tree, set its execution count from
398 the .da file. */
399 /* The first count in the .da file is the number of times that the function
400 was entered. This is the exec_count for block zero. */
402 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
404 edge e;
405 edge_iterator ei;
407 FOR_EACH_EDGE (e, ei, bb->succs)
408 if (!EDGE_INFO (e)->ignore && !EDGE_INFO (e)->on_tree)
410 num_edges++;
411 if (exec_counts)
413 e->count = exec_counts[exec_counts_pos++];
414 if (e->count > profile_info->sum_max)
416 error ("corrupted profile info: edge from %i to %i exceeds maximal count",
417 bb->index, e->dest->index);
420 else
421 e->count = 0;
423 EDGE_INFO (e)->count_valid = 1;
424 BB_INFO (bb)->succ_count--;
425 BB_INFO (e->dest)->pred_count--;
426 if (dump_file)
428 fprintf (dump_file, "\nRead edge from %i to %i, count:",
429 bb->index, e->dest->index);
430 fprintf (dump_file, HOST_WIDEST_INT_PRINT_DEC,
431 (HOST_WIDEST_INT) e->count);
436 return num_edges;
439 /* Compute the branch probabilities for the various branches.
440 Annotate them accordingly. */
442 static void
443 compute_branch_probabilities (void)
445 basic_block bb;
446 int i;
447 int num_edges = 0;
448 int changes;
449 int passes;
450 int hist_br_prob[20];
451 int num_branches;
452 gcov_type *exec_counts = get_exec_counts ();
453 int inconsistent = 0;
455 /* Very simple sanity checks so we catch bugs in our profiling code. */
456 if (!profile_info)
457 return;
458 if (profile_info->run_max * profile_info->runs < profile_info->sum_max)
460 error ("corrupted profile info: run_max * runs < sum_max");
461 exec_counts = NULL;
464 if (profile_info->sum_all < profile_info->sum_max)
466 error ("corrupted profile info: sum_all is smaller than sum_max");
467 exec_counts = NULL;
470 /* Attach extra info block to each bb. */
471 alloc_aux_for_blocks (sizeof (struct bb_info));
472 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
474 edge e;
475 edge_iterator ei;
477 FOR_EACH_EDGE (e, ei, bb->succs)
478 if (!EDGE_INFO (e)->ignore)
479 BB_INFO (bb)->succ_count++;
480 FOR_EACH_EDGE (e, ei, bb->preds)
481 if (!EDGE_INFO (e)->ignore)
482 BB_INFO (bb)->pred_count++;
485 /* Avoid predicting entry on exit nodes. */
486 BB_INFO (EXIT_BLOCK_PTR)->succ_count = 2;
487 BB_INFO (ENTRY_BLOCK_PTR)->pred_count = 2;
489 num_edges = read_profile_edge_counts (exec_counts);
491 if (dump_file)
492 fprintf (dump_file, "\n%d edge counts read\n", num_edges);
494 /* For every block in the file,
495 - if every exit/entrance edge has a known count, then set the block count
496 - if the block count is known, and every exit/entrance edge but one has
497 a known execution count, then set the count of the remaining edge
499 As edge counts are set, decrement the succ/pred count, but don't delete
500 the edge, that way we can easily tell when all edges are known, or only
501 one edge is unknown. */
503 /* The order that the basic blocks are iterated through is important.
504 Since the code that finds spanning trees starts with block 0, low numbered
505 edges are put on the spanning tree in preference to high numbered edges.
506 Hence, most instrumented edges are at the end. Graph solving works much
507 faster if we propagate numbers from the end to the start.
509 This takes an average of slightly more than 3 passes. */
511 changes = 1;
512 passes = 0;
513 while (changes)
515 passes++;
516 changes = 0;
517 FOR_BB_BETWEEN (bb, EXIT_BLOCK_PTR, NULL, prev_bb)
519 struct bb_info *bi = BB_INFO (bb);
520 if (! bi->count_valid)
522 if (bi->succ_count == 0)
524 edge e;
525 edge_iterator ei;
526 gcov_type total = 0;
528 FOR_EACH_EDGE (e, ei, bb->succs)
529 total += e->count;
530 bb->count = total;
531 bi->count_valid = 1;
532 changes = 1;
534 else if (bi->pred_count == 0)
536 edge e;
537 edge_iterator ei;
538 gcov_type total = 0;
540 FOR_EACH_EDGE (e, ei, bb->preds)
541 total += e->count;
542 bb->count = total;
543 bi->count_valid = 1;
544 changes = 1;
547 if (bi->count_valid)
549 if (bi->succ_count == 1)
551 edge e;
552 edge_iterator ei;
553 gcov_type total = 0;
555 /* One of the counts will be invalid, but it is zero,
556 so adding it in also doesn't hurt. */
557 FOR_EACH_EDGE (e, ei, bb->succs)
558 total += e->count;
560 /* Search for the invalid edge, and set its count. */
561 FOR_EACH_EDGE (e, ei, bb->succs)
562 if (! EDGE_INFO (e)->count_valid && ! EDGE_INFO (e)->ignore)
563 break;
565 /* Calculate count for remaining edge by conservation. */
566 total = bb->count - total;
568 gcc_assert (e);
569 EDGE_INFO (e)->count_valid = 1;
570 e->count = total;
571 bi->succ_count--;
573 BB_INFO (e->dest)->pred_count--;
574 changes = 1;
576 if (bi->pred_count == 1)
578 edge e;
579 edge_iterator ei;
580 gcov_type total = 0;
582 /* One of the counts will be invalid, but it is zero,
583 so adding it in also doesn't hurt. */
584 FOR_EACH_EDGE (e, ei, bb->preds)
585 total += e->count;
587 /* Search for the invalid edge, and set its count. */
588 FOR_EACH_EDGE (e, ei, bb->preds)
589 if (!EDGE_INFO (e)->count_valid && !EDGE_INFO (e)->ignore)
590 break;
592 /* Calculate count for remaining edge by conservation. */
593 total = bb->count - total + e->count;
595 gcc_assert (e);
596 EDGE_INFO (e)->count_valid = 1;
597 e->count = total;
598 bi->pred_count--;
600 BB_INFO (e->src)->succ_count--;
601 changes = 1;
606 if (dump_file)
607 dump_flow_info (dump_file, dump_flags);
609 total_num_passes += passes;
610 if (dump_file)
611 fprintf (dump_file, "Graph solving took %d passes.\n\n", passes);
613 /* If the graph has been correctly solved, every block will have a
614 succ and pred count of zero. */
615 FOR_EACH_BB (bb)
617 gcc_assert (!BB_INFO (bb)->succ_count && !BB_INFO (bb)->pred_count);
620 /* Check for inconsistent basic block counts */
621 inconsistent = is_inconsistent ();
623 if (inconsistent)
625 if (flag_profile_correction)
627 /* Inconsistency detected. Make it flow-consistent. */
628 static int informed = 0;
629 if (informed == 0)
631 informed = 1;
632 inform (input_location, "correcting inconsistent profile data");
634 correct_negative_edge_counts ();
635 /* Set bb counts to the sum of the outgoing edge counts */
636 set_bb_counts ();
637 if (dump_file)
638 fprintf (dump_file, "\nCalling mcf_smooth_cfg\n");
639 mcf_smooth_cfg ();
641 else
642 error ("corrupted profile info: profile data is not flow-consistent");
645 /* For every edge, calculate its branch probability and add a reg_note
646 to the branch insn to indicate this. */
648 for (i = 0; i < 20; i++)
649 hist_br_prob[i] = 0;
650 num_branches = 0;
652 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
654 edge e;
655 edge_iterator ei;
657 if (bb->count < 0)
659 error ("corrupted profile info: number of iterations for basic block %d thought to be %i",
660 bb->index, (int)bb->count);
661 bb->count = 0;
663 FOR_EACH_EDGE (e, ei, bb->succs)
665 /* Function may return twice in the cased the called function is
666 setjmp or calls fork, but we can't represent this by extra
667 edge from the entry, since extra edge from the exit is
668 already present. We get negative frequency from the entry
669 point. */
670 if ((e->count < 0
671 && e->dest == EXIT_BLOCK_PTR)
672 || (e->count > bb->count
673 && e->dest != EXIT_BLOCK_PTR))
675 if (block_ends_with_call_p (bb))
676 e->count = e->count < 0 ? 0 : bb->count;
678 if (e->count < 0 || e->count > bb->count)
680 error ("corrupted profile info: number of executions for edge %d-%d thought to be %i",
681 e->src->index, e->dest->index,
682 (int)e->count);
683 e->count = bb->count / 2;
686 if (bb->count)
688 FOR_EACH_EDGE (e, ei, bb->succs)
689 e->probability = (e->count * REG_BR_PROB_BASE + bb->count / 2) / bb->count;
690 if (bb->index >= NUM_FIXED_BLOCKS
691 && block_ends_with_condjump_p (bb)
692 && EDGE_COUNT (bb->succs) >= 2)
694 int prob;
695 edge e;
696 int index;
698 /* Find the branch edge. It is possible that we do have fake
699 edges here. */
700 FOR_EACH_EDGE (e, ei, bb->succs)
701 if (!(e->flags & (EDGE_FAKE | EDGE_FALLTHRU)))
702 break;
704 prob = e->probability;
705 index = prob * 20 / REG_BR_PROB_BASE;
707 if (index == 20)
708 index = 19;
709 hist_br_prob[index]++;
711 num_branches++;
714 /* As a last resort, distribute the probabilities evenly.
715 Use simple heuristics that if there are normal edges,
716 give all abnormals frequency of 0, otherwise distribute the
717 frequency over abnormals (this is the case of noreturn
718 calls). */
719 else if (profile_status == PROFILE_ABSENT)
721 int total = 0;
723 FOR_EACH_EDGE (e, ei, bb->succs)
724 if (!(e->flags & (EDGE_COMPLEX | EDGE_FAKE)))
725 total ++;
726 if (total)
728 FOR_EACH_EDGE (e, ei, bb->succs)
729 if (!(e->flags & (EDGE_COMPLEX | EDGE_FAKE)))
730 e->probability = REG_BR_PROB_BASE / total;
731 else
732 e->probability = 0;
734 else
736 total += EDGE_COUNT (bb->succs);
737 FOR_EACH_EDGE (e, ei, bb->succs)
738 e->probability = REG_BR_PROB_BASE / total;
740 if (bb->index >= NUM_FIXED_BLOCKS
741 && block_ends_with_condjump_p (bb)
742 && EDGE_COUNT (bb->succs) >= 2)
743 num_branches++;
746 counts_to_freqs ();
747 profile_status = PROFILE_READ;
749 if (dump_file)
751 fprintf (dump_file, "%d branches\n", num_branches);
752 if (num_branches)
753 for (i = 0; i < 10; i++)
754 fprintf (dump_file, "%d%% branches in range %d-%d%%\n",
755 (hist_br_prob[i] + hist_br_prob[19-i]) * 100 / num_branches,
756 5 * i, 5 * i + 5);
758 total_num_branches += num_branches;
759 for (i = 0; i < 20; i++)
760 total_hist_br_prob[i] += hist_br_prob[i];
762 fputc ('\n', dump_file);
763 fputc ('\n', dump_file);
766 free_aux_for_blocks ();
769 /* Load value histograms values whose description is stored in VALUES array
770 from .gcda file. */
772 static void
773 compute_value_histograms (histogram_values values)
775 unsigned i, j, t, any;
776 unsigned n_histogram_counters[GCOV_N_VALUE_COUNTERS];
777 gcov_type *histogram_counts[GCOV_N_VALUE_COUNTERS];
778 gcov_type *act_count[GCOV_N_VALUE_COUNTERS];
779 gcov_type *aact_count;
781 for (t = 0; t < GCOV_N_VALUE_COUNTERS; t++)
782 n_histogram_counters[t] = 0;
784 for (i = 0; i < VEC_length (histogram_value, values); i++)
786 histogram_value hist = VEC_index (histogram_value, values, i);
787 n_histogram_counters[(int) hist->type] += hist->n_counters;
790 any = 0;
791 for (t = 0; t < GCOV_N_VALUE_COUNTERS; t++)
793 if (!n_histogram_counters[t])
795 histogram_counts[t] = NULL;
796 continue;
799 histogram_counts[t] =
800 get_coverage_counts (COUNTER_FOR_HIST_TYPE (t),
801 n_histogram_counters[t], NULL);
802 if (histogram_counts[t])
803 any = 1;
804 act_count[t] = histogram_counts[t];
806 if (!any)
807 return;
809 for (i = 0; i < VEC_length (histogram_value, values); i++)
811 histogram_value hist = VEC_index (histogram_value, values, i);
812 gimple stmt = hist->hvalue.stmt;
814 t = (int) hist->type;
816 aact_count = act_count[t];
817 act_count[t] += hist->n_counters;
819 gimple_add_histogram_value (cfun, stmt, hist);
820 hist->hvalue.counters = XNEWVEC (gcov_type, hist->n_counters);
821 for (j = 0; j < hist->n_counters; j++)
822 hist->hvalue.counters[j] = aact_count[j];
825 for (t = 0; t < GCOV_N_VALUE_COUNTERS; t++)
826 if (histogram_counts[t])
827 free (histogram_counts[t]);
830 /* The entry basic block will be moved around so that it has index=1,
831 there is nothing at index 0 and the exit is at n_basic_block. */
832 #define BB_TO_GCOV_INDEX(bb) ((bb)->index - 1)
833 /* When passed NULL as file_name, initialize.
834 When passed something else, output the necessary commands to change
835 line to LINE and offset to FILE_NAME. */
836 static void
837 output_location (char const *file_name, int line,
838 gcov_position_t *offset, basic_block bb)
840 static char const *prev_file_name;
841 static int prev_line;
842 bool name_differs, line_differs;
844 if (!file_name)
846 prev_file_name = NULL;
847 prev_line = -1;
848 return;
851 name_differs = !prev_file_name || strcmp (file_name, prev_file_name);
852 line_differs = prev_line != line;
854 if (name_differs || line_differs)
856 if (!*offset)
858 *offset = gcov_write_tag (GCOV_TAG_LINES);
859 gcov_write_unsigned (BB_TO_GCOV_INDEX (bb));
860 name_differs = line_differs=true;
863 /* If this is a new source file, then output the
864 file's name to the .bb file. */
865 if (name_differs)
867 prev_file_name = file_name;
868 gcov_write_unsigned (0);
869 gcov_write_string (prev_file_name);
871 if (line_differs)
873 gcov_write_unsigned (line);
874 prev_line = line;
879 /* Instrument and/or analyze program behavior based on program flow graph.
880 In either case, this function builds a flow graph for the function being
881 compiled. The flow graph is stored in BB_GRAPH.
883 When FLAG_PROFILE_ARCS is nonzero, this function instruments the edges in
884 the flow graph that are needed to reconstruct the dynamic behavior of the
885 flow graph.
887 When FLAG_BRANCH_PROBABILITIES is nonzero, this function reads auxiliary
888 information from a data file containing edge count information from previous
889 executions of the function being compiled. In this case, the flow graph is
890 annotated with actual execution counts, which are later propagated into the
891 rtl for optimization purposes.
893 Main entry point of this file. */
895 void
896 branch_prob (void)
898 basic_block bb;
899 unsigned i;
900 unsigned num_edges, ignored_edges;
901 unsigned num_instrumented;
902 struct edge_list *el;
903 histogram_values values = NULL;
905 total_num_times_called++;
907 flow_call_edges_add (NULL);
908 add_noreturn_fake_exit_edges ();
910 /* We can't handle cyclic regions constructed using abnormal edges.
911 To avoid these we replace every source of abnormal edge by a fake
912 edge from entry node and every destination by fake edge to exit.
913 This keeps graph acyclic and our calculation exact for all normal
914 edges except for exit and entrance ones.
916 We also add fake exit edges for each call and asm statement in the
917 basic, since it may not return. */
919 FOR_EACH_BB (bb)
921 int need_exit_edge = 0, need_entry_edge = 0;
922 int have_exit_edge = 0, have_entry_edge = 0;
923 edge e;
924 edge_iterator ei;
926 /* Functions returning multiple times are not handled by extra edges.
927 Instead we simply allow negative counts on edges from exit to the
928 block past call and corresponding probabilities. We can't go
929 with the extra edges because that would result in flowgraph that
930 needs to have fake edges outside the spanning tree. */
932 FOR_EACH_EDGE (e, ei, bb->succs)
934 gimple_stmt_iterator gsi;
935 gimple last = NULL;
937 /* It may happen that there are compiler generated statements
938 without a locus at all. Go through the basic block from the
939 last to the first statement looking for a locus. */
940 for (gsi = gsi_last_bb (bb); !gsi_end_p (gsi); gsi_prev (&gsi))
942 last = gsi_stmt (gsi);
943 if (!is_gimple_debug (last)
944 && gimple_has_location (last))
945 break;
948 /* Edge with goto locus might get wrong coverage info unless
949 it is the only edge out of BB.
950 Don't do that when the locuses match, so
951 if (blah) goto something;
952 is not computed twice. */
953 if (last
954 && gimple_has_location (last)
955 && e->goto_locus != UNKNOWN_LOCATION
956 && !single_succ_p (bb)
957 && (LOCATION_FILE (e->goto_locus)
958 != LOCATION_FILE (gimple_location (last))
959 || (LOCATION_LINE (e->goto_locus)
960 != LOCATION_LINE (gimple_location (last)))))
962 basic_block new_bb = split_edge (e);
963 edge ne = single_succ_edge (new_bb);
964 ne->goto_locus = e->goto_locus;
965 ne->goto_block = e->goto_block;
967 if ((e->flags & (EDGE_ABNORMAL | EDGE_ABNORMAL_CALL))
968 && e->dest != EXIT_BLOCK_PTR)
969 need_exit_edge = 1;
970 if (e->dest == EXIT_BLOCK_PTR)
971 have_exit_edge = 1;
973 FOR_EACH_EDGE (e, ei, bb->preds)
975 if ((e->flags & (EDGE_ABNORMAL | EDGE_ABNORMAL_CALL))
976 && e->src != ENTRY_BLOCK_PTR)
977 need_entry_edge = 1;
978 if (e->src == ENTRY_BLOCK_PTR)
979 have_entry_edge = 1;
982 if (need_exit_edge && !have_exit_edge)
984 if (dump_file)
985 fprintf (dump_file, "Adding fake exit edge to bb %i\n",
986 bb->index);
987 make_edge (bb, EXIT_BLOCK_PTR, EDGE_FAKE);
989 if (need_entry_edge && !have_entry_edge)
991 if (dump_file)
992 fprintf (dump_file, "Adding fake entry edge to bb %i\n",
993 bb->index);
994 make_edge (ENTRY_BLOCK_PTR, bb, EDGE_FAKE);
998 el = create_edge_list ();
999 num_edges = NUM_EDGES (el);
1000 alloc_aux_for_edges (sizeof (struct edge_info));
1002 /* The basic blocks are expected to be numbered sequentially. */
1003 compact_blocks ();
1005 ignored_edges = 0;
1006 for (i = 0 ; i < num_edges ; i++)
1008 edge e = INDEX_EDGE (el, i);
1009 e->count = 0;
1011 /* Mark edges we've replaced by fake edges above as ignored. */
1012 if ((e->flags & (EDGE_ABNORMAL | EDGE_ABNORMAL_CALL))
1013 && e->src != ENTRY_BLOCK_PTR && e->dest != EXIT_BLOCK_PTR)
1015 EDGE_INFO (e)->ignore = 1;
1016 ignored_edges++;
1020 /* Create spanning tree from basic block graph, mark each edge that is
1021 on the spanning tree. We insert as many abnormal and critical edges
1022 as possible to minimize number of edge splits necessary. */
1024 find_spanning_tree (el);
1026 /* Fake edges that are not on the tree will not be instrumented, so
1027 mark them ignored. */
1028 for (num_instrumented = i = 0; i < num_edges; i++)
1030 edge e = INDEX_EDGE (el, i);
1031 struct edge_info *inf = EDGE_INFO (e);
1033 if (inf->ignore || inf->on_tree)
1034 /*NOP*/;
1035 else if (e->flags & EDGE_FAKE)
1037 inf->ignore = 1;
1038 ignored_edges++;
1040 else
1041 num_instrumented++;
1044 total_num_blocks += n_basic_blocks;
1045 if (dump_file)
1046 fprintf (dump_file, "%d basic blocks\n", n_basic_blocks);
1048 total_num_edges += num_edges;
1049 if (dump_file)
1050 fprintf (dump_file, "%d edges\n", num_edges);
1052 total_num_edges_ignored += ignored_edges;
1053 if (dump_file)
1054 fprintf (dump_file, "%d ignored edges\n", ignored_edges);
1056 /* Write the data from which gcov can reconstruct the basic block
1057 graph. */
1059 /* Basic block flags */
1060 if (coverage_begin_output ())
1062 gcov_position_t offset;
1064 offset = gcov_write_tag (GCOV_TAG_BLOCKS);
1065 for (i = 0; i != (unsigned) (n_basic_blocks); i++)
1066 gcov_write_unsigned (0);
1067 gcov_write_length (offset);
1070 /* Keep all basic block indexes nonnegative in the gcov output.
1071 Index 0 is used for entry block, last index is for exit block.
1073 ENTRY_BLOCK_PTR->index = 1;
1074 EXIT_BLOCK_PTR->index = last_basic_block;
1076 /* Arcs */
1077 if (coverage_begin_output ())
1079 gcov_position_t offset;
1081 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
1083 edge e;
1084 edge_iterator ei;
1086 offset = gcov_write_tag (GCOV_TAG_ARCS);
1087 gcov_write_unsigned (BB_TO_GCOV_INDEX (bb));
1089 FOR_EACH_EDGE (e, ei, bb->succs)
1091 struct edge_info *i = EDGE_INFO (e);
1092 if (!i->ignore)
1094 unsigned flag_bits = 0;
1096 if (i->on_tree)
1097 flag_bits |= GCOV_ARC_ON_TREE;
1098 if (e->flags & EDGE_FAKE)
1099 flag_bits |= GCOV_ARC_FAKE;
1100 if (e->flags & EDGE_FALLTHRU)
1101 flag_bits |= GCOV_ARC_FALLTHROUGH;
1102 /* On trees we don't have fallthru flags, but we can
1103 recompute them from CFG shape. */
1104 if (e->flags & (EDGE_TRUE_VALUE | EDGE_FALSE_VALUE)
1105 && e->src->next_bb == e->dest)
1106 flag_bits |= GCOV_ARC_FALLTHROUGH;
1108 gcov_write_unsigned (BB_TO_GCOV_INDEX (e->dest));
1109 gcov_write_unsigned (flag_bits);
1113 gcov_write_length (offset);
1117 /* Line numbers. */
1118 if (coverage_begin_output ())
1120 gcov_position_t offset;
1122 /* Initialize the output. */
1123 output_location (NULL, 0, NULL, NULL);
1125 FOR_EACH_BB (bb)
1127 gimple_stmt_iterator gsi;
1129 offset = 0;
1131 if (bb == ENTRY_BLOCK_PTR->next_bb)
1133 expanded_location curr_location =
1134 expand_location (DECL_SOURCE_LOCATION (current_function_decl));
1135 output_location (curr_location.file, curr_location.line,
1136 &offset, bb);
1139 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1141 gimple stmt = gsi_stmt (gsi);
1142 if (gimple_has_location (stmt))
1143 output_location (gimple_filename (stmt), gimple_lineno (stmt),
1144 &offset, bb);
1147 /* Notice GOTO expressions we eliminated while constructing the
1148 CFG. */
1149 if (single_succ_p (bb)
1150 && single_succ_edge (bb)->goto_locus != UNKNOWN_LOCATION)
1152 location_t curr_location = single_succ_edge (bb)->goto_locus;
1153 /* ??? The FILE/LINE API is inconsistent for these cases. */
1154 output_location (LOCATION_FILE (curr_location),
1155 LOCATION_LINE (curr_location), &offset, bb);
1158 if (offset)
1160 /* A file of NULL indicates the end of run. */
1161 gcov_write_unsigned (0);
1162 gcov_write_string (NULL);
1163 gcov_write_length (offset);
1168 ENTRY_BLOCK_PTR->index = ENTRY_BLOCK;
1169 EXIT_BLOCK_PTR->index = EXIT_BLOCK;
1170 #undef BB_TO_GCOV_INDEX
1172 if (flag_profile_values)
1173 find_values_to_profile (&values);
1175 if (flag_branch_probabilities)
1177 compute_branch_probabilities ();
1178 if (flag_profile_values)
1179 compute_value_histograms (values);
1182 remove_fake_edges ();
1184 /* For each edge not on the spanning tree, add counting code. */
1185 if (profile_arc_flag
1186 && coverage_counter_alloc (GCOV_COUNTER_ARCS, num_instrumented))
1188 unsigned n_instrumented;
1190 profile_hooks->init_edge_profiler ();
1192 n_instrumented = instrument_edges (el);
1194 gcc_assert (n_instrumented == num_instrumented);
1196 if (flag_profile_values)
1197 instrument_values (values);
1199 /* Commit changes done by instrumentation. */
1200 gsi_commit_edge_inserts ();
1203 free_aux_for_edges ();
1205 VEC_free (histogram_value, heap, values);
1206 free_edge_list (el);
1207 coverage_end_function ();
1210 /* Union find algorithm implementation for the basic blocks using
1211 aux fields. */
1213 static basic_block
1214 find_group (basic_block bb)
1216 basic_block group = bb, bb1;
1218 while ((basic_block) group->aux != group)
1219 group = (basic_block) group->aux;
1221 /* Compress path. */
1222 while ((basic_block) bb->aux != group)
1224 bb1 = (basic_block) bb->aux;
1225 bb->aux = (void *) group;
1226 bb = bb1;
1228 return group;
1231 static void
1232 union_groups (basic_block bb1, basic_block bb2)
1234 basic_block bb1g = find_group (bb1);
1235 basic_block bb2g = find_group (bb2);
1237 /* ??? I don't have a place for the rank field. OK. Lets go w/o it,
1238 this code is unlikely going to be performance problem anyway. */
1239 gcc_assert (bb1g != bb2g);
1241 bb1g->aux = bb2g;
1244 /* This function searches all of the edges in the program flow graph, and puts
1245 as many bad edges as possible onto the spanning tree. Bad edges include
1246 abnormals edges, which can't be instrumented at the moment. Since it is
1247 possible for fake edges to form a cycle, we will have to develop some
1248 better way in the future. Also put critical edges to the tree, since they
1249 are more expensive to instrument. */
1251 static void
1252 find_spanning_tree (struct edge_list *el)
1254 int i;
1255 int num_edges = NUM_EDGES (el);
1256 basic_block bb;
1258 /* We use aux field for standard union-find algorithm. */
1259 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
1260 bb->aux = bb;
1262 /* Add fake edge exit to entry we can't instrument. */
1263 union_groups (EXIT_BLOCK_PTR, ENTRY_BLOCK_PTR);
1265 /* First add all abnormal edges to the tree unless they form a cycle. Also
1266 add all edges to EXIT_BLOCK_PTR to avoid inserting profiling code behind
1267 setting return value from function. */
1268 for (i = 0; i < num_edges; i++)
1270 edge e = INDEX_EDGE (el, i);
1271 if (((e->flags & (EDGE_ABNORMAL | EDGE_ABNORMAL_CALL | EDGE_FAKE))
1272 || e->dest == EXIT_BLOCK_PTR)
1273 && !EDGE_INFO (e)->ignore
1274 && (find_group (e->src) != find_group (e->dest)))
1276 if (dump_file)
1277 fprintf (dump_file, "Abnormal edge %d to %d put to tree\n",
1278 e->src->index, e->dest->index);
1279 EDGE_INFO (e)->on_tree = 1;
1280 union_groups (e->src, e->dest);
1284 /* Now insert all critical edges to the tree unless they form a cycle. */
1285 for (i = 0; i < num_edges; i++)
1287 edge e = INDEX_EDGE (el, i);
1288 if (EDGE_CRITICAL_P (e) && !EDGE_INFO (e)->ignore
1289 && find_group (e->src) != find_group (e->dest))
1291 if (dump_file)
1292 fprintf (dump_file, "Critical edge %d to %d put to tree\n",
1293 e->src->index, e->dest->index);
1294 EDGE_INFO (e)->on_tree = 1;
1295 union_groups (e->src, e->dest);
1299 /* And now the rest. */
1300 for (i = 0; i < num_edges; i++)
1302 edge e = INDEX_EDGE (el, i);
1303 if (!EDGE_INFO (e)->ignore
1304 && find_group (e->src) != find_group (e->dest))
1306 if (dump_file)
1307 fprintf (dump_file, "Normal edge %d to %d put to tree\n",
1308 e->src->index, e->dest->index);
1309 EDGE_INFO (e)->on_tree = 1;
1310 union_groups (e->src, e->dest);
1314 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
1315 bb->aux = NULL;
1318 /* Perform file-level initialization for branch-prob processing. */
1320 void
1321 init_branch_prob (void)
1323 int i;
1325 total_num_blocks = 0;
1326 total_num_edges = 0;
1327 total_num_edges_ignored = 0;
1328 total_num_edges_instrumented = 0;
1329 total_num_blocks_created = 0;
1330 total_num_passes = 0;
1331 total_num_times_called = 0;
1332 total_num_branches = 0;
1333 for (i = 0; i < 20; i++)
1334 total_hist_br_prob[i] = 0;
1337 /* Performs file-level cleanup after branch-prob processing
1338 is completed. */
1340 void
1341 end_branch_prob (void)
1343 if (dump_file)
1345 fprintf (dump_file, "\n");
1346 fprintf (dump_file, "Total number of blocks: %d\n",
1347 total_num_blocks);
1348 fprintf (dump_file, "Total number of edges: %d\n", total_num_edges);
1349 fprintf (dump_file, "Total number of ignored edges: %d\n",
1350 total_num_edges_ignored);
1351 fprintf (dump_file, "Total number of instrumented edges: %d\n",
1352 total_num_edges_instrumented);
1353 fprintf (dump_file, "Total number of blocks created: %d\n",
1354 total_num_blocks_created);
1355 fprintf (dump_file, "Total number of graph solution passes: %d\n",
1356 total_num_passes);
1357 if (total_num_times_called != 0)
1358 fprintf (dump_file, "Average number of graph solution passes: %d\n",
1359 (total_num_passes + (total_num_times_called >> 1))
1360 / total_num_times_called);
1361 fprintf (dump_file, "Total number of branches: %d\n",
1362 total_num_branches);
1363 if (total_num_branches)
1365 int i;
1367 for (i = 0; i < 10; i++)
1368 fprintf (dump_file, "%d%% branches in range %d-%d%%\n",
1369 (total_hist_br_prob[i] + total_hist_br_prob[19-i]) * 100
1370 / total_num_branches, 5*i, 5*i+5);
1375 /* Set up hooks to enable tree-based profiling. */
1377 void
1378 tree_register_profile_hooks (void)
1380 gcc_assert (current_ir_type () == IR_GIMPLE);
1381 profile_hooks = &tree_profile_hooks;