The GRIN Project:
A Highly Optimising Back End for Lazy Functional Languages
Urban Boquist and Thomas Johnsson

Department of Computing Science
Chalmers University of Technology
Göteborg, Sweden
E-mail: {boquist,johnsson}@cs.chalmers.se

Abstract. Low level optimisations from conventional compiler technol-
ogy often give very poor results when applied to code from lazy func-
tional languages, mainly because of the completely dioeerent structure
of the code, unknown control flow, etc. A novel approach to compiling
laziness is needed.
We describe a complete back end for lazy functional languages, which
uses various interprocedural optimisations to produce highly optimised
code. The main features of our new back end are the following. It uses
a monadic intermediate code, called GRIN (Graph Reduction Interme-
diate Notation). This code has a very "functional flavour", making it
well suited for analysis and program transformations, but at the same
time provides the "low level" machinery needed to express many con-
crete implementation concerns. Using a heap points-to analysis, we are
able to eliminate most unknown control flow due to evals (i.e., forcing of
closures) and applications of higher order functions, in the program. A
transformation machinery uses many, each very simple, GRIN program
transformations to optimise the intermediate code. Eventually, the GRIN
code is translated into RISC machine code, and we apply an interpro-
cedural register allocation algorithm, followed by many other low level
optimisations. The elimination of unknown control flow, made earlier,
will help a lot in making the low level optimisations work well.
Preliminary measurements look very promising: we are currently twice as
fast as the Glasgow Haskell Compiler for some small programs. Our ap-
proach still gives us many opportunities for further optimisations (though
yet unexplored).