In this paper, a formal method is developed to perform efficient on-the-fly analysis of program behavior with regard to path partitioning. The method partitions the control-flow graph into a small set of unique paths, each of which contain a unique edge or vertex where instrumentation code can be placed. Furthermore, the construction of the function-instance graph from a program's call graph refines the analysis. Performance evaluations show that the number of measurement points can be reduced by one third using these methods. Taking advantage of path partitionings and the function-instance graph, the method of static cache simulation is introduced which allows the prediction of a large number of cache references prior to program execution. A number of applications for this method are discussed, ranging from faster instruction cache analysis to the analytical bounding of execution time by static analysis for real-time tasks.