SSA形式を実装してみた！力技で挑むコンパイラ最適化の獣道

2025-03-01
#compiler #optimization

趣味でコンパイラのバックエンドを作っているが現状最適化はほとんどできてない。 最適化をしやすくするために静的単一代入を導入しようとして手間取っているのでメモ （力任せに実装しただけなので真偽は不明です）。

静的単一代入とは

変数への再代入がなければ変数名を追うだけでどんな値が入っているのかが判明するので便利。 静的単一代入（Static Single Assignment, SSA）形式は再代入があったら変数の別バージョンを作ることで再代入を除去して、最適化を行いやすくする。

例えば

a = 1;
x = a + 1;
a = 2;       // 再代入
y = a + 1;

というコードで字面上はxもyもa + 1を代入しているが途中でaの値が再代入で変わっているために実際には値が異なる。 これを、再代入しているaを別バージョンにしてやれば

a = 1;
x = a + 1;
a2 = 2;      // 再代入された変数を別バージョンにする
y = a2 + 1;  // 以降は新しいバージョンを使用

となって別物だということがすぐにわかる。

Φ関数

SSA形式では再代入が不可だが処理の分岐で異なるバージョンが合流する場合にどうするかというと、Φ関数という疑似的な命令を挿入する。例えば

if (condition)
  x = 1;
else
  x = 2;
// xの値は？

というコードを

if (condition)
  x1 = 1;
else
  x2 = 2;
x3 = phi(x1, x2);  // <-Φ関数を挿入

として、x3は上の条件分岐を通ったらx1、下を通ったらx2が選ばれるものとする （疑似的なので実際にこのまま実行するわけではない）。

SSA化されてどの変数も代入が一度限りということになっていれば、さまざまな最適化がしやすくなる。

SSA形式への変換

SSA形式に変換するにはどうするか。 論文では支配辺境がどうだとかいってよく理解できないので、再代入時に別バージョンを割り振ればいいんでしょと力任せにやってみた。

前段階として、レジスタ割付をするための各仮想レジスタの生存範囲を調べる方法を実装済みで、 そのため各基本ブロック（Basic Block, BB）に流入するレジスタと出力するレジスタが把握できる。

再代入は当然として、それ以外にも合流するBBでも別バージョンを作る必要があるので、合流するBBに流入するすべてのレジスタに別バージョンを用意する。 合流なしで一本道で遷移するBBでは前のBBから出力されるバージョンをそのまま使う。

BBに流入するレジスタのバージョンが判明したので、そのBB内のレジスタをそのバージョンに置き換える。 BB内で再代入があった場合には更新する。

ということをBBを辿れる順に行うことで全BBが出力するレジスタのバージョンを決定する。

  • 本当なら合流するどちらのパスでも代入がない変数はバージョンを更新する必要がないので、この方法では無駄に作られてしまうという欠点がある

Φ関数の挿入

合流するBBで流入するレジスタに対して、合流の遷移元から出力するバージョンを集めてΦ関数の引数とする。

SSA形式での最適化

SSA形式に変換できたら最適化を適用できるので、試しにいくつか実装してみた。

コピー伝播

変数に代入された値は再代入されず変わらないので、単なるコピーであればそのコピー元の変数に置き換えてしまうことができる(Copy propagation)。 一番上の疑似コードはaとa2をコピーして

//  a = 1;
    x = 1 + 1;
//  a2 = 2;
    y = 2 + 1;

とすることができる。 コピー元の変数は使われなくなるので削除することができる。

  • Φ関数のすべての引数が同じ値・変数であれば、同様にコピーできる

定数畳み込み

コピー伝播によって定数同士の演算式になった場合、実行時ではなくコンパイル時に計算してしまうことができる(Constant folding)。

x = 2;
y = 3;

SSA形式から戻す方法

最適化を適用した後にマシン語を出力する際にはΦ関数が残ったままでは困るので元に戻す必要がある。 戻すにはΦ関数のBBへの遷移元に目的レジスタへのコピー命令を挿入してやる。

ただ合流元BBからの遷移が条件ジャンプだと条件が不成立で遷移しない場合にもコピー命令が実行されてしまってまずいので、その場合には新たなBBを挿入することにした。

並列でコピーする必要がある件

Φ関数解決時のコピー命令は並列で行う必要がある。 理由は最適化の結果、Φ関数の代入先が別のΦ関数の引数として使われている可能性があるため。 例えばループ中に変数をスワップ、

a = 1;
b = 2;
for (int i = 0; i < 10; ++i) {
  t = a;
  a = b;
  b = t;
}

などというコードをSSA化、

bb0:
  a = 1;
  b = 2;
  i = 0;
  goto bb2;
bb1:
  t = a1;
  a2 = b1;
  b2 = t;
  i2 = i1 + 1;
bb2:
  a1 = phi(a, a2);
  b1 = phi(b, b2);
  i1 = phi(i, i2);
  if (i1 < 10) goto bb1;
bb3:

コピー伝播すると、

bb0:
  goto bb2;
bb1:
  i2 = i1 + 1;
bb2:
  a1 = phi(1, b1);  // <- b1とa1がΦ関数の代入先かつ引数にも登場
  b1 = phi(2, a1);  // <-
  i1 = phi(0, i2);
  if (i1 < 10) goto bb1;
bb3:

単純に順番にΦ関数を解決すると、

bb0:
  a1 = 1;
  b1 = 2;
  i1 = 0;
  goto bb2;
bb1:
  i2 = i1 + 1;
  // vvv
  a1 = b1;  // <- ここでa1が更新されてしまって
  b1 = a1;  // <- b1が旧a1にならない
  i1 = i2;
  // ^^^
bb2:
  if (i1 < 10) goto bb1;
bb3:

となってしまって誤動作してしまう。

解決法は実際には並列に行う必要はなくて、Φ関数の代入での循環を検出して、テンポラリ変数に代入してやる：

bb1:
  ...
  a1_bak = a1;  // a1とb1が循環しているのでテンポラリ変数に待避する
  a1 = b1;
  b1 = a1_bak;  // 退避した変数から復帰
  ...

つまづいている箇所

SSAを適用すればパフォーマンスが向上するわけじゃなく、現状SSAを有効にできてない。

変数爆増による性能劣化

SSAへの変換によって使用する変数が増えてしまうため、後にマシン語に変換する際に問題になる。 実際のマシン語に出力する場合に変数を物理レジスタに割り付ける必要があるが、使用する変数が増えると必然的にレジスタ割付から溢れるものが増えてしまうため性能が劣化してしまう。

対策としてはレジスタの生存期間を最初から最後までではなく途中の穴を考慮してやったり、分岐で別バージョンになる同変数をうまく同じ物理レジスタに割り振れるようにするなどの必要があるのではないかと思う。

共通部分式除去（適用できず）

SSA形式で適用できる最適化として共通部分式除去 (Common Sub-expression Elimination)がある。 ２つの式が同じ演算式であれば、２つ目の計算は１つ目の値に置き換えることができる。

喜び勇んで実装してみたが、部分式の計算をするパスを通らない可能性があるということを見落としていた。 なのでこの最適化を適用するには、後の計算の場所に来るには前の計算が必ず行われることを確認する必要がある。 がわかってないので保留…。

現状のコード

関連記事

新着記事