Interdependent Cache Analyses for better precision and safety


One of the challenges for accurately estimating Worst Case Execution Time(WCET) of executables is to accurately predict their cache behavior. Various techniques have been developed to predict the cache contents at different program points to estimate the execution time of memory-accessing instructions. One of the most widely used techniques is Abstract Interpretation based Must Analysis, which determines the cache blocks guaranteed to be present in the cache, and hence provides safe estimation of cache hits and misses. However, Must Analysis is highly imprecise, and platforms using Must Analysis have been known to produce blown-up WCET estimates. In our work, we propose to use May Analysis to assist the Must Analysis cache update and make it more precise. We prove the safety of our approach as well as provide examples where our Improved Must Analysis provides better precision. Further, we also detect a serious flaw in the original Persistence Analysis, and use Must and May Analysis to assist the Persistence Analysis cache update, to make it safe and more precise than the known solutions to the problem. Finally, we propose an improvement in the original May Analysis, to make it more precise, especially for Data Cache Analysis.

ACM-IEEE International Conference on Formal Methods and Models for System Design