プログラミング言語処理

レジスタマシンへのコンパイラ

前回は、スタックマシンにコンパイルする方法を解説した。今回は、実際のマシン、x86(Pentium)へコンパイルすることにする。スタックマシンではコンパイラが作り安いマシンであるが、実際のマシンではレジスタがあり、これらを使ったコードを生成しなくてはならない。説明するプログラムは以下のものである。

reg_compile.h : レジスタマシンへのコンパイラのheader
reg_code.h : レジスタマシン用の中間コードの定義
compiler_main.c : コンパイラのmain
reg_compile.c : レジスタマシンへのコンパイラの関数、文の処理
reg_compile_expr.c : レジスタマシンへのコンパイラの式の処理
x86_code_gen.c : x86用のコード生成

IA32命令セット：x86(Pentium)プロセッサ

演習室に導入されているプロセッサであるx86のIA32命令セットについては機械語序論において詳しく解説した。ここではコンパイラを作成するのに必要な簡単な命令について説明する。なお、命令の記述形式にはAT&T形式とIntel形式があり、LinuxのアセンブラではAT&Tを使っているので、これで説明する。この AT&T形式では、書き換えられるdestinationを後に書く。

レジスタの構成：プロセッサには、整数レジスタが %eax,%ebx,%ecx,%edx,%edi,%esiの６個、浮動小数点レジスタが８個あるが、 tiny cでは、整数レジスタのみをつかう。このほかに、プログラムカウンタ %pc, スタックポインタ%esp, フレームポインタ%ebpがある。すべてのレジスタにe がついているのはextendの意味で、32ビットで使用するときに用いる。これは、x86が16ビットマシンであったときの名残である。即値は$nと$をつけて記述する。
オペランドの記述については、レジスタの時には%をつけて、%レジスタ名と記述する。メモリ参照は、offset(%レジスタ)と記述する。

命令セット：

命令記法説明

ロード命令 movl offset(reg),dst reg+offsetのメモリの 1word(32bit) の内容を、dstのレジスタに格納する。

ストア命令 movl src, offset(reg) reg+offsetへ、srcの1wordの内容を格納する。

即値ロード命令 movl $int, dst intの数値を、dstにセットする。

レジスタ間移動命令 movl dst,src srcのレジスタの内容をdstにコピーする。

演算命令 addl src1,dst2
subl src1,dst2
mull src1,dst2 src1,dst2のレジスタの内容を加算し、dst2にセットする。減算命令sublは、addlと同じである。乗算命令mullであるが、dst2にはeaxしか使えない。32ビットの乗算ではedxに上位32ビット、eaxには下位32ビットがセットされる。

比較演算命令 cmpl src2,src1 src1からsrc2を減算し、condition code をセットする。src2はレジスタでなくてはならない。

条件分岐命令 je label
jl label
jg label jeは、上の比較演算命令のcondition codeをみて、等しい場合にlabelに分岐する。このほかにsrc1よりもsrc2が小さい場合に分岐するjl、大きい場合に分岐するjg命令がある。

分岐命令 jmp label labelに分岐する。

push命令 pushl src srcをスタックにpushする。なお、spはスタックの先頭の要素をさしている。

関数呼び出し命令 call label 戻り番地のアドレス（次の命令のアドレス）をpushし、labelに分岐する。

leave命令 leave これは、ebpさしているアドレスにespをセットし、pop した内容をebpにセットする。

リターン命令 ret スタックからpopしたアドレスに分岐する。

命令	記法	説明
ロード命令	movl offset(reg),dst	reg+offsetのメモリの 1word(32bit) の内容を、dstのレジスタに格納する。
ストア命令	movl src, offset(reg)	reg+offsetへ、srcの1wordの内容を格納する。
即値ロード命令	movl $int, dst	intの数値を、dstにセットする。
レジスタ間移動命令	movl dst,src	srcのレジスタの内容をdstにコピーする。
演算命令	addl src1,dst2 subl src1,dst2 mull src1,dst2	src1,dst2のレジスタの内容を加算し、dst2にセットする。減算命令sublは、addlと同じである。乗算命令mullであるが、dst2にはeaxしか使えない。32ビットの乗算ではedxに上位32ビット、eaxには下位32ビットがセットされる。
比較演算命令	cmpl src2,src1	src1からsrc2を減算し、condition code をセットする。src2はレジスタでなくてはならない。
条件分岐命令	je label jl label jg label	jeは、上の比較演算命令のcondition codeをみて、等しい場合にlabelに分岐する。このほかにsrc1よりもsrc2が小さい場合に分岐するjl、大きい場合に分岐するjg命令がある。
分岐命令	jmp label	labelに分岐する。
push命令	pushl src	srcをスタックにpushする。なお、spはスタックの先頭の要素をさしている。
関数呼び出し命令	call label	戻り番地のアドレス（次の命令のアドレス）をpushし、labelに分岐する。
leave命令	leave	これは、ebpさしているアドレスにespをセットし、pop した内容をebpにセットする。
リターン命令	ret	スタックからpopしたアドレスに分岐する。

関数の呼び出し規則

スタックマシンではコンパイラに都合が良いように呼び出し規則を考えたが、実際のマシンでは呼び出し規則は決められており、命令を組み合わせて行わなくてはならない。呼び出し側では、スタック上に引数をpushし、call命令を用いる。

pushl 引数2
pushl 引数1
call foo
addl 引数個数*4, %esp

ラベルfooにjumpした時には、スタック上に戻り番地がpushされる。なお、関数呼び出しが終わって、戻ってきたときには、スタックポインタを元に戻しておかなくてはならない。従って、pushした引数個数分だけ、%espを加算して戻す。なお、関数のもどり値は、eaxに入れることになっている。

さて、関数のフレームは右の図のようになっている。関数の先頭では、まず最初に前の関数のフレームポインタをスタックにpushし、ここに現在のフレームポインタをセットする。次に、レジスタの待避領域、局所変数の領域を確保して、スタックポインタをセットする。x86では、%ebx,%ebp,%esi,%ediは、呼び出し側で保存することになっている。このコンパイラでは、レジスタとして%eax,%ebx,%ecx,%edxの4つのレジスタを使い、%esi、％ediを使わないので、まずはじめに%ebxを待避しておく。

foo:   push %ebp
       movl %esp,%ebp
       subl スタック上に確保する領域、%esp
       movl %ebx,-4(%ebp)
         ... 関数の本体　...
       movl -4(%ebp), %ebx
       leave
       ret

関数から戻る場合には、待避していた%ebxを元にもどし、leave命令で、%ebp,%espをもどして、ret命令で呼び出し側に戻る。

スタック上に確保する領域は、%ebxの待避領域、レジスタの待避領域、局所変数の領域の合計したものである。レジスタには数に限りがあるのでレジスタが足りなくなったり、関数呼び出しがある場合には、レジスタの退避領域に保存しておく。このコンパイラでは、レジスタの待避領域は4つまでとしている。そのため、例えば、１番目の局所変数は、(1+4)*4=20から、さらに-4のところ、つまり-24(%ebp)でアクセスすることになる。第一の引数は、逆にフレームポインター待避領域、戻り番地の後であるから、8(%ebp)でアクセスすることができる。

コンパイラの中間コード

一般的に、コンパイラはコンパイラが作り安いように中間コードを設計し、構文解析によって得られた構文木を中間コードに変換する。ここで最適化などの解析を行い、最終的にマシンコードに変換する。中間コードを適当に設計することによって、実際のマシンから独立したものになり、いろいろなマシンに対応できるようにもなる。

tiny Cのターゲットとして考える中間コードは、以下のコードである。以下の説明で、変数rとしているのは、いわゆるプログラム上の局所変数ではなく、レジスタが無限にあるとして考えた時の仮想的なレジスタというべきものである。コード生成のフェーズにおいて、実際のレジスタが割り当てられる。

中間コード説明

LOADI r, n 整数nを変数rにnをセット。

LOADA r, n n番目の引数を変数rにセットする。

LOADL r, n n番目の局所変数を変数rにセットする。

STOREA r, n 変数rの値をn番目の引数に格納する。

STOREL r, n 変数rの値をn番目の局所に格納する。

ADD r,r1,r2 変数r1,r2を加算し、結果をrに格納する。

SUB r,r1,r2 変数r1,r2を減算し、結果をrに格納する。

MUL r,r1,r2 変数r1,r2を乗算し、結果をrに格納する。

GT r,r1,r2 r1とr2して比較し、>ならrに1、それ以外は0をセットする。

LT r,r1,r2 r1とr2して比較し、<ならrに1、それ以外は0をセットする。

BEQ0 r, L rが 0だったら,ラベルLに分岐する。

JUMP L ラベルLにジャンプする。

CALL r, n, e 引数n個で、関数エントリeを関数呼び出しをし、結果をrにセットする。

ARG r,n rをn番目の引数とする。

RET r 変数rを返り値として、関数呼び出しから帰る。

PRINTLN r, s sのformatで、printlnを実行する。

LABEL L 　ラベルLを示す。

中間コード	説明
LOADI r, n	整数nを変数rにnをセット。
LOADA r, n	n番目の引数を変数rにセットする。
LOADL r, n	n番目の局所変数を変数rにセットする。
STOREA r, n	変数rの値をn番目の引数に格納する。
STOREL r, n	変数rの値をn番目の局所に格納する。
ADD r,r1,r2	変数r1,r2を加算し、結果をrに格納する。
SUB r,r1,r2	変数r1,r2を減算し、結果をrに格納する。
MUL r,r1,r2	変数r1,r2を乗算し、結果をrに格納する。
GT r,r1,r2	r1とr2して比較し、>ならrに1、それ以外は0をセットする。
LT r,r1,r2	r1とr2して比較し、<ならrに1、それ以外は0をセットする。
BEQ0 r, L	rが 0だったら,ラベルLに分岐する。
JUMP L	ラベルLにジャンプする。
CALL r, n, e	引数n個で、関数エントリeを関数呼び出しをし、結果をrにセットする。
ARG r,n	rをn番目の引数とする。
RET r	変数rを返り値として、関数呼び出しから帰る。
PRINTLN r, s	sのformatで、printlnを実行する。
LABEL L	ラベルLを示す。

なお、このように

op dst,src1,src2

というような形式のコードを、四つ組と呼ばれる。このほかに、命令に近い形に表現する RTL(Register Transfer Language)をいう形式もある。

中間コードは、reg_code.hに定義してある。スタックマシンの場合と同じように、関数ごとにコンパイルされるが、中間コードは一時的な領域に保存しておき、関数のコンパイルが終るごとに実際のx86のコードに変換して出力される。中間コードには以下のルーチンを使う。

x86_code_gen.c
struct _code { int opcode; int operand1,operand2,operand3; char s_operand; } Codes[MAX_CODE]; int n_code; void initGenCode() { n_code = 0; } void genCode1(int opcode,int operand1) { Codes[n_code].operand1 = operand1; Codes[n_code++].opcode = opcode; } void genCode2(int opcode,int operand1, int operand2) { Codes[n_code].operand1 = operand1; Codes[n_code].operand2 = operand2; Codes[n_code++].opcode = opcode; } void genCode3(int opcode,int operand1, int operand2, int operand3) { Codes[n_code].operand1 = operand1; Codes[n_code].operand2 = operand2; Codes[n_code].operand3 = operand3; Codes[n_code++].opcode = opcode; } void genCodeS(int opcode,int operand1, int operand2, char s) { Codes[n_code].operand1 = operand1; Codes[n_code].operand2 = operand2; Codes[n_code].s_operand = s; Codes[n_code++].opcode = opcode; }

x86_code_gen.c

struct _code {
    int opcode;
    int operand1,operand2,operand3;
    char *s_operand;
} Codes[MAX_CODE];

int n_code;

void initGenCode()
{
    n_code = 0;
}

void genCode1(int opcode,int operand1)
{
    Codes[n_code].operand1 = operand1;
    Codes[n_code++].opcode = opcode;
}

void genCode2(int opcode,int operand1, int operand2)
{
    Codes[n_code].operand1 = operand1;
    Codes[n_code].operand2 = operand2;
    Codes[n_code++].opcode = opcode;
}

void genCode3(int opcode,int operand1, int operand2, int operand3)
{
    Codes[n_code].operand1 = operand1;
    Codes[n_code].operand2 = operand2;
    Codes[n_code].operand3 = operand3;
    Codes[n_code++].opcode = opcode;
}

void genCodeS(int opcode,int operand1, int operand2, char *s)
{
    Codes[n_code].operand1 = operand1;
    Codes[n_code].operand2 = operand2;
    Codes[n_code].s_operand = s;
    Codes[n_code++].opcode = opcode;
}

スタックマシンのコンパイラと同様に、関数のコードを生成する前に、 initGenCodeを呼び出し、領域をクリアする。それぞれの中間コードは、 genCode1, genCode2, genCode3,genCodeSを使って生成する。スタックマシンとは異なり、オペランドは最大3つまで持つことに注意。

式のコンパイル：中間コードへの変換

さて、レジスタマシンへのコンパイラで大きくことなるのは、式の計算をスタックではなくて、レジスタを使っておこなわなくてはならないところである。式のコンパイルから考えてみることにしよう。

式のコンパイルは、compileExprで行う。この関数では、呼び出す側でターゲットとなる一時的な変数を作って、これを引数にして呼び出している。 compileExprは、引数のASTの式に対して、「コードを実行すると与えtargetに結果を格納する」コードを生成する。文として実行され、値を必要としない場合にはtargetを-1としている。一時的な変数を作るのは、大域変数tmp_counterを使って新しい変数の番号を生成する。

reg_compile_expr.c
void compileExpr(int target, AST p) { int r1,r2; if(p == NULL) return; switch(p->op){ case NUM: genCode2(LOADI,target,p->val); return; case SYM: compileLoadVar(target,getSymbol(p)); return; case EQ_OP: if(target != -1) error("assign has no value"); r1 = tmp_counter++; compileExpr(r1,p->right); compileStoreVar(getSymbol(p->left),r1); return; case PLUS_OP: r1 = tmp_counter++; r2 = tmp_counter++; compileExpr(r1,p->left); compileExpr(r2,p->right); genCode3(ADD,target,r1,r2); return; case MINUS_OP: r1 = tmp_counter++; r2 = tmp_counter++; compileExpr(r1,p->left); compileExpr(r2,p->right); genCode3(SUB,target,r1,r2); return; case MUL_OP: r1 = tmp_counter++; r2 = tmp_counter++; compileExpr(r1,p->left); compileExpr(r2,p->right); genCode3(MUL,target,r1,r2); return; case LT_OP: r1 = tmp_counter++; r2 = tmp_counter++; compileExpr(r1,p->left); compileExpr(r2,p->right); genCode3(LT,target,r1,r2); return; case GT_OP: r1 = tmp_counter++; r2 = tmp_counter++; compileExpr(r1,p->left); compileExpr(r2,p->right); genCode3(GT,target,r1,r2); return; case CALL_OP: compileCallFunc(target,getSymbol(p->left),p->right); return; case PRINTLN_OP: if(target != -1) error("println has no value"); printFunc(p->left); return; / 省略 */ default: error("unknown operater/statement"); } }

reg_compile_expr.c

void compileExpr(int target, AST *p)
{
    int r1,r2;
    
    if(p == NULL) return;

    switch(p->op){
    case NUM:
        genCode2(LOADI,target,p->val);
	return;
    case SYM:
	compileLoadVar(target,getSymbol(p));
	return;
    case EQ_OP:
	if(target != -1) error("assign has no value");
	r1 = tmp_counter++; 
	compileExpr(r1,p->right);
	compileStoreVar(getSymbol(p->left),r1);
	return;
    case PLUS_OP:
	r1 = tmp_counter++; r2 = tmp_counter++;
	compileExpr(r1,p->left);
	compileExpr(r2,p->right);
	genCode3(ADD,target,r1,r2);
	return;
    case MINUS_OP:
	r1 = tmp_counter++; r2 = tmp_counter++;
	compileExpr(r1,p->left);
	compileExpr(r2,p->right);
	genCode3(SUB,target,r1,r2);
	return;
    case MUL_OP:
	r1 = tmp_counter++; r2 = tmp_counter++;
	compileExpr(r1,p->left);
	compileExpr(r2,p->right);
	genCode3(MUL,target,r1,r2);
	return;
    case LT_OP:
	r1 = tmp_counter++; r2 = tmp_counter++;
	compileExpr(r1,p->left);
	compileExpr(r2,p->right);
	genCode3(LT,target,r1,r2);
	return;
    case GT_OP:
	r1 = tmp_counter++; r2 = tmp_counter++;
	compileExpr(r1,p->left);
	compileExpr(r2,p->right);
	genCode3(GT,target,r1,r2);
	return;
    case CALL_OP:
	compileCallFunc(target,getSymbol(p->left),p->right);
	return;

    case PRINTLN_OP:
	if(target != -1) error("println has no value");
	printFunc(p->left);
	return;

	/* 省略 */

    default:
	error("unknown operater/statement");
    }
}

式が数字であれば、その数字をターゲットにセットするLOADIコードを生成する。
式は変数であれば、compileLoadVarを呼び出して、その値をロードするコードを生成する。
式が代入であれば、まず、新しい変数を作り、それに演算結果をいれるコードを生成する。そのあとで、compileStoreVarを呼び出して、その変数の値を変数に格納するコードを出す。
式が演算であれば、左辺と右辺に対する変数を作って、それをターゲットにコンパイルし、ターゲットに演算結果をいれるコードを生成する。

ここでは、コンパイラが作った一時的な変数の結果は高々１回しか使わないようにコードを生成している。その理由は、後で説明する実際のレジスタマシンのコードの生成を簡単にするためである。なお、この理由から代入文自体の値は使われないように制限している。例えば、文として現れる

x = z + 1;

は大丈夫であるが、

x = (y=1)+1;

のように式のなかで、y=1は使えない。(代入式は代入文として扱ってもいいが、そうするとfor文の中にはつかえなくなってしまう。)

変数の割り当ての情報を示す環境は、スタックマシンと同じである。

reg_compile.h
#define VAR_ARG 0 #define VAR_LOCAL 1 typedef struct env { Symbol *var; int var_kind; int pos; } Environment;

スタックマシンと同様に、var_kindにはパラメータ変数であるか(VAR_ARG)、局所変数であるか(VAR_LOCAL)を示すvar_kindと関数フレーム上の割り当て位置を示すposがある。

compileLoadVarとcompileStoreVarはこの環境を調べて、適当なロードとストアのコードを生成する。

reg_compile.c
int envp = 0; Environment Env[MAX_ENV]; void compileStoreVar(Symbol var,int r) { int i; for(i = envp-1; i >= 0; i--){ if(Env[i].var == var){ switch(Env[i].var_kind){ case VAR_ARG: genCode2(STOREA,r,Env[i].pos); return; case VAR_LOCAL: genCode2(STOREL,r,Env[i].pos); return; } } } error("undefined variable\n"); } void compileLoadVar(int target, Symbol var) { int i; for(i = envp-1; i >= 0; i--){ if(Env[i].var == var){ switch(Env[i].var_kind){ case VAR_ARG: genCode2(LOADA,target,Env[i].pos); return; case VAR_LOCAL: genCode2(LOADL,target,Env[i].pos); return; } } } error("undefined variable\n"); }

reg_compile.c

int envp = 0;
Environment Env[MAX_ENV];

void compileStoreVar(Symbol *var,int r)
{
    int i;
    for(i = envp-1; i >= 0; i--){
	if(Env[i].var == var){
	    switch(Env[i].var_kind){
	    case VAR_ARG:
		genCode2(STOREA,r,Env[i].pos);
		return;
	    case VAR_LOCAL:
		genCode2(STOREL,r,Env[i].pos);
		return;
	    }
	}
    }
    error("undefined variable\n");
}

void compileLoadVar(int target, Symbol *var)
{
    int i;
    for(i = envp-1; i >= 0; i--){
	if(Env[i].var == var){
	    switch(Env[i].var_kind){
	    case VAR_ARG:
		genCode2(LOADA,target,Env[i].pos);
		return;
	    case VAR_LOCAL:
		genCode2(LOADL,target,Env[i].pos);
		return;
	    }
	}
    }
    error("undefined variable\n");
}

compileStoreVarは、レジスタrを変数にストアするコード、compileLoadVarは、変数をtargetにロードするコードを生成する。

関数のコンパイル

コンパイラのmainプログラムは、スタックマシンのコンパイラとまったく同じである。

compiler_main.c
main() { yyparse(); return 0; }

parserのcparse.yや字句解析のlex.cはインタプリターと同一のものを使い、yyparseからは関数定義が入力されるごとに、defineFunctionや declareVariableが呼び出される。

defineFuctionも、スタックマシンのものとまったく同じである。

reg_compile.c
void defineFunction(Symbol fsym,AST params,AST body) { int param_pos; initGenCode(); envp = 0; param_pos = 0; local_var_pos = 0; for( ; params != NULL; params = getNext(params)){ Env[envp].var = getSymbol(getFirst(params)); Env[envp].var_kind = VAR_ARG; Env[envp].pos = param_pos++; envp++; } compileStatement(body); genFuncCode(fsym->name,local_var_pos,param_pos); envp = 0; / reset */ }

reg_compile.c

void defineFunction(Symbol *fsym,AST *params,AST *body)
{
    int param_pos;

    initGenCode();
    envp = 0;
    param_pos = 0;
    local_var_pos = 0;
    for( ; params != NULL; params = getNext(params)){
	Env[envp].var = getSymbol(getFirst(params));
	Env[envp].var_kind = VAR_ARG;
	Env[envp].pos = param_pos++;
	envp++;
    }
    compileStatement(body);
    genFuncCode(fsym->name,local_var_pos,param_pos);
    envp = 0;  /* reset */
}

パラメータの変数を環境に登録し、本体をcompileStatementでコンパイルする。

文のコンパイル

文のコンパイルは、compileStatementで行う。compileStatementもスタックマシンのものとほとんど同じである。

reg_compile.c
void compileStatement(AST *p) { if(p == NULL) return; switch(p->op){ case BLOCK_STATEMENT: compileBlock(p->left,p->right); break; case RETURN_STATEMENT: compileReturn(p->left); break; case IF_STATEMENT: compileIf(p->left,getNth(p->right,0),getNth(p->right,1)); break; case WHILE_STATEMENT: compileWhile(p->left,p->right); break; case FOR_STATEMENT: compileFor(getNth(p->left,0),getNth(p->left,1),getNth(p->left,2), p->right); break; default: compileExpr(-1,p); } }

reg_compile.c

void compileStatement(AST *p)
{
    if(p == NULL) return;
    switch(p->op){
    case BLOCK_STATEMENT:
	compileBlock(p->left,p->right);
	break;
    case RETURN_STATEMENT:
	compileReturn(p->left);
	break;
    case IF_STATEMENT:
	compileIf(p->left,getNth(p->right,0),getNth(p->right,1));
	break;
    case WHILE_STATEMENT:
	compileWhile(p->left,p->right);
	break;
    case FOR_STATEMENT:
	compileFor(getNth(p->left,0),getNth(p->left,1),getNth(p->left,2),
		   p->right);
	break;
    default:
	compileExpr(-1,p);
    }
}

但し、最後の式を文としてコンパイルする時は、ターゲットを-1にして compileExprを呼び出し、コードコード生成を行う。

それぞれの文の処理は、スタックマシンのものと非常によく似ている。

reg_compile.c
void compileBlock(AST local_vars,AST statements) { int envp_save; envp_save = envp; for( ; local_vars != NULL; local_vars = getNext(local_vars)){ Env[envp].var = getSymbol(getFirst(local_vars)); Env[envp].var_kind = VAR_LOCAL; Env[envp].pos = local_var_pos++; envp++; } for( ; statements != NULL; statements = getNext(statements)) compileStatement(getFirst(statements)); envp = envp_save; } void compileReturn(AST expr) { int r; if(expr != NULL){ r = tmp_counter++; compileExpr(r,expr); } else r = -1; genCode1(RET,r); } void compileCallFunc(int target, Symbol f,AST args) { int narg; narg = compileArgs(args); genCodeS(CALL,target,narg,f->name); } int compileArgs(AST args) { int r,n; if(args != NULL){ n = compileArgs(getNext(args)); r = tmp_counter++; compileExpr(r,getFirst(args)); genCode1(ARG,r); } else return 0; return n+1; } void compileIf(AST cond, AST then_part, AST *else_part) { int l1,l2; int r; r = tmp_counter++; compileExpr(r,cond); l1 = label_counter++; genCode2(BEQ0,r,l1); compileStatement(then_part); if(else_part != NULL){ l2 = label_counter++; genCode1(JUMP,l2); genCode1(LABEL,l1); compileStatement(else_part); genCode1(LABEL,l2); } else { genCode1(LABEL,l1); } }

reg_compile.c

void compileBlock(AST *local_vars,AST *statements)
{
    int envp_save;
    envp_save = envp;
    for(  ; local_vars != NULL; local_vars = getNext(local_vars)){
	Env[envp].var = getSymbol(getFirst(local_vars));
	Env[envp].var_kind = VAR_LOCAL;
	Env[envp].pos = local_var_pos++;
	envp++;
    }
    for( ; statements != NULL; statements = getNext(statements))
	compileStatement(getFirst(statements));
    envp = envp_save;
}

void compileReturn(AST *expr)
{
    int r;
    if(expr != NULL){
	r = tmp_counter++;
	compileExpr(r,expr);
    } else r = -1;
    genCode1(RET,r);
}

void compileCallFunc(int target, Symbol *f,AST *args)
{
    int narg;
    narg = compileArgs(args);
    genCodeS(CALL,target,narg,f->name);
}

int compileArgs(AST *args)
{
    int r,n;

    if(args != NULL){
	n = compileArgs(getNext(args));
	r = tmp_counter++;
	compileExpr(r,getFirst(args));
	genCode1(ARG,r);
    } else return 0;
    return n+1;
}

void compileIf(AST *cond, AST *then_part, AST *else_part)
{
    int l1,l2;
    int r;

    r = tmp_counter++;
    compileExpr(r,cond);
    l1 = label_counter++;
    genCode2(BEQ0,r,l1);
    compileStatement(then_part);
    if(else_part != NULL){
	l2 = label_counter++;
	genCode1(JUMP,l2);
	genCode1(LABEL,l1);
	compileStatement(else_part);
	genCode1(LABEL,l2);
    } else {
	genCode1(LABEL,l1);
    }
}

block文をコンパイルするcompileBlockは、スタックマシンのものと同じでよい。
compileReturnでは、一時レジスタを生成し、それに式が計算されるコードを生成した後、RETのコードを生成する。もし、式がない場合にはコードに対するレジスタを-1にしておく。
関数呼び出しの中間コードはCALLである。中間コードのオペランドは、呼び出した結果をいれるtagetと引数の個数と関数名である。compileCallFunc は、compileArgを使って引数の値を計算するコードを生成し、そのあとでCALL を生成している。
compileArgでは、それぞれの引数について、一時変数を作り、その変数に計算結果が引数が入るコードを生成し、中間コード ARG rを生成する。同時に、引数の個数を計算していることに注意。
If文のコンパイルを行うcompileIfでは、条件式のコンパイルを compileExprで行い、BEQ0のコードを生成している以外は、スタックマシンのものと同じである。

なお、while文についてはプログラムのソースコードを参照のこと。 for文は自分でつくってみること。

中間コードからマシンコードの生成

実際のコンパイラでは、この中間コードについて様々な最適化をし、最後にこれをマシンコード（アセンブリ言語）を出力する。マシンコードに変換するために最低限必要なのは、コンパイラで作り出した一時的な変数（仮想レジスタ）に実際のレジスタを割り当てる作業（register allocation）である。

x86では汎用レジスタとして、6個のレジスタがあるが、このコンパイラでは %eax,%ebx,%ecx,%edxの4つのレジスタを使うことにする。割り当ての過程で、この実際のレジスタが足りなくなったら、適宜、実際のレジスタ上にある仮想レジスタの値をメモリに退避して使い回さなくてはならない。このための領域として４レジスタ分の領域を確保する。実際は複雑な式を実行するには４つ以上の退避領域が必要になることがあるが、簡単にするために４つに限定することにする。(４つ以上の退避領域が必要の場合はコンパイルをあきらめる)

それぞれに、0から3の番号を割り当て、

tmpRegState : 実際のレジスタにどの仮想レジスタ（変数）が割り当てられているかを示す配列
tmpRegSave : 退避領域にどの仮想レジスタの値が退避されているかを示す配列

の２つの配列を準備する。

x86_code_gen.c
#define N_REG 4 /* 一時的な変数に割り当てるレジスタ数 / #define N_SAVE 4 / 一時的な変数の退避領域の数 / #define REG_AX 0 #define REG_BX 1 #define REG_CX 2 #define REG_DX 3 char tmpRegName[N_REG] = { "%eax", "%ebx", "%ecx", "%edx" }; int tmpRegState[N_REG]; /* 実レジスタに割り当てられている仮想レジスタ / int tmpRegSave[N_SAVE]; / 退避領域にある仮想レジスタ */

x86_code_gen.c

#define N_REG 4   /* 一時的な変数に割り当てるレジスタ数 */
#define N_SAVE 4  /* 一時的な変数の退避領域の数 */

#define REG_AX 0
#define REG_BX 1
#define REG_CX 2
#define REG_DX 3

char *tmpRegName[N_REG] = { "%eax", "%ebx", "%ecx", "%edx" };
int tmpRegState[N_REG];  /* 実レジスタに割り当てられている仮想レジスタ */
int tmpRegSave[N_SAVE];  /* 退避領域にある仮想レジスタ */

tmpRegNameは、番号からレジスタ名を求める時に使う配列である。例えば、reg番目のレジスタ（つまり、%eaxであれば、0番目）に仮想レジスタ rが割り当てられているときには、tmpRegState[reg]には、rをいれる。使われていないときには、-1をいれておく。 tmpRegSaveも同様に、i番目の待避領域に仮想レジスタrの値がある場合には tmpRegSave[i]がrとなる。

退避領域と局所変数のbpからのオフセットを計算するマクロが、TMP_OFFと LOCAL_VAR_OFFである。bpから引数のオフセットを計算する関数が、ARG_OFFである。

x86_code_gen.c
#define TMP_OFF(i) -((i+1)+1)4 #define LOCAL_VAR_OFF(i) -(N_SAVE+1+(i+1))4 #define ARG_OFF(i) ((i)+2)*4

退避領域は、常に4ワード分確保していることに注意。

まず、これらの情報を初期化する関数が、initTempRegである。

x86_code_gen.c
void initTmpReg() { int i; for(i = 0; i < N_REG; i++) tmpRegState[i] = -1; for(i = 0; i < N_SAVE; i++) tmpRegSave[i] = -1; }

全ての値を、-1にする。-1は使われていないことを示す。

次に、実際のレジスタを割り当てるのに使われていない実レジスタを探さなくてはならない。getRegは、仮想レジスタrに空いている実際のレジスタを割り当て、その実レジスタの値を返す。

x86_code_gen.c
int getReg(int r) { int i; for(i = 0; i < N_REG; i++){ if(tmpRegState[i] < 0){ tmpRegState[i] = r; return i; } } error("no temp reg"); }

assignRegは、仮想レジスタrを実際のレジスタregに強制的に割り当てる関数である。もしも、現在仮想レジスタに実際のレジスタが割り当てられていればなにもしないが、それ以外の場合は割り当てるレジスタをsaveRegで空いていることを確認してから、割り当てる。この関数は、命令が特定のレジスタが必要な場合に用いる。

x86_code_gen.c
/* assign r to reg */ void assignReg(int r, int reg) { if(tmpRegState[reg] == r) return; saveReg(reg); tmpRegState[reg] = r; }

useRegは、仮想レジスタrがどの実際のレジスタに割りあてられているのかを調べる。もしも、仮想レジスタrが退避領域にある場合には、その値を実レジスタにロードして、その値を返す。

x86_code_gen.c
int useReg(int r) { int i,rr; for(i = 0; i < N_REG; i++){ if(tmpRegState[i] == r) return i; } /* not found in register, then restore from save area. / for(i = 0; i < N_SAVE; i++){ if(tmpRegSave[i] == r){ rr = getReg(r); tmpRegSave[i] = -1; / load into regsiter */ printf("\tmovl\t%d(%%ebp),%s\n",TMP_OFF(i),tmpRegName[rr]); return rr; } } error("reg is not found"); }

x86_code_gen.c

int useReg(int r)
{
    int i,rr;

    for(i = 0; i < N_REG; i++){
	if(tmpRegState[i] == r) return i;
    }
    /* not found in register, then restore from save area. */
    for(i = 0; i < N_SAVE; i++){
	if(tmpRegSave[i] == r){
	    rr = getReg(r);
	    tmpRegSave[i] = -1;
	    /* load into regsiter */
	    printf("\tmovl\t%d(%%ebp),%s\n",TMP_OFF(i),tmpRegName[rr]);
	    return rr;
	}
    }
    error("reg is not found");
}

退避されている値を実レジスタにロードする場合には、

movl TMP_OFF(i)(%bp),レジスタ

が、出力される。

saveRegは、実際のレジスタの値を退避するルーチンである。もしも、なにもレジスタがロードされていない(tmpRegState[reg]が-1)の場合は何もしない。それ以外の場合には、使われていない退避領域を探してそこにセーブするコードをだす。

x86_code_gen.c
void saveReg(int reg) { int i; if(tmpRegState[reg] < 0) return; for(i = 0; i < N_SAVE; i++){ if(tmpRegSave[i] < 0){ printf("\tmovl\t%s,%d(%%ebp)\n",tmpRegName[reg],TMP_OFF(reg)); tmpRegSave[i] = tmpRegState[reg]; tmpRegState[reg] = -1; return; } } error("no temp save"); } void saveAllRegs() { int i; for(i = 0; i < N_REG; i++) saveReg(i); } void freeReg(int reg) { tmpRegState[reg] = -1; }

x86_code_gen.c

void saveReg(int reg)
{
    int i;

    if(tmpRegState[reg] < 0) return;
    for(i = 0; i < N_SAVE; i++){
	if(tmpRegSave[i] < 0){
	    printf("\tmovl\t%s,%d(%%ebp)\n",tmpRegName[reg],TMP_OFF(reg));
	    tmpRegSave[i] = tmpRegState[reg];
	    tmpRegState[reg] = -1;
	    return;
	}
    }
    error("no temp save");
}

void saveAllRegs()
{
    int i;
    for(i = 0; i < N_REG; i++) saveReg(i);
}

void freeReg(int reg)
{
    tmpRegState[reg] = -1;
}

saveAllRegは、全てのレジスタの値を退避する。これは関数呼び出しの場合に用いる。freeRegは、実レジスタregを開放する。

以上の関数を使ってたとえば、ADD　r, r1, r2の中間コードについては以下のようにしてコードを生成する。

r1,r2について、useRegで現在割り当てられているレジスタを求める。これをR1,R2とする。
R1、R2をfreeRegで開放する。
assignRegで、ｒに、R1を割り当てる。
addl R1,R2のコードを生成する。

なお、中間コードの生成では変数は一回しか使われないようにしている。従って、使ってしまえば、開放してよい。しかし、実際のコンパイラではこのような条件は必ずしも成立しないことがあるので、レジスタの開放はこの命令以降、レジスタが使われないことを確かめなくてはならない。

genFuncCodeでは、生成された命令を上の手順を使って、実際の命令を生成している。まず、関数のはじめの部分を生成して、本体のコードを生成し、最後のreturnの部分のコードを生成する。あらかじめ、ret命令が埋め込まれるようにして、RETではここにJUMPするようにするため、ret_labにラベルを作っておく。

x86_code_gen.c
void genFuncCode(char entry_name, int n_local) { int i; int opd1,opd2,opd3; int r,r1,r2; char opds; int ret_lab,l1,l2; int frame_size; /* function header / puts("\t.text"); / .text / puts("\t.align\t4"); / .align 4 / printf("\t.globl\t%s\n", entry_name); / .globl / printf("\t.type\t%s,@function\n", entry_name);/ .type ,@function / printf("%s:\n", entry_name); / : / printf("\tpushl\t%%ebp\n"); printf("\tmovl\t%%esp,%%ebp\n"); frame_size = -LOCAL_VAR_OFF(n_local); ret_lab = label_counter++; printf("\tsubl\t$%d,%%esp\n",frame_size); printf("\tmovl\t%%ebx,-4(%%ebp)\n"); initTmpReg(); for(i = 0; i < n_code; i++){ /debug// printf("%s %d %d %d\n",code_name(Codes[i].opcode), Codes[i].operand1,Codes[i].operand2,Codes[i].operand3); / opd1 = Codes[i].operand1; opd2 = Codes[i].operand2; opd3 = Codes[i].operand3; opds = Codes[i].s_operand; switch(Codes[i].opcode){ case LOADI: if(opd1 < 0) break; r = getReg(opd1); printf("\tmovl\t$%d,%s\n",opd2,tmpRegName[r]); break; case LOADA: / load arg / if(opd1 < 0) break; r = getReg(opd1); printf("\tmovl\t%d(%%ebp),%s\n",ARG_OFF(opd2),tmpRegName[r]); break; case LOADL: / load local / if(opd1 < 0) break; r = getReg(opd1); printf("\tmovl\t%d(%%ebp),%s\n",LOCAL_VAR_OFF(opd2),tmpRegName[r]); break; case STOREA: / store arg / r = useReg(opd1); freeReg(r); printf("\tmovl\t%s,%d(%%ebp)\n",tmpRegName[r],ARG_OFF(opd2)); break; case STOREL: / store local */ r = useReg(opd1); freeReg(r); printf("\tmovl\t%s,%d(%%ebp)\n",tmpRegName[r],LOCAL_VAR_OFF(opd2)); break;

x86_code_gen.c

void genFuncCode(char *entry_name, int n_local)
{
    int i;
    int opd1,opd2,opd3;
    int r,r1,r2;
    char *opds;
    int ret_lab,l1,l2;
    int frame_size;

    /* function header */
    puts("\t.text");       	             /* .text         */
    puts("\t.align\t4");        	     /* .align 4      */
    printf("\t.globl\t%s\n", entry_name);    /* .globl  */
    printf("\t.type\t%s,@function\n", entry_name);/* .type ,@function */
    printf("%s:\n", entry_name);             /* :              */
    printf("\tpushl\t%%ebp\n");
    printf("\tmovl\t%%esp,%%ebp\n");

    frame_size = -LOCAL_VAR_OFF(n_local);
    ret_lab = label_counter++;

    printf("\tsubl\t$%d,%%esp\n",frame_size);
    printf("\tmovl\t%%ebx,-4(%%ebp)\n");
    
    initTmpReg();
    
    for(i = 0; i < n_code; i++){
	/*debug*//* printf("%s %d %d %d\n",code_name(Codes[i].opcode),
	       Codes[i].operand1,Codes[i].operand2,Codes[i].operand3); */
	opd1 = Codes[i].operand1;
	opd2 = Codes[i].operand2;
	opd3 = Codes[i].operand3;
	opds = Codes[i].s_operand;

	switch(Codes[i].opcode){
	case LOADI:
	    if(opd1 < 0) break;
	    r = getReg(opd1);
	    printf("\tmovl\t$%d,%s\n",opd2,tmpRegName[r]);
	    break;
	case LOADA:	/* load arg */
	    if(opd1 < 0) break;
	    r = getReg(opd1);
	    printf("\tmovl\t%d(%%ebp),%s\n",ARG_OFF(opd2),tmpRegName[r]);
	    break;
	case LOADL:	/* load local */
	    if(opd1 < 0) break;
	    r = getReg(opd1);
	    printf("\tmovl\t%d(%%ebp),%s\n",LOCAL_VAR_OFF(opd2),tmpRegName[r]);
	    break;
	case STOREA:	/* store arg */
	    r = useReg(opd1); freeReg(r);
	    printf("\tmovl\t%s,%d(%%ebp)\n",tmpRegName[r],ARG_OFF(opd2));
	    break;
	case STOREL:	/* store local */
	    r = useReg(opd1); freeReg(r);
	    printf("\tmovl\t%s,%d(%%ebp)\n",tmpRegName[r],LOCAL_VAR_OFF(opd2));
	    break;

関数の最初は、以下のコードである。

     .text
     .align 4
     .globl 関数名
     .type 関数名、@function
関数名:
     pushl %ebp
     movl  %esp,%ebp
     subl  フレームのサイズ、%esp
     movl  %ebx,-4(%ebp)

関数の最初では、%ebp,%espのセットの他、callee saveのレジスタである%ebx を退避しておく。本当は、%ebxが使われない限り、セーブする必要はないが、簡単のために常にセーブすることにする。
LOADIに対しては、
movl $n,reg
を生成する。
関数の最初のコードを生成した後は、格納されている中間コードを取り出し、実際の命令コードを生成する。
引数をロード、ストアするLOADA,STOREAについては、ARG_OFFマクロを使って、オフセットを計算してコードを生成する。
ローカル変数をロード、ストアするLOADL,STORELについては、 LOCAL_VAR_OFFマクロを使って、オフセットを計算してコードを生成する。
既に実際にロードされている仮想レジスタについては、useRegを使って探し、新たに確保するレジスタについてはgetRegで割り当てを行っている。１度使ったレジスタについてはfreeRegで解放していることに注意。

x86_code_gen.c
case BEQ0: /* conditional branch */ r = useReg(opd1); freeReg(r); printf("\tcmpl\t$0,%s\n",tmpRegName[r]); printf("\tje\t.L%d\n",opd2); break; case LABEL: printf(".L%d:\n",Codes[i].operand1); break; case JUMP: printf("\tjmp\t.L%d\n",Codes[i].operand1); break;

x86_code_gen.c

	case BEQ0:	/* conditional branch */
	    r = useReg(opd1); freeReg(r);
	    printf("\tcmpl\t$0,%s\n",tmpRegName[r]);
	    printf("\tje\t.L%d\n",opd2);
	    break;
	case LABEL:
	    printf(".L%d:\n",Codes[i].operand1);
	    break;
	case JUMP:
	    printf("\tjmp\t.L%d\n",Codes[i].operand1);
	    break;

条件分岐命令では、cmpl命令で0との比較をし、je命令で分岐している。 GT,LTのコードについては、分岐命令を使って、dstに0か１をセットする命令列を生成している。x86では直接0,1をセットするsetcc命令があるが、ここではあえて使わなかった。
ラベル、JUMP命令については、上の通り。

x86_code_gen.c
case CALL: saveAllRegs(); printf("\tcall\t%s\n",opds); if(opd1 < 0) break; assignReg(opd1,REG_AX); printf("\tadd $%d,%%esp\n",opd2*4); break; case ARG: r = useReg(opd1); freeReg(r); printf("\tpushl %s\n",tmpRegName[r]); break; case RET: r = useReg(opd1); freeReg(r); if(r != REG_AX) printf("\tmovl\t%s,%%eax\n",tmpRegName[r]); printf("\tjmp .L%d\n",ret_lab); break;

x86_code_gen.c

	case CALL:
	    saveAllRegs();
	    printf("\tcall\t%s\n",opds);
	    if(opd1 < 0) break;
	    assignReg(opd1,REG_AX);
	    printf("\tadd $%d,%%esp\n",opd2*4);
	    break;
	case ARG:
	    r = useReg(opd1); freeReg(r);
	    printf("\tpushl %s\n",tmpRegName[r]);
	    break;
	case RET:
	    r = useReg(opd1); freeReg(r);
	    if(r != REG_AX) printf("\tmovl\t%s,%%eax\n",tmpRegName[r]);
	    printf("\tjmp .L%d\n",ret_lab);
	    break;

ARGコードは、push命令で生成される。使った後はfreeしておく。
CALLコードでは、saveAllRegsで現在使われているレジスタを退避させなくてはならないことに注意。call命令を使って生成した後は、addlを使って、pushした分、スタックポインタを元に戻す。返り値は、%eaxに入っているはずなので、ターゲットがある場合には、強制的に、assignRegを使ってREG_AXに割り当てを行う。
RETに関しては、assignRegをrを%eaxにセットして、プログラムの最後に生成されているreturnのところにjumpするようにしている。

x86_code_gen.c
case ADD: r1 = useReg(opd2); r2 = useReg(opd3); freeReg(r1); freeReg(r2); if(opd1 < 0) break; assignReg(opd1,r1); printf("\taddl\t%s,%s\n",tmpRegName[r2],tmpRegName[r1]); break; case SUB: r1 = useReg(opd2); r2 = useReg(opd3); freeReg(r1); freeReg(r2); if(opd1 < 0) break; assignReg(opd1,r1); printf("\tsubl\t%s,%s\n",tmpRegName[r2],tmpRegName[r1]); break; case MUL: r1 = useReg(opd2); r2 = useReg(opd3); freeReg(r1); freeReg(r2); if(opd1 < 0) break; assignReg(opd1,REG_AX); saveReg(REG_DX); if(r1 != REG_AX) printf("\tmovl %s,%s\n",tmpRegName[r1],tmpRegName[REG_AX]); printf("\timull\t%s,%s\n",tmpRegName[r2],tmpRegName[REG_AX]); break; case LT: r1 = useReg(opd2); r2 = useReg(opd3); freeReg(r1); freeReg(r2); if(opd1 < 0) break; r = getReg(opd1); l1 = label_counter++; l2 = label_counter++; printf("\tcmpl\t%s,%s\n",tmpRegName[r2],tmpRegName[r1]); printf("\tjl .L%d\n",l1); printf("\tmovl\t$0,%s\n",tmpRegName[r]); printf("\tjmp .L%d\n",l2); printf(".L%d:\tmovl\t$1,%s\n",l1,tmpRegName[r]); printf(".L%d:",l2); break; case GT: r1 = useReg(opd2); r2 = useReg(opd3); freeReg(r1); freeReg(r2); if(opd1 < 0) break; r = getReg(opd1); l1 = label_counter++; l2 = label_counter++; printf("\tcmpl\t%s,%s\n",tmpRegName[r2],tmpRegName[r1]); printf("\tjg .L%d\n",l1); printf("\tmovl\t$0,%s\n",tmpRegName[r]); printf("\tjmp .L%d\n",l2); printf(".L%d:\tmovl\t$1,%s\n",l1,tmpRegName[r]); printf(".L%d:",l2); break;

x86_code_gen.c

	case ADD:
	    r1 = useReg(opd2); r2 = useReg(opd3);
	    freeReg(r1); freeReg(r2);
	    if(opd1 < 0) break;
	    assignReg(opd1,r1);
	    printf("\taddl\t%s,%s\n",tmpRegName[r2],tmpRegName[r1]);
	    break;
	case SUB:
	    r1 = useReg(opd2); r2 = useReg(opd3);
	    freeReg(r1); freeReg(r2);
	    if(opd1 < 0) break;
	    assignReg(opd1,r1);
	    printf("\tsubl\t%s,%s\n",tmpRegName[r2],tmpRegName[r1]);
	    break;
	case MUL:
	    r1 = useReg(opd2); r2 = useReg(opd3);
	    freeReg(r1); freeReg(r2);
	    if(opd1 < 0) break;
	    assignReg(opd1,REG_AX);
	    saveReg(REG_DX);
	    if(r1 != REG_AX) 
		printf("\tmovl %s,%s\n",tmpRegName[r1],tmpRegName[REG_AX]);
	    printf("\timull\t%s,%s\n",tmpRegName[r2],tmpRegName[REG_AX]);
	    break;
	case LT:
	    r1 = useReg(opd2); r2 = useReg(opd3);
	    freeReg(r1); freeReg(r2);
	    if(opd1 < 0) break;
	    r = getReg(opd1);
	    l1 = label_counter++;
	    l2 = label_counter++;
	    printf("\tcmpl\t%s,%s\n",tmpRegName[r2],tmpRegName[r1]);
	    printf("\tjl .L%d\n",l1);
	    printf("\tmovl\t$0,%s\n",tmpRegName[r]);
	    printf("\tjmp .L%d\n",l2);
	    printf(".L%d:\tmovl\t$1,%s\n",l1,tmpRegName[r]);
	    printf(".L%d:",l2);
	    break;
	case GT:
	    r1 = useReg(opd2); r2 = useReg(opd3);
	    freeReg(r1); freeReg(r2);
	    if(opd1 < 0) break;
	    r = getReg(opd1);
	    l1 = label_counter++;
	    l2 = label_counter++;
	    printf("\tcmpl\t%s,%s\n",tmpRegName[r2],tmpRegName[r1]);
	    printf("\tjg .L%d\n",l1);
	    printf("\tmovl\t$0,%s\n",tmpRegName[r]);
	    printf("\tjmp .L%d\n",l2);
	    printf(".L%d:\tmovl\t$1,%s\n",l1,tmpRegName[r]);
	    printf(".L%d:",l2);
	    break;

演算に関しては、x86は2オペランド命令なので、片方のオペランドになったものは、assginRegでターゲットにわり当てる。
MULに関しては、片方のオペランドが%eaxにいれておく必要がある。
LTやGTについては、ターゲットに0か1が残るようにコードを生成している。しかし、分岐命令を中間コードにして出力するようにすれば、もっと効率的なコードを出力することができる。

x86_code_gen.c
case PRINTLN: r = useReg(opd1); freeReg(r); printf("\tpushl\t%s\n",tmpRegName[r]); printf("\tpushl\t$.LC%d\n",opd2); saveAllRegs(); printf("\tcall\tprintln\n"); printf("\taddl\t$8,%%esp\n"); break; } } /* return sequence */ printf(".L%d:\tmovl\t-4(%%ebp), %%ebx\n",ret_lab); printf("\tleave\n"); printf("\tret\n"); }

x86_code_gen.c

	case PRINTLN:
	    r = useReg(opd1); freeReg(r);
	    printf("\tpushl\t%s\n",tmpRegName[r]);
	    printf("\tpushl\t$.LC%d\n",opd2);
	    saveAllRegs();
	    printf("\tcall\tprintln\n");
	    printf("\taddl\t$8,%%esp\n");
	    break;
	}
    }

    /* return sequence */
    printf(".L%d:\tmovl\t-4(%%ebp), %%ebx\n",ret_lab);
    printf("\tleave\n");
    printf("\tret\n");
}

RPINTLNでは、外部関数であるprintlnを呼び出すコードを生成する。
最後に、ret_labを生成して、ここに関数の戻りのコード列を生成する。
ret_lab: movl -4(%ebp),%ebx leave ret
最初に退避した%ebxを復帰し、leave命令で%ebp,%espを戻し、ret命令で戻る

なお、最後に文字列については、以下のコードを生成して、文字列を確保しておく。

x86_code_gen.c
int genString(char *s) { int l; l = label_counter++; printf("\t.section\t.rodata\n"); printf(".LC%d:\n",l); printf("\t.string \"%s\"\n",s); return l; }

変数と配列の宣言、大域変数

大域変数と配列宣言については、あえてつくっていない。インタプリタと同様に、変数と配列宣言が入力されると、declareVariableと declareArrayがyyparseから呼び出される。最終課題の１つである課題の8-1では、これを作ってもらう。少なくとも、以下の機能が必要である。

declareVariableとdeclareArrayでは、大域変数や配列を確保する命令列を生成する。適当なプログラムをつくってみて、-Sのオプションを付けてコンパイルして、どのようなコード変換されるかを調べること。
Cの大域的な宣言 int a[10]は、.comm a,40, 32のようにコンパイルされている
大域変数や配列を扱うための中間コードが必要である。例えば、以下のコードが必要となるであろう。
1. 変数をロード/ストアする中間コード
2. 配列のアドレスをロードするコード
3. 配列の要素をロード/ストアするコード
これらのコードをコンパイラが生成できるように拡張すること。

コンパイラと実行

以上説明したコンパイラtiny-cc-x86を使ってプログラムをコンパイル、実行する。tiny-cc-x86は、これまでと同じく標準入力から呼んで、コンパイルの結果のコードを標準出力に出力するようになっている。例えば、プログラムfoo.cをコンパイルして、コードfoo.sを作るには、

　% tiny_cc < foo.c > foo.ｓ

とすればよい。printlnはライブラリ関数なので、println.cにある。実行ファイルをつくるには、これをリンクして、コンパイルする。

　% cc foo.s println.c
　% a.out

とすれば、実行できる。ccの代わりに、アセンブラas、リンカldを直接使ってもよい。