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

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

このコミットは、Goコンパイラ（cmd/gc）における一時変数のライフタイム管理を改善し、コンパイラが誤って「生存している」と判断してしまう変数（ambiguously live variables）の数を削減することを目的としています。これにより、生成されるバイナリのサイズ削減や、デバッグ情報の精度向上に寄与します。特に、godocバイナリにおける「ambiguously live variables」の数を大幅に削減することに成功しています。

コミット

daca06f2e35035ea2c9d508f9f52a23baa406885

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

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

元コミット内容

cmd/gc: shorten more temporary lifetimes

1. In functions with heap-allocated result variables or with
defer statements, the return sequence requires more than
just a single RET instruction. There is an optimization that
arranges for all returns to jump to a single copy of the return
epilogue in this case. Unfortunately, that optimization is
fundamentally incompatible with PC-based liveness information:
it takes PCs at many different points in the function and makes
them all land at one PC, making the combined liveness information
at that target PC a mess. Disable this optimization, so that each
return site gets its own copy of the 'call deferreturn' and the
copying of result variables back from the heap.
This removes quite a few spurious 'ambiguously live' variables.

2. Let orderexpr allocate temporaries that are passed by address
to a function call and then die on return, so that we can arrange
an appropriate VARKILL.

2a. Do this for ... slices.

2b. Do this for closure structs.

2c. Do this for runtime.concatstring, which is the implementation
of large string additions. Change representation of OADDSTR to
an explicit list in typecheck to avoid reconstructing list in both
walk and order.

3. Let orderexpr allocate the temporary variable copies used for
range loops, so that they can be killed when the loop is over.
Similarly, let it allocate the temporary holding the map iterator.

CL 81940043 reduced the number of ambiguously live temps
in the godoc binary from 860 to 711.

This CL reduces the number to 121. Still more to do, but another
good checkpoint.

Update #7345

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

変更の背景

Goコンパイラは、プログラムの実行中にどの変数が「生存している（live）」かを追跡する「ライブネス情報（liveness information）」を生成します。この情報は、ガベージコレクション（GC）が不要なメモリを解放するために不可欠です。しかし、コンパイラが変数を必要以上に長く生存していると誤って判断してしまう「ambiguously live variables」という問題が存在していました。これは、実際にはもう使用されない一時変数などが、コンパイラの認識上はまだ参照されている状態にあることを意味します。

このような「ambiguously live variables」は、以下のような悪影響を及ぼします。

  1. メモリ使用量の増加: 不要な変数がGCによって解放されず、メモリを占有し続けるため、プログラムのメモリフットプリントが増大します。
  2. バイナリサイズの肥大化: 特にデバッグ情報やGCメタデータに影響し、最終的な実行可能ファイルのサイズが大きくなる可能性があります。
  3. パフォーマンスの低下: GCがより多くのメモリをスキャンする必要があるため、GCの実行時間が長くなり、プログラム全体のパフォーマンスに影響を与える可能性があります。

このコミットは、以前の変更（CL 81940043）に続くもので、godocバイナリにおける「ambiguously live variables」の数を860から711に削減した実績があります。今回の変更により、さらにその数を121まで大幅に削減することを目指しています。これは、Goプログラムの効率性とパフォーマンスを向上させるための重要なステップです。

前提知識の解説

このコミットを理解するためには、以下のGoコンパイラおよびランタイムに関する概念の理解が不可欠です。

  • ライブネス情報 (Liveness Information):

    • プログラムの特定の時点において、どの変数が将来的に使用される可能性があるか（すなわち「生存している」か）を示す情報です。
    • Goのガベージコレクタは、このライブネス情報に基づいて、どのメモリ領域がまだ参照されており解放できないかを判断します。
    • コンパイラは、各プログラムカウンタ（PC）に対応するライブネス情報を生成します。

  • PCベースのライブネス情報 (PC-based Liveness Information):

    • プログラムカウンタ（PC）は、現在実行されている命令のアドレスを示します。
    • PCベースのライブネス情報は、特定のPC値においてどの変数がライブであるかをマッピングしたものです。これにより、GCは正確なタイミングで不要なメモリを特定し、解放できます。

  • 一時変数 (Temporary Variables):

    • コンパイラがコード生成の過程で内部的に作成する変数です。これらはソースコードには直接現れませんが、計算の中間結果や関数の引数渡しなどに使用されます。
    • 例えば、a + b + cのような式では、a + bの結果を保持するための一時変数が生成されることがあります。

  • defer文:

    • Goのdefer文は、関数がリターンする直前に実行される関数呼び出しをスケジュールします。
    • deferが使用される関数では、通常のRET命令だけでなく、defer呼び出しを処理するための追加のコード（リターンエピローグ）が必要になります。

  • ヒープ割り当てされた結果変数 (Heap-allocated Result Variables):

    • Goの関数は、複数の戻り値を返すことができます。場合によっては、これらの戻り値がスタックではなくヒープに割り当てられることがあります（エスケープ解析の結果など）。
    • ヒープに割り当てられた戻り変数は、関数がリターンする際に適切に処理される必要があります。

  • エスケープ解析 (Escape Analysis):

    • コンパイラが行う最適化の一つで、変数がスタックに割り当てられるべきか、それともヒープに割り当てられるべきかを決定します。
    • 変数が関数のスコープ外で参照される可能性がある場合（「エスケープする」と呼ばれる）、その変数はヒープに割り当てられます。

  • orderexpr:

    • Goコンパイラのgc（Go Compiler）フェーズの一部で、式の評価順序を決定し、必要に応じて一時変数を導入する役割を担います。
    • コードのセマンティクスを維持しつつ、効率的なコード生成のための準備を行います。

  • VARKILL:

    • コンパイラが生成する命令の一つで、特定の変数がその時点以降は不要になることを示します。
    • これにより、GCはより早くその変数が占有していたメモリを解放できるようになります。

  • ... スライス (Variadic Slices):

    • Goの可変長引数（func foo(args ...int)）は、内部的にはスライスとして扱われます。
    • 関数呼び出し時に、渡された引数がこのスライスにパックされます。

  • クロージャ (Closures):

    • Goのクロージャは、それが定義された環境の変数を「キャプチャ」する関数です。
    • キャプチャされた変数は、クロージャが実行される間、生存している必要があります。クロージャ自体も、多くの場合ヒープに割り当てられます。

  • runtime.concatstring:

    • Goの文字列結合（s1 + s2 + s3など）は、コンパイラによってruntime.concatstring（またはそのバリアント）というランタイム関数呼び出しに変換されます。
    • 特に多数の文字列を結合する場合、効率的なメモリ管理が求められます。

  • OADDSTR:

    • Goコンパイラの内部表現（ASTノード）の一つで、文字列結合操作を表します。

  • レンジループ (Range Loops):

    • for ... range構文は、スライス、配列、文字列、マップ、チャネルなどのコレクションをイテレートするために使用されます。
    • イテレーションの過程で、コレクションのコピーやイテレータのための一時変数が生成されることがあります。

  • マップイテレータ (Map Iterators):

    • マップのレンジループでは、マップの要素を順に処理するための内部的なイテレータが使用されます。このイテレータも一時変数として扱われます。

技術的詳細

このコミットは、主に3つの主要な変更点と、それに付随するいくつかの改善から構成されています。

1. リターンエピローグの最適化の無効化

問題点: Goコンパイラには、defer文を持つ関数やヒープ割り当てされた戻り変数を持つ関数において、複数のreturn文が単一の「リターンエピローグ」と呼ばれる共通のコードブロックにジャンプするようにする最適化がありました。この最適化は、コードサイズを削減する効果がありましたが、PCベースのライブネス情報との互換性に根本的な問題がありました。

ライブネス情報は、特定のPC（プログラムカウンタ）においてどの変数が生存しているかを正確に把握する必要があります。しかし、この最適化では、関数の様々な異なるPCから共通のリターンエピローグの単一のPCにジャンプするため、そのターゲットPCにおけるライブネス情報が「曖昧（mess）」になっていました。つまり、コンパイラは、実際にはもう不要な変数であっても、その共通エピローグに到達する可能性のあるすべてのパスで生存していると判断せざるを得なくなり、結果として「ambiguously live variables」が生成されていました。

解決策: このコミットでは、この最適化を無効にします。これにより、各returnサイトは、deferreturnの呼び出しやヒープからの戻り変数のコピーなど、独自のリターンシーケンスを持つようになります。

技術的影響:

  • src/cmd/5g/ggen.c, src/cmd/6g/ggen.c, src/cmd/8g/ggen.c (各アーキテクチャのコードジェネレータ) のginscall関数において、リターンパスの分岐ロジックが変更され、共通のretpcへのジャンプではなく、cgen_ret(N)が直接呼び出されるようになりました。
  • src/cmd/gc/pgen.cのcompile関数から、共通のretpcを管理するロジックが削除されました。これにより、各リターンパスが独立して処理されるようになります。
  • src/cmd/gc/go.hからretpcの宣言が削除されました。

この変更により、コンパイラは各リターンサイトでより正確なライブネス情報を生成できるようになり、結果として「ambiguously live variables」の数が減少します。

2. orderexprによる一時変数の割り当て改善

orderexprは、式の評価順序を決定し、必要に応じて一時変数を導入するコンパイラパスです。このコミットでは、特定のシナリオで一時変数が適切に割り当てられ、関数呼び出しから戻った際にVARKILL（変数の破棄）が可能になるように改善されました。

2a. ... スライス (Variadic Slices): 可変長引数（...）は、内部的にスライスとして扱われます。関数に可変長引数を渡す際、コンパイラはこれらの引数を一時的なスライスにパックします。以前は、この一時スライスのライフタイムが適切に管理されておらず、関数呼び出し後も「ambiguously live」と判断される可能性がありました。 解決策: orderexprがこの一時スライスを割り当てる際に、関数呼び出しから戻った時点で破棄できるよう、適切なVARKILLを生成できるようにします。 技術的影響: src/cmd/gc/esc.cのesccall関数において、ODDDARGノード（可変長引数を表す）がnoescapeとマークされ、orderexprが一時変数を割り当てられるようになりました。src/cmd/gc/walk.cのmkdotargslice関数も、dddノード（可変長引数）のesc情報を使用するように変更されました。

2b. クロージャ構造体 (Closure Structs): Goのクロージャは、外部スコープの変数をキャプチャするために内部的に構造体として表現されます。このクロージャ構造体も一時変数として扱われることがありますが、そのライフタイムが適切に管理されていないと、「ambiguously live」となる原因となっていました。 解決策: orderexprがクロージャ構造体のための一時変数を割り当てる際に、関数呼び出しから戻った時点で破棄できるよう、適切なVARKILLを生成できるようにします。 技術的影響: src/cmd/gc/closure.cのwalkclosure関数において、クロージャの一時変数がfunc->leftに設定され、orderexprがこれを処理できるようになりました。src/cmd/gc/order.cのorderexpr関数でOCLOSUREノードがnoescapeの場合に一時変数を割り当てるロジックが追加されました。

2c. runtime.concatstring (文字列結合): Goの文字列結合（s1 + s2 + s3など）は、内部的にruntime.concatstring（またはconcatstrings）というランタイム関数呼び出しに変換されます。特に多数の文字列を結合する場合、結合結果を保持するための一時的な文字列が生成されます。 問題点: 以前は、OADDSTR（文字列結合を表すASTノード）の内部表現が、walkパスとorderパスの両方でリストを再構築する必要があるような形になっていました。これにより、一時変数のライフタイム管理が複雑になっていました。 解決策: typecheckパスでOADDSTRの表現を明示的な文字列のリストに変更します。これにより、walkパスとorderパスでリストを再構築する必要がなくなり、一時変数のライフタイム管理が容易になります。また、orderexprがruntime.concatstringに渡される文字列を保持するための一時変数を割り当てられるようにします。 技術的影響:

  • src/cmd/gc/const.cとsrc/cmd/gc/fmt.cからOADDSTRが削除され、OADDSTRがNodeListを持つように変更されました。これにより、文字列結合の引数がリストとして直接扱われるようになります。
  • src/cmd/gc/typecheck.cのtypecheck関数で、OADDが文字列結合の場合にOADDSTRノードを生成し、そのlistフィールドに結合される文字列のリストを設定するロジックが追加されました。
  • src/cmd/gc/walk.cのaddstr関数が、OADDSTRのlistフィールドから文字列引数を取得するように変更されました。
  • src/cmd/gc/order.cのorderexpr関数で、OADDSTRノードが5つ以上の文字列を結合する場合に、文字列の配列を保持するための一時変数を割り当てるロジックが追加されました。

3. レンジループとマップイテレータの一時変数管理

問題点: for ... rangeループやマップのイテレーションでは、ループ変数やイテレータ自体を保持するための一時変数が生成されます。これらの変数がループ終了後も「ambiguously live」と判断されることがありました。

解決策: orderexprが、レンジループで使用される一時的なコピー（配列、チャネル、文字列、スライスなど）や、マップイテレータを保持するための一時変数を割り当てられるようにします。これにより、ループが終了した時点でこれらの変数を適切に破棄（VARKILL）できるようになります。

技術的影響:

  • src/cmd/gc/order.cのorderstmt関数において、ORANGE（レンジループ）の処理が大幅に修正されました。レンジ対象の式をorderexprで処理した後、必要に応じてそのコピーを作成し、一時変数に割り当てるロジックが追加されました。特にマップのレンジループでは、イテレータ自体を一時変数として割り当てるようになりました。
  • src/cmd/gc/range.cのwalkrange関数も、orderstmtが一時変数を割り当てるようになった変更に合わせて修正されました。例えば、マップイテレータはn->leftから取得されるようになり、temp関数で新たに割り当てる必要がなくなりました。

これらの変更により、Goコンパイラは一時変数のライフタイムをより正確に管理できるようになり、結果として「ambiguously live variables」の数を大幅に削減し、生成されるバイナリの効率性を向上させます。

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

このコミットは、Goコンパイラの複数のコンポーネントにわたる広範な変更を含んでいます。主要な変更箇所は以下の通りです。

  • src/cmd/5g/ggen.c, src/cmd/6g/ggen.c, src/cmd/8g/ggen.c: 各アーキテクチャ（ARM, x86, AMD64）のコードジェネレータ。リターンエピローグの最適化を無効にするための変更が含まれます。
  • src/cmd/gc/closure.c: クロージャの処理に関連するファイル。クロージャ構造体の一時変数割り当ての改善。
  • src/cmd/gc/const.c: 定数評価に関連するファイル。OADDSTRの定数結合ロジックの変更。
  • src/cmd/gc/esc.c: エスケープ解析に関連するファイル。...スライスやクロージャの一時変数がエスケープしないことを示すロジックの追加。
  • src/cmd/gc/fmt.c: ASTノードのフォーマット（デバッグ出力など）に関連するファイル。OADDSTRの表示方法の変更。
  • src/cmd/gc/go.h: コンパイラのグローバルヘッダファイル。retpc変数の削除。
  • src/cmd/gc/order.c: orderexprパスの実装。一時変数のライフタイム管理に関する最も重要な変更が集中しています。特に、ordercall, orderstmt, orderexpr関数が影響を受けています。
  • src/cmd/gc/pgen.c: プログラム全体のコード生成に関連するファイル。リターンエピローグの最適化無効化に伴う変更。
  • src/cmd/gc/range.c: for ... rangeループの処理に関連するファイル。レンジループの一時変数管理の改善。
  • src/cmd/gc/sinit.c: スライスや複合リテラルの初期化に関連するファイル。一時変数の割り当てロジックの調整。
  • src/cmd/gc/typecheck.c: 型チェックに関連するファイル。OADDSTRの内部表現の変更。
  • src/cmd/gc/walk.c: ASTのウォーク（走査）に関連するファイル。OADDSTRの処理や...スライスの生成ロジックの変更。
  • test/live.go: ライブネス解析のテストケース。このコミットで修正された問題が再現しないことを確認するための新しいテストが追加されています。

コアとなるコードの解説

src/cmd/gc/order.c の変更

このファイルは、一時変数のライフタイム管理において最も重要な変更が行われた箇所です。

ordercall 関数の変更

--- a/src/cmd/gc/order.c
+++ b/src/cmd/gc/order.c
@@ -417,10 +417,12 @@ ordercallargs(NodeList **l, Order *order)
 // Ordercall orders the call expression n.
 // n->op is  OCALLMETH/OCALLFUNC/OCALLINTER.
 static void
-ordercall(Node *n, Order *order)
+ordercall(Node *n, Order *order, int special)
 {
 	orderexpr(&n->left, order);
 	ordercallargs(&n->list, order);
+	if(!special)
+		orderexpr(&n->right, order); // ODDDARG temp
 }

ordercall関数にspecial引数が追加されました。specialがfalseの場合、n->right（可変長引数の一時変数ODDDARGなど）もorderexprで処理されるようになりました。これにより、関数呼び出しに渡される一時変数のライフタイムが適切に管理されます。

orderstmt 関数の ORANGE 処理の変更

--- a/src/cmd/gc/order.c
+++ b/src/cmd/gc/order.c
@@ -682,12 +684,53 @@ orderstmt(Node *n, Order *order)
 	case ORANGE:
-		// TODO(rsc): Clean temporaries.
+		// n->right is the expression being ranged over.
+		// order it, and then make a copy if we need one.
+		// We almost always do, to ensure that we don't
+		// see any value changes made during the loop.
+		// Usually the copy is cheap (e.g., array pointer, chan, slice, string are all tiny).
+		// The exception is ranging over an array value (not a slice, not a pointer to array),
+		// which must make a copy to avoid seeing updates made during
+		// the range body. Ranging over an array value is uncommon though.
+		t = marktemp(order);
 		orderexpr(&n->right, order);
+		switch(n->type->etype) {
+		default:
+			fatal("orderstmt range %T", n->type);
+		case TARRAY:
+			if(count(n->list) < 2 || isblank(n->list->next->n)) {
+				// for i := range x will only use x once, to compute len(x).
+				// No need to copy it.
+				break;
+			}
+			// fall through
+		case TCHAN:
+		case TSTRING:
+			// chan, string, slice, array ranges use value multiple times.
+			// make copy.
+			r = n->right;
+			if(r->type->etype == TSTRING && r->type != types[TSTRING]) {
+				r = nod(OCONV, r, N);
+				r->type = types[TSTRING];
+				typecheck(&r, Erv);
+			}
+			n->right = ordercopyexpr(r, r->type, order, 0);
+			break;
+		case TMAP:
+			// copy the map value in case it is a map literal.
+			// TODO(rsc): Make tmp = literal expressions reuse tmp.
+			// For maps tmp is just one word so it hardly matters.
+			r = n->right;
+			n->right = ordercopyexpr(r, r->type, order, 0);
+			// temp is the iterator instead of the map value.
+			n->left = ordertemp(hiter(n->right->type), order, 1);
+			break;
+		}
 		for(l=n->list; l; l=l->next)
 			orderexprinplace(&l->n, order);
 		orderblock(&n->nbody);
 		order->out = list(order->out, n);
+		cleantemp(t, order);
 		break;

ORANGE（レンジループ）の処理が大幅に拡張されました。

  • t = marktemp(order)とcleantemp(t, order)が追加され、レンジループ全体で一時変数のスコープが管理されるようになりました。
  • レンジ対象の型（配列、チャネル、文字列、マップ）に応じて、一時的なコピーを作成するかどうかのロジックが追加されました。特に、マップのレンジループでは、イテレータ自体を保持するための一時変数（n->left = ordertemp(...)）が割り当てられるようになりました。これにより、ループ終了時にこれらの変数を適切に破棄できるようになります。

orderexpr 関数の OADDSTR, OCLOSURE, ODDDARG 処理の変更

--- a/src/cmd/gc/order.c
+++ b/src/cmd/gc/order.c
@@ -786,6 +830,19 @@ orderexpr(Node **np, Order *order)
 		orderexprlist(n->rlist, order);
 		break;
 	
+	case OADDSTR:
+		// Addition of strings turns into a function call.
+		// Allocate a temporary to hold the strings.
+		// Fewer than 5 strings use direct runtime helpers.
+		orderexprlist(n->list, order);
+		if(count(n->list) > 5) {
+			t = typ(TARRAY);
+			t->bound = count(n->list);
+			t->type = types[TSTRING];
+			n->left = ordertemp(t, order, 0);
+		}
+		break;
+
 	case OINDEXMAP:
 		// key must be addressable
 		orderexpr(&n->left, order);
@@ -809,10 +866,29 @@ orderexpr(Node **np, Order *order)
 	case OCALLINTER:
 	case OAPPEND:\n 	case OCOMPLEX:
-		ordercall(n, order);
+		ordercall(n, order, 0);
 		n = ordercopyexpr(n, n->type, order, 0);
 		break;
 
+	case OCLOSURE:
+		if(n->noescape && n->cvars != nil) {
+			t = typ(TARRAY);
+			t->type = types[TUNSAFEPTR];
+			t->bound = 1+count(n->cvars);
+			n->left = ordertemp(t, order, 0);
+		}
+		break;
+	
+	case ODDDARG:
+		if(n->noescape) {
+			// The ddd argument does not live beyond the call it is created for.
+			// Allocate a temporary that will be cleaned up when this statement
+			// completes. We could be more aggressive and try to arrange for it
+			// to be cleaned up when the call completes.
+			n->left = ordertemp(n->type, order, 0);
+		}
+		break;
+
 	case ORECV:
 		n = ordercopyexpr(n, n->type, order, 1);
 		break;
  • OADDSTR: 5つ以上の文字列を結合する場合、文字列の配列を保持するための一時変数を割り当てるようになりました。これにより、runtime.concatstringsへの引数渡しが効率化され、一時変数のライフタイムが管理されます。
  • OCLOSURE: クロージャがエスケープしない場合（n->noescape）、キャプチャされた変数を保持するための一時配列を割り当てるようになりました。
  • ODDDARG: 可変長引数（...スライス）がエスケープしない場合、その一時変数を割り当てるようになりました。これにより、関数呼び出し後すぐに破棄できるようになります。

src/cmd/gc/typecheck.c の変更

--- a/src/cmd/gc/typecheck.c
+++ b/src/cmd/gc/typecheck.c
@@ -654,8 +654,20 @@ reswitch:
 		if(et == TSTRING) {
 			if(iscmp[n->op]) {
 				n->etype = n->op;
 				n->op = OCMPSTR;
-			} else if(n->op == OADD)
+			} else if(n->op == OADD) {
+				// create OADDSTR node with list of strings in x + y + z + (w + v) + ...
 				n->op = OADDSTR;
+				if(l->op == OADDSTR)
+					n->list = l->list;
+				else
+					n->list = list1(l);
+				if(r->op == OADDSTR)
+					n->list = concat(n->list, r->list);
+				else
+					n->list = list(n->list, r);
+				n->left = N;
+				n->right = N;
+			}
 		}
 		if(et == TINTER) {
 			if(l->op == OLITERAL && l->val.ctype == CTNIL) {

typecheck関数において、文字列のOADD（結合）操作がOADDSTRノードに変換される際に、結合される文字列のリストをn->listに明示的に格納するようになりました。これにより、OADDSTRの内部表現がより構造化され、後続のコンパイラパス（walkやorder）での処理が簡素化されます。以前はn->leftとn->rightでツリー構造を表現していましたが、これをフラットなリストにすることで、文字列結合の引数を一貫して扱えるようになります。

test/live.go の追加テスト

このコミットでは、新しいテストケースf25からf30が追加されています。これらのテストは、defer文、可変長引数スライス、クロージャ、文字列結合、レンジループ、マップイテレータなど、このコミットで改善された一時変数のライフタイム管理が正しく機能していることを検証します。

例えば、f25はdeferが「ambiguously live variables」を引き起こさないことをテストし、f26は可変長引数スライスの一時変数が関数呼び出し後に適切に破棄されることをテストしています。これらのテストは、コンパイラのライブネス解析の精度が向上したことを確認するための重要な役割を果たします。

関連リンク

  • Go CL 83090046: https://golang.org/cl/83090046
  • Go Issue #7345: (公開されているGoリポジトリのIssueトラッカーでは直接見つかりませんでしたが、コミットメッセージの文脈から、一時変数のライフタイムとライブネス解析の改善に関する内部的な追跡番号であると考えられます。)

参考にした情報源リンク