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