fixed a bug in multi-subscript calculation

[unix-history] / usr / src / usr.bin / gprof / arcs.c

diff --git a/usr/src/usr.bin/gprof/arcs.c b/usr/src/usr.bin/gprof/arcs.c
index 450a48a..dd3118d 100644 (file)
--- a/usr/src/usr.bin/gprof/arcs.c
+++ b/usr/src/usr.bin/gprof/arcs.c
@@ -1,5 +1,5 @@
 #ifndef lint
 #ifndef lint

-    static     char *sccsid = "@(#)arcs.c      1.3 (Berkeley) %G%";
+    static     char *sccsid = "@(#)arcs.c      1.13 (Berkeley) %G%";

 #endif lint
 
 #include "gprof.h"
 #endif lint
 
 #include "gprof.h"


@@ -12,7 +12,7 @@ addarc( parentp , childp , count )
     nltype     *childp;
     long       count;
 {
     nltype     *childp;
     long       count;
 {

-    arctype            *malloc();
+    arctype            *calloc();

     arctype            *arcp;
 
 #   ifdef DEBUG
     arctype            *arcp;
 
 #   ifdef DEBUG


@@ -35,7 +35,7 @@ addarc( parentp , childp , count )
        arcp -> arc_count += count;
        return;
     }
        arcp -> arc_count += count;
        return;
     }

-    arcp = malloc( sizeof *arcp );
+    arcp = calloc( 1 , sizeof *arcp );

     arcp -> arc_parentp = parentp;
     arcp -> arc_childp = childp;
     arcp -> arc_count = count;
     arcp -> arc_parentp = parentp;
     arcp -> arc_childp = childp;
     arcp -> arc_count = count;


@@ -51,48 +51,28 @@ addarc( parentp , childp , count )
     childp -> parents = arcp;
 }
 
     childp -> parents = arcp;
 }
 

-topcmp( npp1 , npp2 )
-    nltype     **npp1;
-    nltype     **npp2;
-{
-    return (*npp1) -> toporder - (*npp2) -> toporder;
-}
+    /*
+     * the code below topologically sorts the graph (collapsing cycles),
+     * and propagates time bottom up and flags top down.
+     */

 
     /*
 
     /*

-     * sort by decreasing total time (time+childtime)
-     * if times are equal, but one is a cycle header,
-     * say that's first (e.g. less)
+     * the topologically sorted name list pointers

      */
      */

-int
-totalcmp( npp1 , npp2 )
+nltype **topsortnlp;
+
+topcmp( npp1 , npp2 )

     nltype     **npp1;
     nltype     **npp2;
 {
     nltype     **npp1;
     nltype     **npp2;
 {

-    register nltype    *np1 = *npp1;
-    register nltype    *np2 = *npp2;
-    double             diff;
-
-    diff =    ( np1 -> time + np1 -> childtime )
-           - ( np2 -> time + np2 -> childtime );
-    if ( diff < 0.0 )
-           return 1;
-    if ( diff > 0.0 )
-           return -1;
-    if ( np1 -> name == 0 && np1 -> cycleno != 0 ) 
-       return -1;
-    if ( np2 -> name == 0 && np1 -> cycleno != 0 )
-       return 1;
-    return 0;
+    return (*npp1) -> toporder - (*npp2) -> toporder;

 }
 
 doarcs()
 {
     nltype     *parentp;
     arctype    *arcp;
 }
 
 doarcs()
 {
     nltype     *parentp;
     arctype    *arcp;

-    nltype     **topsortnlp;

     long       index;
     long       index;

-    nltype     *childp;
-    double     share;

 
        /*
         *      initialize various things:
 
        /*
         *      initialize various things:


@@ -109,20 +89,25 @@ doarcs()
        } else {
            parentp -> selfcalls = 0;
        }
        } else {
            parentp -> selfcalls = 0;
        }

-       if ( cflag ) {
-           findcalls( parentp , parentp -> value , (parentp+1) -> value );
-       }
-       parentp -> toporder = 0;
+       parentp -> propfraction = 0.0;
+       parentp -> propself = 0.0;
+       parentp -> propchild = 0.0;
+       parentp -> printflag = FALSE;
+       parentp -> toporder = DFN_NAN;

        parentp -> cycleno = 0;
        parentp -> cyclehead = parentp;
        parentp -> cnext = 0;
        parentp -> cycleno = 0;
        parentp -> cyclehead = parentp;
        parentp -> cnext = 0;

+       if ( cflag ) {
+           findcalls( parentp , parentp -> value , (parentp+1) -> value );
+       }

     }
        /*
         *      topologically order things
     }
        /*
         *      topologically order things

-        *      from each of the roots of the call graph
+        *      if any node is unnumbered,
+        *          number it and any of its descendents.

         */
     for ( parentp = nl ; parentp < npe ; parentp++ ) {
         */
     for ( parentp = nl ; parentp < npe ; parentp++ ) {

-       if ( parentp -> parents == 0 ) {
+       if ( parentp -> toporder == DFN_NAN ) {

            dfn( parentp );
        }
     }
            dfn( parentp );
        }
     }


@@ -152,122 +137,146 @@ doarcs()
            }
        }
 #   endif DEBUG
            }
        }
 #   endif DEBUG

+       /*
+        *      starting from the topological top,
+        *      propagate print flags to children.
+        *      also, calculate propagation fractions.
+        *      this happens before time propagation
+        *      since time propagation uses the fractions.
+        */
+    doflags();

        /*
         *      starting from the topological bottom, 
        /*
         *      starting from the topological bottom, 

-        *      propogate children times
+        *      propogate children times up to parents.

         */
         */

+    dotime();
+    printgprof();
+}
+
+dotime()
+{
+    int        index;
+
+    cycletime();

     for ( index = 0 ; index < nname ; index += 1 ) {
     for ( index = 0 ; index < nname ; index += 1 ) {

-       parentp = topsortnlp[ index ];
-       for ( arcp = parentp->children ; arcp ; arcp = arcp->arc_childlist ) {
-           childp = arcp -> arc_childp;
-#          ifdef DEBUG
-               if ( debug & ARCDEBUG ) {
-                       printf( "[doarcs] " );
-                       printname( parentp );
-                       printf( " calls " );
-                       printname( childp );
-                       printf( " %d (%d) times\n" ,
-                               arcp -> arc_count , childp -> ncall );
-               }
-#          endif DEBUG
-           if ( arcp -> arc_count == 0 ) {
+       timepropagate( topsortnlp[ index ] );
+    }
+}
+
+timepropagate( parentp )
+    nltype     *parentp;
+{
+    arctype    *arcp;
+    nltype     *childp;
+    double     share;
+    double     propshare;
+
+    if ( parentp -> propfraction == 0.0 ) {
+       return;
+    }
+       /*
+        *      gather time from children of this parent.
+        */
+    for ( arcp = parentp -> children ; arcp ; arcp = arcp -> arc_childlist ) {
+       childp = arcp -> arc_childp;
+       if ( arcp -> arc_count == 0 ) {
+           continue;
+       }
+       if ( childp == parentp ) {
+           continue;
+       }
+       if ( childp -> propfraction == 0.0 ) {
+           continue;
+       }
+       if ( childp -> cyclehead != childp ) {
+           if ( parentp -> cycleno == childp -> cycleno ) {

                continue;
            }
                continue;
            }

-           if ( childp -> ncall == 0 ) {
-               continue;
+           if ( parentp -> toporder <= childp -> toporder ) {
+               fprintf( stderr , "[propagate] toporder botches\n" );

            }
            }

-           if ( childp == parentp ) {
+           childp = childp -> cyclehead;
+       } else {
+           if ( parentp -> toporder <= childp -> toporder ) {
+               fprintf( stderr , "[propagate] toporder botches\n" );

                continue;
            }
                continue;
            }

-           if ( childp -> cyclehead != childp ) {
-               if ( parentp -> cycleno == childp -> cycleno ) {
-                   continue;
-               }
-#              ifdef DEBUG
-                   if ( debug & ARCDEBUG ) {
-                       printf( "[doarcs]\t it's a call into cycle %d\n" ,
-                               childp -> cycleno );
-                   }
-#              endif DEBUG
-               if ( parentp -> toporder <= childp -> toporder ) {
-                   fprintf( stderr , "[doarcs] toporder botches\n" );
-               }
-               childp = childp -> cyclehead;
-           } else {
-               if ( parentp -> toporder <= childp -> toporder ) {
-                   fprintf( stderr , "[doarcs] toporder botches\n" );
-                   continue;
-               }
-           }
-               /*
-                *      distribute time for this arc
-                */
-           arcp -> arc_time = childp -> time *
-                               ( ( (double) arcp -> arc_count ) /
-                               ( (double) childp -> ncall ) );
-           arcp -> arc_childtime = childp -> childtime *
-                               ( ( (double) arcp -> arc_count ) /
-                               ( (double) childp -> ncall ) );
-           share = arcp -> arc_time + arcp -> arc_childtime;
-#          ifdef DEBUG
-               if ( debug & ARCDEBUG ) {
-                   printf( "[doarcs]\t " );
-                   printname( childp );
-                   printf( " time %8.2f + childtime %8.2f\n" ,
-                       childp -> time , childp -> childtime );
-                   printf( "[doarcs]\t this is %d arcs of the %d calls\n",
+       }
+       if ( childp -> ncall == 0 ) {
+           continue;
+       }
+           /*
+            *  distribute time for this arc
+            */
+       arcp -> arc_time = childp -> time
+                               * ( ( (double) arcp -> arc_count ) /
+                                   ( (double) childp -> ncall ) );
+       arcp -> arc_childtime = childp -> childtime
+                               * ( ( (double) arcp -> arc_count ) /
+                                   ( (double) childp -> ncall ) );
+       share = arcp -> arc_time + arcp -> arc_childtime;
+       parentp -> childtime += share;
+           /*
+            *  ( 1 - propfraction ) gets lost along the way
+            */
+       propshare = parentp -> propfraction * share;
+           /*
+            *  fix things for printing
+            */
+       parentp -> propchild += propshare;
+       arcp -> arc_time *= parentp -> propfraction;
+       arcp -> arc_childtime *= parentp -> propfraction;
+           /*
+            *  add this share to the parent's cycle header, if any.
+            */
+       if ( parentp -> cyclehead != parentp ) {
+           parentp -> cyclehead -> childtime += share;
+           parentp -> cyclehead -> propchild += propshare;
+       }
+#      ifdef DEBUG
+           if ( debug & PROPDEBUG ) {
+               printf( "[dotime] child \t" );
+               printname( childp );
+               printf( " with %f %f %d/%d\n" ,
+                       childp -> time , childp -> childtime ,

                        arcp -> arc_count , childp -> ncall );
                        arcp -> arc_count , childp -> ncall );

-                   printf( "[doarcs]\t so this gives %8.2f+%8.2f to %s\n" ,
-                       arcp -> arc_time , arcp -> arc_childtime ,
-                       parentp -> name );
-               }
-#          endif DEBUG
-           parentp -> childtime += share;
-               /*
-                *      add this share to the cycle header, if any
-                */
-           if ( parentp -> cyclehead != parentp ) {
-#              ifdef DEBUG
-                   if ( debug & ARCDEBUG ) {
-                       printf( "[doarcs]\t and to cycle %d\n" ,
-                               parentp -> cycleno );
-                   }
-#              endif DEBUG
-               parentp -> cyclehead -> childtime += share;
+               printf( "[dotime] parent\t" );
+               printname( parentp );
+               printf( "\n[dotime] share %f\n" , share );

            }
            }

-       }
+#      endif DEBUG

     }
     }

-    printgprof();

 }
 
 cyclelink()
 {
     register nltype    *nlp;
 }
 
 cyclelink()
 {
     register nltype    *nlp;

-    register nltype    *parentp;
-    register nltype    *childp;

     register nltype    *cyclenlp;
     int                        cycle;
     register nltype    *cyclenlp;
     int                        cycle;

+    nltype             *memberp;

     arctype            *arcp;
     arctype            *arcp;

-    long               ncall;
-    double             time;
-    long               callsamong;

 
        /*
         *      Count the number of cycles, and initialze the cycle lists
         */
 
        /*
         *      Count the number of cycles, and initialze the cycle lists
         */

-    cyclemax = 0;
+    ncycle = 0;

     for ( nlp = nl ; nlp < npe ; nlp++ ) {
            /*
             *  this is how you find unattached cycles
             */
        if ( nlp -> cyclehead == nlp && nlp -> cnext != 0 ) {
     for ( nlp = nl ; nlp < npe ; nlp++ ) {
            /*
             *  this is how you find unattached cycles
             */
        if ( nlp -> cyclehead == nlp && nlp -> cnext != 0 ) {

-           cyclemax += 1;
+           ncycle += 1;

        }
     }
        }
     }

-    if ( cyclemax > ncycles ) {
-       fprintf( stderr , "prof: %d cycles in %d names exceeds %f%%\n" ,
-               cyclemax , nname , CYCLEFRACTION * 100.0 );
-       exit( 1 );
+       /*
+        *      cyclenl is indexed by cycle number:
+        *      i.e. it is origin 1, not origin 0.
+        */
+    cyclenl = (nltype *) calloc( ncycle + 1 , sizeof( nltype ) );
+    if ( cyclenl == 0 ) {
+       fprintf( stderr , "%s: No room for %d bytes of cycle headers\n" ,
+               whoami , ( ncycle + 1 ) * sizeof( nltype ) );
+       done();

     }
        /*
         *      now link cycles to true cycleheads,
     }
        /*
         *      now link cycles to true cycleheads,


@@ -275,14 +284,28 @@ cyclelink()
         */
     cycle = 0;
     for ( nlp = nl ; nlp < npe ; nlp++ ) {
         */
     cycle = 0;
     for ( nlp = nl ; nlp < npe ; nlp++ ) {

-       if ( nlp -> cyclehead != nlp || nlp -> cnext == 0 ) {
+       if ( !( nlp -> cyclehead == nlp && nlp -> cnext != 0 ) ) {

            continue;
        }
        cycle += 1;
            continue;
        }
        cycle += 1;

-       cyclenlp = &nl[nname+cycle];
-       cyclenlp -> cycleno = cycle;
-       cyclenlp -> cyclehead = cyclenlp;
-       cyclenlp -> cnext = nlp;
+       cyclenlp = &cyclenl[cycle];
+        cyclenlp -> name = 0;          /* the name */
+        cyclenlp -> value = 0;         /* the pc entry point */
+        cyclenlp -> time = 0.0;                /* ticks in this routine */
+        cyclenlp -> childtime = 0.0;   /* cumulative ticks in children */
+       cyclenlp -> ncall = 0;          /* how many times called */
+       cyclenlp -> selfcalls = 0;      /* how many calls to self */
+       cyclenlp -> propfraction = 0.0; /* what % of time propagates */
+       cyclenlp -> propself = 0.0;     /* how much self time propagates */
+       cyclenlp -> propchild = 0.0;    /* how much child time propagates */
+       cyclenlp -> printflag = TRUE;   /* should this be printed? */
+       cyclenlp -> index = 0;          /* index in the graph list */
+       cyclenlp -> toporder = DFN_NAN; /* graph call chain top-sort order */
+       cyclenlp -> cycleno = cycle;    /* internal number of cycle on */
+       cyclenlp -> cyclehead = cyclenlp;       /* pointer to head of cycle */
+       cyclenlp -> cnext = nlp;        /* pointer to next member of cycle */
+       cyclenlp -> parents = 0;        /* list of caller arcs */
+       cyclenlp -> children = 0;       /* list of callee arcs */

 #      ifdef DEBUG
            if ( debug & CYCLEDEBUG ) {
                printf( "[cyclelink] " );
 #      ifdef DEBUG
            if ( debug & CYCLEDEBUG ) {
                printf( "[cyclelink] " );


@@ -291,54 +314,201 @@ cyclelink()
            }
 #      endif DEBUG
            /*
            }
 #      endif DEBUG
            /*

-            *  n-squaredly (in the size of the cycle)
-            *  find all the call within the cycle 
-            *  (including self-recursive calls)
-            *  and remove them, thus making the cycle into
-            *  `node' with calls only from the outside.
-            *  note: that this doesn't deal with
-            *  self-recursive calls outside cycles (sigh).
+            *  link members to cycle header
+            */
+       for ( memberp = nlp ; memberp ; memberp = memberp -> cnext ) { 
+           memberp -> cycleno = cycle;
+           memberp -> cyclehead = cyclenlp;
+       }
+           /*
+            *  count calls from outside the cycle
+            *  and those among cycle members

             */
             */

-       callsamong = 0;
-       for ( parentp = nlp ; parentp ; parentp = parentp -> cnext ) {
-           parentp -> cycleno = cycle;
-           parentp -> cyclehead = cyclenlp;
-           for ( childp = nlp ; childp ; childp = childp -> cnext ) {
-               if ( parentp == childp ) {
+       for ( memberp = nlp ; memberp ; memberp = memberp -> cnext ) {
+           for ( arcp=memberp->parents ; arcp ; arcp=arcp->arc_parentlist ) {
+               if ( arcp -> arc_parentp == memberp ) {

                    continue;
                }
                    continue;
                }

-               arcp = arclookup( parentp , childp );
-               if ( arcp != 0 ) {
-                   callsamong += arcp -> arc_count;
-#                  ifdef DEBUG
-                       if ( debug & CYCLEDEBUG ) {
-                           printf("[cyclelink] %s calls sibling %s %d times\n",
-                               parentp -> name , childp -> name ,
-                               arcp -> arc_count );
-                       }
-#                  endif DEBUG
+               if ( arcp -> arc_parentp -> cycleno == cycle ) {
+                   cyclenlp -> selfcalls += arcp -> arc_count;
+               } else {
+                   cyclenlp -> ncall += arcp -> arc_count;

                }
            }
        }
                }
            }
        }

+    }
+}
+
+cycletime()
+{
+    int                        cycle;
+    nltype             *cyclenlp;
+    nltype             *childp;
+
+    for ( cycle = 1 ; cycle <= ncycle ; cycle += 1 ) {
+       cyclenlp = &cyclenl[ cycle ];
+       for ( childp = cyclenlp -> cnext ; childp ; childp = childp -> cnext ) {
+           if ( childp -> propfraction == 0.0 ) {
+                   /*
+                    * all members have the same propfraction except those
+                    *  that were excluded with -E
+                    */
+               continue;
+           }
+           cyclenlp -> time += childp -> time;
+       }
+       cyclenlp -> propself = cyclenlp -> propfraction * cyclenlp -> time;
+    }
+}
+
+    /*
+     * in one top to bottom pass over the topologically sorted namelist
+     * propagate:
+     *         printflag as the union of parents' printflags
+     *         propfraction as the sum of fractional parents' propfractions
+     * and while we're here, sum time for functions.
+     */
+doflags()
+{
+    int                index;
+    nltype     *childp;
+    nltype     *oldhead;
+
+    oldhead = 0;
+    for ( index = nname-1 ; index >= 0 ; index -= 1 ) {
+       childp = topsortnlp[ index ];

            /*
            /*

-            *  collect calls and time around the cycle,
-            *  and save it in the cycle header.
+            *  if we haven't done this function or cycle,
+            *  inherit things from parent.
+            *  this way, we are linear in the number of arcs
+            *  since we do all members of a cycle (and the cycle itself)
+            *  as we hit the first member of the cycle.

             */
             */

-       ncall = -callsamong;
-       time = 0.0;
-       for ( parentp = nlp ; parentp ; parentp = parentp -> cnext ) {
-           ncall += parentp -> ncall;
-           time += parentp -> time;
+       if ( childp -> cyclehead != oldhead ) {
+           oldhead = childp -> cyclehead;
+           inheritflags( childp );

        }
 #      ifdef DEBUG
        }
 #      ifdef DEBUG

-           if ( debug & CYCLEDEBUG ) {
-               printf( "[cyclelink] cycle %d %f ticks in %d (%d) calls\n" ,
-                       cycle , time , ncall , callsamong );
+           if ( debug & PROPDEBUG ) {
+               printf( "[doflags] " );
+               printname( childp );
+               printf( " inherits printflag %d and propfraction %f\n" ,
+                       childp -> printflag , childp -> propfraction );

            }
 #      endif DEBUG
            }
 #      endif DEBUG

-       cyclenlp -> ncall = ncall;
-       cyclenlp -> selfcalls = callsamong;
-       cyclenlp -> time = time;
-       cyclenlp -> childtime = 0.0;
+       if ( ! childp -> printflag ) {
+               /*
+                *      printflag is off
+                *      it gets turned on by
+                *      being on -f list,
+                *      or there not being any -f list and not being on -e list.
+                */
+           if (   onlist( flist , childp -> name )
+               || ( !fflag && !onlist( elist , childp -> name ) ) ) {
+               childp -> printflag = TRUE;
+           }
+       } else {
+               /*
+                *      this function has printing parents:
+                *      maybe someone wants to shut it up
+                *      by putting it on -e list.  (but favor -f over -e)
+                */
+           if (  ( !onlist( flist , childp -> name ) )
+               && onlist( elist , childp -> name ) ) {
+               childp -> printflag = FALSE;
+           }
+       }
+       if ( childp -> propfraction == 0.0 ) {
+               /*
+                *      no parents to pass time to.
+                *      collect time from children if
+                *      its on -F list,
+                *      or there isn't any -F list and its not on -E list.
+                */
+           if ( onlist( Flist , childp -> name )
+               || ( !Fflag && !onlist( Elist , childp -> name ) ) ) {
+                   childp -> propfraction = 1.0;
+           }
+       } else {
+               /*
+                *      it has parents to pass time to, 
+                *      but maybe someone wants to shut it up
+                *      by puttting it on -E list.  (but favor -F over -E)
+                */
+           if (  !onlist( Flist , childp -> name )
+               && onlist( Elist , childp -> name ) ) {
+               childp -> propfraction = 0.0;
+           }
+       }
+       childp -> propself = childp -> time * childp -> propfraction;
+       printtime += childp -> propself;
+#      ifdef DEBUG
+           if ( debug & PROPDEBUG ) {
+               printf( "[doflags] " );
+               printname( childp );
+               printf( " ends up with printflag %d and propfraction %f\n" ,
+                       childp -> printflag , childp -> propfraction );
+               printf( "time %f propself %f printtime %f\n" ,
+                       childp -> time , childp -> propself , printtime );
+           }
+#      endif DEBUG
+    }
+}
+
+    /*
+     * check if any parent of this child
+     * (or outside parents of this cycle)
+     * have their print flags on and set the 
+     * print flag of the child (cycle) appropriately.
+     * similarly, deal with propagation fractions from parents.
+     */
+inheritflags( childp )
+    nltype     *childp;
+{
+    nltype     *headp;
+    arctype    *arcp;
+    nltype     *parentp;
+    nltype     *memp;
+
+    headp = childp -> cyclehead;
+    if ( childp == headp ) {
+           /*
+            *  just a regular child, check its parents
+            */
+       childp -> printflag = FALSE;
+       childp -> propfraction = 0.0;
+       for (arcp = childp -> parents ; arcp ; arcp = arcp -> arc_parentlist) {
+           parentp = arcp -> arc_parentp;
+           if ( childp == parentp ) {
+               continue;
+           }
+           childp -> printflag |= parentp -> printflag;
+           childp -> propfraction += parentp -> propfraction
+                                       * ( ( (double) arcp -> arc_count )
+                                         / ( (double) childp -> ncall ) );
+       }
+    } else {
+           /*
+            *  its a member of a cycle, look at all parents from 
+            *  outside the cycle
+            */
+       headp -> printflag = FALSE;
+       headp -> propfraction = 0.0;
+       for ( memp = headp -> cnext ; memp ; memp = memp -> cnext ) {
+           for (arcp = memp->parents ; arcp ; arcp = arcp->arc_parentlist) {
+               if ( arcp -> arc_parentp -> cyclehead == headp ) {
+                   continue;
+               }
+               parentp = arcp -> arc_parentp;
+               headp -> printflag |= parentp -> printflag;
+               headp -> propfraction += parentp -> propfraction
+                                       * ( ( (double) arcp -> arc_count )
+                                         / ( (double) headp -> ncall ) );
+           }
+       }
+       for ( memp = headp ; memp ; memp = memp -> cnext ) {
+           memp -> printflag = headp -> printflag;
+           memp -> propfraction = headp -> propfraction;
+       }

     }
 }
     }
 }