| blob | 4683bf6fce3b17e9b68ee4a75ac1f911dfca8774 |
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.