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