I think I'm one of the few people actually using LLVM's support for garbage collection, and so far I've found it very difficult to generate code that uses llvm.gcroot() correctly. In the current scheme, it is the frontend's responsibility to insure that any intermediate SSA values containing references to garbage collectible objects are copied to stack variables so that the GC strategy can calculate offsets for them. It is also the frontend's responsibility to reload those values after a sync point, since the collector may have moved them around. An additional chore is creating all of the allocas for those roots, which have to be in the first block of the function (because that's where allocas go according to my understanding of the rules of IR.) What this means is that the frontend is forced to generate very inefficient IR, with dozens of alloca slots at the beginning of the function, each marked as a root. It also has to initialize each of these roots to a known value, even if the root is only "live" for a very small part of the CFG. This is because currently there's no way for the frontend to tell LLVM that a given root has a limited lifespan (since calls to llvm.gcroot also have to be in the first block), and so you have to take a conservative approach and treat every root as if it were live for the entire function. It seems to me that "gc-rootness" should not be an aspect of an alloca, as it currently is now, but rather an aspect of a Value, similar to the way llvm.dbg.value() works. Let's imagine a new intrinsic, llvm.gcvalue(), which takes as its arguments a Value and a metadata pointer, and returns that same value as its result. The frontend can "wrap" any value, of any type, with llvm.gcvalue(), which is a signal to LLVM that this value is a garbage collection root. It would then be the responsibility of LLVM's code generator (or possibly some lowering pass) to insure that this value lives on the stack during sync points, and is reloaded after a sync point if it is still needed. During a sync point, these values would be treated exactly the way llvm.gcroot works today - that is, they live on the stack, and the GCStrategy gets passed a list of stack offsets and metadata pointers. The main difference is that only the values that are actually 'live' during the sync point are lowered from SSA values to allocas. This approach offers a bunch of advantages that I can think of: - LLVM knows much more about the liveness of values than the frontend does, and could compute a much more optimal and minimal stack map for each sync point. That is, two variables whose lifetimes do not overlap can use the same stack location for their roots to be stored in, and the stack maps generated by the GCStrategy would reflect this. - If at some future time LLVM supports register maps for garbage collection, you would not have to update your frontend. Since we're marking values, not stack slots, the frontend doesn't have to care where the variable is stored, so all frontends can take advantage of improvements in the representation of stack maps. - Writing frontends gets a lot easier, since the frontend is no longer responsible for generating and initializing allocas for every root. It also means a lot fewer opportunities for generating incorrect code. What do you think? -- -- Talin -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20110216/b6ed8c13/attachment.html>
On Wed, 2011-02-16 at 16:51 -0800, Talin wrote:> [..] the frontend is forced to generate very inefficient IR, with > dozens of alloca slots at the beginning of the function, each marked > as a root. It also has to initialize each of these roots to a known > value, even if the root is only "live" for a very small part of the > CFG. This is because currently there's no way for the frontend to tell > LLVM that a given root has a limited lifespan (since calls to > llvm.gcroot also have to be in the first block), and so you have to > take a conservative approach and treat every root as if it were live > for the entire function. [..]I can confirm this observation. The generated code is clearly suboptimal, and it gets even worse if one tries to do live-precise garbage collection where the gcroot'ed alloca-slot no longer used must be explicitly assigned a null value. On my list processing micro-benchmarks these effects incur a performance hit of approximately 20%-30% compared to a manually crafted asm code, and that is including the overhead of the garbage collector.> It seems to me that "gc-rootness" should not be an aspect of an > alloca, as it currently is now, but rather an aspect of a Value [..]I'ld second that. -- ; mailto:cessu at iki.fi http://www.iki.fi/~cessu http://cessu.blogspot.com ((lambda(a) (a a((lambda(a)(lambda()(set! a(+ a 1))a))1)))(lambda(a c) ((lambda(b) (newline)(write b)(a a((lambda(c)(lambda()(c c)))(lambda(a) ((lambda(c) (if(=(modulo c b)0)(a a)c))(c))))))(c)))) ; Scheme me!
On Wed, 2011-02-16 at 16:51 -0800, Talin wrote:> > This approach offers a bunch of advantages that I can think of: > * LLVM knows much more about the liveness of values than the > frontend does, and could compute a much more optimal and > minimal stack map for each sync point. That is, two variables > whose lifetimes do not overlap can use the same stack location > for their roots to be stored in, and the stack maps generated > by the GCStrategy would reflect this. > * If at some future time LLVM supports register maps for garbage > collection, you would not have to update your frontend. Since > we're marking values, not stack slots, the frontend doesn't > have to care where the variable is stored, so all frontends > can take advantage of improvements in the representation of > stack maps. > * Writing frontends gets a lot easier, since the frontend is no > longer responsible for generating and initializing allocas for > every root. It also means a lot fewer opportunities for > generating incorrect code. > What do you think?I can't speak to the implementation, but as a potential user of this facility I think this approach is definitely preferable to the current one. The IR that the Open Dylan compiler is generating LLVM code from is almost SSA already, and I don't want to allocate stack slots for everything just for GC maps. -Peter S. Housel- housel at acm.org
On Wed, Feb 16, 2011 at 4:51 PM, Talin <viridia at gmail.com> wrote:> I think I'm one of the few people actually using LLVM's support for garbage > collection, and so far I've found it very difficult to generate code that > uses llvm.gcroot() correctly. > > In the current scheme, it is the frontend's responsibility to insure that > any intermediate SSA values containing references to garbage collectible > objects are copied to stack variables so that the GC strategy can calculate > offsets for them. It is also the frontend's responsibility to reload those > values after a sync point, since the collector may have moved them around. > An additional chore is creating all of the allocas for those roots, which > have to be in the first block of the function (because that's where allocas > go according to my understanding of the rules of IR.) > > What this means is that the frontend is forced to generate very inefficient > IR, with dozens of alloca slots at the beginning of the function, each > marked as a root. It also has to initialize each of these roots to a known > value, even if the root is only "live" for a very small part of the CFG. > This is because currently there's no way for the frontend to tell LLVM that > a given root has a limited lifespan (since calls to llvm.gcroot also have to > be in the first block), and so you have to take a conservative approach and > treat every root as if it were live for the entire function. > > It seems to me that "gc-rootness" should not be an aspect of an alloca, as > it currently is now, but rather an aspect of a Value, similar to the way > llvm.dbg.value() works. > > Let's imagine a new intrinsic, llvm.gcvalue(), which takes as its arguments > a Value and a metadata pointer, and returns that same value as its result. > The frontend can "wrap" any value, of any type, with llvm.gcvalue(), which > is a signal to LLVM that this value is a garbage collection root. It would > then be the responsibility of LLVM's code generator (or possibly some > lowering pass) to insure that this value lives on the stack during sync > points, and is reloaded after a sync point if it is still needed. During a > sync point, these values would be treated exactly the way llvm.gcroot works > today - that is, they live on the stack, and the GCStrategy gets passed a > list of stack offsets and metadata pointers. The main difference is that > only the values that are actually 'live' during the sync point are lowered > from SSA values to allocas. > > This approach offers a bunch of advantages that I can think of: > > - LLVM knows much more about the liveness of values than the frontend > does, and could compute a much more optimal and minimal stack map for each > sync point. That is, two variables whose lifetimes do not overlap can use > the same stack location for their roots to be stored in, and the stack maps > generated by the GCStrategy would reflect this. > - If at some future time LLVM supports register maps for garbage > collection, you would not have to update your frontend. Since we're marking > values, not stack slots, the frontend doesn't have to care where the > variable is stored, so all frontends can take advantage of improvements in > the representation of stack maps. > - Writing frontends gets a lot easier, since the frontend is no longer > responsible for generating and initializing allocas for every root. It also > means a lot fewer opportunities for generating incorrect code. > > What do you think? >So a few additional thoughts: I think that it would be best to keep the existing llvm.gcroot() call in addition to having llvm.gvcalue(). llvm.gcroot() would be used for marking allocas as roots, and llvm.gcvalue() would mark SSA values as roots. In fact, if I could go back in time, I would rename them to correspond exactly with the llvm.dbg intrinsics. So in addition to llvm.dbg.declare() and llvm.dbg.value(), we'd also have llvm.gc.declare() and llvm.gc.value(), with analogous uses. Note that it is important that the LLVM GC intrinsics should not assume that the their arguments are pointers, as they could in some cases be structs or arrays that contain pointers. LLVM should make no assumptions about the internal structure of a GC root, that is an issue for the language's GCStrategy pass to worry about - typically the frontend will use the metadata argument to communicate the structure of a root to the GCStrategy. The only thing that LLVM has to guarantee is that during a sync point, it will be possible to associate each live root with an address in memory somewhere. As far as implementation goes, I'm assuming that there would be some pass that converts llvm.gcvalue() intrinsics into llvm.gcroot() intrinsics by temporarily storing the the root into an alloca and then reloading it as needed. (Actually you would probably want something richer than the current llvm.gcroot that allows an explicit begin and end so that information about liveness can be preserved. How about llvm.gc.beginroot() intrinsic to indicate that a given alloca should be considered a root starting at that point in the CFG, and llvm.gc.endroot() to indicate that the specified root no longer needs to be considered a root. This is much better than the current method of assigning NULL to a root, as it accommodates non-pointer roots, and avoids the extra pointer store which is not needed in many cases.) What is unclear to me is exactly when this should occur relative to other passes, but I think what you would want to do is perform optimization and liveness analysis first - thereby eliminating potentially dead roots before they are converted to memory locations. Unfortunately, I can't say too much about this, as I am not a backend person - I know very little about optimization and code generation in general or LLVM's backend passes in particular. There would also need to be some way to tell the code generator not to reload values after a sync point if the collector doesn't require it, such as a mark-and-sweep or other non-copying algorithm. The most straightforward way to handle this would be as an argument to the pass that does the lowering of llvm.gcvalue intrinsics. -- -- Talin -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20110217/d7f12ee5/attachment.html>
On Thu, Feb 17, 2011 at 1:07 PM, Talin <viridia at gmail.com> wrote:> On Wed, Feb 16, 2011 at 4:51 PM, Talin <viridia at gmail.com> wrote: > >> I think I'm one of the few people actually using LLVM's support for >> garbage collection, and so far I've found it very difficult to generate code >> that uses llvm.gcroot() correctly. >> >> In the current scheme, it is the frontend's responsibility to insure that >> any intermediate SSA values containing references to garbage collectible >> objects are copied to stack variables so that the GC strategy can calculate >> offsets for them. It is also the frontend's responsibility to reload those >> values after a sync point, since the collector may have moved them around. >> An additional chore is creating all of the allocas for those roots, which >> have to be in the first block of the function (because that's where allocas >> go according to my understanding of the rules of IR.) >> >> What this means is that the frontend is forced to generate very >> inefficient IR, with dozens of alloca slots at the beginning of the >> function, each marked as a root. It also has to initialize each of these >> roots to a known value, even if the root is only "live" for a very small >> part of the CFG. This is because currently there's no way for the frontend >> to tell LLVM that a given root has a limited lifespan (since calls to >> llvm.gcroot also have to be in the first block), and so you have to take a >> conservative approach and treat every root as if it were live for the entire >> function. >> >> It seems to me that "gc-rootness" should not be an aspect of an alloca, as >> it currently is now, but rather an aspect of a Value, similar to the way >> llvm.dbg.value() works. >> >> Let's imagine a new intrinsic, llvm.gcvalue(), which takes as its >> arguments a Value and a metadata pointer, and returns that same value as its >> result. The frontend can "wrap" any value, of any type, with llvm.gcvalue(), >> which is a signal to LLVM that this value is a garbage collection root. It >> would then be the responsibility of LLVM's code generator (or possibly some >> lowering pass) to insure that this value lives on the stack during sync >> points, and is reloaded after a sync point if it is still needed. During a >> sync point, these values would be treated exactly the way llvm.gcroot works >> today - that is, they live on the stack, and the GCStrategy gets passed a >> list of stack offsets and metadata pointers. The main difference is that >> only the values that are actually 'live' during the sync point are lowered >> from SSA values to allocas. >> >> This approach offers a bunch of advantages that I can think of: >> >> - LLVM knows much more about the liveness of values than the frontend >> does, and could compute a much more optimal and minimal stack map for each >> sync point. That is, two variables whose lifetimes do not overlap can use >> the same stack location for their roots to be stored in, and the stack maps >> generated by the GCStrategy would reflect this. >> - If at some future time LLVM supports register maps for garbage >> collection, you would not have to update your frontend. Since we're marking >> values, not stack slots, the frontend doesn't have to care where the >> variable is stored, so all frontends can take advantage of improvements in >> the representation of stack maps. >> - Writing frontends gets a lot easier, since the frontend is no longer >> responsible for generating and initializing allocas for every root. It also >> means a lot fewer opportunities for generating incorrect code. >> >> What do you think? >> > > So a few additional thoughts: I think that it would be best to keep the > existing llvm.gcroot() call in addition to having llvm.gvcalue(). > llvm.gcroot() would be used for marking allocas as roots, and llvm.gcvalue() > would mark SSA values as roots. > > In fact, if I could go back in time, I would rename them to correspond > exactly with the llvm.dbg intrinsics. So in addition to llvm.dbg.declare() > and llvm.dbg.value(), we'd also have llvm.gc.declare() and llvm.gc.value(), > with analogous uses. > > Note that it is important that the LLVM GC intrinsics should not assume > that the their arguments are pointers, as they could in some cases be > structs or arrays that contain pointers. LLVM should make no assumptions > about the internal structure of a GC root, that is an issue for the > language's GCStrategy pass to worry about - typically the frontend will use > the metadata argument to communicate the structure of a root to the > GCStrategy. The only thing that LLVM has to guarantee is that during a sync > point, it will be possible to associate each live root with an address in > memory somewhere. > > As far as implementation goes, I'm assuming that there would be some pass > that converts llvm.gcvalue() intrinsics into llvm.gcroot() intrinsics by > temporarily storing the the root into an alloca and then reloading it as > needed. (Actually you would probably want something richer than the current > llvm.gcroot that allows an explicit begin and end so that information about > liveness can be preserved. How about llvm.gc.beginroot() intrinsic to > indicate that a given alloca should be considered a root starting at that > point in the CFG, and llvm.gc.endroot() to indicate that the specified root > no longer needs to be considered a root. This is much better than the > current method of assigning NULL to a root, as it accommodates non-pointer > roots, and avoids the extra pointer store which is not needed in many > cases.) > > What is unclear to me is exactly when this should occur relative to other > passes, but I think what you would want to do is perform optimization and > liveness analysis first - thereby eliminating potentially dead roots before > they are converted to memory locations. Unfortunately, I can't say too much > about this, as I am not a backend person - I know very little about > optimization and code generation in general or LLVM's backend passes in > particular. > > There would also need to be some way to tell the code generator not to > reload values after a sync point if the collector doesn't require it, such > as a mark-and-sweep or other non-copying algorithm. The most straightforward > way to handle this would be as an argument to the pass that does the > lowering of llvm.gcvalue intrinsics. >Thinking about it even more, here's a short summary of what I would propose: - *llvm.gc.value*(value, metadata) - marks an SSA value as a garbage collection root. This remains in effect for the lifetime of the SSA value. - *llvm.gc.declare*(alloca, metadata) - marks an alloca as a garbage collection root. This intrinsic tells LLVM that it should start treating the alloca as a GC root from that point in the CFG onward. - *llvm.gc.undeclare*(alloca) - tells LLVM that the alloca should no longer be considered a GC root. If llvm.undeclare() is never called, then the alloca is treated as a root until the end of the function. One other thing I thought of was that it would be convenient to declare function parameters with llvm.gc.value(). However, I can get around not having that as a feature. -- -- Talin -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20110217/922a0159/attachment.html>