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