最適化の方法 中田育男著 コンパイラの構成と最適化 朝倉書店, 1999年 第１１章.

Presentation on theme: "最適化の方法 中田育男著 コンパイラの構成と最適化 朝倉書店, 1999年 第１１章."— Presentation transcript:

1 最適化の方法 中田育男著 コンパイラの構成と最適化 朝倉書店, 1999年 第１１章

2 最適化の種類 実行速度を速いものにする。 所要メモリを少なくする。 大域的最適化 局所的最適化 命令の実行回数を減らす。
より速い命令を使う。 並列度を上げる。 所要メモリを少なくする。 大域的最適化 局所的最適化 のぞき穴式最適化

3 命令の実行回数を減らす １度実行した結果を再利用する。 コンパイル時に実行してしまう。 命令をより実行頻度の低いところに移す。
共通部分式の削除 コンパイル時に実行してしまう。 定数の畳み込み 命令をより実行頻度の低いところに移す。 命令のループの外への移動 プログラムの形を変換する。 ループの変換 式の性質を利用して実行を省略する。 冗長な命令を取り除く。 無用命令の削除・複写の削除 特殊化する。 手続き呼出しの展開・判定の置換え

4 共通部分式の削除 a = b + c; (1) … d = (b + c) * e; (2)
フロー解析 (2)の計算の前に必ず(1)の計算は行われていること データフロー解析 (1)の計算をしてから(2)の計算をするまでに b, cの値が変わらないこと

5 定数の畳み込み a = 3.5 * 2.0; (3) … b = a + 16.5; (4) (3) ⇒ a = 7.0;

6 命令のループの外への移動 t = b*c do i = 1, 10 do i = 1, 10 … … a = b*c a = t
end do do i = 1, 10 … a = b*c end do ⇒ b*c: ループ不変 相対定数

7 ループ変換 ループつぶし ループ融合 ループ展開 ループif展開

8 式の性質の利用 論理式の部分的評価 算術式の演算順序変更 式の簡単化 x * 1 y + 0

9 無用命令の削除 a = a; a = b + c; その結果得られるaの値がどこでも使われない。

10 複写の削除 a = b; (5) … c = a + d; (6) (5)を削除 (6) ⇒ c = b + d;
(5)を実行してから(6)を実行するまでの間に bの定義はない。 (5)で定義されたaを使うすべての文について 上記の(A), (B)が成り立つ。

11 手続き呼出しの特殊化 手続き呼び出しの展開 手続きの複製 int p(int x) { if (x<10) return x+2;
else return x*2; } a = p(5); ⇒ a = 7; 手続きの複製

12 判定の置換え i = i + 1; if (i <= n) goto loop;

13 のぞき穴式最適化 BrF L ! Branch if False JUMP M L: ⇒ BrT M

14 より速い命令の利用 レジスタ割付け 特殊な命令の利用 メモリアクセス順序の最適化 演算の強さの軽減 ベクトル化 x**2 ⇒ x*x