OPTIMALLY PROFILING AND TRACING PROGRAMS

This paper describes algorithms for inserting monitoring code to profi le and trace programs. These algorithms greatly reduce the cost of mea suring programs with respect to the commonly used technique of placing code in each basic block. Program profiling counts the number of time s each basic block in a program executes. Instruction tracing records the sequence of basic blocks traversed in a program execution. The alg orithms optimize the placement of counting/tracing code with respect t o the expected or measured frequency of each block or edge in a progra m's control-flow graph. We have implemented the algorithms in a profil ing/tracing tool, and they substantially reduce the overhead of profil ing and tracing. We also define and study the hierarchy of profiling p roblems. These problems have two dimensions: what is profiled (i.e., v ertices (basic blocks) or edges in a control-flow graph) and where the instrumentation code is placed (in blocks or along edges). We compare the optimal solutions to the profiling problems and describe a new pr ofiling problem: basic-block profiling with edge counters. This proble m is important because an optimal solution to any other profiling prob lem (for a given control-flow graph) is never better than an optimal s olution to this problem. Unfortunately, finding an optimal placement o f edge counters for vertex profiling appears to be a hard problem in g eneral. However, our work shows that edge profiling with edge counters works well in practice because it is simple and efficient and finds o ptimal counter placements in most cases. Furthermore, it yields more i nformation than a vertex profile. Tracing also benefits from placing i nstrumentation code along edges rather than on vertices.