Universitšt Karlsruhe
Projekt Firm

Graphbasierte SSA Zwischensprache mit expliziten Speicherabhängigkeiten

Firm ist eine moderne Zwischensprache die an unserem Institut entwickelt wurde. Firm implementiert statische Einmalzuweisung (SSA) und stellt ein Programm als einen Datenflussgraphen dar. Neuartige Darstellungen von Abh√§ngigkeiten √ľber Objekte im Speicher und vom Steuerfluss bei Ausnahmen machen Firm zu einer idealen Basis zur Erforschung von Optimierungen.

Das Entstehen von Firm

Firm wurde zuerst von Armbruster und von Roques eingef√ľhrt. Martin Trapp verfeinerte und erweiterte Firm in seiner Doktorarbeit. Armbruster und von Roques implementierten Firm in einem experimentellen √úbersetzer, Fiasco, f√ľr die Sprache Sather-K. Firm ist ebenfalls als eigenst√§ndige Implementierung verf√ľgbar. Diese bietet vielf√§ltige Unterst√ľtzung f√ľr Forschung im Bereich √úbersetzeroptimierungen.

Eigenschaften von Firm

Das Designziel einer neuen Zwischensprache war, eine Darstellung zu entwickeln die schnelle und mächtige Optimierungen objektorientierter Programme ermöglicht. Daher unterscheidet sich Firm in verschiedenen Gesichtspunkten von traditionellen Zwischensprachen.

Firm verwendet statische Einmalzuweisung (SSA). In SSA dargestellte Variablen werden zu Datenflusskanten aufgel√∂st. Daher enth√§lt die Zwischensprache keine Darstellung von Objekten, die solche lokale Variablen enthalten. Durch die Datenflussdarstellung kann Wertnummerierung direkt in die Darstellung integriert werden. Zus√§tzlich zu den Abh√§ngigkeiten die aus der traditionellen SSA Darstellung resultieren werden Abh√§ngigkeiten zwischen dynamisch allozierten Objekten explizit dargestellt. Solche Programmobjekte k√∂nnen nicht in SSA Form dargestellt werden. Daher enth√§lt die Darstellung f√ľr diese Objekte auch Anti- und Ausgabeabhängigkeiten. Weiter implementiert Firm ein neues Konzept zur Darstellung von Ausnahmen. Diese Darstellung minimiert den Informationsverlust bei Datenflussanalysen wenn Ausnahmen als Steuerfluss√§nderungen dargestellt werden.

Firm ist eine niedere Zwischensprache, d.h., die Operationen in Firm sind den Operationen einer Zielmaschine √§hnlich. Dies unterst√ľtzt, Befehlsanordnung auf der Basis von Firm auszuf√ľhren. Bei der Anordnung kann dadurch auf alle Informationen die durch Analysen gewonnen wurden zurückgegriffen werden, um maximale Parallelität auf Befehlsebene zu erreichen. Die Datenflussdarstellung von Variablen, die Registern zugewiesen werden können, repräsentiert syntaktisch die Information, die für die Befehlsanordnung nötig ist.

Existierende Anwendungen von Firm

Fiasco: Der Sather-K Übersetzer Fiasco enthält eine private Firmimplementierung. Dieser Übersetzer führt alle von der Zielmaschine unabhängigen Optimierungen auf dieser Darstellung durch. Trapp entwickelte eine starke Haldenanalyse und Optimierung objektorientierter Konstrukte auf dieser Firmimplementierung. Diese Optimierungen verbessern die Ausführzeiten objektorientierter Programme auf den Level effizient implementierter imperativer Programme.

CoSy System: Im JOSES Project entwickelten wir eine Optimierungsphase auf einer Firmdarstellung in einem mit dem CoSy Übersetzerbaukasten geschriebenen Übersetzer. Zu diesem Zweck entwarfen wir eine fSDL Spezifikation von Firm sowie Transformationsphasen von CCMIR/OMIR zu Firm und zurück.

Bibliothek: Aktuell arbeiten wir mit einer stand-alone Implementierung von Firm in Form einer C-Bibliothek. Die Bibliothek bietet Datenstrukturen um die meisten Informationen aus einem Quellprogramm darzustellen. Sie enthält Module um Typen, alle im Programm spezifizierten Entitäten, Konstanten, Namen, und natürlich Programmcode darzustellen. Die Bibliothek unterst√ľtzt den Aufbau der Zwischensprache aus einem Frontend. Sie bietet eine gro√üe Anzahl von Standardoptimierungen und -analysen. Sie enth√§lt ein Schnittstelle um die Zwischenrepr√§sentation zu transformieren um weitere Optimierungen zu implementieren und unterstützt Debuginformation.

Für Experimente mit Firm kann aus den abstrakten Syntaxbäumen von Jikes, dem GNU C-Übersetzer und dem Metaprogrammierwerkzeug Recoder die Firmdarstellung aufgebaut werden. Der Backendgenerator CGGG kann für die Graphdarstellung der Firmbibliothek verschiedene Ausgaben generieren.

Projektbeteiligte

Alumni
Prof. Sebastian Hack
Dr. Boris Boesler
Dr. Rubino Geiß
Dr. Florian Liekweg
Dr. Götz Lindenmaier
Michael Beck
Matthias Braun
Ex-Hiwi
Sebastian Felis
Ex-Studenten
Matthias Heil
Christoph Mallon
Till Riedel
Andreas Schösser
Johannes Spallek
Beyhan Veliev
Christian W√ľrdig

Software in diesem Projekt

GrGen
Das Graphersetzungs-Werkzeug. GrGen ist SPO basiert, schnell und einfach benutzbar.
libFirm
Eine C Implementierung der Zwischensprache Firm.
yComp
Das Anzeigesystem f√ľr Programmgraphen in VCG-Format

Publikationen zum Projekt

2008
Buchwald, Zwinkau, Befehlsauswahl auf expliziten Abhängigkeitsgraphen
 
2007
Hack, Register Allocation for Programs in SSA Form
Mallon, If-Konversion auf SSA
 
2006
Braun, Heuristisches Auslagern in einem SSA-basierten Registerzuteiler
Liekweg, Compiler-Directed Automatic Memory Management
 
2005
Lindenmaier, Beck, Boesler, Geiß, Firm, an Intermediate Language for Compiler Research
 
2002
Lindenmaier, libFIRM -- A Library for Compiler Optimization Research Implementing FIRM
 
2001
Trapp, Optimierung objektorientierter Programme. √úbersetzungstechniken, Analysen und Transformationen.
 
1999
Trapp, Lindenmaier, Boesler, Documentation of the Intermediate Representation FIRM
Login
Links