Return to arcs.c CVS log

Up to [CSRG BSD Unix] / 43BSD / ucb / gprof

Annotation of 43BSD/ucb/gprof/arcs.c, revision 1.1

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

This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.