For each path of each function instance, the product of a frequency count and the number of always hits (misses) is added to the total number of hits (misses). First misses, weighted by the frequency, are also added to the total number of hits at this point.
The index into the counter array indicates the number of hits and misses for conflicting lines, which are then also multiplied by the corresponding frequency. A zero index indicates that all conflicting lines are cached while the last index corresponds to misses of all conflicting lines (see SPS bit encoding in Figure 4).
Not all cache line configurations may be valid during the execution of the program for a given path and instance. In other words, the frequency count for some indices should be zero. But to minimize the amount of state changes during run time, a conflicting SPS is not updated if it can be determined at simulation time that the corresponding cache state cannot occur. Therefore, only a subset of counter indices may actually correspond to a valid cache configuration for a given path and instance. The number of conflicting lines is thus inferred from the array index combined with an AND mask with bits set in the position of valid cache lines. Consider path 1 in Figure 4. The AND mask for this path is 0x2 since only bit 2 (corresponding to program line a in the encoding of the SPS) is referenced when executing path 1.
If the number of states in the SPS was large and the alternate counting method was applied, then the always hits (misses) and first misses are still counted based on the frequency counter. The number of misses due to conflicts is readily available in one counter. The number of hits can be calculated as the total frequency times the number of conflict lines less the number of misses due to conflicts.
Table 1: Measurements for 1kB Direct-Mapped Cache