– 1 – Complete Worst-Case Execution Time Analysis of Straight-line Hard Real-Time Programs

In this article, the problem of finding a tight estimate on the worst-case execution time (WCET) of a real-time program is addressed. The analysis is focused on straight-line code (i.e. code without loops and recursive func-tion calls) which is quite commonly found in synthesised code of hard real-time embedded systems. The anal-ysis exploits the very simple structure of these programs, resulting in a considerable processing time improvement compared to general-case analysis techniques. A comprehensive timing analysis system, called the Program Timing Analyser (PTA), covering low-level aspects (on the assembler instruction level) as well as high-level aspects (on the programming language level) is presented.The concepts of PTA are demonstrated with a detailed example. Also some experimental results are given. On one hand the low-level analysis covers all speed-up mechanisms used for modern superscalar processors: pipelining, instruction-level parallelism and caching. It can handle a unified cache as well as separate caches for data and instructions. The pipelined and parallel execution of assembler instructions is analysed a-priori. Also, the analysis predicts whether memory accesses will hit the caches at run-time. On the other hand the high-level analysis addresses the problem of using the results from the low-level to com-pute the final estimate on the WCET. This is done by a heuristic for searching the longest really executable path in the control flow, i.e. by taking into account functional dependencies between various program parts. The heuristic represents a reasonable trade-off between accuracy and effort. By exploiting the simple structure of the input code, no user-annotations are necessary, resulting in a safe and efficient analysis