BSD 4.4 Lite Usr.bin Sources

14 files changed, 1371 insertions, 0 deletions

diff --git a/usr.bin/gprof/PSD.doc/Makefile b/usr.bin/gprof/PSD.doc/Makefile
new file mode 100644
index 0000000..12f9c39
--- /dev/null
+++ b/usr.bin/gprof/PSD.doc/Makefile
@@ -0,0 +1,12 @@
+#	@(#)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
+DPADD=	postp1.pic postp2.pic postp3.pic pres1.pic pres2.pic
+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 0000000..28e8066
--- /dev/null
+++ b/usr.bin/gprof/PSD.doc/abstract.me
@@ -0,0 +1,66 @@
+.\" 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 0000000..17130c3
--- /dev/null
+++ b/usr.bin/gprof/PSD.doc/gathering.me
@@ -0,0 +1,231 @@
+.\" 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 0000000..aef606d
--- /dev/null
+++ b/usr.bin/gprof/PSD.doc/header.me
@@ -0,0 +1,38 @@
+.\" 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 0000000..3a872b2
--- /dev/null
+++ b/usr.bin/gprof/PSD.doc/intro.me
@@ -0,0 +1,81 @@
+.\" 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 0000000..d71fefb
--- /dev/null
+++ b/usr.bin/gprof/PSD.doc/postp.me
@@ -0,0 +1,190 @@
+.\" 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 0000000..1446092
--- /dev/null
+++ b/usr.bin/gprof/PSD.doc/postp1.pic
@@ -0,0 +1,54 @@
+.\" 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 0000000..3b31736
--- /dev/null
+++ b/usr.bin/gprof/PSD.doc/postp2.pic
@@ -0,0 +1,56 @@
+.\" 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 0000000..65eb2a7
--- /dev/null
+++ b/usr.bin/gprof/PSD.doc/postp3.pic
@@ -0,0 +1,51 @@
+.\" 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 0000000..0c311a1
--- /dev/null
+++ b/usr.bin/gprof/PSD.doc/pres1.pic
@@ -0,0 +1,56 @@
+.\" 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 0000000..c3a4ea0
--- /dev/null
+++ b/usr.bin/gprof/PSD.doc/pres2.pic
@@ -0,0 +1,52 @@
+.\" 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 0000000..1dd7f62
--- /dev/null
+++ b/usr.bin/gprof/PSD.doc/present.me
@@ -0,0 +1,306 @@
+.\" 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 0000000..227aedf
--- /dev/null
+++ b/usr.bin/gprof/PSD.doc/profiling.me
@@ -0,0 +1,115 @@
+.\" 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 0000000..580d080
--- /dev/null
+++ b/usr.bin/gprof/PSD.doc/refs.me
@@ -0,0 +1,63 @@
+.\" 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.