  Cache persistence analysis is an important part of worst-case execution time
(WCET) analysis. It has been extensively studied in the past twenty years.
Despite these efforts, all existing persistence analyses are approximative in
the sense that they are not guaranteed to find all persistent memory blocks.
  In this paper, we close this gap by introducing the first exact persistence
analysis for caches with least-recently-used (LRU) replacement. To this end, we
first introduce an exact abstraction that exploits monotonicity properties of
LRU to significantly reduce the information the analysis needs to maintain for
exact persistence classifications. We show how to efficiently implement this
abstraction using zero-suppressed binary decision diagrams (ZDDs) and introduce
novel techniques to deal with uncertainty that arises during the analysis of
data caches.
  The experimental evaluation demonstrates that the new exact analysis is
competitive with state-of-the-art inexact analyses in terms of both memory
consumption and analysis run time, which is somewhat surprising as we show that
persistence analysis is NP-complete. We also observe that while prior analyses
are not exact in theory they come close to being exact in practice.
