古典的最適化

最適化には独立した2つの問題がある。変換が正当かどうか、そして正当な変換が価値があるかどうかである。命令が1つ減る、呼び出しが1回減る、あるいはソースコードが少なくなるだけでは、これらの問題に自動的に答えは出ない。正当性はソース言語およびIRのセマンティクスに依存し、利点はターゲットとワークロードに依存する。

これらの最適化はSSA上でのみ実現できるものではなく、すべてが統一的な線形時間計算量を持つわけではない。SSAは明示的なdef-useなどの利便性を提供するものの、実際のアルゴリズムは制御フロー、エイリアス、コスト、およびコンパイル時間の予算にも関わる。

定数畳み込みと伝播

畳み込みは、コンパイル時に既知の式の値を計算する。例えば整数 2+3 は 5 になる。伝播は既知の定数を使用箇所へ運び、さらに多くの畳み込みをトリガーする。SCCPはさらに、実行可能な制御フローエッジを追跡し、定数条件を用いて不可能な分岐を除外する。

x*0→0 は代数簡約であり、すべてのオペランドが定数である畳み込みではない。その正当性はセマンティクスに依存する。IEEE浮動小数点におけるNaN、無限大、符号付きゼロは、実数の代数恒等式のいくつかを破綻させる可能性がある。また、xが副作用を持つ式に由来する場合、その評価を削除することも正当性を証明する必要がある。LLVM IRにおけるpoison、undef、および関連フラグにも独立したルールがある。LLVM UBマニュアル

SSAにおける唯一の静的定義は、値が必ずしも定数であることを意味しない。φ関数とループでは依然として解析が必要である。条件伝播は、削除される分岐が言語フロントエンドにおいて常に構文解析や型チェックを必要としないことを意味しない。

CSEとGVN：再利用可能な値を見つける

2回の b+c が、演算セマンティクス、オペランド、および可視状態と一致している場合、後者は前者の結果を再利用できる可能性がある。既存の値は、それを必要とするパス上で利用可能でなければならない。if文の左側でのみ計算される値を、右側の計算に直接置き換えることはできない。

GVNは値番号付けを用いて同値関係を特定し、文字通りの式マッチングよりも強力な場合がある。loadを処理する際には、その間にエイリアスする可能性のある書き込みや呼び出しによってメモリが変更されていないことを証明する必要がある。2つの命令がテキスト上同じでも、読み取られる状態が異なる場合は、置換可能な値ではない。

再利用は、ある結果の生存期間を延長し、レジスタ圧力を高める可能性があるため、正当なCSEが常に高速化を保証するわけではない。

同じloadでも、間にエイリアスする可能性のあるstoreがある場合

以下の2回の読み取りはソースコードがともに *p であるが、qは同じオブジェクトを指す可能性がある。p=qであり初期値が3の場合、1回目は3を読み取り、7を書き込んだ後、2回目は7を読み取るため、結果は10になる。1回目の読み取りを直接再利用すると、誤って6を計算してしまう。

/* alias.c */
static int original(int *p, int *q) {
    int before = *p;
    *q = 7;
    return before + *p;
}
static int wrong_reuse(int *p, int *q) {
    int before = *p;
    *q = 7;
    return before + before;
}
int main(void) {
    int a = 3, b = 3;
    if (original(&a, &a) != 10) return 1;
    if (wrong_reuse(&b, &b) != 6) return 2;
    a = 3; b = 0;
    if (original(&a, &b) != 6 || b != 7) return 3;
    return 0;
}

この反例はエイリアス規約に違反していない。2つのポインタ関係は、関数が許容する入力すべてに含まれる。インターフェースがさらにrestrictなどの約束事を使用する場合、最適化器はより強力な事実を利用できる可能性があるが、呼び出し側も対応するルールを満たす必要がある。関数に勝手に約束事を付与し、原本許容されていたエイリアス呼び出しを依然として同値性テストとして扱うことはできない。

2回の同じloadでも、読み取るのは同じ状態なのか？

この変換に必要なのは、中間の書き込みによって影響を受けないという証拠であり、ある1つの数値が偶然一致していることではない。qをAを指し、書き込む値も3に設定すると、2つのプログラムは同様に6を返すが、エイリアスのリスクは消えていない。さらに7に変更すると、反例がすぐに現れる。qが独立したBを指す場合、そのstoreはAを変更しないため、本例における2回目のloadに再利用の根拠が生まれる。

DCEとDSE：結果が使われないからといって、振る舞いを削除できるわけではない

純粋な計算結果に使用箇所がない場合、再帰的に削除できる。そのオペランドの定義も、それに伴ってデッドコードになる可能性がある。副作用、例外、同期、および制御フローのセマンティクスは、保持するか、または別途証明する必要がある。

storeはSSAの使用箇所がないからといって削除できるわけではないが、後続で完全に上書きされ、その間に観察がない場合、DSEはデッドな書き込みを削除できる。関数呼び出しも常に削除できないわけではない。関連する効果、終了、および例外の属性が許す場合、結果を使用しない呼び出しは削除される可能性がある。逆に、「メモリを読み取っているだけに見えるから」という理由で自動的に削除できるわけではない。

インライン展開：文脈を露出させ、単にcallを消すだけではない

呼び出される関数の本体を呼び出し箇所に導入することで、定数パラメータ、エイリアス関係、および制御フロー条件を後続の最適化に参加させられる。コストには、コードの膨張、コンパイル作業、命令キャッシュ、およびレジスタ圧力が含まれる。

1回しか呼び出されない関数はインライン展開に非常に適している可能性があるが、元の定義を削除できるかどうかは、エクスポートやアドレスのエスケープなどに依存する。再帰的な呼び出しにも展開の制限が必要である。実際の判断は、コストモデルに基づいて呼び出し単位で行われ、「すべての小関数を必ずインライン展開する」わけではない。

LICM：値の不変性と実行の早期化は安全に分離して証明する

ループ不変量のオペランドはループの反復中に変化せず、関連するメモリもループによって書き換えられてはならない。しかし、preheaderへの移動は実行条件を変更する。ループは0回実行される可能性があり、元の命令が条件分岐内にある場合もある。

正当な外しには、命令が安全に予測実行可能であることを証明するか、または必須の実行条件や他の制約を通じて、早期化が振る舞いを変更しないことを証明する必要がある。loadではアドレスの有効性とエイリアスを考慮し、除算では例外セマンティクスを、呼び出しでは効果を考慮する。「副作用がない＋オペランドが不変」だけでは、すべての制限を完全にカバーできるわけではない。

外し後、元の使用者が必要とする値を保持する必要がある。元の代入を直接削除し、後続のuseに接続しないのは、誤った教育的変換である。

明確な例外セマンティクスを用いて0回のループを検証し、実行ガードを追加する

C言語の除算ゼロにおける未定義動作に依存しないよう、以下のPythonの整数除算と例外セマンティクスを用いて教育的モデルを構築する。非負のループ回数だけを考慮する。原版とガード付き外し版は、結果と例外において同じであるべきである。ガードなし版は n=0、d=0 の際に追加でエラーを投げるため、反例となる。

def original(n, d):
    total = 0
    for _ in range(n):
        total += 10 // d
    return total


def hoisted(n, d):
    if n == 0:
        return 0
    value = 10 // d
    total = 0
    for _ in range(n):
        total += value
    return total


def wrong(n, d):
    value = 10 // d
    return sum(value for _ in range(n))


def outcome(fn, n, d):
    try:
        return ("value", fn(n, d))
    except ZeroDivisionError:
        return ("error", "division by zero")


for n in range(5):
    for d in (-2, 0, 2, 3):
        assert outcome(original, n, d) == outcome(hoisted, n, d)
assert outcome(original, 0, 0) == ("value", 0)
assert outcome(wrong, 0, 0) == ("error", "division by zero")

ガードの有効性は、本例の具体的な構造に依存する。除算はループに入るたびに必ず実行される純粋な計算であり、dは不変であり、それより前に発生しなければならない効果はない。除算がループ内の別の条件分岐に隠れている場合、n>0 であることを証明するだけでは外しに不十分である。他の操作が先に例外を投げる可能性がある場合、言語が要求する例外の順序関係を保持する必要がある。この修正を任意のLICMの統一テンプレートとして一般化することはできない。

オペランドが不変なのに、なぜ直接ループの外に移動できないのか？

結果、例外、および除算の回数をそれぞれ列挙するのは、まず正当性を判断し、次にどれだけ作業を節約できるかを議論するためである。n=0、d=0 が重要な反例である。原版では除算が実行されないが、ガードなし版では提前に例外を投げる。ガード付き版は、この制限されたループにおいて元の実行条件を回復する。表の回数は除算の試行のみを数えており、総命令数や実際の所要時間ではない。

ループ展開：コードサイズと引き換えに、制御と並列の機会を得る

部分的な展開では、いくつかの反復体をコピーし、残りの反復を処理する。完全な展開には、決定可能な有限の反復数、または対応する特殊化条件が必要である。未知の回数でも、尾部処理を伴う部分的な展開を行うことができる。

展開は、バックエッジのオーバーヘッドを削減し、命令レベルの並列性を露出させたり、ベクト化を助けたりする可能性がある。一方で、コードサイズが増加し、スピル（レジスタ溢れ）も発生する可能性がある。すべてのLLVMターゲットに対して固定で2〜4回展開するというルールはなく、連続するスカラーloadが自動的に正当なSIMD loadになるわけではない。境界、アラインメント、依存関係、およびターゲットの能力は依然として確認する必要がある。

SROAとmem2reg：ローカルなメモリ状態を解析しやすくする

アドレスがエスケープせず、アクセスが理解できるローカルな集約オブジェクトは、アクセスする範囲などに従って分解でき、不要な集約メモリ操作を削減できる。適したローカルスロットはSSA値に昇格させることができ、制御フローの合流点でφ関数で表現する。

SROAは機械的に「1フィールド＝1変数」とする必要はなく、いくつかの使用は分解を妨げる可能性がある。また、いくつかの実装では直接昇格を完了できる。mem2regは、もともとスカラーである適切なallocaも処理でき、すべてのシナリオでSROAを経る必要はない。LLVM Passの説明

Passの順序：機会と無効化は同時に発生する

インライン展開は定数を露出させ、定数伝播は分岐を削除し、分岐の削除はより多くのコードを無用にする。展開はループ構造を変更し、後続のクリーンアップは式をさらに簡素化する。いくつかの変換を繰り返すことは価値があるが、コンパイラは無限に飽和を追求せず、時間、サイズ、および分析の無効化を制御する必要がある。

CFGを変更した後、支配木、ループ情報、またはメモリ解析はもはや有効でない可能性がある。変換は、関連する分析を正しく維持するか、無効化を宣言しなければならない。出力IRが表面的に合法に見えるだけにしてはならない。

検証とクイックリファレンス

IR検証子、反例テスト、変換前後の差分、および特定の範囲での同値性検証を組み合わせることができる。テストには境界パスを含める必要があり、単に1つの正常な入力で出力が一致するだけでは不十分である。パフォーマンスを測定する場合は、最適化パイプライン全体の後のターゲットコードを観察する必要がある。

参考文献

• LLVM Analysis and Transform Passes。
• LLVM IR Undefined Behavior。

Keywords: optimization, constant propagation, SCCP, CSE, GVN, DCE, DSE, inlining, LICM, unrolling, SROA, mem2reg