1 /* 2 * Copyright (c) 1983, 1993 3 * The Regents of the University of California. All rights reserved. 4 * 5 * Redistribution and use in source and binary forms, with or without 6 * modification, are permitted provided that the following conditions 7 * are met: 8 * 1. Redistributions of source code must retain the above copyright 9 * notice, this list of conditions and the following disclaimer. 10 * 2. Redistributions in binary form must reproduce the above copyright 11 * notice, this list of conditions and the following disclaimer in the 12 * documentation and/or other materials provided with the distribution. 13 * 3. All advertising materials mentioning features or use of this software 14 * must display the following acknowledgement: 15 * This product includes software developed by the University of 16 * California, Berkeley and its contributors. 17 * 4. Neither the name of the University nor the names of its contributors 18 * may be used to endorse or promote products derived from this software 19 * without specific prior written permission. 20 * 21 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 22 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 23 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 24 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 25 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 26 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 27 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 28 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 29 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 30 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 31 * SUCH DAMAGE. 32 */ 33 34 #ifndef lint 35 static char sccsid[] = "@(#)arcs.c 8.1 (Berkeley) 6/6/93"; 36 #endif /* not lint */ 37 38 #include "gprof.h" 39 40 #ifdef DEBUG 41 int visited; 42 int viable; 43 int newcycle; 44 int oldcycle; 45 #endif DEBUG 46 47 /* 48 * add (or just increment) an arc 49 */ 50 addarc( parentp , childp , count ) 51 nltype *parentp; 52 nltype *childp; 53 long count; 54 { 55 arctype *arcp; 56 57 # ifdef DEBUG 58 if ( debug & TALLYDEBUG ) { 59 printf( "[addarc] %d arcs from %s to %s\n" , 60 count , parentp -> name , childp -> name ); 61 } 62 # endif DEBUG 63 arcp = arclookup( parentp , childp ); 64 if ( arcp != 0 ) { 65 /* 66 * a hit: just increment the count. 67 */ 68 # ifdef DEBUG 69 if ( debug & TALLYDEBUG ) { 70 printf( "[tally] hit %d += %d\n" , 71 arcp -> arc_count , count ); 72 } 73 # endif DEBUG 74 arcp -> arc_count += count; 75 return; 76 } 77 arcp = (arctype *)calloc( 1 , sizeof *arcp ); 78 arcp -> arc_parentp = parentp; 79 arcp -> arc_childp = childp; 80 arcp -> arc_count = count; 81 /* 82 * prepend this child to the children of this parent 83 */ 84 arcp -> arc_childlist = parentp -> children; 85 parentp -> children = arcp; 86 /* 87 * prepend this parent to the parents of this child 88 */ 89 arcp -> arc_parentlist = childp -> parents; 90 childp -> parents = arcp; 91 } 92 93 /* 94 * the code below topologically sorts the graph (collapsing cycles), 95 * and propagates time bottom up and flags top down. 96 */ 97 98 /* 99 * the topologically sorted name list pointers 100 */ 101 nltype **topsortnlp; 102 103 topcmp( npp1 , npp2 ) 104 nltype **npp1; 105 nltype **npp2; 106 { 107 return (*npp1) -> toporder - (*npp2) -> toporder; 108 } 109 110 nltype ** 111 doarcs() 112 { 113 nltype *parentp, **timesortnlp; 114 arctype *arcp; 115 long index; 116 long pass; 117 118 /* 119 * initialize various things: 120 * zero out child times. 121 * count self-recursive calls. 122 * indicate that nothing is on cycles. 123 */ 124 for ( parentp = nl ; parentp < npe ; parentp++ ) { 125 parentp -> childtime = 0.0; 126 arcp = arclookup( parentp , parentp ); 127 if ( arcp != 0 ) { 128 parentp -> ncall -= arcp -> arc_count; 129 parentp -> selfcalls = arcp -> arc_count; 130 } else { 131 parentp -> selfcalls = 0; 132 } 133 parentp -> npropcall = parentp -> ncall; 134 parentp -> propfraction = 0.0; 135 parentp -> propself = 0.0; 136 parentp -> propchild = 0.0; 137 parentp -> printflag = FALSE; 138 parentp -> toporder = DFN_NAN; 139 parentp -> cycleno = 0; 140 parentp -> cyclehead = parentp; 141 parentp -> cnext = 0; 142 if ( cflag ) { 143 findcall( parentp , parentp -> value , (parentp+1) -> value ); 144 } 145 } 146 for ( pass = 1 ; ; pass++ ) { 147 /* 148 * topologically order things 149 * if any node is unnumbered, 150 * number it and any of its descendents. 151 */ 152 for ( dfn_init() , parentp = nl ; parentp < npe ; parentp++ ) { 153 if ( parentp -> toporder == DFN_NAN ) { 154 dfn( parentp ); 155 } 156 } 157 /* 158 * link together nodes on the same cycle 159 */ 160 cyclelink(); 161 /* 162 * if no cycles to break up, proceed 163 */ 164 if ( ! Cflag ) 165 break; 166 /* 167 * analyze cycles to determine breakup 168 */ 169 # ifdef DEBUG 170 if ( debug & BREAKCYCLE ) { 171 printf("[doarcs] pass %d, cycle(s) %d\n" , pass , ncycle ); 172 } 173 # endif DEBUG 174 if ( pass == 1 ) { 175 printf( "\n\n%s %s\n%s %d:\n" , 176 "The following arcs were deleted" , 177 "from the propagation calculation" , 178 "to reduce the maximum cycle size to", cyclethreshold ); 179 } 180 if ( cycleanalyze() ) 181 break; 182 free ( cyclenl ); 183 ncycle = 0; 184 for ( parentp = nl ; parentp < npe ; parentp++ ) { 185 parentp -> toporder = DFN_NAN; 186 parentp -> cycleno = 0; 187 parentp -> cyclehead = parentp; 188 parentp -> cnext = 0; 189 } 190 } 191 if ( pass > 1 ) { 192 printf( "\f\n" ); 193 } else { 194 printf( "\tNone\n\n" ); 195 } 196 /* 197 * Sort the symbol table in reverse topological order 198 */ 199 topsortnlp = (nltype **) calloc( nname , sizeof(nltype *) ); 200 if ( topsortnlp == (nltype **) 0 ) { 201 fprintf( stderr , "[doarcs] ran out of memory for topo sorting\n" ); 202 } 203 for ( index = 0 ; index < nname ; index += 1 ) { 204 topsortnlp[ index ] = &nl[ index ]; 205 } 206 qsort( topsortnlp , nname , sizeof(nltype *) , topcmp ); 207 # ifdef DEBUG 208 if ( debug & DFNDEBUG ) { 209 printf( "[doarcs] topological sort listing\n" ); 210 for ( index = 0 ; index < nname ; index += 1 ) { 211 printf( "[doarcs] " ); 212 printf( "%d:" , topsortnlp[ index ] -> toporder ); 213 printname( topsortnlp[ index ] ); 214 printf( "\n" ); 215 } 216 } 217 # endif DEBUG 218 /* 219 * starting from the topological top, 220 * propagate print flags to children. 221 * also, calculate propagation fractions. 222 * this happens before time propagation 223 * since time propagation uses the fractions. 224 */ 225 doflags(); 226 /* 227 * starting from the topological bottom, 228 * propogate children times up to parents. 229 */ 230 dotime(); 231 /* 232 * Now, sort by propself + propchild. 233 * sorting both the regular function names 234 * and cycle headers. 235 */ 236 timesortnlp = (nltype **) calloc( nname + ncycle , sizeof(nltype *) ); 237 if ( timesortnlp == (nltype **) 0 ) { 238 fprintf( stderr , "%s: ran out of memory for sorting\n" , whoami ); 239 } 240 for ( index = 0 ; index < nname ; index++ ) { 241 timesortnlp[index] = &nl[index]; 242 } 243 for ( index = 1 ; index <= ncycle ; index++ ) { 244 timesortnlp[nname+index-1] = &cyclenl[index]; 245 } 246 qsort( timesortnlp , nname + ncycle , sizeof(nltype *) , totalcmp ); 247 for ( index = 0 ; index < nname + ncycle ; index++ ) { 248 timesortnlp[ index ] -> index = index + 1; 249 } 250 return( timesortnlp ); 251 } 252 253 dotime() 254 { 255 int index; 256 257 cycletime(); 258 for ( index = 0 ; index < nname ; index += 1 ) { 259 timepropagate( topsortnlp[ index ] ); 260 } 261 } 262 263 timepropagate( parentp ) 264 nltype *parentp; 265 { 266 arctype *arcp; 267 nltype *childp; 268 double share; 269 double propshare; 270 271 if ( parentp -> propfraction == 0.0 ) { 272 return; 273 } 274 /* 275 * gather time from children of this parent. 276 */ 277 for ( arcp = parentp -> children ; arcp ; arcp = arcp -> arc_childlist ) { 278 childp = arcp -> arc_childp; 279 if ( arcp -> arc_flags & DEADARC ) { 280 continue; 281 } 282 if ( arcp -> arc_count == 0 ) { 283 continue; 284 } 285 if ( childp == parentp ) { 286 continue; 287 } 288 if ( childp -> propfraction == 0.0 ) { 289 continue; 290 } 291 if ( childp -> cyclehead != childp ) { 292 if ( parentp -> cycleno == childp -> cycleno ) { 293 continue; 294 } 295 if ( parentp -> toporder <= childp -> toporder ) { 296 fprintf( stderr , "[propagate] toporder botches\n" ); 297 } 298 childp = childp -> cyclehead; 299 } else { 300 if ( parentp -> toporder <= childp -> toporder ) { 301 fprintf( stderr , "[propagate] toporder botches\n" ); 302 continue; 303 } 304 } 305 if ( childp -> npropcall == 0 ) { 306 continue; 307 } 308 /* 309 * distribute time for this arc 310 */ 311 arcp -> arc_time = childp -> time 312 * ( ( (double) arcp -> arc_count ) / 313 ( (double) childp -> npropcall ) ); 314 arcp -> arc_childtime = childp -> childtime 315 * ( ( (double) arcp -> arc_count ) / 316 ( (double) childp -> npropcall ) ); 317 share = arcp -> arc_time + arcp -> arc_childtime; 318 parentp -> childtime += share; 319 /* 320 * ( 1 - propfraction ) gets lost along the way 321 */ 322 propshare = parentp -> propfraction * share; 323 /* 324 * fix things for printing 325 */ 326 parentp -> propchild += propshare; 327 arcp -> arc_time *= parentp -> propfraction; 328 arcp -> arc_childtime *= parentp -> propfraction; 329 /* 330 * add this share to the parent's cycle header, if any. 331 */ 332 if ( parentp -> cyclehead != parentp ) { 333 parentp -> cyclehead -> childtime += share; 334 parentp -> cyclehead -> propchild += propshare; 335 } 336 # ifdef DEBUG 337 if ( debug & PROPDEBUG ) { 338 printf( "[dotime] child \t" ); 339 printname( childp ); 340 printf( " with %f %f %d/%d\n" , 341 childp -> time , childp -> childtime , 342 arcp -> arc_count , childp -> npropcall ); 343 printf( "[dotime] parent\t" ); 344 printname( parentp ); 345 printf( "\n[dotime] share %f\n" , share ); 346 } 347 # endif DEBUG 348 } 349 } 350 351 cyclelink() 352 { 353 register nltype *nlp; 354 register nltype *cyclenlp; 355 int cycle; 356 nltype *memberp; 357 arctype *arcp; 358 359 /* 360 * Count the number of cycles, and initialze the cycle lists 361 */ 362 ncycle = 0; 363 for ( nlp = nl ; nlp < npe ; nlp++ ) { 364 /* 365 * this is how you find unattached cycles 366 */ 367 if ( nlp -> cyclehead == nlp && nlp -> cnext != 0 ) { 368 ncycle += 1; 369 } 370 } 371 /* 372 * cyclenl is indexed by cycle number: 373 * i.e. it is origin 1, not origin 0. 374 */ 375 cyclenl = (nltype *) calloc( ncycle + 1 , sizeof( nltype ) ); 376 if ( cyclenl == 0 ) { 377 fprintf( stderr , "%s: No room for %d bytes of cycle headers\n" , 378 whoami , ( ncycle + 1 ) * sizeof( nltype ) ); 379 done(); 380 } 381 /* 382 * now link cycles to true cycleheads, 383 * number them, accumulate the data for the cycle 384 */ 385 cycle = 0; 386 for ( nlp = nl ; nlp < npe ; nlp++ ) { 387 if ( !( nlp -> cyclehead == nlp && nlp -> cnext != 0 ) ) { 388 continue; 389 } 390 cycle += 1; 391 cyclenlp = &cyclenl[cycle]; 392 cyclenlp -> name = 0; /* the name */ 393 cyclenlp -> value = 0; /* the pc entry point */ 394 cyclenlp -> time = 0.0; /* ticks in this routine */ 395 cyclenlp -> childtime = 0.0; /* cumulative ticks in children */ 396 cyclenlp -> ncall = 0; /* how many times called */ 397 cyclenlp -> selfcalls = 0; /* how many calls to self */ 398 cyclenlp -> propfraction = 0.0; /* what % of time propagates */ 399 cyclenlp -> propself = 0.0; /* how much self time propagates */ 400 cyclenlp -> propchild = 0.0; /* how much child time propagates */ 401 cyclenlp -> printflag = TRUE; /* should this be printed? */ 402 cyclenlp -> index = 0; /* index in the graph list */ 403 cyclenlp -> toporder = DFN_NAN; /* graph call chain top-sort order */ 404 cyclenlp -> cycleno = cycle; /* internal number of cycle on */ 405 cyclenlp -> cyclehead = cyclenlp; /* pointer to head of cycle */ 406 cyclenlp -> cnext = nlp; /* pointer to next member of cycle */ 407 cyclenlp -> parents = 0; /* list of caller arcs */ 408 cyclenlp -> children = 0; /* list of callee arcs */ 409 # ifdef DEBUG 410 if ( debug & CYCLEDEBUG ) { 411 printf( "[cyclelink] " ); 412 printname( nlp ); 413 printf( " is the head of cycle %d\n" , cycle ); 414 } 415 # endif DEBUG 416 /* 417 * link members to cycle header 418 */ 419 for ( memberp = nlp ; memberp ; memberp = memberp -> cnext ) { 420 memberp -> cycleno = cycle; 421 memberp -> cyclehead = cyclenlp; 422 } 423 /* 424 * count calls from outside the cycle 425 * and those among cycle members 426 */ 427 for ( memberp = nlp ; memberp ; memberp = memberp -> cnext ) { 428 for ( arcp=memberp->parents ; arcp ; arcp=arcp->arc_parentlist ) { 429 if ( arcp -> arc_parentp == memberp ) { 430 continue; 431 } 432 if ( arcp -> arc_parentp -> cycleno == cycle ) { 433 cyclenlp -> selfcalls += arcp -> arc_count; 434 } else { 435 cyclenlp -> npropcall += arcp -> arc_count; 436 } 437 } 438 } 439 } 440 } 441 442 /* 443 * analyze cycles to determine breakup 444 */ 445 cycleanalyze() 446 { 447 arctype **cyclestack; 448 arctype **stkp; 449 arctype **arcpp; 450 arctype **endlist; 451 arctype *arcp; 452 nltype *nlp; 453 cltype *clp; 454 bool ret; 455 bool done; 456 int size; 457 int cycleno; 458 459 /* 460 * calculate the size of the cycle, and find nodes that 461 * exit the cycle as they are desirable targets to cut 462 * some of their parents 463 */ 464 for ( done = TRUE , cycleno = 1 ; cycleno <= ncycle ; cycleno++ ) { 465 size = 0; 466 for (nlp = cyclenl[ cycleno ] . cnext; nlp; nlp = nlp -> cnext) { 467 size += 1; 468 nlp -> parentcnt = 0; 469 nlp -> flags &= ~HASCYCLEXIT; 470 for ( arcp = nlp -> parents; arcp; arcp = arcp -> arc_parentlist ) { 471 nlp -> parentcnt += 1; 472 if ( arcp -> arc_parentp -> cycleno != cycleno ) 473 nlp -> flags |= HASCYCLEXIT; 474 } 475 } 476 if ( size <= cyclethreshold ) 477 continue; 478 done = FALSE; 479 cyclestack = (arctype **) calloc( size + 1 , sizeof( arctype *) ); 480 if ( cyclestack == 0 ) { 481 fprintf( stderr , "%s: No room for %d bytes of cycle stack\n" , 482 whoami , ( size + 1 ) * sizeof( arctype * ) ); 483 return; 484 } 485 # ifdef DEBUG 486 if ( debug & BREAKCYCLE ) { 487 printf( "[cycleanalyze] starting cycle %d of %d, size %d\n" , 488 cycleno , ncycle , size ); 489 } 490 # endif DEBUG 491 for ( nlp = cyclenl[ cycleno ] . cnext ; nlp ; nlp = nlp -> cnext ) { 492 stkp = &cyclestack[0]; 493 nlp -> flags |= CYCLEHEAD; 494 ret = descend ( nlp , cyclestack , stkp ); 495 nlp -> flags &= ~CYCLEHEAD; 496 if ( ret == FALSE ) 497 break; 498 } 499 free( cyclestack ); 500 if ( cyclecnt > 0 ) { 501 compresslist(); 502 for ( clp = cyclehead ; clp ; ) { 503 endlist = &clp -> list[ clp -> size ]; 504 for ( arcpp = clp -> list ; arcpp < endlist ; arcpp++ ) 505 (*arcpp) -> arc_cyclecnt--; 506 cyclecnt--; 507 clp = clp -> next; 508 free( clp ); 509 } 510 cyclehead = 0; 511 } 512 } 513 # ifdef DEBUG 514 if ( debug & BREAKCYCLE ) { 515 printf("%s visited %d, viable %d, newcycle %d, oldcycle %d\n", 516 "[doarcs]" , visited , viable , newcycle , oldcycle); 517 } 518 # endif DEBUG 519 return( done ); 520 } 521 522 descend( node , stkstart , stkp ) 523 nltype *node; 524 arctype **stkstart; 525 arctype **stkp; 526 { 527 arctype *arcp; 528 bool ret; 529 530 for ( arcp = node -> children ; arcp ; arcp = arcp -> arc_childlist ) { 531 # ifdef DEBUG 532 visited++; 533 # endif DEBUG 534 if ( arcp -> arc_childp -> cycleno != node -> cycleno 535 || ( arcp -> arc_childp -> flags & VISITED ) 536 || ( arcp -> arc_flags & DEADARC ) ) 537 continue; 538 # ifdef DEBUG 539 viable++; 540 # endif DEBUG 541 *stkp = arcp; 542 if ( arcp -> arc_childp -> flags & CYCLEHEAD ) { 543 if ( addcycle( stkstart , stkp ) == FALSE ) 544 return( FALSE ); 545 continue; 546 } 547 arcp -> arc_childp -> flags |= VISITED; 548 ret = descend( arcp -> arc_childp , stkstart , stkp + 1 ); 549 arcp -> arc_childp -> flags &= ~VISITED; 550 if ( ret == FALSE ) 551 return( FALSE ); 552 } 553 } 554 555 addcycle( stkstart , stkend ) 556 arctype **stkstart; 557 arctype **stkend; 558 { 559 arctype **arcpp; 560 arctype **stkloc; 561 arctype **stkp; 562 arctype **endlist; 563 arctype *minarc; 564 arctype *arcp; 565 cltype *clp; 566 int size; 567 568 size = stkend - stkstart + 1; 569 if ( size <= 1 ) 570 return( TRUE ); 571 for ( arcpp = stkstart , minarc = *arcpp ; arcpp <= stkend ; arcpp++ ) { 572 if ( *arcpp > minarc ) 573 continue; 574 minarc = *arcpp; 575 stkloc = arcpp; 576 } 577 for ( clp = cyclehead ; clp ; clp = clp -> next ) { 578 if ( clp -> size != size ) 579 continue; 580 stkp = stkloc; 581 endlist = &clp -> list[ size ]; 582 for ( arcpp = clp -> list ; arcpp < endlist ; arcpp++ ) { 583 if ( *stkp++ != *arcpp ) 584 break; 585 if ( stkp > stkend ) 586 stkp = stkstart; 587 } 588 if ( arcpp == endlist ) { 589 # ifdef DEBUG 590 oldcycle++; 591 # endif DEBUG 592 return( TRUE ); 593 } 594 } 595 clp = (cltype *) 596 calloc( 1 , sizeof ( cltype ) + ( size - 1 ) * sizeof( arctype * ) ); 597 if ( clp == 0 ) { 598 fprintf( stderr , "%s: No room for %d bytes of subcycle storage\n" , 599 whoami , sizeof ( cltype ) + ( size - 1 ) * sizeof( arctype * ) ); 600 return( FALSE ); 601 } 602 stkp = stkloc; 603 endlist = &clp -> list[ size ]; 604 for ( arcpp = clp -> list ; arcpp < endlist ; arcpp++ ) { 605 arcp = *arcpp = *stkp++; 606 if ( stkp > stkend ) 607 stkp = stkstart; 608 arcp -> arc_cyclecnt++; 609 if ( ( arcp -> arc_flags & ONLIST ) == 0 ) { 610 arcp -> arc_flags |= ONLIST; 611 arcp -> arc_next = archead; 612 archead = arcp; 613 } 614 } 615 clp -> size = size; 616 clp -> next = cyclehead; 617 cyclehead = clp; 618 # ifdef DEBUG 619 newcycle++; 620 if ( debug & SUBCYCLELIST ) { 621 printsubcycle( clp ); 622 } 623 # endif DEBUG 624 cyclecnt++; 625 if ( cyclecnt >= CYCLEMAX ) 626 return( FALSE ); 627 return( TRUE ); 628 } 629 630 compresslist() 631 { 632 cltype *clp; 633 cltype **prev; 634 arctype **arcpp; 635 arctype **endlist; 636 arctype *arcp; 637 arctype *maxarcp; 638 arctype *maxexitarcp; 639 arctype *maxwithparentarcp; 640 arctype *maxnoparentarcp; 641 int maxexitcnt; 642 int maxwithparentcnt; 643 int maxnoparentcnt; 644 char *type; 645 646 maxexitcnt = 0; 647 maxwithparentcnt = 0; 648 maxnoparentcnt = 0; 649 for ( endlist = &archead , arcp = archead ; arcp ; ) { 650 if ( arcp -> arc_cyclecnt == 0 ) { 651 arcp -> arc_flags &= ~ONLIST; 652 *endlist = arcp -> arc_next; 653 arcp -> arc_next = 0; 654 arcp = *endlist; 655 continue; 656 } 657 if ( arcp -> arc_childp -> flags & HASCYCLEXIT ) { 658 if ( arcp -> arc_cyclecnt > maxexitcnt || 659 ( arcp -> arc_cyclecnt == maxexitcnt && 660 arcp -> arc_cyclecnt < maxexitarcp -> arc_count ) ) { 661 maxexitcnt = arcp -> arc_cyclecnt; 662 maxexitarcp = arcp; 663 } 664 } else if ( arcp -> arc_childp -> parentcnt > 1 ) { 665 if ( arcp -> arc_cyclecnt > maxwithparentcnt || 666 ( arcp -> arc_cyclecnt == maxwithparentcnt && 667 arcp -> arc_cyclecnt < maxwithparentarcp -> arc_count ) ) { 668 maxwithparentcnt = arcp -> arc_cyclecnt; 669 maxwithparentarcp = arcp; 670 } 671 } else { 672 if ( arcp -> arc_cyclecnt > maxnoparentcnt || 673 ( arcp -> arc_cyclecnt == maxnoparentcnt && 674 arcp -> arc_cyclecnt < maxnoparentarcp -> arc_count ) ) { 675 maxnoparentcnt = arcp -> arc_cyclecnt; 676 maxnoparentarcp = arcp; 677 } 678 } 679 endlist = &arcp -> arc_next; 680 arcp = arcp -> arc_next; 681 } 682 if ( maxexitcnt > 0 ) { 683 /* 684 * first choice is edge leading to node with out-of-cycle parent 685 */ 686 maxarcp = maxexitarcp; 687 # ifdef DEBUG 688 type = "exit"; 689 # endif DEBUG 690 } else if ( maxwithparentcnt > 0 ) { 691 /* 692 * second choice is edge leading to node with at least one 693 * other in-cycle parent 694 */ 695 maxarcp = maxwithparentarcp; 696 # ifdef DEBUG 697 type = "internal"; 698 # endif DEBUG 699 } else { 700 /* 701 * last choice is edge leading to node with only this arc as 702 * a parent (as it will now be orphaned) 703 */ 704 maxarcp = maxnoparentarcp; 705 # ifdef DEBUG 706 type = "orphan"; 707 # endif DEBUG 708 } 709 maxarcp -> arc_flags |= DEADARC; 710 maxarcp -> arc_childp -> parentcnt -= 1; 711 maxarcp -> arc_childp -> npropcall -= maxarcp -> arc_count; 712 # ifdef DEBUG 713 if ( debug & BREAKCYCLE ) { 714 printf( "%s delete %s arc: %s (%d) -> %s from %d cycle(s)\n" , 715 "[compresslist]" , type , maxarcp -> arc_parentp -> name , 716 maxarcp -> arc_count , maxarcp -> arc_childp -> name , 717 maxarcp -> arc_cyclecnt ); 718 } 719 # endif DEBUG 720 printf( "\t%s to %s with %d calls\n" , maxarcp -> arc_parentp -> name , 721 maxarcp -> arc_childp -> name , maxarcp -> arc_count ); 722 prev = &cyclehead; 723 for ( clp = cyclehead ; clp ; ) { 724 endlist = &clp -> list[ clp -> size ]; 725 for ( arcpp = clp -> list ; arcpp < endlist ; arcpp++ ) 726 if ( (*arcpp) -> arc_flags & DEADARC ) 727 break; 728 if ( arcpp == endlist ) { 729 prev = &clp -> next; 730 clp = clp -> next; 731 continue; 732 } 733 for ( arcpp = clp -> list ; arcpp < endlist ; arcpp++ ) 734 (*arcpp) -> arc_cyclecnt--; 735 cyclecnt--; 736 *prev = clp -> next; 737 clp = clp -> next; 738 free( clp ); 739 } 740 } 741 742 #ifdef DEBUG 743 printsubcycle( clp ) 744 cltype *clp; 745 { 746 arctype **arcpp; 747 arctype **endlist; 748 749 arcpp = clp -> list; 750 printf( "%s <cycle %d>\n" , (*arcpp) -> arc_parentp -> name , 751 (*arcpp) -> arc_parentp -> cycleno ) ; 752 for ( endlist = &clp -> list[ clp -> size ]; arcpp < endlist ; arcpp++ ) 753 printf( "\t(%d) -> %s\n" , (*arcpp) -> arc_count , 754 (*arcpp) -> arc_childp -> name ) ; 755 } 756 #endif DEBUG 757 758 cycletime() 759 { 760 int cycle; 761 nltype *cyclenlp; 762 nltype *childp; 763 764 for ( cycle = 1 ; cycle <= ncycle ; cycle += 1 ) { 765 cyclenlp = &cyclenl[ cycle ]; 766 for ( childp = cyclenlp -> cnext ; childp ; childp = childp -> cnext ) { 767 if ( childp -> propfraction == 0.0 ) { 768 /* 769 * all members have the same propfraction except those 770 * that were excluded with -E 771 */ 772 continue; 773 } 774 cyclenlp -> time += childp -> time; 775 } 776 cyclenlp -> propself = cyclenlp -> propfraction * cyclenlp -> time; 777 } 778 } 779 780 /* 781 * in one top to bottom pass over the topologically sorted namelist 782 * propagate: 783 * printflag as the union of parents' printflags 784 * propfraction as the sum of fractional parents' propfractions 785 * and while we're here, sum time for functions. 786 */ 787 doflags() 788 { 789 int index; 790 nltype *childp; 791 nltype *oldhead; 792 793 oldhead = 0; 794 for ( index = nname-1 ; index >= 0 ; index -= 1 ) { 795 childp = topsortnlp[ index ]; 796 /* 797 * if we haven't done this function or cycle, 798 * inherit things from parent. 799 * this way, we are linear in the number of arcs 800 * since we do all members of a cycle (and the cycle itself) 801 * as we hit the first member of the cycle. 802 */ 803 if ( childp -> cyclehead != oldhead ) { 804 oldhead = childp -> cyclehead; 805 inheritflags( childp ); 806 } 807 # ifdef DEBUG 808 if ( debug & PROPDEBUG ) { 809 printf( "[doflags] " ); 810 printname( childp ); 811 printf( " inherits printflag %d and propfraction %f\n" , 812 childp -> printflag , childp -> propfraction ); 813 } 814 # endif DEBUG 815 if ( ! childp -> printflag ) { 816 /* 817 * printflag is off 818 * it gets turned on by 819 * being on -f list, 820 * or there not being any -f list and not being on -e list. 821 */ 822 if ( onlist( flist , childp -> name ) 823 || ( !fflag && !onlist( elist , childp -> name ) ) ) { 824 childp -> printflag = TRUE; 825 } 826 } else { 827 /* 828 * this function has printing parents: 829 * maybe someone wants to shut it up 830 * by putting it on -e list. (but favor -f over -e) 831 */ 832 if ( ( !onlist( flist , childp -> name ) ) 833 && onlist( elist , childp -> name ) ) { 834 childp -> printflag = FALSE; 835 } 836 } 837 if ( childp -> propfraction == 0.0 ) { 838 /* 839 * no parents to pass time to. 840 * collect time from children if 841 * its on -F list, 842 * or there isn't any -F list and its not on -E list. 843 */ 844 if ( onlist( Flist , childp -> name ) 845 || ( !Fflag && !onlist( Elist , childp -> name ) ) ) { 846 childp -> propfraction = 1.0; 847 } 848 } else { 849 /* 850 * it has parents to pass time to, 851 * but maybe someone wants to shut it up 852 * by puttting it on -E list. (but favor -F over -E) 853 */ 854 if ( !onlist( Flist , childp -> name ) 855 && onlist( Elist , childp -> name ) ) { 856 childp -> propfraction = 0.0; 857 } 858 } 859 childp -> propself = childp -> time * childp -> propfraction; 860 printtime += childp -> propself; 861 # ifdef DEBUG 862 if ( debug & PROPDEBUG ) { 863 printf( "[doflags] " ); 864 printname( childp ); 865 printf( " ends up with printflag %d and propfraction %f\n" , 866 childp -> printflag , childp -> propfraction ); 867 printf( "time %f propself %f printtime %f\n" , 868 childp -> time , childp -> propself , printtime ); 869 } 870 # endif DEBUG 871 } 872 } 873 874 /* 875 * check if any parent of this child 876 * (or outside parents of this cycle) 877 * have their print flags on and set the 878 * print flag of the child (cycle) appropriately. 879 * similarly, deal with propagation fractions from parents. 880 */ 881 inheritflags( childp ) 882 nltype *childp; 883 { 884 nltype *headp; 885 arctype *arcp; 886 nltype *parentp; 887 nltype *memp; 888 889 headp = childp -> cyclehead; 890 if ( childp == headp ) { 891 /* 892 * just a regular child, check its parents 893 */ 894 childp -> printflag = FALSE; 895 childp -> propfraction = 0.0; 896 for (arcp = childp -> parents ; arcp ; arcp = arcp -> arc_parentlist) { 897 parentp = arcp -> arc_parentp; 898 if ( childp == parentp ) { 899 continue; 900 } 901 childp -> printflag |= parentp -> printflag; 902 /* 903 * if the child was never actually called 904 * (e.g. this arc is static (and all others are, too)) 905 * no time propagates along this arc. 906 */ 907 if ( arcp -> arc_flags & DEADARC ) { 908 continue; 909 } 910 if ( childp -> npropcall ) { 911 childp -> propfraction += parentp -> propfraction 912 * ( ( (double) arcp -> arc_count ) 913 / ( (double) childp -> npropcall ) ); 914 } 915 } 916 } else { 917 /* 918 * its a member of a cycle, look at all parents from 919 * outside the cycle 920 */ 921 headp -> printflag = FALSE; 922 headp -> propfraction = 0.0; 923 for ( memp = headp -> cnext ; memp ; memp = memp -> cnext ) { 924 for (arcp = memp->parents ; arcp ; arcp = arcp->arc_parentlist) { 925 if ( arcp -> arc_parentp -> cyclehead == headp ) { 926 continue; 927 } 928 parentp = arcp -> arc_parentp; 929 headp -> printflag |= parentp -> printflag; 930 /* 931 * if the cycle was never actually called 932 * (e.g. this arc is static (and all others are, too)) 933 * no time propagates along this arc. 934 */ 935 if ( arcp -> arc_flags & DEADARC ) { 936 continue; 937 } 938 if ( headp -> npropcall ) { 939 headp -> propfraction += parentp -> propfraction 940 * ( ( (double) arcp -> arc_count ) 941 / ( (double) headp -> npropcall ) ); 942 } 943 } 944 } 945 for ( memp = headp ; memp ; memp = memp -> cnext ) { 946 memp -> printflag = headp -> printflag; 947 memp -> propfraction = headp -> propfraction; 948 } 949 } 950 } 951