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 | 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 | |||
24 | cflow_SOURCES = \ | 24 | cflow_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); | |||
172 | void delete_statics(void); | 173 | void delete_statics(void); |
173 | void delete_parms(int level); | 174 | void delete_parms(int level); |
174 | void move_parms(int level); | 175 | void move_parms(int level); |
175 | int collect_symbols(Symbol ***, int (*sel)()); | 176 | size_t collect_symbols(Symbol ***, int (*sel)(), size_t rescnt); |
177 | size_t collect_functions(Symbol ***return_sym); | ||
176 | struct linked_list *linked_list_create(linked_list_free_data_fp fun); | 178 | struct linked_list *linked_list_create(linked_list_free_data_fp fun); |
177 | void linked_list_destroy(struct linked_list **plist); | 179 | void linked_list_destroy(struct linked_list **plist); |
178 | void linked_list_append(struct linked_list **plist, void *data); | 180 | void linked_list_append(struct linked_list **plist, void *data); |
@@ -198,6 +200,7 @@ void newline(void); | |||
198 | void print_level(int lev, int last); | 200 | void print_level(int lev, int last); |
199 | int globals_only(void); | 201 | int globals_only(void); |
200 | int include_symbol(Symbol *sym); | 202 | int include_symbol(Symbol *sym); |
203 | int symbol_is_function(Symbol *sym); | ||
201 | 204 | ||
202 | void sourcerc(int *, char ***); | 205 | void 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 | |||
240 | typedef struct cflow_depmap *cflow_depmap_t; | ||
241 | cflow_depmap_t depmap_alloc(size_t count); | ||
242 | void depmap_set(cflow_depmap_t dmap, size_t row, size_t col); | ||
243 | int depmap_isset(cflow_depmap_t dmap, size_t row, size_t col); | ||
244 | 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 @@ | |||
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 | |||
29 | static void | ||
30 | transitive_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 | |||
76 | struct cflow_depmap { | ||
77 | size_t nrows; | ||
78 | size_t rowlen; | ||
79 | unsigned r[1]; | ||
80 | }; | ||
81 | |||
82 | cflow_depmap_t | ||
83 | depmap_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 | |||
93 | static unsigned * | ||
94 | depmap_rowptr(cflow_depmap_t dmap, size_t row) | ||
95 | { | ||
96 | return dmap->r + dmap->rowlen * row; | ||
97 | } | ||
98 | |||
99 | void | ||
100 | depmap_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 | |||
106 | int | ||
107 | depmap_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 | |||
113 | void | ||
114 | depmap_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 | ||
194 | int | ||
195 | symbol_is_function(Symbol *symp) | ||
196 | { | ||
197 | return symp->type == SymIdentifier && symp->arity >= 0; | ||
198 | } | ||
199 | |||
194 | static void | 200 | static void |
195 | clear_active(Symbol *sym) | 201 | clear_active(Symbol *sym) |
196 | { | 202 | { |
@@ -241,9 +247,9 @@ void | |||
241 | xref_output() | 247 | xref_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 | */ | ||
272 | static void | ||
273 | scan_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 | |||
290 | static void | 276 | static void |
291 | set_active(Symbol *sym) | 277 | set_active(Symbol *sym) |
292 | { | 278 | { |
@@ -361,16 +347,41 @@ static void | |||
361 | tree_output() | 347 | tree_output() |
362 | { |