Compiler Construction Lecture No.5
Menu Menu
部分評価としてのコンパイラ
しかし、このコンパイラ信じられないほど馬鹿である。1+1 の計算も、まじめに実行時に行う。このような計算は実は、コンパイル時におこなってしまって構わない。では、どこまでコンパイル時に計算できるのだろうか?このような考え方は、部分評価(partial evaluation) と呼ばれる。これを、プログラムからプログラムを計算するプログラム変換、α(アルファ)を使って以下のように記述する。
P'(Y)(X) = α(P(X,Y),X) P(X,Y)のうち、Xの値を定数として可能な部分を先に計算する。
αはプログラムと入力変数の指定の2つの引き数を持つ。αは、Pと入力変数の値を受け取り、プログラムP'を出力する。P'は、Xの値を指定すると、それに対応するプログラムを返すプログラムである。P'を、入力の一部を前もって計算するので、部分計算と呼ぶ。
P''(Y) = P'(Y)(5) = α(P(X,Y),X)(5)
とすると、X=5を仮定して計算を進めたプログラムを意味する。このαを二村射影(Futamura projection)と呼んでいる。例えば、i(P)(X)で、入力Xを持つプログラムP(X)をインタプリタiが実行することを表すことにしよう。ここでPは、Xを入力として持つ任意のプログラムを表す変数である。
これに、部分計算αを使って、
α(i(P),P) 入力X以外の部分Pを前もって実行する。
とする。c(X)(p)は、pの字句解析やら構文解析やらの部分を前もって計算したプログラムである。これをコンパイルと考えることもできる。つまりコンパイラc(P)は、
c = α(i(P),P)
となる。また、
y(P) = α(I(P),I)
は、コンパイラコンパイラを表す。あるインタプリタiが与えられると、y(P)(i) は、Pをコンパイルするコンパイラ c(P) = α(i(P),P)(P) を返す。
さらに良いコードを出すためには
ここでは、少しだけ部分計算をおこなう努力をしてみよう。- わかっている結果の計算は先に行う
- 計算を順序を変える
- スタックでなくレジスタに割り付ける
- 同じ式が出てきたら、それを2度計算するようなことはしない
このためには、どうしても、一旦、プログラムを表す構造を作る必要がある。その構造を作る時、あるいは、作った後で解析して、より良いコード生成を行う。この構造は、もちろん、構文木である。コンパイラによって、単なる構文木ではなく、より複雑な構造を採用することもある。気にすると複雑になりやすいので、一旦、疑似コードを生成して、その後に、その最適化をおこなう方法もある。構文木自身も、post fix code (後置コード)と呼ばれる疑似コードとみなすこともできる。
中間木の生成
木を生成するのは、計算するのとほとんど同じで、下位の構文要素の木を下位の構文解析の関数から取りだし、上位に新しい木のノードをつけ加えて送れば良い。木のノードは例えば、
#define NEW(type) ((type *)malloc(sizeof(type)))
typedef struct node {
struct node *left;
struct node *right;
int type;
int value;
} node, *node_ptr;
などのように表すことができる。これを生成するには、
node_ptr
new_node(int type,int value,node_ptr left,node_ptr right)
{
node *d;
// d = (node *)malloc(sizeof(node));
d = NEW(node);
d->type = type;
d->value = value;
d->left = left;
d->right = right;
return d;
}
などとすれば良い。ここでtypeとvalueは、字句解析が返した値をそのまま使う。例えば、aexpr では、以下のように木を生成する。
node *
aexpr()
{
node *d;
d = mexpr();
while(last_token!=EOF) {
switch(last_token) {
case '-':
d = new_node('-',0,d,mexpr());
break;
case '+':
d = new_node('+',0,d,mexpr());
break;
default:
return d;
}
}
}
この時、new_node()は、mexpr()が二つ呼ばれてから呼ばれることに注意しよう。インタプリタと違ってdは、値ではなく木である。
new_node() では、mexpr()の値が分かった段階で呼ばれるのだから、もし、計算可能ならば、その場で計算をおこなうことが望ましい。
node *
new_node(type,value,left,right)
int type;
int value;
node *left;
node *right;
{
node *d;
if ((left && left-> type =='0') &&
(right && right-> type =='0')) {
switch(type) {
case '>':
right->value = (left->value > right->value);
free(left); return right;
break;
case '+':
right->value = left->value + right->value;
free(left); return right;
break;
...
}
}
d = (node *)malloc(sizeof(node));
d->type = type;
d->value = value;
d->left = left;
d->right = right;
return d;
}
などとすれば良い。 s-tree-compile.c
しかし、これで十分だろうか?
実際には、式の計算順序は、+, * などによって変更することができる。この変更によって定数として計算できる範囲が広がることがある。これは、定数を木の葉の方に移動させることによって実現することができる。あるいは、木を使って、共通の式を2度計算しているかどうかを調べることができる。(問:このようなアルゴリズムを考察してみよ)
実際のコンパイラでは、浮動小数点(floating point)と整数(integer)が混在することもあり、安易に計算順序を変更すると、かえって浮動小数演算が増えたり、誤差が大きくなったりすることがある。気を付けて計算する必要がある。
中間木からのコード生成
一旦、中間木ができてしまえば、コード生成は容易である。また、引き算の場合の引き数の順序の制御も楽になる。
code_generate(d)
node *d;
{
int assign;
switch(d->type) {
case '0':
emit_value(d->value);
return;
case 'v':
emit_load(d->value);
return;
....
default: /* calculation */
code_generate(d->right);
emit_push();
code_generate(d->left);
switch(d->type) {
case '+': emit_calc(O_ADD); break;
case '-': emit_calc(O_SUB_R); break;
case '/': emit_calc(O_DIV_R); break;
case '*': emit_calc(O_MUL); break;
default:
error("Internal Error, unknown opecode");
}
return;
}
}
となる。中間木を順序よくたどりながらコードを生成する。ただし、この方法では再帰呼び出しが多用されるので、それに対する工夫が必要となる場合もある。
実際のコンパイラでは、中間木は式だけなくて、手続き内のすべての文に対して生成することが多い。この時、case文のようなものは、超巨大になることがあるので、中間木も巨大になってしまう。この時に安易な木の扱いを行うと、非常に遅いコンパイラになってしまうことがある。
問題5.3
上の構文木の生成では、malloc/free を繰り返している。これは、一般的には効率が悪い方法とされている。前もって、いくつかまとめてnodeをmallocし、それを再利用する方法を考案し、実装せよ。実際には、式の計算順序は、+, * などでは変更することができる。この変更によって定数として計算できる範囲が広がることがある。これは、定数を木の葉の方に移動させることによって実現することができる。あるいは、木を使って、共通の式を2度計算しているかどうかを調べることができる。このようなアルゴリズムを考察し、例題のコンパイラを変更して実装せよ。
問題5.4
s-code-intel-r.c を使った、s-intel について、論理演算 &,| を拡張して見よう。余裕があれば他の拡張にも挑戦して見よう。- 中間木を使い、a+(b+c) -> (a+b)+c のような変形をサポートする
- 配列をサポートする
- Cの3項演算子 (cond)?(true):(false)
- Pointer演算
課題
関数呼び出しの実現変数のスコープ
関数呼び出しのコード生成
レジスタのセーブ
中間木を使った部分評価
バイトコードの設計
バイトコードの生成と実行
バイトコードからのコンパイル