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

/*
 * Copyright (c) 1983, 1993, 2001
 *      The Regents of the University of California.  All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 * 3. Neither the name of the University nor the names of its contributors
 *    may be used to endorse or promote products derived from this software
 *    without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 */
#include "libiberty.h"
#include "gprof.h"
#include "search_list.h"
#include "source.h"
#include "symtab.h"
#include "call_graph.h"
#include "cg_arcs.h"
#include "cg_dfn.h"
#include "cg_print.h"
#include "utils.h"
#include "sym_ids.h"

static int cmp_topo PARAMS ((const PTR, const PTR));
static void propagate_time PARAMS ((Sym *));
static void cycle_time PARAMS ((void));
static void cycle_link PARAMS ((void));
static void inherit_flags PARAMS ((Sym *));
static void propagate_flags PARAMS ((Sym **));
static int cmp_total PARAMS ((const PTR, const PTR));

Sym *cycle_header;
unsigned int num_cycles;
Arc **arcs;
unsigned int numarcs;

/*
 * Return TRUE iff PARENT has an arc to covers the address
 * range covered by CHILD.
 */
Arc *
arc_lookup (parent, child)
     Sym *parent;
     Sym *child;
{
  Arc *arc;

  if (!parent || !child)
    {
      printf ("[arc_lookup] parent == 0 || child == 0\n");
      return 0;
    }
  DBG (LOOKUPDEBUG, printf ("[arc_lookup] parent %s child %s\n",
			    parent->name, child->name));
  for (arc = parent->cg.children; arc; arc = arc->next_child)
    {
      DBG (LOOKUPDEBUG, printf ("[arc_lookup]\t parent %s child %s\n",
				arc->parent->name, arc->child->name));
      if (child->addr >= arc->child->addr
	  && child->end_addr <= arc->child->end_addr)
	{
	  return arc;
	}
    }
  return 0;
}


/*
 * Add (or just increment) an arc:
 */
void
arc_add (parent, child, count)
     Sym *parent;
     Sym *child;
     unsigned long count;
{
  static unsigned int maxarcs = 0;
  Arc *arc, **newarcs;

  DBG (TALLYDEBUG, printf ("[arc_add] %lu arcs from %s to %s\n",
			   count, parent->name, child->name));
  arc = arc_lookup (parent, child);
  if (arc)
    {
      /*
       * A hit: just increment the count.
       */
      DBG (TALLYDEBUG, printf ("[tally] hit %lu += %lu\n",
			       arc->count, count));
      arc->count += count;
      return;
    }
  arc = (Arc *) xmalloc (sizeof (*arc));
  memset (arc, 0, sizeof (*arc));
  arc->parent = parent;
  arc->child = child;
  arc->count = count;

  /* If this isn't an arc for a recursive call to parent, then add it
     to the array of arcs.  */
  if (parent != child)
    {
      /* If we've exhausted space in our current array, get a new one
	 and copy the contents.   We might want to throttle the doubling
	 factor one day.  */
      if (numarcs == maxarcs)
	{
	  /* Determine how much space we want to allocate.  */
	  if (maxarcs == 0)
	    maxarcs = 1;
	  maxarcs *= 2;

	  /* Allocate the new array.  */
	  newarcs = (Arc **)xmalloc(sizeof (Arc *) * maxarcs);

	  /* Copy the old array's contents into the new array.  */
	  memcpy (newarcs, arcs, numarcs * sizeof (Arc *));

	  /* Free up the old array.  */
	  free (arcs);

	  /* And make the new array be the current array.  */
	  arcs = newarcs;
	}

      /* Place this arc in the arc array.  */
      arcs[numarcs++] = arc;
    }

  /* prepend this child to the children of this parent: */
  arc->next_child = parent->cg.children;
  parent->cg.children = arc;

  /* prepend this parent to the parents of this child: */
  arc->next_parent = child->cg.parents;
  child->cg.parents = arc;
}


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

  return left->cg.top_order - right->cg.top_order;
}


static void
propagate_time (parent)
     Sym *parent;
{
  Arc *arc;
  Sym *child;
  double share, prop_share;

  if (parent->cg.prop.fract == 0.0)
    {
      return;
    }

  /* gather time from children of this parent: */

  for (arc = parent->cg.children; arc; arc = arc->next_child)
    {
      child = arc->child;
      if (arc->count == 0 || child == parent || child->cg.prop.fract == 0)
	{
	  continue;
	}
      if (child->cg.cyc.head != child)
	{
	  if (parent->cg.cyc.num == child->cg.cyc.num)
	    {
	      continue;
	    }
	  if (parent->cg.top_order <= child->cg.top_order)
	    {
	      fprintf (stderr, "[propagate] toporder botches\n");
	    }
	  child = child->cg.cyc.head;
	}
      else
	{
	  if (parent->cg.top_order <= child->cg.top_order)
	    {
	      fprintf (stderr, "[propagate] toporder botches\n");
	      continue;
	    }
	}
      if (child->ncalls == 0)
	{
	  continue;
	}

      /* distribute time for this arc: */
      arc->time = child->hist.time * (((double) arc->count)
				      / ((double) child->ncalls));
      arc->child_time = child->cg.child_time
	* (((double) arc->count) / ((double) child->ncalls));
      share = arc->time + arc->child_time;
      parent->cg.child_time += share;

      /* (1 - cg.prop.fract) gets lost along the way: */
      prop_share = parent->cg.prop.fract * share;

      /* fix things for printing: */
      parent->cg.prop.child += prop_share;
      arc->time *= parent->cg.prop.fract;
      arc->child_time *= parent->cg.prop.fract;

      /* add this share to the parent's cycle header, if any: */
      if (parent->cg.cyc.head != parent)
	{
	  parent->cg.cyc.head->cg.child_time += share;
	  parent->cg.cyc.head->cg.prop.child += prop_share;
	}
      DBG (PROPDEBUG,
	   printf ("[prop_time] child \t");
	   print_name (child);
	   printf (" with %f %f %lu/%lu\n", child->hist.time,
		   child->cg.child_time, arc->count, child->ncalls);
	   printf ("[prop_time] parent\t");
	   print_name (parent);
	   printf ("\n[prop_time] share %f\n", share));
    }
}


/*
 * Compute the time of a cycle as the sum of the times of all
 * its members.
 */
static void
cycle_time ()
{
  Sym *member, *cyc;

  for (cyc = &cycle_header[1]; cyc <= &cycle_header[num_cycles]; ++cyc)
    {
      for (member = cyc->cg.cyc.next; member; member = member->cg.cyc.next)
	{
	  if (member->cg.prop.fract == 0.0)
	    {
	      /*
	       * All members have the same propfraction except those
	       * that were excluded with -E.
	       */
	      continue;
	    }
	  cyc->hist.time += member->hist.time;
	}
      cyc->cg.prop.self = cyc->cg.prop.fract * cyc->hist.time;
    }
}


static void
cycle_link ()
{
  Sym *sym, *cyc, *member;
  Arc *arc;
  int num;

  /* count the number of cycles, and initialize the cycle lists: */

  num_cycles = 0;
  for (sym = symtab.base; sym < symtab.limit; ++sym)
    {
      /* this is how you find unattached cycles: */
      if (sym->cg.cyc.head == sym && sym->cg.cyc.next)
	{
	  ++num_cycles;
	}
    }

  /*
   * cycle_header is indexed by cycle number: i.e. it is origin 1,
   * not origin 0.
   */
  cycle_header = (Sym *) xmalloc ((num_cycles + 1) * sizeof (Sym));

  /*
   * Now link cycles to true cycle-heads, number them, accumulate
   * the data for the cycle.
   */
  num = 0;
  cyc = cycle_header;
  for (sym = symtab.base; sym < symtab.limit; ++sym)
    {
      if (!(sym->cg.cyc.head == sym && sym->cg.cyc.next != 0))
	{
	  continue;
	}
      ++num;
      ++cyc;
      sym_init (cyc);
      cyc->cg.print_flag = true;	/* should this be printed? */
      cyc->cg.top_order = DFN_NAN;	/* graph call chain top-sort order */
      cyc->cg.cyc.num = num;	/* internal number of cycle on */
      cyc->cg.cyc.head = cyc;	/* pointer to head of cycle */
      cyc->cg.cyc.next = sym;	/* pointer to next member of cycle */
      DBG (CYCLEDEBUG, printf ("[cycle_link] ");
	   print_name (sym);
	   printf (" is the head of cycle %d\n", num));

      /* link members to cycle header: */
      for (member = sym; member; member = member->cg.cyc.next)
	{
	  member->cg.cyc.num = num;
	  member->cg.cyc.head = cyc;
	}

      /*
       * Count calls from outside the cycle and those among cycle
       * members:
       */
      for (member = sym; member; member = member->cg.cyc.next)
	{
	  for (arc = member->cg.parents; arc; arc = arc->next_parent)
	    {
	      if (arc->parent == member)
		{
		  continue;
		}
	      if (arc->parent->cg.cyc.num == num)
		{
		  cyc->cg.self_calls += arc->count;
		}
	      else
		{
		  cyc->ncalls += arc->count;
		}
	    }
	}
    }
}


/*
 * Check if any parent of this child (or outside parents of this
 * cycle) have their print flags on and set the print flag of the
 * child (cycle) appropriately.  Similarly, deal with propagation
 * fractions from parents.
 */
static void
inherit_flags (child)
     Sym *child;
{
  Sym *head, *parent, *member;
  Arc *arc;

  head = child->cg.cyc.head;
  if (child == head)
    {
      /* just a regular child, check its parents: */
      child->cg.print_flag = false;
      child->cg.prop.fract = 0.0;
      for (arc = child->cg.parents; arc; arc = arc->next_parent)
	{
	  parent = arc->parent;
	  if (child == parent)
	    {
	      continue;
	    }
	  child->cg.print_flag |= parent->cg.print_flag;
	  /*
	   * If the child was never actually called (e.g., this arc
	   * is static (and all others are, too)) no time propagates
	   * along this arc.
	   */
	  if (child->ncalls != 0)
	    {
	      child->cg.prop.fract += parent->cg.prop.fract
		* (((double) arc->count) / ((double) child->ncalls));
	    }
	}
    }
  else
    {
      /*
       * Its a member of a cycle, look at all parents from outside
       * the cycle.
       */
      head->cg.print_flag = false;
      head->cg.prop.fract = 0.0;
      for (member = head->cg.cyc.next; member; member = member->cg.cyc.next)
	{
	  for (arc = member->cg.parents; arc; arc = arc->next_parent)
	    {
	      if (arc->parent->cg.cyc.head == head)
		{
		  continue;
		}
	      parent = arc->parent;
	      head->cg.print_flag |= parent->cg.print_flag;
	      /*
	       * If the cycle was never actually called (e.g. this
	       * arc is static (and all others are, too)) no time
	       * propagates along this arc.
	       */
	      if (head->ncalls != 0)
		{
		  head->cg.prop.fract += parent->cg.prop.fract
		    * (((double) arc->count) / ((double) head->ncalls));
		}
	    }
	}
      for (member = head; member; member = member->cg.cyc.next)
	{
	  member->cg.print_flag = head->cg.print_flag;
	  member->cg.prop.fract = head->cg.prop.fract;
	}
    }
}


/*
 * In one top-to-bottom pass over the topologically sorted symbols
 * propagate:
 *      cg.print_flag as the union of parents' print_flags
 *      propfraction as the sum of fractional parents' propfractions
 * and while we're here, sum time for functions.
 */
static void
propagate_flags (symbols)
     Sym **symbols;
{
  int index;
  Sym *old_head, *child;

  old_head = 0;
  for (index = symtab.len - 1; index >= 0; --index)
    {
      child = symbols[index];
      /*
       * If we haven't done this function or cycle, inherit things
       * from parent.  This way, we are linear in the number of arcs
       * since we do all members of a cycle (and the cycle itself)
       * as we hit the first member of the cycle.
       */
      if (child->cg.cyc.head != old_head)
	{
	  old_head = child->cg.cyc.head;
	  inherit_flags (child);
	}
      DBG (PROPDEBUG,
	   printf ("[prop_flags] ");
	   print_name (child);
	   printf ("inherits print-flag %d and prop-fract %f\n",
		   child->cg.print_flag, child->cg.prop.fract));
      if (!child->cg.print_flag)
	{
	  /*
	   * Printflag is off. It gets turned on by being in the
	   * INCL_GRAPH table, or there being an empty INCL_GRAPH
	   * table and not being in the EXCL_GRAPH table.
	   */
	  if (sym_lookup (&syms[INCL_GRAPH], child->addr)
	      || (syms[INCL_GRAPH].len == 0
		  && !sym_lookup (&syms[EXCL_GRAPH], child->addr)))
	    {
	      child->cg.print_flag = true;
	    }
	}
      else
	{
	  /*
	   * This function has printing parents: maybe someone wants
	   * to shut it up by putting it in the EXCL_GRAPH table.
	   * (But favor INCL_GRAPH over EXCL_GRAPH.)
	   */
	  if (!sym_lookup (&syms[INCL_GRAPH], child->addr)
	      && sym_lookup (&syms[EXCL_GRAPH], child->addr))
	    {
	      child->cg.print_flag = false;
	    }
	}
      if (child->cg.prop.fract == 0.0)
	{
	  /*
	   * No parents to pass time to.  Collect time from children
	   * if its in the INCL_TIME table, or there is an empty
	   * INCL_TIME table and its not in the EXCL_TIME table.
	   */
	  if (sym_lookup (&syms[INCL_TIME], child->addr)
	      || (syms[INCL_TIME].len == 0
		  && !sym_lookup (&syms[EXCL_TIME], child->addr)))
	    {
	      child->cg.prop.fract = 1.0;
	    }
	}
      else
	{
	  /*
	   * It has parents to pass time to, but maybe someone wants
	   * to shut it up by puttting it in the EXCL_TIME table.
	   * (But favor being in INCL_TIME tabe over being in
	   * EXCL_TIME table.)
	   */
	  if (!sym_lookup (&syms[INCL_TIME], child->addr)
	      && sym_lookup (&syms[EXCL_TIME], child->addr))
	    {
	      child->cg.prop.fract = 0.0;
	    }
	}
      child->cg.prop.self = child->hist.time * child->cg.prop.fract;
      print_time += child->cg.prop.self;
      DBG (PROPDEBUG,
	   printf ("[prop_flags] ");
	   print_name (child);
	   printf (" ends up with printflag %d and prop-fract %f\n",
		   child->cg.print_flag, child->cg.prop.fract);
	   printf ("[prop_flags] time %f propself %f print_time %f\n",
		   child->hist.time, child->cg.prop.self, print_time));
    }
}


/*
 * Compare by decreasing propagated time.  If times are equal, but one
 * is a cycle header, say that's first (e.g. less, i.e. -1).  If one's
 * name doesn't have an underscore and the other does, say that one is
 * first.  All else being equal, compare by names.
 */
static int
cmp_total (lp, rp)
     const PTR lp;
     const PTR rp;
{
  const Sym *left = *(const Sym **) lp;
  const Sym *right = *(const Sym **) rp;
  double diff;

  diff = (left->cg.prop.self + left->cg.prop.child)
    - (right->cg.prop.self + right->cg.prop.child);
  if (diff < 0.0)
    {
      return 1;
    }
  if (diff > 0.0)
    {
      return -1;
    }
  if (!left->name && left->cg.cyc.num != 0)
    {
      return -1;
    }
  if (!right->name && right->cg.cyc.num != 0)
    {
      return 1;
    }
  if (!left->name)
    {
      return -1;
    }
  if (!right->name)
    {
      return 1;
    }
  if (left->name[0] != '_' && right->name[0] == '_')
    {
      return -1;
    }
  if (left->name[0] == '_' && right->name[0] != '_')
    {
      return 1;
    }
  if (left->ncalls > right->ncalls)
    {
      return -1;
    }
  if (left->ncalls < right->ncalls)
    {
      return 1;
    }
  return strcmp (left->name, right->name);
}


/*
 * Topologically sort the graph (collapsing cycles), and propagates
 * time bottom up and flags top down.
 */
Sym **
cg_assemble ()
{
  Sym *parent, **time_sorted_syms, **top_sorted_syms;
  unsigned int index;
  Arc *arc;

  /*
   * initialize various things:
   *      zero out child times.
   *      count self-recursive calls.
   *      indicate that nothing is on cycles.
   */
  for (parent = symtab.base; parent < symtab.limit; parent++)
    {
      parent->cg.child_time = 0.0;
      arc = arc_lookup (parent, parent);
      if (arc && parent == arc->child)
	{
	  parent->ncalls -= arc->count;
	  parent->cg.self_calls = arc->count;
	}
      else
	{
	  parent->cg.self_calls = 0;
	}
      parent->cg.prop.fract = 0.0;
      parent->cg.prop.self = 0.0;
      parent->cg.prop.child = 0.0;
      parent->cg.print_flag = false;
      parent->cg.top_order = DFN_NAN;
      parent->cg.cyc.num = 0;
      parent->cg.cyc.head = parent;
      parent->cg.cyc.next = 0;
      if (ignore_direct_calls)
	{
	  find_call (parent, parent->addr, (parent + 1)->addr);
	}
    }
  /*
   * Topologically order things.  If any node is unnumbered, number
   * it and any of its descendents.
   */
  for (parent = symtab.base; parent < symtab.limit; parent++)
    {
      if (parent->cg.top_order == DFN_NAN)
	{
	  cg_dfn (parent);
	}
    }

  /* link together nodes on the same cycle: */
  cycle_link ();

  /* sort the symbol table in reverse topological order: */
  top_sorted_syms = (Sym **) xmalloc (symtab.len * sizeof (Sym *));
  for (index = 0; index < symtab.len; ++index)
    {
      top_sorted_syms[index] = &symtab.base[index];
    }
  qsort (top_sorted_syms, symtab.len, sizeof (Sym *), cmp_topo);
  DBG (DFNDEBUG,
       printf ("[cg_assemble] topological sort listing\n");
       for (index = 0; index < symtab.len; ++index)
       {
       printf ("[cg_assemble] ");
       printf ("%d:", top_sorted_syms[index]->cg.top_order);
       print_name (top_sorted_syms[index]);
       printf ("\n");
       }
  );
  /*
   * Starting from the topological top, propagate print flags to
   * children.  also, calculate propagation fractions.  this happens
   * before time propagation since time propagation uses the
   * fractions.
   */
  propagate_flags (top_sorted_syms);

  /*
   * Starting from the topological bottom, propogate children times
   * up to parents.
   */
  cycle_time ();
  for (index = 0; index < symtab.len; ++index)
    {
      propagate_time (top_sorted_syms[index]);
    }

  free (top_sorted_syms);

  /*
   * Now, sort by CG.PROP.SELF + CG.PROP.CHILD.  Sorting both the regular
   * function names and cycle headers.
   */
  time_sorted_syms = (Sym **) xmalloc ((symtab.len + num_cycles) * sizeof (Sym *));
  for (index = 0; index < symtab.len; index++)
    {
      time_sorted_syms[index] = &symtab.base[index];
    }
  for (index = 1; index <= num_cycles; index++)
    {
      time_sorted_syms[symtab.len + index - 1] = &cycle_header[index];
    }
  qsort (time_sorted_syms, symtab.len + num_cycles, sizeof (Sym *),
	 cmp_total);
  for (index = 0; index < symtab.len + num_cycles; index++)
    {
      time_sorted_syms[index]->cg.index = index + 1;
    }
  return time_sorted_syms;
}
Commit	Line	Data
252b5132	1	/*
5ec4a8f3 NC	2	* Copyright (c) 1983, 1993, 2001
5ec4a8f3 NC	3	* The Regents of the University of California. All rights reserved.
252b5132	4	*
5ec4a8f3 NC	5	* Redistribution and use in source and binary forms, with or without
	6	* modification, are permitted provided that the following conditions
	7	* are met:
	8	* 1. Redistributions of source code must retain the above copyright
	9	* notice, this list of conditions and the following disclaimer.
	10	* 2. Redistributions in binary form must reproduce the above copyright
	11	* notice, this list of conditions and the following disclaimer in the
	12	* documentation and/or other materials provided with the distribution.
	13	* 3. Neither the name of the University nor the names of its contributors
	14	* may be used to endorse or promote products derived from this software
	15	* without specific prior written permission.
	16	*
	17	* THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
	18	* ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
	19	* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
	20	* ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
	21	* FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
	22	* DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
	23	* OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
	24	* HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
	25	* LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
	26	* OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
	27	* SUCH DAMAGE.
252b5132 RH	28	*/
	29	#include "libiberty.h"
	30	#include "gprof.h"
6d9c411a AM	31	#include "search_list.h"
	32	#include "source.h"
	33	#include "symtab.h"
252b5132 RH	34	#include "call_graph.h"
	35	#include "cg_arcs.h"
	36	#include "cg_dfn.h"
	37	#include "cg_print.h"
	38	#include "utils.h"
	39	#include "sym_ids.h"
	40
1355568a AM	41	static int cmp_topo PARAMS ((const PTR, const PTR));
	42	static void propagate_time PARAMS ((Sym *));
	43	static void cycle_time PARAMS ((void));
	44	static void cycle_link PARAMS ((void));
	45	static void inherit_flags PARAMS ((Sym *));
	46	static void propagate_flags PARAMS ((Sym **));
	47	static int cmp_total PARAMS ((const PTR, const PTR));
	48
252b5132 RH	49	Sym *cycle_header;
	50	unsigned int num_cycles;
	51	Arc **arcs;
	52	unsigned int numarcs;
	53
	54	/*
	55	* Return TRUE iff PARENT has an arc to covers the address
	56	* range covered by CHILD.
	57	*/
	58	Arc *
1355568a AM	59	arc_lookup (parent, child)
	60	Sym *parent;
	61	Sym *child;
252b5132 RH	62	{
	63	Arc *arc;
	64
	65	if (!parent \|\| !child)
	66	{
	67	printf ("[arc_lookup] parent == 0 \|\| child == 0\n");
	68	return 0;
	69	}
	70	DBG (LOOKUPDEBUG, printf ("[arc_lookup] parent %s child %s\n",
	71	parent->name, child->name));
	72	for (arc = parent->cg.children; arc; arc = arc->next_child)
	73	{
	74	DBG (LOOKUPDEBUG, printf ("[arc_lookup]\t parent %s child %s\n",
	75	arc->parent->name, arc->child->name));
	76	if (child->addr >= arc->child->addr
	77	&& child->end_addr <= arc->child->end_addr)
	78	{
	79	return arc;
	80	}
	81	}
	82	return 0;
	83	}
	84
	85
	86	/*
	87	* Add (or just increment) an arc:
	88	*/
	89	void
1355568a AM	90	arc_add (parent, child, count)
	91	Sym *parent;
	92	Sym *child;
	93	unsigned long count;
252b5132 RH	94	{
	95	static unsigned int maxarcs = 0;
	96	Arc arc, *newarcs;
	97
	98	DBG (TALLYDEBUG, printf ("[arc_add] %lu arcs from %s to %s\n",
	99	count, parent->name, child->name));
	100	arc = arc_lookup (parent, child);
	101	if (arc)
	102	{
	103	/*
	104	* A hit: just increment the count.
	105	*/
	106	DBG (TALLYDEBUG, printf ("[tally] hit %lu += %lu\n",
	107	arc->count, count));
	108	arc->count += count;
	109	return;
	110	}
	111	arc = (Arc ) xmalloc (sizeof (arc));
	112	memset (arc, 0, sizeof (*arc));
	113	arc->parent = parent;
	114	arc->child = child;
	115	arc->count = count;
	116
	117	/* If this isn't an arc for a recursive call to parent, then add it
	118	to the array of arcs. */
	119	if (parent != child)
	120	{
	121	/* If we've exhausted space in our current array, get a new one
	122	and copy the contents. We might want to throttle the doubling
	123	factor one day. */
	124	if (numarcs == maxarcs)
	125	{
	126	/* Determine how much space we want to allocate. */
	127	if (maxarcs == 0)
	128	maxarcs = 1;
	129	maxarcs *= 2;
0eee5820	130
252b5132 RH	131	/* Allocate the new array. */
	132	newarcs = (Arc *)xmalloc(sizeof (Arc ) * maxarcs);
	133
	134	/* Copy the old array's contents into the new array. */
	135	memcpy (newarcs, arcs, numarcs * sizeof (Arc *));
	136
	137	/* Free up the old array. */
	138	free (arcs);
	139
	140	/* And make the new array be the current array. */
	141	arcs = newarcs;
	142	}
	143
	144	/* Place this arc in the arc array. */
	145	arcs[numarcs++] = arc;
	146	}
	147
	148	/* prepend this child to the children of this parent: */
	149	arc->next_child = parent->cg.children;
	150	parent->cg.children = arc;
	151
	152	/* prepend this parent to the parents of this child: */
	153	arc->next_parent = child->cg.parents;
	154	child->cg.parents = arc;
	155	}
	156
	157
	158	static int
1355568a AM	159	cmp_topo (lp, rp)
	160	const PTR lp;
	161	const PTR rp;
252b5132 RH	162	{
	163	const Sym left = (const Sym **) lp;
	164	const Sym right = (const Sym **) rp;
	165
	166	return left->cg.top_order - right->cg.top_order;
	167	}
	168
	169
	170	static void
1355568a AM	171	propagate_time (parent)
1355568a AM	172	Sym *parent;
252b5132 RH	173	{
	174	Arc *arc;
	175	Sym *child;
	176	double share, prop_share;
	177
	178	if (parent->cg.prop.fract == 0.0)
	179	{
	180	return;
	181	}
	182
	183	/* gather time from children of this parent: */
	184
	185	for (arc = parent->cg.children; arc; arc = arc->next_child)
	186	{
	187	child = arc->child;
	188	if (arc->count == 0 \|\| child == parent \|\| child->cg.prop.fract == 0)
	189	{
	190	continue;
	191	}
	192	if (child->cg.cyc.head != child)
	193	{
	194	if (parent->cg.cyc.num == child->cg.cyc.num)
	195	{
	196	continue;
	197	}
	198	if (parent->cg.top_order <= child->cg.top_order)
	199	{
	200	fprintf (stderr, "[propagate] toporder botches\n");
	201	}
	202	child = child->cg.cyc.head;
	203	}
	204	else
	205	{
	206	if (parent->cg.top_order <= child->cg.top_order)
	207	{
	208	fprintf (stderr, "[propagate] toporder botches\n");
	209	continue;
	210	}
	211	}
	212	if (child->ncalls == 0)
	213	{
	214	continue;
	215	}
	216
	217	/* distribute time for this arc: */
	218	arc->time = child->hist.time * (((double) arc->count)
	219	/ ((double) child->ncalls));
	220	arc->child_time = child->cg.child_time
	221	* (((double) arc->count) / ((double) child->ncalls));
	222	share = arc->time + arc->child_time;
	223	parent->cg.child_time += share;
	224
	225	/* (1 - cg.prop.fract) gets lost along the way: */
	226	prop_share = parent->cg.prop.fract * share;
	227
	228	/* fix things for printing: */
	229	parent->cg.prop.child += prop_share;
	230	arc->time *= parent->cg.prop.fract;
	231	arc->child_time *= parent->cg.prop.fract;
	232
	233	/* add this share to the parent's cycle header, if any: */
	234	if (parent->cg.cyc.head != parent)
	235	{
	236	parent->cg.cyc.head->cg.child_time += share;
237	parent->cg.cyc.head->cg.prop.child += prop_share;
238	}
239	DBG (PROPDEBUG,
240	printf ("[prop_time] child \t");
241	print_name (child);
242	printf (" with %f %f %lu/%lu\n", child->hist.time,
243	child->cg.child_time, arc->count, child->ncalls);
244	printf ("[prop_time] parent\t");
245	print_name (parent);
246	printf ("\n[prop_time] share %f\n", share));
247	}
248	}
249
250
251	/*
252	* Compute the time of a cycle as the sum of the times of all
253	* its members.
254	*/
255	static void
1355568a	256	cycle_time ()
252b5132 RH	257	{
	258	Sym member, cyc;
	259
	260	for (cyc = &cycle_header[1]; cyc <= &cycle_header[num_cycles]; ++cyc)
	261	{
	262	for (member = cyc->cg.cyc.next; member; member = member->cg.cyc.next)
	263	{
	264	if (member->cg.prop.fract == 0.0)
	265	{
	266	/*
	267	* All members have the same propfraction except those
	268	* that were excluded with -E.
	269	*/
	270	continue;
	271	}
	272	cyc->hist.time += member->hist.time;
	273	}
	274	cyc->cg.prop.self = cyc->cg.prop.fract * cyc->hist.time;
	275	}
	276	}
	277
	278
	279	static void
1355568a	280	cycle_link ()
252b5132 RH	281	{
	282	Sym sym, cyc, *member;
	283	Arc *arc;
	284	int num;
	285
	286	/* count the number of cycles, and initialize the cycle lists: */
	287
	288	num_cycles = 0;
	289	for (sym = symtab.base; sym < symtab.limit; ++sym)
	290	{
	291	/* this is how you find unattached cycles: */
	292	if (sym->cg.cyc.head == sym && sym->cg.cyc.next)
	293	{
	294	++num_cycles;
	295	}
	296	}
	297
	298	/*
	299	* cycle_header is indexed by cycle number: i.e. it is origin 1,
	300	* not origin 0.
	301	*/
	302	cycle_header = (Sym ) xmalloc ((num_cycles + 1) sizeof (Sym));
	303
	304	/*
	305	* Now link cycles to true cycle-heads, number them, accumulate
	306	* the data for the cycle.
	307	*/
	308	num = 0;
	309	cyc = cycle_header;
	310	for (sym = symtab.base; sym < symtab.limit; ++sym)
	311	{
	312	if (!(sym->cg.cyc.head == sym && sym->cg.cyc.next != 0))
	313	{
	314	continue;
	315	}
	316	++num;
	317	++cyc;
	318	sym_init (cyc);
bde52789	319	cyc->cg.print_flag = true; /* should this be printed? */
252b5132 RH	320	cyc->cg.top_order = DFN_NAN; /* graph call chain top-sort order */
	321	cyc->cg.cyc.num = num; /* internal number of cycle on */
	322	cyc->cg.cyc.head = cyc; /* pointer to head of cycle */
	323	cyc->cg.cyc.next = sym; /* pointer to next member of cycle */
	324	DBG (CYCLEDEBUG, printf ("[cycle_link] ");
	325	print_name (sym);
	326	printf (" is the head of cycle %d\n", num));
	327
	328	/* link members to cycle header: */
	329	for (member = sym; member; member = member->cg.cyc.next)
	330	{
	331	member->cg.cyc.num = num;
	332	member->cg.cyc.head = cyc;
	333	}
	334
	335	/*
	336	* Count calls from outside the cycle and those among cycle
	337	* members:
	338	*/
	339	for (member = sym; member; member = member->cg.cyc.next)
	340	{
	341	for (arc = member->cg.parents; arc; arc = arc->next_parent)
	342	{
	343	if (arc->parent == member)
	344	{
	345	continue;
	346	}
	347	if (arc->parent->cg.cyc.num == num)
	348	{
	349	cyc->cg.self_calls += arc->count;
	350	}
	351	else
	352	{
	353	cyc->ncalls += arc->count;
	354	}
	355	}
	356	}
	357	}
	358	}
	359
	360
	361	/*
	362	* Check if any parent of this child (or outside parents of this
	363	* cycle) have their print flags on and set the print flag of the
	364	* child (cycle) appropriately. Similarly, deal with propagation
	365	* fractions from parents.
	366	*/
	367	static void
1355568a AM	368	inherit_flags (child)
1355568a AM	369	Sym *child;
252b5132 RH	370	{
	371	Sym head, parent, *member;
	372	Arc *arc;
	373
	374	head = child->cg.cyc.head;
	375	if (child == head)
	376	{
	377	/* just a regular child, check its parents: */
bde52789	378	child->cg.print_flag = false;
252b5132 RH	379	child->cg.prop.fract = 0.0;
	380	for (arc = child->cg.parents; arc; arc = arc->next_parent)
	381	{
	382	parent = arc->parent;
	383	if (child == parent)
	384	{
	385	continue;
	386	}
	387	child->cg.print_flag \|= parent->cg.print_flag;
	388	/*
	389	* If the child was never actually called (e.g., this arc
	390	* is static (and all others are, too)) no time propagates
	391	* along this arc.
	392	*/
	393	if (child->ncalls != 0)
	394	{
	395	child->cg.prop.fract += parent->cg.prop.fract
	396	* (((double) arc->count) / ((double) child->ncalls));
	397	}
	398	}
	399	}
	400	else
	401	{
	402	/*
	403	* Its a member of a cycle, look at all parents from outside
	404	* the cycle.
	405	*/
bde52789	406	head->cg.print_flag = false;
252b5132 RH	407	head->cg.prop.fract = 0.0;
	408	for (member = head->cg.cyc.next; member; member = member->cg.cyc.next)
	409	{
	410	for (arc = member->cg.parents; arc; arc = arc->next_parent)
	411	{
	412	if (arc->parent->cg.cyc.head == head)
	413	{
	414	continue;
	415	}
	416	parent = arc->parent;
	417	head->cg.print_flag \|= parent->cg.print_flag;
	418	/*
	419	* If the cycle was never actually called (e.g. this
	420	* arc is static (and all others are, too)) no time
	421	* propagates along this arc.
	422	*/
	423	if (head->ncalls != 0)
	424	{
	425	head->cg.prop.fract += parent->cg.prop.fract
	426	* (((double) arc->count) / ((double) head->ncalls));
	427	}
	428	}
	429	}
	430	for (member = head; member; member = member->cg.cyc.next)
	431	{
	432	member->cg.print_flag = head->cg.print_flag;
	433	member->cg.prop.fract = head->cg.prop.fract;
	434	}
	435	}
	436	}
	437
	438
	439	/*
	440	* In one top-to-bottom pass over the topologically sorted symbols
	441	* propagate:
	442	* cg.print_flag as the union of parents' print_flags
	443	* propfraction as the sum of fractional parents' propfractions
	444	* and while we're here, sum time for functions.
	445	*/
	446	static void
1355568a AM	447	propagate_flags (symbols)
1355568a AM	448	Sym **symbols;
252b5132 RH	449	{
	450	int index;
	451	Sym old_head, child;
	452
	453	old_head = 0;
	454	for (index = symtab.len - 1; index >= 0; --index)
	455	{
	456	child = symbols[index];
	457	/*
	458	* If we haven't done this function or cycle, inherit things
	459	* from parent. This way, we are linear in the number of arcs
	460	* since we do all members of a cycle (and the cycle itself)
	461	* as we hit the first member of the cycle.
	462	*/
	463	if (child->cg.cyc.head != old_head)
	464	{
	465	old_head = child->cg.cyc.head;
	466	inherit_flags (child);
	467	}
	468	DBG (PROPDEBUG,
	469	printf ("[prop_flags] ");
	470	print_name (child);
	471	printf ("inherits print-flag %d and prop-fract %f\n",
	472	child->cg.print_flag, child->cg.prop.fract));
	473	if (!child->cg.print_flag)
	474	{
	475	/*
	476	* Printflag is off. It gets turned on by being in the
	477	* INCL_GRAPH table, or there being an empty INCL_GRAPH
	478	* table and not being in the EXCL_GRAPH table.
	479	*/
	480	if (sym_lookup (&syms[INCL_GRAPH], child->addr)
	481	\|\| (syms[INCL_GRAPH].len == 0
	482	&& !sym_lookup (&syms[EXCL_GRAPH], child->addr)))
	483	{
bde52789	484	child->cg.print_flag = true;
252b5132 RH	485	}
	486	}
	487	else
	488	{
	489	/*
	490	* This function has printing parents: maybe someone wants
	491	* to shut it up by putting it in the EXCL_GRAPH table.
	492	* (But favor INCL_GRAPH over EXCL_GRAPH.)
	493	*/
	494	if (!sym_lookup (&syms[INCL_GRAPH], child->addr)
	495	&& sym_lookup (&syms[EXCL_GRAPH], child->addr))
	496	{
bde52789	497	child->cg.print_flag = false;
252b5132 RH	498	}
	499	}
	500	if (child->cg.prop.fract == 0.0)
	501	{
	502	/*
	503	* No parents to pass time to. Collect time from children
	504	* if its in the INCL_TIME table, or there is an empty
	505	* INCL_TIME table and its not in the EXCL_TIME table.
	506	*/
	507	if (sym_lookup (&syms[INCL_TIME], child->addr)
	508	\|\| (syms[INCL_TIME].len == 0
	509	&& !sym_lookup (&syms[EXCL_TIME], child->addr)))
	510	{
	511	child->cg.prop.fract = 1.0;
	512	}
	513	}
	514	else
	515	{
	516	/*
	517	* It has parents to pass time to, but maybe someone wants
	518	* to shut it up by puttting it in the EXCL_TIME table.
	519	* (But favor being in INCL_TIME tabe over being in
	520	* EXCL_TIME table.)
	521	*/
	522	if (!sym_lookup (&syms[INCL_TIME], child->addr)
	523	&& sym_lookup (&syms[EXCL_TIME], child->addr))
	524	{
	525	child->cg.prop.fract = 0.0;
	526	}
	527	}
	528	child->cg.prop.self = child->hist.time * child->cg.prop.fract;
	529	print_time += child->cg.prop.self;
	530	DBG (PROPDEBUG,
	531	printf ("[prop_flags] ");
	532	print_name (child);
	533	printf (" ends up with printflag %d and prop-fract %f\n",
	534	child->cg.print_flag, child->cg.prop.fract);
	535	printf ("[prop_flags] time %f propself %f print_time %f\n",
	536	child->hist.time, child->cg.prop.self, print_time));
	537	}
	538	}
	539
	540
	541	/*
	542	* Compare by decreasing propagated time. If times are equal, but one
	543	* is a cycle header, say that's first (e.g. less, i.e. -1). If one's
	544	* name doesn't have an underscore and the other does, say that one is
	545	* first. All else being equal, compare by names.
	546	*/
	547	static int
1355568a AM	548	cmp_total (lp, rp)
	549	const PTR lp;
	550	const PTR rp;
252b5132 RH	551	{
	552	const Sym left = (const Sym **) lp;
	553	const Sym right = (const Sym **) rp;
	554	double diff;
	555
	556	diff = (left->cg.prop.self + left->cg.prop.child)
	557	- (right->cg.prop.self + right->cg.prop.child);
	558	if (diff < 0.0)
	559	{
	560	return 1;
	561	}
	562	if (diff > 0.0)
	563	{
	564	return -1;
	565	}
	566	if (!left->name && left->cg.cyc.num != 0)
	567	{
	568	return -1;
	569	}
	570	if (!right->name && right->cg.cyc.num != 0)
	571	{
	572	return 1;
	573	}
	574	if (!left->name)
	575	{
	576	return -1;
	577	}
	578	if (!right->name)
	579	{
	580	return 1;
	581	}
	582	if (left->name[0] != '_' && right->name[0] == '_')
	583	{
	584	return -1;
	585	}
	586	if (left->name[0] == '_' && right->name[0] != '_')
	587	{
	588	return 1;
	589	}
	590	if (left->ncalls > right->ncalls)
	591	{
	592	return -1;
	593	}
	594	if (left->ncalls < right->ncalls)
	595	{
	596	return 1;
	597	}
	598	return strcmp (left->name, right->name);
	599	}
	600
	601
	602	/*
	603	* Topologically sort the graph (collapsing cycles), and propagates
	604	* time bottom up and flags top down.
	605	*/
	606	Sym **
1355568a	607	cg_assemble ()
252b5132 RH	608	{
	609	Sym parent, time_sorted_syms, *top_sorted_syms;
	610	unsigned int index;
	611	Arc *arc;
	612
	613	/*
	614	* initialize various things:
	615	* zero out child times.
	616	* count self-recursive calls.
	617	* indicate that nothing is on cycles.
	618	*/
	619	for (parent = symtab.base; parent < symtab.limit; parent++)
	620	{
	621	parent->cg.child_time = 0.0;
	622	arc = arc_lookup (parent, parent);
	623	if (arc && parent == arc->child)
	624	{
	625	parent->ncalls -= arc->count;
	626	parent->cg.self_calls = arc->count;
	627	}
	628	else
	629	{
	630	parent->cg.self_calls = 0;
	631	}
	632	parent->cg.prop.fract = 0.0;
	633	parent->cg.prop.self = 0.0;
	634	parent->cg.prop.child = 0.0;
bde52789	635	parent->cg.print_flag = false;
252b5132 RH	636	parent->cg.top_order = DFN_NAN;
	637	parent->cg.cyc.num = 0;
	638	parent->cg.cyc.head = parent;
	639	parent->cg.cyc.next = 0;
	640	if (ignore_direct_calls)
	641	{
	642	find_call (parent, parent->addr, (parent + 1)->addr);
	643	}
	644	}
	645	/*
	646	* Topologically order things. If any node is unnumbered, number
	647	* it and any of its descendents.
	648	*/
	649	for (parent = symtab.base; parent < symtab.limit; parent++)
	650	{
	651	if (parent->cg.top_order == DFN_NAN)
	652	{
	653	cg_dfn (parent);
	654	}
	655	}
	656
	657	/* link together nodes on the same cycle: */
	658	cycle_link ();
	659
	660	/* sort the symbol table in reverse topological order: */
	661	top_sorted_syms = (Sym *) xmalloc (symtab.len sizeof (Sym *));
	662	for (index = 0; index < symtab.len; ++index)
	663	{
	664	top_sorted_syms[index] = &symtab.base[index];
	665	}
	666	qsort (top_sorted_syms, symtab.len, sizeof (Sym *), cmp_topo);
	667	DBG (DFNDEBUG,
	668	printf ("[cg_assemble] topological sort listing\n");
	669	for (index = 0; index < symtab.len; ++index)
	670	{
	671	printf ("[cg_assemble] ");
	672	printf ("%d:", top_sorted_syms[index]->cg.top_order);
	673	print_name (top_sorted_syms[index]);
	674	printf ("\n");
	675	}
	676	);
	677	/*
	678	* Starting from the topological top, propagate print flags to
	679	* children. also, calculate propagation fractions. this happens
	680	* before time propagation since time propagation uses the
	681	* fractions.
	682	*/
	683	propagate_flags (top_sorted_syms);
	684
	685	/*
	686	* Starting from the topological bottom, propogate children times
	687	* up to parents.
	688	*/
	689	cycle_time ();
	690	for (index = 0; index < symtab.len; ++index)
	691	{
	692	propagate_time (top_sorted_syms[index]);
	693	}
	694
	695	free (top_sorted_syms);
	696
	697	/*
	698	* Now, sort by CG.PROP.SELF + CG.PROP.CHILD. Sorting both the regular
	699	* function names and cycle headers.
700	*/
701	time_sorted_syms = (Sym *) xmalloc ((symtab.len + num_cycles) sizeof (Sym *));
702	for (index = 0; index < symtab.len; index++)
703	{
704	time_sorted_syms[index] = &symtab.base[index];
705	}
706	for (index = 1; index <= num_cycles; index++)
707	{
708	time_sorted_syms[symtab.len + index - 1] = &cycle_header[index];
709	}
710	qsort (time_sorted_syms, symtab.len + num_cycles, sizeof (Sym *),
711	cmp_total);
712	for (index = 0; index < symtab.len + num_cycles; index++)
713	{
714	time_sorted_syms[index]->cg.index = index + 1;
715	}
716	return time_sorted_syms;
717	}