This paper presents a program transformation that allows languages with polymorphic typing (e.g. ML) to be implemented with unboxed, multi-word data representations, more efficient than the conventional boxed representations. The transformation introduces coercions between various representations, based on a typing derivation. A prototype MIL compiler utilizing this transformation demonstrates important speedups. It is common saying that statically-typed programs can be compiled more efficiently than dynamically-typed programs. A number of run-time type tests become unnecessary, for instance. In this paper, we study some compilation techniques that rely on the availability of typing information at compile-time. These techniques are connected to the da,ta representation problem: how high-level objects manipulated by the language are mapped onto machine-level objects, Static typing and data representation There are many ways in which knowing type information at compile-time can help in selecting better representations for data. First of all, a compiler needs to know the size (required amount of memory) of all objects manipulated by the program, in order to allocate enough space for variable valu,es and intermediate results, and to move the right number of bits from one Iocation to another when performing bindings or assignments. Without static typing, a default size (usually one word) must be assumed for all objects in the program, and all represent ations must fit in this size. Objects that do not fit naturally in one word, such as * Author's address: INRIA Rocquencourt, projet Formel, B.P. Le Chesnay, France. E-mail: Xavier .Leroy@inria. f r. Permission to copy without fee afl or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the ACM copyright notice and the title of the publication and its date appear, and notice is given that copying is by permission of dte Association for Computing Machinery. To copy otherwise, or to republish, requires a fee and/or specific permission. records and 64-bit floating-point numbers, have to be boxed (allocated in the heap and handled through a pointer). With static typing, objects belonging to different types can have different sizes, as long as all objects of the same type have the same size. The compiler infers the size of an object from its type, and therefore knows how to allocate a variable of that type, or move a value of that type. This makes it possible to have unallocated objects larger than one word: unallocated 64-bit floating-point numbers, and unallocated records, in particular. The form,er are crucial for numericalintensive programs. The latter are crucial for languages based on the A-calculus, such as ML, where functions have only one argument and one result, and functions with several arguments or several results are encoded as functions taking or returning records. A compiler may also us,estatic typing information to indicate which register class is best suited for a given object. Most architectures distinguish floating-point registers from general-purpose registers; floating-point operations can only be performed between floatingpoint registers. When an object is statically known to have type float, it is possible to keep this object in a floating-point register, instead of a general-purpose register, so that computation on this object will not require register moves. The typical example of this type-based targeting is the use of different calling conventions for functions of different types: a function with result type float can be compiled to return its result in a given floating-point register, ready to be used by the caller; a function that returns an object of type int will use a given integer register instead. Static typing guarantees that the caller and the callee agree on the types of the arguments and the results, and therefore on their locations.
The compiler uses the type information to select efficient data representations and to minimize boxing coercions REF .
Unboxed objects and polymorphic typing
POPL '92
Computer Science