リターゲッタブルなコンパイラとは、さまざまな言語に対してさまざまなターゲットマシンのコードを生成することが可能なコンパイラである。リターゲッタブルなコンパイラを実現するためには、コンパイラを構成する数多くのモジュールの独立性を高め、特定の言語やターゲットマシンに依存したモジュールを、他の言語やターゲットマシンのためのモジュールに自由に入れ換えられなければならない。また、言語やターゲットマシンに依存しない部分は汎用のモジュールとして実現できなければならない。特に、コンパイラのバックエンドはさまざまな最適化モジュールから成り、ターゲットマシンに依存した処理も多く、コンパイラのフロントエンドに比べて高いモジュール性を得ることは難しい。

　本研究は、リターゲッタブルなコンパイラのバックエンドのモジュール性を高め、そのコード生成系の生産性を向上させるとともに、コード生成技術の適用範囲を広げることを目的としている。コード生成系のモジュール性を高めるために、特に中間言語の設計が重要である。本研究では、まず最初に、リターゲッタブルなコンパイラのバックエンドで共通に使うことができる汎用的な中間言語LIRの設計とそのコード生成系の実装を行った。このような中間言語の設計には次の三つの基準が重要であると考える。まず、さまざまなターゲットマシンの命令を表現できる柔軟さが必要である。そしてその表現力を失わない範囲で可能な限り単純でなければならない。最後に、その中間言語の意味は信頼性の高い実装のために明確に定義されているべきである。

　LIRは単なる中間言語としてではなく、独立したプログラミング言語として設計されており、上記の三つの基準を満たしている。LIRは、リターゲッタブルコンパイラを開発するCOINS(Compiler INfraStructure)プロジェクトの中間言語として設計され、実際にCOINSコンパイラにおいて現在も広く使われており、様々な最適化モジュールを自由に組み合わせる基盤となっている。また、そのコード生成系TMDは、GCC風の簡潔なマシン記述をDPマッチングのための書き換え規則に変換する、という方法により、GCCとBurg系コンパイラの両者の良い点を取り入れて実装された。TMDは簡潔なマシン記述を可能とし、理論的に最適なコード選択を行う。実際にSPARC及びX86を記述し性能を評価した結果、GCCやBurg系の記述と比較してTMDの記述はより簡潔であり、COINSコンパイラ全体としてGCCに劣らないコードを出力する。

　本論文の第3章から第5章までにおいて、LIRの特徴的な部分に加え、TMDの設計と実装について述べる。

　LIRはコンパイラのバックエンドに共通に使える中間言語として設計されたが、命令選択以後のレジスタアロケーションや命令スケジューリングにおいては、このような中間言語は過剰に具象的であり、中間言語のプログラムは余分な情報を多く含んでいる。これは、命令選択以後のモジュールが、プログラムの意味にほとんど依存せずに、主として、リソース割り当てと命令スケジューリングを行っているためである。

　よって、本研究では、命令選択以後の処理に適した中間言語を設計することにより、命令選択以後のモジュールの汎用性と独立性を高めることを試みた。実際に、リソース割り当てと命令スケジューリングのための中間言語ASL(Allocation and Scheduling Language)の設計を行い、そのコード生成系を実装した。レジスタアロケーションと命令スケジューリングの最適化は互いに排他的であり、この最適化問題はNP−HARDであることが知られているが、本研究では最適解を得るために整数線形計画法に基づく手法を利用した。

　ASLはリソース割り当てと命令スケジューリングにとって適切な抽象度で設計されているため、通常のCPU以外にも、同様の問題を含む幅広い分野に適用可能である。実際に本研究では、DNA実験のために作られたロボットに対する最適なコード生成に応用することができた。このことから、命令選択以後に中間言語を適切な抽象度のものに切り替え、レジスタアロケーション以降のモジュールを独立することで、リターゲッタブルコンパイラの適応範囲を広げられるということが示された。

　本論文の第6章において、ASLとそのコード生成系について述べる。第7章において、DNA実験ロボットへの応用について述べる。

　本論文は9章からなる。第1章はリターゲッタブルコード生成系の概説、及びその中間言語に関する設計思想が述べられている。中間言語はまず、さまざまなターゲットマシンの命令を表現できる柔軟さが必要であり、そしてその表現力を失わない範囲で可能な限り単純でなければならず、その中間言語の意味は信頼性の高い実装のために明確に定義されているべきであると主張している。また、そのような中間言語に基づいてモジュール性を高く設計されたコード生成系は、通常のコンパイラとは異なる問題にも適用可能であると主張している。そして第2章から5章では論文提出者の参加したCOINSプロジェクトにおいて上記の設計思想に基づいて設計された中間言語LIR及びコード生成系TMDの評価と議論がなされている。第6章ではコンパイラの命令選択以後の中間言語を適切な抽象度で設計し直し、そこで行われる最適化のモジュールの独立性を高めることで、リターゲッタブルコンパイラの適用範囲を広げられるという考察の下で、ASLという中間言語とそのコード生成系の実装を述べている。またASLが実際に従来のコンパイラでは扱えなかった問題へ適用可能であることを示すために、第7章ではDNA実験ロボットANP-96の制御プログラムの最適化への適用例を取り上げている。

　中間言語LIRは単なる中間言語としてではなく、独立したプログラミング言語として設計されており、上記の三つの基準を満たしている。この中間言語はCOINSコンパイラの高い信頼性とコード最適化の実装のしやすさに貢献している。また、リターゲッタブルコード生成系TMDは、GCC風の簡潔なマシン記述をDPマッチングのための書き換え規則に変換する、という方法により、GCCとBurg系コンパイラの両者の良い点を取り入れて実装されており、簡潔なマシン記述を可能とし、理論的に最適なコード選択を行うことを可能とした。実際にSPARC及びX86を記述し性能を評価した結果、GCCやBurg系の記述と比較してTMDの記述はより簡潔であり、COINSコンパイラ全体としてGCCに劣らないコードを出力する。

　命令選択以後のモジュールの汎用性と独立性を高めることを試みでは、リソース割り当てと命令スケジュールリングのための中間言語ASL(Allocation and Scheduling Language)の設計を行い、そのコード生成系を実装している。レジスタアロケーションと命令スケジューリングの最適化は互いに排他的であり、この最適化問題はNP-HARDであることが知られているが、本研究では最適解を得るために整数線形計画法に基づく手法を利用した。そしてASLの適用可能性を示すために、DNA実験のために作られたロボットに対する最適なコード生成への応用が述べられており、これらの結論として、命令選択以後に中間言語を適切な抽象度のものに切り替え、レジスタアロケーション以降のモジュールを独立にすることで、リターゲッタブルコンパイラの適応範囲を広げられるということが示されている。

　本研究は、萩谷昌己、中田育男との共同研究であるが、論文提出者が主体となった研究であり、論文提出者の寄与が十分であると判断する。

　よって本論文は博士(情報理工学)の学位請求論文として合格と認められる。