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

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