Editing Cache replacement policies (section)

==Static analysis==
[[Static analysis]] determines which accesses are cache hits or misses to indicate the [[worst-case execution time]] of a program.<ref>{{cite journal|author1=Christian Ferdinand|author2=Reinhard Wilhelm|year=1999|title=Efficient and precise cache behavior prediction for real-time systems|journal=Real-Time Syst.|volume=17|number=2–3|pages=131–181|doi=10.1023/A:1008186323068|bibcode=1999RTSys..17..131F |s2cid=28282721 }}</ref> An approach to analyzing properties of LRU caches is to give each block in the cache an "age" (0 for the most recently used) and compute intervals for possible ages.<ref>{{cite journal|title=Cache Behavior Prediction by Abstract Interpretation|journal=Science of Computer Programming|publisher=Springer|doi=10.1016/S0167-6423(99)00010-6|author1=Christian Ferdinand|author2=Florian Martin|author3=Reinhard Wilhelm|author4=Martin Alt|date=November 1999|volume=35|number=2–3|pages=163–189 }}</ref> This analysis can be refined to distinguish cases where the same program point is accessible by paths that result in misses or hits.<ref>{{cite conference|author1=Valentin Touzeau|author2=Claire Maïza|author3=David Monniaux|author4=Jan Reineke|title=Ascertaining Uncertainty for Efficient Exact Cache Analysis |book-title=Computer-aided verification (2)|date=2017|doi=10.1007/978-3-319-63390-9_2|arxiv=1709.10008}}</ref> An efficient analysis may be obtained by abstracting sets of cache states by [[antichain]]s which are represented by compact [[binary decision diagram]]s.<ref>{{cite journal|author1=Valentin Touzeau|author2=Claire Maïza|author3=David Monniaux|author4=Jan Reineke|title=Fast and exact analysis for LRU caches|journal=Proc. {ACM} Program. Lang|volume=3|number=POPL|pages=54:1–54:29|date=2019|arxiv=1811.01670 }}</ref>

LRU static analysis does not extend to pseudo-LRU policies. According to [[computational complexity theory]], static-analysis problems posed by pseudo-LRU and FIFO are in higher [[complexity class]]es than those for LRU.<ref>{{cite journal|title=On the complexity of cache analysis for different replacement policies|journal=Journal of the ACM|publisher=Association for Computing Machinery|date=2019-11-11|author1=David Monniaux|author2=Valentin Touzeau|volume=66|number=6|pages=1–22 |doi=10.1145/3366018|s2cid=53219937 |url=https://hal.archives-ouvertes.fr/hal-01910216v3/}}</ref><ref>{{cite journal|author=David Monniaux|title=The complexity gap in the static analysis of cache accesses grows if procedure calls are added|journal=Formal Methods in System Design|publisher=Springer Verlag|date=2022-05-13|volume=59 |issue=1–3 |pages=1–20 |doi=10.1007/s10703-022-00392-w|arxiv=2201.13056 |s2cid=246430884 |url=https://hal.archives-ouvertes.fr/hal-03545774/}}</ref>