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