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