llvm dev - Apr 2012 - [LLVMdev] Potential Google Summer of Code Applicant

On 4/6/12 2:21 AM, Talin wrote:
> I would really like to see someone work on LLVM's garbage collection 
> support - it hasn't been updated in 4 years, and while there's been
a
> lot of talk about ways that it could be improved, there's been no
action.
That is *sooo* true! :-) I'm one of the authors of an LLVM backend for 
Erlang (ErLLVM [1]); we have tested and measured our backend  and 
noticed that with the current GC infrastructure we see 20-40% 
performance degradation (because of the loads/stores on the stack for 
all gcroots). It is clear to me and the rest of the team that with this 
infrastructure the LLVM might not be suitable for languages with 
explicit garbage collection, like Erlang. I've also studied the way the 
Vmkit project handles GC and they seem to face the same deficiency too.

offtopic: I am working on an email (more like an RFC) with all the 
details and patches to the LLVM project in order to support our Erlang 
backend. I hope I will be able to send it by next week. Note, that we 
have already talked with the Ericsson/OTP team about integrating our 
work in a future release of Erlang/OTP (as a new HiPE backend).

Yiannis

[1]: http://erllvm.softlab.ntua.gr

-- 
Yiannis Tsiouris
Ph.D. student,
Software Engineering Laboratory,
National Technical University of Athens
WWW: http://www.softlab.ntua.gr/~gtsiour

Hi,

I'm currently working for the next 6 months, but I would be very interested
in looking into this. Are there any discussions in this mailing list that would
be useful in finding out more information?

Regards

Michael Thorpe
Internet Services Developer
Netcraft Ltd


-----Original Message-----
From: llvmdev-bounces at cs.uiuc.edu [mailto:llvmdev-bounces at cs.uiuc.edu] On
Behalf Of Yiannis Tsiouris
Sent: 06 April 2012 09:25
To: llvmdev at cs.uiuc.edu
Subject: Re: [LLVMdev] Potential Google Summer of Code Applicant

On 4/6/12 2:21 AM, Talin wrote:
> I would really like to see someone work on LLVM's garbage collection 
> support - it hasn't been updated in 4 years, and while there's been
a
> lot of talk about ways that it could be improved, there's been no
action.
That is *sooo* true! :-) I'm one of the authors of an LLVM backend for
Erlang (ErLLVM [1]); we have tested and measured our backend  and noticed that
with the current GC infrastructure we see 20-40% performance degradation
(because of the loads/stores on the stack for all gcroots). It is clear to me
and the rest of the team that with this infrastructure the LLVM might not be
suitable for languages with explicit garbage collection, like Erlang. I've
also studied the way the Vmkit project handles GC and they seem to face the same
deficiency too.

offtopic: I am working on an email (more like an RFC) with all the details and
patches to the LLVM project in order to support our Erlang backend. I hope I
will be able to send it by next week. Note, that we have already talked with the
Ericsson/OTP team about integrating our work in a future release of Erlang/OTP
(as a new HiPE backend).

Yiannis

[1]: http://erllvm.softlab.ntua.gr

--
Yiannis Tsiouris
Ph.D. student,
Software Engineering Laboratory,
National Technical University of Athens
WWW: http://www.softlab.ntua.gr/~gtsiour

_______________________________________________
LLVM Developers mailing list
LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

Sorting through all of the discussions would be difficult, as the ideas
have morphed over the years. Also, some of the discussion took place
offline at various LLVM dev conferences.

I can summarize the main points here:

The biggest improvement in GC would be to allow SSA values to be declared
as GC roots - currently only alloca values, that is, values in memory, can
be GC roots. This means that frontends need to copy traceable values to
memory before calling any function that might trigger a collection. This
makes the resulting IR complex and inefficient.

Chris's proposal is that we add metadata to the Pointer type (perhaps using
the address space field) to indicate that a pointer is a GC root. Note that
this would not be a replacement for the existing llvm.gcroot intrinsic, but
rather an addition to it - that is, you could choose to use either the
Pointer attribute or the llvm.gcroot intrinsic. The reason for this is that
for some languages, there are non-pointer GC roots (my language has
discriminated unions that sometimes contains pointers and sometimes not.)
These frontends would need to continue to use the existing intrinsics, but
fortunately such cases are fairly rare and this is not a terrible burden.
For most languages, the Pointer attribute would be a much easier way to
deal with roots, since the "root-ness" of a value is simply a property
of
it's type, and so gets carried along with the value automatically.

Thus, in this new scheme, Pointer types which were marked as roots could be
traced regardless of whether they lived within a memory location or a
register. These could be used to generate either stack maps or register
maps. Note that these maps are language-specific and are implemented via a
language-specific plugin, so you would need to update the current API to
deal with items in registers. (An alternative plan is to allow the frontend
to request via a flag that roots be copied to local variables at each safe
point, so that register maps would not be needed. This alternate plan might
be a good first step, and then move on to the more difficult problem of
register maps if the first step is successful.)

The reason why this is difficult is that the presence of garbage collection
roots has a major impact on the optimizer and backend code generators -
certain optimizations can cause the stack map to be incorrect, so these
optimizations must be prevented or compensated for. However, an advantage
is that variables which are optimized away no longer need to be included in
stack maps - something that is not possible with the current approach.

One other limitation of the Pointer approach over the existing llvm.gcroot
system, is that the latter allows complex metadata to be associated with
each root. This is useful in languages that don't use tagged objects, that
is, the type of every object it known at compile time. However, creating a
metadata pointer for every Pointer type would be expensive, so the Pointer
roots would only be used for languages which use tagged objects - which is
fortunately most languages that use GC.

An even more ambitious plan would be to allow structs in SSA values to be
declared as roots, which would be useful for languages like mine. We
wouldn't use register maps for these, since a struct might get
"sliced"
into multiple registers. Instead, the code generator would automatically
spill the struct value to memory during a safe point, and otherwise treat
the struct like the existing llvm.gcroot() intrinsic does. Note that this
is a much harder problem, and would not be needed for languages like Java
or Python where objects are always passed by reference. I wouldn't expect
an initial implementation to attempt to tackle this harder problem.

That would be the biggest improvement that I can think of. There are a few
other minor improvements that I would also like to see:

One would be a set of intrinsics that would allow efficient iteration of
stack frames in an efficient manner. The existing LLVM stack frame
intrinsics are inefficient and cannot be relied upon in many cases.
Basically you'd want 3 intrinsics, which would work on all supported
platforms: The first would return an opaque reference to the current stack
frame; The second would take a stack frame as it's argument and return a
pointer to it's parent stack frame; And the third would take a stack frame
argument and return a base address for the local variables of that frame.
The lanuguage specific runtime would then use this base address, along with
the generated stack maps, to access all of the stack roots for that frame.

An example of how this stack walking is done can be seen here:
http://code.google.com/p/tart/source/browse/trunk/runtime/lib/gc_common.cpp#155However,
this code only works on x86 - the intrinsics that I envision would
work on a much wider set of backend targets.

Note that these items are just a tiny part of a complete collector,
however, the design of LLVM is that each language is supposed to implement
its own collector, and LLVM only supplies the parts that need to be
integrated into the code generator.

I can also suggest ways to test the new features without having to build a
complete garbage collector. For example, one can create a trivial stack
walker that merely counts the number of non-null root pointers, and write
various unit tests that verify that the results are as expected.

On Fri, Apr 6, 2012 at 6:33 AM, Michael Thorpe <mthorpe at netcraft.com>
wrote:
> Hi,
>
> I'm currently working for the next 6 months, but I would be very
> interested in looking into this. Are there any discussions in this mailing
> list that would be useful in finding out more information?
>
> Regards
>
> Michael Thorpe
> Internet Services Developer
> Netcraft Ltd
>
>
> -----Original Message-----
> From: llvmdev-bounces at cs.uiuc.edu [mailto:llvmdev-bounces at
cs.uiuc.edu] On
> Behalf Of Yiannis Tsiouris
> Sent: 06 April 2012 09:25
> To: llvmdev at cs.uiuc.edu
> Subject: Re: [LLVMdev] Potential Google Summer of Code Applicant
>
> On 4/6/12 2:21 AM, Talin wrote:
> > I would really like to see someone work on LLVM's garbage
collection
> > support - it hasn't been updated in 4 years, and while there's
been a
> > lot of talk about ways that it could be improved, there's been no
action.
> That is *sooo* true! :-) I'm one of the authors of an LLVM backend for
> Erlang (ErLLVM [1]); we have tested and measured our backend  and noticed
> that with the current GC infrastructure we see 20-40% performance
> degradation (because of the loads/stores on the stack for all gcroots). It
> is clear to me and the rest of the team that with this infrastructure the
> LLVM might not be suitable for languages with explicit garbage collection,
> like Erlang. I've also studied the way the Vmkit project handles GC and
> they seem to face the same deficiency too.
>
> offtopic: I am working on an email (more like an RFC) with all the details
> and patches to the LLVM project in order to support our Erlang backend. I
> hope I will be able to send it by next week. Note, that we have already
> talked with the Ericsson/OTP team about integrating our work in a future
> release of Erlang/OTP (as a new HiPE backend).
>
> Yiannis
>
> [1]: http://erllvm.softlab.ntua.gr
>
> --
> Yiannis Tsiouris
> Ph.D. student,
> Software Engineering Laboratory,
> National Technical University of Athens
> WWW: http://www.softlab.ntua.gr/~gtsiour
>
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>


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