Extending optimising compilation to support worst-case execution time analysis : von Raimund Kirner

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. It is necessary to specify this information at the source code level in order to map the information onto the object code. Therefore, to perform precise WCET analysis for programs optimised by the compiler, the flow facts have to be transformed in parallel to the code transformations. In contrast to previous work this thesis presents a framework to construct flow facts update functions for all types of code optimisations. 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. The approach is based on a graphical transformation framework that takes advantage of the additional semantic code information known by the compiler. 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.

Eingebettete Computersysteme werden zunehmend fuer Steuerungsaufgaben eingesetzt. Um deren sicheren Betrieb zu gewaehrleisten, ist sicherzustellen, dass solche Systeme all ihre Aufgaben innerhalb der vorgegebenen Zeitschranken durchfuehren koennen. Es ist daher notwendig, die maximale Programmausfuehrungszeit (WCET) des auf dem System ausgefuehrten Programmcode zu kennen. Um diese WCET moeglichst genau berechnen zu koennen, muss der Programmcode auf Objektcode-Ebene untersucht werden. Software wird heutzutage typischerweise in Programmiersprachen wie C geschrieben und mit einem Compiler uebersetzt. Aufgrund von Unentscheidbarkeiten werden allerdings fuer die Berechnung der WCET zusaetzliche Kontrollfluss-Informationen benoetigt. Es ist aus praktischen Gruenden erwuenscht, diese Information direkt auf der Ebene des Quellcodes anzugeben. Die Kontrollfluss-Informationen muessen in diesem Fall auf Objektcode-Ebene transformiert werden. Um die WCET-Analyse auch fuer Programme, welche durch einen Compiler optimiert wurden, durchfuehren zu koennen, ist es notwendig, die Kontrollfluss-Informationen parallel zu Programm-Transformationen entsprechend zu aktualisieren. Im Gegensatz zu frueheren Arbeiten stellt diese Arbeit ein Framework zur Konstruktion von Transformationen der Kontrollfluss-Informationen bereit, dass alle Arten von Codeoptimierungen unterstuetzt. Zuvor publizierte Ansaetze basierten entweder auf Beziehungen zum Quellcode ueber Debuginformationen beziehungsweise auf Traceausgaben fuer eingeschraenkte Programmtransformationen. In dieser Arbeit wird ein neuartiges Konzept vorgestellt, mit dem Kontrollfluss-Informationen parallel zu vom Compiler durchgefuehrten Programmtransformationen aktualisiert werden. Von den Programmtransformationen wird hierbei auf die relevanten strukturellen Aenderungen abstrahiert. Diese strukturellen Aenderungen zusammen mit der ueber die durchgefuehrte Programmtransformation bekannten Kontrollfluss-Semantik induzieren eine sichere und genaue Transformation der Kontrollfluss-Informationen. Die Durchfuehrung wird durch eine graphische Repraesentation der durchgefuehrten strukturellen Programmaenderungen erleichtert. Die verwendete abstrakte Darstellung des Kontrollflussgraphen erlaubt auch die Verwendung von Bloecken mit beliebig vielen Kontrollflusskanten. Damit wird die Integration der Methode in eine Vielzahl existierender Compiler unterstuetzt.