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