Writing a compiler to handles, but filter seems to executed in reverse
Charles Oliver Nutter
headius at headius.com
Wed Jan 3 00:48:31 UTC 2018
So I have some basic expressions working in my pseudo-compiler, and the
experiment has been interesting so far. A few things I've learned:
(for code "a = 10000; b = 20000; (a + b) > 10000", here's the assembly
output: https://gist.github.com/headius/f765260a00590fc2b4cd033b5a657e6b)
* The approach is interesting and stretches handles quite a bit, but it
takes a long time to heat up and longer to generate native code. This may
be acceptable on platforms where user code can't load new JVM bytecode
(assuming the handle impl on that platform produces decent code).
* My mechanism of using Object[] to hold local variables seems to break
escape analysis on both hotspot and graal, probably because that array
write is too opaque to escape through. The Object[] itself is also
constructed in the same compilation unit, though, that doesn't appear to
tidy up either.
* According to LogCompilation, everything inlines, including the call to my
type-checking "add" method for the "+" call here, but...
* According to PrintAssembly, the direct handles to "add" and "lt" don't
actually appear to inline. Why?
0x000000011418f1f1: movabs rcx,0x76c5065b0 ;*invokestatic linkToStatic
{reexecute=0 rethrow=0 return_oop=0}
; -
java.lang.invoke.LambdaForm$DMH/2137211482::invokeStatic_LL_L at 11
; -
java.lang.invoke.LambdaForm$BMH/522188921::reinvoke at 50
; -
java.lang.invoke.LambdaForm$BMH/522188921::reinvoke at 15
; -
java.lang.invoke.LambdaForm$MH/1973471376::identity_L at 68
; {oop(a
'java/lang/invoke/MemberName' = {method} {0x000000010efd7358} 'add'
'(Ljava/lang/Object;Ljava/lang/Object;)Ljava/lang/Object;' in
'com/headius/jruby/HandleCompiler')}
0x000000011418f1fb: mov QWORD PTR [rsp+0xb0],rax
0x000000011418f203: nop
0x000000011418f204: nop
0x000000011418f205: nop
0x000000011418f206: nop
0x000000011418f207: call 0x00000001138f2420 ; OopMap{[176]=Oop off=460}
;*invokestatic linkToStatic
{reexecute=0 rethrow=0 return_oop=0}
; -
java.lang.invoke.LambdaForm$DMH/2137211482::invokeStatic_LL_L at 11
; -
java.lang.invoke.LambdaForm$BMH/522188921::reinvoke at 50
; -
java.lang.invoke.LambdaForm$BMH/522188921::reinvoke at 15
; -
java.lang.invoke.LambdaForm$MH/1973471376::identity_L at 68
; {static_call}
0x000000011418f20c: mov rsi,rax
0x000000011418f20f: movabs rdx,0x76c511bb8 ; {oop(a 'java/lang/Long'
= 10000)}
0x000000011418f219: movabs rcx,0x76c512068 ;*invokestatic linkToStatic
{reexecute=0 rethrow=0 return_oop=0}
; -
java.lang.invoke.LambdaForm$DMH/2137211482::invokeStatic_LL_L at 11
; -
java.lang.invoke.LambdaForm$BMH/522188921::reinvoke at 50
; -
java.lang.invoke.LambdaForm$MH/1973471376::identity_L at 68
; {oop(a
'java/lang/invoke/MemberName' = {method} {0x000000010efd77d0} 'gt'
'(Ljava/lang/Object;Ljava/lang/Object;)Ljava/lang/Object;' in
'com/headius/jruby/HandleCompiler')}
0x000000011418f223: nop
0x000000011418f224: nop
0x000000011418f225: nop
0x000000011418f226: nop
0x000000011418f227: call 0x00000001138f2420 ; OopMap{off=492}
;*invokestatic linkToStatic
{reexecute=0 rethrow=0 return_oop=0}
; -
java.lang.invoke.LambdaForm$DMH/2137211482::invokeStatic_LL_L at 11
; -
java.lang.invoke.LambdaForm$BMH/522188921::reinvoke at 50
; -
java.lang.invoke.LambdaForm$MH/1973471376::identity_L at 68
; {static_call}
On Tue, Jan 2, 2018 at 3:54 PM Charles Oliver Nutter <headius at headius.com>
wrote:
> I have released invokebinder 1.11, which includes Binder.filterForward
> that guarantees left-to-right evaluation of the filters (by doing them
> individually).
>
> I'd still like to understand if this is intentional behavior in OpenJDK or
> if it is perhaps a bug.
>
> - Charlie
>
> On Tue, Jan 2, 2018 at 3:10 PM Charles Oliver Nutter <headius at headius.com>
> wrote:
>
>> Yes, I figured I would need it for that too, but this filter behavior
>> sent me off on a weird tangent.
>>
>> It is gross in code to do the filters manually in forward order, but
>> perhaps it's not actually a big deal? OpenJDK's impl applies each filter as
>> its own layer anyway.
>>
>> - Charlie
>>
>> On Tue, Jan 2, 2018 at 3:04 PM Remi Forax <forax at univ-mlv.fr> wrote:
>>
>>> You also need the loop combinator for implementing early return (the
>>> return keyword),
>>> I think i have an example of how to map a small language to a loop
>>> combinator somewhere,
>>> i will try to find that (or rewrite it) tomorrow.
>>>
>>> cheers,
>>> Rémi
>>>
>>> ------------------------------
>>>
>>> *De: *"Charles Oliver Nutter" <headius at headius.com>
>>> *À: *"Da Vinci Machine Project" <mlvm-dev at openjdk.java.net>
>>> *Envoyé: *Mardi 2 Janvier 2018 21:36:33
>>> *Objet: *Re: Writing a compiler to handles, but filter seems to
>>> executed in reverse
>>>
>>> An alternative workaround: I do the filters myself, manually, in the
>>> order that I want them to executed. Also gross.
>>>
>>> On Tue, Jan 2, 2018 at 2:35 PM Charles Oliver Nutter <
>>> headius at headius.com> wrote:
>>>
>>>> Ahh I believe I see it now.
>>>> filterArguments starts with the first filter, and wraps the incoming
>>>> target handle with each in turn. However, because it's starting at the
>>>> target, you get the filters stacked up in reverse order:
>>>>
>>>> filter(target, 0, a, b, c, d)
>>>>
>>>> ends up as
>>>>
>>>> d_filter(c_filter(b_filter(a_filter(target))))
>>>>
>>>> And so naturally when invoked, they execute in reverse order.
>>>>
>>>> This seems I am surprised we have not run into this as a problem, but I
>>>> believe most of my uses of filter in JRuby have been pure functions where
>>>> order was not important (except for error conditions).
>>>>
>>>> Now in looking for a fix, I've run into the nasty workaround required
>>>> to get filters to execute in the correct order: you have to reverse the
>>>> filters, and then reverse the results again. This is far from desirable,
>>>> since it requires at least one permute to put the results back in proper
>>>> order.
>>>>
>>>> Is there a good justification for doing it this way, rather than having
>>>> filterArguments start with the *last* filter nearest the target?
>>>>
>>>> - Charlie
>>>>
>>>> On Tue, Jan 2, 2018 at 2:17 PM Charles Oliver Nutter <
>>>> headius at headius.com> wrote:
>>>>
>>>>> Hello all, long time no write!
>>>>> I'm finally playing with writing a "compiler" for JRuby that uses only
>>>>> method handles to represent code structure. For most simple expressions,
>>>>> this obviously works well. However I'm having trouble with blocks of code
>>>>> that contain multiple expressions.
>>>>>
>>>>> Starting with the standard call signature through the handle tree, we
>>>>> have a basic (Object[])Object type. The Object[] contains local variable
>>>>> state for the script, and will be as wide as there are local variables. AST
>>>>> nodes are basically compiled into little functions that take in the
>>>>> variable state and produce a value. In this way, every expression in the
>>>>> tree can be compiled, including local variable sets and gets, loops, and so
>>>>> on.
>>>>>
>>>>> Now the tricky bit...
>>>>>
>>>>> The root node for a given script contains one or more expressions that
>>>>> should be executed in sequence, with the final result being returned. The
>>>>> way I'm handling this in method handles is as follows (invokebinder code
>>>>> but hopefully easy to read):
>>>>>
>>>>> MethodHandle[] handles =
>>>>> Arrays
>>>>> .stream(rootNode.children())
>>>>> .map(node -> compile(node))
>>>>> .toArray(n -> new MethodHandle[n]);
>>>>>
>>>>> return Binder.from(Object.class, Object[].class)
>>>>> .permute(new int[handles.length])
>>>>> .filter(0, handles)
>>>>> .drop(0, handles.length - 1)
>>>>> .identity();
>>>>>
>>>>> In pseudo-code, this basically duplicates the Object[] as many times
>>>>> as there are lines of code to execute, and then uses filterArguments to
>>>>> evaluate each in turn. Then everything but the last result is culled and
>>>>> the final result is returned.
>>>>>
>>>>> Unfortunately, this doesn't work right: filterArguments appears to
>>>>> execute in reverse order. When I try to run a simple script like "a = 1; a"
>>>>> the "a" value comes back null, because it is executed first.
>>>>>
>>>>> Is this expected? Do filters, when executed, actually process from the
>>>>> last argument back, rather than the first argument forward?
>>>>>
>>>>> Note: I know this would be possible to do with guaranteed ordering
>>>>> using the new loop combinators in 9. I'm working up to that for examples
>>>>> for a talk.
>>>>>
>>>>> - Charlie
>>>>>
>>>>>
>>> _______________________________________________
>>> mlvm-dev mailing list
>>> mlvm-dev at openjdk.java.net
>>> http://mail.openjdk.java.net/mailman/listinfo/mlvm-dev
>>>
>>> _______________________________________________
>>> mlvm-dev mailing list
>>> mlvm-dev at openjdk.java.net
>>> http://mail.openjdk.java.net/mailman/listinfo/mlvm-dev
>>>
>>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.openjdk.java.net/pipermail/mlvm-dev/attachments/20180103/5eb39df9/attachment-0001.html>
More information about the mlvm-dev
mailing list