[TYPES] a paper available on "Record Unboxing", a new type-based optimization

[Atsushi Ohori]

Dear Colleagues,

Some of the types-list readers may be interested in the following
paper, which shows a new type-based optimization method that "unboxes"
tuples/records by flattening component tuples and changing top-level
tuples to multiple value passing. The required type based analysis is
simple but the resulting method shown to be quite effective.

This is implemented in the SML# (an extension of the Standard
ML) compiler version 0.30, which is available from:
http://www.pllab.riec.tohoku.ac.jp/smlsharp/

Any comments are welcome.

Best regards,
Atsushi

--------------------------------------------------------------------

			Record Unboxing
               Huu-Duc Nguyen  and  Atsushi Ohori
                    RIEC, Tohoku University

http://www.pllab.riec.tohoku.ac.jp/~ohori/research/RecordUnboxing.pdf

In the conventional implementation of functional languages, tuples
(records) are uniformly implemented as heap allocated objects even
when they are used only for multiple parameter passing.  This paper
develops a type-based ``record unboxing'' optimization method that
reduces the overhead due to those unnecessary heap allocation and
associated memory accesses.  We first develops a type-based algorithm
that infers where each record expression is ``rigid'' or not, i.e. it
requires heap allocation or not based on the observation that change
of a representation of a record type that does not interact with the
external environment does not affect the behavior of the program.  We
then develop a record unboxing algorithm that transforms a functional
language with records to a multiple value calculus in which a function
can take/return multiple values by transforming all non rigid records
into multiple values.  The combination of the two yields a simple and
yet surprisingly effective optimization method.  We have implemented
the proposed method in a compiler for full Standard ML language, and
have evaluated it with a typical benchmark programs.  The results show
significant speed ups for non trivial benchmarks, including 21% speed
up of mlyacc and 27% speed up for lexgen.