著者

伊藤陽 小濱 真樹 佐々 政孝

雑誌

情報処理学会論文誌プログラミング(PRO) (ISSN:18827802)

巻号頁・発行日

vol.46, no.SIG14(PRO27), pp.30-42, 2005-10-15

---

SSA 形式(静的単一代入形式)は,φ 関数という仮想的な関数を用いることで,変数の定義を字面上1 カ所だけになるように表した中間表現である.しかし,SSA 形式を用いたプログラム中に現れるφ 関数が仮想的であることから,SSA 形式から直接目的コードを出すことはできない.そこで,目的コードを出す前段階として,φ 関数を消去して通常形式に戻すことが必要である.これをSSA 逆変換と呼ぶ.SSA 逆変換には主なアルゴリズムが2 つある.以前から用いられているBriggs らのアルゴリズム,およびこれとは異なるアプローチによるSreedhar らのアルゴリズムである.SSA 逆変換アルゴリズムはそれぞれ異なった特徴を持つが,これらを実際に比較した研究はほとんどなされていない.このため,SSA 形式を最適化コンパイラに採用するにあたって,どのSSA 逆変換を用いるかの選択の指標となるものがなかった.そこで本研究では,Briggs らとSreedhar らのアルゴリズムの長所と短所を明確にした.また,Briggs らのアルゴリズムに対する改良案を提案した.さらに,Briggsらのアルゴリズムとその改良案,Sreedhar らのアルゴリズムの3 つを実装し,同一のコンパイラ上で,SPEC ベンチマークを用いて種々の条件を変えながら比較した.本研究により,Briggs らの方法ではコアレッシングすることのできないコピー文が数多く挿入されること,実証的にはSreedharらの方法が最も優れていること,が判明した.