usr.bin/gprof/arcs.c

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