gprof/cg_arcs.c

   1 /*
   2  * Copyright (c) 1983 Regents of the University of California.
   3  * All rights reserved.
   4  *
   5  * Redistribution and use in source and binary forms are permitted
   6  * provided that: (1) source distributions retain this entire copyright
   7  * notice and comment, and (2) distributions including binaries display
   8  * the following acknowledgement:  ``This product includes software
   9  * developed by the University of California, Berkeley and its contributors''
  10  * in the documentation or other materials provided with the distribution
  11  * and in all advertising materials mentioning features or use of this
  12  * software. Neither the name of the University nor the names of its
  13  * contributors may be used to endorse or promote products derived
  14  * from this software without specific prior written permission.
  15  * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR
  16  * IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED
  17  * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
  18  */
  19 #include "libiberty.h"
  20 #include "gprof.h"
  21 #include "call_graph.h"
  22 #include "cg_arcs.h"
  23 #include "cg_dfn.h"
  24 #include "cg_print.h"
  25 #include "utils.h"
  26 #include "sym_ids.h"
  27
  28 Sym *cycle_header;
  29 int num_cycles;
  30
  31 /*
  32  * Return TRUE iff PARENT has an arc to covers the address
  33  * range covered by CHILD.
  34  */
  35 Arc*
  36 DEFUN(arc_lookup, (parent, child), Sym *parent AND Sym *child)
  37 {
  38     Arc *arc;
  39
  40     if (!parent || !child) {
  41         printf("[arc_lookup] parent == 0 || child == 0\n");
  42         return 0;
  43     } /* if */
  44     DBG(LOOKUPDEBUG, printf("[arc_lookup] parent %s child %s\n",
  45                             parent->name, child->name));
  46     for (arc = parent->cg.children; arc; arc = arc->next_child) {
  47         DBG(LOOKUPDEBUG, printf("[arc_lookup]\t parent %s child %s\n",
  48                                 arc->parent->name, arc->child->name));
  49         if (child->addr >= arc->child->addr
  50             && child->end_addr <= arc->child->end_addr)
  51         {
  52             return arc;
  53         } /* if */
  54     } /* for */
  55     return 0;
  56 } /* arc_lookup */
  57
  58
  59 /*
  60  * Add (or just increment) an arc:
  61  */
  62 void
  63 DEFUN(arc_add, (parent, child, count),
  64       Sym *parent AND Sym *child AND int count)
  65 {
  66     Arc *arc;
  67
  68     DBG(TALLYDEBUG, printf("[arc_add] %d arcs from %s to %s\n",
  69                            count, parent->name, child->name));
  70     arc = arc_lookup(parent, child);
  71     if (arc) {
  72         /*
  73          * A hit: just increment the count.
  74          */
  75         DBG(TALLYDEBUG, printf("[tally] hit %d += %d\n",
  76                                arc->count, count));
  77         arc->count += count;
  78         return;
  79     } /* if */
  80     arc = (Arc*)xmalloc(sizeof(*arc));
  81     arc->parent = parent;
  82     arc->child = child;
  83     arc->count = count;
  84
  85     /* prepend this child to the children of this parent: */
  86     arc->next_child = parent->cg.children;
  87     parent->cg.children = arc;
  88
  89     /* prepend this parent to the parents of this child: */
  90     arc->next_parent = child->cg.parents;
  91     child->cg.parents = arc;
  92 } /* arc_add */
  93
  94
  95 static int
  96 DEFUN(cmp_topo, (lp, rp), const PTR lp AND const PTR rp)
  97 {
  98     const Sym *left = *(const Sym **) lp;
  99     const Sym *right = *(const Sym **) rp;
 100
 101     return left->cg.top_order - right->cg.top_order;
 102 } /* cmp_topo */
 103
 104
 105 static void
 106 DEFUN(propagate_time, (parent), Sym *parent)
 107 {
 108     Arc *arc;
 109     Sym *child;
 110     double share, prop_share;
 111
 112     if (parent->cg.prop.fract == 0.0) {
 113         return;
 114     } /* if */
 115
 116     /* gather time from children of this parent: */
 117
 118     for (arc = parent->cg.children; arc; arc = arc->next_child) {
 119         child = arc->child;
 120         if (arc->count == 0 || child == parent || child->cg.prop.fract == 0) {
 121             continue;
 122         } /* if */
 123         if (child->cg.cyc.head != child) {
 124             if (parent->cg.cyc.num == child->cg.cyc.num) {
 125                 continue;
 126             } /* if */
 127             if (parent->cg.top_order <= child->cg.top_order) {
 128                 fprintf(stderr, "[propagate] toporder botches\n");
 129             } /* if */
 130             child = child->cg.cyc.head;
 131         } else {
 132             if (parent->cg.top_order <= child->cg.top_order) {
 133                 fprintf(stderr, "[propagate] toporder botches\n");
 134                 continue;
 135             } /* if */
 136         } /* if */
 137         if (child->ncalls == 0) {
 138             continue;
 139         } /* if */
 140
 141         /* distribute time for this arc: */
 142         arc->time = child->hist.time * (((double) arc->count)
 143                                         / ((double) child->ncalls));
 144         arc->child_time = child->cg.child_time
 145           * (((double) arc->count) / ((double) child->ncalls));
 146         share = arc->time + arc->child_time;
 147         parent->cg.child_time += share;
 148
 149         /* (1 - cg.prop.fract) gets lost along the way: */
 150         prop_share = parent->cg.prop.fract * share;
 151
 152         /* fix things for printing: */
 153         parent->cg.prop.child += prop_share;
 154         arc->time *= parent->cg.prop.fract;
 155         arc->child_time *= parent->cg.prop.fract;
 156
 157         /* add this share to the parent's cycle header, if any: */
 158         if (parent->cg.cyc.head != parent) {
 159             parent->cg.cyc.head->cg.child_time += share;
 160             parent->cg.cyc.head->cg.prop.child += prop_share;
 161         } /* if */
 162         DBG(PROPDEBUG,
 163             printf("[prop_time] child \t");
 164             print_name(child);
 165             printf(" with %f %f %d/%d\n", child->hist.time,
 166                    child->cg.child_time, arc->count, child->ncalls);
 167             printf("[prop_time] parent\t");
 168             print_name(parent);
 169             printf("\n[prop_time] share %f\n", share));
 170     } /* for */
 171 } /* propagate_time */
 172
 173
 174 /*
 175  * Compute the time of a cycle as the sum of the times of all
 176  * its members.
 177  */
 178 static void
 179 DEFUN_VOID(cycle_time)
 180 {
 181     Sym *member, *cyc;
 182
 183     for (cyc = &cycle_header[1]; cyc <= &cycle_header[num_cycles]; ++cyc) {
 184         for (member = cyc->cg.cyc.next; member; member = member->cg.cyc.next) {
 185             if (member->cg.prop.fract == 0.0) {
 186                 /*
 187                  * All members have the same propfraction except those
 188                  * that were excluded with -E.
 189                  */
 190                 continue;
 191             } /* if */
 192             cyc->hist.time += member->hist.time;
 193         } /* for */
 194         cyc->cg.prop.self = cyc->cg.prop.fract * cyc->hist.time;
 195     } /* for */
 196 } /* cycle_time */
 197
 198
 199 static void
 200 DEFUN_VOID(cycle_link)
 201 {
 202     Sym *sym, *cyc, *member;
 203     Arc *arc;
 204     int num;
 205
 206     /* count the number of cycles, and initialize the cycle lists: */
 207
 208     num_cycles = 0;
 209     for (sym = symtab.base; sym < symtab.limit; ++sym) {
 210         /* this is how you find unattached cycles: */
 211         if (sym->cg.cyc.head == sym && sym->cg.cyc.next) {
 212             ++num_cycles;
 213         } /* if */
 214     } /* for */
 215
 216     /*
 217      * cycle_header is indexed by cycle number: i.e. it is origin 1,
 218      * not origin 0.
 219      */
 220     cycle_header = (Sym*)xmalloc((num_cycles + 1) * sizeof(Sym));
 221
 222     /*
 223      * Now link cycles to true cycle-heads, number them, accumulate
 224      * the data for the cycle.
 225      */
 226     num = 0; cyc = cycle_header;
 227     for (sym = symtab.base; sym < symtab.limit; ++sym) {
 228         if (!(sym->cg.cyc.head == sym && sym->cg.cyc.next != 0)) {
 229             continue;
 230         } /* if */
 231         ++num; ++cyc;
 232         sym_init(cyc);
 233         cyc->cg.print_flag = TRUE;      /* should this be printed? */
 234         cyc->cg.top_order = DFN_NAN;    /* graph call chain top-sort order */
 235         cyc->cg.cyc.num = num;          /* internal number of cycle on */
 236         cyc->cg.cyc.head = cyc;         /* pointer to head of cycle */
 237         cyc->cg.cyc.next = sym;         /* pointer to next member of cycle */
 238         DBG(CYCLEDEBUG, printf("[cycle_link] "); print_name(sym);
 239             printf(" is the head of cycle %d\n", num));
 240
 241         /* link members to cycle header: */
 242         for (member = sym; member; member = member->cg.cyc.next) {
 243             member->cg.cyc.num = num;
 244             member->cg.cyc.head = cyc;
 245         } /* for */
 246
 247         /*
 248          * Count calls from outside the cycle and those among cycle
 249          * members:
 250          */
 251         for (member = sym; member; member = member->cg.cyc.next) {
 252             for (arc = member->cg.parents; arc; arc = arc->next_parent) {
 253                 if (arc->parent == member) {
 254                     continue;
 255                 } /* if */
 256                 if (arc->parent->cg.cyc.num == num) {
 257                     cyc->cg.self_calls += arc->count;
 258                 } else {
 259                     cyc->ncalls += arc->count;
 260                 } /* if */
 261             } /* for */
 262         } /* for */
 263     } /* for */
 264 } /* cycle_link */
 265
 266
 267 /*
 268  * Check if any parent of this child (or outside parents of this
 269  * cycle) have their print flags on and set the print flag of the
 270  * child (cycle) appropriately.  Similarly, deal with propagation
 271  * fractions from parents.
 272  */
 273 static void
 274 DEFUN(inherit_flags, (child), Sym *child)
 275 {
 276     Sym *head, *parent, *member;
 277     Arc *arc;
 278
 279     head = child->cg.cyc.head;
 280     if (child == head) {
 281         /* just a regular child, check its parents: */
 282         child->cg.print_flag = FALSE;
 283         child->cg.prop.fract = 0.0;
 284         for (arc = child->cg.parents; arc; arc = arc->next_parent) {
 285             parent = arc->parent;
 286             if (child == parent) {
 287                 continue;
 288             } /* if */
 289             child->cg.print_flag |= parent->cg.print_flag;
 290             /*
 291              * If the child was never actually called (e.g., this arc
 292              * is static (and all others are, too)) no time propagates
 293              * along this arc.
 294              */
 295             if (child->ncalls) {
 296                 child->cg.prop.fract += parent->cg.prop.fract
 297                   * (((double) arc->count) / ((double) child->ncalls));
 298             } /* if */
 299         } /* for */
 300     } else {
 301         /*
 302          * Its a member of a cycle, look at all parents from outside
 303          * the cycle.
 304          */
 305         head->cg.print_flag = FALSE;
 306         head->cg.prop.fract = 0.0;
 307         for (member = head->cg.cyc.next; member; member = member->cg.cyc.next)
 308         {
 309             for (arc = member->cg.parents; arc; arc = arc->next_parent) {
 310                 if (arc->parent->cg.cyc.head == head) {
 311                     continue;
 312                 } /* if */
 313                 parent = arc->parent;
 314                 head->cg.print_flag |= parent->cg.print_flag;
 315                 /*
 316                  * If the cycle was never actually called (e.g. this
 317                  * arc is static (and all others are, too)) no time
 318                  * propagates along this arc.
 319                  */
 320                 if (head->ncalls) {
 321                     head->cg.prop.fract += parent->cg.prop.fract
 322                       * (((double) arc->count) / ((double) head->ncalls));
 323                 } /* if */
 324             } /* for */
 325         } /* for */
 326         for (member = head; member; member = member->cg.cyc.next) {
 327             member->cg.print_flag = head->cg.print_flag;
 328             member->cg.prop.fract = head->cg.prop.fract;
 329         } /* for */
 330     } /* if */
 331 } /* inherit_flags */
 332
 333
 334 /*
 335  * In one top-to-bottom pass over the topologically sorted symbols
 336  * propagate:
 337  *      cg.print_flag as the union of parents' print_flags
 338  *      propfraction as the sum of fractional parents' propfractions
 339  * and while we're here, sum time for functions.
 340  */
 341 static void
 342 DEFUN(propagate_flags, (symbols), Sym **symbols)
 343 {
 344     int index;
 345     Sym *old_head, *child;
 346
 347     old_head = 0;
 348     for (index = symtab.len - 1; index >= 0; --index) {
 349         child = symbols[index];
 350         /*
 351          * If we haven't done this function or cycle, inherit things
 352          * from parent.  This way, we are linear in the number of arcs
 353          * since we do all members of a cycle (and the cycle itself)
 354          * as we hit the first member of the cycle.
 355          */
 356         if (child->cg.cyc.head != old_head) {
 357             old_head = child->cg.cyc.head;
 358             inherit_flags(child);
 359         } /* if */
 360         DBG(PROPDEBUG,
 361             printf("[prop_flags] ");
 362             print_name(child);
 363             printf("inherits print-flag %d and prop-fract %f\n",
 364                    child->cg.print_flag, child->cg.prop.fract));
 365         if (!child->cg.print_flag) {
 366             /*
 367              * Printflag is off. It gets turned on by being in the
 368              * INCL_GRAPH table, or there being an empty INCL_GRAPH
 369              * table and not being in the EXCL_GRAPH table.
 370              */
 371             if (sym_lookup(&syms[INCL_GRAPH], child->addr)
 372                 || (syms[INCL_GRAPH].len == 0
 373                     && !sym_lookup(&syms[EXCL_GRAPH], child->addr)))
 374             {
 375                 child->cg.print_flag = TRUE;
 376             } /* if */
 377         } else {
 378             /*
 379              * This function has printing parents: maybe someone wants
 380              * to shut it up by putting it in the EXCL_GRAPH table.
 381              * (But favor INCL_GRAPH over EXCL_GRAPH.)
 382              */
 383             if (!sym_lookup(&syms[INCL_GRAPH], child->addr)
 384                 && sym_lookup(&syms[EXCL_GRAPH], child->addr))
 385             {
 386                 child->cg.print_flag = FALSE;
 387             } /* if */
 388         } /* if */
 389         if (child->cg.prop.fract == 0.0) {
 390             /*
 391              * No parents to pass time to.  Collect time from children
 392              * if its in the INCL_TIME table, or there is an empty
 393              * INCL_TIME table and its not in the EXCL_TIME table.
 394              */
 395             if (sym_lookup(&syms[INCL_TIME], child->addr)
 396                 || (syms[INCL_TIME].len == 0
 397                     && !sym_lookup(&syms[EXCL_TIME], child->addr)))
 398             {
 399                 child->cg.prop.fract = 1.0;
 400             } /* if */
 401         } else {
 402             /*
 403              * It has parents to pass time to, but maybe someone wants
 404              * to shut it up by puttting it in the EXCL_TIME table.
 405              * (But favor being in INCL_TIME tabe over being in
 406              * EXCL_TIME table.)
 407              */
 408             if (!sym_lookup(&syms[INCL_TIME], child->addr)
 409                 && sym_lookup(&syms[EXCL_TIME], child->addr))
 410             {
 411                 child->cg.prop.fract = 0.0;
 412             } /* if */
 413         } /* if */
 414         child->cg.prop.self = child->hist.time * child->cg.prop.fract;
 415         print_time += child->cg.prop.self;
 416         DBG(PROPDEBUG,
 417             printf("[prop_flags] ");
 418             print_name(child);
 419             printf(" ends up with printflag %d and prop-fract %f\n",
 420                    child->cg.print_flag, child->cg.prop.fract);
 421             printf("[prop_flags] time %f propself %f print_time %f\n",
 422                    child->hist.time, child->cg.prop.self, print_time));
 423     } /* if */
 424 } /* propagate_flags */
 425
 426
 427 /*
 428  * Compare by decreasing propagated time.  If times are equal, but one
 429  * is a cycle header, say that's first (e.g. less, i.e. -1).  If one's
 430  * name doesn't have an underscore and the other does, say that one is
 431  * first.  All else being equal, compare by names.
 432  */
 433 static int
 434 DEFUN(cmp_total, (lp, rp), const PTR lp AND const PTR rp)
 435 {
 436     const Sym *left = *(const Sym**)lp;
 437     const Sym *right = *(const Sym**)rp;
 438     double diff;
 439
 440     diff = (left->cg.prop.self + left->cg.prop.child)
 441       - (right->cg.prop.self + right->cg.prop.child);
 442     if (diff < 0.0) {
 443         return 1;
 444     } /* if */
 445     if (diff > 0.0) {
 446         return -1;
 447     } /* if */
 448     if (!left->name && left->cg.cyc.num != 0) {
 449         return -1;
 450     } /* if */
 451     if (!right->name && right->cg.cyc.num != 0) {
 452         return 1;
 453     } /* if */
 454     if (!left->name) {
 455         return -1;
 456     } /* if */
 457     if (!right->name) {
 458         return 1;
 459     } /* if */
 460     if (left->name[0] != '_' && right->name[0] == '_') {
 461         return -1;
 462     } /* if */
 463     if (left->name[0] == '_' && right->name[0] != '_') {
 464         return 1;
 465     } /* if */
 466     if (left->ncalls > right->ncalls) {
 467         return -1;
 468     } /* if */
 469     if (left->ncalls < right->ncalls) {
 470         return 1;
 471     } /* if */
 472     return strcmp(left->name, right->name);
 473 } /* cmp_total */
 474
 475
 476 /*
 477  * Topologically sort the graph (collapsing cycles), and propagates
 478  * time bottom up and flags top down.
 479  */
 480 Sym**
 481 DEFUN_VOID(cg_assemble)
 482 {
 483     Sym *parent, **time_sorted_syms, **top_sorted_syms;
 484     long index;
 485     Arc *arc;
 486     extern void find_call PARAMS((Sym *parent,
 487                                   bfd_vma p_lowpc, bfd_vma p_highpc));
 488     /*
 489      * initialize various things:
 490      *      zero out child times.
 491      *      count self-recursive calls.
 492      *      indicate that nothing is on cycles.
 493      */
 494     for (parent = symtab.base; parent < symtab.limit; parent++) {
 495         parent->cg.child_time = 0.0;
 496         arc = arc_lookup(parent, parent);
 497         if (arc && parent == arc->child) {
 498             parent->ncalls -= arc->count;
 499             parent->cg.self_calls = arc->count;
 500         } else {
 501             parent->cg.self_calls = 0;
 502         } /* if */
 503         parent->cg.prop.fract = 0.0;
 504         parent->cg.prop.self = 0.0;
 505         parent->cg.prop.child = 0.0;
 506         parent->cg.print_flag = FALSE;
 507         parent->cg.top_order = DFN_NAN;
 508         parent->cg.cyc.num = 0;
 509         parent->cg.cyc.head = parent;
 510         parent->cg.cyc.next = 0;
 511         if (ignore_direct_calls) {
 512             find_call(parent, parent->addr, (parent+1)->addr);
 513         } /* if */
 514     } /* for */
 515     /*
 516      * Topologically order things.  If any node is unnumbered, number
 517      * it and any of its descendents.
 518      */
 519     for (parent = symtab.base; parent < symtab.limit; parent++) {
 520         if (parent->cg.top_order == DFN_NAN) {
 521             cg_dfn(parent);
 522         } /* if */
 523     } /* for */
 524
 525     /* link together nodes on the same cycle: */
 526     cycle_link();
 527
 528     /* sort the symbol table in reverse topological order: */
 529     top_sorted_syms = (Sym**)xmalloc(symtab.len * sizeof(Sym*));
 530     for (index = 0; index < symtab.len; ++index) {
 531         top_sorted_syms[index] = &symtab.base[index];
 532     } /* for */
 533     qsort(top_sorted_syms, symtab.len, sizeof(Sym *), cmp_topo);
 534     DBG(DFNDEBUG,
 535         printf("[cg_assemble] topological sort listing\n");
 536         for (index = 0; index < symtab.len; ++index) {
 537             printf("[cg_assemble] ");
 538             printf("%d:", top_sorted_syms[index]->cg.top_order);
 539             print_name(top_sorted_syms[index]);
 540             printf("\n");
 541         } /* for */);
 542     /*
 543      * Starting from the topological top, propagate print flags to
 544      * children.  also, calculate propagation fractions.  this happens
 545      * before time propagation since time propagation uses the
 546      * fractions.
 547      */
 548     propagate_flags(top_sorted_syms);
 549
 550     /*
 551      * Starting from the topological bottom, propogate children times
 552      * up to parents.
 553      */
 554     cycle_time();
 555     for (index = 0; index < symtab.len; ++index) {
 556         propagate_time(top_sorted_syms[index]);
 557     } /* for */
 558
 559     free(top_sorted_syms);
 560
 561     /*
 562      * Now, sort by CG.PROP.SELF + CG.PROP.CHILD.  Sorting both the regular
 563      * function names and cycle headers.
 564      */
 565     time_sorted_syms = (Sym**)xmalloc((symtab.len + num_cycles)*sizeof(Sym*));
 566     for (index = 0; index < symtab.len; index++) {
 567         time_sorted_syms[index] = &symtab.base[index];
 568     } /* if */
 569     for (index = 1; index <= num_cycles; index++) {
 570         time_sorted_syms[symtab.len + index - 1] = &cycle_header[index];
 571     } /* for */
 572     qsort(time_sorted_syms, symtab.len + num_cycles, sizeof(Sym*),
 573           cmp_total);
 574     for (index = 0; index < symtab.len + num_cycles; index++) {
 575         time_sorted_syms[index]->cg.index = index + 1;
 576     } /* for */
 577     return time_sorted_syms;
 578 } /* cg_assemble */
 579
 580                         /*** end of cg_arcs.c ***/