The loss of explicity for static WCET analysis during compilation

Abstract

Die Analyse der worst-case Laufzeit der Prozesse eines Echtzeitsystems ist eine wichtige Unteraufgabe bei der Konstuktion dieser Systeme. Speziell für harte Echtzeitsysteme, bei denen ein Fehlverhalten zum Verlust menschlichen Lebens führen kann, muss garantiert sein, dass in jedem Fall alle Deadlines des Systems eingehalten werden. Eine statische Analyse der worst-case Laufzeit kann die dafür nötigen sicheren (Über-)Approximationen bieten. Diese (Über-)Approximationen bergen das Risiko in sich, dass diese hoch über der wirklichen worst-case Laufzeit liegen und dass das System als ganzes nicht gebaut werden kann, wenn die berechneten Laufzeiten berücksichtigt werden sollen. Viele Programme für Echtzeitsysteme werden heute in einer höheren Programmiersprache wie C geschrieben. Hauptsächlich da der Objektcode unter anderem Informationen darüber enthält welche Prozessorinstruktionen tatsächlich ausgeführt werden, basiert die statische Laufzeitanalyse nach dem momentaten State-of-the-Art auf Objektcode. Es zeigt sich, dass bei der statischen Laufzeitanalyse von Objektcode Probleme aufteten, die bei der statischen Laufzeitanalyse von Code einer höeren Programmiersprache nicht existent sind. Abstrakt gesehen kann man sagen, dass bestimmte Informationen für die statische Laufzeitanalyse aus dem Code einer höheren Programmiersprache einfacher zu extrahieren sind als jene aus equivalentem Objektcode. In anderen Worten, die Programmrepräsentation einer höheren Programmiersprache ist für diese Information expliziter als die Programmrepräsentation in Objektcode. Diese Diplomarbeit analysiert diesen Verlust an Explizitität und will damit die Forscher auf dem Gebiet der Laufzeitanalyse unterstützen die richtigen Ansatzpunkte zu finden, um diesen Verlust an Explizitheit zu reduzieren und damit bessere Laufzeitanalysesysteme zu schaffen.<br />

The analysis of the worst-case execution time of the processes of a real-time system is an important subtask of building those systems.<br />Especially for hard real-time systems, where a system failure could lead to the loss of human lives, it needs to be ensured that in every case all deadlines of the system are met. Static worst-case execution time (WCET) analysis can provide the necessary safe (over)approximations.<br />Those (over)approximations bear the risk that they are high above the actual worst-case execution time and the system as a whole cannot be built when adhering to the calculated execution time. Today many programs for real-time systems are written in high-level languages such as the C programming language. However, mainly due to the fact that object code contains information on the actually performed processor instructions, it is the state of the art in static WCET analysis to base the analysis on the object code. It turns out that when analyzing object code there are problems for static WCET analysis that are not existent when analyzing high-level language code. Considered from an abstract point of view, it can be said that there is some information that is easier to extract in high-level language code than in the equivalent object code. In other words it can be claimed that the program representation in high-level language is more explicit as far as that information is concerned than the program representation in object code.<br />This thesis analyses this loss of explicity and wants thereby to support researchers in the area of WCET analysis to reduce that loss of explicity in order to create better WCET analysis systems.