Program analysis through profiling and tracing has long been used to evaluate new hardware and software designs. The traditional approach relies on generating a program trace during execution that is analyzed later by a tool. The problem of generating a minimal trace, which can later be expanded to a full event-ordered trace, can be regarded as solved []. A near-optimal (often even optimal) solution to the problem for a control-flow graph G can be found by determining a maximum spanning tree max(G) for the control-flow graph and inserting code on the edges of G-max(G).
Recently, tracing and analyzing of programs has been combined using on-the-fly analysis []. This analysis technique requires that events are analyzed as they occur but does not require the storage of trace data. The analysis is performed during program execution and is specialized for a certain application (e.g. counting hits and misses for cache evaluation). The results of the analysis are available at program termination such that no post-execution analysis by any tool is required. If the application or the configuration changes, the program has to be executed again. In contrast, trace data can be analyzed by several tools and for several configurations once the data is generated. But the generation of trace data is typically slow and space consuming since the data is written to a file and later read again by a tool.
On-the-fly analysis requires that the program be instrumented with code that performs the analysis. Many applications, including cache simulation, require that all events are simulated in the order in which they occur. In the past, each basic block was instrumented with code to support event-ordered analysis []. Inserting code based on the maximum spanning tree (or, to be more precise, on its complement) does not cover all events and is therefore not applicable to on-the-fly analysis. This paper provides the framework to reduce code instrumentation to a small number of places. This framework supports efficient on-the-fly analysis of programs with regard to path partitioning. The execution overhead can be further reduced by analyzing instances of functions. The construction of a function-instance graph from a program's call graph is presented in this paper.
One application for program analysis is cache evaluation. Different cache configurations can be evaluated by determining the number of cache hits and misses for a set of programs. Cache analysis can be performed on-the-fly or by analyzing stored trace data, though faster results have been reported for the former approach []. This paper introduces the method of static cache simulation which predicts the caching behavior of a large number of references prior to execution time. The method employs a novel view of cache memories, which is, to our knowledge, unprecedented. The method is based on a variation of an iterative data-flow algorithm commonly used in optimizing compilers. It can be used to reduce the amount of instrumentation code inserted into a program for on-the-fly analysis. It can also be used to enable a program timing tool to take the effects of caching into account. A more comprehensive overview of static cache simulation including further applications can be found elsewhere [].