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