SSA最適化 - (2007/02/23 (金) 13:05:00) の編集履歴(バックアップ)
SSA最適化
SSA形式
Static Single Assignment form 静的単一代入形式の略
変数をユニークにするために添え字を付けた中間表現形式
例
a = 1
a = a + 1
を
a0 = 1
a1 = a0 + 1
a = a + 1
を
a0 = 1
a1 = a0 + 1
と書き換えると、ユニークになる。
SSA最適化で行える最適化
- コピー伝播
- 条件分岐を考慮した定数伝播
- 支配関係に基づく共通部分式除去
- 無用命令除去
- 無用φ命令除去
- 空ブロック除去
- ループ不変計算のループ外移動
- ループの帰納変数に関わる演算の強さの軽減と判定の置き換え
SSA変換
- 支配辺境を用いる方法(Cytronらによる方法)
- DJグラフを用いる方法による変換時間(Sreedharらによる方法)
SSA形式からの逆変換
- Briggsらの方法
- Sreedharらの方法