Static cache simulation calculates the abstract cache states
associated with UPs. The calculation is performed by repeated
traversal of the function-instance graph and the UPPA of each
function.
The notion of an abstract cache state is a compromise between a
feasible storage complexity of the static cache simulation and the
alternative of an exhaustive set of all cache states that may occur
at execution time with an exponential storage complexity.
Based on the abstract cache state, it becomes possible to statically predict the caching behavior of each instruction of a program. Instructions may be categorized as always-hit, always-miss, first-miss, or conflict. The semantics for each category is as follows. Always-hit (always-miss) instructions will always result in a cache hit (miss) during program execution. First-miss instructions will result in a cache miss on the first reference to the instruction and in a cache hit for any consecutive references. Conflict instructions may result in a cache hit or a cache miss during program execution, i.e. their behavior cannot be predicted statically through this simulation method. The different categories are defined below after introducing the notion of a reaching state.
An always miss occurs when instruction 
is the first instruction
encountered in program line l and l is not in the abstract cache
state s. An always hit occurs either if is not the first
instruction in l or l is the only program line in s mapping into
c. A first miss occurs if the following conditions are met. First,
is first in l and if l and at least one other program line
m (which maps into c) are in s. Second, if one such line m is
in s, then the line must not be reachable anymore from the current
UP. Third, all other instructions in the program line have to be
either always hits or first misses. A conflict occurs in all other
cases.
This categorization results in some interesting properties. If the
size of the program does not exceed the size of the cache, hardly any
instructions will be categorized as conflicts. Thus, the cache
behavior can mostly be statically predicted.
As the program becomes much larger
than the cache, the number of conflicts increases to a certain point.
This point depends on the ratio between program size and cache size.
After this point, conflicts start to decrease again while first misses
increase.
