Instruction Categorization

Static cache simulation calculates the abstract cache states associated with the UPs. Such an abstract cache state specifies the possible cache contents before the UP is executed. First, formal definitions are provided. Then, the caching behavior of each instruction is categorized based on these definitions. An example is discussed in section 4.3 (see [] for more details).



The notion of an abstract cache state is a compromise between the choice of an exhaustive set of all cache states that may occur at execution time and the exponential growth of such an exhaustive set during simulation. The next definition introduces the reaching state, which is used for the categorization of instructions following thereafter.

For a given function instance, each instruction i within a UP is categorized based on its position in the corresponding program line , on the corresponding abstract cache state s, and on the reaching state r. The program line l maps into cache line c, denoted by . The UP containing line l is referred to simply as UP.

always-miss: A cache miss is predicted if

• : instruction i is the first reference to program line l in UP and

• : l is not in the abstract cache state.

always-hit: A cache hit is predicted if

• : instruction i is a consecutive reference to program line l in UP. Or all of the following conditions hold:

• : instruction i is the first reference to program line l in UP,

• : l is in the abstract cache state, and

• :
  no other line k (which maps into the same cache line as l) is in the abstract cache state.

first-miss: The first reference to an instruction will result in a cache miss and all subsequent references in cache hits if

• : instruction i is the first reference to program line l in UP,

• : l is in the abstract cache state,

• :
  another line k (which maps into the same cache line as l) is also in the abstract cache state,

• :
  if any line k (which maps into the same cache line as l) is also in the abstract cache state, then the line is not in the reaching state of UP, and

• -hit, first-:
  all other instructions within the same program line are always-hits or first-misses.

conflict: All other instructions are conflicts.