# Leveraging LLVM's ScalarEvolution for Symbolic Data Cache Analysis

arXiv: https://arxiv.org/abs/2310.04809 · HTML: https://mlsanity.com/paper/2310.04809/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 7 Oct 2023.

## Built on by (most cited first, 1 of 1)

- [PrETi: Predicting Execution Time in Early Stage with LLVM and Machine Learning](https://mlsanity.com/paper/2503.13679/) (2025)

## Abstract (arXiv)

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.