New Technical Report: "Optimally Profiling and Tracing Programs"

****
A postscript version of this technical report is available for anonymous
ftp from primost.cs.wisc.edu in pub/opt-prof-trace.ps.Z
****


Optimally Profiling and Tracing Programs


Thomas Ball James R. Larus


Computer Sciences Department
University of Wisconsin--Madison
1210 W. Dayton St.
Madison, WI 53706 USA


Technical Report #1031


This paper presents two algorithms for inserting monitoring code to
profile and trace programs. These algorithms greatly reduce the cost of
measuring programs. Profiling, which counts the number of times each
basic block in a program executes, is widely used to measure instruction
set utilization of computers, identify program bottlenecks, and estimate
program execution times for code optimization. Instruction traces are the
basis for trace-driven simulation and analysis and are used also in
trace-driven debugging.


The profiling algorithm instruments a program for profiling by choosing a
placement of counters that is optimized--and frequently optimal--with
respect to the expected or measured execution frequency of each basic
block and branch in the program. The tracing algorithm instruments a
program to obtain a subsequence of the basic block trace--whose length is
optimized with respect to the program's execution--from which the entire
trace can be efficiently regenerated.


Both algorithms have been implemented and produce a substantial
improvement over previous approaches, as the performance figures in this
paper show. The profiling algorithm reduces the number of counters by a
factor of two and the number of counter increments by a factor of three.
The tracing algorithm reduces the file size and overhead of an already
highly optimized tracing system by 20-40%.


[An abridged version of this paper will appear in the 19th Symposium on
Principles of Programming Languages (January 19-22, 1992).]
--

Return to the comp.compilers page.
Search the comp.compilers archives again.