(57)【要約】【課題】ループ内変数へのレジスタ割り当ての際にレジスタが足りなくなった場合でも、オブジェクトコードの高速化を可能とする。【解決手段】未使用レジスタ探索手段Ｓ１は既レジスタ割り当てテーブルＴ１を参照してループ内で未使用のレジスタを探索し未使用レジスタテーブルＴ２に登録し、変数優先度決定手段Ｓ２は変数の優先度を決定して変数・優先度登録テーブルＴ３に登録する。レジスタ割り当て手段Ｓ３は、変数・優先度登録テーブルＴ３の変数に対して未使用レジスタテーブルＴ２の未使用のレジスタを優先度の高い順に割り当てた上で、変数・優先度登録テーブルＴ３に変数がまだ残っている場合、残った変数について命令挿入手段Ｓ４によりメモリへの退避命令およびメモリからの復帰命令をループの入口および出口に挿入してメモリを割り当てる。【選択図】　図１
2004021344.tif 000002
【特許請求の範囲】
【請求項１】
ソースプログラムを入力してオブジェクトプログラムへとコンパイルするコンパイラにおいて、
ループ内で未使用のレジスタを探索する未使用レジスタ探索手段と、
命令が変数に書き込みを行っているか否かに応じて変数の優先度を決定する変数優先度決定手段と、
前記変数優先度決定手段により優先度が決定された変数に対して前記未使用レジスタ探索手段により探索された未使用のレジスタを優先度の高い順に割り当て、未使用のレジスタの全てを変数に割り当てた上で、優先度が決定された変数がまだ残っている場合に、
残った変数についてメモリへの退避命令およびメモリからの復帰命令をループの入口および出口に挿入してメモリを割り当てるレジスタ割り当て手段と
を含むことを特徴とするコンパイラ。
【請求項２】
ソースプログラムを入力してオブジェクトプログラムへとコンパイルするコンパイラにおいて、
命令で使用される変数および該変数に対して割り当てられたレジスタが登録された既レジスタ割り当てテーブルと、
ループ内で未使用のレジスタが登録される未使用レジスタテーブルと、
ループ内に含まれる変数の変数名および優先度が登録される変数・優先度登録テーブルと、
前記既レジスタ割り当てテーブルを参照してループ内で未使用のレジスタを探索し前記未使用レジスタテーブルに登録する未使用レジスタ探索手段と、
命令が変数に書き込みを行っているか否かに応じて変数の優先度を決定して前記変数・優先度登録テーブルに登録する変数優先度決定手段と、
前記変数・優先度登録テーブルに登録された全ての変数に対して前記未使用レジスタテーブルに登録されている未使用のレジスタを優先度の高い順に割り当て、前記未使用レジスタテーブルに登録されている全てのレジスタを変数に割り当てた上で、前記変数・優先度登録テーブルに割り当てなければならない変数がまだ残っている場合、
残った変数についてメモリへの退避命令およびメモリからの復帰命令をループの入口および出口に挿入してメモリを割り当てるレジスタ割り当て手段と
を含むことを特徴とするコンパイラ。
【請求項３】
前記未使用レジスタ探索手段が、前記未使用レジスタテーブルの使用／未使用フラグをすべて未使用に初期設定し、先頭側から順にループ内のある命令に着目し、着目命令がループ内に含まれる命令の最後であるかどうかを判定し、着目命令がループ内に含まれる命令の最後でなければ、着目命令が変数にアクセスしているかどうかを判定し、着目命令が変数にアクセスしていれば、着目命令で使用しているレジスタに対応する前記未使用レジスタテーブル内の使用／未使用フラグを使用に設定することを特徴とする請求項２記載のコンパイラ。
【請求項４】
前記変数優先度決定手段が、前記変数・優先度テーブルに登録された全ての変数名に対応する優先度を初期設定し、先頭側から順にループ内のある命令に着目し、着目命令がループ内に含まれる命令の最後であるかどうかを判定し、着目命令がループ内に含まれる命令の最後でなければ、着目命令が変数にアクセスしているかどうかを判定し、着目命令が変数にアクセスしていれば、該変数に書き込みを行っているかどうかを判定し、該変数に書き込みを行っていなければ、前記変数・優先度登録テーブルの変数名に対応する優先度に第１の重みを加え、該変数に書き込みを行っていれば、前記変数・優先度登録テーブルの変数名に対応する優先度に第１の重みより重い第２の重みを加えることを特徴とする請求項２記載のコンパイラ。
【請求項５】
前記レジスタ割り当て手段が、先頭側から順に前記変数・優先度テーブルに登録されているある命令に着目し、ループ内にレジスタが割り当てられていない変数が残っているかどうかを判定し、ループ内にレジスタが割り当てられていない変数が残っていれば、前記未使用レジスタテーブルに使用／未使用フラグが未使用のレジスタが残っているかどうかを判定し、前記未使用レジスタテーブルに使用／未使用フラグが未使用のレジスタが残っていれば、該レジスタに変数を割り当て、変数に割り当てた未使用のレジスタに対応する前記未使用レジスタテーブルの使用／未使用フラグを使用に変更し、未使用のレジスタが残っていなければ、ループの入口にメモリへの退避命令を挿入し、ループの出口にメモリからの復帰命令を挿入することを特徴とする請求項２記載のコンパイラ。
【請求項６】
前記レジスタ割り当て手段が、命令挿入手段により、ループの入口にメモリへの退避命令を挿入し、ループの出口にメモリからの復帰命令を挿入することを特徴とする請求項２記載のコンパイラ。
【請求項７】
ループ内で未使用のレジスタを探索する未使用レジスタ探索工程と、
命令が変数に書き込みを行っているか否かに応じて変数の優先度を決定する変数優先度決定工程と、
前記変数優先度決定工程で優先度が決定された変数に対して前記未使用レジスタ探索工程で探索された未使用のレジスタを優先度の高い順に割り当て、未使用のレジスタの全てを変数に割り当てた上で、優先度が決定された変数がまだ残っている場合に、
残った変数についてメモリへの退避命令およびメモリからの復帰命令をループの入口および出口に挿入してメモリを割り当てるレジスタ割り当て工程と
を含むことを特徴とするループ内変数へのレジスタ割り当て方法。
【請求項８】
ループ内で未使用のレジスタを探索し、命令で使用される変数および該変数に対して割り当てられたレジスタが登録された既レジスタ割り当てテーブルを参照して未使用レジスタテーブルに登録する未使用レジスタ探索工程と、命令が変数に書き込みを行っているか否かに応じて変数の優先度を決定して変数・優先度登録テーブルに登録する変数優先度決定工程と、
前記変数・優先度登録テーブルに登録された全ての変数に対して前記未使用レジスタテーブルに登録されている未使用のレジスタを優先度の高い順に割り当てるレジスタ割り当て工程と、
前記未使用レジスタテーブルに登録されている全てのレジスタを変数に割り当てた上で、前記変数・優先度登録テーブルに割り当てなければならない変数がまだ残っている場合に、残った変数にメモリを割り当て、メモリへの退避命令およびメモリからの復帰命令をループの入口および出口に挿入する命令挿入工程と
を含むことを特徴とするループ内変数へのレジスタ割り当て方法。
【請求項９】
前記未使用レジスタ探索工程が、前記未使用レジスタテーブルの使用／未使用フラグをすべて未使用に初期設定するステップと、先頭側から順にループ内のある命令に着目するステップと、着目命令がループ内に含まれる命令の最後であるかどうかを判定するステップと、着目命令がループ内に含まれる命令の最後でなければ、着目命令が変数にアクセスしているかどうかを判定するステップと、着目命令が変数にアクセスしていれば、着目命令で使用しているレジスタに対応する前記未使用レジスタテーブル内の使用／未使用フラグを使用に設定するステップとを含むことを特徴とする請求項８記載のループ内変数へのレジスタ割り当て方法。
【請求項１０】
前記変数優先度決定工程が、前記変数・優先度テーブルに登録された全ての変数名に対応する優先度を初期設定するステップと、先頭側から順にループ内のある命令に着目するステップと、着目命令がループ内に含まれる命令の最後であるかどうかを判定するステップと、着目命令がループ内に含まれる命令の最後でなければ、着目命令が変数にアクセスしているかどうかを判定するステップと、着目命令が変数にアクセスしていれば、該変数に書き込みを行っているかどうかを判定するステップと、該変数に書き込みを行っていなければ、前記変数・優先度登録テーブルの変数名に対応する優先度に第１の重みを加えるステップと、該変数に書き込みを行っていれば、前記変数・優先度登録テーブルの変数名に対応する優先度に第１の重みより重い第２の重みを加えるステップとを含むことを特徴とする請求項８記載のループ内変数へのレジスタ割り当て方法。
【請求項１１】
前記レジスタ割り当て工程が、先頭側から順に前記変数・優先度テーブルに登録されているある命令に着目するステップと、ループ内にレジスタが割り当てられていない変数が残っているかどうかを判定するステップと、ループ内にレジスタが割り当てられていない変数が残っていれば、前記未使用レジスタテーブルに使用／未使用フラグが未使用のレジスタが残っているかどうかを判定するステップと、前記未使用レジスタテーブルに使用／未使用フラグが未使用のレジスタが残っていれば、該レジスタに変数を割り当てるステップと、変数に割り当てた未使用のレジスタに対応する前記未使用レジスタテーブルの使用／未使用フラグを使用に変更するステップと、未使用のレジスタが残っていなければ、前記命令挿入工程を呼び出すステップとを含むことを特徴とする請求項８記載のループ内変数へのレジスタ割り当て方法。
【請求項１２】
前記命令挿入工程が、ループの入口にメモリへの退避命令を挿入するステップと、ループの出口にメモリからの復帰命令を挿入するステップとを含むことを特徴とする請求項８記載のループ内変数へのレジスタ割り当て方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明はコンパイラおよびループ内変数へのレジスタ割り当て方法に関し、特にソースプログラムを入力してオブジェクトプログラムへとコンパイルするコンパイラおよびそのループ内変数へのレジスタ割り当て方法に関する。
【０００２】
【従来の技術】
従来のコンパイラにおけるループ内変数へのレジスタ割り当て方法では、ループ内の命令で使用される変数に対してレジスタの割り当てを始める前に、ループの入口および出口で値の保証が必要な変数にあらかじめレジスタを割り当て、その後にループ内の命令で使用される変数に対してレジスタの割り当てを行う。それらの命令で使用される変数に対してレジスタの割り当てを行っている過程でレジスタが足らなくなった時点で、ループの入口および出口で値の保証が必要な変数をメモリに退避することにより、そのレジスタを利用可能な状態にしていた。
【０００３】
ループ内の命令で使用される変数に対してレジスタの割り当てを行う際に、ループの入口および出口で変数の値を保証しなければならない場合、コンパイラは、それらの変数の値を可能な限り、レジスタ上で保証しようとする。しかし、それらの変数が大量にある場合、あるいは利用できるレジスタの数が十分でない場合、それらの変数の値をメモリへと退避する必要がある。
【０００４】
【発明が解決しようとする課題】
従来のコンパイラにおけるループ内変数へのレジスタ割り当て方法では、変数の値をメモリへと退避するに当たって、メモリへの退避命令，メモリからの復帰命令などの非効率な命令が多数生成され、オブジェクトプログラムの高速化に大きな弊害となっているという問題点があった。その理由は、ループ内変数へのレジスタ割り当ての際にレジスタが足りなくなった場合、不要なメモリへの退避命令およびメモリからの復帰命令が多数生成されることが多くあったからである。
【０００５】
本発明の目的は、不要なメモリへの退避命令およびメモリからの復帰命令の生成を抑えることにより、オブジェクトプログラムの高速化を可能とするコンパイラを提供することにある。
【０００６】
また、本発明の他の目的は、コンパイラにおいて不要なメモリへの退避命令およびメモリからの復帰命令の生成を抑えることにより、オブジェクトプログラムの高速化を可能とするループ内変数へのレジスタ割り当て方法を提供することにある。
【０００７】
なお、先行技術文献として、特開平０５―１８９２４５号公報，特開２０００−３３９１７１等があるが、いずれも本発明のようにループ内の命令で使用される変数に対してレジスタを割り付けるものではなく、構成および作用が異なる技術を開示するものである。
【０００８】
【課題を解決するための手段】
本発明のコンパイラは、ソースプログラムを入力してオブジェクトプログラムへとコンパイルするコンパイラにおいて、ループ内で未使用のレジスタを探索する未使用レジスタ探索手段と、命令が変数に書き込みを行っているか否かに応じて変数の優先度を決定する変数優先度決定手段と、前記変数優先度決定手段により優先度が決定された変数に対して前記未使用レジスタ探索手段により探索された未使用のレジスタを優先度の高い順に割り当て、未使用のレジスタの全てを変数に割り当てた上で、優先度が決定された変数がまだ残っている場合に、
残った変数についてメモリへの退避命令およびメモリからの復帰命令をループの入口および出口に挿入してメモリを割り当てるレジスタ割り当て手段とを含むことを特徴とする。
【０００９】
また、本発明のコンパイラは、ソースプログラムを入力してオブジェクトプログラムへとコンパイルするコンパイラにおいて、命令で使用される変数および該変数に対して割り当てられたレジスタが登録された既レジスタ割り当てテーブルと、ループ内で未使用のレジスタが登録される未使用レジスタテーブルと、ループ内に含まれる変数の変数名および優先度が登録される変数・優先度登録テーブルと、前記既レジスタ割り当てテーブルを参照してループ内で未使用のレジスタを探索し前記未使用レジスタテーブルに登録する未使用レジスタ探索手段と、命令が変数に書き込みを行っているか否かに応じて変数の優先度を決定して前記変数・優先度登録テーブルに登録する変数優先度決定手段と、前記変数・優先度登録テーブルに登録された全ての変数に対して前記未使用レジスタテーブルに登録されている未使用のレジスタを優先度の高い順に割り当て、前記未使用レジスタテーブルに登録されている全てのレジスタを変数に割り当てた上で、前記変数・優先度登録テーブルに割り当てなければならない変数がまだ残っている場合、
残った変数についてメモリへの退避命令およびメモリからの復帰命令をループの入口および出口に挿入してメモリを割り当てるレジスタ割り当て手段とを含むことを特徴とする。
【００１０】
さらに、本発明のコンパイラは、前記未使用レジスタ探索手段が、前記未使用レジスタテーブルの使用／未使用フラグをすべて未使用に初期設定し、先頭側から順にループ内のある命令に着目し、着目命令がループ内に含まれる命令の最後であるかどうかを判定し、着目命令がループ内に含まれる命令の最後でなければ、着目命令が変数にアクセスしているかどうかを判定し、着目命令が変数にアクセスしていれば、着目命令で使用しているレジスタに対応する前記未使用レジスタテーブル内の使用／未使用フラグを使用に設定することを特徴とする。
【００１１】
さらにまた、本発明のコンパイラは、前記変数優先度決定手段が、前記変数・優先度テーブルに登録された全ての変数名に対応する優先度を初期設定し、先頭側から順にループ内のある命令に着目し、着目命令がループ内に含まれる命令の最後であるかどうかを判定し、着目命令がループ内に含まれる命令の最後でなければ、着目命令が変数にアクセスしているかどうかを判定し、着目命令が変数にアクセスしていれば、該変数に書き込みを行っているかどうかを判定し、該変数に書き込みを行っていなければ、前記変数・優先度登録テーブルの変数名に対応する優先度に第１の重みを加え、該変数に書き込みを行っていれば、前記変数・優先度登録テーブルの変数名に対応する優先度に第１の重みより重い第２の重みを加えることを特徴とする。
【００１２】
また、本発明のコンパイラは、前記レジスタ割り当て手段が、先頭側から順に前記変数・優先度テーブルに登録されているある命令に着目し、ループ内にレジスタが割り当てられていない変数が残っているかどうかを判定し、ループ内にレジスタが割り当てられていない変数が残っていれば、前記未使用レジスタテーブルに使用／未使用フラグが未使用のレジスタが残っているかどうかを判定し、前記未使用レジスタテーブルに使用／未使用フラグが未使用のレジスタが残っていれば、該レジスタに変数を割り当て、変数に割り当てた未使用のレジスタに対応する前記未使用レジスタテーブルの使用／未使用フラグを使用に変更し、未使用のレジスタが残っていなければ、ループの入口にメモリへの退避命令を挿入し、ループの出口にメモリからの復帰命令を挿入することを特徴とする。
【００１３】
さらに、本発明のコンパイラは、前記レジスタ割り当て手段が、命令挿入手段により、ループの入口にメモリへの退避命令を挿入し、ループの出口にメモリからの復帰命令を挿入することを特徴とする。
【００１４】
一方、本発明のループ内変数へのレジスタ割り当て方法は、ループ内で未使用のレジスタを探索する未使用レジスタ探索工程と、命令が変数に書き込みを行っているか否かに応じて変数の優先度を決定する変数優先度決定工程と、前記変数優先度決定工程で優先度が決定された変数に対して前記未使用レジスタ探索工程で探索された未使用のレジスタを優先度の高い順に割り当て、未使用のレジスタの全てを変数に割り当てた上で、優先度が決定された変数がまだ残っている場合に、
残った変数についてメモリへの退避命令およびメモリからの復帰命令をループの入口および出口に挿入してメモリを割り当てるレジスタ割り当て工程とを含むことを特徴とする。
【００１５】
また、本発明のループ内変数へのレジスタ割り当て方法は、ループ内で未使用のレジスタを探索し、命令で使用される変数および該変数に対して割り当てられたレジスタが登録された既レジスタ割り当てテーブルを参照して未使用レジスタテーブルに登録する未使用レジスタ探索工程と、命令が変数に書き込みを行っているか否かに応じて変数の優先度を決定して変数・優先度登録テーブルに登録する変数優先度決定工程と、前記変数・優先度登録テーブルに登録された全ての変数に対して前記未使用レジスタテーブルに登録されている未使用のレジスタを優先度の高い順に割り当てるレジスタ割り当て工程と、前記未使用レジスタテーブルに登録されている全てのレジスタを変数に割り当てた上で、前記変数・優先度登録テーブルに割り当てなければならない変数がまだ残っている場合に、残った変数にメモリを割り当て、メモリへの退避命令およびメモリからの復帰命令をループの入口および出口に挿入する命令挿入工程とを含むことを特徴とする。
【００１６】
さらに、本発明のループ内変数へのレジスタ割り当て方法は、前記未使用レジスタ探索工程が、前記未使用レジスタテーブルの使用／未使用フラグをすべて未使用に初期設定するステップと、先頭側から順にループ内のある命令に着目するステップと、着目命令がループ内に含まれる命令の最後であるかどうかを判定するステップと、着目命令がループ内に含まれる命令の最後でなければ、着目命令が変数にアクセスしているかどうかを判定するステップと、着目命令が変数にアクセスしていれば、着目命令で使用しているレジスタに対応する前記未使用レジスタテーブル内の使用／未使用フラグを使用に設定するステップとを含むことを特徴とする。
【００１７】
さらにまた、本発明のループ内変数へのレジスタ割り当て方法は、前記変数優先度決定工程が、前記変数・優先度テーブルに登録された全ての変数名に対応する優先度を初期設定するステップと、先頭側から順にループ内のある命令に着目するステップと、着目命令がループ内に含まれる命令の最後であるかどうかを判定するステップと、着目命令がループ内に含まれる命令の最後でなければ、着目命令が変数にアクセスしているかどうかを判定するステップと、着目命令が変数にアクセスしていれば、該変数に書き込みを行っているかどうかを判定するステップと、該変数に書き込みを行っていなければ、前記変数・優先度登録テーブルの変数名に対応する優先度に第１の重みを加えるステップと、該変数に書き込みを行っていれば、前記変数・優先度登録テーブルの変数名に対応する優先度に第１の重みより重い第２の重みを加えるステップとを含むことを特徴とする。
【００１８】
また、本発明のループ内変数へのレジスタ割り当て方法は、前記レジスタ割り当て工程が、先頭側から順に前記変数・優先度テーブルに登録されているある命令に着目するステップと、ループ内にレジスタが割り当てられていない変数が残っているかどうかを判定するステップと、ループ内にレジスタが割り当てられていない変数が残っていれば、前記未使用レジスタテーブルに使用／未使用フラグが未使用のレジスタが残っているかどうかを判定するステップと、前記未使用レジスタテーブルに使用／未使用フラグが未使用のレジスタが残っていれば、該レジスタに変数を割り当てるステップと、変数に割り当てた未使用のレジスタに対応する前記未使用レジスタテーブルの使用／未使用フラグを使用に変更するステップと、未使用のレジスタが残っていなければ、前記命令挿入工程を呼び出すステップとを含むことを特徴とする。
【００１９】
さらに、本発明のループ内変数へのレジスタ割り当て方法は、前記命令挿入工程が、ループの入口にメモリへの退避命令を挿入するステップと、ループの出口にメモリからの復帰命令を挿入するステップとを含むことを特徴とする。
【００２０】
本発明のコンパイラでは、ループの入口および出口で値の保証が必要な変数へのレジスタの割り当てを最初に行うのではなく、ループ内で未使用のレジスタを探索し、命令が変数に書き込みを行っているか否かに応じて変数の優先度を決定し、優先度が決定された変数に対して未使用のレジスタを優先度の高い順に割り当てるループ内変数へのレジスタ割り当て方法を採用する。また、未使用のレジスタの全てを変数に割り当てた上で、優先度が決定された変数がまだ残っている場合に、
残った変数についてメモリへの退避命令およびメモリからの復帰命令をループの入口および出口に挿入してメモリを割り当てるループ内変数へのレジスタ割り当て方法を採用する。
【００２１】
【発明の実施の形態】
以下、本発明の実施の形態について図面を参照して詳細に説明する。
【００２２】
図１は、本発明の第１の実施の形態に係るループ内変数へのレジスタ割り当て方法が適用されたコンパイラ１０の要部を示すブロック図である。このコンパイラ１０は、従来からあるレジスタ割り当て処理により変数に割り当てられたレジスタが登録された既レジスタ割り当てテーブルＴ１と、ループ内で未使用のレジスタが登録される未使用レジスタテーブルＴ２と、ループの入口および出口で値の保証が必要な変数の変数名および優先度が登録される変数・優先度テーブルＴ３と、ループ内で未使用のレジスタを探索する未使用レジスタ探索手段Ｓ１と、ループの入口および出口で値の保証が必要な変数の優先度を決定する変数優先度決定手段Ｓ２と、ループの入口および出口で値の保証が必要な変数に対してレジスタを割り当てるレジスタ割り当て手段Ｓ３と、ループの入口および出口で値の保証が必要な変数にレジスタを割り当てられなかった場合に変数のメモリ（図示せず）への退避命令およびメモリからの復帰命令をループの入口および出口に挿入する命令挿入手段Ｓ４とを有する。なお、図１中、符号２０はソースプログラム、３０はオブジェクトプログラムをそれぞれ示す。
【００２３】
図２を参照すると、既レジスタ割り当てテーブルＴ１には、変数名とレジスタ番号との組が複数登録されている。
【００２４】
図３を参照すると、未使用レジスタテーブルＴ２には、レジスタ番号と使用／未使用フラグとの組が複数登録されるようになっている。
【００２５】
図４を参照すると、変数・優先度テーブルＴ３には、変数名と優先度との組が複数登録されるようになっている。
【００２６】
図５を参照すると、未使用レジスタ探索手段Ｓ１の処理は、初期設定ステップＡ１と、ループ内命令着目ステップＡ２と、命令最後判定ステップＡ３と、変数アクセス判定ステップＡ４と、使用レジスタ登録処理ステップＡ５とからなる。
【００２７】
図６を参照すると、変数優先度決定手段Ｓ２の処理は、初期設定ステップＢ１と、ループ内命令着目ステップＢ２と、命令最後判定ステップＢ３と、変数アクセス判定ステップＢ４と、変数書き込み判定ステップＢ５と、重み２加重ステップＢ６と、重み４加重ステップＢ７とからなる。
【００２８】
図７を参照すると、レジスタ割り当て手段Ｓ３の処理は、変数着目ステップＣ１と、変数残判定ステップＣ２と、未使用レジスタ残判定ステップＣ３と、変数レジスタ割り当てステップＣ４と、レジスタ使用変更ステップＣ５と、命令挿入手段呼び出しステップＣ６とからなる。
【００２９】
図８を参照すると、命令挿入手段Ｓ４の処理は、ストア命令挿入ステップＤ１と、ロード命令挿入ステップＤ２とからなる。
【００３０】
次に、このように構成された第１の実施の形態に係るループ内変数へのレジスタ割り当て方法が適用されたコンパイラ１０の動作について、図１ないし図８を参照しながら説明する。
【００３１】
コンパイラ１０は、従来からあるレジスタ割り当て処理により、ソースプログラム２０中のループ内の命令で使用される変数に対してレジスタ割り当てを行って既レジスタ割り当てテーブルＴ１を作成した後、未使用レジスタ探索手段Ｓ１により、ループ内で未使用のレジスタを探索する。
【００３２】
詳しくは、未使用レジスタ探索手段Ｓ１は、まず、未使用レジスタテーブルＴ２の全てのレジスタ番号に対応する使用／未使用フラグを未使用に初期設定する（ステップＡ１）。
【００３３】
次に、未使用レジスタ探索手段Ｓ１は、先頭側から順にループ内のある命令に着目し（ステップＡ２）、着目命令がループ内に含まれる命令の最後であるかどうかを判定する（ステップＡ３）。
【００３４】
着目命令がループ内に含まれる命令の最後でなければ、未使用レジスタ探索手段Ｓ１は、着目命令が変数にアクセスしているかどうかを判定する（ステップＡ４）。着目命令が変数にアクセスしていなければ、未使用レジスタ探索手段Ｓ１は、ステップＡ２に制御を戻す。
【００３５】
着目命令が変数にアクセスしていれば、未使用レジスタ探索手段Ｓ１は、着目命令で使用している変数に対応するレジスタ番号を既レジスタ割り当てテーブルＴ１を参照して得、得られたレジスタ番号に対応する未使用レジスタテーブルＴ２内の使用／未使用フラグを使用に設定し（ステップＡ５）、ステップＡ２に制御を戻す。
【００３６】
そして、着目命令がループ内に含まれる命令の最後になると（ステップＡ３でイエス）、未使用レジスタ探索手段Ｓ１は、処理を終了する。
【００３７】
次に、コンパイラ１０は、変数優先度決定手段Ｓ２により、ループの入口および出口で値の保証が必要な変数の優先度を決定する。
【００３８】
詳しくは、変数優先度決定手段Ｓ２は、まず、変数・優先度テーブルＴ３の全ての変数名に対応する優先度を０に初期設定する（ステップＢ１）。
【００３９】
次に、変数優先度決定手段Ｓ２は、先頭側から順にループ内に含まれるある命令に着目し（ステップＢ２）、着目命令がループ内に含まれる命令の最後であるかどうかを判定する（ステップＢ３）。
【００４０】
着目命令がループ内に含まれる命令の最後でなければ、変数優先度決定手段Ｓ２は、着目命令が変数にアクセスしているかどうかを判定する（ステップＢ４）。着目命令が変数にアクセスしていなければ、変数優先度決定手段Ｓ２は、ステップＢ２に制御を戻す。
【００４１】
着目命令が変数にアクセスしていれば、変数優先度決定手段Ｓ２は、着目命令が変数に書き込みを行っているかどうかを判定する（ステップＢ５）。
【００４２】
着目命令が変数に書き込み（更新）を行っていなければ（すなわち、読み出し（参照）のみを行っていれば）、変数優先度決定手段Ｓ２は、変数・優先度登録テーブルＴ２の変数名に対応する優先度に重み２を加えて（ステップＢ６）、ステップＢ２に制御を戻す。
【００４３】
一方、着目命令が変数に書き込みを行っていれば、変数優先度決定手段Ｓ２は、変数・優先度登録テーブルＴ２の変数名に対応する優先度に重み４を加えて（ステップＢ７）、ステップＢ２に制御を戻す。
【００４４】
なお、着目命令が複数の変数にアクセスしている場合には、各変数について優先度に重み２または重み４を加える操作をする。
【００４５】
そして、着目命令がループ内に含まれる命令の最後になると（ステップＢ３でイエス）、変数優先度決定手段Ｓ２は、処理を終了する。
【００４６】
この結果、ループ内に含まれる各変数の優先度が、変数の参照回数×２と変数の更新回数×４との和として、変数名に対応して変数・優先度登録テーブルＴ２に設定される。
【００４７】
続いて、コンパイラ１０は、レジスタ割り当て手段Ｓ３により、変数・優先度登録テーブルＴ２に登録された全ての変数に対して未使用レジスタテーブルＴ２に登録されている未使用のレジスタを優先度の高い順に割り当てる。このとき、未使用レジスタテーブルＴ２内に登録されている全てのレジスタを変数に割り当てた上で、変数・優先度登録テーブルＴ３に割り当てなければならない変数がまだ残っている場合（ループの入口および出口で値の保証が必要な変数にレジスタを割り当てられなかった場合）に、メモリへの退避命令およびメモリからの復帰命令をループの入口および出口に挿入する。
【００４８】
詳しくは、レジスタ割り当て手段Ｓ３は、先頭側から順に変数・優先度テーブルＴ３に登録されたある変数に着目し（ステップＣ１）、ループ内にレジスタが割り当てられていない変数が残っているかどうかを判定する（ステップＣ２）。
【００４９】
ループ内にレジスタが割り当てられていない変数が残っていれば、レジスタ割り当て手段Ｓ３は、未使用レジスタテーブルＴ２を参照して使用／未使用フラグが未使用のレジスタが残っているかどうかを判定する（ステップＣ３）。
【００５０】
未使用のレジスタが残っていれば、レジスタ割り当て手段Ｓ３は、この未使用のレジスタを着目変数に割り当て（ステップＣ４）、着目変数に割り当てた未使用のレジスタに対応する未使用レジスタテーブルＴ２の使用／未使用フラグを使用に変更して（ステップＣ５）、ステップＣ１に制御を戻す。
【００５１】
一方、未使用のレジスタが残っていなければ、レジスタ割り当て手段Ｓ３は、命令挿入手段Ｓ１を呼び出した後に（ステップＣ５）、ステップＣ１に制御を戻す。
【００５２】
命令挿入手段Ｓ４は、呼び出されると、ループの入口にストア命令（メモリへの退避命令）を挿入し（ステップＤ１）、ループの出口にロード命令（メモリへの復帰命令）を挿入する（ステップＤ２）。
【００５３】
そして、レジスタ割り当て手段Ｓ３は、ループ内にレジスタが割り当てられていない変数が残っていなくなると（ステップＣでノー）、処理を終了する。
【００５４】
ここで、ループを含む具体的なソースコードの一例として、図９に示すようなＣ言語のソースコードがあるとする。
【００５５】
図９中のｆｏｒループの中には、変数ａ，ｂ，ｃ，ｈの４つの変数が存在している。なぜならば、それらの変数は、ループ直後の関数コールｆｕｎｃ（ａ，ｂ，ｃ，ｈ）で引数とされているので、値が保証されなければいけないからである。
【００５６】
図９のソースコードに対し、従来からあるレジスタ割り当て処理を行った後のアセンブラコードは、図１０に示すようになる。
【００５７】
このとき、ループの入口（ラベルＬ１の直前）での、変数：レジスタの関係は、ａ：Ｒ１，ｂ：Ｒ２，ｃ：Ｒ３，ｈ：Ｒ１０１のようになっていると仮定する。つまり、これらの変数ａ，ｂ，ｃ，ｈが、ループの入口および出口で値の保証が必要な変数となる。
【００５８】
図９中のｆｏｒループに、本実施の形態に係るループ内変数へのレジスタ割り当て方法を適用した場合でも、十分なレジスタがまだ残っており、つまりレジスタＲ１，Ｒ２，Ｒ３，Ｒ１０１を他の用途に使わずに済むときには、アセンブラコードに変更はなく、それがベストなアセンブラコードである。
【００５９】
しかし、図９中のｆｏｒループに、本実施の形態に係るループ内変数へのレジスタ割り当て方法を適用しなかった場合、図１１に示すようなアセンブラコードとなる。ここで、レジスタＲ１０１は、ループの入口で変数ｈの値を保持している。また、本実施の形態に係るループ内変数へのレジスタ割り当て方法を適用していないので、ループ内でどのレジスタが使用されているか分からないため、ループの入口でメモリ上のワークエリアｗｋへの退避命令（※１），およびループの出口でワークエリアｗｋからの復帰命令（※２）が必要になる。
【００６０】
また、この後、ループ内で使用している変数に対してのメモリへの退避命令およびメモリからの復帰命令が生成される。この処理は、計算量が非常に多いなどの理由によりループ内に十分なレジスタがなく、変数ａ，ｂ，ｃに既に割り当てられているレジスタＲ１，Ｒ２，Ｒ３が「…」の箇所で別の用途で使われてしまったときの処理である。この処理において生成されるアセンブラコードは、図１２に示すようになる。ただし、紛らしいので、図１２中には変数ｈに対するメモリへの退避命令およびメモリからの復帰命令は示していない。
【００６１】
変数優先度決定手段Ｓ２は、上記（直前）の処理のために、ループ内で使用されている変数ａ，ｂ，ｃに対して全ての変数にはレジスタをそのまま割り当てておくだけの十分なレジスタ（この例では３つのレジスタが必要）がなく、それより少ないレジスタが残っている場合、例えばこの例で１つのレジスタが残っている場合、変数ａ，ｂ，ｃのどの変数にその唯一のレジスタを割り当てるかを判定するために行われる。この例では、変数：優先度の関係が、ａ：２，ｂ：４，ｃ：８となり、変数ｃにレジスタを割り当てた方が効率が良いことになる。
【００６２】
そこで、そのような処理が行われたときのアセンブラコードは、図１３に示すようになる。図１３のアセンブラコードでは、図１２のアセンブラコードの※３１，※３２，※３３，※３４の部分の命令が不要になっている。
【００６３】
【発明の効果】
第１の効果は、ループ内で大量の変数を使っている場合、あるいはループ内で大量の命令があってレジスタが足りなくなった場合に、オブジェクトプログラムの高速化を得ることできるということである。その理由は、ループの入口および出口で値の保証が必要な変数へのレジスタの割り当てを最初に行うのではなく、ループ内の命令で使用される変数に対してレジスタの割り当てが終了した後に、それらの変数にレジスタ割り当ての優先度を決定して割り当てるようにしたからである。
【図面の簡単な説明】
【図１】本発明の第１の実施の形態に係るループ内変数へのレジスタ割り当て方法が適用されたコンパイラの構成を示す図である。
【図２】図１中の既レジスタ割り当てテーブルの内容を示す図である。
【図３】図１中の未使用レジスタテーブルの内容を示す図である。
【図４】図１中の変数・優先度テーブルの内容を示す図である。
【図５】図１中の未使用レジスタ探索手段の処理を示すフローチャートである。
【図６】図１中の変数優先度決定手段の処理を示すフローチャートである。
【図７】図１中のレジスタ割り当て手段の処理を示すフローチャートである。
【図８】図１中の命令挿入手段の処理を示すフローチャートである。
【図９】ループを含む具体的なソースコードの一例を示す図である。
【図１０】第１の実施の形態に係るループ内変数へのレジスタ割り当て方法を適用し、レジスタも十分に存在した場合の結果のアセンブラコードを示す図である。
【図１１】第１の実施の形態に係るループ内変数へのレジスタ割り当て方法を適用しなかった場合の結果のアセンブラコードを示す図である。
【図１２】第１の実施の形態に係るループ内変数へのレジスタ割り当て方法を適用しなかった場合の結果のアセンブラコードを示す図である。
【図１３】第１の実施の形態に係るループ内変数へのレジスタ割り当て方法が適用されたことにより効率の良い変数へのレジスタ割り当てが行われたときのアセンブラコードを示す図である。
【符号の説明】
１０　コンパイラ
２０　ソースプログラム
３０　オブジェクトプログラム
Ａ１　初期設定ステップ
Ａ２　ループ内命令着目ステップ
Ａ３　命令最後判定ステップ
Ａ４　変数アクセス判定ステップ
Ａ５　使用レジスタ登録処理ステップ
Ｂ１　初期設定ステップ
Ｂ２　ループ内命令着目ステップ
Ｂ３　命令最後判定ステップ
Ｂ４　変数アクセス判定ステップ
Ｂ５　変数書き込み判定ステップ
Ｂ６　重み２加重ステップ
Ｂ７　重み４加重ステップ
Ｃ１　変数着目ステップ
Ｃ２　変数残判定ステップ
Ｃ３　未使用レジスタ残判定ステップ
Ｃ４　変数レジスタ割り当てステップ
Ｃ５　レジスタ使用変更ステップ
Ｃ６　命令挿入手段呼び出しステップ
Ｄ１　ストア命令挿入ステップ
Ｄ２　ロード命令挿入ステップ
Ｓ１　未使用レジスタ探索手段
Ｓ２　変数優先度決定手段
Ｓ３　レジスタ割り当て手段
Ｓ４　命令挿入手段
Ｔ１　既レジスタ割り当てテーブル
Ｔ２　未使用レジスタテーブル
Ｔ３　変数・優先度テーブル
【図１】
2004021344.tif 000003
【図２】
2004021344.tif 000004
【図３】
2004021344.tif 000005
【図４】
2004021344.tif 000006
【図５】
2004021344.tif 000007
【図６】
2004021344.tif 000008
【図７】
2004021344.tif 000009
【図８】
2004021344.tif 000010
【図９】
2004021344.tif 000011
【図１０】
2004021344.tif 000012
【図１１】
2004021344.tif 000013
【図１２】
2004021344.tif 000014
【図１３】
2004021344.tif 000015