例外依存関係を越える部分冗長性除去

情報処理学会 Web Site 参考文献25件

書誌事項

タイトル別名
  • Partial Redundancy Elimination beyond Exception Dependency
  • レイガイ イゾン カンケイ オ コエル ブブン ジョウチョウセイ ジョキョ

この論文をさがす

説明

実行時の安全を保証するための例外機構は一方で速度低下の原因となるため，部分冗長性除去（Partial Redundancy Elimination; PRE）で上方移動を用いて不要な例外命令を削除することが有効である．しかし我々はプログラムの意味を保つために例外命令どうしの順序関係である例外依存関係を保つ必要がある．したがって，従来の部分冗長性除去では例外命令の上方移動が阻害されることが多い．本研究で我々はプログラムの意味を保存しつつ例外依存関係を越える部分冗長性除去，Sentinel PRE を提案する．Sentinel PRE は例外依存関係を無視して上方移動を行い，その後で高速な解析により例外順序の入れ替わりを検出する．順序が入れ替わった例外命令で例外が起きた場合，プログラムの意味を保つために上方移動する前の状態に脱最適化でコードを戻す．現実のプログラムで例外が起きることは稀であるため，ほとんどの場合は上方移動により最適化された高速なコードが実行される．Sentinel PRE は特別なハードウェアのサポートには依存せず，動的なコード書き換えにより脱最適化を実現する．我々はSentinel PRE をJava の実行時コンパイラに実装して実験を行い，Java Grande Benchmark 中のheapsort プログラムで8.4%の性能向上を得た．

Exception mechanism guarantees runtime robustness, but results in performance degradation. Thus, it is effective to remove redundant excepting instructions by Partial Redundancy Elimination (PRE), which uses hoisting of instructions. However, we must preserve ordering constraints between excepting instructions, which we call exception dependencies, in order to keep the semantics of the program. Therefore, existing PRE algorithms cannot hoist many excepting instructions. In this work, we propose Sentinel PRE, a PRE algorithm which overcomes exception dependencies and at the same time keeps the semantics. Sentinel PRE first hoists excepting instructions without considering exception dependencies, and then detects exception reordering by fast analysis. If exception occurs at a reordered instruction, it deoptimizes the code into the one before hoisting. Since we rarely encounter exception in real programs, the optimized code is executed in almost all cases. Sentinel PRE does not rely on special hardware support, and performs deoptimization by runtime code patching. We implemented Sentinel PRE in a Java just-in-time compiler and conducted experiments. The results show 8.4% performance improvement in “heapsort” program in Java Grande Benchmark.

収録刊行物

参考文献 (25)*注記

もっと見る

キーワード

詳細情報 詳細情報について

問題の指摘

ページトップへ