diff options
author | Sergey Poznyakoff <gray@gnu.org.ua> | 2009-11-09 01:50:43 +0200 |
---|---|---|
committer | Sergey Poznyakoff <gray@gnu.org.ua> | 2009-11-09 01:50:43 +0200 |
commit | dc1a81526099095b12ef6edb655cf1a773dfa983 (patch) | |
tree | 17defadb706683a3a59ee41428200ee66d91d34b | |
parent | 4d75955e833201c4f1d0219d48676521aeee1afa (diff) | |
download | cflow-dc1a81526099095b12ef6edb655cf1a773dfa983.tar.gz cflow-dc1a81526099095b12ef6edb655cf1a773dfa983.tar.bz2 |
Speed-up recursive call detection.
* src/depmap.c: New file.
* src/Makefile.am: Add depmap.c.
* src/cflow.h (struct symbol.ord): New member.
(collect_symbols): Change signature. All callers
updated.
(collect_functions): New proto.
(symbol_is_function): New proto.
(cflow_depmap_t): New data type.
(depmap_alloc, depmap_set)
(depmap_isset, depmap_tc): New prototypes.
* src/output.c (symbol_is_function): New function.
(scan_tree): Remove.
(tree_output): Use depmap to find out recursive calls.
* src/symbol.c (static_func_list): New list.
(static_free): Add static functions to static_func_list.
(collect_symbols): Return size_t. Take additional number
of slots in the 3rd argument.
(collect_functions): New function.
-rw-r--r-- | src/Makefile.am | 1 | ||||
-rw-r--r-- | src/cflow.h | 11 | ||||
-rw-r--r-- | src/depmap.c | 118 | ||||
-rw-r--r-- | src/output.c | 117 | ||||
-rw-r--r-- | src/symbol.c | 41 |
5 files changed, 228 insertions, 60 deletions
diff --git a/src/Makefile.am b/src/Makefile.am index 7252ff8..ce4663d 100644 --- a/src/Makefile.am +++ b/src/Makefile.am @@ -15,24 +15,25 @@ # # You should have received a copy of the GNU General Public License # along with this program; if not, write to the Free Software # Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA # 02110-1301 USA. INCLUDES = -I$(top_srcdir)/lib -I../ -I../lib bin_PROGRAMS = cflow cflow_SOURCES = \ c.l\ cflow.h\ + depmap.c\ gnu.c\ linked-list.c\ main.c\ output.c\ parser.c\ parser.h\ posix.c\ rc.c\ symbol.c localedir = $(datadir)/locale diff --git a/src/cflow.h b/src/cflow.h index d933750..2593398 100644 --- a/src/cflow.h +++ b/src/cflow.h @@ -108,24 +108,25 @@ struct symbol { struct linked_list *ref_line; /* Referenced in */ int level; /* Block nesting level (for local vars), Parameter nesting level (for params) */ char *decl; /* Declaration */ enum storage storage; /* Storage type */ int arity; /* Number of parameters or -1 for variables */ int recursive; /* Is the function recursive */ + size_t ord; /* ordinal number */ struct linked_list *caller; /* List of callers */ struct linked_list *callee; /* List of callees */ }; /* Output flags */ #define PRINT_XREF 0x01 #define PRINT_TREE 0x02 #ifndef CFLOW_PREPROC # define CFLOW_PREPROC "/usr/bin/cpp" #endif @@ -163,25 +164,26 @@ extern int token_stack_increase; extern int symbol_count; extern unsigned input_file_count; Symbol *lookup(char*); Symbol *install(char*); Symbol *install_ident(char *name, enum storage storage); void ident_change_storage(Symbol *sp, enum storage storage); void delete_autos(int level); void delete_statics(void); void delete_parms(int level); void move_parms(int level); -int collect_symbols(Symbol ***, int (*sel)()); +size_t collect_symbols(Symbol ***, int (*sel)(), size_t rescnt); +size_t collect_functions(Symbol ***return_sym); struct linked_list *linked_list_create(linked_list_free_data_fp fun); void linked_list_destroy(struct linked_list **plist); void linked_list_append(struct linked_list **plist, void *data); void linked_list_prepend(struct linked_list **plist, void *data); void linked_list_iterate(struct linked_list **plist, int (*itr) (void *, void *), void *data); void linked_list_unlink(struct linked_list *list, struct linked_list_entry *ent); int data_in_list(void *data, struct linked_list *list); int get_token(void); @@ -189,24 +191,25 @@ int source(char *name); void init_lex(int debug_level); void set_preprocessor(const char *arg); void pp_option(const char *arg); void init_parse(void); int yyparse(void); void output(void); void newline(void); void print_level(int lev, int last); int globals_only(void); int include_symbol(Symbol *sym); +int symbol_is_function(Symbol *sym); void sourcerc(int *, char ***); typedef enum { cflow_output_init, cflow_output_begin, cflow_output_end, cflow_output_newline, cflow_output_separator, cflow_output_symbol, cflow_output_text } cflow_output_command; @@ -224,12 +227,18 @@ int register_output(const char *name, void *data, void *handler_data), void *handler_data); int select_output_driver (const char *name); void output_init(void); int gnu_output_handler(cflow_output_command cmd, FILE *outfile, int line, void *data, void *handler_data); int posix_output_handler(cflow_output_command cmd, FILE *outfile, int line, void *data, void *handler_data); + +typedef struct cflow_depmap *cflow_depmap_t; +cflow_depmap_t depmap_alloc(size_t count); +void depmap_set(cflow_depmap_t dmap, size_t row, size_t col); +int depmap_isset(cflow_depmap_t dmap, size_t row, size_t col); +void depmap_tc(cflow_depmap_t dmap); diff --git a/src/depmap.c b/src/depmap.c new file mode 100644 index 0000000..340d41f --- /dev/null +++ b/src/depmap.c @@ -0,0 +1,118 @@ +/* This file is part of GNU cflow. + Copyright (C) 2008, 2009 Sergey Poznyakoff + + GNU cflow 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 3, or (at your option) + any later version. + + GNU cflow 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 cflow. If not, see <http://www.gnu.org/licenses/>. */ + +#include <cflow.h> + +#ifndef CHAR_BIT +# define CHAR_BIT 8 +#endif +#define BITS_PER_WORD (sizeof(unsigned)*CHAR_BIT) + +#define WORDSIZE(n) (((n) + BITS_PER_WORD - 1) / BITS_PER_WORD) +#define SETBIT(x, i) ((x)[(i)/BITS_PER_WORD] |= (1<<((i) % BITS_PER_WORD))) +#define RESETBIT(x, i) ((x)[(i)/BITS_PER_WORD] &= ~(1<<((i) % BITS_PER_WORD))) +#define BITISSET(x, i) (((x)[(i)/BITS_PER_WORD] & (1<<((i) % BITS_PER_WORD))) != 0) + +static void +transitive_closure(unsigned *R, int n) +{ + register size_t rowsize; + register unsigned mask; + register unsigned *rowj; + register unsigned *rp; + register unsigned *rend; + register unsigned *ccol; + + unsigned *relend; + unsigned *cword; + unsigned *rowi; + + rowsize = WORDSIZE (n) * sizeof (unsigned); + relend = (unsigned *) ((char *) R + (n * rowsize)); + + cword = R; + mask = 1; + rowi = R; + while (rowi < relend) { + ccol = cword; + rowj = R; + + while (rowj < relend) { + if (*ccol & mask) { + rp = rowi; + rend = (unsigned *) ((char *) rowj + rowsize); + + while (rowj < rend) + *rowj++ |= *rp++; + } else { + rowj = (unsigned *) ((char *) rowj + rowsize); + } + + ccol = (unsigned *) ((char *) ccol + rowsize); + } + + mask <<= 1; + if (mask == 0) { + mask = 1; + cword++; + } + rowi = (unsigned *) ((char *) rowi + rowsize); + } +} + +struct cflow_depmap { + size_t nrows; + size_t rowlen; + unsigned r[1]; +}; + +cflow_depmap_t +depmap_alloc(size_t count) +{ + size_t size = (count + BITS_PER_WORD - 1) / BITS_PER_WORD; + cflow_depmap_t dmap = xzalloc(sizeof(*dmap) - 1 + + count * size * sizeof(unsigned)); + dmap->nrows = count; + dmap->rowlen = size; + return dmap; +} + +static unsigned * +depmap_rowptr(cflow_depmap_t dmap, size_t row) +{ + return dmap->r + dmap->rowlen * row; +} + +void +depmap_set(cflow_depmap_t dmap, size_t row, size_t col) +{ + unsigned *rptr = depmap_rowptr(dmap, row); + SETBIT(rptr, col); +} + +int +depmap_isset(cflow_depmap_t dmap, size_t row, size_t col) +{ + unsigned *rptr = depmap_rowptr(dmap, row); + return BITISSET(rptr, col); +} + +void +depmap_tc(cflow_depmap_t dmap) +{ + transitive_closure(dmap->r, dmap->nrows); +} + diff --git a/src/output.c b/src/output.c index f33d0ae..a617816 100644 --- a/src/output.c +++ b/src/output.c @@ -182,24 +182,30 @@ static int is_var(Symbol *symp) { if (include_symbol(symp)) { if (symp->type == SymIdentifier) return symp->storage == ExternStorage || symp->storage == StaticStorage; else return 1; } return 0; } +int +symbol_is_function(Symbol *symp) +{ + return symp->type == SymIdentifier && symp->arity >= 0; +} + static void clear_active(Symbol *sym) { sym->active = 0; } /* Cross-reference output */ void print_refs(char *name, struct linked_list *reflist) { Ref *refptr; @@ -232,70 +238,50 @@ print_type(Symbol *symp) { if (symp->source) fprintf(outfile, "%s t %s:%d\n", symp->name, symp->source, symp->def_line); } void xref_output() { Symbol **symbols, *symp; - int i, num; + size_t i, num; - num = collect_symbols(&symbols, is_var); + num = collect_symbols(&symbols, is_var, 0); qsort(symbols, num, sizeof(*symbols), compare); /* produce xref output */ for (i = 0; i < num; i++) { symp = symbols[i]; switch (symp->type) { case SymIdentifier: print_function(symp); break; case SymToken: print_type(symp); break; case SymUndefined: break; } } free(symbols); } /* Tree output */ -/* Scan call tree. Mark the recursive calls - */ -static void -scan_tree(int lev, Symbol *sym) -{ - struct linked_list_entry *p; - - if (sym->type == SymUndefined) - return; - if (sym->active) { - sym->recursive = 1; - return; - } - sym->active = 1; - for (p = linked_list_head(sym->callee); p; p = p->next) { - scan_tree(lev+1, (Symbol*)p->data); - } - sym->active = 0; -} - static void set_active(Symbol *sym) { sym->active = out_line; } static int is_printable(struct linked_list_entry *p) { return p != NULL && include_symbol((Symbol*)p->data); } @@ -352,61 +338,86 @@ inverted_tree(int lev, int last, Symbol *sym) set_active(sym); for (p = linked_list_head(sym->caller); p; p = p->next) { set_level_mark(lev+1, is_printable(p->next)); inverted_tree(lev+1, is_last(p), (Symbol*)p->data); } clear_active(sym); } static void tree_output() { Symbol **symbols, *main_sym; - int i, num; + size_t i, num; + cflow_depmap_t depmap; - /* Collect and sort symbols */ - num = collect_symbols(&symbols, is_var); - qsort(symbols, num, sizeof(*symbols), compare); - /* Scan and mark the recursive ones */ + /* Collect functions and assign them ordinal numbers */ + num = collect_functions(&symbols); + for (i = 0; i < num; i++) + symbols[i]->ord = i; + + /* Create a dependency matrix */ + depmap = depmap_alloc(num); for (i = 0; i < num; i++) { - if (symbols[i]->callee) - scan_tree(0, symbols[i]); + if (symbols[i]->callee) { + struct linked_list_entry *p; + + for (p = linked_list_head(symbols[i]->callee); p; + p = p->next) { + Symbol *s = (Symbol*) p->data; + if (symbol_is_function(s)) + depmap_set(depmap, i, ((Symbol*)p->data)->ord); + } + } } + depmap_tc(depmap); + + /* Mark recursive calls */ + for (i = 0; i < num; i++) + if (depmap_isset(depmap, i, i)) + symbols[i]->recursive = 1; + free(depmap); + free(symbols); + + /* Collect and sort all symbols */ + num = collect_symbols(&symbols, is_var, 0); + qsort(symbols, num, sizeof(*symbols), compare); + /* Produce output */ - begin(); - - if (reverse_tree) { - for (i = 0; i < num; i++) { - inverted_tree(0, 0, symbols[i]); - separator(); - } - } else { - main_sym = lookup(start_name); - if (main_sym) { - direct_tree(0, 0, main_sym); - separator(); - } else { - for (i = 0; i < num; i++) { - if (symbols[i]->callee == NULL) - continue; - direct_tree(0, 0, symbols[i]); - separator(); - } - } - } + begin(); - end(); - - free(symbols); + if (reverse_tree) { + for (i = 0; i < num; i++) { + inverted_tree(0, 0, symbols[i]); + separator(); + } + } else { + main_sym = lookup(start_name); + if (main_sym) { + direct_tree(0, 0, main_sym); + separator(); + } else { + for (i = 0; i < num; i++) { + if (symbols[i]->callee == NULL) + continue; + direct_tree(0, 0, symbols[i]); + separator(); + } + } + } + + end(); + + free(symbols); } void output() { if (strcmp(outname, "-") == 0) { outfile = stdout; } else { outfile = fopen(outname, "w"); if (!outfile) error(2, errno, _("cannot open file `%s'"), outname); } diff --git a/src/symbol.c b/src/symbol.c index 80c01a3..677f510 100644 --- a/src/symbol.c +++ b/src/symbol.c @@ -15,24 +15,25 @@ License along with GNU cflow; if not, write to the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA */ #include <cflow.h> #include <parser.h> #include <hash.h> static Hash_table *symbol_table; static struct linked_list *static_symbol_list; static struct linked_list *auto_symbol_list; +static struct linked_list *static_func_list; static void append_symbol(struct linked_list **plist, Symbol *sp) { if (sp->entry) { linked_list_unlink(sp->entry->list, sp->entry); sp->entry = NULL; } if (!data_in_list(sp, *plist)) { linked_list_append(plist, sp); sp->entry = (*plist)->tail; } @@ -198,29 +199,31 @@ delete_symbol(Symbol *sym) NOTE: This takes advantage of the fact that install() uses LIFO strategy, so we don't have to check the name of the source where the symbol was defined. */ static void static_free(void *data) { Symbol *sym = data; struct table_entry *t = sym->owner; if (!t) return; - if (sym->flag == symbol_temp - || globals_only()) + if (sym->flag == symbol_temp) delete_symbol(sym); - else + else { unlink_symbol(sym); + if (symbol_is_function(sym)) + linked_list_append(&static_func_list, sym); + } } void delete_statics() { if (static_symbol_list) { static_symbol_list->free_data = static_free; linked_list_destroy(&static_symbol_list); } } /* See NOTE above */ @@ -271,42 +274,68 @@ collect_processor(void *data, void *proc_data) struct collect_data *cd = proc_data; Symbol *s; for (s = t->sym; s; s = s->next) { if (cd->sel(s)) { if (cd->sym) cd->sym[cd->index] = s; cd->index++; } } return true; } -int -collect_symbols(Symbol ***return_sym, int (*sel)(Symbol *p)) +size_t +collect_symbols(Symbol ***return_sym, int (*sel)(Symbol *p), + size_t reserved_slots) { struct collect_data cdata; cdata.sym = NULL; cdata.index = 0; cdata.sel = sel; hash_do_for_each (symbol_table, collect_processor, &cdata); - cdata.sym = calloc(cdata.index, sizeof(*cdata.sym)); + cdata.sym = calloc(cdata.index + reserved_slots, sizeof(*cdata.sym)); if (!cdata.sym) xalloc_die(); cdata.index = 0; hash_do_for_each (symbol_table, collect_processor, &cdata); *return_sym = cdata.sym; return cdata.index; } +size_t +collect_functions(Symbol ***return_sym) +{ + Symbol **symbols; + size_t num, snum; + struct linked_list_entry *p; + + /* Count static functions */ + snum = 0; + if (static_func_list) + for (p = linked_list_head(static_func_list); p; p = p->next) + snum++; + + /* Collect global functions */ + num = collect_symbols(&symbols, symbol_is_function, snum); + + /* Collect static functions */ + if (snum) + for (p = linked_list_head(static_func_list); p; p = p->next) + symbols[num++] = p->data; + *return_sym = symbols; + return num; +} + + /* Special handling for function parameters */ int delete_parms_itr(void *data, void *call_data) { int level = *(int*)call_data; Symbol *s = data; struct table_entry *t = s->owner; if (!t) return 1; |