-/* Calculate branch probabilities, and basic block execution counts.
- Copyright (C) 1990, 91-94, 96-98, 1999 Free Software Foundation, Inc.
+/* Calculate branch probabilities, and basic block execution counts.
+ Copyright (C) 1990, 1991, 1992, 1993, 1994, 1996, 1997, 1998, 1999,
+ 2000, 2001 Free Software Foundation, Inc.
Contributed by James E. Wilson, UC Berkeley/Cygnus Support;
based on some ideas from Dain Samples of UC Berkeley.
Further mangling by Bob Manson, Cygnus Support.
-This file is part of GNU CC.
+This file is part of GCC.
-GNU CC is free software; you can redistribute it and/or modify
-it under the terms of the GNU General Public License as published by
-the Free Software Foundation; either version 2, or (at your option)
-any later version.
+GCC is free software; you can redistribute it and/or modify it under
+the terms of the GNU General Public License as published by the Free
+Software Foundation; either version 2, or (at your option) any later
+version.
-GNU CC is distributed in the hope that it will be useful,
-but WITHOUT ANY WARRANTY; without even the implied warranty of
-MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
-GNU General Public License for more details.
+GCC is distributed in the hope that it will be useful, but WITHOUT ANY
+WARRANTY; without even the implied warranty of MERCHANTABILITY or
+FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
+for more details.
You should have received a copy of the GNU General Public License
-along with GNU CC; see the file COPYING. If not, write to
-the Free Software Foundation, 59 Temple Place - Suite 330,
-Boston, MA 02111-1307, USA. */
-
-/* ??? Really should not put insns inside of LIBCALL sequences, when putting
- insns after a call, should look for the insn setting the retval, and
- insert the insns after that one. */
+along with GCC; see the file COPYING. If not, write to the Free
+Software Foundation, 59 Temple Place - Suite 330, Boston, MA
+02111-1307, USA. */
+
+/* Generate basic block profile instrumentation and auxiliary files.
+ Profile generation is optimized, so that not all arcs in the basic
+ block graph need instrumenting. First, the BB graph is closed with
+ one entry (function start), and one exit (function exit). Any
+ ABNORMAL_EDGE cannot be instrumented (because there is no control
+ path to place the code). We close the graph by inserting fake
+ EDGE_FAKE edges to the EXIT_BLOCK, from the sources of abnormal
+ edges that do not go to the exit_block. We ignore such abnormal
+ edges. Naturally these fake edges are never directly traversed,
+ and so *cannot* be directly instrumented. Some other graph
+ massaging is done. To optimize the instrumentation we generate the
+ BB minimal span tree, only edges that are not on the span tree
+ (plus the entry point) need instrumenting. From that information
+ all other edge counts can be deduced. By construction all fake
+ edges must be on the spanning tree. We also attempt to place
+ EDGE_CRITICAL edges on the spanning tree.
+
+ The auxiliary file generated is <dumpbase>.bbg. The format is
+ described in full in gcov-io.h. */
/* ??? Register allocation should use basic block execution counts to
give preference to the most commonly executed blocks. */
-/* ??? The .da files are not safe. Changing the program after creating .da
- files or using different options when compiling with -fbranch-probabilities
- can result the arc data not matching the program. Maybe add instrumented
- arc count to .bbg file? Maybe check whether PFG matches the .bbg file? */
-
/* ??? Should calculate branch probabilities before instrumenting code, since
then we can use arc counts to help decide which arcs to instrument. */
-/* ??? Rearrange code so that the most frequently executed arcs become from
- one block to the next block (i.e. a fall through), move seldom executed
- code outside of loops even at the expense of adding a few branches to
- achieve this, see Dain Sample's UC Berkeley thesis. */
-
#include "config.h"
#include "system.h"
+#include "coretypes.h"
+#include "tm.h"
#include "rtl.h"
#include "tree.h"
#include "flags.h"
-#include "insn-flags.h"
#include "insn-config.h"
#include "output.h"
#include "regs.h"
+#include "expr.h"
#include "function.h"
-#include "output.h"
-#include "gcov-io.h"
#include "toplev.h"
#include "ggc.h"
-
-/* One of these is dynamically created whenever we identify an arc in the
- function. */
-
-struct adj_list
-{
- int source;
- int target;
- int arc_count;
+#include "hard-reg-set.h"
+#include "basic-block.h"
+#include "gcov-io.h"
+#include "target.h"
+#include "profile.h"
+#include "libfuncs.h"
+#include "langhooks.h"
+#include "hashtab.h"
+
+/* Additional information about the edges we need. */
+struct edge_info {
unsigned int count_valid : 1;
+
+ /* Is on the spanning tree. */
unsigned int on_tree : 1;
- unsigned int fake : 1;
- unsigned int fall_through : 1;
- rtx branch_insn;
- struct adj_list *pred_next;
- struct adj_list *succ_next;
+
+ /* Pretend this edge does not exist (it is abnormal and we've
+ inserted a fake to compensate). */
+ unsigned int ignore : 1;
};
-#define ARC_TARGET(ARCPTR) (ARCPTR->target)
-#define ARC_SOURCE(ARCPTR) (ARCPTR->source)
-#define ARC_COUNT(ARCPTR) (ARCPTR->arc_count)
+struct bb_info {
+ unsigned int count_valid : 1;
-/* Count the number of basic blocks, and create an array of these structures,
- one for each bb in the function. */
+ /* Number of successor and predecessor edges. */
+ gcov_type succ_count;
+ gcov_type pred_count;
+};
-struct bb_info
+struct function_list
{
- struct adj_list *succ;
- struct adj_list *pred;
- int succ_count;
- int pred_count;
- int exec_count;
- unsigned int count_valid : 1;
- unsigned int on_tree : 1;
- rtx first_insn;
+ struct function_list *next; /* next function */
+ const char *name; /* function name */
+ unsigned cfg_checksum; /* function checksum */
+ unsigned count_edges; /* number of intrumented edges */
};
-/* Indexed by label number, gives the basic block number containing that
- label. */
+static struct function_list *functions_head = 0;
+static struct function_list **functions_tail = &functions_head;
-static int *label_to_bb;
+#define EDGE_INFO(e) ((struct edge_info *) (e)->aux)
+#define BB_INFO(b) ((struct bb_info *) (b)->aux)
-/* Number of valid entries in the label_to_bb array. */
+/* Keep all basic block indexes nonnegative in the gcov output. Index 0
+ is used for entry block, last block exit block. */
+#define BB_TO_GCOV_INDEX(bb) ((bb) == ENTRY_BLOCK_PTR ? 0 \
+ : ((bb) == EXIT_BLOCK_PTR \
+ ? last_basic_block + 1 : (bb)->index + 1))
-static int label_to_bb_size;
+/* Instantiate the profile info structure. */
-/* Indexed by block index, holds the basic block graph. */
-
-static struct bb_info *bb_graph;
+struct profile_info profile_info;
/* Name and file pointer of the output file for the basic block graph. */
-static char *bbg_file_name;
static FILE *bbg_file;
+static char *bbg_file_name;
/* Name and file pointer of the input file for the arc count data. */
-static char *da_file_name;
static FILE *da_file;
+static char *da_file_name;
-/* Pointer of the output file for the basic block/line number map. */
-static FILE *bb_file;
-
-/* Last source file name written to bb_file. */
-
-static char *last_bb_file_name;
-
-/* Indicates whether the next line number note should be output to
- bb_file or not. Used to eliminate a redundant note after an
- expanded inline function call. */
-
-static int ignore_next_note;
-
-/* Used by final, for allocating the proper amount of storage for the
- instrumented arc execution counts. */
-
-int count_instrumented_arcs;
-
-/* Number of executions for the return label. */
-
-int return_label_execution_count;
+/* The name of the count table. Used by the edge profiling code. */
+static GTY(()) rtx profiler_label;
/* Collect statistics on the performance of this pass for the entire source
file. */
static int total_num_blocks;
-static int total_num_arcs;
-static int total_num_arcs_instrumented;
+static int total_num_edges;
+static int total_num_edges_ignored;
+static int total_num_edges_instrumented;
static int total_num_blocks_created;
static int total_num_passes;
static int total_num_times_called;
static int total_num_branches;
/* Forward declarations. */
-static void init_arc PROTO((struct adj_list *, int, int, rtx));
-static void find_spanning_tree PROTO((int));
-static void expand_spanning_tree PROTO((int));
-static void fill_spanning_tree PROTO((int));
-static void init_arc_profiler PROTO((void));
-static void output_arc_profiler PROTO((int, rtx));
-
-#ifndef LONG_TYPE_SIZE
-#define LONG_TYPE_SIZE BITS_PER_WORD
-#endif
-
-/* If non-zero, we need to output a constructor to set up the
- per-object-file data. */
-static int need_func_profiler = 0;
+static void find_spanning_tree PARAMS ((struct edge_list *));
+static rtx gen_edge_profiler PARAMS ((int));
+static void instrument_edges PARAMS ((struct edge_list *));
+static void compute_branch_probabilities PARAMS ((void));
+static hashval_t htab_counts_index_hash PARAMS ((const void *));
+static int htab_counts_index_eq PARAMS ((const void *, const void *));
+static void htab_counts_index_del PARAMS ((void *));
+static void cleanup_counts_index PARAMS ((int));
+static int index_counts_file PARAMS ((void));
+static gcov_type * get_exec_counts PARAMS ((void));
+static unsigned compute_checksum PARAMS ((void));
+static basic_block find_group PARAMS ((basic_block));
+static void union_groups PARAMS ((basic_block, basic_block));
\f
-/* Add arc instrumentation code to the entire insn chain.
+/* Add edge instrumentation code to the entire insn chain.
F is the first insn of the chain.
- NUM_BLOCKS is the number of basic blocks found in F.
- DUMP_FILE, if nonzero, is an rtl dump file we can write to. */
+ NUM_BLOCKS is the number of basic blocks found in F. */
static void
-instrument_arcs (f, num_blocks, dump_file)
- rtx f;
- int num_blocks;
- FILE *dump_file;
+instrument_edges (el)
+ struct edge_list *el;
{
- register int i;
- register struct adj_list *arcptr, *backptr;
- int num_arcs = 0;
- int num_instr_arcs = 0;
- rtx insn;
-
- /* Instrument the program start. */
- /* Handle block 0 specially, since it will always be instrumented,
- but it doesn't have a valid first_insn or branch_insn. We must
- put the instructions before the NOTE_INSN_FUNCTION_BEG note, so
- that they don't clobber any of the parameters of the current
- function. */
- for (insn = f; insn; insn = NEXT_INSN (insn))
- if (GET_CODE (insn) == NOTE
- && NOTE_LINE_NUMBER (insn) == NOTE_INSN_FUNCTION_BEG)
- break;
- insn = PREV_INSN (insn);
- need_func_profiler = 1;
- output_arc_profiler (total_num_arcs_instrumented + num_instr_arcs++, insn);
-
- for (i = 1; i < num_blocks; i++)
- for (arcptr = bb_graph[i].succ; arcptr; arcptr = arcptr->succ_next)
- if (! arcptr->on_tree)
- {
- if (dump_file)
- fprintf (dump_file, "Arc %d to %d instrumented\n", i,
- ARC_TARGET (arcptr));
+ int num_instr_edges = 0;
+ int num_edges = NUM_EDGES (el);
+ basic_block bb;
+ remove_fake_edges ();
- /* Check to see if this arc is the only exit from its source block,
- or the only entrance to its target block. In either case,
- we don't need to create a new block to instrument the arc. */
-
- if (bb_graph[i].succ == arcptr && arcptr->succ_next == 0)
- {
- /* Instrument the source block. */
- output_arc_profiler (total_num_arcs_instrumented
- + num_instr_arcs++,
- PREV_INSN (bb_graph[i].first_insn));
- }
- else if (arcptr == bb_graph[ARC_TARGET (arcptr)].pred
- && arcptr->pred_next == 0)
- {
- /* Instrument the target block. */
- output_arc_profiler (total_num_arcs_instrumented
- + num_instr_arcs++,
- PREV_INSN (bb_graph[ARC_TARGET (arcptr)].first_insn));
- }
- else if (arcptr->fall_through)
+ FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
+ {
+ edge e = bb->succ;
+ while (e)
+ {
+ struct edge_info *inf = EDGE_INFO (e);
+ if (!inf->ignore && !inf->on_tree)
{
- /* This is a fall-through; put the instrumentation code after
- the branch that ends this block. */
-
- for (backptr = bb_graph[i].succ; backptr;
- backptr = backptr->succ_next)
- if (backptr != arcptr)
- break;
-
- output_arc_profiler (total_num_arcs_instrumented
- + num_instr_arcs++,
- backptr->branch_insn);
+ if (e->flags & EDGE_ABNORMAL)
+ abort ();
+ if (rtl_dump_file)
+ fprintf (rtl_dump_file, "Edge %d to %d instrumented%s\n",
+ e->src->index, e->dest->index,
+ EDGE_CRITICAL_P (e) ? " (and split)" : "");
+ insert_insn_on_edge (
+ gen_edge_profiler (total_num_edges_instrumented
+ + num_instr_edges++), e);
}
- else
- {
- /* Must emit a new basic block to hold the arc counting code. */
- enum rtx_code code = GET_CODE (PATTERN (arcptr->branch_insn));
+ e = e->succ_next;
+ }
+ }
- if (code == SET)
- {
- /* Create the new basic block right after the branch.
- Invert the branch so that it jumps past the end of the new
- block. The new block will consist of the instrumentation
- code, and a jump to the target of this arc. */
- int this_is_simplejump = simplejump_p (arcptr->branch_insn);
- rtx new_label = gen_label_rtx ();
- rtx old_label, set_src;
- rtx after = arcptr->branch_insn;
-
- /* Simplejumps can't reach here. */
- if (this_is_simplejump)
- abort ();
+ profile_info.count_edges_instrumented_now = num_instr_edges;
+ total_num_edges_instrumented += num_instr_edges;
+ profile_info.count_instrumented_edges = total_num_edges_instrumented;
- /* We can't use JUMP_LABEL, because it won't be set if we
- are compiling without optimization. */
+ total_num_blocks_created += num_edges;
+ if (rtl_dump_file)
+ fprintf (rtl_dump_file, "%d edges instrumented\n", num_instr_edges);
- set_src = SET_SRC (single_set (arcptr->branch_insn));
- if (GET_CODE (set_src) == LABEL_REF)
- old_label = set_src;
- else if (GET_CODE (set_src) != IF_THEN_ELSE)
- abort ();
- else if (XEXP (set_src, 1) == pc_rtx)
- old_label = XEXP (XEXP (set_src, 2), 0);
- else
- old_label = XEXP (XEXP (set_src, 1), 0);
-
- /* Set the JUMP_LABEL so that redirect_jump will work. */
- JUMP_LABEL (arcptr->branch_insn) = old_label;
-
- /* Add a use for OLD_LABEL that will be needed when we emit
- the JUMP_INSN below. If we don't do this here,
- `invert_jump' might delete it for us. We must add two
- when not optimizing, because the NUSES is zero now,
- but must be at least two to prevent the label from being
- deleted. */
- LABEL_NUSES (old_label) += 2;
-
- /* Emit the insns for the new block in reverse order,
- since that is most convenient. */
+ commit_edge_insertions_watch_calls ();
+}
+\f
+struct section_reference
+{
+ long offset;
+ int owns_summary;
+ long *summary;
+};
- if (this_is_simplejump)
- {
- after = NEXT_INSN (arcptr->branch_insn);
- if (! redirect_jump (arcptr->branch_insn, new_label))
- /* Don't know what to do if this branch won't
- redirect. */
- abort ();
- }
- else
- {
- if (! invert_jump (arcptr->branch_insn, new_label))
- /* Don't know what to do if this branch won't invert. */
- abort ();
+struct da_index_entry
+{
+ /* We hash by */
+ char *function_name;
+ unsigned section;
+ /* and store */
+ unsigned checksum;
+ unsigned n_offsets;
+ struct section_reference *offsets;
+};
- emit_label_after (new_label, after);
- LABEL_NUSES (new_label)++;
- }
- emit_barrier_after (after);
- emit_jump_insn_after (gen_jump (old_label), after);
- JUMP_LABEL (NEXT_INSN (after)) = old_label;
-
- /* Instrument the source arc. */
- output_arc_profiler (total_num_arcs_instrumented
- + num_instr_arcs++,
- after);
- if (this_is_simplejump)
- {
- emit_label_after (new_label, after);
- LABEL_NUSES (new_label)++;
- }
- }
- else if (code == ADDR_VEC || code == ADDR_DIFF_VEC)
- {
- /* A table jump. Create a new basic block immediately
- after the table, by emitting a barrier, a label, a
- counting note, and a jump to the old label. Put the
- new label in the table. */
-
- rtx new_label = gen_label_rtx ();
- rtx old_lref, new_lref;
- int index;
-
- /* Must determine the old_label reference, do this
- by counting the arcs after this one, which will
- give the index of our label in the table. */
-
- index = 0;
- for (backptr = arcptr->succ_next; backptr;
- backptr = backptr->succ_next)
- index++;
-
- old_lref = XVECEXP (PATTERN (arcptr->branch_insn),
- (code == ADDR_DIFF_VEC), index);
-
- /* Emit the insns for the new block in reverse order,
- since that is most convenient. */
- emit_jump_insn_after (gen_jump (XEXP (old_lref, 0)),
- arcptr->branch_insn);
- JUMP_LABEL (NEXT_INSN (arcptr->branch_insn))
- = XEXP (old_lref, 0);
-
- /* Instrument the source arc. */
- output_arc_profiler (total_num_arcs_instrumented
- + num_instr_arcs++,
- arcptr->branch_insn);
-
- emit_label_after (new_label, arcptr->branch_insn);
- LABEL_NUSES (NEXT_INSN (arcptr->branch_insn))++;
- emit_barrier_after (arcptr->branch_insn);
-
- /* Fix up the table jump. */
- new_lref = gen_rtx_LABEL_REF (Pmode, new_label);
- XVECEXP (PATTERN (arcptr->branch_insn),
- (code == ADDR_DIFF_VEC), index) = new_lref;
- }
- else
- abort ();
+static hashval_t
+htab_counts_index_hash (of)
+ const void *of;
+{
+ const struct da_index_entry *entry = of;
- num_arcs += 1;
- if (dump_file)
- fprintf (dump_file,
- "Arc %d to %d needed new basic block\n", i,
- ARC_TARGET (arcptr));
- }
- }
-
- total_num_arcs_instrumented += num_instr_arcs;
- count_instrumented_arcs = total_num_arcs_instrumented;
+ return htab_hash_string (entry->function_name) ^ entry->section;
+}
- total_num_blocks_created += num_arcs;
- if (dump_file)
+static int
+htab_counts_index_eq (of1, of2)
+ const void *of1;
+ const void *of2;
+{
+ const struct da_index_entry *entry1 = of1;
+ const struct da_index_entry *entry2 = of2;
+
+ return !strcmp (entry1->function_name, entry2->function_name)
+ && entry1->section == entry2->section;
+}
+
+static void
+htab_counts_index_del (what)
+ void *what;
+{
+ struct da_index_entry *entry = what;
+ unsigned i;
+
+ for (i = 0; i < entry->n_offsets; i++)
{
- fprintf (dump_file, "%d arcs instrumented\n", num_instr_arcs);
- fprintf (dump_file, "%d extra basic blocks created\n", num_arcs);
+ struct section_reference *act = entry->offsets + i;
+ if (act->owns_summary)
+ free (act->summary);
}
+ free (entry->function_name);
+ free (entry->offsets);
+ free (entry);
}
-/* Output STRING to bb_file, surrounded by DELIMITER. */
+static char *counts_file_name;
+static htab_t counts_file_index = NULL;
static void
-output_gcov_string (string, delimiter)
- char *string;
- long delimiter;
+cleanup_counts_index (close_file)
+ int close_file;
{
- long temp;
-
- /* Write a delimiter to indicate that a file name follows. */
- __write_long (delimiter, bb_file, 4);
-
- /* Write the string. */
- temp = strlen (string) + 1;
- fwrite (string, temp, 1, bb_file);
-
- /* Append a few zeros, to align the output to a 4 byte boundary. */
- temp = temp & 0x3;
- if (temp)
+ if (da_file && close_file)
{
- char c[4];
-
- c[0] = c[1] = c[2] = c[3] = 0;
- fwrite (c, sizeof (char), 4 - temp, bb_file);
+ fclose (da_file);
+ da_file = NULL;
}
-
- /* Store another delimiter in the .bb file, just to make it easy to find the
- end of the file name. */
- __write_long (delimiter, bb_file, 4);
+ if (counts_file_name)
+ free (counts_file_name);
+ counts_file_name = NULL;
+ if (counts_file_index)
+ htab_delete (counts_file_index);
+ counts_file_index = NULL;
}
-\f
-/* Return TRUE if this insn must be a tablejump entry insn. This works for
- the MIPS port, but may give false negatives for some targets. */
-int
-tablejump_entry_p (insn, label)
- rtx insn, label;
+static int
+index_counts_file ()
{
- rtx next = next_active_insn (insn);
- enum rtx_code code = GET_CODE (PATTERN (next));
+ char *function_name_buffer = NULL;
+ unsigned magic, version, ix, checksum;
+ long *summary;
- if (code != ADDR_DIFF_VEC && code != ADDR_VEC)
+ if (!da_file)
return 0;
+ counts_file_index = htab_create (10, htab_counts_index_hash, htab_counts_index_eq, htab_counts_index_del);
- if (PREV_INSN (next) == XEXP (label, 0))
- return 1;
+ /* No .da file, no data. */
+ if (!da_file)
+ return 0;
- return 0;
-}
+ /* Now index all profile sections. */
-/* Instrument and/or analyze program behavior based on program flow graph.
- In either case, this function builds a flow graph for the function being
- compiled. The flow graph is stored in BB_GRAPH.
+ rewind (da_file);
- When FLAG_PROFILE_ARCS is nonzero, this function instruments the arcs in
- the flow graph that are needed to reconstruct the dynamic behavior of the
- flow graph.
+ summary = NULL;
- When FLAG_BRANCH_PROBABILITIES is nonzero, this function reads auxiliary
- information from a data file containing arc count information from previous
- executions of the function being compiled. In this case, the flow graph is
- annotated with actual execution counts, which are later propagated into the
- rtl for optimization purposes.
+ if (gcov_read_unsigned (da_file, &magic) || magic != GCOV_DATA_MAGIC)
+ {
+ warning ("`%s' is not a gcov data file", da_file_name);
+ goto cleanup;
+ }
+ if (gcov_read_unsigned (da_file, &version) || version != GCOV_VERSION)
+ {
+ char v[4], e[4];
+ magic = GCOV_VERSION;
+
+ for (ix = 4; ix--; magic >>= 8, version >>= 8)
+ {
+ v[ix] = version;
+ e[ix] = magic;
+ }
+ warning ("`%s' is version `%.4s', expected version `%.4s'",
+ da_file_name, v, e);
+ goto cleanup;
+ }
+
+ while (1)
+ {
+ unsigned tag, length;
+ long offset;
+
+ offset = gcov_save_position (da_file);
+ if (gcov_read_unsigned (da_file, &tag)
+ || gcov_read_unsigned (da_file, &length))
+ {
+ if (feof (da_file))
+ break;
+ corrupt:;
+ warning ("`%s' is corrupted", da_file_name);
+ goto cleanup;
+ }
+ if (tag == GCOV_TAG_FUNCTION)
+ {
+ if (gcov_read_string (da_file, &function_name_buffer, NULL)
+ || gcov_read_unsigned (da_file, &checksum))
+ goto corrupt;
+ continue;
+ }
+ if (tag == GCOV_TAG_PROGRAM_SUMMARY)
+ {
+ if (length != GCOV_SUMMARY_LENGTH)
+ goto corrupt;
- Main entry point of this file. */
+ if (summary)
+ *summary = offset;
+ summary = NULL;
+ }
+ else
+ {
+ if (function_name_buffer)
+ {
+ struct da_index_entry **slot, elt;
+ elt.function_name = function_name_buffer;
+ elt.section = tag;
-void
-branch_prob (f, dump_file)
- rtx f;
- FILE *dump_file;
-{
- int i, num_blocks;
- struct adj_list *arcptr;
- int num_arcs, changes, passes;
- int total, prob;
- int hist_br_prob[20], num_never_executed, num_branches;
- /* Set to non-zero if we got bad count information. */
- int bad_counts = 0;
-
- /* start of a function. */
- if (flag_test_coverage)
- output_gcov_string (current_function_name, (long) -2);
+ slot = (struct da_index_entry **)
+ htab_find_slot (counts_file_index, &elt, INSERT);
+ if (*slot)
+ {
+ if ((*slot)->checksum != checksum)
+ {
+ warning ("profile mismatch for `%s'", function_name_buffer);
+ goto cleanup;
+ }
+ (*slot)->n_offsets++;
+ (*slot)->offsets = xrealloc ((*slot)->offsets,
+ sizeof (struct section_reference) * (*slot)->n_offsets);
+ }
+ else
+ {
+ *slot = xmalloc (sizeof (struct da_index_entry));
+ (*slot)->function_name = xstrdup (function_name_buffer);
+ (*slot)->section = tag;
+ (*slot)->checksum = checksum;
+ (*slot)->n_offsets = 1;
+ (*slot)->offsets = xmalloc (sizeof (struct section_reference));
+ }
+ (*slot)->offsets[(*slot)->n_offsets - 1].offset = offset;
+ if (summary)
+ (*slot)->offsets[(*slot)->n_offsets - 1].owns_summary = 0;
+ else
+ {
+ summary = xmalloc (sizeof (long));
+ *summary = -1;
+ (*slot)->offsets[(*slot)->n_offsets - 1].owns_summary = 1;
+ }
+ (*slot)->offsets[(*slot)->n_offsets - 1].summary = summary;
+ }
+ }
+ if (gcov_skip (da_file, length))
+ goto corrupt;
+ }
- /* Execute this only if doing arc profiling or branch probabilities. */
- if (! profile_arc_flag && ! flag_branch_probabilities
- && ! flag_test_coverage)
- abort ();
+ free (function_name_buffer);
- total_num_times_called++;
+ return 1;
- /* Create an array label_to_bb of ints of size max_label_num. */
- label_to_bb_size = max_label_num ();
- label_to_bb = (int *) oballoc (label_to_bb_size * sizeof (int));
- bzero ((char *) label_to_bb, label_to_bb_size * sizeof (int));
+cleanup:
+ cleanup_counts_index (1);
+ if (function_name_buffer)
+ free (function_name_buffer);
+ return 0;
+}
- /* Scan the insns in the function, count the number of basic blocks
- present. When a code label is passed, set label_to_bb[label] = bb
- number. */
+/* Computes hybrid profile for all matching entries in da_file.
+ Sets max_counter_in_program as a side effect. */
- /* The first block found will be block 1, so that function entry can be
- block 0. */
+static gcov_type *
+get_exec_counts ()
+{
+ unsigned num_edges = 0;
+ basic_block bb;
+ gcov_type *profile;
+ gcov_type max_count;
+ unsigned ix, i, tag, length, num;
+ const char *name = IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (current_function_decl));
+ struct da_index_entry *entry, what;
+ struct section_reference *act;
+ gcov_type count;
+ struct gcov_summary summ;
+
+ profile_info.max_counter_in_program = 0;
+ profile_info.count_profiles_merged = 0;
+
+ /* No .da file, no execution counts. */
+ if (!da_file)
+ return NULL;
+ if (!counts_file_index)
+ abort ();
- {
- register RTX_CODE prev_code = JUMP_INSN;
- register RTX_CODE code;
- register rtx insn;
- register int i;
- int block_separator_emitted = 0;
+ /* Count the edges to be (possibly) instrumented. */
- ignore_next_note = 0;
+ FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
+ {
+ edge e;
+ for (e = bb->succ; e; e = e->succ_next)
+ if (!EDGE_INFO (e)->ignore && !EDGE_INFO (e)->on_tree)
+ num_edges++;
+ }
- for (insn = NEXT_INSN (f), i = 0; insn; insn = NEXT_INSN (insn))
- {
- code = GET_CODE (insn);
-
- if (code == BARRIER)
- ;
- else if (code == CODE_LABEL)
- /* This label is part of the next block, but we can't increment
- block number yet since there might be multiple labels. */
- label_to_bb[CODE_LABEL_NUMBER (insn)] = i + 1;
- /* We make NOTE_INSN_SETJMP notes into a block of their own, so that
- they can be the target of the fake arc for the setjmp call.
- This avoids creating cycles of fake arcs, which would happen if
- the block after the setjmp call contained a call insn. */
- else if ((prev_code == JUMP_INSN || prev_code == CALL_INSN
- || prev_code == CODE_LABEL || prev_code == BARRIER)
- && (GET_RTX_CLASS (code) == 'i'
- || (code == NOTE
- && NOTE_LINE_NUMBER (insn) == NOTE_INSN_SETJMP)))
- {
- i += 1;
+ /* now read and combine all matching profiles. */
- /* Emit the block separator if it hasn't already been emitted. */
- if (flag_test_coverage && ! block_separator_emitted)
- {
- /* Output a zero to the .bb file to indicate that a new
- block list is starting. */
- __write_long (0, bb_file, 4);
- }
- block_separator_emitted = 0;
- }
- /* If flag_test_coverage is true, then we must add an entry to the
- .bb file for every note. */
- else if (code == NOTE && flag_test_coverage)
- {
- /* Must ignore the line number notes that immediately follow the
- end of an inline function to avoid counting it twice. There
- is a note before the call, and one after the call. */
- if (NOTE_LINE_NUMBER (insn) == NOTE_REPEATED_LINE_NUMBER)
- ignore_next_note = 1;
- else if (NOTE_LINE_NUMBER (insn) > 0)
- {
- if (ignore_next_note)
- ignore_next_note = 0;
- else
- {
- /* Emit a block separator here to ensure that a NOTE
- immediately following a JUMP_INSN or CALL_INSN will end
- up in the right basic block list. */
- if ((prev_code == JUMP_INSN || prev_code == CALL_INSN
- || prev_code == CODE_LABEL || prev_code == BARRIER)
- && ! block_separator_emitted)
- {
- /* Output a zero to the .bb file to indicate that
- a new block list is starting. */
- __write_long (0, bb_file, 4);
+ profile = xmalloc (sizeof (gcov_type) * num_edges);
- block_separator_emitted = 1;
- }
-
- /* If this is a new source file, then output the file's
- name to the .bb file. */
- if (! last_bb_file_name
- || strcmp (NOTE_SOURCE_FILE (insn),
- last_bb_file_name))
- {
- if (last_bb_file_name)
- free (last_bb_file_name);
- last_bb_file_name = xstrdup (NOTE_SOURCE_FILE (insn));
- output_gcov_string (NOTE_SOURCE_FILE (insn), (long)-1);
- }
+ for (ix = 0; ix < num_edges; ix++)
+ profile[ix] = 0;
- /* Output the line number to the .bb file. Must be done
- after the output_bb_profile_data() call, and after the
- file name is written, to ensure that it is correctly
- handled by gcov. */
- __write_long (NOTE_LINE_NUMBER (insn), bb_file, 4);
- }
- }
- }
+ what.function_name = (char *) name;
+ what.section = GCOV_TAG_ARC_COUNTS;
+ entry = htab_find (counts_file_index, &what);
+ if (!entry)
+ {
+ warning ("No profile for function '%s' found.", name);
+ goto cleanup;
+ }
+
+ if (entry->checksum != profile_info.current_function_cfg_checksum)
+ {
+ warning ("profile mismatch for `%s'", current_function_name);
+ goto cleanup;
+ }
- if (code != NOTE)
- prev_code = code;
- else if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_SETJMP)
- prev_code = CALL_INSN;
- }
+ for (i = 0; i < entry->n_offsets; i++)
+ {
+ act = entry->offsets + i;
- /* Allocate last `normal' entry for bb_graph. */
+ /* Read arc counters. */
+ max_count = 0;
+ gcov_resync (da_file, act->offset, 0);
- /* The last insn was a jump, call, or label. In that case we have
- a block at the end of the function with no insns. */
- if (prev_code == JUMP_INSN || prev_code == CALL_INSN
- || prev_code == CODE_LABEL || prev_code == BARRIER)
- {
- i++;
+ if (gcov_read_unsigned (da_file, &tag)
+ || gcov_read_unsigned (da_file, &length)
+ || tag != GCOV_TAG_ARC_COUNTS)
+ {
+ /* We have already passed through file, so any error means
+ something is rotten. */
+ abort ();
+ }
+ num = length / 8;
- /* Emit the block separator if it hasn't already been emitted. */
- if (flag_test_coverage && ! block_separator_emitted)
- {
- /* Output a zero to the .bb file to indicate that a new
- block list is starting. */
- __write_long (0, bb_file, 4);
- }
- }
+ if (num != num_edges)
+ {
+ warning ("profile mismatch for `%s'", current_function_name);
+ goto cleanup;
+ }
+
+ for (ix = 0; ix != num; ix++)
+ {
+ if (gcov_read_counter (da_file, &count))
+ abort ();
+ if (count > max_count)
+ max_count = count;
+ profile[ix] += count;
+ }
- /* Create another block to stand for EXIT, and make all return insns, and
- the last basic block point here. Add one more to account for block
- zero. */
- num_blocks = i + 2;
- }
+ /* Read program summary. */
+ if (*act->summary != -1)
+ {
+ gcov_resync (da_file, *act->summary, 0);
+ if (gcov_read_unsigned (da_file, &tag)
+ || gcov_read_unsigned (da_file, &length)
+ || tag != GCOV_TAG_PROGRAM_SUMMARY
+ || gcov_read_summary (da_file, &summ))
+ abort ();
+ profile_info.count_profiles_merged += summ.runs;
+ profile_info.max_counter_in_program += summ.arc_sum_max;
+ }
+ else
+ summ.runs = 0;
+ if (!summ.runs)
+ {
+ profile_info.count_profiles_merged++;
+ profile_info.max_counter_in_program += max_count;
+ }
+ }
- total_num_blocks += num_blocks;
- if (dump_file)
- fprintf (dump_file, "%d basic blocks\n", num_blocks);
+ if (rtl_dump_file)
+ {
+ fprintf(rtl_dump_file, "Merged %i profiles with maximal count %i.\n",
+ profile_info.count_profiles_merged,
+ (int)profile_info.max_counter_in_program);
+ }
- /* If we are only doing test coverage here, then return now. */
- if (! profile_arc_flag && ! flag_branch_probabilities)
- return;
+ return profile;
- /* Create and initialize the arrays that will hold bb_graph
- and execution count info. */
+cleanup:;
+ free (profile);
+ cleanup_counts_index (1);
+ return NULL;
+}
+\f
- bb_graph = (struct bb_info *) alloca (num_blocks * sizeof (struct bb_info));
- bzero ((char *) bb_graph, (sizeof (struct bb_info) * num_blocks));
+/* Compute the branch probabilities for the various branches.
+ Annotate them accordingly. */
- {
- /* Scan the insns again:
- - at the entry to each basic block, increment the predecessor count
- (and successor of previous block) if it is a fall through entry,
- create adj_list entries for this and the previous block
- - at each jump insn, increment predecessor/successor counts for
- target/source basic blocks, add this insn to pred/succ lists.
-
- This also cannot be broken out as a separate subroutine
- because it uses `alloca'. */
-
- register RTX_CODE prev_code = JUMP_INSN;
- register RTX_CODE code;
- register rtx insn;
- register int i;
- int fall_through = 0;
- struct adj_list *arcptr;
- int dest = 0;
-
- /* Block 0 always falls through to block 1. */
- num_arcs = 0;
- arcptr = (struct adj_list *) alloca (sizeof (struct adj_list));
- init_arc (arcptr, 0, 1, 0);
- arcptr->fall_through = 1;
- num_arcs++;
-
- /* Add a fake fall through arc from the last block to block 0, to make the
- graph complete. */
- arcptr = (struct adj_list *) alloca (sizeof (struct adj_list));
- init_arc (arcptr, num_blocks - 1, 0, 0);
- arcptr->fake = 1;
- num_arcs++;
-
- /* Exit must be one node of the graph, and all exits from the function
- must point there. When see a return branch, must point the arc to the
- exit node. */
-
- /* Must start scan with second insn in function as above. */
- for (insn = NEXT_INSN (f), i = 0; insn; insn = NEXT_INSN (insn))
- {
- code = GET_CODE (insn);
-
- if (code == BARRIER)
- fall_through = 0;
- else if (code == CODE_LABEL)
- ;
- /* We make NOTE_INSN_SETJMP notes into a block of their own, so that
- they can be the target of the fake arc for the setjmp call.
- This avoids creating cycles of fake arcs, which would happen if
- the block after the setjmp call ended with a call. */
- else if ((prev_code == JUMP_INSN || prev_code == CALL_INSN
- || prev_code == CODE_LABEL || prev_code == BARRIER)
- && (GET_RTX_CLASS (code) == 'i'
- || (code == NOTE
- && NOTE_LINE_NUMBER (insn) == NOTE_INSN_SETJMP)))
- {
- /* This is the first insn of the block. */
- i += 1;
- if (fall_through)
- {
- arcptr = (struct adj_list *) alloca (sizeof (struct adj_list));
- init_arc (arcptr, i - 1, i, 0);
- arcptr->fall_through = 1;
+static void
+compute_branch_probabilities ()
+{
+ basic_block bb;
+ int i;
+ int num_edges = 0;
+ int changes;
+ int passes;
+ int hist_br_prob[20];
+ int num_never_executed;
+ int num_branches;
+ gcov_type *exec_counts = get_exec_counts ();
+ int exec_counts_pos = 0;
+
+ /* Attach extra info block to each bb. */
+
+ alloc_aux_for_blocks (sizeof (struct bb_info));
+ FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
+ {
+ edge e;
+
+ for (e = bb->succ; e; e = e->succ_next)
+ if (!EDGE_INFO (e)->ignore)
+ BB_INFO (bb)->succ_count++;
+ for (e = bb->pred; e; e = e->pred_next)
+ if (!EDGE_INFO (e)->ignore)
+ BB_INFO (bb)->pred_count++;
+ }
- num_arcs++;
- }
- fall_through = 1;
- bb_graph[i].first_insn = insn;
- }
- else if (code == NOTE)
- {;}
+ /* Avoid predicting entry on exit nodes. */
+ BB_INFO (EXIT_BLOCK_PTR)->succ_count = 2;
+ BB_INFO (ENTRY_BLOCK_PTR)->pred_count = 2;
- if (code == CALL_INSN)
- {
- /* In the normal case, the call returns, and this is just like
- a branch fall through. */
- fall_through = 1;
-
- /* Setjmp may return more times than called, so to make the graph
- solvable, add a fake arc from the function entrance to the
- next block.
-
- All other functions may return fewer times than called (if
- a descendent call longjmp or exit), so to make the graph
- solvable, add a fake arc to the function exit from the
- current block.
-
- Distinguish the cases by checking for a SETJUMP note.
- A call_insn can be the last ins of a function, so must check
- to see if next insn actually exists. */
- arcptr = (struct adj_list *) alloca (sizeof (struct adj_list));
- if (NEXT_INSN (insn)
- && GET_CODE (NEXT_INSN (insn)) == NOTE
- && NOTE_LINE_NUMBER (NEXT_INSN (insn)) == NOTE_INSN_SETJMP)
- init_arc (arcptr, 0, i+1, insn);
- else
- init_arc (arcptr, i, num_blocks-1, insn);
- arcptr->fake = 1;
- num_arcs++;
- }
- else if (code == JUMP_INSN)
+ /* For each edge not on the spanning tree, set its execution count from
+ the .da file. */
+
+ /* The first count in the .da file is the number of times that the function
+ was entered. This is the exec_count for block zero. */
+
+ FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
+ {
+ edge e;
+ for (e = bb->succ; e; e = e->succ_next)
+ if (!EDGE_INFO (e)->ignore && !EDGE_INFO (e)->on_tree)
{
- rtx tem, pattern = PATTERN (insn);
- rtx tablejump = 0;
-
- /* If running without optimization, then jump label won't be valid,
- so we must search for the destination label in that case.
- We have to handle tablejumps and returns specially anyways, so
- we don't check the JUMP_LABEL at all here. */
-
- /* ??? This code should be rewritten. We need a more elegant way
- to find the LABEL_REF. We need a more elegant way to
- differentiate tablejump entries from computed gotos.
- We should perhaps reuse code from flow to compute the CFG
- instead of trying to compute it here.
-
- We can't use current_function_has_computed_jump, because that
- is calculated later by flow. We can't use computed_jump_p,
- because that returns true for tablejump entry insns for some
- targets, e.g. HPPA and MIPS. */
-
- if (GET_CODE (pattern) == PARALLEL)
+ num_edges++;
+ if (exec_counts)
{
- /* This assumes that PARALLEL jumps with a USE are
- tablejump entry jumps. The same assumption can be found
- in computed_jump_p. */
- /* Make an arc from this jump to the label of the
- jump table. This will instrument the number of
- times the switch statement is executed. */
- if (GET_CODE (XVECEXP (pattern, 0, 1)) == USE)
- {
- tem = XEXP (XVECEXP (pattern, 0, 1), 0);
- if (GET_CODE (tem) != LABEL_REF)
- abort ();
- dest = label_to_bb[CODE_LABEL_NUMBER (XEXP (tem, 0))];
- }
- else if (GET_CODE (XVECEXP (pattern, 0, 0)) == SET
- && SET_DEST (XVECEXP (pattern, 0, 0)) == pc_rtx)
- {
- tem = SET_SRC (XVECEXP (pattern, 0, 0));
- if (GET_CODE (tem) == PLUS
- && GET_CODE (XEXP (tem, 1)) == LABEL_REF)
- {
- tem = XEXP (tem, 1);
- dest = label_to_bb [CODE_LABEL_NUMBER (XEXP (tem, 0))];
- }
- }
- else
- abort ();
+ e->count = exec_counts[exec_counts_pos++];
}
- else if (GET_CODE (pattern) == ADDR_VEC
- || GET_CODE (pattern) == ADDR_DIFF_VEC)
- tablejump = pattern;
- else if (GET_CODE (pattern) == RETURN)
- dest = num_blocks - 1;
- else if (GET_CODE (pattern) != SET)
- abort ();
- else if ((tem = SET_SRC (pattern))
- && GET_CODE (tem) == LABEL_REF)
- dest = label_to_bb[CODE_LABEL_NUMBER (XEXP (tem, 0))];
- /* Recognize HPPA table jump entry. This code is similar to
- the code above in the PARALLEL case. */
- else if (GET_CODE (tem) == PLUS
- && GET_CODE (XEXP (tem, 0)) == MEM
- && GET_CODE (XEXP (XEXP (tem, 0), 0)) == PLUS
- && GET_CODE (XEXP (XEXP (XEXP (tem, 0), 0), 0)) == PC
- && GET_CODE (XEXP (tem, 1)) == LABEL_REF
- && tablejump_entry_p (insn, XEXP (tem, 1)))
- dest = label_to_bb[CODE_LABEL_NUMBER (XEXP (XEXP (tem, 1), 0))];
- /* Recognize the MIPS table jump entry. */
- else if (GET_CODE (tem) == PLUS
- && GET_CODE (XEXP (tem, 0)) == REG
- && GET_CODE (XEXP (tem, 1)) == LABEL_REF
- && tablejump_entry_p (insn, XEXP (tem, 1)))
- dest = label_to_bb[CODE_LABEL_NUMBER (XEXP (XEXP (tem, 1), 0))];
else
+ e->count = 0;
+
+ EDGE_INFO (e)->count_valid = 1;
+ BB_INFO (bb)->succ_count--;
+ BB_INFO (e->dest)->pred_count--;
+ if (rtl_dump_file)
{
- rtx label_ref;
-
- /* Must be an IF_THEN_ELSE branch. If it isn't, assume it
- is a computed goto, which aren't supported yet. */
- if (GET_CODE (tem) != IF_THEN_ELSE)
- fatal ("-fprofile-arcs does not support computed gotos");
- if (XEXP (tem, 1) != pc_rtx)
- label_ref = XEXP (tem, 1);
- else
- label_ref = XEXP (tem, 2);
- dest = label_to_bb[CODE_LABEL_NUMBER (XEXP (label_ref, 0))];
+ fprintf (rtl_dump_file, "\nRead edge from %i to %i, count:",
+ bb->index, e->dest->index);
+ fprintf (rtl_dump_file, HOST_WIDEST_INT_PRINT_DEC,
+ (HOST_WIDEST_INT) e->count);
}
+ }
+ }
- if (tablejump)
- {
- int diff_vec_p = GET_CODE (tablejump) == ADDR_DIFF_VEC;
- int len = XVECLEN (tablejump, diff_vec_p);
- int k;
+ if (rtl_dump_file)
+ fprintf (rtl_dump_file, "\n%d edge counts read\n", num_edges);
- for (k = 0; k < len; k++)
- {
- rtx tem = XEXP (XVECEXP (tablejump, diff_vec_p, k), 0);
- dest = label_to_bb[CODE_LABEL_NUMBER (tem)];
+ /* For every block in the file,
+ - if every exit/entrance edge has a known count, then set the block count
+ - if the block count is known, and every exit/entrance edge but one has
+ a known execution count, then set the count of the remaining edge
- arcptr = (struct adj_list *) alloca (sizeof(struct adj_list));
- init_arc (arcptr, i, dest, insn);
+ As edge counts are set, decrement the succ/pred count, but don't delete
+ the edge, that way we can easily tell when all edges are known, or only
+ one edge is unknown. */
- num_arcs++;
- }
- }
- else
- {
- arcptr = (struct adj_list *) alloca (sizeof (struct adj_list));
- init_arc (arcptr, i, dest, insn);
+ /* The order that the basic blocks are iterated through is important.
+ Since the code that finds spanning trees starts with block 0, low numbered
+ edges are put on the spanning tree in preference to high numbered edges.
+ Hence, most instrumented edges are at the end. Graph solving works much
+ faster if we propagate numbers from the end to the start.
- num_arcs++;
- }
+ This takes an average of slightly more than 3 passes. */
- /* Determine whether or not this jump will fall through.
- Unconditional jumps and returns are not always followed by
- barriers. */
- pattern = PATTERN (insn);
- if (GET_CODE (pattern) == PARALLEL
- || GET_CODE (pattern) == RETURN)
- fall_through = 0;
- else if (GET_CODE (pattern) == ADDR_VEC
- || GET_CODE (pattern) == ADDR_DIFF_VEC)
- /* These aren't actually jump insns, but they never fall
- through, so... */
- fall_through = 0;
- else
- {
- if (GET_CODE (pattern) != SET || SET_DEST (pattern) != pc_rtx)
- abort ();
- if (GET_CODE (SET_SRC (pattern)) != IF_THEN_ELSE)
- fall_through = 0;
- }
- }
+ changes = 1;
+ passes = 0;
+ while (changes)
+ {
+ passes++;
+ changes = 0;
+ FOR_BB_BETWEEN (bb, EXIT_BLOCK_PTR, NULL, prev_bb)
+ {
+ struct bb_info *bi = BB_INFO (bb);
+ if (! bi->count_valid)
+ {
+ if (bi->succ_count == 0)
+ {
+ edge e;
+ gcov_type total = 0;
- if (code != NOTE)
- prev_code = code;
- else if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_SETJMP)
- {
- /* Make a fake insn to tag our notes on. */
- bb_graph[i].first_insn = insn
- = emit_insn_after (gen_rtx_USE (VOIDmode, stack_pointer_rtx),
- insn);
- prev_code = CALL_INSN;
- }
- }
+ for (e = bb->succ; e; e = e->succ_next)
+ total += e->count;
+ bb->count = total;
+ bi->count_valid = 1;
+ changes = 1;
+ }
+ else if (bi->pred_count == 0)
+ {
+ edge e;
+ gcov_type total = 0;
- /* If the code at the end of the function would give a new block, then
- do the following. */
+ for (e = bb->pred; e; e = e->pred_next)
+ total += e->count;
+ bb->count = total;
+ bi->count_valid = 1;
+ changes = 1;
+ }
+ }
+ if (bi->count_valid)
+ {
+ if (bi->succ_count == 1)
+ {
+ edge e;
+ gcov_type total = 0;
- if (prev_code == JUMP_INSN || prev_code == CALL_INSN
- || prev_code == CODE_LABEL || prev_code == BARRIER)
- {
- if (fall_through)
- {
- arcptr = (struct adj_list *) alloca (sizeof (struct adj_list));
- init_arc (arcptr, i, i + 1, 0);
- arcptr->fall_through = 1;
+ /* One of the counts will be invalid, but it is zero,
+ so adding it in also doesn't hurt. */
+ for (e = bb->succ; e; e = e->succ_next)
+ total += e->count;
- num_arcs++;
- }
-
- /* This may not be a real insn, but that should not cause a problem. */
- bb_graph[i+1].first_insn = get_last_insn ();
- }
+ /* Seedgeh for the invalid edge, and set its count. */
+ for (e = bb->succ; e; e = e->succ_next)
+ if (! EDGE_INFO (e)->count_valid && ! EDGE_INFO (e)->ignore)
+ break;
- /* There is always a fake arc from the last block of the function
- to the function exit block. */
- arcptr = (struct adj_list *) alloca (sizeof (struct adj_list));
- init_arc (arcptr, num_blocks-2, num_blocks-1, 0);
- arcptr->fake = 1;
- num_arcs++;
- }
+ /* Calculate count for remaining edge by conservation. */
+ total = bb->count - total;
+
+ if (! e)
+ abort ();
+ EDGE_INFO (e)->count_valid = 1;
+ e->count = total;
+ bi->succ_count--;
+
+ BB_INFO (e->dest)->pred_count--;
+ changes = 1;
+ }
+ if (bi->pred_count == 1)
+ {
+ edge e;
+ gcov_type total = 0;
- total_num_arcs += num_arcs;
- if (dump_file)
- fprintf (dump_file, "%d arcs\n", num_arcs);
+ /* One of the counts will be invalid, but it is zero,
+ so adding it in also doesn't hurt. */
+ for (e = bb->pred; e; e = e->pred_next)
+ total += e->count;
- /* Create spanning tree from basic block graph, mark each arc that is
- on the spanning tree. */
+ /* Seedgeh for the invalid edge, and set its count. */
+ for (e = bb->pred; e; e = e->pred_next)
+ if (! EDGE_INFO (e)->count_valid && ! EDGE_INFO (e)->ignore)
+ break;
- /* To reduce the instrumentation cost, make two passes over the tree.
- First, put as many must-split (crowded and fake) arcs on the tree as
- possible, then on the second pass fill in the rest of the tree.
- Note that the spanning tree is considered undirected, so that as many
- must-split arcs as possible can be put on it.
+ /* Calculate count for remaining edge by conservation. */
+ total = bb->count - total + e->count;
- Fallthrough arcs which are crowded should not be chosen on the first
- pass, since they do not require creating a new basic block. These
- arcs will have fall_through set. */
+ if (! e)
+ abort ();
+ EDGE_INFO (e)->count_valid = 1;
+ e->count = total;
+ bi->pred_count--;
- find_spanning_tree (num_blocks);
+ BB_INFO (e->src)->succ_count--;
+ changes = 1;
+ }
+ }
+ }
+ }
+ if (rtl_dump_file)
+ dump_flow_info (rtl_dump_file);
- /* Create a .bbg file from which gcov can reconstruct the basic block
- graph. First output the number of basic blocks, and then for every
- arc output the source and target basic block numbers.
- NOTE: The format of this file must be compatible with gcov. */
+ total_num_passes += passes;
+ if (rtl_dump_file)
+ fprintf (rtl_dump_file, "Graph solving took %d passes.\n\n", passes);
- if (flag_test_coverage)
+ /* If the graph has been correctly solved, every block will have a
+ succ and pred count of zero. */
+ FOR_EACH_BB (bb)
{
- int flag_bits;
+ if (BB_INFO (bb)->succ_count || BB_INFO (bb)->pred_count)
+ abort ();
+ }
- __write_long (num_blocks, bbg_file, 4);
- __write_long (num_arcs, bbg_file, 4);
+ /* For every edge, calculate its branch probability and add a reg_note
+ to the branch insn to indicate this. */
- for (i = 0; i < num_blocks; i++)
- {
- long count = 0;
- for (arcptr = bb_graph[i].succ; arcptr; arcptr = arcptr->succ_next)
- count++;
- __write_long (count, bbg_file, 4);
+ for (i = 0; i < 20; i++)
+ hist_br_prob[i] = 0;
+ num_never_executed = 0;
+ num_branches = 0;
+
+ FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
+ {
+ edge e;
+ gcov_type total;
+ rtx note;
- for (arcptr = bb_graph[i].succ; arcptr; arcptr = arcptr->succ_next)
+ total = bb->count;
+ if (total)
+ {
+ for (e = bb->succ; e; e = e->succ_next)
+ {
+ e->probability = (e->count * REG_BR_PROB_BASE + total / 2) / total;
+ if (e->probability < 0 || e->probability > REG_BR_PROB_BASE)
+ {
+ error ("corrupted profile info: prob for %d-%d thought to be %d",
+ e->src->index, e->dest->index, e->probability);
+ e->probability = REG_BR_PROB_BASE / 2;
+ }
+ }
+ if (bb->index >= 0
+ && any_condjump_p (bb->end)
+ && bb->succ->succ_next)
{
- flag_bits = 0;
- if (arcptr->on_tree)
- flag_bits |= 0x1;
- if (arcptr->fake)
- flag_bits |= 0x2;
- if (arcptr->fall_through)
- flag_bits |= 0x4;
-
- __write_long (ARC_TARGET (arcptr), bbg_file, 4);
- __write_long (flag_bits, bbg_file, 4);
+ int prob;
+ edge e;
+ int index;
+
+ /* Find the branch edge. It is possible that we do have fake
+ edges here. */
+ for (e = bb->succ; e->flags & (EDGE_FAKE | EDGE_FALLTHRU);
+ e = e->succ_next)
+ continue; /* Loop body has been intentionally left blank. */
+
+ prob = e->probability;
+ index = prob * 20 / REG_BR_PROB_BASE;
+
+ if (index == 20)
+ index = 19;
+ hist_br_prob[index]++;
+
+ note = find_reg_note (bb->end, REG_BR_PROB, 0);
+ /* There may be already note put by some other pass, such
+ as builtin_expect expander. */
+ if (note)
+ XEXP (note, 0) = GEN_INT (prob);
+ else
+ REG_NOTES (bb->end)
+ = gen_rtx_EXPR_LIST (REG_BR_PROB, GEN_INT (prob),
+ REG_NOTES (bb->end));
+ num_branches++;
}
}
-
- /* Emit a -1 to separate the list of all arcs from the list of
- loop back edges that follows. */
- __write_long (-1, bbg_file, 4);
+ /* Otherwise distribute the probabilities evenly so we get sane
+ sum. Use simple heuristics that if there are normal edges,
+ give all abnormals frequency of 0, otherwise distribute the
+ frequency over abnormals (this is the case of noreturn
+ calls). */
+ else
+ {
+ for (e = bb->succ; e; e = e->succ_next)
+ if (!(e->flags & (EDGE_COMPLEX | EDGE_FAKE)))
+ total ++;
+ if (total)
+ {
+ for (e = bb->succ; e; e = e->succ_next)
+ if (!(e->flags & (EDGE_COMPLEX | EDGE_FAKE)))
+ e->probability = REG_BR_PROB_BASE / total;
+ else
+ e->probability = 0;
+ }
+ else
+ {
+ for (e = bb->succ; e; e = e->succ_next)
+ total ++;
+ for (e = bb->succ; e; e = e->succ_next)
+ e->probability = REG_BR_PROB_BASE / total;
+ }
+ if (bb->index >= 0
+ && any_condjump_p (bb->end)
+ && bb->succ->succ_next)
+ num_branches++, num_never_executed;
+ }
}
- /* For each arc not on the spanning tree, add counting code as rtl. */
-
- if (profile_arc_flag)
+ if (rtl_dump_file)
{
- instrument_arcs (f, num_blocks, dump_file);
- allocate_reg_info (max_reg_num (), FALSE, FALSE);
- }
+ fprintf (rtl_dump_file, "%d branches\n", num_branches);
+ fprintf (rtl_dump_file, "%d branches never executed\n",
+ num_never_executed);
+ if (num_branches)
+ for (i = 0; i < 10; i++)
+ fprintf (rtl_dump_file, "%d%% branches in range %d-%d%%\n",
+ (hist_br_prob[i] + hist_br_prob[19-i]) * 100 / num_branches,
+ 5 * i, 5 * i + 5);
- /* Execute the rest only if doing branch probabilities. */
- if (! flag_branch_probabilities)
- return;
+ total_num_branches += num_branches;
+ total_num_never_executed += num_never_executed;
+ for (i = 0; i < 20; i++)
+ total_hist_br_prob[i] += hist_br_prob[i];
- /* For each arc not on the spanning tree, set its execution count from
- the .da file. */
+ fputc ('\n', rtl_dump_file);
+ fputc ('\n', rtl_dump_file);
+ }
- /* The first count in the .da file is the number of times that the function
- was entered. This is the exec_count for block zero. */
+ free_aux_for_blocks ();
+ if (exec_counts)
+ free (exec_counts);
+}
+
+/* Compute checksum for the current function. We generate a CRC32. */
- num_arcs = 0;
- for (i = 0; i < num_blocks; i++)
- for (arcptr = bb_graph[i].succ; arcptr; arcptr = arcptr->succ_next)
- if (! arcptr->on_tree)
+static unsigned
+compute_checksum ()
+{
+ unsigned chksum = 0;
+ basic_block bb;
+
+ FOR_EACH_BB (bb)
+ {
+ edge e = NULL;
+
+ do
{
- num_arcs++;
- if (da_file)
+ unsigned value = BB_TO_GCOV_INDEX (e ? e->dest : bb);
+ unsigned ix;
+
+ /* No need to use all bits in value identically, nearly all
+ functions have less than 256 blocks. */
+ value ^= value << 16;
+ value ^= value << 8;
+
+ for (ix = 8; ix--; value <<= 1)
{
- long value;
- __read_long (&value, da_file, 8);
- ARC_COUNT (arcptr) = value;
+ unsigned feedback;
+
+ feedback = (value ^ chksum) & 0x80000000 ? 0x04c11db7 : 0;
+ chksum <<= 1;
+ chksum ^= feedback;
}
- else
- ARC_COUNT (arcptr) = 0;
- arcptr->count_valid = 1;
- bb_graph[i].succ_count--;
- bb_graph[ARC_TARGET (arcptr)].pred_count--;
+
+ e = e ? e->succ_next : bb->succ;
}
+ while (e);
+ }
+
+ return chksum;
+}
+
+/* Instrument and/or analyze program behavior based on program flow graph.
+ In either case, this function builds a flow graph for the function being
+ compiled. The flow graph is stored in BB_GRAPH.
+
+ When FLAG_PROFILE_ARCS is nonzero, this function instruments the edges in
+ the flow graph that are needed to reconstruct the dynamic behavior of the
+ flow graph.
+
+ When FLAG_BRANCH_PROBABILITIES is nonzero, this function reads auxiliary
+ information from a data file containing edge count information from previous
+ executions of the function being compiled. In this case, the flow graph is
+ annotated with actual execution counts, which are later propagated into the
+ rtl for optimization purposes.
+
+ Main entry point of this file. */
+
+void
+branch_prob ()
+{
+ basic_block bb;
+ int i;
+ int num_edges, ignored_edges;
+ struct edge_list *el;
+ const char *name = IDENTIFIER_POINTER
+ (DECL_ASSEMBLER_NAME (current_function_decl));
+
+ profile_info.current_function_cfg_checksum = compute_checksum ();
- if (dump_file)
- fprintf (dump_file, "%d arc counts read\n", num_arcs);
+ if (rtl_dump_file)
+ fprintf (rtl_dump_file, "CFG checksum is %u\n",
+ profile_info.current_function_cfg_checksum);
- /* For every block in the file,
- - if every exit/entrance arc has a known count, then set the block count
- - if the block count is known, and every exit/entrance arc but one has
- a known execution count, then set the count of the remaining arc
+ total_num_times_called++;
- As arc counts are set, decrement the succ/pred count, but don't delete
- the arc, that way we can easily tell when all arcs are known, or only
- one arc is unknown. */
+ flow_call_edges_add (NULL);
+ add_noreturn_fake_exit_edges ();
- /* The order that the basic blocks are iterated through is important.
- Since the code that finds spanning trees starts with block 0, low numbered
- arcs are put on the spanning tree in preference to high numbered arcs.
- Hence, most instrumented arcs are at the end. Graph solving works much
- faster if we propagate numbers from the end to the start.
-
- This takes an average of slightly more than 3 passes. */
+ /* We can't handle cyclic regions constructed using abnormal edges.
+ To avoid these we replace every source of abnormal edge by a fake
+ edge from entry node and every destination by fake edge to exit.
+ This keeps graph acyclic and our calculation exact for all normal
+ edges except for exit and entrance ones.
- changes = 1;
- passes = 0;
- while (changes)
- {
- passes++;
- changes = 0;
+ We also add fake exit edges for each call and asm statement in the
+ basic, since it may not return. */
- for (i = num_blocks - 1; i >= 0; i--)
+ FOR_EACH_BB (bb)
+ {
+ int need_exit_edge = 0, need_entry_edge = 0;
+ int have_exit_edge = 0, have_entry_edge = 0;
+ rtx insn;
+ edge e;
+
+ /* Add fake edges from entry block to the call insns that may return
+ twice. The CFG is not quite correct then, as call insn plays more
+ role of CODE_LABEL, but for our purposes, everything should be OK,
+ as we never insert code to the beggining of basic block. */
+ for (insn = bb->head; insn != NEXT_INSN (bb->end);
+ insn = NEXT_INSN (insn))
{
- struct bb_info *binfo = &bb_graph[i];
- if (! binfo->count_valid)
- {
- if (binfo->succ_count == 0)
- {
- total = 0;
- for (arcptr = binfo->succ; arcptr;
- arcptr = arcptr->succ_next)
- total += ARC_COUNT (arcptr);
- binfo->exec_count = total;
- binfo->count_valid = 1;
- changes = 1;
- }
- else if (binfo->pred_count == 0)
- {
- total = 0;
- for (arcptr = binfo->pred; arcptr;
- arcptr = arcptr->pred_next)
- total += ARC_COUNT (arcptr);
- binfo->exec_count = total;
- binfo->count_valid = 1;
- changes = 1;
- }
- }
- if (binfo->count_valid)
+ if (GET_CODE (insn) == CALL_INSN
+ && find_reg_note (insn, REG_SETJMP, NULL))
{
- if (binfo->succ_count == 1)
+ if (GET_CODE (bb->head) == CODE_LABEL
+ || insn != NEXT_INSN (bb->head))
{
- total = 0;
- /* One of the counts will be invalid, but it is zero,
- so adding it in also doesn't hurt. */
- for (arcptr = binfo->succ; arcptr;
- arcptr = arcptr->succ_next)
- total += ARC_COUNT (arcptr);
- /* Calculate count for remaining arc by conservation. */
- total = binfo->exec_count - total;
- /* Search for the invalid arc, and set its count. */
- for (arcptr = binfo->succ; arcptr;
- arcptr = arcptr->succ_next)
- if (! arcptr->count_valid)
- break;
- if (! arcptr)
- abort ();
- arcptr->count_valid = 1;
- ARC_COUNT (arcptr) = total;
- binfo->succ_count--;
-
- bb_graph[ARC_TARGET (arcptr)].pred_count--;
- changes = 1;
+ e = split_block (bb, PREV_INSN (insn));
+ make_edge (ENTRY_BLOCK_PTR, e->dest, EDGE_FAKE);
+ break;
}
- if (binfo->pred_count == 1)
+ else
{
- total = 0;
- /* One of the counts will be invalid, but it is zero,
- so adding it in also doesn't hurt. */
- for (arcptr = binfo->pred; arcptr;
- arcptr = arcptr->pred_next)
- total += ARC_COUNT (arcptr);
- /* Calculate count for remaining arc by conservation. */
- total = binfo->exec_count - total;
- /* Search for the invalid arc, and set its count. */
- for (arcptr = binfo->pred; arcptr;
- arcptr = arcptr->pred_next)
- if (! arcptr->count_valid)
- break;
- if (! arcptr)
+ /* We should not get abort here, as call to setjmp should not
+ be the very first instruction of function. */
+ if (bb == ENTRY_BLOCK_PTR)
abort ();
- arcptr->count_valid = 1;
- ARC_COUNT (arcptr) = total;
- binfo->pred_count--;
-
- bb_graph[ARC_SOURCE (arcptr)].succ_count--;
- changes = 1;
+ make_edge (ENTRY_BLOCK_PTR, bb, EDGE_FAKE);
}
}
}
- }
- total_num_passes += passes;
- if (dump_file)
- fprintf (dump_file, "Graph solving took %d passes.\n\n", passes);
+ for (e = bb->succ; e; e = e->succ_next)
+ {
+ if ((e->flags & (EDGE_ABNORMAL | EDGE_ABNORMAL_CALL))
+ && e->dest != EXIT_BLOCK_PTR)
+ need_exit_edge = 1;
+ if (e->dest == EXIT_BLOCK_PTR)
+ have_exit_edge = 1;
+ }
+ for (e = bb->pred; e; e = e->pred_next)
+ {
+ if ((e->flags & (EDGE_ABNORMAL | EDGE_ABNORMAL_CALL))
+ && e->src != ENTRY_BLOCK_PTR)
+ need_entry_edge = 1;
+ if (e->src == ENTRY_BLOCK_PTR)
+ have_entry_edge = 1;
+ }
- /* If the graph has been correctly solved, every block will have a
- succ and pred count of zero. */
- for (i = 0; i < num_blocks; i++)
- {
- struct bb_info *binfo = &bb_graph[i];
- if (binfo->succ_count || binfo->pred_count)
- abort ();
+ if (need_exit_edge && !have_exit_edge)
+ {
+ if (rtl_dump_file)
+ fprintf (rtl_dump_file, "Adding fake exit edge to bb %i\n",
+ bb->index);
+ make_edge (bb, EXIT_BLOCK_PTR, EDGE_FAKE);
+ }
+ if (need_entry_edge && !have_entry_edge)
+ {
+ if (rtl_dump_file)
+ fprintf (rtl_dump_file, "Adding fake entry edge to bb %i\n",
+ bb->index);
+ make_edge (ENTRY_BLOCK_PTR, bb, EDGE_FAKE);
+ }
}
- /* For every arc, calculate its branch probability and add a reg_note
- to the branch insn to indicate this. */
+ el = create_edge_list ();
+ num_edges = NUM_EDGES (el);
+ alloc_aux_for_edges (sizeof (struct edge_info));
- for (i = 0; i < 20; i++)
- hist_br_prob[i] = 0;
- num_never_executed = 0;
- num_branches = 0;
+ /* The basic blocks are expected to be numbered sequentially. */
+ compact_blocks ();
- for (i = 0; i < num_blocks; i++)
+ ignored_edges = 0;
+ for (i = 0 ; i < num_edges ; i++)
{
- struct bb_info *binfo = &bb_graph[i];
+ edge e = INDEX_EDGE (el, i);
+ e->count = 0;
- total = binfo->exec_count;
- for (arcptr = binfo->succ; arcptr; arcptr = arcptr->succ_next)
+ /* Mark edges we've replaced by fake edges above as ignored. */
+ if ((e->flags & (EDGE_ABNORMAL | EDGE_ABNORMAL_CALL))
+ && e->src != ENTRY_BLOCK_PTR && e->dest != EXIT_BLOCK_PTR)
{
- if (arcptr->branch_insn)
- {
- /* This calculates the branch probability as an integer between
- 0 and REG_BR_PROB_BASE, properly rounded to the nearest
- integer. Perform the arithmetic in double to avoid
- overflowing the range of ints. */
+ EDGE_INFO (e)->ignore = 1;
+ ignored_edges++;
+ }
+ }
- if (total == 0)
- prob = -1;
- else
- {
- rtx pat = PATTERN (arcptr->branch_insn);
-
- prob = (((double)ARC_COUNT (arcptr) * REG_BR_PROB_BASE)
- + (total >> 1)) / total;
- if (prob < 0 || prob > REG_BR_PROB_BASE)
- {
- if (dump_file)
- fprintf (dump_file, "bad count: prob for %d-%d thought to be %d (forcibly normalized)\n",
- ARC_SOURCE (arcptr), ARC_TARGET (arcptr),
- prob);
+#ifdef ENABLE_CHECKING
+ verify_flow_info ();
+#endif
- bad_counts = 1;
- prob = REG_BR_PROB_BASE / 2;
- }
-
- /* Match up probability with JUMP pattern. */
+ /* Create spanning tree from basic block graph, mark each edge that is
+ on the spanning tree. We insert as many abnormal and critical edges
+ as possible to minimize number of edge splits necessary. */
- if (GET_CODE (pat) == SET
- && GET_CODE (SET_SRC (pat)) == IF_THEN_ELSE)
- {
- if (ARC_TARGET (arcptr) == ARC_SOURCE (arcptr) + 1)
- {
- /* A fall through arc should never have a
- branch insn. */
- abort ();
- }
- else
- {
- /* This is the arc for the taken branch. */
- if (GET_CODE (XEXP (SET_SRC (pat), 2)) != PC)
- prob = REG_BR_PROB_BASE - prob;
- }
- }
- }
-
- if (prob == -1)
- num_never_executed++;
- else
- {
- int index = prob * 20 / REG_BR_PROB_BASE;
- if (index == 20)
- index = 19;
- hist_br_prob[index]++;
- }
- num_branches++;
-
- REG_NOTES (arcptr->branch_insn)
- = gen_rtx_EXPR_LIST (REG_BR_PROB, GEN_INT (prob),
- REG_NOTES (arcptr->branch_insn));
- }
- }
+ find_spanning_tree (el);
- /* Add a REG_EXEC_COUNT note to the first instruction of this block. */
- if (! binfo->first_insn
- || GET_RTX_CLASS (GET_CODE (binfo->first_insn)) != 'i')
- {
- /* Block 0 is a fake block representing function entry, and does
- not have a real first insn. The second last block might not
- begin with a real insn. */
- if (i == num_blocks - 1)
- return_label_execution_count = total;
- else if (i != 0 && i != num_blocks - 2)
- abort ();
- }
- else
+ /* Fake edges that are not on the tree will not be instrumented, so
+ mark them ignored. */
+ for (i = 0; i < num_edges; i++)
+ {
+ edge e = INDEX_EDGE (el, i);
+ struct edge_info *inf = EDGE_INFO (e);
+ if ((e->flags & EDGE_FAKE) && !inf->ignore && !inf->on_tree)
{
- REG_NOTES (binfo->first_insn)
- = gen_rtx_EXPR_LIST (REG_EXEC_COUNT, GEN_INT (total),
- REG_NOTES (binfo->first_insn));
- if (i == num_blocks - 1)
- return_label_execution_count = total;
+ inf->ignore = 1;
+ ignored_edges++;
}
}
-
- /* This should never happen. */
- if (bad_counts)
- warning ("Arc profiling: some arc counts were bad.");
- if (dump_file)
- {
- fprintf (dump_file, "%d branches\n", num_branches);
- fprintf (dump_file, "%d branches never executed\n",
- num_never_executed);
- if (num_branches)
- for (i = 0; i < 10; i++)
- fprintf (dump_file, "%d%% branches in range %d-%d%%\n",
- (hist_br_prob[i]+hist_br_prob[19-i])*100/num_branches,
- 5*i, 5*i+5);
+ total_num_blocks += n_basic_blocks + 2;
+ if (rtl_dump_file)
+ fprintf (rtl_dump_file, "%d basic blocks\n", n_basic_blocks);
- total_num_branches += num_branches;
- total_num_never_executed += num_never_executed;
- for (i = 0; i < 20; i++)
- total_hist_br_prob[i] += hist_br_prob[i];
- }
+ total_num_edges += num_edges;
+ if (rtl_dump_file)
+ fprintf (rtl_dump_file, "%d edges\n", num_edges);
-}
-\f
-/* Initialize a new arc.
- ARCPTR is the empty adj_list this function fills in.
- SOURCE is the block number of the source block.
- TARGET is the block number of the target block.
- INSN is the insn which transfers control from SOURCE to TARGET,
- or zero if the transfer is implicit. */
+ total_num_edges_ignored += ignored_edges;
+ if (rtl_dump_file)
+ fprintf (rtl_dump_file, "%d ignored edges\n", ignored_edges);
-static void
-init_arc (arcptr, source, target, insn)
- struct adj_list *arcptr;
- int source, target;
- rtx insn;
-{
- ARC_TARGET (arcptr) = target;
- ARC_SOURCE (arcptr) = source;
-
- ARC_COUNT (arcptr) = 0;
- arcptr->count_valid = 0;
- arcptr->on_tree = 0;
- arcptr->fake = 0;
- arcptr->fall_through = 0;
- arcptr->branch_insn = insn;
-
- arcptr->succ_next = bb_graph[source].succ;
- bb_graph[source].succ = arcptr;
- bb_graph[source].succ_count++;
-
- arcptr->pred_next = bb_graph[target].pred;
- bb_graph[target].pred = arcptr;
- bb_graph[target].pred_count++;
-}
+ /* Create a .bbg file from which gcov can reconstruct the basic block
+ graph. First output the number of basic blocks, and then for every
+ edge output the source and target basic block numbers.
+ NOTE: The format of this file must be compatible with gcov. */
-/* This function searches all of the arcs in the program flow graph, and puts
- as many bad arcs as possible onto the spanning tree. Bad arcs include
- fake arcs (needed for setjmp(), longjmp(), exit()) which MUST be on the
- spanning tree as they can't be instrumented. Also, arcs which must be
- split when instrumented should be part of the spanning tree if possible. */
+ if (flag_test_coverage && bbg_file)
+ {
+ long offset;
+
+ /* Announce function */
+ if (gcov_write_unsigned (bbg_file, GCOV_TAG_FUNCTION)
+ || !(offset = gcov_reserve_length (bbg_file))
+ || gcov_write_string (bbg_file, name,
+ strlen (name))
+ || gcov_write_unsigned (bbg_file,
+ profile_info.current_function_cfg_checksum)
+ || gcov_write_length (bbg_file, offset))
+ goto bbg_error;
+
+ /* Basic block flags */
+ if (gcov_write_unsigned (bbg_file, GCOV_TAG_BLOCKS)
+ || !(offset = gcov_reserve_length (bbg_file)))
+ goto bbg_error;
+ for (i = 0; i != n_basic_blocks + 2; i++)
+ if (gcov_write_unsigned (bbg_file, 0))
+ goto bbg_error;
+ if (gcov_write_length (bbg_file, offset))
+ goto bbg_error;
+
+ /* Arcs */
+ FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
+ {
+ edge e;
-static void
-find_spanning_tree (num_blocks)
- int num_blocks;
-{
- int i;
- struct adj_list *arcptr;
- struct bb_info *binfo = &bb_graph[0];
+ if (gcov_write_unsigned (bbg_file, GCOV_TAG_ARCS)
+ || !(offset = gcov_reserve_length (bbg_file))
+ || gcov_write_unsigned (bbg_file, BB_TO_GCOV_INDEX (bb)))
+ goto bbg_error;
- /* Fake arcs must be part of the spanning tree, and are always safe to put
- on the spanning tree. Fake arcs will either be a successor of node 0,
- a predecessor of the last node, or from the last node to node 0. */
+ for (e = bb->succ; e; e = e->succ_next)
+ {
+ struct edge_info *i = EDGE_INFO (e);
+ if (!i->ignore)
+ {
+ unsigned flag_bits = 0;
+
+ if (i->on_tree)
+ flag_bits |= GCOV_ARC_ON_TREE;
+ if (e->flags & EDGE_FAKE)
+ flag_bits |= GCOV_ARC_FAKE;
+ if (e->flags & EDGE_FALLTHRU)
+ flag_bits |= GCOV_ARC_FALLTHROUGH;
+
+ if (gcov_write_unsigned (bbg_file,
+ BB_TO_GCOV_INDEX (e->dest))
+ || gcov_write_unsigned (bbg_file, flag_bits))
+ goto bbg_error;
+ }
+ }
+ if (gcov_write_length (bbg_file, offset))
+ goto bbg_error;
+ }
- for (arcptr = bb_graph[0].succ; arcptr; arcptr = arcptr->succ_next)
- if (arcptr->fake)
+ /* Output line number information about each basic block for
+ GCOV utility. */
{
- /* Adding this arc should never cause a cycle. This is a fatal
- error if it would. */
- if (bb_graph[ARC_TARGET (arcptr)].on_tree && binfo->on_tree)
- abort();
- else
+ char const *prev_file_name = NULL;
+
+ FOR_EACH_BB (bb)
{
- arcptr->on_tree = 1;
- bb_graph[ARC_TARGET (arcptr)].on_tree = 1;
- binfo->on_tree = 1;
- }
- }
+ rtx insn = bb->head;
+ int ignore_next_note = 0;
+
+ offset = 0;
+
+ /* We are looking for line number notes. Search backward
+ before basic block to find correct ones. */
+ insn = prev_nonnote_insn (insn);
+ if (!insn)
+ insn = get_insns ();
+ else
+ insn = NEXT_INSN (insn);
- binfo = &bb_graph[num_blocks-1];
- for (arcptr = binfo->pred; arcptr; arcptr = arcptr->pred_next)
- if (arcptr->fake)
- {
- /* Adding this arc should never cause a cycle. This is a fatal
- error if it would. */
- if (bb_graph[ARC_SOURCE (arcptr)].on_tree && binfo->on_tree)
- abort();
- else
- {
- arcptr->on_tree = 1;
- bb_graph[ARC_SOURCE (arcptr)].on_tree = 1;
- binfo->on_tree = 1;
- }
- }
- /* The only entrace to node zero is a fake arc. */
- bb_graph[0].pred->on_tree = 1;
-
- /* Arcs which are crowded at both the source and target should be put on
- the spanning tree if possible, except for fall_throuch arcs which never
- require adding a new block even if crowded, add arcs with the same source
- and dest which must always be instrumented. */
- for (i = 0; i < num_blocks; i++)
- {
- binfo = &bb_graph[i];
-
- for (arcptr = binfo->succ; arcptr; arcptr = arcptr->succ_next)
- if (! ((binfo->succ == arcptr && arcptr->succ_next == 0)
- || (bb_graph[ARC_TARGET (arcptr)].pred
- && arcptr->pred_next == 0))
- && ! arcptr->fall_through
- && ARC_TARGET (arcptr) != i)
- {
- /* This is a crowded arc at both source and target. Try to put
- in on the spanning tree. Can do this if either the source or
- target block is not yet on the tree. */
- if (! bb_graph[ARC_TARGET (arcptr)].on_tree || ! binfo->on_tree)
+ while (insn != bb->end)
+ {
+ if (GET_CODE (insn) == NOTE)
+ {
+ /* Must ignore the line number notes that immediately
+ follow the end of an inline function to avoid counting
+ it twice. There is a note before the call, and one
+ after the call. */
+ if (NOTE_LINE_NUMBER (insn)
+ == NOTE_INSN_REPEATED_LINE_NUMBER)
+ ignore_next_note = 1;
+ else if (NOTE_LINE_NUMBER (insn) <= 0)
+ /*NOP*/;
+ else if (ignore_next_note)
+ ignore_next_note = 0;
+ else
+ {
+ if (offset)
+ /*NOP*/;
+ else if (gcov_write_unsigned (bbg_file, GCOV_TAG_LINES)
+ || !(offset = gcov_reserve_length (bbg_file))
+ || gcov_write_unsigned (bbg_file,
+ BB_TO_GCOV_INDEX (bb)))
+ goto bbg_error;
+ /* If this is a new source file, then output
+ the file's name to the .bb file. */
+ if (!prev_file_name
+ || strcmp (NOTE_SOURCE_FILE (insn),
+ prev_file_name))
+ {
+ prev_file_name = NOTE_SOURCE_FILE (insn);
+ if (gcov_write_unsigned (bbg_file, 0)
+ || gcov_write_string (bbg_file, prev_file_name,
+ strlen (prev_file_name)))
+ goto bbg_error;
+ }
+ if (gcov_write_unsigned (bbg_file, NOTE_LINE_NUMBER (insn)))
+ goto bbg_error;
+ }
+ }
+ insn = NEXT_INSN (insn);
+ }
+ if (offset)
{
- arcptr->on_tree = 1;
- bb_graph[ARC_TARGET (arcptr)].on_tree = 1;
- binfo->on_tree = 1;
+ if (gcov_write_unsigned (bbg_file, 0)
+ || gcov_write_string (bbg_file, NULL, 0)
+ || gcov_write_length (bbg_file, offset))
+ {
+ bbg_error:;
+ warning ("error writing `%s'", bbg_file_name);
+ fclose (bbg_file);
+ bbg_file = NULL;
+ }
}
}
+ }
}
- /* Clear all of the basic block on_tree bits, so that we can use them to
- create the spanning tree. */
- for (i = 0; i < num_blocks; i++)
- bb_graph[i].on_tree = 0;
+ if (flag_branch_probabilities)
+ compute_branch_probabilities ();
- /* Now fill in the spanning tree until every basic block is on it.
- Don't put the 0 to 1 fall through arc on the tree, since it is
- always cheap to instrument, so start filling the tree from node 1. */
+ /* For each edge not on the spanning tree, add counting code as rtl. */
- for (i = 1; i < num_blocks; i++)
- for (arcptr = bb_graph[i].succ; arcptr; arcptr = arcptr->succ_next)
- if (! arcptr->on_tree
- && ! bb_graph[ARC_TARGET (arcptr)].on_tree)
- {
- fill_spanning_tree (i);
- break;
- }
+ if (cfun->arc_profile && profile_arc_flag)
+ {
+ struct function_list *item;
+
+ instrument_edges (el);
+ allocate_reg_info (max_reg_num (), FALSE, FALSE);
+
+ /* ??? Probably should re-use the existing struct function. */
+ item = xmalloc (sizeof (struct function_list));
+
+ *functions_tail = item;
+ functions_tail = &item->next;
+
+ item->next = 0;
+ item->name = xstrdup (name);
+ item->cfg_checksum = profile_info.current_function_cfg_checksum;
+ item->count_edges = profile_info.count_edges_instrumented_now;
+ }
+
+ remove_fake_edges ();
+ /* Re-merge split basic blocks and the mess introduced by
+ insert_insn_on_edge. */
+ cleanup_cfg (profile_arc_flag ? CLEANUP_EXPENSIVE : 0);
+ if (rtl_dump_file)
+ dump_flow_info (rtl_dump_file);
+
+ free_aux_for_edges ();
+ free_edge_list (el);
}
+\f
+/* Union find algorithm implementation for the basic blocks using
+ aux fields. */
+
+static basic_block
+find_group (bb)
+ basic_block bb;
+{
+ basic_block group = bb, bb1;
-/* Add arcs reached from BLOCK to the spanning tree if they are needed and
- not already there. */
+ while ((basic_block) group->aux != group)
+ group = (basic_block) group->aux;
+
+ /* Compress path. */
+ while ((basic_block) bb->aux != group)
+ {
+ bb1 = (basic_block) bb->aux;
+ bb->aux = (void *) group;
+ bb = bb1;
+ }
+ return group;
+}
static void
-fill_spanning_tree (block)
- int block;
+union_groups (bb1, bb2)
+ basic_block bb1, bb2;
{
- struct adj_list *arcptr;
-
- expand_spanning_tree (block);
+ basic_block bb1g = find_group (bb1);
+ basic_block bb2g = find_group (bb2);
- for (arcptr = bb_graph[block].succ; arcptr; arcptr = arcptr->succ_next)
- if (! arcptr->on_tree
- && ! bb_graph[ARC_TARGET (arcptr)].on_tree)
- {
- arcptr->on_tree = 1;
- fill_spanning_tree (ARC_TARGET (arcptr));
- }
-}
+ /* ??? I don't have a place for the rank field. OK. Lets go w/o it,
+ this code is unlikely going to be performance problem anyway. */
+ if (bb1g == bb2g)
+ abort ();
-/* When first visit a block, must add all blocks that are already connected
- to this block via tree arcs to the spanning tree. */
+ bb1g->aux = bb2g;
+}
+\f
+/* This function searches all of the edges in the program flow graph, and puts
+ as many bad edges as possible onto the spanning tree. Bad edges include
+ abnormals edges, which can't be instrumented at the moment. Since it is
+ possible for fake edges to form a cycle, we will have to develop some
+ better way in the future. Also put critical edges to the tree, since they
+ are more expensive to instrument. */
static void
-expand_spanning_tree (block)
- int block;
+find_spanning_tree (el)
+ struct edge_list *el;
{
- struct adj_list *arcptr;
+ int i;
+ int num_edges = NUM_EDGES (el);
+ basic_block bb;
- bb_graph[block].on_tree = 1;
+ /* We use aux field for standard union-find algorithm. */
+ FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
+ bb->aux = bb;
- for (arcptr = bb_graph[block].succ; arcptr; arcptr = arcptr->succ_next)
- if (arcptr->on_tree && ! bb_graph[ARC_TARGET (arcptr)].on_tree)
- expand_spanning_tree (ARC_TARGET (arcptr));
-
- for (arcptr = bb_graph[block].pred;
- arcptr; arcptr = arcptr->pred_next)
- if (arcptr->on_tree && ! bb_graph[ARC_SOURCE (arcptr)].on_tree)
- expand_spanning_tree (ARC_SOURCE (arcptr));
+ /* Add fake edge exit to entry we can't instrument. */
+ union_groups (EXIT_BLOCK_PTR, ENTRY_BLOCK_PTR);
+
+ /* First add all abnormal edges to the tree unless they form a cycle. Also
+ add all edges to EXIT_BLOCK_PTR to avoid inserting profiling code behind
+ setting return value from function. */
+ for (i = 0; i < num_edges; i++)
+ {
+ edge e = INDEX_EDGE (el, i);
+ if (((e->flags & (EDGE_ABNORMAL | EDGE_ABNORMAL_CALL | EDGE_FAKE))
+ || e->dest == EXIT_BLOCK_PTR
+ )
+ && !EDGE_INFO (e)->ignore
+ && (find_group (e->src) != find_group (e->dest)))
+ {
+ if (rtl_dump_file)
+ fprintf (rtl_dump_file, "Abnormal edge %d to %d put to tree\n",
+ e->src->index, e->dest->index);
+ EDGE_INFO (e)->on_tree = 1;
+ union_groups (e->src, e->dest);
+ }
+ }
+
+ /* Now insert all critical edges to the tree unless they form a cycle. */
+ for (i = 0; i < num_edges; i++)
+ {
+ edge e = INDEX_EDGE (el, i);
+ if ((EDGE_CRITICAL_P (e))
+ && !EDGE_INFO (e)->ignore
+ && (find_group (e->src) != find_group (e->dest)))
+ {
+ if (rtl_dump_file)
+ fprintf (rtl_dump_file, "Critical edge %d to %d put to tree\n",
+ e->src->index, e->dest->index);
+ EDGE_INFO (e)->on_tree = 1;
+ union_groups (e->src, e->dest);
+ }
+ }
+
+ /* And now the rest. */
+ for (i = 0; i < num_edges; i++)
+ {
+ edge e = INDEX_EDGE (el, i);
+ if (find_group (e->src) != find_group (e->dest)
+ && !EDGE_INFO (e)->ignore)
+ {
+ if (rtl_dump_file)
+ fprintf (rtl_dump_file, "Normal edge %d to %d put to tree\n",
+ e->src->index, e->dest->index);
+ EDGE_INFO (e)->on_tree = 1;
+ union_groups (e->src, e->dest);
+ }
+ }
+
+ FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
+ bb->aux = NULL;
}
\f
/* Perform file-level initialization for branch-prob processing. */
init_branch_prob (filename)
const char *filename;
{
- long len;
+ int len = strlen (filename);
int i;
if (flag_test_coverage)
{
- /* Open an output file for the basic block/line number map. */
- int len = strlen (filename);
- char *data_file = (char *) alloca (len + 4);
- strcpy (data_file, filename);
- strip_off_ending (data_file, len);
- strcat (data_file, ".bb");
- if ((bb_file = fopen (data_file, "w")) == 0)
- pfatal_with_name (data_file);
-
- /* Open an output file for the program flow graph. */
- len = strlen (filename);
- bbg_file_name = (char *) alloca (len + 5);
+ /* Open the bbg output file. */
+ bbg_file_name = (char *) xmalloc (len + strlen (GCOV_GRAPH_SUFFIX) + 1);
strcpy (bbg_file_name, filename);
- strip_off_ending (bbg_file_name, len);
- strcat (bbg_file_name, ".bbg");
- if ((bbg_file = fopen (bbg_file_name, "w")) == 0)
- pfatal_with_name (bbg_file_name);
-
- /* Initialize to zero, to ensure that the first file name will be
- written to the .bb file. */
- last_bb_file_name = 0;
+ strcat (bbg_file_name, GCOV_GRAPH_SUFFIX);
+ bbg_file = fopen (bbg_file_name, "wb");
+ if (!bbg_file)
+ fatal_io_error ("cannot open %s", bbg_file_name);
+
+ if (gcov_write_unsigned (bbg_file, GCOV_GRAPH_MAGIC)
+ || gcov_write_unsigned (bbg_file, GCOV_VERSION))
+ {
+ fclose (bbg_file);
+ fatal_io_error ("cannot write `%s'", bbg_file_name);
+ }
}
+ da_file_name = (char *) xmalloc (len + strlen (GCOV_DATA_SUFFIX) + 1);
+ strcpy (da_file_name, filename);
+ strcat (da_file_name, GCOV_DATA_SUFFIX);
+
if (flag_branch_probabilities)
{
- len = strlen (filename);
- da_file_name = (char *) alloca (len + 4);
- strcpy (da_file_name, filename);
- strip_off_ending (da_file_name, len);
- strcat (da_file_name, ".da");
- if ((da_file = fopen (da_file_name, "r")) == 0)
- warning ("file %s not found, execution counts assumed to be zero.",
+ da_file = fopen (da_file_name, "rb");
+ if (!da_file)
+ warning ("file %s not found, execution counts assumed to be zero",
da_file_name);
-
- /* The first word in the .da file gives the number of instrumented arcs,
- which is not needed for our purposes. */
-
- if (da_file)
- __read_long (&len, da_file, 8);
+ if (counts_file_index && strcmp (da_file_name, counts_file_name))
+ cleanup_counts_index (0);
+ if (index_counts_file ())
+ counts_file_name = xstrdup (da_file_name);
}
if (profile_arc_flag)
- init_arc_profiler ();
-
+ {
+ /* Generate and save a copy of this so it can be shared. */
+ char buf[20];
+
+ ASM_GENERATE_INTERNAL_LABEL (buf, "LPBX", 2);
+ profiler_label = gen_rtx_SYMBOL_REF (Pmode, ggc_strdup (buf));
+ }
+
total_num_blocks = 0;
- total_num_arcs = 0;
- total_num_arcs_instrumented = 0;
+ total_num_edges = 0;
+ total_num_edges_ignored = 0;
+ total_num_edges_instrumented = 0;
total_num_blocks_created = 0;
total_num_passes = 0;
total_num_times_called = 0;
is completed. */
void
-end_branch_prob (dump_file)
- FILE *dump_file;
+end_branch_prob ()
{
if (flag_test_coverage)
{
- fclose (bb_file);
- fclose (bbg_file);
- }
-
- if (flag_branch_probabilities)
- {
- if (da_file)
+ if (bbg_file)
{
- long temp;
- /* This seems slightly dangerous, as it presumes the EOF
- flag will not be set until an attempt is made to read
- past the end of the file. */
- if (feof (da_file))
- warning (".da file contents exhausted too early\n");
- /* Should be at end of file now. */
- if (__read_long (&temp, da_file, 8) == 0)
- warning (".da file contents not exhausted\n");
- fclose (da_file);
+#if __GNUC__ && !CROSS_COMPILE && SUPPORTS_WEAK
+ /* If __gcov_init has a value in the compiler, it means we
+ are instrumenting ourselves. We should not remove the
+ counts file, because we might be recompiling
+ ourselves. The .da files are all removed during copying
+ the stage1 files. */
+ extern void __gcov_init (void *)
+ __attribute__ ((weak));
+
+ if (!__gcov_init)
+ unlink (da_file_name);
+#else
+ unlink (da_file_name);
+#endif
+ fclose (bbg_file);
+ }
+ else
+ {
+ unlink (bbg_file_name);
+ unlink (da_file_name);
}
}
- if (dump_file)
+ if (da_file)
+ fclose (da_file);
+
+ if (rtl_dump_file)
{
- fprintf (dump_file, "\n");
- fprintf (dump_file, "Total number of blocks: %d\n", total_num_blocks);
- fprintf (dump_file, "Total number of arcs: %d\n", total_num_arcs);
- fprintf (dump_file, "Total number of instrumented arcs: %d\n",
- total_num_arcs_instrumented);
- fprintf (dump_file, "Total number of blocks created: %d\n",
+ fprintf (rtl_dump_file, "\n");
+ fprintf (rtl_dump_file, "Total number of blocks: %d\n",
+ total_num_blocks);
+ fprintf (rtl_dump_file, "Total number of edges: %d\n", total_num_edges);
+ fprintf (rtl_dump_file, "Total number of ignored edges: %d\n",
+ total_num_edges_ignored);
+ fprintf (rtl_dump_file, "Total number of instrumented edges: %d\n",
+ total_num_edges_instrumented);
+ fprintf (rtl_dump_file, "Total number of blocks created: %d\n",
total_num_blocks_created);
- fprintf (dump_file, "Total number of graph solution passes: %d\n",
+ fprintf (rtl_dump_file, "Total number of graph solution passes: %d\n",
total_num_passes);
if (total_num_times_called != 0)
- fprintf (dump_file, "Average number of graph solution passes: %d\n",
+ fprintf (rtl_dump_file, "Average number of graph solution passes: %d\n",
(total_num_passes + (total_num_times_called >> 1))
/ total_num_times_called);
- fprintf (dump_file, "Total number of branches: %d\n", total_num_branches);
- fprintf (dump_file, "Total number of branches never executed: %d\n",
+ fprintf (rtl_dump_file, "Total number of branches: %d\n",
+ total_num_branches);
+ fprintf (rtl_dump_file, "Total number of branches never executed: %d\n",
total_num_never_executed);
if (total_num_branches)
{
int i;
for (i = 0; i < 10; i++)
- fprintf (dump_file, "%d%% branches in range %d-%d%%\n",
+ fprintf (rtl_dump_file, "%d%% branches in range %d-%d%%\n",
(total_hist_br_prob[i] + total_hist_br_prob[19-i]) * 100
/ total_num_branches, 5*i, 5*i+5);
}
}
}
-\f
-/* The label used by the arc profiling code. */
-
-static rtx profiler_label;
-
-/* Initialize the profiler_label. */
-
-static void
-init_arc_profiler ()
-{
- /* Generate and save a copy of this so it can be shared. */
- char *name = xmalloc (20);
- ASM_GENERATE_INTERNAL_LABEL (name, "LPBX", 2);
- profiler_label = gen_rtx_SYMBOL_REF (Pmode, name);
- ggc_add_rtx_root (&profiler_label, 1);
-}
-
-/* Output instructions as RTL to increment the arc execution count. */
-
-static void
-output_arc_profiler (arcno, insert_after)
- int arcno;
- rtx insert_after;
-{
- rtx profiler_target_addr
- = (arcno ? plus_constant (profiler_label,
- LONG_TYPE_SIZE / BITS_PER_UNIT * arcno)
- : profiler_label);
- enum machine_mode mode = mode_for_size (LONG_TYPE_SIZE, MODE_INT, 0);
- rtx profiler_reg = gen_reg_rtx (mode);
- rtx address_reg = gen_reg_rtx (Pmode);
- rtx mem_ref, add_ref;
- rtx sequence;
-
- /* In this case, reload can use explicitly mentioned hard registers for
- reloads. It is not safe to output profiling code between a call
- and the instruction that copies the result to a pseudo-reg. This
- is because reload may allocate one of the profiling code pseudo-regs
- to the return value reg, thus clobbering the return value. So we
- must check for calls here, and emit the profiling code after the
- instruction that uses the return value, if any.
-
- ??? The code here performs the same tests that reload does so hopefully
- all the bases are covered. */
-
- if (SMALL_REGISTER_CLASSES
- && GET_CODE (insert_after) == CALL_INSN
- && (GET_CODE (PATTERN (insert_after)) == SET
- || (GET_CODE (PATTERN (insert_after)) == PARALLEL
- && GET_CODE (XVECEXP (PATTERN (insert_after), 0, 0)) == SET)))
- {
- rtx return_reg;
- rtx next_insert_after = next_nonnote_insn (insert_after);
-
- /* The first insn after the call may be a stack pop, skip it. */
- if (next_insert_after
- && GET_CODE (next_insert_after) == INSN
- && GET_CODE (PATTERN (next_insert_after)) == SET
- && SET_DEST (PATTERN (next_insert_after)) == stack_pointer_rtx)
- next_insert_after = next_nonnote_insn (next_insert_after);
-
- if (next_insert_after
- && GET_CODE (next_insert_after) == INSN)
- {
- if (GET_CODE (PATTERN (insert_after)) == SET)
- return_reg = SET_DEST (PATTERN (insert_after));
- else
- return_reg = SET_DEST (XVECEXP (PATTERN (insert_after), 0, 0));
-
- /* Now, NEXT_INSERT_AFTER may be an instruction that uses the
- return value. However, it could also be something else,
- like a CODE_LABEL, so check that the code is INSN. */
- if (next_insert_after != 0
- && GET_RTX_CLASS (GET_CODE (next_insert_after)) == 'i'
- && reg_referenced_p (return_reg, PATTERN (next_insert_after)))
- insert_after = next_insert_after;
- }
- }
-
- start_sequence ();
-
- emit_move_insn (address_reg, profiler_target_addr);
- mem_ref = gen_rtx_MEM (mode, address_reg);
- emit_move_insn (profiler_reg, mem_ref);
-
- add_ref = gen_rtx_PLUS (mode, profiler_reg, GEN_INT (1));
- emit_move_insn (profiler_reg, add_ref);
-
- /* This is the same rtx as above, but it is not legal to share this rtx. */
- mem_ref = gen_rtx_MEM (mode, address_reg);
- emit_move_insn (mem_ref, profiler_reg);
-
- sequence = gen_sequence ();
- end_sequence ();
- emit_insn_after (sequence, insert_after);
-}
-/* Output code for a constructor that will invoke __bb_init_func, if
- this has not already been done. */
+/* Write out the structure which libgcc uses to locate all the arc
+ counters. The structures used here must match those defined in
+ gcov-io.h. Write out the constructor to call __gcov_init. */
void
-output_func_start_profiler ()
+create_profiler ()
{
- tree fnname, fndecl;
- char *name, *cfnname;
- rtx table_address;
- enum machine_mode mode = mode_for_size (LONG_TYPE_SIZE, MODE_INT, 0);
+ tree fields, field, value = NULL_TREE;
+ tree ginfo_type;
+ tree string_type;
+ tree gcov_type, gcov_ptr_type;
+ char name[20];
+ char *ctor_name;
+ tree structure, ctor;
+ rtx structure_address;
int save_flag_inline_functions = flag_inline_functions;
- /* It's either already been output, or we don't need it because we're
- not doing profile-arcs. */
- if (! need_func_profiler)
+ if (!profile_info.count_instrumented_edges)
return;
+
+ string_type = build_pointer_type
+ (build_qualified_type (char_type_node, TYPE_QUAL_CONST));
+ gcov_type = make_signed_type (GCOV_TYPE_SIZE);
+ gcov_ptr_type
+ = build_pointer_type (build_qualified_type
+ (gcov_type, TYPE_QUAL_CONST));
+
+ ginfo_type = (*lang_hooks.types.make_type) (RECORD_TYPE);
+
+
+ /* Version ident */
+ fields = build_decl (FIELD_DECL, NULL_TREE, long_unsigned_type_node);
+ value = tree_cons (fields, convert (long_unsigned_type_node, build_int_2
+ (GCOV_VERSION, 0)), value);
+
+ /* NULL */
+ field = build_decl (FIELD_DECL, NULL_TREE, build_pointer_type
+ (build_qualified_type
+ (ginfo_type, TYPE_QUAL_CONST)));
+ TREE_CHAIN (field) = fields;
+ fields = field;
+ value = tree_cons (fields, null_pointer_node, value);
+
+ /* Filename */
+ {
+ tree filename_string;
+ char *filename;
+ int filename_len;
+
+ filename = getpwd ();
+ filename = (filename && da_file_name[0] != '/'
+ ? concat (filename, "/", da_file_name, NULL)
+ : da_file_name);
+ filename_len = strlen (filename);
+ filename_string = build_string (filename_len + 1, filename);
+ if (filename != da_file_name)
+ free (filename);
+ TREE_TYPE (filename_string) = build_array_type
+ (char_type_node, build_index_type
+ (build_int_2 (filename_len, 0)));
+
+ field = build_decl (FIELD_DECL, NULL_TREE, string_type);
+ TREE_CHAIN (field) = fields;
+ fields = field;
+ value = tree_cons (fields, build1 (ADDR_EXPR, string_type,
+ filename_string), value);
+ }
+
+ /* Workspace */
+ field = build_decl (FIELD_DECL, NULL_TREE, long_integer_type_node);
+ TREE_CHAIN (field) = fields;
+ fields = field;
+ value = tree_cons (fields,
+ convert (long_integer_type_node, integer_zero_node),
+ value);
+
+ /* function_info table */
+ {
+ struct function_list *item;
+ int num_nodes = 0;
+ tree array_value = NULL_TREE;
+ tree finfo_type, finfo_ptr_type;
+ tree name, checksum, arcs;
+
+ finfo_type = (*lang_hooks.types.make_type) (RECORD_TYPE);
+ name = build_decl (FIELD_DECL, NULL_TREE, string_type);
+ checksum = build_decl (FIELD_DECL, NULL_TREE, unsigned_type_node);
+ TREE_CHAIN (checksum) = name;
+ arcs = build_decl (FIELD_DECL, NULL_TREE, unsigned_type_node);
+ TREE_CHAIN (arcs) = checksum;
+ finish_builtin_struct (finfo_type, "__function_info",
+ arcs, NULL_TREE);
+ finfo_ptr_type = build_pointer_type
+ (build_qualified_type (finfo_type, TYPE_QUAL_CONST));
+
+ for (item = functions_head; item != 0; item = item->next, num_nodes++)
+ {
+ size_t name_len = strlen (item->name);
+ tree finfo_value = NULL_TREE;
+ tree fname = build_string (name_len + 1, item->name);
+
+ TREE_TYPE (fname) = build_array_type
+ (char_type_node, build_index_type (build_int_2 (name_len, 0)));
+ finfo_value = tree_cons (name, build1
+ (ADDR_EXPR, string_type,
+ fname), finfo_value);
+ finfo_value = tree_cons (checksum, convert
+ (unsigned_type_node,
+ build_int_2 (item->cfg_checksum, 0)),
+ finfo_value);
+ finfo_value = tree_cons (arcs, convert
+ (unsigned_type_node,
+ build_int_2 (item->count_edges, 0)),
+ finfo_value);
+ array_value = tree_cons (NULL_TREE, build
+ (CONSTRUCTOR, finfo_type, NULL_TREE,
+ nreverse (finfo_value)), array_value);
+ }
- need_func_profiler = 0;
-
- /* Synthesize a constructor function to invoke __bb_init_func with a
- pointer to this object file's profile block. */
-
- /* Try and make a unique name given the "file function name".
-
- And no, I don't like this either. */
-
- fnname = get_file_function_name ('I');
- cfnname = IDENTIFIER_POINTER (fnname);
- name = xmalloc (strlen (cfnname) + 5);
- sprintf (name, "%sGCOV",cfnname);
- fnname = get_identifier (name);
- free (name);
-
- fndecl = build_decl (FUNCTION_DECL, fnname,
- build_function_type (void_type_node, NULL_TREE));
- DECL_EXTERNAL (fndecl) = 0;
- TREE_PUBLIC (fndecl) = 1;
- DECL_ASSEMBLER_NAME (fndecl) = fnname;
- DECL_RESULT (fndecl) = build_decl (RESULT_DECL, NULL_TREE, void_type_node);
-
- fndecl = pushdecl (fndecl);
- rest_of_decl_compilation (fndecl, 0, 1, 0);
- announce_function (fndecl);
- current_function_decl = fndecl;
- DECL_INITIAL (fndecl) = error_mark_node;
- temporary_allocation ();
- make_function_rtl (fndecl);
- init_function_start (fndecl, input_filename, lineno);
- pushlevel (0);
- expand_function_start (fndecl, 0);
-
- /* Actually generate the code to call __bb_init_func. */
- name = xmalloc (20);
+ /* Create constructor for array. */
+ if (num_nodes)
+ {
+ tree array_type;
+
+ array_type = build_array_type (finfo_type, build_index_type
+ (build_int_2 (num_nodes - 1, 0)));
+ array_value = build (CONSTRUCTOR, array_type,
+ NULL_TREE, nreverse (array_value));
+ array_value = build1
+ (ADDR_EXPR, finfo_ptr_type, array_value);
+ }
+ else
+ array_value = null_pointer_node;
+
+ field = build_decl (FIELD_DECL, NULL_TREE, finfo_ptr_type);
+ TREE_CHAIN (field) = fields;
+ fields = field;
+ value = tree_cons (fields, array_value, value);
+
+ /* number of functions */
+ field = build_decl (FIELD_DECL, NULL_TREE, unsigned_type_node);
+ TREE_CHAIN (field) = fields;
+ fields = field;
+ value = tree_cons (fields, convert (unsigned_type_node, build_int_2
+ (num_nodes, 0)), value);
+ }
+
+ /* arc count table */
+ {
+ tree counts_table = null_pointer_node;
+
+ if (profile_info.count_instrumented_edges)
+ {
+ tree gcov_type_array_type
+ = build_array_type (gcov_type, build_index_type
+ (build_int_2 (profile_info.
+ count_instrumented_edges - 1, 0)));
+ /* No values. */
+ counts_table
+ = build (VAR_DECL, gcov_type_array_type, NULL_TREE, NULL_TREE);
+ TREE_STATIC (counts_table) = 1;
+ DECL_NAME (counts_table) = get_identifier (XSTR (profiler_label, 0));
+ assemble_variable (counts_table, 0, 0, 0);
+ counts_table = build1 (ADDR_EXPR, gcov_ptr_type, counts_table);
+ }
+
+ field = build_decl (FIELD_DECL, NULL_TREE, gcov_ptr_type);
+ TREE_CHAIN (field) = fields;
+ fields = field;
+ value = tree_cons (fields, counts_table, value);
+ }
+
+ /* number of arc counts */
+ field = build_decl (FIELD_DECL, NULL_TREE, unsigned_type_node);
+ TREE_CHAIN (field) = fields;
+ fields = field;
+ value = tree_cons (fields, convert
+ (unsigned_type_node,
+ build_int_2 (profile_info
+ .count_instrumented_edges, 0)),
+ value);
+
+ finish_builtin_struct (ginfo_type, "__gcov_info", fields, NULL_TREE);
+ structure = build (VAR_DECL, ginfo_type, NULL_TREE, NULL_TREE);
+ DECL_INITIAL (structure)
+ = build (CONSTRUCTOR, ginfo_type, NULL_TREE, nreverse (value));
+ TREE_STATIC (structure) = 1;
ASM_GENERATE_INTERNAL_LABEL (name, "LPBX", 0);
- table_address = force_reg (Pmode, gen_rtx_SYMBOL_REF (Pmode, name));
- emit_library_call (gen_rtx_SYMBOL_REF (Pmode, "__bb_init_func"), 0,
- mode, 1, table_address, Pmode);
+ DECL_NAME (structure) = get_identifier (name);
+
+ /* Build structure. */
+ assemble_variable (structure, 0, 0, 0);
+
+ /* Build the constructor function to invoke __gcov_init. */
+ ctor_name = concat (IDENTIFIER_POINTER (get_file_function_name ('I')),
+ "_GCOV", NULL);
+ ctor = build_decl (FUNCTION_DECL, get_identifier (ctor_name),
+ build_function_type (void_type_node, NULL_TREE));
+ free (ctor_name);
+ DECL_EXTERNAL (ctor) = 0;
+
+ /* It can be a static function as long as collect2 does not have
+ to scan the object file to find its ctor/dtor routine. */
+ TREE_PUBLIC (ctor) = ! targetm.have_ctors_dtors;
+ TREE_USED (ctor) = 1;
+ DECL_RESULT (ctor) = build_decl (RESULT_DECL, NULL_TREE, void_type_node);
+
+ ctor = (*lang_hooks.decls.pushdecl) (ctor);
+ rest_of_decl_compilation (ctor, 0, 1, 0);
+ announce_function (ctor);
+ current_function_decl = ctor;
+ DECL_INITIAL (ctor) = error_mark_node;
+ make_decl_rtl (ctor, NULL);
+ init_function_start (ctor, input_filename, lineno);
+ (*lang_hooks.decls.pushlevel) (0);
+ expand_function_start (ctor, 0);
+ cfun->arc_profile = 0;
+
+ /* Actually generate the code to call __gcov_init. */
+ structure_address = force_reg (Pmode, gen_rtx_SYMBOL_REF
+ (Pmode, IDENTIFIER_POINTER
+ (DECL_NAME (structure))));
+ emit_library_call (gen_rtx_SYMBOL_REF (Pmode, "__gcov_init"),
+ LCT_NORMAL, VOIDmode, 1,
+ structure_address, Pmode);
expand_function_end (input_filename, lineno, 0);
- poplevel (1, 0, 1);
+ (*lang_hooks.decls.poplevel) (1, 0, 1);
- /* Since fndecl isn't in the list of globals, it would never be emitted
+ /* Since ctor isn't in the list of globals, it would never be emitted
when it's considered to be 'safe' for inlining, so turn off
flag_inline_functions. */
flag_inline_functions = 0;
- rest_of_compilation (fndecl);
+ rest_of_compilation (ctor);
/* Reset flag_inline_functions to its original value. */
flag_inline_functions = save_flag_inline_functions;
fflush (asm_out_file);
current_function_decl = NULL_TREE;
- assemble_constructor (IDENTIFIER_POINTER (DECL_NAME (fndecl)));
+ if (targetm.have_ctors_dtors)
+ (* targetm.asm_out.constructor) (XEXP (DECL_RTL (ctor), 0),
+ DEFAULT_INIT_PRIORITY);
+}
+\f
+/* Output instructions as RTL to increment the edge execution count. */
+
+static rtx
+gen_edge_profiler (edgeno)
+ int edgeno;
+{
+ enum machine_mode mode = mode_for_size (GCOV_TYPE_SIZE, MODE_INT, 0);
+ rtx mem_ref, tmp;
+ rtx sequence;
+
+ start_sequence ();
+
+ tmp = force_reg (Pmode, profiler_label);
+ tmp = plus_constant (tmp, GCOV_TYPE_SIZE / BITS_PER_UNIT * edgeno);
+ mem_ref = validize_mem (gen_rtx_MEM (mode, tmp));
+
+ set_mem_alias_set (mem_ref, new_alias_set ());
+
+ tmp = expand_simple_binop (mode, PLUS, mem_ref, const1_rtx,
+ mem_ref, 0, OPTAB_WIDEN);
+
+ if (tmp != mem_ref)
+ emit_move_insn (copy_rtx (mem_ref), tmp);
+
+ sequence = get_insns ();
+ end_sequence ();
+ return sequence;
}
+
+#include "gt-profile.h"