Hi Talin, Let me ask a question before we go too much further. Currently the argument> to llvm.gcroot must be an alloca instruction. You cannot GEP an internal > field within the alloca and pass it to the gcroot intrinsic. So the entire > alloca is considered a root, even if it has non-pointer fields. My question > is, in this new address-space proposal, are we talking about changing this > so that the garbage collector only "sees" the internal pointer fields within > the alloca, or will it still be able to "see" the entire alloca? This is the > crucial point for me - I've written my GC strategy to deal with complex > allocas, and there are several data types - such as unions - which depend on > this. > > I can probably work around the union issue using methods like you suggest - > that is building some "dummy" type containing a pointer as the long-term > storage format - as long as the GC can still see the entire struct. It's > ugly because it means that my frontend has to know about padding and > alignment and such, issues which I prefer to leave to LLVM to figure out. >Correct me if I am wrong, but to use unions without IR support means you already have to worry about padding.> > But if we change it so that the GC only sees pointers, then I'm dead in the > water. >In the end, the GC should only be seeing pointers anyway - some of whose "pointer-ness" depends on other values (as in the tagged union). I think your method could still work with the GC only seeing pointers (albeit with a little modification) - the only requirement I see that your method imposes on the design of a address-space based GC strategy is to maintain information about the structure (union) containing the pointer, next to the pointer. For this, metadata should work fine. While it is not particularly elegant, I don't see why you would be "dead in the water" - because it could be made to work.> > As far as my suggestion of marking types go, you are right, it doesn't make > sense for most types. It really only matters for structs and pointers. > Imagine if structs had an "isRoot" flag that lived next to "isPacked", which > makes the struct a distinct type. This would be written in IR as "gcroot { > i1, float }" or something like that. The presence of this flag has the same > effect as marking a pointer in the GC address space. Combine that with the > ability to mark SSA values as roots, and my life would get vastly simpler > and my generated code would get about 20% faster :) > >I'm not saying this approach wouldn't work or that it is in any way worse than the address-space method, but I think it would require many more changes to how LLVM handles types. One problem with how you are envisioning it (though not with the idea itself) is that it will probably be beneficial to be able to track multiple, independent types of roots - for example, roots for a long-term heap (where Method, Class, etc. might live) and the normal heap. The address-space method would handle this, but the isRoot() method would have to be extended to handle distinct roots - more like isRoot(int rootId) - which would *really* complicate the type system. -Joshua -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20110308/1e74213c/attachment.html>
On Tue, Mar 8, 2011 at 12:11 PM, Joshua Warner <joshuawarner32 at gmail.com>wrote:> > Hi Talin, > > Let me ask a question before we go too much further. Currently the argument >> to llvm.gcroot must be an alloca instruction. You cannot GEP an internal >> field within the alloca and pass it to the gcroot intrinsic. So the entire >> alloca is considered a root, even if it has non-pointer fields. My question >> is, in this new address-space proposal, are we talking about changing this >> so that the garbage collector only "sees" the internal pointer fields within >> the alloca, or will it still be able to "see" the entire alloca? This is the >> crucial point for me - I've written my GC strategy to deal with complex >> allocas, and there are several data types - such as unions - which depend on >> this. >> >> I can probably work around the union issue using methods like you suggest >> - that is building some "dummy" type containing a pointer as the long-term >> storage format - as long as the GC can still see the entire struct. It's >> ugly because it means that my frontend has to know about padding and >> alignment and such, issues which I prefer to leave to LLVM to figure out. >> > > Correct me if I am wrong, but to use unions without IR support means you > already have to worry about padding. >Well, I sort of do - I estimate which variant of the union is the largest without knowing its exact size. A long time ago I had hoped to make my frontend generate IR that was completely target-independent, and eventually I had to give up that plan. Unions turned out to be one of the few cases where it's impossible to be target-neutral. However, my frontend is "mostly" target independent in that the only piece of information it currently knows about the target is whether pointers are 32 or 64 bits. I should also mention that tagged unions are surprisingly useful in a statically typed language and I would hope that more languages in the future adopt them. A typical example is how Iterators work in my language: // Iterator that returns the sequence of integers 0..N class CountingIterator : Iterator[int] { var index = 0; var limit; def construct(limit:int) { self.limit = limit; } def next -> int or void { if index < limit { return index++; } // return an int return; // return no value } }> >> But if we change it so that the GC only sees pointers, then I'm dead in >> the water. >> > > In the end, the GC should only be seeing pointers anyway - some of whose > "pointer-ness" depends on other values (as in the tagged union). I think > your method could still work with the GC only seeing pointers (albeit with a > little modification) - the only requirement I see that your method imposes > on the design of a address-space based GC strategy is to maintain > information about the structure (union) containing the pointer, next to the > pointer. For this, metadata should work fine. While it is not particularly > elegant, I don't see why you would be "dead in the water" - because it could > be made to work. >Here's a question - if the only way to identify a root is via pointer address space, then where does the metadata go? Adding a metadata field to the pointer type would also greatly complicate LLVM. My worry is that folks will say "well, since every root is a pointer now, we no longer need the metadata argument to describe it's type."> >> As far as my suggestion of marking types go, you are right, it doesn't >> make sense for most types. It really only matters for structs and pointers. >> Imagine if structs had an "isRoot" flag that lived next to "isPacked", which >> makes the struct a distinct type. This would be written in IR as "gcroot { >> i1, float }" or something like that. The presence of this flag has the same >> effect as marking a pointer in the GC address space. Combine that with the >> ability to mark SSA values as roots, and my life would get vastly simpler >> and my generated code would get about 20% faster :) >> >> > I'm not saying this approach wouldn't work or that it is in any way worse > than the address-space method, but I think it would require many more > changes to how LLVM handles types. One problem with how you are envisioning > it (though not with the idea itself) is that it will probably be beneficial > to be able to track multiple, independent types of roots - for example, > roots for a long-term heap (where Method, Class, etc. might live) and the > normal heap. The address-space method would handle this, but the isRoot() > method would have to be extended to handle distinct roots - more like > isRoot(int rootId) - which would *really* complicate the type system. > > I realize that it has drawbacks. I'm mainly just brainstorming.As far as multiple heaps go: There are two classes of heaps we're talking about. The first class are heaps that have different object lifetime policies. Those kinds of heaps should IMHO be managed entirely by the collector without the need for compiler support. In other words, if there's a permgen heap for permanent objects, the collector can store bits in the object header or it can do address comparisons to determine whether an object is in the permgen heap without needing to use the pointer address space field. In fact, using the pointer-address-space property wouldn't work for this, because that's a function of pointer type, and you want the ability to have instances of the same type with different lifetime policies. Objects such as Method and Class will have internal references to instances of String and List that live in the permgen heap along with them, but other objects would have references to String and List in the regular heap. The other class of heap is where you have different classes of memory - RAM and ROM, or NUMA-style shared memory spaces - or where the address space represents some semantic difference that the compiler or optimization passes need to be aware of. These heaps may be garbage collected in addition to whatever other special properties they have. So the property of being garbage collected is (at least for me) a single bit, and orthogonal to whether the object is in a special heap or not. Let me take a step back for a second and think about this thread as a whole. The current LLVM approach to garbage collection requires a division of responsibility between the LLVM libraries and the compilers that call those libraries. As I see it, it's the frontend's job to understand the semantics and structure of data types, and it's LLVM's job to know things like underlying representations and lifetimes of SSA values. The biggest problem that I have with the current system is that garbage collection roots can only live in allocas, not SSA values, so that I am constantly having to load and store values to memory. The second biggest problem is related to the first - since the scope of an alloca root is the entire function (because calls to llvm.gcroot have to be in the first block) there's no way for me to tell LLVM that a root is confined to a given lexical block, so I have to generate extra code to zero out the root even if it's dead. In fact, most roots get assigned three times - zeroed out at the beginning of the function, then set to a value sometime later, and then set back to zero when I'm done with the value. What I like about the current system is that the responsibility for interpreting roots is entirely in my hands, and LLVM can treat the entire alloca as an opaque blob if it wants to. In my compiler I treat stack roots exactly like I treat fields within a heap object - the compiler-generated trace tables are exactly the same, except that in the case of stack roots the offsets are negative and the object base address is the frame pointer. The same function that traces the fields of an object also traces the variables on the stack, including handling complex types such as unions and variable length arrays. (Although the latter never occurs on the stack since alloca only takes constant arguments. But I could imagine a SmallVector type situation where you have some number of pointers, only the first N of which have been initialized.) So when we talk about which solution is more elegant, I think we need to look at the elegance of the whole, not just of the LLVM part. That being said, I admit that there is one downside to sticking with the current approach going forward, which I will explain. In the current system, a large stack root has the same cost as a small one, since both are access via pointer. However, in a future version of LLVM in which SSA roots are automatically spilled to memory during a safe point and reloaded after, a large root will be more expensive than a small one. This means that there will be pressure to make roots as small as possible, so that if a large struct type has roots confined to just a few fields, it would be more efficient to declare just those fields as roots rather than the entire struct. So I agree with you this much: It would be nice if there was a way for marking of roots to be finer-grained than an entire SSA value, *including* being able to associate metadata with that finer-grained portion.> -Joshua >-- -- Talin -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20110308/4449b6d1/attachment.html>
Hi Talin,> Well, I sort of do - I estimate which variant of the union is the largest > without knowing its exact size. A long time ago I had hoped to make my > frontend generate IR that was completely target-independent, and eventually > I had to give up that plan. Unions turned out to be one of the few cases > where it's impossible to be target-neutral. However, my frontend is "mostly" > target independent in that the only piece of information it currently knows > about the target is whether pointers are 32 or 64 bits. > >I still think complete platform independence is something that *all* systems, including LLVM should aspire to, but (probably) never attain.> I should also mention that tagged unions are surprisingly useful in a > statically typed language and I would hope that more languages in the future > adopt them. A typical example is how Iterators work in my language: > > I completely agree - I included them, albeit in a slightly different form,in my own pet language.> } > >> >>> But if we change it so that the GC only sees pointers, then I'm dead in >>> the water. >>> >> >> In the end, the GC should only be seeing pointers anyway - some of whose >> "pointer-ness" depends on other values (as in the tagged union). I think >> your method could still work with the GC only seeing pointers (albeit with a >> little modification) - the only requirement I see that your method imposes >> on the design of a address-space based GC strategy is to maintain >> information about the structure (union) containing the pointer, next to the >> pointer. For this, metadata should work fine. While it is not particularly >> elegant, I don't see why you would be "dead in the water" - because it could >> be made to work. >> > > Here's a question - if the only way to identify a root is via pointer > address space, then where does the metadata go? Adding a metadata field to > the pointer type would also greatly complicate LLVM. My worry is that folks > will say "well, since every root is a pointer now, we no longer need the > metadata argument to describe it's type." >I'm not quite sure what you are asking. I don't know enough about LLVM to tell you how it should be done off the top of my head - but it should just be a matter of attaching the metadata to the instruction that produces the value. In order for this to work, LLVM would have to include the IR instruction that produced the value in the generated stack-root data.> I realize that it has drawbacks. I'm mainly just brainstorming. >Likewise.> > As far as multiple heaps go: There are two classes of heaps we're talking > about. The first class are heaps that have different object lifetime > policies. Those kinds of heaps should IMHO be managed entirely by the > collector without the need for compiler support. >Perhaps that was a bad example - but I'm sure there are valid use cases of where you might want to independently track different types of roots. This is something the address-space solution would handle naturally.> > The other class of heap is where you have different classes of memory - RAM > and ROM, or NUMA-style shared memory spaces - or where the address space > represents some semantic difference that the compiler or optimization passes > need to be aware of. These heaps may be garbage collected in addition to > whatever other special properties they have. So the property of being > garbage collected is (at least for me) a single bit, and orthogonal to > whether the object is in a special heap or not. > > Let me take a step back for a second and think about this thread as a > whole. The current LLVM approach to garbage collection requires a division > of responsibility between the LLVM libraries and the compilers that call > those libraries. As I see it, it's the frontend's job to understand the > semantics and structure of data types, and it's LLVM's job to know things > like underlying representations and lifetimes of SSA values. > > The biggest problem that I have with the current system is that garbage > collection roots can only live in allocas, not SSA values, so that I am > constantly having to load and store values to memory. The second biggest > problem is related to the first - since the scope of an alloca root is the > entire function (because calls to llvm.gcroot have to be in the first block) > there's no way for me to tell LLVM that a root is confined to a given > lexical block, so I have to generate extra code to zero out the root even if > it's dead. In fact, most roots get assigned three times - zeroed out at the > beginning of the function, then set to a value sometime later, and then set > back to zero when I'm done with the value. >This is something that LLVM should handle completely, independent of which solution is chosen - just propagate the liveness info into the generated stack maps. Not being very familiar with the internals of LLVM (I've used it a lot, but not hacked on it), I'm not sure how this would work.> > What I like about the current system is that the responsibility for > interpreting roots is entirely in my hands, and LLVM can treat the entire > alloca as an opaque blob if it wants to. In my compiler I treat stack roots > exactly like I treat fields within a heap object - the compiler-generated > trace tables are exactly the same, except that in the case of stack roots > the offsets are negative and the object base address is the frame pointer. > The same function that traces the fields of an object also traces the > variables on the stack, including handling complex types such as unions and > variable length arrays. (Although the latter never occurs on the stack since > alloca only takes constant arguments. But I could imagine a SmallVector type > situation where you have some number of pointers, only the first N of which > have been initialized.) > > So when we talk about which solution is more elegant, I think we need to > look at the elegance of the whole, not just of the LLVM part. >I agree - but when a little effort can get you *most* of what you (in the general sense) want, IMHO it is almost always preferable to putting tons of work into making it *perfect*.> > That being said, I admit that there is one downside to sticking with the > current approach going forward, which I will explain. In the current system, > a large stack root has the same cost as a small one, since both are access > via pointer. However, in a future version of LLVM in which SSA roots are > automatically spilled to memory during a safe point and reloaded after, a > large root will be more expensive than a small one. This means that there > will be pressure to make roots as small as possible, so that if a large > struct type has roots confined to just a few fields, it would be more > efficient to declare just those fields as roots rather than the entire > struct. >I don't think it is a matter of efficiency - that should be completely up to the spiller making good choices, and the stack maps (perhaps optionally) being smart enough to recognize things in registers.> So I agree with you this much: It would be nice if there was a way for > marking of roots to be finer-grained than an entire SSA value, *including* > being able to associate metadata with that finer-grained portion. > >The main benefit that the address-space method has is that it should be a big improvement over the current solution and it should (as far as I can tell) be relatively simple to implement. -Joshua -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20110308/8fe7583c/attachment.html>