a21_opt のバックアップ(No.4)

プログラミング言語における最適化について

プログラミング言語（コンパイラ）で最適化というと、「静的単一代入（SSA）形式への変換」などの難しいイメージが先行して、もはや普通のプログラマは手出しせずにLLVMに任せてしまうのが普通になってしまった感じがします（私の思い込みかもしれませんが）。
- そのためにLLVMをバックエンドに選ぶ人もいるくらいです。
しかしHLXで最適化についてあれこれと実験してみた経験から言うと、最適化処理はそれほど難しいものではありません。いや難しくしようと思えば難しくできそうですし、そうすればもっと高度な最適化ができそうですが、でもそこまではできなくても、たいていは十分に役立つのです。
どうにかしてその「感じ」をうまく伝えたいです。

最適化はいろいろありますが、派手な効果が出ると私が思っているのは、以下の4つです。
- [1]コンパイル時に答えが確定しているものは、定数に置き換えてしまう。
- [2]結果が利用されない命令は消す。
- [3]決して通ることがない命令列は消す。
- [4]ループをアンロールする。
これに加えて、最適化を楽しむために、「最適化を頑張らない、深入りしない」というのもあります。
それぞれ説明します。

さらに、
```
a = 1;
b = a + 2;
```
というのがあれば、
```
a = 1;
b = 3;
```
に置き換えることもします。これは文脈上、「b = a + 2;」のときのaは、必ず1だと決まっているからです。
ちなみに、
```
a = 1;
label:
b = a + 2;
```
であれば、「b = 3;」にはできません。なぜならlabelへgotoで合流することがあるかもしれず、そのときに「a = 1」かどうかが分からないからです。
ここを頑張って、「labelから合流した時も含めて、この文脈では必ず a = 1 になっている、だからここは b = 3; にできる！」という判定ができる最適化手法は存在しますが、それは楽ではありません。できるならやってもいいと思いますが、無理してやって最適化がすべて嫌になるくらいなら、「こういうケースは最適化しない」と割り切っていいと思います。
そんな「がんばらない」最適化でも、しないよりはずっといいのです（後述）。

この最適化が最も成果を上げるのは、条件分岐命令が事前に判定できるときです。
```
if (a == 0) { b = 1; } else { b = 2; }
```
もしここでaの値が文脈上確定するのなら、if文の条件式の結果も確定するので、どちらかの文を選んでしまうことができます。

以下のプログラムがあったします。

a = 1;
printf("%d", a);
a++;
printf("%d", a);
a++;
printf("%d", a);

このプログラムを最適化すると(3-1)のルールにより、

a = 1;
printf("%d", 1);
a = 2;
printf("%d", 2);
a = 3;
printf("%d", 3);

となります。
そして、これを見ると、もはや「a = 1;」と「a = 2;」は何の役にも立っていません。代入したけど結果は使っていなくて、使う前に次の値に上書きされているからです。

ということでこれを消します。

printf("%d", 1);
printf("%d", 2);
a = 3;
printf("%d", 3);

コメント	お名前	NameLink