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

このコミットは、Go言語の実験的なSSA (Static Single Assignment) バックエンドにおいて、同じステートメントに複数のラベルが付与されているケースのサポートを明確にし、関連する最適化を導入するものです。具体的には、Go言語の仕様では既に複数ラベルが許容されていることを確認し、その挙動を検証するテストを追加しています。また、Function.lblocksマップの初期化を遅延させることで、リソースの効率的な利用を図っています。

コミット

commit c8c16cfbb98b717dc6807228e8a6e3553ab63b64
Author: Alan Donovan <adonovan@google.com>
Date:   Tue Feb 26 14:07:03 2013 -0500

    exp/ssa: support multiple labels on same statement.
    
    Actually it already worked since the spec only requires that
    the one immediately preceding a for/switch/... be usable as
    the target of a break or continue statement.
    
    Added a test.
    Also: allocate Function.lblocks on first use.
    
    R=gri
    CC=golang-dev
    https://golang.org/cl/7365058

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

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

元コミット内容

exp/ssa: support multiple labels on same statement.

Actually it already worked since the spec only requires that
the one immediately preceding a for/switch/... be usable as
the target of a break or continue statement.

Added a test.
Also: allocate Function.lblocks on first use.

R=gri
CC=golang-dev
https://golang.org/cl/7365058

変更の背景

このコミットには主に二つの背景があります。

1. 複数ラベルの挙動の明確化と検証: Go言語のコンパイラ開発において、同じステートメントに複数のラベルが付与された場合の挙動について、SSA (Static Single Assignment) 形式のコード生成器が正しく処理できるかどうかの懸念があったようです。src/pkg/exp/ssa/builder.go には、この点に関するTODOコメントが存在していました。コミットメッセージによると、Go言語の仕様ではbreakやcontinueのターゲットとして使用できるラベルは、対象のステートメントの直前のものに限られるものの、複数のラベルを同じステートメントに付与すること自体は許容されており、SSAビルダーが既にこの仕様に準拠していたことが確認されました。このコミットは、その確認をテストによって裏付け、不要なTODOコメントを削除することで、コードベースの正確性を向上させています。

2. リソース効率の改善: Function構造体内のlblocksマップは、ラベル付きブロックの情報を保持するために使用されます。以前の実装では、Functionが初期化される際に常にこのマップが割り当てられていました。しかし、すべての関数がラベル付きブロックを使用するわけではないため、これは不要なメモリ割り当てとなる可能性がありました。このコミットでは、lblocksマップが実際に必要とされるまで（つまり、labelledBlockメソッドが初めて呼び出されるまで）初期化を遅延させることで、メモリ使用量を削減し、パフォーマンスを向上させることを目的としています。

前提知識の解説

Go言語のラベルと制御フロー文

Go言語では、for、switch、selectといった制御フロー文に対してラベルを付与し、breakやcontinue文でそのラベルを指定することで、ネストされたループやスイッチから特定の外側のループ/スイッチを抜ける、または次のイテレーションに進むことができます。また、goto文は指定されたラベルにプログラムの実行をジャンプさせます。

• break Label: Labelで指定されたfor、switch、select文の実行を終了し、その文の直後のステートメントに制御を移します。
• continue Label: Labelで指定されたforループの次のイテレーションを開始します。
• goto Label: Labelで指定されたステートメントに無条件にジャンプします。gotoのターゲットとなるラベルは、同じ関数内の任意のステートメントに付与できます。

Go言語の仕様では、複数のラベルを同じステートメントに付与することが許可されています。しかし、breakやcontinueのターゲットとして有効なのは、対象の制御フロー文の直前に付与されたラベルのみです。gotoの場合は、どのラベルもターゲットになり得ます。

SSA (Static Single Assignment) 形式

SSA (Static Single Assignment) 形式は、コンパイラの中間表現の一種です。SSA形式では、各変数が一度だけ代入されるようにプログラムが変換されます。これにより、データフロー解析や最適化が大幅に容易になります。Goコンパイラも、バージョン1.7以降でSSA形式をバックエンドとして採用しています（このコミットが作成された2013年時点では、exp/ssaパッケージとして実験的に開発されていました）。

SSA形式への変換プロセスでは、元のソースコードの構造（ループ、条件分岐、ラベルなど）がSSA形式の基本ブロックと命令にマッピングされます。ラベルは、プログラムの特定のポイントを識別し、goto、break、continueといった制御フロー文のターゲットとして機能するため、SSA形式においてもこれらの制御フローを正しく表現する必要があります。

exp/ssaパッケージ

exp/ssaパッケージは、Go言語のコンパイラにおけるSSAバックエンドの実験的な実装でした。このパッケージは、Goの抽象構文木 (AST) をSSA形式に変換し、その後の最適化やコード生成の基盤を提供することを目的としていました。このコミットは、この実験的なSSAバックエンドの正確性と効率性を向上させるためのものです。

技術的詳細

複数ラベルのサポートの明確化

Go言語の仕様では、同じステートメントに複数のラベルを付与することが可能です。例えば、label1: label2: for { ... } のように書くことができます。この場合、break label1もbreak label2も有効ですが、breakやcontinueのターゲットとして機能するのは、その制御フロー文の直前に付与されたラベル（この例ではlabel2）が最も自然なターゲットとなります。しかし、Goの仕様はより柔軟で、breakやcontinueは、そのラベルが指す最も内側のfor、switch、select文を対象とします。このコミットのメッセージは、SSAビルダーがこの挙動を既に正しく処理していることを確認し、そのためのTODOコメントが不要であることを示しています。

Function.lblocksの遅延初期化

src/pkg/exp/ssa/func.go内のFunction構造体には、lblocksというマップが含まれています。このマップは、*ast.Object（ラベルの識別子）をキーとし、*lblock（ラベル付きブロックの内部表現）を値として、関数内のラベル付きブロックの情報を管理します。

以前の実装では、Function.start()メソッド内でf.lblocks = make(map[*ast.Object]*lblock)という行があり、すべての関数に対して無条件にマップが初期化されていました。しかし、多くの関数はラベルを使用しないため、この初期化は不要なオーバーヘッドとなります。

このコミットでは、この初期化行を削除し、代わりにFunction.labelledBlock()メソッド内で、f.lblocksがnilの場合にのみmakeで初期化するように変更しました。これにより、lblocksマップは実際にラベル付きブロックの情報が必要になったときに初めて割り当てられるようになり、メモリ使用量と初期化コストが削減されます。これは、リソースのオンデマンド割り当てという一般的な最適化パターンです。

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

このコミットによる変更は以下の3つのファイルにわたります。

1. src/pkg/exp/ssa/builder.go:

   • func (b *Builder) stmt(fn *Function, _s ast.Stmt)関数内のコメント行 - // TODO(adonovan): fix: handle multiple labels on the same stmt. が削除されました。

2. src/pkg/exp/ssa/func.go:

   • func (f *Function) labelledBlock(label *ast.Ident) *lblock関数内で、f.lblocksがnilの場合にマップを初期化するロジックが追加されました。

     --- a/src/pkg/exp/ssa/func.go
     +++ b/src/pkg/exp/ssa/func.go
     @@ -152,6 +152,9 @@ func (f *Function) labelledBlock(label *ast.Ident) *lblock {
      	lb := f.lblocks[label.Obj]
      	if lb == nil {
      		lb = &lblock{_goto: f.newBasicBlock(label.Name)}
     +		if f.lblocks == nil {
     +			f.lblocks = make(map[*ast.Object]*lblock)
     +		}
      		f.lblocks[label.Obj] = lb
      	}
      	return lb
     @@ -200,7 +203,6 @@ func (f *Function) start(idents map[*ast.Ident]types.Object) {
      	if f.syntax == nil {
      		return // synthetic function; no syntax tree
      	}
     -	f.lblocks = make(map[*ast.Object]*lblock)
      
      	// Receiver (at most one inner iteration).
      	if f.syntax.recvField != nil {
     

3. src/pkg/exp/ssa/interp/testdata/coverage.go:

   • multipleLabels()という新しいテスト関数が追加されました。この関数は、同じforループに複数のラベルを付与し、continue、goto、breakが期待通りに動作することを確認します。
   • init()関数内でmultipleLabels()が呼び出されるように変更されました。

コアとなるコードの解説

src/pkg/exp/ssa/builder.go の変更

削除されたTODOコメントは、// TODO(adonovan): fix: handle multiple labels on the same stmt.というものでした。このコメントの削除は、当初懸念されていた「同じステートメントに複数のラベルがある場合の処理」が、Go言語の仕様上問題なく機能することが確認されたため、修正の必要がないと判断されたことを示しています。これは、SSAビルダーが既にこの複雑なケースを正しく扱っていたか、あるいはGoの仕様がSSAビルダーの実装に影響を与えない形で複数ラベルを許容していたかのいずれかを示唆しています。

src/pkg/exp/ssa/func.go の変更

このファイルでは、Function構造体のlblocksマップの初期化ロジックが変更されました。

• 変更前: Function.start()メソッド内で、関数が開始される際に常にf.lblocks = make(map[*ast.Object]*lblock)が実行されていました。これは、関数がラベルを使用するかどうかにかかわらず、マップが割り当てられることを意味します。
• 変更後: Function.start()からこの行が削除されました。代わりに、Function.labelledBlock()メソッド内で、if f.lblocks == nil { f.lblocks = make(map[*ast.Object]*lblock) }というチェックが追加されました。 labelledBlockメソッドは、特定のラベルに対応するlblock（ラベル付きブロック）を取得または作成する際に呼び出されます。したがって、この変更により、f.lblocksマップは、関数内で実際にラベルが参照されるまで（つまり、labelledBlockが初めて呼び出されるまで）割り当てられないようになりました。これにより、ラベルを使用しない関数ではマップの割り当てが完全にスキップされ、メモリとCPUサイクルの両方で効率が向上します。

src/pkg/exp/ssa/interp/testdata/coverage.go の変更

このファイルには、multipleLabels()という新しいテスト関数が追加されました。このテストは、同じforループにone:とtwo:という2つのラベルを付与し、Go言語における複数ラベルの挙動を検証します。

// Multiple labels on same statement.
func multipleLabels() {
	var trace []int
	i := 0
one:
two:
	for ; i < 3; i++ {
		trace = append(trace, i)
		switch i {
		case 0:
			continue two // 'two'ラベルが付与されたforループの次のイテレーションへ
		case 1:
			i++
			goto one // 'one'ラベルの直後（つまり'two'ラベルの直後）へジャンプ
		case 2:
			break two // 'two'ラベルが付与されたforループを抜ける
		}
	}
	if x := fmt.Sprint(trace); x != "[0 1 2]" {
		panic(x)
	}
}

このテストのポイントは以下の通りです。

• one:とtwo:という2つのラベルが同じforループの直前に付与されています。
• case 0:ではcontinue twoが実行され、forループの次のイテレーションに進みます。これは期待通りの動作です。
• case 1:ではgoto oneが実行されます。goto oneはone:ラベルの直後、つまりtwo:ラベルの直後から実行を再開します。これにより、iがインクリメントされた後、forループの条件が再評価され、次のイテレーションに進みます。
• case 2:ではbreak twoが実行され、two:ラベルが付与されたforループ全体を抜けます。

このテストは、GoのSSAバックエンドが複数ラベルのシナリオにおいて、continue、goto、breakといった制御フロー文を正しく解釈し、期待されるプログラムの実行パスを生成できることを確認しています。最終的にtraceスライスが[0 1 2]となることを検証することで、これらの制御フローが正しく機能していることを証明しています。

関連リンク

• Go言語仕様 - Labels: https://go.dev/ref/spec#Labels
• Go言語仕様 - Break statements: https://go.dev/ref/spec#Break_statements
• Go言語仕様 - Continue statements: https://go.dev/ref/spec#Continue_statements
• Go言語仕様 - Goto statements: https://go.dev/ref/spec#Goto_statements
• Go compiler: SSA: https://go.dev/doc/go1.7#compiler (Go 1.7でのSSAバックエンド導入に関する公式ドキュメント)

参考にした情報源リンク

• Go言語の公式ドキュメントおよび仕様書
• GitHubのgolang/goリポジトリのコミット履歴
• SSA形式に関する一般的なコンパイラ理論の知識