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