usr.bin/gprof/arcs.c

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