High-level compiler support for timing analysis

Abstract

Um robuste eingebettete Systeme zu entwerfen, ist die Analyse der Ausführungszeit von großer Bedeutung. Ziel der vorliegenden Dissertation ist es einen Weg aufzuzeigen, wie das Zeitverhalten von Computerprogrammen mit geringstmöglicher Unterstützung von menschlicher Seite untersucht werden kann. Um möglichst straffe, aber sichere Schranken für die Ausführungszeit eines Programms zu erhalten, sind exakte Informationen über dessen Kontroll- und Datenfluss notwendig. Bisweilen wird diese Information von Hand gesammelt und an das übersetzte Binärprogramm annotiert. Im letzten Jahrzehnt konnte ein deutlicher Trend festgestellt werden, diesen Vorgang durch den Einsatz statischer Programmanalysen zu automatisieren. Da das Problem im Allgemeinen jedoch unlösbar ist, werden manuelle Annotationen wohl immer vonnöten sein. Akzeptiert man diese Tatsache, so ist es unumgänglich, diesen mühsamen und fehlerbehafteten Vorgang so einfach und sicher wie möglich zu machen.<br />Wie die Sicherheit ist auch Leistung ein zentraler Punkt, wenn eingebettete Systeme in großen Stückzahlen produziert werden sollen. Während sich die durchschnittliche Leistung vor allem auf den Stromverbrauch auswirkt, so ist die Leistung im schlechtestmöglichen Fall (Worst-case-Performance) der bestimmende Faktor eines Echtzeitsystems: Eine höhere Worst-case-Performance bewirkt, dass das System kosteneffizienter dimensioniert werden kann, wodurch die Produktionskosten gesenkt werden, ohne die Sicherheit zu gefährden. Daher ist in diesem Bereich auch die Verbindung von Zeitanalyse und Programmoptimierungen eine der Kernaufgaben der Forschung. Ziel soll jedoch nicht sein, den hochoptimierten Binärcode, wie er von einem Compiler erzeugt wird, von Programmieren annotieren zu lassen. Ziel ist vielmehr, Kontrollflussannotationen bereits auf Quelltextebene durchzuführen und diese Informationen dann gemeinsam mit dem Programm durch die Optimierungsschritte zu führen und entsprechend zu transformieren.<br />In dieser Arbeit zeigen wir (1) einen Weg, das Annotationsniveau von der Maschinensprache auf die Quelltextebene anzuheben, um Annotationen auf der Abstraktionsebene der Programmiersprache zu präsentieren.<br />Weiters (2) stellen wir auf dem Quelltext arbeitende statische Programmanalysen vor, mit denen die Notwendigkeit, Annotationen manuell vornehemen zu müssen, auf ein Mindestmaß reduziert werden kann. Damit (3) präsentieren wir eine portable Lösung für die oben genannten Probleme, die mit minimalem Aufwand auf andere Zielarchitekturen übertragen werden kann.<br />Die Teilnahme an der WCET Tool Challenge 2008 hat bestätigt, dass unser Ansatz mit anderen Implementierungen konkurrenzfähig ist, insbesondere in Bezug auf die automatische Kontrollflussanalyse.<br />Damit, dass unsere Implementierung eine Teilmenge von C++ unterstützt, greifen wir auch einen aufkommenden Trend für eingebettete Systeme auf, in denen C nach wie vor die vorherrschende Programmiersprache ist, jedoch nach und nach durch C++ abgelöst wird.<br />

Timing analysis is an important prerequisite for the design of robust embedded systems. The purpose of this thesis is to show how to analyze the timing of computer programs with as little human assistance as possible. In order to get tight and safe bounds for the timing of a program, precise information about its control flow and data flow is needed. Traditionally, this information is collected by hand and annotated to the binary program. The last decade showed a trend to automate much of this work by employing static analyses. However, due to the theoretical intractability of the general problem, manual input is still and will aways be necessary. Once we acknowledge the need for manual annotations, it is important to make this cumbersome and error-prone process as easy and safe as possible.<br />Performance is also a critical issue for systems that are produced in large quantities. While the average performance has an influence on power consumption, the worst-case performance is what is critical for a real-time system: A better worst-case performance means that the hardware can be dimensioned more cost-effective, thus lowering production costs, without sacrificing safety. The main research question is therefore how to adequately combine code optimizations and timing analysis. We do not intend to force the programmer to manually annotate control flow information to highly optimized code produced by the compiler. Instead, flow annotations should be made at the source code level and be transformed alongside the program during the optimization phase.<br />In this thesis we (1) show how to lift the annotation level from the machine code to the source code, which is the adequate and more natural representation for the programmer, and (2) reduce the need for manual annotations by using static analysis at the source code level, thus (3) providing a portable solution to the problems mentioned above that is largely independent from the target architecture.<br />By entering the implementation into the WCET Tool Challenge 2008 we demonstrated that this approach is on par with competing approaches, especially with respect to automatic control flow and data flow analysis. With our implementation we also embrace a continuing trend in the embedded systems market, by supporting a subset of C++ instead of just C, which is still the prevailing programming language in this field.