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