スタックマシンへのコンパイラ

前回は、コンパイル対象となるスタックマシンについて説明した。今回は、ス タックマシンへのtiny Cコンパイラについて解説する。 プログラムは、以下のものである。

コンパイラのmainプログラム

コンパイラでは、最初に構文解析を呼び出し、構文解析ルーチンのの中で、入 力された外部定義ごとにdefineFunctionやdeclareVariableが呼び出される。 この関数がASTを入力してコンパイルを行う。したがって、コンパイラのmain プログラムは単に、yyparseを呼び出すのみである。

compiler_main.c 
main()
{
    yyparse();
    return 0;
}
なお、parserのcparse.yや字句解析のlex.cはインタプリターと同一のものを 使う。

コードの生成ルーチン

コンパイラの説明を始める前に、コード生成部のルーチンについて説明してお く。コンパイラでは、通常、一つ一つの関数ごとにコンパイルしていく。コン パイラでは、このコードをメモリに格納しておき、関数のコンパイルが終るご とに出力する。スタックマシンの説明で述べたとおり、命令は命令コードとオ ペランドからなる。コードを格納する領域の定義は以下のようになる。

st_code_gen.c 
struct _code {
    int opcode;
    int operand;
} Codes[MAX_CODE];

int n_code;
n_codeはいくつコードが生成されたかを管理するカウンタ である。

コード生成は以下の関数を使って行う。initGenCodeはそれぞれの関数のコン パイルの前に呼び出し、コード領域をクリアする。

st_code_gen.c 
void initGenCode()
{
    n_code = 0;
}

void genCode(int opcode)
{
    Codes[n_code++].opcode = opcode;
}

void genCodeI(int opcode, int i)
{
    Codes[n_code].opcode = opcode;
    Codes[n_code++].operand = i;
}

void genCodeS(int opcode,char *s)
{
    Codes[n_code].opcode = opcode;
    Codes[n_code++].operand = (int)s;
}
オペランドが文字列のアドレスなどのポインタの場合は、キャストして無理 矢理代入している。

関数がコンパイルが終ったら、genFuncCodeでコードを出力する。これについ ては、関数のコンパイルで説明する。 

void genFuncCode(char *entry_name, int n_local);
なお、スタックマシンの命令コードは、st_code.hに定義されている。

スタックマシンの関数呼び出しの構造

前回説明したとおり、スタックマシンは関数呼び出しのために、SPとFPを つかう。SPスタックポインタは、スタックのtop（の上）を指しているレジ スタで、フレームポインタFPは関数の呼び出し側の情報を保存しているとこ ろを指すようにする。ここからの相対で、引数や局所変数にアクセスする。関 数の呼び出しの手順は、以下のようにする。

  1. スタック上に引数を積む。
  2. 現在のPCの次のアドレスをスタック上に保存(push)し、関数の先頭の アドレスにjumpする。（CALL命令） 現在のFPをスタック上に保存し(push)し、ここを新たなFPとする。FPか ら、上の部分を局所変数の領域を確保し、ここを新たなスタックの先頭にする。 (FRAME命令)
  3. 式の評価のためのstackはここから始まる。
  4. 引数にアクセスするためには、FPから２つ離れたところにあるので、こ こからとればよい。(LOADA/STOREA命令)
  5. 局所変数にアクセスするためには、FPの上にあるので、FPを基準にして アクセスする。(LOADL/STOREL命令)
  6. 関数から帰る場合には、stackに積まれている値を戻り値にする。元の関 数に戻るためには、FPのところにSPを戻して、まず、前のFPを戻して、次に戻 りアドレスを取り出して、そこにjumpすればよい。(RET命令)
  7. 戻ったら、引数の部分をpopして、関数の戻り値をpushしておく。 (POPR命令)
このような構造を、関数フレームと呼ぶ。

さて、関数定義に対するコードは以下のようになる。 

ENTRY foo
FRAME ローカル変数の個数
 ... 関数本体のコード...
RET
また、関数呼び出しは、 
引数１のpush ...
引数2のpush ...
 ....
CALL foo
POPR  pushした引数の個数

コンパイラのための環境

上でみたように、関数のコンパイルするためには引数や局所変数の位置を決め なくてはならない。 パラメータの変数や局所変数は、スタック上にその領域が確保されるが、ど こに確保されるかを数えておかなくてはならない。この変数がどこに割り当て られているかを覚えておくために、インタプリータで使った環境Envと同じよ うなデータ構造をつかう。コンパイラでは、Envでコンパイルしているときに どの変数がスタック上のどこに割り当てられているかを覚えておく。パラメー タについては、パラメータの何番目かについて、Envに登録しておく。したがっ て、コンパイラでは環境は以下のようなデータ構造である。

st_compile.c 
#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)を区 別するフィールドで、posにフレーム上の位置を記録しておく。

関数のコンパイル

yyparseの中で、関数定義が入力されるとdefineFunctionが呼び出される。

st_compiler.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);
    envp = 0;  /* reset */
}
  1. まず、genCodeInitを呼び出し、コード領域をクリアする。
  2. パラメータ変数に番号をつける。関数が呼ばれた場合にはこの順番でス タックに積まれていることになる。これをEnvをいれておく。この時、ローカ ル変数であることを示すVAR_ARGをセットしておく。
  3. 関数の本体をコンパイルする。本体の文がコンパイルされると、 本体の実行のためのコードが生成され、コード領域に格納される。
  4. 最後に、genFuncCodeを実行し、コード領域にあるコードを出力する。
コードを一時的にコード領域に格納しておいて、genFuncCodeで出力する理由 の一つは、コードを全部コンパイルしてみないとローカル変数などに必要な 関数フレームのサイズが分からないためである。 関数の本体にblock文（Cの｛｝にあたる）がある場合には、局所変数が定義 される可能性がある。block文をコンパイルするときには、local_var_posとい う変数を使って数えて、これでスタック上の何番目に割り当てるかを決める。 本体のコンパイルが終わると、局所変数が何個合ったかがわかるので、これを 使って関数の先頭で、FRAME命令を生成しなくてはならない。そのため、生成 されたコードを配列(Codes)にとっておき、ENTRY命令の後にFRAME命令を生成 し、とっておいた残りの命令を出力する。 必要なローカル変数 のカウンタであるlocal_var_posを引数にして、genFuncCodeが呼び出される。 genFuncCodeを下に示す。
st_code_gen.c 
void genFuncCode(char *entry_name, int n_local)
{
    int i;

    printf("ENTRY %s\n",entry_name);
    printf("FRAME %d\n",n_local);
    for(i = 0; i < n_code; i++){
	printf("%s ",st_code_name(Codes[i].opcode));
	switch(Codes[i].opcode){
	case PUSHI:
	case LOADA:
	case LOADL:
	case STOREA:
	case STOREL:
	case POPR:
	    printf("%d",Codes[i].operand);
	    break;
	case BEQ0:
	case LABEL:
	case JUMP:
	    printf("L%d",Codes[i].operand);
	    break;
	case CALL:
	    printf("%s",(char *)Codes[i].operand);
	    break;
	case PRINTLN:
	    printf("\"%s\"",(char *)Codes[i].operand);
	    break;
	}
	printf("\n");
    }
    printf("RET\n");
}
既に生成されているコードに関数の始めのENTRYとローカル変数を指定する FRAME命令、RETのコードを加えて、コードを出力する。

式のコンパイル

さて、式のコンパイルから説明することにする。 インタープリタでは、executeExprという関数を使って式を実行したが、コン パイラではcompileExprという関数で式に対するコードを生成する。式をコン パイルすると「実行すると式の値がスタック上につまれる」コードが生成され る。コードはexecuteExprと非常に良くにている。
st_compile_expr.c 
void  compileExpr(AST *p)
{
    if(p == NULL) return;

    switch(p->op){
    case NUM:
        genCodeI(PUSHI,p->val);
	return;
    case SYM:
	compileLoadVar(getSymbol(p));
	return;
    case EQ_OP:
	compileStoreVar(getSymbol(p->left),p->right);
	return;
    case PLUS_OP:
	compileExpr(p->left);
	compileExpr(p->right);
	genCode(ADD);
	return;
    case MINUS_OP:
	compileExpr(p->left);
	compileExpr(p->right);
	genCode(SUB);
	return;
    case MUL_OP:
	compileExpr(p->left);
	compileExpr(p->right);
	genCode(MUL);
	return;
    case LT_OP:
	compileExpr(p->left);
	compileExpr(p->right);
	genCode(LT);
	return;
    case GT_OP:
	compileExpr(p->left);
	compileExpr(p->right);
	genCode(GT);
	return;

    case CALL_OP:
	compileCallFunc(getSymbol(p->left),p->right);
	return;

    case PRINTLN_OP:
	printFunc(p->left);
	return;

    /* 省略 */

    default:
	error("unknown operater/statement");
    }
}
  1. 式が数字であれば、その数字をpushするコードを出す。
  2. 式は変数であれば、compileLoadVarを呼び出して、その値をpushするコー ドをだす。
  3. 代入式の場合は、compileStoreVarを呼び出す。
  4. 式が演算であれば、左辺と右辺をコンパイルし、それぞれの結果をスタッ クにつむコードを出す。その後、演算子に対応したスタックマシンのコードを 出す。
  5. 関数呼び出しに対しては、compileCallFuncを呼び出す。
  6. printlnについては、printFuncを呼び出し、PRINTLNのコードを生成する。
変数はパラメータや局所変数があるについては、上に述べたようにEnv に記録されている。compileLoadVarではまず、Envを探し、それが引数であれば、 LOADAを生成する。局所変数であれば、LOADLを出力することになる。 逆に、ローカル変数やパラメータ変数に代入する関数が、compileStoreVarである。 compileStoreVarでは、右辺の式をコンパイルし、右辺式の結果をスタック上 に計算するコードを生成し、つぎに、STOREAまたはSTORELを生成する。
st_compile.c 
void compileStoreVar(Symbol *var,AST *v)
{
    int i;
    compileExpr(v);
    for(i = envp-1; i >= 0; i--){
	if(Env[i].var == var){
	    switch(Env[i].var_kind){
	    case VAR_ARG:
		genCodeI(STOREA,Env[i].pos);
		return;
	    case VAR_LOCAL:
		genCodeI(STOREL,Env[i].pos);
		return;
	    }
	}
    }
    error("undefined variable\n");
}

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

文のコンパイル

文をコンパイルするcompileStatementは、executeStatementと同じく、文の ASTのopから、それぞれの構文をコンパイルする関数を呼び出す。

st_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(p);
	genCode(POP);
    }
}
但し、式が文になる場合には、式をコンパイルするcompileExprを呼び出すが、 compileExprでは、スタック上に式の結果を残すので、それをPOPしてとりのぞ いておかなくてはならない。これを忘れるとスタックが尽きてしまう。 compileStatementでは、文の実行が終ったら、スタックは元にもどっているこ とに注意。

制御文のコンパイル

JUMP命令は、LABEL文で示されたところに制御を移す命令である。このスタッ クマシンは分岐命令は、BEQ0命令しかない。この命令は、スタック上の値を popして、これが0だったら、分岐する命令である。これを組みああわせてIF文 をコンパイルする。コードは次のようになる。 

 ...条件文のコード...
BEQ0 L0   /* もし、条件文が実行されて、結果が0だったら,Ｌに分岐*/
 ...thenの部分のコード...
JUMP L1
LABEL L0
... elseの部分のコード...
 LABEL L1

IF文のコンパイルは以下のようになる。

st_compile.c 
void compileIf(AST *cond, AST *then_part, AST *else_part)
{
    int l1,l2;

    compileExpr(cond);
    l1 = label_counter++;
    genCodeI(BEQ0,l1);
    compileStatement(then_part);
    l2 = label_counter++;
    if(else_part != NULL){
	genCodeI(JUMP,l2);
	genCodeI(LABEL,l1);
	compileStatement(else_part);
	genCodeI(LABEL,l2);
    } else {
	genCodeI(LABEL,l1);
    }
}
  1. 条件式の部分のコンパイルする。これが実行されるスタック上には、条 件式の結果が積まれているはずである。
  2. ラベルをl1を作って、BEQ L0を生成。
  3. then部分の文をコンパイルする。
  4. else部分がある場合には、
    1. then部のコードの後に、ラベルl2を作って、ここにJUMPする命令を生成する。
    2. 条件文が0だったときに実行するコードを生成する前に、LABEL l1を生成する。
    3. else部の文をコンパイル。
    4. その後に、then部の実行が終わったときに飛ぶ先LABEL l2をここにおい ておく。
  5. else部がない時に、LABEL l1を生成するだけでよい。

関数呼び出しのコンパイル

関数呼び出しのコンパイル（compileFuncCall）は、引数をスタックに積ん で、CALL命令を出す。引数をスタックに積むのは、式の実行が終わるとスタッ ク上につまれるはずなので、単に引数をコンパイルすればよい。その後に、 CALL命令を生成し、その後で、引数をスタックからpopして、結果をpushする 命令POPR命令を生成しておく。

st_compile.c 
void compileCallFunc(Symbol *f,AST *args)
{
    int nargs;
    nargs = compileArgs(args);
    genCodeS(CALL,f->name);
    genCodeI(POPR,nargs);
}

int compileArgs(AST *args)
{
    int nargs;
    if(args != NULL){
	nargs = compileArgs(getNext(args));
	compileExpr(getFirst(args));
	return nargs+1;
    } else return 0;
}
スタックに積む順番は、引数の最後からなので、compileArgsでは再帰を使っ て、引数の最後からコンパイルしている。また、この関数は同時に引数の個数 を数えていることに注意。

局所変数のコンパイル

block文では、局所変数が宣言されることがあるが、以下のようにしてコンパ イルする。

st_compile.c 
void compileBlock(AST *local_vars,AST *statements)
{
    int v;
    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;
}
  1. 局所変数について、どこに割り当てるかを決める。割り当てるスタック 上の場所の番号をつけるための数えている変数が、local_var_posである。割 り当てるときには、local_var_posを１つ加えてこの値がスタック上の局所変 数の位置になる。
  2. これがきまったら、変数のシンボルとこのスタック上をペアにして、Env に登録しておく。登録は、1で決めたスタックの位置と、var_kindをVAR_LOCAL にしておく。
  3. blockの本体の文をコンパイルする。
  4. 本体のコンパイル中に局所変数が現れた場合には、Envを探して、どこに 割り当てられているかによって、LOADA/LOADL/STOREA/STOREL命令を生成され る。
  5. blockの全部のコンパイルが終わったら、局所変数について変化させた Envを元にもどしておく。これによって、局所変数に使われた領域は参照され なくなる。

return文のコンパイル

return文のコンパイルはスタック上に式の値を残し、RET命令を生成すればよ い。

st_compile.c 
void compileReturn(AST *expr)
{
    compileExpr(expr);
    genCode(RET);
}
  1. 式をコンパイル。結果は、スタック上に結果が残るはずである。
  2. これで、RET命令を生成する。
なお、式exprがNULLの場合は結果はなにも残らないので、RETが実行されると その時点でのtopの値が返されるが、値は不定である。

While文、For文

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

変数と配列の宣言

変数と配列宣言についても、省略してある。 インタプリタと同様に、変数と配列宣言が入力されると、declareVariableと declareArrayがyyparseから呼び出される。前回説明したスタックマシン st_machineには、大域変数を扱う機能がない。これを扱うためにはどのような コードが必要なのかについて、考えてみよ。

コンパイラとスタックマシンの実行

さて、説明したコードをコンパイルして tiny-cc-stを作る。 tiny-cc-stは、標準入力から呼んで、コンパイルの結果のコードを標準出力に 出力するようになっている。例えば、プログラムfoo.cをコンパイルして、コー ドfoo.iを作るには、 

% tiny_cc < foo.c > foo.i
とすればよい。st_machineもコードは標準入力から読むようになっているので、 
% st_machine < foo.i
とすればよい。もしも、連続して動かす場合には、 
% tiny_cc < foo.c | st_machine
としてもよい。