![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
[[FrontPage]] 2008/05/16からのアクセス回数 &counter; #contents * 第6章 メモリ割当て [#ne4a42c7] さて、sampleCの特定マシンに対するインプリメンテーションを定義する準備ができた。 我々はまず、メモリ割当てとコード生成のポリシーを決めなければならない。 言語認識の問題が、目的マシンに対する知識なしで解決できるということは興味深い。これ は、コンパイラ・コードの大部分が目的マシンやホスト・マシンから独立しているようにする という目的にかなっている。 これ以下の章では、特定のマシンの特色に合わせようとするのではなく、共通原理に重点を 置くことにする。したがって、ここではsampleCが必要とするものをすべて持つような、架空 のマシンに対するインプリメンテーションについて述べることにする。 ** 原理 [#b3d6f64b] メモリ割当てのポリシーとは、変数の表現方法、すなわち宣言のインプリメンテーションを 定義することである。すなわち、各データ型のオブジェクトに対し、どれくらいのメモリを割 り当てるかを決めなければならないし、そのオブジェクトにどのようにアドレスを付けるかも 決めなければならない。すなわち、オブジェクトの特定の寿命をサポートするため、プログラ ムの実行中にそれらをどこに置くか、というようなことを決めなければならない。 実行時メモリ割当ては、ある程度記号テーブル生成に影響する傾向がある。次のようなこと を考えてみよう。 - BASICでは広域変数のみが存在し、それらは広域記号テーブルに置かれる。インタプリタ は、同様にまた実行時に変数の値を保持している。ユーザ定義関数引数は、通常、式の評 価に使われるスタック上で扱われる。 - FORTRANでは、サブプログラムを再帰的に呼び出すことができない。局所変数の値は、 同じ関数に対する以降の呼出しまで保持されていなければならないので、各サブプログラ ムの各変数に対し、ユニークなメモリ・セルを割り当てなければならない。 - C言語やPascal、それにその他のAlgol系言語では、サブプログラムを再帰的に呼び出す ことができる。したがって、サブプログラムが呼び出されるたびに、それらの局所変数に 対して空間を動的に確保しなければならない。局所変数は通常、いったんサブプログラム が終了すると存在しなくなるので、それらの空間を解放し、再利用することができる。 Algol系言語の可視範囲の入れ子構造は、他にも問題を提起する。関数が定義中に入れ子にな ると、現在アクティベートされている関数の局所変数の中の選択された部分集合のみに対する 名前によるアクセスしかできなくなってしまう。 複合文の中で宣言された変数の寿命に対応する規則とともに、複合文の入れ子は、コンパイ ル時に管理できるようなメモリ再利用に関連する。複合文は、逐次的にのみ呼び出すことがで きる、名前のないサブプログラムとして捉えることができる。すなわち、コンパイラがそれら を眺めるのと同じ順序である。複合文には名前がないので、それ自身を再帰的に呼び出すこと はできない。したがって、コンパイラは複合文の中で定義されている局所変数の寿命の動きに 関するすべての情報を持っている。 スカラ型のデータを表現するのは一般に簡単である。これらは、通常計算機上の直接的表現 と、それに対する操作が存在するような特定のオブジェクトに対応している。PascalやC言語 に見られるような数え1二げデータ型は、稀な例外である。 構造体を表現するのはもっと困難である。言語要素としてのベクトルや配列は、コンパイル 時や実行時に行なわれるアドレス計算を必要としている。APLのような言語では、さらに精密 な動的メモリ管理が行なわれることも必要である。配列の大きさがPascalのように定数境界 を持つ場合や、少なくともFORTRANやC言語のようにディメンションを動的に変えられな いのであれば、比較的簡単である。このような場合、コンパイラが割当ての調整を行なうこと ができる。すなわち、アドレス割当てである。これにより、配列は非常に大きなスカラのオブ ジェクトと同じように見える。PL/Iのように配列が動的にディメンションを変えられる場合 は、割当ては実行時でなければできない。通常この時は、ポインタを通して操作する。 Pascalの定義で提案されているような、可変レコードがメモリに対する要求が変わるように 実際にインプリメントされていることを除いて、レコードや構造体は比較的実現することが容 易である。構成要素のアドレスは、その構造体の基点に対して相対的に割り当てられなければ ならないし、境界調整の問題も考慮されなければならない。それに従えば、構造体は全体とし て大きなスカラ・オブジェクトとして扱える。 ボーアによれば「一歩戻れば、元に戻れなくなる」ものであるポインタは、マシン・アドレ スで簡単に表現することができる。ポインタにまつわるトラブルは通常、特定のデータ型のオ ブジェクトをポイントするように制限される、というセマンディックス上のことの結果として 起こる。ポインタの使用方法はコンパイル時にチェックできるが、ポインタにストアされた値 (すなわちアドレス)の妥当性は、実行時でも監視するのは困難である。通常、言語定義にポイ ンタが含まれていることは、動的メモリ管埋が存在しなければならないことを意味している。 calloc()やnew()のような関数をサポートするのは簡単である一最初の見積りとして、一つ の配列の次の要素を扱うだけである一が、cfree()やdispose()などの明示的メモリ解放のた めの関数のことまで考慮すると、ポインタはもはや廉価な方法では検証できなくなってしまう。 さてそれでは、Cのような言語に対するメモリ割当ての本質的問題についてもっと詳しく考 えてみることにしよう。すなわち、データ型の表現方法、複合文の入れ子の中での割当てポリ シー、入れ子になって呼び出される関数に対する空間の動的割当てなどを決めなければならな い。 sampleCについての最初の決定は単純である。なぜならば、整数型の変数しかないからであ る。すなわち、各オブジェクトはコンピュータのメモリを1語を占めるだけということにする。 アドレッシングはもっと複雑である。なぜならば、広域的オブジェクトと局所的オブジェク トが存在し、関数が再帰的に呼び出されることがあるからである。さらに、パラメータの受渡 しに対して重要な寛大さがある。つまり、仮引数の数と実引数の数が一致していなくても良い が、実引数が渡された仮引数がアクセスされる限り、プログラムは正しく機能しなけれぱなら ないからである。 一般的解決方法としては、各関数に対する局所変数をアクティベーション・レコードに集め、 実行時には関数呼出しに対応して、それらレコードのスタックを管理することである。コード 生成を行なう時に広域変数を保持する広域アクティベーション・レコードを一つ作ることがで きる。実行時にはこのアクティベーション・レコードがスタックの最初のエントリになる。 コードをスタック・マシン用に生成するのであれば、アクティベーション・レコード、数式 の評価、およびサブプログラムヘの引数雫渡しにマシンのスタックを使うこともできる。 呼び出されようとしている関数の引数の値は、その関数に対するアクティベーション・レコ ードの確定に先立って、このスタックに遡慣に置かれるので、実行時におけるアクティベーシ ョン・レコードの先頭からの相対的オフセットは、コード生成の時に決めることができる。も ちろん、それらの数をコード生成時に決めることはできない。 引数の順序を変えるのは、コード生成の時に引数である式のために中間的領域を必要とする ので、多少複雑である。幸い、ここで扱っている架空の計算機は、基本的にパラメータ受渡し のためにアクティベーション・レコードを別に設けることができるようになっていることにす る。 変数は、ユニークなオフセットを割り当てられ、そのオフセットは後でコード生成フェーズ で使えるよう記号テーブルの中に置いておくことにより、アクティベーション・レコードに割 り当てられる。オフセットは、アクティベーション・レコードの先頭からの相対位置で定義さ れているので、実行時にアクセス可能なアクティベーション・レコードのべ一ス・アドレスが 得られるような手配が必要である。 Cのような言語に対しては、このようなべ一ス・アドレスを三つ用意するだけでよい。すなわ ち、広域的アクティベーション・レコード、パラメータ領域、そして現在の局所的アクティベ ーション・レコード用である。Algo1系言語では、関数定義が入れ子になることができるの で、多くのアクティベーション・レコードに対する同時アクセスが可能であり、また必要にな り、それに対するなんらかの手配をどこかに用意しなければならない。Algo1系言語のよう に、関数が実引数として受渡しできると、物事はもっと複雑になる。すなわち、ディスプレイ と呼ばれる、関数からアクセスすることができるアクティベーション・レコードのアドレスが、 引数となる関数の見えない部分として存在する。これが、Pascalにおいて関数呼出しが重い操 作になり、C言語ではそうならないという理由である。 関数呼出しが起こると、古いディスプレイは(スタック風に)保持されなければならず、これ により関数から戻ってくる時に回復することができる。ディスプレイは、本質的に関数からの リターン・アドレスの一部分になっている。C言語やsampleCに対しては、直前の局所的アク ティベーション・レコードのアドレスを保持しておくだけでよい。なぜならば、広域的アクテ ィベーション・レコードは常にアクセスできるからである。 他の多くの言語と同様、sampleCでは、名前の可視範囲と寿命を変更した、入れ子になった 複合文を定義することができる。このことによって、複数のアクティベーション・レコードを 実行時に管理しなければならないということにはならない。すなわち、コード生成を行なう時 に、関数全体に対して一つのアクティベーション・レコードを用意し、複数の複合文にまたが った局所的カウンタを一つ管理するだけである。 局所的オフセットに対するカウンタは、関数ヘッダが処理されるたびにゼロに初期化される。 さらに、このカウンタの最大値もまた管理される。複合文の先頭で、局所的オフセット・カウ ンタの現在の値をスタックにプ・ソシュする。カウンタの値は、各局所変数の定義で必要とされ ている分だけ増加される。複合文が完了すると、現在の局所的オフセットが、その時にはわか っている最大値と比較され、必要であれば新たな最大値が記憶される。そして、局所的オフセ ット・カウンタは、スタックからその時の複合文の先頭になるように回復される。このように して、同じ入れ子レベルにある二つの複合文で宣言されている変数は、(時間的には異なるが)同 じメモリ位置を占めることになる。 局所的アクティベーション・レコードの処理が完了すると、その大きさがわかるので、後で 必要量のメモリを動的に割り当て・るコードを生成することができる。 C言語では、広域的データ定義を関数定義と混在させることができるので、別の広域的オフ セット・カウンタを管理することにする。これは、適切な値で初期化され、各広域変数の定義 の時に増加される。 パラメータは、パラメータ・リストを認識処理している時にチェーンにされる。次にパラメ ータの宣言が集められる。異なるパラメータは、それらの定義に従って異なる大きさの空間を 必要とするかもしれない。一つの関数に対するパラメータ宣言がすべて処理されると、パラメ ータ・チェーンに従い、すべてのパラメータに対して同時に実際のオフセットの割当てを行な うことができる。この時、チェーンとパラメータ宣言の順序が、割り当てられるオフセットの 順序と量を決定する。 ** 例 [#p99cbeeb] 次の例は、同じレベルの複合文に対するアクティベーション・レコードのパーツに必要な再 割当てを示している。 #pre{{ /* * allocation demonstration -- specifically nested compounds */ main(p0, p1) { int main0, main1; { int nest2, next3, nest4; } { int new2; { int inner3; } { int inner3, inner4; } } { int last2; } } }} この関数に対しては、次のようなアクティペーション・レコードを定義しなければならない。 #ref(fig_6.2_1.jpg); この関数が処理されたときの、メモリ・アロケータからの出力は、次のようなものになる。 #pre{{ line 6 near "{": parameter region has 2 word(s) line 8 near "}": Popping nest4: variable, depth 4, offset 4 line 8 near "}": Popping nest3: variable, depth 4, offset 3 line 8 near "}": Popping nest2: variable, depth 4, offset 2 line 11 near "}": Popping inner3: variable, depth 5, offset 3 line 13 near "}": Popping inner4: variable, depth 5, offset 4 line 13 near "}": Popping inner3: variable, depth 5, offset 3 line 14 near "}": Popping new2: variable, depth 4, offset 2 line 16 near "}": Popping last2: variable, depth 4, offset 2 line 17 near "}": Popping main1: variable, depth 3, offset 1 line 17 near "}": Popping main0: variable, depth 3, offset 0 line 17 near "}": Popping p1: variable, depth 2, offset 1 line 17 near "}": Popping p0: variable, depth 2, offset 0 line 17 near "}": local region has 5 word(s) line 17 Popping main: function, depth 1, offset 0 line 17: global region has 1 word(s) }} この出力は、記号テーブル操作ルーチンの一部に組み込まれているトレースによって生成され たものである。オフセットは記号テーブルのs_offsetで定義され、その内容がトレースによっ て一表示されている。 メモリ割当てに必・要な動作について見てみよう。局所的ないし広域的アクティベーション・ レコード内のオフセットは、変数名がdeclarator」istに入ってきた時に割り当てられなければ ならない。 #pre{{ declarator_list : Identifier { all_var($1); } | declarator_list ',' Identifier { all_var($3); yyerrok; } | error | declarator_list error | declarator_list error Identifier { all_var($3); yyerrok; } | declarator_list ',' error }} このdeclarator listは、局所および広域宣言の一部として存在する。これら二つのケース は、Identifierが記号テーブル管理部によって処理されると、s_blknumにある入れ子レベルに よって区別することができる。したがって、記号テーブル・ルーチンmake_var()によってエン トリが調べられた後に、入れ子レベル2すなわちパラメータや、入れ子レベル1すなわち初期 化されていない記号テーブル・エントリがあってはならない。 #pre{{ int g_offset = 1, /* offset in global region */ l_offset = 0, /* offset in local region */ l_max; /* size of local region */ all_var(symbol) register struct symtab * symbol; { extern struct symtab * make_var(); symbol = make_var(symbol); /* if not in parameter region, assing suitable offset */ switch(symbol->s_blknum) { default: /* local region */ case 2: /* parameter region */ break; case 1: symbol->s_offset = g_offset++; break; case 0: bug("all_var"); } } }} 局所変数に対するオフセットは、局所オフセット・カウンタl_offsetによって決定され、広域 変数はg_offsetを通して割り当てられる。s_offsetにアクティベーション・レコードの先頭か らの適切なオフセットが代入されると、オフセット・カウンタは今定義されたオブジェクトの 大きさの分だけ増加されなければならない。ここではワード指向マシンを仮定しており、整数 変数しか扱わないので、いつでもオフセット・カウンタを1だけ増加することになる。 変数は、二つのコンテクストで定義される。すなわち、関数の外側でプログラム全体に広が っている広域変数と、各関数の中にある局所変数である。 広域的割当ては簡単なケースである。g_offsetは初期化された後、コンパイル中にカウント アップされるだけである。プログラム全体が認識されると、 #pre{{ program : { init(); } definitions { all_program(); } }} g_offsetに広域的アクティベーション・レコードの大きさが入っている。 #pre{{ all_program() { blk_pop(); #ifdf TRACE message("global region has %d word(s)", g_offset); #endif } }} 広域セグメントの最初のワードを、各関数の結果の値を返すために用いることにする。したが って、g_offsetは、1すなわちOではない値で初期化される。 局所的アクティベーション・レコードに対して入れ子になった複合文に沿って進むに従って・ スタックでl_offsetを管理しなければならない。 #pre{{ compound_statement : '{' { $<y_lab>$ = l_offset; blk_push(); } declarations statements rr { if (l_offset > l_max) l_max = l_offset; l_offset = $<y_lab>2; blk_pop(); } }} 埋込みアクションが$$に値を代入することにより、yaccのスタックに値をプッシュするこ とに注意しなさい。この値は。後で位置変数$2として取り出される。それはちょうど、そのア クションが記号であったかのように行なわれる。もし、値のスタックに型を付けるとすれば・ 埋込みアクションに対応するスタックの要素に対する参照に対しても・明示的に型を付けなけ ればならない。例では、これがスタック参照への適切な型情報を置くことによって行なわれて いることを示している。 この場合の型は新しいもので、ラベルとして扱う。したがって・値スタックを記述するunion に新しい要素を追加しなければならない。 #pre{{ %union { struct symtab * y_sym; /* Identifier */ char * y_str; /* Constant */ int y_num; /* count */ int y_lab; /* label */ }} compound_statementの処理が始まると、1_offsetは、局所的アクティベーション・レコード の中で、その。ompound_statementの最初の局所変数が割り当てられる場所を示している・一 番外側の。ompound_statementにおいて、これはl_offsetの初期値、すなわちゼロである。 この最初のオフセットは、yaccの値スタックにセーブされる。compomd-statement全体が 処理されると、l_offsetの値が回復され、アクティベーション・レコードの中の、compomd_ statementのために予約されていた領域を再利用することができる。 一つの関数のための局所的アクティベーション・レコードのエクステントを知りたいので、 l_offsetの上位水準点を監視しなければならない。局所的アクティベーション・レコードのエ クステント、l_maxは、その関数で入れ子になっているすべての複合文を通して、l_offsetが 到達できる最大値である。各関数の一番外側の複合文を処理し始める前に、l_maXをゼロに初 期化する。 #pre{{ function_definition : Identifier '(' { make_func($1); blk_push(); } optional_parameter_list rep parameter_declarations { chk_parm($1, parm_default($4)); all_parm($4); l_max = 0; } compound_statement { all_func($1); } }} 一つの関数の処理が終ると、l_maXに必要とする値がある。 #pre{{ all_func(symbol) register struct symtab * symbol; { blk_pop(); #ifdf TRACE message("local region has %d word(s)", l_max); #endif } }} 仮引数のオフセットは、parameter」istの中の引数の位置、および(もしあれば)引数の型に よって決められなければならない。したがって、parameter-listを処理している時に、直接的 にオフセットを割り当てることはできない。その代わり、parameter_declarationsが全部処理 され、残った未定義引数にデフォルト処理されると、引数に対する記号テーブル・エントリを つないだチェーンに従って、すべてのオフセットをまとめて計算することができる。 #pre{{ all_parm(symbol) register struct symtab * symbol; { register int p_offset = 0; while (symbol) { symbol->s_offset = p_offset ++; symbol = symbol->s_plist; } #ifdf TRACE message("parameter region has %d word(s)", p_offset); #endif } }} 一つの独立した引数セグメントの中でp-offsetをゼロから正のオフセットに増加させよう が、現在の局所的アクティベーション・レコードに先立ってゼロから負のオフセットに減少さ せようが、エントリがチェーンにされている順序は、実行時にどこから実引数の値をとってこ ようとしているかを定義する。 このインプリメンテーションでは、実引数の値を左から右ヘプッシュする。最初にプッシュ される引数のアドレスは、各関数の特別な引数セグメントのべ一ス・アドレスとして記憶され る。引数オフセットは、このべ一ス・アドレスからのオフセットとしてとられ、parameter-list の順序に従って左から右へと、ゼロから増加されなければならない。つまり、引数は左から右 ヘチェーンにし、チェーンをたどる時にp-offsetを数え上げなければならない。 まずいことに、これまでparameter_listを左再帰的に定義してきた。 #pre{{ parameter_list : Identifier { $$ = link_parm($1, 0); } | parameter_list ',' Identifier { $$ = link_parm($3, $1); yyerrok; } | error { $$ = 0; } | parameter_list error | parameter_list error Ideitifier { $$ = link_parm($3, $1); yyerrok; } | parameter_list ',' error }} しかしながらこれは、リストが左から右へ集められることを意味している。すなわち、この規 則によりチェーンは逆向きにつながるということである。 答えは白明である。すなわち、チェーンはIdentifierをparameter_listに変形する時に起こ る。単に、これが右から左へとしか起こらないということを確実にすれば良い。つまり、新た なIdentifierは、すでに存在しているparameter_listの前に追加する形でチェーンを作れば良 い。これは、まさに右再帰的定義を用いたケースである。 #pre{{ parameter_list : Identifier { $$ = link_parm($1, 0); } | Identifier ',' parameter_list { $$ = link_parm($1, $3); yyerrok; } | error { $$ = 0; } | error parameter_list | Ideitifier error parameter_list { $$ = link_parm($1, $3); yyerrok; } | error ',' parameter_list { $$ = $3; yyerrok; } }} このようにして、余計な努力なしに、いかに簡単に文法規則が変更できるかを味わってほしい。 どうして同じトリックが、実引数の値の計算順序をひっくり返すことに使えないのだろうか。 前章の例で、ソース・プログラムに誤りがある場合に、何が起こるかを見てみよう。 #pre{{ /* * symtab demonstration, including errors */ main(a,b) int a,b; { a=b; {a;b;} if (a==b) {a;b;} if (a==b+1) a; else b; while (a==b) {a; break;} return } int f() { int x; int y; return x+y;} f(a,b) /* 14: duplicate function definition */ int a; /* undeclared parm b (not an error) */ { int b,c; /* 16: symbol b duplicates parm b */ int c,d; /* 17: duplicate symbol c */ e=b; /* 18: undeclared e */ f=c+d; /* 19: use func for var */ a(b); /* 20: use var for func */ g(); /* 21: undefined function g */ } h(a,a) /* 23: duplicate parameter */ int f; /* 24: not a parameter */ int a; int a; /* 26: duplicate parameter */ { } }} メモリ・アロケータからの出力は次のようになる。 #pre{{ line 6 near "{": parameter region has 2 word(s) line 12 near "}": Popping b: variable, depth 2, offset 1 line 12 near "}": Popping a: variable, depth 2, offset 0 line 12 near "}": local region has 0 word(s) line 13 near "}": Popping y: variable, depth 3, offset 1 line 13 near "}": Popping x: variable, depth 3, offset 0 line 13 near "}": local region has 2 word(s) [error 1] line 14 near "(": duplicate function definition f [warning] line 16 near "{": function f should have 0 arguments(s) line 16 near "{": parameter region has 2 word(s) [error 2] line 16 near "b": duplicate name b [error 3] line 17 near "c": duplicate name c [error 4] line 18 near ";": undeclared variable e [error 5] line 19 near ";": function f used as variable [error 6] line 20 near "(": variable a used as function line 22 near "}": Popping e: variable, depth 3, offset 0 line 22 near "}": Popping d: variable, depth 3, offset 3 line 22 near "}": Popping c: variable, depth 3, offset 2 line 22 near "}": Popping c: variable, depth 3, offset 1 line 22 near "}": Popping b: variable, depth 3, offset 0 line 22 near "}": Popping b: variable, depth 2, offset 1 line 22 near "}": Popping a: variable, depth 2, offset 0 line 22 near "}": local region has 4 word(s) [error 7] line 23 near "a": duplicate parameter a [error 8] line 24 near "f": f is not a parameter [error 9] line 26 near "a": parameter a declared twice line 27 near "{": parameter region has 1 word(s) line 27 near "}": Popping f: variable, depth 2, offset 0 line 27 near "}": Popping a: variable, depth 2, offset 0 line 27 near "}": local region has 0 word(s) line 27 Popping h: function, depth 1, offset 0 line 27 Popping f: function, depth 1, offset 0 line 27 Popping main: function, depth 1, offset 0 line 27 Popping g: undefined function, depth 1, offset 0 [error 10] line 27: undefined function g line 27 : global region has 1 word(s) }} 未宣言変数にはオフセットが割り当てられず、重複している変数名がオフセット割当てに混 乱をもたらしていることに特に注意しなさい。原則的には、プログラムが誤りを含んでいる場 合、結果として得られるコードの正しさは保証されないが、コンパイラが、意外な場所や妥当 とは言えない方法で停止してしまわないように配慮しなければならない。 ** 問題 [#ade2e6e9] + このコンパイラの出力がアセンブラによって処理される、すなわちコンパイラがマシン ・コードではなく、アセンブラ・コードを発生するとする。広域変数を名前で割り当てる ためには、どのようなことが必要になるか。このようにした時に、コンパイルがどのよう に簡略になるか。 + sampleCが、ワードがアドレス付けできるメモリ位置を一つ以上占める(たとえば、1語 は独立してアドレス付けできる2バイトからなる)とする。メモリ割当てルーチンにどのよ うな変更を加えなければならないか。 + 多くの言語で、関数定義が入れ子になることができる。samp1eCの割当てアルゴリズム のどの部分を変更すれば、関数定義を入れ子にすることができるか。入れ子の外側の変数 は、内側の入れ・子になっている関数から(内側の関数で名前定義の衝突が起こらない限り) 広域変数としてアクセスすることができるということを念頭におけ。内部関数は、どのよ うにしてそのような変数を参照することができるか。 + 右再帰的定義を用いることにより、parameter」iStでの名前の受付け順序を逆にするの は簡単だった。では、argument-liStの定義を右再帰的に行なったらどうなるか。この場 合、右再帰的定義は使えないから、一つの関数呼出しに対し、引数がスタックに逆順にプ ッシュされるように調整するため、他にどのようなテクニックが使えるか。 ** コメント [#c6a074d8] この記事は、 #vote(おもしろかった[1],そうでもない[0],わかりずらい[0]) 皆様のご意見、ご希望をお待ちしております。 #comment_kcaptcha 削除しました（removed）
