Cコンパイラ設計(yacc・lexの応用)/第7章　コードの生成のバックアップソース(No.2)

[[FrontPage]]

2008/05/17からのアクセス回数 &counter;

#contents

* 第7章　コードの生成 [#u53265b5]

以上のことで、架空の計算機においてメモリの割当てができるようになったので、その計算
機に対するコードを生成するコンパイラを作成する準備は整ったと言える。この章の大部分
は、スタック・マシンに対するコードの生成をいかにして行なうかを示す。7.2節では、マシ
ン上で利用可能な命令を定義することから始まり、式の値の計算や、ステートメントの割当て
のためのコードの生成をポし、その上で、ifやwhileといった制御構造を実現するためのコー
ドの生成に関する問題点を考える。生成されるコードの最適化についてはほとんど扱わない。
しかし、この章の最後の問題では、いかにして効率を良くするかについてある程度示す。

** 原理 [#odf557af]
コード生成において行なう基本的なことは、プログラミング言語において表現されるおのお
のの動作(action)に対して、どのような命令が実行されなければならないかを決定することで
ある。もっとも直接的な方法は、スタック・マシンを仮定して、式を決められた形に変更して
しまうことである。局所変数や広域変数を指定可能とすることに対しては、対象となるマシン
のアドレス構造に依存した問題を提起するであろう。

これを実現するための、非常に重要であるが、しかし困難な問題とは、関数コールに対する
呼出し手続きの設計である。以下で示す例のために、ここでは“適当な''命令を仮定している。
実際のマシン上での作業領域スタックの管理を行なうためには、専用のサブプログラムを作成
し、コンパイルされたそれぞれのプログラムにリンクすることが必要である。このようなサブ
プログラムは、コンパイルされたコードのデバッグや実行過程表示のためのトレースを挿入す
るためにも使用される。

繰返しや、なんらかの決定を行なうステートメントの実現のためには、通常、前方への分岐
が多数必要となる。たとえば、if文のelse部の周辺などでは、残念ながら、前方分岐の命令
は通常2回実行されなければならない。目的となるアドレスがわからない場合には、命令に対
してはある空白値がとられる。そしてその後、決定されたアドレスが代入される。もしプログ
ラムがメモリ上に存在するのであれば、関連したメモリを直接修正することが必要となる。

もしアセンブラのテキストを出力するのであれば、そのアセンブラに適切なプログラム・ア
ドレスを示すための。rigin疑似命令を使用することが可能である。これによって、実際の目
的アドレスが判明した時点でjump命令を再発行することが可能となる。しかし、この場合で
のもっとも臭い方法は、ただ単に、シンボリック・ラベルを作成し、アセンブラに前方分岐を
扱わせることである。

sampleCのbreakおよびcontinue文を実現するためには、whileやそれに類似した文が実
行された場合に、関連したラベルの情報をf呆存しておくためのスタ・ソクが必要である。もし、
switch文が言語に含まれているのであれば、二つのスタックが必要である。と言うのも、
continueのための情報と、breakのための情報とはまったく異なるからである。また、スタ
ックはこれらの文が使用可能か否かを決定するというセマンディックスの検査のためにも用い
られる。

** 例 [#ce79fd99]
ここでは、いかにして架空の計算機のためのアセンブラ・コードを生成するかについて示
す。アセンブラ・ソースのフォーマットは、多くの実在するアセンブラのものとよく似てい
る。つまり1行に一命令、必要に応じて設けるラベルのフィールドは1カラムから始まる。2
番目のフィールドは必ず存在しなければならず、ここには二一モニック・コードが存在する。
3番目のフィールドは、操作に対するf修飾やその他の情報を含む。各フィールドは空白で区切
られる。注釈は行末まで続く。ここでは書式の詳細はさほど重要ではない。と言うのも、それ
らはコード生成ルーチンで簡単一に変更できるからである。

使用可能な命令の早見表として、以下のようなヘッダ・ファイルgen.hを考える。


#pre{{
/*
 *	operation codes for pseudo machine
 */

#define OP_ALU	"alu"		/* arithmetic-logic-op	*/
#define OP_DEC	"dec"		/* region,offset	*/
#define OP_INC	"inc"		/* region,offset	*/
#define OP_LOAD	  "load"	/* region,offset	*/
#define OP_STORE  "store"	/* region,offset	*/
#define OP_POP	  "pop"		/* 			*/
#define OP_JUMPZ  "jumpz"	/* label		*/
#define OP_JUMP   "jump"	/* label		*/
#define OP_CALL   "call"	/* parm-count,address	*/
#define OP_ENTRY  "entry"	/* local-frame-size	*/
#define OP_RETURN "return"	/* 			*/

/*
 *	region modifiers
 */

#define	MOD_GLOBAL "gbl"	/* global region	*/
#define	MOD_PARAM  "par"	/* parameter region	*/
#define MOD_LOCAL  "lcl"	/* local region		*/
#define MOD_IMMED  "con"	/* load only: Constant	*/

/*
 *	OP_ALU modifiers
 */

#define ALU_ADD "+"		/* addtion		*/
#define ALU_SUB "-"		/* subtraction		*/
#define ALU_MUL "*"		/* multiplication	*/
#define ALU_DIV "/"		/* division		*/
#define ALU_MOD	"%"		/* remainder		*/
#define ALU_LT	"<"		/* compares as: <	*/
#define ALU_GT	">"		/*		>	*/
#define ALU_LE	"<="		/*		<=	*/
#define ALU_GE	">="		/*		>=	*/
#define ALU_EQ	"=="		/*		==	*/
#define ALU_NE	"!="		/*		!=	*/
#define ALU_AND	"&"		/* bit-wise and		*/
#define ALU_OR	"|"		/* bit-wise or		*/
#define ALU_XOR	"^"		/* bit-wise excl. or	*/

/*
 *	typed functions, code generator
 */

char * gen_mod();		/* region modifier	*/

}}


おのおのの命令の正確な定義は、第8章で示すシミュレータの項で与えている。コード生成
の目的のもと、おのおのの命令の影響を性格付けるために、次のような注意を払わなければな
らない。

ここでの架空計算機はスタック・マシンである。それゆえ、式に対するコード生成はきわめ
て簡単である。変数値や定数はスタック上に保存されていなければならない。このために
load命令が使用される。また演算子のためにはalu命令も実行されなければならない。alu命
令は、スタックの先頭の二つの要素の間でどのような算術演算や論理演算が行なわれるかを示
す修飾子を持っている。演算の結果はスタック上の二つの要素に取って代わる。また、修飾子
はsampleCのおのおのの演算子に対応するものとなっている。

当然、代入はstore命令によって実現される。しかし、sampleCでは、代入はなんらかの式
の中にはめ込まれた操作とすることも可能である。したがって、Store命令はスタックから値
を消去しない。その代わり、スタックトの値の消去はpop命令の使用によって実現される。
pop命令は、式の値が捨てられる時は常に実行されなければならない。

if文やwhile文に対応するコードの生成のためには、適当な分岐命令を組み合わせることが
必要である。たとえば、if文のelse部などのような、現在よりも先の位置に対する参照が必
要な場合もある。これらはカウンタによる一意的なラベルの生成、yaccのアクションによっ
て記述されるyacc用のセマンティック・スタックヘのラベルの保存、という形で処理され
る。そして、その定義されたラベルの本当の解決はアセンブラに任せられる。

breakやcontinueは、もっと難しい問題を抱えている。そういうこともあって、sampleC
ではwhileループ内でのみ使用が許されている。この場合、いくつかのスタックを持ち、それ
ぞれのwhile文に対応して適切なラベルが保存され、それらはその関係したwhileループの終
了とともにすべて消去される、といった方法がもっとも良いものである。

関数呼出しは、call命令によって実現される。この場合、関数の引数はスタック上に置かれ
ることを想定している。またcall命令は、必要となるパラメータのための領域を確保するた
めに、引数の数をその命・令の中に持っている。

関数の先頭では、局所変数のためにスタック上に確保するメモリの量を宣言するための
entry命令が必要である。callとentryの組合せによって、パラメータの引渡しや、ローカル
変数の動的な割付けに関する問題が解決される。

return命令はスタック上の局所領域をすべて消去し、関連するすべてのハードウェア・レ
ジスタを復帰する。もしreturn命令が式の評価の後に使用されるのであれば、呼出し側での
callに続くコードが、スタックからすべての引数を消去するように生成されるはずなので、
returnに先立って、結果の値を保存する必要が生じる。このコードはスタック上に関数の戻
り値を保存するようなものでなければならない。

以下に、文法規則の拡張を、それらの規則に対するアクションから呼ばれる新たなコード生
成用の関数に続いて示す。完全なリストについては、付録のA.6節を参照されたい。まず、
算術表現のためのコード生成について考えてみる。


#pre{{
binary
	: binary '+' binary
		{ gen_alu(ALU_ADD, "+"); }
}}

ほとんどすべてのコード生成関数がそうであるように、gen_alu()は単にprintf()ライブラリ
関数で構成されている。

#pre{{
gen_alu(mod, comment)
	char * mod;		/* mnemonic modifier */
	char * commnent;	/* istruction comment */
{
	printf("\t%s\t%s\t\t; %s\n", OP_ALU, mod, comment);
}
}}

aluは算術演算であることを示す。それぞれの動作はスタック上の二つの値を取り出し、そ
れらに操作を加えた上、結果をスタックに戻すというものである。この動作を行なうため、お
のおのの算術操作のオペランドはスタ・ソク上に存在していなければならない。それゆえ、まず
始めに、式の中に現われた定数や変数の値をプッシュする必要がある。

#pre{{
binary
	: Constant
		{ gen_li($1); }
}}

先に示したように、s_lookup()によってConstantに対応するテキストは保存され・このテキ
ストヘのポインタはyaccのスタック上にプッシュされている。このテキストは、ロード・イ
ミディエイト命令の作成のために使用される。この方法では、字句解析はConstantの全表現
を定義している。

#pre{{
gen_li(const)
	char * const;		/* Constant value */
{
	printf("\t%s\t%s,%s\n, OP_LOAD, MOD_IMMED, const);
}
}}

変数の値を取り出すためには、記号テーブルを作成することが必要となる。

#pre{{
%{
#define	OFFSET(x)	( ((struct symtab *) x) -> s_offset)
#define	NAME(x)		( ((struct symtab *) x) -> s_name)
%}
%%

binary
	: Identifier
		{ chk_var($1);
		  gen(OP_LOAD, gen_mod($1), OFFSET($1), NAME($1));
		}
}}

gen_mod()がs_blknumの値から適切な領域に対する修飾子を作り出し、OFFSET()と
NAME()は記号テーブルのエントリから関係する項目を選び出す。また、gen()はさまざまな
項目から一つの命令を作成する。

#pre{{
char * gen_mod(symbol)
	struct symtab * symbol;
{
	switch (symbol->s_blknum) {
	case 1:
		return MOD_GLOBAL;
	case 2:
		return MOD_PARAM;
	}
	return MOD_LOCAL;
}

gen(op, mod, val, comment)
	char * op;		/* mnemonic operation code */
	char * mod;		/* mnemonic modifier */
	int val;		/* offset field */
	char * comment;		/* instruction comment */
{
	printf("\t%s\t%s,%d\t\t; %s\n", op, mod, val, commnet);
}
}}

代入文に対しては、代入されるべき値を評価するようなコードを生成しなくてはならない。
単純な代入であればstore命令で実現できるが、複雑な代入文に対してはまずloadが実行さ
れ、適切なa1u命令がそれに続くことが必要であり、その後にStore命令が実行される。
Storeは、式中や関数の引数中での代人のことを考えて、スタックに保存された値を取り出さ
ない。

#pre{{
binary
	: Identifier '=' binary
		{ chk_var($1);
		  gen(OP_STORE, gen_mod($1), OFFSET($1), NAME($1));
		}
	| Identifier PE
		{ chk_var($1);
		  gen(OP_LOAD, gen_mod($1), OFFSET($1), NAME($1));
		}
	  binary
		{ gen_alu(ALU_ADD, "+");
		  gen(OP_STORE, gen_mod($1), OFFSET($1), NAME($1));
		}


}}

"幸運なことに"インクリメントやデクリメント操作に対しては特別な命令が設定されてい
る。それはメモリの内容を変更し、さらにその結果をスタックに置くものである。その例とし
て、ここではインクリメント操作に関して示す。

#pre{{
binary
	: PP Identifier
		{ chk_var($2);
		  gen(OP_INC, gen_mod($2), OFFSET($2), NAME($2);
		}
}}

C言語におけるコンマ演算子は、二つの式を順番に評価するものである。つまり、まず左側
のオペランドが評価されてその結果が捨てられ、次に右のオペランドが評価されてその結果が
返される。ここで・結果を捨てるとは・スターソクをポップすることを意味している。

#pre{{
expression
	: binary
	| expression ','
		{ gen_pr(OP_POP, "discard"); }
	  binary
		{ yyerrok; }
}}

pop命令は、ただ単にポップ動作を行なうだけである。二番目のbina町のリデュースの結果
として、別の結果の値はスタック上に残したままにするようなコードが生成される。gen.prO
は、後にreturn命令を生成するためにも使われる。

#pre{{
gen_pr(op, comment)
	char * op;		/* mnemonic operation code */
	char * comment;		/* instruction comment */
{
	printf("\t%s\t\t\t; %s\n", op, comment);
}
}}

ここまでで、いろいろなステートメントを考慮するための準備が整った。もちろん、空のス
テートメントに対しては何も生成する必要はない。compound.statementはその構成要素の
並びとして自動的に処理される。ステートメントとしての算術式の評価は、コンマ演算子の場
合に似ている。つま^)、式の結果の値は捨てられなければならない、ということである。

#pre{{
statement
	: sc
	| compound_statement
	| expression sc
		{ gen_pr(OP_POP, "clear stack"); }
}}


制御構造は分岐命令を用いて実現される。そのもっとも簡単なものがif文である。

#pre{{
%type	<y_lab> if_prefix
%%
if_prefix
	: IF '(' expression rp
		{ $$ = gen_jump(OP_JUMPZ, new_label(), "IF"); }
}}

式に対するコードは通常、ある値をスタック上に残すように生成される。jumpz命令は、こ
の値がゼロである場合に分岐を行なう。そして分岐の有無を問わず、値はスタックから消去さ
れる。

#pre{{
int gen_jump(op, label, comment)
	char * op;		/* mnemonic operation code */
	int label;		/* target of jump */
	char * comment;		/* instruction comment	*/
{
	printf("\t%s\t%s\t\t; %s\n"), op, format_label(label),
		comment);
	return label;
}
}}

new_lable()は、呼び出されるごとに、新たな一意的なラベルを返す関数である。ここでは
ある静的な整数変数を数え上げることによって、一意的なラベルを作り出している。この結果
の値はyaccのスタックに保存される。（gen_jump()はこの目的のためのラベルの値を返す。）
format_label()関数は、一意的な整数値を、アセンブラに受け入れられるラベルとして表現す
るために用いられる。

#pre{{
int new_label()
{	sttaic int new_label = 0;
	return ++new_label;
}

#define	LABEL	"$$%d"

static char * format_label(label)
	int label;
{	static char buffer[sizeof LABEL + 2];

	sprintf(buffer, LABEL, label);
	return buffer;
}
}}


** コメント [#ueedca7c]
この記事は、

#vote(おもしろかった,そうでもない,わかりずらい)

皆様のご意見、ご希望をお待ちしております。

#comment
Cコンパイラ設計(yacc・lexの応用)/第7章 コードの生成 のバックアップソース(No.2)

Cコンパイラ設計(yacc・lexの応用)/第7章　コードの生成のバックアップソース(No.2)
