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