Hi Sam,<br><br>Thanks for this + sorry for not replying earlier.<br><br>I'm afraid I'm not sure I've understood your advice. I have a working implementation for interfaces with inheritance - I use constant negative indexes into class vtables for class methods that implement methods in interfaces. These indexes are allocated at compile time either via graph coloring (if whole program is compiled as a unit) or by hashing method signatures (if parts of program are compiled separately). Any collisions arising from the hashing method are resolved on method call by thunks in any vtable slots hashed to by more than one selector.<br>
<br>Advantages of this mechanism are it's as fast as regular virtual method dispatch (except in the method signature hash collision case) and that there is no difference between calls through objects and calls through interfaces (in fact there are no interfaces as such at runtime, only references to regular objects)<br>
<br>What I'm looking to do is speed up the thunk that's called when two or more interface method signatures hash to the same slot in the vtable. Currently it just does a linear search over a compile time generated table of selector ids->method address. I think common improvements are using a self ordering list or using a binary search.<br>
<br>My conclusion is that I could probably use LLVM to generate a thunk to resolve each vtable collision to do a binary search over the expected method signatures, providing I use varargs calling convention. I'll need to do some profiling to determine if this is worthwhile, given the overhead of adding an additional parameter to both all calls to methods interfaces and methods in classes that implement methods in interfaces.<br>
<br>-- James.<br><br><div class="gmail_quote">On 31 January 2011 22:28, Samuel Crow <span dir="ltr"><<a href="mailto:samuraileumas@yahoo.com" target="_blank">samuraileumas@yahoo.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0pt 0pt 0pt 0.8ex;border-left:1px solid rgb(204, 204, 204);padding-left:1ex">
<div><div style="font-family:'times new roman','new york',times,serif;font-size:12pt"><div>Forgot to cc the list.</div><blockquote style="border-left:2px solid rgb(16, 16, 255);margin-left:5px;padding-left:5px">
<div style="font-family:times new roman,new york,times,serif;font-size:12pt"><br><div style="font-family:times new roman,new york,times,serif;font-size:12pt"><div><font face="Tahoma" size="2">----- Forwarded Message ----<br>
<b><span style="font-weight:bold">From:</span></b> Samuel Crow <<a href="mailto:samuraileumas@yahoo.com" target="_blank">samuraileumas@yahoo.com</a>><br><b><span style="font-weight:bold">To:</span></b> James Williams <<a href="mailto:junk@giantblob.com" target="_blank">junk@giantblob.com</a>><br>
<b><span style="font-weight:bold">Sent:</span></b> Mon, January 31, 2011 4:27:45 PM<br><b><span style="font-weight:bold">Subject:</span></b> Re: [LLVMdev] Compile function with limited set of registers? Jump to another function?<br>
</font><br>
</div><div style="font-family:times,serif;font-size:12pt"><div><div>Hi James,</div><div><br></div><div>If you're looking for a way to implement interface inheritance, I think the easiest way is to use double-indirection. It's slow but it does the job. You just use an array to hold the interface and have each entry point to the vtable entry for the appropriate functions in the class. Then you can treat the interface as a read-only class once the constructor is run and the interface will assign its values when the class is allocated before the invocation of the actual constructor.</div>
<div><br></div><div>The faster way to implement interfaces is with generics but that generates bigger code.</div><div><br></div><div>I hope this answers your question,</div><div><br></div><div>--Sam</div></div><blockquote style="border-left:2px solid rgb(16, 16, 255);margin-left:5px;padding-left:5px">
<div style="font-family:times new roman,new york,times,serif;font-size:12pt"><br><div style="font-family:times new roman,new york,times,serif;font-size:12pt"><div><font face="Tahoma" size="2"><b><span style="font-weight:bold">From:</span></b> James Williams <<a href="mailto:junk@giantblob.com" target="_blank">junk@giantblob.com</a>><br>
<b><span style="font-weight:bold">To:</span></b> <a href="mailto:joshuawarner32@gmail.com" target="_blank">joshuawarner32@gmail.com</a><br><b><span style="font-weight:bold">Cc:</span></b> <a href="mailto:llvmdev@cs.uiuc.edu" target="_blank">llvmdev@cs.uiuc.edu</a><br>
<b><span style="font-weight:bold">Sent:</span></b> Mon, January 31, 2011 4:01:24 PM<br><b><span style="font-weight:bold">Subject:</span></b> Re: [LLVMdev] Compile function with limited set of registers? Jump to another function?<br>
</font><br></div><div><div></div><div>
Thanks, that's a good idea - I'll have a look through the VMKit source.<br><br>-- James<br><br><div class="gmail_quote">On 31 January 2011 21:39, Joshua Warner <span dir="ltr"><<a rel="nofollow" href="mailto:joshuawarner32@gmail.com" target="_blank">joshuawarner32@gmail.com</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0pt 0pt 0pt 0.8ex;border-left:1px solid rgb(204, 204, 204);padding-left:1ex">Hi James,<div><br><div><div>I see the problem now. You might look at VMKit (a Java VM build with the LLVM JIT compiler) - I would expect it uses a similar method for resolving interface calls (the method, if I understand it correctly, is well-known in the Java world).</div>
<div><br></div><div>I've CC'd the main dev behind VMKit - he might be able to lend some insight.</div><div><br></div><font color="#888888"><div>--Joshua</div></font><div><div></div><div><br><div class="gmail_quote">
On Mon, Jan 31, 2011 at 2:24 PM, James Williams <span dir="ltr"><<a rel="nofollow" href="mailto:junk@giantblob.com" target="_blank">junk@giantblob.com</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0pt 0pt 0pt 0.8ex;border-left:1px solid rgb(204, 204, 204);padding-left:1ex">Hi Joshua,<br><br>Thanks - I was hoping that would be the case.<br><br>However, I've had a think about this since I posted to the list and I believe the
only way to handle these issues safely in LLVM IR would be to define
the thunk as varargs. I'm not sure how well LLVM handles varargs but
ideally it would all compile down to nothing since the parameters to the
the thunk would be in the same registers/stack locations as required by
the target method.<br><br>Unfortunately, varargs has some downsides: there's the additional overhead for the
extra hidden parameter to every interface method call for the parameter
count plus it doesn't (I don't think) support tail calls.<br><font color="#888888"><br>-- James</font><div><div></div><div><br> <br><div class="gmail_quote">On 27 January 2011 17:37, Joshua Warner <span dir="ltr"><<a rel="nofollow" href="mailto:joshuawarner32@gmail.com" target="_blank">joshuawarner32@gmail.com</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0pt 0pt 0pt 0.8ex;border-left:1px solid rgb(204, 204, 204);padding-left:1ex">Hi James,<div><br></div><div>I'm no expert in LLVM IR, but I think that just encoding each *actual* method invocation in the thunk as a tail call would work. This would require trusting that LLVM passes / code generators will translate down to a jump, as is normal. If the passes / code generators are smart, I see no reason that LLVM wouldn't emit code that fits your requirements. Either way, you know that your thunk will be correct - it just might not be as efficient as you want.</div>
<div><br></div><div>I would suggest experimenting with generating a thunk this way, and look at the resultant target assembly to make sure it's doing what you want.</div><div><br></div><div>-Joshua<br><br><div class="gmail_quote">
<div><div></div><div>
On Tue, Jan 25, 2011 at 2:04 AM, James Williams <span dir="ltr"><<a rel="nofollow" href="mailto:junk@giantblob.com" target="_blank">junk@giantblob.com</a>></span> wrote:<br></div></div><blockquote class="gmail_quote" style="margin:0pt 0pt 0pt 0.8ex;border-left:1px solid rgb(204, 204, 204);padding-left:1ex">
<div><div></div><div>
Hi,<br><br>Can anyone tell me, is it possible to express in LLVM IR:<br> - that, for a specific function, register allocator can use only limited set of registers? (specifically, cannot touch any registers that might contain parameters)<br>
- that stack can't be touched? (or at least must balance on exit from thunk)<br> - jump, not call, to another function leaving any received parameters unchanged in registers and on stack?<br><br>Thanks,<br>-- James Williams<br>
<br>Background:<br><br>I'm looking for some advice on implementing thunks required by my language's interface call mechanism. This is a fairly conventional arrangement where method selectors in interfaces are hashed to determine their index within a vtable and hash collisions are disambiguated at runtime by a thunk, which determines which method to call from a selector id passed as the first method parameter.<br>
<br>I'm currently using a single thunk (written in assembly) for all collisions that walks a table to determine what method to call. This works but it's inefficient and requires the a hand written thunk for each supported target.<br>
<br>I'd like to instead generate IR for a specific thunk for each vtable collisoin that does a binary search of possible selectors because this will avoid some pointer dereferences and an additional indirect call.<br>
<br>The problem is that a thunk may need to decide between methods with different signatures without disturbing parameters in registers and on the stack and then jump to, rather than call, another function:<br><br>interface X:<br>
method A(a, b)<br><br>interface Y:<br> method B(c, d, e)<br><br>class Z implements X, y:<br> method A(a, b) ...<br> method B(c, d, e) ...<br><br>X.A + Y.B happen to hash to same vtable index, say -3<br><br>This would require a thunk something like:<br>
<br>vtable[-3] = <br> thunk_Z_AorB(selector_id, ...)<br> // binary search for matching selector id:<br> if selector_id <= selector_Z_A then<br> Z.A(selector_id, ...)<br> else<br> Z.B(selector_id, ...)<br>
fi<br><br>which would ideally would compile on x64 to something like:<br><br>thunk_Z_AorB:<br> cmp $selector_Z_A, %rdi<br> jle Z.A<br> jmp Z.B <br><br><br>
<br></div></div>_______________________________________________<br>
LLVM Developers mailing list<br>
<a rel="nofollow" href="mailto:LLVMdev@cs.uiuc.edu" target="_blank">LLVMdev@cs.uiuc.edu</a><span><span> <a href="http://llvm.cs.uiuc.edu" target="_blank">http://llvm.cs.uiuc.edu</a></span></span><br><span><span>
<a href="http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev" target="_blank">http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev</a></span></span><br>
<br></blockquote></div><br></div>
</blockquote></div><br>
</div></div></blockquote></div><br></div></div></div></div>
</blockquote></div><br>
</div></div></div></div></blockquote><div></div>
</div><br>
</div></div></blockquote><div></div></div><br>
</div><br>_______________________________________________<br>
LLVM Developers mailing list<br>
<a href="mailto:LLVMdev@cs.uiuc.edu" target="_blank">LLVMdev@cs.uiuc.edu</a> <a href="http://llvm.cs.uiuc.edu" target="_blank">http://llvm.cs.uiuc.edu</a><br>
<a href="http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev" target="_blank">http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev</a><br>
<br></blockquote></div><br>