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

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

このコミットは、Goコンパイラのcmd/8g（x86アーキテクチャ向けコンパイラ）において、レジスタ最適化（regopt）の前に、明らかに不要な一時変数（テンポラリ）を排除する新しい最適化パスを導入するものです。これにより、特に算術演算が多用される関数において、スタック変数の使用量を大幅に削減し、パフォーマンスを向上させます。

コミット

commit fa316ba4d85b4b5df3f47ac3ac8dfbdbedcc2948
Author: Rémy Oudompheng <oudomphe@phare.normalesup.org>
Date:   Tue Nov 13 07:39:18 2012 +0100

    cmd/8g: eliminate obviously useless temps before regopt.
    
    This patch introduces a sort of pre-regopt peephole optimization.
    When a temporary is introduced that just holds a value for the
    duration of the next instruction and is otherwise unused, we
    elide it to make the job of regopt easier.
    
    Since x86 has very few registers, this situation happens very
    often. The result is large savings in stack variables for
    arithmetic-heavy functions.
    
    crypto/aes
    
    benchmark                 old ns/op    new ns/op    delta
    BenchmarkEncrypt               1301          392  -69.87%
    BenchmarkDecrypt               1309          368  -71.89%\n    BenchmarkExpand                2913         1036  -64.44%
    benchmark                  old MB/s     new MB/s  speedup
    BenchmarkEncrypt              12.29        40.74    3.31x
    BenchmarkDecrypt              12.21        43.37    3.55x
    
    crypto/md5
    
    benchmark                 old ns/op    new ns/op    delta
    BenchmarkHash8Bytes            1761          914  -48.10%
    BenchmarkHash1K               16912         5570  -67.06%
    BenchmarkHash8K              123895        38286  -69.10%
    benchmark                  old MB/s     new MB/s  speedup
    BenchmarkHash8Bytes            4.54         8.75    1.93x
    BenchmarkHash1K               60.55       183.83    3.04x
    BenchmarkHash8K               66.12       213.97    3.24x
    
    bench/go1
    
    benchmark                 old ns/op    new ns/op    delta
    BenchmarkBinaryTree17    8364835000   8303154000   -0.74%
    BenchmarkFannkuch11      7511723000   6381729000  -15.04%
    BenchmarkGobDecode         27764090     27103270   -2.38%
    BenchmarkGobEncode         11240880     11184370   -0.50%
    BenchmarkGzip            1470224000    856668400  -41.73%
    BenchmarkGunzip           240660800    201697300  -16.19%
    BenchmarkJSONEncode       155225800    185571900  +19.55%
    BenchmarkJSONDecode       243347900    282123000  +15.93%
    BenchmarkMandelbrot200     12240970     12201880   -0.32%
    BenchmarkParse              8837445      8765210   -0.82%
    BenchmarkRevcomp         2556310000   1868566000  -26.90%
    BenchmarkTemplate         389298000    379792000   -2.44%
    benchmark                  old MB/s     new MB/s  speedup
    BenchmarkGobDecode            27.64        28.32    1.02x
    BenchmarkGobEncode            68.28        68.63    1.01x
    BenchmarkGzip                 13.20        22.65    1.72x
    BenchmarkGunzip               80.63        96.21    1.19x
    BenchmarkJSONEncode           12.50        10.46    0.84x
    BenchmarkJSONDecode            7.97         6.88    0.86x
    BenchmarkParse                 6.55         6.61    1.01x
    BenchmarkRevcomp              99.43       136.02    1.37x
    BenchmarkTemplate              4.98         5.11    1.03x
    
    Fixes #4035.
    
    R=golang-dev, minux.ma, rsc
    CC=golang-dev
    https://golang.org/cl/6828056

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

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

元コミット内容

cmd/8g: eliminate obviously useless temps before regopt.

This patch introduces a sort of pre-regopt peephole optimization.
When a temporary is introduced that just holds a value for the
duration of the next instruction and is otherwise unused, we
elide it to make the job of regopt easier.

Since x86 has very few registers, this situation happens very
often. The result is large savings in stack variables for
arithmetic-heavy functions.

crypto/aes

benchmark                 old ns/op    new ns/op    delta
BenchmarkEncrypt               1301          392  -69.87%
BenchmarkDecrypt               1309          368  -71.89%
BenchmarkExpand                2913         1036  -64.44%
benchmark                  old MB/s     new MB/s  speedup
BenchmarkEncrypt              12.29        40.74    3.31x
BenchmarkDecrypt              12.21        43.37    3.55x

crypto/md5

benchmark                 old ns/op    new ns/op    delta
BenchmarkHash8Bytes            1761          914  -48.10%
BenchmarkHash1K               16912         5570  -67.06%
BenchmarkHash8K              123895        38286  -69.10%
benchmark                  old MB/s     new MB/s  speedup
BenchmarkHash8Bytes            4.54         8.75    1.93x
BenchmarkHash1K               60.55       183.83    3.04x
BenchmarkHash8K               66.12       213.97    3.24x

bench/go1

benchmark                 old ns/op    new ns/op    delta
BenchmarkBinaryTree17    8364835000   8303154000   -0.74%
BenchmarkFannkuch11      7511723000   6381729000  -15.04%
BenchmarkGobDecode         27764090     27103270   -2.38%
BenchmarkGobEncode         11240880     11184370   -0.50%
BenchmarkGzip            1470224000    856668400  -41.73%
BenchmarkGunzip           240660800    201697300  -16.19%
BenchmarkJSONEncode       155225800    185571900  +19.55%
BenchmarkJSONDecode       243347900    282123000  +15.93%
BenchmarkMandelbrot200     12240970     12201880   -0.32%
BenchmarkParse              8837445      8765210   -0.82%
BenchmarkRevcomp         2556310000   1868566000  -26.90%
BenchmarkTemplate         389298000    379792000   -2.44%
benchmark                  old MB/s     new MB/s  speedup
BenchmarkGobDecode            27.64        28.32    1.02x
BenchmarkGobEncode            68.28        68.63    1.01x
BenchmarkGzip                 13.20        22.65    1.72x
BenchmarkGunzip               80.63        96.21    1.19x
BenchmarkJSONEncode           12.50        10.46    0.84x
BenchmarkJSONDecode            7.97         6.88    0.86x
BenchmarkParse                 6.55         6.61    1.01x
BenchmarkRevcomp              99.43       136.02    1.37x
BenchmarkTemplate              4.98         5.11    1.03x

Fixes #4035.

R=golang-dev, minux.ma, rsc
CC=golang-dev
https://golang.org/cl/6828056

変更の背景

このコミットの主な背景は、Goコンパイラが生成するコードのパフォーマンス最適化、特にx86アーキテクチャにおけるレジスタの制約への対応です。

x86アーキテクチャは、他の多くのアーキテクチャ（例えばARMやRISC-V）と比較して、汎用レジスタの数が少ないという特徴があります。コンパイラがコードを生成する際、計算の中間結果を一時的に保持するために「一時変数（temporary variables）」を多用します。これらの変数は、理想的にはCPUのレジスタに割り当てられるべきですが、レジスタが不足している場合、コンパイラはこれらの変数をメモリ（特にスタック）にスピル（spill）せざるを得なくなります。メモリへのアクセスはレジスタへのアクセスよりもはるかに遅いため、これがプログラムの実行速度を低下させる主要な要因となります。

Goコンパイラのレジスタ最適化（regopt）は、プログラム全体のレジスタ割り当てを最適化する重要なフェーズです。しかし、regoptが処理する命令列の中に、ごく短期間しか使用されない、つまり次の命令で消費され、その後は二度と参照されないような「明らかに不要な一時変数」が多数存在すると、regoptの作業が複雑になり、最適なレジスタ割り当てを妨げる可能性があります。regoptは、多くの変数を扱うほど、その複雑性が増し、場合によっては最適化の効率が低下したり、最適化自体を諦めたりすることもあります。

この問題に対処するため、regoptの前に、このような「明らかに不要な一時変数」を特定し、排除する「プリ・レジスタ最適化（pre-regopt）のピーホール最適化」が導入されました。これにより、regoptに渡される命令列がよりシンプルになり、regoptがより効果的に機能し、結果としてスタック変数の使用が減り、パフォーマンスが向上します。特に、暗号化アルゴリズムのように算術演算が頻繁に行われるコードでは、この種の最適化が大きな効果を発揮します。コミットメッセージに記載されているcrypto/aesやcrypto/md5のベンチマーク結果は、この最適化がもたらす劇的なパフォーマンス改善を明確に示しています。

前提知識の解説

コンパイラの最適化フェーズ

コンパイラは、ソースコードを機械語に変換する過程で、生成されるコードの効率を向上させるために様々な最適化を行います。一般的な最適化フェーズには以下のようなものがあります。

  • フロントエンド: 字句解析、構文解析、意味解析を行い、中間表現（IR: Intermediate Representation）を生成します。
  • 中間コード最適化: ターゲットアーキテクチャに依存しない形で、中間表現に対して様々な最適化を適用します（例: 定数畳み込み、デッドコード削除、ループ最適化）。
  • バックエンド: 中間表現をターゲットアーキテクチャの機械語に変換します。このフェーズでレジスタ割り当てや命令スケジューリングなどの最適化が行われます。

レジスタ割り当て（Register Allocation）とレジスタ最適化（Register Optimization, Regopt）

レジスタ割り当ては、コンパイラのバックエンドにおける最も重要な最適化の一つです。プログラム中の変数をCPUの高速なレジスタに割り当てることで、メモリへのアクセスを減らし、実行速度を向上させます。レジスタは数が限られているため、どの変数をどのレジスタに割り当てるか、いつメモリに退避（スピル）させるか、いつレジスタに戻すか（リロード）を決定する複雑な問題です。

Goコンパイラにおけるregoptは、このレジスタ割り当てと最適化を担当するモジュールを指します。

ピーホール最適化（Peephole Optimization）

ピーホール最適化は、コンパイラの最適化手法の一つで、生成されたコードの小さな「窓（peephole）」、つまり数命令のシーケンスを検査し、より効率的な同等のシーケンスに置き換えるものです。局所的な最適化であり、通常は他のより広範囲な最適化の後に適用されます。このコミットでは、regoptの前に適用される「プリ・レジスタ最適化」として、このピーホール最適化の概念が用いられています。

一時変数（Temporary Variables）とスタック変数（Stack Variables）

  • 一時変数: コンパイラが中間コード生成の過程で、複雑な式の中間結果を保持するために内部的に生成する変数です。ソースコードには直接現れません。
  • スタック変数: 関数内で宣言されたローカル変数や、レジスタに割り当てられなかった一時変数が、実行時スタック上に確保されるメモリ領域に格納される場合に「スタック変数」と呼ばれます。スタックへのアクセスはレジスタアクセスよりも遅いため、可能な限りレジスタに割り当てることが望ましいです。

x86アーキテクチャのレジスタ制約

x86（特に32ビット版）は、他の多くのCPUアーキテクチャと比較して、汎用レジスタの数が少ないという特徴があります（例: EAX, EBX, ECX, EDX, EBP, ESP, ESI, EDIなど）。このレジスタの少なさが、コンパイラが効率的なコードを生成する上での大きな課題となります。レジスタが不足すると、頻繁にメモリへのスピルが発生し、パフォーマンスが低下します。

FNV-1ハッシュ関数

fnv1関数は、FNV-1（Fowler-Noll-Vo hash function）アルゴリズムを実装しています。これは、高速で衝突が少ないことで知られる非暗号学的ハッシュ関数です。このコミットでは、スタック変数の参照回数を近似的にカウントするために、変数名（シンボル）のハッシュ値を計算し、それをハッシュテーブルのインデックスとして使用しています。

  • FNV-1アルゴリズムの概要:
    1. 初期ハッシュ値（FNV_offset_basis）を設定します。
    2. 入力データの各バイトに対して、現在のハッシュ値にFNV_primeを乗算し、その結果と現在のバイトのXORを取ります。
    3. この操作をすべてのバイトに対して繰り返します。

このコミットでは、FNV_offset_basisとして2166136261U（32ビットFNV-1の標準的なオフセット基底）、FNV_primeとして16777619（32ビットFNV-1の標準的な素数）が使用されています。

技術的詳細

このコミットで導入された主要な最適化は、fixtemp関数によって実現されます。この関数は、レジスタ最適化（regopt）の前に実行され、特定のパターンを持つ命令シーケンスを識別し、最適化します。

具体的には、以下のような命令シーケンスをターゲットとします。

MOV reg1, mem   ; reg1 の値を一時変数 mem に移動
OP  mem, reg2   ; mem の値と reg2 を使って演算し、結果を reg2 に格納

ここで、memはスタック上に割り当てられた一時変数であり、このMOV命令で書き込まれた後、次のOP命令で読み込まれるだけで、それ以降はプログラムのどこからも参照されないことが「明らかに不要」と判断される条件です。

fixtemp関数は、このようなシーケンスを以下のように変換します。

OP  reg1, reg2  ; reg1 の値と reg2 を使って演算し、結果を reg2 に格納

これにより、中間の一時変数memへのMOV命令が完全に削除され、memがスタックに割り当てられる必要がなくなります。これは、レジスタの利用効率を高め、メモリへのスピルを減らすことに直結します。

fixtempの動作原理

  1. 変数参照のカウント（近似）: fixtempはまず、プログラム内の各スタック変数（D_AUTOタイプ）がどれくらいの頻度で参照されているかを近似的にカウントします。これは、fnv1ハッシュ関数とhash32to16関数を使用して変数名から16ビットのハッシュ値を生成し、そのハッシュ値をインデックスとしてcounts配列（サイズ1<<16、つまり65536エントリ）をインクリメントすることで行われます。

    • counts[h] < 10という条件があるため、参照回数が10回を超えるとそれ以上カウントされません。これは、正確な参照カウントではなく、単一の書き込みと単一の読み込み（つまり参照回数が2回）のパターンを効率的に検出するためのヒューリスティックです。
    • ハッシュ衝突の可能性があるため、このカウントは「近似」です。しかし、この最適化の目的（「明らかに不要な」一時変数の排除）には十分な精度を提供します。

  2. シーケンスの識別と最適化: 次に、fixtempは命令列を走査し、以下の条件を満たすMOV命令（p）を探します。

    • pの次の命令（p->link）が存在すること。
    • pのソースオペランド（p->from）がレジスタ（RtoB(p->from.type)）であること。
    • pのデスティネーションオペランド（p->to）がスタック変数（D_AUTO）であること。
    • pのデスティネーションオペランドが浮動小数点型ではないこと（浮動小数点レジスタの扱いが異なるため）。
    • pがAMOVB, AMOVW, AMOVLのいずれかであり、かつその幅がデスティネーションの幅と一致すること（バイト、ワード、ロングワードの移動命令）。

    上記の条件を満たすMOV命令pが見つかった場合、そのデスティネーションである一時変数p->to.symのハッシュ値を計算し、counts配列で参照回数をチェックします。

    • counts[h] != 2の場合、その一時変数は単一の書き込みと単一の読み込みのパターンではないため、最適化の対象外となります。
    • counts[h] == 2の場合、その一時変数はこのMOV命令で書き込まれ、次の命令で読み込まれる可能性が高いと判断されます。

    次に、pの次の命令p2をチェックします。

    • p2がALEAL, AFMOVL, AFMOVW, AFMOVVのような特殊な命令でないこと（これらの命令はアドレス計算や浮動小数点移動であり、単純なオペランド置換ができない場合があるため）。
    • p2のソースオペランド（p2->from）が、pのデスティネーションオペランド（p->to）と完全に一致すること（同じシンボル、オフセット、タイプ）。

    これらのすべての条件が満たされた場合、p2は「OP mem, reg2」の形式であり、memはpによって書き込まれた一時変数であると確定します。 このとき、fixtempは以下の変換を行います。

    • p2のソースオペランドをpのソースオペランド（reg1）に置き換えます: p2->from = p->from;
    • pの命令をp2の命令で上書きします: *p = *p2;
    • pの次の命令をp2の次の命令に設定します: p->link = p2->link; これにより、元のMOV命令pは実質的に削除され、p2の命令がpの位置に移動し、memへのアクセスがreg1へのアクセスに置き換えられます。

この最適化は、特にx86のようなレジスタが少ないアーキテクチャにおいて、コンパイラが生成するコードの品質を大幅に向上させます。一時変数をスタックにスピルする頻度が減ることで、メモリ帯域の消費が抑えられ、CPUのキャッシュ効率も向上し、結果として実行速度が向上します。

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

変更はsrc/cmd/8g/reg.cファイルに集中しています。

  1. fixtemp関数のプロトタイプ宣言の追加:

    static void fixtemp(Prog*);

    regopt関数の前にfixtemp関数が呼び出されるように、プロトタイプが追加されています。

  2. regopt関数内でのfixtempの呼び出し:

    regopt(Prog *firstp)
{
    // ... 既存のコード ...
    fixtemp(firstp); // ここで新しく追加されたfixtempが呼び出される
    fixjmp(firstp);
    // ... 既存のコード ...
}

    regoptの初期段階でfixtempが呼び出されることで、レジスタ最適化が始まる前に不要な一時変数が排除されます。

  3. fnv1関数の追加:

    static uint32
fnv1(Sym *sym)
{
    uint32 h;
    char *s;

    h = 2166136261U;
    for(s=sym->name;*s;s++) {
        h = (16777619 * h) ^ (uint32)(uint8)(*s);
    }
    return h;
}

    シンボル名からFNV-1ハッシュを計算するヘルパー関数が追加されています。

  4. hash32to16関数の追加:

    static uint16
hash32to16(uint32 h)
{
    return (h & 0xffff) ^ (h >> 16);
}

    32ビットハッシュ値を16ビットに縮小するヘルパー関数が追加されています。これは、counts配列のインデックスとして使用するためです。

  5. fixtemp関数の実装: fixtemp関数の本体が追加されています。この関数は、前述の「技術的詳細」セクションで説明したロジックに従って、不要な一時変数を排除するピーホール最適化を実行します。

コアとなるコードの解説

fixtemp関数は、Goコンパイラのcmd/8g（x86アセンブラ）の最適化パスの一部として、レジスタ最適化（regopt）の前に実行されます。その目的は、レジスタ割り当てを容易にするために、ごく短期間しか使用されない一時変数（スタック変数）を排除することです。

void
fixtemp(Prog *firstp)
{
    static uint8 counts[1<<16]; // 変数参照カウント用のハッシュテーブル
    int i;
    Prog *p, *p2;
    uint32 h;

    if(debug['R'] && debug['v'])
        print("\nfixtemp\n");

    // 1. 変数参照の近似カウント
    // プログラム内のすべての命令を走査し、D_AUTO (スタック変数) タイプのオペランドの参照をカウントする。
    // FNV-1ハッシュと16ビットへの縮小を使って、ハッシュテーブルにカウントを格納。
    // counts[h] < 10 の条件で、カウントは最大9までしか増えない。
    for(i=0; i<nelem(counts); i++)
        counts[i] = 0; // counts配列を初期化
    for(p=firstp; p!=P; p=p->link) { // 命令リストを走査
        if(p->from.type == D_AUTO) { // ソースオペランドがスタック変数なら
            h = hash32to16(fnv1(p->from.sym)); // シンボル名からハッシュ値を計算
            if(counts[h] < 10)
                counts[h]++; // カウントをインクリメント
        }
        if(p->to.type == D_AUTO) { // デスティネーションオペランドがスタック変数なら
            h = hash32to16(fnv1(p->to.sym)); // シンボル名からハッシュ値を計算
            if(counts[h] < 10)
                counts[h]++; // カウントをインクリメント
        }
    }

    // 2. 単一書き込み、単一読み込みのスタック変数を排除
    // 命令リストを再度走査し、特定のパターンを識別して最適化する。
    for(p=firstp; p!=P; p=p->link) { // 命令リストを走査
        if(debug['R'] && debug['v'])
            print("%P\n", p);

        // 最適化対象のMOV命令の条件チェック
        // - 次の命令が存在すること
        // - ソースオペランドがレジスタであること (RtoBはレジスタタイプをチェックするマクロ)
        // - デスティネーションオペランドがスタック変数であること (D_AUTO)
        // - デスティネーションオペランドが浮動小数点型ではないこと
        if(p->link == P
            || !RtoB(p->from.type)
            || p->to.type != D_AUTO
            || isfloat[p->to.etype])
            continue; // 条件を満たさない場合はスキップ

        // MOV命令のタイプチェック (バイト、ワード、ロングワード)
        switch(p->as) {
        case AMOVB:
            if(p->to.width == 1) break;
        case AMOVW:
            if(p->to.width == 2) break;
        case AMOVL:
            if(p->to.width == 4) break;
        default:
            continue; // MOV命令でないか、幅が一致しない場合はスキップ
        }
        // ここに到達した場合、p は "MOV reg, mem" の形式の命令である。

        p2 = p->link; // 次の命令を取得
        h = hash32to16(fnv1(p->to.sym)); // MOV命令のデスティネーション変数 (mem) のハッシュ値を取得

        // 変数の参照カウントが2であることのチェック
        // これは、その変数がこのMOV命令で書き込まれ、次の命令で読み込まれるだけの「一時変数」であることを示唆する。
        if(counts[h] != 2) {
            continue; // 参照カウントが2でない場合はスキップ
        }

        // 次の命令 p2 のタイプチェック (特殊な命令はスキップ)
        switch(p2->as) {
        case ALEAL: // Load Effective Address
        case AFMOVL: // Floating Point Move Long
        case AFMOVW: // Floating Point Move Word
        case AFMOVV: // Floating Point Move Double
            // これらの命令は特殊なセマンティクスを持つため、単純なオペランド置換は避ける
            continue;
        }
        // ここに到達した場合、p2 は "OP mem, reg2" の形式の命令である。

        // p2 のソースオペランドが p のデスティネーションオペランドと完全に一致することを確認
        if(p2->from.sym == p->to.sym
            && p2->from.offset == p->to.offset
            && p2->from.type == p->to.type) {
            // 最適化の実行:
            // p2 のソースオペランドを p のソースオペランド (reg1) に置き換える
            p2->from = p->from;
            // p の命令を p2 の命令で上書きする (p2 は実質的に削除される)
            *p = *p2;
            // p の次の命令を p2 の次の命令に設定する (命令リストから p2 を削除する)
            p->link = p2->link;

            if(debug['R'] && debug['v']) {
                print(" ===change== %P\n", p);
            }
        }
    }
}

このコードは、Goコンパイラのバックエンドにおける低レベルな最適化の典型例であり、ターゲットアーキテクチャ（x86）の特性（レジスタの少なさ）を考慮して設計されています。

関連リンク

参考にした情報源リンク