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