  While instruction cache analysis is essentially a solved problem, data cache
analysis is more challenging. In contrast to instruction fetches, the data
accesses generated by a memory instruction may vary with the program's inputs
and across dynamic occurrences of the same instruction in loops.
  We observe that the plain control-flow graph (CFG) abstraction employed in
classical cache analyses is inadequate to capture the dynamic behavior of
memory instructions. On top of plain CFGs, accurate analysis of the underlying
program's cache behavior is impossible.
  Thus, our first contribution is the definition of a more expressive program
abstraction coined symbolic control-flow graphs, which can be obtained from
LLVM's ScalarEvolution analysis. To exploit this richer abstraction, our main
contribution is the development of symbolic data cache analysis, a smooth
generalization of classical LRU must analysis from plain to symbolic
control-flow graphs.
  The experimental evaluation demonstrates that symbolic data cache analysis
consistently outperforms classical LRU must analysis both in terms of accuracy
and analysis runtime.
