From: Andy Wingo <wingo@pobox.com>
To: guile-devel <guile-devel@gnu.org>
Subject: Register VM WIP
Date: Fri, 11 May 2012 18:19:35 +0200 [thread overview]
Message-ID: <871umqr8q0.fsf@pobox.com> (raw)
Hi all,
This mail announces some very early work on a register VM. The code is
in wip-rtl ("work in progress, register transfer language". The latter
bit is something of a misnomer.). There is not much there yet:
basically just the VM, an assembler, and a disassembler. Still, it's
interesting, and I thought people might want to hear more about it.
So, the deal: why is it interesting to switch from a stack VM, which is
what we have, to a register VM? There are three overriding
disadvantages to the current VM.
1) With our stack VM, instructions are smaller. They do less, so you
need more of them. This increases dispatch cost, which is the
largest cost of a VM.
2) On a stack VM, there is a penalty to naming values. Since the only
values that are accessible to an instruction are the ones on the
top of the stack, whenever you want to use more names, you end up
doing a lot of local-ref / local-set operations. In contrast an
instruction for a register VM can address many more operands, so
there is much less penalty to storing something on the stack. (The
penalty is not so much in the storage, but in the pushing and
popping needed to access it.)
3) Our stack VM has variable-sized stack frames, so we need to check
for overflow every time we push a value on the stack. This is
quite costly.
The WIP register VM fixes all of these issues.
The basic design of the VM is: 32-bit instruction words, 8-bit opcodes,
variable-length instructions, maximum of 24-bit register addressing, and
static, relocatable allocation of constants.
Also, with the wip-rtl VM there is no stack pointer: locals are
addressed directly via the frame pointer, and the call frame for a
function is of a fixed size. Indeed the IP and FP are the only state
variables of the VM, which makes it much easier to think about native
compilation, given the scarcity of CPU registers on some architectures.
See vm-engine.c from around line 1000 for a commented set of
instructions. It's messy in many ways now, but hey.
As far as performance goes, we won't know yet. But at least for a
simple loop, counting down from a billion, the register VM is a few
times faster than the stack VM. Still, I would be happy if the general
speedup were on the order of 40%. We'll see.
Here's that loop in rtl VM:
(use-modules (system vm rtl))
(assemble-rtl-program
0
'((assert-nargs-ee/locals 1 2)
(br fix-body)
loop-head
(make-short-immediate 2 0)
(br-if-= 1 2 out)
(sub1 1 1)
(br loop-head)
fix-body
(mov 1 0)
(br loop-head)
out
(make-short-immediate 0 #t)
(return 0)))
There are various ways to improve this, but its structure is like what
the stack VM produces.
Compare to the current opcode:
scheme@(guile-user)> (define (countdown n) (let lp ((n n)) (or (zero? n) (lp (1- n)))))
scheme@(guile-user)> ,x countdown
Disassembly of #<procedure countdown (n)>:
0 (assert-nargs-ee/locals 17) ;; 1 arg, 2 locals
2 (br :L186) ;; -> 30
6 (local-ref 1) ;; `n'
8 (make-int8:0) ;; 0
9 (ee?)
10 (local-set 2) ;; `t'
12 (local-ref 2) ;; `t'
14 (br-if-not :L187) ;; -> 21
18 (local-ref 2) ;; `t'
20 (return)
21 (local-ref 1) ;; `n'
23 (sub1)
24 (local-set 1) ;; `n'
26 (br :L188) ;; -> 6
30 (local-ref 0) ;; `n'
32 (local-set 1)
34 (br :L188) ;; -> 6
OK, time to set down the keyboard; been working far too much on this in
recent days. I still need to adapt the compiler to produce RTL
bytecode. I am going to let it sit for a week or two before touching it
again. Comments welcome.
Regards,
Andy
--
http://wingolog.org/
next reply other threads:[~2012-05-11 16:19 UTC|newest]
Thread overview: 20+ messages / expand[flat|nested] mbox.gz Atom feed top
2012-05-11 16:19 Andy Wingo [this message]
2012-05-11 20:29 ` Register VM WIP Stefan Israelsson Tampe
2012-05-16 15:01 ` Andy Wingo
2012-05-14 21:09 ` Ludovic Courtès
2012-05-14 21:28 ` Andrew Gwozdziewycz
2012-05-15 18:45 ` Andy Wingo
2012-05-16 0:39 ` Noah Lavine
2012-05-16 4:23 ` Mark H Weaver
2012-05-16 7:15 ` Andy Wingo
2012-05-16 13:44 ` Mark H Weaver
2012-05-16 14:00 ` David Kastrup
2012-05-16 14:54 ` Noah Lavine
2012-05-16 15:05 ` Andy Wingo
2012-05-16 20:39 ` Ludovic Courtès
2012-05-16 14:58 ` Andy Wingo
2012-05-16 16:27 ` Mark H Weaver
2012-05-16 16:39 ` Andy Wingo
2012-05-16 18:23 ` Noah Lavine
2012-05-16 7:10 ` Andy Wingo
2012-05-15 18:49 ` Andy Wingo
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
List information: https://www.gnu.org/software/guile/
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=871umqr8q0.fsf@pobox.com \
--to=wingo@pobox.com \
--cc=guile-devel@gnu.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).