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

/* symtab.c

   Copyright 1999, 2000, 2001, 2002, 2004, 2007, 2008
   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 3 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., 51 Franklin Street - Fifth Floor, Boston, MA
   02110-1301, USA.  */
\f
#include "gprof.h"
#include "search_list.h"
#include "source.h"
#include "symtab.h"
#include "cg_arcs.h"
#include "corefile.h"

static int cmp_addr (const PTR, const PTR);

Sym_Table symtab;


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

void
sym_init (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
cmp_addr (const PTR lp, const PTR rp)
{
  const Sym *left = (const Sym *) lp;
  const Sym *right = (const 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
symtab_finalize (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 + bfd_get_section_size (core_text_sect) - 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",
		   (unsigned long) tab->base[j].addr,
		   (unsigned long) tab->base[j].end_addr,
		   tab->base[j].name);
	 }
  );
}


#ifdef DEBUG

Sym *
dbg_sym_lookup (Sym_Table *sym_tab, bfd_vma address)
{
  unsigned long low, mid, high;
  Sym *sym;

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

  sym = sym_tab->base;
  for (low = 0, high = sym_tab->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 *
sym_lookup (Sym_Table *sym_tab, bfd_vma address)
{
  long low, high;
  long mid = -1;
  Sym *sym;
#ifdef DEBUG
  int probes = 0;
#endif /* DEBUG */

  if (!sym_tab->len)
    return 0;

  sym = sym_tab->base;
  for (low = 0, high = sym_tab->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, sym_tab->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, sym_tab->len - 1));
	  return &sym[mid + 1];
	}
    }

  return 0;
}
Commit	Line	Data
ef368dac NC	1	/* symtab.c
ef368dac NC	2
0af1713e AM	3	Copyright 1999, 2000, 2001, 2002, 2004, 2007, 2008
0af1713e AM	4	Free Software Foundation, Inc.
ef368dac NC	5
	6	This file is part of GNU Binutils.
	7
	8	This program is free software; you can redistribute it and/or modify
	9	it under the terms of the GNU General Public License as published by
651dbc76	10	the Free Software Foundation; either version 3 of the License, or
ef368dac NC	11	(at your option) any later version.
	12
	13	This program is distributed in the hope that it will be useful,
	14	but WITHOUT ANY WARRANTY; without even the implied warranty of
	15	MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
	16	GNU General Public License for more details.
	17
	18	You should have received a copy of the GNU General Public License
	19	along with this program; if not, write to the Free Software
44eb1801 NC	20	Foundation, Inc., 51 Franklin Street - Fifth Floor, Boston, MA
44eb1801 NC	21	02110-1301, USA. */
ef368dac	22	\f
252b5132	23	#include "gprof.h"
6d9c411a AM	24	#include "search_list.h"
	25	#include "source.h"
	26	#include "symtab.h"
252b5132 RH	27	#include "cg_arcs.h"
252b5132 RH	28	#include "corefile.h"
252b5132	29
3e8f6abf	30	static int cmp_addr (const PTR, const PTR);
1355568a	31
252b5132 RH	32	Sym_Table symtab;
	33
	34
ef368dac NC	35	/* Initialize a symbol (so it's empty). */
ef368dac NC	36
252b5132	37	void
3e8f6abf	38	sym_init (Sym *sym)
252b5132 RH	39	{
252b5132 RH	40	memset (sym, 0, sizeof (*sym));
0eee5820	41
ef368dac NC	42	/* It is not safe to assume that a binary zero corresponds
ef368dac NC	43	to a floating-point 0.0, so initialize floats explicitly. */
252b5132 RH	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
ef368dac NC	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
252b5132	61	static int
3e8f6abf	62	cmp_addr (const PTR lp, const PTR rp)
252b5132	63	{
1355568a AM	64	const Sym left = (const Sym ) lp;
1355568a AM	65	const Sym right = (const Sym ) rp;
252b5132 RH	66
252b5132 RH	67	if (left->addr > right->addr)
ef368dac	68	return 1;
252b5132	69	else if (left->addr < right->addr)
ef368dac	70	return -1;
252b5132 RH	71
252b5132 RH	72	if (left->is_func != right->is_func)
ef368dac	73	return right->is_func - left->is_func;
252b5132 RH	74
	75	return left->is_static - right->is_static;
	76	}
	77
	78
	79	void
3e8f6abf	80	symtab_finalize (Sym_Table *tab)
252b5132 RH	81	{
	82	Sym src, dst;
	83	bfd_vma prev_addr;
	84
	85	if (!tab->len)
ef368dac	86	return;
252b5132	87
ef368dac	88	/* Sort symbol table in order of increasing function addresses. */
252b5132 RH	89	qsort (tab->base, tab->len, sizeof (Sym), cmp_addr);
252b5132 RH	90
ef368dac NC	91	/* Remove duplicate entries to speed-up later processing and
ef368dac NC	92	set end_addr if its not set yet. */
252b5132	93	prev_addr = tab->base[0].addr + 1;
0eee5820	94
252b5132 RH	95	for (src = dst = tab->base; src < tab->limit; ++src)
	96	{
	97	if (src->addr == prev_addr)
	98	{
ef368dac NC	99	/* If same address, favor global symbol over static one,
	100	then function over line number. If both symbols are
	101	either static or global and either function or line, check
	102	whether one has name beginning with underscore while
	103	the other doesn't. In such cases, keep sym without
	104	underscore. This takes cares of compiler generated
	105	symbols (such as __gnu_compiled, __c89_used, etc.). */
252b5132 RH	106	if ((!src->is_static && dst[-1].is_static)
	107	\|\| ((src->is_static == dst[-1].is_static)
	108	&& ((src->is_func && !dst[-1].is_func)
	109	\|\| ((src->is_func == dst[-1].is_func)
	110	&& ((src->name[0] != '_' && dst[-1].name[0] == '_')
	111	\|\| (src->name[0]
	112	&& src->name[1] != '_'
	113	&& dst[-1].name[1] == '_'))))))
	114	{
	115	DBG (AOUTDEBUG \| IDDEBUG,
	116	printf ("[symtab_finalize] favor %s@%c%c over %s@%c%c",
	117	src->name, src->is_static ? 't' : 'T',
	118	src->is_func ? 'F' : 'f',
	119	dst[-1].name, dst[-1].is_static ? 't' : 'T',
	120	dst[-1].is_func ? 'F' : 'f');
fdcf7d43	121	printf (" (addr=%lx)\n", (unsigned long) src->addr));
0eee5820	122
252b5132 RH	123	dst[-1] = *src;
	124	}
	125	else
	126	{
	127	DBG (AOUTDEBUG \| IDDEBUG,
	128	printf ("[symtab_finalize] favor %s@%c%c over %s@%c%c",
	129	dst[-1].name, dst[-1].is_static ? 't' : 'T',
	130	dst[-1].is_func ? 'F' : 'f',
	131	src->name, src->is_static ? 't' : 'T',
	132	src->is_func ? 'F' : 'f');
fdcf7d43	133	printf (" (addr=%lx)\n", (unsigned long) src->addr));
252b5132 RH	134	}
	135	}
	136	else
	137	{
	138	if (dst > tab->base && dst[-1].end_addr == 0)
ef368dac	139	dst[-1].end_addr = src->addr - 1;
252b5132	140
ef368dac	141	/* Retain sym only if it has a non-empty address range. */
252b5132 RH	142	if (!src->end_addr \|\| src->addr <= src->end_addr)
252b5132 RH	143	{
ccb57eba AM	144	dst = src;
ccb57eba AM	145	dst++;
252b5132 RH	146	prev_addr = src->addr;
	147	}
	148	}
	149	}
0eee5820	150
252b5132	151	if (tab->len > 0 && dst[-1].end_addr == 0)
67cf9bc5 AM	152	dst[-1].end_addr
67cf9bc5 AM	153	= core_text_sect->vma + bfd_get_section_size (core_text_sect) - 1;
252b5132 RH	154
	155	DBG (AOUTDEBUG \| IDDEBUG,
	156	printf ("[symtab_finalize]: removed %d duplicate entries\n",
	157	tab->len - (int) (dst - tab->base)));
	158
	159	tab->limit = dst;
	160	tab->len = tab->limit - tab->base;
	161
	162	DBG (AOUTDEBUG \| IDDEBUG,
	163	unsigned int j;
	164
	165	for (j = 0; j < tab->len; ++j)
0eee5820	166	{
ef368dac	167	printf ("[symtab_finalize] 0x%lx-0x%lx\t%s\n",
0af1713e AM	168	(unsigned long) tab->base[j].addr,
	169	(unsigned long) tab->base[j].end_addr,
	170	tab->base[j].name);
0eee5820	171	}
252b5132 RH	172	);
	173	}
	174
	175
	176	#ifdef DEBUG
	177
	178	Sym *
3e8f6abf	179	dbg_sym_lookup (Sym_Table *sym_tab, bfd_vma address)
252b5132	180	{
0af1713e	181	unsigned long low, mid, high;
252b5132 RH	182	Sym *sym;
252b5132 RH	183
fdcf7d43 ILT	184	fprintf (stderr, "[dbg_sym_lookup] address 0x%lx\n",
fdcf7d43 ILT	185	(unsigned long) address);
252b5132	186
1355568a AM	187	sym = sym_tab->base;
1355568a AM	188	for (low = 0, high = sym_tab->len - 1; low != high;)
252b5132 RH	189	{
252b5132 RH	190	mid = (high + low) >> 1;
0eee5820	191
252b5132 RH	192	fprintf (stderr, "[dbg_sym_lookup] low=0x%lx, mid=0x%lx, high=0x%lx\n",
	193	low, mid, high);
	194	fprintf (stderr, "[dbg_sym_lookup] sym[m]=0x%lx sym[m + 1]=0x%lx\n",
fdcf7d43 ILT	195	(unsigned long) sym[mid].addr,
fdcf7d43 ILT	196	(unsigned long) sym[mid + 1].addr);
0eee5820	197
252b5132	198	if (sym[mid].addr <= address && sym[mid + 1].addr > address)
ef368dac NC	199	return &sym[mid];
ef368dac NC	200
252b5132	201	if (sym[mid].addr > address)
ef368dac	202	high = mid;
252b5132	203	else
ef368dac	204	low = mid + 1;
252b5132	205	}
0eee5820	206
252b5132	207	fprintf (stderr, "[dbg_sym_lookup] binary search fails???\n");
0eee5820	208
252b5132 RH	209	return 0;
	210	}
	211
	212	#endif /* DEBUG */
	213
	214
ef368dac NC	215	/* Look up an address in the symbol-table that is sorted by address.
ef368dac NC	216	If address does not hit any symbol, 0 is returned. */
252b5132	217	Sym *
3e8f6abf	218	sym_lookup (Sym_Table *sym_tab, bfd_vma address)
252b5132 RH	219	{
	220	long low, high;
	221	long mid = -1;
	222	Sym *sym;
	223	#ifdef DEBUG
	224	int probes = 0;
	225	#endif /* DEBUG */
	226
1355568a	227	if (!sym_tab->len)
ef368dac	228	return 0;
252b5132	229
1355568a AM	230	sym = sym_tab->base;
1355568a AM	231	for (low = 0, high = sym_tab->len - 1; low != high;)
252b5132 RH	232	{
	233	DBG (LOOKUPDEBUG, ++probes);
	234	mid = (high + low) / 2;
0eee5820	235
252b5132 RH	236	if (sym[mid].addr <= address && sym[mid + 1].addr > address)
	237	{
	238	if (address > sym[mid].end_addr)
	239	{
ef368dac NC	240	/* Address falls into gap between
ef368dac NC	241	sym[mid] and sym[mid + 1]. */
252b5132 RH	242	return 0;
	243	}
	244	else
	245	{
	246	DBG (LOOKUPDEBUG,
	247	printf ("[sym_lookup] %d probes (symtab->len=%u)\n",
1355568a	248	probes, sym_tab->len - 1));
252b5132 RH	249	return &sym[mid];
	250	}
	251	}
0eee5820	252
252b5132	253	if (sym[mid].addr > address)
ef368dac	254	high = mid;
252b5132	255	else
ef368dac	256	low = mid + 1;
252b5132	257	}
0eee5820	258
252b5132 RH	259	if (sym[mid + 1].addr <= address)
	260	{
	261	if (address > sym[mid + 1].end_addr)
	262	{
ef368dac	263	/* Address is beyond end of sym[mid + 1]. */
252b5132 RH	264	return 0;
	265	}
	266	else
	267	{
	268	DBG (LOOKUPDEBUG, printf ("[sym_lookup] %d (%u) probes, fall off\n",
1355568a	269	probes, sym_tab->len - 1));
252b5132 RH	270	return &sym[mid + 1];
	271	}
	272	}
0eee5820	273
252b5132 RH	274	return 0;
252b5132 RH	275	}