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