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