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

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

(by K, 2021.10.04)

↑

(1)

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

↑

(2)

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

↑

(3-1) コンパイル時に答えが確定しているものは、定数に置き換えてしまう。

これは簡単です。
```
a = 1 + 2 + b;
```
みたいなのがあれば、
```
a = 3 + b;
```
に置き換える、というだけの話です。1+2の部分を3に置き換えました。

さらに、
```
a = 1;
b = a + 2;
```

というのがあれば、

a = 1;
b = 3; // まず 1 + 2 に置き換えられて、それが計算されて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文の条件式の結果も確定するので、どちらかの文を選んでしまうことができます。

この最適化を実現するアルゴリズムは簡単です。
プログラムを上から順番に見ていくことにします。
もし変数に定数が代入されたら、この変数の値は〇〇である、とテーブルに登録しておきます。
もし定数ではない値が代入されたら、もう変数の値は不定なので、もしテーブルにその変数が登録されていればそれを消しますし、登録されていなければ何もしません。
テーブルに登録された変数を参照された場合は、それを全部定数に置換してしまいます。
ラベル定義文やforやwhileの先頭は繰り返しやcontiuneで合流が発生する可能性があるところです。そうなると合流の際に変数の値がどうなっているかわかったものではないので、テーブルはクリアしてしまいます。forやwhileの直後の文もbreakなどで飛んでくるので、テーブルのクリアが必要です。そんな感じで、合流の可能性があるところでは全部テーブルクリアです。
置換の結果（もしくは置換する前から）式の一部または全部が定数だけで構成されていたら、そこは計算してしまって計算値と置換します。
こうして最後までプログラムをチェックし終わったら、それでおしまいです。

ちなみにプログラム内で一度でもポインタを取得した変数（p = &i; としたときのiのこと）は、そのポインタを使って中身を書き換えたり読んだりする可能性があります。それはいつ起こるか簡単にはわかりません。だからそういう変数に対しては、たとえ定数の代入があってもその後も定数のままでいると仮定することなく、変数扱いにします。
ここも頑張ればもっと最適化がうまくなるのですが、それをやると大変なので、面倒なら無理せずに変数扱いにしてしまいましょう。それでも多くのケースで十分に最適化はできます。

ここでは説明のためにC言語のままで処理するかのように書きましたが、HLXではアセンブラみたいな単純な命令列に変換してから最適化するので、最適化の処理はさらに単純です。

↑

(3-2) 結果が利用されない命令は消す。

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

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);

この例では最適化の結果として「結果が利用されない命令」が生じましたが、人間が作るプログラムに最初から「結果が利用されない命令」が含まれていることはたまにあります。そういうのももちろん消します。

なお、この最適化は連鎖性があります。
```
a = x;
b = a + 2;
c = b * 3;
```
みたいな場合、この先でaもbもcも使わないのであれば、まず「c = b * 3;」が消えて、次にそれによってbが使われなくなって、「b = a + 2;」が消えて、そして「a = x;」も消えることになるわけです。

この最適化を実現するアルゴリズムは簡単です。
プログラムを上から順番に見ていくことにします（下から順番に見ていってもいい）。
何か変数に「代入する命令」があったとき、その直後からその結果を使う命令がどこにあるかを探します（これは上から順番に見る）。つまり二重ループです。
もし誰からも参照されないまま、新しい別の値を代入する命令にぶつかったら、それは「結果は使われていない」と判断できます。また値を利用する命令にぶつかったときも、「結果は使われている」と判断できます。・・・判断できたら命令を順番に調べていく内側のループからは抜けられます。
悩ましいのは分岐命令や条件分岐命令にぶつかったときです。こうなると分岐先でどうなるのかを解析しないと判断できません。でもそれはちょっとめんどくさそうです（たとえ分かれ道がなくて単純そうな無条件分岐であっても、ただそれをたどっていくとかだと、無限ループとかの場合に出られなくなる恐れがある）。・・・ここを頑張れば最適化性能は間違いなく向上しますが、やっぱり面倒なので、分岐命令にぶつかったら、「もうよくわからん、わからんから結果はたぶん使うだろうということにしておこう」って私はやりました。それでも最適化は結構効きます。
それで、上記の判定で「結果は使われていない」と判断できた場合に限り、その「代入する命令」は消してしまいます。

ここでは説明のためにC言語のままで処理するかのように書きましたが、HLXではアセンブラみたいな単純な命令列に変換してから最適化するので、最適化の処理はさらに単純です。

↑

(3-3) 決して通ることがない命令列は消す。

たとえば

a = 0;
for (i = 0; i < 10; i++) {
    printf("%d", i);
    if (a == 0) continue;
    printf("hello");
}

このプログラムの中で、 printf("hello"); は一度も実行されません。それは(3-1)の最適化をすればはっきりわかります。
こういうのを見つけた場合は、邪魔なので消してしまいます。

この最適化を実現するアルゴリズムは簡単です。
gotoやbreakやcontinueなどが、条件なしで現れた場合、それは無条件分岐命令であり、そこより下が実行される可能性はありません。
ということで、次の合流可能性があるところ（ラベルがあるところ、ifやelseの終わりなど）まで、全部消してしまいます。

ここでは説明のためにC言語のままで処理するかのように書きましたが、HLXではアセンブラみたいな単純な命令列に変換してから最適化するので、最適化の処理はさらに単純です（条件分岐や無条件分岐が見つけやすいし、合流可能性のあるところも見つけやすい）。

↑

(3-4) ループをアンロールする。

以下のようなループがあったとします。・・・1から10までの和を計算するループです。
```
s = 0;
for (k = 1; k <= 10; k++) {
    s += k;
}
```
これはwhileを使って書き直すとこうなります。
```
s = 0; k = 1;
while (k <= 10) {
    s += k; k++;
}
```

ここで、whileを5回分だけアンロールしてみましょう。

    s = 0; k = 1;
    if (k > 10) goto skip; s += k; k++;
    if (k > 10) goto skip; s += k; k++;
    if (k > 10) goto skip; s += k; k++;
    if (k > 10) goto skip; s += k; k++;
    if (k > 10) goto skip; s += k; k++;
    while (k <= 10) {
        s += k; k++;
    }
skip:

その上で、(3-1)を適用するとこうなります。

    s = 0; k = 1;
    s = 1; k = 2;
    s = 3; k = 3;
    s = 6; k = 4;
    s = 10; k = 5;
    s = 15; k = 6;
    while (k <= 10) {
        s += k; k++;
    }

さらに(3-2)を適用するとこうなります。

    s = 15; k = 6;
    while (k <= 10) {
        s += k; k++;
    }

さらにさらに、もし最初から10回分以上のアンロールをして、(3-1)や(3-2)の最適化を適用すれば、
```
s = 55;
```
だけになります。

どうですか。最初に示したループが「s = 55;」まで最適化できちゃったら、結構楽しくないですか？

↑

(4) 最適化で難しいと感じたところ

[1]ループのアンロールをどのくらいやるべきなのか判断するのがむずかしい
- 上記の例のように、うまくいったときの効果が大きくて面白い「ループのアンロール」なのですが、実際のそれぞれのループについて、どのくらいアンロールしたらいいのかを自動で判断させるのはかなり難しい印象です。
- アンロールしないほうがいいループはたくさんあります。・・・少しアンロールしてみてアンロール部分がうまくまとまるか見てみて、まとまったらアンロールを増やせばいいのでしょうか？そんな方法でもできるかもしれませんが、処理は複雑で大変そうですし、コンパイル時間はかなり長引きそうです。
- HLXでは、プログラム内に「これは〇〇回アンロールすべし」と明記する仕様にしました。自動判定は手に負えないと思ったので、プログラマに判断を手伝ってもらおうというわけです。
[2]どの変数をレジスタ変数にするべきか？
[3]純関数はどれか？

↑

こめんと欄

コメント	お名前	NameLink