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