The iterative Algorithm 2 calculates the abstract cache states. In the algorithm, the abstract cache state of the program line of a UP that is referenced first is referred to as input_state. Conversely, the abstract cache state after the program line of a UP that is referenced last is referred to as output_state. The set of vertices (basic blocks) in a UP provides the scope of program lines to transform an input_state into an output_state.
The algorithm is a variation of an iterative data-flow analysis
algorithm commonly used in optimizing compilers. Thus, the time
overhead of the algorithm is comparable to that of data-flow analysis
and the space overhead is O(pl*UPs*fi), where pl is the number of
program lines, UPs is the number of paths, and fi the number of
function instances. The correctness of the algorithm for data-flow
analysis is discussed in []. The calculation can be performed
for an arbitrary control-flow graph, even if it is irreducible. In
addition, the order of processing basic blocks is irrelevant for the
correctness of the algorithm. The reaching states can be calculated
using the same base algorithm with input_state(main) =
conf_lines(UP) = 
.
The current implementation of the static simulator imposes the restriction that only direct-mapped cache configurations are allowed. Recent results show that direct-mapped caches have a faster access time for hits, which outweighs the benefit of a higher hit ratio in set-associative caches for large cache sizes [].
