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
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
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.
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|
|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|