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

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

このコミットは、Go言語の実験的なSSA (Static Single Assignment) パッケージ exp/ssa におけるバグ修正と複数のリファクタリングを含んでいます。主な修正は、匿名フィールドのプロモーション処理におけるバグ（タイポ）の修正です。これにより、SSA形式のコード生成と解析の正確性が向上しています。

コミット

commit 71c37e1c88884edd7c9681ebbed9e3bbc1a08915
Author: Alan Donovan <adonovan@google.com>
Date:   Fri Feb 22 12:35:45 2013 -0500

    exp/ssa: fixed bug (typo) in findPromotedField.
    
    By appending to the wrong (always empty) list, only the last
    anonymous field was being considered for promotion.
    
    Also:
    - eliminated "function-local NamedTypes" TODO; nothing to do.
    - fixed Function.DumpTo: printing of anon receivers was "( T)",
      now "(T)"; extracted writeSignature into own function.
    - eliminated blockNames function;
      thanks to BasicBlock.String, "%s" of []*BasicBlock is fine.
    - extracted buildReferrers into own function.
    
    exp/ssa can now build its own transitive closure.
    
    R=gri
    CC=golang-dev
    https://golang.org/cl/7384054

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

https://github.com/golang/go/commit/71c37e1c88884edd7c9681ebbed9e3bbc1a08915

元コミット内容

exp/ssa: fixed bug (typo) in findPromotedField.

このコミットは、exp/ssa パッケージ内の findPromotedField 関数におけるタイプミスによるバグを修正しました。このバグにより、匿名フィールドのプロモーション処理が正しく行われず、常に最後の匿名フィールドのみが考慮されるという問題が発生していました。

また、以下の改善も含まれています。

  • 「関数ローカルなNamedTypes」に関するTODOコメントが削除されました。これは、対応すべき事項がないと判断されたためです。
  • Function.DumpTo 関数における匿名レシーバーの表示形式が修正されました。以前は ( T) のようにスペースが含まれていましたが、 (T) となり、より整形された出力になりました。また、シグネチャの書き出し処理が writeSignature という独立した関数に抽出されました。
  • blockNames 関数が削除されました。BasicBlock.String メソッドが []*BasicBlock の文字列化に十分対応できるため、冗長な関数が不要になりました。
  • buildReferrers 処理が独立した関数として抽出されました。

これらの変更により、exp/ssa パッケージは自身の推移的閉包を構築できるようになりました。

変更の背景

このコミットの主な背景は、GoコンパイラのSSAバックエンドの正確性と堅牢性を向上させることです。

  1. 匿名フィールドのプロモーションバグ: Go言語の重要な機能の一つに、構造体の匿名フィールドのプロモーションがあります。これにより、埋め込まれた構造体のフィールドやメソッドが、外側の構造体のフィールドやメソッドであるかのように直接アクセスできます。exp/ssa パッケージは、このセマンティクスをSSA形式で正確に表現する必要があります。findPromotedField のバグは、この重要な言語機能のSSA表現に誤りをもたらし、コンパイラの最適化や解析の正確性に影響を与える可能性がありました。
  2. コードの整理と保守性: Function.DumpTo から writeSignature の抽出、blockNames の削除、buildReferrers の関数化は、コードのモジュール化、可読性、および保守性の向上を目的としたリファクタリングです。冗長なコードの削除や関心の分離は、大規模なコードベースにおいてバグの発生を抑制し、将来の機能追加や変更を容易にします。
  3. SSAの自己完結性: 「exp/ssa can now build its own transitive closure」という記述は、SSAパッケージが自身の内部データ構造（特に参照関係）をより効率的かつ正確に管理できるようになったことを示唆しています。これは、SSA形式のコード解析や最適化の基盤となる重要な能力です。

これらの変更は、GoコンパイラのSSAバックエンドがより成熟し、信頼性の高いものになるための継続的な取り組みの一環です。

前提知識の解説

このコミットを理解するためには、以下の概念に関する基本的な知識が必要です。

  1. SSA (Static Single Assignment) 形式:

    • コンパイラ最適化の中間表現（IR）の一種です。
    • 各変数が一度だけ代入されるという特性を持ちます。これにより、データフロー解析が容易になり、多くの最適化（例: 共通部分式除去、定数伝播、デッドコード除去）が効率的に行えます。
    • Goコンパイラは、ソースコードを抽象構文木（AST）に変換した後、SSA形式に変換して様々な最適化を適用し、最終的に機械語を生成します。
    • exp/ssa は、Go言語のプログラムをSSA形式に変換し、操作するための実験的なパッケージでした。

  2. Go言語の構造体と匿名フィールド (Embedded Fields):

    • Goの構造体は、他の構造体を匿名フィールドとして埋め込むことができます。
    • 匿名フィールドを埋め込むと、埋め込まれた構造体のフィールドやメソッドが、外側の構造体のフィールドやメソッドであるかのように直接アクセスできるようになります。これを「プロモーション (Promotion)」と呼びます。
    • 例: 
      type Inner struct {
    X int
}
type Outer struct {
    Inner // 匿名フィールド
    Y int
}
func main() {
    o := Outer{Inner: Inner{X: 10}, Y: 20}
    fmt.Println(o.X) // Inner.X が Outer にプロモーションされている
}
    • コンパイラは、このプロモーションを正しく処理し、SSA形式でもそのセマンティクスを維持する必要があります。

  3. データフロー解析と参照関係 (Referrers):

    • コンパイラは、プログラム内のデータの流れ（データフロー）を解析します。
    • SSA形式では、各変数の定義と使用の関係（def-use/use-def chain）が明確になります。
    • Value.Referrers は、特定のSSA値（変数や計算結果）がプログラムのどこで使われているか（参照されているか）を示すリストです。この情報は、デッドコード除去やレジスタ割り当てなど、多くの最適化で不可欠です。

  4. Goのtypesパッケージ:

    • Goの標準ライブラリの一部で、Goプログラムの型情報を表現・操作するためのパッケージです。
    • コンパイラやツール（go vetなど）が、プログラムの型チェックやセマンティック解析を行う際に利用します。
    • types.Signature は関数のシグネチャ（引数と戻り値の型）を表し、types.Struct は構造体の型情報を表します。

  5. Gerrit (golang.org/cl/):

    • Goプロジェクトがコードレビューと変更管理に使用しているシステムです。
    • https://golang.org/cl/7384054 は、このコミットに対応するGerritのチェンジリスト（Change-ID）を示しています。

技術的詳細

このコミットは、主に exp/ssa パッケージの内部実装に焦点を当てています。

  1. findPromotedField のバグ修正 (src/pkg/exp/ssa/promote.go):

    • この関数は、構造体 st 内で特定のIDを持つプロモートされた匿名フィールドを検索します。
    • 元のコードでは、匿名フィールドのパスを探索する際に、list = append(next, ...) という誤った記述がありました。ここで next は常に空のスライスでした。
    • このため、ループの各イテレーションで list は新しい匿名フィールドパスで上書きされ、結果として最後に発見された匿名フィールドしか list に残らない状態でした。
    • 正しい修正は list = append(list, ...) です。これにより、発見されたすべての匿名フィールドパスが list に追加され、プロモーションの探索が正しく行われるようになりました。これは典型的な「タイポ」によるバグであり、スライスの append 操作のセマンティクスに関する誤解が原因です。

  2. buildReferrers の抽出 (src/pkg/exp/ssa/func.go):

    • 以前は Function.finish() メソッド内に直接記述されていた、SSA値の参照者（Referrers）情報を構築するロジックが、buildReferrers という独立した関数に切り出されました。
    • この関数は、関数のすべての基本ブロック（BasicBlock）と命令（Instr）を走査し、各命令のオペランド（rand）がどのSSA値を参照しているかを特定します。
    • そして、参照されているSSA値の Referrers() スライスに、その命令（instr）を追加します。
    • この分離により、finish() メソッドの責務が明確になり、buildReferrers のロジックが再利用可能になりました。

  3. writeSignature の抽出と Function.DumpTo の改善 (src/pkg/exp/ssa/func.go):

    • Function.DumpTo は、SSA関数の人間が読める形式の「逆アセンブル」を出力する関数です。
    • 関数のシグネチャ（レシーバー、パラメータ、戻り値）を整形して出力するロジックが、writeSignature という新しいヘルパー関数に抽出されました。
    • これにより、DumpTo のコードが簡潔になり、シグネチャの出力ロジックが一箇所に集約されました。
    • また、匿名レシーバーの出力形式が ( T) から (T) に修正され、より標準的なGoの構文に近づきました。これは、fmt.Fprintf の書式指定ではなく、直接文字列操作でスペースを制御することで実現されています。

  4. blockNames 関数の削除 (src/pkg/exp/ssa/sanity.go):

    • sanity.go はSSA形式の健全性チェックを行うファイルです。
    • 以前は、[]*BasicBlock のリストを人間が読める文字列に変換するための blockNames というヘルパー関数が存在しました。
    • しかし、BasicBlock 型自体が String() メソッドを実装しており、fmt.Sprintf や fmt.Fprintf で []*BasicBlock を %s フォーマットで出力すると、Goのデフォルトの文字列化メカニズムが各要素の String() メソッドを呼び出して適切に連結するため、blockNames 関数は冗長であることが判明しました。
    • このため、blockNames 関数は削除され、直接 b.Preds や b.Succs を %s で出力するように変更されました。これにより、コードが簡潔になり、不必要な抽象化が取り除かれました。

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

このコミットで変更された主要なファイルと、その中のコアとなる変更箇所は以下の通りです。

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

    --- a/src/pkg/exp/ssa/promote.go
+++ b/src/pkg/exp/ssa/promote.go
@@ -408,7 +408,7 @@ func findPromotedField(st *types.Struct, id Id) (*anonFieldPath, int) {
 	var list, next []*anonFieldPath
 	for i, f := range st.Fields {
 		if f.IsAnonymous {
-			list = append(next, &anonFieldPath{nil, i, f})
+			list = append(list, &anonFieldPath{nil, i, f})
 		}
 	}
    • findPromotedField 関数内の append の対象が next から list に変更されました。これが匿名フィールドのプロモーションバグの修正です。

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

    --- a/src/pkg/exp/ssa/func.go
+++ b/src/pkg/exp/ssa/func.go
@@ -265,6 +265,25 @@ func numberRegisters(f *Function) {
 	}
 }
 
+// buildReferrers populates the def/use information in all non-nil
+// Value.Referrers slice.
+// Precondition: all such slices are initially empty.
+func buildReferrers(f *Function) {
+	var rands []*Value
+	for _, b := range f.Blocks {
+		for _, instr := range b.Instrs {
+			rands = instr.Operands(rands[:0]) // recycle storage
+			for _, rand := range rands {
+				if r := *rand; r != nil {
+					if ref := r.Referrers(); ref != nil {
+						*ref = append(*ref, instr)
+					}
+				}
+			}
+		}
+	}
+}
+
 // finish() finalizes the function after SSA code generation of its body.
 func (f *Function) finish() {
  f.objects = nil
@@ -289,20 +308,7 @@ func (f *Function) finish() {
 
  optimizeBlocks(f)
 
-	// Build immediate-use (referrers) graph.
-	var rands []*Value
-	for _, b := range f.Blocks {
-		for _, instr := range b.Instrs {
-			rands = instr.Operands(rands[:0]) // recycle storage
-			for _, rand := range rands {
-				if r := *rand; r != nil {
-					if ref := r.Referrers(); ref != nil {
-						*ref = append(*ref, instr)
-					}
-				}
-			}
-		}
-	}
+	buildReferrers(f)
 
  if f.Prog.mode&NaiveForm == 0 {
  	// For debugging pre-state of lifting pass:
@@ -460,39 +466,22 @@ func (f *Function) fullName(from *Package) string {
  	return f.Name_
  }
  
-// DumpTo prints to w a human readable "disassembly" of the SSA code of
-// all basic blocks of function f.
+// writeSignature writes to w the signature sig in declaration syntax.
+// Derived from types.Signature.String().
 //
-func (f *Function) DumpTo(w io.Writer) {
-	fmt.Fprintf(w, "# Name: %s\\n", f.FullName())
-	fmt.Fprintf(w, "# Declared at %s\\n", f.Prog.Files.Position(f.Pos))
-
-	if f.Enclosing != nil {
-		fmt.Fprintf(w, "# Parent: %s\\n", f.Enclosing.Name())
-	}
-
-	if f.FreeVars != nil {
-		io.WriteString(w, "# Free variables:\\n")
-		for i, fv := range f.FreeVars {
-			fmt.Fprintf(w, "# % 3d:\\t%s %s\\n", i, fv.Name(), fv.Type())
-		}
-	}
-
-	if len(f.Locals) > 0 {
-		io.WriteString(w, "# Locals:\\n")
-		for i, l := range f.Locals {
-			fmt.Fprintf(w, "# % 3d:\\t%s %s\\n", i, l.Name(), indirectType(l.Type()))
-		}
-	}
-
-	// Function Signature in declaration syntax; derived from types.Signature.String().
+func writeSignature(w io.Writer, name string, sig *types.Signature, params []*Parameter) {
 	io.WriteString(w, "func ")
-	params := f.Params
-	if f.Signature.Recv != nil {
-		fmt.Fprintf(w, "(%s %s) ", params[0].Name(), params[0].Type())
+	if sig.Recv != nil {
+		io.WriteString(w, "(")
+		if n := params[0].Name(); n != "" {
+			io.WriteString(w, n)
+			io.WriteString(w, " ")
+		}
+		io.WriteString(w, params[0].Type().String())
+		io.WriteString(w, ") ")
 		params = params[1:]
 	}
-	io.WriteString(w, f.Name())
+	io.WriteString(w, name)
 	io.WriteString(w, "(")
  for i, v := range params {
  	if i > 0 {
@@ -500,13 +489,13 @@ func (f *Function) DumpTo(w io.Writer) {
  		}
  		io.WriteString(w, v.Name())
  		io.WriteString(w, " ")
-		if f.Signature.IsVariadic && i == len(params)-1 {
+		if sig.IsVariadic && i == len(params)-1 {
  			io.WriteString(w, "...")
  		}
  		io.WriteString(w, v.Type().String())
  	}
  	io.WriteString(w, ")")
-	if res := f.Signature.Results; res != nil {
+	if res := sig.Results; res != nil {
  		io.WriteString(w, " ")
  		var t types.Type
  		if len(res) == 1 && res[0].Name == "" {
@@ -516,6 +505,34 @@ func (f *Function) DumpTo(w io.Writer) {
  		}
  		io.WriteString(w, t.String())
  	}
+}
+
+// DumpTo prints to w a human readable "disassembly" of the SSA code of
+// all basic blocks of function f.
+//
+func (f *Function) DumpTo(w io.Writer) {
+	fmt.Fprintf(w, "# Name: %s\\n", f.FullName())
+	fmt.Fprintf(w, "# Declared at %s\\n", f.Prog.Files.Position(f.Pos))
+
+	if f.Enclosing != nil {
+		fmt.Fprintf(w, "# Parent: %s\\n", f.Enclosing.Name())
+	}
+
+	if f.FreeVars != nil {
+		io.WriteString(w, "# Free variables:\\n")
+		for i, fv := range f.FreeVars {
+			fmt.Fprintf(w, "# % 3d:\\t%s %s\\n", i, fv.Name(), fv.Type())
+		}
+	}
+
+	if len(f.Locals) > 0 {
+		io.WriteString(w, "# Locals:\\n")
+		for i, l := range f.Locals {
+			fmt.Fprintf(w, "# % 3d:\\t%s %s\\n", i, l.Name(), indirectType(l.Type()))
+		}
+	}
+
+	writeSignature(w, f.Name(), f.Signature, f.Params)
  io.WriteString(w, ":\\n")
  
  if f.Blocks == nil {
@@ -530,7 +547,7 @@ func (f *Function) DumpTo(w io.Writer) {
  		}
  		fmt.Fprintf(w, ".%s:\\t\\t\\t\\t\\t\\t\\t       P:%d S:%d\\n\", b, len(b.Preds), len(b.Succs))\n      	if false { // CFG debugging
-		fmt.Fprintf(w, "\\t# CFG: %s --> %s --> %s\\n\", blockNames(b.Preds), b, blockNames(b.Succs))\n    +		fmt.Fprintf(w, "\\t# CFG: %s --> %s --> %s\\n\", b.Preds, b, b.Succs)\n      	}\n      	for _, instr := range b.Instrs {
  		io.WriteString(w, "\\t")
    • buildReferrers 関数が新しく追加され、Function.finish() からその呼び出しに置き換えられました。
    • writeSignature 関数が新しく追加され、Function.DumpTo からシグネチャ出力ロジックが移動しました。
    • Function.DumpTo 内で、writeSignature が呼び出されるようになりました。
    • Function.DumpTo 内のCFGデバッグ出力で、blockNames の代わりに直接 b.Preds と b.Succs が使われるようになりました。

  3. src/pkg/exp/ssa/sanity.go:

    --- a/src/pkg/exp/ssa/sanity.go
+++ b/src/pkg/exp/ssa/sanity.go
@@ -4,7 +4,6 @@ package ssa
 // Currently it checks CFG invariants but little at the instruction level.
 
 import (
-	"bytes"
  	"fmt"
  	"io"
  	"os"
@@ -41,20 +40,6 @@ func MustSanityCheck(fn *Function, reporter io.Writer) {
  	}
  }
  
-// blockNames returns the names of the specified blocks as a
-// human-readable string.
-//
-func blockNames(blocks []*BasicBlock) string {
-	var buf bytes.Buffer
-	for i, b := range blocks {
-		if i > 0 {
-			io.WriteString(&buf, ", ")
-		}
-		io.WriteString(&buf, b.String())
-	}
-	return buf.String()
-}
-
  func (s *sanity) diagnostic(prefix, format string, args ...interface{}) {
  	fmt.Fprintf(s.reporter, "%s: function %s", prefix, s.fn.FullName())
  	if s.block != nil {
@@ -236,7 +221,7 @@ func (s *sanity) checkBlock(b *BasicBlock, index int) {
  			}
  		}
  		if !found {
-			s.errorf("expected successor edge in predecessor %s; found only: %s", a, blockNames(a.Succs))\n    +			s.errorf("expected successor edge in predecessor %s; found only: %s", a, a.Succs)\n      		}
  		if a.Func != s.fn {
  			s.errorf("predecessor %s belongs to different function %s", a, a.Func.FullName())
  		}
@@ -251,7 +236,7 @@ func (s *sanity) checkBlock(b *BasicBlock, index int) {
  			}
  		}
  		if !found {
-			s.errorf("expected predecessor edge in successor %s; found only: %s", c, blockNames(c.Preds))\n    +			s.errorf("expected predecessor edge in successor %s; found only: %s", c, c.Preds)\n      		}
  		if c.Func != s.fn {
  			s.errorf("successor %s belongs to different function %s", c, c.Func.FullName())
  		}
    • blockNames 関数が完全に削除されました。
    • checkBlock 関数内のエラーメッセージで、blockNames の代わりに直接 a.Succs や c.Preds が使われるようになりました。

コアとなるコードの解説

src/pkg/exp/ssa/promote.go の修正

// promote.go
var list, next []*anonFieldPath
for i, f := range st.Fields {
    if f.IsAnonymous {
        // 修正前: list = append(next, &anonFieldPath{nil, i, f})
        // 修正後: list = append(list, &anonFieldPath{nil, i, f})
    }
}

このコードスニペットは、構造体 st の匿名フィールドを探索し、それらのパスを list に追加する部分です。 元のコードでは list = append(next, ...) となっていました。ここで next はループの各イテレーションで初期化されるか、あるいは常に空のスライスとして扱われていたため、append 操作は常に新しい要素を空のスライスに追加し、その結果を list に代入していました。これにより、list には常に最後に処理された匿名フィールドしか含まれず、それ以前に見つかった匿名フィールドの情報が失われていました。 修正後の list = append(list, ...) は、既存の list スライスに新しい匿名フィールドパスを追加します。これにより、すべての匿名フィールドパスが正しく収集され、プロモーションのロジックが意図通りに機能するようになりました。これは、Goのスライス操作における一般的な落とし穴の一つであり、スライスの再割り当てと元のスライスの参照を正しく理解することが重要です。

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

buildReferrers 関数の抽出

// func.go
func buildReferrers(f *Function) {
    var rands []*Value
    for _, b := range f.Blocks {
        for _, instr := range b.Instrs {
            rands = instr.Operands(rands[:0]) // recycle storage
            for _, rand := range rands {
                if r := *rand; r != nil {
                    if ref := r.Referrers(); ref != nil {
                        *ref = append(*ref, instr)
                    }
                }
            }
        }
    }
}

func (f *Function) finish() {
    // ...
    buildReferrers(f) // 以前はここに直接ロジックがあった
    // ...
}

buildReferrers 関数は、SSA形式の関数 f 内のすべてのSSA値（Value）に対する参照者（Referrers）情報を構築します。これは、各SSA値がプログラムのどの命令によって使用されているかを追跡するための重要なデータ構造です。 このロジックが finish メソッドから独立した関数に切り出されたことで、finish メソッドの責務が軽減され、コードのモジュール性が向上しました。また、buildReferrers は他の場所からも呼び出せるようになり、再利用性が高まります。rands = instr.Operands(rands[:0]) のようにスライスを再利用するイディオムは、アロケーションを減らしパフォーマンスを向上させるためのGoの一般的なパターンです。

writeSignature 関数の抽出と Function.DumpTo の変更

// func.go
func writeSignature(w io.Writer, name string, sig *types.Signature, params []*Parameter) {
    io.WriteString(w, "func ")
    if sig.Recv != nil {
        io.WriteString(w, "(")
        if n := params[0].Name(); n != "" {
            io.WriteString(w, n)
            io.WriteString(w, " ")
        }
        io.WriteString(w, params[0].Type().String())
        io.WriteString(w, ") ")
        params = params[1:]
    }
    io.WriteString(w, name)
    io.WriteString(w, "(")
    // ... パラメータの出力ロジック ...
    io.WriteString(w, ")")
    if res := sig.Results; res != nil {
        io.WriteString(w, " ")
        // ... 戻り値の出力ロジック ...
    }
}

func (f *Function) DumpTo(w io.Writer) {
    // ...
    writeSignature(w, f.Name(), f.Signature, f.Params) // 以前はここに直接ロジックがあった
    io.WriteString(w, ":\\n")
    // ...
}

writeSignature 関数は、Goの関数のシグネチャ（レシーバー、関数名、パラメータ、戻り値）を、宣言構文（例: func (r ReceiverType) MyFunc(arg1 Type1) (ret1 Type2)）で出力するためのヘルパー関数です。 この関数が Function.DumpTo から分離されたことで、DumpTo の主要な目的であるSSAコードのダンプに集中できるようになりました。また、匿名レシーバーの出力形式が ( T) から (T) に修正されたのは、params[0].Name() が空文字列の場合に余分なスペースが出力されないように、条件分岐でスペースの追加を制御しているためです。これは、出力の整形と一貫性を保つための細かな改善です。

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

// sanity.go
// 削除された blockNames 関数
// func blockNames(blocks []*BasicBlock) string { ... }

func (s *sanity) checkBlock(b *BasicBlock, index int) {
    // ...
    if !found {
        // 修正前: s.errorf("...", blockNames(a.Succs))
        // 修正後: s.errorf("...", a.Succs)
    }
    // ...
}

blockNames 関数は、[]*BasicBlock のスライスを文字列に変換するために使用されていました。しかし、Goの fmt パッケージは、スライス内の要素が String() メソッドを実装している場合、そのメソッドを呼び出して要素を文字列化し、それらを適切に連結して出力する機能を持っています。BasicBlock 型は String() メソッドを実装しているため、blockNames 関数は冗長でした。 このコミットでは、blockNames 関数が削除され、エラーメッセージのフォーマット文字列内で直接 a.Succs や c.Preds といった []*BasicBlock 型の変数を %s で出力するように変更されました。これにより、コードが簡潔になり、Goの標準的な文字列化メカニズムをより活用するようになりました。

関連リンク

  • Go言語のSSAパッケージに関する公式ドキュメントや関連資料は、Goのソースコードリポジトリや公式ブログで探すことができます。
  • Go言語の構造体と匿名フィールド（埋め込み）に関する公式ドキュメント: https://go.dev/tour/methods/10
  • Go言語のコンパイラに関する一般的な情報: https://go.dev/doc/compiler

参考にした情報源リンク