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