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