A Constraint-based Logic Analysis for TuBound

Adrian Prantl

Vienna University of Technology, Vienna, Austria
 

The safety of our day-to-day life depends crucially on the correct functioning of embedded software systems which control the functioning of more and more technical devices. Many of these software systems are time-critical. Hence, computations performed need not only to be correct, but must also be issued in a timely fashion. Worst case execution time (WCET) analysis is concerned with computing tight upper bounds for the execution time of a system in order to provide formal guarantees for the proper timing behaviour of a system. State-of-the-art WCET analysis tools rely on supporting analyses and manual annotations to provide them with information on the execution behaviour of the program such as loop bounds or maximum recursion depths. Typically, both steps are performed on the binary code of the program. The manual annotation of a binary program, however, imposes high demands on the programmer [1].

With TuBound, we are providing an improved work-flow by lifting manual annotations and supporting analyses to the source code level of a program. The information computed on this level and annotated in the code is then conjointly transformed throughout the compilation and optimization of the program to the binary code level to make it accessible to the WCET analysis component of our TuBound tool [2].

In this talk, we highlight the static program analysis component of TuBound at whose heart is an interprocedural interval analysis and an approach to loop analysis that is based on constraint logic programming [3].  

References:

[1]     Raimund Kirner, Jens Knoop, Adrian Prantl, Markus Schordan, and Ingomar Wenzel. WCET Analysis: The Annotation Language Challenge. In Proceedings 7th Int. Workshop on Worst-Case Execution Time Analysis (WCET 2007), 83 - 99, Pisa, Italy, 2007.
[2]     Adrian Prantl, Markus Schordan, and Jens Knoop. TuBound A Conceptually New Tool for Worst-Case Execution Time Analysis. In Proceedings 8th Int. Workshop on Worst-Case Execution Time Analysis (WCET 2008), 141-148, Prague, Czech Republic, 2008. ISBN: 978-3-85403-237-3.
[3]     Adrian Prantl, Jens Knoop, Markus Schordan, and Markus Triska. Constraint solving for high-level WCET analysis. In Proceedings of the 18th Int. Workshop on Logic-based methods in Programming Environments (WLPE 2008), Udine, Italy, 2008.
 

Biography:

Adrian Prantl studied computer science at the Vienna University of Technology. During the final year he worked with OnDemand Microelectronics designing and implementing the compiler tool chain for the Chili family of VLIW processors. He is currently working towards a PhD and engaged in the FWF-funded project "Compiler Support for Timing Analysis" (CoSTA) aiming at bringing the power of source code transformations to the field of worst-case execution time analysis.

Contact Adrian at:

Dipl.-Ing. Adrian Prantl
Institute of Computer Languages
Vienna University of Technology
A-1040 Vienna, Austria
adrian at complang.tuwien.ac.at
http://www.complang.tuwien.ac.at/adrian