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