プログラミング言語処理系論
(6)
Design and Implementation of
Programming Language Processors
佐藤周行
（情報基盤センター/電気系専攻融合情報学
今日やること
Perlの吐き出すコードの観察 関数コールに関係するさまざまな話題 Call by ** Frame Calling ConventionPerlの生成するコードを観察する。
sub factorial { $r = 1; while ($i>0) { $r = $r * $i; $i = $i-1; } return $r; } $i = 7; print factorial();$ 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
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
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
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
PerlのParse Tree
Perlは、コードセグメントはほぼParse Tree
実行のための最小限のヒープ、スタックが用
意されている
Perlの実行について （課題５） PerlのB::Conciseモジュールを利 用して、以下についてレポートせよ (1) 適当なプログラムに対してのソースとパー ス木の対応（-src）の観察 (2) 実行に際して必要となるデータ構造（ス タック、フレーム、ヒープ）の特定(myによる ローカル変数の扱いを観察すること) (3) ループ構造を必ず含むこと
今回触れないこと
処理の一単位となる「トークン」をうまく切り分
ける必要があるので…
その他大切なこと：パス
Def. Pass ソースプログラム(および中間生成物)を処理する 一単位。 Def. One-Pass パス一つ（パースを終了させるまで）でコード生成 まで済ませる Def. Multi-Pass 複数のパスから構成されるもの。一般的にはパー スをした後で、解析（最適化等）をするパスを追加 する複数パスの表現
ソースファイル中での表現
main(int ac, char **av) { if (ac >= 2){ if (!strcmp(*++av, "-d")) debug = 1; } code = yyparse(); if (!code) exit(1); nextPass(Entry); } Node *Entry; Top: … {Entry = …}; /* 最初か最後に、後々の 処理のエントリーポイン トを設定しておく */
パスの考え方
近年の考え方では、パースまでと、パース以 後の最適化をわけています。 パースまででできることは高が知れていると認 識が一般的になりました。 最適化ルーチン インタラクティブな言語では、パースまでの処 理と、それ以後の処理（最適化等）のバランス が問題になっています。関数コールの実現
プログラミング言語への進化（復習）
コンパイラシステムの構築 仮想マシンとマシン上の機械語の定義 仮想マシン上での実行 変数の導入 制御構文の導入(複文, if, while, …) 関数の導入(function def/call)関数の出現
関数の出現につれて考えなければならない問 題 コードセグメントの管理 フレームの管理 ローカル変数、グローバル変数 スコープの管理 引数の渡し方変数のバインディング
関数コールについて考えるべきこと (a) 関数には引数をどう渡すのか？ (b) 引数が渡されると、変数名とデータの対応 がどのように変更されるか。また、関数からリ ターンするとき、どのような処理が必要か？いくつかの解（下に行くほど上等）
関数の呼び出しごとにローカル変数の情報を 退避し、バインディングをし直し、関数がリター ンするときに復帰する（vcc7, 昔のLispの実 装） ローカルな変数とグローバルな変数をわけ、 スコープを別にとる（perl） あらかじめローカル変数のアクセスされ方を解 析しておき、バインディングのための情報をコ ード生成時に埋め込む（コンパイル言語）フレーム
関数実行の時に必要な局所的な情報を格納 しておく場所を一般にフレーム (frame) とい います Frameに含まれる情報には以下があります Return address 引数のバインディング情報（特に実引数と仮引数 の対応関係） 関数内のローカル変数のための領域バインディングの余談：
Call by **
Call by Value 値を実引数として渡す (C) ほとんどの現代的言語で実装される JavaのreferenceやCのポインタをわたすのも実 はCall by Value Call by Reference 変数のアドレスを引数として渡す（Fortran, C++ の一部機能） Call by Keyword パラメタに「名前」が付いている (Fortran)関数コールについて
呼び出し側と呼び出される側がどのように引 数（実引数と仮引数）の対応を取るかはデザイ ン上の問題の一つである 例えばperlでは… sub perr { my ($a,$b) = @_; … スタック上に$a, $bの場所を確保し、大域変数_の 値（可変長）を「流し込む」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);呼ぶ方
$ 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
呼ばれる方
$ 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 <0> pushmark sRM*/128 ->6 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 <2> sassign vKS/2 ->f c <$> const[IV 1] s ->d d <0> padsv[$r:2,5] sRM* ->e
一般のプログラミング言語
関数呼び出しの仕方を観察してみる 対象となるアーキテクチャによって大きく変わ る Java on Java VM とC on ネイティブなマシ ン環境の二つを例にとって見るCの実行環境
GCCはCPUを直に実行す るコードを生成する アセンブリコードを見てみる ソースコードa.c Gcc –O3 (4.8.2) アセンブリコードa.s この後に、リンクが入るのだ が、これは省略する Calling conventionは一般にハードウェアと してのCPUの機能ではなく、言語処理系での 「約束事」 スタックにつむのはIntel系で一般的 その他では、レジスタのある部分を引数を割り 当てるのに使用する言語処理系が多数 IBM POWER上のコンパイラ SPARC上のコンパイラ
Calling Conventionを調べるには
コンパイラの内部ドキュメントをみましょう 他のコンパイラとの連携するためにはCalling Conventionは公開情報でなければなりません なければ探しましょう。 cdecl かregcall 間違っても最初からアセンブリコードを解析しては いけません。 で、GCCだ あなたはWikipediaを信用するか？（結果的に正しく ても）Intelの定めるCalling Convention
cdecl
引数はスタックに積む
EAX, ECX, EDXはcaller save
そのほか(ESI, EDI)はcallee save
Return value はEAXに返る FloatならST0に返る
x86-64の場合
regcallがcdeclに加えて定められている
Caller save: RAX, RCX, RDX, RDI, RSI,
R8 - R15 (引数を渡すのに使われる)
以下の簡単なプログラムで実験する
(cdecl)
a(int x0, int x1, int x2) { return x0+x1*2+x2*3; } b() { return a(1,2,3); } $ cc –S a.c
.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
movl 12(%ebp), %eax
leal (%eax,%eax), %edx
movl 8(%ebp), %eax
leal (%edx,%eax), %ecx
movl 16(%ebp), %edx movl %edx, %eax
addl %eax, %eax addl %edx, %eax addl %ecx, %eax popl %ebp
.cfi_restore 5
.cfi_def_cfa 4, 4 ret
.cfi_endproc LFE0: .globl _b .def _b; .scl 2; .type 32; .endef _b: LFB1:
.cfi_startproc pushl %ebp
.cfi_def_cfa_offset 8 .cfi_offset 5, -8
movl %esp, %ebp
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"
GCCのcalling convention
esp +8(引数ここから) +12 +16 Return address ebp ＋方向 スタックはこちら方向に 伸びる （課題6） 手近にあるコンパイラをひとつ対象にし、 calling conventionとフレームを解析せよ。この時 に 以下のことに注意せよ （１）コンパイラ・OS・CPUを明記すること （２）解析の手法を明らかにすること （３）calling conventionは、呼び出し側と呼び出さ れる側の約束であるが、そのときに呼び出される側 から呼び出し側へも約束が存在することに注意せよ
Javaの実行環境
Cと同じことをJavaで調べられるだろうか？
JavaのCalling Conventionは…
とりあえずJNI (Java Native Interface)は
JAVA VM
Thread PC Thread PC VM stack VM stack frame frame Heap Class instance arrays Method Area text Segment Incl. Runtime Constant pool HeapCと同じ事を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 }
“Compiling” Java Program
int add12and13() { return addTwoStatic(12, 13); } Method bipush 12 bipush 13 invokestatic #3 ireturn（課題7） 実行環境としてスタックを用いたフレームを作り たい （１）関数からのリターン情報を含む関数実行の ためのフレームを設計せよ （２）Calling Conventionを一つ定めよ。特に 引数へのアクセス方法を与えよ。 [これで言語設計は一段落！]
