home *** CD-ROM | disk | FTP | other *** search
/ InfoMagic Source Code 1993 July / THE_SOURCE_CODE_CD_ROM.iso / bsd_srcs / usr.bin / gprof / arcs.c next >
Encoding:
C/C++ Source or Header  |  1991-04-12  |  16.5 KB  |  582 lines
  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, 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. All advertising materials mentioning features or use of this software
  14.  *    must display the following acknowledgement:
  15.  *    This product includes software developed by the University of
  16.  *    California, Berkeley and its contributors.
  17.  * 4. Neither the name of the University nor the names of its contributors
  18.  *    may be used to endorse or promote products derived from this software
  19.  *    without specific prior written permission.
  20.  *
  21.  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  22.  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  23.  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  24.  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  25.  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  26.  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  27.  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  28.  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  29.  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  30.  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  31.  * SUCH DAMAGE.
  32.  */
  33.  
  34. #ifndef lint
  35. static char sccsid[] = "@(#)arcs.c    5.6 (Berkeley) 6/1/90";
  36. #endif /* not lint */
  37.  
  38. #include "gprof.h"
  39.  
  40.     /*
  41.      *    add (or just increment) an arc
  42.      */
  43. addarc( parentp , childp , count )
  44.     nltype    *parentp;
  45.     nltype    *childp;
  46.     long    count;
  47. {
  48.     arctype        *calloc();
  49.     arctype        *arcp;
  50.  
  51. #   ifdef DEBUG
  52.     if ( debug & TALLYDEBUG ) {
  53.         printf( "[addarc] %d arcs from %s to %s\n" ,
  54.             count , parentp -> name , childp -> name );
  55.     }
  56. #   endif DEBUG
  57.     arcp = arclookup( parentp , childp );
  58.     if ( arcp != 0 ) {
  59.         /*
  60.          *    a hit:  just increment the count.
  61.          */
  62. #    ifdef DEBUG
  63.         if ( debug & TALLYDEBUG ) {
  64.         printf( "[tally] hit %d += %d\n" ,
  65.             arcp -> arc_count , count );
  66.         }
  67. #    endif DEBUG
  68.     arcp -> arc_count += count;
  69.     return;
  70.     }
  71.     arcp = calloc( 1 , sizeof *arcp );
  72.     arcp -> arc_parentp = parentp;
  73.     arcp -> arc_childp = childp;
  74.     arcp -> arc_count = count;
  75.     /*
  76.      *    prepend this child to the children of this parent
  77.      */
  78.     arcp -> arc_childlist = parentp -> children;
  79.     parentp -> children = arcp;
  80.     /*
  81.      *    prepend this parent to the parents of this child
  82.      */
  83.     arcp -> arc_parentlist = childp -> parents;
  84.     childp -> parents = arcp;
  85. }
  86.  
  87.     /*
  88.      *    the code below topologically sorts the graph (collapsing cycles),
  89.      *    and propagates time bottom up and flags top down.
  90.      */
  91.  
  92.     /*
  93.      *    the topologically sorted name list pointers
  94.      */
  95. nltype    **topsortnlp;
  96.  
  97. topcmp( npp1 , npp2 )
  98.     nltype    **npp1;
  99.     nltype    **npp2;
  100. {
  101.     return (*npp1) -> toporder - (*npp2) -> toporder;
  102. }
  103.  
  104. nltype **
  105. doarcs()
  106. {
  107.     nltype    *parentp, **timesortnlp;
  108.     arctype    *arcp;
  109.     long    index;
  110.  
  111.     /*
  112.      *    initialize various things:
  113.      *        zero out child times.
  114.      *        count self-recursive calls.
  115.      *        indicate that nothing is on cycles.
  116.      */
  117.     for ( parentp = nl ; parentp < npe ; parentp++ ) {
  118.     parentp -> childtime = 0.0;
  119.     arcp = arclookup( parentp , parentp );
  120.     if ( arcp != 0 ) {
  121.         parentp -> ncall -= arcp -> arc_count;
  122.         parentp -> selfcalls = arcp -> arc_count;
  123.     } else {
  124.         parentp -> selfcalls = 0;
  125.     }
  126.     parentp -> propfraction = 0.0;
  127.     parentp -> propself = 0.0;
  128.     parentp -> propchild = 0.0;
  129.     parentp -> printflag = FALSE;
  130.     parentp -> toporder = DFN_NAN;
  131.     parentp -> cycleno = 0;
  132.     parentp -> cyclehead = parentp;
  133.     parentp -> cnext = 0;
  134.     if ( cflag ) {
  135.         findcall( parentp , parentp -> value , (parentp+1) -> value );
  136.     }
  137.     }
  138.     /*
  139.      *    topologically order things
  140.      *    if any node is unnumbered,
  141.      *        number it and any of its descendents.
  142.      */
  143.     for ( parentp = nl ; parentp < npe ; parentp++ ) {
  144.     if ( parentp -> toporder == DFN_NAN ) {
  145.         dfn( parentp );
  146.     }
  147.     }
  148.     /*
  149.      *    link together nodes on the same cycle
  150.      */
  151.     cyclelink();
  152.     /*
  153.      *    Sort the symbol table in reverse topological order
  154.      */
  155.     topsortnlp = (nltype **) calloc( nname , sizeof(nltype *) );
  156.     if ( topsortnlp == (nltype **) 0 ) {
  157.     fprintf( stderr , "[doarcs] ran out of memory for topo sorting\n" );
  158.     }
  159.     for ( index = 0 ; index < nname ; index += 1 ) {
  160.     topsortnlp[ index ] = &nl[ index ];
  161.     }
  162.     qsort( topsortnlp , nname , sizeof(nltype *) , topcmp );
  163. #   ifdef DEBUG
  164.     if ( debug & DFNDEBUG ) {
  165.         printf( "[doarcs] topological sort listing\n" );
  166.         for ( index = 0 ; index < nname ; index += 1 ) {
  167.         printf( "[doarcs] " );
  168.         printf( "%d:" , topsortnlp[ index ] -> toporder );
  169.         printname( topsortnlp[ index ] );
  170.         printf( "\n" );
  171.         }
  172.     }
  173. #   endif DEBUG
  174.     /*
  175.      *    starting from the topological top,
  176.      *    propagate print flags to children.
  177.      *    also, calculate propagation fractions.
  178.      *    this happens before time propagation
  179.      *    since time propagation uses the fractions.
  180.      */
  181.     doflags();
  182.     /*
  183.      *    starting from the topological bottom, 
  184.      *    propogate children times up to parents.
  185.      */
  186.     dotime();
  187.     /*
  188.      *    Now, sort by propself + propchild.
  189.      *    sorting both the regular function names
  190.      *    and cycle headers.
  191.      */
  192.     timesortnlp = (nltype **) calloc( nname + ncycle , sizeof(nltype *) );
  193.     if ( timesortnlp == (nltype **) 0 ) {
  194.     fprintf( stderr , "%s: ran out of memory for sorting\n" , whoami );
  195.     }
  196.     for ( index = 0 ; index < nname ; index++ ) {
  197.     timesortnlp[index] = &nl[index];
  198.     }
  199.     for ( index = 1 ; index <= ncycle ; index++ ) {
  200.     timesortnlp[nname+index-1] = &cyclenl[index];
  201.     }
  202.     qsort( timesortnlp , nname + ncycle , sizeof(nltype *) , totalcmp );
  203.     for ( index = 0 ; index < nname + ncycle ; index++ ) {
  204.     timesortnlp[ index ] -> index = index + 1;
  205.     }
  206.     return( timesortnlp );
  207. }
  208.  
  209. dotime()
  210. {
  211.     int    index;
  212.  
  213.     cycletime();
  214.     for ( index = 0 ; index < nname ; index += 1 ) {
  215.     timepropagate( topsortnlp[ index ] );
  216.     }
  217. }
  218.  
  219. timepropagate( parentp )
  220.     nltype    *parentp;
  221. {
  222.     arctype    *arcp;
  223.     nltype    *childp;
  224.     double    share;
  225.     double    propshare;
  226.  
  227.     if ( parentp -> propfraction == 0.0 ) {
  228.     return;
  229.     }
  230.     /*
  231.      *    gather time from children of this parent.
  232.      */
  233.     for ( arcp = parentp -> children ; arcp ; arcp = arcp -> arc_childlist ) {
  234.     childp = arcp -> arc_childp;
  235.     if ( arcp -> arc_count == 0 ) {
  236.         continue;
  237.     }
  238.     if ( childp == parentp ) {
  239.         continue;
  240.     }
  241.     if ( childp -> propfraction == 0.0 ) {
  242.         continue;
  243.     }
  244.     if ( childp -> cyclehead != childp ) {
  245.         if ( parentp -> cycleno == childp -> cycleno ) {
  246.         continue;
  247.         }
  248.         if ( parentp -> toporder <= childp -> toporder ) {
  249.         fprintf( stderr , "[propagate] toporder botches\n" );
  250.         }
  251.         childp = childp -> cyclehead;
  252.     } else {
  253.         if ( parentp -> toporder <= childp -> toporder ) {
  254.         fprintf( stderr , "[propagate] toporder botches\n" );
  255.         continue;
  256.         }
  257.     }
  258.     if ( childp -> ncall == 0 ) {
  259.         continue;
  260.     }
  261.         /*
  262.          *    distribute time for this arc
  263.          */
  264.     arcp -> arc_time = childp -> time
  265.                     * ( ( (double) arcp -> arc_count ) /
  266.                     ( (double) childp -> ncall ) );
  267.     arcp -> arc_childtime = childp -> childtime
  268.                     * ( ( (double) arcp -> arc_count ) /
  269.                     ( (double) childp -> ncall ) );
  270.     share = arcp -> arc_time + arcp -> arc_childtime;
  271.     parentp -> childtime += share;
  272.         /*
  273.          *    ( 1 - propfraction ) gets lost along the way
  274.          */
  275.     propshare = parentp -> propfraction * share;
  276.         /*
  277.          *    fix things for printing
  278.          */
  279.     parentp -> propchild += propshare;
  280.     arcp -> arc_time *= parentp -> propfraction;
  281.     arcp -> arc_childtime *= parentp -> propfraction;
  282.         /*
  283.          *    add this share to the parent's cycle header, if any.
  284.          */
  285.     if ( parentp -> cyclehead != parentp ) {
  286.         parentp -> cyclehead -> childtime += share;
  287.         parentp -> cyclehead -> propchild += propshare;
  288.     }
  289. #    ifdef DEBUG
  290.         if ( debug & PROPDEBUG ) {
  291.         printf( "[dotime] child \t" );
  292.         printname( childp );
  293.         printf( " with %f %f %d/%d\n" ,
  294.             childp -> time , childp -> childtime ,
  295.             arcp -> arc_count , childp -> ncall );
  296.         printf( "[dotime] parent\t" );
  297.         printname( parentp );
  298.         printf( "\n[dotime] share %f\n" , share );
  299.         }
  300. #    endif DEBUG
  301.     }
  302. }
  303.  
  304. cyclelink()
  305. {
  306.     register nltype    *nlp;
  307.     register nltype    *cyclenlp;
  308.     int            cycle;
  309.     nltype        *memberp;
  310.     arctype        *arcp;
  311.  
  312.     /*
  313.      *    Count the number of cycles, and initialze the cycle lists
  314.      */
  315.     ncycle = 0;
  316.     for ( nlp = nl ; nlp < npe ; nlp++ ) {
  317.         /*
  318.          *    this is how you find unattached cycles
  319.          */
  320.     if ( nlp -> cyclehead == nlp && nlp -> cnext != 0 ) {
  321.         ncycle += 1;
  322.     }
  323.     }
  324.     /*
  325.      *    cyclenl is indexed by cycle number:
  326.      *    i.e. it is origin 1, not origin 0.
  327.      */
  328.     cyclenl = (nltype *) calloc( ncycle + 1 , sizeof( nltype ) );
  329.     if ( cyclenl == 0 ) {
  330.     fprintf( stderr , "%s: No room for %d bytes of cycle headers\n" ,
  331.         whoami , ( ncycle + 1 ) * sizeof( nltype ) );
  332.     done();
  333.     }
  334.     /*
  335.      *    now link cycles to true cycleheads,
  336.      *    number them, accumulate the data for the cycle
  337.      */
  338.     cycle = 0;
  339.     for ( nlp = nl ; nlp < npe ; nlp++ ) {
  340.     if ( !( nlp -> cyclehead == nlp && nlp -> cnext != 0 ) ) {
  341.         continue;
  342.     }
  343.     cycle += 1;
  344.     cyclenlp = &cyclenl[cycle];
  345.         cyclenlp -> name = 0;        /* the name */
  346.         cyclenlp -> value = 0;        /* the pc entry point */
  347.         cyclenlp -> time = 0.0;        /* ticks in this routine */
  348.         cyclenlp -> childtime = 0.0;    /* cumulative ticks in children */
  349.     cyclenlp -> ncall = 0;        /* how many times called */
  350.     cyclenlp -> selfcalls = 0;    /* how many calls to self */
  351.     cyclenlp -> propfraction = 0.0;    /* what % of time propagates */
  352.     cyclenlp -> propself = 0.0;    /* how much self time propagates */
  353.     cyclenlp -> propchild = 0.0;    /* how much child time propagates */
  354.     cyclenlp -> printflag = TRUE;    /* should this be printed? */
  355.     cyclenlp -> index = 0;        /* index in the graph list */
  356.     cyclenlp -> toporder = DFN_NAN;    /* graph call chain top-sort order */
  357.     cyclenlp -> cycleno = cycle;    /* internal number of cycle on */
  358.     cyclenlp -> cyclehead = cyclenlp;    /* pointer to head of cycle */
  359.     cyclenlp -> cnext = nlp;    /* pointer to next member of cycle */
  360.     cyclenlp -> parents = 0;    /* list of caller arcs */
  361.     cyclenlp -> children = 0;    /* list of callee arcs */
  362. #    ifdef DEBUG
  363.         if ( debug & CYCLEDEBUG ) {
  364.         printf( "[cyclelink] " );
  365.         printname( nlp );
  366.         printf( " is the head of cycle %d\n" , cycle );
  367.         }
  368. #    endif DEBUG
  369.         /*
  370.          *    link members to cycle header
  371.          */
  372.     for ( memberp = nlp ; memberp ; memberp = memberp -> cnext ) { 
  373.         memberp -> cycleno = cycle;
  374.         memberp -> cyclehead = cyclenlp;
  375.     }
  376.         /*
  377.          *    count calls from outside the cycle
  378.          *    and those among cycle members
  379.          */
  380.     for ( memberp = nlp ; memberp ; memberp = memberp -> cnext ) {
  381.         for ( arcp=memberp->parents ; arcp ; arcp=arcp->arc_parentlist ) {
  382.         if ( arcp -> arc_parentp == memberp ) {
  383.             continue;
  384.         }
  385.         if ( arcp -> arc_parentp -> cycleno == cycle ) {
  386.             cyclenlp -> selfcalls += arcp -> arc_count;
  387.         } else {
  388.             cyclenlp -> ncall += arcp -> arc_count;
  389.         }
  390.         }
  391.     }
  392.     }
  393. }
  394.  
  395. cycletime()
  396. {
  397.     int            cycle;
  398.     nltype        *cyclenlp;
  399.     nltype        *childp;
  400.  
  401.     for ( cycle = 1 ; cycle <= ncycle ; cycle += 1 ) {
  402.     cyclenlp = &cyclenl[ cycle ];
  403.     for ( childp = cyclenlp -> cnext ; childp ; childp = childp -> cnext ) {
  404.         if ( childp -> propfraction == 0.0 ) {
  405.             /*
  406.              * all members have the same propfraction except those
  407.              *    that were excluded with -E
  408.              */
  409.         continue;
  410.         }
  411.         cyclenlp -> time += childp -> time;
  412.     }
  413.     cyclenlp -> propself = cyclenlp -> propfraction * cyclenlp -> time;
  414.     }
  415. }
  416.  
  417.     /*
  418.      *    in one top to bottom pass over the topologically sorted namelist
  419.      *    propagate:
  420.      *        printflag as the union of parents' printflags
  421.      *        propfraction as the sum of fractional parents' propfractions
  422.      *    and while we're here, sum time for functions.
  423.      */
  424. doflags()
  425. {
  426.     int        index;
  427.     nltype    *childp;
  428.     nltype    *oldhead;
  429.  
  430.     oldhead = 0;
  431.     for ( index = nname-1 ; index >= 0 ; index -= 1 ) {
  432.     childp = topsortnlp[ index ];
  433.         /*
  434.          *    if we haven't done this function or cycle,
  435.          *    inherit things from parent.
  436.          *    this way, we are linear in the number of arcs
  437.          *    since we do all members of a cycle (and the cycle itself)
  438.          *    as we hit the first member of the cycle.
  439.          */
  440.     if ( childp -> cyclehead != oldhead ) {
  441.         oldhead = childp -> cyclehead;
  442.         inheritflags( childp );
  443.     }
  444. #    ifdef DEBUG
  445.         if ( debug & PROPDEBUG ) {
  446.         printf( "[doflags] " );
  447.         printname( childp );
  448.         printf( " inherits printflag %d and propfraction %f\n" ,
  449.             childp -> printflag , childp -> propfraction );
  450.         }
  451. #    endif DEBUG
  452.     if ( ! childp -> printflag ) {
  453.         /*
  454.          *    printflag is off
  455.          *    it gets turned on by
  456.          *    being on -f list,
  457.          *    or there not being any -f list and not being on -e list.
  458.          */
  459.         if (   onlist( flist , childp -> name )
  460.         || ( !fflag && !onlist( elist , childp -> name ) ) ) {
  461.         childp -> printflag = TRUE;
  462.         }
  463.     } else {
  464.         /*
  465.          *    this function has printing parents:
  466.          *    maybe someone wants to shut it up
  467.          *    by putting it on -e list.  (but favor -f over -e)
  468.          */
  469.         if (  ( !onlist( flist , childp -> name ) )
  470.         && onlist( elist , childp -> name ) ) {
  471.         childp -> printflag = FALSE;
  472.         }
  473.     }
  474.     if ( childp -> propfraction == 0.0 ) {
  475.         /*
  476.          *    no parents to pass time to.
  477.          *    collect time from children if
  478.          *    its on -F list,
  479.          *    or there isn't any -F list and its not on -E list.
  480.          */
  481.         if ( onlist( Flist , childp -> name )
  482.         || ( !Fflag && !onlist( Elist , childp -> name ) ) ) {
  483.             childp -> propfraction = 1.0;
  484.         }
  485.     } else {
  486.         /*
  487.          *    it has parents to pass time to, 
  488.          *    but maybe someone wants to shut it up
  489.          *    by puttting it on -E list.  (but favor -F over -E)
  490.          */
  491.         if (  !onlist( Flist , childp -> name )
  492.         && onlist( Elist , childp -> name ) ) {
  493.         childp -> propfraction = 0.0;
  494.         }
  495.     }
  496.     childp -> propself = childp -> time * childp -> propfraction;
  497.     printtime += childp -> propself;
  498. #    ifdef DEBUG
  499.         if ( debug & PROPDEBUG ) {
  500.         printf( "[doflags] " );
  501.         printname( childp );
  502.         printf( " ends up with printflag %d and propfraction %f\n" ,
  503.             childp -> printflag , childp -> propfraction );
  504.         printf( "time %f propself %f printtime %f\n" ,
  505.             childp -> time , childp -> propself , printtime );
  506.         }
  507. #    endif DEBUG
  508.     }
  509. }
  510.  
  511.     /*
  512.      *    check if any parent of this child
  513.      *    (or outside parents of this cycle)
  514.      *    have their print flags on and set the 
  515.      *    print flag of the child (cycle) appropriately.
  516.      *    similarly, deal with propagation fractions from parents.
  517.      */
  518. inheritflags( childp )
  519.     nltype    *childp;
  520. {
  521.     nltype    *headp;
  522.     arctype    *arcp;
  523.     nltype    *parentp;
  524.     nltype    *memp;
  525.  
  526.     headp = childp -> cyclehead;
  527.     if ( childp == headp ) {
  528.         /*
  529.          *    just a regular child, check its parents
  530.          */
  531.     childp -> printflag = FALSE;
  532.     childp -> propfraction = 0.0;
  533.     for (arcp = childp -> parents ; arcp ; arcp = arcp -> arc_parentlist) {
  534.         parentp = arcp -> arc_parentp;
  535.         if ( childp == parentp ) {
  536.         continue;
  537.         }
  538.         childp -> printflag |= parentp -> printflag;
  539.         /*
  540.          *    if the child was never actually called
  541.          *    (e.g. this arc is static (and all others are, too))
  542.          *    no time propagates along this arc.
  543.          */
  544.         if ( childp -> ncall ) {
  545.         childp -> propfraction += parentp -> propfraction
  546.                         * ( ( (double) arcp -> arc_count )
  547.                           / ( (double) childp -> ncall ) );
  548.         }
  549.     }
  550.     } else {
  551.         /*
  552.          *    its a member of a cycle, look at all parents from 
  553.          *    outside the cycle
  554.          */
  555.     headp -> printflag = FALSE;
  556.     headp -> propfraction = 0.0;
  557.     for ( memp = headp -> cnext ; memp ; memp = memp -> cnext ) {
  558.         for (arcp = memp->parents ; arcp ; arcp = arcp->arc_parentlist) {
  559.         if ( arcp -> arc_parentp -> cyclehead == headp ) {
  560.             continue;
  561.         }
  562.         parentp = arcp -> arc_parentp;
  563.         headp -> printflag |= parentp -> printflag;
  564.             /*
  565.              *    if the cycle was never actually called
  566.              *    (e.g. this arc is static (and all others are, too))
  567.              *    no time propagates along this arc.
  568.              */
  569.         if ( headp -> ncall ) {
  570.             headp -> propfraction += parentp -> propfraction
  571.                         * ( ( (double) arcp -> arc_count )
  572.                           / ( (double) headp -> ncall ) );
  573.         }
  574.         }
  575.     }
  576.     for ( memp = headp ; memp ; memp = memp -> cnext ) {
  577.         memp -> printflag = headp -> printflag;
  578.         memp -> propfraction = headp -> propfraction;
  579.     }
  580.     }
  581. }
  582.