Fast and Precise WCET Prediction by Separated Cache and Path Analyses

Abstract. Precise run-time prediction suffers from a complexity problem when doing an integrated analysis. This problem is characterised by the conflict between an optimal solution and the complexity of the computation of the solution. The analysis of modern hardware consists of two parts: a) the analysis of the microarchitecture’s behaviour (caches, pipelines) and b) the search for the longest program path. Because an integrated analysis has a significant computational complexity, we chose to separate these two steps. By this, an ordering problem arises, because the steps depend on each other. In this paper we show how the microarchitecture analysis can be separated from the path analysis in order to make the overall analysis fast. Practical experiments will show that this separation, however, does not make the analysis more pessimistic than existing approaches. Furthermore, we show that the approach can be used to analyse executables created by a standard optimising compiler. Keywords: Run-time analysis, hard real-time systems, abstract interpretation, integer linear programming (ILP), phase ordering problem. 1