スタック変数

現状のKLICでは、複数のボディ・ゴールを有するクローズの実行時に、2番目以降の ゴールに対してゴールレコードと呼ぶ構造をヒープに生成する。 ゴールレコードには、対応する述語が何かを示す情報と、ゴール引 数が格納される。 例えば、リストに示すようなプログラムでは、 図1のように二つのゴールレコードが生成される。 また代表的なProlog処理系であるWAM[3]における局所変数に相当する変数、 すなわち上記の例のL1とL2は、ゴールレコード中に割付けられる。

		    リスト1quick sortの一部

		qsort([X|L],R,R0) :- true |
		          partition(L,X,L1,L2),
		          qsort(L2,R1,R0),
		          qsort(L1,R,[X|R1]).

一方、我々のこれまでの研究で用いた方式では、ゴールレコードに相当する構造をス タックに生成するが、局所変数はヒープに割付けられ、スタック上のゴールレコード には変数へのポインタが格納される[1,2]。 その結果、たとえば上記のL2の値を第2ゴールが参照する際に、1段の余分な デレファレンスが必要となる。

そこで本研究では、余分なデレファレンスが生じないように、局所変数をスタックに 割付けることとした。 また、この スタック変数の導入によって、

• ヒープ消費量が減少し、GC回数が少なくなる。
• 参照局所性が向上する。

スタック変数は、それを参照する最後のゴールが呼び出される時点でスタックから除 去されるので、以下の条件を満たすようにしなければならない。

1. スタック中に存在するスタック変数へのポインタは、 「祖先側」を指す。
   問題となるのは未定義スタック変数間の単一化であり、WAMでは両者のアドレス 比較によりこの条件を満たすようにしている。 しかし我々の処理系ではスタック領域の動的拡張を行なうため、変数の世代と アドレスの間に一定の大小関係が成立しない。 そこで、未定義スタック変数間の単一化では、新しい未定義ヒープ変数を生成 し、両スタック変数がそのヒープ変数を指すようにする「大域化」を行なう。
2. ヒープにはスタック変数へのポインタは存在しない。
   未定義変数間の単一化では、 アドレス比較によりヒープ／スタック変数の区別が可能であるので、条件を満 たすようにすることができる。 また生成される構造体に含まれる変数については、ヘッド引数の場合は動的大 域化を行ない、それ以外の場合は静的に大域化するか、あるいは静的解析によ り未定義スタック変数でないことを保証する。
3. スレッドの実行環境には、他のスレッドのスタック変数へのポインタは存 在しない。
   スレッド間共有変数を静的大域化することで解決できる。
4. スタック変数を除去して引数レジスタに移すとき、変数は未定 義ではない。
   静的解析により、未定義スタック変数でないことが保証される。