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) (ignore 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.c117
-rw-r--r--src/symbol.c41
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
@@ -26,2 +26,3 @@ cflow_SOURCES = \
cflow.h\
+ depmap.c\
gnu.c\
diff --git a/src/cflow.h b/src/cflow.h
index d933750..2593398 100644
--- a/src/cflow.h
+++ b/src/cflow.h
@@ -119,2 +119,3 @@ struct symbol {
int recursive; /* Is the function recursive */
+ size_t ord; /* ordinal number */
struct linked_list *caller; /* List of callers */
@@ -174,3 +175,4 @@ 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);
@@ -200,2 +202,3 @@ int globals_only(void);
int include_symbol(Symbol *sym);
+int symbol_is_function(Symbol *sym);
@@ -235 +238,7 @@ int posix_output_handler(cflow_output_command cmd,
+
+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
@@ -193,2 +193,8 @@ is_var(Symbol *symp)
+int
+symbol_is_function(Symbol *symp)
+{
+ return symp->type == SymIdentifier && symp->arity >= 0;
+}
+
static void
@@ -243,5 +249,5 @@ 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);
@@ -269,22 +275,2 @@ xref_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
@@ -363,39 +349,64 @@ 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);
}
diff --git a/src/symbol.c b/src/symbol.c
index 80c01a3..677f510 100644
--- a/src/symbol.c
+++ b/src/symbol.c
@@ -26,2 +26,3 @@ static struct linked_list *static_symbol_list;
static struct linked_list *auto_symbol_list;
+static struct linked_list *static_func_list;
@@ -209,7 +210,9 @@ static_free(void *data)
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);
+ }
}
@@ -282,4 +285,5 @@ collect_processor(void *data, void *proc_data)
-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)
{
@@ -291,3 +295,3 @@ collect_symbols(Symbol ***return_sym, int (*sel)(Symbol *p))
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)
@@ -300,2 +304,27 @@ collect_symbols(Symbol ***return_sym, int (*sel)(Symbol *p))
+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;
+}
+
+

Return to:

Send suggestions and report system problems to the System administrator.