On Wed, Feb 16, 2011 at 4:51 PM, Talin <span dir="ltr"><<a href="mailto:viridia@gmail.com">viridia@gmail.com</a>></span> wrote:<br><div class="gmail_quote"><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">

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.<div><br></div><div>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.)</div>


<div><br></div><div>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.</div>


<div><br></div><div>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.</div><div><br></div>


<div>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.</div>


<div><br></div><div>This approach offers a bunch of advantages that I can think of:</div><div><ul><li>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.</li>


<li>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.</li>


<li>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.</li></ul>


</div><div><div><div><div><div>What do you think?</div><div></div></div></div></div></div></blockquote></div><div><br></div>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.<div>

<br></div><div>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.</div>

<div><br></div><div>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.</div>

<div><br></div><div>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.)</div>

<div><br></div><div>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.</div>

<div><br></div><div>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.</div>

<div><br></div><div><div><div>-- <br>-- Talin<br>
</div></div></div>