Compilation for predictable real-time systems

Abstract

Echtzeitsysteme benötigen Garantien zum Laufzeitverhalten der ausgeführten Programme, üblicherweise zumindest eine Schranke der maximalen Ausführungszeit (WCET). Die Komplexität heutiger Computer-Architekturen macht es allerdings schwierig das Laufzeitverhalten eines Programmes vorherzusagen. Die Single-Path Programmier-Methodik vereinfacht die Vorhersage des Laufzeitverhaltens dadurch, dass vermieden wird, dass Eingangsdaten die Auswahl des Ausführungspfads beeinflussen. Derartige Programme führen bei jeder Ausführung exakt die gleiche Befehlssequenz durch. Dieses Dokument beschreibt die automatische Übersetzung von annotiertem Quellcode in ein Single-Path Programm. Diese Übersetzung besteht aus einer Datenflussanalyse zur Bestimmung der eingangsdatenabhängigen Verzweigungen und einer Übersetzungsphase, die diese Verzweigungen durch bedingt ausgeführten Maschinencode ersetzt.

Real-Time systems require guarantees on the execution time of the executed programs, commonly at least a Worst-Case Execution-Time (WCET) bound. The complexity of today's computing architectures makes it difficult to predict the execution timing of a program. The single-path programming scheme improves timing predictability by eliminating the selection of different execution paths depending on the input data provided to the program. Such programs execute the exactly same sequence of instructions for every invocation. This document describes the automated transformation to a single-path program from annotated source code. The transformation consists of a dataflow analysis to identify the input-data dependent branches in the program and a transformation phase that replaces these branches by utilizing conditional execution, i.e., predicated instructions.