1*2a6b7db3Sskrll /* 2*2a6b7db3Sskrll * Copyright (c) 1983, 1993, 2001 3*2a6b7db3Sskrll * The Regents of the University of California. All rights reserved. 4*2a6b7db3Sskrll * 5*2a6b7db3Sskrll * Redistribution and use in source and binary forms, with or without 6*2a6b7db3Sskrll * modification, are permitted provided that the following conditions 7*2a6b7db3Sskrll * are met: 8*2a6b7db3Sskrll * 1. Redistributions of source code must retain the above copyright 9*2a6b7db3Sskrll * notice, this list of conditions and the following disclaimer. 10*2a6b7db3Sskrll * 2. Redistributions in binary form must reproduce the above copyright 11*2a6b7db3Sskrll * notice, this list of conditions and the following disclaimer in the 12*2a6b7db3Sskrll * documentation and/or other materials provided with the distribution. 13*2a6b7db3Sskrll * 3. Neither the name of the University nor the names of its contributors 14*2a6b7db3Sskrll * may be used to endorse or promote products derived from this software 15*2a6b7db3Sskrll * without specific prior written permission. 16*2a6b7db3Sskrll * 17*2a6b7db3Sskrll * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 18*2a6b7db3Sskrll * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 19*2a6b7db3Sskrll * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 20*2a6b7db3Sskrll * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 21*2a6b7db3Sskrll * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 22*2a6b7db3Sskrll * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 23*2a6b7db3Sskrll * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 24*2a6b7db3Sskrll * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 25*2a6b7db3Sskrll * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 26*2a6b7db3Sskrll * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 27*2a6b7db3Sskrll * SUCH DAMAGE. 28*2a6b7db3Sskrll */ 29*2a6b7db3Sskrll #include "gprof.h" 30*2a6b7db3Sskrll #include "libiberty.h" 31*2a6b7db3Sskrll #include "search_list.h" 32*2a6b7db3Sskrll #include "source.h" 33*2a6b7db3Sskrll #include "symtab.h" 34*2a6b7db3Sskrll #include "call_graph.h" 35*2a6b7db3Sskrll #include "cg_arcs.h" 36*2a6b7db3Sskrll #include "cg_dfn.h" 37*2a6b7db3Sskrll #include "cg_print.h" 38*2a6b7db3Sskrll #include "utils.h" 39*2a6b7db3Sskrll #include "sym_ids.h" 40*2a6b7db3Sskrll 41*2a6b7db3Sskrll static int cmp_topo (const PTR, const PTR); 42*2a6b7db3Sskrll static void propagate_time (Sym *); 43*2a6b7db3Sskrll static void cycle_time (void); 44*2a6b7db3Sskrll static void cycle_link (void); 45*2a6b7db3Sskrll static void inherit_flags (Sym *); 46*2a6b7db3Sskrll static void propagate_flags (Sym **); 47*2a6b7db3Sskrll static int cmp_total (const PTR, const PTR); 48*2a6b7db3Sskrll 49*2a6b7db3Sskrll Sym *cycle_header; 50*2a6b7db3Sskrll unsigned int num_cycles; 51*2a6b7db3Sskrll Arc **arcs; 52*2a6b7db3Sskrll unsigned int numarcs; 53*2a6b7db3Sskrll 54*2a6b7db3Sskrll /* 55*2a6b7db3Sskrll * Return TRUE iff PARENT has an arc to covers the address 56*2a6b7db3Sskrll * range covered by CHILD. 57*2a6b7db3Sskrll */ 58*2a6b7db3Sskrll Arc * 59*2a6b7db3Sskrll arc_lookup (Sym *parent, Sym *child) 60*2a6b7db3Sskrll { 61*2a6b7db3Sskrll Arc *arc; 62*2a6b7db3Sskrll 63*2a6b7db3Sskrll if (!parent || !child) 64*2a6b7db3Sskrll { 65*2a6b7db3Sskrll printf ("[arc_lookup] parent == 0 || child == 0\n"); 66*2a6b7db3Sskrll return 0; 67*2a6b7db3Sskrll } 68*2a6b7db3Sskrll DBG (LOOKUPDEBUG, printf ("[arc_lookup] parent %s child %s\n", 69*2a6b7db3Sskrll parent->name, child->name)); 70*2a6b7db3Sskrll for (arc = parent->cg.children; arc; arc = arc->next_child) 71*2a6b7db3Sskrll { 72*2a6b7db3Sskrll DBG (LOOKUPDEBUG, printf ("[arc_lookup]\t parent %s child %s\n", 73*2a6b7db3Sskrll arc->parent->name, arc->child->name)); 74*2a6b7db3Sskrll if (child->addr >= arc->child->addr 75*2a6b7db3Sskrll && child->end_addr <= arc->child->end_addr) 76*2a6b7db3Sskrll { 77*2a6b7db3Sskrll return arc; 78*2a6b7db3Sskrll } 79*2a6b7db3Sskrll } 80*2a6b7db3Sskrll return 0; 81*2a6b7db3Sskrll } 82*2a6b7db3Sskrll 83*2a6b7db3Sskrll 84*2a6b7db3Sskrll /* 85*2a6b7db3Sskrll * Add (or just increment) an arc: 86*2a6b7db3Sskrll */ 87*2a6b7db3Sskrll void 88*2a6b7db3Sskrll arc_add (Sym *parent, Sym *child, unsigned long count) 89*2a6b7db3Sskrll { 90*2a6b7db3Sskrll static unsigned int maxarcs = 0; 91*2a6b7db3Sskrll Arc *arc, **newarcs; 92*2a6b7db3Sskrll 93*2a6b7db3Sskrll DBG (TALLYDEBUG, printf ("[arc_add] %lu arcs from %s to %s\n", 94*2a6b7db3Sskrll count, parent->name, child->name)); 95*2a6b7db3Sskrll arc = arc_lookup (parent, child); 96*2a6b7db3Sskrll if (arc) 97*2a6b7db3Sskrll { 98*2a6b7db3Sskrll /* 99*2a6b7db3Sskrll * A hit: just increment the count. 100*2a6b7db3Sskrll */ 101*2a6b7db3Sskrll DBG (TALLYDEBUG, printf ("[tally] hit %lu += %lu\n", 102*2a6b7db3Sskrll arc->count, count)); 103*2a6b7db3Sskrll arc->count += count; 104*2a6b7db3Sskrll return; 105*2a6b7db3Sskrll } 106*2a6b7db3Sskrll arc = (Arc *) xmalloc (sizeof (*arc)); 107*2a6b7db3Sskrll memset (arc, 0, sizeof (*arc)); 108*2a6b7db3Sskrll arc->parent = parent; 109*2a6b7db3Sskrll arc->child = child; 110*2a6b7db3Sskrll arc->count = count; 111*2a6b7db3Sskrll 112*2a6b7db3Sskrll /* If this isn't an arc for a recursive call to parent, then add it 113*2a6b7db3Sskrll to the array of arcs. */ 114*2a6b7db3Sskrll if (parent != child) 115*2a6b7db3Sskrll { 116*2a6b7db3Sskrll /* If we've exhausted space in our current array, get a new one 117*2a6b7db3Sskrll and copy the contents. We might want to throttle the doubling 118*2a6b7db3Sskrll factor one day. */ 119*2a6b7db3Sskrll if (numarcs == maxarcs) 120*2a6b7db3Sskrll { 121*2a6b7db3Sskrll /* Determine how much space we want to allocate. */ 122*2a6b7db3Sskrll if (maxarcs == 0) 123*2a6b7db3Sskrll maxarcs = 1; 124*2a6b7db3Sskrll maxarcs *= 2; 125*2a6b7db3Sskrll 126*2a6b7db3Sskrll /* Allocate the new array. */ 127*2a6b7db3Sskrll newarcs = (Arc **)xmalloc(sizeof (Arc *) * maxarcs); 128*2a6b7db3Sskrll 129*2a6b7db3Sskrll /* Copy the old array's contents into the new array. */ 130*2a6b7db3Sskrll memcpy (newarcs, arcs, numarcs * sizeof (Arc *)); 131*2a6b7db3Sskrll 132*2a6b7db3Sskrll /* Free up the old array. */ 133*2a6b7db3Sskrll free (arcs); 134*2a6b7db3Sskrll 135*2a6b7db3Sskrll /* And make the new array be the current array. */ 136*2a6b7db3Sskrll arcs = newarcs; 137*2a6b7db3Sskrll } 138*2a6b7db3Sskrll 139*2a6b7db3Sskrll /* Place this arc in the arc array. */ 140*2a6b7db3Sskrll arcs[numarcs++] = arc; 141*2a6b7db3Sskrll } 142*2a6b7db3Sskrll 143*2a6b7db3Sskrll /* prepend this child to the children of this parent: */ 144*2a6b7db3Sskrll arc->next_child = parent->cg.children; 145*2a6b7db3Sskrll parent->cg.children = arc; 146*2a6b7db3Sskrll 147*2a6b7db3Sskrll /* prepend this parent to the parents of this child: */ 148*2a6b7db3Sskrll arc->next_parent = child->cg.parents; 149*2a6b7db3Sskrll child->cg.parents = arc; 150*2a6b7db3Sskrll } 151*2a6b7db3Sskrll 152*2a6b7db3Sskrll 153*2a6b7db3Sskrll static int 154*2a6b7db3Sskrll cmp_topo (const PTR lp, const PTR rp) 155*2a6b7db3Sskrll { 156*2a6b7db3Sskrll const Sym *left = *(const Sym **) lp; 157*2a6b7db3Sskrll const Sym *right = *(const Sym **) rp; 158*2a6b7db3Sskrll 159*2a6b7db3Sskrll return left->cg.top_order - right->cg.top_order; 160*2a6b7db3Sskrll } 161*2a6b7db3Sskrll 162*2a6b7db3Sskrll 163*2a6b7db3Sskrll static void 164*2a6b7db3Sskrll propagate_time (Sym *parent) 165*2a6b7db3Sskrll { 166*2a6b7db3Sskrll Arc *arc; 167*2a6b7db3Sskrll Sym *child; 168*2a6b7db3Sskrll double share, prop_share; 169*2a6b7db3Sskrll 170*2a6b7db3Sskrll if (parent->cg.prop.fract == 0.0) 171*2a6b7db3Sskrll { 172*2a6b7db3Sskrll return; 173*2a6b7db3Sskrll } 174*2a6b7db3Sskrll 175*2a6b7db3Sskrll /* gather time from children of this parent: */ 176*2a6b7db3Sskrll 177*2a6b7db3Sskrll for (arc = parent->cg.children; arc; arc = arc->next_child) 178*2a6b7db3Sskrll { 179*2a6b7db3Sskrll child = arc->child; 180*2a6b7db3Sskrll if (arc->count == 0 || child == parent || child->cg.prop.fract == 0) 181*2a6b7db3Sskrll { 182*2a6b7db3Sskrll continue; 183*2a6b7db3Sskrll } 184*2a6b7db3Sskrll if (child->cg.cyc.head != child) 185*2a6b7db3Sskrll { 186*2a6b7db3Sskrll if (parent->cg.cyc.num == child->cg.cyc.num) 187*2a6b7db3Sskrll { 188*2a6b7db3Sskrll continue; 189*2a6b7db3Sskrll } 190*2a6b7db3Sskrll if (parent->cg.top_order <= child->cg.top_order) 191*2a6b7db3Sskrll { 192*2a6b7db3Sskrll fprintf (stderr, "[propagate] toporder botches\n"); 193*2a6b7db3Sskrll } 194*2a6b7db3Sskrll child = child->cg.cyc.head; 195*2a6b7db3Sskrll } 196*2a6b7db3Sskrll else 197*2a6b7db3Sskrll { 198*2a6b7db3Sskrll if (parent->cg.top_order <= child->cg.top_order) 199*2a6b7db3Sskrll { 200*2a6b7db3Sskrll fprintf (stderr, "[propagate] toporder botches\n"); 201*2a6b7db3Sskrll continue; 202*2a6b7db3Sskrll } 203*2a6b7db3Sskrll } 204*2a6b7db3Sskrll if (child->ncalls == 0) 205*2a6b7db3Sskrll { 206*2a6b7db3Sskrll continue; 207*2a6b7db3Sskrll } 208*2a6b7db3Sskrll 209*2a6b7db3Sskrll /* distribute time for this arc: */ 210*2a6b7db3Sskrll arc->time = child->hist.time * (((double) arc->count) 211*2a6b7db3Sskrll / ((double) child->ncalls)); 212*2a6b7db3Sskrll arc->child_time = child->cg.child_time 213*2a6b7db3Sskrll * (((double) arc->count) / ((double) child->ncalls)); 214*2a6b7db3Sskrll share = arc->time + arc->child_time; 215*2a6b7db3Sskrll parent->cg.child_time += share; 216*2a6b7db3Sskrll 217*2a6b7db3Sskrll /* (1 - cg.prop.fract) gets lost along the way: */ 218*2a6b7db3Sskrll prop_share = parent->cg.prop.fract * share; 219*2a6b7db3Sskrll 220*2a6b7db3Sskrll /* fix things for printing: */ 221*2a6b7db3Sskrll parent->cg.prop.child += prop_share; 222*2a6b7db3Sskrll arc->time *= parent->cg.prop.fract; 223*2a6b7db3Sskrll arc->child_time *= parent->cg.prop.fract; 224*2a6b7db3Sskrll 225*2a6b7db3Sskrll /* add this share to the parent's cycle header, if any: */ 226*2a6b7db3Sskrll if (parent->cg.cyc.head != parent) 227*2a6b7db3Sskrll { 228*2a6b7db3Sskrll parent->cg.cyc.head->cg.child_time += share; 229*2a6b7db3Sskrll parent->cg.cyc.head->cg.prop.child += prop_share; 230*2a6b7db3Sskrll } 231*2a6b7db3Sskrll DBG (PROPDEBUG, 232*2a6b7db3Sskrll printf ("[prop_time] child \t"); 233*2a6b7db3Sskrll print_name (child); 234*2a6b7db3Sskrll printf (" with %f %f %lu/%lu\n", child->hist.time, 235*2a6b7db3Sskrll child->cg.child_time, arc->count, child->ncalls); 236*2a6b7db3Sskrll printf ("[prop_time] parent\t"); 237*2a6b7db3Sskrll print_name (parent); 238*2a6b7db3Sskrll printf ("\n[prop_time] share %f\n", share)); 239*2a6b7db3Sskrll } 240*2a6b7db3Sskrll } 241*2a6b7db3Sskrll 242*2a6b7db3Sskrll 243*2a6b7db3Sskrll /* 244*2a6b7db3Sskrll * Compute the time of a cycle as the sum of the times of all 245*2a6b7db3Sskrll * its members. 246*2a6b7db3Sskrll */ 247*2a6b7db3Sskrll static void 248*2a6b7db3Sskrll cycle_time () 249*2a6b7db3Sskrll { 250*2a6b7db3Sskrll Sym *member, *cyc; 251*2a6b7db3Sskrll 252*2a6b7db3Sskrll for (cyc = &cycle_header[1]; cyc <= &cycle_header[num_cycles]; ++cyc) 253*2a6b7db3Sskrll { 254*2a6b7db3Sskrll for (member = cyc->cg.cyc.next; member; member = member->cg.cyc.next) 255*2a6b7db3Sskrll { 256*2a6b7db3Sskrll if (member->cg.prop.fract == 0.0) 257*2a6b7db3Sskrll { 258*2a6b7db3Sskrll /* 259*2a6b7db3Sskrll * All members have the same propfraction except those 260*2a6b7db3Sskrll * that were excluded with -E. 261*2a6b7db3Sskrll */ 262*2a6b7db3Sskrll continue; 263*2a6b7db3Sskrll } 264*2a6b7db3Sskrll cyc->hist.time += member->hist.time; 265*2a6b7db3Sskrll } 266*2a6b7db3Sskrll cyc->cg.prop.self = cyc->cg.prop.fract * cyc->hist.time; 267*2a6b7db3Sskrll } 268*2a6b7db3Sskrll } 269*2a6b7db3Sskrll 270*2a6b7db3Sskrll 271*2a6b7db3Sskrll static void 272*2a6b7db3Sskrll cycle_link () 273*2a6b7db3Sskrll { 274*2a6b7db3Sskrll Sym *sym, *cyc, *member; 275*2a6b7db3Sskrll Arc *arc; 276*2a6b7db3Sskrll int num; 277*2a6b7db3Sskrll 278*2a6b7db3Sskrll /* count the number of cycles, and initialize the cycle lists: */ 279*2a6b7db3Sskrll 280*2a6b7db3Sskrll num_cycles = 0; 281*2a6b7db3Sskrll for (sym = symtab.base; sym < symtab.limit; ++sym) 282*2a6b7db3Sskrll { 283*2a6b7db3Sskrll /* this is how you find unattached cycles: */ 284*2a6b7db3Sskrll if (sym->cg.cyc.head == sym && sym->cg.cyc.next) 285*2a6b7db3Sskrll { 286*2a6b7db3Sskrll ++num_cycles; 287*2a6b7db3Sskrll } 288*2a6b7db3Sskrll } 289*2a6b7db3Sskrll 290*2a6b7db3Sskrll /* 291*2a6b7db3Sskrll * cycle_header is indexed by cycle number: i.e. it is origin 1, 292*2a6b7db3Sskrll * not origin 0. 293*2a6b7db3Sskrll */ 294*2a6b7db3Sskrll cycle_header = (Sym *) xmalloc ((num_cycles + 1) * sizeof (Sym)); 295*2a6b7db3Sskrll 296*2a6b7db3Sskrll /* 297*2a6b7db3Sskrll * Now link cycles to true cycle-heads, number them, accumulate 298*2a6b7db3Sskrll * the data for the cycle. 299*2a6b7db3Sskrll */ 300*2a6b7db3Sskrll num = 0; 301*2a6b7db3Sskrll cyc = cycle_header; 302*2a6b7db3Sskrll for (sym = symtab.base; sym < symtab.limit; ++sym) 303*2a6b7db3Sskrll { 304*2a6b7db3Sskrll if (!(sym->cg.cyc.head == sym && sym->cg.cyc.next != 0)) 305*2a6b7db3Sskrll { 306*2a6b7db3Sskrll continue; 307*2a6b7db3Sskrll } 308*2a6b7db3Sskrll ++num; 309*2a6b7db3Sskrll ++cyc; 310*2a6b7db3Sskrll sym_init (cyc); 311*2a6b7db3Sskrll cyc->cg.print_flag = TRUE; /* should this be printed? */ 312*2a6b7db3Sskrll cyc->cg.top_order = DFN_NAN; /* graph call chain top-sort order */ 313*2a6b7db3Sskrll cyc->cg.cyc.num = num; /* internal number of cycle on */ 314*2a6b7db3Sskrll cyc->cg.cyc.head = cyc; /* pointer to head of cycle */ 315*2a6b7db3Sskrll cyc->cg.cyc.next = sym; /* pointer to next member of cycle */ 316*2a6b7db3Sskrll DBG (CYCLEDEBUG, printf ("[cycle_link] "); 317*2a6b7db3Sskrll print_name (sym); 318*2a6b7db3Sskrll printf (" is the head of cycle %d\n", num)); 319*2a6b7db3Sskrll 320*2a6b7db3Sskrll /* link members to cycle header: */ 321*2a6b7db3Sskrll for (member = sym; member; member = member->cg.cyc.next) 322*2a6b7db3Sskrll { 323*2a6b7db3Sskrll member->cg.cyc.num = num; 324*2a6b7db3Sskrll member->cg.cyc.head = cyc; 325*2a6b7db3Sskrll } 326*2a6b7db3Sskrll 327*2a6b7db3Sskrll /* 328*2a6b7db3Sskrll * Count calls from outside the cycle and those among cycle 329*2a6b7db3Sskrll * members: 330*2a6b7db3Sskrll */ 331*2a6b7db3Sskrll for (member = sym; member; member = member->cg.cyc.next) 332*2a6b7db3Sskrll { 333*2a6b7db3Sskrll for (arc = member->cg.parents; arc; arc = arc->next_parent) 334*2a6b7db3Sskrll { 335*2a6b7db3Sskrll if (arc->parent == member) 336*2a6b7db3Sskrll { 337*2a6b7db3Sskrll continue; 338*2a6b7db3Sskrll } 339*2a6b7db3Sskrll if (arc->parent->cg.cyc.num == num) 340*2a6b7db3Sskrll { 341*2a6b7db3Sskrll cyc->cg.self_calls += arc->count; 342*2a6b7db3Sskrll } 343*2a6b7db3Sskrll else 344*2a6b7db3Sskrll { 345*2a6b7db3Sskrll cyc->ncalls += arc->count; 346*2a6b7db3Sskrll } 347*2a6b7db3Sskrll } 348*2a6b7db3Sskrll } 349*2a6b7db3Sskrll } 350*2a6b7db3Sskrll } 351*2a6b7db3Sskrll 352*2a6b7db3Sskrll 353*2a6b7db3Sskrll /* 354*2a6b7db3Sskrll * Check if any parent of this child (or outside parents of this 355*2a6b7db3Sskrll * cycle) have their print flags on and set the print flag of the 356*2a6b7db3Sskrll * child (cycle) appropriately. Similarly, deal with propagation 357*2a6b7db3Sskrll * fractions from parents. 358*2a6b7db3Sskrll */ 359*2a6b7db3Sskrll static void 360*2a6b7db3Sskrll inherit_flags (Sym *child) 361*2a6b7db3Sskrll { 362*2a6b7db3Sskrll Sym *head, *parent, *member; 363*2a6b7db3Sskrll Arc *arc; 364*2a6b7db3Sskrll 365*2a6b7db3Sskrll head = child->cg.cyc.head; 366*2a6b7db3Sskrll if (child == head) 367*2a6b7db3Sskrll { 368*2a6b7db3Sskrll /* just a regular child, check its parents: */ 369*2a6b7db3Sskrll child->cg.print_flag = FALSE; 370*2a6b7db3Sskrll child->cg.prop.fract = 0.0; 371*2a6b7db3Sskrll for (arc = child->cg.parents; arc; arc = arc->next_parent) 372*2a6b7db3Sskrll { 373*2a6b7db3Sskrll parent = arc->parent; 374*2a6b7db3Sskrll if (child == parent) 375*2a6b7db3Sskrll { 376*2a6b7db3Sskrll continue; 377*2a6b7db3Sskrll } 378*2a6b7db3Sskrll child->cg.print_flag |= parent->cg.print_flag; 379*2a6b7db3Sskrll /* 380*2a6b7db3Sskrll * If the child was never actually called (e.g., this arc 381*2a6b7db3Sskrll * is static (and all others are, too)) no time propagates 382*2a6b7db3Sskrll * along this arc. 383*2a6b7db3Sskrll */ 384*2a6b7db3Sskrll if (child->ncalls != 0) 385*2a6b7db3Sskrll { 386*2a6b7db3Sskrll child->cg.prop.fract += parent->cg.prop.fract 387*2a6b7db3Sskrll * (((double) arc->count) / ((double) child->ncalls)); 388*2a6b7db3Sskrll } 389*2a6b7db3Sskrll } 390*2a6b7db3Sskrll } 391*2a6b7db3Sskrll else 392*2a6b7db3Sskrll { 393*2a6b7db3Sskrll /* 394*2a6b7db3Sskrll * Its a member of a cycle, look at all parents from outside 395*2a6b7db3Sskrll * the cycle. 396*2a6b7db3Sskrll */ 397*2a6b7db3Sskrll head->cg.print_flag = FALSE; 398*2a6b7db3Sskrll head->cg.prop.fract = 0.0; 399*2a6b7db3Sskrll for (member = head->cg.cyc.next; member; member = member->cg.cyc.next) 400*2a6b7db3Sskrll { 401*2a6b7db3Sskrll for (arc = member->cg.parents; arc; arc = arc->next_parent) 402*2a6b7db3Sskrll { 403*2a6b7db3Sskrll if (arc->parent->cg.cyc.head == head) 404*2a6b7db3Sskrll { 405*2a6b7db3Sskrll continue; 406*2a6b7db3Sskrll } 407*2a6b7db3Sskrll parent = arc->parent; 408*2a6b7db3Sskrll head->cg.print_flag |= parent->cg.print_flag; 409*2a6b7db3Sskrll /* 410*2a6b7db3Sskrll * If the cycle was never actually called (e.g. this 411*2a6b7db3Sskrll * arc is static (and all others are, too)) no time 412*2a6b7db3Sskrll * propagates along this arc. 413*2a6b7db3Sskrll */ 414*2a6b7db3Sskrll if (head->ncalls != 0) 415*2a6b7db3Sskrll { 416*2a6b7db3Sskrll head->cg.prop.fract += parent->cg.prop.fract 417*2a6b7db3Sskrll * (((double) arc->count) / ((double) head->ncalls)); 418*2a6b7db3Sskrll } 419*2a6b7db3Sskrll } 420*2a6b7db3Sskrll } 421*2a6b7db3Sskrll for (member = head; member; member = member->cg.cyc.next) 422*2a6b7db3Sskrll { 423*2a6b7db3Sskrll member->cg.print_flag = head->cg.print_flag; 424*2a6b7db3Sskrll member->cg.prop.fract = head->cg.prop.fract; 425*2a6b7db3Sskrll } 426*2a6b7db3Sskrll } 427*2a6b7db3Sskrll } 428*2a6b7db3Sskrll 429*2a6b7db3Sskrll 430*2a6b7db3Sskrll /* 431*2a6b7db3Sskrll * In one top-to-bottom pass over the topologically sorted symbols 432*2a6b7db3Sskrll * propagate: 433*2a6b7db3Sskrll * cg.print_flag as the union of parents' print_flags 434*2a6b7db3Sskrll * propfraction as the sum of fractional parents' propfractions 435*2a6b7db3Sskrll * and while we're here, sum time for functions. 436*2a6b7db3Sskrll */ 437*2a6b7db3Sskrll static void 438*2a6b7db3Sskrll propagate_flags (Sym **symbols) 439*2a6b7db3Sskrll { 440*2a6b7db3Sskrll int index; 441*2a6b7db3Sskrll Sym *old_head, *child; 442*2a6b7db3Sskrll 443*2a6b7db3Sskrll old_head = 0; 444*2a6b7db3Sskrll for (index = symtab.len - 1; index >= 0; --index) 445*2a6b7db3Sskrll { 446*2a6b7db3Sskrll child = symbols[index]; 447*2a6b7db3Sskrll /* 448*2a6b7db3Sskrll * If we haven't done this function or cycle, inherit things 449*2a6b7db3Sskrll * from parent. This way, we are linear in the number of arcs 450*2a6b7db3Sskrll * since we do all members of a cycle (and the cycle itself) 451*2a6b7db3Sskrll * as we hit the first member of the cycle. 452*2a6b7db3Sskrll */ 453*2a6b7db3Sskrll if (child->cg.cyc.head != old_head) 454*2a6b7db3Sskrll { 455*2a6b7db3Sskrll old_head = child->cg.cyc.head; 456*2a6b7db3Sskrll inherit_flags (child); 457*2a6b7db3Sskrll } 458*2a6b7db3Sskrll DBG (PROPDEBUG, 459*2a6b7db3Sskrll printf ("[prop_flags] "); 460*2a6b7db3Sskrll print_name (child); 461*2a6b7db3Sskrll printf ("inherits print-flag %d and prop-fract %f\n", 462*2a6b7db3Sskrll child->cg.print_flag, child->cg.prop.fract)); 463*2a6b7db3Sskrll if (!child->cg.print_flag) 464*2a6b7db3Sskrll { 465*2a6b7db3Sskrll /* 466*2a6b7db3Sskrll * Printflag is off. It gets turned on by being in the 467*2a6b7db3Sskrll * INCL_GRAPH table, or there being an empty INCL_GRAPH 468*2a6b7db3Sskrll * table and not being in the EXCL_GRAPH table. 469*2a6b7db3Sskrll */ 470*2a6b7db3Sskrll if (sym_lookup (&syms[INCL_GRAPH], child->addr) 471*2a6b7db3Sskrll || (syms[INCL_GRAPH].len == 0 472*2a6b7db3Sskrll && !sym_lookup (&syms[EXCL_GRAPH], child->addr))) 473*2a6b7db3Sskrll { 474*2a6b7db3Sskrll child->cg.print_flag = TRUE; 475*2a6b7db3Sskrll } 476*2a6b7db3Sskrll } 477*2a6b7db3Sskrll else 478*2a6b7db3Sskrll { 479*2a6b7db3Sskrll /* 480*2a6b7db3Sskrll * This function has printing parents: maybe someone wants 481*2a6b7db3Sskrll * to shut it up by putting it in the EXCL_GRAPH table. 482*2a6b7db3Sskrll * (But favor INCL_GRAPH over EXCL_GRAPH.) 483*2a6b7db3Sskrll */ 484*2a6b7db3Sskrll if (!sym_lookup (&syms[INCL_GRAPH], child->addr) 485*2a6b7db3Sskrll && sym_lookup (&syms[EXCL_GRAPH], child->addr)) 486*2a6b7db3Sskrll { 487*2a6b7db3Sskrll child->cg.print_flag = FALSE; 488*2a6b7db3Sskrll } 489*2a6b7db3Sskrll } 490*2a6b7db3Sskrll if (child->cg.prop.fract == 0.0) 491*2a6b7db3Sskrll { 492*2a6b7db3Sskrll /* 493*2a6b7db3Sskrll * No parents to pass time to. Collect time from children 494*2a6b7db3Sskrll * if its in the INCL_TIME table, or there is an empty 495*2a6b7db3Sskrll * INCL_TIME table and its not in the EXCL_TIME table. 496*2a6b7db3Sskrll */ 497*2a6b7db3Sskrll if (sym_lookup (&syms[INCL_TIME], child->addr) 498*2a6b7db3Sskrll || (syms[INCL_TIME].len == 0 499*2a6b7db3Sskrll && !sym_lookup (&syms[EXCL_TIME], child->addr))) 500*2a6b7db3Sskrll { 501*2a6b7db3Sskrll child->cg.prop.fract = 1.0; 502*2a6b7db3Sskrll } 503*2a6b7db3Sskrll } 504*2a6b7db3Sskrll else 505*2a6b7db3Sskrll { 506*2a6b7db3Sskrll /* 507*2a6b7db3Sskrll * It has parents to pass time to, but maybe someone wants 508*2a6b7db3Sskrll * to shut it up by puttting it in the EXCL_TIME table. 509*2a6b7db3Sskrll * (But favor being in INCL_TIME tabe over being in 510*2a6b7db3Sskrll * EXCL_TIME table.) 511*2a6b7db3Sskrll */ 512*2a6b7db3Sskrll if (!sym_lookup (&syms[INCL_TIME], child->addr) 513*2a6b7db3Sskrll && sym_lookup (&syms[EXCL_TIME], child->addr)) 514*2a6b7db3Sskrll { 515*2a6b7db3Sskrll child->cg.prop.fract = 0.0; 516*2a6b7db3Sskrll } 517*2a6b7db3Sskrll } 518*2a6b7db3Sskrll child->cg.prop.self = child->hist.time * child->cg.prop.fract; 519*2a6b7db3Sskrll print_time += child->cg.prop.self; 520*2a6b7db3Sskrll DBG (PROPDEBUG, 521*2a6b7db3Sskrll printf ("[prop_flags] "); 522*2a6b7db3Sskrll print_name (child); 523*2a6b7db3Sskrll printf (" ends up with printflag %d and prop-fract %f\n", 524*2a6b7db3Sskrll child->cg.print_flag, child->cg.prop.fract); 525*2a6b7db3Sskrll printf ("[prop_flags] time %f propself %f print_time %f\n", 526*2a6b7db3Sskrll child->hist.time, child->cg.prop.self, print_time)); 527*2a6b7db3Sskrll } 528*2a6b7db3Sskrll } 529*2a6b7db3Sskrll 530*2a6b7db3Sskrll 531*2a6b7db3Sskrll /* 532*2a6b7db3Sskrll * Compare by decreasing propagated time. If times are equal, but one 533*2a6b7db3Sskrll * is a cycle header, say that's first (e.g. less, i.e. -1). If one's 534*2a6b7db3Sskrll * name doesn't have an underscore and the other does, say that one is 535*2a6b7db3Sskrll * first. All else being equal, compare by names. 536*2a6b7db3Sskrll */ 537*2a6b7db3Sskrll static int 538*2a6b7db3Sskrll cmp_total (const PTR lp, const PTR rp) 539*2a6b7db3Sskrll { 540*2a6b7db3Sskrll const Sym *left = *(const Sym **) lp; 541*2a6b7db3Sskrll const Sym *right = *(const Sym **) rp; 542*2a6b7db3Sskrll double diff; 543*2a6b7db3Sskrll 544*2a6b7db3Sskrll diff = (left->cg.prop.self + left->cg.prop.child) 545*2a6b7db3Sskrll - (right->cg.prop.self + right->cg.prop.child); 546*2a6b7db3Sskrll if (diff < 0.0) 547*2a6b7db3Sskrll { 548*2a6b7db3Sskrll return 1; 549*2a6b7db3Sskrll } 550*2a6b7db3Sskrll if (diff > 0.0) 551*2a6b7db3Sskrll { 552*2a6b7db3Sskrll return -1; 553*2a6b7db3Sskrll } 554*2a6b7db3Sskrll if (!left->name && left->cg.cyc.num != 0) 555*2a6b7db3Sskrll { 556*2a6b7db3Sskrll return -1; 557*2a6b7db3Sskrll } 558*2a6b7db3Sskrll if (!right->name && right->cg.cyc.num != 0) 559*2a6b7db3Sskrll { 560*2a6b7db3Sskrll return 1; 561*2a6b7db3Sskrll } 562*2a6b7db3Sskrll if (!left->name) 563*2a6b7db3Sskrll { 564*2a6b7db3Sskrll return -1; 565*2a6b7db3Sskrll } 566*2a6b7db3Sskrll if (!right->name) 567*2a6b7db3Sskrll { 568*2a6b7db3Sskrll return 1; 569*2a6b7db3Sskrll } 570*2a6b7db3Sskrll if (left->name[0] != '_' && right->name[0] == '_') 571*2a6b7db3Sskrll { 572*2a6b7db3Sskrll return -1; 573*2a6b7db3Sskrll } 574*2a6b7db3Sskrll if (left->name[0] == '_' && right->name[0] != '_') 575*2a6b7db3Sskrll { 576*2a6b7db3Sskrll return 1; 577*2a6b7db3Sskrll } 578*2a6b7db3Sskrll if (left->ncalls > right->ncalls) 579*2a6b7db3Sskrll { 580*2a6b7db3Sskrll return -1; 581*2a6b7db3Sskrll } 582*2a6b7db3Sskrll if (left->ncalls < right->ncalls) 583*2a6b7db3Sskrll { 584*2a6b7db3Sskrll return 1; 585*2a6b7db3Sskrll } 586*2a6b7db3Sskrll return strcmp (left->name, right->name); 587*2a6b7db3Sskrll } 588*2a6b7db3Sskrll 589*2a6b7db3Sskrll 590*2a6b7db3Sskrll /* 591*2a6b7db3Sskrll * Topologically sort the graph (collapsing cycles), and propagates 592*2a6b7db3Sskrll * time bottom up and flags top down. 593*2a6b7db3Sskrll */ 594*2a6b7db3Sskrll Sym ** 595*2a6b7db3Sskrll cg_assemble () 596*2a6b7db3Sskrll { 597*2a6b7db3Sskrll Sym *parent, **time_sorted_syms, **top_sorted_syms; 598*2a6b7db3Sskrll unsigned int index; 599*2a6b7db3Sskrll Arc *arc; 600*2a6b7db3Sskrll 601*2a6b7db3Sskrll /* 602*2a6b7db3Sskrll * initialize various things: 603*2a6b7db3Sskrll * zero out child times. 604*2a6b7db3Sskrll * count self-recursive calls. 605*2a6b7db3Sskrll * indicate that nothing is on cycles. 606*2a6b7db3Sskrll */ 607*2a6b7db3Sskrll for (parent = symtab.base; parent < symtab.limit; parent++) 608*2a6b7db3Sskrll { 609*2a6b7db3Sskrll parent->cg.child_time = 0.0; 610*2a6b7db3Sskrll arc = arc_lookup (parent, parent); 611*2a6b7db3Sskrll if (arc && parent == arc->child) 612*2a6b7db3Sskrll { 613*2a6b7db3Sskrll parent->ncalls -= arc->count; 614*2a6b7db3Sskrll parent->cg.self_calls = arc->count; 615*2a6b7db3Sskrll } 616*2a6b7db3Sskrll else 617*2a6b7db3Sskrll { 618*2a6b7db3Sskrll parent->cg.self_calls = 0; 619*2a6b7db3Sskrll } 620*2a6b7db3Sskrll parent->cg.prop.fract = 0.0; 621*2a6b7db3Sskrll parent->cg.prop.self = 0.0; 622*2a6b7db3Sskrll parent->cg.prop.child = 0.0; 623*2a6b7db3Sskrll parent->cg.print_flag = FALSE; 624*2a6b7db3Sskrll parent->cg.top_order = DFN_NAN; 625*2a6b7db3Sskrll parent->cg.cyc.num = 0; 626*2a6b7db3Sskrll parent->cg.cyc.head = parent; 627*2a6b7db3Sskrll parent->cg.cyc.next = 0; 628*2a6b7db3Sskrll if (ignore_direct_calls) 629*2a6b7db3Sskrll { 630*2a6b7db3Sskrll find_call (parent, parent->addr, (parent + 1)->addr); 631*2a6b7db3Sskrll } 632*2a6b7db3Sskrll } 633*2a6b7db3Sskrll /* 634*2a6b7db3Sskrll * Topologically order things. If any node is unnumbered, number 635*2a6b7db3Sskrll * it and any of its descendents. 636*2a6b7db3Sskrll */ 637*2a6b7db3Sskrll for (parent = symtab.base; parent < symtab.limit; parent++) 638*2a6b7db3Sskrll { 639*2a6b7db3Sskrll if (parent->cg.top_order == DFN_NAN) 640*2a6b7db3Sskrll { 641*2a6b7db3Sskrll cg_dfn (parent); 642*2a6b7db3Sskrll } 643*2a6b7db3Sskrll } 644*2a6b7db3Sskrll 645*2a6b7db3Sskrll /* link together nodes on the same cycle: */ 646*2a6b7db3Sskrll cycle_link (); 647*2a6b7db3Sskrll 648*2a6b7db3Sskrll /* sort the symbol table in reverse topological order: */ 649*2a6b7db3Sskrll top_sorted_syms = (Sym **) xmalloc (symtab.len * sizeof (Sym *)); 650*2a6b7db3Sskrll for (index = 0; index < symtab.len; ++index) 651*2a6b7db3Sskrll { 652*2a6b7db3Sskrll top_sorted_syms[index] = &symtab.base[index]; 653*2a6b7db3Sskrll } 654*2a6b7db3Sskrll qsort (top_sorted_syms, symtab.len, sizeof (Sym *), cmp_topo); 655*2a6b7db3Sskrll DBG (DFNDEBUG, 656*2a6b7db3Sskrll printf ("[cg_assemble] topological sort listing\n"); 657*2a6b7db3Sskrll for (index = 0; index < symtab.len; ++index) 658*2a6b7db3Sskrll { 659*2a6b7db3Sskrll printf ("[cg_assemble] "); 660*2a6b7db3Sskrll printf ("%d:", top_sorted_syms[index]->cg.top_order); 661*2a6b7db3Sskrll print_name (top_sorted_syms[index]); 662*2a6b7db3Sskrll printf ("\n"); 663*2a6b7db3Sskrll } 664*2a6b7db3Sskrll ); 665*2a6b7db3Sskrll /* 666*2a6b7db3Sskrll * Starting from the topological top, propagate print flags to 667*2a6b7db3Sskrll * children. also, calculate propagation fractions. this happens 668*2a6b7db3Sskrll * before time propagation since time propagation uses the 669*2a6b7db3Sskrll * fractions. 670*2a6b7db3Sskrll */ 671*2a6b7db3Sskrll propagate_flags (top_sorted_syms); 672*2a6b7db3Sskrll 673*2a6b7db3Sskrll /* 674*2a6b7db3Sskrll * Starting from the topological bottom, propogate children times 675*2a6b7db3Sskrll * up to parents. 676*2a6b7db3Sskrll */ 677*2a6b7db3Sskrll cycle_time (); 678*2a6b7db3Sskrll for (index = 0; index < symtab.len; ++index) 679*2a6b7db3Sskrll { 680*2a6b7db3Sskrll propagate_time (top_sorted_syms[index]); 681*2a6b7db3Sskrll } 682*2a6b7db3Sskrll 683*2a6b7db3Sskrll free (top_sorted_syms); 684*2a6b7db3Sskrll 685*2a6b7db3Sskrll /* 686*2a6b7db3Sskrll * Now, sort by CG.PROP.SELF + CG.PROP.CHILD. Sorting both the regular 687*2a6b7db3Sskrll * function names and cycle headers. 688*2a6b7db3Sskrll */ 689*2a6b7db3Sskrll time_sorted_syms = (Sym **) xmalloc ((symtab.len + num_cycles) * sizeof (Sym *)); 690*2a6b7db3Sskrll for (index = 0; index < symtab.len; index++) 691*2a6b7db3Sskrll { 692*2a6b7db3Sskrll time_sorted_syms[index] = &symtab.base[index]; 693*2a6b7db3Sskrll } 694*2a6b7db3Sskrll for (index = 1; index <= num_cycles; index++) 695*2a6b7db3Sskrll { 696*2a6b7db3Sskrll time_sorted_syms[symtab.len + index - 1] = &cycle_header[index]; 697*2a6b7db3Sskrll } 698*2a6b7db3Sskrll qsort (time_sorted_syms, symtab.len + num_cycles, sizeof (Sym *), 699*2a6b7db3Sskrll cmp_total); 700*2a6b7db3Sskrll for (index = 0; index < symtab.len + num_cycles; index++) 701*2a6b7db3Sskrll { 702*2a6b7db3Sskrll time_sorted_syms[index]->cg.index = index + 1; 703*2a6b7db3Sskrll } 704*2a6b7db3Sskrll return time_sorted_syms; 705*2a6b7db3Sskrll } 706