#include <getopt.h>
-typedef HOST_WIDEST_INT gcov_type;
+#define IN_GCOV 1
#include "gcov-io.h"
+#include "gcov-io.c"
/* The bbg file is generated by -ftest-coverage option. The da file is
generated by a program compiled with -fprofile-arcs. Their formats
/* Is an unconditional branch. */
unsigned int is_unconditional : 1;
- /* Arc on the local block spanning tree. */
- unsigned int local_span : 1;
-
+ /* Loop making arc. */
+ unsigned int cycle : 1;
+
/* Next branch on line. */
struct arc_info *line_next;
unsigned invalid_chain : 1;
/* Block is a call instrumenting site. */
- unsigned is_call_site : 1;
+ unsigned is_call_site : 1; /* Does the call. */
+ unsigned is_call_return : 1; /* Is the return. */
/* Block is a landing pad for longjmp or throw. */
unsigned is_nonlocal_return : 1;
} line; /* Valid until blocks are linked onto lines */
struct
{
- /* Single line spanning tree workspace. Used for all-blocks mode. */
- struct block_info *root;
- unsigned siblings;
- } span; /* Used in all-blocks mode, after blocks are linked onto
+ /* Single line graph cycle workspace. Used for all-blocks
+ mode. */
+ arc_t *arc;
+ unsigned ident;
+ } cycle; /* Used in all-blocks mode, after blocks are linked onto
lines. */
} u;
{
/* Name of function. */
char *name;
+ unsigned ident;
unsigned checksum;
/* Array of basic blocks. */
static void print_version PARAMS ((void)) ATTRIBUTE_NORETURN;
static void process_file PARAMS ((const char *));
static void create_file_names PARAMS ((const char *));
-static source_t *find_source PARAMS ((char *));
+static source_t *find_source PARAMS ((const char *));
static int read_graph_file PARAMS ((void));
static int read_count_file PARAMS ((void));
static void solve_flow_graph PARAMS ((function_t *));
}
static void
-fnotice VPARAMS ((FILE *file, const char *msgid, ...))
+fnotice (FILE *file, const char *msgid, ...)
{
- VA_OPEN (ap, msgid);
- VA_FIXEDARG (ap, FILE *, file);
- VA_FIXEDARG (ap, const char *, msgid);
-
+ va_list ap;
+
+ va_start (ap, msgid);
vfprintf (file, _(msgid), ap);
- VA_CLOSE (ap);
+ va_end (ap);
}
/* More 'friendly' abort that prints the line and file.
{ "object-directory", required_argument, NULL, 'o' },
{ "object-file", required_argument, NULL, 'o' },
{ "unconditional-branches", no_argument, NULL, 'u' },
+ { 0, 0, 0, 0 }
};
/* Process args, return index to first non-arg. */
return;
}
-/* Find or create a source file structure for FILE_NAME. Free
- FILE_NAME appropriately */
+/* Find or create a source file structure for FILE_NAME. Copies
+ FILE_NAME on creation */
static source_t *
find_source (file_name)
- char *file_name;
+ const char *file_name;
{
-
source_t *src;
+
+ if (!file_name)
+ file_name = "<unknown>";
for (src = sources; src; src = src->next)
if (!strcmp (file_name, src->name))
- {
- free (file_name);
- break;
- }
- if (!src)
- {
- src = (source_t *)xcalloc (1, sizeof (source_t));
- src->name = file_name;
- src->coverage.name = file_name;
- src->index = sources ? sources->index + 1 : 1;
- src->next = sources;
- sources = src;
- }
+ return src;
+
+ src = (source_t *)xcalloc (1, sizeof (source_t));
+ src->name = xstrdup (file_name);
+ src->coverage.name = src->name;
+ src->index = sources ? sources->index + 1 : 1;
+ src->next = sources;
+ sources = src;
+
return src;
}
static int
read_graph_file ()
{
- FILE *file;
- struct stat status;
- unsigned magic, version;
+ unsigned version;
unsigned current_tag = 0;
- unsigned tag;
struct function_info *fn = NULL;
source_t *src = NULL;
unsigned ix;
-
- file = fopen (bbg_file_name, "rb");
- if (!file)
+ unsigned tag;
+
+ if (!gcov_open (bbg_file_name, 1))
{
fnotice (stderr, "%s:cannot open graph file\n", bbg_file_name);
return 1;
}
- if (!fstat (fileno (file), &status))
- bbg_file_time = status.st_mtime;
- if (gcov_read_unsigned (file, &magic) || magic != GCOV_GRAPH_MAGIC)
+ bbg_file_time = gcov_time ();
+ if (gcov_read_unsigned () != GCOV_GRAPH_MAGIC)
{
fnotice (stderr, "%s:not a gcov graph file\n", bbg_file_name);
- fclose (file);
+ gcov_close ();
return 1;
}
- if (gcov_read_unsigned (file, &version) || version != GCOV_VERSION)
+ version = gcov_read_unsigned ();
+ if (version != GCOV_VERSION)
{
char v[4], e[4];
-
- magic = GCOV_VERSION;
+ unsigned required = GCOV_VERSION;
- for (ix = 4; ix--; magic >>= 8, version >>= 8)
+ for (ix = 4; ix--; required >>= 8, version >>= 8)
{
v[ix] = version;
- e[ix] = magic;
+ e[ix] = required;
}
fnotice (stderr, "%s:version `%.4s', prefer `%.4s'\n",
bbg_file_name, v, e);
}
- while (!gcov_read_unsigned (file, &tag))
+ while ((tag = gcov_read_unsigned ()))
{
- unsigned length;
- long base;
-
- if (gcov_read_unsigned (file, &length))
- goto corrupt;
-
- base = gcov_save_position (file);
+ unsigned length = gcov_read_unsigned ();
+ gcov_position_t base = gcov_position ();
if (tag == GCOV_TAG_FUNCTION)
{
- char *function_name = NULL;
- char *function_file = NULL;
- unsigned checksum, lineno;
+ char *function_name;
+ unsigned ident, checksum, lineno;
source_t *src;
function_t *probe, *prev;
- if (gcov_read_string (file, &function_name, NULL)
- || gcov_read_unsigned (file, &checksum)
- || gcov_read_string (file, &function_file, NULL)
- || gcov_read_unsigned (file, &lineno))
- goto corrupt;
- src = find_source (function_file);
+ ident = gcov_read_unsigned ();
+ checksum = gcov_read_unsigned ();
+ function_name = xstrdup (gcov_read_string ());
+ src = find_source (gcov_read_string ());
+ lineno = gcov_read_unsigned ();
+
fn = (function_t *)xcalloc (1, sizeof (function_t));
fn->name = function_name;
+ fn->ident = ident;
fn->checksum = checksum;
fn->src = src;
fn->line = lineno;
fn->blocks
= (block_t *)xcalloc (fn->num_blocks, sizeof (block_t));
for (ix = 0; ix != num_blocks; ix++)
- {
- unsigned flags;
-
- if (gcov_read_unsigned (file, &flags))
- goto corrupt;
- fn->blocks[ix].flags = flags;
- }
+ fn->blocks[ix].flags = gcov_read_unsigned ();
}
}
else if (fn && tag == GCOV_TAG_ARCS)
{
- unsigned src;
+ unsigned src = gcov_read_unsigned ();
unsigned num_dests = (length - 4) / 8;
- unsigned dest, flags;
- if (gcov_read_unsigned (file, &src)
- || src >= fn->num_blocks
- || fn->blocks[src].succ)
+ if (src >= fn->num_blocks || fn->blocks[src].succ)
goto corrupt;
while (num_dests--)
{
struct arc_info *arc;
+ unsigned dest = gcov_read_unsigned ();
+ unsigned flags = gcov_read_unsigned ();
- if (gcov_read_unsigned (file, &dest)
- || gcov_read_unsigned (file, &flags)
- || dest >= fn->num_blocks)
+ if (dest >= fn->num_blocks)
goto corrupt;
arc = (arc_t *) xcalloc (1, sizeof (arc_t));
}
else if (fn && tag == GCOV_TAG_LINES)
{
- unsigned blockno;
+ unsigned blockno = gcov_read_unsigned ();
unsigned *line_nos
= (unsigned *)xcalloc ((length - 4) / 4, sizeof (unsigned));
- if (gcov_read_unsigned (file, &blockno)
- || blockno >= fn->num_blocks
- || fn->blocks[blockno].u.line.encoding)
+ if (blockno >= fn->num_blocks || fn->blocks[blockno].u.line.encoding)
goto corrupt;
for (ix = 0; ; )
{
- unsigned lineno;
+ unsigned lineno = gcov_read_unsigned ();
- if (gcov_read_unsigned (file, &lineno))
- goto corrupt;
if (lineno)
{
if (!ix)
}
else
{
- char *file_name = NULL;
+ const char *file_name = gcov_read_string ();
- if (gcov_read_string (file, &file_name, NULL))
- goto corrupt;
if (!file_name)
break;
src = find_source (file_name);
fn = NULL;
current_tag = 0;
}
- if (gcov_resync (file, base, length))
- {
- corrupt:;
- fnotice (stderr, "%s:corrupted\n", bbg_file_name);
- fclose (file);
- return 1;
- }
+ gcov_sync (base, length);
+ if (gcov_is_error ())
+ break;
}
- fclose (file);
+ if (!gcov_is_eof ())
+ {
+ corrupt:;
+ fnotice (stderr, "%s:corrupted\n", bbg_file_name);
+ gcov_close ();
+ return 1;
+ }
+ gcov_close ();
/* We built everything backwards, so nreverse them all */
static int
read_count_file ()
{
- FILE *file;
unsigned ix;
- char *function_name_buffer = NULL;
- unsigned magic, version;
+ unsigned version;
+ unsigned tag;
function_t *fn = NULL;
+ int error = 0;
- file = fopen (da_file_name, "rb");
- if (!file)
+ if (!gcov_open (da_file_name, 1))
{
fnotice (stderr, "%s:cannot open data file\n", da_file_name);
return 1;
}
- if (gcov_read_unsigned (file, &magic) || magic != GCOV_DATA_MAGIC)
+ if (gcov_read_unsigned () != GCOV_DATA_MAGIC)
{
fnotice (stderr, "%s:not a gcov data file\n", da_file_name);
cleanup:;
- free (function_name_buffer);
- fclose (file);
+ gcov_close ();
return 1;
}
- if (gcov_read_unsigned (file, &version) || version != GCOV_VERSION)
+ version = gcov_read_unsigned ();
+ if (version != GCOV_VERSION)
{
char v[4], e[4];
+ unsigned desired = GCOV_VERSION;
- magic = GCOV_VERSION;
- for (ix = 4; ix--; magic >>= 8, version >>= 8)
+ for (ix = 4; ix--; desired >>= 8, version >>= 8)
{
v[ix] = version;
- e[ix] = magic;
+ e[ix] = desired;
}
fnotice (stderr, "%s:version `%.4s', prefer version `%.4s'\n",
da_file_name, v, e);
}
- while (1)
+ while ((tag = gcov_read_unsigned ()))
{
- unsigned tag, length;
- long base;
-
- if (gcov_read_unsigned (file, &tag)
- || gcov_read_unsigned (file, &length))
- {
- if (feof (file))
- break;
-
- corrupt:;
- fnotice (stderr, "%s:corrupted\n", da_file_name);
- goto cleanup;
- }
- base = gcov_save_position (file);
+ unsigned length = gcov_read_unsigned ();
+ unsigned long base = gcov_position ();
+
if (tag == GCOV_TAG_OBJECT_SUMMARY)
- {
- if (gcov_read_summary (file, &object_summary))
- goto corrupt;
- }
- else if (tag == GCOV_TAG_PROGRAM_SUMMARY
- || tag == GCOV_TAG_INCORRECT_SUMMARY)
+ gcov_read_summary (&object_summary);
+ else if (tag == GCOV_TAG_PROGRAM_SUMMARY)
program_count++;
else if (tag == GCOV_TAG_FUNCTION)
{
- unsigned checksum;
+ unsigned ident = gcov_read_unsigned ();
struct function_info *fn_n = functions;
-
- if (gcov_read_string (file, &function_name_buffer, NULL)
- || gcov_read_unsigned (file, &checksum))
- goto corrupt;
for (fn = fn ? fn->next : NULL; ; fn = fn->next)
{
fn_n = NULL;
else
{
- fnotice (stderr, "%s:unknown function `%s'\n",
- da_file_name, function_name_buffer);
+ fnotice (stderr, "%s:unknown function `%u'\n",
+ da_file_name, ident);
break;
}
- if (!strcmp (fn->name, function_name_buffer))
+ if (fn->ident == ident)
break;
}
if (!fn)
;
- else if (checksum != fn->checksum)
+ else if (gcov_read_unsigned () != fn->checksum)
{
mismatch:;
fnotice (stderr, "%s:profile mismatch for `%s'\n",
- da_file_name, function_name_buffer);
+ da_file_name, fn->name);
goto cleanup;
}
}
- else if (tag == GCOV_TAG_ARC_COUNTS && fn)
+ else if (tag == GCOV_TAG_FOR_COUNTER (GCOV_COUNTER_ARCS) && fn)
{
if (length != 8 * fn->num_counts)
goto mismatch;
= (gcov_type *)xcalloc (fn->num_counts, sizeof (gcov_type));
for (ix = 0; ix != fn->num_counts; ix++)
- {
- gcov_type count;
-
- if (gcov_read_counter (file, &count))
- goto corrupt;
- fn->counts[ix] += count;
- }
+ fn->counts[ix] += gcov_read_counter ();
}
- gcov_resync (file, base, length);
+ gcov_sync (base, length);
+ if ((error = gcov_is_error ()))
+ break;
}
- fclose (file);
- free (function_name_buffer);
+ if (!gcov_is_eof ())
+ {
+ fnotice (stderr, error < 0 ? "%s:overflowed\n" : "%s:corrupted\n",
+ da_file_name);
+ goto cleanup;
+ }
+
+ gcov_close ();
return 0;
}
arc->is_unconditional = 1;
/* If this block is instrumenting a call, it might be
an artifical block. It is not artificial if it has
- a non-fallthrough exit, or the destination of the
- exit has more than one entry. */
- if (!arc->fall_through
- || arc->dst->pred != arc || arc->pred_next)
- blk->is_call_site = 0;
+ a non-fallthrough exit, or the destination of this
+ arc has more than one entry. Mark the destination
+ block as a return site, if none of those conditions
+ hold. */
+ if (blk->is_call_site && arc->fall_through
+ && arc->dst->pred == arc && !arc->pred_next)
+ arc->dst->is_call_return = 1;
}
}
- else
- /* If there is more than one exit, it cannot be an artificial
- call instrumenting site. */
- blk->is_call_site = 0;
/* Sort the successor arcs into ascending dst order. profile.c
normally produces arcs in the right order, but sometimes with
unsigned *encoding;
const source_t *src = NULL;
unsigned jx;
- line_t *first_line = NULL;
if (block->count && ix && ix + 1 != fn->num_blocks)
fn->blocks_executed++;
}
line->exists = 1;
line->count += block->count;
- if (!first_line)
- first_line = line;
}
free (block->u.line.encoding);
- block->u.span.root = NULL;
- if (!first_line)
- first_line = line;
-
+ block->u.cycle.arc = NULL;
+ block->u.cycle.ident = ~0U;
+
if (!ix || ix + 1 == fn->num_blocks)
/* Entry or exit block */;
else if (flag_all_blocks)
{
- if (!first_line)
- first_line = &fn->src->lines[fn->line];
+ line_t *block_line = line ? line : &fn->src->lines[fn->line];
- block->chain = first_line->u.blocks;
- first_line->u.blocks = block;
+ block->chain = block_line->u.blocks;
+ block_line->u.blocks = block;
}
else if (flag_branches)
{
/* The user expects the line count to be the number of times
a line has been executed. Simply summing the block count
will give an artificially high number. The Right Thing
- is to generate the spanning tree of the blocks on this
- line, and the sum the entry arcs to that tree. */
+ is to sum the entry counts to the graph of blocks on this
+ line, then find the elementary cycles of the local graph
+ and add the transition counts of those cycles. */
block_t *block, *block_p, *block_n;
- int changes = 1;
gcov_type count = 0;
/* Reverse the block information */
{
block_n = block->chain;
block->chain = block_p;
- /* Each block is it's own spanning tree, with no siblings */
- block->u.span.root = block;
- block->u.span.siblings = 0;
+ block->u.cycle.ident = ix;
}
line->u.blocks = block_p;
+
+ /* Sum the entry arcs. */
+ for (block = line->u.blocks; block; block = block->chain)
+ {
+ arc_t *arc;
- while (changes)
+ for (arc = block->pred; arc; arc = arc->pred_next)
+ {
+ if (arc->src->u.cycle.ident != ix)
+ count += arc->count;
+ if (flag_branches)
+ add_branch_counts (&src->coverage, arc);
+ }
+ }
+
+ /* Find the loops. This uses the algorithm described in
+ Tiernan 'An Efficient Search Algorithm to Find the
+ Elementary Circuits of a Graph', CACM Dec 1970. We hold
+ the P array by having each block point to the arc that
+ connects to the previous block. The H array is implicitly
+ held because of the arc ordering, and the block's
+ previous arc pointer.
+
+ Although the algorithm is O(N^3) for highly connected
+ graphs, at worst we'll have O(N^2), as most blocks have
+ only one or two exits. Most graphs will be small.
+
+ For each loop we find, locate the arc with the smallest
+ transition count, and add that to the cumulative
+ count. Remove the arc from consideration. */
+ for (block = line->u.blocks; block; block = block->chain)
{
- changes = 0;
+ block_t *head = block;
+ arc_t *arc;
- for (block = line->u.blocks; block; block = block->chain)
+ next_vertex:;
+ arc = head->succ;
+ current_vertex:;
+ while (arc)
{
- arc_t *arc;
+ block_t *dst = arc->dst;
+ if (/* Already used that arc. */
+ arc->cycle
+ /* Not to same graph, or before first vertex. */
+ || dst->u.cycle.ident != ix
+ /* Already in path. */
+ || dst->u.cycle.arc)
+ {
+ arc = arc->succ_next;
+ continue;
+ }
- for (arc = block->succ; arc; arc = arc->succ_next)
+ if (dst == block)
{
- block_t *dst = arc->dst;
+ /* Found a closing arc. */
+ gcov_type cycle_count = arc->count;
+ arc_t *cycle_arc = arc;
+ arc_t *probe_arc;
- if (!dst->u.span.root)
- /* Not on this line. */;
- else if (dst->u.span.root == block->u.span.root)
- /* Same spanning tree. */;
- else
+ /* Locate the smallest arc count of the loop. */
+ for (dst = head; (probe_arc = dst->u.cycle.arc);
+ dst = probe_arc->src)
+ if (cycle_count > probe_arc->count)
+ {
+ cycle_count = probe_arc->count;
+ cycle_arc = probe_arc;
+ }
+
+ count += cycle_count;
+ cycle_arc->cycle = 1;
+ /* Unwind to the cyclic arc. */
+ while (head != cycle_arc->src)
{
- block_t *root = block->u.span.root;
- block_t *dst_root = dst->u.span.root;
-
- /* Join spanning trees */
- if (root->u.span.siblings && !dst_root->u.span.root)
- {
- root = dst->u.span.root;
- dst_root = block->u.span.root;
- }
-
- dst->u.span.root = root;
- root->u.span.siblings += 1 + dst->u.span.siblings;
- if (dst->u.span.siblings)
- {
- block_t *dst_sib;
-
- dst->u.span.siblings = 0;
- for (dst_sib = line->u.blocks; dst_sib;
- dst_sib = dst_sib->chain)
- if (dst_sib->u.span.root == dst_root)
- dst_sib->u.span.root = root;
- }
- arc->local_span = 1;
- changes = 1;
+ arc = head->u.cycle.arc;
+ head = arc->src;
}
+ /* Move on. */
+ arc = arc->succ_next;
+ continue;
}
+
+ /* Add new block to chain. */
+ dst->u.cycle.arc = arc;
+ head = dst;
+ goto next_vertex;
}
- }
-
- /* Now sum the entry counts */
- for (block = line->u.blocks; block; block = block->chain)
- {
- arc_t *arc;
-
- for (arc = block->succ; arc; arc = arc->succ_next)
+ /* We could not add another vertex to the path. Remove
+ the last vertex from the list. */
+ arc = head->u.cycle.arc;
+ if (arc)
{
- if (!arc->local_span)
- count += arc->count;
- if (flag_branches)
- add_branch_counts (&src->coverage, arc);
+ /* It was not the first vertex. Move onto next arc. */
+ head->u.cycle.arc = NULL;
+ head = arc->src;
+ arc = arc->succ_next;
+ goto current_vertex;
}
- block->u.span.root = NULL;
+ /* Mark this block as unusable. */
+ block->u.cycle.ident = ~0U;
}
-
+
line->count = count;
}
else
fnotice (gcov_file, "branch %2d never executed\n", ix);
}
- else if (flag_unconditional && !arc->src->is_call_site)
+ else if (flag_unconditional && !arc->dst->is_call_return)
{
if (arc->src->count)
fnotice (gcov_file, "unconditional %2d taken %s\n", ix,
fprintf (gcov_file, "%9s:%5d:Source:%s\n", "-", 0, src->name);
fprintf (gcov_file, "%9s:%5d:Graph:%s\n", "-", 0, bbg_file_name);
fprintf (gcov_file, "%9s:%5d:Data:%s\n", "-", 0, da_file_name);
- fprintf (gcov_file, "%9s:%5d:Runs:%u\n", "-", 0, object_summary.runs);
+ fprintf (gcov_file, "%9s:%5d:Runs:%u\n", "-", 0,
+ object_summary.ctrs[GCOV_COUNTER_ARCS].runs);
fprintf (gcov_file, "%9s:%5d:Programs:%u\n", "-", 0, program_count);
source_file = fopen (src->name, "r");
{
retval = fgets (string, STRING_SIZE, source_file);
if (!retval)
- {
- fnotice (stderr, "%s:unexpected EOF\n", src->name);
- break;
- }
+ break;
fputs (retval, gcov_file);
}
while (!retval[0] || retval[strlen (retval) - 1] != '\n');
}
if (!retval)
- fputs ("??\n", gcov_file);
+ fputs ("/*EOF*/\n", gcov_file);
if (flag_all_blocks)
{
block_t *block;
+ arc_t *arc;
int ix, jx;
for (ix = jx = 0, block = line->u.blocks; block;
block = block->chain)
{
- arc_t *arc;
-
- if (!block->is_call_site)
+ if (!block->is_call_return)
fprintf (gcov_file, "%9s:%5u-block %2d\n",
!line->exists ? "-" : !block->count ? "$$$$$"
- : format_gcov (block->count, 0, -1), line_num, ix++);
+ : format_gcov (block->count, 0, -1),
+ line_num, ix++);
if (flag_branches)
for (arc = block->succ; arc; arc = arc->succ_next)
jx += output_branch_count (gcov_file, jx, arc);
OSDN Git Service
