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