optimally profiling and tracing programs
This paper presents algorithms for inserting monitoring code to profile and trace programs. These algorithms greatly reduce the cost of measuring programs. Profiling counts the number of times each basic block in a program executes and has a variety of applications. Instruction traces are the basis for trace-driven simulation and analysis, and are also used in trace-driven debugging. The profiling algorithm chooses a placement of counters that is optimizedand frequently optimalwith 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 tracewhose length is optimized with respect to the program's executionfrom which the entire trace can be efficiently regenerated. Both algorithms have been implemented and produce a substantial improvement over previous approaches. The profiling algorithm reduces the number of counters by a factor of two and the number of counter increments by up to a factor of four. The tracing algorithm reduces the file size and overhead of an already highly optimized tracing system by 20-40\%.
optimality profiling traces program paper algorithm monitor code cost measurement blocking instruction instruction tracing placement instrumentation efficiency place tool general hierarchies control-flow graph practical informal sequence records