Re: Reduced Machine Description
Mon, 27 Feb 89 09:48:31 EST

          From comp.compilers

Related articles
Reduced Machine Description martins@rwthinf.uucp (1989-02-22)
Re: Reduced Machine Description (1989-03-15)
Re: Reduced Machine Description (1989-03-02)
Re: Reduced Machine Description (1989-02-27)
| List of all articles for this month |

Date: Mon, 27 Feb 89 09:48:31 EST

martins@rwthinf.uucp (Martin Schoenert) writes:

> Suppose I want to write a new compiler. Portability is a very
>important goal, maximum speed is not. The language is unspecified, I tend to
>think of a compiler that would support multiple front ends.
>. . . (descriptions of UCSD and GNU approaches) . . .
> My idea is a reduced machine description. It consists of the
>following functions, which emit corresponding instructions for say a MC68000:
>. . . (description of simple machine description approach) . . .
> Has anyone tried this approach ? Has anyone rejected is as too
>expensive ? How much of the maximal performance (say defined by the speed
>of the code generated by the GNU C compiler) of a MC68000 or a VAX could
>such a compiler achieve ? For C or similar languages ? For Lisp ?

The approach you describe is very similar to the 'machine class' work
in which similar machines are grouped together and the differences between
them are described using a short machine description of the kind you propose.
This has been tried with some success by at least two different people using
different underlying methods of code selection. One such approach I know
of is Kessler's PhD work which I believe uses Cattel's method for code selection:

        Kessler, R.R.; COG: An Architectural-Description-Driven Compiler Generator;
        Ph.D. Thesis, Department of Computer Science, University of Utah, 1981.

The second one I am much more familiar with. It is an attempt to provide
portability using massive simplification of the code selection process, and
employs a two-stage code selection using simple decision trees. This method has
been shown to achieve the simplicity of machine description you are asking for,
while losing less than 5% in generated code quality over production code
generators for the same language:

        Cordy, J.R.; An Orthogonal Model for Code Generation;
        Ph.D. Thesis, Department of Computer Science, University of Toronto,
        Technical Report CSRI-177, Computer Systems Research Institute,
        University of Toronto, January 1986 (PhD thesis).

A short summary of this work appears in:

        Cordy, J.R.; Code Generation Using an Orthogonal Model;
        Proc. HICSS-20 Hawaii International Conference on System Sciences,
        Kona, Hawaii, January 1987.

And more experience with the technique is described by:

        Hall C.B.; A Production Quality Machine-Independent Compiler for Turing;
        M.Sc. Thesis, Dept. of Computer Science, University of Toronto, 1986.

        Eliot, N.; Automatic Derivation of Orthogonal Code Generators from
        Applicative Specifications; M.Sc. thesis, Dept. Computing and Information
        Science, Queen's University, July 1988.

I'm sure there are other people who have explored code generation with
portability as the prime goal and have used the machine class idea also,
but such practical work is difficult to publish because the accepted
measure for success in code generation is optimality rather than portability.

Jim Cordy
Queen's University at Kingston, Canada
Cordy@QueensU.CA cordy@qucis.bitnet

Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.