ループ内条件分岐排除に関する新方式の提案と評価

概要

論文の詳細を見る
コンパイラにおける最適化は, 計算機の性能を十分に発揮するためのコードを生成することである.この最適化に関する研究の中で, コード中で最も実行頻度が高いとされているループ文の最適化はプログラムの実行速度向上に効果的である.本論文では, ループ最適化の中で特に, ループ内で命令の流れを妨げるような条件分岐を取り除く最適化を取り扱う.ループ内の条件分岐を排除する従来方式としては, Loop Unswitching, Loop Unrolling, Loop Peeling, Index Set Splittingがある.これらの方式は, if文の条件判定式がループ不変な変数と定数との比較の場合や, 単一のループインデックス変数と定数との比較の場合にしか適用できないため, 適用範囲が狭いという問題点がある.そこで, 本論文では, 複数のループインデックス変数を含む条件判定式に対しても適用できる新しいアルゴリズムを提案する.これにより, 従来方式では適用できなかった条件分岐を排除できるようになる.また, 提案方式について, 実行時間に関して評価を行った.その結果, 提案方式の有効性を確認できた.
2006-02-15