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

このコミットは、Go言語の初期のコンパイラである6g（64-bit x86アーキテクチャ向けコンパイラ）におけるコード生成ロジックの重要な改善を目的としています。特に、レジスタ割り当ての効率化と、特定の演算（除算、シフト）におけるコード生成の複雑さを軽減することに焦点を当てています。

コミット

commit 719b088697a3da28090a561280726631ceb373a7
Author: Ken Thompson <ken@golang.org>
Date:   Sat Dec 13 16:41:47 2008 -0800

    code generation
    
    R=r
    OCL=21146
    CL=21146
---
 src/cmd/6g/cgen.c  | 64 ++++++++++++++++++++++++++++++++-----------
 src/cmd/6g/gen.c   | 79 ++----------------------------------------------------\
 src/cmd/6g/gg.h    |  2 +-\n src/cmd/6g/gsubr.c | 39 ++++++++++++++++-----------\n 4 files changed, 75 insertions(+), 109 deletions(-)

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

https://github.com/golang/go/commit/719b088697a3da28090a561280726631ceb373a7

元コミット内容

このコミットは、Goコンパイラのコード生成部分、特にcgen.c、gen.c、gg.h、gsubr.cの4つのファイルにわたる変更を含んでいます。主な目的は、レジスタ割り当ての最適化と、除算やシフトといった特定の命令における特殊なレジスタ使用規則への対応を改善することです。

変更の概要は以下の通りです。

• src/cmd/6g/cgen.c: コード生成のメインロジックを担うcgen関数において、sudoaddable関数の呼び出し方法が変更され、レジスタ割り当てと解放のロジックが洗練されました。特に、リテラルやレジスタ値の扱いが改善されています。
• src/cmd/6g/gen.c: 除算（cgen_div）とシフト（cgen_shift）のコード生成関数から、複雑なレジスタ退避・復元ロジックが大幅に削除されました。これは、sudoaddableの改善や、レジスタ管理のより一般的なメカニズムによって、これらの特殊なケースがより効率的に扱えるようになったことを示唆しています。
• src/cmd/6g/gg.h: sudoaddable関数のシグネチャが変更され、追加のNode*引数を受け取るようになりました。
• src/cmd/6g/gsubr.c: ginitおよびgclean関数において、特定のレジスタ（AX, CX, DI, DX, SI）がデフォルトで「使用中」としてマークされるようになりました。また、sudoaddable関数の実装が、新しいシグネチャに合わせて更新され、渡されたレジスタノードを一時レジスタとして利用するようになりました。

変更の背景

Go言語の初期のコンパイラ（6gなど）は、アセンブリコードを直接生成するバックエンドを持っていました。x86アーキテクチャでは、特定の命令（例えば、DIV命令はAX/DXレジスタを暗黙的に使用し、シフト命令はシフトカウントにCLレジスタを使用するなど）が特定のレジスタを必要とするという制約があります。

従来のコード生成ロジックでは、これらの特殊なレジスタが既に他の目的で使用されている場合に、その値を一時的に退避し、命令実行後に復元するという複雑な処理が各所で必要でした。これはコードの重複や、レジスタ割り当ての非効率性を招く可能性がありました。

このコミットの背景には、以下の課題があったと考えられます。

1. レジスタ管理の複雑性: 除算やシフトなどの特殊な命令が要求するレジスタ（AX, DX, CXなど）と、コンパイラが自由に使える汎用レジスタとの間で、競合が発生しやすく、その解決が煩雑であった。
2. コードの冗長性: 特殊レジスタの退避・復元ロジックが、cgen_divやcgen_shiftのような個別のコード生成関数内に散在しており、保守性や最適化の妨げとなっていた。
3. 最適化の機会: 特定のオペランドが直接メモリアドレスとして扱える場合（sudoaddableの役割）に、不必要なレジスタへのロード・ストアを避けることで、生成されるアセンブリコードの効率を向上させる余地があった。

このコミットは、これらの課題に対処し、コード生成バックエンドのレジスタ管理をより体系的かつ効率的に行うことを目指しています。

前提知識の解説

このコミットを理解するためには、以下の概念が役立ちます。

1. コンパイラのコード生成:

   • コンパイラのバックエンドは、中間表現（IR）からターゲットマシン（この場合はx86-64）のアセンブリコードを生成する部分です。
   • レジスタ割り当て: CPUのレジスタは高速なデータアクセスを提供しますが、数が限られています。コンパイラは、どの変数をどのレジスタに割り当てるかを決定し、レジスタが不足した場合はメモリに退避（スピル）させます。
   • 命令選択: 中間表現の操作を、ターゲットアーキテクチャの具体的なアセンブリ命令に変換します。

2. x86-64アーキテクチャのレジスタ:

   • x86-64には汎用レジスタ（RAX, RBX, RCX, RDX, RSI, RDI, RBP, RSP, R8-R15）があります。
   • 特殊な役割を持つレジスタ:
     • RAX (Accumulator Register): 算術演算の結果を格納するためによく使われます。特に、DIV命令では除算の商がRAXに、剰余がRDXに格納されます。
     • RDX (Data Register): RAXと共に、乗算や除算のオペランド・結果を格納します。DIV命令では、被除数の上位ビットを格納します。
     • RCX (Count Register): シフト命令（SHL, SHRなど）では、シフトするビット数がCL（RCXの下位8ビット）レジスタに格納されている必要があります。
     • RSI (Source Index) / RDI (Destination Index): 文字列操作命令（MOVSB, MOVSDなど）で、ソース/デスティネーションのアドレスを指すために使われます。
   • これらの特殊なレジスタの制約が、コンパイラのコード生成を複雑にする要因となります。

3. Ullman Number (ウルマン数):

   • 式木の各ノードに割り当てられる数値で、そのノードを評価するために必要なレジスタの最小数を示します。
   • UINF (Ullman Infinity) は、そのノードが非常に複雑であるか、レジスタにロードできない（例えば、メモリ上の特定のアドレスを指す）ことを示すために使われることがあります。res->ullman >= UINFという条件は、結果をレジスタに直接格納できない、あるいはレジスタに格納するメリットが少ない場合に、別のコード生成パスを選択するためのヒューリスティックとして機能します。

4. sudoaddable関数:

   • このコミットで変更される重要な関数です。名前から推測すると、「疑似的にアドレス指定可能（pseudo-addressable）」という意味合いで、あるノード（オペランド）が、レジスタにロードすることなく、直接メモリアドレスとしてアセンブリ命令のオペランドに指定できるかどうかを判断する役割を持つと考えられます。例えば、構造体のフィールドや配列の要素など、ベースアドレスとオフセットで表現できるようなケースです。
   • この関数がtrueを返す場合、コンパイラは不必要なMOV命令（レジスタへのロード）を省略し、より効率的なコードを生成できます。

技術的詳細

このコミットの技術的な核心は、レジスタ管理の責任を分散させ、より一般的なメカニズムで特殊なレジスタの制約を扱うように変更した点にあります。

sudoaddable関数の強化

最も重要な変更点の一つは、sudoaddable関数のシグネチャ変更です。 int sudoaddable(Node *n, Type *t, Addr *a) から int sudoaddable(Node *n, Type *t, Addr *a, Node *reg) へと変更されました。

新しいNode *reg引数は、sudoaddable関数が内部で一時レジスタを必要とする場合に、そのレジスタを呼び出し元から提供されるregノードに割り当てることを可能にします。これにより、sudoaddableが独自のレジスタを割り当てて解放するのではなく、cgenのような上位のコード生成関数がレジスタ管理のコンテキストを提供できるようになります。

gsubr.cのsudoaddableの実装では、以前は内部でregalloc(&n1, ...)のように新しいNodeを宣言してレジスタを割り当てていましたが、変更後は引数として渡されたregノードを利用するようになりました。

--- a/src/cmd/6g/gsubr.c
+++ b/src/cmd/6g/gsubr.c
@@ -1831,28 +1841,27 @@ sudoaddable(Node *n, int *oary, Node **nn)
 		}
 
-		regalloc(&n1, types[tptr], N);
-		n2 = n1;
-		n2.op = OINDREG;
+		regalloc(reg, types[tptr], N);
+		n1 = *reg;
+		n1.op = OINDREG;
 		if(oary[0] >= 0) {
-			agen(nn, &n1);
-			n2.xoffset = oary[0];
+			agen(nn, reg);
+			n1.xoffset = oary[0];
 		} else {
-			cgen(nn, &n1);
-			n2.xoffset = -(oary[0]+1);
+			cgen(nn, reg);
+			n1.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);
+			gins(AMOVQ, &n1, reg);
+			n1.xoffset = -(oary[i]+1);
 		}
 
 		a->type = D_NONE;
 		a->index = D_NONE;
-		naddr(&n2, a);
-		regfree(&n1);
+		naddr(&n1, a);
 		break;
 	}
 	return 1;

この変更により、cgen関数はsudoaddableを呼び出す際に、一時レジスタを明示的に提供できるようになり、レジスタのライフサイクル管理がより一貫性を持つようになりました。

cgen.cにおけるレジスタ管理の改善

cgen関数では、sudoaddableの新しいシグネチャに合わせて呼び出しが変更されました。特に、res->ullman >= UINFのチェックが追加され、リテラルやレジスタ値の最適化パスが導入されました。

--- a/src/cmd/6g/cgen.c
+++ b/src/cmd/6g/cgen.c
@@ -48,6 +48,36 @@ cgen(Node *n, Node *res)
 		goto ret;
 	}
 
+	if(res->ullman >= UINF)
+		goto gen;
+
+	f = 1;	// gen thru register
+	switch(n->op) {
+	case OLITERAL:
+		if(isint[n->type->etype])
+		if(n->type->width <= 4)
+			f = 0;
+		break;
+	case OREGISTER:
+		f = 0;
+		break;
+	}
+
+	if(sudoaddable(res, n->type, &addr, &n1)) {
+		a = optoas(OAS, res->type);
+		if(f) {
+			regalloc(&n2, res->type, N);
+			cgen(n, &n2);
+			p1 = gins(a, &n2, N);
+			regfree(&n2);
+		} else
+			p1 = gins(a, n, N);
+		p1->to = addr;
+		regfree(&n1);
+		goto ret;
+	}
+
+gen:
 	igen(res, &n1, N);
 	cgen(n, &n1);
 	regfree(&n1);
@@ -71,19 +101,20 @@ cgen(Node *n, Node *res)
 		goto ret;
 	}
 
-	if(sudoaddable(n, res->type, &addr)) {
+	if(sudoaddable(n, res->type, &addr, &n1)) {
 		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);
+			regalloc(&n2, n->type, &n1);
+			p1 = gins(a, N, &n2);
 			p1->from = addr;
-			gins(a, &n1, res);
-			regfree(&n1);
+			gins(a, &n2, res);
+			regfree(&n2);
 		}
-		return;
+		regfree(&n1);
+		goto ret;
 	}

この変更は、sudoaddableがtrueを返す場合に、結果を直接アドレスに格納するパスを導入しています。fフラグは、リテラルや既存のレジスタ値の場合に、不必要なレジスタ割り当てを避けるための最適化を示唆しています。

gen.cにおける特殊レジスタ管理の簡素化

gen.cのcgen_div（除算）とcgen_shift（シフト）関数から、レジスタAX, DX, CXの明示的な退避・復元ロジックが削除されました。

--- a/src/cmd/6g/gen.c
+++ b/src/cmd/6g/gen.c
@@ -1184,64 +1179,12 @@ cgen_div(int op, Node *nl, Node *nr, Node *res)
 	regalloc(&ax, nl->type, &ax);
 	regalloc(&dx, nl->type, &dx);
 
-	// clean out the AX register
-	if(rax && !samereg(res, &ax)) {
-		if(rdx && !samereg(res, &dx)) {
-			regalloc(&tmpdx, types[TINT64], N);
-			regalloc(&tmpax, types[TINT64], N);
-			regalloc(&n3, nl->type, N);		// dest for div
-
-			gins(AMOVQ, &dx, &tmpdx);
-			gins(AMOVQ, &ax, &tmpax);
-			dodiv(op, nl, nr, &n3, &ax, &dx);
-			gins(AMOVQ, &tmpax, &ax);
-			gins(AMOVQ, &tmpdx, &dx);
-			gmove(&n3, res);
-
-			regfree(&tmpdx);
-			regfree(&tmpax);
-			regfree(&n3);
-			goto ret;
-		}
-		regalloc(&tmpax, types[TINT64], N);
-		regalloc(&n3, nl->type, N);		// dest for div
-
-		gins(AMOVQ, &ax, &tmpax);
-		dodiv(op, nl, nr, &n3, &ax, &dx);
-		gins(AMOVQ, &tmpax, &ax);
-		gmove(&n3, res);
-
-		regfree(&tmpax);
-		regfree(&n3);
-		goto ret;
-	}
-
-	// clean out the DX register
-	if(rdx && !samereg(res, &dx)) {
-		regalloc(&tmpdx, types[TINT64], N);
-		regalloc(&n3, nl->type, N);		// dest for div
-
-		gins(AMOVQ, &dx, &tmpdx);
-		dodiv(op, nl, nr, &n3, &ax, &dx);
-		gins(AMOVQ, &tmpdx, &dx);
-		gmove(&n3, res);
-
-		regfree(&tmpdx);
-		regfree(&n3);
-		goto ret;
-	}
 	dodiv(op, nl, nr, res, &ax, &dx);
 
-ret:
 	regfree(&ax);
 	regfree(&dx);
 }
 
-/*
- * this is hard because shift
- * count is either constant
- * or the CL register
- */
 void
 cgen_shift(int op, Node *nl, Node *nr, Node *res)
 {
@@ -1271,25 +1214,7 @@ cgen_shift(int op, Node *nl, Node *nr, Node *res)
 	nodreg(&n1, types[TINT64], D_CX);
 	regalloc(&n1, nr->type, &n1);
 
-	// clean out the CL register
-	if(rcl) {
-		regalloc(&n2, types[TINT64], N);
-		gins(AMOVQ, &n1, &n2);
-		regfree(&n1);
-
-		reg[D_CX] = 0;
-		if(samereg(res, &n1))
-			cgen_shift(op, nl, nr, &n2);
-		else
-			cgen_shift(op, nl, nr, res);
-		reg[D_CX] = rcl;
-
-		gins(AMOVQ, &n2, &n1);
-		regfree(&n2);
-		goto ret;
-	}
-
-	regalloc(&n2, nl->type, res);	// can one shift the CL register
+	regalloc(&n2, nl->type, res);
 	if(nl->ullman >= nr->ullman) {
 		cgen(nl, &n2);
 		cgen(nr, &n1);

この大幅な削除は、gsubr.cのginit/gcleanにおけるレジスタのデフォルト割り当てと、sudoaddableの改善によって、これらの特殊レジスタの管理がより上位のレイヤーや一般的なメカニズムで処理されるようになったことを強く示唆しています。つまり、個々の演算ハンドラがレジスタの競合解決に責任を持つ必要がなくなり、コードが簡素化されたと考えられます。

gsubr.cにおけるレジスタのデフォルト割り当て

ginit（コンパイラ初期化時）とgclean（コンパイラ終了時）において、特定のレジスタがデフォルトで「使用中」としてマークされるようになりました。

--- a/src/cmd/6g/gsubr.c
+++ b/src/cmd/6g/gsubr.c
@@ -113,7 +113,12 @@ ginit(void)
 		reg[i] = 0;
 	for(i=D_X0; i<=D_X7; i++)
 		reg[i] = 0;
-	reg[D_SP]++;
+	reg[D_AX]++;	// for divide
+	reg[D_CX]++;	// for shift
+	reg[D_DI]++;	// for movstring
+	reg[D_DX]++;	// for divide
+	reg[D_SI]++;	// for movstring
+	reg[D_SP]++;	// for stack
 }
 
 void
@@ -121,7 +126,12 @@ gclean(void)
 {
 	int i;
 
-	reg[D_SP]--;
+	reg[D_AX]--;	// for divide
+	reg[D_CX]--;	// for shift
+	reg[D_DI]--;	// for movstring
+	reg[D_DX]--;	// for divide
+	reg[D_SI]--;	// for movstring
+	reg[D_SP]--;	// for stack
 	for(i=D_AX; i<=D_R15; i++)
 		if(reg[i])
 			yyerror("reg %R left allocated\n", i);

これは、AX, DX（除算用）、CX（シフト用）、DI, SI（文字列操作用）といった特殊なレジスタが、コンパイラの実行中、常に特定の目的のために予約されているか、あるいはその使用がコンパイラ全体で考慮されるようになったことを意味します。これにより、個々のコード生成関数がこれらのレジスタの競合を心配する必要がなくなります。

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

このコミットのコアとなる変更は、src/cmd/6g/cgen.cにおけるcgen関数のレジスタ管理ロジックの修正と、src/cmd/6g/gen.cにおけるcgen_divおよびcgen_shift関数の簡素化、そしてsrc/cmd/6g/gsubr.cにおけるsudoaddable関数のシグネチャ変更とginit/gcleanでのレジスタ初期化の変更です。

特に、cgen.cの以下の部分が変更の核心を示しています。

// src/cmd/6g/cgen.c
@@ -48,6 +48,36 @@ cgen(Node *n, Node *res)
 		goto ret;
 	}
 
+	if(res->ullman >= UINF)
+		goto gen;
+
+	f = 1;	// gen thru register
+	switch(n->op) {
+	case OLITERAL:
+		if(isint[n->type->etype])
+		if(n->type->width <= 4)
+			f = 0;
+		break;
+	case OREGISTER:
+		f = 0;
+		break;
+	}
+
+	if(sudoaddable(res, n->type, &addr, &n1)) {
+		a = optoas(OAS, res->type);
+		if(f) {
+			regalloc(&n2, res->type, N);
+			cgen(n, &n2);
+			p1 = gins(a, &n2, N);
+			regfree(&n2);
+		} else
+			p1 = gins(a, n, N);
+		p1->to = addr;
+		regfree(&n1);
+		goto ret;
+	}
+
+gen:
 	igen(res, &n1, N);
 	cgen(n, &n1);
 	regfree(&n1);

コアとなるコードの解説

上記のcgen.cのコードスニペットは、Goコンパイラのコード生成におけるレジスタ割り当てと最適化の新しいアプローチを示しています。

1. if(res->ullman >= UINF):

   • resはコード生成の結果を格納するノードです。ullmanはウルマン数で、そのノードを評価するために必要なレジスタの最小数を示します。
   • UINF（Ullman Infinity）は、そのノードが非常に複雑であるか、レジスタに直接格納できない（例えば、メモリ上の特定のアドレスを指す）ことを示す特別な値です。
   • この条件は、「もし結果を格納する場所がレジスタに直接割り当てられない、あるいはレジスタに格納するメリットが少ない場合」という最適化の分岐点を示しています。この場合、通常のコード生成パス（goto gen;）に進みます。

2. f = 1; // gen thru register:

   • fはフラグ変数で、デフォルトで1に設定されています。これは、通常はレジスタを介してコードを生成することを示唆しています。

3. switch(n->op)ブロック:

   • nは現在処理しているノード（オペランド）です。
   • case OLITERAL:: もしオペランドがリテラル（定数）であれば、かつそれが4バイト以下の整数型であれば、fを0に設定します。これは、小さな定数はレジスタにロードするよりも、直接命令の即値オペランドとして使用する方が効率的であるため、レジスタを介した生成を避けることを意味します。
   • case OREGISTER:: もしオペランドが既にレジスタに格納されている値であれば、fを0に設定します。これも同様に、既にレジスタにあるものを再度レジスタにロードする（あるいは一時レジスタを介する）必要がないためです。

4. if(sudoaddable(res, n->type, &addr, &n1)):

   • ここがこのコミットの重要な変更点です。sudoaddable関数が呼び出され、res（結果の格納先）、n->type（オペランドの型）、&addr（結果のアドレス情報）、そして新しい引数である&n1（一時レジスタとして使用するノード）が渡されます。
   • sudoaddableがtrueを返した場合、つまりresが直接アドレス指定可能であると判断された場合、以下の最適化パスに進みます。

5. 最適化されたコード生成パス:

   • a = optoas(OAS, res->type);: 代入命令（OAS）のアセンブリ命令コードを取得します。
   • if(f)ブロック:
     • fが1の場合（つまり、リテラルや既存レジスタ値ではない場合）、n2という新しい一時レジスタを割り当てます。
     • cgen(n, &n2);: 現在のオペランドnをこの一時レジスタn2にコード生成します。
     • p1 = gins(a, &n2, N);: n2の内容をaddrに代入するアセンブリ命令を生成します。
     • regfree(&n2);: 一時レジスタn2を解放します。
   • elseブロック:
     • fが0の場合（リテラルや既存レジスタ値の場合）、nの内容を直接addrに代入するアセンブリ命令を生成します。この場合、一時レジスタn2は不要です。
   • p1->to = addr;: 生成された命令の宛先をaddrに設定します。
   • regfree(&n1);: sudoaddableに渡された一時レジスタn1を解放します。
   • goto ret;: コード生成が完了したため、関数を終了します。

この新しいロジックは、sudoaddableの判断に基づいて、結果をレジスタにロードしてからメモリにストアするのではなく、直接メモリにストアするパスを提供します。これにより、不必要なレジスタ操作を削減し、より効率的なアセンブリコードを生成することが可能になります。また、fフラグによるリテラルや既存レジスタ値の特殊な扱いも、さらなる最適化に貢献しています。

関連リンク

• Go言語の初期のコンパイラに関する情報:
  • The Go Programming Language Specification (Go 1.0) - Go言語の初期の設計思想や仕様について理解するのに役立ちます。
  • Go's Toolchain - Goのビルドツールチェーンの概要。6gのような初期のコンパイラについても言及があるかもしれません。
• コンパイラのコード生成と最適化に関する一般的な情報:
  • Compilers: Principles, Techniques, and Tools (Dragon Book) - コンパイラ理論の古典的な教科書。レジスタ割り当てやコード生成のアルゴリズムについて詳細に解説されています。
  • x86 Assembly Language Programming - x86アセンブリの命令セットとレジスタの使用法について理解を深めるのに役立ちます。

参考にした情報源リンク

• Go言語の公式ドキュメントとソースコードリポジトリ:
  • golang/go GitHub Repository - このコミットが属する公式リポジトリ。
• コンパイラ設計に関する一般的な知識。
• x86-64アーキテクチャのレジスタと命令セットに関する知識。