gcc/
[official-gcc.git] / gcc / profile.c
blob75b418d1657311db8683f1dfb651b182ae49e6d5
1 /* Calculate branch probabilities, and basic block execution counts.
2 Copyright (C) 1990-2015 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
12 version.
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
17 for more details.
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. */
50 #include "config.h"
51 #include "system.h"
52 #include "coretypes.h"
53 #include "tm.h"
54 #include "rtl.h"
55 #include "flags.h"
56 #include "regs.h"
57 #include "symtab.h"
58 #include "hard-reg-set.h"
59 #include "function.h"
60 #include "alias.h"
61 #include "tree.h"
62 #include "insn-config.h"
63 #include "expmed.h"
64 #include "dojump.h"
65 #include "explow.h"
66 #include "calls.h"
67 #include "emit-rtl.h"
68 #include "varasm.h"
69 #include "stmt.h"
70 #include "expr.h"
71 #include "predict.h"
72 #include "dominance.h"
73 #include "cfg.h"
74 #include "cfganal.h"
75 #include "basic-block.h"
76 #include "diagnostic-core.h"
77 #include "coverage.h"
78 #include "value-prof.h"
79 #include "fold-const.h"
80 #include "tree-ssa-alias.h"
81 #include "internal-fn.h"
82 #include "gimple-expr.h"
83 #include "gimple.h"
84 #include "gimple-iterator.h"
85 #include "tree-cfg.h"
86 #include "cfgloop.h"
87 #include "dumpfile.h"
88 #include "plugin-api.h"
89 #include "ipa-ref.h"
90 #include "cgraph.h"
92 #include "profile.h"
94 struct bb_profile_info {
95 unsigned int count_valid : 1;
97 /* Number of successor and predecessor edges. */
98 gcov_type succ_count;
99 gcov_type pred_count;
102 #define BB_INFO(b) ((struct bb_profile_info *) (b)->aux)
105 /* Counter summary from the last set of coverage counts read. */
107 const struct gcov_ctr_summary *profile_info;
109 /* Counter working set information computed from the current counter
110 summary. Not initialized unless profile_info summary is non-NULL. */
111 static gcov_working_set_t gcov_working_sets[NUM_GCOV_WORKING_SETS];
113 /* Collect statistics on the performance of this pass for the entire source
114 file. */
116 static int total_num_blocks;
117 static int total_num_edges;
118 static int total_num_edges_ignored;
119 static int total_num_edges_instrumented;
120 static int total_num_blocks_created;
121 static int total_num_passes;
122 static int total_num_times_called;
123 static int total_hist_br_prob[20];
124 static int total_num_branches;
126 /* Helper function to update gcov_working_sets. */
128 void add_working_set (gcov_working_set_t *set) {
129 int i = 0;
130 for (; i < NUM_GCOV_WORKING_SETS; i++)
131 gcov_working_sets[i] = set[i];
134 /* Forward declarations. */
135 static void find_spanning_tree (struct edge_list *);
137 /* Add edge instrumentation code to the entire insn chain.
139 F is the first insn of the chain.
140 NUM_BLOCKS is the number of basic blocks found in F. */
142 static unsigned
143 instrument_edges (struct edge_list *el)
145 unsigned num_instr_edges = 0;
146 int num_edges = NUM_EDGES (el);
147 basic_block bb;
149 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun), NULL, next_bb)
151 edge e;
152 edge_iterator ei;
154 FOR_EACH_EDGE (e, ei, bb->succs)
156 struct edge_profile_info *inf = EDGE_INFO (e);
158 if (!inf->ignore && !inf->on_tree)
160 gcc_assert (!(e->flags & EDGE_ABNORMAL));
161 if (dump_file)
162 fprintf (dump_file, "Edge %d to %d instrumented%s\n",
163 e->src->index, e->dest->index,
164 EDGE_CRITICAL_P (e) ? " (and split)" : "");
165 gimple_gen_edge_profiler (num_instr_edges++, e);
170 total_num_blocks_created += num_edges;
171 if (dump_file)
172 fprintf (dump_file, "%d edges instrumented\n", num_instr_edges);
173 return num_instr_edges;
176 /* Add code to measure histograms for values in list VALUES. */
177 static void
178 instrument_values (histogram_values values)
180 unsigned i;
182 /* Emit code to generate the histograms before the insns. */
184 for (i = 0; i < values.length (); i++)
186 histogram_value hist = values[i];
187 unsigned t = COUNTER_FOR_HIST_TYPE (hist->type);
189 if (!coverage_counter_alloc (t, hist->n_counters))
190 continue;
192 switch (hist->type)
194 case HIST_TYPE_INTERVAL:
195 gimple_gen_interval_profiler (hist, t, 0);
196 break;
198 case HIST_TYPE_POW2:
199 gimple_gen_pow2_profiler (hist, t, 0);
200 break;
202 case HIST_TYPE_SINGLE_VALUE:
203 gimple_gen_one_value_profiler (hist, t, 0);
204 break;
206 case HIST_TYPE_CONST_DELTA:
207 gimple_gen_const_delta_profiler (hist, t, 0);
208 break;
210 case HIST_TYPE_INDIR_CALL:
211 case HIST_TYPE_INDIR_CALL_TOPN:
212 gimple_gen_ic_profiler (hist, t, 0);
213 break;
215 case HIST_TYPE_AVERAGE:
216 gimple_gen_average_profiler (hist, t, 0);
217 break;
219 case HIST_TYPE_IOR:
220 gimple_gen_ior_profiler (hist, t, 0);
221 break;
223 case HIST_TYPE_TIME_PROFILE:
225 basic_block bb =
226 split_edge (single_succ_edge (ENTRY_BLOCK_PTR_FOR_FN (cfun)));
227 gimple_stmt_iterator gsi = gsi_start_bb (bb);
229 gimple_gen_time_profiler (t, 0, gsi);
230 break;
233 default:
234 gcc_unreachable ();
240 /* Fill the working set information into the profile_info structure. */
242 void
243 get_working_sets (void)
245 unsigned ws_ix, pctinc, pct;
246 gcov_working_set_t *ws_info;
248 if (!profile_info)
249 return;
251 compute_working_sets (profile_info, gcov_working_sets);
253 if (dump_file)
255 fprintf (dump_file, "Counter working sets:\n");
256 /* Multiply the percentage by 100 to avoid float. */
257 pctinc = 100 * 100 / NUM_GCOV_WORKING_SETS;
258 for (ws_ix = 0, pct = pctinc; ws_ix < NUM_GCOV_WORKING_SETS;
259 ws_ix++, pct += pctinc)
261 if (ws_ix == NUM_GCOV_WORKING_SETS - 1)
262 pct = 9990;
263 ws_info = &gcov_working_sets[ws_ix];
264 /* Print out the percentage using int arithmatic to avoid float. */
265 fprintf (dump_file, "\t\t%u.%02u%%: num counts=%u, min counter="
266 "%" PRId64 "\n",
267 pct / 100, pct - (pct / 100 * 100),
268 ws_info->num_counters,
269 (int64_t)ws_info->min_counter);
274 /* Given a the desired percentage of the full profile (sum_all from the
275 summary), multiplied by 10 to avoid float in PCT_TIMES_10, returns
276 the corresponding working set information. If an exact match for
277 the percentage isn't found, the closest value is used. */
279 gcov_working_set_t *
280 find_working_set (unsigned pct_times_10)
282 unsigned i;
283 if (!profile_info)
284 return NULL;
285 gcc_assert (pct_times_10 <= 1000);
286 if (pct_times_10 >= 999)
287 return &gcov_working_sets[NUM_GCOV_WORKING_SETS - 1];
288 i = pct_times_10 * NUM_GCOV_WORKING_SETS / 1000;
289 if (!i)
290 return &gcov_working_sets[0];
291 return &gcov_working_sets[i - 1];
294 /* Computes hybrid profile for all matching entries in da_file.
296 CFG_CHECKSUM is the precomputed checksum for the CFG. */
298 static gcov_type *
299 get_exec_counts (unsigned cfg_checksum, unsigned lineno_checksum)
301 unsigned num_edges = 0;
302 basic_block bb;
303 gcov_type *counts;
305 /* Count the edges to be (possibly) instrumented. */
306 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun), NULL, next_bb)
308 edge e;
309 edge_iterator ei;
311 FOR_EACH_EDGE (e, ei, bb->succs)
312 if (!EDGE_INFO (e)->ignore && !EDGE_INFO (e)->on_tree)
313 num_edges++;
316 counts = get_coverage_counts (GCOV_COUNTER_ARCS, num_edges, cfg_checksum,
317 lineno_checksum, &profile_info);
318 if (!counts)
319 return NULL;
321 get_working_sets ();
323 if (dump_file && profile_info)
324 fprintf (dump_file, "Merged %u profiles with maximal count %u.\n",
325 profile_info->runs, (unsigned) profile_info->sum_max);
327 return counts;
331 static bool
332 is_edge_inconsistent (vec<edge, va_gc> *edges)
334 edge e;
335 edge_iterator ei;
336 FOR_EACH_EDGE (e, ei, edges)
338 if (!EDGE_INFO (e)->ignore)
340 if (e->count < 0
341 && (!(e->flags & EDGE_FAKE)
342 || !block_ends_with_call_p (e->src)))
344 if (dump_file)
346 fprintf (dump_file,
347 "Edge %i->%i is inconsistent, count%" PRId64,
348 e->src->index, e->dest->index, e->count);
349 dump_bb (dump_file, e->src, 0, TDF_DETAILS);
350 dump_bb (dump_file, e->dest, 0, TDF_DETAILS);
352 return true;
356 return false;
359 static void
360 correct_negative_edge_counts (void)
362 basic_block bb;
363 edge e;
364 edge_iterator ei;
366 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun), NULL, next_bb)
368 FOR_EACH_EDGE (e, ei, bb->succs)
370 if (e->count < 0)
371 e->count = 0;
376 /* Check consistency.
377 Return true if inconsistency is found. */
378 static bool
379 is_inconsistent (void)
381 basic_block bb;
382 bool inconsistent = false;
383 FOR_EACH_BB_FN (bb, cfun)
385 inconsistent |= is_edge_inconsistent (bb->preds);
386 if (!dump_file && inconsistent)
387 return true;
388 inconsistent |= is_edge_inconsistent (bb->succs);
389 if (!dump_file && inconsistent)
390 return true;
391 if (bb->count < 0)
393 if (dump_file)
395 fprintf (dump_file, "BB %i count is negative "
396 "%" PRId64,
397 bb->index,
398 bb->count);
399 dump_bb (dump_file, bb, 0, TDF_DETAILS);
401 inconsistent = true;
403 if (bb->count != sum_edge_counts (bb->preds))
405 if (dump_file)
407 fprintf (dump_file, "BB %i count does not match sum of incoming edges "
408 "%" PRId64" should be %" PRId64,
409 bb->index,
410 bb->count,
411 sum_edge_counts (bb->preds));
412 dump_bb (dump_file, bb, 0, TDF_DETAILS);
414 inconsistent = true;
416 if (bb->count != sum_edge_counts (bb->succs) &&
417 ! (find_edge (bb, EXIT_BLOCK_PTR_FOR_FN (cfun)) != NULL
418 && block_ends_with_call_p (bb)))
420 if (dump_file)
422 fprintf (dump_file, "BB %i count does not match sum of outgoing edges "
423 "%" PRId64" should be %" PRId64,
424 bb->index,
425 bb->count,
426 sum_edge_counts (bb->succs));
427 dump_bb (dump_file, bb, 0, TDF_DETAILS);
429 inconsistent = true;
431 if (!dump_file && inconsistent)
432 return true;
435 return inconsistent;
438 /* Set each basic block count to the sum of its outgoing edge counts */
439 static void
440 set_bb_counts (void)
442 basic_block bb;
443 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun), NULL, next_bb)
445 bb->count = sum_edge_counts (bb->succs);
446 gcc_assert (bb->count >= 0);
450 /* Reads profile data and returns total number of edge counts read */
451 static int
452 read_profile_edge_counts (gcov_type *exec_counts)
454 basic_block bb;
455 int num_edges = 0;
456 int exec_counts_pos = 0;
457 /* For each edge not on the spanning tree, set its execution count from
458 the .da file. */
459 /* The first count in the .da file is the number of times that the function
460 was entered. This is the exec_count for block zero. */
462 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun), NULL, next_bb)
464 edge e;
465 edge_iterator ei;
467 FOR_EACH_EDGE (e, ei, bb->succs)
468 if (!EDGE_INFO (e)->ignore && !EDGE_INFO (e)->on_tree)
470 num_edges++;
471 if (exec_counts)
473 e->count = exec_counts[exec_counts_pos++];
474 if (e->count > profile_info->sum_max)
476 if (flag_profile_correction)
478 static bool informed = 0;
479 if (dump_enabled_p () && !informed)
480 dump_printf_loc (MSG_NOTE, input_location,
481 "corrupted profile info: edge count"
482 " exceeds maximal count\n");
483 informed = 1;
485 else
486 error ("corrupted profile info: edge from %i to %i exceeds maximal count",
487 bb->index, e->dest->index);
490 else
491 e->count = 0;
493 EDGE_INFO (e)->count_valid = 1;
494 BB_INFO (bb)->succ_count--;
495 BB_INFO (e->dest)->pred_count--;
496 if (dump_file)
498 fprintf (dump_file, "\nRead edge from %i to %i, count:",
499 bb->index, e->dest->index);
500 fprintf (dump_file, "%" PRId64,
501 (int64_t) e->count);
506 return num_edges;
509 #define OVERLAP_BASE 10000
511 /* Compare the static estimated profile to the actual profile, and
512 return the "degree of overlap" measure between them.
514 Degree of overlap is a number between 0 and OVERLAP_BASE. It is
515 the sum of each basic block's minimum relative weights between
516 two profiles. And overlap of OVERLAP_BASE means two profiles are
517 identical. */
519 static int
520 compute_frequency_overlap (void)
522 gcov_type count_total = 0, freq_total = 0;
523 int overlap = 0;
524 basic_block bb;
526 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun), NULL, next_bb)
528 count_total += bb->count;
529 freq_total += bb->frequency;
532 if (count_total == 0 || freq_total == 0)
533 return 0;
535 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun), NULL, next_bb)
536 overlap += MIN (bb->count * OVERLAP_BASE / count_total,
537 bb->frequency * OVERLAP_BASE / freq_total);
539 return overlap;
542 /* Compute the branch probabilities for the various branches.
543 Annotate them accordingly.
545 CFG_CHECKSUM is the precomputed checksum for the CFG. */
547 static void
548 compute_branch_probabilities (unsigned cfg_checksum, unsigned lineno_checksum)
550 basic_block bb;
551 int i;
552 int num_edges = 0;
553 int changes;
554 int passes;
555 int hist_br_prob[20];
556 int num_branches;
557 gcov_type *exec_counts = get_exec_counts (cfg_checksum, lineno_checksum);
558 int inconsistent = 0;
560 /* Very simple sanity checks so we catch bugs in our profiling code. */
561 if (!profile_info)
562 return;
564 if (profile_info->sum_all < profile_info->sum_max)
566 error ("corrupted profile info: sum_all is smaller than sum_max");
567 exec_counts = NULL;
570 /* Attach extra info block to each bb. */
571 alloc_aux_for_blocks (sizeof (struct bb_profile_info));
572 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun), NULL, next_bb)
574 edge e;
575 edge_iterator ei;
577 FOR_EACH_EDGE (e, ei, bb->succs)
578 if (!EDGE_INFO (e)->ignore)
579 BB_INFO (bb)->succ_count++;
580 FOR_EACH_EDGE (e, ei, bb->preds)
581 if (!EDGE_INFO (e)->ignore)
582 BB_INFO (bb)->pred_count++;
585 /* Avoid predicting entry on exit nodes. */
586 BB_INFO (EXIT_BLOCK_PTR_FOR_FN (cfun))->succ_count = 2;
587 BB_INFO (ENTRY_BLOCK_PTR_FOR_FN (cfun))->pred_count = 2;
589 num_edges = read_profile_edge_counts (exec_counts);
591 if (dump_file)
592 fprintf (dump_file, "\n%d edge counts read\n", num_edges);
594 /* For every block in the file,
595 - if every exit/entrance edge has a known count, then set the block count
596 - if the block count is known, and every exit/entrance edge but one has
597 a known execution count, then set the count of the remaining edge
599 As edge counts are set, decrement the succ/pred count, but don't delete
600 the edge, that way we can easily tell when all edges are known, or only
601 one edge is unknown. */
603 /* The order that the basic blocks are iterated through is important.
604 Since the code that finds spanning trees starts with block 0, low numbered
605 edges are put on the spanning tree in preference to high numbered edges.
606 Hence, most instrumented edges are at the end. Graph solving works much
607 faster if we propagate numbers from the end to the start.
609 This takes an average of slightly more than 3 passes. */
611 changes = 1;
612 passes = 0;
613 while (changes)
615 passes++;
616 changes = 0;
617 FOR_BB_BETWEEN (bb, EXIT_BLOCK_PTR_FOR_FN (cfun), NULL, prev_bb)
619 struct bb_profile_info *bi = BB_INFO (bb);
620 if (! bi->count_valid)
622 if (bi->succ_count == 0)
624 edge e;
625 edge_iterator ei;
626 gcov_type total = 0;
628 FOR_EACH_EDGE (e, ei, bb->succs)
629 total += e->count;
630 bb->count = total;
631 bi->count_valid = 1;
632 changes = 1;
634 else if (bi->pred_count == 0)
636 edge e;
637 edge_iterator ei;
638 gcov_type total = 0;
640 FOR_EACH_EDGE (e, ei, bb->preds)
641 total += e->count;
642 bb->count = total;
643 bi->count_valid = 1;
644 changes = 1;
647 if (bi->count_valid)
649 if (bi->succ_count == 1)
651 edge e;
652 edge_iterator ei;
653 gcov_type total = 0;
655 /* One of the counts will be invalid, but it is zero,
656 so adding it in also doesn't hurt. */
657 FOR_EACH_EDGE (e, ei, bb->succs)
658 total += e->count;
660 /* Search for the invalid edge, and set its count. */
661 FOR_EACH_EDGE (e, ei, bb->succs)
662 if (! EDGE_INFO (e)->count_valid && ! EDGE_INFO (e)->ignore)
663 break;
665 /* Calculate count for remaining edge by conservation. */
666 total = bb->count - total;
668 gcc_assert (e);
669 EDGE_INFO (e)->count_valid = 1;
670 e->count = total;
671 bi->succ_count--;
673 BB_INFO (e->dest)->pred_count--;
674 changes = 1;
676 if (bi->pred_count == 1)
678 edge e;
679 edge_iterator ei;
680 gcov_type total = 0;
682 /* One of the counts will be invalid, but it is zero,
683 so adding it in also doesn't hurt. */
684 FOR_EACH_EDGE (e, ei, bb->preds)
685 total += e->count;
687 /* Search for the invalid edge, and set its count. */
688 FOR_EACH_EDGE (e, ei, bb->preds)
689 if (!EDGE_INFO (e)->count_valid && !EDGE_INFO (e)->ignore)
690 break;
692 /* Calculate count for remaining edge by conservation. */
693 total = bb->count - total + e->count;
695 gcc_assert (e);
696 EDGE_INFO (e)->count_valid = 1;
697 e->count = total;
698 bi->pred_count--;
700 BB_INFO (e->src)->succ_count--;
701 changes = 1;
706 if (dump_file)
708 int overlap = compute_frequency_overlap ();
709 gimple_dump_cfg (dump_file, dump_flags);
710 fprintf (dump_file, "Static profile overlap: %d.%d%%\n",
711 overlap / (OVERLAP_BASE / 100),
712 overlap % (OVERLAP_BASE / 100));
715 total_num_passes += passes;
716 if (dump_file)
717 fprintf (dump_file, "Graph solving took %d passes.\n\n", passes);
719 /* If the graph has been correctly solved, every block will have a
720 succ and pred count of zero. */
721 FOR_EACH_BB_FN (bb, cfun)
723 gcc_assert (!BB_INFO (bb)->succ_count && !BB_INFO (bb)->pred_count);
726 /* Check for inconsistent basic block counts */
727 inconsistent = is_inconsistent ();
729 if (inconsistent)
731 if (flag_profile_correction)
733 /* Inconsistency detected. Make it flow-consistent. */
734 static int informed = 0;
735 if (dump_enabled_p () && informed == 0)
737 informed = 1;
738 dump_printf_loc (MSG_NOTE, input_location,
739 "correcting inconsistent profile data\n");
741 correct_negative_edge_counts ();
742 /* Set bb counts to the sum of the outgoing edge counts */
743 set_bb_counts ();
744 if (dump_file)
745 fprintf (dump_file, "\nCalling mcf_smooth_cfg\n");
746 mcf_smooth_cfg ();
748 else
749 error ("corrupted profile info: profile data is not flow-consistent");
752 /* For every edge, calculate its branch probability and add a reg_note
753 to the branch insn to indicate this. */
755 for (i = 0; i < 20; i++)
756 hist_br_prob[i] = 0;
757 num_branches = 0;
759 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun), NULL, next_bb)
761 edge e;
762 edge_iterator ei;
764 if (bb->count < 0)
766 error ("corrupted profile info: number of iterations for basic block %d thought to be %i",
767 bb->index, (int)bb->count);
768 bb->count = 0;
770 FOR_EACH_EDGE (e, ei, bb->succs)
772 /* Function may return twice in the cased the called function is
773 setjmp or calls fork, but we can't represent this by extra
774 edge from the entry, since extra edge from the exit is
775 already present. We get negative frequency from the entry
776 point. */
777 if ((e->count < 0
778 && e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
779 || (e->count > bb->count
780 && e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun)))
782 if (block_ends_with_call_p (bb))
783 e->count = e->count < 0 ? 0 : bb->count;
785 if (e->count < 0 || e->count > bb->count)
787 error ("corrupted profile info: number of executions for edge %d-%d thought to be %i",
788 e->src->index, e->dest->index,
789 (int)e->count);
790 e->count = bb->count / 2;
793 if (bb->count)
795 FOR_EACH_EDGE (e, ei, bb->succs)
796 e->probability = GCOV_COMPUTE_SCALE (e->count, bb->count);
797 if (bb->index >= NUM_FIXED_BLOCKS
798 && block_ends_with_condjump_p (bb)
799 && EDGE_COUNT (bb->succs) >= 2)
801 int prob;
802 edge e;
803 int index;
805 /* Find the branch edge. It is possible that we do have fake
806 edges here. */
807 FOR_EACH_EDGE (e, ei, bb->succs)
808 if (!(e->flags & (EDGE_FAKE | EDGE_FALLTHRU)))
809 break;
811 prob = e->probability;
812 index = prob * 20 / REG_BR_PROB_BASE;
814 if (index == 20)
815 index = 19;
816 hist_br_prob[index]++;
818 num_branches++;
821 /* As a last resort, distribute the probabilities evenly.
822 Use simple heuristics that if there are normal edges,
823 give all abnormals frequency of 0, otherwise distribute the
824 frequency over abnormals (this is the case of noreturn
825 calls). */
826 else if (profile_status_for_fn (cfun) == PROFILE_ABSENT)
828 int total = 0;
830 FOR_EACH_EDGE (e, ei, bb->succs)
831 if (!(e->flags & (EDGE_COMPLEX | EDGE_FAKE)))
832 total ++;
833 if (total)
835 FOR_EACH_EDGE (e, ei, bb->succs)
836 if (!(e->flags & (EDGE_COMPLEX | EDGE_FAKE)))
837 e->probability = REG_BR_PROB_BASE / total;
838 else
839 e->probability = 0;
841 else
843 total += EDGE_COUNT (bb->succs);
844 FOR_EACH_EDGE (e, ei, bb->succs)
845 e->probability = REG_BR_PROB_BASE / total;
847 if (bb->index >= NUM_FIXED_BLOCKS
848 && block_ends_with_condjump_p (bb)
849 && EDGE_COUNT (bb->succs) >= 2)
850 num_branches++;
853 counts_to_freqs ();
854 profile_status_for_fn (cfun) = PROFILE_READ;
855 compute_function_frequency ();
857 if (dump_file)
859 fprintf (dump_file, "%d branches\n", num_branches);
860 if (num_branches)
861 for (i = 0; i < 10; i++)
862 fprintf (dump_file, "%d%% branches in range %d-%d%%\n",
863 (hist_br_prob[i] + hist_br_prob[19-i]) * 100 / num_branches,
864 5 * i, 5 * i + 5);
866 total_num_branches += num_branches;
867 for (i = 0; i < 20; i++)
868 total_hist_br_prob[i] += hist_br_prob[i];
870 fputc ('\n', dump_file);
871 fputc ('\n', dump_file);
874 free_aux_for_blocks ();
877 /* Load value histograms values whose description is stored in VALUES array
878 from .gcda file.
880 CFG_CHECKSUM is the precomputed checksum for the CFG. */
882 static void
883 compute_value_histograms (histogram_values values, unsigned cfg_checksum,
884 unsigned lineno_checksum)
886 unsigned i, j, t, any;
887 unsigned n_histogram_counters[GCOV_N_VALUE_COUNTERS];
888 gcov_type *histogram_counts[GCOV_N_VALUE_COUNTERS];
889 gcov_type *act_count[GCOV_N_VALUE_COUNTERS];
890 gcov_type *aact_count;
891 struct cgraph_node *node;
893 for (t = 0; t < GCOV_N_VALUE_COUNTERS; t++)
894 n_histogram_counters[t] = 0;
896 for (i = 0; i < values.length (); i++)
898 histogram_value hist = values[i];
899 n_histogram_counters[(int) hist->type] += hist->n_counters;
902 any = 0;
903 for (t = 0; t < GCOV_N_VALUE_COUNTERS; t++)
905 if (!n_histogram_counters[t])
907 histogram_counts[t] = NULL;
908 continue;
911 histogram_counts[t] =
912 get_coverage_counts (COUNTER_FOR_HIST_TYPE (t),
913 n_histogram_counters[t], cfg_checksum,
914 lineno_checksum, NULL);
915 if (histogram_counts[t])
916 any = 1;
917 act_count[t] = histogram_counts[t];
919 if (!any)
920 return;
922 for (i = 0; i < values.length (); i++)
924 histogram_value hist = values[i];
925 gimple stmt = hist->hvalue.stmt;
927 t = (int) hist->type;
929 aact_count = act_count[t];
931 if (act_count[t])
932 act_count[t] += hist->n_counters;
934 gimple_add_histogram_value (cfun, stmt, hist);
935 hist->hvalue.counters = XNEWVEC (gcov_type, hist->n_counters);
936 for (j = 0; j < hist->n_counters; j++)
937 if (aact_count)
938 hist->hvalue.counters[j] = aact_count[j];
939 else
940 hist->hvalue.counters[j] = 0;
942 /* Time profiler counter is not related to any statement,
943 so that we have to read the counter and set the value to
944 the corresponding call graph node. */
945 if (hist->type == HIST_TYPE_TIME_PROFILE)
947 node = cgraph_node::get (hist->fun->decl);
948 node->tp_first_run = hist->hvalue.counters[0];
950 if (dump_file)
951 fprintf (dump_file, "Read tp_first_run: %d\n", node->tp_first_run);
955 for (t = 0; t < GCOV_N_VALUE_COUNTERS; t++)
956 free (histogram_counts[t]);
959 /* When passed NULL as file_name, initialize.
960 When passed something else, output the necessary commands to change
961 line to LINE and offset to FILE_NAME. */
962 static void
963 output_location (char const *file_name, int line,
964 gcov_position_t *offset, basic_block bb)
966 static char const *prev_file_name;
967 static int prev_line;
968 bool name_differs, line_differs;
970 if (!file_name)
972 prev_file_name = NULL;
973 prev_line = -1;
974 return;
977 name_differs = !prev_file_name || filename_cmp (file_name, prev_file_name);
978 line_differs = prev_line != line;
980 if (name_differs || line_differs)
982 if (!*offset)
984 *offset = gcov_write_tag (GCOV_TAG_LINES);
985 gcov_write_unsigned (bb->index);
986 name_differs = line_differs=true;
989 /* If this is a new source file, then output the
990 file's name to the .bb file. */
991 if (name_differs)
993 prev_file_name = file_name;
994 gcov_write_unsigned (0);
995 gcov_write_string (prev_file_name);
997 if (line_differs)
999 gcov_write_unsigned (line);
1000 prev_line = line;
1005 /* Instrument and/or analyze program behavior based on program the CFG.
1007 This function creates a representation of the control flow graph (of
1008 the function being compiled) that is suitable for the instrumentation
1009 of edges and/or converting measured edge counts to counts on the
1010 complete CFG.
1012 When FLAG_PROFILE_ARCS is nonzero, this function instruments the edges in
1013 the flow graph that are needed to reconstruct the dynamic behavior of the
1014 flow graph. This data is written to the gcno file for gcov.
1016 When FLAG_BRANCH_PROBABILITIES is nonzero, this function reads auxiliary
1017 information from the gcda file containing edge count information from
1018 previous executions of the function being compiled. In this case, the
1019 control flow graph is annotated with actual execution counts by
1020 compute_branch_probabilities().
1022 Main entry point of this file. */
1024 void
1025 branch_prob (void)
1027 basic_block bb;
1028 unsigned i;
1029 unsigned num_edges, ignored_edges;
1030 unsigned num_instrumented;
1031 struct edge_list *el;
1032 histogram_values values = histogram_values ();
1033 unsigned cfg_checksum, lineno_checksum;
1035 total_num_times_called++;
1037 flow_call_edges_add (NULL);
1038 add_noreturn_fake_exit_edges ();
1040 /* We can't handle cyclic regions constructed using abnormal edges.
1041 To avoid these we replace every source of abnormal edge by a fake
1042 edge from entry node and every destination by fake edge to exit.
1043 This keeps graph acyclic and our calculation exact for all normal
1044 edges except for exit and entrance ones.
1046 We also add fake exit edges for each call and asm statement in the
1047 basic, since it may not return. */
1049 FOR_EACH_BB_FN (bb, cfun)
1051 int need_exit_edge = 0, need_entry_edge = 0;
1052 int have_exit_edge = 0, have_entry_edge = 0;
1053 edge e;
1054 edge_iterator ei;
1056 /* Functions returning multiple times are not handled by extra edges.
1057 Instead we simply allow negative counts on edges from exit to the
1058 block past call and corresponding probabilities. We can't go
1059 with the extra edges because that would result in flowgraph that
1060 needs to have fake edges outside the spanning tree. */
1062 FOR_EACH_EDGE (e, ei, bb->succs)
1064 gimple_stmt_iterator gsi;
1065 gimple last = NULL;
1067 /* It may happen that there are compiler generated statements
1068 without a locus at all. Go through the basic block from the
1069 last to the first statement looking for a locus. */
1070 for (gsi = gsi_last_nondebug_bb (bb);
1071 !gsi_end_p (gsi);
1072 gsi_prev_nondebug (&gsi))
1074 last = gsi_stmt (gsi);
1075 if (gimple_has_location (last))
1076 break;
1079 /* Edge with goto locus might get wrong coverage info unless
1080 it is the only edge out of BB.
1081 Don't do that when the locuses match, so
1082 if (blah) goto something;
1083 is not computed twice. */
1084 if (last
1085 && gimple_has_location (last)
1086 && LOCATION_LOCUS (e->goto_locus) != UNKNOWN_LOCATION
1087 && !single_succ_p (bb)
1088 && (LOCATION_FILE (e->goto_locus)
1089 != LOCATION_FILE (gimple_location (last))
1090 || (LOCATION_LINE (e->goto_locus)
1091 != LOCATION_LINE (gimple_location (last)))))
1093 basic_block new_bb = split_edge (e);
1094 edge ne = single_succ_edge (new_bb);
1095 ne->goto_locus = e->goto_locus;
1097 if ((e->flags & (EDGE_ABNORMAL | EDGE_ABNORMAL_CALL))
1098 && e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
1099 need_exit_edge = 1;
1100 if (e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
1101 have_exit_edge = 1;
1103 FOR_EACH_EDGE (e, ei, bb->preds)
1105 if ((e->flags & (EDGE_ABNORMAL | EDGE_ABNORMAL_CALL))
1106 && e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun))
1107 need_entry_edge = 1;
1108 if (e->src == ENTRY_BLOCK_PTR_FOR_FN (cfun))
1109 have_entry_edge = 1;
1112 if (need_exit_edge && !have_exit_edge)
1114 if (dump_file)
1115 fprintf (dump_file, "Adding fake exit edge to bb %i\n",
1116 bb->index);
1117 make_edge (bb, EXIT_BLOCK_PTR_FOR_FN (cfun), EDGE_FAKE);
1119 if (need_entry_edge && !have_entry_edge)
1121 if (dump_file)
1122 fprintf (dump_file, "Adding fake entry edge to bb %i\n",
1123 bb->index);
1124 make_edge (ENTRY_BLOCK_PTR_FOR_FN (cfun), bb, EDGE_FAKE);
1125 /* Avoid bbs that have both fake entry edge and also some
1126 exit edge. One of those edges wouldn't be added to the
1127 spanning tree, but we can't instrument any of them. */
1128 if (have_exit_edge || need_exit_edge)
1130 gimple_stmt_iterator gsi;
1131 gimple first;
1133 gsi = gsi_start_nondebug_after_labels_bb (bb);
1134 gcc_checking_assert (!gsi_end_p (gsi));
1135 first = gsi_stmt (gsi);
1136 /* Don't split the bbs containing __builtin_setjmp_receiver
1137 or ABNORMAL_DISPATCHER calls. These are very
1138 special and don't expect anything to be inserted before
1139 them. */
1140 if (is_gimple_call (first)
1141 && (gimple_call_builtin_p (first, BUILT_IN_SETJMP_RECEIVER)
1142 || (gimple_call_flags (first) & ECF_RETURNS_TWICE)
1143 || (gimple_call_internal_p (first)
1144 && (gimple_call_internal_fn (first)
1145 == IFN_ABNORMAL_DISPATCHER))))
1146 continue;
1148 if (dump_file)
1149 fprintf (dump_file, "Splitting bb %i after labels\n",
1150 bb->index);
1151 split_block_after_labels (bb);
1156 el = create_edge_list ();
1157 num_edges = NUM_EDGES (el);
1158 alloc_aux_for_edges (sizeof (struct edge_profile_info));
1160 /* The basic blocks are expected to be numbered sequentially. */
1161 compact_blocks ();
1163 ignored_edges = 0;
1164 for (i = 0 ; i < num_edges ; i++)
1166 edge e = INDEX_EDGE (el, i);
1167 e->count = 0;
1169 /* Mark edges we've replaced by fake edges above as ignored. */
1170 if ((e->flags & (EDGE_ABNORMAL | EDGE_ABNORMAL_CALL))
1171 && e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun)
1172 && e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
1174 EDGE_INFO (e)->ignore = 1;
1175 ignored_edges++;
1179 /* Create spanning tree from basic block graph, mark each edge that is
1180 on the spanning tree. We insert as many abnormal and critical edges
1181 as possible to minimize number of edge splits necessary. */
1183 find_spanning_tree (el);
1185 /* Fake edges that are not on the tree will not be instrumented, so
1186 mark them ignored. */
1187 for (num_instrumented = i = 0; i < num_edges; i++)
1189 edge e = INDEX_EDGE (el, i);
1190 struct edge_profile_info *inf = EDGE_INFO (e);
1192 if (inf->ignore || inf->on_tree)
1193 /*NOP*/;
1194 else if (e->flags & EDGE_FAKE)
1196 inf->ignore = 1;
1197 ignored_edges++;
1199 else
1200 num_instrumented++;
1203 total_num_blocks += n_basic_blocks_for_fn (cfun);
1204 if (dump_file)
1205 fprintf (dump_file, "%d basic blocks\n", n_basic_blocks_for_fn (cfun));
1207 total_num_edges += num_edges;
1208 if (dump_file)
1209 fprintf (dump_file, "%d edges\n", num_edges);
1211 total_num_edges_ignored += ignored_edges;
1212 if (dump_file)
1213 fprintf (dump_file, "%d ignored edges\n", ignored_edges);
1215 total_num_edges_instrumented += num_instrumented;
1216 if (dump_file)
1217 fprintf (dump_file, "%d instrumentation edges\n", num_instrumented);
1219 /* Compute two different checksums. Note that we want to compute
1220 the checksum in only once place, since it depends on the shape
1221 of the control flow which can change during
1222 various transformations. */
1223 cfg_checksum = coverage_compute_cfg_checksum (cfun);
1224 lineno_checksum = coverage_compute_lineno_checksum ();
1226 /* Write the data from which gcov can reconstruct the basic block
1227 graph and function line numbers (the gcno file). */
1228 if (coverage_begin_function (lineno_checksum, cfg_checksum))
1230 gcov_position_t offset;
1232 /* Basic block flags */
1233 offset = gcov_write_tag (GCOV_TAG_BLOCKS);
1234 for (i = 0; i != (unsigned) (n_basic_blocks_for_fn (cfun)); i++)
1235 gcov_write_unsigned (0);
1236 gcov_write_length (offset);
1238 /* Arcs */
1239 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun),
1240 EXIT_BLOCK_PTR_FOR_FN (cfun), next_bb)
1242 edge e;
1243 edge_iterator ei;
1245 offset = gcov_write_tag (GCOV_TAG_ARCS);
1246 gcov_write_unsigned (bb->index);
1248 FOR_EACH_EDGE (e, ei, bb->succs)
1250 struct edge_profile_info *i = EDGE_INFO (e);
1251 if (!i->ignore)
1253 unsigned flag_bits = 0;
1255 if (i->on_tree)
1256 flag_bits |= GCOV_ARC_ON_TREE;
1257 if (e->flags & EDGE_FAKE)
1258 flag_bits |= GCOV_ARC_FAKE;
1259 if (e->flags & EDGE_FALLTHRU)
1260 flag_bits |= GCOV_ARC_FALLTHROUGH;
1261 /* On trees we don't have fallthru flags, but we can
1262 recompute them from CFG shape. */
1263 if (e->flags & (EDGE_TRUE_VALUE | EDGE_FALSE_VALUE)
1264 && e->src->next_bb == e->dest)
1265 flag_bits |= GCOV_ARC_FALLTHROUGH;
1267 gcov_write_unsigned (e->dest->index);
1268 gcov_write_unsigned (flag_bits);
1272 gcov_write_length (offset);
1275 /* Line numbers. */
1276 /* Initialize the output. */
1277 output_location (NULL, 0, NULL, NULL);
1279 FOR_EACH_BB_FN (bb, cfun)
1281 gimple_stmt_iterator gsi;
1282 gcov_position_t offset = 0;
1284 if (bb == ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb)
1286 expanded_location curr_location =
1287 expand_location (DECL_SOURCE_LOCATION (current_function_decl));
1288 output_location (curr_location.file, curr_location.line,
1289 &offset, bb);
1292 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1294 gimple stmt = gsi_stmt (gsi);
1295 if (gimple_has_location (stmt))
1296 output_location (gimple_filename (stmt), gimple_lineno (stmt),
1297 &offset, bb);
1300 /* Notice GOTO expressions eliminated while constructing the CFG. */
1301 if (single_succ_p (bb)
1302 && LOCATION_LOCUS (single_succ_edge (bb)->goto_locus)
1303 != UNKNOWN_LOCATION)
1305 expanded_location curr_location
1306 = expand_location (single_succ_edge (bb)->goto_locus);
1307 output_location (curr_location.file, curr_location.line,
1308 &offset, bb);
1311 if (offset)
1313 /* A file of NULL indicates the end of run. */
1314 gcov_write_unsigned (0);
1315 gcov_write_string (NULL);
1316 gcov_write_length (offset);
1321 if (flag_profile_values)
1322 gimple_find_values_to_profile (&values);
1324 if (flag_branch_probabilities)
1326 compute_branch_probabilities (cfg_checksum, lineno_checksum);
1327 if (flag_profile_values)
1328 compute_value_histograms (values, cfg_checksum, lineno_checksum);
1331 remove_fake_edges ();
1333 /* For each edge not on the spanning tree, add counting code. */
1334 if (profile_arc_flag
1335 && coverage_counter_alloc (GCOV_COUNTER_ARCS, num_instrumented))
1337 unsigned n_instrumented;
1339 gimple_init_edge_profiler ();
1341 n_instrumented = instrument_edges (el);
1343 gcc_assert (n_instrumented == num_instrumented);
1345 if (flag_profile_values)
1346 instrument_values (values);
1348 /* Commit changes done by instrumentation. */
1349 gsi_commit_edge_inserts ();
1352 free_aux_for_edges ();
1354 values.release ();
1355 free_edge_list (el);
1356 coverage_end_function (lineno_checksum, cfg_checksum);
1359 /* Union find algorithm implementation for the basic blocks using
1360 aux fields. */
1362 static basic_block
1363 find_group (basic_block bb)
1365 basic_block group = bb, bb1;
1367 while ((basic_block) group->aux != group)
1368 group = (basic_block) group->aux;
1370 /* Compress path. */
1371 while ((basic_block) bb->aux != group)
1373 bb1 = (basic_block) bb->aux;
1374 bb->aux = (void *) group;
1375 bb = bb1;
1377 return group;
1380 static void
1381 union_groups (basic_block bb1, basic_block bb2)
1383 basic_block bb1g = find_group (bb1);
1384 basic_block bb2g = find_group (bb2);
1386 /* ??? I don't have a place for the rank field. OK. Lets go w/o it,
1387 this code is unlikely going to be performance problem anyway. */
1388 gcc_assert (bb1g != bb2g);
1390 bb1g->aux = bb2g;
1393 /* This function searches all of the edges in the program flow graph, and puts
1394 as many bad edges as possible onto the spanning tree. Bad edges include
1395 abnormals edges, which can't be instrumented at the moment. Since it is
1396 possible for fake edges to form a cycle, we will have to develop some
1397 better way in the future. Also put critical edges to the tree, since they
1398 are more expensive to instrument. */
1400 static void
1401 find_spanning_tree (struct edge_list *el)
1403 int i;
1404 int num_edges = NUM_EDGES (el);
1405 basic_block bb;
1407 /* We use aux field for standard union-find algorithm. */
1408 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun), NULL, next_bb)
1409 bb->aux = bb;
1411 /* Add fake edge exit to entry we can't instrument. */
1412 union_groups (EXIT_BLOCK_PTR_FOR_FN (cfun), ENTRY_BLOCK_PTR_FOR_FN (cfun));
1414 /* First add all abnormal edges to the tree unless they form a cycle. Also
1415 add all edges to the exit block to avoid inserting profiling code behind
1416 setting return value from function. */
1417 for (i = 0; i < num_edges; i++)
1419 edge e = INDEX_EDGE (el, i);
1420 if (((e->flags & (EDGE_ABNORMAL | EDGE_ABNORMAL_CALL | EDGE_FAKE))
1421 || e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
1422 && !EDGE_INFO (e)->ignore
1423 && (find_group (e->src) != find_group (e->dest)))
1425 if (dump_file)
1426 fprintf (dump_file, "Abnormal edge %d to %d put to tree\n",
1427 e->src->index, e->dest->index);
1428 EDGE_INFO (e)->on_tree = 1;
1429 union_groups (e->src, e->dest);
1433 /* Now insert all critical edges to the tree unless they form a cycle. */
1434 for (i = 0; i < num_edges; i++)
1436 edge e = INDEX_EDGE (el, i);
1437 if (EDGE_CRITICAL_P (e) && !EDGE_INFO (e)->ignore
1438 && find_group (e->src) != find_group (e->dest))
1440 if (dump_file)
1441 fprintf (dump_file, "Critical edge %d to %d put to tree\n",
1442 e->src->index, e->dest->index);
1443 EDGE_INFO (e)->on_tree = 1;
1444 union_groups (e->src, e->dest);
1448 /* And now the rest. */
1449 for (i = 0; i < num_edges; i++)
1451 edge e = INDEX_EDGE (el, i);
1452 if (!EDGE_INFO (e)->ignore
1453 && find_group (e->src) != find_group (e->dest))
1455 if (dump_file)
1456 fprintf (dump_file, "Normal edge %d to %d put to tree\n",
1457 e->src->index, e->dest->index);
1458 EDGE_INFO (e)->on_tree = 1;
1459 union_groups (e->src, e->dest);
1463 clear_aux_for_blocks ();
1466 /* Perform file-level initialization for branch-prob processing. */
1468 void
1469 init_branch_prob (void)
1471 int i;
1473 total_num_blocks = 0;
1474 total_num_edges = 0;
1475 total_num_edges_ignored = 0;
1476 total_num_edges_instrumented = 0;
1477 total_num_blocks_created = 0;
1478 total_num_passes = 0;
1479 total_num_times_called = 0;
1480 total_num_branches = 0;
1481 for (i = 0; i < 20; i++)
1482 total_hist_br_prob[i] = 0;
1485 /* Performs file-level cleanup after branch-prob processing
1486 is completed. */
1488 void
1489 end_branch_prob (void)
1491 if (dump_file)
1493 fprintf (dump_file, "\n");
1494 fprintf (dump_file, "Total number of blocks: %d\n",
1495 total_num_blocks);
1496 fprintf (dump_file, "Total number of edges: %d\n", total_num_edges);
1497 fprintf (dump_file, "Total number of ignored edges: %d\n",
1498 total_num_edges_ignored);
1499 fprintf (dump_file, "Total number of instrumented edges: %d\n",
1500 total_num_edges_instrumented);
1501 fprintf (dump_file, "Total number of blocks created: %d\n",
1502 total_num_blocks_created);
1503 fprintf (dump_file, "Total number of graph solution passes: %d\n",
1504 total_num_passes);
1505 if (total_num_times_called != 0)
1506 fprintf (dump_file, "Average number of graph solution passes: %d\n",
1507 (total_num_passes + (total_num_times_called >> 1))
1508 / total_num_times_called);
1509 fprintf (dump_file, "Total number of branches: %d\n",
1510 total_num_branches);
1511 if (total_num_branches)
1513 int i;
1515 for (i = 0; i < 10; i++)
1516 fprintf (dump_file, "%d%% branches in range %d-%d%%\n",
1517 (total_hist_br_prob[i] + total_hist_br_prob[19-i]) * 100
1518 / total_num_branches, 5*i, 5*i+5);