![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
[[FrontPage]] 2008/05/19からのアクセス回数 &counter; #contents * 第8章 ロードアンドゴー・システム [#s17bc16b] 前章で、ターゲット・マシンのアーキテクチャがソース言語に近ければ、コード生成部を作 るのは比較的簡単であることを示した。メモリ配置のポリシーやソース言語における種々の動 作に対するコード配列といったインプリメンテーションが定義されれば、プログラミング・シ ステムを完成させる一つの手段として、適切なマシンのシミュレーションに取りかかることが できる。この章では、前の二つの章で仮定していた計算機のシミュレータを作成し、続いでこ のようなシミュレータを用いて、どのようにロードアンドゴー・システムを構成していくかを 示すことにする。本書の構成上、議論をsampleCに限ることにするが、いくつかの言語(たと えばPascalやModula-2)についても同じように移植を行なうことができる。 ** マシン・シミュレータ [#f10718a8] ここでの仮想マシンのシミュレータ製作は、きわめて簡単である。まず始めに、個々の命令 およびそれらの修飾部に対する数値コードを定義する必要がある。これを実現したヘッダ・フ ァイルsim.hでは、先にgen.hの中で定義した名前すべてに対し、異なった表現を与えてい る。 #pre{{ /* * operation codes for pseudo machine */ #define OP_ALU 1 /* alu arithmetic-logic-op */ #define OP_DEC 2 /* dec region,offset */ #define OP_INC 3 /* inc region,offset */ #define OP_LOAD 4 /* load region,offset */ #define OP_STORE 5 /* store region,offset */ #define OP_POP 6 /* pop */ #define OP_JUMPZ 7 /* jumpz label */ #define OP_JUMP 8 /* jump label */ #define OP_CALL 9 /* call routine-address */ #define OP_ENTRY 10 /* entry local-frame-size */ #define OP_RETURN 11 /* return */ /* * region modifiers */ #define MOD_GLOBAL 1 /* global region */ #define MOD_PARAM 2 /* parameter region */ #define MOD_LOCAL 3 /* local region */ #define MOD_IMMED 4 /* load only: Constant */ /* * OP_ALU modifiers */ #define ALU_ADD 1 /* addtion */ #define ALU_SUB 2 /* subtraction */ #define ALU_MUL 3 /* multiplication */ #define ALU_DIV 4 /* division */ #define ALU_MOD 5 /* remainder */ #define ALU_LT 6 /* compares as: < */ #define ALU_GT 7 /* > */ #define ALU_LE 8 /* <= */ #define ALU_GE 9 /* >= */ #define ALU_EQ 10 /* == */ #define ALU_NE 11 /* != */ #define ALU_AND 12 /* bit-wise and */ #define ALU_OR 13 /* bit-wise or */ #define ALU_XOR 14 /* bit-wise excl. or */ }} 最初に、仮想マシンのプログラムおよびデータ空間を扱うための配列を定義することにしよ う。データ・セルは整数型として表現するが、プログラム・セルは、デコーディングを簡単にす るために構造体を用いることにする。 #pre{{ struct prog { short p_op; /* operation code */ short p_mod; /* modifier */ int p_val; /* offset or other value */ }; /* * tunable limits */ #define L_PROG 200 /* max. program size */ #define L_DATA 100 /* max. area for stack, etc. */ #define DIM(x) (sizeof x / sizeof x[0') /* extent */ }} プログラム・セグメントの最大値および構造体progの定義は、少なくともヘッダ・ファイル に加えなければならない。コードを半成する時にこれらが必要になる。以トのことから、配列 は次のようになる。 #pre{{ #include "sim.h" /* * data and program memory */ static int data[L_DATA]; extern struct prog prog[]; }} prog[]はコード生成モジュールの中で定義する。上で示したマクロDIM()を使って配列の大 きさを調べることができるので、ベクトルに大きさを与えるための定数に依存しなくてよい。 次にレジスタの定義を行なう。現在実行中の命令を記憶する内部レジスタinstを定め、こ れによりデコーディンクを簡素化する。データ・セグメント中の種々の位置は、レジスタG、 P、L、Tでマークする。Gは、グローバル・セグメントの先頭を指し、定数Oのポインタであ る。Pは、アクティベーション・レコードの前に位置する現在のパラメータ・セグ.メントの先 頭を指す。Lは、現在のローカル・セグメント、すなわちアクティベーション・レコードの先 頭を指す。Tは、スタックのトップ、すなわちローカル・セグメントと、それに続いて現在 スタックに積まれているすべての値の次に位置するワードを示す。 #pre{{ /* * registers */ static sturct prog * inst; /* -> current instruction */ #define G 0 /* global segment */ static int P; /* current parameter segment */ static int L; /* current local segment */ static int T; /* top of stack */ }} ここでいくつかの略記を用いることにする。TOPとNEXTはスタックの一番。上二と二番目に 積まれている値を指す。PUSHは値をスタックに積む。POPはスタックの一番上にある要素 を取り除く。RESULTはデータ・セグメントの先頭に位置する語を指し、関数からの戻り値 を返すために用いる。MEMORYは現在の命令がアドレスするメモリ・セルのことである。 #pre{{ /* * shorthand notations */ #define TOP data[T-1] /* right operand; top of stack */ #define NEXT data[T-2] /* left operand: below TOP */ #define PUSH data[T++] /* new cell to come onto stack */ #define POP -- T /* -> descarded cell from stack */ #define MEMORY data[address()] /* effectively addressed cell */ #define RESULT data[G] /* result value of function */ }} これらの定義により、シミュレータを害く言語は効果的に拡張されている。ここでは、コード そのものがプログラムの仕様を改良する手助けにもなっているが、このような言語の拡張を多 用すると作られたプログラムはかえって曖昧なものとなったり、改良しにくいものとなったり しがちである。 MEMORYは関数address()を用い、data[]中のどのセルを現在の命令が参照するのかを決 定する。 #pre{{ static int address() /* effective current data address */ { regster int ad; switch (inst->p_mod) { case MOD_GLOBAL: ad = G; break; case MOD_PARAM ad = P; break; case MOD_LOCAL; ad = L; break; default: bug("invalid p_mod"); } ad += inst->p_val; if (ad < 0 || ad >= T) bug("invalid effective address"); return ad; } }} 実効アドレスは、命令の中のオフセットの値を修飾部が示すセグメントのべ一ス・アドレスに 加えることによって得られる。このアドレスは、現在のデータ・セグメントの範囲内になけれ ばならない。 これで、シミュレータの基本的な命令実行部を設計する準備ができた。simulate()は、コン パイルされたプログラムのend文から、情報を得る。この擬似命令が生成された時、コンパ イルされたプログラムの大きさpc_limit、グローバル・セグメントの大きさglobal、シミュ レーションを開始するプログラム・セグメント中の位置、すなわちコンパイルされたプログラ ム中の関数main()のアドレスpcはわかっている。したがって、これらの値はsimulate()に 渡すことができる。さらに、pcはシミュレータのプログラム・カウンタの役割も果たす。 #pre{{ simulate(pc_limit, global, pc) int pc_limit, global, pc; { /* initialize */ printf("\nExecution begins...\n\n"); for (;;) { /* fetch */ if (pc < 0 || pc >= pc_limit) bug("pc not in program area"); inst = &prog[pc++]; /* decode operation adn dispatch */ switch (inst->p_op) { default: printf("%d:\thalt\n", inst-prog); return; /* other instructions */ } } } }} 今のところレジスタP、L、Tの初期化は行なわない。これは関数の呼出し順序を定めて初 めて可能になる。main()のreturnでマシンが停止するように、レジスタおよびスタックの初 期値を定めなければならない。 第7章で導入した順序で、それぞれの命令を考えてみよう。 alu命令は簡単である。命令修飾部を別のswitch文でディスパッチして、修飾部を適切な C言語の演算子に対応させれぱよい。例を簡単にするため、O除法のような算術演算例外に対 する予防措置はとらない。ただし、オペランドが実際にスタックに存在するかどうかは調べる ことにする。もし(Lにある)ローカル・セグメントの先頭と(Tにある)スタック・トップの問 に二つのオペランドを置くための十分な空間がなければ、これはまったく不可能である。いく つかの典型的な例を示すことにしよう。 #pre{{ case OP_ALU: if (T <= L+1) bug("simulator stack underflow"); switch (inst->p_mod) { default: bug("illegal ALU instrction"); case ALU_ADD: NEXT += TOP; break; case ALU_LT: NEXT = NEXT < TOP; break; } POP break; }} コンパイル中にエラーがなかったのに、スタックのアンダーフローが起こった場合は、バグが 原因である。つまり、そのようなことは起こってはならないはずである。プログラムに誤りが ある場合にスタックがアンダーフローを起こすことがあるが、それは避けることができなかっ た、誤ったコード生成が原因である。いずれにせよ、スタック・アンダーフローの検査を厳密 に行なうのは不可能なので、そのような状況をバグであると考えることにする。 load命令では、MEMORYから変数の値をロードするのか、命令自身から直接Constant の値をロードするのかを区別しなければならない。新しい値をスタックに積んだ時は、オーバ ーフローを起こしていないかを監視する。 #pre{{ case OP_LOAD: if (T >= DIM(data)) fatal("Too much data."); if (inst->p_mod == MOD_MIMED) PUSH = inst->p_val; else PUSH = MEMORY; break; }} Store命令は、スタックにある値をメモリにコピーする。ここでは、スタックに実際に値が あるかどうか調べることにする。 #pre{{ case OP_STORE: if (T <= L) bug("simulator stack underflow"); printf("%d:\tstore\t%d,%d\tto %d\n", inst-prog, inst->p_mod, inst->p_val, MEMORY = TOP); break; }} Store命令は、シミュレーションの効果を示す良い例であろう。この命令をトレースし、どの ように値がストアされるかを示すことにする。 inc命令およびdec命令はメモリの値を変化させるだけでなく、その結果をスタックに積ま なければならない。このとき、スタ・ソクはオーバーフローを起こしてはならない。 #pre{{ case OP_INC: if (T >= DIM(data)) fatal("Too much data."); printf("%d:\tinc\t%d,%d\tto %d\n"), inst-prog, inst->p_mod, inst->p_val, PUSH = ++ MEMORY); break; case OP_DEC: if (T >= DIM(data)) fatal("Too much data."); printf("%d:\tdec\t%d,%d\tto %d\n"), inst-prog, inst->p_mod, inst->p_val, PUSH = -- MEMORY); break; }} どちらの命令もトレースされるので、メモリの変化すべてを追うことができる。 pop命令は、スタック要素が一つは存在する場合、それを捨てる。 #pre{{ case OP_POP: if (T <= L) bug("simulator stack underflow"); POP; break; }} j㎜p命令は、プログラム・カウンタpcに値を代入する。シミュレーションのループが続 いている限り、その新しい値が次の命令のアドレスとして使われる。このアドレスは、命令取 出しの時に照合される。 #pre{{ case OP_JUMP: printf("%d:\tjump\tjump=t%d\n, inst-prog, inst->p_val); pc = inst->p_val; brreak; }} jmpz命令は、スタックから値を一つ取り出し、それをテストする。もしその値がOなら ば、プログラム・カウンタに値を代入し、それにより分岐が実行される。 #pre{{ case OP_JUMPZ: if (T <= L) bug("simulator stack underflow"); if (data[POP] == 0) { printf("%d:\tjumpz\t%d\n", inst-prog, inst->p_val); pc = inst->p_val; } break; }} 分岐を実行する場合、命令をトレースすることにした。これにより命令の流れを追うことがで きる。 call命令はプログラム・カウンタの値をスタックに積む。命令取出しの段階で、プログラム ・カウンタは次の命令のアドレスを指しているので、これが正しいリターン・アドレスとな る。Can命令はまた、現在のパラメータ・セグメント・アドレスをスタックに積み、レジスタ Pがスタックにある新しいパラメータ・セグメントを指すようにする。渡される引数の数は call命令の修飾部に置かれており、またcall命令実行前に引数の値はスタックに積まれてい るので、Pの新しい値の計算は容易にできる。これらが行なわれた後、必要な関数に分岐す る。call命令もトレースする。 #pre{{ case OP_CALL: printf("%d:\tcall\t%d\n", inst-prog, inst->p_val); PUSH = pc; pc = inst->p_val; PUSH P; P = T - 2 - inst->p_mod; break; }} 新しい関数を実行する時は、(Lにある)旧ローカル・セグメントのアドレスをスタックに積 まなければならない。(Tにある)現在のスタック・トップの値をしに設定し、新しいローカ ル・セグメントの大きさに合わせてTを増加させることにより、新しいローカル・セグメン トが確立する。これらすべては、entry命令の仕事である。 #pre{{ case OP_ENTRY: PUSH = L; L = T; T += inst->p_val; if (T >= DIM(data)) fatal("Too much data."); break; }} return命令を実行する時には現在のローカル・セグメントの値をスタックから取り除かな ければならない。これはTに(Lにある)開始アドレスを設定することで実現する。これによ り、直前のローカル・セグメントとパラメータ・セグメントのアドレスがスタックの先頭に現 われる。これら二つのすぐ下にリターン・アドレスがある。これら三語もまた、スターソクから 取り除がなければならない。 #pre{{ case OP_RETURN: if (T < L) bug("simulator stack underflow"); T = L; L = data[POP]; P = data[POP]; pc = data[POP] printf("%d:\treturn\t%d to %d\n", inst-prog, RESULT, pc); break; }} 関数が値を返す場合、そ剛直は後でRESULTから取り出されスタックに積まれる。return命 令をトレースする時に、この動作を見ることができる。 関数呼出しおよびreturnはさらに簡素化することができる。パラメータ・セグメントの値 を廃棄するためだけにpop命令を生成する必要は、本当はない。つまり、元のスタックのト ップは、現在のパラメータ・セグメントの先頭として回復することができる。さらに RESULTも必要ない。元のスタック・トップを決定できるのであるから、return命令は、関 数の結果の値をそこに移せばよい。このような簡素化により、生成されるコードは短くなる が、シミュレータが複雑になってしまう。どちらの場合も簡素化はそれほど現実的とは言えな い一ハードウェア命令のreturnは、通常これよりもずっと単純である。 これでシミュレータが完成した。残っているのは初期化だけである。return命令が実行さ れる前に、プログラム・カウンタとパラメータ・セグメントのアドレスはcall命令により、 ローカル・セグメントのアドレスはentry命令により、それぞれスタック・トップに置かれる ことを前提としているのは、いま見てきたとおりである。ここで、main()呼出しのシミュレ ーションが必要である。すなわち、main()から復帰したときにシミュレータは停止しなけれ ばならない。 シミュレータは、命令コードOをプログラム・メモリの最初のアドレスに置くことにより停 止する。すなわち、すべての未定義分岐および呼出しはシミュレータを停止させる。というの も、これらはアドレスOに制御を移行するからである。したがって、main()の中のentry命 令の解釈を行なう前に、スタックにリターン・アドレスとしてOを置くことにする。こうすれ ば、main()から復帰すると同時に、シミュレータは停止する。PとLのための初期値は必要 ない。これらの値は使われないからである。call命令のシミュレーションによってスタックに 積まれているPにも初期値を設定しないでおく。 #pre{{ if (global >= DIM(data)) fatal("Not enough room for global data."); T = global + 2; }} プログラム・メモリはstaticであり、したがってOに初期化されている。 ** インコア・コード生成 [#udd38097] シミュレーションで魅力があるものの一つに、コンパイラに直接シミュレータのメモリ上に コードを生成させる方法がある。こうすれば、プログラムが(エラーを出さずに)コンパイルさ れれば、直ちに実行することができる。 生成されるコードの順序に関する限り、インコア・コード生成はアセンブラ・テキストを出 力するのと同等である。しかしながら、前方参照は2パス・アセンブラに引き渡せないので、 解決できない。したがって、シミュレーションを行なう前に、コンパイラが解消しなければな らない。命令の形式にもよるが、コード出力のためにかなりの量のビット操作が必要になるこ とがある。これがアセンブラ・テキストを生成する方法の長所の一つで、多くの困難を回避 し、コンパイラの移植性を高めている。 この節では、sampleCのためのインコア・コード生成用ユーティリティが・前節で提示し たシミュレータと組み合せてどのように使われるかを示すことにする。新しく導入する関数 は、名前と呼ばれる順序が、第7章で作成したコード生成用関数と同等である。新しいヘッダ ・ファイルsim.hでは、異なる命令コード表現が与えられているが、それ以外の点ではパー サに変更を加える必要はない。 プログラム・メモリと、その上に命令を追加するためのルーチンを定義することから始めよ う。アセンブラとまったく同様、コード生成部は固有のプログラム・カウンタpcを必要とす るが、このカウンタは次に使われるプログラム・メモリ位置を指す。最終的に、pcの値はpc- limitになってシミュレータに渡される。これはコード生成が完了した時点で、使用されるプ ログラム・セグメントの大きさを定めるためである。 #pre{{ #include "sim.h" #include "symtab.h" /* * program memory */ struct prog prog[L_PROG]; static int pc = 1; /* current program counter */ /* HALT (0) is at address 0 */ /* * generate a single instruction */ int gen(op, mod, val, comment) int op; /* operation code */ int mod; /* modifier */ int val; /* offset field */ char * comment; /* instruction comment */ { if (pc >= DIM(prog)) fatal("Not enough program memory."); prog[pc].p_op = op prog[pc].p_mod = mod; prog[pc].p_val = val; printf("%d:\t%d\t%d\t; %s\n", pc, op, mod, val, comment); return pc ++; } }} プログラム・カウンタは初期値1を与えられる。プログラム・メモリのアドレスOの値はOで ある。8.1節で述べたように、未定義関数やmain()がらのreturnが実行されるとアドレスO に制御が移行し、それによりシミュレータは停止する。 genOはプログラム・メモリに命令を置く唯一の関数である。この関数は、シミュレータの ためのコード生成をトレースするにはちょうどよい場所である。genOは、命令が生成された 時点でのプログラム・カウンタの値を返す。後で出てくるが、他のコード生成関数で、この関 数を必要とするものがある。ただし、それはパーサのアクションからのgen()の呼出しとは関係がない。 領域修飾部は前と同様に計算されるが、今回はgeしmod()が整数型として表現されている 点が異なる。 #pre{{ int gen_mod(symbol) struct symtab * symbol; { switch (symbol->s_blknum) { case 1: return MOD_GLOBAL; case 2: return MOD_PARAM; } return MOD_LOCAL; } }} gen()を用いてプログラム・メモリに書き込むことができるようになると、いくつかのコー ド生成ルーチンは簡単に作成できる。というのも、それらは呼出し列を変えただけで、同じ gen()を呼び出しているにすぎないからである。これらのルーチンはマクロとして定義するこ ともできる。 #pre{{ gen_alu(mod, comment) int mod; /* modifier */ char * comment; /* instruction comment */ { gen(OP_ALU mod, 0, comment); } gen_li(const) char * const; /* Constant value */ { gen(OP_LOAD, MOD_IMMED, atoi(const), const); } gen_pr(op, comment) int op; /* operaion code */ char * comment; /* instruction comment */ { gen(op, 0, 0, comment); } }} ここで、Constantは数値に変換し、メモリにストアしなければならない。この変換にはライ ブラリ関数atoiOを使う。したがって、定数は(少なくとも)この関数の満たすべきシンタッ クスを満足するものでなければならない。字句解析部の定数に関するパターンは二もっと制限 が強い。 前方参照をどのように扱うかは、インコア・コード生成における唯一の深刻な問題である。 典型的な例を見てみよう。 #pre{{ if_prefix : IF '(' expression rp { $$ = gen_jump(OP_JUMPZ, new_label(), "IF"); } statement : if_prefix statement { gen_label($1); } }} new_label()は必要な前方分岐の目標をマークし、その結果はgen_jump()に渡される。gen_ jump()から戻ってくる値が何であっても、それはyaccのスタックからgen_label()に引き渡 されるが、ここで必要な解消策がとられなければならない。すなわち、前方参照を現在のpc の値に分岐するように解決しなければならない。 gen_jump()が前方分岐を起こす場合、定義されていないアドレスヘの分岐を生成すること ができる。この前方分岐のプログラム・メモリ位置は、gen_jump()によって返され、gen_ label()に渡される。gen_label()は、現在のコード生成のプログラム・カウンタpcの値、す なわち生成されるべき次の命令のアドレスを、前方分岐のためのオフセット・フィールドに挿 入する。これで参照は解決される。 この技法は、一度だけ参照される前方のラベルに対してはうまくいく。通常の制御構造がそ うである。しかし、ある種のループのためのbreak文やcontinue文では、前方のラベルが複 数回参照されることがある。 明らかに、一般に同じ未定義ラベルに対するすべての参照は、gen_label()がまとめて解決 するように、チェーンにしておくべきである。前方分岐命令のオフセット・フィールドは、 gen_label()がこれを解決するまで使われないので、チェーンを作っておくにはよい場所であ る。チェーンはアドレスOを含むことはできない。もし含まれるなら、値Oにより動作が停止 する恐れがある。 break文やcontinue文を、チェーンにしておかなければならない前方分岐で扱ったらよい のか、直ちに解決することができる後方分岐で扱ったらよいのかは、コンテクストから知るこ とはできない。これら二つを区別するため、解決していない前方分岐のチェーンをプログラム ・メモリに対するインデックスを負にしてマークすることにする。 gen_jump()は前方分岐をチェーンにしておかなければならない。すなわち・メモリ位置を 負の値として返さなければならない。そうすれば、後方分岐の目標から戻る時に便利である。 #pre{{ int gen_jump(op, label, comment) int op; /* operation code */ int label; /* target of jump */ char * comment; /* instruction comment */ { int pc = gen(op, 0, label, comment); if (label <= 0) return -pc; /* new head of chain */ else return label; /* already defined */ } }} new_label()は、常に前方分岐のチェーンの最後をマークしている。すなわち、Oを返さな ければならない。 #pre{{ int new_label() { return 0; /* end of chain */ } }} この時点でのgen_label()は、解決しなければならないチェーンの処理だけを行えばよ い。後で出てくるが、gen_label()がcontinue文のコンテキスト処理中に呼ばれた場合、何も しないことがある。すなわち、引数を調べて値が負でなければ、解決しなければならないチェーンはない。 #pre{{ int gen_label(chain) int chain; { int next; while (chain < 0) { chain = - chain; next = prog[chain].p_val; if (next > 0) break; /* already ok */ prog[chain].p_val = pc; printf("%d:\t(fixup)\t%d\n", chain, pc); chain = next; } return; } }} gen_label()は、while文が正しく処理されるよう、生成されたラベルすなわちpcの値を返さなければならない。 #pre{{ loop_prefix : WHILE '(' { $$ = gen_label(new_label()); push_continue($$); } expression rp { $$ = $3 } statement : loop_prefix { $$ = gen_jump(OP_JUMPZ, new_label(), "WHILE"); push_break($$); } statement { gen_jump(OP_JUMP, $1, "repeat WHILE"); gen_label($2); pop_break(); pop_continue(); } }} break文と。ontime文の操作を理解するために、while文の処理を見てみよう。WHILEで は、継続点は新しいラベルとして定義される。すなわち、new_1abelOがこれをマークし、gen- labelOで解決する(この場合は何もしない)。そして定義されたアドレスを返し、continue スタックに積まれる。 #pre{{ push_continue(label) int label; { c_top = push(c_top, label); } }} Continue文によってスタックのトップが引き続き参照されると、そこには定義されたラベル があるので、その結果は後方分岐となり、解決する。 statementのloop-prefixに続き、ループ終端点への前方分岐が生成される。すなわち、 new_labe1(〕がチェーンの終わ`)をマークし、gen_jump()がそれをチェーンにし、メモリ上 の位置を(負の値として)返す。結果は、後で解決されるため、yaccのスタック、そして break文のbreakスタックに置かれる。 #pre{{ push_break(label) int label; { b_top = push(b_top, label); } }} break文は、breakスタックの先頭を参照する。そこには未解決ラベルがあり、したがってチ ェーンを作らなければならない。 while文に続き、(すでに定義されている)継続点$1への分岐が生成される。次に、終端点 $2がgen_label()の呼出しで定義される。ここへの前方分岐を行なうjumpzが前にコード化 されているから、そこで解決される。 breakスタックをポップする準備ができた。break文で生成された分岐は、gen_break()に よってスタックにチェーンが作られている場合に限って解決できる。 #pre{{ gen_break() { *top(&b_top) = gen_jump(OP_JUMP, *top(&b_top), "BREAK"); } }} チェーンは、スタック・トップから始まり、前方分岐により伸びていく。チェーンにもう一つ の前方分岐を結び付けなければならない。その位置はgen_jump()によって返され、それはス タック・トップと置きかわらなければならない。gen-jump()は、後方への(定義されている) 分岐目標を返すから・スタック・トップがすでに存在するラベルを参照するなら、それを変更 することはない。したがって、gen.continue()は同じように扱うことができる.つまり、分 岐が後方であろうと前方であろうと、両方の文は正しく処理される. #pre{{ gen_continue() { *top(&c_top) = gen_jump(OP_JUMP, *top(&c_top), "CONTINUE"); } }} しかしながら、問題が一つある。スタ・ソクが空の場合、スタ・ソク・トップの要素を割り当て ることができない。他のスタック操作のルーチンはシンボル・コード生成部から呼ばれている が、top()は空のスタックにダミー要素をプッシュできるように、スタック・ヘッダにアクセ スできる。 #pre{{ static int * top(stack) struct bc_stack ** stack; { if (! *stack) { error("no loop open"); *stack = push(*stack, 0); } return & (*stack) -> bc_label; } }} top()はスタック・トップのラベル・エントリヘのポインタを返す。そうすれば、スタック 表現に関する情報なしに、エントリを書き込むことができる。 breakスタックをポップする問題に戻ろう。ループの終端点への未定義分岐を解決する必要 がある。すなわち、pop-break()がgen」abelOを呼ばなければならない。 #pre{{ pop_break() { gen_label(*top(&b_top)); b_top = pop(b_top); } }} ここで、gen_label()は前方分岐を解決する役割を果たす。終端点で解決しなければならない 前方参照がある場合のみ、pop_break()が呼ばれる。 しかしながら、終端点への分岐のチェーンは、loop_prefixに続いて生成される一つの jumpzにたどり着くが、それはすでに解決されている。これで、すでに解決されているチェ ーンの上の分岐に到達したとき、gen_label()の、 #pre{{ if (next > 0) }} で、解決を行なうループを中止する必要がなぜあるのか説明がつく。 continueに対する関数も、breakめそれと同様に機能する。すなわち、continueスタック も同様にポップされる。ただし、この場合解決されるべき分岐は存在しない。 #pre{{ pop_continue() { gen_label(*top(&c_top)); c_top = pop(c_top); } }} 関数呼出しにも、同様な前方参照の問題がある。C言語においては、関数が定義される前に 呼び出されることがある。この場合、このcall命令が前方参照になる。関数が定義されると、 それのentry命令の場所を知る必要がある。これにより、引き続くこの関数の呼出しは直ちに 解決される。 この問題を解決するのによく使われる方法は、転送ベクトルである。すべての関数呼出し は、関数のアドレス・ベクトルを通して間接的に行なわれる。これは広域的にアクセスできる 場所に置かれ、既知となった開始点が入れられる。 ここで採用する方法はより効率的である。すなわち、すべての前方への呼出しをチェーンに まとめ、entry命令が生成されるとgen_label()を使ってこれを解決するというものである。 チェーンの先頭は、それが既知となったentry命令の場所と同様、その関数の記号テーブル・ エントリのs_offsetに保持される。これは初期値Oが与えられていて、適切なチェーンの終 端になっている。 #pre{{ gen_call(symbol, count) struct symtab * symbol; /* function */ int count; /* # of arguments */ { int pc; chk_parm(symbol, count); pc = gen(OP_CALL, count, symbol->s_offset, symbol->s_name); if (symbol->s_offset <= 0) symbol->s_offset = -pc; /* head of chain */ while (count-- > 0) gen_pr(OP_POP, "pop argument"); gen(OP_LOAD, MOD_GLOBAL, 0, "push result"); } }} get_entry()は、gen_label()を使ってどんな前方参照も解決し、関数の実際の開始アドレス をs-offsetに定義しなければならない。entry命令は新たな前方参照の問題を引き起こす。つ まり、ローカル・セグメントの大きさがわからなければならないが、これはentry命令が生成 される関数の先頭ではまだわかっていないのである。この場合もまた、未解決の命令アドレス を返し、それをyaccの値スタックに置いておいて、最終的には次に定義するfix_entry()関 数の中で調整することにする。 #pre{{ int gen_entry(symbol) struct symtab * symbol; /* function */ { symbol->s-offset = gen_label(symbol->s_offset); gen(OP_ENTRY, 0, 0, symbol->s_name); return symbol->s_offset; } fix_entry(symbol, label) struct symtab * symbol; /* function */ int lable; { extern int l_max; /* size of local region */ prog[label].p_val = l_max; printf("%d:\tentry\t%d\t; %s\n" labe, l_max, symbol->s_name); } }} コード生成は完成した。end_program()に達すると、生成されたプゴルラム・セグメント と広域涼気の大きさがわかり、記号テーブルの中の開始アドレスを探すことができる。この 情報を元に、シミュレータを呼び出すことができる。 #pre{{ end_program() { extern int g_offset; /* size of global region */ extern struct symtab * s_find(); int main = s_find("main") -> s_offset; all_program(); /* allocate global variables */ printf("%d:\tend=t%d,%d\n", pc, g_offset, main); simulate(pc, g_offset, main); } }} s_findで、main()の記号テーブル・エントリを見つけ出す。この関数が定義されていなければ 、s_offsetの値は0である。したがって、シミュレーションはアドレス０から開始され、 シミュレータは直ちに停止する。 コンパイル・エラーがあったときに、シミュレータを起動するかどうかを決定することは可能 である。関数error()が知らせるエラーを含め、コンパイル中のエラーの数は変数yynerrs にある。ここでは、実行中に何か問題が起きた場合には少なくとも停止できるように設計して いるので、どんな場合でもシミュレータを起動するようにしたい。 ** 例 [#s5b3cc7f] ユークリッドのアルゴリズムの再帰定義の例を考えてみよう。 #pre{{ /* * Euclid's algorithm (recursively) */ main() { gcd(36,54); } gcd(a,b) { if (a == b) return a; else if (a > b) return gcd(a-b, b); else return gcd(a, b-a); } }} このプログラムを実行すると、次のような結果が得られる。 #pre{{ 1: 10 0,0 ; main 2: 4 4,36 ; 36 3: 4 4,54 ; 54 4: 9 2,0 ; gcd 5: 6 0,0 ; pop argment 6: 6 0,0 ; pop argument 7: 4 1,0 ; push result 8: 6 0,0 ; clear stack 9: 11 0,0 ; end of function 1: entry 0 ; main 4: (fixup) 10 10: 10 0,0 ; gcd 11: 4 2,0 ; a 12: 4 2,1 ; b 13: 1 10,0 ; == 14 7 0,0 ; IF 15: 4 2.0 ; a 16: 5 1,0 ; save result 17: 11 0,0 ; RETURN 18: 8 0,0 ; past ELSE 14: (fixup) 19 19: 4 2,0 ; a 20: 4 2,1 ; b 21: 1 7,0 ; > 22 7 0,0 ; IF 23: 4 2,0 ; a 24: 4 2,1 ; b 25: 1 2,0 ; - 26: 4 2,1 ; b 27: 9 2,10 ; gcd 28: 6 0,0 ; pop argument 29: 6 0,0 ; pop argument 30: 4 1,0 ; push result 31: 5 1,0 ; save result 32: 11 0,0 ; RETURN 33: 8 0,0 ; past ELSE 22: (fixup) 34 34: 4 2,0 ; a 35: 4 2,1 ; b 36: 4 2,0 ; a 37: 1 2,0 ; - 38: 9 2,10 ; gcd 39: 6 0,0 ; pop argument 40: 6 0,0 ; pop argument 41: 4 1,0 ; push result 42: 5 1,0 ; save result 43: 11 0,0 ; RETURN 33 (fixup) 44 18: (fixup) 44 44 11 0,0 ; end of function 10: entry 0 ; gcd 45: end 1,1 Execution begins... 4: call 10 14 jummpz 19 22 jumpz 34 38 call 10 14: jumpz 19 27 call 10 16: store 1,0 to 18 17: return 18 to 28 31: store 1,0 to 18 32: return 18 to 39 42: store 1,0 to 18 43: return 18 to 5 9: return 18 to 0 0: halt }} この例は、後処理を行なえばコードを短くすることができる可能性があることをよく示して いる。たとえば・連なるreturn命令は、実際には最初の一つしか実行されないなどの点にお いてである。 ** 問題 [#m27ed32d] + シミュレータを改良し、returnの結果をスタックに渡すことにより、gen_callOから call命令に続くpopおよび1oad命令を割愛せよ。 + 先に述べたように、我々の仮想マシンの。a11、return、entry各命令はあまり現実的でな い。実際の計算機では、これらの命令はずっと単純なものである。より現実的な命令を設 許し、それを使ってコード生成部およびシミュレータを改造せよ。 ヒント:いくつかのレジスタ操作命令が必要になるであろう。 + コンパイラ・オプション、あるいは適切な擬似命令を生成する特別なコメントを用い て、シミュレータに実行時オプションを追加せよ。考えられるオプションには次のような ものがある、すなわち、実行開始前にコンパイルされたコードを印刷するか否かを指定; コンパイル・エラーの存在の有無、あるいはエラーの数または種類(通常のエラーである か警告であるか)によって、プログラムを実行するか否かを指定;シミュレーションを行な う命令の数の上限指定;トレースする命令の数あるいは種類を制限する機能などを含むよ り強力なトレース・オプション、などである。 + O除法のような算術演算例外を扱えるように、シミュレータを改良せよ。 + 本章の初めで定義した、調整可能ではあるが、固定した大きさの配列を用いずに、動的 管理されたメモリを扱えるよう、シミュレータを改造せよ。 + 本章の初めで定義した、デコーディンクを簡素化するためのプログラム・セグメントの 構造は、通常の計算機のアーキテクチャでは現実的ではなく、かといって特に簡潔なもの でもない。シミュレータのこの部分を、より効率的でかつ現実的なものにせよ。 ** 研究課題 [#h9242bda] + コンパイラを、次の三つの独立したプログラムとして再構成せよ。(1)第7章のコンパ イラ、これはアセンブラ・コードを生成する。(2)簡単なアセンブラ(アセンブラはもち ろんyaccおよびlexを用いて書ける)。(3)シミュレータ. + 上の課題の三つのプログラムを用いて、関数を分割コンパイルできるように、またその 結果をアセンブラあるいは独立したリンキング・ローダを用いてリンクできるように、コ ンパイラを再編せよ。どの関数をコンパイルする時も、広域変数が含まれている可能性が あり、それらは最終的な実行可能プログラムにすべて存在しなければならないことに注意 せよ。 + 言語拡張に関していろいろなことが考えられる。char型あるいは他の整数型の変数、 浮動小数点型変数、ポインタを伴うかあるいは伴わないベクトル、構造体、他の制御構 造、たとえばswitch文、for文、dowhile文などである。 + より興味深い言語拡張として、並列処理の導入がある。たとえば、Modula-2流のコル ーチン分岐のための標準手続き(すなわちシミュレータ命令)の導入、あるいはparalle1 制御構造の追加などである。この拡張をより現実的なものにするため、ベクトルを付け加 えるべきである。 ** コメント [#x9bba112] この記事は、 #vote(おもしろかった[3],そうでもない[0],わかりずらい[0]) 皆様のご意見、ご希望をお待ちしております。 #comment_kcaptcha 削除しました（removed）
