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 topcmp(nltype **npp1, nltype **npp2)
 102 {
 103     return (*npp1) -> toporder - (*npp2) -> toporder;
 104 }
 105
 106 nltype **
 107 doarcs(void)
 108 {
 109     nltype      *parentp, **timesortnlp;
 110     arctype     *arcp;
 111     long        index;
 112     long        pass;
 113
 114         /*
 115          *      initialize various things:
 116          *          zero out child times.
 117          *          count self-recursive calls.
 118          *          indicate that nothing is on cycles.
 119          */
 120     for ( parentp = nl ; parentp < npe ; parentp++ ) {
 121         parentp -> childtime = 0.0;
 122         arcp = arclookup( parentp , parentp );
 123         if ( arcp != 0 ) {
 124             parentp -> ncall -= arcp -> arc_count;
 125             parentp -> selfcalls = arcp -> arc_count;
 126         } else {
 127             parentp -> selfcalls = 0;
 128         }
 129         parentp -> npropcall = parentp -> ncall;
 130         parentp -> propfraction = 0.0;
 131         parentp -> propself = 0.0;
 132         parentp -> propchild = 0.0;
 133         parentp -> printflag = FALSE;
 134         parentp -> toporder = DFN_NAN;
 135         parentp -> cycleno = 0;
 136         parentp -> cyclehead = parentp;
 137         parentp -> cnext = 0;
 138         if ( cflag ) {
 139             findcall( parentp , parentp -> value , (parentp+1) -> value );
 140         }
 141     }
 142     for ( pass = 1 ; ; pass++ ) {
 143             /*
 144              *  topologically order things
 145              *  if any node is unnumbered,
 146              *      number it and any of its descendents.
 147              */
 148         for ( dfn_init() , parentp = nl ; parentp < npe ; parentp++ ) {
 149             if ( parentp -> toporder == DFN_NAN ) {
 150                 dfn( parentp );
 151             }
 152         }
 153             /*
 154              *  link together nodes on the same cycle
 155              */
 156         cyclelink();
 157             /*
 158              *  if no cycles to break up, proceed
 159              */
 160         if ( ! Cflag )
 161             break;
 162             /*
 163              *  analyze cycles to determine breakup
 164              */
 165 #       ifdef DEBUG
 166             if ( debug & BREAKCYCLE ) {
 167                 printf("[doarcs] pass %d, cycle(s) %d\n" , pass , ncycle );
 168             }
 169 #       endif /* DEBUG */
 170         if ( pass == 1 ) {
 171             printf( "\n\n%s %s\n%s %d:\n" ,
 172                 "The following arcs were deleted" ,
 173                 "from the propagation calculation" ,
 174                 "to reduce the maximum cycle size to", cyclethreshold );
 175         }
 176         if ( cycleanalyze() )
 177             break;
 178         free ( cyclenl );
 179         ncycle = 0;
 180         for ( parentp = nl ; parentp < npe ; parentp++ ) {
 181             parentp -> toporder = DFN_NAN;
 182             parentp -> cycleno = 0;
 183             parentp -> cyclehead = parentp;
 184             parentp -> cnext = 0;
 185         }
 186     }
 187     if ( pass > 1 ) {
 188         printf( "\f\n" );
 189     } else {
 190         printf( "\tNone\n\n" );
 191     }
 192         /*
 193          *      Sort the symbol table in reverse topological order
 194          */
 195     topsortnlp = (nltype **) calloc( nname , sizeof(nltype *) );
 196     if ( topsortnlp == NULL ) {
 197         fprintf( stderr , "[doarcs] ran out of memory for topo sorting\n" );
 198     }
 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          *      propogate 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 == NULL ) {
 234         warnx("ran out of memory for sorting");
 235     }
 236     for ( index = 0 ; index < nname ; index++ ) {
 237         timesortnlp[index] = &nl[index];
 238     }
 239     for ( index = 1 ; index <= ncycle ; index++ ) {
 240         timesortnlp[nname+index-1] = &cyclenl[index];
 241     }
 242     qsort( timesortnlp , nname + ncycle , sizeof(nltype *) , totalcmp );
 243     for ( index = 0 ; index < nname + ncycle ; index++ ) {
 244         timesortnlp[ index ] -> index = index + 1;
 245     }
 246     return( timesortnlp );
 247 }
 248
 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 timepropagate(nltype *parentp)
 260 {
 261     arctype     *arcp;
 262     nltype      *childp;
 263     double      share;
 264     double      propshare;
 265
 266     if ( parentp -> propfraction == 0.0 ) {
 267         return;
 268     }
 269         /*
 270          *      gather time from children of this parent.
 271          */
 272     for ( arcp = parentp -> children ; arcp ; arcp = arcp -> arc_childlist ) {
 273         childp = arcp -> arc_childp;
 274         if ( arcp -> arc_flags & DEADARC ) {
 275             continue;
 276         }
 277         if ( arcp -> arc_count == 0 ) {
 278             continue;
 279         }
 280         if ( childp == parentp ) {
 281             continue;
 282         }
 283         if ( childp -> propfraction == 0.0 ) {
 284             continue;
 285         }
 286         if ( childp -> cyclehead != childp ) {
 287             if ( parentp -> cycleno == childp -> cycleno ) {
 288                 continue;
 289             }
 290             if ( parentp -> toporder <= childp -> toporder ) {
 291                 fprintf( stderr , "[propagate] toporder botches\n" );
 292             }
 293             childp = childp -> cyclehead;
 294         } else {
 295             if ( parentp -> toporder <= childp -> toporder ) {
 296                 fprintf( stderr , "[propagate] toporder botches\n" );
 297                 continue;
 298             }
 299         }
 300         if ( childp -> npropcall == 0 ) {
 301             continue;
 302         }
 303             /*
 304              *  distribute time for this arc
 305              */
 306         arcp -> arc_time = childp -> time
 307                                 * ( ( (double) arcp -> arc_count ) /
 308                                     ( (double) childp -> npropcall ) );
 309         arcp -> arc_childtime = childp -> childtime
 310                                 * ( ( (double) arcp -> arc_count ) /
 311                                     ( (double) childp -> npropcall ) );
 312         share = arcp -> arc_time + arcp -> arc_childtime;
 313         parentp -> childtime += share;
 314             /*
 315              *  ( 1 - propfraction ) gets lost along the way
 316              */
 317         propshare = parentp -> propfraction * share;
 318             /*
 319              *  fix things for printing
 320              */
 321         parentp -> propchild += propshare;
 322         arcp -> arc_time *= parentp -> propfraction;
 323         arcp -> arc_childtime *= parentp -> propfraction;
 324             /*
 325              *  add this share to the parent's cycle header, if any.
 326              */
 327         if ( parentp -> cyclehead != parentp ) {
 328             parentp -> cyclehead -> childtime += share;
 329             parentp -> cyclehead -> propchild += propshare;
 330         }
 331 #       ifdef DEBUG
 332             if ( debug & PROPDEBUG ) {
 333                 printf( "[dotime] child \t" );
 334                 printname( childp );
 335                 printf( " with %f %f %d/%d\n" ,
 336                         childp -> time , childp -> childtime ,
 337                         arcp -> arc_count , childp -> npropcall );
 338                 printf( "[dotime] parent\t" );
 339                 printname( parentp );
 340                 printf( "\n[dotime] share %f\n" , share );
 341             }
 342 #       endif /* DEBUG */
 343     }
 344 }
 345
 346 cyclelink(void)
 347 {
 348     nltype      *nlp;
 349     nltype      *cyclenlp;
 350     int                 cycle;
 351     nltype              *memberp;
 352     arctype             *arcp;
 353
 354         /*
 355          *      Count the number of cycles, and initialze the cycle lists
 356          */
 357     ncycle = 0;
 358     for ( nlp = nl ; nlp < npe ; nlp++ ) {
 359             /*
 360              *  this is how you find unattached cycles
 361              */
 362         if ( nlp -> cyclehead == nlp && nlp -> cnext != 0 ) {
 363             ncycle += 1;
 364         }
 365     }
 366         /*
 367          *      cyclenl is indexed by cycle number:
 368          *      i.e. it is origin 1, not origin 0.
 369          */
 370     cyclenl = (nltype *) calloc( ncycle + 1 , sizeof( nltype ) );
 371     if ( cyclenl == 0 ) {
 372         warnx("no room for %d bytes of cycle headers",
 373                    ( ncycle + 1 ) * sizeof( nltype ) );
 374         done();
 375     }
 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 cycleanalyze(void)
 441 {
 442     arctype     **cyclestack;
 443     arctype     **stkp;
 444     arctype     **arcpp;
 445     arctype     **endlist;
 446     arctype     *arcp;
 447     nltype      *nlp;
 448     cltype      *clp;
 449     bool        ret;
 450     bool        done;
 451     int         size;
 452     int         cycleno;
 453
 454         /*
 455          *      calculate the size of the cycle, and find nodes that
 456          *      exit the cycle as they are desirable targets to cut
 457          *      some of their parents
 458          */
 459     for ( done = TRUE , cycleno = 1 ; cycleno <= ncycle ; cycleno++ ) {
 460         size = 0;
 461         for (nlp = cyclenl[ cycleno ] . cnext; nlp; nlp = nlp -> cnext) {
 462             size += 1;
 463             nlp -> parentcnt = 0;
 464             nlp -> flags &= ~HASCYCLEXIT;
 465             for ( arcp = nlp -> parents; arcp; arcp = arcp -> arc_parentlist ) {
 466                 nlp -> parentcnt += 1;
 467                 if ( arcp -> arc_parentp -> cycleno != cycleno )
 468                     nlp -> flags |= HASCYCLEXIT;
 469             }
 470         }
 471         if ( size <= cyclethreshold )
 472             continue;
 473         done = FALSE;
 474         cyclestack = (arctype **) calloc( size + 1 , sizeof( arctype *) );
 475         if ( cyclestack == 0 ) {
 476             warnx("no room for %d bytes of cycle stack",
 477                            ( size + 1 ) * sizeof( arctype * ) );
 478             return;
 479         }
 480 #       ifdef DEBUG
 481             if ( debug & BREAKCYCLE ) {
 482                 printf( "[cycleanalyze] starting cycle %d of %d, size %d\n" ,
 483                     cycleno , ncycle , size );
 484             }
 485 #       endif /* DEBUG */
 486         for ( nlp = cyclenl[ cycleno ] . cnext ; nlp ; nlp = nlp -> cnext ) {
 487             stkp = &cyclestack[0];
 488             nlp -> flags |= CYCLEHEAD;
 489             ret = descend ( nlp , cyclestack , stkp );
 490             nlp -> flags &= ~CYCLEHEAD;
 491             if ( ret == FALSE )
 492                 break;
 493         }
 494         free( cyclestack );
 495         if ( cyclecnt > 0 ) {
 496             compresslist();
 497             for ( clp = cyclehead ; clp ; ) {
 498                 endlist = &clp -> list[ clp -> size ];
 499                 for ( arcpp = clp -> list ; arcpp < endlist ; arcpp++ )
 500                     (*arcpp) -> arc_cyclecnt--;
 501                 cyclecnt--;
 502                 clp = clp -> next;
 503                 free( clp );
 504             }
 505             cyclehead = 0;
 506         }
 507     }
 508 #   ifdef DEBUG
 509         if ( debug & BREAKCYCLE ) {
 510             printf("%s visited %d, viable %d, newcycle %d, oldcycle %d\n",
 511                 "[doarcs]" , visited , viable , newcycle , oldcycle);
 512         }
 513 #   endif /* DEBUG */
 514     return( done );
 515 }
 516
 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 }
 546
 547 addcycle(arctype **stkstart, arctype **stkend)
 548 {
 549     arctype     **arcpp;
 550     arctype     **stkloc;
 551     arctype     **stkp;
 552     arctype     **endlist;
 553     arctype     *minarc;
 554     arctype     *arcp;
 555     cltype      *clp;
 556     int         size;
 557
 558     size = stkend - stkstart + 1;
 559     if ( size <= 1 )
 560         return( TRUE );
 561     for ( arcpp = stkstart , minarc = *arcpp ; arcpp <= stkend ; arcpp++ ) {
 562         if ( *arcpp > minarc )
 563             continue;
 564         minarc = *arcpp;
 565         stkloc = arcpp;
 566     }
 567     for ( clp = cyclehead ; clp ; clp = clp -> next ) {
 568         if ( clp -> size != size )
 569             continue;
 570         stkp = stkloc;
 571         endlist = &clp -> list[ size ];
 572         for ( arcpp = clp -> list ; arcpp < endlist ; arcpp++ ) {
 573             if ( *stkp++ != *arcpp )
 574                 break;
 575             if ( stkp > stkend )
 576                 stkp = stkstart;
 577         }
 578         if ( arcpp == endlist ) {
 579 #           ifdef DEBUG
 580                 oldcycle++;
 581 #           endif /* DEBUG */
 582             return( TRUE );
 583         }
 584     }
 585     clp = (cltype *)
 586         calloc( 1 , sizeof ( cltype ) + ( size - 1 ) * sizeof( arctype * ) );
 587     if ( clp == 0 ) {
 588         warnx("no room for %d bytes of subcycle storage",
 589             sizeof ( cltype ) + ( size - 1 ) * sizeof( arctype * ) );
 590         return( FALSE );
 591     }
 592     stkp = stkloc;
 593     endlist = &clp -> list[ size ];
 594     for ( arcpp = clp -> list ; arcpp < endlist ; arcpp++ ) {
 595         arcp = *arcpp = *stkp++;
 596         if ( stkp > stkend )
 597             stkp = stkstart;
 598         arcp -> arc_cyclecnt++;
 599         if ( ( arcp -> arc_flags & ONLIST ) == 0 ) {
 600             arcp -> arc_flags |= ONLIST;
 601             arcp -> arc_next = archead;
 602             archead = arcp;
 603         }
 604     }
 605     clp -> size = size;
 606     clp -> next = cyclehead;
 607     cyclehead = clp;
 608 #   ifdef DEBUG
 609         newcycle++;
 610         if ( debug & SUBCYCLELIST ) {
 611             printsubcycle( clp );
 612         }
 613 #   endif /* DEBUG */
 614     cyclecnt++;
 615     if ( cyclecnt >= CYCLEMAX )
 616         return( FALSE );
 617     return( TRUE );
 618 }
 619
 620 compresslist(void)
 621 {
 622     cltype      *clp;
 623     cltype      **prev;
 624     arctype     **arcpp;
 625     arctype     **endlist;
 626     arctype     *arcp;
 627     arctype     *maxarcp;
 628     arctype     *maxexitarcp;
 629     arctype     *maxwithparentarcp;
 630     arctype     *maxnoparentarcp;
 631     int         maxexitcnt;
 632     int         maxwithparentcnt;
 633     int         maxnoparentcnt;
 634
 635     maxexitcnt = 0;
 636     maxwithparentcnt = 0;
 637     maxnoparentcnt = 0;
 638     for ( endlist = &archead , arcp = archead ; arcp ; ) {
 639         if ( arcp -> arc_cyclecnt == 0 ) {
 640             arcp -> arc_flags &= ~ONLIST;
 641             *endlist = arcp -> arc_next;
 642             arcp -> arc_next = 0;
 643             arcp = *endlist;
 644             continue;
 645         }
 646         if ( arcp -> arc_childp -> flags & HASCYCLEXIT ) {
 647             if ( arcp -> arc_cyclecnt > maxexitcnt ||
 648                 ( arcp -> arc_cyclecnt == maxexitcnt &&
 649                 arcp -> arc_cyclecnt < maxexitarcp -> arc_count ) ) {
 650                 maxexitcnt = arcp -> arc_cyclecnt;
 651                 maxexitarcp = arcp;
 652             }
 653         } else if ( arcp -> arc_childp -> parentcnt > 1 ) {
 654             if ( arcp -> arc_cyclecnt > maxwithparentcnt ||
 655                 ( arcp -> arc_cyclecnt == maxwithparentcnt &&
 656                 arcp -> arc_cyclecnt < maxwithparentarcp -> arc_count ) ) {
 657                 maxwithparentcnt = arcp -> arc_cyclecnt;
 658                 maxwithparentarcp = arcp;
 659             }
 660         } else {
 661             if ( arcp -> arc_cyclecnt > maxnoparentcnt ||
 662                 ( arcp -> arc_cyclecnt == maxnoparentcnt &&
 663                 arcp -> arc_cyclecnt < maxnoparentarcp -> arc_count ) ) {
 664                 maxnoparentcnt = arcp -> arc_cyclecnt;
 665                 maxnoparentarcp = arcp;
 666             }
 667         }
 668         endlist = &arcp -> arc_next;
 669         arcp = arcp -> arc_next;
 670     }
 671     if ( maxexitcnt > 0 ) {
 672         /*
 673          *      first choice is edge leading to node with out-of-cycle parent
 674          */
 675         maxarcp = maxexitarcp;
 676 #       ifdef DEBUG
 677             type = "exit";
 678 #       endif /* DEBUG */
 679     } else if ( maxwithparentcnt > 0 ) {
 680         /*
 681          *      second choice is edge leading to node with at least one
 682          *      other in-cycle parent
 683          */
 684         maxarcp = maxwithparentarcp;
 685 #       ifdef DEBUG
 686             type = "internal";
 687 #       endif /* DEBUG */
 688     } else {
 689         /*
 690          *      last choice is edge leading to node with only this arc as
 691          *      a parent (as it will now be orphaned)
 692          */
 693         maxarcp = maxnoparentarcp;
 694 #       ifdef DEBUG
 695             type = "orphan";
 696 #       endif /* DEBUG */
 697     }
 698     maxarcp -> arc_flags |= DEADARC;
 699     maxarcp -> arc_childp -> parentcnt -= 1;
 700     maxarcp -> arc_childp -> npropcall -= maxarcp -> arc_count;
 701 #   ifdef DEBUG
 702         if ( debug & BREAKCYCLE ) {
 703             printf( "%s delete %s arc: %s (%d) -> %s from %d cycle(s)\n" ,
 704                 "[compresslist]" , type , maxarcp -> arc_parentp -> name ,
 705                 maxarcp -> arc_count , maxarcp -> arc_childp -> name ,
 706                 maxarcp -> arc_cyclecnt );
 707         }
 708 #   endif /* DEBUG */
 709     printf( "\t%s to %s with %d calls\n" , maxarcp -> arc_parentp -> name ,
 710         maxarcp -> arc_childp -> name , maxarcp -> arc_count );
 711     prev = &cyclehead;
 712     for ( clp = cyclehead ; clp ; ) {
 713         endlist = &clp -> list[ clp -> size ];
 714         for ( arcpp = clp -> list ; arcpp < endlist ; arcpp++ )
 715             if ( (*arcpp) -> arc_flags & DEADARC )
 716                 break;
 717         if ( arcpp == endlist ) {
 718             prev = &clp -> next;
 719             clp = clp -> next;
 720             continue;
 721         }
 722         for ( arcpp = clp -> list ; arcpp < endlist ; arcpp++ )
 723             (*arcpp) -> arc_cyclecnt--;
 724         cyclecnt--;
 725         *prev = clp -> next;
 726         clp = clp -> next;
 727         free( clp );
 728     }
 729 }
 730
 731 #ifdef DEBUG
 732 printsubcycle(cltype *clp)
 733 {
 734     arctype     **arcpp;
 735     arctype     **endlist;
 736
 737     arcpp = clp -> list;
 738     printf( "%s <cycle %d>\n" , (*arcpp) -> arc_parentp -> name ,
 739         (*arcpp) -> arc_parentp -> cycleno ) ;
 740     for ( endlist = &clp -> list[ clp -> size ]; arcpp < endlist ; arcpp++ )
 741         printf( "\t(%d) -> %s\n" , (*arcpp) -> arc_count ,
 742             (*arcpp) -> arc_childp -> name ) ;
 743 }
 744 #endif /* DEBUG */
 745
 746 cycletime(void)
 747 {
 748     int                 cycle;
 749     nltype              *cyclenlp;
 750     nltype              *childp;
 751
 752     for ( cycle = 1 ; cycle <= ncycle ; cycle += 1 ) {
 753         cyclenlp = &cyclenl[ cycle ];
 754         for ( childp = cyclenlp -> cnext ; childp ; childp = childp -> cnext ) {
 755             if ( childp -> propfraction == 0.0 ) {
 756                     /*
 757                      * all members have the same propfraction except those
 758                      *  that were excluded with -E
 759                      */
 760                 continue;
 761             }
 762             cyclenlp -> time += childp -> time;
 763         }
 764         cyclenlp -> propself = cyclenlp -> propfraction * cyclenlp -> time;
 765     }
 766 }
 767
 768     /*
 769      *  in one top to bottom pass over the topologically sorted namelist
 770      *  propagate:
 771      *          printflag as the union of parents' printflags
 772      *          propfraction as the sum of fractional parents' propfractions
 773      *  and while we're here, sum time for functions.
 774      */
 775 doflags(void)
 776 {
 777     int         index;
 778     nltype      *childp;
 779     nltype      *oldhead;
 780
 781     oldhead = 0;
 782     for ( index = nname-1 ; index >= 0 ; index -= 1 ) {
 783         childp = topsortnlp[ index ];
 784             /*
 785              *  if we haven't done this function or cycle,
 786              *  inherit things from parent.
 787              *  this way, we are linear in the number of arcs
 788              *  since we do all members of a cycle (and the cycle itself)
 789              *  as we hit the first member of the cycle.
 790              */
 791         if ( childp -> cyclehead != oldhead ) {
 792             oldhead = childp -> cyclehead;
 793             inheritflags( childp );
 794         }
 795 #       ifdef DEBUG
 796             if ( debug & PROPDEBUG ) {
 797                 printf( "[doflags] " );
 798                 printname( childp );
 799                 printf( " inherits printflag %d and propfraction %f\n" ,
 800                         childp -> printflag , childp -> propfraction );
 801             }
 802 #       endif /* DEBUG */
 803         if ( ! childp -> printflag ) {
 804                 /*
 805                  *      printflag is off
 806                  *      it gets turned on by
 807                  *      being on -f list,
 808                  *      or there not being any -f list and not being on -e list.
 809                  */
 810             if (   onlist( flist , childp -> name )
 811                 || ( !fflag && !onlist( elist , childp -> name ) ) ) {
 812                 childp -> printflag = TRUE;
 813             }
 814         } else {
 815                 /*
 816                  *      this function has printing parents:
 817                  *      maybe someone wants to shut it up
 818                  *      by putting it on -e list.  (but favor -f over -e)
 819                  */
 820             if (  ( !onlist( flist , childp -> name ) )
 821                 && onlist( elist , childp -> name ) ) {
 822                 childp -> printflag = FALSE;
 823             }
 824         }
 825         if ( childp -> propfraction == 0.0 ) {
 826                 /*
 827                  *      no parents to pass time to.
 828                  *      collect time from children if
 829                  *      its on -F list,
 830                  *      or there isn't any -F list and its not on -E list.
 831                  */
 832             if ( onlist( Flist , childp -> name )
 833                 || ( !Fflag && !onlist( Elist , childp -> name ) ) ) {
 834                     childp -> propfraction = 1.0;
 835             }
 836         } else {
 837                 /*
 838                  *      it has parents to pass time to,
 839                  *      but maybe someone wants to shut it up
 840                  *      by puttting it on -E list.  (but favor -F over -E)
 841                  */
 842             if (  !onlist( Flist , childp -> name )
 843                 && onlist( Elist , childp -> name ) ) {
 844                 childp -> propfraction = 0.0;
 845             }
 846         }
 847         childp -> propself = childp -> time * childp -> propfraction;
 848         printtime += childp -> propself;
 849 #       ifdef DEBUG
 850             if ( debug & PROPDEBUG ) {
 851                 printf( "[doflags] " );
 852                 printname( childp );
 853                 printf( " ends up with printflag %d and propfraction %f\n" ,
 854                         childp -> printflag , childp -> propfraction );
 855                 printf( "time %f propself %f printtime %f\n" ,
 856                         childp -> time , childp -> propself , printtime );
 857             }
 858 #       endif /* DEBUG */
 859     }
 860 }
 861
 862     /*
 863      *  check if any parent of this child
 864      *  (or outside parents of this cycle)
 865      *  have their print flags on and set the
 866      *  print flag of the child (cycle) appropriately.
 867      *  similarly, deal with propagation fractions from parents.
 868      */
 869 inheritflags(nltype *childp)
 870 {
 871     nltype      *headp;
 872     arctype     *arcp;
 873     nltype      *parentp;
 874     nltype      *memp;
 875
 876     headp = childp -> cyclehead;
 877     if ( childp == headp ) {
 878             /*
 879              *  just a regular child, check its parents
 880              */
 881         childp -> printflag = FALSE;
 882         childp -> propfraction = 0.0;
 883         for (arcp = childp -> parents ; arcp ; arcp = arcp -> arc_parentlist) {
 884             parentp = arcp -> arc_parentp;
 885             if ( childp == parentp ) {
 886                 continue;
 887             }
 888             childp -> printflag |= parentp -> printflag;
 889                 /*
 890                  *      if the child was never actually called
 891                  *      (e.g. this arc is static (and all others are, too))
 892                  *      no time propagates along this arc.
 893                  */
 894             if ( arcp -> arc_flags & DEADARC ) {
 895                 continue;
 896             }
 897             if ( childp -> npropcall ) {
 898                 childp -> propfraction += parentp -> propfraction
 899                                         * ( ( (double) arcp -> arc_count )
 900                                           / ( (double) childp -> npropcall ) );
 901             }
 902         }
 903     } else {
 904             /*
 905              *  its a member of a cycle, look at all parents from
 906              *  outside the cycle
 907              */
 908         headp -> printflag = FALSE;
 909         headp -> propfraction = 0.0;
 910         for ( memp = headp -> cnext ; memp ; memp = memp -> cnext ) {
 911             for (arcp = memp->parents ; arcp ; arcp = arcp->arc_parentlist) {
 912                 if ( arcp -> arc_parentp -> cyclehead == headp ) {
 913                     continue;
 914                 }
 915                 parentp = arcp -> arc_parentp;
 916                 headp -> printflag |= parentp -> printflag;
 917                     /*
 918                      *  if the cycle was never actually called
 919                      *  (e.g. this arc is static (and all others are, too))
 920                      *  no time propagates along this arc.
 921                      */
 922                 if ( arcp -> arc_flags & DEADARC ) {
 923                     continue;
 924                 }
 925                 if ( headp -> npropcall ) {
 926                     headp -> propfraction += parentp -> propfraction
 927                                         * ( ( (double) arcp -> arc_count )
 928                                           / ( (double) headp -> npropcall ) );
 929                 }
 930             }
 931         }
 932         for ( memp = headp ; memp ; memp = memp -> cnext ) {
 933             memp -> printflag = headp -> printflag;
 934             memp -> propfraction = headp -> propfraction;
 935         }
 936     }
 937 }