1-7 コード生成２

前回は構文木から IA32 用のアセンブラ命令を出力するコード生成器を作成した。 今回はさらに配列も操作できるようにする。

配列の実装

int a[10];

すると a[i] の内容をレジスタ %edx に読み出すためのコードは、

movl 変数 i の値, %edx
shll $2, %edx                  # 左へ 2bit シフトで 4 倍
movl %ebp, %ecx
subl $44, %ecx
addl %ecx, %edx
movl 0(%edx), %edx

上のコードははじめの2行で、配列の添字 (offset) の値を4倍して、a[0]用に割り当てられたメモリのアドレスから、何bytes離れたところに a[i] 用のメモリが割り当てられているか計算する。3-5 行目は、a[i]用に割り当てられているメモリのアドレスを求めている。例では a[0] はスタック・フレームの末尾から 12 番目なので、 $ebp - 44 の値が a[0] のアドレスである。a[i] はこれに i の 4 倍を足し合わせたものである。

このコードを見ると、C言語で、配列名が a[0] へのポインタ、すなわち &a[0]、 と同一視されるのは合理的であることがわかるだろう。 3行目は、ポインタ変数 a の値を計算しているともとれる。a[i] と *(a + i) はC言語では等価であるが、*(a + i) を単純にコンパイルすると、

movl 変数 i の値, %edx
shll $2, %edx                 #  左へ 2bit シフトで 4 倍
movl 変数 a の値, %ecx        # *ここが異なる*
addl %ecx, %edx
movl 0(%edx), %edx

codegen.c の変更点

配列に関係するプログラムは、次のような構文木に変換されるのであった。

int k[3]
=> (*var* k int 3)

k[i]
=> ([] k i)

まずは ComputeDeclaration() で局所変数の個数を計算するとき、配列の場合にも正しく計算するようにする。

int ComputeDeclaration(Environment* env, List* decl)
{
    int s = GetArraySize(decl);
    if (s < 0)
        return 1; /* not an array */
    else
        return s;
}

これによって大域変数 nLocalVars の値が正しく設定されるようになる。 (codegen.c にはこの変更は既に適用ずみ。)

変数宣言は次のようにしてコンパイルする。

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

    name = GetSymbolElement(GetSecond(decl));
    typename = GetSymbolElement(GetThird(decl));
    if (配列である)
	localVars += /* 配列の大きさ */;
    else
	++localVars;

    RecordEnvironment(env, name,
                      GetTypeIdentifier(typename, /* 配列か否か */),
                      localVars - 1);
}

宣言された変数が配列の場合は、localVars の値を 1 ではなく、配列の大きさ分増やしていることに注意。 こうすることによって、配列の大きさ分の変数が、スタック・フレーム内に連続して配置されるようになる。

残るは、配列の要素を読み出す式と配列の要素への代入式のコンパイルである。

変数の値を読み出すコードを生成する関数は CompileRead() であるが、読み出す変数として配列変数が指定された場合は、どのようなコードを生成すればよいのだろうか。

void CompileRead(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;

    if (配列である)
        /* varname の変数が配列の場合の処理 */
    else
	printf(" movl %d(%s), %s\n", offset, BP, regname);
}

変数が配列でない場合には、regname が指定するレジスタに、読み出した変数の値を書きこめばよい。 一方、配列の場合には、varname が指定する配列の先頭要素のアドレスを、regname が指定するレジスタに書きこまなければならない。 C 言語では、配列名 k は、&k[0] (配列 k の先頭要素 k[0] へのポインタ) と同じ意味であることを思い出してほしい。 したがって生成するべきコードは次のようになる。

movl $<配列の先頭へのオフセット値>, %<reg>
addl %ebp, %<reg>

ここで %<reg> は regname が指定するレジスタである。 配列の先頭へのオフセット値とは、配列がスタックフレームの先頭から何 byte 目から始まるかを表す値である。 オフセット値が n ならば n 番目から始まる。

CompileRead() を上のように修正すれば、配列の要素を読み出す式のコンパイルは容易である。配列の要素の読み出し ("[]" 配列名 index式) からは、次のようなコードを生成すればよい。

「配列名」の計算 (結果は %edx に格納)
%edx を一時退避
「index式」の計算 (結果は %edx に格納)
退避しておいた %edx の値を %ecx に読み出す
shll $2, %edx
addl %edx, %ecx
movl 0(%ecx), %edx

「配列名」の計算は、配列名について CompileOperand() を呼べばよい。 オペランドが配列名であれば、CompileOperand() は CompileRead() を呼び出し、%edx に配列の先頭要素のアドレスを書き込むコードが生成される。 結局、他の2項演算子とほぼ同様の手順でコンパイルできる。

配列の要素への代入は、CompileAssign() を拡張して実装する。 配列要素への代入文は

(= ([] 配列名 index式) 式)

という形をしているので、CompileAssign() で kind の値が LIST であれば配列であることがわかる。

配列要素への代入文のコンパイル方法は、読み出しの場合とほぼ同様で、最後の movl 命令のオペランドの順序が入れ替わる程度である。

代入する値の計算 (結果は %edx に格納)
%edx を一時退避
「配列名」の計算 (結果は %edx に保存)
%edx を一時退避
「index式」の計算 (結果は %edx に保存)
退避しておいた %edx の値を %ecx に読み出す
shll $2, %edx
addl %edx, %ecx
退避しておいた代入する値を %edx に読み出す
movl %edx, 0(%ecx)

課題7

前回の課題で作成した Tiny C コンパイラを拡張して、配列が扱えるようにせよ。

またテスト・プログラム bar.c を実際にコンパイルしてみよ。

% ./tinyc < bar.c > bar.s
% gcc atest.c bar.s
% ./a.out

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

Copyright (C) 1999-2000 Shigeru Chiba