[deliverable/binutils-gdb.git] / gprof / symtab.c

/* symtab.c

   Copyright 2000, 2001 Free Software Foundation, Inc.

   This file is part of GNU Binutils.

   This program is free software; you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
   the Free Software Foundation; either version 2 of the License, or
   (at your option) any later version.

   This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.

   You should have received a copy of the GNU General Public License
   along with this program; if not, write to the Free Software
   Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
   02111-1307, USA.  */
\f
#include "gprof.h"
#include "search_list.h"
#include "source.h"
#include "symtab.h"
#include "cg_arcs.h"
#include "corefile.h"

Sym_Table symtab;


/* Initialize a symbol (so it's empty).  */

void
DEFUN (sym_init, (sym), Sym * sym)
{
  memset (sym, 0, sizeof (*sym));

  /* It is not safe to assume that a binary zero corresponds
     to a floating-point 0.0, so initialize floats explicitly.  */
  sym->hist.time = 0.0;
  sym->cg.child_time = 0.0;
  sym->cg.prop.fract = 0.0;
  sym->cg.prop.self = 0.0;
  sym->cg.prop.child = 0.0;
}


/* Compare the function entry-point of two symbols and return <0, =0,
   or >0 depending on whether the left value is smaller than, equal
   to, or greater than the right value.  If two symbols are equal
   but one has is_func set and the other doesn't, we make the
   non-function symbol one "bigger" so that the function symbol will
   survive duplicate removal.  Finally, if both symbols have the
   same is_func value, we discriminate against is_static such that
   the global symbol survives.  */

static int
DEFUN (cmp_addr, (lp, rp), const PTR lp AND const PTR rp)
{
  Sym *left = (Sym *) lp;
  Sym *right = (Sym *) rp;

  if (left->addr > right->addr)
    return 1;
  else if (left->addr < right->addr)
    return -1;

  if (left->is_func != right->is_func)
    return right->is_func - left->is_func;

  return left->is_static - right->is_static;
}


void
DEFUN (symtab_finalize, (tab), Sym_Table * tab)
{
  Sym *src, *dst;
  bfd_vma prev_addr;

  if (!tab->len)
    return;

  /* Sort symbol table in order of increasing function addresses.  */
  qsort (tab->base, tab->len, sizeof (Sym), cmp_addr);

  /* Remove duplicate entries to speed-up later processing and
     set end_addr if its not set yet.  */
  prev_addr = tab->base[0].addr + 1;

  for (src = dst = tab->base; src < tab->limit; ++src)
    {
      if (src->addr == prev_addr)
	{
	  /* If same address, favor global symbol over static one,
	     then function over line number.  If both symbols are
	     either static or global and either function or line, check
	     whether one has name beginning with underscore while
	     the other doesn't.  In such cases, keep sym without
	     underscore.  This takes cares of compiler generated
	     symbols (such as __gnu_compiled, __c89_used, etc.).  */
	  if ((!src->is_static && dst[-1].is_static)
	      || ((src->is_static == dst[-1].is_static)
		  && ((src->is_func && !dst[-1].is_func)
		      || ((src->is_func == dst[-1].is_func)
			  && ((src->name[0] != '_' && dst[-1].name[0] == '_')
			      || (src->name[0]
				  && src->name[1] != '_'
				  && dst[-1].name[1] == '_'))))))
	    {
	      DBG (AOUTDEBUG | IDDEBUG,
		   printf ("[symtab_finalize] favor %s@%c%c over %s@%c%c",
			   src->name, src->is_static ? 't' : 'T',
			   src->is_func ? 'F' : 'f',
			   dst[-1].name, dst[-1].is_static ? 't' : 'T',
			   dst[-1].is_func ? 'F' : 'f');
		   printf (" (addr=%lx)\n", (unsigned long) src->addr));

	      dst[-1] = *src;
	    }
	  else
	    {
	      DBG (AOUTDEBUG | IDDEBUG,
		   printf ("[symtab_finalize] favor %s@%c%c over %s@%c%c",
			   dst[-1].name, dst[-1].is_static ? 't' : 'T',
			   dst[-1].is_func ? 'F' : 'f',
			   src->name, src->is_static ? 't' : 'T',
			   src->is_func ? 'F' : 'f');
		   printf (" (addr=%lx)\n", (unsigned long) src->addr));
	    }
	}
      else
	{
	  if (dst > tab->base && dst[-1].end_addr == 0)
	    dst[-1].end_addr = src->addr - 1;

	  /* Retain sym only if it has a non-empty address range.  */
	  if (!src->end_addr || src->addr <= src->end_addr)
	    {
	      *dst = *src;
	      dst++;
	      prev_addr = src->addr;
	    }
	}
    }

  if (tab->len > 0 && dst[-1].end_addr == 0)
    dst[-1].end_addr = core_text_sect->vma + core_text_sect->_raw_size - 1;

  DBG (AOUTDEBUG | IDDEBUG,
       printf ("[symtab_finalize]: removed %d duplicate entries\n",
	       tab->len - (int) (dst - tab->base)));

  tab->limit = dst;
  tab->len = tab->limit - tab->base;

  DBG (AOUTDEBUG | IDDEBUG,
       unsigned int j;

       for (j = 0; j < tab->len; ++j)
	 {
	   printf ("[symtab_finalize] 0x%lx-0x%lx\t%s\n",
		 (long) tab->base[j].addr, (long) tab->base[j].end_addr,
		 tab->base[j].name);
	 }
  );
}


#ifdef DEBUG

Sym *
DEFUN (dbg_sym_lookup, (symtab, address), Sym_Table * symtab AND bfd_vma address)
{
  long low, mid, high;
  Sym *sym;

  fprintf (stderr, "[dbg_sym_lookup] address 0x%lx\n",
	   (unsigned long) address);

  sym = symtab->base;
  for (low = 0, high = symtab->len - 1; low != high;)
    {
      mid = (high + low) >> 1;

      fprintf (stderr, "[dbg_sym_lookup] low=0x%lx, mid=0x%lx, high=0x%lx\n",
	       low, mid, high);
      fprintf (stderr, "[dbg_sym_lookup] sym[m]=0x%lx sym[m + 1]=0x%lx\n",
	       (unsigned long) sym[mid].addr,
	       (unsigned long) sym[mid + 1].addr);

      if (sym[mid].addr <= address && sym[mid + 1].addr > address)
	return &sym[mid];

      if (sym[mid].addr > address)
	high = mid;
      else
	low = mid + 1;
    }

  fprintf (stderr, "[dbg_sym_lookup] binary search fails???\n");

  return 0;
}

#endif	/* DEBUG */


/* Look up an address in the symbol-table that is sorted by address.
   If address does not hit any symbol, 0 is returned.  */
Sym *
DEFUN (sym_lookup, (symtab, address), Sym_Table * symtab AND bfd_vma address)
{
  long low, high;
  long mid = -1;
  Sym *sym;
#ifdef DEBUG
  int probes = 0;
#endif /* DEBUG */

  if (!symtab->len)
    return 0;

  sym = symtab->base;
  for (low = 0, high = symtab->len - 1; low != high;)
    {
      DBG (LOOKUPDEBUG, ++probes);
      mid = (high + low) / 2;

      if (sym[mid].addr <= address && sym[mid + 1].addr > address)
	{
	  if (address > sym[mid].end_addr)
	    {
	      /* Address falls into gap between
		 sym[mid] and sym[mid + 1].  */
	      return 0;
	    }
	  else
	    {
	      DBG (LOOKUPDEBUG,
		   printf ("[sym_lookup] %d probes (symtab->len=%u)\n",
			   probes, symtab->len - 1));
	      return &sym[mid];
	    }
	}

      if (sym[mid].addr > address)
	high = mid;
      else
	low = mid + 1;
    }

  if (sym[mid + 1].addr <= address)
    {
      if (address > sym[mid + 1].end_addr)
	{
	  /* Address is beyond end of sym[mid + 1].  */
	  return 0;
	}
      else
	{
	  DBG (LOOKUPDEBUG, printf ("[sym_lookup] %d (%u) probes, fall off\n",
				    probes, symtab->len - 1));
	  return &sym[mid + 1];
	}
    }

  return 0;
}
Commit	Line	Data
ef368dac NC	1	/* symtab.c
ef368dac NC	2
0eee5820	3	Copyright 2000, 2001 Free Software Foundation, Inc.
ef368dac NC	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
252b5132	22	#include "gprof.h"
6d9c411a AM	23	#include "search_list.h"
	24	#include "source.h"
	25	#include "symtab.h"
252b5132 RH	26	#include "cg_arcs.h"
252b5132 RH	27	#include "corefile.h"
252b5132 RH	28
	29	Sym_Table symtab;
	30
	31
ef368dac NC	32	/* Initialize a symbol (so it's empty). */
ef368dac NC	33
252b5132 RH	34	void
	35	DEFUN (sym_init, (sym), Sym * sym)
	36	{
	37	memset (sym, 0, sizeof (*sym));
0eee5820	38
ef368dac NC	39	/* It is not safe to assume that a binary zero corresponds
ef368dac NC	40	to a floating-point 0.0, so initialize floats explicitly. */
252b5132 RH	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
ef368dac NC	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
252b5132 RH	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)
ef368dac	65	return 1;
252b5132	66	else if (left->addr < right->addr)
ef368dac	67	return -1;
252b5132 RH	68
252b5132 RH	69	if (left->is_func != right->is_func)
ef368dac	70	return right->is_func - left->is_func;
252b5132 RH	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)
ef368dac	83	return;
252b5132	84
ef368dac	85	/* Sort symbol table in order of increasing function addresses. */
252b5132 RH	86	qsort (tab->base, tab->len, sizeof (Sym), cmp_addr);
252b5132 RH	87
ef368dac NC	88	/* Remove duplicate entries to speed-up later processing and
ef368dac NC	89	set end_addr if its not set yet. */
252b5132	90	prev_addr = tab->base[0].addr + 1;
0eee5820	91
252b5132 RH	92	for (src = dst = tab->base; src < tab->limit; ++src)
	93	{
	94	if (src->addr == prev_addr)
	95	{
ef368dac NC	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.). */
252b5132 RH	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');
fdcf7d43	118	printf (" (addr=%lx)\n", (unsigned long) src->addr));
0eee5820	119
252b5132 RH	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');
fdcf7d43	130	printf (" (addr=%lx)\n", (unsigned long) src->addr));
252b5132 RH	131	}
	132	}
	133	else
	134	{
	135	if (dst > tab->base && dst[-1].end_addr == 0)
ef368dac	136	dst[-1].end_addr = src->addr - 1;
252b5132	137
ef368dac	138	/* Retain sym only if it has a non-empty address range. */
252b5132 RH	139	if (!src->end_addr \|\| src->addr <= src->end_addr)
252b5132 RH	140	{
ccb57eba AM	141	dst = src;
ccb57eba AM	142	dst++;
252b5132 RH	143	prev_addr = src->addr;
	144	}
	145	}
	146	}
0eee5820	147
252b5132	148	if (tab->len > 0 && dst[-1].end_addr == 0)
ef368dac	149	dst[-1].end_addr = core_text_sect->vma + core_text_sect->_raw_size - 1;
252b5132 RH	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)
0eee5820	162	{
ef368dac NC	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);
0eee5820	166	}
252b5132 RH	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
fdcf7d43 ILT	179	fprintf (stderr, "[dbg_sym_lookup] address 0x%lx\n",
fdcf7d43 ILT	180	(unsigned long) address);
252b5132 RH	181
	182	sym = symtab->base;
	183	for (low = 0, high = symtab->len - 1; low != high;)
	184	{
	185	mid = (high + low) >> 1;
0eee5820	186
252b5132 RH	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",
fdcf7d43 ILT	190	(unsigned long) sym[mid].addr,
fdcf7d43 ILT	191	(unsigned long) sym[mid + 1].addr);
0eee5820	192
252b5132	193	if (sym[mid].addr <= address && sym[mid + 1].addr > address)
ef368dac NC	194	return &sym[mid];
ef368dac NC	195
252b5132	196	if (sym[mid].addr > address)
ef368dac	197	high = mid;
252b5132	198	else
ef368dac	199	low = mid + 1;
252b5132	200	}
0eee5820	201
252b5132	202	fprintf (stderr, "[dbg_sym_lookup] binary search fails???\n");
0eee5820	203
252b5132 RH	204	return 0;
	205	}
	206
	207	#endif /* DEBUG */
	208
	209
ef368dac NC	210	/* Look up an address in the symbol-table that is sorted by address.
ef368dac NC	211	If address does not hit any symbol, 0 is returned. */
252b5132 RH	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)
ef368dac	223	return 0;
252b5132 RH	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;
0eee5820	230
252b5132 RH	231	if (sym[mid].addr <= address && sym[mid + 1].addr > address)
	232	{
	233	if (address > sym[mid].end_addr)
	234	{
ef368dac NC	235	/* Address falls into gap between
ef368dac NC	236	sym[mid] and sym[mid + 1]. */
252b5132 RH	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	}
0eee5820	247
252b5132	248	if (sym[mid].addr > address)
ef368dac	249	high = mid;
252b5132	250	else
ef368dac	251	low = mid + 1;
252b5132	252	}
0eee5820	253
252b5132 RH	254	if (sym[mid + 1].addr <= address)
	255	{
	256	if (address > sym[mid + 1].end_addr)
	257	{
ef368dac	258	/* Address is beyond end of sym[mid + 1]. */
252b5132 RH	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	}
0eee5820	268
252b5132 RH	269	return 0;
252b5132 RH	270	}