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