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

このコミットは、Goコンパイラのcmd/gc（共通フロントエンド）および各アーキテクチャ固有のバックエンド（5g for ARM, 8g for x86, 6g for amd64）において、定数による除算（ODIV）および剰余（OMOD）演算を、より効率的なシフト演算や「マジック乗算」（magic multiplies）に書き換える最適化を導入するものです。これにより、特に32ビットアーキテクチャでの除算性能が向上します。64ビット算術の最適化は6g（amd64）に限定され、他のアーキテクチャでは関数呼び出しにフォールバックします。

コミット

commit 4cc9de914764679defbffd77b30e80a325e4ebd0
Author: Rémy Oudompheng <oudomphe@phare.normalesup.org>
Date:   Mon Nov 26 23:45:22 2012 +0100

    cmd/gc: add division rewrite to walk pass.
    
    This allows 5g and 8g to benefit from the rewrite as shifts
    or magic multiplies. The 64-bit arithmetic is not handled there,
    and left in 6g.
    
    Update #2230.
    
    R=golang-dev, dave, mtj, iant, rsc
    CC=golang-dev
    https://golang.org/cl/6819123

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

https://github.com/golang/go/commit/4cc9de914764679defbffd77b30e80a325e4ebd0

元コミット内容

cmd/gc: add division rewrite to walk pass.

This allows 5g and 8g to benefit from the rewrite as shifts
or magic multiplies. The 64-bit arithmetic is not handled there,
and left in 6g.

Update #2230.

R=golang-dev, dave, mtj, iant, rsc
CC=golang-dev
https://golang.org/cl/6819123

変更の背景

この変更の背景には、Issue 2230（Update #2230と記載）があります。このIssueは、Goコンパイラが定数による除算を最適化できていないというパフォーマンス上の問題に対処するためのものです。特に、除算はCPUにとって比較的コストの高い演算であり、コンパイル時に除数が定数であることが分かっている場合、より高速なビットシフトや乗算（マジック乗算）に置き換えることで、生成されるコードの実行速度を大幅に向上させることができます。

従来のGoコンパイラでは、この最適化が十分に適用されていませんでした。このコミットは、cmd/gcのwalkパス（中間表現の変換フェーズ）にこの最適化ロジックを組み込むことで、5g（ARM）や8g（x86）といった32ビットアーキテクチャでもこの恩恵を受けられるようにすることを目的としています。ただし、64ビット算術の最適化はより複雑であるため、このコミット時点では6g（amd64）に限定されています。

前提知識の解説

• cmd/gc: Goコンパイラの共通フロントエンド部分です。Goのソースコードを解析し、抽象構文木（AST）を生成し、型チェックや一部の最適化を行います。その後、各アーキテクチャ固有のバックエンドに中間表現を渡します。
• 5g, 8g, 6g: Goコンパイラの各アーキテクチャ固有のバックエンドです。
  • 5g: ARMアーキテクチャ向けのコンパイラ。
  • 8g: x86（32ビット）アーキテクチャ向けのコンパイラ。
  • 6g: amd64（64ビット）アーキテクチャ向けのコンパイラ。
• walk pass: cmd/gcにおけるコンパイルフェーズの一つで、抽象構文木（AST）を走査（walk）しながら、より低レベルな中間表現に変換したり、特定の最適化を行ったりします。このコミットでは、除算の最適化がこのwalkパスに追加されました。
• division rewrite: 除算演算を、より高速な別の演算（シフトや乗算）に置き換える最適化手法です。特に除数が定数である場合に有効です。
• magic multiplies (マジック乗算): 除算を乗算とビットシフトの組み合わせで実現する最適化手法です。整数除算 N / D は、特定の「マジックナンバー」M を用いて (N * M) >> S のように表現できる場合があります。これは、除算が乗算よりもCPUサイクルを多く消費するため、パフォーマンス向上に寄与します。特に、除数が2の冪乗でない場合に用いられます。
• ullman number: 式の評価順序を決定するために使用される値で、レジスタ割り当てのヒューリスティックに利用されます。値が小さいほど、そのノードを評価するために必要なレジスタが少ないことを示唆します。
• OMUL, OHMUL: Goコンパイラの中間表現における演算子の種類です。
  • OMUL: 通常の乗算。
  • OHMUL: "High Multiply" の略で、乗算結果の上位ワード（または上位ビット）を取得する演算です。例えば、32ビット数同士の乗算結果は最大64ビットになりますが、OHMULは結果の上位32ビットを返します。マジック乗算において、除算結果を得るためにこの上位ワードが必要になることがあります。
• OLITERAL: コンパイラの中間表現で、リテラル定数を表すノードです。
• powtwo(nr): nr（除数）が2の冪乗であるかどうかを判定し、その冪乗数を返す関数です。例えば、powtwo(8)は3を返します（2^3 = 8）。
• simtype: Goの型を、コンパイラ内部で扱う単純な型（TINT8, TUINT32など）にマッピングするための配列または関数。
• issigned: 型が符号付き整数であるかどうかを判定する配列または関数。
• typecheck: ASTノードの型チェックを行う関数。
• cheapexpr: 式を評価し、その結果を一時的な変数に格納するなどして、後続の処理で再利用できるようにする関数。
• nod: 新しいASTノードを作成する関数。
• nodconst: 定数値を表すASTノードを作成する関数。
• conv: 型変換を行う関数。
• mkcall: 関数呼び出しを表すASTノードを作成する関数。
• regalloc, regfree: レジスタの割り当てと解放を行う関数。
• gmove: 値をある場所から別の場所へ移動させる（コピーする）命令を生成する関数。
• gins: アセンブリ命令を生成する関数。
• savex, restx: レジスタの値を保存・復元する関数。特に、特定のレジスタ（例: D_AX, D_DX）が特定の操作で破壊される可能性がある場合に用いられます。
• D_AX, D_DX: x86アーキテクチャにおけるレジスタ名。除算や乗算などの特定の命令で暗黙的に使用されます。
• TINT8, TINT16, TINT32, TINT64, TUINT8, TUINT16, TUINT32, TUINT64: Goコンパイラ内部で使われる整数型を表す定数。それぞれ符号付き/符号なしの8, 16, 32, 64ビット整数に対応します。
• widthptr: ポインタの幅（ビット数）を示すグローバル変数。32ビットシステムでは32、64ビットシステムでは64。
• isfloat, iscomplex: 型が浮動小数点数型または複素数型であるかを判定する関数。
• isfixedarray: 型が固定長配列であるかを判定する関数。
• isconst, CTINT, CTSTR: ノードが定数であるか、その定数の種類（整数定数、文字列定数）を判定する関数。
• mpgetfix: 多倍長整数（Mpint）から固定長の整数値を取得する関数。
• smagic, umagic: 符号付き/符号なし整数除算のためのマジックナンバーを計算する関数。
• bad: マジック乗算が適用できない場合に設定されるフラグ。
• tempname: 一時変数の名前を生成する関数。
• types: Goの組み込み型を表す配列。
• Erv: 式の評価結果が値として使用されることを示すフラグ。
• warn, yyerror: 警告やエラーメッセージを出力する関数。

技術的詳細

このコミットの主要な技術的詳細は、cmd/gc/walk.c内のwalkdiv関数と、各アーキテクチャ固有のggen.cファイルに実装されたcgen_hmul関数にあります。

1. walkdiv関数（src/cmd/gc/walk.c）:

   • この関数は、除算（ODIV）または剰余（OMOD）演算のASTノードを受け取ります。
   • まず、除数（n->right）がOLITERAL（定数）であるかどうかをチェックします。定数でない場合は、最適化を行わずに通常の除算処理にフォールバックします。
   • 2の冪乗による除算/剰余の最適化:
     • powtwo(nr)を使用して、除数が2の冪乗であるかを判定します。
     • もし2の冪乗であれば、除算は右シフト（ORSH）に、剰余はビットAND（OAND）に変換されます。
     • 符号付き整数に対する除算/剰余の場合、負の数に対する挙動が異なるため、特別な処理（例えば、nlが負の場合に2^pow-1を加算してからシフトするなど）が導入されます。これは、C言語の>>演算子が算術右シフトであり、負の数に対しては切り捨ての挙動が異なるためです。
   • マジック乗算による除算の最適化:
     • 除数が2の冪乗でない定数の場合、smagic（符号付き）またはumagic（符号なし）関数を呼び出して、マジックナンバー（m.umまたはm.sm）とシフト量（m.s）を計算します。これらの値は、"Hacker's Delight" の第10章に記載されているアルゴリズムに基づいています。
     • 計算されたマジックナンバーとシフト量を用いて、除算をOHMUL（高位乗算）とビットシフトの組み合わせに変換します。
     • m.ua（符号なし）またはm.sm < 0（符号付き）の場合、オーバーフローを考慮して分子を加算する追加の処理が必要になります。
     • 剰余演算（OMOD）の場合、A % B = A - (A / B * B)という関係を利用して、除算をマジック乗算で計算した後、乗算と減算に変換します。
   • 64ビット算術のフォールバック:
     • widthptr > 4（つまり64ビットシステムでない場合）かつ、型がTUINT64またはTINT64である場合、この最適化は適用されず、代わりにmkcallを使用してランタイム関数（例: int64div, uint64mod）への呼び出しに変換されます。これは、32ビットシステムで64ビット除算を直接アセンブリで効率的に実装するのが難しいためです。

2. cgen_hmul関数（src/cmd/5g/ggen.c, src/cmd/6g/ggen.c, src/cmd/8g/ggen.c）:

   • この関数は、OHMUL演算子に対応するアセンブリコードを生成します。
   • nlとnrの2つのノード（オペランド）を受け取り、その乗算結果の上位ワードをresに格納します。
   • 各アーキテクチャ（ARM, x86, amd64）で、それぞれの命令セットに合わせた高位乗算命令（例: x86のIMUL命令で結果の上位ワードがDXレジスタに格納される挙動を利用）を生成します。
   • 特に、8ビットの乗算は他のビット幅と挙動が異なるため、特別な処理が施されています。

この最適化により、コンパイル時に除数が定数であることが判明している場合、実行時の除算命令の代わりに、より高速な乗算とシフト命令が生成されるようになります。

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

主要な変更は以下のファイルに集中しています。

• src/cmd/gc/walk.c:
  • walkexpr関数内で、ODIVおよびOMOD演算子に対する処理が追加され、walkdiv関数が呼び出されるようになりました。
  • 新しい静的関数walkdivが追加され、定数除算の最適化ロジックが実装されました。
• src/cmd/5g/cgen.c, src/cmd/5g/gg.h, src/cmd/5g/ggen.c, src/cmd/5g/peep.c:
  • ARMアーキテクチャ（5g）向けにOHMUL演算子を処理するためのcgen_hmul関数が追加され、関連するヘッダファイルやコード生成ロジックが更新されました。
• src/cmd/6g/cgen.c, src/cmd/6g/gg.h, src/cmd/6g/ggen.c, src/cmd/6g/peep.c:
  • amd64アーキテクチャ（6g）向けにOHMUL演算子を処理するためのcgen_hmul関数が追加され、関連するヘッダファイルやコード生成ロジックが更新されました。
  • cgen_div関数から、定数除算の最適化ロジックが削除され、walkdivに一元化されました。
• src/cmd/8g/cgen.c, src/cmd/8g/gg.h, src/cmd/8g/ggen.c, src/cmd/8g/gsubr.c:
  • x86アーキテクチャ（8g）向けにOHMUL演算子を処理するためのcgen_hmul関数が追加され、関連するヘッダファイルやコード生成ロジックが更新されました。
  • optoas関数にOHMULに対応するアセンブリ命令（AIMULB, AIMULW, AIMULL, AMULB, AMULW, AMULL）のマッピングが追加されました。

コアとなるコードの解説

src/cmd/gc/walk.c の walkdiv 関数

static void
walkdiv(Node **np, NodeList **init)
{
    Node *n, *nl, *nr, *nc;
    Node *n1, *n2, *n3, *n4;
    int pow; // if >= 0, nr is 1<<pow
    int s; // 1 if nr is negative.
    int w;
    Type *twide;
    Magic m;

    n = *np;
    if(n->right->op != OLITERAL)
        return; // 除数が定数でない場合は何もしない

    nl = cheapexpr(n->left, init); // 被除数を評価
    nr = n->right; // 除数

    w = nl->type->width*8; // ビット幅
    s = 0;
    pow = powtwo(nr); // 除数が2の冪乗かチェック

    if(pow >= 1000) { // 負の2の冪乗の場合
        s = 1;
        pow -= 1000;
    }

    if(pow+1 >= w) { // 除数が大きすぎる場合
        return;
    }
    if(pow < 0) { // 2の冪乗でない場合、マジック乗算へ
        goto divbymul;
    }

    switch(pow) {
    case 0: // 除数が1または-1の場合
        if(n->op == OMOD) { // nl % 1 は 0
            nodconst(n, n->type, 0);
        } else if(s) { // nl / -1 は -nl
            n->op = OMINUS;
            n->right = N;
        } else { // nl / 1 は nl
            n = nl;
        }
        break;
    default: // 除数が2の冪乗の場合
        if(issigned[n->type->etype]) { // 符号付き整数
            if(n->op == OMOD) { // 符号付き剰余
                // 複雑なロジックで (nl + epsilon) & (nr-1) - epsilon を計算
                // epsilon は nl が負の場合に調整するための値
            } else { // 符号付き除算
                // 複雑なロジックで (nl + adjustment) >> pow を計算
                // adjustment は nl が負の場合に正しい切り捨てを行うための値
                n->op = ORSH; // 右シフトに変換
                nodconst(nc, types[simtype[TUINT]], pow);
                n->right = nc;
                n->typecheck = 0;
            }
            if(s) // 除数が負の場合、結果を反転
                n = nod(OMINUS, n, N);
            break;
        }
        // 符号なし整数
        nc = nod(OXXX, N, N);
        if(n->op == OMOD) { // 符号なし剰余: nl & (nr-1)
            n->op = OAND;
            nodconst(nc, nl->type, mpgetfix(nr->val.u.xval)-1);
        } else { // 符号なし除算: nl >> pow
            n->op = ORSH;
            nodconst(nc, types[simtype[TUINT]], pow);
        }
        n->typecheck = 0;
        n->right = nc;
        break;
    }
    goto ret;

divbymul: // マジック乗算による除算
    m.w = w;
    if(issigned[nl->type->etype]) {
        m.sd = mpgetfix(nr->val.u.xval);
        smagic(&m); // 符号付きマジックナンバー計算
    } else {
        m.ud = mpgetfix(nr->val.u.xval);
        umagic(&m); // 符号なしマジックナンバー計算
    }
    if(m.bad) // マジック乗算が適用できない場合
        return;

    if(n->op == OMOD) // 剰余は A % B = A - (A/B * B) に変換
        goto longmod;

    switch(simtype[nl->type->etype]) {
    // ... (TUINT8, TUINT16, TUINT32, TINT8, TINT16, TINT32 の処理)
    // nl * magic >> w (OHMUL) を利用して除算を実装
    // 必要に応じて分子の加算や結果の調整を行う
    }
    goto ret;

longmod: // 剰余を A - (A/B * B) に変換
    n1 = nod(ODIV, nl, nr); // 除算
    n2 = nod(OMUL, n1, nr); // 乗算
    n = nod(OSUB, nl, n2); // 減算
    goto ret;

ret:
    typecheck(&n, Erv);
    walkexpr(&n, init);
    *np = n;
}

walkdiv関数は、除数が定数である場合に、その定数の性質（2の冪乗か、符号付きか符号なしなど）に応じて、除算や剰余をより効率的なビット演算やマジック乗算に変換します。特に、符号付き整数に対する2の冪乗による除算や剰余は、負の数に対する挙動が複雑なため、複数のステップで変換が行われます。マジック乗算は、OHMUL演算子を利用して、乗算結果の上位ワードを取得し、それをシフトすることで除算を実現します。

src/cmd/5g/ggen.c, src/cmd/6g/ggen.c, src/cmd/8g/ggen.c の cgen_hmul 関数

これらのファイルには、OHMUL演算子に対応するアセンブリコードを生成するcgen_hmul関数が追加されています。

例: src/cmd/6g/ggen.c の cgen_hmul

void
cgen_hmul(Node *nl, Node *nr, Node *res)
{
    Type *t;
    int a;
    Node n1, n2, ax, dx, *tmp;

    t = nl->type;
    a = optoas(OHMUL, t); // OHMULに対応するアセンブリ命令を取得
    if(nl->ullman < nr->ullman) { // ullman number に基づいてオペランドを入れ替え
        tmp = nl;
        nl = nr;
        nr = tmp;
    }
    cgenr(nl, &n1, res); // nl をレジスタ n1 に生成
    cgenr(nr, &n2, N); // nr をレジスタ n2 に生成

    nodreg(&ax, t, D_AX); // AX レジスタのノードを作成
    gmove(&n1, &ax); // n1 の値を AX レジスタに移動
    gins(a, &n2, N); // n2 をオペランドとして高位乗算命令を生成 (結果は AX/DX に)
    regfree(&n2);
    regfree(&n1);

    if(t->width == 1) { // 8ビット乗算の特殊処理
        // byte multiply behaves differently.
        nodreg(&ax, t, D_AH);
        nodreg(&dx, t, D_DL);
        gmove(&ax, &dx);
    }
    nodreg(&dx, t, D_DX); // DX レジスタのノードを作成
    gmove(&dx, res); // DX レジスタの値を結果レジスタ res に移動
}

cgen_hmul関数は、各アーキテクチャの特性に合わせて、高位乗算を行うアセンブリ命令を生成します。x86/amd64アーキテクチャでは、IMUL命令（符号付き乗算）やMUL命令（符号なし乗算）が使用され、これらの命令は乗算結果の上位ワードを特定のレジスタ（通常はDX）に格納します。cgen_hmulはこのDXレジスタの値を結果として返すようにコードを生成します。ARMアーキテクチャでも同様に、高位乗算をサポートする命令が利用されます。

これらの変更により、Goコンパイラは定数除算をより効率的な命令シーケンスに変換できるようになり、生成されるバイナリのパフォーマンスが向上します。

関連リンク

• Go CL 6819123: https://golang.org/cl/6819123
• Go Issue 2230: https://golang.org/issue/2230

参考にした情報源リンク

• Hacker's Delight (Second Edition) by Henry S. Warren, Jr. - Chapter 10: Integer Division (マジック乗算のアルゴリズムに関する詳細)
• Go Compiler Source Code (特に src/cmd/gc/walk.c, src/cmd/5g/ggen.c, src/cmd/6g/ggen.c, src/cmd/8g/ggen.c の関連部分)
• x86 Instruction Set Reference (IMUL, MUL 命令の動作に関する情報)
• ARM Architecture Reference Manual (高位乗算命令に関する情報)
• Go言語のコンパイラに関するドキュメントやブログ記事 (一般的なコンパイラの構造や最適化に関する情報)
• https://go.dev/doc/articles/go-compiler-walk (Goコンパイラのwalkパスに関する一般的な情報)
• https://go.dev/doc/articles/go-compiler-backend (Goコンパイラのバックエンドに関する一般的な情報)