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