Lots of changes from David Mosberger-Tang; see ChangeLog and NOTES for details:
[external/binutils.git] / gprof / sym_ids.c
1 #include "libiberty.h"
2 #include "cg_arcs.h"
3 #include "sym_ids.h"
4
5 struct sym_id {
6     struct sym_id       *next;
7     char                *spec;          /* parsing modifies this */
8     Table_Id            which_table;
9     bool                has_right;
10     struct match {
11         int             prev_index;             /* index of prev match */
12         Sym             *prev_match;            /* previous match */
13         Sym             *first_match;           /* chain of all matches */
14         Sym             sym;
15     } left, right;
16 } *id_list;
17
18 Sym_Table syms[NUM_TABLES];
19
20 #ifdef DEBUG
21 const char *table_name[] = {
22     "INCL_GRAPH", "EXCL_GRAPH",
23     "INCL_ARCS", "EXCL_ARCS",
24     "INCL_FLAT", "EXCL_FLAT",
25     "INCL_TIME", "EXCL_TIME",
26     "INCL_ANNO", "EXCL_ANNO",
27     "INCL_EXEC", "EXCL_EXEC"
28 };
29 #endif /* DEBUG */
30
31 /*
32  * This is the table in which we keep all the syms that match
33  * the right half of an arc id.  It is NOT sorted according
34  * to the addresses, because it is accessed only through
35  * the left half's CHILDREN pointers (so it's crucial not
36  * to reorder this table once pointers into it exist).
37  */
38 static Sym_Table right_ids;
39
40 static Source_File non_existent_file = {
41     0, "<non-existent-file>"
42 };
43
44
45 void
46 DEFUN(sym_id_add, (spec, which_table),
47       const char *spec AND Table_Id which_table)
48 {
49     struct sym_id *id;
50     int len = strlen(spec);
51
52     id = (struct sym_id*) xmalloc(sizeof(*id) + len + 1);
53     memset(id, 0, sizeof(*id));
54
55     id->spec = (char*)id + sizeof(*id);
56     strcpy(id->spec, spec);
57     id->which_table = which_table;
58
59     id->next = id_list;
60     id_list = id;
61 } /* sym_id_add */
62
63
64 /*
65  * A spec has the syntax FILENAME:(FUNCNAME|LINENUM).  As a convenience
66  * to the user, a spec without a colon is interpreted as:
67  *
68  *      (i)   a FILENAME if it contains a dot
69  *      (ii)  a FUNCNAME if it starts with a non-digit character
70  *      (iii) a LINENUM if it starts with a digit
71  *
72  * A FUNCNAME containing a dot can be specified by :FUNCNAME, a
73  * FILENAME not containing a dot can be specified by FILENAME:.
74  */
75 static void
76 DEFUN(parse_spec, (spec, sym), char *spec AND Sym *sym)
77 {
78     char *colon;
79
80     sym_init(sym);
81     colon = strrchr(spec, ':');
82     if (colon) {
83         *colon = '\0';
84         if (colon > spec) {
85             sym->file = source_file_lookup_name(spec);
86             if (!sym->file) {
87                 sym->file = &non_existent_file;
88             } /* if */
89         } /* if */
90         spec = colon + 1;
91         if (strlen(spec)) {
92             if (isdigit(spec[0])) {
93                 sym->line_num = atoi(spec);
94             } else {
95                 sym->name = spec;
96             } /* if */
97         } /* if */
98     } else if (strlen(spec)) {
99         /* no colon: spec is a filename if it contains a dot: */
100         if (strchr(spec, '.')) {
101             sym->file = source_file_lookup_name(spec);
102             if (!sym->file) {
103                 sym->file = &non_existent_file;
104             } /* if */
105         } else if (isdigit(*spec)) {
106             sym->line_num = atoi(spec);
107         } else if (strlen(spec)) {
108             sym->name = spec;
109         } /* if */
110     } /* if */
111 } /* parse_spec */
112
113
114 /*
115  * A symbol id has the syntax SPEC[/SPEC], where SPEC is is defined
116  * by parse_spec().
117  */
118 static void
119 DEFUN(parse_id, (id), struct sym_id *id)
120 {
121     char *slash;
122
123     DBG(IDDEBUG, printf("[parse_id] %s -> ", id->spec));
124
125     slash = strchr(id->spec, '/');
126     if (slash) {
127         parse_spec(slash + 1, &id->right.sym);
128         *slash = '\0';
129         id->has_right = TRUE;
130     } /* if */
131     parse_spec(id->spec, &id->left.sym);
132
133     DBG(IDDEBUG,
134         printf("%s:", id->left.sym.file ? id->left.sym.file->name : "*");
135         if (id->left.sym.name) {
136             printf("%s", id->left.sym.name);
137         } else if (id->left.sym.line_num) {
138             printf("%d", id->left.sym.line_num);
139         } else {
140             printf("*");
141         } /* if */
142         if (id->has_right) {
143             printf("/%s:",
144                    id->right.sym.file ? id->right.sym.file->name : "*");
145             if (id->right.sym.name) {
146                 printf("%s", id->right.sym.name);
147             } else if (id->right.sym.line_num) {
148                 printf("%d", id->right.sym.line_num);
149             } else {
150                 printf("*");
151             } /* if */
152         } /* if */
153         printf("\n"));
154 } /* parse_id */
155
156
157 /*
158  * Return TRUE iff PATTERN matches SYM.
159  */
160 static bool
161 DEFUN(match, (pattern, sym), Sym *pattern AND Sym *sym)
162 {
163     return (pattern->file ? pattern->file == sym->file : TRUE)
164       && (pattern->line_num ? pattern->line_num == sym->line_num : TRUE)
165         && (pattern->name ? strcmp(pattern->name, sym->name) == 0 : TRUE);
166 } /* match */
167
168
169 static void
170 DEFUN(extend_match, (m, sym, tab, second_pass),
171       struct match *m AND Sym *sym AND Sym_Table *tab AND bool second_pass)
172 {
173     if (m->prev_match != sym - 1) {
174         /* discontinuity: add new match to table: */
175         if (second_pass) {
176             tab->base[tab->len] = *sym;
177             m->prev_index = tab->len;
178
179             /* link match into match's chain: */
180             tab->base[tab->len].next = m->first_match;
181             m->first_match = &tab->base[tab->len];
182         } /* if */
183         ++tab->len;
184     } /* if */
185
186     /* extend match to include this symbol: */
187     if (second_pass) {
188         tab->base[m->prev_index].end_addr = sym->end_addr;
189     } /* if */
190     m->prev_match = sym;
191 } /* extend_match */
192
193
194 /*
195  * Go through sym_id list produced by option processing and fill
196  * in the various symbol tables indicating what symbols should
197  * be displayed or suppressed for the various kinds of outputs.
198  *
199  * This can potentially produce huge tables and in particulars
200  * tons of arcs, but this happens only if the user makes silly
201  * requests---you get what you ask for!
202  */
203 void
204 DEFUN_VOID(sym_id_parse)
205 {
206     Sym *sym, *left, *right;
207     struct sym_id *id;
208     Sym_Table *tab;
209
210     /*
211      * Convert symbol ids into Syms, so we can deal with them more easily:
212      */
213     for (id = id_list; id; id = id->next) {
214         parse_id(id);
215     } /* for */
216
217     /* first determine size of each table: */
218
219     for (sym = symtab.base; sym < symtab.limit; ++sym) {
220         for (id = id_list; id; id = id->next) {
221             if (match(&id->left.sym, sym)) {
222                 extend_match(&id->left, sym, &syms[id->which_table], FALSE);
223             } /* if */
224             if (id->has_right && match(&id->right.sym, sym)) {
225                 extend_match(&id->right, sym, &right_ids, FALSE);
226             } /* if */
227         } /* for */
228     } /* for */
229
230     /* create tables of appropriate size and reset lengths: */
231
232     for (tab = syms; tab < &syms[NUM_TABLES]; ++tab) {
233         if (tab->len) {
234             tab->base = (Sym*) xmalloc(tab->len * sizeof(Sym));
235             tab->limit = tab->base + tab->len;
236             tab->len = 0;
237         } /* if */
238     } /* for */
239     if (right_ids.len) {
240         right_ids.base = (Sym*) xmalloc(right_ids.len * sizeof(Sym));
241         right_ids.limit = right_ids.base + right_ids.len;
242         right_ids.len = 0;
243     } /* if */
244
245     /* make a second pass through symtab, creating syms as necessary: */
246
247     for (sym = symtab.base; sym < symtab.limit; ++sym) {
248         for (id = id_list; id; id = id->next) {
249             if (match(&id->left.sym, sym)) {
250                 extend_match(&id->left, sym, &syms[id->which_table], TRUE);
251             } /* if */
252             if (id->has_right && match(&id->right.sym, sym)) {
253                 extend_match(&id->right, sym, &right_ids, TRUE);
254             } /* if */
255         } /* for */
256     } /* for */
257
258     /* go through ids creating arcs as needed: */
259
260     for (id = id_list; id; id = id->next) {
261         if (id->has_right) {
262             for (left = id->left.first_match; left; left = left->next) {
263                 for (right = id->right.first_match; right; right = right->next)
264                 {
265                     DBG(IDDEBUG,
266                         printf(
267 "[sym_id_parse]: arc %s:%s(%lx-%lx) -> %s:%s(%lx-%lx) to %s\n",
268                                left->file ? left->file->name : "*",
269                                left->name ? left->name : "*", left->addr,
270                                left->end_addr,
271                                right->file ? right->file->name : "*",
272                                right->name ? right->name : "*", right->addr,
273                                right->end_addr,
274                                table_name[id->which_table]));
275                     arc_add(left, right, 0);
276                 } /* for */
277             } /* for */
278         } /* if */
279     } /* for */
280
281     /* finally, we can sort the tables and we're done: */
282
283     for (tab = &syms[0]; tab < &syms[NUM_TABLES]; ++tab) {
284         DBG(IDDEBUG, printf("[sym_id_parse] syms[%s]:\n",
285                             table_name[tab - &syms[0]]));
286         symtab_finalize(tab);
287     } /* for */
288 } /* sym_id_parse */
289
290
291 /*
292  * Symbol tables storing the FROM symbols of arcs do not necessarily
293  * have distinct address ranges.  For example, somebody might request
294  * -k /_mcount to suppress any arcs into _mcount, while at the same
295  * time requesting -k a/b.  Fortunately, those symbol tables don't get
296  * very big (the user has to type them!), so a linear search is probably
297  * tolerable.
298  */
299 bool
300 DEFUN(sym_id_arc_is_present, (symtab, from, to),
301       Sym_Table *symtab AND Sym *from AND Sym *to)
302 {
303     Sym *sym;
304
305     for (sym = symtab->base; sym < symtab->limit; ++sym) {
306         if (from->addr >= sym->addr && from->addr <= sym->end_addr
307             && arc_lookup(sym, to))
308         {
309             return TRUE;
310         } /* if */
311     } /* for */
312     return FALSE;
313 } /* sym_id_arc_is_present */
314
315                         /*** end of sym_ids.h ***/