VMの考え方と具体例

プログラミング言語処理系論 (8)
Design and Implementation of
Programming Language Processors
佐藤周行
（情報基盤センター/電気系専攻融合情報学
コース）
今日の予定
 VM設計の実際(前回とすこし被る)
 Stack Machine vs. Register Machine
 命令セットアーキテクチャ
 ターゲットとなるプログラミング言語を効率よく実行す
るために
 Java VM vs. Parrot
parrot.org/
Stack Machine vs. Register
Machine
 Stack Machine
 各種演算（load/store, arithmetic, …）のオペ
ランドにスタックを想定する
 スタックに「プッシュする」「ポップする」演算が
explicit/implicitにある
 フレームなど、スタックで効率よく実装できるもの
が多くある
 コードが簡潔になる場合が多い
Register Machine
 Register Machine
 各種演算のオペランドにレジスタ（変数）を想定す
る
 ハードウェア命令との親和性が高いと主張する
 ハードウェアとの親和性を考えるとき、命令体系のレ
ジスタセットとハードウェアのレジスタセットが異なる
場合、「Register Allocation」が必要になる
 レジスタの選択の自由度が上がる分、コードは一
般に複雑
ではJava VMをみてみましょう
命令セットアーキテクチャ (ISA)
 VMで扱うデータの型について
 対象となる言語によって若干違い
 命令をデザインする時に必要
 JAVA VM




byte/char/short/int/long
float/double
boolean/return address
reference (class/array/interface)
ISA
 Parrot




I (Integer)
N (Real)
S (String)
P (Polymorphic)
 それぞれの型に応じてレジスタが用意されて
いる
 Ixx, Nxx, Sxx, Pxx
言語的に重要なもの
 オブジェクトの生成
 new
 関数（メソッド）コール
 フレームの構築




invokevirtual
invokestatic
invokespecial
invokedynamic
コンパイルしてみる
class x {
static int content;
x(int y) {
content = y;
}
public int get_content() {
return content;
}
public void addxx(x x1) {
int y;
}
}
フレーム
フレーム０
フレーム１
フレーム２
フレーム３
this
第一引数
第二引数
第三引数
０
y = x1.get_content();
content += y;
iload_n, aload_n, istore_n, aload_n等の命令が
フレーム内のデータにアクセスするために用意されている
コンパイル結果
class x {
static int content;
x(int);
Code:
0: aload_0
1: invokespecial #1
// Method
java/lang/Object."<init>":()V
4: iload_1
5: putstatic
#2
8: return
public int get_content();
Code:
0: getstatic
#2
3: ireturn
}
public void addxx(x);
Code:
0: aload_1
1: invokevirtual #3
// Method get_content:()I
4: istore_2
5: getstatic
#2
// Field content:I
8: iload_2
9: iadd
10: putstatic
#2
// Field content:I
13: return
ターゲット言語の重要な要素
 オブジェクト指向言語
 オブジェクト
 Method invocation
 フレームは普通にスタックに積むのだが、Java VMで
はそこまでは強制されていない
 スクリプト言語
 動的型付け
 文字列の操作が…
Parrot
 Perl6用のVM
 多くの動的型付け言語対応を唱う
 では、Parrotのうたい文句を見てみましょう
Parrot is a language-neutral virtual machine for
dynamic languages such as Ruby, Python, PHP,
and Perl. It hosts a powerful suite of compiler
tools tailored to dynamic languages and a next
generation regular expression engine.
 少しambitiousなことが書いてある
 Its architecture is fundamentally
different than existing virtual
machines such as the JVM or CLR,
with optimizations for dynamic
languages included, a register-based
system rather than stack-based, and
the use of continuations as the core
means of flow control.
構成
 Parrot
 VM
 言語として
 PIR
 PASM
中間言語系
アセンブリ言語
Parrotの構造
Perl他ターゲット言語
PIR
PASM
PBC
Parrot
では、Parrotの解析
 データ型は




Integer
Number
String
PMC (Parrot Magic Cookie)
Register Machine
 Registerとして




Ixx
Nxx
Sxx
Pxx
 変数はスタックに積むことなく、「レジスタ名」で
アクセスされる
簡単な例（ただし分厚いライブラリ付）
.loadlib 'io_ops'
.pcc_sub :main main:
getstdin P0
getstdout P1
REDO:
readline S0, P0
print S0
if S0, REDO
end
Parrotに求められるものは何か？
 「オブジェクト」に対する動的な型付けのサポ
ート。そのためにPMCを用意した
 PMC
 Scalar/array/subroutine/namespace を収
容できる
 目的に応じて柔軟に型変換が可能になっている
PMCのタイプ









Env
Iterator
Array
Hash
String
Integer
Float
Exception
Timer
たとえば、これはどうか（動的関係ない
.sub 'example' :main
$I1 = 96
$I2 = 64
print "Algorithm E (Euclid's algorithm)¥n"
e1:
$I4 = mod $I1, $I2
e2:
unless $I4 goto done
e3:
$I1 = $I2
$I2 = $I4
branch e1
done: print "The greatest common denominator of 96 and 64 is "
print $I2
print ".¥n"
.end
ではこちらはどうか
$i = 4.3;
print fact();
sub fact {
$r = 1;
while ($i > 0) {
$r = $r * $i;
$i--;
}
return $r;
}
解決方法
 特定の演算を指定して、polymorphicにする
 この場合はdecrement, multiply
 PMCを引数に取る時の挙動を定める
 → VTABLEで処理内容を指定する
 型指定のタイミングを変数の代入の時点で制御で
きるようにする
 代入のsemanticsを定める
実際 src/ops/math.opsでは
inline op dec(inout INT) {
$1--;
}
inline op dec(inout NUM) {
$1--;
}
inline op dec(invar PMC) {
VTABLE_decrement(interp, $1);
}
ISA
 まずは命令セットを眺めてみましょうか
 src/include/oplib/ops.h
 1124個の命令
 高レベルのものを含む（特に制御関係）
ISA

特に代入(set)を見てみましょう
inline op set(out INT, in INT) {
$1 = $2;
}
inline op set(out INT, in NUM) {
$1 = (INTVAL)($2);
}
inline op set(out INT, in STR) {
$1 = Parrot_str_to_int(interp, $2);
}
inline op set(out NUM, in NUM) {
$1 = $2;
}
…
Non-trivialなsetは…
inline op set(invar PMC, in INT) {
VTABLE_set_integer_native(interp, $1, $2);
}
inline op set(invar PMC, in NUM) {
VTABLE_set_number_native(interp, $1, $2);
}
inline op set(invar PMC, invar STR) {
VTABLE_set_string_native(interp, $1, $2);
}
inline op set(invar PMC, inconst STR) {
VTABLE_set_string_native(interp, $1, $2);
}
inline op set(out INT, invar PMC) {
$1 = VTABLE_get_integer(interp, $2);
}
Set
 全体として以下のパターンに対してそれぞれ
対応する関数が定められている
 set (単純なパターン)
 set P {I/N/S}
 set Px [key] By/ set Ax Py[key]
 白鳥は優雅に泳いでいるが…というパターン
関数呼び出しについて（PIR)
 まずはフレーム
# factorial.pir
.sub 'main' :main
.local int count
.local int product
count = 5
product = 1
$I0 = 'fact'(count,
product)
say $I0
.end
.sub 'fact'
.param int c
.param int p
loop:
if c <= 1 goto fin
p=c*p
dec c
branch loop
fin:
.return (p)
.end
関数コール
 Signature で型付け
 IN -> OUT
 関数コールごとにcontextを作成（特別のスタ
ックがあるわけではない）
 Continuationを受け渡すことができる
 Coroutine等が実現可能…
名前解決
 後は、グローバルな変数（名前でしかアクセス
できないデータ）の扱いですが
 以下の命令が用意されている
 {store/find}_lex 名前付き変数の解決
 get_namespace をやる前提で
 get_global
 set_global
 find_name

Download Report