Re: Mercury front-end

[Fergus Henderson <fjh at cs dot mu dot oz dot au>]

On 26-Jan-2001, Geert Bosch <bosch@gnat.com> wrote:
> On Fri, 26 Jan 2001 08:27:52 +1100, Fergus Henderson wrote:
> 
>   On 02-Jan-2001, Fergus Henderson <fjh@cs.mu.OZ.AU> wrote:
>   > I've implemented an initial version of a Mercury front-end for GCC.
>   
>   ... and it now bootstraps :->
> 
> A new GCC compiler is born! Congratulations! :-) Do you see any
> difference in code generated with your new front-end versus the old
> one, or do you get pretty much the same mapping as you did before?

Well, that depends on exactly what you mean by "the old one".
The Mercury compiler has two different back-ends that compile to C.
The code generated with Mercury GCC back-end is almost the same as
that generated with the new "high-level" C back-end, but it is quite
different from the code generated by the original "low-level" C back-end.

The original "low-level" C back-end of the Mercury compiler was based
on an abstract machine, with its own registers and stacks; we
generated code for this abstract machine and implemented the abstract
machine instructions using C macros.  The macros had alternative
definitions depending on whether we were compiling to GNU C, or to
portable ANSI C.  For GNU C, the most frequently accessed abstract
machine registers were mapped to real registers using GNU C's global
register variables feature.  Tail calls were mapped to GOTO
instructions in the abstract machine, which were implemented using
inline assembler labels and GNU C's computed goto extension to jump
from the middle of one C function to the middle of another.  This
approach was of course not officially supported by GNU C, was rather
fragile, and made porting more difficult than But it did work, and it
had the advantage over competing alternatives of (1) being efficient;
(2) supporting tail calls (in 1994!); and (3) being relatively
portable (a lot more so than writing our own native code compiler,
for example).

More recently, we've developed a new back-end for the Mercury compiler
that compiles to a fairly high-level intermediate representation based
on an abstraction of various imperative/OOP languages (C, C++, Java,
and the like).  We then convert this representation to either C,
MS IL (the Microsoft.NET Intermediate Language), Java, or GCC trees.

The assembler code generated by the high-level C back-end and the GCC
back-end is very similar; not exactly the same, but close enough that
I was able to use `diff' on the generated assembler files to help find
bugs.  But that is after I made a couple of changes to the C back-end
to make it more closely match the GCC back-end, in particular using
__builtin_{set,long}jmp and changing the way we generate switches so
that the default case comes first (to better optimize switches with
unreachable default cases).

Note that this is without any information being passed from the
Mercury front-end to the GCC back-end about tail calls; I plan to
do better in that regard.

Compared to the original low-level C back-end, the code generated by
the high-level C back-end is quite different; sometimes better,
sometimes worse.  For the Mercury compiler itself, the new high-level
C back-end beat the low-level back-end by about 10% on Alpha but lost
by a similar amount on x86, if I recall correctly.

The low-level C back-end does a much better job than GCC on a few
optimizations that are sometimes important for the kind of code that
we generate.  One of them is delaying/avoiding stack frame creation.
For functions like

	void foo(arg) {
		if (arg == 0) {
			... base case ...
		} else {
			... recursive case that needs a stack frame ...
		}
	}

GCC will (AFAIK) always create a stack frame for every call to foo(),
whereas for the equivalent Mercury code the Mercury compiler's
"low-level C" back-end will avoid creating a stack frame for calls
which use the base case, if the base case doesn't need a stack frame.

-- 
Fergus Henderson <fjh@cs.mu.oz.au>  |  "I have always known that the pursuit
                                    |  of excellence is a lethal habit"
WWW: <http://www.cs.mu.oz.au/~fjh>  |     -- the last words of T. S. Garp.