gprof/arcs.c

   1 /*
   2  * Copyright (c) 1983 Regents of the University of California.
   3  * All rights reserved.
   4  *
   5  * Redistribution and use in source and binary forms are permitted
   6  * provided that: (1) source distributions retain this entire copyright
   7  * notice and comment, and (2) distributions including binaries display
   8  * the following acknowledgement:  ``This product includes software
   9  * developed by the University of California, Berkeley and its contributors''
  10  * in the documentation or other materials provided with the distribution
  11  * and in all advertising materials mentioning features or use of this
  12  * software. Neither the name of the University nor the names of its
  13  * contributors may be used to endorse or promote products derived
  14  * from this software without specific prior written permission.
  15  * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR
  16  * IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED
  17  * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
  18  */
  19
  20 #ifndef lint
  21 static char sccsid[] = "@(#)arcs.c      5.6 (Berkeley) 6/1/90";
  22 #endif /* not lint */
  23
  24 #include "gprof.h"
  25
  26     /*
  27      *  add (or just increment) an arc
  28      */
  29 addarc( parentp , childp , count )
  30     nltype      *parentp;
  31     nltype      *childp;
  32     long        count;
  33 {
  34     arctype             *arcp;
  35
  36 #   ifdef DEBUG
  37         if ( debug & TALLYDEBUG ) {
  38             printf( "[addarc] %d arcs from %s to %s\n" ,
  39                     count , parentp -> name , childp -> name );
  40         }
  41 #   endif DEBUG
  42     arcp = arclookup( parentp , childp );
  43     if ( arcp != 0 ) {
  44             /*
  45              *  a hit:  just increment the count.
  46              */
  47 #       ifdef DEBUG
  48             if ( debug & TALLYDEBUG ) {
  49                 printf( "[tally] hit %d += %d\n" ,
  50                         arcp -> arc_count , count );
  51             }
  52 #       endif DEBUG
  53         arcp -> arc_count += count;
  54         return;
  55     }
  56     arcp = (arctype *) calloc( 1 , sizeof *arcp );
  57     arcp -> arc_parentp = parentp;
  58     arcp -> arc_childp = childp;
  59     arcp -> arc_count = count;
  60         /*
  61          *      prepend this child to the children of this parent
  62          */
  63     arcp -> arc_childlist = parentp -> children;
  64     parentp -> children = arcp;
  65         /*
  66          *      prepend this parent to the parents of this child
  67          */
  68     arcp -> arc_parentlist = childp -> parents;
  69     childp -> parents = arcp;
  70 }
  71
  72     /*
  73      *  the code below topologically sorts the graph (collapsing cycles),
  74      *  and propagates time bottom up and flags top down.
  75      */
  76
  77     /*
  78      *  the topologically sorted name list pointers
  79      */
  80 nltype  **topsortnlp;
  81
  82 topcmp( npp1 , npp2 )
  83     nltype      **npp1;
  84     nltype      **npp2;
  85 {
  86     return (*npp1) -> toporder - (*npp2) -> toporder;
  87 }
  88
  89 nltype **
  90 doarcs()
  91 {
  92     nltype      *parentp, **timesortnlp;
  93     arctype     *arcp;
  94     long        index;
  95
  96         /*
  97          *      initialize various things:
  98          *          zero out child times.
  99          *          count self-recursive calls.
 100          *          indicate that nothing is on cycles.
 101          */
 102     for ( parentp = nl ; parentp < npe ; parentp++ ) {
 103         parentp -> childtime = 0.0;
 104         arcp = arclookup( parentp , parentp );
 105         if ( arcp != 0 ) {
 106             parentp -> ncall -= arcp -> arc_count;
 107             parentp -> selfcalls = arcp -> arc_count;
 108         } else {
 109             parentp -> selfcalls = 0;
 110         }
 111         parentp -> propfraction = 0.0;
 112         parentp -> propself = 0.0;
 113         parentp -> propchild = 0.0;
 114         parentp -> printflag = FALSE;
 115         parentp -> toporder = DFN_NAN;
 116         parentp -> cycleno = 0;
 117         parentp -> cyclehead = parentp;
 118         parentp -> cnext = 0;
 119         if ( cflag ) {
 120             findcall( parentp , parentp -> value , (parentp+1) -> value );
 121         }
 122     }
 123         /*
 124          *      topologically order things
 125          *      if any node is unnumbered,
 126          *          number it and any of its descendents.
 127          */
 128     for ( parentp = nl ; parentp < npe ; parentp++ ) {
 129         if ( parentp -> toporder == DFN_NAN ) {
 130             dfn( parentp );
 131         }
 132     }
 133         /*
 134          *      link together nodes on the same cycle
 135          */
 136     cyclelink();
 137         /*
 138          *      Sort the symbol table in reverse topological order
 139          */
 140     topsortnlp = (nltype **) calloc( nname , sizeof(nltype *) );
 141     if ( topsortnlp == (nltype **) 0 ) {
 142         fprintf( stderr , "[doarcs] ran out of memory for topo sorting\n" );
 143     }
 144     for ( index = 0 ; index < nname ; index += 1 ) {
 145         topsortnlp[ index ] = &nl[ index ];
 146     }
 147     qsort( topsortnlp , nname , sizeof(nltype *) , topcmp );
 148 #   ifdef DEBUG
 149         if ( debug & DFNDEBUG ) {
 150             printf( "[doarcs] topological sort listing\n" );
 151             for ( index = 0 ; index < nname ; index += 1 ) {
 152                 printf( "[doarcs] " );
 153                 printf( "%d:" , topsortnlp[ index ] -> toporder );
 154                 printname( topsortnlp[ index ] );
 155                 printf( "\n" );
 156             }
 157         }
 158 #   endif DEBUG
 159         /*
 160          *      starting from the topological top,
 161          *      propagate print flags to children.
 162          *      also, calculate propagation fractions.
 163          *      this happens before time propagation
 164          *      since time propagation uses the fractions.
 165          */
 166     doflags();
 167         /*
 168          *      starting from the topological bottom,
 169          *      propogate children times up to parents.
 170          */
 171     dotime();
 172         /*
 173          *      Now, sort by propself + propchild.
 174          *      sorting both the regular function names
 175          *      and cycle headers.
 176          */
 177     timesortnlp = (nltype **) calloc( nname + ncycle , sizeof(nltype *) );
 178     if ( timesortnlp == (nltype **) 0 ) {
 179         fprintf( stderr , "%s: ran out of memory for sorting\n" , whoami );
 180     }
 181     for ( index = 0 ; index < nname ; index++ ) {
 182         timesortnlp[index] = &nl[index];
 183     }
 184     for ( index = 1 ; index <= ncycle ; index++ ) {
 185         timesortnlp[nname+index-1] = &cyclenl[index];
 186     }
 187     qsort( timesortnlp , nname + ncycle , sizeof(nltype *) , totalcmp );
 188     for ( index = 0 ; index < nname + ncycle ; index++ ) {
 189         timesortnlp[ index ] -> index = index + 1;
 190     }
 191     return( timesortnlp );
 192 }
 193
 194 dotime()
 195 {
 196     int index;
 197
 198     cycletime();
 199     for ( index = 0 ; index < nname ; index += 1 ) {
 200         timepropagate( topsortnlp[ index ] );
 201     }
 202 }
 203
 204 timepropagate( parentp )
 205     nltype      *parentp;
 206 {
 207     arctype     *arcp;
 208     nltype      *childp;
 209     double      share;
 210     double      propshare;
 211
 212     if ( parentp -> propfraction == 0.0 ) {
 213         return;
 214     }
 215         /*
 216          *      gather time from children of this parent.
 217          */
 218     for ( arcp = parentp -> children ; arcp ; arcp = arcp -> arc_childlist ) {
 219         childp = arcp -> arc_childp;
 220         if ( arcp -> arc_count == 0 ) {
 221             continue;
 222         }
 223         if ( childp == parentp ) {
 224             continue;
 225         }
 226         if ( childp -> propfraction == 0.0 ) {
 227             continue;
 228         }
 229         if ( childp -> cyclehead != childp ) {
 230             if ( parentp -> cycleno == childp -> cycleno ) {
 231                 continue;
 232             }
 233             if ( parentp -> toporder <= childp -> toporder ) {
 234                 fprintf( stderr , "[propagate] toporder botches\n" );
 235             }
 236             childp = childp -> cyclehead;
 237         } else {
 238             if ( parentp -> toporder <= childp -> toporder ) {
 239                 fprintf( stderr , "[propagate] toporder botches\n" );
 240                 continue;
 241             }
 242         }
 243         if ( childp -> ncall == 0 ) {
 244             continue;
 245         }
 246             /*
 247              *  distribute time for this arc
 248              */
 249         arcp -> arc_time = childp -> time
 250                                 * ( ( (double) arcp -> arc_count ) /
 251                                     ( (double) childp -> ncall ) );
 252         arcp -> arc_childtime = childp -> childtime
 253                                 * ( ( (double) arcp -> arc_count ) /
 254                                     ( (double) childp -> ncall ) );
 255         share = arcp -> arc_time + arcp -> arc_childtime;
 256         parentp -> childtime += share;
 257             /*
 258              *  ( 1 - propfraction ) gets lost along the way
 259              */
 260         propshare = parentp -> propfraction * share;
 261             /*
 262              *  fix things for printing
 263              */
 264         parentp -> propchild += propshare;
 265         arcp -> arc_time *= parentp -> propfraction;
 266         arcp -> arc_childtime *= parentp -> propfraction;
 267             /*
 268              *  add this share to the parent's cycle header, if any.
 269              */
 270         if ( parentp -> cyclehead != parentp ) {
 271             parentp -> cyclehead -> childtime += share;
 272             parentp -> cyclehead -> propchild += propshare;
 273         }
 274 #       ifdef DEBUG
 275             if ( debug & PROPDEBUG ) {
 276                 printf( "[dotime] child \t" );
 277                 printname( childp );
 278                 printf( " with %f %f %d/%d\n" ,
 279                         childp -> time , childp -> childtime ,
 280                         arcp -> arc_count , childp -> ncall );
 281                 printf( "[dotime] parent\t" );
 282                 printname( parentp );
 283                 printf( "\n[dotime] share %f\n" , share );
 284             }
 285 #       endif DEBUG
 286     }
 287 }
 288
 289 cyclelink()
 290 {
 291     register nltype     *nlp;
 292     register nltype     *cyclenlp;
 293     int                 cycle;
 294     nltype              *memberp;
 295     arctype             *arcp;
 296
 297         /*
 298          *      Count the number of cycles, and initialze the cycle lists
 299          */
 300     ncycle = 0;
 301     for ( nlp = nl ; nlp < npe ; nlp++ ) {
 302             /*
 303              *  this is how you find unattached cycles
 304              */
 305         if ( nlp -> cyclehead == nlp && nlp -> cnext != 0 ) {
 306             ncycle += 1;
 307         }
 308     }
 309         /*
 310          *      cyclenl is indexed by cycle number:
 311          *      i.e. it is origin 1, not origin 0.
 312          */
 313     cyclenl = (nltype *) calloc( ncycle + 1 , sizeof( nltype ) );
 314     if ( cyclenl == 0 ) {
 315         fprintf( stderr , "%s: No room for %d bytes of cycle headers\n" ,
 316                 whoami , ( ncycle + 1 ) * sizeof( nltype ) );
 317         done();
 318     }
 319         /*
 320          *      now link cycles to true cycleheads,
 321          *      number them, accumulate the data for the cycle
 322          */
 323     cycle = 0;
 324     for ( nlp = nl ; nlp < npe ; nlp++ ) {
 325         if ( !( nlp -> cyclehead == nlp && nlp -> cnext != 0 ) ) {
 326             continue;
 327         }
 328         cycle += 1;
 329         cyclenlp = &cyclenl[cycle];
 330         cyclenlp -> name = 0;           /* the name */
 331         cyclenlp -> value = 0;          /* the pc entry point */
 332         cyclenlp -> time = 0.0;         /* ticks in this routine */
 333         cyclenlp -> childtime = 0.0;    /* cumulative ticks in children */
 334         cyclenlp -> ncall = 0;          /* how many times called */
 335         cyclenlp -> selfcalls = 0;      /* how many calls to self */
 336         cyclenlp -> propfraction = 0.0; /* what % of time propagates */
 337         cyclenlp -> propself = 0.0;     /* how much self time propagates */
 338         cyclenlp -> propchild = 0.0;    /* how much child time propagates */
 339         cyclenlp -> printflag = TRUE;   /* should this be printed? */
 340         cyclenlp -> index = 0;          /* index in the graph list */
 341         cyclenlp -> toporder = DFN_NAN; /* graph call chain top-sort order */
 342         cyclenlp -> cycleno = cycle;    /* internal number of cycle on */
 343         cyclenlp -> cyclehead = cyclenlp;       /* pointer to head of cycle */
 344         cyclenlp -> cnext = nlp;        /* pointer to next member of cycle */
 345         cyclenlp -> parents = 0;        /* list of caller arcs */
 346         cyclenlp -> children = 0;       /* list of callee arcs */
 347 #       ifdef DEBUG
 348             if ( debug & CYCLEDEBUG ) {
 349                 printf( "[cyclelink] " );
 350                 printname( nlp );
 351                 printf( " is the head of cycle %d\n" , cycle );
 352             }
 353 #       endif DEBUG
 354             /*
 355              *  link members to cycle header
 356              */
 357         for ( memberp = nlp ; memberp ; memberp = memberp -> cnext ) {
 358             memberp -> cycleno = cycle;
 359             memberp -> cyclehead = cyclenlp;
 360         }
 361             /*
 362              *  count calls from outside the cycle
 363              *  and those among cycle members
 364              */
 365         for ( memberp = nlp ; memberp ; memberp = memberp -> cnext ) {
 366             for ( arcp=memberp->parents ; arcp ; arcp=arcp->arc_parentlist ) {
 367                 if ( arcp -> arc_parentp == memberp ) {
 368                     continue;
 369                 }
 370                 if ( arcp -> arc_parentp -> cycleno == cycle ) {
 371                     cyclenlp -> selfcalls += arcp -> arc_count;
 372                 } else {
 373                     cyclenlp -> ncall += arcp -> arc_count;
 374                 }
 375             }
 376         }
 377     }
 378 }
 379
 380 cycletime()
 381 {
 382     int                 cycle;
 383     nltype              *cyclenlp;
 384     nltype              *childp;
 385
 386     for ( cycle = 1 ; cycle <= ncycle ; cycle += 1 ) {
 387         cyclenlp = &cyclenl[ cycle ];
 388         for ( childp = cyclenlp -> cnext ; childp ; childp = childp -> cnext ) {
 389             if ( childp -> propfraction == 0.0 ) {
 390                     /*
 391                      * all members have the same propfraction except those
 392                      *  that were excluded with -E
 393                      */
 394                 continue;
 395             }
 396             cyclenlp -> time += childp -> time;
 397         }
 398         cyclenlp -> propself = cyclenlp -> propfraction * cyclenlp -> time;
 399     }
 400 }
 401
 402     /*
 403      *  in one top to bottom pass over the topologically sorted namelist
 404      *  propagate:
 405      *          printflag as the union of parents' printflags
 406      *          propfraction as the sum of fractional parents' propfractions
 407      *  and while we're here, sum time for functions.
 408      */
 409 doflags()
 410 {
 411     int         index;
 412     nltype      *childp;
 413     nltype      *oldhead;
 414
 415     oldhead = 0;
 416     for ( index = nname-1 ; index >= 0 ; index -= 1 ) {
 417         childp = topsortnlp[ index ];
 418             /*
 419              *  if we haven't done this function or cycle,
 420              *  inherit things from parent.
 421              *  this way, we are linear in the number of arcs
 422              *  since we do all members of a cycle (and the cycle itself)
 423              *  as we hit the first member of the cycle.
 424              */
 425         if ( childp -> cyclehead != oldhead ) {
 426             oldhead = childp -> cyclehead;
 427             inheritflags( childp );
 428         }
 429 #       ifdef DEBUG
 430             if ( debug & PROPDEBUG ) {
 431                 printf( "[doflags] " );
 432                 printname( childp );
 433                 printf( " inherits printflag %d and propfraction %f\n" ,
 434                         childp -> printflag , childp -> propfraction );
 435             }
 436 #       endif DEBUG
 437         if ( ! childp -> printflag ) {
 438                 /*
 439                  *      printflag is off
 440                  *      it gets turned on by
 441                  *      being on -f list,
 442                  *      or there not being any -f list and not being on -e list.
 443                  */
 444             if (   onlist( flist , childp -> name )
 445                 || ( !fflag && !onlist( elist , childp -> name ) ) ) {
 446                 childp -> printflag = TRUE;
 447             }
 448         } else {
 449                 /*
 450                  *      this function has printing parents:
 451                  *      maybe someone wants to shut it up
 452                  *      by putting it on -e list.  (but favor -f over -e)
 453                  */
 454             if (  ( !onlist( flist , childp -> name ) )
 455                 && onlist( elist , childp -> name ) ) {
 456                 childp -> printflag = FALSE;
 457             }
 458         }
 459         if ( childp -> propfraction == 0.0 ) {
 460                 /*
 461                  *      no parents to pass time to.
 462                  *      collect time from children if
 463                  *      its on -F list,
 464                  *      or there isn't any -F list and its not on -E list.
 465                  */
 466             if ( onlist( Flist , childp -> name )
 467                 || ( !Fflag && !onlist( Elist , childp -> name ) ) ) {
 468                     childp -> propfraction = 1.0;
 469             }
 470         } else {
 471                 /*
 472                  *      it has parents to pass time to,
 473                  *      but maybe someone wants to shut it up
 474                  *      by puttting it on -E list.  (but favor -F over -E)
 475                  */
 476             if (  !onlist( Flist , childp -> name )
 477                 && onlist( Elist , childp -> name ) ) {
 478                 childp -> propfraction = 0.0;
 479             }
 480         }
 481         childp -> propself = childp -> time * childp -> propfraction;
 482         printtime += childp -> propself;
 483 #       ifdef DEBUG
 484             if ( debug & PROPDEBUG ) {
 485                 printf( "[doflags] " );
 486                 printname( childp );
 487                 printf( " ends up with printflag %d and propfraction %f\n" ,
 488                         childp -> printflag , childp -> propfraction );
 489                 printf( "time %f propself %f printtime %f\n" ,
 490                         childp -> time , childp -> propself , printtime );
 491             }
 492 #       endif DEBUG
 493     }
 494 }
 495
 496     /*
 497      *  check if any parent of this child
 498      *  (or outside parents of this cycle)
 499      *  have their print flags on and set the
 500      *  print flag of the child (cycle) appropriately.
 501      *  similarly, deal with propagation fractions from parents.
 502      */
 503 inheritflags( childp )
 504     nltype      *childp;
 505 {
 506     nltype      *headp;
 507     arctype     *arcp;
 508     nltype      *parentp;
 509     nltype      *memp;
 510
 511     headp = childp -> cyclehead;
 512     if ( childp == headp ) {
 513             /*
 514              *  just a regular child, check its parents
 515              */
 516         childp -> printflag = FALSE;
 517         childp -> propfraction = 0.0;
 518         for (arcp = childp -> parents ; arcp ; arcp = arcp -> arc_parentlist) {
 519             parentp = arcp -> arc_parentp;
 520             if ( childp == parentp ) {
 521                 continue;
 522             }
 523             childp -> printflag |= parentp -> printflag;
 524                 /*
 525                  *      if the child was never actually called
 526                  *      (e.g. this arc is static (and all others are, too))
 527                  *      no time propagates along this arc.
 528                  */
 529             if ( childp -> ncall ) {
 530                 childp -> propfraction += parentp -> propfraction
 531                                             * ( ( (double) arcp -> arc_count )
 532                                               / ( (double) childp -> ncall ) );
 533             }
 534         }
 535     } else {
 536             /*
 537              *  its a member of a cycle, look at all parents from
 538              *  outside the cycle
 539              */
 540         headp -> printflag = FALSE;
 541         headp -> propfraction = 0.0;
 542         for ( memp = headp -> cnext ; memp ; memp = memp -> cnext ) {
 543             for (arcp = memp->parents ; arcp ; arcp = arcp->arc_parentlist) {
 544                 if ( arcp -> arc_parentp -> cyclehead == headp ) {
 545                     continue;
 546                 }
 547                 parentp = arcp -> arc_parentp;
 548                 headp -> printflag |= parentp -> printflag;
 549                     /*
 550                      *  if the cycle was never actually called
 551                      *  (e.g. this arc is static (and all others are, too))
 552                      *  no time propagates along this arc.
 553                      */
 554                 if ( headp -> ncall ) {
 555                     headp -> propfraction += parentp -> propfraction
 556                                             * ( ( (double) arcp -> arc_count )
 557                                               / ( (double) headp -> ncall ) );
 558                 }
 559             }
 560         }
 561         for ( memp = headp ; memp ; memp = memp -> cnext ) {
 562             memp -> printflag = headp -> printflag;
 563             memp -> propfraction = headp -> propfraction;
 564         }
 565     }
 566 }