gprof/cg_arcs.c

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