(57)【特許請求の範囲】
【請求項１】
高級言語で書かれたプログラムを機械語プログラムに翻訳するコンパイラに用いられ、プログラミング言語で記述されたプログラムの中の変数と生存区間の組である割付対象を複数個生成し、生成した割付対象に順次レジスタ、メモリ等のハードウェアである資源が有する資源要素を割り付ける資源割付装置であって、
次に割り付けるべき割付対象にどの資源要素が適切かを示す得失値を、資源要素に既に割り付けられた割付対象の生存区間と次に割り付けるべき割付対象の生存区間とがプログラムにおいてどのような位置関係にあるかに基づいて、各資源要素について算出する得失値算出手段と、
各資源要素について算出された得失値の大きさに基づいて何れかの資源要素を割り付けるべき割付対象に割り付ける割付手段と、
全ての割付対象が割り付けられるまで得失値算出手段及び割付手段の起動を繰り返す制御手段と
を備えることを特徴とする資源割付装置。
【請求項２】
請求項１記載の資源割付装置は、
プログラム中の各割付対象の位置関係を判定する位置関係判定手段を有し、
前記位置関係判定手段は、
既に資源要素が割り付けられた割付対象の生存区間が、割り付けるべき割付対象の生存区間と重複しているかを判定する重複関係判定手段と、
資源要素が既に割り付けられた割付対象の生存区間と、割り付けるべき割付対象の生存区間とが連続しているかを判定する割付済み−被割付間連続判定手段とを備え、
前記得失値算出手段は、
割付済み−被割付間連続判定手段によって割り付けるべき割付対象と生存区間が連続していることが判定されると、資源要素が既に割り付けられた割付対象から割り付けるべき割付対象までの生存区間長の短さに応じて、連続が判定された割付済みの割付対象に既に割り付けられている資源要素の得失値を増加させる第１の増加部と、
前記割付手段は、
重複関係判定手段によって生存区間が重複していることが判定された重複している生存区間を有する割付済みの割付対象に割り付けられている資源要素を割り付けるべき割付対象に割り付けず、生存区間が重複していないことが判定された割付済みの割付対象のうち、得失値が最大の資源要素を割り付けるべき割付対象に割り付ける
ことを特徴とする資源割付装置。
【請求項３】
請求項２記載の資源割付装置において位置関係判定手段は、
資源要素が既に割り付けられた割付対象と重なる生存区間を有する未割り付けの割付対象を検出する第１の割付済み側重なり割付対象検出手段と、
検出された未割り付けの割付対象の生存区間と、割り付けるべき割付対象の生存区間とが連続しているかを判定する未割り付け−被割付間連続判定手段とを備え、
前記得失値算出手段は、
連続すると判定されると、第１の割付済み側重なり割付対象検出手段によって検出された未割り付けの割付対象から割り付けるべき割付対象までの生存区間長の短さに応じて、当該割付済みの割付対象に割り付けられている資源要素の得失値を減少させる第１の減少部
を備えることを特徴とする資源割付装置。
【請求項４】
請求項３記載の資源割付装置において第１の割付済み側重なり割付対象検出手段によって複数個の未割り付けの割付対象が判定された場合、
前記未割り付け−被割付間連続判定手段は
検出された複数個の未割り付けの割付対象のうち、何れかのものの生存区間と、割り付けるべき割付対象の生存区間とが連続しているかを判定する
ことを特徴とする資源割付装置。
【請求項５】
請求項３記載の資源割付装置は、
プログラムにおける割付対象の使用頻度及び／又は生存区間のネストレベルが反映された割付対象の優先度を各割付対象に対応づけて記憶する優先度記憶手段を備え、
前記得失値算出手段及び割付手段は、優先度記憶手段が記憶する優先度順に、割り付けるべき割付対象を決定する
ことを特徴とする資源割付装置。
【請求項６】
請求項５記載の資源割付装置において位置関係判定手段は、
各資源要素について得失値算出手段によって算出された得失値が複数個の資源要素同士で同一の大きさになった場合、割り付けるべき割付対象の生存区間と重なる生存区間を有する未割り付けの割付対象を検出する被割付側重なり割付対象検出手段と、
検出された割付対象の生存区間と、資源要素が既に割り付けられた割付対象の生存区間とが連続しているかを判定する未割り付け−割付済み間連続判定手段とを備え、
前記得失値算出手段は、
被割付側重なり割付対象検出部によって検出された割付対象の優先度を検出する優先度検出部と、
割付済みの割付対象から検出された未割り付けの割付対象までの生存区間長の短さを算出する第１の短さ算出部と、
検出された優先度に算出された短さを乗じ、その乗算結果に応じて当該割付済みの資源要素の得失値を減少させる第２の減少部と
を備えることを特徴とする資源割付装置。
【請求項７】
請求項６記載の資源割付装置において位置関係判定手段は、
資源要素が既に割り付けられた割付対象の生存区間と重なる生存区間を有する未割り付けの割付対象を検出する第２の割付済み側重なり割付対象検出手段と、
被割付側重なり割付対象検出手段によって検出された未割り付けの割付対象の生存区間と、第２の割付済み側重なり割付対象検出手段によって検出された未割り付けの割付対象の生存区間とが連続しているかを判定する未割り付け−未割り付け間連続判定手段とを備え、
前記得失値算出手段は、
被割付側重なり割付対象検出手段によって検出された未割り付けの割付対象から第２の割付済み側重なり割付対象検出手段によって検出された未割り付けの割付対象までの生存区間長の短さを算出する第２の短さ算出部と、
検出された優先度に算出された短さを乗じ、その乗算結果に応じて割付済みの割付対象に割り付けられた資源要素の得失値を増加させる第２の増加部と
を備えることを特徴とする資源割付装置。
【請求項８】
請求項７記載の資源割付装置において第２の割付済み側重なり割付対象検出手段によって複数個の未割り付けの割付対象が判定された場合、
前記未割り付け−未割り付け間連続判定手段は
検出された複数個の未割り付けの割付対象のうち、何れかのものの生存区間と、割り付けるべき割付対象の生存区間とが連続しているかを判定する
ことを特徴とする資源割付装置。
【請求項９】
請求項７記載の資源割付装置は、
全ての資源要素と、各々の資源要素の得失値の初期値とを対応づけて記憶する得失値記憶部を備え、
第１及び第２の増加部は、得失値記憶部に記憶されている各資源要素の得失値を増加させ、第１及び第２の減少部は得失値記憶部に記憶されている各資源要素の得失値を減少させる
ことを特徴とする資源割付装置。
【請求項１０】
請求項９記載の資源割付装置は更に、
プログラムにおいて各資源の資源要素を割り付けると、割り付けるべき割付対象が定義されている全ての定義命令及び使用されている全ての使用命令の実行サイクルおよび／又はコードサイズの集計値がどれだけになるかを割り付けるべき割付対象と各資源要素との組み合わせについてその集計値の推定値を算出することで推定する推定手段と、
各資源要素毎の推定結果である推定値を比較し、推定値が最小である資源要素が１つか複数かを判定する資源要素単複判定手段とを備え、
前記割付手段は
１つと判定された場合、割り付けるべき割付対象に推定値が最小である資源要素を割り付け、複数個と判定された場合、得失値が最大の資源要素を割り付けるべき割付対象に割り付ける
ことを特徴とする資源割付装置。
【請求項１１】
請求項１０記載の資源割付装置において推定手段は、
機械語命令の命令フォーマットを用いてプログラム中の割付対象の定義命令及び使用命令を表現した情報である命令パタンをプログラム中における当該割付対象の全ての定義命令及び使用命令について出力する命令パタン出力部と、
機械語命令の各オペランドに各資源の資源要素を用いた場合の当該定義命令及び使用命令の実行サイクルおよび／又はコードサイズを示すコストを命令パタン出力部によって出力され得る命令パタンのそれぞれに対応づけて記憶するコスト記憶部と、
コスト記憶部から出力された命令パタンに対応するコストを取り出し、取り出したコストを各資源要素毎に集計し、集計した集計値を推定値とするコスト集計部と
を備えることを特徴とする資源割付装置。
【請求項１２】
請求項１０記載の資源割付装置は更に、
各資源要素について得失値算出手段によって算出された得失値が複数個の異なる資源の資源要素同士で同一の大きさになった場合、割り付けるべき割付対象より優先度が低く、割り付けるべき割付対象の後に割り付けられる全ての未割り付けの割付対象に最も相応しい資源要素を予測する予測手段を備え、
前記割付手段は、
予測手段によって予測された資源要素を割り付けるべき割付対象に割り付ける
ことを特徴とする資源割付装置。
【請求項１３】
請求項１２記載の資源割付装置において前記予測手段は、
割り付けるべき割付対象が有する生存区間と連続する生存区間を有し且つ当該割付対象より優先度が低い未割り付けの割付対象を全て検出する第１の後順割付対象検出手段と、
検出された各割付対象に各資源要素を割り付けたとすると当該割付対象が定義されている全ての定義命令及び使用されている全ての使用命令の実行サイクルおよび／又はコードサイズの集計値がどれだけになるかを第１の後順割付対象検出手段に検出された全ての割付対象と各資源要素との組み合わせについて当該集計値の推定値を算出することにより推定する第１の推定手段と、
第１の後順割付対象検出手段によって検出された各割付対象と割り付けるべき割付対象との間に介在する生存区間長を第１の後順割付対象検出手段によって検出された各割付対象毎に計数する第１の生存区間長計数手段と、
検出された各割付対象と各資源要素との組み合わせに対して第１の推定手段によって算出された推定値にその割付対象に対して計数された生存区間長の短さを重みとして重み付けを行う第１の重み付け手段と、
第１の重み付け手段によって重み付けられた推定値を各資源要素毎に集計する第１の集計手段と、
第１の集計手段によって集計された集計結果が最も小さい資源要素を割り付けるべき割付対象より優先度が低い未割り付けの割付対象に最も相応しい資源要素と判定する第１の最適資源要素判定手段と
を備えることを特徴とする資源割付装置。
【請求項１４】
請求項１３記載の資源割付装置において予測手段は、
第１の最適資源要素判定手段によって複数個の資源要素が最も相応しいと判定された場合、割り付けるべき割付対象と生存区間が重なる未割り付けの割付対象及びその未割り付けの割付対象の生存区間と連続する生存区間を有する未割り付けの割付対象を検出する第２の後順割付対象検出手段と、
第２の後順割付対象検出手段によって検出された未割り付けの割付対象に各資源要素を割り付けたとすると、検出された各割付対象が定義されている全ての定義命令及び使用されている全ての使用命令の実行サイクルおよび／又はコードサイズの集計値がどれだけになるかを検出された割付対象と各資源要素との組み合わせについて当該集計値の推定値を算出することにより推定する第２の推定手段と、
割り付けるべき割付対象が有する生存区間と生存区間が重なる未割り付けの割付対象と、その重なる側の割付対象の生存区間と連続する生存区間を有する割付対象との間に介在する生存区間長を当該第２の後順割付対象検出手段によって検出された各割付対象毎に計数する第２の生存区間長計数手段と、
第２の後順割付対象検出手段によって未割り付けの割付対象と各資源要素との組み合わせに対して第２の推定手段によって推定された推定値にその割付対象に対して計数された生存区間長の短さと、各割付対象の優先度とを重みとして重み付けを行う第２の重み付け手段と、
第２の重み付け手段によって重み付けられた各割付対象の推定値を資源要素毎に集計する第２の集計手段と、
第２の集計手段によって集計された各資源要素についての集計値が最も大きい資源要素を割り付けるべき割付対象より後に割り付けられる全ての未割り付けの割付対象に最も相応しい資源要素と判定する第２の最適資源要素判定手段と
を備えることを特徴とする資源割付装置。
【請求項１５】
請求項１４記載の資源割付装置において第１及び第２の重み付け手段は、
第１及び第２の生存区間長計数手段によって計数された割付対象間の生存区間長が０であった場合、１を生存区間長の短さとして重み付けを行い、計数された生存区間長が０でない場合、その生存区間長の逆数を算出し、算出した生存区間長の逆数を生存区間長の短さとして重み付けを行う
ことを特徴とする資源割付装置。
【請求項１６】
請求項１４又は１５記載の資源割付装置において資源割付装置は、
機械語命令の命令フォーマットを用いてプログラム中の割付対象の定義命令及び使用命令を表現した情報である命令パタンを複数個記憶し、また機械語命令の各オペランドに各資源の資源要素を用いた場合のプログラム中の割付対象の定義命令及び使用命令の実行サイクルおよび／又はコードサイズを示すコストをそれぞれの命令パタンに対応づけて記憶するコスト記憶手段を備え、
前記第１の推定手段は、
第１の後順割付対象検出手段によって検出された未割り付けの割付対象の全ての定義命令及び使用命令に対応する命令パタンを読み出し、読み出した命令パタンを出力する第１の命令パタン出力部と、
コスト記憶手段から出力された命令パタンに対応するコストを取り出し、取り出したコストを各資源要素毎に集計し、集計した集計値を推定値とする第１のコスト集計部とを備え、
第２の推定手段は、
第２の後順割付対象検出手段によって検出された未割り付けの割付対象の全ての定義命令及び使用命令に対応する命令パタンを読み出し、読み出した命令パタンを出力する第２の命令パタン出力部と、
コスト記憶手段から出力された命令パタンに対応するコストを取り出し、取り出したコストを各資源要素毎に集計し、集計した集計値を推定値とする第２のコスト集計部と
を備えることを特徴とする資源割付装置。
【請求項１７】
請求項１１又は１６記載の資源割付装置において命令パタンは、演算結果の格納先がどのオペランドであるか、何れのオペランドにも一致しないかを示す情報を有し、
格納先がオペランドである命令パタンに対応するコストはそうでない命令パタンに対応するコストよりも小さい
ことを特徴とする資源割付装置。
【請求項１８】
請求項１１又は１６記載の資源割付装置において命令パタンは、対応する使用命令が、生存区間の終了点であるか、そうでないかを示す情報を有し、
終了点である命令パタンに対応するコストはそうでない命令パタンに対応するコストよりも小さい
ことを特徴とする資源割付装置。
【請求項１９】
請求項９記載の資源割付装置において資源割付装置は更に、
割り付けるべき資源要素が予め定められている割付対象を前記プログラムから検出する予約割付対象検出手段と、
予約割付対象検出手段が検出した割付対象に割り付けるべき資源要素を記憶する予約資源要素記憶手段と、
割付手段は予約割付対象検出手段によって検出された割付対象に割り付けられるべき資源要素を割り付け、割り付けた後に最大の優先度の割付対象に資源要素の何れかを割り付ける
ことを特徴とする資源割付装置。
【請求項２０】
請求項１９記載の資源割付装置において前記予約割付対象検出手段は、前記プログラムから関数呼び出しの引数を保持する割付対象を検出し、前記予約資源要素記憶手段は当該割付対象に割り付けるべき引数レジスタを記憶する
ことを特徴とする資源割付装置。
【請求項２１】
請求項１９記載の資源割付装置において前記予約割付対象検出手段は、前記プログラムから関数呼び出しの戻り値を保持する割付対象を検出し、前記予約資源要素記憶手段は当該割付対象に割り付けるべき戻り値レジスタを記憶する
ことを特徴とする資源割付装置。
【請求項２２】
請求項１９記載の資源割付装置において前記予約割付対象検出手段は、前記プログラムから値が書き換えられてもよい割付対象を検出し、前記予約資源要素記憶手段は当該割付対象に割り付けるべき破壊レジスタを記憶する
ことを特徴とする資源割付装置。
【請求項２３】
請求項２〜９記載の何れかの資源割付装置は更に、
プログラム中の各割付対象を当該割付対象の開始点で生存区間が終了する全ての割付対象と、当該割付対象の終了点で生存区間が始まる全ての割付対象とからなる集合である生存区間継承関係集合に対応づけて記憶する生存区間継承関係集合記憶手段を備え、
割付済み−被割付間連続判定手段は、
割り付けるべき割付対象についての生存区間継承関係集合を参照し、当該生存区間継承関係集合に割付済みの割付対象が存在するか否かを判定する第１の判定部と、
存在しなければ、生存区間継承関係集合内の他の割付対象を取り出し、取り出した割付対象についての生存区間継承関係集合を参照し、当該生存区間継承関係集合に割付済みの割付対象が存在するかを判定する第２の判定部と、
存在することが判定されるまで第２の判定部の起動を繰り返させる制御部とを備え、
得失値算出手段は、
検出結果とされた割付対象の生存区間長を集計する集計部と、
割り付けるべき割付対象の生存区間長と集計部によって集計された生存区間長との和の逆数を算出し、算出結果を生存区間の短さとする逆数算出部と
を備えることを特徴とする資源割付装置。
【請求項２４】
請求項３〜９記載の何れかの資源割付装置は更に、
プログラム中の各割付対象を、当該割付対象の開始点で生存区間が終了する全ての割付対象と、当該割付対象の終了点で生存区間が始まる全ての割付対象とからなる集合である生存区間継承関係集合に対応づけて記憶する生存区間継承関係集合記憶手段を備え、
未割り付け−被割付間連続判定手段は、
割り付けるべき割付対象についての生存区間継承関係集合を参照し、当該生存区間継承関係集合に第１の割付済み側重なり割付対象検出手段によって検出された未割り付けの割付対象が存在するか否かを判定する第１の判定部と、
存在しなければ、生存区間継承関係集合内の他の割付対象を取り出し、取り出した割付対象についての生存区間継承関係集合を参照し、当該生存区間継承関係集合に第１の割付済み側重なり割付対象検出手段によって検出された未割り付けの割付対象が存在するかを判定する第２の判定部と、
存在することが判定されるまで第２の判定部の起動を繰り返させる制御部とを備え、
得失値算出手段は、
検出結果とされた割付対象の生存区間長を集計する集計部と、
割り付けるべき割付対象の生存区間長と集計部によって集計された生存区間長との和の逆数を算出し、算出結果を生存区間の短さとする逆数算出部と
を備えることを特徴とする資源割付装置。
【請求項２５】
請求項６〜９記載の何れかの資源割付装置は更に、
プログラム中の各割付対象を当該割付対象の開始点で生存区間が終了する全ての割付対象と、当該割付対象の終了点で生存区間が始まる全ての割付対象とからなる集合である生存区間継承関係集合に対応づけて記憶する生存区間継承関係集合記憶手段を備え、
未割り付け−割付済み間連続判定手段は、
被割付側重なり割付対象検出手段によって検出された未割り付けの割付対象についての生存区間継承関係集合を参照し、当該生存区間継承関係集合に割付済みの割付対象が存在するか否かを判定する第１の判定部と、
存在しなければ、生存区間継承関係集合内の他の割付対象を取り出し、取り出した割付対象についての生存区間継承関係集合を参照し、当該生存区間継承関係集合に割付済みの割付対象が存在するかを判定する第２の判定部と、
存在することが判定されるまで、第２の判定部の起動を繰り返させる制御部とを備え、
得失値算出手段は、
検出結果とされた割付対象の生存区間長を集計する集計部と、
割り付けるべき割付対象の生存区間長と集計部によって集計された生存区間長との和の逆数を算出し、算出結果を生存区間の短さとする逆数算出部と
を備えることを特徴とする資源割付装置。
【請求項２６】
請求項７〜９記載の何れかの資源割付装置は更に、
プログラム中の各割付対象を、当該割付対象の開始点で生存区間が終了する全ての割付対象と、当該割付対象の終了点で生存区間が始まる全ての割付対象とからなる集合である生存区間継承関係集合に対応づけて記憶する生存区間継承関係集合記憶手段を備え、
未割り付け−未割り付け間連続判定手段は、
被割付側重なり割付対象検出手段によって検出された未割り付けの割付対象についての生存区間継承関係集合を参照し、当該生存区間継承関係集合に第２の割付済み側重なり割付対象検出手段によって検出された未割り付けの割付対象が存在するか否かを判定する第１の判定部と、
存在しなければ、生存区間継承関係集合内の他の割付対象を取り出し、取り出した割付対象についての生存区間継承関係集合を参照し、当該生存区間継承関係集合に第２の割付済み側重なり割付対象検出手段によって検出された未割り付けの割付対象が存在するかを判定する第２の判定部と、
存在することが判定されるまで第２の判定部の起動を繰り返させる制御部とを備え、
得失値算出手段は、
検出結果とされた割付対象の生存区間長を集計する集計部と、
割り付けるべき割付対象の生存区間長と集計部によって集計された生存区間長との和の逆数を算出し、算出結果を生存区間の短さとする逆数算出部と
を備えることを特徴とする資源割付装置。
【請求項２７】
請求項２３〜２６記載の何れかの資源割付装置において割付対象の生存区間は、当該生存区間によって占められるプログラム中の開始点から終了点までの命令位置情報で表され、
集計部は命令位置情報の数を集計し、集計値を生存区間長とする
ことを特徴とする資源割付装置。
【請求項２８】
請求項２７記載の資源割付装置において、割付対象の生存区間の開始点及び終了点は、プログラム中の命令位置情報で表され、
資源割付装置は更に、
プログラム中の割付対象と、各割付対象の生存区間の開始点に相当する命令位置情報と、各割付対象の生存区間の終了点に相当する命令位置情報とを対応づけて記憶する開始終了点記憶手段と、
開始終了点記憶手段を参照してプログラム中の各割付対象の生存区間の開始点に相当する命令位置情報が終了点に相当するものを全て探し出し、探し出した割付対象と、プログラム中の割付対象とを同一の生存区間継承関係集合にする第１の集合化手段と、
開始終了点記憶手段を参照してプログラム中の各割付対象の生存区間の終了点に相当する命令位置情報が、開始点に相当するものを全て探し出し、探し出した割付対象と、プログラム中の割付対象とを同一の生存区間継承関係集合にする第２の集合化手段と、
プログラム中の割付対象と、第１及び第２の集合化手段によって集合化された生存区間継承集合とを対応づけて生存区間継承関係集合記憶部に書き込む書き込み手段と
を備えることを特徴とする資源割付装置。
【請求項２９】
高級言語で書かれたプログラムを機械語プログラムに翻訳するコンパイラに用いられ、プログラミング言語で記述されたプログラムの中の変数と生存区間の組である割付対象にレジスタ、メモリ等のハードウェアである資源が有する資源要素を割り付ける資源割付装置であって、
プログラム中の割付対象をその優先度に対応づけて保持する割付対象保持手段と、
前記割付対象保持手段から優先度最大の割付対象を取り出し、優先度が最大の割付対象に資源要素の何れかを割り付ける第１の資源要素割付手段と、
直前に割り付けられた割付対象の優先度に対して、次順位の優先度を持つ割付対象を、前記割付対象保持手段から取り出す割付対象取出手段と、
前記割付対象取出手段が取り出した割付対象について、生存区間が重なっている割付対象を検出する一次重なり割付対象検出手段と、
前記一次重なり割付対象検出手段が検出した割付対象に、既に割り付けられている資源要素を検出する資源要素検出手段と、
検出された資源要素とは異なる資源要素が既に割り付けられている割付対象を全て検出する割付対象−資源要素検出手段と、
割付対象−資源要素検出手段によって検出された割付済みの割付対象のうち、割付対象取出手段によって取り出された割付対象と生存区間が連続している割付対象を全て判定する利得側連続割付済み割付対象判定手段と、
既に割付対象に割り付けられた資源要素がこれから割り付けようとする割付対象にどれだけ適切であるかを示す値である得失値を連続すると判定された割付済みの割付対象から割付対象取出手段によって取り出された割付対象までの生存区間長の短さに基づき、生存区間が連続すると判定された割付対象に割り付けられている全ての資源要素について算出する第１の得失値算出手段と、
算出された得失値を割付対象−資源要素検出手段によって判定された各資源要素毎に累計する累計手段と、
累計手段によって累計された累計値が最大の資源要素を割付対象取り出し手段が取り出した割付対象に割り付ける第２の資源要素割付手段と、
全ての割付対象が割り付けられるまで前記割付対象取出手段の起動を繰り返えす制御手段と
を備えることを特徴とする資源割付装置。
【請求項３０】
請求項２９において資源割付装置は更に、
割付対象−資源要素検出手段によって検出された割付済みの割付対象のうち、割付対象取出手段によって取り出された割付対象と生存区間が連続せず且つ生存区間が重なっていない割付対象を判定する第１の非重なり非連続割付済み割付対象判定手段と、
第１の非重なり非連続割付済み割付対象判定手段によって判定された割付済みの割付対象の生存区間と生存区間が重なる未割り付けの割付対象であって割付対象取出手段によって取り出された割付対象と生存区間が連続している割付対象を検出する利得側連続未割り付け割付対象検出手段と、
利得側連続未割り付け割付対象検出手段によって検出された未割り付けの割付対象から割付対象取出手段によって取り出された割付対象までの生存区間長の短さに基づき、第１の非重なり非連続割付済み割付対象判定手段によって判定された割付済みの割付対象に割り付けられた資源要素の得失値を算出する第２の得失値算出手段と、
前記累計手段によって累計された当該資源要素についての得失値から第２の得失値算出手段によって算出された得失値を減ずる第１の減算手段とを備え、
前記第２の資源要素割付手段は、第１の減算手段によって得失値が減ぜられた得失値が最大の資源要素を割付対象取出手段が取り出した割付対象に割り付ける
ことを特徴とする資源割付装置。
【請求項３１】
請求項３０において資源割付装置は更に、
割付対象−資源要素検出手段によって検出された割付済みの割付対象のうち、一次重なり割付対象検出手段によって検出された割付対象と、生存区間が連続しているものを判定する重なり側連続割付済み割付対象判定手段と、
重なり側連続割付済み割付対象判定手段によって判定された割付済みの割付対象から一次重なり割付対象検出手段によって検出された割付対象までの生存区間長の短さに基づき、重なり側連続割付済み割付対象判定手段によって判定された割付済みの割付対象に割り付けられた資源要素の得失値を算出する第３の得失値算出手段と、
前記累計手段によって累計された当該資源要素についての累計値から第３の得失値算出手段によって算出された得失値を減ずる第２の減算手段と、
第２の資源要素割付手段は第２の減算手段によって得失値が減ぜられた後の累計値が最大の資源要素を割付対象取出手段が取り出した割付対象に割り付ける
ことを特徴とする資源割付装置。
【請求項３２】
請求項３１において資源割付装置は更に、
割付対象−資源要素検出手段によって検出された割付済みの割付対象のうち、一次重なり割付対象検出手段によって検出された割付対象と生存区間が連続せず且つ生存区間が重なっていない割付対象を判定する第２の非重なり非連続割付済み割付対象判定手段と、
第２の非重なり非連続割付済み割付対象判定手段によって判定された割付済みの割付対象の生存区間と生存区間が重なる未割り付けの割付対象であって一次重なり割付対象検出手段によって検出された割付対象と生存区間が連続しているものを判定する重なり側連続未割り付け割付対象判定手段と、
重なり側連続未割り付け割付対象判定手段によって判定された割付対象から一次重なり割付対象検出手段によって検出された割付対象までの生存区間長の短さに基づいて第２の非重なり非連続割付済み割付対象判定手段によって判定された割付済みの割付対象に割り付けられている資源要素の得失値を算出する第４の得失値算出手段と、
前記累計手段によって累計された当該資源要素についての累計値に第４の得失値算出手段によって算出された得失値を加算する加算手段と、
前記第２の資源要素割付手段は加算手段によって得失値が加算された累計値が最大の資源要素を割付対象取出手段が取り出した割付対象に割り付ける
ことを特徴とする資源割付装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、高級言語で書かれたソースプログラムを機械語プログラムに翻訳するコンパイラにおいてプログラム中の変数をレジスタ、メモリ等の資源へ割り付ける資源割付装置に関する。
【０００２】
【従来の技術】
近年、組み込み用途向けのマイクロプロセッサを用いて多種多様なニーズに応えるようにした情報機器が盛んに開発されている。このような情報機器の開発においてはソフトウェアの面でも、処理の高速化やハードウェアコストの縮減（メモリサイズの縮小）の徹底が求められる。そのため上記の情報機器の開発では冗長な転送命令を徹底して除去し、アドレッシングモード等、マイクロプロセッサが有する機能を最大限まで引き出すべく、アセンブリ言語でソフトウェアの開発が行われてきた。ところが、アセンブリ言語の文法はプロセッサの命令体系そのものであるから至って開発効率が低く、ソースファイルの移植性に問題がある。そのため組み込み用途向けのマイクロプロセッサのソフトウェアを高級プログラミング言語で作成することで開発効率を高めることが近年注目を集めている。
【０００３】
高級プログラミング言語を用いれば、プログラマはプログラム中の数値の保持、演算、転送等の処理を変数を被演算子とした演算で表現できる。この変数はプログラマによって任意に定義され、また必要な個数だけ用いられるため、プログラマは自由にプログラムを記述できる。また記述されたプログラム（ソースプログラムと称す。）はコンパイルされることよりコンピュータが理解可能な機械語プログラムとなる。当該機械語プログラム中の演算は機械語命令によって表現され、また当該機械語命令はレジスタあるいはメモリを被演算子とするので、上記変数にはレジスタあるいはメモリを割り付ける必要がある。この割り付け処理は資源割付処理と称される。この資源割付処理はマイクロプロセッサの能力を最大限まで引き出すようなソフトウェアの開発においては特に重要視される。
【０００４】
従来の資源割付装置に付いて述べる前に以下の説明で使用する用語について説明しておく。
・変数の定義、参照、使用
変数の値を設定することを「定義する」と呼び、設定した値を使用することを「参照する」と呼ぶ。またプログラム上で変数を定義したり、参照したりすることを変数を「使用する」と呼ぶことにする。
・中間命令
処理をし易すくするためにコンパイラがソースプログラムのコードを中間的なコードに変換したものを中間コードと呼び、中間コードの１ステップを中間命令と呼ぶことにする。中間命令には４つ組や３つ組などが存在し、これらが変換されて最終的なオブジェクトコードが生成される。またソースプログラムを中間命令の列に変換したものを中間プログラムと呼ぶことにする。
・生存区間
生存区間とは広義にはそれぞれの変数に保持されている値が有効となる区間であり、狭義には変数に値を定義する中間命令からその定義された値を最後に参照する中間命令までのプログラム上の区間のことであり、生存区間はこの区間に含まれる中間命令の集合で表される。ここで変数に値を定義する中間命令は生存区間の開始点に相当し、生存区間中で定義された値を参照している中間命令のうち、最後に参照する中間命令は生存区間の終了点に相当する。また生存区間の重複、非重複を中間命令の集合積で判定するため、生存区間の終始が一致する中間命令では生存区間は重ならないとする。
【０００５】
中間プログラムの例（これは図３０（ａ）に示すソースプログラムを変換したものである。）と、その生存区間との対応の一例を図２８に示す。図２８において生存区間は縦線ｓ１、ｓ２、ｓ３で表されている。生存区間の開始点、及び終了点は点ｐ１、ｐ２、ｐ３、ｐ４・・・で表現している。図３０（ａ）において変数ｃ及びｄの開始点は２箇所存在しているが、これは変数ｃ、ｄが、判断文ｉｆ（ｂ＞＝１０）｛処理ｐ１｝else｛処理ｐ２｝の処理ｐ１、ｐ２において定義されているからである。
・割付対象
資源の割付対象としては単に変数をとる場合もあるが、一つの変数に対して複数の生存区間が存在する場合はそれぞれの生存区間ごとに別々の資源要素に割り付けることができるので、本明細書では割付対象は変数と生存区間の組とし、割付対象は変数と生存区間とを保持するものとする。ここで図２８の変数ｂのように生存区間が複数ある場合は、互いに区別するために割付対象ｂ１、ｂ２として独立した割付対象として表現する。
【０００６】
また割付対象が保持する変数を「定義する」こと、「参照する」こと、「使用する」ことをそれぞれ、その変数を保持する割付対象を「定義する」「参照する」「使用する」とも呼ぶことにする。更に割付対象が定義される中間命令、及び参照される中間命令をそれぞれ、その割付対象の定義中間命令、参照中間命令と呼び、定義及び参照中間命令を併せて使用中間命令と呼ぶ。
・割付優先度
割り付けを行う際、割付対象の割り付けの順番を決めるためのパラメータである。
【０００７】
割付優先度の計算には様々な方法が存在する。例えば、プログラム中の割付対象の使用率を割付優先度としたときの計算式の例を以下の｛数式１｝に示す。
0003638171.tif 000002
尚、割付対象が使用される中間命令が、プログラム中のループ処理の中に存在するときは割付優先度にそのループレベルを算入してもよい。
【０００８】
例えば、
割付優先度＝使用率＝使用中間命令が存在するループレベルの総和／生存区間の長さ
・資源要素
コンピュータのハードウェアの要素のうち、割付対象に割り付け可能な最小単位である。値を一時的に保持するバッファや個々のレジスタ、メモリ内の番地単位のメモリ要素がその例である。０番目のレジスタ、１番目のレジスタ、１００番地のメモリ、１０１番地のメモリはそれぞれ別の資源要素である。
・資源
同じ機能を果たす資源要素の集合を示す。
【０００９】
例えば、資源にはレジスタとメモリとが存在する。更にレジスタはアドレスレジスタ（ＡＲ）、データレジスタ（ＤＲ）、大域的レジスタ、局所的レジスタというように同一機能を果たすもので分類できる。またメモリは高速メモリ、低速メモリというように同一機能を果たすもので分類できる。このように資源要素が同一機能を果たすもの同士で分類できれば、その分類毎が別々の資源になる。
・干渉グラフ
割付対象と、割付対象同士の生存区間の重なりとを図示するためのグラフである。
【００１０】
干渉グラフとは割付対象をグラフの頂点とし、生存区間が重なる割付対象（頂点）同士を互いに結んで辺として描かれる。
・頂点の次数
干渉グラフにおいて頂点に結合している辺の数である。
次に図２９にコンパイラの構成図を示す。コンパイラは構文解析装置１１と、最適化装置１２と、資源割付装置６３と、コード生成装置１４とで構成されている。このコンパイラの各構成について図２９の構成図、図２８、図３０（ａ）、図３０（ｂ）、図３０（ｃ）の説明図を用いて説明する。
【００１１】
構文解析装置１１は記憶装置（図外）にファイルとして記憶されているソースプログラムの字句解析、構文解析および意味解析を行い、ソースプログラムを中間プログラムに変換する。例えば、図３０（ａ）のソースプログラムは図２８の中間プログラムに変換される。
最適化装置１２は最終的に生成される機械語プログラムのプログラムサイズ及び処理実行時間を向上させる目的で中間プログラムの最適化を行う。この最適化の詳細については本発明の主眼ではないため説明を省略し、資源割付処理と特に関連がある点のみ説明する。最適化作業には基本ブロック化、制御フロー解析、データフロー解析という作業が含まれている。基本ブロック化とは処理対象のプログラムを基本ブロックに分割することである。
【００１２】
この分割処理を簡単に説明する。先ず最適化装置１２は中間プログラムの最初の中間命令、無条件あるいは条件飛び越しの行き先の中間命令、無条件あるいは条件飛び越しの直後の中間命令を検出し、検出したこれらをリーダーとみなす。更に最適化装置１２はリーダーから始まり、次のリーダーの一つ手前まであるいはプログラムの最後までの一連の中間命令を抽出する。この抽出処理によって得られた命令列は基本ブロックと称され、以降の処理単位となる。
【００１３】
制御フロー解析とは各基本ブロック間の制御の流れを解析することである。
データフロー解析とは各基本ブロック中、それぞれの変数がどこで定義され、どこで参照されているかについて解析することである。これらの解析結果を参照して変数の生存区間の情報が得られる。
資源割付装置６３は資源割り付けのためのアルゴリズムの一つであるグラフ縮退によるグラフ彩色法を用いて中間プログラム中の割付対象にレジスタ、メモリを割り付ける。グラフ縮退によるグラフ彩色法とは、干渉グラフの各頂点の色分けをする場合に辺で結ばれていれば異なる色を塗るという規則に従って、近似的に最も少ない色数で干渉グラフの各頂点の色分けを行うアルゴリズムである。図３０（ａ）のプログラム中の割付対象は資源割付処理によって図３０（ｂ）のように資源要素が割り付けられる。本図において図３０（ａ）に示した割付対象ａには資源要素Ｒ０を割り付けたことを示し、割付対象ｂ２には資源要素Ｒ２を割り付けたことを示す。
【００１４】
コード生成装置１４は図３０（ｃ）に示すように中間プログラム内の各中間命令の機械語命令化を行い、中間プログラムをターゲットマシンが解読可能な機械語プログラムに変換する。このようにコード生成装置１４によって変換された機械語プログラムを目的プログラムと呼ぶ。本目的プログラム中の機械語命令と、図３０（ａ）、図２８のソースプログラム及び中間プログラムとの対応は▲１▼▲２▼▲３▼▲４▼記号で表される。上記機械語命令化において各機械語命令のオペランドには図３０（ｂ）に示した資源割付結果のものを用いる。また図中の転送命令ｔ１１、ｔ１２、ｔ１３、ｔ１４、ｔ１５・・・は図２８の中間プログラム中の各中間命令の処理が、機械語命令によって実現されるようにするためコード生成装置１４によって生成されたものである。また資源割付の結果によってはこの転送命令の幾つかが不用になることも有り得る。図３０（ｃ）において▲７▼は割付対象ｂ２と、ｃとが同一レジスタに割り付けられたため、転送命令生成が不用になった例である。
【００１５】
次に資源割付装置６３について説明を行う。上記グラフ彩色法を用いた資源割付処理の詳細は以下に示す文献に記されている。
従来の資源割付け方式、特にレジスタの割付け方式としては
[1]A.V.Aho,  R.Sethi,  J.D.Ullman:  "Compilers  Principles,  Techniques,  and  Tools",  Addison-Wesley,  1986
[2]Chaitin..  :"Register  allocation  and  spilling  via  graph  coloring",United  States  Patent,  pat.num.  4.571.678,  Feb.18,  1986
[3]Frederick  Chow,  John  Hennessy:"Register  Allcation  by  Priority-based  Coloring",Computer  Systems  Laboratory,Stanford  University
[4]David  Bernstein,..,Ron  Y.Pinter:"Spill  code  minimization  techniquesof  optimizing  compilers",SIGPLAN  1989,  IBM  Israel  Science  and  Technology  Technion  City  Haifa,  Israel
[5]佐々  政孝  :"プログラミング言語処理系",  岩波書店  レジスタ割付け  p420〜p423
[6]森、他  :"複合バンク機構を考慮した系統的なレジスタ割当て方式と
その一般化",  情報処理学会,  Vol.30,  No6,  Jun,  1989がある。
【００１６】
上記資源割付装置６３の構成を図３１に示す。図３１に示すように資源割付装置６３は最適化装置１２の処理結果に応じて割付対象を生成する割付対象生成部７１と、割付対象生成部７１によって生成された割付対象を保持する割付対象保持部７２と、当該保持部に保持されている各割付対象の優先度を上記｛数式１｝に示した計算式を用いて計算し、記憶する優先度計算部７３と、図２８に示したような各割付対象の生存区間についての情報及び当該生存区間がどう重なっているかの情報を記憶する生存区間情報記憶部７４と、保持部に保持されている全割付対象を干渉グラフ状に展開する展開部７５と、展開部が展開を行うためのバッファ７６と、一旦展開部によって展開された割付対象を全て積み込むためのスタック７７と、上記グラフ縮退によるグラフ彩色法で資源割付を行う制御部８０と、資源割付の結果を図３０（ｂ）の形式で記憶する記憶部７８とを備える。
【００１７】
図３２（ａ）、図３２（ｂ）、及び図３３（ａ）〜図３３（ｉ）はグラフ縮退によるグラフ彩色法を説明するための説明図である。これらの説明図を用いて上記資源割付装置６３の処理内容を説明する。ここでは割り付け可能なレジスタの個数を３個とし、レジスタに割り付けられなかったものはメモリに割り付けるものとする。
【００１８】
上記展開部７５は図２８に示した割付対象及び当該割付対象間の生存区間の重なりを図３２（ａ）に示すような干渉グラフで表現する。このような干渉グラフにおいて各割付対象がどれだけの割付対象と生存区間の重なりがあるかは、頂点から出ている辺の数（次数）で表現される。また図３２（ｂ）に示したように割付対象のうち、生存区間の終了点及び開始点が１中間命令で一致しているもの同士は（図２８の割付対象ｂ２、ｃ）、１つの割付対象と見なせ得るため、図３２（ｂ）に示すように制御部８０はそれぞれが対応している頂点を結合し、干渉グラフの簡易化を図る（図３２（ｂ）、割付対象ｂ２ｃ）。このような簡易化の後、干渉グラフの頂点には高低が発生している。頂点の次数が、レジスタの数が３個未満の頂点は次数の低い頂点と称され、次数がレジスタの数以上の頂点は次数の高い頂点と称される。この次数の高低はグラフ縮退の成立条件として利用される。グラフ縮退とは図３３（ａ）の矢線ｙ１１、ｙ１２に指示するように次数が低い頂点を｛数式１｝で求めた優先度の低い順に削除してゆき、削除された頂点に割付対象を後積み先出し方式のスタック領域に積み込むことであり、ｅ２及びｄを削除した結果、図３３（ａ）に示した干渉グラフは図３３（ｂ）に示すものへと変遷する。
【００１９】
この図３３（ｂ）の状態では全頂点の次数が高いため、上記条件が成立しない。そこでこれらの頂点のうち、矢線ｙ１３に示すように最低優先度の割付対象ｂ１にメモリを割り付け頂点ｂ１を削除する。この頂点ｂ１の削除により干渉グラフは図３３（ｃ）のものへと変遷し、再び、上記成立条件が成立する。図３３（ｃ）の状態で再び、グラフ縮退を繰り返し、図３３（ｄ）に示すように全割付対象をスタックに積み込む。このような積み込み処理を終えたのちに、これから資源割付処理を行う。先ず、図３３（ｅ）に示すようにスタックのトップから割付対象ａを取り出し、割付対象ａにレジスタＲ０を割り付け、同様にスタックのトップから割付対象ｅ１、ｂ２ｃを取り出し、図３３（ｆ）、図３３（ｇ）に示すように割付対象ｅ１、ｂ２ｃにレジスタＲ１、Ｒ２を割り付ける。次順の割付対象ｅ２、ｄはｂ２ｃとは生存区間が重なるが、割付対象ａ、ｅ１とは生存区間が重ならないため、図３３（ｈ）に示すように割付可能なレジスタのうち、最も番号の若いレジスタＲ０を割付対象ｅ２に割り付け、同じく、図３３（ｉ）に示すようにレジスタＲ１を割付対象ｄに割り付ける。このような割付処理によって生存区間が重なり合う割付対象同士に異なるレジスタを割り付けることができる。
【００２０】
上記の割付対象ａ、ｂ２、ｃ、ｄ、ｅ１、ｅ２、ｂ１は資源割付処理によって何れかの資源要素を割り付けていたが、Ｃ言語等の高級言語においては割付対象との組み合わせが予め設定されているレジスタがある。それは関数呼び出し作業の効率化を図るために用いられるものであり、引数レジスタ、戻り値レジスタ、破壊レジスタと称される。
【００２１】
引数レジスタとは関数呼び出し時に引数をレジスタで引き渡すためのレジスタである。中間プログラムにおいて引数として使用されている割付対象はこの引数レジスタが割り付けられる。
戻り値レジスタとは関数呼び出しの戻り値を返すためのレジスタである。中間プログラムにおいて戻り値を返すために使用されている割付対象は、この戻り値レジスタが割り付けられる。
【００２２】
破壊レジスタとは関数呼び出しの開始と終了時に格納値を退避・復元する必要のないレジスタである。この破壊レジスタは関数呼び出しのオーバーヘッド軽減を目的としている。上記関数呼び出しを行う場合、呼び出される関数内での処理によって各レジスタの内容は書き換えられる可能性があり関数呼び出しの前後においてレジスタ内容の退避・復元を行う必要がある。但し、全レジスタについてこの退避・復元作業を行うことは関数呼び出しのオーバヘッドを増大させることになるから、レジスタ内容の退避・復元作業が必要でない破壊レジスタを予め設定し、割付対象のうち、関数呼び出し命令を生存区間に含まないものに破壊レジスタを割り付け、退避・復元作業を最低限のものにする。
【００２３】
【発明が解決しようとする課題】
しかしながら上記従来技術における資源割付装置によれば、目的プログラムの実行時間、メモリサイズを増加させるような資源割付を行い得るという問題点があった。この問題点を図３４を参照しながら説明を行う。本図に示されている縦線は割付対象の生存区間を表し、そのうち、白抜きのものは未割り付けの割付対象、黒で塗り潰されているものは割付済みの割付対象を示す。一方、本図において割付対象x0,x1,x5を表す縦線は割付対象z0,z1,z2を表す縦線と並行部分を有するのでこれらは互いに生存区間が重なっていることが判る。
【００２４】
また図３４に示すように生存区間が連続し合う割付対象同士（割付対象x0、x1、x2、x3、x4、x5）は、上記の頂点結合によって１つの割付対象yへと結合される。結合された割付対象yは既に資源要素R0が割り付けられている割付対象z0、資源要素R1が割り付けられている割付対象z1、資源要素R2が割り付けられている割付対象z2と生存区間が重なってしまう。このように割付済みの割付対象と生存区間と重なれば、当該割付済みの割付対象に割り付けられている資源要素（資源要素R0、R1、R2）を割付対象yに割り付けることはできない。そのため割付対象yを構成する割付対象x0、x1、x2、x3、x4、x5は全てメモリを割り付けてしまうことになる。これらの割付対象を全てメモリに割り付ければ、これらの割付対象を被演算子として使用している中間命令は全てメモリを被演算子とする機械語命令へと変換される。被演算子がメモリの機械語命令は概して実行速度が遅く、またメモリサイズが大きくなり、目的プログラムの実行時間、メモリサイズに悪影響を及ぼしてしまう。
【００２５】
また資源が３種類以上の機能に別れている場合に資源の機能に応じた割付対象の割り付けを行わないと、目的プログラムの実行時間、メモリサイズに悪影響を及ぼしてしまうという問題点があった。
上記文献のうち、[6]に記載されているものはアドレスレジスタ、データレジスタといったクラスが異なる複数種のレジスタへのアクセスに必要なコストを参照する資源割り付けについて述べている。この文献では、「Ｃ言語でのポインタ型のようなアドレス型の変数を保持する割付対象は全てアドレスレジスタに割り付ける。」というようなルールづけを行っている。但しアドレス型の割付対象には加算や減算で複数回使用され、メモリの間接参照が僅かな割付対象も存在し得る。データレジスタに関して高速な加算、減算演算を有するターゲットマシンにおいてはこのような割付対象を一律にアドレスレジスタに割り付けてしまえば、目的プログラム中にはアドレスレジスタからデータレジスタへの転送命令が多数生成され、目的プログラムのメモリサイズや実行時間を増大させる結果となる。
【００２６】
このように単にあるクラスのレジスタへのアクセスに必要なコストを参照するだけではかえって多くの転送命令を生成する結果を招いてしまう。
更に関数呼び出しを効率良く行うために設定される引数レジスタ、戻り値レジスタ、破壊レジスタの格納値をそのまま利用できるような資源割付が行えないという問題点があった。
【００２７】
グラフ彩色法とは干渉グラフの頂点塗り分けを最適に行うための近似アルゴリズムである。引数レジスタ、戻り値レジスタ、破壊レジスタはアルゴリズム実行前に予め割付対象に割り付けられた資源要素であるため、干渉グラフにおいてこれらのレジスタは色付きの頂点とみなされる。戻り値レジスタ、引数レジスタの格納値をそのまま利用出来るような資源割付を実現するためには、色付きの頂点を干渉グラフ内に組み込み、有効であればその色に他の頂点を彩色するという処理が必要となるが、これはグラフ彩色法の域を逸脱してしまう。以上の理由から通常はグラフ彩色法で割り付けるレジスタとは別個に引数レジスタ、戻り値レジスタに用いるためのレジスタを用意する必要がある。そして引数レジスタ、戻り値レジスタの格納値を使用するため、割り付け用レジスタへの転送命令が必要となる。このように転送命令が必要となるとその命令の追加分だけ、目的プログラムのメモリサイズ及び実行時間が増大する。
【００２８】
以上の問題点による影響はレジスタの個数にかなり余裕がある場合無視できるレベルに留まる。しかし多くの組み込み用途向けのマイクロプロセッサのようにレジスタの個数が制限されている場合、あるいは果たす機能が異なるレジスタが少数でかつ多種類備えられている場合にはこれらの問題点は顕著に現れる。
本発明の目的は優先度順に割付対象に資源要素を割り付けることができ、転送命令の生成量を最低限に留めることにより目的プログラムのメモリサイズ及び実行時間を最低限にすることができる資源割付装置を提供することである。
【００２９】
【課題を解決するための手段】
本発明は、資源要素に既に割り付けられた割付対象の生存区間と割り付けるべき割付対象の生存区間の位置関係に基づいて、資源要素を割付対象に割り付けるようにしている。
【００３０】
【発明の実施の形態】
上記目的を達成するために請求項１記載の資源割付装置は、
高級言語で書かれたプログラムを機械語プログラムに翻訳するコンパイラに用いられ、プログラミング言語で記述されたプログラムの中の変数と生存区間の組である割付対象を複数個生成し、生成した割付対象にレジスタ、メモリ等のハードウェアである資源が有する資源要素を割り付ける資源割付装置であって、次に割り付けるべき割付対象にどの資源要素が適切かを示す得失値を、資源要素に既に割り付けられた割付対象の生存区間と割り付けるべき割付対象の生存区間とがプログラムにおいてどのような位置関係にあるかに基づいて、各資源要素について算出する得失値算出手段と、各資源要素について算出された得失値の大きさに基づいて、何れかの資源要素を、割り付けるべき割付対象に割り付ける割付手段と、全ての割付対象が割り付けられるまで、得失値算出手段及び割付手段の起動を繰り返す制御手段とを備えることを特徴としており、
次に割り付けるべき割付対象にどの資源要素が適切かを示す得失値が、資源要素に既に割り付けられた割付対象の生存区間と割り付けるべき割付対象の生存区間とがプログラムにおいてどのような位置関係にあるかに基づいて、得失値算出手段によって各資源要素について算出される。各資源要素について算出された得失値の大きさに基づいて、割付手段によって何れかの資源要素が、割り付けるべき割付対象に割り付けられる。全ての割付対象が割り付けられるまで、制御手段によって得失値算出手段及び割付手段の起動が繰り返される。以上の繰り返しによって、割り付けるべき割付対象には、既に割り付けられた資源要素のうち、得失値が大きいものが割り付けられる。この得失値には、プログラムにおける生存区間の位置関係が反映されているので、この位置関係に準拠した資源要素が、各割付対象に割り付けられる。
【００３１】
また、請求項２において、資源割付装置は、プログラム中の各割付対象の位置関係を判定する位置関係判定手段を有し、位置関係判定手段は、既に資源要素が割り付けられた割付対象の生存区間が、割り付けるべき割付対象の生存区間と重複しているかを判定する重複関係判定手段と、資源要素が既に割り付けられた割付対象の生存区間と、割り付けるべき割付対象の生存区間とが連続しているかを判定する割付済み−被割付間連続判定手段とを備え、得失値算出手段は、割付済み−被割付間連続判定手段によって割り付けるべき割付対象と生存区間が連続していることが判定されると、資源要素が既に割り付けられた割付対象から割り付けるべき割付対象までの生存区間長の短さに応じて、連続が判定された割付済みの割付対象に既に割り付けられている資源要素の得失値を増加させる第１の増加部を備え、割付手段は、重複関係判定手段によって生存区間が重複していることが判定された重複している生存区間を有する割付済みの割付対象に割り付けられている資源要素を割り付けるべき割付対象に割り付けず、生存区間が重複していないことが判定された割付済みの割付対象のうち、得失値が最大の資源要素を割り付けるべき割付対象に割り付けることを特徴としたものであり、
既に資源要素が割り付けられた割付対象の生存区間が、割り付けるべき割付対象の生存区間と重複しているかが重複関係判定手段によって判定される。また資源要素が既に割り付けられた割付対象の生存区間と、割り付けるべき割付対象の生存区間とが連続しているかが割付済み−被割付間連続判定手段によって判定される。割付済み−被割付間連続判定手段によって割り付けるべき割付対象と生存区間が連続していることが判定されると、資源要素が既に割り付けられた割付対象から割り付けるべき割付対象までの生存区間長の短さに応じて、連続が判定された割付済みの割付対象に既に割り付けられている資源要素の得失値が第１の増加部によって増加される。このように、生存区間が連続し合うような位置関係にあっては、生存区間長の短さに応じて得失値が増加されるため、生存区間が連続し合う割付済みの割付対象に割り付けられている資源要素はより割り付けられる確率が高くなる。
【００３２】
重複関係判定手段によって生存区間が重複していることが判定されると、重複している生存区間を有する割付済みの割付対象に割り付けられている資源要素が割り付けるべき割付対象に割り付けられないため、生存区間が重複し合う割付対象に、同一の資源要素が割り付けられることが避けられる。また、生存区間が連続し合う割付対象群のうち、生存区間の重なりによって、不具合が生じる割付対象には、異なる資源要素が割り付けられる。
【００３３】
また、請求項３において、位置関係判定手段は、資源要素が既に割り付けられた割付対象と重なる生存区間を有する未割り付けの割付対象を検出する第１の割付済み側重なり割付対象検出手段と、検出された未割り付けの割付対象の生存区間と、割り付けるべき割付対象の生存区間とが連続しているかを判定する未割り付け−被割付間連続判定手段とを備え、得失値算出手段は、連続すると判定されると、割付済み側重なり割付対象検出手段によって検出された未割り付けの割付対象から、割り付けるべき割付対象までの生存区間長の短さに応じて、当該割付済みの割付対象に割り付けられている資源要素の得失値を減少させる第１の減少部を備えることを特徴としており、
請求項３によれば、資源要素が既に割り付けられた割付対象と重なる生存区間を有する未割り付けの割付対象が、第１の割付済み側重なり割付対象検出手段によって検出される。検出された未割り付けの割付対象の生存区間と、割り付けるべき割付対象の生存区間とが連続しているかが未割り付け−被割付間連続判定手段によって判定される。連続することが判定されると、第１の割付済み側重なり割付対象検出手段によって検出された未割り付けの割付対象から、割り付けるべき割付対象までの生存区間長の短さに応じて、第１の減少部によって、当該割付済みの割付対象に割り付けられている資源要素の得失値が減少される。このように、得失値が減少されることによって、割り付けるべき割付対象からみて損失となるような位置の割付対象に割り付けられている資源要素は低く見積もられるようになる。このように低く見積もられた資源要素は、得失値が低いものとなるため、割り付けられる可能性が低くなるという作用を有する。
【００３４】
また、請求項４において、第１の割付済み側重なり割付対象検出手段によって、複数個の未割り付けの割付対象が判定された場合、未割り付け−被割付間連続判定手段は、検出された複数個の未割り付けの割付対象のうち、何れかのものの生存区間と、割り付けるべき割付対象の生存区間とが連続しているかを判定することを特徴としており、また、請求項４によれば、第１の割付済み側重なり割付対象検出手段によって、複数個の未割り付けの割付対象が判定された場合、検出された複数個の未割り付けの割付対象のうち、何れかのものの生存区間と、割り付けるべき割付対象の生存区間とが連続しているかが未割り付け−被割付間連続判定手段によって判定されると、いう作用を有する。
【００３５】
また、請求項５において、資源割付装置は、プログラムにおける割付対象の使用頻度及び／又は生存区間のネストレベルが反映された割付対象の優先度を、各割付対象に対応づけて記憶する優先度記憶手段を備え、得失値算出手段及び割付手段は、優先度記憶手段が記憶する優先度順に、割り付けるべき割付対象を決定することを特徴としており、請求項５によれば、割り付けるべき割付対象は、得失値算出手段及び割付手段によって優先度記憶手段が記憶する優先度順に決定される。この優先度には、プログラムにおける割付対象の使用頻度及び／又は生存区間のネストレベルが反映されているため、割付対象は、使用頻度又はネストレベルが高い順に資源要素が割り付けられてゆくという作用を有する。
【００３６】
また、請求項６において、位置関係判定手段は、各資源要素について得失値算出手段によって算出された得失値が複数個の資源要素同士で同一の大きさになった場合、割り付けるべき割付対象の生存区間と重なる生存区間を有する未割り付けの割付対象を検出する被割付側重なり割付対象検出手段と、検出された割付対象の生存区間と、資源要素が既に割り付けられた割付対象の生存区間とが連続しているかを判定する未割り付け−割付済み間連続判定手段とを備え、得失値算出手段は、被割付側重なり割付対象検出手段によって検出された割付対象の優先度を検出する優先度検出部と、割付済みの割付対象から検出された未割り付けの割付対象までの生存区間長の短さを算出する第１の短さ算出部と、検出された優先度に算出された短さを乗じ、その乗算結果に応じて、当該割付済みの資源要素の得失値を減少させる第２の減少部とを備えることを特徴としており、
請求項６によれば、割り付けるべき割付対象の生存区間と重なる生存区間を有する未割り付けの割付対象が、被割付側重なり割付対象検出手段によって検出される。検出された割付対象の生存区間と資源要素が既に割り付けられた割付対象の生存区間とが連続しているかが未割り付け−割付済み間連続判定手段によって判定される。被割付側重なり割付対象検出手段によって検出された割付対象の優先度が優先度検出部によって検出され、割付済みの割付対象から検出された未割り付けの割付対象までの生存区間長の短さが第１の短さ算出部によって算出される。検出された優先度に算出された短さを乗じ、その乗算結果に応じて、当該割付済みの資源要素の得失値が第２の減少部によって減少される。このように、得失値が減少されることによって、割り付けるべき割付対象からみて損失となるような位置の割付対象に割り付けられている資源要素は低く見積もられるようになる。このように低く見積もられた資源要素は、得失値が低いものとなるため、割り付けられる可能性が低くなるという作用を有する。
【００３７】
また、請求項７において、位置関係判定手段は、資源要素が既に割り付けられた割付対象の生存区間と重なる生存区間を有する未割り付けの割付対象を検出する第２の割付済み側重なり割付対象検出手段と、被割付側重なり割付対象検出手段によって検出された未割り付けの割付対象の生存区間と、第２の割付済み側重なり割付対象検出手段によって検出された未割り付けの割付対象の生存区間とが連続しているかを判定する未割り付け−未割り付け間連続判定手段とを備え、得失値算出手段は、被割付側重なり割付対象検出手段によって検出された未割り付けの割付対象から、第２の割付済み側重なり割付対象検出手段によって検出された未割り付けの割付対象までの生存区間長の短さを算出する第２の短さ算出部と、検出された優先度に算出された短さを乗じ、その乗算結果に応じて、割付済みの割付対象に割り付けられた資源要素の得失値を増加させる第２の増加部とを備えることを特徴としており、請求項７によれば、資源要素が既に割り付けられた割付対象の生存区間と重なる生存区間を有する未割り付けの割付対象が第２の割付済み側重なり割付対象検出手段によって検出される。被割付側重なり割付対象検出手段によって検出された未割り付けの割付対象の生存区間と、第２の割付済み側重なり割付対象検出手段によって検出された未割り付けの割付対象の生存区間とが連続しているかが未割り付け−未割り付け間連続判定手段によって判定される。被割付側重なり割付対象検出手段によって検出された未割り付けの割付対象から、第２の割付済み側重なり割付対象検出手段によって検出された未割り付けの割付対象までの生存区間長の短さが第２の短さ算出部によって算出される。検出された優先度に算出された短さを乗じ、その乗算結果に応じて、割付済みの割付対象に割り付けられた資源要素の得失値が第２の増加部によって増加される。得失値が増加されることによって、割り付けるべき割付対象からみて利得となるような位置の割付対象に割り付けられている資源要素は高く見積もられるようになる。このように高く見積もられた資源要素は、得失値が高いものとなるため、割り付けられる可能性が高くなるという作用を有する。
【００３８】
また、請求項８において、第２の割付済み側重なり割付対象検出手段によって、複数個の未割り付けの割付対象が判定された場合、未割り付け−未割り付け間連続判定手段は、検出された複数個の未割り付けの割付対象のうち、何れかのものの生存区間と、割り付けるべき割付対象の生存区間とが連続しているかを判定することを特徴としており、請求項８によれば、第２の割付済み側重なり割付対象検出手段によって、複数個の未割り付けの割付対象が判定された場合、検出された複数個の未割り付けの割付対象のうち、何れかのものの生存区間と、割り付けるべき割付対象の生存区間とが連続しているかが未割り付け−未割り付け間連続判定手段によって判定されるという作用を有する。
【００３９】
また、請求項９において、資源割付装置は、全ての資源要素と、各々の資源要素の得失値の初期値とを対応づけて記憶する得失値記憶部を備え、第１及び第２の増加部は、得失値記憶部に記憶されている各資源要素の得失値を増加させ、第１及び第２の減少部は、得失値記憶部に記憶されている各資源要素の得失値を減少させることを特徴としており、請求項９によれば、得失値記憶部に記憶されている各資源要素の得失値が、第１及び第２の増加部によって増加され、得失値記憶部に記憶されている各資源要素の得失値が第１及び第２の減少部によって減少させられる。得失値記憶部は、全ての資源要素と、各々の資源要素の得失値の累計の初期値とを対応づけて記憶しているので、全ての資源要素が損失になるような位置に割り付けられていれば、どの割付対象にも割り付けられてない資源要素の得失値が大きく見積もられるようになる。そのため、どの割付対象にも割り付けられてない資源要素を割り付けるべき割付対象に割り付けることができるという作用を有する。
【００４０】
また、請求項１０において、資源割付装置は更に、プログラムにおいて、各資源の資源要素を割り付けると、割り付けるべき割付対象が定義されている全ての定義命令、及び、使用されている全ての使用命令の実行サイクルおよび／又はコードサイズの集計値がどれだけになるかを、割り付けるべき割付対象と各資源要素との組み合わせについてその集計値の推定値を算出することで推定する推定手段と、各資源要素毎の推定結果である推定値を比較し、推定値が最小である資源要素が１つか複数かを判定する資源要素単複判定手段とを備え、前記割付手段は、１つと判定された場合、割り付けるべき割付対象に推定値が最小である資源要素を割り付け、複数個と判定された場合、得失値が最大の資源要素を、割り付けるべき割付対象に割り付けることを特徴としており、また、請求項１０によれば、プログラム中の各割付対象の定義命令及び使用命令の実行サイクルおよび／又はコードサイズの集計がどれだけになるかを示す推定値が、推定値算出手段によって各資源要素について算出される。各資源要素毎の推定値が比較され、推定値が最小である資源要素が、資源要素単複判定手段によって１つか複数かが判定される。１つと判定された場合、割り付けるべき割付対象に推定値が最小である資源要素が割付手段によって割り付けられ、複数個と判定された場合、得失値の累計が最大の資源要素が割り付けるべき割付対象に割り付けられる。このように割付対象に割り付けるのに際して、推定値を用いるか得失値を用いるかが切り換えられ、推定値が最大の資源要素が１つである場合、推定値が優先されるため、割付対象の定義命令及び使用命令の実行サイクルおよび／又はコードサイズの増加量を優先させた資源割り付けが行えるという作用を有する。
【００４１】
また、請求項１１において、推定手段は、機械語命令の命令フォーマットを用いて、プログラム中の割付対象の定義命令及び使用命令を表現した情報である命令パタンを、プログラム中における当該割付対象の全ての定義命令及び使用命令について出力する命令パタン出力部と、機械語命令の各オペランドに各資源の資源要素を用いた場合の、当該定義命令及び使用命令の実行サイクルおよび／又はコードサイズを示すコストを、命令パタン出力部によって出力され得る命令パタンのそれぞれに対応づけて記憶するコスト記憶部と、コスト記憶部から、出力された命令パタンに対応するコストを取り出し、取り出したコストを各資源要素毎に集計し、集計した集計値を推定値とするコスト集計部とを備えることを特徴としており、請求項１１によれば機械語命令の命令フォーマットを用いて、プログラム中の割付対象の定義命令及び使用命令を表現した情報である命令パタンが、命令パタン出力部によってプログラム中における当該割付対象の全ての定義命令及び使用命令について生成される。コスト記憶部から、出力された命令パタンに対応するコストがコスト集計部によって取り出され、取り出されたコストが各資源要素毎に集計され、集計された集計値が推定値とされる。コスト記憶部は、各機械語命令の各オペランドに各資源の資源要素を用いた場合の当該定義命令及び使用命令の実行サイクルおよび／又はコードサイズを示すコストを命令パタン出力部によって出力され得る命令パタンのそれぞれに対応づけて記憶しているため、割付対象の定義命令及び使用命令を機械語命令化するのに、どの資源の資源要素が適切であるかが綿密に判定されるという作用を有する。
【００４２】
また、請求項１２において、資源割付装置は更に、各資源要素について得失値算出手段によって算出された得失値が複数個の異なる資源の資源要素同士で同一の大きさになった場合、割り付けるべき割付対象より優先度が低く、割り付けるべき割付対象の後に割り付けられる全ての未割り付けの割付対象に最も相応しい資源要素を予測する予測手段を備え、前記割付手段は、予測手段によって予測された資源要素を、割り付けるべき割付対象に割り付けることを特徴としており、請求項１２によれば、各資源要素について得失値算出手段によって算出された得失値が複数個の異なる資源の資源要素同士で同一の大きさになった場合、割り付けるべき割付対象より優先度が低く、割り付けるべき割付対象の後に割り付けられる全ての未割り付けの割付対象に最も相応しい資源要素が予測手段によって予測される。このように予測された資源要素が、割付手段によって割り付けるべき割付対象に割り付けられるという作用を有する。
【００４３】
また、請求項１３において、予測手段は、割り付けるべき割付対象が有する生存区間と連続する生存区間を有し、かつ、当該割付対象より優先度が低い未割り付けの割付対象を全て検出する第１の後順割付対象検出手段と、検出された各割付対象に各資源要素を割り付けたとすると当該割付対象が定義されている全ての定義命令及び使用されている全ての使用命令の実行サイクルおよび／又はコードサイズの集計値がどれだけになるかを、第１の後順割付対象検出手段に検出された全ての割付対象と各資源要素との組み合わせについて当該集計値の推定値を算出することにより推定する第１の推定手段と、第１の後順割付対象検出手段によって検出された各割付対象と割り付けるべき割付対象との間に介在する生存区間長を、第１の後順割付対象検出手段によって検出された各割付対象毎に計数する第１の生存区間長計数手段と、検出された各割付対象と各資源要素との組み合わせに対して第１の推定手段によって算出された推定値に、その割付対象に対して計数された生存区間長の短さを重みとして、重み付けを行う第１の重み付け手段と、第１の重み付け手段によって重み付けられた推定値を各資源要素毎に集計する第１の集計手段と、第１の集計手段によって集計された集計結果が最も小さい資源要素を、割り付けるべき割付対象より優先度が低い未割り付けの割付対象に最も相応しい資源要素と判定する第１の最適資源要素判定手段とを備えることを特徴としており、
請求項１３によれば、割り付けるべき割付対象が有する生存区間と連続する生存区間を有し、かつ、当該割付対象より優先度が低い未割り付けの割付対象が第１の後順割付対象検出手段によって全て検出される。次に検出された各割付対象に各資源要素を割り付けたとすると当該割付対象が定義されている全ての定義命令及び使用されている全ての使用命令の実行サイクルおよび／又はコードサイズの集計値がどれだけになるかが、第１の推定手段によって推定される。第１の後順割付対象検出手段によって検出された各割付対象と割り付けるべき割付対象との間に介在する生存区間長が、第１の生存区間長計数手段によって計数される。検出された各割付対象と各資源要素との組み合わせに対して第１の推定手段によって算出された推定値に、その割付対象に対して計数された生存区間長の短さを重みとして、第１の重み付け手段によって重み付けが行われる。第１の重み付け手段によって重み付けられた推定値が第１の集計手段によって各資源要素毎に集計される。第１の集計手段によって集計された集計結果が最も小さい資源要素が割り付けるべき割付対象より優先度が低い未割り付けの割付対象に最も相応しい資源要素として第１の最適資源要素判定手段によって判定され、このように判定された資源要素が割付対象に割り付けられるという作用を有する。
【００４４】
また、請求項１４において、予測手段は、第１の最適資源要素判定手段によって複数個の資源要素が最も相応しいと判定された場合、割り付けるべき割付対象と生存区間が重なる未割り付けの割付対象、及び、その未割り付けの割付対象の生存区間と連続する生存区間を有する未割り付けの割付対象を検出する第２の後順割付対象検出手段と、第２の後順割付対象検出手段によって検出された未割り付けの割付対象に各資源要素を割り付けたとすると、検出された各割付対象が定義されている全ての定義命令及び使用されている全ての使用命令の実行サイクルおよび／又はコードサイズの集計値がどれだけになるかを、検出された割付対象と各資源要素との組み合わせについて当該集計値の推定値を算出することで推定する第２の推定手段と、割り付けるべき割付対象が有する生存区間と生存区間が重なる未割り付けの割付対象と、その重なる側の割付対象の生存区間と連続する生存区間を有する割付対象との間に介在し、連続する生存区間長を当該第２の後順割付対象検出手段によって検出された各割付対象毎に計数する第２の生存区間長計数手段と、第２の後順割付対象検出手段によって未割り付けの割付対象と各資源要素との組み合わせに対して第２の推定手段によって推定された推定値に、その割付対象に対して計数された生存区間長の短さと、各割付対象の優先度とを重みとして、重み付けを行う第２の重み付け手段と、第２の重み付け手段によって重み付けられた各割付対象の推定値を資源要素毎に集計する第２の集計手段と、第２の集計手段によって集計された各資源要素についての集計値が最も大きい資源要素を、割り付けるべき割付対象より後に割り付けられる全ての未割り付けの割付対象に最も相応しい資源要素と判定する第２の最適資源要素判定手段とを備えることを特徴としており、
請求項１４によれば、第１の最適資源要素判定手段によって複数個の資源要素が最も相応しいと判定された場合、割り付けるべき割付対象と生存区間が重なる未割り付けの割付対象、及び、その未割り付けの割付対象の生存区間と連続する生存区間を有する未割り付けの割付対象が第２の後順割付対象検出手段によって検出される。第２の後順割付対象検出手段によって検出された未割り付けの割付対象に各資源要素が割り付けられたとすると検出された各割付対象が定義されている全ての定義命令及び使用されている全ての使用命令の実行サイクルおよび／又はコードサイズの集計値がどれだけになるかが、検出された割付対象と各資源要素との組み合わせについて当該集計値の推定値が算出されることで第２の推定手段によって推定される。
【００４５】
割り付けるべき割付対象が有する生存区間と生存区間が重なる未割り付けの割付対象と、その重なる側の割付対象の生存区間と連続する生存区間が有する割付対象との間に介在し、連続する生存区間長が第２の生存区間長計数手段によって当該第２の後順割付対象検出手段によって検出された各割付対象毎に計数される。
【００４６】
第２の後順割付対象検出手段によって未割り付けの割付対象と各資源要素との組み合わせに対して第２の推定手段によって推定された推定値に、その割付対象に対して計数された生存区間長の短さと各割付対象の優先度とが重みとして、第２の重み付け手段によって重み付けされる。
第２の重み付け手段によって重み付けられた各割付対象の推定値が、第２の集計手段によって資源要素毎に集計される。第２の集計手段によって集計された各資源要素についての集計値が最も大きい資源要素が、第２の最適資源要素判定手段によって割り付けるべき割付対象より後に割り付けられる全ての未割り付けの割付対象に最も相応しい資源要素と判定されるという作用を有する。
【００４７】
また、請求項１５において、第１及び第２の重み付け手段は、第１及び第２の生存区間長計数手段によって計数された割付対象間の生存区間長が０であった場合、１を生存区間長の短さとして重み付けを行い、計数された生存区間長が０でない場合、その生存区間長の逆数を算出し、算出した生存区間長の逆数を生存区間長の短さとして重み付けを行うことを特徴としており、また、請求項１５によれば、第１及び第２の重み付け手段は、第１及び第２の生存区間長計数手段によって計数された割付対象間の生存区間長が０であった場合、１が生存区間長の短さとして重み付けが行われ、計数された生存区間長が０でない場合、その生存区間
長の逆数が算出され、算出された生存区間長の逆数を生存区間長の短さとして重み付けが行われるという作用を有する。
【００４８】
また、請求項１６において、資源割付装置は、
機械語命令の命令フォーマットを用いてプログラム中の割付対象の定義命令及び使用命令を表現した情報である命令パタンを複数個記憶し、また、機械語命令の各オペランドに各資源の資源要素を用いた場合のプログラム中の割付対象の定義命令及び使用命令の実行サイクルおよび／又はコードサイズを示すコストをそれぞれの命令パタンに対応づけて記憶するコスト記憶手段を備え、第１の推定手段は、第１の後順割付対象検出手段によって検出された未割り付けの割付対象の全ての定義命令及び使用命令に対応する命令パタンを読み出し、読み出した命令パタンを出力する第１の命令パタン出力部と、コスト記憶手段から、出力された命令パタンに対応するコストを取り出し、取り出したコストを各資源要素毎に集計し、集計した集計値を推定値とする第１のコスト集計部とを備え、
第２の推定手段は、第２の後順割付対象検出手段によって検出された未割り付けの割付対象の全ての定義命令及び使用命令に対応する命令パタンを読み出し、読み出した命令パタンを出力する第２の命令パタン出力部と、コスト記憶手段から、出力された命令パタンに対応するコストを取り出し、取り出したコストを各資源要素毎に集計し、集計した集計値を推定値とする第２のコスト集計部とを備えることを特徴としており、
また、請求項１７において、命令パタンは、演算結果の格納先がどのオペランドであるか、何れのオペランドにも一致しないかを示す情報を有し、格納先がオペランドである命令パタンに対応するコストは、そうでない命令パタンに対応するコストよりも小さいことを特徴としており、
また、請求項１８において、命令パタンは、対応する使用命令が、生存区間の終了点であるか、そうでないかを示す情報を有し、終了点である命令パタンに対応するコストは、そうでない命令パタンに対応するコストよりも小さいことを特徴としており、
また、請求項１６〜１８によれば、コスト記憶手段には、機械語命令の命令フォーマットを用いてプログラム中の割付対象の定義命令及び使用命令が表現した情報である命令パタンが複数個記憶され、また、機械語命令の各オペランドに各資源の資源要素を用いた場合のプログラム中の割付対象の定義命令及び使用命令の実行サイクルおよび／又はコードサイズを示すコストがそれぞれの命令パタンに対応づけて記憶されている。
【００４９】
第１の後順割付対象検出手段によって検出された未割り付けの割付対象の全ての定義命令及び使用命令に対応する命令パタンが読み出され、第１の命令パタン出力部によって読み出された命令パタンが出力される。
コスト記憶手段から、出力された命令パタンに対応するコストが取り出され、取り出したコストが各資源要素毎に集計され、集計した集計値が第１のコスト集計部によって推定値とされる。第２の後順割付対象検出手段によって検出された未割り付けの割付対象の全ての定義命令及び使用命令に対応する命令パタンが読み出され、第２の命令パタン出力部によって読み出された命令パタンが出力される。コスト記憶手段から、第２のコスト集計部によって出力された命令パタンに対応するコストが取り出され、取り出されたコストが各資源要素毎に集計され、集計された集計値が推定値とされるという作用を有する。
【００５０】
また、請求項１９において、資源割付装置は更に、割り付けるべき資源要素が予め定められている割付対象を、前記プログラムから検出する予約割付対象検出手段と、予約割付対象検出手段が検出した割付対象に割り付けるべき資源要素を記憶する予約資源要素記憶手段と、割付手段は、予約割付対象検出手段によって検出された割付対象に割り付けられるべき資源要素を割り付け、割り付けた後に最大の優先度の割付対象に、資源要素の何れかを割り付けることを特徴としており、
また、請求項２０において、前記予約割付対象検出手段は、前記プログラムから関数呼び出しの引数を保持する割付対象を検出し、前記予約資源要素記憶手段は、当該割付対象に割り付けるべき引数レジスタを記憶することを特徴としており、
また、請求項２１において、前記予約割付対象検出手段は、前記プログラムから関数呼び出しの戻り値を保持する割付対象を検出し、前記予約資源要素記憶手段は、当該割付対象に割り付けるべき戻り値レジスタを記憶することを特徴としており、
また、請求項２２において、前記予約割付対象検出手段は、前記プログラムから値が書き換えられてもよい割付対象を検出し、前記予約資源要素記憶手段は、当該割付対象に割り付けるべき破壊レジスタを記憶することを特徴としており、
また、請求項１９〜２２によれば、割り付けるべき資源要素が予め定められている割付対象が、予約割付対象検出手段によって前記プログラムから検出される。割付手段は、予約割付対象検出手段によって検出された割付対象に割り付けられるべき資源要素を割り付け、割り付けた後に最大の優先度の割付対象に資源要素の何れかを割り付ける。このように、引数レジスタ、戻り値レジスタ、破壊レジスタ等、割り付けるべき資源要素が予め定められている割付対象への資源割り付けの後に優先度順に割付対象を割り付けるため、引数レジスタ、戻り値レジスタ、破壊レジスタを、他の割付対象に割り付けることができるという作用を有する。
【００５１】
また、請求項２３において資源割付装置は更に、プログラム中の各割付対象を、当該割付対象の開始点で生存区間が終了する全ての割付対象と、当該割付対象の終了点で生存区間が始まる全ての割付対象とからなる集合である生存区間継承関係集合に対応づけて記憶する生存区間継承関係集合記憶手段を備え、割付済み−被割付間連続判定手段は、割り付けるべき割付対象についての生存区間継承関係集合を参照し、当該生存区間継承関係集合に、割付済みの割付対象が存在するか否かを判定する第１の判定部と、存在しなければ、生存区間継承関係集合内の他の割付対象を取り出し、取り出した割付対象についての生存区間継承関係集合を参照し、当該生存区間継承関係集合に、割付済みの割付対象が存在するかを判定する第２の判定部と、存在することが判定されるまで、第２の判定部の起動を繰り返させる制御部とを備え、得失値算出手段は、検出結果とされた割付対象の生存区間長を集計する集計部と、割り付けるべき割付対象の生存区間長と集計部によって集計された生存区間長との和の逆数を算出し、算出結果を生存区間の短さとする逆数算出部とを備えることを特徴としており、
また、請求項２３によれば、
割り付けられるべき割付対象についての生存区間継承関係集合が参照され、当該生存区間継承関係集合に、割付済みの割付対象が存在するか否かが第１の判定部によって判定される。存在しなければ、生存区間継承関係集合内の他の割付対象が取り出され、取り出された割付対象についての生存区間継承関係集合が参照され、当該生存区間継承関係集合に、第２の判定部によって、割付済みの割付対象が存在するかが判定される。存在することが判定されるまで、制御部によって、第２の判定部の起動が繰り返させられる。また、検出された割付対象の生存区間長が集計部によって集計され、割り付けられるべき割付対象の生存区間長と集計部によって集計された生存区間長との和の逆数が算出され、算出結果が、逆数算出部によって生存区間の短さとされるという作用を有する。
【００５２】
また、請求項２４において、資源割付装置は更に、
プログラム中の各割付対象を、当該割付対象の開始点で生存区間が終了する全ての割付対象と、当該割付対象の終了点で生存区間が始まる全ての割付対象とからなる集合である生存区間継承関係集合に対応づけて記憶する生存区間継承関係集合記憶手段を備え、
未割り付け−被割付間連続判定手段は、割り付けるべき割付対象についての生存区間継承関係集合を参照し、当該生存区間継承関係集合に、割付済み側重なり割付対象検出手段によって検出された未割り付けの割付対象が存在するか否かを判定する第１の判定部と、存在しなければ、生存区間継承関係集合内の他の割付対象を取り出し、取り出した割付対象についての生存区間継承関係集合を参照し、当該生存区間継承関係集合に、割付済み側重なり割付対象検出手段によって検出された未割り付けの割付対象が存在するかを判定する第２の判定部と、存在することが判定されるまで、第２の判定部の起動を繰り返させる制御部とを備え、得失値算出手段は、検出結果とされた割付対象の生存区間長を集計する集計部と、割り付けるべき割付対象の生存区間長と集計部によって集計された生存区間長との和の逆数を算出し、算出結果を生存区間の短さとする逆数算出部とを備えることを特徴としており、
また、請求項２４によれば、割り付けられるべき割付対象についての生存区間継承関係集合が参照され、当該生存区間継承関係集合に、割付済み側重なり割付対象検出手段によって検出された未割り付けの割付対象が存在するか否かが第１の判定部によって判定される。存在しなければ、生存区間継承関係集合内の他の割付対象が取り出され、取り出された割付対象についての生存区間継承関係集合が参照され、当該生存区間継承関係集合に、割付済み側重なり割付対象検出手段によって検出された未割り付けの割付対象が存在するかが第２の判定部によって判定される。存在することが判定されるまで、制御部によって第２の判定部の起動が繰り返させられる。また、検出結果とされた割付対象の生存区間長が集計部によって、集計される。割り付けられるべき割付対象の生存区間長と集計部によって集計された生存区間長との和の逆数が逆数算出部によって算出され、算出結果が生存区間の短さとされるという作用を有する。
【００５３】
また、請求項２５において、資源割付装置は更に、
プログラム中の各割付対象を、当該割付対象の開始点で生存区間が終了する全ての割付対象と、当該割付対象の終了点で生存区間が始まる全ての割付対象とからなる集合である生存区間継承関係集合に対応づけて記憶する生存区間継承関係集合記憶手段を備え、
未割り付け−割付済み間連続判定手段は、被割付側重なり割付対象検出手段によって検出された未割り付けの割付対象についての生存区間継承関係集合を参照し、当該生存区間継承関係集合に、割付済みの割付対象が存在するか否かを判定する第１の判定部と、存在しなければ、生存区間継承関係集合内の他の割付対象を取り出し、取り出した割付対象についての生存区間継承関係集合を参照し、当該生存区間継承関係集合に、割付済みの割付対象が存在するかを判定する第２の判定部と、存在することが判定されるまで、第２の判定部の起動を繰り返させる制御部とを備え、得失値算出手段は、検出結果とされた割付対象の生存区間長を集計する集計部と、割り付けるべき割付対象の生存区間長と集計部によって集計された生存区間長との和の逆数を算出し、算出結果を生存区間の短さとする逆数算出部とを備えることを特徴としており、
また、請求項２５によれば、被割付側重なり割付対象検出手段によって検出された未割り付けの割付対象についての生存区間継承関係集合が第１の判定部によって参照され、当該生存区間継承関係集合に、割付済みの割付対象が存在するか否かが判定される。存在しなければ、生存区間継承関係集合内の他の割付対象が取り出され、取り出された割付対象についての生存区間継承関係集合が第２の判定部によって参照され、当該生存区間継承関係集合に、割付済みの割付対象が存在するかが判定される。存在することが判定されるまで、第２の判定部の起動が制御部によって繰り返させられる。検出結果とされた割付対象の生存区間長が集計部によって集計される。割り付けられるべき割付対象の生存区間長と集計部によって集計された生存区間長との和の逆数が逆数算出部によって算出され、算出結果が生存区間の短さとされるという作用を有する。
【００５４】
また、請求項２６において、資源割付装置は更に、プログラム中の各割付対象を、当該割付対象の開始点で生存区間が終了する全ての割付対象と、当該割付対象の終了点で生存区間が始まる全ての割付対象とからなる集合である生存区間継承関係集合に対応づけて記憶する生存区間継承関係集合記憶手段を備え、未割り付け−未割り付け間連続判定手段は、被割付側重なり割付対象検出手段によって検出された未割り付けの割付対象についての生存区間継承関係集合を参照し、当該生存区間継承関係集合に、割付済み側重なり割付対象検出手段によって検出された未割り付けの割付対象が存在するか否かを判定する第１の判定部と、存在しなければ、生存区間継承関係集合内の他の割付対象を取り出し、取り出した割付対象についての生存区間継承関係集合を参照し、当該生存区間継承関係集合に、割付済み側重なり割付対象検出手段によって検出された未割り付けの割付対象が存在するかを判定する第２の判定部と、存在することが判定されるまで、第２の判定部の起動を繰り返させる制御部とを備え、得失値算出手段は、検出結果とされた割付対象の生存区間長を集計する集計部と、割り付けるべき割付対象の生存区間長と集計部によって集計された生存区間長との和の逆数を算出し、算出結果を生存区間の短さとする逆数算出部とを備えることを特徴としており、
また、請求項２６によれば、
被割付側重なり割付対象検出手段によって検出された未割り付けの割付対象についての生存区間継承関係集合が第１の判定部によって参照され、当該生存区間継承関係集合に、割付済み側重なり割付対象検出手段によって検出された未割り付けの割付対象が存在するか否かが判定される。存在しなければ、第２の判定部によって、生存区間継承関係集合内の他の割付対象が取り出され、取り出された割付対象についての生存区間継承関係集合が参照され、当該生存区間継承関係集合に、割付済み側重なり割付対象検出手段によって検出された未割り付けの割付対象が存在するかが判定される。存在することが判定されるまで、制御部によって第２の判定部の起動が繰り返させられる。検出結果とされた割付対象の生存区間長が集計部によって集計される。割り付けられるべき割付対象の生存区間長と集計部によって集計された生存区間長との和の逆数が逆数算出部によって算出され、算出結果が生存区間の短さとされるという作用を有する。
【００５５】
また、請求項２７において、割付対象の生存区間は、当該生存区間によって占められるプログラム中の開始点から終了点までの命令位置情報で表され、集計部は、命令位置情報の数を集計し、集計値を生存区間長とすることを特徴としており、
また、請求項２７によれば、集計部によって命令位置情報の数が集計され、集計値が生存区間長とされる。
【００５６】
また、請求項２８において、割付対象の生存区間の開始点及び終了点は、プログラム中の命令位置情報で表され、資源割付装置は更に、プログラム中の割付対象と、各割付対象の生存区間の開始点に相当する命令位置情報と、各割付対象の生存区間の終了点に相当する命令位置情報とを対応づけて記憶する開始終了点記憶手段と、開始終了点記憶手段を参照して、プログラム中の各割付対象の生存区間の開始点に相当する命令位置情報が終了点に相当するものを全て探し出し、探し出した割付対象と、プログラム中の割付対象とを同一の生存区間継承関係集合にする第１の集合化手段と、開始終了点記憶手段を参照して、プログラム中の各割付対象の生存区間の終了点に相当する命令位置情報が、開始点に相当するものを全て探し出し、探し出した割付対象と、プログラム中の割付対象とを同一の生存区間継承関係集合にする第２の集合化手段と、プログラム中の割付対象と、第１及び第２の集合化手段によって集合化された生存区間継承集合とを対応づけて、生存区間継承関係集合記憶部に書き込む書き込み手段とを備えることを特徴としており、請求項２８によれば、第１の集合化手段によって開始終了点記憶手段が参照され、プログラム中の各割付対象の生存区間の開始点に相当される命令位置情報が終了点に相当されるものが全て探し出され、探し出された割付対象と、プログラム中の割付対象とが同一の生存区間継承関係集合にされる。第２の集合化手段によって開始終了点記憶手段が参照され、プログラム中の各割付対象の生存区間の終了点に相当される命令位置情報が、開始点に相当されるものが全て探し出され、探し出された割付対象と、プログラム中の割付対象とが同一の生存区間継承関係集合にされる。プログラム中の割付対象と、第１及び第２の集合化手段によって集合化された生存区間継承集合とが書き込み手段によって対応づけられて、生存区間継承関係集合記憶部に書き込まれるという作用を有する。
【００５７】
また、請求項２９において、高級言語で書かれたプログラムを機械語プログラムに翻訳するコンパイラに用いられ、プログラミング言語で記述されたプログラムの中の変数と生存区間の組である割付対象にレジスタ、メモリ等のハードウェアである資源が有する資源要素を割り付ける資源割付装置であって、
プログラム中の割付対象を、その優先度に対応づけて保持する割付対象保持手段と、前記割付対象保持手段から優先度最大の割付対象を取り出し、優先度が最大の割付対象に資源要素の何れかを割り付ける第１の資源要素割付手段と、直前に割り付けられた割付対象の優先度に対して、次順位の優先度を持つ割付対象を、前記割付対象保持手段から取り出す割付対象取出手段と、前記割付対象取出手段が取り出した割付対象について、生存区間が重なっている割付対象を検出する一次重なり割付対象検出手段と、前記一次重なり割付対象検出手段が検出した割付対象に、既に割り付けられている資源要素を検出する資源要素検出手段と、検出された資源要素とは異なる資源要素が既に割り付けられている割付対象を全て検出する割付対象−資源要素検出手段と、割付対象−資源要素検出手段によって検出された割付済みの割付対象のうち、割付対象取出手段によって取り出された割付対象と生存区間が連続している割付対象を全て判定する利得側連続割付済み割付対象判定手段と、既に割付対象に割り付けられた資源要素がこれから割り付けようとする割付対象にどれだけ適切であるかを示す値である得失値を、連続すると判定された割付済みの割付対象から割付対象取出手段によって取り出された割付対象までの生存区間長の短さに基づき、生存区間が連続すると判定された割付対象に割り付けられている全ての資源要素について算出する第１の得失値算出手段と、算出された得失値を、割付対象−資源要素検出手段によって判定された各資源要素毎に累計する累計手段と、累計手段によって累計された累計値が最大の資源要素を、割付対象取り出し手段が取り出した割付対象に割り付ける第２の資源要素割付手段と、全ての割付対象が割り付けられるまで、前記割付対象取出手段の起動を繰り返えす制御手段とを備えることを特徴としており、
また、請求項２９によれば、前記割付対象保持手段から優先度最大の割付対象が第１の資源要素割付手段によって取り出され、優先度が最大の割付対象に資源要素の何れかが割り付けられる。直前に割り付けられた割付対象の優先度に対して、次順位の優先度が持つ割付対象が、割付対象取出手段によって前記割付対象保持手段から取り出される。前記割付対象取出手段が取り出された割付対象について、一次重なり割付対象検出手段によって生存区間が重なっている割付対象が検出される。前記一次重なり割付対象検出手段が検出した割付対象に、資源要素検出手段によって既に割り付けられている資源要素が検出される。検出された資源要素とは異なる資源要素が既に割り付けられている割付対象が割付対象−資源要素検出手段によって全て検出される。割付対象−資源要素検出手段によって検出された割付済みの割付対象のうち、割付対象取出手段によって取り出された割付対象と生存区間が連続している割付対象が利得側連続割付済み割付対象判定手段によって全て判定される。既に割付対象に割り付けられた資源要素がこれから割り付けようとされる割付対象にどれだけ適切であるかが示す値である得失値が、第１の得失値算出手段によって、連続すると、判定された割付済みの割付対象から割付対象取出手段によって取り出された割付対象までの生存区間長の短さに基づき、生存区間が連続されると、判定された割付対象に割り付けられている全ての資源要素について算出される。算出された得失値が、累計手段によって、割付対象−資源要素検出手段によって判定された各資源要素毎に累計される。累計手段によって累計された累計値が最大の資源要素が、第２の資源要素割付手段によって割付対象取り出し手段が取り出された割付対象に割り付けられる。全ての割付対象が割り付けられるまで、制御手段によって前記割付対象取出手段の起動が繰り返えさせられるという作用を有する。
【００５８】
また、請求項３０において、資源割付装置は更に、割付対象−資源要素検出手段によって検出された割付済みの割付対象のうち、割付対象取出手段によって取り出された割付対象と生存区間が連続せず、かつ、生存区間が重なっていない割付対象を判定する第１の非重なり非連続割付済み割付対象判定手段と、第１の非重なり非連続割付済み割付対象判定手段によって判定された割付済みの割付対象の生存区間と生存区間が重なる未割り付けの割付対象であって、割付対象取出手段によって取り出された割付対象と生存区間が連続している割付対象を検出する利得側連続未割り付け割付対象検出手段と、利得側連続未割り付け割付対象検出手段によって検出された未割り付けの割付対象から、割付対象取出手段によって取り出された割付対象までの生存区間長の短さに基づき、第１の非重なり非連続割付済み割付対象判定手段によって判定された割付済みの割付対象に割り付けられた資源要素の得失値を算出する第２の得失値算出手段と、前記累計手段によって累計された当該資源要素についての得失値から、第２の得失値算出手段によって算出された得失値を減ずる第１の減算手段とを備え、第２の資源要素割付手段は、第１の減算手段によって得失値が減ぜられた得失値が最大の資源要素を、割付対象取出手段が取り出した割付対象に割り付けることを特徴としており、
また、請求項３０によれば、
割付対象−資源要素検出手段によって検出された割付済みの割付対象のうち、割付対象取出手段によって取り出された割付対象と生存区間が連続せず、かつ、生存区間が重なっていない割付対象が第１の非重なり非連続割付済み割付対象判定手段によって判定される。第１の非重なり非連続割付済み割付対象判定手段によって判定された割付済みの割付対象の生存区間と生存区間が重なる未割り付けの割付対象であって、割付対象取出手段によって取り出された割付対象と生存区間が連続している割付対象が利得側連続未割り付け割付対象検出手段によって検出される。利得側連続未割り付け割付対象検出手段によって検出された未割り付けの割付対象から、割付対象取出手段によって取り出された割付対象までの生存区間長の短さに基づき、第１の非重なり非連続割付済み割付対象判定手段によって判定された割付済みの割付対象に割り付けられた資源要素の得失値が第２の得失値算出手段によって算出される。前記累計手段によって累計された当該資源要素についての得失値から、第２の得失値算出手段によって算出された得失値が第１の減算手段によって減ぜられる。第２の資源要素割付手段によって、第１の減算手段によって得失値が減ぜられた得失値が最大の資源要素が、割付対象取出手段が取り出された割付対象に割り付けられるという作用を有する。
【００５９】
また、請求項３１において、資源割付装置は更に、
割付対象−資源要素検出手段によって検出された割付済みの割付対象のうち、一次重なり割付対象検出手段によって検出された割付対象と、生存区間が連続しているものを判定する重なり側連続割付済み割付対象判定手段と、重なり側連続割付済み割付対象判定手段によって判定された割付済みの割付対象から一次重なり割付対象検出手段によって検出された割付対象までの生存区間長の短さに基づき、重なり側連続割付済み割付対象判定手段によって判定された割付済みの割付対象に割り付けられた資源要素の得失値を算出する第３の得失値算出手段と、前記累計手段によって累計された当該資源要素についての累計値から、第３の得失値算出手段によって算出された得失値を減ずる第２の減算手段と、第２の資源要素割付手段は、第２の減算手段によって得失値が減ぜられた後の累計値が最大の資源要素を、割付対象取出手段が取り出した割付対象に割り付けることを特徴としており、
また、請求項３１によれば、
割付対象−資源要素検出手段によって検出された割付済みの割付対象のうち、一次重なり割付対象検出手段によって検出された割付対象と、生存区間が連続しているものが重なり側連続割付済み割付対象判定手段によって判定される。重なり側連続割付済み割付対象判定手段によって判定された割付済みの割付対象から一次重なり割付対象検出手段によって検出された割付対象までの生存区間長の短さに基づき、重なり側連続割付済み割付対象判定手段によって判定された割付済みの割付対象に割り付けられた資源要素の得失値が第３の得失値算出手段によって算出される。前記累計手段によって累計された当該資源要素についての累計値から、第３の得失値算出手段によって算出された得失値が第２の減算手段によって減ぜられる。第２の資源要素割付手段によって、第２の減算手段によって得失値が減ぜられた後の累計値が最大の資源要素が、割付対象取出手段が取り出された割付対象に割り付けられるという作用を有する。
【００６０】
また、請求項３２において、資源割付装置は更に、
割付対象−資源要素検出手段によって検出された割付済みの割付対象のうち、一次重なり割付対象検出手段によって検出された割付対象と生存区間が連続せず、かつ、生存区間が重なっていない割付対象を判定する第２の非重なり非連続割付済み割付対象判定手段と、第２の非重なり非連続割付済み割付対象判定手段によって判定された割付済みの割付対象の生存区間と生存区間が重なる未割り付けの割付対象であって、一次重なり割付対象検出手段によって検出された割付対象と生存区間が連続しているものを判定する重なり側連続未割り付け割付対象判定手段と、重なり側連続未割り付け割付対象判定手段によって判定された割付対象から、一次重なり割付対象検出手段によって検出された割付対象までの生存区間長の短さに基づいて、第２の非重なり非連続割付済み割付対象判定手段によって判定された割付済みの割付対象に割り付けられている資源要素の得失値を算出する第４の得失値算出手段と、前記累計手段によって累計された当該資源要素についての累計値に、第４の得失値算出手段によって算出された得失値を加算する加算手段と、第２の資源要素割付手段は、加算手段によって得失値が加算された累計値が最大の資源要素を、割付対象取出手段が取り出した割付対象に割り付けることを特徴としており、
また、請求項３２によれば、
割付対象−資源要素検出手段によって検出された割付済みの割付対象のうち、一次重なり割付対象検出手段によって検出された割付対象と生存区間が連続せず、かつ、生存区間が重なっていない割付対象が第２の非重なり非連続割付済み割付対象判定手段によって判定される。第２の非重なり非連続割付済み割付対象判定手段によって判定された割付済みの割付対象の生存区間と生存区間が重なる未割り付けの割付対象であって、一次重なり割付対象検出手段によって検出された割付対象と生存区間が連続しているものが重なり側連続未割り付け割付対象判定手段によって判定される。重なり側連続未割り付け割付対象判定手段によって判定された割付対象から、一次重なり割付対象検出手段によって検出された割付対象までの生存区間長の短さに基づいて、第２の非重なり非連続割付済み割付対象判定手段によって判定された割付済みの割付対象に割り付けられている資源要素の得失値が第４の得失値算出手段によって算出される。前記累計手段によって累計された当該資源要素についての累計値に、加算手段によって第４の得失値算出手段によって算出された得失値が加算される。加算手段によって得失値が加算された累計値が最大の資源要素が、第２の資源要素割付手段によって割付対象取出手段が取り出された割付対象に割り付けられるという作用を有する。
【００６１】
＜用語の説明＞
本発明の実施形態の説明の前に以下で使用する用語について説明しておく。
・ループレベル
ループレベルとはループのネストの深さのことであり、中間命令のループレベルとはその中間命令が存在するループのレベルを意味する。例えば、図２６において中間命令i1  のループレベルは1である。中間命令i8は中間命令i31のジャンプ先になっているのでループレベルは2である。
・多資源
メモリなどのように他に比べて豊富な資源要素を持ち、どの資源要素を割付対象に割り付けても特に生成コードの品質に影響を及ぼさない資源を示す。
・割付資源
割付対象に割付け可能な資源要素または多資源を元とする集合である。通常は１つの割付対象に１つの割付資源を割付けるが、ここでは資源は前述のように同じ機能を果たす資源要素の集合であるから割付対象に多資源Ｒを割付けるとは、Ｒに属する資源要素のどれか１つを割付対象に割り付けることとする。
・資源要素（広義）
割付資源の要素を示す。以下特に断りがない限り資源要素は広義の意味とする。
・資源継承関係
資源継承関係とは割付対象同士の割り付けられた資源要素を継承し得る関係をいう。また資源要素の継承とは既に割り付けられた資源要素と同一の資源要素を割り付けることをいい、このような同一資源要素への割り付けによってコード生成装置に転送命令の生成を省かせることができる。加えて割り付け済みの資源要素をまわりに広げてゆくことができる。プログラム中ではこのような資源継承関係は生存区間の連続によって表される。即ちプログラム上のある中間命令s1が、割付対象ｙの生存区間の終了点であり、かつ中間命令s1が、割付対象ｘの開始点であれば、これらの割付対象ｘと割付対象ｙとは資源要素継承関係にある。但し生存区間の終始点は一致しているが、同一の資源要素に割り付けても転送命令の生成を省かせることが明確に不可能な場合は資源継承関係にないとする。
【００６２】
例えばプログラム上の中間命令s1:  x  =  y;において割付対象xの生存区間の開始点が中間命令s1であり、割付対象yの生存区間の終了点が中間命令s1であるとき割付対象x,割付対象yは同じ資源要素に割付られると、割付対象yから割付対象xへの転送は不要である。よって割付対象xと割付対象yは資源継承関係にある。
【００６３】
またターゲットマシンが２アドレス形式のマイクロプロセッサであり、被演算子に演算の結果が格納されるとき（ターゲットマシンの減算命令の被減数側のオペランドに演算結果が格納されるとき）、プログラム上の中間命令s2:  z  =  x  -  w;において割付対象zの生存区間の開始点が中間命令s2であり、割付対象xの生存区間の終了点が中間命令s2である際に割付対象xと割付対象zは資源継承関係にある。そのため割付対象xと割付対象zを同じ資源要素に割り付けると不要な転送命令は生成されない。しかしここで割付対象wも中間命令s2が生存区間の終了点である場合、割付対象zと資源要素に割り付けるとかえって転送命令が増えるので割付対象zと割付対象wとは資源継承関係にない。
【００６４】
また一般に割付対象Aと割付対象A1、割付対象A2、....、割付対象An-2と割付対象An-1、割付対象An-1と割付対象Anが各々資源継承関係にあるとき割付対象Aと割付対象Anは「間接的に資源継承関係にある」と言うことにする。例えば、上記の中間命令s1、s2において割付対象yと割付対象zとは割付対象xを介して間接的に資源継承関係にある。
・使用コスト値
使用コスト値とはこれから割り付けられようとする割付対象ｘに各々の資源の資源要素を割り付ければ、割付対象ｘが使用されている中間命令のコードサイズ、実行時間がどれだけになるかを示す値である。中間命令と、使用コスト値との関係を図１２及び図１３に示す使用コスト計算例の説明図を参照しながら説明を行う。
【００６５】
図１２は各資源の資源要素を被演算子にすることで機械語命令のコードサイズ又は実行時間がどのように増減するかを示した図である。
本図には「C(x,AR,INDIRECT REFERENCE)＝１」、「C(x,DR,INDIRECT REFERENCE)＝２」、「C(x,Mem,INDIRECT REFERENCE)＝３」という数式が示されている。これらは「間接参照」という命令を機械語命令で行うのにどの資源を用いるのがよいかを示すものである。
【００６６】
この「C(x,AR,INDIRECT REFERENCE)＝１」はアドレスレジスタ（ＡＲ）で間接参照という命令を行うとメモリサイズ又は実行時間が「１」だけ増加することを示す。
「C(x,DR,INDIRECT REFERENCE)＝２」はデータレジスタ（ＤＲ）で間接参照という命令を行うと、メモリサイズ又は実行時間が「２」だけ増加することを示す。
【００６７】
「C(x,Mem,INDIRECT REFERENCE)＝３」はメモリ（Ｍｅｍ）で間接参照という命令を行うとメモリサイズ又は実行時間が「３」だけ増加することを示す。
また図中の「C(x,Mem,ADDITION)＝３」はメモリで加算を行うと、メモリサイズ又は実行時間が「３」増加することを示す。
「C(x,Mem,SUBTRACTION)＝３」はメモリで減算を行うとメモリサイズ又は実行時間が「３」増加することを示す。
【００６８】
図１３において左半分に示しているのは中間プログラム例である。この中間プログラム内の割付対象の一部は○印で囲まれ、当該○印からは矢線が伸びている。図中の割付対象「ｓ」からは矢線ａ１１が伸び、ａ１１の先は３つに別れている。この先にある「C(s,AR,INDIRECT REFERENCE)」「C(s,DR,INDIRECT REFERENCE)」「C(s,Mem,INDIRECT REFERENCE)」は割付対象ｓが間接参照という命令で使用されていることを示している。その下の「Cost(AR,ｓ)=１」「Cost(DR,ｓ)=２」「Cost（Mem,ｓ)=３」は割付対象ｓについての使用コスト値の集計を示している。即ち、割付対象ｓに資源ＡＲの資源要素を割り付ける場合、その使用コスト値が「１」となり、割付対象ｓに資源ＤＲの資源要素を割り付ける場合、その使用コスト値が「２」となることを示す。また割付対象ｓにＭｅｍを割り付ける場合、その使用コスト値が「３」となることを示す。
【００６９】
またこのプログラム例には割付対象ｒが３箇所存在し、これらの割付対象は○印で囲まれている。更にこれらの割付対象からは矢線ａ１３、ａ１４、ａ１５が伸びている。これらの矢線の先には「C(r,AR,INDIRECT REFERENCE)」、「C(r,DR,INDIRECT REFERENCE)」「C(r,Mem,INDIRECT REFERENCE)」が３つずつ存在するが、これらは基本ブロック中において割付対象ｒが３箇所使用されているためその３箇所について評価を行うことを示す。この３箇所についての使用コスト値の集計が「Cost(AR,ｒ)=３」「Cost(DR,ｒ)=６」「Cost（Mem,ｒ)=９」である。
【００７０】
以上のような使用コスト値の集計値の算出を矢線ａ１１、ａ１２、ａ１３・・・のように行うと、図１３の下半分の表に示すように全ての割付対象についての３通りの資源についての使用コスト値の集計が得られる。この集計が各割付対象に対する適応、不適応のパラメータであり、これが小さいほどその割付対象に資源が適応していることを示している。但しこの使用コストの短所はコードサイズや実行時間を目安にしたものであるから、同機能のデータレジスタDO〜D2やアドレスレジスタA0〜A2は使用コストが何れも同値になり、おおまかな目安にしかならないことである。
・得失値
得失値とは、既に割付対象に割り付けられた資源要素がこれから割り付けようとする割付対象にどれだけ影響するかを示す値である。そのため、得失値は既に割り付けられたそれぞれの資源要素に与えられる。この得失値を資源要素毎に累計したものは利得値と称される。
【００７１】
割付済みの資源要素の得失値がどのような値になるかを図１４に示す説明図を参照しながら説明を行う。図１４は利得要因を処理対象とした場合の各資源要素の得失値を表した説明図である。尚、図中の割付対象ｘは優先度による優先順位が次順であり、割り付けの順番がまわってきた割付対象である（以降の説明において特に断らない場合は割付対象ｘをこの意味で用いる。）。
【００７２】
図中に示されている縦線は割付対象の生存区間を表し、そのうち、白抜きのものは未割り付けの割付対象、黒で塗り潰されているものは割付済みの割付対象を示す。当該割付対象の生存区間の始点及び終点を黒点「・」で表す。図中の黒点の中には破線の横線で結ばれているものが存在するが、これは生存区間の終点と始点とが一致していることを示し、このように破線によって終始点が結ばれている割付対象同士は資源継承関係にあることが判る。生存区間を表す縦線にはそれぞれ、「割付対象ｘ１」、「割付対象ｘ２」、「割付対象ｘ１１」のように当該生存区間を有する割付対象の名称を示す文字列が付されている。
【００７３】
更に当該割付対象のうち、資源要素を割り付けているものは当該文字列の真下に資源要素の名称を示す文字列が示されている。この資源要素の名称を示す文字列から矢線が伸び、その矢先には「＋１／Ｌ１」、「＋１／（Ｌ１＋Ｌ２）」、「＋１／（Ｌ１＋Ｌ３＋Ｌ４）」という数式が存在するが、これらの数式は各資源要素の得失値を示している。
【００７４】
本図において文字列「資源要素Ｄ２」から矢線が伸び、その矢先が、数式「＋１／Ｌ１」に伸びているが、これは割付対象ｘ３に割り付けられた資源要素Ｄ２の得失値が「＋１／Ｌ１」になることを示す。
また文字列「資源要素Ｄ３」から矢線が伸び、その矢先が、数式「＋１／（Ｌ１＋Ｌ２）」に伸びているが、これは割付対象ｘ１に割り付けられた資源要素Ｄ３の得失値が「＋１／（Ｌ１＋Ｌ２）」になることを示す。得失値がこのような値になるのは割付対象ｘ１の生存区間と、割付対象ｘの生存区間との間に生存区間長Ｌ２の生存区間が介在しており、この生存区間長が得失値に反映されているからである。
【００７５】
更に文字列「資源要素Ｄ１」から矢線が伸び、その矢先が、数式「＋１／（Ｌ１＋Ｌ３＋Ｌ４）」に伸びているが、これは割付対象ｘ２に割り付けられた資源要素Ｄ１の得失値が、＋１／（Ｌ１＋Ｌ３＋Ｌ４）になることを示す。得失値がこのような値になるのは割付対象ｘ２の生存区間と、割付対象ｘの生存区間との間に生存区間長Ｌ３及び生存区間長Ｌ４の生存区間が介在しており、この生存区間長が得失値に反映されているからである。
【００７６】
一方、本図において割付対象ｘ１１を表す縦線は生存区間Ｌ３を有する割付対象と並行部分を有するので割付対象ｘ１１と生存区間Ｌ３を有する割付対象ｘ5と生存区間が重なることが判る。
この縦線の左下に「−１／（Ｌ１＋Ｌ３）」という文字列が付されれているが、これは割付対象ｘ１１に割り付けられている資源要素Ｄ０の得失値が「−１／（Ｌ１＋Ｌ３）」であることを示す。得失値がこのような値になるのは割付対象ｘ１１の生存区間と、割付対象ｘの生存区間との間に生存区間長Ｌ３の生存区間が介在しており、この生存区間長が反映されるからである。
【００７７】
尚、本図において得失値「−１／（Ｌ１＋Ｌ３）」に負の符号が付され、「＋１／（Ｌ１＋Ｌ２）」、「＋１／（Ｌ１＋Ｌ３＋Ｌ４）」に正の符号が付されている理由は以下の通りである。
得失値「＋１／（Ｌ１＋Ｌ２）」が与えられた資源要素Ｄ３は割付対象ｘを割り付ける際、転送命令を削除できるような割付対象（割付対象ｘ１）に割り付けられ、得失値「＋１／（Ｌ１＋Ｌ３＋Ｌ４）」が与えられた資源要素Ｄ１は割付対象ｘを割り付ける際、転送命令を削除できるような割付対象（割付対象ｘ２）に割り付けられているのに対し得失値「−１／（Ｌ１＋Ｌ３）」が与えられた資源要素Ｄ０は割付対象ｘを割り付ける際転送命令を生じるような割付対象（割付対象ｘ１１）に割り付けられているからである。
【００７８】
また得失値の分母は割付対象ｘを基点とした生存区間長の和であるので生存区間長Ｌ１を単に「１」としても構わない。
以上の説明から割付対象ｘに近い割付対象に割り付けられた資源要素ほど得失値は大きく割付対象ｘに遠い割付対象に割り付けられた資源要素ほど得失値は小さくなることが判る。割り付けの順番が回ってきた割付対象はより近い割り付け済み資源要素に影響されるのである。先に述べたように使用コストではデータレジスタD0,D1,D2間アドレスレジスタA0,A1,A2間等同機能の資源間では優劣の決着がつきにくい。これに対して得失値はデータレジスタD0,D1,D2のうち、どれが先に割り付けられているかに影響する。割付済みの場合でもデータレジスタD0,D1,D2のうち、どれが割付対象xに一番近いかで優劣が決着する。
【００７９】
また割り付け済みの割付対象からみれば、自身の身近にある後順の割付対象に影響を与えることができる。つまり割付済みの割付対象は周辺の割付対象に自身と同じ資源要素を分配することができる。本実施形態でもネストレベルと使用頻度を表した割付優先度の順に割付対象に資源要素を割り付けてゆくのだが、この優先度と得失値との組み合わせによって、ネストレベルが深い箇所に優先してレジスタを割り付け、その割り付け済みのレジスタをネストレベルが浅くなる箇所に拡散してゆくようなスマートな割付結果が得ることができる。同様に使用頻度が高い箇所に優先してレジスタを割り付け、その割り付け済みのレジスタをネストレベルが低い箇所に拡散してゆくようなスマートな割付結果を得ることができる。更に引数レジスタ、戻り値レジスタ、破壊レジスタ等予め割り付ける相手が決められた割付対象がその資源を周りに拡げてゆくようなスマートな資源割り付けを実現できる。
【００８０】
以上の説明は割付対象ｘと生存区間が連続する割付済み割付対象について説明を行ったが、連続するものばかりを見ていればかえって損失が生じることがある。これは、割付対象ｘと重なる側の生存区間の延長線上に既に幾つもの資源要素が割り付けられている場合はこれらに割り付けることを何とか避けねばならない。避け得ない場合はこれらのうち、最も損失が軽度のものを選択する必要がある。このような損失を定量的に見積もるためにも得失値は用いられる。損失を見積もるために得失値を用いる場合を図１５の説明図を参照しながら説明を行う。図１５において縦線は割付対象を表し、そのうち、白抜きのものは未割り付けの割付対象、黒で塗り潰されているものは割付済みの割付対象を示す。当該生存区間の始点及び終点を黒点「・」で表す。図中の黒点の中には破線の横線で結ばれているものが存在するが、これは生存区間の終点と始点とが一致していることを示し、このように破線によって終始点が結ばれている割付対象同士は資源継承関係にあることが判る。生存区間を表す縦線にはそれぞれ、「割付対象ｘ２」、「割付対象ｘ３」、「割付対象ｘ４」のように当該生存区間を有する割付対象の名称を示す文字列が付されている。
【００８１】
更に当該割付対象のうち、資源要素を割り付けているものは当該文字列の真下に資源要素の名称を示す文字列が示されている。この資源要素の名称を示す文字列から伸びる矢線の先には「＋Ｐｘ／（Ｌ２＋Ｌ３）」、「−Ｐｘ／（Ｌ２＋Ｌ３）」という数式が示されているが、これらは各資源要素の得失値を示す。
本図において文字列「資源要素Ｄ１」から矢線が伸びその矢先が文字列「−Ｐx／（Ｌ２＋Ｌ３）」に至っているが、これは割付対象ｘ４に割り付けられた資源要素Ｄ１のマイナスの符号を持った得失値、つまり損失を示す得失値が「−Ｐx／（Ｌ２＋Ｌ３）」であることを示す。得失値がこのような値になるのは割付対象ｘ４の生存区間と、割付対象ｘと生存区間が重なる割付対象ｘ２の生存区間との間に生存区間長Ｌ２及びＬ３の生存区間が介在しており、この生存区間長が、得失値に反映されているからである。
【００８２】
一方、本図において割付対象ｘ３１を表す縦線は生存区間長Ｌ３を有する割付対象ｘ３と並行部分を有するので割付対象ｘ３１と割付対象ｘ３とは生存区間が重複し合うことが判る。
この縦線の左下に「＋Ｐx／（Ｌ２＋Ｌ３）」という文字列が付されれているが、これは割付対象ｘ３１に割り付けられている資源要素Ｄ２の得失値が「＋Ｐx／（Ｌ２＋Ｌ３）」であることを示す。得失値がこのような値になるのは割付対象ｘ３１の生存区間と、割付対象ｘと生存区間が重なる割付対象ｘ２の生存区間との間に生存区間長Ｌ２及び生存区間長Ｌ３の生存区間が介在しており、この生存区間長が反映されるからである。
【００８３】
尚、本図において得失値「−Ｐｘ／（Ｌ２＋Ｌ３）」に負の符号が付され、「＋Ｐｘ／（Ｌ２＋Ｌ３）」に正の符号が付されている理由は以下の通りである。
得失値「＋Ｐｘ／（Ｌ２＋Ｌ３）」が与えられた資源要素Ｄ２は、割付対象ｘを割り付ける際、転送命令を削除できるような割付対象（割付対象ｘ３１）に割り付けられ、得失値「−Ｐｘ／（Ｌ２＋Ｌ３）」が与えられた資源要素Ｄ１は、割付対象ｘを割り付ける際、転送命令を生じるような割付対象（割付対象ｘ４）に割り付けられているからである。また得失値の分母は割付対象ｘ２を基点とした生存区間長の和であるので生存区間長Ｌ２を単に「１」としても構わない。
・追跡対象
追跡対象とは資源継承関係を辿って行き、各資源要素の得失値を算出するための情報である。そのため追跡対象はプログラムにおいて現在資源継承関係を辿っている箇所を示す情報（これは割付対象名で表される）とその箇所の割付対象と割付対象ｘとの間に介在する生存区間長の総和と、その現在位置において割付可能な資源要素の集合とを含んでいる。これらの情報を含むため、本実施形態では追跡対象を構造体変数として扱い、上記の現在位置情報、生存区間長の総和、割付可能な資源要素集合をその構造体のメンバーとして扱っている（本実施形態では追跡対象をA、現在の追跡位置の割付対象をA.ASO、生存区間長の総和をA.LNS、資源要素集合をA.RESと表している。）。
・後順コスト値
後順コスト値とは優先度が割付対象ｘより低く割付対象ｘより後に割り付けられる割付対象を使用している中間命令のコードサイズ、実行時間が割付対象ｘに各々の資源の資源要素を割り付けることでどう増減するかを示す値である。
【００８４】
優先順位が後順である未割り付けの割付対象の後順コスト値がどのような値になるかを図１６の説明図を参照しながら説明を行う。図１６は未割り付けの割付対象の後順コスト値を表した説明図である。
図中に示されている白抜きの縦線は割付対象の生存区間を表し、当該割付対象の生存区間の始点及び終点を白丸で表す。図中の白丸の中には破線の横線で結ばれているものが存在するが、これは生存区間の終点と始点とが一致していることを示し、このように破線によって終始点が結ばれている割付対象同士は資源継承関係にあることが判る。生存区間を表す縦線にはそれぞれ「割付対象ｘ１」、「割付対象ｘ２」、「割付対象ｘ３」のように割付対象の名称を示す文字列が付されている。また割付対象ｘ１の左隣には「「x1=u+v」「y=x1+200」「r=x1/40」「t=30+x1」「w=x1+3」」といった中間命令群が存在する。これらは中間プログラムにおいて割付対象ｘ１が使用されている中間命令群を表している。
【００８５】
また割付対象ｘ２の左隣には「「x2=u+v」「y=x2+200」「r=x2/40」「t=30+x2」「w=x2+3」」といった中間命令群が存在するが、これらは中間プログラムにおいて割付対象ｘ２が使用されている中間命令群を表している。
更に割付対象ｘ３の左隣には「「x3=u+v」「y=x3+200」「r=x3/40」「t=30+x3」「w=x3+32」」といった中間命令群が存在するが、これらは中間プログラムにおいて割付対象ｘ３が使用されている中間命令群を表している。
【００８６】
本図において「割付対象ｘ１」という文字列の真下には『ＤＲの後順コスト値』、『ＡＲの後順コスト値』といった文字列が存在し、更にその下には『Cost(DR)／L』『Cost(AR)／L』という数式が存在するが、これらの数式は資源であるデータレジスタ、アドレスレジスタの資源要素を割付対象ｘ１に割り付けた場合の割付対象ｘ１の後順コスト値を示している。また割付対象ｘ１の左隣に位置する中間命令群の各中間命令『「x1=u+v」「y=x1+200」「r=x1/40」「t=30+x1」「w=x1+3」』から伸びた矢印がこの数式における『Cost(DR)』『Cost(AR)』に至っているが、これは後順コスト値の式における使用コストの集計値『Cost(DR)』『Cost(AR)』が、データレジスタＤＲ、アドレスレジスタＡＲの資源要素を割り付けた場合の割付対象ｘ１の使用コスト値の集計値であることを示している。
【００８７】
本図において「割付対象ｘ２」といった文字列の真下には『ＤＲの後順コスト値』、『ＡＲの後順コスト値』といった文字列が存在し、更にその下には『Cost(DR)／(L1+L)』『Cost(AR)／(L1+L)』という数式が存在するが、これらの数式は割付対象ｘ２の後順コスト値を示している。また割付対象ｘ２の左隣に位置する中間命令群の各中間命令『「x2=u+v」「y=x2+200」「r=x2/40」「t=30+x2」「w=x2+3」』から伸びた矢印がこの後順コスト値の式における『Cost(DR)』『Cost(AR)』に至っているが、これは後順コスト値の式における使用コストの集計値『Cost(DR)』『Cost(AR)』が、データレジスタＤＲ、アドレスレジスタＡＲの資源要素を割り付けた場合の中間命令群での割付対象ｘ２の使用コスト値の集計値であることを示している。この使用コストの集計値『Cost(DR)』『Cost(AR)』が、数式において生存区間長（Ｌ１＋Ｌ）で割られているが、これは割付対象ｘ２と割付対象ｘとの間に割付対象ｘ１が介在しており、これの生存区間長（Ｌ１＋Ｌ）が後順コスト値に反映されていることを示す。
【００８８】
「割付対象ｘ３」の文字列の真下には『ＤＲの後順コスト値』、『ＡＲの後順コスト値』といった文字列が存在し、更にその下には『Cost(DR)／(L1+L2+L)』『Cost(AR)／(L1+L2+L)』という数式が存在するが、これらの数式は割付対象ｘ３の後順コスト値を示している。また割付対象ｘ３の左隣に位置する中間命令群の各中間命令『「x1=u+v」「y=x3+200」「r=x3/40」「t=30+x3」「w=x3+32」』から伸びた矢印はこの後順コスト値の式における使用コストの集計値『Cost(DR)』『Cost(AR)』に至っているが、これは後順コスト値の式における『Cost(DR)』『Cost(AR)』が、データレジスタＤＲ、アドレスレジスタＡＲの資源要素を割り付けた場合の中間命令群での割付対象ｘ３の使用コスト値の集計値であることを示している。この使用コストの集計値『Cost(DR)』『Cost(AR)』が数式において生存区間長（Ｌ１＋Ｌ２＋Ｌ）で割られているが、これは割付対象ｘ３と割付対象ｘとの間に割付対象ｘ１、ｘ２が介在しており、これの生存区間長の総和（Ｌ１＋Ｌ２＋Ｌ）が後順コスト値に反映されていることを示す。尚、後順コスト値の分母は割付対象ｘを基点とした生存区間長の和であるので生存区間長Ｌを単に「１」としても構わない。
【００８９】
＜資源割付装置１３の構成＞
図１は資源割付装置１３の構成図である。資源割付装置１３は割付対象保持部２１と、割付対象生成部２２と、生存区間重複割付対象検出部２３と、資源継承割付対象検出部２４と、割付優先度計算部２５と、割付資源要素決定部２６と、資源割付制御部２７とで構成される。
【００９０】
割付対象保持部２１は割付対象生成部２２で生成された割付対象と、割付対象の情報とからなる割付情報テーブルを保持し、また割付状況テーブルを保持する。
割付情報テーブルの一例を図１７及び図１８に示す。図１７は以下で行う割り付け処理によって資源要素が割付けられる割付対象の割付情報を表している。尚これらの図の内容は図２６に示す中間プログラム例内に存在する割付対象及び生存区間と対応している。
【００９１】
図１７に示すように割付情報テーブルは割付対象ｎ１０と当該割付対象の生存区間がプログラム内のどれだけの範囲を占めているかを中間命令の集合で表した割付対象の生存区間ｎ１１と、当該集合の要素数で表された当該割付対象の生存区間長ｎ１２と、当該割付対象が使用される中間命令を示す使用中間命令集合ｎ１３と、当該生存区間の開始点となる中間命令の集合である開始点集合ｎ１４と、当該生存区間の終了点となる中間命令の集合である終了点集合ｎ１５と、当該割付対象の生存区間と重複する生存区間を有する割付対象の集合である重複割付対象集合ｎ１６と、当該割付対象と資源継承関係にある割付対象の集合を表した資源継承割付対象集合ｎ１７と、当該割付対象の割付優先度ｎ１８とからなる。
【００９２】
本図において割付対象「t35」の右隣の「i2〜i6」は割付対象t35の生存区間が、図２６における、i2からi6までの中間命令によって表されることを示す。
またその右隣の「５」は割付対象「t35」の生存区間長を示す。その右隣の「i1、i5、i6」は割付対象「t35」を使用している中間命令を示す。その右隣の「i1」は割付対象「t35」の開始点集合が、「i1」であることを示す。その右隣の「i6」は割付対象「t35」の終了点集合が、「i6」であることを示す。その右隣の「t34、t1、a1、p1」は割付対象「t35」の重複割付対象集合が、「t34、t1、a1、p1」であることを示す。その右隣の「Pr1」は割付対象「t35」と資源継承関係にある割付対象が「Pr1」であることを示す。その右隣の「0.6」は割付対象「t35」の優先度を示す。尚、開始点である「i1」が生存区間n11に含まれていないのは、生存区間の終始が一致する割付対象間の生存区間が重ならないということを、生存区間の集合積により単純に判定可能とするためである。よって全ての割付対象の生存区間には、開始点を含めないものとする。
【００９３】
また図１８は実引数(Ar)、関数の戻り値(Fr)、破壊レジスタ(Br)等、既に資源要素が割付けられている割付対象の割付情報の一例を表している。
図１８に示す割付情報テーブルは割付対象ｎ２０と、当該割付対象の生存区間が中間プログラム内のどれだけの範囲を占めているかを中間命令の集合で表した割付対象の生存区間ｎ２１と、当該集合の要素数で表された当該割付対象の生存区間長ｎ２２と、当該割付対象が使用される中間命令を示す使用中間命令集合ｎ２３と、当該生存区間の開始点となる中間命令の集合である開始点集合ｎ２４と、当該生存区間の終了点となる中間命令の集合である終了点集合ｎ２５と、当該割付対象の生存区間と重複する生存区間を有する割付対象の集合である重複割付対象集合ｎ２６と、当該割付対象と資源継承関係にある割付対象を表した資源継承関係割付対象集合ｎ２７と、当該割付対象に割り付けられている割付資源要素ｎ２８とからなる。
【００９４】
更に割付け状況テーブルの一例を図１９（ａ）に示す。割付け状況テーブルは割付対象の一覧と、各割付対象に割り付けられた資源要素を記入する記入欄とからなり割り付けがどのように進行しているかが反映されている。尚本図の内容は図２６に示す中間プログラム例内に存在する割付対象及び生存区間と対応している。
【００９５】
本図の記入欄のうち、右端に「(a)」と付されたものは優先度が最大の割付対象である「t262」が割り付けられた時点での割り付け状況を示している。また右端に「(b)」と付されたものは優先度が次に大きい割付対象である「t263」が割り付けられた時点での割り付け状況を示している。更に右端に「(c)」と付されたものは優先度が次に大きい割付対象である「t264」が割り付けられた時点での割り付け状況を示している。
【００９６】
割付対象生成部２２はデータフロー解析の結果（以下データフロー情報と呼ぶ）や制御フロー解析の結果（以下制御フロー情報と呼ぶ）をもとに割付対象を生成する。またこのとき生存区間や使用中間命令、生存区間の開始点、終了点も検出される。更に図１８のように割付処理の前に割り付けることが必要な割付対象はここで資源要素を割り付ける。生成された割付対象は割付対象保持部２１に格納される。
【００９７】
生存区間重複割付対象検出部２３は割付対象同士の生存区間の重なりを調べる。つまり任意の割付対象ｘと生存区間が重なる割付対象の集合である割付対象集合Ｏｖ（ｘ）を求める。Ｏｖ（ｘ）の内容は割付対象保持部２１に保持される。資源継承割付対象検出部２４は割付対象保持部２１に保持されている割付対象に関して資源継承関係にある全ての割付対象を検出する。即ち任意の割付対象ｘと資源継承関係にある割付対象の集合である割付対象集合Ｒｓ（ｘ）を求める。Ｒｓ（ｘ）の内容は割付対象保持部２１に保持される。
【００９８】
Ｒｓ（ｘ）を得るための集合化は以下のようにして行われる。
割付対象保持部２１は各割付対象と、各割付対象の生存区間の開始点に相当する中間命令と、各割付対象の生存区間の終了点に相当する中間命令とを対応づけて保持しているので、資源継承割付対象検出部２４は保持している割付対象のうち、割付対象ｘの生存区間の開始点に相当する中間命令が、終了点に相当するものを全て探し出す。そして探し出した割付対象を割付対象ｘの資源継承割付対象集合に格納する。
【００９９】
また割付対象ｘの生存区間の終了点に相当する中間命令が、開始点に相当する割付対象を全て探し出す。そして探し出した割付対象と、割付対象ｘとを同一の集合にする。以上の処理を繰り返し、各割付対象についてのＲｓ（ｘ）を生成する。但し明らかに探し出した割付対象と割付対象ｘとに同じ資源要素を割り付けても、転送命令を省けないときは割付対象ｘの資源継承割付対象集合に格納しない。
【０１００】
割付優先度計算部２５は割付対象保持部２１に保持されている割付対象ｘについての割付優先度を計算する。割付優先度とは資源要素への割り付けをどの割付対象から行なうかを示す優先度である。ここでは以下の計算式を使用して求める。
割付優先度  ＝  （ｘの使用中間命令が存在するループレベルの総和）／ｘの生存区間の長さ
割付資源要素決定部２６は割付情報テーブルの記述内容に基づいて割付対象に資源要素を割付ける。
【０１０１】
資源割付制御部２７は割付け処理全体を制御する。
図５は資源割付制御部２７のフローチャートである。
ステップａ１では資源割付制御部２７は割付対象生成部２２を起動する。
ステップａ２では資源割付制御部２７は生存区間重複割付対象検出部２３を起動する。
【０１０２】
ステップａ３では資源割付制御部２７は資源継承割付対象検出部２４を起動する。
ステップａ４では資源割付制御部２７は割付優先度計算部２５を起動する。
ステップａ５では資源割付制御部２７は割付資源要素決定部２６を起動する。
＜図１に示した割付資源要素決定部２６の構成＞
割付資源要素決定部２６は割付情報テーブルの保持内容に基づいて各割付対象に割り付ける資源要素を決定するように構成されている。
【０１０３】
図２は図１における割付資源要素決定部２６の構成図である。
割付資源要素決定部２６は割付候補資源要素保持部３１と、割付可能資源要素検出部３２と、使用コスト計算部３４と、使用コスト保持部３５と、推定利得計算部３６と、利得保持部３７と、資源要素決定制御部３８と、資源別コスト計算部３９と、資源別コスト保持部４０と、評価資源保持部４１とで構成される。  図６は資源要素決定制御部３８のフローチャートである。
【０１０４】
本フロ−チャ−トは図６に示すように割付対象ｘに割り付け可能な資源要素を求めるステップｂ３と、割り付け可能な資源要素が複数個存在する場合、各資源要素の使用コストを算出することによって割り付けるべき資源要素を選考するステップｂ４と、選考の結果１つの資源要素のみが残れば、その資源要素に割付対象ｘを割り付けるステップｂ１６と、選考の結果複数の資源要素が残れば、それらに候補を絞り込むステップｂ７と、絞り込まれた候補について得失値を算出することで割付対象ｘに割り付ける資源要素の再選考を行うステップｂ８と、再選考の結果単一資源の資源要素が残った場合、その資源要素を割付対象ｘに割り付けるステップｂ１４と、再選考の結果、複数資源の資源要素が残った場合、各資源の後順コスト値を算出して各資源が有する資源要素の再々選考を行うステップｂ１２とを有し、以上の処理を未割り付けの割付対象について割付優先度順に行うループ構造（ステップｂ１〜ｂ１４）になっている。
【０１０５】
本フロ−チャ−トにおいて集合Ｒは割付対象ｘと生存区間が重なる割付対象に割付けられていない資源要素の集合を示す。
以降、本フロ−チャ−トが有する各ステップを順を追って更に詳しく説明してゆく。
ステップｂ１では資源要素決定制御部３８は割付対象保持部２１に保持されていて資源要素が未だ割付られていない割付対象が存在するときステップｂ２を行ない、割付対象保持部２１に存在しないときは割付資源要素決定部２６の処理を終了する。
【０１０６】
ステップｂ２では資源要素決定制御部３８は割付対象保持部２１に保持されている未割付けの割付対象のうち、割付優先度計算部２５で求めた割付優先度が最大の割付対象ｘを取り出す。
ステップｂ３では割付可能資源要素検出部３２を起動して割付対象ｘに割付け可能な資源要素の集合を求める。即ち、割付対象ｘと生存区間が重なる割付対象に割付けられていない資源要素（割付可能資源要素という。）の集合Ｒを求め、割付候補資源要素保持部３１に保持させる。
【０１０７】
ステップｂ４では更に詳しくは使用コスト計算部３４を起動して割付候補資源要素保持部３１に保持されている集合Ｒの各資源要素に対して割付対象ｘの中間命令での使用コストを計算し、計算結果を使用コスト保持部３５に保持させる。
ステップｂ５では割付候補資源要素保持部３１に保持されている資源要素のうち、ステップｂ４で得られた使用コストが最小である資源要素に多資源ｒｈが存在するときはステップｂ１５を行ない、そうでないときはステップｂ６を行なう。
【０１０８】
ステップｂ６では割付候補資源要素保持部３１に保持されている資源要素のうち、ステップｂ４で得られた使用コストが最小の資源要素ｒが一つしかないときはステップｂ１６を行ない、そうでないときはステップｂ７を行なう。
ステップｂ７では割付候補資源要素保持部３１を一旦空にしてステップｂ４で得られた使用コストが最小の資源要素のみを新たに割付候補資源要素保持部３１に保持させる。
【０１０９】
ステップｂ８では更に詳しくは推定利得計算部３６を起動し、割付対象ｘの資源継承関係にある割付対象から資源要素毎の利得値を求め、求めた利得値を利得保持部３７に保持させる。
ステップｂ９では割付候補資源要素保持部３１に保持されている資源要素のうち、ステップｂ８で求められ、利得保持部３７に保持されている利得値が最大の資源要素の集合ＲＳを求め、割付候補資源要素保持部３１の内容を一旦空にし、集合ＲＳに属する資源要素を格納する。
【０１１０】
ステップｂ１０では集合ＲＳ内の資源要素が属する資源の集合ＲＥＳを求め、評価資源保持部４１に格納する。
ステップｂ１１では評価資源保持部４１に保持されている集合ＲＥＳに複数の資源が存在する場合にステップｂ１２を行ない、そうでない場合はステップｂ１４を行なう。
【０１１１】
ステップｂ１２では更に詳しくは資源別コスト計算部３９を起動し、後順コスト値の算出を行ない、各資源毎の計算結果を資源別コスト保持部４０に算出する。
ステップｂ１３では評価資源保持部４１に属しかつ、資源別コスト保持部４０に格納されているコストが最小の資源が有する資源要素でありかつ、割付候補資源要素保持部３１に保持されている資源要素を割付対象ｘに割り付け、ステップｂ１へ戻る。
【０１１２】
ステップｂ１４では割付候補資源要素保持部３１に保持されている資源要素を割付対象ｘに割り付け、ステップｂ１へ戻る。
ステップｂ１５ではｘと生存区間が重なる割付対象に多資源ｒｈの資源要素が割付けられているときはその資源要素とは異なる多資源ｒｈの資源要素を割付対象ｘに割り付け、ステップｂ１へ戻る。
【０１１３】
ステップｂ１６では資源要素ｒを割付対象ｘに割り付け、ステップｂ１へ戻る。
割付候補資源要素保持部３１は割付対象ｘについての割付可能資源要素を保持する。割付候補資源要素保持部３１の保持内容及び当該保持内容の推移を図１９（ｂ）に示す。本図において右端に付された(a)、(d)、(e)、(f)・・・は図１９（ａ）に示した(a)、(d)、(e)、(f)・・・に対応し、図２６に示すプログラム例内の(a)、(d)、(e)、(f)・・・に対応している。ここで割付可能資源要素とは割付対象ｘと生存区間が重なる割付対象に割り付けられていない資源要素である。
【０１１４】
図１９（ｂ）の(a),(d)の状況ではＤ０、Ｄ１、Ｄ２、Ｄ３、Ａ０、Ａ１、Ａ２、Ｍｍが、割付可能資源要素となっていることがわかる。更に(f)の状態から(f-1)の状態へと遷移すると、資源要素Ｄ１が、割付可能資源要素として除外されていることがわかる。
割付可能資源要素検出部３２はステップｂ３で起動され、割付可能資源要素を検出する。割付可能資源要素検出部３２によって求められた割付可能資源要素の集合は割付候補資源要素保持部３１に格納される。
【０１１５】
使用コスト計算部３４はステップｂ４で起動され、使用コストを算出することで割付候補資源要素保持部３１に保持されている各資源要素を割付対象ｘに割り付た場合に割付対象ｘの使用中間命令に対応する機械語命令がどれくらいのメモリサイズまたは実行時間数を費やするかを見積もり、各資源要素の選考を行う。また使用コスト計算部３４は見積もり結果として算出したコスト値を各資源要素毎に使用コスト保持部３５に保持させる。
【０１１６】
使用コスト保持部３５はステップｂ４で算出された使用コスト計算部３４の計算結果を保持する。
推定利得計算部３６は使用コスト計算部３４がメモリサイズまたは実行時間を見積もるのに対し、得失値を算出することで割付対象ｘに各資源要素を割り付けると、どれだけ転送命令が削除できるかを見積もり、各資源要素の選考を行う。
【０１１７】
利得保持部３７はステップｂ９において推定利得計算部３６によって算出された得失値の累計である利得値を保持する。利得保持部３７の保持内容の一例を図２１（ａ）に示す。本図において各記入欄には右端に「(d)」「(d-1)」「(d-2)」「(d-3)」「(d-4)」・・・・といった記号が付されているが、これは割付対象t265に対する推定利得計算部３６での各資源要素の利得値の保持内容の推移が示されている。
【０１１８】
資源要素決定制御部３８は割付資源決定の処理全体を制御する。
資源別コスト計算部３９はステップｂ１２において推定利得計算部３６によって算出された利得値が複数の資源について最大であった場合、後順コスト値の計算を行なう。
資源別コスト保持部４０は資源別コスト計算部３９の計算結果である後順コスト値を資源毎に保持する。
【０１１９】
評価資源保持部４１はステップｂ１２における資源別コスト計算部３９の計算によって有効であることが判明した資源を保持する。評価資源保持部４１の保持内容の一例を図２４（ｃ）に示す。本図において各記入欄には右端に「(d)」「(d-1)」といった記号が付されているが、これは割付対象t265に対する資源別コスト計算部３９での評価資源保持部４１の保持内容の推移が示されている。
【０１２０】
＜使用コスト計算部３４の構成図＞
図２に示した使用コスト計算部３４は各割付対象の使用コストを算出するように構成されている。図３に使用コスト計算部３４の構成を示す。
使用コスト計算部３４はパタン保持部４３と、演算コスト保持部４４と、総コスト保持部４６と、使用コスト計算制御部４７とで構成される。
【０１２１】
図７は使用コスト計算制御部４７のフローチャートである。
本フロ−チャ−トにおいて中間命令ｉは割付対象ｘが使用されている中間命令を表す。資源要素ｒは割付候補資源要素保持部３１に保持されている資源要素を表す。コストパタンｐは資源要素ｒを用いて中間命令ｉについて生成されたコストパタンを表す（尚、コストパタンについては後述する。）。
【０１２２】
本フロ−チャ−トは割付対象ｘの使用中間命令ｉの被演算子（オペランド）に資源要素ｒを用いた場合のコストパタンｐを生成するステップｃ５と、生成したコストパタンｐとマッチングするコストエントリを求めるステップｃ６と、求めたコストエントリを総コスト保持部４６に加算するステップｃ７とが割付対象ｘの全ての使用中間命令に対して繰り返されるループ構造になっており（ステップｃ４〜ｃ９）、このループ構造が更に割付可能な資源要素の全てについて繰り返される二重ループ構造になっている（ステップｃ２〜ｃ１０  尚、コストエントリについては後述する。）。
【０１２３】
以降、本フロ−チャ−トが有する各ステップを順を追って更に詳しく説明してゆく。
ステップｃ１では使用コスト保持部３５の保持領域のうち、割付候補資源要素保持部３１に保持されている資源要素に対応するものにはゼロを書き込み、そうでないものには「無効」を書き込む。
【０１２４】
ステップｃ２では割付候補資源要素保持部３１に保持されている資源要素ｒの全てについてステップｃ３からｃ１０を繰り返す。繰り返し終了後、使用コスト計算部３４を終了する。
ステップｃ３では総コスト保持部４６にゼロを保持させる。
ステップｃ４では入力として与えられた割付対象ｘを使用している中間命令を１つずつ取り出し、取り出した中間命令ｉについてステップｃ５からステップｃ９までの１連の処理を繰り返す。
【０１２５】
ステップｃ５では中間命令ｉにおいて割付対象ｘを使用している部分に資源要素ｒを当てはめて中間命令ｉに関するコストパタンｐを生成し、パタン保持部４３に保持させる。
ステップｃ６ではコストパタンｐと演算コスト保持部４４に保持されているコストエントリとのマッチングを行ない、マッチングするコストエントリｅ１を取り出す。
【０１２６】
ステップｃ７ではコストエントリｅ１のコストを取り出し、取り出したコストを総コスト保持部４６に加算する。
ステップｃ８ではコストエントリｅ１のWORKに資源要素が設定されているか否かを判定し、設定されているときステップｃ９を行ない、そうでないときステップｃ４を行なう。WORKとは、コード生成装置１４において機械語命令を生成する際に、中間命令iのオペランド及び演算結果に設定されている資源要素の他に、必要となる資源要素である。
【０１２７】
ステップｃ９では中間命令ｉを生存区間に含む割付対象に割付けている資源要素の集合Ｒ１を求め、コストエントリｅ１のWORKで指定されている資源要素ｒ１が集合Ｒ１に存在するときはスピルコストを総コスト保持部４６に加える。スピルコストとは資源要素ｒ１の格納値を一旦スタックに退避し、中間命令ｉの使用後に復帰させるために要するコストである。スピルコストの加算後、ステップｃ４を行なう（以下では資源要素ｒ１を中間命令ｉにおけるスピル資源要素と呼ぶことにする。）
ステップｃ１０では割付対象ｘに資源要素ｒを割り付けたときの使用コストを総コスト保持部４６に保持されている値として使用コスト保持部３５に格納し、ステップｃ２を行なう。
【０１２８】
パタン保持部４３はステップｃ５で生成されるコストパタンを保持する。コストパタンとは割付対象ｘを使用している中間命令を以下に示す４つの項目の組み合わせで表したものであり、使用コスト計算をより具体的にかつより精密に計算するために必要なものである。
(OP,  OPR1,  OPR2,  RESULT)
OP  ...  この項目には「乗算」「加算」「代入」といった、中間命令の演算子の種類が設定される。
【０１２９】
OPR1...  この項目は中間命令の第１オぺランド（OPが２項演算のときは左辺のオペランドに相当する。）と対応し、この第１オペランドがどう設定されているかが記述される。
第１オペランドが、即値に設定されていれば、即値を表す「IM」が設定される。また第１オペランドの割付対象が既に資源要素に割付けられていれば、当該資源要素が設定される。オペランドが即値でなくかつ資源要素も割付けられていないときは未割付けを表す「未」が設定される。またこの第１オぺランドの項目にはこの中間命令が終了点に相当するか否かを示す「K」か「N」の特性も付加される。
【０１３０】
OPR2...この項目には中間命令の第２オペランド（２項演算のときは右辺のオペランドが相当する。）に相当し、OPR1と同様な値が設定される。
RESULT...この項目には演算結果を保持させるための資源要素が、どの割付対象に割り付けられている資源要素と同一であるかを示す情報が設定される。
左辺に割付けられている資源要素とが同じときにはこのRESULTには「左同」、右辺と同じときに「右同」が設定され、左右辺と異なるときは「異」が設定される。また結果に資源要素が割付けられていないときは「未」が設定される。但し、代入演算及び比較演算のときはこの項は未設定である。
【０１３１】
（以下ではこの４つ組のパタンをコストパタンと呼ぶことにする。）
例えば、図２６のプログラムの一例における中間命令i3「t1=t34+3」において割付対象t34がD0に割付けられ、割付対象t1が未割付けであるとする。このとき演算の種類の項目が「加算」に設定される。また中間命令i3は割付対象t34の終了中間命令であり、割付対象t34は割付対象D0に割付けられているからOPR1は「D0.K」に設定される。第２オペランドは即値３であるからOPR2は「IM」に設定される。演算結果のt1が未割付けであるからRESULTの項目は「未」が設定される。
【０１３２】
そのため中間命令i3「t1=t34+3」のコストパタンは(加算,  D0.K,  IM,  未)となる。
演算コスト保持部４４は全てのコストパタンと、当該コストパタンに対応するコストとを欄とする演算コストテーブルを保持するものであり、使用コスト計算をより具体的にかつより精密に計算するために必要なものである。
【０１３３】
演算コストテーブルの一例を図２０（ａ）に示す。コストパタンは先に述べたOP,OPR1,OPR2,RESULTからなる４つの項目と、当該項目の組み合わせにおいてオペランドや結果に割付けられている資源要素以外に必要な資源要素を示すWORKと、当該組み合わせのコスト値を示すCOSTとからなる（以下ではコストのテーブルの要素をコストエントリと呼ぶことにする。）
例えば、図２０においてDn,Dmは資源ＤＲの資源要素のうち、D0〜D3の何れであってもマッチングすることを示す。またAn,Amは資源ＡＲの資源要素のうち、A0〜A2の何れかであってもマッチングすることを示す。IMは即値にマッチングすることを示す。Dn及びAnは「|」によって区切られているが、これは資源ＤＲあるいは資源ＡＲの何れの資源要素でもマッチングすることを示す。図２０（ａ）(a)のコストエントリのように「K」「N」の特性がないものはコストパタンに「K」「N」の特性が付いているか否かにかかわらずそれとマッチングすることを表す。前述の「t1=t34+3」のコストパタン(加算,D0.K,IM,未)は図２０（ａ）(b)のコストエントリにマッチングする。そのため当該コストパタンのコストは２となる。
【０１３４】
このようにマッチングされたコストは総コスト保持部４６において総和される。
使用コスト計算制御部４７は割付対象ｘを入力とし、割付対象ｘに割付候補資源要素保持部３１に保持されている各資源要素を割り付けたときの使用コストを算出するよう、図７に示したフロ−チャ−トに従って制御を行う。
【０１３５】
＜推定利得計算部３６の構成＞
推定利得計算部３６は利得値を算出することで転送命令の削減度合を見積もるよう構成されている。図４（ａ）は推定利得計算部３６の構成図である。
推定利得計算部３６は利得推定制御部５１と、追跡対象保持部５２と、処理済割付対象保持部５３と、既損失割付対象保持部５４と、重複割付対象保持部５５、得失保持部５６とで構成される。
【０１３６】
利得推定制御部５１は割付対象ｘについての利得値を計算するよう、処理制御を行う。
利得推定制御部５１の処理内容を図８及び図９のフローチャートに示す。図８は利得推定制御部５１の処理制御を示すメインフローであり、図９は得失計算処理のフローチャートである(このフローチャートによって表される得失値計算処理を得失計算ルーチンと呼ぶ。)。
【０１３７】
図８のフローチャートは割付対象ｘから資源継承関係を辿ってゆくための追跡対象を生成するステップｄ３と、追跡対象によって順々に資源継承関係を辿って行き、各資源要素の得失値を算出して資源要素の第１段階の再選考を行うステップｄ４と、第１段階の再選考の結果利得値が最大の資源要素が複数個である場合、割付対象ｘと生存区間が重なりかつ未割付けの割付対象の資源継承関係を辿って行き、各資源要素の得失値を算出して資源要素の第２段階の再選考を行うステップｄ１２〜ｄ１７とを有している。
【０１３８】
本フロ−チャ−トの第２段階の再選考の部分は割付対象ｙ（割付対象ｘと生存区間が重なる割付対象であって未割り付けである割付対象）に対して追跡対象を生成するステップｄ１５と、その追跡対象について得失値を算出するステップｄ１６と、算出された得失値に割付対象ｙの優先度を乗じた値を資源要素の利得値から減じるステップｄ１７とが全ての割付対象ｙについて繰り返されるループ構造（ステップｄ１２〜ｄ１７）になっている。
【０１３９】
以降、本フロ−チャ−トが有する各ステップを順を追って更に詳しく説明してゆく。
図８のステップｄ１では利得推定制御部５１は利得保持部３７および得失保持部５６の各資源要素に対応する内容をゼロにする。
ステップｄ２では追跡対象保持部５２、処理済割付対象保持部５３、既損失割付対象保持部５４を空にする。
【０１４０】
ステップｄ３では割付対象ｘに対して追跡対象A(x)を生成し、A(x)の各項目を
追跡対象A(x)の割付対象 ＝  A(x).ASO ＝  ｘ
追跡対象A(x)の生存区間長の和＝  A(x).LNS ＝  １
追跡対象A(x)の資源要素集合＝  A(x).RES ＝
割付候補資源要素保持部３１に保持されている資源要素の集合
に設定し、生成した追跡対象A(x)を追跡対象保持部５２に格納する。
【０１４１】
ステップｄ４では後述する得失計算ルーチンを呼び出し、得失計算を行ない、各資源要素毎の計算結果を得失保持部５６に保持させる。
ステップｄ５では各資源要素毎に得失保持部５６に格納されている値を利得保持部３７に格納する。
ステップｄ６では割付候補資源要素保持部３１に格納されている資源要素であり且つ利得保持部３７に格納されている値が最大の資源要素の集合ＲＳを求める。
【０１４２】
ステップｄ７では集合ＲＳの要素数が複数個であるときステップｄ８を行なう。そうでないときは推定利得計算部３６の処理を終了する。
ステップｄ８では割付対象ｘと生存区間が重なり且つ未割付けの割付対象が存在するときステップｄ９を行う。そうでないときは推定利得計算部３６の処理を終了する。
【０１４３】
ステップｄ９では割付候補資源要素保持部３１を一旦空にし、新たに集合ＲＳの資源要素を全て格納する。
ステップｄ１０では利得保持部３７の各資源要素に対応する内容をゼロにし、追跡対象保持部５２を空にする。
ステップｄ１１では割付対象ｘと生存区間が重なり且つ未割付けの割付対象のみを重複割付対象保持部５５に格納する。
【０１４４】
ステップｄ１２では重複割付対象保持部５５が空になるまでステップｄ１３〜ステップｄ１７までを繰り返す。空になったら推定利得計算部３６の処理を終了する。
ステップｄ１３では重複割付対象保持部５５から割付対象ｙを一つ取り出し、重複割付対象保持部５５から削除する。
【０１４５】
ステップｄ１４では 得失保持部５６の各資源要素に対応する内容をゼロにし、処理済割付対象保持部５３、既損失割付対象保持部５４を空にする。
ステップｄ１５では割付対象ｙに対して追跡対象B(y)を生成し、B(y)の各項目を追跡対象B(y)の割付対象 ＝  B(y).ASO ＝  ｙ
追跡対象B(y)の生存区間長の和＝  B(y).LNS ＝  １
追跡対象B(y)の資源要素集合＝  B(y).RES ＝
割付候補資源要素保持部３１に保持されている資源要素の集合
に設定し、生成した追跡対象B(y)を追跡対象保持部５２に格納する。
【０１４６】
ステップｄ１６では後述する得失計算ルーチンを呼び出し、得失計算を行ない、各資源要素毎の計算結果を得失保持部５６に算出する。
ステップｄ１７では各資源要素毎に得失保持部５６に格納されている値に割付対象ｙの割付優先度を乗じた値を利得保持部３７から減じてステップｄ１２へ戻る。
【０１４７】
以上のように利得推定制御部５１は割付対象ｘと資源継承関係にある割付対象から利得値を算出し(ステップｄ１〜ステップｄ５)、さらに算出した利得値が最大の資源要素が複数個あった場合、このうち、生存区間が重なる他の割付対象ｙに割り付けた方が転送命令が削減される可能性のある場合も考慮して最終的な利得値を算出している(ステップｄ９〜ステップｄ１７)
特に割付対象ｘと生存区間が重なる割付対象ｙに関して算出された得失値は割付対象ｙに割り付けるとどれだけ有利な資源要素であるかを示している。この度合が大きい資源要素ほど、割付対象ｘに割り付けると転送命令が増加する事を示す。さらに割付対象ｙの中でも、割付優先度が小さいものはレジスタ等の個数が限られている資源要素に割り付けられる可能性も小さいのでその効果を小さく見積もる必要がある。よってステップｄ１７において割付対象ｙに関して算出された得失値に割付対象ｙの割付優先度を乗じた値を利得保持部３７から減じている。
【０１４８】
＜得失計算ルーチンの詳細フロ−チャ−ト＞
得失計算ルーチンは図８のステップｄ４からもステップｄ１６からも呼び出されるサブルーチンであり、図８のフロ−チャ−トのステップｄ３及びステップｄ１５で追跡対象保持部５２に格納された全ての追跡対象に対して図９の処理を繰り返す。
【０１４９】
得失計算ルーチンには連続生存群（生存区間が連続し合う一連の割付対象の集合のことである。）において現在資源継承関係を辿っている箇所の割付対象A.ASOに資源要素が割付けられているかを判定するステップｅ３があり、このステップｅ３の判定結果に応じてステップｅ４が実行されるかステップｅ５〜ステップｅ１０が実行されるかが切り換る。
【０１５０】
ステップｅ４では割り付けられていると判定された場合割付済みの割付対象まで辿り着いたとしてその資源要素の得失値を算出して得失値分だけ資源要素の利得値を増加する。これに対しステップｅ３において割り付けられてない場合、ステップｅ５〜ステップｅ１０において割付対象A.ASOと生存区間が重なる側へと探索の域を広げる。具体的には割付対象A.ASOについての損失要因（利得値減少の要因となる割付対象）を算出するステップｅ５〜ｅ８と、損失要因となる割付対象に割り付けられている資源要素の得失値を算出してその資源要素の利得値を得失値だけ減少させるステップｅ９と、減少後、割付対象A.ASOと資源継承関係にある割付対象について追跡対象を新たに生成するステップｅ１０とを有し、追跡対象を保持する追跡対象保持部５２内から追跡対象が無くなるまでステップｅ２〜ｅ１０を繰り返し、資源継承関係にある連続的に割付対象を順に追ってゆくループ構造になっている。
【０１５１】
以降本フロ−チャ−トが有する各ステップを順を追って更に詳しく説明してゆく。
ステップｅ１では追跡対象保持部５２が空になるまでステップｅ２〜ステップｅ１０まで繰り返す。空になったら得失計算ルーチンの処理を終了する。
ステップｅ２では追跡対象保持部５２から追跡対象Aを一つ取り出し、追跡対象保持部５２から削除し、さらに追跡対象Aの割付対象項目である割付対象A.ASOを処理済割付対象保持部５３に格納する。
【０１５２】
ステップｅ３では割付対象A.ASOに資源要素rが割付けられているか判定し、割付けられているときはステップｅ４を行ない、そうでないときはステップｅ５を行なう。
ステップｅ４では資源要素rが追跡対象Aの資源要素集合の項目であるA.RESに属しているとき得失値  ＝  １ ／  追跡対象Aの生存区間長の和A.LNSを求め、この値を得失保持部５６の資源要素rの内容に加える。次にステップｅ１に戻る。
【０１５３】
ステップｅ５では割付対象A.ASOと生存区間が重なり、かつ資源要素に割り付けられている割付対象の集合ＯＳ１を求める。
ステップｅ６では集合ＯＳ１に属している割付対象に割付けられている資源要素の集合ＲＳ１を求める。
ステップｅ７では集合ＯＳ１に属しかつ、既損失割付対象保持部５４に格納されていない割付対象ｘの集合ＯＳ２を求め、集合ＯＳ２の要素を既損失割付対象保持部５４に格納する。
【０１５４】
ステップｅ８では集合ＯＳ２に属している割付対象に割付けられている資源要素の集合ＲＳ２を求める。
ステップｅ９では得失値  ＝  １ ／  追跡対象Aの生存区間長の和A.LNSを求め、得失保持部５６内の集合ＲＳ２に属する資源要素の内容から求めた得失値を減ずる。
【０１５５】
ステップｅ１０では割付対象A.ASOと資源継承関係にある割付対象であり、かつ処理済割付対象保持部５３に格納されていない割付対象ｙの全てに関して各々のｙ毎に追跡対象B(y)を生成し、B(y)の各項目を
追跡対象B(y)の割付対象 ＝  B(y).ASO ＝  ｙ
追跡対象B(y)の生存区間長の和＝  B(y).LNS ＝
生存区間長の和 A.LNS ＋  割付対象A.ASOの生存区間長
追跡対象B(y)の資源要素集合＝  B(y).RES ＝
資源要素集合 A.RES − 集合ＲＳ１   に設定し、
生成した追跡対象B(y)を追跡対象保持部５２に格納し、ステップｅ１０の実行後、ステップｅ１に戻る。
【０１５６】
以上のように得失計算ルーチンはステップｅ１０により資源継承関係にあるものを新たに追跡対象保持部５２に追加することによって資源継承関係を辿ることを可能としている。この設定によって追跡対象が増えるので得失値算出のための探索の範囲がまた広がることになる。
追跡対象保持部５２はステップｄ３、ｄ１５、ｅ１０において得失計算ルーチンの処理対象として生成された複数個の追跡対象を保持する。追跡対象保持部５２の保持内容の一例を図２１（ｃ）に示す。本図において各記入欄には「(d)」「(d-1)」「(d-2)」「(d-3)」「(d-4)」・・・・といった記号が付されているが、これは割付対象t265に対する推定利得計算部３６での追跡対象保持部５２の保持内容の推移を示している。これらの記号「(d)」「(d-1)」「(d-2)」「(d-3)」「(d-4)」・・・・が付された追跡対象の割付対象は割付対象t265の得失値を計算する際に資源継承関係が辿られる割付対象を示している。これらの資源継承関係が辿られる割付対象が、割付対象t265の生存区間とどのような位置関係にあるかは図２７に示す通りである。本図では得失値計算の対象となる割付対象t265を黒で塗り潰された縦線で示し、その得失値計算を行う際、資源継承関係が辿られてゆく割付対象を白抜きの縦線で示す。
【０１５７】
図２１（ｃ）の記入欄のうち、右端に「(d-1)」と付されたものは割付対象t265を構造体のメンバーとした追跡対象が生成されたことを示している。同様に右端に「(d-4)」と付されたものは割付対象t265の生存区間と重なる生存区間を有する割付対象p1を構造体のメンバーとした追跡対象が生成されたことを示している。同様に右端に「(d-6)」と付されたものは割付対象t265の生存区間と重なる生存区間を有する割付対象a3を構造体のメンバーとした追跡対象が生成されたことを示している。
【０１５８】
また右端に「(d-8)」と付されたものは割付対象t265の生存区間と重なる生存区間を有する割付対象a3と資源継承関係にある割付対象t263、t264、x2、x3を構造体のメンバーとした追跡対象が生成されたことを示している。
図２１（ｃ）における「(d-4)」では生存区間が重なり合う割付対象p1が割付対象t265についての追跡対象として選択されている。図２１（ｃ）における「(d-6)」では生存区間が重なり合う割付対象a3が割付対象t265についての追跡対象として選択されている。図２１（ｃ）における「(d-8)」では割付対象a3と資源継承関係になる割付対象t263,t264,x2,x3が割付対象t265についての追跡対象として選択されている。
【０１５９】
このように図２１（ｃ）を参照すれば割付対象t265の得失値を算出するために割付対象p1,a3,t263,t264,x2,x3まで探索の域が広がっていることがわかる。
処理済割付対象保持部５３はステップｅ２において得失計算ルーチンの処理を完了することになる追跡対象の割付対象を保持する。特に処理済割付対象保持部５３の役割は資源継承関係が直接または間接的に循環している場合、得失計算ルーチンの処理が無限に繰り返すことを防ぐためである。
【０１６０】
処理済割付対象保持部５３の保持内容の一例を図２２（ａ）に示す。本図において各記入欄には「(d)」「(d-1)」「(d-2)」「(d-3)」「(d-4)」・・・・といった記号が付されているが、これは割付対象t265に対する推定利得計算部３６での処理済割付対象保持部５３の保持内容の推移を示している。本図の記入欄のうち、右端に「(d-1)」と付されたものは割付対象t265が、処理済みの割付対象になったことを示している。これが「(d-1)」「(d-2)」「(d-3)」「(d-4)」・・・・というように下欄に進むにつれ、割付対象t265の生存区間と重なる生存区間を有する割付対象p1、割付対象t265の生存区間と重なる生存区間を有する割付対象a3及び割付対象a3と資源継承関係にある割付対象t263、t264、x2、x3をメンバーとした追跡対象が処理済み割付対象保持部５３に追加されてゆくことがわかる。
【０１６１】
既損失割付対象保持部５４は得失計算ルーチンの過程で同じ割付対象に対して得失値を減ずる処理を２回以上行わないようにするため、ステップｅ７において損失要因として一度選択された割付対象を保持する。このように既損失割付対象保持部５４が設られているのは損失要因の極端な見積りを避けるためである。例えば図１４における割付対象xを保持する追跡対象をまずステップｄ３において追跡対象保持部５２に格納したとする。その後に得失計算ルーチンが呼び出され、ステップｅ１０で割付対象x3,x4, x5 を保持する追跡対象が追跡対象保持部５２に格納されたとする。このときステップｅ７、ｅ８がなく、ステップｅ９において集合ＲＳ２の代わりに集合ＲＳ１を用いるとすると、割付対象x4,x5を保持する追跡対象がステップｅ９で処理されると、き、割付対象x4, x5と生存区間が重なる割付対象x11の割付けられている資源要素D0の得失値が２回減じられる。さらにその後、割付対象x6を保持する追跡対象がステップｅ９で処理されると、きも同様に割付対象x11に割付けられている資源要素D0の得失値が減じられ、資源要素D0の得失値が極端に小さく算出されてしまう可能性がある。このことを防ぐためにステップｅ７において既損失割付対象保持部５４に未格納の割付対象のみを得失値計算の対象としている。
【０１６２】
既損失割付対象保持部５４の保持内容の一例を図２２（ｂ）に示す。本図において各記入欄には「(d)」「(d-1)」「(d-2)」「(d-3)」「(d-4)」・・・・といった記号が付されているが、これは割付対象t265に対する推定利得計算部３６での既損失割付対象保持部５４の保持内容の推移を示している。本図の記入欄のうち、右端に「(d)」「(d-1)」「(d-2)」と付されたものは割付対象t265に対する推定利得計算の初期段階で既に損失要因となった割付対象を示している。これが、「(d-3)」の欄で割付対象t265の生存区間と重なる生存区間を有する割付対象p1に対して得失計算ルーチンが呼ばれ、割付対象p1と生存区間が重なる割付対象Ar11、Fr1、Ar12等が既損失割付対象保持部５４に追加されてゆくことがわかる。
【０１６３】
重複割付対象保持部５５は割付対象ｘと生存区間が重なりかつ、未だ資源要素を割付けていない割付対象を保持する。重複割付対象保持部５５の保持内容の一例を図２２（ｃ）に示す。本図において各記入欄には右端に「(d)」「(d-1)」「(d-2)」といった記号が付されているが、これは割付対象t265に対する推定利得計算部３６での重複割付対象保持部５５の保持内容の推移を示している。特に右端に「(d)」と付されたものは割付対象t265の生存区間と重なる生存区間を有する割付対象p1、割付対象a3が重複割付対象保持部５５に格納されたことを示す。
【０１６４】
得失保持部５６はステップｄ４、ｄ１６において得失計算ルーチンの実行によって算出された得失値を各資源要素毎に保持する。得失保持部５６の保持内容の一例を図２１（ｂ）に示す。本図において各記入欄には右端に「(d)」「(d-1)」「(d-2)」「(d-3)」「(d-4)」・・・・といった記号が付されているが、割付対象t265に対する推定利得計算部３６での得失保持部５６の保持内容の推移を示している。
【０１６５】
＜資源別コスト計算部３９の構成＞
図４（ｂ）に示した資源別コスト計算部３９は割り付けられる順序が後の割付対象がより適切な資源要素に割り付けられるように構成されている。
資源別コスト計算部３９は資源別コスト計算制御部５０１と、コストパタン保持部５０２と、資源演算コスト保持部５０３と、追跡対象保持部５０４と、資源別総コスト保持部５０５と、処理済割付対象保持部５０６と、重複割付対象保持部５０７とで構成される。
【０１６６】
資源別コスト計算制御部５０１は割付対象ｘについての資源別の使用コストを計算するよう、処理制御を行う。
資源別コスト計算制御部５０１の処理内容を図１０及び図１１のフローチャートに示す。図１０は資源別コスト計算制御部の処理制御を示すメインフローであり、図１１は後順コスト値計算処理のフローチャートである(このフローチャートによって表される後順コスト値計算処理を後順コスト値計算ルーチンと呼ぶ。)。
【０１６７】
図１０のフローチャートは割付対象ｘから資源継承関係を辿ってゆくための追跡対象を生成するステップｆ３と、追跡対象によって順々に資源継承関係を辿って行き各資源の後順コスト値を算出して資源の第１段階の再々選考を行うステップｆ４と、第１段階の再々選考の結果後順コスト値が最小の資源が複数個である場合、割付対象ｘと生存区間が重なり且つ未割付けの割付対象の資源継承関係を辿って行き、各資源の後順コスト値を算出して資源要素の第２段階の再々選考を行うステップｆ１５とを有している。
【０１６８】
本フロ−チャ−トの第２段階の再々選考の部分は割付対象ｙ（割付対象ｘと生存区間が重なる割付対象であって未割り付けである割付対象）に対して追跡対象を生成するステップｆ１４と、その追跡対象について後順コスト値を算出するステップｆ１５と、算出された後順コスト値に割付対象ｙの優先度を乗じた値を資源の後順コスト値から減じるステップｆ１６とが、全ての割付対象ｙについて繰り返されるループ構造（ステップｆ１１〜ｆ１６）になっている。
【０１６９】
以降、本フロ−チャ−トが有する各ステップを順を追って更に詳しく説明してゆく。
ステップｆ１では資源別コスト保持部４０および資源別総コスト保持部５０５の各資源に対応する内容をゼロにする。
ステップｆ２では追跡対象保持部５０４、処理済割付対象保持部５０６を空にする。
【０１７０】
ステップｆ３では割付対象ｘに対して追跡対象rA(x)を生成し、rA(x)の各項目を
追跡対象rA(x)の割付対象 ＝  rA(x).ASO ＝  ｘ
追跡対象rA(x)の生存区間長の和＝  rA(x).LNS ＝  １に設定し、
生成した追跡対象rA(x)を追跡対象保持部５０４に格納する。
【０１７１】
ステップｆ４では後述する後順コスト値計算ルーチンを呼び出し、コスト計算を行ない、各資源毎の計算結果を資源別総コスト保持部５０５に算出する。
ステップｆ５では各資源毎に資源別総コスト保持部５０５に格納されている値を資源別コスト保持部４０に格納する。
ステップｆ６では資源別コスト保持部４０に格納されている値が最小である資源の集合Ｒを求め、評価資源保持部４１を一旦空にし、集合Ｒに属する資源を格納する。
【０１７２】
ステップｆ７では集合Ｒの要素数が複数個であるときステップｆ８を行なう。そうでないときは資源別コスト計算部３９の処理を終了する。
ステップｆ８では割付対象ｘと生存区間が重なり且つ未割付けの割付対象が存在するときステップｆ９を行う。そうでないときは資源別コスト計算部３９の処理を終了する、
ステップｆ９では資源別コスト保持部４０の各資源に対応する内容をゼロにし、追跡対象保持部５０４を空にする。
【０１７３】
ステップｆ１０では割付対象ｘと生存区間が重なり且つ未割付けの割付対象のみを重複割付対象保持部５０７に格納する。
ステップｆ１１では重複割付対象保持部５０７が空になるまでステップｆ１２〜ステップｆ１６までを繰り返す。空になったら資源別コスト計算部３９の処理を終了する。
【０１７４】
ステップｆ１２では重複割付対象保持部５０７から割付対象ｙを一つ取り出し、重複割付対象保持部５０７から削除する。
ステップｆ１３では 資源別総コスト保持部５０５の各資源に対応する内容をゼロにし、処理済割付対象保持部５０６を空にする。
ステップｆ１４では割付対象ｙに対して追跡対象rB(y)を生成し、rB(y)の各項目を
追跡対象rB(y)の割付対象 ＝  rB(y).ASO ＝  ｙ
追跡対象rB(y)の生存区間長の和＝  rB(y).LNS ＝  １に設定し、生成した追跡対象rB(y)を追跡対象保持部５０４に格納する。
【０１７５】
ステップｆ１５では後述する後順コスト値計算ルーチンを呼び出し、コスト計算を行ない、各資源毎の計算結果を資源別総コスト保持部５０５に算出する。
ステップｆ１６では評価資源保持部４１に格納されている各資源に対して資源別総コスト保持部５０５に格納されている値に割付対象ｙの割付優先度を乗じた値を資源別コスト保持部４０から減じ、ステップｆ１１へ戻る。
【０１７６】
以上のように資源別コスト計算制御部５０１は割付対象ｘと資源継承関係にある割付対象から後順コストを算出し(ステップｆ１〜ステップｆ５)、さらに算出したコストが最小の資源が複数個あった場合、このうち、生存区間が重なる他の割付対象ｙに関する後順コスト計算を行なうことにより割付対象ｙをも考慮した割付対象ｘに対する後順コストの算出を行っている(ステップｆ９〜ステップｆ１６)
特にステップｆ１５おいて求められる後順コストの大きい資源は割付対象ｘと生存区間が重なる割付対象ｙにとって後順コストがかかる資源であり、割付対象ｘに当該資源を含めて他に割付け可能な資源が存在するときは当該資源を割付対象ｘに割付ければ、割付対象ｙには後順コストのかからない資源を割り付けれる可能性が増す。よってステップｆ１６では求めた後順コストを資源別コスト保持部４０から減じている。またステップｆ１６において求めた後順コストに割付対象ｙの優先度を乗じているのは割付対象ｙの中でも割付優先度が小さいものはレジスタ等の個数の限定された資源に割り付けられる可能性も小さいのでその効果を小さく見積もるためである。
【０１７７】
＜後順コスト値計算ルーチンの詳細フローチャート＞
図１１は後順コスト値計算ルーチンのフローチャートである。後順コスト値計算ルーチンは割付対象rA.ASO中の使用中間命令についてコストパタンを生成するステップｇ５と、コストエントリとのマッチングをとり、コストエントリｅ１を取りだすステップｇ６と、当該コストエントリｅ１のコストｃと、追跡対象rAの生存区間長の和であるrA.LNS とから後順コスト値  ＝ コストｃ / rA.LNS を算出するステップｇ７と、算出した後順コスト値を資源ｒの後順コスト値に加えるステップｇ８とが割付対象rA.ASOに含まれる全ての使用中間命令に対して繰り返されるループ構造（ステップｇ４〜ｇ８）になっており、
このループ構造が更に資源要素が再々選考に残った資源について繰り返される二重ループ構造（ステップｇ３）になっている。
【０１７８】
またこの二重ループ構造が更に追跡対象保持部５０４から追跡対象rAが取り出される度に起動され、また追跡対象保持部５０４には二重ループ構造が１度実行される度に現在資源継承関係を辿っている箇所の割付対象rA.ASOと資源継承関係にある割付対象が新たに格納される構造になっている（ステップｇ９）。そのため当該二重ループ構造は連続的に資源継承関係にある未割り付けの割付対象が処理されるまで繰り返される三重ループ構造になっている（ステップｇ１）。
【０１７９】
以降、本フロ−チャ−トが有する各ステップを順を追って更に詳しく説明してゆく。
ステップｇ１では追跡対象保持部５０４が空になるまでステップｇ２〜ステップｇ９まで繰り返す。空になったら後順コスト値計算ルーチンの処理を終了する。
【０１８０】
ステップｇ２では追跡対象保持部５０４から追跡対象rAを一つ取り出し、追跡対象保持部５０４から削除する。さらに追跡対象rAの割付対象項目である割付対象rA.ASOを処理済割付対象保持部５０６に格納する。
ステップｇ３では評価資源保持部４１に保持されている資源であり、追跡対象rAの割付対象項目である割付対象rA.ASOに割付け可能な資源rの一つ一つについてステップｇ４〜ステップｇ８の一連の処理を繰り返す。繰り返し処理を終了したらステップｇ９を行なう。ここで割付対象rA.ASOに割付け可能な資源とは割付対象rA.ASOと生存区間が重なる割付対象に割付けられていない資源要素が属する資源のことである。つまり割付対象rA.ASOと生存区間が重なる割付対象にある資源が有する資源要素の全てが割付けられているとき当該資源は割付け不可能となる。
【０１８１】
ステップｇ４では割付対象rA.ASOを使用している中間命令を１つずつ取りだし、取り出した中間命令ｉについてステップｇ５〜ステップｇ８の一連の処理を繰り返す。繰り返し処理を終了したらステップｇ３に戻る。
ステップｇ５では中間命令ｉにおいて割付対象rA.ASOを使用している部分に資源rを割り付けて中間命令ｉに関するコストパタンpを生成し、コストパタン保持部５０２に保持させる。
【０１８２】
ステップｇ６ではコストパタン保持部５０２に格納されているコストパタンpと資源演算コスト保持部５０３に保持されているコストエントリとのマッチングを行ない、マッチングするコストエントリｅ１を取り出す。
ステップｇ７ではコストエントリｅ１のコストｃを取りだし、当該コストｃと、追跡対象rAの生存区間長の和であるrA.LNS とから後順コスト値  ＝ コストｃ / rA.LNS を算出する。
【０１８３】
ステップｇ８ではステップｇ７で求めた後順コスト値を資源別総コスト保持部５０５の資源rの内容に加える。次にステップｇ４に戻る。
ステップｇ９では割付対象rA.ASOと資源継承関係にある未割付けの割付対象であり、かつ処理済割付対象保持部５０６に格納されていない割付対象ｙの全てに関して各々の割付対象ｙ毎に追跡対象rB(y)を生成し、
rB(y)の各項目を
追跡対象rB(y)の割付対象 ＝  rB(y).ASO ＝  ｙ
追跡対象rB(y)の生存区間長の和＝  rB(y).LNS ＝
生存区間長の和 rA.LNS ＋  割付対象rA.ASOの生存区間長
に設定し、生成した追跡対象rB(y)を追跡対象保持部５０４に格納してステップｇ１へ戻る。
【０１８４】
コストパタン保持部５０２は後順コスト値の計算のために図１１のステップｇ５で生成されたコストパタンを保持している。このコストパタンはパタン保持部４３が保持したものと同一の項目で構成されているので説明は省略する。コストパタン保持部５０２の保持内容の一例を図２４（ｂ）に示す。本図において各記入欄には右端に「(d)」といった記号が付されているが、これは割付対象t265に対する資源別コスト計算部３９でのコストパタン保持部５０２の推移を示すものである。
【０１８５】
資源演算コスト保持部５０３は全てのコストパタンと、当該コストパタンに対応するコストとを欄とする演算コストテーブルを後順コスト値計算用に保持している。
資源演算コスト保持部５０３が保持する演算コストテーブルは図２０（ａ）のうち、OP, OPR1, OPR2, RESULTからなる４つの項目と、当該項目の組み合わせのコスト値を示すCOSTからなる。
【０１８６】
追跡対象保持部５０４は後順コスト値計算ルーチンの処理対象となる複数個の追跡対象を保持する。追跡対象保持部５０４に保持される追跡対象は推定利得計算部３６で使用する追跡対象保持部５２によって保持される追跡対象と異なり、割付可能な資源要素の集合がメンバから省かれている。そのため追跡対象保持部５０４に保持される追跡対象は割付対象と生存区間長の和の２項目のデータで構成されている。本実施形態では追跡対象保持部５２で保持される追跡対象と区別するため、追跡対象において現在資源継承関係を辿っている箇所の割付対象をASO、そこまでの生存区間長の和をLNSで表現し、これらを参照する場合は割付対象rA.ASO、生存区間長の和rA.LNSというように先頭に「r」を付けて表している。
【０１８７】
資源別総コスト保持部５０５は後順コスト値計算ルーチンで算出されるコストを保持する。
処理済割付対象保持部５０６は推定利得計算部３６の処理済割付対象保持部５３同様、後順コスト値計算ルーチンの処理を完了した割付対象を保持する。処理済割付対象保持部５３同様、処理済割付対象保持部５０６の役割も、資源継承関係が直接または間接的に循環している場合、後順コスト値計算ルーチンの処理が無限に繰り返すことを防ぐために備えられている。処理済割付対象保持部５０６の保持内容の一例を図２４（ａ）に示す。本図において各記入欄には右端に「(d)」「(d-1)」「(d-2)」「(d-3)」「(d-4)」・・・・といった記号が付されているが、これは割付対象t265に対する資源別コスト計算部３９での処理済割付対象保持部５０６の推移を示すものである。本図の記入欄のうち、右端に「(d-1)」と付されたものは割付対象t265に対する資源別コスト計算部３９での処理済みの初期の時点での割付対象を示している。これが、「(d-1)」「(d-2)」「(d-3)」「(d-4)」・・・・というように下欄に進むにつれ、割付対象t265の生存区間と重なる生存区間を有する割付対象a3及び割付対象a3と資源継承関係にある割付対象x2、x3をメンバーとした追跡対象が処理済割付対象保持部５０６に追加されてゆくことがわかる。
【０１８８】
重複割付対象保持部５０７は割付対象ｘと生存区間が重なりかつ、未だ資源要素を割付けていない割付対象を保持する。重複割付対象保持部５０７の保持内容の一例を図２４（ｄ）に示す。本図において各記入欄には右端に「(d)」「(d-1)」「(d-2)」・・・・といった記号が付されているが、これは割付対象t265に対する資源別コスト計算部３９での重複割付対象保持部５０７の推移を示す。右端に「(d)」と付されたものは割付対象t265の生存区間と重なる生存区間を有する割付対象p1、割付対象a3が重複割付対象保持部５０７に格納されたことを示す。
【０１８９】
以上のように構成される本実施形態の資源割付装置における具体的な処理内容をこれまでに示したフローチャートを再度参照しながら説明する。
まず前提としてここで扱う資源をアドレスレジスタ(AR)、データレジスタ(DR)、多資源をメモリ(Mm)とする。また資源ARの資源要素をA0,A1,A2とし、資源DRの資源要素をD0,D1,D2,D3とし、また多資源Mmも資源要素とする。
【０１９０】
また資源別の機能制限として資源ARはメモリの間接参照機能を持つが、資源DRは持たないとする。さらに資源DRは乗除算演算の被演算子となりうるが、資源ARはならないとする。更に関数の引数渡しに使用する引数レジスタ、および関数呼び出しにおいて破壊レジスタをD0,D1,A0とし、関数の戻り値に使用する戻り値レジスタをD0,A0とし、戻り値のデータ型によってD0,A0の使用区別を行なうものとする。
【０１９１】
図２５のＣ言語記述のプログラムに対して既に構文解析装置１１および最適化装置１２によって図２６(1)のような３番地形式の中間プログラムが出力されている。さらに最適化装置１２によって中間プログラムから基本ブロックが抽出され、制御フロー情報、およびデータフロー情報が得られている。図２６(1)では特に矢印↑は間接参照演算を表しており、図中の変数Ar1,Ar2,  Frはそれぞれ関数の実引数および関数の戻り値を保持させる変数を表している。
【０１９２】
この状態で資源割付装置１３に処理が移る。資源割付制御部２７は割付対象生成部２２を起動する。割付対象生成部２２は制御フロー情報、およびデータフロー情報から変数に対する割付対象を生成する（ステップａ１）。その結果図１７のｎ１０からｎ１５までの情報が得られる。図１７は以下で行う割り付け処理により資源要素が割付けられるものを表し、図１８は実引数(Ar)、関数の戻り値(Fr)、破壊レジスタ(Br)を表す割付対象を示している。さらに図２６(2)は生存区間を実線で示したものである。図２６(2)および図１７において変数t26のように生存区間が複数存在する変数はそれぞれ別々に割付対象になるのでt261,  t262のように区別される。
【０１９３】
図１７に示された割付対象の情報は図１中の割付対象保持部２１に保持される。
次に資源割付制御部２７は生存区間重複割付対象検出部２３を起動する。生存区間重複割付対象検出部２３は割付対象保持部２１に保持されている各々の割付対象に関して生存区間が重なる割付け対象を求める（ステップａ２）。その結果図１７のｎ１６の情報が得られる。
【０１９４】
次に資源割付制御部２７は資源継承割付対象検出部２４を起動する。資源継承割付対象検出部２４は割付対象保持部２１に保持されている各々の割付対象に関して資源継承関係にある割付対象を求める（ステップａ３）。その結果図１７のｎ１７の情報が得られる。
次に資源割付制御部２７は割付優先度計算部２５を起動する。割付優先度計算部２５は各割付対象に関して次の式により割付優先度を計算する（ステップａ４）。
【０１９５】
割付優先度＝使用率
＝使用中間命令が存在するループレベルの総和／生存区間の長さ
次に資源割付制御部２７は割付資源要素決定部２６を起動する。割付資源要素決定部２６は割付優先度の高い割付対象から順に資源要素を割付対象に割付ける（ステップａ５）。
【０１９６】
ここで割付資源要素決定部２６の処理を図６に示す資源要素決定制御部３８のフローチャートを参照しながら説明する。
＜(a)割付対象t262を対象とした処理内容＞
先ず、資源要素決定制御部３８は未割付けの割付対象が存在するか否か判定し、未割付けの割付対象のうち、割付優先度が最大の割付対象t262を取り出す（ステップｂ１、ｂ２）。
【０１９７】
次に資源要素決定制御部３８は割付可能資源要素検出部３２を起動する（ステップｂ３）。割付可能資源要素検出部３２は生存区間が重なる割付対象に割付けられていない資源要素である、D0,D1,D2,D3,A0,A1,A2と多資源要素のMmを割付候補資源要素保持部３１に保持させる（図１９（ｂ）の(a)）。次に資源要素決定制御部３８は使用コスト計算部３４を起動する（ステップｂ４）。
【０１９８】
使用コスト計算部３４は割付対象t262の使用箇所において割付候補資源要素保持部３１に保持されている資源要素を使用したときの使用コストを各資源要素毎に求める。
＜(a-1)割付対象t262の使用中間命令i10と、資源要素D0とを対象にした処理内容＞
ここでさらに使用コスト計算部３４の処理内容を図７に示す使用コスト計算制御部４７のフローチャートを参照しながら説明する。
【０１９９】
次に使用コスト計算制御部４７は使用コスト保持部３５の各資源要素の内容にゼロを保持させる（ステップｃ１）。
次に使用コスト計算制御部４７は割付候補資源要素保持部３１に格納されており、未だ使用コストを算出していない資源要素D0を取り出す（ステップｃ２）。
次に使用コスト計算制御部４７は総コスト保持部４６にゼロを保持させる（ステップｃ３）。
【０２００】
次に使用コスト計算制御部４７は割付対象t262の使用中間命令のうち、D0について未だ使用コストの計算を行なってい中間命令i10を取り出す（ステップｃ４）。
次に使用コスト計算制御部４７は使用中間命令i10に対して  コストパタン(代入,D0.N,D0.K,-)を生成し、パタン保持部４３に保持させる（ステップｃ５）。
【０２０１】
次に使用コスト計算制御部４７は演算コスト保持部４４に保持されている図２０（ａ）の演算コストテーブルと、パタン保持部４３に保持されているコストパタンとのマッチングをとる。このとき図２０（ａ）の(c)のコストエントリとマッチングが成立し、コスト0を得、得られたコストを総コスト保持部４６に保持されている値に加える（ステップｃ６、ｃ７）。
【０２０２】
次に使用コスト計算制御部４７はマッチングしたコストエントリのWORK項目が未設定であると判定してステップｃ４を行なう。
＜(a-2)t262の中間命令i11と、資源要素D0とを対象にした処理内容＞
次に使用コスト計算制御部４７は割付対象t262のD0について未だ使用コストを計算していない中間命令i11を取り出し、コストパタン(加算,D0.K,IM,未)を生成しパタン保持部４３に保持させる。図２０（ａ）の演算コストテーブルの(b)のコストエントリとマッチングを成立させてコスト2を得て総コスト保持部４６に加える。次にマッチングしたコストエントリのWORK項目が未設定であると判定してステップｃ４を行なう（ステップｃ４からｃ８）。
【０２０３】
次に使用コスト計算制御部４７は資源要素D0について未だ使用コストを計算していない割付対象t262の中間命令が存在しないことを検出し、総コスト保持部４６に保持されている値をt262にD0を割付けたときの使用コストととして使用コスト保持部３５のD0の内容に保持させる（ステップｃ４、ｃ１０）。
＜(a-3)t262の中間命令i10、i11と、資源要素D1とを対象にした処理内容＞
次に使用コスト計算制御部４７は割付候補資源要素保持部３１にから未だ使用コストを算出していない資源要素D1を取り出し、資源要素D0のときと同様に割付対象t262の中間命令i10,i11に対してそれぞれ、コストパタン(代入,D1.N,D0.K,-)(加算,D1.K,Im,未)を生成し、演算コストテーブルとマッチングをとり、それぞれ図２０（ａ）の(d),(b)のコストエントリとマッチングしてそれぞれコスト1,2を得る。そしてその和3を総コスト保持部４６に得て使用コスト保持部３５のD1の欄に保持させる（ステップｃ２からｃ８）。
【０２０４】
次に使用コスト計算制御部４７は資源要素D2,D3,A0,A1,A2  に関しても、資源要素D1と同様に計算を行い、使用コストの結果を得る。
次に使用コスト計算制御部４７は割付候補資源要素保持部３１にから未だ使用コストを算出していない資源要素Mmを取り出し、割付対象t262の中間命令i10,i11に対してそれぞれ、コストパタン(代入,Mm.N,D0.K,-)(加算,Mm.K,Im,未)を生成し、演算コストテーブルとマッチングをとり、それぞれの図２０（ａ）の(e),(f)のコストエントリとマッチングしてそれぞれコスト  2,  3  を得る。そしてその和  5  を総コスト保持部４６に得て使用コスト保持部３５のMmの欄に保持させる（ステップｃ２からｃ７）。また図２０（ａ）(f)のコストエントリのWORK項目が指定されているが、中間命令i11におけるスピル資源要素が存在しないのでスピルコストを総コスト保持部４６には算入しない（ステップｃ８、ｃ９）。
【０２０５】
次に使用コスト計算制御部４７は割付候補資源要素保持部３１に格納されており、未だ使用コストを求めていない資源要素が存在しないことを判定し（ステップｃ２）、使用コスト計算部３４の処理を終え、ステップｂ４へ戻る。尚、この時点での使用コスト保持部３５の内容は図２０（ｂ）の(a)のように得られる。
資源要素決定制御部３８は使用コスト保持部３５を参照して多資源であるMmのコストが最小でないとことを判定して（ステップｂ５）、ステップｂ６を行なう。
【０２０６】
次に資源要素決定制御部３８は使用コスト保持部３５を参照して使用コストが最小である資源要素D0が存在することを判定し、資源要素D0を割付対象t262に割付ける（ステップｂ６、ｂ１６、図１９（ａ）の(a)、図２０（ｂ）の(a)）。
＜(b)(c)割付対象t263、t264を対象とした処理内容＞
次に資源要素決定制御部３８はステップｂ１に戻り、未割付けの割付対象  t263,  t264についても割付対象t262と同様に割付け処理を行ない、図１９（ａ）の(b)(c)のようにD0を割り付ける。
＜(d)割付対象t265を対象とした処理内容＞
次に資源要素決定制御部３８は未割り付けで優先度が高いt265を取り出す（ステップｂ１、ｂ２）。
【０２０７】
次に資源要素決定制御部３８は割付可能資源要素検出部３２を起動し、割付可能な資源要素、D0,D1,D2,D3,A0,A1,A2,Mmを得て割付候補資源要素保持部３１に保持させる（ステップｂ３、図１９（ｂ）の(d)）。
次に資源要素決定制御部３８は使用コスト計算部３４を起動し、割付候補資源要素保持部３１の各資源要素に関して図２０（ｂ）(d)のように使用コストを計算する（ステップｂ４）。
【０２０８】
次に資源要素決定制御部３８は多資源であるメモリが最小の使用コストとなっているかを判定するが、そうでないのでステップｂ６を行う（ステップｂ５）。
次に資源要素決定制御部３８は使用コストが最小である資源要素が唯一つかどうかを判定するが、そうでないのでステップｂ７を行う（ステップｂ６）。
次に資源要素決定制御部３８は使用コストが最小でない資源要素を割付候補資源要素保持部３１の割付候補集合から削除する（ステップｂ７、図１９（ｂ）の(d-1)）。
【０２０９】
次に資源要素決定制御部３８はt265を入力として推定利得計算部３６を起動し、割付候補資源要素保持部３１に保持されている各資源要素に関して利得計算を行う(ステップｂ８)。
＜割付対象t265に関するステップｄ１以降の処理＞
ここでさらにt265に関して推定利得計算部３６の処理内容を図８、図９に示す利得推定制御部５１のフローチャートを参照しながら説明する。
【０２１０】
まず利得推定制御部５１は利得保持部３７および得失保持部５６の各資源要素に対応する内容をゼロにする(ステップｄ１、図２１（ａ）の(d)、図２１（ｂ）の(d))。
次に利得推定制御部５１は追跡対象保持部５２、処理済割付対象保持部５３、既損失割付対象保持部５４を空にする(ステップｄ２、図２１（ｃ）の(d)、図２２（ａ）の(d)、図２２（ｂ）の(d))。
【０２１１】
次に利得推定制御部５１は割付対象t265に対して追跡対象A1を生成し、A1の各項目を図１７からA1.ASO = t265 A1.LNS = 1 A1.RES = D0, D1, D2, D3, A0, A1, A2に設定する。 次に図２１（ｃ）の(d-1)のようにA1を追跡対象保持部５２に格納する(ステップｄ３)  図２１（ｃ）の(d-1)では追跡対象を(A1, t265, 1, (D0,D1,D2,D3,A0,A1,A2))で表現し、各項目は(追跡対象名、割付対象、生存区間長の和、資源要素集合)を示す。
【０２１２】
次に利得推定制御部５１は得失計算ルーチンを呼び出す。
＜追跡対象A1の処理＞
ここでさらに割付対象t265に関する利得推定制御部５１の処理内容を図９に示すフローチャートを参照しながら説明する。
まず、ステップｅ１、ステップｅ２では追跡対象A1を追跡対象保持部５２から取り出し、追跡対象保持部５２から削除する。さらに追跡対象A1の割付対象項目である割付対象t265を処理済割付対象保持部５３に格納する(図２１（ｃ）の(d-2)、図２２（ａ）の(d-1))。
【０２１３】
次にステップｅ３では追跡対象A1の割付対象項目である割付対象t265は資源要素に割り付けられていないのでステップｅ５に進む。
次にステップｅ５〜ステップｅ９では集合ＯＳ１が空であるので集合ＲＳ１、集合ＯＳ２、集合ＲＳ２が空となり得失値は計算されない(図２２（ｂ）の(d-1))。
【０２１４】
次にステップｅ１０では追跡対象A1の割付対象項目である割付対象t265と資源継承関係にある割付対象が存在しないので新しい追跡対象は生成されない。次にステップｅ１へ戻る。
次にステップｅ１において追跡対象保持部５２が(図２１（ｃ）の(d-2))のように空なので得失計算ルーチンの処理を終了し、ステップｄ４に戻る。
【０２１５】
＜割付対象t265に関するステップｄ５以降の処理＞
ここでさらに割付対象t265に関する利得推定制御部５１の処理内容を図８に示すフローチャートのステップｄ５以降を参照しながら説明する。
まず、利得推定制御部５１は図２１（ｂ）の(d)に示す得失保持部５６の値を利得保持部３７に格納する(ステップｄ５、図２１（ａ）の(d-1))。
【０２１６】
次に利得推定制御部５１は図２１（ａ）の(d-1)に示す利得保持部３７に格納されている値が最大の資源要素の集合ＲＳ＝(D0, D1, D2, D3, A0, A1, A2)を求める(ステップｄ６)。
次に利得推定制御部５１は集合ＲＳの要素数が複数個であり、割付対象t265と生存区間が重なり且つ未割付けの割付対象 p1, a3 が存在するのでステップｄ９を行う(ステップｄ７、ステップｄ８)。
【０２１７】
次に利得推定制御部５１は集合ＲＳを割付候補資源要素保持部３１に格納し、利得保持部３７の各資源要素に対応する内容をゼロにし、追跡対象保持部５２を空にし、重複割付対象保持部５５に割付対象t265と生存区間が重なり且つ未割付けの割付対象p1, a3 を重複割付対象保持部５５に格納する(ステップｄ９、ステップｄ１０、ステップｄ１１、図１９（ｂ）(d-2)、図２１（ｃ）の(d-3)、図２１（ａ）の(d-2)、図２２（ｃ）の(d))。
【０２１８】
次に利得推定制御部５１は重複割付対象保持部５５から割付対象p1を取り出し、重複割付対象保持部５５から削除する(ステップｄ１２、ステップｄ１３、図２２（ｃ）の(d-1))。
次に得失保持部５６の各資源要素に対応する内容をゼロにし、利得推定制御部５１は処理済割付対象保持部５３、既損失割付対象保持部５４を空にする(ステップｄ１４、図２１（ｂ）の(d-1)、図２２（ａ）の(d-2)、図２２（ｂ）の(d-2))。
【０２１９】
次に利得推定制御部５１は割付対象p1に対して追跡対象A2を生成し、A2の各項目を図１７からA2.ASO = p1,A2.LNS = 1,A2.RES = D0, D1, D2, D3, A0, A1, A2に設定する。 次に図２１（ｃ）の(d-4)のようにA2を追跡対象保持部５２に格納する(ステップｄ１５)。
次に利得推定制御部５１は得失計算ルーチンを呼び出す。
【０２２０】
ここでさらに割付対象t265に関する利得推定制御部５１の処理内容を図９に示すフローチャートを参照しながら説明する。
＜追跡対象A2の処理＞
まず、ステップｅ１、ステップｅ２では追跡対象A2を追跡対象保持部５２から取り出し、追跡対象保持部５２から削除する。さらに追跡対象A2の割付対象項目である割付対象p1を処理済割付対象保持部５３に格納する(図２１（ｃ）の(d-5)、図２２（ａ）の(d-3))。
【０２２１】
次にステップｅ３では追跡対象A2の割付対象項目である割付対象p1は資源要素に割り付けられていないのでステップｅ５に進む。
次にステップｅ５、ステップｅ６では集合ＯＳ１ = (Ar11, Fr1, Ar12, Ar22, Fr2, Ar13, Ar23, Fr3, Br1, Br2, Br3, t262, t263, t264)、集合ＲＳ１ = (D0, D1, A0) を求める。
【０２２２】
次にステップｅ７、ステップｅ８では既損失割付対象保持部５４が図２２（ｂ）の(d-2)のように空なので集合ＯＳ２ = (Ar11, Fr1, Ar12, Ar22, Fr2, Ar13, Ar23, Fr3, Br1, Br2, Br3, t262, t263, t264)、集合ＲＳ２ = (D0, D1, A0) となり、既損失割付対象保持部５４は図２２（ｂ）の(d-3)となる。
次にステップｅ９では得失値 = 1 / A2.LNS = 1 を求め、図２１（ｂ）の(d-1)の得失保持部５６の資源要素D0, D1, A0の内容から減ずる(図２１（ｂ）の(d-2))。
【０２２３】
次にステップｅ１０では追跡対象A2の割付対象項目である割付対象p2と資源継承関係にある割付対象が存在しないので新しい追跡対象は生成されない。次にステップｅ１へ戻る。
次にステップｅ１において追跡対象保持部５２が(図２１（ｃ）の(d-5))のように空なので得失計算ルーチンの処理を終了し、ステップｄ１６に戻る。
【０２２４】
＜割付対象t265に関するステップｄ１７以降の処理その１＞
ここでさらに割付対象t265に関する利得推定制御部５１の処理内容を図８に示すフローチャートのステップｄ１７以降を参照しながら説明する。
まず、利得推定制御部５１は図２１（ｂ）の(d-2)に示す得失保持部５６に格納されている値に割付対象p1の割付優先度0.27を乗じた値を利得保持部３７から減ずる。つまり、図２１（ｂ）の(d-2)のように得失値がマイナスであるところは最終的に図２１（ａ）の(d-3)のように各値を加算することになる。 次にステップｄ１２へ戻る(ステップｄ１７)。
【０２２５】
次に利得推定制御部５１は重複割付対象保持部５５から割付対象a3を取り出し、重複割付対象保持部５５から削除する(ステップｄ１２、ステップｄ１３、図２２（ｃ）の(d-2))。
次に利得推定制御部５１は得失保持部５６の各資源要素に対応する内容をゼロにし、処理済割付対象保持部５３、既損失割付対象保持部５４を空にする(ステップｄ１４、図２１（ｂ）の(d-3)、図２２（ａ）の(d-4)、図２２（ｂ）の(d-4))。
【０２２６】
次に利得推定制御部５１は割付対象a3に対して追跡対象A3を生成し、A3の各項目を図１７および図１９（ｂ）の(d-2)からA3.ASO = a3,A3.LNS = 1,A3.RES = D0, D1, D2, D3, A0, A1, A2に設定する。 次に図２１（ｃ）の(d-6)のようにA2を追跡対象保持部５２に格納する(ステップｄ１５)。
次に利得推定制御部５１は得失計算ルーチンを呼び出す(ステップｄ１６)
ここでさらに割付対象t265に関する利得推定制御部５１の処理内容を図９に示すフローチャートを参照しながら説明する。
【０２２７】
＜追跡対象A3の処理＞
まず、ステップｅ１、ステップｅ２では追跡対象A3を追跡対象保持部５２から取り出し、追跡対象保持部５２から削除する。さらに追跡対象A3の割付対象項目である割付対象a3を処理済割付対象保持部５３に格納する(図２１（ｃ）の(d-7)、図２２（ａ）の(d-5))。
【０２２８】
次にステップｅ３では追跡対象A3の割付対象項目である割付対象a3は資源要素に割り付けられていないのでステップｅ５に進む。
次にステップｅ５〜ステップｅ９では集合ＯＳ１が空であるので集合ＲＳ１、集合ＯＳ２、集合ＲＳ２が空となり得失値は計算されない(図２２（ｂ）の(d-5))。
【０２２９】
次にステップｅ１０では追跡対象A3の割付対象項目である割付対象a3と資源継承関係にある割付対象t263, t264, x2, x3 に対して図２１（ｃ）の(d-8)のように追跡対象A4, A5, A6, A7を生成する。ここで各追跡対象の生存区間長の和はA3.LNS の 1と、割付対象a3 の生存区間長 3 の和 4 となる。次にステップｅ１へ戻る。
【０２３０】
＜追跡対象A4の処理＞
次にステップｅ１、ステップｅ２では追跡対象A4を追跡対象保持部５２から取り出し、追跡対象保持部５２から削除する。さらに追跡対象A4の割付対象項目である割付対象t263を処理済割付対象保持部５３に格納する(図２１（ｃ）の(d-9)、(図２２（ａ）の(d-6))。
【０２３１】
次にステップｅ３では追跡対象A4の割付対象項目である割付対象t263は資源要素D0に割り付けられているのでステップｅ４に進む。
次にステップｅ４では得失値 = 1 / A4.LNS = 0.25 を求め、図２１（ｂ）の(d-3)の得失保持部５６の資源要素D0の内容に加え、ステップｅ１へ戻る(図２１（ｂ）の(d-4))。
【０２３２】
＜追跡対象A5の処理＞
次に追跡対象A5に対しても、追跡対象A4と同様に処理され、追跡対象保持部５２は図２１（ｃ）の(d-10)に得失保持部５６は図２１（ｂ）の(d-5)に処理済割付対象保持部５３は図２２（ａ）の(d-7)に推移する(ステップｅ１〜ステップｅ４、ステップｅ１１)。
【０２３３】
＜追跡対象A6の処理＞
次にステップｅ１、ステップｅ２では追跡対象A6を追跡対象保持部５２から取り出し、追跡対象保持部５２から削除する。さらに追跡対象A6の割付対象項目である割付対象x2を処理済割付対象保持部５３に格納する(図２１（ｃ）の(d-11)、図２２（ａ）の(d-8))。
【０２３４】
次にステップｅ３では追跡対象A6の割付対象項目である割付対象x2は資源要素に割り付けられていないのでステップｅ５に進む。
次にステップｅ５、ステップｅ６では集合ＯＳ１ = (Ar12, Ar22, Fr2, t263, Br2)、集合ＲＳ１ = (D0, D1, A0) を求める。
次にステップｅ７、ステップｅ８では既損失割付対象保持部５４が図２２（ｂ）の(d-5)のように空であるので集合ＯＳ２ = (Ar12, Ar22, Fr2, t263, Br2)、集合ＲＳ２ = (D0, D1, A0) となり、既損失割付対象保持部５４は図２２（ｂ）の(d-6)となる。
【０２３５】
次にステップｅ９では得失値 = 1 / A6.LNS = 0.25 を求め、図２１（ｂ）の(d-5)の得失保持部５６の資源要素D0, D1, A0の内容から減ずる(図２１（ｂ）の(d-6))。
次にステップｅ１０では追跡対象A6の割付対象項目である割付対象x2と資源継承関係にある割付対象a3は図２２（ａ）の(d-8)の処理済割付対象保持部５３に格納されているので追跡対象は生成されない。次にステップｅ１へ戻る。
【０２３６】
＜追跡対象A7の処理＞
次に追跡対象A7に対しても、追跡対象A6と同様に処理され、追跡対象保持部５２は図２１（ｃ）の(d-12)に、得失保持部５６は図２１（ｂ）の(d-7)に、処理済割付対象保持部５３は図２２（ａ）の(d-9)に推移する(ステップｅ１〜ステップｅ４、ステップｅ１０)。
【０２３７】
次にステップｅ１において追跡対象保持部５２が図２１（ｃ）の(d-12)のように空なので得失計算ルーチンの処理を終了し、ステップｄ１６に戻る。
＜割付対象t265に関するステップｄ１７以降の処理その２＞
ここでさらに割付対象t265に関する利得推定制御部５１の処理内容を図８に示すフローチャートのステップｄ１７以降を参照しながら説明する。
【０２３８】
まず、利得推定制御部５１は図２１（ｂ）の(d-7)に示す得失保持部５６に格納されている値に割付対象a3の割付優先度2.67を乗じた値を利得保持部３７から減ずる。つまり、図２１（ｂ）の(d-7)のように得失値がマイナスであるところは最終的に図２１（ａ）の(d-4)のように各値を加算することになる。 次にステップｄ１２へ戻る(ステップｄ１７)。
【０２３９】
次に利得推定制御部５１は図２２（ｃ）の(d-2)に示す重複割付対象保持部５５が空であるので推定利得計算部３６を終了し、ステップｂ８に戻る。
ここでさらに割付対象t265に関する資源別コスト計算部３９の処理内容を図７に示すフローチャートのステップｂ９以降を参照しながら説明する。
＜割付対象t265に関するステップｂ９以降の処理＞
まず、資源要素決定制御部３８は図２１（ａ）の(d-4)に示す利得保持部３７に格納されている値が最大の資源要素の 集合RS = { D1, A0 }を求め、割付候補資源要素保持部３１に格納する(図１９（ｂ）の(d-3))（ステップｂ９）。
【０２４０】
次に資源要素決定制御部３８は集合ＲＳの内容から集合ＲＥＳ = { AR, DR }を得え、評価資源保持部４１に格納する（ステップｂ１０、図２４（ｃ）の(d)）。
次に資源要素決定制御部３８は集合ＲＥＳには二つの資源が存在するのでステップｂ１２を行なう（ステップｂ１１）
次に資源要素決定制御部３８は資源別コスト計算部３９を起動し、コストの算出を行なう（ステップｂ１２）
＜割付対象t265に関する資源別コスト計算部３９の処理＞
ここでさらに割付対象t265に関する資源別コスト計算部３９の処理内容を図１０に示すフローチャートを参照しながら説明する。
【０２４１】
まず、資源別コスト計算制御部５０１は資源別コスト保持部４０および資源別総コスト保持部５０５の各資源要素に対応する内容をゼロにする（ステップｆ１、図２３（ａ）の(d)、図２３（ｂ）の(d)）。
次に資源別コスト計算制御部５０１は追跡対象保持部５０４、処理済割付対象保持部５０６を空にする（ステップｆ２、図２３（ｃ）の(d)、図２４（ａ）の(d)）。
【０２４２】
次に資源別コスト計算制御部５０１は割付対象t265に対して追跡対象rA1を生成し、rA1の各項目をrA1.ASO = t265,rA1.LNS = 1に設定する。  次に図２３（ｃ）の(d-1)のようにrA1を追跡対象保持部５０４に格納する（ステップｆ３）  図２３（ｃ）の(d-1)では追跡対象を(rA1, t265, 1)のように表現し、各項目は（追跡対象名、割付対象、生存区間長の和）を示す。
【０２４３】
次に資源別コスト計算制御部５０１は後順コスト値計算ルーチンを呼び出す（ステップｆ４）
ここでさらに割付対象t265に関する資源別コスト計算部３９の処理内容を図１１に示すフローチャートを参照しながら説明する。
＜追跡対象rA1の処理＞
まず、ステップｇ１、ステップｇ２では追跡対象rA1を追跡対象保持部５０４から取りだし、追跡対象保持部５０４から削除する。さらに追跡対象rA1の割付対象項目であるt265を処理済割付対象保持部５０６に格納する（図２３（ｃ）の(d-2)、図２４（ａ）の(d-1)）。
【０２４４】
次にステップｇ３では図２４（ｃ）の(d)の評価資源保持部４１に格納されておりかつ、割付対象t265に割付け可能な資源AR, DRが存在するのでまず資源ARについてステップｇ４以降を行なう。
＜資源ARについての処理＞
次にステップｇ４においてまず、割付対象t265の使用中間命令i27が取り出され、ステップｇ５おいてコストパタン(間接参照, An, 未, -)が生成され、コストパタン保持部５０２に格納される（図２４（ｂ）の(d)）。
【０２４５】
次にステップｇ６においてコストパタン(間接参照, An, 未)とマッチングするコストエントリである図２０（ａ）の(g)が取り出される。
次にステップｇ７において取り出されたコストエントリのコスト 2 と、追跡対象rA1の生存区間長さの和であるrA1.LSNから後順コスト値 2/1 = 2を算出する。
【０２４６】
次にステップｇ８おいて求めた後順コスト値を資源別総コスト保持部５０５の資源ARの内容に加える（図２３（ｂ）の(d-1)）。
次にステップｇ４に戻り、割付対象t265の中間命令i28が取り出され、コストパタン(加算, 未, An, 未)が生成され、このコストパタンとマッチングする図２０（ａ）の(f)のコストパタンが取り出される。当該コストパタンのコスト3と、追跡対象rA1の生存区間長さの和であるrA1.LSNから後順コスト値 3/1 = 3が算出され、資源別総コスト保持部５０５の資源ARの内容に加算されて図２３（ｂ）の(d-2)となる。
【０２４７】
次にステップｇ４に戻るが、割付対象t265の中間命令が全て取り出されたのでステップｇ３に戻る。
＜資源DRについての処理＞
資源DRについても資源ARと同様にコストの算出を行なうと、図２０（ａ）の(g)(f)のコストエントリにマッチングするので結果的に資源別総コスト保持部５０５は図２３（ｂ）の(d-3)となる。
【０２４８】
次にステップｇ３に戻るが、評価資源保持部４１に格納されている資源AR, DR（図２４（ｃ）(d)）全てについてコスト計算が終了したのでステップｇ９を行なう。
次にステップｇ９では割付対象t265と資源継承関係にある割付対象が存在しないので追跡対象は生成されない。
【０２４９】
次にステップｇ１に戻るが、図２３（ｃ）の(d-2)のように追跡対象保持部５０４が空なので後順コスト値計算ルーチンの処理を終了し、ステップｆ４に戻る。
ここでさらに割付対象t265に関する資源別コスト計算部３９の処理内容を図１０に示すフローチャートのステップｆ５以降を参照しながら説明する。
【０２５０】
＜割付対象t265に関するステップｆ５以降の処理＞
まず、ステップｆ５では資源別総コスト保持部５０５に格納されている値を資源別コスト保持部４０に格納する（図２３（ａ）の(d-1)）。
次にステップｆ６では資源別コスト保持部４０の値が最小である資源 AR, DR を求め、図２４（ｃ）の(d-1)のように評価資源保持部４１に格納する。
【０２５１】
次にステップｆ７では資源別コスト保持部４０の値が最小である資源が複数個であるのでステップｆ８を行なう。
次にステップｆ８では割付対象t265と生存区間が重なる割付対象p1, a3 が存在するのでステップｆ９を行う。
次にステップｆ９、ｆ１０では資源別コスト保持部４０の内容をゼロにし、追跡対象保持部５０４を空にし、割付対象p1, a3 を重複割付対象保持部５０７に格納する(図２３（ａ）の(d-2)、図２３（ｃ）の(d-3)、図２４（ｄ）の(d))。
【０２５２】
次にステップｆ１１、ｆ１２、f１３では重複割付対象保持部５０７から割付対象p1を取り出し、資源別総コスト保持部５０５の内容をゼロにし、処理済割付対象保持部５０６を空にする(図２４（ｄ）の(d-1)、図２３（ｂ）の(d-4)、図２４（ａ）の(d-2))。
次にステップｆ１４では取り出した割付対象p1に対して追跡対象rA2を生成し、rA2の各項目をrA2.ASO = p1rA2.LNS = 1に設定する。次に図２３（ｃ）の(d-4)のようにrA2を追跡対象保持部５０４に格納する。
次に資源別コスト計算制御部５０１は後順コスト値計算ルーチンを呼び出す（ステップｆ１５）
ここでさらに割付対象t265に関する資源別コスト計算部３９の処理内容を図１１に示すフローチャートを参照しながら説明する。
【０２５３】
＜追跡対象rA2の処理＞
まず、ステップｇ１、ステップｇ２では追跡対象rA2を追跡対象保持部５０４から取りだし、追跡対象保持部５０４から削除する。さらに追跡対象rA2の割付対象項目である割付対象p1を処理済割付対象保持部５０６に格納する（図２３（ｃ）の(d-5)、図２４（ａ）の(d-3)）。
【０２５４】
次にステップｇ３では図２４（ｃ）の(d-1)の評価資源保持部４１に格納されておりかつ、割付対象p1に割付け可能な資源AR, DR が存在するのでまず資源ARについてステップｇ４以降を行なう。
＜資源ARについての処理＞
割付対象p1の使用中間命令i5, i27, i29, i30に対してコストパタンがそれぞれ、(代入, An, 未, -)、(間接参照, 未, An, -)、(加算, An, IM, 左同)、(間接参照, 未, An, -)が生成され、それぞれ図２０（ａ）のコストエントリ(h)(i)(a)(i)とマッチングとられ、追跡対象rA2の生存区間長の和であるrA2.LNSから後順コスト値を求めると、図２３（ｂ）の(d-5)のように資源別総コスト保持部５０５の資源ARの内容が更新される(ステップｇ４〜ステップｇ８)。
【０２５５】
＜資源DRについての処理＞
次にステップｇ３に戻り、資源DRが取り出され、割付対象p1の使用中間命令i5, i27, i29, i30に対してコストパタンがそれぞれ、(代入, Dn, 未, -)、(間接参照, 未, Dn, -)、(加算, Dn, IM, 左同)、(間接参照, 未, Dn, -)が生成され、それぞれ図２０（ａ）のコストエントリ(h)(j)(a)(i)とマッチングをとり、追跡対象rA2の生存区間長の和であるrA2.LNSから後順コスト値を求めると、図２３（ｂ）の(d-6)のように資源別総コスト保持部５０５の資源DRの内容が更新される(ステップｇ４〜ステップｇ８)。
【０２５６】
次にステップｇ３に戻るが、条件を満たす資源がすべて取り出されたのでステップｇ９を行う。
次にステップｇ９では割付対象p1と資源継承関係にある割付対象が存在しないので新たに追跡対象は生成せずにステップｇ１へ戻る。
次にステップｇ１では図２３（ｃ）の(d-5)のように追跡対象保持部５０４が空であるので後順コスト値計算ルーチンの処理を終了し、ステップｆ１５に戻る。
【０２５７】
ここでさらに割付対象t265に関する資源別コスト計算部３９の処理内容を図１０に示すフローチャートのステップｆ１６以降を参照しながら説明する。
＜割付対象t265に関するステップｆ１６以降の処理その１＞
まず、ステップｆ１６では得失保持部５６に格納されている値と、割付対象p1の優先度0.27から資源別コスト保持部４０の資源AR, DRの内容は図２３（ａ）の(d-3)のように更新される。
【０２５８】
次にステップｆ１１、ｆ１２、f１３では重複割付対象保持部５０７から割付対象a3を取り出し、資源別総コスト保持部５０５の内容をゼロにし、処理済割付対象保持部５０６を空にする(図２４（ｄ）の(d-2)、図２３（ｂ）の(d-7)、図２４（ａ）の(d-4))。
次にステップｆ１４では取り出した割付対象a3に対して追跡対象rA3を生成し、rA3の各項目をrA3.ASO = a3,rA3.LNS = 1に設定する。
【０２５９】
次に図２３（ｃ）の(d-6)のようにrA3を追跡対象保持部５０４に格納する。
次に資源別コスト計算制御部５０１は後順コスト値計算ルーチンを呼び出す（ステップｆ１５）
ここでさらに割付対象t265に関する資源別コスト計算部３９の処理内容を図１１に示すフローチャートを参照しながら説明する。
【０２６０】
＜追跡対象rA3の処理＞
まず、ステップｇ１、ステップｇ２では追跡対象rA3を追跡対象保持部５０４から取りだし、追跡対象保持部５０４から削除する。さらに追跡対象rA3の割付対象項目である割付対象a3を処理済割付対象保持部５０６に格納する（図２３（ｃ）の(d-7)、図２４（ａ）の(d-5)）。
【０２６１】
次にステップｇ３では図２４（ｃ）の(d-1)の評価資源保持部４１に格納されておりかつ、割付対象a3に割付け可能な資源AR, DRが存在するのでステップｇ４以降を行なう。
＜資源ARについての処理＞
割付対象a3の中間命令i20, i26, i28に対してコストパタンがそれぞれ、(加算, 未, 未, 異)、(加算, 未, 未, 異)、(加算, An, 未, 未)が生成され、図２０のコストエントリ(k)(k)(l)とマッチングがとられ、図２３（ｂ）の(d-8)のように資源別総コスト保持部５０５の資源ARの内容が更新される(ステップｇ４〜ステップｇ８)。
【０２６２】
＜資源DRについての処理＞
次にステップｇ３に戻り、資源DRが取り出され、資源DRについてのも同様に処理を行うなわれ、図２３（ｂ）の(d-9)のように資源別総コスト保持部５０５の資源DRの内容が更新される(ステップｇ４〜ステップｇ８)。
次にステップｇ３に戻るが、条件を満たす資源がすべて取り出されたのでステップｇ９を行う。
【０２６３】
次にステップｇ９では割付対象a3と資源継承関係にある未割付けの割付対象であり、図２４（ａ）の(d-5)の処理済割付対象保持部５０６に格納されていない割付対象x2, x3 に対して追跡対象rA4, rA5を図２３（ｃ）の(d-8)のように生成する。
＜追跡対象rA4の処理＞
次にステップｇ１、ステップｇ２では追跡対象rA4を追跡対象保持部５０４から取りだし、追跡対象保持部５０４から削除する。さらに追跡対象rA4の割付対象項目であるx2を処理済割付対象保持部５０６に格納する（図２３（ｃ）の(d-9)、図２４（ａ）の(d-6)）。
【０２６４】
次にステップｇ３では図２４（ｃ）の(d-1)の評価資源保持部４１に格納されておりかつ、割付対象x2に割付け可能な資源AR, DRが存在するのでステップｇ４以降を行なう。
＜資源ARについての処理＞
割付対象x2の使用中間命令i12, i13, i20に対してコストパタンがそれぞれ、(加算, 未, IM, 異)、(加算, An, IM, 未)、(加算, 未, An, 未)が生成され、図２０の（ａ）のコストエントリ(m)(b)(f)とマッチングがとられ、コスト値 8 が求めれられ、さらに追跡対象rA4の生存区間長の和の項目であるrA4.LNS が４であるから後順コスト値 = 8 / 4 = 2 となり、図２３（ｂ）の(d-10)のように資源別総コスト保持部５０５の資源ARの内容が更新される(ステップｇ４〜ステップｇ８)。
【０２６５】
＜資源DRについての処理＞
次にステップｇ３に戻り、資源DRが取り出され、資源DRについてのも同様に処理を行うなわれ、図２３（ｂ）の(d-11)のように資源別総コスト保持部５０５の資源DRの内容が更新される(ステップｇ４〜ステップｇ８)。
次にステップｇ３に戻るが、条件を満たす資源がすべて取り出されたのでステップｇ９を行う。
【０２６６】
次にステップｇ９では割付対象x2と資源継承関係にある唯一の割付対象a3が、図２４（ａ）の(d-6)のように処理済割付対象保持部５０６に格納されていないるので新たな追跡対象は生成せずにステップｇ１へ戻る。
＜追跡対象rA5の処理＞
次にステップｇ１、ステップｇ２では追跡対象rA5を追跡対象保持部５０４から取りだし、追跡対象保持部５０４から削除する。さらに追跡対象rA5の割付対象項目であるx3を処理済割付対象保持部５０６に格納する（図２３（ｃ）の(d-10)、図２４（ａ）の(d-7)）。
【０２６７】
次に前述に追跡対象rA4の割付対象x2と同様に割付対象x3の使用中間命令i13, i26おける、資源AR, DR の後順コスト値が求められ資源別総コスト保持部５０５の資源AR、資源DRの内容が図２３（ｂ）の(d-12)のように更新される(ステップｇ３〜ステップｇ８)。
さらにステップｇ９では割付対象x3と資源継承関係にある唯一の割付対象a3が、図２４（ａ）の(d-7)のように処理済割付対象保持部５０６に格納されていないるので新たな追跡対象は生成せずにステップｇ１へ戻る。
【０２６８】
次にステップｇ１では図２３（ｃ）の(d-10)のように追跡対象保持部５０４が空であるので後順コスト値計算ルーチンの処理を終了し、ステップｆ１５に戻る。
ここでさらに割付対象t265に関する資源別コスト計算部３９の処理内容を図１０に示すフローチャートのステップｆ１６以降を参照しながら説明する。
【０２６９】
＜割付対象t265に関するステップｆ１６以降の処理その２＞
まず、ステップｆ１６では得失保持部５６に格納されている値と、割付対象a3の優先度2.67から資源別コスト保持部４０の資源AR, DRの内容は図２３（ａ）の(d-4)のように更新される。
次にステップｆ１１に戻るが、図２４（ｄ）の(d-2)のように重複割付対象保持部５０７が空であるので資源別コスト計算部３９の処理を終了し、ステップｂ１２へ戻る。
【０２７０】
ここでさらに割付対象t265に関する資源別コスト計算部３９の処理内容を図７に示すフローチャートのステップｂ１３以降を参照しながら説明する。
＜割付対象t265に関するステップｂ１３以降の処理＞
まず、資源要素決定制御部３８は図２４（ｃ）の(d-1)の評価資源保持部４１に属し、かつ図２３（ａ）の(d-4)の資源別コスト保持部４０に格納されているコストが最小の資源であり、かつ図１９（ｂ）の(d-3)の割付候補資源要素保持部３１に格納されている資源要素D1を t265に割り付ける(ステップｂ１３)。
【０２７１】
このような処理を全ての割付対象に対して行い、各割付対象に資源要素を割り付ける（尚、以上割付対象t265以降の割付対象については説明を省略する。）
このように本発明によれば、プログラム中の各割付対象の資源継承関係が広域的にどうなっているかを参照するため、より理想的な資源割付が行われる。
ネストレベルが深い箇所に優先してレジスタを割り付け、その割り付け済みのレジスタをネストレベルが浅くなる箇所に拡散してゆくようなスマートな割付結果が得られる。また使用頻度が高い箇所に優先してレジスタを割り付け、その割り付け済みのレジスタをネストレベルが低い箇所に拡散してゆくようなスマートな割付結果も得られる。更に引数レジスタ、戻り値レジスタ、破壊レジスタ等予め割り付ける相手が決められた割付対象がその資源を周りに拡げてゆくようなスマートな資源割り付けを実現できる。
【０２７２】
割付結果が非常に洗練されたものになるため最終的に生成する機械語プログラムのプログラムサイズおよび実行速度は一層向上する。
上記実施形態は使用コスト値計算、得失値計算、後順コスト値計算を順に行う構成で計算処理を階層的に詳細化する形で説明してきたが、本実施形態はその要旨を逸脱しない範囲で変更実施することができるのはゆうまでもない。代表的な２つの応用例を以下に示す。
【０２７３】
＜応用例１＞
特にコンパイラが生成する目的コードのサイズの縮小より実行時間の短縮を重視するときは割付対象ｘの使用中間命令ｉが存在するループレベルまたはiの実行回数が解るときはその実行回数をステップｃ７において取り出されるコストエントリｅ１のコストに乗じ、その乗じた値を総コスト保持部に加えてもよい（尚、ループレベルは図８の使用コスト計算制御部４７のフローチャートのステップｃ４で検出され、使用コスト計算部３４に入力される。）。
【０２７４】
＜応用例２＞
またステップｂ９で求められる資源要素の集合ＲＳに複数個の資源要素が存在する場合、ステップｂ１２における資源別コスト計算の後順コスト値計算においてステップｂ４で行った使用コスト計算と同様の処理をすることにより集合ＲＳから更に最適な資源要素を選び出して割付対象ｘに割り付けてもよい。
【０２７５】
この場合、先ず、ステップｇ５からｇ８を更にステップｃ５からｃ９と同様な処理に置き換えて使用コストを算出するようにし、更に図１０、図１１における資源別総コスト保持部５０５を総コスト保持部４６、資源別コスト保持部４０を使用コスト保持部３５、後順コスト値を使用コストに置き換える。そしてステップｂ１１で集合ＲＳの要素が複数かどうかで判定するようにする。
【０２７６】
更にステップｂ１２及びステップｆ１からｆ６において割付対象ｘと資源継承関係にあるか、また間接的に資源継承関係にある未割り付けの割付対象ｘ１に資源ＲＳに属する資源要素を割り付けたときの使用コストを求め、求めた使用コストを更に割付対象ｘから割付対象ｘ１に至る生存区間の長さで割り算した値を使用コスト保持部３５に保持させるようにする。
【０２７７】
加えてステップｆ７において使用コスト保持部３５に保持されている最小コストの資源要素が複数個存在するときステップｆ８を行い、ステップｆ８からステップｆ１１において割付対象ｘと生存区間が重なりかつ未割り付けである割付対象ｘ２と資源継承関係にあるか、あるいは間接的に資源継承関係にある未割り付けの割付対象ｘ３に集合ＲＳに属する資源要素を割り付けたときの使用コストを求め、求めた値を更に割付対象ｘ２から割付対象ｘ３に至る生存区間の長さで割り算した値に−１を乗じた値を使用コスト保持部３５に保持させるようにする。
【０２７８】
このように使用コストを保持させた使用コスト保持部３５の保持内容を参照し、保持内容が最小の資源要素を割付対象ｘに割り付ける。
＜応用例３＞
尚、本実施形態では、得失値として生存区間の和を用いているが、これを割付対象の個数としてもよい。例えば、図１４において、割付対象ｘから割付対象ｘ２に達するまでに存在する割付対象の個数３（割付対象x、x5、x6）を用いて割付対象x2に割り付けられた資源要素の得失値を１／３にしてもよい。
【０２７９】
＜応用例４＞
また、本実施形態では、正の符号を持つ得失値と、負の符号を持つ得失値を求めてそれの和を最終的な得失値としているが、これを別々に使用して、一方の得失値から割り付けレジスタの候補を絞り、更にもう一方の得失値から割り付けレジスタを決定してもよい。例えば、図１５の割付対象ｘのレジスタ決定において、割付対象ｘに割付可能な資源要素をD1,D2,D3とする。このとき、割付け可能な資源要素のうち、先ず負の得失値が最小の資源要素を割付対象ｘの割り付け候補にする。但し、負の得失値が設定されていない資源要素に関しては、負の得失値を０とする。よって資源要素D2,D3の負の得失値は０になる。すると、資源要素D1の負の得失値は『Px／（L1+L2）』であるので、負の得失値が最大の資源要素はレジスタD2,D3となり、これを新たに割付対象ｘの割付け候補にする。
【０２８０】
次に正の得失値が最大の資源要素を割付対象ｘに割り付ける。但し、正の得失値が設定されていない資源要素に関しては正の得失値を０とする。よって資源要素D3の得失値は０となり、得失値が最大の資源要素D2を割付対象ｘに割り付ける。
【０２８１】
【発明の効果】
以上説明したように請求項１又は２記載の資源割付装置によれば、生存区間が連続し合うような位置関係にある複数個の割付対象群は生存区間長の短さに応じて得失値が増加され、また群中の割付対象のうち、割付済みの割付対象と生存区間が重複するものには異なる資源要素が割り付けられるので、生存区間が連続し合う複数個の割付対象が一律に同一の資源要素に割り付けられることはなく、また生存区間の遠近が影響するように資源割付が行われる。そのため周辺の割り付け状況が次回の資源割付に影響するようになり、転送命令の削減数をより多くすることができる。
【０２８２】
また請求項３記載の資源割付装置によれば、得失値が減少されることによって割り付けるべき割付対象からみて損失となるような位置の割付対象に割り付けられている資源要素は低く見積もられるようになるため、周辺の割り付け状況が次回の資源割付に影響するようになり、転送命令の削減数をより多くすることができる。
【０２８３】
また請求項４記載の資源割付装置によれば、未割り付けの割付対象が検出されることで割付済み割付対象に割り付けられている資源要素の得失値が複数回減じられ、他に比べて低く見積もられてしまうことを防止できる。
また請求項５記載の資源割付装置によれば、使用頻度又はネストレベルが高い順に資源要素が割り付けられてゆくため、生存区間の位置関係と、使用頻度及びネストレベルとを考慮した資源割付を実現でき、目的プログラムの品質を向上させることができる。
【０２８４】
また請求項６記載の資源割付装置によれば、得失値が減少されることによって割り付けるべき割付対象からみて損失となるような位置の割付対象に割り付けられている資源要素は低く見積もられるようになるため、周辺の割り付け状況が次回の資源割付に影響するようになり、転送命令の削減数をより多くすることができる。
【０２８５】
また請求項７記載の資源割付装置によれば、得失値が増加されることによって割り付けるべき割付対象からみて利得となるような位置の割付対象に割り付けられている資源要素は高く見積もられるようになるため、周辺の割り付け状況が次回の資源割付に影響するようになり、転送命令の削減数をより多くすることができる。
【０２８６】
また請求項８記載の資源割付装置によれば未割り付けの割付対象が検出されることで割付済み割付対象に割り付けられている資源要素の得失値が複数回減じられ、他に比べて低く見積もられてしまうことを防止できる。
また請求項９記載の資源割付装置によれば、得失値記憶部に記憶されている各資源要素の得失値が、第１及び第２の増加部によって増加され、得失値記憶部に記憶されている各資源要素の得失値が第１及び第２の減少部によって減少させられる。そのため割り付けるべき割付対象から見て同一の資源要素が利得になる箇所と損失になる箇所とに割り付けられていても、当該資源要素がどれだけの利得あるいは損失をもたらすかを客観的に評価でき、より綿密に資源割付を行える。または得失値記憶部は全ての資源要素と、各々の資源要素の得失値の累計の初期値とを対応づけて記憶しているので全ての資源要素が損失になるような位置に割り付けられていれば、どの割付対象にも割り付けられてない資源要素の得失値が大きく見積もられるようになる。そのためどの割付対象にも割り付けられてない資源要素を割り付けるべき割付対象に割り付けることができる。
【０２８７】
また請求項１０記載の資源割付装置によれば、推定値を用いるか得失値を用いるかが切り換えられ、推定値を用いた場合、コードサイズ及び実行時間を資源割付に反映できるのでマイクロプロセッサの持つ命令の詳しいコスト情報を十分に活用でき、３種類以上の機能に別れている資源から割付対象を割付けるのにふさわしい複数の資源要素を選び出せる。機能が異なる資源を複数個備える組み込み用途向けのマイクロプロセッサのプログラムの開発にあたって本発明のコンパイラを使用すれば、そのマイクロプロセッサが備えている機能を充分に発揮する目的プログラムを作成することができる。
【０２８８】
また、請求項１１記載の資源割付装置によれば、割付対象の定義命令及び使用命令を機械語命令化するのにどの資源の資源要素が適切であるかが綿密に判定されるのでターゲットマシンのマイクロプロセッサが備えている機能を充分に発揮する目的プログラムを作成することができる。
また、請求項１２記載の資源割付装置によれば、割り付け済の資源要素について算出された得失値が複数個の異なる資源の資源要素同士で同一の大きさになった場合、優先度がより低い全ての割付対象に相応しいと予測された資源要素をもとに、割付手段が割り付けるべき割付対象に資源要素を割り付けるので、得失値による比較では優劣が付け難い場合に、より綿密な資源要素の選考を行うことができる。その結果として優先度がより低い全ての割付対象の定義命令、使用命令の実行時間および／又はコードサイズが小さくなるような資源割り付けを行うことができる。更にこのように資源要素を割り付ければ、次の割付対象の割り付ける際にその資源要素を継承できるので互いに生存区間が連続しあう割付対象が全て同一の資源要素を割り付ける可能性が高まる。
【０２８９】
また、請求項１３記載の資源割付装置によれば、優先度がより低く、割り付けるべき割付対象より後に割り付けられる割付対象のうち、生存区間が連続し合うものの定義命令、使用命令の実行時間および／又はコードサイズの推定値の大きさと、および、未割り付けの割付対象が、割り付けるべき割付対象からどれだけ遠いかとに基づいて予測が行われるので割り付けるべき割付対象に近い位置にある割付対象の定義命令、使用命令の実行時間および／又はコードサイズが大きく見積もられ、割り付けるべき割付対象に遠い位置にある割付対象の定義命令、使用命令の実行時間および／又はコードサイズが小さく見積もられる。そのため互いに生存区間が連続しあう割付対象が同一の資源要素を割り付ければ可能性が高まる。その結果として後順の割付対象について実行時間および／又はコードサイズが小さくなるような資源要素の予測を確実に行うことができる。
【０２９０】
また、請求項１４または１５記載の資源割付装置によれば、優先度がより低く、割り付けるべき割付対象より後に割り付けられる割付対象のうち、生存区間が重なる側の割付対象の定義命令、使用命令の実行時間および／又はコードサイズの推定値の比較と、および、未割り付けの割付対象から割り付けるべき割付対象がどれだけ遠いかとに基づいて予測が行われるので後順の割付対象について実行時間および／又はコードサイズが小さくなるような資源要素の予測を確実に行うことができる。
【０２９１】
また、請求項１６〜１８記載の何れかの資源割付装置によれば、割付対象の定義命令及び使用命令を機械語命令化するのにどの資源の資源要素が適切であるかが綿密に判定されるので、後順の割付対象について実行時間および／又はコードサイズが小さくなるような資源要素の予測がより確実になる。
また、請求項１９〜２２記載の何れかの資源割付装置によれば、
引数レジスタ、戻り値レジスタ、破壊レジスタを他の割付対象に割り付けることができ、引数レジスタ、戻り値レジスタ、破壊レジスタの格納値をそのまま利用できるような資源割付が行える。そのため転送命令の削減数をより多くすることができる。
【０２９２】
また、請求項２３〜２６記載の何れかの資源割付装置によれば、
割り付けられるべき割付対象の生存区間長と集計部によって集計された生存区間長との和の逆数が算出され、算出結果が、逆数算出部によって生存区間の短さとされるので生存区間長の和を資源割付に反映させることができ、転送命令の削減数をより多くすることができる。
。
【０２９３】
また、請求項２７又は２８記載の資源割付装置によれば、
プログラム中の割付対象と、第１及び第２の集合化手段によって集合化された生存区間継承集合とが書き込み手段によって対応づけられて、生存区間継承関係集合記憶部に書き込まれるので、生存区間の継承、非継承をより効率良く判定することができる。
【０２９４】
また、請求項２９記載の資源割付装置によれば、割り付けるべき割付対象には既に割り付けられた資源要素のうち、得失値が大きいものが割り付けられるので、資源要素を割付対象に割付ける過程において、割付対象への資源要素の割付け状況を綿密に判断することができる。そのため、メモリ、レジスタ間およびレジスタ、レジスタ間の転送命令も少なくなるので、最終的に生成される機械語プログラムのプログラムサイズおよび実行速度を向上させることができる。特にレジスタ数が少数であるターゲットマシンに対して資源割付けを行う場合、上述のプログラムサイズおよび実行速度の向上は特に顕著になる。
【０２９５】
また、請求項３０記載の資源割付装置によれば、得失値が減少されることによって、割り付けるべき割付対象からみて損失となるような位置の割付対象に割り付けられている資源要素は低く見積もられるようになるため、周辺の割り付け状況が次回の資源割付に影響するようになり、転送命令の削減数をより多くすることができる。
【０２９６】
また、請求項３１記載の資源割付装置によれば、得失値が減少されることによって、割り付けるべき割付対象からみて損失となるような位置の割付対象に割り付けられている資源要素は低く見積もられるようになるため、周辺の割り付け状況が次回の資源割付に影響するようになり、転送命令の削減数をより多くすることができる。
【０２９７】
また、請求項３２記載の資源割付装置によれば、得失値が増加されることによって、割り付けるべき割付対象からみて利得となるような位置の割付対象に割り付けられている資源要素は高く見積もられるようになるため、周辺の割り付け状況が次回の資源割付に影響するようになり、転送命令の削減数をより多くすることができる。
【図面の簡単な説明】
【図１】実施形態に係る資源割付装置１３の構成図である。
【図２】割付資源要素決定部２６の構成図である。
【図３】使用コスト計算部３４の構成図である。
【図４】（ａ）推定利得計算部３６の構成図である。
（ｂ）資源別コスト計算部３９の構成図である。
【図５】資源割付制御部２７のフローチャートである。
【図６】資源要素決定制御部３８のフローチャートである。
【図７】使用コスト計算制御部４７の制御内容を示すフローチャートである。
【図８】利得推定制御部５１の制御内容を示すフローチャートである。
【図９】得失計算のフローチャートである。
【図１０】資源別コスト計算制御部５０１の制御内容を示すフロ−チャ−トである。
【図１１】後順コスト計算ルーチンのフロ−チャ−トである。
【図１２】資源とコストとの対応を表す図である。
【図１３】割付対象に各資源の資源要素を割り付けることでその割付対象が定義、使用されている中間命令のコストがどう増減するかを示した図である。
【図１４】割付済みの割付対象の得失値がどう増減するかを示した説明図である。
【図１５】割付済みの割付対象の得失値がどう増減するかを示した説明図である。
【図１６】未割り付けの割付対象の後順コスト値がどういう値になるかを示した説明図である。
【図１７】割付対象保持部２１の保持内容の一例を示す図である。
【図１８】割付対象保持部２１の保持内容の一例を示す図である。
【図１９】（ａ）割付状況テーブルの保持内容の推移の一例を示す図である。
（ｂ）割付候補資源要素保持部３１の保持内容の一例を示す図である。
【図２０】（ａ）演算コストテーブルの一例を示す図である。
（ｂ）使用コスト保持部３５の推移の一例を示す図である。
【図２１】（ａ）利得保持部３７の保持内容の推移の一例を示す図である。
（ｂ）得失保持部５６の保持内容の推移の一例を示す図である。
（ｃ）追跡対象保持部５２の保持内容の推移の一例を示す図である。
【図２２】（ａ）処理済割付対象保持部５３の保持内容の推移の一例を示す図である。
（ｂ）既損失割付対象保持部５４の保持内容の推移の一例を示す図である。
（ｃ）重複割付対象保持部５５の保持内容の推移の一例を示す図である。
【図２３】（ａ）資源別コスト保持部４０の保持内容の推移の一例を示す図である。
（ｂ）資源別総コスト保持部５０５の保持内容の推移の一例を示す図である。
（ｃ）追跡対象保持部５０４の保持内容の推移の一例を示す図である。
【図２４】（ａ）処理済割付対象保持部５０６の保持内容の推移の一例を示す図である。
（ｂ）コストパタン保持部５０２の保持内容の推移の一例を示す図である。
（ｃ）評価資源保持部４１の保持内容の推移の一例を示す図である。
（ｄ）重複割付対象保持部５０７の保持内容の推移の一例を示す図である。
【図２５】高級言語で書かれたプログラムの一例を示す図である。
【図２６】プログラム例に対する中間コードと割付対象の生存区間を示す図である。
【図２７】図２６中の割付対象t265について得失値が計算される際、資源継承関係が辿られる割付対象を図示した図である。
【図２８】プログラムと、当該プログラム中の割付対象とを示した図である。
【図２９】コンパイラの構成図である。
【図３０】（ａ）〜（ｃ）コンパイラによる処理過程を示す図である。
【図３１】従来の資源割付装置６３の構成を示す図である。
【図３２】（ａ）（ｂ）干渉グラフと、当該干渉グラフを頂点結合することで干渉グラフがどう変遷したかを示す図である。
【図３３】（ａ）〜（ｉ）干渉グラフが、グラフ縮退されてゆく様子を示す図である。
【図３４】頂点結合による問題点を表した図である。
【符号の説明】
１１    構文解析装置
１２    最適化装置
１３    資源割付装置
２１    割付対象保持部
２２    割付対象生成部
２３    生存区間重複割付対象検出部
２４    資源継承割付対象検出部
２５    割付優先度計算部
２６    割付資源要素決定部
２７    資源割付制御部
３１    割付候補資源要素保持部
３２    割付可能資源要素検出部
３４    使用コスト計算部
３５    使用コスト保持部
３６    推定利得計算部
３７    利得保持部
３８    資源要素決定制御部
３９    資源別コスト計算部
４０    資源別コスト保持部
４１    評価資源保持部
４３    パタン保持部
４４    演算コスト保持部
４６    総コスト保持部
４７    使用コスト計算制御部
５１    利得推定制御部
５２    追跡対象保持部
５３    処理済割付対象保持部
５４    既損失割付対象保持部
５５    重複割付対象保持部
５６    得失保持部
６３    資源割付装置
５０１    資源別コスト計算制御部
５０２    コストパタン保持部
５０３    資源演算コスト保持部
５０４    追跡対象保持部
５０５    資源別総コスト保持部
５０６    処理済割付対象保持部
５０７    重複割付対象保持部
【図１】
0003638171.tif 000003
【図２】
0003638171.tif 000004
【図３】
0003638171.tif 000005
【図４】
0003638171.tif 000006
【図５】
0003638171.tif 000007
【図６】
0003638171.tif 000008
【図７】
0003638171.tif 000009
【図８】
0003638171.tif 000010
【図９】
0003638171.tif 000011
【図１０】
0003638171.tif 000012
【図１１】
0003638171.tif 000013
【図１２】
0003638171.tif 000014
【図１３】
0003638171.tif 000015
【図１４】
0003638171.tif 000016
【図１５】
0003638171.tif 000017
【図１６】
0003638171.tif 000018
【図１７】
0003638171.tif 000019
【図１８】
0003638171.tif 000020
【図１９】
0003638171.tif 000021
【図２０】
0003638171.tif 000022
【図２１】
0003638171.tif 000023
【図２２】
0003638171.tif 000024
【図２３】
0003638171.tif 000025
【図２４】
0003638171.tif 000026
【図２５】
0003638171.tif 000027
【図２６】
0003638171.tif 000028
【図２７】
0003638171.tif 000029
【図２８】
0003638171.tif 000030
【図２９】
0003638171.tif 000031
【図３０】
0003638171.tif 000032
【図３１】
0003638171.tif 000033
【図３２】
0003638171.tif 000034
【図３３】
0003638171.tif 000035
【図３４】
0003638171.tif 000036