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

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

このコミットは、Goコンパイラのcmd/8g（386アーキテクチャ向けコンパイラ）において、6g（amd64アーキテクチャ向けコンパイラ）からcomponentgenというコード生成ロジックをインポートし、適用するものです。これにより、コンパイラのコードベースの類似性を高めるとともに、特に構造体（スライス、文字列、インターフェースなど）のコピーやゼロ初期化におけるコード生成の効率を大幅に改善しています。結果として、生成されるアセンブリコード中のLEAL命令の数が劇的に減少し、様々なベンチマークで顕著なパフォーマンス向上が見られます。

コミット

commit ae0862c1ec6850035bbb89aa6274392de1020039
Author: Rémy Oudompheng <oudomphe@phare.normalesup.org>
Date:   Sun Sep 9 20:30:08 2012 +0200

    cmd/8g: import componentgen from 6g.
    
    This makes the compilers code more similar and improves
    code generation a lot.
    
    The number of LEAL instructions generated for cmd/go drops
    by 60%.
    
    % GOARCH=386 go build -gcflags -S -a cmd/go | grep LEAL | wc -l
    Before:       89774
    After:        47548
    
    benchmark                              old ns/op    new ns/op    delta
    BenchmarkAppendFloatDecimal                  540          444  -17.78%
    BenchmarkAppendFloat                        1160         1035  -10.78%
    BenchmarkAppendFloatExp                     1060          922  -13.02%
    BenchmarkAppendFloatNegExp                  1053          920  -12.63%
    BenchmarkAppendFloatBig                     1773         1558  -12.13%
    BenchmarkFormatInt                         13065        12481   -4.47%
    BenchmarkAppendInt                         10981         9900   -9.84%
    BenchmarkFormatUint                         3804         3650   -4.05%
    BenchmarkAppendUint                         3506         3303   -5.79%
    BenchmarkUnquoteEasy                         714          683   -4.34%
    BenchmarkUnquoteHard                        5117         2915  -43.03%
    
    Update #1914.
    
    R=nigeltao, rsc, golang-dev
    CC=golang-dev, remy
    https://golang.org/cl/6489067

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

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

元コミット内容

cmd/8g: import componentgen from 6g.

This makes the compilers code more similar and improves
code generation a lot.

The number of LEAL instructions generated for cmd/go drops
by 60%.

% GOARCH=386 go build -gcflags -S -a cmd/go | grep LEAL | wc -l
Before:       89774
After:        47548

benchmark                              old ns/op    new ns/op    delta
BenchmarkAppendFloatDecimal                  540          444  -17.78%
BenchmarkAppendFloat                        1160         1035  -10.78%
BenchmarkAppendFloatExp                     1060          922  -13.02%
BenchmarkAppendFloatNegExp                  1053          920  -12.63%
BenchmarkAppendFloatBig                     1773         1558  -12.13%
BenchmarkFormatInt                         13065        12481   -4.47%
BenchmarkAppendInt                         10981         9900   -9.84%
BenchmarkFormatUint                         3804         3650   -4.05%
BenchmarkAppendUint                         3506         3303   -5.79%
BenchmarkUnquoteEasy                         714          683   -4.34%
BenchmarkUnquoteHard                        5117         2915  -43.03%

Update #1914.

R=nigeltao, rsc, golang-dev
CC=golang-dev, remy
https://golang.org/cl/6489067

変更の背景

この変更の主な背景には、以下の2点があります。

  1. コンパイラコードの類似性向上: Goコンパイラは複数のアーキテクチャ（例: 386, amd64）をサポートしており、それぞれのアーキテクチャ向けに異なるコンパイラ（8g, 6gなど）が存在します。これらのコンパイラ間で共通の最適化ロジックやコード生成パターンを共有することで、コードベースの一貫性を保ち、メンテナンス性を向上させることが目的です。componentgenは6gで既に効果が確認されていた最適化であり、これを8gにも適用することで、両者のコード生成戦略をより類似させることができます。

  2. コード生成の効率化とパフォーマンス改善: 特に構造体（スライス、文字列、インターフェースなど）のコピーやゼロ初期化において、既存の8gコンパイラが生成するアセンブリコードには非効率な部分がありました。具体的には、LEAL（Load Effective Address）命令が過剰に生成される傾向がありました。LEAL命令はアドレス計算に用いられますが、これが多用されると、より直接的なメモリアクセスやレジスタ利用に比べて効率が落ちる可能性があります。componentgenの導入により、これらの操作がより最適化されたアセンブリコードに変換され、結果としてLEAL命令の数が大幅に削減され、実行時のパフォーマンスが向上しました。コミットメッセージに記載されているベンチマーク結果は、このパフォーマンス改善を明確に示しています。

前提知識の解説

このコミットを理解するためには、以下の概念について知っておく必要があります。

  • Goコンパイラ (cmd/8g, cmd/6g):

    • Go言語のコンパイラは、ソースコードを機械語に変換する役割を担います。Goのツールチェインには、異なるCPUアーキテクチャに対応するための複数のコンパイラが含まれています。
    • cmd/8g: Intel 386 (IA-32) アーキテクチャ向けのGoコンパイラです。32ビットシステムをターゲットとします。
    • cmd/6g: AMD64 (x86-64) アーキテクチャ向けのGoコンパイラです。64ビットシステムをターゲットとします。
    • これらのコンパイラは、それぞれのアセンブリコードを生成するバックエンド部分が異なりますが、フロントエンド（構文解析、型チェックなど）や中間表現の処理は共通化されています。

  • LEAL (Load Effective Address) 命令:

    • x86アセンブリ言語における命令の一つで、「実効アドレスをロードする」という意味を持ちます。
    • 通常、メモリからデータをロードするMOV命令などとは異なり、LEALはメモリの内容を読み込むのではなく、オペランドで指定されたアドレス計算の結果をレジスタに格納します。
    • 例: LEAL (%EAX, %EBX, 4), %ECX は、ECX = EAX + EBX * 4 という計算を行い、その結果をECXに格納します。
    • LEALは、ポインタ演算、配列のインデックス計算、あるいは単純な加算や乗算の最適化（特に定数による乗算）など、様々なアドレス計算に利用されます。
    • この命令が過剰に生成される場合、それはコンパイラがメモリ上のデータにアクセスする際に、不必要に複雑なアドレス計算を行っている可能性を示唆します。より効率的なコードでは、直接的なレジスタ操作や、よりシンプルなメモリアクセスパターンが採用されるべきです。

  • コード生成 (Code Generation):

    • コンパイラの最終段階の一つで、中間表現（IR）をターゲットアーキテクチャの機械語（アセンブリコード）に変換するプロセスです。
    • この段階では、レジスタ割り当て、命令選択、命令スケジューリング、最適化などが行われます。
    • 効率的なコード生成は、プログラムの実行速度に直結するため、コンパイラ最適化の重要な側面です。

  • Goのデータ構造の内部表現:

    • スライス (Slice): Goのスライスは、内部的にポインタ、長さ、容量の3つの要素から構成される構造体です。
    • 文字列 (String): Goの文字列は、内部的にバイト配列へのポインタと長さの2つの要素から構成される構造体です。
    • インターフェース (Interface): Goのインターフェースは、内部的に型情報へのポインタとデータへのポインタの2つの要素から構成される構造体です。
    • これらの構造体は、メモリ上で連続した領域を占めますが、そのコピーやゼロ初期化は、各コンポーネント（ポインタ、長さ、容量など）を個別に処理する必要があります。

技術的詳細

このコミットの核心は、componentgenという新しいコード生成戦略の導入にあります。これは、特にGoのスライス、文字列、インターフェースといった複合データ型（内部的には構造体として表現される）のコピーやゼロ初期化を最適化するために設計されています。

従来のコード生成では、これらの複合データ型をコピーする際に、全体を一つの大きなブロックとして扱うか、あるいは各コンポーネントへのアクセスが非効率な方法で行われていた可能性があります。その結果、アドレス計算のためにLEAL命令が多用され、生成されるアセンブリコードが冗長になっていました。

componentgen関数は、これらの複合データ型を「コンポーネントごと」に処理するアプローチを取ります。例えば、スライスであれば、そのポインタ、長さ、容量の各フィールドを個別に、かつ効率的にコピーまたはゼロ初期化します。これにより、コンパイラはより直接的なメモリアクセス命令やレジスタ操作命令を選択できるようになり、不必要なアドレス計算（LEAL命令の生成）を避けることができます。

具体的には、componentgenは以下の処理を行います。

  1. cadable関数の導入: componentgenの内部で利用されるヘルパー関数cadableは、与えられたNode（コンパイラ内部の抽象構文木のノード）が「アドレス可能（addable）」であるか、つまりそのアドレスを直接取得できるかをチェックします。これは、メモリ上の位置が確定している変数やフィールドに対して効率的な操作を行うための前提となります。
  2. 型に応じたコンポーネント処理: componentgenは、入力されたNodeの型（TARRAY、TSTRING、TINTER）に応じて、その内部構造を解析し、各コンポーネント（例: スライスのArray_array、Array_nel、Array_capフィールド）に対して個別のコピー操作（gmove）を生成します。
  3. 効率的なgmoveの利用: gmoveはGoコンパイラのバックエンドにおける基本的なデータ移動操作であり、componentgenはこれを利用して、各コンポーネントを効率的に移動させます。これにより、コンパイラは各コンポーネントのサイズとオフセットに基づいて最適なアセンブリ命令（例: MOV命令）を選択できるようになります。
  4. sgenとclearfatからの呼び出し: componentgenは、構造体の生成（sgen）やゼロ初期化（clearfat）を行う関数から呼び出されます。特に、サイズが8バイトまたは12バイトの構造体（これはGoのスライス、文字列、インターフェースの一般的なサイズに該当します）に対してこの最適化が適用されます。

この「コンポーネントごと」の処理により、コンパイラはより粒度の細かい、かつターゲットアーキテクチャに最適化されたアセンブリコードを生成できるようになり、結果としてLEAL命令の削減と全体的なパフォーマンス向上を実現しています。

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

このコミットによる主要なコード変更は以下の3つのファイルにわたります。

  1. src/cmd/8g/cgen.c:

    • cadable関数が新しく追加されました。この関数は、与えられたノードがアドレス可能であるかをチェックします。
    • componentgen関数が新しく追加されました。この関数は、スライス、文字列、インターフェースなどの複合型をコンポーネントごとにコピーまたはゼロ初期化するロジックを含みます。
    • sgen関数（構造体生成を担当）内で、サイズが8バイトまたは12バイトの構造体に対してcomponentgenが呼び出されるようになりました。
    // src/cmd/8g/cgen.c (抜粋)
@@ -1197,6 +1197,11 @@ sgen(Node *n, Node *res, int64 w)
 	return;
 	}
 
+	if (w == 8 || w == 12) {
+		if(componentgen(n, res))
+			return;
+	}
+
 	// offset on the stack
 	osrc = stkof(n);
 	odst = stkof(res);
@@ -1280,3 +1285,162 @@ sgen(Node *n, Node *res, int64 w)
 	}
 }
 
+static int
+cadable(Node *n)
+{
+	if(!n->addable) {
+		// dont know how it happens,
+		// but it does
+		return 0;
+	}
+
+	switch(n->op) {
+	case ONAME:
+		return 1;
+	}
+	return 0;
+}
+
+/*
+ * copy a structure component by component
+ * return 1 if can do, 0 if cant.
+ * nr is N for copy zero
+ */
+int
+componentgen(Node *nr, Node *nl)
+{
+	Node nodl, nodr;
+	int freel, freer;
+
+	freel = 0;
+	freer = 0;
+
+	switch(nl->type->etype) {
+	default:
+		goto no;
+
+	case TARRAY:
+		if(!isslice(nl->type))
+			goto no;
+	case TSTRING:
+	case TINTER:
+		break;
+	}
+
+	nodl = *nl;
+	if(!cadable(nl)) {
+		if(nr == N || !cadable(nr))
+			goto no;
+		igen(nl, &nodl, N);
+		freel = 1;
+	}
+
+	if(nr != N) {
+		nodr = *nr;
+		if(!cadable(nr)) {
+			igen(nr, &nodr, N);
+			freer = 1;
+		}
+	}
+
+	switch(nl->type->etype) {
+	case TARRAY:
+		if(!isslice(nl->type))
+			goto no;
+
+		nodl.xoffset += Array_array;
+		nodl.type = ptrto(nl->type->type);
+
+		if(nr != N) {
+			nodr.xoffset += Array_array;
+			nodr.type = nodl.type;
+		} else
+			nodconst(&nodr, nodl.type, 0);
+		gmove(&nodr, &nodl);
+
+		nodl.xoffset += Array_nel-Array_array;
+		nodl.type = types[TUINT32];
+
+		if(nr != N) {
+			nodr.xoffset += Array_nel-Array_array;
+			nodr.type = nodl.type;
+		} else
+			nodconst(&nodr, nodl.type, 0);
+		gmove(&nodr, &nodl);
+
+		nodl.xoffset += Array_cap-Array_nel;
+		nodl.type = types[TUINT32];
+
+		if(nr != N) {
+			nodr.xoffset += Array_cap-Array_nel;
+			nodr.type = nodl.type;
+		} else
+			nodconst(&nodr, nodl.type, 0);
+		gmove(&nodr, &nodl);
+
+		goto yes;
+
+	case TSTRING:
+		nodl.xoffset += Array_array;
+		nodl.type = ptrto(types[TUINT8]);
+
+		if(nr != N) {
+			nodr.xoffset += Array_array;
+			nodr.type = nodl.type;
+		} else
+			nodconst(&nodr, nodl.type, 0);
+		gmove(&nodr, &nodl);
+
+		nodl.xoffset += Array_nel-Array_array;
+		nodl.type = types[TUINT32];
+
+		if(nr != N) {
+			nodr.xoffset += Array_nel-Array_array;
+			nodr.type = nodl.type;
+		} else
+			nodconst(&nodr, nodl.type, 0);
+		gmove(&nodr, &nodl);
+
+		goto yes;
+
+	case TINTER:
+		nodl.xoffset += Array_array;
+		nodl.type = ptrto(types[TUINT8]);
+
+		if(nr != N) {
+			nodr.xoffset += Array_array;
+			nodr.type = nodl.type;
+		} else
+			nodconst(&nodr, nodl.type, 0);
+		gmove(&nodr, &nodl);
+
+		nodl.xoffset += Array_nel-Array_array;
+		nodl.type = ptrto(types[TUINT8]);
+
+		if(nr != N) {
+			nodr.xoffset += Array_nel-Array_array;
+			nodr.type = nodl.type;
+		} else
+			nodconst(&nodr, nodl.type, 0);
+		gmove(&nodr, &nodl);
+
+		goto yes;
+
+	case TSTRUCT:
+		goto no;
+	}
+
+no:
+	if(freer)
+		regfree(&nodr);
+	if(freel)
+		regfree(&nodl);
+	return 0;
+
+yes:
+	if(freer)
+		regfree(&nodr);
+	if(freel)
+		regfree(&nodl);
+	return 1;
+}

  2. src/cmd/8g/gg.h:

    • componentgen関数のプロトタイプ宣言が追加されました。
    // src/cmd/8g/gg.h (抜粋)
@@ -107,6 +107,7 @@ void	cgen_aret(Node*, Node*);
 Node*	ncon(uint32);
 void	mgen(Node*, Node*, Node*);
 void	mfree(Node*);
+int	componentgen(Node*, Node*);
 
 /*
  * cgen64.c

  3. src/cmd/8g/ggen.c:

    • clearfat関数（構造体のゼロ初期化を担当）内で、サイズが8バイトまたは12バイトの構造体に対してcomponentgenが呼び出されるようになりました。
    // src/cmd/8g/ggen.c (抜粋)
@@ -59,6 +59,10 @@ clearfat(Node *nl)
 	dump(" clearfat", nl);
 
 	w = nl->type->width;
+	if(w == 8 || w == 12)
+		if(componentgen(N, nl))
+			return;
+
 	c = w % 4;	// bytes
 	q = w / 4;	// quads

コアとなるコードの解説

cadable関数

cadable関数は、Goコンパイラの内部表現であるNodeが「アドレス可能（addable）」であるかを判定します。アドレス可能とは、そのノードがメモリ上の具体的な位置（アドレス）を持つエンティティ（例えば、変数名ONAME）を表していることを意味します。componentgenが効率的なコピー操作を行うためには、コピー元またはコピー先がアドレス可能である必要があります。

static int
cadable(Node *n)
{
	if(!n->addable) {
		// dont know how it happens,
		// but it does
		return 0;
	}

	switch(n->op) {
	case ONAME: // ノードが変数名を表す場合
		return 1;
	}
	return 0;
}

componentgen関数

componentgen関数は、このコミットの主要なロジックを担います。この関数は、Goのスライス、文字列、インターフェースといった複合データ型を、その内部コンポーネント（ポインタ、長さ、容量など）ごとに効率的にコピーまたはゼロ初期化します。

  • 引数:
    • Node *nr: コピー元となるノード。ゼロ初期化の場合はN（NULL）が渡されます。
    • Node *nl: コピー先となるノード。
  • 戻り値: 処理が成功した場合は1、失敗した場合は0を返します。

関数の内部では、まずコピー元とコピー先がcadableであるかを確認し、必要に応じて一時的なノードを生成します。その後、nl->type->etype（コピー先の型）に基づいて処理を分岐します。

  • TARRAY (スライス):

    • スライスは内部的にデータへのポインタ、長さ、容量の3つのフィールドを持ちます。
    • componentgenは、Array_array（データポインタ）、Array_nel（長さ）、Array_cap（容量）の各オフセットを計算し、それぞれのコンポーネントに対してgmove（汎用的なデータ移動関数）を呼び出します。
    • nr == Nの場合（ゼロ初期化）、nodconstを使って0を生成し、その値をコピー先に移動させます。

  • TSTRING (文字列):

    • 文字列は内部的にバイト配列へのポインタと長さの2つのフィールドを持ちます。
    • componentgenは、Array_array（データポインタ）とArray_nel（長さ）の各コンポーネントを個別に処理します。

  • TINTER (インターフェース):

    • インターフェースは内部的に型情報へのポインタとデータへのポインタの2つのフィールドを持ちます。
    • componentgenは、Array_array（型情報ポインタ）とArray_nel（データポインタ）の各コンポーネントを個別に処理します。

  • TSTRUCT: 構造体全体としてのコピーはここでは処理せず、goto no;で終了します。これは、componentgenが特定の複合型（スライス、文字列、インターフェース）の最適化に特化しているためです。

int
componentgen(Node *nr, Node *nl)
{
	Node nodl, nodr;
	int freel, freer;

	freel = 0;
	freer = 0;

	// コピー先の型がTARRAY, TSTRING, TINTER以外の場合は処理しない
	switch(nl->type->etype) {
	default:
		goto no;
	case TARRAY:
		if(!isslice(nl->type)) // スライスでない配列は処理しない
			goto no;
	case TSTRING:
	case TINTER:
		break;
	}

	nodl = *nl;
	if(!cadable(nl)) { // コピー先がアドレス可能でない場合、一時ノードを生成
		if(nr == N || !cadable(nr)) // コピー元もアドレス可能でない場合は処理しない
			goto no;
		igen(nl, &nodl, N); // 一時ノードにコピー先の値をロード
		freel = 1;
	}

	if(nr != N) { // コピー元がある場合
		nodr = *nr;
		if(!cadable(nr)) { // コピー元がアドレス可能でない場合、一時ノードを生成
			igen(nr, &nodr, N); // 一時ノードにコピー元の値をロード
			freer = 1;
		}
	}

	// 型に応じたコンポーネントごとの処理
	switch(nl->type->etype) {
	case TARRAY: // スライスの場合
		// データポインタのコピー
		nodl.xoffset += Array_array;
		nodl.type = ptrto(nl->type->type);
		if(nr != N) {
			nodr.xoffset += Array_array;
			nodr.type = nodl.type;
		} else
			nodconst(&nodr, nodl.type, 0); // ゼロ初期化
		gmove(&nodr, &nodl);

		// 長さのコピー
		nodl.xoffset += Array_nel-Array_array;
		nodl.type = types[TUINT32];
		if(nr != N) {
			nodr.xoffset += Array_nel-Array_array;
			nodr.type = nodl.type;
		} else
			nodconst(&nodr, nodl.type, 0); // ゼロ初期化
		gmove(&nodr, &nodl);

		// 容量のコピー
		nodl.xoffset += Array_cap-Array_nel;
		nodl.type = types[TUINT32];
		if(nr != N) {
			nodr.xoffset += Array_cap-Array_nel;
			nodr.type = nodl.type;
		} else
			nodconst(&nodr, nodl.type, 0); // ゼロ初期化
		gmove(&nodr, &nodl);

		goto yes;

	case TSTRING: // 文字列の場合
		// データポインタのコピー
		nodl.xoffset += Array_array;
		nodl.type = ptrto(types[TUINT8]);
		if(nr != N) {
			nodr.xoffset += Array_array;
			nodr.type = nodl.type;
		} else
			nodconst(&nodr, nodl.type, 0);
		gmove(&nodr, &nodl);

		// 長さのコピー
		nodl.xoffset += Array_nel-Array_array;
		nodl.type = types[TUINT32];
		if(nr != N) {
			nodr.xoffset += Array_nel-Array_array;
			nodr.type = nodl.type;
		} else
			nodconst(&nodr, nodl.type, 0);
		gmove(&nodr, &nodl);

		goto yes;

	case TINTER: // インターフェースの場合
		// 型情報ポインタのコピー
		nodl.xoffset += Array_array;
		nodl.type = ptrto(types[TUINT8]);
		if(nr != N) {
			nodr.xoffset += Array_array;
			nodr.type = nodl.type;
		} else
			nodconst(&nodr, nodl.type, 0);
		gmove(&nodr, &nodl);

		// データポインタのコピー
		nodl.xoffset += Array_nel-Array_array;
		nodl.type = ptrto(types[TUINT8]);
		if(nr != N) {
			nodr.xoffset += Array_nel-Array_array;
			nodr.type = nodl.type;
		} else
			nodconst(&nodr, nodl.type, 0);
		gmove(&nodr, &nodl);

		goto yes;

	case TSTRUCT: // 構造体はここでは処理しない
		goto no;
	}

no: // 処理失敗時のクリーンアップ
	if(freer)
		regfree(&nodr);
	if(freel)
		regfree(&nodl);
	return 0;

yes: // 処理成功時のクリーンアップ
	if(freer)
		regfree(&nodr);
	if(freel)
		regfree(&nodl);
	return 1;
}

sgen関数とclearfat関数からの呼び出し

sgen関数は、Goコンパイラが構造体などの値を生成する際に使用される関数です。clearfat関数は、メモリ領域をゼロで初期化する際に使用されます。

このコミットでは、これらの関数内で、コピーまたはゼロ初期化の対象となる構造体のサイズが8バイトまたは12バイトの場合に、新しく導入されたcomponentgen関数を呼び出すように変更されています。これは、Goのスライス、文字列、インターフェースがこれらのサイズに該当することが多いため、これらの型に対する最適化を狙っています。

// src/cmd/8g/cgen.c の sgen 関数内 (抜粋)
if (w == 8 || w == 12) {
    if(componentgen(n, res)) // コピー元n、コピー先res
        return;
}

// src/cmd/8g/ggen.c の clearfat 関数内 (抜粋)
if(w == 8 || w == 12)
    if(componentgen(N, nl)) // ゼロ初期化のためコピー元はN、コピー先nl
        return;

この変更により、これらの複合型のコピーやゼロ初期化の際に、より効率的なcomponentgenのロジックが適用され、結果として生成されるアセンブリコードの品質が向上し、LEAL命令の削減とパフォーマンス改善が実現されました。

関連リンク

参考にした情報源リンク

  • Go言語のコンパイラに関する一般的な情報 (Goの公式ドキュメントやブログ記事など)
  • x86アセンブリ言語におけるLEAL命令の機能と用途に関する情報
  • Goのスライス、文字列、インターフェースの内部構造に関する情報
  • Goコンパイラのソースコード (特にsrc/cmd/8gディレクトリ内のファイル)
  • GoのIssue Tracker (#1914)