12a6b7db3Sskrll /*
22a6b7db3Sskrll * Copyright (c) 1983, 1993, 2001
32a6b7db3Sskrll * The Regents of the University of California. All rights reserved.
42a6b7db3Sskrll *
52a6b7db3Sskrll * Redistribution and use in source and binary forms, with or without
62a6b7db3Sskrll * modification, are permitted provided that the following conditions
72a6b7db3Sskrll * are met:
82a6b7db3Sskrll * 1. Redistributions of source code must retain the above copyright
92a6b7db3Sskrll * notice, this list of conditions and the following disclaimer.
102a6b7db3Sskrll * 2. Redistributions in binary form must reproduce the above copyright
112a6b7db3Sskrll * notice, this list of conditions and the following disclaimer in the
122a6b7db3Sskrll * documentation and/or other materials provided with the distribution.
132a6b7db3Sskrll * 3. Neither the name of the University nor the names of its contributors
142a6b7db3Sskrll * may be used to endorse or promote products derived from this software
152a6b7db3Sskrll * without specific prior written permission.
162a6b7db3Sskrll *
172a6b7db3Sskrll * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
182a6b7db3Sskrll * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
192a6b7db3Sskrll * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
202a6b7db3Sskrll * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
212a6b7db3Sskrll * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
222a6b7db3Sskrll * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
232a6b7db3Sskrll * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
242a6b7db3Sskrll * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
252a6b7db3Sskrll * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
262a6b7db3Sskrll * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
272a6b7db3Sskrll * SUCH DAMAGE.
282a6b7db3Sskrll */
292a6b7db3Sskrll #include "gprof.h"
302a6b7db3Sskrll #include "libiberty.h"
312a6b7db3Sskrll #include "search_list.h"
322a6b7db3Sskrll #include "source.h"
332a6b7db3Sskrll #include "symtab.h"
342a6b7db3Sskrll #include "call_graph.h"
352a6b7db3Sskrll #include "cg_arcs.h"
362a6b7db3Sskrll #include "cg_dfn.h"
372a6b7db3Sskrll #include "cg_print.h"
382a6b7db3Sskrll #include "utils.h"
392a6b7db3Sskrll #include "sym_ids.h"
402a6b7db3Sskrll
41*f22f0ef4Schristos static int cmp_topo (const void *, const void *);
422a6b7db3Sskrll static void propagate_time (Sym *);
432a6b7db3Sskrll static void cycle_time (void);
442a6b7db3Sskrll static void cycle_link (void);
452a6b7db3Sskrll static void inherit_flags (Sym *);
462a6b7db3Sskrll static void propagate_flags (Sym **);
47*f22f0ef4Schristos static int cmp_total (const void *, const void *);
482a6b7db3Sskrll
492a6b7db3Sskrll Sym *cycle_header;
502a6b7db3Sskrll unsigned int num_cycles;
512a6b7db3Sskrll Arc **arcs;
522a6b7db3Sskrll unsigned int numarcs;
532a6b7db3Sskrll
542a6b7db3Sskrll /*
552a6b7db3Sskrll * Return TRUE iff PARENT has an arc to covers the address
562a6b7db3Sskrll * range covered by CHILD.
572a6b7db3Sskrll */
582a6b7db3Sskrll Arc *
arc_lookup(Sym * parent,Sym * child)592a6b7db3Sskrll arc_lookup (Sym *parent, Sym *child)
602a6b7db3Sskrll {
612a6b7db3Sskrll Arc *arc;
622a6b7db3Sskrll
632a6b7db3Sskrll if (!parent || !child)
642a6b7db3Sskrll {
652a6b7db3Sskrll printf ("[arc_lookup] parent == 0 || child == 0\n");
662a6b7db3Sskrll return 0;
672a6b7db3Sskrll }
682a6b7db3Sskrll DBG (LOOKUPDEBUG, printf ("[arc_lookup] parent %s child %s\n",
692a6b7db3Sskrll parent->name, child->name));
702a6b7db3Sskrll for (arc = parent->cg.children; arc; arc = arc->next_child)
712a6b7db3Sskrll {
722a6b7db3Sskrll DBG (LOOKUPDEBUG, printf ("[arc_lookup]\t parent %s child %s\n",
732a6b7db3Sskrll arc->parent->name, arc->child->name));
742a6b7db3Sskrll if (child->addr >= arc->child->addr
752a6b7db3Sskrll && child->end_addr <= arc->child->end_addr)
762a6b7db3Sskrll {
772a6b7db3Sskrll return arc;
782a6b7db3Sskrll }
792a6b7db3Sskrll }
802a6b7db3Sskrll return 0;
812a6b7db3Sskrll }
822a6b7db3Sskrll
832a6b7db3Sskrll
842a6b7db3Sskrll /*
852a6b7db3Sskrll * Add (or just increment) an arc:
862a6b7db3Sskrll */
872a6b7db3Sskrll void
arc_add(Sym * parent,Sym * child,unsigned long count)882a6b7db3Sskrll arc_add (Sym *parent, Sym *child, unsigned long count)
892a6b7db3Sskrll {
902a6b7db3Sskrll static unsigned int maxarcs = 0;
912a6b7db3Sskrll Arc *arc, **newarcs;
922a6b7db3Sskrll
932a6b7db3Sskrll DBG (TALLYDEBUG, printf ("[arc_add] %lu arcs from %s to %s\n",
942a6b7db3Sskrll count, parent->name, child->name));
952a6b7db3Sskrll arc = arc_lookup (parent, child);
962a6b7db3Sskrll if (arc)
972a6b7db3Sskrll {
982a6b7db3Sskrll /*
992a6b7db3Sskrll * A hit: just increment the count.
1002a6b7db3Sskrll */
1012a6b7db3Sskrll DBG (TALLYDEBUG, printf ("[tally] hit %lu += %lu\n",
1022a6b7db3Sskrll arc->count, count));
1032a6b7db3Sskrll arc->count += count;
1042a6b7db3Sskrll return;
1052a6b7db3Sskrll }
1062a6b7db3Sskrll arc = (Arc *) xmalloc (sizeof (*arc));
1072a6b7db3Sskrll memset (arc, 0, sizeof (*arc));
1082a6b7db3Sskrll arc->parent = parent;
1092a6b7db3Sskrll arc->child = child;
1102a6b7db3Sskrll arc->count = count;
1112a6b7db3Sskrll
1122a6b7db3Sskrll /* If this isn't an arc for a recursive call to parent, then add it
1132a6b7db3Sskrll to the array of arcs. */
1142a6b7db3Sskrll if (parent != child)
1152a6b7db3Sskrll {
1162a6b7db3Sskrll /* If we've exhausted space in our current array, get a new one
1172a6b7db3Sskrll and copy the contents. We might want to throttle the doubling
1182a6b7db3Sskrll factor one day. */
1192a6b7db3Sskrll if (numarcs == maxarcs)
1202a6b7db3Sskrll {
1212a6b7db3Sskrll /* Determine how much space we want to allocate. */
1222a6b7db3Sskrll if (maxarcs == 0)
1232a6b7db3Sskrll maxarcs = 1;
1242a6b7db3Sskrll maxarcs *= 2;
1252a6b7db3Sskrll
1262a6b7db3Sskrll /* Allocate the new array. */
1272a6b7db3Sskrll newarcs = (Arc **)xmalloc(sizeof (Arc *) * maxarcs);
1282a6b7db3Sskrll
1292a6b7db3Sskrll /* Copy the old array's contents into the new array. */
1302a6b7db3Sskrll memcpy (newarcs, arcs, numarcs * sizeof (Arc *));
1312a6b7db3Sskrll
1322a6b7db3Sskrll /* Free up the old array. */
1332a6b7db3Sskrll free (arcs);
1342a6b7db3Sskrll
1352a6b7db3Sskrll /* And make the new array be the current array. */
1362a6b7db3Sskrll arcs = newarcs;
1372a6b7db3Sskrll }
1382a6b7db3Sskrll
1392a6b7db3Sskrll /* Place this arc in the arc array. */
1402a6b7db3Sskrll arcs[numarcs++] = arc;
1412a6b7db3Sskrll }
1422a6b7db3Sskrll
1432a6b7db3Sskrll /* prepend this child to the children of this parent: */
1442a6b7db3Sskrll arc->next_child = parent->cg.children;
1452a6b7db3Sskrll parent->cg.children = arc;
1462a6b7db3Sskrll
1472a6b7db3Sskrll /* prepend this parent to the parents of this child: */
1482a6b7db3Sskrll arc->next_parent = child->cg.parents;
1492a6b7db3Sskrll child->cg.parents = arc;
1502a6b7db3Sskrll }
1512a6b7db3Sskrll
1522a6b7db3Sskrll
1532a6b7db3Sskrll static int
cmp_topo(const void * lp,const void * rp)154*f22f0ef4Schristos cmp_topo (const void *lp, const void *rp)
1552a6b7db3Sskrll {
1562a6b7db3Sskrll const Sym *left = *(const Sym **) lp;
1572a6b7db3Sskrll const Sym *right = *(const Sym **) rp;
1582a6b7db3Sskrll
1592a6b7db3Sskrll return left->cg.top_order - right->cg.top_order;
1602a6b7db3Sskrll }
1612a6b7db3Sskrll
1622a6b7db3Sskrll
1632a6b7db3Sskrll static void
propagate_time(Sym * parent)1642a6b7db3Sskrll propagate_time (Sym *parent)
1652a6b7db3Sskrll {
1662a6b7db3Sskrll Arc *arc;
1672a6b7db3Sskrll Sym *child;
1682a6b7db3Sskrll double share, prop_share;
1692a6b7db3Sskrll
1702a6b7db3Sskrll if (parent->cg.prop.fract == 0.0)
1712a6b7db3Sskrll {
1722a6b7db3Sskrll return;
1732a6b7db3Sskrll }
1742a6b7db3Sskrll
1752a6b7db3Sskrll /* gather time from children of this parent: */
1762a6b7db3Sskrll
1772a6b7db3Sskrll for (arc = parent->cg.children; arc; arc = arc->next_child)
1782a6b7db3Sskrll {
1792a6b7db3Sskrll child = arc->child;
1802a6b7db3Sskrll if (arc->count == 0 || child == parent || child->cg.prop.fract == 0)
1812a6b7db3Sskrll {
1822a6b7db3Sskrll continue;
1832a6b7db3Sskrll }
1842a6b7db3Sskrll if (child->cg.cyc.head != child)
1852a6b7db3Sskrll {
1862a6b7db3Sskrll if (parent->cg.cyc.num == child->cg.cyc.num)
1872a6b7db3Sskrll {
1882a6b7db3Sskrll continue;
1892a6b7db3Sskrll }
1902a6b7db3Sskrll if (parent->cg.top_order <= child->cg.top_order)
1912a6b7db3Sskrll {
1922a6b7db3Sskrll fprintf (stderr, "[propagate] toporder botches\n");
1932a6b7db3Sskrll }
1942a6b7db3Sskrll child = child->cg.cyc.head;
1952a6b7db3Sskrll }
1962a6b7db3Sskrll else
1972a6b7db3Sskrll {
1982a6b7db3Sskrll if (parent->cg.top_order <= child->cg.top_order)
1992a6b7db3Sskrll {
2002a6b7db3Sskrll fprintf (stderr, "[propagate] toporder botches\n");
2012a6b7db3Sskrll continue;
2022a6b7db3Sskrll }
2032a6b7db3Sskrll }
2042a6b7db3Sskrll if (child->ncalls == 0)
2052a6b7db3Sskrll {
2062a6b7db3Sskrll continue;
2072a6b7db3Sskrll }
2082a6b7db3Sskrll
2092a6b7db3Sskrll /* distribute time for this arc: */
2102a6b7db3Sskrll arc->time = child->hist.time * (((double) arc->count)
2112a6b7db3Sskrll / ((double) child->ncalls));
2122a6b7db3Sskrll arc->child_time = child->cg.child_time
2132a6b7db3Sskrll * (((double) arc->count) / ((double) child->ncalls));
2142a6b7db3Sskrll share = arc->time + arc->child_time;
2152a6b7db3Sskrll parent->cg.child_time += share;
2162a6b7db3Sskrll
2172a6b7db3Sskrll /* (1 - cg.prop.fract) gets lost along the way: */
2182a6b7db3Sskrll prop_share = parent->cg.prop.fract * share;
2192a6b7db3Sskrll
2202a6b7db3Sskrll /* fix things for printing: */
2212a6b7db3Sskrll parent->cg.prop.child += prop_share;
2222a6b7db3Sskrll arc->time *= parent->cg.prop.fract;
2232a6b7db3Sskrll arc->child_time *= parent->cg.prop.fract;
2242a6b7db3Sskrll
2252a6b7db3Sskrll /* add this share to the parent's cycle header, if any: */
2262a6b7db3Sskrll if (parent->cg.cyc.head != parent)
2272a6b7db3Sskrll {
2282a6b7db3Sskrll parent->cg.cyc.head->cg.child_time += share;
2292a6b7db3Sskrll parent->cg.cyc.head->cg.prop.child += prop_share;
2302a6b7db3Sskrll }
2312a6b7db3Sskrll DBG (PROPDEBUG,
2322a6b7db3Sskrll printf ("[prop_time] child \t");
2332a6b7db3Sskrll print_name (child);
2342a6b7db3Sskrll printf (" with %f %f %lu/%lu\n", child->hist.time,
2352a6b7db3Sskrll child->cg.child_time, arc->count, child->ncalls);
2362a6b7db3Sskrll printf ("[prop_time] parent\t");
2372a6b7db3Sskrll print_name (parent);
2382a6b7db3Sskrll printf ("\n[prop_time] share %f\n", share));
2392a6b7db3Sskrll }
2402a6b7db3Sskrll }
2412a6b7db3Sskrll
2422a6b7db3Sskrll
2432a6b7db3Sskrll /*
2442a6b7db3Sskrll * Compute the time of a cycle as the sum of the times of all
2452a6b7db3Sskrll * its members.
2462a6b7db3Sskrll */
2472a6b7db3Sskrll static void
cycle_time(void)24875f9f1baSchristos cycle_time (void)
2492a6b7db3Sskrll {
2502a6b7db3Sskrll Sym *member, *cyc;
2512a6b7db3Sskrll
2522a6b7db3Sskrll for (cyc = &cycle_header[1]; cyc <= &cycle_header[num_cycles]; ++cyc)
2532a6b7db3Sskrll {
2542a6b7db3Sskrll for (member = cyc->cg.cyc.next; member; member = member->cg.cyc.next)
2552a6b7db3Sskrll {
2562a6b7db3Sskrll if (member->cg.prop.fract == 0.0)
2572a6b7db3Sskrll {
2582a6b7db3Sskrll /*
2592a6b7db3Sskrll * All members have the same propfraction except those
2602a6b7db3Sskrll * that were excluded with -E.
2612a6b7db3Sskrll */
2622a6b7db3Sskrll continue;
2632a6b7db3Sskrll }
2642a6b7db3Sskrll cyc->hist.time += member->hist.time;
2652a6b7db3Sskrll }
2662a6b7db3Sskrll cyc->cg.prop.self = cyc->cg.prop.fract * cyc->hist.time;
2672a6b7db3Sskrll }
2682a6b7db3Sskrll }
2692a6b7db3Sskrll
2702a6b7db3Sskrll
2712a6b7db3Sskrll static void
cycle_link(void)27275f9f1baSchristos cycle_link (void)
2732a6b7db3Sskrll {
2742a6b7db3Sskrll Sym *sym, *cyc, *member;
2752a6b7db3Sskrll Arc *arc;
2762a6b7db3Sskrll int num;
2772a6b7db3Sskrll
2782a6b7db3Sskrll /* count the number of cycles, and initialize the cycle lists: */
2792a6b7db3Sskrll
2802a6b7db3Sskrll num_cycles = 0;
2812a6b7db3Sskrll for (sym = symtab.base; sym < symtab.limit; ++sym)
2822a6b7db3Sskrll {
2832a6b7db3Sskrll /* this is how you find unattached cycles: */
2842a6b7db3Sskrll if (sym->cg.cyc.head == sym && sym->cg.cyc.next)
2852a6b7db3Sskrll {
2862a6b7db3Sskrll ++num_cycles;
2872a6b7db3Sskrll }
2882a6b7db3Sskrll }
2892a6b7db3Sskrll
2902a6b7db3Sskrll /*
2912a6b7db3Sskrll * cycle_header is indexed by cycle number: i.e. it is origin 1,
2922a6b7db3Sskrll * not origin 0.
2932a6b7db3Sskrll */
2942a6b7db3Sskrll cycle_header = (Sym *) xmalloc ((num_cycles + 1) * sizeof (Sym));
2952a6b7db3Sskrll
2962a6b7db3Sskrll /*
2972a6b7db3Sskrll * Now link cycles to true cycle-heads, number them, accumulate
2982a6b7db3Sskrll * the data for the cycle.
2992a6b7db3Sskrll */
3002a6b7db3Sskrll num = 0;
3012a6b7db3Sskrll cyc = cycle_header;
3022a6b7db3Sskrll for (sym = symtab.base; sym < symtab.limit; ++sym)
3032a6b7db3Sskrll {
3042a6b7db3Sskrll if (!(sym->cg.cyc.head == sym && sym->cg.cyc.next != 0))
3052a6b7db3Sskrll {
3062a6b7db3Sskrll continue;
3072a6b7db3Sskrll }
3082a6b7db3Sskrll ++num;
3092a6b7db3Sskrll ++cyc;
3102a6b7db3Sskrll sym_init (cyc);
311*f22f0ef4Schristos cyc->cg.print_flag = true; /* should this be printed? */
3122a6b7db3Sskrll cyc->cg.top_order = DFN_NAN; /* graph call chain top-sort order */
3132a6b7db3Sskrll cyc->cg.cyc.num = num; /* internal number of cycle on */
3142a6b7db3Sskrll cyc->cg.cyc.head = cyc; /* pointer to head of cycle */
3152a6b7db3Sskrll cyc->cg.cyc.next = sym; /* pointer to next member of cycle */
3162a6b7db3Sskrll DBG (CYCLEDEBUG, printf ("[cycle_link] ");
3172a6b7db3Sskrll print_name (sym);
3182a6b7db3Sskrll printf (" is the head of cycle %d\n", num));
3192a6b7db3Sskrll
3202a6b7db3Sskrll /* link members to cycle header: */
3212a6b7db3Sskrll for (member = sym; member; member = member->cg.cyc.next)
3222a6b7db3Sskrll {
3232a6b7db3Sskrll member->cg.cyc.num = num;
3242a6b7db3Sskrll member->cg.cyc.head = cyc;
3252a6b7db3Sskrll }
3262a6b7db3Sskrll
3272a6b7db3Sskrll /*
3282a6b7db3Sskrll * Count calls from outside the cycle and those among cycle
3292a6b7db3Sskrll * members:
3302a6b7db3Sskrll */
3312a6b7db3Sskrll for (member = sym; member; member = member->cg.cyc.next)
3322a6b7db3Sskrll {
3332a6b7db3Sskrll for (arc = member->cg.parents; arc; arc = arc->next_parent)
3342a6b7db3Sskrll {
3352a6b7db3Sskrll if (arc->parent == member)
3362a6b7db3Sskrll {
3372a6b7db3Sskrll continue;
3382a6b7db3Sskrll }
3392a6b7db3Sskrll if (arc->parent->cg.cyc.num == num)
3402a6b7db3Sskrll {
3412a6b7db3Sskrll cyc->cg.self_calls += arc->count;
3422a6b7db3Sskrll }
3432a6b7db3Sskrll else
3442a6b7db3Sskrll {
3452a6b7db3Sskrll cyc->ncalls += arc->count;
3462a6b7db3Sskrll }
3472a6b7db3Sskrll }
3482a6b7db3Sskrll }
3492a6b7db3Sskrll }
3502a6b7db3Sskrll }
3512a6b7db3Sskrll
3522a6b7db3Sskrll
3532a6b7db3Sskrll /*
3542a6b7db3Sskrll * Check if any parent of this child (or outside parents of this
3552a6b7db3Sskrll * cycle) have their print flags on and set the print flag of the
3562a6b7db3Sskrll * child (cycle) appropriately. Similarly, deal with propagation
3572a6b7db3Sskrll * fractions from parents.
3582a6b7db3Sskrll */
3592a6b7db3Sskrll static void
inherit_flags(Sym * child)3602a6b7db3Sskrll inherit_flags (Sym *child)
3612a6b7db3Sskrll {
3622a6b7db3Sskrll Sym *head, *parent, *member;
3632a6b7db3Sskrll Arc *arc;
3642a6b7db3Sskrll
3652a6b7db3Sskrll head = child->cg.cyc.head;
3662a6b7db3Sskrll if (child == head)
3672a6b7db3Sskrll {
3682a6b7db3Sskrll /* just a regular child, check its parents: */
369*f22f0ef4Schristos child->cg.print_flag = false;
3702a6b7db3Sskrll child->cg.prop.fract = 0.0;
3712a6b7db3Sskrll for (arc = child->cg.parents; arc; arc = arc->next_parent)
3722a6b7db3Sskrll {
3732a6b7db3Sskrll parent = arc->parent;
3742a6b7db3Sskrll if (child == parent)
3752a6b7db3Sskrll {
3762a6b7db3Sskrll continue;
3772a6b7db3Sskrll }
3782a6b7db3Sskrll child->cg.print_flag |= parent->cg.print_flag;
3792a6b7db3Sskrll /*
3802a6b7db3Sskrll * If the child was never actually called (e.g., this arc
3812a6b7db3Sskrll * is static (and all others are, too)) no time propagates
3822a6b7db3Sskrll * along this arc.
3832a6b7db3Sskrll */
3842a6b7db3Sskrll if (child->ncalls != 0)
3852a6b7db3Sskrll {
3862a6b7db3Sskrll child->cg.prop.fract += parent->cg.prop.fract
3872a6b7db3Sskrll * (((double) arc->count) / ((double) child->ncalls));
3882a6b7db3Sskrll }
3892a6b7db3Sskrll }
3902a6b7db3Sskrll }
3912a6b7db3Sskrll else
3922a6b7db3Sskrll {
3932a6b7db3Sskrll /*
3942a6b7db3Sskrll * Its a member of a cycle, look at all parents from outside
3952a6b7db3Sskrll * the cycle.
3962a6b7db3Sskrll */
397*f22f0ef4Schristos head->cg.print_flag = false;
3982a6b7db3Sskrll head->cg.prop.fract = 0.0;
3992a6b7db3Sskrll for (member = head->cg.cyc.next; member; member = member->cg.cyc.next)
4002a6b7db3Sskrll {
4012a6b7db3Sskrll for (arc = member->cg.parents; arc; arc = arc->next_parent)
4022a6b7db3Sskrll {
4032a6b7db3Sskrll if (arc->parent->cg.cyc.head == head)
4042a6b7db3Sskrll {
4052a6b7db3Sskrll continue;
4062a6b7db3Sskrll }
4072a6b7db3Sskrll parent = arc->parent;
4082a6b7db3Sskrll head->cg.print_flag |= parent->cg.print_flag;
4092a6b7db3Sskrll /*
4102a6b7db3Sskrll * If the cycle was never actually called (e.g. this
4112a6b7db3Sskrll * arc is static (and all others are, too)) no time
4122a6b7db3Sskrll * propagates along this arc.
4132a6b7db3Sskrll */
4142a6b7db3Sskrll if (head->ncalls != 0)
4152a6b7db3Sskrll {
4162a6b7db3Sskrll head->cg.prop.fract += parent->cg.prop.fract
4172a6b7db3Sskrll * (((double) arc->count) / ((double) head->ncalls));
4182a6b7db3Sskrll }
4192a6b7db3Sskrll }
4202a6b7db3Sskrll }
4212a6b7db3Sskrll for (member = head; member; member = member->cg.cyc.next)
4222a6b7db3Sskrll {
4232a6b7db3Sskrll member->cg.print_flag = head->cg.print_flag;
4242a6b7db3Sskrll member->cg.prop.fract = head->cg.prop.fract;
4252a6b7db3Sskrll }
4262a6b7db3Sskrll }
4272a6b7db3Sskrll }
4282a6b7db3Sskrll
4292a6b7db3Sskrll
4302a6b7db3Sskrll /*
4312a6b7db3Sskrll * In one top-to-bottom pass over the topologically sorted symbols
4322a6b7db3Sskrll * propagate:
4332a6b7db3Sskrll * cg.print_flag as the union of parents' print_flags
4342a6b7db3Sskrll * propfraction as the sum of fractional parents' propfractions
4352a6b7db3Sskrll * and while we're here, sum time for functions.
4362a6b7db3Sskrll */
4372a6b7db3Sskrll static void
propagate_flags(Sym ** symbols)4382a6b7db3Sskrll propagate_flags (Sym **symbols)
4392a6b7db3Sskrll {
440b578a859Schristos int sym_index;
4412a6b7db3Sskrll Sym *old_head, *child;
4422a6b7db3Sskrll
4432a6b7db3Sskrll old_head = 0;
444b578a859Schristos for (sym_index = symtab.len - 1; sym_index >= 0; --sym_index)
4452a6b7db3Sskrll {
446b578a859Schristos child = symbols[sym_index];
4472a6b7db3Sskrll /*
4482a6b7db3Sskrll * If we haven't done this function or cycle, inherit things
4492a6b7db3Sskrll * from parent. This way, we are linear in the number of arcs
4502a6b7db3Sskrll * since we do all members of a cycle (and the cycle itself)
4512a6b7db3Sskrll * as we hit the first member of the cycle.
4522a6b7db3Sskrll */
4532a6b7db3Sskrll if (child->cg.cyc.head != old_head)
4542a6b7db3Sskrll {
4552a6b7db3Sskrll old_head = child->cg.cyc.head;
4562a6b7db3Sskrll inherit_flags (child);
4572a6b7db3Sskrll }
4582a6b7db3Sskrll DBG (PROPDEBUG,
4592a6b7db3Sskrll printf ("[prop_flags] ");
4602a6b7db3Sskrll print_name (child);
4612a6b7db3Sskrll printf ("inherits print-flag %d and prop-fract %f\n",
4622a6b7db3Sskrll child->cg.print_flag, child->cg.prop.fract));
4632a6b7db3Sskrll if (!child->cg.print_flag)
4642a6b7db3Sskrll {
4652a6b7db3Sskrll /*
4662a6b7db3Sskrll * Printflag is off. It gets turned on by being in the
4672a6b7db3Sskrll * INCL_GRAPH table, or there being an empty INCL_GRAPH
4682a6b7db3Sskrll * table and not being in the EXCL_GRAPH table.
4692a6b7db3Sskrll */
4702a6b7db3Sskrll if (sym_lookup (&syms[INCL_GRAPH], child->addr)
4712a6b7db3Sskrll || (syms[INCL_GRAPH].len == 0
4722a6b7db3Sskrll && !sym_lookup (&syms[EXCL_GRAPH], child->addr)))
4732a6b7db3Sskrll {
474*f22f0ef4Schristos child->cg.print_flag = true;
4752a6b7db3Sskrll }
4762a6b7db3Sskrll }
4772a6b7db3Sskrll else
4782a6b7db3Sskrll {
4792a6b7db3Sskrll /*
4802a6b7db3Sskrll * This function has printing parents: maybe someone wants
4812a6b7db3Sskrll * to shut it up by putting it in the EXCL_GRAPH table.
4822a6b7db3Sskrll * (But favor INCL_GRAPH over EXCL_GRAPH.)
4832a6b7db3Sskrll */
4842a6b7db3Sskrll if (!sym_lookup (&syms[INCL_GRAPH], child->addr)
4852a6b7db3Sskrll && sym_lookup (&syms[EXCL_GRAPH], child->addr))
4862a6b7db3Sskrll {
487*f22f0ef4Schristos child->cg.print_flag = false;
4882a6b7db3Sskrll }
4892a6b7db3Sskrll }
4902a6b7db3Sskrll if (child->cg.prop.fract == 0.0)
4912a6b7db3Sskrll {
4922a6b7db3Sskrll /*
4932a6b7db3Sskrll * No parents to pass time to. Collect time from children
4942a6b7db3Sskrll * if its in the INCL_TIME table, or there is an empty
4952a6b7db3Sskrll * INCL_TIME table and its not in the EXCL_TIME table.
4962a6b7db3Sskrll */
4972a6b7db3Sskrll if (sym_lookup (&syms[INCL_TIME], child->addr)
4982a6b7db3Sskrll || (syms[INCL_TIME].len == 0
4992a6b7db3Sskrll && !sym_lookup (&syms[EXCL_TIME], child->addr)))
5002a6b7db3Sskrll {
5012a6b7db3Sskrll child->cg.prop.fract = 1.0;
5022a6b7db3Sskrll }
5032a6b7db3Sskrll }
5042a6b7db3Sskrll else
5052a6b7db3Sskrll {
5062a6b7db3Sskrll /*
5072a6b7db3Sskrll * It has parents to pass time to, but maybe someone wants
5082a6b7db3Sskrll * to shut it up by puttting it in the EXCL_TIME table.
5092a6b7db3Sskrll * (But favor being in INCL_TIME tabe over being in
5102a6b7db3Sskrll * EXCL_TIME table.)
5112a6b7db3Sskrll */
5122a6b7db3Sskrll if (!sym_lookup (&syms[INCL_TIME], child->addr)
5132a6b7db3Sskrll && sym_lookup (&syms[EXCL_TIME], child->addr))
5142a6b7db3Sskrll {
5152a6b7db3Sskrll child->cg.prop.fract = 0.0;
5162a6b7db3Sskrll }
5172a6b7db3Sskrll }
5182a6b7db3Sskrll child->cg.prop.self = child->hist.time * child->cg.prop.fract;
5192a6b7db3Sskrll print_time += child->cg.prop.self;
5202a6b7db3Sskrll DBG (PROPDEBUG,
5212a6b7db3Sskrll printf ("[prop_flags] ");
5222a6b7db3Sskrll print_name (child);
5232a6b7db3Sskrll printf (" ends up with printflag %d and prop-fract %f\n",
5242a6b7db3Sskrll child->cg.print_flag, child->cg.prop.fract);
5252a6b7db3Sskrll printf ("[prop_flags] time %f propself %f print_time %f\n",
5262a6b7db3Sskrll child->hist.time, child->cg.prop.self, print_time));
5272a6b7db3Sskrll }
5282a6b7db3Sskrll }
5292a6b7db3Sskrll
5302a6b7db3Sskrll
5312a6b7db3Sskrll /*
5322a6b7db3Sskrll * Compare by decreasing propagated time. If times are equal, but one
5332a6b7db3Sskrll * is a cycle header, say that's first (e.g. less, i.e. -1). If one's
5342a6b7db3Sskrll * name doesn't have an underscore and the other does, say that one is
5352a6b7db3Sskrll * first. All else being equal, compare by names.
5362a6b7db3Sskrll */
5372a6b7db3Sskrll static int
cmp_total(const void * lp,const void * rp)538*f22f0ef4Schristos cmp_total (const void *lp, const void *rp)
5392a6b7db3Sskrll {
5402a6b7db3Sskrll const Sym *left = *(const Sym **) lp;
5412a6b7db3Sskrll const Sym *right = *(const Sym **) rp;
5422a6b7db3Sskrll double diff;
5432a6b7db3Sskrll
5442a6b7db3Sskrll diff = (left->cg.prop.self + left->cg.prop.child)
5452a6b7db3Sskrll - (right->cg.prop.self + right->cg.prop.child);
5462a6b7db3Sskrll if (diff < 0.0)
5472a6b7db3Sskrll {
5482a6b7db3Sskrll return 1;
5492a6b7db3Sskrll }
5502a6b7db3Sskrll if (diff > 0.0)
5512a6b7db3Sskrll {
5522a6b7db3Sskrll return -1;
5532a6b7db3Sskrll }
5542a6b7db3Sskrll if (!left->name && left->cg.cyc.num != 0)
5552a6b7db3Sskrll {
5562a6b7db3Sskrll return -1;
5572a6b7db3Sskrll }
5582a6b7db3Sskrll if (!right->name && right->cg.cyc.num != 0)
5592a6b7db3Sskrll {
5602a6b7db3Sskrll return 1;
5612a6b7db3Sskrll }
5622a6b7db3Sskrll if (!left->name)
5632a6b7db3Sskrll {
5642a6b7db3Sskrll return -1;
5652a6b7db3Sskrll }
5662a6b7db3Sskrll if (!right->name)
5672a6b7db3Sskrll {
5682a6b7db3Sskrll return 1;
5692a6b7db3Sskrll }
5702a6b7db3Sskrll if (left->name[0] != '_' && right->name[0] == '_')
5712a6b7db3Sskrll {
5722a6b7db3Sskrll return -1;
5732a6b7db3Sskrll }
5742a6b7db3Sskrll if (left->name[0] == '_' && right->name[0] != '_')
5752a6b7db3Sskrll {
5762a6b7db3Sskrll return 1;
5772a6b7db3Sskrll }
5782a6b7db3Sskrll if (left->ncalls > right->ncalls)
5792a6b7db3Sskrll {
5802a6b7db3Sskrll return -1;
5812a6b7db3Sskrll }
5822a6b7db3Sskrll if (left->ncalls < right->ncalls)
5832a6b7db3Sskrll {
5842a6b7db3Sskrll return 1;
5852a6b7db3Sskrll }
5862a6b7db3Sskrll return strcmp (left->name, right->name);
5872a6b7db3Sskrll }
5882a6b7db3Sskrll
5892a6b7db3Sskrll
590b578a859Schristos /* Topologically sort the graph (collapsing cycles), and propagates
591b578a859Schristos time bottom up and flags top down. */
592b578a859Schristos
5932a6b7db3Sskrll Sym **
cg_assemble(void)594b578a859Schristos cg_assemble (void)
5952a6b7db3Sskrll {
5962a6b7db3Sskrll Sym *parent, **time_sorted_syms, **top_sorted_syms;
597b578a859Schristos unsigned int sym_index;
5982a6b7db3Sskrll Arc *arc;
5992a6b7db3Sskrll
600b578a859Schristos /* Initialize various things:
601b578a859Schristos Zero out child times.
602b578a859Schristos Count self-recursive calls.
603b578a859Schristos Indicate that nothing is on cycles. */
6042a6b7db3Sskrll for (parent = symtab.base; parent < symtab.limit; parent++)
6052a6b7db3Sskrll {
6062a6b7db3Sskrll parent->cg.child_time = 0.0;
6072a6b7db3Sskrll arc = arc_lookup (parent, parent);
6082a6b7db3Sskrll if (arc && parent == arc->child)
6092a6b7db3Sskrll {
6102a6b7db3Sskrll parent->ncalls -= arc->count;
6112a6b7db3Sskrll parent->cg.self_calls = arc->count;
6122a6b7db3Sskrll }
6132a6b7db3Sskrll else
6142a6b7db3Sskrll {
6152a6b7db3Sskrll parent->cg.self_calls = 0;
6162a6b7db3Sskrll }
6172a6b7db3Sskrll parent->cg.prop.fract = 0.0;
6182a6b7db3Sskrll parent->cg.prop.self = 0.0;
6192a6b7db3Sskrll parent->cg.prop.child = 0.0;
620*f22f0ef4Schristos parent->cg.print_flag = false;
6212a6b7db3Sskrll parent->cg.top_order = DFN_NAN;
6222a6b7db3Sskrll parent->cg.cyc.num = 0;
6232a6b7db3Sskrll parent->cg.cyc.head = parent;
6242a6b7db3Sskrll parent->cg.cyc.next = 0;
6252a6b7db3Sskrll if (ignore_direct_calls)
6262a6b7db3Sskrll find_call (parent, parent->addr, (parent + 1)->addr);
6272a6b7db3Sskrll }
628b578a859Schristos
629b578a859Schristos /* Topologically order things. If any node is unnumbered, number
630b578a859Schristos it and any of its descendents. */
6312a6b7db3Sskrll for (parent = symtab.base; parent < symtab.limit; parent++)
6322a6b7db3Sskrll {
6332a6b7db3Sskrll if (parent->cg.top_order == DFN_NAN)
6342a6b7db3Sskrll cg_dfn (parent);
6352a6b7db3Sskrll }
6362a6b7db3Sskrll
637b578a859Schristos /* Link together nodes on the same cycle. */
6382a6b7db3Sskrll cycle_link ();
6392a6b7db3Sskrll
640b578a859Schristos /* Sort the symbol table in reverse topological order. */
6412a6b7db3Sskrll top_sorted_syms = (Sym **) xmalloc (symtab.len * sizeof (Sym *));
642b578a859Schristos for (sym_index = 0; sym_index < symtab.len; ++sym_index)
643b578a859Schristos top_sorted_syms[sym_index] = &symtab.base[sym_index];
644b578a859Schristos
6452a6b7db3Sskrll qsort (top_sorted_syms, symtab.len, sizeof (Sym *), cmp_topo);
6462a6b7db3Sskrll DBG (DFNDEBUG,
6472a6b7db3Sskrll printf ("[cg_assemble] topological sort listing\n");
648b578a859Schristos for (sym_index = 0; sym_index < symtab.len; ++sym_index)
6492a6b7db3Sskrll {
6502a6b7db3Sskrll printf ("[cg_assemble] ");
651b578a859Schristos printf ("%d:", top_sorted_syms[sym_index]->cg.top_order);
652b578a859Schristos print_name (top_sorted_syms[sym_index]);
6532a6b7db3Sskrll printf ("\n");
6542a6b7db3Sskrll }
6552a6b7db3Sskrll );
656b578a859Schristos
657b578a859Schristos /* Starting from the topological top, propagate print flags to
658b578a859Schristos children. also, calculate propagation fractions. this happens
659b578a859Schristos before time propagation since time propagation uses the
660b578a859Schristos fractions. */
6612a6b7db3Sskrll propagate_flags (top_sorted_syms);
6622a6b7db3Sskrll
66398f124a6Schristos /* Starting from the topological bottom, propagate children times
664b578a859Schristos up to parents. */
6652a6b7db3Sskrll cycle_time ();
666b578a859Schristos for (sym_index = 0; sym_index < symtab.len; ++sym_index)
667b578a859Schristos propagate_time (top_sorted_syms[sym_index]);
6682a6b7db3Sskrll
6692a6b7db3Sskrll free (top_sorted_syms);
6702a6b7db3Sskrll
671b578a859Schristos /* Now, sort by CG.PROP.SELF + CG.PROP.CHILD. Sorting both the regular
672b578a859Schristos function names and cycle headers. */
6732a6b7db3Sskrll time_sorted_syms = (Sym **) xmalloc ((symtab.len + num_cycles) * sizeof (Sym *));
674b578a859Schristos for (sym_index = 0; sym_index < symtab.len; sym_index++)
675b578a859Schristos time_sorted_syms[sym_index] = &symtab.base[sym_index];
676b578a859Schristos
677b578a859Schristos for (sym_index = 1; sym_index <= num_cycles; sym_index++)
678b578a859Schristos time_sorted_syms[symtab.len + sym_index - 1] = &cycle_header[sym_index];
679b578a859Schristos
6802a6b7db3Sskrll qsort (time_sorted_syms, symtab.len + num_cycles, sizeof (Sym *),
6812a6b7db3Sskrll cmp_total);
682b578a859Schristos
683b578a859Schristos for (sym_index = 0; sym_index < symtab.len + num_cycles; sym_index++)
684b578a859Schristos time_sorted_syms[sym_index]->cg.index = sym_index + 1;
685b578a859Schristos
6862a6b7db3Sskrll return time_sorted_syms;
6872a6b7db3Sskrll }
688