summaryrefslogtreecommitdiffstats
path: root/usr.bin/gprof
diff options
context:
space:
mode:
Diffstat (limited to 'usr.bin/gprof')
-rw-r--r--usr.bin/gprof/Makefile12
-rw-r--r--usr.bin/gprof/PSD.doc/Makefile12
-rw-r--r--usr.bin/gprof/PSD.doc/abstract.me66
-rw-r--r--usr.bin/gprof/PSD.doc/gathering.me231
-rw-r--r--usr.bin/gprof/PSD.doc/header.me38
-rw-r--r--usr.bin/gprof/PSD.doc/intro.me81
-rw-r--r--usr.bin/gprof/PSD.doc/postp.me190
-rw-r--r--usr.bin/gprof/PSD.doc/postp1.pic54
-rw-r--r--usr.bin/gprof/PSD.doc/postp2.pic56
-rw-r--r--usr.bin/gprof/PSD.doc/postp3.pic51
-rw-r--r--usr.bin/gprof/PSD.doc/pres1.pic56
-rw-r--r--usr.bin/gprof/PSD.doc/pres2.pic52
-rw-r--r--usr.bin/gprof/PSD.doc/present.me306
-rw-r--r--usr.bin/gprof/PSD.doc/profiling.me115
-rw-r--r--usr.bin/gprof/PSD.doc/refs.me63
-rw-r--r--usr.bin/gprof/arcs.c950
-rw-r--r--usr.bin/gprof/dfn.c325
-rw-r--r--usr.bin/gprof/gprof.1281
-rw-r--r--usr.bin/gprof/gprof.c749
-rw-r--r--usr.bin/gprof/gprof.callg108
-rw-r--r--usr.bin/gprof/gprof.flat32
-rw-r--r--usr.bin/gprof/gprof.h347
-rw-r--r--usr.bin/gprof/hertz.c59
-rw-r--r--usr.bin/gprof/hp300.c11
-rw-r--r--usr.bin/gprof/hp300.h44
-rw-r--r--usr.bin/gprof/i386.c11
-rw-r--r--usr.bin/gprof/i386.h44
-rw-r--r--usr.bin/gprof/lookup.c115
-rw-r--r--usr.bin/gprof/mips.c112
-rw-r--r--usr.bin/gprof/mips.h50
-rw-r--r--usr.bin/gprof/pathnames.h38
-rw-r--r--usr.bin/gprof/printgprof.c718
-rw-r--r--usr.bin/gprof/printlist.c91
-rw-r--r--usr.bin/gprof/sparc.c110
-rw-r--r--usr.bin/gprof/sparc.h48
-rw-r--r--usr.bin/gprof/tahoe.c349
-rw-r--r--usr.bin/gprof/tahoe.h59
-rw-r--r--usr.bin/gprof/vax.c347
-rw-r--r--usr.bin/gprof/vax.h65
39 files changed, 6446 insertions, 0 deletions
diff --git a/usr.bin/gprof/Makefile b/usr.bin/gprof/Makefile
new file mode 100644
index 0000000..0762b78
--- /dev/null
+++ b/usr.bin/gprof/Makefile
@@ -0,0 +1,12 @@
+# @(#)Makefile 8.1 (Berkeley) 6/29/93
+
+PROG= gprof
+SRCS= gprof.c arcs.c dfn.c lookup.c ${MACHINE}.c hertz.c \
+ printgprof.c printlist.c
+
+beforeinstall:
+ install -c -o ${BINOWN} -g ${BINGRP} -m 444 \
+ ${.CURDIR}/gprof.flat ${.CURDIR}/gprof.callg \
+ ${DESTDIR}/usr/share/misc
+
+.include <bsd.prog.mk>
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.
diff --git a/usr.bin/gprof/arcs.c b/usr.bin/gprof/arcs.c
new file mode 100644
index 0000000..e5bbc24
--- /dev/null
+++ b/usr.bin/gprof/arcs.c
@@ -0,0 +1,950 @@
+/*
+ * Copyright (c) 1983, 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.
+ */
+
+#ifndef lint
+static char sccsid[] = "@(#)arcs.c 8.1 (Berkeley) 6/6/93";
+#endif /* not lint */
+
+#include "gprof.h"
+
+#ifdef DEBUG
+int visited;
+int viable;
+int newcycle;
+int oldcycle;
+#endif DEBUG
+
+ /*
+ * add (or just increment) an arc
+ */
+addarc( parentp , childp , count )
+ nltype *parentp;
+ nltype *childp;
+ long count;
+{
+ arctype *arcp;
+
+# ifdef DEBUG
+ if ( debug & TALLYDEBUG ) {
+ printf( "[addarc] %d arcs from %s to %s\n" ,
+ count , parentp -> name , childp -> name );
+ }
+# endif DEBUG
+ arcp = arclookup( parentp , childp );
+ if ( arcp != 0 ) {
+ /*
+ * a hit: just increment the count.
+ */
+# ifdef DEBUG
+ if ( debug & TALLYDEBUG ) {
+ printf( "[tally] hit %d += %d\n" ,
+ arcp -> arc_count , count );
+ }
+# endif DEBUG
+ arcp -> arc_count += count;
+ return;
+ }
+ arcp = (arctype *)calloc( 1 , sizeof *arcp );
+ arcp -> arc_parentp = parentp;
+ arcp -> arc_childp = childp;
+ arcp -> arc_count = count;
+ /*
+ * prepend this child to the children of this parent
+ */
+ arcp -> arc_childlist = parentp -> children;
+ parentp -> children = arcp;
+ /*
+ * prepend this parent to the parents of this child
+ */
+ arcp -> arc_parentlist = childp -> parents;
+ childp -> parents = arcp;
+}
+
+ /*
+ * the code below topologically sorts the graph (collapsing cycles),
+ * and propagates time bottom up and flags top down.
+ */
+
+ /*
+ * the topologically sorted name list pointers
+ */
+nltype **topsortnlp;
+
+topcmp( npp1 , npp2 )
+ nltype **npp1;
+ nltype **npp2;
+{
+ return (*npp1) -> toporder - (*npp2) -> toporder;
+}
+
+nltype **
+doarcs()
+{
+ nltype *parentp, **timesortnlp;
+ arctype *arcp;
+ long index;
+ long pass;
+
+ /*
+ * initialize various things:
+ * zero out child times.
+ * count self-recursive calls.
+ * indicate that nothing is on cycles.
+ */
+ for ( parentp = nl ; parentp < npe ; parentp++ ) {
+ parentp -> childtime = 0.0;
+ arcp = arclookup( parentp , parentp );
+ if ( arcp != 0 ) {
+ parentp -> ncall -= arcp -> arc_count;
+ parentp -> selfcalls = arcp -> arc_count;
+ } else {
+ parentp -> selfcalls = 0;
+ }
+ parentp -> npropcall = parentp -> ncall;
+ parentp -> propfraction = 0.0;
+ parentp -> propself = 0.0;
+ parentp -> propchild = 0.0;
+ parentp -> printflag = FALSE;
+ parentp -> toporder = DFN_NAN;
+ parentp -> cycleno = 0;
+ parentp -> cyclehead = parentp;
+ parentp -> cnext = 0;
+ if ( cflag ) {
+ findcall( parentp , parentp -> value , (parentp+1) -> value );
+ }
+ }
+ for ( pass = 1 ; ; pass++ ) {
+ /*
+ * topologically order things
+ * if any node is unnumbered,
+ * number it and any of its descendents.
+ */
+ for ( dfn_init() , parentp = nl ; parentp < npe ; parentp++ ) {
+ if ( parentp -> toporder == DFN_NAN ) {
+ dfn( parentp );
+ }
+ }
+ /*
+ * link together nodes on the same cycle
+ */
+ cyclelink();
+ /*
+ * if no cycles to break up, proceed
+ */
+ if ( ! Cflag )
+ break;
+ /*
+ * analyze cycles to determine breakup
+ */
+# ifdef DEBUG
+ if ( debug & BREAKCYCLE ) {
+ printf("[doarcs] pass %d, cycle(s) %d\n" , pass , ncycle );
+ }
+# endif DEBUG
+ if ( pass == 1 ) {
+ printf( "\n\n%s %s\n%s %d:\n" ,
+ "The following arcs were deleted" ,
+ "from the propagation calculation" ,
+ "to reduce the maximum cycle size to", cyclethreshold );
+ }
+ if ( cycleanalyze() )
+ break;
+ free ( cyclenl );
+ ncycle = 0;
+ for ( parentp = nl ; parentp < npe ; parentp++ ) {
+ parentp -> toporder = DFN_NAN;
+ parentp -> cycleno = 0;
+ parentp -> cyclehead = parentp;
+ parentp -> cnext = 0;
+ }
+ }
+ if ( pass > 1 ) {
+ printf( "\f\n" );
+ } else {
+ printf( "\tNone\n\n" );
+ }
+ /*
+ * Sort the symbol table in reverse topological order
+ */
+ topsortnlp = (nltype **) calloc( nname , sizeof(nltype *) );
+ if ( topsortnlp == (nltype **) 0 ) {
+ fprintf( stderr , "[doarcs] ran out of memory for topo sorting\n" );
+ }
+ for ( index = 0 ; index < nname ; index += 1 ) {
+ topsortnlp[ index ] = &nl[ index ];
+ }
+ qsort( topsortnlp , nname , sizeof(nltype *) , topcmp );
+# ifdef DEBUG
+ if ( debug & DFNDEBUG ) {
+ printf( "[doarcs] topological sort listing\n" );
+ for ( index = 0 ; index < nname ; index += 1 ) {
+ printf( "[doarcs] " );
+ printf( "%d:" , topsortnlp[ index ] -> toporder );
+ printname( topsortnlp[ index ] );
+ printf( "\n" );
+ }
+ }
+# endif DEBUG
+ /*
+ * starting from the topological top,
+ * propagate print flags to children.
+ * also, calculate propagation fractions.
+ * this happens before time propagation
+ * since time propagation uses the fractions.
+ */
+ doflags();
+ /*
+ * starting from the topological bottom,
+ * propogate children times up to parents.
+ */
+ dotime();
+ /*
+ * Now, sort by propself + propchild.
+ * sorting both the regular function names
+ * and cycle headers.
+ */
+ timesortnlp = (nltype **) calloc( nname + ncycle , sizeof(nltype *) );
+ if ( timesortnlp == (nltype **) 0 ) {
+ fprintf( stderr , "%s: ran out of memory for sorting\n" , whoami );
+ }
+ for ( index = 0 ; index < nname ; index++ ) {
+ timesortnlp[index] = &nl[index];
+ }
+ for ( index = 1 ; index <= ncycle ; index++ ) {
+ timesortnlp[nname+index-1] = &cyclenl[index];
+ }
+ qsort( timesortnlp , nname + ncycle , sizeof(nltype *) , totalcmp );
+ for ( index = 0 ; index < nname + ncycle ; index++ ) {
+ timesortnlp[ index ] -> index = index + 1;
+ }
+ return( timesortnlp );
+}
+
+dotime()
+{
+ int index;
+
+ cycletime();
+ for ( index = 0 ; index < nname ; index += 1 ) {
+ timepropagate( topsortnlp[ index ] );
+ }
+}
+
+timepropagate( parentp )
+ nltype *parentp;
+{
+ arctype *arcp;
+ nltype *childp;
+ double share;
+ double propshare;
+
+ if ( parentp -> propfraction == 0.0 ) {
+ return;
+ }
+ /*
+ * gather time from children of this parent.
+ */
+ for ( arcp = parentp -> children ; arcp ; arcp = arcp -> arc_childlist ) {
+ childp = arcp -> arc_childp;
+ if ( arcp -> arc_flags & DEADARC ) {
+ continue;
+ }
+ if ( arcp -> arc_count == 0 ) {
+ continue;
+ }
+ if ( childp == parentp ) {
+ continue;
+ }
+ if ( childp -> propfraction == 0.0 ) {
+ continue;
+ }
+ if ( childp -> cyclehead != childp ) {
+ if ( parentp -> cycleno == childp -> cycleno ) {
+ continue;
+ }
+ if ( parentp -> toporder <= childp -> toporder ) {
+ fprintf( stderr , "[propagate] toporder botches\n" );
+ }
+ childp = childp -> cyclehead;
+ } else {
+ if ( parentp -> toporder <= childp -> toporder ) {
+ fprintf( stderr , "[propagate] toporder botches\n" );
+ continue;
+ }
+ }
+ if ( childp -> npropcall == 0 ) {
+ continue;
+ }
+ /*
+ * distribute time for this arc
+ */
+ arcp -> arc_time = childp -> time
+ * ( ( (double) arcp -> arc_count ) /
+ ( (double) childp -> npropcall ) );
+ arcp -> arc_childtime = childp -> childtime
+ * ( ( (double) arcp -> arc_count ) /
+ ( (double) childp -> npropcall ) );
+ share = arcp -> arc_time + arcp -> arc_childtime;
+ parentp -> childtime += share;
+ /*
+ * ( 1 - propfraction ) gets lost along the way
+ */
+ propshare = parentp -> propfraction * share;
+ /*
+ * fix things for printing
+ */
+ parentp -> propchild += propshare;
+ arcp -> arc_time *= parentp -> propfraction;
+ arcp -> arc_childtime *= parentp -> propfraction;
+ /*
+ * add this share to the parent's cycle header, if any.
+ */
+ if ( parentp -> cyclehead != parentp ) {
+ parentp -> cyclehead -> childtime += share;
+ parentp -> cyclehead -> propchild += propshare;
+ }
+# ifdef DEBUG
+ if ( debug & PROPDEBUG ) {
+ printf( "[dotime] child \t" );
+ printname( childp );
+ printf( " with %f %f %d/%d\n" ,
+ childp -> time , childp -> childtime ,
+ arcp -> arc_count , childp -> npropcall );
+ printf( "[dotime] parent\t" );
+ printname( parentp );
+ printf( "\n[dotime] share %f\n" , share );
+ }
+# endif DEBUG
+ }
+}
+
+cyclelink()
+{
+ register nltype *nlp;
+ register nltype *cyclenlp;
+ int cycle;
+ nltype *memberp;
+ arctype *arcp;
+
+ /*
+ * Count the number of cycles, and initialze the cycle lists
+ */
+ ncycle = 0;
+ for ( nlp = nl ; nlp < npe ; nlp++ ) {
+ /*
+ * this is how you find unattached cycles
+ */
+ if ( nlp -> cyclehead == nlp && nlp -> cnext != 0 ) {
+ ncycle += 1;
+ }
+ }
+ /*
+ * cyclenl is indexed by cycle number:
+ * i.e. it is origin 1, not origin 0.
+ */
+ cyclenl = (nltype *) calloc( ncycle + 1 , sizeof( nltype ) );
+ if ( cyclenl == 0 ) {
+ fprintf( stderr , "%s: No room for %d bytes of cycle headers\n" ,
+ whoami , ( ncycle + 1 ) * sizeof( nltype ) );
+ done();
+ }
+ /*
+ * now link cycles to true cycleheads,
+ * number them, accumulate the data for the cycle
+ */
+ cycle = 0;
+ for ( nlp = nl ; nlp < npe ; nlp++ ) {
+ if ( !( nlp -> cyclehead == nlp && nlp -> cnext != 0 ) ) {
+ continue;
+ }
+ cycle += 1;
+ cyclenlp = &cyclenl[cycle];
+ cyclenlp -> name = 0; /* the name */
+ cyclenlp -> value = 0; /* the pc entry point */
+ cyclenlp -> time = 0.0; /* ticks in this routine */
+ cyclenlp -> childtime = 0.0; /* cumulative ticks in children */
+ cyclenlp -> ncall = 0; /* how many times called */
+ cyclenlp -> selfcalls = 0; /* how many calls to self */
+ cyclenlp -> propfraction = 0.0; /* what % of time propagates */
+ cyclenlp -> propself = 0.0; /* how much self time propagates */
+ cyclenlp -> propchild = 0.0; /* how much child time propagates */
+ cyclenlp -> printflag = TRUE; /* should this be printed? */
+ cyclenlp -> index = 0; /* index in the graph list */
+ cyclenlp -> toporder = DFN_NAN; /* graph call chain top-sort order */
+ cyclenlp -> cycleno = cycle; /* internal number of cycle on */
+ cyclenlp -> cyclehead = cyclenlp; /* pointer to head of cycle */
+ cyclenlp -> cnext = nlp; /* pointer to next member of cycle */
+ cyclenlp -> parents = 0; /* list of caller arcs */
+ cyclenlp -> children = 0; /* list of callee arcs */
+# ifdef DEBUG
+ if ( debug & CYCLEDEBUG ) {
+ printf( "[cyclelink] " );
+ printname( nlp );
+ printf( " is the head of cycle %d\n" , cycle );
+ }
+# endif DEBUG
+ /*
+ * link members to cycle header
+ */
+ for ( memberp = nlp ; memberp ; memberp = memberp -> cnext ) {
+ memberp -> cycleno = cycle;
+ memberp -> cyclehead = cyclenlp;
+ }
+ /*
+ * count calls from outside the cycle
+ * and those among cycle members
+ */
+ for ( memberp = nlp ; memberp ; memberp = memberp -> cnext ) {
+ for ( arcp=memberp->parents ; arcp ; arcp=arcp->arc_parentlist ) {
+ if ( arcp -> arc_parentp == memberp ) {
+ continue;
+ }
+ if ( arcp -> arc_parentp -> cycleno == cycle ) {
+ cyclenlp -> selfcalls += arcp -> arc_count;
+ } else {
+ cyclenlp -> npropcall += arcp -> arc_count;
+ }
+ }
+ }
+ }
+}
+
+ /*
+ * analyze cycles to determine breakup
+ */
+cycleanalyze()
+{
+ arctype **cyclestack;
+ arctype **stkp;
+ arctype **arcpp;
+ arctype **endlist;
+ arctype *arcp;
+ nltype *nlp;
+ cltype *clp;
+ bool ret;
+ bool done;
+ int size;
+ int cycleno;
+
+ /*
+ * calculate the size of the cycle, and find nodes that
+ * exit the cycle as they are desirable targets to cut
+ * some of their parents
+ */
+ for ( done = TRUE , cycleno = 1 ; cycleno <= ncycle ; cycleno++ ) {
+ size = 0;
+ for (nlp = cyclenl[ cycleno ] . cnext; nlp; nlp = nlp -> cnext) {
+ size += 1;
+ nlp -> parentcnt = 0;
+ nlp -> flags &= ~HASCYCLEXIT;
+ for ( arcp = nlp -> parents; arcp; arcp = arcp -> arc_parentlist ) {
+ nlp -> parentcnt += 1;
+ if ( arcp -> arc_parentp -> cycleno != cycleno )
+ nlp -> flags |= HASCYCLEXIT;
+ }
+ }
+ if ( size <= cyclethreshold )
+ continue;
+ done = FALSE;
+ cyclestack = (arctype **) calloc( size + 1 , sizeof( arctype *) );
+ if ( cyclestack == 0 ) {
+ fprintf( stderr , "%s: No room for %d bytes of cycle stack\n" ,
+ whoami , ( size + 1 ) * sizeof( arctype * ) );
+ return;
+ }
+# ifdef DEBUG
+ if ( debug & BREAKCYCLE ) {
+ printf( "[cycleanalyze] starting cycle %d of %d, size %d\n" ,
+ cycleno , ncycle , size );
+ }
+# endif DEBUG
+ for ( nlp = cyclenl[ cycleno ] . cnext ; nlp ; nlp = nlp -> cnext ) {
+ stkp = &cyclestack[0];
+ nlp -> flags |= CYCLEHEAD;
+ ret = descend ( nlp , cyclestack , stkp );
+ nlp -> flags &= ~CYCLEHEAD;
+ if ( ret == FALSE )
+ break;
+ }
+ free( cyclestack );
+ if ( cyclecnt > 0 ) {
+ compresslist();
+ for ( clp = cyclehead ; clp ; ) {
+ endlist = &clp -> list[ clp -> size ];
+ for ( arcpp = clp -> list ; arcpp < endlist ; arcpp++ )
+ (*arcpp) -> arc_cyclecnt--;
+ cyclecnt--;
+ clp = clp -> next;
+ free( clp );
+ }
+ cyclehead = 0;
+ }
+ }
+# ifdef DEBUG
+ if ( debug & BREAKCYCLE ) {
+ printf("%s visited %d, viable %d, newcycle %d, oldcycle %d\n",
+ "[doarcs]" , visited , viable , newcycle , oldcycle);
+ }
+# endif DEBUG
+ return( done );
+}
+
+descend( node , stkstart , stkp )
+ nltype *node;
+ arctype **stkstart;
+ arctype **stkp;
+{
+ arctype *arcp;
+ bool ret;
+
+ for ( arcp = node -> children ; arcp ; arcp = arcp -> arc_childlist ) {
+# ifdef DEBUG
+ visited++;
+# endif DEBUG
+ if ( arcp -> arc_childp -> cycleno != node -> cycleno
+ || ( arcp -> arc_childp -> flags & VISITED )
+ || ( arcp -> arc_flags & DEADARC ) )
+ continue;
+# ifdef DEBUG
+ viable++;
+# endif DEBUG
+ *stkp = arcp;
+ if ( arcp -> arc_childp -> flags & CYCLEHEAD ) {
+ if ( addcycle( stkstart , stkp ) == FALSE )
+ return( FALSE );
+ continue;
+ }
+ arcp -> arc_childp -> flags |= VISITED;
+ ret = descend( arcp -> arc_childp , stkstart , stkp + 1 );
+ arcp -> arc_childp -> flags &= ~VISITED;
+ if ( ret == FALSE )
+ return( FALSE );
+ }
+}
+
+addcycle( stkstart , stkend )
+ arctype **stkstart;
+ arctype **stkend;
+{
+ arctype **arcpp;
+ arctype **stkloc;
+ arctype **stkp;
+ arctype **endlist;
+ arctype *minarc;
+ arctype *arcp;
+ cltype *clp;
+ int size;
+
+ size = stkend - stkstart + 1;
+ if ( size <= 1 )
+ return( TRUE );
+ for ( arcpp = stkstart , minarc = *arcpp ; arcpp <= stkend ; arcpp++ ) {
+ if ( *arcpp > minarc )
+ continue;
+ minarc = *arcpp;
+ stkloc = arcpp;
+ }
+ for ( clp = cyclehead ; clp ; clp = clp -> next ) {
+ if ( clp -> size != size )
+ continue;
+ stkp = stkloc;
+ endlist = &clp -> list[ size ];
+ for ( arcpp = clp -> list ; arcpp < endlist ; arcpp++ ) {
+ if ( *stkp++ != *arcpp )
+ break;
+ if ( stkp > stkend )
+ stkp = stkstart;
+ }
+ if ( arcpp == endlist ) {
+# ifdef DEBUG
+ oldcycle++;
+# endif DEBUG
+ return( TRUE );
+ }
+ }
+ clp = (cltype *)
+ calloc( 1 , sizeof ( cltype ) + ( size - 1 ) * sizeof( arctype * ) );
+ if ( clp == 0 ) {
+ fprintf( stderr , "%s: No room for %d bytes of subcycle storage\n" ,
+ whoami , sizeof ( cltype ) + ( size - 1 ) * sizeof( arctype * ) );
+ return( FALSE );
+ }
+ stkp = stkloc;
+ endlist = &clp -> list[ size ];
+ for ( arcpp = clp -> list ; arcpp < endlist ; arcpp++ ) {
+ arcp = *arcpp = *stkp++;
+ if ( stkp > stkend )
+ stkp = stkstart;
+ arcp -> arc_cyclecnt++;
+ if ( ( arcp -> arc_flags & ONLIST ) == 0 ) {
+ arcp -> arc_flags |= ONLIST;
+ arcp -> arc_next = archead;
+ archead = arcp;
+ }
+ }
+ clp -> size = size;
+ clp -> next = cyclehead;
+ cyclehead = clp;
+# ifdef DEBUG
+ newcycle++;
+ if ( debug & SUBCYCLELIST ) {
+ printsubcycle( clp );
+ }
+# endif DEBUG
+ cyclecnt++;
+ if ( cyclecnt >= CYCLEMAX )
+ return( FALSE );
+ return( TRUE );
+}
+
+compresslist()
+{
+ cltype *clp;
+ cltype **prev;
+ arctype **arcpp;
+ arctype **endlist;
+ arctype *arcp;
+ arctype *maxarcp;
+ arctype *maxexitarcp;
+ arctype *maxwithparentarcp;
+ arctype *maxnoparentarcp;
+ int maxexitcnt;
+ int maxwithparentcnt;
+ int maxnoparentcnt;
+ char *type;
+
+ maxexitcnt = 0;
+ maxwithparentcnt = 0;
+ maxnoparentcnt = 0;
+ for ( endlist = &archead , arcp = archead ; arcp ; ) {
+ if ( arcp -> arc_cyclecnt == 0 ) {
+ arcp -> arc_flags &= ~ONLIST;
+ *endlist = arcp -> arc_next;
+ arcp -> arc_next = 0;
+ arcp = *endlist;
+ continue;
+ }
+ if ( arcp -> arc_childp -> flags & HASCYCLEXIT ) {
+ if ( arcp -> arc_cyclecnt > maxexitcnt ||
+ ( arcp -> arc_cyclecnt == maxexitcnt &&
+ arcp -> arc_cyclecnt < maxexitarcp -> arc_count ) ) {
+ maxexitcnt = arcp -> arc_cyclecnt;
+ maxexitarcp = arcp;
+ }
+ } else if ( arcp -> arc_childp -> parentcnt > 1 ) {
+ if ( arcp -> arc_cyclecnt > maxwithparentcnt ||
+ ( arcp -> arc_cyclecnt == maxwithparentcnt &&
+ arcp -> arc_cyclecnt < maxwithparentarcp -> arc_count ) ) {
+ maxwithparentcnt = arcp -> arc_cyclecnt;
+ maxwithparentarcp = arcp;
+ }
+ } else {
+ if ( arcp -> arc_cyclecnt > maxnoparentcnt ||
+ ( arcp -> arc_cyclecnt == maxnoparentcnt &&
+ arcp -> arc_cyclecnt < maxnoparentarcp -> arc_count ) ) {
+ maxnoparentcnt = arcp -> arc_cyclecnt;
+ maxnoparentarcp = arcp;
+ }
+ }
+ endlist = &arcp -> arc_next;
+ arcp = arcp -> arc_next;
+ }
+ if ( maxexitcnt > 0 ) {
+ /*
+ * first choice is edge leading to node with out-of-cycle parent
+ */
+ maxarcp = maxexitarcp;
+# ifdef DEBUG
+ type = "exit";
+# endif DEBUG
+ } else if ( maxwithparentcnt > 0 ) {
+ /*
+ * second choice is edge leading to node with at least one
+ * other in-cycle parent
+ */
+ maxarcp = maxwithparentarcp;
+# ifdef DEBUG
+ type = "internal";
+# endif DEBUG
+ } else {
+ /*
+ * last choice is edge leading to node with only this arc as
+ * a parent (as it will now be orphaned)
+ */
+ maxarcp = maxnoparentarcp;
+# ifdef DEBUG
+ type = "orphan";
+# endif DEBUG
+ }
+ maxarcp -> arc_flags |= DEADARC;
+ maxarcp -> arc_childp -> parentcnt -= 1;
+ maxarcp -> arc_childp -> npropcall -= maxarcp -> arc_count;
+# ifdef DEBUG
+ if ( debug & BREAKCYCLE ) {
+ printf( "%s delete %s arc: %s (%d) -> %s from %d cycle(s)\n" ,
+ "[compresslist]" , type , maxarcp -> arc_parentp -> name ,
+ maxarcp -> arc_count , maxarcp -> arc_childp -> name ,
+ maxarcp -> arc_cyclecnt );
+ }
+# endif DEBUG
+ printf( "\t%s to %s with %d calls\n" , maxarcp -> arc_parentp -> name ,
+ maxarcp -> arc_childp -> name , maxarcp -> arc_count );
+ prev = &cyclehead;
+ for ( clp = cyclehead ; clp ; ) {
+ endlist = &clp -> list[ clp -> size ];
+ for ( arcpp = clp -> list ; arcpp < endlist ; arcpp++ )
+ if ( (*arcpp) -> arc_flags & DEADARC )
+ break;
+ if ( arcpp == endlist ) {
+ prev = &clp -> next;
+ clp = clp -> next;
+ continue;
+ }
+ for ( arcpp = clp -> list ; arcpp < endlist ; arcpp++ )
+ (*arcpp) -> arc_cyclecnt--;
+ cyclecnt--;
+ *prev = clp -> next;
+ clp = clp -> next;
+ free( clp );
+ }
+}
+
+#ifdef DEBUG
+printsubcycle( clp )
+ cltype *clp;
+{
+ arctype **arcpp;
+ arctype **endlist;
+
+ arcpp = clp -> list;
+ printf( "%s <cycle %d>\n" , (*arcpp) -> arc_parentp -> name ,
+ (*arcpp) -> arc_parentp -> cycleno ) ;
+ for ( endlist = &clp -> list[ clp -> size ]; arcpp < endlist ; arcpp++ )
+ printf( "\t(%d) -> %s\n" , (*arcpp) -> arc_count ,
+ (*arcpp) -> arc_childp -> name ) ;
+}
+#endif DEBUG
+
+cycletime()
+{
+ int cycle;
+ nltype *cyclenlp;
+ nltype *childp;
+
+ for ( cycle = 1 ; cycle <= ncycle ; cycle += 1 ) {
+ cyclenlp = &cyclenl[ cycle ];
+ for ( childp = cyclenlp -> cnext ; childp ; childp = childp -> cnext ) {
+ if ( childp -> propfraction == 0.0 ) {
+ /*
+ * all members have the same propfraction except those
+ * that were excluded with -E
+ */
+ continue;
+ }
+ cyclenlp -> time += childp -> time;
+ }
+ cyclenlp -> propself = cyclenlp -> propfraction * cyclenlp -> time;
+ }
+}
+
+ /*
+ * in one top to bottom pass over the topologically sorted namelist
+ * propagate:
+ * printflag as the union of parents' printflags
+ * propfraction as the sum of fractional parents' propfractions
+ * and while we're here, sum time for functions.
+ */
+doflags()
+{
+ int index;
+ nltype *childp;
+ nltype *oldhead;
+
+ oldhead = 0;
+ for ( index = nname-1 ; index >= 0 ; index -= 1 ) {
+ childp = topsortnlp[ index ];
+ /*
+ * if we haven't done this function or cycle,
+ * inherit things from parent.
+ * this way, we are linear in the number of arcs
+ * since we do all members of a cycle (and the cycle itself)
+ * as we hit the first member of the cycle.
+ */
+ if ( childp -> cyclehead != oldhead ) {
+ oldhead = childp -> cyclehead;
+ inheritflags( childp );
+ }
+# ifdef DEBUG
+ if ( debug & PROPDEBUG ) {
+ printf( "[doflags] " );
+ printname( childp );
+ printf( " inherits printflag %d and propfraction %f\n" ,
+ childp -> printflag , childp -> propfraction );
+ }
+# endif DEBUG
+ if ( ! childp -> printflag ) {
+ /*
+ * printflag is off
+ * it gets turned on by
+ * being on -f list,
+ * or there not being any -f list and not being on -e list.
+ */
+ if ( onlist( flist , childp -> name )
+ || ( !fflag && !onlist( elist , childp -> name ) ) ) {
+ childp -> printflag = TRUE;
+ }
+ } else {
+ /*
+ * this function has printing parents:
+ * maybe someone wants to shut it up
+ * by putting it on -e list. (but favor -f over -e)
+ */
+ if ( ( !onlist( flist , childp -> name ) )
+ && onlist( elist , childp -> name ) ) {
+ childp -> printflag = FALSE;
+ }
+ }
+ if ( childp -> propfraction == 0.0 ) {
+ /*
+ * no parents to pass time to.
+ * collect time from children if
+ * its on -F list,
+ * or there isn't any -F list and its not on -E list.
+ */
+ if ( onlist( Flist , childp -> name )
+ || ( !Fflag && !onlist( Elist , childp -> name ) ) ) {
+ childp -> propfraction = 1.0;
+ }
+ } else {
+ /*
+ * it has parents to pass time to,
+ * but maybe someone wants to shut it up
+ * by puttting it on -E list. (but favor -F over -E)
+ */
+ if ( !onlist( Flist , childp -> name )
+ && onlist( Elist , childp -> name ) ) {
+ childp -> propfraction = 0.0;
+ }
+ }
+ childp -> propself = childp -> time * childp -> propfraction;
+ printtime += childp -> propself;
+# ifdef DEBUG
+ if ( debug & PROPDEBUG ) {
+ printf( "[doflags] " );
+ printname( childp );
+ printf( " ends up with printflag %d and propfraction %f\n" ,
+ childp -> printflag , childp -> propfraction );
+ printf( "time %f propself %f printtime %f\n" ,
+ childp -> time , childp -> propself , printtime );
+ }
+# endif DEBUG
+ }
+}
+
+ /*
+ * check if any parent of this child
+ * (or outside parents of this cycle)
+ * have their print flags on and set the
+ * print flag of the child (cycle) appropriately.
+ * similarly, deal with propagation fractions from parents.
+ */
+inheritflags( childp )
+ nltype *childp;
+{
+ nltype *headp;
+ arctype *arcp;
+ nltype *parentp;
+ nltype *memp;
+
+ headp = childp -> cyclehead;
+ if ( childp == headp ) {
+ /*
+ * just a regular child, check its parents
+ */
+ childp -> printflag = FALSE;
+ childp -> propfraction = 0.0;
+ for (arcp = childp -> parents ; arcp ; arcp = arcp -> arc_parentlist) {
+ parentp = arcp -> arc_parentp;
+ if ( childp == parentp ) {
+ continue;
+ }
+ childp -> printflag |= parentp -> printflag;
+ /*
+ * if the child was never actually called
+ * (e.g. this arc is static (and all others are, too))
+ * no time propagates along this arc.
+ */
+ if ( arcp -> arc_flags & DEADARC ) {
+ continue;
+ }
+ if ( childp -> npropcall ) {
+ childp -> propfraction += parentp -> propfraction
+ * ( ( (double) arcp -> arc_count )
+ / ( (double) childp -> npropcall ) );
+ }
+ }
+ } else {
+ /*
+ * its a member of a cycle, look at all parents from
+ * outside the cycle
+ */
+ headp -> printflag = FALSE;
+ headp -> propfraction = 0.0;
+ for ( memp = headp -> cnext ; memp ; memp = memp -> cnext ) {
+ for (arcp = memp->parents ; arcp ; arcp = arcp->arc_parentlist) {
+ if ( arcp -> arc_parentp -> cyclehead == headp ) {
+ continue;
+ }
+ parentp = arcp -> arc_parentp;
+ headp -> printflag |= parentp -> printflag;
+ /*
+ * if the cycle was never actually called
+ * (e.g. this arc is static (and all others are, too))
+ * no time propagates along this arc.
+ */
+ if ( arcp -> arc_flags & DEADARC ) {
+ continue;
+ }
+ if ( headp -> npropcall ) {
+ headp -> propfraction += parentp -> propfraction
+ * ( ( (double) arcp -> arc_count )
+ / ( (double) headp -> npropcall ) );
+ }
+ }
+ }
+ for ( memp = headp ; memp ; memp = memp -> cnext ) {
+ memp -> printflag = headp -> printflag;
+ memp -> propfraction = headp -> propfraction;
+ }
+ }
+}
diff --git a/usr.bin/gprof/dfn.c b/usr.bin/gprof/dfn.c
new file mode 100644
index 0000000..987929f
--- /dev/null
+++ b/usr.bin/gprof/dfn.c
@@ -0,0 +1,325 @@
+/*
+ * Copyright (c) 1983, 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.
+ */
+
+#ifndef lint
+static char sccsid[] = "@(#)dfn.c 8.1 (Berkeley) 6/6/93";
+#endif /* not lint */
+
+#include <stdio.h>
+#include "gprof.h"
+
+#define DFN_DEPTH 100
+struct dfnstruct {
+ nltype *nlentryp;
+ int cycletop;
+};
+typedef struct dfnstruct dfntype;
+
+dfntype dfn_stack[ DFN_DEPTH ];
+int dfn_depth;
+
+int dfn_counter;
+
+dfn_init()
+{
+
+ dfn_depth = 0;
+ dfn_counter = DFN_NAN;
+}
+
+ /*
+ * given this parent, depth first number its children.
+ */
+dfn( parentp )
+ nltype *parentp;
+{
+ arctype *arcp;
+
+# ifdef DEBUG
+ if ( debug & DFNDEBUG ) {
+ printf( "[dfn] dfn(" );
+ printname( parentp );
+ printf( ")\n" );
+ }
+# endif DEBUG
+ /*
+ * if we're already numbered, no need to look any furthur.
+ */
+ if ( dfn_numbered( parentp ) ) {
+ return;
+ }
+ /*
+ * if we're already busy, must be a cycle
+ */
+ if ( dfn_busy( parentp ) ) {
+ dfn_findcycle( parentp );
+ return;
+ }
+ /*
+ * visit yourself before your children
+ */
+ dfn_pre_visit( parentp );
+ /*
+ * visit children
+ */
+ for ( arcp = parentp -> children ; arcp ; arcp = arcp -> arc_childlist ) {
+ if ( arcp -> arc_flags & DEADARC )
+ continue;
+ dfn( arcp -> arc_childp );
+ }
+ /*
+ * visit yourself after your children
+ */
+ dfn_post_visit( parentp );
+}
+
+ /*
+ * push a parent onto the stack and mark it busy
+ */
+dfn_pre_visit( parentp )
+ nltype *parentp;
+{
+
+ dfn_depth += 1;
+ if ( dfn_depth >= DFN_DEPTH ) {
+ fprintf( stderr , "[dfn] out of my depth (dfn_stack overflow)\n" );
+ exit( 1 );
+ }
+ dfn_stack[ dfn_depth ].nlentryp = parentp;
+ dfn_stack[ dfn_depth ].cycletop = dfn_depth;
+ parentp -> toporder = DFN_BUSY;
+# ifdef DEBUG
+ if ( debug & DFNDEBUG ) {
+ printf( "[dfn_pre_visit]\t\t%d:" , dfn_depth );
+ printname( parentp );
+ printf( "\n" );
+ }
+# endif DEBUG
+}
+
+ /*
+ * are we already numbered?
+ */
+bool
+dfn_numbered( childp )
+ nltype *childp;
+{
+
+ return ( childp -> toporder != DFN_NAN && childp -> toporder != DFN_BUSY );
+}
+
+ /*
+ * are we already busy?
+ */
+bool
+dfn_busy( childp )
+ nltype *childp;
+{
+
+ if ( childp -> toporder == DFN_NAN ) {
+ return FALSE;
+ }
+ return TRUE;
+}
+
+ /*
+ * MISSING: an explanation
+ */
+dfn_findcycle( childp )
+ nltype *childp;
+{
+ int cycletop;
+ nltype *cycleheadp;
+ nltype *tailp;
+ int index;
+
+ for ( cycletop = dfn_depth ; cycletop > 0 ; cycletop -= 1 ) {
+ cycleheadp = dfn_stack[ cycletop ].nlentryp;
+ if ( childp == cycleheadp ) {
+ break;
+ }
+ if ( childp -> cyclehead != childp &&
+ childp -> cyclehead == cycleheadp ) {
+ break;
+ }
+ }
+ if ( cycletop <= 0 ) {
+ fprintf( stderr , "[dfn_findcycle] couldn't find head of cycle\n" );
+ exit( 1 );
+ }
+# ifdef DEBUG
+ if ( debug & DFNDEBUG ) {
+ printf( "[dfn_findcycle] dfn_depth %d cycletop %d " ,
+ dfn_depth , cycletop );
+ printname( cycleheadp );
+ printf( "\n" );
+ }
+# endif DEBUG
+ if ( cycletop == dfn_depth ) {
+ /*
+ * this is previous function, e.g. this calls itself
+ * sort of boring
+ */
+ dfn_self_cycle( childp );
+ } else {
+ /*
+ * glom intervening functions that aren't already
+ * glommed into this cycle.
+ * things have been glommed when their cyclehead field
+ * points to the head of the cycle they are glommed into.
+ */
+ for ( tailp = cycleheadp ; tailp -> cnext ; tailp = tailp -> cnext ) {
+ /* void: chase down to tail of things already glommed */
+# ifdef DEBUG
+ if ( debug & DFNDEBUG ) {
+ printf( "[dfn_findcycle] tail " );
+ printname( tailp );
+ printf( "\n" );
+ }
+# endif DEBUG
+ }
+ /*
+ * if what we think is the top of the cycle
+ * has a cyclehead field, then it's not really the
+ * head of the cycle, which is really what we want
+ */
+ if ( cycleheadp -> cyclehead != cycleheadp ) {
+ cycleheadp = cycleheadp -> cyclehead;
+# ifdef DEBUG
+ if ( debug & DFNDEBUG ) {
+ printf( "[dfn_findcycle] new cyclehead " );
+ printname( cycleheadp );
+ printf( "\n" );
+ }
+# endif DEBUG
+ }
+ for ( index = cycletop + 1 ; index <= dfn_depth ; index += 1 ) {
+ childp = dfn_stack[ index ].nlentryp;
+ if ( childp -> cyclehead == childp ) {
+ /*
+ * not yet glommed anywhere, glom it
+ * and fix any children it has glommed
+ */
+ tailp -> cnext = childp;
+ childp -> cyclehead = cycleheadp;
+# ifdef DEBUG
+ if ( debug & DFNDEBUG ) {
+ printf( "[dfn_findcycle] glomming " );
+ printname( childp );
+ printf( " onto " );
+ printname( cycleheadp );
+ printf( "\n" );
+ }
+# endif DEBUG
+ for ( tailp = childp ; tailp->cnext ; tailp = tailp->cnext ) {
+ tailp -> cnext -> cyclehead = cycleheadp;
+# ifdef DEBUG
+ if ( debug & DFNDEBUG ) {
+ printf( "[dfn_findcycle] and its tail " );
+ printname( tailp -> cnext );
+ printf( " onto " );
+ printname( cycleheadp );
+ printf( "\n" );
+ }
+# endif DEBUG
+ }
+ } else if ( childp -> cyclehead != cycleheadp /* firewall */ ) {
+ fprintf( stderr ,
+ "[dfn_busy] glommed, but not to cyclehead\n" );
+ }
+ }
+ }
+}
+
+ /*
+ * deal with self-cycles
+ * for lint: ARGSUSED
+ */
+dfn_self_cycle( parentp )
+ nltype *parentp;
+{
+ /*
+ * since we are taking out self-cycles elsewhere
+ * no need for the special case, here.
+ */
+# ifdef DEBUG
+ if ( debug & DFNDEBUG ) {
+ printf( "[dfn_self_cycle] " );
+ printname( parentp );
+ printf( "\n" );
+ }
+# endif DEBUG
+}
+
+ /*
+ * visit a node after all its children
+ * [MISSING: an explanation]
+ * and pop it off the stack
+ */
+dfn_post_visit( parentp )
+ nltype *parentp;
+{
+ nltype *memberp;
+
+# ifdef DEBUG
+ if ( debug & DFNDEBUG ) {
+ printf( "[dfn_post_visit]\t%d: " , dfn_depth );
+ printname( parentp );
+ printf( "\n" );
+ }
+# endif DEBUG
+ /*
+ * number functions and things in their cycles
+ * unless the function is itself part of a cycle
+ */
+ if ( parentp -> cyclehead == parentp ) {
+ dfn_counter += 1;
+ for ( memberp = parentp ; memberp ; memberp = memberp -> cnext ) {
+ memberp -> toporder = dfn_counter;
+# ifdef DEBUG
+ if ( debug & DFNDEBUG ) {
+ printf( "[dfn_post_visit]\t\tmember " );
+ printname( memberp );
+ printf( " -> toporder = %d\n" , dfn_counter );
+ }
+# endif DEBUG
+ }
+ } else {
+# ifdef DEBUG
+ if ( debug & DFNDEBUG ) {
+ printf( "[dfn_post_visit]\t\tis part of a cycle\n" );
+ }
+# endif DEBUG
+ }
+ dfn_depth -= 1;
+}
diff --git a/usr.bin/gprof/gprof.1 b/usr.bin/gprof/gprof.1
new file mode 100644
index 0000000..dfb0f21
--- /dev/null
+++ b/usr.bin/gprof/gprof.1
@@ -0,0 +1,281 @@
+.\" Copyright (c) 1983, 1990, 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.
+.\"
+.\" @(#)gprof.1 8.1 (Berkeley) 6/6/93
+.\"
+.Dd June 6, 1993
+.Dt GPROF 1
+.Os BSD 4.2
+.Sh NAME
+.Nm gprof
+.Nd display call graph profile data
+.Sh SYNOPSIS
+.Nm gprof
+.Op options
+.Op Ar a.out Op Ar gmon.out ...
+.Sh DESCRIPTION
+.Nm Gprof
+produces an execution profile of C, Pascal, or Fortran77 programs.
+The effect of called routines is incorporated in the profile of each caller.
+The profile data is taken from the call graph profile file
+.Pf ( Pa gmon.out
+default) which is created by programs
+that are compiled with the
+.Fl pg
+option of
+.Xr cc 1 ,
+.Xr pc 1 ,
+and
+.Xr f77 1 .
+The
+.Fl pg
+option also links in versions of the library routines
+that are compiled for profiling.
+.Nm Gprof
+reads the given object file (the default is
+.Pa a.out)
+and establishes the relation between it's symbol table
+and the call graph profile from
+.Pa gmon.out .
+If more than one profile file is specified,
+the
+.Nm gprof
+output shows the sum of the profile information in the given profile files.
+.Pp
+.Nm Gprof
+calculates the amount of time spent in each routine.
+Next, these times are propagated along the edges of the call graph.
+Cycles are discovered, and calls into a cycle are made to share the time
+of the cycle.
+The first listing shows the functions
+sorted according to the time they represent
+including the time of their call graph descendents.
+Below each function entry is shown its (direct) call graph children,
+and how their times are propagated to this function.
+A similar display above the function shows how this function's time and the
+time of its descendents is propagated to its (direct) call graph parents.
+.Pp
+Cycles are also shown, with an entry for the cycle as a whole and
+a listing of the members of the cycle and their contributions to the
+time and call counts of the cycle.
+.Pp
+Second, a flat profile is given,
+similar to that provided by
+.Xr prof 1 .
+This listing gives the total execution times, the call counts,
+the time in milleseconds the call spent in the routine itself, and
+the time in milleseconds the call spent in the routine itself including
+its descendents.
+.Pp
+Finally, an index of the function names is provided.
+.Pp
+The following options are available:
+.Bl -tag -width Fl
+.It Fl a
+Suppresses the printing of statically declared functions.
+If this option is given, all relevant information about the static function
+(e.g., time samples, calls to other functions, calls from other functions)
+belongs to the function loaded just before the static function in the
+.Pa a.out
+file.
+.It Fl b
+Suppresses the printing of a description of each field in the profile.
+.It Fl c
+The static call graph of the program is discovered by a heuristic
+that examines the text space of the object file.
+Static-only parents or children are shown
+with call counts of 0.
+.It Fl C Ar count
+Find a minimal set of arcs that can be broken to eliminate all cycles with
+.Ar count
+or more members.
+Caution: the algorithm used to break cycles is exponential,
+so using this option may cause
+.Nm gprof
+to run for a very long time.
+.It Fl e Ar name
+Suppresses the printing of the graph profile entry for routine
+.Ar name
+and all its descendants
+(unless they have other ancestors that aren't suppressed).
+More than one
+.Fl e
+option may be given.
+Only one
+.Ar name
+may be given with each
+.Fl e
+option.
+.It Fl E Ar name
+Suppresses the printing of the graph profile entry for routine
+.Ar name
+(and its descendants) as
+.Fl e ,
+above, and also excludes the time spent in
+.Ar name
+(and its descendants) from the total and percentage time computations.
+(For example,
+.Fl E
+.Ar mcount
+.Fl E
+.Ar mcleanup
+is the default.)
+.It Fl f Ar name
+Prints the graph profile entry of only the specified routine
+.Ar name
+and its descendants.
+More than one
+.Fl f
+option may be given.
+Only one
+.Ar name
+may be given with each
+.Fl f
+option.
+.It Fl F Ar name
+Prints the graph profile entry of only the routine
+.Ar name
+and its descendants (as
+.Fl f ,
+above) and also uses only the times of the printed routines
+in total time and percentage computations.
+More than one
+.Fl F
+option may be given.
+Only one
+.Ar name
+may be given with each
+.Fl F
+option.
+The
+.Fl F
+option
+overrides
+the
+.Fl E
+option.
+.It Fl k Ar fromname Ar toname
+Will delete any arcs from routine
+.Ar fromname
+to routine
+.Ar toname .
+This can be used to break undesired cycles.
+More than one
+.Fl k
+option may be given.
+Only one pair of routine names may be given with each
+.Fl k
+option.
+.It Fl s
+A profile file
+.Pa gmon.sum
+is produced that represents
+the sum of the profile information in all the specified profile files.
+This summary profile file may be given to later
+executions of gprof (probably also with a
+.Fl s )
+to accumulate profile data across several runs of an
+.Pa a.out
+file.
+.It Fl z
+Displays routines that have zero usage (as shown by call counts
+and accumulated time).
+This is useful with the
+.Fl c
+option for discovering which routines were never called.
+.El
+.Sh FILES
+.Bl -tag -width gmon.sum -compact
+.It Pa a.out
+The namelist and text space.
+.It Pa gmon.out
+Dynamic call graph and profile.
+.It Pa gmon.sum
+Summarized dynamic call graph and profile.
+.El
+.Sh SEE ALSO
+.Xr monitor 3 ,
+.Xr profil 2 ,
+.Xr cc 1 ,
+.Xr prof 1
+.Rs
+.%T "An Execution Profiler for Modular Programs"
+.%A S. Graham
+.%A P. Kessler
+.%A M. McKusick
+.%J "Software - Practice and Experience"
+.%V 13
+.%P pp. 671-685
+.%D 1983
+.Re
+.Rs
+.%T "gprof: A Call Graph Execution Profiler"
+.%A S. Graham
+.%A P. Kessler
+.%A M. McKusick
+.%J "Proceedings of the SIGPLAN '82 Symposium on Compiler Construction, SIGPLAN Notices"
+.%V 17
+.%N 6
+.%P pp. 120-126
+.%D June 1982
+.Re
+.Sh HISTORY
+The
+.Nm gprof
+profiler
+appeared in
+.Bx 4.2 .
+.Sh BUGS
+The granularity of the sampling is shown, but remains
+statistical at best.
+We assume that the time for each execution of a function
+can be expressed by the total time for the function divided
+by the number of times the function is called.
+Thus the time propagated along the call graph arcs to the function's
+parents is directly proportional to the number of times that
+arc is traversed.
+.Pp
+Parents that are not themselves profiled will have the time of
+their profiled children propagated to them, but they will appear
+to be spontaneously invoked in the call graph listing, and will
+not have their time propagated further.
+Similarly, signal catchers, even though profiled, will appear
+to be spontaneous (although for more obscure reasons).
+Any profiled children of signal catchers should have their times
+propagated properly, unless the signal catcher was invoked during
+the execution of the profiling routine, in which case all is lost.
+.Pp
+The profiled program must call
+.Xr exit 2
+or return normally for the profiling information to be saved
+in the
+.Pa gmon.out
+file.
diff --git a/usr.bin/gprof/gprof.c b/usr.bin/gprof/gprof.c
new file mode 100644
index 0000000..5057e32
--- /dev/null
+++ b/usr.bin/gprof/gprof.c
@@ -0,0 +1,749 @@
+/*
+ * Copyright (c) 1983, 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.
+ */
+
+#ifndef lint
+static char copyright[] =
+"@(#) Copyright (c) 1983, 1993\n\
+ The Regents of the University of California. All rights reserved.\n";
+#endif /* not lint */
+
+#ifndef lint
+static char sccsid[] = "@(#)gprof.c 8.1 (Berkeley) 6/6/93";
+#endif /* not lint */
+
+#include "gprof.h"
+
+char *whoami = "gprof";
+
+ /*
+ * things which get -E excluded by default.
+ */
+char *defaultEs[] = { "mcount" , "__mcleanup" , 0 };
+
+static struct gmonhdr gmonhdr;
+
+main(argc, argv)
+ int argc;
+ char **argv;
+{
+ char **sp;
+ nltype **timesortnlp;
+
+ --argc;
+ argv++;
+ debug = 0;
+ bflag = TRUE;
+ while ( *argv != 0 && **argv == '-' ) {
+ (*argv)++;
+ switch ( **argv ) {
+ case 'a':
+ aflag = TRUE;
+ break;
+ case 'b':
+ bflag = FALSE;
+ break;
+ case 'C':
+ Cflag = TRUE;
+ cyclethreshold = atoi( *++argv );
+ break;
+ case 'c':
+#if defined(vax) || defined(tahoe)
+ cflag = TRUE;
+#else
+ fprintf(stderr, "gprof: -c isn't supported on this architecture yet\n");
+ exit(1);
+#endif
+ break;
+ case 'd':
+ dflag = TRUE;
+ setlinebuf(stdout);
+ debug |= atoi( *++argv );
+ debug |= ANYDEBUG;
+# ifdef DEBUG
+ printf("[main] debug = %d\n", debug);
+# else not DEBUG
+ printf("%s: -d ignored\n", whoami);
+# endif DEBUG
+ break;
+ case 'E':
+ ++argv;
+ addlist( Elist , *argv );
+ Eflag = TRUE;
+ addlist( elist , *argv );
+ eflag = TRUE;
+ break;
+ case 'e':
+ addlist( elist , *++argv );
+ eflag = TRUE;
+ break;
+ case 'F':
+ ++argv;
+ addlist( Flist , *argv );
+ Fflag = TRUE;
+ addlist( flist , *argv );
+ fflag = TRUE;
+ break;
+ case 'f':
+ addlist( flist , *++argv );
+ fflag = TRUE;
+ break;
+ case 'k':
+ addlist( kfromlist , *++argv );
+ addlist( ktolist , *++argv );
+ kflag = TRUE;
+ break;
+ case 's':
+ sflag = TRUE;
+ break;
+ case 'z':
+ zflag = TRUE;
+ break;
+ }
+ argv++;
+ }
+ if ( *argv != 0 ) {
+ a_outname = *argv;
+ argv++;
+ } else {
+ a_outname = A_OUTNAME;
+ }
+ if ( *argv != 0 ) {
+ gmonname = *argv;
+ argv++;
+ } else {
+ gmonname = GMONNAME;
+ }
+ /*
+ * turn off default functions
+ */
+ for ( sp = &defaultEs[0] ; *sp ; sp++ ) {
+ Eflag = TRUE;
+ addlist( Elist , *sp );
+ eflag = TRUE;
+ addlist( elist , *sp );
+ }
+ /*
+ * get information about a.out file.
+ */
+ getnfile();
+ /*
+ * get information about mon.out file(s).
+ */
+ do {
+ getpfile( gmonname );
+ if ( *argv != 0 ) {
+ gmonname = *argv;
+ }
+ } while ( *argv++ != 0 );
+ /*
+ * how many ticks per second?
+ * if we can't tell, report time in ticks.
+ */
+ if (hz == 0) {
+ hz = 1;
+ fprintf(stderr, "time is in ticks, not seconds\n");
+ }
+ /*
+ * dump out a gmon.sum file if requested
+ */
+ if ( sflag ) {
+ dumpsum( GMONSUM );
+ }
+ /*
+ * assign samples to procedures
+ */
+ asgnsamples();
+ /*
+ * assemble the dynamic profile
+ */
+ timesortnlp = doarcs();
+ /*
+ * print the dynamic profile
+ */
+ printgprof( timesortnlp );
+ /*
+ * print the flat profile
+ */
+ printprof();
+ /*
+ * print the index
+ */
+ printindex();
+ done();
+}
+
+ /*
+ * Set up string and symbol tables from a.out.
+ * and optionally the text space.
+ * On return symbol table is sorted by value.
+ */
+getnfile()
+{
+ FILE *nfile;
+ int valcmp();
+
+ nfile = fopen( a_outname ,"r");
+ if (nfile == NULL) {
+ perror( a_outname );
+ done();
+ }
+ fread(&xbuf, 1, sizeof(xbuf), nfile);
+ if (N_BADMAG(xbuf)) {
+ fprintf(stderr, "%s: %s: bad format\n", whoami , a_outname );
+ done();
+ }
+ getstrtab(nfile);
+ getsymtab(nfile);
+ gettextspace( nfile );
+ qsort(nl, nname, sizeof(nltype), valcmp);
+ fclose(nfile);
+# ifdef DEBUG
+ if ( debug & AOUTDEBUG ) {
+ register int j;
+
+ for (j = 0; j < nname; j++){
+ printf("[getnfile] 0X%08x\t%s\n", nl[j].value, nl[j].name);
+ }
+ }
+# endif DEBUG
+}
+
+getstrtab(nfile)
+ FILE *nfile;
+{
+
+ fseek(nfile, (long)(N_SYMOFF(xbuf) + xbuf.a_syms), 0);
+ if (fread(&ssiz, sizeof (ssiz), 1, nfile) == 0) {
+ fprintf(stderr, "%s: %s: no string table (old format?)\n" ,
+ whoami , a_outname );
+ done();
+ }
+ strtab = calloc(ssiz, 1);
+ if (strtab == NULL) {
+ fprintf(stderr, "%s: %s: no room for %d bytes of string table\n",
+ whoami , a_outname , ssiz);
+ done();
+ }
+ if (fread(strtab+sizeof(ssiz), ssiz-sizeof(ssiz), 1, nfile) != 1) {
+ fprintf(stderr, "%s: %s: error reading string table\n",
+ whoami , a_outname );
+ done();
+ }
+}
+
+ /*
+ * Read in symbol table
+ */
+getsymtab(nfile)
+ FILE *nfile;
+{
+ register long i;
+ int askfor;
+ struct nlist nbuf;
+
+ /* pass1 - count symbols */
+ fseek(nfile, (long)N_SYMOFF(xbuf), 0);
+ nname = 0;
+ for (i = xbuf.a_syms; i > 0; i -= sizeof(struct nlist)) {
+ fread(&nbuf, sizeof(nbuf), 1, nfile);
+ if ( ! funcsymbol( &nbuf ) ) {
+ continue;
+ }
+ nname++;
+ }
+ if (nname == 0) {
+ fprintf(stderr, "%s: %s: no symbols\n", whoami , a_outname );
+ done();
+ }
+ askfor = nname + 1;
+ nl = (nltype *) calloc( askfor , sizeof(nltype) );
+ if (nl == 0) {
+ fprintf(stderr, "%s: No room for %d bytes of symbol table\n",
+ whoami, askfor * sizeof(nltype) );
+ done();
+ }
+
+ /* pass2 - read symbols */
+ fseek(nfile, (long)N_SYMOFF(xbuf), 0);
+ npe = nl;
+ nname = 0;
+ for (i = xbuf.a_syms; i > 0; i -= sizeof(struct nlist)) {
+ fread(&nbuf, sizeof(nbuf), 1, nfile);
+ if ( ! funcsymbol( &nbuf ) ) {
+# ifdef DEBUG
+ if ( debug & AOUTDEBUG ) {
+ printf( "[getsymtab] rejecting: 0x%x %s\n" ,
+ nbuf.n_type , strtab + nbuf.n_un.n_strx );
+ }
+# endif DEBUG
+ continue;
+ }
+ npe->value = nbuf.n_value;
+ npe->name = strtab+nbuf.n_un.n_strx;
+# ifdef DEBUG
+ if ( debug & AOUTDEBUG ) {
+ printf( "[getsymtab] %d %s 0x%08x\n" ,
+ nname , npe -> name , npe -> value );
+ }
+# endif DEBUG
+ npe++;
+ nname++;
+ }
+ npe->value = -1;
+}
+
+ /*
+ * read in the text space of an a.out file
+ */
+gettextspace( nfile )
+ FILE *nfile;
+{
+
+ if ( cflag == 0 ) {
+ return;
+ }
+ textspace = (u_char *) malloc( xbuf.a_text );
+ if ( textspace == 0 ) {
+ fprintf( stderr , "%s: ran out room for %d bytes of text space: " ,
+ whoami , xbuf.a_text );
+ fprintf( stderr , "can't do -c\n" );
+ return;
+ }
+ (void) fseek( nfile , N_TXTOFF( xbuf ) , 0 );
+ if ( fread( textspace , 1 , xbuf.a_text , nfile ) != xbuf.a_text ) {
+ fprintf( stderr , "%s: couldn't read text space: " , whoami );
+ fprintf( stderr , "can't do -c\n" );
+ free( textspace );
+ textspace = 0;
+ return;
+ }
+}
+ /*
+ * information from a gmon.out file is in two parts:
+ * an array of sampling hits within pc ranges,
+ * and the arcs.
+ */
+getpfile(filename)
+ char *filename;
+{
+ FILE *pfile;
+ FILE *openpfile();
+ struct rawarc arc;
+
+ pfile = openpfile(filename);
+ readsamples(pfile);
+ /*
+ * the rest of the file consists of
+ * a bunch of <from,self,count> tuples.
+ */
+ while ( fread( &arc , sizeof arc , 1 , pfile ) == 1 ) {
+# ifdef DEBUG
+ if ( debug & SAMPLEDEBUG ) {
+ printf( "[getpfile] frompc 0x%x selfpc 0x%x count %d\n" ,
+ arc.raw_frompc , arc.raw_selfpc , arc.raw_count );
+ }
+# endif DEBUG
+ /*
+ * add this arc
+ */
+ tally( &arc );
+ }
+ fclose(pfile);
+}
+
+FILE *
+openpfile(filename)
+ char *filename;
+{
+ struct gmonhdr tmp;
+ FILE *pfile;
+ int size;
+ int rate;
+
+ if((pfile = fopen(filename, "r")) == NULL) {
+ perror(filename);
+ done();
+ }
+ fread(&tmp, sizeof(struct gmonhdr), 1, pfile);
+ if ( s_highpc != 0 && ( tmp.lpc != gmonhdr.lpc ||
+ tmp.hpc != gmonhdr.hpc || tmp.ncnt != gmonhdr.ncnt ) ) {
+ fprintf(stderr, "%s: incompatible with first gmon file\n", filename);
+ done();
+ }
+ gmonhdr = tmp;
+ if ( gmonhdr.version == GMONVERSION ) {
+ rate = gmonhdr.profrate;
+ size = sizeof(struct gmonhdr);
+ } else {
+ fseek(pfile, sizeof(struct ophdr), SEEK_SET);
+ size = sizeof(struct ophdr);
+ gmonhdr.profrate = rate = hertz();
+ gmonhdr.version = GMONVERSION;
+ }
+ if (hz == 0) {
+ hz = rate;
+ } else if (hz != rate) {
+ fprintf(stderr,
+ "%s: profile clock rate (%d) %s (%d) in first gmon file\n",
+ filename, rate, "incompatible with clock rate", hz);
+ done();
+ }
+ s_lowpc = (unsigned long) gmonhdr.lpc;
+ s_highpc = (unsigned long) gmonhdr.hpc;
+ lowpc = (unsigned long)gmonhdr.lpc / sizeof(UNIT);
+ highpc = (unsigned long)gmonhdr.hpc / sizeof(UNIT);
+ sampbytes = gmonhdr.ncnt - size;
+ nsamples = sampbytes / sizeof (UNIT);
+# ifdef DEBUG
+ if ( debug & SAMPLEDEBUG ) {
+ printf( "[openpfile] hdr.lpc 0x%x hdr.hpc 0x%x hdr.ncnt %d\n",
+ gmonhdr.lpc , gmonhdr.hpc , gmonhdr.ncnt );
+ printf( "[openpfile] s_lowpc 0x%x s_highpc 0x%x\n" ,
+ s_lowpc , s_highpc );
+ printf( "[openpfile] lowpc 0x%x highpc 0x%x\n" ,
+ lowpc , highpc );
+ printf( "[openpfile] sampbytes %d nsamples %d\n" ,
+ sampbytes , nsamples );
+ printf( "[openpfile] sample rate %d\n" , hz );
+ }
+# endif DEBUG
+ return(pfile);
+}
+
+tally( rawp )
+ struct rawarc *rawp;
+{
+ nltype *parentp;
+ nltype *childp;
+
+ parentp = nllookup( rawp -> raw_frompc );
+ childp = nllookup( rawp -> raw_selfpc );
+ if ( parentp == 0 || childp == 0 )
+ return;
+ if ( kflag
+ && onlist( kfromlist , parentp -> name )
+ && onlist( ktolist , childp -> name ) ) {
+ return;
+ }
+ childp -> ncall += rawp -> raw_count;
+# ifdef DEBUG
+ if ( debug & TALLYDEBUG ) {
+ printf( "[tally] arc from %s to %s traversed %d times\n" ,
+ parentp -> name , childp -> name , rawp -> raw_count );
+ }
+# endif DEBUG
+ addarc( parentp , childp , rawp -> raw_count );
+}
+
+/*
+ * dump out the gmon.sum file
+ */
+dumpsum( sumfile )
+ char *sumfile;
+{
+ register nltype *nlp;
+ register arctype *arcp;
+ struct rawarc arc;
+ FILE *sfile;
+
+ if ( ( sfile = fopen ( sumfile , "w" ) ) == NULL ) {
+ perror( sumfile );
+ done();
+ }
+ /*
+ * dump the header; use the last header read in
+ */
+ if ( fwrite( &gmonhdr , sizeof gmonhdr , 1 , sfile ) != 1 ) {
+ perror( sumfile );
+ done();
+ }
+ /*
+ * dump the samples
+ */
+ if (fwrite(samples, sizeof (UNIT), nsamples, sfile) != nsamples) {
+ perror( sumfile );
+ done();
+ }
+ /*
+ * dump the normalized raw arc information
+ */
+ for ( nlp = nl ; nlp < npe ; nlp++ ) {
+ for ( arcp = nlp -> children ; arcp ; arcp = arcp -> arc_childlist ) {
+ arc.raw_frompc = arcp -> arc_parentp -> value;
+ arc.raw_selfpc = arcp -> arc_childp -> value;
+ arc.raw_count = arcp -> arc_count;
+ if ( fwrite ( &arc , sizeof arc , 1 , sfile ) != 1 ) {
+ perror( sumfile );
+ done();
+ }
+# ifdef DEBUG
+ if ( debug & SAMPLEDEBUG ) {
+ printf( "[dumpsum] frompc 0x%x selfpc 0x%x count %d\n" ,
+ arc.raw_frompc , arc.raw_selfpc , arc.raw_count );
+ }
+# endif DEBUG
+ }
+ }
+ fclose( sfile );
+}
+
+valcmp(p1, p2)
+ nltype *p1, *p2;
+{
+ if ( p1 -> value < p2 -> value ) {
+ return LESSTHAN;
+ }
+ if ( p1 -> value > p2 -> value ) {
+ return GREATERTHAN;
+ }
+ return EQUALTO;
+}
+
+readsamples(pfile)
+ FILE *pfile;
+{
+ register i;
+ UNIT sample;
+
+ if (samples == 0) {
+ samples = (UNIT *) calloc(sampbytes, sizeof (UNIT));
+ if (samples == 0) {
+ fprintf( stderr , "%s: No room for %d sample pc's\n",
+ whoami , sampbytes / sizeof (UNIT));
+ done();
+ }
+ }
+ for (i = 0; i < nsamples; i++) {
+ fread(&sample, sizeof (UNIT), 1, pfile);
+ if (feof(pfile))
+ break;
+ samples[i] += sample;
+ }
+ if (i != nsamples) {
+ fprintf(stderr,
+ "%s: unexpected EOF after reading %d/%d samples\n",
+ whoami , --i , nsamples );
+ done();
+ }
+}
+
+/*
+ * Assign samples to the procedures to which they belong.
+ *
+ * There are three cases as to where pcl and pch can be
+ * with respect to the routine entry addresses svalue0 and svalue1
+ * as shown in the following diagram. overlap computes the
+ * distance between the arrows, the fraction of the sample
+ * that is to be credited to the routine which starts at svalue0.
+ *
+ * svalue0 svalue1
+ * | |
+ * v v
+ *
+ * +-----------------------------------------------+
+ * | |
+ * | ->| |<- ->| |<- ->| |<- |
+ * | | | | | |
+ * +---------+ +---------+ +---------+
+ *
+ * ^ ^ ^ ^ ^ ^
+ * | | | | | |
+ * pcl pch pcl pch pcl pch
+ *
+ * For the vax we assert that samples will never fall in the first
+ * two bytes of any routine, since that is the entry mask,
+ * thus we give call alignentries() to adjust the entry points if
+ * the entry mask falls in one bucket but the code for the routine
+ * doesn't start until the next bucket. In conjunction with the
+ * alignment of routine addresses, this should allow us to have
+ * only one sample for every four bytes of text space and never
+ * have any overlap (the two end cases, above).
+ */
+asgnsamples()
+{
+ register int j;
+ UNIT ccnt;
+ double time;
+ unsigned long pcl, pch;
+ register int i;
+ unsigned long overlap;
+ unsigned long svalue0, svalue1;
+
+ /* read samples and assign to namelist symbols */
+ scale = highpc - lowpc;
+ scale /= nsamples;
+ alignentries();
+ for (i = 0, j = 1; i < nsamples; i++) {
+ ccnt = samples[i];
+ if (ccnt == 0)
+ continue;
+ pcl = lowpc + scale * i;
+ pch = lowpc + scale * (i + 1);
+ time = ccnt;
+# ifdef DEBUG
+ if ( debug & SAMPLEDEBUG ) {
+ printf( "[asgnsamples] pcl 0x%x pch 0x%x ccnt %d\n" ,
+ pcl , pch , ccnt );
+ }
+# endif DEBUG
+ totime += time;
+ for (j = j - 1; j < nname; j++) {
+ svalue0 = nl[j].svalue;
+ svalue1 = nl[j+1].svalue;
+ /*
+ * if high end of tick is below entry address,
+ * go for next tick.
+ */
+ if (pch < svalue0)
+ break;
+ /*
+ * if low end of tick into next routine,
+ * go for next routine.
+ */
+ if (pcl >= svalue1)
+ continue;
+ overlap = min(pch, svalue1) - max(pcl, svalue0);
+ if (overlap > 0) {
+# ifdef DEBUG
+ if (debug & SAMPLEDEBUG) {
+ printf("[asgnsamples] (0x%x->0x%x-0x%x) %s gets %f ticks %d overlap\n",
+ nl[j].value/sizeof(UNIT), svalue0, svalue1,
+ nl[j].name,
+ overlap * time / scale, overlap);
+ }
+# endif DEBUG
+ nl[j].time += overlap * time / scale;
+ }
+ }
+ }
+# ifdef DEBUG
+ if (debug & SAMPLEDEBUG) {
+ printf("[asgnsamples] totime %f\n", totime);
+ }
+# endif DEBUG
+}
+
+
+unsigned long
+min(a, b)
+ unsigned long a,b;
+{
+ if (a<b)
+ return(a);
+ return(b);
+}
+
+unsigned long
+max(a, b)
+ unsigned long a,b;
+{
+ if (a>b)
+ return(a);
+ return(b);
+}
+
+ /*
+ * calculate scaled entry point addresses (to save time in asgnsamples),
+ * and possibly push the scaled entry points over the entry mask,
+ * if it turns out that the entry point is in one bucket and the code
+ * for a routine is in the next bucket.
+ */
+alignentries()
+{
+ register struct nl *nlp;
+ unsigned long bucket_of_entry;
+ unsigned long bucket_of_code;
+
+ for (nlp = nl; nlp < npe; nlp++) {
+ nlp -> svalue = nlp -> value / sizeof(UNIT);
+ bucket_of_entry = (nlp->svalue - lowpc) / scale;
+ bucket_of_code = (nlp->svalue + UNITS_TO_CODE - lowpc) / scale;
+ if (bucket_of_entry < bucket_of_code) {
+# ifdef DEBUG
+ if (debug & SAMPLEDEBUG) {
+ printf("[alignentries] pushing svalue 0x%x to 0x%x\n",
+ nlp->svalue, nlp->svalue + UNITS_TO_CODE);
+ }
+# endif DEBUG
+ nlp->svalue += UNITS_TO_CODE;
+ }
+ }
+}
+
+bool
+funcsymbol( nlistp )
+ struct nlist *nlistp;
+{
+ extern char *strtab; /* string table from a.out */
+ extern int aflag; /* if static functions aren't desired */
+ char *name, c;
+
+ /*
+ * must be a text symbol,
+ * and static text symbols don't qualify if aflag set.
+ */
+ if ( ! ( ( nlistp -> n_type == ( N_TEXT | N_EXT ) )
+ || ( ( nlistp -> n_type == N_TEXT ) && ( aflag == 0 ) ) ) ) {
+ return FALSE;
+ }
+ /*
+ * can't have any `funny' characters in name,
+ * where `funny' includes `.', .o file names
+ * and `$', pascal labels.
+ * need to make an exception for sparc .mul & co.
+ * perhaps we should just drop this code entirely...
+ */
+ name = strtab + nlistp -> n_un.n_strx;
+#ifdef sparc
+ if ( *name == '.' ) {
+ char *p = name + 1;
+ if ( *p == 'u' )
+ p++;
+ if ( strcmp ( p, "mul" ) == 0 || strcmp ( p, "div" ) == 0 ||
+ strcmp ( p, "rem" ) == 0 )
+ return TRUE;
+ }
+#endif
+ while ( c = *name++ ) {
+ if ( c == '.' || c == '$' ) {
+ return FALSE;
+ }
+ }
+ return TRUE;
+}
+
+done()
+{
+
+ exit(0);
+}
diff --git a/usr.bin/gprof/gprof.callg b/usr.bin/gprof/gprof.callg
new file mode 100644
index 0000000..533c96c
--- /dev/null
+++ b/usr.bin/gprof/gprof.callg
@@ -0,0 +1,108 @@
+
+
+
+call graph profile:
+ The sum of self and descendents is the major sort
+ for this listing.
+
+ function entries:
+
+index the index of the function in the call graph
+ listing, as an aid to locating it (see below).
+
+%time the percentage of the total time of the program
+ accounted for by this function and its
+ descendents.
+
+self the number of seconds spent in this function
+ itself.
+
+descendents
+ the number of seconds spent in the descendents of
+ this function on behalf of this function.
+
+called the number of times this function is called (other
+ than recursive calls).
+
+self the number of times this function calls itself
+ recursively.
+
+name the name of the function, with an indication of
+ its membership in a cycle, if any.
+
+index the index of the function in the call graph
+ listing, as an aid to locating it.
+
+
+
+ parent listings:
+
+self* the number of seconds of this function's self time
+ which is due to calls from this parent.
+
+descendents*
+ the number of seconds of this function's
+ descendent time which is due to calls from this
+ parent.
+
+called** the number of times this function is called by
+ this parent. This is the numerator of the
+ fraction which divides up the function's time to
+ its parents.
+
+total* the number of times this function was called by
+ all of its parents. This is the denominator of
+ the propagation fraction.
+
+parents the name of this parent, with an indication of the
+ parent's membership in a cycle, if any.
+
+index the index of this parent in the call graph
+ listing, as an aid in locating it.
+
+
+
+ children listings:
+
+self* the number of seconds of this child's self time
+ which is due to being called by this function.
+
+descendent*
+ the number of seconds of this child's descendent's
+ time which is due to being called by this
+ function.
+
+called** the number of times this child is called by this
+ function. This is the numerator of the
+ propagation fraction for this child.
+
+total* the number of times this child is called by all
+ functions. This is the denominator of the
+ propagation fraction.
+
+children the name of this child, and an indication of its
+ membership in a cycle, if any.
+
+index the index of this child in the call graph listing,
+ as an aid to locating it.
+
+
+
+ * these fields are omitted for parents (or
+ children) in the same cycle as the function. If
+ the function (or child) is a member of a cycle,
+ the propagated times and propagation denominator
+ represent the self time and descendent time of the
+ cycle as a whole.
+
+ ** static-only parents and children are indicated
+ by a call count of 0.
+
+
+
+ cycle listings:
+ the cycle as a whole is listed with the same
+ fields as a function entry. Below it are listed
+ the members of the cycle, and their contributions
+ to the time and call counts of the cycle.
+
diff --git a/usr.bin/gprof/gprof.flat b/usr.bin/gprof/gprof.flat
new file mode 100644
index 0000000..60999a3
--- /dev/null
+++ b/usr.bin/gprof/gprof.flat
@@ -0,0 +1,32 @@
+
+
+
+flat profile:
+
+ % the percentage of the total running time of the
+time program used by this function.
+
+cumulative a running sum of the number of seconds accounted
+ seconds for by this function and those listed above it.
+
+ self the number of seconds accounted for by this
+seconds function alone. This is the major sort for this
+ listing.
+
+calls the number of times this function was invoked, if
+ this function is profiled, else blank.
+
+ self the average number of milliseconds spent in this
+ms/call function per call, if this function is profiled,
+ else blank.
+
+ total the average number of milliseconds spent in this
+ms/call function and its descendents per call, if this
+ function is profiled, else blank.
+
+name the name of the function. This is the minor sort
+ for this listing. The index shows the location of
+ the function in the gprof listing. If the index is
+ in parenthesis it shows where it would appear in
+ the gprof listing if it were to be printed.
+
diff --git a/usr.bin/gprof/gprof.h b/usr.bin/gprof/gprof.h
new file mode 100644
index 0000000..ef1cc19
--- /dev/null
+++ b/usr.bin/gprof/gprof.h
@@ -0,0 +1,347 @@
+/*
+ * Copyright (c) 1983, 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.
+ *
+ * @(#)gprof.h 8.1 (Berkeley) 6/6/93
+ */
+
+#include <sys/types.h>
+#include <sys/stat.h>
+#include <sys/gmon.h>
+
+#include <a.out.h>
+#include <stdio.h>
+#include <stdlib.h>
+
+#if vax
+# include "vax.h"
+#endif
+#if sparc
+# include "sparc.h"
+#endif
+#if tahoe
+# include "tahoe.h"
+#endif
+#if hp300
+# include "hp300.h"
+#endif
+#if luna68k
+# include "luna68k.h"
+#endif
+#if i386
+# include "i386.h"
+#endif
+#if mips
+# include "mips.h"
+#endif
+
+
+ /*
+ * who am i, for error messages.
+ */
+char *whoami;
+
+ /*
+ * booleans
+ */
+typedef int bool;
+#define FALSE 0
+#define TRUE 1
+
+ /*
+ * ticks per second
+ */
+long hz;
+
+typedef u_short UNIT; /* unit of profiling */
+char *a_outname;
+#define A_OUTNAME "a.out"
+
+char *gmonname;
+#define GMONNAME "gmon.out"
+#define GMONSUM "gmon.sum"
+
+ /*
+ * a constructed arc,
+ * with pointers to the namelist entry of the parent and the child,
+ * a count of how many times this arc was traversed,
+ * and pointers to the next parent of this child and
+ * the next child of this parent.
+ */
+struct arcstruct {
+ struct nl *arc_parentp; /* pointer to parent's nl entry */
+ struct nl *arc_childp; /* pointer to child's nl entry */
+ long arc_count; /* num calls from parent to child */
+ double arc_time; /* time inherited along arc */
+ double arc_childtime; /* childtime inherited along arc */
+ struct arcstruct *arc_parentlist; /* parents-of-this-child list */
+ struct arcstruct *arc_childlist; /* children-of-this-parent list */
+ struct arcstruct *arc_next; /* list of arcs on cycle */
+ unsigned short arc_cyclecnt; /* num cycles involved in */
+ unsigned short arc_flags; /* see below */
+};
+typedef struct arcstruct arctype;
+
+ /*
+ * arc flags
+ */
+#define DEADARC 0x01 /* time should not propagate across the arc */
+#define ONLIST 0x02 /* arc is on list of arcs in cycles */
+
+ /*
+ * The symbol table;
+ * for each external in the specified file we gather
+ * its address, the number of calls and compute its share of cpu time.
+ */
+struct nl {
+ char *name; /* the name */
+ unsigned long value; /* the pc entry point */
+ unsigned long svalue; /* entry point aligned to histograms */
+ double time; /* ticks in this routine */
+ double childtime; /* cumulative ticks in children */
+ long ncall; /* how many times called */
+ long npropcall; /* times called by live arcs */
+ long selfcalls; /* how many calls to self */
+ double propfraction; /* what % of time propagates */
+ double propself; /* how much self time propagates */
+ double propchild; /* how much child time propagates */
+ short printflag; /* should this be printed? */
+ short flags; /* see below */
+ int index; /* index in the graph list */
+ int toporder; /* graph call chain top-sort order */
+ int cycleno; /* internal number of cycle on */
+ int parentcnt; /* number of live parent arcs */
+ struct nl *cyclehead; /* pointer to head of cycle */
+ struct nl *cnext; /* pointer to next member of cycle */
+ arctype *parents; /* list of caller arcs */
+ arctype *children; /* list of callee arcs */
+};
+typedef struct nl nltype;
+
+nltype *nl; /* the whole namelist */
+nltype *npe; /* the virtual end of the namelist */
+int nname; /* the number of function names */
+
+#define HASCYCLEXIT 0x08 /* node has arc exiting from cycle */
+#define CYCLEHEAD 0x10 /* node marked as head of a cycle */
+#define VISITED 0x20 /* node visited during a cycle */
+
+ /*
+ * The cycle list.
+ * for each subcycle within an identified cycle, we gather
+ * its size and the list of included arcs.
+ */
+struct cl {
+ int size; /* length of cycle */
+ struct cl *next; /* next member of list */
+ arctype *list[1]; /* list of arcs in cycle */
+ /* actually longer */
+};
+typedef struct cl cltype;
+
+arctype *archead; /* the head of arcs in current cycle list */
+cltype *cyclehead; /* the head of the list */
+int cyclecnt; /* the number of cycles found */
+#define CYCLEMAX 100 /* maximum cycles before cutting one of them */
+
+ /*
+ * flag which marks a nl entry as topologically ``busy''
+ * flag which marks a nl entry as topologically ``not_numbered''
+ */
+#define DFN_BUSY -1
+#define DFN_NAN 0
+
+ /*
+ * namelist entries for cycle headers.
+ * the number of discovered cycles.
+ */
+nltype *cyclenl; /* cycle header namelist */
+int ncycle; /* number of cycles discovered */
+
+ /*
+ * The header on the gmon.out file.
+ * gmon.out consists of a struct phdr (defined in gmon.h)
+ * and then an array of ncnt samples representing the
+ * discretized program counter values.
+ *
+ * Backward compatible old style header
+ */
+struct ophdr {
+ UNIT *lpc;
+ UNIT *hpc;
+ int ncnt;
+};
+
+int debug;
+
+ /*
+ * Each discretized pc sample has
+ * a count of the number of samples in its range
+ */
+UNIT *samples;
+
+unsigned long s_lowpc; /* lowpc from the profile file */
+unsigned long s_highpc; /* highpc from the profile file */
+unsigned lowpc, highpc; /* range profiled, in UNIT's */
+unsigned sampbytes; /* number of bytes of samples */
+int nsamples; /* number of samples */
+double actime; /* accumulated time thus far for putprofline */
+double totime; /* total time for all routines */
+double printtime; /* total of time being printed */
+double scale; /* scale factor converting samples to pc
+ values: each sample covers scale bytes */
+char *strtab; /* string table in core */
+long ssiz; /* size of the string table */
+struct exec xbuf; /* exec header of a.out */
+unsigned char *textspace; /* text space of a.out in core */
+int cyclethreshold; /* with -C, minimum cycle size to ignore */
+
+ /*
+ * option flags, from a to z.
+ */
+bool aflag; /* suppress static functions */
+bool bflag; /* blurbs, too */
+bool cflag; /* discovered call graph, too */
+bool Cflag; /* find cut-set to eliminate cycles */
+bool dflag; /* debugging options */
+bool eflag; /* specific functions excluded */
+bool Eflag; /* functions excluded with time */
+bool fflag; /* specific functions requested */
+bool Fflag; /* functions requested with time */
+bool kflag; /* arcs to be deleted */
+bool sflag; /* sum multiple gmon.out files */
+bool zflag; /* zero time/called functions, too */
+
+ /*
+ * structure for various string lists
+ */
+struct stringlist {
+ struct stringlist *next;
+ char *string;
+};
+struct stringlist *elist;
+struct stringlist *Elist;
+struct stringlist *flist;
+struct stringlist *Flist;
+struct stringlist *kfromlist;
+struct stringlist *ktolist;
+
+ /*
+ * function declarations
+ */
+/*
+ addarc();
+*/
+int arccmp();
+arctype *arclookup();
+/*
+ asgnsamples();
+ printblurb();
+ cyclelink();
+ dfn();
+*/
+bool dfn_busy();
+/*
+ dfn_findcycle();
+*/
+bool dfn_numbered();
+/*
+ dfn_post_visit();
+ dfn_pre_visit();
+ dfn_self_cycle();
+*/
+nltype **doarcs();
+/*
+ done();
+ findcalls();
+ flatprofheader();
+ flatprofline();
+*/
+bool funcsymbol();
+/*
+ getnfile();
+ getpfile();
+ getstrtab();
+ getsymtab();
+ gettextspace();
+ gprofheader();
+ gprofline();
+ main();
+*/
+unsigned long max();
+int membercmp();
+unsigned long min();
+nltype *nllookup();
+FILE *openpfile();
+long operandlength();
+operandenum operandmode();
+char *operandname();
+/*
+ printchildren();
+ printcycle();
+ printgprof();
+ printmembers();
+ printname();
+ printparents();
+ printprof();
+ readsamples();
+*/
+unsigned long reladdr();
+/*
+ sortchildren();
+ sortmembers();
+ sortparents();
+ tally();
+ timecmp();
+ topcmp();
+*/
+int totalcmp();
+/*
+ valcmp();
+*/
+
+#define LESSTHAN -1
+#define EQUALTO 0
+#define GREATERTHAN 1
+
+#define DFNDEBUG 1
+#define CYCLEDEBUG 2
+#define ARCDEBUG 4
+#define TALLYDEBUG 8
+#define TIMEDEBUG 16
+#define SAMPLEDEBUG 32
+#define AOUTDEBUG 64
+#define CALLDEBUG 128
+#define LOOKUPDEBUG 256
+#define PROPDEBUG 512
+#define BREAKCYCLE 1024
+#define SUBCYCLELIST 2048
+#define ANYDEBUG 4096
diff --git a/usr.bin/gprof/hertz.c b/usr.bin/gprof/hertz.c
new file mode 100644
index 0000000..41b455f
--- /dev/null
+++ b/usr.bin/gprof/hertz.c
@@ -0,0 +1,59 @@
+/*
+ * Copyright (c) 1983, 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.
+ */
+
+#ifndef lint
+static char sccsid[] = "@(#)hertz.c 8.1 (Berkeley) 6/6/93";
+#endif /* not lint */
+
+#include <sys/time.h>
+
+ /*
+ * discover the tick frequency of the machine
+ * if something goes wrong, we return 0, an impossible hertz.
+ */
+#define HZ_WRONG 0
+
+hertz()
+{
+ struct itimerval tim;
+
+ tim.it_interval.tv_sec = 0;
+ tim.it_interval.tv_usec = 1;
+ tim.it_value.tv_sec = 0;
+ tim.it_value.tv_usec = 0;
+ setitimer(ITIMER_REAL, &tim, 0);
+ setitimer(ITIMER_REAL, 0, &tim);
+ if (tim.it_interval.tv_usec < 2)
+ return(HZ_WRONG);
+ return (1000000 / tim.it_interval.tv_usec);
+}
diff --git a/usr.bin/gprof/hp300.c b/usr.bin/gprof/hp300.c
new file mode 100644
index 0000000..6a47408
--- /dev/null
+++ b/usr.bin/gprof/hp300.c
@@ -0,0 +1,11 @@
+#include "gprof.h"
+
+/*
+ * gprof -c isn't currently supported...
+ */
+findcall( parentp , p_lowpc , p_highpc )
+ nltype *parentp;
+ unsigned long p_lowpc;
+ unsigned long p_highpc;
+{
+}
diff --git a/usr.bin/gprof/hp300.h b/usr.bin/gprof/hp300.h
new file mode 100644
index 0000000..15b9597
--- /dev/null
+++ b/usr.bin/gprof/hp300.h
@@ -0,0 +1,44 @@
+/*-
+ * Copyright (c) 1991, 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.
+ *
+ * @(#)hp300.h 8.1 (Berkeley) 6/6/93
+ */
+
+ /*
+ * offset (in bytes) of the code from the entry address of a routine.
+ * (see asgnsamples for use and explanation.)
+ */
+#define OFFSET_OF_CODE 0
+#define UNITS_TO_CODE (OFFSET_OF_CODE / sizeof(UNIT))
+
+enum opermodes { dummy };
+typedef enum opermodes operandenum;
diff --git a/usr.bin/gprof/i386.c b/usr.bin/gprof/i386.c
new file mode 100644
index 0000000..6a47408
--- /dev/null
+++ b/usr.bin/gprof/i386.c
@@ -0,0 +1,11 @@
+#include "gprof.h"
+
+/*
+ * gprof -c isn't currently supported...
+ */
+findcall( parentp , p_lowpc , p_highpc )
+ nltype *parentp;
+ unsigned long p_lowpc;
+ unsigned long p_highpc;
+{
+}
diff --git a/usr.bin/gprof/i386.h b/usr.bin/gprof/i386.h
new file mode 100644
index 0000000..067e019
--- /dev/null
+++ b/usr.bin/gprof/i386.h
@@ -0,0 +1,44 @@
+/*-
+ * Copyright (c) 1991, 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.
+ *
+ * @(#)i386.h 8.1 (Berkeley) 6/6/93
+ */
+
+ /*
+ * offset (in bytes) of the code from the entry address of a routine.
+ * (see asgnsamples for use and explanation.)
+ */
+#define OFFSET_OF_CODE 0
+#define UNITS_TO_CODE (OFFSET_OF_CODE / sizeof(UNIT))
+
+enum opermodes { dummy };
+typedef enum opermodes operandenum;
diff --git a/usr.bin/gprof/lookup.c b/usr.bin/gprof/lookup.c
new file mode 100644
index 0000000..d63c13bf
--- /dev/null
+++ b/usr.bin/gprof/lookup.c
@@ -0,0 +1,115 @@
+/*
+ * Copyright (c) 1983, 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.
+ */
+
+#ifndef lint
+static char sccsid[] = "@(#)lookup.c 8.1 (Berkeley) 6/6/93";
+#endif /* not lint */
+
+#include "gprof.h"
+
+ /*
+ * look up an address in a sorted-by-address namelist
+ * this deals with misses by mapping them to the next lower
+ * entry point.
+ */
+nltype *
+nllookup( address )
+ unsigned long address;
+{
+ register long low;
+ register long middle;
+ register long high;
+# ifdef DEBUG
+ register int probes;
+
+ probes = 0;
+# endif DEBUG
+ for ( low = 0 , high = nname - 1 ; low != high ; ) {
+# ifdef DEBUG
+ probes += 1;
+# endif DEBUG
+ middle = ( high + low ) >> 1;
+ if ( nl[ middle ].value <= address && nl[ middle+1 ].value > address ) {
+# ifdef DEBUG
+ if ( debug & LOOKUPDEBUG ) {
+ printf( "[nllookup] %d (%d) probes\n" , probes , nname-1 );
+ }
+# endif DEBUG
+ return &nl[ middle ];
+ }
+ if ( nl[ middle ].value > address ) {
+ high = middle;
+ } else {
+ low = middle + 1;
+ }
+ }
+# ifdef DEBUG
+ if ( debug & LOOKUPDEBUG ) {
+ fprintf( stderr , "[nllookup] (%d) binary search fails\n" ,
+ nname-1 );
+ }
+# endif DEBUG
+ return 0;
+}
+
+arctype *
+arclookup( parentp , childp )
+ nltype *parentp;
+ nltype *childp;
+{
+ arctype *arcp;
+
+ if ( parentp == 0 || childp == 0 ) {
+ fprintf( stderr, "[arclookup] parentp == 0 || childp == 0\n" );
+ return 0;
+ }
+# ifdef DEBUG
+ if ( debug & LOOKUPDEBUG ) {
+ printf( "[arclookup] parent %s child %s\n" ,
+ parentp -> name , childp -> name );
+ }
+# endif DEBUG
+ for ( arcp = parentp -> children ; arcp ; arcp = arcp -> arc_childlist ) {
+# ifdef DEBUG
+ if ( debug & LOOKUPDEBUG ) {
+ printf( "[arclookup]\t arc_parent %s arc_child %s\n" ,
+ arcp -> arc_parentp -> name ,
+ arcp -> arc_childp -> name );
+ }
+# endif DEBUG
+ if ( arcp -> arc_childp == childp ) {
+ return arcp;
+ }
+ }
+ return 0;
+}
diff --git a/usr.bin/gprof/mips.c b/usr.bin/gprof/mips.c
new file mode 100644
index 0000000..295d64e
--- /dev/null
+++ b/usr.bin/gprof/mips.c
@@ -0,0 +1,112 @@
+/*
+ * Copyright (c) 1992, 1993
+ * The Regents of the University of California. All rights reserved.
+ *
+ * This software was developed by the Computer Systems Engineering group
+ * at Lawrence Berkeley Laboratory under DARPA contract BG 91-66 and
+ * contributed to Berkeley. Modified by Ralph Campbell for mips.
+ *
+ * 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.
+ *
+ * From: sparc.c 5.1 (Berkeley) 7/7/92
+ */
+
+#ifndef lint
+static char sccsid[] = "@(#)mips.c 8.1 (Berkeley) 6/6/93";
+#endif /* not lint */
+
+#include "gprof.h"
+
+ /*
+ * a namelist entry to be the child of indirect calls
+ */
+nltype indirectchild = {
+ "(*)" , /* the name */
+ (unsigned long) 0 , /* the pc entry point */
+ (unsigned long) 0 , /* entry point aligned to histogram */
+ (double) 0.0 , /* ticks in this routine */
+ (double) 0.0 , /* cumulative ticks in children */
+ (long) 0 , /* how many times called */
+ (long) 0 , /* times called by live arcs */
+ (long) 0 , /* how many calls to self */
+ (double) 1.0 , /* propagation fraction */
+ (double) 0.0 , /* self propagation time */
+ (double) 0.0 , /* child propagation time */
+ (short) 0 , /* print flag */
+ (short) 0 , /* flags */
+ (int) 0 , /* index in the graph list */
+ (int) 0 , /* graph call chain top-sort order */
+ (int) 0 , /* internal number of cycle on */
+ (int) 0 , /* number of live parent arcs */
+ (struct nl *) &indirectchild , /* pointer to head of cycle */
+ (struct nl *) 0 , /* pointer to next member of cycle */
+ (arctype *) 0 , /* list of caller arcs */
+ (arctype *) 0 /* list of callee arcs */
+};
+
+findcall(parentp, p_lowpc, p_highpc)
+ nltype *parentp;
+ unsigned long p_lowpc;
+ unsigned long p_highpc;
+{
+ register u_long pc;
+ nltype *childp;
+ unsigned long destpc;
+ register long op;
+ register int off;
+
+ if (textspace == 0)
+ return;
+ if (p_lowpc < s_lowpc)
+ p_lowpc = s_lowpc;
+ if (p_highpc > s_highpc)
+ p_highpc = s_highpc;
+
+ for (pc = p_lowpc; pc < p_highpc; pc += 4) {
+ off = pc - s_lowpc;
+ op = *(u_long *)&textspace[off];
+ if ((op & 0xfc000000) == 0x0c000000) {
+ /*
+ * a jal insn -- check that this
+ * is the address of a function.
+ */
+ off = (op & 0x03ffffff) << 2;
+ destpc = (pc & 0xf0000000) | off;
+ if (destpc >= s_lowpc && destpc <= s_highpc) {
+ childp = nllookup(destpc);
+ if (childp != 0 && childp->value == destpc)
+ addarc(parentp, childp, 0L);
+ }
+ } else if ((op & 0xfc00f83f) == 0x0000f809)
+ /*
+ * A jalr -- an indirect call.
+ */
+ addarc(parentp, &indirectchild, 0L);
+ }
+}
diff --git a/usr.bin/gprof/mips.h b/usr.bin/gprof/mips.h
new file mode 100644
index 0000000..cd67a43
--- /dev/null
+++ b/usr.bin/gprof/mips.h
@@ -0,0 +1,50 @@
+/*-
+ * Copyright (c) 1992, 1993
+ * The Regents of the University of California. All rights reserved.
+ *
+ * This software was developed by the Computer Systems Engineering group
+ * at Lawrence Berkeley Laboratory under DARPA contract BG 91-66 and
+ * contributed to Berkeley. Modified by Ralph Campbell for mips.
+ *
+ * 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.
+ *
+ * @(#)mips.h 8.1 (Berkeley) 6/6/93
+ *
+ * From: @(#)sparc.h 5.1 (Berkeley) 7/8/92
+ */
+
+/*
+ * offset (in bytes) of the code from the entry address of a routine.
+ * (see asgnsamples for use and explanation.)
+ */
+#define OFFSET_OF_CODE 0
+#define UNITS_TO_CODE (OFFSET_OF_CODE / sizeof(UNIT))
+
+enum opermodes { dummy };
+typedef enum opermodes operandenum;
diff --git a/usr.bin/gprof/pathnames.h b/usr.bin/gprof/pathnames.h
new file mode 100644
index 0000000..ea554c6
--- /dev/null
+++ b/usr.bin/gprof/pathnames.h
@@ -0,0 +1,38 @@
+/*
+ * Copyright (c) 1989, 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.
+ *
+ * @(#)pathnames.h 8.1 (Berkeley) 6/6/93
+ */
+
+#define _PATH_FLAT_BLURB "/usr/share/misc/gprof.flat"
+#define _PATH_CALLG_BLURB "/usr/share/misc/gprof.callg"
+
diff --git a/usr.bin/gprof/printgprof.c b/usr.bin/gprof/printgprof.c
new file mode 100644
index 0000000..5ede772
--- /dev/null
+++ b/usr.bin/gprof/printgprof.c
@@ -0,0 +1,718 @@
+/*
+ * Copyright (c) 1983, 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.
+ */
+
+#ifndef lint
+static char sccsid[] = "@(#)printgprof.c 8.1 (Berkeley) 6/6/93";
+#endif /* not lint */
+
+#include "gprof.h"
+#include "pathnames.h"
+
+printprof()
+{
+ register nltype *np;
+ nltype **sortednlp;
+ int index, timecmp();
+
+ actime = 0.0;
+ printf( "\f\n" );
+ flatprofheader();
+ /*
+ * Sort the symbol table in by time
+ */
+ sortednlp = (nltype **) calloc( nname , sizeof(nltype *) );
+ if ( sortednlp == (nltype **) 0 ) {
+ fprintf( stderr , "[printprof] ran out of memory for time sorting\n" );
+ }
+ for ( index = 0 ; index < nname ; index += 1 ) {
+ sortednlp[ index ] = &nl[ index ];
+ }
+ qsort( sortednlp , nname , sizeof(nltype *) , timecmp );
+ for ( index = 0 ; index < nname ; index += 1 ) {
+ np = sortednlp[ index ];
+ flatprofline( np );
+ }
+ actime = 0.0;
+ free( sortednlp );
+}
+
+timecmp( npp1 , npp2 )
+ nltype **npp1, **npp2;
+{
+ double timediff;
+ long calldiff;
+
+ timediff = (*npp2) -> time - (*npp1) -> time;
+ if ( timediff > 0.0 )
+ return 1 ;
+ if ( timediff < 0.0 )
+ return -1;
+ calldiff = (*npp2) -> ncall - (*npp1) -> ncall;
+ if ( calldiff > 0 )
+ return 1;
+ if ( calldiff < 0 )
+ return -1;
+ return( strcmp( (*npp1) -> name , (*npp2) -> name ) );
+}
+
+ /*
+ * header for flatprofline
+ */
+flatprofheader()
+{
+
+ if ( bflag ) {
+ printblurb( _PATH_FLAT_BLURB );
+ }
+ printf( "\ngranularity: each sample hit covers %d byte(s)" ,
+ (long) scale * sizeof(UNIT) );
+ if ( totime > 0.0 ) {
+ printf( " for %.2f%% of %.2f seconds\n\n" ,
+ 100.0/totime , totime / hz );
+ } else {
+ printf( " no time accumulated\n\n" );
+ /*
+ * this doesn't hurt sinc eall the numerators will be zero.
+ */
+ totime = 1.0;
+ }
+ printf( "%5.5s %10.10s %8.8s %8.8s %8.8s %8.8s %-8.8s\n" ,
+ "% " , "cumulative" , "self " , "" , "self " , "total " , "" );
+ printf( "%5.5s %10.10s %8.8s %8.8s %8.8s %8.8s %-8.8s\n" ,
+ "time" , "seconds " , "seconds" , "calls" ,
+ "ms/call" , "ms/call" , "name" );
+}
+
+flatprofline( np )
+ register nltype *np;
+{
+
+ if ( zflag == 0 && np -> ncall == 0 && np -> time == 0 ) {
+ return;
+ }
+ actime += np -> time;
+ printf( "%5.1f %10.2f %8.2f" ,
+ 100 * np -> time / totime , actime / hz , np -> time / hz );
+ if ( np -> ncall != 0 ) {
+ printf( " %8d %8.2f %8.2f " , np -> ncall ,
+ 1000 * np -> time / hz / np -> ncall ,
+ 1000 * ( np -> time + np -> childtime ) / hz / np -> ncall );
+ } else {
+ printf( " %8.8s %8.8s %8.8s " , "" , "" , "" );
+ }
+ printname( np );
+ printf( "\n" );
+}
+
+gprofheader()
+{
+
+ if ( bflag ) {
+ printblurb( _PATH_CALLG_BLURB );
+ }
+ printf( "\ngranularity: each sample hit covers %d byte(s)" ,
+ (long) scale * sizeof(UNIT) );
+ if ( printtime > 0.0 ) {
+ printf( " for %.2f%% of %.2f seconds\n\n" ,
+ 100.0/printtime , printtime / hz );
+ } else {
+ printf( " no time propagated\n\n" );
+ /*
+ * this doesn't hurt, since all the numerators will be 0.0
+ */
+ printtime = 1.0;
+ }
+ printf( "%6.6s %5.5s %7.7s %11.11s %7.7s/%-7.7s %-8.8s\n" ,
+ "" , "" , "" , "" , "called" , "total" , "parents");
+ printf( "%-6.6s %5.5s %7.7s %11.11s %7.7s+%-7.7s %-8.8s\t%5.5s\n" ,
+ "index" , "%time" , "self" , "descendents" ,
+ "called" , "self" , "name" , "index" );
+ printf( "%6.6s %5.5s %7.7s %11.11s %7.7s/%-7.7s %-8.8s\n" ,
+ "" , "" , "" , "" , "called" , "total" , "children");
+ printf( "\n" );
+}
+
+gprofline( np )
+ register nltype *np;
+{
+ char kirkbuffer[ BUFSIZ ];
+
+ sprintf( kirkbuffer , "[%d]" , np -> index );
+ printf( "%-6.6s %5.1f %7.2f %11.2f" ,
+ kirkbuffer ,
+ 100 * ( np -> propself + np -> propchild ) / printtime ,
+ np -> propself / hz ,
+ np -> propchild / hz );
+ if ( ( np -> ncall + np -> selfcalls ) != 0 ) {
+ printf( " %7d" , np -> npropcall );
+ if ( np -> selfcalls != 0 ) {
+ printf( "+%-7d " , np -> selfcalls );
+ } else {
+ printf( " %7.7s " , "" );
+ }
+ } else {
+ printf( " %7.7s %7.7s " , "" , "" );
+ }
+ printname( np );
+ printf( "\n" );
+}
+
+printgprof(timesortnlp)
+ nltype **timesortnlp;
+{
+ int index;
+ nltype *parentp;
+
+ /*
+ * Print out the structured profiling list
+ */
+ gprofheader();
+ for ( index = 0 ; index < nname + ncycle ; index ++ ) {
+ parentp = timesortnlp[ index ];
+ if ( zflag == 0 &&
+ parentp -> ncall == 0 &&
+ parentp -> selfcalls == 0 &&
+ parentp -> propself == 0 &&
+ parentp -> propchild == 0 ) {
+ continue;
+ }
+ if ( ! parentp -> printflag ) {
+ continue;
+ }
+ if ( parentp -> name == 0 && parentp -> cycleno != 0 ) {
+ /*
+ * cycle header
+ */
+ printcycle( parentp );
+ printmembers( parentp );
+ } else {
+ printparents( parentp );
+ gprofline( parentp );
+ printchildren( parentp );
+ }
+ printf( "\n" );
+ printf( "-----------------------------------------------\n" );
+ printf( "\n" );
+ }
+ free( timesortnlp );
+}
+
+ /*
+ * sort by decreasing propagated time
+ * if times are equal, but one is a cycle header,
+ * say that's first (e.g. less, i.e. -1).
+ * if one's name doesn't have an underscore and the other does,
+ * say the one is first.
+ * all else being equal, sort by names.
+ */
+int
+totalcmp( npp1 , npp2 )
+ nltype **npp1;
+ nltype **npp2;
+{
+ register nltype *np1 = *npp1;
+ register nltype *np2 = *npp2;
+ double diff;
+
+ diff = ( np1 -> propself + np1 -> propchild )
+ - ( np2 -> propself + np2 -> propchild );
+ if ( diff < 0.0 )
+ return 1;
+ if ( diff > 0.0 )
+ return -1;
+ if ( np1 -> name == 0 && np1 -> cycleno != 0 )
+ return -1;
+ if ( np2 -> name == 0 && np2 -> cycleno != 0 )
+ return 1;
+ if ( np1 -> name == 0 )
+ return -1;
+ if ( np2 -> name == 0 )
+ return 1;
+ if ( *(np1 -> name) != '_' && *(np2 -> name) == '_' )
+ return -1;
+ if ( *(np1 -> name) == '_' && *(np2 -> name) != '_' )
+ return 1;
+ if ( np1 -> ncall > np2 -> ncall )
+ return -1;
+ if ( np1 -> ncall < np2 -> ncall )
+ return 1;
+ return strcmp( np1 -> name , np2 -> name );
+}
+
+printparents( childp )
+ nltype *childp;
+{
+ nltype *parentp;
+ arctype *arcp;
+ nltype *cycleheadp;
+
+ if ( childp -> cyclehead != 0 ) {
+ cycleheadp = childp -> cyclehead;
+ } else {
+ cycleheadp = childp;
+ }
+ if ( childp -> parents == 0 ) {
+ printf( "%6.6s %5.5s %7.7s %11.11s %7.7s %7.7s <spontaneous>\n" ,
+ "" , "" , "" , "" , "" , "" );
+ return;
+ }
+ sortparents( childp );
+ for ( arcp = childp -> parents ; arcp ; arcp = arcp -> arc_parentlist ) {
+ parentp = arcp -> arc_parentp;
+ if ( childp == parentp || ( arcp -> arc_flags & DEADARC ) ||
+ ( childp->cycleno != 0 && parentp->cycleno == childp->cycleno ) ) {
+ /*
+ * selfcall or call among siblings
+ */
+ printf( "%6.6s %5.5s %7.7s %11.11s %7d %7.7s " ,
+ "" , "" , "" , "" ,
+ arcp -> arc_count , "" );
+ printname( parentp );
+ printf( "\n" );
+ } else {
+ /*
+ * regular parent of child
+ */
+ printf( "%6.6s %5.5s %7.2f %11.2f %7d/%-7d " ,
+ "" , "" ,
+ arcp -> arc_time / hz , arcp -> arc_childtime / hz ,
+ arcp -> arc_count , cycleheadp -> npropcall );
+ printname( parentp );
+ printf( "\n" );
+ }
+ }
+}
+
+printchildren( parentp )
+ nltype *parentp;
+{
+ nltype *childp;
+ arctype *arcp;
+
+ sortchildren( parentp );
+ arcp = parentp -> children;
+ for ( arcp = parentp -> children ; arcp ; arcp = arcp -> arc_childlist ) {
+ childp = arcp -> arc_childp;
+ if ( childp == parentp || ( arcp -> arc_flags & DEADARC ) ||
+ ( childp->cycleno != 0 && childp->cycleno == parentp->cycleno ) ) {
+ /*
+ * self call or call to sibling
+ */
+ printf( "%6.6s %5.5s %7.7s %11.11s %7d %7.7s " ,
+ "" , "" , "" , "" , arcp -> arc_count , "" );
+ printname( childp );
+ printf( "\n" );
+ } else {
+ /*
+ * regular child of parent
+ */
+ printf( "%6.6s %5.5s %7.2f %11.2f %7d/%-7d " ,
+ "" , "" ,
+ arcp -> arc_time / hz , arcp -> arc_childtime / hz ,
+ arcp -> arc_count , childp -> cyclehead -> npropcall );
+ printname( childp );
+ printf( "\n" );
+ }
+ }
+}
+
+printname( selfp )
+ nltype *selfp;
+{
+
+ if ( selfp -> name != 0 ) {
+ printf( "%s" , selfp -> name );
+# ifdef DEBUG
+ if ( debug & DFNDEBUG ) {
+ printf( "{%d} " , selfp -> toporder );
+ }
+ if ( debug & PROPDEBUG ) {
+ printf( "%5.2f%% " , selfp -> propfraction );
+ }
+# endif DEBUG
+ }
+ if ( selfp -> cycleno != 0 ) {
+ printf( " <cycle %d>" , selfp -> cycleno );
+ }
+ if ( selfp -> index != 0 ) {
+ if ( selfp -> printflag ) {
+ printf( " [%d]" , selfp -> index );
+ } else {
+ printf( " (%d)" , selfp -> index );
+ }
+ }
+}
+
+sortchildren( parentp )
+ nltype *parentp;
+{
+ arctype *arcp;
+ arctype *detachedp;
+ arctype sorted;
+ arctype *prevp;
+
+ /*
+ * unlink children from parent,
+ * then insertion sort back on to sorted's children.
+ * *arcp the arc you have detached and are inserting.
+ * *detachedp the rest of the arcs to be sorted.
+ * sorted arc list onto which you insertion sort.
+ * *prevp arc before the arc you are comparing.
+ */
+ sorted.arc_childlist = 0;
+ for ( (arcp = parentp -> children)&&(detachedp = arcp -> arc_childlist);
+ arcp ;
+ (arcp = detachedp)&&(detachedp = detachedp -> arc_childlist)) {
+ /*
+ * consider *arcp as disconnected
+ * insert it into sorted
+ */
+ for ( prevp = &sorted ;
+ prevp -> arc_childlist ;
+ prevp = prevp -> arc_childlist ) {
+ if ( arccmp( arcp , prevp -> arc_childlist ) != LESSTHAN ) {
+ break;
+ }
+ }
+ arcp -> arc_childlist = prevp -> arc_childlist;
+ prevp -> arc_childlist = arcp;
+ }
+ /*
+ * reattach sorted children to parent
+ */
+ parentp -> children = sorted.arc_childlist;
+}
+
+sortparents( childp )
+ nltype *childp;
+{
+ arctype *arcp;
+ arctype *detachedp;
+ arctype sorted;
+ arctype *prevp;
+
+ /*
+ * unlink parents from child,
+ * then insertion sort back on to sorted's parents.
+ * *arcp the arc you have detached and are inserting.
+ * *detachedp the rest of the arcs to be sorted.
+ * sorted arc list onto which you insertion sort.
+ * *prevp arc before the arc you are comparing.
+ */
+ sorted.arc_parentlist = 0;
+ for ( (arcp = childp -> parents)&&(detachedp = arcp -> arc_parentlist);
+ arcp ;
+ (arcp = detachedp)&&(detachedp = detachedp -> arc_parentlist)) {
+ /*
+ * consider *arcp as disconnected
+ * insert it into sorted
+ */
+ for ( prevp = &sorted ;
+ prevp -> arc_parentlist ;
+ prevp = prevp -> arc_parentlist ) {
+ if ( arccmp( arcp , prevp -> arc_parentlist ) != GREATERTHAN ) {
+ break;
+ }
+ }
+ arcp -> arc_parentlist = prevp -> arc_parentlist;
+ prevp -> arc_parentlist = arcp;
+ }
+ /*
+ * reattach sorted arcs to child
+ */
+ childp -> parents = sorted.arc_parentlist;
+}
+
+ /*
+ * print a cycle header
+ */
+printcycle( cyclep )
+ nltype *cyclep;
+{
+ char kirkbuffer[ BUFSIZ ];
+
+ sprintf( kirkbuffer , "[%d]" , cyclep -> index );
+ printf( "%-6.6s %5.1f %7.2f %11.2f %7d" ,
+ kirkbuffer ,
+ 100 * ( cyclep -> propself + cyclep -> propchild ) / printtime ,
+ cyclep -> propself / hz ,
+ cyclep -> propchild / hz ,
+ cyclep -> npropcall );
+ if ( cyclep -> selfcalls != 0 ) {
+ printf( "+%-7d" , cyclep -> selfcalls );
+ } else {
+ printf( " %7.7s" , "" );
+ }
+ printf( " <cycle %d as a whole>\t[%d]\n" ,
+ cyclep -> cycleno , cyclep -> index );
+}
+
+ /*
+ * print the members of a cycle
+ */
+printmembers( cyclep )
+ nltype *cyclep;
+{
+ nltype *memberp;
+
+ sortmembers( cyclep );
+ for ( memberp = cyclep -> cnext ; memberp ; memberp = memberp -> cnext ) {
+ printf( "%6.6s %5.5s %7.2f %11.2f %7d" ,
+ "" , "" , memberp -> propself / hz , memberp -> propchild / hz ,
+ memberp -> npropcall );
+ if ( memberp -> selfcalls != 0 ) {
+ printf( "+%-7d" , memberp -> selfcalls );
+ } else {
+ printf( " %7.7s" , "" );
+ }
+ printf( " " );
+ printname( memberp );
+ printf( "\n" );
+ }
+}
+
+ /*
+ * sort members of a cycle
+ */
+sortmembers( cyclep )
+ nltype *cyclep;
+{
+ nltype *todo;
+ nltype *doing;
+ nltype *prev;
+
+ /*
+ * detach cycle members from cyclehead,
+ * and insertion sort them back on.
+ */
+ todo = cyclep -> cnext;
+ cyclep -> cnext = 0;
+ for ( (doing = todo)&&(todo = doing -> cnext);
+ doing ;
+ (doing = todo )&&(todo = doing -> cnext )){
+ for ( prev = cyclep ; prev -> cnext ; prev = prev -> cnext ) {
+ if ( membercmp( doing , prev -> cnext ) == GREATERTHAN ) {
+ break;
+ }
+ }
+ doing -> cnext = prev -> cnext;
+ prev -> cnext = doing;
+ }
+}
+
+ /*
+ * major sort is on propself + propchild,
+ * next is sort on ncalls + selfcalls.
+ */
+int
+membercmp( this , that )
+ nltype *this;
+ nltype *that;
+{
+ double thistime = this -> propself + this -> propchild;
+ double thattime = that -> propself + that -> propchild;
+ long thiscalls = this -> ncall + this -> selfcalls;
+ long thatcalls = that -> ncall + that -> selfcalls;
+
+ if ( thistime > thattime ) {
+ return GREATERTHAN;
+ }
+ if ( thistime < thattime ) {
+ return LESSTHAN;
+ }
+ if ( thiscalls > thatcalls ) {
+ return GREATERTHAN;
+ }
+ if ( thiscalls < thatcalls ) {
+ return LESSTHAN;
+ }
+ return EQUALTO;
+}
+ /*
+ * compare two arcs to/from the same child/parent.
+ * - if one arc is a self arc, it's least.
+ * - if one arc is within a cycle, it's less than.
+ * - if both arcs are within a cycle, compare arc counts.
+ * - if neither arc is within a cycle, compare with
+ * arc_time + arc_childtime as major key
+ * arc count as minor key
+ */
+int
+arccmp( thisp , thatp )
+ arctype *thisp;
+ arctype *thatp;
+{
+ nltype *thisparentp = thisp -> arc_parentp;
+ nltype *thischildp = thisp -> arc_childp;
+ nltype *thatparentp = thatp -> arc_parentp;
+ nltype *thatchildp = thatp -> arc_childp;
+ double thistime;
+ double thattime;
+
+# ifdef DEBUG
+ if ( debug & TIMEDEBUG ) {
+ printf( "[arccmp] " );
+ printname( thisparentp );
+ printf( " calls " );
+ printname ( thischildp );
+ printf( " %f + %f %d/%d\n" ,
+ thisp -> arc_time , thisp -> arc_childtime ,
+ thisp -> arc_count , thischildp -> ncall );
+ printf( "[arccmp] " );
+ printname( thatparentp );
+ printf( " calls " );
+ printname( thatchildp );
+ printf( " %f + %f %d/%d\n" ,
+ thatp -> arc_time , thatp -> arc_childtime ,
+ thatp -> arc_count , thatchildp -> ncall );
+ printf( "\n" );
+ }
+# endif DEBUG
+ if ( thisparentp == thischildp ) {
+ /* this is a self call */
+ return LESSTHAN;
+ }
+ if ( thatparentp == thatchildp ) {
+ /* that is a self call */
+ return GREATERTHAN;
+ }
+ if ( thisparentp -> cycleno != 0 && thischildp -> cycleno != 0 &&
+ thisparentp -> cycleno == thischildp -> cycleno ) {
+ /* this is a call within a cycle */
+ if ( thatparentp -> cycleno != 0 && thatchildp -> cycleno != 0 &&
+ thatparentp -> cycleno == thatchildp -> cycleno ) {
+ /* that is a call within the cycle, too */
+ if ( thisp -> arc_count < thatp -> arc_count ) {
+ return LESSTHAN;
+ }
+ if ( thisp -> arc_count > thatp -> arc_count ) {
+ return GREATERTHAN;
+ }
+ return EQUALTO;
+ } else {
+ /* that isn't a call within the cycle */
+ return LESSTHAN;
+ }
+ } else {
+ /* this isn't a call within a cycle */
+ if ( thatparentp -> cycleno != 0 && thatchildp -> cycleno != 0 &&
+ thatparentp -> cycleno == thatchildp -> cycleno ) {
+ /* that is a call within a cycle */
+ return GREATERTHAN;
+ } else {
+ /* neither is a call within a cycle */
+ thistime = thisp -> arc_time + thisp -> arc_childtime;
+ thattime = thatp -> arc_time + thatp -> arc_childtime;
+ if ( thistime < thattime )
+ return LESSTHAN;
+ if ( thistime > thattime )
+ return GREATERTHAN;
+ if ( thisp -> arc_count < thatp -> arc_count )
+ return LESSTHAN;
+ if ( thisp -> arc_count > thatp -> arc_count )
+ return GREATERTHAN;
+ return EQUALTO;
+ }
+ }
+}
+
+printblurb( blurbname )
+ char *blurbname;
+{
+ FILE *blurbfile;
+ int input;
+
+ blurbfile = fopen( blurbname , "r" );
+ if ( blurbfile == NULL ) {
+ perror( blurbname );
+ return;
+ }
+ while ( ( input = getc( blurbfile ) ) != EOF ) {
+ putchar( input );
+ }
+ fclose( blurbfile );
+}
+
+int
+namecmp( npp1 , npp2 )
+ nltype **npp1, **npp2;
+{
+ return( strcmp( (*npp1) -> name , (*npp2) -> name ) );
+}
+
+printindex()
+{
+ nltype **namesortnlp;
+ register nltype *nlp;
+ int index, nnames, todo, i, j;
+ char peterbuffer[ BUFSIZ ];
+
+ /*
+ * Now, sort regular function name alphbetically
+ * to create an index.
+ */
+ namesortnlp = (nltype **) calloc( nname + ncycle , sizeof(nltype *) );
+ if ( namesortnlp == (nltype **) 0 ) {
+ fprintf( stderr , "%s: ran out of memory for sorting\n" , whoami );
+ }
+ for ( index = 0 , nnames = 0 ; index < nname ; index++ ) {
+ if ( zflag == 0 && nl[index].ncall == 0 && nl[index].time == 0 )
+ continue;
+ namesortnlp[nnames++] = &nl[index];
+ }
+ qsort( namesortnlp , nnames , sizeof(nltype *) , namecmp );
+ for ( index = 1 , todo = nnames ; index <= ncycle ; index++ ) {
+ namesortnlp[todo++] = &cyclenl[index];
+ }
+ printf( "\f\nIndex by function name\n\n" );
+ index = ( todo + 2 ) / 3;
+ for ( i = 0; i < index ; i++ ) {
+ for ( j = i; j < todo ; j += index ) {
+ nlp = namesortnlp[ j ];
+ if ( nlp -> printflag ) {
+ sprintf( peterbuffer , "[%d]" , nlp -> index );
+ } else {
+ sprintf( peterbuffer , "(%d)" , nlp -> index );
+ }
+ if ( j < nnames ) {
+ printf( "%6.6s %-19.19s" , peterbuffer , nlp -> name );
+ } else {
+ printf( "%6.6s " , peterbuffer );
+ sprintf( peterbuffer , "<cycle %d>" , nlp -> cycleno );
+ printf( "%-19.19s" , peterbuffer );
+ }
+ }
+ printf( "\n" );
+ }
+ free( namesortnlp );
+}
diff --git a/usr.bin/gprof/printlist.c b/usr.bin/gprof/printlist.c
new file mode 100644
index 0000000..f29ecc9
--- /dev/null
+++ b/usr.bin/gprof/printlist.c
@@ -0,0 +1,91 @@
+/*
+ * Copyright (c) 1983, 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.
+ */
+
+#ifndef lint
+static char sccsid[] = "@(#)printlist.c 8.1 (Berkeley) 6/6/93";
+#endif /* not lint */
+
+#include "gprof.h"
+
+ /*
+ * these are the lists of names:
+ * there is the list head and then the listname
+ * is a pointer to the list head
+ * (for ease of passing to stringlist functions).
+ */
+struct stringlist kfromhead = { 0 , 0 };
+struct stringlist *kfromlist = &kfromhead;
+struct stringlist ktohead = { 0 , 0 };
+struct stringlist *ktolist = &ktohead;
+struct stringlist fhead = { 0 , 0 };
+struct stringlist *flist = &fhead;
+struct stringlist Fhead = { 0 , 0 };
+struct stringlist *Flist = &Fhead;
+struct stringlist ehead = { 0 , 0 };
+struct stringlist *elist = &ehead;
+struct stringlist Ehead = { 0 , 0 };
+struct stringlist *Elist = &Ehead;
+
+addlist( listp , funcname )
+ struct stringlist *listp;
+ char *funcname;
+{
+ struct stringlist *slp;
+
+ slp = (struct stringlist *) malloc( sizeof(struct stringlist));
+ if ( slp == (struct stringlist *) 0 ) {
+ fprintf( stderr, "gprof: ran out room for printlist\n" );
+ done();
+ }
+ slp -> next = listp -> next;
+ slp -> string = funcname;
+ listp -> next = slp;
+}
+
+bool
+onlist( listp , funcname )
+ struct stringlist *listp;
+ char *funcname;
+{
+ struct stringlist *slp;
+
+ for ( slp = listp -> next ; slp ; slp = slp -> next ) {
+ if ( ! strcmp( slp -> string , funcname ) ) {
+ return TRUE;
+ }
+ if ( funcname[0] == '_' && ! strcmp( slp -> string , &funcname[1] ) ) {
+ return TRUE;
+ }
+ }
+ return FALSE;
+}
diff --git a/usr.bin/gprof/sparc.c b/usr.bin/gprof/sparc.c
new file mode 100644
index 0000000..513a525
--- /dev/null
+++ b/usr.bin/gprof/sparc.c
@@ -0,0 +1,110 @@
+/*
+ * Copyright (c) 1992, 1993
+ * The Regents of the University of California. All rights reserved.
+ *
+ * This software was developed by the Computer Systems Engineering group
+ * at Lawrence Berkeley Laboratory under DARPA contract BG 91-66 and
+ * contributed to Berkeley.
+ *
+ * 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.
+ */
+
+#ifndef lint
+static char sccsid[] = "@(#)sparc.c 8.1 (Berkeley) 6/6/93";
+#endif /* not lint */
+
+#include "gprof.h"
+
+ /*
+ * a namelist entry to be the child of indirect calls
+ */
+nltype indirectchild = {
+ "(*)" , /* the name */
+ (unsigned long) 0 , /* the pc entry point */
+ (unsigned long) 0 , /* entry point aligned to histogram */
+ (double) 0.0 , /* ticks in this routine */
+ (double) 0.0 , /* cumulative ticks in children */
+ (long) 0 , /* how many times called */
+ (long) 0 , /* times called by live arcs */
+ (long) 0 , /* how many calls to self */
+ (double) 1.0 , /* propagation fraction */
+ (double) 0.0 , /* self propagation time */
+ (double) 0.0 , /* child propagation time */
+ (short) 0 , /* print flag */
+ (short) 0 , /* flags */
+ (int) 0 , /* index in the graph list */
+ (int) 0 , /* graph call chain top-sort order */
+ (int) 0 , /* internal number of cycle on */
+ (int) 0 , /* number of live parent arcs */
+ (struct nl *) &indirectchild , /* pointer to head of cycle */
+ (struct nl *) 0 , /* pointer to next member of cycle */
+ (arctype *) 0 , /* list of caller arcs */
+ (arctype *) 0 /* list of callee arcs */
+};
+
+findcall(parentp, p_lowpc, p_highpc)
+ nltype *parentp;
+ unsigned long p_lowpc;
+ unsigned long p_highpc;
+{
+ register u_long pc;
+ nltype *childp;
+ unsigned long destpc;
+ register long op;
+ register int off;
+
+ if (textspace == 0)
+ return;
+ if (p_lowpc < s_lowpc)
+ p_lowpc = s_lowpc;
+ if (p_highpc > s_highpc)
+ p_highpc = s_highpc;
+
+ for (pc = p_lowpc; pc < p_highpc; pc += 4) {
+ off = pc - s_lowpc;
+ op = *(u_long *)&textspace[off];
+ if ((op & 0xc0000000) == 0x40000000) {
+ /*
+ * a pc relative call insn -- check that this
+ * is the address of a function.
+ */
+ off = (op & 0x3fffffff) << 2;
+ destpc = pc + off;
+ if (destpc >= s_lowpc && destpc <= s_highpc) {
+ childp = nllookup(destpc);
+ if (childp != 0 && childp->value == destpc)
+ addarc(parentp, childp, 0L);
+ }
+ } else if ((op & 0xfff80000) == 0x9fc00000)
+ /*
+ * A jmpl with rd = 15 (%o7) -- an indirect call.
+ */
+ addarc(parentp, &indirectchild, 0L);
+ }
+}
diff --git a/usr.bin/gprof/sparc.h b/usr.bin/gprof/sparc.h
new file mode 100644
index 0000000..e2455ea
--- /dev/null
+++ b/usr.bin/gprof/sparc.h
@@ -0,0 +1,48 @@
+/*-
+ * Copyright (c) 1992, 1993
+ * The Regents of the University of California. All rights reserved.
+ *
+ * This software was developed by the Computer Systems Engineering group
+ * at Lawrence Berkeley Laboratory under DARPA contract BG 91-66 and
+ * contributed to Berkeley.
+ *
+ * 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.
+ *
+ * @(#)sparc.h 8.1 (Berkeley) 6/6/93
+ */
+
+/*
+ * offset (in bytes) of the code from the entry address of a routine.
+ * (see asgnsamples for use and explanation.)
+ */
+#define OFFSET_OF_CODE 0
+#define UNITS_TO_CODE (OFFSET_OF_CODE / sizeof(UNIT))
+
+enum opermodes { dummy };
+typedef enum opermodes operandenum;
diff --git a/usr.bin/gprof/tahoe.c b/usr.bin/gprof/tahoe.c
new file mode 100644
index 0000000..ac027f9
--- /dev/null
+++ b/usr.bin/gprof/tahoe.c
@@ -0,0 +1,349 @@
+/*
+ * Copyright (c) 1983, 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.
+ */
+
+#ifndef lint
+static char sccsid[] = "@(#)tahoe.c 8.1 (Berkeley) 6/6/93";
+#endif /* not lint */
+
+#include "gprof.h"
+
+ /*
+ * a namelist entry to be the child of indirect callf
+ */
+nltype indirectchild = {
+ "(*)" , /* the name */
+ (unsigned long) 0 , /* the pc entry point */
+ (unsigned long) 0 , /* entry point aligned to histogram */
+ (double) 0.0 , /* ticks in this routine */
+ (double) 0.0 , /* cumulative ticks in children */
+ (long) 0 , /* how many times called */
+ (long) 0 , /* how many calls to self */
+ (double) 1.0 , /* propagation fraction */
+ (double) 0.0 , /* self propagation time */
+ (double) 0.0 , /* child propagation time */
+ (bool) 0 , /* print flag */
+ (int) 0 , /* index in the graph list */
+ (int) 0 , /* graph call chain top-sort order */
+ (int) 0 , /* internal number of cycle on */
+ (struct nl *) &indirectchild , /* pointer to head of cycle */
+ (struct nl *) 0 , /* pointer to next member of cycle */
+ (arctype *) 0 , /* list of caller arcs */
+ (arctype *) 0 /* list of callee arcs */
+ };
+
+operandenum
+operandmode( modep )
+ unsigned char *modep;
+{
+ long usesreg = ((long)*modep) & 0xf;
+
+ switch ( ((long)*modep) >> 4 ) {
+ case 0:
+ case 1:
+ case 2:
+ case 3:
+ return literal;
+ case 4:
+ return indexed;
+ case 5:
+ return reg;
+ case 6:
+ return regdef;
+ case 7:
+ return autodec;
+ case 8:
+ return ( usesreg != 0xe ? autoinc : immediate );
+ case 9:
+ return ( usesreg != PC ? autoincdef : absolute );
+ case 10:
+ return ( usesreg != PC ? bytedisp : byterel );
+ case 11:
+ return ( usesreg != PC ? bytedispdef : bytereldef );
+ case 12:
+ return ( usesreg != PC ? worddisp : wordrel );
+ case 13:
+ return ( usesreg != PC ? worddispdef : wordreldef );
+ case 14:
+ return ( usesreg != PC ? longdisp : longrel );
+ case 15:
+ return ( usesreg != PC ? longdispdef : longreldef );
+ }
+ /* NOTREACHED */
+}
+
+char *
+operandname( mode )
+ operandenum mode;
+{
+
+ switch ( mode ) {
+ case literal:
+ return "literal";
+ case indexed:
+ return "indexed";
+ case reg:
+ return "register";
+ case regdef:
+ return "register deferred";
+ case autodec:
+ return "autodecrement";
+ case autoinc:
+ return "autoincrement";
+ case autoincdef:
+ return "autoincrement deferred";
+ case bytedisp:
+ return "byte displacement";
+ case bytedispdef:
+ return "byte displacement deferred";
+ case byterel:
+ return "byte relative";
+ case bytereldef:
+ return "byte relative deferred";
+ case worddisp:
+ return "word displacement";
+ case worddispdef:
+ return "word displacement deferred";
+ case wordrel:
+ return "word relative";
+ case wordreldef:
+ return "word relative deferred";
+ case immediate:
+ return "immediate";
+ case absolute:
+ return "absolute";
+ case longdisp:
+ return "long displacement";
+ case longdispdef:
+ return "long displacement deferred";
+ case longrel:
+ return "long relative";
+ case longreldef:
+ return "long relative deferred";
+ }
+ /* NOTREACHED */
+}
+
+long
+operandlength( modep )
+ unsigned char *modep;
+{
+
+ switch ( operandmode( modep ) ) {
+ case literal:
+ case reg:
+ case regdef:
+ case autodec:
+ case autoinc:
+ case autoincdef:
+ return 1;
+ case bytedisp:
+ case bytedispdef:
+ case byterel:
+ case bytereldef:
+ return 2;
+ case worddisp:
+ case worddispdef:
+ case wordrel:
+ case wordreldef:
+ return 3;
+ case immediate:
+ case absolute:
+ case longdisp:
+ case longdispdef:
+ case longrel:
+ case longreldef:
+ return 5;
+ case indexed:
+ return 1+operandlength( modep + 1 );
+ }
+ /* NOTREACHED */
+}
+
+unsigned long
+reladdr( modep )
+ char *modep;
+{
+ operandenum mode = operandmode( modep );
+ char *cp;
+ short *sp;
+ long *lp;
+ int i;
+ long value = 0;
+
+ cp = modep;
+ cp += 1; /* skip over the mode */
+ switch ( mode ) {
+ default:
+ fprintf( stderr , "[reladdr] not relative address\n" );
+ return (unsigned long) modep;
+ case byterel:
+ return (unsigned long) ( cp + sizeof *cp + *cp );
+ case wordrel:
+ for (i = 0; i < sizeof *sp; i++)
+ value = (value << 8) + (cp[i] & 0xff);
+ return (unsigned long) ( cp + sizeof *sp + value );
+ case longrel:
+ for (i = 0; i < sizeof *lp; i++)
+ value = (value << 8) + (cp[i] & 0xff);
+ return (unsigned long) ( cp + sizeof *lp + value );
+ }
+}
+
+findcall( parentp , p_lowpc , p_highpc )
+ nltype *parentp;
+ unsigned long p_lowpc;
+ unsigned long p_highpc;
+{
+ unsigned char *instructp;
+ long length;
+ nltype *childp;
+ operandenum mode;
+ operandenum firstmode;
+ unsigned long destpc;
+
+ if ( textspace == 0 ) {
+ return;
+ }
+ if ( p_lowpc < s_lowpc ) {
+ p_lowpc = s_lowpc;
+ }
+ if ( p_highpc > s_highpc ) {
+ p_highpc = s_highpc;
+ }
+# ifdef DEBUG
+ if ( debug & CALLDEBUG ) {
+ printf( "[findcall] %s: 0x%x to 0x%x\n" ,
+ parentp -> name , p_lowpc , p_highpc );
+ }
+# endif DEBUG
+ for ( instructp = textspace + p_lowpc ;
+ instructp < textspace + p_highpc ;
+ instructp += length ) {
+ length = 1;
+ if ( *instructp == CALLF ) {
+ /*
+ * maybe a callf, better check it out.
+ * skip the count of the number of arguments.
+ */
+# ifdef DEBUG
+ if ( debug & CALLDEBUG ) {
+ printf( "[findcall]\t0x%x:callf" , instructp - textspace );
+ }
+# endif DEBUG
+ firstmode = operandmode( instructp+length );
+ switch ( firstmode ) {
+ case literal:
+ case immediate:
+ break;
+ default:
+ goto botched;
+ }
+ length += operandlength( instructp+length );
+ mode = operandmode( instructp + length );
+# ifdef DEBUG
+ if ( debug & CALLDEBUG ) {
+ printf( "\tfirst operand is %s", operandname( firstmode ) );
+ printf( "\tsecond operand is %s\n" , operandname( mode ) );
+ }
+# endif DEBUG
+ switch ( mode ) {
+ case regdef:
+ case bytedispdef:
+ case worddispdef:
+ case longdispdef:
+ case bytereldef:
+ case wordreldef:
+ case longreldef:
+ /*
+ * indirect call: call through pointer
+ * either *d(r) as a parameter or local
+ * (r) as a return value
+ * *f as a global pointer
+ * [are there others that we miss?,
+ * e.g. arrays of pointers to functions???]
+ */
+ addarc( parentp , &indirectchild , (long) 0 );
+ length += operandlength( instructp + length );
+ continue;
+ case byterel:
+ case wordrel:
+ case longrel:
+ /*
+ * regular pc relative addressing
+ * check that this is the address of
+ * a function.
+ */
+ destpc = reladdr( instructp+length )
+ - (unsigned long) textspace;
+ if ( destpc >= s_lowpc && destpc <= s_highpc ) {
+ childp = nllookup( destpc );
+# ifdef DEBUG
+ if ( debug & CALLDEBUG ) {
+ printf( "[findcall]\tdestpc 0x%x" , destpc );
+ printf( " childp->name %s" , childp -> name );
+ printf( " childp->value 0x%x\n" ,
+ childp -> value );
+ }
+# endif DEBUG
+ if ( childp -> value == destpc ) {
+ /*
+ * a hit
+ */
+ addarc( parentp , childp , (long) 0 );
+ length += operandlength( instructp + length );
+ continue;
+ }
+ goto botched;
+ }
+ /*
+ * else:
+ * it looked like a callf,
+ * but it wasn't to anywhere.
+ */
+ goto botched;
+ default:
+ botched:
+ /*
+ * something funny going on.
+ */
+# ifdef DEBUG
+ if ( debug & CALLDEBUG ) {
+ printf( "[findcall]\tbut it's a botch\n" );
+ }
+# endif DEBUG
+ length = 1;
+ continue;
+ }
+ }
+ }
+}
diff --git a/usr.bin/gprof/tahoe.h b/usr.bin/gprof/tahoe.h
new file mode 100644
index 0000000..7fd0d04
--- /dev/null
+++ b/usr.bin/gprof/tahoe.h
@@ -0,0 +1,59 @@
+/*
+ * Copyright (c) 1983, 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.
+ *
+ * @(#)tahoe.h 8.1 (Berkeley) 6/6/93
+ */
+
+ /*
+ * opcode of the `callf' instruction
+ */
+#define CALLF 0xfe
+
+ /*
+ * offset (in bytes) of the code from the entry address of a routine.
+ * (see asgnsamples for use and explanation.)
+ */
+#define OFFSET_OF_CODE 2
+#define UNITS_TO_CODE (OFFSET_OF_CODE / sizeof(UNIT))
+
+ /*
+ * register for pc relative addressing
+ */
+#define PC 0xf
+
+enum opermodes {
+ literal, indexed, reg, regdef, autodec, autoinc, autoincdef,
+ bytedisp, bytedispdef, worddisp, worddispdef, longdisp, longdispdef,
+ immediate, absolute, byterel, bytereldef, wordrel, wordreldef,
+ longrel, longreldef
+};
+typedef enum opermodes operandenum;
diff --git a/usr.bin/gprof/vax.c b/usr.bin/gprof/vax.c
new file mode 100644
index 0000000..ec3232a
--- /dev/null
+++ b/usr.bin/gprof/vax.c
@@ -0,0 +1,347 @@
+/*
+ * Copyright (c) 1983, 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.
+ */
+
+#ifndef lint
+static char sccsid[] = "@(#)vax.c 8.1 (Berkeley) 6/6/93";
+#endif /* not lint */
+
+#include "gprof.h"
+
+ /*
+ * a namelist entry to be the child of indirect calls
+ */
+nltype indirectchild = {
+ "(*)" , /* the name */
+ (unsigned long) 0 , /* the pc entry point */
+ (unsigned long) 0 , /* entry point aligned to histogram */
+ (double) 0.0 , /* ticks in this routine */
+ (double) 0.0 , /* cumulative ticks in children */
+ (long) 0 , /* how many times called */
+ (long) 0 , /* how many calls to self */
+ (double) 1.0 , /* propagation fraction */
+ (double) 0.0 , /* self propagation time */
+ (double) 0.0 , /* child propagation time */
+ (bool) 0 , /* print flag */
+ (int) 0 , /* index in the graph list */
+ (int) 0 , /* graph call chain top-sort order */
+ (int) 0 , /* internal number of cycle on */
+ (struct nl *) &indirectchild , /* pointer to head of cycle */
+ (struct nl *) 0 , /* pointer to next member of cycle */
+ (arctype *) 0 , /* list of caller arcs */
+ (arctype *) 0 /* list of callee arcs */
+ };
+
+operandenum
+operandmode( modep )
+ struct modebyte *modep;
+{
+ long usesreg = modep -> regfield;
+
+ switch ( modep -> modefield ) {
+ case 0:
+ case 1:
+ case 2:
+ case 3:
+ return literal;
+ case 4:
+ return indexed;
+ case 5:
+ return reg;
+ case 6:
+ return regdef;
+ case 7:
+ return autodec;
+ case 8:
+ return ( usesreg != PC ? autoinc : immediate );
+ case 9:
+ return ( usesreg != PC ? autoincdef : absolute );
+ case 10:
+ return ( usesreg != PC ? bytedisp : byterel );
+ case 11:
+ return ( usesreg != PC ? bytedispdef : bytereldef );
+ case 12:
+ return ( usesreg != PC ? worddisp : wordrel );
+ case 13:
+ return ( usesreg != PC ? worddispdef : wordreldef );
+ case 14:
+ return ( usesreg != PC ? longdisp : longrel );
+ case 15:
+ return ( usesreg != PC ? longdispdef : longreldef );
+ }
+ /* NOTREACHED */
+}
+
+char *
+operandname( mode )
+ operandenum mode;
+{
+
+ switch ( mode ) {
+ case literal:
+ return "literal";
+ case indexed:
+ return "indexed";
+ case reg:
+ return "register";
+ case regdef:
+ return "register deferred";
+ case autodec:
+ return "autodecrement";
+ case autoinc:
+ return "autoincrement";
+ case autoincdef:
+ return "autoincrement deferred";
+ case bytedisp:
+ return "byte displacement";
+ case bytedispdef:
+ return "byte displacement deferred";
+ case byterel:
+ return "byte relative";
+ case bytereldef:
+ return "byte relative deferred";
+ case worddisp:
+ return "word displacement";
+ case worddispdef:
+ return "word displacement deferred";
+ case wordrel:
+ return "word relative";
+ case wordreldef:
+ return "word relative deferred";
+ case immediate:
+ return "immediate";
+ case absolute:
+ return "absolute";
+ case longdisp:
+ return "long displacement";
+ case longdispdef:
+ return "long displacement deferred";
+ case longrel:
+ return "long relative";
+ case longreldef:
+ return "long relative deferred";
+ }
+ /* NOTREACHED */
+}
+
+long
+operandlength( modep )
+ struct modebyte *modep;
+{
+
+ switch ( operandmode( modep ) ) {
+ case literal:
+ case reg:
+ case regdef:
+ case autodec:
+ case autoinc:
+ case autoincdef:
+ return 1;
+ case bytedisp:
+ case bytedispdef:
+ case byterel:
+ case bytereldef:
+ return 2;
+ case worddisp:
+ case worddispdef:
+ case wordrel:
+ case wordreldef:
+ return 3;
+ case immediate:
+ case absolute:
+ case longdisp:
+ case longdispdef:
+ case longrel:
+ case longreldef:
+ return 5;
+ case indexed:
+ return 1+operandlength( (struct modebyte *) ((char *) modep) + 1 );
+ }
+ /* NOTREACHED */
+}
+
+unsigned long
+reladdr( modep )
+ struct modebyte *modep;
+{
+ operandenum mode = operandmode( modep );
+ char *cp;
+ short *sp;
+ long *lp;
+
+ cp = (char *) modep;
+ cp += 1; /* skip over the mode */
+ switch ( mode ) {
+ default:
+ fprintf( stderr , "[reladdr] not relative address\n" );
+ return (unsigned long) modep;
+ case byterel:
+ return (unsigned long) ( cp + sizeof *cp + *cp );
+ case wordrel:
+ sp = (short *) cp;
+ return (unsigned long) ( cp + sizeof *sp + *sp );
+ case longrel:
+ lp = (long *) cp;
+ return (unsigned long) ( cp + sizeof *lp + *lp );
+ }
+}
+
+findcall( parentp , p_lowpc , p_highpc )
+ nltype *parentp;
+ unsigned long p_lowpc;
+ unsigned long p_highpc;
+{
+ unsigned char *instructp;
+ long length;
+ nltype *childp;
+ operandenum mode;
+ operandenum firstmode;
+ unsigned long destpc;
+
+ if ( textspace == 0 ) {
+ return;
+ }
+ if ( p_lowpc < s_lowpc ) {
+ p_lowpc = s_lowpc;
+ }
+ if ( p_highpc > s_highpc ) {
+ p_highpc = s_highpc;
+ }
+# ifdef DEBUG
+ if ( debug & CALLDEBUG ) {
+ printf( "[findcall] %s: 0x%x to 0x%x\n" ,
+ parentp -> name , p_lowpc , p_highpc );
+ }
+# endif DEBUG
+ for ( instructp = textspace + p_lowpc ;
+ instructp < textspace + p_highpc ;
+ instructp += length ) {
+ length = 1;
+ if ( *instructp == CALLS ) {
+ /*
+ * maybe a calls, better check it out.
+ * skip the count of the number of arguments.
+ */
+# ifdef DEBUG
+ if ( debug & CALLDEBUG ) {
+ printf( "[findcall]\t0x%x:calls" , instructp - textspace );
+ }
+# endif DEBUG
+ firstmode = operandmode( (struct modebyte *) (instructp+length) );
+ switch ( firstmode ) {
+ case literal:
+ case immediate:
+ break;
+ default:
+ goto botched;
+ }
+ length += operandlength( (struct modebyte *) (instructp+length) );
+ mode = operandmode( (struct modebyte *) ( instructp + length ) );
+# ifdef DEBUG
+ if ( debug & CALLDEBUG ) {
+ printf( "\tfirst operand is %s", operandname( firstmode ) );
+ printf( "\tsecond operand is %s\n" , operandname( mode ) );
+ }
+# endif DEBUG
+ switch ( mode ) {
+ case regdef:
+ case bytedispdef:
+ case worddispdef:
+ case longdispdef:
+ case bytereldef:
+ case wordreldef:
+ case longreldef:
+ /*
+ * indirect call: call through pointer
+ * either *d(r) as a parameter or local
+ * (r) as a return value
+ * *f as a global pointer
+ * [are there others that we miss?,
+ * e.g. arrays of pointers to functions???]
+ */
+ addarc( parentp , &indirectchild , (long) 0 );
+ length += operandlength(
+ (struct modebyte *) ( instructp + length ) );
+ continue;
+ case byterel:
+ case wordrel:
+ case longrel:
+ /*
+ * regular pc relative addressing
+ * check that this is the address of
+ * a function.
+ */
+ destpc = reladdr( (struct modebyte *) (instructp+length) )
+ - (unsigned long) textspace;
+ if ( destpc >= s_lowpc && destpc <= s_highpc ) {
+ childp = nllookup( destpc );
+# ifdef DEBUG
+ if ( debug & CALLDEBUG ) {
+ printf( "[findcall]\tdestpc 0x%x" , destpc );
+ printf( " childp->name %s" , childp -> name );
+ printf( " childp->value 0x%x\n" ,
+ childp -> value );
+ }
+# endif DEBUG
+ if ( childp -> value == destpc ) {
+ /*
+ * a hit
+ */
+ addarc( parentp , childp , (long) 0 );
+ length += operandlength( (struct modebyte *)
+ ( instructp + length ) );
+ continue;
+ }
+ goto botched;
+ }
+ /*
+ * else:
+ * it looked like a calls,
+ * but it wasn't to anywhere.
+ */
+ goto botched;
+ default:
+ botched:
+ /*
+ * something funny going on.
+ */
+# ifdef DEBUG
+ if ( debug & CALLDEBUG ) {
+ printf( "[findcall]\tbut it's a botch\n" );
+ }
+# endif DEBUG
+ length = 1;
+ continue;
+ }
+ }
+ }
+}
diff --git a/usr.bin/gprof/vax.h b/usr.bin/gprof/vax.h
new file mode 100644
index 0000000..b5fbf35
--- /dev/null
+++ b/usr.bin/gprof/vax.h
@@ -0,0 +1,65 @@
+/*
+ * Copyright (c) 1983, 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.
+ *
+ * @(#)vax.h 8.1 (Berkeley) 6/6/93
+ */
+
+ /*
+ * opcode of the `calls' instruction
+ */
+#define CALLS 0xfb
+
+ /*
+ * offset (in bytes) of the code from the entry address of a routine.
+ * (see asgnsamples for use and explanation.)
+ */
+#define OFFSET_OF_CODE 2
+#define UNITS_TO_CODE (OFFSET_OF_CODE / sizeof(UNIT))
+
+ /*
+ * register for pc relative addressing
+ */
+#define PC 0xf
+
+enum opermodes {
+ literal, indexed, reg, regdef, autodec, autoinc, autoincdef,
+ bytedisp, bytedispdef, worddisp, worddispdef, longdisp, longdispdef,
+ immediate, absolute, byterel, bytereldef, wordrel, wordreldef,
+ longrel, longreldef
+};
+typedef enum opermodes operandenum;
+
+struct modebyte {
+ unsigned int regfield:4;
+ unsigned int modefield:4;
+};
+
OpenPOWER on IntegriCloud