On Fri, Jul 1, 2011 at 4:41 PM, Andrew Trick <span dir="ltr"><<a href="mailto:atrick@apple.com" target="_blank">atrick@apple.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 style="word-wrap:break-word"><div><div>Hi Talin,</div><div><br></div><div>I have some questions below. If these topics have already been discussed in earlier threads, kindly point me there. I'm aware of your GC proposal, but the rest is new to me.</div>
<div><div><br></div><div>On Jul 1, 2011, at 11:05 AM, Talin wrote:</div><blockquote type="cite"><div><div><b>Garbage collection is still way too difficult</b>. The biggest problem is the inability to track SSA values - it requires the frontend to generate very inefficient and error-prone code, manually spilling SSA values to the stack around nearly every function call. I've written proposals for improving the situation, which I won't repeat here - but realistically there's no way that I am ever going to have time learn to enough about LLVM's code generation passes to implement something like this myself.</div>
<div><br></div><div>Another area which I'd like to see supported is stack walking - that is, starting from the current call frame, iterate through all of the call frames above it. Currently the only way to do this is via platform-specific assembly language - I'd think it would be relatively simple to make an intrinsic that does this. (Note that the current stack intrinsics are unusable, because they are (a) unreliable, and (b) inefficient. Taking an integer index of a stack frame as a parameter is not the right way to do it.)</div>
<div><br></div><div>I have to say, if there's any single issue that could make me give up on LLVM and switch over to using something like a JVM, it would be this - because as far as I can tell, LLVM's garbage collection features are in exactly the same state they were in when I started working with LLVM four years ago.</div>
</div></blockquote><div><br></div></div><div>JVM implementers have done a lot of work in their respective compiler backend to support moving collectors. I'm not aware of any efficient solution short of making the backend aware of object pointer types. i.e. Machine operands need to carry these types.</div>
<div><br></div></div></div></blockquote><div>So, I have a working implementation of a moving collector that uses the LLVM intrinsics. This consists of three components:</div><div><ul><li>My frontend code that tells LLVM which data values contain traceable roots.</li>
<li>My custom GCStrategy class which uses information about the roots to generate a stack map for every function identifying the relative offset of each root.</li><li>My runtime library which traverses those stack maps.</li>
</ul><div>All of this is pretty standard stuff. What's nice about it is that LLVM doesn't really need to know any of the details of my garbage collection algorithm, or even what a root looks like - I'm sure you saw my earlier discussion of discriminated unions as roots, where the collector needs access to the discriminator field to determine whether the payload is a pointer or not. Since the llvm.gcroot intrinsic causes the root to be passed to the strategy with no assumptions about its internal structure, that gives me a lot of flexibility.</div>
</div><div><br></div><div>For having SSA values as roots, the situation is obviously more complex. One simplifying assumption is that we don't try and trace register values directly (because a structure may have been 'sliced' into multiple registers and it would be hard for the GCStrategy to handle that), but rather do what we do now and say that the collector can only trace objects which live in memory. Thus, we still need to spill SSA values into memory and reload them - but that work should be done by LLVM and not by the frontend, because LLVM has far more detailed knowledge of value lifetimes.</div>
<div><br></div><div>The other hard bit is how to 'mark' arbitrary values as roots. Right now values are marked using the llvm.gcroot intrinsics, but that only works on allocas. My current thinking is that we add a second bit to the "Struct" type (the first bit being isPacked) called "isRoot". If you want to declare a pointer as a root, then wrap it in a struct having that bit set - so you have to add an extra 0 into your GEP to get the value out, but that's trivial. Since a struct can contain any other data type, it makes it easy to create roots having any desired structure. Again, these get communicated from the frontend to the strategy pass without interpretation by LLVM, except for one stipulation, which is that the structure isn't 'sliced', that the offset given to the strategy pass points to a complete copy of the struct.</div>
<div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div style="word-wrap:break-word"><div><div></div><div>For stack walking, what do you need in addition to DWARF unwind? Or is generating correct unwind tables the problem? I'm not sure what stack intrinsics you mean... returnaddress and frameaddress? They don't always work if you provide the necessary target options? It almost sounds like you want more control than libunwind provides? Or do you want more efficiency?</div>
<div><br></div></div></div></blockquote><div>Here's what my stack walker for x86 platforms looks like now:</div><div><br></div></div><blockquote style="margin:0 0 0 40px;border:none;padding:0px">
<div class="gmail_quote"><div><div><font face="'courier new', monospace">struct CallFrame {</font></div></div></div><div class="gmail_quote"><div><div><font face="'courier new', monospace"> CallFrame * prevFrame;</font></div>
</div></div><div class="gmail_quote"><div><div><font face="'courier new', monospace"> void * returnAddr;</font></div></div></div><div class="gmail_quote"><div><div><font face="'courier new', monospace">};</font></div>
</div></div><div class="gmail_quote"><div><div><font face="'courier new', monospace"><br></font></div></div></div><div class="gmail_quote"><div><div><font face="'courier new', monospace">void GC_traceStack(tart_object * traceAction) {</font></div>
</div></div><div class="gmail_quote"><div><div><font face="'courier new', monospace"> CallFrame * framePtr;</font></div></div></div><div class="gmail_quote"><div><div><font face="'courier new', monospace"> #if _MSC_VER</font></div>
</div></div><div class="gmail_quote"><div><div><font face="'courier new', monospace"> #if SIZEOF_VOID_PTR == 4</font></div></div></div><div class="gmail_quote"><div><div><font face="'courier new', monospace"> __asm {</font></div>
</div></div><div class="gmail_quote"><div><div><font face="'courier new', monospace"> mov framePtr, ebp</font></div></div></div><div class="gmail_quote"><div><div><font face="'courier new', monospace"> }</font></div>
</div></div><div class="gmail_quote"><div><div><font face="'courier new', monospace"> #else</font></div></div></div><div class="gmail_quote"><div><div><font face="'courier new', monospace"> __asm {</font></div>
</div></div><div class="gmail_quote"><div><div><font face="'courier new', monospace"> mov framePtr, rbp</font></div></div></div><div class="gmail_quote"><div><div><font face="'courier new', monospace"> }</font></div>
</div></div><div class="gmail_quote"><div><div><font face="'courier new', monospace"> #endif</font></div></div></div><div class="gmail_quote"><div><div><font face="'courier new', monospace"> #else</font></div>
</div></div><div class="gmail_quote"><div><div><font face="'courier new', monospace"> #if SIZEOF_VOID_PTR == 4</font></div></div></div><div class="gmail_quote"><div><div><font face="'courier new', monospace"> __asm__("movl %%ebp, %0" :"=r"(framePtr));</font></div>
</div></div><div class="gmail_quote"><div><div><font face="'courier new', monospace"> #else</font></div></div></div><div class="gmail_quote"><div><div><font face="'courier new', monospace"> __asm__("movq %%rbp, %0" :"=r"(framePtr));</font></div>
</div></div><div class="gmail_quote"><div><div><font face="'courier new', monospace"> #endif</font></div></div></div><div class="gmail_quote"><div><div><font face="'courier new', monospace"> #endif</font></div>
</div></div><div class="gmail_quote"><div><div><font face="'courier new', monospace"><br></font></div></div></div><div class="gmail_quote"><div><div><font face="'courier new', monospace"> while (framePtr != NULL) {</font></div>
</div></div><div class="gmail_quote"><div><div><font face="'courier new', monospace"> void * returnAddr = framePtr->returnAddr;</font></div></div></div><div class="gmail_quote"><div>
<div><font face="'courier new', monospace"> framePtr = framePtr->prevFrame;</font></div></div></div><div class="gmail_quote"><div><div><font face="'courier new', monospace"> TraceDescriptor * tdesc = GC_lookupStackFrameDesc(returnAddr);</font></div>
</div></div><div class="gmail_quote"><div><div><font face="'courier new', monospace"> if (tdesc != NULL) {</font></div></div></div><div class="gmail_quote"><div><div><font face="'courier new', monospace"> TraceAction_traceDescriptors(traceAction, (void *)framePtr, tdesc);</font></div>
</div></div><div class="gmail_quote"><div><div><font face="'courier new', monospace"> }</font></div></div></div><div class="gmail_quote"><div><div><font face="'courier new', monospace"> }</font></div>
</div></div><div class="gmail_quote"><div><div><font face="'courier new', monospace">}</font></div></div></div></blockquote><div class="gmail_quote"><div><div><br></div></div><div>Basically it gets the bp register as a pointer, and treats it as the head of a linked list. It iterates through the list nodes until it finds NULL. For each node, it finds the return address (which is stored next to the node pointer), and looks that up in a map which returns the stack frame descriptor for that function. As you can see this is extremely simple and fast.</div>
<div><br></div><div>If I were designing a set of llvm intrinsics to replicate this, I would have three functions: llvm.callframe.current() simply returns the value of the bp register; llvm.callframe.next() takes the address of the previous stack frame and returns its parent; and llvm.callframe.returnaddress() takes the address of a call frame and returns the associated return address. These three intrinsics should (I hope) be implementable on any platform that LLVM targets, and would (I would think) each lower into a single instruction.</div>
<div><br></div><div>This would avoid me having to have a different set of inline assembly for each different processor family that LLVM supports.</div>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div style="word-wrap:break-word"><div><div><blockquote type="cite"><div><div><b>Light-weight coroutines</b> would be a "nice to have", as would better <b>concurrency primitives</b>. </div>
</div></blockquote><div><br></div></div><div>This could be interesting. Can you explain in more detail or just point me to some examples?</div></div><div><div><br></div></div></div></blockquote><div>I'm thinking of the kind of things that Go or IBM's X10 language does, or possibly Python's generators. Each language is of course going to create its own model of concurrency, but that model is going to be created from lower-level primitives that are either provided by LLVM (things like stack-swapping and thread-local variables) or provided by the various operating system libraries (thread creation and semaphores and such.)</div>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div style="word-wrap:break-word"><div><div><blockquote type="cite"><div>
<div>There's been a lot of discussion about divide-by-zero errors and other <b>non-declared exceptions</b>. Having this available would be a great help.</div></div></blockquote></div></div>What is a non-declared exception (no throw statement in the source code?), and do you think something is missing from LLVM IR? I don't see any difficulty expressing Java/C# exceptions in LLVM IR. Do you want to build high-level language semantics into LLVM IR to avoid duplicating effort across Java/C#/Tart frontends? Or do you want better optimization/codegen in these cases (language-friendly backend)?<div>
<div><div><br></div></div></div></div></blockquote><div>There's been several threads on this lately, and I am by no means an expert in this area, but I do understand that the basic problem of jumping out from the middle of a basic block is a hard one to solve - but I would like to see it solved. I can work with whatever solution you guys come up with.</div>
<div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div style="word-wrap:break-word"><div><div><div></div><div>Keep in mind that adding higher level IR constructs only inhibits optimization. Java bytecode bakes language semantics into opcodes as a compression technique. It's not a form that is amenable to optimization.</div>
<div><br></div><div>Maybe what you really want is a managed language toolkit for use in frontends such as yours?</div><div><br></div><div>Backing up now to the overall topic, which of these general themes fits your experience:</div>
<div>1) You want more efficient support for implementing advanced runtime features for a given target</div><div>2) You want more ABI abstraction for easier porting across a range of targets</div><div><br></div></div></div>
</div></blockquote><div>I think #2 is more interesting to me. It's not hard to do #1 for a given platform, as there are libraries a-plenty to do most of this stuff.</div><div><br></div><div>Think of it this way: The name of the project is LLVM: "Low-Level Virtual Machine". I realize that's a bit of a misnomer, in that LLVM isn't primarily about executing code, but more about preparing code for execution. (I suppose we could call it LLISEE - Low Level Instruction Set and Execution Environment - but that's a mouthful. You could also call it LLVVM - Low Level "Virtual" Virtual Machine, in that the VM doesn't actually exist). But the "VM" part of the name seems to imply that it's not just a compiler, but a framework for execution and for building environments in which execution happens.</div>
<meta http-equiv="content-type" content="text/html; charset=utf-8"><div><br></div><div><div style="word-wrap:break-word"><div><div><div></div><div>-Andy</div>
</div></div></div></div></div><br><br clear="all"><br>-- <br>-- Talin<br>