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

このコミットは、Goコンパイラの6g（64ビットアーキテクチャ向け）のコード生成部分、具体的にはsrc/cmd/6g/cgen.cファイルに対する変更です。主な目的は、配列やスライスのインデックス処理における最適化と、それに伴うバグ修正です。

コミット

commit a6182dab47eadcd4f90ee8ef2c99e5e8fef2c89e
Author: Ken Thompson <ken@golang.org>
Date:   Sun Nov 23 17:26:49 2008 -0800

    indexing optimizations and bug fix

    R=r
    OCL=19886
    CL=19886

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

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

元コミット内容

このコミットは、Goコンパイラの6g（64ビットアーキテクチャ向け）のコードジェネレータであるcgen.cファイルにおいて、配列およびスライスのインデックス処理に関する最適化とバグ修正を行っています。具体的には、インデックス計算の効率化、特に定数インデックスの場合の処理の改善、そして動的配列（スライス）の境界チェックと基底アドレスの取得ロジックの修正が含まれています。

変更の背景

Go言語は、その設計当初から安全性とパフォーマンスの両立を目指していました。配列やスライスへのアクセスにおける境界チェック（bounds checking）は、メモリ安全性を保証するための重要な機能です。しかし、このチェックは実行時のオーバーヘッドを伴う可能性があります。

このコミットが行われた2008年11月は、Go言語がまだ初期開発段階にあった時期です。コンパイラの最適化は、言語のパフォーマンスを向上させる上で不可欠な要素でした。特に、配列やスライスのインデックスアクセスは非常に頻繁に行われる操作であるため、ここでの効率改善は全体の実行速度に大きな影響を与えます。

変更の背景には、以下の点が考えられます。

1. パフォーマンスの向上: インデックス計算のコード生成をより効率的にすることで、生成されるアセンブリコードの命令数を減らし、実行速度を向上させる。特に、定数インデックスの場合にコンパイル時最適化を適用することで、実行時の計算を省略できる。
2. バグの修正: 既存のインデックス処理ロジックに潜在するバグ、特に動的配列（スライス）の境界チェックや基底アドレスの取得に関する問題を解決する。
3. コードの整理と改善: コード生成ロジックをより明確で保守しやすいものにする。

このコミットは、Goコンパイラの初期の最適化努力の一環であり、言語の基本的なランタイムパフォーマンスを確立する上で重要な役割を果たしました。

前提知識の解説

このコミットを理解するためには、以下のGoコンパイラおよび関連する概念に関する知識が必要です。

1. Goコンパイラ（6g）:
   • Go言語の初期のコンパイラ群は、ターゲットアーキテクチャごとに5g (ARM), 6g (x86-64), 8g (x86) のように命名されていました。6gは64ビットIntel/AMDアーキテクチャ向けのコンパイラです。
   • これらのコンパイラは、Goのソースコードをアセンブリコードに変換する役割を担っていました。
2. cgen.c:
   • cgen.cは"code generation"の略で、コンパイラのバックエンドの一部です。抽象構文木（AST）を走査し、ターゲットアーキテクチャ（この場合はx86-64）の機械語命令を生成する役割を担います。
   • agen関数は、アドレス生成（address generation）を担当する関数で、配列や構造体の要素へのアクセスなど、メモリアドレスを計算する必要がある場合に呼び出されます。
3. Goの配列とスライス:
   • 配列 (Array): 固定長で、コンパイル時にサイズが決定されます。[N]Tのように宣言されます。
   • スライス (Slice): 可変長で、実行時にサイズが決定されます。配列のセグメントを参照するデータ構造であり、ポインタ、長さ（len）、容量（cap）の3つの要素から構成されます。Goのコードでは、スライスが配列よりも頻繁に使用されます。
4. 境界チェック (Bounds Checking):
   • Go言語では、配列やスライスにアクセスする際に、インデックスが有効な範囲内にあるかを自動的にチェックします。インデックスが範囲外の場合、ランタイムパニック（panic: runtime error: index out of range）が発生します。
   • このチェックは、C/C++のような言語で発生しがちなバッファオーバーフローなどのメモリ安全性の問題を防止するために重要です。
   • コンパイラは、可能な限り境界チェックを最適化（省略）しようとしますが、動的なインデックスの場合など、実行時にチェックが必要な場合があります。
   • debug['B']は、コンパイラのデバッグフラグの一つで、境界チェックを強制的に有効にする（または無効にする）ために使用されることがあります。
5. Node構造体:
   • コンパイラ内部で、ASTのノードを表すデータ構造です。Nodeは、変数、定数、演算子、関数呼び出しなど、プログラムの様々な要素を表現します。
   • nlとnrは、それぞれノードの左の子と右の子を指すことが多いです（例: a[i]の場合、aがnl、iがnr）。
   • addableは、そのノードがアドレスとして直接使用できるか（例: 変数）を示すフラグかもしれません。
   • whatis(nr) == Wlitintは、nrがリテラル整数（定数）であるかをチェックしています。
6. レジスタ割り当てとコード生成関数:
   • regalloc(&n1, type, N): レジスタを割り当て、その情報をn1に格納します。Nはnilノードを意味し、特定のレジスタを要求しないことを示します。
   • cgen(node, res): nodeの値を計算し、その結果をresに格納するコードを生成します。
   • agen(node, res): nodeのアドレスを計算し、その結果をresに格納するコードを生成します。
   • gmove(src, dst): srcからdstへ値を移動するアセンブリ命令を生成します。
   • gins(op, src, dst): 指定されたオペレーションopとオペランドsrc, dstを持つアセンブリ命令を生成します。
   • nodconst(&n, type, val): 定数valを持つノードnを作成します。
   • mpgetfix(val): 多倍長整数valから固定小数点値を取得します。
   • optoas(op, type): 抽象的な演算子opを、指定されたtypeに応じたアセンブリ命令に変換します。
   • throwindex: 境界チェックに失敗した場合に呼び出されるランタイム関数（パニックを発生させる）。
7. Array構造体とoffsetof:
   • Goのランタイム内部でスライスを表現するために使用される構造体（またはそれに相当する概念）です。
   • offsetof(Array, nel): Array構造体内のnel（number of elements、要素数）フィールドのオフセットを取得します。
   • offsetof(Array, array): Array構造体内のarray（基底配列へのポインタ）フィールドのオフセットを取得します。
   • isptrdarray(type): ポインタを持つ動的配列（スライス）であるかをチェックします。
   • isptrarray(type): ポインタを持つ配列であるかをチェックします。

これらの概念を理解することで、コミットがGoコンパイラの低レベルなコード生成と最適化にどのように関わっているかを把握できます。

技術的詳細

このコミットの技術的詳細は、src/cmd/6g/cgen.c内のagen関数における配列/スライスインデックス処理の変更に集約されます。agen関数は、メモリ上のアドレスを計算するコードを生成する役割を担っています。

変更の核心は、インデックス計算の効率化と、動的配列（スライス）の境界チェックおよび基底アドレスの取得ロジックの改善です。

変更点の概要

1. 定数インデックスの最適化:
   • インデックスがリテラル整数（定数）である場合（whatis(nr) == Wlitint）、インデックス値を直接使用してオフセットを計算し、レジスタ割り当てやcgen呼び出しを省略するようになりました。これにより、生成されるアセンブリコードが簡潔になります。
   • 以前は、定数であってもcgen(nr, &n1)でレジスタにロードしてから計算していましたが、新しいコードではregfree(&n1)が削除され、n1が不要になるケースが増えました。
2. 動的配列（スライス）の処理改善:
   • isptrdarray(nl->type)（ポインタを持つ動的配列、つまりスライス）の場合の処理が大幅に変更されました。
   • 以前は、スライスの基底アドレスと要素数を取得するために、resレジスタを一時的に使用し、OINDREGオペレーションでArray構造体のnelとarrayフィールドにアクセスしていました。
   • 新しいコードでは、n3という新しいノード（types[tptr]型のポインタ）を導入し、スライスの基底アドレスを保持するようにしています。これにより、インデックス計算と基底アドレスの取得がより明確に分離され、効率的になりました。
   • 特に、定数インデックスの場合でも、スライスの基底アドレスをn3にロードする処理が追加されています。
3. 境界チェックのロジック変更:
   • debug['B']フラグが設定されていない場合（つまり、通常のビルドで境界チェックが有効な場合）の境界チェックロジックが再構築されました。
   • 以前は、isptrdarrayとそうでない場合で境界チェックのコードが重複していましたが、新しいコードではより統一された形で処理されています。
   • n1ノードがインデックス値を保持し、n3ノードが配列/スライスの基底アドレスまたはサイズ情報を保持するように役割が明確化されています。
   • 境界チェックの比較対象が、以前はtypes[TUINT32]（32ビット符号なし整数）だったものが、types[TUINT64]（64ビット符号なし整数）に変更されています。これは、64ビットシステムでのインデックスの最大値に対応するため、またはより一般的な型を使用するためと考えられます。
4. インデックス乗算の最適化:
   • インデックスiに要素の幅wを乗算する部分（i * w）において、wが1の場合（w != 1）にのみ乗算命令を生成するように変更されました。wが1の場合は乗算が不要なため、命令を省略できます。
5. レジスタ管理の改善:
   • regfreeの呼び出し位置が調整され、不要になったレジスタが適切に解放されるようになっています。特に、n1とn3のレジスタが適切に解放されるようになりました。

具体的なコード変更点と影響

• agen関数のOADDおよびOINDEXケース:
  • 以前は、nr（インデックス）がaddableでない場合、またはnl（基底アドレス）がaddableでない場合に、無条件にregallocとcgenを呼び出していましたが、whatis(nr) != Wlitintのチェックが追加され、定数インデックスの場合はこれらの処理をスキップするようになりました。
  • regalloc(&n3, types[tptr], res); cgen(nl, &n3); のように、基底アドレスをn3にロードする処理が追加され、resレジスタの役割がより明確になりました。
• indexラベル以降の処理:
  • コメントが// &a is in resから// &a is in &n3 (allocated in res)に変更され、基底アドレスがn3に格納されることが明示されました。
  • 定数インデックスの場合の処理ブロック（if(whatis(nr) == Wlitint)）が大幅に修正され、スライスの場合の基底アドレスの再取得と、n3への結果の格納が追加されました。
  • 非定数インデックスの場合の境界チェックロジックが、isptrdarrayとisptrarrayのケースをより統一的に扱うように変更されました。特に、境界値の取得方法がn1ノードに格納されるようになりました。
  • w != 1のチェックが追加され、インデックス乗算の命令生成が条件付きになりました。
  • 最終的な結果をresに移動するgmove(&n3, res);が追加され、n3とn2のレジスタが解放されるようになりました。

これらの変更により、Goコンパイラは配列やスライスのインデックスアクセスに対して、より効率的で正確なアセンブリコードを生成できるようになりました。特に、定数インデックスの最適化は、コンパイル時に計算を完了させることで、実行時のオーバーヘッドを削減する典型的なコンパイラ最適化手法です。また、スライスの内部表現（Array構造体）へのアクセス方法を改善することで、動的なインデックス処理の効率も向上させています。

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

src/cmd/6g/cgen.c ファイルの agen 関数内、特に OADD および OINDEX のケース、そして index ラベル以降の処理がコアとなる変更箇所です。

--- a/src/cmd/6g/cgen.c
+++ b/src/cmd/6g/cgen.c
@@ -351,9 +351,12 @@ agen(Node *n, Node *res)\
 		if(nr->addable)
 			goto iprad;
 		if(nl->addable) {
-			regalloc(&n1, nr->type, N);
-			cgen(nr, &n1);
-			cgen(nl, res);
+			if(whatis(nr) != Wlitint) {
+				regalloc(&n1, nr->type, N);
+				cgen(nr, &n1);
+			}
+			regalloc(&n3, types[tptr], res);
+			cgen(nl, &n3);
 			goto index;
 		}
 		cgen(nr, res);
@@ -361,9 +364,12 @@ agen(Node *n, Node *res)\
 		gmove(res, &tmp);\
 
 iprad:
-		cgen(nl, res);
-		regalloc(&n1, nr->type, N);
-		cgen(nr, &n1);
+		regalloc(&n3, types[tptr], res);
+		cgen(nl, &n3);
+		if(whatis(nr) != Wlitint) {
+			regalloc(&n1, nr->type, N);
+			cgen(nr, &n1);
+		}
 		goto index;
 
 	case OINDEX:
@@ -371,9 +377,12 @@ agen(Node *n, Node *res)\
 		if(nr->addable)
 			goto irad;
 		if(nl->addable) {
-			regalloc(&n1, nr->type, N);
-			cgen(nr, &n1);
-			agen(nl, res);
+			if(whatis(nr) != Wlitint) {
+				regalloc(&n1, nr->type, N);
+				cgen(nr, &n1);
+			}
+			regalloc(&n3, types[tptr], res);
+			agen(nl, &n3);
 			goto index;
 		}
 		cgen(nr, res);
@@ -381,66 +390,39 @@ agen(Node *n, Node *res)\
 		gmove(res, &tmp);\
 
 irad:
-		agen(nl, res);
-		regalloc(&n1, nr->type, N);
-		cgen(nr, &n1);
+		regalloc(&n3, types[tptr], res);
+		agen(nl, &n3);
+		if(whatis(nr) != Wlitint) {
+			regalloc(&n1, nr->type, N);
+			cgen(nr, &n1);
+		}
 		goto index;
 
 	index:
-		// &a is in res
-		// i is in &n1
+		// &a is in &n3 (allocated in res)
+		// i is in &n1 (if not constant)
 		// w is width
 
 		if(w == 0)
 			fatal("index is zero width");
 
-		if(isptrdarray(nl->type)) {
-			regalloc(&n2, types[tptr], res);
-			gmove(res, &n2);
-
-			if(!debug['B']) {
-				// check bounds
-				n3 = n2;
-				n3.op = OINDREG;
-				n3.type = types[tptr];
-				n3.xoffset = offsetof(Array, nel);
-				gins(optoas(OCMP, types[TUINT32]), &n1, &n3);
-
-				p1 = gbranch(optoas(OLT, types[TUINT32]), T);
-
-				gins(ACALL, N, throwindex);
-				patch(p1, pc);
-			}
-
-			// fetch array base from dope
-			n3 = n2;
-			n3.op = OINDREG;
-			n3.type = types[tptr];
-			n3.xoffset = offsetof(Array, array);
-			gins(AMOVQ, &n3, &n2);
-			gmove(&n2, res);
-			regfree(&n2);
-		} else
-			if(!debug['B']) {
-				// check bounds
-				nodconst(&n3, types[TUINT32], nl->type->bound);
-				if(isptrarray(nl->type))
-					nodconst(&n3, types[TUINT32], nl->type->type->bound);
-				gins(optoas(OCMP, types[TUINT32]), &n1, &n3);
-
-				p1 = gbranch(optoas(OLT, types[TUINT32]), T);
-				gins(ACALL, N, throwindex);
-				patch(p1, pc);
-			}
-
 		if(whatis(nr) == Wlitint) {
-			regfree(&n1);
+			if(isptrdarray(nl->type)) {
+				n1 = n3;
+				n1.op = OINDREG;
+				n1.type = types[tptr];
+				n1.xoffset = offsetof(Array, array);
+				gmove(&n1, &n3);
+			}
 			v = mpgetfix(nr->val.u.xval);
 			nodconst(&n2, types[tptr], v*w);
-			gins(optoas(OADD, types[tptr]), &n2, res);
+			gins(optoas(OADD, types[tptr]), &n2, &n3);
+			gmove(&n3, res);
+			regfree(&n3);
 			break;
 		}
 
+		// type of the index
 		t = types[TUINT64];
 		if(issigned[n1.type->etype])
 			t = types[TINT64];
@@ -449,10 +431,41 @@ agen(Node *n, Node *res)\
 		gmove(&n1, &n2);\
 		regfree(&n1);\
 
-\t\tnodconst(&n3, t, w);\t\t\t// w\
-\t\tgins(optoas(OMUL, t), &n3, &n2);\
-\t\tgins(optoas(OADD, types[tptr]), &n2, res);\
+\t\tif(!debug['B']) {
+\t\t\t// check bounds
+\t\t\tif(isptrdarray(nl->type)) {
+\t\t\t\tn1 = n3;
+\t\t\t\tn1.op = OINDREG;
+\t\t\t\tn1.type = types[tptr];
+\t\t\t\tn1.xoffset = offsetof(Array, nel);
+\t\t\t} else {
+\t\t\t\tnodconst(&n1, types[TUINT64], nl->type->bound);
+\t\t\t\tif(isptrarray(nl->type))
+\t\t\t\t\tnodconst(&n1, types[TUINT64], nl->type->type->bound);
+\t\t\t}
+\t\t\tgins(optoas(OCMP, types[TUINT64]), &n2, &n1);
+\t\t\tp1 = gbranch(optoas(OLT, types[TUINT64]), T);
+\t\t\tgins(ACALL, N, throwindex);
+\t\t\tpatch(p1, pc);
+\t\t}
+\
+\t\tif(w != 1) {
+\t\t\tnodconst(&n1, t, w);\t\t\t// w
+\t\t\tgins(optoas(OMUL, t), &n1, &n2);\
+\t\t}
+\
+\t\tif(isptrdarray(nl->type)) {
+\t\t\tn1 = n3;
+\t\t\tn1.op = OINDREG;
+\t\t\tn1.type = types[tptr];
+\t\t\tn1.xoffset = offsetof(Array, array);
+\t\t\tgmove(&n1, &n3);\
+\t\t}
+\t\tgins(optoas(OADD, types[tptr]), &n2, &n3);\
+\t\tgmove(&n3, res);\
+\
 \t\tregfree(&n2);\
+\t\tregfree(&n3);\
 \t\tbreak;\
 
 	case OIND:

コアとなるコードの解説

このコミットの主要な変更は、Goコンパイラの6g（64ビットアーキテクチャ向け）のコード生成器であるsrc/cmd/6g/cgen.cファイル内のagen関数に集中しています。agen関数は、配列やスライスのインデックスアクセスなど、メモリアドレスを計算するコードを生成する役割を担っています。

変更の目的は、インデックス計算の最適化と、動的配列（スライス）の境界チェックおよび基底アドレスの取得ロジックの改善です。

変更のポイント

1. 定数インデックスの最適化 (if(whatis(nr) != Wlitint)):

   • 以前のコードでは、インデックスnrが定数であるかどうかにかかわらず、regalloc（レジスタ割り当て）とcgen（コード生成）を呼び出してインデックス値をレジスタにロードしていました。
   • 新しいコードでは、if(whatis(nr) != Wlitint)という条件が追加されました。これは、「もしインデックスnrがリテラル整数（定数）でないならば」という意味です。
   • この条件により、インデックスが定数の場合、レジスタへのロードとコード生成のステップがスキップされます。定数インデックスの場合、コンパイル時にオフセットを直接計算できるため、実行時のレジスタ操作や命令生成が不要になり、生成されるコードがより効率的になります。

2. 基底アドレスの管理強化 (regalloc(&n3, types[tptr], res); cgen(nl, &n3);):

   • 以前のコードでは、配列/スライスの基底アドレスnlを直接resレジスタにロードしていました。
   • 新しいコードでは、n3という新しいNode（ポインタ型types[tptr]）が導入され、基底アドレスnlがまずn3にロードされるようになりました。
   • これにより、基底アドレスの計算と、その後のインデックスオフセットの加算がより明確に分離されます。n3は、インデックス計算の過程で基底アドレスを保持するための一時的な場所として機能します。最終的な結果はn3からresに移動されます。

3. 動的配列（スライス）の基底アドレス取得の改善:

   • indexラベル内のif(whatis(nr) == Wlitint)ブロック（定数インデックスの場合）に、スライス（isptrdarray(nl->type)）の基底アドレスをArray構造体から取得するロジックが追加されました。
   • n1 = n3; n1.op = OINDREG; n1.type = types[tptr]; n1.xoffset = offsetof(Array, array); gmove(&n1, &n3);
     • これは、n3が現在保持しているスライス記述子（Array構造体へのポインタ）から、実際のデータ配列へのポインタ（Array.arrayフィールド）を読み出し、それを再びn3に格納する処理です。これにより、n3はスライスの基底アドレスを正確に指すようになります。

4. 境界チェックロジックの統一と型変更:

   • if(!debug['B'])ブロック（境界チェックが有効な場合）のロジックが大幅に簡素化され、isptrdarrayとそうでない場合の重複が解消されました。
   • 境界値の取得方法が、n1ノードに格納されるようになりました。
   • 比較演算の型がtypes[TUINT32]（32ビット符号なし整数）からtypes[TUINT64]（64ビット符号なし整数）に変更されました。これは、64ビットシステムでのインデックスの最大値に対応するため、またはより一般的な型を使用するためと考えられます。
   • gins(optoas(OCMP, types[TUINT64]), &n2, &n1); は、インデックス値n2と境界値n1を比較するアセンブリ命令を生成します。
   • p1 = gbranch(optoas(OLT, types[TUINT64]), T); は、インデックスが境界値より小さい場合にジャンプする命令を生成します。
   • gins(ACALL, N, throwindex); patch(p1, pc); は、境界チェックに失敗した場合にthrowindex関数（パニックを発生させる）を呼び出すコードを生成します。

5. インデックス乗算の最適化 (if(w != 1)):

   • インデックス値n2に要素の幅wを乗算する部分（gins(optoas(OMUL, t), &n1, &n2);）に、if(w != 1)という条件が追加されました。
   • 要素の幅wが1の場合（例: byte配列）、乗算は不要です。この条件により、不要な乗算命令の生成がスキップされ、コードがさらに効率化されます。

6. レジスタ解放の調整:

   • regfree(&n2); と regfree(&n3); が追加され、使用済みの一時レジスタが適切に解放されるようになりました。これは、レジスタの効率的な再利用と、コンパイラ内部のリソース管理にとって重要です。

これらの変更は、Goコンパイラが配列やスライスのインデックスアクセスに対して、より最適化された、かつ正確なアセンブリコードを生成することを可能にしました。特に、定数インデックスのコンパイル時最適化と、動的配列のランタイム処理の改善は、Goプログラムの全体的なパフォーマンス向上に貢献しています。

関連リンク

• Go言語の公式ウェブサイト: https://go.dev/
• Go言語のソースコードリポジトリ（GitHub）: https://github.com/golang/go
• Goコンパイラの設計に関する初期のドキュメント（もし公開されていれば）

参考にした情報源リンク

• Go言語のコンパイラに関する一般的な情報（Goのコンパイラがどのように動作するか、gツールチェーンなど）
• Goの配列とスライスの内部表現に関するドキュメントや記事
• コンパイラの最適化、特に定数伝播や境界チェック除去に関する一般的な情報
• offsetofマクロのC言語における使用法と、それが構造体フィールドのオフセットをどのように計算するかに関する情報
• Ken ThompsonのGo言語への貢献に関する情報（初期のGo開発者の一人）
• Goの初期のコミット履歴を辿るためのGitコマンドやGitHubの機能