Back to index

cell-binutils  2.17cvs20070401
cg_arcs.c
Go to the documentation of this file.
00001 /*
00002  * Copyright (c) 1983, 1993, 2001
00003  *      The Regents of the University of California.  All rights reserved.
00004  *
00005  * Redistribution and use in source and binary forms, with or without
00006  * modification, are permitted provided that the following conditions
00007  * are met:
00008  * 1. Redistributions of source code must retain the above copyright
00009  *    notice, this list of conditions and the following disclaimer.
00010  * 2. Redistributions in binary form must reproduce the above copyright
00011  *    notice, this list of conditions and the following disclaimer in the
00012  *    documentation and/or other materials provided with the distribution.
00013  * 3. Neither the name of the University nor the names of its contributors
00014  *    may be used to endorse or promote products derived from this software
00015  *    without specific prior written permission.
00016  *
00017  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
00018  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
00019  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
00020  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
00021  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
00022  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
00023  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
00024  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
00025  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
00026  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
00027  * SUCH DAMAGE.
00028  */
00029 #include "libiberty.h"
00030 #include "gprof.h"
00031 #include "search_list.h"
00032 #include "source.h"
00033 #include "symtab.h"
00034 #include "call_graph.h"
00035 #include "cg_arcs.h"
00036 #include "cg_dfn.h"
00037 #include "cg_print.h"
00038 #include "utils.h"
00039 #include "sym_ids.h"
00040 
00041 static int cmp_topo (const PTR, const PTR);
00042 static void propagate_time (Sym *);
00043 static void cycle_time (void);
00044 static void cycle_link (void);
00045 static void inherit_flags (Sym *);
00046 static void propagate_flags (Sym **);
00047 static int cmp_total (const PTR, const PTR);
00048 
00049 Sym *cycle_header;
00050 unsigned int num_cycles;
00051 Arc **arcs;
00052 unsigned int numarcs;
00053 
00054 /*
00055  * Return TRUE iff PARENT has an arc to covers the address
00056  * range covered by CHILD.
00057  */
00058 Arc *
00059 arc_lookup (Sym *parent, Sym *child)
00060 {
00061   Arc *arc;
00062 
00063   if (!parent || !child)
00064     {
00065       printf ("[arc_lookup] parent == 0 || child == 0\n");
00066       return 0;
00067     }
00068   DBG (LOOKUPDEBUG, printf ("[arc_lookup] parent %s child %s\n",
00069                          parent->name, child->name));
00070   for (arc = parent->cg.children; arc; arc = arc->next_child)
00071     {
00072       DBG (LOOKUPDEBUG, printf ("[arc_lookup]\t parent %s child %s\n",
00073                             arc->parent->name, arc->child->name));
00074       if (child->addr >= arc->child->addr
00075          && child->end_addr <= arc->child->end_addr)
00076        {
00077          return arc;
00078        }
00079     }
00080   return 0;
00081 }
00082 
00083 
00084 /*
00085  * Add (or just increment) an arc:
00086  */
00087 void
00088 arc_add (Sym *parent, Sym *child, unsigned long count)
00089 {
00090   static unsigned int maxarcs = 0;
00091   Arc *arc, **newarcs;
00092 
00093   DBG (TALLYDEBUG, printf ("[arc_add] %lu arcs from %s to %s\n",
00094                         count, parent->name, child->name));
00095   arc = arc_lookup (parent, child);
00096   if (arc)
00097     {
00098       /*
00099        * A hit: just increment the count.
00100        */
00101       DBG (TALLYDEBUG, printf ("[tally] hit %lu += %lu\n",
00102                             arc->count, count));
00103       arc->count += count;
00104       return;
00105     }
00106   arc = (Arc *) xmalloc (sizeof (*arc));
00107   memset (arc, 0, sizeof (*arc));
00108   arc->parent = parent;
00109   arc->child = child;
00110   arc->count = count;
00111 
00112   /* If this isn't an arc for a recursive call to parent, then add it
00113      to the array of arcs.  */
00114   if (parent != child)
00115     {
00116       /* If we've exhausted space in our current array, get a new one
00117         and copy the contents.   We might want to throttle the doubling
00118         factor one day.  */
00119       if (numarcs == maxarcs)
00120        {
00121          /* Determine how much space we want to allocate.  */
00122          if (maxarcs == 0)
00123            maxarcs = 1;
00124          maxarcs *= 2;
00125 
00126          /* Allocate the new array.  */
00127          newarcs = (Arc **)xmalloc(sizeof (Arc *) * maxarcs);
00128 
00129          /* Copy the old array's contents into the new array.  */
00130          memcpy (newarcs, arcs, numarcs * sizeof (Arc *));
00131 
00132          /* Free up the old array.  */
00133          free (arcs);
00134 
00135          /* And make the new array be the current array.  */
00136          arcs = newarcs;
00137        }
00138 
00139       /* Place this arc in the arc array.  */
00140       arcs[numarcs++] = arc;
00141     }
00142 
00143   /* prepend this child to the children of this parent: */
00144   arc->next_child = parent->cg.children;
00145   parent->cg.children = arc;
00146 
00147   /* prepend this parent to the parents of this child: */
00148   arc->next_parent = child->cg.parents;
00149   child->cg.parents = arc;
00150 }
00151 
00152 
00153 static int
00154 cmp_topo (const PTR lp, const PTR rp)
00155 {
00156   const Sym *left = *(const Sym **) lp;
00157   const Sym *right = *(const Sym **) rp;
00158 
00159   return left->cg.top_order - right->cg.top_order;
00160 }
00161 
00162 
00163 static void
00164 propagate_time (Sym *parent)
00165 {
00166   Arc *arc;
00167   Sym *child;
00168   double share, prop_share;
00169 
00170   if (parent->cg.prop.fract == 0.0)
00171     {
00172       return;
00173     }
00174 
00175   /* gather time from children of this parent: */
00176 
00177   for (arc = parent->cg.children; arc; arc = arc->next_child)
00178     {
00179       child = arc->child;
00180       if (arc->count == 0 || child == parent || child->cg.prop.fract == 0)
00181        {
00182          continue;
00183        }
00184       if (child->cg.cyc.head != child)
00185        {
00186          if (parent->cg.cyc.num == child->cg.cyc.num)
00187            {
00188              continue;
00189            }
00190          if (parent->cg.top_order <= child->cg.top_order)
00191            {
00192              fprintf (stderr, "[propagate] toporder botches\n");
00193            }
00194          child = child->cg.cyc.head;
00195        }
00196       else
00197        {
00198          if (parent->cg.top_order <= child->cg.top_order)
00199            {
00200              fprintf (stderr, "[propagate] toporder botches\n");
00201              continue;
00202            }
00203        }
00204       if (child->ncalls == 0)
00205        {
00206          continue;
00207        }
00208 
00209       /* distribute time for this arc: */
00210       arc->time = child->hist.time * (((double) arc->count)
00211                                   / ((double) child->ncalls));
00212       arc->child_time = child->cg.child_time
00213        * (((double) arc->count) / ((double) child->ncalls));
00214       share = arc->time + arc->child_time;
00215       parent->cg.child_time += share;
00216 
00217       /* (1 - cg.prop.fract) gets lost along the way: */
00218       prop_share = parent->cg.prop.fract * share;
00219 
00220       /* fix things for printing: */
00221       parent->cg.prop.child += prop_share;
00222       arc->time *= parent->cg.prop.fract;
00223       arc->child_time *= parent->cg.prop.fract;
00224 
00225       /* add this share to the parent's cycle header, if any: */
00226       if (parent->cg.cyc.head != parent)
00227        {
00228          parent->cg.cyc.head->cg.child_time += share;
00229          parent->cg.cyc.head->cg.prop.child += prop_share;
00230        }
00231       DBG (PROPDEBUG,
00232           printf ("[prop_time] child \t");
00233           print_name (child);
00234           printf (" with %f %f %lu/%lu\n", child->hist.time,
00235                  child->cg.child_time, arc->count, child->ncalls);
00236           printf ("[prop_time] parent\t");
00237           print_name (parent);
00238           printf ("\n[prop_time] share %f\n", share));
00239     }
00240 }
00241 
00242 
00243 /*
00244  * Compute the time of a cycle as the sum of the times of all
00245  * its members.
00246  */
00247 static void
00248 cycle_time ()
00249 {
00250   Sym *member, *cyc;
00251 
00252   for (cyc = &cycle_header[1]; cyc <= &cycle_header[num_cycles]; ++cyc)
00253     {
00254       for (member = cyc->cg.cyc.next; member; member = member->cg.cyc.next)
00255        {
00256          if (member->cg.prop.fract == 0.0)
00257            {
00258              /*
00259               * All members have the same propfraction except those
00260               * that were excluded with -E.
00261               */
00262              continue;
00263            }
00264          cyc->hist.time += member->hist.time;
00265        }
00266       cyc->cg.prop.self = cyc->cg.prop.fract * cyc->hist.time;
00267     }
00268 }
00269 
00270 
00271 static void
00272 cycle_link ()
00273 {
00274   Sym *sym, *cyc, *member;
00275   Arc *arc;
00276   int num;
00277 
00278   /* count the number of cycles, and initialize the cycle lists: */
00279 
00280   num_cycles = 0;
00281   for (sym = symtab.base; sym < symtab.limit; ++sym)
00282     {
00283       /* this is how you find unattached cycles: */
00284       if (sym->cg.cyc.head == sym && sym->cg.cyc.next)
00285        {
00286          ++num_cycles;
00287        }
00288     }
00289 
00290   /*
00291    * cycle_header is indexed by cycle number: i.e. it is origin 1,
00292    * not origin 0.
00293    */
00294   cycle_header = (Sym *) xmalloc ((num_cycles + 1) * sizeof (Sym));
00295 
00296   /*
00297    * Now link cycles to true cycle-heads, number them, accumulate
00298    * the data for the cycle.
00299    */
00300   num = 0;
00301   cyc = cycle_header;
00302   for (sym = symtab.base; sym < symtab.limit; ++sym)
00303     {
00304       if (!(sym->cg.cyc.head == sym && sym->cg.cyc.next != 0))
00305        {
00306          continue;
00307        }
00308       ++num;
00309       ++cyc;
00310       sym_init (cyc);
00311       cyc->cg.print_flag = TRUE;   /* should this be printed? */
00312       cyc->cg.top_order = DFN_NAN; /* graph call chain top-sort order */
00313       cyc->cg.cyc.num = num;       /* internal number of cycle on */
00314       cyc->cg.cyc.head = cyc;      /* pointer to head of cycle */
00315       cyc->cg.cyc.next = sym;      /* pointer to next member of cycle */
00316       DBG (CYCLEDEBUG, printf ("[cycle_link] ");
00317           print_name (sym);
00318           printf (" is the head of cycle %d\n", num));
00319 
00320       /* link members to cycle header: */
00321       for (member = sym; member; member = member->cg.cyc.next)
00322        {
00323          member->cg.cyc.num = num;
00324          member->cg.cyc.head = cyc;
00325        }
00326 
00327       /*
00328        * Count calls from outside the cycle and those among cycle
00329        * members:
00330        */
00331       for (member = sym; member; member = member->cg.cyc.next)
00332        {
00333          for (arc = member->cg.parents; arc; arc = arc->next_parent)
00334            {
00335              if (arc->parent == member)
00336               {
00337                 continue;
00338               }
00339              if (arc->parent->cg.cyc.num == num)
00340               {
00341                 cyc->cg.self_calls += arc->count;
00342               }
00343              else
00344               {
00345                 cyc->ncalls += arc->count;
00346               }
00347            }
00348        }
00349     }
00350 }
00351 
00352 
00353 /*
00354  * Check if any parent of this child (or outside parents of this
00355  * cycle) have their print flags on and set the print flag of the
00356  * child (cycle) appropriately.  Similarly, deal with propagation
00357  * fractions from parents.
00358  */
00359 static void
00360 inherit_flags (Sym *child)
00361 {
00362   Sym *head, *parent, *member;
00363   Arc *arc;
00364 
00365   head = child->cg.cyc.head;
00366   if (child == head)
00367     {
00368       /* just a regular child, check its parents: */
00369       child->cg.print_flag = FALSE;
00370       child->cg.prop.fract = 0.0;
00371       for (arc = child->cg.parents; arc; arc = arc->next_parent)
00372        {
00373          parent = arc->parent;
00374          if (child == parent)
00375            {
00376              continue;
00377            }
00378          child->cg.print_flag |= parent->cg.print_flag;
00379          /*
00380           * If the child was never actually called (e.g., this arc
00381           * is static (and all others are, too)) no time propagates
00382           * along this arc.
00383           */
00384          if (child->ncalls != 0)
00385            {
00386              child->cg.prop.fract += parent->cg.prop.fract
00387               * (((double) arc->count) / ((double) child->ncalls));
00388            }
00389        }
00390     }
00391   else
00392     {
00393       /*
00394        * Its a member of a cycle, look at all parents from outside
00395        * the cycle.
00396        */
00397       head->cg.print_flag = FALSE;
00398       head->cg.prop.fract = 0.0;
00399       for (member = head->cg.cyc.next; member; member = member->cg.cyc.next)
00400        {
00401          for (arc = member->cg.parents; arc; arc = arc->next_parent)
00402            {
00403              if (arc->parent->cg.cyc.head == head)
00404               {
00405                 continue;
00406               }
00407              parent = arc->parent;
00408              head->cg.print_flag |= parent->cg.print_flag;
00409              /*
00410               * If the cycle was never actually called (e.g. this
00411               * arc is static (and all others are, too)) no time
00412               * propagates along this arc.
00413               */
00414              if (head->ncalls != 0)
00415               {
00416                 head->cg.prop.fract += parent->cg.prop.fract
00417                   * (((double) arc->count) / ((double) head->ncalls));
00418               }
00419            }
00420        }
00421       for (member = head; member; member = member->cg.cyc.next)
00422        {
00423          member->cg.print_flag = head->cg.print_flag;
00424          member->cg.prop.fract = head->cg.prop.fract;
00425        }
00426     }
00427 }
00428 
00429 
00430 /*
00431  * In one top-to-bottom pass over the topologically sorted symbols
00432  * propagate:
00433  *      cg.print_flag as the union of parents' print_flags
00434  *      propfraction as the sum of fractional parents' propfractions
00435  * and while we're here, sum time for functions.
00436  */
00437 static void
00438 propagate_flags (Sym **symbols)
00439 {
00440   int index;
00441   Sym *old_head, *child;
00442 
00443   old_head = 0;
00444   for (index = symtab.len - 1; index >= 0; --index)
00445     {
00446       child = symbols[index];
00447       /*
00448        * If we haven't done this function or cycle, inherit things
00449        * from parent.  This way, we are linear in the number of arcs
00450        * since we do all members of a cycle (and the cycle itself)
00451        * as we hit the first member of the cycle.
00452        */
00453       if (child->cg.cyc.head != old_head)
00454        {
00455          old_head = child->cg.cyc.head;
00456          inherit_flags (child);
00457        }
00458       DBG (PROPDEBUG,
00459           printf ("[prop_flags] ");
00460           print_name (child);
00461           printf ("inherits print-flag %d and prop-fract %f\n",
00462                  child->cg.print_flag, child->cg.prop.fract));
00463       if (!child->cg.print_flag)
00464        {
00465          /*
00466           * Printflag is off. It gets turned on by being in the
00467           * INCL_GRAPH table, or there being an empty INCL_GRAPH
00468           * table and not being in the EXCL_GRAPH table.
00469           */
00470          if (sym_lookup (&syms[INCL_GRAPH], child->addr)
00471              || (syms[INCL_GRAPH].len == 0
00472                 && !sym_lookup (&syms[EXCL_GRAPH], child->addr)))
00473            {
00474              child->cg.print_flag = TRUE;
00475            }
00476        }
00477       else
00478        {
00479          /*
00480           * This function has printing parents: maybe someone wants
00481           * to shut it up by putting it in the EXCL_GRAPH table.
00482           * (But favor INCL_GRAPH over EXCL_GRAPH.)
00483           */
00484          if (!sym_lookup (&syms[INCL_GRAPH], child->addr)
00485              && sym_lookup (&syms[EXCL_GRAPH], child->addr))
00486            {
00487              child->cg.print_flag = FALSE;
00488            }
00489        }
00490       if (child->cg.prop.fract == 0.0)
00491        {
00492          /*
00493           * No parents to pass time to.  Collect time from children
00494           * if its in the INCL_TIME table, or there is an empty
00495           * INCL_TIME table and its not in the EXCL_TIME table.
00496           */
00497          if (sym_lookup (&syms[INCL_TIME], child->addr)
00498              || (syms[INCL_TIME].len == 0
00499                 && !sym_lookup (&syms[EXCL_TIME], child->addr)))
00500            {
00501              child->cg.prop.fract = 1.0;
00502            }
00503        }
00504       else
00505        {
00506          /*
00507           * It has parents to pass time to, but maybe someone wants
00508           * to shut it up by puttting it in the EXCL_TIME table.
00509           * (But favor being in INCL_TIME tabe over being in
00510           * EXCL_TIME table.)
00511           */
00512          if (!sym_lookup (&syms[INCL_TIME], child->addr)
00513              && sym_lookup (&syms[EXCL_TIME], child->addr))
00514            {
00515              child->cg.prop.fract = 0.0;
00516            }
00517        }
00518       child->cg.prop.self = child->hist.time * child->cg.prop.fract;
00519       print_time += child->cg.prop.self;
00520       DBG (PROPDEBUG,
00521           printf ("[prop_flags] ");
00522           print_name (child);
00523           printf (" ends up with printflag %d and prop-fract %f\n",
00524                  child->cg.print_flag, child->cg.prop.fract);
00525           printf ("[prop_flags] time %f propself %f print_time %f\n",
00526                  child->hist.time, child->cg.prop.self, print_time));
00527     }
00528 }
00529 
00530 
00531 /*
00532  * Compare by decreasing propagated time.  If times are equal, but one
00533  * is a cycle header, say that's first (e.g. less, i.e. -1).  If one's
00534  * name doesn't have an underscore and the other does, say that one is
00535  * first.  All else being equal, compare by names.
00536  */
00537 static int
00538 cmp_total (const PTR lp, const PTR rp)
00539 {
00540   const Sym *left = *(const Sym **) lp;
00541   const Sym *right = *(const Sym **) rp;
00542   double diff;
00543 
00544   diff = (left->cg.prop.self + left->cg.prop.child)
00545     - (right->cg.prop.self + right->cg.prop.child);
00546   if (diff < 0.0)
00547     {
00548       return 1;
00549     }
00550   if (diff > 0.0)
00551     {
00552       return -1;
00553     }
00554   if (!left->name && left->cg.cyc.num != 0)
00555     {
00556       return -1;
00557     }
00558   if (!right->name && right->cg.cyc.num != 0)
00559     {
00560       return 1;
00561     }
00562   if (!left->name)
00563     {
00564       return -1;
00565     }
00566   if (!right->name)
00567     {
00568       return 1;
00569     }
00570   if (left->name[0] != '_' && right->name[0] == '_')
00571     {
00572       return -1;
00573     }
00574   if (left->name[0] == '_' && right->name[0] != '_')
00575     {
00576       return 1;
00577     }
00578   if (left->ncalls > right->ncalls)
00579     {
00580       return -1;
00581     }
00582   if (left->ncalls < right->ncalls)
00583     {
00584       return 1;
00585     }
00586   return strcmp (left->name, right->name);
00587 }
00588 
00589 
00590 /*
00591  * Topologically sort the graph (collapsing cycles), and propagates
00592  * time bottom up and flags top down.
00593  */
00594 Sym **
00595 cg_assemble ()
00596 {
00597   Sym *parent, **time_sorted_syms, **top_sorted_syms;
00598   unsigned int index;
00599   Arc *arc;
00600 
00601   /*
00602    * initialize various things:
00603    *      zero out child times.
00604    *      count self-recursive calls.
00605    *      indicate that nothing is on cycles.
00606    */
00607   for (parent = symtab.base; parent < symtab.limit; parent++)
00608     {
00609       parent->cg.child_time = 0.0;
00610       arc = arc_lookup (parent, parent);
00611       if (arc && parent == arc->child)
00612        {
00613          parent->ncalls -= arc->count;
00614          parent->cg.self_calls = arc->count;
00615        }
00616       else
00617        {
00618          parent->cg.self_calls = 0;
00619        }
00620       parent->cg.prop.fract = 0.0;
00621       parent->cg.prop.self = 0.0;
00622       parent->cg.prop.child = 0.0;
00623       parent->cg.print_flag = FALSE;
00624       parent->cg.top_order = DFN_NAN;
00625       parent->cg.cyc.num = 0;
00626       parent->cg.cyc.head = parent;
00627       parent->cg.cyc.next = 0;
00628       if (ignore_direct_calls)
00629        {
00630          find_call (parent, parent->addr, (parent + 1)->addr);
00631        }
00632     }
00633   /*
00634    * Topologically order things.  If any node is unnumbered, number
00635    * it and any of its descendents.
00636    */
00637   for (parent = symtab.base; parent < symtab.limit; parent++)
00638     {
00639       if (parent->cg.top_order == DFN_NAN)
00640        {
00641          cg_dfn (parent);
00642        }
00643     }
00644 
00645   /* link together nodes on the same cycle: */
00646   cycle_link ();
00647 
00648   /* sort the symbol table in reverse topological order: */
00649   top_sorted_syms = (Sym **) xmalloc (symtab.len * sizeof (Sym *));
00650   for (index = 0; index < symtab.len; ++index)
00651     {
00652       top_sorted_syms[index] = &symtab.base[index];
00653     }
00654   qsort (top_sorted_syms, symtab.len, sizeof (Sym *), cmp_topo);
00655   DBG (DFNDEBUG,
00656        printf ("[cg_assemble] topological sort listing\n");
00657        for (index = 0; index < symtab.len; ++index)
00658        {
00659        printf ("[cg_assemble] ");
00660        printf ("%d:", top_sorted_syms[index]->cg.top_order);
00661        print_name (top_sorted_syms[index]);
00662        printf ("\n");
00663        }
00664   );
00665   /*
00666    * Starting from the topological top, propagate print flags to
00667    * children.  also, calculate propagation fractions.  this happens
00668    * before time propagation since time propagation uses the
00669    * fractions.
00670    */
00671   propagate_flags (top_sorted_syms);
00672 
00673   /*
00674    * Starting from the topological bottom, propogate children times
00675    * up to parents.
00676    */
00677   cycle_time ();
00678   for (index = 0; index < symtab.len; ++index)
00679     {
00680       propagate_time (top_sorted_syms[index]);
00681     }
00682 
00683   free (top_sorted_syms);
00684 
00685   /*
00686    * Now, sort by CG.PROP.SELF + CG.PROP.CHILD.  Sorting both the regular
00687    * function names and cycle headers.
00688    */
00689   time_sorted_syms = (Sym **) xmalloc ((symtab.len + num_cycles) * sizeof (Sym *));
00690   for (index = 0; index < symtab.len; index++)
00691     {
00692       time_sorted_syms[index] = &symtab.base[index];
00693     }
00694   for (index = 1; index <= num_cycles; index++)
00695     {
00696       time_sorted_syms[symtab.len + index - 1] = &cycle_header[index];
00697     }
00698   qsort (time_sorted_syms, symtab.len + num_cycles, sizeof (Sym *),
00699         cmp_total);
00700   for (index = 0; index < symtab.len + num_cycles; index++)
00701     {
00702       time_sorted_syms[index]->cg.index = index + 1;
00703     }
00704   return time_sorted_syms;
00705 }