最適化コンパイラが高速なコードを生成するためには、プログラムの意味を変えない範囲で実行命令数を削減することが重要である。そのためには、コンパイラはプログラム中に多数存在する冗長な算術命令、メモリアクセス命令、例外チェック命令を除去する必要がある。しかし、既存の冗長性除去の手法はプログラム中に存在する3種の依存関係、すなわちデータ、制御、および例外依存関係により制約を受けるため、解析時間と増加と最適化能力の制限という欠点を持つ。

　我々はデータ、制御、および例外依存関係による制約を越える、高速かつ強力な冗長性除去の手法を提案する。我々はまず、データ依存関係と制御依存関係を越えるためにPartial Value Number Redundancy Elimination (PVNRE) と呼ぶ手法を提案する。PVNRE はデータフロー解析において値番号を用いることでデータ依存関係による制約を受けない。また、制御フローの合流点において値番号を動的に変換することで制御依存関係を扱うことができる。

　我々はさらに、例外依存関係を越えるためにSentinel PRE (Partial Redundancy Elimination) と呼ぶ手法を提案する。既存手法では、プログラムの意味を保つために例外依存を越えて例外チェック命令を冗長性除去できない。一方、Sentinel PRE は例外依存を無視して冗長性除去を行い、プログラムの意味を保つために実行時の逆最適化を用いることで例外依存関係を克服する。

　我々は PVNRE と Sentinel PRE を組み合わせた冗長性除去の手法をJava 用の実行時最適化コンパイラに実装し、UltraSPARC III 上で解析時間と生成されたコードの実行時間を計測した。SPECjvm98 と Java Grande Benchmark において本手法は最大 8% の性能向上を示し、解析時間は最大で 45% 短縮された。

　本研究の結果は、PVNRE と Sentinel PRE を用いることでプログラム中の依存関係はもはや冗長性除去の阻害要因とはならず、より広範囲な冗長性をより高速に除去できることを示している。

　本論文は、最適化コンパイラにおいて、データ依存、制御依存、および例外依存の3種類の依存関係のもとで、部分冗長性除去を行う二種類の最適化手法を提案・実装し、その評価を行っている。しかも、従来の手法と比較して、これまでに不可能であった最適化が可能になっただけでなく、Javaのような動的なプログラミング環境でも十分に利用可能なように、より短い解析時間で最適化を行うことができる。具体的には、データ依存関係と制御依存関係を克服した部分冗長性除去の手法であるPartial Value Number Redundancy Elimination (PVNRE)と、例外依存関係を克服しつつ例外チェック命令の冗長性を除去するSentinel PRE (Partial Redundancy Elimination) と呼ぶ手法を提案・実装している。

　本論文の第1章では、本研究の動機、冗長性除去における3種類の依存関係、本研究の目的がまとめられている。

　第2章では、本研究の背景であるGlobal Value Numberingの手法と部分冗長性除去に関して解説されている。

　第3章ではPVNREについて述べられている。PVNRE は、データフロー解析において値番号を用いることにより、データ依存関係による制約を受けない部分冗長性除去の手法である。また、制御フローの合流点において値番号を動的に変換することで制御依存関係を扱うことができる。この手法をJava 用の実行時最適化コンパイラに実装し、UltraSPARC III 上で解析時間と生成されたコードの実行時間を計測した。Global Value Numberingの後に、部分冗長性除去と複写伝播の繰り返しを行う従来の手法と比較して、17個の標準的なベンチマークのうち、12個では本手法は同等の最適化能力を示し、2個では本質的に本手法の方がすぐれていた。また、解析時間は、従来手法と比較して、ほとんどのプログラムに対して2倍速く、2個のプログラムに対しては2.5倍以上速かった。全体の実行時間に関しては、解析時間の短さから最大2%のスピードアップ、最適化能力により最大13.1%のスピードアップが得られた。

　第4章ではSentinel PRE について述べられている。既存手法では、プログラムの意味を保つために例外依存を越えて例外チェック命令を冗長性除去できない。一方、Sentinel PRE は例外依存を無視して冗長性除去を行い、プログラムの意味を保つために実行時の逆最適化を用いることで例外依存関係を克服している。同様のベンチマークにより、既存手法と比較して、最大10.0%のスピードアップが得られた。解析時間は、コンパイル時間の1.38%を占めるに過ぎなかった。

　第5章では関連研究との比較が行われている。第6章は本研究の貢献についてまとめ、将来の課題を述べている。

　以上に述べたように、本研究の結果は、提案したPVNRE と Sentinel PRE の二つの手法を用いることで、プログラム中の依存関係は冗長性除去の阻害要因とはならず、より広範囲な冗長性をより高速に除去できることを示している。よって、本論文は博士（情報理工学）の学位請求論文として合格と認められる。