We are currently working on applying Static Cache Simulation to data caches under certain restrictions, such as the absence of pointers and dynamic memory allocation. Most other data references could be predicted statically. Previous work has shown improvements by balancing the number of instructions placed behind loads where the memory latency was uncertain []. By predicting the memory latency of a large portion of loads, instruction scheduling could be performed more effectively. For example, the number of instructions the scheduler would place between a load instruction and the first instruction referencing the loaded register should be greater for a data reference classified as an always miss than an always hit.
We are currently working on integrating the method of Static Cache Simulation with a tool which estimates a program's best-case execution time (BET) and worst-case execution time (WET) [, ]. Using the information provided by Static Cache Simulation, the BET and WET can be based on the categorization of instructions. This relieves the time-estimation tool from having to simulate all possible cache states. The instruction categorization is refined to provide a separate category for each loop level, thereby providing the base for tight execution time predictions.
With the bit-encoding approach, a traditional tool predicting the execution time can perform the same type of analysis and provide estimations for both BET and WET. But the execution time predictions can be tighter since the caching behavior is fully predictable. Instructions classified as always-hits can be assumed to require one cycle, and always-misses or conflicts can be estimated to take n+1 cycles. For a first-miss, the tool could distinguish between the first reference (n+1 cycles) and any subsequent references (one cycle) by simply tagging first-miss instructions which have been encountered. A traditional timing tool should be easily modified to take the effect of bit-encoding into account. The resulting execution time estimate will be as tight as for uncached systems since the estimation of the fetch cost accurately represents the number of cycles taken for an instruction in any category. There is no uncertainty with respect to the effect of an instruction classified as conflict, the fetch will always take n+1 cycles.
The static simulator could be extended in several ways. First, recursive functions could be handled by applying the described algorithm to calculate abstract cache states repeatedly on a function instance. Second, a modified algorithm and data structure could be designed to handle set-associative caches.
There are several other applications of Static Cache Simulation. For example, instruction cache analysis can be sped up by determining the caching behavior of a large number of references prior to execution time []. Other applications include detailed profiling and tracking of execution time for a real-time debugger [].