1 #ifndef lint 2 static char *sccsid = "@(#)arcs.c 1.12 (Berkeley) 10/26/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 347 for ( cycle = 1 ; cycle <= ncycle ; cycle += 1 ) { 348 cyclenlp = &cyclenl[ cycle ]; 349 for ( childp = cyclenlp -> cnext ; childp ; childp = childp -> cnext ) { 350 if ( childp -> propfraction == 0.0 ) { 351 /* 352 * all members have the same propfraction except those 353 * that were excluded with -E 354 */ 355 continue; 356 } 357 cyclenlp -> time += childp -> time; 358 } 359 cyclenlp -> propself = cyclenlp -> propfraction * cyclenlp -> time; 360 } 361 } 362 363 /* 364 * in one top to bottom pass over the topologically sorted namelist 365 * propagate: 366 * printflag as the union of parents' printflags 367 * propfraction as the sum of fractional parents' propfractions 368 * and while we're here, sum time for functions. 369 */ 370 doflags() 371 { 372 int index; 373 nltype *childp; 374 nltype *oldhead; 375 376 oldhead = 0; 377 for ( index = nname-1 ; index >= 0 ; index -= 1 ) { 378 childp = topsortnlp[ index ]; 379 /* 380 * if we haven't done this function or cycle, 381 * inherit things from parent. 382 * this way, we are linear in the number of arcs 383 * since we do all members of a cycle (and the cycle itself) 384 * as we hit the first member of the cycle. 385 */ 386 if ( childp -> cyclehead != oldhead ) { 387 oldhead = childp -> cyclehead; 388 inheritflags( childp ); 389 } 390 # ifdef DEBUG 391 if ( debug & PROPDEBUG ) { 392 printf( "[doflags] " ); 393 printname( childp ); 394 printf( " inherits printflag %d and propfraction %f\n" , 395 childp -> printflag , childp -> propfraction ); 396 } 397 # endif DEBUG 398 if ( ! childp -> printflag ) { 399 /* 400 * printflag is off 401 * it gets turned on by 402 * being on -f list, 403 * or there not being any -f list and not being on -e list. 404 */ 405 if ( onlist( flist , childp -> name ) 406 || ( !fflag && !onlist( elist , childp -> name ) ) ) { 407 childp -> printflag = TRUE; 408 } 409 } else { 410 /* 411 * this function has printing parents: 412 * maybe someone wants to shut it up 413 * by putting it on -e list. (but favor -f over -e) 414 */ 415 if ( ( !onlist( flist , childp -> name ) ) 416 && onlist( elist , childp -> name ) ) { 417 childp -> printflag = FALSE; 418 } 419 } 420 if ( childp -> propfraction == 0.0 ) { 421 /* 422 * no parents to pass time to. 423 * collect time from children if 424 * its on -F list, 425 * or there isn't any -F list and its not on -E list. 426 */ 427 if ( onlist( Flist , childp -> name ) 428 || ( !Fflag && !onlist( Elist , childp -> name ) ) ) { 429 childp -> propfraction = 1.0; 430 } 431 } else { 432 /* 433 * it has parents to pass time to, 434 * but maybe someone wants to shut it up 435 * by puttting it on -E list. (but favor -F over -E) 436 */ 437 if ( !onlist( Flist , childp -> name ) 438 && onlist( Elist , childp -> name ) ) { 439 childp -> propfraction = 0.0; 440 } 441 } 442 childp -> propself = childp -> time * childp -> propfraction; 443 printtime += childp -> propself; 444 # ifdef DEBUG 445 if ( debug & PROPDEBUG ) { 446 printf( "[doflags] " ); 447 printname( childp ); 448 printf( " ends up with printflag %d and propfraction %f\n" , 449 childp -> printflag , childp -> propfraction ); 450 printf( "time %f propself %f printtime %f\n" , 451 childp -> time , childp -> propself , printtime ); 452 } 453 # endif DEBUG 454 } 455 } 456 457 /* 458 * check if any parent of this child 459 * (or outside parents of this cycle) 460 * have their print flags on and set the 461 * print flag of the child (cycle) appropriately. 462 * similarly, deal with propagation fractions from parents. 463 */ 464 inheritflags( childp ) 465 nltype *childp; 466 { 467 nltype *headp; 468 arctype *arcp; 469 nltype *parentp; 470 nltype *memp; 471 472 headp = childp -> cyclehead; 473 if ( childp == headp ) { 474 /* 475 * just a regular child, check its parents 476 */ 477 childp -> printflag = FALSE; 478 childp -> propfraction = 0.0; 479 for (arcp = childp -> parents ; arcp ; arcp = arcp -> arc_parentlist) { 480 parentp = arcp -> arc_parentp; 481 if ( childp == parentp ) { 482 continue; 483 } 484 childp -> printflag |= parentp -> printflag; 485 childp -> propfraction += parentp -> propfraction 486 * ( ( (double) arcp -> arc_count ) 487 / ( (double) childp -> ncall ) ); 488 } 489 } else { 490 /* 491 * its a member of a cycle, look at all parents from 492 * outside the cycle 493 */ 494 headp -> printflag = FALSE; 495 headp -> propfraction = 0.0; 496 for ( memp = headp -> cnext ; memp ; memp = memp -> cnext ) { 497 for (arcp = memp->parents ; arcp ; arcp = arcp->arc_parentlist) { 498 if ( arcp -> arc_parentp -> cyclehead == headp ) { 499 continue; 500 } 501 parentp = arcp -> arc_parentp; 502 headp -> printflag |= parentp -> printflag; 503 headp -> propfraction += parentp -> propfraction 504 * ( ( (double) arcp -> arc_count ) 505 / ( (double) headp -> ncall ) ); 506 } 507 } 508 for ( memp = headp ; memp ; memp = memp -> cnext ) { 509 memp -> printflag = headp -> printflag; 510 memp -> propfraction = headp -> propfraction; 511 } 512 } 513 } 514