@INPROCEEDINGS{Grund09,
  author = {Daniel Grund and Jan Reineke},
  title = {Abstract Interpretation of {FIFO} Replacement},
  booktitle = {Static Analysis, 16th International Symposium, SAS 2009},
  year = {2009},
  editor = {Jens Palsberg and Zhendong Su},
  volume = {5673},
  series = {LNCS},
  pages = {120--136},
  month = {August},
  publisher = {Springer-Verlag},
  subproject={R2},
  access={restricted},
  bibtex={grund.sas09.bib},
  pdf={grund.sas09.pdf},
  abstract={In hard real-time systems, the execution time of programs
must be bounded by static timing analysis. For today's embedded systems
featuring caches, static analyses must predict cache hits and misses
with high precision to obtain useful bounds. For caches with least-recentlyused
(LRU) replacement policy, editorcient and precise cache analyses exist.
However, for other widely-used policies like rst-in rst-out (FIFO),
current cache analyses are much less precise.
This paper discusses challenges in FIFO cache analysis and advances the
state of the art. We identify a generic framework for cache analysis that
couples may- and must-analyses by means of domain cooperation. Our
main contribution is a more precise may-analysis for FIFO. It not only
increases the number of predicted misses, but also|due to the domain
cooperation|the number of predicted hits.We instantiate the framework
with a canonical must-analysis and three dirent may-analyses, including
our new one, and compare the resulting three analyses to the collecting
semantics. Our evaluation results characterize the progress achieved
by our new may-analysis and reveal room for further improvement.},
}