论文标题
如果添加了过程调用，请访问静态分析中的复杂性差距会增长
The complexity gap in the static analysis of cache accesses grows if procedure calls are added
论文作者
论文摘要
缓存访问的静态分析包括正确预测哪些访问是命中或错过。尽管对实施最近使用的最少使用（LRU）替换策略的缓存进行了良好的精确分析，但对于其他替代政策而言，此类分析很难找到。发现了一个理论上的解释：对于对控制流图的适当分析，缓存分析对于所有常见的替换策略（FIFO，PLRU，NMRU）都是PSPACE分析，除了LRU，它仅是NP完整的。在本文中，我们表明，如果将过程调用添加到控制流中，则差距扩大：分析对于LRU来说仍然是NP的固定，但是对于其他三个策略来说，分析已成为Exptime-Complete。为此，我们改善了较早的结果，即通过程序调用在布尔计划上的可及性问题的复杂性。此外，对于LRU策略，我们得出了回溯算法，以及在其他分析未能得出结论之后，将其用作最后手段的方法。
The static analysis of cache accesses consists in correctly predicting which accesses are hits or misses. While there exist good exact and approximate analyses for caches implementing the least recently used (LRU) replacement policy, such analyses were harder to find for other replacement policies. A theoretical explanation was found: for an appropriate setting of analysis over control-flow graphs, cache analysis is PSPACE-complete for all common replacement policies (FIFO, PLRU, NMRU) except for LRU, for which it is only NP-complete. In this paper, we show that if procedure calls are added to the control flow, then the gap widens: analysis remains NP-complete for LRU, but becomes EXPTIME-complete for the three other policies. For this, we improve on earlier results on the complexity of reachability problems on Boolean programs with procedure calls. In addition, for the LRU policy we derive a backtracking algorithm as well as an approach for using it as a last resort after other analyses have failed to conclude.
