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