Static single-assignment formってなんぞと思ったのでメモ

背景

wasm runtimeを作る選択肢としてllvmのチュートリアル（カレイドスコープ作ってみよう）を読んでいたら知らない概念が出てきたのでメモ．wikipediaを参照となっていたのでそこからスタート．(以後SSA) llvm.org

japan語で検索するなら

wikipedia 曰く

In compiler design, static single assignment form (often abbreviated as SSA form or simply SSA) is a property of an intermediate representation (IR) that requires each variable to be assigned exactly once and defined before it is used. Existing variables in the original IR are split into versions, new variables typically indicated by the original name with a subscript in textbooks, so that every definition gets its own version. In SSA form, use-def chains are explicit and each contains a single element.

コンパイラ設計において、静的単一代入形式（しばしばSSA形式または単にSSAと略される）とは、中間表現（IR）の特性であり、各変数が正確に一度だけ代入され、使用される前に定義されることを要求する。元のIRの既存の変数はバージョンに分割され、新しい変数は教科書では通常、元の名前に添え字をつけて示され、すべての定義が独自のバージョンを持つようになる。SSAの形式では、use-defの連鎖は明示的で、それぞれが単一の要素を含んでいます。

下の例がバージョンを持つこと，一度だけ代入されることの例としてわかりやすかった．

y := 1 
y := 2 
x := y

y 1  := 1 
y 2  := 2 
x 1  := y 2

use-defとdef-use

同じものかと思ったら別物だった．GPTに例を提示してもらい，自分の解釈と一致したので記載

=================以下GPT=================

使用定義チェーン（UD Chain）と定義使用チェーン（DU Chain）の具体例を以下に示します。これは簡単なコード例を通じて、これらの概念がどのように機能するかを説明するものです。

コード例

以下の簡単なプログラムを考えます：

1: int x = 5;
2: int y = x + 1;
3: x = 10;
4: int z = x + 2;

このコードを使って、UDチェーンとDUチェーンを説明します。

使用定義チェーン（UD Chain）

行2の x のUDチェーン:
- この場合、行2で x が使用されています。x の値は行1で定義されているので、行2の x のUDチェーンは行1の定義にリンクされます。
- UD(x at line 2) = {definition at line 1}
行4の x のUDチェーン:
- 行4で x が再度使用されていますが、この時点での x の値は行3で再定義されています。そのため、行4の x のUDチェーンは行3の定義にリンクされます。
- UD(x at line 4) = {definition at line 3}

定義使用チェーン（DU Chain）

行1の x のDUチェーン:
- 行1で x は5に設定されています。この定義から直接使用されるのは行2です。
- DU(x at line 1) = {use at line 2}
行3の x のDUチェーン:
- 行3で x が再び定義され（10に設定）、この値は行4で使用されます。
- DU(x at line 3) = {use at line 4}

これらのチェーンを理解することは、コンパイラがコードをどのように最適化するかを理解するのに役立ちます。例えば、もし行2と行4の間で x に関する操作がなければ、x の初期値が不変であると判断し、定数伝播を行うことができます。また、変数の生存期間やスコープを理解することで、メモリ管理の最適化も可能になります。

=================GPT終わり=================

コンパイラ最適化の文脈での恩恵

Constant propagation : 実行時からコンパイル時への計算の変換。たとえば、命令a=3*4+5をa=17であるかのように扱います。;
Value range propagation: 計算が取り得る潜在的な範囲を事前計算し、事前に分岐予測を作成できるようにします。
Sparse conditional constant propagation : 一部の値の範囲チェックにより、テストで最も可能性の高い分岐を予測できるようになります
Dead-code elimination: 結果に影響を与えないコードを削除します。
Global value numbering: 同じ結果を生成する重複した計算を置き換えます
Partial-redundancy elimination:プログラムの一部のブランチで以前に実行された重複した計算を削除します。
Strength reduction :高価な演算を、より安価だが同等の演算に置き換えます。たとえば、整数の乗算または 2 のべき乗による除算を、より安価な可能性のある左シフト (乗算の場合) または右シフト (除算の場合) に置き換えます。
Register allocation:限られた数のマシンレジスタを計算に使用する方法を最適化します。

コンパイラの最適化の例で有名な（？）なStrength reduction（べき乗をシフト計算に変換）もこれなんだーといった感じ．

golangの静的解析の文脈でもSSA

golangは学生の頃息抜きに入門したきりでやった限りで知識が怪しいが，golangは静的解析のパッケージが標準ライブラリに含まれていることは知識としては知っていた．その標準ライブラリにSSAが含まれているようなので，SSAが静的解析の文脈でどのような利用されるかはGolangのこのパッケージ経由で調べると見つかりやすそう．

pkg.go.dev

軽くDocを眺めていたら，ここでもwikipediaのリンクがあった．．．わかりやすかったしそれはそう．

http://www.dcs.gla.ac.uk/~jsinger/ssa.html.みたいに，DocのOverviewで色々紹介されているので，wikiとGoのssaのライブラリのdocを読むとざっくりわかっていいかもしれない．

まとめ

wikipediaを流し見しただけになったが，多分わかった（フラグ）のでllvmのチュートリアルを読み進めることにする．またなんぞとなったらメモを書く．

刹那的思考をメモる

AIのミトコンドリアになれるといいね