(57)【要約】【課題】ソース・プログラムをターゲット・マシン上での演算と振る舞いが相違しないように中間表現に変換して処理する。【解決手段】コンパイラ・バックエンドと呼ばれる部分で使用することを低水準中間表現がなされた言語ＬＩＲを提案する。ＬＩＲは、コンパイラ・バックエンドと呼ばれる部分で使用することを目的とした中間言語であり、コード最適化から最終的な機械語生成までの各フェーズにおいて使うことができる。ＬＩＲは、Ｓ式によるシンタックス定義、メモリ参照の考え方はＲＴＬと同様の部分も多いが、とりわけ、上位構造と表示的意味定義を含むという点でＲＴＬとは相違する。【選択図】　図２
2004021441.tif 000002
【特許請求の範囲】
【請求項１】
プログラムを中間表現に変換するプログラム処理装置であって、
上位構造と表示的意味定義に関する記述を含んだ中間言語を生成する、
ことを特徴とするプログラム処理装置。
【請求項２】
前記の上位構造は、１つのコンパイル単位となるモジュールと多値関数インターフェースからなる、
ことを特徴とする請求項１に記載のプログラム処理装置。
【請求項３】
前記の多値関数インターフェースは、関数の始まりの引数に関数の引数を持つとともに、関数の終わりの引数に返却値を持つ、
ことを特徴とする請求項２に記載のプログラム処理装置。
【請求項４】
前記の多値関数インターフェースは、他の関数の呼び出しにおいて当該関数の引数と該他の関数からの返却値を引数に持つ、
ことを特徴とする請求項２に記載のプログラム処理装置。
【請求項５】
前記の多値関数インターフェースは、呼び出した他の関数との間で変数が対応する、
ことを特徴とする請求項４に記載のプログラム処理装置。
【請求項６】
元のプログラム中の基本演算における整数の表現を２の補数表現とする、
ことを特徴とする請求項１に記載のプログラム処理装置。
【請求項７】
元のプログラム中のシフト命令にマシン毎のモディファイヤを付加する、
ことを特徴とする請求項１に記載のプログラム処理装置。
【請求項８】
前記のモディファイヤは、変数が符号付き又は符号なしのいずれであるか、ｎビット符号付き数又は符号なし数として表現できるか、並びに表現できない場合における挙動を表す、
ことを特徴とする請求項７に記載のプログラム処理装置。
【請求項９】
元のプログラム中のｖｏｌａｔｉｌｅ変数をチャネルとして動作するプロセスとして扱う、
ことを特徴とする請求項１に記載のプログラム処理装置。
【請求項１０】
プログラムを中間表現に変換するプログラム処理方法であって、
上位構造と表示的意味定義に関する記述を含んだ中間言語を生成する、
ことを特徴とするプログラム処理方法。
【請求項１１】
前記の上位構造は、１つのコンパイル単位となるモジュールと多値関数インターフェースからなる、
ことを特徴とする請求項１０に記載のプログラム処理方法。
【請求項１２】
前記の多値関数インターフェースは、関数の始まりの引数に関数の引数を持つとともに、関数の終わりの引数に返却値を持つ、
ことを特徴とする請求項１１に記載のプログラム処理方法。
【請求項１３】
前記の多値関数インターフェースは、他の関数の呼び出しにおいて当該関数の引数と該他の関数からの返却値を引数に持つ、
ことを特徴とする請求項１１に記載のプログラム処理方法。
【請求項１４】
前記の多値関数インターフェースは、呼び出した他の関数との間で変数が対応する、
ことを特徴とする請求項１３に記載のプログラム処理方法。
【請求項１５】
元のプログラム中の基本演算における整数の表現を２の補数表現とする、
ことを特徴とする請求項１０に記載のプログラム処理方法。
【請求項１６】
元のプログラム中のシフト命令にマシン毎のモディファイヤを付加する、
ことを特徴とする請求項１０に記載のプログラム処理方法。
【請求項１７】
前記のモディファイヤは、変数が符号付き又は符号なしのいずれであるか、ｎビット符号付き数又は符号なし数として表現できるか、並びに表現できない場合における挙動を表す、
ことを特徴とする請求項１０に記載のプログラム処理方法。
【請求項１８】
元のプログラム中のｖｏｌａｔｉｌｅ変数をチャネルとして動作するプロセスとして扱う、
ことを特徴とする請求項１０に記載のプログラム処理方法。
【請求項１９】
プログラムを中間表現に変換するための処理をコンピュータ・システム上で実行するようにコンピュータ可読形式で記述されたコンピュータ・プログラムであって、
上位構造と表示的意味定義に関する記述を含んだ中間言語を生成する、
ことを特徴とするコンピュータ・プログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、コンピュータ上で実行されるプログラム・コードを処理するプログラム処理装置及びプログラム処理方法、並びにコンピュータ・プログラムに係り、特に、プログラマによって高級プログラミング言語形式で記述されたソース・プログラムを中間表現に変換してから最適化や最終的な機械語生成などの処理を行なうプログラム処理装置及びプログラム処理方法、並びにコンピュータ・プログラムに関する。
【０００２】
さらに詳しくは、本発明は、高級プログラミング言語形式で記述されたソース・プログラムをターゲット・マシン上での演算と振る舞いが相違しないように中間表現に変換して処理するプログラム処理装置及びプログラム処理方法、並びにコンピュータ・プログラムに係り、特に、高級プログラミング言語形式で記述されたソース・プログラムにおける命令の意味を厳密に定義した中間表現に変換してターゲット・マシン上での正確な演算と振る舞いを実現するプログラム処理装置及びプログラム処理方法、並びにコンピュータ・プログラムに関する。
【０００３】
【従来の技術】
昨今の技術革新に伴い、さまざまなアーキテクチャのコンピュータ・システムが開発され広汎に普及している。コンピュータは、コンピュータ可読形式で記述されたプログラム・コードを実行することによって、産業上のさまざまな制御や適用業務など、所望の処理を実行することができる。
【０００４】
コンピュータ・プログラムは、一般に、プログラマによって高級プログラミング言語形式で記述されたソース・コードを、対象とするアーキテクチャが実行可能な命令セットを用いて記述された形式すなわちオブジェクト・コードに変換すなわちコンパイルして用いられる。そして、コンパイル処理時には、元のプログラム・コードをいわゆる中間表現に置き換え、実際の処理効率を向上し処理の高速化を実現するために変更を加える「最適化」から、最終的な機械語生成までの各フェーズにおいて使われる。
【０００５】
コンパイラの中間表現において、それを使った積極的な最適化を行なうためには、プログラム・コードの意味が厳密に定義されている必要がある。
【０００６】
例えば、Ｊａｖａ（登録商標）のようなどのマシンでも動くプログラム言語体系においては、同じ命令は同じ意味を持つ。したがって、コンパイラのインプリメント言語としてＪａｖａ（登録商標）を使用した場合、命令の使用が厳密に決められているので、あるターゲット・マシン上でそのマシンのオブジェクト・コードを生成するという状況においてすら、そのコンパイラは「クロス・コンパイラ」である。すなわち、Ｊａｖａ（登録商標）のある演算は、一見対応するように見えるターゲット・マシンでの演算と振る舞いが異なる可能性がある。典型的には、定数畳み込みなどでバグの原因となりかねない。実際、クロス環境で動作する動作する高級言語コンパイラのバグは基本的に中間言語が持つ意味定義のあいまいさに起因していることが多いと考えられる。
【０００７】
このような危険性を回避するために、命令の意味を厳密に定義する必要があると本発明者らは思料する。
【０００８】
しかし、この問題は単に何らかの厳密な定義を与えればよいというものでは解決されない。すなわち、リターゲッタブル・コンパイラである以上、Ｊａｖａ（登録商標）のようにターゲット・マシンをこちらで勝手に定義することはできない。アドレッシング・モードの多様性は、たしかに基本演算の組み合わせで吸収することができるが、ここで問題なのは加算とか乗算といった基本演算である。例えば２の補数表現の計算機と１の補数表現の計算機では同じ整数加算でも異なる意味となる。
【０００９】
単に表現力のみ追求するならば、基本演算を増やすなり多義にすればよいが、そのために命令の簡潔さが失われ、インプリメントは複雑になる。
【００１０】
【発明が解決しようとする課題】
本発明の目的は、高級プログラミング言語形式で記述されたソース・プログラムをターゲット・マシン上での演算と振る舞いが相違しないように中間表現に変換して処理することができる、優れたプログラム処理装置及びプログラム処理方法、並びにコンピュータ・プログラムを提供することにある。
【００１１】
本発明のさらなる目的は、高級プログラミング言語形式で記述されたソース・プログラムにおける命令の意味を厳密に定義した中間表現に変換してターゲット・マシン上での正確な演算と振る舞いを実現することができる、優れたプログラム処理装置及びプログラム処理方法、並びにコンピュータ・プログラムを提供することにある。
【００１２】
【課題を解決するための手段及び作用】
本発明は、上記課題を参酌してなされたものであり、その第１の側面は、プログラムを中間表現に変換するプログラム処理装置又はプログラム処理方法であって、
上位構造と表示的意味定義に関する記述を含んだ中間言語を生成する、
ことを特徴とするプログラム処理装置又はプログラム処理方法である。
【００１３】
本発明者らは、多言語（マルチソース）、多機種（リターゲッタブル）コンパイラを目指している。多言語サポートに関しては、ＨＩＲ（Ｈｉｇｈ−ｌｅｖｅｌ　Ｉｎｔｅｒｍｅｄｉａｔｅ　Ｒｅｐｒｅｓｅｎｔａｔｉｏｎ）という中間言語があり、少なくともＣ、Ｆｏｒｔｒａｎ、Ｊａｖａ（登録商標）の３つのソース言語を表現することを目指している。
【００１４】
中間言語を、基本的な演算ノードからなるツリーで表現し、それを各マシン命令を表すツリーでパターン・マッチし、マシン固有の命令に分解することによりコード生成を行なうという構成自体は、既にリターゲッタブル・コンパイラの確立した技術である。本発明は、このアプローチに従う。
【００１５】
ＧＣＣ（ＧＮＵ　Ｃ　Ｃｏｍｐｉｌｅｒ）もこのアプローチに基づくリターゲッタブル・コンパイラであり、その中間言語はＲＴＬ（Ｒｅｇｉｓｔｅｒ　Ｔｒａｎｓｆｅｒ　Ｌａｎｇｕａｇｅ）と呼ばれる。最近では、厳密にＧＣＣのＲＴＬではないのに、同様の表現をＲＴＬと呼ぶこともあるようで、ＧＣＣの影響力を感じる。ＧＣＣが成功した大きな理由の１つは明らかにこのＲＴＬの簡潔で明解なデザインにある。
【００１６】
多くのコンパイラの中間言語は、インプリメンタのみ知り得るものであり、よって、その意味はアドホックに多義的なものになりがちである。その点、ＧＣＣのＲＴＬはその名前通り正式な言語として設計されている。それはＳ式によるシンタックスを持ち、また、非公式であるが十分に厳密な意味定義もされており、しっかりしたドキュメントも存在する。
【００１７】
本発明者らは、ＲＴＬ以外の、コンパイラ・バックエンドと呼ばれる部分で使用することを低水準中間表現がなされた言語（Ｌｏｗ−ｌｅｖｅｌ　Ｉｎｔｅｒｍｅｄｉａｔｅ　Ｒｅｐｒｅｓｅｎｔａｔｉｏｎ：以下、「ＬＩＲ」とも呼ぶ）を提案する。
【００１８】
本発明に係るＬＩＲは、コンパイラ・バックエンドと呼ばれる部分で使用することを目的とした中間言語であり、コード最適化から最終的な機械語生成までの各フェーズにおいて使うことができる。
【００１９】
ＬＩＲは、Ｓ式によるシンタックス定義、メモリ参照の考え方はＲＴＬと同様の部分も多いが、とりわけ、上位構造と表示的意味定義を含むという点でＲＴＬとは相違する。
【００２０】
ＬＩＲ＝ＲＴＬ＋上位構造＋表示的意味定義
【００２１】
ここで、上位構造とは、モジュールとたち関数インターフェースからなる。ＧＣＣのＲＴＬは実行可能コードのみの表現であった。しかし、中間言語を正式なプログラミング言語として設計するには、データの表現も含めた１つのコンパイラ単位すなわち「モジュール」に対する表現が必要になってくる。
【００２２】
また、表示的意味定義とは、ＬＩＲのセマンティックスが公式に定義されていることを意味する。どんな言語であれ、言語仕様は厳密であることに越したことはないが、リターゲッタブル性を考慮した中間言語において厳密な定義は本質的である。
【００２３】
プログラムを実際に起動するターゲット・マシン以外のマシン上でオブジェクト・コードを生成するというクロス・コンパイラ環境下では、一見対応するように見えるターゲット・マシンでの演算と振る舞いが異なる可能性がある。典型的には、定数畳み込みなどでバグの原因となりかねない。実際、クロス環境で動作する動作する高級言語コンパイラのバグは基本的に中間言語が持つ意味定義のあいまいさに起因していることが多いと考えられる。
【００２４】
このような危険性を回避するためには、命令の意味を厳密にする必要があるが、単に何らかの厳密な定義を与えれば解決できるという問題ではない。アドレッシング・モードの多様性は、たしかに基本演算の組み合わせで吸収することができるが、ここで問題なのは加算とか乗算といった基本演算である。例えば２の補数表現の計算機と１の補数表現の計算機では同じ整数加算でも異なる意味となる。
【００２５】
単に表現力のみ追求するならば、基本演算を増やすなり多義にすればよいが、そのために命令の簡潔さが失われ、インプリメントは複雑になる。そこで、本発明者らは、現在主に使われている計算機のハードウェア構成を考慮して、メモリがバイト・アドレスであることから、整数の表現は２の補数であるという仮定をおくことにした。
【００２６】
また、そのような仮定をおいてもなお意味を１つに定義することができないような命令が残る。それは、Ｊａｖａ（登録商標）とＣに存在するシフト命令である。そのために、ＬＩＲのシフト命令は現行のマシンにおける相違を吸収することができる表現を採用する。
【００２７】
また、Ｃ言語にあるｖｏｌａｔｉｌｅ変数の考えは重要なものである。ＬＩＲのメモリ・アクセス式はｖｏｌａｔｉｌｅオブジェクトを表現することができる。同様の表現はＲＴＬにも存在するが、本発明者らはその表示的意味を定義し、その定義が自然であることを示す。
【００２８】
また、関数呼び出しはリターゲッタブル・コンパイラで問題となる部分の１つである。ターゲット・マシンを固定したとしてもなお、さまざまなコーリング・シーケンスがあり得る。引数の一部は通常レジスタに割り当てるが、それは後にレジスタ・アロケータが自由に割り当ててよいものではなく、関数呼び出しの規約に従った割り当てをしなければならない。ＧＣＣではＲＴＬ生成時にコーリング・シーケンスを展開してしまう、という方法を採用している。これは１つの極端な方法であり、最適化の品質を期待することはできるがコード最適化が複雑になる。
【００２９】
これに対し、本発明では、ＬＩＲの関数呼び出しを高級言語のようにパラメータを明示する表現としており、ＲＴＬとのアプローチと逆のメリットを持つ。
【００３０】
また、本発明の第２の側面は、プログラムを中間表現に変換するための処理をコンピュータ・システム上で実行するようにコンピュータ可読形式で記述されたコンピュータ・プログラムであって、
上位構造と表示的意味定義に関する記述を含んだ中間言語を生成する、
ことを特徴とするコンピュータ・プログラムである。
【００３１】
本発明の第２の側面に係るコンピュータ・プログラムは、コンピュータ・システム上で所定の処理を実現するようにコンピュータ可読形式で記述されたコンピュータ・プログラムを定義したものである。換言すれば、本発明の第２の側面に係るコンピュータ・プログラムをコンピュータ・システムにインストールすることによって、コンピュータ・システム上では協働的作用が発揮され、本発明の第１の側面に係るプログラム変換装置又はプログラム変換方法と同様の作用効果を得ることができる。
【００３２】
本発明のさらに他の目的、特徴や利点は、後述する本発明の実施形態や添付する図面に基づくより詳細な説明によって明らかになるであろう。
【００３３】
【発明の実施の形態】
以下、図面を参照しながら本発明の実施形態について詳解する。
【００３４】
Ａ．システム構成
図１には、本実施形態に係るプログラム処理装置１００のハードウェア構成を模式的に示している。
【００３５】
メイン・コントローラであるＣＰＵ（Ｃｅｎｔｒａｌ　Ｐｒｏｃｅｓｓｉｎｇ　Ｕｎｉｔ）１０１は、オペレーティング・システム（ＯＳ）の制御下で、各種のアプリケーションを実行する。
【００３６】
本実施形態では、ＣＰＵ１０１は、例えば、高級プログラミング言語を用いてソース・プログラムを作成・編集するためのエディタや、ソース・プログラムをオブジェクト・プログラムに変換するためのコンパイラ、コンパイラによって生成されたオブジェクト・プログラムなどを実行することができる。コンパイラは、最適化処理を備えている。また、コンパイラは、コード最適化から最終的な機械語生成までの各フェーズにおいて、ソース・プログラムを中間的に表現した中間言語を生成し使用する。
【００３７】
図示の通り、ＣＰＵ１０１は、バス１０８によって他の機器類（後述）と相互接続されている。
【００３８】
主メモリ１０２は、ＣＰＵ１０１において実行されるプログラム・コードをロードしたり、実行プログラムの作業データを一時保管するために使用される記憶装置であり、例えばＤＲＡＭ（Ｄｙｎａｍｉｃ　ＲＡＭ）のような半導体メモリが使用される。例えば、エディタ、コンパイラ、オブジェクト・プログラムなどが実行プログラムとして主メモリ１０２にロードされる。また、編集中・コンパイル中のソース・プログラムや、コンパイラがソース・プログラムをコンパイル処理中に生成するソース・プログラムの中間表現（中間表現は、基本ブロックに分割されることもあり、また、基本ブロックは、ＤＡＧ（Ｄｉｒｅｃｔｅｄ　Ａｃｙｃｌｉｃ　Ｇｒａｐｈ）で表現されることもある）、コンパイル処理されたオブジェクト・プログラムなどが作業データとして主メモリ１０２に一時的に格納される。
【００３９】
また、ＲＯＭ（Ｒｅａｄ　Ｏｎｌｙ　Ｍｅｍｏｒｙ）１０３は、データを恒久的に格納する半導体メモリであり、例えば、起動時の自己診断テスト（ＰＯＳＴ：Ｐｏｗｅｒ　Ｏｎ　Ｓｅｌｆ　Ｔｅｓｔ）や、ハードウェア入出力用のプログラム・コード（ＢＩＯＳ：Ｂａｓｉｃ　Ｉｎｐｕｔ／Ｏｕｔｐｕｔ　Ｓｙｓｔｅｍ）などが書き込まれている。
【００４０】
ディスプレイ・コントローラ１０４は、ＣＰＵ１０１が発行する描画命令を実際に処理するための専用コントローラである。ディスプレイ・コントローラ１０３において処理された描画データは、例えばフレーム・バッファ（図示しない）に一旦書き込まれた後、ディスプレイ１１１によって画面出力される。
【００４１】
ディスプレイ１１１の表示画面は、一般に、ユーザからの入力内容やその処理結果、あるいはエラーその他のシステム・メッセージをユーザに視覚的にフィードバックする役割を持つ。また、本実施形態においては、ディスプレイ１１１の表示画面には、ソース・プログラムを編集するためのエディタ画面や、コンパイル処理中の基本ブロックやＤＡＧ、中間表現などの経過データ、オブジェクト・プログラム、オブジェクト・プログラムによる実行内容などを表示出力するために利用される。
【００４２】
入力機器インターフェース１０５は、キーボード１１２やマウス１１３などのユーザ入力機器を対話装置１００に接続するための装置である。
【００４３】
キーボード１１２やマウス１１３は、データやコマンドなどのユーザ入力をシステムに取り込む役割を持つ。本実施形態では、キーボード１１２やマウス１１３は、エディタの起動、エディタ画面でのソース・プログラムの入力・編集、コンパイラの起動、オブジェクト・プログラムの起動などをユーザが指示するために使用される。
【００４４】
ネットワーク・インターフェース１０６は、Ｅｔｈｅｒｎｅｔ（登録商標）などの所定の通信プロトコルに従って、システム１００をＬＡＮ（Ｌｏｃａｌ　Ａｒｅａ　Ｎｅｔｗｏｒｋ）などの局所的ネットワーク、さらにはインターネットのような広域ネットワークに接続することができる。
【００４５】
ネットワーク上では、複数のホスト端末（図示しない）がトランスペアレントな状態で接続され、分散コンピューティング環境が構築されている。ネットワーク上では、ソフトウェア・プログラムやデータ・コンテンツなどの配信サービスを行なうことができる。例えば、高級プログラミング言語を用いてソース・プログラムを作成・編集するためのエディタや、ソース・プログラムをオブジェクト・プログラムに変換するためのコンパイラ、コンパイラによって生成されたオブジェクト・プログラムなどを、ネットワーク経由でダウンロードすることができる。また、コンパイル前のソース・プログラムやコンパイル処理後のオブジェクト・プログラムなどを、ネットワーク経由で他のホスト装置との間で配信・配布することができる。
【００４６】
外部機器インターフェース１０７は、ハード・ディスク・ドライブ（ＨＤＤ）１１４やメディア・ドライブ１１５などの外部装置を本動作情報処理装置１００に接続するための装置である。
【００４７】
ＨＤＤ１１４は、記憶担体としての磁気ディスクを固定的に搭載した外部記憶装置であり（周知）、記憶容量やデータ転送速度などの点で他の外部記憶装置よりも優れている。ソフトウェア・プログラムを実行可能な状態でＨＤＤ１１４上に置くことを、プログラムのシステムへの「インストール」と呼ぶ。通常、ＨＤＤ１１４には、ＣＰＵ１０１が実行すべきオペレーティング・システムのプログラム・コードや、アプリケーション・プログラム、デバイス・ドライバなどが不揮発的に格納されている。例えば、高級プログラミング言語を用いてソース・プログラムを作成・編集するためのエディタや、ソース・プログラムをオブジェクト・プログラムに変換するためのコンパイラ、コンパイラによって生成されたオブジェクト・プログラムなどを、ＨＤＤ１１４上にインストールすることができる。また、編集中・コンパイル中のソース・プログラムや、コンパイラがソース・プログラムをコンパイル処理中に生成するソース・プログラムの中間表現（中間表現は、基本ブロックに分割されることもあり、また、基本ブロックは、ＤＡＧ（Ｄｉｒｅｃｔｅｄ　Ａｃｙｃｌｉｃ　Ｇｒａｐｈ）で表現されることもある）、コンパイル処理されたオブジェクト・プログラムなどをＨＤＤ１１４上に蓄積しておいてもよい。
【００４８】
メディア・ドライブ１１５は、ＣＤ（Ｃｏｍｐａｃｔ　Ｄｉｓｃ）やＭＯ（Ｍａｇｎｅｔｏ−Ｏｐｔｉｃａｌｄｉｓｃ）、ＤＶＤ（Ｄｉｇｉｔａｌ　Ｖｅｒｓａｔｉｌｅ　Ｄｉｓｃ）などの可搬型メディアを装填して、そのデータ記録面にアクセスするための装置である。
【００４９】
可搬型メディアは、主として、ソフトウェア・プログラムやデータ・ファイルなどをコンピュータ可読形式のデータとしてバックアップすることや、これらをシステム間で移動（すなわち販売・流通・配布を含む）する目的で使用される。例えば、高級プログラミング言語を用いてソース・プログラムを作成・編集するためのエディタや、ソース・プログラムをオブジェクト・プログラムに変換するためのコンパイラ、コンパイラによって生成されたオブジェクト・プログラムなどを、これら可搬型メディアを利用して複数の機器間で物理的に流通・配布することができる。また、編集中・コンパイル中のソース・プログラムや、コンパイラがソース・プログラムをコンパイル処理中に生成する中間表現、コンパイル処理されたオブジェクト・プログラムなどを他の装置との間で交換するために、可搬型メディアを利用することができる。
【００５０】
なお、図１に示すようなプログラム処理装置１００の一例は、米ＩＢＭ社のパーソナル・コンピュータ”ＰＣ／ＡＴ（Ｐｅｒｓｏｎａｌ　Ｃｏｍｐｕｔｅｒ／Ａｄｖａｎｃｅｄ　Ｔｅｃｈｎｏｌｏｇｙ）”の互換機又は後継機である。勿論、他のアーキテクチャで構成されるコンピュータを、本実施形態に係るプログラム処理装置１００として適用することも可能である。
【００５１】
Ｂ．基本演算
厳密な意味論が与えられている言語としては、高級言語においてＳｃｈｅｍａ（Ｗ．　Ｃｌｉｎｇｅｒ、Ｊ．　Ｒｅｅｓ（ｅｄｓ）共著”Ｒｅｖｉｓｅｄ　Ｒｅｐｏｒｔ　ｏｎ　Ｔｈｅ　Ａｌｇｏｒｉｔｈｍｉｃ　Ｌａｎｇｕａｇｅ　Ｓｃｈｅｍｅ”（１９９１）を参照のこと）やＭＬ（Ｍｉｌｉｎｇｅｒ，　Ｒ．、Ｔｏｆｔｅ，　Ｍ．、Ｈａｒｐｅｒ，　Ｒ．共著”Ｔｈｅ　Ｄｅｆｉｎｉｔｉｏｎ　ｏｆ　Ｓｔａｎｄａｒｄ　ＭＬ”（ＭＩＴ　Ｐｒｅｓｓ，　Ｃａｍｂｒｉｄｇｅ，　ＭＡ　１９９０）を参照のこと）、また、コンパイラの中間言語においてＳＭＬがある。しかし、いずれも加算や乗算といった基本命令の仕様を厳密には規定していない。コンパイラの最適化変換は書く演算が満たす代数的関係に基づいて行われるため、それら演算の仕様が厳密に定義され、それらが満たす代数的性質も明確でなければならない。例えば、以下のような最適化を行ってよいかどうかが、その中間言語の仕様から決定できなければならない。
【００５２】
【数１】
2004021441.tif 000003
【００５３】
Ｃ言語の仕様書（ＩＳＯ，　ＩＳＯ／ＩＥＣ　９８９９：１９９９　Ｐｒｏｇｒａｍｍｉｎｇ　ｌａｎｇｕａｇｅｓ　−　Ｃ，　１９９９）では、整数の表現が２の補数表示、１の補数表示、及び符号と絶対値のいずれの表現を持つマシンでも実装できるような配慮がなされている。逆に言えば、Ｃ言語の演算で成立する代数的性質を制限している。例えば、上の最適化を行なってよいかどうかはＣ言語の仕様書だけからは決定することができない（処理系依存）。
【００５４】
２の補数表現は数学的に最も優れた表現であり、１ワードの整数の集合は単位可換環をなす。よって、例えば上の最適化を行なうことができる。現在使用されているほとんどすべての計算機は２の補数表現を採用していることを考慮し、本発明者らの中間言語における整数は２の補数表現によるものとした。このように、ＬＩＲの設計においては現在使用されているハードウェア構成を考慮し、幾つかの特定の仮定を設けている。メモリについても、１バイトが８ビットでアルバイト・アドレス・マシンのみを前提としている。
【００５５】
高級言語の意味論ではデータのドメインはさまざまな型の直和で表現されるが、コンパイラの中間言語が表現するものは実際のハードウェアであり、本発明者らはタグ付きアーキテクチャのような特殊なものは対象外としている。したがって、データをあらわすドメインは単なるビット列とする。また、メモリでアドレス指定される最小単位のビット列としてバイトを定義する。
【００５６】
【数２】
2004021441.tif 000004
【００５７】
以下はビット列を数学的な数と解釈する関数である。自然数の集合Ｎは理想的な符号なし整数、整数の集合Ｚは理想的な符号付き整数、実数の集合Ｒは理想的な浮動小数と考えている。
【００５８】
【数３】
2004021441.tif 000005
【００５９】
ここで、ｚｂは２の補数表示を仮定した定義になっている。ｒｂ　ｂで、
【００６０】
【数４】
2004021441.tif 000006
【００６１】
がＩＥＥＥ解釈で実数とならない場合、
【００６２】
【数５】
2004021441.tif 000007
【００６３】
である。以下は数学的な数をビット列に変換する関数である。ｂｒもｒｂも同様部分関数であり、ｒｂｎｘでｘがＩＥＥＥ解釈のｎビット表現を持たない場合は、
【００６４】
【数６】
2004021441.tif 000008
【００６５】
である。
【００６６】
【数７】
2004021441.tif 000009
【００６７】
図２には、本実施形態に係る中間言語における２の補数表現の仕組みを図解している。
【００６８】
例えば、加算命令は変換関数と数学的な加算演算＋により、以下のように定義される。ここで、σはメモリ、ρは環境を表す。
【００６９】
【数８】
2004021441.tif 000010
【００７０】
先述したように、ｎビットの２の補数表現は数学的に言うとＺの剰余環として得られる単位可換環Ｚ／（２ｎ）の代数に対応した、理論的に正しい表現である。本明細書中では、ビット列
【００７１】
【数９】
2004021441.tif 000011
【００７２】
とＺ／（２ｎ）が一対一に対応する。その対応を与えるのがｎｂ，ｚｂ，ｂｚであり、ｂに対してｎｂ　ｂを要素とするＺ／（２ｎ）の剰余類が対応する。言い換えると、ｎｂ　ｂはその剰余類から代表元ｘを０≦ｘ＜２ｎの範囲で選ぶ関数に他ならない。ｚｂ　ｂも同様だが代表元ｘを−２ｎ−１≦ｘ＜２ｎ−１の範囲で選んでいる点が異なる。ｂｚは整数ｘに、それを要素とする剰余類を表すビット列を対応させている。これらの事実を関数の間に成り立つ定理として述べると、以下のようになる。
【００７３】
【数１０】
2004021441.tif 000012
【００７４】
ＬＩＲでは、整数演算でオーバーフローを無視している。その理由はまず第一に本発明で対象とする言語の中で、ＣとＪａｖａ（登録商標）はオーバーフローを無視している（直接書かれた定数についてはチェックしているが）という理由が挙げられる。第二に、オーバーフローを無視するＬＩＲの整数演算は２の補数表示により副作用を無視すれば単位可換環をなすが、オーバーフローを無視しないと、そういう数学的に奇麗な性質は成り立たなくなる。すなわち環の演算のみからなる式は数学的に許される自由な変形を行なっても意味は変わらない。したがって、もし「コンパイラは入力がオーバーフローや未定義値を発生させないと仮定し、その範囲で最適化変換を行なってよい」という前提が許されるならば、効率的な最適化を安心して行なうことが可能となる。この前提は、少なくとも本発明が対象とする言語では事実上認められていると思料される。
【００７５】
Ｃ．シフト演算
いくつかの現実的な仮定を置くことにより、本実施形態に係る中間言語ＬＩＲの命令は簡潔なものになったが、シフト演算についてはやや複雑な定義とせざるを得ない。例えば、左シフト命令ｘ＜＜ｎにおいて、ｎが負の場合、右シフトになるようなマシン（例えばＶＡＸなど）もあれば、そうならないマシン（例えばＳＰＡＲＣなど）もある。よって、Ｃ言語ではｎが負の場合の値は未定義と定めている。すなわち、ＶＡＸのシフト命令を仮定したようなＣのプログラムはポータブルではない。
【００７６】
実際には、そのようなプログラムを書くことは少ないかもしれないが、ｎがせいの場合でもＶＡＸでは１＜＜３２＝１となるので、ＶＡＸからＳＰＡＲＣへ移行した者は要注意である。ＳＰＡＲＣの左シフト命令はｎの下位５ビットのみを符号なし整数と解釈し、左シフトの量としているため、このような結果になる。
【００７７】
また、右シフト命令ｘ＞＞ｎには符号ビットをコピーする算術シフトとコピーしない論理シフトがあり、その区別も必要である。これらシフト命令のバリエーションを整理することにより、ＬＩＲのシフト命令は左シフトの算術版ＬＳＨＳと論理版ＬＳＨＵ、及び右シフトの算術版ＲＳＨＳと論理版ＲＳＨＵの４つとし、以下のような定義とした（ただし、算術左シフト）。
【００７８】
【数１１】
2004021441.tif 000013
【００７９】
記号＆はＬＩＲでは命令の修飾を表す記号であり、それに続くＳ式を「モディファイヤ」と言う。ｘ２の値とモディファイヤｍ＝（ｓｎｄ）に従い、以下のようにシフト・カウントが決まる。まず、ｘ２の値をｎビットの符号付き（ｓ＝Ｓ）、あるいは符号なし（ｓ＝Ｕ）整数と解釈し、仮のシフト・カウントとする。次に、ｘ２の値がそのｎビット符号付き（あるいは符号なし）数として表現できるならば仮のカウントを正式なシフト・カウントとする。そうでない場合、その挙動はｄに依存し、ｄ＝Ｄなら表現できなくてもその解釈された値をシフト・カウントとする。ｄ＝Ｕならシフト・カウントを⊥とし、シフト結果全体を⊥とする。
【００８０】
以下の表は、シフト・モディファイヤと対応するマシンの例である。
【００８１】
【表１】
2004021441.tif 000014
【００８２】
また、結果が未定義になる例として、Ｉｎｔｅｌ　ｘ８６のＳＨＬＤ、ＳＨＲＤで、８、１６ビット・レジスタをシフトするときで、シフト・カウントの下位５ビットが８，１６を越える場合が挙げられる。
【００８３】
Ｄ．ｖｏｌａｔｉｌｅオブジェクト
マシンはメモリを介して外部とのやり取りを行なう。したがって、そのポートとして使われる変数についての最適化は制限される。Ｃ言語ではそのような変数、一般的にはオブジェクトをｖｏｌａｔｉｌｅという一種の型により表現することができる。
【００８４】
本実施形態に係る中間言語ＬＩＲでは、＆　Ｖというモディファイヤを伴ったＭＥＭ式によりｖｏｌａｔｉｌｅオブジェクトを表す。この項では、ｖｏｌａｔｉｌｅオブジェクトの意味定義を解説し、またその定義が自然なものであることを示す。
【００８５】
Ｄ−１．ランダム・ステートによる意味付け
ここで、ｖ１、ｖ２が何らかの装置とのポートとして使われているｖｏｌａｔｉｌｅ変数と仮定し、どのような変換が許されないかを考察してみる。
【００８６】
まず、明らかに以下のような変換は禁止しなければならない。これは、パイプライン・スケジューラなどがやるような最適化変換である。
【００８７】
【数１２】
2004021441.tif 000015
【００８８】
以下も同様に禁止しなければならない。これは、ｄｅｃｏｄｅ　ｅｌｉｍｉｎａｔｉｏｎで行なわれるような最適化変換である。
【００８９】
【数１３】
2004021441.tif 000016
【００９０】
装置がｖｏｌａｔｉｌｅオブジェクトを読むことにより動作し、また外部からそこへ書き込まれる可能性もあるので、以下の変換も禁止される。これは共通部分式と式の簡略化で行なわれるような最適化変換である。
【００９１】
【数１４】
2004021441.tif 000017
【００９２】
よって、ｖｏｌａｔｉｌｅオブジェクトの意味としては、以上のような変換がその意味を変えてしまうような定義をしなければならない。そのために、意味定義におけるメモリには以下のような２つのフィールド、トレース及びランダム・ステートが存在し、トレースによりＲｕｌｅ１，２を、ランダム・ステートによりＲｕｌｅ３に反映させている。
【００９３】
【数１５】
2004021441.tif 000018
【００９４】
ここで、トレースはアクションのリストである。また、新たなランダム・ステートを求めるために関数ｒａｎｄｏｍがあるとする。
【００９５】
【数１６】
2004021441.tif 000019
【００９６】
【表２】
2004021441.tif 000020
【００９７】
そして、ｖｏｌａｔｉｌｅメモリの参照ではそのアドレスがトレースに記録され、値はランダム・ステートとなる。
【００９８】
【数１７】
2004021441.tif 000021
【００９９】
また、ｖｏｌａｔｉｌｅメモリへの書き込みではそのアドレスと値がトレースに記録される。
【０１００】
【数１８】
2004021441.tif 000022
【０１０１】
Ｄ−２．意味定義の妥当性
このトレースとランダム・ステートに基づいた意味定義は、上記のＲｕｌｅ１からＲｕｌｅ３にのみ基づいたものであり、その妥当性に疑問がある。何かｖｏｌａｔｉｌｅ変数のより自然なモデルからの裏付けがほしい。ＬＩＲの実行可能なプログラム（以下、「Ｌプログラム」とする）はｖｏｌａｔｉｌｅ変数をチャネルとして動作するプロセスとみなすことができる。ここでは、このような視点で本発明者らの意味定義の妥当性について考察する。
【０１０２】
はじめに、ｂｉｓｉｍｕｌａｔｉｏｎ（Ｒ．　Ｍｉｌｎｅｒ著”Ａ　Ｃａｌｃｕｌｕｓ　ｏｆ　Ｃｏｍｍｕｎｉｃａｔｉｎｇ　Ｓｙｓｔｅｍｓ”（ＬＮＣＳ　９２，　１９８０））に基づいたＬプログラムの等価性を定義する。その定式化は、ｃｏａｌｅｂｒａ（Ｊ．　Ｊ．　Ｍ．　Ｍ．　Ｒｕｔｔｅｎ著”Ｕｎｉｖｅｒｓａｌ　ｃｏａｌｇｅｂｒａ：　ａ　ｔｈｅｏｒｙ　ｏｆ　ｓｙｓｔｅｍｓ”（Ｔｈｅｏｒｅｔｉｃａｌ　Ｃｏｍｐｕｔｅｒ　Ｓｃｉｅｎｃｅ，　２４９：　３−８０，　２０００）），（Ｐ．　Ａｃｚｅｌ、Ｎ．　Ｍｅｎｄｌｅｒ共著”Ａ　ｆｉｎａｌ　ｃｏａｌｇｅｂｒａ　ｔｈｅｏｒｅｍ”（Ｉｎ　Ｐｒｏｃｅｅｄｉｎｇｓ　Ｃａｔｅｇｏｒｙ　Ｔｈｅｏｒｙ　ａｎｄ　Ｃｏｍｐｕｔｅｒ　Ｓｃｉｅｎｃｅ，　ＬＮＣＳ　３８９：３５７−３６５，　１９８９））で行なう。次に、本発明者らが与えた表示的意味、すなわちトレースとランダム・ステートに基づくｖｏｌａｔｉｌｅ変数の意味に従ったＬプログラムの第二の等価性を定義する。最初の等価性をｃｏａｌｇｅｂｒａ等価性、第二の等価性をトレース等価性と言う。そして、この２つの等価性は同等であることを証明する。
【０１０３】
まず、以下の議論で使用する概念を要約する。
【０１０４】
Ｆ：Ｃ→ＣをカテゴリＣ上のファンクタとするとき、Ｆ−ｃｏａｌｇｅｂｒａとはオブジェクトＳと射α：Ｓ→Ｆ（Ｓ）の組（Ｓ，α）から（Ｔ，β）へのＦ−ｈｏｍｏｍｏｒｐｈｉｓｍという（図２を参照のこと）。
【０１０５】
与えられたカテゴリＣとファンクタＦについて、Ｆ−ｃｏａｌｇｅｂｒａをオブジェクト、Ｆ−ｈｏｍｏｍｏｒｐｈｉｓｍを射とするカテゴリをＣＦで表す。このとき、ＣをＣＦのｕｎｄｅｒｌｙｉｎｇ　ｃａｔｅｇｏｒｙという。ＣＦにおいて以下の（Ｒ，γ）を（Ｓ，α）と（Ｔ，β）のＦ−ｂｉｓｉｍｕｌａｔｉｏｎという。また、このような（Ｒ，γ）が存在するとき、（Ｓ，α）と（Ｔ，β）はｂｉｓｉｍｉｌａｒであるという。
【０１０６】
【数１９】
2004021441.tif 000023
【０１０７】
以下の議論で、ｕｎｄｅｒｌｙｉｎｇ　ｃａｔｅｇｏｒｙはＳｅｔである。この場合、上の条件は図４に示す図式の可換性と同一である。ここに、
【０１０８】
【数２０】
2004021441.tif 000024
【０１０９】
Ｄ−３．ｃｏａｌｇｅｂｒａ等価性
ｃｏａｌｇｅｂｒａ等価性はＬプログラムのプロセスを以下に述べる方法でラベル付き遷移系とみなしたときのｂｉｓｉｍｉｌａｔｉｏｎ等価性である。
【０１１０】
本発明者らの意味定義におけるメモリσはプログラム・メモリとデータ・メモリを含んでいるので、σをプログラムとも呼ぶ。
【０１１１】
【数２１】
2004021441.tif 000025
【０１１２】
図５に示す遷移図におけるσｉはすべて同一のプログラムであり、遷移によってデータ・メモリのみが変化している。
【０１１３】
【数２２】
2004021441.tif 000026
【０１１４】
ラベルｖ：＝ｘはｖｏｌａｔｉｌｅ変数ｖへ値ｘほか着込むことによる遷移を意味する。ラベルｖ？ｘｉによる遷移の「直前」に起こると考える。また、以後の説明では、各ＬＩＲ命令（以下、「Ｌ式」とする）は高々１つのｖｏｌａｔｉｌｅアクセス（読み書き）を持つと仮定する。ＬＩＲでは部分式の評価順序が定められているので、これらの仮定は本質的な制限にはならない。
【０１１５】
Ｌプログラムを以上のようなラベル付き遷移系とみなすと、ｂｉｓｉｍｉｌａｔｉｏｎによりその自然な等価性が定義される。本発明者らは、この等価性をフォーマライズの容易さのためにｃｏａｌｇｅｂｒａにより表現する。上述したラベル付き遷移系をｃｏａｌｇｅｂｒａで表すために、ファンクタＦ、キャリアＸ、射α：Ｘ→Ｆ（Ｘ）を以下のように定義する。
【０１１６】
【数２３】
2004021441.tif 000027
【０１１７】
ここに、Ｖｏｌは、ｖｏｌａｔｉｌｅオブジェクトのアドレスの集合である。
【０１１８】
【数２４】
2004021441.tif 000028
【０１１９】
ファンクタＦは３つのファンクタの直和であり、その最初のものがｖ：＝ｘ、第二がｖ？ｘに、そして、⊥はｖｏｌａｔｉｌｅオブジェクトにアクセスしないまま動き続けるプロセスを意味する。ｃｏａｌｇｅｂｒａ等価性ではトレースとランダム・ステートは参照しないので、それらをＭｅｍから除いたものがキャリアＭｅｍｃである。ＳｃはＬＩＲの仕様で定義されている意味関数Ｓをトレースとランダム・ステートを無視するように修正したものである。それも除外している。αはこのＳｃによりｖｏｌａｔｉｌｅアクセス単位で以下のような実行をする。まずｖｏｌａｔｉｌｅアクセスの直前まで実行を進め、そのアクセスがｘをｖで示されるオブジェクトへ書き込む命令ならば、αは（ｖ，ｘ，σ’）を返す。
【０１２０】
【数２５】
2004021441.tif 000029
【０１２１】
ここに、σ’は書き込み後のメモリである。また、もしそのｖｏｌａｔｉｌｅアクセスがｖからの読み込みの場合は、（ｖ，ｆ：Ｂｉｔｓ→Ｍｅｍｃ）を返す。ここに、ｆｘｉは先のラベル付き遷移系において、ラベルｖ？ｘｉによる遷移先のαである。
【０１２２】
以上で、本発明者らはＬＩＲにおけるプログラム全体のｃｏａｌｇｅｂｒａを定義したことになる。とく指定のプログラムσのｃｏａｌｇｅｂｒａはその部分
【０１２３】
【数２６】
2004021441.tif 000030
【０１２４】
であり、そのキャリアは以下のように定義される。
【０１２５】
【数２７】
2004021441.tif 000031
【０１２６】
以上より、ｃｏａｌｇｅｂｒａ等価性を以下のように定義する。
【０１２７】
【数２８】
2004021441.tif 000032
【０１２８】
この等価性の定義は、ＯＳのように停止しないで動き続けるプログラムの透過性も含んだ自然なものである。一方、本発明者らが与えたＬＩＲの表示的意味では停止しないプログラムはすべて⊥という扱いになってしまう。しかし、プログラムがデイ視する場合には、これら２つの等価性は投下であることが示される。
【０１２９】
Ｄ−４．トレース等価性
はじめにＬＩＲの本来の意味論すなわちとレースとランダム・ステートに基づいたプログラムの等価性（トレース等価性）を定義する必要がある。そのために、プログラムはある特定のメイン関数から開始するものとする。まず、以下の定義を行なう。
【０１３０】
【数２９】
2004021441.tif 000033
【０１３１】
ここで、βはαと同様のｖｏｌａｔｉｌｅアクセス単位での実行関数であるが、これは本来のトレースとランダム・ステートを使った意味関数εとＳに基づくものである。関数ｔはプログラムτの全体の挙動としてのトレースを返す。引数ｒはτの実行におけるランダム・ステートの初期値である。関数ｃはプログラムτからランダム・ステートとトレースを無視（削除）するものである。
【０１３２】
プログラムτの挙動は乱数関数ｒａｎｄｏｍ及びランダム・ステートの初期値ｒで完全に決定される。
【０１３３】
【数３０】
2004021441.tif 000034
【０１３４】
しかし、ｒａｎｄｏｍの実現の仕方が高々加算であることから、ある特別なｒａｎｄｏｍ関数を固定し、可能なあらゆるランダム列を初期値の違いでのみ表現することは可能である。よって、以後プログラムの挙動は単に初期値ｒで完全に決定されるとして議論する。以下がトレース等価性の定義である。
【０１３５】
【数３１】
2004021441.tif 000035
【０１３６】
Ｄ−５．２つの等価性の同値性
以下の定理はｃｏａｌｇｅｂｒａ等価性とトレース透過性が同値であるということを意味する。証明はスケッチである。
【０１３７】
【数３２】
2004021441.tif 000036
【０１３８】
遷移関数の定義を公式には与えていないが、
【０１３９】
【数３３】
2004021441.tif 000037
【０１４０】
ならば、以下に示す２式が同じアクション、すなわちともに書き込み又は読み込みか⊥であることは明らかである。
【０１４１】
【数３４】
2004021441.tif 000038
【０１４２】
以下、Ｆの場合分けをして説明する。
【０１４３】
１．（Ｖｏｌ×Ｂｉｔｓ×（−））の場合：
図６を参照されたい。Ｒｃの定義より、あるτ１’、τ２’が存在して、σｉ＝ｃτｉ’（ｉ＝１，２）となる。いまの場合、τｉの選択は任意である。
【０１４４】
【数３５】
2004021441.tif 000039
【０１４５】
Ｒｔの定義より、τ１’、τ２’のアクションは等しい。
【０１４６】
例えばそれがｖ：＝ｘであれば、以下が成り立つ。
【０１４７】
【数３６】
2004021441.tif 000040
【０１４８】
すなわち、図６の下の左右は正しい。よって、
【０１４９】
【数３７】
2004021441.tif 000041
【０１５０】
であれば、γを図式とおりに定義できるが、上記の説明より（σ１’，σ２’）＝（ｃτ１”，ｃτ２”）であり、Ｒｔの定義から、以下が成立する。
【０１５１】
【数３８】
2004021441.tif 000042
【０１５２】
２．（Ｖｏｌ×Ｈｏｍ（Ｂｉｔｓ，−））の場合：
同様の議論により、図７で示されていることはほぼ明らかである。証明を完結するには、γの定義が必要である。もし任意のｘについて、
【０１５３】
【数３９】
2004021441.tif 000043
【０１５４】
であるならば、以下に示すようにしてγを定義することができる。
【０１５５】
【数４０】
2004021441.tif 000044
【０１５６】
そのようなｘを固定し、σｉ＝ｃτｉ’で且つ
【０１５７】
【数４１】
2004021441.tif 000045
【０１５８】
のアクションがｖ？ｘとなるようにτ１’、τ２’を選ぶ。
【０１５９】
【数４２】
2004021441.tif 000046
【０１６０】
これはＲｔの定義及び乱数の初期値のみですべての挙動が決定するという議論から可能である。よって、ｆｉｘ＝ｃτｉ”（ｉ＝１，２）、すなわち
【０１６１】
【数４３】
2004021441.tif 000047
【０１６２】
である。逆の証明、及び⊥の場合については説明を省略する。
【０１６３】
Ｅ．多値関数の導入
関数呼び出しはリターゲッタブル・コンパイラで問題になる部分の１つである。ターゲット・マシンを固定したとしてもなお、さまざまなコーリング・シーケンスがあり得る。引数の一部は通常レジスタに割り当てられるが、それは後にレジスタ・アロケータが自由に割り当ててよいものではなく、関数呼び出しの規約に従った割り当てをしなければならない。このような特殊な扱いが必要なレジスタをｐｒｅ−ａｌｌｏｃａｔｅｄレジスタという。
【０１６４】
このようないわゆる実際上の問題は標準的なコンパイラの参考文献では記述されていないが、実装上はきわめて重要で且つ難解な問題である。最近でも、ＭＬ−ＲＩＳＣプロジェクト（Ａ．　Ｖ．　Ａｈｏ、Ｒ．　Ｓｅｔｈｉ、Ｊ．　Ｄ．　Ｕｌｌｍａｎ共著”Ｃｏｍｐｉｌｅｒｓ：Ｐｒｉｎｃｉｐｌｅｓ，　Ｔｅｃｈｎｉｑｕｅｓ，　ａｎｄ　Ｔｏｏｌｓ”（Ａｄｄｉｓｏｎ−Ｗｅｓｌｅｙ，　１９８５））（Ａｎｄｒｅｗ　Ｗ．Ａｐｐｅｌ著”Ｃｏｍｐｉｌｅｒ　Ｉｍｐｌｅｍｅｎｔａｔｉｏｎｉｎ　ＭＬ”（Ｃａｍｂｒｉｄｇｅ　Ｕｎｉｖ．　Ｐｒｅｓｓ，　１９９８））（中田育男著「コンパイラの構成と最適化」（朝倉書店，１９９９））で１つの提案がなされている。彼らの方法はＳＳＡとの変換過程でｐｒｅ−ａｌｌｏｃａｔｅｄレジスタの処理をするものであり、ＳＳＡに特化されているし、また提案されている方法も複雑なので、本明細書中ではこれ以上言及しない。
【０１６５】
この項では、以下に示すＣコードを例とし、従来の代表的なアプローチと本発明に係るアプローチについて説明する。
【０１６６】
【数４４】
2004021441.tif 000048
【０１６７】
以下で使用する中間言語のシンタックスはＬＩＲのものも含めて説明のために簡素化したものである。ｖｎは仮想レジスタ、ｒｎは実レジスタを表すとし、引数はｒ０、ｒ１、返却値はｒ０に入るようなコーリング・コンベンションを仮定する。
【０１６８】
Ｅ−１．従来の代表的な方法
実際的でよくある方法は、コーリング・シーケンスを表す特殊な式を代入する方法である。
【０１６９】
【数４５】
2004021441.tif 000049
【０１７０】
ここで、ａｒｇ（ｉ）はｉ番目のｆの引数を表す特殊な式と考える。また、ｓｅｔａｒｇ（ｉ，ｖ）はｉ番目のｇの引数をセットする特殊な式である。ｒｅｔｕｒｎ　ｖはｆの返却値を表す。
【０１７１】
このアプローチの利点は、コード最適化の段階でｐｒｅ−ａｌｌｏｃａｔｅｄレジスタを注意することが不要であるという点である。実際、実レジスタは後にレジスタ・アロケータがそれぞれの特殊な式と、定められたコーリング・コンベンションに従って実レジスタを割り当てることになる。
【０１７２】
一方、このアプローチの欠点は、ａｒｇといった特殊な式に対して、コード最適化ルーチンは特別な注意を払わなければならないという点である。それは大したコストではないとも言えるが、よりよい表現があればそれに越したことはない。ある意味で、本発明者らのアプローチは、この多少厄介な部分を解決したものである。本発明者らのアプローチを紹介する前に、ＧＣＣの思い切った解決方法について説明する。
【０１７３】
Ｅ−２．ＧＣＣの方法
ＧＣＣは最初の中間言語（ＲＴＬ）生成時においてパターン・マッチングを行ない、ターゲット・マシン固有の表現を展開するという戦略を採用している。これは、リターゲッタブル・コンパイラの中でもＧＣＣ独自の戦略と言える（Ｒ．　Ｌｅｕｐｅｒｓ、Ｐ．　Ｍａｒｗｅｄｅｌ共著”Ｒｅｔａｒｇｅｔａｂｌｅ　Ｃｏｍｐｉｌｅｒ　Ｔｅｃｈｎｏｌｏｇｙ　ｆｏｒ　Ｅｍｂｅｄｄｅｄ　Ｓｙｓｔｅｍｓ　Ｔｏｏｌｓ　ａｎｄ　Ａｐｐｌｉｃａｔｉｏｎｓ”（Ｋｌｕｗｅｒ　Ａｃａｄｅｍｉｃ　Ｐｕｂｌｉｓｈｅｒｓ，　２００１））。
【０１７４】
ＧＣＣでは、したがって先のＣコードが最初にＲＴＬへと変換された時点でコーリング・コンベンションは完全に展開されている。
【０１７５】
【数４６】
2004021441.tif 000050
【０１７６】
ここに、ｃｌｏｂｂｅｒは関数呼び出し中に破壊されるレジスタを明示するための指定である。ｕｓｅはそのレジスタが使用されていることを明示する式である。このようにＲＴＬでは一般にｐｒｅ−ａｌｌｏｃａｔｅｄレジスタと仮想レジスタが混在している。フレーム・ポインタやスタック・ポインタもＲＴＬではｐｒｅ−ａｌｌｏｃａｔｅｄレジスタとして明示的に現れている。
【０１７７】
このアプローチの利点は明らかである。コード最適化はまさにマシン固有の表現を対象に動作するのだから、よりクォリティの高い最適化を行なうことが可能となる。明らかにこのアプローチでなければやりにくい最適化として、関数呼び出しが連続する場合にスタックのｐｏｐをまとめて行なうような最適化（ｄｅｆｅｒ　ｐｏｐ）が挙げられる。
【０１７８】
このアプローチの欠点もまた明らかであろう。ｐｒｅ−ａｌｌｏｃａｔｅｄレジスタを注意しなければならないというのは、コード最適化を複雑なものにしてしまう。また、ＲＴＬ最盛時に既にコーリング・コンベンションが展開されるということは、ＲＴＬベースでのインライン展開やｔａｉｌ　ｒｅｃｕｒｓｉｏｎの最適化を困難にする。実際、ＧＣＣではパーザのレベルでそのような最適化を行なっており、ＲＴＬが生成された以後はそういった最適化は行なわれない。
【０１７９】
Ｅ−３．ＬＩＲのアプローチ
最初のアプローチの問題点は、中間言語でも高級言語のように関数インターフェースを保持するようにすることで解決することができる。以下に示すＬＩＲコードは説明のためのシンタックスであり正式なものではない。ＬＩＲはコンパイラの中間言語であるが、以下のようなモジュールと関数インターフェースを持っている。
【０１８０】
【数４７】
2004021441.tif 000051
【０１８１】
このモジュールは１つのコンパイル単位となる。ｒｅｇ　ｖ０，ｖ１，ｖ２，ｖ３は、関数ｆのローカルな仮想レジスタである。ｐｒｏｌｏｇｕｅとｅｐｉｌｏｇｕｅはそれぞれ関数の始まりと終わりを示す。ｐｒｏｌｏｇｕｅの引数が関数の引数であり、ｅｐｉｌｏｇｕｅの引数が返却値である。ここで重要なのは、ｐｒｏｌｏｇｕｅやｅｐｉｌｏｇｕｅは式ではないということである。コード最適化ルーチンが扱う式の中には最初のアプローチにおけるａｒｇ（ｉ）やｒｅｔｕｒｎといった特殊な注意が必要となるものは存在しない。
【０１８２】
本発明に係るアプローチでは、ＧＣＣと異なりコード最適化の段階では一切ｐｒｅ−ａｌｌｏｃａｔｅｄレジスタが現れないようにしている。よって、確かにＧＣＣのｄｅｆｅｒ　ｐｏｐのような最適化はやりにくくなるが、一方でＬＩＲを対象としたコード最適化の１つとしてインライン展開、末尾再帰、部分評価などの最適化が可能になる。
【０１８３】
ＬＩＲではレジスタの表現自体に仮想レジスタと実レジスタの区別はない。その区別はスコープによってなされる。実レジスタとはグローバルなスコープで宣言されているレジスタとみなす。そして、レジスタ・アロケーションも含めて、コンパイラのすべての処理をプログラム変換として捉えている。レジスタ・アロケーションとは、ローカルなレジスタ（仮想レジスタ）をグローバルなものに等価に変換する処理と考える。先の例は、レジスタ・アロケーションの後、以下のように変換される。
【０１８４】
【数４８】
2004021441.tif 000052
【０１８５】
プログラム変換とはいうまでもなくプログラムの意味を変えない変換である。よって、コンパイラの処理をプログラム変換として定義するためには、プログラムすなわちＬＩＲの意味が明確に定義されている必要がある。
【０１８６】
ＧｌａｓｇｏｗのＨＡＳＫＥＬＬコンパイラはＧＮＵ　Ｃを「ターゲット・アセンブラ」としてきたが、別にＣ−−（ｓｉｍｏｎ　Ｐ．　Ｊｏｎｅｓ外著”Ｃ−−：　Ａ　Ｐｏｒｔａｂｌｅ　Ａｓｓｅｍｂｌｙ　Ｌａｎｇｕａｇｅ”（Ｉｍｐｌｅｍｅｎｔｉｎｇ　Ｆｕｎｃｔｉｏｎａｌ　Ｌａｎｇｕａｇｅｓ　１９９７，　ＬＮＣＳ，　１９９８））という中間コードも提案され、ＭＬ−ＲＩＳＣ（Ｌ．　Ｇｅｏｒｇｅ著”Ｃｕｓｔｏｍｉｚａｂｌｅ　ａｎｄＲｅｕｓａｂｌｅ　Ｃｏｄｅ　Ｇｅｎｅｒａｔｏｒｓ”（Ｔｅｃｈｎｉｃａｌ　ｒｅｐｏｒｔ，　Ｂｅｌｌ　Ｌａｂｏｒａｔｏｒｉｅｓ，　Ｍｕｒｒａｙ　Ｈｉｌｌ，　１９９７））を利用して実装されている。これはＣ言語をよりアセンブラに近付けるというアプローチであり、構造体型といった高級な型は排除されているが、代わりに多値関数が導入されている。その理由は、インライン展開や末尾再帰のための便宜である。すなわち、Ｃ言語から無駄を削って行ない、関数インターフェースが残る。本発明者らは、アセンブラ言語レベルの中間コードに構造を追加することで、やはり関数インターフェースを保持したほうがよいと思料する。
【０１８７】
Ｆ．例
この項では、中間言語ＬＩＲを簡単な例によって紹介し、ＬＩＲ全体構造について説明する。
【０１８８】
以下に示すコードは２つのソースｍａｉｎ．ｃとｓｕｂ．ｃからなるＣ言語プログラムであり、ｐｒｏｄｖはｆｏｌｄ１を利用して配列ｖの要素の積を計算する。
【０１８９】
【数４９】
2004021441.tif 000053
【０１９０】
ｍａｉｎ．ｃをＬＩＲに変換したものを以下に示す。
【０１９１】
【数５０】
2004021441.tif 000054
【０１９２】
ＬＩＲはＳ式で表現されており、セミコロンから行末まではコメントと扱う。ここで、整数、アドレス、浮動小数ともに３２ビットで、アラインメントの要求はすべて４バイト境界とする。また、コード、データの置かれるセグメント名はそれぞれｔｅｘｔ、ｄａｔａとする。
【０１９３】
これは、ＬＩＲのコンパイル単位であるＬモジュールの例である。Ｌモジュールはモジュール名（ここではソース・ファイルに基づいて付けた）、連想リスト、そして関数とデータの定義列から成り立つ。関数定義は、関数名、関数のローカルな連想リスト、そしてＬ式列と呼ばれる命令列から成り立つ。データの定義はデータ名とその内容からなり、内容は具体的な値の他に領域を確保する命令、境界制御命令も含む。
【０１９４】
連想リストの各エントリはその第一要素に依存する。エントリの第二要素がＳＴＡＴＩＣなら名前は静的なアドレス（最終的にリンカが解決する）を表す。例えば、Ｌモジュール“ｍａｉｎ”の第６行は“ｎ”が静的なアドレスを表し、さらにそこにはＩ３２という型（３２ビット整数）のオブジェクトが置かれており、境界の要求は４バイトでｄａｔａセグメントに割り当てられ、リンケージはローカル定義ＬＤＥＦすなわちモジュール外から参照できないことを意味する。リンケージには他に外部に対して定義することを意味するＸＤＥＦと、外部参照を意味するＸＲＥＦがある。
【０１９５】
第６行のｖの型は単なる９６とあるが、これは９６（＝３２×３）ビットのオブジェクトであることを意味する型である。他にＬＩＲは浮動小数用の型（例えば第１３行にあるＦ３２）もある。ＬＩＲの型システムはこのようにハードウェアが直接認識できるものとなっている。これをＬタイプと呼ぶ。コンパイル時のその実際の大きさがわからない場合はＵＮＫＮＯＷＮとしているが、これはＬタイプではない。
【０１９６】
第１０行は簡単な関数定義の例である。Ｌ式列の最初と最後の命令ＰＲＯＬＯＧＵＥ、ＥＰＩＬＯＧＵＥは関数としてのインターフェースを定義している。これは、実際のハードウェアでは通常存在しない命令であるが、ＬＩＲではこのようなインターフェースを付加することにより、コード最適化において幾つかの定理を提供している。ＬＩＲでは関数は多値関数であり、ＰＲＯＬＯＧＵＥの第三要素以降が値を受け取る変数の並び、ＥＰＩＬＯＧＵＥの第三要素以降が返される多値を表す式の並びである。
【０１９７】
ＰＲＯＬＯＧＵＥ、ＥＰＩＬＯＧＵＥのＬ式の第二要素（ｗｆｗｒ）はフレームのサイズを表す。最初のｗｆはフレームのサイズだが、次のｗｒはレジスタ・フレームのサイズである。
【０１９８】
関数定義中の連想リストのエントリ（例えば第１３行）は、その名前がフレーム中のオフセットを表すものであることを示すＦＲＡＭＥを第二要素として持つ。このエントリでは型、境界、フレーム中のオフセットが要素である。
【０１９９】
第１８行が典型的なＬ式である。対応するＣ言語のコードと比較されたい。まず、メモリの参照（読み書き）は明示的に（ＭＥＭ型アドレス）というＬ式で表されている点がＣ言語と相違する。型はそのメモリ参照が表すオブジェクトの型である。そして、例えば第１３行で定義されている”ｘ”は、フレームに割り当てられた変数のアドレスを表すＬ式（フレーム式）により（ＦＲＡＭＥ　Ｉ３２　”ｘ”）と表される。ここで、Ｉ３２は、このＬ式の型すなわちアドレスの型である。
【０２００】
フレーム・ポインタは様に現れていない。これによりコード最適化フェーズでの処理が容易となる。しかし、ＬＩＲにはフレーム・ポインタも存在し、フレーム式の意味定義ではそれが参照されている。
【０２０１】
第３０行がＬＩＲの関数呼出し命令であり、多値を返すために（ＣＡＬＬ　関数アドレス　（引数…））（結果を入れる変数…）というシンタックスとなっている。
【０２０２】
関数呼び出しは他の命令の部分にはなれない。よって、ｔ１という一時変数が導入されている。
【０２０３】
第３１行の（ＭＥＭ　Ｉ３２　（ＳＴＡＴＩＣ　Ｉ３２　“ｎ”））はグローバル変数の参照例であり、第７行で宣言された“ｎ”がスタティックなアドレスを表すＬ式により（ＳＴＡＴＩＣ　Ｉ３２　“ｎ”）と表されている。
【０２０４】
［数５０］に示す例でかけている重要なものにレジスタがある。ＬＩＲのレジスタは、（ＲＥＧ型　“ｒｅｇｎａｍｅ”）というシンタックスで表され、“ｒｅｇｎａｍｅ”は連想リストにおいては（“ｒｅｇｎａｍｅ”　ＲＥＧ型　オフセット）というエントリで表される。レジスタの名前が表すものはそれが保持するオブジェクトであり、レジスタのアドレスではない。そもそもレジスタのアドレスと言うものは通常存在しないが、ＬＩＲではレジスタ・メモリというものを仮定し、各レジスタはそのメモリ中に置かれるとして扱う。上記のレジスタのエントリにおけるオフセットとは、そのレジスタのアドレスを決定するのに使われる。先述したレジスタ・フレームのサイズｗｒもまたそのアドレスの決定に使われる。
【０２０５】
ｓｕｂ．ｃに対応するＬＩＲコード（Ｌモジュール）を以下に示す。
【０２０６】
【数５１】
2004021441.tif 000055
【０２０７】
この関数定義は制御構造を含む例である。いわゆる構造化プログラミング向けの高級な制御構造は提供せず、代わりに幾つかの条件分岐命令を提供する。（ＤＥＦＬＡＢＥＬ　“ラベル”）によりラベルを定義し、参照は（ＬＡＢＥＬ　型“ラベル”）で行なう。この方はコードのアドレスを表す整数の適当な型である。ＪＵＭＰは無条件分岐、ＪＵＭＰＣは条件分岐である。他にＪＵＭＰＮという他方項分岐命令もある。
【０２０８】
ラベルのスコープは関数内であり、関数の外のラベルへ分岐することはできない。無論、ラベル名は最終的に生成されるアセンブラ言語にそのまま使われるなら、アセンブラでは関数ローカルなラベルというものは存在しないので、適当なリネーム処理が必要とされる。しかし、ＬＩＲの言語仕様上はあくまでラベルのスコープは関数内と定める。
【０２０９】
第２２行は関数の間接呼び出しの例にもなっている。少なくともＣ言語を表現する必要上、間接呼び出しは必要であり、ＣＡＬＬ式の第一引数はしたがって関数のアドレスを表す任意の式が書けるようになっている。しかし、ＬＩＲのモデルではこの計算されたアドレスは必ずＬＩＲで書かれた関数であると考える。
【０２１０】
［追補］
以上、特定の実施形態を参照しながら、本発明について詳解してきた。しかしながら、本発明の要旨を逸脱しない範囲で当業者が該実施形態の修正や代用を成し得ることは自明である。すなわち、例示という形態で本発明を開示してきたのであり、本明細書の記載内容を限定的に解釈するべきではない。本発明の要旨を判断するためには、冒頭に記載した特許請求の範囲の欄を参酌すべきである。
【０２１１】
【発明の効果】
以上詳記したように、本発明によれば、高級プログラミング言語形式で記述されたソース・プログラムをターゲット・マシン上での演算と振る舞いが相違しないように中間表現に変換して処理することができる、優れたプログラム処理装置及びプログラム処理方法、並びにコンピュータ・プログラムを提供することができる。
【０２１２】
また、本発明によれば、高級プログラミング言語形式で記述されたソース・プログラムにおける命令の意味を厳密に定義した中間表現に変換してターゲット・マシン上での正確な演算と振る舞いを実現することができる、優れたプログラム処理装置及びプログラム処理方法、並びにコンピュータ・プログラムを提供することができる。
【０２１３】
本発明は、実用規模のコンパイラ中間言語ＬＩＲを設計し、従来はあまり試みられなかった厳密な仕様記述を与えるものである。また、ｖｏｌａｔｉｌｅオブジェクトの表示的意味を与え、その妥当性を示すものである。本発明によってもたらされる中間言語ＬＩＲは、現在成功しているリターゲッタブル・コンパイラの中間言語、特にＧＣＣのＲＴＬに対して幾つかの試みを付加している。
【図面の簡単な説明】
【図１】本実施形態に係るプログラム処理装置１００のハードウェア構成を模式的に示した図である。
【図２】本実施形態に係る中間言語における２の補数表現の仕組みを模式的に示した図である。
【図３】ＬＩＲの実行可能なプログラムの等価性を説明するための図である。
【図４】意味定義の妥当性を説明するための図である。
【図５】ｃｏａｌｇｅｂｒａ等価性を説明するための図である。
【図６】２つの等価性の同値性を説明するための図である。
【図７】２つの等価性の同値性を説明するための図である。
【符号の説明】
１００…プログラム処理装置
１０１…ＣＰＵ，
１０２…主メモリ，１０３…ＲＯＭ
１０４…ディスプレイ・コントローラ
１０５…入力機器インターフェース
１０６…ネットワーク・インターフェース
１０７…外部機器インターフェース
１０８…バス
１１１…ディスプレイ
１１２…キーボード，１１３…マウス
１１４…ハード・ディスク装置
１１５…メディア・ドライブ
【図１】
2004021441.tif 000056
【図２】
2004021441.tif 000057
【図３】
2004021441.tif 000058
【図４】
2004021441.tif 000059
【図５】
2004021441.tif 000060
【図６】
2004021441.tif 000061
【図７】
2004021441.tif 000062