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