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

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

このコミットは、Go言語のコンパイラバックエンドの一部である src/cmd/8g/cgen.c ファイルに対する変更です。cgen.c は、Goコンパイラが抽象構文木（AST）や中間表現（IR）から、ターゲットアーキテクチャ（この場合は386/amd64アーキテクチャを指す8g）向けの機械語コードを生成する際の主要な部分を担っています。特に、bgen関数はブール式や条件分岐のコード生成に関連しており、このコミットではその効率性を改善しています。

コミット

commit 14f3276c9d2659f7ae295d63e2692cb739337fa4
Author: Rémy Oudompheng <oudomphe@phare.normalesup.org>
Date:   Mon Sep 24 21:29:24 2012 +0200

    cmd/8g: don't create redundant temporaries in bgen.
    
    Comparisons used to create temporaries for arguments
    even if they were already variables or addressable.
    Removing the extra ones reduces pressure on regopt.
    
    benchmark                 old ns/op    new ns/op    delta
    BenchmarkGobDecode         50787620     49908980   -1.73%
    BenchmarkGobEncode         19870190     19473030   -2.00%
    BenchmarkGzip            3214321000   3067929000   -4.55%
    BenchmarkGunzip           496792800    465828600   -6.23%
    BenchmarkJSONEncode       232524800    263864400  +13.48%
    BenchmarkJSONDecode       622038400    506600600  -18.56%
    BenchmarkMandelbrot200     23937310     45913060  +91.81%
    BenchmarkParse             14364450     13997010   -2.56%
    BenchmarkRevcomp         6919028000   6480009000   -6.35%
    BenchmarkTemplate         594458800    539528200   -9.24%
    
    benchmark                  old MB/s     new MB/s  speedup
    BenchmarkGobDecode            15.11        15.38    1.02x
    BenchmarkGobEncode            38.63        39.42    1.02x
    BenchmarkGzip                  6.04         6.33    1.05x
    BenchmarkGunzip               39.06        41.66    1.07x
    BenchmarkJSONEncode            8.35         7.35    0.88x
    BenchmarkJSONDecode            3.12         3.83    1.23x
    BenchmarkParse                 4.03         4.14    1.03x
    BenchmarkRevcomp              36.73        39.22    1.07x
    BenchmarkTemplate              3.26         3.60    1.10x
    
    R=mtj, daniel.morsing, rsc
    CC=golang-dev
    https://golang.org/cl/6547064

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

https://github.com/golang/go/commit/14f3276c9d2659f7ae295d63e2692cb739337fa4

元コミット内容

このコミットは、Goコンパイラのcmd/8g（386/amd64アーキテクチャ向けコンパイラ）において、bgen関数が冗長な一時変数を生成するのを停止させることを目的としています。以前のバージョンでは、比較演算の引数が既に変数として存在するか、あるいは直接アドレス指定可能である場合でも、不必要に一時変数が作成されていました。これらの余分な一時変数を削除することで、レジスタ最適化（regopt）への負荷が軽減され、全体的なコード生成の効率と実行時パフォーマンスが向上します。

コミットメッセージには、様々なベンチマーク結果が示されており、多くのケースで実行時間（ns/op）の短縮やスループット（MB/s）の向上が見られます。特にBenchmarkJSONDecodeでは18.56%の実行時間短縮、BenchmarkGunzipでは6.23%の短縮と顕著な改善を達成しています。一方で、BenchmarkJSONEncodeとBenchmarkMandelbrot200ではパフォーマンスの低下（それぞれ+13.48%と+91.81%の実行時間増加）も報告されており、これはレジスタ割り当ての変更が特定のコードパスで逆効果になった可能性を示唆しています。

変更の背景

Goコンパイラは、生成されるバイナリのパフォーマンスを最大化するために、様々な最適化を施します。その中でも、レジスタの効率的な利用は非常に重要です。レジスタはCPUがデータを高速に処理するための限られたリソースであり、レジスタが不足すると、データはより低速なメモリに退避され（スピル）、パフォーマンスが低下します。

このコミット以前のGoコンパイラ（特にcmd/8gのbgen関数）では、比較演算子（例: a == b, x < y）のコードを生成する際に、その引数（a, b, x, yなど）が既にメモリ上の変数であったり、レジスタに格納されていたりして、直接利用可能な状態であるにもかかわらず、不必要に「一時変数」を生成し、そこに引数の値をコピーしてから比較を行うという非効率な挙動がありました。

このような冗長な一時変数の生成は、以下のような問題を引き起こしていました。

  1. レジスタの枯渇: 一時変数を格納するために余分なレジスタが必要となり、レジスタの利用効率が低下します。これにより、他の重要な値がレジスタからメモリにスピルされる可能性が高まります。
  2. コードサイズの増加: 一時変数の生成とコピーのための命令が追加され、生成される機械語コードのサイズが増加します。
  3. 実行時間の増加: 余分なコピー操作やメモリへのアクセスが発生するため、プログラムの実行時間が長くなります。

このコミットは、これらの問題を解決し、コンパイラがより効率的なコードを生成できるようにすることを目的としています。具体的には、比較演算の引数が既に「アドレス可能」（addable）であるかどうかをチェックし、不要な一時変数の生成をスキップすることで、レジスタの利用効率を高め、全体的なパフォーマンスを向上させようとしています。

前提知識の解説

このコミットの変更を理解するためには、以下のコンパイラ技術とGoコンパイラの内部構造に関する知識が役立ちます。

1. コンパイラの基本構造

コンパイラは通常、以下の主要なフェーズで構成されます。

  • フロントエンド: ソースコードを解析し、抽象構文木（AST）などの中間表現（IR）を生成します。
  • ミドルエンド（最適化フェーズ）: 生成されたIRに対して、様々な最適化を適用し、より効率的なコードに変換します。レジスタ割り当てや不要なコードの削除などがここで行われます。
  • バックエンド（コード生成フェーズ）: 最適化されたIRを、ターゲットアーキテクチャ（例: x86-64）の機械語コードに変換します。

このコミットは、Goコンパイラのバックエンド、特にコード生成とレジスタ割り当ての境界に近い部分に影響を与えます。

2. Goコンパイラ (cmd/8g)

Go言語の初期のコンパイラは、ターゲットアーキテクチャごとに異なる名前を持っていました。

  • 8g: 386アーキテクチャ（32ビットx86）向けのGoコンパイラ。
  • 6g: amd64アーキテクチャ（64ビットx86）向けのGoコンパイラ。
  • 5g: ARMアーキテクチャ向けのGoコンパイラ。

これらのコンパイラは、共通のフロントエンドと、アーキテクチャ固有のバックエンドを持っていました。このコミットのcmd/8gは、当時のGoコンパイラのx86系バックエンドを指しており、32ビットおよび64ビットのx86アーキテクチャ両方に影響を与える可能性があります。

3. 中間表現 (IR) と Node 構造体

コンパイラは、ソースコードを直接機械語に変換するのではなく、まず人間が理解しやすいソースコードを、コンパイラが処理しやすい形式に変換します。これが中間表現（IR）です。Goコンパイラでは、AST（抽象構文木）が主要なIRの一つです。

  • Node: cgen.cのようなコード生成フェーズでは、ASTの各要素がNode構造体として表現されます。Nodeは、変数、定数、演算子、関数呼び出しなど、プログラムのあらゆる要素を表すことができます。
  • addableプロパティ: Node構造体には、そのノードが表す値が「アドレス可能」であるか、つまり、メモリ上の特定のアドレスに直接対応しているか、あるいはレジスタに既に格納されているかを示すフラグ（addable）が含まれていることがあります。addableがtrueの場合、その値は一時的なコピーを必要とせずに直接利用できることを意味します。

4. レジスタ割り当てと regopt

  • レジスタ: CPU内部にある高速な記憶領域で、演算の対象となるデータを一時的に保持します。レジスタへのアクセスはメモリへのアクセスよりもはるかに高速です。
  • レジスタ割り当て: コンパイラの最適化フェーズの一つで、プログラム中の変数をどのレジスタに割り当てるかを決定します。レジスタの数は限られているため、どの変数をレジスタに置き、どの変数をメモリに退避させるか（スピル）を効率的に決定することが、生成コードのパフォーマンスに直結します。
  • regopt: Goコンパイラにおけるレジスタ最適化のモジュールまたはフェーズを指します。このモジュールは、レジスタの利用効率を最大化し、スピルを最小限に抑えることを目指します。一時変数が冗長に生成されると、regoptはより多くのレジスタを必要とし、その最適化の「圧力」が増大します。

5. ullman数 (Ullman's Algorithm)

Ullmanのアルゴリズムは、式を評価するために必要な最小レジスタ数を決定するためのアルゴリズムです。ASTの各ノードに対して「Ullman数」を計算し、その数に基づいてレジスタ割り当ての優先順位を決定します。

  • ullmanプロパティ: Node構造体に含まれるullmanプロパティは、そのノード（サブツリー）を評価するために必要なレジスタの数を表します。
  • UINF: "Infinity"（無限大）の略で、非常に大きなUllman数を表します。これは、そのノードが非常に複雑な式を表しており、評価に多くのレジスタや一時変数が必要となる可能性が高いことを示唆します。このコミットのコードでは、ullman >= UINFの場合に特別な処理を行っています。これは、非常に複雑な式の場合には、たとえaddableであっても一時変数を生成する方が効率的である可能性があるためです。

6. tempname, cgen, gmove, gins, optoas

これらはGoコンパイラのバックエンドでコード生成を行うためのユーティリティ関数です。

  • tempname(&node, type): 指定された型の一時変数ノードを作成し、その情報をnodeに格納します。
  • cgen(src_node, dst_node): src_nodeの値を評価し、その結果をdst_nodeに格納するためのコードを生成します。
  • gmove(src_node, dst_node): src_nodeからdst_nodeへ値を移動する（コピーする）ための機械語命令を生成します。
  • gins(opcode, arg1, arg2): 指定されたオペコード（opcode）と引数（arg1, arg2）を持つ汎用的な機械語命令を生成します。
  • optoas(opcode, type): Goコンパイラの内部オペコード（例: OCMP）と型情報に基づいて、対応するアセンブリ命令（例: CMPL）を返します。

これらの前提知識を理解することで、コミットがGoコンパイラのどの部分で、どのような目的で、どのように機能しているのかを深く把握することができます。

技術的詳細

このコミットの核心は、src/cmd/8g/cgen.c内のbgen関数における、比較演算の引数処理の改善です。bgen関数は、ブール式（例: a == b）を評価し、その結果に基づいて条件分岐（if文など）を生成する役割を担っています。

変更前は、bgen関数が比較演算の左右の引数（nlとnr）を処理する際に、無条件に一時変数を作成し、そこに引数の値をコピーしてから比較を行っていました。これは、引数が既にメモリ上の変数であったり、レジスタに格納されていて直接利用可能な場合でも行われていました。

このコミットでは、この冗長な一時変数生成を排除するために、以下の技術的詳細が導入されました。

  1. addableプロパティの活用:

    • Node構造体には、そのノードが表す値が「アドレス可能」（addable）であるかを示すフラグがあります。addableがtrueの場合、そのノードは一時的なコピーを必要とせずに直接利用できることを意味します。
    • 変更後のコードでは、if(!nl->addable)およびif(!nr->addable)という条件分岐が導入されました。これは、「もし左（または右）の引数が直接アドレス可能でない場合のみ、一時変数を生成してそこに値をコピーする」というロジックを意味します。
    • これにより、引数が既にアドレス可能であれば、tempname（一時変数ノードの作成）とcgen（一時変数への値のコピー）の呼び出しがスキップされ、不要な命令の生成が抑制されます。

  2. ノードポインタの更新:

    • 一時変数が生成された場合（つまり、!nl->addableがtrueだった場合）、元のノードポインタnl（またはnr）は、新しく生成された一時変数ノード&n1（または&tmp）を指すように更新されます（例: nl = &n1;）。
    • この更新により、後続のコード生成ステップ（ginsやgmoveなど）では、常に適切なノード（元のノードか、必要に応じて生成された一時変数ノード）が引数として渡されるようになります。これにより、コードの簡潔性が保たれつつ、効率的なコード生成が可能になります。

  3. ullman数に基づく例外処理の維持:

    • コードの冒頭部分には、if(nr->ullman >= UINF)という条件が残されています。これは、Ullman数が非常に大きい（つまり、非常に複雑な式である）場合、たとえaddableであっても一時変数を生成する方が、レジスタ割り当ての複雑性を軽減し、全体として効率的である可能性があるためです。このケースでは、引き続き一時変数が生成されます。

これらの変更により、コンパイラは比較演算のコードを生成する際に、引数の性質に応じて動的に最適な戦略を選択できるようになりました。これにより、不要な一時変数の生成が大幅に削減され、レジスタの利用効率が向上し、結果として生成される機械語コードのサイズが小さくなり、実行速度が向上します。

ベンチマーク結果の分析

コミットメッセージに記載されているベンチマーク結果は、この変更がGoプログラムのパフォーマンスに与える影響を具体的に示しています。

  • 改善が見られたベンチマーク:

    • BenchmarkGobDecode, BenchmarkGobEncode, BenchmarkGzip, BenchmarkGunzip, BenchmarkJSONDecode, BenchmarkParse, BenchmarkRevcomp, BenchmarkTemplate
    • これらのベンチマークでは、実行時間（ns/op）が短縮され、スループット（MB/s）が向上しています。これは、一時変数の削減がレジスタ割り当ての効率化に繋がり、CPUキャッシュの利用率向上やメモリアクセスの削減に寄与したためと考えられます。特にJSONDecodeやGunzipのようなデータ処理系のベンチマークで顕著な改善が見られるのは、比較演算が頻繁に行われるコードパスで効果があったことを示唆しています。

  • パフォーマンスが低下したベンチマーク:

    • BenchmarkJSONEncode (+13.48% ns/op)
    • BenchmarkMandelbrot200 (+91.81% ns/op)
    • これらのベンチマークでパフォーマンスが低下した理由は、レジスタ割り当ての変更が、特定のアルゴリズムやデータ構造のアクセスパターンに対して、かえって非効率なコードを生成してしまった可能性が考えられます。例えば、一時変数を生成しないことで、レジスタの寿命が延び、他の重要な値がレジスタから追い出される（スピルされる）頻度が増加した、あるいは、特定のレジスタ割り当てパターンがCPUのパイプライン最適化と相性が悪くなった、といったケースが考えられます。Mandelbrot200のような数値計算が主体のベンチマークでは、浮動小数点演算やループ内のレジスタ利用が非常に重要になるため、レジスタ割り当てのわずかな変更が大きな影響を与えることがあります。

全体として、このコミットはGoコンパイラのコード生成戦略を洗練させ、多くのGoプログラムの実行時パフォーマンスを向上させる重要な最適化であると言えます。パフォーマンス低下が見られたケースは、コンパイラ最適化の複雑性と、すべてのシナリオで普遍的に最適な解を見つけることの難しさを示しています。

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

変更は src/cmd/8g/cgen.c ファイルの bgen 関数内で行われています。

--- a/src/cmd/8g/cgen.c
+++ b/src/cmd/8g/cgen.c
@@ -1091,31 +1091,43 @@ bgen(Node *n, int true, int likely, Prog *to)
 		a = optoas(a, nr->type);
 
 		if(nr->ullman >= UINF) {
-			tempname(&n1, nl->type);
-			tempname(&tmp, nr->type);
-			cgen(nl, &n1);
-			cgen(nr, &tmp);
+			if(!nl->addable) {
+				tempname(&n1, nl->type);
+				cgen(nl, &n1);
+				nl = &n1;
+			}
+			if(!nr->addable) {
+				tempname(&tmp, nr->type);
+				cgen(nr, &tmp);
+				nr = &tmp;
+			}
 			regalloc(&n2, nr->type, N);
-			cgen(&tmp, &n2);
+			cgen(nr, &n2);
 			goto cmp;
 		}
 
-		tempname(&n1, nl->type);
-		cgen(nl, &n1);
+		if(!nl->addable) {
+			tempname(&n1, nl->type);
+			cgen(nl, &n1);
+			nl = &n1;
+		}
 
 		if(smallintconst(nr)) {
-			gins(optoas(OCMP, nr->type), &n1, nr);
+			gins(optoas(OCMP, nr->type), nl, nr);
 			patch(gbranch(a, nr->type, likely), to);
 			break;
 		}
 
-		tempname(&tmp, nr->type);
-		cgen(nr, &tmp);
+		if(!nr->addable) {
+			tempname(&tmp, nr->type);
+			cgen(nr, &tmp);
+			nr = &tmp;
+		}
 		regalloc(&n2, nr->type, N);
-		gmove(&tmp, &n2);
+		gmove(nr, &n2);
 
 cmp:
-		gins(optoas(OCMP, nr->type), &n1, &n2);
+		gins(optoas(OCMP, nr->type), nl, &n2);
 		patch(gbranch(a, nr->type, likely), to);
 		regfree(&n2);
 		break;

コアとなるコードの解説

上記のdiffは、bgen関数内の3つの主要なコードブロックにわたる変更を示しています。それぞれの変更がどのように冗長な一時変数の生成を排除しているかを詳しく見ていきます。

1. if(nr->ullman >= UINF) ブロック内の変更

このブロックは、右側のオペランドnrのUllman数が非常に大きい（UINF以上）場合に実行される特殊なケースです。これは、非常に複雑な式を扱う際に、レジスタ割り当ての複雑性を軽減するために一時変数を生成する方が良いと判断されるシナリオです。

  • 変更前:

    tempname(&n1, nl->type); // 左オペランド用の一時変数n1を無条件に作成
tempname(&tmp, nr->type); // 右オペランド用の一時変数tmpを無条件に作成
cgen(nl, &n1); // 左オペランドの値をn1にコピー
cgen(nr, &tmp); // 右オペランドの値をtmpにコピー
// ...
cgen(&tmp, &n2); // tmpの値をレジスタn2にコピー

    ここでは、nlとnrが既にアドレス可能であるかどうかにかかわらず、常にn1とtmpという一時変数が作成され、値がコピーされていました。

  • 変更後:

    if(!nl->addable) { // nlがアドレス可能でない場合のみ
    tempname(&n1, nl->type); // n1を作成
    cgen(nl, &n1); // nlの値をn1にコピー
    nl = &n1; // nlポインタをn1に更新
}
if(!nr->addable) { // nrがアドレス可能でない場合のみ
    tempname(&tmp, nr->type); // tmpを作成
    cgen(nr, &tmp); // nrの値をtmpにコピー
    nr = &tmp; // nrポインタをtmpに更新
}
regalloc(&n2, nr->type, N);
cgen(nr, &n2); // 更新されたnr（元のnrかtmp）の値をレジスタn2にコピー

    この変更により、nlやnrが既にaddableである場合は、一時変数n1やtmpの作成と値のコピーがスキップされます。nl = &n1;やnr = &tmp;という行は、一時変数が作成された場合に、後続のコードがその一時変数を使用するようにノードポインタを更新する役割を果たします。これにより、冗長な一時変数の生成が抑制されます。

2. if(smallintconst(nr)) ブロックの前の変更

このブロックは、右側のオペランドnrが小さな整数定数である場合に実行される最適化パスです。

  • 変更前:

    tempname(&n1, nl->type); // 左オペランド用の一時変数n1を無条件に作成
cgen(nl, &n1); // 左オペランドの値をn1にコピー
// ...
gins(optoas(OCMP, nr->type), &n1, nr); // n1とnrを比較

    ここでも、nlがaddableであるかどうかにかかわらず、一時変数n1が作成されていました。

  • 変更後:

    if(!nl->addable) { // nlがアドレス可能でない場合のみ
    tempname(&n1, nl->type); // n1を作成
    cgen(nl, &n1); // nlの値をn1にコピー
    nl = &n1; // nlポインタをn1に更新
}
// ...
gins(optoas(OCMP, nr->type), nl, nr); // 更新されたnl（元のnlかn1）とnrを比較

    同様に、nlがaddableであれば、一時変数n1の作成とコピーがスキップされ、nlが直接比較命令の引数として使用されます。

3. 最後のコードブロック（smallintconstでない場合）の変更

このブロックは、右側のオペランドnrが小さな整数定数ではない場合に実行される一般的な比較パスです。

  • 変更前:

    tempname(&tmp, nr->type); // 右オペランド用の一時変数tmpを無条件に作成
cgen(nr, &tmp); // 右オペランドの値をtmpにコピー
// ...
gmove(&tmp, &n2); // tmpの値をレジスタn2に移動
// ...
gins(optoas(OCMP, nr->type), &n1, &n2); // n1とn2を比較

    ここでも、nrがaddableであるかどうかにかかわらず、一時変数tmpが作成されていました。また、比較命令の左オペランドも常にn1（前のブロックで作成された一時変数）でした。

  • 変更後:

    if(!nr->addable) { // nrがアドレス可能でない場合のみ
    tempname(&tmp, nr->type); // tmpを作成
    cgen(nr, &tmp); // nrの値をtmpにコピー
    nr = &tmp; // nrポインタをtmpに更新
}
regalloc(&n2, nr->type, N);
gmove(nr, &n2); // 更新されたnr（元のnrかtmp）の値をレジスタn2に移動
// ...
gins(optoas(OCMP, nr->type), nl, &n2); // 更新されたnl（元のnlかn1）とn2を比較

    この変更により、nrがaddableであれば、一時変数tmpの作成とコピーがスキップされ、nrが直接gmoveの引数として使用されます。さらに、最後のgins呼び出しでは、左オペランドが&n1からnlに変更されています。これは、前のブロックでnlがaddableであればn1が作成されず、nlがそのまま使われるようになったため、それに合わせて引数を変更したものです。

これらの変更は、Goコンパイラが生成するコードの効率を向上させるための、細かではあるが重要な最適化です。不要な一時変数を排除することで、レジスタの利用効率が高まり、結果としてより高速でコンパクトなバイナリが生成されることに貢献しています。

関連リンク

  • Go言語公式ドキュメント: Go言語のコンパイラや内部構造に関する公式情報は、Goの公式ウェブサイトで確認できます。
  • GoのGerrit変更リスト: このコミットの元の変更リスト（CL）は、GoプロジェクトのGerritレビューシステムで確認できます。

参考にした情報源リンク

  • コンパイラ最適化に関する一般的な情報:
  • Ullmanのアルゴリズムに関する情報:
    • Wikipedia: Ullman's algorithm (graph theory) - 直接的なレジスタ割り当てのUllmanアルゴリズムに関する日本語記事は少ないため、グラフ理論の文脈でのUllmanアルゴリズムを参照し、その概念がコンパイラ最適化に応用されていることを理解する手助けとします。コンパイラにおけるUllmanのアルゴリズムは、式評価に必要なレジスタ数を決定するために用いられます。
  • Goコンパイラのソースコード:
    • golang/go GitHubリポジトリ - src/cmd/compile/internal/ ディレクトリ以下に、現在のGoコンパイラのバックエンドコードがあります。当時のcmd/8gのコードは、現在のコンパイラの基盤となっています。