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

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

(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]どの変数をレジスタ変数にするべきか？
- 変数をどのようにレジスタに割り当てるかは、かなり性能に影響する重要事項です。これだけでも様々なアルゴリズムがあるくらいなのですが、私はどれも大変そうだと感じたので、この問題から逃げることにしました。
- ということでHLXでは、プログラマがどの変数をレジスタに割り当ててほしいのかをプログラム内で記述することになっています。
[3]純関数はどれか？
- プログラム内で、 y = f(x); みたいな記述があって、しかしこのyの値がその先で使われないのなら、この関数呼び出しそのものを最適化によって消したほうがいいかもしれないという可能性が出てきます。もし消せれば、このxについても参照回数が1回減るので、他で使われていないのなら、xへの代入も消せるかもしれません。
- それでそういうときにf(x)の呼び出しが消せるかどうかは、fが副作用のない純関数かどうかにかかっています。この f(x) が単に計算をして値を返すだけで、他に何も影響を残さない関数なのであれば、純関数なので消せます。しかしそうではないのなら消してはいけません。
- コンパイラからすると、ある関数が純関数かどうかは容易には判断できません。アルゴリズムを頑張れば純関数かどうかの判定もできるようになるかもしれません。そうしたら「結果を利用しない純関数の呼び出しは消す」という最適化が可能になるのです。
- HLXでもこの最適化はやりたいと思っていますが、与えられた関数が純関数かどうかを自動判定させるは大変そうなので、関数宣言時に純関数だよと書いてあったらそれを信じる、くらいの方法でごまかしたいなと思っています。

↑

(5) 最適化を頑張るとどこまでできるか #1

ここで標準関数のprintfやputsに似た、my_printf、my_putsという関数を考えます。これらは本家と異なって、返り値はなく（void）、しかもmy_putsは自動改行機能がないとします。
本家のprintfやputsのまま話を進めたかったのですが、そうすると話が面倒になりそうなので・・・。

ここで、こんなことを妄想します。

my_printf("My name is %s.\n", nam);
が
my_puts("My name is ");
my_puts(nam);
my_puts(".\n");
に変換されたらいいのにな・・・。

この妄想の背景として、printf族は実行時に複雑なフォーマット文字列を解釈するので、実行速度は遅いし、printf自体も巨大な関数なのです。だからこれを使いたくない、リンクしたくないというのはたまに聞く話です。
上記の妄想のようにprintf族を使わない形に変換できれば、実行速度の改善が十分に期待できます。

ここでmy_printf()がこんな実装だったとしましょう。

void my_printf(const char *fmt, ...)
{
    va_list ap;
    va_start(ap, fmt);
    int i = 0;
    while (fmt[i] != 0) {
        if (fmt[i] != '%') {
            putchar(fmt[i++]);
        } else if (fmt[i + 1] == 's') {
            my_puts(va_arg(ap, const char *));
            i += 2;
        } else if (fmt[i + 1] == 'c') {
            putchar(va_arg(ap, int));
            i += 2;
        } else if (fmt[i + 1] == '%') {
            putchar('%');
            i += 2;
        }
        // すみません、説明のための手抜きなのでいろいろ足りないところは許してください.
    }
    va_end(ap);
}

この定義に対して my_printf("My name is %s.\n", nam); を適用して、しかも関数をインライン展開したとします。・・・すると、最適化の結果として、以下が得られるはずです。
```
putchar('M'); putchar('y'); putchar(' '); ... putchar('i'); putchar('s'); putchar(' ');
my_puts(nam);
putchar('.'); putchar('\n');
```
あとは連続するputcharをmy_putsにまとめる最適化さえつけておけば、
```
my_puts("My name is ");
my_puts(nam);
my_puts(".\n");
```
が得られるのです。これはいい！！

↑

(6) 最適化を頑張るとどこまでできるか #2

C言語は変数が型を持つ言語（静的型付き言語）ですが、世の中には動的型付き言語というものもあって、たとえばRubyやLISPなどが有名です。

もしC言語で動的型付き言語みたいなことをするとしたら、以下のようにするかもしれません。

typedef struct Var_ {
    int t; // 0:int, 1:char *, 2:double,...
    union {
        int i;
        char *s;
        double d;
    };
} Var;

void func()
{
    Var a, b, c, d;
    a.t = 0; a.i = 2;
    b.t = 1; b.s = "hello";
    c.t = 2; c.d = 3.14;

    // 以下、型を気にせずに共通の演算ができる（print, add）.
    VarPrint(a);
    VarPrint(b);
    VarPrint(c);
    d = VarAdd(a, b); // d = "2hello" になる.
    ...
}

この中で、VarPrint()やVarAdd()は内部にif（もしくはswitch～case）を持っていて、型に合わせて適切な処理が実行されます。
そしてこの「型に応じた処理のための分岐」が、実行速度を目に見えて下げてしまうことになります。それが動的型付き言語の弱点だと言われています。

こんなプログラムでも、もし構造体のメンバに対しても「この文脈では〇〇になるはず」という処理ができるようになれば、関数をインライン展開することで、「型に応じた処理のための分岐」の多くを省略できるようになって、静的型付き言語に匹敵する速度が出せるようになります。

ということで、上記の(3-1)～(3-4)の最適化だけでも、十分に面白い成果が期待できるのです。
どうかその雰囲気が伝わりますように・・・。

↑

こめんと欄

コメント	お名前	NameLink