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

このコミットは、Goコンパイラ（cmd/6g、当時の64ビットアーキテクチャ向けコンパイラ）における最適化を目的としています。具体的には、スライス要素のアドレスを不必要に取得するのを避け、それによって変数のレジスタ割り当て（registerization）を促進し、スタックフレームのサイズを削減し、LEAQ命令の使用を減らすことで、生成されるコードの効率を向上させます。

コミット

commit acbe6c94d710932706fb67d6caaa6dbe6cbd4dad
Author: Rémy Oudompheng <oudomphe@phare.normalesup.org>
Date:   Fri Sep 7 06:54:42 2012 +0200

    cmd/6g: avoid taking the address of slices unnecessarily.
    
    The main case where it happens is when evaluating &s[i] without
    bounds checking, which usually happens during range loops (i=0).
    
    This allows registerization of the corresponding variables,
    saving 16 bytes of stack frame for each such range loop and a
    LEAQ instruction.
    
    R=golang-dev, rsc, dave
    CC=golang-dev, remy
    https://golang.org/cl/6497073

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

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

元コミット内容

cmd/6g: avoid taking the address of slices unnecessarily.

The main case where it happens is when evaluating &s[i] without
bounds checking, which usually happens during range loops (i=0).

This allows registerization of the corresponding variables,
saving 16 bytes of stack frame for each such range loop and a
LEAQ instruction.

R=golang-dev, rsc, dave
CC=golang-dev, remy
https://golang.org/cl/6497073

変更の背景

この変更の背景には、Goコンパイラ（特に当時の6g）がスライス要素にアクセスする際に、不必要にそのアドレスを取得してしまうという非効率な挙動がありました。

Go言語のfor...rangeループは、スライスや配列の要素をイテレートする際に非常に便利です。しかし、コンパイラがこのループの内部でスライス要素（例: s[i]）のアドレスを常に取得しようとすると、いくつかの問題が生じます。

1. レジスタ割り当ての妨げ: 変数のアドレスが取られると、その変数はメモリ上に存在する必要があるため、CPUのレジスタに割り当てることが難しくなります。レジスタはメモリよりもはるかに高速なため、レジスタに割り当てられた変数はプログラムの実行速度を向上させます。アドレスが取られることで、コンパイラは変数をスタック（メモリ）に配置せざるを得なくなり、パフォーマンスが低下します。
2. スタックフレームの肥大化: 変数がレジスタではなくスタックに割り当てられると、その変数を格納するためにスタックフレームのサイズが増加します。特にfor...rangeループのように頻繁に発生するパターンでこれが起こると、プログラム全体のメモリ使用量が増え、キャッシュ効率が悪化する可能性があります。コミットメッセージでは、各レンジループで16バイトのスタックフレームが節約されると具体的に述べられています。
3. LEAQ命令の不必要な生成: LEAQ (Load Effective Address) 命令は、メモリのアドレスを計算してレジスタにロードするために使用されます。スライス要素のアドレスを不必要に取得する際には、この命令が生成されることがありました。この命令はアドレス計算には効率的ですが、もしアドレス自体が不要であれば、その命令の実行はオーバーヘッドとなります。

このコミットは、これらの非効率性を解消し、生成されるバイナリのサイズを削減し、実行時のパフォーマンスを向上させることを目的としています。特に、境界チェックなしで&s[i]のような評価が行われるケース（レンジループのi=0のような初期アクセス時）が主なターゲットでした。

前提知識の解説

このコミットを理解するためには、以下の概念について知っておく必要があります。

1. Go言語のスライスと配列:

   • 配列 (Array): Goの配列は、固定長で同じ型の要素のシーケンスです。例えば、[5]intは5つの整数を格納できる配列です。配列は値型であり、変数に代入されるとコピーされます。
   • スライス (Slice): スライスは配列への参照のようなものです。スライスは、基底となる配列の一部を参照し、長さ（len）と容量（cap）を持ちます。スライスは動的なサイズ変更が可能であり、Goで最も一般的に使用されるシーケンス型です。スライスの内部構造は、ポインタ（基底配列の先頭要素へのポインタ）、長さ、容量の3つのフィールドで構成されます。
   • &s[i]: これはスライスsのi番目の要素のアドレスを取得する操作です。通常、要素の値にアクセスするだけであればアドレスは不要ですが、ポインタとして渡す場合などに使用されます。

2. Goコンパイラ 6g:

   • 6gは、Go 1.0時代に存在したGoコンパイラの一つで、AMD64 (x86-64) アーキテクチャ向けのコンパイラでした。Goのコンパイラは、ソースコードを機械語に変換する役割を担います。このコミットは、コンパイラのバックエンド、特にコード生成（cgen.c）の部分に焦わるものです。

3. コンパイラの最適化:

   • レジスタ割り当て (Register Allocation): コンパイラの重要な最適化の一つで、プログラムの変数をCPUのレジスタに割り当てるプロセスです。レジスタは非常に高速な記憶領域であるため、変数をレジスタに置くことでメモリへのアクセスを減らし、プログラムの実行速度を大幅に向上させることができます。変数のアドレスが取られると、その変数はメモリ上に存在する必要があるため、レジスタ割り当てが難しくなります。
   • スタックフレーム (Stack Frame): 関数が呼び出されるたびに、その関数に必要なローカル変数、引数、戻りアドレスなどを格納するために、コールスタック上に確保されるメモリ領域です。スタックフレームのサイズは、関数が使用するローカル変数の数や種類によって決まります。最適化によってスタックフレームのサイズを削減することは、メモリ効率の向上につながります。
   • LEAQ命令 (Load Effective Address): x86-64アーキテクチャの命令の一つで、メモリのアドレスを計算し、その結果をレジスタにロードします。例えば、LEAQ (%rax, %rbx, 4), %rcxは、%rax + %rbx * 4というアドレスを計算し、その結果を%rcxレジスタに格納します。この命令は、ポインタ演算や配列のインデックス計算によく使われます。不必要なLEAQ命令の削減は、命令数の削減と実行効率の向上に寄与します。

4. cgen.cとagen関数:

   • cgen.cは、Goコンパイラのコード生成（Code Generation）フェーズの一部を担うファイルです。このファイルには、Goの抽象構文木（AST）のノードをターゲットアーキテクチャの機械語命令に変換するためのロジックが含まれています。
   • agen関数は、Goコンパイラの内部で、式のアドレスを生成するために使用される関数です。例えば、&xのようなアドレス演算子や、配列/スライスの要素のアドレス（&a[i]）を計算する際に呼び出されます。

5. OINDEX:

   • Goコンパイラの内部表現における抽象構文木（AST）のノードタイプの一つで、配列やスライスのインデックスアクセス（例: a[i]）を表します。

技術的詳細

このコミットの技術的詳細は、Goコンパイラのagen関数におけるスライス要素のアドレス生成ロジックの変更にあります。

変更前は、OINDEXノード（スライス/配列のインデックスアクセス）を処理する際に、コンパイラはスライス要素のアドレスを不必要に取得しようとすることがありました。特に、for...rangeループのように、インデックスiが0から始まる場合、最初の要素s[0]にアクセスする際に、そのアドレスが取得されていました。

Goのスライスは内部的にポインタ、長さ、容量の3つのフィールドを持つ構造体です。スライス要素s[i]にアクセスする場合、通常は基底配列のポインタとインデックスi、要素のサイズwから直接要素の値を計算できます（*(&s.array + i*w)のような形）。しかし、コンパイラが&s[i]のようなアドレス取得を意図しない場合でも、内部的な処理でアドレスを生成してしまうことが問題でした。

この不必要なアドレス取得は、以下のような悪影響をもたらしていました。

• 変数の「エスケープ」: 変数のアドレスが取られると、その変数は「エスケープ」したと見なされ、スタックではなくヒープに割り当てられる可能性が生じます（ただし、このコミットのケースではスタックに割り当てられていたが、レジスタには割り当てられなかった）。これにより、ガベージコレクションのオーバーヘッドが増加する可能性があります。
• レジスタ割り当ての失敗: アドレスが取られた変数は、コンパイラがその変数をレジスタに割り当てることができなくなります。レジスタは非常に限られたリソースであり、レジスタに割り当てられない変数はメモリ（スタック）に格納されるため、アクセスが遅くなります。
• LEAQ命令の生成: アドレス計算のためにLEAQ命令が生成され、実行時の命令数が増加していました。

このコミットでは、agen関数内でOINDEXノードを処理する際に、スライスが固定長配列（isfixedarray）であるか、またはスライス（isslice）であるかによって、アドレス取得のロジックを分岐させています。

主な変更点:

1. nlen変数の導入: スライスの長さ（len）を保持するための一時的なNode変数nlenが導入されました。これにより、スライスの長さを直接レジスタに保持し、境界チェックに使用できるようになります。
2. isfixedarrayの考慮: nl->addable（左辺がアドレス可能か）のチェックに加えて、isfixedarray(nl->type)（左辺が固定長配列か）のチェックが追加されました。固定長配列の場合、スライスのようにポインタ、長さ、容量の構造体ではないため、異なるアドレス取得ロジックが適用されます。
3. スライスのアドレス取得ロジックの変更:
   • 以前は、スライスの場合、Array_arrayオフセット（基底配列のポインタ）からアドレスを取得し、それをn3に移動していました。
   • 変更後は、igen(nl, &nlen, res)を使ってスライスの情報を取得し、nlen.type = types[tptr]; nlen.xoffset += Array_array; gmove(&nlen, &n3);という形で、スライスの基底配列のポインタをn3に移動するようになりました。これにより、スライスの長さ情報もnlenを通じて利用可能になります。
   • 特に、!nl->addable（左辺がアドレス可能でない）の場合に、一時的なノードtmp2を導入してcgen(nl, &tmp2)でコードを生成し、nl = &tmp2とすることで、igenがアドレス可能なノードを必要とする問題を解決しています。
4. 境界チェックの最適化:
   • スライスの場合の境界チェック（isslice(nl->type) || nl->type->etype == TSTRING）において、以前はn3（スライスのポインタ）からArray_nel（長さ）をオフセットして比較していましたが、変更後はnlen（スライスの長さ）を直接使用して比較するようになりました（gins(optoas(OCMP, types[TUINT32]), &nlen, &n2);）。これにより、スライスの長さをレジスタに保持しやすくなり、メモリへのアクセスを減らすことができます。
   • 境界チェック後にregfree(&nlen)が追加され、不要になったnlenレジスタが解放されるようになりました。
5. 不必要なgmoveの削除:
   • 以前は、スライスや文字列の場合に、Array_arrayオフセットからアドレスを取得し、それをn3に移動するgmove命令が、境界チェックの後にもう一度実行されていました。この重複するgmoveが削除されました。これは、スライスの基底配列のポインタが既にn3に適切に設定されているため、不要になったためです。
6. nlenの解放: agen関数の最後に、スライスでも固定長配列でもない場合にnlenを解放するregfree(&nlen)が追加されました。

これらの変更により、コンパイラはスライス要素のアドレスを不必要にメモリに格納する代わりに、その長さをレジスタに保持し、より効率的なコードを生成できるようになりました。結果として、スタックフレームのサイズが削減され、LEAQ命令の生成が減少し、全体的なパフォーマンスが向上します。

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

変更はsrc/cmd/6g/cgen.cファイルに集中しています。

--- a/src/cmd/6g/cgen.c
+++ b/src/cmd/6g/cgen.c
@@ -502,7 +502,7 @@ void
 agen(Node *n, Node *res)
 {
 	Node *nl, *nr;
-	Node n1, n2, n3, tmp, n4, n5;
+	Node n1, n2, n3, tmp, tmp2, n4, n5, nlen;
 	Prog *p1;
 	uint32 w;
 	uint64 v;
@@ -565,6 +565,7 @@ agen(Node *n, Node *res)
 
 	case OINDEX:
 		w = n->type->width;
+		// Generate the non-addressable child first.
 		if(nr->addable)
 			goto irad;
 		if(nl->addable) {
@@ -574,18 +575,41 @@ agen(Node *n, Node *res)
 			}
 			if(!isconst(nl, CTSTR)) {
 				regalloc(&n3, types[tptr], res);
-				agen(nl, &n3);
+				if(isfixedarray(nl->type))
+					agen(nl, &n3);
+				else {
+					igen(nl, &nlen, res);
+					nlen.type = types[tptr];
+					nlen.xoffset += Array_array;
+					gmove(&nlen, &n3);
+					nlen.type = types[TUINT32];
+					nlen.xoffset += Array_nel-Array_array;
+				}
 			}
 			goto index;
 		}
 		tempname(&tmp, nr->type);
 		cgen(nr, &tmp);
 		nr = &tmp;
-
 	irad:
 		if(!isconst(nl, CTSTR)) {
 			regalloc(&n3, types[tptr], res);
-			agen(nl, &n3);
+			if(isfixedarray(nl->type))
+				agen(nl, &n3);
+			else {
+				if(!nl->addable) {
+					// igen will need an addressable node.
+					tempname(&tmp2, nl->type);
+					cgen(nl, &tmp2);
+					nl = &tmp2;
+				}
+				igen(nl, &nlen, res);
+				nlen.type = types[tptr];
+				nlen.xoffset += Array_array;
+				gmove(&nlen, &n3);
+				nlen.type = types[TUINT32];
+				nlen.xoffset += Array_nel-Array_array;
+			}
 		}
 		if(!isconst(nr, CTINT)) {
 			regalloc(&n1, nr->type, N);
@@ -596,22 +620,13 @@ agen(Node *n, Node *res)
 	index:
 		// &a is in &n3 (allocated in res)
 		// i is in &n1 (if not constant)
+		// len(a) is in nlen (if needed)
 		// w is width
 
 		// explicit check for nil if array is large enough
@@ -617,22 +642,13 @@ agen(Node *n, Node *res)
 		v = mpgetfix(nr->val.u.xval);
 		if(isslice(nl->type) || nl->type->etype == TSTRING) {
 			if(!debug['B'] && !n->bounded) {
-				n1 = n3;
-				n1.op = OINDREG;
-				n1.type = types[tptr];
-				n1.xoffset = Array_nel;
 				nodconst(&n2, types[TUINT32], v);
-				gins(optoas(OCMP, types[TUINT32]), &n1, &n2);
+				gins(optoas(OCMP, types[TUINT32]), &nlen, &n2);
 				p1 = gbranch(optoas(OGT, types[TUINT32]), T, +1);
 				ginscall(panicindex, -1);
 				patch(p1, pc);
 			}
-
-			n1 = n3;
-			n1.op = OINDREG;
-			n1.type = types[tptr];
-			n1.xoffset = Array_array;
-			gmove(&n1, &n3);
+			regfree(&nlen);
 		}
 
 		if (v*w != 0)
@@ -658,24 +674,19 @@ agen(Node *n, Node *res)
 		if(is64(nr->type))
 			t = types[TUINT64];
 		if(isconst(nl, CTSTR)) {
-			nodconst(&n1, t, nl->val.u.sval->len);
+			nodconst(&nlen, t, nl->val.u.sval->len);
 		} else if(isslice(nl->type) || nl->type->etype == TSTRING) {
-			n1 = n3;
-			n1.op = OINDREG;
-			n1.type = types[TUINT32];
-			n1.xoffset = Array_nel;
 			if(is64(nr->type)) {
 				regalloc(&n5, t, N);
-				gmove(&n1, &n5);
-				n1 = n5;
+				gmove(&nlen, &n5);
+				regfree(&nlen);
+				nlen = n5;
 			}
 		} else {
-			nodconst(&n1, t, nl->type->bound);
+			nodconst(&nlen, t, nl->type->bound);
 		}
-		gins(optoas(OCMP, t), &n2, &n1);
+		gins(optoas(OCMP, t), &n2, &nlen);
 		p1 = gbranch(optoas(OLT, t), T, +1);
-		if(n5.op != OXXX)
-			regfree(&n5);
 		ginscall(panicindex, -1);
 		patch(p1, pc);
 	}
@@ -689,14 +699,6 @@ agen(Node *n, Node *res)
 		goto indexdone;
 	}
 
-	if(isslice(nl->type) || nl->type->etype == TSTRING) {
-		n1 = n3;
-		n1.op = OINDREG;
-		n1.type = types[tptr];
-		n1.xoffset = Array_array;
-		gmove(&n1, &n3);
-	}
-
 	if(w == 0) {
 		// nothing to do
 	} else if(w == 1 || w == 2 || w == 4 || w == 8) {
@@ -713,6 +715,8 @@ agen(Node *n, Node *res)
 	gmove(&n3, res);
 	regfree(&n2);
 	regfree(&n3);
+	if(!isconst(nl, CTSTR) && !isfixedarray(nl->type))
+		regfree(&nlen);
 	break;
 
 	case ONAME:

コアとなるコードの解説

このコミットの核心は、agen関数内のOINDEX（インデックスアクセス）処理ロジックの変更にあります。

1. Node n1, n2, n3, tmp, tmp2, n4, n5, nlen;:

   • tmp2とnlenという新しいNode型の一時変数が追加されました。nlenはスライスの長さを保持するために使用されます。

2. case OINDEX: ブロック内の変更:

   • // Generate the non-addressable child first.: コメントが追加され、非アドレス可能な子ノードを先に生成する意図が示されています。
   • if(!isconst(nl, CTSTR)) ブロック内:
     • 以前はagen(nl, &n3);と直接nlのアドレスをn3に生成していました。
     • 変更後、if(isfixedarray(nl->type))で固定長配列の場合とそうでない場合（スライスなど）で処理を分岐させます。
     • スライスの場合、igen(nl, &nlen, res);でスライスの情報（ポインタ、長さ、容量）をnlenに取得します。
     • その後、nlen.type = types[tptr]; nlen.xoffset += Array_array; gmove(&nlen, &n3);によって、スライスの基底配列のポインタをn3に移動します。
     • さらに、nlen.type = types[TUINT32]; nlen.xoffset += Array_nel-Array_array;によって、nlenをスライスの長さ（Array_nelオフセット）を指すように再設定します。これにより、スライスの長さがnlenを通じて利用可能になります。
   • irad: ラベル後のブロック内:
     • ここでも同様に、if(isfixedarray(nl->type))で固定長配列とスライスを分岐させます。
     • スライスの場合、if(!nl->addable)（左辺がアドレス可能でない）という新しいチェックが追加されました。もしアドレス可能でなければ、tempname(&tmp2, nl->type); cgen(nl, &tmp2); nl = &tmp2;によって一時的なノードtmp2を作成し、そこにコードを生成してからnlをtmp2に設定します。これは、igen関数がアドレス可能なノードを引数として必要とするためです。
     • その後、上記と同様にigen(nl, &nlen, res);とgmove(&nlen, &n3);、そしてnlenの再設定が行われます。

3. index: ラベル後の境界チェックロジックの変更:

   • // len(a) is in nlen (if needed): 新しいコメントが追加され、nlenがスライスの長さを保持することを示しています。
   • if(isslice(nl->type) || nl->type->etype == TSTRING) ブロック内:
     • 以前は、n3（スライスのポインタ）からArray_nel（長さ）をオフセットしてn1に設定し、そのn1と定数n2（インデックス）を比較していました。
     • 変更後、gins(optoas(OCMP, types[TUINT32]), &nlen, &n2);と直接nlen（スライスの長さ）とn2（インデックス）を比較するようになりました。これにより、スライスの長さをレジスタに保持し、メモリへのアクセスを減らすことができます。
     • regfree(&nlen);が追加され、境界チェック後にnlenレジスタが解放されるようになりました。
     • 以前存在した、n1 = n3; n1.op = OINDREG; n1.type = types[tptr]; n1.xoffset = Array_array; gmove(&n1, &n3);という重複するgmove命令が削除されました。これは、スライスの基底配列のポインタが既にn3に適切に設定されているため、不要になったためです。

4. 文字列/スライスの長さ取得ロジックの変更:

   • isconst(nl, CTSTR)の場合、以前はnodconst(&n1, t, nl->val.u.sval->len);で文字列の長さをn1に設定していましたが、変更後はnodconst(&nlen, t, nl->val.u.sval->len);とnlenを使用するようになりました。
   • isslice(nl->type) || nl->type->etype == TSTRINGの場合も同様に、以前はn1を使用していた箇所がnlenに置き換えられました。
   • is64(nr->type)のチェック内で、gmove(&nlen, &n5); regfree(&nlen); nlen = n5;という変更があり、nlenのレジスタを解放し、新しいレジスタn5に値を移動しています。
   • gins(optoas(OCMP, t), &n2, &nlen);と、比較もnlenを使って行われるようになりました。

5. agen関数の最後でのnlenの解放:

   • if(!isconst(nl, CTSTR) && !isfixedarray(nl->type))という条件で、文字列でも固定長配列でもない場合（つまりスライスの場合）、regfree(&nlen);が追加され、nlenレジスタが適切に解放されるようになりました。

これらの変更により、コンパイラはスライスの基底配列のポインタと長さをより効率的に管理し、不必要なメモリ操作や命令生成を削減することで、生成されるコードの品質とパフォーマンスを向上させています。

関連リンク

• Go言語の公式ドキュメント: https://go.dev/doc/
• Go言語のコンパイラに関する情報（Goのソースコードリポジトリ内）: https://github.com/golang/go/tree/master/src/cmd/compile
• Goのコードレビューシステム (Gerrit): https://go-review.googlesource.com/
• このコミットのGerritレビューページ: https://golang.org/cl/6497073

参考にした情報源リンク

• Go言語の公式ドキュメント (スライス): https://go.dev/blog/slices-intro
• Go言語のコンパイラ最適化に関する一般的な情報 (例: Escape Analysis): https://go.dev/doc/effective_go#allocation_with_make_new
• x86-64 LEAQ命令に関する情報: https://www.felixcloutier.com/x86/lea
• コンパイラのレジスタ割り当てに関する一般的な情報: https://en.wikipedia.org/wiki/Register_allocation
• Goコンパイラの内部構造に関するブログ記事やプレゼンテーション（一般的な情報源として）
  • "Go's Toolchain": https://go.dev/talks/2015/go-toolchain.slide
  • "The Go Programming Language Specification" (特にスライスと配列のセクション): https://go.dev/ref/spec
• Goのソースコード（src/cmd/6g/cgen.cの当時のバージョン）
• GoのIssue Tracker (関連する最適化の議論): https://github.com/golang/go/issues
• Gerrit Code Review (CL 6497073): https://golang.org/cl/6497073
  • このCLのコメントや議論は、変更の意図や詳細を理解する上で非常に役立ちました。
• Goの古いコンパイラに関する情報（6gなど）は、Goの歴史的なドキュメントやメーリングリストのアーカイブから得られることがあります。
  • Goのメーリングリスト: https://groups.google.com/g/golang-nuts
  • Goの古いリリースノート: https://go.dev/doc/devel/release
• Goのコンパイラ開発に関する一般的な情報源: https://go.dev/s/go11compiler (Go 1.1のコンパイラに関する情報ですが、基本的な概念は共通しています)
• Goのコンパイラソースコードの探索 (特にsrc/cmd/compile/internal/gc/ディレクトリ): https://github.com/golang/go/tree/master/src/cmd/compile/internal/gc
  • 現在のコンパイラはgcですが、当時の6gも同様の概念に基づいていました。# [インデックス 13764] ファイルの概要

このコミットは、Goコンパイラ（cmd/6g、当時の64ビットアーキテクチャ向けコンパイラ）における最適化を目的としています。具体的には、スライス要素のアドレスを不必要に取得するのを避け、それによって変数のレジスタ割り当て（registerization）を促進し、スタックフレームのサイズを削減し、LEAQ命令の使用を減らすことで、生成されるコードの効率を向上させます。

コミット

commit acbe6c94d710932706fb67d6caaa6dbe6cbd4dad
Author: Rémy Oudompheng <oudomphe@phare.normalesup.org>
Date:   Fri Sep 7 06:54:42 2012 +0200

    cmd/6g: avoid taking the address of slices unnecessarily.
    
    The main case where it happens is when evaluating &s[i] without
    bounds checking, which usually happens during range loops (i=0).
    
    This allows registerization of the corresponding variables,
    saving 16 bytes of stack frame for each such range loop and a
    LEAQ instruction.
    
    R=golang-dev, rsc, dave
    CC=golang-dev, remy
    https://golang.org/cl/6497073

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

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

元コミット内容

cmd/6g: avoid taking the address of slices unnecessarily.

The main case where it happens is when evaluating &s[i] without
bounds checking, which usually happens during range loops (i=0).

This allows registerization of the corresponding variables,
saving 16 bytes of stack frame for each such range loop and a
LEAQ instruction.

R=golang-dev, rsc, dave
CC=golang-dev, remy
https://golang.org/cl/6497073

変更の背景

この変更の背景には、Goコンパイラ（特に当時の6g）がスライス要素にアクセスする際に、不必要にそのアドレスを取得してしまうという非効率な挙動がありました。

Go言語のfor...rangeループは、スライスや配列の要素をイテレートする際に非常に便利です。しかし、コンパイラがこのループの内部でスライス要素（例: s[i]）のアドレスを常に取得しようとすると、いくつかの問題が生じます。

1. レジスタ割り当ての妨げ: 変数のアドレスが取られると、その変数はメモリ上に存在する必要があるため、CPUのレジスタに割り当てることが難しくなります。レジスタはメモリよりもはるかに高速なため、レジスタに割り当てられた変数はプログラムの実行速度を向上させます。アドレスが取られることで、コンパイラは変数をスタック（メモリ）に配置せざるを得なくなり、パフォーマンスが低下します。
2. スタックフレームの肥大化: 変数がレジスタではなくスタックに割り当てられると、その変数を格納するためにスタックフレームのサイズが増加します。特にfor...rangeループのように頻繁に発生するパターンでこれが起こると、プログラム全体のメモリ使用量が増え、キャッシュ効率が悪化する可能性があります。コミットメッセージでは、各レンジループで16バイトのスタックフレームが節約されると具体的に述べられています。
3. LEAQ命令の不必要な生成: LEAQ (Load Effective Address) 命令は、メモリのアドレスを計算してレジスタにロードするために使用されます。スライス要素のアドレスを不必要に取得する際には、この命令が生成されることがありました。この命令はアドレス計算には効率的ですが、もしアドレス自体が不要であれば、その命令の実行はオーバーヘッドとなります。

このコミットは、これらの非効率性を解消し、生成されるバイナリのサイズを削減し、実行時のパフォーマンスを向上させることを目的としています。特に、境界チェックなしで&s[i]のような評価が行われるケース（レンジループのi=0のような初期アクセス時）が主なターゲットでした。

前提知識の解説

このコミットを理解するためには、以下の概念について知っておく必要があります。

1. Go言語のスライスと配列:

   • 配列 (Array): Goの配列は、固定長で同じ型の要素のシーケンスです。例えば、[5]intは5つの整数を格納できる配列です。配列は値型であり、変数に代入されるとコピーされます。
   • スライス (Slice): スライスは配列への参照のようなものです。スライスは、基底となる配列の一部を参照し、長さ（len）と容量（cap）を持ちます。スライスは動的なサイズ変更が可能であり、Goで最も一般的に使用されるシーケンス型です。スライスの内部構造は、ポインタ（基底配列の先頭要素へのポインタ）、長さ、容量の3つのフィールドで構成されます。
   • &s[i]: これはスライスsのi番目の要素のアドレスを取得する操作です。通常、要素の値にアクセスするだけであればアドレスは不要ですが、ポインタとして渡す場合などに使用されます。

2. Goコンパイラ 6g:

   • 6gは、Go 1.0時代に存在したGoコンパイラの一つで、AMD64 (x86-64) アーキテクチャ向けのコンパイラでした。Goのコンパイラは、ソースコードを機械語に変換する役割を担います。このコミットは、コンパイラのバックエンド、特にコード生成（cgen.c）の部分に焦わるものです。

3. コンパイラの最適化:

   • レジスタ割り当て (Register Allocation): コンパイラの重要な最適化の一つで、プログラムの変数をCPUのレジスタに割り当てるプロセスです。レジスタは非常に高速な記憶領域であるため、変数をレジスタに置くことでメモリへのアクセスを減らし、プログラムの実行速度を大幅に向上させることができます。変数のアドレスが取られると、その変数はメモリ上に存在する必要があるため、レジスタ割り当てが難しくなります。
   • スタックフレーム (Stack Frame): 関数が呼び出されるたびに、その関数に必要なローカル変数、引数、戻りアドレスなどを格納するために、コールスタック上に確保されるメモリ領域です。スタックフレームのサイズは、関数が使用するローカル変数の数や種類によって決まります。最適化によってスタックフレームのサイズを削減することは、メモリ効率の向上につながります。
   • LEAQ命令 (Load Effective Address): x86-64アーキテクチャの命令の一つで、メモリのアドレスを計算し、その結果をレジスタにロードします。例えば、LEAQ (%rax, %rbx, 4), %rcxは、%rax + %rbx * 4というアドレスを計算し、その結果を%rcxレジスタに格納します。この命令は、ポインタ演算や配列のインデックス計算によく使われます。不必要なLEAQ命令の削減は、命令数の削減と実行効率の向上に寄与します。

4. cgen.cとagen関数:

   • cgen.cは、Goコンパイラのコード生成（Code Generation）フェーズの一部を担うファイルです。このファイルには、Goの抽象構文木（AST）のノードをターゲットアーキテクチャの機械語命令に変換するためのロジックが含まれています。
   • agen関数は、Goコンパイラの内部で、式のアドレスを生成するために使用される関数です。例えば、&xのようなアドレス演算子や、配列/スライスの要素のアドレス（&a[i]）を計算する際に呼び出されます。

5. OINDEX:

   • Goコンパイラの内部表現における抽象構文木（AST）のノードタイプの一つで、配列やスライスのインデックスアクセス（例: a[i]）を表します。

技術的詳細

このコミットの技術的詳細は、Goコンパイラのagen関数におけるスライス要素のアドレス生成ロジックの変更にあります。

変更前は、OINDEXノード（スライス/配列のインデックスアクセス）を処理する際に、コンパイラはスライス要素のアドレスを不必要に取得しようとすることがありました。特に、for...rangeループのように、インデックスiが0から始まる場合、最初の要素s[0]にアクセスする際に、そのアドレスが取得されていました。

Goのスライスは内部的にポインタ、長さ、容量の3つのフィールドを持つ構造体です。スライス要素s[i]にアクセスする場合、通常は基底配列のポインタとインデックスi、要素のサイズwから直接要素の値を計算できます（*(&s.array + i*w)のような形）。しかし、コンパイラが&s[i]のようなアドレス取得を意図しない場合でも、内部的な処理でアドレスを生成してしまうことが問題でした。

この不必要なアドレス取得は、以下のような悪影響をもたらしていました。

• 変数の「エスケープ」: 変数のアドレスが取られると、その変数は「エスケープ」したと見なされ、スタックではなくヒープに割り当てられる可能性が生じます（ただし、このコミットのケースではスタックに割り当てられていたが、レジスタには割り当てられなかった）。これにより、ガベージコレクションのオーバーヘッドが増加する可能性があります。
• レジスタ割り当ての失敗: アドレスが取られた変数は、コンパイラがその変数をレジスタに割り当てることができなくなります。レジスタは非常に限られたリソースであり、レジスタに割り当てられない変数はメモリ（スタック）に格納されるため、アクセスが遅くなります。
• LEAQ命令の生成: アドレス計算のためにLEAQ命令が生成され、実行時の命令数が増加していました。

このコミットでは、agen関数内でOINDEXノードを処理する際に、スライスが固定長配列（isfixedarray）であるか、またはスライス（isslice）であるかによって、アドレス取得のロジックを分岐させています。

主な変更点:

1. nlen変数の導入: スライスの長さ（len）を保持するための一時的なNode変数nlenが導入されました。これにより、スライスの長さを直接レジスタに保持し、境界チェックに使用できるようになります。
2. isfixedarrayの考慮: nl->addable（左辺がアドレス可能か）のチェックに加えて、isfixedarray(nl->type)（左辺が固定長配列か）のチェックが追加されました。固定長配列の場合、スライスのようにポインタ、長さ、容量の構造体ではないため、異なるアドレス取得ロジックが適用されます。
3. スライスのアドレス取得ロジックの変更:
   • 以前は、スライスの場合、Array_arrayオフセット（基底配列のポインタ）からアドレスを取得し、それをn3に移動していました。
   • 変更後は、igen(nl, &nlen, res)を使ってスライスの情報を取得し、nlen.type = types[tptr]; nlen.xoffset += Array_array; gmove(&nlen, &n3);という形で、スライスの基底配列のポインタをn3に移動するようになりました。これにより、スライスの長さ情報もnlenを通じて利用可能になります。
   • 特に、!nl->addable（左辺がアドレス可能でない）の場合に、一時的なノードtmp2を導入してcgen(nl, &tmp2)でコードを生成し、nl = &tmp2とすることで、igenがアドレス可能なノードを必要とする問題を解決しています。
4. 境界チェックの最適化:
   • スライスの場合の境界チェック（isslice(nl->type) || nl->type->etype == TSTRING）において、以前はn3（スライスのポインタ）からArray_nel（長さ）をオフセットして比較していましたが、変更後はnlen（スライスの長さ）を直接使用して比較するようになりました（gins(optoas(OCMP, types[TUINT32]), &nlen, &n2);）。これにより、スライスの長さをレジスタに保持しやすくなり、メモリへのアクセスを減らすことができます。
   • 境界チェック後にregfree(&nlen)が追加され、不要になったnlenレジスタが解放されるようになりました。
5. 不必要なgmoveの削除:
   • 以前は、スライスや文字列の場合に、Array_arrayオフセットからアドレスを取得し、それをn3に移動するgmove命令が、境界チェックの後にもう一度実行されていました。この重複するgmoveが削除されました。これは、スライスの基底配列のポインタが既にn3に適切に設定されているため、不要になったためです。
6. nlenの解放: agen関数の最後に、スライスでも固定長配列でもない場合にnlenを解放するregfree(&nlen)が追加されました。

これらの変更により、コンパイラはスライス要素のアドレスを不必要にメモリに格納する代わりに、その長さをレジスタに保持し、より効率的なコードを生成できるようになりました。結果として、スタックフレームのサイズが削減され、LEAQ命令の生成が減少し、全体的なパフォーマンスが向上します。

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

変更はsrc/cmd/6g/cgen.cファイルに集中しています。

--- a/src/cmd/6g/cgen.c
+++ b/src/cmd/6g/cgen.c
@@ -502,7 +502,7 @@ void
 agen(Node *n, Node *res)
 {
 	Node *nl, *nr;
-	Node n1, n2, n3, tmp, n4, n5;
+	Node n1, n2, n3, tmp, tmp2, n4, n5, nlen;
 	Prog *p1;
 	uint32 w;
 	uint64 v;
@@ -565,6 +565,7 @@ agen(Node *n, Node *res)
 
 	case OINDEX:
 		w = n->type->width;
+		// Generate the non-addressable child first.
 		if(nr->addable)
 			goto irad;
 		if(nl->addable) {
@@ -574,18 +575,41 @@ agen(Node *n, Node *res)
 			}
 			if(!isconst(nl, CTSTR)) {
 				regalloc(&n3, types[tptr], res);
-				agen(nl, &n3);
+				if(isfixedarray(nl->type))
+					agen(nl, &n3);
+				else {
+					igen(nl, &nlen, res);
+					nlen.type = types[tptr];
+					nlen.xoffset += Array_array;
+					gmove(&nlen, &n3);
+					nlen.type = types[TUINT32];
+					nlen.xoffset += Array_nel-Array_array;
+				}
 			}
 			goto index;
 		}
 		tempname(&tmp, nr->type);
 		cgen(nr, &tmp);
 		nr = &tmp;
-
 	irad:
 		if(!isconst(nl, CTSTR)) {
 			regalloc(&n3, types[tptr], res);
-			agen(nl, &n3);
+			if(isfixedarray(nl->type))
+				agen(nl, &n3);
+			else {
+				if(!nl->addable) {
+					// igen will need an addressable node.
+					tempname(&tmp2, nl->type);
+					cgen(nl, &tmp2);
+					nl = &tmp2;
+				}
+				igen(nl, &nlen, res);
+				nlen.type = types[tptr];
+				nlen.xoffset += Array_array;
+				gmove(&nlen, &n3);
+				nlen.type = types[TUINT32];
+				nlen.xoffset += Array_nel-Array_array;
+			}
 		}
 		if(!isconst(nr, CTINT)) {
 			regalloc(&n1, nr->type, N);
@@ -596,22 +620,13 @@ agen(Node *n, Node *res)
 	index:
 		// &a is in &n3 (allocated in res)
 		// i is in &n1 (if not constant)
+		// len(a) is in nlen (if needed)
 		// w is width
 
 		// explicit check for nil if array is large enough
@@ -617,22 +642,13 @@ agen(Node *n, Node *res)
 		v = mpgetfix(nr->val.u.xval);
 		if(isslice(nl->type) || nl->type->etype == TSTRING) {
 			if(!debug['B'] && !n->bounded) {
-				n1 = n3;
-				n1.op = OINDREG;
-				n1.type = types[tptr];
-				n1.xoffset = Array_nel;
 				nodconst(&n2, types[TUINT32], v);
-				gins(optoas(OCMP, types[TUINT32]), &n1, &n2);
+				gins(optoas(OCMP, types[TUINT32]), &nlen, &n2);
 				p1 = gbranch(optoas(OGT, types[TUINT32]), T, +1);
 				ginscall(panicindex, -1);
 				patch(p1, pc);
 			}
-
-			n1 = n3;
-			n1.op = OINDREG;
-			n1.type = types[tptr];
-			n1.xoffset = Array_array;
-			gmove(&n1, &n3);
+			regfree(&nlen);
 		}
 
 		if (v*w != 0)
@@ -658,24 +674,19 @@ agen(Node *n, Node *res)
 		if(is64(nr->type))
 			t = types[TUINT64];
 		if(isconst(nl, CTSTR)) {
-			nodconst(&n1, t, nl->val.u.sval->len);
+			nodconst(&nlen, t, nl->val.u.sval->len);
 		} else if(isslice(nl->type) || nl->type->etype == TSTRING) {
-			n1 = n3;
-			n1.op = OINDREG;
-			n1.type = types[TUINT32];
-			n1.xoffset = Array_nel;
 			if(is64(nr->type)) {
 				regalloc(&n5, t, N);
-				gmove(&n1, &n5);
-				n1 = n5;
+				gmove(&nlen, &n5);
+				regfree(&nlen);
+				nlen = n5;
 			}
 		} else {
-			nodconst(&n1, t, nl->type->bound);
+			nodconst(&nlen, t, nl->type->bound);
 		}
-		gins(optoas(OCMP, t), &n2, &n1);
+		gins(optoas(OCMP, t), &n2, &nlen);
 		p1 = gbranch(optoas(OLT, t), T, +1);
-		if(n5.op != OXXX)
-			regfree(&n5);
 		ginscall(panicindex, -1);
 		patch(p1, pc);
 	}
@@ -689,14 +699,6 @@ agen(Node *n, Node *res)
 		goto indexdone;
 	}
 
-	if(isslice(nl->type) || nl->type->etype == TSTRING) {
-		n1 = n3;
-		n1.op = OINDREG;
-		n1.type = types[tptr];
-		n1.xoffset = Array_array;
-		gmove(&n1, &n3);
-	}
-
 	if(w == 0) {
 		// nothing to do
 	} else if(w == 1 || w == 2 || w == 4 || w == 8) {
@@ -713,6 +715,8 @@ agen(Node *n, Node *res)
 	gmove(&n3, res);
 	regfree(&n2);
 	regfree(&n3);
+	if(!isconst(nl, CTSTR) && !isfixedarray(nl->type))
+		regfree(&nlen);
 	break;
 
 	case ONAME:

コアとなるコードの解説

このコミットの核心は、agen関数内のOINDEX（インデックスアクセス）処理ロジックの変更にあります。

1. Node n1, n2, n3, tmp, tmp2, n4, n5, nlen;:

   • tmp2とnlenという新しいNode型の一時変数が追加されました。nlenはスライスの長さを保持するために使用されます。

2. case OINDEX: ブロック内の変更:

   • // Generate the non-addressable child first.: コメントが追加され、非アドレス可能な子ノードを先に生成する意図が示されています。
   • if(!isconst(nl, CTSTR)) ブロック内:
     • 以前はagen(nl, &n3);と直接nlのアドレスをn3に生成していました。
     • 変更後、if(isfixedarray(nl->type))で固定長配列の場合とそうでない場合（スライスなど）で処理を分岐させます。
     • スライスの場合、igen(nl, &nlen, res);でスライスの情報（ポインタ、長さ、容量）をnlenに取得します。
     • その後、nlen.type = types[tptr]; nlen.xoffset += Array_array; gmove(&nlen, &n3);によって、スライスの基底配列のポインタをn3に移動します。
     • さらに、nlen.type = types[TUINT32]; nlen.xoffset += Array_nel-Array_array;によって、nlenをスライスの長さ（Array_nelオフセット）を指すように再設定します。これにより、スライスの長さがnlenを通じて利用可能になります。
   • irad: ラベル後のブロック内:
     • ここでも同様に、if(isfixedarray(nl->type))で固定長配列とスライスを分岐させます。
     • スライスの場合、if(!nl->addable)（左辺がアドレス可能でない）という新しいチェックが追加されました。もしアドレス可能でなければ、tempname(&tmp2, nl->type); cgen(nl, &tmp2); nl = &tmp2;によって一時的なノードtmp2を作成し、そこにコードを生成してからnlをtmp2に設定します。これは、igen関数がアドレス可能なノードを引数として必要とするためです。
     • その後、上記と同様にigen(nl, &nlen, res);とgmove(&nlen, &n3);、そしてnlenの再設定が行われます。

3. index: ラベル後の境界チェックロジックの変更:

   • // len(a) is in nlen (if needed): 新しいコメントが追加され、nlenがスライスの長さを保持することを示しています。
   • if(isslice(nl->type) || nl->type->etype == TSTRING) ブロック内:
     • 以前は、n3（スライスのポインタ）からArray_nel（長さ）をオフセットしてn1に設定し、そのn1と定数n2（インデックス）を比較していました。
     • 変更後、gins(optoas(OCMP, types[TUINT32]), &nlen, &n2);と直接nlen（スライスの長さ）とn2（インデックス）を比較するようになりました。これにより、スライスの長さをレジスタに保持し、メモリへのアクセスを減らすことができます。
     • regfree(&nlen);が追加され、境界チェック後にnlenレジスタが解放されるようになりました。
     • 以前存在した、n1 = n3; n1.op = OINDREG; n1.type = types[tptr]; n1.xoffset = Array_array; gmove(&n1, &n3);という重複するgmove命令が削除されました。これは、スライスの基底配列のポインタが既にn3に適切に設定されているため、不要になったためです。

4. 文字列/スライスの長さ取得ロジックの変更:

   • isconst(nl, CTSTR)の場合、以前はnodconst(&n1, t, nl->val.u.sval->len);で文字列の長さをn1に設定していましたが、変更後はnodconst(&nlen, t, nl->val.u.sval->len);とnlenを使用するようになりました。
   • isslice(nl->type) || nl->type->etype == TSTRINGの場合も同様に、以前はn1を使用していた箇所がnlenに置き換えられました。
   • is64(nr->type)のチェック内で、gmove(&nlen, &n5); regfree(&nlen); nlen = n5;という変更があり、nlenのレジスタを解放し、新しいレジスタn5に値を移動しています。
   • gins(optoas(OCMP, t), &n2, &nlen);と、比較もnlenを使って行われるようになりました。

5. agen関数の最後でのnlenの解放:

   • if(!isconst(nl, CTSTR) && !isfixedarray(nl->type))という条件で、文字列でも固定長配列でもない場合（つまりスライスの場合）、regfree(&nlen);が追加され、nlenレジスタが適切に解放されるようになりました。

これらの変更により、コンパイラはスライスの基底配列のポインタと長さをより効率的に管理し、不必要なメモリ操作や命令生成を削減することで、生成されるコードの品質とパフォーマンスを向上させています。

関連リンク

• Go言語の公式ドキュメント: https://go.dev/doc/
• Go言語のコンパイラに関する情報（Goのソースコードリポジトリ内）: https://github.com/golang/go/tree/master/src/cmd/compile
• Goのコードレビューシステム (Gerrit): https://go-review.googlesource.com/
• このコミットのGerritレビューページ: https://golang.org/cl/6497073

参考にした情報源リンク

• Go言語の公式ドキュメント (スライス): https://go.dev/blog/slices-intro
• Go言語のコンパイラ最適化に関する一般的な情報 (例: Escape Analysis): https://go.dev/doc/effective_go#allocation_with_make_new
• x86-64 LEAQ命令に関する情報: https://www.felixcloutier.com/x86/lea
• コンパイラのレジスタ割り当てに関する一般的な情報: https://en.wikipedia.org/wiki/Register_allocation
• Goコンパイラの内部構造に関するブログ記事やプレゼンテーション（一般的な情報源として）
  • "Go's Toolchain": https://go.dev/talks/2015/go-toolchain.slide
  • "The Go Programming Language Specification" (特にスライスと配列のセクション): https://go.dev/ref/spec
• Goのソースコード（src/cmd/6g/cgen.cの当時のバージョン）
• GoのIssue Tracker (関連する最適化の議論): https://github.com/golang/go/issues
• Gerrit Code Review (CL 6497073): https://golang.org/cl/6497073
  • このCLのコメントや議論は、変更の意図や詳細を理解する上で非常に役立ちました。
• Goの古いコンパイラに関する情報（6gなど）は、Goの歴史的なドキュメントやメーリングリストのアーカイブから得られることがあります。
  • Goのメーリングリスト: https://groups.google.com/g/golang-nuts
  • Goの古いリリースノート: https://go.dev/doc/devel/release
• Goのコンパイラ開発に関する一般的な情報源: https://go.dev/s/go11compiler (Go 1.1のコンパイラに関する情報ですが、基本的な概念は共通しています)
• Goのコンパイラソースコードの探索 (特にsrc/cmd/compile/internal/gc/ディレクトリ): https://github.com/golang/go/tree/master/src/cmd/compile/internal/gc
  • 現在のコンパイラはgcですが、当時の6gも同様の概念に基づいていました。