3 ms·
This is very interesting, because it's extremely similar to the design that we need for Rust. We need: * A generational GC, preferably bump-allocating so that
by pcwalton 14y ago
This is very interesting, because it's extremely similar to the design that we need for Rust. We need:
* A generational GC, preferably bump-allocating so that we can win on allocation-heavy workloads.
* A non-thread-safe GC, because all GC'd data is local to a single task in Rust (and we enforce this in the type system).
* A precise GC, because (a) we don't want accidental or malicious leaks due to misinterpreting non-pointers as pointers; and (b) because we need precise GC metadata to clean up shared data and run destructors when tasks fail.
* An incremental GC, because minimizing pause times is absolutely critical for browsers.
* A non-copying GC, because LLVM doesn't currently support copying GC satisfactorily (i.e. when allowing pointers to live in registers). Fixing this would require a significant portion of all target code to be rewritten.
Also of particular interest is the ability for individual allocation sites to choose to bump allocate only, in the interests of performance (but at the expense of fragmentation). This could potentially allow Rust programmers to fine-tune their allocation behavior and trade performance for fragmentation when it makes sense to do so.
Very cool, and I'll be sure to keep an eye on this.
- Raphael_Amiard 14y ago> A non-copying GC, because LLVM doesn't currently support copying GC satisfactorily This is a shame that this is so badly documented. I stumbled upon this way after having coded the whole code generator of my Z3 project (https://github.com/raph-amiard/Z3 https://github.com/raph-amiard/Z3 - Ocaml bytecode -> LLVM compiler). The fact that you have to explicitly handle live roots with stacks instructions defeats a lot of the purpose of LLVM IR.
- pcwalton 14y agoI've got a bunch of code in a branch to allow register roots: https://github.com/pcwalton/llvm/tree/noteroots-ir https://github.com/pcwalton/llvm/tree/noteroots-ir It just automatically roots live values that are pointers in a nonzero addrspace. Still doesn't support copying GC, and only works in the fast instruction selector at the moment, but it goes a long way toward making GC performant in LLVM.
- cwzwarich 14y agoThe fast instruction selector only supports some constructs, whereas others are handled by fallback to the standard SelectionDAG instruction selection. In order to use this, do you have to ensure that you never trigger any of these fallbacks?
- pcwalton 14y agoYes. This is just for now, as fast isel is much easier to work with. I have other branches that implement most of the SelectionDAG support needed as well, but they aren't updated to the most recent work.
- rayiner 14y agoThis sounds like a perfect fit for you guys: http://www.hpl.hp.com/techreports/Compaq-DEC/WRL-91-8.pdf http://www.hpl.hp.com/techreports/Compaq-DEC/WRL-91-8.pdf It's the same algorithm used in SBCL (in non-incremental form), and in Dalvik. It's a good fit for LLVM because it's mostly precise. I.e. it scans the stack and registers conservatively, and prevents objects referred-to from those roots from moving, but scans everything else precisely. It's also quite simple to implement, as far as garbage collectors go. I'm working on an extension of the algorithm to support local heaps that can be collected independently of each other. The flexibility of the mostly-copying algorithm is hard to beat for stuff like this.
- pcwalton 14y agoUnfortunately, we need precise stack and register maps because we have pointers into the exchange heap, which are collected eagerly. If the GC tries to follow those, then it'll crash. At the same time, we have to store a liveness-accurate stack map of those pointers so that they can be collected during unwinding.
- rayiner 14y agoInteresting... If you have precise stack and register maps, why does the collector need to be nonmoving?
- pcwalton 14y agoLLVM code generation passes can introduce any number of register-to-register moves and perform arbitrary arithmetic that we don't track. We have to be able to find all derived pointers so we can write those into the stack map and update register/stack locations if we move an object. The right solution is to have MachineInstr-level getelementptr instructions, so that we can discover all derived pointers and copies from a GC root after codegen passes are done. Right now, getelementptr instructions get lowered into "add"/"sub"/"mul"/"lea"/etc instructions too early and we can't track them. What we can do relatively easily (with the series of patches I've been working on) is to track one instance of each GC root across a call (basically with a fake instruction after each call for each root that represents a virtual "use" of that root). That we can at least find the pointers.
- BruceM 14y agoHave you or Mike Pall looked at the Memory Pool System from Ravenbrook: http://www.ravenbrook.com/project/mps/ http://www.ravenbrook.com/project/mps/ ? This used to be the GC at Harlequin and is still used today in some commercial projects (and by OpenDylan on some platforms). I've been talking to them about re-licensing under something more liberal and there's hope that that might happen. (If others expressed a similar interest, it might help.) It is in need of some love: * Support x86_64 * Support ARM * Support threads on OS X * Compilation and/or crash issues on modern Linux I'd personally like to see some other improvements to the build system and have started on a reworking of the documentation into something more cohesive ...
- carterschonwald 14y agoYou might want to look at how ghc does copying gc via its llvm backend
- pcwalton 14y agoAccording to what I've read, in GHC there are only four STG registers that are mapped to fixed registers in the x86 backend (and only one of them can contain a value). All roots are guaranteed to be either in this STG register or in the STG stack, which is kept separate from the C stack and is tagged with pointer/nonpointer info. This is certainly an option, but it seems suboptimal to me; we want LLVM to have the freedom to assign registers as it likes.