gprof/symtab.c

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