1 /* Calculate branch probabilities, and basic block execution counts.
2 Copyright (C) 1990-2013 Free Software Foundation, Inc.
3 Contributed by James E. Wilson, UC Berkeley/Cygnus Support;
4 based on some ideas from Dain Samples of UC Berkeley.
5 Further mangling by Bob Manson, Cygnus Support.
7 This file is part of GCC.
9 GCC is free software; you can redistribute it and/or modify it under
10 the terms of the GNU General Public License as published by the Free
11 Software Foundation; either version 3, or (at your option) any later
14 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
15 WARRANTY; without even the implied warranty of MERCHANTABILITY or
16 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
19 You should have received a copy of the GNU General Public License
20 along with GCC; see the file COPYING3. If not see
21 <http://www.gnu.org/licenses/>. */
23 /* Generate basic block profile instrumentation and auxiliary files.
24 Profile generation is optimized, so that not all arcs in the basic
25 block graph need instrumenting. First, the BB graph is closed with
26 one entry (function start), and one exit (function exit). Any
27 ABNORMAL_EDGE cannot be instrumented (because there is no control
28 path to place the code). We close the graph by inserting fake
29 EDGE_FAKE edges to the EXIT_BLOCK, from the sources of abnormal
30 edges that do not go to the exit_block. We ignore such abnormal
31 edges. Naturally these fake edges are never directly traversed,
32 and so *cannot* be directly instrumented. Some other graph
33 massaging is done. To optimize the instrumentation we generate the
34 BB minimal span tree, only edges that are not on the span tree
35 (plus the entry point) need instrumenting. From that information
36 all other edge counts can be deduced. By construction all fake
37 edges must be on the spanning tree. We also attempt to place
38 EDGE_CRITICAL edges on the spanning tree.
40 The auxiliary files generated are <dumpbase>.gcno (at compile time)
41 and <dumpbase>.gcda (at run time). The format is
42 described in full in gcov-io.h. */
44 /* ??? Register allocation should use basic block execution counts to
45 give preference to the most commonly executed blocks. */
47 /* ??? Should calculate branch probabilities before instrumenting code, since
48 then we can use arc counts to help decide which arcs to instrument. */
52 #include "coretypes.h"
59 #include "basic-block.h"
60 #include "diagnostic-core.h"
62 #include "value-prof.h"
72 unsigned int count_valid
: 1;
74 /* Number of successor and predecessor edges. */
79 #define BB_INFO(b) ((struct bb_info *) (b)->aux)
82 /* Counter summary from the last set of coverage counts read. */
84 const struct gcov_ctr_summary
*profile_info
;
86 /* Counter working set information computed from the current counter
87 summary. Not initialized unless profile_info summary is non-NULL. */
88 static gcov_working_set_t gcov_working_sets
[NUM_GCOV_WORKING_SETS
];
90 /* Collect statistics on the performance of this pass for the entire source
93 static int total_num_blocks
;
94 static int total_num_edges
;
95 static int total_num_edges_ignored
;
96 static int total_num_edges_instrumented
;
97 static int total_num_blocks_created
;
98 static int total_num_passes
;
99 static int total_num_times_called
;
100 static int total_hist_br_prob
[20];
101 static int total_num_branches
;
103 /* Forward declarations. */
104 static void find_spanning_tree (struct edge_list
*);
106 /* Add edge instrumentation code to the entire insn chain.
108 F is the first insn of the chain.
109 NUM_BLOCKS is the number of basic blocks found in F. */
112 instrument_edges (struct edge_list
*el
)
114 unsigned num_instr_edges
= 0;
115 int num_edges
= NUM_EDGES (el
);
118 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, NULL
, next_bb
)
123 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
125 struct edge_info
*inf
= EDGE_INFO (e
);
127 if (!inf
->ignore
&& !inf
->on_tree
)
129 gcc_assert (!(e
->flags
& EDGE_ABNORMAL
));
131 fprintf (dump_file
, "Edge %d to %d instrumented%s\n",
132 e
->src
->index
, e
->dest
->index
,
133 EDGE_CRITICAL_P (e
) ? " (and split)" : "");
134 gimple_gen_edge_profiler (num_instr_edges
++, e
);
139 total_num_blocks_created
+= num_edges
;
141 fprintf (dump_file
, "%d edges instrumented\n", num_instr_edges
);
142 return num_instr_edges
;
145 /* Add code to measure histograms for values in list VALUES. */
147 instrument_values (histogram_values values
)
151 /* Emit code to generate the histograms before the insns. */
153 for (i
= 0; i
< values
.length (); i
++)
155 histogram_value hist
= values
[i
];
156 unsigned t
= COUNTER_FOR_HIST_TYPE (hist
->type
);
158 if (!coverage_counter_alloc (t
, hist
->n_counters
))
163 case HIST_TYPE_INTERVAL
:
164 gimple_gen_interval_profiler (hist
, t
, 0);
168 gimple_gen_pow2_profiler (hist
, t
, 0);
171 case HIST_TYPE_SINGLE_VALUE
:
172 gimple_gen_one_value_profiler (hist
, t
, 0);
175 case HIST_TYPE_CONST_DELTA
:
176 gimple_gen_const_delta_profiler (hist
, t
, 0);
179 case HIST_TYPE_INDIR_CALL
:
180 gimple_gen_ic_profiler (hist
, t
, 0);
183 case HIST_TYPE_AVERAGE
:
184 gimple_gen_average_profiler (hist
, t
, 0);
188 gimple_gen_ior_profiler (hist
, t
, 0);
198 /* Fill the working set information into the profile_info structure. */
201 get_working_sets (void)
203 unsigned ws_ix
, pctinc
, pct
;
204 gcov_working_set_t
*ws_info
;
209 compute_working_sets (profile_info
, gcov_working_sets
);
213 fprintf (dump_file
, "Counter working sets:\n");
214 /* Multiply the percentage by 100 to avoid float. */
215 pctinc
= 100 * 100 / NUM_GCOV_WORKING_SETS
;
216 for (ws_ix
= 0, pct
= pctinc
; ws_ix
< NUM_GCOV_WORKING_SETS
;
217 ws_ix
++, pct
+= pctinc
)
219 if (ws_ix
== NUM_GCOV_WORKING_SETS
- 1)
221 ws_info
= &gcov_working_sets
[ws_ix
];
222 /* Print out the percentage using int arithmatic to avoid float. */
223 fprintf (dump_file
, "\t\t%u.%02u%%: num counts=%u, min counter="
224 HOST_WIDEST_INT_PRINT_DEC
"\n",
225 pct
/ 100, pct
- (pct
/ 100 * 100),
226 ws_info
->num_counters
,
227 (HOST_WIDEST_INT
)ws_info
->min_counter
);
232 /* Given a the desired percentage of the full profile (sum_all from the
233 summary), multiplied by 10 to avoid float in PCT_TIMES_10, returns
234 the corresponding working set information. If an exact match for
235 the percentage isn't found, the closest value is used. */
238 find_working_set (unsigned pct_times_10
)
243 gcc_assert (pct_times_10
<= 1000);
244 if (pct_times_10
>= 999)
245 return &gcov_working_sets
[NUM_GCOV_WORKING_SETS
- 1];
246 i
= pct_times_10
* NUM_GCOV_WORKING_SETS
/ 1000;
248 return &gcov_working_sets
[0];
249 return &gcov_working_sets
[i
- 1];
252 /* Computes hybrid profile for all matching entries in da_file.
254 CFG_CHECKSUM is the precomputed checksum for the CFG. */
257 get_exec_counts (unsigned cfg_checksum
, unsigned lineno_checksum
)
259 unsigned num_edges
= 0;
263 /* Count the edges to be (possibly) instrumented. */
264 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, NULL
, next_bb
)
269 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
270 if (!EDGE_INFO (e
)->ignore
&& !EDGE_INFO (e
)->on_tree
)
274 counts
= get_coverage_counts (GCOV_COUNTER_ARCS
, num_edges
, cfg_checksum
,
275 lineno_checksum
, &profile_info
);
281 if (dump_file
&& profile_info
)
282 fprintf (dump_file
, "Merged %u profiles with maximal count %u.\n",
283 profile_info
->runs
, (unsigned) profile_info
->sum_max
);
290 is_edge_inconsistent (vec
<edge
, va_gc
> *edges
)
294 FOR_EACH_EDGE (e
, ei
, edges
)
296 if (!EDGE_INFO (e
)->ignore
)
299 && (!(e
->flags
& EDGE_FAKE
)
300 || !block_ends_with_call_p (e
->src
)))
305 "Edge %i->%i is inconsistent, count"HOST_WIDEST_INT_PRINT_DEC
,
306 e
->src
->index
, e
->dest
->index
, e
->count
);
307 dump_bb (dump_file
, e
->src
, 0, TDF_DETAILS
);
308 dump_bb (dump_file
, e
->dest
, 0, TDF_DETAILS
);
318 correct_negative_edge_counts (void)
324 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, NULL
, next_bb
)
326 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
334 /* Check consistency.
335 Return true if inconsistency is found. */
337 is_inconsistent (void)
340 bool inconsistent
= false;
343 inconsistent
|= is_edge_inconsistent (bb
->preds
);
344 if (!dump_file
&& inconsistent
)
346 inconsistent
|= is_edge_inconsistent (bb
->succs
);
347 if (!dump_file
&& inconsistent
)
353 fprintf (dump_file
, "BB %i count is negative "
354 HOST_WIDEST_INT_PRINT_DEC
,
357 dump_bb (dump_file
, bb
, 0, TDF_DETAILS
);
361 if (bb
->count
!= sum_edge_counts (bb
->preds
))
365 fprintf (dump_file
, "BB %i count does not match sum of incoming edges "
366 HOST_WIDEST_INT_PRINT_DEC
" should be " HOST_WIDEST_INT_PRINT_DEC
,
369 sum_edge_counts (bb
->preds
));
370 dump_bb (dump_file
, bb
, 0, TDF_DETAILS
);
374 if (bb
->count
!= sum_edge_counts (bb
->succs
) &&
375 ! (find_edge (bb
, EXIT_BLOCK_PTR
) != NULL
&& block_ends_with_call_p (bb
)))
379 fprintf (dump_file
, "BB %i count does not match sum of outgoing edges "
380 HOST_WIDEST_INT_PRINT_DEC
" should be " HOST_WIDEST_INT_PRINT_DEC
,
383 sum_edge_counts (bb
->succs
));
384 dump_bb (dump_file
, bb
, 0, TDF_DETAILS
);
388 if (!dump_file
&& inconsistent
)
395 /* Set each basic block count to the sum of its outgoing edge counts */
400 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, NULL
, next_bb
)
402 bb
->count
= sum_edge_counts (bb
->succs
);
403 gcc_assert (bb
->count
>= 0);
407 /* Reads profile data and returns total number of edge counts read */
409 read_profile_edge_counts (gcov_type
*exec_counts
)
413 int exec_counts_pos
= 0;
414 /* For each edge not on the spanning tree, set its execution count from
416 /* The first count in the .da file is the number of times that the function
417 was entered. This is the exec_count for block zero. */
419 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, NULL
, next_bb
)
424 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
425 if (!EDGE_INFO (e
)->ignore
&& !EDGE_INFO (e
)->on_tree
)
430 e
->count
= exec_counts
[exec_counts_pos
++];
431 if (e
->count
> profile_info
->sum_max
)
433 if (flag_profile_correction
)
435 static bool informed
= 0;
436 if (dump_enabled_p () && !informed
)
437 dump_printf_loc (MSG_NOTE
, input_location
,
438 "corrupted profile info: edge count"
439 " exceeds maximal count\n");
443 error ("corrupted profile info: edge from %i to %i exceeds maximal count",
444 bb
->index
, e
->dest
->index
);
450 EDGE_INFO (e
)->count_valid
= 1;
451 BB_INFO (bb
)->succ_count
--;
452 BB_INFO (e
->dest
)->pred_count
--;
455 fprintf (dump_file
, "\nRead edge from %i to %i, count:",
456 bb
->index
, e
->dest
->index
);
457 fprintf (dump_file
, HOST_WIDEST_INT_PRINT_DEC
,
458 (HOST_WIDEST_INT
) e
->count
);
466 #define OVERLAP_BASE 10000
468 /* Compare the static estimated profile to the actual profile, and
469 return the "degree of overlap" measure between them.
471 Degree of overlap is a number between 0 and OVERLAP_BASE. It is
472 the sum of each basic block's minimum relative weights between
473 two profiles. And overlap of OVERLAP_BASE means two profiles are
477 compute_frequency_overlap (void)
479 gcov_type count_total
= 0, freq_total
= 0;
483 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, NULL
, next_bb
)
485 count_total
+= bb
->count
;
486 freq_total
+= bb
->frequency
;
489 if (count_total
== 0 || freq_total
== 0)
492 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, NULL
, next_bb
)
493 overlap
+= MIN (bb
->count
* OVERLAP_BASE
/ count_total
,
494 bb
->frequency
* OVERLAP_BASE
/ freq_total
);
499 /* Compute the branch probabilities for the various branches.
500 Annotate them accordingly.
502 CFG_CHECKSUM is the precomputed checksum for the CFG. */
505 compute_branch_probabilities (unsigned cfg_checksum
, unsigned lineno_checksum
)
512 int hist_br_prob
[20];
514 gcov_type
*exec_counts
= get_exec_counts (cfg_checksum
, lineno_checksum
);
515 int inconsistent
= 0;
517 /* Very simple sanity checks so we catch bugs in our profiling code. */
520 if (profile_info
->run_max
* profile_info
->runs
< profile_info
->sum_max
)
522 error ("corrupted profile info: run_max * runs < sum_max");
526 if (profile_info
->sum_all
< profile_info
->sum_max
)
528 error ("corrupted profile info: sum_all is smaller than sum_max");
532 /* Attach extra info block to each bb. */
533 alloc_aux_for_blocks (sizeof (struct bb_info
));
534 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, NULL
, next_bb
)
539 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
540 if (!EDGE_INFO (e
)->ignore
)
541 BB_INFO (bb
)->succ_count
++;
542 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
543 if (!EDGE_INFO (e
)->ignore
)
544 BB_INFO (bb
)->pred_count
++;
547 /* Avoid predicting entry on exit nodes. */
548 BB_INFO (EXIT_BLOCK_PTR
)->succ_count
= 2;
549 BB_INFO (ENTRY_BLOCK_PTR
)->pred_count
= 2;
551 num_edges
= read_profile_edge_counts (exec_counts
);
554 fprintf (dump_file
, "\n%d edge counts read\n", num_edges
);
556 /* For every block in the file,
557 - if every exit/entrance edge has a known count, then set the block count
558 - if the block count is known, and every exit/entrance edge but one has
559 a known execution count, then set the count of the remaining edge
561 As edge counts are set, decrement the succ/pred count, but don't delete
562 the edge, that way we can easily tell when all edges are known, or only
563 one edge is unknown. */
565 /* The order that the basic blocks are iterated through is important.
566 Since the code that finds spanning trees starts with block 0, low numbered
567 edges are put on the spanning tree in preference to high numbered edges.
568 Hence, most instrumented edges are at the end. Graph solving works much
569 faster if we propagate numbers from the end to the start.
571 This takes an average of slightly more than 3 passes. */
579 FOR_BB_BETWEEN (bb
, EXIT_BLOCK_PTR
, NULL
, prev_bb
)
581 struct bb_info
*bi
= BB_INFO (bb
);
582 if (! bi
->count_valid
)
584 if (bi
->succ_count
== 0)
590 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
596 else if (bi
->pred_count
== 0)
602 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
611 if (bi
->succ_count
== 1)
617 /* One of the counts will be invalid, but it is zero,
618 so adding it in also doesn't hurt. */
619 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
622 /* Search for the invalid edge, and set its count. */
623 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
624 if (! EDGE_INFO (e
)->count_valid
&& ! EDGE_INFO (e
)->ignore
)
627 /* Calculate count for remaining edge by conservation. */
628 total
= bb
->count
- total
;
631 EDGE_INFO (e
)->count_valid
= 1;
635 BB_INFO (e
->dest
)->pred_count
--;
638 if (bi
->pred_count
== 1)
644 /* One of the counts will be invalid, but it is zero,
645 so adding it in also doesn't hurt. */
646 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
649 /* Search for the invalid edge, and set its count. */
650 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
651 if (!EDGE_INFO (e
)->count_valid
&& !EDGE_INFO (e
)->ignore
)
654 /* Calculate count for remaining edge by conservation. */
655 total
= bb
->count
- total
+ e
->count
;
658 EDGE_INFO (e
)->count_valid
= 1;
662 BB_INFO (e
->src
)->succ_count
--;
670 int overlap
= compute_frequency_overlap ();
671 gimple_dump_cfg (dump_file
, dump_flags
);
672 fprintf (dump_file
, "Static profile overlap: %d.%d%%\n",
673 overlap
/ (OVERLAP_BASE
/ 100),
674 overlap
% (OVERLAP_BASE
/ 100));
677 total_num_passes
+= passes
;
679 fprintf (dump_file
, "Graph solving took %d passes.\n\n", passes
);
681 /* If the graph has been correctly solved, every block will have a
682 succ and pred count of zero. */
685 gcc_assert (!BB_INFO (bb
)->succ_count
&& !BB_INFO (bb
)->pred_count
);
688 /* Check for inconsistent basic block counts */
689 inconsistent
= is_inconsistent ();
693 if (flag_profile_correction
)
695 /* Inconsistency detected. Make it flow-consistent. */
696 static int informed
= 0;
697 if (dump_enabled_p () && informed
== 0)
700 dump_printf_loc (MSG_NOTE
, input_location
,
701 "correcting inconsistent profile data\n");
703 correct_negative_edge_counts ();
704 /* Set bb counts to the sum of the outgoing edge counts */
707 fprintf (dump_file
, "\nCalling mcf_smooth_cfg\n");
711 error ("corrupted profile info: profile data is not flow-consistent");
714 /* For every edge, calculate its branch probability and add a reg_note
715 to the branch insn to indicate this. */
717 for (i
= 0; i
< 20; i
++)
721 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, NULL
, next_bb
)
728 error ("corrupted profile info: number of iterations for basic block %d thought to be %i",
729 bb
->index
, (int)bb
->count
);
732 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
734 /* Function may return twice in the cased the called function is
735 setjmp or calls fork, but we can't represent this by extra
736 edge from the entry, since extra edge from the exit is
737 already present. We get negative frequency from the entry
740 && e
->dest
== EXIT_BLOCK_PTR
)
741 || (e
->count
> bb
->count
742 && e
->dest
!= EXIT_BLOCK_PTR
))
744 if (block_ends_with_call_p (bb
))
745 e
->count
= e
->count
< 0 ? 0 : bb
->count
;
747 if (e
->count
< 0 || e
->count
> bb
->count
)
749 error ("corrupted profile info: number of executions for edge %d-%d thought to be %i",
750 e
->src
->index
, e
->dest
->index
,
752 e
->count
= bb
->count
/ 2;
757 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
758 e
->probability
= GCOV_COMPUTE_SCALE (e
->count
, bb
->count
);
759 if (bb
->index
>= NUM_FIXED_BLOCKS
760 && block_ends_with_condjump_p (bb
)
761 && EDGE_COUNT (bb
->succs
) >= 2)
767 /* Find the branch edge. It is possible that we do have fake
769 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
770 if (!(e
->flags
& (EDGE_FAKE
| EDGE_FALLTHRU
)))
773 prob
= e
->probability
;
774 index
= prob
* 20 / REG_BR_PROB_BASE
;
778 hist_br_prob
[index
]++;
783 /* As a last resort, distribute the probabilities evenly.
784 Use simple heuristics that if there are normal edges,
785 give all abnormals frequency of 0, otherwise distribute the
786 frequency over abnormals (this is the case of noreturn
788 else if (profile_status
== PROFILE_ABSENT
)
792 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
793 if (!(e
->flags
& (EDGE_COMPLEX
| EDGE_FAKE
)))
797 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
798 if (!(e
->flags
& (EDGE_COMPLEX
| EDGE_FAKE
)))
799 e
->probability
= REG_BR_PROB_BASE
/ total
;
805 total
+= EDGE_COUNT (bb
->succs
);
806 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
807 e
->probability
= REG_BR_PROB_BASE
/ total
;
809 if (bb
->index
>= NUM_FIXED_BLOCKS
810 && block_ends_with_condjump_p (bb
)
811 && EDGE_COUNT (bb
->succs
) >= 2)
816 profile_status
= PROFILE_READ
;
817 compute_function_frequency ();
821 fprintf (dump_file
, "%d branches\n", num_branches
);
823 for (i
= 0; i
< 10; i
++)
824 fprintf (dump_file
, "%d%% branches in range %d-%d%%\n",
825 (hist_br_prob
[i
] + hist_br_prob
[19-i
]) * 100 / num_branches
,
828 total_num_branches
+= num_branches
;
829 for (i
= 0; i
< 20; i
++)
830 total_hist_br_prob
[i
] += hist_br_prob
[i
];
832 fputc ('\n', dump_file
);
833 fputc ('\n', dump_file
);
836 free_aux_for_blocks ();
839 /* Load value histograms values whose description is stored in VALUES array
842 CFG_CHECKSUM is the precomputed checksum for the CFG. */
845 compute_value_histograms (histogram_values values
, unsigned cfg_checksum
,
846 unsigned lineno_checksum
)
848 unsigned i
, j
, t
, any
;
849 unsigned n_histogram_counters
[GCOV_N_VALUE_COUNTERS
];
850 gcov_type
*histogram_counts
[GCOV_N_VALUE_COUNTERS
];
851 gcov_type
*act_count
[GCOV_N_VALUE_COUNTERS
];
852 gcov_type
*aact_count
;
854 for (t
= 0; t
< GCOV_N_VALUE_COUNTERS
; t
++)
855 n_histogram_counters
[t
] = 0;
857 for (i
= 0; i
< values
.length (); i
++)
859 histogram_value hist
= values
[i
];
860 n_histogram_counters
[(int) hist
->type
] += hist
->n_counters
;
864 for (t
= 0; t
< GCOV_N_VALUE_COUNTERS
; t
++)
866 if (!n_histogram_counters
[t
])
868 histogram_counts
[t
] = NULL
;
872 histogram_counts
[t
] =
873 get_coverage_counts (COUNTER_FOR_HIST_TYPE (t
),
874 n_histogram_counters
[t
], cfg_checksum
,
875 lineno_checksum
, NULL
);
876 if (histogram_counts
[t
])
878 act_count
[t
] = histogram_counts
[t
];
883 for (i
= 0; i
< values
.length (); i
++)
885 histogram_value hist
= values
[i
];
886 gimple stmt
= hist
->hvalue
.stmt
;
888 t
= (int) hist
->type
;
890 aact_count
= act_count
[t
];
892 act_count
[t
] += hist
->n_counters
;
894 gimple_add_histogram_value (cfun
, stmt
, hist
);
895 hist
->hvalue
.counters
= XNEWVEC (gcov_type
, hist
->n_counters
);
896 for (j
= 0; j
< hist
->n_counters
; j
++)
898 hist
->hvalue
.counters
[j
] = aact_count
[j
];
900 hist
->hvalue
.counters
[j
] = 0;
903 for (t
= 0; t
< GCOV_N_VALUE_COUNTERS
; t
++)
904 free (histogram_counts
[t
]);
907 /* When passed NULL as file_name, initialize.
908 When passed something else, output the necessary commands to change
909 line to LINE and offset to FILE_NAME. */
911 output_location (char const *file_name
, int line
,
912 gcov_position_t
*offset
, basic_block bb
)
914 static char const *prev_file_name
;
915 static int prev_line
;
916 bool name_differs
, line_differs
;
920 prev_file_name
= NULL
;
925 name_differs
= !prev_file_name
|| filename_cmp (file_name
, prev_file_name
);
926 line_differs
= prev_line
!= line
;
928 if (name_differs
|| line_differs
)
932 *offset
= gcov_write_tag (GCOV_TAG_LINES
);
933 gcov_write_unsigned (bb
->index
);
934 name_differs
= line_differs
=true;
937 /* If this is a new source file, then output the
938 file's name to the .bb file. */
941 prev_file_name
= file_name
;
942 gcov_write_unsigned (0);
943 gcov_write_string (prev_file_name
);
947 gcov_write_unsigned (line
);
953 /* Instrument and/or analyze program behavior based on program the CFG.
955 This function creates a representation of the control flow graph (of
956 the function being compiled) that is suitable for the instrumentation
957 of edges and/or converting measured edge counts to counts on the
960 When FLAG_PROFILE_ARCS is nonzero, this function instruments the edges in
961 the flow graph that are needed to reconstruct the dynamic behavior of the
962 flow graph. This data is written to the gcno file for gcov.
964 When FLAG_BRANCH_PROBABILITIES is nonzero, this function reads auxiliary
965 information from the gcda file containing edge count information from
966 previous executions of the function being compiled. In this case, the
967 control flow graph is annotated with actual execution counts by
968 compute_branch_probabilities().
970 Main entry point of this file. */
977 unsigned num_edges
, ignored_edges
;
978 unsigned num_instrumented
;
979 struct edge_list
*el
;
980 histogram_values values
= histogram_values ();
981 unsigned cfg_checksum
, lineno_checksum
;
983 total_num_times_called
++;
985 flow_call_edges_add (NULL
);
986 add_noreturn_fake_exit_edges ();
988 /* We can't handle cyclic regions constructed using abnormal edges.
989 To avoid these we replace every source of abnormal edge by a fake
990 edge from entry node and every destination by fake edge to exit.
991 This keeps graph acyclic and our calculation exact for all normal
992 edges except for exit and entrance ones.
994 We also add fake exit edges for each call and asm statement in the
995 basic, since it may not return. */
999 int need_exit_edge
= 0, need_entry_edge
= 0;
1000 int have_exit_edge
= 0, have_entry_edge
= 0;
1004 /* Functions returning multiple times are not handled by extra edges.
1005 Instead we simply allow negative counts on edges from exit to the
1006 block past call and corresponding probabilities. We can't go
1007 with the extra edges because that would result in flowgraph that
1008 needs to have fake edges outside the spanning tree. */
1010 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1012 gimple_stmt_iterator gsi
;
1015 /* It may happen that there are compiler generated statements
1016 without a locus at all. Go through the basic block from the
1017 last to the first statement looking for a locus. */
1018 for (gsi
= gsi_last_nondebug_bb (bb
);
1020 gsi_prev_nondebug (&gsi
))
1022 last
= gsi_stmt (gsi
);
1023 if (gimple_has_location (last
))
1027 /* Edge with goto locus might get wrong coverage info unless
1028 it is the only edge out of BB.
1029 Don't do that when the locuses match, so
1030 if (blah) goto something;
1031 is not computed twice. */
1033 && gimple_has_location (last
)
1034 && LOCATION_LOCUS (e
->goto_locus
) != UNKNOWN_LOCATION
1035 && !single_succ_p (bb
)
1036 && (LOCATION_FILE (e
->goto_locus
)
1037 != LOCATION_FILE (gimple_location (last
))
1038 || (LOCATION_LINE (e
->goto_locus
)
1039 != LOCATION_LINE (gimple_location (last
)))))
1041 basic_block new_bb
= split_edge (e
);
1042 edge ne
= single_succ_edge (new_bb
);
1043 ne
->goto_locus
= e
->goto_locus
;
1045 if ((e
->flags
& (EDGE_ABNORMAL
| EDGE_ABNORMAL_CALL
))
1046 && e
->dest
!= EXIT_BLOCK_PTR
)
1048 if (e
->dest
== EXIT_BLOCK_PTR
)
1051 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1053 if ((e
->flags
& (EDGE_ABNORMAL
| EDGE_ABNORMAL_CALL
))
1054 && e
->src
!= ENTRY_BLOCK_PTR
)
1055 need_entry_edge
= 1;
1056 if (e
->src
== ENTRY_BLOCK_PTR
)
1057 have_entry_edge
= 1;
1060 if (need_exit_edge
&& !have_exit_edge
)
1063 fprintf (dump_file
, "Adding fake exit edge to bb %i\n",
1065 make_edge (bb
, EXIT_BLOCK_PTR
, EDGE_FAKE
);
1067 if (need_entry_edge
&& !have_entry_edge
)
1070 fprintf (dump_file
, "Adding fake entry edge to bb %i\n",
1072 make_edge (ENTRY_BLOCK_PTR
, bb
, EDGE_FAKE
);
1073 /* Avoid bbs that have both fake entry edge and also some
1074 exit edge. One of those edges wouldn't be added to the
1075 spanning tree, but we can't instrument any of them. */
1076 if (have_exit_edge
|| need_exit_edge
)
1078 gimple_stmt_iterator gsi
;
1082 gsi
= gsi_after_labels (bb
);
1083 gcc_checking_assert (!gsi_end_p (gsi
));
1084 first
= gsi_stmt (gsi
);
1085 if (is_gimple_debug (first
))
1087 gsi_next_nondebug (&gsi
);
1088 gcc_checking_assert (!gsi_end_p (gsi
));
1089 first
= gsi_stmt (gsi
);
1091 /* Don't split the bbs containing __builtin_setjmp_receiver
1092 or __builtin_setjmp_dispatcher calls. These are very
1093 special and don't expect anything to be inserted before
1095 if (is_gimple_call (first
)
1096 && (((fndecl
= gimple_call_fndecl (first
)) != NULL
1097 && DECL_BUILT_IN_CLASS (fndecl
) == BUILT_IN_NORMAL
1098 && (DECL_FUNCTION_CODE (fndecl
)
1099 == BUILT_IN_SETJMP_RECEIVER
1100 || (DECL_FUNCTION_CODE (fndecl
)
1101 == BUILT_IN_SETJMP_DISPATCHER
)))
1102 || gimple_call_flags (first
) & ECF_RETURNS_TWICE
))
1106 fprintf (dump_file
, "Splitting bb %i after labels\n",
1108 split_block_after_labels (bb
);
1113 el
= create_edge_list ();
1114 num_edges
= NUM_EDGES (el
);
1115 alloc_aux_for_edges (sizeof (struct edge_info
));
1117 /* The basic blocks are expected to be numbered sequentially. */
1121 for (i
= 0 ; i
< num_edges
; i
++)
1123 edge e
= INDEX_EDGE (el
, i
);
1126 /* Mark edges we've replaced by fake edges above as ignored. */
1127 if ((e
->flags
& (EDGE_ABNORMAL
| EDGE_ABNORMAL_CALL
))
1128 && e
->src
!= ENTRY_BLOCK_PTR
&& e
->dest
!= EXIT_BLOCK_PTR
)
1130 EDGE_INFO (e
)->ignore
= 1;
1135 /* Create spanning tree from basic block graph, mark each edge that is
1136 on the spanning tree. We insert as many abnormal and critical edges
1137 as possible to minimize number of edge splits necessary. */
1139 find_spanning_tree (el
);
1141 /* Fake edges that are not on the tree will not be instrumented, so
1142 mark them ignored. */
1143 for (num_instrumented
= i
= 0; i
< num_edges
; i
++)
1145 edge e
= INDEX_EDGE (el
, i
);
1146 struct edge_info
*inf
= EDGE_INFO (e
);
1148 if (inf
->ignore
|| inf
->on_tree
)
1150 else if (e
->flags
& EDGE_FAKE
)
1159 total_num_blocks
+= n_basic_blocks
;
1161 fprintf (dump_file
, "%d basic blocks\n", n_basic_blocks
);
1163 total_num_edges
+= num_edges
;
1165 fprintf (dump_file
, "%d edges\n", num_edges
);
1167 total_num_edges_ignored
+= ignored_edges
;
1169 fprintf (dump_file
, "%d ignored edges\n", ignored_edges
);
1171 total_num_edges_instrumented
+= num_instrumented
;
1173 fprintf (dump_file
, "%d instrumentation edges\n", num_instrumented
);
1175 /* Compute two different checksums. Note that we want to compute
1176 the checksum in only once place, since it depends on the shape
1177 of the control flow which can change during
1178 various transformations. */
1179 cfg_checksum
= coverage_compute_cfg_checksum ();
1180 lineno_checksum
= coverage_compute_lineno_checksum ();
1182 /* Write the data from which gcov can reconstruct the basic block
1183 graph and function line numbers (the gcno file). */
1184 if (coverage_begin_function (lineno_checksum
, cfg_checksum
))
1186 gcov_position_t offset
;
1188 /* Basic block flags */
1189 offset
= gcov_write_tag (GCOV_TAG_BLOCKS
);
1190 for (i
= 0; i
!= (unsigned) (n_basic_blocks
); i
++)
1191 gcov_write_unsigned (0);
1192 gcov_write_length (offset
);
1195 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, EXIT_BLOCK_PTR
, next_bb
)
1200 offset
= gcov_write_tag (GCOV_TAG_ARCS
);
1201 gcov_write_unsigned (bb
->index
);
1203 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1205 struct edge_info
*i
= EDGE_INFO (e
);
1208 unsigned flag_bits
= 0;
1211 flag_bits
|= GCOV_ARC_ON_TREE
;
1212 if (e
->flags
& EDGE_FAKE
)
1213 flag_bits
|= GCOV_ARC_FAKE
;
1214 if (e
->flags
& EDGE_FALLTHRU
)
1215 flag_bits
|= GCOV_ARC_FALLTHROUGH
;
1216 /* On trees we don't have fallthru flags, but we can
1217 recompute them from CFG shape. */
1218 if (e
->flags
& (EDGE_TRUE_VALUE
| EDGE_FALSE_VALUE
)
1219 && e
->src
->next_bb
== e
->dest
)
1220 flag_bits
|= GCOV_ARC_FALLTHROUGH
;
1222 gcov_write_unsigned (e
->dest
->index
);
1223 gcov_write_unsigned (flag_bits
);
1227 gcov_write_length (offset
);
1231 /* Initialize the output. */
1232 output_location (NULL
, 0, NULL
, NULL
);
1236 gimple_stmt_iterator gsi
;
1237 gcov_position_t offset
= 0;
1239 if (bb
== ENTRY_BLOCK_PTR
->next_bb
)
1241 expanded_location curr_location
=
1242 expand_location (DECL_SOURCE_LOCATION (current_function_decl
));
1243 output_location (curr_location
.file
, curr_location
.line
,
1247 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1249 gimple stmt
= gsi_stmt (gsi
);
1250 if (gimple_has_location (stmt
))
1251 output_location (gimple_filename (stmt
), gimple_lineno (stmt
),
1255 /* Notice GOTO expressions eliminated while constructing the CFG. */
1256 if (single_succ_p (bb
)
1257 && LOCATION_LOCUS (single_succ_edge (bb
)->goto_locus
)
1258 != UNKNOWN_LOCATION
)
1260 expanded_location curr_location
1261 = expand_location (single_succ_edge (bb
)->goto_locus
);
1262 output_location (curr_location
.file
, curr_location
.line
,
1268 /* A file of NULL indicates the end of run. */
1269 gcov_write_unsigned (0);
1270 gcov_write_string (NULL
);
1271 gcov_write_length (offset
);
1276 if (flag_profile_values
)
1277 gimple_find_values_to_profile (&values
);
1279 if (flag_branch_probabilities
)
1281 compute_branch_probabilities (cfg_checksum
, lineno_checksum
);
1282 if (flag_profile_values
)
1283 compute_value_histograms (values
, cfg_checksum
, lineno_checksum
);
1286 remove_fake_edges ();
1288 /* For each edge not on the spanning tree, add counting code. */
1289 if (profile_arc_flag
1290 && coverage_counter_alloc (GCOV_COUNTER_ARCS
, num_instrumented
))
1292 unsigned n_instrumented
;
1294 gimple_init_edge_profiler ();
1296 n_instrumented
= instrument_edges (el
);
1298 gcc_assert (n_instrumented
== num_instrumented
);
1300 if (flag_profile_values
)
1301 instrument_values (values
);
1303 /* Commit changes done by instrumentation. */
1304 gsi_commit_edge_inserts ();
1307 free_aux_for_edges ();
1310 free_edge_list (el
);
1311 coverage_end_function (lineno_checksum
, cfg_checksum
);
1314 /* Union find algorithm implementation for the basic blocks using
1318 find_group (basic_block bb
)
1320 basic_block group
= bb
, bb1
;
1322 while ((basic_block
) group
->aux
!= group
)
1323 group
= (basic_block
) group
->aux
;
1325 /* Compress path. */
1326 while ((basic_block
) bb
->aux
!= group
)
1328 bb1
= (basic_block
) bb
->aux
;
1329 bb
->aux
= (void *) group
;
1336 union_groups (basic_block bb1
, basic_block bb2
)
1338 basic_block bb1g
= find_group (bb1
);
1339 basic_block bb2g
= find_group (bb2
);
1341 /* ??? I don't have a place for the rank field. OK. Lets go w/o it,
1342 this code is unlikely going to be performance problem anyway. */
1343 gcc_assert (bb1g
!= bb2g
);
1348 /* This function searches all of the edges in the program flow graph, and puts
1349 as many bad edges as possible onto the spanning tree. Bad edges include
1350 abnormals edges, which can't be instrumented at the moment. Since it is
1351 possible for fake edges to form a cycle, we will have to develop some
1352 better way in the future. Also put critical edges to the tree, since they
1353 are more expensive to instrument. */
1356 find_spanning_tree (struct edge_list
*el
)
1359 int num_edges
= NUM_EDGES (el
);
1362 /* We use aux field for standard union-find algorithm. */
1363 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, NULL
, next_bb
)
1366 /* Add fake edge exit to entry we can't instrument. */
1367 union_groups (EXIT_BLOCK_PTR
, ENTRY_BLOCK_PTR
);
1369 /* First add all abnormal edges to the tree unless they form a cycle. Also
1370 add all edges to EXIT_BLOCK_PTR to avoid inserting profiling code behind
1371 setting return value from function. */
1372 for (i
= 0; i
< num_edges
; i
++)
1374 edge e
= INDEX_EDGE (el
, i
);
1375 if (((e
->flags
& (EDGE_ABNORMAL
| EDGE_ABNORMAL_CALL
| EDGE_FAKE
))
1376 || e
->dest
== EXIT_BLOCK_PTR
)
1377 && !EDGE_INFO (e
)->ignore
1378 && (find_group (e
->src
) != find_group (e
->dest
)))
1381 fprintf (dump_file
, "Abnormal edge %d to %d put to tree\n",
1382 e
->src
->index
, e
->dest
->index
);
1383 EDGE_INFO (e
)->on_tree
= 1;
1384 union_groups (e
->src
, e
->dest
);
1388 /* Now insert all critical edges to the tree unless they form a cycle. */
1389 for (i
= 0; i
< num_edges
; i
++)
1391 edge e
= INDEX_EDGE (el
, i
);
1392 if (EDGE_CRITICAL_P (e
) && !EDGE_INFO (e
)->ignore
1393 && find_group (e
->src
) != find_group (e
->dest
))
1396 fprintf (dump_file
, "Critical edge %d to %d put to tree\n",
1397 e
->src
->index
, e
->dest
->index
);
1398 EDGE_INFO (e
)->on_tree
= 1;
1399 union_groups (e
->src
, e
->dest
);
1403 /* And now the rest. */
1404 for (i
= 0; i
< num_edges
; i
++)
1406 edge e
= INDEX_EDGE (el
, i
);
1407 if (!EDGE_INFO (e
)->ignore
1408 && find_group (e
->src
) != find_group (e
->dest
))
1411 fprintf (dump_file
, "Normal edge %d to %d put to tree\n",
1412 e
->src
->index
, e
->dest
->index
);
1413 EDGE_INFO (e
)->on_tree
= 1;
1414 union_groups (e
->src
, e
->dest
);
1418 clear_aux_for_blocks ();
1421 /* Perform file-level initialization for branch-prob processing. */
1424 init_branch_prob (void)
1428 total_num_blocks
= 0;
1429 total_num_edges
= 0;
1430 total_num_edges_ignored
= 0;
1431 total_num_edges_instrumented
= 0;
1432 total_num_blocks_created
= 0;
1433 total_num_passes
= 0;
1434 total_num_times_called
= 0;
1435 total_num_branches
= 0;
1436 for (i
= 0; i
< 20; i
++)
1437 total_hist_br_prob
[i
] = 0;
1440 /* Performs file-level cleanup after branch-prob processing
1444 end_branch_prob (void)
1448 fprintf (dump_file
, "\n");
1449 fprintf (dump_file
, "Total number of blocks: %d\n",
1451 fprintf (dump_file
, "Total number of edges: %d\n", total_num_edges
);
1452 fprintf (dump_file
, "Total number of ignored edges: %d\n",
1453 total_num_edges_ignored
);
1454 fprintf (dump_file
, "Total number of instrumented edges: %d\n",
1455 total_num_edges_instrumented
);
1456 fprintf (dump_file
, "Total number of blocks created: %d\n",
1457 total_num_blocks_created
);
1458 fprintf (dump_file
, "Total number of graph solution passes: %d\n",
1460 if (total_num_times_called
!= 0)
1461 fprintf (dump_file
, "Average number of graph solution passes: %d\n",
1462 (total_num_passes
+ (total_num_times_called
>> 1))
1463 / total_num_times_called
);
1464 fprintf (dump_file
, "Total number of branches: %d\n",
1465 total_num_branches
);
1466 if (total_num_branches
)
1470 for (i
= 0; i
< 10; i
++)
1471 fprintf (dump_file
, "%d%% branches in range %d-%d%%\n",
1472 (total_hist_br_prob
[i
] + total_hist_br_prob
[19-i
]) * 100
1473 / total_num_branches
, 5*i
, 5*i
+5);