(57)【要約】【課題】ループ内でリストベクトルをアクセスする場合のキャッシュミスを減少させ，翻訳されたプログラムの実行性能を向上させるコンパイル技術を提供する。【解決手段】コンパイラは，ループ内でアクセスされるリストベクトルの構造体の領域を確保する領域確保命令１１，領域解放命令１２を，それぞれ新領域確保命令２１，新領域解放命令２２に変換したオブジェクトプログラム２０を生成する。新領域確保命令２１によって呼び出される新領域確保命令処理部３１は，最初の領域確保要求に対して構造体の領域の整数倍以上の一括確保領域５１を確保し，そこから構造体の領域を切り出して割り当てる。２回目以降の領域確保要求に対しては，一括確保領域５１から前の構造体の領域に連続した領域を割り当てる。新領域解放命令２２によって呼び出される新領域解放命令処理部３２は，一括確保領域５１が不要となったときにまとめて解放する。【選択図】図１
2008003882.tif 000002
【特許請求の範囲】
【請求項１】
ソースプログラムを入力し，オブジェクトプログラムに翻訳するコンパイラプログラムであって，
コンピュータを，
ソースプログラムを解析した結果に基づき，複数の構造体の連鎖からなるリストベクトルへのアクセスを含むループを検出するリストベクトルループ検出手段と，
前記検出したループ内でアクセスされるリストベクトルにおける構造体の領域をメモリから確保する命令および解放する命令を検出する領域確保／解放命令検出手段と，
前記検出した構造体の領域を確保する命令を，最初の呼出し時には前記構造体の領域サイズのｎ倍（ｎ≧２）以上のサイズの連続領域を確保し，その連続領域から構造体の領域を切り出して割り当て，２回目以降の呼出し時には確保済みの前記連続領域から構造体の領域を切り出して割り当てる新領域確保命令処理部を呼び出す新領域確保命令に書き換え，前記検出した構造体の領域を解放する命令を，前記連続領域における構造体の領域の使用状況を管理し，構造体の領域がすべて未使用状態になったときに，当該連続領域を解放する新領域解放命令処理部を呼び出す新領域解放命令に書き換える領域確保／解放命令変換手段と，
前記領域確保／解放命令変換手段によって変換された命令を含むコードを生成し，オブジェクトプログラムとして出力するコード生成手段として
機能させるためのコンパイラプログラム。
【請求項２】
請求項１記載のコンパイラプログラムにおいて，
前記新領域確保命令処理部によって確保される連続領域のサイズを定めるｎの値が，前記オブジェクトプログラムの試験走行において採取された前記ループが実行された回数を記録したプロファイル情報に基づき決定されたものである
ことを特徴とするコンパイラプログラム。
【請求項３】
ソースプログラムを入力し，オブジェクトプログラムに翻訳するコンパイラプログラムを搭載するコンピュータが実行するリストベクトルの領域割当て最適化方法であって，
ソースプログラムを解析した結果に基づき，複数の構造体の連鎖からなるリストベクトルへのアクセスを含むループを検出するリストベクトルループ検出過程と，
前記検出したループ内でアクセスされるリストベクトルにおける構造体の領域をメモリから確保する命令および解放する命令を検出する領域確保／解放命令検出過程と，
前記検出した構造体の領域を確保する命令を，最初の呼出し時には前記構造体の領域サイズのｎ倍（ｎ≧２）以上のサイズの連続領域を確保し，その連続領域から構造体の領域を切り出して割り当て，２回目以降の呼出し時には確保済みの前記連続領域から構造体の領域を切り出して割り当てる新領域確保命令処理部を呼び出す新領域確保命令に書き換え，前記検出した構造体の領域を解放する命令を，前記連続領域における構造体の領域の使用状況を管理し，構造体の領域がすべて未使用状態になったときに，当該連続領域を解放する新領域解放命令処理部を呼び出す新領域解放命令に書き換える領域確保／解放命令変換過程と，
前記領域確保／解放命令変換過程によって変換された命令を含むコードを生成し，オブジェクトプログラムとして出力するコード生成過程とを有する
ことを特徴とするリストベクトルの領域割当て最適化方法。
【請求項４】
ソースプログラムを入力し，オブジェクトプログラムに翻訳するコンパイラプログラムを搭載したコンピュータによるコンパイル処理装置であって，
ソースプログラムを解析した結果に基づき，複数の構造体の連鎖からなるリストベクトルへのアクセスを含むループを検出するリストベクトルループ検出手段と，
前記検出したループ内でアクセスされるリストベクトルにおける構造体の領域をメモリから確保する命令および解放する命令を検出する領域確保／解放命令検出手段と，
前記検出した構造体の領域を確保する命令を，最初の呼出し時には前記構造体の領域サイズのｎ倍（ｎ≧２）以上のサイズの連続領域を確保し，その連続領域から構造体の領域を切り出して割り当て，２回目以降の呼出し時には確保済みの前記連続領域から構造体の領域を切り出して割り当てる新領域確保命令処理部を呼び出す新領域確保命令に書き換え，前記検出した構造体の領域を解放する命令を，前記連続領域における構造体の領域の使用状況を管理し，構造体の領域がすべて未使用状態になったときに，当該連続領域を解放する新領域解放命令処理部を呼び出す新領域解放命令に書き換える領域確保／解放命令変換手段と，
前記領域確保／解放命令変換手段によって変換された命令を含むコードを生成し，オブジェクトプログラムとして出力するコード生成手段とを備える
ことを特徴とするコンパイル処理装置。
【請求項５】
ソースプログラムを入力し，オブジェクトプログラムに翻訳するコンパイラプログラムを記録したコンピュータ読み取り可能な記録媒体であって，
コンピュータを，
ソースプログラムを解析した結果に基づき，複数の構造体の連鎖からなるリストベクトルへのアクセスを含むループを検出するリストベクトルループ検出手段と，
前記検出したループ内でアクセスされるリストベクトルにおける構造体の領域をメモリから確保する命令および解放する命令を検出する領域確保／解放命令検出手段と，
前記検出した構造体の領域を確保する命令を，最初の呼出し時には前記構造体の領域サイズのｎ倍（ｎ≧２）以上のサイズの連続領域を確保し，その連続領域から構造体の領域を切り出して割り当て，２回目以降の呼出し時には確保済みの前記連続領域から構造体の領域を切り出して割り当てる新領域確保命令処理部を呼び出す新領域確保命令に書き換え，前記検出した構造体の領域を解放する命令を，前記連続領域における構造体の領域の使用状況を管理し，構造体の領域がすべて未使用状態になったときに，当該連続領域を解放する新領域解放命令処理部を呼び出す新領域解放命令に書き換える領域確保／解放命令変換手段と，
前記領域確保／解放命令変換手段によって変換された命令を含むコードを生成し，オブジェクトプログラムとして出力するコード生成手段として
機能させるためのコンパイラプログラムを記録したコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は，コンパイラによるプログラムの翻訳技術に関し，特にコンパイラが出力するオブジェクトプログラムの実行性能を向上させるリストベクトルの領域割当て最適化方法およびそのプログラムに関する。
【背景技術】
【０００２】
図１１はリストベクトルの説明図，図１２はリストベクトル領域のメモリ割当ての例を示す図である。また，図１３はリストベクトルをアクセスするループを持つプログラムの例を示す図である。
【０００３】
プログラムの中に図１１のような構造体（以降，構造体Ａとする）領域をリンクするリストベクトルが存在するケースを考える。リストベクトルとは，自身と同じ構造体へのポインタ（図１１の例ではｎｅｘｔ）を持つ構造体の連鎖である。
【０００４】
この構造体Ａのメモリ領域が，領域確保命令（関数やマクロ命令を含む）で確保されると，確保された各構造体領域は，ばらばらな不連続な領域になる可能性がある。すなわち，領域確保命令による実際の領域割付けでは，領域確保を実施するタイミング毎に，各構造体領域がどのアドレスに割り付けられるかが決まる。したがって，図１２のように分散したばらばらのアドレスの領域が割り当てられる可能性がある。
【０００５】
例えばＣ言語の場合，メモリ領域を確保するための領域確保命令は，ｍａｌｌｏｃ関数などのシステム関数である。また，領域解放命令は，ｆｒｅｅ関数である。以下では，領域確保／解放命令として，ｍａｌｌｏｃ／ｆｒｅｅ関数を用いた例について説明する。
【０００６】
図１２に示すように，各構造体に対して割り当てられる領域がばらばらであると，ある構造体メンバから次の構造体メンバをアクセスする際には，キャッシュミスを起こす可能性が高くなる。例えば図１３のように，ループ内で構造体のポインタｐを辿り，構造体メンバを連鎖的にアクセスするプログラムは，多用されるプログラムであるが，あるイテレーションのアクセスｐ−＞ｘでキャッシュミスし，次のイテレーションのアクセスｐ−＞ｘでもキャッシュミスする可能性は高い。キャッシュミスの場合，主記憶からキャッシュメモリへのデータの読み込みが必要になるため，アクセス時間が長くなる。
【０００７】
近年，ハードウェアプリフェッチをサポートするアーキテクチャは多いが，ハードウェアプリフェッチ機構は隣接領域を連続アクセスするような領域アクセスを先読みする方法しか対応していないため，図１３のようなリストベクトルでアクセスされる領域が図１２のように割り当てられていると，必ずキャッシュミスが起こってしまう。
【０００８】
下記の特許文献１には，リスト構造データを繰り返し処理するループを含むプログラムの高速化を行うために，ループ制御文を，リスト構造データの先頭アドレスを作業配列の配列要素に登録するとともにリスト構造データの個数を数えるループ制御文に変形する技術が示されている。すなわち，特許文献１の技術では，リストベクトルへのアクセスを，作業配列に格納した先頭アドレスを用いて行うように元のループの変形と前後処理を生成することで，ループの高速化を図っている。
【０００９】
また，下記の特許文献２には，制御データは主記憶に割り当て，データ要素のサイズが拡張記憶のサイズと一致する場合には，拡張記憶に割り当て，拡張記憶のアクセスサイズと同一ならば，拡張記憶に格納しても，書き込みと読み出しを行う際，アクセスするデータをロックする必要がないので，拡張記憶に格納することで，データのアクセス時間を短縮する技術が示されている。すなわち，特許文献２の技術では，構造体制御データと構造体データの格納先を，主記憶と拡張記憶の大きさに応じて割当て制御することで，アクセス時間の短縮を図っている。
【００１０】
しかし，特許文献１，２では，どちらもループ内でのリスト型構造体のアクセスを，連続領域のアクセスにコンパイラが自動変換することにより，キャッシュメモリへのアクセス時のヒット率を向上させることについて，まったく考慮されていない。
【特許文献１】特開２００３−３３７７０７号公報
【特許文献２】特開平１１−１５７９８号公報
【発明の開示】
【発明が解決しようとする課題】
【００１１】
コンパイラが翻訳するプログラムにおいて，リストベクトルの領域を割り当てる際，１つの構造体（ノード）毎に領域確保が行われると，各構造体領域がメモリ空間上に分散して確保される可能性がある。もし，この各構造体がループ内で連続してアクセスされると，キャッシュ効率が悪くなるなどの性能低下の要因となりうる。
【００１２】
各構造体領域の分散を防ぐために，構造体のポインタで指標される領域サイズが固定であるとか，領域サイズの最大値が静的に確定する場合には，動的な領域の割付けを止め，静的な連続する領域に割り付けることも考えられるが，どれだけの領域を使うか分からない場合には，静的な連続する領域への割付けはできない。
【００１３】
構造体のポインタで指標される領域サイズが固定であるとは，例えばＣ言語により次のように命令が記述される場合である。
【００１４】
ｐ＝（ｓｔｒｕｃｔ  Ａ  ＊）ｍａｌｌｏｃ（ｓｉｚｅｏｆ（ｓｔｒｕｃｔ  Ａ）＊１０）
もし，図１３のようなプログラムでアクセスするリストベクトル領域が，図１４のように連続した領域に割り当てられれば，ある構造体からネクストポインタ（ｎｅｘｔ）で辿れる構造体の同一メンバ間（図１４の変数ｘ）の距離は定幅となる。
【００１５】
これにより，例えば定幅アクセスのハードウェアプリフェッチをサポートしているアーキテクチャや，リストベクトルが上記のように割り付けてあることを利用してソフトウェアプリフェッチを出力することで，リストベクトルのキャッシュミスを防ぐことが可能となる。
【００１６】
しかしながら，これを実現するには，図１４のように構造体Ａのための領域が連続して割り付けられるような工夫をしなければならない。このための連続領域の確保で問題になるのは，ある構造体Ａの領域を確保するための要求がきた段階では，将来どの程度の領域が必要となるかが不明であることである。このことから，従来のコンパイラでは，リストベクトルの領域割当てにおける最適化の改善ができていない。
【００１７】
本発明は上記問題点の解決を図り，翻訳対象のプログラムについて，実行時に適切な連続領域にリストベクトルを割り当てるようにし，キャッシュミスを少なくすることにより，実行性能のよいオブジェクトプログラムの生成を可能とするコンパイル技術を提供することを目的とする。
【課題を解決するための手段】
【００１８】
本発明は，上記課題を解決するため，ループで扱われるリストベクトルのアクセスに対し，その領域を確保する領域確保命令，領域解放命令（関数やマクロ命令を含む）を検出し，その領域確保／解放命令を独自の新領域確保／解放命令に変換する。独自の新領域確保命令では，最初の領域確保要求（アロケート要求）に対して，ある程度大きな領域を取り，それ以降の領域確保要求に対してはその領域からの切り出しを行う。こうすることで，リストベクトル（複数の構造体連鎖）でも自動的に連続領域が割り当てられるようにし，コンパイラによる最適化を実現する。
【００１９】
すなわち，コンパイラプログラムが，翻訳対象のソースプログラムの解析結果から，ループ内で連続アクセスするリストベクトルを検出し，そのリストベクトルの構造体領域を確保する領域確保命令を，新領域確保命令に書き換える。新領域確保命令の処理では，最初にその構造体領域のサイズの整数倍以上のメモリ領域を確保し，その中から構造体領域を割り当て，２回目以降の命令に対しては，最初に確保したメモリ領域から連続的に構造体領域を切り出して割り当てる。
【００２０】
また，コンパイラプログラムは，領域確保命令に対応する領域解放命令を新領域解放命令に書き換える。新領域解放命令の処理では，構造体領域のサイズの整数倍以上のメモリ領域におけるすべての領域が解放されたときに，全体のメモリ領域を解放する。
【発明の効果】
【００２１】
本発明によれば，コンパイラが既存の領域確保／解放命令を新領域確保／解放命令に書き換えることにより，ループ内で使用されるリストベクトルの各構造体領域が連続領域に割り付けられるようになり，実行時においてキャッシュミスの発生回数が減少するので，リストベクトルを含むプログラムの実行性能が向上する。また，構造体領域のアクセスにおけるページフォルトも減少し，メモリのフラグメンテーションも改善される。特に，本発明は，既存のソースプログラムについても，それをプログラム作成者が書き換えることなく，再コンパイルするだけで実行性能を向上させることができる。
【発明を実施するための最良の形態】
【００２２】
以下では，本発明をＣ言語のコンパイラに適用した実施の形態を説明するが，本発明は，Ｃ言語のコンパイラに限らず，リスト型構造体を記述可能な計算機言語のコンパイラに同様に適用することが可能である。
【００２３】
図１は，本発明の概要を説明する図である。図１において，１０はＣ言語で記述されたソースプログラムであり，２０はソースプログラム１０を翻訳した結果のオブジェクトプログラムである。ソースプログラム１０において，領域確保命令１１は，Ｃ言語プログラムにおいてメモリ領域を確保するためのｍａｌｌｏｃ関数であり，領域解放命令１２は，Ｃ言語プログラムにおいてメモリ領域を解放するためのｆｒｅｅ関数である。オブジェクトプログラム２０は，機械語命令列からなるプログラムであるが，以下では説明を分かりやすくするために，命令の表記をソースプログラムと同様な表記で示す。
【００２４】
本発明で処理対象となるのは，リストベクトルの構造体領域を確保する領域確保命令１１であり，特にリストベクトルがプログラムのループ内で使用される場合である。
【００２５】
コンパイラは，ソースプログラム１０においてループ内で使用されるリストベクトルを検出すると，そのリストベクトルの構造体領域を確保する領域確保命令１１を探し出し，それを新領域確保命令２１に書き換える。また，その領域確保命令１１で確保した構造体領域を解放する領域解放命令１２を探し出し，それを新領域解放命令２２に書き換えて，それらの命令コードをオブジェクトプログラム２０として出力する。
【００２６】
このオブジェクトプログラム２０をリンカによって処理して実行形式プログラム（以下，説明の都合上，この実行形式プログラムについてもオブジェクトプログラムとして説明する。）とし，実行させると，新領域確保命令２１によって新領域確保命令処理部３１が呼び出される。なお，新領域確保命令処理部３１および新領域解放命令処理部３２は，動的リンクライブラリ（ＤＬＬ）として用意されたプログラムである。これらは，予め静的にリンクされるライブラリとして用意されるものであってもよい。
【００２７】
新領域確保命令処理部２１は，最初の呼出し時には，１つの構造体領域のサイズのｎ倍（ｎ≧２）以上の一括確保領域（以下，これをＳ領域ともいう）５１を確保し，その領域管理情報を領域マネージャ４０に設定する。領域マネージャ４０は，Ｓ領域５１の領域管理情報を記憶しておくための作業領域である。オブジェクトプログラム２０から要求された構造体５０−１の領域を，確保したＳ領域５１から切り出して，そのアドレスを戻り値として新領域確保命令２１の発行元へ返却する。
【００２８】
２回目の新領域確保命令２１による呼出しに対しては，新領域確保命令処理部３１は，既に確保しているＳ領域５１から，次の構造体５０−２の領域を確保し，そのアドレスを戻り値として新領域確保命令２１の発行元へ返却する。３回目以降も同様である。これによって，各構造体５０−１，５０−２，５０−３，…は，連続領域に割り当てられることになる。Ｓ領域５１を構造体の領域の割り当て用に使い切った場合には，その後の新領域確保命令処理部３１の呼出しに対して，１回目の呼出しのときと同様に，再度メモリの別領域からＳ領域５１を確保し，新しい構造体領域を割り当てることを繰り返す。なお，Ｓ領域５１における構造体領域の使用状況，割当て状況は，領域マネージャ４０内に保持しておく。
【００２９】
次に，オブジェクトプログラム２０の実行により新領域解放命令２２が実行されると，新領域解放命令処理部３２が呼び出される。新領域解放命令処理部３２は，解放要求があった構造体領域のアドレスをもとに，領域マネージャ４０内に保持している構造体領域の使用状況を更新する。例えば使用状況として，領域マネージャ４０内に各構造体が使用中であるか否かを示す領域状態フラグを各構造体毎に用意しておき，解放要求に対して，該当する構造体の領域状態フラグをＯＦＦにする。新領域解放命令処理部３２は，Ｓ領域５１内の構造体のすべての領域状態フラグがＯＦＦになったときに初めてＳ領域５１を解放し，システムに返却する。
【００３０】
図１に示す処理を実現するためのコンパイラが行う処理について，さらに詳しく説明する。本実施の形態では，以下のプロセスで，ループ内で連続アクセスするリストベクトルの領域を，図１４のようにできるだけ連続領域に割り当てることを実現する。これにより，ループ内の命令のキャッシュミスやページフォルト，メモリのフラグメンテーションを防ぎ，高速な実行が可能となる。
【００３１】
（１）ループに着目し，リストアクセスするポインタを見つける。具体的には，図１３のように，ループ中で『ｐ＝ｐ−＞ｎｅｘｔ』のような形式によって構造体ポインタを更新し，『ｐ！＝ＮＵＬＬ（またはｐ＝＝ＮＵＬＬ）』のような終了判定を行うループを検出する。
【００３２】
（２）そのポインタが指す構造体の領域確保／解放を行うための命令，すなわちｍａｌｌｏｃ関数（領域確保命令）／ｆｒｅｅ関数（領域解放命令）を，独自のアロケータ関数（新領域確保命令）／フリー関数（新領域解放命令）に変更する。
【００３３】
独自のアロケータ関数では，最初のアロケート要求時点で要求されたサイズのｎ倍（ｎ≧２）以上となる領域を確保する（この領域サイズをサイズＳバイトとする）。そして，次のアロケート要求からは，最初に確保した領域から必要なサイズだけの領域を切り出すことを繰り返し行う。確保した領域を使い切った場合には，再びサイズＳの領域を確保し，以降のアロケート要求に対しては，新しいＳ領域からの切り出しを行うことで，リストベクトルに対して連続領域を割り当てる。
【００３４】
ただし，（１）において，ループの回転数が静的に判明する場合を除けば，ループが回るかどうかは全く不明である。そこで，以下の３つの手段を利用することで，構造体Ａのためにどのくらいの連続領域を確保すべきかの目安をつけ，妥当な大きさのＳ領域の確保を図る。
【００３５】
〔Ｓ領域のサイズ決定方法〕
（方法１）：プロファイル情報（一度実行してみた結果どの程度の領域を使っていたかを採取する）を利用し，リストベクトルを含むループがどの程度回るかを把握し，何バイトの連続領域をとるかを決定する。すなわち，オブジェクトプログラム２０を試験的に実行させ，その実行履歴情報をプロファイル情報として記録しておき，実行時のループ回数などをもとにＳ領域のサイズを決定する。例えば，１６バイトのサイズの構造体をアクセスするループの回転数が１００であった場合，Ｓ領域のサイズを１６×１００バイトとする。ただし，Ｓ領域のサイズは，キャッシュメモリのサイズを超えないサイズとする。
【００３６】
（方法２）：キャッシュミスを防ぎたいリストベクトルが何バイトの領域を使うかをユーザに指示してもらう。例えば，構造体Ａのアロケート要求として，４００バイト（１要素４バイト×１００個分）の領域を確保する旨の指示情報を，コンパイルオプションのような翻訳時のパラメータとして，ユーザが入力する。
【００３７】
（方法３）：ループは回るという予想のもと，コンパイラが予め設定された設定値に基づき適当にＳ領域サイズを決定する。例えば，ループはＮ回（Ｎは設定値）回ると仮定して，ｓｉｚｅｏｆ（Ａ）＊Ｎバイトの領域をＳ領域として確保する。
【００３８】
図２は，本発明を実行する装置構成例を示す図である。図２において，１０は翻訳対象のソースプログラム，２０は翻訳結果のオブジェクトプログラム，３０はオブジェクトプログラム２０から呼び出されるプログラムが格納されたプログラムライブラリである。プログラムライブラリ３０には，予めｍａｌｌｏｃ関数を処理する領域確保命令処理部３３のプログラム，ｆｒｅｅ関数を処理する領域解放命令処理部３４のプログラムが格納されている。また，リストベクトル用の連続領域を確保，解放するための関数を処理する新領域確保命令処理部３１，新領域解放命令処理部３２の各プログラムも格納されている。
【００３９】
新領域確保命令処理部３１を呼び出す関数を，ここではｌｉｓｔｖｅｃ＿ｍａｌｌｏｃ関数，新領域解放命令処理部３２を呼び出す関数を，ｌｉｓｔｖｅｃ＿ｆｒｅｅ関数として説明する。
【００４０】
処理装置６０は，ＣＰＵおよびメモリ等からなるコンピュータである。コンパイラ７０は，高級言語で記述されたソースプログラム１０を，機械語命令群からなるオブジェクトプログラム２０に翻訳するプログラムである。ソースプログラム解析部７１は，翻訳対象のソースプログラム１０を入力し，構文解析，意味解析などの解析処理を行う。リストベクトル用領域最適化部７２は，リストベクトルループ検出部７３，領域確保／解放命令検出部７４，領域確保／解放命令変換部７５を備える。なお，コンパイラ７０は，他にも種々の最適化部を有しているが，本発明に関係ない部分は従来技術と同様でよいので，その部分の説明は省略する。コード生成部７６は，最適化部の処理結果に基づき，各命令列にレジスタ割付けを行い，機械語コードの命令列をオブジェクトプログラム２０として出力する。
【００４１】
リストベクトル用領域最適化部７２におけるリストベクトルループ検出部７３は，ソースプログラム１０中に，リストベクトルへのアクセスを含むｆｏｒ文，ｗｈｉｌｅ文などのループを検出し，そのループ内で検出されたリストベクトルの型を検出する。領域確保／解放命令検出部７４は，リストベクトルループ検出部７３によって検出されたリストベクトルの領域を確保／解放するｍａｌｌｏｃ関数，ｆｒｅｅ関数を検出する。領域確保／解放命令変換部７５は，検出されたｍａｌｌｏｃ関数，ｆｒｅｅ関数を，それぞれ新領域確保命令処理部３１を呼び出すためのｌｉｓｔｖｅｃ＿ｍａｌｌｏｃ関数，新領域解放命令処理部３２を呼び出すためのｌｉｓｔｖｅｃ＿ｆｒｅｅ関数に変換する。
【００４２】
これにより，オブジェクトプログラム２０の実行時には，ループ内で使用されるリストベクトルの構造体領域を確保／解放するときに，それぞれ新領域確保命令処理部３１および新領域解放命令処理部３２が呼び出されることになる。
【００４３】
図３は，リストベクトル用領域最適化部７２の処理フローチャートである。ステップＳ１，Ｓ２をリストベクトルループ検出部７３が実行し，ステップＳ３を領域確保／解放命令検出部７４が実行し，ステップＳ４を領域確保／解放命令変換部７５が実行する。
【００４４】
ステップＳ１では，まずリストベクトルへのアクセスを含むループ，すなわちリストベクトルの各構造体にポインタを辿ってアクセスする命令を有するループを検出する。検出できなかった場合には，リストベクトル用領域割当ての最適化は行わない。
【００４５】
リストベクトルへのアクセスを含むループを検出できた場合，ステップＳ２では，そのポインタが指標するリストベクトルの型を検出する。検出できなかった場合には，リストベクトル用領域割当ての最適化は行わない。
【００４６】
型を検出したならば，続くステップＳ３では，構造体の領域を確保／解放し，そのポインタを初期化／解放するｍａｌｌｏｃ／ｆｒｅｅ関数を検出する。ステップＳ４では，検出したｍａｌｌｏｃ関数，ｆｒｅｅ関数を，それぞれｌｉｓｔｖｅｃ＿ｍａｌｌｏｃ関数（新領域確保命令），ｌｉｓｔｖｅｃ＿ｆｒｅｅ関数（新領域解放命令）に変換する。
【００４７】
なお，ポインタを初期化するすべてのｍａｌｌｏｃ関数において，構造体１要素分の領域確保を行っている場合に限定し，ｌｉｓｔｖｅｃ＿ｍａｌｌｏｃ関数への変換対象とする。すなわち，
ｍａｌｌｏｃ（ｓｉｚｅｏｆ（構造体名））
でのみ領域確保している場合に限定して，ｍａｌｌｏｃ／ｆｒｅｅ関数を，ｌｉｓｔｖｅｃ＿ｍａｌｌｏｃ／ｌｉｓｔｖｅｃ＿ｆｒｅｅ関数への変換対象とする。
【００４８】
ｌｉｓｔｖｅｃ＿ｍａｌｌｏｃ関数で確保するＳ領域５１のサイズは，例えば次のように決定する。あるリストベクトルの最大必要領域サイズをＭＡＸＳ，１回の領域確保で行う連続割当て用のＳ領域５１のサイズをＳとする。Ｓは，
Ｓ＝ｓｉｚｅｏｆ（Ａ）＊Ｎ  （Ｎは整数）  単位：バイト
であり，
１次キャッシュラインサイズ＊Ｍ≦Ｓ≦ＭＩＮ（ＭＡＸＳ，１次キャッシュのサイズ）    （Ｍは整数）
となるようなＳを選択する。ＭＩＮ（ＭＡＸＳ，１次キャッシュのサイズ）は，ＭＡＸＳと１次キャッシュのサイズのうち，小さいほうである。Ｓが（１次キャッシュラインサイズ＊Ｍ）より小さい場合，本変換は実施しない。
【００４９】
図３のステップＳ４において，ステップＳ３で検出したｍａｌｌｏｃ関数をｌｉｓｔｖｅｃ＿ｍａｌｌｏｃ関数に変換する場合，例えば，
ｐ＝（ｓｔｒｕｃｔ  Ａ  ＊）ｍａｌｌｏｃ（ｓｉｚｅｏｆ（ｓｔｒｕｃｔ  Ａ））；
の命令文を，
ｐ＝（ｓｔｒｕｃｔ  Ａ  ＊）ｌｉｓｔｖｅｃ＿ｍａｌｌｏｃ（ｓｉｚｅｏｆ（ｓｔｒｕｃｔ  Ａ），”ｓｔｒｕｃｔ  Ａ”）；
に変換する。
【００５０】
また，ステップＳ３で検出したｆｒｅｅ関数をｌｉｓｔｖｅｃ＿ｆｒｅｅ関数に変換する場合，例えば，ｆｒｅｅ（ｐ）；を，
ｌｉｓｔｖｅｃ＿ｆｒｅｅ（ｐ）；
に変換する。
【００５１】
図４は，Ｓ領域を型名毎に管理する場合の領域マネージャの例を示している。ｌｉｓｔｖｅｃ＿ｍａｌｌｏｃ関数により呼び出される新領域確保命令処理部３１は，リストベクトルの型名を関数の引数で受け取り，型名ごとに型別領域マネージャ４１−１，４１−２，…を作成し，型別領域マネージャ４１−１，…によって，それぞれＳ領域マネージャ４２−１，…を管理する。Ｓ領域マネージャ４２−１，…は，連続領域である一括確保領域（Ｓ領域）５１−１，…ごとに作成され，型別毎に連鎖される。  
【００５２】
図５は，ｌｉｓｔｖｅｃ＿ｍａｌｌｏｃ関数によって確保される領域の具体例を示している。ｌｉｓｔｖｅｃ＿ｍａｌｌｏｃ関数では，領域確保命令処理部３１に構造体Ａの領域サイズと，型名とが引数として引き渡される。領域確保命令処理部３１は，最初のｌｉｓｔｖｅｃ＿ｍａｌｌｏｃ関数に対してＳバイトのＳ領域５１−１（領域Ｘ）を確保し，１つの構造体５０の領域をＳ領域５１−１の先頭から順番に切り出し，そのアドレスａｄｄｒ１を戻り値として返却する。アドレスａｄｄｒ１がポインタｐ１に格納されることになる。次のｌｉｓｔｖｅｃ＿ｍａｌｌｏｃ関数に対しては，領域確保命令処理部３１は，新たなＳ領域の確保は行わず，既に確保した領域ＸのＳ領域５１−１から１つの構造体５０の領域を切り出し，そのアドレスａｄｄｒ２を戻り値として返却する。アドレスａｄｄｒ２がポインタｐ２に格納されることになる。
【００５３】
領域Ｘを使い切り，領域ＸのＳ領域５１−１から構造体５０の領域を切り出せなくなった場合，領域確保命令処理部３１は，新たなＳ領域５１−２を確保し，そこから１つの構造体５０の領域を切り出して，割当てを行う。図５の例では，９番目のｌｉｓｔｖｅｃ＿ｍａｌｌｏｃ関数に対して，新たなＳ領域５１−２を確保し，そこから切り出した構造体５０のアドレスａｄｄｒ９を戻り値として返却している。アドレスａｄｄｒ９がポインタｐ９に格納されることになる。
【００５４】
図６は，型別領域マネージャおよびＳ領域マネージャの具体例を示している。型別領域マネージャ４１−１，…は，型名ごとに，型名（例えば，”ｓｔｒｕｃｔ＿Ａ”），構造体のサイズ（ｓｉｚｅ），Ｓ領域のサイズ（ｓｉｚｅ＊Ｎ），Ｓ領域マネージャの領域連鎖へのポインタなどの情報を持つ。
【００５５】
Ｓ領域マネージャ４２は，Ｓ領域の先頭アドレス，Ｓ領域において次の構造体領域用に割り当てることができる未使用領域のアドレス，各構造体領域が使用中であるか否かを示す領域状態フラグ，および次のＳ領域マネージャへのポインタなどの情報を持つ。領域状態フラグは，「ｕｓｅｄ」というｂｉｔｖｅｃｔｏｒを用いて表現され，１つのＳ領域からＮ個の構造体領域を切り出すことができる場合，Ｎ個のフラグからなる。各フラグの初期値はＯＦＦ（“０”）であり，先頭からｎ番目の領域を切り出して構造体領域として割り当てた場合には，ｎ番目のフラグがＯＮ（“１”）に変わる。ｌｉｓｔｖｅｃ＿ｆｒｅｅ関数によって，ｎ番目の構造体領域が解放された場合には，領域状態フラグのｎ番目のフラグがＯＦＦ（“０”）に戻される。
【００５６】
図７は，新領域確保命令処理部の処理フローチャートである。新領域確保命令処理部３１は，例えば次のような引数の命令記述で呼び出される。
【００５７】
ｖｏｉｄ  ＊ｌｉｓｔｖｅｃ＿ｍａｌｌｏｃ（ｕｎｉｔ３２＿ｔ  ｓｉｚｅ，ｃｈａｒ  ＊ｔｙｐｅｎａｍｅ）；
まず，ステップＳ１０では，領域サイズがｓｉｚｅで，型名がｔｙｐｅｎａｍｅを持つ型別領域マネージャを検索する。ステップＳ１１では，該当する型別領域マネージャが見つかったかどうかを判定し，該当する型別領域マネージャが見つかった場合，ステップＳ１４へ進む。該当する型別領域マネージャが見つからなかった場合，ステップＳ１２へ進む。
【００５８】
ステップＳ１２では，型別領域マネージャ（ｔｍａｎａｇｅｒ）を新規作成する。型別領域マネージャは，例えば次のように作成されることになる。
【００５９】
型名＝”ｓｔｒｕｃｔ  Ａ”；
ｓｉｚｅ＝ｓｔｒｕｃｔ  Ａのサイズ（バイト数）；
Ｓ＝ｓｉｚｅ＊Ｎ；
ｓｍａｎａｇｅｒ＝Ｓ領域マネージャの新規作成；
ｌａｔｅｓｔ＿Ｓｍａｎａｇｅｒ＝ＮＵＬＬ；  ／＊  最終のＳ領域マネージャへのポインタの初期化  ＊／
ステップＳ１３では，上記「ｓｍａｎａｇｅｒ＝Ｓ領域マネージャの新規作成；」の処理として，Ｓ領域マネージャ（ｓｍａｎａｇｅｒ）が次のように作成される。
【００６０】
ｓｔａｒｔ＝ｍａｌｌｏｃ（Ｓ）；    ／＊  サイズＳのＳ領域確保  ＊／
ｎｅｘｔ＿ｆｒｅｅ＝ｓｔａｒｔ；    ／＊  未使用領域ポインタの初期化  ＊／
ｂｉｔｖｅｃｔｏｒ  ｕｓｅｄ；      ／＊  領域状態フラグの初期化  ＊／
ｎｅｘｔ＿ｓｍａｎａｇｅｒ＝ＮＵＬＬ；    ／＊  次のＳ領域への連鎖の初期化  ＊／
その後，ステップＳ１７へ進む。
【００６１】
ステップＳ１４，Ｓ１５では，連鎖の最終のＳ領域マネージャが管理するＳ領域の未使用領域（空領域）を検索し，未使用領域があるかどうかを判定する。ここでは，以下の判定を行う。
【００６２】
ｌａｔｅｓｔ＿Ｓｍａｎａｇｅｒ＝ｔｍａｎａｇｅｒ−＞ｓｍａｎａｇｅｒ；
ｌａｔｅｓｔ＿Ｓｍａｎａｇｅｒ−＞ｎｅｘｔ＿ｆｒｅｅ                            ＞＝ｌａｔｅｓｔ＿Ｓｍａｎａｇｅｒ−＞ｓｔａｒｔ＋Ｓ；
未使用領域があれば，ステップＳ１７へ進み，最終のＳ領域に未使用領域が残っていなければ，ステップＳ１６へ進む。
【００６３】
ステップＳ１６では，次のようにＳ領域マネージャ（ｓｍａｎａｇｅｒ）の新規作成処理を行う。
【００６４】
ｎｅｗ＿Ｓｍａｎａｇｅｒ＝Ｓ領域マネージャの新規作成；
ｔｍａｎａｇｅｒ−＞ｓｍａｎａｇｅｒ＝ｎｅｗ＿Ｓｍａｎａｇｅｒ；
ｎｅｗ＿Ｓｍａｎａｇｅｒ−＞ｎｅｘｔ＿ｓｍａｎａｇｅｒ＝ｌａｔｅｓｔ＿Ｓｍａｎａｇｅｒ；
ｌａｔｅｓｔ＿Ｓｍａｎａｇｅｒ＝ｎｅｗ＿Ｓｍａｎａｇｅｒ；
先頭行の「ｎｅｗ＿Ｓｍａｎａｇｅｒ＝Ｓ領域マネージャの新規作成；」では，ステップＳ１３と同様に次の処理が行われる。
【００６５】
ｓｔａｒｔ＝ｍａｌｌｏｃ（Ｓ）；    ／＊  サイズＳのＳ領域確保  ＊／
ｎｅｘｔ＿ｆｒｅｅ＝ｓｔａｒｔ；    ／＊  未使用領域ポインタの初期化  ＊／
ｂｉｔｖｅｃｔｏｒ  ｕｓｅｄ；      ／＊  領域状態フラグの初期化  ＊／
ｎｅｘｔ＿ｓｍａｎａｇｅｒ＝ＮＵＬＬ；／＊  次のＳ領域への連鎖の初期化  ＊／
ステップＳ１７，Ｓ１８では，構造体への割当て領域をＳ領域から切り出し，その領域状態フラグをＯＮにし，未使用領域ポインタを更新する。Ｓ領域から切り出した割当て領域のアドレスを，領域確保の要求元（ｌｉｓｔｖｅｃ＿ｍａｌｌｏｃ関数の発行元）へ返却し，処理を終了する。具体的には，次のような処理が行われる。
【００６６】
ｎ＝ｇｅｔ＿ｎｂｉｔ（ｌａｔｅｓｔ＿Ｓｍａｎａｇｅｒ，ｌａｔｅｓｔ＿Ｓｍａｎａｇｅｒ−＞ｎｅｘｔ＿ｆｒｅｅ）；
ｌａｔｅｓｔ＿Ｓｍａｎａｇｅｒが管理しているのは，Ｎ個の領域であり，ｇｅｔ＿ｎｂｉｔ（）は，引数のｌａｔｅｓｔ＿Ｓｍａｎａｇｅｒ−＞ｎｅｘｔ＿ｆｒｅｅが何番目の領域かを返す関数である。
【００６７】
該当する領域状態フラグの設定は，次の関数によって行われる。
【００６８】
ｂｉｔｖｅｃｔｏｒ＿ｏｎ（ｌａｔｅｓｔ＿Ｓｍａｎａｇｅｒ−＞ｕｓｅｄ，ｎ）；
これは，ｎ番目の領域状態フラグをＯＮにし，ｎ番目の領域が使用中であることを示す。
【００６９】
割当て領域アドレスは，ｌａｔｅｓｔ＿Ｓｍａｎａｇｅｒ−＞ｎｅｘｔ＿ｆｒｅｅである。未使用領域ポインタの更新は，次のように行う。
【００７０】
ｌａｔｅｓｔ＿Ｓｍａｎａｇｅｒ−＞ｎｅｘｔ＿ｆｒｅｅ＋＝ｓｉｚｅ；
割当て領域アドレスの返却は，
ｒｅｔｕｒｎ  割当て領域アドレス；
である。
【００７１】
図８は，新領域解放命令処理部の処理フローチャートである。新領域解放命令処理部３２は，例えば次のような引数の命令記述で呼び出される。
【００７２】
ｖｏｉｄ  ｌｉｓｔｖｅｃ＿ｆｒｅｅ（ｖｏｉｄ  ＊ｐ）；
新領域解放命令処理部３２は，ｌｉｓｔｖｅｃ＿ｆｒｅｅ関数によって，引数のアドレスｐからのｓｉｚｅバイトが不要となったときに呼び出される。
【００７３】
ステップＳ２０では，渡された引数のアドレスｐを管理している型別領域マネージャ（ｔｍａｎａｇｅｒ）およびＳ領域マネージャ（ｓｍａｎａｇｅｒ）を，引数のアドレスｐをもとに検索する。ステップＳ２１では，その検索したＳ領域マネージャが管理するｂｉｔｖｅｃｔｏｒ  ｕｓｅｄに対し，引数のアドレスｐに相当する領域状態フラグをＯＦＦにする。すなわち，
ｎ＝ｇｅｔ＿ｎｂｉｔ（ｓｍａｎａｇｅｒ，ｐ）；
によって，アドレスｐが先頭からｎ番目のフラグであることを取得し，
ｂｉｔｖｅｃｔｏｒ＿ｏｆｆ（ｓｍａｎａｇｅｒ−＞ｕｓｅｄ，ｎ）；
によって，該当する領域状態フラグをＯＦＦにする。
【００７４】
次に，ステップＳ２２では，そのＳ領域マネージャの領域状態フラグ（ｕｓｅｄ）がすべてＯＦＦになったかどうかを判定し，ＯＮのフラグがあれば，そのまま処理を終了する。すべての領域状態フラグがＯＦＦになったならば，そのＳ領域マネージャは不要となるため，ステップＳ２３へ進み，そのＳ領域マネージャが管理する領域を解放し，そのＳ領域マネージャを型別領域マネージャの管理から外す。すなわち，
ｆｒｅｅ（ｓｍａｎａｇｅｒ−＞ｓｔａｒｔ）；
のｆｒｅｅ関数（領域解放命令）により，Ｓ領域を解放し，型別領域マネージャ管理下のＳｍａｎａｇｅｒリストからｓｍａｎａｇｅｒを外す。
【００７５】
これら一連の操作により，構造体Ａのリストベクトル全体は無理でも，ある程度まとまった連続領域（サイズＳ）をリストベクトルに対して割り当てることが可能となる。
【００７６】
以上では，リストベクトルの型名をｌｉｓｔｖｅｃ＿ｍａｌｌｏｃ関数，ｌｉｓｔｖｅｃ＿ｆｒｅｅ関数の引数とし，新領域確保命令処理部３１，新領域解放命令処理部３２では，型別にＳ領域を管理する例を説明した。
【００７７】
本発明は，型別領域マネージャを設けてＳ領域を型別に管理するのではなく，新領域確保命令処理部３１，新領域解放命令処理部３２を，予め型別に用意する実装も可能である。すなわち，ｌｉｓｔｖｅｃ＿ｍａｌｌｏｃ／ｌｉｓｔｖｅｃ＿ｆｒｅｅ関数を構造体毎に別関数にする実装でも，上述した例と同じことが可能となる。
【００７８】
図９は，型別に用意された新領域確保命令処理部の処理フローチャートである。例えば，構造体Ａ用の新領域確保命令処理部３１は，次のような引数の命令記述で呼び出される。
【００７９】
ｖｏｉｄ  ＊ｌｉｓｔｖｅｃ＿ｍａｌｌｏｃ＿ｆｏｒＡ（ｕｎｉｔ３２＿ｔ  ｓｉｚｅ）；
型別の新領域確保命令処理部３１では，基本的に図６のＳ領域マネージャ４２だけを待つと考えてよい。
【００８０】
まず，ステップＳ３０では，構造体Ａ用のＳ領域マネージャが存在するかどうかを，
ｌａｔｅｓｔ＿Ｓｍａｎａｇｅｒ＝＝ＮＵＬＬ？
が真かどうかによって判定する。Ｓ領域マネージャが存在する場合，ステップＳ３２へ進む。Ｓ領域マネージャがない場合，すなわち，ｌａｔｅｓｔ＿ＳｍａｎａｇｅｒがＮＵＬＬの場合には，ステップＳ３１へ進む。
【００８１】
ステップＳ３１では，Ｓ領域マネージャを新規作成する。
【００８２】
ｌａｔｅｓｔ＿Ｓｍａｎａｇｅｒ＝Ｓ領域マネージャの新規作成；
この「Ｓ領域マネージャの新規作成」では，
ｓｔａｒｔ＝ｍａｌｌｏｃ（Ｓ）；    ／＊  サイズＳのＳ領域確保  ＊／
ｎｅｘｔ＿ｆｒｅｅ＝ｓｔａｒｔ；    ／＊  未使用領域ポインタの初期化  ＊／
ｂｉｔｖｅｃｔｏｒ  ｕｓｅｄ；      ／＊  領域状態フラグの初期化  ＊／
ｎｅｘｔ＿ｓｍａｎａｇｅｒ＝ＮＵＬＬ；    ／＊  次のＳ領域への連鎖の初期化  ＊／
の処理が行われる。その後，ステップＳ３５へ進む。
【００８３】
ステップＳ３２，Ｓ３３では，連鎖の最終のＳ領域マネージャが管理するＳ領域の未使用領域（空領域）を検索し，未使用領域があるかどうかを判定する。ここでは，以下の判定を行う。
【００８４】
ｌａｔｅｓｔ＿Ｓｍａｎａｇｅｒ−＞ｎｅｘｔ＿ｆｒｅｅ                            ＞＝ｌａｔｅｓｔ＿Ｓｍａｎａｇｅｒ−＞ｓｔａｒｔ＋Ｓ；
未使用領域があれば，ステップＳ３５へ進み，最終のＳ領域に未使用領域が残っていなければ，ステップＳ３４へ進む。
【００８５】
ステップＳ３４では，次のようにＳ領域マネージャ（ｓｍａｎａｇｅｒ）の新規作成処理を行う。
【００８６】
ｎｅｗ＿Ｓｍａｎａｇｅｒ＝Ｓ領域マネージャの新規作成；
ｎｅｗ＿Ｓｍａｎａｇｅｒ−＞ｎｅｘｔ＿ｓｍａｎａｇｅｒ＝ｌａｔｅｓｔ＿Ｓｍａｎａｇｅｒ；
ｌａｔｅｓｔ＿Ｓｍａｎａｇｅｒ＝ｎｅｗ＿Ｓｍａｎａｇｅｒ；
先頭行の「ｎｅｗ＿Ｓｍａｎａｇｅｒ＝Ｓ領域マネージャの新規作成；」では，ステップＳ３１と同様に次の処理が行われる。
【００８７】
ｓｔａｒｔ＝ｍａｌｌｏｃ（Ｓ）；    ／＊  サイズＳのＳ領域確保  ＊／
ｎｅｘｔ＿ｆｒｅｅ＝ｓｔａｒｔ；    ／＊  未使用領域ポインタの初期化  ＊／
ｂｉｔｖｅｃｔｏｒ  ｕｓｅｄ；      ／＊  領域状態フラグの初期化  ＊／
ｎｅｘｔ＿ｓｍａｎａｇｅｒ＝ＮＵＬＬ；／＊  次のＳ領域への連鎖の初期化  ＊／
ステップＳ３５，Ｓ３６では，構造体への割当て領域をＳ領域から切り出し，その領域状態フラグをＯＮにし，未使用領域ポインタを更新する。Ｓ領域から切り出した割当て領域のアドレスを，領域確保の要求元（関数の発行元）へ返却し，処理を終了する。具体的には，次のような処理が行われる。
【００８８】
ｎ＝ｇｅｔ＿ｎｂｉｔ（ｌａｔｅｓｔ＿Ｓｍａｎａｇｅｒ，ｌａｔｅｓｔ＿Ｓｍａｎａｇｅｒ−＞ｎｅｘｔ＿ｆｒｅｅ）；
ｌａｔｅｓｔ＿Ｓｍａｎａｇｅｒが管理しているのは，Ｎ個の領域であり，ｇｅｔ＿ｎｂｉｔ（）は，引数のｌａｔｅｓｔ＿Ｓｍａｎａｇｅｒ−＞ｎｅｘｔ＿ｆｒｅｅが何番目の領域かを返す関数である。
【００８９】
該当する領域状態フラグの設定は，次の関数によって行われる。
【００９０】
ｂｉｔｖｅｃｔｏｒ＿ｏｎ（ｌａｔｅｓｔ＿Ｓｍａｎａｇｅｒ−＞ｕｓｅｄ，ｎ）；
これは，ｎ番目の領域状態フラグをＯＮにし，ｎ番目の領域が使用中であることを示す。
【００９１】
割当て領域アドレスは，ｌａｔｅｓｔ＿Ｓｍａｎａｇｅｒ−＞ｎｅｘｔ＿ｆｒｅｅである。未使用領域ポインタの更新は，次のように行う。
【００９２】
ｌａｔｅｓｔ＿Ｓｍａｎａｇｅｒ−＞ｎｅｘｔ＿ｆｒｅｅ＋＝ｓｉｚｅ；
割当て領域アドレスの返却は，
ｒｅｔｕｒｎ  割当て領域アドレス；
である。
【００９３】
図１０は，型別に用意された新領域解放命令処理部の処理フローチャートである。型別の新領域解放命令処理部３２は，例えば次のような引数の命令記述で呼び出される。
【００９４】
ｖｏｉｄ  ｌｉｓｔｖｅｃ＿ｆｒｅｅ＿ｆｏｒＡ（ｖｏｉｄ  ＊ｐ）；
新領域解放命令処理部３２は，引数のアドレスｐからのｓｉｚｅバイトが不要となったときに呼び出される。
【００９５】
ステップＳ４０では，ｌａｔｅｓｔ＿Ｓｍａｎａｇｅｒから始まるＳ領域マネージャ（ｓｍａｎａｇｅｒ）の連鎖から，引数で渡されたアドレスｐを管理しているＳ領域マネージャを検索する。ステップＳ４１では，その検索したＳ領域マネージャが管理するｂｉｔｖｅｃｔｏｒ  ｕｓｅｄに対し，引数のアドレスｐに相当する領域状態フラグをＯＦＦにする。すなわち，
ｎ＝ｇｅｔ＿ｎｂｉｔ（ｓｍａｎａｇｅｒ，ｐ）；
によって，アドレスｐが先頭からｎ番目のフラグであることを取得し，
ｂｉｔｖｅｃｔｏｒ＿ｏｆｆ（ｓｍａｎａｇｅｒ−＞ｕｓｅｄ，ｎ）；
によって，該当する領域状態フラグをＯＦＦにする。
【００９６】
次に，ステップＳ４２では，そのＳ領域マネージャの領域状態フラグ（ｕｓｅｄ）がすべてＯＦＦになったかどうかを判定し，ＯＮのフラグがあれば，そのまま処理を終了する。すべての領域状態フラグがＯＦＦになったならば，そのＳ領域マネージャは不要となるため，ステップＳ４３へ進み，そのＳ領域マネージャが管理する領域を解放し，そのＳ領域マネージャを管理用の連鎖から外す。すなわち，
ｆｒｅｅ（ｓｍａｎａｇｅｒ−＞ｓｔａｒｔ）；
のｆｒｅｅ関数（領域解放命令）により，Ｓ領域を解放し，Ｓｍａｎａｇｅｒリストからｓｍａｎａｇｅｒを外す。もし，ｓｍａｎａｇｅｒがｌａｔｅｓｔ＿Ｓｍａｎａｇｅｒである場合には，ｌａｔｅｓｔ＿Ｓｍａｎａｇｅｒは，ｓｍａｎａｇｅｒ−＞ｎｅｘｔ＿ｓｍａｎａｇｅｒとなる。
【００９７】
以上説明したコンパイラ７０および新領域確保命令処理部３１，新領域解放命令処理部３２が行う処理は，コンピュータとソフトウェアプログラムとによって実現することができ，そのプログラムをコンピュータ読み取り可能な記録媒体に記録して提供することも，ネットワークを通して提供することも可能である。
【００９８】
以上の本発明の実施の形態の特徴を列挙すると，以下のとおりである。
【００９９】
（付記１）
ソースプログラムを入力し，オブジェクトプログラムに翻訳するコンパイラプログラムであって，
コンピュータを，
ソースプログラムを解析した結果に基づき，複数の構造体の連鎖からなるリストベクトルへのアクセスを含むループを検出するリストベクトルループ検出手段と，
前記検出したループ内でアクセスされるリストベクトルにおける構造体の領域をメモリから確保する命令および解放する命令を検出する領域確保／解放命令検出手段と，
前記検出した構造体の領域を確保する命令を，最初の呼出し時には前記構造体の領域サイズのｎ倍（ｎ≧２）以上のサイズの連続領域を確保し，その連続領域から構造体の領域を切り出して割り当て，２回目以降の呼出し時には確保済みの前記連続領域から構造体の領域を切り出して割り当てる新領域確保命令処理部を呼び出す新領域確保命令に書き換え，前記検出した構造体の領域を解放する命令を，前記連続領域における構造体の領域の使用状況を管理し，構造体の領域がすべて未使用状態になったときに，当該連続領域を解放する新領域解放命令処理部を呼び出す新領域解放命令に書き換える領域確保／解放命令変換手段と，
前記領域確保／解放命令変換手段によって変換された命令を含むコードを生成し，オブジェクトプログラムとして出力するコード生成手段として
機能させるためのコンパイラプログラム。
【０１００】
（付記２）
付記１記載のコンパイラプログラムにおいて，
前記新領域確保命令処理部によって確保される連続領域のサイズを定めるｎの値が，前記オブジェクトプログラムの試験走行において採取された前記ループが実行された回数を記録したプロファイル情報に基づき決定されたものである
ことを特徴とするコンパイラプログラム。
【０１０１】
（付記３）
付記１記載のコンパイラプログラムにおいて，
前記新領域確保命令処理部によって確保される連続領域のサイズを定めるｎの値が，コンパイル時のオプション情報によって決定されたもの，またはオブジェクトプログラムの実行時のパラメータとして指定されたものである
ことを特徴とするコンパイラプログラム。
【０１０２】
（付記４）
付記１記載のコンパイラプログラムにおいて，
前記新領域確保命令処理部によって確保される連続領域のサイズを定めるｎの値が，コンパイラの設定値として予め定められたものである
ことを特徴とするコンパイラプログラム。
【０１０３】
（付記５）
付記１から付記４までのいずれかに記載のコンパイラプログラムにおいて，
前記新領域確保命令処理部によって確保される連続領域のサイズが，前記オブジェクトプログラムが走行するコンピュータが持つキャッシュメモリのサイズより小さく，該キャッシュメモリのラインサイズより大きいサイズである
ことを特徴とするコンパイラプログラム。
【０１０４】
（付記６）
ソースプログラムを入力し，オブジェクトプログラムに翻訳するコンパイラプログラムを搭載するコンピュータが実行するリストベクトルの領域割当て最適化方法であって，
ソースプログラムを解析した結果に基づき，複数の構造体の連鎖からなるリストベクトルへのアクセスを含むループを検出するリストベクトルループ検出過程と，
前記検出したループ内でアクセスされるリストベクトルにおける構造体の領域をメモリから確保する命令および解放する命令を検出する領域確保／解放命令検出過程と，
前記検出した構造体の領域を確保する命令を，最初の呼出し時には前記構造体の領域サイズのｎ倍（ｎ≧２）以上のサイズの連続領域を確保し，その連続領域から構造体の領域を切り出して割り当て，２回目以降の呼出し時には確保済みの前記連続領域から構造体の領域を切り出して割り当てる新領域確保命令処理部を呼び出す新領域確保命令に書き換え，前記検出した構造体の領域を解放する命令を，前記連続領域における構造体の領域の使用状況を管理し，構造体の領域がすべて未使用状態になったときに，当該連続領域を解放する新領域解放命令処理部を呼び出す新領域解放命令に書き換える領域確保／解放命令変換過程と，
前記領域確保／解放命令変換過程によって変換された命令を含むコードを生成し，オブジェクトプログラムとして出力するコード生成過程を有する
ことを特徴とするリストベクトルの領域割当て最適化方法。
【０１０５】
（付記７）
ソースプログラムを入力し，オブジェクトプログラムに翻訳するコンパイラプログラムを搭載したコンピュータによるコンパイル処理装置であって，
ソースプログラムを解析した結果に基づき，複数の構造体の連鎖からなるリストベクトルへのアクセスを含むループを検出するリストベクトルループ検出手段と，
前記検出したループ内でアクセスされるリストベクトルにおける構造体の領域をメモリから確保する命令および解放する命令を検出する領域確保／解放命令検出手段と，
前記検出した構造体の領域を確保する命令を，最初の呼出し時には前記構造体の領域サイズのｎ倍（ｎ≧２）以上のサイズの連続領域を確保し，その連続領域から構造体の領域を切り出して割り当て，２回目以降の呼出し時には確保済みの前記連続領域から構造体の領域を切り出して割り当てる新領域確保命令処理部を呼び出す新領域確保命令に書き換え，前記検出した構造体の領域を解放する命令を，前記連続領域における構造体の領域の使用状況を管理し，構造体の領域がすべて未使用状態になったときに，当該連続領域を解放する新領域解放命令処理部を呼び出す新領域解放命令に書き換える領域確保／解放命令変換手段と，
前記領域確保／解放命令変換手段によって変換された命令を含むコードを生成し，オブジェクトプログラムとして出力するコード生成手段とを備える
ことを特徴とするコンパイル処理装置。
【０１０６】
（付記８）
ソースプログラムを入力し，オブジェクトプログラムに翻訳するコンパイラプログラムを記録したコンピュータ読み取り可能な記録媒体であって，
コンピュータを，
ソースプログラムを解析した結果に基づき，複数の構造体の連鎖からなるリストベクトルへのアクセスを含むループを検出するリストベクトルループ検出手段と，
前記検出したループ内でアクセスされるリストベクトルにおける構造体の領域をメモリから確保する命令および解放する命令を検出する領域確保／解放命令検出手段と，
前記検出した構造体の領域を確保する命令を，最初の呼出し時には前記構造体の領域サイズのｎ倍（ｎ≧２）以上のサイズの連続領域を確保し，その連続領域から構造体の領域を切り出して割り当て，２回目以降の呼出し時には確保済みの前記連続領域から構造体の領域を切り出して割り当てる新領域確保命令処理部を呼び出す新領域確保命令に書き換え，前記検出した構造体の領域を解放する命令を，前記連続領域における構造体の領域の使用状況を管理し，構造体の領域がすべて未使用状態になったときに，当該連続領域を解放する新領域解放命令処理部を呼び出す新領域解放命令に書き換える領域確保／解放命令変換手段と，
前記領域確保／解放命令変換手段によって変換された命令を含むコードを生成し，オブジェクトプログラムとして出力するコード生成手段として
機能させるためのコンパイラプログラムを記録したコンピュータ読み取り可能な記録媒体。
【図面の簡単な説明】
【０１０７】
【図１】本発明の概要を説明する図である。
【図２】本発明を実行する装置構成例を示す図である。
【図３】リストベクトル用領域最適化部７２の処理フローチャートである。
【図４】Ｓ領域を型名毎に管理する場合の領域マネージャの例を示す図である。
【図５】ｌｉｓｔｖｅｃ＿ｍａｌｌｏｃ関数によって確保される領域の具体例を示す図である。
【図６】型別領域マネージャおよびＳ領域マネージャの具体例を示す図である。
【図７】新領域確保命令処理部の処理フローチャートである。
【図８】新領域解放命令処理部の処理フローチャートである。
【図９】型別に用意された新領域確保命令処理部の処理フローチャートである。
【図１０】型別に用意された新領域解放命令処理部の処理フローチャートである。
【図１１】リストベクトルの説明図である。
【図１２】リストベクトル領域のメモリ割当ての例を示す図である。
【図１３】リストベクトルをアクセスするループを持つプログラムの例を示す図である。
【図１４】リストベクトル領域のメモリ割当ての例を示す図である。
【符号の説明】
【０１０８】
１０  ソースプログラム
２０  オブジェクトプログラム
３０  プログラムライブラリ
３１  新領域確保命令処理部
３２  新領域解放命令処理部
３３  領域確保命令処理部
３４  領域解放命令処理部
４０  領域マネージャ
４１  型別領域マネージャ
４２  Ｓ領域マネージャ
５０  構造体
５１  一括確保領域（Ｓ領域）
６０  処理装置
７０  コンパイラ
７１  ソースプログラム解析部
７２  リストベクトル用領域最適化部
７３  リストベクトルループ検出部
７４  領域確保／解放命令検出部
７５  領域確保／解放命令変換部
７６  コード生成部
【図１】
2008003882.tif 000003
【図２】
2008003882.tif 000004
【図３】
2008003882.tif 000005
【図４】
2008003882.tif 000006
【図５】
2008003882.tif 000007
【図６】
2008003882.tif 000008
【図７】
2008003882.tif 000009
【図８】
2008003882.tif 000010
【図９】
2008003882.tif 000011
【図１０】
2008003882.tif 000012
【図１１】
2008003882.tif 000013
【図１２】
2008003882.tif 000014
【図１３】
2008003882.tif 000015
【図１４】
2008003882.tif 000016