[ main page ] [ back ]

2003 : Extending Optimising Compilation to Support Worst-Case Execution Time Analysis

Author(s)
Abstract
Embedded real-time systems are increasingly used in control applications. To guarantee the safe operation it is required to verify that the system can complete its tasks within their deadlines. Therefore, it is important to know the worst-case execution time (WCET) of the code running on the system. For the precise calculation of the WCET, the code has to be analysed at the object code level. The software is typically written in a language like C and translated by a compiler. Due to undecidability, the calculation of the WCET needs the knowledge of additional control-flow information -- so-called flow facts. It is necessary to specify this information at the source code level in order to map the information onto the object code. For precise WCET analysis of programs optimised by the compiler, the flow facts have to be transformed in parallel to the code transformations performed during optimisation. This thesis presents a framework to maintain correct flow facts during code optimisation. Previous solutions are either based on matching the debug information with the source code or on logging of only restricted code transformations. This thesis presents a novel concept to transform flow information in parallel to the code transformations performed by the compiler. The code transformations are abstracted to their relevant structural changes. From the structural update and the known semantic control-flow information of the performed code transformation, a safe and precise transformation of the flow information is induced. A graphical transformation framework to describe the performed code transformations supports the reader in understanding the required update of flow facts. The abstract representation of the control flow graph allows the modelling of blocks with multiple branching edges which enables the integration of this method into various compilers. The result is a framework that supports high-quality WCET analysis of optimised code.
Bibtex
@PhdThesis{Kirner:PTHESIS2003,
  author = 	 {Raimund Kirner},
  title = 	 {Extending Optimising Compilation to Support                      
                  Worst-Case Execution Time Analysis},
  school = 	 {Technische Universit\"at Wien},
  year = 	 {2003},
  address =      {{Treitlstr. 3/3/182-1, 1040 Vienna, Austria}},
  month = 	 {May}
}
Download
Get kirner_phd.pdf - Adobe PDF-format, (1504.6982 KB; posted at July 09 2013; includes hyperlinks)


[ main page ] [ back ]