This commit was generated by cvs2svn to track changes on a CVS vendor
[external/binutils.git] / gprof / symtab.c
1 #include "gprof.h"
2 #include "cg_arcs.h"
3 #include "corefile.h"
4 #include "symtab.h"
5
6 Sym_Table symtab;
7
8
9 /*
10  * Initialize a symbol (so it's empty).
11  */
12 void
13 DEFUN (sym_init, (sym), Sym * sym)
14 {
15   memset (sym, 0, sizeof (*sym));
16   /*
17    * It is not safe to assume that a binary zero corresponds to
18    * a floating-point 0.0, so initialize floats explicitly:
19    */
20   sym->hist.time = 0.0;
21   sym->cg.child_time = 0.0;
22   sym->cg.prop.fract = 0.0;
23   sym->cg.prop.self = 0.0;
24   sym->cg.prop.child = 0.0;
25 }
26
27
28 /*
29  * Compare the function entry-point of two symbols and return <0, =0,
30  * or >0 depending on whether the left value is smaller than, equal
31  * to, or greater than the right value.  If two symbols are equal
32  * but one has is_func set and the other doesn't, we make the
33  * non-function symbol one "bigger" so that the function symbol will
34  * survive duplicate removal.  Finally, if both symbols have the
35  * same is_func value, we discriminate against is_static such that
36  * the global symbol survives.
37  */
38 static int
39 DEFUN (cmp_addr, (lp, rp), const PTR lp AND const PTR rp)
40 {
41   Sym *left = (Sym *) lp;
42   Sym *right = (Sym *) rp;
43
44   if (left->addr > right->addr)
45     {
46       return 1;
47     }
48   else if (left->addr < right->addr)
49     {
50       return -1;
51     }
52
53   if (left->is_func != right->is_func)
54     {
55       return right->is_func - left->is_func;
56     }
57
58   return left->is_static - right->is_static;
59 }
60
61
62 void
63 DEFUN (symtab_finalize, (tab), Sym_Table * tab)
64 {
65   Sym *src, *dst;
66   bfd_vma prev_addr;
67
68   if (!tab->len)
69     {
70       return;
71     }
72
73   /*
74    * Sort symbol table in order of increasing function addresses:
75    */
76   qsort (tab->base, tab->len, sizeof (Sym), cmp_addr);
77
78   /*
79    * Remove duplicate entries to speed-up later processing and
80    * set end_addr if its not set yet:
81    */
82   prev_addr = tab->base[0].addr + 1;
83   for (src = dst = tab->base; src < tab->limit; ++src)
84     {
85       if (src->addr == prev_addr)
86         {
87           /*
88            * If same address, favor global symbol over static one,
89            * then function over line number.  If both symbols are
90            * either static or global and either function or line, check
91            * whether one has name beginning with underscore while
92            * the other doesn't.  In such cases, keep sym without
93            * underscore.  This takes cares of compiler generated
94            * symbols (such as __gnu_compiled, __c89_used, etc.).
95            */
96           if ((!src->is_static && dst[-1].is_static)
97               || ((src->is_static == dst[-1].is_static)
98                   && ((src->is_func && !dst[-1].is_func)
99                       || ((src->is_func == dst[-1].is_func)
100                           && ((src->name[0] != '_' && dst[-1].name[0] == '_')
101                               || (src->name[0]
102                                   && src->name[1] != '_'
103                                   && dst[-1].name[1] == '_'))))))
104             {
105               DBG (AOUTDEBUG | IDDEBUG,
106                    printf ("[symtab_finalize] favor %s@%c%c over %s@%c%c",
107                            src->name, src->is_static ? 't' : 'T',
108                            src->is_func ? 'F' : 'f',
109                            dst[-1].name, dst[-1].is_static ? 't' : 'T',
110                            dst[-1].is_func ? 'F' : 'f');
111                    printf (" (addr=%lx)\n", (unsigned long) src->addr));
112               dst[-1] = *src;
113             }
114           else
115             {
116               DBG (AOUTDEBUG | IDDEBUG,
117                    printf ("[symtab_finalize] favor %s@%c%c over %s@%c%c",
118                            dst[-1].name, dst[-1].is_static ? 't' : 'T',
119                            dst[-1].is_func ? 'F' : 'f',
120                            src->name, src->is_static ? 't' : 'T',
121                            src->is_func ? 'F' : 'f');
122                    printf (" (addr=%lx)\n", (unsigned long) src->addr));
123             }
124         }
125       else
126         {
127           if (dst > tab->base && dst[-1].end_addr == 0)
128             {
129               dst[-1].end_addr = src->addr - 1;
130             }
131
132           /* retain sym only if it has a non-empty address range: */
133           if (!src->end_addr || src->addr <= src->end_addr)
134             {
135               *dst++ = *src;
136               prev_addr = src->addr;
137             }
138         }
139     }
140   if (tab->len > 0 && dst[-1].end_addr == 0)
141     {
142       dst[-1].end_addr = core_text_sect->vma + core_text_sect->_raw_size - 1;
143     }
144
145   DBG (AOUTDEBUG | IDDEBUG,
146        printf ("[symtab_finalize]: removed %d duplicate entries\n",
147                tab->len - (int) (dst - tab->base)));
148
149   tab->limit = dst;
150   tab->len = tab->limit - tab->base;
151
152   DBG (AOUTDEBUG | IDDEBUG,
153        unsigned int j;
154
155        for (j = 0; j < tab->len; ++j)
156        {
157        printf ("[symtab_finalize] 0x%lx-0x%lx\t%s\n",
158                (long) tab->base[j].addr, (long) tab->base[j].end_addr,
159                tab->base[j].name);
160        }
161   );
162 }
163
164
165 #ifdef DEBUG
166
167 Sym *
168 DEFUN (dbg_sym_lookup, (symtab, address), Sym_Table * symtab AND bfd_vma address)
169 {
170   long low, mid, high;
171   Sym *sym;
172
173   fprintf (stderr, "[dbg_sym_lookup] address 0x%lx\n",
174            (unsigned long) address);
175
176   sym = symtab->base;
177   for (low = 0, high = symtab->len - 1; low != high;)
178     {
179       mid = (high + low) >> 1;
180       fprintf (stderr, "[dbg_sym_lookup] low=0x%lx, mid=0x%lx, high=0x%lx\n",
181                low, mid, high);
182       fprintf (stderr, "[dbg_sym_lookup] sym[m]=0x%lx sym[m + 1]=0x%lx\n",
183                (unsigned long) sym[mid].addr,
184                (unsigned long) sym[mid + 1].addr);
185       if (sym[mid].addr <= address && sym[mid + 1].addr > address)
186         {
187           return &sym[mid];
188         }
189       if (sym[mid].addr > address)
190         {
191           high = mid;
192         }
193       else
194         {
195           low = mid + 1;
196         }
197     }
198   fprintf (stderr, "[dbg_sym_lookup] binary search fails???\n");
199   return 0;
200 }
201
202 #endif  /* DEBUG */
203
204
205 /*
206  * Look up an address in the symbol-table that is sorted by address.
207  * If address does not hit any symbol, 0 is returned.
208  */
209 Sym *
210 DEFUN (sym_lookup, (symtab, address), Sym_Table * symtab AND bfd_vma address)
211 {
212   long low, high;
213   long mid = -1;
214   Sym *sym;
215 #ifdef DEBUG
216   int probes = 0;
217 #endif /* DEBUG */
218
219   if (!symtab->len)
220     {
221       return 0;
222     }
223
224   sym = symtab->base;
225   for (low = 0, high = symtab->len - 1; low != high;)
226     {
227       DBG (LOOKUPDEBUG, ++probes);
228       mid = (high + low) / 2;
229       if (sym[mid].addr <= address && sym[mid + 1].addr > address)
230         {
231           if (address > sym[mid].end_addr)
232             {
233               /*
234                * Address falls into gap between sym[mid] and
235                * sym[mid + 1]:
236                */
237               return 0;
238             }
239           else
240             {
241               DBG (LOOKUPDEBUG,
242                    printf ("[sym_lookup] %d probes (symtab->len=%u)\n",
243                            probes, symtab->len - 1));
244               return &sym[mid];
245             }
246         }
247       if (sym[mid].addr > address)
248         {
249           high = mid;
250         }
251       else
252         {
253           low = mid + 1;
254         }
255     }
256   if (sym[mid + 1].addr <= address)
257     {
258       if (address > sym[mid + 1].end_addr)
259         {
260           /* address is beyond end of sym[mid + 1]: */
261           return 0;
262         }
263       else
264         {
265           DBG (LOOKUPDEBUG, printf ("[sym_lookup] %d (%u) probes, fall off\n",
266                                     probes, symtab->len - 1));
267           return &sym[mid + 1];
268         }
269     }
270   return 0;
271 }