diff options
Diffstat (limited to 'usr.bin/gprof/PSD.doc')
| -rw-r--r-- | usr.bin/gprof/PSD.doc/Makefile | 14 | ||||
| -rw-r--r-- | usr.bin/gprof/PSD.doc/abstract.me | 68 | ||||
| -rw-r--r-- | usr.bin/gprof/PSD.doc/gathering.me | 233 | ||||
| -rw-r--r-- | usr.bin/gprof/PSD.doc/header.me | 40 | ||||
| -rw-r--r-- | usr.bin/gprof/PSD.doc/intro.me | 83 | ||||
| -rw-r--r-- | usr.bin/gprof/PSD.doc/postp.me | 192 | ||||
| -rw-r--r-- | usr.bin/gprof/PSD.doc/postp1.pic | 56 | ||||
| -rw-r--r-- | usr.bin/gprof/PSD.doc/postp2.pic | 58 | ||||
| -rw-r--r-- | usr.bin/gprof/PSD.doc/postp3.pic | 53 | ||||
| -rw-r--r-- | usr.bin/gprof/PSD.doc/pres1.pic | 58 | ||||
| -rw-r--r-- | usr.bin/gprof/PSD.doc/pres2.pic | 54 | ||||
| -rw-r--r-- | usr.bin/gprof/PSD.doc/present.me | 308 | ||||
| -rw-r--r-- | usr.bin/gprof/PSD.doc/profiling.me | 117 | ||||
| -rw-r--r-- | usr.bin/gprof/PSD.doc/refs.me | 65 |
14 files changed, 1399 insertions, 0 deletions
diff --git a/usr.bin/gprof/PSD.doc/Makefile b/usr.bin/gprof/PSD.doc/Makefile new file mode 100644 index 00000000000..db317092eac --- /dev/null +++ b/usr.bin/gprof/PSD.doc/Makefile @@ -0,0 +1,14 @@ +# $NetBSD: Makefile,v 1.3 1995/04/19 07:16:35 cgd Exp $ +# @(#)Makefile 8.1 (Berkeley) 8/14/93 + +DIR= psd/18.gprof +SRCS= header.me abstract.me intro.me profiling.me gathering.me \ + postp.me present.me refs.me +EXTRA= postp1.pic postp2.pic postp3.pic pres1.pic pres2.pic +DPADD= ${EXTRA} +MACROS= -me + +paper.ps: ${SRCS} ${DPADD} + ${SOELIM} ${SRCS} | ${PIC} | ${TBL} | ${EQN} | ${ROFF} > ${.TARGET} + +.include <bsd.doc.mk> diff --git a/usr.bin/gprof/PSD.doc/abstract.me b/usr.bin/gprof/PSD.doc/abstract.me new file mode 100644 index 00000000000..7eebfe62d41 --- /dev/null +++ b/usr.bin/gprof/PSD.doc/abstract.me @@ -0,0 +1,68 @@ +.\" $NetBSD: abstract.me,v 1.2 1995/04/19 07:16:37 cgd Exp $ +.\" +.\" Copyright (c) 1982, 1993 +.\" The Regents of the University of California. All rights reserved. +.\" +.\" Redistribution and use in source and binary forms, with or without +.\" modification, are permitted provided that the following conditions +.\" are met: +.\" 1. Redistributions of source code must retain the above copyright +.\" notice, this list of conditions and the following disclaimer. +.\" 2. Redistributions in binary form must reproduce the above copyright +.\" notice, this list of conditions and the following disclaimer in the +.\" documentation and/or other materials provided with the distribution. +.\" 3. All advertising materials mentioning features or use of this software +.\" must display the following acknowledgement: +.\" This product includes software developed by the University of +.\" California, Berkeley and its contributors. +.\" 4. Neither the name of the University nor the names of its contributors +.\" may be used to endorse or promote products derived from this software +.\" without specific prior written permission. +.\" +.\" THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND +.\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE +.\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE +.\" ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE +.\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL +.\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS +.\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) +.\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT +.\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY +.\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF +.\" SUCH DAMAGE. +.\" +.\" @(#)abstract.me 8.1 (Berkeley) 6/8/93 +.\" +.sp 1 +\fB\s+2gprof: a Call Graph Execution Profiler\s-2\fP\** +.(f +\**This work was supported by grant MCS80-05144 +from the National Science Foundation. +.)f +.sp 1 +by +\fISusan L. Graham\fP +\fIPeter B. Kessler\fP +\fIMarshall K. McKusick\fP +.sp 1 +Computer Science Division +Electrical Engineering and Computer Science Department +University of California, Berkeley +Berkeley, California 94720 +.ce 0 +.sp 1 +.sp 0.5i +.sh 0 "Abstract" +.pp +Large complex programs are composed of many small routines +that implement abstractions for the routines that call them. +To be useful, an execution profiler must attribute +execution time in a way that is significant for the +logical structure of a program +as well as for its textual decomposition. +This data must then be displayed to the user +in a convenient and informative way. +The \fBgprof\fP profiler +accounts for the running time of called routines +in the running time of the routines that call them. +The design and use of this profiler is described. diff --git a/usr.bin/gprof/PSD.doc/gathering.me b/usr.bin/gprof/PSD.doc/gathering.me new file mode 100644 index 00000000000..835d8a9ef39 --- /dev/null +++ b/usr.bin/gprof/PSD.doc/gathering.me @@ -0,0 +1,233 @@ +.\" $NetBSD: gathering.me,v 1.2 1995/04/19 07:16:39 cgd Exp $ +.\" +.\" Copyright (c) 1982, 1993 +.\" The Regents of the University of California. All rights reserved. +.\" +.\" Redistribution and use in source and binary forms, with or without +.\" modification, are permitted provided that the following conditions +.\" are met: +.\" 1. Redistributions of source code must retain the above copyright +.\" notice, this list of conditions and the following disclaimer. +.\" 2. Redistributions in binary form must reproduce the above copyright +.\" notice, this list of conditions and the following disclaimer in the +.\" documentation and/or other materials provided with the distribution. +.\" 3. All advertising materials mentioning features or use of this software +.\" must display the following acknowledgement: +.\" This product includes software developed by the University of +.\" California, Berkeley and its contributors. +.\" 4. Neither the name of the University nor the names of its contributors +.\" may be used to endorse or promote products derived from this software +.\" without specific prior written permission. +.\" +.\" THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND +.\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE +.\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE +.\" ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE +.\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL +.\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS +.\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) +.\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT +.\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY +.\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF +.\" SUCH DAMAGE. +.\" +.\" @(#)gathering.me 8.1 (Berkeley) 6/8/93 +.\" +.sh 1 "Gathering Profile Data" +.pp +Routine calls or statement executions can be measured by having a +compiler augment the code at strategic points. +The additions can be inline increments to counters [Knuth71] +[Satterthwaite72] [Joy79] or calls to +monitoring routines [Unix]. +The counter increment overhead is low, and is suitable for +profiling statements. +A call of the monitoring routine has an overhead comparable with a +call of a regular routine, and is therefore only suited +to profiling on a routine by routine basis. +However, the monitoring routine solution has certain advantages. +Whatever counters are needed by the monitoring routine can be +managed by the monitoring routine itself, rather than being +distributed around the code. +In particular, a monitoring routine can easily be called from separately +compiled programs. +In addition, different monitoring routines can be linked into the +program +being measured +to assemble different profiling data without having to +change the compiler or recompile the program. +We have exploited this approach; +our compilers for C, Fortran77, and Pascal can insert calls to a +monitoring routine in the prologue for each routine. +Use of the monitoring routine requires no planning on part of a +programmer other than to request that augmented routine +prologues be produced during compilation. +.pp +We are interested in gathering three pieces of information during +program execution: call counts and execution times for +each profiled routine, and the arcs of the dynamic call graph +traversed by this execution of the program. +By post-processing of this data we can build the dynamic call +graph for this execution of the program and propagate times along +the edges of this graph to attribute times for routines to the +routines that invoke them. +.pp +Gathering of the profiling information should not greatly +interfere with the running of the program. +Thus, the monitoring routine must not produce trace output each +time it is invoked. +The volume of data thus produced would be unmanageably large, +and the time required to record it would overwhelm the running +time of most programs. +Similarly, the monitoring routine can not do the analysis of +the profiling data (e.g. assembling the call graph, propagating +times around it, discovering cycles, etc.) during program +execution. +Our solution is to gather profiling data in memory during program +execution and to condense it to a file as the profiled +program exits. +This file is then processed by a separate program to produce the +listing of the profile data. +An advantage of this approach is that the profile data for +several executions of a program can be combined by the +post-processing to provide a profile of many +executions. +.pp +The execution time monitoring consists of three parts. +The first part allocates and initializes the runtime monitoring data +structures before the program begins execution. +The second part is the monitoring routine invoked from the +prologue of each profiled routine. +The third part condenses the data structures and writes them +to a file as the program terminates. +The monitoring routine is discussed in detail in the following sections. +.sh 2 "Execution Counts" +.pp +The \fBgprof\fP monitoring routine counts the number of times +each profiled routine is called. +The monitoring routine also records the arc in the call graph +that activated the profiled routine. +The count is associated with the arc in the call graph +rather than with the routine. +Call counts for routines can then be determined by summing the counts +on arcs directed into that routine. +In a machine-dependent fashion, the monitoring routine notes its +own return address. +This address is in the prologue of some profiled routine that is +the destination of an arc in the dynamic call graph. +The monitoring routine also discovers the return address for that +routine, thus identifying the call site, or source of the arc. +The source of the arc is in the \fIcaller\fP, and the destination is in +the \fIcallee\fP. +For example, if a routine A calls a routine B, A is the caller, +and B is the callee. +The prologue of B will include a call to the monitoring routine +that will note the arc from A to B and either initialize or +increment a counter for that arc. +.pp +One can not afford to have the monitoring routine output tracing +information as each arc is identified. +Therefore, the monitoring routine maintains a table of all the +arcs discovered, with counts of the numbers of times each is +traversed during execution. +This table is accessed once per routine call. +Access to it +must be as fast as possible so as not to overwhelm the time +required to execute the program. +.pp +Our solution is to access the table through a hash table. +We use the call site as the primary key with the callee +address being the secondary key. +Since each call site typically calls only one callee, we can +reduce (usually to one) the number of minor lookups based on the callee. +Another alternative would use the callee as the primary key and the +call site as the secondary key. +Such an organization has the advantage of associating callers with +callees, at the expense of longer lookups in the monitoring +routine. +We are fortunate to be running in a virtual memory environment, +and (for the sake of speed) were able to allocate enough space +for the primary hash table to allow a one-to-one mapping from +call site addresses to the primary hash table. +Thus our hash function is trivial to calculate and collisions +occur only for call sites that call multiple +destinations (e.g. functional parameters and functional variables). +A one level hash function using both call site and callee would +result in an unreasonably large hash table. +Further, the number of dynamic call sites and callees is not known during +execution of the profiled program. +.pp +Not all callers and callees can be identified by the monitoring +routine. +Routines that were compiled without the profiling augmentations +will not call the monitoring routine as part of their prologue, +and thus no arcs will be recorded whose destinations are in these +routines. +One need not profile all the routines in a program. +Routines that are not profiled run at full speed. +Certain routines, notably exception handlers, are invoked by +non-standard calling sequences. +Thus the monitoring routine may know the destination of an arc +(the callee), +but find it difficult or +impossible to determine the source of the arc (the caller). +Often in these cases the apparent source of the arc is not a call +site at all. +Such anomalous invocations are declared ``spontaneous''. +.sh 2 "Execution Times" +.pp +The execution times for routines can be gathered in at least two +ways. +One method measures the execution time of a routine by measuring +the elapsed time from routine entry to routine exit. +Unfortunately, time measurement is complicated on time-sharing +systems by the time-slicing of the program. +A second method samples the value of the program counter at some +interval, and infers execution time from the distribution of the +samples within the program. +This technique is particularly suited to time-sharing systems, +where the time-slicing can serve as the basis for sampling +the program counter. +Notice that, whereas the first method could provide exact timings, +the second is inherently a statistical approximation. +.pp +The sampling method need not require support from the operating +system: all that is needed is the ability to set and respond to +``alarm clock'' interrupts that run relative to program time. +It is imperative that the intervals be uniform since the +sampling of the program counter rather than the duration of the +interval is the basis of the distribution. +If sampling is done too often, the interruptions to sample the +program counter will overwhelm the running of the profiled program. +On the other hand, the program must run for enough sampled +intervals that the distribution of the samples accurately +represents the distribution of time for the execution of the +program. +As with routine call tracing, the monitoring routine can not +afford to output information for each program counter +sample. +In our computing environment, the operating system can provide a +histogram of the location of the program counter at the end of +each clock tick (1/60th of a second) in which a program runs. +The histogram is assembled in memory as the program runs. +This facility is enabled by our monitoring routine. +We have adjusted the granularity of the histogram so that +program counter values map one-to-one onto the histogram. +We make the simplifying assumption that all calls to a specific +routine require the same amount of time to execute. +This assumption may disguise that some calls +(or worse, some call sites) always invoke a routine +such that its execution is faster (or slower) +than the average time for that routine. +.pp +When the profiled program terminates, +the arc table and the histogram of +program counter samples is written to a file. +The arc table is condensed to consist of the source and destination +addresses of the arc and the count of the number of times the arc +was traversed by this execution of the program. +The recorded histogram consists of counters of the number of +times the program counter was found to be in each of the ranges covered +by the histogram. +The ranges themselves are summarized as a +lower and upper bound and a step size. diff --git a/usr.bin/gprof/PSD.doc/header.me b/usr.bin/gprof/PSD.doc/header.me new file mode 100644 index 00000000000..4b4772e6fd6 --- /dev/null +++ b/usr.bin/gprof/PSD.doc/header.me @@ -0,0 +1,40 @@ +.\" $NetBSD: header.me,v 1.2 1995/04/19 07:16:41 cgd Exp $ +.\" +.\" Copyright (c) 1982, 1993 +.\" The Regents of the University of California. All rights reserved. +.\" +.\" Redistribution and use in source and binary forms, with or without +.\" modification, are permitted provided that the following conditions +.\" are met: +.\" 1. Redistributions of source code must retain the above copyright +.\" notice, this list of conditions and the following disclaimer. +.\" 2. Redistributions in binary form must reproduce the above copyright +.\" notice, this list of conditions and the following disclaimer in the +.\" documentation and/or other materials provided with the distribution. +.\" 3. All advertising materials mentioning features or use of this software +.\" must display the following acknowledgement: +.\" This product includes software developed by the University of +.\" California, Berkeley and its contributors. +.\" 4. Neither the name of the University nor the names of its contributors +.\" may be used to endorse or promote products derived from this software +.\" without specific prior written permission. +.\" +.\" THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND +.\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE +.\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE +.\" ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE +.\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL +.\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS +.\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) +.\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT +.\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY +.\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF +.\" SUCH DAMAGE. +.\" +.\" @(#)header.me 8.1 (Berkeley) 8/14/93 +.\" +.\"he 'gprof''Graham, Kessler, McKusick' +.\"fo 'Draft of \*(td''%' +.\"ls 2 +.eh 'PSD:18-%''gprof \*- a Call Graph Execution Profiler' +.oh 'gprof \*- A Call Graph Execution Profiler''PSD:18-%' diff --git a/usr.bin/gprof/PSD.doc/intro.me b/usr.bin/gprof/PSD.doc/intro.me new file mode 100644 index 00000000000..9428568debe --- /dev/null +++ b/usr.bin/gprof/PSD.doc/intro.me @@ -0,0 +1,83 @@ +.\" $NetBSD: intro.me,v 1.2 1995/04/19 07:16:42 cgd Exp $ +.\" +.\" Copyright (c) 1982, 1993 +.\" The Regents of the University of California. All rights reserved. +.\" +.\" Redistribution and use in source and binary forms, with or without +.\" modification, are permitted provided that the following conditions +.\" are met: +.\" 1. Redistributions of source code must retain the above copyright +.\" notice, this list of conditions and the following disclaimer. +.\" 2. Redistributions in binary form must reproduce the above copyright +.\" notice, this list of conditions and the following disclaimer in the +.\" documentation and/or other materials provided with the distribution. +.\" 3. All advertising materials mentioning features or use of this software +.\" must display the following acknowledgement: +.\" This product includes software developed by the University of +.\" California, Berkeley and its contributors. +.\" 4. Neither the name of the University nor the names of its contributors +.\" may be used to endorse or promote products derived from this software +.\" without specific prior written permission. +.\" +.\" THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND +.\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE +.\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE +.\" ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE +.\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL +.\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS +.\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) +.\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT +.\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY +.\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF +.\" SUCH DAMAGE. +.\" +.\" @(#)intro.me 8.1 (Berkeley) 6/8/93 +.\" +.sh 1 "Programs to be Profiled" +.pp +Software research environments +normally include many large programs +both for production use and for experimental investigation. +These programs are typically modular, +in accordance with generally accepted principles +of good program design. +Often they consist of numerous small routines +that implement various abstractions. +Sometimes such large programs are written +by one programmer +who has understood the requirements for +these abstractions, and has programmed them +appropriately. +More frequently the program has +had multiple authors and has +evolved over time, changing the demands placed +on the implementation of the abstractions without +changing the implementation itself. +Finally, the program may be assembled from a library +of abstraction implementations +unexamined by the programmer. +.pp +Once a large program is executable, +it is often desirable to increase its speed, +especially if small portions of the program +are found to dominate its execution time. +The purpose of the \fBgprof\fP profiling tool is to +help the user evaluate alternative implementations +of abstractions. +We developed this tool in response to our efforts +to improve a code generator we were writing [Graham82]. +.pp +The \fBgprof\fP design takes advantage of the fact that the programs +to be measured are large, structured and hierarchical. +We provide a profile in which the execution time +for a set of routines that implement an +abstraction is collected and charged +to that abstraction. +The profile can be used to compare and assess the costs of +various implementations. +.pp +The profiler can be linked into a program without +special planning by the programmer. +The overhead for using \fBgprof\fP is low; +both in terms of added execution time and in the +volume of profiling information recorded. diff --git a/usr.bin/gprof/PSD.doc/postp.me b/usr.bin/gprof/PSD.doc/postp.me new file mode 100644 index 00000000000..8587882da21 --- /dev/null +++ b/usr.bin/gprof/PSD.doc/postp.me @@ -0,0 +1,192 @@ +.\" $NetBSD: postp.me,v 1.2 1995/04/19 07:16:44 cgd Exp $ +.\" +.\" Copyright (c) 1982, 1993 +.\" The Regents of the University of California. All rights reserved. +.\" +.\" Redistribution and use in source and binary forms, with or without +.\" modification, are permitted provided that the following conditions +.\" are met: +.\" 1. Redistributions of source code must retain the above copyright +.\" notice, this list of conditions and the following disclaimer. +.\" 2. Redistributions in binary form must reproduce the above copyright +.\" notice, this list of conditions and the following disclaimer in the +.\" documentation and/or other materials provided with the distribution. +.\" 3. All advertising materials mentioning features or use of this software +.\" must display the following acknowledgement: +.\" This product includes software developed by the University of +.\" California, Berkeley and its contributors. +.\" 4. Neither the name of the University nor the names of its contributors +.\" may be used to endorse or promote products derived from this software +.\" without specific prior written permission. +.\" +.\" THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND +.\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE +.\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE +.\" ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE +.\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL +.\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS +.\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) +.\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT +.\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY +.\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF +.\" SUCH DAMAGE. +.\" +.\" @(#)postp.me 8.1 (Berkeley) 6/8/93 +.\" +.EQ +delim $$ +gsize 11 +.EN +.sh 1 "Post Processing" +.pp +Having gathered the arcs of the call graph and timing information +for an execution of the program, +we are interested in attributing the time for each routine to the +routines that call it. +We build a dynamic call graph with arcs from caller to callee, +and propagate time from descendants to ancestors +by topologically sorting the call graph. +Time propagation is performed from the leaves of the +call graph toward the roots, according to the order +assigned by a topological numbering algorithm. +The topological numbering ensures that +all edges in the graph go from higher numbered nodes to lower +numbered nodes. +An example is given in Figure 1. +If we propagate time from nodes in the +order assigned by the algorithm, +execution time can be propagated from descendants to ancestors +after a single traversal of each arc in the call graph. +Each parent receives some fraction of a child's time. +Thus time is charged to the +caller in addition to being charged to the callee. +.(z +.so postp1.pic +.ce 2 +Topological ordering +Figure 1. +.ce 0 +.)z +.pp +Let $C sub e$ be the number of calls to some routine, +$e$, and $C sub e sup r$ be the number of +calls from a caller $r$ to a callee $e$. +Since we are assuming each call to a routine takes the +average amount of time for all calls to that routine, +the caller is accountable for +$C sub e sup r / C sub e$ +of the time spent by the callee. +Let the $S sub e$ be the $selftime$ of a routine, $e$. +The selftime of a routine can be determined from the +timing information gathered during profiled program execution. +The total time, $T sub r$, we wish to account to a routine +$r$, is then given by the recurrence equation: +.EQ +T sub r ~ = ~ {S sub r} ~ + ~ + sum from {r ~ roman CALLS ~ e} + {T sub e times {{C sub e sup r} over {C sub e}}} +.EN +where $r ~ roman CALLS ~ e$ is a relation showing all routines +$e$ called by a routine $r$. +This relation is easily available from the call graph. +.pp +However, if the execution contains recursive calls, +the call graph has cycles that +cannot be topologically sorted. +In these cases, we discover strongly-connected +components in the call graph, +treat each such component as a single node, +and then sort the resulting graph. +We use a variation of Tarjan's strongly-connected +components algorithm +that discovers strongly-connected components as it is assigning +topological order numbers [Tarjan72]. +.pp +Time propagation within strongly connected +components is a problem. +For example, a self-recursive routine +(a trivial cycle in the call graph) +is accountable for all the time it +uses in all its recursive instantiations. +In our scheme, this time should be +shared among its call graph parents. +The arcs from a routine to itself are of interest, +but do not participate in time propagation. +Thus the simple equation for time propagation +does not work within strongly connected components. +Time is not propagated from one member of a cycle to another, +since, by definition, this involves propagating time from a routine +to itself. +In addition, children of one member of a cycle +must be considered children of all members of the cycle. +Similarly, parents of one member of the cycle must inherit +all members of the cycle as descendants. +It is for these reasons that we collapse connected components. +Our solution collects all members of a cycle together, +summing the time and call counts for all members. +All calls into the cycle are made to share the total +time of the cycle, and all descendants of the cycle +propagate time into the cycle as a whole. +Calls among the members of the cycle +do not propagate any time, +though they are listed in the call graph profile. +.pp +Figure 2 shows a modified version of the call graph of Figure 1, +in which the nodes labelled 3 and 7 in Figure 1 are mutually +recursive. +The topologically sorted graph after the cycle is collapsed is +given in Figure 3. +.(z +.so postp2.pic +.ce 2 +Cycle to be collapsed. +Figure 2. +.ce 0 +.)z +.(z +.so postp3.pic +.ce 2 +Topological numbering after cycle collapsing. +Figure 3. +.ce 0 +.)z +.pp +Since the technique described above only collects the +dynamic call graph, +and the program typically does not call every routine +on each execution, +different executions can introduce different cycles in the +dynamic call graph. +Since cycles often have a significant effect on time propagation, +it is desirable to incorporate the static call graph so that cycles +will have the same members regardless of how the program runs. +.pp +The static call graph can be constructed from the source text +of the program. +However, discovering the static call graph from the source text +would require two moderately difficult steps: +finding the source text for the program +(which may not be available), +and scanning and parsing that text, +which may be in any one of several languages. +.pp +In our programming system, +the static calling information is also contained in the +executable version of the program, +which we already have available, +and which is in language-independent form. +One can examine the instructions +in the object program, +looking for calls to routines, and note which +routines can be called. +This technique allows us to add arcs to those already in the +dynamic call graph. +If a statically discovered arc already exists in the dynamic call +graph, no action is required. +Statically discovered arcs that do not exist in the dynamic call +graph are added to the graph with a traversal count of zero. +Thus they are never responsible for any time propagation. +However, they may affect the structure of the graph. +Since they may complete strongly connected components, +the static call graph construction is +done before topological ordering. diff --git a/usr.bin/gprof/PSD.doc/postp1.pic b/usr.bin/gprof/PSD.doc/postp1.pic new file mode 100644 index 00000000000..7a776a725db --- /dev/null +++ b/usr.bin/gprof/PSD.doc/postp1.pic @@ -0,0 +1,56 @@ +.\" $NetBSD: postp1.pic,v 1.2 1995/04/19 07:16:46 cgd Exp $ +.\" +.\" Copyright (c) 1986, 1993 +.\" The Regents of the University of California. All rights reserved. +.\" +.\" Redistribution and use in source and binary forms, with or without +.\" modification, are permitted provided that the following conditions +.\" are met: +.\" 1. Redistributions of source code must retain the above copyright +.\" notice, this list of conditions and the following disclaimer. +.\" 2. Redistributions in binary form must reproduce the above copyright +.\" notice, this list of conditions and the following disclaimer in the +.\" documentation and/or other materials provided with the distribution. +.\" 3. All advertising materials mentioning features or use of this software +.\" must display the following acknowledgement: +.\" This product includes software developed by the University of +.\" California, Berkeley and its contributors. +.\" 4. Neither the name of the University nor the names of its contributors +.\" may be used to endorse or promote products derived from this software +.\" without specific prior written permission. +.\" +.\" THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND +.\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE +.\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE +.\" ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE +.\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL +.\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS +.\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) +.\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT +.\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY +.\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF +.\" SUCH DAMAGE. +.\" +.\" @(#)postp1.pic 8.1 (Berkeley) 6/8/93 +.\" +.PS +circle diam .3i "8" +circle diam .3i "9" at 1st circle + (2i,0i) +circle diam .3i "3" at 1st circle + (0.5i,-0.5i) +circle diam .3i "7" at 2nd circle - (0.5i, 0.5i) +circle diam .3i "2" at 1st circle - (0i,1i) +circle diam .3i "5" at 5th circle + (1i,0i) +circle diam .3i "6" at 2nd circle - (0i,1i) +circle diam .3i "1" at 3rd circle - (0i,1i) +circle diam .3i "4" at 4th circle - (0i,1i) +arrow from 1st circle to 3rd circle chop .15i chop .15i +arrow from 1st circle to 4th circle chop .15i chop .15i +arrow from 2nd circle to 4th circle chop .15i chop .15i +arrow from 3rd circle to 5th circle chop .15i chop .15i +arrow from 4th circle to 5th circle chop .15i chop .15i +arrow from 4th circle to 6th circle chop .15i chop .15i +arrow from 4th circle to 7th circle chop .15i chop .15i +arrow from 5th circle to 8th circle chop .15i chop .15i +arrow from 6th circle to 8th circle chop .15i chop .15i +arrow from 6th circle to 9th circle chop .15i chop .15i +.PE diff --git a/usr.bin/gprof/PSD.doc/postp2.pic b/usr.bin/gprof/PSD.doc/postp2.pic new file mode 100644 index 00000000000..5d90291f357 --- /dev/null +++ b/usr.bin/gprof/PSD.doc/postp2.pic @@ -0,0 +1,58 @@ +.\" $NetBSD: postp2.pic,v 1.2 1995/04/19 07:16:48 cgd Exp $ +.\" +.\" Copyright (c) 1986, 1993 +.\" The Regents of the University of California. All rights reserved. +.\" +.\" Redistribution and use in source and binary forms, with or without +.\" modification, are permitted provided that the following conditions +.\" are met: +.\" 1. Redistributions of source code must retain the above copyright +.\" notice, this list of conditions and the following disclaimer. +.\" 2. Redistributions in binary form must reproduce the above copyright +.\" notice, this list of conditions and the following disclaimer in the +.\" documentation and/or other materials provided with the distribution. +.\" 3. All advertising materials mentioning features or use of this software +.\" must display the following acknowledgement: +.\" This product includes software developed by the University of +.\" California, Berkeley and its contributors. +.\" 4. Neither the name of the University nor the names of its contributors +.\" may be used to endorse or promote products derived from this software +.\" without specific prior written permission. +.\" +.\" THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND +.\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE +.\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE +.\" ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE +.\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL +.\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS +.\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) +.\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT +.\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY +.\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF +.\" SUCH DAMAGE. +.\" +.\" @(#)postp2.pic 8.1 (Berkeley) 6/8/93 +.\" +.PS +circle diam .3i "\(ci" +circle diam .3i "\(ci" at 1st circle + (2i,0i) +circle diam .3i "\(bu" at 1st circle + (0.5i,-0.5i) +circle diam .3i "\(bu" at 2nd circle - (0.5i, 0.5i) +circle diam .3i "\(ci" at 1st circle - (0i,1i) +circle diam .3i "\(ci" at 5th circle + (1i,0i) +circle diam .3i "\(ci" at 2nd circle - (0i,1i) +circle diam .3i "\(ci" at 3rd circle - (0i,1i) +circle diam .3i "\(ci" at 4th circle - (0i,1i) +arrow from 1st circle to 3rd circle chop .15i chop .15i +arrow from 1st circle to 4th circle chop .15i chop .15i +arrow from 2nd circle to 4th circle chop .15i chop .15i +spline -> from 3rd circle right .5i up .075i then right .5i down .075i chop .15i chop .15i +spline -> from 4th circle left .5i down .075i then left .5i up .075i chop .15i chop .15i +arrow from 3rd circle to 5th circle chop .15i chop .15i +arrow from 4th circle to 5th circle chop .15i chop .15i +arrow from 4th circle to 6th circle chop .15i chop .15i +arrow from 4th circle to 7th circle chop .15i chop .15i +arrow from 5th circle to 8th circle chop .15i chop .15i +arrow from 6th circle to 8th circle chop .15i chop .15i +arrow from 6th circle to 9th circle chop .15i chop .15i +.PE diff --git a/usr.bin/gprof/PSD.doc/postp3.pic b/usr.bin/gprof/PSD.doc/postp3.pic new file mode 100644 index 00000000000..4a3ce97a62e --- /dev/null +++ b/usr.bin/gprof/PSD.doc/postp3.pic @@ -0,0 +1,53 @@ +.\" $NetBSD: postp3.pic,v 1.2 1995/04/19 07:16:50 cgd Exp $ +.\" +.\" Copyright (c) 1986, 1993 +.\" The Regents of the University of California. All rights reserved. +.\" +.\" Redistribution and use in source and binary forms, with or without +.\" modification, are permitted provided that the following conditions +.\" are met: +.\" 1. Redistributions of source code must retain the above copyright +.\" notice, this list of conditions and the following disclaimer. +.\" 2. Redistributions in binary form must reproduce the above copyright +.\" notice, this list of conditions and the following disclaimer in the +.\" documentation and/or other materials provided with the distribution. +.\" 3. All advertising materials mentioning features or use of this software +.\" must display the following acknowledgement: +.\" This product includes software developed by the University of +.\" California, Berkeley and its contributors. +.\" 4. Neither the name of the University nor the names of its contributors +.\" may be used to endorse or promote products derived from this software +.\" without specific prior written permission. +.\" +.\" THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND +.\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE +.\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE +.\" ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE +.\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL +.\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS +.\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) +.\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT +.\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY +.\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF +.\" SUCH DAMAGE. +.\" +.\" @(#)postp3.pic 8.1 (Berkeley) 6/8/93 +.\" +.PS +circle diam .3i "7" +circle diam .3i "8" at 1st circle + (2i,0i) +EL: ellipse wid 1i ht .3i "\fB6\fR\h'.7i'\fB6\fR" at 1st circle + (1i,-0.5i) +circle diam .3i "2" at 1st circle - (0i,1i) +circle diam .3i "4" at 3th circle + (1i,0i) +circle diam .3i "5" at 2nd circle - (0i,1i) +circle diam .3i "1" at 3rd circle + (0.5i,-0.5i) +circle diam .3i "3" at 5th circle - (0.5i,0.5i) +arrow from 1st circle to EL.nw chop .15i chop 0i +arrow from 2nd circle to EL.ne chop .15i chop 0i +arrow from EL.sw to 3rd circle chop 0i chop .15i +arrow from EL.s to 4th circle chop 0i chop .15i +arrow from EL.se to 5th circle chop 0i chop .15i +arrow from 3rd circle to 6th circle chop .15i chop .15i +arrow from 4th circle to 6th circle chop .15i chop .15i +arrow from 4th circle to 7th circle chop .15i chop .15i +.PE diff --git a/usr.bin/gprof/PSD.doc/pres1.pic b/usr.bin/gprof/PSD.doc/pres1.pic new file mode 100644 index 00000000000..50f33f9a5a6 --- /dev/null +++ b/usr.bin/gprof/PSD.doc/pres1.pic @@ -0,0 +1,58 @@ +.\" $NetBSD: pres1.pic,v 1.2 1995/04/19 07:16:52 cgd Exp $ +.\" +.\" Copyright (c) 1986, 1993 +.\" The Regents of the University of California. All rights reserved. +.\" +.\" Redistribution and use in source and binary forms, with or without +.\" modification, are permitted provided that the following conditions +.\" are met: +.\" 1. Redistributions of source code must retain the above copyright +.\" notice, this list of conditions and the following disclaimer. +.\" 2. Redistributions in binary form must reproduce the above copyright +.\" notice, this list of conditions and the following disclaimer in the +.\" documentation and/or other materials provided with the distribution. +.\" 3. All advertising materials mentioning features or use of this software +.\" must display the following acknowledgement: +.\" This product includes software developed by the University of +.\" California, Berkeley and its contributors. +.\" 4. Neither the name of the University nor the names of its contributors +.\" may be used to endorse or promote products derived from this software +.\" without specific prior written permission. +.\" +.\" THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND +.\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE +.\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE +.\" ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE +.\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL +.\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS +.\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) +.\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT +.\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY +.\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF +.\" SUCH DAMAGE. +.\" +.\" @(#)pres1.pic 8.1 (Berkeley) 6/8/93 +.\" +.PS +ellipse ht .3i wid .75i "\s-1CALLER1\s+1" +ellipse ht .3i wid .75i "\s-1CALLER2\s+1" at 1st ellipse + (2i,0i) +ellipse ht .3i wid .8i "\s-1EXAMPLE\s+1" at 1st ellipse + (1i,-.5i) +ellipse ht .3i wid .5i "\s-1SUB1\s+1" at 1st ellipse - (0i,1i) +ellipse ht .3i wid .5i "\s-1SUB2\s+1" at 3rd ellipse - (0i,.5i) +ellipse ht .3i wid .5i "\s-1SUB3\s+1" at 2nd ellipse - (0i,1i) +line <- from 1st ellipse up .5i left .5i chop .1875i +line <- from 1st ellipse up .5i right .5i chop .1875i +line <- from 2nd ellipse up .5i left .5i chop .1875i +line <- from 2nd ellipse up .5i right .5i chop .1875i +arrow from 1st ellipse to 3rd ellipse chop +arrow from 2nd ellipse to 3rd ellipse chop +arrow from 3rd ellipse to 4th ellipse chop +arrow from 3rd ellipse to 5th ellipse chop .15i chop .15i +arrow from 3rd ellipse to 6th ellipse chop +arrow from 4th ellipse down .5i left .5i chop .1875i +arrow from 4th ellipse down .5i right .5i chop .1875i +arrow from 5th ellipse down .5i left .5i chop .1875i +arrow from 5th ellipse down .5i right .5i chop .1875i +arrow from 6th ellipse down .5i left .5i chop .1875i +arrow from 6th ellipse down .5i right .5i chop .1875i +.PE diff --git a/usr.bin/gprof/PSD.doc/pres2.pic b/usr.bin/gprof/PSD.doc/pres2.pic new file mode 100644 index 00000000000..acb32c1e61e --- /dev/null +++ b/usr.bin/gprof/PSD.doc/pres2.pic @@ -0,0 +1,54 @@ +.\" $NetBSD: pres2.pic,v 1.2 1995/04/19 07:16:53 cgd Exp $ +.\" +.\" Copyright (c) 1986, 1993 +.\" The Regents of the University of California. All rights reserved. +.\" +.\" Redistribution and use in source and binary forms, with or without +.\" modification, are permitted provided that the following conditions +.\" are met: +.\" 1. Redistributions of source code must retain the above copyright +.\" notice, this list of conditions and the following disclaimer. +.\" 2. Redistributions in binary form must reproduce the above copyright +.\" notice, this list of conditions and the following disclaimer in the +.\" documentation and/or other materials provided with the distribution. +.\" 3. All advertising materials mentioning features or use of this software +.\" must display the following acknowledgement: +.\" This product includes software developed by the University of +.\" California, Berkeley and its contributors. +.\" 4. Neither the name of the University nor the names of its contributors +.\" may be used to endorse or promote products derived from this software +.\" without specific prior written permission. +.\" +.\" THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND +.\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE +.\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE +.\" ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE +.\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL +.\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS +.\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) +.\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT +.\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY +.\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF +.\" SUCH DAMAGE. +.\" +.\" @(#)pres2.pic 8.1 (Berkeley) 6/8/93 +.\" +.PS +ellipse ht .3i wid .6i "\s-1CALC1\s+1" +ellipse ht .3i wid .6i "\s-1CALC2\s+1" at 1st ellipse + (.75i,0i) +ellipse ht .3i wid .6i "\s-1CALC3\s+1" at 1st ellipse + (1.5i,0i) +ellipse ht .3i wid .8i "\s-1FORMAT1\s+1" at 1st ellipse - (0i,.5i) +ellipse ht .3i wid .8i "\s-1FORMAT2\s+1" at 3rd ellipse - (0i,.5i) +ellipse ht .3i wid .75i "\s-1\"WRITE\"\s+1" at 5th ellipse - (.75i,.5i) +line <- from 1st ellipse up .5i left .4i chop .1825i +line <- from 1st ellipse up .5i right .4i chop .1825i +line <- from 2nd ellipse up .5i left .4i chop .1825i +line <- from 2nd ellipse up .5i right .4i chop .1825i +line <- from 3rd ellipse up .5i left .4i chop .1825i +line <- from 3rd ellipse up .5i right .4i chop .1825i +arrow from 1st ellipse to 4th ellipse chop .15i +arrow from 2nd ellipse to 5th ellipse chop +arrow from 3rd ellipse to 5th ellipse chop .15i +arrow from 4th ellipse to 6th ellipse chop +arrow from 5th ellipse to 6th ellipse chop +.PE diff --git a/usr.bin/gprof/PSD.doc/present.me b/usr.bin/gprof/PSD.doc/present.me new file mode 100644 index 00000000000..04b6ab314f1 --- /dev/null +++ b/usr.bin/gprof/PSD.doc/present.me @@ -0,0 +1,308 @@ +.\" $NetBSD: present.me,v 1.2 1995/04/19 07:16:54 cgd Exp $ +.\" +.\" Copyright (c) 1982, 1993 +.\" The Regents of the University of California. All rights reserved. +.\" +.\" Redistribution and use in source and binary forms, with or without +.\" modification, are permitted provided that the following conditions +.\" are met: +.\" 1. Redistributions of source code must retain the above copyright +.\" notice, this list of conditions and the following disclaimer. +.\" 2. Redistributions in binary form must reproduce the above copyright +.\" notice, this list of conditions and the following disclaimer in the +.\" documentation and/or other materials provided with the distribution. +.\" 3. All advertising materials mentioning features or use of this software +.\" must display the following acknowledgement: +.\" This product includes software developed by the University of +.\" California, Berkeley and its contributors. +.\" 4. Neither the name of the University nor the names of its contributors +.\" may be used to endorse or promote products derived from this software +.\" without specific prior written permission. +.\" +.\" THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND +.\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE +.\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE +.\" ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE +.\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL +.\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS +.\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) +.\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT +.\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY +.\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF +.\" SUCH DAMAGE. +.\" +.\" @(#)present.me 8.1 (Berkeley) 6/8/93 +.\" +.sh 1 "Data Presentation" +.pp +The data is presented to the user in two different formats. +The first presentation simply lists the routines +without regard to the amount of time their descendants use. +The second presentation incorporates the call graph of the +program. +.sh 2 "The Flat Profile +.pp +The flat profile consists of a list of all the routines +that are called during execution of the program, +with the count of the number of times they are called +and the number of seconds of execution time for which they +are themselves accountable. +The routines are listed in decreasing order of execution time. +A list of the routines that are never called during execution of +the program is also available +to verify that nothing important is omitted by +this execution. +The flat profile gives a quick overview of the routines that are used, +and shows the routines that are themselves responsible +for large fractions of the execution time. +In practice, +this profile usually shows that no single function +is overwhelmingly responsible for +the total time of the program. +Notice that for this profile, +the individual times sum to the total execution time. +.sh 2 "The Call Graph Profile" +.sz 10 +.(z +.TS +box center; +c c c c c l l +c c c c c l l +c c c c c l l +l n n n c l l. + called/total \ \ parents +index %time self descendants called+self name index + called/total \ \ children +_ + 0.20 1.20 4/10 \ \ \s-1CALLER1\s+1 [7] + 0.30 1.80 6/10 \ \ \s-1CALLER2\s+1 [1] +[2] 41.5 0.50 3.00 10+4 \s-1EXAMPLE\s+1 [2] + 1.50 1.00 20/40 \ \ \s-1SUB1\s+1 <cycle1> [4] + 0.00 0.50 1/5 \ \ \s-1SUB2\s+1 [9] + 0.00 0.00 0/5 \ \ \s-1SUB3\s+1 [11] +.TE +.ce 2 +Profile entry for \s-1EXAMPLE\s+1. +Figure 4. +.)z +.pp +Ideally, we would like to print the call graph of the program, +but we are limited by the two-dimensional nature of our output +devices. +We cannot assume that a call graph is planar, +and even if it is, that we can print a planar version of it. +Instead, we choose to list each routine, +together with information about +the routines that are its direct parents and children. +This listing presents a window into the call graph. +Based on our experience, +both parent information and child information +is important, +and should be available without searching +through the output. +.pp +The major entries of the call graph profile are the entries from the +flat profile, augmented by the time propagated to each +routine from its descendants. +This profile is sorted by the sum of the time for the routine +itself plus the time inherited from its descendants. +The profile shows which of the higher level routines +spend large portions of the total execution time +in the routines that they call. +For each routine, we show the amount of time passed by each child +to the routine, which includes time for the child itself +and for the descendants of the child +(and thus the descendants of the routine). +We also show the percentage these times represent of the total time +accounted to the child. +Similarly, the parents of each routine are listed, +along with time, +and percentage of total routine time, +propagated to each one. +.pp +Cycles are handled as single entities. +The cycle as a whole is shown as though it were a single routine, +except that members of the cycle are listed in place of the children. +Although the number of calls of each member +from within the cycle are shown, +they do not affect time propagation. +When a child is a member of a cycle, +the time shown is the appropriate fraction of the time +for the whole cycle. +Self-recursive routines have their calls broken +down into calls from the outside and self-recursive calls. +Only the outside calls affect the propagation of time. +.pp +The following example is a typical fragment of a call graph. +.(b +.so pres1.pic +.)b +The entry in the call graph profile listing for this example is +shown in Figure 4. +.pp +The entry is for routine \s-1EXAMPLE\s+1, which has +the Caller routines as its parents, +and the Sub routines as its children. +The reader should keep in mind that all information +is given \fIwith respect to \s-1EXAMPLE\s+1\fP. +The index in the first column shows that \s-1EXAMPLE\s+1 +is the second entry in the profile listing. +The \s-1EXAMPLE\s+1 routine is called ten times, four times by \s-1CALLER1\s+1, +and six times by \s-1CALLER2\s+1. +Consequently 40% of \s-1EXAMPLE\s+1's time is propagated to \s-1CALLER1\s+1, +and 60% of \s-1EXAMPLE\s+1's time is propagated to \s-1CALLER2\s+1. +The self and descendant fields of the parents +show the amount of self and descendant time \s-1EXAMPLE\s+1 +propagates to them (but not the time used by +the parents directly). +Note that \s-1EXAMPLE\s+1 calls itself recursively four times. +The routine \s-1EXAMPLE\s+1 calls routine \s-1SUB1\s+1 twenty times, \s-1SUB2\s+1 once, +and never calls \s-1SUB3\s+1. +Since \s-1SUB2\s+1 is called a total of five times, +20% of its self and descendant time is propagated to \s-1EXAMPLE\s+1's +descendant time field. +Because \s-1SUB1\s+1 is a member of \fIcycle 1\fR, +the self and descendant times +and call count fraction +are those for the cycle as a whole. +Since cycle 1 is called a total of forty times +(not counting calls among members of the cycle), +it propagates 50% of the cycle's self and descendant +time to \s-1EXAMPLE\s+1's descendant time field. +Finally each name is followed by an index that shows +where on the listing to find the entry for that routine. +.sh 1 "Using the Profiles" +.pp +The profiler is a useful tool for improving +a set of routines that implement an abstraction. +It can be helpful in identifying poorly coded routines, +and in evaluating the new algorithms and code that replace them. +Taking full advantage of the profiler +requires a careful examination of the call graph profile, +and a thorough knowledge of the abstractions underlying +the program. +.pp +The easiest optimization that can be performed +is a small change +to a control construct or data structure that improves the +running time of the program. +An obvious starting point +is a routine that is called many times. +For example, suppose an output +routine is the only parent +of a routine that formats the data. +If this format routine is expanded inline in the +output routine, the overhead of a function call and +return can be saved for each datum that needs to be formatted. +.pp +The drawback to inline expansion is that the data abstractions +in the program may become less parameterized, +hence less clearly defined. +The profiling will also become less useful since the loss of +routines will make its output more granular. +For example, +if the symbol table functions ``lookup'', ``insert'', and ``delete'' +are all merged into a single parameterized routine, +it will be impossible to determine the costs +of any one of these individual functions from the profile. +.pp +Further potential for optimization lies in routines that +implement data abstractions whose total execution +time is long. +For example, a lookup routine might be called only a few +times, but use an inefficient linear search algorithm, +that might be replaced with a binary search. +Alternately, the discovery that a rehashing function is being +called excessively, can lead to a different +hash function or a larger hash table. +If the data abstraction function cannot easily be speeded up, +it may be advantageous to cache its results, +and eliminate the need to rerun +it for identical inputs. +These and other ideas for program improvement are discussed in +[Bentley81]. +.pp +This tool is best used in an iterative approach: +profiling the program, +eliminating one bottleneck, +then finding some other part of the program +that begins to dominate execution time. +For instance, we have used \fBgprof\fR on itself; +eliminating, rewriting, and inline expanding routines, +until reading +data files (hardly a target for optimization!) +represents the dominating factor in its execution time. +.pp +Certain types of programs are not easily analyzed by \fBgprof\fR. +They are typified by programs that exhibit a large degree of +recursion, such as recursive descent compilers. +The problem is that most of the major routines are grouped +into a single monolithic cycle. +As in the symbol table abstraction that is placed +in one routine, +it is impossible to distinguish which members of the cycle are +responsible for the execution time. +Unfortunately there are no easy modifications to these programs that +make them amenable to analysis. +.pp +A completely different use of the profiler is to analyze the control +flow of an unfamiliar program. +If you receive a program from another user that you need to modify +in some small way, +it is often unclear where the changes need to be made. +By running the program on an example and then using \fBgprof\fR, +you can get a view of the structure of the program. +.pp +Consider an example in which you need to change the output format +of the program. +For purposes of this example suppose that the call graph +of the output portion of the program has the following structure: +.(b +.so pres2.pic +.)b +Initially you look through the \fBgprof\fR +output for the system call ``\s-1WRITE\s+1''. +The format routine you will need to change is probably +among the parents of the ``\s-1WRITE\s+1'' procedure. +The next step is to look at the profile entry for each +of parents of ``\s-1WRITE\s+1'', +in this example either ``\s-1FORMAT1\s+1'' or ``\s-1FORMAT2\s+1'', +to determine which one to change. +Each format routine will have one or more parents, +in this example ``\s-1CALC1\s+1'', ``\s-1CALC2\s+1'', and ``\s-1CALC3\s+1''. +By inspecting the source code for each of these routines +you can determine which format routine generates the output that +you wish to modify. +Since the \fBgprof\fR entry shows all the +potential calls to the format routine you intend to change, +you can determine if your modifications will affect output that +should be left alone. +If you desire to change the output of ``\s-1CALC2\s+1'', but not ``\s-1CALC3\s+1'', +then formatting routine ``\s-1FORMAT2\s+1'' needs to be split +into two separate routines, +one of which implements the new format. +You can then retarget just the call by ``\s-1CALC2\s+1'' +that needs the new format. +It should be noted that the static call information is particularly +useful here since the test case you run probably will not +exercise the entire program. +.sh 1 "Conclusions" +.pp +We have created a profiler that aids in the evaluation +of modular programs. +For each routine in the program, +the profile shows the extent to which that routine +helps support various abstractions, +and how that routine uses other abstractions. +The profile accurately assesses the cost of routines +at all levels of the program decomposition. +The profiler is easily used, +and can be compiled into the program without any prior planning by +the programmer. +It adds only five to thirty percent execution overhead to the program +being profiled, +produces no additional output until after the program finishes, +and allows the program to be measured in its actual environment. +Finally, the profiler runs on a time-sharing system +using only the normal services provided by the operating system +and compilers. diff --git a/usr.bin/gprof/PSD.doc/profiling.me b/usr.bin/gprof/PSD.doc/profiling.me new file mode 100644 index 00000000000..13c375c602e --- /dev/null +++ b/usr.bin/gprof/PSD.doc/profiling.me @@ -0,0 +1,117 @@ +.\" $NetBSD: profiling.me,v 1.2 1995/04/19 07:16:56 cgd Exp $ +.\" +.\" Copyright (c) 1982, 1993 +.\" The Regents of the University of California. All rights reserved. +.\" +.\" Redistribution and use in source and binary forms, with or without +.\" modification, are permitted provided that the following conditions +.\" are met: +.\" 1. Redistributions of source code must retain the above copyright +.\" notice, this list of conditions and the following disclaimer. +.\" 2. Redistributions in binary form must reproduce the above copyright +.\" notice, this list of conditions and the following disclaimer in the +.\" documentation and/or other materials provided with the distribution. +.\" 3. All advertising materials mentioning features or use of this software +.\" must display the following acknowledgement: +.\" This product includes software developed by the University of +.\" California, Berkeley and its contributors. +.\" 4. Neither the name of the University nor the names of its contributors +.\" may be used to endorse or promote products derived from this software +.\" without specific prior written permission. +.\" +.\" THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND +.\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE +.\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE +.\" ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE +.\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL +.\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS +.\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) +.\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT +.\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY +.\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF +.\" SUCH DAMAGE. +.\" +.\" @(#)profiling.me 8.1 (Berkeley) 6/8/93 +.\" +.sh 1 "Types of Profiling" +.pp +There are several different uses for program profiles, +and each may require different information from the profiles, +or different presentation of the information. +We distinguish two broad categories of profiles: +those that present counts of statement or routine invocations, +and those that display timing information about statements +or routines. +Counts are typically presented in tabular form, +often in parallel with a listing of the source code. +Timing information could be similarly presented; +but more than one measure of time might be associated with each +statement or routine. +For example, +in the framework used by \fBgprof\fP +each profiled segment would display two times: +one for the time used by the segment itself, and another for the +time inherited from code segments it invokes. +.pp +Execution counts are used in many different contexts. +The exact number of times a routine or statement is activated +can be used to determine if an algorithm is performing as +expected. +Cursory inspection of such counters may show algorithms whose +complexity is unsuited to the task at hand. +Careful interpretation of counters can often suggest +improvements to acceptable algorithms. +Precise examination can uncover subtle errors in an +algorithm. +At this level, profiling counters are similar to +debugging statements whose purpose is to show the number of times +a piece of code is executed. +Another view of such counters is as boolean values. +One may be interested that a portion of code has executed at +all, for exhaustive testing, or to check that one implementation +of an abstraction completely replaces a previous one. +.pp +Execution counts are not necessarily proportional to the amount +of time required to execute the routine or statement. +Further, the execution time of a routine will not be the same for +all calls on the routine. +The criteria for establishing execution time +must be decided. +If a routine implements an abstraction by invoking other abstractions, +the time spent in the routine will not accurately reflect the +time required by the abstraction it implements. +Similarly, if an abstraction is implemented by several +routines the time required by the abstraction will be distributed +across those routines. +.pp +Given the execution time of individual routines, +\fBgprof\fP accounts to each routine the time spent +for it by the routines it invokes. +This accounting is done by assembling a \fIcall graph\fP with nodes that +are the routines of the program and directed arcs that represent +calls from call sites to routines. +We distinguish among three different call graphs for a program. +The \fIcomplete call graph\fP incorporates all routines and all +potential arcs, +including arcs that represent calls to functional parameters +or functional variables. +This graph contains the other two graphs as subgraphs. +The \fIstatic call graph\fP includes all routines and all possible arcs +that are not calls to functional parameters or variables. +The \fIdynamic call graph\fP includes only those routines and +arcs traversed by the profiled execution of the program. +This graph need not include all routines, nor need it include all +potential arcs between the routines it covers. +It may, however, include arcs to functional parameters or +variables that the static call graph may omit. +The static call graph can be determined from the (static) program text. +The dynamic call graph is determined only by profiling an +execution of the program. +The complete call graph for a monolithic program could be determined +by data flow analysis techniques. +The complete call graph for programs that change +during execution, by modifying themselves or dynamically loading +or overlaying code, may never be determinable. +Both the static call graph and the dynamic call graph are used +by \fBgprof\fP, but it does not search for the complete call +graph. diff --git a/usr.bin/gprof/PSD.doc/refs.me b/usr.bin/gprof/PSD.doc/refs.me new file mode 100644 index 00000000000..a027b01e559 --- /dev/null +++ b/usr.bin/gprof/PSD.doc/refs.me @@ -0,0 +1,65 @@ +.\" $NetBSD: refs.me,v 1.2 1995/04/19 07:16:58 cgd Exp $ +.\" +.\" Copyright (c) 1982, 1993 +.\" The Regents of the University of California. All rights reserved. +.\" +.\" Redistribution and use in source and binary forms, with or without +.\" modification, are permitted provided that the following conditions +.\" are met: +.\" 1. Redistributions of source code must retain the above copyright +.\" notice, this list of conditions and the following disclaimer. +.\" 2. Redistributions in binary form must reproduce the above copyright +.\" notice, this list of conditions and the following disclaimer in the +.\" documentation and/or other materials provided with the distribution. +.\" 3. All advertising materials mentioning features or use of this software +.\" must display the following acknowledgement: +.\" This product includes software developed by the University of +.\" California, Berkeley and its contributors. +.\" 4. Neither the name of the University nor the names of its contributors +.\" may be used to endorse or promote products derived from this software +.\" without specific prior written permission. +.\" +.\" THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND +.\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE +.\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE +.\" ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE +.\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL +.\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS +.\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) +.\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT +.\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY +.\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF +.\" SUCH DAMAGE. +.\" +.\" @(#)refs.me 8.1 (Berkeley) 6/8/93 +.\" +.sh 1 "References" +.ls 1 +.ip [Bentley81] +Bentley, J. L., +``Writing Efficient Code'', +Department of Computer Science, +Carnegie-Mellon University, +Pittsburgh, Pennsylvania, +CMU-CS-81-116, 1981. +.ip [Graham82] +Graham, S. L., Henry, R. R., Schulman, R. A., +``An Experiment in Table Driven Code Generation'', +SIGPLAN '82 Symposium on Compiler Construction, +June, 1982. +.ip [Joy79] +Joy, W. N., Graham, S. L., Haley, C. B. ``Berkeley Pascal User's Manual'', +Version 1.1, Computer Science Division +University of California, Berkeley, CA. April 1979. +.ip [Knuth71] +Knuth, D. E. ``An empirical study of FORTRAN programs'', +Software - Practice and Experience, 1, 105-133. 1971 +.ip [Satterthwaite72] +Satterthwaite, E. ``Debugging Tools for High Level Languages'', +Software - Practice and Experience, 2, 197-217, 1972 +.ip [Tarjan72] +Tarjan, R. E., ``Depth first search and linear graph algorithm,'' +\fISIAM J. Computing\fP \fB1\fP:2, 146-160, 1972. +.ip [Unix] +Unix Programmer's Manual, ``\fBprof\fR command'', section 1, +Bell Laboratories, Murray Hill, NJ. January 1979. |