1 #ifndef lint 2 static char *sccsid = "@(#)arcs.c 1.8 (Berkeley) 06/18/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 257 /* 258 * Count the number of cycles, and initialze the cycle lists 259 */ 260 ncycle = 0; 261 for ( nlp = nl ; nlp < npe ; nlp++ ) { 262 /* 263 * this is how you find unattached cycles 264 */ 265 if ( nlp -> cyclehead == nlp && nlp -> cnext != 0 ) { 266 ncycle += 1; 267 } 268 } 269 /* 270 * cyclenl is indexed by cycle number: 271 * i.e. it is origin 1, not origin 0. 272 */ 273 cyclenl = (nltype *) calloc( ncycle + 1 , sizeof( nltype ) ); 274 if ( cyclenl == 0 ) { 275 fprintf( stderr , "%s: No room for %d bytes of cycle headers\n" , 276 whoami , ( ncycle + 1 ) * sizeof( nltype ) ); 277 done(); 278 } 279 /* 280 * now link cycles to true cycleheads, 281 * number them, accumulate the data for the cycle 282 */ 283 cycle = 0; 284 for ( nlp = nl ; nlp < npe ; nlp++ ) { 285 if ( nlp -> cyclehead != nlp || nlp -> cnext == 0 ) { 286 continue; 287 } 288 cycle += 1; 289 cyclenlp = &cyclenl[cycle]; 290 cyclenlp -> name = ""; /* the name */ 291 cyclenlp -> value = 0; /* the pc entry point */ 292 cyclenlp -> time = 0.0; /* ticks in this routine */ 293 cyclenlp -> childtime = 0.0; /* cumulative ticks in children */ 294 cyclenlp -> ncall = 0; /* how many times called */ 295 cyclenlp -> selfcalls = 0; /* how many calls to self */ 296 cyclenlp -> propfraction = 0.0; /* what % of time propagates */ 297 cyclenlp -> propself = 0.0; /* how much self time propagates */ 298 cyclenlp -> propchild = 0.0; /* how much child time propagates */ 299 cyclenlp -> printflag = TRUE; /* should this be printed? */ 300 cyclenlp -> index = 0; /* index in the graph list */ 301 cyclenlp -> toporder = 0; /* graph call chain top-sort order */ 302 cyclenlp -> cycleno = cycle; /* internal number of cycle on */ 303 cyclenlp -> cyclehead = cyclenlp; /* pointer to head of cycle */ 304 cyclenlp -> cnext = nlp; /* pointer to next member of cycle */ 305 cyclenlp -> parents = 0; /* list of caller arcs */ 306 cyclenlp -> children = 0; /* list of callee arcs */ 307 # ifdef DEBUG 308 if ( debug & CYCLEDEBUG ) { 309 printf( "[cyclelink] " ); 310 printname( nlp ); 311 printf( " is the head of cycle %d\n" , cycle ); 312 } 313 # endif DEBUG 314 for ( memberp = nlp ; memberp ; memberp = memberp -> cnext ) { 315 memberp -> cycleno = cycle; 316 memberp -> cyclehead = cyclenlp; 317 } 318 } 319 } 320 321 cycletime() 322 { 323 int cycle; 324 nltype *cyclenlp; 325 nltype *childp; 326 arctype *arcp; 327 nltype *parentp; 328 329 for ( cycle = 1 ; cycle <= ncycle ; cycle += 1 ) { 330 cyclenlp = &cyclenl[ cycle ]; 331 for ( childp = cyclenlp -> cnext ; childp ; childp = childp -> cnext ) { 332 if ( childp -> propfraction == 0.0 ) { 333 /* 334 * all members have the same propfraction except those 335 * that were excluded with -E 336 */ 337 continue; 338 } 339 cyclenlp -> time += childp -> time; 340 for ( arcp=childp->parents ; arcp ; arcp=arcp->arc_parentlist ) { 341 parentp = arcp -> arc_parentp; 342 if ( parentp == childp ) { 343 continue; 344 } 345 if ( parentp -> cyclehead == cyclenlp ) { 346 cyclenlp -> selfcalls += arcp -> arc_count; 347 } else { 348 cyclenlp -> ncall += arcp -> arc_count; 349 } 350 } 351 } 352 cyclenlp -> propself = cyclenlp -> propfraction * cyclenlp -> time; 353 } 354 } 355 356 /* 357 * in one top to bottom pass over the topologically sorted namelist 358 * propagate: 359 * printflag as the union of parents' printflags 360 * propfraction as the sum of fractional parents' propfractions 361 * and while we're here, sum time for functions. 362 */ 363 doflags() 364 { 365 int index; 366 nltype *childp; 367 nltype *oldhead; 368 369 oldhead = 0; 370 for ( index = nname-1 ; index >= 0 ; index -= 1 ) { 371 childp = topsortnlp[ index ]; 372 /* 373 * if we haven't done this function or cycle, 374 * inherit things from parent. 375 * this way, we are linear in the number of arcs 376 * since we do all members of a cycle (and the cycle itself) 377 * as we hit the first member of the cycle. 378 */ 379 if ( childp -> cyclehead != oldhead ) { 380 oldhead = childp -> cyclehead; 381 inheritflags( childp ); 382 } 383 # ifdef DEBUG 384 if ( debug & PROPDEBUG ) { 385 printf( "[doflags] " ); 386 printname( childp ); 387 printf( " inherits printflag %d and propfraction %f\n" , 388 childp -> printflag , childp -> propfraction ); 389 } 390 # endif DEBUG 391 if ( ! childp -> printflag ) { 392 /* 393 * printflag is off 394 * it gets turned on by 395 * being on -f list, 396 * or there not being any -f list and not being on -e list. 397 */ 398 if ( onlist( flist , childp -> name ) 399 || ( !fflag && !onlist( elist , childp -> name ) ) ) { 400 childp -> printflag = TRUE; 401 } 402 } else { 403 /* 404 * this function has printing parents: 405 * maybe someone wants to shut it up 406 * by putting it on -e list. (but favor -f over -e) 407 */ 408 if ( ( !onlist( flist , childp -> name ) ) 409 && onlist( elist , childp -> name ) ) { 410 childp -> printflag = FALSE; 411 } 412 } 413 if ( childp -> propfraction == 0.0 ) { 414 /* 415 * no parents to pass time to. 416 * collect time from children if 417 * its on -F list, 418 * or there isn't any -F list and its not on -E list. 419 */ 420 if ( onlist( Flist , childp -> name ) 421 || ( !Fflag && !onlist( Elist , childp -> name ) ) ) { 422 childp -> propfraction = 1.0; 423 } 424 } else { 425 /* 426 * it has parents to pass time to, 427 * but maybe someone wants to shut it up 428 * by puttting it on -E list. (but favor -F over -E) 429 */ 430 if ( !onlist( Flist , childp -> name ) 431 && onlist( Elist , childp -> name ) ) { 432 childp -> propfraction = 0.0; 433 } 434 } 435 childp -> propself = childp -> time * childp -> propfraction; 436 printtime += childp -> propself; 437 # ifdef DEBUG 438 if ( debug & PROPDEBUG ) { 439 printf( "[doflags] " ); 440 printname( childp ); 441 printf( " ends up with printflag %d and propfraction %f\n" , 442 childp -> printflag , childp -> propfraction ); 443 printf( "time %f propself %f\n" , 444 childp -> time , childp -> propself ); 445 } 446 # endif DEBUG 447 } 448 } 449 450 /* 451 * check if any parent of this child 452 * (or outside parents of this cycle) 453 * have their print flags on and set the 454 * print flag of the child (cycle) appropriately. 455 * similarly, deal with propagation fractions from parents. 456 */ 457 inheritflags( childp ) 458 nltype *childp; 459 { 460 nltype *headp; 461 arctype *arcp; 462 nltype *parentp; 463 nltype *memp; 464 465 headp = childp -> cyclehead; 466 if ( childp == headp ) { 467 /* 468 * just a regular child, check its parents 469 */ 470 childp -> printflag = FALSE; 471 childp -> propfraction = 0.0; 472 for (arcp = childp -> parents ; arcp ; arcp = arcp -> arc_parentlist) { 473 parentp = arcp -> arc_parentp; 474 childp -> printflag |= parentp -> printflag; 475 childp -> propfraction += parentp -> propfraction 476 * ( ( (double) arcp -> arc_count ) 477 / ( (double) childp -> ncall) ); 478 } 479 } else { 480 /* 481 * its a member of a cycle, look at all parents from 482 * outside the cycle 483 */ 484 headp -> printflag = FALSE; 485 headp -> propfraction = 0.0; 486 for ( memp = headp -> cnext ; memp ; memp = memp -> cnext ) { 487 for (arcp = memp->parents ; arcp ; arcp = arcp->arc_parentlist) { 488 if ( arcp -> arc_parentp -> cyclehead == headp ) { 489 continue; 490 } 491 parentp = arcp -> arc_parentp; 492 headp -> printflag |= parentp -> printflag; 493 headp -> propfraction += parentp -> propfraction * 494 (arcp -> arc_count / headp -> ncall); 495 } 496 } 497 for ( memp = headp ; memp ; memp = memp -> cnext ) { 498 memp -> printflag = headp -> printflag; 499 memp -> propfraction = headp -> propfraction; 500 } 501 } 502 } 503