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) == last_basic_block + 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 ? last_basic_block + 1 : (bb)->index + 1))
82 /* Instantiate the profile info structure. */
84 struct profile_info profile_info;
86 /* Name and file pointer of the output file for the basic block graph. */
88 static FILE *bbg_file;
90 /* Name and file pointer of the input file for the arc count data. */
94 /* Pointer of the output file for the basic block/line number map. */
97 /* Last source file name written to bb_file. */
99 static char *last_bb_file_name;
101 /* Collect statistics on the performance of this pass for the entire source
104 static int total_num_blocks;
105 static int total_num_edges;
106 static int total_num_edges_ignored;
107 static int total_num_edges_instrumented;
108 static int total_num_blocks_created;
109 static int total_num_passes;
110 static int total_num_times_called;
111 static int total_hist_br_prob[20];
112 static int total_num_never_executed;
113 static int total_num_branches;
115 /* Forward declarations. */
116 static void find_spanning_tree PARAMS ((struct edge_list *));
117 static void init_edge_profiler PARAMS ((void));
118 static rtx gen_edge_profiler PARAMS ((int));
119 static void instrument_edges PARAMS ((struct edge_list *));
120 static void output_gcov_string PARAMS ((const char *, long));
121 static void compute_branch_probabilities PARAMS ((void));
122 static gcov_type * get_exec_counts PARAMS ((void));
123 static long compute_checksum PARAMS ((void));
124 static basic_block find_group PARAMS ((basic_block));
125 static void union_groups PARAMS ((basic_block, basic_block));
127 /* If non-zero, we need to output a constructor to set up the
128 per-object-file data. */
129 static int need_func_profiler = 0;
131 /* Add edge instrumentation code to the entire insn chain.
133 F is the first insn of the chain.
134 NUM_BLOCKS is the number of basic blocks found in F. */
137 instrument_edges (el)
138 struct edge_list *el;
140 int num_instr_edges = 0;
141 int num_edges = NUM_EDGES (el);
143 remove_fake_edges ();
145 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
150 struct edge_info *inf = EDGE_INFO (e);
151 if (!inf->ignore && !inf->on_tree)
153 if (e->flags & EDGE_ABNORMAL)
156 fprintf (rtl_dump_file, "Edge %d to %d instrumented%s\n",
157 e->src->index, e->dest->index,
158 EDGE_CRITICAL_P (e) ? " (and split)" : "");
159 need_func_profiler = 1;
160 insert_insn_on_edge (
161 gen_edge_profiler (total_num_edges_instrumented
162 + num_instr_edges++), e);
168 profile_info.count_edges_instrumented_now = num_instr_edges;
169 total_num_edges_instrumented += num_instr_edges;
170 profile_info.count_instrumented_edges = total_num_edges_instrumented;
172 total_num_blocks_created += num_edges;
174 fprintf (rtl_dump_file, "%d edges instrumented\n", num_instr_edges);
176 commit_edge_insertions_watch_calls ();
179 /* Output STRING to bb_file, surrounded by DELIMITER. */
182 output_gcov_string (string, delimiter)
188 /* Write a delimiter to indicate that a file name follows. */
189 __write_long (delimiter, bb_file, 4);
191 /* Write the string. */
192 temp = strlen (string) + 1;
193 fwrite (string, temp, 1, bb_file);
195 /* Append a few zeros, to align the output to a 4 byte boundary. */
201 c[0] = c[1] = c[2] = c[3] = 0;
202 fwrite (c, sizeof (char), 4 - temp, bb_file);
205 /* Store another delimiter in the .bb file, just to make it easy to find
206 the end of the file name. */
207 __write_long (delimiter, bb_file, 4);
211 /* Computes hybrid profile for all matching entries in da_file.
212 Sets max_counter_in_program as a side effect. */
222 char *function_name_buffer;
223 int function_name_buffer_len;
224 gcov_type max_counter_in_run;
226 profile_info.max_counter_in_program = 0;
227 profile_info.count_profiles_merged = 0;
229 /* No .da file, no execution counts. */
233 /* Count the edges to be (possibly) instrumented. */
235 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
238 for (e = bb->succ; e; e = e->succ_next)
239 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");
366 fprintf(rtl_dump_file, "Merged %i profiles with maximal count %i.\n",
367 profile_info.count_profiles_merged,
368 (int)profile_info.max_counter_in_program);
375 /* Compute the branch probabilities for the various branches.
376 Annotate them accordingly. */
379 compute_branch_probabilities ()
386 int hist_br_prob[20];
387 int num_never_executed;
389 gcov_type *exec_counts = get_exec_counts ();
390 int exec_counts_pos = 0;
392 /* Attach extra info block to each bb. */
394 alloc_aux_for_blocks (sizeof (struct bb_info));
395 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
399 for (e = bb->succ; e; e = e->succ_next)
400 if (!EDGE_INFO (e)->ignore)
401 BB_INFO (bb)->succ_count++;
402 for (e = bb->pred; e; e = e->pred_next)
403 if (!EDGE_INFO (e)->ignore)
404 BB_INFO (bb)->pred_count++;
407 /* Avoid predicting entry on exit nodes. */
408 BB_INFO (EXIT_BLOCK_PTR)->succ_count = 2;
409 BB_INFO (ENTRY_BLOCK_PTR)->pred_count = 2;
411 /* For each edge not on the spanning tree, set its execution count from
414 /* The first count in the .da file is the number of times that the function
415 was entered. This is the exec_count for block zero. */
417 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
420 for (e = bb->succ; e; e = e->succ_next)
421 if (!EDGE_INFO (e)->ignore && !EDGE_INFO (e)->on_tree)
426 e->count = exec_counts[exec_counts_pos++];
431 EDGE_INFO (e)->count_valid = 1;
432 BB_INFO (bb)->succ_count--;
433 BB_INFO (e->dest)->pred_count--;
436 fprintf (rtl_dump_file, "\nRead edge from %i to %i, count:",
437 bb->index, e->dest->index);
438 fprintf (rtl_dump_file, HOST_WIDEST_INT_PRINT_DEC,
439 (HOST_WIDEST_INT) e->count);
445 fprintf (rtl_dump_file, "\n%d edge counts read\n", num_edges);
447 /* For every block in the file,
448 - if every exit/entrance edge has a known count, then set the block count
449 - if the block count is known, and every exit/entrance edge but one has
450 a known execution count, then set the count of the remaining edge
452 As edge counts are set, decrement the succ/pred count, but don't delete
453 the edge, that way we can easily tell when all edges are known, or only
454 one edge is unknown. */
456 /* The order that the basic blocks are iterated through is important.
457 Since the code that finds spanning trees starts with block 0, low numbered
458 edges are put on the spanning tree in preference to high numbered edges.
459 Hence, most instrumented edges are at the end. Graph solving works much
460 faster if we propagate numbers from the end to the start.
462 This takes an average of slightly more than 3 passes. */
470 FOR_BB_BETWEEN (bb, EXIT_BLOCK_PTR, NULL, prev_bb)
472 struct bb_info *bi = BB_INFO (bb);
473 if (! bi->count_valid)
475 if (bi->succ_count == 0)
480 for (e = bb->succ; e; e = e->succ_next)
486 else if (bi->pred_count == 0)
491 for (e = bb->pred; e; e = e->pred_next)
500 if (bi->succ_count == 1)
505 /* One of the counts will be invalid, but it is zero,
506 so adding it in also doesn't hurt. */
507 for (e = bb->succ; e; e = e->succ_next)
510 /* Seedgeh for the invalid edge, and set its count. */
511 for (e = bb->succ; e; e = e->succ_next)
512 if (! EDGE_INFO (e)->count_valid && ! EDGE_INFO (e)->ignore)
515 /* Calculate count for remaining edge by conservation. */
516 total = bb->count - total;
520 EDGE_INFO (e)->count_valid = 1;
524 BB_INFO (e->dest)->pred_count--;
527 if (bi->pred_count == 1)
532 /* One of the counts will be invalid, but it is zero,
533 so adding it in also doesn't hurt. */
534 for (e = bb->pred; e; e = e->pred_next)
537 /* Seedgeh for the invalid edge, and set its count. */
538 for (e = bb->pred; e; e = e->pred_next)
539 if (! EDGE_INFO (e)->count_valid && ! EDGE_INFO (e)->ignore)
542 /* Calculate count for remaining edge by conservation. */
543 total = bb->count - total + e->count;
547 EDGE_INFO (e)->count_valid = 1;
551 BB_INFO (e->src)->succ_count--;
558 dump_flow_info (rtl_dump_file);
560 total_num_passes += passes;
562 fprintf (rtl_dump_file, "Graph solving took %d passes.\n\n", passes);
564 /* If the graph has been correctly solved, every block will have a
565 succ and pred count of zero. */
568 if (BB_INFO (bb)->succ_count || BB_INFO (bb)->pred_count)
572 /* For every edge, calculate its branch probability and add a reg_note
573 to the branch insn to indicate this. */
575 for (i = 0; i < 20; i++)
577 num_never_executed = 0;
580 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
589 for (e = bb->succ; e; e = e->succ_next)
591 e->probability = (e->count * REG_BR_PROB_BASE + total / 2) / total;
592 if (e->probability < 0 || e->probability > REG_BR_PROB_BASE)
594 error ("corrupted profile info: prob for %d-%d thought to be %d",
595 e->src->index, e->dest->index, e->probability);
596 e->probability = REG_BR_PROB_BASE / 2;
600 && any_condjump_p (bb->end)
601 && bb->succ->succ_next)
607 /* Find the branch edge. It is possible that we do have fake
609 for (e = bb->succ; e->flags & (EDGE_FAKE | EDGE_FALLTHRU);
611 continue; /* Loop body has been intentionally left blank. */
613 prob = e->probability;
614 index = prob * 20 / REG_BR_PROB_BASE;
618 hist_br_prob[index]++;
620 note = find_reg_note (bb->end, REG_BR_PROB, 0);
621 /* There may be already note put by some other pass, such
622 as builtin_expect expander. */
624 XEXP (note, 0) = GEN_INT (prob);
627 = gen_rtx_EXPR_LIST (REG_BR_PROB, GEN_INT (prob),
628 REG_NOTES (bb->end));
632 /* Otherwise distribute the probabilities evenly so we get sane sum.
633 Use simple heuristics that if there are normal edges, give all abnormals
634 frequency of 0, otherwise distribute the frequency over abnormals
635 (this is the case of noreturn calls). */
638 for (e = bb->succ; e; e = e->succ_next)
639 if (!(e->flags & (EDGE_COMPLEX | EDGE_FAKE)))
643 for (e = bb->succ; e; e = e->succ_next)
644 if (!(e->flags & (EDGE_COMPLEX | EDGE_FAKE)))
645 e->probability = REG_BR_PROB_BASE / total;
651 for (e = bb->succ; e; e = e->succ_next)
653 for (e = bb->succ; e; e = e->succ_next)
654 e->probability = REG_BR_PROB_BASE / total;
657 && any_condjump_p (bb->end)
658 && bb->succ->succ_next)
659 num_branches++, num_never_executed;
665 fprintf (rtl_dump_file, "%d branches\n", num_branches);
666 fprintf (rtl_dump_file, "%d branches never executed\n",
669 for (i = 0; i < 10; i++)
670 fprintf (rtl_dump_file, "%d%% branches in range %d-%d%%\n",
671 (hist_br_prob[i] + hist_br_prob[19-i]) * 100 / num_branches,
674 total_num_branches += num_branches;
675 total_num_never_executed += num_never_executed;
676 for (i = 0; i < 20; i++)
677 total_hist_br_prob[i] += hist_br_prob[i];
679 fputc ('\n', rtl_dump_file);
680 fputc ('\n', rtl_dump_file);
683 free_aux_for_blocks ();
688 /* Compute checksum for the current function. */
690 #define CHSUM_HASH 500000003
691 #define CHSUM_SHIFT 2
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. */
735 int num_edges, ignored_edges;
736 struct edge_list *el;
738 profile_info.current_function_cfg_checksum = compute_checksum ();
741 fprintf (rtl_dump_file, "CFG checksum is %ld\n",
742 profile_info.current_function_cfg_checksum);
744 /* Start of a function. */
745 if (flag_test_coverage)
746 output_gcov_string (current_function_name, (long) -2);
748 total_num_times_called++;
750 flow_call_edges_add (NULL);
751 add_noreturn_fake_exit_edges ();
753 /* We can't handle cyclic regions constructed using abnormal edges.
754 To avoid these we replace every source of abnormal edge by a fake
755 edge from entry node and every destination by fake edge to exit.
756 This keeps graph acyclic and our calculation exact for all normal
757 edges except for exit and entrance ones.
759 We also add fake exit edges for each call and asm statement in the
760 basic, since it may not return. */
764 int need_exit_edge = 0, need_entry_edge = 0;
765 int have_exit_edge = 0, have_entry_edge = 0;
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. */
790 if (bb == ENTRY_BLOCK_PTR)
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)
860 static int ignore_next_note = 0;
862 /* We are looking for line number notes. Search backward before
863 basic block to find correct ones. */
864 insn = prev_nonnote_insn (insn);
868 insn = NEXT_INSN (insn);
870 /* Output a zero to the .bb file to indicate that a new
871 block list is starting. */
872 __write_long (0, bb_file, 4);
874 while (insn != bb->end)
876 if (GET_CODE (insn) == NOTE)
878 /* Must ignore the line number notes that immediately
879 follow the end of an inline function to avoid counting
880 it twice. There is a note before the call, and one
882 if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_REPEATED_LINE_NUMBER)
883 ignore_next_note = 1;
884 else if (NOTE_LINE_NUMBER (insn) > 0)
886 if (ignore_next_note)
887 ignore_next_note = 0;
890 /* If this is a new source file, then output the
891 file's name to the .bb file. */
892 if (! last_bb_file_name
893 || strcmp (NOTE_SOURCE_FILE (insn),
896 if (last_bb_file_name)
897 free (last_bb_file_name);
899 = xstrdup (NOTE_SOURCE_FILE (insn));
900 output_gcov_string (NOTE_SOURCE_FILE (insn),
903 /* Output the line number to the .bb file. Must be
904 done after the output_bb_profile_data() call, and
905 after the file name is written, to ensure that it
906 is correctly handled by gcov. */
907 __write_long (NOTE_LINE_NUMBER (insn), bb_file, 4);
911 insn = NEXT_INSN (insn);
914 __write_long (0, bb_file, 4);
917 /* Create spanning tree from basic block graph, mark each edge that is
918 on the spanning tree. We insert as many abnormal and critical edges
919 as possible to minimize number of edge splits necessary. */
921 find_spanning_tree (el);
923 /* Fake edges that are not on the tree will not be instrumented, so
924 mark them ignored. */
925 for (i = 0; i < num_edges; i++)
927 edge e = INDEX_EDGE (el, i);
928 struct edge_info *inf = EDGE_INFO (e);
929 if ((e->flags & EDGE_FAKE) && !inf->ignore && !inf->on_tree)
936 total_num_blocks += n_basic_blocks + 2;
938 fprintf (rtl_dump_file, "%d basic blocks\n", n_basic_blocks);
940 total_num_edges += num_edges;
942 fprintf (rtl_dump_file, "%d edges\n", num_edges);
944 total_num_edges_ignored += ignored_edges;
946 fprintf (rtl_dump_file, "%d ignored edges\n", ignored_edges);
948 /* Create a .bbg file from which gcov can reconstruct the basic block
949 graph. First output the number of basic blocks, and then for every
950 edge output the source and target basic block numbers.
951 NOTE: The format of this file must be compatible with gcov. */
953 if (flag_test_coverage)
957 __write_gcov_string (current_function_name,
958 strlen (current_function_name), bbg_file, -1);
960 /* write checksum. */
961 __write_long (profile_info.current_function_cfg_checksum, bbg_file, 4);
963 /* The plus 2 stands for entry and exit block. */
964 __write_long (n_basic_blocks + 2, bbg_file, 4);
965 __write_long (num_edges - ignored_edges + 1, bbg_file, 4);
967 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
972 for (e = bb->succ; e; e = e->succ_next)
973 if (!EDGE_INFO (e)->ignore)
975 __write_long (count, bbg_file, 4);
977 for (e = bb->succ; e; e = e->succ_next)
979 struct edge_info *i = EDGE_INFO (e);
985 if (e->flags & EDGE_FAKE)
987 if (e->flags & EDGE_FALLTHRU)
990 __write_long (BB_TO_GCOV_INDEX (e->dest), bbg_file, 4);
991 __write_long (flag_bits, bbg_file, 4);
995 /* Emit fake loopback edge for EXIT block to maintain compatibility with
997 __write_long (1, bbg_file, 4);
998 __write_long (0, bbg_file, 4);
999 __write_long (0x1, bbg_file, 4);
1001 /* Emit a -1 to separate the list of all edges from the list of
1002 loop back edges that follows. */
1003 __write_long (-1, bbg_file, 4);
1006 if (flag_branch_probabilities)
1007 compute_branch_probabilities ();
1009 /* For each edge not on the spanning tree, add counting code as rtl. */
1011 if (profile_arc_flag)
1013 instrument_edges (el);
1014 allocate_reg_info (max_reg_num (), FALSE, FALSE);
1017 remove_fake_edges ();
1018 /* Re-merge split basic blocks and the mess introduced by
1019 insert_insn_on_edge. */
1020 cleanup_cfg (profile_arc_flag ? CLEANUP_EXPENSIVE : 0);
1022 dump_flow_info (rtl_dump_file);
1024 free_aux_for_edges ();
1025 free_edge_list (el);
1028 /* Union find algorithm implementation for the basic blocks using
1035 basic_block group = bb, bb1;
1037 while ((basic_block) group->aux != group)
1038 group = (basic_block) group->aux;
1040 /* Compress path. */
1041 while ((basic_block) bb->aux != group)
1043 bb1 = (basic_block) bb->aux;
1044 bb->aux = (void *) group;
1051 union_groups (bb1, bb2)
1052 basic_block bb1, bb2;
1054 basic_block bb1g = find_group (bb1);
1055 basic_block bb2g = find_group (bb2);
1057 /* ??? I don't have a place for the rank field. OK. Lets go w/o it,
1058 this code is unlikely going to be performance problem anyway. */
1065 /* This function searches all of the edges in the program flow graph, and puts
1066 as many bad edges as possible onto the spanning tree. Bad edges include
1067 abnormals edges, which can't be instrumented at the moment. Since it is
1068 possible for fake edges to form an cycle, we will have to develop some
1069 better way in the future. Also put critical edges to the tree, since they
1070 are more expensive to instrument. */
1073 find_spanning_tree (el)
1074 struct edge_list *el;
1077 int num_edges = NUM_EDGES (el);
1080 /* We use aux field for standard union-find algorithm. */
1081 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
1084 /* Add fake edge exit to entry we can't instrument. */
1085 union_groups (EXIT_BLOCK_PTR, ENTRY_BLOCK_PTR);
1087 /* First add all abnormal edges to the tree unless they form an cycle. Also
1088 add all edges to EXIT_BLOCK_PTR to avoid inserting profiling code behind
1089 setting return value from function. */
1090 for (i = 0; i < num_edges; i++)
1092 edge e = INDEX_EDGE (el, i);
1093 if (((e->flags & (EDGE_ABNORMAL | EDGE_ABNORMAL_CALL | EDGE_FAKE))
1094 || e->dest == EXIT_BLOCK_PTR
1096 && !EDGE_INFO (e)->ignore
1097 && (find_group (e->src) != find_group (e->dest)))
1100 fprintf (rtl_dump_file, "Abnormal edge %d to %d put to tree\n",
1101 e->src->index, e->dest->index);
1102 EDGE_INFO (e)->on_tree = 1;
1103 union_groups (e->src, e->dest);
1107 /* Now insert all critical edges to the tree unless they form an cycle. */
1108 for (i = 0; i < num_edges; i++)
1110 edge e = INDEX_EDGE (el, i);
1111 if ((EDGE_CRITICAL_P (e))
1112 && !EDGE_INFO (e)->ignore
1113 && (find_group (e->src) != find_group (e->dest)))
1116 fprintf (rtl_dump_file, "Critical edge %d to %d put to tree\n",
1117 e->src->index, e->dest->index);
1118 EDGE_INFO (e)->on_tree = 1;
1119 union_groups (e->src, e->dest);
1123 /* And now the rest. */
1124 for (i = 0; i < num_edges; i++)
1126 edge e = INDEX_EDGE (el, i);
1127 if (find_group (e->src) != find_group (e->dest)
1128 && !EDGE_INFO (e)->ignore)
1131 fprintf (rtl_dump_file, "Normal edge %d to %d put to tree\n",
1132 e->src->index, e->dest->index);
1133 EDGE_INFO (e)->on_tree = 1;
1134 union_groups (e->src, e->dest);
1138 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
1142 /* Perform file-level initialization for branch-prob processing. */
1145 init_branch_prob (filename)
1146 const char *filename;
1151 if (flag_test_coverage)
1153 int len = strlen (filename);
1154 char *data_file, *bbg_file_name;
1156 /* Open an output file for the basic block/line number map. */
1157 data_file = (char *) alloca (len + 4);
1158 strcpy (data_file, filename);
1159 strip_off_ending (data_file, len);
1160 strcat (data_file, ".bb");
1161 if ((bb_file = fopen (data_file, "wb")) == 0)
1162 fatal_io_error ("can't open %s", data_file);
1164 /* Open an output file for the program flow graph. */
1165 bbg_file_name = (char *) alloca (len + 5);
1166 strcpy (bbg_file_name, filename);
1167 strip_off_ending (bbg_file_name, len);
1168 strcat (bbg_file_name, ".bbg");
1169 if ((bbg_file = fopen (bbg_file_name, "wb")) == 0)
1170 fatal_io_error ("can't open %s", bbg_file_name);
1172 /* Initialize to zero, to ensure that the first file name will be
1173 written to the .bb file. */
1174 last_bb_file_name = 0;
1177 if (flag_branch_probabilities)
1181 len = strlen (filename);
1182 da_file_name = (char *) alloca (len + 4);
1183 strcpy (da_file_name, filename);
1184 strip_off_ending (da_file_name, len);
1185 strcat (da_file_name, ".da");
1186 if ((da_file = fopen (da_file_name, "rb")) == 0)
1187 warning ("file %s not found, execution counts assumed to be zero",
1191 if (profile_arc_flag)
1192 init_edge_profiler ();
1194 total_num_blocks = 0;
1195 total_num_edges = 0;
1196 total_num_edges_ignored = 0;
1197 total_num_edges_instrumented = 0;
1198 total_num_blocks_created = 0;
1199 total_num_passes = 0;
1200 total_num_times_called = 0;
1201 total_num_branches = 0;
1202 total_num_never_executed = 0;
1203 for (i = 0; i < 20; i++)
1204 total_hist_br_prob[i] = 0;
1207 /* Performs file-level cleanup after branch-prob processing
1213 if (flag_test_coverage)
1219 if (flag_branch_probabilities && da_file)
1224 fprintf (rtl_dump_file, "\n");
1225 fprintf (rtl_dump_file, "Total number of blocks: %d\n",
1227 fprintf (rtl_dump_file, "Total number of edges: %d\n", total_num_edges);
1228 fprintf (rtl_dump_file, "Total number of ignored edges: %d\n",
1229 total_num_edges_ignored);
1230 fprintf (rtl_dump_file, "Total number of instrumented edges: %d\n",
1231 total_num_edges_instrumented);
1232 fprintf (rtl_dump_file, "Total number of blocks created: %d\n",
1233 total_num_blocks_created);
1234 fprintf (rtl_dump_file, "Total number of graph solution passes: %d\n",
1236 if (total_num_times_called != 0)
1237 fprintf (rtl_dump_file, "Average number of graph solution passes: %d\n",
1238 (total_num_passes + (total_num_times_called >> 1))
1239 / total_num_times_called);
1240 fprintf (rtl_dump_file, "Total number of branches: %d\n",
1241 total_num_branches);
1242 fprintf (rtl_dump_file, "Total number of branches never executed: %d\n",
1243 total_num_never_executed);
1244 if (total_num_branches)
1248 for (i = 0; i < 10; i++)
1249 fprintf (rtl_dump_file, "%d%% branches in range %d-%d%%\n",
1250 (total_hist_br_prob[i] + total_hist_br_prob[19-i]) * 100
1251 / total_num_branches, 5*i, 5*i+5);
1256 /* The label used by the edge profiling code. */
1258 static rtx profiler_label;
1260 /* Initialize the profiler_label. */
1263 init_edge_profiler ()
1265 /* Generate and save a copy of this so it can be shared. */
1267 ASM_GENERATE_INTERNAL_LABEL (buf, "LPBX", 2);
1268 profiler_label = gen_rtx_SYMBOL_REF (Pmode, ggc_strdup (buf));
1269 ggc_add_rtx_root (&profiler_label, 1);
1272 /* Output instructions as RTL to increment the edge execution count. */
1275 gen_edge_profiler (edgeno)
1278 enum machine_mode mode = mode_for_size (GCOV_TYPE_SIZE, MODE_INT, 0);
1284 tmp = force_reg (Pmode, profiler_label);
1285 tmp = plus_constant (tmp, GCOV_TYPE_SIZE / BITS_PER_UNIT * edgeno);
1286 mem_ref = validize_mem (gen_rtx_MEM (mode, tmp));
1288 set_mem_alias_set (mem_ref, new_alias_set ());
1290 tmp = expand_simple_binop (mode, PLUS, mem_ref, const1_rtx,
1291 mem_ref, 0, OPTAB_WIDEN);
1294 emit_move_insn (copy_rtx (mem_ref), tmp);
1296 sequence = gen_sequence ();
1301 /* Output code for a constructor that will invoke __bb_init_func, if
1302 this has not already been done. */
1305 output_func_start_profiler ()
1307 tree fnname, fndecl;
1310 const char *cfnname;
1312 enum machine_mode mode = mode_for_size (GCOV_TYPE_SIZE, MODE_INT, 0);
1313 int save_flag_inline_functions = flag_inline_functions;
1315 /* It's either already been output, or we don't need it because we're
1316 not doing profile-edges. */
1317 if (! need_func_profiler)
1320 need_func_profiler = 0;
1322 /* Synthesize a constructor function to invoke __bb_init_func with a
1323 pointer to this object file's profile block. */
1325 /* Try and make a unique name given the "file function name".
1327 And no, I don't like this either. */
1329 fnname = get_file_function_name ('I');
1330 cfnname = IDENTIFIER_POINTER (fnname);
1331 name = concat (cfnname, "GCOV", NULL);
1332 fnname = get_identifier (name);
1335 fndecl = build_decl (FUNCTION_DECL, fnname,
1336 build_function_type (void_type_node, NULL_TREE));
1337 DECL_EXTERNAL (fndecl) = 0;
1339 /* It can be a static function as long as collect2 does not have
1340 to scan the object file to find its ctor/dtor routine. */
1341 TREE_PUBLIC (fndecl) = ! targetm.have_ctors_dtors;
1343 TREE_USED (fndecl) = 1;
1345 DECL_RESULT (fndecl) = build_decl (RESULT_DECL, NULL_TREE, void_type_node);
1347 fndecl = (*lang_hooks.decls.pushdecl) (fndecl);
1348 rest_of_decl_compilation (fndecl, 0, 1, 0);
1349 announce_function (fndecl);
1350 current_function_decl = fndecl;
1351 DECL_INITIAL (fndecl) = error_mark_node;
1352 make_decl_rtl (fndecl, NULL);
1353 init_function_start (fndecl, input_filename, lineno);
1354 (*lang_hooks.decls.pushlevel) (0);
1355 expand_function_start (fndecl, 0);
1356 cfun->arc_profile = 0;
1358 /* Actually generate the code to call __bb_init_func. */
1359 ASM_GENERATE_INTERNAL_LABEL (buf, "LPBX", 0);
1360 table_address = force_reg (Pmode,
1361 gen_rtx_SYMBOL_REF (Pmode, ggc_strdup (buf)));
1362 emit_library_call (gen_rtx_SYMBOL_REF (Pmode, "__bb_init_func"), LCT_NORMAL,
1363 mode, 1, table_address, Pmode);
1365 expand_function_end (input_filename, lineno, 0);
1366 (*lang_hooks.decls.poplevel) (1, 0, 1);
1368 /* Since fndecl isn't in the list of globals, it would never be emitted
1369 when it's considered to be 'safe' for inlining, so turn off
1370 flag_inline_functions. */
1371 flag_inline_functions = 0;
1373 rest_of_compilation (fndecl);
1375 /* Reset flag_inline_functions to its original value. */
1376 flag_inline_functions = save_flag_inline_functions;
1379 fflush (asm_out_file);
1380 current_function_decl = NULL_TREE;
1382 if (targetm.have_ctors_dtors)
1383 (* targetm.asm_out.constructor) (XEXP (DECL_RTL (fndecl), 0),
1384 DEFAULT_INIT_PRIORITY);