[LLVMdev] Improving Garbage Collection

Talin viridia at gmail.com
Thu Jul 7 17:13:29 PDT 2011

On Thu, Jul 7, 2011 at 2:25 PM, Cameron Zwarich <zwarich at apple.com> wrote:

> On Jul 6, 2011, at 3:24 PM, Talin wrote:
> *Overall Proposal: Support marking SSA values as roots (an evolutionary
> approach)*
> My proposal consists of three rather significant changes to LLVM:
>    - Allow frontends to mark SSA values - or even portions of SSA values -
>    as stack roots.
>    - For alloca roots, add a way to communicate to LLVM when a root goes
>    out of scope.
>    - Transfer the responsibility for copying stack roots to memory, from
>    the frontend to the LLVM code generators.
> Let me take the last point first.
> *Proposal Pt 3: **Copying Stack Roots to Memory*
> The LLVM code generators and analysis passes have a much more thorough
> knowledge of SSA value lifetimes than frontends do, and therefore could
> avoid spilling and reloading of values when it wasn't needed. So the LLVM
> libraries should take over the job of creating local allocas for holding SSA
> values during a safe point, as well as the job of copying those SSA values
> to those allocas.
> Of course, generating "optimal" code (as outlined in the previous section)
> would require a lot of work to the backends. But we don't need to do that
> right away. The first goal should be a "conservative, pessimistic"
> implementation that's no better or worse than what we have today (other than
> being far easier to use.) It might be possible to do this as some sort of
> stand-alone transformation/lowering pass.
> This is what I mean by an evolutionary approach - come up with the right
> interface between the frontends and LLVM that enables us to gradually move
> towards that eventual goal.
> The initial step of your evolutionary approach sounds basically equivalent
> to what is possible today. When you try to go beyond that you will run into
> a lot of issues, since the backend is untyped and doesn't even distinguish
> between pointers and integers. The closest thing we have to tracking
> liveness of SSA values throughout the backend is debug info, which is
> frequently incorrect (although usually not due to the code generator
> itself).
> Who is going to implement support for all of this in the code generator
> passes and maintain it? Will GC compatibility be a requirement for any
> further improvements in code generation?
> That's really the key question. Most of the developers who are paid to work
on LLVM are doing so in support of Clang, which doesn't need this feature.
And language experimenters generally don't have time to work on their own
language and at the same time become familiar enough with the LLVM code
generator passes to do useful work.

It's kind of a chicken and egg problem: Managed language creators aren't
attracted to LLVM because it lacks certain features - they are far more
likely to choose the JVM as a development platform (as seen in the case of
Scala, Groovy, and many others). Conversely, the lack of customers for those
features in LLVM makes it difficult to justify putting significant effort
into building and maintaining them. This is what I meant when I said that
the LLVM community lacks momentum in certain areas.

However, what I'm attempting to do is at least get some sort of consensus on
what we'd *like* to have happen, even if we don't yet have someone available
to do the work. If some GSoC student showed up tomorrow and volunteered to
do all this, I don't think we'd be in agreement as to what we'd want them to

I would say that first and foremost, let's come up with some scheme that
allows types, rather than values, to be marked as roots, and which doesn't
impose a huge cost on users that don't need GC. Pretty much everything else
is contingent on that. I suggested several approaches, but I'm sure that
there are people on this list who have much better ideas than mine.

> Cameron

-- Talin
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20110707/252fd228/attachment.html>

More information about the llvm-dev mailing list