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 /* 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;
141 int num_instr_edges = 0;
142 int num_edges = NUM_EDGES (el);
143 remove_fake_edges ();
145 for (i = 0; i < n_basic_blocks + 2; i++)
147 basic_block bb = GCOV_INDEX_TO_BB (i);
151 struct edge_info *inf = EDGE_INFO (e);
152 if (!inf->ignore && !inf->on_tree)
154 if (e->flags & EDGE_ABNORMAL)
157 fprintf (rtl_dump_file, "Edge %d to %d instrumented%s\n",
158 e->src->index, e->dest->index,
159 EDGE_CRITICAL_P (e) ? " (and split)" : "");
160 need_func_profiler = 1;
161 insert_insn_on_edge (
162 gen_edge_profiler (total_num_edges_instrumented
163 + num_instr_edges++), e);
169 profile_info.count_edges_instrumented_now = num_instr_edges;
170 total_num_edges_instrumented += num_instr_edges;
171 profile_info.count_instrumented_edges = total_num_edges_instrumented;
173 total_num_blocks_created += num_edges;
175 fprintf (rtl_dump_file, "%d edges instrumented\n", num_instr_edges);
177 commit_edge_insertions_watch_calls ();
180 /* Output STRING to bb_file, surrounded by DELIMITER. */
183 output_gcov_string (string, delimiter)
189 /* Write a delimiter to indicate that a file name follows. */
190 __write_long (delimiter, bb_file, 4);
192 /* Write the string. */
193 temp = strlen (string) + 1;
194 fwrite (string, temp, 1, bb_file);
196 /* Append a few zeros, to align the output to a 4 byte boundary. */
202 c[0] = c[1] = c[2] = c[3] = 0;
203 fwrite (c, sizeof (char), 4 - temp, bb_file);
206 /* Store another delimiter in the .bb file, just to make it easy to find
207 the end of the file name. */
208 __write_long (delimiter, bb_file, 4);
212 /* Computes hybrid profile for all matching entries in da_file.
213 Sets max_counter_in_program as a side effect. */
223 char *function_name_buffer;
224 int function_name_buffer_len;
225 gcov_type max_counter_in_run;
227 profile_info.max_counter_in_program = 0;
228 profile_info.count_profiles_merged = 0;
230 /* No .da file, no execution counts. */
234 /* Count the edges to be (possibly) instrumented. */
236 for (i = 0; i < n_basic_blocks + 2; i++)
238 basic_block bb = GCOV_INDEX_TO_BB (i);
240 for (e = bb->succ; e; e = e->succ_next)
241 if (!EDGE_INFO (e)->ignore && !EDGE_INFO (e)->on_tree)
247 /* now read and combine all matching profiles. */
249 profile = xmalloc (sizeof (gcov_type) * num_edges);
251 function_name_buffer_len = strlen (current_function_name) + 1;
252 function_name_buffer = xmalloc (function_name_buffer_len + 1);
254 for (i = 0; i < num_edges; i++)
259 long magic, extra_bytes;
263 if (__read_long (&magic, da_file, 4) != 0)
272 if (__read_long (&func_count, da_file, 4) != 0)
278 if (__read_long (&extra_bytes, da_file, 4) != 0)
284 fseek (da_file, 4 + 8, SEEK_CUR);
286 /* read the maximal counter. */
287 __read_gcov_type (&max_counter_in_run, da_file, 8);
289 /* skip the rest of "statistics" emited by __bb_exit_func. */
290 fseek (da_file, extra_bytes - (4 + 8 + 8), SEEK_CUR);
292 for (i = 0; i < func_count; i++)
298 if (__read_gcov_string
299 (function_name_buffer, function_name_buffer_len, da_file,
306 if (__read_long (&chksum, da_file, 4) != 0)
312 if (__read_long (&arc_count, da_file, 4) != 0)
318 if (strcmp (function_name_buffer, current_function_name) != 0)
321 if (fseek (da_file, arc_count * 8, SEEK_CUR) < 0)
327 else if (arc_count != num_edges
328 || chksum != profile_info.current_function_cfg_checksum)
329 okay = 0, mismatch = 1;
334 profile_info.max_counter_in_program += max_counter_in_run;
335 profile_info.count_profiles_merged++;
337 for (j = 0; j < arc_count; j++)
338 if (__read_gcov_type (&tmp, da_file, 8) != 0)
355 free (function_name_buffer);
361 ("Profile does not match flowgraph of function %s (out of date?)",
362 current_function_name);
364 error (".da file corrupted");
370 fprintf(rtl_dump_file, "Merged %i profiles with maximal count %i.\n",
371 profile_info.count_profiles_merged,
372 (int)profile_info.max_counter_in_program);
379 /* Compute the branch probabilities for the various branches.
380 Annotate them accordingly. */
383 compute_branch_probabilities ()
389 int hist_br_prob[20];
390 int num_never_executed;
392 gcov_type *exec_counts = get_exec_counts ();
393 int exec_counts_pos = 0;
395 /* Attach extra info block to each bb. */
397 alloc_aux_for_blocks (sizeof (struct bb_info));
398 for (i = 0; i < n_basic_blocks + 2; i++)
400 basic_block bb = GCOV_INDEX_TO_BB (i);
403 for (e = bb->succ; e; e = e->succ_next)
404 if (!EDGE_INFO (e)->ignore)
405 BB_INFO (bb)->succ_count++;
406 for (e = bb->pred; e; e = e->pred_next)
407 if (!EDGE_INFO (e)->ignore)
408 BB_INFO (bb)->pred_count++;
411 /* Avoid predicting entry on exit nodes. */
412 BB_INFO (EXIT_BLOCK_PTR)->succ_count = 2;
413 BB_INFO (ENTRY_BLOCK_PTR)->pred_count = 2;
415 /* For each edge not on the spanning tree, set its execution count from
418 /* The first count in the .da file is the number of times that the function
419 was entered. This is the exec_count for block zero. */
421 for (i = 0; i < n_basic_blocks + 2; i++)
423 basic_block bb = GCOV_INDEX_TO_BB (i);
425 for (e = bb->succ; e; e = e->succ_next)
426 if (!EDGE_INFO (e)->ignore && !EDGE_INFO (e)->on_tree)
431 e->count = exec_counts[exec_counts_pos++];
436 EDGE_INFO (e)->count_valid = 1;
437 BB_INFO (bb)->succ_count--;
438 BB_INFO (e->dest)->pred_count--;
441 fprintf (rtl_dump_file, "\nRead edge from %i to %i, count:",
442 bb->index, e->dest->index);
443 fprintf (rtl_dump_file, HOST_WIDEST_INT_PRINT_DEC,
444 (HOST_WIDEST_INT) e->count);
450 fprintf (rtl_dump_file, "\n%d edge counts read\n", num_edges);
452 /* For every block in the file,
453 - if every exit/entrance edge has a known count, then set the block count
454 - if the block count is known, and every exit/entrance edge but one has
455 a known execution count, then set the count of the remaining edge
457 As edge counts are set, decrement the succ/pred count, but don't delete
458 the edge, that way we can easily tell when all edges are known, or only
459 one edge is unknown. */
461 /* The order that the basic blocks are iterated through is important.
462 Since the code that finds spanning trees starts with block 0, low numbered
463 edges are put on the spanning tree in preference to high numbered edges.
464 Hence, most instrumented edges are at the end. Graph solving works much
465 faster if we propagate numbers from the end to the start.
467 This takes an average of slightly more than 3 passes. */
475 for (i = n_basic_blocks + 1; i >= 0; i--)
477 basic_block bb = GCOV_INDEX_TO_BB (i);
478 struct bb_info *bi = BB_INFO (bb);
479 if (! bi->count_valid)
481 if (bi->succ_count == 0)
486 for (e = bb->succ; e; e = e->succ_next)
492 else if (bi->pred_count == 0)
497 for (e = bb->pred; e; e = e->pred_next)
506 if (bi->succ_count == 1)
511 /* One of the counts will be invalid, but it is zero,
512 so adding it in also doesn't hurt. */
513 for (e = bb->succ; e; e = e->succ_next)
516 /* Seedgeh for the invalid edge, and set its count. */
517 for (e = bb->succ; e; e = e->succ_next)
518 if (! EDGE_INFO (e)->count_valid && ! EDGE_INFO (e)->ignore)
521 /* Calculate count for remaining edge by conservation. */
522 total = bb->count - total;
526 EDGE_INFO (e)->count_valid = 1;
530 BB_INFO (e->dest)->pred_count--;
533 if (bi->pred_count == 1)
538 /* One of the counts will be invalid, but it is zero,
539 so adding it in also doesn't hurt. */
540 for (e = bb->pred; e; e = e->pred_next)
543 /* Seedgeh for the invalid edge, and set its count. */
544 for (e = bb->pred; e; e = e->pred_next)
545 if (! EDGE_INFO (e)->count_valid && ! EDGE_INFO (e)->ignore)
548 /* Calculate count for remaining edge by conservation. */
549 total = bb->count - total + e->count;
553 EDGE_INFO (e)->count_valid = 1;
557 BB_INFO (e->src)->succ_count--;
564 dump_flow_info (rtl_dump_file);
566 total_num_passes += passes;
568 fprintf (rtl_dump_file, "Graph solving took %d passes.\n\n", passes);
570 /* If the graph has been correctly solved, every block will have a
571 succ and pred count of zero. */
572 for (i = 0; i < n_basic_blocks; i++)
574 basic_block bb = BASIC_BLOCK (i);
575 if (BB_INFO (bb)->succ_count || BB_INFO (bb)->pred_count)
579 /* For every edge, calculate its branch probability and add a reg_note
580 to the branch insn to indicate this. */
582 for (i = 0; i < 20; i++)
584 num_never_executed = 0;
587 for (i = 0; i <= n_basic_blocks + 1; i++)
589 basic_block bb = GCOV_INDEX_TO_BB (i);
597 for (e = bb->succ; e; e = e->succ_next)
599 e->probability = (e->count * REG_BR_PROB_BASE + total / 2) / total;
600 if (e->probability < 0 || e->probability > REG_BR_PROB_BASE)
602 error ("corrupted profile info: prob for %d-%d thought to be %d",
603 e->src->index, e->dest->index, e->probability);
604 e->probability = REG_BR_PROB_BASE / 2;
608 && any_condjump_p (bb->end)
609 && bb->succ->succ_next)
615 /* Find the branch edge. It is possible that we do have fake
617 for (e = bb->succ; e->flags & (EDGE_FAKE | EDGE_FALLTHRU);
619 continue; /* Loop body has been intentionally left blank. */
621 prob = e->probability;
622 index = prob * 20 / REG_BR_PROB_BASE;
626 hist_br_prob[index]++;
628 note = find_reg_note (bb->end, REG_BR_PROB, 0);
629 /* There may be already note put by some other pass, such
630 as builtin_expect expander. */
632 XEXP (note, 0) = GEN_INT (prob);
635 = gen_rtx_EXPR_LIST (REG_BR_PROB, GEN_INT (prob),
636 REG_NOTES (bb->end));
640 /* Otherwise distribute the probabilities evenly so we get sane sum.
641 Use simple heuristics that if there are normal edges, give all abnormals
642 frequency of 0, otherwise distribute the frequency over abnormals
643 (this is the case of noreturn calls). */
646 for (e = bb->succ; e; e = e->succ_next)
647 if (!(e->flags & (EDGE_COMPLEX | EDGE_FAKE)))
651 for (e = bb->succ; e; e = e->succ_next)
652 if (!(e->flags & (EDGE_COMPLEX | EDGE_FAKE)))
653 e->probability = REG_BR_PROB_BASE / total;
659 for (e = bb->succ; e; e = e->succ_next)
661 for (e = bb->succ; e; e = e->succ_next)
662 e->probability = REG_BR_PROB_BASE / total;
665 && any_condjump_p (bb->end)
666 && bb->succ->succ_next)
667 num_branches++, num_never_executed;
673 fprintf (rtl_dump_file, "%d branches\n", num_branches);
674 fprintf (rtl_dump_file, "%d branches never executed\n",
677 for (i = 0; i < 10; i++)
678 fprintf (rtl_dump_file, "%d%% branches in range %d-%d%%\n",
679 (hist_br_prob[i] + hist_br_prob[19-i]) * 100 / num_branches,
682 total_num_branches += num_branches;
683 total_num_never_executed += num_never_executed;
684 for (i = 0; i < 20; i++)
685 total_hist_br_prob[i] += hist_br_prob[i];
687 fputc ('\n', rtl_dump_file);
688 fputc ('\n', rtl_dump_file);
691 free_aux_for_blocks ();
696 /* Compute checksum for the current function. */
698 #define CHSUM_HASH 500000003
699 #define CHSUM_SHIFT 2
708 for (i = 0; i < n_basic_blocks ; i++)
710 basic_block bb = BASIC_BLOCK (i);
713 for (e = bb->succ; e; e = e->succ_next)
715 chsum = ((chsum << CHSUM_SHIFT) + (BB_TO_GCOV_INDEX (e->dest) + 1)) % CHSUM_HASH;
718 chsum = (chsum << CHSUM_SHIFT) % CHSUM_HASH;
724 /* Instrument and/or analyze program behavior based on program flow graph.
725 In either case, this function builds a flow graph for the function being
726 compiled. The flow graph is stored in BB_GRAPH.
728 When FLAG_PROFILE_ARCS is nonzero, this function instruments the edges in
729 the flow graph that are needed to reconstruct the dynamic behavior of the
732 When FLAG_BRANCH_PROBABILITIES is nonzero, this function reads auxiliary
733 information from a data file containing edge count information from previous
734 executions of the function being compiled. In this case, the flow graph is
735 annotated with actual execution counts, which are later propagated into the
736 rtl for optimization purposes.
738 Main entry point of this file. */
744 int num_edges, ignored_edges;
745 struct edge_list *el;
747 profile_info.current_function_cfg_checksum = compute_checksum ();
750 fprintf (rtl_dump_file, "CFG checksum is %ld\n",
751 profile_info.current_function_cfg_checksum);
753 /* Start of a function. */
754 if (flag_test_coverage)
755 output_gcov_string (current_function_name, (long) -2);
757 total_num_times_called++;
759 flow_call_edges_add (NULL);
760 add_noreturn_fake_exit_edges ();
762 /* We can't handle cyclic regions constructed using abnormal edges.
763 To avoid these we replace every source of abnormal edge by a fake
764 edge from entry node and every destination by fake edge to exit.
765 This keeps graph acyclic and our calculation exact for all normal
766 edges except for exit and entrance ones.
768 We also add fake exit edges for each call and asm statement in the
769 basic, since it may not return. */
771 for (i = 0; i < n_basic_blocks ; i++)
773 int need_exit_edge = 0, need_entry_edge = 0;
774 int have_exit_edge = 0, have_entry_edge = 0;
775 basic_block bb = BASIC_BLOCK (i);
779 /* Add fake edges from entry block to the call insns that may return
780 twice. The CFG is not quite correct then, as call insn plays more
781 role of CODE_LABEL, but for our purposes, everything should be OK,
782 as we never insert code to the beggining of basic block. */
783 for (insn = bb->head; insn != NEXT_INSN (bb->end);
784 insn = NEXT_INSN (insn))
786 if (GET_CODE (insn) == CALL_INSN
787 && find_reg_note (insn, REG_SETJMP, NULL))
789 if (GET_CODE (bb->head) == CODE_LABEL
790 || insn != NEXT_INSN (bb->head))
792 e = split_block (bb, PREV_INSN (insn));
793 make_edge (ENTRY_BLOCK_PTR, e->dest, EDGE_FAKE);
798 /* We should not get abort here, as call to setjmp should not
799 be the very first instruction of function. */
802 make_edge (ENTRY_BLOCK_PTR, bb, EDGE_FAKE);
807 for (e = bb->succ; e; e = e->succ_next)
809 if ((e->flags & (EDGE_ABNORMAL | EDGE_ABNORMAL_CALL))
810 && e->dest != EXIT_BLOCK_PTR)
812 if (e->dest == EXIT_BLOCK_PTR)
815 for (e = bb->pred; e; e = e->pred_next)
817 if ((e->flags & (EDGE_ABNORMAL | EDGE_ABNORMAL_CALL))
818 && e->src != ENTRY_BLOCK_PTR)
820 if (e->src == ENTRY_BLOCK_PTR)
824 if (need_exit_edge && !have_exit_edge)
827 fprintf (rtl_dump_file, "Adding fake exit edge to bb %i\n",
829 make_edge (bb, EXIT_BLOCK_PTR, EDGE_FAKE);
831 if (need_entry_edge && !have_entry_edge)
834 fprintf (rtl_dump_file, "Adding fake entry edge to bb %i\n",
836 make_edge (ENTRY_BLOCK_PTR, bb, EDGE_FAKE);
840 el = create_edge_list ();
841 num_edges = NUM_EDGES (el);
842 alloc_aux_for_edges (sizeof (struct edge_info));
845 for (i = 0 ; i < num_edges ; i++)
847 edge e = INDEX_EDGE (el, i);
850 /* Mark edges we've replaced by fake edges above as ignored. */
851 if ((e->flags & (EDGE_ABNORMAL | EDGE_ABNORMAL_CALL))
852 && e->src != ENTRY_BLOCK_PTR && e->dest != EXIT_BLOCK_PTR)
854 EDGE_INFO (e)->ignore = 1;
859 #ifdef ENABLE_CHECKING
863 /* Output line number information about each basic block for
865 if (flag_test_coverage)
868 for (i = 0 ; i < n_basic_blocks; i++)
870 basic_block bb = BASIC_BLOCK (i);
872 static int ignore_next_note = 0;
874 /* We are looking for line number notes. Search backward before
875 basic block to find correct ones. */
876 insn = prev_nonnote_insn (insn);
880 insn = NEXT_INSN (insn);
882 /* Output a zero to the .bb file to indicate that a new
883 block list is starting. */
884 __write_long (0, bb_file, 4);
886 while (insn != bb->end)
888 if (GET_CODE (insn) == NOTE)
890 /* Must ignore the line number notes that immediately
891 follow the end of an inline function to avoid counting
892 it twice. There is a note before the call, and one
894 if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_REPEATED_LINE_NUMBER)
895 ignore_next_note = 1;
896 else if (NOTE_LINE_NUMBER (insn) > 0)
898 if (ignore_next_note)
899 ignore_next_note = 0;
902 /* If this is a new source file, then output the
903 file's name to the .bb file. */
904 if (! last_bb_file_name
905 || strcmp (NOTE_SOURCE_FILE (insn),
908 if (last_bb_file_name)
909 free (last_bb_file_name);
911 = xstrdup (NOTE_SOURCE_FILE (insn));
912 output_gcov_string (NOTE_SOURCE_FILE (insn),
915 /* Output the line number to the .bb file. Must be
916 done after the output_bb_profile_data() call, and
917 after the file name is written, to ensure that it
918 is correctly handled by gcov. */
919 __write_long (NOTE_LINE_NUMBER (insn), bb_file, 4);
923 insn = NEXT_INSN (insn);
926 __write_long (0, bb_file, 4);
929 /* Create spanning tree from basic block graph, mark each edge that is
930 on the spanning tree. We insert as many abnormal and critical edges
931 as possible to minimize number of edge splits necessary. */
933 find_spanning_tree (el);
935 /* Fake edges that are not on the tree will not be instrumented, so
936 mark them ignored. */
937 for (i = 0; i < num_edges; i++)
939 edge e = INDEX_EDGE (el, i);
940 struct edge_info *inf = EDGE_INFO (e);
941 if ((e->flags & EDGE_FAKE) && !inf->ignore && !inf->on_tree)
948 total_num_blocks += n_basic_blocks + 2;
950 fprintf (rtl_dump_file, "%d basic blocks\n", n_basic_blocks);
952 total_num_edges += num_edges;
954 fprintf (rtl_dump_file, "%d edges\n", num_edges);
956 total_num_edges_ignored += ignored_edges;
958 fprintf (rtl_dump_file, "%d ignored edges\n", ignored_edges);
960 /* Create a .bbg file from which gcov can reconstruct the basic block
961 graph. First output the number of basic blocks, and then for every
962 edge output the source and target basic block numbers.
963 NOTE: The format of this file must be compatible with gcov. */
965 if (flag_test_coverage)
969 __write_gcov_string (current_function_name,
970 strlen (current_function_name), bbg_file, -1);
972 /* write checksum. */
973 __write_long (profile_info.current_function_cfg_checksum, bbg_file, 4);
975 /* The plus 2 stands for entry and exit block. */
976 __write_long (n_basic_blocks + 2, bbg_file, 4);
977 __write_long (num_edges - ignored_edges + 1, bbg_file, 4);
979 for (i = 0; i < n_basic_blocks + 1; i++)
981 basic_block bb = GCOV_INDEX_TO_BB (i);
985 for (e = bb->succ; e; e = e->succ_next)
986 if (!EDGE_INFO (e)->ignore)
988 __write_long (count, bbg_file, 4);
990 for (e = bb->succ; e; e = e->succ_next)
992 struct edge_info *i = EDGE_INFO (e);
998 if (e->flags & EDGE_FAKE)
1000 if (e->flags & EDGE_FALLTHRU)
1003 __write_long (BB_TO_GCOV_INDEX (e->dest), bbg_file, 4);
1004 __write_long (flag_bits, bbg_file, 4);
1008 /* Emit fake loopback edge for EXIT block to maintain compatibility with
1010 __write_long (1, bbg_file, 4);
1011 __write_long (0, bbg_file, 4);
1012 __write_long (0x1, bbg_file, 4);
1014 /* Emit a -1 to separate the list of all edges from the list of
1015 loop back edges that follows. */
1016 __write_long (-1, bbg_file, 4);
1019 if (flag_branch_probabilities)
1020 compute_branch_probabilities ();
1022 /* For each edge not on the spanning tree, add counting code as rtl. */
1024 if (profile_arc_flag)
1026 instrument_edges (el);
1027 allocate_reg_info (max_reg_num (), FALSE, FALSE);
1030 remove_fake_edges ();
1031 /* Re-merge split basic blocks and the mess introduced by
1032 insert_insn_on_edge. */
1033 cleanup_cfg (profile_arc_flag ? CLEANUP_EXPENSIVE : 0);
1035 dump_flow_info (rtl_dump_file);
1037 free_aux_for_edges ();
1038 free_edge_list (el);
1041 /* Union find algorithm implementation for the basic blocks using
1048 basic_block group = bb, bb1;
1050 while ((basic_block) group->aux != group)
1051 group = (basic_block) group->aux;
1053 /* Compress path. */
1054 while ((basic_block) bb->aux != group)
1056 bb1 = (basic_block) bb->aux;
1057 bb->aux = (void *) group;
1064 union_groups (bb1, bb2)
1065 basic_block bb1, bb2;
1067 basic_block bb1g = find_group (bb1);
1068 basic_block bb2g = find_group (bb2);
1070 /* ??? I don't have a place for the rank field. OK. Lets go w/o it,
1071 this code is unlikely going to be performance problem anyway. */
1078 /* This function searches all of the edges in the program flow graph, and puts
1079 as many bad edges as possible onto the spanning tree. Bad edges include
1080 abnormals edges, which can't be instrumented at the moment. Since it is
1081 possible for fake edges to form an cycle, we will have to develop some
1082 better way in the future. Also put critical edges to the tree, since they
1083 are more expensive to instrument. */
1086 find_spanning_tree (el)
1087 struct edge_list *el;
1090 int num_edges = NUM_EDGES (el);
1092 /* We use aux field for standard union-find algorithm. */
1093 EXIT_BLOCK_PTR->aux = EXIT_BLOCK_PTR;
1094 ENTRY_BLOCK_PTR->aux = ENTRY_BLOCK_PTR;
1095 for (i = 0; i < n_basic_blocks; i++)
1096 BASIC_BLOCK (i)->aux = BASIC_BLOCK (i);
1098 /* Add fake edge exit to entry we can't instrument. */
1099 union_groups (EXIT_BLOCK_PTR, ENTRY_BLOCK_PTR);
1101 /* First add all abnormal edges to the tree unless they form an cycle. Also
1102 add all edges to EXIT_BLOCK_PTR to avoid inserting profiling code behind
1103 setting return value from function. */
1104 for (i = 0; i < num_edges; i++)
1106 edge e = INDEX_EDGE (el, i);
1107 if (((e->flags & (EDGE_ABNORMAL | EDGE_ABNORMAL_CALL | EDGE_FAKE))
1108 || e->dest == EXIT_BLOCK_PTR
1110 && !EDGE_INFO (e)->ignore
1111 && (find_group (e->src) != find_group (e->dest)))
1114 fprintf (rtl_dump_file, "Abnormal edge %d to %d put to tree\n",
1115 e->src->index, e->dest->index);
1116 EDGE_INFO (e)->on_tree = 1;
1117 union_groups (e->src, e->dest);
1121 /* Now insert all critical edges to the tree unless they form an cycle. */
1122 for (i = 0; i < num_edges; i++)
1124 edge e = INDEX_EDGE (el, i);
1125 if ((EDGE_CRITICAL_P (e))
1126 && !EDGE_INFO (e)->ignore
1127 && (find_group (e->src) != find_group (e->dest)))
1130 fprintf (rtl_dump_file, "Critical edge %d to %d put to tree\n",
1131 e->src->index, e->dest->index);
1132 EDGE_INFO (e)->on_tree = 1;
1133 union_groups (e->src, e->dest);
1137 /* And now the rest. */
1138 for (i = 0; i < num_edges; i++)
1140 edge e = INDEX_EDGE (el, i);
1141 if (find_group (e->src) != find_group (e->dest)
1142 && !EDGE_INFO (e)->ignore)
1145 fprintf (rtl_dump_file, "Normal edge %d to %d put to tree\n",
1146 e->src->index, e->dest->index);
1147 EDGE_INFO (e)->on_tree = 1;
1148 union_groups (e->src, e->dest);
1152 EXIT_BLOCK_PTR->aux = NULL;
1153 ENTRY_BLOCK_PTR->aux = NULL;
1154 for (i = 0; i < n_basic_blocks; i++)
1155 BASIC_BLOCK (i)->aux = NULL;
1158 /* Perform file-level initialization for branch-prob processing. */
1161 init_branch_prob (filename)
1162 const char *filename;
1167 if (flag_test_coverage)
1169 int len = strlen (filename);
1170 char *data_file, *bbg_file_name;
1172 /* Open an output file for the basic block/line number map. */
1173 data_file = (char *) alloca (len + 4);
1174 strcpy (data_file, filename);
1175 strip_off_ending (data_file, len);
1176 strcat (data_file, ".bb");
1177 if ((bb_file = fopen (data_file, "wb")) == 0)
1178 fatal_io_error ("can't open %s", data_file);
1180 /* Open an output file for the program flow graph. */
1181 bbg_file_name = (char *) alloca (len + 5);
1182 strcpy (bbg_file_name, filename);
1183 strip_off_ending (bbg_file_name, len);
1184 strcat (bbg_file_name, ".bbg");
1185 if ((bbg_file = fopen (bbg_file_name, "wb")) == 0)
1186 fatal_io_error ("can't open %s", bbg_file_name);
1188 /* Initialize to zero, to ensure that the first file name will be
1189 written to the .bb file. */
1190 last_bb_file_name = 0;
1193 if (flag_branch_probabilities)
1197 len = strlen (filename);
1198 da_file_name = (char *) alloca (len + 4);
1199 strcpy (da_file_name, filename);
1200 strip_off_ending (da_file_name, len);
1201 strcat (da_file_name, ".da");
1202 if ((da_file = fopen (da_file_name, "rb")) == 0)
1203 warning ("file %s not found, execution counts assumed to be zero",
1207 if (profile_arc_flag)
1208 init_edge_profiler ();
1210 total_num_blocks = 0;
1211 total_num_edges = 0;
1212 total_num_edges_ignored = 0;
1213 total_num_edges_instrumented = 0;
1214 total_num_blocks_created = 0;
1215 total_num_passes = 0;
1216 total_num_times_called = 0;
1217 total_num_branches = 0;
1218 total_num_never_executed = 0;
1219 for (i = 0; i < 20; i++)
1220 total_hist_br_prob[i] = 0;
1223 /* Performs file-level cleanup after branch-prob processing
1229 if (flag_test_coverage)
1235 if (flag_branch_probabilities && da_file)
1240 fprintf (rtl_dump_file, "\n");
1241 fprintf (rtl_dump_file, "Total number of blocks: %d\n",
1243 fprintf (rtl_dump_file, "Total number of edges: %d\n", total_num_edges);
1244 fprintf (rtl_dump_file, "Total number of ignored edges: %d\n",
1245 total_num_edges_ignored);
1246 fprintf (rtl_dump_file, "Total number of instrumented edges: %d\n",
1247 total_num_edges_instrumented);
1248 fprintf (rtl_dump_file, "Total number of blocks created: %d\n",
1249 total_num_blocks_created);
1250 fprintf (rtl_dump_file, "Total number of graph solution passes: %d\n",
1252 if (total_num_times_called != 0)
1253 fprintf (rtl_dump_file, "Average number of graph solution passes: %d\n",
1254 (total_num_passes + (total_num_times_called >> 1))
1255 / total_num_times_called);
1256 fprintf (rtl_dump_file, "Total number of branches: %d\n",
1257 total_num_branches);
1258 fprintf (rtl_dump_file, "Total number of branches never executed: %d\n",
1259 total_num_never_executed);
1260 if (total_num_branches)
1264 for (i = 0; i < 10; i++)
1265 fprintf (rtl_dump_file, "%d%% branches in range %d-%d%%\n",
1266 (total_hist_br_prob[i] + total_hist_br_prob[19-i]) * 100
1267 / total_num_branches, 5*i, 5*i+5);
1272 /* The label used by the edge profiling code. */
1274 static rtx profiler_label;
1276 /* Initialize the profiler_label. */
1279 init_edge_profiler ()
1281 /* Generate and save a copy of this so it can be shared. */
1283 ASM_GENERATE_INTERNAL_LABEL (buf, "LPBX", 2);
1284 profiler_label = gen_rtx_SYMBOL_REF (Pmode, ggc_strdup (buf));
1285 ggc_add_rtx_root (&profiler_label, 1);
1288 /* Output instructions as RTL to increment the edge execution count. */
1291 gen_edge_profiler (edgeno)
1294 enum machine_mode mode = mode_for_size (GCOV_TYPE_SIZE, MODE_INT, 0);
1300 tmp = force_reg (Pmode, profiler_label);
1301 tmp = plus_constant (tmp, GCOV_TYPE_SIZE / BITS_PER_UNIT * edgeno);
1302 mem_ref = validize_mem (gen_rtx_MEM (mode, tmp));
1304 set_mem_alias_set (mem_ref, new_alias_set ());
1306 tmp = expand_simple_binop (mode, PLUS, mem_ref, const1_rtx,
1307 mem_ref, 0, OPTAB_WIDEN);
1310 emit_move_insn (copy_rtx (mem_ref), tmp);
1312 sequence = gen_sequence ();
1317 /* Output code for a constructor that will invoke __bb_init_func, if
1318 this has not already been done. */
1321 output_func_start_profiler ()
1323 tree fnname, fndecl;
1326 const char *cfnname;
1328 enum machine_mode mode = mode_for_size (GCOV_TYPE_SIZE, MODE_INT, 0);
1329 int save_flag_inline_functions = flag_inline_functions;
1331 /* It's either already been output, or we don't need it because we're
1332 not doing profile-edges. */
1333 if (! need_func_profiler)
1336 need_func_profiler = 0;
1338 /* Synthesize a constructor function to invoke __bb_init_func with a
1339 pointer to this object file's profile block. */
1341 /* Try and make a unique name given the "file function name".
1343 And no, I don't like this either. */
1345 fnname = get_file_function_name ('I');
1346 cfnname = IDENTIFIER_POINTER (fnname);
1347 name = concat (cfnname, "GCOV", NULL);
1348 fnname = get_identifier (name);
1351 fndecl = build_decl (FUNCTION_DECL, fnname,
1352 build_function_type (void_type_node, NULL_TREE));
1353 DECL_EXTERNAL (fndecl) = 0;
1355 /* It can be a static function as long as collect2 does not have
1356 to scan the object file to find its ctor/dtor routine. */
1357 TREE_PUBLIC (fndecl) = ! targetm.have_ctors_dtors;
1359 TREE_USED (fndecl) = 1;
1361 DECL_RESULT (fndecl) = build_decl (RESULT_DECL, NULL_TREE, void_type_node);
1363 fndecl = (*lang_hooks.decls.pushdecl) (fndecl);
1364 rest_of_decl_compilation (fndecl, 0, 1, 0);
1365 announce_function (fndecl);
1366 current_function_decl = fndecl;
1367 DECL_INITIAL (fndecl) = error_mark_node;
1368 make_decl_rtl (fndecl, NULL);
1369 init_function_start (fndecl, input_filename, lineno);
1370 (*lang_hooks.decls.pushlevel) (0);
1371 expand_function_start (fndecl, 0);
1372 cfun->arc_profile = 0;
1374 /* Actually generate the code to call __bb_init_func. */
1375 ASM_GENERATE_INTERNAL_LABEL (buf, "LPBX", 0);
1376 table_address = force_reg (Pmode,
1377 gen_rtx_SYMBOL_REF (Pmode, ggc_strdup (buf)));
1378 emit_library_call (gen_rtx_SYMBOL_REF (Pmode, "__bb_init_func"), LCT_NORMAL,
1379 mode, 1, table_address, Pmode);
1381 expand_function_end (input_filename, lineno, 0);
1382 (*lang_hooks.decls.poplevel) (1, 0, 1);
1384 /* Since fndecl isn't in the list of globals, it would never be emitted
1385 when it's considered to be 'safe' for inlining, so turn off
1386 flag_inline_functions. */
1387 flag_inline_functions = 0;
1389 rest_of_compilation (fndecl);
1391 /* Reset flag_inline_functions to its original value. */
1392 flag_inline_functions = save_flag_inline_functions;
1395 fflush (asm_out_file);
1396 current_function_decl = NULL_TREE;
1398 if (targetm.have_ctors_dtors)
1399 (* targetm.asm_out.constructor) (XEXP (DECL_RTL (fndecl), 0),
1400 DEFAULT_INIT_PRIORITY);