123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687 |
- /*
- * 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 "gprof.h"
- #include "libiberty.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;
- /*
- * Return TRUE iff PARENT has an arc to covers the address
- * range covered by CHILD.
- */
- 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;
- }
- /*
- * Add (or just increment) an arc:
- */
- 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)
- {
- /*
- * 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 (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;
- }
- /* 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 (void)
- {
- 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 (void)
- {
- 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 (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 (Sym **symbols)
- {
- int sym_index;
- Sym *old_head, *child;
- old_head = 0;
- for (sym_index = symtab.len - 1; sym_index >= 0; --sym_index)
- {
- child = symbols[sym_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 (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 (void)
- {
- Sym *parent, **time_sorted_syms, **top_sorted_syms;
- unsigned int sym_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 (sym_index = 0; sym_index < symtab.len; ++sym_index)
- top_sorted_syms[sym_index] = &symtab.base[sym_index];
- qsort (top_sorted_syms, symtab.len, sizeof (Sym *), cmp_topo);
- DBG (DFNDEBUG,
- printf ("[cg_assemble] topological sort listing\n");
- for (sym_index = 0; sym_index < symtab.len; ++sym_index)
- {
- printf ("[cg_assemble] ");
- printf ("%d:", top_sorted_syms[sym_index]->cg.top_order);
- print_name (top_sorted_syms[sym_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, propagate children times
- up to parents. */
- cycle_time ();
- for (sym_index = 0; sym_index < symtab.len; ++sym_index)
- propagate_time (top_sorted_syms[sym_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 (sym_index = 0; sym_index < symtab.len; sym_index++)
- time_sorted_syms[sym_index] = &symtab.base[sym_index];
- for (sym_index = 1; sym_index <= num_cycles; sym_index++)
- time_sorted_syms[symtab.len + sym_index - 1] = &cycle_header[sym_index];
- qsort (time_sorted_syms, symtab.len + num_cycles, sizeof (Sym *),
- cmp_total);
- for (sym_index = 0; sym_index < symtab.len + num_cycles; sym_index++)
- time_sorted_syms[sym_index]->cg.index = sym_index + 1;
- return time_sorted_syms;
- }
|