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

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

このコミットは、Go言語の実験的なSSA (Static Single Assignment) 形式の中間表現 (exp/ssaパッケージ) のAPIとドキュメントを導入するものです。具体的には、src/pkg/exp/ssa/doc.goとsrc/pkg/exp/ssa/ssa.goの2つの新規ファイルが追加されており、Goプログラムの静的解析ツール構築を目的としたSSA形式の定義と、その利用方法に関する詳細な説明が含まれています。

コミット

commit 09899d3b355a2e34d01751cdbeeeb36418be37d1
Author: Alan Donovan <adonovan@google.com>
Date:   Thu Jan 24 17:21:48 2013 -0500

    exp/ssa: API and documentation.
    
    R=gri, iant, crawshaw, bradfitz, gri, iant
    CC=golang-dev
    https://golang.org/cl/7071058

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

https://github.com/golang/go/commit/09899d3b355a2e34d01751cdbeeeb36418be37d1

元コミット内容

exp/ssa: API and documentation.

R=gri, iant, crawshaw, bradfitz, gri, iant
CC=golang-dev
https://golang.org/cl/7071058

変更の背景

このコミットは、Go言語のコンパイラや静的解析ツールにおいて、プログラムのより効率的かつ正確な分析を可能にするための基盤として、SSA (Static Single Assignment) 形式の中間表現を導入することを目的としています。

従来のGoコンパイラは、AST (Abstract Syntax Tree) を直接操作するか、より低レベルな中間表現を使用していました。しかし、SSA形式は、各変数が一度だけ代入されるという特性を持つため、データフロー解析や最適化を大幅に簡素化し、精度を向上させることができます。特に、Go言語のようなポインタやインターフェースを持つ言語では、エイリアシング（複数のポインタが同じメモリ位置を指すこと）の問題が複雑になりがちですが、SSA形式はこのような問題を扱う上で強力なツールとなります。

exp/ssaパッケージは、GoプログラムのASTをSSA形式に変換し、そのSSA形式を操作するためのAPIを提供します。これにより、Go言語のツール開発者は、より高度な静的解析やコード生成ツールを容易に構築できるようになります。コミットメッセージやdoc.goの内容から、このインターフェースが「実験的であり、変更される可能性が高い」と明記されていることから、将来的なGoコンパイラの進化やツールエコシステムの発展を見据えた、初期段階の重要な取り組みであったことが伺えます。

前提知識の解説

1. 静的単一代入 (Static Single Assignment, SSA) 形式

SSA形式は、コンパイラ最適化やプログラム解析において広く用いられる中間表現の一種です。その核心的な原則は、「各変数がプログラム内で一度だけ代入される」というものです。

  • なぜSSAが必要か？: 従来のプログラムでは、同じ変数名がプログラムの異なる箇所で複数回代入されることがあります。これにより、ある変数の値がどこで定義され、どこで使われているかを追跡するのが困難になり、データフロー解析や最適化が複雑になります。SSA形式は、この問題を解決するために、各代入ごとに新しい「バージョン」の変数を導入します。例えば、x = 1; x = 2; y = x;というコードは、SSA形式ではx1 = 1; x2 = 2; y1 = x2;のようになります。
  • φ (Phi) 関数: SSA形式の重要な要素として「φ関数」（ファイ関数）があります。これは、複数の制御フローパスが合流する地点（例えば、if-else文の終わりやループの合流点）で、異なるパスから来た同じ変数の異なるバージョンを結合するために使用されます。例えば、if cond { x = 1 } else { x = 2 } y = xというコードでは、y = φ(x_if, x_else)のように表現され、yがifブロックからのxの値とelseブロックからのxの値を結合して受け取ることを示します。
  • 利点:
    • データフロー解析の簡素化: 各変数の定義と使用が明確になるため、到達定義解析やライブ変数解析などのデータフロー解析が容易になります。
    • 最適化の促進: 定数伝播、共通部分式除去、デッドコード除去など、多くのコンパイラ最適化がSSA形式上で効率的に実行できます。
    • 正確性の向上: 変数のライフタイムが明確になるため、解析の正確性が向上します。

2. Go言語の型システム (go/typesパッケージ)

go/typesパッケージは、Go言語のソースコードの型チェックを行うための標準ライブラリです。AST (Abstract Syntax Tree) を入力として受け取り、各識別子や式の型情報を解決し、型エラーを検出します。

  • types.Package: Goのパッケージを表すオブジェクトで、パッケージ内の名前解決されたオブジェクト（変数、関数、型など）の情報を含みます。
  • types.Type: Goの型を表すインターフェースで、プリミティブ型、構造体、インターフェース、関数、ポインタなど、あらゆるGoの型を表現します。
  • types.Signature: 関数のシグネチャ（引数と戻り値の型）を表します。
  • types.Object: 名前解決されたGoのエンティティ（変数、関数、型、定数など）を表します。

exp/ssaパッケージは、go/typesパッケージによって提供される型情報に基づいてSSA形式を構築します。これにより、SSA形式の各値が正確な型情報を持つことが保証され、型安全な解析や変換が可能になります。

3. Go言語のAST (go/astパッケージ)

go/astパッケージは、Go言語のソースコードを抽象構文木 (AST) として表現するためのデータ構造を定義しています。Goコンパイラやツールは、まずソースコードをASTにパースし、そのASTを操作することで、型チェック、コード生成、静的解析などを行います。

  • ast.File: 単一のGoソースファイルを表すASTのルートノードです。
  • ast.Expr: 式を表すインターフェースです。
  • ast.Stmt: 文を表すインターフェースです。

exp/ssaパッケージは、go/astパッケージによって生成されたASTを読み込み、それをSSA形式に変換する役割を担います。

4. go/tokenパッケージ

go/tokenパッケージは、Goソースコード内のトークン（キーワード、識別子、演算子など）と、それらのソースコード上の位置情報（ファイル名、行番号、列番号）を扱うためのデータ構造と関数を提供します。

  • token.Pos: ソースコード上の位置を表す型です。
  • token.FileSet: 複数のソースファイルの集合を管理し、token.Posからファイル名や行番号などの具体的な位置情報を取得するために使用されます。

exp/ssaパッケージのSSA形式の要素（関数、命令など）は、元のソースコード上の位置情報をtoken.Posとして保持しており、これにより、SSA形式の解析結果を元のソースコードにマッピングすることが可能になります。これは、デバッグ情報やエラー報告において非常に重要です。

技術的詳細

exp/ssaパッケージは、GoプログラムをSSA形式で表現するための包括的なAPIを提供します。その設計思想は、ソース言語に近い抽象度を保ちつつ、静的解析ツールの構築を容易にすることにあります。

主要なデータ構造

  • Program: Goプログラム全体を表す最上位の構造体です。複数のパッケージ、ファイルセット、組み込み関数などの情報を含みます。
  • Package: 単一のGoパッケージを表します。パッケージレベルの関数、変数、定数、型などのメンバー (Member) を持ちます。
  • Memberインターフェース: パッケージメンバー（*Literal, *Global, *Function, *Type）の共通インターフェースです。
  • Id構造体: 構造体のフィールド名やメソッド名を識別するための型です。エクスポートされていない名前の曖昧さを解消するために、パッケージ情報を含みます。
  • MethodSet: 型に属するメソッドの集合です。
  • Type構造体: パッケージスコープで宣言された名前付き型を表します。
  • Valueインターフェース: SSA形式における値（仮想レジスタ）を表します。命令のオペランドとして使用されます。
  • Instructionインターフェース: SSA形式における命令を表します。値を定義する命令（例: BinOp）はValueインターフェースも実装します。
  • Function: 関数のパラメータ、結果、およびコード（SSAブロック）を表します。ネストされた関数はCaptureパラメータを持ち、クロージャによって提供される自由変数を扱います。
  • BasicBlock: SSA形式の基本ブロックを表します。命令のリストと、先行ブロック (Preds) および後続ブロック (Succs) への参照を持ちます。

SSA値と命令の種類

ssa.goには、Goプログラムの様々な構文要素をSSA形式で表現するための豊富な値と命令が定義されています。

値を定義する命令 (Value-defining instructions)

これらの命令は、新しいSSA仮想レジスタ（値）を生成します。

  • Alloc: メモリを確保し、そのアドレスを返します。スタック (Heap=false) またはヒープ (Heap=true) に割り当てられます。
    • 例: t0 = local int, t1 = new int
  • Phi: φ関数を表し、複数の制御フローパスから来る値を結合します。
    • 例: t2 = phi [0.start: t0, 1.if.then: t1, ...]
  • Call: 関数またはメソッドの呼び出しを表し、その結果を返します。
    • 例: t2 = println(t0, t1), t7 = invoke t5.Println(...t6)
  • BinOp: 二項演算（加算、減算、論理演算など）の結果を返します。
    • 例: t1 = t0 + 1:int
  • UnOp: 単項演算（ポインタの逆参照、チャネル受信など）の結果を返します。
    • 例: t0 = *x, t2 = <-t1,ok
  • Conv: 型変換を表します。
    • 例: t1 = convert interface{} <- int (t0)
  • ChangeInterface: あるインターフェース型から別のインターフェース型への変換を表します。
    • 例: t1 = change interface interface{} <- I (t0)
  • MakeInterface: 値からインターフェースのインスタンスを構築します。
    • 例: t1 = make interface interface{} <- int (42:int)
  • MakeClosure: 匿名関数（クロージャ）の値を生成します。自由変数のバインディングを含みます。
    • 例: t0 = make closure anon@1.2 [x y z]
  • MakeMap: 新しいマップオブジェクトを生成します。
  • MakeChan: 新しいチャネルオブジェクトを生成します。
  • MakeSlice: 新しいスライスオブジェクトを生成します。
  • Slice: 既存の文字列、スライス、または配列からスライスを生成します。
  • FieldAddr: 構造体のフィールドのアドレスを返します。
  • Field: 構造体のフィールドの値を返します。
  • IndexAddr: 配列またはスライスの要素のアドレスを返します。
  • Index: 配列の要素の値を返します。
  • Lookup: マップまたは文字列の要素の値を検索します。
  • Select: select文を表し、チャネル操作の結果を返します。
  • Range: rangeループのイテレータを生成します。
  • Next: イテレータから次の要素を読み取ります。
  • TypeAssert: インターフェース値の型アサーションを行います。
  • Extract: 複数の戻り値を持つ命令（Call, TypeAssertなど）の結果タプルから特定のコンポーネントを抽出します。

副作用を持つ命令 (Instructions executed for effect)

これらの命令は値を生成せず、プログラムの状態を変更したり、制御フローを操作したりします。

  • Jump: 無条件ジャンプ。
  • If: 条件付きジャンプ。
  • Ret: 関数からの戻り。
  • Go: 新しいゴルーチンを起動し、関数を呼び出します。
  • Defer: 遅延実行される関数呼び出しを登録します。
  • Send: チャネルに値を送信します。
  • Store: アドレスに値を格納します。
  • MapUpdate: マップのエントリを更新します。

設計原則

  • ソース言語への近さ: SSA形式の抽象度は、ソース言語（Go）に意図的に近く保たれており、静的解析ツールの構築を容易にします。
  • 非構造化制御フロー: ループ、分岐、スイッチなどの構造化された制御フローは、非構造化された制御フロー（ジャンプ、条件分岐）に置き換えられます。
  • 型解決: go/typesパッケージを使用して型チェックが行われ、SSA形式の各要素は完全に解決された型情報を持つことが保証されます。
  • 名前の非重要性: SSA形式のオブジェクト（Value, Package, Functionなど）の名前は、セマンティックな意味を持たず、デバッグの補助としてのみ存在します。プログラムの正しい解釈は、オブジェクトの同一性とSSAグラフのトポロジーによってのみ決定されます。これにより、名前ベースの操作を避け、後続のパスの実装を簡素化し、効率を向上させます。
  • 実験的インターフェース: doc.goに明記されている通り、このインターフェースは実験的であり、将来的に変更される可能性があります。

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

このコミットでは、以下の2つのファイルが新規追加されています。

  1. src/pkg/exp/ssa/doc.go: exp/ssaパッケージの目的、設計原則、主要なデータ構造、およびSSA形式の例を含むドキュメンテーション。
  2. src/pkg/exp/ssa/ssa.go: exp/ssaパッケージの主要なAPIとデータ構造の定義。Program, Package, Function, BasicBlockなどのコア構造体、およびValueとInstructionインターフェースを実装する多数の具体的なSSA値と命令（Alloc, Phi, Call, BinOpなど）が含まれます。

コアとなるコードの解説

src/pkg/exp/ssa/doc.go

このファイルは、exp/ssaパッケージの包括的な概要を提供します。

  • パッケージの目的: Goプログラムの要素（パッケージ、型、関数、変数、定数）をSSA形式の中間表現で定義することを目的としています。
  • 実験的性質: インターフェースが実験的であり、変更される可能性があることが明記されています。
  • 抽象度の高さ: ソース言語に近い抽象度を保ち、静的解析ツールの構築を容易にすることを目指しています。機械語生成を主目的とはしていません。
  • 制御フロー: ループ、分岐、スイッチは非構造化制御フローに置き換えられます。
  • Builder: go/typesとgo/astを使用して、Goソースファイルを型チェックし、ASTからSSA表現に変換する役割を担います。
  • SourceLocator: インポートされたパッケージのソースファイルをビルダがどのように見つけ、ロードし、パースするかをクライアントが制御できるようにします。
  • 初期のSSA形式: ビルダは、すべてのローカル変数がスタック位置のアドレスであり、明示的なロードとストアを持つナイーブなSSA形式を構築します。レジスタ割り当てやφノード挿入は、後のパスで実行される可能性があります（このコミット時点では未実装）。
  • 名前の非重要性: プログラム表現は内部的に完全に解決されており、Value, Package, Function, Type, BasicBlockの名前には依存しません。オブジェクトの同一性とSSAおよび型グラフのトポロジーのみがセマンティックに重要です。
  • 例: main.hello関数のSSA形式の出力例が示されており、各基本ブロックと命令、およびSSA仮想レジスタの型がどのように表示されるかが説明されています。

src/pkg/exp/ssa/ssa.go

このファイルは、exp/ssaパッケージの主要なデータ構造とインターフェースを定義しています。

  • Program構造体:
    • Files: token.FileSetで、プログラムのファイルの位置情報を提供します。
    • Packages: map[string]*Packageで、インポートパスをキーとするロードされたすべてのパッケージを保持します。
    • Builtins: map[types.Object]*Builtinで、型チェッカーオブジェクトをキーとする組み込み関数を保持します。
  • Package構造体:
    • Prog: 所属するProgramへのポインタ。
    • Types: go/typesパッケージの*types.Packageオブジェクト。
    • ImportPath: パッケージのインポートパス（例: "sync/atomic"）。
    • Members: map[string]Memberで、パッケージのすべてのエクスポートされたメンバーとエクスポートされていないメンバーを保持します。
    • Init: パッケージのinit関数。
    • Func, Var, Const, Typeなどのヘルパーメソッドが提供され、名前でパッケージメンバーにアクセスできます。
  • Memberインターフェース: Name(), String(), Type()メソッドを持ち、ImplementsMember()ダミーメソッドで実装関係を示します。
  • Id構造体: フィールド名やメソッド名を識別するための型で、PkgとNameフィールドを持ちます。
  • Function構造体:
    • Name_: 関数の名前。
    • Signature: *types.Signatureで、関数のシグネチャ。
    • Pos: 定義位置。
    • Enclosing: 匿名関数の場合、囲む関数へのポインタ。
    • Pkg: 所属パッケージ。
    • Params: パラメータのリスト。
    • FreeVars: クロージャによって提供される自由変数のリスト。
    • Locals: ローカル変数のリスト。
    • Blocks: 関数の基本ブロックのリスト。nilの場合、外部関数を示します。
  • BasicBlock構造体:
    • Name: ラベル（セマンティックな意味なし）。
    • Func: 所属関数。
    • Instrs: 命令のリスト。
    • Preds, Succs: 先行ブロックと後続ブロックのリスト。
  • Valueインターフェース: Name(), String(), Type()メソッドを持ち、ImplementsValue()ダミーメソッドで実装関係を示します。
  • Instructionインターフェース: String(), Block(), SetBlock()メソッドを持ち、ImplementsInstruction()ダミーメソッドで実装関係を示します。
  • 具体的なSSA値と命令の構造体: Alloc, Phi, Call, BinOp, UnOp, Conv, MakeClosureなど、Go言語の様々な操作に対応する多数の構造体が定義されています。これらの構造体は、Register（値を定義する命令の場合）やanInstruction（すべての命令の場合）といった埋め込みミックスインを使用して、共通のフィールドやメソッドを共有しています。
  • CallCommon構造体: Go, Defer, Call命令に埋め込まれるミックスインで、関数呼び出しとインターフェースメソッド呼び出しの共通部分を扱います。Recv（レシーバ）、Method（インターフェースメソッドのインデックス）、Func（呼び出し対象関数）、Args（引数）、HasEllipsis（可変長引数かどうか）、Pos（呼び出し位置）などのフィールドを持ちます。

このコミットは、Go言語の静的解析とコンパイラ最適化の将来の発展に向けた、重要な基盤を築くものです。

関連リンク

参考にした情報源リンク