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

このコミットは、Goコンパイラ（6g、amd64アーキテクチャ向け）におけるコード生成の改善を目的としています。具体的には、構造体のフィールドアクセスやポインタのデリファレンスを含む複雑なメモリアドレス計算を最適化するための新しい関数 sudoaddable を導入し、より効率的なアセンブリ命令を生成できるようにしています。また、様々なデータ型に対する代入操作（OAS）のための optoas 関数に、より適切なアセンブリ移動命令（AMOVB, AMOVW, AMOVL, AMOVQ, AMOVSS, AMOVSD）を追加し、コード生成の精度と効率を向上させています。

コミット

commit 937ac13f26a95f018e1706a7faaddab7369a8416
Author: Ken Thompson <ken@golang.org>
Date:   Sat Dec 13 13:16:14 2008 -0800

    code improvement
    
    R=r
    OCL=21144
    CL=21144

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

https://github.com/golang/go/commit/937ac13f26a95f018e1706a7faaddab7369a8416

元コミット内容

code improvement

R=r
OCL=21144
CL=21144

変更の背景

Goコンパイラの初期段階において、生成されるアセンブリコードの効率性は重要な課題でした。特に、構造体のフィールドアクセスやポインタを介したデータアクセスは、複数の命令を必要とすることが多く、パフォーマンスのボトルネックとなる可能性がありました。

このコミットの背景には、以下のような目的があったと考えられます。

1. コード生成の効率化: 複雑なメモリアクセスパターン（例: s.field.subfield や ptr->field.subfield）を、単一の効率的なアセンブリ命令（例: MOVQ (base_reg + offset), target_reg）に変換することで、生成されるコードのサイズを削減し、実行速度を向上させる。
2. コンパイラの最適化能力の向上: コンパイラがより多くのケースで直接アドレス指定可能な式を認識し、それに応じて最適なコードを生成できるようにする。
3. 型に応じた適切な命令選択: 代入操作において、対象となるデータの型（バイト、ワード、ロング、クアッド、浮動小数点数など）に応じて、より特化したアセンブリ移動命令を選択することで、生成コードの正確性と効率性を高める。

これらの改善は、Goプログラム全体の実行時パフォーマンスに直接貢献します。

前提知識の解説

このコミットを理解するためには、Goコンパイラの内部構造と、一般的なコンパイラ最適化の概念に関するいくつかの前提知識が必要です。

• Goコンパイラ (6g):
  • 6g は、Go言語の初期のコンパイラの一つで、AMD64 (x86-64) アーキテクチャをターゲットとしていました。Goのコンパイラは、ターゲットアーキテクチャに基づいて命名されることがありました（例: 8g は386、5g はARM）。
  • Goコンパイラは、ソースコードを抽象構文木（AST）にパースし、中間表現（IR）に変換し、最終的にターゲットアーキテクチャのアセンブリコードを生成します。
• 抽象構文木 (AST) と Node:
  • Goのソースコードは、コンパイラによってASTに変換されます。ASTは、プログラムの構造を木構造で表現したものです。
  • コンパイラ内部では、このASTの各要素が Node 構造体として表現されます。例えば、変数、定数、演算子、関数呼び出しなどが Node になります。
  • n->op: Node の種類（例: ODOT、ODOTPTR、OAS など）を示すフィールドです。
  • n->type: Node が表す式の型情報（例: TINT64、TFLOAT32 など）を持つフィールドです。
  • n->xoffset: 構造体のフィールドアクセス (ODOT) において、フィールドのオフセット（構造体の先頭からのバイト単位の距離）を示すフィールドです。
• 中間表現 (IR):
  • ASTは、さらにコンパイラ内部で処理しやすい中間表現に変換されます。この中間表現は、ターゲットマシンに依存しない形式で、様々な最適化が適用されます。
• コード生成 (cgen):
  • cgen 関数は、Goコンパイラの主要なコード生成フェーズの一つです。ASTノードを受け取り、それに対応するアセンブリ命令を生成します。
  • gins(opcode, from_operand, to_operand): "Generate Instruction" の略で、指定されたオペコードとオペランドを持つアセンブリ命令を生成し、出力ストリームに追加する関数です。
• アセンブリ命令と Addr:
  • Addr 構造体は、ターゲットマシンにおけるメモリアドレスやレジスタ、定数などのオペランドを表現するために使用されます。
  • D_NONE: Addr 構造体で、オペランドが指定されていないことを示す値です。
  • AMOVB, AMOVW, AMOVL, AMOVQ: それぞれバイト、ワード（2バイト）、ロング（4バイト）、クアッド（8バイト）のデータを移動するアセンブリ命令（x86/x86-64アーキテクチャ）。
  • AMOVSS, AMOVSD: それぞれ単精度浮動小数点数、倍精度浮動小数点数を移動するアセンブリ命令（SSE/SSE2命令セット）。
• レジスタ割り当て (regalloc, regfree):
  • regalloc(&node, type, hint): 実行時に値を保持するために、利用可能なCPUレジスタを割り当てる関数です。
  • regfree(&node): 割り当てられたレジスタを解放する関数です。
• ullman 数:
  • コンパイラのレジスタ割り当てアルゴリズムで用いられる概念で、式の複雑さを示す指標です。ullman 数が大きいほど、その式を評価するためにより多くのレジスタが必要になる可能性が高いことを示します。abop (asymmetric binary operation) の処理で利用されます。
• ODOT と ODOTPTR:
  • ODOT: 構造体のフィールドアクセス（例: myStruct.field）。
  • ODOTPTR: ポインタのデリファレンスとフィールドアクセスを組み合わせたもの（例: myPtr->field または (*myPtr).field）。
• optoas:
  • "Optimize to Assembly" の略で、Goの操作（OAS など）と型に基づいて、最適なアセンブリ命令のオペコードを返す関数です。
• simtype:
  • "Simplified Type" の略で、Goの複雑な型を、コンパイラ内部で比較や処理が容易な基本的な型にマッピングするために使用される配列または関数です。

技術的詳細

このコミットの核となる技術的詳細は、sudoaddable 関数とその補助関数 dotoffset、そして optoas の拡張にあります。

sudoaddable 関数の役割と動作

sudoaddable 関数は、特定の Node が、アセンブリレベルで直接的かつ効率的なメモリアドレス指定モードに変換可能かどうかを判断し、可能であればそのアドレス情報を Addr 構造体に格納します。

1. 入力チェック:
   • 入力 Node *n と Type *t が有効であること（T は無効な型を示す）。
   • n の型と t の「簡略化された型」（simtype）が一致することを確認します。これは、代入操作の互換性を保証するためです。
2. ノードの種類による分岐:
   • sudoaddable は、ODOT (構造体フィールドアクセス) と ODOTPTR (ポインタデリファレンスとフィールドアクセス) のノードタイプのみを処理対象とします。これら以外のノードは、直接アドレス指定可能ではないと判断し、0 を返します。
3. オフセットの収集 (dotoffset の利用):
   • dotoffset(n, oary, &nn) を呼び出し、n が表す式（例: a.b.c や p->q.r）における一連のオフセットと、その式の「基底」となるノード nn を収集します。
   • oary は、オフセットの配列です。正の値は直接的なフィールドオフセットを、負の値はポインタデリファレンス（-(xoffset+1) の形式）を示します。
   • nn は、オフセットチェーンの開始点となるノード（例: a や p）です。
   • もしオフセットの数が多すぎる（oary のサイズ 10 を超える）場合、nn は N (null) に設定され、sudoaddable は 0 を返します。
4. アドレス計算とコード生成:
   • regalloc(&n1, types[tptr], N);: ポインタ型の一時レジスタ n1 を割り当てます。
   • n2 = n1; n2.op = OINDREG;: n1 を基底レジスタとする間接レジスタアクセスを表す n2 ノードを作成します。
   • 最初のオフセットの処理:
     • oary[0] >= 0 (直接オフセットの場合): agen(nn, &n1); を呼び出し、基底ノード nn のアドレスを n1 に計算します。n2.xoffset に最初のオフセットを設定します。
     • oary[0] < 0 (ポインタデリファレンスの場合): cgen(nn, &n1); を呼び出し、基底ノード nn の値を n1 に計算します（つまり、ポインタの値をレジスタにロードします）。n2.xoffset にデリファレンスオフセットを設定します。
   • 後続のオフセットの処理:
     • for(i=1; i<o; i++): 最初のオフセット以降のオフセットをループで処理します。
     • if(oary[i] >= 0) fatal("cant happen");: ここが重要な制約です。最初のオフセットがポインタデリファレンスであった場合、それ以降のオフセットはすべてポインタデリファレンスでなければならないことを示しています。もし直接オフセットが来た場合、コンパイラは致命的なエラーを発生させます。これは、sudoaddable が処理できるアドレス指定パターンの種類を限定していることを意味します。
     • gins(AMOVQ, &n2, &n1);: n2 が指すメモリ位置（n1 レジスタの値 + n2.xoffset）から8バイト（AMOVQ）を読み込み、その値を n1 に格納します。これにより、ポインタのデリファレンスが実行されます。
     • n2.xoffset = -(oary[i]+1);: 次のデリファレンスのためのオフセットを更新します。
   • 最終アドレスの格納:
     • naddr(&n2, a);: 最終的に計算されたアドレス情報を持つ n2 ノードを、出力 Addr *a 構造体に変換して格納します。
     • regfree(&n1);: 一時レジスタ n1 を解放します。
5. 結果の返却:
   • アドレスが正常に計算され、a に格納された場合、1 を返します。それ以外の場合は 0 を返します。

dotoffset 関数の役割と動作

dotoffset 関数は、ODOT および ODOTPTR ノードの連鎖を解析し、それぞれのフィールドオフセットやポインタデリファレンスオフセットを oary 配列に収集します。

• 再帰的な処理: n->left を再帰的に呼び出すことで、a.b.c のようなネストされたフィールドアクセスを処理します。
• ODOT の処理:
  • n->xoffset を現在のオフセットとして扱います。
  • もし前のオフセットが既に存在し、それが直接オフセット（oary[i-1] >= 0）であれば、現在のオフセットを前のオフセットに加算します。これは、struct { int x; int y; } s; s.y のように、連続する直接オフセットを単一のオフセットにまとめるためです。
  • もし前のオフセットがポインタデリファレンス（oary[i-1] < 0）であれば、現在のオフセットを前のオフセットから減算します。これは、ポインタのデリファレンス後にフィールドアクセスがある場合のオフセット調整です。
  • oary に新しいオフセットとして n->xoffset を追加します。
• ODOTPTR の処理:
  • -(n->xoffset+1) という形式で、ポインタデリファレンスを示す負の値を oary に追加します。この負の値は、sudoaddable 関数内でポインタデリファレンスとして特別に扱われます。
• 基底ノードの特定:
  • default ケースでは、ODOT や ODOTPTR ではないノード（例: 変数そのもの）に到達したことを意味します。このノードがオフセットチェーンの「基底」となるノード nn として設定されます。
• オフセット数の返却: 収集されたオフセットの数を返します。

optoas の拡張

gsubr.c 内の optoas 関数は、OAS (代入) 操作に対して、より多くの型に応じたアセンブリ移動命令を返すように拡張されました。

• TBOOL, TINT8, TUINT8 (1バイト): AMOVB
• TINT16, TUINT16 (2バイト): AMOVW
• TINT32, TUINT32, TPTR32 (4バイト): AMOVL
• TINT64, TUINT64, TPTR64 (8バイト): AMOVQ
• TFLOAT32 (単精度浮動小数点数): AMOVSS
• TFLOAT64 (倍精度浮動小数点数): AMOVSD

これにより、コンパイラは代入操作を行う際に、汎用的な移動命令ではなく、データのサイズと種類に最適なアセンブリ命令を選択できるようになり、生成されるコードの効率が向上します。

cgen における sudoaddable の統合

cgen.c では、sudoaddable 関数が2箇所で呼び出されています。

1. cgen 関数の冒頭:
   • cgen がノードのコード生成を開始する際に、まずそのノードが sudoaddable であるかをチェックします。
   • もし sudoaddable であれば、sudoaddable が計算した最適化されたアドレス情報を使って直接アセンブリ命令を生成し、通常のコード生成パスをスキップして早期リターンします。これにより、複雑な式に対するコード生成が大幅に簡素化され、効率化されます。
2. abop (asymmetric binary operation) の処理内:
   • 二項演算子（例: +, -）のコード生成において、左右のオペランドの ullman 数に基づいて処理順序が決定されます。
   • 左オペランド nl の処理後、右オペランド nr が sudoaddable であるかをチェックします。
   • もし sudoaddable であれば、同様に最適化されたアドレス情報を使ってコードを生成し、効率的な二項演算を実現します。

これらの変更により、Goコンパイラは、構造体やポインタを介したデータアクセスにおいて、より洗練されたアセンブリコードを生成できるようになり、プログラムの実行効率が向上します。

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

src/cmd/6g/cgen.c

--- a/src/cmd/6g/cgen.c
+++ b/src/cmd/6g/cgen.c
@@ -11,6 +11,7 @@ cgen(Node *n, Node *res)
 	Node n1, n2;
 	int a;
 	Prog *p1, *p2, *p3;
+	Addr addr;
 
 	if(debug['g']) {
 		dump("cgen-res", res);
@@ -70,6 +71,21 @@ cgen(Node *n, Node *res)
 		goto ret;
 	}
 
+	if(sudoaddable(n, res->type, &addr)) {
+		a = optoas(OAS, n->type);
+		if(res->op == OREGISTER) {
+			p1 = gins(a, N, res);
+			p1->from = addr;
+		} else {
+			regalloc(&n1, n->type, N);
+			p1 = gins(a, N, &n1);
+			p1->from = addr;
+			gins(a, &n1, res);
+			regfree(&n1);
+		}
+		return;
+	}
+
 	switch(n->op) {
 	default:
 		dump("cgen", n);
@@ -269,6 +285,15 @@ abop:	// asymmetric binary
 	if(nl->ullman >= nr->ullman) {
 		regalloc(&n1, nl->type, res);
 		cgen(nl, &n1);
+
+if(sudoaddable(nr, nl->type, &addr)) {
+	p1 = gins(a, N, &n1);
+	p1->from = addr;
+	gmove(&n1, res);
+	regfree(&n1);
+	goto ret;
+}
+
 		regalloc(&n2, nr->type, N);
 		cgen(nr, &n2);
 	} else {

src/cmd/6g/gg.h

--- a/src/cmd/6g/gg.h
+++ b/src/cmd/6g/gg.h
@@ -199,6 +199,7 @@ void	tempname(Node*, Type*);
 Plist*	newplist(void);
 int	isfat(Type*);
 void	setmaxarg(Type*);
+int	sudoaddable(Node*, Type*, Addr*);
 
 /*
  * list.c

src/cmd/6g/gsubr.c

--- a/src/cmd/6g/gsubr.c
+++ b/src/cmd/6g/gsubr.c
@@ -1175,6 +1175,37 @@ optoas(int op, Type *t)
 		a = AUCOMISD;
 		break;
 
+	case CASE(OAS, TBOOL):
+	case CASE(OAS, TINT8):
+	case CASE(OAS, TUINT8):
+		a = AMOVB;
+		break;
+
+	case CASE(OAS, TINT16):
+	case CASE(OAS, TUINT16):
+		a = AMOVW;
+		break;
+
+	case CASE(OAS, TINT32):
+	case CASE(OAS, TUINT32):
+	case CASE(OAS, TPTR32):
+		a = AMOVL;
+		break;
+
+	case CASE(OAS, TINT64):
+	case CASE(OAS, TUINT64):
+	case CASE(OAS, TPTR64):
+		a = AMOVQ;
+		break;
+
+	case CASE(OAS, TFLOAT32):
+		a = AMOVSS;
+		break;
+
+	case CASE(OAS, TFLOAT64):
+		a = AMOVSD;
+		break;
+
 	case CASE(OADD, TINT8):
 	case CASE(OADD, TUINT8):
 		a = AADDB;
@@ -1728,3 +1759,101 @@ setmaxarg(Type *t)
 	if(w > maxarg)
 		maxarg = w;
 }
+
+/*
+ * gather series of offsets
+ * >=0 is direct addressed field
+ * <0 is pointer to next field (+1)
+ */
+int
+dotoffset(Node *n, int *oary, Node **nn)
+{
+	int i;
+
+	switch(n->op) {
+	case ODOT:
+		i = dotoffset(n->left, oary, nn);
+		if(i > 0) {
+			if(oary[i-1] >= 0)
+				oary[i-1] += n->xoffset;
+			else
+				oary[i-1] -= n->xoffset;
+			break;
+		}
+		if(i < 10)
+			oary[i++] = n->xoffset;
+		break;
+
+	case ODOTPTR:
+		i = dotoffset(n->left, oary, nn);
+		if(i < 10)
+			oary[i++] = -(n->xoffset+1);
+		break;
+
+	default:
+		*nn = n;
+		return 0;
+	}
+	if(i >= 10)
+		*nn = N;
+	return i;
+}
+
+int
+sudoaddable(Node *n, Type *t, Addr *a)
+{
+	int et, o, i;
+	int oary[10];
+	Node n1, n2, *nn;
+
+	if(n->type == T || t == T)
+		return 0;
+	et = simtype[n->type->etype];
+	if(et != simtype[t->etype])
+		return 0;
+
+	switch(n->op) {
+	default:
+		return 0;
+
+	case ODOT:
+	case ODOTPTR:
+		o = dotoffset(n, oary, &nn);
+		if(nn == N)
+			return 0;
+
+		if(0) {
+			dump("XX", n);
+			dump("YY", nn);
+			for(i=0; i<o; i++)
+				print(" %d", oary[i]);
+			print("\n");
+			return 0;
+		}
+
+		regalloc(&n1, types[tptr], N);
+		n2 = n1;
+		n2.op = OINDREG;
+		if(oary[0] >= 0) {
+			agen(nn, &n1);
+			n2.xoffset = oary[0];
+		} else {
+			cgen(nn, &n1);
+			n2.xoffset = -(oary[0]+1);
+		}
+
+		for(i=1; i<o; i++) {
+			if(oary[i] >= 0)
+				fatal("cant happen");
+			gins(AMOVQ, &n2, &n1);
+			n2.xoffset = -(oary[i]+1);
+		}
+
+		a->type = D_NONE;
+		a->index = D_NONE;
+		naddr(&n2, a);
+		regfree(&n1);
+		break;
+	}
+	return 1;
+}

コアとなるコードの解説

src/cmd/6g/cgen.c の変更点

• Addr addr; の追加: cgen 関数内で、最適化されたアドレス情報を保持するための一時変数 addr が宣言されました。
• sudoaddable を利用した早期最適化パス:
  • cgen 関数の冒頭に、if(sudoaddable(n, res->type, &addr)) という条件分岐が追加されました。
  • もし現在のノード n が sudoaddable であれば、つまりそのアドレス計算が最適化可能であれば、optoas(OAS, n->type) で適切な代入命令（例: AMOVQ）を取得します。
  • 結果がレジスタ (res->op == OREGISTER) であれば、gins(a, N, res) で直接 addr から res へ値を移動する命令を生成します。
  • そうでなければ、一時レジスタ n1 を割り当て、addr から n1 へ、そして n1 から res へと値を移動する命令を生成します。
  • このパスが実行された場合、return; で通常のコード生成ロジックをスキップし、効率的なコード生成を実現します。
• abop 内での sudoaddable の利用:
  • 非対称二項演算（abop）の処理中に、右オペランド nr が sudoaddable であるかをチェックする同様のブロックが追加されました。
  • これにより、二項演算の一方のオペランドが直接アドレス指定可能である場合に、より効率的なコードを生成できるようになります。

src/cmd/6g/gg.h の変更点

• sudoaddable 関数のプロトタイプ宣言 int sudoaddable(Node*, Type*, Addr*); が追加されました。これにより、他のファイルからこの関数を呼び出すことが可能になります。

src/cmd/6g/gsubr.c の変更点

• optoas の拡張:
  • optoas 関数に、OAS (代入) 操作に対する新しい case 文が多数追加されました。
  • これにより、TBOOL, TINT8, TUINT8 には AMOVB (Move Byte)、TINT16, TUINT16 には AMOVW (Move Word)、TINT32, TUINT32, TPTR32 には AMOVL (Move Long)、TINT64, TUINT64, TPTR64 には AMOVQ (Move Quad)、TFLOAT32 には AMOVSS (Move Scalar Single)、TFLOAT64 には AMOVSD (Move Scalar Double) といった、型に応じた最適なアセンブリ移動命令が選択されるようになりました。
• dotoffset 関数の新規追加:
  • この関数は、ODOT (フィールドアクセス) と ODOTPTR (ポインタデリファレンスとフィールドアクセス) ノードの連鎖を解析し、それらのオフセット情報を oary 配列に収集します。
  • oary には、直接オフセット（正の値）とポインタデリファレンス（負の値、-(xoffset+1) 形式）が混在して格納されます。
  • 再帰的に呼び出されることで、a.b.c や p->q.r のようなネストされたアクセスパスを処理します。
  • オフセットチェーンの基底となるノード（例: a や p）を nn に設定して返します。
• sudoaddable 関数の新規追加:
  • この関数は、特定の Node が直接アドレス指定可能であるかを判断し、可能であればそのアドレスを Addr 構造体 a に格納します。
  • まず、入力ノードとターゲット型の有効性および互換性を simtype を使ってチェックします。
  • switch(n->op) で ODOT または ODOTPTR の場合にのみ処理を進めます。
  • dotoffset を呼び出してオフセットチェーンと基底ノード nn を取得します。
  • 一時レジスタ n1 を割り当て、n2 を間接レジスタアクセスノードとして設定します。
  • 最初のオフセットが直接オフセット (oary[0] >= 0) の場合、agen(nn, &n1) で nn のアドレスを n1 に計算し、n2.xoffset を設定します。
  • 最初のオフセットがポインタデリファレンス (oary[0] < 0) の場合、cgen(nn, &n1) で nn の値を n1 に計算し、n2.xoffset を設定します。
  • 後続のオフセットについてはループで処理します。ここで、ポインタデリファレンス後に直接オフセットが続く場合は fatal("cant happen") でエラーとなります。これは、sudoaddable が処理できるアドレス指定パターンに制約があることを示します。
  • gins(AMOVQ, &n2, &n1) で、ポインタデリファレンスを実行し、n1 に新しいアドレスをロードします。
  • 最終的に naddr(&n2, a) で、計算されたアドレスを Addr 構造体 a に変換して格納します。
  • 成功した場合 1 を、失敗した場合 0 を返します。

これらの変更は、Goコンパイラが生成するアセンブリコードの品質と実行効率を向上させるための重要な最適化です。

関連リンク

• Go言語のコンパイラに関する初期のドキュメントや設計思想は、Goの公式リポジトリの doc/ ディレクトリや、初期のGoブログ記事に散見されます。
• Goコンパイラのソースコード: https://github.com/golang/go
• Goコンパイラの内部構造に関する一般的な情報:
  • "Go Compiler Internals" (Goのコンパイラに関するプレゼンテーションや記事)
  • "A Tour of the Go Compiler" (Goのコンパイラツアー)

参考にした情報源リンク

• Go言語の公式ドキュメント
• Goコンパイラのソースコード (特に src/cmd/6g/ ディレクトリ)
• x86-64 アセンブリ言語の命令セットリファレンス (MOV命令など)
• コンパイラ最適化に関する一般的な書籍やオンラインリソース (例: Dragon Book)
• Goの初期のコミット履歴と関連する議論 (Goのメーリングリストなど)