Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

[インデックス 15130] ファイルの概要

このコミットは、Go言語のコンパイラツールチェーンにおける実験的なSSA (Static Single Assignment) 形式のバックエンド開発の一環として、SSAビルダーの実装に焦点を当てています。特に、src/pkg/exp/ssa/builder.goという新しいファイルが追加され、SSA形式のコード生成の中核を担うロジックが導入されています。

コミット

commit c06a5335baf80308c0765700378826ff929db86d
Author: Alan Donovan <adonovan@google.com>
Date:   Mon Feb 4 12:22:35 2013 -0500

    exp/ssa: (#4 of 5): the SSA builder.
    
    R=iant, gri, iant, rogpeppe
    CC=golang-dev
    https://golang.org/cl/7196053

GitHub上でのコミットページへのリンク

https://github.com/golang/go/commit/c06a5335baf80308c0765700378826ff929db86d

元コミット内容

このコミットは、Go言語のコンパイラにおけるSSA (Static Single Assignment) 形式のバックエンドを構築する一連の変更のうち、4番目のコミットです。主な目的は、GoのソースコードからSSA形式の命令を生成するための「SSAビルダー」を実装することです。

具体的には、以下のファイルが変更されています。

  • src/pkg/exp/ssa/builder.go: 新規追加されたファイルで、SSAビルダーの主要なロジックが記述されています。このファイルだけで2600行以上のコードが追加されており、このコミットの核心部分です。
  • src/pkg/exp/ssa/emit.go: SSA命令の生成に関連するコードが追加されています。
  • src/pkg/exp/ssa/func.go: 関数に関連するSSA構造の定義や操作が更新されています。
  • src/pkg/exp/ssa/importer.go: パッケージのインポート処理に関連する変更が含まれています。
  • src/pkg/exp/ssa/lvalue.go: L-value (代入可能な左辺値) の処理に関連するコードが追加されています。
  • src/pkg/exp/ssa/print.go: SSA形式のコードを整形して出力する機能が更新されています。
  • src/pkg/exp/ssa/promote.go: 構造体のフィールド昇格 (promotion) をSSA形式で扱うためのコードが追加されています。
  • src/pkg/exp/ssa/ssa.go: SSAパッケージの基本的な定義やユーティリティが更新されています。
  • src/pkg/exp/ssa/util.go: ユーティリティ関数が追加されています。

これらの変更は、GoのAST (Abstract Syntax Tree) からSSA形式への変換ロジックを確立し、コンパイラの最適化フェーズやコード生成フェーズで利用可能な中間表現を構築することを目的としています。

変更の背景

このコミットは、Go言語のコンパイラにSSA形式の中間表現を導入する大規模なプロジェクトの一部です。SSA形式は、コンパイラの最適化において非常に強力な表現であり、データフロー解析や様々な最適化（例: 共通部分式除去、定数伝播、デッドコード削除など）を効率的に行うことを可能にします。

従来のGoコンパイラは、ASTを直接操作するか、より低レベルのG-code（Go独自のバイトコードのようなもの）を使用していましたが、SSA形式の導入により、より高度で一般的な最適化手法を適用できるようになります。このコミットは、そのSSA形式を構築するための「ビルダー」という重要なコンポーネントを実装するものです。

変更の背景には、以下のような目的が考えられます。

  • 最適化の強化: SSA形式は、コンパイラがプログラムのデータフローをより正確に把握できるため、より効果的な最適化を適用できるようになります。
  • コンパイラのモジュール化: SSAビルダーを独立したコンポーネントとして実装することで、コンパイラの各フェーズがより明確に分離され、保守性や拡張性が向上します。
  • 将来的なコンパイラ開発の基盤: SSA形式は、多くの最新のコンパイラで採用されている標準的な中間表現であり、今後のコンパイラ開発や研究の基盤となります。

前提知識の解説

SSA (Static Single Assignment) 形式

SSA形式は、コンパイラの中間表現の一種で、プログラム中の各変数が一度だけ代入されるように制約を課します。これにより、変数の定義と使用の関係が明確になり、データフロー解析が容易になります。

例えば、以下のコードを考えます。

x = 1
x = x + 1
y = x * 2

これをSSA形式に変換すると、以下のようになります。

x0 = 1
x1 = x0 + 1
y0 = x1 * 2

ここで、x0、x1、y0はそれぞれ異なる変数として扱われます。同じ変数名が複数回代入される場合、SSA形式では新しいバージョン（例: x0, x1）が導入されます。

SSA形式の主な利点は以下の通りです。

  • データフローの明確化: 各変数の定義が一度だけであるため、変数の値がどこで定義され、どこで使用されているかが一目でわかります。
  • 最適化の容易さ: 共通部分式除去、定数伝播、デッドコード削除などの多くのコンパイラ最適化が、SSA形式上で効率的に実装できます。
  • Phi関数: 制御フローグラフ (CFG) の複数のパスが合流する点（例: if文の終わり、ループの終わり）では、異なるバージョンの変数が合流する可能性があります。これを解決するために「Phi関数 (Φ関数)」が導入されます。Phi関数は、どのパスから来たかによって適切な変数のバージョンを選択する仮想的な命令です。

Go言語のAST (Abstract Syntax Tree)

Go言語のコンパイラは、まずソースコードを解析してASTを構築します。ASTは、プログラムの構造を木構造で表現したものです。例えば、a + bという式は、+演算子をルートとするノード、その子ノードとしてaとbを表すノードを持つASTとして表現されます。

SSAビルダーは、このASTを入力として受け取り、それをSSA形式の命令列に変換する役割を担います。

Goのgo/typesパッケージ

go/typesパッケージは、Go言語の型システムを扱うための標準ライブラリです。コンパイラやツールがGoのコードを解析し、型情報を取得するために使用されます。SSAビルダーは、ASTノードの型情報をgo/typesパッケージから取得し、それに基づいてSSA命令を生成します。

技術的詳細

このコミットで追加されたsrc/pkg/exp/ssa/builder.goファイルは、Builder構造体を定義し、GoのASTからSSA形式の命令を生成する主要なロジックを実装しています。

Builderは、以下の2つのフェーズで動作します。

  1. CREATEフェーズ:

    • すべてのパッケージが構築され、型チェックが行われます。
    • パッケージメンバーの定義が作成され、メソッドセットが計算され、ブリッジメソッドが合成されます。
    • このフェーズは、インポート依存関係グラフのトポロジカル順序で進行します。
    • Builder.types (式の推論された型)、Builder.constants (定数式の値)、Builder.idents (名前付きエンティティの正規型オブジェクト)、Builder.globals (パッケージレベルの関数、変数、組み込み関数) などのマップがこのフェーズで初期化されます。

  2. BUILDフェーズ:

    • 各Goソース関数のASTをトラバースし、関数本体のSSA命令を生成します。
    • 各パッケージ内では、シンボル参照グラフのトポロジカル順序でビルドが進行します。
    • このフェーズでは、Builderのマップは基本的に定数ですが、一部の例外（demoteSelector、globalValueSpec、Program.methodSets）があります。

Builder構造体は、SSAプログラム全体を保持するProgram、ビルドモード、ソースローダー、型チェックのエラーハンドラ、パッケージごとのSSAパッケージマップ、式の型マップ、定数マップ、識別子マップ、グローバル変数マップなど、SSA構築に必要な様々な情報を管理します。

主要なメソッドと機能

  • NewBuilder: 新しいBuilderインスタンスを作成します。ビルドモード、ソースローダー、エラーハンドラを設定し、組み込み関数 (built-in functions) のSSA Value を初期化します。
  • cond(fn *Function, e ast.Expr, t, f *BasicBlock): 論理条件式eを評価し、その値に基づいてtまたはfの基本ブロックにジャンプするSSAコードを生成します。&&、||、!などの論理演算子を効率的に処理します。
  • logicalBinop(fn *Function, e *ast.BinaryExpr) Value: 論理二項演算子 (&&, ||) のショートサーキット評価をSSA形式で実装します。
  • exprN(fn *Function, e ast.Expr) Value: 複数の結果を返す式 (例: 関数呼び出し、マップのインデックスアクセス、型アサーション、チャネルからの受信) をSSA形式に変換し、タプル型のValueを返します。
  • builtin(fn *Function, name string, args []ast.Expr, typ types.Type) Value: make、new、len、capなどの組み込み関数の呼び出しをSSA命令に変換します。これらの関数は特殊なセマンティクスを持つため、個別に処理されます。
  • demoteSelector(sel *ast.SelectorExpr, pkg *Package) (sel2 *ast.SelectorExpr, index int): 構造体のフィールド昇格 (promoted fields) を含むセレクタ式を、昇格されていない形式に変換します。これは、SSAコード生成の前にASTを「脱糖 (desugar)」する役割を果たします。
  • addr(fn *Function, e ast.Expr, escaping bool) lvalue: アドレス可能な式 (L-value) をSSA形式に変換し、その場所 (アドレス) を表すlvalueを返します。エスケープ解析も行い、ヒープ割り当てが必要な場合にフラグを立てます。
  • exprInPlace(fn *Function, loc lvalue, e ast.Expr): 式eの値をlocで指定されたL-valueに初期化するSSAコードを生成します。複合リテラル (composite literals) のインプレース初期化など、最適化されたコード生成を試みます。
  • expr(fn *Function, e ast.Expr) Value: 単一の結果を返す式をSSA形式に変換し、その値を表すValueを返します。リテラル、関数リテラル、型アサーション、関数呼び出し、単項演算子、二項演算子、スライス式、識別子、セレクタ式、インデックス式、複合リテラル、ポインタ参照など、様々な種類の式を処理します。
  • stmtList(fn *Function, list []ast.Stmt): ステートメントのリストを順に処理します。
  • setCallFunc(fn *Function, e *ast.CallExpr, c *CallCommon): 関数呼び出しの対象 (関数、メソッド、レシーバ) を特定し、CallCommon構造体に設定します。
  • setCall(fn *Function, e *ast.CallExpr, c *CallCommon): 関数呼び出しの引数を評価し、CallCommon構造体に設定します。可変長引数 (variadic arguments) や多値戻り値の処理も含まれます。
  • assignOp(fn *Function, loc lvalue, incr Value, op token.Token): 複合代入演算子 (例: +=, -=) をSSA形式で実装します。
  • buildGlobal(g *Global, obj types.Object): グローバル変数の定義に対するSSAコードを生成します。
  • globalValueSpec(init *Function, spec *ast.ValueSpec, g *Global, obj types.Object): パッケージレベルのValueSpec (変数宣言) をSSA形式に変換し、初期化コードを生成します。初期化順序の複雑さを考慮しています。
  • localValueSpec(fn *Function, spec *ast.ValueSpec): 関数ローカルなValueSpecをSSA形式に変換します。
  • assignStmt(fn *Function, lhss, rhss []ast.Expr, isDef bool): 並列代入文 (例: x, y = a, b) や短い変数宣言 (:=) をSSA形式に変換します。
  • compLit(fn *Function, addr Value, e *ast.CompositeLit, typ types.Type): 複合リテラル (構造体、配列、スライス、マップ) の初期化をSSA形式で実装します。ネストされた複合リテラルも再帰的に処理します。
  • switchStmt(fn *Function, s *ast.SwitchStmt, label *lblock): switchステートメントをSSA形式に変換します。これは、一連のif-else文として扱われます。
  • typeSwitchStmt(fn *Function, s *ast.TypeSwitchStmt, label *lblock): 型スイッチ (switch x.(type)) ステートメントをSSA形式に変換します。これもif-elseチェーンとして実装されます。
  • selectStmt(fn *Function, s *ast.SelectStmt, label *lblock): selectステートメントをSSA形式に変換します。単一のケースを持つselectは最適化されます。
  • forStmt(fn *Function, s *ast.ForStmt, label *lblock): forループをSSA形式に変換します。
  • rangeStmt(fn *Function, s *ast.RangeStmt, label *lblock): rangeループをSSA形式に変換します。

このコミットは、Goの言語仕様の様々な側面 (型システム、制御フロー、組み込み関数、複合リテラルなど) をSSA形式に正確にマッピングするための複雑なロジックを含んでいます。

コアとなるコードの変更箇所

このコミットのコアとなる変更は、src/pkg/exp/ssa/builder.goの新規追加です。このファイルは、Builder構造体とそのメソッド群を定義しており、GoのASTからSSA形式の命令を生成する中心的な役割を担っています。

特に、以下のメソッドは、Goの主要な言語構造をSSAに変換する上で不可欠です。

  • func (b *Builder) expr(fn *Function, e ast.Expr) Value
  • func (b *Builder) stmt(fn *Function, s ast.Stmt) (これは提供されたファイル内容には直接含まれていませんが、stmtListや他のステートメント処理メソッドから推測されます)
  • func (b *Builder) cond(fn *Function, e ast.Expr, t, f *BasicBlock)
  • func (b *Builder) setCall(fn *Function, e *ast.CallExpr, c *CallCommon)
  • func (b *Builder) compLit(fn *Function, addr Value, e *ast.CompositeLit, typ types.Type)
  • func (b *Builder) switchStmt(fn *Function, s *ast.SwitchStmt, label *lblock)
  • func (b *Builder) typeSwitchStmt(fn *Function, s *ast.TypeSwitchStmt, label *lblock)
  • func (b *Builder) selectStmt(fn *Function, s *ast.SelectStmt, label *lblock)
  • func (b *Builder) forStmt(fn *Function, s *ast.ForStmt, label *lblock)
  • func (b *Builder) rangeStmt(fn *Function, s *ast.RangeStmt, label *lblock)

これらのメソッドは、GoのASTノードを走査し、対応するSSA命令 (例: Load, Store, Call, If, Phiなど) を生成して、SSA形式の関数 (Function構造体) の基本ブロック (BasicBlock) に追加していきます。

コアとなるコードの解説

builder.goのコードは、GoのASTノードの種類ごとに、それをSSA命令に変換するロジックを詳細に記述しています。

例えば、exprメソッドは、様々な種類の式 (ast.Ident, ast.CallExpr, ast.BinaryExprなど) を受け取り、それらをSSAのValueに変換します。この変換プロセスでは、型情報 (b.exprType) や定数情報 (b.constants) が活用されます。

stmtメソッド (直接は示されていませんが、stmtListから呼び出されると推測されます) は、ast.AssignStmt (代入文)、ast.IfStmt (if文)、ast.ForStmt (forループ) などのステートメントを処理し、制御フローをSSAの基本ブロックと分岐命令 (If, Jump) で表現します。

特に注目すべきは、Goの複雑な言語機能、例えば多値戻り値、可変長引数、型スイッチ、selectステートメント、rangeループなどが、どのようにSSA形式に「脱糖」され、基本的なSSA命令の組み合わせで表現されているかです。

  • 多値戻り値: exprNメソッドで処理され、複数の結果をtypes.Result型のタプルとして表現し、emitExtractで個々の値を取り出します。
  • 可変長引数: setCallメソッドで、可変長引数がスライスとして構築され、関数に渡されます。
  • 型スイッチ: typeSwitchStmtメソッドで、一連の型アサーションと条件分岐 (TypeAssert, If) に変換されます。特定の型にマッチした場合、その型にキャストされたシャドウ変数が導入されます。
  • selectステートメント: selectStmtメソッドで、Select命令とそれに続く条件分岐 (If) の組み合わせで表現されます。Select命令は、どのチャネル操作が準備できたかを示すインデックスを返します。
  • 複合リテラル: compLitメソッドで、構造体、配列、スライス、マップの初期化が、フィールドや要素へのアドレス取得 (FieldAddr, IndexAddr) と値のストア (emitStore) の組み合わせで表現されます。

これらの変換ロジックは、Goの言語セマンティクスをSSA形式で正確に表現するための基盤となります。

関連リンク

参考にした情報源リンク

  • Static Single Assignment form (Wikipedia): https://en.wikipedia.org/wiki/Static_single-assignment_form
  • Go compiler internals (various articles and talks on Go compiler design and SSA):
    • "Go's new SSA backend" by Keith Randall: https://go.dev/blog/go1.7-ssa (このブログ記事は、このコミットの後のGo 1.7でSSAバックエンドが導入された際の解説ですが、SSAの概念とGoコンパイラにおけるその役割を理解するのに役立ちます。)
    • "The Go Programming Language Specification": https://go.dev/ref/spec (Go言語のセマンティクスを理解するために不可欠です。)
    • "Go's Type System" (go/typesパッケージに関する情報): https://go.dev/blog/go-type-system

これらの情報源は、SSA形式の一般的な概念、Go言語のコンパイラにおけるSSAの導入、およびGoの型システムに関する理解を深めるのに役立ちます。