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