Static Cache Simulation calculates the abstract cache states
associated with basic blocks. The calculation is performed by repeated
traversal of the call graph's functions, their function instances, and
the basic blocks of each function's control-flow graph.
The notion of an abstract cache state is a compromise between a
feasible storage complexity of the proposed method and the alternative
of an exhaustive set of all cache states which may occur at execution
time with an exponential storage complexity.
For a given function instance, each instruction i within a basic
block b is categorized based on its position in the corresponding
program line 
, on the corresponding abstract cache
state s, and on the reaching state t. The program line l maps
into cache line c, denoted by 
.
:
instruction i is the first reference to program line l in
b and
:
l is not in the abstract cache state.
:
instruction i is not the first reference to program line l in b.
Or
:
instruction i is the first reference to program line l in b,
:
l is in the abstract cache state, and
:
no other line m (which maps into the same cache line as l) is
in the abstract cache state.
:
instruction i is the first reference to program line l in b,
:
l is in the abstract cache state,
: another line m
(which maps into the same cache line as l) is also in the abstract
cache state,
:
all other program lines m (which maps into the same cache line as l)
cannot be reached anymore if they are in the abstract cache state, and
:
all other instructions of program line l are either always hits or
first misses.
The categorization can be used to statically infer non-trivial caching behavior as will be shown in the next subsection.