#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 (const PTR, const PTR);
static void propagate_time (Sym *);
static void cycle_time (void);
static void cycle_link (void);
static void inherit_flags (Sym *);
static void propagate_flags (Sym **);
static int cmp_total (const PTR, const PTR);
Sym *cycle_header;
unsigned int num_cycles;
Arc **arcs;
unsigned int numarcs;
Arc *
arc_lookup (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;
}
void
arc_add (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)
{
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 (parent != child)
{
if (numarcs == maxarcs)
{
if (maxarcs == 0)
maxarcs = 1;
maxarcs *= 2;
newarcs = (Arc **)xmalloc(sizeof (Arc *) * maxarcs);
memcpy (newarcs, arcs, numarcs * sizeof (Arc *));
free (arcs);
arcs = newarcs;
}
arcs[numarcs++] = arc;
}
arc->next_child = parent->cg.children;
parent->cg.children = arc;
arc->next_parent = child->cg.parents;
child->cg.parents = arc;
}
static int
cmp_topo (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 (Sym *parent)
{
Arc *arc;
Sym *child;
double share, prop_share;
if (parent->cg.prop.fract == 0.0)
{
return;
}
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;
}
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;
prop_share = parent->cg.prop.fract * share;
parent->cg.prop.child += prop_share;
arc->time *= parent->cg.prop.fract;
arc->child_time *= parent->cg.prop.fract;
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));
}
}
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)
{
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;
num_cycles = 0;
for (sym = symtab.base; sym < symtab.limit; ++sym)
{
if (sym->cg.cyc.head == sym && sym->cg.cyc.next)
{
++num_cycles;
}
}
cycle_header = (Sym *) xmalloc ((num_cycles + 1) * sizeof (Sym));
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;
cyc->cg.top_order = DFN_NAN;
cyc->cg.cyc.num = num;
cyc->cg.cyc.head = cyc;
cyc->cg.cyc.next = sym;
DBG (CYCLEDEBUG, printf ("[cycle_link] ");
print_name (sym);
printf (" is the head of cycle %d\n", num));
for (member = sym; member; member = member->cg.cyc.next)
{
member->cg.cyc.num = num;
member->cg.cyc.head = cyc;
}
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;
}
}
}
}
}
static void
inherit_flags (Sym *child)
{
Sym *head, *parent, *member;
Arc *arc;
head = child->cg.cyc.head;
if (child == head)
{
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 (child->ncalls != 0)
{
child->cg.prop.fract += parent->cg.prop.fract
* (((double) arc->count) / ((double) child->ncalls));
}
}
}
else
{
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 (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;
}
}
}
static void
propagate_flags (Sym **symbols)
{
int index;
Sym *old_head, *child;
old_head = 0;
for (index = symtab.len - 1; index >= 0; --index)
{
child = symbols[index];
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)
{
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
{
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)
{
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
{
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));
}
}
static int
cmp_total (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);
}
Sym **
cg_assemble ()
{
Sym *parent, **time_sorted_syms, **top_sorted_syms;
unsigned int index;
Arc *arc;
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);
}
}
for (parent = symtab.base; parent < symtab.limit; parent++)
{
if (parent->cg.top_order == DFN_NAN)
{
cg_dfn (parent);
}
}
cycle_link ();
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");
}
);
propagate_flags (top_sorted_syms);
cycle_time ();
for (index = 0; index < symtab.len; ++index)
{
propagate_time (top_sorted_syms[index]);
}
free (top_sorted_syms);
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;
}