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) (unidiff)
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
@@ -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
--- a/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,43 +347,68 @@ static void
361tree_output() 347tree_output()
362{ 348{
363 Symbol **symbols, *main_sym; 349 Symbol **symbols, *main_sym;
364 int i, num; 350 size_t i, num;
351 cflow_depmap_t depmap;
365 352
366 /* Collect and sort symbols */ 353 /* Collect functions and assign them ordinal numbers */
367 num = collect_symbols(&symbols, is_var); 354 num = collect_functions(&symbols);
368 qsort(symbols, num, sizeof(*symbols), compare); 355 for (i = 0; i < num; i++)
369 /* Scan and mark the recursive ones */ 356 symbols[i]->ord = i;
357
358 /* Create a dependency matrix */
359 depmap = depmap_alloc(num);
370 for (i = 0; i < num; i++) { 360 for (i = 0; i < num; i++) {
371 if (symbols[i]->callee) 361 if (symbols[i]->callee) {
372 scan_tree(0, symbols[i]); 362 struct linked_list_entry *p;
363
364 for (p = linked_list_head(symbols[i]->callee); p;
365 p = p->next) {
366 Symbol *s = (Symbol*) p->data;
367 if (symbol_is_function(s))
368 depmap_set(depmap, i, ((Symbol*)p->data)->ord);
369 }
370 }
373 } 371 }
374 372
373 depmap_tc(depmap);
374
375 /* Mark recursive calls */
376 for (i = 0; i < num; i++)
377 if (depmap_isset(depmap, i, i))
378 symbols[i]->recursive = 1;
379 free(depmap);
380 free(symbols);
381
382 /* Collect and sort all symbols */
383 num = collect_symbols(&symbols, is_var, 0);
384 qsort(symbols, num, sizeof(*symbols), compare);
385
375 /* Produce output */ 386 /* Produce output */
376 begin(); 387 begin();
377
378 if (reverse_tree) {
379 for (i = 0; i < num; i++) {
380 inverted_tree(0, 0, symbols[i]);
381 separator();
382 }
383 } else {
384 main_sym = lookup(start_name);
385 if (main_sym) {
386 direct_tree(0, 0, main_sym);
387 separator();
388 } else {
389 for (i = 0; i < num; i++) {
390 if (symbols[i]->callee == NULL)
391 continue;
392 direct_tree(0, 0, symbols[i]);
393 separator();
394 }
395 }
396 }
397 388
398 end(); 389 if (reverse_tree) {
399 390 for (i = 0; i < num; i++) {
400 free(symbols); 391 inverted_tree(0, 0, symbols[i]);
392 separator();
393 }
394 } else {
395 main_sym = lookup(start_name);
396 if (main_sym) {
397 direct_tree(0, 0, main_sym);
398 separator();
399 } else {
400 for (i = 0; i < num; i++) {
401 if (symbols[i]->callee == NULL)
402 continue;
403 direct_tree(0, 0, symbols[i]);
404 separator();
405 }
406 }
407 }
408
409 end();
410
411 free(symbols);
401} 412}
402 413
403void 414void
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;
24 24
25static struct linked_list *static_symbol_list; 25static struct linked_list *static_symbol_list;
26static struct linked_list *auto_symbol_list; 26static struct linked_list *auto_symbol_list;
27static struct linked_list *static_func_list;
27 28
28static void 29static void
29append_symbol(struct linked_list **plist, Symbol *sp) 30append_symbol(struct linked_list **plist, Symbol *sp)
@@ -207,11 +208,13 @@ static_free(void *data)
207 208
208 if (!t) 209 if (!t)
209 return; 210 return;
210 if (sym->flag == symbol_temp 211 if (sym->flag == symbol_temp)
211 || globals_only())
212 delete_symbol(sym); 212 delete_symbol(sym);
213 else 213 else {
214 unlink_symbol(sym); 214 unlink_symbol(sym);
215 if (symbol_is_function(sym))
216 linked_list_append(&static_func_list, sym);
217 }
215} 218}
216 219
217void 220void
@@ -280,8 +283,9 @@ collect_processor(void *data, void *proc_data)
280 return true; 283 return true;
281} 284}
282 285
283int 286size_t
284collect_symbols(Symbol ***return_sym, int (*sel)(Symbol *p)) 287collect_symbols(Symbol ***return_sym, int (*sel)(Symbol *p),
288 size_t reserved_slots)
285{ 289{
286 struct collect_data cdata; 290 struct collect_data cdata;
287 291
@@ -289,7 +293,7 @@ collect_symbols(Symbol ***return_sym, int (*sel)(Symbol *p))
289 cdata.index = 0; 293 cdata.index = 0;
290 cdata.sel = sel; 294 cdata.sel = sel;
291 hash_do_for_each (symbol_table, collect_processor, &cdata); 295 hash_do_for_each (symbol_table, collect_processor, &cdata);
292 cdata.sym = calloc(cdata.index, sizeof(*cdata.sym)); 296 cdata.sym = calloc(cdata.index + reserved_slots, sizeof(*cdata.sym));
293 if (!cdata.sym) 297 if (!cdata.sym)
294 xalloc_die(); 298 xalloc_die();
295 cdata.index = 0; 299 cdata.index = 0;
@@ -298,6 +302,31 @@ collect_symbols(Symbol ***return_sym, int (*sel)(Symbol *p))
298 return cdata.index; 302 return cdata.index;
299} 303}
300 304
305size_t
306collect_functions(Symbol ***return_sym)
307{
308 Symbol **symbols;
309 size_t num, snum;
310 struct linked_list_entry *p;
311
312 /* Count static functions */
313 snum = 0;
314 if (static_func_list)
315 for (p = linked_list_head(static_func_list); p; p = p->next)
316 snum++;
317
318 /* Collect global functions */
319 num = collect_symbols(&symbols, symbol_is_function, snum);
320
321 /* Collect static functions */
322 if (snum)
323 for (p = linked_list_head(static_func_list); p; p = p->next)
324 symbols[num++] = p->data;
325 *return_sym = symbols;
326 return num;
327}
328
329
301 330
302/* Special handling for function parameters */ 331/* Special handling for function parameters */
303 332

Return to:

Send suggestions and report system problems to the System administrator.