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
,
221 lineno_checksum
, num_edges
);
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 n_histogram_counters
[t
]);
785 if (histogram_counts
[t
])
787 act_count
[t
] = histogram_counts
[t
];
792 for (i
= 0; i
< values
.length (); i
++)
794 histogram_value hist
= values
[i
];
795 gimple
*stmt
= hist
->hvalue
.stmt
;
797 t
= (int) hist
->type
;
799 aact_count
= act_count
[t
];
802 act_count
[t
] += hist
->n_counters
;
804 gimple_add_histogram_value (cfun
, stmt
, hist
);
805 hist
->hvalue
.counters
= XNEWVEC (gcov_type
, hist
->n_counters
);
806 for (j
= 0; j
< hist
->n_counters
; j
++)
808 hist
->hvalue
.counters
[j
] = aact_count
[j
];
810 hist
->hvalue
.counters
[j
] = 0;
812 /* Time profiler counter is not related to any statement,
813 so that we have to read the counter and set the value to
814 the corresponding call graph node. */
815 if (hist
->type
== HIST_TYPE_TIME_PROFILE
)
817 node
= cgraph_node::get (hist
->fun
->decl
);
818 node
->tp_first_run
= hist
->hvalue
.counters
[0];
821 fprintf (dump_file
, "Read tp_first_run: %d\n", node
->tp_first_run
);
825 for (t
= 0; t
< GCOV_N_VALUE_COUNTERS
; t
++)
826 free (histogram_counts
[t
]);
829 /* Location triplet which records a location. */
830 struct location_triplet
832 const char *filename
;
837 /* Traits class for streamed_locations hash set below. */
839 struct location_triplet_hash
: typed_noop_remove
<location_triplet
>
841 typedef location_triplet value_type
;
842 typedef location_triplet compare_type
;
845 hash (const location_triplet
&ref
)
847 inchash::hash
hstate (0);
849 hstate
.add_int (strlen (ref
.filename
));
850 hstate
.add_int (ref
.lineno
);
851 hstate
.add_int (ref
.bb_index
);
852 return hstate
.end ();
856 equal (const location_triplet
&ref1
, const location_triplet
&ref2
)
858 return ref1
.lineno
== ref2
.lineno
859 && ref1
.bb_index
== ref2
.bb_index
860 && ref1
.filename
!= NULL
861 && ref2
.filename
!= NULL
862 && strcmp (ref1
.filename
, ref2
.filename
) == 0;
866 mark_deleted (location_triplet
&ref
)
872 mark_empty (location_triplet
&ref
)
878 is_deleted (const location_triplet
&ref
)
880 return ref
.lineno
== -1;
884 is_empty (const location_triplet
&ref
)
886 return ref
.lineno
== -2;
893 /* When passed NULL as file_name, initialize.
894 When passed something else, output the necessary commands to change
895 line to LINE and offset to FILE_NAME. */
897 output_location (hash_set
<location_triplet_hash
> *streamed_locations
,
898 char const *file_name
, int line
,
899 gcov_position_t
*offset
, basic_block bb
)
901 static char const *prev_file_name
;
902 static int prev_line
;
903 bool name_differs
, line_differs
;
905 location_triplet triplet
;
906 triplet
.filename
= file_name
;
907 triplet
.lineno
= line
;
908 triplet
.bb_index
= bb
? bb
->index
: 0;
910 if (streamed_locations
->add (triplet
))
915 prev_file_name
= NULL
;
920 name_differs
= !prev_file_name
|| filename_cmp (file_name
, prev_file_name
);
921 line_differs
= prev_line
!= line
;
925 *offset
= gcov_write_tag (GCOV_TAG_LINES
);
926 gcov_write_unsigned (bb
->index
);
927 name_differs
= line_differs
= true;
930 /* If this is a new source file, then output the
931 file's name to the .bb file. */
934 prev_file_name
= file_name
;
935 gcov_write_unsigned (0);
936 gcov_write_filename (prev_file_name
);
940 gcov_write_unsigned (line
);
945 /* Helper for qsort so edges get sorted from highest frequency to smallest.
946 This controls the weight for minimal spanning tree algorithm */
948 compare_freqs (const void *p1
, const void *p2
)
950 const_edge e1
= *(const const_edge
*)p1
;
951 const_edge e2
= *(const const_edge
*)p2
;
953 /* Critical edges needs to be split which introduce extra control flow.
954 Make them more heavy. */
955 int m1
= EDGE_CRITICAL_P (e1
) ? 2 : 1;
956 int m2
= EDGE_CRITICAL_P (e2
) ? 2 : 1;
958 if (EDGE_FREQUENCY (e1
) * m1
+ m1
!= EDGE_FREQUENCY (e2
) * m2
+ m2
)
959 return EDGE_FREQUENCY (e2
) * m2
+ m2
- EDGE_FREQUENCY (e1
) * m1
- m1
;
960 /* Stabilize sort. */
961 if (e1
->src
->index
!= e2
->src
->index
)
962 return e2
->src
->index
- e1
->src
->index
;
963 return e2
->dest
->index
- e1
->dest
->index
;
966 /* Instrument and/or analyze program behavior based on program the CFG.
968 This function creates a representation of the control flow graph (of
969 the function being compiled) that is suitable for the instrumentation
970 of edges and/or converting measured edge counts to counts on the
973 When FLAG_PROFILE_ARCS is nonzero, this function instruments the edges in
974 the flow graph that are needed to reconstruct the dynamic behavior of the
975 flow graph. This data is written to the gcno file for gcov.
977 When FLAG_BRANCH_PROBABILITIES is nonzero, this function reads auxiliary
978 information from the gcda file containing edge count information from
979 previous executions of the function being compiled. In this case, the
980 control flow graph is annotated with actual execution counts by
981 compute_branch_probabilities().
983 Main entry point of this file. */
990 unsigned num_edges
, ignored_edges
;
991 unsigned num_instrumented
;
992 struct edge_list
*el
;
993 histogram_values values
= histogram_values ();
994 unsigned cfg_checksum
, lineno_checksum
;
996 total_num_times_called
++;
998 flow_call_edges_add (NULL
);
999 add_noreturn_fake_exit_edges ();
1001 hash_set
<location_triplet_hash
> streamed_locations
;
1003 /* We can't handle cyclic regions constructed using abnormal edges.
1004 To avoid these we replace every source of abnormal edge by a fake
1005 edge from entry node and every destination by fake edge to exit.
1006 This keeps graph acyclic and our calculation exact for all normal
1007 edges except for exit and entrance ones.
1009 We also add fake exit edges for each call and asm statement in the
1010 basic, since it may not return. */
1012 FOR_EACH_BB_FN (bb
, cfun
)
1014 int need_exit_edge
= 0, need_entry_edge
= 0;
1015 int have_exit_edge
= 0, have_entry_edge
= 0;
1019 /* Functions returning multiple times are not handled by extra edges.
1020 Instead we simply allow negative counts on edges from exit to the
1021 block past call and corresponding probabilities. We can't go
1022 with the extra edges because that would result in flowgraph that
1023 needs to have fake edges outside the spanning tree. */
1025 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1027 gimple_stmt_iterator gsi
;
1028 gimple
*last
= NULL
;
1030 /* It may happen that there are compiler generated statements
1031 without a locus at all. Go through the basic block from the
1032 last to the first statement looking for a locus. */
1033 for (gsi
= gsi_last_nondebug_bb (bb
);
1035 gsi_prev_nondebug (&gsi
))
1037 last
= gsi_stmt (gsi
);
1038 if (!RESERVED_LOCATION_P (gimple_location (last
)))
1042 /* Edge with goto locus might get wrong coverage info unless
1043 it is the only edge out of BB.
1044 Don't do that when the locuses match, so
1045 if (blah) goto something;
1046 is not computed twice. */
1048 && gimple_has_location (last
)
1049 && !RESERVED_LOCATION_P (e
->goto_locus
)
1050 && !single_succ_p (bb
)
1051 && (LOCATION_FILE (e
->goto_locus
)
1052 != LOCATION_FILE (gimple_location (last
))
1053 || (LOCATION_LINE (e
->goto_locus
)
1054 != LOCATION_LINE (gimple_location (last
)))))
1056 basic_block new_bb
= split_edge (e
);
1057 edge ne
= single_succ_edge (new_bb
);
1058 ne
->goto_locus
= e
->goto_locus
;
1060 if ((e
->flags
& (EDGE_ABNORMAL
| EDGE_ABNORMAL_CALL
))
1061 && e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
1063 if (e
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
1066 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1068 if ((e
->flags
& (EDGE_ABNORMAL
| EDGE_ABNORMAL_CALL
))
1069 && e
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
))
1070 need_entry_edge
= 1;
1071 if (e
->src
== ENTRY_BLOCK_PTR_FOR_FN (cfun
))
1072 have_entry_edge
= 1;
1075 if (need_exit_edge
&& !have_exit_edge
)
1078 fprintf (dump_file
, "Adding fake exit edge to bb %i\n",
1080 make_edge (bb
, EXIT_BLOCK_PTR_FOR_FN (cfun
), EDGE_FAKE
);
1082 if (need_entry_edge
&& !have_entry_edge
)
1085 fprintf (dump_file
, "Adding fake entry edge to bb %i\n",
1087 make_edge (ENTRY_BLOCK_PTR_FOR_FN (cfun
), bb
, EDGE_FAKE
);
1088 /* Avoid bbs that have both fake entry edge and also some
1089 exit edge. One of those edges wouldn't be added to the
1090 spanning tree, but we can't instrument any of them. */
1091 if (have_exit_edge
|| need_exit_edge
)
1093 gimple_stmt_iterator gsi
;
1096 gsi
= gsi_start_nondebug_after_labels_bb (bb
);
1097 gcc_checking_assert (!gsi_end_p (gsi
));
1098 first
= gsi_stmt (gsi
);
1099 /* Don't split the bbs containing __builtin_setjmp_receiver
1100 or ABNORMAL_DISPATCHER calls. These are very
1101 special and don't expect anything to be inserted before
1103 if (is_gimple_call (first
)
1104 && (gimple_call_builtin_p (first
, BUILT_IN_SETJMP_RECEIVER
)
1105 || (gimple_call_flags (first
) & ECF_RETURNS_TWICE
)
1106 || (gimple_call_internal_p (first
)
1107 && (gimple_call_internal_fn (first
)
1108 == IFN_ABNORMAL_DISPATCHER
))))
1112 fprintf (dump_file
, "Splitting bb %i after labels\n",
1114 split_block_after_labels (bb
);
1119 el
= create_edge_list ();
1120 num_edges
= NUM_EDGES (el
);
1121 qsort (el
->index_to_edge
, num_edges
, sizeof (edge
), compare_freqs
);
1122 alloc_aux_for_edges (sizeof (struct edge_profile_info
));
1124 /* The basic blocks are expected to be numbered sequentially. */
1128 for (i
= 0 ; i
< num_edges
; i
++)
1130 edge e
= INDEX_EDGE (el
, i
);
1132 /* Mark edges we've replaced by fake edges above as ignored. */
1133 if ((e
->flags
& (EDGE_ABNORMAL
| EDGE_ABNORMAL_CALL
))
1134 && e
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
1135 && e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
1137 EDGE_INFO (e
)->ignore
= 1;
1142 /* Create spanning tree from basic block graph, mark each edge that is
1143 on the spanning tree. We insert as many abnormal and critical edges
1144 as possible to minimize number of edge splits necessary. */
1146 find_spanning_tree (el
);
1148 /* Fake edges that are not on the tree will not be instrumented, so
1149 mark them ignored. */
1150 for (num_instrumented
= i
= 0; i
< num_edges
; i
++)
1152 edge e
= INDEX_EDGE (el
, i
);
1153 struct edge_profile_info
*inf
= EDGE_INFO (e
);
1155 if (inf
->ignore
|| inf
->on_tree
)
1157 else if (e
->flags
& EDGE_FAKE
)
1166 total_num_blocks
+= n_basic_blocks_for_fn (cfun
);
1168 fprintf (dump_file
, "%d basic blocks\n", n_basic_blocks_for_fn (cfun
));
1170 total_num_edges
+= num_edges
;
1172 fprintf (dump_file
, "%d edges\n", num_edges
);
1174 total_num_edges_ignored
+= ignored_edges
;
1176 fprintf (dump_file
, "%d ignored edges\n", ignored_edges
);
1178 total_num_edges_instrumented
+= num_instrumented
;
1180 fprintf (dump_file
, "%d instrumentation edges\n", num_instrumented
);
1182 /* Compute two different checksums. Note that we want to compute
1183 the checksum in only once place, since it depends on the shape
1184 of the control flow which can change during
1185 various transformations. */
1186 cfg_checksum
= coverage_compute_cfg_checksum (cfun
);
1187 lineno_checksum
= coverage_compute_lineno_checksum ();
1189 /* Write the data from which gcov can reconstruct the basic block
1190 graph and function line numbers (the gcno file). */
1191 if (coverage_begin_function (lineno_checksum
, cfg_checksum
))
1193 gcov_position_t offset
;
1195 /* Basic block flags */
1196 offset
= gcov_write_tag (GCOV_TAG_BLOCKS
);
1197 gcov_write_unsigned (n_basic_blocks_for_fn (cfun
));
1198 gcov_write_length (offset
);
1201 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
),
1202 EXIT_BLOCK_PTR_FOR_FN (cfun
), next_bb
)
1207 offset
= gcov_write_tag (GCOV_TAG_ARCS
);
1208 gcov_write_unsigned (bb
->index
);
1210 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1212 struct edge_profile_info
*i
= EDGE_INFO (e
);
1215 unsigned flag_bits
= 0;
1218 flag_bits
|= GCOV_ARC_ON_TREE
;
1219 if (e
->flags
& EDGE_FAKE
)
1220 flag_bits
|= GCOV_ARC_FAKE
;
1221 if (e
->flags
& EDGE_FALLTHRU
)
1222 flag_bits
|= GCOV_ARC_FALLTHROUGH
;
1223 /* On trees we don't have fallthru flags, but we can
1224 recompute them from CFG shape. */
1225 if (e
->flags
& (EDGE_TRUE_VALUE
| EDGE_FALSE_VALUE
)
1226 && e
->src
->next_bb
== e
->dest
)
1227 flag_bits
|= GCOV_ARC_FALLTHROUGH
;
1229 gcov_write_unsigned (e
->dest
->index
);
1230 gcov_write_unsigned (flag_bits
);
1234 gcov_write_length (offset
);
1238 /* Initialize the output. */
1239 output_location (&streamed_locations
, NULL
, 0, NULL
, NULL
);
1241 hash_set
<int_hash
<location_t
, 0, 2> > seen_locations
;
1243 FOR_EACH_BB_FN (bb
, cfun
)
1245 gimple_stmt_iterator gsi
;
1246 gcov_position_t offset
= 0;
1248 if (bb
== ENTRY_BLOCK_PTR_FOR_FN (cfun
)->next_bb
)
1250 location_t loc
= DECL_SOURCE_LOCATION (current_function_decl
);
1251 seen_locations
.add (loc
);
1252 expanded_location curr_location
= expand_location (loc
);
1253 output_location (&streamed_locations
, curr_location
.file
,
1254 curr_location
.line
, &offset
, bb
);
1257 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1259 gimple
*stmt
= gsi_stmt (gsi
);
1260 location_t loc
= gimple_location (stmt
);
1261 if (!RESERVED_LOCATION_P (loc
))
1263 seen_locations
.add (loc
);
1264 output_location (&streamed_locations
, gimple_filename (stmt
),
1265 gimple_lineno (stmt
), &offset
, bb
);
1269 /* Notice GOTO expressions eliminated while constructing the CFG.
1270 It's hard to distinguish such expression, but goto_locus should
1271 not be any of already seen location. */
1273 if (single_succ_p (bb
)
1274 && (loc
= single_succ_edge (bb
)->goto_locus
)
1275 && !RESERVED_LOCATION_P (loc
)
1276 && !seen_locations
.contains (loc
))
1278 expanded_location curr_location
= expand_location (loc
);
1279 output_location (&streamed_locations
, curr_location
.file
,
1280 curr_location
.line
, &offset
, bb
);
1285 /* A file of NULL indicates the end of run. */
1286 gcov_write_unsigned (0);
1287 gcov_write_string (NULL
);
1288 gcov_write_length (offset
);
1293 if (flag_profile_values
)
1294 gimple_find_values_to_profile (&values
);
1296 if (flag_branch_probabilities
)
1298 compute_branch_probabilities (cfg_checksum
, lineno_checksum
);
1299 if (flag_profile_values
)
1300 compute_value_histograms (values
, cfg_checksum
, lineno_checksum
);
1303 remove_fake_edges ();
1305 /* For each edge not on the spanning tree, add counting code. */
1306 if (profile_arc_flag
1307 && coverage_counter_alloc (GCOV_COUNTER_ARCS
, num_instrumented
))
1309 unsigned n_instrumented
;
1311 gimple_init_gcov_profiler ();
1313 n_instrumented
= instrument_edges (el
);
1315 gcc_assert (n_instrumented
== num_instrumented
);
1317 if (flag_profile_values
)
1318 instrument_values (values
);
1320 /* Commit changes done by instrumentation. */
1321 gsi_commit_edge_inserts ();
1324 free_aux_for_edges ();
1327 free_edge_list (el
);
1328 coverage_end_function (lineno_checksum
, cfg_checksum
);
1329 if (flag_branch_probabilities
1330 && (profile_status_for_fn (cfun
) == PROFILE_READ
))
1333 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1334 report_predictor_hitrates ();
1336 /* At this moment we have precise loop iteration count estimates.
1337 Record them to loop structure before the profile gets out of date. */
1338 FOR_EACH_LOOP (loop
, 0)
1339 if (loop
->header
->count
> 0)
1341 gcov_type nit
= expected_loop_iterations_unbounded (loop
);
1342 widest_int bound
= gcov_type_to_wide_int (nit
);
1343 loop
->any_estimate
= false;
1344 record_niter_bound (loop
, bound
, true, false);
1346 compute_function_frequency ();
1350 /* Union find algorithm implementation for the basic blocks using
1354 find_group (basic_block bb
)
1356 basic_block group
= bb
, bb1
;
1358 while ((basic_block
) group
->aux
!= group
)
1359 group
= (basic_block
) group
->aux
;
1361 /* Compress path. */
1362 while ((basic_block
) bb
->aux
!= group
)
1364 bb1
= (basic_block
) bb
->aux
;
1365 bb
->aux
= (void *) group
;
1372 union_groups (basic_block bb1
, basic_block bb2
)
1374 basic_block bb1g
= find_group (bb1
);
1375 basic_block bb2g
= find_group (bb2
);
1377 /* ??? I don't have a place for the rank field. OK. Lets go w/o it,
1378 this code is unlikely going to be performance problem anyway. */
1379 gcc_assert (bb1g
!= bb2g
);
1384 /* This function searches all of the edges in the program flow graph, and puts
1385 as many bad edges as possible onto the spanning tree. Bad edges include
1386 abnormals edges, which can't be instrumented at the moment. Since it is
1387 possible for fake edges to form a cycle, we will have to develop some
1388 better way in the future. Also put critical edges to the tree, since they
1389 are more expensive to instrument. */
1392 find_spanning_tree (struct edge_list
*el
)
1395 int num_edges
= NUM_EDGES (el
);
1398 /* We use aux field for standard union-find algorithm. */
1399 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
), NULL
, next_bb
)
1402 /* Add fake edge exit to entry we can't instrument. */
1403 union_groups (EXIT_BLOCK_PTR_FOR_FN (cfun
), ENTRY_BLOCK_PTR_FOR_FN (cfun
));
1405 /* First add all abnormal edges to the tree unless they form a cycle. Also
1406 add all edges to the exit block to avoid inserting profiling code behind
1407 setting return value from function. */
1408 for (i
= 0; i
< num_edges
; i
++)
1410 edge e
= INDEX_EDGE (el
, i
);
1411 if (((e
->flags
& (EDGE_ABNORMAL
| EDGE_ABNORMAL_CALL
| EDGE_FAKE
))
1412 || e
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
1413 && !EDGE_INFO (e
)->ignore
1414 && (find_group (e
->src
) != find_group (e
->dest
)))
1417 fprintf (dump_file
, "Abnormal edge %d to %d put to tree\n",
1418 e
->src
->index
, e
->dest
->index
);
1419 EDGE_INFO (e
)->on_tree
= 1;
1420 union_groups (e
->src
, e
->dest
);
1424 /* And now the rest. Edge list is sorted according to frequencies and
1425 thus we will produce minimal spanning tree. */
1426 for (i
= 0; i
< num_edges
; i
++)
1428 edge e
= INDEX_EDGE (el
, i
);
1429 if (!EDGE_INFO (e
)->ignore
1430 && find_group (e
->src
) != find_group (e
->dest
))
1433 fprintf (dump_file
, "Normal edge %d to %d put to tree\n",
1434 e
->src
->index
, e
->dest
->index
);
1435 EDGE_INFO (e
)->on_tree
= 1;
1436 union_groups (e
->src
, e
->dest
);
1440 clear_aux_for_blocks ();
1443 /* Perform file-level initialization for branch-prob processing. */
1446 init_branch_prob (void)
1450 total_num_blocks
= 0;
1451 total_num_edges
= 0;
1452 total_num_edges_ignored
= 0;
1453 total_num_edges_instrumented
= 0;
1454 total_num_blocks_created
= 0;
1455 total_num_passes
= 0;
1456 total_num_times_called
= 0;
1457 total_num_branches
= 0;
1458 for (i
= 0; i
< 20; i
++)
1459 total_hist_br_prob
[i
] = 0;
1462 /* Performs file-level cleanup after branch-prob processing
1466 end_branch_prob (void)
1470 fprintf (dump_file
, "\n");
1471 fprintf (dump_file
, "Total number of blocks: %d\n",
1473 fprintf (dump_file
, "Total number of edges: %d\n", total_num_edges
);
1474 fprintf (dump_file
, "Total number of ignored edges: %d\n",
1475 total_num_edges_ignored
);
1476 fprintf (dump_file
, "Total number of instrumented edges: %d\n",
1477 total_num_edges_instrumented
);
1478 fprintf (dump_file
, "Total number of blocks created: %d\n",
1479 total_num_blocks_created
);
1480 fprintf (dump_file
, "Total number of graph solution passes: %d\n",
1482 if (total_num_times_called
!= 0)
1483 fprintf (dump_file
, "Average number of graph solution passes: %d\n",
1484 (total_num_passes
+ (total_num_times_called
>> 1))
1485 / total_num_times_called
);
1486 fprintf (dump_file
, "Total number of branches: %d\n",
1487 total_num_branches
);
1488 if (total_num_branches
)
1492 for (i
= 0; i
< 10; i
++)
1493 fprintf (dump_file
, "%d%% branches in range %d-%d%%\n",
1494 (total_hist_br_prob
[i
] + total_hist_br_prob
[19-i
]) * 100
1495 / total_num_branches
, 5*i
, 5*i
+5);