Return to arcs.c CVS log

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

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

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

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