JP2011181114A - プログラム変換装置、プログラム変換方法及び記録媒体 - Google Patents

Abstract

【課題】転送命令の生成を低減するプログラム変換装置を提供する。
【解決手段】プログラム変換装置は、ソースプログラムをオブジェクトプログラムに変換するプログラム変換装置であって、実レジスタの代わりに仮想レジスタより記述されたプログラム部分を含むソースプログラムをメモリに記憶し、プログラム部分を跨ぐ生存区間を有する変数を検出し（ステップｃ２）、検出された変数に対して実レジスタを割り当てた場合の得失値を実レジスタ毎に算出し（ステップｃ３）、前記得失値が最小の実レジスタを前記仮想レジスタに割り当てる（ステップｃ４）。
【選択図】図４

Description

本発明は、高級プログラミング言語で書かれたソースプログラムを機械語プログラムやアセンブラプログラムなどの目的プログラム（オブジェクトプログラム）に翻訳するプログラム言語処理系において、高級プログラミング言語で書かれたプログラム部分と、プログラムの特定部分を高速実行するために、より機械語に近いアセンブラ言語で記述した部分の両方を含むソースプログラムを翻訳するプログラム変換装置、プログラム変換方法及び記録媒体に関する。

近年、機器組み込み用プロセッサとともに機器に搭載されるプログラム（以下、組み込みプログラムと呼ぶ）の規模が増大し、組み込みプログラムと言えども、そのプログラム開発はＣ言語などの高級言語で行なわれるのが一般的である。特に、近年急速に発展している通信、画像、文字、音声処理などを扱う、マルチメディア処理を行なう情報機器に搭載される組み込みプログラムでは、プログラムサイズが増大し、高級言語開発は必須となっている。

ところで、これらマルチメディア処理は、大量のデータを高速に処理する事が要求されるため、頻繁に実行されかつ短時間実行を強く要求されるプログラム部分は、高級言語を用いた記述をせずに、機械語に近いアセンブラ言語による記述を行なうことが多い。これは、高級言語記述を用いたプログラム部分は、コンパイラによって、より機械語に近いアセンブラ言語などに変換されるが、コンパイラでは高級言語記述された様々な形のプログラムを想定して翻訳処理を行なうので、どうしても冗長なアセンブラ言語プログラムに変換してしまう場合があるからである。

そこで高級言語の拡張機能として、高級言語記述部分とアセンブラ言語記述部分との値の受渡しを行なえる機能を備えかつ、高級言語記述部分にアセンブラ言語記述部分を埋め込むことができる、「インラインアセンブラ機能」を有するコンパイラが多数存在している。インラインアセンブラ機能の実現方式に関しては、様々な方式が存在するが、その中でも、より使い勝手の良い文献３（後述）の方式について次に述べる。ここでは、説明の簡単化のために、文献３の方式説明でも扱っているＣ言語の除算、剰余算を例にした説明を行なう。

まず、コンパイラがターゲットとするマイクロプロセッサが２オペランド形式のロードストア方式（オペランドのアドレシングにおいて、メモリ間演算命令は転送命令しかない）であり、かつ、除算命令ｄｉｖが次のような仕様であるとする。
ｄｉｖ ｒｍ，ｒｎ
ここにおいて除算命令ｄｉｖは、レジスタｒｍをレジスタｒｎで除算し、除算結果をｒｎに格納し、剰余結果を特殊レジスタｍｄｒに格納する。

このように多くのマイクロプロセッサの除算命令は、除算と剰余算を１命令で同時に算出することが可能である。また図１２などに記述されている転送命令ｍｏｖは第１オペランドの値を第２オペランドに転送することを示すとする。そこで、図１２（ａ）のように「ａｓｍ」キーワードを用いた「ａｓｍ文」（後述するが、正確には「ａｓｍ文ブロック」）を使用して、アセンブラルーチンをマクロ定義し、同図（ｂ）のように複数箇所で使用する。マクロ定義されたマクロｄｍは同図（ｃ）のように展開される。文献３の方式では、変数のうちマクロｄｍの間、値が保存される変数（マクロｄｍに跨って生きている変数と言う）には、マクロｄｍで値が壊されるレジスタ（この場合はレジスタｒ０, ｒ１）が割り付けられないことをコンパイラが保証するので、マクロｄｍを任意の場所に記述することが可能となり、プログラミングの自由度が向上する。

なお、図１２（ａ）のａｓｍ文の記述例は、文献３の例と若干異なっており、複数のａｓｍ文の集合を「｛」「｝」で囲むことによって表現している。このように、複数のａｓｍ文の集合を「ａｓｍブロック」と呼ぶことにする。一つのａｓｍブロックを一つのａｓｍ文と同様に扱うことによって、文献３の方式をａｓｍブロックにも容易に適用できる。

A.V.Aho, R.Sethi, J.D.Ullman:"Compilers, Principle, Techniques, andTool", Addison Wesley Publishing Company Inc.,1986,（邦訳）原田賢一："コンパイラI、II",サイエンス社,1990

しかしながら、文献３の方式では、マクロｄｍの使用箇所によっては、コンパイラが必ずしも効率のよいアセンブラコードに変換できないという問題がある。この点を具体的な例で示す。図１３は、図１２（ｃ）の関数ｆ２をさらにコンパイラ内部で処理しやすいように内部変換したものである。特に図１３の（ｓ１）のように関数ｈの呼び出しの前に、コンパイラが生成した一時変数ｔに変数ｍの値を格納し、変数ｔを関数ｈの引数としている。これは、コンパイラが関数の引数の値を確実にレジスタで渡すために導入したものであり、一時変数ｔにはレジスタｒ０が割り付けられているものとする。（引数をレジスタで渡すことは、高速な関数呼び出しを行なうために、広くコンパイラで行なわれている方式である。）このとき図１３の変数ｍは、ａｓｍブロックに跨って生きているので、レジスタｒ０，ｒ１は変数ｍには割り付けることができない。その結果、変数ｍにはレジスタｒ０，ｒ１以外のレジスタが割り付けられることになり、図１３の（ｓ１）において転送命令が生成されることとなる。

そこで本発明の目的は、転送命令の生成を低減するプログラム変換装置（コンパイラ装置）、プログラム変換方法及び記録媒体を提供することを目的とする。

上記目的を達成するため、本発明に係るプログラム変換装置は、高級言語で記載されたソースプログラムをオブジェクトプログラムに変換するプログラム変換装置であって、任意の実レジスタに割り当てられうる複数の仮想レジスタを用いて、各仮想レジスタが区別して記述されたプログラム部分を含むソースプログラムを入力として受け付ける入力部と、ソースプログラム中の変数であって、プログラム部分を跨ぐ生存区間を有する変数を検出する検出手段と、プログラム部分に出現する複数の仮想レジスタのそれぞれに対して、同一の仮想レジスタには同一の実レジスタを割り当て、相互に異なる仮想レジスタには異なる実レジスタを割り当てるようにしながら、プログラム部分を跨ぐ生存区間を有するソースプログラム中の変数に割り当てられる実レジスタとは異なるレジスタを割り当てる割り当て手段と、割り当て手段によって割り当てられた実レジスタに従って、オブジェクトプログラムを生成する生成手段とを備える。

本構成によれば、プログラム部分を跨ぐ生存区間の変数と、当該変数と資源継承関係にある別の変数とに同じレジスタが割り当てられる可能性が高くなり、同じレジスタが割り当てられた場合には、資源継承関係にある変数と別の変数との間の転送命令を削除することができるので、無用な転送命令の数を低減することができるという効果がある。
また、本発明に係るプログラム変換装置は、上記割り当て手段が、優先的に仮想レジスタに実レジスタを割り当てた後、ソースプログラム中の変数へのレジスタ割り当てを行うものであってもよい。

また、本発明に係るプログラム変換装置は、上記割り当て手段が、すべての実レジスタのうち特定の機能を有する実レジスタ群のうちの１つの実レジスタを仮想レジスタに割り当てるものであってもよい。
本構成によれば、仮想レジスタに割り当てられる実レジスタを特定の機能を有する実レジスタに限定することができるという効果がある。

第１の実施形態に係るコンパイラ装置１の構成図である。 ａｓｍブロック定義レジスタ検出部１７の処理フローチャートである。 ａｓｍブロック生存区間生成部１９の処理フローチャートである。 資源割付部１４の処理フローチャートである。 ａｓｍブロックで定義されたマクロの例と、マクロの使用プログラム例と、マクロの展開プログラムの例を示す図である。 ａｓｍブロックを含む中間プログラムと、レジスタ引数置換部１６の処理を行なった後の中間プログラムの例を示す図である。 ａｓｍブロックを含む中間プログラムと、中間プログラムの生存区間と、割り付け後の中間プログラムを示す図である。 ａｓｍブロック定義レジスタ保持部１８の保持内容の図である。 ａｓｍブロックで定義されたマクロの例と、マクロの使用プログラム例と、マクロの展開プログラムの例を示す図である。 ａｓｍブロックを含む中間プログラムと、レジスタ引数置換部１６の処理を行なった後の中間プログラムの例を示す図である。 ａｓｍブロックを含む中間プログラムと、中間プログラムの生存区間と、割り付け後の中間プログラムを示す図である。 ａｓｍブロックで定義されたマクロの例と、マクロの使用プログラム例と、マクロの展開プログラムの例を示す図である。 ａｓｍブロックを含む中間プログラムの例である。

本発明の実施形態の説明に先だって、本発明に関連する文献を挙げ、以下で用いる用語について説明しておく。
＜文献＞
１．A.V.Aho, R.Sethi, J.D.Ullman:”Compilers, Principle, Techniques, andTool”, Addison Wesley Publishing Company Inc.,1986,（邦訳）原田賢一：”コンパイラI、II”,サイエンス社,1990
２．田中：”資源割付装置及び資源割付プログラムが記録されたコンピュータ読み取り可能な記録媒体”，出願番号 特願平１０−３４４５２４
３．田中：”コンパイラ装置及びコンパイラプログラムが記録されたコンピュータ読み取り可能な記録媒体およびコンパイル方法”，出願番号 特願平１１−１９５７１７
＜用語の説明＞
・変数の定義、参照、使用
変数の値を設定することを「定義する」と呼び、設定した値を使用することを「参照する」と呼ぶ。またプログラム上で変数を定義したり、参照したりすることを、変数を「使用する」と呼ぶことにする。また、以下では仮引数も特に断らない限り変数と同様に扱う。
・一時変数
コンパイラが計算結果を一時的に格納するために生成する変数や、処理の効率化を図る上で生成する変数のことを「一時変数」と呼ぶことにする。以下では特に断らない限り通常のソースプログラムで記述される変数と同様に扱う。
・中間命令
処理をし易すくするためにコンパイラがソースプログラムのコードを中間的なコードに変換したものを「中間コード」と呼び、中間コードの１ステップを「中間命令」と呼ぶことにする。中間命令には４つ組や３つ組などが存在し、これらが変換されて最終的な目的プログラム（オブジェクトプログラム）が生成される。またソースプログラムを中間命令の列に変換したものを「中間プログラム」と呼ぶことにする。図６（ａ）は図５（ｃ）関数ｆ２のプログラムに対する中間プログラムの一例であり、４つ組の一つである３番地コードで表現している。また図６（ａ）のｉ１，ｉ２など、「ｉ」とそれに付随する番号で示したものは、中間命令の識別子を意味している。また、図５（ｃ）のａｓｍブロックは、図６（ａ）のように図面上は図５（ｃ）と同一な形式の中間命令に変換されている。特に図６（ａ）のａｓｍブロックの中間命令を「ａｓｍブロック中間命令」と呼ぶことにする。

尚、本発明における中間命令は特にこの形式に限りるわけでなく他の形式の中間命令にも適用可能である。また、コンパイラ装置内の処理を簡単化するために、中間プログラムの最初と終りを表す中間命令や、関数の始めと終りを表す中間命令など特定のプログラム範囲を表す中間命令も用意されている。図６（ａ）では中間命令ｉ５０，ｉ５１のように表現される関数の関数の始めと終りを示す中間命令が示されている。
・基本ブロック
中間命令列のうち、中間命令列内部からの飛び越しも、また中間命令列内部への飛び越しもなく、中間命令列の実行順が一定順序である場合、その中間命令列を基本ブロックと言う。基本ブロックについては文献１に詳細に記載されている。
・生存区間
生存区間とはそれぞれの変数に保持されている値が有効となる区間であり、正確には変数の値を定義する中間命令からその定義された値を最後に参照する中間命令までのプログラム上の区間のことである。また生存区間中において変数は「生きている」と言うことにする。生存区間のさらに詳しい説明は、文献１、２、３に記載されている。図７（ｂ）が生存区間の一例である。図７（ｂ）において生存区間は縦線の実線で表されている。生存区間の開始点、及び終了点をそれぞれ白丸、黒丸で表現している。また、図７（ｂ）のようにａｓｍブロック中間命令に対する生存区間に関しては、ａｓｍブロック内のａｓｍ文毎の生存区間までも求める必要はなく、生存区間はａｓｍブロック全体を表すもので十分である。
・変数への資源割り付け
変数への資源割り付けとは、変数にレジスタやメモリを割り付けることである。一つのレジスタやメモリにはプログラムの同一区間で二つ以上の値を保持することは不可能であるため、生存区間が重なる変数には同じレジスタやメモリを割り付けることは不可能であり、異なるレジスタやメモリを割り付けることが必須となる。例えば、図７の変数ｍと変数ｓ２（ｓ２に関しては後述）の二つの生存区間が重なっており、それぞれの変数には異なるレジスタやメモリを割り付ける必要がある。以下ではレジスタやメモリを合わせて「資源」と呼ぶことにする。
・資源継承関係
変数ｔと生存区間の始めと終りが一致し、同一の資源に割り付けると転送命令の発生を削減できる変数ｕが存在するとき、変数ｔと変数ｕは「資源継承関係」にあると言うことにする。例えば、図７（ｂ）において、変数ｅと変数ｔ１、変数ｔ１と変数ｍ、変数ｍと変数ｔ２はそれぞれ、資源継承関係にある。また、変数ｅと変数ｍは、「間接的資源継承関係」にあると言うことにする。資源継承関係の詳細な説明は文献２に記載されているので、これ以上の説明は省略する。
・得失値
得失値とは、目的プログラムの転送命令の発生を抑える観点から考えて、既に変数に割り付けられた資源の要素（レジスタやメモリ）を、これから割り付けようとする変数ｔに割り付けたとき、どれだけ転送命令の発生抑制に貢献するかを、変数ｔと資源継承関係または間接的資源継承関係にある変数に着目して定量化した値である。例えば、図７（ｂ）において、変数ｍにレジスタｒ０を割り付けると、中間命令ｉ１１は削除可能となるので、この場合、レジスタｒ０の得失値は増加し、得失値の算出結果から変数ｍにレジスタｒ０を割り付けると有利であると判断される。得失値の詳細な説明は文献２に記載されているので、これ以上の説明は省略する。
＜実施形態の説明＞
本実施形態のコンパイラ装置では、ａｓｍブロック内のレジスタの記述方法において、レジスタ名の前に「ｖ＿」をつけた場合は、特定のレジスタではなく、任意のレジスタを意味することとし、この「ｖ＿」付きのレジスタを「仮想レジスタ」と呼ぶことにする。そして、その有効範囲は、ａｓｍブロック内であるとする。

以下では、図５から図７のプログラム例を参照しながら説明を行なう。特に、図５（ａ）は従来技術の説明で用いた図１２（ａ）のレジスタｒ０の使用部分を仮想レジスタｖ＿ｒ０としたものである。ａｓｍブロック中のレジスタを仮想レジスタで記述するのは、プログラム作成者が行なうものとする。図１は本実施形態のコンパイラ装置の構成図である。図１のコンパイラ装置１は、マクロ展開部１１、構文解析部１２、最適化部１３、資源割付部１４及びコード生成部１５からなる一般的なコンパイラ装置を構成する部分と、レジスタ引数置換部１６、ａｓｍブロック定義レジスタ検出部１７、ａｓｍブロック定義レジスタ保持部１８及びａｓｍブロック生存区間生成部１９からなる本発明に関係する部分から構成されている。

次に各部の動作と機能について例を示しながら説明する。コンパイラ装置１はまず最初にマクロ展開部１１を起動する。マクロ展開部１１は、マクロ定義されたマクロ識別子をその本体で置き換える。この処理部分は一般的なＣ言語コンパイラのマクロプロセッサの処理と同様なので詳細説明は省略し処理結果の例について説明する。
例えば、図５（ａ）がマクロ定義されたマクロｄｍであり、図５（ｂ）がマクロｄｍのソースプログラムにおける使用例であり、図５（ｃ）がマクロ展開部１１によってマクロｄｍをその本体で置き換えた結果である。次にコンパイラ装置１は構文解析部１２を起動する。構文解析部１２はマクロ展開部１１が出力するマクロ展開されたプログラムの字句解析、構文解析および意味解析を行い、コンパイラが処理し易い形の中間プログラムに変換する。

例えば、図５（ｃ）の関数ｆ２は図６（ａ）の中間プログラムに変換される。この構文解析部１２の詳細は本発明の主眼ではないので説明を省略する。次にコンパイラ装置１は最適化部１３を起動する。最適化部１３は、まず後述のレジスタ引数置換部１６を起動し処理を終えた後、最終的にコンパイラ装置１が生成する目的プログラムのプログラムサイズ縮小化及び処理実行時間の短縮化を図るよう中間プログラムの最適化を行う。この最適化部１３の詳細は本発明の主眼ではないので説明を省略し、本発明に関連のある点についてのみ説明する。

最適化部１３では、最適化を行なうために、基本ブロック解析、制御フロー解析、データフロー解析と言う処理を行なう。基本ブロック解析とは処理対象の中間プログラムを基本ブロックに分割することである。制御フロー解析とは各基本ブロック間の制御の流れを解析することである。データフロー解析とは各基本ブロック中、それぞれの変数がどこで定義され、どこで参照されているかについて解析することである。またこれらの解析結果から、後の資源割付部１４は生存区間を算出する。

最適化部１３より起動されるレジスタ引数置換部１６は、まずレジスタで渡される仮引数の値を一旦一時変数に格納する中間命令を関数の最初に挿入し、さらに中間プログラムの仮引数の使用部分を全て一時変数に置き換える。さらに、レジスタで引き渡す実引数の値を一旦一時変数に格納する中間命令を生成し、生成した関数呼び出しの前に挿入し、さらに一時変数に、引き渡しレジスタを割り付けるものである。

例えば、図６（ｂ）では仮引数ｅを一旦一時変数ｔ１に格納する中間命令ｉ１０を関数の最初に挿入し、仮引数ｅの使用箇所を一時変数ｔ１に置き換えている。さらに、図６（ｂ）では実引数ｍに対して一旦一時変数ｔ２に格納する中間命令ｉ１１を関数ｈの呼び出しの前に挿入し、一時変数ｔ２を実引数として関数ｈを呼び出すように置き換えている。なお、ここで、仮引数ｅと、一時変数ｔ２にはレジスタｒ０が割り付けられるものとする。

次にコンパイラ装置１は資源割付部１４を起動する。資源割付部１４はまず最初にａｓｍブロック定義レジスタ検出部１７を起動する。ａｓｍブロック定義レジスタ検出部１７は、中間プログラムからａｓｍブロックの中間命令を抽出し、抽出したａｓｍブロック内に存在するａｓｍ文で定義されるレジスタを検出し、結果をａｓｍブロック定義レジスタ保持部１８に格納する。図２はａｓｍブロック定義レジスタ検出部１７の処理フローチャートである。ステップａ１では、全ての中間命令ｉについてステップａ２からステップａ３を繰り返し、全ての中間命令ｉについて処理を終えたらａｓｍブロック定義レジスタ検出部１７の処理を終了する。ステップａ２では、中間命令ｉがａｓｍブロック中間命令であるときステップａ３を行なう。そうでないときはステップａ１へ戻る。

ステップａ３では、仮想レジスタも含めて、中間命令ｉでレジスタｒが定義されている場合、中間命令ｉとレジスタｒをａｓｍブロック定義レジスタ保持部１８に格納し、ステップａ１へ戻る。
（フローチャート終了）例えば、図８はａｓｍブロック定義レジスタ保持部１８の図６（ｂ）の中間プログラムの例に対する保持内容である。ａｓｍブロック中間命令毎に、ａｓｍブロック中間命令で定義するレジスタを保持しており、図６（ｂ）のａｓｍブロック中間命令ｉ２では変数ｇの値が仮想レジスタｖ＿ｒ０に転送され、変数ｈの値が実レジスタｒ１に転送され、ｄｉｖ命令では仮想レジスタｖ＿ｒ０が更新され、さらに実レジスタｍｄｒも更新されるので、図８のａｓｍ文中間命令ｉ２で定義されるレジスタの欄にはｖ＿ｒ０、ｒ１、ｍｄｒが格納される。（ステップａ３）。

尚、ステップａ３の処理において、ａｓｍブロックで定義されるレジスタを、単にａｓｍブロックに出現するレジスタとして、処理の負荷を軽減させてももよい。なぜならば、特殊な場合を除いて、ａｓｍブロックで記述される大部分のレジスタは、ａｓｍブロック内で定義されてから参照されることが常だからである。
次に資源割付部１４は、最適化部１３で解析された制御フロー情報とデータフロー情報を用いて、前述のレジスタ引数置換部１６で生成した一時変数も含めて、全ての変数の生存区間を算出する。生存区間の算出方法は従来方式と同様なので詳細説明は省略し、ここでは、図６（ｂ）の中間プログラム例に対する生存区間の算出結果を示すにとどめる。図７（ｂ）が図６（ｂ）の中間プログラムに対して生存区間を算出した結果である。生存区間は、文献２などのように中間命令の集合として表現されるが、ここでは直観的に解り易いように実線でその範囲を示している。また、図７（ｂ）の仮引数ｅの生存区間に記載されている（ｒ０）は、仮引数ｅにレジスタｒ０が割り付けられていることを意味している。一時変数ｔ２も同様である。（但し、変数ｓ１、ｓ２の生存区間は次に説明するａｓｍブロック生存区間生成部１９で生成さるものである。）さらに資源割付部１４は、ａｓｍブロック生存区間生成部１９を起動して、ａｓｍ文で定義されるレジスタに割り付けられた特殊な一時変数とその生存区間を生成する。図３がａｓｍブロック生存区間生成部１９の処理フローチャートである。

ステップｂ１では、全てのａｓｍブロック中間命令ｉについてステップｄ２からステップｄ５まで繰り返し、処理を終えたらａｓｍブロック生存区間生成部１９の処理を終了する。ステップｂ２では、仮想レジスタも含めて、ａｓｍブロック定義レジスタ保持部１８からａｓｍブロック中間命令ｉで定義されるレジスタｒが存在するとき、全てのレジスタｒに対して、ステップｄ３からステップｄ５を行ない、そうでないときはステップｄ１へ戻る。

ステップｂ３では、新たに一時変数ｓを生成する。ステップｂ４では、生成した一時変数ｓに対してａｓｍブロック中間命令ｉで生存区間が開始し終了する生存区間を生成する。ステップｂ５では、生成した一時変数ｓにレジスタｒを割り付け、ステップｄ１へ戻る。
（フローチャート終了）例えば、図７（ｂ）において、ｓ１，ｓ２が、ａｓｍブロック生存区間生成部１９で生成された特殊な一時変数であり、生存区間が中間命令ｉ２においてしか存在しておらず、かつ、一時変数ｓ１には仮想レジスタｖ＿ｒ０, 一時変数ｓ２には実レジスタｒ１が割り付けられている。尚、図７の例では、中間命令ｉ２のｄｉｖ命令において、レジスタｍｄｒも値が更新さるが、ここでは、レジスタｍｄｒ自体は変数への割り付けレジスタとはしないこととするので、レジスタｍｄｒに割り付けられた一時変数は生成していない。

次に資源割付部１４は、前述のレジスタ引数置換部１６で生成した未だレジスタが未割り付けの一時変数（図７の例では一時変数ｔ１）および、ａｓｍブロック生存区間生成部１９で生成した一時変数のうち仮想レジスタに割り付けられた一時変数（図７の例では一時変数ｓ１）も含めた変数への資源割り付けを行なう。特に資源割付部１４は、仮想レジスタに割り付けられた一時変数への割り付けを優先する。この割り付けのとき、仮想レジスタに割り付けられた一時変数と生存区間が重なる変数へ割り付けるべきレジスタを考慮してレジスタを割り付ける。図４が資源割付部１４の処理フローチャートである。

ステップｃ１では、全ての、仮想レジスタに割り付けられた変数ｓについてステップｃ２からステップｃ３まで繰り返し、全ての変数ｓについて処理を終えたらステップｃ５に進む。ステップｃ２では、変数ｓと生存区間が重なる変数に割り付けられているレジスタの集合Ｒ１を求める。
ステップｃ３では、変数ｓと生存区間が重なる全ての変数ｔについて、変数ｔと資源継承関係または、間接的資源継承関係にある変数に着目して得失値を算出する。ステップｃ４では、集合Ｒ１に属さずかつ、ステップｃ３で求めた得失値が最小のレジスタを変数ｓに割り付ける。（得失値が大きいレジスタは、変数ｔに割り付けた方が有利であるので、ここでは得失値のより小さいレジスタを変数ｓに割り付ける。尚、この得失値の詳細は文献２で述べられている「資源排他関係」にある変数（文献２では割付対象）に対する得失値計算と同様である。）ここで変数ｓに得失値さ最小のレジスタを割り付けるとしているが、得失値が最小のレジスタに限らず、例えば得失値が最大ではないレジスタとしてもよい。

ステップｃ５では、残りの全ての変数ｖについてステップｃ６からステップｃ９まで繰り返し、全ての変数ｖについて処理を終えたら資源割付部１４の処理を終了する。ステップｃ６では、変数ｖと生存区間が重なる変数に割り付けられているレジスタの集合Ｒ２を求める。
ステップｃ７、集合Ｒ２に属さないレジスタが存在しないときは変数ｖにメモリを割り付けステップｃ５に戻る。ステップｃ８では、変数ｖに関して得失値を算出する。ステップｃ９では、集合Ｒ２に属さないレジスタのうち、ステップｃ８で求めた得失値が最大のレジスタを変数ｖに割り付け、ステップｃ５に戻る。

（フローチャート終了）尚、上記ステップｃ５からステップｃ９の変数ｖへの資源割り付けは、文献２と同様のより厳密な資源割り付けを行なってもよい。図７（ｂ）の例では、一時変数ｓ１へのレジスタ割り付けにおいて、まずステップｃ２で、一時変数ｓ１と生存区間が重なる一時変数ｓ２に割り付けられているレジスタｒ１を要素とする集合Ｒ１が求められる。次にステップｃ３では、一時変数ｓ１と生存区間が重なる変数ｍについて得失値が求められ、この例の場合は、レジスタｒ０の得失値が最大となる。次にステップｃ４では、集合Ｒ１に属さない、つまりレジスタｒ１ではなく、かつ、変数ｍの得失値からレジスタｒ０でもない、レジスタｒ２が一時変数ｓ１への割り付けレジスタとして選択される。

また、変数ｍへのレジスタ割り付けにおいては、まず、ステップｃ６で、変数ｍと生存区間が重なる一時変数ｓ１、ｓ２に割り付けられているレジスタｒ２、ｒ１を要素とする集合Ｒ２が求められる。次にステップｃ８では変数ｍの得失値が求められ、この例ではレジスタｒ０の得失値が最大となる。次にステップｃ９では、集合Ｒ２に属しておらず得失値が最大のレジスタｒ０が変数ｍへの割り付けレジスタとして選択される。変数ｔ１も同様にレジスタｒ０に割り付けられる。

結果、図７（ａ）の中間プログラムは、図７（ｃ）のように変換され、ａｓｍブロック中間命令中の仮想レジスタｖ＿ｒ０は実レジスタｒ２に置き換えられ、また、中間命令ｉ１０、ｉ１１は同一レジスタへの転送となるので削除が可能となる。次にコンパイラ装置１はコード生成部１５を起動し、中間命令をコンパイラがターゲットとするマシンのアセンブラ命令または機械語命令などの目的プログラムに変換する。コード生成部１５自体は従来方式と同様なので詳細説明は省略する。

以上述べた通り、図７、図８のａｓｍブロック中間命令ｉ２内で記述されている仮想レジスタｖ＿ｒ０はレジスタｒ２に置き換えられ、変数ｍはレジスタｒ０に割り付け可能となり、中間命令ｉ１１が削除できる。このように、ａｓｍブロックが記述された場所、または、ａｓｍブロックで定義されたマクロが記述された場所の状況によって、ａｓｍブロック内で記述された仮想レジスタがより適切な実レジスタに置き換わるので、より効率のよいコード生成を行なうことが可能となる。

以下に図５から図７のプログラム例とは別のプログラム例を図９から図１１を用いて説明する。図９（ａ）は図５（ａ）と同様のマクロ定義されたマクロｄｍであり、従来技術の説明で用いた図９（ａ）のレジスタｒ０の使用部分を仮想レジスタｖ＿ｒ０としたものである。ａｓｍブロック中のレジスタを仮想レジスタで記述するのは、プログラム作成者が行なうものとする。図９（ｂ）はマクロｄｍのソースプログラムにおける使用例であり、図９（ｃ）がマクロ展開部１１によってマクロｄｍをその本体で置き換えた結果である。図９（ｃ）の関数ｆ２は図１０（ａ）の中間プログラムに変換される。図１０（ｂ）は、図１０（ａ）の中間プログラムに対して、レジスタ引数置換部１６によって仮引数ｅを一旦一時変数ｔ１に格納する中間命令ｉ１０が挿入され、実引数ｍに対して一旦一時変数ｔ２に格納する中間命令ｉ１１と実引数ｎに対して一旦一時変数ｔ３に格納する中間命令ｉ１２とが関数ｈの呼び出しの前に挿入されている。仮引数の使用部分が一時変数に置き換えられている。図１１（ｂ）は図１０（ｂ）の中間プログラムに対して生存区間を算出した結果である。ここで仮引数ｅに記載されている（ｒ０）は、仮引数ｅにレジスタｒ０が割り付けられていることを意味する。同様に一時変数ｔ２、ｔ３にはそれぞれレジスタｒ０、ｒ１が割り付けられていることを意味する。

図１１（ｂ）の例において図４に示すフローチャートが実行された場合、一時変数ｓ１へのレジスタ割り付けにおいて、まずステップｃ２で、一時変数ｓ１と生存区間が重なる一時変数ｓ２に割り付けられているレジスタｒ２を要素とする集合Ｒ１が求められる。次にステップｃ３では、一時変数ｓ１と生存区間が重なる変数ｍ、ｎについて得失値が求められ、この例の場合は、変数ｍについてはレジスタｒ０、変数ｎについてはｒ１の得失値が最大となる。次にステップｃ４では、集合Ｒ１に属さない、つまりレジスタｒ１ではなく、かつ、変数ｍ、ｎの得失値からレジスタｒ０でもｒ１でもｒ２でもない、レジスタｒ３が一時変数ｓ１への割り付けレジスタとして選択される。

また、変数ｍへのレジスタ割り付けにおいては、まず、ステップｃ６で、変数ｍと生存区間が重なる一時変数ｓ１、ｓ２に割り付けられているレジスタｒ３、ｒ２を要素とする集合Ｒ２が求められる。次にステップｃ８では変数ｍの得失値が求められ、この例ではレジスタｒ０の得失値が最大となる。次にステップｃ９では、集合Ｒ２に属しておらず得失値が最大のレジスタｒ０が変数ｍへの割り付けレジスタとして選択される。変数ｎも同様にレジスタｒ１に割り付けられる。変数ｔ１、ｅも同様にしてレジスタｒ１に割り付けられる。

結果、図１１（ａ）の中間プログラムは、図１１（ｃ）のように変換され、ａｓｍブロック中間命令中の仮想レジスタｖ＿ｒ０は実レジスタｒ３に置き換えられ、また、中間命令ｉ１０、ｉ１１は同一レジスタへの転送となるので削除が可能となる。
以上のようにプログラム部分（実施例においてはａｓｍブロック）内で記述されている仮想レジスタの置換えレジスタを、プログラム部分に跨って生きている変数を考慮して決定することが可能となり、より効率のよいコード生成が可能となる。また、仮想レジスタ記述を含んだプログラム部分をしようして定義された、Ｃ言語のマクロ関数や、Ｃ＋＋言語の「inline」指定関数など、ソースプログラムにインラインされる（埋め込まれる）関数は、ソースプログラムの任意の場所に記述でき、かつ記述された場所の使用状況に応じて、仮想レジスタがより適切な実レジスタに置き換えられるのでコンパイラの生成コード効率が一段と高まる。

以上本発明にかかるプログラム変換装置（コンパイラ装置）について実施形態に基いて説明したが本発明はこれらの実施形態に限らず、以下のようにしてもよい。
（１）本実施の形態の具体例ではａｓｍブロック内の仮想レジスタに対してのみコンパイラがより適切なレジスタに置き換える方式について示したが、特に仮想レジスタ記述を設けずに、ａｓｍブロック内の全てのレジスタ記述を仮想レジスタとして扱い、コンパイラがａｓｍブロック内の全てのレジスタを適切なレジスタに置き換えることも可能である。
（２）仮想レジスタが置き換えられるレジスタに制限を設けてもよい。例えばコンパイラでは、関数の始めでレジスタの値をメモリに退避し、関数の終りでレジスタの値を復帰する必要がある保証レジスタと、その必要がない破壊レジスタを設けることが一般的である。そのため、仮想レジスタの置き換えレジスタを破壊レジスタのいずれかにできると効率の良いコード生成が可能となる場合がある。

この場合コンパイラ装置１は、破壊レジスタの集合を予め記憶し、図４のステップｃ４の処理において、破壊レジスタの集合に属し、集合Ｒ１に属さずかつステップｃ３で求めた得失値が最小のレジスタを変数ｓに割り付けるよう構成すればよい。このように本発明は、例えば破壊レジスタ等の特定の機能を有する実レジスタの集合のうちの１つの実レジスタを仮想レジスタに割り付けるよう構成してもよい。特定の機能を有する実レジスタの種類としては、破壊レジスタ以外に、アドレスレジスタやデータレジスタ等がある。
（３）またアドレスレジスタ、データレジスタのように特定の機能を有する実レジスタの集合が複数ある場合において、これら複数の集合のうちの１つの集合のうちの１つの実レジスタを仮想レジスタに割り当てるよう構成してもよい。この場合、仮想レジスタの種類を仮想レジスタｖ＿Ａｒｉ、ｖ＿Ｂｒｉというように特定の機能を有する集合それぞれに対応するように設け、プログラマはそれら複数種類の仮想レジスタを使い分けた記述を行う。コンパイラ装置１は、仮想レジスタの種類と特定の機能を有する集合とを対応させて記憶しており、ソースプログラム中の仮想レジスタの種類に応じて、対応する特定の機能を有する集合に属し、当該仮想レジスタに割り付けられた変数ｓと生存区間が重なる変数に割り付けられた実レジスタの集合に属さず（つまりＲ１に属さない）、得失値が最小の実レジスタを変数ｓに割り付ける。

より具体的には、図４の資源割付部１４のフローチャートのステップｃ４を「ステップ４において、変数ｓに割り付けられている仮想レジスタの種類に対応する、特定の機能を有する集合に属し、集合Ｒ１に属さず、かつ、ステップ３で求めた得失値が最小のレジスタを変数ｓに割り付ける」となる。
（４）以上の実施例では説明の簡単化のために、除算命令に関するものについて述べたが、単に除算命令に対してのみ適用できるだけでなく、積和演算命令などのマルチメディア処理対応の高機能命令にも適用できることは言うまでもない。
（５）コンパイラ装置１の各構成要素の動作手順、特に図２、３、４に示すフローチャートに示した手順を、汎用のコンピュータ又はプログラム実行機能を有する機器等に実行させるためのコンピュータプログラムを、記録媒体に記録し又は各種通信路等を介して、流通させ頒布することもできる。このような記録媒体にはＩＣカード、光ディスク、フレキシブルディスク、ＲＯＭ等がある。

本発明は、高級プログラミング言語で書かれたソースプログラムを機械語プログラムやアセンブラプログラムなどの目的プログラム（オブジェクトプログラム）に翻訳するプログラム言語処理系において、高級プログラミング言語で書かれたプログラム部分と、プログラムの特定部分を高速実行するために、より機械語に近いアセンブラ言語で記述した部分の両方を含むソースプログラムを翻訳するプログラム変換装置、プログラム変換方法及び記録媒体に好適である。

１ コンパイラ
１１ マクロ展開部
１２ 構文解析部
１３ 最適化部
１４ 資源割付部
１５ コード生成部
１６ レジスタ引数置換部
１７ ａｓｍブロック定義レジスタ検出部
１８ ａｓｍブロック定義レジスタ保持部
１９ ａｓｍブロック生存区間生成部

Claims (5)

1. 高級言語で記載されたソースプログラムをオブジェクトプログラムに変換するプログラム変換装置であって、
   任意の実レジスタに割り当てられうる複数の仮想レジスタを用いて、各仮想レジスタが区別して記述されたプログラム部分を含むソースプログラムを入力として受け付ける入力部と、
   前記ソースプログラム中の変数であって、前記プログラム部分を跨ぐ生存区間を有する変数を検出する検出手段と、
   前記プログラム部分に出現する前記複数の仮想レジスタのそれぞれに対して、同一の仮想レジスタには同一の実レジスタを割り当て、相互に異なる仮想レジスタには異なる実レジスタを割り当てるようにしながら、前記プログラム部分を跨ぐ生存区間を有する前記ソースプログラム中の変数に割り当てられる実レジスタとは異なるレジスタを割り当てる割り当て手段と、
   前記割り当て手段によって割り当てられた実レジスタに従って、オブジェクトプログラムを生成する生成手段と
   を備えることを特徴とするプログラム変換装置。
2. 前記割り当て手段は、優先的に仮想レジスタに実レジスタを割り当てた後、ソースプログラム中の変数へのレジスタ割り当てを行う
   ことを特徴とする請求項１記載のプログラム変換装置。
3. 前記割り当て手段は、すべての実レジスタのうち特定の機能を有する実レジスタ群のうちの１つの実レジスタを仮想レジスタに割り当てる
   ことを特徴とする請求項１記載のプログラム変換装置。
4. 高級言語で記載されたソースプログラムをオブジェクトプログラムに変換するプログラム変換方法であって、
   メモリに記憶されたソースプログラムであって、任意の実レジスタに割り当てられうる複数の仮想レジスタを用いて、各仮想レジスタが区別して記述されたプログラム部分を含むソースプログラムを入力として受け付ける入力部と、
   前記ソースプログラム中の変数であって、前記プログラム部分を跨ぐ生存区間を有する変数を検出する検出ステップと、
   前記プログラム部分に出現する前記複数の仮想レジスタのそれぞれに対して、同一の仮想レジスタには同一の実レジスタを割り当て、相互に異なる仮想レジスタには異なる実レジスタを割り当てるようにしながら、前記プログラム部分を跨ぐ生存区間を有する前記ソースプログラム中の変数に割り当てられる実レジスタとは異なる実レジスタを割り当てる割り当てステップと、
   前記割り当てステップにおいて割り当てられた実レジスタに従って、オブジェクトプログラムを生成する生成ステップとからなる
   ことを特徴とするプログラム変換方法。
5. 高級言語で記載されたソースプログラムをオブジェクトプログラムに変換する処理をコンピュータに実行させるためのプログラムを記録したコンピュータ読み取り可能な記録媒体であって、
   当該プログラムはコンピュータに、メモリに記憶されたソースプログラムであって、任意の実レジスタに割り当てられうる複数の仮想レジスタを用いて、各仮想レジスタが区別して記述されたプログラム部分を含むソースプログラムを入力として受け付ける入力部と、
   前記ソースプログラム中の変数であって、前記プログラム部分を跨ぐ生存区間を有する変数を検出する検出ステップと、
   前記プログラム部分に出現する前記複数の仮想レジスタのそれぞれに対して、同一の仮想レジスタには同一の実レジスタを割り当て、相互に異なる仮想レジスタには異なる実レジスタを割り当てるようにしながら、前記プログラム部分を跨ぐ生存区間を有する前記ソースプログラム中の変数に割り当てられる実レジスタとは異なる実レジスタを割り当てる割り当てステップと、
   前記割り当てステップにおいて割り当てられた実レジスタに従って、オブジェクトプログラムを生成する生成ステップとを実行させる
   ことを特徴とするプログラムを記録した記録媒体。

Images