[Vm-dev] Compiling with Continuations and LLVM

Ben Coman btc at openinworld.com
Fri Jun 12 15:55:42 UTC 2020


Could Smalltalk VM be defined as a "Continuation Passing Style", or is that
still more the realm of more functional languages?

I vaguely remember one of the arguments against using LLVM is that its IR
was Single Static Assignment that wasn't well suited for continuations and
non-local returns.  I bumped into the following article...

"Compiling with Continuations and LLVM"
https://arxiv.org/pdf/1805.08842.pdf

...and wondered if it addresses any of those concerns, and refresh myself
on other impediments to making use of the code-optimisation parts of LLVM.
A few extracts...

While LLVM provides a relatively easy path to high-quality native code, its
design is based on a traditional runtime model which is not well suited to
alternative compilation strategies used in high-level language compilers,
such as the use of heap-allocated continuation closures. This paper
describes a new LLVM-based backend that supports heap-allocated
continuation closures, which enables constant-time callcc and
very-lightweight multithreading.
...
The LLVM backend for the MLton SML compiler uses trampolining to avoid the
issues with TCO [23]. As far as we know, no one has successfully
implemented heap-allocated first-class continuations with LLVM. In the
remainder of the paper, we describe a new calling convention that we have
added to LLVM, how we handle the GC interface, and how we support capturing
continuations to support preemption
...
In preparation for generating native code that uses bump allocation in the
heap, we insert heap-limit tests into the CFG representation. [...]  The
limit tests introduce continuation captures that are not present in the
original program, which can be used to implement preemptive scheduling
 ...
Most functional languages use tail recursion to express loops and, thus,
require that tail calls do not grow the stack. In limited circumstances,
LLVM can meet this requirement, but even when LLVM is able to apply TCO to
a call, there is extra stack-management overhead on function entry and
exit. This extra overhead is bad enough for implementations that rely on
traditional stacks, but it is prohibitively expensive for implementations
that use CPS and heap-allocated continuations.  [...] Our solution to this
problem is to add a new calling convention, which we call
Jump-With-Arguments (JWA), to LLVM. This calling convention has the
property that it uses all of the available hardware registers and that no
registers are preserved by either the caller or callee.  [...] we mark
every function with the naked attribute, which tells the code generator to
completely skip the emission of a function prologue and epilogue

[This sounds a bit like how our VM works...]
We use the technique developed for supporting asynchronous signals in
SML/NJ [26], which limits preemption to safe points where all live values
are known.   We store the heap limit pointer in memory, which means that we
can set it to zero when we need to force a heap-limit check to fail.

Cheers, Ben
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.squeakfoundation.org/pipermail/vm-dev/attachments/20200612/f1ad4bf3/attachment.html>


More information about the Vm-dev mailing list