Interdependent Cache Analyses for better precision and safety
Kartik Nagar, Y N Srikant
Abstract: One of the challenges for accurately estimating Worst Case Execu-
tion Time(WCET) of executables is to accurately predict their cache
behaviour. 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 de-
termines 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 up-
date 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.
pdf