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
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
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
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. */
54 #include "coretypes.h"
64 #include "value-prof.h"
67 #include "tree-flow.h"
70 #include "tree-pass.h"
72 /* Hooks for profiling. */
73 static struct profile_hooks
* profile_hooks
;
75 /* Additional information about the edges we need. */
77 unsigned int count_valid
: 1;
79 /* Is on the spanning tree. */
80 unsigned int on_tree
: 1;
82 /* Pretend this edge does not exist (it is abnormal and we've
83 inserted a fake to compensate). */
84 unsigned int ignore
: 1;
88 unsigned int count_valid
: 1;
90 /* Number of successor and predecessor edges. */
95 #define EDGE_INFO(e) ((struct edge_info *) (e)->aux)
96 #define BB_INFO(b) ((struct bb_info *) (b)->aux)
99 /* Counter summary from the last set of coverage counts read. */
101 const struct gcov_ctr_summary
*profile_info
;
103 /* Collect statistics on the performance of this pass for the entire source
106 static int total_num_blocks
;
107 static int total_num_edges
;
108 static int total_num_edges_ignored
;
109 static int total_num_edges_instrumented
;
110 static int total_num_blocks_created
;
111 static int total_num_passes
;
112 static int total_num_times_called
;
113 static int total_hist_br_prob
[20];
114 static int total_num_never_executed
;
115 static int total_num_branches
;
117 /* Forward declarations. */
118 static void find_spanning_tree (struct edge_list
*);
119 static unsigned instrument_edges (struct edge_list
*);
120 static void instrument_values (histogram_values
);
121 static void compute_branch_probabilities (void);
122 static void compute_value_histograms (histogram_values
);
123 static gcov_type
* get_exec_counts (void);
124 static basic_block
find_group (basic_block
);
125 static void union_groups (basic_block
, basic_block
);
128 /* Add edge instrumentation code to the entire insn chain.
130 F is the first insn of the chain.
131 NUM_BLOCKS is the number of basic blocks found in F. */
134 instrument_edges (struct edge_list
*el
)
136 unsigned num_instr_edges
= 0;
137 int num_edges
= NUM_EDGES (el
);
140 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, NULL
, next_bb
)
145 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
147 struct edge_info
*inf
= EDGE_INFO (e
);
149 if (!inf
->ignore
&& !inf
->on_tree
)
151 gcc_assert (!(e
->flags
& EDGE_ABNORMAL
));
153 fprintf (dump_file
, "Edge %d to %d instrumented%s\n",
154 e
->src
->index
, e
->dest
->index
,
155 EDGE_CRITICAL_P (e
) ? " (and split)" : "");
156 (profile_hooks
->gen_edge_profiler
) (num_instr_edges
++, e
);
161 total_num_blocks_created
+= num_edges
;
163 fprintf (dump_file
, "%d edges instrumented\n", num_instr_edges
);
164 return num_instr_edges
;
167 /* Add code to measure histograms for values in list VALUES. */
169 instrument_values (histogram_values values
)
173 /* Emit code to generate the histograms before the insns. */
175 for (i
= 0; i
< VEC_length (histogram_value
, values
); i
++)
177 histogram_value hist
= VEC_index (histogram_value
, values
, i
);
180 case HIST_TYPE_INTERVAL
:
181 t
= GCOV_COUNTER_V_INTERVAL
;
185 t
= GCOV_COUNTER_V_POW2
;
188 case HIST_TYPE_SINGLE_VALUE
:
189 t
= GCOV_COUNTER_V_SINGLE
;
192 case HIST_TYPE_CONST_DELTA
:
193 t
= GCOV_COUNTER_V_DELTA
;
196 case HIST_TYPE_INDIR_CALL
:
197 t
= GCOV_COUNTER_V_INDIR
;
200 case HIST_TYPE_AVERAGE
:
201 t
= GCOV_COUNTER_AVERAGE
;
205 t
= GCOV_COUNTER_IOR
;
211 if (!coverage_counter_alloc (t
, hist
->n_counters
))
216 case HIST_TYPE_INTERVAL
:
217 (profile_hooks
->gen_interval_profiler
) (hist
, t
, 0);
221 (profile_hooks
->gen_pow2_profiler
) (hist
, t
, 0);
224 case HIST_TYPE_SINGLE_VALUE
:
225 (profile_hooks
->gen_one_value_profiler
) (hist
, t
, 0);
228 case HIST_TYPE_CONST_DELTA
:
229 (profile_hooks
->gen_const_delta_profiler
) (hist
, t
, 0);
232 case HIST_TYPE_INDIR_CALL
:
233 (profile_hooks
->gen_ic_profiler
) (hist
, t
, 0);
236 case HIST_TYPE_AVERAGE
:
237 (profile_hooks
->gen_average_profiler
) (hist
, t
, 0);
241 (profile_hooks
->gen_ior_profiler
) (hist
, t
, 0);
251 /* Computes hybrid profile for all matching entries in da_file. */
254 get_exec_counts (void)
256 unsigned num_edges
= 0;
260 /* Count the edges to be (possibly) instrumented. */
261 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, NULL
, next_bb
)
266 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
267 if (!EDGE_INFO (e
)->ignore
&& !EDGE_INFO (e
)->on_tree
)
271 counts
= get_coverage_counts (GCOV_COUNTER_ARCS
, num_edges
, &profile_info
);
275 if (dump_file
&& profile_info
)
276 fprintf(dump_file
, "Merged %u profiles with maximal count %u.\n",
277 profile_info
->runs
, (unsigned) profile_info
->sum_max
);
283 /* Compute the branch probabilities for the various branches.
284 Annotate them accordingly. */
287 compute_branch_probabilities (void)
294 int hist_br_prob
[20];
295 int num_never_executed
;
297 gcov_type
*exec_counts
= get_exec_counts ();
298 int exec_counts_pos
= 0;
300 /* Very simple sanity checks so we catch bugs in our profiling code. */
303 if (profile_info
->run_max
* profile_info
->runs
< profile_info
->sum_max
)
305 error ("corrupted profile info: run_max * runs < sum_max");
309 if (profile_info
->sum_all
< profile_info
->sum_max
)
311 error ("corrupted profile info: sum_all is smaller than sum_max");
316 /* Attach extra info block to each bb. */
318 alloc_aux_for_blocks (sizeof (struct bb_info
));
319 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, NULL
, next_bb
)
324 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
325 if (!EDGE_INFO (e
)->ignore
)
326 BB_INFO (bb
)->succ_count
++;
327 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
328 if (!EDGE_INFO (e
)->ignore
)
329 BB_INFO (bb
)->pred_count
++;
332 /* Avoid predicting entry on exit nodes. */
333 BB_INFO (EXIT_BLOCK_PTR
)->succ_count
= 2;
334 BB_INFO (ENTRY_BLOCK_PTR
)->pred_count
= 2;
336 /* For each edge not on the spanning tree, set its execution count from
339 /* The first count in the .da file is the number of times that the function
340 was entered. This is the exec_count for block zero. */
342 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, NULL
, next_bb
)
347 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
348 if (!EDGE_INFO (e
)->ignore
&& !EDGE_INFO (e
)->on_tree
)
353 e
->count
= exec_counts
[exec_counts_pos
++];
354 if (e
->count
> profile_info
->sum_max
)
356 error ("corrupted profile info: edge from %i to %i exceeds maximal count",
357 bb
->index
, e
->dest
->index
);
363 EDGE_INFO (e
)->count_valid
= 1;
364 BB_INFO (bb
)->succ_count
--;
365 BB_INFO (e
->dest
)->pred_count
--;
368 fprintf (dump_file
, "\nRead edge from %i to %i, count:",
369 bb
->index
, e
->dest
->index
);
370 fprintf (dump_file
, HOST_WIDEST_INT_PRINT_DEC
,
371 (HOST_WIDEST_INT
) e
->count
);
377 fprintf (dump_file
, "\n%d edge counts read\n", num_edges
);
379 /* For every block in the file,
380 - if every exit/entrance edge has a known count, then set the block count
381 - if the block count is known, and every exit/entrance edge but one has
382 a known execution count, then set the count of the remaining edge
384 As edge counts are set, decrement the succ/pred count, but don't delete
385 the edge, that way we can easily tell when all edges are known, or only
386 one edge is unknown. */
388 /* The order that the basic blocks are iterated through is important.
389 Since the code that finds spanning trees starts with block 0, low numbered
390 edges are put on the spanning tree in preference to high numbered edges.
391 Hence, most instrumented edges are at the end. Graph solving works much
392 faster if we propagate numbers from the end to the start.
394 This takes an average of slightly more than 3 passes. */
402 FOR_BB_BETWEEN (bb
, EXIT_BLOCK_PTR
, NULL
, prev_bb
)
404 struct bb_info
*bi
= BB_INFO (bb
);
405 if (! bi
->count_valid
)
407 if (bi
->succ_count
== 0)
413 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
419 else if (bi
->pred_count
== 0)
425 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
434 if (bi
->succ_count
== 1)
440 /* One of the counts will be invalid, but it is zero,
441 so adding it in also doesn't hurt. */
442 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
445 /* Search for the invalid edge, and set its count. */
446 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
447 if (! EDGE_INFO (e
)->count_valid
&& ! EDGE_INFO (e
)->ignore
)
450 /* Calculate count for remaining edge by conservation. */
451 total
= bb
->count
- total
;
454 EDGE_INFO (e
)->count_valid
= 1;
458 BB_INFO (e
->dest
)->pred_count
--;
461 if (bi
->pred_count
== 1)
467 /* One of the counts will be invalid, but it is zero,
468 so adding it in also doesn't hurt. */
469 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
472 /* Search for the invalid edge, and set its count. */
473 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
474 if (!EDGE_INFO (e
)->count_valid
&& !EDGE_INFO (e
)->ignore
)
477 /* Calculate count for remaining edge by conservation. */
478 total
= bb
->count
- total
+ e
->count
;
481 EDGE_INFO (e
)->count_valid
= 1;
485 BB_INFO (e
->src
)->succ_count
--;
492 dump_flow_info (dump_file
, dump_flags
);
494 total_num_passes
+= passes
;
496 fprintf (dump_file
, "Graph solving took %d passes.\n\n", passes
);
498 /* If the graph has been correctly solved, every block will have a
499 succ and pred count of zero. */
502 gcc_assert (!BB_INFO (bb
)->succ_count
&& !BB_INFO (bb
)->pred_count
);
505 /* For every edge, calculate its branch probability and add a reg_note
506 to the branch insn to indicate this. */
508 for (i
= 0; i
< 20; i
++)
510 num_never_executed
= 0;
513 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, NULL
, next_bb
)
520 error ("corrupted profile info: number of iterations for basic block %d thought to be %i",
521 bb
->index
, (int)bb
->count
);
524 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
526 /* Function may return twice in the cased the called function is
527 setjmp or calls fork, but we can't represent this by extra
528 edge from the entry, since extra edge from the exit is
529 already present. We get negative frequency from the entry
532 && e
->dest
== EXIT_BLOCK_PTR
)
533 || (e
->count
> bb
->count
534 && e
->dest
!= EXIT_BLOCK_PTR
))
536 if (block_ends_with_call_p (bb
))
537 e
->count
= e
->count
< 0 ? 0 : bb
->count
;
539 if (e
->count
< 0 || e
->count
> bb
->count
)
541 error ("corrupted profile info: number of executions for edge %d-%d thought to be %i",
542 e
->src
->index
, e
->dest
->index
,
544 e
->count
= bb
->count
/ 2;
549 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
550 e
->probability
= (e
->count
* REG_BR_PROB_BASE
+ bb
->count
/ 2) / bb
->count
;
551 if (bb
->index
>= NUM_FIXED_BLOCKS
552 && block_ends_with_condjump_p (bb
)
553 && EDGE_COUNT (bb
->succs
) >= 2)
559 /* Find the branch edge. It is possible that we do have fake
561 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
562 if (!(e
->flags
& (EDGE_FAKE
| EDGE_FALLTHRU
)))
565 prob
= e
->probability
;
566 index
= prob
* 20 / REG_BR_PROB_BASE
;
570 hist_br_prob
[index
]++;
575 /* As a last resort, distribute the probabilities evenly.
576 Use simple heuristics that if there are normal edges,
577 give all abnormals frequency of 0, otherwise distribute the
578 frequency over abnormals (this is the case of noreturn
580 else if (profile_status
== PROFILE_ABSENT
)
584 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
585 if (!(e
->flags
& (EDGE_COMPLEX
| EDGE_FAKE
)))
589 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
590 if (!(e
->flags
& (EDGE_COMPLEX
| EDGE_FAKE
)))
591 e
->probability
= REG_BR_PROB_BASE
/ total
;
597 total
+= EDGE_COUNT (bb
->succs
);
598 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
599 e
->probability
= REG_BR_PROB_BASE
/ total
;
601 if (bb
->index
>= NUM_FIXED_BLOCKS
602 && block_ends_with_condjump_p (bb
)
603 && EDGE_COUNT (bb
->succs
) >= 2)
604 num_branches
++, num_never_executed
;
611 fprintf (dump_file
, "%d branches\n", num_branches
);
612 fprintf (dump_file
, "%d branches never executed\n",
615 for (i
= 0; i
< 10; i
++)
616 fprintf (dump_file
, "%d%% branches in range %d-%d%%\n",
617 (hist_br_prob
[i
] + hist_br_prob
[19-i
]) * 100 / num_branches
,
620 total_num_branches
+= num_branches
;
621 total_num_never_executed
+= num_never_executed
;
622 for (i
= 0; i
< 20; i
++)
623 total_hist_br_prob
[i
] += hist_br_prob
[i
];
625 fputc ('\n', dump_file
);
626 fputc ('\n', dump_file
);
629 free_aux_for_blocks ();
632 /* Load value histograms values whose description is stored in VALUES array
636 compute_value_histograms (histogram_values values
)
638 unsigned i
, j
, t
, any
;
639 unsigned n_histogram_counters
[GCOV_N_VALUE_COUNTERS
];
640 gcov_type
*histogram_counts
[GCOV_N_VALUE_COUNTERS
];
641 gcov_type
*act_count
[GCOV_N_VALUE_COUNTERS
];
642 gcov_type
*aact_count
;
644 for (t
= 0; t
< GCOV_N_VALUE_COUNTERS
; t
++)
645 n_histogram_counters
[t
] = 0;
647 for (i
= 0; i
< VEC_length (histogram_value
, values
); i
++)
649 histogram_value hist
= VEC_index (histogram_value
, values
, i
);
650 n_histogram_counters
[(int) hist
->type
] += hist
->n_counters
;
654 for (t
= 0; t
< GCOV_N_VALUE_COUNTERS
; t
++)
656 if (!n_histogram_counters
[t
])
658 histogram_counts
[t
] = NULL
;
662 histogram_counts
[t
] =
663 get_coverage_counts (COUNTER_FOR_HIST_TYPE (t
),
664 n_histogram_counters
[t
], NULL
);
665 if (histogram_counts
[t
])
667 act_count
[t
] = histogram_counts
[t
];
672 for (i
= 0; i
< VEC_length (histogram_value
, values
); i
++)
674 histogram_value hist
= VEC_index (histogram_value
, values
, i
);
675 gimple stmt
= hist
->hvalue
.stmt
;
677 t
= (int) hist
->type
;
679 aact_count
= act_count
[t
];
680 act_count
[t
] += hist
->n_counters
;
682 gimple_add_histogram_value (cfun
, stmt
, hist
);
683 hist
->hvalue
.counters
= XNEWVEC (gcov_type
, hist
->n_counters
);
684 for (j
= 0; j
< hist
->n_counters
; j
++)
685 hist
->hvalue
.counters
[j
] = aact_count
[j
];
688 for (t
= 0; t
< GCOV_N_VALUE_COUNTERS
; t
++)
689 if (histogram_counts
[t
])
690 free (histogram_counts
[t
]);
693 /* The entry basic block will be moved around so that it has index=1,
694 there is nothing at index 0 and the exit is at n_basic_block. */
695 #define BB_TO_GCOV_INDEX(bb) ((bb)->index - 1)
696 /* When passed NULL as file_name, initialize.
697 When passed something else, output the necessary commands to change
698 line to LINE and offset to FILE_NAME. */
700 output_location (char const *file_name
, int line
,
701 gcov_position_t
*offset
, basic_block bb
)
703 static char const *prev_file_name
;
704 static int prev_line
;
705 bool name_differs
, line_differs
;
709 prev_file_name
= NULL
;
714 name_differs
= !prev_file_name
|| strcmp (file_name
, prev_file_name
);
715 line_differs
= prev_line
!= line
;
717 if (name_differs
|| line_differs
)
721 *offset
= gcov_write_tag (GCOV_TAG_LINES
);
722 gcov_write_unsigned (BB_TO_GCOV_INDEX (bb
));
723 name_differs
= line_differs
=true;
726 /* If this is a new source file, then output the
727 file's name to the .bb file. */
730 prev_file_name
= file_name
;
731 gcov_write_unsigned (0);
732 gcov_write_string (prev_file_name
);
736 gcov_write_unsigned (line
);
742 /* Instrument and/or analyze program behavior based on program flow graph.
743 In either case, this function builds a flow graph for the function being
744 compiled. The flow graph is stored in BB_GRAPH.
746 When FLAG_PROFILE_ARCS is nonzero, this function instruments the edges in
747 the flow graph that are needed to reconstruct the dynamic behavior of the
750 When FLAG_BRANCH_PROBABILITIES is nonzero, this function reads auxiliary
751 information from a data file containing edge count information from previous
752 executions of the function being compiled. In this case, the flow graph is
753 annotated with actual execution counts, which are later propagated into the
754 rtl for optimization purposes.
756 Main entry point of this file. */
763 unsigned num_edges
, ignored_edges
;
764 unsigned num_instrumented
;
765 struct edge_list
*el
;
766 histogram_values values
= NULL
;
768 total_num_times_called
++;
770 flow_call_edges_add (NULL
);
771 add_noreturn_fake_exit_edges ();
773 /* We can't handle cyclic regions constructed using abnormal edges.
774 To avoid these we replace every source of abnormal edge by a fake
775 edge from entry node and every destination by fake edge to exit.
776 This keeps graph acyclic and our calculation exact for all normal
777 edges except for exit and entrance ones.
779 We also add fake exit edges for each call and asm statement in the
780 basic, since it may not return. */
784 int need_exit_edge
= 0, need_entry_edge
= 0;
785 int have_exit_edge
= 0, have_entry_edge
= 0;
789 /* Functions returning multiple times are not handled by extra edges.
790 Instead we simply allow negative counts on edges from exit to the
791 block past call and corresponding probabilities. We can't go
792 with the extra edges because that would result in flowgraph that
793 needs to have fake edges outside the spanning tree. */
795 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
797 gimple_stmt_iterator gsi
;
800 /* It may happen that there are compiler generated statements
801 without a locus at all. Go through the basic block from the
802 last to the first statement looking for a locus. */
803 for (gsi
= gsi_last_bb (bb
); !gsi_end_p (gsi
); gsi_prev (&gsi
))
805 last
= gsi_stmt (gsi
);
806 if (gimple_has_location (last
))
810 /* Edge with goto locus might get wrong coverage info unless
811 it is the only edge out of BB.
812 Don't do that when the locuses match, so
813 if (blah) goto something;
814 is not computed twice. */
816 && gimple_has_location (last
)
817 && e
->goto_locus
!= UNKNOWN_LOCATION
818 && !single_succ_p (bb
)
819 && (LOCATION_FILE (e
->goto_locus
)
820 != LOCATION_FILE (gimple_location (last
))
821 || (LOCATION_LINE (e
->goto_locus
)
822 != LOCATION_LINE (gimple_location (last
)))))
824 basic_block new_bb
= split_edge (e
);
825 single_succ_edge (new_bb
)->goto_locus
= e
->goto_locus
;
827 if ((e
->flags
& (EDGE_ABNORMAL
| EDGE_ABNORMAL_CALL
))
828 && e
->dest
!= EXIT_BLOCK_PTR
)
830 if (e
->dest
== EXIT_BLOCK_PTR
)
833 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
835 if ((e
->flags
& (EDGE_ABNORMAL
| EDGE_ABNORMAL_CALL
))
836 && e
->src
!= ENTRY_BLOCK_PTR
)
838 if (e
->src
== ENTRY_BLOCK_PTR
)
842 if (need_exit_edge
&& !have_exit_edge
)
845 fprintf (dump_file
, "Adding fake exit edge to bb %i\n",
847 make_edge (bb
, EXIT_BLOCK_PTR
, EDGE_FAKE
);
849 if (need_entry_edge
&& !have_entry_edge
)
852 fprintf (dump_file
, "Adding fake entry edge to bb %i\n",
854 make_edge (ENTRY_BLOCK_PTR
, bb
, EDGE_FAKE
);
858 el
= create_edge_list ();
859 num_edges
= NUM_EDGES (el
);
860 alloc_aux_for_edges (sizeof (struct edge_info
));
862 /* The basic blocks are expected to be numbered sequentially. */
866 for (i
= 0 ; i
< num_edges
; i
++)
868 edge e
= INDEX_EDGE (el
, i
);
871 /* Mark edges we've replaced by fake edges above as ignored. */
872 if ((e
->flags
& (EDGE_ABNORMAL
| EDGE_ABNORMAL_CALL
))
873 && e
->src
!= ENTRY_BLOCK_PTR
&& e
->dest
!= EXIT_BLOCK_PTR
)
875 EDGE_INFO (e
)->ignore
= 1;
880 /* Create spanning tree from basic block graph, mark each edge that is
881 on the spanning tree. We insert as many abnormal and critical edges
882 as possible to minimize number of edge splits necessary. */
884 find_spanning_tree (el
);
886 /* Fake edges that are not on the tree will not be instrumented, so
887 mark them ignored. */
888 for (num_instrumented
= i
= 0; i
< num_edges
; i
++)
890 edge e
= INDEX_EDGE (el
, i
);
891 struct edge_info
*inf
= EDGE_INFO (e
);
893 if (inf
->ignore
|| inf
->on_tree
)
895 else if (e
->flags
& EDGE_FAKE
)
904 total_num_blocks
+= n_basic_blocks
;
906 fprintf (dump_file
, "%d basic blocks\n", n_basic_blocks
);
908 total_num_edges
+= num_edges
;
910 fprintf (dump_file
, "%d edges\n", num_edges
);
912 total_num_edges_ignored
+= ignored_edges
;
914 fprintf (dump_file
, "%d ignored edges\n", ignored_edges
);
916 /* Write the data from which gcov can reconstruct the basic block
919 /* Basic block flags */
920 if (coverage_begin_output ())
922 gcov_position_t offset
;
924 offset
= gcov_write_tag (GCOV_TAG_BLOCKS
);
925 for (i
= 0; i
!= (unsigned) (n_basic_blocks
); i
++)
926 gcov_write_unsigned (0);
927 gcov_write_length (offset
);
930 /* Keep all basic block indexes nonnegative in the gcov output.
931 Index 0 is used for entry block, last index is for exit block.
933 ENTRY_BLOCK_PTR
->index
= 1;
934 EXIT_BLOCK_PTR
->index
= last_basic_block
;
937 if (coverage_begin_output ())
939 gcov_position_t offset
;
941 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, EXIT_BLOCK_PTR
, next_bb
)
946 offset
= gcov_write_tag (GCOV_TAG_ARCS
);
947 gcov_write_unsigned (BB_TO_GCOV_INDEX (bb
));
949 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
951 struct edge_info
*i
= EDGE_INFO (e
);
954 unsigned flag_bits
= 0;
957 flag_bits
|= GCOV_ARC_ON_TREE
;
958 if (e
->flags
& EDGE_FAKE
)
959 flag_bits
|= GCOV_ARC_FAKE
;
960 if (e
->flags
& EDGE_FALLTHRU
)
961 flag_bits
|= GCOV_ARC_FALLTHROUGH
;
962 /* On trees we don't have fallthru flags, but we can
963 recompute them from CFG shape. */
964 if (e
->flags
& (EDGE_TRUE_VALUE
| EDGE_FALSE_VALUE
)
965 && e
->src
->next_bb
== e
->dest
)
966 flag_bits
|= GCOV_ARC_FALLTHROUGH
;
968 gcov_write_unsigned (BB_TO_GCOV_INDEX (e
->dest
));
969 gcov_write_unsigned (flag_bits
);
973 gcov_write_length (offset
);
978 if (coverage_begin_output ())
980 gcov_position_t offset
;
982 /* Initialize the output. */
983 output_location (NULL
, 0, NULL
, NULL
);
987 gimple_stmt_iterator gsi
;
991 if (bb
== ENTRY_BLOCK_PTR
->next_bb
)
993 expanded_location curr_location
=
994 expand_location (DECL_SOURCE_LOCATION (current_function_decl
));
995 output_location (curr_location
.file
, curr_location
.line
,
999 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1001 gimple stmt
= gsi_stmt (gsi
);
1002 if (gimple_has_location (stmt
))
1003 output_location (gimple_filename (stmt
), gimple_lineno (stmt
),
1007 /* Notice GOTO expressions we eliminated while constructing the
1009 if (single_succ_p (bb
)
1010 && single_succ_edge (bb
)->goto_locus
!= UNKNOWN_LOCATION
)
1012 location_t curr_location
= single_succ_edge (bb
)->goto_locus
;
1013 /* ??? The FILE/LINE API is inconsistent for these cases. */
1014 output_location (LOCATION_FILE (curr_location
),
1015 LOCATION_LINE (curr_location
), &offset
, bb
);
1020 /* A file of NULL indicates the end of run. */
1021 gcov_write_unsigned (0);
1022 gcov_write_string (NULL
);
1023 gcov_write_length (offset
);
1028 ENTRY_BLOCK_PTR
->index
= ENTRY_BLOCK
;
1029 EXIT_BLOCK_PTR
->index
= EXIT_BLOCK
;
1030 #undef BB_TO_GCOV_INDEX
1032 if (flag_profile_values
)
1033 find_values_to_profile (&values
);
1035 if (flag_branch_probabilities
)
1037 compute_branch_probabilities ();
1038 if (flag_profile_values
)
1039 compute_value_histograms (values
);
1042 remove_fake_edges ();
1044 /* For each edge not on the spanning tree, add counting code. */
1045 if (profile_arc_flag
1046 && coverage_counter_alloc (GCOV_COUNTER_ARCS
, num_instrumented
))
1048 unsigned n_instrumented
;
1050 profile_hooks
->init_edge_profiler ();
1052 n_instrumented
= instrument_edges (el
);
1054 gcc_assert (n_instrumented
== num_instrumented
);
1056 if (flag_profile_values
)
1057 instrument_values (values
);
1059 /* Commit changes done by instrumentation. */
1060 gsi_commit_edge_inserts ();
1063 free_aux_for_edges ();
1065 VEC_free (histogram_value
, heap
, values
);
1066 free_edge_list (el
);
1067 if (flag_branch_probabilities
)
1068 profile_status
= PROFILE_READ
;
1069 coverage_end_function ();
1072 /* Union find algorithm implementation for the basic blocks using
1076 find_group (basic_block bb
)
1078 basic_block group
= bb
, bb1
;
1080 while ((basic_block
) group
->aux
!= group
)
1081 group
= (basic_block
) group
->aux
;
1083 /* Compress path. */
1084 while ((basic_block
) bb
->aux
!= group
)
1086 bb1
= (basic_block
) bb
->aux
;
1087 bb
->aux
= (void *) group
;
1094 union_groups (basic_block bb1
, basic_block bb2
)
1096 basic_block bb1g
= find_group (bb1
);
1097 basic_block bb2g
= find_group (bb2
);
1099 /* ??? I don't have a place for the rank field. OK. Lets go w/o it,
1100 this code is unlikely going to be performance problem anyway. */
1101 gcc_assert (bb1g
!= bb2g
);
1106 /* This function searches all of the edges in the program flow graph, and puts
1107 as many bad edges as possible onto the spanning tree. Bad edges include
1108 abnormals edges, which can't be instrumented at the moment. Since it is
1109 possible for fake edges to form a cycle, we will have to develop some
1110 better way in the future. Also put critical edges to the tree, since they
1111 are more expensive to instrument. */
1114 find_spanning_tree (struct edge_list
*el
)
1117 int num_edges
= NUM_EDGES (el
);
1120 /* We use aux field for standard union-find algorithm. */
1121 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, NULL
, next_bb
)
1124 /* Add fake edge exit to entry we can't instrument. */
1125 union_groups (EXIT_BLOCK_PTR
, ENTRY_BLOCK_PTR
);
1127 /* First add all abnormal edges to the tree unless they form a cycle. Also
1128 add all edges to EXIT_BLOCK_PTR to avoid inserting profiling code behind
1129 setting return value from function. */
1130 for (i
= 0; i
< num_edges
; i
++)
1132 edge e
= INDEX_EDGE (el
, i
);
1133 if (((e
->flags
& (EDGE_ABNORMAL
| EDGE_ABNORMAL_CALL
| EDGE_FAKE
))
1134 || e
->dest
== EXIT_BLOCK_PTR
)
1135 && !EDGE_INFO (e
)->ignore
1136 && (find_group (e
->src
) != find_group (e
->dest
)))
1139 fprintf (dump_file
, "Abnormal edge %d to %d put to tree\n",
1140 e
->src
->index
, e
->dest
->index
);
1141 EDGE_INFO (e
)->on_tree
= 1;
1142 union_groups (e
->src
, e
->dest
);
1146 /* Now insert all critical edges to the tree unless they form a cycle. */
1147 for (i
= 0; i
< num_edges
; i
++)
1149 edge e
= INDEX_EDGE (el
, i
);
1150 if (EDGE_CRITICAL_P (e
) && !EDGE_INFO (e
)->ignore
1151 && find_group (e
->src
) != find_group (e
->dest
))
1154 fprintf (dump_file
, "Critical edge %d to %d put to tree\n",
1155 e
->src
->index
, e
->dest
->index
);
1156 EDGE_INFO (e
)->on_tree
= 1;
1157 union_groups (e
->src
, e
->dest
);
1161 /* And now the rest. */
1162 for (i
= 0; i
< num_edges
; i
++)
1164 edge e
= INDEX_EDGE (el
, i
);
1165 if (!EDGE_INFO (e
)->ignore
1166 && find_group (e
->src
) != find_group (e
->dest
))
1169 fprintf (dump_file
, "Normal edge %d to %d put to tree\n",
1170 e
->src
->index
, e
->dest
->index
);
1171 EDGE_INFO (e
)->on_tree
= 1;
1172 union_groups (e
->src
, e
->dest
);
1176 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, NULL
, next_bb
)
1180 /* Perform file-level initialization for branch-prob processing. */
1183 init_branch_prob (void)
1187 total_num_blocks
= 0;
1188 total_num_edges
= 0;
1189 total_num_edges_ignored
= 0;
1190 total_num_edges_instrumented
= 0;
1191 total_num_blocks_created
= 0;
1192 total_num_passes
= 0;
1193 total_num_times_called
= 0;
1194 total_num_branches
= 0;
1195 total_num_never_executed
= 0;
1196 for (i
= 0; i
< 20; i
++)
1197 total_hist_br_prob
[i
] = 0;
1200 /* Performs file-level cleanup after branch-prob processing
1204 end_branch_prob (void)
1208 fprintf (dump_file
, "\n");
1209 fprintf (dump_file
, "Total number of blocks: %d\n",
1211 fprintf (dump_file
, "Total number of edges: %d\n", total_num_edges
);
1212 fprintf (dump_file
, "Total number of ignored edges: %d\n",
1213 total_num_edges_ignored
);
1214 fprintf (dump_file
, "Total number of instrumented edges: %d\n",
1215 total_num_edges_instrumented
);
1216 fprintf (dump_file
, "Total number of blocks created: %d\n",
1217 total_num_blocks_created
);
1218 fprintf (dump_file
, "Total number of graph solution passes: %d\n",
1220 if (total_num_times_called
!= 0)
1221 fprintf (dump_file
, "Average number of graph solution passes: %d\n",
1222 (total_num_passes
+ (total_num_times_called
>> 1))
1223 / total_num_times_called
);
1224 fprintf (dump_file
, "Total number of branches: %d\n",
1225 total_num_branches
);
1226 fprintf (dump_file
, "Total number of branches never executed: %d\n",
1227 total_num_never_executed
);
1228 if (total_num_branches
)
1232 for (i
= 0; i
< 10; i
++)
1233 fprintf (dump_file
, "%d%% branches in range %d-%d%%\n",
1234 (total_hist_br_prob
[i
] + total_hist_br_prob
[19-i
]) * 100
1235 / total_num_branches
, 5*i
, 5*i
+5);
1240 /* Set up hooks to enable tree-based profiling. */
1243 tree_register_profile_hooks (void)
1245 gcc_assert (current_ir_type () == IR_GIMPLE
);
1246 profile_hooks
= &tree_profile_hooks
;