The method of Static Cache Simulation can be used to statically predict the behavior of a large number of the instruction cache references for a given program/task with a specific cache configuration. Unlike many data references, the address of each instruction is known statically. This is certainly true for code which is physically locked into memory. It also holds for virtual memory mapping if and only if the page size is an integer multiple of the instruction cache size, which is typical for many systems []. In this case, the relocation of a virtual page would not affect the mapping of program lines into cache lines.
Figure 1 depicts an overview of the tools and interfaces involved in instruction cache analysis using Static Cache Simulation.
Figure 1: Overview of Static Cache Simulation
The set of source files of a program are translated by a compiler. The compiler generates object code and passes information about the control flow of each source file to the static cache simulator. The static cache simulator performs the task of determining which instruction references can be predicted prior to execution time. It constructs the call graph of the program and the control-flow graph of each function based on the information provided by the compiler. The cache behavior is then simulated for a given cache configuration. Furthermore, the static simulator produces instruction annotations and passes them to the linker which modifies the object code according to the annotations and creates an executable program.
The task of Static Cache Simulation is to determine whether each instruction reference will result in a cache hit or miss during program execution. This is done by analyzing the call graph and the control flow for each function. Since it is not always possible to determine if a reference is a hit or miss, instructions are classified into categories of always-hit, always-miss, first-miss, or conflict. If an instruction is always (never) in cache, then it is denoted as an always-hit (always-miss). If an access to an instruction results in a miss on the first access and in hits for any subsequent accesses, then it is classified as a first-miss. If an access to a program line results in either a hit or a misses depending on the flow of control, then it is referred to as a conflict.
The following subsections describe this process in more detail. A formal approach to Static Cache Simulation can be found elsewhere [].