1 /* Calculate branch probabilities, and basic block execution counts.
2 Copyright (C) 1990, 1991, 1992, 1993, 1994, 1996, 1997, 1998, 1999,
3 2000, 2001 Free Software Foundation, Inc.
4 Contributed by James E. Wilson, UC Berkeley/Cygnus Support;
5 based on some ideas from Dain Samples of UC Berkeley.
6 Further mangling by Bob Manson, Cygnus Support.
8 This file is part of GCC.
10 GCC is free software; you can redistribute it and/or modify it under
11 the terms of the GNU General Public License as published by the Free
12 Software Foundation; either version 2, or (at your option) any later
15 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
16 WARRANTY; without even the implied warranty of MERCHANTABILITY or
17 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
20 You should have received a copy of the GNU General Public License
21 along with GCC; see the file COPYING. If not, write to the Free
22 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
25 /* ??? Register allocation should use basic block execution counts to
26 give preference to the most commonly executed blocks. */
28 /* ??? The .da files are not safe. Changing the program after creating .da
29 files or using different options when compiling with -fbranch-probabilities
30 can result the arc data not matching the program. Maybe add instrumented
31 arc count to .bbg file? Maybe check whether PFG matches the .bbg file? */
33 /* ??? Should calculate branch probabilities before instrumenting code, since
34 then we can use arc counts to help decide which arcs to instrument. */
41 #include "insn-config.h"
48 #include "hard-reg-set.h"
49 #include "basic-block.h"
54 #include "langhooks.h"
56 /* Additional information about the edges we need. */
59 unsigned int count_valid : 1;
60 unsigned int on_tree : 1;
61 unsigned int ignore : 1;
65 unsigned int count_valid : 1;
70 #define EDGE_INFO(e) ((struct edge_info *) (e)->aux)
71 #define BB_INFO(b) ((struct bb_info *) (b)->aux)
73 /* Keep all basic block indexes nonnegative in the gcov output. Index 0
74 is used for entry block, last block exit block. */
75 #define GCOV_INDEX_TO_BB(i) ((i) == 0 ? ENTRY_BLOCK_PTR \
76 : (((i) == n_basic_blocks + 1) \
77 ? EXIT_BLOCK_PTR : BASIC_BLOCK ((i)-1)))
78 #define BB_TO_GCOV_INDEX(bb) ((bb) == ENTRY_BLOCK_PTR ? 0 \
79 : ((bb) == EXIT_BLOCK_PTR \
80 ? n_basic_blocks + 1 : (bb)->index + 1))
82 /* Name and file pointer of the output file for the basic block graph. */
84 static FILE *bbg_file;
86 /* Name and file pointer of the input file for the arc count data. */
90 /* Pointer of the output file for the basic block/line number map. */
93 /* Last source file name written to bb_file. */
95 static char *last_bb_file_name;
97 /* Collect statistics on the performance of this pass for the entire source
100 static int total_num_blocks;
101 static int total_num_edges;
102 static int total_num_edges_ignored;
103 static int total_num_edges_instrumented;
104 static int total_num_blocks_created;
105 static int total_num_passes;
106 static int total_num_times_called;
107 static int total_hist_br_prob[20];
108 static int total_num_never_executed;
109 static int total_num_branches;
111 /* Forward declarations. */
112 static void find_spanning_tree PARAMS ((struct edge_list *));
113 static void init_edge_profiler PARAMS ((void));
114 static rtx gen_edge_profiler PARAMS ((int));
115 static void instrument_edges PARAMS ((struct edge_list *));
116 static void output_gcov_string PARAMS ((const char *, long));
117 static void compute_branch_probabilities PARAMS ((void));
118 static gcov_type * get_exec_counts PARAMS ((void));
119 static long compute_checksum PARAMS ((void));
120 static basic_block find_group PARAMS ((basic_block));
121 static void union_groups PARAMS ((basic_block, basic_block));
123 /* If non-zero, we need to output a constructor to set up the
124 per-object-file data. */
125 static int need_func_profiler = 0;
127 /* Add edge instrumentation code to the entire insn chain.
129 F is the first insn of the chain.
130 NUM_BLOCKS is the number of basic blocks found in F. */
133 instrument_edges (el)
134 struct edge_list *el;
137 int num_instr_edges = 0;
138 int num_edges = NUM_EDGES (el);
139 remove_fake_edges ();
141 for (i = 0; i < n_basic_blocks + 2; i++)
143 basic_block bb = GCOV_INDEX_TO_BB (i);
147 struct edge_info *inf = EDGE_INFO (e);
148 if (!inf->ignore && !inf->on_tree)
150 if (e->flags & EDGE_ABNORMAL)
153 fprintf (rtl_dump_file, "Edge %d to %d instrumented%s\n",
154 e->src->index, e->dest->index,
155 EDGE_CRITICAL_P (e) ? " (and split)" : "");
156 need_func_profiler = 1;
157 insert_insn_on_edge (
158 gen_edge_profiler (total_num_edges_instrumented
159 + num_instr_edges++), e);
165 profile_info.count_edges_instrumented_now = num_instr_edges;
166 total_num_edges_instrumented += num_instr_edges;
167 profile_info.count_instrumented_edges = total_num_edges_instrumented;
169 total_num_blocks_created += num_edges;
171 fprintf (rtl_dump_file, "%d edges instrumented\n", num_instr_edges);
173 commit_edge_insertions_watch_calls ();
176 /* Output STRING to bb_file, surrounded by DELIMITER. */
179 output_gcov_string (string, delimiter)
185 /* Write a delimiter to indicate that a file name follows. */
186 __write_long (delimiter, bb_file, 4);
188 /* Write the string. */
189 temp = strlen (string) + 1;
190 fwrite (string, temp, 1, bb_file);
192 /* Append a few zeros, to align the output to a 4 byte boundary. */
198 c[0] = c[1] = c[2] = c[3] = 0;
199 fwrite (c, sizeof (char), 4 - temp, bb_file);
202 /* Store another delimiter in the .bb file, just to make it easy to find
203 the end of the file name. */
204 __write_long (delimiter, bb_file, 4);
208 /* Computes hybrid profile for all matching entries in da_file.
209 Sets max_counter_in_program as a side effect. */
219 char *function_name_buffer;
220 int function_name_buffer_len;
221 gcov_type max_counter_in_run;
223 profile_info.max_counter_in_program = 0;
224 profile_info.count_profiles_merged = 0;
226 /* No .da file, no execution counts. */
230 /* Count the edges to be (possibly) instrumented. */
232 for (i = 0; i < n_basic_blocks + 2; i++)
234 basic_block bb = GCOV_INDEX_TO_BB (i);
236 for (e = bb->succ; e; e = e->succ_next)
237 if (!EDGE_INFO (e)->ignore && !EDGE_INFO (e)->on_tree)
243 /* now read and combine all matching profiles. */
245 profile = xmalloc (sizeof (gcov_type) * num_edges);
247 function_name_buffer_len = strlen (current_function_name) + 1;
248 function_name_buffer = xmalloc (function_name_buffer_len + 1);
250 for (i = 0; i < num_edges; i++)
255 long magic, extra_bytes;
259 if (__read_long (&magic, da_file, 4) != 0)
268 if (__read_long (&func_count, da_file, 4) != 0)
274 if (__read_long (&extra_bytes, da_file, 4) != 0)
280 fseek (da_file, 4 + 8, SEEK_CUR);
282 /* read the maximal counter. */
283 __read_gcov_type (&max_counter_in_run, da_file, 8);
285 /* skip the rest of "statistics" emited by __bb_exit_func. */
286 fseek (da_file, extra_bytes - (4 + 8 + 8), SEEK_CUR);
288 for (i = 0; i < func_count; i++)
294 if (__read_gcov_string
295 (function_name_buffer, function_name_buffer_len, da_file,
302 if (__read_long (&chksum, da_file, 4) != 0)
308 if (__read_long (&arc_count, da_file, 4) != 0)
314 if (strcmp (function_name_buffer, current_function_name) != 0)
317 if (fseek (da_file, arc_count * 8, SEEK_CUR) < 0)
323 else if (arc_count != num_edges
324 || chksum != profile_info.current_function_cfg_checksum)
325 okay = 0, mismatch = 1;
330 profile_info.max_counter_in_program += max_counter_in_run;
331 profile_info.count_profiles_merged++;
333 for (j = 0; j < arc_count; j++)
334 if (__read_gcov_type (&tmp, da_file, 8) != 0)
351 free (function_name_buffer);
357 ("Profile does not match flowgraph of function %s (out of date?)",
358 current_function_name);
360 error (".da file corrupted");
369 /* Compute the branch probabilities for the various branches.
370 Annotate them accordingly. */
373 compute_branch_probabilities ()
379 int hist_br_prob[20];
380 int num_never_executed;
382 gcov_type *exec_counts = get_exec_counts ();
383 int exec_counts_pos = 0;
385 /* Attach extra info block to each bb. */
387 alloc_aux_for_blocks (sizeof (struct bb_info));
388 for (i = 0; i < n_basic_blocks + 2; i++)
390 basic_block bb = GCOV_INDEX_TO_BB (i);
393 for (e = bb->succ; e; e = e->succ_next)
394 if (!EDGE_INFO (e)->ignore)
395 BB_INFO (bb)->succ_count++;
396 for (e = bb->pred; e; e = e->pred_next)
397 if (!EDGE_INFO (e)->ignore)
398 BB_INFO (bb)->pred_count++;
401 /* Avoid predicting entry on exit nodes. */
402 BB_INFO (EXIT_BLOCK_PTR)->succ_count = 2;
403 BB_INFO (ENTRY_BLOCK_PTR)->pred_count = 2;
405 /* For each edge not on the spanning tree, set its execution count from
408 /* The first count in the .da file is the number of times that the function
409 was entered. This is the exec_count for block zero. */
411 for (i = 0; i < n_basic_blocks + 2; i++)
413 basic_block bb = GCOV_INDEX_TO_BB (i);
415 for (e = bb->succ; e; e = e->succ_next)
416 if (!EDGE_INFO (e)->ignore && !EDGE_INFO (e)->on_tree)
421 e->count = exec_counts[exec_counts_pos++];
426 EDGE_INFO (e)->count_valid = 1;
427 BB_INFO (bb)->succ_count--;
428 BB_INFO (e->dest)->pred_count--;
431 fprintf (rtl_dump_file, "\nRead edge from %i to %i, count:",
432 bb->index, e->dest->index);
433 fprintf (rtl_dump_file, HOST_WIDEST_INT_PRINT_DEC,
434 (HOST_WIDEST_INT) e->count);
440 fprintf (rtl_dump_file, "\n%d edge counts read\n", num_edges);
442 /* For every block in the file,
443 - if every exit/entrance edge has a known count, then set the block count
444 - if the block count is known, and every exit/entrance edge but one has
445 a known execution count, then set the count of the remaining edge
447 As edge counts are set, decrement the succ/pred count, but don't delete
448 the edge, that way we can easily tell when all edges are known, or only
449 one edge is unknown. */
451 /* The order that the basic blocks are iterated through is important.
452 Since the code that finds spanning trees starts with block 0, low numbered
453 edges are put on the spanning tree in preference to high numbered edges.
454 Hence, most instrumented edges are at the end. Graph solving works much
455 faster if we propagate numbers from the end to the start.
457 This takes an average of slightly more than 3 passes. */
465 for (i = n_basic_blocks + 1; i >= 0; i--)
467 basic_block bb = GCOV_INDEX_TO_BB (i);
468 struct bb_info *bi = BB_INFO (bb);
469 if (! bi->count_valid)
471 if (bi->succ_count == 0)
476 for (e = bb->succ; e; e = e->succ_next)
482 else if (bi->pred_count == 0)
487 for (e = bb->pred; e; e = e->pred_next)
496 if (bi->succ_count == 1)
501 /* One of the counts will be invalid, but it is zero,
502 so adding it in also doesn't hurt. */
503 for (e = bb->succ; e; e = e->succ_next)
506 /* Seedgeh for the invalid edge, and set its count. */
507 for (e = bb->succ; e; e = e->succ_next)
508 if (! EDGE_INFO (e)->count_valid && ! EDGE_INFO (e)->ignore)
511 /* Calculate count for remaining edge by conservation. */
512 total = bb->count - total;
516 EDGE_INFO (e)->count_valid = 1;
520 BB_INFO (e->dest)->pred_count--;
523 if (bi->pred_count == 1)
528 /* One of the counts will be invalid, but it is zero,
529 so adding it in also doesn't hurt. */
530 for (e = bb->pred; e; e = e->pred_next)
533 /* Seedgeh for the invalid edge, and set its count. */
534 for (e = bb->pred; e; e = e->pred_next)
535 if (! EDGE_INFO (e)->count_valid && ! EDGE_INFO (e)->ignore)
538 /* Calculate count for remaining edge by conservation. */
539 total = bb->count - total + e->count;
543 EDGE_INFO (e)->count_valid = 1;
547 BB_INFO (e->src)->succ_count--;
554 dump_flow_info (rtl_dump_file);
556 total_num_passes += passes;
558 fprintf (rtl_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 (i = 0; i < n_basic_blocks; i++)
564 basic_block bb = BASIC_BLOCK (i);
565 if (BB_INFO (bb)->succ_count || BB_INFO (bb)->pred_count)
569 /* For every edge, calculate its branch probability and add a reg_note
570 to the branch insn to indicate this. */
572 for (i = 0; i < 20; i++)
574 num_never_executed = 0;
577 for (i = 0; i <= n_basic_blocks + 1; i++)
579 basic_block bb = GCOV_INDEX_TO_BB (i);
587 for (e = bb->succ; e; e = e->succ_next)
589 e->probability = (e->count * REG_BR_PROB_BASE + total / 2) / total;
590 if (e->probability < 0 || e->probability > REG_BR_PROB_BASE)
592 error ("corrupted profile info: prob for %d-%d thought to be %d",
593 e->src->index, e->dest->index, e->probability);
594 e->probability = REG_BR_PROB_BASE / 2;
598 && any_condjump_p (bb->end)
599 && bb->succ->succ_next)
605 /* Find the branch edge. It is possible that we do have fake
607 for (e = bb->succ; e->flags & (EDGE_FAKE | EDGE_FALLTHRU);
609 continue; /* Loop body has been intentionally left blank. */
611 prob = e->probability;
612 index = prob * 20 / REG_BR_PROB_BASE;
616 hist_br_prob[index]++;
618 note = find_reg_note (bb->end, REG_BR_PROB, 0);
619 /* There may be already note put by some other pass, such
620 as builtin_expect expander. */
622 XEXP (note, 0) = GEN_INT (prob);
625 = gen_rtx_EXPR_LIST (REG_BR_PROB, GEN_INT (prob),
626 REG_NOTES (bb->end));
630 /* Otherwise distribute the probabilities evenly so we get sane sum.
631 Use simple heuristics that if there are normal edges, give all abnormals
632 frequency of 0, otherwise distribute the frequency over abnormals
633 (this is the case of noreturn calls). */
636 for (e = bb->succ; e; e = e->succ_next)
637 if (!(e->flags & (EDGE_COMPLEX | EDGE_FAKE)))
641 for (e = bb->succ; e; e = e->succ_next)
642 if (!(e->flags & (EDGE_COMPLEX | EDGE_FAKE)))
643 e->probability = REG_BR_PROB_BASE / total;
649 for (e = bb->succ; e; e = e->succ_next)
651 for (e = bb->succ; e; e = e->succ_next)
652 e->probability = REG_BR_PROB_BASE / total;
655 && any_condjump_p (bb->end)
656 && bb->succ->succ_next)
657 num_branches++, num_never_executed;
663 fprintf (rtl_dump_file, "%d branches\n", num_branches);
664 fprintf (rtl_dump_file, "%d branches never executed\n",
667 for (i = 0; i < 10; i++)
668 fprintf (rtl_dump_file, "%d%% branches in range %d-%d%%\n",
669 (hist_br_prob[i] + hist_br_prob[19-i]) * 100 / num_branches,
672 total_num_branches += num_branches;
673 total_num_never_executed += num_never_executed;
674 for (i = 0; i < 20; i++)
675 total_hist_br_prob[i] += hist_br_prob[i];
677 fputc ('\n', rtl_dump_file);
678 fputc ('\n', rtl_dump_file);
681 free_aux_for_blocks ();
686 /* Compute checksum for the current function. */
688 #define CHSUM_HASH 500000003
689 #define CHSUM_SHIFT 2
698 for (i = 0; i < n_basic_blocks ; i++)
700 basic_block bb = BASIC_BLOCK (i);
703 for (e = bb->succ; e; e = e->succ_next)
705 chsum = ((chsum << CHSUM_SHIFT) + (BB_TO_GCOV_INDEX (e->dest) + 1)) % CHSUM_HASH;
708 chsum = (chsum << CHSUM_SHIFT) % CHSUM_HASH;
714 /* Instrument and/or analyze program behavior based on program flow graph.
715 In either case, this function builds a flow graph for the function being
716 compiled. The flow graph is stored in BB_GRAPH.
718 When FLAG_PROFILE_ARCS is nonzero, this function instruments the edges in
719 the flow graph that are needed to reconstruct the dynamic behavior of the
722 When FLAG_BRANCH_PROBABILITIES is nonzero, this function reads auxiliary
723 information from a data file containing edge count information from previous
724 executions of the function being compiled. In this case, the flow graph is
725 annotated with actual execution counts, which are later propagated into the
726 rtl for optimization purposes.
728 Main entry point of this file. */
734 int num_edges, ignored_edges;
735 struct edge_list *el;
737 profile_info.current_function_cfg_checksum = compute_checksum ();
740 fprintf (rtl_dump_file, "CFG checksum is %ld\n",
741 profile_info.current_function_cfg_checksum);
743 /* Start of a function. */
744 if (flag_test_coverage)
745 output_gcov_string (current_function_name, (long) -2);
747 total_num_times_called++;
749 flow_call_edges_add (NULL);
750 add_noreturn_fake_exit_edges ();
752 /* We can't handle cyclic regions constructed using abnormal edges.
753 To avoid these we replace every source of abnormal edge by a fake
754 edge from entry node and every destination by fake edge to exit.
755 This keeps graph acyclic and our calculation exact for all normal
756 edges except for exit and entrance ones.
758 We also add fake exit edges for each call and asm statement in the
759 basic, since it may not return. */
761 for (i = 0; i < n_basic_blocks ; i++)
763 int need_exit_edge = 0, need_entry_edge = 0;
764 int have_exit_edge = 0, have_entry_edge = 0;
765 basic_block bb = BASIC_BLOCK (i);
769 /* Add fake edges from entry block to the call insns that may return
770 twice. The CFG is not quite correct then, as call insn plays more
771 role of CODE_LABEL, but for our purposes, everything should be OK,
772 as we never insert code to the beggining of basic block. */
773 for (insn = bb->head; insn != NEXT_INSN (bb->end);
774 insn = NEXT_INSN (insn))
776 if (GET_CODE (insn) == CALL_INSN
777 && find_reg_note (insn, REG_SETJMP, NULL))
779 if (GET_CODE (bb->head) == CODE_LABEL
780 || insn != NEXT_INSN (bb->head))
782 e = split_block (bb, PREV_INSN (insn));
783 make_edge (ENTRY_BLOCK_PTR, e->dest, EDGE_FAKE);
788 /* We should not get abort here, as call to setjmp should not
789 be the very first instruction of function. */
792 make_edge (ENTRY_BLOCK_PTR, bb, EDGE_FAKE);
797 for (e = bb->succ; e; e = e->succ_next)
799 if ((e->flags & (EDGE_ABNORMAL | EDGE_ABNORMAL_CALL))
800 && e->dest != EXIT_BLOCK_PTR)
802 if (e->dest == EXIT_BLOCK_PTR)
805 for (e = bb->pred; e; e = e->pred_next)
807 if ((e->flags & (EDGE_ABNORMAL | EDGE_ABNORMAL_CALL))
808 && e->src != ENTRY_BLOCK_PTR)
810 if (e->src == ENTRY_BLOCK_PTR)
814 if (need_exit_edge && !have_exit_edge)
817 fprintf (rtl_dump_file, "Adding fake exit edge to bb %i\n",
819 make_edge (bb, EXIT_BLOCK_PTR, EDGE_FAKE);
821 if (need_entry_edge && !have_entry_edge)
824 fprintf (rtl_dump_file, "Adding fake entry edge to bb %i\n",
826 make_edge (ENTRY_BLOCK_PTR, bb, EDGE_FAKE);
830 el = create_edge_list ();
831 num_edges = NUM_EDGES (el);
832 alloc_aux_for_edges (sizeof (struct edge_info));
835 for (i = 0 ; i < num_edges ; i++)
837 edge e = INDEX_EDGE (el, i);
840 /* Mark edges we've replaced by fake edges above as ignored. */
841 if ((e->flags & (EDGE_ABNORMAL | EDGE_ABNORMAL_CALL))
842 && e->src != ENTRY_BLOCK_PTR && e->dest != EXIT_BLOCK_PTR)
844 EDGE_INFO (e)->ignore = 1;
849 #ifdef ENABLE_CHECKING
853 /* Output line number information about each basic block for
855 if (flag_test_coverage)
858 for (i = 0 ; i < n_basic_blocks; i++)
860 basic_block bb = BASIC_BLOCK (i);
862 static int ignore_next_note = 0;
864 /* We are looking for line number notes. Search backward before
865 basic block to find correct ones. */
866 insn = prev_nonnote_insn (insn);
870 insn = NEXT_INSN (insn);
872 /* Output a zero to the .bb file to indicate that a new
873 block list is starting. */
874 __write_long (0, bb_file, 4);
876 while (insn != bb->end)
878 if (GET_CODE (insn) == NOTE)
880 /* Must ignore the line number notes that immediately
881 follow the end of an inline function to avoid counting
882 it twice. There is a note before the call, and one
884 if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_REPEATED_LINE_NUMBER)
885 ignore_next_note = 1;
886 else if (NOTE_LINE_NUMBER (insn) > 0)
888 if (ignore_next_note)
889 ignore_next_note = 0;
892 /* If this is a new source file, then output the
893 file's name to the .bb file. */
894 if (! last_bb_file_name
895 || strcmp (NOTE_SOURCE_FILE (insn),
898 if (last_bb_file_name)
899 free (last_bb_file_name);
901 = xstrdup (NOTE_SOURCE_FILE (insn));
902 output_gcov_string (NOTE_SOURCE_FILE (insn),
905 /* Output the line number to the .bb file. Must be
906 done after the output_bb_profile_data() call, and
907 after the file name is written, to ensure that it
908 is correctly handled by gcov. */
909 __write_long (NOTE_LINE_NUMBER (insn), bb_file, 4);
913 insn = NEXT_INSN (insn);
916 __write_long (0, bb_file, 4);
919 /* Create spanning tree from basic block graph, mark each edge that is
920 on the spanning tree. We insert as many abnormal and critical edges
921 as possible to minimize number of edge splits necessary. */
923 find_spanning_tree (el);
925 /* Fake edges that are not on the tree will not be instrumented, so
926 mark them ignored. */
927 for (i = 0; i < num_edges; i++)
929 edge e = INDEX_EDGE (el, i);
930 struct edge_info *inf = EDGE_INFO (e);
931 if ((e->flags & EDGE_FAKE) && !inf->ignore && !inf->on_tree)
938 total_num_blocks += n_basic_blocks + 2;
940 fprintf (rtl_dump_file, "%d basic blocks\n", n_basic_blocks);
942 total_num_edges += num_edges;
944 fprintf (rtl_dump_file, "%d edges\n", num_edges);
946 total_num_edges_ignored += ignored_edges;
948 fprintf (rtl_dump_file, "%d ignored edges\n", ignored_edges);
950 /* Create a .bbg file from which gcov can reconstruct the basic block
951 graph. First output the number of basic blocks, and then for every
952 edge output the source and target basic block numbers.
953 NOTE: The format of this file must be compatible with gcov. */
955 if (flag_test_coverage)
959 __write_gcov_string (current_function_name,
960 strlen (current_function_name), bbg_file, -1);
962 /* write checksum. */
963 __write_long (profile_info.current_function_cfg_checksum, bbg_file, 4);
965 /* The plus 2 stands for entry and exit block. */
966 __write_long (n_basic_blocks + 2, bbg_file, 4);
967 __write_long (num_edges - ignored_edges + 1, bbg_file, 4);
969 for (i = 0; i < n_basic_blocks + 1; i++)
971 basic_block bb = GCOV_INDEX_TO_BB (i);
975 for (e = bb->succ; e; e = e->succ_next)
976 if (!EDGE_INFO (e)->ignore)
978 __write_long (count, bbg_file, 4);
980 for (e = bb->succ; e; e = e->succ_next)
982 struct edge_info *i = EDGE_INFO (e);
988 if (e->flags & EDGE_FAKE)
990 if (e->flags & EDGE_FALLTHRU)
993 __write_long (BB_TO_GCOV_INDEX (e->dest), bbg_file, 4);
994 __write_long (flag_bits, bbg_file, 4);
998 /* Emit fake loopback edge for EXIT block to maintain compatibility with
1000 __write_long (1, bbg_file, 4);
1001 __write_long (0, bbg_file, 4);
1002 __write_long (0x1, bbg_file, 4);
1004 /* Emit a -1 to separate the list of all edges from the list of
1005 loop back edges that follows. */
1006 __write_long (-1, bbg_file, 4);
1009 if (flag_branch_probabilities)
1010 compute_branch_probabilities ();
1012 /* For each edge not on the spanning tree, add counting code as rtl. */
1014 if (profile_arc_flag)
1016 instrument_edges (el);
1017 allocate_reg_info (max_reg_num (), FALSE, FALSE);
1020 remove_fake_edges ();
1021 /* Re-merge split basic blocks and the mess introduced by
1022 insert_insn_on_edge. */
1023 cleanup_cfg (profile_arc_flag ? CLEANUP_EXPENSIVE : 0);
1025 dump_flow_info (rtl_dump_file);
1027 free_aux_for_edges ();
1028 free_edge_list (el);
1031 /* Union find algorithm implementation for the basic blocks using
1038 basic_block group = bb, bb1;
1040 while ((basic_block) group->aux != group)
1041 group = (basic_block) group->aux;
1043 /* Compress path. */
1044 while ((basic_block) bb->aux != group)
1046 bb1 = (basic_block) bb->aux;
1047 bb->aux = (void *) group;
1054 union_groups (bb1, bb2)
1055 basic_block bb1, bb2;
1057 basic_block bb1g = find_group (bb1);
1058 basic_block bb2g = find_group (bb2);
1060 /* ??? I don't have a place for the rank field. OK. Lets go w/o it,
1061 this code is unlikely going to be performance problem anyway. */
1068 /* This function searches all of the edges in the program flow graph, and puts
1069 as many bad edges as possible onto the spanning tree. Bad edges include
1070 abnormals edges, which can't be instrumented at the moment. Since it is
1071 possible for fake edges to form an cycle, we will have to develop some
1072 better way in the future. Also put critical edges to the tree, since they
1073 are more expensive to instrument. */
1076 find_spanning_tree (el)
1077 struct edge_list *el;
1080 int num_edges = NUM_EDGES (el);
1082 /* We use aux field for standard union-find algorithm. */
1083 EXIT_BLOCK_PTR->aux = EXIT_BLOCK_PTR;
1084 ENTRY_BLOCK_PTR->aux = ENTRY_BLOCK_PTR;
1085 for (i = 0; i < n_basic_blocks; i++)
1086 BASIC_BLOCK (i)->aux = BASIC_BLOCK (i);
1088 /* Add fake edge exit to entry we can't instrument. */
1089 union_groups (EXIT_BLOCK_PTR, ENTRY_BLOCK_PTR);
1091 /* First add all abnormal edges to the tree unless they form an cycle. Also
1092 add all edges to EXIT_BLOCK_PTR to avoid inserting profiling code behind
1093 setting return value from function. */
1094 for (i = 0; i < num_edges; i++)
1096 edge e = INDEX_EDGE (el, i);
1097 if (((e->flags & (EDGE_ABNORMAL | EDGE_ABNORMAL_CALL | EDGE_FAKE))
1098 || e->dest == EXIT_BLOCK_PTR
1100 && !EDGE_INFO (e)->ignore
1101 && (find_group (e->src) != find_group (e->dest)))
1104 fprintf (rtl_dump_file, "Abnormal edge %d to %d put to tree\n",
1105 e->src->index, e->dest->index);
1106 EDGE_INFO (e)->on_tree = 1;
1107 union_groups (e->src, e->dest);
1111 /* Now insert all critical edges to the tree unless they form an cycle. */
1112 for (i = 0; i < num_edges; i++)
1114 edge e = INDEX_EDGE (el, i);
1115 if ((EDGE_CRITICAL_P (e))
1116 && !EDGE_INFO (e)->ignore
1117 && (find_group (e->src) != find_group (e->dest)))
1120 fprintf (rtl_dump_file, "Critical edge %d to %d put to tree\n",
1121 e->src->index, e->dest->index);
1122 EDGE_INFO (e)->on_tree = 1;
1123 union_groups (e->src, e->dest);
1127 /* And now the rest. */
1128 for (i = 0; i < num_edges; i++)
1130 edge e = INDEX_EDGE (el, i);
1131 if (find_group (e->src) != find_group (e->dest)
1132 && !EDGE_INFO (e)->ignore)
1135 fprintf (rtl_dump_file, "Normal edge %d to %d put to tree\n",
1136 e->src->index, e->dest->index);
1137 EDGE_INFO (e)->on_tree = 1;
1138 union_groups (e->src, e->dest);
1142 EXIT_BLOCK_PTR->aux = NULL;
1143 ENTRY_BLOCK_PTR->aux = NULL;
1144 for (i = 0; i < n_basic_blocks; i++)
1145 BASIC_BLOCK (i)->aux = NULL;
1148 /* Perform file-level initialization for branch-prob processing. */
1151 init_branch_prob (filename)
1152 const char *filename;
1157 if (flag_test_coverage)
1159 int len = strlen (filename);
1160 char *data_file, *bbg_file_name;
1162 /* Open an output file for the basic block/line number map. */
1163 data_file = (char *) alloca (len + 4);
1164 strcpy (data_file, filename);
1165 strip_off_ending (data_file, len);
1166 strcat (data_file, ".bb");
1167 if ((bb_file = fopen (data_file, "wb")) == 0)
1168 fatal_io_error ("can't open %s", data_file);
1170 /* Open an output file for the program flow graph. */
1171 bbg_file_name = (char *) alloca (len + 5);
1172 strcpy (bbg_file_name, filename);
1173 strip_off_ending (bbg_file_name, len);
1174 strcat (bbg_file_name, ".bbg");
1175 if ((bbg_file = fopen (bbg_file_name, "wb")) == 0)
1176 fatal_io_error ("can't open %s", bbg_file_name);
1178 /* Initialize to zero, to ensure that the first file name will be
1179 written to the .bb file. */
1180 last_bb_file_name = 0;
1183 if (flag_branch_probabilities)
1187 len = strlen (filename);
1188 da_file_name = (char *) alloca (len + 4);
1189 strcpy (da_file_name, filename);
1190 strip_off_ending (da_file_name, len);
1191 strcat (da_file_name, ".da");
1192 if ((da_file = fopen (da_file_name, "rb")) == 0)
1193 warning ("file %s not found, execution counts assumed to be zero",
1197 if (profile_arc_flag)
1198 init_edge_profiler ();
1200 total_num_blocks = 0;
1201 total_num_edges = 0;
1202 total_num_edges_ignored = 0;
1203 total_num_edges_instrumented = 0;
1204 total_num_blocks_created = 0;
1205 total_num_passes = 0;
1206 total_num_times_called = 0;
1207 total_num_branches = 0;
1208 total_num_never_executed = 0;
1209 for (i = 0; i < 20; i++)
1210 total_hist_br_prob[i] = 0;
1213 /* Performs file-level cleanup after branch-prob processing
1219 if (flag_test_coverage)
1225 if (flag_branch_probabilities && da_file)
1230 fprintf (rtl_dump_file, "\n");
1231 fprintf (rtl_dump_file, "Total number of blocks: %d\n",
1233 fprintf (rtl_dump_file, "Total number of edges: %d\n", total_num_edges);
1234 fprintf (rtl_dump_file, "Total number of ignored edges: %d\n",
1235 total_num_edges_ignored);
1236 fprintf (rtl_dump_file, "Total number of instrumented edges: %d\n",
1237 total_num_edges_instrumented);
1238 fprintf (rtl_dump_file, "Total number of blocks created: %d\n",
1239 total_num_blocks_created);
1240 fprintf (rtl_dump_file, "Total number of graph solution passes: %d\n",
1242 if (total_num_times_called != 0)
1243 fprintf (rtl_dump_file, "Average number of graph solution passes: %d\n",
1244 (total_num_passes + (total_num_times_called >> 1))
1245 / total_num_times_called);
1246 fprintf (rtl_dump_file, "Total number of branches: %d\n",
1247 total_num_branches);
1248 fprintf (rtl_dump_file, "Total number of branches never executed: %d\n",
1249 total_num_never_executed);
1250 if (total_num_branches)
1254 for (i = 0; i < 10; i++)
1255 fprintf (rtl_dump_file, "%d%% branches in range %d-%d%%\n",
1256 (total_hist_br_prob[i] + total_hist_br_prob[19-i]) * 100
1257 / total_num_branches, 5*i, 5*i+5);
1262 /* The label used by the edge profiling code. */
1264 static rtx profiler_label;
1266 /* Initialize the profiler_label. */
1269 init_edge_profiler ()
1271 /* Generate and save a copy of this so it can be shared. */
1273 ASM_GENERATE_INTERNAL_LABEL (buf, "LPBX", 2);
1274 profiler_label = gen_rtx_SYMBOL_REF (Pmode, ggc_strdup (buf));
1275 ggc_add_rtx_root (&profiler_label, 1);
1278 /* Output instructions as RTL to increment the edge execution count. */
1281 gen_edge_profiler (edgeno)
1284 enum machine_mode mode = mode_for_size (GCOV_TYPE_SIZE, MODE_INT, 0);
1290 tmp = force_reg (Pmode, profiler_label);
1291 tmp = plus_constant (tmp, GCOV_TYPE_SIZE / BITS_PER_UNIT * edgeno);
1292 mem_ref = validize_mem (gen_rtx_MEM (mode, tmp));
1294 tmp = expand_simple_binop (mode, PLUS, mem_ref, const1_rtx,
1295 mem_ref, 0, OPTAB_WIDEN);
1297 set_mem_alias_set (mem_ref, new_alias_set ());
1300 emit_move_insn (copy_rtx (mem_ref), tmp);
1302 sequence = gen_sequence ();
1307 /* Output code for a constructor that will invoke __bb_init_func, if
1308 this has not already been done. */
1311 output_func_start_profiler ()
1313 tree fnname, fndecl;
1316 const char *cfnname;
1318 enum machine_mode mode = mode_for_size (GCOV_TYPE_SIZE, MODE_INT, 0);
1319 int save_flag_inline_functions = flag_inline_functions;
1321 /* It's either already been output, or we don't need it because we're
1322 not doing profile-edges. */
1323 if (! need_func_profiler)
1326 need_func_profiler = 0;
1328 /* Synthesize a constructor function to invoke __bb_init_func with a
1329 pointer to this object file's profile block. */
1331 /* Try and make a unique name given the "file function name".
1333 And no, I don't like this either. */
1335 fnname = get_file_function_name ('I');
1336 cfnname = IDENTIFIER_POINTER (fnname);
1337 name = concat (cfnname, "GCOV", NULL);
1338 fnname = get_identifier (name);
1341 fndecl = build_decl (FUNCTION_DECL, fnname,
1342 build_function_type (void_type_node, NULL_TREE));
1343 DECL_EXTERNAL (fndecl) = 0;
1345 /* It can be a static function as long as collect2 does not have
1346 to scan the object file to find its ctor/dtor routine. */
1347 TREE_PUBLIC (fndecl) = ! targetm.have_ctors_dtors;
1349 TREE_USED (fndecl) = 1;
1351 DECL_RESULT (fndecl) = build_decl (RESULT_DECL, NULL_TREE, void_type_node);
1353 fndecl = (*lang_hooks.decls.pushdecl) (fndecl);
1354 rest_of_decl_compilation (fndecl, 0, 1, 0);
1355 announce_function (fndecl);
1356 current_function_decl = fndecl;
1357 DECL_INITIAL (fndecl) = error_mark_node;
1358 make_decl_rtl (fndecl, NULL);
1359 init_function_start (fndecl, input_filename, lineno);
1360 (*lang_hooks.decls.pushlevel) (0);
1361 expand_function_start (fndecl, 0);
1362 cfun->arc_profile = 0;
1364 /* Actually generate the code to call __bb_init_func. */
1365 ASM_GENERATE_INTERNAL_LABEL (buf, "LPBX", 0);
1366 table_address = force_reg (Pmode,
1367 gen_rtx_SYMBOL_REF (Pmode, ggc_strdup (buf)));
1368 emit_library_call (gen_rtx_SYMBOL_REF (Pmode, "__bb_init_func"), LCT_NORMAL,
1369 mode, 1, table_address, Pmode);
1371 expand_function_end (input_filename, lineno, 0);
1372 (*lang_hooks.decls.poplevel) (1, 0, 1);
1374 /* Since fndecl isn't in the list of globals, it would never be emitted
1375 when it's considered to be 'safe' for inlining, so turn off
1376 flag_inline_functions. */
1377 flag_inline_functions = 0;
1379 rest_of_compilation (fndecl);
1381 /* Reset flag_inline_functions to its original value. */
1382 flag_inline_functions = save_flag_inline_functions;
1385 fflush (asm_out_file);
1386 current_function_decl = NULL_TREE;
1388 if (targetm.have_ctors_dtors)
1389 (* targetm.asm_out.constructor) (XEXP (DECL_RTL (fndecl), 0),
1390 DEFAULT_INIT_PRIORITY);