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