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