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

このコミットは、Goコンパイラ（特にcmd/6gとcmd/8g、それぞれ386アーキテクチャとamd64アーキテクチャ向けのコンパイラ）におけるコード生成の最適化に関するものです。具体的には、OCONVNOPノードという、実質的に何もしない型変換を表す中間表現ノードを、コード生成フェーズでスキップすることで、レジスタ不足の問題を解消しています。

コミット

commit 0285d2b96b4b4d96281a23b9f938aed4de9146c3
Author: Rémy Oudompheng <oudomphe@phare.normalesup.org>
Date:   Thu Mar 20 22:22:37 2014 +0100

    cmd/6g, cmd/8g: skip CONVNOP nodes in bgen.
    
    Revision 3ae4607a43ff introduced CONVNOP layers
    to fix type checking issues arising from comparisons.
    The added complexity made 8g run out of registers
    when compiling an equality function in go.net/ipv6.
    
    A similar issue occurred in test/sizeof.go on
    amd64p32 with 6g.
    
    Fixes #7405.
    
    LGTM=khr
    R=rsc, dave, iant, khr
    CC=golang-codereviews
    https://golang.org/cl/78100044

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

https://github.com/golang/go/commit/0285d2b96b4b4d96281a23b9f938aed4de9146c3

元コミット内容

このコミットは、Goコンパイラのcmd/6g（386アーキテクチャ向け）とcmd/8g（amd64アーキテクチャ向け）において、bgen関数がOCONVNOPノードをスキップするように変更するものです。これにより、以前のコミット（リビジョン3ae4607a43ff）で導入されたOCONVNOPレイヤーが引き起こしていたレジスタ不足の問題を解決します。具体的には、go.net/ipv6パッケージ内の等価性関数をコンパイルする際に8gがレジスタを使い果たしたり、amd64p32環境で6gがtest/sizeof.goをコンパイルする際に同様の問題が発生したりするのを修正します。この変更は、GoのIssue #7405を解決します。

変更の背景

この変更の背景には、Goコンパイラの内部的な型チェックとコード生成の複雑さがあります。

1. 先行する変更 (リビジョン 3ae4607a43ff): 以前のリビジョン3ae4607a43ffでは、比較演算子に関連する型チェックの問題を修正するために、OCONVNOPという特殊なノードが導入されました。このOCONVNOPノードは、コンパイラの抽象構文木（AST）や中間表現（IR）において、実質的に何もしない型変換（no-op conversion）を表します。例えば、int(x)のように、変数をその自身の型に変換する場合や、基底型が同じ名前付き型間の変換などがこれに該当します。これらのノードは、型システムの一貫性を保ち、正確な型チェックを行うために導入されました。

2. パフォーマンスへの影響: しかし、このOCONVNOPノードの導入は、コンパイラのコード生成フェーズにおいて予期せぬ複雑さを生み出しました。特に、bgen（おそらく"branch generation"または"block generation"の略で、条件分岐や基本的なコードブロックを生成する関数）のようなコード生成関数がこれらのOCONVNOPノードを処理する際に、必要以上に多くのレジスタを消費するようになりました。

3. 具体的な問題の発生:

   • go.net/ipv6パッケージ内の等価性関数（==演算子を使用する関数）を8gコンパイラ（amd64向け）でコンパイルする際に、レジスタが不足し、コンパイルエラーや非効率なコード生成が発生しました。これは、多くの埋め込みフィールドを持つ構造体の等価性チェックが、OCONVNOPノードの連鎖を生成し、コンパイラがこれを効率的に扱えなかったためと考えられます。
   • 同様の問題が、amd64p32環境（32ビットポインタを使用するamd64）で6gコンパイラ（386向け）がtest/sizeof.goをコンパイルする際にも発生しました。

4. Issue #7405: これらの問題は、GoのバグトラッカーでIssue #7405として報告されました。このコミットは、このIssueを直接的に解決することを目的としています。

要するに、型チェックの正確性を向上させるために導入されたOCONVNOPノードが、コード生成の段階でレジスタ不足という新たな問題を引き起こしたため、その問題を解決するために、コード生成時にOCONVNOPノードをスキップするという最適化が施された、というのがこの変更の背景です。

前提知識の解説

このコミットを理解するためには、以下のGoコンパイラの内部構造と概念に関する知識が必要です。

1. Goコンパイラのフェーズ: Goコンパイラは、ソースコードを機械語に変換するまでに複数のフェーズを経ます。

   • 字句解析 (Lexing): ソースコードをトークンに分割します。
   • 構文解析 (Parsing): トークンから抽象構文木 (AST) を構築します。
   • 型チェック (Type Checking): ASTに対して型の一貫性を検証します。
   • 中間表現 (IR) 生成: ASTを、より機械語に近い中間表現に変換します。Goコンパイラでは、ASTノードがそのままIRとしても機能することが多いです。
   • 最適化 (Optimization): IRに対して様々な最適化を適用します。
   • コード生成 (Code Generation): 最適化されたIRから最終的な機械語を生成します。

2. 抽象構文木 (AST) と中間表現 (IR):

   • AST: ソースコードの構造を木構造で表現したものです。プログラミング言語の構文要素（変数宣言、関数呼び出し、演算子など）がノードとして表現されます。
   • IR: コンパイラ内部で使われる、ASTよりも低レベルで、機械語に近い表現です。最適化やコード生成の効率を高めるために用いられます。Goコンパイラでは、ASTノードがそのままIRとしても機能する場合があります。

3. Node構造体とopフィールド: Goコンパイラのソースコードでは、ASTやIRの各要素がNode構造体として表現されます。このNode構造体には、そのノードがどのような種類の操作を表すかを示すopフィールド（Node.Op）があります。例えば、OADDは加算、OCALLは関数呼び出しなどを表します。

4. OCONVNOP:

   • OCONVNOPは、Goコンパイラ内部で定義される特殊なNode.Opの一つです。
   • これは "Type(X) (type conversion, no effect)" を意味し、実質的に何もしない型変換を表します。
   • 例えば、var i int = 10; var j int = int(i) のように、int(i)の部分はiの型が既にintであるため、実行時に実際の変換処理は不要です。しかし、コンパイラは型チェックの厳密性を保つために、このような変換が存在することを内部的に記録します。
   • OCONVNOPノードは、主に型チェックフェーズで導入され、型システムの一貫性を保証するために使用されます。

5. bgen関数:

   • bgenは、Goコンパイラのコード生成フェーズで使用される重要な関数です。
   • その名前が示す通り、"branch generation"（分岐命令の生成）や"block generation"（基本的なコードブロックの生成）に関連する処理を行います。
   • この関数は、AST/IRノードを受け取り、それに対応する機械語命令を生成する役割を担います。条件分岐（if文など）やループ、比較演算子などの処理において、適切なジャンプ命令やレジスタ操作を決定します。

6. レジスタ割り当て (Register Allocation):

   • CPUには、高速なデータ処理のために少数のレジスタが搭載されています。コンパイラは、プログラムの実行中に使用する変数の値をこれらのレジスタに割り当てることで、メモリへのアクセスを減らし、パフォーマンスを向上させます。
   • レジスタ不足 (Register Exhaustion): コンパイラが生成するコードが複雑になりすぎると、利用可能なレジスタが不足し、一時的な値をメモリに退避させる（スピルする）必要が生じます。これはパフォーマンスの低下を招くだけでなく、場合によってはコンパイルエラーの原因となることもあります。

これらの概念を理解することで、OCONVNOPノードがなぜ導入され、それがどのようにレジスタ不足を引き起こし、そして今回のコミットがどのようにその問題を解決しているのかが明確になります。

技術的詳細

このコミットの技術的詳細は、Goコンパイラのコード生成ロジックにおけるOCONVNOPノードの扱い方に焦点を当てています。

1. OCONVNOPノードの役割と問題点:

   • 前述の通り、OCONVNOPノードは、型チェックの目的で導入された「実質的に何もしない型変換」を表す中間表現です。例えば、interface{}(nil)のようなインターフェースへの変換や、基底型が同じ構造体間の変換などで生成されることがあります。
   • これらのノードは、型システムの一貫性を保つ上では重要ですが、コード生成の観点からは、対応する機械語命令を生成する必要がありません。つまり、これらのノードは「ノイズ」となり得ます。
   • 以前のリビジョン3ae4607a43ffでOCONVNOPレイヤーが導入された際、bgen関数がこれらのノードを適切に最適化せずに処理してしまい、結果として不要なレジスタ操作や複雑なコードパスを生成してしまいました。特に、多くの埋め込みフィールドを持つ構造体の等価性チェックなど、複雑な型構造が絡む場合に、OCONVNOPノードが連鎖的に発生し、bgenが処理すべきノードの数が大幅に増加しました。

2. bgen関数の処理フロー:

   • bgen関数は、与えられたNode（AST/IRノード）を評価し、その結果に基づいて条件分岐やコードブロックを生成します。
   • この関数は、再帰的にノードを処理し、必要に応じてレジスタを割り当て、機械語命令を生成します。
   • OCONVNOPノードがbgenに渡された場合、そのノード自体は実行時に何もしないにもかかわらず、bgenはそれを通常のノードと同様に処理しようとしました。これにより、レジスタの不必要な使用や、コンパイラの内部状態の複雑化を招きました。

3. 今回の修正のメカニズム:

   • このコミットでは、bgen関数の冒頭にシンプルなwhileループを追加することで、この問題を解決しています。
   • このループは、入力されたNode *nがOCONVNOPである限り、そのノードのleft子ノード（変換元のノード）にnを更新し続けます。
   • 同時に、OCONVNOPノードに付随する初期化リスト（n->ninit）が存在する場合は、genlist(n->ninit)を呼び出して、その初期化処理を実行します。これは、OCONVNOPノード自体はスキップされても、それに付随する副作用（例えば、一時変数の初期化など）は正しく処理されるようにするためです。
   • このループにより、bgen関数が実際に処理を開始する前に、OCONVNOPノードの連鎖が「剥がされ」、実質的な操作を行うノード（OCONVNOPの変換元ノード）が直接bgenのメインロジックに渡されるようになります。

4. 効果:

   • この変更により、bgenは不要なOCONVNOPノードを処理する必要がなくなり、レジスタの消費が抑えられます。
   • 特に、複雑な型構造を持つ等価性関数など、OCONVNOPノードが多数生成されるケースにおいて、コンパイラのレジスタ割り当てが効率化され、レジスタ不足の問題が解消されます。
   • 結果として、コンパイルが成功するようになり、生成されるコードの効率も向上する可能性があります。

この修正は、コンパイラのフロントエンド（型チェック）とバックエンド（コード生成）間のインターフェースにおける、中間表現の効率的な処理の重要性を示しています。

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

変更は主に以下の2つのファイルにあります。

1. src/cmd/6g/cgen.c
2. src/cmd/8g/cgen.c

両ファイルとも、bgen関数の冒頭に以下のコードブロックが追加されています。

	while(n->op == OCONVNOP) {
		n = n->left;
		if(n->ninit != nil)
			genlist(n->ninit);
	}

また、test/fixedbugs/issue7405.goという新しいテストファイルが追加されています。

// compile

// Copyright 2014 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

// Issue 7405: the equality function for struct with many
// embedded fields became more complex after fixing issue 7366,
// leading to out of registers on 386.

package p

type T1 struct {
	T2
	T3
	T4
}

type T2 struct {
	Conn
}

type T3 struct {
	PacketConn
}

type T4 struct {
	PacketConn
	T5
}

type T5 struct {
	x int
	T6
}

type T6 struct {
	y, z int
}

type Conn interface {
	A()
}

type PacketConn interface {
	B()
}

func F(a, b T1) bool {
	return a == b
}

コアとなるコードの解説

追加されたコードブロックは、bgen関数の入力ノードnがOCONVNOPである場合に、そのノードをスキップし、実質的な操作を行う子ノードに処理を移すためのものです。

	while(n->op == OCONVNOP) { // (1)
		n = n->left;          // (2)
		if(n->ninit != nil)   // (3)
			genlist(n->ninit); // (4)
	}

1. while(n->op == OCONVNOP):

   • このループは、現在のノードnの操作タイプ（n->op）がOCONVNOPである限り繰り返されます。
   • OCONVNOPは、前述の通り「実質的に何もしない型変換」を表すコンパイラ内部のノードです。

2. n = n->left;:

   • OCONVNOPノードは、通常、変換元の式をleft子ノードとして持ちます。
   • この行は、現在のOCONVNOPノードをスキップし、そのleft子ノード（つまり、変換元の実際の式）を新しい現在のノードnとして設定します。
   • これにより、bgenはOCONVNOPという「ノイズ」を無視して、その背後にある本来処理すべきノードに直接アクセスできるようになります。

3. if(n->ninit != nil):

   • ninitは、GoコンパイラのNode構造体におけるフィールドで、そのノードに関連付けられた初期化ステートメントのリストを指します。
   • 型変換ノード（OCONVNOPを含む）は、変換処理の一部として一時変数の初期化など、何らかの初期化処理を伴う場合があります。
   • この条件は、現在のOCONVNOPノードに初期化リストが存在するかどうかをチェックします。

4. genlist(n->ninit);:

   • もしninitがnilでなければ、genlist関数が呼び出されます。
   • genlistは、与えられたステートメントのリストを生成する関数です。
   • この行は、OCONVNOPノード自体はスキップされるものの、それに付随する必要な初期化処理は正しく実行されることを保証します。これにより、コードの正確性が保たれます。

このループは、bgen関数が実際のコード生成ロジックに入る前に、OCONVNOPノードの連鎖を効率的に「剥がす」役割を果たします。これにより、bgenはよりクリーンな入力ノードを受け取り、レジスタ不足の問題を回避し、より効率的なコードを生成できるようになります。

追加されたtest/fixedbugs/issue7405.goは、この問題が再現する具体的なコードパターンを示しています。複数の埋め込み構造体を持つT1型に対して等価性比較を行うF関数が定義されており、このような複雑な型構造がOCONVNOPノードの連鎖を生成し、レジスタ不足を引き起こしていたことが示唆されます。このテストケースは、修正が正しく機能することを確認するために使用されます。

関連リンク

• Go Issue #7405: このコミットが修正したバグのトラッキング。
  • 直接的なリンクは古いGoのバグトラッカーのため見つけにくいですが、コミットメッセージに記載されているhttps://golang.org/cl/78100044は、この変更のコードレビューページへのリンクです。
• Goコンパイラのソースコード:
  • src/cmd/6g/cgen.c
  • src/cmd/8g/cgen.c
  • src/cmd/gc/go.h (Goコンパイラの内部ノード定義、OCONVNOPなどが定義されている)

参考にした情報源リンク

• Goの公式ドキュメントやコンパイラの内部構造に関する資料 (一般的なGoコンパイラの知識)
• GoのIssueトラッカー (Issue #7405に関する情報)
• Goのコードレビューシステム (CL 78100044に関する情報)
• Go compiler OCONVNOP - Google Search Results
• Go issue 7405 - Google Search Results
• Go compiler source code on GitHub
• Go compiler internal representation (IR) concepts (現代のGoコンパイラにおけるIRの概念理解のため)
• Go compiler Node structure (現代のGoコンパイラにおけるASTノードの概念理解のため)