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