ハクソク

世界を動かす技術を、日本語で。

なぜSSAコンパイラなのか？

215日前原文(mcyoung.xyz)

概要

  • SSA（Static Single Assignment）は最適化コンパイラで広く利用される中間表現（IR）の一種。
  • 主要なコンパイラ（LLVM、GCC、Go、CUDA、Swift、MSVC、HotSpot C2など）がSSAを採用。
  • SSAは各変数が一度だけ代入されるという特性で、プログラム解析・変換を容易化。
  • 複雑な命令列や制御フローも、SSAを用いることでグラフ理論的手法で最適化可能。
  • 本記事ではSSAの概念、利点、変換方法、IR設計例などを解説。

SSAコンパイラとその特徴

  • SSA（Static Single Assignment） は、 最適化コンパイラ で中心的に使われる 中間表現（IR）。
  • LLVM、GCC、Go、CUDA、Swift、MSVC などの ahead-of-time 型、 HotSpot C2、V8、SpiderMonkey、LuaJIT、Android Runtime などの just-in-time 型コンパイラで採用。
  • SSA では、 各変数が一度だけ代入 されるため、 プログラム解析・変換 が効率的。
  • 多くの 最適化処理 （データフロー解析、定数畳み込み、デッドコード除去等）をシンプルに実現。
  • SSA IR は、 表層言語 や アセンブリ言語 とは異なり、 最適化に特化した表現。

命令型コードと最適化の難しさ

  • 命令型プログラム は、状態変化の連続で目的の結果を得るスタイル。
  • 変数の 再代入 や 順序依存 があるため、 全体のデータフロー解析 が困難。
  • 例：Cコードで複数回代入される変数a, bの追跡と最適化の難しさ。
  • SSA変換 により、各変数の値が一意に決まり、 依存関係グラフ として表現可能。
  • これにより、 グラフ理論 の手法（DAG解析等）で効率的な最適化が実現。

SSAの基本概念と利点

  • SSAの不変条件 ：各変数は 一度だけ定義 される。
  • これにより、 命令間の依存関係 が明確化し、 回路図（DAG） のような構造に。
  • 基本ブロック ：制御フロー命令以外の命令列＋終端命令で構成される単位。
  • 制御フローグラフ（CFG） ：基本ブロック間の遷移関係をグラフ化。
  • SSA-CFG ：基本ブロック＋SSAの組み合わせで、解析・最適化が容易。

phiノードとブロック引数

  • phiノード ：複数の前段ブロックから値を選択する特殊命令。
  • 例：ループの繰り返しで、どの経路から値が来たかに応じて変数を決定。
  • LLVM IR はphiノードを利用、 MLIR などはブロック引数方式を採用。
  • phiノードは 前段ごとに異なる値を選択 し、SSAの不変条件を維持。

SSA IRの設計例（Fibonacci関数）

  • CのFibonacci実装をSSA-CFG IRに変換する例。

    • 関数宣言、 基本ブロック、 gotoによる制御フロー、 ブロック引数 で構成。

  • 各ブロックは 引数として変数を受け取る ことで、再代入を避ける。

  • goto 命令で制御を次のブロックへ移動、各ブロックは 関数のように振る舞う。

  • phiノード方式 では、各ブロックの変数は前段ブロックからの値をphiノードで選択。

    • 例（phiノード式）： 
      %n = phi { @entry -> 0, @loop.body -> %n.2 }

SSA変換の実際

  • 変数の 再代入 をすべて 新しい変数名 に置き換え、 各ブロックで引数として受け渡し。
  • メモリ管理が必要な場合は、 スタック領域を明示的に宣言・利用 する手法も。

    • 例：%np, %ap, %bp などの スタックスロット を宣言し、load/store命令でアクセス。

    • 例（スタック利用SSA IR）：

      %np = stack i32
store %np, %n
...
%n = load %np

SSAのまとめと意義

  • SSA IR は、 データ依存性が明確 で、 最適化アルゴリズムの適用が容易。
  • 複雑な制御フロー や 変数の再代入 も、SSA化により単純なグラフ構造へ。
  • 現代の多くのコンパイラ がSSAを採用し、最適化技術の基盤となっている。
  • SSAの理解 は、 最適化コンパイラ設計 や プログラム解析 の基礎。

Hackerたちの意見

ブログのスタイルは好きだけど、ちょっと気になるのは、最初にSSAの定義を入れてほしいってことかな。SSAについて結構長く話してるけど、「SSAは中間表現（IR）の特性です」とか、「よく使われます」とか言って、実際にSSAが何かを定義するのは10段落も下の方なんだよね。> SSAは「静的単一割り当て」の略で、80年代に既存の三引数コード（すべての文がx = y op zの形）を強化するために開発されたんだ。これによって、すべてのプログラムが回路のようになり、上で説明したのと非常に似た手法を使うようになったんだ。これが「知らないならこの投稿は君のためじゃない」っていうのは分かるけど、いい記事だと思うし、詳細に不慣れな人たちも興味を持てるんじゃないかな。> これがうまくいく理由は、変異を持つ関数を取り、それを状態を持たない組み合わせ回路に変換したからなんだ。デジタル論理回路の一種で、分析がすごく簡単なんだよね。面白い洞察だと思った。SSAにはバイトコードの逆コンパイルやコンパイラのデバッグでしか関わったことがなかったから、なぜ必要なのかは知らなかったけど、これで納得できたよ。

└

この投稿は正直、今まで読んだSSAに関する最も複雑な議論の一つだと思う。情報はたくさんあるけど、実際に実装に関する論文を見直すことを勧めるよ。最初にSSAに出会ったのは、WirthのOberonコンパイラに追加する論文だったけど、もっと分かりやすかった。編集：これがBrandisとMössenböckの論文だよ：https://share.google/QNoV9G8yMBWQJqC82

└

コンパイラの授業で少しSSAについて学んだよ。他にもたくさんのことがあるけど、レジスタ割り当てには欠かせないんだ。存在するそれぞれの異なる値と、その値のライフタイムを知って、各値にレジスタを割り当てる必要があるんだ。もし同時に存在する異なる値の数がレジスタの数を超えたら、スタックに押し込むことになるよ。

└

SSAについて簡潔に説明すると、通常の（命令型）コードは最適化が難しいんだ。なぜなら、一般的に命令は純粋じゃないから。もし命令に副作用があったら、その命令を最適化するために、例えば以下のことをするのが難しくなるんだ。1. その命令を削除する（デッドコード削除） 2. その命令を重複排除する（利用可能な式） 3. 他の命令と順序を入れ替える（ホイスティングやループ不変コードの移動） 4. その命令を複製する（他の最適化を可能にするために役立つことがある） これらの最適化はコンパイラにとって非常に重要で、プログラムを操作する際に副作用を気にしなくて済むなら、実装がずっと楽になるんだ。だから、SSAのポイントは、プログラムを副作用ができるだけ少ない同等のプログラムに変換することなんだ。結果的に、見た目は関数型プログラムに似ていることが多いよ。（詳しくは、コンパイラコミュニティで有名なこの論文を見てみてね： https://www.cs.princeton.edu/~appel/papers/ssafun.pdf）実際、基本ブロック自体を関数として見ると、phiノードは基本ブロックの引数を「宣言」していて、分岐は対応する値を持つ次の基本ブロックをテールコールすることに対応しているんだ。これがMLIRにおける基本ブロックの引数の動機になっている。 「組合せ回路」という比喩は少し間違っているけど、ほとんどのSSA実装は、任意のメモリへのロードやストア、あるいは任意の関数呼び出しの状態を考慮する必要があるからね。また、任意の長さのループを（有限の）組合せ回路としてモデル化するのは簡単じゃない。著者がAIアクセラレータの会社で働いていることを考えると、その比喩に傾く理由がわかるけどね。

└

その動機や理由も間違っているよ。優しいイントロだとは理解しているけど、あまりにも歴史を改変するようなことはしなくてもいいと思う ;) ケン・ザデックは何年も私のオフィス仲間だったから、これは私の記憶だけど、数十年経っているから、間違いがあったらごめんね :) 彼らがなぜうまくいったのかという理由は確かに間違っている - 彼らはSSAの書き換え形式を使っていなかったし、長い間使わなかったんだ。最初の「完全なSSA」コンパイラ（一般的にopen64と考えられている）でさえ、IRをSSAに書き換えなかった。うまくいった理由は、効果的な変数ごとのデータフローを実行できるようにしたからなんだ。実際、これが解決する唯一の問題で、すぐに変数ごとのデータフローを迅速に実行する能力なんだ。これは当時の歴史的文脈から見れば明らかだったけど、今は歴史になってしまったからあまり明らかではないね :) 最も単純な本質として、SSAは変数のデータフローのチェーンを非常に簡単にたどることができるようにしているんだ。それが私が言いたかったことだと思う。確かに、単純なスカラー・プログラムの場合、変数名の再利用がこれらのデータフローのチェーンを壊すのは主に明示的なミューテーションポイントで起こるけど、これはコンパイラのIRによって常に正しいわけではないし、メモリに拡張するときなどは絶対に正しくない。SSAが可能にすること（迅速な変数ごとのデータフロー）を他の問題クラス（SSU、SSIなど）に拡張するのも全く正しくない。歴史的に見ると、この投稿はSSAがどこからともなく現れて、誰も考えたことがない革命的なものだったかのように暗示しているけど、実際には彼らがしばらく取り組んできた変数ごとのデータフローの試みの形式化だったんだ。私はおそらく、優しいイントロとしてそれを言うだろうけど、歴史の残りを知りたいなら、ここにあるよ：SSAのずっと前から、ビットベクターデータフロー（当時のSSAの主流アプローチ）の下限があまり良くないことは知られていた。年月が経つにつれて、当初の予想よりもずっと良くなったことが判明したけど、結局はプログラムが大きくなるにつれて誰もが望んでいたよりも悪くなってしまった。ほとんどの問題に対してN^2またはN^3のビットベクタ操作が必要だった。インクリメンタリティは基本的に不可能だった[2]。関連する変数間の依存関係のため、理解したりデバッグしたりするのも難しかった。より速くて良いデータフローの試みは、2つの大まかな形で存在していて、どちらも同じ下限には縛られていなかった：1. 構造化データフロー/区間解析アルゴリズム/排除データフロー - CFGをさまざまなタイプの領域に減らし、既知の方程式系を解き、その結果を領域に分配する。これは還元可能なグラフでうまく機能する。注意深く行えばインクリメンタルに実行できる。これはビットベクターと並行して主に研究されていて、急速なデータフロー問題のクラスがあることが知られる前に多く考えられていた（IE 70年代後半以前）。領域方程式を十分に理解してデバッグするには、データフローの基礎（ラティスなど）を非常に深く理解する必要がある。その意味では、ほとんどの人にとってビットベクターよりも理解するのが難しかった。グラフの還元性の制限は面倒だったけど、ノードを分割することで前方グラフでは扱いやすかった（研究によれば、当時のプログラムの90%以上はすでに還元可能なフローネットワークを持っていた）。しかし、ほとんどの後方CFGは還元不可能で、後方データフロー問題は非常に面倒だった。結局、反復データフローが証明可能に速くなり、コンパイラが理論の専門家だけのものではなくなったとき、このようなものは消えてしまった[3]。もしコンパイラ理論のオタクになったら、実際に見ると面白いと思うよ。2. 変数ごとのデータフローアプローチ。これは基本的に「すべての変数を一度に解くのではなく、単一の変数または変数のクラスのデータフロー問題を解く」ということだ。実際には、これが実用的なアプローチになるとは考えている人はあまりいなかった：a. 到達定義（例えば）を一度に1つの変数で解くというアイデアは、すべての変数を一度に解くよりもずっと遅くなるように思えた。b. 変数を効果的に分割して、1つの変数（または変数のクラス）で問題を計算できるようにする方法は非常に明白ではなかった。もしこれをうまく機能させることができれば、かなり速いインクリメンタルデータフロー解決が得られるだろうというのは当時明らかだった。SSAはこのアプローチから生まれた。ケニーの論文はインクリメンタルデータフローと分割変数問題を扱っていて、さまざまな分割/クラスタリングされた変数問題の時間的制約を証明した。SSAの基礎は、物事を考える方法に見ることができる。ここでいくつかの部分から引用するよ：「変数ごとのDefサイトの密度が増すにつれて、各変更の影響を受ける領域の平均サイズは減少する...」。彼の論文は（他のことの中で）当時の典型的な方法（IE SSAではない）でこれを行うためのメカニズムについて述べている：「パフォーマンスを向上させるために使用されるメカニズムは、各変数のDefサイトの密度を上げることだ。UseとDefの密度を増やす最も明白な方法は、プログラムフローグラフの削減を試みることだ。この削減は、ノードのグループを単一の新しいノードに置き換えることになる。この新しいノードには、そのノードのグループを通過する実行の影響を要約した情報がラベル付けされる。」これは、支配関係に基づいて変数を分割する方法が知られていなかったからで、これがまさにSSAなんだ。そして、ケニーは太陽の熱的死の前に論文を終わらせたかったんだ。この意味で、彼らは「正しい数の名前」を変数に与えれば、ほとんどの問題（到達定義など）に必要なデータフロー計算が非常に小さくなり、変更が簡単に処理できることをすぐに理解した。彼らは、解決したいデータフロー問題について、各変数が単一の到達定義を持つ必要があることをすぐに知っていた（到達定義はよく知られていた）など。SSAは、そこから変数のクラスタリング/パーティショニングを見つけることに至るインクリメンタルな集大成だった。これは、正式に構造化された制御フロー領域（すべての変数に関するもの）に基づくのではなく、特定の変数に対するローカルデータフローに基づいており、特定の変数に対するローカルな結果に影響を与えるCFG構造の部分を取り入れている。これは体系的にアプローチされていて、必要な特性を理解し、それを解決するアルゴリズムを見つけることなどを行っていた。多くの予想外に有用なものが世界を席巻することになるように

└

そうだね、これがますます問題になってきてるのがわかる。記事で初めて使う頭字語や略語はちゃんと説明するのがいい習慣だし、ウェブだから、ウィキペディアの記事にリンクを貼るのも簡単だよね。自分で説明を加えたくないなら、そういうのを使えばいいんだし。

└

でも、これが何のためのものかはあまり説明できてないと思う。私の説明をするね（私の博士論文からの引用だけど）：静的単一代入（SSA）形式は、プログラム解析のための効率的な中間表現を提供するんだ [Cytron et al., 1989, 1991]。データフロー解析を効率的に表現する方法として導入されたんだ。SSAは一つの重要なアイデアを使ってる：プログラム内のすべての変数が名前を変更されて、各変数がプログラム内の一つのユニークな文で値を割り当てられるようにすること。この重要なアイデアから、SSAは他のデータフロー解析技術に対していくつかの利点を提供できるんだ。定義-使用チェーンの要素分解：定義-使用チェーンを使うと、データフローの結果が変数の割り当てからそのすべての使用に直接伝播されるんだ。でも、定義-使用チェーンは、各定義から各使用へのエッジが必要で、同じ変数の定義と使用が多いプログラムではコストがかかることがある。実際には、スイッチ文があるときにこれが発生する。SSAはφノードを介して定義-使用チェーンを要素分解することで、この病的なケースを回避するんだ。フロー感度：SSA形式で行われるフロー非感度アルゴリズムは、SSA形式が使われない場合よりもはるかに精度が高いんだ。同じ変数への複数の定義のフロー非感度問題は、単一代入プロパティによって解決される。これにより、フロー非感度アルゴリズムはフロー感度アルゴリズムの精度に近づくことができる。メモリ使用量：SSA形式がないと、解析はプログラムのすべてのポイントで各変数の情報を保存しなければならない。SSA形式を使うと、プログラム内の各割り当ての情報だけを保存すればいいスパース解析が可能になる。各割り当てごとにユニークなバージョンがあることで、解析結果を保存するためのメモリ使用量は、ビットベクタやセットベースのアプローチを使うよりもかなり少なくなることがあるんだ。

驚くべき真実は、SSAは関数型なんだ！そう、君の好きな命令型言語のコンパイラは実際に関数型プログラムを最適化してるんだよ。例えば、これを見てみて：https://www.jantar.org/papers/chakravarty03perspective.pdf。実際、SSA、継続渡しスタイル、ANFは基本的に同じことなんだ。

└

SSAについての経験はすごく限られてるから、もしかしたらバカな質問かもしれないけど、メモリが関わるとどうなるの？昔触ったllvmのチュートリアルでは、「すべてを割り当ててmem2regを信じればいい」って感じで、ユーザー視点からはほぼSSAが抽象化されてるように見えたんだよね。

└

いや、そうじゃないよ。関数型言語の本質は、名前がラムダによって作られ、ラムダがファーストクラスで、同じスコープ内でXへの2つの参照が異なる値を持つ2つのインスタンスを参照することがあるってことなんだ。一方、SSAの本質は、名前が必ず自己エイリアスしなきゃいけないってこと（同じスコープ内で2回参照されたXは必ず同じ値を返す）。他にも興味深い違いはたくさんあるけど、最も重要な違いは、SSAやCPS、ANFを実装するときに、スキルの移転の機会がほとんどないような、全く異なるものになることなんだ（SSAのコンパイラハッカーなら、CPSのコンパイラではまるで魚が水から出たように感じるだろうね）。みんな「かわいい」論文を書きたがるけど、聞こえはいいけど本当じゃないことが多いんだよね。

└

同じことは分からないけど…昔、SSAとCPSが同型だって読んだ記憶があるんだ。基本的にCPSは関数型言語で使われるものだよね。編集：実際、ここでも話題になってるけど、CPSは形式的にSSAと同等だよね？CPSを使う利点は何なのか… | Hacker News https://share.google/PkSUW97GIknkag7WY

コンパイラのことは忘れて、SSAは人間にとっても読みやすさを大幅に向上させる価値があるよ。

こういうクリーンなSSAの解説を見るたびに、「SSAのシンプルさ」って、ミューテーションが悪だと決めたからこそ存在するんだなって思う。SSAがシンプルってわけじゃなくて、状態が存在しないふりをするように、最適化パイプライン全体を設計してるんだよね。これは素晴らしい幻想だけど…エイリアシングやメモリモデル、並行性にぶつかると、あっという間に美しいDAGがphiノードとロード/ストアの地獄に崩れ落ちる。

└

SSAの魅力は、いくつかの最適化が終わった後にロード/ストアの地獄を先延ばしにできるところなんだよね。状態が存在しないふりをすることで、そういう最適化がずっと考えやすくなるんだ。

└

逆だよ。現代のコンパイラがSSAを使うのは「シンプルだから」じゃなくて、すごく速いデータフロー最適化（定数伝播、CSE、レジスタ割り当てなど）ができるからなんだ。そうじゃなきゃ多くの状態が必要になる。SSAは「状態が存在しないふりをする」わけじゃなくて、実際にはコンパイラが状態の変化を扱うのを可能にするものなんだ。証拠として、Haskellは不変性を強制する言語だけど、そのコンパイラであるGHCはメインの中間表現にSSAを使ってない。実際にはその不変性に依存する「スピンレスタグレスgマシン」のグラフ表現を使ってる。SSAは変化する形に落とし込まれた後に初めて現れるんだ。もし変数がミューテートされてないなら、SSAに変換する必要すらないよ！もちろん、他の方法を試してみるのもいいけど、実際にやってる人もいるし、V8のSea-of-Nodesへの移行がどうなったか見てみて。

└

状態が存在しないふりをする。機能型言語のファンとして、不変性は状態が存在しないことを意味しないよ。代入で状態を保持するんだ --- SSAでは、すべての状態に新しい名前が付けられる。関数のスコープを超えて状態を保持したいなら、それを返すか、別の関数を呼び出す必要がある（テールコール最適化ができることを願って）。あるいは、可変のエスケープハッチに隠しておくこともできる。

└

SSA形式は状態の表現なんだ。SSAはデータフロー情報を明示的にエンコードしているから、他のすべての解析パスを簡素化するんだ。エイリアス解析も含めて。

└

SSAはミューテーションが悪だと言っているわけじゃないんだ。むしろ、def-useルールを追いかけるのを簡単にするためのものだよ。ドラゴンブックでは、基本的に最初に紹介されるデータフロー解析は「到達定義」と「生存変数」なんだけど、SSAベースのIR内では、これらのアルゴリズムは基本的に「いくつかのポインタをたどる」だけなんだ。他にもいくつかの付随的な利点があって、SSAはいくつかの変数をリネームするだけで、フローに依存しないアルゴリズムを部分的にフローに依存させることができるんだ。もちろん、メモリのロードやストアについて推論できるようにするためには、これらのアルゴリズムを維持する必要があるけどね。でも、メモリ操作を仮想レジスタ操作に移行する努力をすれば（SSAを無料で手に入れることができる）、コンパイラを速くすることもできるよ。なぜなら、これらの解析を常に再実行する必要がなくなるから、特にロードやストアを排除したり移動したりすることに特化した数少ないパスのためだけに実行すればいいからね。

└

我々は変異が悪だと決めた。SSAは（主に）メモリに関心があるわけじゃなく、ローカル変数に関心があるんだ。ローカル変数のストレージを完全に仮想化するし、実際にはすべての中間計算を仮想化する。計算をデータフローのエッジでつなげて、ストレージを使わないことで、順序を考慮しない（依存エッジによって引き起こされる順序を除いて）。結局、これはCPUがレジスタの名前を変更する時にやってることなんだよ！彼らは我々コンパイラの人たちから盗んだダイナミックSSAをやってるんだ！

└

我々は変異が悪だと決めた。関数型プログラマたちは変異が悪だと決めたけど、命令型プログラマたちはそうじゃない。関数型プログラマはクレイジーなことをして、実際のハードウェアじゃないふりをするんだよね。変異する代わりに新しい変数を作ったり（無駄だよね！）、無限のレジスタを使ったり（そんな現実のマシンあるのか！？）。まあ、SSA/CPS/ANFの代替案はたくさんあるし、変異をもっと使ったものを考えるのはいつでも可能だよ。

└

なんて馬鹿げたコメントなんだ。誰も変異が「悪」だなんて言ってないよ。ただ最適化が難しいだけ。で、コンパイラが本当に機能してないかのように、偽の出力を出してるっていう話が続くのは何なんだろう。あなたの変な道徳的なトーンでコンパイラの最適化を語る人はいないから、安心して。

└

我々がそれを悪だと思っているのか、それともコード内でSSAに似たパターンを保証しながら扱いやすいからなのか？それを維持するのは比較的簡単なことだし、もっと自由にやると、非常に面倒なパスになるか、常にDFAを実行し続けることになるかもしれないね。

└

SSAは状態を隠すことじゃなくて、中間状態に名前を付けて、何らかの形でそれを参照できるようにすることなんだよ。

ちょっとした指摘だけど、描かれている乗算器は2ビットの乗算器だね。1ビットの乗算器はただのANDゲートだよ。

この記事はすごく好きだけど、「なぜSSAなのか？」って質問には答えてないね。グラフ表現は確かにいいけど、それはSSAだけの特性じゃない。SSAじゃないグラフIRもあるし、SSAは一部の最適化を簡単にするけど、他の操作を難しくすることもある。そう考えると、SSAに入ったり出たりするのが結構面倒なことを考えると、SSAがそんなに価値があるとは思えない。じゃあ、なぜSSAなのか？実はコンパイラにはシーケンシングの問題があるんだ。コンパイルを小さなコード変換の連続と見ると、表現はA -> B、次にB -> C、C -> Dと進んでいく。少なくとも、最適化しないコンパイラではそうなる。でも最適化コンパイラでは、パスがループしたいんだ。最適化が見つかるたびに、以前のパスを新しい入力で再実行する必要がある…可能ならね。これを確実にする一番簡単な方法は、すべての最適化が同じ表現を入力と出力にすることなんだ。だからA -> Bはダメなんだ。A -> A、つまり一つの表現が欲しい。だから、いい表現を選ぼうよね？ほとんどのことにうまく機能するやつ。これがSSAが役立つ理由なんだ。すべてのパスで使える、そこそこ良い一つの表現なんだよ。

静的単一代入（SSA）

一つの基本ブロックから別の基本ブロックに移る時は、ライブな値を共通の場所にコピーして、命令カウンタをジャンプさせて、その場所から値をコピーしてφノードの結果を得るんだ。関数から別の関数に移る時は、引数を共通の場所にコピーして、命令カウンタをジャンプさせて、その場所から値をコピーしてパラメータの初期値を得る。これらは同じことなんだけど、最初のケースの分岐は常にブロックの終わりにあるんだ。テールポジションにね。基本ブロック間の分岐が好きなら、それは関数間のテールコールと全く同じなんだ。ただし、いくつかのブロック引数はφノードとして表現されてるけどね。ブロックは関数だからなんだ。

https://lwn.net/Articles/84888/ GCCがSSAに移行した時のコンパイラの歴史についてのちょっとした話