gprof/cg_arcs.c

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