From patchwork Thu Nov 10 19:17:17 2011 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Nathan Sidwell X-Patchwork-Id: 124986 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Received: from sourceware.org (server1.sourceware.org [209.132.180.131]) by ozlabs.org (Postfix) with SMTP id 090551007D1 for ; Fri, 11 Nov 2011 06:17:43 +1100 (EST) Received: (qmail 8182 invoked by alias); 10 Nov 2011 19:17:40 -0000 Received: (qmail 8172 invoked by uid 22791); 10 Nov 2011 19:17:37 -0000 X-SWARE-Spam-Status: No, hits=-1.0 required=5.0 tests=AWL, BAYES_00, RCVD_IN_DNSWL_LOW, TW_CF, TW_CP, TW_FN X-Spam-Check-By: sourceware.org Received: from mail-wy0-f175.google.com (HELO mail-wy0-f175.google.com) (74.125.82.175) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Thu, 10 Nov 2011 19:17:22 +0000 Received: by wyh5 with SMTP id 5so3441870wyh.20 for ; Thu, 10 Nov 2011 11:17:21 -0800 (PST) Received: by 10.227.59.204 with SMTP id m12mr5999701wbh.14.1320952640977; Thu, 10 Nov 2011 11:17:20 -0800 (PST) Received: by 10.227.59.204 with SMTP id m12mr5999661wbh.14.1320952640185; Thu, 10 Nov 2011 11:17:20 -0800 (PST) Received: from [192.168.44.105] (5ac3c889.bb.sky.com. [90.195.200.137]) by mx.google.com with ESMTPS id j29sm2118329wbn.5.2011.11.10.11.17.18 (version=SSLv3 cipher=OTHER); Thu, 10 Nov 2011 11:17:19 -0800 (PST) Message-ID: <4EBC233D.6070203@acm.org> Date: Thu, 10 Nov 2011 19:17:17 +0000 From: Nathan Sidwell User-Agent: Mozilla/5.0 (X11; U; Linux i686; en-US; rv:1.9.2.23) Gecko/20110922 Lightning/1.0b2 Thunderbird/3.1.15 MIME-Version: 1.0 To: GCC Patches Subject: gcov internal changes Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Unsubscribe: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Delivered-To: mailing list gcc-patches@gcc.gnu.org I've committed this patch to reorganize the internal data structures of gcov in preparation for some future features. The main change is that the sources list becomes an array. This changes references to a source_info object to be an index into the array, rather than a pointer. In making this change I noticed a bug introduced by my comdat support. We were adding a function into the list for a source file before determining whether that instance of the function was in the executable at all. built & tested on i686-pc-linux-gnu. nathan 2011-11-10 Nathan Sidwell * gcov.c (struct function_info): Make src an index, not a pointer. (struct source_info): Remove index and next source fields. (fn_end): New static var. (sources_index): Remove. (sources): Now a pointer to an array, not a list. (n_sources, a_sources): New. (process_file): Adjust for changes to read_graph_file. Insert functions into source lists and check line numbers here. (generate_results): Only allocate lines for sources with contents. Adjust for source array. (release_structures): Likewise. (find_source): Return source index, adjust for source array. (read_graph_file): Return function list. Don't insert into source lists here. (read_count_file): Take list of functions. (solve_flow_graph): Reverse the arc lists here. (add_line_counts): Adjust for source array. Index: gcov.c =================================================================== --- gcov.c (revision 181105) +++ gcov.c (working copy) @@ -181,9 +181,9 @@ typedef struct function_info gcov_type *counts; unsigned num_counts; - /* First line number. */ + /* First line number & file. */ unsigned line; - struct source_info *src; + unsigned src; /* Next function in same source file. */ struct function_info *line_next; @@ -233,7 +233,6 @@ typedef struct source_info { /* Name of source file. */ char *name; - unsigned index; time_t file_time; /* Array of line information. */ @@ -245,23 +244,16 @@ typedef struct source_info /* Functions in this source file. These are in ascending line number order. */ function_t *functions; - - /* Next source file. */ - struct source_info *next; } source_t; /* Holds a list of function basic block graphs. */ static function_t *functions; +static function_t **fn_end = &functions; -/* This points to the head of the sourcefile structure list. New elements - are always prepended. */ - -static source_t *sources; - -/* Next index for a source file. */ - -static unsigned source_index; +static source_t *sources; /* Array of source files */ +static unsigned n_sources; /* Number of sources */ +static unsigned a_sources; /* Allocated sources */ /* This holds data summary information. */ @@ -349,9 +341,9 @@ static void print_version (void) ATTRIBU static void process_file (const char *); static void generate_results (const char *); static void create_file_names (const char *); -static source_t *find_source (const char *); -static int read_graph_file (void); -static int read_count_file (void); +static unsigned find_source (const char *); +static function_t *read_graph_file (void); +static int read_count_file (function_t *); static void solve_flow_graph (function_t *); static void add_branch_counts (coverage_t *, const arc_t *); static void add_line_counts (coverage_t *, function_t *); @@ -537,57 +529,85 @@ process_args (int argc, char **argv) static void process_file (const char *file_name) { - function_t *fn; - function_t **fn_p; - function_t *old_functions; - - /* Save and clear the list of current functions. They will be appended - later. */ - old_functions = functions; - functions = NULL; + function_t *fns; create_file_names (file_name); - if (read_graph_file ()) + fns = read_graph_file (); + if (!fns) return; - - if (!functions) + + read_count_file (fns); + while (fns) { - fnotice (stderr, "%s:no functions found\n", bbg_file_name); - return; - } - - if (read_count_file ()) - return; + function_t *fn = fns; - fn_p = &functions; - while ((fn = *fn_p) != NULL) - { + fns = fn->next; + fn->next = NULL; if (fn->counts) { + unsigned src = fn->src; + unsigned line = fn->line; + unsigned block_no; + function_t *probe, **prev; + + /* Now insert it into the source file's list of + functions. Normally functions will be encountered in + ascending order, so a simple scan is quick. Note we're + building this list in reverse order. */ + for (prev = &sources[src].functions; + (probe = *prev); prev = &probe->line_next) + if (probe->line <= line) + break; + fn->line_next = probe; + *prev = fn; + + /* Mark last line in files touched by function. */ + for (block_no = 0; block_no != fn->num_blocks; block_no++) + { + unsigned *enc = fn->blocks[block_no].u.line.encoding; + unsigned num = fn->blocks[block_no].u.line.num; + + for (; num--; enc++) + if (!*enc) + { + if (enc[1] != src) + { + if (line >= sources[src].num_lines) + sources[src].num_lines = line + 1; + line = 0; + src = enc[1]; + } + enc++; + num--; + } + else if (*enc > line) + line = *enc; + } + if (line >= sources[src].num_lines) + sources[src].num_lines = line + 1; + solve_flow_graph (fn); - fn_p = &fn->next; + *fn_end = fn; + fn_end = &fn->next; } else - { - /* The function was not in the executable -- some other - instance must have been selected. */ - function_t *next = fn->next; - release_function (fn); - *fn_p = next; - } + /* The function was not in the executable -- some other + instance must have been selected. */ + release_function (fn); } - - *fn_p = old_functions; } static void generate_results (const char *file_name) { + unsigned ix; source_t *src; function_t *fn; - for (src = sources; src; src = src->next) - src->lines = XCNEWVEC (line_t, src->num_lines); + for (ix = n_sources, src = sources; ix--; src++) + if (src->num_lines) + src->lines = XCNEWVEC (line_t, src->num_lines); + for (fn = functions; fn; fn = fn->next) { coverage_t coverage; @@ -602,7 +622,7 @@ generate_results (const char *file_name) } } - for (src = sources; src; src = src->next) + for (ix = n_sources, src = sources; ix--; src++) { accumulate_line_counts (src); function_summary (&src->coverage, "File"); @@ -657,15 +677,13 @@ release_function (function_t *fn) static void release_structures (void) { + unsigned ix; function_t *fn; - source_t *src; - while ((src = sources)) + for (ix = n_sources; ix--;) { - sources = src->next; - - free (src->name); - free (src->lines); + free (sources[ix].name); + free (sources[ix].lines); } while ((fn = functions)) @@ -746,28 +764,40 @@ create_file_names (const char *file_name /* Find or create a source file structure for FILE_NAME. Copies FILE_NAME on creation */ -static source_t * +static unsigned find_source (const char *file_name) { - source_t *src; + unsigned ix; + source_t *src = 0; struct stat status; if (!file_name) file_name = ""; - for (src = sources; src; src = src->next) - if (!filename_cmp (file_name, src->name)) - break; + for (ix = n_sources; ix--;) + if (!filename_cmp (file_name, sources[ix].name)) + { + src = &sources[ix]; + break; + } if (!src) { - src = XCNEW (source_t); + if (n_sources == a_sources) + { + if (!a_sources) + a_sources = 10; + a_sources *= 2; + src = XNEWVEC (source_t, a_sources); + memcpy (src, sources, n_sources * sizeof (*sources)); + free (sources); + sources = src; + } + ix = n_sources; + src = &sources[ix]; src->name = xstrdup (file_name); src->coverage.name = src->name; - src->index = source_index++; - src->next = sources; - sources = src; - + n_sources++; if (!stat (file_name, &status)) src->file_time = status.st_mtime; } @@ -787,33 +817,34 @@ find_source (const char *file_name) src->file_time = 0; } - return src; + return ix; } -/* Read the graph file. Return nonzero on fatal error. */ +/* Read the graph file. Return list of functions read -- in reverse order. */ -static int +static function_t * read_graph_file (void) { unsigned version; unsigned current_tag = 0; - struct function_info *fn = NULL; - function_t *old_functions_head = functions; - source_t *src = NULL; + function_t *fn = NULL; + function_t *fns = NULL; + function_t **fns_end = &fns; + unsigned src_idx = 0; unsigned ix; unsigned tag; if (!gcov_open (bbg_file_name, 1)) { fnotice (stderr, "%s:cannot open graph file\n", bbg_file_name); - return 1; + return fns; } bbg_file_time = gcov_time (); if (!gcov_magic (gcov_read_unsigned (), GCOV_NOTE_MAGIC)) { fnotice (stderr, "%s:not a gcov graph file\n", bbg_file_name); gcov_close (); - return 1; + return fns; } version = gcov_read_unsigned (); @@ -839,14 +870,12 @@ read_graph_file (void) char *function_name; unsigned ident, lineno; unsigned lineno_checksum, cfg_checksum; - source_t *src; - function_t *probe, *prev; ident = gcov_read_unsigned (); lineno_checksum = gcov_read_unsigned (); cfg_checksum = gcov_read_unsigned (); function_name = xstrdup (gcov_read_string ()); - src = find_source (gcov_read_string ()); + src_idx = find_source (gcov_read_string ()); lineno = gcov_read_unsigned (); fn = XCNEW (function_t); @@ -854,27 +883,14 @@ read_graph_file (void) fn->ident = ident; fn->lineno_checksum = lineno_checksum; fn->cfg_checksum = cfg_checksum; - fn->src = src; + fn->src = src_idx; fn->line = lineno; - fn->next = functions; - functions = fn; + fn->line_next = NULL; + fn->next = NULL; + *fns_end = fn; + fns_end = &fn->next; current_tag = tag; - - if (lineno >= src->num_lines) - src->num_lines = lineno + 1; - /* Now insert it into the source file's list of - functions. Normally functions will be encountered in - ascending order, so a simple scan is quick. */ - for (probe = src->functions, prev = NULL; - probe && probe->line > lineno; - prev = probe, probe = probe->line_next) - continue; - fn->line_next = probe; - if (prev) - prev->line_next = fn; - else - src->functions = fn; } else if (fn && tag == GCOV_TAG_BLOCKS) { @@ -966,11 +982,9 @@ read_graph_file (void) if (!ix) { line_nos[ix++] = 0; - line_nos[ix++] = src->index; + line_nos[ix++] = src_idx; } line_nos[ix++] = lineno; - if (lineno >= src->num_lines) - src->num_lines = lineno + 1; } else { @@ -978,10 +992,9 @@ read_graph_file (void) if (!file_name) break; - src = find_source (file_name); - + src_idx = find_source (file_name); line_nos[ix++] = 0; - line_nos[ix++] = src->index; + line_nos[ix++] = src_idx; } } @@ -998,72 +1011,22 @@ read_graph_file (void) { corrupt:; fnotice (stderr, "%s:corrupted\n", bbg_file_name); - gcov_close (); - return 1; + break; } } gcov_close (); - /* We built everything backwards, so nreverse them all. */ - - /* Reverse sources. Not strictly necessary, but we'll then process - them in the 'expected' order. */ - { - source_t *src, *src_p, *src_n; - - for (src_p = NULL, src = sources; src; src_p = src, src = src_n) - { - src_n = src->next; - src->next = src_p; - } - sources = src_p; - } - - /* Reverse functions. */ - { - function_t *fn, *fn_p, *fn_n; - - for (fn_p = old_functions_head, fn = functions; - fn != old_functions_head; - fn_p = fn, fn = fn_n) - { - unsigned ix; - - fn_n = fn->next; - fn->next = fn_p; + if (!fns) + fnotice (stderr, "%s:no functions found\n", bbg_file_name); - /* Reverse the arcs. */ - for (ix = fn->num_blocks; ix--;) - { - arc_t *arc, *arc_p, *arc_n; - - for (arc_p = NULL, arc = fn->blocks[ix].succ; arc; - arc_p = arc, arc = arc_n) - { - arc_n = arc->succ_next; - arc->succ_next = arc_p; - } - fn->blocks[ix].succ = arc_p; - - for (arc_p = NULL, arc = fn->blocks[ix].pred; arc; - arc_p = arc, arc = arc_n) - { - arc_n = arc->pred_next; - arc->pred_next = arc_p; - } - fn->blocks[ix].pred = arc_p; - } - } - functions = fn_p; - } - return 0; + return fns; } /* Reads profiles from the count file and attach to each function. Return nonzero if fatal error. */ static int -read_count_file (void) +read_count_file (function_t *fns) { unsigned ix; unsigned version; @@ -1125,7 +1088,7 @@ read_count_file (void) /* Try to find the function in the list. To speed up the search, first start from the last function found. */ ident = gcov_read_unsigned (); - fn_n = functions; + fn_n = fns; for (fn = fn ? fn->next : NULL; ; fn = fn->next) { if (fn) @@ -1190,6 +1153,28 @@ solve_flow_graph (function_t *fn) block_t *valid_blocks = NULL; /* valid, but unpropagated blocks. */ block_t *invalid_blocks = NULL; /* invalid, but inferable blocks. */ + /* The arcs were built in reverse order. Fix that now. */ + for (ix = fn->num_blocks; ix--;) + { + arc_t *arc_p, *arc_n; + + for (arc_p = NULL, arc = fn->blocks[ix].succ; arc; + arc_p = arc, arc = arc_n) + { + arc_n = arc->succ_next; + arc->succ_next = arc_p; + } + fn->blocks[ix].succ = arc_p; + + for (arc_p = NULL, arc = fn->blocks[ix].pred; arc; + arc_p = arc, arc = arc_n) + { + arc_n = arc->pred_next; + arc->pred_next = arc_p; + } + fn->blocks[ix].pred = arc_p; + } + if (fn->num_blocks < 2) fnotice (stderr, "%s:'%s' lacks entry and/or exit blocks\n", bbg_file_name, fn->name); @@ -1643,10 +1628,7 @@ add_line_counts (coverage_t *coverage, f jx != block->u.line.num; jx++, encoding++) if (!*encoding) { - unsigned src_n = *++encoding; - - for (src = sources; src->index != src_n; src = src->next) - continue; + src = &sources[*++encoding]; jx++; } else @@ -1671,7 +1653,10 @@ add_line_counts (coverage_t *coverage, f /* Entry or exit block */; else if (flag_all_blocks) { - line_t *block_line = line ? line : &fn->src->lines[fn->line]; + line_t *block_line = line; + + if (!block_line) + block_line = &sources[fn->src].lines[fn->line]; block->chain = block_line->u.blocks; block_line->u.blocks = block;