Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

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

このコミットは、Goコンパイラ（6g）におけるラベル付きbreakおよびcontinue文の挙動に関するバグ（内部的に「bug 137」と識別されていたもの）を修正します。具体的には、コード生成フェーズにおいて、ループやスイッチ文に付随するラベルのbreakおよびcontinueターゲットの解決ロジックが改善されています。これにより、ネストされたループ内でラベル付きbreakやcontinueが正しく機能するようになります。

コミット

commit 48f6b516e24d55e14d866a7e7140fb3b1d1ae218
Author: Ken Thompson <ken@golang.org>
Date:   Wed Mar 11 16:25:45 2009 -0700

    bug 137
    
    R=r
    OCL=26142
    CL=26142
---
 src/cmd/6g/gen.c                   | 150 +++++++++++++++++++------------------
 src/cmd/6g/gg.h                    |   4 +-\
 test/{bugs => fixedbugs}/bug137.go |   0
 test/golden.out                    |   5 --
 4 files changed, 81 insertions(+), 78 deletions(-)

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

https://github.com/golang/go/commit/48f6b516e24d55e14d866a7e7140fb3b1d1ae218

元コミット内容

bug 137

R=r
OCL=26142
CL=26142

変更の背景

このコミットは、Goコンパイラ（6g）がラベル付きbreakおよびcontinue文を正しく処理できないという既知のバグ（内部的な「bug 137」）に対応するために行われました。Go言語では、forループやswitch文、select文にラベルを付与し、そのラベルを指定してbreakやcontinueを行うことができます。これにより、ネストされたループの特定の外側のループから抜け出したり、特定のループの次のイテレーションに進んだりすることが可能になります。

しかし、この機能の実装には問題があり、コンパイラがラベル付きbreakやcontinueのジャンプ先を誤って解決してしまうことがありました。特に、gen関数がループのコンテキストをLabel* labloopという引数で受け取っていましたが、この方法では複雑なネスト構造や複数のラベルが存在する場合に、正しいジャンプ先を特定できないケースが発生していました。その結果、「break label is not defined」のようなコンパイルエラーが発生したり、意図しない挙動を引き起こしたりしていました。

このコミットは、ラベルの管理と解決のメカニズムを根本的に見直し、より堅牢な方法でラベル付き制御フローをサポートすることを目的としています。

前提知識の解説

このコミットの変更内容を理解するためには、以下のGoコンパイラの基本的な概念と、Go言語の制御フローに関する知識が必要です。

  1. Goコンパイラ (6g) の構造:

    • 6gは、Go言語のソースコードをアセンブリコードに変換するコンパイラの一つです（6はamd64アーキテクチャを指します）。
    • コンパイルプロセスには、字句解析、構文解析、意味解析、中間コード生成、最適化、コード生成などのフェーズがあります。
    • このコミットが関連するのは主にコード生成フェーズです。

  2. src/cmd/6g/gen.c:

    • Goコンパイラのコード生成を担当するC言語のソースファイルです。
    • 抽象構文木（AST）をトラバースし、対応するアセンブリ命令（Prog構造体で表現される）を生成します。
    • gen関数は、ASTのノードを受け取り、そのノードに対応するコードを生成する主要な関数です。

  3. src/cmd/6g/gg.h:

    • 6gコンパイラで使用される共通の定義や構造体が含まれるヘッダファイルです。
    • Node、Sym、Progなどの重要な構造体が定義されています。
    • 特に、Label構造体は、goto、break、continueなどの制御フロー文のジャンプ先を管理するために使用されます。

  4. Label構造体:

    • Label構造体は、Goコンパイラがコード生成時にラベル情報を管理するために使用されます。
    • sym: ラベル名に対応するシンボル。
    • op: ラベルの種類（例: OLABEL、OGOTO）。
    • label: ラベルが指すコードのプログラムカウンタ（Progへのポインタ）。
    • breakpc: このラベルに関連付けられたbreak文がジャンプするべきプログラムカウンタ。
    • continpc: このラベルに関連付けられたcontinue文がジャンプするべきプログラムカウンタ。
    • labellist: 現在アクティブなラベルのリンクリスト。

  5. breakとcontinue文:

    • Go言語では、breakはループやswitch、select文を終了させます。continueはループの次のイテレーションに進みます。
    • ラベル付きbreak/continue: break LabelNameやcontinue LabelNameのように、特定のラベルが付与されたループやswitch/select文を対象に制御を移すことができます。これは、ネストされた制御構造から特定の外側の構造を操作する際に特に有用です。

  6. プログラムカウンタ (pc) とパッチ (patch):

    • pcは、現在生成中のアセンブリ命令の場所を示すポインタです。
    • gbranch(AJMP, T)のような関数は、条件なしジャンプ命令（AJMP）を生成し、そのジャンプ先のポインタを返します。
    • patch(p, target_pc)は、以前に生成されたジャンプ命令pのジャンプ先をtarget_pcに修正（パッチ）するために使用されます。これは、ジャンプ先がコード生成時にまだ不明な場合に、後で解決するために使われる一般的な手法です。

このコミットは、これらの要素がどのように連携してラベル付き制御フローを実装し、その中で発生していたバグをどのように修正したかを示しています。

技術的詳細

このコミットの技術的な核心は、Goコンパイラがラベル付きbreakおよびcontinue文のジャンプ先を解決する方法の変更にあります。

  1. gen関数のシグネチャ変更:

    • 変更前: void gen(Node *n, Label *labloop)
    • 変更後: void gen(Node *n)
    • labloop引数が削除されました。これは、以前はgen関数が現在のループのラベル情報を引数として受け取っていましたが、この方法では複雑なラベル解決に対応しきれなかったことを示唆しています。代わりに、ラベル情報はグローバルなlabellistリンクリストを通じて管理されるようになりました。これにより、gen関数はより汎用的なコード生成ロジックに集中できるようになります。

  2. newlab関数の導入:

    • 新しいヘルパー関数newlab(int op, Sym *s)が導入されました。
    • この関数は、新しいLabel構造体を動的に割り当て、labellistの先頭にリンクし、sym、op、および現在のプログラムカウンタpcをlabelフィールドに設定します。
    • これにより、ラベルの作成とlabellistへの追加が中央集権化され、コードの重複が減り、一貫性が向上します。

  3. OLISTノードの処理の簡素化:

    • OLISTは、複数の文を順次実行するリストを表すASTノードです。
    • 変更前は、OLIST内でラベルが検出された場合に、gen関数を再帰的に呼び出す際にlabellistを渡すなど、複雑なロジックがありました。
    • 変更後、この複雑なロジックは削除され、gen(n->left)とn = n->right; goto loop;というシンプルな再帰呼び出しとループ処理に置き換えられました。これは、ラベルの解決がgen関数の引数ではなく、labellistの動的な走査によって行われるようになったため、OLISTの処理が簡素化されたことを意味します。

  4. OLABELとOGOTOの処理の改善:

    • OLABEL（ラベル定義）とOGOTO（goto文）のケースでは、newlab関数を使用してLabel構造体が作成されるようになりました。これにより、ラベルの登録がよりクリーンに行われます。

  5. OBREAKとOCONTINUEの解決ロジックの変更:

    • 変更前: findlab(n->left->sym)を使用してラベルを検索し、そのラベルのbreakpcまたはcontinpcが有効かどうかを確認していました。findlabがどのように機能していたかは不明ですが、このアプローチでは問題があったようです。
    • 変更後: labellistを先頭から（つまり、最も新しく定義されたラベルから）走査し、有効なbreakpcまたはcontinpcを持つ最初のLabelを見つけます。そして、そのbreakpcまたはcontinpcに対してジャンプ命令をパッチします。
    • この変更は非常に重要です。ラベル付きbreak/continueの場合、n->leftはラベルのシンボルを指します。このシンボルに対応するLabelをlabellistから探し、そのbreakpc/continpcをパッチします。ラベルなしの場合（n->left == N）、グローバルなbreakpc/continpcが使用されます。この動的な走査により、ネストされた構造における正しいジャンプ先が確実に解決されるようになります。

  6. ループ/スイッチ/セレクト文におけるラベルの関連付け:

    • OFOR（forループ）、OSWITCH（switch文）、OSELECT（select文）のコード生成ロジックが変更されました。
    • これらの構造の開始時に、現在のプログラムカウンタpcがp3として保存されます。
    • その後、labellistを走査し、p3と一致するlabelフィールドを持つOLABEL（つまり、このループ/スイッチ/セレクトの直前に定義されたラベル）を探します。
    • 見つかった場合、そのLabelのbreakpcとcontinpc（OFORの場合）を、現在生成中のループ/スイッチ/セレクトのbreakおよびcontinueターゲットに設定します。
    • このメカニズムにより、ラベルがその直後の制御フロー構造に正しく「関連付け」られるようになります。これにより、ラベル付きbreakやcontinueが、意図した特定のループやスイッチ文を対象にできるようになります。

  7. テストケースの移動:

    • test/bugs/bug137.goがtest/fixedbugs/bug137.goにリネームされました。これは、このコミットによってバグが修正され、テストが「修正済みバグ」のカテゴリに移動したことを示しています。
    • test/golden.outからもbug137.goに関するエラーメッセージが削除されています。

これらの変更により、Goコンパイラはラベル付きbreakおよびcontinue文をより正確に処理できるようになり、コンパイル時のエラーや実行時の誤った挙動が解消されました。

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

このコミットの主要な変更は、src/cmd/6g/gen.cファイルに集中しています。

  1. gen関数のシグネチャ変更:

    --- a/src/cmd/6g/gen.c
+++ b/src/cmd/6g/gen.c
@@ -82,8 +82,8 @@ compile(Node *fn)
 //	inarggen();
 
 	ginit();
-	gen(curfn->enter, L);
-	gen(curfn->nbody, L);
+	gen(curfn->enter);
+	gen(curfn->nbody);
 	gclean();
 	checklabels();

    gen関数の呼び出し箇所からL（null Label）引数が削除されています。

  2. newlab関数の追加:

    --- a/src/cmd/6g/gen.c
+++ b/src/cmd/6g/gen.c
@@ -143,16 +143,29 @@ allocparams(void)
 	}
 }
 
+void
+newlab(int op, Sym *s)
+{
+	Label *lab;
+
+	lab = mal(sizeof(*lab));
+	lab->link = labellist;
+	labellist = lab;
+
+	lab->sym = s;
+	lab->op = op;
+	lab->label = pc;
+}
+
 /*
  * compile statements
  */
 void
-gen(Node *n, Label *labloop)
+gen(Node *n)
 {
 	int32 lno;
 	Prog *scontin, *sbreak;
 	Prog *p1, p2, p3;
-	Node *l;
 	Label *lab;

    newlab関数が新しく定義され、gen関数のシグネチャも変更されています。

  3. OLIST、OLABEL、OGOTOの処理変更:

    --- a/src/cmd/6g/gen.c
+++ b/src/cmd/6g/gen.c
@@ -160,8 +173,10 @@ gen(Node *n, Label *labloop)
 loop:
 	if(n == N)
 		goto ret;
+
+	p3 = pc;	// save pc for loop labels
 	if(n->ninit)
-		gen(n->ninit, L);
+		gen(n->ninit);
 
 	setlineno(n);
 
@@ -171,24 +186,8 @@ loop:
 		break;
 
 	case OLIST:
-		l = n->left;
-		gen(l, L);
-		if(l != N && l->op == OLABEL) {
-			// call the next statement with a label
-			l = n->right;
-			if(l != N) {
-				if(l->op != OLIST) {
-					gen(l, labellist);
-					break;
-				}
-				gen(l->left, labellist);
-				n = l->right;
-				labloop = L;
-				goto loop;
-			}
-		}
+		gen(n->left);
 		n = n->right;
-		labloop = L;
 		goto loop;
 
 	case OPANIC:
@@ -203,37 +202,26 @@ loop:
 		break;
 
 	case OLABEL:
-		lab = mal(sizeof(*lab));
-		lab->link = labellist;
-		labellist = lab;
-		lab->sym = n->left->sym;
-
-		lab->op = OLABEL;
-		lab->label = pc;
+		newlab(OLABEL, n->left->sym);
 		break;
 
 	case OGOTO:
-		lab = mal(sizeof(*lab));
-		lab->link = labellist;
-		labellist = lab;
-		lab->sym = n->left->sym;
-
-		lab->op = OGOTO;
-		lab->label = pc;
+		newlab(OGOTO, n->left->sym);
 		gbranch(AJMP, T);
 		break;

    OLISTの処理が簡素化され、OLABELとOGOTOでnewlabが使われるようになりました。

  4. OBREAKとOCONTINUEの解決ロジック変更:

    --- a/src/cmd/6g/gen.c
+++ b/src/cmd/6g/gen.c
@@ -215,20 +203,20 @@ loop:
 
 	case OBREAK:
 		if(n->left != N) {
-			lab = findlab(n->left->sym);
-			if(lab == L || lab->breakpc == P) {
-				yyerror("break label is not defined: %S", n->left->sym);
-				break;
+			for(lab=labellist; lab!=L; lab=lab->link) {
+				if(lab->breakpc != P) {
+					patch(gbranch(AJMP, T), lab->breakpc);
+					break;
+				}
 			}
-			patch(gbranch(AJMP, T), lab->breakpc);
+			if(lab == L)
+				yyerror("break label not defined: %S", n->left->sym);
 			break;
 		}
-
 		if(breakpc == P) {
 			yyerror("break is not in a loop");
 			break;
@@ -243,12 +231,14 @@ loop:
 
 	case OCONTINUE:
 		if(n->left != N) {
-			lab = findlab(n->left->sym);
-			if(lab == L || lab->continpc == P) {
-				yyerror("continue label is not defined: %S", n->left->sym);
-				break;
+			for(lab=labellist; lab!=L; lab=lab->link) {
+				if(lab->continpc != P) {
+					patch(gbranch(AJMP, T), lab->continpc);
+					break;
+				}
 			}
-			patch(gbranch(AJMP, T), lab->continpc);
+			if(lab == L)
+				yyerror("break label not defined: %S", n->left->sym);
 			break;
 		}

    findlabの使用が削除され、labellistを走査してbreakpc/continpcを解決するロジックに変更されています。

  5. ループ/スイッチ/セレクト文におけるラベルの関連付け:

    --- a/src/cmd/6g/gen.c
+++ b/src/cmd/6g/gen.c
@@ -265,18 +255,24 @@ loop:
 		breakpc = gbranch(AJMP, T);		// break:	goto done
 		scontin = continpc;
 		continpc = pc;
-		gen(n->nincr, L);				// contin:	incr
+
+		// define break and cotinue labels
+		for(lab=labellist; lab!=L; lab=lab->link) {
+			if(lab->label != p3)
+				break;
+			if(lab->op == OLABEL) {
+				lab->breakpc = breakpc;
+				lab->continpc = continpc;
+			}
+		}
+
+		gen(n->nincr);				// contin:	incr
 		patch(p1, pc);				// test:
 		if(n->ntest != N)
 			if(n->ntest->ninit != N)
-				gen(n->ntest->ninit, L);
+				gen(n->ntest->ninit);
 		bgen(n->ntest, 0, breakpc);		//		if(!test) goto break
-		if(labloop != L) {
-			labloop->op = OFOR;
-			labloop->continpc = continpc;
-			labloop->breakpc = breakpc;
-		}
-		gen(n->nbody, L);			//		body
+		gen(n->nbody);			//		body
 		patch(gbranch(AJMP, T), continpc);	//		goto contin
 		patch(breakpc, pc);			// done:
 		continpc = scontin;
@@ -289,12 +285,12 @@ loop:
 		patch(p1, pc);				// test:
 		if(n->ntest != N)
 			if(n->ntest->ninit != N)
-				gen(n->ntest->ninit, L);
+				gen(n->ntest->ninit);
 		bgen(n->ntest, 0, p2);			// 	if(!test) goto p2
-		gen(n->nbody, L);			//		then
+		gen(n->nbody);			//		then
 		p3 = gbranch(AJMP, T);			//		goto done
 		patch(p2, pc);				// else:
-		gen(n->nelse, L);			//		else
+		gen(n->nelse);			//		else
 		patch(p3, pc);				// done:
 		break;
 
@@ -302,12 +298,18 @@ loop:
 		sbreak = breakpc;
 		p1 = gbranch(AJMP, T);			// 	goto test
 		breakpc = gbranch(AJMP, T);		// break:	goto done
-		patch(p1, pc);				// test:
-		if(labloop != L) {
-			labloop->op = OFOR;
-			labloop->breakpc = breakpc;
+		// define break label
+		for(lab=labellist; lab!=L; lab=lab->link) {
+			if(lab->label != p3)
+				break;
+			if(lab->op == OLABEL) {
+				lab->breakpc = breakpc;
+			}
 		}
-		gen(n->nbody, L);			//		switch(test) body
+
+		patch(p1, pc);				// test:
+		gen(n->nbody);			//		switch(test) body
 		patch(breakpc, pc);			// done:
 		breakpc = sbreak;
 		break;
@@ -316,12 +318,18 @@ loop:
 		sbreak = breakpc;
 		p1 = gbranch(AJMP, T);			// 	goto test
 		breakpc = gbranch(AJMP, T);		// break:	goto done
-		patch(p1, pc);				// test:
-		if(labloop != L) {
-			labloop->op = OFOR;
-			labloop->breakpc = breakpc;
+		// define break label
+		for(lab=labellist; lab!=L; lab=lab->link) {
+			if(lab->label != p3)
+				break;
+			if(lab->op == OLABEL) {
+				lab->breakpc = breakpc;
+			}
 		}
-		gen(n->nbody, L);			//		select() body
+
+		patch(p1, pc);				// test:
+		gen(n->nbody);			//		select() body
 		patch(breakpc, pc);			// done:
 		breakpc = sbreak;
 		break;

    labloopの使用が削除され、p3とlabellistを組み合わせた新しいラベル関連付けロジックが導入されています。

  6. その他のgen呼び出しの変更:

    --- a/src/cmd/6g/gen.c
+++ b/src/cmd/6g/gen.c
@@ -484,7 +492,7 @@ cgen_callinter(Node *n, Node *res, int proc)
 		i = &tmpi;
 	}
 
-	gen(n->right, L);		// args
+	gen(n->right);			// args
 
 	regalloc(&nodr, types[tptr], res);
 	regalloc(&nodo, types[tptr], &nodr);
@@ -561,7 +569,7 @@ cgen_call(Node *n, int proc)
 		cgen(n->left, &afun);
 	}
 
-	gen(n->right, L);	// assign the args
+	gen(n->right);		// assign the args
 	t = n->left->type;
 
 	setmaxarg(t);
@@ -694,7 +702,7 @@ cgen_aret(Node *n, Node *res)
 void
 cgen_ret(Node *n)
 {
-	gen(n->left, L);	// copy out args
+	gen(n->left);		// copy out args
 	if(hasdefer)
 		ginscall(deferreturn, 0);
 	gins(ARET, N, N);

    cgen_callinter、cgen_call、cgen_ret内のgen呼び出しも引数Lが削除されています。

  7. src/cmd/6g/gg.hの変更:

    --- a/src/cmd/6g/gg.h
+++ b/src/cmd/6g/gg.h
@@ -74,7 +74,7 @@ struct	Pool
 typedef	struct	Label Label;
 struct	Label
 {
-	uchar	op;		// OFOR/OGOTO/OLABEL
+	uchar	op;		// OGOTO/OLABEL
 	Sym*	sym;
 	Prog*	label;		// pointer to code
 	Prog*	breakpc;	// pointer to code
@@ -133,7 +133,7 @@ EXTERN	int	sizeof_Array;	// runtime sizeof(Array)
  */
 void	compile(Node*);
 void	proglist(void);
-void	gen(Node*, Label*);
+void	gen(Node*);
 Node*	lookdot(Node*, Node*, int);
 void	inarggen(void);
 void	cgen_as(Node*, Node*);

    Label構造体のopフィールドのコメントからOFORが削除され、gen関数のプロトタイプが更新されています。

  8. テストファイルの移動とgolden.outの変更:

    --- a/test/bugs/bug137.go
+++ b/test/fixedbugs/bug137.go
similarity index 100%
rename from test/bugs/bug137.go
rename to test/fixedbugs/bug137.go

    --- a/test/golden.out
+++ b/test/golden.out
@@ -140,11 +140,6 @@ BUG: compilation succeeds incorrectly
 =========== bugs/bug136.go
 BUG: should not compile
 
-=========== bugs/bug137.go
-bugs/bug137.go:9: break label is not defined: L2
-bugs/bug137.go:15: break label is not defined: L4
-BUG should compile
-
 =========== bugs/bug138.go
 bugs/bug138.go:8: overflow converting constant to uint
 bugs/bug138.go:8: illegal combination of literals CONV 7

    bug137.goがfixedbugsディレクトリに移動し、golden.outから関連するエラーメッセージが削除されています。

コアとなるコードの解説

このコミットの核心は、gen関数におけるラベルの管理と解決のパラダイムシフトにあります。

以前のgen(Node *n, Label *labloop)では、labloop引数を通じて現在のループのラベル情報を明示的に渡していました。しかし、これはネストされたループや複数のラベルが存在する複雑なシナリオにおいて、正しいbreakやcontinueのターゲットを特定するのに不十分でした。

新しいアプローチでは、labloop引数を削除し、代わりにグローバルなlabellistリンクリストと、gen関数内で動的にラベルを関連付けるロジックを使用します。

  1. newlab関数: この関数は、新しいLabel構造体を作成し、それをlabellistの先頭に追加します。labellistは、現在アクティブな（定義された）すべてのラベルを追跡するスタックのような役割を果たします。新しいラベルが追加されると、それはリストの先頭に来るため、最も最近定義されたラベルが最初に検索されるようになります。

  2. OLABELとOGOTOの処理: これらのケースでは、newlab関数を呼び出すことで、ラベルの定義（OLABEL）やgoto文のターゲット（OGOTO）がlabellistに登録されます。lab->label = pc;という行は、ラベルが指すコードの開始位置（プログラムカウンタ）を記録します。

  3. OBREAKとOCONTINUEの解決: ラベル付きbreakやcontinue（n->left != Nの場合）では、もはやfindlab関数は使用されません。代わりに、labellistを先頭から走査します。

    for(lab=labellist; lab!=L; lab=lab->link) {
    if(lab->breakpc != P) { // または lab->continpc != P
        patch(gbranch(AJMP, T), lab->breakpc); // または lab->continpc
        break;
    }
}

    このループは、labellist内で有効なbreakpc（またはcontinpc）を持つ最初のLabelを見つけます。labellistは新しいラベルが先頭に追加されるため、この走査は最も内側の（最も最近定義された）有効なbreak/continueターゲットを優先的に見つけます。これにより、ラベルなしのbreak/continueが最も内側のループを対象とするのと同様に、ラベル付きの場合も正しいターゲットにジャンプできるようになります。

  4. ループ/スイッチ/セレクト文におけるラベルの関連付け: OFOR、OSWITCH、OSELECTのコード生成時、p3 = pc;で現在の文の開始位置のプログラムカウンタを保存します。その後、以下のループでlabellistを走査します。

    for(lab=labellist; lab!=L; lab=lab->link) {
    if(lab->label != p3) // 現在の文の開始位置と異なるラベルはスキップ
        break;
    if(lab->op == OLABEL) { // ラベル定義の場合
        lab->breakpc = breakpc;
        lab->continpc = continpc; // OFORの場合のみ
    }
}

    このループは、p3（現在のループ/スイッチ/セレクトの開始位置）と一致するlabelフィールドを持つOLABELを探します。これは、この制御フロー構造の直前に定義されたラベルを意味します。見つかった場合、そのラベルのbreakpcとcontinpcを、現在生成中の制御フロー構造のbreakおよびcontinueターゲットに設定します。 このメカニズムにより、Label: for { ... break Label }のようなコードで、Labelが正しくforループに関連付けられ、break Labelがそのforループから抜け出すようにコンパイルされるようになります。

この変更は、ラベルの解決をより動的かつコンテキスト依存的に行うことで、Go言語のラベル付き制御フローのセマンティクスを正確に反映することを可能にしました。

関連リンク

参考にした情報源リンク

  • Go言語のソースコード（特にsrc/cmd/6g/ディレクトリ）
  • Go言語のコンパイラに関する一般的な知識
  • Go言語のbreakとcontinueのセマンティクスに関する知識
  • Web検索: "Go bug 137 golang" (ただし、このコミットの「bug 137」はGoの公式Issueトラッカーの番号ではなく、当時の内部的な識別子である可能性が高いことを考慮)