Validating a Worst-Case Execution Time Analysis Method for an Embedded Processor

Knowing the Worst-Case Execution Time (WCET) of a program is necessary when designing and verifying real-time systems. When evaluating WCET analysis methods, the common methodology is to compare a WCET estimate with an execution of the same program with known worst-case data on the target hardware. This evaluation method is inadequate, since errors in one part of the analysis might mask errors occuring in other parts of the analysis. In this paper we present a methodology for systematically testing WCET analysis tools for modern pipelined processors. The methodology is based on a decomposition of WCET analysis into a set of components that should be tested and validated in isolation. Our testing methodology does not require that we have a perfect model of the hardware, thus the validation of the hardware model is considered as a separate problem. We apply the methodology to our previously published WCET analysis method, and show that the pipeline analysis and the calculation method we use are safe and produce tight results. We also show that our WCET analysis method can handle programs containing nested loops, functions whose execution times depend on parameters, multiway branches (switch statements) and unstructured code.