wip-rtl, solstice edition

wip-rtl, solstice edition

[Andy Wingo]

Hello all,

A few changes in master and wip-rtl.

First of all, I have changed the on-disk format for .go files to be ELF,
even for the old Guile 2.0-style bytecode.  This increases the file size
somewhat, though the memory footprint is the same.  What it gives us,
though, is extensibility.

In that regard, I have rebased wip-rtl on top of master.  If you have
existing wip-rtl checkouts, you'll have to be sure that they are
current.

Finally, I merged in the DWARF parser from guile-dlhacks.  It's not used
yet.  As I said in my mail to Noah, my first idea is to emit DWARF based
on macro-instructions in the assembly.  We'll see.

For me, my next steps are:

 1) Convert the ELF parser and linker to use symbols instead of the raw
    ELF codes, as the DWARF parser does.  It's more convenient and not
    significantly different, performance-wise.

 2) Add enough debugging information so that procedure-name works, and
    that we can determine the bounds of procedures.  (Determining where
    a procedure ends is a precondition for being able to disassemble
    it!)

 3) Create tests for all of the opcodes.  This task is somewhat
    decoupled from the previous tasks; if people want to help out, see
    libguile/vm-engine.c and test-suite/tests/rtl.test.

 4) Update the tools (debugger, frame printer, etc) to be able to deal
    with the new debugging format.

There are also some fundamentals of the VM that need nailing down.  One
is that the VM needs some more operations that take immediate operands.
That's pretty easy.  We should also think about inline caches.  It seems
like the way to go for toplevel calls and references, though it will
take some thinking for it to be reasonable in a VM.

But after those things are done, we still need to bridge the gap between
Tree-IL and RTL assembly.  We will probably have to scrap GLIL, though I
can't tell yet.

So, that's the status.  Apologies for there being no overview yet; I
will try to write something about that soon.  I reckon we are about a
month away from a VM that works well, and has good debugging
information, and two or three months away from a merge to master
(meaning, we compile all of Scheme).  At that point we could look to
release the first 2.2 beta release, aiming at a final 2.2 sometime early
next year.

Regards,

Andy
-- 
http://wingolog.org/

Re: wip-rtl, solstice edition

[Noah Lavine]

Hello,

The new VM looks great.

> But after those things are done, we still need to bridge the gap between
> Tree-IL and RTL assembly.  We will probably have to scrap GLIL, though I
> can't tell yet.

As I said, I've been working on a compiler from Tree-IL directly to
RTL. So far, I have not found that I really wanted another layer in
between the RTL and the Tree-IL.

It looks to me like the GLIL->assembly compiler spends most of its
effort building constant tables, which I believe the RTL assembler
does in the rtl branch. So GLIL wouldn't be abstracting over much
compared to plain RTL, unless you moved that out of the assembler, or
made the GLIL-equivalent higher level in some way.

> So, that's the status.  Apologies for there being no overview yet; I
> will try to write something about that soon.  I reckon we are about a
> month away from a VM that works well, and has good debugging
> information, and two or three months away from a merge to master
> (meaning, we compile all of Scheme).  At that point we could look to
> release the first 2.2 beta release, aiming at a final 2.2 sometime early
> next year.

This is very exciting! Thanks for working on the new VM.

Noah

Re: wip-rtl, solstice edition

[Andy Wingo]

Hi Noah,

Thanks for the thoughts and the hack!

On Sat 23 Jun 2012 16:03, Noah Lavine <noah.b.lavine@gmail.com> writes:

> It looks to me like the GLIL->assembly compiler spends most of its
> effort building constant tables, which I believe the RTL assembler
> does in the rtl branch.

The other things that it does, for the record:

 1) Allocate variable cache cells.  Related to the constant table, so
    perhaps the assembler can take care of this.

 2) Assembling the "meta" procedure.  Given that the debugging will be
    significantly different in the rtl branch, again the assembler might
    be able to understand inline debugging macro-instructions.

 3) Some instruction selection, based on whether the indexes of
    variables are in range or not.  Again, the assembler can do this.

So yes, I guess you are right.

Here are some things that I would like to be able to do, that we can't
do yet easily:

 1) Reorder basic blocks.  We should be able to do a topological sort of
    the blocks based on the dominator tree, and put cold blocks like
    bailouts at the end of a function.

 2) Simplify the control-flow graph.  Sometimes we have blocks that
    basically just jump to another block without doing anything.  We
    need to be able to reason about jumps.  We also need to be able to
    turn two-jump loops into one-jump loops.

 3) Fix order of evaluation.  A lower-level transformation could do
    that: either to CPS/ANF in Tree-IL itself, or to SSA.

 4) Loop optimizations.  For example, loop peeling: unrolling the first
    round through a loop can let CSE do a great job in the loop.  Loop
    peeling + CSE is basically LICM.

All of these things seem to indicate that we need some changes to
Tree-IL.  I don't know exactly what though, and this is something we can
work on after having a working tree-il->rtl compiler.

As food for thought, I really liked Kennedy's "Compiling with
Continuations, Continued" paper:

  http://research.microsoft.com/pubs/64044/compilingwithcontinuationscontinued.pdf

Happy hacking,

Andy
-- 
http://wingolog.org/

Re: wip-rtl, solstice edition

[Ludovic Courtès]

Hello, and happy Solstice!  :-)

Andy Wingo <wingo@pobox.com> skribis:

> First of all, I have changed the on-disk format for .go files to be ELF,
> even for the old Guile 2.0-style bytecode.  This increases the file size
> somewhat, though the memory footprint is the same.  What it gives us,
> though, is extensibility.

Neat.

> For me, my next steps are:
>
>  1) Convert the ELF parser and linker to use symbols instead of the raw
>     ELF codes, as the DWARF parser does.  It's more convenient and not
>     significantly different, performance-wise.

Yes.  The one at
<https://gitorious.org/guile-dlhacks/guile-dlhacks/blobs/master/dlhacks/elf.scm>
could use more comments, docstrings, and tests, if you ask me.  :-)

>  2) Add enough debugging information so that procedure-name works, and
>     that we can determine the bounds of procedures.  (Determining where
>     a procedure ends is a precondition for being able to disassemble
>     it!)
>
>  3) Create tests for all of the opcodes.  This task is somewhat
>     decoupled from the previous tasks; if people want to help out, see
>     libguile/vm-engine.c and test-suite/tests/rtl.test.

I’m afraid that writing tests after code may either not happen, or may
be unable to uncover bugs if it’s written by the same person, or may be
difficult for someone without a clear picture of the API.

WDYT?

That said, I’ll look into all this as time permits, and see what I can
contribute myself.

>  4) Update the tools (debugger, frame printer, etc) to be able to deal
>     with the new debugging format.

Sounds like a nice plan!

> So, that's the status.  Apologies for there being no overview yet; I
> will try to write something about that soon.  I reckon we are about a
> month away from a VM that works well, and has good debugging
> information, and two or three months away from a merge to master
> (meaning, we compile all of Scheme).  At that point we could look to
> release the first 2.2 beta release, aiming at a final 2.2 sometime early
> next year.

Didn’t you once say “2.2 will have native compilation”?  ;-)

Seriously though, that seems like a good plan.  I wonder what Noah’s
attempts at JITing the 2.0 bytecode would have achieved, though, if we
think of both JIT and the new VM as an “interim solution” before AOT
native compilation.

Thanks for the update, and thanks for all the work!

Ludo’.

Re: wip-rtl, solstice edition

[Noah Lavine]

Hello,

> Seriously though, that seems like a good plan.  I wonder what Noah’s
> attempts at JITing the 2.0 bytecode would have achieved, though, if we
> think of both JIT and the new VM as an “interim solution” before AOT
> native compilation.

I can't remember the last email I sent about that, but I think I might
have dropped the ball here, so let me say what the current status of
the project was. The JIT compiler worked fine. You could JIT-compile a
function and have Guile automatically run the JITted code. The real
problem was writing the JIT compiler - the one I had only supported
four instructions, because I just wanted to prove I could integrate it
with the rest of Guile.

I sent another email recently about different ways to make the JITter
understand all of the bytecode, but at the time, I thought I would
have to parse the C definition of the VM and generate the JITter from
that in order for it to be merged into Guile. I never got over that
hurdle. If we are willing to generate both the VM and the JITter from
another source, it's possible that I could revive my old JIT branch.

However, I'm still not sure if that's the best way there. Having the
assembler written in Scheme gives you an easier path towards
all-Scheme native compilation, which you'd probably want for an AOT
compiler.

Noah

Re: wip-rtl, solstice edition

[Ludovic Courtès]

Hello,

Noah Lavine <noah.b.lavine@gmail.com> skribis:

> I sent another email recently about different ways to make the JITter
> understand all of the bytecode, but at the time, I thought I would
> have to parse the C definition of the VM and generate the JITter from
> that in order for it to be merged into Guile. I never got over that
> hurdle. If we are willing to generate both the VM and the JITter from
> another source, it's possible that I could revive my old JIT branch.

I think it could be beneficial in terms of hackability and maintenance
to have instructions defined as slightly abstracted s-exps.  Now, if
it’s only used to generate vm-engine.c & co., it’s probably too much
work for what it’s worth.

> However, I'm still not sure if that's the best way there. Having the
> assembler written in Scheme gives you an easier path towards
> all-Scheme native compilation, which you'd probably want for an AOT
> compiler.

Yeah, especially since it could easily be used at run-time too.

Thanks,
Ludo’.

Re: wip-rtl, solstice edition

[Andy Wingo]

On Mon 25 Jun 2012 22:52, ludo@gnu.org (Ludovic Courtès) writes:

>>  1) Convert the ELF parser and linker to use symbols instead of the raw
>>     ELF codes, as the DWARF parser does.  It's more convenient and not
>>     significantly different, performance-wise.
>
> Yes.  The one at
> <https://gitorious.org/guile-dlhacks/guile-dlhacks/blobs/master/dlhacks/elf.scm>
> could use more comments, docstrings, and tests, if you ask me.  :-)

It's the same one that's in master :)  Agreed, though.  I would note
that in wip-rtl it is tested by rtl.test, though not as a unit.

>>  2) Add enough debugging information so that procedure-name works, and
>>     that we can determine the bounds of procedures.  (Determining where
>>     a procedure ends is a precondition for being able to disassemble
>>     it!)
>>
>>  3) Create tests for all of the opcodes.  This task is somewhat
>>     decoupled from the previous tasks; if people want to help out, see
>>     libguile/vm-engine.c and test-suite/tests/rtl.test.
>
> I’m afraid that writing tests after code may either not happen, or may
> be unable to uncover bugs if it’s written by the same person, or may be
> difficult for someone without a clear picture of the API.
>
> WDYT?
>
> That said, I’ll look into all this as time permits, and see what I can
> contribute myself.

Yes I see what you are saying.  It was only recently that things came
together enough to be testable at all (to have the circle between
assembler, linker, and loader).  However, the instructions themselves
are fairly well documented; do see

  http://git.savannah.gnu.org/gitweb/?p=guile.git;a=blob;f=libguile/vm-engine.c;h=3f575880d5210a1ab5bd4a28b429a0807864be43;hb=refs/heads/wip-rtl#l941

So for this purpose, writing tests should be possible.  WDYT?

> Didn’t you once say “2.2 will have native compilation”?  ;-)

:)

> Seriously though, that seems like a good plan.  I wonder what Noah’s
> attempts at JITing the 2.0 bytecode would have achieved, though, if we
> think of both JIT and the new VM as an “interim solution” before AOT
> native compilation.

It would have been possible but not ideal.  Rewriting the VM to
e.g. have fixed-size stack frames, only two virtual registers, separate
debugging information, statically allocate constants, etc. would still
be necessary, and at that point a refactor to the VM would be more
difficult.

IMO anyway :)

Cheers,

Andy
-- 
http://wingolog.org/

Re: wip-rtl, solstice edition

[Ludovic Courtès]

Hello!

Andy Wingo <wingo@pobox.com> skribis:

> Yes I see what you are saying.  It was only recently that things came
> together enough to be testable at all (to have the circle between
> assembler, linker, and loader).  However, the instructions themselves
> are fairly well documented; do see
>
>   http://git.savannah.gnu.org/gitweb/?p=guile.git;a=blob;f=libguile/vm-engine.c;h=3f575880d5210a1ab5bd4a28b429a0807864be43;hb=refs/heads/wip-rtl#l941
>
> So for this purpose, writing tests should be possible.  WDYT?

Yes, probably.

>> Seriously though, that seems like a good plan.  I wonder what Noah’s
>> attempts at JITing the 2.0 bytecode would have achieved, though, if we
>> think of both JIT and the new VM as an “interim solution” before AOT
>> native compilation.
>
> It would have been possible but not ideal.  Rewriting the VM to
> e.g. have fixed-size stack frames, only two virtual registers, separate
> debugging information, statically allocate constants, etc. would still
> be necessary, and at that point a refactor to the VM would be more
> difficult.

Yes, good point.

And it’s true that the work on ELF and DWARF is definitely valuable for
the future.

Thanks!

Ludo’.