Compiler-Support for Timing Analysis (COSTA)

The COSTA project is concerned with worst-case execution time (WCET) analysis of embedded systems, focusing in particular on developing techniques for compilers to support WCET analysis. A compiler has detailed knowledge about a program and the particular transformations applied to it, which can be used to improve the usability of WCET analysis and the precision of the calculated WCET bound. To achieve this, we focus on two main contributions: 1) the flow facts transformation to support WCET analysis for optimized code and 2) the timing-anomalies aware code generation that makes code more predictable. To calculate the WCET, information describing the feasible paths of a program is needed. We assume that this information - also called "flow facts" - has been already collected by automatic calculations or from manual code annotations. It is preferable to collect these flow facts at high-level program representations like the source code: automatic calculation can use more precise information about the program and in case of manual code annotations it is more convenient doing it at the same level where the program is developed. However, to get precise results for a specific processor, the WCET analysis itself has to be done at object code level. Within COSTA we aim to develop a flow facts transformation framework that keeps the flow facts collected at source-code level consistent in case the compiler performs any code transformations during compilation. As previous work has shown, this update of flow facts cannot be done without the help of the compiler. Beside the flow facts, also the execution time of instructions has to be known to finally calculate the WCET. As complex processors with features like pipelines or caches have a context-dependent instruction timing, it is challenging to calculate the instruction timing. Effects like the so-called Timing Anomalies may occur, where in the extreme case a small local change in the instruction timing will result into an unbounded effect on the overall execution time. Therefore, as a further improvement of compiler support for WCET analysis we will develop a code generation module for the compiler backend that performs instruction scheduling to avoid the potential occurrence of timing anomalies. To achieve this, we will investigate the mechanisms that can lead to such unbounded timing effects and develop a formal specification mechanism for such effects. Compilers providing such support of WCET analysis will help to improve the precision of the analysis and to increase the industrial acceptance of WCET analysis techniques.

Embedded systems have become a quite important part of our daily life. They control a lot of technical processes around us, most of the time even without our awareness. And in many cases even our lives rely on the correct operation of those computer systems, in which case we have to ensure to our best knowledge that they are dependable. For dependable embedded systems, an important factor is to ensure that they fulfill the temporal requirements of their controlled technical processes. A correct result at the wrong time may still lead to catastrophic consequences. Zooming into the internals of a computer system, fulfilling the real-time requirements can be tracked down to the requirement that the execution times of individual software tasks are within their maximal allocated time budget, called deadline. Thus the challenge for a system developer is to ensure that the worst-case execution time (WCET) is below its allowed limit, which is actually a quite complex task, especially in face of the current complexity of software programs and processors. The COSTA project addresses the tool-support for WCET analysis, helping to make WCET analysis simpler and more precise, and thus making the embedded systems trustworthier. WCET analysis needs a description of the possible control flow of a program to derive a precise WCET bound. Such a control-flow description is easier to derive at source-code level than at machine- code level. Within COSTA we developed a technique to automatically transform these control-flow descriptions from source-code level to machine-code level. The strength of this approach is that it works correctly even if the compiler applies a lot of code optimizations that may change the control flow dramatically. As a further improvement, the COSTA project addressed the issue of generating code that is easier to analyze, making WCET analysis faster and more precise for complex processors that show so-called timing anomalies. As the name "timing anomalies" suggests, this is about rather unwanted timing behavior, where a hardware state showing a local execution time of a code fragment being smaller than the local WCET can still lead to the overall WCET of the whole program. This means that in case of timing anomalies the WCET analysis tool cannot apply some periodic filtering of system states to reduce the number of states to be considered for the WCET bound. The code generation techniques developed in COSTA allow to ensure the absence of such timing anomalies for the generated machine code when executed on the target processor.