「型安全でないCプログラムのポインタ解析」 [論文誌Vol.45, No.SIG12(PRO23), pp. 52-66 (2004)]

平成17年度論文賞受賞者の紹介

「型安全でないCプログラムのポインタ解析」 [論文誌Vol.45, No.SIG12(PRO23), pp. 52-66 (2004)]

[論文概要]
 ポインタ解析とはプログラム中のポインタの指示先を求める解析である.多くのコンパイラ最適化がポインタ解析の結果を利用しており,その解析精度を高めることはプログラムの実行性能を向上させる上で重要である. Cプログラムに対するポインタ解析では,特に型変換の扱いが問題になる. Cではポインタ値の整数値への変換や,構造体変数の別の型による参照のような宣言型を尊重しない処理が可能であり,精密な解析モデルの生成を困難にしていた.本論文ではポインタ解析と並行して各変数の参照時の型を解析し,その結果を解析モデルに反映させることでより高精度な解析結果を得る方法を示している.

[推薦理由]
 ポインタ解析とはプログラム中のポインタが実行時に指す可能性のある領域を求めることである.正確なポインタ解析がコンパイラの最適化に大きく寄与することが広く知られている.本論文は,ANSIC 標準で定められた仕様に加えて,商用コンパイラが保証する性質を解析に応用することで,解析の精度とコストを大幅に改善できることを示している.提案された解析アルゴリズムは商用コンパイラに組み込まれ,数多くのベンチマークを対象として念入りに評価されており,実用性も高い.特に,ポインタ解析ではしばしば問題となる過大な解析コストをほぼ線形オーダーに抑え,秒速約十万行の解析性能が得られることを報告している.この研究は,実用性と新規性の両面で重要な意義を持ち,高く評価できる.よって,本論文を論文賞に推薦する.

千代 英一郎 君 1999年東京大学大学院工学系研究科情報工学専攻修士課程修了.同年日立製作所(株)入社.システム開発研究所にてコンパイラの研究開発に従事.興味はプログラム解析,最適化,検証および意味論.