マルチプロセッサアーキテクチャの発展によりアプリケーションの自動並列化が重要になってきた。一方、オブジェクト指向(00)技術の広まりにより、データ抽象化や拡張性などの点で優れたプログラミングが良く用いられる所となっている。このパラダイムは、メッセージ通信を利用するプログラミング方法論である。

　本論分では、メソッドレベルの自動並列化方式を提案するとともにその絶対並列性がどれほど得られるかを考察する。起動境界を超えた分析結果を生みだせる最適化ツールのデザインと統合はコンパイラ工学分野における興味深い挑戦である。

　この研究では広い意味で00技術に関する問題を記述し、最適化及び並列化技術の詳細を論じる。研究の焦点はJavaアプリケーションの静的解析のため開発したフレームワークにあるが、またそれは自動並列化処理を目指したプロジェクトの一部でもある。特に、この論文は一組のベンチマークの実験を通して、(1)タイプ推論、(2)エイリアス分析、および(3)それらの量的評価のためのテクニックに焦点を合わせる。

　学術的にもビジネス的にもJavaに対する興味がますます増大している。コードの携帯性はこの言語の最も特徴的なポイントの1つであり、それはJVM(Java Virtual Machine)によるJavaバイトコードの解釈により実現されている。欠点としては、ネイティブコードを使うのと比べて、プログラム実行がかなり遅い場合があることである。一般に提案されている解決策はJIT(Just-In Time)ホットスポット技術を用いるか、ネイティブコードへのコンパイルを利用することである。両方のアプローチは、しかしながら、固有の限界を持っている。我々の新しいアプローチは、並列処理を目指して、静的解析により、マルチスレッド化プログラムに元のプログラムを変換することである。このような戦略は従来主流となっているアプローチの限界を克服する代替手段として興味深い。

　我々が開発したコンパイラシステムの中では、分析されるプログラムをAT(Application Taxonomy)を通して表現する。入力データに基づき、実行パスは多数のクラスを利用したり生成したりする。ATはコントロールフロー性的に解析して必要な参照タイプを集め、Javaの継承メカニズムに基づくAT要素を用いて一部の順序関係を定義する。

　アナライザは、実行時のインスタンスになるクラスを推論する。ATを定義した後、最適化のため、実体クラスとそのアプリケーションであるLCS(Living Classes Set)の概念を述べる。LCSを計算するためFixed-pointアルゴリズムを提案する。

　LCSは、アプリケーション実行パスが生成するクラスに一致したATのクラスノードの集合として定義される。クラスCが示されるアプリケーションに実行パスがない時のみ、CはLCSから除かれる。特に、LCA(Living Classes Analysis)に基づいて、Javaアプリケーションにタイプ推論アルゴリズムを適用するにはATとLCSが重要である。LCAは、静的な分析を向上させるためにアプリケーションで示されるATクラスの情報を使う。

　type(.)をプログラム表現に関連した単一の静的タイプを返す関数とする。また、全ATノードnをATサブツリーのクラスノードセットに写像する関数SubTreeClasses(.)を定義する。アプリケーション中の参照タイプとATノード間では一対一の写像 が存在する。従って、SubTreeClasses(.)は各参照タイプtを、サブクラスtを持つ全クラスセットsに写像する関数である。よって表現exprが静的参照タイプt＝type(expr)を持つならば、実行時においてexprはSubTreeClasses((t))のクラス例となる。

　さらに、タイプ情報の精度を向上するため、LCSを用いて次の関数を定義する。

　LCAタイプ推論ではJava言語に特定の意味特徴を記述する。そして実験が示すように、よい結果が得られでいる。すなわち、異なる状況において00パラダイム(特にJava言語)に固有の特定要素を利用する。特に内部進行分析の問題に関しては、JVMを利用してコードの携帯性を保証するJava実行モデルを利用する。Javaバイトコードの特徴からJavaアプリケーションを分析でき、またサードパーティーのクラスライブラリに利用できる。ライブラリの使用はソフトウエア開発ではありふれたことであるが、コンパイル言語(例えばC、C++)の場合にソースレベルの内部進行を分析することは、ライブラリのメソッド実行中において一般的に最悪のケースであるといえる。一方、我々のフレームワークでは、サードパーティーのJavaクラスライブラリは最適化の過程にも関わっている。よって、最適化アルゴリズムとソフトウエアアーキテクチャの特性との内部関係をよりよく理解できる。非常に複雑で特徴付けるのがかなり難しい場合に、クラスライブラリとアプリケーションコード間の相互関係を調べることは非常に有効である.

　次にエイリアス衝突問題について述べる。エイリアシングはJavaアプリケーションの並列処理化に関連した問題である。Javaはポインタ演算を許さない(例えばC言語では利用可能である)。しかし、Javaはほぼ純粋な00言語である:すなわちJavaの実体は、ほぼオブジェクトである。唯一の例外は原始タイプ(integer、booleans等)であり、対応するラッパーオブジェクトが提供される。Javaのオブジェクトはポインタを通してアクセスされるため、エイリアス衝突が容易に起こり、内部進行及び依存関係を分析するときに特に注意する必要がある。アナライザはタイプベースのエイリアス分析(TBAA)を中心としたオリジナルのアプローチを取る。TBAAは多くの統合アルゴリズムへの興味深く有望な代替手段である。それらの統合アルゴリズムは一般にメモリベースもしくはインストラクションベースのエイリアスモデルを取扱う。TBAAは現代のプログラミング言語の静的タイプシステムを対象にし、単一プロセッサ計算機上の低レベル最適化(例えばRedundant Load Elimination)のみが実装されている。本研究の特徴は、1.)ハイレベル最適化を目指したTBAAの有効な利用2.)LCAタイプ推論で得たタイプ情報を用いた新しいアルゴリズム開発によるTBAAの能力向上、の2点である。このため、新たなエイリアス分析方法論LCA-TBAAを開発した。

　LCA-TBAAはプログラム表現に基づいた静的タイプ情報を利用する。exprl、expr2をそれぞれ、タイプtl＝type(expr2).タイプt2＝type(expr2)の表現とする。LCA-TBAAは関連クラスのデータ構造定義と共に、(t1)及び(t2)内のATサブツリーの位相的な構造を分析する。多角的に両立したデータデータメンバがなければ、expr1とexpr2の間にはどのようなエイリアス関係も起こり得ない。

　静的アナライザのモジュールデザインは顕著な特性を示している。すなわち、タイプ推論モジュールとエイリアスモジュール間が非常に緊密に統合されている。このようなデザインにした理由は、第一番目のモジュール改良によって2番目のモジュールの高いパフォーマンスが同様に得られることを保証するためである。エイリアシングへの伝統的アプローチを捨てることはそのような目標を達成するために重要な要素である。

　次いで本論文では、実世界Javaアプリケーションのベンチマークの一組にアクセスする実験を通してLCAとLCA-TBAAの影響力を考察する。ベンチマークの選択はデリケートなタスクであるが、これはJavaコミュニティに広く受け入れられるべき標準プログラムの不足のためである。このことは一方でJava APIが記述する広範なプログラミング状況に対して、言語が相対的に新規であるから当然であるといえる。本実験では、アプリケーション分野において多様で複雑な、いくつかのJavaベンチマークを選んだ。

　LCAは、グラフ呼び出し構造を最適化するのに使われる。いくつかのグラフ呼び出し構造技術は内部進行データフロー分析を利用する。開発されたアナライザはその代わりにLCAタイプ推論の可能性と利便性を調べるものである。データフロー解析に比べ、LCAは簡便性の利点を持ち、グラフ呼び出しの最適化において効果的である。得られた結果はLCAがアプリケーションのグラフ呼び出しにおいて多数のメソッド(コンストラクタ)を削減できたことを示している。付け加えて、LCAの有効性は、呼び出しサイトの通信におけるメソッド発信の遅い結合を排除することにおいて有効である。次にLCA-TBAAの実験について考える。ベンチマークのグラフ呼び出しにおいて、LCA-TBAAを通じグローバルエイリアス解析を実行する。そして静的に潜在的なエイリアスのあいまいさを大部分除く。この状況で、コンパイラ最適化の内部依存関連の結果が記述される。すなわち本実験では、グローバルな最適化プロセスにおいて、ソフトウェア構造、LCAタイプ推論、グラフ呼び出しの最適化、LCA-TBAAの間の相互作用を測る。

　コンパイラ最適化デザインとその開発においては、簡便で秩序だった変換を考案する必要がある。それは変換中に存在する複雑な相互関係のためである。確かな最適化の可能性と有効性は、簡便な方法で入力プログラムを変換した後のみ現れる。従来の最適化のおいて、コンパイラ技術者がせねばならない選択を容易にする為にガイドラインを利用できる。しかしながら我々が興味を持つ従来にない最適化において、プログラム変換の秩序化はまだ非常にアクティヴで重要な研究分野であり、それは紀合的な最適化の効果に大きなインパクトを与える。本研究が貢献した点の一つに、このような重要分野を明らかにしたことがあげられる。特に、開発したアルゴリズムがどのように相互影響するかを直接実験で効果的に示している。さらに詳細に示すと、我々は静的な最適化の状況におけるタイプ推論とエイリアス分析の互いの影響を調査した。エイリアス分析に対してタイプ情報に基づいた独特のアプローチを取ったため、ベンチマークから得られる数字の結果は非常に有用である。そして提案手法である、タイプ情報とグラフ呼び出し最適化の連帯利用によって、得られた静的情報の質を大幅に向上することができたことを示した。

　本論文は、「A Type-Based Static Analysis Framework for Java Applications(Javaフログラムに対するタイプベースド静的解析フレームワークの研究)」と題し、英語で書かれ8章と付録からなる。Javaで書かれたプログラムは、異なるコンピュータの間で容易に移行できる特徴を有し、分散処理のベース言語として期待されているが、その実行効率は余り高くないので処理の高速化の工夫が必要となる。本論文は、Javaで書かれたプログラムを並列化し、高速に実行するためのキー技術である静的解析の手法を論じたものである。

　第1章「Introduction」は、本研究の背景と目的、並びに本論文の構成をまとめたものである。

　第2章「The Optimization Process」は、コンパイラの技術について概観し、コンパイラを設計する場合の要点をまとめるとともに、幾つかの主要なコンパイラで採用されている手法を概観している。

　第3章「The Application Taxonomy」は、静的解析の最初に行なう仕事である、応用実行時に関与する可能性のある全クラスATを抽出する作業について述べている。まず、Javaタイプシステムに適用されるスコープルールについて触れ、次にネームの衝突を避けるためのネームマングリングを述べ、用いたデータ構造の説明を行ない、最後に参照タイプの抽出アルゴリズムを与えている。

　第4章「Type Inference」は、実行時に式がインスタンスとなるそのクラスセットをできるだけ小さくするアルゴリズムについて述べたものである。オブジェクト指向言語では、メリッドオーバローディング、ボリモーフィズム、ダイナミックメソッドディスバッチなどによりプログラムの再利用性が高まるが、そのために、通常の静的解析によるタイプ情報だけでは不十分で、より詳しい解析が必要となる。本章ではまず、応用プログラム内で実行時にインスタンシエートされるオブジェクトを解析することにより、式がインスタンスとなるそのクラス(Living Classes:LC)の概念を新たに導入し、それを集めた集合LCSを生成するアルゴリズムを与えている。このアルゴリズムは、言語がJavaであることから、バイトコードを用いた実行モデルを利用して、非常にコンパクトで且つ、精密な解析が可能となっている。次に、応用のコールグラフの最適化アルゴリズムCGOを与え、それにLCSの結果を適用することを提案している。更に、ベンチマークとして、幾つかのJavaプログラムを用いてこれらのアルゴリズムの実験を行ない、ここで与えたアルゴリズムが有効であることを示している。

　第5章「Type-Based Alias Analysis」は、並列化のための手続き間解析をする上で大きな問題とたるエイリアス解析について、非常に詳しい解析が可能た、タイプ情報の利用に基づく新たな手法TBAAを提案したものである。前章で用いたものと同じベンチマーク用いての実験をおこない、これまでに与えた3つのアルゴリズム、CGO、LCA、TBAAを種々に組み合わせることによる効果を明らかにしている。

　第6章は、「Interprocedural Analysis for Parallelization」で、前章までに開発してきたアルゴリズムを、プログラムの自動並列化における主要な二つの問題、手続き間解析と依存性解析に適用する手法を考察したものである。まず、従来までに研究されてきた並列化手法を概観するとともに、まだ未解決の問題をまとめ、次に、本論文で提案した手法について詳述し、その実装法を考察している。本手法は、メソッド起動状況を考慮に入れるとともに、メソッド境界を越えた静的解析であるので、命令ベースの従来手法よりもプログラム依存性がより精密に分析可能である。また、マルチプロセッサシステムの上にJavaマルチスレッドを載せることを想定しているので、CORBAとRMIを利用する従来の分散処理向きの実装よりも並列粒度が小さくて良いという特徴を有する。すべてを組み込んだ完全な実装は今後の問題であるが、予備的なプロトタイプ実装の実験では、エイリアス解析をより深く行なうことにより、より並列性の改善がみられ、本論文で提案しているような深い解析を用いた並列性抽出の有効性が間接的ながら示されている。

　第7章は、「Ana1yser Implementation」で、実装を行なった静的解析プログラム部分について述べている。すなわち、パーシング、意味解析、LCAタイプ推論とコールグラフ構成、LCA-TBAAグローバルエイリアス解析の4バスからなるソフトウエアであり、これらは、Javaのパッケージとして実装されている。

　第8章「Concluding Remarks」は結論であり、成果をまとめるとともに、今後の課題を述べている。

　論文の最後には「Appendix」が付けられ、各Javaクラスやインタフェースに関係する抽象シンタックスツリーを定義する為に開発した文脈自由文法を示すとともに、用いたツールなどについてまとめている。

　以上これを要するに、本論文は、Javaプログラムを自動的に並列スレッドプログラムに変換するコンパイラ技術の中核をなす、非常に精密な静的解析手法を提案し実装したもので、今後の並列オブジェクト指向言語の処理技術に与える影響が大きく、情報工学上貢献する所少なくない。

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