1 /* Calculate branch probabilities, and basic block execution counts.
2 Copyright (C) 1990-2018 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"
60 #include "diagnostic-core.h"
62 #include "value-prof.h"
63 #include "gimple-iterator.h"
70 /* Map from BBs/edges to gcov counters. */
71 vec
<gcov_type
> bb_gcov_counts
;
72 hash_map
<edge
,gcov_type
> *edge_gcov_counts
;
74 struct bb_profile_info
{
75 unsigned int count_valid
: 1;
77 /* Number of successor and predecessor edges. */
82 #define BB_INFO(b) ((struct bb_profile_info *) (b)->aux)
85 /* Counter summary from the last set of coverage counts read. */
87 gcov_summary
*profile_info
;
89 /* Collect statistics on the performance of this pass for the entire source
92 static int total_num_blocks
;
93 static int total_num_edges
;
94 static int total_num_edges_ignored
;
95 static int total_num_edges_instrumented
;
96 static int total_num_blocks_created
;
97 static int total_num_passes
;
98 static int total_num_times_called
;
99 static int total_hist_br_prob
[20];
100 static int total_num_branches
;
102 /* Forward declarations. */
103 static void find_spanning_tree (struct edge_list
*);
105 /* Add edge instrumentation code to the entire insn chain.
107 F is the first insn of the chain.
108 NUM_BLOCKS is the number of basic blocks found in F. */
111 instrument_edges (struct edge_list
*el
)
113 unsigned num_instr_edges
= 0;
114 int num_edges
= NUM_EDGES (el
);
117 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
), NULL
, next_bb
)
122 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
124 struct edge_profile_info
*inf
= EDGE_INFO (e
);
126 if (!inf
->ignore
&& !inf
->on_tree
)
128 gcc_assert (!(e
->flags
& EDGE_ABNORMAL
));
130 fprintf (dump_file
, "Edge %d to %d instrumented%s\n",
131 e
->src
->index
, e
->dest
->index
,
132 EDGE_CRITICAL_P (e
) ? " (and split)" : "");
133 gimple_gen_edge_profiler (num_instr_edges
++, e
);
138 total_num_blocks_created
+= num_edges
;
140 fprintf (dump_file
, "%d edges instrumented\n", num_instr_edges
);
141 return num_instr_edges
;
144 /* Add code to measure histograms for values in list VALUES. */
146 instrument_values (histogram_values values
)
150 /* Emit code to generate the histograms before the insns. */
152 for (i
= 0; i
< values
.length (); i
++)
154 histogram_value hist
= values
[i
];
155 unsigned t
= COUNTER_FOR_HIST_TYPE (hist
->type
);
157 if (!coverage_counter_alloc (t
, hist
->n_counters
))
162 case HIST_TYPE_INTERVAL
:
163 gimple_gen_interval_profiler (hist
, t
, 0);
167 gimple_gen_pow2_profiler (hist
, t
, 0);
170 case HIST_TYPE_SINGLE_VALUE
:
171 gimple_gen_one_value_profiler (hist
, t
, 0);
174 case HIST_TYPE_INDIR_CALL
:
175 case HIST_TYPE_INDIR_CALL_TOPN
:
176 gimple_gen_ic_profiler (hist
, t
, 0);
179 case HIST_TYPE_AVERAGE
:
180 gimple_gen_average_profiler (hist
, t
, 0);
184 gimple_gen_ior_profiler (hist
, t
, 0);
187 case HIST_TYPE_TIME_PROFILE
:
188 gimple_gen_time_profiler (t
, 0);
198 /* Computes hybrid profile for all matching entries in da_file.
200 CFG_CHECKSUM is the precomputed checksum for the CFG. */
203 get_exec_counts (unsigned cfg_checksum
, unsigned lineno_checksum
)
205 unsigned num_edges
= 0;
209 /* Count the edges to be (possibly) instrumented. */
210 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
), NULL
, next_bb
)
215 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
216 if (!EDGE_INFO (e
)->ignore
&& !EDGE_INFO (e
)->on_tree
)
220 counts
= get_coverage_counts (GCOV_COUNTER_ARCS
, cfg_checksum
,
229 is_edge_inconsistent (vec
<edge
, va_gc
> *edges
)
233 FOR_EACH_EDGE (e
, ei
, edges
)
235 if (!EDGE_INFO (e
)->ignore
)
237 if (edge_gcov_count (e
) < 0
238 && (!(e
->flags
& EDGE_FAKE
)
239 || !block_ends_with_call_p (e
->src
)))
244 "Edge %i->%i is inconsistent, count%" PRId64
,
245 e
->src
->index
, e
->dest
->index
, edge_gcov_count (e
));
246 dump_bb (dump_file
, e
->src
, 0, TDF_DETAILS
);
247 dump_bb (dump_file
, e
->dest
, 0, TDF_DETAILS
);
257 correct_negative_edge_counts (void)
263 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
), NULL
, next_bb
)
265 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
267 if (edge_gcov_count (e
) < 0)
268 edge_gcov_count (e
) = 0;
273 /* Check consistency.
274 Return true if inconsistency is found. */
276 is_inconsistent (void)
279 bool inconsistent
= false;
280 FOR_EACH_BB_FN (bb
, cfun
)
282 inconsistent
|= is_edge_inconsistent (bb
->preds
);
283 if (!dump_file
&& inconsistent
)
285 inconsistent
|= is_edge_inconsistent (bb
->succs
);
286 if (!dump_file
&& inconsistent
)
288 if (bb_gcov_count (bb
) < 0)
292 fprintf (dump_file
, "BB %i count is negative "
296 dump_bb (dump_file
, bb
, 0, TDF_DETAILS
);
300 if (bb_gcov_count (bb
) != sum_edge_counts (bb
->preds
))
304 fprintf (dump_file
, "BB %i count does not match sum of incoming edges "
305 "%" PRId64
" should be %" PRId64
,
308 sum_edge_counts (bb
->preds
));
309 dump_bb (dump_file
, bb
, 0, TDF_DETAILS
);
313 if (bb_gcov_count (bb
) != sum_edge_counts (bb
->succs
) &&
314 ! (find_edge (bb
, EXIT_BLOCK_PTR_FOR_FN (cfun
)) != NULL
315 && block_ends_with_call_p (bb
)))
319 fprintf (dump_file
, "BB %i count does not match sum of outgoing edges "
320 "%" PRId64
" should be %" PRId64
,
323 sum_edge_counts (bb
->succs
));
324 dump_bb (dump_file
, bb
, 0, TDF_DETAILS
);
328 if (!dump_file
&& inconsistent
)
335 /* Set each basic block count to the sum of its outgoing edge counts */
340 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
), NULL
, next_bb
)
342 bb_gcov_count (bb
) = sum_edge_counts (bb
->succs
);
343 gcc_assert (bb_gcov_count (bb
) >= 0);
347 /* Reads profile data and returns total number of edge counts read */
349 read_profile_edge_counts (gcov_type
*exec_counts
)
353 int exec_counts_pos
= 0;
354 /* For each edge not on the spanning tree, set its execution count from
356 /* The first count in the .da file is the number of times that the function
357 was entered. This is the exec_count for block zero. */
359 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
), NULL
, next_bb
)
364 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
365 if (!EDGE_INFO (e
)->ignore
&& !EDGE_INFO (e
)->on_tree
)
369 edge_gcov_count (e
) = exec_counts
[exec_counts_pos
++];
371 edge_gcov_count (e
) = 0;
373 EDGE_INFO (e
)->count_valid
= 1;
374 BB_INFO (bb
)->succ_count
--;
375 BB_INFO (e
->dest
)->pred_count
--;
378 fprintf (dump_file
, "\nRead edge from %i to %i, count:",
379 bb
->index
, e
->dest
->index
);
380 fprintf (dump_file
, "%" PRId64
,
381 (int64_t) edge_gcov_count (e
));
390 /* Compute the branch probabilities for the various branches.
391 Annotate them accordingly.
393 CFG_CHECKSUM is the precomputed checksum for the CFG. */
396 compute_branch_probabilities (unsigned cfg_checksum
, unsigned lineno_checksum
)
403 int hist_br_prob
[20];
405 gcov_type
*exec_counts
= get_exec_counts (cfg_checksum
, lineno_checksum
);
406 int inconsistent
= 0;
408 /* Very simple sanity checks so we catch bugs in our profiling code. */
412 fprintf (dump_file
, "Profile info is missing; giving up\n");
416 bb_gcov_counts
.safe_grow_cleared (last_basic_block_for_fn (cfun
));
417 edge_gcov_counts
= new hash_map
<edge
,gcov_type
>;
419 /* Attach extra info block to each bb. */
420 alloc_aux_for_blocks (sizeof (struct bb_profile_info
));
421 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
), NULL
, next_bb
)
426 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
427 if (!EDGE_INFO (e
)->ignore
)
428 BB_INFO (bb
)->succ_count
++;
429 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
430 if (!EDGE_INFO (e
)->ignore
)
431 BB_INFO (bb
)->pred_count
++;
434 /* Avoid predicting entry on exit nodes. */
435 BB_INFO (EXIT_BLOCK_PTR_FOR_FN (cfun
))->succ_count
= 2;
436 BB_INFO (ENTRY_BLOCK_PTR_FOR_FN (cfun
))->pred_count
= 2;
438 num_edges
= read_profile_edge_counts (exec_counts
);
441 fprintf (dump_file
, "\n%d edge counts read\n", num_edges
);
443 /* For every block in the file,
444 - if every exit/entrance edge has a known count, then set the block count
445 - if the block count is known, and every exit/entrance edge but one has
446 a known execution count, then set the count of the remaining edge
448 As edge counts are set, decrement the succ/pred count, but don't delete
449 the edge, that way we can easily tell when all edges are known, or only
450 one edge is unknown. */
452 /* The order that the basic blocks are iterated through is important.
453 Since the code that finds spanning trees starts with block 0, low numbered
454 edges are put on the spanning tree in preference to high numbered edges.
455 Hence, most instrumented edges are at the end. Graph solving works much
456 faster if we propagate numbers from the end to the start.
458 This takes an average of slightly more than 3 passes. */
466 FOR_BB_BETWEEN (bb
, EXIT_BLOCK_PTR_FOR_FN (cfun
), NULL
, prev_bb
)
468 struct bb_profile_info
*bi
= BB_INFO (bb
);
469 if (! bi
->count_valid
)
471 if (bi
->succ_count
== 0)
477 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
478 total
+= edge_gcov_count (e
);
479 bb_gcov_count (bb
) = total
;
483 else if (bi
->pred_count
== 0)
489 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
490 total
+= edge_gcov_count (e
);
491 bb_gcov_count (bb
) = total
;
498 if (bi
->succ_count
== 1)
504 /* One of the counts will be invalid, but it is zero,
505 so adding it in also doesn't hurt. */
506 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
507 total
+= edge_gcov_count (e
);
509 /* Search for the invalid edge, and set its count. */
510 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
511 if (! EDGE_INFO (e
)->count_valid
&& ! EDGE_INFO (e
)->ignore
)
514 /* Calculate count for remaining edge by conservation. */
515 total
= bb_gcov_count (bb
) - total
;
518 EDGE_INFO (e
)->count_valid
= 1;
519 edge_gcov_count (e
) = total
;
522 BB_INFO (e
->dest
)->pred_count
--;
525 if (bi
->pred_count
== 1)
531 /* One of the counts will be invalid, but it is zero,
532 so adding it in also doesn't hurt. */
533 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
534 total
+= edge_gcov_count (e
);
536 /* Search for the invalid edge, and set its count. */
537 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
538 if (!EDGE_INFO (e
)->count_valid
&& !EDGE_INFO (e
)->ignore
)
541 /* Calculate count for remaining edge by conservation. */
542 total
= bb_gcov_count (bb
) - total
+ edge_gcov_count (e
);
545 EDGE_INFO (e
)->count_valid
= 1;
546 edge_gcov_count (e
) = total
;
549 BB_INFO (e
->src
)->succ_count
--;
556 total_num_passes
+= passes
;
558 fprintf (dump_file
, "Graph solving took %d passes.\n\n", passes
);
560 /* If the graph has been correctly solved, every block will have a
561 succ and pred count of zero. */
562 FOR_EACH_BB_FN (bb
, cfun
)
564 gcc_assert (!BB_INFO (bb
)->succ_count
&& !BB_INFO (bb
)->pred_count
);
567 /* Check for inconsistent basic block counts */
568 inconsistent
= is_inconsistent ();
572 if (flag_profile_correction
)
574 /* Inconsistency detected. Make it flow-consistent. */
575 static int informed
= 0;
576 if (dump_enabled_p () && informed
== 0)
579 dump_printf_loc (MSG_NOTE
,
580 dump_user_location_t::from_location_t (input_location
),
581 "correcting inconsistent profile data\n");
583 correct_negative_edge_counts ();
584 /* Set bb counts to the sum of the outgoing edge counts */
587 fprintf (dump_file
, "\nCalling mcf_smooth_cfg\n");
591 error ("corrupted profile info: profile data is not flow-consistent");
594 /* For every edge, calculate its branch probability and add a reg_note
595 to the branch insn to indicate this. */
597 for (i
= 0; i
< 20; i
++)
601 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
), NULL
, next_bb
)
606 if (bb_gcov_count (bb
) < 0)
608 error ("corrupted profile info: number of iterations for basic block %d thought to be %i",
609 bb
->index
, (int)bb_gcov_count (bb
));
610 bb_gcov_count (bb
) = 0;
612 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
614 /* Function may return twice in the cased the called function is
615 setjmp or calls fork, but we can't represent this by extra
616 edge from the entry, since extra edge from the exit is
617 already present. We get negative frequency from the entry
619 if ((edge_gcov_count (e
) < 0
620 && e
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
621 || (edge_gcov_count (e
) > bb_gcov_count (bb
)
622 && e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)))
624 if (block_ends_with_call_p (bb
))
625 edge_gcov_count (e
) = edge_gcov_count (e
) < 0
626 ? 0 : bb_gcov_count (bb
);
628 if (edge_gcov_count (e
) < 0
629 || edge_gcov_count (e
) > bb_gcov_count (bb
))
631 error ("corrupted profile info: number of executions for edge %d-%d thought to be %i",
632 e
->src
->index
, e
->dest
->index
,
633 (int)edge_gcov_count (e
));
634 edge_gcov_count (e
) = bb_gcov_count (bb
) / 2;
637 if (bb_gcov_count (bb
))
639 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
640 e
->probability
= profile_probability::probability_in_gcov_type
641 (edge_gcov_count (e
), bb_gcov_count (bb
));
642 if (bb
->index
>= NUM_FIXED_BLOCKS
643 && block_ends_with_condjump_p (bb
)
644 && EDGE_COUNT (bb
->succs
) >= 2)
650 /* Find the branch edge. It is possible that we do have fake
652 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
653 if (!(e
->flags
& (EDGE_FAKE
| EDGE_FALLTHRU
)))
656 prob
= e
->probability
.to_reg_br_prob_base ();
657 index
= prob
* 20 / REG_BR_PROB_BASE
;
661 hist_br_prob
[index
]++;
666 /* As a last resort, distribute the probabilities evenly.
667 Use simple heuristics that if there are normal edges,
668 give all abnormals frequency of 0, otherwise distribute the
669 frequency over abnormals (this is the case of noreturn
671 else if (profile_status_for_fn (cfun
) == PROFILE_ABSENT
)
675 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
676 if (!(e
->flags
& (EDGE_COMPLEX
| EDGE_FAKE
)))
680 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
681 if (!(e
->flags
& (EDGE_COMPLEX
| EDGE_FAKE
)))
683 = profile_probability::guessed_always ().apply_scale (1, total
);
685 e
->probability
= profile_probability::never ();
689 total
+= EDGE_COUNT (bb
->succs
);
690 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
692 = profile_probability::guessed_always ().apply_scale (1, total
);
694 if (bb
->index
>= NUM_FIXED_BLOCKS
695 && block_ends_with_condjump_p (bb
)
696 && EDGE_COUNT (bb
->succs
) >= 2)
702 profile_status_for_fn (cfun
) = PROFILE_READ
;
704 /* If we have real data, use them! */
705 if (bb_gcov_count (ENTRY_BLOCK_PTR_FOR_FN (cfun
))
706 || !flag_guess_branch_prob
)
707 FOR_ALL_BB_FN (bb
, cfun
)
708 bb
->count
= profile_count::from_gcov_type (bb_gcov_count (bb
));
709 /* If function was not trained, preserve local estimates including statically
710 determined zero counts. */
711 else if (profile_status_for_fn (cfun
) == PROFILE_READ
)
712 FOR_ALL_BB_FN (bb
, cfun
)
713 if (!(bb
->count
== profile_count::zero ()))
714 bb
->count
= bb
->count
.global0 ();
716 bb_gcov_counts
.release ();
717 delete edge_gcov_counts
;
718 edge_gcov_counts
= NULL
;
720 update_max_bb_count ();
724 fprintf (dump_file
, " Profile feedback for function");
725 fprintf (dump_file
, ((profile_status_for_fn (cfun
) == PROFILE_READ
)
727 : " is not available \n"));
729 fprintf (dump_file
, "%d branches\n", num_branches
);
731 for (i
= 0; i
< 10; i
++)
732 fprintf (dump_file
, "%d%% branches in range %d-%d%%\n",
733 (hist_br_prob
[i
] + hist_br_prob
[19-i
]) * 100 / num_branches
,
736 total_num_branches
+= num_branches
;
737 for (i
= 0; i
< 20; i
++)
738 total_hist_br_prob
[i
] += hist_br_prob
[i
];
740 fputc ('\n', dump_file
);
741 fputc ('\n', dump_file
);
744 free_aux_for_blocks ();
747 /* Load value histograms values whose description is stored in VALUES array
750 CFG_CHECKSUM is the precomputed checksum for the CFG. */
753 compute_value_histograms (histogram_values values
, unsigned cfg_checksum
,
754 unsigned lineno_checksum
)
756 unsigned i
, j
, t
, any
;
757 unsigned n_histogram_counters
[GCOV_N_VALUE_COUNTERS
];
758 gcov_type
*histogram_counts
[GCOV_N_VALUE_COUNTERS
];
759 gcov_type
*act_count
[GCOV_N_VALUE_COUNTERS
];
760 gcov_type
*aact_count
;
761 struct cgraph_node
*node
;
763 for (t
= 0; t
< GCOV_N_VALUE_COUNTERS
; t
++)
764 n_histogram_counters
[t
] = 0;
766 for (i
= 0; i
< values
.length (); i
++)
768 histogram_value hist
= values
[i
];
769 n_histogram_counters
[(int) hist
->type
] += hist
->n_counters
;
773 for (t
= 0; t
< GCOV_N_VALUE_COUNTERS
; t
++)
775 if (!n_histogram_counters
[t
])
777 histogram_counts
[t
] = NULL
;
781 histogram_counts
[t
] = get_coverage_counts (COUNTER_FOR_HIST_TYPE (t
),
784 if (histogram_counts
[t
])
786 act_count
[t
] = histogram_counts
[t
];
791 for (i
= 0; i
< values
.length (); i
++)
793 histogram_value hist
= values
[i
];
794 gimple
*stmt
= hist
->hvalue
.stmt
;
796 t
= (int) hist
->type
;
798 aact_count
= act_count
[t
];
801 act_count
[t
] += hist
->n_counters
;
803 gimple_add_histogram_value (cfun
, stmt
, hist
);
804 hist
->hvalue
.counters
= XNEWVEC (gcov_type
, hist
->n_counters
);
805 for (j
= 0; j
< hist
->n_counters
; j
++)
807 hist
->hvalue
.counters
[j
] = aact_count
[j
];
809 hist
->hvalue
.counters
[j
] = 0;
811 /* Time profiler counter is not related to any statement,
812 so that we have to read the counter and set the value to
813 the corresponding call graph node. */
814 if (hist
->type
== HIST_TYPE_TIME_PROFILE
)
816 node
= cgraph_node::get (hist
->fun
->decl
);
817 node
->tp_first_run
= hist
->hvalue
.counters
[0];
820 fprintf (dump_file
, "Read tp_first_run: %d\n", node
->tp_first_run
);
824 for (t
= 0; t
< GCOV_N_VALUE_COUNTERS
; t
++)
825 free (histogram_counts
[t
]);
828 /* Location triplet which records a location. */
829 struct location_triplet
831 const char *filename
;
836 /* Traits class for streamed_locations hash set below. */
838 struct location_triplet_hash
: typed_noop_remove
<location_triplet
>
840 typedef location_triplet value_type
;
841 typedef location_triplet compare_type
;
844 hash (const location_triplet
&ref
)
846 inchash::hash
hstate (0);
848 hstate
.add_int (strlen (ref
.filename
));
849 hstate
.add_int (ref
.lineno
);
850 hstate
.add_int (ref
.bb_index
);
851 return hstate
.end ();
855 equal (const location_triplet
&ref1
, const location_triplet
&ref2
)
857 return ref1
.lineno
== ref2
.lineno
858 && ref1
.bb_index
== ref2
.bb_index
859 && ref1
.filename
!= NULL
860 && ref2
.filename
!= NULL
861 && strcmp (ref1
.filename
, ref2
.filename
) == 0;
865 mark_deleted (location_triplet
&ref
)
871 mark_empty (location_triplet
&ref
)
877 is_deleted (const location_triplet
&ref
)
879 return ref
.lineno
== -1;
883 is_empty (const location_triplet
&ref
)
885 return ref
.lineno
== -2;
892 /* When passed NULL as file_name, initialize.
893 When passed something else, output the necessary commands to change
894 line to LINE and offset to FILE_NAME. */
896 output_location (hash_set
<location_triplet_hash
> *streamed_locations
,
897 char const *file_name
, int line
,
898 gcov_position_t
*offset
, basic_block bb
)
900 static char const *prev_file_name
;
901 static int prev_line
;
902 bool name_differs
, line_differs
;
904 location_triplet triplet
;
905 triplet
.filename
= file_name
;
906 triplet
.lineno
= line
;
907 triplet
.bb_index
= bb
? bb
->index
: 0;
909 if (streamed_locations
->add (triplet
))
914 prev_file_name
= NULL
;
919 name_differs
= !prev_file_name
|| filename_cmp (file_name
, prev_file_name
);
920 line_differs
= prev_line
!= line
;
924 *offset
= gcov_write_tag (GCOV_TAG_LINES
);
925 gcov_write_unsigned (bb
->index
);
926 name_differs
= line_differs
= true;
929 /* If this is a new source file, then output the
930 file's name to the .bb file. */
933 prev_file_name
= file_name
;
934 gcov_write_unsigned (0);
935 gcov_write_filename (prev_file_name
);
939 gcov_write_unsigned (line
);
944 /* Helper for qsort so edges get sorted from highest frequency to smallest.
945 This controls the weight for minimal spanning tree algorithm */
947 compare_freqs (const void *p1
, const void *p2
)
949 const_edge e1
= *(const const_edge
*)p1
;
950 const_edge e2
= *(const const_edge
*)p2
;
952 /* Critical edges needs to be split which introduce extra control flow.
953 Make them more heavy. */
954 int m1
= EDGE_CRITICAL_P (e1
) ? 2 : 1;
955 int m2
= EDGE_CRITICAL_P (e2
) ? 2 : 1;
957 if (EDGE_FREQUENCY (e1
) * m1
+ m1
!= EDGE_FREQUENCY (e2
) * m2
+ m2
)
958 return EDGE_FREQUENCY (e2
) * m2
+ m2
- EDGE_FREQUENCY (e1
) * m1
- m1
;
959 /* Stabilize sort. */
960 if (e1
->src
->index
!= e2
->src
->index
)
961 return e2
->src
->index
- e1
->src
->index
;
962 return e2
->dest
->index
- e1
->dest
->index
;
965 /* Instrument and/or analyze program behavior based on program the CFG.
967 This function creates a representation of the control flow graph (of
968 the function being compiled) that is suitable for the instrumentation
969 of edges and/or converting measured edge counts to counts on the
972 When FLAG_PROFILE_ARCS is nonzero, this function instruments the edges in
973 the flow graph that are needed to reconstruct the dynamic behavior of the
974 flow graph. This data is written to the gcno file for gcov.
976 When FLAG_BRANCH_PROBABILITIES is nonzero, this function reads auxiliary
977 information from the gcda file containing edge count information from
978 previous executions of the function being compiled. In this case, the
979 control flow graph is annotated with actual execution counts by
980 compute_branch_probabilities().
982 Main entry point of this file. */
989 unsigned num_edges
, ignored_edges
;
990 unsigned num_instrumented
;
991 struct edge_list
*el
;
992 histogram_values values
= histogram_values ();
993 unsigned cfg_checksum
, lineno_checksum
;
995 total_num_times_called
++;
997 flow_call_edges_add (NULL
);
998 add_noreturn_fake_exit_edges ();
1000 hash_set
<location_triplet_hash
> streamed_locations
;
1002 /* We can't handle cyclic regions constructed using abnormal edges.
1003 To avoid these we replace every source of abnormal edge by a fake
1004 edge from entry node and every destination by fake edge to exit.
1005 This keeps graph acyclic and our calculation exact for all normal
1006 edges except for exit and entrance ones.
1008 We also add fake exit edges for each call and asm statement in the
1009 basic, since it may not return. */
1011 FOR_EACH_BB_FN (bb
, cfun
)
1013 int need_exit_edge
= 0, need_entry_edge
= 0;
1014 int have_exit_edge
= 0, have_entry_edge
= 0;
1018 /* Functions returning multiple times are not handled by extra edges.
1019 Instead we simply allow negative counts on edges from exit to the
1020 block past call and corresponding probabilities. We can't go
1021 with the extra edges because that would result in flowgraph that
1022 needs to have fake edges outside the spanning tree. */
1024 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1026 gimple_stmt_iterator gsi
;
1027 gimple
*last
= NULL
;
1029 /* It may happen that there are compiler generated statements
1030 without a locus at all. Go through the basic block from the
1031 last to the first statement looking for a locus. */
1032 for (gsi
= gsi_last_nondebug_bb (bb
);
1034 gsi_prev_nondebug (&gsi
))
1036 last
= gsi_stmt (gsi
);
1037 if (!RESERVED_LOCATION_P (gimple_location (last
)))
1041 /* Edge with goto locus might get wrong coverage info unless
1042 it is the only edge out of BB.
1043 Don't do that when the locuses match, so
1044 if (blah) goto something;
1045 is not computed twice. */
1047 && gimple_has_location (last
)
1048 && !RESERVED_LOCATION_P (e
->goto_locus
)
1049 && !single_succ_p (bb
)
1050 && (LOCATION_FILE (e
->goto_locus
)
1051 != LOCATION_FILE (gimple_location (last
))
1052 || (LOCATION_LINE (e
->goto_locus
)
1053 != LOCATION_LINE (gimple_location (last
)))))
1055 basic_block new_bb
= split_edge (e
);
1056 edge ne
= single_succ_edge (new_bb
);
1057 ne
->goto_locus
= e
->goto_locus
;
1059 if ((e
->flags
& (EDGE_ABNORMAL
| EDGE_ABNORMAL_CALL
))
1060 && e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
1062 if (e
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
1065 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1067 if ((e
->flags
& (EDGE_ABNORMAL
| EDGE_ABNORMAL_CALL
))
1068 && e
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
))
1069 need_entry_edge
= 1;
1070 if (e
->src
== ENTRY_BLOCK_PTR_FOR_FN (cfun
))
1071 have_entry_edge
= 1;
1074 if (need_exit_edge
&& !have_exit_edge
)
1077 fprintf (dump_file
, "Adding fake exit edge to bb %i\n",
1079 make_edge (bb
, EXIT_BLOCK_PTR_FOR_FN (cfun
), EDGE_FAKE
);
1081 if (need_entry_edge
&& !have_entry_edge
)
1084 fprintf (dump_file
, "Adding fake entry edge to bb %i\n",
1086 make_edge (ENTRY_BLOCK_PTR_FOR_FN (cfun
), bb
, EDGE_FAKE
);
1087 /* Avoid bbs that have both fake entry edge and also some
1088 exit edge. One of those edges wouldn't be added to the
1089 spanning tree, but we can't instrument any of them. */
1090 if (have_exit_edge
|| need_exit_edge
)
1092 gimple_stmt_iterator gsi
;
1095 gsi
= gsi_start_nondebug_after_labels_bb (bb
);
1096 gcc_checking_assert (!gsi_end_p (gsi
));
1097 first
= gsi_stmt (gsi
);
1098 /* Don't split the bbs containing __builtin_setjmp_receiver
1099 or ABNORMAL_DISPATCHER calls. These are very
1100 special and don't expect anything to be inserted before
1102 if (is_gimple_call (first
)
1103 && (gimple_call_builtin_p (first
, BUILT_IN_SETJMP_RECEIVER
)
1104 || (gimple_call_flags (first
) & ECF_RETURNS_TWICE
)
1105 || (gimple_call_internal_p (first
)
1106 && (gimple_call_internal_fn (first
)
1107 == IFN_ABNORMAL_DISPATCHER
))))
1111 fprintf (dump_file
, "Splitting bb %i after labels\n",
1113 split_block_after_labels (bb
);
1118 el
= create_edge_list ();
1119 num_edges
= NUM_EDGES (el
);
1120 qsort (el
->index_to_edge
, num_edges
, sizeof (edge
), compare_freqs
);
1121 alloc_aux_for_edges (sizeof (struct edge_profile_info
));
1123 /* The basic blocks are expected to be numbered sequentially. */
1127 for (i
= 0 ; i
< num_edges
; i
++)
1129 edge e
= INDEX_EDGE (el
, i
);
1131 /* Mark edges we've replaced by fake edges above as ignored. */
1132 if ((e
->flags
& (EDGE_ABNORMAL
| EDGE_ABNORMAL_CALL
))
1133 && e
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
1134 && e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
1136 EDGE_INFO (e
)->ignore
= 1;
1141 /* Create spanning tree from basic block graph, mark each edge that is
1142 on the spanning tree. We insert as many abnormal and critical edges
1143 as possible to minimize number of edge splits necessary. */
1145 find_spanning_tree (el
);
1147 /* Fake edges that are not on the tree will not be instrumented, so
1148 mark them ignored. */
1149 for (num_instrumented
= i
= 0; i
< num_edges
; i
++)
1151 edge e
= INDEX_EDGE (el
, i
);
1152 struct edge_profile_info
*inf
= EDGE_INFO (e
);
1154 if (inf
->ignore
|| inf
->on_tree
)
1156 else if (e
->flags
& EDGE_FAKE
)
1165 total_num_blocks
+= n_basic_blocks_for_fn (cfun
);
1167 fprintf (dump_file
, "%d basic blocks\n", n_basic_blocks_for_fn (cfun
));
1169 total_num_edges
+= num_edges
;
1171 fprintf (dump_file
, "%d edges\n", num_edges
);
1173 total_num_edges_ignored
+= ignored_edges
;
1175 fprintf (dump_file
, "%d ignored edges\n", ignored_edges
);
1177 total_num_edges_instrumented
+= num_instrumented
;
1179 fprintf (dump_file
, "%d instrumentation edges\n", num_instrumented
);
1181 /* Compute two different checksums. Note that we want to compute
1182 the checksum in only once place, since it depends on the shape
1183 of the control flow which can change during
1184 various transformations. */
1185 cfg_checksum
= coverage_compute_cfg_checksum (cfun
);
1186 lineno_checksum
= coverage_compute_lineno_checksum ();
1188 /* Write the data from which gcov can reconstruct the basic block
1189 graph and function line numbers (the gcno file). */
1190 if (coverage_begin_function (lineno_checksum
, cfg_checksum
))
1192 gcov_position_t offset
;
1194 /* Basic block flags */
1195 offset
= gcov_write_tag (GCOV_TAG_BLOCKS
);
1196 gcov_write_unsigned (n_basic_blocks_for_fn (cfun
));
1197 gcov_write_length (offset
);
1200 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
),
1201 EXIT_BLOCK_PTR_FOR_FN (cfun
), next_bb
)
1206 offset
= gcov_write_tag (GCOV_TAG_ARCS
);
1207 gcov_write_unsigned (bb
->index
);
1209 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1211 struct edge_profile_info
*i
= EDGE_INFO (e
);
1214 unsigned flag_bits
= 0;
1217 flag_bits
|= GCOV_ARC_ON_TREE
;
1218 if (e
->flags
& EDGE_FAKE
)
1219 flag_bits
|= GCOV_ARC_FAKE
;
1220 if (e
->flags
& EDGE_FALLTHRU
)
1221 flag_bits
|= GCOV_ARC_FALLTHROUGH
;
1222 /* On trees we don't have fallthru flags, but we can
1223 recompute them from CFG shape. */
1224 if (e
->flags
& (EDGE_TRUE_VALUE
| EDGE_FALSE_VALUE
)
1225 && e
->src
->next_bb
== e
->dest
)
1226 flag_bits
|= GCOV_ARC_FALLTHROUGH
;
1228 gcov_write_unsigned (e
->dest
->index
);
1229 gcov_write_unsigned (flag_bits
);
1233 gcov_write_length (offset
);
1237 /* Initialize the output. */
1238 output_location (&streamed_locations
, NULL
, 0, NULL
, NULL
);
1240 hash_set
<int_hash
<location_t
, 0, 2> > seen_locations
;
1242 FOR_EACH_BB_FN (bb
, cfun
)
1244 gimple_stmt_iterator gsi
;
1245 gcov_position_t offset
= 0;
1247 if (bb
== ENTRY_BLOCK_PTR_FOR_FN (cfun
)->next_bb
)
1249 location_t loc
= DECL_SOURCE_LOCATION (current_function_decl
);
1250 seen_locations
.add (loc
);
1251 expanded_location curr_location
= expand_location (loc
);
1252 output_location (&streamed_locations
, curr_location
.file
,
1253 curr_location
.line
, &offset
, bb
);
1256 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1258 gimple
*stmt
= gsi_stmt (gsi
);
1259 location_t loc
= gimple_location (stmt
);
1260 if (!RESERVED_LOCATION_P (loc
))
1262 seen_locations
.add (loc
);
1263 output_location (&streamed_locations
, gimple_filename (stmt
),
1264 gimple_lineno (stmt
), &offset
, bb
);
1268 /* Notice GOTO expressions eliminated while constructing the CFG.
1269 It's hard to distinguish such expression, but goto_locus should
1270 not be any of already seen location. */
1272 if (single_succ_p (bb
)
1273 && (loc
= single_succ_edge (bb
)->goto_locus
)
1274 && !RESERVED_LOCATION_P (loc
)
1275 && !seen_locations
.contains (loc
))
1277 expanded_location curr_location
= expand_location (loc
);
1278 output_location (&streamed_locations
, curr_location
.file
,
1279 curr_location
.line
, &offset
, bb
);
1284 /* A file of NULL indicates the end of run. */
1285 gcov_write_unsigned (0);
1286 gcov_write_string (NULL
);
1287 gcov_write_length (offset
);
1292 if (flag_profile_values
)
1293 gimple_find_values_to_profile (&values
);
1295 if (flag_branch_probabilities
)
1297 compute_branch_probabilities (cfg_checksum
, lineno_checksum
);
1298 if (flag_profile_values
)
1299 compute_value_histograms (values
, cfg_checksum
, lineno_checksum
);
1302 remove_fake_edges ();
1304 /* For each edge not on the spanning tree, add counting code. */
1305 if (profile_arc_flag
1306 && coverage_counter_alloc (GCOV_COUNTER_ARCS
, num_instrumented
))
1308 unsigned n_instrumented
;
1310 gimple_init_gcov_profiler ();
1312 n_instrumented
= instrument_edges (el
);
1314 gcc_assert (n_instrumented
== num_instrumented
);
1316 if (flag_profile_values
)
1317 instrument_values (values
);
1319 /* Commit changes done by instrumentation. */
1320 gsi_commit_edge_inserts ();
1323 free_aux_for_edges ();
1326 free_edge_list (el
);
1327 coverage_end_function (lineno_checksum
, cfg_checksum
);
1328 if (flag_branch_probabilities
1329 && (profile_status_for_fn (cfun
) == PROFILE_READ
))
1332 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1333 report_predictor_hitrates ();
1335 /* At this moment we have precise loop iteration count estimates.
1336 Record them to loop structure before the profile gets out of date. */
1337 FOR_EACH_LOOP (loop
, 0)
1338 if (loop
->header
->count
> 0)
1340 gcov_type nit
= expected_loop_iterations_unbounded (loop
);
1341 widest_int bound
= gcov_type_to_wide_int (nit
);
1342 loop
->any_estimate
= false;
1343 record_niter_bound (loop
, bound
, true, false);
1345 compute_function_frequency ();
1349 /* Union find algorithm implementation for the basic blocks using
1353 find_group (basic_block bb
)
1355 basic_block group
= bb
, bb1
;
1357 while ((basic_block
) group
->aux
!= group
)
1358 group
= (basic_block
) group
->aux
;
1360 /* Compress path. */
1361 while ((basic_block
) bb
->aux
!= group
)
1363 bb1
= (basic_block
) bb
->aux
;
1364 bb
->aux
= (void *) group
;
1371 union_groups (basic_block bb1
, basic_block bb2
)
1373 basic_block bb1g
= find_group (bb1
);
1374 basic_block bb2g
= find_group (bb2
);
1376 /* ??? I don't have a place for the rank field. OK. Lets go w/o it,
1377 this code is unlikely going to be performance problem anyway. */
1378 gcc_assert (bb1g
!= bb2g
);
1383 /* This function searches all of the edges in the program flow graph, and puts
1384 as many bad edges as possible onto the spanning tree. Bad edges include
1385 abnormals edges, which can't be instrumented at the moment. Since it is
1386 possible for fake edges to form a cycle, we will have to develop some
1387 better way in the future. Also put critical edges to the tree, since they
1388 are more expensive to instrument. */
1391 find_spanning_tree (struct edge_list
*el
)
1394 int num_edges
= NUM_EDGES (el
);
1397 /* We use aux field for standard union-find algorithm. */
1398 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
), NULL
, next_bb
)
1401 /* Add fake edge exit to entry we can't instrument. */
1402 union_groups (EXIT_BLOCK_PTR_FOR_FN (cfun
), ENTRY_BLOCK_PTR_FOR_FN (cfun
));
1404 /* First add all abnormal edges to the tree unless they form a cycle. Also
1405 add all edges to the exit block to avoid inserting profiling code behind
1406 setting return value from function. */
1407 for (i
= 0; i
< num_edges
; i
++)
1409 edge e
= INDEX_EDGE (el
, i
);
1410 if (((e
->flags
& (EDGE_ABNORMAL
| EDGE_ABNORMAL_CALL
| EDGE_FAKE
))
1411 || e
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
1412 && !EDGE_INFO (e
)->ignore
1413 && (find_group (e
->src
) != find_group (e
->dest
)))
1416 fprintf (dump_file
, "Abnormal edge %d to %d put to tree\n",
1417 e
->src
->index
, e
->dest
->index
);
1418 EDGE_INFO (e
)->on_tree
= 1;
1419 union_groups (e
->src
, e
->dest
);
1423 /* And now the rest. Edge list is sorted according to frequencies and
1424 thus we will produce minimal spanning tree. */
1425 for (i
= 0; i
< num_edges
; i
++)
1427 edge e
= INDEX_EDGE (el
, i
);
1428 if (!EDGE_INFO (e
)->ignore
1429 && find_group (e
->src
) != find_group (e
->dest
))
1432 fprintf (dump_file
, "Normal edge %d to %d put to tree\n",
1433 e
->src
->index
, e
->dest
->index
);
1434 EDGE_INFO (e
)->on_tree
= 1;
1435 union_groups (e
->src
, e
->dest
);
1439 clear_aux_for_blocks ();
1442 /* Perform file-level initialization for branch-prob processing. */
1445 init_branch_prob (void)
1449 total_num_blocks
= 0;
1450 total_num_edges
= 0;
1451 total_num_edges_ignored
= 0;
1452 total_num_edges_instrumented
= 0;
1453 total_num_blocks_created
= 0;
1454 total_num_passes
= 0;
1455 total_num_times_called
= 0;
1456 total_num_branches
= 0;
1457 for (i
= 0; i
< 20; i
++)
1458 total_hist_br_prob
[i
] = 0;
1461 /* Performs file-level cleanup after branch-prob processing
1465 end_branch_prob (void)
1469 fprintf (dump_file
, "\n");
1470 fprintf (dump_file
, "Total number of blocks: %d\n",
1472 fprintf (dump_file
, "Total number of edges: %d\n", total_num_edges
);
1473 fprintf (dump_file
, "Total number of ignored edges: %d\n",
1474 total_num_edges_ignored
);
1475 fprintf (dump_file
, "Total number of instrumented edges: %d\n",
1476 total_num_edges_instrumented
);
1477 fprintf (dump_file
, "Total number of blocks created: %d\n",
1478 total_num_blocks_created
);
1479 fprintf (dump_file
, "Total number of graph solution passes: %d\n",
1481 if (total_num_times_called
!= 0)
1482 fprintf (dump_file
, "Average number of graph solution passes: %d\n",
1483 (total_num_passes
+ (total_num_times_called
>> 1))
1484 / total_num_times_called
);
1485 fprintf (dump_file
, "Total number of branches: %d\n",
1486 total_num_branches
);
1487 if (total_num_branches
)
1491 for (i
= 0; i
< 10; i
++)
1492 fprintf (dump_file
, "%d%% branches in range %d-%d%%\n",
1493 (total_hist_br_prob
[i
] + total_hist_br_prob
[19-i
]) * 100
1494 / total_num_branches
, 5*i
, 5*i
+5);