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