[MLton-devel] HiPE/x86 Erlang compiler paper

[Matthew Fluet]

HiPE/x86 Erlang team,

Stephen Weeks (of the MLton compiler team) pointed me to your paper
describing the HiPE/x86 Erlang compiler
(http://www.csd.uu.se/~kostis/Papers/x86.ps.gz). As the primary designer
of MLton's x86 backend, I thought I would comment on our "unusual
arrangement". 

> 	"In MLTon, %esp is the heap pointer and %ebp points to a
> 	simulated call stack. It is not clear to us what the advantage
> 	of this unusual arrangement is."

As you note, MLton uses a simulated call stack.  All arguments (and
returns) for (non-foreign function) function calls are passed via this
simulated call stack.  As you mention in your future improvements,
changing this calling convention to pass some parameters in memory would
benefit tail-call and leaf functions.

There are three distinct reasons for not using %esp to point to this
simulated call stack.

1. the stack grows "backwards" compared to a C stack, so we can't use
     push instructions to fill in arguments and auto increment the stack
     pointer
2. in computing GC masks, variables live across potential GC points are
     allocated stack frame slots; other variables are allocated to a
     global pool of slots.  During register allocation, these slots
     correspond to the spill location of temporaries.  Due to register
     pressure (and the fact that stack slot variables are not passed in
     registers across basic blocks [1]), there are many reads and writes 
     to stack slots.  For reasons beyond my understanding, x86 addresses
     with %esp are one byte longer than addresses with %ebp, so it saves
     code space and nets better instruction cache usage.
3. to make a foreign function call, we must use standard C calling
     conventions.  In order to accomplish this, we save the original value
     of %esp at program start-up and load that before making a foreign
     funcion call and use push instructions to fill in the arguments.
     Because of the reasons outlined in 2, many of these arguments are
     allocated on the simulated stack, so there is extra shuffling of
     registers at a C call if we were to %esp for the simulated stack as
     well.

The reason for using %esp for the frontier is primarily motivated by a
desire to use %esp for something, so it isn't used as a general purpose
register.  Again, one can't use %esp in the index of an address, so there
is unnecessary shuffling if %esp is used for arbitrary temporaries.
Reserving it for the frontier keeps it occupied most of the time, in a
role that doesn't interfere with C calls and doesn't require it to be used
in an index position.  Unfortunately, the heap grows "backwards" compared
to a C stack as well, because it would be nice to use push instructions
for allocation.

There is, however, one caveat for this setup.  Because MLton provides
signal handling, we need a way of indicating to signal handlers that %esp
does not point to a valid C stack.  In Linux, this is accomplished by
the sigaltstack system call.  Recently, when porting MLton to Cygwin, we
discovered that Cygwin does not provide sigaltstack, and we've been forced
to use %edi for the simulated stack pointer.  Removing %esp from the set
of available registers hurts code size because of additional register
pressure and spilling, but had mixed results on execution time.  For the
last set of benchmarks I have, it really hurt vector concatenation
benchmark, but helped a word-count benchmark (because so many C calls were
made that the global invariant of %esp pointing to the C stack was better
than loading the C stack at each call).

Hope this clarifies a few things.

-Matthew Fluet

[1] I've made some progress towards improving the backend by passing both
stack slot variables and variables allocated to the global pool in
registers across basic block boundaries; it's not quite ready for release,
but it alleviates some unecessary loads and stores to stack slots.


_______________________________________________________________

Have big pipes? SourceForge.net is looking for download mirrors. We supply
the hardware. You get the recognition. Email Us: bandwidth@sourceforge.net
_______________________________________________
MLton-devel mailing list
MLton-devel@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/mlton-devel