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