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

このコミットは、Go言語のコンパイラである6g（当時の64ビットアーキテクチャ向けGoコンパイラの名称）におけるクロージャ（closures）のサポートを追加するものです。具体的には、クロージャが外部スコープの変数を正しくキャプチャし、それらの変数がクロージャの実行中も有効であるようにするためのコンパイラ内部の変更が含まれています。

コミット

commit 0970c4686350f772b481a270bd48767a953d3eb8
Author: Russ Cox <rsc@golang.org>
Date:   Fri Feb 6 13:47:10 2009 -0800

    closures - 6g support
    
    R=ken
    OCL=24501
    CL=24566

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

https://github.com/golang/go/commit/0970c4686350f772b481a270bd48767a953d3eb8

元コミット内容

closures - 6g support

R=ken
OCL=24501
CL=24566

変更の背景

Go言語は、関数をファーストクラスのオブジェクトとして扱うことができ、関数内で別の関数を定義する（ネストされた関数）ことをサポートしています。このようなネストされた関数が、その外側のスコープ（エンクロージングスコープ）の変数を参照する場合、そのネストされた関数は「クロージャ」となります。

クロージャが正しく機能するためには、外側の関数の実行が終了した後でも、クロージャが参照する変数がメモリ上に存在し続ける必要があります。これは、通常スタックに割り当てられるローカル変数の寿命とは異なるため、コンパイラが特別な処理を行う必要があります。

このコミットは、Go言語の初期段階において、6gコンパイラがクロージャを正しくコンパイルし、外部変数のキャプチャ（特にヒープへのエスケープ）をサポートするための基盤を構築することを目的としています。これにより、Go言語でより柔軟で表現力豊かなプログラミングが可能になります。

前提知識の解説

クロージャ (Closures)

クロージャとは、関数とその関数が定義された環境（レキシカル環境）を組み合わせたものです。具体的には、クロージャは自身が定義されたスコープ内の変数を「記憶」し、そのスコープが終了した後でもそれらの変数にアクセスして操作することができます。

例（Go言語）：

func outerFunction() func() int {
    x := 0 // outerFunctionのローカル変数
    return func() int { // クロージャ
        x++ // xをキャプチャして変更
        return x
    }
}

func main() {
    increment := outerFunction()
    fmt.Println(increment()) // 1
    fmt.Println(increment()) // 2
}

この例では、incrementというクロージャはouterFunctionが返された後も変数xにアクセスし、その値を変更し続けています。

エスケープ解析は、コンパイラ最適化の一種で、変数がその定義されたスコープの外に「エスケープ」するかどうかを判断します。もし変数がエスケープする場合（例えば、クロージャによって参照される場合や、ポインタとして返される場合）、その変数はスタックではなくヒープに割り当てられる必要があります。これにより、変数がスコープ外でも有効な状態を保つことができます。Goコンパイラは自動的にエスケープ解析を行い、変数をスタックまたはヒープに適切に割り当てます。

6g コンパイラ

6gは、Go言語の初期のコンパイラツールチェーンの一部で、64ビットシステム（AMD64アーキテクチャ）向けのGoコードをコンパイルするために使用されていました。現在では、gc（Go Compiler）という統一された名称で提供されており、6gという名前は使われていませんが、このコミットが作成された当時は特定のアーキテクチャ向けのコンパイラがxg（xはアーキテクチャ名）という命名規則で呼ばれていました。

コンパイラの内部構造（Go言語の場合）

Goコンパイラ（gc）は、主に以下のフェーズで構成されます。

パーシング (Parsing): ソースコードを抽象構文木（AST）に変換します。
型チェック (Type Checking): ASTの各ノードの型を検証し、型エラーを検出します。
中間表現 (IR) 生成: ASTをコンパイラ内部の中間表現に変換します。
最適化 (Optimization): 中間表現に対して様々な最適化を適用します（エスケープ解析もこの段階で行われることが多いです）。
コード生成 (Code Generation): 最適化された中間表現からターゲットアーキテクチャの機械語コードを生成します。

このコミットでは、特にパーシング後のASTの処理、型チェック、およびコード生成に関連する部分に影響を与えています。

技術的詳細

このコミットは、Goコンパイラがクロージャをサポートするために、主に以下の技術的側面を強化しています。

funcdepth の導入:
- Node構造体にfuncdepthフィールドが追加されました。これは、変数が定義された関数のネストの深さを示すものです。トップレベルの関数はfuncdepthが0となり、ネストが深くなるにつれて値が増加します。
- このfuncdepthは、変数が外部スコープから参照されているかどうか、つまりクロージャによってキャプチャされる必要があるかどうかを判断するために使用されます。
PPARAMREF クラスの導入:
- NodeのclassフィールドにPPARAMREFという新しい定数が追加されました。これは、外部関数のパラメータがクロージャによって参照される場合に、そのパラメータが参照渡しされることを示すために使用されます。
- PHEAP（ヒープに割り当てられる変数）とPPARAMREFは、クロージャが外部変数を参照する際の重要な分類となります。
クロージャ変数のキャプチャメカニズム:
- oldname関数（シンボルテーブルから既存の変数を取得する関数）が変更され、外部スコープの変数が内部関数（クロージャ）から参照された場合に、その変数をキャプチャするためのロジックが追加されました。
- 具体的には、n->closureという新しいフィールドが導入され、元の変数とクロージャ内でその変数を参照するための新しいONAMEノード（PPARAMREFクラスを持つ）が関連付けられます。
- キャプチャされた変数は、funclit->cvarsリストに追加され、後でクロージャの引数として渡されることになります。
クロージャのコード生成:
- funclit0とfunclit1という新しい関数が導入されました。これらは、関数リテラル（クロージャ）の宣言とコード生成を処理します。
- funclit1は、クロージャがキャプチャした変数（func->cvars）を基に、新しい関数型を構築します。キャプチャされた変数は、生成される関数の追加の引数として扱われます。
- sys.closureというランタイム関数が導入され、コンパイラはクロージャを生成する際にこの関数を呼び出します。sys.closureは、キャプチャされた変数と実際のクロージャ関数のポインタを組み合わせて、実行可能なクロージャオブジェクトを構築します。
エスケープ解析の調整:
- addrescapes関数（エスケープ解析を行う関数）が変更され、PPARAM（関数パラメータ）がエスケープする場合の処理が調整されました。エスケープするパラメータはPHEAPとしてマークされ、ヒープに割り当てられるようになります。また、スタック上のコピーを参照するためのstackparamノードも導入されます。

これらの変更により、Goコンパイラはクロージャが外部変数を参照する際に、その変数をヒープに適切に割り当て、クロージャがその変数にアクセスするためのメカニズムを確立します。

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

このコミットで特に重要な変更は以下のファイルに集中しています。

src/cmd/6g/cgen.c:
- agen関数（アドレス生成）において、ONAMEノードの処理が変更され、PHEAPだけでなくPPARAMREFクラスの変数も適切に扱われるようになりました。これは、クロージャが参照する外部変数のアドレスを正しく解決するために必要です。
src/cmd/gc/dcl.c:
- funchdrおよびfuncbody関数でfuncdepthのインクリメント/デクリメントが追加され、関数のネストレベルが追跡されるようになりました。
- funclit0とfunclit1という新しい関数が追加され、クロージャの宣言とコード生成のロジックが実装されました。
- oldname関数が大幅に修正され、外部スコープの変数がクロージャによって参照された場合に、その変数をキャプチャし、PPARAMREFノードを生成するロジックが追加されました。
- addvar関数でfuncdepthが設定されるようになりました。
- markdclstack関数が削除されました。
src/cmd/gc/go.h:
- Node構造体にfuncdepth、cvars（クロージャがキャプチャする変数リスト）、outer、closureといった新しいフィールドが追加されました。
- PPARAMREFという新しいPクラス定数が追加されました。
- グローバル変数としてfuncdepthとfunclitが宣言されました。
- funclit0とfunclit1のプロトタイプ宣言が追加されました。
src/cmd/gc/go.y:
- Go言語の文法定義ファイルで、関数リテラル（クロージャ）のパーシングロジックがfunclit0とfunclit1を呼び出すように変更されました。これにより、パーサーがクロージャを認識し、コンパイラのバックエンドに処理を委ねるようになりました。
src/cmd/gc/subr.c:
- デバッグ出力のためにNodeのfuncdepthを表示するロジックが追加されました。
- ullmancalc関数（Ullman数計算）でPPARAMREFとPHEAPクラスの変数のUllman数が調整されました。
src/cmd/gc/sys.go:
- sys.closureというランタイム関数が宣言されました。これはコンパイラがクロージャを生成する際に内部的に使用するものです。
src/cmd/gc/sysimport.c:
- sys.closureがシステムインポートリストに追加されました。
src/cmd/gc/walk.c:
- ONAMEノードの処理でPPARAMREFクラスが考慮されるようになりました。
- addrescapes関数（エスケープ解析）が変更され、関数パラメータがヒープにエスケープする場合の処理が調整されました。

コアとなるコードの解説

`src/cmd/gc/dcl.c` の変更点

このファイルは、Goコンパイラの宣言処理（declaration processing）を担当しています。クロージャのサポートにおいて、最も重要な変更が集中しています。

funcdepth の管理:

--- a/src/cmd/gc/dcl.c
+++ b/src/cmd/gc/dcl.c
@@ -402,13 +402,12 @@ funchdr(Node *n)
 	autodcl = dcl();
 	autodcl->back = autodcl;

-	if(dclcontext != PEXTERN)
+	if(funcdepth == 0 && dclcontext != PEXTERN)
 		fatal("funchdr: dclcontext");

 	dclcontext = PAUTO;
 	markdcl();
 	funcargs(n->type);
-
 }

 void
@@ -418,6 +417,8 @@ funcargs(Type *ft)
 	Iter save;
 	int all;

+	funcdepth++;
+
 	// declare the this/in arguments
 	t = funcfirst(&save, ft);
 	while(t != T) {
@@ -466,9 +467,176 @@ funcbody(Node *n)
 	if(dclcontext != PAUTO)
 		fatal("funcbody: dclcontext");
 	popdcl();
-	dclcontext = PEXTERN;
+	funcdepth--;
+	if(funcdepth == 0)
+		dclcontext = PEXTERN;
 }

funcdepthは、現在の関数のネストレベルを追跡するためのグローバル変数です。funcargs（関数の引数を処理する前）でインクリメントされ、funcbody（関数本体の処理後）でデクリメントされます。これにより、コンパイラはどの変数がどのネストレベルで定義されているかを把握し、クロージャによる外部変数のキャプチャを判断できるようになります。

funclit0 と funclit1 の導入:

--- a/src/cmd/gc/dcl.c
+++ b/src/cmd/gc/dcl.c
@@ -469,6 +469,8 @@ funcbody(Node *n)
 	if(funcdepth == 0)
 		dclcontext = PEXTERN;
 }
+
+void
+funclit0(Type *t)
+{
+	Node *n;
+
+	n = nod(OXXX, N, N);
+	n->outer = funclit;
+	funclit = n;
+
+	funcargs(t);
+}
+
+Node*
+funclit1(Type *type, Node *body)
+{
+	Node *func;
+	Node *a, *d, *f, *n, *args, *clos, *in, *out;
+	Type *ft, *t;
+	Iter save;
+	int narg, shift;
+
+	popdcl();
+	func = funclit;
+	funclit = func->outer;
+
+	// build up type of func f that we're going to compile.
+	// as we referred to variables from the outer function,
+	// we accumulated a list of PHEAP names in func.
+	//
+	narg = 0;
+	if(func->cvars == N)
+		ft = type;
+	else {
+		// add PHEAP versions as function arguments.
+		in = N;
+		for(a=listfirst(&save, &func->cvars); a; a=listnext(&save)) {
+			d = nod(ODCLFIELD, a, N);
+			d->type = ptrto(a->type);
+			in = list(in, d);
+
+			// while we're here, set up a->heapaddr for back end
+			n = nod(ONAME, N, N);
+			snprint(namebuf, sizeof namebuf, "&%s", a->sym->name);
+			n->sym = lookup(namebuf);
+			n->type = ptrto(a->type);
+			n->class = PPARAM;
+			n->xoffset = narg*types[tptr]->width;
+			n->addable = 1;
+			n->ullman = 1;
+			narg++;
+			a->heapaddr = n;
+
+			a->xoffset = 0;
+
+			// unlink from actual ONAME in symbol table
+			a->closure->closure = a->outer;
+		}
+
+		// add a dummy arg for the closure's caller pc
+		d = nod(ODCLFIELD, a, N);
+		d->type = types[TUINTPTR];
+		in = list(in, d);
+
+		// slide param offset to make room for ptrs above.
+		// narg+1 to skip over caller pc.
+		shift = (narg+1)*types[tptr]->width;
+
+		// now the original arguments.
+		for(t=structfirst(&save, getinarg(type)); t; t=structnext(&save)) {
+			d = nod(ODCLFIELD, t->nname, N);
+			d->type = t->type;
+			in = list(in, d);
+
+			a = t->nname;
+			if(a != N) {
+				if(a->stackparam != N)
+					a = a->stackparam;
+				a->xoffset += shift;
+			}
+		}
+		in = rev(in);
+
+		// out arguments
+		out = N;
+		for(t=structfirst(&save, getoutarg(type)); t; t=structnext(&save)) {
+			d = nod(ODCLFIELD, t->nname, N);
+			d->type = t->type;
+			out = list(out, d);
+
+			a = t->nname;
+			if(a != N) {
+				if(a->stackparam != N)
+					a = a->stackparam;
+				a->xoffset += shift;
+			}
+		}
+		out = rev(out);
+
+		ft = functype(N, in, out);
+	}
+
+	// declare function.
+	vargen++;
+	snprint(namebuf, sizeof(namebuf), "_f%.3ld", vargen);
+	f = newname(lookup(namebuf));
+	addvar(f, ft, PFUNC);
+	f->funcdepth = 0;
+
+	// compile function
+	n = nod(ODCLFUNC, N, N);
+	n->nname = f;
+	n->type = ft;
+	if(body == N)
+		body = nod(ORETURN, N, N);
+	n->nbody = body;
+	compile(n);
+	funcdepth--;
+
+	// if there's no closure, we can use f directly
+	if(func->cvars == N)
+		return f;
+
+	// build up type for this instance of the closure func.
+	in = N;
+	d = nod(ODCLFIELD, N, N);	// siz
+	d->type = types[TINT];
+	in = list(in, d);
+	d = nod(ODCLFIELD, N, N);	// f
+	d->type = ft;
+	in = list(in, d);
+	for(a=listfirst(&save, &func->cvars); a; a=listnext(&save)) {
+		d = nod(ODCLFIELD, N, N);	// arg
+		d->type = ptrto(a->type);
+		in = list(in, d);
+	}
+	in = rev(in);
+
+	d = nod(ODCLFIELD, N, N);
+	d->type = type;
+	out = d;
+
+	clos = syslook("closure", 1);
+	clos->type = functype(N, in, out);
+
+	// literal expression is sys.closure(siz, f, arg0, arg1, ...)
+	// which builds a function that calls f after filling in arg0,
+	// arg1, ... for the PHEAP arguments above.
+	args = N;
+	if(narg*8 > 100)
+		yyerror("closure needs too many variables; runtime will reject it");
+	a = nodintconst(narg*8);
+	args = list(args, a);	// siz
+	args = list(args, f);	// f
+	for(a=listfirst(&save, &func->cvars); a; a=listnext(&save)) {
+		d = oldname(a->sym);
+		addrescapes(d);
+		args = list(args, nod(OADDR, d, N));
+	}
+	args = rev(args);
+
+	return nod(OCALL, clos, args);
+}

funclit0は、関数リテラルの宣言時に呼び出され、現在のfunclit（クロージャの情報を保持するノード）を保存し、新しいfunclitを設定します。 funclit1は、関数リテラルの本体が解析された後に呼び出され、実際のクロージャのコード生成を行います。

func->cvarsリスト（クロージャがキャプチャする変数）が存在する場合、これらの変数は生成される関数の追加の引数として扱われます。これにより、クロージャは外部変数を「受け取る」ことができます。
sys.closureというランタイム関数が呼び出され、キャプチャされた変数と実際のクロージャ関数のポインタを組み合わせて、実行可能なクロージャオブジェクトが構築されます。これは、クロージャが外部変数を参照するための重要なメカニズムです。

oldname の変更:
```
--- a/src/cmd/gc/dcl.c
+++ b/src/cmd/gc/dcl.c
@@ -909,6 +1056,7 @@ Node*
 oldname(Sym *s)
 {
 	Node *n;
+	Node *c;

 	n = s->oname;
 	if(n == N) {
@@ -918,6 +1066,26 @@ oldname(Sym *s)
 		n->addable = 1;
 		n->ullman = 1;
 	}
+	if(n->funcdepth > 0 && n->funcdepth != funcdepth) {
+		// inner func is referring to var
+		// in outer func.
+		if(n->closure == N || n->closure->funcdepth != funcdepth) {
+			// create new closure var.
+			c = nod(ONAME, N, N);
+			c->sym = s;
+			c->class = PPARAMREF;
+			c->type = n->type;
+			c->addable = 0;
+			c->ullman = 2;
+			c->funcdepth = funcdepth;
+			c->outer = n->closure;
+			n->closure = c;
+			c->closure = n;
+			funclit->cvars = list(c, funclit->cvars);
+		}
+		// return ref to closure var, not original
+		return n->closure;
+	}
 	return n;
 }
```
oldname関数は、シンボルテーブルから既存の変数を参照する際に呼び出されます。この変更は、クロージャが外部スコープの変数を参照する際の核心部分です。もし参照される変数のfuncdepthが現在の関数のfuncdepthと異なる場合（つまり、外部スコープの変数である場合）、新しいONAMEノードが作成されます。この新しいノードはPPARAMREFクラスを持ち、元の変数への参照として機能します。このPPARAMREFノードはfunclit->cvarsリストに追加され、クロージャがキャプチャする変数としてマークされます。これにより、コンパイラは後でこれらの変数をヒープに割り当て、クロージャがアクセスできるようにします。

`src/cmd/gc/go.h` の変更点

このファイルは、Goコンパイラの内部で使用される主要なデータ構造や定数を定義しています。

Node 構造体の拡張:

--- a/src/cmd/gc/go.h
+++ b/src/cmd/gc/go.h
@@ -187,6 +187,7 @@ struct	Node
 	uchar	colas;		// OAS resulting from :=
 	uchar	diag;		// already printed error about this
 	uchar	noescape;	// ONAME never move to heap
+	uchar	funcdepth;

 	// most nodes
 	Node*	left;
@@ -209,6 +210,7 @@ struct	Node
 	Node*	nname;
 	Node*	enter;
 	Node*	exit;
+	Node*	cvars;	// closure params

 	// OLITERAL/OREGISTER
 	Val	val;
@@ -218,6 +220,10 @@ struct	Node
 	Node*	stackparam;	// OPARAM node referring to stack copy of param
 	Node*	alloc;	// allocation call

+	// ONAME closure param with PPARAMREF
+	Node*	outer;	// outer PPARAMREF in nested closure
+	Node*	closure;	// ONAME/PHEAP <-> ONAME/PPARAMREF
+
 	Sym*	osym;		// import
 	Sym*	psym;		// import
 	Sym*	sym;		// various

Node構造体は、抽象構文木（AST）の各ノードを表します。funcdepthは前述の通りネストレベルを、cvarsはクロージャがキャプチャする変数のリストを、outerとclosureはネストされたクロージャにおける変数参照のリンキングを管理するために追加されました。

PPARAMREF の追加:
```
--- a/src/cmd/gc/go.h
+++ b/src/cmd/gc/go.h
@@ -414,6 +420,7 @@ enum
 	PAUTO,
 	PPARAM,
 	PPARAMOUT,
+	PPARAMREF,	// param passed by reference
 	PFUNC,

 	PHEAP = 1<<7,
```
PPARAMREFは、クロージャによって参照される外部パラメータを示す新しいクラスです。これにより、コンパイラはこれらの変数を特別に扱い、ヒープに割り当てるなどの処理を行うことができます。

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

このファイルは、6gコンパイラのコード生成バックエンドの一部です。

agen 関数の変更:

--- a/src/cmd/6g/cgen.c
+++ b/src/cmd/6g/cgen.c
@@ -526,9 +526,18 @@ agen(Node *n, Node *res)
 		break;

 	case ONAME:
-		// should only get here for heap vars
-		if(!(n->class & PHEAP))
+		// should only get here with names in this func.
+		if(n->funcdepth > 0 && n->funcdepth != funcdepth) {
+			dump("bad agen", n);
+			fatal("agen: bad ONAME funcdepth %d != %d",
+				n->funcdepth, funcdepth);
+		}
+
+		// should only get here for heap vars or paramref
+		if(!(n->class & PHEAP) && n->class != PPARAMREF) {
+			dump("bad agen", n);
 			fatal("agen: bad ONAME class %#x", n->class);
+		}
 		cgen(n->heapaddr, res);
 		if(n->xoffset != 0) {
 			nodconst(&n1, types[TINT64], n->xoffset);

agen関数は、変数のアドレスを生成する際に呼び出されます。この変更により、ONAMEノードがPHEAPまたはPPARAMREFクラスである場合にのみ、そのアドレスが正しく処理されるようになります。これは、クロージャがキャプチャした変数がヒープ上に存在することを前提としたコード生成を行うために重要です。

参考にした情報源リンク

Go closures implementation details 6g compiler - Web search results (provided by the tool)

comemo