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