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