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 accomplished 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 to be in the
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 miss depending on the flow
of control, then it is referred to as a conflict.
The categorization of instruction references will be discussed briefly. A more formal description and the corresponding algorithms can be found elsewhere [, ]. An abstract cache state of a basic block in the control-flow graph denotes the subset of program lines which can potentially be cached before executing the block, i.e. there exists an execution path for each program line of the subset such that the program line is cached at the beginning of the block.
A program line reference results in an always-miss if the program line is not in the abstract cache state. An always hit occurs if the line is in the abstract cache state and no other program line mapping into the same cache line is in the abstract cache state. A first miss occurs if the line is in the abstract cache state, and all other lines in the abstract cache state (mapping into the same cache line) cannot be reached anymore through the control flow. The remaining instructions are classified as conflicts.
The calculation of the abstract cache states is performed by an iterative algorithm similar to the data-flow analysis performed in optimizing compilers. The categorization amounts to a traversal of the program lines, i.e. a traversal of the program lines for each basic block within the combination of the call graph and the control-flow graphs of each function.
Based on the category of a program line, the static simulator emits instruction annotations, placed at the beginning of basic blocks, which provide frequency counts and simulate the ``conflicts'' using simple state transitions at execution time. The additional code affects the run time of the program but not the calculation of the elapsed time since the latter is based on the cache simulation performed on the original, uninstrumented program.
Figure 2: Annotated Sample Debugging Session