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

このコミットは、Go言語の実験的なSSA (Static Single Assignment) パッケージ exp/ssa におけるコアユーティリティの導入を目的としています。具体的には、SSA形式におけるリテラル値の表現、SSA値と命令の文字列表現（デバッグ用）、SSA表現の整合性チェックを行うサニティチェッカー、およびその他の雑多なユーティリティ関数が追加・修正されています。

変更されたファイルは以下の通りです。

• src/pkg/exp/ssa/literal.go: リテラルSSA値の定義と関連するヘルパー関数。
• src/pkg/exp/ssa/print.go: SSA値と命令のString()メソッドの実装。
• src/pkg/exp/ssa/sanity.go: SSA表現の整合性をチェックするサニティチェッカー。
• src/pkg/exp/ssa/ssa.go: 既存のSSAコア定義ファイルへの軽微な修正。
• src/pkg/exp/ssa/util.go: ASTおよび型に関するユーティリティ関数。

コミット

コミットハッシュ: 66bf59712e6ee1ea84ce88ff35cea78e525ac5a7 Author: Alan Donovan adonovan@google.com Date: Mon Jan 28 18:06:14 2013 -0500

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

https://github.com/golang/go/commit/66bf59712e6ee1ea84ce88ff35cea78e525ac5a7

元コミット内容

exp/ssa: (#2 of 5): core utilities

This CL includes the implementation of Literal, all the
Value.String and Instruction.String methods, the sanity
checker, and other misc utilities.

R=gri, iant, iant
CC=golang-dev
https://golang.org/cl/7199052

変更の背景

このコミットは、Go言語のコンパイラツールチェーンにおけるexp/ssaパッケージの初期開発フェーズの一部です。exp/ssaは、GoプログラムのSSA（Static Single Assignment）形式での高レベル中間表現を定義することを目的としていました。SSA形式は、コンパイラの最適化や静的解析において非常に強力なツールとなります。

このコミットの目的は、SSA表現を構築し、操作し、デバッグするために不可欠な基本的なユーティリティを提供することです。具体的には、以下の機能が不足しており、それらを補完するためにこの変更が行われました。

1. リテラル値の表現: プログラム中の定数（数値、文字列、真偽値など）をSSA形式で表現するためのLiteral型が必要でした。
2. デバッグと可視化: SSA形式は複雑なグラフ構造を持つため、その内容を人間が理解しやすい形で出力するString()メソッドが、デバッグや開発の進行に不可欠でした。
3. 整合性チェック: SSA変換や最適化の過程で、生成されるSSAグラフが正しい構造を保っているかを検証するメカニズム（サニティチェッカー）は、バグの早期発見と品質保証のために重要です。
4. 共通ユーティリティ: AST（Abstract Syntax Tree）や型システムに関連する一般的なヘルパー関数も、SSAパッケージ全体で再利用されるため、util.goとして集約されました。

これらのユーティリティは、exp/ssaパッケージが実用的なツールとして機能するための基盤を固めるものです。

前提知識の解説

SSA (Static Single Assignment) 形式

SSA（Static Single Assignment）形式は、コンパイラの中間表現（IR）の一種で、各変数が一度だけ代入されるという特性を持ちます。これにより、データフロー解析や最適化が大幅に簡素化されます。

• 単一代入の原則: SSA形式では、変数が代入されるたびに新しい「バージョン」の変数が作成されます。例えば、x = a + b; x = x * 2; はSSA形式では x1 = a + b; x2 = x1 * 2; のようになります。
• Φ（ファイ）関数: 複数の制御フローパスが合流する点（例: if文の終わり、ループの終わり）では、異なるバージョンの同じ変数が存在する可能性があります。SSAでは、これらの異なるバージョンを結合するためにΦ関数（Phi function）が導入されます。Φ関数は、どのパスから来たかに応じて適切なバージョンの変数を選択します。
• 利点:
  • データフロー解析の簡素化: 各変数の定義と使用が明確になり、データフロー解析が容易になります。
  • 最適化の効率化: 共通部分式除去、定数伝播、デッドコード削除など、多くのコンパイラ最適化がSSA形式上で効率的に実装できます。
  • レジスタ割り当ての改善: 変数のライフタイムが明確になるため、レジスタ割り当ての品質が向上します。

Go言語の go/types パッケージ

go/typesパッケージは、Goプログラムの型システムを表現するためのAPIを提供します。コンパイラや静的解析ツールがGoの型情報を扱う際に使用されます。

• 型表現: types.Typeインターフェースとその具体的な実装（types.Basic、types.Pointer、types.Struct、types.Signatureなど）を通じて、Goのあらゆる型を表現します。
• 型チェック: Goの言語仕様に基づいた型チェックロジックを提供します。
• 型情報へのアクセス: 変数、関数、構造体フィールドなどの型情報にアクセスするための機能を提供します。

Go言語の go/ast パッケージ

go/astパッケージは、Goプログラムの抽象構文木（AST）を表現するためのAPIを提供します。ソースコードを解析して得られる構文構造をツリー形式で表現します。

• ASTノード: ast.Nodeインターフェースとその具体的な実装（ast.FuncDecl、ast.AssignStmt、ast.Identなど）を通じて、Goのソースコードの各要素を表現します。
• 構文解析: ソースコードをASTに変換するパーサー（go/parserパッケージ）と組み合わせて使用されます。
• コード生成・変換: ASTを操作することで、コードの変換や生成を行うことができます。

これらのパッケージは、Goのコンパイラやツールが言語のセマンティクスを理解し、操作するための基本的な構成要素です。exp/ssaパッケージは、これらの低レベルの構文・型情報の上に、より高レベルなSSA中間表現を構築します。

技術的詳細

このコミットは、exp/ssaパッケージの複数の側面を強化しています。

src/pkg/exp/ssa/literal.go

このファイルでは、SSA形式におけるリテラル値（定数）を表現するLiteral型が定義されています。Goの組み込み型だけでなく、math/bigパッケージの*big.Intや*big.Ratといった任意精度数値、さらにはgo/typesパッケージのtypes.Complex（複素数）やtypes.NilType（nil値）もサポートしています。

• newLiteral(val interface{}, typ types.Type) *Literal: 指定された値と型を持つ新しいリテラルを作成するコンストラクタ。
• intLiteral(i int64) *Literal: int64値から untyped integer リテラルを作成するヘルパー。
• nilLiteral(typ types.Type) *Literal: 指定された参照型を持つnilリテラルを作成するヘルパー。
• Name() string: リテラルの値を人間が読める形式で返すメソッド。型情報も付加されます。
• Type() types.Type: リテラルの型を返すメソッド。
• IsNil() bool: リテラルがnil値を表すかどうかをチェックするメソッド。
• Int64() int64, Uint64() uint64, Float64() float64, Complex128() complex128: リテラルの値をそれぞれのGoの組み込み数値型に変換するメソッド。math/bigの型も適切に処理されます。これらのメソッドは、SSA形式で表現された定数値を、実際の計算や型チェックのためにGoのネイティブな数値型に変換する際に使用されます。

src/pkg/exp/ssa/print.go

このファイルは、SSA値（Value）と命令（Instruction）のString()メソッドを実装しており、SSAグラフのデバッグ出力に不可欠です。これにより、SSA形式のプログラムを人間が読める形で表示できます。

• Id.String(): パッケージ情報を含むIDの文字列表現。
• relName(v Value, i Instruction) string: 命令iからの相対的なSSA値vの名前を返します。同じパッケージ内の参照は単純な名前、異なるパッケージの関数やグローバル変数への参照は完全修飾名（Package.Name）を使用します。これは、SSAのダンプ出力の可読性を高めるために重要です。
• Value.String()メソッド群: Literal, Parameter, Capture, Global, Builtin, Functionといった様々なSSA値のString()メソッドが実装されています。これらは、値の種類と名前、型情報を含む詳細なデバッグ情報を出力します。
• Instruction.String()メソッド群: Alloc, Phi, Call, BinOp, UnOp, Conv, MakeClosure, MakeSlice, FieldAddr, IndexAddr, Lookup, TypeAssert, Extract, If, Jump, Ret, Send, Defer, Select, Store, MapUpdate, Nextなど、ほぼ全てのSSA命令に対するString()メソッドが実装されています。これにより、各命令のオペランド、操作、結果が明確に表示され、SSAグラフの構造を視覚的に理解するのに役立ちます。
• FullName()メソッド: FunctionとGlobalに対して、パッケージ名を含む完全修飾名を生成します。これは、特に異なるパッケージ間の参照を明確にするために使用されます。

src/pkg/exp/ssa/sanity.go

このファイルは、SSA表現の整合性をチェックするサニティチェッカーを実装しています。これは、SSA変換パスや最適化パスがSSAグラフを破損させていないことを検証するために使用されます。

• SanityCheck(fn *Function, reporter io.Writer) bool: 指定された関数fnのSSA表現の整合性をチェックします。問題が見つかった場合、reporterに診断メッセージを出力し、falseを返します。
• MustSanityCheck(fn *Function, reporter io.Writer): SanityCheckと同様ですが、整合性チェックに失敗した場合にパニックします。テストや開発中に厳密なチェックを行う際に便利です。
• checkFunction(fn *Function) bool: 関数全体のSSA表現をチェックします。
• checkBlock(b *BasicBlock, isEntry bool): 各基本ブロックの整合性をチェックします。
  • 到達可能性のチェック（エントリブロック以外で到達不能なブロックがないか）。
  • 先行ブロックと後続ブロックの関係が双方向で正しいか（CFGの整合性）。
  • 各命令が正しいブロックに属しているか。
  • Φ関数がブロックの先頭にあり、先行ブロックの数とエッジの数が一致しているか。
  • 制御フロー命令（If, Jump, Ret）がブロックの最後の命令であるか。
  • If命令が2つの異なる後続ブロックを持つか。
  • Jump命令が1つの後続ブロックを持つか。
  • Ret命令が後続ブロックを持たないか。
• checkInstr(idx int, instr Instruction): 個々の命令の基本的な整合性をチェックします。

src/pkg/exp/ssa/ssa.go

このファイルは、SSAパッケージのコアデータ構造を定義しています。このコミットでは、主にFunction構造体のフィールドのコメント修正と、Literal, Global, FunctionのString()メソッドのプレースホルダーが削除され、print.goに実際のString()メソッドが移動されたことによる変更が含まれています。これは、責務の分離とコードの整理を反映しています。

src/pkg/exp/ssa/util.go

このファイルには、SSAパッケージ全体で利用される様々なユーティリティ関数が含まれています。これらは主にAST（抽象構文木）とGoの型システムに関連するものです。

• ASTユーティリティ:
  • noparens(e ast.Expr) ast.Expr: 式から括弧を取り除く。
  • isBlankIdent(e ast.Expr) bool: 式がアンダースコア_の識別子であるかをチェックする。
• 型ユーティリティ:
  • underlyingType(typ types.Type) types.Type: 型の基底型（エイリアスや名前付き型を解決した後の実際の型）を返す。これはgo/typesパッケージの内部関数をコピーしたもので、後にエクスポートされる可能性があります。
  • isPointer(typ types.Type) bool: 型がポインタ型であるかをチェックする。
  • pointer(typ types.Type) *types.Pointer: 指定された型へのポインタ型を生成する。
  • indirectType(ptr types.Type) types.Type: ポインタ型の基底型を返す。ポインタ型でない場合はパニック。
  • deref(typ types.Type) types.Type: ポインタ型であればその基底型を、そうでなければ元の型を返す。
  • methodIndex(typ types.Type, methods []*types.Method, id Id) (i int, m *types.Method): 型のメソッドテーブルから指定されたIDのメソッドとそのインデックスを検索する。
  • objKind(obj types.Object) ast.ObjKind: go/types.Objectのカテゴリ（パッケージ、型名、定数、変数、関数）をgo/ast.ObjKindに変換する。
  • DefaultType(typ types.Type) types.Type: untypedな型（例: untyped int）に対応するデフォルトのtypedな型（例: int）を返す。これもgo/typesパッケージの内部関数をコピーしたものです。
  • makeId(name string, pkg *types.Package) Id: 名前とパッケージからId構造体を作成する。エクスポートされた名前の場合はパッケージ情報を含まない。
  • IdFromQualifiedName(qn types.QualifiedName) Id: types.QualifiedNameからIdを作成する。

これらのユーティリティ関数は、SSA形式の構築、型チェック、およびAST操作の様々な段階で再利用される共通のロジックを提供します。

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

src/pkg/exp/ssa/literal.go (Literal型の定義とメソッド)

// newLiteral returns a new literal of the specified value and type.
// val must be valid according to the specification of Literal.Value.
//
func newLiteral(val interface{}, typ types.Type) *Literal {
	// This constructor exists to provide a single place to
	// insert logging/assertions during debugging.
	return &Literal{typ, val}
}

// Int64 returns the numeric value of this literal truncated to fit
// a signed 64-bit integer.
//
func (l *Literal) Int64() int64 {
	switch x := l.Value.(type) {
	case int64:
		return x
	case *big.Int:
		return x.Int64()
	case *big.Rat:
		// TODO(adonovan): fix: is this the right rounding mode?
		var q big.Int
		return q.Quo(x.Num(), x.Denom()).Int64()
	}
	panic(fmt.Sprintf("unexpected literal value: %T", l.Value))
}

src/pkg/exp/ssa/print.go (relName関数とInstruction.String()の例)

// relName returns the name of v relative to i.
// In most cases, this is identical to v.Name(), but for cross-package
// references to Functions (including methods) and Globals, the
// package-qualified FullName is used instead.
//
func relName(v Value, i Instruction) string {
	switch v := v.(type) {
	case *Global:
		if v.Pkg == i.Block().Func.Pkg {
			return v.Name()
		}
		return v.FullName()
	case *Function:
		if v.Pkg == nil || v.Pkg == i.Block().Func.Pkg {
			return v.Name()
		}
		return v.FullName()
	}
	return v.Name()
}

func (v *BinOp) String() string {
	return fmt.Sprintf("%s %s %s", relName(v.X, v), v.Op.String(), relName(v.Y, v))
}

src/pkg/exp/ssa/sanity.go (checkBlock関数の一部)

func (s *sanity) checkBlock(b *BasicBlock, isEntry bool) {
	s.block = b

	// Check predecessor and successor relations are dual.
	for _, a := range b.Preds {
		found := false
		for _, bb := range a.Succs {
			if bb == b {
				found = true
				break
			}
		}
		if !found {
			s.errorf("expected successor edge in predecessor %s; found only: %s", a.Name, blockNames(a.Succs))
		}
	}
	// ... (後略)
}

src/pkg/exp/ssa/util.go (underlyingType関数)

// underlyingType returns the underlying type of typ.
// TODO(gri): this is a copy of go/types.underlying; export that function.
//
func underlyingType(typ types.Type) types.Type {
	if typ, ok := typ.(*types.NamedType); ok {
		return typ.Underlying // underlying types are never NamedTypes
	}
	if typ == nil {
		panic("underlyingType(nil)")
	}
	return typ
}

コアとなるコードの解説

Literal 型と数値変換

literal.goで定義されているLiteral型は、Goプログラム中の定数値をSSA形式で表現するための中心的なデータ構造です。newLiteral関数は、interface{}で任意の値を、types.Typeでその型を受け取り、Literal構造体を初期化します。これにより、Goの型システムとSSA表現が連携します。

Int64(), Uint64(), Float64(), Complex128()といったメソッドは、Literalが保持する値を、Goの組み込み数値型に変換する機能を提供します。特に注目すべきは、math/bigパッケージの*big.Intや*big.Ratといった任意精度数値型を適切に処理している点です。これにより、SSA形式がGoの数値リテラルの完全なセマンティクスを保持し、必要に応じて特定のビット幅や浮動小数点形式に変換できる柔軟性を提供します。これは、コンパイラが型チェックや最適化を行う上で、数値の精度を維持しつつ、ターゲットアーキテクチャの制約に合わせて値を扱うために重要です。

relName 関数と String() メソッド

print.goのrelName関数は、SSAグラフの可読性を高めるための重要なユーティリティです。SSA形式のダンプでは、各値や命令が参照する他のSSA要素の名前が表示されます。relNameは、参照元と参照先のパッケージが同じであれば単純な名前を、異なるパッケージであれば完全修飾名（Package.Name）を使用することで、出力の冗長性を減らしつつ、必要な情報を提供します。これにより、大規模なプログラムのSSAグラフでも、どの要素がどこから来ているのかを容易に追跡できます。

BinOp.String()のような各命令のString()メソッドは、SSA命令を人間が読める形式に変換します。例えば、BinOp（二項演算）の場合、XとYという2つのオペランドとOp（演算子）を持ちます。String()メソッドはrelNameを使用してオペランドの名前を取得し、演算子と組み合わせて「X Op Y」のような形式で出力します。これにより、SSAグラフをテキストとしてダンプした際に、各命令が何を行っているのかを一目で理解できます。これは、SSA変換のデバッグや、最適化パスが期待通りに動作しているかの検証に不可欠な機能です。

サニティチェッカーのCFG整合性チェック

sanity.goのcheckBlock関数は、SSAグラフの基本ブロック（BasicBlock）の整合性を検証します。特に重要なのは、制御フローグラフ（CFG）の整合性チェックです。

	// Check predecessor and successor relations are dual.
	for _, a := range b.Preds {
		found := false
		for _, bb := range a.Succs {
			if bb == b {
				found = true
				break
			}
		}
		if !found {
			s.errorf("expected successor edge in predecessor %s; found only: %s", a.Name, blockNames(a.Succs))
		}
	}

このコードスニペットは、現在のブロックbの各先行ブロックaについて、aがbを後続ブロックとして持っているかを検証しています。つまり、「A -> B」というエッジが存在するならば、AのサクセッサリストにBが含まれ、かつBのプリデセッサリストにAが含まれる、という双方向の整合性を確認しています。このチェックは、SSAグラフの構築や変換中にCFGが破損していないことを保証するために極めて重要です。CFGの整合性が崩れると、データフロー解析や最適化が誤った結果を生成したり、コンパイラがクラッシュしたりする原因となります。

underlyingType ユーティリティ関数

util.goのunderlyingType関数は、Goの型システムにおける「基底型」の概念を扱います。Goでは、type MyInt intのように既存の型に新しい名前を付けることができます（名前付き型）。また、type MySlice []intのように構造体やインターフェースなども定義できます。underlyingTypeは、これらの名前付き型やエイリアスを解決し、その型の真の基底となる型（例: MyIntの基底型はint）を返します。

func underlyingType(typ types.Type) types.Type {
	if typ, ok := typ.(*types.NamedType); ok {
		return typ.Underlying // underlying types are never NamedTypes
	}
	if typ == nil {
		panic("underlyingType(nil)")
	}
	return typ
}

この関数は、go/typesパッケージの内部ロジックをコピーしたもので、SSAパッケージが型情報を扱う際に、名前付き型と基底型を区別して処理するために使用されます。例えば、型チェックや型変換の際に、名前付き型ではなくその基底型に基づいて操作を行う必要がある場合にこの関数が役立ちます。これは、Goの型システムのセマンティクスをSSA表現に正確に反映させるために不可欠なユーティリティです。

関連リンク

• https://github.com/golang/go/commit/66bf59712e6ee1ea84ce88ff35cea78e525ac5a7
• https://golang.org/cl/7199052

参考にした情報源リンク

• https://vertexaisearch.cloud.google.com/grounding-api-redirect/AUZIYQH9X0T09VZR72PNxR7ioS4SwGGHFWzhTYY_1a9_tZQBCRV40SRKLELZKv9Yp2lyVp8x6RJgn9wYnHe3YwcG-GFs7dCyMxR93gQMC7ZsMlSW9xumWUisM9yMpVSY_sMRYsg-4lnkrjIaBI--00g-RwO6QkmPCS1n3s2EhlC3f4pScRajRHH6wHfiYVZk8SryB5Y=
• https://vertexaisearch.cloud.google.com/grounding-api-redirect/AUZIYQEzGvLLY_BwsPBY8lGCI4y7XwcXl8sG2Ss9pMHBC9ryPqC45BpGWd6Vo0z1ocsXfThVLSkujjzgziJTJxGDmaXZoFnCd7---nMmJBfN86Ctas9yYULeuquXdPlRwNETAo127DiqQHyaJTrpid3AQI-8hl4=