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