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

このコミットは、Goコンパイラのcmd/gc（現在のcmd/compileに相当）における、一時変数のライフタイム管理に関する重要な改善を導入しています。特に、チャネル操作やマップ操作に関連する一時変数の生存期間を短縮し、ガベージコレクション（GC）の効率とコンパイラの最適化能力を向上させることを目的としています。order.c（現在のcmd/compile/internal/walk）にVARKILL命令の挿入ロジックを追加することで、一時変数が不要になった時点で明示的にその生存期間を終了させ、ライブネス解析の精度を高めています。

コミット

commit b700cb4974c23a030775a311e6c60cf93b220a6f
Author: Russ Cox <rsc@golang.org>
Date:   Tue Apr 1 13:31:38 2014 -0400

    cmd/gc: shorten temporary lifetimes when possible

    The new channel and map runtime routines take pointers
    to values, typically temporaries. Without help, the compiler
    cannot tell when those temporaries stop being needed,
    because it isn't sure what happened to the pointer.
    Arrange to insert explicit VARKILL instructions for these
    temporaries so that the liveness analysis can avoid seeing
    them as "ambiguously live".

    The change is made in order.c, which was already in charge of
    introducing temporaries to preserve the order-of-evaluation
    guarantees. Now its job has expanded to include introducing
    temporaries as needed by runtime routines, and then also
    inserting the VARKILL annotations for all these temporaries,
    so that their lifetimes can be shortened.

    In order to do its job for the map runtime routines, order.c arranges
    that all map lookups or map assignments have the form:

            x = m[k]
            x, y = m[k]
            m[k] = x

    where x, y, and k are simple variables (often temporaries).
    Likewise, receiving from a channel is now always:

            x = <-c

    In order to provide the map guarantee, order.c is responsible for
    rewriting x op= y into x = x op y, so that m[k] += z becomes

            t = m[k]
            t2 = t + z
            m[k] = t2

    While here, fix a few bugs in order.c's traversal: it was failing to
    walk into select and switch case bodies, so order of evaluation
    guarantees were not preserved in those situations.
    Added tests to test/reorder2.go.

    Fixes #7671.

    In gc/popt's temporary-merging optimization, allow merging
    of temporaries with their address taken as long as the liveness
    ranges do not intersect. (There is a good chance of that now
    that we have VARKILL annotations to limit the liveness range.)

    Explicitly killing temporaries cuts the number of ambiguously
    live temporaries that must be zeroed in the godoc binary from
    860 to 711, or -17%. There is more work to be done, but this
    is a good checkpoint.

    Update #7345

    LGTM=khr
    R=khr
    CC=golang-codereviews
    https://golang.org/cl/81940043

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

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

元コミット内容

このコミットは、Goコンパイラ（cmd/gc）において、一時変数のライフタイムを可能な限り短縮することを目的としています。特に、新しいチャネルおよびマップのランタイムルーチンが値へのポインタ（通常は一時変数）を受け取る際に、コンパイラがその一時変数がいつ不要になるかを正確に判断できない問題に対処します。

主な変更点は以下の通りです。

• VARKILL命令の導入: コンパイラが一時変数の生存期間を正確に判断できるよう、明示的なVARKILL命令を挿入します。これにより、ライブネス解析が一時変数を「曖昧に生存している」と見なすことを防ぎます。
• order.cの役割拡張: order.c（評価順序の保証のために一時変数を導入する役割を担っていた部分）の機能が拡張され、ランタイムルーチンが必要とする一時変数を導入し、それらの一時変数に対してVARKILLアノテーションを挿入するようになりました。
• マップおよびチャネル操作の正規化: order.cは、マップのルックアップや代入、チャネルからの受信操作が特定の単純な形式（例: x = m[k], x = <-c）になるようにコードを書き換えます。
• 複合代入演算子（op=）の書き換え: x op= yのような複合代入演算子をx = x op yの形式に書き換えます。これにより、マップのインデックス式における読み取りと書き込みを分離し、最適化を容易にします。
• order.cのバグ修正: select文やswitch文のケースボディを正しくトラバースできていなかったバグが修正され、これらの状況での評価順序の保証が改善されました。
• 一時変数マージ最適化の改善: gc/poptにおける一時変数マージ最適化において、VARKILLアノテーションによって生存範囲が制限された一時変数であれば、アドレスが取られていてもマージを許可するようになりました。
• 効果: この変更により、godocバイナリにおける「曖昧に生存している」一時変数の数が860から711に削減され、約17%の改善が見られました。

変更の背景

このコミットの背景には、Goのガベージコレクション（GC）とコンパイラの最適化における課題がありました。

1. GCの効率化: GoのGCは、プログラムが使用しなくなったメモリを自動的に解放することで、メモリ管理の負担を軽減します。GCは「ライブネス解析」を用いて、どの変数がまだ使用されているかを判断します。しかし、チャネルやマップのような複雑なデータ構造のランタイムルーチンは、内部的に一時変数のアドレスを引数として受け取ることがあります。この場合、コンパイラは一時変数のポインタがランタイムに渡された後、いつその一時変数が不要になるかを正確に追跡することが困難でした。結果として、一時変数が実際には不要になった後も「曖昧に生存している」と見なされ、GCがそのメモリを解放できず、メモリ使用量が増加したり、GCのサイクルが長くなったりする可能性がありました。

2. コンパイラ最適化の制約: 一時変数のライフタイムが不必要に長く設定されると、コンパイラのレジスタ割り当てや他の最適化の機会が制限されます。特に、アドレスが取られた変数は、コンパイラがその生存期間を正確に把握するのが難しく、レジスタに割り当てることができない場合があります。

このコミットは、VARKILLという新しいメカニズムを導入することで、これらの問題を解決しようとしました。VARKILLは、一時変数が不要になったことをコンパイラに明示的に伝えることで、ライブネス解析の精度を向上させ、GCの効率を高め、コンパイラがより積極的な最適化を行えるようにします。

前提知識の解説

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

1. Goコンパイラの構造（cmd/gcとorder.c）:

   • Goコンパイラは、当初C言語で書かれており、cmd/gcというディレクトリにそのソースコードがありました。現在ではGo言語で書き直され、cmd/compileにその機能が移行しています。
   • order.cは、Goコンパイラの「walk」フェーズ（現在のcmd/compile/internal/walk）の一部でした。このフェーズの主な役割は、Goのソースコードから生成された抽象構文木（AST）を、より単純な中間表現に変換することです。具体的には、複雑な式や文を、評価順序を保証しつつ、より基本的な操作のシーケンスに「脱糖（desugar）」し、その過程で一時変数を導入します。

2. 一時変数（Temporary Variables）:

   • コンパイラは、複雑な式の中間結果を保持したり、評価順序を保証したりするために、一時変数を自動的に生成します。例えば、a + b * cのような式では、b * cの結果を一時変数に格納し、その一時変数とaを加算するといった処理が行われます。
   • これらの変数はソースコードには明示的に現れませんが、コンパイルされたバイナリの効率に大きく影響します。

3. ライブネス解析（Liveness Analysis）:

   • ライブネス解析は、コンパイラが実行するデータフロー解析の一種です。プログラムの各ポイントにおいて、どの変数が「ライブ（生きてる）」であるか、つまりその変数の現在の値が将来的に使用される可能性があるかを判断します。
   • この解析は、レジスタ割り当て（ライブな変数をCPUレジスタに割り当てる）、デッドコード削除（決して使用されないコードを削除する）、そしてGoにおいては特にエスケープ解析（変数をスタックに割り当てるかヒープに割り当てるかを決定する）に不可欠です。
   • 変数が「ライブ」であると判断されると、その変数が占めるメモリはGCによって解放されません。

4. addrtaken（アドレスが取られた変数）:

   • Goでは、変数のアドレスを&演算子で取得し、ポインタとして使用することができます。変数のアドレスが取られると、コンパイラはその変数がどこでどのように使用されるかを完全に追跡するのが難しくなります。
   • 特に、ランタイムルーチンにポインタが渡される場合、コンパイラはランタイム内部でのそのポインタの使用状況を把握できないため、変数の生存期間を正確に判断できず、不必要に長くライブであると見なしてしまうことがあります。

5. VARDEFとVARKILL:

   • VARDEF（Variable Define）は、コンパイラが変数が定義されたことを示すために挿入する命令です。これは、その変数がこの時点からライブになる可能性があることを示します。
   • VARKILL（Variable Kill）は、このコミットで導入された新しい概念です。これは、変数がこの時点から不要になることをコンパイラに明示的に伝える命令です。これにより、ライブネス解析は変数の生存期間をより正確に判断し、不要になった変数を早期にGCの対象とすることができます。特に、アドレスが取られた一時変数に対して有効です。

6. Goのマップとチャネルの内部動作:

   • Goのマップとチャネルは、ランタイムによって管理される複雑なデータ構造です。これらの操作（例: m[k] = v, <-c）は、コンパイラによってランタイム関数呼び出しに変換されます。
   • これらのランタイム関数は、キーや値、チャネル要素などの引数をポインタとして受け取ることが多く、その引数には一時変数が使われることがあります。

技術的詳細

このコミットの技術的な核心は、Goコンパイラのorder.c（現在のcmd/compile/internal/walk）における一時変数のライフタイム管理の改善と、VARKILL命令の導入にあります。

1. order.cの役割の拡張とVARKILLの導入:

   • 従来のorder.cは、式の評価順序を保証するために一時変数を導入していました。例えば、f(g(), h())のような呼び出しでは、g()とh()の評価結果を一時変数に格納し、その一時変数を使ってfを呼び出す、といった変換を行います。
   • このコミットでは、order.cの役割が拡張され、チャネルやマップのランタイムルーチンが必要とする一時変数を導入するようになりました。さらに重要なのは、これらの導入された一時変数に対して、不要になった時点で明示的にVARKILLアノテーションを挿入するようになった点です。
   • VARKILLは、コンパイラのライブネス解析に対して、その変数がこの時点以降は「死んでいる（dead）」、つまりその値が将来的に使用されることはない、と伝えます。これにより、たとえその一時変数のアドレスがランタイムに渡されていたとしても、コンパイラはより正確にその生存期間を判断し、GCがそのメモリを早期に解放できるようになります。

2. マップおよびチャネル操作の正規化:

   • order.cは、マップのルックアップや代入、チャネルからの受信操作を特定の単純な形式に書き換えるようになりました。
     • マップ操作: x = m[k], x, y = m[k], m[k] = x の形式に正規化されます。ここで、x, y, k は単純な変数（多くは一時変数）です。
     • チャネル受信: x = <-c の形式に正規化されます。
   • この正規化により、コンパイラはこれらの操作をより予測可能な方法で処理できるようになり、VARKILLの挿入やその他の最適化が容易になります。

3. 複合代入演算子（OASOP）の書き換え:

   • x op= y（例: m[k] += z）のような複合代入演算子は、order.cによってx = x op yの形式に書き換えられます。
   • 例えば、m[k] += zは以下のように変換されます。

     t = m[k]  // マップから値を読み込み、一時変数tに格納
     t2 = t + z // tとzを加算し、一時変数t2に格納
     m[k] = t2 // t2の値をマップに書き込む
     

   • この書き換えは、マップの読み取りと書き込みを明確に分離し、特にマップのキーや値が複雑な式である場合に、評価順序の保証と一時変数の管理を簡素化します。

4. ライブネス解析と一時変数マージの改善:

   • VARKILLアノテーションの導入により、一時変数のライブネス範囲がより正確に限定されるようになりました。
   • gc/popt（コンパイラの最適化フェーズの一つ）における一時変数マージ最適化では、アドレスが取られた一時変数であっても、そのライブネス範囲が重複しない限りマージが許可されるようになりました。これは、VARKILLによって一時変数の生存期間が短縮されたことで、マージの機会が増えたためです。
   • 結果として、godocバイナリにおける「曖昧に生存している」一時変数の数が削減され、メモリ効率が向上しました。

5. selectおよびswitch文のトラバーサル修正:

   • order.cがselectおよびswitch文のケースボディを正しくトラバースできていなかったバグが修正されました。これにより、これらの制御構造内での評価順序の保証が適切に行われるようになりました。

これらの変更は、Goコンパイラが生成するコードの効率性を高め、特にGCのパフォーマンスに寄与するものです。

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

このコミットにおけるコアとなるコードの変更は、主に以下のファイルに集中しています。

• src/cmd/gc/order.c: このコミットの主要な変更が行われたファイルです。一時変数の導入、VARKILL命令の挿入、マップ/チャネル操作の正規化、複合代入演算子の書き換えなど、評価順序の保証と一時変数のライフタイム管理に関するロジックが大幅に修正・拡張されています。
  • Order構造体の導入: 評価順序処理中の状態（生成された文のリスト、一時変数のスタックなど）を管理するための構造体。
  • ordertemp, ordercopyexpr: 新しい一時変数を割り当て、必要に応じて初期化する関数。
  • isaddrokay: 変数のアドレスをランタイムルーチンに渡しても安全かどうかを判断する関数。一時変数であれば安全と見なされます。
  • cleantemp, cleantempnopop: 一時変数のスタックをクリーンアップし、OVARKILL命令を挿入する関数。
  • orderstmt, orderexpr: 文や式の評価順序を処理する主要な関数。これらの関数内で、VARKILLの挿入や式の書き換えが行われます。特に、OASOP（複合代入）の処理がOAS（単純代入）に書き換えられるロジックが追加されています。
  • ordermapassign: マップへの代入を処理し、必要に応じて一時変数を導入する関数。
• src/cmd/gc/pgen.c: gvardef関数がgvardefxにリファクタリングされ、AVARDEFとAVARKILLの両方を処理できるようになりました。また、gvarkill関数が新しく追加され、OVARKILLノードに対応する命令を生成します。
• src/cmd/gc/plive.c: ライブネス解析のロジックが修正され、AVARKILL命令を考慮に入れるようになりました。これにより、VARKILLによってマークされた一時変数が、不要になった時点で正しく「死んでいる」と判断されるようになります。
• src/cmd/gc/popt.c: 一時変数のマージ最適化に関するロジックが修正されました。VARKILLアノテーションの導入により、アドレスが取られた一時変数であっても、ライブネス範囲が重複しない場合にマージを許可するようになりました。
• src/cmd/gc/go.h: OVARKILLという新しいノードタイプと、gvarkill関数のプロトタイプが追加されています。
• src/cmd/gc/gen.c: OVARKILLノードを処理するためのgvarkill呼び出しが追加されています。
• src/cmd/gc/walk.c: OAS（代入）やOAS2RECV（チャネルからの複数値受信）などの処理が変更され、order.cによって導入された一時変数やVARKILLのロジックと連携するようになりました。特に、マップ操作やチャネル受信操作における一時変数のアドレス可能性の扱いが変更されています。
• test/live.go, test/reorder2.go: 新しいテストケースが追加され、このコミットで導入された一時変数のライフタイム短縮と評価順序の保証が正しく機能するかを検証しています。

これらのファイルは、Goコンパイラのフロントエンド（ASTの構築と初期変換）、中間表現の最適化、およびコード生成の各フェーズにまたがっており、一時変数のライフタイム管理がコンパイラの多くの側面に影響を与えることを示しています。

コアとなるコードの解説

ここでは、特に重要なsrc/cmd/gc/order.cの変更点に焦点を当てて解説します。

Order構造体と一時変数管理

// Order holds state during the ordering process.
typedef struct Order Order;
struct Order
{
	NodeList *out; // list of generated statements
	NodeList *temp; // head of stack of temporary variables
	NodeList *free; // free list of NodeList* structs (for use in temp)
};

// Ordertemp allocates a new temporary with the given type,
// pushes it onto the temp stack, and returns it.
// If clear is true, ordertemp emits code to zero the temporary.
static Node*
ordertemp(Type *t, Order *order, int clear)
{
	Node *var, *a;
	NodeList *l;

	var = temp(t); // 新しい一時変数を生成
	if(clear) {
		a = nod(OAS, var, N); // ゼロ初期化の代入ノードを生成
		typecheck(&a, Etop);
		order->out = list(order->out, a); // 生成された文リストに追加
	}
	// 一時変数スタックにプッシュ
	if((l = order->free) == nil)
		l = mal(sizeof *l);
	order->free = l->next;
	l->next = order->temp;
	l->n = var;
	order->temp = l;
	return var;
}

// Ordercopyexpr behaves like ordertemp but also emits
// code to initialize the temporary to the value n.
static Node*
ordercopyexpr(Node *n, Type *t, Order *order, int clear)
{
	Node *a, *var;

	var = ordertemp(t, order, clear); // 一時変数を生成
	a = nod(OAS, var, n); // nの値を一時変数に代入するノードを生成
	typecheck(&a, Etop);
	order->out = list(order->out, a); // 生成された文リストに追加
	return var;
}

// Cleantemp emits VARKILL instructions for each temporary above the
// mark on the temporary stack and removes them from the stack.
static void
cleantemp(NodeList *top, Order *order)
{
	NodeList *l;
	Node *kill;

	for(l=order->temp; l != top; l=l->next) {
		kill = nod(OVARKILL, l->n, N); // OVARKILLノードを生成
		typecheck(&kill, Etop);
		order->out = list(order->out, kill); // 生成された文リストに追加
	}
	poptemp(top, order); // 一時変数スタックからポップ
}

• Order構造体は、order.cの処理中に生成される文のリスト（out）、現在アクティブな一時変数のスタック（temp）、および再利用可能なNodeList要素のフリーリスト（free）を保持します。
• ordertempは、新しい一時変数を割り当て、必要に応じてゼロ初期化のコードを生成し、その一時変数をorder構造体の一時変数スタックにプッシュします。
• ordercopyexprはordertempと同様に一時変数を割り当てますが、さらに指定されたノードnの値をその一時変数にコピーする代入文を生成します。
• cleantempは、指定されたマーク（top）よりも上位にあるすべての一時変数に対してOVARKILLノードを生成し、それをorder->outリストに追加します。これにより、これらの変数が不要になったことをコンパイラに明示的に伝えます。その後、一時変数スタックからそれらをポップします。

OASOP（複合代入）の書き換え

// src/cmd/gc/order.c 内の orderstmt 関数の一部
case OASOP:
	// Special: rewrite l op= r into l = l op r.
	// This simplies quite a few operations;
	// most important is that it lets us separate
	// out map read from map write when l is
	// a map index expression.
	t = marktemp(order); // 一時変数スタックのマークを設定
	orderexpr(&n->left, order); // 左辺を評価
	orderexpr(&n->right, order); // 右辺を評価
	n->left = ordersafeexpr(n->left, order); // 左辺を安全な形式に変換
	tmp1 = treecopy(n->left); // 左辺のコピーを作成
	if(tmp1->op == OINDEXMAP)
		tmp1->etype = 0; // now an rvalue not an lvalue
	tmp1 = ordercopyexpr(tmp1, n->left->type, order, 0); // コピーを一時変数に格納
	n->right = nod(n->etype, tmp1, n->right); // 新しい右辺 (tmp1 op n->right) を構築
	typecheck(&n->right, Erv);
	n->etype = 0;
	n->op = OAS; // 複合代入を単純代入に変換
	ordermapassign(n, order); // マップ代入を処理
	cleantemp(t, order); // 一時変数をクリーンアップ
	break;

• OASOPは+=, -=, *=などの複合代入演算子を表します。
• このコードは、l op= rという形式の複合代入を、l = l op rという形式の単純代入に書き換えます。
• 特にマップのインデックス式（例: m[k] += z）の場合、この書き換えにより、マップからの読み取り（t = m[k]）とマップへの書き込み（m[k] = t2）が明確に分離され、コンパイラがそれぞれの操作を個別に最適化できるようになります。
• ordersafeexprは、左辺が複数回評価されても問題ないように、必要に応じて一時変数にコピーします。

マップ操作とチャネル受信の正規化

order.c内のorderstmt関数やorderexpr関数では、OINDEXMAP（マップインデックス）やORECV（チャネル受信）などの操作が特別に処理され、ランタイムルーチンに渡す引数（キーや受信値）がアドレス可能であることを保証するために、必要に応じて一時変数が導入されます。

// src/cmd/gc/order.c 内の orderexpr 関数の一部
case OINDEXMAP:
	// key must be addressable
	orderexpr(&n->left, order);
	orderexpr(&n->right, order);
	orderaddrtemp(&n->right, order); // キーがアドレス可能であることを保証
	if(n->etype == 0) {
		// use of value (not being assigned);
		// make copy in temporary.
		n = ordercopyexpr(n, n->type, order, 0); // 値の使用の場合、一時変数にコピー
	}
	break;

// src/cmd/gc/order.c 内の orderstmt 関数の一部
case OAS2RECV:
	// Special: avoid copy of receive.
	// Use temporary variables to hold result,
	// so that chanrecv can take address of temporary.
	t = marktemp(order);
	orderexprlist(n->list, order);
	orderexpr(&n->rlist->n->left, order);  // arg to recv
	ch = n->rlist->n->left->type;
	tmp1 = ordertemp(ch->type, order, haspointers(ch->type)); // 受信値用の一時変数
	tmp2 = ordertemp(types[TBOOL], order, 0); // ok値用の一時変数
	order->out = list(order->out, n);
	r = nod(OAS, n->list->n, tmp1);
	typecheck(&r, Etop);
	ordermapassign(r, order);
	r = nod(OAS, n->list->next->n, tmp2);
	typecheck(&r, Etop);
	ordermapassign(r, order);
	n->list = list(list1(tmp1), tmp2);
	cleantemp(t, order);
	break;

• orderaddrtemp関数は、引数として渡されたノードがアドレス可能でない場合、そのノードの値を一時変数にコピーし、その一時変数を元のノードの代わりに設定します。これにより、ランタイムルーチンがポインタを受け取る際に、常に有効なアドレスが提供されるようになります。
• OAS2RECV（x, ok = <-cのような複数値受信）の場合、受信した値とokフラグを保持するための一時変数が導入され、ランタイム関数がこれらの変数へのポインタを受け取れるようにします。

これらの変更は、Goコンパイラが一時変数をより細かく制御し、そのライフタイムを正確に管理することで、生成されるコードの効率とGCのパフォーマンスを向上させるための重要なステップです。

関連リンク

• Go Compiler Design: https://go.dev/doc/compiler
• Go Garbage Collection: https://go.dev/doc/gc-guide
• Go Escape Analysis: https://go.dev/blog/escape-analysis

参考にした情報源リンク

• Go compiler liveness analysis - Google Search
• Go compiler order.c - Google Search
• Go compiler VARKILL - Google Search
• Go runtime channel implementation details - Google Search
• Go runtime map implementation details - Google Search
• Go compiler temporary variables - Google Search
• Go compiler garbage collection liveness - Google Search
• Go compiler OASOP rewrite - Google Search