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