この記事はひとりでCPUとエミュレータとコンパイラを作る Advent Calendar 2017の24日目の記事です。

一昨日は抽象構文木を作り、昨日はシンボルテーブルを作成した。これらを元にアセンブラのコードを吐き出せば、コンパイラは完成だ。

この最後の工程をコード生成という。難しい話はないものの、説明すべき内容が多い。まず第一部として制御フローのコード生成を説明し、第二部で計算関連を説明することにする。

第一部:制御フロー

制御フローというタイトルだが、拡大解釈して計算以外の全処理のコード生成をここで解説する。

抽象構文木をアセンブラのコードに変換する命令は main関数内で

// main関数内

// 空のシンボルテーブル
TABLE tb[MAX_HASH_NUMBER];

// srcは抽象構文木の構造体
// fileは出力ファイルポインタ
asm_program(file, src, tb);

で呼び出される asm_program関数によってスタートする。

この関数は以下のテンプレートに従って抽象構文木をx86のニーモニックに変換する。

bits 32
org 0x0
jmp _main_

* -- LOOP BEGIN (PROGRAMノードに生える関数ノード N でループ)
*
* 1. シンボルテーブルにNの引数とローカル変数を追加
*
* 2. asm_function(N) で処理を書き出す
*
* 3. N が main関数なら、最後を
*    jmp _program_halt_
*    で終える
*
* 4. N が main 以外の関数なら、最後を
*    leave
*    ret
*    で終える
*
* 5. シンボルテーブルから N の引数とローカル変数を削除
* -- LOOP END

_program_halt_:
hlt

* グローバル変数の数だけ
dd 0x0
* を書く

このコードを上から辿ると

bits 32とorg 0x0はおまじない
次のjmp _main_でmain関数にジャンプするが、それは LOOP の内側にいる
main関数が終了すると、_program_halt_に飛ぶ
hlt命令でCPUが停止する

となる。C言語を実行してる雰囲気がつかめると思う。

最後のdd 0x0命令は、単純に 0x00 0x00 0x00 0x00 という4byteの機械語に変化する命令だ。こうすることで、ゼロで初期化されたグローバル変数が関数本体の後ろに設置される。

関数

前節のPROGRAMノードのテンプレートを見ると、関数処理の書き出しは asm_function関数で行われていた。

こいつは以下のテンプレートに基いてコードを生成する。

push ebp
mov ebp, esp
sub esp, スタックフレーム

* -- LOOP BEGIN
* FUNCTIONノード直下の、V_DEC以外のノードの処理を
* asm_sentence() で書き出す
* -- LOOP END

スタックフレームはローカル変数の領域を確保する処理だった。要するにローカル変数の数 * 4だけespを引けば良い。ローカル変数の数は、シンボルテーブルを走査すれば容易く計算できる。この辺の詳しい解説は昨日のシンボルテーブル記事の最後に載せた。

ついでにRETURNノードの書き出しも見ておこう。処理は asm_return関数で行っているのだが、テンプレートは

* 返り値をスタックに積む
pop eax

シンプルだ。これで良い理由は関数呼出の記事を参照して欲しい。

ちなみにこれは手抜き実装なので、関数末尾以外のreturn文は破綻する。仕様というかバグに近いな。

文

前節で、関数の中身を書き出す処理は asm_sentence関数に一任していた。

これはテンプレートではなく実装を貼った方が分かりやすい。

void asm_sentence(FILE *fp, NODE *sentence, SOURCE s, TABLE *tb) {
  if (sentence != NULL) {
    const int kind = sentence -> kind;

    // 文の中に文がある場合
    if        (kind == SENTENCE) {
      NODE *down = sentence -> down;

      // 再帰呼び出し
      while (down != NULL) {
        asm_sentence(fp, down, s, tb);
        down = down -> right;
      }
    }

    // 実質的な処理
    else if (kind == IF_FLOW)    asm_if(    fp, sentence, s, tb);
    else if (kind == WHILE_FLOW) asm_while( fp, sentence, s, tb);
    else if (kind == RETURN)     asm_return(fp, sentence, s, tb);
    else if (kind == ASSIGN)     asm_assign(fp, sentence, s, tb);
    else if (kind == CALL)       asm_call(  fp, sentence, s, tb);
    else syntax_error(__func__);
  }
}

この関数の挙動を二言で言うと

文の中に文がある場合は、再帰的にasm_sentence自身を呼び出し、どんどんもぐる
ifやwhile、代入文であれば、専用の書き出し関数 asm_*** に処理を丸投げ

さっきreturn文は解説したので、その他のif, while, assign, call文の書き出し関数を見てみよう。

if文

asm_if関数の処理を見てみる。

まず条件文を処理するテンプレートを見ると

* 条件の部分をasm_expr()に投げる。結果がスタックに積まれる
pop eax
cmp eax, 0

要するに条件式と0を比較している。条件式の計算を行うasm_expr関数は、第二部の計算パートで扱うことにしよう。

次に、構文がif (...) {...}型の場合のテンプレートを見てみる。

je  LABEL@IFNUM@_if_end
* asm_sentence() で {...} の部分を書き出す
LABEL@IFNUM@_if_end:

さっきの条件式が0なら{...}の部分がスキップされる。これはC言語の

if (0) {実行されない} ここに飛ぶ

if (0以外) {実行される} 終わったらここに進む

という分岐フローに対応している。

ちなみに@IFNUM@は"if"文字列のトークン番号を指す。この数字は、ソースコード内に出現する複数のif文を区別するためのものだ。 @IFNUM@無しでは、異なるif文のラベル名が重複してしまう。

次に構文がif (...) {...} else {...}のテンプレートを見てみる。

je  LABEL@IFNUM@_else
* asm_sentence() で else節 の {...} の部分を書き出す
jmp LABEL@IFNUM@_if_end
LABEL@IFNUM_else:
* asm_sentence() で if 節の {...} の部分を書き出す
LABEL@IFNUM@_if_end:

さっきとほぼ同じなので、説明不要だと思う。

while文

asm_while関数で用いるテンプレートは

* 条件の部分を asm_expr() に投げる。結果がスタックに積まれる
pop eax
cmp eax, 0
je  LABEL@WHILENUM@_while_end

LABEL@WHILENUM@_while_begin:
* while {...} の中身の処理を asm_sentence() に投げる
* 条件の部分を asm_expr() に投げる。結果がスタックに積まれる
pop eax
cmp eax, 0
jne LABEL@WHILENUM@_while_begin

LABEL@WHILENUM@_while_end:

前節のif文の処理が理解できれば、while文の仕組みも分かるだろう。

ifの場合と同様に、asm_expr関数で条件式を計算して0と比較し、je命令でジャンプしている。条件式が0だった場合は、C言語の

while (0) {実行されない} ここにジャンプ

という処理が実現する。

条件式が0以外だった場合は、while {...}の中身を実行する。

その後再び条件式を評価し、もし条件式が0ならジャンプせずループを抜ける。条件式が0以外だった場合は、while {...}の{あたりにジャンプし、ループが再開する。

代入文

代入文の asm_assign関数で使用するテンプレートを見てみる。

* 左辺の変数名をfprint_variable()でアドレスに変換
* 右辺をasm_expr()に投げる。結果がスタックに積まれる
mov [左辺のアドレス], eax

要するに fprint_variable関数で指定される場所に、右辺の結果をmovしている。この関数の実装は

void fprint_variable(FILE *fp, NODE *var, SOURCE s, TABLE *tb) {
  int hash = search_hash(var, tb, s);
  if (hash < 0) {
    fprintf(fp, "\n");
    syntax_error(__func__);
    fprintf(fp, "hash:%d str:%s\n", hash, s.token[var -> init].str);
  }
  int block   = tb[hash].block;

  if      (block == 0) fprintf(fp, "[_%s_]"    ,  tb[hash].str);     // グローバル変数
  else if (block == 1) fprintf(fp, "[ebp+0x%x]",  tb[hash].address); // 関数の引数
  else if (block >  1) fprintf(fp, "[ebp-0x%x]", -tb[hash].address); // ローカル変数
}

変数名でシンボルテーブルを検索し、スコープに応じてアドレスを書き出している。グローバル変数と引数とローカル変数でアドレスの形式が異なるが、これはcdecl規約やスタックフレーム等の絡んだややこしい話だった。詳細は昨日のシンボルテーブル記事の最後の方で説明しておいた。

関数呼出文

関数呼出しを処理する asm_call関数のテンプレートを見てみる。

まず引数がない場合のテンプレート

call _呼び出す関数名_

明らかに説明不要なので、引数がある場合のテンプレートを見てみる。

* LOOP BEGIN
* 関数呼出の引数を、右側から順に
* 全て asm_expr() に投げる。
* 計算結果は自動でスタックに積み重なる
* LOOP END

call _呼び出す関数名_

* LOOP BEGIN (引数の数だけ)
pop edx
* LOOP END

まず最初に、cdecl規約に従って右側の引数から順にスタックに積む。意味が分からなければ関数呼出の記事を読み直して欲しい。

次にcall命令で関数を呼び出す。

最後に、引数の数だけpop edxを行っている。これは引数として積んだスタックを解放する処理だ。この処理を忘れると、関数呼出しの度にスタックがどんどん増えてゆき、最終的にオーバーフローしてしまう。

ちなみにもう少しスマートに解放するには、add esp 引数の数*4とすればよい。

以上で制御フローの話は終了だ。 x86のニーモニックや関数呼出規約を知った上で読めば、何一つ難しいところはないと思う。

第二部: 計算

前セクションではasm_exprという関数が頻出していた。

これは「式」を受け取って計算結果をスタックに積む関数だが、実装は未説明だった。

ここからの目標は、asm_exprの実装を理解することだ。

スタックマシン

要するに数式をニーモニックに変換したいのだが、まずは簡単な

(0+2)+(4+(6+8))

という数式を考える。これをC言語のコードだと思って抽象構文木を作ると

f:id:kaitou_ryaku:20171224065710p:plain:w500

手で計算するのは簡単だが、x86のCPUにやらせるにはどうすれば良いだろうか。素直に考えるとeax=0、ecx=2、edx=4のように各レジスタに値を割り振って計算するのが手っ取り早い。しかしこの方法は、式中の項の数が増えた時に破綻してしまう。レジスタの数は高々10個程度しかないからだ。

そこで、あえてレジスタの使用を最低限に留め、スタックを主体として計算する方法を考えてみたい。スタックは無尽蔵に使えるので、項が増えても対応できるはずだ。

x86のレジスタを減らした、以下の系を考える

2つのレジスタeax,edxとスタックメモリがある
レジスタ同士を加減乗除し、結果をレジスタに代入できる

このような系をスタックマシン[^1]という(多分)。x86はスタックマシン的な扱い方ができる。この系でさっきの計算を実行してみよう。

計算のアルゴリズム

スタックマシンによる計算の手順をgif動画にしてみた。

f:id:kaitou_ryaku:20171224065718g:plain:w500

文章でアルゴリズムを説明すると

どんどん左下に進む
左下の即値に到達したら、値をスタックに積み、ノードを削除
1つ上に戻り、1つ右下に移動し、さらにどんどん左下に進む
1-3を繰り返す
途中で右下の即値に到達したら、値をスタックに詰み、ノードを削除
演算を実行し、その結果で演算のノードを置換

みたいな感じだが、意味不明だと思うのでgif動画をしっかり見てくれ。スタックマシンに搭載された2つのレジスタは、スタックに積まれた2つの即値を足す時に使用している。

ニーモニックで処理を記述すると

mov  eax, 0x0 ;
push eax      ; 0をスタックに積んだ
mov  eax, 0x2 ;
push eax      ; 2をスタックに積んだ
pop  edx      ;
pop  eax      ;
add  eax, edx ; eax=0+2
push eax      ; 2をスタックに積んだ
mov  eax, 0x4 ;
push eax      ; 4をスタックに積んだ
mov  eax, 0x6 ;
push eax      ; 6をスタックに積んだ
mov  eax, 0x8 ;
push eax      ; 8をスタックに積んだ
pop  edx      ;
pop  eax      ;
add  eax, edx ; eax=6+8
push eax      ; 14をスタックに積んだ
pop  edx      ;
pop  eax      ;
add  eax, edx ; eax=4+14
push eax      ; 18をスタックに積んだ
pop  edx      ;
pop  eax      ;
add  eax, edx ; eax=2+18
push eax      ; 20をスタックに積んだ

C言語で記述

// 即値ならスタックに積む
// 演算子ならasm_operatorを呼び出す
void asm_expr(NOedxE *expr) {
  if (exprが即値) {
    printf("mov eax, 即値");
    printf("push eax\n");
  }
  else if (exprが加算演算子) asm_operator(expr);
}

// 左下と右下の各々をasm_exprで処理
// 右下が即値ならば、演算を実行し、結果をスタックに積む
void asm_operator(NOedxE *ope) {
  NOedxE *down_left  = ope -> down;
  NOedxE *down_right = down_left -> right;

  asm_expr(down_left );
  asm_expr(down_right);

  printf("pop edx\n");
  printf("pop eax\n");

  if (opeが加算演算子) printf("add  eax, edx\n");
  printf("push eax\n");
}

ポイントは、asm_exprでasm_operatorを呼び出し、またasm_operatorからasm_exprを呼び出す部分。つまり再帰関数になっている。木の探索でよく使うやつだ。このコードは加算演算子しか書かなかったけど、減算や乗除に対応するには

if (exprが加算演算子)
if (opeが加算演算子)

の部分に他の演算の処理を付け足せば良い。減算ならaddの代わりにsub、乗算ならimul、除算ならidiv、剰余ならimodとすればよい。

変数と関数への対応

式中に変数や関数が含まれている場合を考える。

変数については、第一節の制御フローの代入文のところで説明したように、変数名を fprint_variable関数に入れることで値を取得できる。
関数については、第一節の制御フローの関数呼出文の節で値の取得方法を解説した。

これらの方法で得られた値をスタックに詰めば、スタックマシンを用いた計算を継続することができる。

比較演算子の処理

例えばa==bは、aとbが等しい場合は1で、異なる場合は0と定義される(Cと同じ)。こうした処理を実行するには、cmp命令と条件付きジャンプ命令を使えば良い。 cmp命令はsub命令を実行したと仮定してフラグだけを更新し、汎用レジスタは変更しない処理だった。

どちらも二項演算子であり、ニーモニックをadd命令からcmp命令に変更すればよい。

例として、aの値がeaxに入っていて、bの値がedxに入っている場合に、a==bの値をeaxに入れる処理は

cmp eax, edx ; eax-edxを実行したと仮定してフラグを更新
je  _TRUE_   ; ゼロフラグが立っていればジャンプ。つまりeaxとedxが等しければジャンプ

mov eax, 0   ; ジャンプしなかった場合は、eaxに0が入る
jmp _END_

_TRUE_:
mov eax, 1   ; ジャンプした場合は、eaxに1が入る

_END_:       ; いずれの場合もここにたどり着く

比較演算子と条件付きジャンプ命令を表にしておくと

比較演算子	ジャンプ命令
"=="	`je`
"!="	`jne`
"<"	`jl`
"<="	`jle`
">"	`jg`
">="	`jge`

冒頭の画像のB_OPERATORのノードは全て加算演算子だったが、もし数式中に比較演算子が出現したら、今説明した方法でeaxを作りスタックに積むことで計算が実行できる。

以上でコード生成は終了。コンパイラが完成した！

どうでもいい話

長かったアドベントカレンダーも、いよいよ明日で終了だ。それにあわせて今日は大容量の記事になってしまった。しかし中身は薄いので、苦労せずに終えると思う。

明日は自作コンパイラのコードを自作エミュ上で動かし、自作CPU上でも動かしてみる。すべてが繋がる。

しかくいさんかく

解答略のメモ

24日目: [コンパイラ] コード生成