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