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