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