usr.bin/gprof/PSD.doc/postp.me

   1 .\" Copyright (c) 1982, 1993
   2 .\"     The Regents of the University of California.  All rights reserved.
   3 .\"
   4 .\" Redistribution and use in source and binary forms, with or without
   5 .\" modification, are permitted provided that the following conditions
   6 .\" are met:
   7 .\" 1. Redistributions of source code must retain the above copyright
   8 .\"    notice, this list of conditions and the following disclaimer.
   9 .\" 2. Redistributions in binary form must reproduce the above copyright
  10 .\"    notice, this list of conditions and the following disclaimer in the
  11 .\"    documentation and/or other materials provided with the distribution.
  12 .\" 3. All advertising materials mentioning features or use of this software
  13 .\"    must display the following acknowledgement:
  14 .\"     This product includes software developed by the University of
  15 .\"     California, Berkeley and its contributors.
  16 .\" 4. Neither the name of the University nor the names of its contributors
  17 .\"    may be used to endorse or promote products derived from this software
  18 .\"    without specific prior written permission.
  19 .\"
  20 .\" THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  21 .\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  22 .\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  23 .\" ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  24 .\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  25 .\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  26 .\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  27 .\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  28 .\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  29 .\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  30 .\" SUCH DAMAGE.
  31 .\"
  32 .\"     @(#)postp.me    8.1 (Berkeley) 6/8/93
  33 .\"
  34 .EQ
  35 delim $$
  36 gsize 11
  37 .EN
  38 .sh 1 "Post Processing"
  39 .pp
  40 Having gathered the arcs of the call graph and timing information
  41 for an execution of the program,
  42 we are interested in attributing the time for each routine to the
  43 routines that call it.
  44 We build a dynamic call graph with arcs from caller to callee,
  45 and propagate time from descendants to ancestors
  46 by topologically sorting the call graph.
  47 Time propagation is performed from the leaves of the
  48 call graph toward the roots, according to the order
  49 assigned by a topological numbering algorithm.
  50 The topological numbering ensures that
  51 all edges in the graph go from higher numbered nodes to lower
  52 numbered nodes.
  53 An example is given in Figure 1.
  54 If we propagate time from nodes in the
  55 order assigned by the algorithm,
  56 execution time can be propagated from descendants to ancestors
  57 after a single traversal of each arc in the call graph.
  58 Each parent receives some fraction of a child's time.
  59 Thus time is charged to the
  60 caller in addition to being charged to the callee.
  61 .(z
  62 .so postp1.pic
  63 .ce 2
  64 Topological ordering
  65 Figure 1.
  66 .ce 0
  67 .)z
  68 .pp
  69 Let $C sub e$ be the number of calls to some routine,
  70 $e$, and $C sub e sup r$ be the number of
  71 calls from a caller $r$ to a callee $e$.
  72 Since we are assuming each call to a routine takes the
  73 average amount of time for all calls to that routine,
  74 the caller is accountable for
  75 $C sub e sup r / C sub e$
  76 of the time spent by the callee.
  77 Let the $S sub e$ be the $selftime$ of a routine, $e$.
  78 The selftime of a routine can be determined from the
  79 timing information gathered during profiled program execution.
  80 The total time, $T sub r$, we wish to account to a routine
  81 $r$, is then given by the recurrence equation:
  82 .EQ
  83 T sub r ~ = ~ {S sub r} ~ + ~
  84                    sum from {r ~ roman CALLS ~ e}
  85                    {T sub e times {{C sub e sup r} over {C sub e}}}
  86 .EN
  87 where $r ~ roman CALLS ~ e$ is a relation showing all routines
  88 $e$ called by a routine $r$.
  89 This relation is easily available from the call graph.
  90 .pp
  91 However, if the execution contains recursive calls,
  92 the call graph has cycles that
  93 cannot be topologically sorted.
  94 In these cases, we discover strongly-connected
  95 components in the call graph,
  96 treat each such component as a single node,
  97 and then sort the resulting graph.
  98 We use a variation of Tarjan's strongly-connected
  99 components algorithm
 100 that discovers strongly-connected components as it is assigning
 101 topological order numbers [Tarjan72].
 102 .pp
 103 Time propagation within strongly connected
 104 components is a problem.
 105 For example, a self-recursive routine
 106 (a trivial cycle in the call graph)
 107 is accountable for all the time it
 108 uses in all its recursive instantiations.
 109 In our scheme, this time should be
 110 shared among its call graph parents.
 111 The arcs from a routine to itself are of interest,
 112 but do not participate in time propagation.
 113 Thus the simple equation for time propagation
 114 does not work within strongly connected components.
 115 Time is not propagated from one member of a cycle to another,
 116 since, by definition, this involves propagating time from a routine
 117 to itself.
 118 In addition, children of one member of a cycle
 119 must be considered children of all members of the cycle.
 120 Similarly, parents of one member of the cycle must inherit
 121 all members of the cycle as descendants.
 122 It is for these reasons that we collapse connected components.
 123 Our solution collects all members of a cycle together,
 124 summing the time and call counts for all members.
 125 All calls into the cycle are made to share the total
 126 time of the cycle, and all descendants of the cycle
 127 propagate time into the cycle as a whole.
 128 Calls among the members of the cycle
 129 do not propagate any time,
 130 though they are listed in the call graph profile.
 131 .pp
 132 Figure 2 shows a modified version of the call graph of Figure 1,
 133 in which the nodes labelled 3 and 7 in Figure 1 are mutually
 134 recursive.
 135 The topologically sorted graph after the cycle is collapsed is
 136 given in Figure 3.
 137 .(z
 138 .so postp2.pic
 139 .ce 2
 140 Cycle to be collapsed.
 141 Figure 2.
 142 .ce 0
 143 .)z
 144 .(z
 145 .so postp3.pic
 146 .ce 2
 147 Topological numbering after cycle collapsing.
 148 Figure 3.
 149 .ce 0
 150 .)z
 151 .pp
 152 Since the technique described above only collects the
 153 dynamic call graph,
 154 and the program typically does not call every routine
 155 on each execution,
 156 different executions can introduce different cycles in the
 157 dynamic call graph.
 158 Since cycles often have a significant effect on time propagation,
 159 it is desirable to incorporate the static call graph so that cycles
 160 will have the same members regardless of how the program runs.
 161 .pp
 162 The static call graph can be constructed from the source text
 163 of the program.
 164 However, discovering the static call graph from the source text
 165 would require two moderately difficult steps:
 166 finding the source text for the program
 167 (which may not be available),
 168 and scanning and parsing that text,
 169 which may be in any one of several languages.
 170 .pp
 171 In our programming system,
 172 the static calling information is also contained in the
 173 executable version of the program,
 174 which we already have available,
 175 and which is in language-independent form.
 176 One can examine the instructions
 177 in the object program,
 178 looking for calls to routines, and note which
 179 routines can be called.
 180 This technique allows us to add arcs to those already in the
 181 dynamic call graph.
 182 If a statically discovered arc already exists in the dynamic call
 183 graph, no action is required.
 184 Statically discovered arcs that do not exist in the dynamic call
 185 graph are added to the graph with a traversal count of zero.
 186 Thus they are never responsible for any time propagation.
 187 However, they may affect the structure of the graph.
 188 Since they may complete strongly connected components,
 189 the static call graph construction is
 190 done before topological ordering.