Merge branch 'vendor/GCC44'
[dragonfly.git] / contrib / binutils-2.22 / gprof / sym_ids.c
1 /* sym_ids.c
2
3    Copyright 1999, 2000, 2001, 2002, 2004, 2007 Free Software Foundation, Inc.
4
5    This file is part of GNU Binutils.
6
7    This program is free software; you can redistribute it and/or modify
8    it under the terms of the GNU General Public License as published by
9    the Free Software Foundation; either version 3 of the License, or
10    (at your option) any later version.
11
12    This program is distributed in the hope that it will be useful,
13    but WITHOUT ANY WARRANTY; without even the implied warranty of
14    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15    GNU General Public License for more details.
16
17    You should have received a copy of the GNU General Public License
18    along with this program; if not, write to the Free Software
19    Foundation, Inc., 51 Franklin Street - Fifth Floor, Boston, MA
20    02110-1301, USA.  */
21 \f
22 #include "gprof.h"
23 #include "libiberty.h"
24 #include "safe-ctype.h"
25 #include "search_list.h"
26 #include "source.h"
27 #include "symtab.h"
28 #include "cg_arcs.h"
29 #include "sym_ids.h"
30 #include "corefile.h"
31
32 struct match
33   {
34     int prev_index;     /* Index of prev match.  */
35     Sym *prev_match;    /* Previous match.  */
36     Sym *first_match;   /* Chain of all matches.  */
37     Sym sym;
38   };
39
40 struct sym_id
41   {
42     struct sym_id *next;
43     char *spec;                 /* Parsing modifies this.  */
44     Table_Id which_table;
45     bfd_boolean has_right;
46
47     struct match left, right;
48   };
49
50 static struct sym_id  *id_list;
51
52 static void parse_spec
53   (char *, Sym *);
54 static void parse_id
55   (struct sym_id *);
56 static bfd_boolean match
57   (Sym *, Sym *);
58 static void extend_match
59   (struct match *, Sym *, Sym_Table *, bfd_boolean);
60
61
62 Sym_Table syms[NUM_TABLES];
63
64 #ifdef DEBUG
65 static const char *table_name[] =
66 {
67   "INCL_GRAPH", "EXCL_GRAPH",
68   "INCL_ARCS", "EXCL_ARCS",
69   "INCL_FLAT", "EXCL_FLAT",
70   "INCL_TIME", "EXCL_TIME",
71   "INCL_ANNO", "EXCL_ANNO",
72   "INCL_EXEC", "EXCL_EXEC"
73 };
74 #endif /* DEBUG */
75
76 /* This is the table in which we keep all the syms that match
77    the right half of an arc id.  It is NOT sorted according
78    to the addresses, because it is accessed only through
79    the left half's CHILDREN pointers (so it's crucial not
80    to reorder this table once pointers into it exist).  */
81 static Sym_Table right_ids;
82
83 static Source_File non_existent_file =
84 {
85   0, "<non-existent-file>", 0, 0, 0, NULL
86 };
87
88
89 void
90 sym_id_add (const char *spec, Table_Id which_table)
91 {
92   struct sym_id *id;
93   int len = strlen (spec);
94
95   id = (struct sym_id *) xmalloc (sizeof (*id) + len + 1);
96   memset (id, 0, sizeof (*id));
97
98   id->spec = (char *) id + sizeof (*id);
99   strcpy (id->spec, spec);
100   id->which_table = which_table;
101
102   id->next = id_list;
103   id_list = id;
104 }
105
106
107 /* A spec has the syntax FILENAME:(FUNCNAME|LINENUM).  As a convenience
108    to the user, a spec without a colon is interpreted as:
109
110         (i)   a FILENAME if it contains a dot
111         (ii)  a FUNCNAME if it starts with a non-digit character
112         (iii) a LINENUM if it starts with a digit
113
114    A FUNCNAME containing a dot can be specified by :FUNCNAME, a
115    FILENAME not containing a dot can be specified by FILENAME.  */
116
117 static void
118 parse_spec (char *spec, Sym *sym)
119 {
120   char *colon;
121
122   sym_init (sym);
123   colon = strrchr (spec, ':');
124
125   if (colon)
126     {
127       *colon = '\0';
128
129       if (colon > spec)
130         {
131           sym->file = source_file_lookup_name (spec);
132
133           if (!sym->file)
134             sym->file = &non_existent_file;
135         }
136
137       spec = colon + 1;
138
139       if (strlen (spec))
140         {
141           if (ISDIGIT (spec[0]))
142             sym->line_num = atoi (spec);
143           else
144             sym->name = spec;
145         }
146     }
147   else if (strlen (spec))
148     {
149       /* No colon: spec is a filename if it contains a dot.  */
150       if (strchr (spec, '.'))
151         {
152           sym->file = source_file_lookup_name (spec);
153
154           if (!sym->file)
155             sym->file = &non_existent_file;
156         }
157       else if (ISDIGIT (*spec))
158         {
159           sym->line_num = atoi (spec);
160         }
161       else if (strlen (spec))
162         {
163           sym->name = spec;
164         }
165     }
166 }
167
168
169 /* A symbol id has the syntax SPEC[/SPEC], where SPEC is is defined
170    by parse_spec().  */
171
172 static void
173 parse_id (struct sym_id *id)
174 {
175   char *slash;
176
177   DBG (IDDEBUG, printf ("[parse_id] %s -> ", id->spec));
178
179   slash = strchr (id->spec, '/');
180   if (slash)
181     {
182       parse_spec (slash + 1, &id->right.sym);
183       *slash = '\0';
184       id->has_right = TRUE;
185     }
186   parse_spec (id->spec, &id->left.sym);
187
188 #ifdef DEBUG
189   if (debug_level & IDDEBUG)
190     {
191       printf ("%s:", id->left.sym.file ? id->left.sym.file->name : "*");
192
193       if (id->left.sym.name)
194         printf ("%s", id->left.sym.name);
195       else if (id->left.sym.line_num)
196         printf ("%d", id->left.sym.line_num);
197       else
198         printf ("*");
199
200       if (id->has_right)
201         {
202           printf ("/%s:",
203                   id->right.sym.file ? id->right.sym.file->name : "*");
204
205           if (id->right.sym.name)
206             printf ("%s", id->right.sym.name);
207           else if (id->right.sym.line_num)
208             printf ("%d", id->right.sym.line_num);
209           else
210             printf ("*");
211         }
212
213       printf ("\n");
214     }
215 #endif
216 }
217
218
219 /* Return TRUE iff PATTERN matches SYM.  */
220
221 static bfd_boolean
222 match (Sym *pattern, Sym *sym)
223 {
224   if (pattern->file && pattern->file != sym->file)
225     return FALSE;
226   if (pattern->line_num && pattern->line_num != sym->line_num)
227     return FALSE;
228   if (pattern->name)
229     {
230       const char *sym_name = sym->name;
231       if (*sym_name && bfd_get_symbol_leading_char (core_bfd) == *sym_name)
232         sym_name++;
233       if (strcmp (pattern->name, sym_name) != 0)
234         return FALSE;
235     }
236   return TRUE;
237 }
238
239
240 static void
241 extend_match (struct match *m, Sym *sym, Sym_Table *tab, bfd_boolean second_pass)
242 {
243   if (m->prev_match != sym - 1)
244     {
245       /* Discontinuity: add new match to table.  */
246       if (second_pass)
247         {
248           tab->base[tab->len] = *sym;
249           m->prev_index = tab->len;
250
251           /* Link match into match's chain.  */
252           tab->base[tab->len].next = m->first_match;
253           m->first_match = &tab->base[tab->len];
254         }
255
256       ++tab->len;
257     }
258
259   /* Extend match to include this symbol.  */
260   if (second_pass)
261     tab->base[m->prev_index].end_addr = sym->end_addr;
262
263   m->prev_match = sym;
264 }
265
266
267 /* Go through sym_id list produced by option processing and fill
268    in the various symbol tables indicating what symbols should
269    be displayed or suppressed for the various kinds of outputs.
270
271    This can potentially produce huge tables and in particulars
272    tons of arcs, but this happens only if the user makes silly
273    requests---you get what you ask for!  */
274
275 void
276 sym_id_parse ()
277 {
278   Sym *sym, *left, *right;
279   struct sym_id *id;
280   Sym_Table *tab;
281
282   /* Convert symbol ids into Syms, so we can deal with them more easily.  */
283   for (id = id_list; id; id = id->next)
284     parse_id (id);
285
286   /* First determine size of each table.  */
287   for (sym = symtab.base; sym < symtab.limit; ++sym)
288     {
289       for (id = id_list; id; id = id->next)
290         {
291           if (match (&id->left.sym, sym))
292             extend_match (&id->left, sym, &syms[id->which_table], FALSE);
293
294           if (id->has_right && match (&id->right.sym, sym))
295             extend_match (&id->right, sym, &right_ids, FALSE);
296         }
297     }
298
299   /* Create tables of appropriate size and reset lengths.  */
300   for (tab = syms; tab < &syms[NUM_TABLES]; ++tab)
301     {
302       if (tab->len)
303         {
304           tab->base = (Sym *) xmalloc (tab->len * sizeof (Sym));
305           tab->limit = tab->base + tab->len;
306           tab->len = 0;
307         }
308     }
309
310   if (right_ids.len)
311     {
312       right_ids.base = (Sym *) xmalloc (right_ids.len * sizeof (Sym));
313       right_ids.limit = right_ids.base + right_ids.len;
314       right_ids.len = 0;
315     }
316
317   /* Make a second pass through symtab, creating syms as necessary.  */
318   for (sym = symtab.base; sym < symtab.limit; ++sym)
319     {
320       for (id = id_list; id; id = id->next)
321         {
322           if (match (&id->left.sym, sym))
323             extend_match (&id->left, sym, &syms[id->which_table], TRUE);
324
325           if (id->has_right && match (&id->right.sym, sym))
326             extend_match (&id->right, sym, &right_ids, TRUE);
327         }
328     }
329
330   /* Go through ids creating arcs as needed.  */
331   for (id = id_list; id; id = id->next)
332     {
333       if (id->has_right)
334         {
335           for (left = id->left.first_match; left; left = left->next)
336             {
337               for (right = id->right.first_match; right; right = right->next)
338                 {
339                   DBG (IDDEBUG,
340                        printf (
341                                 "[sym_id_parse]: arc %s:%s(%lx-%lx) -> %s:%s(%lx-%lx) to %s\n",
342                                 left->file ? left->file->name : "*",
343                                 left->name ? left->name : "*",
344                                 (unsigned long) left->addr,
345                                 (unsigned long) left->end_addr,
346                                 right->file ? right->file->name : "*",
347                                 right->name ? right->name : "*",
348                                 (unsigned long) right->addr,
349                                 (unsigned long) right->end_addr,
350                                 table_name[id->which_table]));
351
352                   arc_add (left, right, (unsigned long) 0);
353                 }
354             }
355         }
356     }
357
358   /* Finally, we can sort the tables and we're done.  */
359   for (tab = &syms[0]; tab < &syms[NUM_TABLES]; ++tab)
360     {
361       DBG (IDDEBUG, printf ("[sym_id_parse] syms[%s]:\n",
362                             table_name[tab - &syms[0]]));
363       symtab_finalize (tab);
364     }
365 }
366
367
368 /* Symbol tables storing the FROM symbols of arcs do not necessarily
369    have distinct address ranges.  For example, somebody might request
370    -k /_mcount to suppress any arcs into _mcount, while at the same
371    time requesting -k a/b.  Fortunately, those symbol tables don't get
372    very big (the user has to type them!), so a linear search is probably
373    tolerable.  */
374 bfd_boolean
375 sym_id_arc_is_present (Sym_Table *sym_tab, Sym *from, Sym *to)
376 {
377   Sym *sym;
378
379   for (sym = sym_tab->base; sym < sym_tab->limit; ++sym)
380     {
381       if (from->addr >= sym->addr && from->addr <= sym->end_addr
382           && arc_lookup (sym, to))
383         return TRUE;
384     }
385
386   return FALSE;
387 }