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