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