aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorSergey Poznyakoff <gray@gnu.org.ua>2009-11-09 01:50:43 +0200
committerSergey Poznyakoff <gray@gnu.org.ua>2009-11-09 01:50:43 +0200
commitdc1a81526099095b12ef6edb655cf1a773dfa983 (patch)
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.
-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
24cflow_SOURCES = \ 24cflow_SOURCES = \
25 c.l\ 25 c.l\
26 cflow.h\ 26 cflow.h\
27 depmap.c\
27 gnu.c\ 28 gnu.c\
28 linked-list.c\ 29 linked-list.c\
29 main.c\ 30 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 {
117 variables */ 117 variables */
118 118
119 int recursive; /* Is the function recursive */ 119 int recursive; /* Is the function recursive */
120 size_t ord; /* ordinal number */
120 struct linked_list *caller; /* List of callers */ 121 struct linked_list *caller; /* List of callers */
121 struct linked_list *callee; /* List of callees */ 122 struct linked_list *callee; /* List of callees */
122}; 123};
@@ -172,7 +173,8 @@ void delete_autos(int level);
172void delete_statics(void); 173void delete_statics(void);
173void delete_parms(int level); 174void delete_parms(int level);
174void move_parms(int level); 175void move_parms(int level);
175int collect_symbols(Symbol ***, int (*sel)()); 176size_t collect_symbols(Symbol ***, int (*sel)(), size_t rescnt);
177size_t collect_functions(Symbol ***return_sym);
176struct linked_list *linked_list_create(linked_list_free_data_fp fun); 178struct linked_list *linked_list_create(linked_list_free_data_fp fun);
177void linked_list_destroy(struct linked_list **plist); 179void linked_list_destroy(struct linked_list **plist);
178void linked_list_append(struct linked_list **plist, void *data); 180void linked_list_append(struct linked_list **plist, void *data);
@@ -198,6 +200,7 @@ void newline(void);
198void print_level(int lev, int last); 200void print_level(int lev, int last);
199int globals_only(void); 201int globals_only(void);
200int include_symbol(Symbol *sym); 202int include_symbol(Symbol *sym);
203int symbol_is_function(Symbol *sym);
201 204
202void sourcerc(int *, char ***); 205void sourcerc(int *, char ***);
203 206
@@ -233,3 +236,9 @@ int posix_output_handler(cflow_output_command cmd,
233 FILE *outfile, int line, 236 FILE *outfile, int line,
234 void *data, void *handler_data); 237 void *data, void *handler_data);
235 238
239
240typedef struct cflow_depmap *cflow_depmap_t;
241cflow_depmap_t depmap_alloc(size_t count);
242void depmap_set(cflow_depmap_t dmap, size_t row, size_t col);
243int depmap_isset(cflow_depmap_t dmap, size_t row, size_t col);
244void 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 @@
1/* This file is part of GNU cflow.
2 Copyright (C) 2008, 2009 Sergey Poznyakoff
3
4 GNU cflow is free software; you can redistribute it and/or modify
5 it under the terms of the GNU General Public License as published by
6 the Free Software Foundation; either version 3, or (at your option)
7 any later version.
8
9 GNU cflow is distributed in the hope that it will be useful,
10 but WITHOUT ANY WARRANTY; without even the implied warranty of
11 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 GNU General Public License for more details.
13
14 You should have received a copy of the GNU General Public License
15 along with GNU cflow. If not, see <http://www.gnu.org/licenses/>. */
16
17#include <cflow.h>
18
19#ifndef CHAR_BIT
20# define CHAR_BIT 8
21#endif
22#define BITS_PER_WORD (sizeof(unsigned)*CHAR_BIT)
23
24#define WORDSIZE(n) (((n) + BITS_PER_WORD - 1) / BITS_PER_WORD)
25#define SETBIT(x, i) ((x)[(i)/BITS_PER_WORD] |= (1<<((i) % BITS_PER_WORD)))
26#define RESETBIT(x, i) ((x)[(i)/BITS_PER_WORD] &= ~(1<<((i) % BITS_PER_WORD)))
27#define BITISSET(x, i) (((x)[(i)/BITS_PER_WORD] & (1<<((i) % BITS_PER_WORD))) != 0)
28
29static void
30transitive_closure(unsigned *R, int n)
31{
32 register size_t rowsize;
33 register unsigned mask;
34 register unsigned *rowj;
35 register unsigned *rp;
36 register unsigned *rend;
37 register unsigned *ccol;
38
39 unsigned *relend;
40 unsigned *cword;
41 unsigned *rowi;
42
43 rowsize = WORDSIZE (n) * sizeof (unsigned);
44 relend = (unsigned *) ((char *) R + (n * rowsize));
45
46 cword = R;
47 mask = 1;
48 rowi = R;
49 while (rowi < relend) {
50 ccol = cword;
51 rowj = R;
52
53 while (rowj < relend) {
54 if (*ccol & mask) {
55 rp = rowi;
56 rend = (unsigned *) ((char *) rowj + rowsize);
57
58 while (rowj < rend)
59 *rowj++ |= *rp++;
60 } else {
61 rowj = (unsigned *) ((char *) rowj + rowsize);
62 }
63
64 ccol = (unsigned *) ((char *) ccol + rowsize);
65 }
66
67 mask <<= 1;
68 if (mask == 0) {
69 mask = 1;
70 cword++;
71 }
72 rowi = (unsigned *) ((char *) rowi + rowsize);
73 }
74}
75
76struct cflow_depmap {
77 size_t nrows;
78 size_t rowlen;
79 unsigned r[1];
80};
81
82cflow_depmap_t
83depmap_alloc(size_t count)
84{
85 size_t size = (count + BITS_PER_WORD - 1) / BITS_PER_WORD;
86 cflow_depmap_t dmap = xzalloc(sizeof(*dmap) - 1
87 + count * size * sizeof(unsigned));
88 dmap->nrows = count;
89 dmap->rowlen = size;
90 return dmap;
91}
92
93static unsigned *
94depmap_rowptr(cflow_depmap_t dmap, size_t row)
95{
96 return dmap->r + dmap->rowlen * row;
97}
98
99void
100depmap_set(cflow_depmap_t dmap, size_t row, size_t col)
101{
102 unsigned *rptr = depmap_rowptr(dmap, row);
103 SETBIT(rptr, col);
104}
105
106int
107depmap_isset(cflow_depmap_t dmap, size_t row, size_t col)
108{
109 unsigned *rptr = depmap_rowptr(dmap, row);
110 return BITISSET(rptr, col);
111}
112
113void
114depmap_tc(cflow_depmap_t dmap)
115{
116 transitive_closure(dmap->r, dmap->nrows);
117}
118
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)
191 return 0; 191 return 0;
192} 192}
193 193
194int
195symbol_is_function(Symbol *symp)
196{
197 return symp->type == SymIdentifier && symp->arity >= 0;
198}
199
194static void 200static void
195clear_active(Symbol *sym) 201clear_active(Symbol *sym)
196{ 202{
@@ -241,9 +247,9 @@ void
241xref_output() 247xref_output()
242{ 248{
243 Symbol **symbols, *symp; 249 Symbol **symbols, *symp;
244 int i, num; 250 size_t i, num;
245 251
246 num = collect_symbols(&symbols, is_var); 252 num = collect_symbols(&symbols, is_var, 0);
247 qsort(symbols, num, sizeof(*symbols), compare); 253 qsort(symbols, num, sizeof(*symbols), compare);
248 254
249 /* produce xref output */ 255 /* produce xref output */
@@ -267,26 +273,6 @@ xref_output()
267 273
268/* Tree output */ 274/* Tree output */
269 275
270/* Scan call tree. Mark the recursive calls
271 */
272static void
273scan_tree(int lev, Symbol *sym)
274{
275 struct linked_list_entry *p;
276
277 if (sym->type == SymUndefined)
278 return;
279 if (sym->active) {
280 sym->recursive = 1;
281 return;
282 }
283 sym->active = 1;
284 for (p = linked_list_head(sym->callee); p; p = p->next) {
285 scan_tree(lev+1, (Symbol*)p->data);
286 }
287 sym->active = 0;
288}
289
290static void 276static void
291set_active(Symbol *sym) 277set_active(Symbol *sym)
292{ 278{
@@ -361,16 +347,41 @@ static void
361tree_output() 347tree_output()
362{