arcs.c

Functions

addarc            X
cyclelink         X
cycletime         X
doarcs            X
doflags           X
dotime            X
inheritflags      X
timepropagate     X
topcmp            X

Variables

topsortnlp        X

   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: }