cg_arcs.c

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

/*
 * Copyright (c) 1983, 2001 Regents of the University of California.
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms are permitted
 * provided that: (1) source distributions retain this entire copyright
 * notice and comment, and (2) distributions including binaries display
 * the following acknowledgement:  ``This product includes software
 * developed by the University of California, Berkeley and its contributors''
 * in the documentation or other materials provided with the distribution
 * and in all advertising materials mentioning features or use of this
 * software. 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 ``AS IS'' AND WITHOUT ANY EXPRESS OR
 * IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED
 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
 */
#include "libiberty.h"
#include "gprof.h"
#include "call_graph.h"
#include "cg_arcs.h"
#include "cg_dfn.h"
#include "cg_print.h"
#include "utils.h"
#include "sym_ids.h"

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 *
DEFUN (arc_lookup, (parent, child), Sym * parent AND 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
DEFUN (arc_add, (parent, child, count),
       Sym * parent AND Sym * child AND 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
DEFUN (cmp_topo, (lp, rp), const PTR lp AND 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
DEFUN (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
DEFUN_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
DEFUN_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
DEFUN (inherit_flags, (child), Sym * child)
{
  Sym *head, *parent, *member;
  Arc *arc;