For each UP of every function instance, an array of frequency counters is used to keep track of the execution frequency of the UP. The size of the array is determined by the number of permutations of conflicting lines for a SPS. Since the size is growing exponentially with the number of conflicting lines, an alternate counter array with a constant size of two entries is provided for large numbers of conflicting lines in the SPS. There is a time/space trade-off between the two alternatives (discussed in the context of the path macros).
Figure 4 shows the frequency counter, indexed by the SPS of path 1 and 2, which is incremented. Path 2 has an array of four frequency counters, corresponding to each possible value of the SPS. An increment of the first counter element corresponds to hits on line a and b, an increment of the second counter element indicates a hit on a and a miss on b, etc. The frequency counter increments for paths 3 and 4 are not shown.