cg_arcs.c

来自「基于4个mips核的noc设计」· C语言 代码 · 共 686 行 · 第 1/2 页

  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
DEFUN (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
DEFUN (cmp_total, (lp, rp), const PTR lp AND 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 **
DEFUN_VOID (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;
}