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