gprof/symtab.c

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