<html><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space; ">Hi again Terence,<div><br><div><div>On Apr 22, 2008, at 15:20, Terence Parr wrote:</div><div><br></div><div><blockquote type="cite">Sorry for the long questions...gotta figure this out.<br></blockquote></div><div apple-content-edited="true"><div style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space; "><div><br class="khtml-block-placeholder"></div><div>Not a problem!</div><div><br></div></div></div><blockquote type="cite">On Apr 21, 2008, at 6:23 PM, Gordon Henriksen wrote:<br><br><blockquote type="cite">On Apr 21, 2008, at 20:09, Terence Parr wrote:<br></blockquote><blockquote type="cite"><br></blockquote><blockquote type="cite"><blockquote type="cite">Ok, I *might* be getting this from the assembly code. ... From <span class="Apple-style-span" style="-webkit-text-stroke-width: -1; ">that, it will push/pop in functions? If so, that's easy enough. :)</span></blockquote></blockquote><blockquote type="cite"><br></blockquote><blockquote type="cite">Yup! Sounds like you've got it.<br></blockquote><br>Yup, what i was missing and what somebody should add to the doc is that "shadow-stack" adds a preamble/postamble snippet to each function that must bind with<br><br>StackEntry *llvm_gc_root_chain;<br><br>wherever you choose to define it. I put into my GC.c file.<br><br>Further, that shadow-stack snippet generation assumes the following structures for tracking roots:<br><br>typedef struct FrameMap FrameMap;<br>struct FrameMap {<br> int32_t NumRoots; // Number of roots in stack frame.<br> int32_t NumMeta; // Number of metadata descriptors. May be < <br>NumRoots.<br> void *Meta[]; // May be absent for roots without metadata.<br>};<br><br>typedef struct StackEntry StackEntry;<br>struct StackEntry {<br> StackEntry *Next; // Caller's stack entry.<br> const FrameMap *Map; // Pointer to constant FrameMap.<br> void *Roots[]; // Stack roots (in-place array).<br>};<br><br>The doc says compiler / runtime must agree, but not what the structs are...Seems like those few lines above would make everything clear. I don't have write access to svn, but I plan on a big chapter full of ANTLR -> LLVM examples in my DSL problem solving book.<br></blockquote><div><br></div><div>If you'd like to propose clarified language once you've wrapped your head around the framework, I'd be happy to incorporate it. Most ideally, submit a patch against GarbageCollection.html in <a href="http://llvm.org/svn/llvm-project/llvm/trunk/docs/">http://llvm.org/svn/llvm-project/llvm/trunk/docs/</a>.</div><div><br></div><blockquote type="cite"><blockquote type="cite"><blockquote type="cite">What I was/am missing is the explicit link between types and <span class="Apple-style-span" style="-webkit-text-stroke-width: -1; ">variables in a GC.c file and the generated machine code. If I can get that last explicit link, I'm off to the races.</span></blockquote></blockquote><blockquote type="cite"><br></blockquote><blockquote type="cite">You mean, how do you know what sort of object you're tracing?<br></blockquote><br>I assumed that I needed to generate my object maps or at least a list of pointers for each object type. Related to that, i have two important questions:<br><br>1. How do I know the offset (due to alignment/padding by LLVM) of a pointer within an object using {...} struct type? GEP instruction gets an address, of course, but how does my C collector compute these. Do I need to make a metadata struct and fill it with GEP instructions? I guess that makes sense.<br></blockquote><div><br></div><div>You can use a constant expression to compute this. Specifically:</div><div><br></div></div></div><blockquote class="webkit-indent-blockquote" style="margin: 0 0 0 40px; border: none; padding: 0px;">i32 ptrtoint(gep %mytype* null, i32 0, i32 ??? to i32)</blockquote><div><br></div>Where ??? is the number of the field within the struct. (Could be a list of indices.)<br><div><div><br><blockquote type="cite">2. How do I know how big a struct is? I have my gc_allocate() method</blockquote><div><br></div>Note: There's absolutely nothing special about the name @llvm_gc_allocate, it's just a gentle suggestion. In fact, if you're using the "model 1" heap tracing strategy, you probably want to use something like this:</div><div><br></div></div><blockquote class="webkit-indent-blockquote" style="margin: 0 0 0 40px; border: none; padding: 0px;">%class.object* @alloc_object(%runtime.class* %vtable, i32 %nbytes)</blockquote><div><div><br></div><div>This way, the vtable pointer is guaranteed to be initialized before the collector can possibly see it. (A null vtable could be defended against in the collector, but that's an expensive spot to put a branch.)<i></i></div><div><i><span class="Apple-style-span" style="font-style: normal;"><br></span></i><div></div><blockquote type="cite"></blockquote><blockquote type="cite">but I have no idea how big the struct will be; i see now sizeof. Alignment makes it unclear how big something is; it's >= size of elements like i32 but how much bigger than packed struct is it? I.e.,<br><br>%struct.A = type {i32 x, [10 x i32]*}<br><br>define void @foo() gc "shadow-stack" {<br> %s = alloca %struct.A ; this knows how big struct.A is</blockquote><blockquote type="cite"> %a = call i32* @llvm_gc_allocate(i32 11); this does not know. is <br>it 11 or more?<br> ret void<br>}<br></blockquote><div><br></div><div>You can again use a constant expression here. Specifically:</div><div><br></div></div></div><blockquote class="webkit-indent-blockquote" style="margin: 0 0 0 40px; border: none; padding: 0px;">i32 ptrtoint(gep %mytype* null, i32 1 to i32)</blockquote><div><div><br></div><div>ConstantExpr has a helper similar to sizeOf(Type*) which build this expression.</div></div><div><div><br></div><div><blockquote type="cite"><blockquote type="cite"><span class="Apple-style-span" style="-webkit-text-stroke-width: -1; ">• If you have a type forest (as in C or C++) with optional vtables, then no such assumption is possible, and you can include type layout information in the %metadata parameter to @llvm.gcroot. The FrameMap type includes this data.</span></blockquote></blockquote><blockquote type="cite"><br>Ok, so I pass it an arbitrary struct pointer and it just gives it back later for me to peruse, right?<br></blockquote><div><br></div><div>Yep! You can use any constant pointer (which means: any global variable, alias, or function). For example, something like this:</div><div><br></div></div></div><blockquote class="webkit-indent-blockquote" style="margin: 0 0 0 40px; border: none; padding: 0px;"><font class="Apple-style-span" face="'Courier New'">class IntList {<br> int count;<br> ListEntry head;<br> ListEntry tail;</font></blockquote><blockquote class="webkit-indent-blockquote" style="margin: 0 0 0 40px; border: none; padding: 0px;"><span class="Apple-style-span" style="font-family: 'Courier New'; ">};</span></blockquote><blockquote class="webkit-indent-blockquote" style="margin: 0 0 0 40px; border: none; padding: 0px;"><font class="Apple-style-span" face="'Courier New'"><br>class IntListEntry {<br> IntListEntry prev;<br> IntListEntry next;<br> int value;</font></blockquote><blockquote class="webkit-indent-blockquote" style="margin: 0 0 0 40px; border: none; padding: 0px;"><span class="Apple-style-span" style="font-family: 'Courier New'; ">};</span></blockquote><blockquote class="webkit-indent-blockquote" style="margin: 0 0 0 40px; border: none; padding: 0px;"><font class="Apple-style-span" face="'Courier New'"><br></font></blockquote><blockquote class="webkit-indent-blockquote" style="margin: 0 0 0 40px; border: none; padding: 0px;"><font class="Apple-style-span" face="'Courier New'">int SumOfList(IntList list) {<br> return RecursiveSumOfList(list.head, 0);<br>}<br></font></blockquote><div><blockquote class="webkit-indent-blockquote" style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 40px; border-top-style: none; border-right-style: none; border-bottom-style: none; border-left-style: none; border-width: initial; border-color: initial; padding-top: 0px; padding-right: 0px; padding-bottom: 0px; padding-left: 0px; "><font class="Apple-style-span" face="'Courier New'"><br></font></blockquote><blockquote class="webkit-indent-blockquote" style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 40px; border-top-style: none; border-right-style: none; border-bottom-style: none; border-left-style: none; border-width: initial; border-color: initial; padding-top: 0px; padding-right: 0px; padding-bottom: 0px; padding-left: 0px; "><font class="Apple-style-span" face="'Courier New'">int RecursiveSumOfList(IntList entry, int sumSoFar) {<br> if (entry == null)<br> return sumSoFar;<br> return RecursiveSumOfList(entry.next, sumSoFar + entry.value);<br>}<br></font></blockquote><div><div><br></div><div>Could be hypothetically translated into the following LLVM IR. Note the following aspects:</div><div><br></div><div><ul class="MailOutline"><li>Class metadata is emitted as constants to allow the GC to trace the heap.</li><ul class="MailOutline"><li>Offsets to reference fields are calculated portably using the 'gep null' trick.</li><li>You don't want to write these constants by hand. :)</li><li>It would also be possible to tag roots with a trace function with a prototype like "void(Object*, void (*)(Class*, Object*))" which invokes the callback for each reference in the parameter object.</li></ul><li>This is the "model 2" tagless object model, where neither tag bits nor a vtable pointer are present in all objects.</li><ul class="MailOutline"><li>Each call @llvm.gcroot must specify the metadata pointer so the collector knows how to trace the object (or find the vtable, where applicable).</li></ul><li>This is somewhat conservative with respect to certain GC behaviors. More elaboration is inline.</li><ul class="MailOutline"><li>Ephemeral temporaries get gcroots. This could be unnecessary for a single-threaded collector if the temp isn't alive across a call.</li><li>Each use of a reference variable or temp is reloaded from the gcroot. This is necessary only for copying collectors.</li><li>However, @llvm.readbarrier and @llvm.writebarrier are not used. Using them would be more conservative still, but quite verbose.</li></ul></ul></div><div><br></div></div></div><blockquote class="webkit-indent-blockquote" style="margin: 0 0 0 40px; border: none; padding: 0px;"><font class="Apple-style-span" face="'Courier New'">; This is the runtime-defined type for class metadata.<br></font><font class="Apple-style-span" face="'Courier New'">; Here, it contains only GC tracing information.<br></font><font class="Apple-style-span" face="'Courier New'">; <br></font><font class="Apple-style-span" face="'Courier New'">; namespace runtime {<br></font><font class="Apple-style-span" face="'Courier New'">; class Class {<br></font><font class="Apple-style-span" face="'Courier New'">; unsigned NumReferences;<br></font><font class="Apple-style-span" face="'Courier New'">; struct {<br></font><font class="Apple-style-span" face="'Courier New'">; unsigned ReferenceOffset;<br></font><font class="Apple-style-span" face="'Courier New'">; Class *ReferenceType;<br></font><font class="Apple-style-span" face="'Courier New'">; } References[NumReferences]; // Flexible array member.<br></font><font class="Apple-style-span" face="'Courier New'">; };<br></font><font class="Apple-style-span" face="'Courier New'">; }<br></font><font class="Apple-style-span" face="'Courier New'">; <br></font><font class="Apple-style-span" face="'Courier New'">; The recursive nature of GC references should be clear.<br></font><font class="Apple-style-span" face="'Courier New'">; The type would need to be more complex to handle arrays and type hierarchies.<br></font><font class="Apple-style-span" face="'Courier New'"><br></font><font class="Apple-style-span" face="'Courier New'">%runtime.Class = type {i32, [0 x {i32, %runtime.Class*}]}<br></font><font class="Apple-style-span" face="'Courier New'"><span class="Apple-style-span" style="font-family: 'Trebuchet MS'; "><font class="Apple-style-span" face="'Courier New'">declare void @llvm.gcroot(i8** %root, i8* %metadata)<br></font><font class="Apple-style-span" face="'Courier New'"><br></font></span></font><font class="Apple-style-span" face="'Courier New'">; User-defined datatype:<br></font><font class="Apple-style-span" face="'Courier New'">; <br></font><font class="Apple-style-span" face="'Courier New'">; class IntList {<br></font><font class="Apple-style-span" face="'Courier New'">; int count;<br></font><font class="Apple-style-span" face="'Courier New'">; IntListEntry head;<br></font><font class="Apple-style-span" face="'Courier New'">; IntListEntry tail;<br></font><font class="Apple-style-span" face="'Courier New'">; }<br></font><font class="Apple-style-span" face="'Courier New'"><br></font><font class="Apple-style-span" face="'Courier New'">%class.IntList = type {i32, %class.IntListEntry*, %class.IntListEntry*}<br></font><font class="Apple-style-span" face="'Courier New'"><br></font><font class="Apple-style-span" face="'Courier New'">@class_IntList = constant {i32, [2 x {i32, %runtime.Class*}]} {<br></font><span class="Apple-tab-span" style="white-space:pre"><font class="Apple-style-span" face="'Courier New'"> </font></span><font class="Apple-style-span" face="'Courier New'">i32 0,<br></font><span class="Apple-tab-span" style="white-space:pre"><font class="Apple-style-span" face="'Courier New'"> </font></span><font class="Apple-style-span" face="'Courier New'">[2 x {i32, %runtime.Class*}] [<br></font><span class="Apple-tab-span" style="white-space:pre"><font class="Apple-style-span" face="'Courier New'"> </font></span><font class="Apple-style-span" face="'Courier New'">{i32, %runtime.Class*} {<br></font><span class="Apple-tab-span" style="white-space:pre"><font class="Apple-style-span" face="'Courier New'"> </font></span><font class="Apple-style-span" face="'Courier New'">i32 ptrtoint(%class.IntListEntry** getelementptr(%class.IntList* null, i32 0, i32 1) to i32),<br></font><span class="Apple-tab-span" style="white-space:pre"><font class="Apple-style-span" face="'Courier New'"> </font></span><font class="Apple-style-span" face="'Courier New'">%runtime.Class* bitcast({i32, [2 x {i32, %runtime.Class*}]}* @class_IntListEntry to %runtime.Class*)<br></font><span class="Apple-tab-span" style="white-space:pre"><font class="Apple-style-span" face="'Courier New'"> </font></span><font class="Apple-style-span" face="'Courier New'">},<br></font><span class="Apple-tab-span" style="white-space:pre"><font class="Apple-style-span" face="'Courier New'"> </font></span><font class="Apple-style-span" face="'Courier New'">{i32, %runtime.Class*} {<br></font><span class="Apple-tab-span" style="white-space:pre"><font class="Apple-style-span" face="'Courier New'"> </font></span><font class="Apple-style-span" face="'Courier New'">i32 ptrtoint(%class.IntListEntry** getelementptr(%class.IntList* null, i32 0, i32 2) to i32),<br></font><span class="Apple-tab-span" style="white-space:pre"><font class="Apple-style-span" face="'Courier New'"> </font></span><font class="Apple-style-span" face="'Courier New'">%runtime.Class* bitcast({i32, [2 x {i32, %runtime.Class*}]}* @class_IntListEntry to %runtime.Class*)<br></font><span class="Apple-tab-span" style="white-space:pre"><font class="Apple-style-span" face="'Courier New'"> </font></span><font class="Apple-style-span" face="'Courier New'">}<br></font><span class="Apple-tab-span" style="white-space:pre"><font class="Apple-style-span" face="'Courier New'"> </font></span><font class="Apple-style-span" face="'Courier New'">]<br></font><font class="Apple-style-span" face="'Courier New'">}<br></font><font class="Apple-style-span" face="'Courier New'"><br></font><font class="Apple-style-span" face="'Courier New'">; User-defined datatype:<br></font><font class="Apple-style-span" face="'Courier New'">; <br></font><font class="Apple-style-span" face="'Courier New'">; class IntListEntry {<br></font><font class="Apple-style-span" face="'Courier New'">; IntListEntry prev;<br></font><font class="Apple-style-span" face="'Courier New'">; IntListEntry next;<br></font><font class="Apple-style-span" face="'Courier New'">; int value;<br></font><font class="Apple-style-span" face="'Courier New'">; }<br></font><font class="Apple-style-span" face="'Courier New'"><br></font><font class="Apple-style-span" face="'Courier New'">%class.IntListEntry = type {%class.IntListEntry*, %class.IntListEntry*, i32}<br></font><font class="Apple-style-span" face="'Courier New'"><br></font><font class="Apple-style-span" face="'Courier New'">@class_IntListEntry = constant {i32, [2 x {i32, %runtime.Class*}]} {<br></font><span class="Apple-tab-span" style="white-space:pre"><font class="Apple-style-span" face="'Courier New'"> </font></span><font class="Apple-style-span" face="'Courier New'">i32 0,<br></font><span class="Apple-tab-span" style="white-space:pre"><font class="Apple-style-span" face="'Courier New'"> </font></span><font class="Apple-style-span" face="'Courier New'">[2 x {i32, %runtime.Class*}] [<br></font><span class="Apple-tab-span" style="white-space:pre"><font class="Apple-style-span" face="'Courier New'"> </font></span><font class="Apple-style-span" face="'Courier New'">{i32, %runtime.Class*} {<br></font><span class="Apple-tab-span" style="white-space:pre"><font class="Apple-style-span" face="'Courier New'"> </font></span><font class="Apple-style-span" face="'Courier New'">i32 ptrtoint(%class.IntListEntry** getelementptr(%class.IntListEntry* null, i32 0, i32 0) to i32),<br></font><span class="Apple-tab-span" style="white-space:pre"><font class="Apple-style-span" face="'Courier New'"> </font></span><font class="Apple-style-span" face="'Courier New'">%runtime.Class* bitcast({i32, [2 x {i32, %runtime.Class*}]}* @class_IntListEntry to %runtime.Class*)<br></font><span class="Apple-tab-span" style="white-space:pre"><font class="Apple-style-span" face="'Courier New'"> </font></span><font class="Apple-style-span" face="'Courier New'">},<br></font><span class="Apple-tab-span" style="white-space:pre"><font class="Apple-style-span" face="'Courier New'"> </font></span><font class="Apple-style-span" face="'Courier New'">{i32, %runtime.Class*} {<br></font><span class="Apple-tab-span" style="white-space:pre"><font class="Apple-style-span" face="'Courier New'"> </font></span><font class="Apple-style-span" face="'Courier New'">i32 ptrtoint(%class.IntListEntry** getelementptr(%class.IntListEntry* null, i32 0, i32 1) to i32),<br></font><span class="Apple-tab-span" style="white-space:pre"><font class="Apple-style-span" face="'Courier New'"> </font></span><font class="Apple-style-span" face="'Courier New'">%runtime.Class* bitcast({i32, [2 x {i32, %runtime.Class*}]}* @class_IntListEntry to %runtime.Class*)<br></font><span class="Apple-tab-span" style="white-space:pre"><font class="Apple-style-span" face="'Courier New'"> </font></span><font class="Apple-style-span" face="'Courier New'">}<br></font><span class="Apple-tab-span" style="white-space:pre"><font class="Apple-style-span" face="'Courier New'"> </font></span><font class="Apple-style-span" face="'Courier New'">]<br></font><font class="Apple-style-span" face="'Courier New'">}<br></font><font class="Apple-style-span" face="'Courier New'"><br></font><font class="Apple-style-span" face="'Courier New'">; User-defined function:<br></font><font class="Apple-style-span" face="'Courier New'">; <br></font><font class="Apple-style-span" face="'Courier New'">; int SumOfList(IntList list) {<br></font><font class="Apple-style-span" face="'Courier New'">; return RecursiveSumOfList(list.head, 0);<br></font><font class="Apple-style-span" face="'Courier New'">; }<br></font><font class="Apple-style-span" face="'Courier New'"><br></font><font class="Apple-style-span" face="'Courier New'">define i32 @SumOfList(%class.IntList* %list) gc "shadow-stack" {<br></font><font class="Apple-style-span" face="'Courier New'">entry:<br></font><span class="Apple-tab-span" style="white-space:pre"><font class="Apple-style-span" face="'Courier New'"> </font></span><font class="Apple-style-span" face="'Courier New'">; Prologue. 2 reference variables (including temps): list and list.head.<br></font><span class="Apple-tab-span" style="white-space:pre"><font class="Apple-style-span" face="'Courier New'"> </font></span><font class="Apple-style-span" face="'Courier New'">; 1. Create an alloca for each variable, including parameters.<br></font><span class="Apple-tab-span" style="white-space:pre"><font class="Apple-style-span" face="'Courier New'"> </font></span><font class="Apple-style-span" face="'Courier New'">%list.var = alloca %class.IntList*<br></font><span class="Apple-tab-span" style="white-space:pre"><font class="Apple-style-span" face="'Courier New'"> </font></span><font class="Apple-style-span" face="'Courier New'">%head.var = alloca %class.IntListEntry*<br></font><span class="Apple-tab-span" style="white-space:pre"><font class="Apple-style-span" face="'Courier New'"> </font></span><font class="Apple-style-span" face="'Courier New'">; 2. Call @llvm.gcroot for it.<br></font><span class="Apple-tab-span" style="white-space:pre"><font class="Apple-style-span" face="'Courier New'"> </font></span><font class="Apple-style-span" face="'Courier New'">%list.root = bitcast %class.IntList** %list.var to i8**<br></font><span class="Apple-tab-span" style="white-space:pre"><font class="Apple-style-span" face="'Courier New'"> </font></span><font class="Apple-style-span" face="'Courier New'">%head.root = bitcast %class.IntListEntry** %head.var to i8**<br></font><span class="Apple-tab-span" style="white-space:pre"><font class="Apple-style-span" face="'Courier New'"> </font></span><font class="Apple-style-span" face="'Courier New'">call void @llvm.gcroot(i8** %list.root, i8* bitcast({i32, [2 x {i32, %runtime.Class*}]}* @class_IntList to i8*))<br></font><span class="Apple-tab-span" style="white-space:pre"><font class="Apple-style-span" face="'Courier New'"> </font></span><font class="Apple-style-span" face="'Courier New'">call void @llvm.gcroot(i8** %head.root, i8* bitcast({i32, [2 x {i32, %runtime.Class*}]}* @class_IntListEntry to i8*))<br></font><span class="Apple-tab-span" style="white-space:pre"><font class="Apple-style-span" face="'Courier New'"> </font></span><font class="Apple-style-span" face="'Courier New'">; 3. Initialize parameters. Note: No need to null-init roots; the GC does so if necessary.<br></font><span class="Apple-tab-span" style="white-space:pre"><font class="Apple-style-span" face="'Courier New'"> </font></span><font class="Apple-style-span" face="'Courier New'">store %class.IntList* %list, %class.IntList** %list.var<br></font><span class="Apple-tab-span" style="white-space:pre"><font class="Apple-style-span" face="'Courier New'"> </font></span><font class="Apple-style-span" face="'Courier New'">; End prologue.<br></font><span class="Apple-tab-span" style="white-space:pre"><font class="Apple-style-span" face="'Courier New'"> <br></font></span><span class="Apple-tab-span" style="white-space:pre"><font class="Apple-style-span" face="'Courier New'"> </font></span><font class="Apple-style-span" face="'Courier New'">; This load is possibly unnecessary, depending on the GC.<br></font><span class="Apple-tab-span" style="white-space:pre"><font class="Apple-style-span" face="'Courier New'"> </font></span><font class="Apple-style-span" face="'Courier New'">; If the GC is copying, then the pointer may change whenever the GC is invoked.<br></font><span class="Apple-tab-span" style="white-space:pre"><font class="Apple-style-span" face="'Courier New'"> </font></span><font class="Apple-style-span" face="'Courier New'">; But if the GC is non-moving, there's no need to reload from head.var.<br></font><span class="Apple-tab-span" style="white-space:pre"><font class="Apple-style-span" face="'Courier New'"> </font></span><font class="Apple-style-span" face="'Courier New'">; Eliding the load will generate faster code.<br></font><span class="Apple-tab-span" style="white-space:pre"><font class="Apple-style-span" face="'Courier New'"> </font></span><font class="Apple-style-span" face="'Courier New'">%list.1 = load %class.IntList** %list.var<br></font><span class="Apple-tab-span" style="white-space:pre"><font class="Apple-style-span" face="'Courier New'"> <br></font></span><span class="Apple-tab-span" style="white-space:pre"><font class="Apple-style-span" face="'Courier New'"> </font></span><font class="Apple-style-span" face="'Courier New'">%head.ptr = getelementptr %class.IntList* %list.1, i32 0, i32 1<br></font><span class="Apple-tab-span" style="white-space:pre"><font class="Apple-style-span" face="'Courier New'"> </font></span><font class="Apple-style-span" face="'Courier New'">%head = load %class.IntListEntry** %head.ptr<br></font><span class="Apple-tab-span" style="white-space:pre"><font class="Apple-style-span" face="'Courier New'"> <br></font></span><span class="Apple-tab-span" style="white-space:pre"><font class="Apple-style-span" face="'Courier New'"> </font></span><font class="Apple-style-span" face="'Courier New'">; This store (and thus %head.var gcroot) is possibly unnecessary, depending on the GC.<br></font><span class="Apple-tab-span" style="white-space:pre"><font class="Apple-style-span" face="'Courier New'"> </font></span><font class="Apple-style-span" face="'Courier New'">; In a threaded collector, it's possible that the function call site could've been patched<br></font><span class="Apple-tab-span" style="white-space:pre"><font class="Apple-style-span" face="'Courier New'"> </font></span><font class="Apple-style-span" face="'Courier New'">; to enlist the thread in a 'stop the world' event. (This is necessary to bound collection<br></font><span class="Apple-tab-span" style="white-space:pre"><font class="Apple-style-span" face="'Courier New'"> </font></span><font class="Apple-style-span" face="'Courier New'">; pause times.) Thus, the act of calling a function could invoke the collector, in which<br></font><span class="Apple-tab-span" style="white-space:pre"><font class="Apple-style-span" face="'Courier New'"> </font></span><font class="Apple-style-span" face="'Courier New'">; case temps like %head would need to be rooted.</font></blockquote><br><blockquote class="webkit-indent-blockquote" style="margin: 0 0 0 40px; border: none; padding: 0px;"><span class="Apple-tab-span" style="white-space:pre"><font class="Apple-style-span" face="'Courier New'"> </font></span><font class="Apple-style-span" face="'Courier New'">store %class.IntListEntry* %head, %class.IntListEntry** %head.var<br></font><span class="Apple-tab-span" style="white-space:pre"><font class="Apple-style-span" face="'Courier New'"> <br></font></span><span class="Apple-tab-span" style="white-space:pre"><font class="Apple-style-span" face="'Courier New'"> </font></span><font class="Apple-style-span" face="'Courier New'">%head.1 = load %class.IntListEntry** %head.var<br></font><span class="Apple-tab-span" style="white-space:pre"><font class="Apple-style-span" face="'Courier New'"> </font></span><font class="Apple-style-span" face="'Courier New'">%sum = tail call i32 @RecursiveSumOfList(%class.IntListEntry* %head, i32 0)<br></font><span class="Apple-tab-span" style="white-space:pre"><font class="Apple-style-span" face="'Courier New'"> </font></span><font class="Apple-style-span" face="'Courier New'">ret i32 %sum<br></font><font class="Apple-style-span" face="'Courier New'">}<br></font><font class="Apple-style-span" face="'Courier New'"><br></font><font class="Apple-style-span" face="'Courier New'">; User-defined function:<br></font><font class="Apple-style-span" face="'Courier New'">; <br></font><font class="Apple-style-span" face="'Courier New'">; int SumOfList(IntList entry, int sumSoFar) {<br></font><font class="Apple-style-span" face="'Courier New'">; if (entry == null)<br></font><font class="Apple-style-span" face="'Courier New'">; return sumSoFar;<br></font><font class="Apple-style-span" face="'Courier New'">; return RecursiveSumOfList(entry.next, sumSoFar + entry.value);<br></font><font class="Apple-style-span" face="'Courier New'">; }<br></font><font class="Apple-style-span" face="'Courier New'"><br></font><font class="Apple-style-span" face="'Courier New'">define i32 @RecursiveSumOfList(%class.IntListEntry* %entry, i32 %sumSoFar) gc "shadow-stack" {<br></font><font class="Apple-style-span" face="'Courier New'">entry:<br></font><span class="Apple-tab-span" style="white-space:pre"><font class="Apple-style-span" face="'Courier New'"> </font></span><font class="Apple-style-span" face="'Courier New'">; Prologue. 2 reference variables (including temps): entry and entry.value<br></font><span class="Apple-tab-span" style="white-space:pre"><font class="Apple-style-span" face="'Courier New'"> </font></span><font class="Apple-style-span" face="'Courier New'">%entry.var = alloca %class.IntListEntry*<br></font><span class="Apple-tab-span" style="white-space:pre"><font class="Apple-style-span" face="'Courier New'"> </font></span><font class="Apple-style-span" face="'Courier New'">%next.var = alloca %class.IntListEntry*<br></font><span class="Apple-tab-span" style="white-space:pre"><font class="Apple-style-span" face="'Courier New'"> </font></span><font class="Apple-style-span" face="'Courier New'">%entry.root = bitcast %class.IntListEntry** %entry.var to i8**<br></font><span class="Apple-tab-span" style="white-space:pre"><font class="Apple-style-span" face="'Courier New'"> </font></span><font class="Apple-style-span" face="'Courier New'">%next.root = bitcast %class.IntListEntry** %next.var to i8**<br></font><span class="Apple-tab-span" style="white-space:pre"><font class="Apple-style-span" face="'Courier New'"> </font></span><font class="Apple-style-span" face="'Courier New'">call void @llvm.gcroot(i8** %entry.root, i8* bitcast({i32, [2 x {i32, %runtime.Class*}]}* @class_IntListEntry to i8*))<br></font><span class="Apple-tab-span" style="white-space:pre"><font class="Apple-style-span" face="'Courier New'"> </font></span><font class="Apple-style-span" face="'Courier New'">call void @llvm.gcroot(i8** %next.root, i8* bitcast({i32, [2 x {i32, %runtime.Class*}]}* @class_IntListEntry to i8*))<br></font><span class="Apple-tab-span" style="white-space:pre"><font class="Apple-style-span" face="'Courier New'"> </font></span><font class="Apple-style-span" face="'Courier New'">store %class.IntListEntry* %entry, %class.IntListEntry** %entry.var<br></font><span class="Apple-tab-span" style="white-space:pre"><font class="Apple-style-span" face="'Courier New'"> <br></font></span><span class="Apple-tab-span" style="white-space:pre"><font class="Apple-style-span" face="'Courier New'"> </font></span><font class="Apple-style-span" face="'Courier New'">%entry.0 = load %class.IntListEntry** %entry.var<br></font><span class="Apple-tab-span" style="white-space:pre"><font class="Apple-style-span" face="'Courier New'"> </font></span><font class="Apple-style-span" face="'Courier New'">%if = icmp eq %class.IntListEntry* %entry.0, null<br></font><span class="Apple-tab-span" style="white-space:pre"><font class="Apple-style-span" face="'Courier New'"> </font></span><font class="Apple-style-span" face="'Courier New'">br i1 %if, label %then, label %else<br></font><span class="Apple-tab-span" style="white-space:pre"><font class="Apple-style-span" face="'Courier New'"> <br></font></span><font class="Apple-style-span" face="'Courier New'">then:<br></font><span class="Apple-tab-span" style="white-space:pre"><font class="Apple-style-span" face="'Courier New'"> </font></span><font class="Apple-style-span" face="'Courier New'">ret i32 %sumSoFar<br></font><span class="Apple-tab-span" style="white-space:pre"><font class="Apple-style-span" face="'Courier New'"> <br></font></span><font class="Apple-style-span" face="'Courier New'">else:<br></font><span class="Apple-tab-span" style="white-space:pre"><font class="Apple-style-span" face="'Courier New'"> </font></span><font class="Apple-style-span" face="'Courier New'">%next.ptr = getelementptr %class.IntListEntry* %entry, i32 0, i32 0<br></font><span class="Apple-tab-span" style="white-space:pre"><font class="Apple-style-span" face="'Courier New'"> </font></span><font class="Apple-style-span" face="'Courier New'">%next = load %class.IntListEntry** %next.ptr<br></font><span class="Apple-tab-span" style="white-space:pre"><font class="Apple-style-span" face="'Courier New'"> </font></span><font class="Apple-style-span" face="'Courier New'">store %class.IntListEntry* %next, %class.IntListEntry** %next.var<br></font><span class="Apple-tab-span" style="white-space:pre"><font class="Apple-style-span" face="'Courier New'"> <br></font></span><span class="Apple-tab-span" style="white-space:pre"><font class="Apple-style-span" face="'Courier New'"> </font></span><font class="Apple-style-span" face="'Courier New'">; Note: entry.value is not a reference; no need to root it.<br></font><span class="Apple-tab-span" style="white-space:pre"><font class="Apple-style-span" face="'Courier New'"> </font></span><font class="Apple-style-span" face="'Courier New'">%value.ptr = getelementptr %class.IntListEntry* %entry, i32 0, i32 2<br></font><span class="Apple-tab-span" style="white-space:pre"><font class="Apple-style-span" face="'Courier New'"> </font></span><font class="Apple-style-span" face="'Courier New'">%value = load i32* %value.ptr<br></font><span class="Apple-tab-span" style="white-space:pre"><font class="Apple-style-span" face="'Courier New'"> </font></span><font class="Apple-style-span" face="'Courier New'">%temp = add i32 %sumSoFar, %value<br></font><span class="Apple-tab-span" style="white-space:pre"><font class="Apple-style-span" face="'Courier New'"> <br></font></span><span class="Apple-tab-span" style="white-space:pre"><font class="Apple-style-span" face="'Courier New'"> </font></span><font class="Apple-style-span" face="'Courier New'">%next.1 = load %class.IntListEntry** %next.var<br></font><span class="Apple-tab-span" style="white-space:pre"><font class="Apple-style-span" face="'Courier New'"> </font></span><font class="Apple-style-span" face="'Courier New'">%sum = tail call i32 @RecursiveSumOfList(%class.IntListEntry* %next.1, i32 %temp)<br></font><span class="Apple-tab-span" style="white-space:pre"><font class="Apple-style-span" face="'Courier New'"> </font></span><font class="Apple-style-span" face="'Courier New'">ret i32 %sum<br></font><font class="Apple-style-span" face="'Courier New'">}</font></blockquote><div><div><span class="Apple-style-span" style="-webkit-text-stroke-width: -1;"><br></span></div><div>As you can see, there are many dimensions of flexibility here.</div><div><span class="Apple-style-span" style="-webkit-text-stroke-width: -1;"><span class="Apple-style-span" style="-webkit-text-stroke-width: 0; "><div><br></div></span></span></div><div><span class="Apple-style-span" style="-webkit-text-stroke-width: -1; ">— Gordon</span></div><div apple-content-edited="true"> </div><br></div></body></html>