1 /* Calculate branch probabilities, and basic block execution counts.
2 Copyright (C) 1990, 1991, 1992, 1993, 1994, 1996, 1997, 1998, 1999,
3 2000, 2001, 2002, 2003, 2004, 2005 Free Software Foundation, Inc.
4 Contributed by James E. Wilson, UC Berkeley/Cygnus Support;
5 based on some ideas from Dain Samples of UC Berkeley.
6 Further mangling by Bob Manson, Cygnus Support.
8 This file is part of GCC.
10 GCC is free software; you can redistribute it and/or modify it under
11 the terms of the GNU General Public License as published by the Free
12 Software Foundation; either version 2, or (at your option) any later
15 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
16 WARRANTY; without even the implied warranty of MERCHANTABILITY or
17 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
20 You should have received a copy of the GNU General Public License
21 along with GCC; see the file COPYING. If not, write to the Free
22 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
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
;
198 if (!coverage_counter_alloc (t
, hist
->n_counters
))
203 case HIST_TYPE_INTERVAL
:
204 (profile_hooks
->gen_interval_profiler
) (hist
, t
, 0);
208 (profile_hooks
->gen_pow2_profiler
) (hist
, t
, 0);
211 case HIST_TYPE_SINGLE_VALUE
:
212 (profile_hooks
->gen_one_value_profiler
) (hist
, t
, 0);
215 case HIST_TYPE_CONST_DELTA
:
216 (profile_hooks
->gen_const_delta_profiler
) (hist
, t
, 0);
226 /* Computes hybrid profile for all matching entries in da_file. */
229 get_exec_counts (void)
231 unsigned num_edges
= 0;
235 /* Count the edges to be (possibly) instrumented. */
236 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, NULL
, next_bb
)
241 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
242 if (!EDGE_INFO (e
)->ignore
&& !EDGE_INFO (e
)->on_tree
)
246 counts
= get_coverage_counts (GCOV_COUNTER_ARCS
, num_edges
, &profile_info
);
250 if (dump_file
&& profile_info
)
251 fprintf(dump_file
, "Merged %u profiles with maximal count %u.\n",
252 profile_info
->runs
, (unsigned) profile_info
->sum_max
);
258 /* Compute the branch probabilities for the various branches.
259 Annotate them accordingly. */
262 compute_branch_probabilities (void)
269 int hist_br_prob
[20];
270 int num_never_executed
;
272 gcov_type
*exec_counts
= get_exec_counts ();
273 int exec_counts_pos
= 0;
275 /* Very simple sanity checks so we catch bugs in our profiling code. */
278 if (profile_info
->run_max
* profile_info
->runs
< profile_info
->sum_max
)
280 error ("corrupted profile info: run_max * runs < sum_max");
284 if (profile_info
->sum_all
< profile_info
->sum_max
)
286 error ("corrupted profile info: sum_all is smaller than sum_max");
291 /* Attach extra info block to each bb. */
293 alloc_aux_for_blocks (sizeof (struct bb_info
));
294 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, NULL
, next_bb
)
299 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
300 if (!EDGE_INFO (e
)->ignore
)
301 BB_INFO (bb
)->succ_count
++;
302 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
303 if (!EDGE_INFO (e
)->ignore
)
304 BB_INFO (bb
)->pred_count
++;
307 /* Avoid predicting entry on exit nodes. */
308 BB_INFO (EXIT_BLOCK_PTR
)->succ_count
= 2;
309 BB_INFO (ENTRY_BLOCK_PTR
)->pred_count
= 2;
311 /* For each edge not on the spanning tree, set its execution count from
314 /* The first count in the .da file is the number of times that the function
315 was entered. This is the exec_count for block zero. */
317 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, NULL
, next_bb
)
322 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
323 if (!EDGE_INFO (e
)->ignore
&& !EDGE_INFO (e
)->on_tree
)
328 e
->count
= exec_counts
[exec_counts_pos
++];
329 if (e
->count
> profile_info
->sum_max
)
331 error ("corrupted profile info: edge from %i to %i exceeds maximal count",
332 bb
->index
, e
->dest
->index
);
338 EDGE_INFO (e
)->count_valid
= 1;
339 BB_INFO (bb
)->succ_count
--;
340 BB_INFO (e
->dest
)->pred_count
--;
343 fprintf (dump_file
, "\nRead edge from %i to %i, count:",
344 bb
->index
, e
->dest
->index
);
345 fprintf (dump_file
, HOST_WIDEST_INT_PRINT_DEC
,
346 (HOST_WIDEST_INT
) e
->count
);
352 fprintf (dump_file
, "\n%d edge counts read\n", num_edges
);
354 /* For every block in the file,
355 - if every exit/entrance edge has a known count, then set the block count
356 - if the block count is known, and every exit/entrance edge but one has
357 a known execution count, then set the count of the remaining edge
359 As edge counts are set, decrement the succ/pred count, but don't delete
360 the edge, that way we can easily tell when all edges are known, or only
361 one edge is unknown. */
363 /* The order that the basic blocks are iterated through is important.
364 Since the code that finds spanning trees starts with block 0, low numbered
365 edges are put on the spanning tree in preference to high numbered edges.
366 Hence, most instrumented edges are at the end. Graph solving works much
367 faster if we propagate numbers from the end to the start.
369 This takes an average of slightly more than 3 passes. */
377 FOR_BB_BETWEEN (bb
, EXIT_BLOCK_PTR
, NULL
, prev_bb
)
379 struct bb_info
*bi
= BB_INFO (bb
);
380 if (! bi
->count_valid
)
382 if (bi
->succ_count
== 0)
388 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
394 else if (bi
->pred_count
== 0)
400 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
409 if (bi
->succ_count
== 1)
415 /* One of the counts will be invalid, but it is zero,
416 so adding it in also doesn't hurt. */
417 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
420 /* Seedgeh for the invalid edge, and set its count. */
421 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
422 if (! EDGE_INFO (e
)->count_valid
&& ! EDGE_INFO (e
)->ignore
)
425 /* Calculate count for remaining edge by conservation. */
426 total
= bb
->count
- total
;
429 EDGE_INFO (e
)->count_valid
= 1;
433 BB_INFO (e
->dest
)->pred_count
--;
436 if (bi
->pred_count
== 1)
442 /* One of the counts will be invalid, but it is zero,
443 so adding it in also doesn't hurt. */
444 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
447 /* Search for the invalid edge, and set its count. */
448 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
449 if (!EDGE_INFO (e
)->count_valid
&& !EDGE_INFO (e
)->ignore
)
452 /* Calculate count for remaining edge by conservation. */
453 total
= bb
->count
- total
+ e
->count
;
456 EDGE_INFO (e
)->count_valid
= 1;
460 BB_INFO (e
->src
)->succ_count
--;
467 dump_flow_info (dump_file
, dump_flags
);
469 total_num_passes
+= passes
;
471 fprintf (dump_file
, "Graph solving took %d passes.\n\n", passes
);
473 /* If the graph has been correctly solved, every block will have a
474 succ and pred count of zero. */
477 gcc_assert (!BB_INFO (bb
)->succ_count
&& !BB_INFO (bb
)->pred_count
);
480 /* For every edge, calculate its branch probability and add a reg_note
481 to the branch insn to indicate this. */
483 for (i
= 0; i
< 20; i
++)
485 num_never_executed
= 0;
488 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, NULL
, next_bb
)
495 error ("corrupted profile info: number of iterations for basic block %d thought to be %i",
496 bb
->index
, (int)bb
->count
);
499 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
501 /* Function may return twice in the cased the called function is
502 setjmp or calls fork, but we can't represent this by extra
503 edge from the entry, since extra edge from the exit is
504 already present. We get negative frequency from the entry
507 && e
->dest
== EXIT_BLOCK_PTR
)
508 || (e
->count
> bb
->count
509 && e
->dest
!= EXIT_BLOCK_PTR
))
511 if (block_ends_with_call_p (bb
))
512 e
->count
= e
->count
< 0 ? 0 : bb
->count
;
514 if (e
->count
< 0 || e
->count
> bb
->count
)
516 error ("corrupted profile info: number of executions for edge %d-%d thought to be %i",
517 e
->src
->index
, e
->dest
->index
,
519 e
->count
= bb
->count
/ 2;
524 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
525 e
->probability
= (e
->count
* REG_BR_PROB_BASE
+ bb
->count
/ 2) / bb
->count
;
526 if (bb
->index
>= NUM_FIXED_BLOCKS
527 && block_ends_with_condjump_p (bb
)
528 && EDGE_COUNT (bb
->succs
) >= 2)
534 /* Find the branch edge. It is possible that we do have fake
536 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
537 if (!(e
->flags
& (EDGE_FAKE
| EDGE_FALLTHRU
)))
540 prob
= e
->probability
;
541 index
= prob
* 20 / REG_BR_PROB_BASE
;
545 hist_br_prob
[index
]++;
550 /* As a last resort, distribute the probabilities evenly.
551 Use simple heuristics that if there are normal edges,
552 give all abnormals frequency of 0, otherwise distribute the
553 frequency over abnormals (this is the case of noreturn
555 else if (profile_status
== PROFILE_ABSENT
)
559 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
560 if (!(e
->flags
& (EDGE_COMPLEX
| EDGE_FAKE
)))
564 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
565 if (!(e
->flags
& (EDGE_COMPLEX
| EDGE_FAKE
)))
566 e
->probability
= REG_BR_PROB_BASE
/ total
;
572 total
+= EDGE_COUNT (bb
->succs
);
573 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
574 e
->probability
= REG_BR_PROB_BASE
/ total
;
576 if (bb
->index
>= NUM_FIXED_BLOCKS
577 && block_ends_with_condjump_p (bb
)
578 && EDGE_COUNT (bb
->succs
) >= 2)
579 num_branches
++, num_never_executed
;
586 fprintf (dump_file
, "%d branches\n", num_branches
);
587 fprintf (dump_file
, "%d branches never executed\n",
590 for (i
= 0; i
< 10; i
++)
591 fprintf (dump_file
, "%d%% branches in range %d-%d%%\n",
592 (hist_br_prob
[i
] + hist_br_prob
[19-i
]) * 100 / num_branches
,
595 total_num_branches
+= num_branches
;
596 total_num_never_executed
+= num_never_executed
;
597 for (i
= 0; i
< 20; i
++)
598 total_hist_br_prob
[i
] += hist_br_prob
[i
];
600 fputc ('\n', dump_file
);
601 fputc ('\n', dump_file
);
604 free_aux_for_blocks ();
607 /* Load value histograms values whose description is stored in VALUES array
611 compute_value_histograms (histogram_values values
)
613 unsigned i
, j
, t
, any
;
614 unsigned n_histogram_counters
[GCOV_N_VALUE_COUNTERS
];
615 gcov_type
*histogram_counts
[GCOV_N_VALUE_COUNTERS
];
616 gcov_type
*act_count
[GCOV_N_VALUE_COUNTERS
];
617 gcov_type
*aact_count
;
619 for (t
= 0; t
< GCOV_N_VALUE_COUNTERS
; t
++)
620 n_histogram_counters
[t
] = 0;
622 for (i
= 0; i
< VEC_length (histogram_value
, values
); i
++)
624 histogram_value hist
= VEC_index (histogram_value
, values
, i
);
625 n_histogram_counters
[(int) hist
->type
] += hist
->n_counters
;
629 for (t
= 0; t
< GCOV_N_VALUE_COUNTERS
; t
++)
631 if (!n_histogram_counters
[t
])
633 histogram_counts
[t
] = NULL
;
637 histogram_counts
[t
] =
638 get_coverage_counts (COUNTER_FOR_HIST_TYPE (t
),
639 n_histogram_counters
[t
], NULL
);
640 if (histogram_counts
[t
])
642 act_count
[t
] = histogram_counts
[t
];
647 for (i
= 0; i
< VEC_length (histogram_value
, values
); i
++)
649 histogram_value hist
= VEC_index (histogram_value
, values
, i
);
650 tree stmt
= hist
->hvalue
.stmt
;
652 t
= (int) hist
->type
;
654 aact_count
= act_count
[t
];
655 act_count
[t
] += hist
->n_counters
;
657 gimple_add_histogram_value (cfun
, stmt
, hist
);
658 hist
->hvalue
.counters
= XNEWVEC (gcov_type
, hist
->n_counters
);
659 for (j
= 0; j
< hist
->n_counters
; j
++)
660 hist
->hvalue
.counters
[j
] = aact_count
[j
];
663 for (t
= 0; t
< GCOV_N_VALUE_COUNTERS
; t
++)
664 if (histogram_counts
[t
])
665 free (histogram_counts
[t
]);
668 /* The entry basic block will be moved around so that it has index=1,
669 there is nothing at index 0 and the exit is at n_basic_block. */
670 #define BB_TO_GCOV_INDEX(bb) ((bb)->index - 1)
671 /* When passed NULL as file_name, initialize.
672 When passed something else, output the necessary commands to change
673 line to LINE and offset to FILE_NAME. */
675 output_location (char const *file_name
, int line
,
676 gcov_position_t
*offset
, basic_block bb
)
678 static char const *prev_file_name
;
679 static int prev_line
;
680 bool name_differs
, line_differs
;
684 prev_file_name
= NULL
;
689 name_differs
= !prev_file_name
|| strcmp (file_name
, prev_file_name
);
690 line_differs
= prev_line
!= line
;
692 if (name_differs
|| line_differs
)
696 *offset
= gcov_write_tag (GCOV_TAG_LINES
);
697 gcov_write_unsigned (BB_TO_GCOV_INDEX (bb
));
698 name_differs
= line_differs
=true;
701 /* If this is a new source file, then output the
702 file's name to the .bb file. */
705 prev_file_name
= file_name
;
706 gcov_write_unsigned (0);
707 gcov_write_string (prev_file_name
);
711 gcov_write_unsigned (line
);
717 /* Instrument and/or analyze program behavior based on program flow graph.
718 In either case, this function builds a flow graph for the function being
719 compiled. The flow graph is stored in BB_GRAPH.
721 When FLAG_PROFILE_ARCS is nonzero, this function instruments the edges in
722 the flow graph that are needed to reconstruct the dynamic behavior of the
725 When FLAG_BRANCH_PROBABILITIES is nonzero, this function reads auxiliary
726 information from a data file containing edge count information from previous
727 executions of the function being compiled. In this case, the flow graph is
728 annotated with actual execution counts, which are later propagated into the
729 rtl for optimization purposes.
731 Main entry point of this file. */
738 unsigned num_edges
, ignored_edges
;
739 unsigned num_instrumented
;
740 struct edge_list
*el
;
741 histogram_values values
= NULL
;
743 total_num_times_called
++;
745 flow_call_edges_add (NULL
);
746 add_noreturn_fake_exit_edges ();
748 /* We can't handle cyclic regions constructed using abnormal edges.
749 To avoid these we replace every source of abnormal edge by a fake
750 edge from entry node and every destination by fake edge to exit.
751 This keeps graph acyclic and our calculation exact for all normal
752 edges except for exit and entrance ones.
754 We also add fake exit edges for each call and asm statement in the
755 basic, since it may not return. */
759 int need_exit_edge
= 0, need_entry_edge
= 0;
760 int have_exit_edge
= 0, have_entry_edge
= 0;
764 /* Functions returning multiple times are not handled by extra edges.
765 Instead we simply allow negative counts on edges from exit to the
766 block past call and corresponding probabilities. We can't go
767 with the extra edges because that would result in flowgraph that
768 needs to have fake edges outside the spanning tree. */
770 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
772 block_stmt_iterator bsi
;
775 /* It may happen that there are compiler generated statements
776 without a locus at all. Go through the basic block from the
777 last to the first statement looking for a locus. */
778 for (bsi
= bsi_last (bb
); !bsi_end_p (bsi
); bsi_prev (&bsi
))
780 last
= bsi_stmt (bsi
);
781 if (EXPR_LOCUS (last
))
785 /* Edge with goto locus might get wrong coverage info unless
786 it is the only edge out of BB.
787 Don't do that when the locuses match, so
788 if (blah) goto something;
789 is not computed twice. */
790 if (last
&& EXPR_LOCUS (last
)
792 && !single_succ_p (bb
)
793 #ifdef USE_MAPPED_LOCATION
794 && (LOCATION_FILE (e
->goto_locus
)
795 != LOCATION_FILE (EXPR_LOCATION (last
))
796 || (LOCATION_LINE (e
->goto_locus
)
797 != LOCATION_LINE (EXPR_LOCATION (last
)))))
799 && (e
->goto_locus
->file
!= EXPR_LOCUS (last
)->file
800 || (e
->goto_locus
->line
!= EXPR_LOCUS (last
)->line
)))
803 basic_block
new = split_edge (e
);
804 single_succ_edge (new)->goto_locus
= e
->goto_locus
;
806 if ((e
->flags
& (EDGE_ABNORMAL
| EDGE_ABNORMAL_CALL
))
807 && e
->dest
!= EXIT_BLOCK_PTR
)
809 if (e
->dest
== EXIT_BLOCK_PTR
)
812 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
814 if ((e
->flags
& (EDGE_ABNORMAL
| EDGE_ABNORMAL_CALL
))
815 && e
->src
!= ENTRY_BLOCK_PTR
)
817 if (e
->src
== ENTRY_BLOCK_PTR
)
821 if (need_exit_edge
&& !have_exit_edge
)
824 fprintf (dump_file
, "Adding fake exit edge to bb %i\n",
826 make_edge (bb
, EXIT_BLOCK_PTR
, EDGE_FAKE
);
828 if (need_entry_edge
&& !have_entry_edge
)
831 fprintf (dump_file
, "Adding fake entry edge to bb %i\n",
833 make_edge (ENTRY_BLOCK_PTR
, bb
, EDGE_FAKE
);
837 el
= create_edge_list ();
838 num_edges
= NUM_EDGES (el
);
839 alloc_aux_for_edges (sizeof (struct edge_info
));
841 /* The basic blocks are expected to be numbered sequentially. */
845 for (i
= 0 ; i
< num_edges
; i
++)
847 edge e
= INDEX_EDGE (el
, i
);
850 /* Mark edges we've replaced by fake edges above as ignored. */
851 if ((e
->flags
& (EDGE_ABNORMAL
| EDGE_ABNORMAL_CALL
))
852 && e
->src
!= ENTRY_BLOCK_PTR
&& e
->dest
!= EXIT_BLOCK_PTR
)
854 EDGE_INFO (e
)->ignore
= 1;
859 /* Create spanning tree from basic block graph, mark each edge that is
860 on the spanning tree. We insert as many abnormal and critical edges
861 as possible to minimize number of edge splits necessary. */
863 find_spanning_tree (el
);
865 /* Fake edges that are not on the tree will not be instrumented, so
866 mark them ignored. */
867 for (num_instrumented
= i
= 0; i
< num_edges
; i
++)
869 edge e
= INDEX_EDGE (el
, i
);
870 struct edge_info
*inf
= EDGE_INFO (e
);
872 if (inf
->ignore
|| inf
->on_tree
)
874 else if (e
->flags
& EDGE_FAKE
)
883 total_num_blocks
+= n_basic_blocks
;
885 fprintf (dump_file
, "%d basic blocks\n", n_basic_blocks
);
887 total_num_edges
+= num_edges
;
889 fprintf (dump_file
, "%d edges\n", num_edges
);
891 total_num_edges_ignored
+= ignored_edges
;
893 fprintf (dump_file
, "%d ignored edges\n", ignored_edges
);
895 /* Write the data from which gcov can reconstruct the basic block
898 /* Basic block flags */
899 if (coverage_begin_output ())
901 gcov_position_t offset
;
903 offset
= gcov_write_tag (GCOV_TAG_BLOCKS
);
904 for (i
= 0; i
!= (unsigned) (n_basic_blocks
); i
++)
905 gcov_write_unsigned (0);
906 gcov_write_length (offset
);
909 /* Keep all basic block indexes nonnegative in the gcov output.
910 Index 0 is used for entry block, last index is for exit block.
912 ENTRY_BLOCK_PTR
->index
= 1;
913 EXIT_BLOCK_PTR
->index
= last_basic_block
;
916 if (coverage_begin_output ())
918 gcov_position_t offset
;
920 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, EXIT_BLOCK_PTR
, next_bb
)
925 offset
= gcov_write_tag (GCOV_TAG_ARCS
);
926 gcov_write_unsigned (BB_TO_GCOV_INDEX (bb
));
928 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
930 struct edge_info
*i
= EDGE_INFO (e
);
933 unsigned flag_bits
= 0;
936 flag_bits
|= GCOV_ARC_ON_TREE
;
937 if (e
->flags
& EDGE_FAKE
)
938 flag_bits
|= GCOV_ARC_FAKE
;
939 if (e
->flags
& EDGE_FALLTHRU
)
940 flag_bits
|= GCOV_ARC_FALLTHROUGH
;
941 /* On trees we don't have fallthru flags, but we can
942 recompute them from CFG shape. */
943 if (e
->flags
& (EDGE_TRUE_VALUE
| EDGE_FALSE_VALUE
)
944 && e
->src
->next_bb
== e
->dest
)
945 flag_bits
|= GCOV_ARC_FALLTHROUGH
;
947 gcov_write_unsigned (BB_TO_GCOV_INDEX (e
->dest
));
948 gcov_write_unsigned (flag_bits
);
952 gcov_write_length (offset
);
957 if (coverage_begin_output ())
959 gcov_position_t offset
;
961 /* Initialize the output. */
962 output_location (NULL
, 0, NULL
, NULL
);
966 block_stmt_iterator bsi
;
970 if (bb
== ENTRY_BLOCK_PTR
->next_bb
)
972 expanded_location curr_location
=
973 expand_location (DECL_SOURCE_LOCATION (current_function_decl
));
974 output_location (curr_location
.file
, curr_location
.line
,
978 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
980 tree stmt
= bsi_stmt (bsi
);
981 if (EXPR_HAS_LOCATION (stmt
))
982 output_location (EXPR_FILENAME (stmt
), EXPR_LINENO (stmt
),
986 /* Notice GOTO expressions we eliminated while constructing the
988 if (single_succ_p (bb
) && single_succ_edge (bb
)->goto_locus
)
990 /* ??? source_locus type is marked deprecated in input.h. */
991 source_locus curr_location
= single_succ_edge (bb
)->goto_locus
;
992 /* ??? The FILE/LINE API is inconsistent for these cases. */
993 #ifdef USE_MAPPED_LOCATION
994 output_location (LOCATION_FILE (curr_location
),
995 LOCATION_LINE (curr_location
), &offset
, bb
);
997 output_location (curr_location
->file
, curr_location
->line
,
1004 /* A file of NULL indicates the end of run. */
1005 gcov_write_unsigned (0);
1006 gcov_write_string (NULL
);
1007 gcov_write_length (offset
);
1012 ENTRY_BLOCK_PTR
->index
= ENTRY_BLOCK
;
1013 EXIT_BLOCK_PTR
->index
= EXIT_BLOCK
;
1014 #undef BB_TO_GCOV_INDEX
1016 if (flag_profile_values
)
1017 find_values_to_profile (&values
);
1019 if (flag_branch_probabilities
)
1021 compute_branch_probabilities ();
1022 if (flag_profile_values
)
1023 compute_value_histograms (values
);
1026 remove_fake_edges ();
1028 /* For each edge not on the spanning tree, add counting code. */
1029 if (profile_arc_flag
1030 && coverage_counter_alloc (GCOV_COUNTER_ARCS
, num_instrumented
))
1032 unsigned n_instrumented
;
1034 profile_hooks
->init_edge_profiler ();
1036 n_instrumented
= instrument_edges (el
);
1038 gcc_assert (n_instrumented
== num_instrumented
);
1040 if (flag_profile_values
)
1041 instrument_values (values
);
1043 /* Commit changes done by instrumentation. */
1044 bsi_commit_edge_inserts ();
1047 free_aux_for_edges ();
1049 VEC_free (histogram_value
, heap
, values
);
1050 free_edge_list (el
);
1051 if (flag_branch_probabilities
)
1052 profile_status
= PROFILE_READ
;
1053 coverage_end_function ();
1056 /* Union find algorithm implementation for the basic blocks using
1060 find_group (basic_block bb
)
1062 basic_block group
= bb
, bb1
;
1064 while ((basic_block
) group
->aux
!= group
)
1065 group
= (basic_block
) group
->aux
;
1067 /* Compress path. */
1068 while ((basic_block
) bb
->aux
!= group
)
1070 bb1
= (basic_block
) bb
->aux
;
1071 bb
->aux
= (void *) group
;
1078 union_groups (basic_block bb1
, basic_block bb2
)
1080 basic_block bb1g
= find_group (bb1
);
1081 basic_block bb2g
= find_group (bb2
);
1083 /* ??? I don't have a place for the rank field. OK. Lets go w/o it,
1084 this code is unlikely going to be performance problem anyway. */
1085 gcc_assert (bb1g
!= bb2g
);
1090 /* This function searches all of the edges in the program flow graph, and puts
1091 as many bad edges as possible onto the spanning tree. Bad edges include
1092 abnormals edges, which can't be instrumented at the moment. Since it is
1093 possible for fake edges to form a cycle, we will have to develop some
1094 better way in the future. Also put critical edges to the tree, since they
1095 are more expensive to instrument. */
1098 find_spanning_tree (struct edge_list
*el
)
1101 int num_edges
= NUM_EDGES (el
);
1104 /* We use aux field for standard union-find algorithm. */
1105 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, NULL
, next_bb
)
1108 /* Add fake edge exit to entry we can't instrument. */
1109 union_groups (EXIT_BLOCK_PTR
, ENTRY_BLOCK_PTR
);
1111 /* First add all abnormal edges to the tree unless they form a cycle. Also
1112 add all edges to EXIT_BLOCK_PTR to avoid inserting profiling code behind
1113 setting return value from function. */
1114 for (i
= 0; i
< num_edges
; i
++)
1116 edge e
= INDEX_EDGE (el
, i
);
1117 if (((e
->flags
& (EDGE_ABNORMAL
| EDGE_ABNORMAL_CALL
| EDGE_FAKE
))
1118 || e
->dest
== EXIT_BLOCK_PTR
)
1119 && !EDGE_INFO (e
)->ignore
1120 && (find_group (e
->src
) != find_group (e
->dest
)))
1123 fprintf (dump_file
, "Abnormal edge %d to %d put to tree\n",
1124 e
->src
->index
, e
->dest
->index
);
1125 EDGE_INFO (e
)->on_tree
= 1;
1126 union_groups (e
->src
, e
->dest
);
1130 /* Now insert all critical edges to the tree unless they form a cycle. */
1131 for (i
= 0; i
< num_edges
; i
++)
1133 edge e
= INDEX_EDGE (el
, i
);
1134 if (EDGE_CRITICAL_P (e
) && !EDGE_INFO (e
)->ignore
1135 && find_group (e
->src
) != find_group (e
->dest
))
1138 fprintf (dump_file
, "Critical edge %d to %d put to tree\n",
1139 e
->src
->index
, e
->dest
->index
);
1140 EDGE_INFO (e
)->on_tree
= 1;
1141 union_groups (e
->src
, e
->dest
);
1145 /* And now the rest. */
1146 for (i
= 0; i
< num_edges
; i
++)
1148 edge e
= INDEX_EDGE (el
, i
);
1149 if (!EDGE_INFO (e
)->ignore
1150 && find_group (e
->src
) != find_group (e
->dest
))
1153 fprintf (dump_file
, "Normal edge %d to %d put to tree\n",
1154 e
->src
->index
, e
->dest
->index
);
1155 EDGE_INFO (e
)->on_tree
= 1;
1156 union_groups (e
->src
, e
->dest
);
1160 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, NULL
, next_bb
)
1164 /* Perform file-level initialization for branch-prob processing. */
1167 init_branch_prob (void)
1171 total_num_blocks
= 0;
1172 total_num_edges
= 0;
1173 total_num_edges_ignored
= 0;
1174 total_num_edges_instrumented
= 0;
1175 total_num_blocks_created
= 0;
1176 total_num_passes
= 0;
1177 total_num_times_called
= 0;
1178 total_num_branches
= 0;
1179 total_num_never_executed
= 0;
1180 for (i
= 0; i
< 20; i
++)
1181 total_hist_br_prob
[i
] = 0;
1184 /* Performs file-level cleanup after branch-prob processing
1188 end_branch_prob (void)
1192 fprintf (dump_file
, "\n");
1193 fprintf (dump_file
, "Total number of blocks: %d\n",
1195 fprintf (dump_file
, "Total number of edges: %d\n", total_num_edges
);
1196 fprintf (dump_file
, "Total number of ignored edges: %d\n",
1197 total_num_edges_ignored
);
1198 fprintf (dump_file
, "Total number of instrumented edges: %d\n",
1199 total_num_edges_instrumented
);
1200 fprintf (dump_file
, "Total number of blocks created: %d\n",
1201 total_num_blocks_created
);
1202 fprintf (dump_file
, "Total number of graph solution passes: %d\n",
1204 if (total_num_times_called
!= 0)
1205 fprintf (dump_file
, "Average number of graph solution passes: %d\n",
1206 (total_num_passes
+ (total_num_times_called
>> 1))
1207 / total_num_times_called
);
1208 fprintf (dump_file
, "Total number of branches: %d\n",
1209 total_num_branches
);
1210 fprintf (dump_file
, "Total number of branches never executed: %d\n",
1211 total_num_never_executed
);
1212 if (total_num_branches
)
1216 for (i
= 0; i
< 10; i
++)
1217 fprintf (dump_file
, "%d%% branches in range %d-%d%%\n",
1218 (total_hist_br_prob
[i
] + total_hist_br_prob
[19-i
]) * 100
1219 / total_num_branches
, 5*i
, 5*i
+5);
1224 /* Set up hooks to enable tree-based profiling. */
1227 tree_register_profile_hooks (void)
1229 gcc_assert (current_ir_type () == IR_GIMPLE
);
1230 profile_hooks
= &tree_profile_hooks
;