Eingebettete Systeme sind in zahlreichen Gebieten wie Unterhaltungselektronik, mobile Kommunikation, Bildverarbeitung oder Fahrzeugbau längst allgegenwärtig. Entwickler sind heute mit Rechenanforderungen konfrontiert, die vor nicht allzu langer Zeit noch Stand der Technik im Supercomputing-Bereich waren. Immer kürzere Entwicklungszyklen bei gleichzeitig steigender Komplexität erfordern optimierende Übersetzer, die Hochsprachen möglichst optimal auf die jeweilige Zielarchitektur übersetzten.<br />Nahezu in jedem modernen Übersetzer wird die Quellsprache zumindest an ausgewählten Punkten in eine Zwischendarstellung basierend auf sogenannter SSA-Form (static single assignment) transformiert. Dabei wird das Quellprogramm in eine Form gebracht, in der jede skalare Variable genau einmal im gesamten Programm definiert wird. Dadurch wird die Analyse und Verwaltung von erreichbaren Definitionen überflüssig und zahlreiche Analysen und Optimierungen werden erheblich vereinfacht. Bisher wurde SSA-Form hauptsächlich für maschinenunabhängige Optimierungen verwendet. Eine Reihe interessanter Eigenschaften macht sie jedoch auch zu einer vorteilhaften Basis für maschinenabhängige Codegenerierungstechniken. In dieser Arbeit werden im Speziellen zwei Teilprobleme betrachtet, die erheblichen Einfluss auf die Qualität optimierender Übersetzer haben: Instruktionsauswahl und Registerzuteilung. In beiden Fällen ziehen heute vorherrschende Techniken noch keinen Nutzen aus den Vorteilen von SSA-Form.<br />Die Aufgabe der Instruktionsauswahl ist es, die Zwischendarstellung des Übersetzters auf Instruktionen der Zielarchitektur in effektiver Art und Weise zu übersetzen. Eine weit verbreitete Technik dafür ist so genanntes Pattern Matching. Dabei wird der Befehlssatz der Zielarchitektur mit Hilfe mehrdeutiger Grammatiken modelliert. Diese werden verwendet, um eine kostenminimale Überdeckung des Eingabeprogramms in Form von Datenflussbäumen zu berechnen. Eine solche Überdeckung entspricht einer konkreten Auswahl von Instruktionen der Zielarchitektur. Traditionelle Techniken sind auf Datenflussbäume beschränkt. In den letzten Jahren wurden jedoch Ansätze vorgeschlagen, die es erlauben, die Techniken für ganze Funktionen mit im Allgemeinen zyklischem Kontrollfluss zu erweitern. Die verwendeten Muster müssen jedoch in einer Baumgrammatik vorliegen, in der jede Produktion eine einfache baumartike Struktur hat. Zahlreiche Instruktionen verbreiteter Architekturen können nicht mit derartigen Grammatiken modelliert werden. Diese Arbeit stellt eine Generalisierung bestehender Techniken vor, die es erlaubt, allgemeinere Graphgrammatiken zu verarbeiten um damit den Befehlssatz verbreiteter Architekturen vollständig zu beschreiben.<br />Das zweite in dieser Arbeit behandelte Optimierungsproblem ist Spilling - ein Teilproblem der Registerzuteilung. Ziel ist es, die beliebig große Menge an temporären Variablen, die während der Instruktionsauswahl generiert wurden, einer endlichen Anzahl von Maschinenregistern zuzuordnen. Im Allgemeinen muss eine Teilmenge dieser Variablen in den Hauptspeicher ausgelagert werden. Dieser Vorgang ist in der Literatur unter dem Begriff Spilling bekannt und hat wesentlichen Einfluss auf das Laufzeitverhalten des erzeugten Maschinencodes aufgrund der hohen Speicherlatenzzeiten. Üblicherweise wird das Registerzuteilungsproblem erst nach Elimination der SSA-Form behandelt. Entwicklungen der letzten Jahre auf dem Gebiet der SSA-basierten Registerzuteilung ermöglichen jedoch eine getrennte Betrachtung der einzelnen Teilprobleme, insbesondere Spilling. Diese Arbeit stellt einen neuen flexiblen Ansatz für Spilling vor. Die neue Technik bietet wesentliche Vorteile, insbesondere für Architekturen mit sehr wenigen Registern.<br />Anstatt problemspezifischer Algorithmen werden beide betrachteten Teilprobleme mit Hilfe von allgemeinen kombinatorischen Optimierungsproblemen modelliert und gelöst. Im Fall der Instruktionsauswahl verwenden wir Partitioned Binary Quadratic Programming (PBQP) - ein generalisiertes quadratisches Zuordnungsproblem. Für das Spilling-Problem entwickeln wir ein Schnittproblem unter Nebenbedingungen, das so genannte Constrained Min-Cut (CMC) Problem. Beide betrachteten Probleme sind NP-vollständig. Nichtsdestotrotz zeigen Experimente mit umfangreichen Testprogrammen, dass beweisbar optimale Lösungen unter akzeptablen Zeitvorgaben berechnet werden können.<br />
de
Embedded systems have become prevalent in various areas such as mobile communication, consumer electronics, image processing, and automotive. Often, the complexity of these systems has reached a point that would have been state-of-the-art in the supercomputing domain not long ago. With decreasing time-to-market cycles and increased software complexity, optimizing compilers that effectively translate applications written in high-level languages to a particular target platform have already become indispensable tools.<br />Almost all modern compiler infrastructures translate high-level programming languages at some point to an internal intermediate representation based on static single assignment (SSA) form. The main idea is to transform a program such that each scalar variable has exactly one definition in the program. Explicitly maintaining so-called use-def chains becomes dispensable and several traditional optimization and analysis passes simplify to a great extent. While SSA form has been traditionally used for high-level optimizations, it has some interesting properties that make it also a valuable tool for backend code generation techniques. In this thesis, we consider two subproblems that are vital for high-quality code generators:<br />instruction selection and register allocation. In both cases, the prevalent techniques are based on traditional program representations that do not take advantage of SSA form.<br />Instruction selection aims to translate a compiler's intermediate code representation to a target-dependent form in a way that is efficient for a particular micro-architecture. A popular algorithmic approach is pattern matching: the target instruction set is modeled using ambiguous cost-annotated graph grammars such that a cover of the program represented in the form of data flow trees can be used to obtain a favorable and semantically equivalent machine representation. Previous work extends the scope of these techniques to the computational flow of a whole function using so-called SSA graphs. However, these techniques are confined to simple tree grammars where each production has tree structure. In this thesis, we show that numerous architectural features of popular embedded architectures cannot be modeled using tree grammars and present a generalization of previous work that is able to deal with generalized graph grammars. The second subproblem considered in this thesis is spilling for programs in SSA form. Spilling is a subtask of register allocation, which aims to map an unlimited set of temporaries produced by the instruction selector to a finite set of machine registers. In general, a subset of these variables has to be deferred to main memory. This process is known as spilling in register allocation literature and has profound effects on the code quality of compilers for embedded systems due to large memory access latencies. Traditionally, compilers eliminate SSA form prior to register allocation. However, recent work shows that programs in SSA form have several interesting properties. In particular, these properties allow for a decoupled approach of spilling that is independent from the remaining register allocator. We propose a new approach to the spilling problem in the most-flexible spill-everywhere model and demonstrate its advantage compared to traditional heuristic techniques, especially for machines with few registers.<br />In both cases, the proposed techniques are based on a modeling of the problem in the form of generic combinatorial optimization problems. In the case of instruction selection, the underlying problem is partitioned binary quadratic programming (PBQP), which is a generalized quadratic assignment problem. Our approach to spilling is based on constrained min-cut (CMC) problems. In both cases, we proof that the underlying decision problem is NP complete. However, we present experimental evidence using major benchmark suites showing that algorithms delivering optimal or near-optimal results are feasible, even for very large programs.
