Automatic safe data reuse detection for the WCET analysis of systems with data caches

Worst-case execution time (WCET) analysis of systems with data caches is one of the key challenges in real-time systems. Caches exploit the inherent reuse properties of programs, temporarily storing certain memory contents near the processor, in order that further accesses to such contents do not require costly memory transfers. Current worst-case data cache analysis methods focus on specific cache organizations (LRU, locked, ACDC, etc.). In this article, we analyze data reuse (in the worst case) as a property of the program, and thus independent of the data cache. Our analysis method uses Abstract Interpretation on the compiled program to extract, for each static load/store instruction, a linear expression for the address pattern of its data accesses, according to the Loop Nest Data Reuse Theory. Each data access expression is compared to that of prior (dominant) memory instructions to verify whether it presents a guaranteed reuse. Our proposal manages references to scalars, arrays, and non-linear accesses, provides both temporal and spatial reuse information, and does not require the exploration of explicit data access sequences. As a proof of concept we analyze the TACLeBench benchmark suite, showing that most loads/stores present data reuse, and how compiler optimizations affect it. Using a simple hit/miss estimation on our reuse results, the time devoted to data accesses in the worst case is reduced to 27% compared to an always-miss system, equivalent to a data hit ratio of 81%. With compiler optimization, such time is reduced to 6.5%.This work was supported in part by MINECO/AEI/ERDF (EU) under Grant TIN2016-76635-C2-1-R, Grant TIN2017-86727-C2-1-R, and Grant PID2019-105660RB-C21; in part by the Aragón Government under Grant T58_20R research group; in part by the Generalitat de Catalunya under Grant 2017 SGR 786 and Grant FI-DGR 2015; and in part by the Construyendo Europa desde Aragón under Grant ERDF 2014-2020.Peer ReviewedPostprint (published version