llvm dev - Jan 2011 - [LLVMdev] Compile function with limited set of registers? Jump to another function?

Hi James,

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).

I've CC'd the main dev behind VMKit - he might be able to lend some
insight.

--Joshua

On Mon, Jan 31, 2011 at 2:24 PM, James Williams <junk at giantblob.com>
wrote:
> Hi Joshua,
>
> Thanks - I was hoping that would be the case.
>
> 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.
>
> 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.
>
> -- James
>
>
> On 27 January 2011 17:37, Joshua Warner <joshuawarner32 at gmail.com>
wrote:
>
>> Hi James,
>>
>> 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.
>>
>> 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.
>>
>> -Joshua
>>
>>  On Tue, Jan 25, 2011 at 2:04 AM, James Williams <junk at
giantblob.com>wrote:
>>
>>>  Hi,
>>>
>>> Can anyone tell me, is it possible to express in LLVM IR:
>>>   - that, for a specific function, register allocator can use only
>>> limited set of registers? (specifically, cannot touch any registers
that
>>> might contain parameters)
>>>   - that stack can't be touched? (or at least must balance on
exit from
>>> thunk)
>>>   - jump, not call, to another function leaving any received
parameters
>>> unchanged in registers and on stack?
>>>
>>> Thanks,
>>> -- James Williams
>>>
>>> Background:
>>>
>>> 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.
>>>
>>> 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.
>>>
>>> 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.
>>>
>>> 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:
>>>
>>> interface X:
>>>   method A(a, b)
>>>
>>> interface Y:
>>>   method B(c, d, e)
>>>
>>> class Z implements X, y:
>>>   method A(a, b) ...
>>>   method B(c, d, e) ...
>>>
>>> X.A + Y.B happen to hash to same vtable index, say -3
>>>
>>> This would require a thunk something like:
>>>
>>> vtable[-3] >>>   thunk_Z_AorB(selector_id, ...)
>>>     // binary search for matching selector id:
>>>     if selector_id <= selector_Z_A then
>>>       Z.A(selector_id, ...)
>>>     else
>>>       Z.B(selector_id, ...)
>>>     fi
>>>
>>> which would ideally would compile on x64 to something like:
>>>
>>> thunk_Z_AorB:
>>>   cmp $selector_Z_A, %rdi
>>>   jle Z.A
>>>   jmp Z.B
>>>
>>>
>>>
>>> _______________________________________________
>>> LLVM Developers mailing list
>>> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
>>> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>>>
>>>
>>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20110131/356a77a4/attachment.html>

Thanks, that's a good idea - I'll have a look through the VMKit source.

-- James

On 31 January 2011 21:39, Joshua Warner <joshuawarner32 at gmail.com>
wrote:
> Hi James,
>
> 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).
>
> I've CC'd the main dev behind VMKit - he might be able to lend some
> insight.
>
> --Joshua
>
> On Mon, Jan 31, 2011 at 2:24 PM, James Williams <junk at
giantblob.com>wrote:
>
>> Hi Joshua,
>>
>> Thanks - I was hoping that would be the case.
>>
>> 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.
>>
>> 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.
>>
>> -- James
>>
>>
>> On 27 January 2011 17:37, Joshua Warner <joshuawarner32 at
gmail.com> wrote:
>>
>>> Hi James,
>>>
>>> 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.
>>>
>>> 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.
>>>
>>> -Joshua
>>>
>>>  On Tue, Jan 25, 2011 at 2:04 AM, James Williams <junk at
giantblob.com>wrote:
>>>
>>>>  Hi,
>>>>
>>>> Can anyone tell me, is it possible to express in LLVM IR:
>>>>   - that, for a specific function, register allocator can use
only
>>>> limited set of registers? (specifically, cannot touch any
registers that
>>>> might contain parameters)
>>>>   - that stack can't be touched? (or at least must balance
on exit from
>>>> thunk)
>>>>   - jump, not call, to another function leaving any received
parameters
>>>> unchanged in registers and on stack?
>>>>
>>>> Thanks,
>>>> -- James Williams
>>>>
>>>> Background:
>>>>
>>>> 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.
>>>>
>>>> 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.
>>>>
>>>> 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.
>>>>
>>>> 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:
>>>>
>>>> interface X:
>>>>   method A(a, b)
>>>>
>>>> interface Y:
>>>>   method B(c, d, e)
>>>>
>>>> class Z implements X, y:
>>>>   method A(a, b) ...
>>>>   method B(c, d, e) ...
>>>>
>>>> X.A + Y.B happen to hash to same vtable index, say -3
>>>>
>>>> This would require a thunk something like:
>>>>
>>>> vtable[-3] >>>>   thunk_Z_AorB(selector_id, ...)
>>>>     // binary search for matching selector id:
>>>>     if selector_id <= selector_Z_A then
>>>>       Z.A(selector_id, ...)
>>>>     else
>>>>       Z.B(selector_id, ...)
>>>>     fi
>>>>
>>>> which would ideally would compile on x64 to something like:
>>>>
>>>> thunk_Z_AorB:
>>>>   cmp $selector_Z_A, %rdi
>>>>   jle Z.A
>>>>   jmp Z.B
>>>>
>>>>
>>>>
>>>> _______________________________________________
>>>> LLVM Developers mailing list
>>>> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
>>>> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>>>>
>>>>
>>>
>>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20110131/e68303e9/attachment.html>

Forgot to cc the list.
>
>----- Forwarded Message ----
>From: Samuel Crow <samuraileumas at yahoo.com>
>To: James Williams <junk at giantblob.com>
>Sent: Mon, January 31, 2011 4:27:45 PM
>Subject: Re: [LLVMdev] Compile function with limited set of registers? Jump
to
>another function?
>
>
>Hi James,
>
>
>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.
>
>
>The faster way to implement interfaces is with generics but that generates 
>bigger code.
>
>
>I hope this answers your question,
>
>
>--Sam
>
>>
>>From: James Williams <junk at giantblob.com>
>>To: joshuawarner32 at gmail.com
>>Cc: llvmdev at cs.uiuc.edu
>>Sent: Mon, January 31, 2011 4:01:24 PM
>>Subject: Re: [LLVMdev] Compile function with limited set of registers?
Jump to
>>another function?
>>
>>Thanks, that's a good idea - I'll have a look through the VMKit
source.
>>
>>-- James
>>
>>
>>On 31 January 2011 21:39, Joshua Warner <joshuawarner32 at
gmail.com> wrote:
>>
>>Hi James,
>>>
>>>
>>>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).
>>>
>>>
>>>I've CC'd the main dev behind VMKit - he might be able to
lend some insight.
>>>
>>>--Joshua
>>>
>>>
>>>On Mon, Jan 31, 2011 at 2:24 PM, James Williams <junk at
giantblob.com> wrote:
>>>
>>>Hi Joshua,
>>>>
>>>>Thanks - I was hoping that would be the case.
>>>>
>>>>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.
>>>>
>>>>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.
>>>>
>>>>-- James
>>>>
>>>> 
>>>>
>>>>On 27 January 2011 17:37, Joshua Warner <joshuawarner32 at
gmail.com> wrote:
>>>>
>>>>Hi James,
>>>>>
>>>>>
>>>>>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.
>>>>>
>>>>>
>>>>>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.
>>>>>
>>>>>
>>>>>-Joshua
>>>>>
>>>>>
>>>>>On Tue, Jan 25, 2011 at 2:04 AM, James Williams <junk at
giantblob.com> wrote:
>>>>>
>>>>>Hi,
>>>>>>
>>>>>>Can anyone tell me, is it possible to express in LLVM
IR:
>>>>>>  - that, for a specific function, register allocator
can use only limited set
>>>>>>of registers? (specifically, cannot touch any registers
that might contain
>>>>>>parameters)
>>>>>>  - that stack can't be touched? (or at least must
balance on exit from
>>>thunk)
>>>>>>  - jump, not call, to another function leaving any
received parameters
>>>>>>unchanged in registers and on stack?
>>>>>>
>>>>>>Thanks,
>>>>>>-- James Williams
>>>>>>
>>>>>>Background:
>>>>>>
>>>>>>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.
>>>>>>
>>>>>>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.
>>>>>>
>>>>>>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.
>>>>>>
>>>>>>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:
>>>>>>
>>>>>>interface X:
>>>>>>  method A(a, b)
>>>>>>
>>>>>>interface Y:
>>>>>>  method B(c, d, e)
>>>>>>
>>>>>>class Z implements X, y:
>>>>>>  method A(a, b) ...
>>>>>>  method B(c, d, e) ...
>>>>>>
>>>>>>X.A + Y.B happen to hash to same vtable index, say -3
>>>>>>
>>>>>>This would require a thunk something like:
>>>>>>
>>>>>>vtable[-3] = 
>>>>>>  thunk_Z_AorB(selector_id, ...)
>>>>>>    // binary search for matching selector id:
>>>>>>    if selector_id <= selector_Z_A then
>>>>>>      Z.A(selector_id, ...)
>>>>>>    else
>>>>>>      Z.B(selector_id, ...)
>>>>>>    fi
>>>>>>
>>>>>>which would ideally would compile on x64 to something
like:
>>>>>>
>>>>>>thunk_Z_AorB:
>>>>>>  cmp $selector_Z_A, %rdi
>>>>>>  jle Z.A
>>>>>>  jmp Z.B 
>>>>>>
>>>>>>
>>>>>>
>>>>>>_______________________________________________
>>>>>>LLVM Developers mailing list
>>>>>>LLVMdev at cs.uiuc.edu        http://llvm.cs.uiuc.edu
>>>>>>http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>>>>>>
>>>>>>
>>>>>
>>>>
>>>
>>
>

      
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20110131/9e150722/attachment.html>

Hi James,

Joshua is right, what you're trying to accomplish is quite known in the Java
VM world (
http://domino.research.ibm.com/comm/research_people.nsf/pages/dgrove.oopsla01.html
).

In order to express the "thunk" code in LLVM you need a full control
of how
registers are used (because otherwise they would mess up with the
arguments). I haven't investigated enough to know if that's possible
today
in LLVM (I think it wasn't a few years ago when I added the optimization).
So what I ended up with was a generic IR that walks the interface table of
an object and detects collisions. The IR was inline in the caller to make
sure that arguments in registers are not overriden.

This may not be the best approach today, but I believe it was the easiest
way to have something efficient at that point.

Cheers,
Nicolas

On Mon, Jan 31, 2011 at 11:01 PM, James Williams <junk at giantblob.com>
wrote:
> Thanks, that's a good idea - I'll have a look through the VMKit
source.
>
> -- James
>
>
> On 31 January 2011 21:39, Joshua Warner <joshuawarner32 at gmail.com>
wrote:
>
>> Hi James,
>>
>> 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).
>>
>> I've CC'd the main dev behind VMKit - he might be able to lend
some
>> insight.
>>
>> --Joshua
>>
>> On Mon, Jan 31, 2011 at 2:24 PM, James Williams <junk at
giantblob.com>wrote:
>>
>>> Hi Joshua,
>>>
>>> Thanks - I was hoping that would be the case.
>>>
>>> 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.
>>>
>>> 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.
>>>
>>> -- James
>>>
>>>
>>> On 27 January 2011 17:37, Joshua Warner <joshuawarner32 at
gmail.com>wrote:
>>>
>>>> Hi James,
>>>>
>>>> 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.
>>>>
>>>> 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.
>>>>
>>>> -Joshua
>>>>
>>>>  On Tue, Jan 25, 2011 at 2:04 AM, James Williams <junk at
giantblob.com>wrote:
>>>>
>>>>>  Hi,
>>>>>
>>>>> Can anyone tell me, is it possible to express in LLVM IR:
>>>>>   - that, for a specific function, register allocator can
use only
>>>>> limited set of registers? (specifically, cannot touch any
registers that
>>>>> might contain parameters)
>>>>>   - that stack can't be touched? (or at least must
balance on exit from
>>>>> thunk)
>>>>>   - jump, not call, to another function leaving any
received parameters
>>>>> unchanged in registers and on stack?
>>>>>
>>>>> Thanks,
>>>>> -- James Williams
>>>>>
>>>>> Background:
>>>>>
>>>>> 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.
>>>>>
>>>>> 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.
>>>>>
>>>>> 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.
>>>>>
>>>>> 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:
>>>>>
>>>>> interface X:
>>>>>   method A(a, b)
>>>>>
>>>>> interface Y:
>>>>>   method B(c, d, e)
>>>>>
>>>>> class Z implements X, y:
>>>>>   method A(a, b) ...
>>>>>   method B(c, d, e) ...
>>>>>
>>>>> X.A + Y.B happen to hash to same vtable index, say -3
>>>>>
>>>>> This would require a thunk something like:
>>>>>
>>>>> vtable[-3] >>>>>   thunk_Z_AorB(selector_id,
...)
>>>>>     // binary search for matching selector id:
>>>>>     if selector_id <= selector_Z_A then
>>>>>       Z.A(selector_id, ...)
>>>>>     else
>>>>>       Z.B(selector_id, ...)
>>>>>     fi
>>>>>
>>>>> which would ideally would compile on x64 to something like:
>>>>>
>>>>> thunk_Z_AorB:
>>>>>   cmp $selector_Z_A, %rdi
>>>>>   jle Z.A
>>>>>   jmp Z.B
>>>>>
>>>>>
>>>>>
>>>>> _______________________________________________
>>>>> LLVM Developers mailing list
>>>>> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
>>>>> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>>>>>
>>>>>
>>>>
>>>
>>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20110202/daca0361/attachment.html>