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

このコミットは、Goコンパイラのコード生成部分、特にループのコードレイアウトと分岐予測に関する改善を目的としています。expecttaken関数の廃止と、gbranchおよびbgen関数へのlikely引数の追加により、生成されるアセンブリコードの連続性を高め、可読性を向上させるとともに、一部のベンチマークでパフォーマンスの改善が見られました。

コミット

commit 001b75c942b67e09893c8ad895b2c9c01e4e14b1
Author: Russ Cox <rsc@golang.org>
Date:   Wed May 30 18:07:39 2012 -0400

    cmd/gc: contiguous loop layout
    
    Drop expecttaken function in favor of extra argument
    to gbranch and bgen. Mark loop condition as likely to
    be true, so that loops are generated inline.
    
    The main benefit here is contiguous code when trying
    to read the generated assembly. It has only minor effects
    on the timing, and they mostly cancel the minor effects
    that aligning function entry points had.  One exception:
    both changes made Fannkuch faster.
    
    Compared to before CL 6244066 (before aligned functions)
    benchmark                 old ns/op    new ns/op    delta
    BenchmarkBinaryTree17    4222117400   4201958800   -0.48%
    BenchmarkFannkuch11      3462631800   3215908600   -7.13%
    BenchmarkGobDecode         20887622     20899164   +0.06%
    BenchmarkGobEncode          9548772      9439083   -1.15%
    BenchmarkGzip                151687       152060   +0.25%
    BenchmarkGunzip                8742         8711   -0.35%
    BenchmarkJSONEncode        62730560     62686700   -0.07%
    BenchmarkJSONDecode       252569180    252368960   -0.08%
    BenchmarkMandelbrot200      5267599      5252531   -0.29%
    BenchmarkRevcomp25M       980813500    985248400   +0.45%
    BenchmarkTemplate         361259100    357414680   -1.06%
    
    Compared to tip (aligned functions):
    benchmark                 old ns/op    new ns/op    delta
    BenchmarkBinaryTree17    4140739800   4201958800   +1.48%
    BenchmarkFannkuch11      3259914400   3215908600   -1.35%
    BenchmarkGobDecode         20620222     20899164   +1.35%
    BenchmarkGobEncode          9384886      9439083   +0.58%
    BenchmarkGzip                150333       152060   +1.15%
    BenchmarkGunzip                8741         8711   -0.34%
    BenchmarkJSONEncode        65210990     62686700   -3.87%
    BenchmarkJSONDecode       249394860    252368960   +1.19%
    BenchmarkMandelbrot200      5273394      5252531   -0.40%
    BenchmarkRevcomp25M       996013800    985248400   -1.08%
    BenchmarkTemplate         360620840    357414680   -0.89%
    
    R=ken2
    CC=golang-dev
    https://golang.org/cl/6245069

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

https://github.com/golang/go/commit/001b75c942b67e09893c8ad895b2c9c01e4e14b1

元コミット内容

cmd/gc: 連続的なループレイアウト

expecttaken関数を廃止し、gbranchとbgenに引数を追加。ループ条件が真である可能性が高いとマークすることで、ループがインラインで生成されるようにする。

これにより、生成されたアセンブリを読み取る際にコードが連続的になるという主な利点がある。タイミングへの影響はごくわずかで、関数のエントリポイントをアラインメントしたことによるわずかな影響をほとんど打ち消す。ただし、Fannkuchベンチマークは両方の変更によって高速化された。

CL 6244066（関数アラインメント前）との比較: （ベンチマーク結果は上記コミット内容を参照）

tip（関数アラインメント後）との比較: （ベンチマーク結果は上記コミット内容を参照）

変更の背景

この変更の主な背景は、Goコンパイラが生成するアセンブリコードの品質向上にあります。特に、以下の点が挙げられます。

1. 可読性の向上: 生成されるアセンブリコードにおいて、ループの本体と条件分岐が連続して配置されるようにすることで、人間がアセンブリコードを読んだりデバッグしたりする際の理解を容易にすることが目的です。従来のコード生成では、ループの条件が偽の場合の分岐先が遠く離れて配置されることがあり、コードの流れを追いにくくなることがありました。
2. 分岐予測の最適化: 現代のCPUは、パイプライン処理を効率的に行うために「分岐予測」という技術を使用しています。これは、条件分岐が発生した際に、どちらのパスが実行される可能性が高いかを予測し、その予測に基づいて次の命令を事前にフェッチ・実行しておくものです。予測が当たれば高速に処理が進みますが、外れるとパイプラインのフラッシュが発生し、性能が低下します。このコミットでは、ループの条件が「真である可能性が高い」というヒントをコンパイラに与えることで、CPUの分岐予測をより正確にし、パフォーマンスの向上を図っています。
3. 以前の変更との関連: コミットメッセージに言及されているCL 6244066は、関数のエントリポイントをアラインメントすることで、キャッシュ効率を向上させようとした変更です。このコミットは、その変更がもたらしたわずかな性能影響を相殺しつつ、Fannkuchベンチマークにおいては両方の変更が相乗効果で高速化をもたらしたと報告されています。これは、コンパイラの最適化が複雑な相互作用を持つことを示唆しています。

前提知識の解説

このコミットを理解するためには、以下の前提知識が役立ちます。

1. コンパイラのコード生成:

   • 中間表現 (IR): ソースコードは、コンパイラによって直接機械語に変換されるのではなく、まず抽象構文木 (AST) や中間表現 (IR) と呼ばれる形式に変換されます。Goコンパイラも同様に、Go言語のコードを内部的なデータ構造（Nodeなど）に変換し、それらを基にアセンブリコードを生成します。
   • コードジェネレータ (Code Generator): IRからターゲットアーキテクチャ（x86, ARMなど）のアセンブリコードを生成する部分です。このコミットで変更されているcmd/gc内のファイル群（cgen.c, ggen.c, gsubr.cなど）は、このコード生成の役割を担っています。
   • 分岐命令 (Branch Instructions): プログラムの実行フローを制御する命令です。if文やforループ、switch文などは、最終的にアセンブリレベルでは条件分岐命令（例: JMP, JE, JNE, JL, JGなど）に変換されます。
   • パッチ (Patch): コード生成の過程で、ジャンプ命令のターゲットアドレスがまだ確定していない場合があります。このような場合、一時的にプレースホルダーを置いておき、後で正しいアドレスで埋め合わせる（パッチを当てる）処理が行われます。patch関数はこの役割を担います。

2. CPUの分岐予測 (Branch Prediction):

   • パイプライン処理: 現代のCPUは、複数の命令を同時に処理するためにパイプラインという仕組みを持っています。これにより、命令のフェッチ、デコード、実行、ライトバックといった各ステージを並行して進めることができます。
   • 分岐のコスト: 条件分岐命令に遭遇すると、CPUは次にどの命令を実行すべきか確定できません。もし間違ったパスの命令をフェッチして実行し始めてしまうと、後でその結果を破棄し、正しいパスの命令を最初からやり直す必要があります。この「パイプラインのフラッシュ」は非常にコストが高く、性能を大きく低下させます。
   • 分岐予測器 (Branch Predictor): この問題を緩和するために、CPUには分岐予測器が搭載されています。これは、過去の分岐の挙動を学習し、次に同じ分岐に遭遇した際にどちらのパスが実行される可能性が高いかを予測するハードウェアです。
   • 予測ヒント (Prediction Hints): コンパイラは、プログラムの構造や開発者の意図に基づいて、特定の分岐が「真になりやすい」か「偽になりやすい」かといったヒントを生成されるアセンブリコードに埋め込むことができます。CPUはこれらのヒントを参考にすることで、より正確な予測を行うことが可能になります。このコミットで追加されたlikely引数は、この予測ヒントを提供するためのものです。

3. Goコンパイラの構造:

   • cmd/gc: Go言語の主要なコンパイラです。
   • cmd/5g, cmd/6g, cmd/8g: それぞれARM (5g), x86-64 (6g), x86 (8g) アーキテクチャ向けのコード生成を担当する部分です。これらのディレクトリ内のファイルが、各アーキテクチャ固有のアセンブリ命令生成ロジックを含んでいます。
   • gbranch関数: アセンブリの分岐命令を生成する関数です。
   • bgen関数: 論理式（ブール式）の評価結果に基づいて条件分岐を生成する関数です。if文やループの条件などで使用されます。
   • expecttaken関数: 以前のGoコンパイラに存在した、分岐が「取られる（実行される）」か「取られない」かをコンパイラにヒントとして与えるための関数です。このコミットで廃止されました。

技術的詳細

このコミットの技術的な核心は、Goコンパイラのコード生成における分岐命令の扱いと、それに伴う分岐予測のヒントの与え方の変更にあります。

expecttaken関数の廃止とlikely引数の導入

• expecttakenの課題: 以前のGoコンパイラでは、expecttaken(Prog *p, int taken)という関数を使用して、生成された分岐命令pがtaken（真）であるか否かのヒントを与えていました。このアプローチは、分岐命令が生成された後に別途ヒントを与える形になっており、コードの連続性や管理の面で改善の余地がありました。
• likely引数の導入: このコミットでは、expecttaken関数を廃止し、代わりに分岐命令を生成する主要な関数であるgbranchと、ブール条件を生成するbgen関数に直接likelyという新しい引数を追加しました。
  • likelyの値は以下の意味を持ちます。
    • +1: 分岐が「取られる（実行される）」可能性が高い (likely taken)。
    • -1: 分岐が「取られない（スキップされる）」可能性が高い (likely not taken)。
    • 0: どちらとも言えない（意見なし）。
• コードレイアウトへの影響:
  • ループの条件分岐は、通常、ループが継続する限り真（ループ本体が実行される）である可能性が高いです。このコミットでは、このようなループ条件に対してlikely引数に+1（またはlikely）を設定することで、コンパイラがループ本体のコードを条件分岐の直後に配置するよう促します。これにより、CPUの命令キャッシュの効率が向上し、パイプラインのフラッシュが減少する可能性があります。
  • コミットメッセージにある「contiguous loop layout」とは、この「ループ本体のコードが条件分岐の直後に連続して配置される」状態を指します。これにより、生成されたアセンブリコードの可読性も向上します。

gbranchとbgenの変更

• gbranchのシグネチャ変更:
  • 変更前: Prog* gbranch(int as, Type *t)
  • 変更後: Prog* gbranch(int as, Type *t, int likely)
  • as: アセンブリ命令の種類（例: ABNE (Branch Not Equal), AJMP (Jump) など）。
  • t: 型情報（多くの場合無視される）。
  • likely: 新しく追加された分岐予測ヒント。
• bgenのシグネチャ変更:
  • 変更前: void bgen(Node *n, int true, Prog *to)
  • 変更後: void bgen(Node *n, int true, int likely, Prog *to)
  • n: 評価するブール式を表すノード。
  • true: nが真の場合にジャンプするかどうか。
  • likely: 新しく追加された分岐予測ヒント。
  • to: ジャンプ先のプログラムカウンタ。

パフォーマンスへの影響

コミットメッセージには、この変更がベンチマークに与える影響が詳細に記載されています。

• 全体的な影響: 多くのベンチマークでは、タイミングへの影響は「ごくわずか」であり、以前の「関数のエントリポイントのアラインメント」によるわずかな影響を「ほとんど打ち消す」とされています。これは、コンパイラの最適化が複雑なトレードオフの上に成り立っていることを示しています。
• Fannkuchベンチマークの高速化: 唯一の例外として、Fannkuchベンチマークは両方の変更（関数アラインメントと今回のループレイアウト改善）によって顕著に高速化されたと報告されています。これは、Fannkuchのような計算集約型でループが多用されるアルゴリズムにおいて、コードレイアウトと分岐予測の最適化が特に効果的であることを示唆しています。

実装の詳細

• gbranch関数内で、likely引数の値に基づいて、生成されるProg構造体のfrom.typeとfrom.offsetフィールドが設定されます。これらのフィールドは、リンカや後続の最適化パスで分岐予測のヒントとして利用される可能性があります。
• bgen関数は、内部でgbranchやgencmp0といった関数を呼び出す際に、自身のlikely引数を下位の関数に伝播させます。これにより、ブール式の評価から最終的な分岐命令の生成まで、一貫した分岐予測ヒントが適用されます。
• src/cmd/gc/cplx.cのcomplexbool関数も、bgenを呼び出す際にlikely引数を渡すように変更されています。これは、複素数に関するブール条件の評価にも同様の最適化が適用されることを意味します。

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

このコミットで変更された主要なファイルと、その変更の概要は以下の通りです。

• src/cmd/{5g,6g,8g}/cgen.c: 各アーキテクチャのコード生成のコア部分。gbranchやbgenの呼び出し箇所が変更され、likely引数が追加されています。
• src/cmd/{5g,6g,8g}/cgen64.c: 64ビット整数演算のコード生成部分。cmp64関数のシグネチャが変更され、likely引数が追加されています。
• src/cmd/{5g,6g,8g}/gg.h: 各アーキテクチャのヘッダファイル。gbranch, bgen, cmp64, complexbool関数のプロトタイプ宣言が変更され、expecttaken関数の宣言が削除されています。
• src/cmd/{5g,6g,8g}/ggen.c: ジェネリックなコード生成部分。gbranchやginscallの呼び出し箇所が変更され、likely引数が追加されています。
• src/cmd/{5g,6g,8g}/gsubr.c: サブルーチンやユーティリティ関数。gbranch関数の実装が変更され、likely引数を受け取るようになり、expecttaken関数の実装が削除されています。
• src/cmd/{5g,6g,8g}/reg.c: レジスタ割り当て関連。mark関数内の条件分岐が変更され、AUNDEF命令が考慮されるようになっています。
• src/cmd/gc/cplx.c: 複素数演算のコード生成部分。complexbool関数のシグネチャが変更され、likely引数が追加されています。
• src/cmd/gc/gen.c: ジェネリックなコード生成部分。ループや条件分岐の生成においてbgenの呼び出し箇所が変更され、likely引数が追加されています。
• src/cmd/gc/go.h: Goコンパイラの主要なヘッダファイル。complexboolとbgenのプロトタイプ宣言が変更されています。

全体として、gbranchとbgenの関数シグネチャ変更が広範囲に影響しており、それらの関数を呼び出す全ての箇所で新しいlikely引数が追加されています。

コアとなるコードの解説

このコミットのコアとなる変更は、gbranchとbgen関数のシグネチャ変更と、それに伴う分岐予測ヒントの導入です。

gbranch関数の変更 (src/cmd/*/gsubr.c)

gbranch関数は、アセンブリレベルの条件分岐命令を生成する役割を担っています。

変更前:

Prog*
gbranch(int as, Type *t)
{
    Prog *p;
    USED(t);
    p = prog(as);
    p->to.type = D_BRANCH;
    p->to.branch = P;
    return p;
}

変更後:

Prog*
gbranch(int as, Type *t, int likely)
{
    Prog *p;
    USED(t);
    USED(likely);  // TODO: record this for linker
    p = prog(as);
    p->to.type = D_BRANCH;
    p->to.branch = P;
    if(as != AJMP && likely != 0) { // AJMP (無条件ジャンプ) 以外で、likelyヒントがある場合
        p->from.type = D_CONST;
        p->from.offset = likely > 0; // likelyが+1なら1、-1なら0を設定
    }
    return p;
}

• likely引数の追加: gbranch関数は、as（アセンブリ命令の種類）とt（型）に加えて、likelyという新しい整数引数を受け取るようになりました。
• 分岐予測ヒントの記録: asがAJMP（無条件ジャンプ）ではない場合（つまり条件分岐の場合）かつ、likelyが0ではない場合（つまりヒントが与えられている場合）、生成されるProg構造体のfrom.typeをD_CONSTに、from.offsetをlikely > 0の結果（likelyが正なら1、負なら0）に設定しています。このfrom.offsetの値が、後続のリンカや最適化パスで分岐予測のヒントとして利用されます。TODO: record this for linkerというコメントは、このヒントが最終的にリンカに伝達され、実行ファイルの生成に影響を与えることを示唆しています。

bgen関数の変更 (src/cmd/*/cgen.c, src/cmd/gc/gen.c)

bgen関数は、ブール式を評価し、その結果に基づいて条件分岐を生成します。

変更前 (src/cmd/5g/cgen.cの例):

void
bgen(Node *n, int true, Prog *to)
{
    // ... 既存のロジック ...
    // 例: OLITERALの場合
    case OLITERAL:
        if(!true == !n->val.u.bval)
            patch(gbranch(AB, T), to);
        goto ret;
    // ...
}

変更後 (src/cmd/5g/cgen.cの例):

void
bgen(Node *n, int true, int likely, Prog *to)
{
    // ... 既存のロジック ...
    // 例: OLITERALの場合
    case OLITERAL:
        if(!true == !n->val.u.bval)
            patch(gbranch(AB, T, 0), to); // likely引数が追加
        goto ret;
    // ...
    // 例: OANDANDの場合
    caseand:
        p1 = gbranch(AB, T, 0); // likely引数が追加
        p2 = gbranch(AB, T, 0); // likely引数が追加
        patch(p1, pc);
        bgen(n->left, !true, -likely, p2); // likely引数が伝播
        bgen(n->right, !true, -likely, p2); // likely引数が伝播
        p1 = gbranch(AB, T, 0); // likely引数が追加
        patch(p1, to);
        patch(p2, pc);
        goto ret;
    // ...
}

• likely引数の追加: bgen関数もlikely引数を受け取るようになりました。
• gbranchへのlikelyの伝播: bgenの内部でgbranchを呼び出す際に、この新しいlikely引数が渡されます。これにより、ブール式の評価結果に基づく最終的な分岐命令に、適切な分岐予測ヒントが適用されます。
• 論理演算子におけるlikelyの伝播: OANDANDやOORORのような論理演算子の場合、bgenは再帰的に自身を呼び出します。この際、likely引数が適切に反転されたり（例: !trueの場合に-likely）、そのまま伝播されたりすることで、複合的な条件分岐全体にわたって分岐予測ヒントが適用されるようになっています。

これらの変更により、コンパイラはより詳細な分岐予測ヒントを生成されるアセンブリコードに埋め込むことが可能になり、CPUの効率的なパイプライン処理と分岐予測に貢献します。特にループのような頻繁に実行されるコードパスにおいて、この最適化はパフォーマンスに良い影響を与えることが期待されます。

関連リンク

• Go Change-Id: I2222222222222222222222222222222222222222 (コミットメッセージに記載のCL 6245069に対応するGoの内部変更ID)
• Go CL 6245069: https://golang.org/cl/6245069

参考にした情報源リンク

• Go compiler source code (特に src/cmd/gc, src/cmd/5g, src/cmd/6g, src/cmd/8g ディレクトリ)
• Branch predictor - Wikipedia
• CPUパイプライン - Wikipedia
• Go compiler internals (general knowledge) (一般的なGoコンパイラの内部構造に関する知識)
• Understanding the Go source code (Goソースコードの理解に関する一般的な情報)
• Go issue tracker (for related CLs) (関連する変更履歴や議論を検索する際に利用)
• Go benchmarks (Goのベンチマークに関する一般的な情報)