On Mon, Mar 7, 2011 at 9:35 AM, 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;">
<div class="im">On Mon, Mar 7, 2011 at 4:08 AM, nicolas geoffray <span dir="ltr"><<a href="mailto:nicolas.geoffray@gmail.com" target="_blank">nicolas.geoffray@gmail.com</a>></span> wrote:<br></div><div class="gmail_quote">
<div class="im"><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
Hi Talin,<br><br><div class="gmail_quote"><div>On Sat, Mar 5, 2011 at 6:42 PM, Talin <span dir="ltr"><<a href="mailto:viridia@gmail.com" target="_blank">viridia@gmail.com</a>></span> wrote:<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<div><div><div class="gmail_quote"><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
</blockquote></div><div><br></div></div></div>So I've been thinking about your proposal, that of using a special address space to indicate garbage collection roots instead of intrinsics.</blockquote><div><br></div></div>
<div>
Great!</div><div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div><br></div><div>To address this, we need a better way of telling LLVM that a given variable is no longer a root. </div>
</blockquote><div><br></div></div><div>Live variable analysis is already in LLVM and for me that's enough to know whether a given variable is no longer a root. Note that each safe point has its own set of root locations, and these locations all contain live variables. Dead variables may still be in register or stack, but the GC will not visit them.</div>
<div>
<div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div>2) As I mentioned, my language supports tagged unions and other "value" types. Another example is a tuple type, such as (String, String). Such types are never allocated on the heap by themselves, because they don't have the object header structure that holds the type information needed by the garbage collector. Instead, these values can live in SSA variables, or in allocas, or they can be embedded inside larger types which do live on the heap.</div>
</blockquote><div><br></div></div><div>If you know, at compile-time, whether you are dealing with a struct or a heap, what prevents you from emitting code that won't need such tagged unions in the IR. Same for structs: if they contain pointers to heap objects, those will be in that special address space.</div>
</div></blockquote><div><br></div></div><div>I'm not sure what you mean by this.</div><div><br></div><div>Take for example a union of a String (which is a pointer) and a float. The union is either { i1; String * } or { i1; float }. The garbage collector needs to see that i1 in order to know whether the second field of the struct is a pointer - if it attempted to dereference the pointer when the field actually contains a float, the program would crash. The metadata argument that I pass to llvm.gcroot informs the garbage collector about the structure of the union.</div>
</div></blockquote><div><br></div><div>Sorry, I left a part out. The way that my garbage collector works currently is that the collector gets a pointer to the enture union struct, not just the pointer field within the union. In other words, the entire union struct is considered a "root".</div>
<div><br></div><div>In fact, there might not even be a pointer in the struct. You see, because LLVM doesn't directly support unions, I have to simulate that support by casting pointers. That is, for each different type contained in the union, I have a different struct type, and when I want to extract data from the union I cast the pointer to the appropriate type and then use GEP to get the data out. However, when allocating storage for the union, I have to use the largest data type, which might not be a pointer.</div>
<div><br></div><div>For example, suppose I have a type "String or (float, float, float)" - that is, a union of a string and a 3-tuple of floats. Most of the time what LLVM will see is { i1; { float; float; float; } } because that's bigger than { i1; String* }. LLVM won't even know there's a pointer in there, except during those brief times when I'm accessing the pointer field. So tagging the pointer in a different address space won't help at all here. </div>
<div><br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;"><div class="gmail_quote"><div class="im"><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<div class="gmail_quote"><div><div><br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div>3) I've been following the discussions on llvm-dev about the use of the address-space property of pointers to signal different kinds of memory pools for things like shared address spaces. If we try to use that same variable to indicate garbage collection, now we have to multiplex both meanings onto the same field. We can't just dedicate one special ID for the garbage collected heap, because there could be multiple such heaps. As you add additional orthogonal meanings to the address-space field, you end up with a combinatorial explosion of possible values for it.</div>
<div><br></div></blockquote><div><br></div></div><div>I think there exist already some convention between an ID and some codegen. Having one additional seems fine to me, even if you need to play with bits in case you need different IDs for a single pointer.<br>
</div><div><br></div><div>I'm also fine with the intrinsic way of declaring a GC root. But I think it is cumbersome, and error-prone in the presence of optimizers that may try to move away that intrinsic (I remember similar issues with the current EH intrinsics).</div>
<div><br></div><div>Nicolas</div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div></div><div>-- </div><div>-- Talin<br>
</div>
</blockquote></div><br>
</blockquote></div></div><br><br clear="all"><br>-- <br><font color="#888888">-- Talin<br>
</font></blockquote></div><br><br clear="all"><br>-- <br>-- Talin<br>