Worst-Case Execution Time Analysis for Optimized Code

By Jakob Engblom

MSc Thesis DoCS 97/94

ABSTRACT

In the field of real-time systems, accurate estimates of the worst-case execution time of programs are required for real-time modelling and verication, scheduling analysis, feasibility analysis, and dimensioning of the system hardware. At present, such estimates are produced by measuring program runs on inputs which are believed to produce long execution times. Unfortunately, such measurements provide no guarantee for finding the worst execution time, thereby producing unsafe systems. To obtain safe estimates (estimates which do not underestimate the worst-case time), we have to use formal static analysis.

Because the market demands high performance, low cost products, we must use optimizing compilers when developing software for real-time systems. An optimizing compiler improves the performance of a program and reduces the size of the code, both important factors to save costs while maintaining performance. An optimizing compiler makes static analysis of a program more dicult by complicating the relationship between the program source code (where we can obtain knowledge about possible program executions) and the object code (where we can find concrete execution times).

In this thesis, we present (1) a new framework for static timing analysis of optimized pro- grams and (2) co-transformation, a new approach tokeep track of timing information while performing the various transforming and optimizing steps in a compiler. The co-transformer is based on a close cooperation between compiler and timing analyzer.
We have implemented a prototype co-transformer, and evaluated it using a representative set of compiler optimizations. We show that the idea is feasible, but that much more work is needed to design a datastructure powerful enough to capture all necessary information about program execution. In addition, the thesis points out some directions for future research in the field of worst-case execution time analysis in particular and the real-time programming field in general.

Updated Friday, 11-Apr-2008 15:44 by Roland Grönroos
Webmaster: anton@control.lth.se
Location: http://www.snart.org/docs/Exjobb98/jengblomabstract.shtml