Efficient On-the-fly Analysis of Program Behavior and Static Cache Simulation

. The main contributions of this paper are twofold. First, a general framework for control-flow partitioning is presented for efficient on-the-fly analysis, i.e. for program behavior analysis during execution using a small number of instrumentation points. The formal model is further refined for certain analyses by transforming a program's call graph into a function-instance graph. Performance evaluations show that the number of measurement points can be reduced by one third using these methods. Second, the method of static cache simulation is introduced. Static cache simulation provides the means to predict a large number of cache references prior to the execution time of a program. The method is based on a variation of an iterative data-flow algorithm commonly used in optimizing compilers. It utilizes control-flow partitioning and function-instance graphs for predicting the caching behavior of each instruction. To our knowledge, no prior work has been done on predicting caching behav..