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