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

このコミットは、Goコンパイラ（cmd/gcおよび各アーキテクチャ固有のバックエンド）におけるコード生成の最適化に焦点を当てています。特に、ビットローテーション操作の効率化、既知の小さなシフト量に対する境界チェックの削除、およびより積極的な範囲分析の導入により、生成されるバイナリのパフォーマンス向上を目指しています。

コミット

commit c6ce44822c5dba80ed8a2c3e5ebbd86e1a185dd1
Author: Russ Cox <rsc@golang.org>
Date:   Thu May 24 17:20:07 2012 -0400

    cmd/gc: faster code, mainly for rotate

    * Eliminate bounds check on known small shifts.
    * Rewrite x<<s | x>>(32-s) as a rotate (constant s).
    * More aggressive (but still minimal) range analysis.

    R=ken, dave, iant
    CC=golang-dev
    https://golang.org/cl/6209077

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

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

元コミット内容

このコミットは、Goコンパイラ（cmd/gc）のコード生成を高速化することを目的としており、主に以下の3つの主要な変更を含んでいます。

1. 既知の小さなシフト量に対する境界チェックの削除: シフト演算（<<, >>）において、シフト量がコンパイル時に安全な範囲内であることが判明している場合、実行時の不要な境界チェックを省略します。これにより、生成されるコードのオーバーヘッドが削減され、実行速度が向上します。
2. x<<s | x>>(32-s) をローテーションとして書き換え（定数 s の場合）: ビットローテーションは、特定のビットパターンを循環的にシフトする操作です。多くのプログラミング言語には直接的なローテーション演算子がないため、x<<s | x>>(WIDTH-s)（WIDTHはビット幅、例: 32または64）のような組み合わせで表現されることが一般的です。このコミットでは、コンパイラがこのパターンを認識し、ターゲットアーキテクチャがサポートしていれば、より効率的な単一のローテーション命令（例: x86のROL/ROR）に置き換えるようにします。これにより、特に暗号化アルゴリズムなどで頻繁に使用されるローテーション操作のパフォーマンスが大幅に向上します。
3. より積極的な（しかし最小限の）範囲分析: コンパイラが変数の取りうる値の範囲をより詳細に分析するようになります。この改善された範囲分析は、前述の境界チェックの削除や、その他の最適化（例えば、特定の条件分岐の削除など）を可能にする基盤となります。

変更の背景

このコミットの背景には、Goプログラムの実行効率をさらに高めるという目標があります。特に、ビット操作は低レベルの処理や数値計算、暗号化などで頻繁に利用されます。

• パフォーマンスの向上: ビットローテーションは、ハッシュ関数や暗号化アルゴリズム（例: MD5、SHA-1、AESなど）で頻繁に登場する操作です。これらのアルゴリズムは計算負荷が高いため、ローテーション操作をCPUのネイティブ命令にマッピングすることで、大幅な速度向上が期待できます。従来のシフトとORの組み合わせは複数のCPU命令を必要とし、オーバーヘッドがありました。
• コードの簡潔化と効率化: コンパイラが共通のイディオム（x<<s | x>>(32-s)）を認識し、より効率的な命令に変換することで、開発者が手動でアセンブリレベルの最適化を意識する必要がなくなります。これは、Go言語の「シンプルさ」と「効率性」という設計哲学にも合致しています。
• 境界チェックの最適化: 配列アクセスやシフト操作における境界チェックは、プログラムの安全性を保証するために重要ですが、不要なチェックはパフォーマンスのボトルネックになります。コンパイラがより賢く境界チェックを省略できるようになることで、安全性を損なうことなく実行速度を向上させることができます。これは、特にループ内で頻繁にアクセスされるデータ構造において顕著な効果を発揮します。
• コンパイラのインテリジェンス向上: 範囲分析の強化は、コンパイラがプログラムの振る舞いをより深く理解し、より多くの最適化機会を見つけ出す能力を高めることを意味します。これは、将来的なさらなる最適化の基盤ともなります。

これらの変更は、Go言語がシステムプログラミングや高性能計算の分野でより競争力を持つための重要なステップと言えます。

前提知識の解説

1. ビット演算とビットローテーション

• ビット演算: コンピュータのデータはビット（0または1）の集まりで表現されます。ビット演算は、これらのビットに対して直接行われる論理操作です。
  • 左シフト (<<): ビットを左に指定された数だけ移動させます。右から0が埋められます。x << s は x * 2^s と同等です（オーバーフローを無視すれば）。
  • 右シフト (>>): ビットを右に指定された数だけ移動させます。符号なし整数では左から0が埋められます。符号あり整数では、最上位ビット（符号ビット）が複製されるか（算術右シフト）、0が埋められるか（論理右シフト）は言語や実装に依存します。Go言語では、符号なし整数は論理右シフト、符号あり整数は算術右シフトです。
  • ビットOR (|): 対応するビットのどちらか一方が1であれば結果は1、両方0であれば結果は0となります。
• ビットローテーション (Circular Shift): ビットをシフトする際に、桁からあふれたビットが反対側の端に戻ってくる操作です。例えば、32ビットの数値 x を左に s ビットローテーションする場合、x の最上位 s ビットが右端に移動し、残りのビットは左にシフトされます。
  • 左ローテーション (ROL - Rotate Left): x << s | x >> (WIDTH - s) で表現されます。
  • 右ローテーション (ROR - Rotate Right): x >> s | x << (WIDTH - s) で表現されます。
  • 多くのCPUアーキテクチャ（x86など）は、このローテーション操作を単一の命令（ROL, ROR）としてサポートしており、複数のシフトとOR命令を組み合わせるよりもはるかに高速です。

2. コンパイラの最適化

コンパイラ最適化とは、ソースコードを機械語に変換する際に、プログラムの実行速度を向上させたり、メモリ使用量を削減したりするために行われる変換のことです。

• パターン認識と命令選択: コンパイラは、特定のコードパターン（例: x<<s | x>>(32-s)）を認識し、それをターゲットCPUのより効率的なネイティブ命令（例: ROL）に置き換えることができます。これは「命令選択 (Instruction Selection)」と呼ばれる最適化の一種です。
• 境界チェックの削除 (Bounds Check Elimination): 配列やスライスへのアクセス時に、インデックスが有効な範囲内にあるかをチェックするコード（境界チェック）が自動的に挿入されます。これはプログラムの安全性を高めますが、頻繁に実行されるとオーバーヘッドになります。コンパイラは、インデックスが常に有効な範囲内にあることを静的に証明できる場合、このチェックを削除することができます。
• 範囲分析 (Range Analysis): コンパイラが変数の取りうる値の範囲を推論する技術です。例えば、ループ変数がある範囲内でしか変化しないことを特定したり、シフト量や配列インデックスが特定の最大値を超えないことを判断したりします。この分析結果は、境界チェックの削除や、より効率的なコード生成に利用されます。

3. Goコンパイラの構造

Go言語のコンパイラツールチェーンは、複数のコンポーネントから構成されています。

• cmd/gc: Go言語のフロントエンドコンパイラです。Goのソースコードを解析し、中間表現（IR）に変換します。型チェック、AST（抽象構文木）の変換、一部の最適化（このコミットで変更される範囲分析など）が行われます。
• cmd/5g, cmd/6g, cmd/8g: それぞれARM (5g), AMD64 (6g), x86 (8g) アーキテクチャ向けのバックエンドコンパイラです。gcから受け取った中間表現を、それぞれのアーキテクチャの機械語に変換し、最終的なバイナリを生成します。この段階で、命令選択やレジスタ割り当てなどのアーキテクチャ固有の最適化が行われます。

このコミットでは、gcでより高度な分析を行い、その結果を各バックエンドが利用して、より効率的な機械語を生成するように連携が強化されています。

技術的詳細

1. ビットローテーションの最適化 (x<<s | x>>(32-s) -> ROL)

この最適化は、Goコンパイラが特定のビット操作パターンを認識し、それをCPUのネイティブなローテーション命令に変換するものです。

• パターン認識: src/cmd/gc/walk.c の walkrotate 関数がこの最適化の核となります。この関数は、抽象構文木 (AST) を走査し、OOR (ビットOR) 演算子を持つノードをチェックします。その左右の子ノードがそれぞれ OLSH (左シフト) と ORSH (右シフト) であり、かつシフト対象のオペランドが同じである（例: x << s | x >> (32 - s) の x の部分）場合に、ローテーションパターンとして認識します。
• 定数シフト量のチェック: この最適化は、シフト量 s がコンパイル時に既知の定数である場合に適用されます。さらに、s と (WIDTH - s) の合計がビット幅 WIDTH に等しいことを確認します。例えば、32ビット整数であれば s + (32 - s) == 32 となります。
• OLROT オペレーションの導入: パターンが認識されると、元の OOR ノードは新しい OLROT (Left Rotate) オペレーションに変換されます。この OLROT は、Goコンパイラの中間表現における新しい内部オペレーションコードです。
• バックエンドでの命令生成: 各アーキテクチャ固有のバックエンドコンパイラ（5g, 6g, 8g）は、この OLROT オペレーションを処理するように変更されます。
  • src/cmd/6g/gsubr.c の optoas 関数には、OLROT に対応するアセンブリ命令（AROLL for 32-bit, AROLQ for 64-bit on AMD64）が追加されています。
  • src/cmd/5g/cgen64.c および src/cmd/8g/cgen64.c では、64ビット整数に対するローテーションのコード生成ロジックが追加されています。これらは、32ビットレジスタを組み合わせて64ビット操作をエミュレートする複雑な処理を含みます。例えば、shld hi:lo, c のような命令は、2つのレジスタにまたがるシフト操作を効率的に行います。

2. 境界チェックの削除の強化

Go言語では、スライスや配列へのアクセス時に自動的に境界チェックが行われます。このコミットでは、コンパイラの範囲分析を強化することで、不要な境界チェックをより多く削除できるようになります。

• Node.bounded フィールドの導入: src/cmd/gc/go.h の Node 構造体に bounded という新しいフィールドが追加されました。これは、そのノードが表す値が既に境界チェック済みであるか、またはコンパイル時に安全な範囲内にあることが証明されているかを示すフラグです。
• bounded 関数の追加: src/cmd/gc/walk.c に bounded 関数が追加されました。この関数は、与えられたノード（通常は配列インデックスやシフト量）が、指定された最大値 max の範囲内にあることを静的に推論できる場合に 1 を返します。
  • 定数インデックス: インデックスが定数であり、かつ 0 <= index < max の範囲内であれば bounded と判断されます。
  • ビットAND: index & mask の形式で、mask が max より小さい場合、結果は max より小さくなるため bounded と判断されます。
  • 剰余: index % N の形式で、N が max より小さい場合、結果は N 未満になるため bounded と判断されます。
  • 右シフトや除算: これらの操作は値の範囲を狭めるため、特定の条件下で bounded と判断されることがあります。
• walkexpr での利用: src/cmd/gc/walk.c の walkexpr 関数（ASTの走査と変換を行う主要な関数）内で、シフト操作 (OLSH, ORSH) やインデックス操作 (OINDEX) の際に bounded 関数が呼び出され、結果が Node.bounded フィールドに設定されます。
• バックエンドでの利用: 各バックエンドコンパイラ（5g, 6g, 8g）のコード生成ロジック（例: cgen_shift, agen, oindex 関数など）は、Node.bounded フラグをチェックし、bounded が 1 の場合は境界チェックのコード生成をスキップします。これにより、実行時のオーバーヘッドが削減されます。

3. 範囲分析の改善

このコミットは、コンパイラの範囲分析をより「積極的」にしますが、同時に「最小限」に留めるというバランスを取っています。これは、コンパイル時間の増加を抑えつつ、効果的な最適化を可能にするためです。

• bounded 関数の実装が、より多くのケースで値の範囲を正確に推論できるように改善されています。特に、ビット演算（AND, MOD, SHIFT）の結果が特定の範囲に収まることを検出するロジックが追加されています。
• test/bounds.go には、様々な型の変数と演算子を組み合わせたインデックスアクセスが記述されており、コンパイラがどのケースで境界チェックを省略できるかをテストしています。これにより、新しい範囲分析の正確性と効果が検証されます。

これらの変更は、Goコンパイラが生成するコードの品質を向上させ、特に数値計算や低レベルの操作が多いプログラムにおいて、より高いパフォーマンスを実現することに貢献します。

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

このコミットにおける主要なコード変更は、Goコンパイラのフロントエンド (src/cmd/gc) と、各アーキテクチャ固有のバックエンド (src/cmd/5g, src/cmd/6g, src/cmd/8g) にまたがっています。

1. src/cmd/gc/go.h

• Node 構造体に uchar bounded; フィールドが追加されました。これは、ノードが表す値が境界チェック不要であることを示すフラグです。

2. src/cmd/gc/walk.c

• walkexpr 関数内で、シフト操作 (OLSH, ORSH) およびインデックス操作 (OINDEX) の処理において、n->bounded = bounded(...) の形で新しい bounded 関数が呼び出され、結果が Node.bounded に設定されるようになりました。
• 新しい静的関数 walkrotate(Node **np) が追加されました。この関数は、x<<s | x>>(WIDTH-s) のようなビットローテーションパターンを検出し、ASTノードの op を OLROT に書き換えます。
• 新しい静的関数 bounded(Node *n, int64 max) が追加されました。この関数は、与えられたノード n の値が [0, max) の範囲内にあることを静的に推論できる場合に 1 を返します。OAND, OMOD, ODIV, ORSH などの演算子に対する範囲推論ロジックが含まれています。
• mpzero (多倍長整数0) が初期化されました。

3. src/cmd/gc/range.c, src/cmd/gc/sinit.c, src/cmd/gc/subr.c

• これらのファイルでは、以前 n->etype = 1; で境界チェックを無効にしていた箇所が、新しい n->bounded = 1; に変更されました。これは、etype フィールドが他の目的にも使用されるため、より明確な bounded フラグを導入したことによる修正です。

4. src/cmd/{5g,6g,8g}/gg.h

• cgen_shift 関数のシグネチャが void cgen_shift(int, Node*, Node*, Node*) から void cgen_shift(int, int, Node*, Node*, Node*) に変更され、bounded フラグを受け取るようになりました。

5. src/cmd/{5g,6g,8g}/cgen.c, src/cmd/{5g,6g,8g}/ggen.c, src/cmd/{5g,6g,8g}/gsubr.c

• 各アーキテクチャのコードジェネレータにおいて、OLROT オペレーションの処理が追加されました。特に gsubr.c の optoas 関数には、OLROT に対応するアセンブリ命令（AROLB, AROLW, AROLL, AROLQ）が追加されています。
• cgen_shift 関数が bounded フラグを考慮し、不要なシフト量チェック（例: シフト量がビット幅以上の場合の処理）をスキップするようになりました。
• agen や oindex_const などの関数で、Node.bounded フラグを利用して境界チェックのコード生成を抑制するロジックが追加されました。
• src/cmd/5g/cgen64.c と src/cmd/8g/cgen64.c には、64ビット整数に対する OLROT の具体的なコード生成ロジックが追加されています。これは、32ビットレジスタを組み合わせて64ビットローテーションを実現する複雑なアセンブリ命令のシーケンスを含みます。

6. test/bounds.go (新規追加)

• コンパイラの境界チェック削除機能が正しく動作するかを検証するためのテストファイルです。様々なデータ型と演算子（%, &, >>, /）を組み合わせたインデックスアクセスに対して、// ERROR "index bounds check elided" コメントで期待される最適化（境界チェックの削除）が示されています。

7. test/rotate.go (新規追加)

• ビットローテーション最適化が正しく動作するかを検証するためのテストファイルを生成するGoプログラムです。異なるビット幅（8, 16, 32, 64ビット）とシフト量、符号の有無、反転の有無を組み合わせて、x<<s | x>>(WIDTH-s) 形式の式が期待通りのローテーション結果を生成するかをチェックします。

コアとなるコードの解説

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

static void
walkrotate(Node **np)
{
    int w, sl, sr, s;
    Node *l, *r;
    Node *n;

    n = *np;

    // Want << | >> or >> | << on unsigned value.
    if(n->op != OOR ||
       (l->op != OLSH && l->op != ORSH) ||
       (r->op != OLSH && r->op != ORSH) ||
       n->type == T || issigned[n->type->etype] ||
       l->op == r->op) {
        return;
    }

    // Want same, side effect-free expression on lhs of both shifts.
    if(!samecheap(l->left, r->left))
        return;

    // Constants adding to width?
    w = l->type->width * 8; // ビット幅
    if(smallintconst(l->right) && smallintconst(r->right)) {
        if((sl=mpgetfix(l->right->val.u.xval)) >= 0 && (sr=mpgetfix(r->right->val.u.xval)) >= 0 && sl+sr == w)
            goto yes; // シフト量の合計がビット幅に等しい場合
        return;
    }

    // TODO: Could allow s and 32-s if s is bounded (maybe s&31 and 32-s&31).
    return;

yes:
    // Rewrite left shift half to left rotate.
    if(l->op == OLSH)
        n = l; // 左シフトがローテーションの基準となる
    else
        n = r;
    n->op = OLROT; // ノードのオペレーションをOLROTに書き換え

    // Remove rotate 0 and rotate w.
    s = mpgetfix(n->right->val.u.xval);
    if(s == 0 || s == w)
        n = n->left; // シフト量が0またはビット幅に等しい場合は、元のオペランドに置き換える（実質的なno-op）

    *np = n; // 変更されたノードをASTに反映
    return;
}

この関数は、ASTを走査し、x << s | x >> (WIDTH - s) または x >> s | x << (WIDTH - s) の形式のビットローテーションパターンを識別します。

1. まず、現在のノードが OOR (ビットOR) であること、その左右の子ノードがそれぞれシフト演算 (OLSH または ORSH) であること、そしてシフト対象のオペランドが同じであること（l->left と r->left が同じ）を確認します。また、符号なし整数型であることも条件です。
2. 次に、左右のシフト量が定数であり、その合計が対象のデータ型（例: int32 なら32、int64 なら64）のビット幅に等しいことを確認します。
3. これらの条件が満たされた場合、コンパイラは元の OOR ノードを新しい内部オペレーションコード OLROT (Left Rotate) に書き換えます。これにより、バックエンドコンパイラは、この OLROT を単一のCPUローテーション命令に変換できるようになります。
4. シフト量が0またはビット幅に等しい場合は、実質的に何も変更されないため、元のオペランドに置き換えられます。

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

static int
bounded(Node *n, int64 max)
{
    int64 v;
    int32 bits;
    int sign;

    if(n->type == T || !isint[n->type->etype])
        return 0;

    sign = issigned[n->type->etype];
    bits = 8*n->type->width; // ビット幅

    if(smallintconst(n)) { // 定数である場合
        v = mpgetfix(n->val.u.xval);
        return 0 <= v && v < max; // 0以上max未満ならbounded
    }

    switch(n->op) {
    case OAND: // ビットANDの場合
        v = -1;
        if(smallintconst(n->left)) {
            v = mpgetfix(n->left->val.u.xval);
        } else if(smallintconst(n->right)) {
            v = mpgetfix(n->right->val.u.xval);
        }
        if(0 <= v && v < max) // マスク値がmax未満ならbounded
            return 1;
        break;

    case OMOD: // 剰余の場合
        if(!sign && smallintconst(n->right)) { // 符号なしで、剰余の右オペランドが定数
            v = mpgetfix(n->right->val.u.xval);
            if(0 <= v && v <= max) // 剰余の右オペランドがmax以下ならbounded
                return 1;
        }
        break;

    case ODIV: // 除算の場合
        if(!sign && smallintconst(n->right)) { // 符号なしで、除算の右オペランドが定数
            v = mpgetfix(n->right->val.u.xval);
            while(bits > 0 && v >= 2) {
                bits--;
                v >>= 1;
            }
        }
        break;

    case ORSH: // 右シフトの場合
        if(!sign && smallintconst(n->right)) { // 符号なしで、シフト量が定数
            v = mpgetfix(n->right->val.u.xval);
            if(v > bits) // シフト量がビット幅より大きい場合、結果は0になるためbounded
                return 1;
            bits -= v; // 有効ビット幅を減らす
        }
        break;
    }

    if(!sign && bits <= 62 && (1LL<<bits) <= max) // 符号なしで、有効ビット幅がmax以下ならbounded
        return 1;

    return 0;
}

この関数は、与えられた整数ノード n の値が、指定された上限 max 未満であることがコンパイル時に保証できるかどうかを判断します。

• 定数: ノードが定数であれば、その値が 0 <= value < max の範囲内にあるかを直接チェックします。
• ビットAND (OAND): x & MASK の形式で、MASK が max 未満であれば、結果も max 未満になるため、境界チェックを省略できます。
• 剰余 (OMOD): x % N の形式で、N が max 以下であれば、結果は N 未満になるため、境界チェックを省略できます（符号なしの場合）。
• 除算 (ODIV): x / N の形式で、N が大きい場合、結果の範囲が狭まるため、境界チェックを省略できる可能性があります（符号なしの場合）。
• 右シフト (ORSH): x >> S の形式で、S が大きい場合、結果の範囲が狭まるため、境界チェックを省略できる可能性があります（符号なしの場合）。特に、シフト量がビット幅以上であれば結果は0になるため、常に bounded となります。

この関数は、src/cmd/gc/walk.c の walkexpr 関数内で、配列インデックスやシフト量の分析に利用され、Node.bounded フラグを設定します。このフラグが設定されている場合、各バックエンドコンパイラは対応する境界チェックのコード生成をスキップします。

src/cmd/6g/gsubr.c の optoas 関数

// ... (既存のコード) ...

	case CASE(OLROT, TINT8):
	case CASE(OLROT, TUINT8):
		a = AROLB; // 8ビット左ローテーション
		break;

	case CASE(OLROT, TINT16):
	case CASE(OLROT, TUINT16):
		a = AROLW; // 16ビット左ローテーション
		break;

	case CASE(OLROT, TINT32):
	case CASE(OLROT, TUINT32):
	case CASE(OLROT, TPTR32):
		a = AROLL; // 32ビット左ローテーション
		break;

	case CASE(OLROT, TINT64):
	case CASE(OLROT, TUINT64):
	case CASE(OLROT, TPTR64):
		a = AROLQ; // 64ビット左ローテーション
		break;

// ... (既存のコード) ...

この関数は、Goコンパイラの中間表現のオペレーションコード（op）と型（t）を受け取り、対応するターゲットアーキテクチャのアセンブリ命令（as）を返します。このコミットでは、新しく導入された OLROT オペレーションに対して、x86/AMD64アーキテクチャのネイティブなローテーション命令（AROLB, AROLW, AROLL, AROLQ）がマッピングされています。これにより、gcが OLROT に変換したビットローテーションパターンは、最終的に単一の効率的なCPU命令としてコンパイルされます。

関連リンク

• Go Issue Tracker (CL 6209077): https://golang.org/cl/6209077 - このコミットに対応するGoのコードレビュー（ChangeList）ページです。詳細な議論や変更の経緯を確認できます。
• Go Language Specification - Shift operators: https://go.dev/ref/spec#Shift_operators - Go言語におけるシフト演算子の公式仕様。
• Go Language Specification - Arithmetic operators: https://go.dev/ref/spec#Arithmetic_operators - Go言語における算術演算子の公式仕様。

参考にした情報源リンク

• Go Compiler Internals (古い情報ですが概念は共通): https://go.dev/doc/articles/go_compiler_internals.html
• Bitwise operations in C (概念的な理解に): https://en.wikipedia.org/wiki/Bitwise_operations_in_C
• Rotate (bit operation): https://en.wikipedia.org/wiki/Circular_shift
• Bounds checking elimination: https://en.wikipedia.org/wiki/Bounds-checking_elimination
• x86 Instruction Set Reference (ROL/ROR): https://www.felixcloutier.com/x86/rol:ror (Intel/AMDの公式ドキュメントへのリンクがあることが多い)