Cコンパイラ設計(yacc・lexの応用)/第7章　コードの生成 の変更点

http://www.pwv.co.jp/~take/TakeWiki/index.php?C%E3%82%B3%E3%83%B3%E3%83%91%E3%82%A4%E3%83%A9%E8%A8%AD%E8%A8%88%28yacc%E3%83%BBlex%E3%81%AE%E5%BF%9C%E7%94%A8%29%2F%E7%AC%AC7%E7%AB%A0%E3%80%80%E3%82%B3%E3%83%BC%E3%83%89%E3%81%AE%E7%94%9F%E6%88%90

[ トップ ]   [ 編集 | 差分 | バックアップ | 添付 | リロード ]   [ 新規 | 一覧 | 単語検索 | 最終更新 | ヘルプ ]

• 追加された行はこの色です。
• 削除された行はこの色です。
• Cコンパイラ設計(yacc・lexの応用)/第7章　コードの生成 へ行く。
• Cコンパイラ設計(yacc・lexの応用)/第7章　コードの生成 の差分を削除

---

[[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;
}
}}


if_prefixは、式の評価を行なうとともに一まだ決定されていない一ラベルヘの分岐を
決定する必要がある。このラベルはif_prefixがyaccのスタック上に保存するようにするも
のである。分岐は、状態が達成されていない場合にはif文のthen部をスキップするようにし
なければならない。このラベルは対応するステートメントの後に定義されなければならない。

#pre{{
statement
	: if_prefix statement
		{ gen_label($1); }
}}

gen_label()は、equ疑似命令を用いてラベルの定義を作り出す。

#pre{{
int gen_label(label)
	int label
{
	printf("%s\tequ\t*\n", format_label(label));
	return label
}
}}

else部が存在する場合には、else部の先頭でラベルが定義されなければならない。しかし、
そのラベルよりも前に、制御をthen部の最後から直接if文の最後に移すための無条件分岐が
置かれなければならない。そこで再び、末定義ラベルをそのラベルが定義される地点にまで渡
すために、yaccのスタックが使用される。

#pre{{
statement
	: if_prefix statement ELSE
		{ $<y_lab>$ = gen_jump(OP_JUMP, new_label(),
			"past ELSE");
		  gen_lable($1);
	  statement
		{ gen_label($<y_lab>4); }
}}

入力エラーが生じると、生成されるコードが無効になってしまう。そこで、分岐のための命
令は、次のように生成されなくてはならない。

#pre{{
if_prefix
	: IF error
		{ $$ = gen_jump(OP_JUMPZ, new label(), "IF"); }
}}

もし適当な値がスタック上に存在しなければ、jumpzはアンダーフローを起こしてしまうで
あろう。また、分岐命令を生成することなく、new」abelOから得た値を返すだけであれば、
長時間の実行の後にスタックのオーバーフローを起こすであろう。

whileループも同じ手法で処理される。

#pre{{
%type	<y_lab> loop_prefix
%%

loop_prefix
	: WHILE '('
		{ $<y_lab>$ = gen_label(newlabel());
		  push_continue($<y_lab>$);
		}
	  expression rp
		{ $$ = $<y_lab>3; }
	| WHILE error
		{ $$ = gen_label(new_label());
		  push_continue($$);
		}
}}
loop_prefixでは、まず繰返し地点をマークするために新たなラベルが定義された後、状態
評価のためのコードが生成される。このラベルは結果として渡される。

二番目の、この時点では未定義であり、状態値をテストする地点を示しているラベルヘの分
岐命令は、ステートメントのレベルで生成される。この方法を用いると、このラベルはyacc
のスタックの二番目のスロットで渡されるはずである。

statement
	: loop_prefix
		{ $<y_lab>$ = gen_jump(OP_JUMPZ, new_label(),
			"WHILE");
		  push_break($<y_lab>$);
		}
	  statement
		{ gen_jump(OP_JUMP, $1, "repeat WHILE");
		  gen_label($<y_lab>2);
		  pop_break();
		  pop_continue();
		}

続いて、関連するステートメントに対するコードが生成される。繰返し地点への無条件分岐が
それに続き、while構造から脱出する際に分岐する光となるラベルが定義される。

結果として得られるコードは、決して最適な効率のものではない。もし状態評価のためのコ
ードを、関連するステートメントの後に移動させるならば、ループを継続させるために条件付
き分岐を使用することが可能になり、一回の繰返しにつき一つの分岐命令を節約できる。しか
し、そのためには式のためのコードを(ステートメントに対応するコードの生成が終了するま
で)どこかに退避しておかなければならない。

sampleCにはbreak文とcontinue文が存在する。これらはwhile構造内で終了地点や継続
地点に制御を移すものである。これらのステートメントは無条件分岐として実現されなければ
ならず、したがって適切なラベルを与える必要がある。while文は入れ十にすることができる
ので、ラベルはスタックされなくてはならない。C言語ではswitchがbreakに対する新たな
入れ戸のレベルを作り出してしまうが、continueに対するものはwhile以外では作られない
ので、sampleCでは一種類のスタックだけで実現可能であったが、二種類のスタックが実現
されることが必要となる。

ラベルはすでに、loop_prefix内やwhile文の展開の際に、スタックに保存されている。こ
のラベルはwhileの構造に従ってpopされていく。push()やpop()というスタック管理用関数
の存在を仮定すると、この処理は以下に示すようなものとなる。

#pre{{
push_break(labe)
	int label;
{
	b_top = push(b_top, label);
}

push_continue(label)
	int label;
{
	c_ctop = push(c_top, label);
}

pop_break()
{
	b_top = pop(b_top);
}

pop_continue()
{
	c_top = pop(c_top);
}

}}

スタックを調べるためのtop()関数を仮定すると、breakやcontinueを実現するのは簡単であ
る。

#pre{{
statement
	: BREAK sc
		{ gen_break(); }
	| CONTINUE sc
		{ gen_continue(); }

}}

#pre{{
gen_break()
{
	gen_jump(OP_JUMP, top(b_top), "BREAK");
}

gen_continue()
{
	gen_jump(OP_JUMP, top(c_top), "CONTINUE");
}
}}

スタック管理そのものは、特に難しいものではない。以下に内部的なラベルを保持し、かつス
タックとしてリンクされる構造体を定義する。

#pre{{
static struct bc_stack {
	int bc_label;		/* label from new_label */
	struct bc_stack *bc_next;
	} * b_top,		/* head of break stack */
	  * c_top;		/* head of continue stack */
}}


b_topはbreakスタックの先頭要素へのポインタである。同様に、c_topもcontinueスタッ
クを指している。スタックが空の場合、すなわちbreakやcontinue文の使用が許されない場
合には、双方ともnullとなる。

push()には、スタックヘのポインタと、プッシュすべきラベルの値が渡され、これに対して
新たな要素へのポインタが返される。この要素の先には、残りのスタックがリンクされてい
る。プッシュ操作を完了させるためには、結果の値は引数として渡されたポインタに割り当て
られなければならない。

#pre{{
static struc bc_stack * push(stack, label)
	struct bcstack * stack;
	int label;
{	struct bc_stack * new_entry = (struct bc_stack *)
		calloc(1, sizeof(struct bc_stack));
		
	if (new_entry)
	{	new_entry->bc_next = stack;
		new_entry->bc_label = label;
		return new_entry;
	}
	ftal("No more room to compile loops.");
	/*NOTREACHED*/
}
}}

同様に、pop()はスタックの先頭要素を捨て、残りへのポインタを返すが、このポインタ
も、引数として渡されたスタック・ポインタに割り当てられなければならない。

#pre{{
static struct bc_stack * pop(stack)
	struct bc_stack * stack;
{	struct bc_stack * old_entry;

	if (stack)
	{	old_entry = stack;
		stack = old_entry->bc_next;
		cfree(old_entry);
		return stack;
	}
	bug("break/continue stack underflow");
	/*notREACHED*/
}
}}

top()では、breakやcontinueの正当性の検査が行なわれる。

#pre{{
static int top(stack)
	struct bc_stack * stack;
{
	if (! stack)
	{	error("no loop opne");
		return 0;
	}
	else
		return stack->bc_label;
}
}}

残された実現すべき操作は一つだけである。それは、関数呼出しを行ない、新たな関数の作
業領域の初期化を行ない、そして関数呼出しからの復帰を行なうためのコードを生成すること
である。call命令はある関数に制御を移すために使用される。

#pre{{
binary
	: Identifier '('
		{ chk_func($1); }
	  optional_argument_list rp
		{ gen_call($1,$4); }
}}

引数となっている式がまずリデュースされるため、この関数ではパラメータの値はスタックに
置かれる。したがって、関数からのreturnの際には、これらの値をすべてスタック上からホ
ップしてしまわなくてはならない。このため、結果をスタック上で渡すための方法は難しくな

ってしまう。したがって、ここではグローバル・セグメントの・先頭で結果を渡すようにしてい
る。gen、call()はこの値をスタック.トにプッシュしなければならない。そして・そこで関数値
がcallに続く部分に対しての引数に置き換えられることになる。

#pre{{
gen_call(symbol, count)
	struct symtab * symbol;	/* function */
	int count;		/* # of arguments */
{
	chk_parm(symbol, count);
	printf("\t%s\t%d,%s\n", OP_CALL, count, symbol->s_name);
	while (count-- > 0)
		gen_pr(OP_POP, "pop argument");
	gen(OP_LOAD, MOD_GLOBAL, 0, "push result");
}
}}

call命令に続く地点に制御を戻すために、return命令が存在する。callは戻り番地をスタッ
クにプッシュし、returnはそれを消去する。したがって、それらは再帰的に使用することが
可能となる。もし値が返されるのであオーじは、それはスターソク。」二に置かれているので、return
命令が実行される前に、グローバル・セグメントの先頭に設定された結果のための領域に移動
されなければならない。

#pre{{
statement
	: RETURN sc
		{ gen_pr(OP_RETURN, "RETURN"); }
	| RETURN expression sc
		{ gen(OP_STORE, MOD_GLOBAL, 0, "save result");
		  gen_pr(OP_RETURN, "RETRUN");
		}
}}

callは戻り番地をスタック上にプッシュしている。ある関数が呼ばれた場合、そこではスタ
ック上に古い作業領域のアドレスをプッシュしなければならないし、新たなその時点での作業
領域の先頭をスタックの先頭に割り当て、その値をレジスタにセットしなければならない。そ
の上でスタックの先頭を指していたレジスタは、新たな作業領域に適応するように変更されな
ければならない。これらすべてのことは、entry命令によって行なわれる。このentry命令
は、新たな作業領域のサイズをそのパラメータとして必要とする。

#pre{{
function_definition
	: Identifier '('
		{ make_func($1);
		  blk_push();
		}
	  optional_parameter_list rp
	  parameter_declarations
		{ chk_parm($1, parm_default($4);
		  all_parm($4);
		  l_max = 0;
		  $<y_lab>$ = gen_entry($1);
		}
	  compound_statement
		{ all_func($1);
		  gen_pr(OP_RETURN, "end of function");
		  fix_entry($1, $<y_lab>7);
		}
}}

残念ながら、コンパイルを開始する時点では、作業領域のサイズを知ることはできない。した
がって、entry命令のパラメータとして新たなラベルを使用し、これをyaccのスタックを利用
して渡すことにする。

#pre{{
gen_entry(symbol)
	struct symtab * symbol;	/* function */
{	int label = new_label();

	printf("%s\t", symbol->s_name);
	printf("%s\t%s\n", OP_ENTRY, format_label(label));
	return label;
}
}}

関数本体のコンパイルを行うことで、このラベルの値を定義することができるようになる。

#pre{{
fix_entry(symbol, label)
	struct symtab * symbol;	/* function */
	int label;
{	extern int l_max;	/* size of local region */

	printf("%s\tequ=t%d\t\t; %s\n", format_label(label),
		l_max, symbol->s_name);
}
}}

全プログラムのコンパイル終了時には、グローバル・セグメントのサイズがわかる。また、
プログラムのどこかで定義されているmain()関数を呼び出すことで、実行が始まるようにし
なければならない。この情報はendという疑似命令を通じて決定される。

#pre{{
program
	:	{ init(); }
	  definitions
		{ end_program(); }
}}

#pre{{
end_program()
{	extern int g_offset;	/* size of global region */

	all_program();		/* allocate global variables */
	printf("\tend=t%d,main\n", g_offset);
}
}}

コード生成の例として、二つの正の整数の最大公約数を求めるためのユークリッドのアルゴリズムの
実現を以下にしめす。

#pre{{
/*
 *	Euclid's algorithm
 */

main()
{	int a,b;

	a = 36;
	b = 54;
	
	while( a != b)
		if (a > b)
			a -= b;
		else
			b -= a;
}
}}

結果のアセンブラ・コードは、以下に示す通りである。

#pre{{
main	entry	$$1
	load	con,36
		store	lcl,0		; a
		pop			; clear stack
		load	con,54
		store	lcl,1		; b
		pop			; clear stack
$$2	equ	*
	load	lcl,0			; a
	load	lcl,1			; b
	alu	!=			; !=
	jumpz	$$3			; WHILE
	load	lcl,0			; a
	load	lcl,1			; b
	alu	>			; >
	jumpz	$$4			; IF
	load	lcl,0			; a
	load	lcl,1			; b
	alu	-			; -
	store	lcl,0			; a
	pop				; clear stack
	jump	$$5			; past ELSE
$$4	equ	*
	load	lcl,1			; b
	load	lcl,0			; b
	alu	-			; -
	store	lcl,1			; b
	pop				; clear stack
$$5	equ	*
	jump	$$2			; repeat WHILE
$$3	equ	*
	return				; end of function
$$1	equ	2			; main
	end	1,main
}}

** 問題 [#g4f4abf5]
+ samp1eCを実際の計算機トで実現せよ。一つの方法は、この章で用いた命令を実際の
計算機のマクロとして定義する方法である。もう一つの方法は、コード生成部を直接変更
することである。ただし、スタック・マシンであるという仮定はそのままにする。異なっ
たアーキテクチャ、たとえばレジスタ・マシンでの使用に適した実現は非常に難しいはず
である。.
+ ユークリッソド・アルゴリズムの例からもわかるように、生成されたアセンブラ・コード
は常に効率が良いものであるとは言えない。たとえば、生成されたコードの一部は、次の
ようなものである。
#pre{{
	jump	$$5		; past ELSE
	...
$$5	equ	*		
	sump	$$2		; repeat WHILE
}}
不連統な制御の移動は、ラベルの付けられた地点に対してしか行なわれない。もし、その
ようなラベルの定義の直後がjumpであるとすると、ラベルをそのjumpのターゲットと
等しくすることで、最適化が可能となる。この例では、先に示したequの代わりに、次
のようなコードが生成されるべきである。
#pre{{
$$5     equ     $$2
}}
これはいかにすれば達成できるか。
ヒント:一つの方法はポスト・プロセッサを含むことである。このポスト・プロセッサ
はコンパイラの出力を得て、アセンブラに渡す前に最適化を行なうプログラムである。最
適化は1パス・コンパイラそのものの中で可能であろうか?
+ 別の効率の低下は、制御が移ることのないコードの問題によって生じる。たとえば、
return文が関数の終了よりも前にあった場合、sampleCのコンパイラは二つのreturn命
令を生成してしまう。実際、これは値を返すような関数においては頻繁に生じる。いかに
すればこの余分なreturn命令を削除できるか?
+ もう一つ別の効率の低ドは、連続的な1oadとpopの実行によるものである。たとえ
ば、ステートメントが関数の呼出しから成立している場合(この関数の結果は無視する)、
今まで示したコンパイラでは、callに続いて結果の値をloadしてしまい、その直後にス
テートメントの終了として同じ値をpopしてしまう。この不必要な連続はいかにすれば
削除されるか?

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

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

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

#comment_kcaptcha

削除しました（removed）

       

Site admin: anonymous

PukiWiki 1.4.7 Copyright © 2001-2006 PukiWiki Developers Team. License is GPL.
Based on "PukiWiki" 1.3 by yu-ji. Powered by PHP 5.1.6. HTML convert time: 0.010 sec.