スライド 1

Size: px

Start display at page:

Download "スライド 1"

なぎさはまもり
4 years ago
Views:

1 プログラミング言語処理系論 (9) Design and Implementation of Programming Language Processors 佐藤周行 ( 情報基盤センター / 電気系専攻融合情報学コース )

2 今日の予定 Register machine の実際 Parrot Stack machine vs Register machine VMの設計 vmgen

3 parrot.org/

4 Register Machine Register Machine 各種演算のオペランドにレジスタ ( 変数 ) を想定するハードウェア命令との親和性が高いと主張するハードウェアとの親和性を考えるとき命令体系のレジスタセットとハードウェアのレジスタセットが異なる場合 Register Allocation が必要になるレジスタの選択の自由度が上がる分コードは一般に複雑

5 ISA of Parrot Parrot I (Integer) N (Real) S (String) P (Polymorphic) それぞれの型に応じてレジスタが用意されている ( 実質無限個 ) Ixx, Nxx, Sxx, Pxx

6 ターゲット言語の重要な要素スクリプト言語としての Perl の特徴動的型付け実行時に文字列 (S) か数 (I, N) かが決まる文字列の操作パターン照合を含む Array の操作

7 Parrot Perl6 用の VM 多くの動的型付け言語対応を唱う Rakudo Perl6 Lua Winxed では 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.

8 少し 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.

9 構成 Parrot VM 言語として PIR PASM 中間言語系アセンブリ言語

10 Parrot の構造 Perl 他ターゲット言語 PIR PASM PIR: Parrot Intermediate Language PASM: Parrot Assembly Language PBC: Parrot ByteCode PBC Parrot

11 では Parrot の解析データ型は Integer Number String PMC (PolyMorphic Container)

12 Register Machine Register として Ixx Nxx Sxx Pxx 変数はスタックに積むことなくレジスタ名でアクセスされる

13 簡単な例 ( ただし分厚いライブラリ付 ).loadlib 'io_ops'.pcc_sub :main main: getstdin P0 getstdout P1 REDO: readline S0, P0 print S0 if S0, REDO end

14 Parrot に求められるものは何か? オブジェクトに対する動的な型付けのサポートそのために PMC を用意した PMC Scalar/array/subroutine/namespace を収容できる目的に応じて柔軟に型変換が可能になっている

15 PMC のタイプ Env Iterator Array Hash String Integer Float Exception Timer

16 たとえばこれはどうか ( 動的関係ない.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

17 ではこちらはどうか $i = 4.3; print fact(); sub fact { $r = 1; while ($i > 0) { $r = $r * $i; $i--; } return $r; }

18 解決方法特定の演算を指定して polymorphic にするこの場合はdecrement, multiply PMCを引数に取る時の挙動を定める VTABLEで処理内容を指定する型指定のタイミングを変数の代入の時点で制御できるようにする代入の semantics を定める

19 実際 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); }

20 ISA まずは命令セットを眺めてみましょうか include/parrot/oplib/ops.h 1129 個の命令高レベルのものを含む ( 特に制御関係 )

21 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; }

22 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); }

23 Set 全体として以下のパターンに対してそれぞれ対応する関数が定められている set ( 単純なパターン ) set P {I/N/S} set Px [key] By/ set Ax Py[key] 白鳥は優雅に泳いでいるがというパターン

24 関数呼び出しについて (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

25 PASM での表現.pcc_sub :main main: new P10, 'ResizableIntegerArray' set I1,0 ## P9 is used as a stack for temporaries. new P9, 'ResizableIntegerArray' loop: done: print "fact of " print I1 print " is: " new P0, 'Integer' set P0,I1 local_branch P10, fact print P0 print " n" inc I1 eq branch end I1,31,done loop ### P0 is the number to compute,and also the return value. fact: lt P0,2,is_one ## save I2, because we're gonna trash it. push is_one: set I2,P0 dec P0 P9,I2 local_branch P10, fact mul P0,P0,I2 pop I2,P9 local_return P10 set P0,1 local_return P10

26 まともなやつ.pcc_sub :main main: # as a ResizableStringArray get_params "0", P0 # Discard the program name shift S0, P0 FOUND_EXTRA_ARG: shift S1, P0 print "Hello " print S1 print " n" end # Look for additional args if P0, FOUND_EXTRA_ARG print "Hello World n" end

27 関数コール Signature で型付け IN -> OUT 関数コールごとに context を作成 ( 特別のスタックがあるわけではない ) Continuation を受け渡すことができる Coroutine 等が実現可能

28 OpCode を見てみるクラス関係 Callmethod, tailcallmethod, addmethod, can, does, isa (VTABLE), newclass, subclass, get_class, class, addparent, removeparent, addattribute, removeattribute, getattribute, setattribute, inspect

29 文字列命令 ord, chr, chopn, concat, repeat, length, bytelength, pin, new, substr, replace, index, rindex, sprintf, upcase, downcase, titlecase, stringinfo, join, split, encoding, find_encoding, trans_encoding, finc_cclass, escape, compose, find_compose

30 PMC new, root_new, typeof, find_method, defined, exists, delete, elements, push, pop, shift, splice, setprop, getprop, freeze, thaw, box, iter,

31 プロセス管理 schedule, add_handler, wait, pass, invokecc, returncc, disable/enablepreemption, terminate, 関数コール get/set_params, get/set_result

32 名前解決後はグローバルな変数 ( 名前でしかアクセスできないデータ ) の扱いですが以下の命令が用意されている {store/find}_lex 名前付き変数の解決 get_namespace をやる前提で get_global set_global find_name

33 ( 問題 8 への追加 ) CPython の VM について JVM と同じことを解析せよ ( 問題 8 ) Parrot について JVM と同じことを解析せよ

34 stack machine vs. register machine 微妙な pros/cons がある少し古い論文だが Y. Shi, K. Casey, M. A. Ertl, D. Gregg: Virtual Machine Showdown: Stack Versus Registers, ACM Transactions on Architecture and Code Optimization, r(4), ( このグループは vmgen の開発者です )

35 stack machine と register machine はどちらが高速に動くか? JIT コンパイラとは別の話 register machine を新たに定義し JVM との性能比較実験をしてみた vmgen を利用して気軽に VM が実装できる生成されたコードは load/store に関して最適化を行った load/store の挙動が両アーキテクチャの最大の違いであることはすぐわかる

36 Load/Store stack machine ( 基本的に ) 演算の度に stack へのデータ移動が発生対 frame, 対 constant pool, 対 object pool register machine register にデータを移動したら register を使って演算ができる copy propagation, redundant load elimination は性能を出すうえで必須の最適化

37 性能比較生成されたコードの比較 Naïve な stack register 変換 Move 31%, constant load 28% ( これが stack machine の特徴と考えてよい ) Load/store の最適化後命令数全体で 44% 削減 ( ただし 1 命令あたりのサイズは大きくなっているコード量では 26% 削減 ) Move は大部分削除 constant load は 35% 削減実行されたコードの比較 Move 42% ほとんど削除 Constant load は全体の 6.4% 2.9% ( 実行頻度は少ない ) 実行命令数全体で 46% 削減 (NOT 実行時間 )

38 Load/Store (VM ではなく ) 実行プラットフォーム CPU の load/store 数の比較 VM でレジスタを実装しても裏でメモリ load/store をする register machine は stack machine と比較して load で 35% 削減 store で 48% 削減全体性能として (dispatch に気を配れば )2 倍程度性能向上 (AMD64)

39 オチとして命令 dispatch の方法の改善が重要 vmgenはいろいろ実験ができる switch 文を使ったdispatch ノーマルな方法 direct-threaded dispatch Next PCの指す命令に対応するラベルに直接 goto 言語のサポート必要 (GCCならできる)

40 Just in Time Compiler 昔そういう技術がありまして Java の実行速度を上げるための工夫に使われた VM code VM CPU 実行直前にコンパイル Native code 実用的にはこのアイデアはいろいろなところに残っている LTO など

41 Note JVM の命令列を register machine の命令列に変換したと言っているが Stack machine の命令列にする時点で情報がだいぶ落ちている最適化の支障になる可能性がある ( 論文中で言及されている ) 最適化をするなら中間表現の設計に気を配るのが筋 ( これは次回以降のトピック )

42 VM の設計 VM を設計する Engine 部分ならごく簡単 load/link データ領域の確保を忘れずにスレッド等並列サポートもあればなおよい

43 ターゲット言語の重要な要素オブジェクト指向言語オブジェクト Method invocation フレームは普通にスタックに積むのだが Java VM ではそこまでは強制されていないスクリプト言語動的型付け文字列の操作が

44 決めるべきこと ISA 重要な feature をサポートすることを考える今まで説明してきた VM の真似から始めるのがよかろう Minimum set として何が必要かを考えると言語の設計とリンクしてきますデータコード Reference 方法の決定大昔は Addressing Mode などと言いましてね Frame Management Call 関係の命令の実装

45 VM の実装 Stack/register machine ISA Code/data/stack segment Symbol table これらが決まったら後は各命令の解釈を書くだけ vmgen など便利そうに見えるツールがある

46 問題 10 Stack machine の VM を一つ設計せよ命令セットは DCC.zip 中の opcode.h を使うこと stack segment と data segment を定義すること各命令を実行したときの stack/data segment の状態変化を記述すること OP_CALL と OP_RETURN については詳述することこの記述に従って vmgen で VM を作成するとなおよいコンパイラを作る必要はない

47 VMGEN の強調すること VMGEN は Gforth の実装言語として世に出た ( らしい ) n ここからダウンロードはできない Project Homepage にいって Gforth をダウンロードするとついてくる VM のエンジン部分を生成してくれる命令 dispatch に凝っている Switch (naïve, simple, but slow) Direct threaded dispatch のサポート

48 Switch vmexec(int pc) { { for (;;) { switch (codeseg[pc].op) case OP_NOP: NEXTPC; case OP_POP: stacktop -= codeseg[pc].operand ; NEXTPC; case OP_U_NOT: stackseg[stacktop] =!stackseg[stacktop]; NEXTPC; case OP_B_ADD: binop(+); NEXTPC; case OP_B_SUB: binop(-); NEXTPC;

49 Direct Threaded Dispatch vmexec(int pc) { for (;;) { switch (codeseg[pc].op) { case OP_NOP: goto codeseg[nextpc]; case OP_POP: stacktop -= codeseg[pc].operand; goto codeseg[nextpc]; case OP_U_NOT: stackseg[stacktop] =!stackseg[stacktop]; goto codeseg[nextpc]; case OP_B_ADD: binop(+); goto codeseg[nextpc]; case OP_B_SUB: binop(-); goto codeseg[nextpc];

50 さてとレジスタ変数 ( またはスタック上の変数 ) の間の演算列という形でプログラムが書かれるようになれば最適化が可能になります今までの tree traversal ではできる最適化にも限度がありましたが最適化は性能をあげるためには必須です register machine architecture では load/store の最適化が stack machine architecture より劇的に効くことを説明しました

51 動的言語では動的な型変換が性能にどれだけのマイナス要因になっているかを理解する静的にでも動的にでも型変換のルーチンをスキップできれば性能が上がる JVM 上でスクリプト言語を実行する場合引数の動的型チェックを行う引数の型チェックをできるものは静的にすませてしまう

52 動的型変換においてはルーチン内で型が伝播する可能性があるローカルな解析をもとにしてデータフロー解析をもとにしてルーチンをまたいで型が分かる場合がある手続き関解析をもとにして

53 最適化の分類 1. ローカル最適化 1. 基本ブロック内外で一定のパターンに当てはまるものを変換 ( ピープホール最適化 ) 2. 基本ブロック内で変数の挙動を解析して変換 2. データフロー解析をもとにした大域最適化 3. データ依存解析をもとにしたループ最適化 4. 手続き間解析をもとにした手続き間最適化 1. LTO 2. WPRO

54 LTO (Link Time Optimization) 関数をまたいだ最適化を効率よく行うためにリンク時に最終的に最適化を行うことが普通になりつつあるコンパイラシステムがサポートすることも普通になってきている

55 代表的な手続き間解析部分評価手続きに渡される引数の性質を利用する int g(x) { if (x==0) return 1; else return h(x-1); } int g(x) { if (x==0) return 1; else return h(x-1); } main() { print g(2)+g(0); } main() { print h(1)+1; }

プログラミング言語処理系論 (9) Design and Implementation of Programming Language Processors 佐藤周行 ( 情報基盤センター / 電気系専攻融合情報学コース )

プログラミング言語処理系論 (9) Design and Implementation of Programming Language Processors 佐藤周行 ( 情報基盤センター / 電気系専攻融合情報学コース ) 今日の予定 Parrot 設計の実際最適化について JVM で十分か? ( 問題 11) 次の論文のうちどれかを読み要約せよ 1. JVM-hosted languages: