diff options
author | uqs <uqs@FreeBSD.org> | 2010-12-04 10:11:20 +0000 |
---|---|---|
committer | uqs <uqs@FreeBSD.org> | 2010-12-04 10:11:20 +0000 |
commit | 9242c645f81d22058934688725f1fff0bc88cb64 (patch) | |
tree | a39140e4d881fbba4f04ac77974bfbb05df9d360 /usr.bin/gprof | |
parent | 06cd6f2bc1f94f941b57ef92ed6445529822669b (diff) | |
download | FreeBSD-src-9242c645f81d22058934688725f1fff0bc88cb64.zip FreeBSD-src-9242c645f81d22058934688725f1fff0bc88cb64.tar.gz |
Move most of the remaining USD/PSD/SMM papers into share/doc
Diffstat (limited to 'usr.bin/gprof')
-rw-r--r-- | usr.bin/gprof/PSD.doc/abstract.me | 66 | ||||
-rw-r--r-- | usr.bin/gprof/PSD.doc/gathering.me | 231 | ||||
-rw-r--r-- | usr.bin/gprof/PSD.doc/header.me | 38 | ||||
-rw-r--r-- | usr.bin/gprof/PSD.doc/intro.me | 81 | ||||
-rw-r--r-- | usr.bin/gprof/PSD.doc/postp.me | 190 | ||||
-rw-r--r-- | usr.bin/gprof/PSD.doc/postp1.pic | 54 | ||||
-rw-r--r-- | usr.bin/gprof/PSD.doc/postp2.pic | 56 | ||||
-rw-r--r-- | usr.bin/gprof/PSD.doc/postp3.pic | 51 | ||||
-rw-r--r-- | usr.bin/gprof/PSD.doc/pres1.pic | 56 | ||||
-rw-r--r-- | usr.bin/gprof/PSD.doc/pres2.pic | 52 | ||||
-rw-r--r-- | usr.bin/gprof/PSD.doc/present.me | 306 | ||||
-rw-r--r-- | usr.bin/gprof/PSD.doc/profiling.me | 115 | ||||
-rw-r--r-- | usr.bin/gprof/PSD.doc/refs.me | 63 |
13 files changed, 0 insertions, 1359 deletions
diff --git a/usr.bin/gprof/PSD.doc/abstract.me b/usr.bin/gprof/PSD.doc/abstract.me deleted file mode 100644 index 28e8066..0000000 --- a/usr.bin/gprof/PSD.doc/abstract.me +++ /dev/null @@ -1,66 +0,0 @@ -.\" 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 deleted file mode 100644 index 17130c3..0000000 --- a/usr.bin/gprof/PSD.doc/gathering.me +++ /dev/null @@ -1,231 +0,0 @@ -.\" 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 deleted file mode 100644 index aef606d..0000000 --- a/usr.bin/gprof/PSD.doc/header.me +++ /dev/null @@ -1,38 +0,0 @@ -.\" 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 deleted file mode 100644 index 3a872b2..0000000 --- a/usr.bin/gprof/PSD.doc/intro.me +++ /dev/null @@ -1,81 +0,0 @@ -.\" 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 deleted file mode 100644 index d71fefb..0000000 --- a/usr.bin/gprof/PSD.doc/postp.me +++ /dev/null @@ -1,190 +0,0 @@ -.\" 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 deleted file mode 100644 index 1446092..0000000 --- a/usr.bin/gprof/PSD.doc/postp1.pic +++ /dev/null @@ -1,54 +0,0 @@ -.\" 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 deleted file mode 100644 index 3b31736..0000000 --- a/usr.bin/gprof/PSD.doc/postp2.pic +++ /dev/null @@ -1,56 +0,0 @@ -.\" 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 deleted file mode 100644 index 65eb2a7..0000000 --- a/usr.bin/gprof/PSD.doc/postp3.pic +++ /dev/null @@ -1,51 +0,0 @@ -.\" 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 deleted file mode 100644 index 0c311a1..0000000 --- a/usr.bin/gprof/PSD.doc/pres1.pic +++ /dev/null @@ -1,56 +0,0 @@ -.\" 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 deleted file mode 100644 index c3a4ea0..0000000 --- a/usr.bin/gprof/PSD.doc/pres2.pic +++ /dev/null @@ -1,52 +0,0 @@ -.\" 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 deleted file mode 100644 index 1dd7f62..0000000 --- a/usr.bin/gprof/PSD.doc/present.me +++ /dev/null @@ -1,306 +0,0 @@ -.\" 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 deleted file mode 100644 index 227aedf..0000000 --- a/usr.bin/gprof/PSD.doc/profiling.me +++ /dev/null @@ -1,115 +0,0 @@ -.\" 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 deleted file mode 100644 index 580d080..0000000 --- a/usr.bin/gprof/PSD.doc/refs.me +++ /dev/null @@ -1,63 +0,0 @@ -.\" 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. |