diff options
| author | rgrimes <rgrimes@FreeBSD.org> | 1994-05-27 12:33:43 +0000 |
|---|---|---|
| committer | rgrimes <rgrimes@FreeBSD.org> | 1994-05-27 12:33:43 +0000 |
| commit | f9ab90d9d6d02989a075d0f0074496d5b1045e4b (patch) | |
| tree | add7e996bac5289cdc55e6935750c352505560a9 /usr.bin/gprof | |
| parent | be22b15ae2ff8d7fe06b6e14fddf0c5b444a95da (diff) | |
| download | FreeBSD-src-f9ab90d9d6d02989a075d0f0074496d5b1045e4b.zip FreeBSD-src-f9ab90d9d6d02989a075d0f0074496d5b1045e4b.tar.gz | |
BSD 4.4 Lite Usr.bin Sources
Diffstat (limited to 'usr.bin/gprof')
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; +}; + |
