(57)【要約】【課題】  参照で連結されたデータ構造群について、参照経由でデータ構造をたどる処理に対してプリフェッチを適用し、たどる処理の高速化を実現する。【解決手段】  リンクを順次たどる処理のうち、頻繁に実行されるものを、プロファイラ８０６を使って求め、求めたリンクを順次たどる処理をコンパイルする際に、リンクをたどる過程で参照する一連のデータ構造の配置順序を決める配置図８１１を定め、実行時にデータ構造が配置図８１１の通りに並ぶものと想定してプリフェッチ命令を挿入する。プリフェッチ命令を挿入した機械コード８０９を生成したら、生成した機械コード８０９を実行する際に、ごみ集め８１２を実行する過程で、データ構造の配置を、配置図８１１の通りに詰めなおす。【選択図】      図１
2007041853.tif 000002
【特許請求の範囲】
【請求項１】
プログラムを格納する記憶部と、処理部とを含んで構成される言語処理装置であって、
前記処理部は、
前記記憶部の前記プログラム中の機械コードに基づいて、高速化すべき参照列を探し出し、
前記探し出した参照列の中で最初に参照するデータ構造の先頭アドレスから、前記参照列をたどる過程で参照するデータ構造内のメンバ変数のアドレスまでの各オフセットを格納する配置図を作成し、
前記参照列の中で最初に参照するデータ構造の先頭アドレスを指定する参照の値と、前記メンバ変数のアドレスまでのオフセットとの和に相当するアドレスを算出し、当該算出したアドレスによって指定された値をプリフェッチする命令を含んだ機械コードを作成し、
前記作成した配置図に従って、前記参照列をたどる過程で参照するデータ構造の詰めなおしを行い、前記参照の値を前記参照列の中で最初に参照するデータ構造の移動先のアドレスに更新し、
前記詰めなおしたデータ構造を用いて、前記作成した機械コードを実行する
ことを特徴とする言語処理装置。
【請求項２】
プログラムを格納する記憶部と、処理部とを含んで構成されるコンピュータにより実行される言語処理方法であって、
前記処理部は、
前記記憶部の前記プログラム中の機械コードに基づいて、高速化すべき参照列を探し出し、
前記探し出した参照列の中で最初に参照するデータ構造の先頭アドレスから、前記参照列をたどる過程で参照するデータ構造内のメンバ変数のアドレスまでの各オフセットを格納する配置図を作成し、
前記参照列の中で最初に参照するデータ構造の先頭アドレスを指定する参照の値と、前記メンバ変数のアドレスまでのオフセットとの和に相当するアドレスを算出し、当該算出したアドレスによって指定された値をプリフェッチする命令を含んだ機械コードを作成し、
前記作成した配置図に従って、前記参照列をたどる過程で参照するデータ構造の詰めなおしを行い、前記参照の値を前記参照列の中で最初に参照するデータ構造の移動先のアドレスに更新し、
前記詰めなおしたデータ構造を用いて、前記作成した機械コードを実行する
ことを特徴とする言語処理方法。
【請求項３】
請求項２に記載の言語処理方法をコンピュータに実行させるための言語処理プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、プリフェッチ命令を機械コードに挿入する言語処理装置、言語処理方法および言語処理プログラムに関する。
【背景技術】
【０００２】
コンピュータの構成要素に、プロセッサと主記憶がある。近年、プロセッサの動作速度が大きく向上しているが、その一方で、主記憶を構成するメモリの動作速度は、プロセッサほど大きく向上していない。この結果として、プロセッサが主記憶からのデータの転送待ちで動作を一時停止せざるをえないケースが頻発し、プロセッサの処理能力を十分に活用できなくなっている。
【０００３】
この問題を回避する手段として、プリフェッチ命令が考案されている。プリフェッチ命令の役割は、プロセッサが計算に使う主記憶装置（主記憶ともいう）の内容を、計算に使うよりも前に、あらかじめキャッシュメモリに転送しておくことにある。キャッシュメモリとは、主記憶よりも高速で、小容量な記憶装置であり、主記憶に記録されているデータの一部の複写を保持する役割を果たす。プロセッサはメモリ参照をおこなう際に、まずキャッシュメモリを探索して求めるデータがあるか調べ、あればキャッシュメモリの内容を参照し、なければ主記憶を参照する。こうすることで、キャッシュメモリにデータがあった場合には、高速にデータを参照可能になる。プリフェッチ命令を使って、プロセッサが計算に必要とする主記憶の内容を、あらかじめキャッシュメモリに転送しておけば、プロセッサが主記憶からのデータの転送待ちで一時停止することがなくなり、プロセッサの処理効率が向上する。
【０００４】
プリフェッチ命令を使ってプロセッサの処理効率を改善するには、コンパイラでソースプログラムを機械コードに変換する際に、機械コードの中にプリフェッチ命令を挿入しておく必要がある。具体的には、データを参照する命令の前に、該データをキャッシュメモリに転送するためのプリフェッチ命令を挿入する。このときプリフェッチ命令の挿入先は、データを読み込む命令の直前ではなく、数百命令程度前である必要がある。なぜなら主記憶からキャッシュメモリへのデータの転送にはある程度の時間が必要であるため、データを読み込む命令の直前でプリフェッチ命令を実行しても、データの転送が間に合わず、プロセッサがデータの転送待ちで一時停止してしまうからである。
【０００５】
プリフェッチ命令を、実際にデータを読み込む命令より数百命令前に配置するためには、プリフェッチ対象の主記憶のアドレス、つまり実際にデータを読み込む命令が参照する主記憶のアドレスが、プリフェッチ命令を配置する場所、つまり、実際にデータを読み込む命令よりも数百命令前の時点で判明している必要がある。さもないと、プリフェッチすべきアドレスが判らないことから、プリフェッチ命令の挿入が困難になる。
【０００６】
プリフェッチ対象の主記憶のアドレスを、実際にデータを読み込む命令よりも数百命令前に把握することは、必ずしも容易でない。特に、参照で連結されたデータ構造を順次たどる処理について、たどる処理において参照するデータ構造の内容をプリフェッチするのは難しい。なぜなら参照で連結されたデータ構造をたどる処理では、次にたどるデータ構造の内容を参照するまで、次の次にたどるデータ構造のアドレスが判らないことから、プリフェッチ処理に必要な数百命令の間隔を確保できない場合が多いからである。
【０００７】
例えば、図１６に示すデータ構造群のように、従業員型のデータ構造が、メンバ変数NAMEを通じて名前型のデータ構造を参照し、名前型のデータ構造がメンバ変数LASTを通じて文字列型のデータ構造を参照する場合について考える。図１６のデータ構造群について、プリフェッチ命令を使った高速化によって、従業員型のデータ構造を参照する変数WORKERを起点として参照をたどる処理WORKER→NAME→LASTを高速化するには、メンバ変数NAMEおよびLASTの参照に先立って、それぞれの内容をプリフェッチする命令を挿入する必要がある。ここで、メンバ変数NAMEのプリフェッチは必ずしも困難でないが、メンバ変数LASTのプリフェッチは容易でない。メンバ変数NAMEのプリフェッチが必ずしも困難でないとした理由は、メンバ変数NAMEのアドレスが変数WORKERの内容に依存するので、メンバ変数NAMEへの参照が発生するよりも数百命令前の、プリフェッチ命令を挿入すべき箇所までに変数WORKERの内容が定まっていれば、メンバ変数NAMEの内容をプリフェッチすることができるからである。メンバ変数LASTのプリフェッチが容易でないとした理由は、メンバ変数LASTのアドレスが、メンバ変数NAMEの内容に依存するのに対し、参照をたどる処理WORKER→NAME→LASTの機械命令列では、図１７に示すように、メンバ変数NAMEの内容を読み込んだ直後の命令でメンバ変数LASTを参照するので、メンバ変数NAMEの内容を読み込んでから、メンバ変数LASTを参照するまでの間に、プリフェッチ処理の実施に必要な数百命令の間隔を確保することが困難だからである。
【０００８】
プリフェッチ命令を使った高速化を、参照で連結されたデータ構造を順次たどる処理に適用しにくいという問題の解決を目的として、非特許文献１では、Java（登録商標）のようにごみ集めでメモリ管理を実施する言語処理系において、ごみ集めにおいて詰めなおしという処理をおこなった結果として、データ構造の配置にある程度の規則性が生じることを利用して、プリフェッチ命令を挿入する方法を提案している。非特許文献１の方法によれば、参照をたどる処理WORKER→NAME→LASTにおいて、メンバ変数LASTのアドレスを、変数WORKERの値から推測するので、メンバ変数NAMEの内容の読み込みを待つことなく、メンバ変数LASTのプリフェッチが可能になる。
【０００９】
非特許文献１が利用する「ごみ集め」とは、メモリ領域中に存在するデータ構造を、今後プログラムの実行中に参照しうる（生きている）ものと、参照しえないもの（ごみ）に分類し、後者が占有しているメモリ領域を解放して空き領域とし、再利用可能にする処理である。また、ごみ集めにおける詰めなおしとは、ごみ集めの結果として生じる空き領域を、連続した記憶領域にするために、生きているデータ構造を移動する処理のことである。
【００１０】
ごみ集めの実装方法の１つである、複写式ごみ集め（非特許文献２）を例にとって、ごみ集めと詰めなおしの処理について具体的に説明する。複写式ごみ集めでは、管理対象のメモリ領域を２等分し、片方をfrom領域と呼び、もう片方をto領域と呼ぶ。プログラムの実行時にメモリ割付の要求が発生した場合には、from領域に端から順に割り付けてゆく（図１８参照）。そして、図１９にあるように、from領域を使い切ったら、ごみ集めを開始する。具体的には、まず、ルートと呼ぶ参照が指示するデータ構造をto領域に詰め込みながら複写してゆく。ここでルートとは、管理領域内のデータ構造を指示する参照のうち、実行時スタックなど、管理領域外に存在するものを指す。図１９では実行時スタックに、from領域のデータ構造を指示する参照が１つあるので、この参照が指示するデータ構造をto領域に複写する。複写が済んだら、複写元のデータ構造への参照（ここでは実行時スタック内の参照）を更新して、複写先のデータ構造を指示させる。
【００１１】
複写が終わった時点の状態を図２０に示す。複写が終わり、図２０の状態になったら次に、to領域に複写したデータ構造を順に走査して、その内部にあるメンバ変数を順に調べ、メンバ変数が参照を保持する場合には、参照が指示するデータ構造をto領域に複写する。to領域に複写した全データ構造の走査が終了した時点で、生きているデータ構造は全てto領域に複写されているので（図２１参照）、from領域全体を冗長な記憶領域とみなしてまとめて解放する。一方でto領域には生きているデータ構造が連続して存在し、空き領域が１つの大きなかたまりになっている状態、つまり詰めなおしが済んだ状態になっている。from領域の解放が済んだら、to領域とfrom領域の役割を入れ替える（図２２参照）。これでごみ集めは終了したので、プログラムの実行に戻る。
【００１２】
非特許文献１が指摘した、データ構造の配置の規則性は、ごみ集めにおける詰めなおしの際に生じる。例えば図１８〜２２を使って説明した複写式ごみ集めによって、図１６の変数WORKERが指示するデータ構造をto領域に複写すると、まず従業員型のデータ構造が複写され、続いて複写した従業員型のデータ構造の走査によって、住所型のデータ構造が複写され（IDは整数型、つまり非参照型なので複写の対象にならない）、名前型のデータ構造が複写される。結果としてto領域にはデータ構造が従業員型、住所型、名前型の順に並ぶという規則性が生まれる。
【００１３】
このような規則性がある状況下では、参照で連結されたデータ構造をたどる処理にプリフェッチ命令を挿入して、処理の高速化を図ることが可能になる。例えば図１７のコードについて、従業員型のデータ構造に続いて住所型、名前型のデータ構造が存在すると判っていれば、変数WORKERの値、つまり従業員型のデータ構造のアドレスから、名前型のデータ構造内のメンバ変数LASTのアドレスを予測することが可能であり（具体的には、メンバ変数LASTのアドレスを、「WORKER + 従業員型のデータ構造のサイズ + 住所型のデータ構造のサイズ + LAST＿OFFSET」と予測できる。ここでLAST＿OFFSETは名前型のデータ構造の先頭から、その内部にあるメンバ変数LASTまでのオフセットである。）、図１７の２行目より前に、予測したアドレスに対するプリフェッチ命令を挿入することで、３行目のメモリ参照を高速化できる。
【非特許文献１】A.-R. Adl-Tabatabai, R. L. Hudson, M. J. Serrano, S. Subramoney, Prefetch injection based on hardware monitoring and object metadata, In Proceedings of the 2004 ACM SIGPLAN Conferences on Programming Language Design and Implementation, pp.267-276, 2004.
【非特許文献２】C. J. Cheney, A nonrecursive list compacting algorithm, Communication of the ACM, Vol. 13, No. 11, pp.677-678, 1970.
【発明の開示】
【発明が解決しようとする課題】
【００１４】
従来のごみ集めの詰めなおし処理は、生きているデータ構造を連続領域に詰めこむことで、空き領域を大きな連続領域にすることを目的とした処理であり、詰めなおしによって配置に規則性をもたせるための処理ではない。このため、従来の詰めなおし処理から得られる配置の規則性には改善の余地がある。例えば図１６の従業員型のデータ構造に、複写式ごみ集めにおける詰めなおし処理を適用した結果として生じるデータ構造の配置について考察する。従業員型のデータ構造のメンバ変数ADDRESS、NAMEがそれぞれ住所型と名前型のデータ構造を参照する場合には、詰めなおしの結果として、データ構造が従業員型、住所型、名前型の順に並ぶが、メンバ変数ADDRESSの内容が空（null）である場合（図１３に示すような場合）には、詰めなおし処理において住所型のデータ構造が複写されないので、データ構造の並びが従業員型、名前型になってしまう。つまり、従来の詰めなおし処理では、同じ従業員型のデータ構造を詰めなおした場合であっても、その内容によって、詰めなおしの結果として生じるデータ構造の並びが変化しうる。このように配置が一定にならない状況下では、プリフェッチ命令の有効性が十分にならない。
【課題を解決するための手段】
【００１５】
本発明は、前記課題を解決するために創案されたものであり、本発明の言語処理装置は、プログラムを格納する記憶部と、処理部とを含んで構成され、前記処理部が、前記記憶部の前記プログラム中の機械コードに基づいて、高速化すべき参照列を探し出し、前記探し出した参照列の中で最初に参照するデータ構造の先頭アドレスから、前記参照列をたどる過程で参照するデータ構造内のメンバ変数のアドレスまでの各オフセットを格納する配置図を作成し、前記参照列の中で最初に参照するデータ構造の先頭アドレスを指定する参照の値と、前記メンバ変数のアドレスまでのオフセットとの和に相当するアドレスを算出し、当該算出したアドレスによって指定された値をプリフェッチする命令を含んだ機械コードを作成し、前記作成した配置図に従って、前記参照列をたどる過程で参照するデータ構造の詰めなおしを行い、前記参照の値を前記参照列の中で最初に参照するデータ構造の移動先のアドレスに更新し、前記詰めなおしたデータ構造を用いて、前記作成した機械コードを実行することを特徴とした。
【００１６】
このような構成によれば、参照列をたどる過程で参照されるデータ構造のメンバ変数のアドレスを予測することが可能となり、予測したアドレスで指定された値をプリフェッチすることで、プログラムの実行を高速化することが可能となる。ここで、参照列とは、参照で連結されたデータ構造を順次たどる過程で生じる一連のメモリ参照からなる列である。例えば、データ構造をたどる列WORKER→NAME→LASTは、２つの参照「WORKER→NAME」、「NAME→LAST」からなる参照列である。
【発明の効果】
【００１７】
本発明によれば、プログラムの実行を高速化することが可能となる。
【発明を実施するための最良の形態】
【００１８】
以下、本発明の実施例について、図１から図１５に基づいて説明する。
まず、本実施例における言語処理系の概要を説明する。
３つの要素、すなわち、（１）プロファイラ、（２）本発明を適用したコンパイラ、（３）本発明を適用したごみ集めの機能を有する実行時システム、からなる言語処理系において、まず、プロファイラを用いて、高速化すべき参照列の集合を求め、求めた集合（＝参照列群）を本発明のコンパイラに引き渡す。コンパイラは引き渡された参照列群を元に、プリフェッチ命令を含む機械コードと、該機械コードの生成にあたって想定したデータ構造群の配置図を生成し、実行時システムに引き渡す。実行時システムは受け取った機械コードを使ってプログラムの実行をおこない、その過程でごみ集めをおこなうときに、受け取った配置図に従って詰めなおし処理をおこなう。
【００１９】
本発明の言語処理系が動作するコンピュータシステム（言語処理装置）の構成例を図１に示す。図１のコンピュータシステムは、ハードディスク８０１、バス８０２、主記憶（記憶部）８０３およびプロセッサ（処理部）８０４からなり、プロセッサ８０４は、ハードディスク８０１にインストールされた本発明の言語処理系８０５を、バス８０２を介して主記憶８０３に読み込み、実行する。
【００２０】
言語処理系８０５は、プロファイラ８０６、コンパイラ８０７および実行時システム８０８からなり、プロファイラ８０６は、機械コード８０９の実行を監視して、機械コード８０９が含む参照列の中から、本発明の最適化によって高速化すべき対象を探し出す役割を果たす。
コンパイラ８０７は、ソースコード８１０を入力として受け取り、機械コード８０９を出力する役割を果たす。また、コンパイラ８０７は、本発明のプリフェッチを挿入する最適化機能を備える。この機能により、プロファイラ８０６が求めた高速化すべき参照列の集合を入力として受け取って動作し、参照列が参照するデータ構造の配置図８１１を決定して、機械コード８０９と共に出力する。また、配置図８１１に従って、機械コード８０９が含む参照列を高速化するためのプリフェッチ命令を挿入する。
実行時システム８０８は、コンパイラ８０７が生成した機械コード８０９を実行する過程で呼び出され、実行に必要なサービス（ごみ集め８１２などによるサービス）を提供する役割を果たす。ごみ集め８１２は、詰めなおしをおこなう際に配置図８１１を参照し、データ構造の配置を調整することで、機械コード８０９が含むプリフェッチ命令を有効に機能させる役割を果たす。
【００２１】
プロファイラ８０６が高速化すべき参照列の集合を求める具体的な方法としては、非特許文献１にあるように、キャッシュミスを頻発する参照命令を検出し、該命令を含む参照列を求める手法などがある。本実施例では、プロファイラ８０６が求めた高速化すべき参照列の集合の中身が、図１６のデータ構造に関する２つの参照列「WORKER→NAME→LAST」と「WORKER→ADDRESS→ZIPCODE」であったと仮定し、これらの参照列を高速化するために、本発明のコンパイラ８０７およびごみ集め８１２が、どのように動くかを説明する。
【００２２】
本発明のコンパイラ８０７の機能例を図２に示す。図２のコンパイラ８０７は、ソースコード８１０を入力として受け取り、処理９０１でソースコード８１０を中間表現９０２に変換し、続く処理９０３で中間表現９０２に最適化処理を適用し、最後に処理９０４で、中間表現９０２を機械コード８０９に変換して、出力する。ここで出力した機械コード８０９を実行して、その実行の様子をプロファイラ８０６で監視すると、機械コード８０９（プログラムコード）が含む参照列のうち、プロファイラ８０６で高速化すべきものの集合（参照列群９０５）が求められる。求めた参照列群９０５を使って、コンパイラ８０７でソースコード８１０を再コンパイルすると、最適化処理９０３が含む本発明の最適化処理９０６においてプリフェッチ命令の挿入がおこなわれ、また、配置図８１１が生成される。配置図８１１は、機械コード８０９が実行時システム８０８のごみ集め８１２を呼び出すときに、引数として渡される。ごみ集め８１２は引数として受け取った配置図８１１を参照しつつ詰めなおし処理をおこない、処理９０６で挿入したプリフェッチ命令が有効に動作するよう、データ構造の配置を調整する。
【００２３】
本発明の処理９０６の処理例を図３に示す。ここで、処理９０６とは、コンパイラ８０７によるプリフェッチ命令挿入処理を意味する。図３では、まず処理１００１で高速化すべき参照列群を、最初に参照するデータ構造の型によって分類する。高速化すべき参照列群の要素が「WORKER→NAME→LAST」と「WORKER→ADDRESS→ZIPCODE」である場合には、これらの参照列が最初に参照するデータ構造の型が、共に従業員型であることから、処理１００１における分類の結果として、１つの集合Swができあがる。できあがった集合Swは参照列「WORKER→NAME→LAST」と「WORKER→ADDRESS→ZIPCODE」を含む。
【００２４】
続く処理１００２では、処理１００１で得られた集合の集合をSとおく。ここではできあがった集合がSwのみなので、SはSwのみを要素として持つ集合になる。処理１００２に続く判断１００３では、集合Sが空集合φか否かを判定する。ここでは集合Sが空集合φでないので（判断１００３のＮｏ）、処理１００４に進む。処理１００４では、集合Sから要素を一つ取り出して、集合Stとおく。ここでは、集合St = 集合Swになる。
続く処理１００５では、後記する図４の配置図８１１の作成をおこなう。処理１００５で作成する配置図８１１は、集合Stが含む参照列が参照しうる全データ構造を格納できるものである。ここでは集合St（=集合Sw）が参照しうるデータ構造は、次に示す（１）〜（３）の３つである。（１）変数WORKERが参照する従業員型のデータ構造、（２）従業員型のデータ構造のメンバ変数ADDRESSが指示する住所型のデータ構造、（３）従業員型のデータ構造のメンバ変数NAMEが参照する名前型のデータ構造。そこで、処理１００５では、これら３つのデータ構造を格納できる配置図８１１を作成する。配置図８１１を作成する処理１００５の処理例については後記するものとし、先に処理１００５が作成する配置図８１１の構成例について説明する。
【００２５】
図３の処理１００５で作成される配置図８１１の構成例を図４に示す。ここで、処理１００５とは、コンパイラ８０７による配置図８１１の作成処理を意味する。図４の配置図８１１は、従業員型のデータ構造と、住所型のデータ構造と、名前型のデータ構造とを含んで構成されているが、ごみ集め８１２の詰めなおし処理により、図５に示す順序に配置されることとなる。図４の配置図８１１は、データ構造の配置を表形式で表しており、次に示す（１）〜（６）の６つのフィールドを持つ。（１）最初に参照するデータ構造の型を記録するフィールド１１０１、（２）配置するデータ構造の型名を記録するフィールド１１０２、（３）データ構造が保持するメンバ変数名を記録するフィールド１１０３、（４）データ構造が保持するメンバ変数の参照先を記録するフィールド１１０４、（５）データ構造が保持するメンバ変数の、先頭からのオフセットを記録するフィールド１１０５、（６）配置図が含む全データ構造のサイズの総和を記録するフィールド１１０６。
【００２６】
図４では、配置するデータ構造の型名を記録するフィールド１１０２の１番目には、暗黙に、最初に参照するデータ構造の型名を記録するものとし、本実施例においては、例えば、最初に参照するデータ構造の１番目のメンバ変数のオフセットを０にする。ここでは、最初に参照するデータ構造の型が従業員型であることから、図４において、最初に参照するデータ構造の型を記録するフィールド１１０１の値と、配置するデータ構造の型名を記録するフィールド１１０２の１番目のフィールドの値が「従業員型」になっている。また、従業員型のデータ構造の最初のメンバ変数（ヘッダ）のオフセットが０になっている。図４の配置図８１１において、データ構造が保持するメンバ変数の参照先を記録するフィールド１１０４には、もしメンバ変数が参照するデータ構造が配置図８１１の中にあれば、その先頭オフセットを記入し、なければ、例えば−１を記入する。整数型のメンバ変数のように、そもそも参照を含み得ないメンバ変数についても、−１を記入する。図４においては、従業員型のデータ構造のメンバ変数ADDRESSおよびNAMEが参照するデータ構造が配置図８１１の中に存在することから、メンバ変数ADDRESSおよびNAMEに対応するフィールド１１０４に、それぞれ値１６と２８が記録してある。その他のメンバ変数に対応するフィールド１１０４の値はいずれも−１になっている。例えば、名前型のデータ構造のメンバ変数LASTが指示する文字列は、図４の配置図８１１の中にないので、メンバ変数LASTに対応するフィールド１１０４の値は−１になっている。
【００２７】
図４の配置図８１１を作成する、処理１００５（図３参照）の処理例を図６に示す。図６では、まず処理１３０１で配置図８１１の最初に参照するデータ構造の型を記録するフィールド１１０１に、集合St中の参照列が最初に参照するデータ構造の型tを書き込む。ここでは集合Stが含む参照列が「WORKER→NAME→LAST」と「WORKER→ADDRESS→ZIPCODE」であることから、変数WORKERが指示するデータ構造の型名「従業員型」をフィールド１１０１に書き込む。この結果、配置図８１１のフィールド１１０１に「従業員型」と記載される。
【００２８】
続いて処理１３０２に進み、データ構造のオフセットoを０とおき、判断１３０３に進んで集合Stが空集合φか否かを検査する。ここでは空集合φでないことから（判断１３０３のＮｏ）、処理１３０４に進み、集合Stが含む参照列の１つを取り出してrとし、参照列rが含む最初の参照をpとおく。また、参照pで参照するデータ構造の型をdtとおく。ここでは参照列「WORKER→ADDRESS→ZIPCODE」をrとし、参照列「WORKER→ADDRESS→ZIPCODE」が含む最初の参照「WORKER→ADDRESS」をpとおく。なお、参照pとしては、例えば、「WORKER→ADDRESS」や、「ADDRESS→ZIPCODE」などの場所を示す値を、コンパイラの内部表現として保持する変数が考えられる。また、参照列rとしては、例えば、参照pをリストや配列状にしたものが考えられる。
続く処理１３０５では変数zの値を設定する。変数zの役割は参照pの直前の参照が参照するメンバ変数に対応する、配置図８１１における参照元のフィールド１１０４を指示することにある。処理１３０５では参照pが参照列「WORKER→ADDRESS→ZIPCODE」の最初の参照であることから、参照pの直前の参照が存在せず、従って変数zの値をnullとしている。
【００２９】
次の判断１３０６では、参照列rが最初に参照するデータ構造に関する情報が配置図８１１に出力済か否かを、変数oの値をみて判断する。具体的には、変数oの値が０であるか否かを調べ、０であれば（判断１３０６のＹｅｓ）、未出力と判断して処理１３０８に進み、０でなければ（判断１３０６のＮｏ）、すでに集合St中の参照列が参照する１つ以上のデータ構造に関する情報が配置図８１１に出力済みであることから、最初に参照するデータ構造に関する情報は出力済みと判断し、判断１３１２に進む。ここではoの値が０であることから未出力とみなし、処理１３０８に進む。
【００３０】
処理１３０８では、参照pにおける参照先のデータ構造の型をdtとおき、型dtの名前（ここでは「従業員型」）を配置図８１１のデータ型名を記録するフィールド１１０２に出力する。型dtは参照pにおける参照元の宣言型から求めることが可能である。ここでは参照pが「WORKER→ADDRESS」であることから、その参照元である変数WORKERの宣言型をdtとおく。宣言型はソースコード８１０から求められる。続く処理１３０９では、型dtのデータ構造が保持する個々のメンバ変数について、その名前、オフセット、参照先を配置図８１１のフィールド１１０３〜１１０５に出力する。ここでオフセット１１０５の値は、型dtを持つデータ構造の先頭から個々のメンバ変数までのオフセットに、変数oの値を加算した値とし、参照先の値は−１とする。なお、メンバ変数名１１０３は、ソースコード８１０から求めることが可能であるが、必須のものではない。また、オフセット１１０５としては、各メンバ変数に対してコンパイラ８０７が割り振ったデータ領域の大きさを用いればよい。
【００３１】
処理１３０９が終了したら、処理１３１０に進み、変数zの値がnullでない場合には、変数zが指示する参照先フィールド１１０４に変数oの値を書き込む。ここでは変数zの値がnullであることから何もせずに、次の処理１３１１に進み、変数oに、型dtを持つデータ構造の大きさ（ここでは従業員型のデータ構造の大きさ１６）を加算する。処理１３１１が終わったら判断１３１２に進み、参照列rが、参照pの次の参照npを含むか否かを調べ、含む場合には（判断１３１２のＹｅｓ）、処理１３１３に進み、含まない場合には（判断１３１２のＮｏ）、判断１３０３に戻る。ここでは参照pが参照列「WORKER→ADDRESS→ZIPCODE」における最初の参照「WORKER→ADDRESS」であることから、次の参照np、つまり「ADDRESS→ZIPCODE」が存在するので、処理１３１３に進む。
【００３２】
処理１３１３では、変数zの指示先を、参照pにおける参照先のメンバ変数に対応する配置図８１１のフィールド１１０４に定める。ここでは参照pの参照先のメンバ変数は、変数WORKERが指示する従業員型のデータ構造のメンバ変数ADDRESSなので、変数tの指示先は、図４のフィールド１１０４の上から３番目の欄になる。続く処理１３１４では、参照p=npとおく。ここではnpの値が「ADDRESS→ZIPCODE」であるため、参照pが「WORKER→ADDRESS」から「ADDRESS→ZIPCODE」に更新される。
【００３３】
続く判断１３１５では、参照pに関する情報が既に配置図８１１に記録済みか否かを判定するために、変数zの指示先の欄の値を参照する。参照の結果、値が−１である場合には（判断１３１５のＹｅｓ）、記録済みでないとみなして処理１３０８に戻り、−１でない場合には（判断１３１５のＮｏ）、記録済みとみなして判断１３１２に戻る。ここでは変数zの指示先、つまりメンバ変数ADDRESSの参照先１１０４の欄の値が−１であることから（最終的にできあがる図４の配置図８１１では、メンバ変数ADDRESSの参照先の欄は、図４にあるように16になるが、現時点では、まだ処理１３０９で出力した−１が記録されている）、処理１３０８に戻る。
【００３４】
処理１３０８および処理１３０９では、住所型のデータ構造に関する情報が配置図８１１に書き出され、続く処理１３１０では、変数zの指示先のフィールド、つまりメンバ変数ADDRESSに対応する参照先のフィールドの値が、−１から変数oの値、つまり16に更新される。続く処理１３１１で変数oに住所型のデータ構造の大きさ12を加算して、変数oの値を28とし、判断１３１２に進むと、今度は参照列「WORKER→ADDRESS→ZIPCODE」が含む２つの参照「WORKER→ADDRESS」と「ADDRESS→ZIPCODE」の処理が全て終了してしまっていることから、次の参照npは存在せず（判断１３１２のＮｏ）、判断１３０３に戻る。判断１３０３に戻った時点で、集合Stには、まだ参照列「WORKER→NAME→LAST」が残っていることから（判断１３０３のＮｏ）、処理１３０４に進み、処理１３０４から先で参照列「WORKER→NAME→LAST」に関する情報を配置図８１１に出力して再び判断１３０３に戻ると、今度は集合Stが空集合φになっているので（判断１３０３のＹｅｓ）、処理１３１６に進み、総データ構造長を記録するフィールド１１０６に変数oの値を出力して処理を終了する。処理が終了した時点で、配置図８１１には、図４に示す通りの内容が記載されている。
【００３５】
図３の処理１００５で配置図８１１を作成すると、コンパイラ８０７は、処理１００６に進んでプリフェッチ命令を挿入する処理をおこなう。具体的には、中間表現９０２を走査して、集合Stに属する参照列が存在するか否かを調べ、存在する場合、その参照列を用いた処理の前に、参照列において参照するアドレスに対するプリフェッチ命令を挿入する。プリフェッチ命令の挿入にあたっては、プリフェッチ対象のアドレスを、最初に参照するデータ構造のアドレスと、処理１００５で生成した配置図８１１のフィールド１１０５から得られるオフセットの和とする。例えば中間表現９０２を走査する過程で図１７の機械コード列に対応する参照列を発見したら、その参照列を用いた処理の前に、この参照列において参照するメンバ変数NAMEおよびLASTの内容をプリフェッチする命令を挿入する。
【００３６】
コンパイラ８０７によるプリフェッチ命令の挿入結果として得られる命令列を図７に示す。図７の１行目ではメンバ変数NAMEをプリフェッチし、２行目ではメンバ変数LASTをプリフェッチする。プリフェッチするアドレスがそれぞれ、変数WORKERの値を格納するレジスタr1の値に、整定数１２および４０を加えた値になっている理由は、図４の配置図８１１から、それぞれのメンバ変数のアドレスが、最初に参照するデータ構造の先頭アドレスに、オフセット１２および４０を加えた値になると判るからである。
【００３７】
図３の処理１００６でプリフェッチ命令の挿入をおこなったら、判断１００３に戻って集合Ｓが空集合φか否かを調べる。ここでは、集合Ｓが空集合φであることから（判断１００３のＹｅｓ）、図３の処理を終了する。
【００３８】
図３の処理１００５で生成した配置図８１１は、機械コード８０９に収められ、実行時にごみ集め８１２に引き渡される。ごみ集め８１２の処理の実施例を図８に示す。図８に示した処理１５０１〜１５０４の手順自体は単なる複写式ごみ集めの手順である。まず処理１５０１でルートが指示するデータ構造をto領域に複写することを通じて移動し、次に、処理１５０２でto領域中のデータ構造内にある参照が指示するデータ構造をto領域に移動する。処理１５０２が終了したら、処理１５０３でfrom領域全体を解放し、最後に処理１５０４でfrom領域とto領域の役割を交代する。本発明のごみ集め８１２が従来の複写式ごみ集めと異なるのは、処理１５０１および処理１５０２で実行する、参照が指示するデータ構造を移動する手順である。
従来の複写式ごみ集めにおける移動の手順と、本発明における移動の手順の違いを示すために、それぞれの移動の手順について順次述べる。
【００３９】
まず、従来の複写式ごみ集めにおけるデータ構造の移動の手順を図９に示す。図９の処理では、まず判断１６０１で参照が指示するデータ構造が移動済みか否かを調べ、移動済みでなければ（判断１６０１のＮｏ）、処理１６０２に進んで参照が指示するデータ構造をto領域に複写することを通じて移動し、続く処理１６０３で複写元のデータ構造に、移動済みの印と移動先（複写先）のアドレスを記録しておく。判断１６０１でデータ構造が移動済みか否かを判断できるのは、処理１６０３で移動済みの印を記録するからである。移動済みの印は、移動前のデータ構造にはついていない。処理１６０３が終わったら処理１６０４に進み、参照の値を移動先のアドレスに更新する。判断１６０１でデータ構造が移動済みと判断した場合にも（判断１６０１のＹｅｓ）、処理１６０４に進んで参照の更新をおこなうが、このとき更新先のアドレス、つまり参照が指示するデータ構造の移動先のアドレスは、参照が指示するデータ構造から取得できる。なぜなら処理１６０３で、移動元のデータ構造、つまり参照が指示するデータ構造に、移動先のアドレスを記録しておいたからである。
【００４０】
次に、本発明におけるデータ構造の移動の手順を図１０に示す。図１０の処理では、図９の処理と、判断１６０１、処理１６０３および処理１６０４を共有しているが、残りの部分（処理１７０１〜１７０６）が本発明の処理に相当する。図１０では、まず、最初に、図９の処理と同様に、判断１６０１で参照が指示するデータ構造が移動済みか否かを調べ、移動済みであれば（判断１６０１のＮｏ）、図９と同様に処理１６０４に進んで参照の指示先を更新し、移動済みでなければ（判断１６０１のＹｅｓ）、判断１７０１に進む。判断１７０１では参照が指示するデータ構造が配置図８１１に従って詰めなおすべきものかを判断する。具体的には、参照が指示するデータ構造向けの配置図８１１が存在する場合には（判断１７０１のＹｅｓ）、配置図８１１に従って詰めなおすべきであると判断して処理１７０２に進み、配置図８１１が示す通りに詰めなおしの処理をおこなう。さもなければ（判断１７０１のＮｏ）、処理１７０３に進み、従来のごみ集めと同様の詰めなおし（複写）処理の実行を試みる。
【００４１】
処理１７０３で実行する処理は、基本的に図９の処理１６０２と同様だが、異なる点が１つある。それは、後記するように、配置図８１１を使う図１０の処理によるごみ集めでは、詰めなおしたデータ構造の間に空き領域が生じて、余分な記憶領域を消費しうることから、from領域中の全データ構造をto領域に移動できるとは限らず、処理１７０３における移動の処理が失敗しうることである。移動に失敗した場合には（判断１７０４のＮｏ）、処理１７０５に進み、処理１７０５でこれまでに実行したごみ集めの処理をキャンセルした上で、配置図８１１を使わない従来の複写式ごみ集めを実行する。これまでに実行したごみ集めの処理をキャンセルするには、次に示す２つの処理を実施すればよい。（１）from領域中のデータ構造に書き込んだ、移動済みの印および移動先のアドレスを消す。この処理は、移動済みの印と移動先のアドレスがデータ構造のヘッダに記載されていると仮定するとき、ヘッダの内容を移動先から書き戻すことで実現できる。書き戻す処理を実行した際には、移動先のデータ構造に、移動元のデータ構造のアドレスを書き込んでおく。（２）ルートが含むto領域中への参照をfrom領域中への参照に戻す。この処理は、to領域中への参照の値を、参照が指示するデータ構造に、処理（１）で書き込んだ、移動元のアドレスに修正することで実現できる。
【００４２】
図１０の処理１７０３において、従来のごみ集めと同様の詰めなおし処理に成功した場合には（判断１７０４のＹｅｓ）、処理１６０３に進み、従来のごみ集めと同様に、複写元のデータ構造に、移動先のアドレスと複写済みの印を書き込み、処理１６０４に進んで参照を移動先のアドレスに更新する。
【００４３】
図１０の判断１７０１で、配置図８１１に従って詰めなおすべきであると判断した場合には（判断１７０１のＹｅｓ）、処理１７０２に進んで配置図８１１に従った詰めなおしを試みるが、ここでも処理１７０３と同様の理由から、詰めなおしに失敗する場合がある。失敗した場合には（判断１７０６のＮｏ）、処理１７０５に進み、これまで実行したごみ集めの処理をキャンセルし、配置図８１１を使わない従来のごみ集めを実行する。詰めなおしに成功した場合には（判断１７０６のＹｅｓ）、処理を終了する。
【００４４】
判断１７０１および処理１７０２の実施例を図１１に示す。図１１は、処理１８０１、判断１８０２、処理１８０３、判断１８０４、処理１８０５、処理１８０６および処理１８０７からなるが、これらのうち、判断１７０１を構成する役割を担うのが処理１８０１と判断１８０２であり、処理１７０２を構成する役割を担うのが処理１８０３、判断１８０４、処理１８０５、処理１８０６および処理１８０７である。
【００４５】
図１１の処理１８０１では、参照が指示するデータ構造の型をtとおく。ここでデータ構造の型は、データ構造のヘッダに記載してあるものと仮定する。次に判断１８０２で配置図８１１を検索し、配置図８１１の中に、初回参照データ型名１１０１の欄の値がtと一致するものが存在するか否かを調べる。存在した場合には（判断１８０２のＹｅｓ）、発見した配置図８１１をzとおいて処理１８０３に進み、存在しない場合には（判断１８０２のＮｏ）、配置図８１１を使って詰めなおすデータ構造でないとみなし、図１０の処理１７０３に進む。
【００４６】
図１１の処理１８０３では、配置図ｚを参照し、その総データ構造長の欄１１０６に記載してある広さの空き領域aをto領域に確保するよう試み、続く判断１８０４で確保に成功したか否かを調べ、成功した場合には（判断１８０４のＹｅｓ）、処理１８０５に進み、失敗した場合には（判断１８０４のＮｏ）、移動に失敗したものとして図１１の処理を終了する。成功した場合に行う処理１８０５では、参照が指示するデータ構造を領域aの冒頭に移動する。移動の処理は、次の３つの要素からなる。（１）データ構造を複写する処理、（２）複写元のデータ構造に移動済みの印および移動先のアドレスを記載する処理、（３）参照の値を移動先に更新する処理。
【００４７】
移動が済んだら、処理１８０６に進み、領域aに移動したデータ構造を走査し、データ構造の内部にある参照が指示するデータ構造を、配置図zに従って、領域aに詰めなおす。処理１８０６における走査の対象となるデータ構造は、処理１８０５で領域aに移動したデータ構造に限らず、処理１８０６で領域aに移動したデータ構造を含む。領域aに移動した全部のデータ構造の走査が終了したら、処理１８０６を終了する。
【００４８】
処理１８０６の実施例を図１２に示す。図１２では、まず判断１９０１で領域aに未走査のデータ構造があるか否かを調べ、ない場合には（判断１９０１のＮｏ）、処理を終了し、ある場合には（判断１９０１のＹｅｓ）、処理１９０２に進んで未走査のデータ構造の１つをdとおく。続いて判断１９０３でデータ構造dを走査して、未走査のメンバ変数を含むか否かを調べ、含まない場合には（判断１９０３のＮｏ）、判断１９０１に戻り、含む場合には（判断１９０３のＹｅｓ）、処理１９０４に進んで、未走査のメンバ変数の１つをfとおく。続く処理１９０５で配置図ｚの、メンバ変数fに対応するエントリを参照し、エントリの参照先を表す欄１１０４の値oが−１か判断１９０６で判定して、−１の場合には（判断１９０６のＹｅｓ）、メンバ変数fが参照するデータ構造を領域aに回収する必要がないので判断１９０３に戻り、−１でない場合には（判断１９０６のＮｏ）、回収する必要があるので判断１９０７に進む。判断１９０７ではメンバ変数fの内容がnullか否かを調べ、nullの場合には（判断１９０７のＮｏ）、メンバ変数fが参照するデータ構造がないので判断１９０３に戻る。nullでない場合には（判断１９０７のＹｅｓ）、判断１９０８に進み、メンバ変数fが指示するデータ構造が移動済みか否かを調べ、移動済みでない場合には（判断１９０８のＮｏ）、処理１９０９で指示先のデータ構造を領域aのオフセットoの位置に複写し、続く処理１９１０で複写元のデータ構造に、移動済みの印と移動先のアドレスを記入する。処理１９１０が終了した場合、または判断１９０８で移動済みであった場合には（判断１９０８のＹｅｓ）、処理１９１１に進み、メンバ変数fの内容を移動先のアドレスに更新する。
【００４９】
図１２の処理と図４の配置図を使って、図１６および図１３のデータ構造を移動すると、データ構造が図５または図１４の順に並ぶ。図１６と図１３のデータ構造の違いは、従業員型のデータ構造が保持するメンバ変数ADDRESSの値がnullであるか否かである。図１６と図１３のデータ構造を、本発明のごみ集め８１２を使って移動した結果である図５と図１３を比較すると、メンバ変数ADDRESSの値によらず、従業員型のデータ構造が保持するメンバ変数NAMEが参照する名前型のデータ構造が同じ位置にあることが判る。このことは、本発明の最適化処理９０６を使ってプリフェッチ命令を挿入した機械コード（図７参照）によって実行を高速化する上で重要である。なぜなら図７のコードでは名前型のデータ構造が保持するメンバ変数LASTの位置が、従業員型のデータ構造の先頭アドレスから４０先にあると仮定しており、この仮定が崩れるとプリフェッチ命令が有効に働かなくなるからである。図５と図１４を参照すると、どちらの場合でもメンバ変数LASTの位置が、従業員型のデータ構造の先頭アドレスから４０先にあり、図７のプリフェッチ命令を活用できていることが判る。
【００５０】
なお、従来のごみ集めの処理（図９参照）を使って図１３のデータ構造を移動すると、図１５の配置になって、メンバ変数LASTの位置が、従業員型のデータ構造の先頭アドレスから４０先ではなくなり、図７のプリフェッチ命令を活用できなくなる。図１５の配置には、空き領域を挟まない分、図１４の配置より消費メモリが小さいという利点がある。しかしながら図１５の配置を採用して消費メモリを抑えることに必ずしも大きな意味はない。搭載メモリ量が少ない旧来の機械であれば、消費メモリを抑えると、ごみ集めの発生頻度が少なくなって実行を高速化する効果が得られたが、昨今のサーバは膨大なメモリを搭載していることから、そもそもごみ集めの発生頻度が極めて小さく、図１５の配置を採用して消費メモリが多少増えても、ごみ集めの発生頻度に大きな影響を与えないからである。昨今のサーバでは、図１４の配置によってプリフェッチ命令を活用した方が実行を高速化できる可能性がある。また、図１１では、処理１８０６に続く処理１８０７で、領域a内に空き領域として残った領域を、空き領域を管理するためのリスト（空きリスト）につなぎ、別のデータ構造を割り付けるための領域として使用可能にする措置をとっているので、空き領域は無駄にならない。図１４に存在する空きリストからのリンクは処理１８０７を適用した結果として生じたものである。
【００５１】
なお、本実施例では、図６で配置図８１１を作成する際に、参照の宣言型と、参照が指示するデータ構造の型が一致すると仮定し、したがって参照が指示するデータ構造の大きさは、参照の宣言型をもつデータ構造の大きさに一致すると仮定して、処理１３１１で変数oにdtを持つデータ構造の大きさを加算する。しかしながら、この処理１３１１の実現は、参照の宣言型と、参照が指示するデータ構造の型が一致するとは限らないプログラミング言語向けには必ずしも適当でない。例えばJava（登録商標）では、参照が指示するデータ構造の型は、必ずしも参照の宣言型とは一致せず、このときデータ構造の大きさは、参照の宣言型から求めた大きさより大きくなりうる。参照先のデータ構造の大きさが、参照の宣言型から求められる大きさよりも大きいとき、図６の処理１３１１を使って作成した配置図８１１を使ってごみ集めを適用しようとすると、配置図８１１の通りにデータ構造を配置できなくなりうる。例えば図４の配置図８１１を使ってごみ集めを実施しようとした際に、従業員型のデータ構造のメンバ変数ADDRESSが、メンバ変数ADDRESSの宣言型から求めた大きさ１２よりも大きいデータ構造を指示していたとしたら、図５の位置にデータ構造を配置できなくなる。
【００５２】
この問題に対処するには、ここで示した実施例に、次に示す２つの改良を加えればよい。（１）処理１３１１で変数oにデータ構造の大きさを加算する際に、加算する大きさを、参照の宣言型dtから求めるのではなく、参照が実行時に指示するデータ構造の型から求める。参照が実行時に指示するデータ構造の型は実行プロファイルを使って求められる。実行プロファイルから、参照が実行時に複数の型のデータ構造を指示したと判った場合には、指示したデータ構造のうち、最も大きなデータ構造の大きさを加算する。また、ここで加算した値、つまりデータ構造の大きさを、配置図８１１に追記しておく。（２）ごみ集めにおいて、配置図を使った詰めなおし処理を適用する際に、参照が指示するデータ構造の大きさを確認し、大きさが（１）で加算した大きさよりも小さいか、配置図に追記した内容と照らし合わせて調べ、小さい場合には配置図の通りにデータ構造を詰めなおし、大きい場合には配置図の範囲外に詰めなおす。
【産業上の利用可能性】
【００５３】
本発明は、ごみ集めの機能を提供するプログラミング言語処理系において利用できる。
【図面の簡単な説明】
【００５４】
【図１】本発明の言語処理系が動作するシステムの構成例を示す図である。
【図２】本発明のコンパイラの機能例を示す図である。
【図３】本発明のコンパイラによるプリフェッチ命令挿入処理例を示すフローチャートである。
【図４】本発明のコンパイラによって作成される配置図の構成例を示す図である。
【図５】データ構造の配置の例（その１）を示す図である。
【図６】本発明における配置図の作成手順の例を示すフローチャートである。
【図７】プリフェッチ命令を含む機械命令列の例を示す図である。
【図８】複写式ごみ集めの手順の例を示す図である。
【図９】従来の複写式ごみ集めにおける詰めなおし処理の例を示す図である。
【図１０】本発明による複写式ごみ集めにおける詰めなおし処理の例（その１）を示す図である。
【図１１】本発明による複写式ごみ集めにおける詰めなおし処理の例（その２）を示す図である。
【図１２】本発明による複写式ごみ集めにおける詰めなおし処理の例（その３）を示す図である。
【図１３】参照で連結されたデータ構造の例（その１）を示す図である。
【図１４】データ構造の配置の例（その２）を示す図である。
【図１５】データ構造の配置の例（その３）を示す図である。
【図１６】参照で連結されたデータ構造の例（その２）を示す図である。
【図１７】参照列WORKER→NAME→LASTに対応する機械命令列の例を示す図である。
【図１８】従来の複写式ごみ集めの例（その１）を示す図である。
【図１９】従来の複写式ごみ集めの例（その２）を示す図である。
【図２０】従来の複写式ごみ集めの例（その３）を示す図である。
【図２１】従来の複写式ごみ集めの例（その４）を示す図である。
【図２２】従来の複写式ごみ集めの例（その５）を示す図である。
【符号の説明】
【００５５】
８０１  ハードディスク
８０２  バス
８０３  主記憶
８０４  プロセッサ
８０５  言語処理系
８０６  プロファイラ
８０７  コンパイラ
８０８  実行時システム
８０９  機械コード
８１０  ソースコード
９０２  中間表現
９０５  参照列群
【図１】
2007041853.tif 000003
【図２】
2007041853.tif 000004
【図３】
2007041853.tif 000005
【図４】
2007041853.tif 000006
【図５】
2007041853.tif 000007
【図６】
2007041853.tif 000008
【図７】
2007041853.tif 000009
【図８】
2007041853.tif 000010
【図９】
2007041853.tif 000011
【図１０】
2007041853.tif 000012
【図１１】
2007041853.tif 000013
【図１２】
2007041853.tif 000014
【図１３】
2007041853.tif 000015
【図１４】
2007041853.tif 000016
【図１５】
2007041853.tif 000017
【図１６】
2007041853.tif 000018
【図１７】
2007041853.tif 000019
【図１８】
2007041853.tif 000020
【図１９】
2007041853.tif 000021
【図２０】
2007041853.tif 000022
【図２１】
2007041853.tif 000023
【図２２】
2007041853.tif 000024