Universitšt Karlsruhe
Project Firm

Graph Based SSA Intermediate Language with Explicit Memory Dependencies

Firm is a modern intermediate representation (ir) developed at our institute. It implements single static assignment form and represents a program as a dataflow graph. Novel representations of dependencies through objects in memory and control flow in case of exceptions make it an ideal basis for optimization research.

The Origin of Firm

Firm was first presented by Armbruster and von Roques, subsequently refined and extended by Trapp in his PhD Thesis. Armbruster and von Roques implemented Firm in an experimental compiler, Fiasco, for the language Sather-K. Firm is also available as a standalone implementation supplying various support for compiler optimization research.

Properties of Firm

The design goal for a new intermediate representation was to develop an ir that supports fast and powerful optimization of object oriented programs. Therefore Firm differs in several aspects from traditional irs.

Firm is based on static single assignment (SSA) form. Variables represented in SSA are resolved to data flow edges so that the ir contains no representation of objects that hold local variables. The dataflow representation further allows to include value numbering in the representation. In addition to the dependencies represented in SSA by traditional irs, Firm represents dependencies between dynamic allocated objects explicitly. Such program objects can not be represented in SSA, so that anti- and output dependencies between these objects are modeled. Further Firm implements a new concept to model exceptions reducing the loss of preciseness of dataflow analysis if exceptions are modeled as control flow changes.

Firm is a low ir, it's operations are similar to operations on target machines. This supports to perform scheduling directly in Firm, so that the scheduler can use all information gathered by any optimization to achieve maximal parallelism. The dataflow representation of variables that can be allocated to registers represents the information needed for scheduling syntactically.

Existing applications of Firm

Fiasco: The Sather-K compiler Fiasco contains a private implementation of Firm. This compiler performs all target independent optimizations on this representation. Trapp developed a strong heap analysis and optimizations of object oriented constructs on this Firm implementation improving program performance of object oriented programs to a level of clever implemented imperative programs.

CoSy System: The JOSES project constructed a Firm optimization phase in a compiler written with the CoSy compiler system. For this purpose we designed a fSDL specification for Firm and transformation phases between the CCMIR/OMIR and Firm representations.

Library implementation: Currently, we are working with a stand alone library implementation of Firm. The library supplies data structures to represent most of the information available in a program. It contains modules to represent type information, all entities specified by a program, a constant table, a name table and, of course, program code. The library supports constructing intermediate code from a front end. It offers a large set of standard optimizations and analyses. It supplies functionality to transform the ir to implement additional optimizations. It can handle debug information for the compiled program.

To experiment with the Firm representation the library is linked with the abstract syntax trees constructed by the Jikes compiler, the gnu C compiler and the meta programming tool Recoder. The backend generator CGGG can consume Firm graphs from the library and produce various outputs.

We lately extended firm by a variety of features. A generator constructs a Java Native Interface for the Firm interface. This allows to generate the Firm representation from a frontend written in Java.

We utilized the Firm-JNI to construct a phase that builds firm from the Recoder abstract syntax tree (See IPD project COMPOST).

We implemented a target machine arithmetics module for constant evaluation in Firm replacing the old tv module. This target arithmetic can be configured to various target machines by specifying the features of the target machine. The performed computations suffice the according standards as IEEE745.


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

Software in this Project

The Graph Rewrite Tool. GrGen is SPO based, fast and easy to use.
A C implementation of the intermediate representation Firm.
Visualization system for Program Dependency Graphs in VCG format

Related Publications

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