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

プログラミング言語処理系論

(6)

Design and Implementation of

Programming Language Processors

佐藤周行

（情報基盤センター

/電気系専攻融合情報学

コース）

今日やること



関数コールの実現と関係するさまざまな話題



Frameのデザイン



Calling Convention



Compile & Goによる実行



VMの定義



ISA



実行エンジン

関数の出現



Homomorphicな考えをサポート



この他には変数（シンボル）管理



関数の出現につれて考えなければならない問題



コードセグメントの管理



HW, VMのサポートの理解



Calling Conventionの理解



フレームの管理



ローカル変数、グローバル変数



スコープの管理



引数の渡し方

変数のバインディング



関数コールについて考えるべきこと

(a) 関数には引数をどう渡すのか？

(b) 引数が渡されると、変数名とデータの対応

がどのように変更されるか。また、関数からリ

ターンするとき、どのような処理が必要か？

フレーム



関数実行の時に必要な局所的な情報を格納して

おく場所を一般にフレーム

(frame) といいます



フレームを一つ作ると、環境が変化します



関数呼び出しが終了したら、環境を元に戻さなけ

ればなりません



Frameに含まれる情報には以下があります



Return address



引数のバインディング情報（特に実引数と仮引数の対

応関係）



関数内のローカル変数のための領域



局所的な環境は、任意の場所に現れるという

のが現代的なプログラミング言語の常識



考え方はフレームと同じ



局所的な環境を定義するときに、変数と値の結合

の仕方を改めて定義する



局所的な環境が「終了」したら、変数と値の結合を

元にもどす



source tree traversalでのやり方をまず見

関数コールについて



呼び出し側と呼び出される側がどのように引数（実引数と仮

引数）の対応を取るかはデザイン上の問題の一つ



この「約束」を

calling conventionという



HW, VMのサポートによる制約



言語実装上の「取り決め」（自由にデザインできる）



HW, VMで様々な機能がcallの実行時にサポートされてい

る場合がある



Frameの自動構築



レジスタの自動rename



x86は、このサポート（制約）がほとんどない



Code生成をする場合、このサポート（制約）を満たさなければな

らない



Interpreterの場合、自由にデザインできる

後述しますが

…



JVMの場合、Invoke***を実行すると



そのメソッド用の

frameが構築される。



callerは、呼び出し側のオブジェクト（this）とメソッ

ドの引数を指定しておく



calleeは、指定されたデータを0から順にアクセス

できるように、

frameの初期化を行う



Return addressの操作は（原則）implicitに行う

HWの制約も存在する



SPARCの場合call命令を実行すると



callerのレジスタ%o0-%o7を%i0-%i7にマップす

る



return時には、Return addressがcallerによって

%i7に指定されていると考える



x86の場合call命令を実行すると



Stack Segmentに、return addressがpushされ

る



Security視点でのアタックの場合、これらが悪用

Calling conventionのデザイン



perlでは…

sub perr

{

my ($a,$b) = @_;

…



スタック上に$a, $bの場所を確保し、大域変数”_”

の値（可変長）を「流し込む」



perlは、原則全部が「大域変数」（frameを作らな

い）発想だったが、そういうわけにはいかなくて

_…

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 この実行により、 実行結果がLabel 9で 引数として 参照可能になる

呼ばれる方

$ 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 引数は_で渡ってくる リストとして frameを構成 名前のresolutionが 済んでいる Return addressはここ

関数呼び出しをデザインする



Perlにおいても、いろいろな情報が貯められて

いる（

ASTには出てこないが…）



引数情報（実引数

@_の取り込み）



ローカル変数のリスト（

pad）



リターンアドレス（

end）



戻り値

()

関数呼び出しをデザインする

 関数内のコードで 変数を参照するときには、「どの」変数を参照しているかを決めなければならな い。 def fac(n) { my(r); r = 1; while (n>0) { r=r*n; n=n-1; } r = 10; n = 3; fac(5); r; n;



data segment vs. stack segment



一般的に、

frameは関数コールごとに作成さ

れるので、

stackとして実現するとよいかもし

れない



並列実行等、関数実行のオプションが増えると、

単一の

stack segmentでframeを実現するのは

時代遅れかもしれない



関数コールごとに概念上独立の

frame構成を許

す

Javaのチームは、頭が良いんでしょうね



DCIでは

t_vardat frames[128];

int frametop;

int savedframetop;



環境が新たに作られる



{…}の始まり

case LENV:

{ int r;

lvarstack[lvarp++] = frametop;

r = eval(cstack[top].val1);

frametop = lvarstack[--lvarp];

return r;

}



関数コール

funprolog(v->param, cstack[top].val2,

v->paramlen);

r = eval(v->val);

calledtop = savedcalledtop;

funepilog();

frameを作って、parameter名で 引数の値を参照可能にする frameの破壊（stackと同じく、topのpointer を巻き戻す）

Name Resolution



frame内の変数か？大域変数か？



参照の仕方が異なることが通常



関数ボディ内の変数参照をあらかじめ解析してお

く。

Perlではgvとpadの二つのアクセス方法を提

供する



Perlでは、実行前に解析して解決しておく(gv or

pad)



DCIでは実行時に、変数参照を解析する。

一般のコンパイラでは？



話の本質は

interpreterかcompilerかに依存し

ない



教材だけでは、世間の水準を理解しずらい

…



関数呼び出しの仕方を観察してみる



対象となるアーキテクチャ、メモリモデルに依存す

る



C on ネイティブなマシン環境と、Java on JVM,

Python on CPythonを例にとって見る

Cの実行環境



GCCはCPUを直に実行す

るコードを生成する



アセンブリコードを見てみる



ソースコード

a.c



gcc –O3 (4.8.2)



アセンブリコード

a.s



この後に、リンクが入るのだ

が、これは省略する

Calling Convention



Calling conventionは一般にハードウェアとし

ての

CPUの機能ではなく、言語処理系での「約束

事」



もちろん、その前の

HWの制約を理解することが

必要



スタックに積むのは

x86で一般的



その他では、レジスタのある部分を引数を割り当

てるのに使用する言語処理系が多数



IBM POWER上のコンパイラ



SPARC上のコンパイラ

Calling Conventionを調べるには



コンパイラの内部ドキュメントをみましょう



他のコンパイラとの連携するためには

Calling

Conventionは公開情報でなければなりません



なければ探しましょう。



cdecl かregcall



間違っても最初からアセンブリコードを解析しては

いけません。



で、

GCCだ



あなたは

Wikipediaを信用するか？（結果的に正しく

ても）

Intelの定めるCalling Convention



まずは

naitive環境から見る



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 x86)

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

movl 12(%ebp), %eax

leal

(%eax,%eax), %edx

movl 8(%ebp), %eax

leal

(%edx,%eax), %ecx

movl 16(%ebp), %edx

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



Stack segmentに

frameを作る

esp +8(引数ここから) +12 +16 Return address ebp ＋方向 スタックはこちら方向に 伸びる



（課題

6）

手近にあるコンパイラをひとつ対象にし、

calling conventionとフレームを解析せよ。この時

に

以下のことに注意せよ

（１）コンパイラ・

OS・CPUを明記すること

（２）解析の手法を明らかにすること

（３）

calling conventionは、呼び出し側と呼び出さ

れる側の約束であるが、そのときに呼び出される側

から呼び出し側へも約束が存在することに注意せよ

X86-64ではどうか

コンパイラのオプションは効いているか？

extern int gv;

a(int x0, int x1, int x2)

{

return x0+x1*2+x2*3;

}

b()

{

return gv+a(1,2,3);

}

cc –O0 -S

.file "x.c" .text .globl a .type a, @function a: .LFB0: .cfi_startproc pushq %rbp .cfi_def_cfa_offset 16 .cfi_offset 6, -16 movq %rsp, %rbp .cfi_def_cfa_register 6 movl %edi, -4(%rbp) movl %esi, -8(%rbp) movl %edx, -12(%rbp) movl -8(%rbp), %eax leal (%rax,%rax), %edx movl -4(%rbp), %eax leal (%rdx,%rax), %ecx movl -12(%rbp), %edx movl %edx, %eax addl %eax, %eax addl %edx, %eax addl %ecx, %eax popq %rbp .cfi_def_cfa 7, 8 ret .cfi_endproc .LFE0: .size a, .-a .globl b .type b, @function b: .LFB1: .cfi_startproc pushq %rbp .cfi_def_cfa_offset 16 .cfi_offset 6, -16 movq %rsp, %rbp .cfi_def_cfa_register 6 movl $3, %edx movl $2, %esi movl $1, %edi call a

movl %eax, %edx

movl gv(%rip), %eax addl %edx, %eax popq %rbp .cfi_def_cfa 7, 8 ret .cfi_endproc .LFE1: .size b, .-b

cc –O3 -S

.text .p2align 4,,15 .globl a .type a, @function a: .LFB0: .cfi_startproc

leal (%rdi,%rsi,2), %eax leal (%rdx,%rdx,2), %edx addl %edx, %eax

ret .cfi_endproc .LFE0: .size a, .-a .p2align 4,,15 .globl b .type b, @function b: .LFB1: .cfi_startproc

movl gv(%rip), %eax

addl $14, %eax ret .cfi_endproc .LFE1: .size b, .-b .ident "GCC: (Ubuntu7.3.0-16ubuntu3) 7.3.0" .section .note.GNU-stack,"",@progbits

Javaの実行環境



Cと同じことをJavaで調べられるだろうか？

（

nativeでもVMでも基本は同じ）



Java on JVMのCalling Conventionは…



とりあえず

JNI (Java Native Interface)はここ

https://docs.oracle.com/javase/jp/1.5.0

/guide/jni/index.html

JAVA VM

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

フレームに格納されるデータ



リターンアドレス

(*returnで使用)



local variable (*load/*storeで使用)



Exception Table

コンパイルしてみる

class x {

static int content; x(int y) {

content = y; }

public int get_content() { return content;

}

public void addxx(x x1) { int y; y = x1.get_content(); content += y; } } ０ フレーム フレーム０ フレーム１ フレーム２ フレーム３ this 第一引数 第二引数 第三引数

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 }

Argumentの扱い

３ Invoke前 メソッドAの フレーム ３ Invokeされた時の AとBのフレーム ５ Invoke完了後の メソッドAの フレーム

Pythonでも同様な観察ができる

>>> def myplus(i, j):

... return i+j;

...

>>> dis.dis(myplus)

2 0 LOAD_FAST 0 (i)

3 LOAD_FAST 1 (j)

6 BINARY_ADD

7 RETURN_VALUE

>>> def myplus2(i,j,k):

... return i+k+myplus(i,j);

...

>>> dis.dis(myplus2) 2 0 LOAD_FAST 0 (i) 3 LOAD_FAST 2 (k) 6 BINARY_ADD 7 LOAD_GLOBAL 0 (myplus) 10 LOAD_FAST 0 (i) 13 LOAD_FAST 1 (j) 16 CALL_FUNCTION 2 19 BINARY_ADD 20 RETURN_VALUE

文法要素以降の作業（

VM構築）

High Level Concept

Syntax Design Semantics Design Parsing Ｓｅｍａｎｔｉｃ Analysis（Type/Class Check) Code Generation(codemit.c) Execution(vm.c) Optimization Optimization Interpreter Compiler VM

stack machineの定義



ISAを定める



Stack



Code segment



Data segment



Special registers/Data Structure



実行エンジンのプログラムを書く

(vm.c)



ASTから、命令列を生成するプログラムを書く

(codemit.c)  evalとの相似に注目する

(homomorphicとまではいかないが…）

STACK (Frame) DATA SEGMENT (Data) CODE SEGMENT (Functions) Object Table PC SP FP

Alternative to source tree

traversal



VMを定義して、その上のコード生成を行う



stack machineの設計

t_codeseg codeseg[CODESEGSIZE];

t_stackseg stackseg[STACKLEN];

int dataseg[DATASEGSIZE];

t_dataseg objectab[128];

int framestack[STACKLEN];

Mnemonic （最小限）

"NOP", "POP", "DUP", "U_NOT", "B_ADD", "B_SUB", "B_MUL", "B_DIV", "B_GREATEREQ", "B_GREATER", "B_LESS", "B_LESSEQ", "B_EQUAL", "B_NOTEQUAL", "JMP", "JMPPOS", "JMPZ", "JMPNEG", "PUSH_CONST", "PUSH_GVAR", "PUSH_LVAR", "PUSH_ADDR", "STORE_GVAR", "STORE_LVAR", "STORE_ADDR", "CALL", "RETURN", "PRINT_TOP ",



VAR (変数参照)に対応するコード生成



対応する

evalの部分

case VAR:

{int varpos = staticvarsearch(cstack[top].val1); if (varpos == -1) {

codepush2(OP_PUSH_GVAR, cstack[top].val1); } else {

codepush2(OP_PUSH_LVAR, varpos); } break; } case VAR: /* 2018 */ {int varpos; if ((varpos = varsearch(cstack[top].val1)) == -1) { return vars[globalvarsearch(cstack[top].val1)].val; } else { return frames[varpos].val; } }



MOVに対応するコード

case MOV:

codemit(cstack[top].val2);

codepush(OP_DUP); /* added on March 20, 2018 */ {

if (cstack[cstack[top].val1].opcode == VAR) { int varname = cstack[cstack[top].val1].val1; int varpos = staticvarsearch(varname);

if (varpos == -1) { /* global var */

codepush2(OP_STORE_GVAR, varname); } else { /* local var */



VMのISAのデザインは、哲学の発露（少し大

げさ）



JVM



なぜ、

invokeが複数種類あるのか



なぜ、基本型ごとの命令セットに分離されているのか



CPython



なぜ、ループ命令があるのか



CALLに対応するコード



VMでの実行

case FUNCALL: { int alen;

alen = codemitargs(cstack[top].val2); codepush2(OP_PUSH_CONST, alen); codepush2(OP_CALL, cstack[top].val1); break; } switch (objectab[gv].typ) { case FUN: framestack[savedframetop++] = pc+1; framestack[savedframetop++] = stacktop-objectab[gv].paramlen+1; pc = objectab[gv].val; break; …

Native Codeへのコンパイル



Native Codeへのコンパイルも、その本質は

変わりません



Assembly codeの出力ができるようにするには

プラス少しの文法の勉強で足りる



Native Codeを相手にするときは、ファイル

形式

, load, linkについて、少し勉強する必

要があります



次回、おおまかなところについてはふれます

仕様



プログラミング言語を定義したら、仕様にまとめてみる。



これができない人が

…



概念の説明を最初につける



プログラミング言語を定義するときに必要な（デリケート

な）要素は大体以下の通り



プログラム全体の構造



制御構造



データオブジェクト



式



関数（手続き）の扱い



環境、変数のバインディング



＋ 多言語とのインターフェイス、ライブラリ関数

課題

7



自分で言語を定義してみよ



仕様書を書け（これが一番大事）



High Level Conceptは「新しい概念のない電卓であ

る」でもかまわない



ただし、変数は扱えるようにすること



関数コールをデザインすること



Lexical analysisに関係するコードは自分で書くこと



Parse したら、ASTは生成できるようにすること



評価系

(eval)は書かなくてもよいが…きっと書きたく

なる。

(Note)

言語

designとVMのInterface



「値」とは何か？



基本型だけではない



Scalar＋Array（Fortran）



Tuple, list, (Python)



Object (OOP)



計算機械の上での実装（表現）の検討の必要性（

処理系の検討には必須）



Referenceのメカニズムの検討



オブジェクト管理、メモリ管理

(in VM) へつなが

る

ちょっと見てみる



Perl



stringが基本型のひとつとして入る



scalar ($xの形) + array (@xの形)



Objectは…



厳密に言えばオブジェクト指向のようなプログラミング

スタイルを

packageを導入することで提供



Python



基本型＋

tuple+リスト



Objectは最初からデザインの中に入っている

(Note)

関数コール、フレーム管理の

Semanticsの例

 Javaの規格

 15.12.4 Runtime Evaluation of Method Invocation

 15.12.4.1 Compute Target Reference (If Necessary)  15.12.4.2 Evaluate Arguments

 15.12.4.3 Check Accessibility of Type and Method  15.12.4.4 Locate Method to Invoke

 15.12.4.5 Create Frame, Synchronize, Transfer Control

 15.12.4.6 Example: Target Reference and Static Methods  15.12.4.7 Example: Evaluation Order

 15.12.4.8 Example: Overriding

 15.12.4.9 Example: Method Invocation using super

 Fortranの規格

VMを用いた実行モデルの記述



Virtual Machineを定義する



Operational Semanticsの忠実な表現

 ISAを定義する（大別してstack machineとregister machine）  プログラムの意味とは、VM上にコンパイルされたコードのVM上の 意味と定義する  ハードウェアシステムとは薄皮一枚で隔てられている



「状態」の記述

 メモリの状態  スレッドの状態



「状態遷移」の記述

 主だった命令がマシンの状態をどう変化させるかを記述



VMで行うのは、計算機械の「実装」だけではない



オブジェクトの生成・GCに係るメモリ管理



関数呼び出しに係るフレーム管理、並列性に係るスレッド管理

Java VM



Java VMもPython VMもスタックマシンです



JVMの当初の目的は、安全な形でコードの流通

性を高めることであった（特にアプレット）



コードの流通性の確保が目的の一つに入っていた



HTML5で廃止



JavaのSemanticsはJava VMの上で定義する

ことができる



速度を考えて

JITが出現した



速度はこんな技術で稼ぐんじゃない



https://docs.oracle.com/javase/specs

/jvms/se10/jvms10.pdf （2018）



（課題

8）上のドキュメントを以下の観点から要

約せよ



VMの仮想機械としての構造



Javaの実行をサポートするためのフレーム管理、

メソッド呼び出し等、命令セットの特徴

Python VM

 どこかの書き込み(2004)

Xavier> Is there any paper describing the instruction set of the Python

Xavier> Virtual Machine or should I learn anything from Python/ceval2.c?

I think right now Python/ceval.c is your only choice. I recently began working on something, but really have nothing more than a crude

outline. If

you start looking at ceval.c and get stuck, drop me a note. I'd be happy to

try and explain things. It might motivate me to work on pyvm.tex a bit more as well. ここでしょうか (ceval.c)(泣) https://github.com/certik/python-3.2/blob/master/Python/ceval.c もしくはdisassemblerの方を見た方がよいでしょうか https://docs.python.jp/3/library/dis.html#python-bytecode-instructions



（課題

8’）上のドキュメントを以下の観点から要

約せよ



CPython VMの仮想機械としての構造



Pythonの実行をサポートするためのフレーム管

理、メソッド呼び出し、ループ実行等の命令セット

の特徴

MSの.NETも同じ哲学を持つ



プログラミング言語と実行のための仮想機械

は「くっついて」いる必要はない。



言語から仮想機械への「コンパイラ」が提供さ

れればよい



仮想機械の動作仕様が定義されていればよ

い



⇒

CLI (MS .NET)