Lecture Notes

1-6 コード生成１

前回は yacc を使って構文木を組み立てた。今回は、こうして組み立てた構文木を元に、Intel x86 アーキテクチャ用のコード生成をおこなう。

IA32 (x86) の命令セット

Intel Pentium や AMD Athlon などの x86 系と総称されるプロセッサは IA32 と呼ばれる、i8080 時代からの互換性をひきづった命令セットをもつ。

IA32 は数多くの命令を含むが、この講義で使うのはごく一部である。

レジスタ

IA32 は8つの汎用 32bit レジスタをもつ。%eax, %ebx, %ecx, %edx, %esi, %edi, %ebp, %esp である。このうち %ebp と %esp は、それぞれ特別な用途に使われるので、コンパイラが生成するコードが自由に使ってよいのは、残りの 6 つである。ただしいくつかの命令は、特定のレジスタをオペランドにとる。これは 8080 からの互換性故であろうが、今回の講義ではこのような命令はとくに使わない。

ロードとストア

movl <offset>(%<src>), %<dest>

レジスタ %<src> の値に offset を足したアドレスのメモリの内容 32bit (1 word)分を、レジスタ %<dest> に読み込む。オフセット付きレジスタ間接アドレッシングによる

movl %<src>, <offset>(%<dest>)

レジスタ %<dest> の値に offset を足したアドレスに、レジスタ %<src> の内容 32bit (1 word)分を書き込む。オフセット付きレジスタ間接アドレッシングによる

movl $<integer>, %<dest>

<integer> をレジスタ %<dest> に書き込む。 load immediate (ロード即値)命令。

movl %<src>, %<dest>

レジスタ %<src> の値をレジスタ %<dest> に書き込む。

pushl %<r>

レジスタ %<r> の値をスタックに積む。つまり、レジスタ %esp の値 - 4が指すアドレスにレジスタ %<r> の値を書きこみ、%esp の値を -4 増やす。

演算命令

addl %<r>, %<s>

レジスタ %<r> とレジスタ %<s> の値を加算した結果を、レジスタ %<s> に書き込む。

subl %<r>, %<s>

レジスタ %<s> からレジスタ %<r> の値を減算した結果を、レジスタ %<s> に書き込む。引かれる数がレジスタ %<s> であることに注意。

imull %<r>, %<s>

レジスタ %<r> とレジスタ %<s> の値を乗算した結果を、レジスタ %<s> に書き込む。

cmpl %<r>, $<s>

レジスタ %<r> とレジスタ %<s> の値を比較し、結果を条件レジスタに書きこむ。 %<r> > %<s> なら less、%<r> < %<s> なら greater である。

setg %al
movzbl %al, %edx

setg %al は直前の比較演算の結果が greater ならばレジスタ %al (レジスタ %eax の下位 8 bit) を 1 を、そうでなければ 0 にする。movzbl (move zero-extension from byte to long) は 8bit レジスタ %al の値を 32bit レジスタ %edx にコピーする。上位 24bit は 0 になる。

結局、これら２つの命令の組み合わせは、直前の比較演算の結果が greater ならば、%edx を 1 に、そうでなければ 0 にする。

sete %al
movzbl %al, %edx

これら２つの命令の組み合わせは、直前の比較演算の結果が equal ならば、%edx を 1 に、そうでなければ 0 にする。

分岐命令

je <label>

直前の比較演算の結果が等しければ、ラベル<label> へ分岐、そうでなければ次の命令を実行する。Jump Equal 命令。

jl <label>

直前の比較演算の結果が less ならば、ラベル<label> へ分岐、そうでなければ次の命令を実行する。

jmp <label>

ラベル <label> へ無条件に分岐する。

call <label>

次の命令のアドレスをスタックに push し、ラベル <label> へ分岐する。

ret

次の命令のアドレスをスタックから pop し、そこへ分岐する。 Return 命令。

leave

%ebp の値を %esp にコピーし、スタックから pop した値を %ebp に保存する。

関数のコンパイル

Tiny C は大域変数がないので、コンパイラの仕事とは関数をコンパイルすることである。

関数のコンパイルを考える上で、忘れてはならない点は局所変数の実現である。Lisp のインタプリタで見たように、局所変数の値を保存するために、関数呼び出しごとに異なるメモリ領域(Lips インタプリタでは環境)を確保しなければならない。

コンパイラでは、局所変数を保存するメモリを確保するために、スタック (stack) を使う。スタックとは、最後に格納したデータが最初に取り出される性質をもったデータ構造のことである。

一般に、プログラムの実行を開始すると、OS はスタック領域という比較的大きなメモリ領域を確保する。(実際には OS は必要に応じて少しづつメモリを確保するのだが、ユーザからはそれは見えない。) そして確保したメモリ領域の末尾のアドレスを、スタック・ポインタ %esp に書き込む。

最初の関数 main() が呼ばれると、呼ばれた関数は自分が必要なだけのメモリ量を %esp から引き、%esp が指すアドレスとスタック領域の末尾の間を、局所変数の保存に使用する。スタック領域に確保したこのメモリを、関数 main() のスタック・フレーム (stack frame) または activation record と呼ぶ。

さて関数 main() の中から別な関数 foo() が呼ばれたとしよう。関数 foo() は自分の局所変数を保存するメモリを確保しなければならない。そこで foo() は、%esp から必要なメモリ量を引き、%esp が元々指していたアドレスと、%esp が新しく指しているアドレスの間をスタック・フレームとして使う。

通常、古い方の %esp の値は %ebp (base pointer) に退避しておいて、%esp と %ebp のペアでスタック・フレームを表現する。したがって関数の先頭は次のような命令になる。

関数 foo の本体
foo:
     pushl %ebp
     movl %esp, %ebp
     subl $<frame size>, %esp

関数 foo() の中で、スタック・フレームに参照するときは、

movl -4(%ebp), %eax

などとする。この命令は、末尾から2つめのスタック・フレームの要素を取り出し、レジスタ %eax に書き込む。レジスタ長は 32bits、つまり 4bytes なので、0(%ebp) が末尾の要素、 -4(%ebp) が次の要素、-8(%ebp) がその次の要素を指すことに注意。

関数 foo() の実行が終了したら、使用済みのスタック・フレームを解放しなければならない。この処理は単純で、leave 命令を実行すればよい。

関数 foo の本体
foo:
        :
     アセンブリ命令列
     leave
     ret

このようにすると、呼び出し側の main() では、元のとおり movl $8, -4(%ebp) のようにして %ebp 間接アドレッシングでスタック・フレームを参照することができる。また別の関数を呼ぶ際にも、foo() が使った領域が再利用される。

こうしてコンパイルした関数の呼出しは call 命令と ret 命令の組み合わせて実現される。

関数 foo の呼び出し側
        :
     call foo
        :

関数 foo の本体
foo:
     スタック・フレームの操作
     アセンブリ命令列
     スタック・フレームの操作
     ret

call 命令は戻り番地をスタックに push してからラベル foo へ分岐するので、ret によって、呼び出し元に戻ることができる。

なお、ここではラベル名として C 言語での関数名と同じ foo を用いた。 OS によっては、関数 foo() をコンパイルした結果得られるアセンブリ命令列には、_foo (foo の前に underscore が付加される) というラベルが付けられる。 Tiny C コンパイラを改造して他のプロセッサ用のアセンブリ命令を生成する場合には、この点を気をつけなければならない。

関数引数や返り値はどう取り扱うのだろうか。 IA32 の C 言語のコンパイル規則(calling convention という)では、関数引数はスタックに push して渡すことになっており、返り値はレジスタ %eax を使って渡すことになっている。 (返り値が整数でない場合は、スタックを使う。)

例えば a = foo(i, j) をコンパイルすると、

関数 foo の呼び出し側
        :
     pushl 変数 j
     pushl 変数 i
     call foo
     addl $8, %esp
     movl %eax, 変数 a
        :

関数 foo の本体
foo:
     アセンブリ命令列
     movl 返り値, %eax
     leave
     ret

のようになる。引数が複数ある場合には、末尾(右側)の引数から順に push する。 push すると %esp の値が増えるので、関数呼び出しから戻ったら、%esp の値を元に戻す必要がある。

呼ばれた方の関数から引数をレジスタに読みこむためには、%ebp 相対アドレッシングを使えばよい。例えば、先頭の(左側の第一)引数を読みこむためには、次のようにすればよい。

movl 8(%ebp), %eax

0(%ebp) には古い %ebp の値が、4(%ebp) には戻り番地が保存されているので、引数は 8(%ebp) が先頭となる。

関数本体のコンパイル

関数本体に直接対応するアセンブリ命令列は、関数本体を表わすリスト構造の各要素を先頭から一つづつコンパイルして得る。 Lisp インタプリタでは、リスト構造を再帰的にたどることで、関数本体の式を先頭から順に実行していった。 Tiny C コンパイラでは、同様のアルゴリズムでリスト構造をたどりながら、各文をひとつづつコンパイルしては、その結果得られた命令列を順に出力してゆく。 Lisp インタプリタとの本質的な違いは、プログラムを直接実行するのではなく、コンパイルして得られた命令列を出力する点だけである。

以下では順に、変数宣言、式文、そして if 文について、どのようにコンパイルすればよいかを説明する。

変数宣言のコンパイル

局所変数はスタック・フレームの中に保存されるのだが、具体的にどこに保存するのか決めなければならない。そこで、スタック・フレームの中を 4bytes づつに区切り、各局所変数に、末尾から順に割り当てることにする。

どの変数にスタック・フレームのどこを割り当てたかは、環境を使って記録する。Lisp インタプリタでは、環境の中に、変数名とその値のペアを記録したが、Tiny C コンパイラでは、変数名とスタック・フレーム中のその位置のペアを記録する。

(コンパイラの場合、教科書によっては環境のことを名前表 [symbol table] と呼ぶこともある。)

変数宣言をコンパイルする関数は次のようになる。

void CompileDeclaration(Environment* env, List* decl)
{
    char* name;
    char* typename;

    name = GetSymbolElement(GetSecond(decl));
    typename = GetSymbolElement(GetThird(decl));
    RecordEnvironment(env, name,
                      GetTypeIdentifier(typename, false), localVars);
    ++localVars;
}

変数 localVars は大域変数である。この変数は始め 0 に初期化され、局所変数をひとつ割り当てるごとに 1 づつ増やされる。環境に変数名を登録する関数は RecordEnvironment() である。引数は順に、登録先の環境、変数名、変数の型、それにスタック・フレーム中の位置である。変数の型を表す整数定数は、GetTypeIdentifier() で得る。この関数は型名を表す文字列と、配列型であるか否かを表す真偽値を引数にとる。今回は配列型を扱わないので、2番目の引数は false でよい。

このようにすると、局所変数 i の値を読み出してレジスタ %eax に書き込む命令は、下のようにして生成することができる。 LookupEnvironment() は、指定された変数の型を type に代入し、スタック・フレーム中での位置を返す関数である。

int index, type;
index = LookupEnvironment(env, "i", &type);
printf("movl %d(%%ebp), %%eax\n", -(index + 1) * 4);

スッタク・フレームの末尾には古い %ebp が保存されているので index に +1 していることに注意。また全体を 4 倍していることに注意されたい。これは局所変数1つあたり 4 bytes 消費するからである。例えば 3 番目の局所変数は、スタック・フレームの末尾から -4 x (3 + 1) = -16 bytes 目に保存される。

関数引数のコンパイル

局所変数と関数引数はともに変数だが、局所変数が呼ばれた側のスタック・フレーム上に保存されるのに対し、関数引数は呼んだ側のスタック・フレーム上に保存される。したがってコンパイルの方法の細部は異なるが、基本はどちらも同じである。

まず、局所変数を保存するスタック・フレーム内の位置を環境に記録したように、それぞれの関数引数についても、スタック・フレーム内のどの位置に保存されているかを、環境に記録しなければならない。 IA32 の C 言語のコンパイル規則 (calling convention)では、最後の引数から順にスタックに push される。そこで環境には、第1引数なら -1、第2引数なら -2、... と記録することにする。

void RecordArguments(Environment* env, List* args)
{
    List* a;
    char* name;
    char* typename;
    int   index;

    index = -1;
    while (args != NULL) {
        a = GetListElement(args);
        name = GetSymbolElement(GetSecond(a));
        typename = GetSymbolElement(GetThird(a));
        RecordEnvironment(env, name,
                          GetTypeIdentifier(typename, FALSE), index--);
        args = GetSecond(args);
    }
}

こうすれば、値の正負で、その変数が局所変数か関数引数かを区別することができる。

void CompileLoad(Environment* env, char* regname, char* varname)
{
    int index, type, offset;

    index = LookupEnvironment(env, varname, &type);
    if (index < 0)      /* argument */
        offset = (ARG_BASE - index - 1) * 4;
    else                /* local variable */
        offset = -(VAR_BASE + index) * 4;

    printf("movl %d(%s), %s\n", offset, BP, regname);
}

ここでマクロ ARG_BASE は 2、VAR_BASE は 1 である。

式のコンパイル

式をコンパイルする方法は様々であるが、ここでは実行効率は非常に悪いが最も簡単な方法を紹介する。基本となる考え方は、実際に演算を実行する順序にしたがって、コードを生成していく、というものである。

例えば a = a + b - 3 をコンパイルすることを考える。

この文は (= a (- (+ a b) 3)) と構文解析されるだろう。Lisp インタプリタのときと同様に、実行する順序にしたがって構文木をたどり、順にコードを生成していけばよい。

movl 変数 a, %edx
movl 変数 b, %ecx
addl %ecx, %edx        # (+ a b)
movl $3, %ecx
subl %ecx, %edx        # (- ... 3)
movl %edx, 変数 a         # (= a ...)

最初の3行が、(+ a b) のコンパイル結果で、次の2行が - 演算のコンパイル結果、最後の1行は代入文のコンパイル結果である。各部分ごとの計算結果はレジスタ %edx に書き込むようにしている。

Lips インタプリタでは、構文木をたどりながら、直接演算を実行し、結果を Eval... 関数の返り値としていた。一方、Tiny C コンパイラでは、構文木をたどりながら「演算を実行し、結果をレジスタ %edx に書き込むアセンブリ命令」を生成する。

ところがこのままでは、a - b == c + 1 のような式をコンパイルできない。c + 1 を実行している間、レジスタ %edx の中に保存された a - b の結果が壊されてしまうからだ。

そこで + のような2オペランドの演算をおこなうときには、左側の式を計算してから右側の式の計算に移る間に、レジスタ %edx の内容をメモリに退避することにする。退避先として、スタック・フレームを使う。このためスタック・フレームを大きめにとることにする。この方法にしたがうと、a = a + b - 3 は次のようになる。

movl 変数 a, %edx
movl %edx, -4(%ebp)         # 退避 %edx -> -4(%ebp)
mvol 変数 b, %edx
movl -4(%ebp), %ecx         # 復帰 %ecx <- -4(%ebp)
addl %ecx, %edx       # (+ a b)
movl %edx, -4(%ebp)         # 退避 %edx -> -4(%ebp)
movl $3, %edx
movl -4(%ebp), %ecx         # 復帰 %ecx <- -4(%ebp)
subl %edx, %ecx       # (- ... 3)
movl %ecx, %edx
movl %edx, 変数 a         # (= a ...)

このコンパイル結果は、無駄な退避が多く、あきらかに非効率だが、a - b == c + 1 のような式も正しくコンパイルできる。

movl 変数 a, %edx
movl %edx, -4(%ebp)         # 退避 %edx -> -4(%ebp)
movl 変数 b, %edx
movl -4(%ebp), %ecx          # 復帰 %ecx <- -4(%ebp)
subl %edx, %ecx        # (- a b)
movl %ecx, %edx
movl %edx, -4(%ebp)         # 退避 %edx -> -4(%ebp)
movl 変数 c, %edx
movl %edx, -8(%ebp)         # 退避 %edx -> -8(%ebp)
movl $1, %edx
movl -8(%ebp), %ecx         # 復帰 %ecx <- -8(%ebp)
addl %ecx, %edx       # (+ c 1)
movl -4(%ebp), %ecx         # 復帰 %ecx <- -4(%ebp)
cmpl %edx, %ecx        # (== (- a b) (+ c 1))
sete %al
movzbl %al, %edx

-4(%ebp) と -8(%ebp) をレジスタ %edx の退避に使っていることがわかる。ところで退避先の位置はどのように計算すればよいのだろうか？誤って同じ位置に退避してしまっては、元も子もない。

退避先は、式の入れ子の段数だけ必要で、最後に割り当てた退避先から順に不要になることを考えると、スタックを使って管理すればよいことがわかる。そこでスタック・フレームには必ず 32 words(個数はマクロ SAVEDAREA_SIZE で指定)余分に取って、ここを退避領域として使うことにする。固定長なので、式の入れ子の深さが 32 を越えるとコンパイルできなくなるが、今回は無視する。

現在の何個の値を退避しているか記録するために、大域変数 savedTemps を用意して 0 で初期化しておく。そしてレジスタの値を退避する必要がでる度に、

printf("movl %s, %d(%%ebp)\n", register_name, -(savedTemps + VAR_BASE + nLocalVars) * 4);
++savedTemps;

のよう savedTemps を 1 増やすことにする。 nLocalVars は大域変数で、コンパイル中の関数の中で使われている局所変数の個数を表す。

そして退避した値をレジスタに復帰する際に、

--savedTemps;
printf("movl %d(%%ebp), %s\n", -(savedTemps + VAR_BASE + nLocalVars) * 4, register_name);

と savedTemps を 1 減らすようにする。こうすれば退避領域を有効に活用できる。

なおこのようにスタック・フレームを設計すると、あらかじめコード生成をはじめる前に、コンパイル中の関数の中で使われている局所変数の個数を数え、nLocalVars に代入しておかなければならない。このため、用意した Tiny C のコード生成部 codegen.c の中では、コード生成をはじめる前に、構文木全体をたどって、関数の中に何個の局所変数が宣言されているか数えている。この処理をおこなうのは、ComputeStatement() など、Compute で始まる関数群である。このため、Tiny C は構文木を2回たどってコードを生成することになる。

pushl 命令を使った別な実装

上で示した式のコンパイル技法では、中間値の退避先としてスタック上にあらかじめ確保した領域を使用している。

この他の方法としては、pushl 命令を使って中間値を退避する方法が考えられる。この方法の利点は退避できる値の数に (メモリがある限り) 上限がないことである。

SPARC など、pushl 命令がないプロセッサの場合、この方法は中間値の退避に2 命令必要とするという欠点 (もっとも実行速度はそれほど変わらないだろう) がある。また pushl 命令を使う方法では、中間値を退避するたびに %esp の加算演算をともなう。 pushl 命令を使わない方法では、この加算演算は必要ないので、pushl 命令を使う方法は多少の実行速度の低下をもたらすかもしれない。

pushl 命令を使う方法には、このような欠点があるものの、IA32 の場合にはこちらの方法を使って実装してもよいだろう。

If 文のコンパイル

if 文は je 命令を使って実現される。

if (i > 0)
    i = 1;
else
    i = 2;

return i;

このプログラムは次のようにコンパイルすればよい。

    式 i > 0 のコンパイル結果
    cmpl $0, %edx
    je L1
    文 i = 1 (then 部分) のコンパイル結果
    jmp L2
L1:
    文 i = 2 (else 部分) のコンパイル結果
L2:
    return i (if の次の文) のコンパイル結果

比較演算子の計算結果もレジスタ %edx に書き込まれる。そこで %edx と 0 を比較して同じなら else に分岐し、そうでなければ then 部を実行する。C 言語では 0 が false で、0 以外が true である。

L1 や L2 はラベルである。codegen.c の中では、大域変数 labelNum を使って、L0, L1, L2, ... と毎回違ったラベルを生成し、ラベルが重ならないようにしている。

課題6

codegen.h、codegen.c は Tiny C 言語のコード生成部である。

まずコード生成部を呼び出せるよう、前回の課題で完成させた tinyc.y の一部を次のように変更せよ。

function
    : typename Identifier '(' formal.arguments ')' function.body
      {
        List* lst;
        lst = ConcatLists($1, $2);
        lst = AddList(lst, $4);
        lst = ConcatLists(lst, $6);
        CompileFunction(NULL, lst);
      }

次にコード生成部の未完成部分 CompileIfStatement(), CompileBinaryExpression(), CompileFunctionCall() を完成させよ。

そしてこれらをコンパイルし、

% yacc -dv tinyc.y
% lex tinyc.l
% gcc -o tinyc y.tab.c lex.yy.c codegen.c list.c -ll

(Makefile を使ってもよい。)

最後に、テスト・プログラム foo.c を実際にコンパイルしてみよ。

% ./tinyc < foo.c > foo.s
% gcc test.c foo.s
% ./a.out

実行結果が正しいか確認せよ。

註：出力するアセンブラ・プログラム中にコメントを含める場合は、# から行末まででがコメントである。

さらに次の項目の中から1つ選んで、よりよいコードを生成できるように codegen.c を改良せよ。

1. CompileLoadTemporary(), CompileSaveTemporary() などを改造して、-4(%ebp) や -8(%ebp) に %edx の値を退避するときには、代わりに使われていないレジスタ %esi や %edi に退避するようにする。ただしこの工夫をした場合には、他の関数を呼び出すときに、%esi と %edi も退避しなければならない(かもしれない)ことに注意せよ。

2. + や - などの二項演算子をコンパイルするとき、右側の式が式ではなく、変数か整数であるなら、右側の式をコンパイルする前に %edx を退避するのをやめる。例えば a + b - 3 をコンパイルすると

movl 変数 a, %edx
movl 変数 b, %ecx
addl %ecx, %edx       # (+ a b)
movl $3, %ecx
subl %ecx, %edx       # (- ... 3)

となるようにする。

3. 中間値を pushl 命令を使って退避するように改造する。その場合、%ebp と %esp の関係を考察せよ。

4. その他、生成されるコードのサイズを小さくしたり、速度を改良する工夫。

目次へ戻る

Email: chiba@is.tsukuba.ac.jp