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");
373 /* Compute the branch probabilities for the various branches.
374 Annotate them accordingly. */
377 compute_branch_probabilities ()
383 int hist_br_prob[20];
384 int num_never_executed;
386 gcov_type *exec_counts = get_exec_counts ();
387 int exec_counts_pos = 0;
389 /* Attach extra info block to each bb. */
391 alloc_aux_for_blocks (sizeof (struct bb_info));
392 for (i = 0; i < n_basic_blocks + 2; i++)
394 basic_block bb = GCOV_INDEX_TO_BB (i);
397 for (e = bb->succ; e; e = e->succ_next)
398 if (!EDGE_INFO (e)->ignore)
399 BB_INFO (bb)->succ_count++;
400 for (e = bb->pred; e; e = e->pred_next)
401 if (!EDGE_INFO (e)->ignore)
402 BB_INFO (bb)->pred_count++;
405 /* Avoid predicting entry on exit nodes. */
406 BB_INFO (EXIT_BLOCK_PTR)->succ_count = 2;
407 BB_INFO (ENTRY_BLOCK_PTR)->pred_count = 2;
409 /* For each edge not on the spanning tree, set its execution count from
412 /* The first count in the .da file is the number of times that the function
413 was entered. This is the exec_count for block zero. */
415 for (i = 0; i < n_basic_blocks + 2; i++)
417 basic_block bb = GCOV_INDEX_TO_BB (i);
419 for (e = bb->succ; e; e = e->succ_next)
420 if (!EDGE_INFO (e)->ignore && !EDGE_INFO (e)->on_tree)
425 e->count = exec_counts[exec_counts_pos++];
430 EDGE_INFO (e)->count_valid = 1;
431 BB_INFO (bb)->succ_count--;
432 BB_INFO (e->dest)->pred_count--;
435 fprintf (rtl_dump_file, "\nRead edge from %i to %i, count:",
436 bb->index, e->dest->index);
437 fprintf (rtl_dump_file, HOST_WIDEST_INT_PRINT_DEC,
438 (HOST_WIDEST_INT) e->count);
444 fprintf (rtl_dump_file, "\n%d edge counts read\n", num_edges);
446 /* For every block in the file,
447 - if every exit/entrance edge has a known count, then set the block count
448 - if the block count is known, and every exit/entrance edge but one has
449 a known execution count, then set the count of the remaining edge
451 As edge counts are set, decrement the succ/pred count, but don't delete
452 the edge, that way we can easily tell when all edges are known, or only
453 one edge is unknown. */
455 /* The order that the basic blocks are iterated through is important.
456 Since the code that finds spanning trees starts with block 0, low numbered
457 edges are put on the spanning tree in preference to high numbered edges.
458 Hence, most instrumented edges are at the end. Graph solving works much
459 faster if we propagate numbers from the end to the start.
461 This takes an average of slightly more than 3 passes. */
469 for (i = n_basic_blocks + 1; i >= 0; i--)
471 basic_block bb = GCOV_INDEX_TO_BB (i);
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. */
566 for (i = 0; i < n_basic_blocks; i++)
568 basic_block bb = BASIC_BLOCK (i);
569 if (BB_INFO (bb)->succ_count || BB_INFO (bb)->pred_count)
573 /* For every edge, calculate its branch probability and add a reg_note
574 to the branch insn to indicate this. */
576 for (i = 0; i < 20; i++)
578 num_never_executed = 0;
581 for (i = 0; i <= n_basic_blocks + 1; i++)
583 basic_block bb = GCOV_INDEX_TO_BB (i);
591 for (e = bb->succ; e; e = e->succ_next)
593 e->probability = (e->count * REG_BR_PROB_BASE + total / 2) / total;
594 if (e->probability < 0 || e->probability > REG_BR_PROB_BASE)
596 error ("corrupted profile info: prob for %d-%d thought to be %d",
597 e->src->index, e->dest->index, e->probability);
598 e->probability = REG_BR_PROB_BASE / 2;
602 && any_condjump_p (bb->end)
603 && bb->succ->succ_next)
609 /* Find the branch edge. It is possible that we do have fake
611 for (e = bb->succ; e->flags & (EDGE_FAKE | EDGE_FALLTHRU);
613 continue; /* Loop body has been intentionally left blank. */
615 prob = e->probability;
616 index = prob * 20 / REG_BR_PROB_BASE;
620 hist_br_prob[index]++;
622 note = find_reg_note (bb->end, REG_BR_PROB, 0);
623 /* There may be already note put by some other pass, such
624 as builtin_expect expander. */
626 XEXP (note, 0) = GEN_INT (prob);
629 = gen_rtx_EXPR_LIST (REG_BR_PROB, GEN_INT (prob),
630 REG_NOTES (bb->end));
634 /* Otherwise distribute the probabilities evenly so we get sane sum.
635 Use simple heuristics that if there are normal edges, give all abnormals
636 frequency of 0, otherwise distribute the frequency over abnormals
637 (this is the case of noreturn calls). */
640 for (e = bb->succ; e; e = e->succ_next)
641 if (!(e->flags & (EDGE_COMPLEX | EDGE_FAKE)))
645 for (e = bb->succ; e; e = e->succ_next)
646 if (!(e->flags & (EDGE_COMPLEX | EDGE_FAKE)))
647 e->probability = REG_BR_PROB_BASE / total;
653 for (e = bb->succ; e; e = e->succ_next)
655 for (e = bb->succ; e; e = e->succ_next)
656 e->probability = REG_BR_PROB_BASE / total;
659 && any_condjump_p (bb->end)
660 && bb->succ->succ_next)
661 num_branches++, num_never_executed;
667 fprintf (rtl_dump_file, "%d branches\n", num_branches);
668 fprintf (rtl_dump_file, "%d branches never executed\n",
671 for (i = 0; i < 10; i++)
672 fprintf (rtl_dump_file, "%d%% branches in range %d-%d%%\n",
673 (hist_br_prob[i] + hist_br_prob[19-i]) * 100 / num_branches,
676 total_num_branches += num_branches;
677 total_num_never_executed += num_never_executed;
678 for (i = 0; i < 20; i++)
679 total_hist_br_prob[i] += hist_br_prob[i];
681 fputc ('\n', rtl_dump_file);
682 fputc ('\n', rtl_dump_file);
685 free_aux_for_blocks ();
690 /* Compute checksum for the current function. */
692 #define CHSUM_HASH 500000003
693 #define CHSUM_SHIFT 2
702 for (i = 0; i < n_basic_blocks ; i++)
704 basic_block bb = BASIC_BLOCK (i);
707 for (e = bb->succ; e; e = e->succ_next)
709 chsum = ((chsum << CHSUM_SHIFT) + (BB_TO_GCOV_INDEX (e->dest) + 1)) % CHSUM_HASH;
712 chsum = (chsum << CHSUM_SHIFT) % CHSUM_HASH;
718 /* Instrument and/or analyze program behavior based on program flow graph.
719 In either case, this function builds a flow graph for the function being
720 compiled. The flow graph is stored in BB_GRAPH.
722 When FLAG_PROFILE_ARCS is nonzero, this function instruments the edges in
723 the flow graph that are needed to reconstruct the dynamic behavior of the
726 When FLAG_BRANCH_PROBABILITIES is nonzero, this function reads auxiliary
727 information from a data file containing edge count information from previous
728 executions of the function being compiled. In this case, the flow graph is
729 annotated with actual execution counts, which are later propagated into the
730 rtl for optimization purposes.
732 Main entry point of this file. */
738 int num_edges, ignored_edges;
739 struct edge_list *el;
741 profile_info.current_function_cfg_checksum = compute_checksum ();
744 fprintf (rtl_dump_file, "CFG checksum is %ld\n",
745 profile_info.current_function_cfg_checksum);
747 /* Start of a function. */
748 if (flag_test_coverage)
749 output_gcov_string (current_function_name, (long) -2);
751 total_num_times_called++;
753 flow_call_edges_add (NULL);
754 add_noreturn_fake_exit_edges ();
756 /* We can't handle cyclic regions constructed using abnormal edges.
757 To avoid these we replace every source of abnormal edge by a fake
758 edge from entry node and every destination by fake edge to exit.
759 This keeps graph acyclic and our calculation exact for all normal
760 edges except for exit and entrance ones.
762 We also add fake exit edges for each call and asm statement in the
763 basic, since it may not return. */
765 for (i = 0; i < n_basic_blocks ; i++)
767 int need_exit_edge = 0, need_entry_edge = 0;
768 int have_exit_edge = 0, have_entry_edge = 0;
769 basic_block bb = BASIC_BLOCK (i);
773 /* Add fake edges from entry block to the call insns that may return
774 twice. The CFG is not quite correct then, as call insn plays more
775 role of CODE_LABEL, but for our purposes, everything should be OK,
776 as we never insert code to the beggining of basic block. */
777 for (insn = bb->head; insn != NEXT_INSN (bb->end);
778 insn = NEXT_INSN (insn))
780 if (GET_CODE (insn) == CALL_INSN
781 && find_reg_note (insn, REG_SETJMP, NULL))
783 if (GET_CODE (bb->head) == CODE_LABEL
784 || insn != NEXT_INSN (bb->head))
786 e = split_block (bb, PREV_INSN (insn));
787 make_edge (ENTRY_BLOCK_PTR, e->dest, EDGE_FAKE);
792 /* We should not get abort here, as call to setjmp should not
793 be the very first instruction of function. */
796 make_edge (ENTRY_BLOCK_PTR, bb, EDGE_FAKE);
801 for (e = bb->succ; e; e = e->succ_next)
803 if ((e->flags & (EDGE_ABNORMAL | EDGE_ABNORMAL_CALL))
804 && e->dest != EXIT_BLOCK_PTR)
806 if (e->dest == EXIT_BLOCK_PTR)
809 for (e = bb->pred; e; e = e->pred_next)
811 if ((e->flags & (EDGE_ABNORMAL | EDGE_ABNORMAL_CALL))
812 && e->src != ENTRY_BLOCK_PTR)
814 if (e->src == ENTRY_BLOCK_PTR)
818 if (need_exit_edge && !have_exit_edge)
821 fprintf (rtl_dump_file, "Adding fake exit edge to bb %i\n",
823 make_edge (bb, EXIT_BLOCK_PTR, EDGE_FAKE);
825 if (need_entry_edge && !have_entry_edge)
828 fprintf (rtl_dump_file, "Adding fake entry edge to bb %i\n",
830 make_edge (ENTRY_BLOCK_PTR, bb, EDGE_FAKE);
834 el = create_edge_list ();
835 num_edges = NUM_EDGES (el);
836 alloc_aux_for_edges (sizeof (struct edge_info));
839 for (i = 0 ; i < num_edges ; i++)
841 edge e = INDEX_EDGE (el, i);
844 /* Mark edges we've replaced by fake edges above as ignored. */
845 if ((e->flags & (EDGE_ABNORMAL | EDGE_ABNORMAL_CALL))
846 && e->src != ENTRY_BLOCK_PTR && e->dest != EXIT_BLOCK_PTR)
848 EDGE_INFO (e)->ignore = 1;
853 #ifdef ENABLE_CHECKING
857 /* Output line number information about each basic block for
859 if (flag_test_coverage)
862 for (i = 0 ; i < n_basic_blocks; i++)
864 basic_block bb = BASIC_BLOCK (i);
866 static int ignore_next_note = 0;
868 /* We are looking for line number notes. Search backward before
869 basic block to find correct ones. */
870 insn = prev_nonnote_insn (insn);
874 insn = NEXT_INSN (insn);
876 /* Output a zero to the .bb file to indicate that a new
877 block list is starting. */
878 __write_long (0, bb_file, 4);
880 while (insn != bb->end)
882 if (GET_CODE (insn) == NOTE)
884 /* Must ignore the line number notes that immediately
885 follow the end of an inline function to avoid counting
886 it twice. There is a note before the call, and one
888 if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_REPEATED_LINE_NUMBER)
889 ignore_next_note = 1;
890 else if (NOTE_LINE_NUMBER (insn) > 0)
892 if (ignore_next_note)
893 ignore_next_note = 0;
896 /* If this is a new source file, then output the
897 file's name to the .bb file. */
898 if (! last_bb_file_name
899 || strcmp (NOTE_SOURCE_FILE (insn),
902 if (last_bb_file_name)
903 free (last_bb_file_name);
905 = xstrdup (NOTE_SOURCE_FILE (insn));
906 output_gcov_string (NOTE_SOURCE_FILE (insn),
909 /* Output the line number to the .bb file. Must be
910 done after the output_bb_profile_data() call, and
911 after the file name is written, to ensure that it
912 is correctly handled by gcov. */
913 __write_long (NOTE_LINE_NUMBER (insn), bb_file, 4);
917 insn = NEXT_INSN (insn);
920 __write_long (0, bb_file, 4);
923 /* Create spanning tree from basic block graph, mark each edge that is
924 on the spanning tree. We insert as many abnormal and critical edges
925 as possible to minimize number of edge splits necessary. */
927 find_spanning_tree (el);
929 /* Fake edges that are not on the tree will not be instrumented, so
930 mark them ignored. */
931 for (i = 0; i < num_edges; i++)
933 edge e = INDEX_EDGE (el, i);
934 struct edge_info *inf = EDGE_INFO (e);
935 if ((e->flags & EDGE_FAKE) && !inf->ignore && !inf->on_tree)
942 total_num_blocks += n_basic_blocks + 2;
944 fprintf (rtl_dump_file, "%d basic blocks\n", n_basic_blocks);
946 total_num_edges += num_edges;
948 fprintf (rtl_dump_file, "%d edges\n", num_edges);
950 total_num_edges_ignored += ignored_edges;
952 fprintf (rtl_dump_file, "%d ignored edges\n", ignored_edges);
954 /* Create a .bbg file from which gcov can reconstruct the basic block
955 graph. First output the number of basic blocks, and then for every
956 edge output the source and target basic block numbers.
957 NOTE: The format of this file must be compatible with gcov. */
959 if (flag_test_coverage)
963 __write_gcov_string (current_function_name,
964 strlen (current_function_name), bbg_file, -1);
966 /* write checksum. */
967 __write_long (profile_info.current_function_cfg_checksum, bbg_file, 4);
969 /* The plus 2 stands for entry and exit block. */
970 __write_long (n_basic_blocks + 2, bbg_file, 4);
971 __write_long (num_edges - ignored_edges + 1, bbg_file, 4);
973 for (i = 0; i < n_basic_blocks + 1; i++)
975 basic_block bb = GCOV_INDEX_TO_BB (i);
979 for (e = bb->succ; e; e = e->succ_next)
980 if (!EDGE_INFO (e)->ignore)
982 __write_long (count, bbg_file, 4);
984 for (e = bb->succ; e; e = e->succ_next)
986 struct edge_info *i = EDGE_INFO (e);
992 if (e->flags & EDGE_FAKE)
994 if (e->flags & EDGE_FALLTHRU)
997 __write_long (BB_TO_GCOV_INDEX (e->dest), bbg_file, 4);
998 __write_long (flag_bits, bbg_file, 4);
1002 /* Emit fake loopback edge for EXIT block to maintain compatibility with
1004 __write_long (1, bbg_file, 4);
1005 __write_long (0, bbg_file, 4);
1006 __write_long (0x1, bbg_file, 4);
1008 /* Emit a -1 to separate the list of all edges from the list of
1009 loop back edges that follows. */
1010 __write_long (-1, bbg_file, 4);
1013 if (flag_branch_probabilities)
1014 compute_branch_probabilities ();
1016 /* For each edge not on the spanning tree, add counting code as rtl. */
1018 if (profile_arc_flag)
1020 instrument_edges (el);
1021 allocate_reg_info (max_reg_num (), FALSE, FALSE);
1024 remove_fake_edges ();
1025 /* Re-merge split basic blocks and the mess introduced by
1026 insert_insn_on_edge. */
1027 cleanup_cfg (profile_arc_flag ? CLEANUP_EXPENSIVE : 0);
1029 dump_flow_info (rtl_dump_file);
1031 free_aux_for_edges ();
1032 free_edge_list (el);
1035 /* Union find algorithm implementation for the basic blocks using
1042 basic_block group = bb, bb1;
1044 while ((basic_block) group->aux != group)
1045 group = (basic_block) group->aux;
1047 /* Compress path. */
1048 while ((basic_block) bb->aux != group)
1050 bb1 = (basic_block) bb->aux;
1051 bb->aux = (void *) group;
1058 union_groups (bb1, bb2)
1059 basic_block bb1, bb2;
1061 basic_block bb1g = find_group (bb1);
1062 basic_block bb2g = find_group (bb2);
1064 /* ??? I don't have a place for the rank field. OK. Lets go w/o it,
1065 this code is unlikely going to be performance problem anyway. */
1072 /* This function searches all of the edges in the program flow graph, and puts
1073 as many bad edges as possible onto the spanning tree. Bad edges include
1074 abnormals edges, which can't be instrumented at the moment. Since it is
1075 possible for fake edges to form an cycle, we will have to develop some
1076 better way in the future. Also put critical edges to the tree, since they
1077 are more expensive to instrument. */
1080 find_spanning_tree (el)
1081 struct edge_list *el;
1084 int num_edges = NUM_EDGES (el);
1086 /* We use aux field for standard union-find algorithm. */
1087 EXIT_BLOCK_PTR->aux = EXIT_BLOCK_PTR;
1088 ENTRY_BLOCK_PTR->aux = ENTRY_BLOCK_PTR;
1089 for (i = 0; i < n_basic_blocks; i++)
1090 BASIC_BLOCK (i)->aux = BASIC_BLOCK (i);
1092 /* Add fake edge exit to entry we can't instrument. */
1093 union_groups (EXIT_BLOCK_PTR, ENTRY_BLOCK_PTR);
1095 /* First add all abnormal edges to the tree unless they form an cycle. Also
1096 add all edges to EXIT_BLOCK_PTR to avoid inserting profiling code behind
1097 setting return value from function. */
1098 for (i = 0; i < num_edges; i++)
1100 edge e = INDEX_EDGE (el, i);
1101 if (((e->flags & (EDGE_ABNORMAL | EDGE_ABNORMAL_CALL | EDGE_FAKE))
1102 || e->dest == EXIT_BLOCK_PTR
1104 && !EDGE_INFO (e)->ignore
1105 && (find_group (e->src) != find_group (e->dest)))
1108 fprintf (rtl_dump_file, "Abnormal edge %d to %d put to tree\n",
1109 e->src->index, e->dest->index);
1110 EDGE_INFO (e)->on_tree = 1;
1111 union_groups (e->src, e->dest);
1115 /* Now insert all critical edges to the tree unless they form an cycle. */
1116 for (i = 0; i < num_edges; i++)
1118 edge e = INDEX_EDGE (el, i);
1119 if ((EDGE_CRITICAL_P (e))
1120 && !EDGE_INFO (e)->ignore
1121 && (find_group (e->src) != find_group (e->dest)))
1124 fprintf (rtl_dump_file, "Critical edge %d to %d put to tree\n",
1125 e->src->index, e->dest->index);
1126 EDGE_INFO (e)->on_tree = 1;
1127 union_groups (e->src, e->dest);
1131 /* And now the rest. */
1132 for (i = 0; i < num_edges; i++)
1134 edge e = INDEX_EDGE (el, i);
1135 if (find_group (e->src) != find_group (e->dest)
1136 && !EDGE_INFO (e)->ignore)
1139 fprintf (rtl_dump_file, "Normal edge %d to %d put to tree\n",
1140 e->src->index, e->dest->index);
1141 EDGE_INFO (e)->on_tree = 1;
1142 union_groups (e->src, e->dest);
1146 EXIT_BLOCK_PTR->aux = NULL;
1147 ENTRY_BLOCK_PTR->aux = NULL;
1148 for (i = 0; i < n_basic_blocks; i++)
1149 BASIC_BLOCK (i)->aux = NULL;
1152 /* Perform file-level initialization for branch-prob processing. */
1155 init_branch_prob (filename)
1156 const char *filename;
1161 if (flag_test_coverage)
1163 int len = strlen (filename);
1164 char *data_file, *bbg_file_name;
1166 /* Open an output file for the basic block/line number map. */
1167 data_file = (char *) alloca (len + 4);
1168 strcpy (data_file, filename);
1169 strip_off_ending (data_file, len);
1170 strcat (data_file, ".bb");
1171 if ((bb_file = fopen (data_file, "wb")) == 0)
1172 fatal_io_error ("can't open %s", data_file);
1174 /* Open an output file for the program flow graph. */
1175 bbg_file_name = (char *) alloca (len + 5);
1176 strcpy (bbg_file_name, filename);
1177 strip_off_ending (bbg_file_name, len);
1178 strcat (bbg_file_name, ".bbg");
1179 if ((bbg_file = fopen (bbg_file_name, "wb")) == 0)
1180 fatal_io_error ("can't open %s", bbg_file_name);
1182 /* Initialize to zero, to ensure that the first file name will be
1183 written to the .bb file. */
1184 last_bb_file_name = 0;
1187 if (flag_branch_probabilities)
1191 len = strlen (filename);
1192 da_file_name = (char *) alloca (len + 4);
1193 strcpy (da_file_name, filename);
1194 strip_off_ending (da_file_name, len);
1195 strcat (da_file_name, ".da");
1196 if ((da_file = fopen (da_file_name, "rb")) == 0)
1197 warning ("file %s not found, execution counts assumed to be zero",
1201 if (profile_arc_flag)
1202 init_edge_profiler ();
1204 total_num_blocks = 0;
1205 total_num_edges = 0;
1206 total_num_edges_ignored = 0;
1207 total_num_edges_instrumented = 0;
1208 total_num_blocks_created = 0;
1209 total_num_passes = 0;
1210 total_num_times_called = 0;
1211 total_num_branches = 0;
1212 total_num_never_executed = 0;
1213 for (i = 0; i < 20; i++)
1214 total_hist_br_prob[i] = 0;
1217 /* Performs file-level cleanup after branch-prob processing
1223 if (flag_test_coverage)
1229 if (flag_branch_probabilities && da_file)
1234 fprintf (rtl_dump_file, "\n");
1235 fprintf (rtl_dump_file, "Total number of blocks: %d\n",
1237 fprintf (rtl_dump_file, "Total number of edges: %d\n", total_num_edges);
1238 fprintf (rtl_dump_file, "Total number of ignored edges: %d\n",
1239 total_num_edges_ignored);
1240 fprintf (rtl_dump_file, "Total number of instrumented edges: %d\n",
1241 total_num_edges_instrumented);
1242 fprintf (rtl_dump_file, "Total number of blocks created: %d\n",
1243 total_num_blocks_created);
1244 fprintf (rtl_dump_file, "Total number of graph solution passes: %d\n",
1246 if (total_num_times_called != 0)
1247 fprintf (rtl_dump_file, "Average number of graph solution passes: %d\n",
1248 (total_num_passes + (total_num_times_called >> 1))
1249 / total_num_times_called);
1250 fprintf (rtl_dump_file, "Total number of branches: %d\n",
1251 total_num_branches);
1252 fprintf (rtl_dump_file, "Total number of branches never executed: %d\n",
1253 total_num_never_executed);
1254 if (total_num_branches)
1258 for (i = 0; i < 10; i++)
1259 fprintf (rtl_dump_file, "%d%% branches in range %d-%d%%\n",
1260 (total_hist_br_prob[i] + total_hist_br_prob[19-i]) * 100
1261 / total_num_branches, 5*i, 5*i+5);
1266 /* The label used by the edge profiling code. */
1268 static rtx profiler_label;
1270 /* Initialize the profiler_label. */
1273 init_edge_profiler ()
1275 /* Generate and save a copy of this so it can be shared. */
1277 ASM_GENERATE_INTERNAL_LABEL (buf, "LPBX", 2);
1278 profiler_label = gen_rtx_SYMBOL_REF (Pmode, ggc_strdup (buf));
1279 ggc_add_rtx_root (&profiler_label, 1);
1282 /* Output instructions as RTL to increment the edge execution count. */
1285 gen_edge_profiler (edgeno)
1288 enum machine_mode mode = mode_for_size (GCOV_TYPE_SIZE, MODE_INT, 0);
1294 tmp = force_reg (Pmode, profiler_label);
1295 tmp = plus_constant (tmp, GCOV_TYPE_SIZE / BITS_PER_UNIT * edgeno);
1296 mem_ref = validize_mem (gen_rtx_MEM (mode, tmp));
1298 tmp = expand_simple_binop (mode, PLUS, mem_ref, const1_rtx,
1299 mem_ref, 0, OPTAB_WIDEN);
1301 set_mem_alias_set (mem_ref, new_alias_set ());
1304 emit_move_insn (copy_rtx (mem_ref), tmp);
1306 sequence = gen_sequence ();
1311 /* Output code for a constructor that will invoke __bb_init_func, if
1312 this has not already been done. */
1315 output_func_start_profiler ()
1317 tree fnname, fndecl;
1320 const char *cfnname;
1322 enum machine_mode mode = mode_for_size (GCOV_TYPE_SIZE, MODE_INT, 0);
1323 int save_flag_inline_functions = flag_inline_functions;
1325 /* It's either already been output, or we don't need it because we're
1326 not doing profile-edges. */
1327 if (! need_func_profiler)
1330 need_func_profiler = 0;
1332 /* Synthesize a constructor function to invoke __bb_init_func with a
1333 pointer to this object file's profile block. */
1335 /* Try and make a unique name given the "file function name".
1337 And no, I don't like this either. */
1339 fnname = get_file_function_name ('I');
1340 cfnname = IDENTIFIER_POINTER (fnname);
1341 name = concat (cfnname, "GCOV", NULL);
1342 fnname = get_identifier (name);
1345 fndecl = build_decl (FUNCTION_DECL, fnname,
1346 build_function_type (void_type_node, NULL_TREE));
1347 DECL_EXTERNAL (fndecl) = 0;
1349 /* It can be a static function as long as collect2 does not have
1350 to scan the object file to find its ctor/dtor routine. */
1351 TREE_PUBLIC (fndecl) = ! targetm.have_ctors_dtors;
1353 TREE_USED (fndecl) = 1;
1355 DECL_RESULT (fndecl) = build_decl (RESULT_DECL, NULL_TREE, void_type_node);
1357 fndecl = (*lang_hooks.decls.pushdecl) (fndecl);
1358 rest_of_decl_compilation (fndecl, 0, 1, 0);
1359 announce_function (fndecl);
1360 current_function_decl = fndecl;
1361 DECL_INITIAL (fndecl) = error_mark_node;
1362 make_decl_rtl (fndecl, NULL);
1363 init_function_start (fndecl, input_filename, lineno);
1364 (*lang_hooks.decls.pushlevel) (0);
1365 expand_function_start (fndecl, 0);
1366 cfun->arc_profile = 0;
1368 /* Actually generate the code to call __bb_init_func. */
1369 ASM_GENERATE_INTERNAL_LABEL (buf, "LPBX", 0);
1370 table_address = force_reg (Pmode,
1371 gen_rtx_SYMBOL_REF (Pmode, ggc_strdup (buf)));
1372 emit_library_call (gen_rtx_SYMBOL_REF (Pmode, "__bb_init_func"), LCT_NORMAL,
1373 mode, 1, table_address, Pmode);
1375 expand_function_end (input_filename, lineno, 0);
1376 (*lang_hooks.decls.poplevel) (1, 0, 1);
1378 /* Since fndecl isn't in the list of globals, it would never be emitted
1379 when it's considered to be 'safe' for inlining, so turn off
1380 flag_inline_functions. */
1381 flag_inline_functions = 0;
1383 rest_of_compilation (fndecl);
1385 /* Reset flag_inline_functions to its original value. */
1386 flag_inline_functions = save_flag_inline_functions;
1389 fflush (asm_out_file);
1390 current_function_decl = NULL_TREE;
1392 if (targetm.have_ctors_dtors)
1393 (* targetm.asm_out.constructor) (XEXP (DECL_RTL (fndecl), 0),
1394 DEFAULT_INIT_PRIORITY);