Re: Compilers in six hours

Henry G. Baker <hbaker@netcom.com> wrote:
> Generating machine-language that works is not difficult, and in many ways
> easier than generating C (e.g., in C you have to worry about overrunning
> the C compiler's statement length and parser stack limitations, and about
> guaranteeing the proper ordering of side-effects). This is especially
> true if you have a decent assembly macro system to build your own little
> 'mini-machine', which has no overlapped operations, no branch delay slots,
> etc. The hard part, of course, is to generate machine language that
> actually runs faster than the compiled (and optimized) C.
>
> I would imagine that for many students, the problem is that you have to
> know the machine language pretty well before you can generate code in it,
> and many of the students may not be that experienced in assembler.


I did a code-generator of a compiler of a subset of ML and can only say
this is all too true. Generating C code isn't too hard as long as you
don't care about tail-recursion elimination and garbage collection. Of
course, in this case you could use the scheme suggested by Henry somewhere
else, but I didn't know about it at that time (and it forces you to make a
CPS conversion, even though the intermediate language wasn't CPS
converted).


I generated code for the MIPS assembler and it proved very easy: the
assembler took care of delay slots, instruction scheduling and a few
little macro expansions (like multiplies, big immediate constants, etc..).
Moreover, the assembly is very simple: you don't really have to learn it,
just look in the book to find the mnemonic and that's it (I'm serious, the
semantics is very clean and natural).


The only additional step I had to do to generate assembly instead of C was
register allocation, and to make it simpler, I only did register
assignment (if spilling is needed, the compiler crashes (well, actually,
it doesn't crash but loops, looking for a non-existant free register) :-).
Of course, good register allocation isn't easy and precise live-range
analysis can be a problem for some languages, but you can always make
things easy. F.ex, you can have a very conservative live-range analysis,
where every variable is always live.


Aside note: the compiler was written in SML and I think it helped a lot
(compared to C, for instance) because of its type checking and garbage
collection which makes tree manipulation much easier.


Stefan
--

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