diff options
-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 | 69 | ||||
-rw-r--r-- | src/symbol.c | 41 |
5 files changed, 204 insertions, 36 deletions
diff --git a/src/Makefile.am b/src/Makefile.am index 7252ff8..ce4663d 100644 --- a/src/Makefile.am +++ b/src/Makefile.am @@ -24,6 +24,7 @@ bin_PROGRAMS = cflow cflow_SOURCES = \ c.l\ cflow.h\ + depmap.c\ gnu.c\ linked-list.c\ main.c\ diff --git a/src/cflow.h b/src/cflow.h index d933750..2593398 100644 --- a/src/cflow.h +++ b/src/cflow.h @@ -117,6 +117,7 @@ struct symbol { 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 */ }; @@ -172,7 +173,8 @@ 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); @@ -198,6 +200,7 @@ 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 ***); @@ -233,3 +236,9 @@ 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 @@ -191,6 +191,12 @@ is_var(Symbol *symp) return 0; } +int +symbol_is_function(Symbol *symp) +{ + return symp->type == SymIdentifier && symp->arity >= 0; +} + static void clear_active(Symbol *sym) { @@ -241,9 +247,9 @@ 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 */ @@ -267,26 +273,6 @@ xref_output() /* 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) { @@ -361,16 +347,41 @@ 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(); diff --git a/src/symbol.c b/src/symbol.c index 80c01a3..677f510 100644 --- a/src/symbol.c +++ b/src/symbol.c @@ -24,6 +24,7 @@ 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) @@ -207,11 +208,13 @@ static_free(void *data) 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 @@ -280,8 +283,9 @@ collect_processor(void *data, void *proc_data) 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; @@ -289,7 +293,7 @@ collect_symbols(Symbol ***return_sym, int (*sel)(Symbol *p)) 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; @@ -298,6 +302,31 @@ collect_symbols(Symbol ***return_sym, int (*sel)(Symbol *p)) 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 */ |