<html><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space; "><div><div>On 2007-09-03, at 23:14, Talin wrote:</div><br class="Apple-interchange-newline"><blockquote type="cite"><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">On Sep 2, 2007 5:31 AM, Gordon Henriksen <<a href="mailto:gordonhenriksen@mac.com">gordonhenriksen@mac.com</a>> wrote:</div> <blockquote type="cite"><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; "></div></blockquote><br class="webkit-block-placeholder"></blockquote><blockquote type="cite"><blockquote type="cite"><span class="Apple-style-span" style="-webkit-text-stroke-width: -1; ">On Sep 2, 2007, at 04:54, Talin wrote:</span></blockquote></blockquote><blockquote type="cite"><blockquote type="cite"><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; min-height: 14px; "><br></div> <blockquote type="cite"><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">I've been looking through the documentation (<a href="http://llvm.org/docs/">http://llvm.org/docs/</a><span class="Apple-style-span" style="-webkit-text-stroke-width: -1; ">GarbageCollection.html) on how to implement a garbage collector for LLVM and there's a couple of things that I don't quite understand. Specifically, it says that when a stack variable goes out of scope, you're supposed to assign a null value to it to indicate that the value is no longer live.</span></div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; min-height: 14px; "><br></div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">What I don't quite understand is how the GC can efficiently use <span class="Apple-style-span" style="-webkit-text-stroke-width: -1; ">this information.</span></div> </blockquote><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; min-height: 14px; "><br></div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">The GC intrinsics exist for the type of collector which depends on <span class="Apple-style-span" style="-webkit-text-stroke-width: -1; ">metadata compiled alongside the function. At runtime, such a collector walks the dynamic call stack and merges that with the static metadata to identify dynamically live roots. Like "zero cost exception handling" or debug info, collecting this kind of metadata requires backend code generator support, which again is the reason these intrinsics exist.</span></div> </blockquote><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; min-height: 14px; "><br></div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">So, if I understand what you are saying correctly, the "llvm.gcroot" <span class="Apple-style-span" style="-webkit-text-stroke-width: -1; ">intrinsic isn't actually an "instruction" in the sense I normally think of as an action to be taken; It's more of a marker which is used by the code generator to create a data structure that describes the stack layout. Is that correct?</span></div></blockquote><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; min-height: 14px; "><br></div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; min-height: 14px; ">That's correct; the gcroot intrinsic is an annotation of an alloca. This is not without precedent. The llvm.noalias intrinsic is an annotation of an SSA pointer value.</div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; min-height: 14px; "><br class="webkit-block-placeholder"></div><blockquote type="cite"><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">If that's the case, then my next question is: How do the LLVM garbage <span class="Apple-style-span" style="-webkit-text-stroke-width: -1; ">collection intrinsics work in a multi-threaded environment? If there's a data structure that describes the layout of the stack, and you have multiple stacks, what happens?</span></div></blockquote><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; min-height: 14px; "><br></div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; min-height: 14px; ">The intrinsics are entirely neutral to collector implementation, and thus to threading. They could easily be used to implement reference counting, for instance, which may or may not be implemented in a threadsafe manner. However, as with your algorithm, reference counting does not require code generator support, and so would not justify the introduction of the intrinsics.</div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; min-height: 14px; "><br class="webkit-block-placeholder"></div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; min-height: 14px; ">But to elaborate upon the described class of collectors: The emitted GC tables do not describe the dynamic call stack; rather, they are static data compiled into the executable. Only when cross-referenced with the dynamic call stack do they identify the roots. The garbage collectors for .NET and Java work in this manner.</div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; min-height: 14px; "><br class="webkit-block-placeholder"></div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; min-height: 14px; ">Here's an example of the sort of data these tables might contain. (I generated this using the <font class="Apple-style-span" face="Courier">-print-gc</font> feature which I have added to <font class="Apple-style-span" face="Courier">llc</font> locally; the <font class="Apple-style-span" face="Courier">llc</font> in Subversion does cannot print this data because it does not collect it.) This test case has a simple function with 2 roots and 1 call.</div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; min-height: 14px; "><br class="webkit-block-placeholder"></div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; min-height: 14px; "><div><font class="Apple-style-span" face="Courier">GC roots for fun:</font></div><div><font class="Apple-style-span" face="Courier"> 0 8[sp]</font></div><div><font class="Apple-style-span" face="Courier"> 1 4[sp]</font></div><div><font class="Apple-style-span" face="Courier">GC safe points for fun:</font></div><div><font class="Apple-style-span" face="Courier"> label 1: post-call, live = { 0, 1 }</font></div></div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; min-height: 14px; "><br></div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; min-height: 14px; ">Provided this information, the collector can easily identify the live roots within <font class="Apple-style-span" face="Courier">fun</font>'s stack frame at runtime—so long as <font class="Apple-style-span" face="Courier">fun</font> is paused at the safe point, which it must be if it is not the topmost stack frame.</div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; min-height: 14px; "><br class="webkit-block-placeholder"></div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; min-height: 14px; ">Walking the stack; identifying the current safe point and stack pointer; stopping concurrent threads at safe points; and actually tracing the heap—all left as exercises to the interested reader. :)</div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; min-height: 14px; "><br class="webkit-block-placeholder"></div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; min-height: 14px; ">Here's a resource you might find interesting for further reading:</div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; min-height: 14px; "><br class="webkit-block-placeholder"></div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; min-height: 14px; "> <a href="http://www.cs.kent.ac.uk/people/staff/rej/gcbib/gcbib.html">http://www.cs.kent.ac.uk/people/staff/rej/gcbib/gcbib.html</a></div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; min-height: 14px; "><br class="webkit-block-placeholder"></div><blockquote type="cite"><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">BTW, I'm also noticing that the current SemiSpace example code seems <span class="Apple-style-span" style="-webkit-text-stroke-width: -1; ">quite incomplete.</span></div></blockquote><br></div><div>I observed that myself.</div><div><br class="webkit-block-placeholder"></div><div><span class="Apple-style-span" style="border-collapse: separate; border-spacing: 0px 0px; color: rgb(0, 0, 0); font-family: Trebuchet MS; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; text-align: auto; -khtml-text-decorations-in-effect: none; text-indent: 0px; -apple-text-size-adjust: auto; text-transform: none; orphans: 2; white-space: normal; widows: 2; word-spacing: 0px; "><span class="Apple-style-span" style="border-collapse: separate; border-spacing: 0px 0px; color: rgb(0, 0, 0); font-family: Trebuchet MS; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; text-align: auto; -khtml-text-decorations-in-effect: none; text-indent: 0px; -apple-text-size-adjust: auto; text-transform: none; orphans: 2; white-space: normal; widows: 2; word-spacing: 0px; "><span class="Apple-style-span" style="border-collapse: separate; border-spacing: 0px 0px; color: rgb(0, 0, 0); font-family: Trebuchet MS; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; text-align: auto; -khtml-text-decorations-in-effect: none; text-indent: 0px; -apple-text-size-adjust: auto; text-transform: none; orphans: 2; white-space: normal; widows: 2; word-spacing: 0px; "><span class="Apple-style-span" style="border-collapse: separate; border-spacing: 0px 0px; color: rgb(0, 0, 0); font-family: Trebuchet MS; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; text-align: auto; -khtml-text-decorations-in-effect: none; text-indent: 0px; -apple-text-size-adjust: auto; text-transform: none; orphans: 2; white-space: normal; widows: 2; word-spacing: 0px; "><span class="Apple-style-span" style="border-collapse: separate; border-spacing: 0px 0px; color: rgb(0, 0, 0); font-family: Trebuchet MS; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; text-align: auto; -khtml-text-decorations-in-effect: none; text-indent: 0px; -apple-text-size-adjust: auto; text-transform: none; orphans: 2; white-space: normal; widows: 2; word-spacing: 0px; "><span class="Apple-style-span" style="border-collapse: separate; border-spacing: 0px 0px; color: rgb(0, 0, 0); font-family: Trebuchet MS; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; text-align: auto; -khtml-text-decorations-in-effect: none; text-indent: 0px; -apple-text-size-adjust: auto; text-transform: none; orphans: 2; white-space: normal; widows: 2; word-spacing: 0px; ">— Gordon<br class="Apple-interchange-newline"></span></span></span></span></span></span> </div><br></body></html>