著者

伊藤陽 小濱 真樹 佐々 政孝

雑誌

情報処理学会論文誌プログラミング(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らの方法が最も優れていること,が判明した.

著者

伊藤陽 小濱 真樹 佐々 政孝

出版者

一般社団法人情報処理学会

雑誌

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

巻号頁・発行日

vol.46, no.14, pp.30-42, 2005-10-15

被引用文献数

3

---

SSA 形式(静的単一代入形式)は,φ 関数という仮想的な関数を用いることで,変数の定義を字面上1 カ所だけになるように表した中間表現である.しかし,SSA 形式を用いたプログラム中に現れるφ 関数が仮想的であることから,SSA 形式から直接目的コードを出すことはできない.そこで,目的コードを出す前段階として,φ 関数を消去して通常形式に戻すことが必要である.これをSSA 逆変換と呼ぶ.SSA 逆変換には主なアルゴリズムが2 つある.以前から用いられているBriggs らのアルゴリズム,およびこれとは異なるアプローチによるSreedhar らのアルゴリズムである.SSA 逆変換アルゴリズムはそれぞれ異なった特徴を持つが,これらを実際に比較した研究はほとんどなされていない.このため,SSA 形式を最適化コンパイラに採用するにあたって,どのSSA 逆変換を用いるかの選択の指標となるものがなかった.そこで本研究では,Briggs らとSreedhar らのアルゴリズムの長所と短所を明確にした.また,Briggs らのアルゴリズムに対する改良案を提案した.さらに,Briggsらのアルゴリズムとその改良案,Sreedhar らのアルゴリズムの3 つを実装し,同一のコンパイラ上で,SPEC ベンチマークを用いて種々の条件を変えながら比較した.本研究により,Briggs らの方法ではコアレッシングすることのできないコピー文が数多く挿入されること,実証的にはSreedharらの方法が最も優れていること,が判明した.The SSA form (static single assignment form) is an intermediate representation where the definition of each variable appears only once in the program by using a hypothetical function called φ-function. However, since the φ-functions appearing in the program using the SSA form are non-executable, the target code cannot be directly generated from the SSA form. Therefore, it is necessary to delete the φ-function and put the SSA form back to the normal form before generating the target code. This conversion is called SSA reverse translation'. There are two major SSA reverse translation algorithms. One is the method by Briggs et al., which is used from relatively early times. The other is the method by Sreedhar et al., which is based on a completely different approach. So far, there has been almost no research that actually compares these SSA reverse translation algorithms, although each algorithm has different characteristic features. Therefore, there have been no criteria as to which SSA reverse translation algorithm should be selected when the SSA form is used in an optimizing compiler. In this paper, we clarify merits and weak points of algorithms by Briggs and Sreedhar. We also propose an improvement of the algorithm by Briggs. Then, we implement algorithms by Briggs and its improvement and the algorithm by Sreedhar on the same compiler, and compare the three by changing the various environments using the SPEC benchmarks. The experiment has shown that the method by Briggs inserts a lot of copy statements that cannot be coalesced. Empirically, the method by Sreedhar is the most efficient.