usr.bin/gprof/arcs.c

   1 /*
   2  * Copyright (c) 1983, 1993
   3  *      The Regents of the University of California.  All rights reserved.
   4  *
   5  * Redistribution and use in source and binary forms, with or without
   6  * modification, are permitted provided that the following conditions
   7  * are met:
   8  * 1. Redistributions of source code must retain the above copyright
   9  *    notice, this list of conditions and the following disclaimer.
  10  * 2. Redistributions in binary form must reproduce the above copyright
  11  *    notice, this list of conditions and the following disclaimer in the
  12  *    documentation and/or other materials provided with the distribution.
  13  * 3. All advertising materials mentioning features or use of this software
  14  *    must display the following acknowledgement:
  15  *      This product includes software developed by the University of
  16  *      California, Berkeley and its contributors.
  17  * 4. Neither the name of the University nor the names of its contributors
  18  *    may be used to endorse or promote products derived from this software
  19  *    without specific prior written permission.
  20  *
  21  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  22  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  23  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  24  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  25  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  26  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  27  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  28  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  29  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  30  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  31  * SUCH DAMAGE.
  32  *
  33  * @(#)arcs.c   8.1 (Berkeley) 6/6/93
  34  * $FreeBSD: src/usr.bin/gprof/arcs.c,v 1.6 1999/08/28 01:01:54 peter Exp $
  35  * $DragonFly: src/usr.bin/gprof/arcs.c,v 1.2 2003/06/17 04:29:27 dillon Exp $
  36  */
  37
  38 #include <err.h>
  39 #include "gprof.h"
  40
  41 #ifdef DEBUG
  42 int visited;
  43 int viable;
  44 int newcycle;
  45 int oldcycle;
  46 #endif DEBUG
  47
  48     /*
  49      *  add (or just increment) an arc
  50      */
  51 addarc( parentp , childp , count )
  52     nltype      *parentp;
  53     nltype      *childp;
  54     long        count;
  55 {
  56     arctype             *arcp;
  57
  58 #   ifdef DEBUG
  59         if ( debug & TALLYDEBUG ) {
  60             printf( "[addarc] %d arcs from %s to %s\n" ,
  61                     count , parentp -> name , childp -> name );
  62         }
  63 #   endif DEBUG
  64     arcp = arclookup( parentp , childp );
  65     if ( arcp != 0 ) {
  66             /*
  67              *  a hit:  just increment the count.
  68              */
  69 #       ifdef DEBUG
  70             if ( debug & TALLYDEBUG ) {
  71                 printf( "[tally] hit %d += %d\n" ,
  72                         arcp -> arc_count , count );
  73             }
  74 #       endif DEBUG
  75         arcp -> arc_count += count;
  76         return;
  77     }
  78     arcp = (arctype *)calloc( 1 , sizeof *arcp );
  79     arcp -> arc_parentp = parentp;
  80     arcp -> arc_childp = childp;
  81     arcp -> arc_count = count;
  82         /*
  83          *      prepend this child to the children of this parent
  84          */
  85     arcp -> arc_childlist = parentp -> children;
  86     parentp -> children = arcp;
  87         /*
  88          *      prepend this parent to the parents of this child
  89          */
  90     arcp -> arc_parentlist = childp -> parents;
  91     childp -> parents = arcp;
  92 }
  93
  94     /*
  95      *  the code below topologically sorts the graph (collapsing cycles),
  96      *  and propagates time bottom up and flags top down.
  97      */
  98
  99     /*
 100      *  the topologically sorted name list pointers
 101      */
 102 nltype  **topsortnlp;
 103
 104 topcmp( npp1 , npp2 )
 105     nltype      **npp1;
 106     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 %d, 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         fprintf( stderr , "[doarcs] ran out of memory for topo sorting\n" );
 203     }
 204     for ( index = 0 ; index < nname ; index += 1 ) {
 205         topsortnlp[ index ] = &nl[ index ];
 206     }
 207     qsort( topsortnlp , nname , sizeof(nltype *) , topcmp );
 208 #   ifdef DEBUG
 209         if ( debug & DFNDEBUG ) {
 210             printf( "[doarcs] topological sort listing\n" );
 211             for ( index = 0 ; index < nname ; index += 1 ) {
 212                 printf( "[doarcs] " );
 213                 printf( "%d:" , topsortnlp[ index ] -> toporder );
 214                 printname( topsortnlp[ index ] );
 215                 printf( "\n" );
 216             }
 217         }
 218 #   endif DEBUG
 219         /*
 220          *      starting from the topological top,
 221          *      propagate print flags to children.
 222          *      also, calculate propagation fractions.
 223          *      this happens before time propagation
 224          *      since time propagation uses the fractions.
 225          */
 226     doflags();
 227         /*
 228          *      starting from the topological bottom,
 229          *      propogate children times up to parents.
 230          */
 231     dotime();
 232         /*
 233          *      Now, sort by propself + propchild.
 234          *      sorting both the regular function names
 235          *      and cycle headers.
 236          */
 237     timesortnlp = (nltype **) calloc( nname + ncycle , sizeof(nltype *) );
 238     if ( timesortnlp == (nltype **) 0 ) {
 239         warnx("ran out of memory for sorting");
 240     }
 241     for ( index = 0 ; index < nname ; index++ ) {
 242         timesortnlp[index] = &nl[index];
 243     }
 244     for ( index = 1 ; index <= ncycle ; index++ ) {
 245         timesortnlp[nname+index-1] = &cyclenl[index];
 246     }
 247     qsort( timesortnlp , nname + ncycle , sizeof(nltype *) , totalcmp );
 248     for ( index = 0 ; index < nname + ncycle ; index++ ) {
 249         timesortnlp[ index ] -> index = index + 1;
 250     }
 251     return( timesortnlp );
 252 }
 253
 254 dotime()
 255 {
 256     int index;
 257
 258     cycletime();
 259     for ( index = 0 ; index < nname ; index += 1 ) {
 260         timepropagate( topsortnlp[ index ] );
 261     }
 262 }
 263
 264 timepropagate( parentp )
 265     nltype      *parentp;
 266 {
 267     arctype     *arcp;
 268     nltype      *childp;
 269     double      share;
 270     double      propshare;
 271
 272     if ( parentp -> propfraction == 0.0 ) {
 273         return;
 274     }
 275         /*
 276          *      gather time from children of this parent.
 277          */
 278     for ( arcp = parentp -> children ; arcp ; arcp = arcp -> arc_childlist ) {
 279         childp = arcp -> arc_childp;
 280         if ( arcp -> arc_flags & DEADARC ) {
 281             continue;
 282         }
 283         if ( arcp -> arc_count == 0 ) {
 284             continue;
 285         }
 286         if ( childp == parentp ) {
 287             continue;
 288         }
 289         if ( childp -> propfraction == 0.0 ) {
 290             continue;
 291         }
 292         if ( childp -> cyclehead != childp ) {
 293             if ( parentp -> cycleno == childp -> cycleno ) {
 294                 continue;
 295             }
 296             if ( parentp -> toporder <= childp -> toporder ) {
 297                 fprintf( stderr , "[propagate] toporder botches\n" );
 298             }
 299             childp = childp -> cyclehead;
 300         } else {
 301             if ( parentp -> toporder <= childp -> toporder ) {
 302                 fprintf( stderr , "[propagate] toporder botches\n" );
 303                 continue;
 304             }
 305         }
 306         if ( childp -> npropcall == 0 ) {
 307             continue;
 308         }
 309             /*
 310              *  distribute time for this arc
 311              */
 312         arcp -> arc_time = childp -> time
 313                                 * ( ( (double) arcp -> arc_count ) /
 314                                     ( (double) childp -> npropcall ) );
 315         arcp -> arc_childtime = childp -> childtime
 316                                 * ( ( (double) arcp -> arc_count ) /
 317                                     ( (double) childp -> npropcall ) );
 318         share = arcp -> arc_time + arcp -> arc_childtime;
 319         parentp -> childtime += share;
 320             /*
 321              *  ( 1 - propfraction ) gets lost along the way
 322              */
 323         propshare = parentp -> propfraction * share;
 324             /*
 325              *  fix things for printing
 326              */
 327         parentp -> propchild += propshare;
 328         arcp -> arc_time *= parentp -> propfraction;
 329         arcp -> arc_childtime *= parentp -> propfraction;
 330             /*
 331              *  add this share to the parent's cycle header, if any.
 332              */
 333         if ( parentp -> cyclehead != parentp ) {
 334             parentp -> cyclehead -> childtime += share;
 335             parentp -> cyclehead -> propchild += propshare;
 336         }
 337 #       ifdef DEBUG
 338             if ( debug & PROPDEBUG ) {
 339                 printf( "[dotime] child \t" );
 340                 printname( childp );
 341                 printf( " with %f %f %d/%d\n" ,
 342                         childp -> time , childp -> childtime ,
 343                         arcp -> arc_count , childp -> npropcall );
 344                 printf( "[dotime] parent\t" );
 345                 printname( parentp );
 346                 printf( "\n[dotime] share %f\n" , share );
 347             }
 348 #       endif DEBUG
 349     }
 350 }
 351
 352 cyclelink()
 353 {
 354     register nltype     *nlp;
 355     register nltype     *cyclenlp;
 356     int                 cycle;
 357     nltype              *memberp;
 358     arctype             *arcp;
 359
 360         /*
 361          *      Count the number of cycles, and initialze the cycle lists
 362          */
 363     ncycle = 0;
 364     for ( nlp = nl ; nlp < npe ; nlp++ ) {
 365             /*
 366              *  this is how you find unattached cycles
 367              */
 368         if ( nlp -> cyclehead == nlp && nlp -> cnext != 0 ) {
 369             ncycle += 1;
 370         }
 371     }
 372         /*
 373          *      cyclenl is indexed by cycle number:
 374          *      i.e. it is origin 1, not origin 0.
 375          */
 376     cyclenl = (nltype *) calloc( ncycle + 1 , sizeof( nltype ) );
 377     if ( cyclenl == 0 ) {
 378         warnx("no room for %d bytes of cycle headers",
 379                    ( ncycle + 1 ) * sizeof( nltype ) );
 380         done();
 381     }
 382         /*
 383          *      now link cycles to true cycleheads,
 384          *      number them, accumulate the data for the cycle
 385          */
 386     cycle = 0;
 387     for ( nlp = nl ; nlp < npe ; nlp++ ) {
 388         if ( !( nlp -> cyclehead == nlp && nlp -> cnext != 0 ) ) {
 389             continue;
 390         }
 391         cycle += 1;
 392         cyclenlp = &cyclenl[cycle];
 393         cyclenlp -> name = 0;           /* the name */
 394         cyclenlp -> value = 0;          /* the pc entry point */
 395         cyclenlp -> time = 0.0;         /* ticks in this routine */
 396         cyclenlp -> childtime = 0.0;    /* cumulative ticks in children */
 397         cyclenlp -> ncall = 0;          /* how many times called */
 398         cyclenlp -> selfcalls = 0;      /* how many calls to self */
 399         cyclenlp -> propfraction = 0.0; /* what % of time propagates */
 400         cyclenlp -> propself = 0.0;     /* how much self time propagates */
 401         cyclenlp -> propchild = 0.0;    /* how much child time propagates */
 402         cyclenlp -> printflag = TRUE;   /* should this be printed? */
 403         cyclenlp -> index = 0;          /* index in the graph list */
 404         cyclenlp -> toporder = DFN_NAN; /* graph call chain top-sort order */
 405         cyclenlp -> cycleno = cycle;    /* internal number of cycle on */
 406         cyclenlp -> cyclehead = cyclenlp;       /* pointer to head of cycle */
 407         cyclenlp -> cnext = nlp;        /* pointer to next member of cycle */
 408         cyclenlp -> parents = 0;        /* list of caller arcs */
 409         cyclenlp -> children = 0;       /* list of callee arcs */
 410 #       ifdef DEBUG
 411             if ( debug & CYCLEDEBUG ) {
 412                 printf( "[cyclelink] " );
 413                 printname( nlp );
 414                 printf( " is the head of cycle %d\n" , cycle );
 415             }
 416 #       endif DEBUG
 417             /*
 418              *  link members to cycle header
 419              */
 420         for ( memberp = nlp ; memberp ; memberp = memberp -> cnext ) {
 421             memberp -> cycleno = cycle;
 422             memberp -> cyclehead = cyclenlp;
 423         }
 424             /*
 425              *  count calls from outside the cycle
 426              *  and those among cycle members
 427              */
 428         for ( memberp = nlp ; memberp ; memberp = memberp -> cnext ) {
 429             for ( arcp=memberp->parents ; arcp ; arcp=arcp->arc_parentlist ) {
 430                 if ( arcp -> arc_parentp == memberp ) {
 431                     continue;
 432                 }
 433                 if ( arcp -> arc_parentp -> cycleno == cycle ) {
 434                     cyclenlp -> selfcalls += arcp -> arc_count;
 435                 } else {
 436                     cyclenlp -> npropcall += arcp -> arc_count;
 437                 }
 438             }
 439         }
 440     }
 441 }
 442
 443     /*
 444      *  analyze cycles to determine breakup
 445      */
 446 cycleanalyze()
 447 {
 448     arctype     **cyclestack;
 449     arctype     **stkp;
 450     arctype     **arcpp;
 451     arctype     **endlist;
 452     arctype     *arcp;
 453     nltype      *nlp;
 454     cltype      *clp;
 455     bool        ret;
 456     bool        done;
 457     int         size;
 458     int         cycleno;
 459
 460         /*
 461          *      calculate the size of the cycle, and find nodes that
 462          *      exit the cycle as they are desirable targets to cut
 463          *      some of their parents
 464          */
 465     for ( done = TRUE , cycleno = 1 ; cycleno <= ncycle ; cycleno++ ) {
 466         size = 0;
 467         for (nlp = cyclenl[ cycleno ] . cnext; nlp; nlp = nlp -> cnext) {
 468             size += 1;
 469             nlp -> parentcnt = 0;
 470             nlp -> flags &= ~HASCYCLEXIT;
 471             for ( arcp = nlp -> parents; arcp; arcp = arcp -> arc_parentlist ) {
 472                 nlp -> parentcnt += 1;
 473                 if ( arcp -> arc_parentp -> cycleno != cycleno )
 474                     nlp -> flags |= HASCYCLEXIT;
 475             }
 476         }
 477         if ( size <= cyclethreshold )
 478             continue;
 479         done = FALSE;
 480         cyclestack = (arctype **) calloc( size + 1 , sizeof( arctype *) );
 481         if ( cyclestack == 0 ) {
 482             warnx("no room for %d bytes of cycle stack",
 483                            ( size + 1 ) * sizeof( arctype * ) );
 484             return;
 485         }
 486 #       ifdef DEBUG
 487             if ( debug & BREAKCYCLE ) {
 488                 printf( "[cycleanalyze] starting cycle %d of %d, size %d\n" ,
 489                     cycleno , ncycle , size );
 490             }
 491 #       endif DEBUG
 492         for ( nlp = cyclenl[ cycleno ] . cnext ; nlp ; nlp = nlp -> cnext ) {
 493             stkp = &cyclestack[0];
 494             nlp -> flags |= CYCLEHEAD;
 495             ret = descend ( nlp , cyclestack , stkp );
 496             nlp -> flags &= ~CYCLEHEAD;
 497             if ( ret == FALSE )
 498                 break;
 499         }
 500         free( cyclestack );
 501         if ( cyclecnt > 0 ) {
 502             compresslist();
 503             for ( clp = cyclehead ; clp ; ) {
 504                 endlist = &clp -> list[ clp -> size ];
 505                 for ( arcpp = clp -> list ; arcpp < endlist ; arcpp++ )
 506                     (*arcpp) -> arc_cyclecnt--;
 507                 cyclecnt--;
 508                 clp = clp -> next;
 509                 free( clp );
 510             }
 511             cyclehead = 0;
 512         }
 513     }
 514 #   ifdef DEBUG
 515         if ( debug & BREAKCYCLE ) {
 516             printf("%s visited %d, viable %d, newcycle %d, oldcycle %d\n",
 517                 "[doarcs]" , visited , viable , newcycle , oldcycle);
 518         }
 519 #   endif DEBUG
 520     return( done );
 521 }
 522
 523 descend( node , stkstart , stkp )
 524     nltype      *node;
 525     arctype     **stkstart;
 526     arctype     **stkp;
 527 {
 528     arctype     *arcp;
 529     bool        ret;
 530
 531     for ( arcp = node -> children ; arcp ; arcp = arcp -> arc_childlist ) {
 532 #       ifdef DEBUG
 533             visited++;
 534 #       endif DEBUG
 535         if ( arcp -> arc_childp -> cycleno != node -> cycleno
 536             || ( arcp -> arc_childp -> flags & VISITED )
 537             || ( arcp -> arc_flags & DEADARC ) )
 538             continue;
 539 #       ifdef DEBUG
 540             viable++;
 541 #       endif DEBUG
 542         *stkp = arcp;
 543         if ( arcp -> arc_childp -> flags & CYCLEHEAD ) {
 544             if ( addcycle( stkstart , stkp ) == FALSE )
 545                 return( FALSE );
 546             continue;
 547         }
 548         arcp -> arc_childp -> flags |= VISITED;
 549         ret = descend( arcp -> arc_childp , stkstart , stkp + 1 );
 550         arcp -> arc_childp -> flags &= ~VISITED;
 551         if ( ret == FALSE )
 552             return( FALSE );
 553     }
 554 }
 555
 556 addcycle( stkstart , stkend )
 557     arctype     **stkstart;
 558     arctype     **stkend;
 559 {
 560     arctype     **arcpp;
 561     arctype     **stkloc;
 562     arctype     **stkp;
 563     arctype     **endlist;
 564     arctype     *minarc;
 565     arctype     *arcp;
 566     cltype      *clp;
 567     int         size;
 568
 569     size = stkend - stkstart + 1;
 570     if ( size <= 1 )
 571         return( TRUE );
 572     for ( arcpp = stkstart , minarc = *arcpp ; arcpp <= stkend ; arcpp++ ) {
 573         if ( *arcpp > minarc )
 574             continue;
 575         minarc = *arcpp;
 576         stkloc = arcpp;
 577     }
 578     for ( clp = cyclehead ; clp ; clp = clp -> next ) {
 579         if ( clp -> size != size )
 580             continue;
 581         stkp = stkloc;
 582         endlist = &clp -> list[ size ];
 583         for ( arcpp = clp -> list ; arcpp < endlist ; arcpp++ ) {
 584             if ( *stkp++ != *arcpp )
 585                 break;
 586             if ( stkp > stkend )
 587                 stkp = stkstart;
 588         }
 589         if ( arcpp == endlist ) {
 590 #           ifdef DEBUG
 591                 oldcycle++;
 592 #           endif DEBUG
 593             return( TRUE );
 594         }
 595     }
 596     clp = (cltype *)
 597         calloc( 1 , sizeof ( cltype ) + ( size - 1 ) * sizeof( arctype * ) );
 598     if ( clp == 0 ) {
 599         warnx("no room for %d bytes of subcycle storage",
 600             sizeof ( cltype ) + ( size - 1 ) * sizeof( arctype * ) );
 601         return( FALSE );
 602     }
 603     stkp = stkloc;
 604     endlist = &clp -> list[ size ];
 605     for ( arcpp = clp -> list ; arcpp < endlist ; arcpp++ ) {
 606         arcp = *arcpp = *stkp++;
 607         if ( stkp > stkend )
 608             stkp = stkstart;
 609         arcp -> arc_cyclecnt++;
 610         if ( ( arcp -> arc_flags & ONLIST ) == 0 ) {
 611             arcp -> arc_flags |= ONLIST;
 612             arcp -> arc_next = archead;
 613             archead = arcp;
 614         }
 615     }
 616     clp -> size = size;
 617     clp -> next = cyclehead;
 618     cyclehead = clp;
 619 #   ifdef DEBUG
 620         newcycle++;
 621         if ( debug & SUBCYCLELIST ) {
 622             printsubcycle( clp );
 623         }
 624 #   endif DEBUG
 625     cyclecnt++;
 626     if ( cyclecnt >= CYCLEMAX )
 627         return( FALSE );
 628     return( TRUE );
 629 }
 630
 631 compresslist()
 632 {
 633     cltype      *clp;
 634     cltype      **prev;
 635     arctype     **arcpp;
 636     arctype     **endlist;
 637     arctype     *arcp;
 638     arctype     *maxarcp;
 639     arctype     *maxexitarcp;
 640     arctype     *maxwithparentarcp;
 641     arctype     *maxnoparentarcp;
 642     int         maxexitcnt;
 643     int         maxwithparentcnt;
 644     int         maxnoparentcnt;
 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( "%s delete %s arc: %s (%d) -> %s from %d cycle(s)\n" ,
 715                 "[compresslist]" , type , maxarcp -> arc_parentp -> name ,
 716                 maxarcp -> arc_count , maxarcp -> arc_childp -> name ,
 717                 maxarcp -> arc_cyclecnt );
 718         }
 719 #   endif DEBUG
 720     printf( "\t%s to %s with %d 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         clp = clp -> next;
 738         free( clp );
 739     }
 740 }
 741
 742 #ifdef DEBUG
 743 printsubcycle( clp )
 744     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(%d) -> %s\n" , (*arcpp) -> arc_count ,
 754             (*arcpp) -> arc_childp -> name ) ;
 755 }
 756 #endif DEBUG
 757
 758 cycletime()
 759 {
 760     int                 cycle;
 761     nltype              *cyclenlp;
 762     nltype              *childp;
 763
 764     for ( cycle = 1 ; cycle <= ncycle ; cycle += 1 ) {
 765         cyclenlp = &cyclenl[ cycle ];
 766         for ( childp = cyclenlp -> cnext ; childp ; childp = childp -> cnext ) {
 767             if ( childp -> propfraction == 0.0 ) {
 768                     /*
 769                      * all members have the same propfraction except those
 770                      *  that were excluded with -E
 771                      */
 772                 continue;
 773             }
 774             cyclenlp -> time += childp -> time;
 775         }
 776         cyclenlp -> propself = cyclenlp -> propfraction * cyclenlp -> time;
 777     }
 778 }
 779
 780     /*
 781      *  in one top to bottom pass over the topologically sorted namelist
 782      *  propagate:
 783      *          printflag as the union of parents' printflags
 784      *          propfraction as the sum of fractional parents' propfractions
 785      *  and while we're here, sum time for functions.
 786      */
 787 doflags()
 788 {
 789     int         index;
 790     nltype      *childp;
 791     nltype      *oldhead;
 792
 793     oldhead = 0;
 794     for ( index = nname-1 ; index >= 0 ; index -= 1 ) {
 795         childp = topsortnlp[ index ];
 796             /*
 797              *  if we haven't done this function or cycle,
 798              *  inherit things from parent.
 799              *  this way, we are linear in the number of arcs
 800              *  since we do all members of a cycle (and the cycle itself)
 801              *  as we hit the first member of the cycle.
 802              */
 803         if ( childp -> cyclehead != oldhead ) {
 804             oldhead = childp -> cyclehead;
 805             inheritflags( childp );
 806         }
 807 #       ifdef DEBUG
 808             if ( debug & PROPDEBUG ) {
 809                 printf( "[doflags] " );
 810                 printname( childp );
 811                 printf( " inherits printflag %d and propfraction %f\n" ,
 812                         childp -> printflag , childp -> propfraction );
 813             }
 814 #       endif DEBUG
 815         if ( ! childp -> printflag ) {
 816                 /*
 817                  *      printflag is off
 818                  *      it gets turned on by
 819                  *      being on -f list,
 820                  *      or there not being any -f list and not being on -e list.
 821                  */
 822             if (   onlist( flist , childp -> name )
 823                 || ( !fflag && !onlist( elist , childp -> name ) ) ) {
 824                 childp -> printflag = TRUE;
 825             }
 826         } else {
 827                 /*
 828                  *      this function has printing parents:
 829                  *      maybe someone wants to shut it up
 830                  *      by putting it on -e list.  (but favor -f over -e)
 831                  */
 832             if (  ( !onlist( flist , childp -> name ) )
 833                 && onlist( elist , childp -> name ) ) {
 834                 childp -> printflag = FALSE;
 835             }
 836         }
 837         if ( childp -> propfraction == 0.0 ) {
 838                 /*
 839                  *      no parents to pass time to.
 840                  *      collect time from children if
 841                  *      its on -F list,
 842                  *      or there isn't any -F list and its not on -E list.
 843                  */
 844             if ( onlist( Flist , childp -> name )
 845                 || ( !Fflag && !onlist( Elist , childp -> name ) ) ) {
 846                     childp -> propfraction = 1.0;
 847             }
 848         } else {
 849                 /*
 850                  *      it has parents to pass time to,
 851                  *      but maybe someone wants to shut it up
 852                  *      by puttting it on -E list.  (but favor -F over -E)
 853                  */
 854             if (  !onlist( Flist , childp -> name )
 855                 && onlist( Elist , childp -> name ) ) {
 856                 childp -> propfraction = 0.0;
 857             }
 858         }
 859         childp -> propself = childp -> time * childp -> propfraction;
 860         printtime += childp -> propself;
 861 #       ifdef DEBUG
 862             if ( debug & PROPDEBUG ) {
 863                 printf( "[doflags] " );
 864                 printname( childp );
 865                 printf( " ends up with printflag %d and propfraction %f\n" ,
 866                         childp -> printflag , childp -> propfraction );
 867                 printf( "time %f propself %f printtime %f\n" ,
 868                         childp -> time , childp -> propself , printtime );
 869             }
 870 #       endif DEBUG
 871     }
 872 }
 873
 874     /*
 875      *  check if any parent of this child
 876      *  (or outside parents of this cycle)
 877      *  have their print flags on and set the
 878      *  print flag of the child (cycle) appropriately.
 879      *  similarly, deal with propagation fractions from parents.
 880      */
 881 inheritflags( childp )
 882     nltype      *childp;
 883 {
 884     nltype      *headp;
 885     arctype     *arcp;
 886     nltype      *parentp;
 887     nltype      *memp;
 888
 889     headp = childp -> cyclehead;
 890     if ( childp == headp ) {
 891             /*
 892              *  just a regular child, check its parents
 893              */
 894         childp -> printflag = FALSE;
 895         childp -> propfraction = 0.0;
 896         for (arcp = childp -> parents ; arcp ; arcp = arcp -> arc_parentlist) {
 897             parentp = arcp -> arc_parentp;
 898             if ( childp == parentp ) {
 899                 continue;
 900             }
 901             childp -> printflag |= parentp -> printflag;
 902                 /*
 903                  *      if the child was never actually called
 904                  *      (e.g. this arc is static (and all others are, too))
 905                  *      no time propagates along this arc.
 906                  */
 907             if ( arcp -> arc_flags & DEADARC ) {
 908                 continue;
 909             }
 910             if ( childp -> npropcall ) {
 911                 childp -> propfraction += parentp -> propfraction
 912                                         * ( ( (double) arcp -> arc_count )
 913                                           / ( (double) childp -> npropcall ) );
 914             }
 915         }
 916     } else {
 917             /*
 918              *  its a member of a cycle, look at all parents from
 919              *  outside the cycle
 920              */
 921         headp -> printflag = FALSE;
 922         headp -> propfraction = 0.0;
 923         for ( memp = headp -> cnext ; memp ; memp = memp -> cnext ) {
 924             for (arcp = memp->parents ; arcp ; arcp = arcp->arc_parentlist) {
 925                 if ( arcp -> arc_parentp -> cyclehead == headp ) {
 926                     continue;
 927                 }
 928                 parentp = arcp -> arc_parentp;
 929                 headp -> printflag |= parentp -> printflag;
 930                     /*
 931                      *  if the cycle was never actually called
 932                      *  (e.g. this arc is static (and all others are, too))
 933                      *  no time propagates along this arc.
 934                      */
 935                 if ( arcp -> arc_flags & DEADARC ) {
 936                     continue;
 937                 }
 938                 if ( headp -> npropcall ) {
 939                     headp -> propfraction += parentp -> propfraction
 940                                         * ( ( (double) arcp -> arc_count )
 941                                           / ( (double) headp -> npropcall ) );
 942                 }
 943             }
 944         }
 945         for ( memp = headp ; memp ; memp = memp -> cnext ) {
 946             memp -> printflag = headp -> printflag;
 947             memp -> propfraction = headp -> propfraction;
 948         }
 949     }
 950 }