Compiler-Unterstützung für Zeitanalyse

Das Projekt COSTA beschäftigt sich mit der Analyse der Maximalen Programmausführungszeit (WCET) von Eingebetteten Systemen, wobei der Fokus im Speziellen auf der Entwicklung von Compiler-Techniken zur Unterstützung der WCET-Analyse liegt. Ein Compiler hat detailliertes Wissen über ein Programm und die darauf angewendeten Transformationen, was dazu benutzt werden kann, die Verwendbarkeit der WCET-Analysise und die Präzision der berechneten WCET-Schranke zu verbessern. Zur Erreichung dieser Ziele behandeln wir die folgenden zwei Beiträge: 1) Transformation von Fluss-Daten um die WCET-Analyse für optimierten Code zu unterstützen, und 2) eine Codegenerierung welche den Code durch die Vermeidung von Zeitanomalien besser vorhersagbar macht. Um die WCET zu berechnen sind Informationen notwendig, welche erreichbare Programmpfade beschreiben. Wir nehmen an, das solche Information - auch "Fluss-Daten" genannt - bereits mittels automatischer Berechnung oder manueller Zusicherungen vorliegen. Es ist vorteilhaft wenn solche Fluss-Daten auf einer abstrakten Ebene wie etwa auf Quellcodeebene vorliegen: die automatische Berechnung der Fluss-Daten hat in diesem Fall mehr Programminformation zur Verfügung und bei Verwendung von manueller Zusicherungen ist es wesentlich komfortabler, diese auf der selben Ebene anzugeben, wo man auch das Programm entwickelt. Um jedoch präzise Ergebnisse für einen konkreten Prozessor zu erhalten, muss die WCET-Analyse selbst auf der Ebene des Objektcodes gemacht werden. Innerhalb von COSTA werden wir eine Methode zur Transformation der Fluss- Daten entwickeln, welche die auf Quellcodeebene gesammelten Flussdaten konsistent hält wenn der Compiler während der Kompilierung Codetransformationen durchführt. Vorarbeiten haben gezeigt, dass die Anpassung der Fluss-Daten nicht ohne die Hilfe des Compilers gemacht werden kann. Neben den Fluss-Daten werden auch die Ausführungszeiten von Programminstruktionen benötigt um letztendlich die WCET zu berechnen. Da aber komplexe Prozessoren mit Features wie etwa Pipelining oder Caching kontext- abhängige Instruktionsausführungszeiten haben, ist es eine Herausforderung, diese Instruktionsausführungszeiten zu berechnen. Effekte wie die so genannten "Zeitanomalien" können auftreten, wobei im Extremfall sogar eine kleine Änderung einer Instruktionsausführungszeit zu einer unbeschrankten Veränderung der Gesamtausführungszeit führen kann. Aus diesem Grunde entwickeln wir als weitere Unterstützung der WCET-Analyse ein Compiler- Modul zur Codegenerierung, welches Instruktionsscheduling zur Vermeidung des potentiellen Auftretens von Zeitanomalien durchführt. Compiler, die eine Unterstützung der WCET-Analyse anbieten, werden dazu beitragen, die Qualität der Analyse zu verbessern sowie die Akzeptanz von WCET-Analysetechniken seitens der Industrie zu erhöhen.

Eingebettete Systeme sind zu einem sehr wichtigen Bestandteil unseres täglichen Lebens geworden. Sie kontrollieren viele technische Prozesse rund um uns, oft ohne dass wir überhaupt Notiz davon nehmen. Jedoch in vielen Fällen hängt sogar unser Leben von der korrekten Funktionsweise dieser Computersysteme ab. Deshalb liegt es in unserer Verantwortung, diese Systeme auf bestmögliche Zuverlässigkeit hin zu entwickeln. Für solche sicherheitskritischen Systeme ist es auch sehr wichtig, dass sie die zeitlichen Anforderungen ihrer kontrollierten Prozesse erfüllen. Das heißt, ein korrektes Ergebnis zum falschen Zeitpunkt kann immer noch zu katastrophalen Konsequenzen führen. Schaut man nun in die Innereien solch eines Computersystems hinein, so kann man erkennen, dass für die Einhaltung der Echtzeiteigenschaften es notwendig ist, dass individuelle Softwaretasks innerhalb des ihnen zugewiesenen maximalen Zeitbudgets, auch Deadline genannt, ausgeführt werden. Es ist daher die Aufgabe des Entwicklungsingenieurs, sicherzustellen, dass die maximale Programmausführungszeit (engl. Worst-Case Execution Time, kurz WCET) unterhalb des erlaubten Limits ist. Dies ist allerdings keine leichte Aufgabe, vor allem aufgrund der hohen Komplexität typischer Softwareprogramme und Prozessoren. Das Ziel des COSTA-Projektes ist die Toolunterstützung für WCET-Analyse, um somit WCET-Analyse sowohl einfacher wie auch präziser zu machen, und somit die entwickelten Eingebetteten Systeme vertrauenswürdiger zu machen. Für WCET-Analyse wird eine Beschreibung des möglichen Kontrollflusses eines Programms benötigt, um eine präzise obere Schranke der WCET zu berechnen, wobei eine solche Kontrollflussbeschreibung viel einfacher auf Quellcodeebene als auf Maschinencodeebene bestimmt werden kann. Innerhalb von COSTA wurde daher eine Technik entwickelt, um solche Kontrollflussbeschreibungen von Quellcodeebene to Maschinencodeebene zu transferieren. Die Stärke dieses Ansatzes ist, dass er auch dann korrekt funktioniert, wenn der Compiler viele Codeoptimierungen anwendet, welche den Kontrollfluss drastisch verändern können. Ein weiterer Beitrag des COSTA-Projektes ist die Generierung von leicht analysierbaren Maschinencode, um letztendlich WCET-Analyse schneller und präziser zu machen für Prozessoren, welche sogenannte "Zeitanomalien" aufweisen. Wie der Name "Zeitanomalie" schon vermuten lässt, handelt es sich dabei um ein unerwünschtes Verhalten, bei welchem ein Hardwarezustand, obwohl er für einen bestimmten Programmausschnitt zu einer kleineren als der maximalen Ausführungszeit führt, trotzdem zur WCET für das gesamte Programm führen kann. Das heißt, dass im Falle von Zeitanomalien die WCET-Analyse nicht sporadisch Systemzustände ausfiltern kann, für welche man weiß, dass sie für die Bestimmung der WCET irrelevant sind. Die in COSTA entwickelte Codegenerierungstechnik erlaubt es, für das konkrete Programm sicherzustellen, dass es bei Ausführung auf dem gewählten Ziel-Prozessor keine Zeitanomalien aufweist.