gprof/cg_arcs.c

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