最適化の方法 中田育男著 コンパイラの構成と最適化 朝倉書店, 1999年 第１１章
最適化の種類 実行速度を速いものにする。 所要メモリを少なくする。 大域的最適化 局所的最適化 命令の実行回数を減らす。 より速い命令を使う。 並列度を上げる。 所要メモリを少なくする。 大域的最適化 局所的最適化 のぞき穴式最適化
命令の実行回数を減らす １度実行した結果を再利用する。 コンパイル時に実行してしまう。 命令をより実行頻度の低いところに移す。 共通部分式の削除 コンパイル時に実行してしまう。 定数の畳み込み 命令をより実行頻度の低いところに移す。 命令のループの外への移動 プログラムの形を変換する。 ループの変換 式の性質を利用して実行を省略する。 冗長な命令を取り除く。 無用命令の削除・複写の削除 特殊化する。 手続き呼出しの展開・判定の置換え
共通部分式の削除 a = b + c; (1) … d = (b + c) * e; (2) フロー解析 (2)の計算の前に必ず(1)の計算は行われていること データフロー解析 (1)の計算をしてから(2)の計算をするまでに b, cの値が変わらないこと
定数の畳み込み a = 3.5 * 2.0; (3) … b = a + 16.5; (4) (3) ⇒ a = 7.0;
命令のループの外への移動 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: ループ不変 相対定数
ループ変換 ループつぶし ループ融合 ループ展開 ループif展開
式の性質の利用 論理式の部分的評価 算術式の演算順序変更 式の簡単化 x * 1 y + 0
無用命令の削除 a = a; a = b + c; その結果得られるaの値がどこでも使われない。
複写の削除 a = b; (5) … c = a + d; (6) (5)を削除 (6) ⇒ c = b + d; (5)を実行してから(6)を実行するまでの間に bの定義はない。 (5)で定義されたaを使うすべての文について 上記の(A), (B)が成り立つ。
手続き呼出しの特殊化 手続き呼び出しの展開 手続きの複製 int p(int x) { if (x<10) return x+2; else return x*2; } a = p(5); ⇒ a = 7; 手続きの複製
判定の置換え i = i + 1; if (i <= n) goto loop;
のぞき穴式最適化 BrF L ! Branch if False JUMP M L: ⇒ BrT M
より速い命令の利用 レジスタ割付け 特殊な命令の利用 メモリアクセス順序の最適化 演算の強さの軽減 ベクトル化 x**2 ⇒ x*x