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

Size: px

Start display at page:

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

ゆきうばら
4 years ago
Views:

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

2 今日やること Perlの吐き出すコードの観察関数コールに関係するさまざまな話題 Call by ** Frame Calling Convention

3 Perl の生成するコードを観察する sub factorial { $r = 1; } while ($i>0) { $r = $r * $i; $i = $i-1; } return $r; $i = 7; print factorial();

4 $ perl -MO=Concise,factorial,-src fact.pl main::factorial: t <1> leavesub[1 ref] K/REFC,1 ->(end) - <@> lineseq KP ->t # 3: $r = 1; 1 <;> nextstate(main 1 fact.pl:3) v:{ ->2 4 <2> sassign vks/2 ->5 2 <$> const[iv 1] s ->3 - <1> ex-rv2sv skrm*/1 ->4 3 <#> gvsv[*r] s ->4 # 5: while ($i>0) { 5 <;> nextstate(main 3 fact.pl:5) v:{ ->6

5 o <2> leaveloop vkp/2 ->p 6 <{> enterloop(next->j last->o redo->7) v ->k - <1> null vk/1 ->o n < > and(other->7) vk/1 ->o m <2> gt sk/2 ->n - <1> ex-rv2sv sk/1 ->l k <#> gvsv[*i] s ->l l <$> const[iv 0] s ->m - <@> lineseq vkp ->- # 6: $r = $r * $i; 7 <;> nextstate(main 1 fact.pl:6) v:{ ->8 c <2> sassign vks/2 ->d

6 a <2> multiply[t6] sk/2 ->b - <1> ex-rv2sv sk/1 ->9 8 <#> gvsv[*r] s ->9 - <1> ex-rv2sv sk/1 ->a 9 <#> gvsv[*i] s ->a - <1> ex-rv2sv skrm*/1 ->c b <#> gvsv[*r] s ->c # 7: $i = $i-1; d <;> nextstate(main 1 fact.pl:7) v:{ ->e i <2> sassign vks/2 ->j g <2> subtract[t9] sk/2 ->h - <1> ex-rv2sv sk/1 ->f

7 e <#> gvsv[*i] s ->f f <$> const[iv 1] s ->g - <1> ex-rv2sv skrm*/1 ->i h <#> gvsv[*i] s ->i j <0> unstack v ->k # 9: return $r; p <;> nextstate(main 3 fact.pl:9) v:{ ->q s <@> return K ->t q <0> pushmark s ->r - <1> ex-rv2sv sk/1 ->s r <#> gvsv[*r] s ->s

8 Perl の Parse Tree Perl はコードセグメントはほぼ Parse Tree 実行のための最小限のヒープスタックが用意されている B::Concise で内容を見ることができる

9 Perl の実行について ( 課題 5) Perl の B::Concise モジュールを利用して以下についてレポートせよ (1) 適当なプログラムに対してのソースとパース木の対応 (-src) の観察 (2) 実行に際して必要となるデータ構造 ( スタックフレームヒープ ) の特定 (my によるローカル変数の扱いを観察すること ) (3) ループ構造を必ず含むこと

10 今回触れないこと処理の一単位となるトークンをうまく切り分ける必要があるので yylex はまじめにかきましょう

11 その他大切なこと : パス Def. Pass ソースプログラム ( および中間生成物 ) を処理する一単位 Def. One-Pass パス一つ ( パースを終了させるまで ) でコード生成まで済ませる Def. Multi-Pass 複数のパスから構成されるもの一般的にはパースをした後で解析 ( 最適化等 ) をするパスを追加する

12 複数パスの表現ソースファイル中での表現 Node *Entry; main(int ac, char **av) { if (ac >= 2){ if (!strcmp(*++av, "-d")) debug = 1; } code = yyparse(); if (!code) exit(1); nextpass(entry); } Top: {Entry = }; /* 最初か最後に後々の処理のエントリーポイントを設定しておく */

13 パスの考え方近年の考え方ではパースまでとパース以後の最適化をわけていますパースまででできることは高が知れていると認識が一般的になりました最適化ルーチンインタラクティブな言語ではパースまでの処理とそれ以後の処理 ( 最適化等 ) のバランスが問題になっています

14 関数コールの実現関数の実現について

15 プログラミング言語への進化 ( 復習 ) コンパイラシステムの構築仮想マシンとマシン上の機械語の定義仮想マシン上での実行変数の導入制御構文の導入 ( 複文, if, while, ) 関数の導入 (function def/call)

16 関数の出現関数の出現につれて考えなければならない問題コードセグメントの管理フレームの管理ローカル変数グローバル変数スコープの管理引数の渡し方

17 変数のバインディング関数コールについて考えるべきこと (a) 関数には引数をどう渡すのか? (b) 引数が渡されると変数名とデータの対応がどのように変更されるかまた関数からリターンするときどのような処理が必要か?

18 いくつかの解 ( 下に行くほど上等 ) 関数の呼び出しごとにローカル変数の情報を退避しバインディングをし直し関数がリターンするときに復帰する (vcc7, 昔の Lisp の実装 ) ローカルな変数とグローバルな変数をわけスコープを別にとる (perl) あらかじめローカル変数のアクセスされ方を解析しておきバインディングのための情報をコード生成時に埋め込む ( コンパイル言語 )

19 フレーム関数実行の時に必要な局所的な情報を格納しておく場所を一般にフレーム (frame) といいます Frame に含まれる情報には以下があります Return address 引数のバインディング情報 ( 特に実引数と仮引数の対応関係 ) 関数内のローカル変数のための領域

20 バインディングの余談 :Call by ** Call by Value 値を実引数として渡す (C) ほとんどの現代的言語で実装される Java の reference や C のポインタをわたすのも実は Call by Value Call by Reference 変数のアドレスを引数として渡す (Fortran, C++ の一部機能 ) Call by Keyword パラメタに名前が付いている (Fortran)

21 関数コールについて呼び出し側と呼び出される側がどのように引数 ( 実引数と仮引数 ) の対応を取るかはデザイン上の問題の一つである例えば perl では sub perr { my ($a,$b) スタック上に $a, $b の場所を確保し大域変数 _ の値 ( 可変長 ) を流し込む

22 Perl での引数の渡し方の観察 sub factorial { my ($i, $j) my($r); $r = 1; } while ($i>0) { $r = $r * $i; $i = $i-1; } return $r; print factorial(7, 8);

23 呼ぶ方 $ perl -MO=Concise,-src fact2.pl a <@> leave[1 ref] vkp/refc ->(end) 1 <0> enter ->2 # 17: print factorial(7, 8); 2 <;> nextstate(main 6 fact2.pl:17) v:{ ->3 9 <@> print vk ->a 3 <0> pushmark s ->4 8 <1> entersub[t3] lks/targ,1 ->9 - <1> ex-list lk ->8 4 <0> pushmark s ->5 5 <$> const[iv 7] sm ->6 6 <$> const[iv 8] sm ->7 - <1> ex-rv2cv sk ->- 7 <#> gv[*factorial] s ->8

24 呼ばれる方 $ perl -MO=Concise,factorial,-src fact2.pl main::factorial: z <1> leavesub[1 ref] K/REFC,1 - >(end) - <@> lineseq KP ->z # 3: my ($i, $j) 1 <;> nextstate(main 1 fact2.pl:3) v ->2 8 <2> aassign[t5] vks ->9 - <1> ex-list lk ->5 2 <0> pushmark s ->3 4 <1> rv2av[t4] lk/1 ->5 3 <#> gv[*_] s ->4 - <1> ex-list lkprm*/128 ->8 5 >6 <0> pushmark srm*/128-6 <0> padsv[$i:1,5] lrm*/lvintro ->7 7 <0> padsv[$j:1,5] lrm*/lvintro ->8 # 5: my($r); 9 <;> nextstate(main 2 fact2.pl:5) v ->a a <0> padsv[$r:2,5] vpm/lvintro ->b # 7: $r = 1; b <;> nextstate(main 3 fact2.pl:7) v:{ ->c e c d <2> sassign vks/2 ->f <$> const[iv 1] s ->d <0> padsv[$r:2,5] srm* ->e

25 一般のプログラミング言語関数呼び出しの仕方を観察してみる対象となるアーキテクチャによって大きく変わる Java on Java VM と C on ネイティブなマシン環境の二つを例にとって見る

26 C の実行環境 GCC は CPU を直に実行するコードを生成するアセンブリコードを見てみるソースコードa.c Gcc O3 (4.8.2) アセンブリコード a.s この後にリンクが入るのだがこれは省略する

27 Calling convention は一般にハードウェアとしての CPU の機能ではなく言語処理系での約束事スタックにつむのは Intel 系で一般的その他ではレジスタのある部分を引数を割り当てるのに使用する言語処理系が多数 IBM POWER 上のコンパイラ SPARC 上のコンパイラ

28 Calling Convention を調べるにはコンパイラの内部ドキュメントをみましょう他のコンパイラとの連携するためには Calling Convention は公開情報でなければなりませんなければ探しましょう cdecl か regcall 間違っても最初からアセンブリコードを解析してはいけませんで GCC だあなたは Wikipedia を信用するか?( 結果的に正しくても )

29 Intel の定める Calling Convention cdecl 引数はスタックに積む EAX, ECX, EDXはcaller save そのほか (ESI, EDI) はcallee save Return value はEAXに返る FloatならST0に返るスタックをクリーンアップするのはcaller

30 x86-64 の場合 regcall が cdecl に加えて定められている Caller save: RAX, RCX, RDX, RDI, RSI, R8 - R15 ( 引数を渡すのに使われる ) Callee save: R10 - R15, RBX, RBP, RSP

31 以下の簡単なプログラムで実験する (cdecl) a(int x0, int x1, int x2) { $ cc S a.c return x0+x1*2+x2*3; } b() { return a(1,2,3); }

32 .file "a.c".text.globl _a.def _a;.scl 2;.type 32;.endef _a: LFB0:.cfi_startproc pushl %ebp.cfi_def_cfa_offset 8.cfi_offset 5, -8 movl %esp, %ebp.cfi_def_cfa_register 5

33 movl 12(%ebp), %eax leal (%eax,%eax), %edx movl 8(%ebp), %eax leal (%edx,%eax), %ecx movl 16(%ebp), %edx movl %edx, %eax

34 addl %eax, %eax addl %edx, %eax addl %ecx, %eax popl %ebp.cfi_restore 5.cfi_def_cfa 4, 4 ret

35 .cfi_endproc LFE0: _b:.globl _b.def _b;.scl 2;.type 32;.endef LFB1:

36 .cfi_startproc pushl %ebp.cfi_def_cfa_offset 8.cfi_offset 5, -8 movl %esp, %ebp.cfi_def_cfa_register 5

37 subl $12, %esp movl $3, 8(%esp) movl $2, 4(%esp) movl $1, (%esp) call _a leave.cfi_restore 5.cfi_def_cfa 4, 4 ret.cfi_endproc LFE1:.ident "GCC: (GNU) 4.8.2"

38 GCC の calling convention esp ebp Return address スタックはこちら方向に伸びる +8( 引数ここから ) 方向

39 ( 課題 6) 手近にあるコンパイラをひとつ対象にし calling convention とフレームを解析せよこの時に以下のことに注意せよ (1) コンパイラ OS CPU を明記すること (2) 解析の手法を明らかにすること (3)calling convention は呼び出し側と呼び出される側の約束であるがそのときに呼び出される側から呼び出し側へも約束が存在することに注意せよ

40 Java の実行環境 C と同じことを Java で調べられるだろうか? Java の Calling Convention はとりあえず JNI (Java Native Interface) はここ

41 JAVA VM Heap Thread PC Thread PC VM stack VM stack frame Method Area Heap text Segment Class instance arrays Incl. Runtime Constant pool frame

42 C と同じ事を Java でしてみるソースファイル a.java ディスアセンブルしたコード (javap c) Compiled from "a.java" class a extends java.lang.object{ a(); Code: 0: aload_0 1: invokespecial #1; //Method java/lang/object."<init>":()v 4: return int add12and13(int,int); Code: 0: iload_1 1: iload_2 2: iadd 3: ireturn }

43 Compiling Java Program int add12and13() { return addtwostatic(12, 13); } Method bipush 12 bipush 13 invokestatic #3 ireturn

44 ( 課題 7) 実行環境としてスタックを用いたフレームを作りたい (1) 関数からのリターン情報を含む関数実行のためのフレームを設計せよ (2)Calling Convention を一つ定めよ特に引数へのアクセス方法を与えよ [ これで言語設計は一段落!]

45 課題 8 自分でプログラミング言語を定義せよ仕様を書けそのプログラミング言語の Parser を与えよそのプログラミング言語で書いたプログラムを評価するプログラムを書け Interpreter + 仮想マシン Compiler + 仮想マシン or ネイティブマシン

46 仕様プログラミング言語を定義したら仕様にまとめてみるこれができない人がプログラミング言語を定義するときに必要な要素は大体以下の通りプログラム全体の構造制御構造データオブジェクト式関数 ( 手続き ) の扱い変数のバインディング

プログラミング言語処理系論 (4) Design and Implementation of Programming Language Processors

プログラミング言語処理系論 (4) Design and Implementation of Programming Language Processors プログラミング言語処理系論 (6) Design and Implementation of Programming Language Processors 佐藤周行 ( 情報基盤センター / 電気系専攻融合情報学コース ) 2014-5 の残業から Perl の吐き出すコードをながめてみる Parser Kit 中の vcc6.y をながめてみる文法定義パースツリーの格納実行 fact.pl