Compiler-Support for Timing Analysis

01.07.2006 - 30.06.2009
Research funding project
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.

People

Project leader

Sub project leader

Project personnel

Institute

Grant funds

  • FWF - Österr. Wissenschaftsfonds (National) Austrian Science Fund (FWF)

Research focus

  • Computer Engineering: 100%

Keywords

GermanEnglish
Maximale Programmausführungszeit (WCET)worst-case execution time analysis (WCET)
Flussfaktenflow facts
Compilertechnikencompilation techniques
Zeitanomalientiming anomalies
Laufzeitmessungenexecution time measurements

External partner

  • Institut für Computersprachen

Publications