summaryrefslogtreecommitdiffabout
authorSergey Poznyakoff <gray@gnu.org.ua>2009-11-08 23:50:43 (GMT)
committer Sergey Poznyakoff <gray@gnu.org.ua>2009-11-08 23:50:43 (GMT)
commitdc1a81526099095b12ef6edb655cf1a773dfa983 (patch) (side-by-side diff)
tree17defadb706683a3a59ee41428200ee66d91d34b
parent4d75955e833201c4f1d0219d48676521aeee1afa (diff)
downloadcflow-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.
Diffstat (more/less context) (show whitespace changes)
-rw-r--r--src/Makefile.am1
-rw-r--r--src/cflow.h11
-rw-r--r--src/depmap.c118
-rw-r--r--src/output.c69
-rw-r--r--src/symbol.c41
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
--- a/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 */

Return to:

Send suggestions and report system problems to the System administrator.