変更文の移動を可能にした 静的単一代入形式上の部分冗長性除去 ０３Ｍ３７２９７ 佐々研究室　溝渕 裕司 本研究では従来のSSAPREで制約されていた、計算の移動と

静的単一代入形式（SSA形式） 部分冗長性除去(PRE) SSA形式上のPRE 背景 最適化に適した表現 すべての変数の定義が一箇所 変数の定義と使用の関係が明確 部分冗長性除去(PRE) 優れた最適化アルゴリズム 共通部分式除去 ループ不変式のループ外移動 SSA形式上のPRE 簡単にそれぞれを説明した後、従来のSSAPREで最適化効果の出せない場合に注目して

SSA形式 SSA形式化（Φ関数） SSA形式化 a= =a a2= a1= a3=φ(a1,a2) =a3 a = a = a + b 最適化に適した表現 すべての変数の定義が一箇所 変数の定義と使用の関係が明確

部分冗長性除去 最適化前 最適化後 t = a + b = t = a + b = a + b a = t = a + b = t 変更文

SSA形式上でのPRE(SSAPRE) 通常形式上のPRE SSA形式上のPRE a = 2 a = 1 = a + b t = a + b = ｔ 通常形式上のPRE 変更文 a2 = 2 a1 = 1 = a1 + b1 a3=φ(a1,a2) =　a3 + b1 t2 = a2 + b1 t1 = a1 + b1 = t1 t3 = φ(t1, t2) =　t3 SSA形式上のPRE

いずれの手法も変更文を移動させないことを前提としたアルゴリズム 関連研究 Brrigs らの方法 SSA形式を用いて解析し、いったん通常形式に戻して処理を行う 　Kennedy らの方法 対象式ごとにFRGというグラフを作成して解析し処理を行う 　立川の方法 Knoop[94]の方法をSSA形式に対応するように改造 計算移動に伴うSSAの添え字の変更について解析し処理を行う ビットベクトル計算により複数の式を同時に解析できる いずれの手法も変更文を移動させないことを前提としたアルゴリズム

SSAPREの例 最適化前 最適化後 a0 = c0 a2 = Φ(a1, a0) x0 = a2 + b0 a3 = c0 y0 = a3 + b0 z0 = a1 + b0 a0 = c0 t1 = a0 + b0 a2 = Φ(a1, a0) t4 =Φ(t3, t1) x0 = t4 a3 = c0 t2 = a3 + b0 y0 = t2 t3 = Φ(t2, t4) z0 = t3 以降立川の方法を従来法と呼びます。

変更文によって最適化効果の出せない例 最適化前 最適化後 a0 = c0 a2 = Φ(a1, a0) x0 = a2 + b0 y0 = a3 + b0 a1 =d0 z0 = a1 + b0 a0 = c0 a2 = Φ(a1, a0) t1 = a2 + b0 x0 = t1 a3 = c0 t2 = a3 + b0 y0 = t2 a1 =d0 t3 = a1 + b0 z0 = t3 変更文 問題２ 変更文により挿入可能な範囲が限定的 問題 変更文によりコード移動可能な範囲が制限 問題２ 変更文により挿入可能な範囲が限定的 Aやbの値を変えるものを変更文という。

計算式のコード移動が変更文によって妨げられている 従来SSAPREの問題点 　計算式のコード移動が変更文によって妨げられている そこで 変更文を移動することにより計算式をより最適な場所にコード移動したい

同一Φ関数内の変数の生存区間干渉がないことが前提 問題点 同一Φ関数内の変数の生存区間干渉を誘発する最適化の後に適用できない 立川の方法（従来法）の特徴 特徴 　Knoop[94]の方法をSSA形式に対応するように改造 　同一Φ関数内の変数の生存区間干渉がないことが前提 　通常形式からSSA変換直後に最適化可能 問題点 　同一Φ関数内の変数の生存区間干渉を誘発する最適化の後に適用できない 変更文を移動すると 同一Φ関数内の変数の生存区間干渉が起きてしまう 以降立川の方法を従来法と呼びます。 生存区間干渉が起きると 立川の方法をそのまま使えない

変更文の移動可能にした部分冗長性除去のアルゴリズムの提案 本研究の目的 変更文の移動可能にした部分冗長性除去のアルゴリズムの提案 　変更文の移動のアルゴリズム 　計算式の最適なコード移動 　同一Φ関数内の変数の生存区間干渉の起こしているプログラムにも対応 アルゴリズムの有用性 　最適化そのものとして 　変更文の移動による最適化効果の違い

本研究の最適化効果 a0 = 0 b0 = 0 a0 = 0 t0 = a0 + b0 b0 = 0 = t0 = a0 + b0 c0 = b2 = Φ(b0, b1) t2 = Φ(t0, t1) a2 = b0 b3 = 1 t5 = a2 + b2 t10 = a2 + b3 b2 = Φ(b0, b1) a3 = Φ(a2, a0) b5 = Φ(b4, b2) t7 = Φ(t6, t2) t8 = Φ(t6, t5 a3 = Φ(a2, a0) b5 = Φ(b4, b2) = a3 + b5 a1 = b5 b3 = 1 = a1 + b3 a1 = b5 = t7 = a1 + b3 b4 = Φ(b3, b5) a2 = c0 = a2 + b4 b4 = Φ(b3, b5) = t6

前処理 計算式のφ関数の作成 本処理 本アルゴリズムの概要 部分冗長となる式の候補作成 新しく出来るφ関数の添え字の解析 変更文の巻上げ 計算式の巻上げ 計算式の巻き下げ 変更文の巻き下げ

前処理 計算式のφ関数の作成 部分冗長となる式の候補作成 →Candidate Tableの作成 c. 新しく出来るφ関数の添え字の解 　　　→Suffix Tableの作成 c0 = b1 = c0 = a0 + b1 = a0 + b0 = a0 + b1 b2 = Φ(b0, b1) a0 + b2 = Φ(a0 + b0, a0 + b1) a2 + b2 = Φ(a2 + b0, a2 + b1) Suffix Table a0 + b0 → t0 a0 + b1 → t1 a0 + b2 → t2 a2 + b0 → t3 a2 + b1 → t4 a2 + b2 → t5 a2 + b4 → t6 a3 + b5 → t7 a2 + b5 → t8 a1 + b3 → t9 a2 + b3 → t10 t2 = Φ(t0, t1) t5 = Φ(t3, t4) t7 = Φ(t6, t2) t8 = Φ(t6, t5) t6 = Φ(t10, t8) Candidate Table a0 + b0 a0 + b1 a1 + b3 a2 + b0 a2 + b1 a2 + b3 a3 = Φ(a2, a0) b5 = Φ(b4, b2) a3 + b5 = Φ(a2 + b4, a0 + b2) a2 + b5 =Φ(a2 + b4, a2 + b2) = a3 + b5 a1 = b5 b3 = 1 = a1 + b3 b4 = Φ(b3, b5) a2 + b4 = Φ(a2 + b3, a2 + b5) a2 = c0 = a2 + b4

本処理（変更文の巻上げ） a0 = 0 b0 = 0 = a0 + b0 a0 = 0 b0 = 0 b3 = 1 = a0 + b0 c0 = b1 = c0 = a0 + b1 c0 = b1 = c0 = a0 + b1 = a0 + b0 = a0 + b1 = a0 + b0 = a0 + b1 b2 = Φ(b0, b1) b2 = Φ(b0, b1) a2 = c0 a3 = Φ(a2, a0) b5 = Φ(b4, b2) a3 = Φ(a2, a0) b5 = Φ(b4, b2) a1 = b5 = a3 + b5 a1 = b5 b3 = 1 = a1 + b3 = a3 + b5 = a1 + b3 b4 = Φ(b3, b5) a2 = c0 = a2 + b4 b4 = Φ(b3, b5) = a2 + b4

変更文「x0 = y0」の出来るだけ巻き上げた場所の解析（ModEarliest) 本処理（変更文の巻上げ） 変更文「x0 = y0」が移動可能な場所の解析 1.右辺「y0」の定義を上向きに超えない場所を探す →定義と使用の順番を守るため 2.求められたNMayMoveとXMayMoveを支配木とマージ（NCanMoveとXCanMoveが求まる) →Dominance Property を守るため 変更文「x0 = y0」の出来るだけ巻き上げた場所の解析（ModEarliest) 3.求められたNCanMoveとXCanMoveがtrueの範囲で支配木の親となるブロック

本処理（計算式の巻上げ） a0 = 0 b0 = 0 b3 = 1 t0 = a0 + b0 = t0 a0 = 0 b0 = 0 c0 = b1 = c0 t1 = a0 + b1 = t1 c0 = b1 = c0 = a0 + b1 = t0 = t1 = a0 + b0 = a0 + b1 b2 = Φ(b0, b1) t2 =　Φ(t0, t1) a2 = c0 t3 = a2 + b0 t4 = a2 + b1 t10 = a2 + b3 b2 = Φ(b0, b1) a2 = c0 a3 = Φ(a2, a0) b5 = Φ(b4, b2) a1 = b5 a3 = Φ(a2, a0) b5 = Φ(b4, b2) t7 = Φ(t6, t2) t8 = Φ(t6, t5) a1 = b5 t9 = a1 + b3 = a3 + b5 = a1 + b3 = t7 = t9 b4 = Φ(b3, b5) = a2 + b4 b4 = Φ(b3, b5) t6 = Φ(t10, t8) = t5

計算式「t0 = a0 + b0」の出来るだけ巻き上げることのできる場所の解析(Earliest) 本処理（計算式の巻上げ） 計算式「t0 = a0 + b0」の出来るだけ巻き上げることのできる場所の解析(Earliest) 1.変数「a0」と変数「b0」の定義するブロックが同時に支配するブロックまで移動できる →定義と使用の関係を守るため

本処理（計算式の巻き下げ, 計算式の合成） a0 = 0 b0 = 0 b3 = 1 t0 = a0 + b0 = t0 a0 = 0 c0 = b1 = c0 t1 = a0 + b1 = t1 c0 = b1 = c0 t1 = a0 + b1 = t1 = t0 = t1 = t0 = t1 b2 = Φ(b0, b1) t2 =　Φ(t0, t1) a2 = c0 t3 = a2 + b0 t4 = a2 + b1 t10 = a2 + b3 b2 = Φ(b0, b1) t2 =　Φ(t0, t1) a2 = c0 t5 = a2 + b2 t10 = a2 + b3 Suffix Table a0 + b0 → t0 a0 + b1 → t1 a0 + b2 → t2 a2 + b0 → t3 a2 + b1 → t4 a2 + b2 → t5 a2 + b4 → t6 a3 + b5 → t7 a2 + b5 → t8 a1 + b3 → t9 a2 + b3 → t10 t2 = Φ(t0, t1) t5 = Φ(t3, t4) t7 = Φ(t6, t2) t8 = Φ(t6, t5) t6 = Φ(t10, t8) a3 = Φ(a2, a0) b5 = Φ(b4, b2) t7 = Φ(t6, t2) t8 = Φ(t6, t5) a1 = b5 t9 = a1 + b3 a3 = Φ(a2, a0) b5 = Φ(b4, b2) t7 = Φ(t6, t2) t8 = Φ(t6, t5) a1 = b5 = t7 t9 = a1 + b3 = t9 = t7 = t9 b4 = Φ(b3, b5) t6 = Φ(t10, t8) = t5 b4 = Φ(b3, b5) t6 = Φ(t10, t8) = t5

計算式「t0 = a0 + b0」を遅れさせることの出来る場所の解析(Delay) 本処理（計算式の巻き下げ） 計算式「t0 = a0 + b0」を遅れさせることの出来る場所の解析(Delay) 1.Earliestから遅れさせることの出来る場所(Delay)

計算式「t0 = a0 + b0」と「t1 = a1 + b1」を「t2 = a2 + b2」に置き換え(ReMakeSuffix) 本処理（計算式の合成） 計算式「t0 = a0 + b0」と「t1 = a1 + b1」を「t2 = a2 + b2」に置き換え(ReMakeSuffix) 1. 「t0 = a0 + b0」 と「t1 = a1 + b1」が同時に挿入される可能性がある場所の解析 2. ReMakeSuffixの成り立つ場所でSuffixTableを参照して合成

本処理（計算式のコード移動場所を遅くする） 計算式「t0 = a0 + b0」を出来るだけ遅れさせることの出来る場所の解析(Latest)

本処理（変更文の巻き下げ） a0 = 0 b0 = 0 b3 = 1 t0 = a0 + b0 = t0 a0 = 0 b0 = 0 c0 = b1 = c0 t1 = a0 + b1 = t1 c0 = b1 = c0 t1 = a0 + b1 = t1 = t0 = t1 = t0 = t1 b2 = Φ(b0, b1) t2 =　Φ(t0, t1) b3 = 1 a2 = c0 t3 = a2 + b0 t4 = a2 + b1 t10 = a2 + b3 b2 = Φ(b0, b1) t2 =　Φ(t0, t1) a2 = c0 t3 = a2 + b0 t4 = a2 + b1 t10 = a2 + b3 a3 = Φ(a2, a0) b5 = Φ(b4, b2) t7 = Φ(t6, t2) t8 = Φ(t6, t5) a1 = b5 t9 = a1 + b3 a3 = Φ(a2, a0) b5 = Φ(b4, b2) t7 = Φ(t6, t2) t8 = Φ(t6, t5) a1 = b5 = t7 t9 = a1 + b3 = t9 = t7 = t9 b4 = Φ(b3, b5) t6 = Φ(t10, t8) = t5 b4 = Φ(b3, b5) t6 = Φ(t10, t8) = t5

変更文「x0 = y0」を遅れさせることの出来る場所の解析 本処理（変更文の巻き下げ） 変更文「x0 = y0」を遅れさせることの出来る場所の解析 1.CanMoveのtrueの場所を辿る 2.それぞれの場所ですべての「x0」の使用を支配する場所を求める 3.支配木の子供となる場所を求める

COINS1.0.2上で実装および実験 ベンチマーク 実装・実験 出力コードの実行時間を計測 ロード命令回数の静的カウント SPECint2000 181.mcf SPECint2000 164.gzip 14女王問題 挿入ソート 選択ソート ヒープソート tpprime

最適化効果 評価内容 最適化そのものとしての評価 変更文移動によってどれほど最適化効果が変わるか 本手法と他の最適化を比較 ロードカウント 最適化効果　 最適化そのものとしての評価 本手法と他の最適化を比較 ロードカウント 変更文移動によってどれほど最適化効果が変わるか 本手法と従来法と実行速度の改善度を比較

実験環境 Sun Blade 1000 アーキテクチャ Superscalar SPARCTMVersion9 プロセッサ 750MHz UltraSPARCIII×2 1次キャッシュ 64KBデータ，32KBインストラクション 2次キャッシュ 8MB外部キャッシュ メモリ容量 1GByte OS環境 SunOS 5.8

評価１ 最適化0 SSA変換→SSA逆変換 最適化1 SSA変換→コピー伝播→定数伝播 →無用コードの除去→SSA逆変換 最適化2 最適化3 SSA変換→定数伝播→ループ不変式 →共通部分式→コピー伝播→定数伝播→ 無用コードの除去→SSA逆変換→合併 本手法1 SSA変換→危険辺除去→本手法→SSA逆変換 本手法2 SSA変換→危険辺除去→コピー伝播→本手法→コピー伝播 →定数伝播→無用コードの除去 →SSA逆変換

最適化効果の比較

ロード命令の静的カウント

評価２ 最適化0 SSA変換→SSA逆変換 従来法１ SSA変換→従来法→SSA逆変換 従来法2 SSA変換→従来法→定数伝播 →無効コードの除去 →SSA逆変換→合併 本手法1 SSA変換→危険辺除去→本手法→SSA逆変換 本手法2 SSA変換→危険辺除去→コピー伝播→本手法→コピー伝播 →定数伝播→無用コードの除去 →SSA逆変換

本手法と従来法の比較

変更文の移動を可能にした部分冗長性除去の提案 まとめ 変更文の移動を可能にした部分冗長性除去の提案 変更文のコード移動アルゴリズム 生存区間干渉に対応→他の最適化後にも適用可能 最適化効果 最適化そのものとしては効果あり 従来法とはほぼ互角 レジスタプレッシャによるロード回数の上昇 最適化効果改善の余地があり

変更文移動のアルゴリズムの改善 冗長効果の高い計算式の選択 意味等価な式を扱う 今後の課題 Dominace Property を守る方法として支配木の親を辿る方法を採用 柔軟なコード移動が出来るように 冗長効果の高い計算式の選択 Briggs[94]の方法では計算式にランクをつけている 意味等価な式を扱う 滝本[97]ではSSAグラフというグラフを用いて解析 実装が困難