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)
98 /* Counter summary from the last set of coverage counts read. */
100 const struct gcov_ctr_summary
*profile_info
;
102 /* Collect statistics on the performance of this pass for the entire source
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
;
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
);
127 /* Add edge instrumentation code to the entire insn chain.
129 F is the first insn of the chain.
130 NUM_BLOCKS is the number of basic blocks found in F. */
133 instrument_edges (struct edge_list
*el
)
135 unsigned num_instr_edges
= 0;
136 int num_edges
= NUM_EDGES (el
);
139 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, NULL
, next_bb
)
144 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
146 struct edge_info
*inf
= EDGE_INFO (e
);
148 if (!inf
->ignore
&& !inf
->on_tree
)
150 gcc_assert (!(e
->flags
& EDGE_ABNORMAL
));
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
);
160 total_num_blocks_created
+= num_edges
;
162 fprintf (dump_file
, "%d edges instrumented\n", num_instr_edges
);
163 return num_instr_edges
;
166 /* Add code to measure histograms for values in list VALUES. */
168 instrument_values (histogram_values values
)
172 /* Emit code to generate the histograms before the insns. */
174 for (i
= 0; i
< VEC_length (histogram_value
, values
); i
++)
176 histogram_value hist
= VEC_index (histogram_value
, values
, i
);
179 case HIST_TYPE_INTERVAL
:
180 t
= GCOV_COUNTER_V_INTERVAL
;
184 t
= GCOV_COUNTER_V_POW2
;
187 case HIST_TYPE_SINGLE_VALUE
:
188 t
= GCOV_COUNTER_V_SINGLE
;
191 case HIST_TYPE_CONST_DELTA
:
192 t
= GCOV_COUNTER_V_DELTA
;
195 case HIST_TYPE_INDIR_CALL
:
196 t
= GCOV_COUNTER_V_INDIR
;
199 case HIST_TYPE_AVERAGE
:
200 t
= GCOV_COUNTER_AVERAGE
;
204 t
= GCOV_COUNTER_IOR
;
210 if (!coverage_counter_alloc (t
, hist
->n_counters
))
215 case HIST_TYPE_INTERVAL
:
216 (profile_hooks
->gen_interval_profiler
) (hist
, t
, 0);
220 (profile_hooks
->gen_pow2_profiler
) (hist
, t
, 0);
223 case HIST_TYPE_SINGLE_VALUE
:
224 (profile_hooks
->gen_one_value_profiler
) (hist
, t
, 0);
227 case HIST_TYPE_CONST_DELTA
:
228 (profile_hooks
->gen_const_delta_profiler
) (hist
, t
, 0);
231 case HIST_TYPE_INDIR_CALL
:
232 (profile_hooks
->gen_ic_profiler
) (hist
, t
, 0);
235 case HIST_TYPE_AVERAGE
:
236 (profile_hooks
->gen_average_profiler
) (hist
, t
, 0);
240 (profile_hooks
->gen_ior_profiler
) (hist
, t
, 0);
250 /* Computes hybrid profile for all matching entries in da_file. */
253 get_exec_counts (void)
255 unsigned num_edges
= 0;
259 /* Count the edges to be (possibly) instrumented. */
260 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, NULL
, next_bb
)
265 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
266 if (!EDGE_INFO (e
)->ignore
&& !EDGE_INFO (e
)->on_tree
)
270 counts
= get_coverage_counts (GCOV_COUNTER_ARCS
, num_edges
, &profile_info
);
274 if (dump_file
&& profile_info
)
275 fprintf(dump_file
, "Merged %u profiles with maximal count %u.\n",
276 profile_info
->runs
, (unsigned) profile_info
->sum_max
);
282 /* Compute the branch probabilities for the various branches.
283 Annotate them accordingly. */
286 compute_branch_probabilities (void)
293 int hist_br_prob
[20];
294 int num_never_executed
;
296 gcov_type
*exec_counts
= get_exec_counts ();
297 int exec_counts_pos
= 0;
299 /* Very simple sanity checks so we catch bugs in our profiling code. */
302 if (profile_info
->run_max
* profile_info
->runs
< profile_info
->sum_max
)
304 error ("corrupted profile info: run_max * runs < sum_max");
308 if (profile_info
->sum_all
< profile_info
->sum_max
)
310 error ("corrupted profile info: sum_all is smaller than sum_max");
315 /* Attach extra info block to each bb. */
317 alloc_aux_for_blocks (sizeof (struct bb_info
));
318 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, NULL
, next_bb
)
323 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
324 if (!EDGE_INFO (e
)->ignore
)
325 BB_INFO (bb
)->succ_count
++;
326 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
327 if (!EDGE_INFO (e
)->ignore
)
328 BB_INFO (bb
)->pred_count
++;
331 /* Avoid predicting entry on exit nodes. */
332 BB_INFO (EXIT_BLOCK_PTR
)->succ_count
= 2;
333 BB_INFO (ENTRY_BLOCK_PTR
)->pred_count
= 2;
335 /* For each edge not on the spanning tree, set its execution count from
338 /* The first count in the .da file is the number of times that the function
339 was entered. This is the exec_count for block zero. */
341 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, NULL
, next_bb
)
346 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
347 if (!EDGE_INFO (e
)->ignore
&& !EDGE_INFO (e
)->on_tree
)
352 e
->count
= exec_counts
[exec_counts_pos
++];
353 if (e
->count
> profile_info
->sum_max
)
355 error ("corrupted profile info: edge from %i to %i exceeds maximal count",
356 bb
->index
, e
->dest
->index
);
362 EDGE_INFO (e
)->count_valid
= 1;
363 BB_INFO (bb
)->succ_count
--;
364 BB_INFO (e
->dest
)->pred_count
--;
367 fprintf (dump_file
, "\nRead edge from %i to %i, count:",
368 bb
->index
, e
->dest
->index
);
369 fprintf (dump_file
, HOST_WIDEST_INT_PRINT_DEC
,
370 (HOST_WIDEST_INT
) e
->count
);
376 fprintf (dump_file
, "\n%d edge counts read\n", num_edges
);
378 /* For every block in the file,
379 - if every exit/entrance edge has a known count, then set the block count
380 - if the block count is known, and every exit/entrance edge but one has
381 a known execution count, then set the count of the remaining edge
383 As edge counts are set, decrement the succ/pred count, but don't delete
384 the edge, that way we can easily tell when all edges are known, or only
385 one edge is unknown. */
387 /* The order that the basic blocks are iterated through is important.
388 Since the code that finds spanning trees starts with block 0, low numbered
389 edges are put on the spanning tree in preference to high numbered edges.
390 Hence, most instrumented edges are at the end. Graph solving works much
391 faster if we propagate numbers from the end to the start.
393 This takes an average of slightly more than 3 passes. */
401 FOR_BB_BETWEEN (bb
, EXIT_BLOCK_PTR
, NULL
, prev_bb
)
403 struct bb_info
*bi
= BB_INFO (bb
);
404 if (! bi
->count_valid
)
406 if (bi
->succ_count
== 0)
412 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
418 else if (bi
->pred_count
== 0)
424 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
433 if (bi
->succ_count
== 1)
439 /* One of the counts will be invalid, but it is zero,
440 so adding it in also doesn't hurt. */
441 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
444 /* Seedgeh for the invalid edge, and set its count. */
445 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
446 if (! EDGE_INFO (e
)->count_valid
&& ! EDGE_INFO (e
)->ignore
)
449 /* Calculate count for remaining edge by conservation. */
450 total
= bb
->count
- total
;
453 EDGE_INFO (e
)->count_valid
= 1;
457 BB_INFO (e
->dest
)->pred_count
--;
460 if (bi
->pred_count
== 1)
466 /* One of the counts will be invalid, but it is zero,
467 so adding it in also doesn't hurt. */
468 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
471 /* Search for the invalid edge, and set its count. */
472 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
473 if (!EDGE_INFO (e
)->count_valid
&& !EDGE_INFO (e
)->ignore
)
476 /* Calculate count for remaining edge by conservation. */
477 total
= bb
->count
- total
+ e
->count
;
480 EDGE_INFO (e
)->count_valid
= 1;
484 BB_INFO (e
->src
)->succ_count
--;
491 dump_flow_info (dump_file
, dump_flags
);
493 total_num_passes
+= passes
;
495 fprintf (dump_file
, "Graph solving took %d passes.\n\n", passes
);
497 /* If the graph has been correctly solved, every block will have a
498 succ and pred count of zero. */
501 gcc_assert (!BB_INFO (bb
)->succ_count
&& !BB_INFO (bb
)->pred_count
);
504 /* For every edge, calculate its branch probability and add a reg_note
505 to the branch insn to indicate this. */
507 for (i
= 0; i
< 20; i
++)
509 num_never_executed
= 0;
512 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, NULL
, next_bb
)
519 error ("corrupted profile info: number of iterations for basic block %d thought to be %i",
520 bb
->index
, (int)bb
->count
);
523 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
525 /* Function may return twice in the cased the called function is
526 setjmp or calls fork, but we can't represent this by extra
527 edge from the entry, since extra edge from the exit is
528 already present. We get negative frequency from the entry
531 && e
->dest
== EXIT_BLOCK_PTR
)
532 || (e
->count
> bb
->count
533 && e
->dest
!= EXIT_BLOCK_PTR
))
535 if (block_ends_with_call_p (bb
))
536 e
->count
= e
->count
< 0 ? 0 : bb
->count
;
538 if (e
->count
< 0 || e
->count
> bb
->count
)
540 error ("corrupted profile info: number of executions for edge %d-%d thought to be %i",
541 e
->src
->index
, e
->dest
->index
,
543 e
->count
= bb
->count
/ 2;
548 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
549 e
->probability
= (e
->count
* REG_BR_PROB_BASE
+ bb
->count
/ 2) / bb
->count
;
550 if (bb
->index
>= NUM_FIXED_BLOCKS
551 && block_ends_with_condjump_p (bb
)
552 && EDGE_COUNT (bb
->succs
) >= 2)
558 /* Find the branch edge. It is possible that we do have fake
560 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
561 if (!(e
->flags
& (EDGE_FAKE
| EDGE_FALLTHRU
)))
564 prob
= e
->probability
;
565 index
= prob
* 20 / REG_BR_PROB_BASE
;
569 hist_br_prob
[index
]++;
574 /* As a last resort, distribute the probabilities evenly.
575 Use simple heuristics that if there are normal edges,
576 give all abnormals frequency of 0, otherwise distribute the
577 frequency over abnormals (this is the case of noreturn
579 else if (profile_status
== PROFILE_ABSENT
)
583 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
584 if (!(e
->flags
& (EDGE_COMPLEX
| EDGE_FAKE
)))
588 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
589 if (!(e
->flags
& (EDGE_COMPLEX
| EDGE_FAKE
)))
590 e
->probability
= REG_BR_PROB_BASE
/ total
;
596 total
+= EDGE_COUNT (bb
->succs
);
597 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
598 e
->probability
= REG_BR_PROB_BASE
/ total
;
600 if (bb
->index
>= NUM_FIXED_BLOCKS
601 && block_ends_with_condjump_p (bb
)
602 && EDGE_COUNT (bb
->succs
) >= 2)
603 num_branches
++, num_never_executed
;
610 fprintf (dump_file
, "%d branches\n", num_branches
);
611 fprintf (dump_file
, "%d branches never executed\n",
614 for (i
= 0; i
< 10; i
++)
615 fprintf (dump_file
, "%d%% branches in range %d-%d%%\n",
616 (hist_br_prob
[i
] + hist_br_prob
[19-i
]) * 100 / num_branches
,
619 total_num_branches
+= num_branches
;
620 total_num_never_executed
+= num_never_executed
;
621 for (i
= 0; i
< 20; i
++)
622 total_hist_br_prob
[i
] += hist_br_prob
[i
];
624 fputc ('\n', dump_file
);
625 fputc ('\n', dump_file
);
628 free_aux_for_blocks ();
631 /* Load value histograms values whose description is stored in VALUES array
635 compute_value_histograms (histogram_values values
)
637 unsigned i
, j
, t
, any
;
638 unsigned n_histogram_counters
[GCOV_N_VALUE_COUNTERS
];
639 gcov_type
*histogram_counts
[GCOV_N_VALUE_COUNTERS
];
640 gcov_type
*act_count
[GCOV_N_VALUE_COUNTERS
];
641 gcov_type
*aact_count
;
643 for (t
= 0; t
< GCOV_N_VALUE_COUNTERS
; t
++)
644 n_histogram_counters
[t
] = 0;
646 for (i
= 0; i
< VEC_length (histogram_value
, values
); i
++)
648 histogram_value hist
= VEC_index (histogram_value
, values
, i
);
649 n_histogram_counters
[(int) hist
->type
] += hist
->n_counters
;
653 for (t
= 0; t
< GCOV_N_VALUE_COUNTERS
; t
++)
655 if (!n_histogram_counters
[t
])
657 histogram_counts
[t
] = NULL
;
661 histogram_counts
[t
] =
662 get_coverage_counts (COUNTER_FOR_HIST_TYPE (t
),
663 n_histogram_counters
[t
], NULL
);
664 if (histogram_counts
[t
])
666 act_count
[t
] = histogram_counts
[t
];
671 for (i
= 0; i
< VEC_length (histogram_value
, values
); i
++)
673 histogram_value hist
= VEC_index (histogram_value
, values
, i
);
674 tree stmt
= hist
->hvalue
.stmt
;
676 t
= (int) hist
->type
;
678 aact_count
= act_count
[t
];
679 act_count
[t
] += hist
->n_counters
;
681 gimple_add_histogram_value (cfun
, stmt
, hist
);
682 hist
->hvalue
.counters
= XNEWVEC (gcov_type
, hist
->n_counters
);
683 for (j
= 0; j
< hist
->n_counters
; j
++)
684 hist
->hvalue
.counters
[j
] = aact_count
[j
];
687 for (t
= 0; t
< GCOV_N_VALUE_COUNTERS
; t
++)
688 if (histogram_counts
[t
])
689 free (histogram_counts
[t
]);
692 /* The entry basic block will be moved around so that it has index=1,
693 there is nothing at index 0 and the exit is at n_basic_block. */
694 #define BB_TO_GCOV_INDEX(bb) ((bb)->index - 1)
695 /* When passed NULL as file_name, initialize.
696 When passed something else, output the necessary commands to change
697 line to LINE and offset to FILE_NAME. */
699 output_location (char const *file_name
, int line
,
700 gcov_position_t
*offset
, basic_block bb
)
702 static char const *prev_file_name
;
703 static int prev_line
;
704 bool name_differs
, line_differs
;
708 prev_file_name
= NULL
;
713 name_differs
= !prev_file_name
|| strcmp (file_name
, prev_file_name
);
714 line_differs
= prev_line
!= line
;
716 if (name_differs
|| line_differs
)
720 *offset
= gcov_write_tag (GCOV_TAG_LINES
);
721 gcov_write_unsigned (BB_TO_GCOV_INDEX (bb
));
722 name_differs
= line_differs
=true;
725 /* If this is a new source file, then output the
726 file's name to the .bb file. */
729 prev_file_name
= file_name
;
730 gcov_write_unsigned (0);
731 gcov_write_string (prev_file_name
);
735 gcov_write_unsigned (line
);
741 /* Instrument and/or analyze program behavior based on program flow graph.
742 In either case, this function builds a flow graph for the function being
743 compiled. The flow graph is stored in BB_GRAPH.
745 When FLAG_PROFILE_ARCS is nonzero, this function instruments the edges in
746 the flow graph that are needed to reconstruct the dynamic behavior of the
749 When FLAG_BRANCH_PROBABILITIES is nonzero, this function reads auxiliary
750 information from a data file containing edge count information from previous
751 executions of the function being compiled. In this case, the flow graph is
752 annotated with actual execution counts, which are later propagated into the
753 rtl for optimization purposes.
755 Main entry point of this file. */
762 unsigned num_edges
, ignored_edges
;
763 unsigned num_instrumented
;
764 struct edge_list
*el
;
765 histogram_values values
= NULL
;
767 total_num_times_called
++;
769 flow_call_edges_add (NULL
);
770 add_noreturn_fake_exit_edges ();
772 /* We can't handle cyclic regions constructed using abnormal edges.
773 To avoid these we replace every source of abnormal edge by a fake
774 edge from entry node and every destination by fake edge to exit.
775 This keeps graph acyclic and our calculation exact for all normal
776 edges except for exit and entrance ones.
778 We also add fake exit edges for each call and asm statement in the
779 basic, since it may not return. */
783 int need_exit_edge
= 0, need_entry_edge
= 0;
784 int have_exit_edge
= 0, have_entry_edge
= 0;
788 /* Functions returning multiple times are not handled by extra edges.
789 Instead we simply allow negative counts on edges from exit to the
790 block past call and corresponding probabilities. We can't go
791 with the extra edges because that would result in flowgraph that
792 needs to have fake edges outside the spanning tree. */
794 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
796 block_stmt_iterator bsi
;
799 /* It may happen that there are compiler generated statements
800 without a locus at all. Go through the basic block from the
801 last to the first statement looking for a locus. */
802 for (bsi
= bsi_last (bb
); !bsi_end_p (bsi
); bsi_prev (&bsi
))
804 last
= bsi_stmt (bsi
);
805 if (EXPR_LOCUS (last
))
809 /* Edge with goto locus might get wrong coverage info unless
810 it is the only edge out of BB.
811 Don't do that when the locuses match, so
812 if (blah) goto something;
813 is not computed twice. */
814 if (last
&& EXPR_LOCUS (last
)
816 && !single_succ_p (bb
)
817 && (LOCATION_FILE (e
->goto_locus
)
818 != LOCATION_FILE (EXPR_LOCATION (last
))
819 || (LOCATION_LINE (e
->goto_locus
)
820 != LOCATION_LINE (EXPR_LOCATION (last
)))))
822 basic_block
new = split_edge (e
);
823 single_succ_edge (new)->goto_locus
= e
->goto_locus
;
825 if ((e
->flags
& (EDGE_ABNORMAL
| EDGE_ABNORMAL_CALL
))
826 && e
->dest
!= EXIT_BLOCK_PTR
)
828 if (e
->dest
== EXIT_BLOCK_PTR
)
831 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
833 if ((e
->flags
& (EDGE_ABNORMAL
| EDGE_ABNORMAL_CALL
))
834 && e
->src
!= ENTRY_BLOCK_PTR
)
836 if (e
->src
== ENTRY_BLOCK_PTR
)
840 if (need_exit_edge
&& !have_exit_edge
)
843 fprintf (dump_file
, "Adding fake exit edge to bb %i\n",
845 make_edge (bb
, EXIT_BLOCK_PTR
, EDGE_FAKE
);
847 if (need_entry_edge
&& !have_entry_edge
)
850 fprintf (dump_file
, "Adding fake entry edge to bb %i\n",
852 make_edge (ENTRY_BLOCK_PTR
, bb
, EDGE_FAKE
);
856 el
= create_edge_list ();
857 num_edges
= NUM_EDGES (el
);
858 alloc_aux_for_edges (sizeof (struct edge_info
));
860 /* The basic blocks are expected to be numbered sequentially. */
864 for (i
= 0 ; i
< num_edges
; i
++)
866 edge e
= INDEX_EDGE (el
, i
);
869 /* Mark edges we've replaced by fake edges above as ignored. */
870 if ((e
->flags
& (EDGE_ABNORMAL
| EDGE_ABNORMAL_CALL
))
871 && e
->src
!= ENTRY_BLOCK_PTR
&& e
->dest
!= EXIT_BLOCK_PTR
)
873 EDGE_INFO (e
)->ignore
= 1;
878 /* Create spanning tree from basic block graph, mark each edge that is
879 on the spanning tree. We insert as many abnormal and critical edges
880 as possible to minimize number of edge splits necessary. */
882 find_spanning_tree (el
);
884 /* Fake edges that are not on the tree will not be instrumented, so
885 mark them ignored. */
886 for (num_instrumented
= i
= 0; i
< num_edges
; i
++)
888 edge e
= INDEX_EDGE (el
, i
);
889 struct edge_info
*inf
= EDGE_INFO (e
);
891 if (inf
->ignore
|| inf
->on_tree
)
893 else if (e
->flags
& EDGE_FAKE
)
902 total_num_blocks
+= n_basic_blocks
;
904 fprintf (dump_file
, "%d basic blocks\n", n_basic_blocks
);
906 total_num_edges
+= num_edges
;
908 fprintf (dump_file
, "%d edges\n", num_edges
);
910 total_num_edges_ignored
+= ignored_edges
;
912 fprintf (dump_file
, "%d ignored edges\n", ignored_edges
);
914 /* Write the data from which gcov can reconstruct the basic block
917 /* Basic block flags */
918 if (coverage_begin_output ())
920 gcov_position_t offset
;
922 offset
= gcov_write_tag (GCOV_TAG_BLOCKS
);
923 for (i
= 0; i
!= (unsigned) (n_basic_blocks
); i
++)
924 gcov_write_unsigned (0);
925 gcov_write_length (offset
);
928 /* Keep all basic block indexes nonnegative in the gcov output.
929 Index 0 is used for entry block, last index is for exit block.
931 ENTRY_BLOCK_PTR
->index
= 1;
932 EXIT_BLOCK_PTR
->index
= last_basic_block
;
935 if (coverage_begin_output ())
937 gcov_position_t offset
;
939 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, EXIT_BLOCK_PTR
, next_bb
)
944 offset
= gcov_write_tag (GCOV_TAG_ARCS
);
945 gcov_write_unsigned (BB_TO_GCOV_INDEX (bb
));
947 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
949 struct edge_info
*i
= EDGE_INFO (e
);
952 unsigned flag_bits
= 0;
955 flag_bits
|= GCOV_ARC_ON_TREE
;
956 if (e
->flags
& EDGE_FAKE
)
957 flag_bits
|= GCOV_ARC_FAKE
;
958 if (e
->flags
& EDGE_FALLTHRU
)
959 flag_bits
|= GCOV_ARC_FALLTHROUGH
;
960 /* On trees we don't have fallthru flags, but we can
961 recompute them from CFG shape. */
962 if (e
->flags
& (EDGE_TRUE_VALUE
| EDGE_FALSE_VALUE
)
963 && e
->src
->next_bb
== e
->dest
)
964 flag_bits
|= GCOV_ARC_FALLTHROUGH
;
966 gcov_write_unsigned (BB_TO_GCOV_INDEX (e
->dest
));
967 gcov_write_unsigned (flag_bits
);
971 gcov_write_length (offset
);
976 if (coverage_begin_output ())
978 gcov_position_t offset
;
980 /* Initialize the output. */
981 output_location (NULL
, 0, NULL
, NULL
);
985 block_stmt_iterator bsi
;
989 if (bb
== ENTRY_BLOCK_PTR
->next_bb
)
991 expanded_location curr_location
=
992 expand_location (DECL_SOURCE_LOCATION (current_function_decl
));
993 output_location (curr_location
.file
, curr_location
.line
,
997 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
999 tree stmt
= bsi_stmt (bsi
);
1000 if (EXPR_HAS_LOCATION (stmt
))
1001 output_location (EXPR_FILENAME (stmt
), EXPR_LINENO (stmt
),
1003 /* Take into account modify statements nested in return
1004 produced by C++ NRV transformation. */
1005 if (TREE_CODE (stmt
) == RETURN_EXPR
1006 && TREE_OPERAND (stmt
, 0)
1007 && TREE_CODE (TREE_OPERAND (stmt
, 0)) == MODIFY_EXPR
1008 && EXPR_HAS_LOCATION (TREE_OPERAND (stmt
, 0)))
1009 output_location (EXPR_FILENAME (TREE_OPERAND (stmt
, 0)),
1010 EXPR_LINENO (TREE_OPERAND (stmt
, 0)),
1014 /* Notice GOTO expressions we eliminated while constructing the
1016 if (single_succ_p (bb
) && single_succ_edge (bb
)->goto_locus
)
1018 location_t curr_location
= single_succ_edge (bb
)->goto_locus
;
1019 /* ??? The FILE/LINE API is inconsistent for these cases. */
1020 output_location (LOCATION_FILE (curr_location
),
1021 LOCATION_LINE (curr_location
), &offset
, bb
);
1026 /* A file of NULL indicates the end of run. */
1027 gcov_write_unsigned (0);
1028 gcov_write_string (NULL
);
1029 gcov_write_length (offset
);
1034 ENTRY_BLOCK_PTR
->index
= ENTRY_BLOCK
;
1035 EXIT_BLOCK_PTR
->index
= EXIT_BLOCK
;
1036 #undef BB_TO_GCOV_INDEX
1038 if (flag_profile_values
)
1039 find_values_to_profile (&values
);
1041 if (flag_branch_probabilities
)
1043 compute_branch_probabilities ();
1044 if (flag_profile_values
)
1045 compute_value_histograms (values
);
1048 remove_fake_edges ();
1050 /* For each edge not on the spanning tree, add counting code. */
1051 if (profile_arc_flag
1052 && coverage_counter_alloc (GCOV_COUNTER_ARCS
, num_instrumented
))
1054 unsigned n_instrumented
;
1056 profile_hooks
->init_edge_profiler ();
1058 n_instrumented
= instrument_edges (el
);
1060 gcc_assert (n_instrumented
== num_instrumented
);
1062 if (flag_profile_values
)
1063 instrument_values (values
);
1065 /* Commit changes done by instrumentation. */
1066 bsi_commit_edge_inserts ();
1069 free_aux_for_edges ();
1071 VEC_free (histogram_value
, heap
, values
);
1072 free_edge_list (el
);
1073 if (flag_branch_probabilities
)
1074 profile_status
= PROFILE_READ
;
1075 coverage_end_function ();
1078 /* Union find algorithm implementation for the basic blocks using
1082 find_group (basic_block bb
)
1084 basic_block group
= bb
, bb1
;
1086 while ((basic_block
) group
->aux
!= group
)
1087 group
= (basic_block
) group
->aux
;
1089 /* Compress path. */
1090 while ((basic_block
) bb
->aux
!= group
)
1092 bb1
= (basic_block
) bb
->aux
;
1093 bb
->aux
= (void *) group
;
1100 union_groups (basic_block bb1
, basic_block bb2
)
1102 basic_block bb1g
= find_group (bb1
);
1103 basic_block bb2g
= find_group (bb2
);
1105 /* ??? I don't have a place for the rank field. OK. Lets go w/o it,
1106 this code is unlikely going to be performance problem anyway. */
1107 gcc_assert (bb1g
!= bb2g
);
1112 /* This function searches all of the edges in the program flow graph, and puts
1113 as many bad edges as possible onto the spanning tree. Bad edges include
1114 abnormals edges, which can't be instrumented at the moment. Since it is
1115 possible for fake edges to form a cycle, we will have to develop some
1116 better way in the future. Also put critical edges to the tree, since they
1117 are more expensive to instrument. */
1120 find_spanning_tree (struct edge_list
*el
)
1123 int num_edges
= NUM_EDGES (el
);
1126 /* We use aux field for standard union-find algorithm. */
1127 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, NULL
, next_bb
)
1130 /* Add fake edge exit to entry we can't instrument. */
1131 union_groups (EXIT_BLOCK_PTR
, ENTRY_BLOCK_PTR
);
1133 /* First add all abnormal edges to the tree unless they form a cycle. Also
1134 add all edges to EXIT_BLOCK_PTR to avoid inserting profiling code behind
1135 setting return value from function. */
1136 for (i
= 0; i
< num_edges
; i
++)
1138 edge e
= INDEX_EDGE (el
, i
);
1139 if (((e
->flags
& (EDGE_ABNORMAL
| EDGE_ABNORMAL_CALL
| EDGE_FAKE
))
1140 || e
->dest
== EXIT_BLOCK_PTR
)
1141 && !EDGE_INFO (e
)->ignore
1142 && (find_group (e
->src
) != find_group (e
->dest
)))
1145 fprintf (dump_file
, "Abnormal edge %d to %d put to tree\n",
1146 e
->src
->index
, e
->dest
->index
);
1147 EDGE_INFO (e
)->on_tree
= 1;
1148 union_groups (e
->src
, e
->dest
);
1152 /* Now insert all critical edges to the tree unless they form a cycle. */
1153 for (i
= 0; i
< num_edges
; i
++)
1155 edge e
= INDEX_EDGE (el
, i
);
1156 if (EDGE_CRITICAL_P (e
) && !EDGE_INFO (e
)->ignore
1157 && find_group (e
->src
) != find_group (e
->dest
))
1160 fprintf (dump_file
, "Critical edge %d to %d put to tree\n",
1161 e
->src
->index
, e
->dest
->index
);
1162 EDGE_INFO (e
)->on_tree
= 1;
1163 union_groups (e
->src
, e
->dest
);
1167 /* And now the rest. */
1168 for (i
= 0; i
< num_edges
; i
++)
1170 edge e
= INDEX_EDGE (el
, i
);
1171 if (!EDGE_INFO (e
)->ignore
1172 && find_group (e
->src
) != find_group (e
->dest
))
1175 fprintf (dump_file
, "Normal edge %d to %d put to tree\n",
1176 e
->src
->index
, e
->dest
->index
);
1177 EDGE_INFO (e
)->on_tree
= 1;
1178 union_groups (e
->src
, e
->dest
);
1182 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, NULL
, next_bb
)
1186 /* Perform file-level initialization for branch-prob processing. */
1189 init_branch_prob (void)
1193 total_num_blocks
= 0;
1194 total_num_edges
= 0;
1195 total_num_edges_ignored
= 0;
1196 total_num_edges_instrumented
= 0;
1197 total_num_blocks_created
= 0;
1198 total_num_passes
= 0;
1199 total_num_times_called
= 0;
1200 total_num_branches
= 0;
1201 total_num_never_executed
= 0;
1202 for (i
= 0; i
< 20; i
++)
1203 total_hist_br_prob
[i
] = 0;
1206 /* Performs file-level cleanup after branch-prob processing
1210 end_branch_prob (void)
1214 fprintf (dump_file
, "\n");
1215 fprintf (dump_file
, "Total number of blocks: %d\n",
1217 fprintf (dump_file
, "Total number of edges: %d\n", total_num_edges
);
1218 fprintf (dump_file
, "Total number of ignored edges: %d\n",
1219 total_num_edges_ignored
);
1220 fprintf (dump_file
, "Total number of instrumented edges: %d\n",
1221 total_num_edges_instrumented
);
1222 fprintf (dump_file
, "Total number of blocks created: %d\n",
1223 total_num_blocks_created
);
1224 fprintf (dump_file
, "Total number of graph solution passes: %d\n",
1226 if (total_num_times_called
!= 0)
1227 fprintf (dump_file
, "Average number of graph solution passes: %d\n",
1228 (total_num_passes
+ (total_num_times_called
>> 1))
1229 / total_num_times_called
);
1230 fprintf (dump_file
, "Total number of branches: %d\n",
1231 total_num_branches
);
1232 fprintf (dump_file
, "Total number of branches never executed: %d\n",
1233 total_num_never_executed
);
1234 if (total_num_branches
)
1238 for (i
= 0; i
< 10; i
++)
1239 fprintf (dump_file
, "%d%% branches in range %d-%d%%\n",
1240 (total_hist_br_prob
[i
] + total_hist_br_prob
[19-i
]) * 100
1241 / total_num_branches
, 5*i
, 5*i
+5);
1246 /* Set up hooks to enable tree-based profiling. */
1249 tree_register_profile_hooks (void)
1251 gcc_assert (current_ir_type () == IR_GIMPLE
);
1252 profile_hooks
= &tree_profile_hooks
;