From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: Andy Wingo Newsgroups: gmane.lisp.guile.devel Subject: Register VM WIP Date: Fri, 11 May 2012 18:19:35 +0200 Message-ID: <871umqr8q0.fsf@pobox.com> NNTP-Posting-Host: plane.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii X-Trace: dough.gmane.org 1336753220 25715 80.91.229.3 (11 May 2012 16:20:20 GMT) X-Complaints-To: usenet@dough.gmane.org NNTP-Posting-Date: Fri, 11 May 2012 16:20:20 +0000 (UTC) To: guile-devel Original-X-From: guile-devel-bounces+guile-devel=m.gmane.org@gnu.org Fri May 11 18:20:19 2012 Return-path: Envelope-to: guile-devel@m.gmane.org Original-Received: from lists.gnu.org ([208.118.235.17]) by plane.gmane.org with esmtp (Exim 4.69) (envelope-from ) id 1SSsZl-0004DX-R4 for guile-devel@m.gmane.org; Fri, 11 May 2012 18:20:18 +0200 Original-Received: from localhost ([::1]:35748 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1SSsZk-0003v0-Us for guile-devel@m.gmane.org; Fri, 11 May 2012 12:20:16 -0400 Original-Received: from eggs.gnu.org ([208.118.235.92]:34813) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1SSsZg-0003tS-Nf for guile-devel@gnu.org; Fri, 11 May 2012 12:20:15 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1SSsZe-0001LU-10 for guile-devel@gnu.org; Fri, 11 May 2012 12:20:12 -0400 Original-Received: from a-pb-sasl-sd.pobox.com ([74.115.168.62]:61501 helo=sasl.smtp.pobox.com) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1SSsZd-0000wF-PA for guile-devel@gnu.org; Fri, 11 May 2012 12:20:09 -0400 Original-Received: from sasl.smtp.pobox.com (unknown [127.0.0.1]) by a-pb-sasl-sd.pobox.com (Postfix) with ESMTP id BBF458FDE for ; Fri, 11 May 2012 12:19:39 -0400 (EDT) DKIM-Signature: v=1; a=rsa-sha1; c=relaxed; d=pobox.com; h=from:to :subject:date:message-id:mime-version:content-type; s=sasl; bh=/ EPgZ7pGa1KD3UxYQbffNdhMusU=; b=Gb6K1O8bOps4JVQlAByABFumT4ntwnwHT 5rtTsD+fgvUZ92vvr5n4+LAAZS7ltugroa1vV+bybOqbp7E6kj9IUF+U7E0pTobe YOk4W93Mqe0T8VHT0Jc0o//yBq1EAoW0Fthn0Cyri6/YvCgTsOTHF8audXDcn8Jr XwVaU21QPY= DomainKey-Signature: a=rsa-sha1; c=nofws; d=pobox.com; h=from:to:subject :date:message-id:mime-version:content-type; q=dns; s=sasl; b=xNZ HrFcc7BOA9J6r+WZXY9XLhGvz9/Zf+hL17sZJFAAmXFk97cPUzUuvnCGw2bWPPDM KkFgzrtW7Gjj0Jc5rMNBy+5waeeQZTRfUVDXUiwcy/omV/sYPk/WQugfsqLO/BHB I0horzcQqYPXpDLj1I6jgqgOCJI4S3/pyaroViQ8= Original-Received: from a-pb-sasl-sd.pobox.com (unknown [127.0.0.1]) by a-pb-sasl-sd.pobox.com (Postfix) with ESMTP id A8B008FDD for ; Fri, 11 May 2012 12:19:39 -0400 (EDT) Original-Received: from badger (unknown [90.164.198.39]) (using TLSv1 with cipher DHE-RSA-AES256-SHA (256/256 bits)) (No client certificate requested) by a-pb-sasl-sd.pobox.com (Postfix) with ESMTPSA id 9B1C38FDB for ; Fri, 11 May 2012 12:19:38 -0400 (EDT) User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/23.4 (gnu/linux) X-Pobox-Relay-ID: 1B3ED2A2-9B85-11E1-B58A-E981AF15ED39-02397024!a-pb-sasl-sd.pobox.com X-detected-operating-system: by eggs.gnu.org: Solaris 10 (beta) X-Received-From: 74.115.168.62 X-BeenThere: guile-devel@gnu.org X-Mailman-Version: 2.1.14 Precedence: list List-Id: "Developers list for Guile, the GNU extensibility library" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: guile-devel-bounces+guile-devel=m.gmane.org@gnu.org Original-Sender: guile-devel-bounces+guile-devel=m.gmane.org@gnu.org Xref: news.gmane.org gmane.lisp.guile.devel:14394 Archived-At: 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 #: 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/