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

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

このコミットは、Goコンパイラのバックエンドの一部であるcmd/gc内のエスケープ解析ロジックに対する重要な改善を導入しています。具体的には、src/cmd/gc/esc.cとsrc/cmd/gc/go.hの2つのファイルが変更されています。

  • src/cmd/gc/esc.c: Goコンパイラのエスケープ解析の主要なロジックが実装されているC言語のソースファイルです。このファイルは、変数がスタックに割り当てられるべきか、それともヒープに「エスケープ」してガベージコレクションの対象となるべきかを決定する役割を担っています。
  • src/cmd/gc/go.h: Goコンパイラの内部で使用される共通のヘッダーファイルで、データ構造、定数、列挙型などが定義されています。このコミットでは、エスケープ解析に関連する新しい定数が追加されています。

コミット

このコミットは、Goコンパイラのエスケープ解析において、関数の入力パラメータ（inパラメータ）が出力パラメータ（outパラメータ、つまり戻り値）にどのように流れるかをより正確に追跡するための機能を追加します。これにより、不要なヒープ割り当てを減らし、プログラムのパフォーマンスを向上させることを目的としています。

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

https://github.com/golang/go/commit/75692424d2b8e01d24bca015c480af7874373b5e

元コミット内容

commit 75692424d2b8e01d24bca015c480af7874373b5e
Author: Luuk van Dijk <lvd@golang.org>
Date:   Mon Oct 22 10:18:17 2012 +0200

    cmd/gc: escape analysis to track flow of in to out parameters.
    
    includes step 0: synthesize outparams, from 6600044
    step 1: give outparams loopdepth 0 and verify unchanged results
    step 2: generate esc:$mask tags, but still tie to sink if a param has mask != 0
    next step: use in esccall (and ORETURN with implicit OAS2FUNC) to avoid tying to sink
    
    R=rsc
    CC=golang-dev
    https://golang.org/cl/6610054

変更の背景

Go言語はガベージコレクション（GC）を持つ言語であり、メモリ管理はコンパイラとランタイムによって自動的に行われます。エスケープ解析は、このメモリ管理を最適化するための重要なコンパイラ最適化の一つです。変数がその宣言されたスコープを「エスケープ」しない場合、その変数はスタックに割り当てることができ、ヒープ割り当てとそれに伴うGCのオーバーヘッドを回避できます。

しかし、以前のエスケープ解析では、関数の入力パラメータが戻り値として返される（inからoutへのフロー）ケースを正確に追跡する能力に限界がありました。例えば、以下のようなGoのコードを考えます。

func createAndReturn(x int) *int {
    y := x // yはxの値を持つ
    return &y // yのアドレスを返す
}

この場合、yはcreateAndReturn関数のスコープ内で宣言されていますが、そのアドレスが戻り値として返されるため、yは関数スコープを「エスケープ」し、ヒープに割り当てられる必要があります。もしエスケープ解析がこのフローを正確に検出できないと、誤ってスタックに割り当てようとして不正なメモリ参照を引き起こすか、あるいは安全側に倒して不必要にヒープに割り当ててしまい、パフォーマンスの低下を招く可能性がありました。

このコミットは、特にinパラメータがoutパラメータ（戻り値）として使用される場合のフローをより詳細に追跡することで、エスケープ解析の精度を向上させ、より多くの変数をスタックに割り当てられるようにし、結果としてGCの負荷を軽減し、プログラムの実行速度を向上させることを目的としています。

前提知識の解説

エスケープ解析 (Escape Analysis)

エスケープ解析は、コンパイラ最適化の一種で、プログラム内の変数がその宣言されたスコープを「エスケープ」するかどうかを決定します。

  • スタック割り当て: 変数がその関数呼び出しの期間中のみ存在し、関数が終了すると破棄される場合、その変数はスタックに割り当てられます。スタック割り当ては非常に高速で、ガベージコレクションの対象になりません。
  • ヒープ割り当て: 変数がその関数呼び出しの期間を超えて存在する必要がある場合（例：ポインタが関数外に返される、グローバル変数に代入されるなど）、その変数はヒープに割り当てられます。ヒープ割り当てはスタック割り当てよりも遅く、ガベージコレクタが不要になったメモリを回収する必要があります。

エスケープ解析の目的は、可能な限り多くの変数をスタックに割り当てることで、ヒープ割り当ての数を減らし、ガベージコレクションの頻度と時間を削減し、プログラムのパフォーマンスを向上させることです。

Goコンパイラ (cmd/gc)

cmd/gcは、Go言語の公式コンパイラのフロントエンドおよびバックエンドの一部です。Goのソースコードを解析し、抽象構文木（AST）を構築し、型チェック、エスケープ解析、最適化、そして最終的に機械語コードを生成する役割を担っています。

抽象構文木 (Abstract Syntax Tree, AST)

ASTは、ソースコードの構造を木構造で表現したものです。コンパイラはソースコードを直接操作するのではなく、ASTを操作して様々な解析や変換を行います。エスケープ解析もAST上で行われます。

パラメータのフロー (inパラメータとoutパラメータ)

  • inパラメータ (Input Parameters): 関数に渡される引数です。
  • outパラメータ (Output Parameters): 関数の戻り値です。Goでは複数の戻り値をサポートしており、これらもoutパラメータとして扱われます。

エスケープ解析では、inパラメータがoutパラメータとして「流れる」場合、つまりinパラメータの参照がoutパラメータを通じて関数外に公開される場合に、そのinパラメータがエスケープすると判断する必要があります。

sink (シンク)

エスケープ解析の文脈におけるsinkは、変数が「どこか不明な場所」にエスケープする、あるいは「グローバルな場所」にエスケープするときの抽象的な概念です。変数がsinkに流れると判断された場合、それはヒープに割り当てられると見なされます。このコミットの目的の一つは、inからoutへのフローを正確に追跡することで、不必要にsinkに「結びつける」（tie to sink）ことを避けることです。

loopdepth (ループ深度)

エスケープ解析では、変数の寿命を判断するためにloopdepthという概念が使われることがあります。これは、変数が宣言されたスコープがどれくらいの「深さ」のループ内にあるかを示す指標です。loopdepthが小さいほど、変数の寿命は短いと判断され、スタック割り当ての可能性が高まります。このコミットでは、outパラメータにloopdepth 0を設定することで、特別な扱いをしています。これは、outパラメータが関数の呼び出し元に直接返されるため、その寿命が関数内のループ構造に依存しないことを示唆している可能性があります。

技術的詳細

このコミットの核心は、エスケープ解析がinパラメータからoutパラメータへのデータフローをより正確に追跡し、それに基づいて適切なエスケープ判断を下すためのメカニズムを導入することです。

  1. outパラメータの合成とloopdepthの初期化:

    • コミットメッセージの「step 0: synthesize outparams」は、コンパイラが関数の戻り値を内部的に表現するノード（PARAMOUT）を生成することを指します。
    • 「step 1: give outparams loopdepth 0」は、これらのPARAMOUTノードのescloopdepthを0に設定することを意味します。これは、outパラメータが関数内のローカル変数とは異なる寿命を持つことをエスケープ解析に伝えるための重要なステップです。loopdepth 0は、その変数が最も外側のスコープ、あるいは特別なスコープに属していることを示唆し、エスケープ解析のフロー追跡において、ローカル変数とは異なる優先順位やルールが適用されることを可能にします。

  2. esc:$maskタグの導入:

    • 以前のエスケープ解析では、safetagという単一のタグ（"noescape"）を使用して、パラメータがエスケープしないことを示していました。しかし、inからoutへのフローを詳細に追跡するためには、より粒度の高い情報が必要です。
    • このコミットでは、esc:$maskという新しい形式のタグが導入されます。$maskはビットマスクであり、特定のビットがセットされることで、そのパラメータがどのoutパラメータに流れるか、あるいは他のエスケープ特性を持つかを示すことができます。
    • mktag(int mask)関数は、このビットマスクから"esc:%#x"形式の文字列リテラルを生成します。
    • parsetag(Strlit *note)関数は、この文字列リテラルを解析してビットマスクを抽出し、エスケープ特性を判断します。
    • EscBitsとEscMaskという新しい定数がgo.hに追加され、このビットマスク操作をサポートします。EscBitsはマスクのオフセットを、EscMaskはエスケープタイプ（EscNone, EscReturnなど）を抽出するためのマスクを定義します。

  3. ORETURN（戻り値）の特殊なハンドリング:

    • ORETURNはGoのreturn文に対応するASTノードです。関数が複数の戻り値を持つ場合、Goコンパイラは内部的にOAS2FUNC（複数値の代入）のような構造に変換することがあります。
    • このコミットでは、ORETURNノードが処理される際に、戻り値がcurfn->dcl（現在の関数の宣言リスト、これにはPARAMOUTも含まれる）内の対応するPARAMOUTノードにescassignされるように変更されています。これにより、戻り値として渡される値のエスケープ特性が、そのPARAMOUTノードに正確に伝播されるようになります。

  4. esccallにおけるタグの利用:

    • esccall関数は、関数呼び出しのエスケープ解析を行います。以前はsafetag（"noescape"）のみをチェックしていましたが、この変更によりparsetag関数を使用して、より詳細なesc:$maskタグを解析し、それに基づいて引数がsinkに結びつけられるべきかを判断します。これにより、EscReturnなどの新しいエスケープ特性を持つパラメータが適切に処理されます。

  5. escwalkにおけるinからoutへのフロー検出:

    • escwalk関数は、ASTを再帰的に走査し、変数のフローを追跡してエスケープ特性を決定する主要な関数です。
    • このコミットの最も重要な変更点の一つは、escwalk内にinパラメータがoutパラメータに流れるケースを明示的に検出するロジックが追加されたことです。
    • 具体的には、dst（代入先）がPARAMOUTであり、src（代入元）がPARAM（入力パラメータ）であり、かつlevel == 0（直接の代入）の場合に、srcのescプロパティにEscReturnフラグと、どのoutパラメータに流れるかを示すビットマスク（1<<(dst->vargen + EscBits)）が設定されます。vargenはパラメータのインデックスを示します。
    • これにより、inパラメータが特定のoutパラメータを通じてエスケープすることが正確に記録され、不必要なsinkへの結びつけが回避されます。

  6. esctagにおけるタグの生成:

    • esctag関数は、エスケープ解析の結果に基づいて、関数のパラメータにエスケープタグを付与します。
    • 以前は、ポインタを持つEscNoneのパラメータに一律でsafetagを付与していました。
    • 変更後、EscNoneまたはEscReturnのエスケープ特性を持つポインタパラメータに対して、mktag(ll->n->esc)を使用して、そのパラメータの実際のエスケープ特性（EscReturnの場合はどのoutパラメータに流れるかを含む）をエンコードしたesc:$maskタグを付与するようになりました。

これらの変更により、Goコンパイラのエスケープ解析は、関数の入力と出力の間で発生する複雑なデータフローをより正確にモデル化できるようになり、結果としてより効率的なコード生成が可能になります。

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

src/cmd/gc/esc.c

  1. safetagの削除とtags配列、mktag、parsetag関数の追加:

    • safetagグローバル変数が削除され、代わりにtagsというStrlitポインタの配列が導入されました。
    • mktag(int mask): maskに基づいて"esc:%#x"形式の文字列リテラルを生成し、キャッシュする新しい関数。
    • parsetag(Strlit *note): note文字列からエスケープマスクを解析して返す新しい関数。
    -static Strlit*\tsafetag;\t// gets slapped on safe parameters\' field types for export
+static Strlit *tags[16] = { nil, nil, nil, nil, nil, nil, nil, nil, nil, nil, nil, nil, nil, nil, nil, nil };
+
+static Strlit*
+mktag(int mask)
+// ... (implementation)
+
+static int
+parsetag(Strlit *note)
+// ... (implementation)

  2. analyze関数からsafetag初期化の削除:

    • analyze関数内のsafetagの初期化が不要になったため削除。
    -	if(safetag == nil)
-		safetag = strlit("noescape");

  3. escfunc関数におけるPARAMOUTとPARAMのescloopdepth設定の変更:

    • PARAMOUT（出力パラメータ）のescloopdepthがe->loopdepthから0に固定されました。
    • PARAM（入力パラメータ）のescloopdepthがe->loopdepthから1に固定されました。
    		case PPARAMOUT:
-			// output parameters flow to the sink
-			escflows(e, &e->theSink, ll->n);
-			ll->n->escloopdepth = e->loopdepth;
+			// out params are in a loopdepth between the sink and all local variables
+			ll->n->escloopdepth = 0;
			break;
		case PPARAM:
			if(ll->n->type && !haspointers(ll->n->type))
				break;
			ll->n->esc = EscNone;	// prime for escflood later
			e->noesc = list(e->noesc, ll->n);
-			ll->n->escloopdepth = e->loopdepth;
+			ll->n->escloopdepth = 1; 
			break;

  4. ORETURN（戻り値）の処理の変更:

    • 単一の戻り値でOAS2FUNCに変換されるケースをスキップするロジックが追加されました。
    • 複数の戻り値の場合、curfn->dcl（関数の宣言リスト）から対応するPARAMOUTノードを見つけ、escassignを使用して戻り値のフローをPARAMOUTに結びつけるようになりました。
    	case ORETURN:
-		for(ll=n->list; ll; ll=ll->next)
-			escassign(e, &e->theSink, ll->n);
+		if(count(n->list) == 1 && curfn->type->outtuple > 1) {
+			// OAS2FUNC in disguise
+			break;
+		}
+
+		ll=n->list;
+		for(lr = curfn->dcl; lr && ll; lr=lr->next) {
+			if (lr->n->op != ONAME || lr->n->class != PPARAMOUT)
+				continue;
+			escassign(e, lr->n, ll->n);
+			ll = ll->next;
+		}
+		if (ll != nil)
+			fatal("esc return list");
		break;

  5. esccall関数におけるタグチェックの変更:

    • safetag->sとの文字列比較から、parsetag(t->note) != EscNoneという新しいタグ解析関数を使用するように変更されました。
    	if(n->op != OCALLFUNC) {
		t = getthisx(fntype)->type;
-		if(!t->note || strcmp(t->note->s, safetag->s) != 0)
+		if(parsetag(t->note) != EscNone)
			escassign(e, &e->theSink, n->left->left);
	}
	// ...
-	if(!t->note || strcmp(t->note->s, safetag->s) != 0)
+	if(parsetag(t->note) != EscNone)
		escassign(e, &e->theSink, src);

  6. escwalk関数におけるinからoutへのフロー追跡ロジックの追加:

    • dstがPARAMOUTでsrcがPARAMの場合に、srcのエスケープ特性にEscReturnフラグと、outパラメータのインデックスに基づくビットマスクを追加するロジックが導入されました。
    +	// Input parameter flowing to output parameter?
+	if(dst->op == ONAME && dst->class == PPARAMOUT && dst->vargen < 20) {
+		if(src->op == ONAME && src->class == PPARAM && level == 0 && src->curfn == dst->curfn) {
+			if(src->esc != EscScope && src->esc != EscHeap) {
+				if(debug['m'])
+					warnl(src->lineno, "leaking param: %hN to result %S", src, dst->sym);
+				if((src->esc&EscMask) != EscReturn)
+					src->esc = EscReturn;
+				src->esc |= 1<<(dst->vargen + EscBits);
+			}
+			goto recurse;
+		}
+	}

  7. esctag関数におけるタグ生成の変更:

    • ll->n->escのチェックがEscNoneだけでなくEscReturnも含むように変更され、safetagの代わりにmktag(ll->n->esc)を使用して、より具体的なエスケープタグを生成するようになりました。
    -		switch (ll->n->esc) {
+		switch (ll->n->esc&EscMask) {
		case EscNone:	// not touched by escflood
+		case EscReturn:	
			if(haspointers(ll->n->type)) // don't bother tagging for scalars
-				ll->n->paramfld->note = safetag;
+				ll->n->paramfld->note = mktag(ll->n->esc);
+			break;
		case EscHeap:	// touched by escflood, moved to heap
		case EscScope:	// touched by escflood, value leaves scope
			break;

src/cmd/gc/go.h

  1. 新しいエスケープ定数の追加:

    • EscReturn、EscBits、EscMaskがenumに追加されました。
    	EscHeap,
	EscScope,
	EscNone,
+	EscReturn,
 	EscNever,
+	EscBits = 4,
+	EscMask = (1<<EscBits) - 1,
 };

コアとなるコードの解説

src/cmd/gc/esc.c

  • mktagとparsetag:

    • mktagは、エスケープ解析の結果をエンコードするための新しいタグ文字列（例: "esc:0x1"）を生成します。mask引数は、エスケープの種類（EscReturnなど）と、どの戻り値に流れるかを示すビットマスクを含みます。これにより、単に「エスケープしない」という情報だけでなく、より詳細なエスケープ経路を表現できるようになります。
    • parsetagは、このタグ文字列を解析して元のマスク値を取り出します。これにより、関数呼び出しのエスケープ解析時に、呼び出される関数のパラメータがどのようなエスケープ特性を持つかを正確に読み取ることができます。

  • escfuncにおけるPARAMOUTとPARAMのescloopdepth:

    • PARAMOUT（戻り値）のescloopdepthを0に設定することは、これらの変数が関数内の通常のローカル変数とは異なる、より「グローバル」な寿命を持つことをエスケープ解析に伝えます。これにより、エスケープ解析は戻り値を特別に扱い、関数呼び出し元へのフローを考慮できるようになります。
    • PARAM（入力パラメータ）のescloopdepthを1に設定することも同様に、これらの変数が関数内のローカル変数とは異なる初期状態を持つことを示唆し、inからoutへのフロー追跡の基盤となります。

  • ORETURNの処理:

    • 以前は、return文のすべての戻り値が単純にtheSink（ヒープへのエスケープ）に結びつけられていました。
    • 変更後、ORETURNが複数の戻り値を持つ場合、それぞれの戻り値が対応するPARAMOUTノードにescassignされるようになりました。これは、戻り値がヒープにエスケープするのではなく、特定のoutパラメータを通じて関数外に「流れる」ことを正確にモデル化します。これにより、戻り値がスタックに割り当てられる可能性が広がります。

  • esccallにおけるタグの利用:

    • 関数呼び出しのエスケープ解析を行うesccallでは、呼び出される関数のパラメータの型に付与されたタグをparsetagで解析します。もしタグがEscNoneでない（つまり、何らかのエスケープ特性を持つ）場合、そのパラメータはtheSinkに結びつけられます。これにより、EscReturnなどの新しいエスケープ特性を持つパラメータが、呼び出し側で適切にヒープに割り当てられるべきかどうかが判断されます。

  • escwalkにおけるinからoutへのフロー追跡:

    • この変更は、inパラメータがoutパラメータに直接代入されるケースを明示的に検出します。
    • dst->op == ONAME && dst->class == PPARAMOUTは、代入先がoutパラメータであることを意味します。
    • src->op == ONAME && src->class == PPARAMは、代入元がinパラメータであることを意味します。
    • level == 0は、直接の代入であることを示します。
    • この条件が満たされた場合、src（inパラメータ）のescプロパティにEscReturnフラグがセットされ、さらに1<<(dst->vargen + EscBits)というビットマスクが追加されます。このビットマスクは、srcがどの特定のoutパラメータ（dst->vargenで識別される）を通じてエスケープするかをエンコードします。これにより、エスケープ解析はinからoutへの正確なフローを把握し、不必要なヒープ割り当てを回避できます。

  • esctagにおけるタグ生成:

    • エスケープ解析の最終段階で、esctagは関数のパラメータにタグを付与します。
    • EscNoneまたはEscReturnのエスケープ特性を持つポインタパラメータに対して、mktag(ll->n->esc)を使用して、そのパラメータの正確なエスケープ特性をエンコードしたタグを生成します。これにより、コンパイラの他の部分や、将来の最適化でこの詳細なエスケープ情報が利用できるようになります。

src/cmd/gc/go.h

  • EscReturn: 新しいエスケープタイプで、変数が関数の戻り値としてエスケープすることを示します。
  • EscBitsとEscMask: EscBitsは、EscReturnのビットマスク内でoutパラメータのインデックスをエンコードするためのビットシフト量（4ビット）を定義します。EscMaskは、エスケープタイプ（EscNone, EscReturnなど）を抽出するためのマスク（下位4ビット）を定義します。これらは、inからoutへのフローをビットマスクで効率的に表現するための基盤となります。

関連リンク

  • Go言語のエスケープ解析に関する公式ドキュメントやブログ記事（当時のものがあれば）
  • GoのIssueトラッカーで関連するエスケープ解析の改善に関する議論
  • Goのコードレビューシステム（Gerrit）のCL (Change List) ページ: https://golang.org/cl/6610054

参考にした情報源リンク

  • Go言語のエスケープ解析に関する一般的な情報源 (例: Goの公式ブログ、Goのドキュメント、関連する技術記事)
  • コンパイラ最適化、特にエスケープ解析に関する一般的なコンピュータサイエンスの教科書や論文
  • Goコンパイラのソースコード（src/cmd/gcディレクトリ）の他の部分の構造と命名規則
  • GoのGerritシステムでのコードレビューコメント（CL 6610054）