Cache Behavior Analysis with SP-Relative Addressing for WCET Estimation
摘要
Accurately bounding the worst-case execution time (WCET) is crucial for efficient real-time system design. Precisely analyzing whether a memory reference results in a cache miss or a cache hit significantly impacts the accuracy of the estimated WCET bound, as the latency of a cache miss is typically two orders of magnitude higher than that of a cache hit access. SP-relative addressing enables dynamic memory allocation on the stack, enhances thread safety, an therefore is widely adopted in embedded real-time systems. However, existing cache behavior analysis requires obtaining the exact address of each memory reference and pessimistically assumes that SP-relative addressing could access any memory address, resulting in an overestimated WCET bound. In this paper, we propose a new WCET analysis framework that first identifies the program segments in which the SP value remains constant for a accurate cache behavior analysis, and then comprehensively compute the WCET of the whole program based on the constraints between the SP value defined by the program’s control flow. Experimental results show that, our method can tighten the estimated WCET bound by up to 36.31% and achieve an average improvement of 11.85%.