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