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

このコミットは、Goコンパイラ（cmd/gc）における最適化の改善に関するものです。具体的には、ビット単位のローテーション操作をより広範なパターンで認識し、対応する効率的なアセンブリ命令（ROLLなど）に変換できるようにすることで、生成されるコードのパフォーマンスを向上させます。特に、構造体のフィールドアクセスや配列のインデックス付けを含む複雑な式におけるローテーションパターンも最適化の対象となります。

コミット

commit 4de66875545233a2fadca8768d100efbcd110f67
Author: Nigel Tao <nigeltao@golang.org>
Date:   Tue Apr 2 21:14:34 2013 +1100

    cmd/gc: recognize (a.b[0]<<1 | a.b[0]>>31) as a rotate, not just
    (x<<1 | x>>31).
    
    Fixes #5084.
    
    On the SHA3 benchmark proposals at
    https://golang.org/cl/7760044/
    
    benchmark                       old ns/op    new ns/op    delta
    BenchmarkPermutationFunction         1288         1191   -7.53%
    BenchmarkSingleByteWrite             5795         5811   +0.28%
    BenchmarkBlockWrite512                178          179   +0.56%
    BenchmarkBlockWrite384                230          233   +1.30%
    BenchmarkBlockWrite256                282          286   +1.42%
    BenchmarkBlockWrite224                301          306   +1.66%
    BenchmarkBulkHashSHA3_512          326885       304548   -6.83%
    BenchmarkBulkHashSHA3_384          234839       220074   -6.29%
    BenchmarkBulkHashSHA3_256          186969       175790   -5.98%
    BenchmarkBulkHashSHA3_224          178133       167489   -5.98%
    
    For a function like
    
    func g() {
            x = a[3]<<20 | a[3]>>12
    }
    
    the asm goes from
    
    0006 (main.go:10) TEXT    g+0(SB),$0-0
    0007 (main.go:10) MOVL    a+12(SB),BP
    0008 (main.go:10) LOCALS  ,$0
    0009 (main.go:11) MOVL    BP,BX
    0010 (main.go:11) SHLL    $20,BX
    0011 (main.go:11) SHRL    $12,BP
    0012 (main.go:11) ORL     BP,BX
    0013 (main.go:11) MOVL    BX,x+0(SB)
    0014 (main.go:12) RET     ,
    
    to
    
    0006 (main.go:10) TEXT    g+0(SB),$0-0
    0007 (main.go:10) LOCALS  ,$0
    0008 (main.go:11) MOVL    a+12(SB),BX
    0009 (main.go:11) ROLL    $20,BX
    0010 (main.go:11) MOVL    BX,x+0(SB)
    0011 (main.go:12) RET     ,
    
    R=rsc, iant, remyoudompheng
    CC=golang-dev, jcb
    https://golang.org/cl/7944043

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

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

元コミット内容

このコミットは、Goコンパイラ（cmd/gc）がビット単位のローテーション操作を認識する能力を拡張することを目的としています。以前は、x<<N | x>>(32-N)のような単純な変数に対するローテーションのみを最適化していましたが、この変更により、a.b[0]<<N | a.b[0]>>(32-N)のように、構造体のフィールドアクセスや配列のインデックス付けを含むより複雑な式に対してもローテーションとして認識し、効率的なアセンブリ命令に変換できるようになります。

この最適化は、特にSHA3ベンチマークにおいて顕著なパフォーマンス改善をもたらしており、BenchmarkPermutationFunctionで-7.53%、BenchmarkBulkHashSHA3_512で-6.83%といった改善が見られます。これは、暗号化アルゴリズムが頻繁にビットローテーションを利用するため、この最適化が非常に効果的であることを示しています。

コミットメッセージには、x = a[3]<<20 | a[3]>>12というGoのコードが、最適化前は複数のMOVL、SHLL、SHRL、ORL命令に展開されていたものが、最適化後は単一のMOVLとROLL命令に簡略化される例が示されています。

変更の背景

ビット単位のローテーション操作は、暗号化アルゴリズムやハッシュ関数など、多くのパフォーマンスが要求される計算において頻繁に使用されます。これらの操作は、通常、左シフトと右シフト、そしてビット単位のOR演算の組み合わせとして表現されます。しかし、多くのCPUアーキテクチャには、このようなローテーションを単一の命令で実行できる専用の命令（例: x86のROL/ROR命令）が存在します。

Goコンパイラは、以前からx<<N | x>>(32-N)のような単純な形式のローテーションパターンを認識し、これらの専用命令に最適化する能力を持っていました。しかし、実際のコードでは、ローテーションの対象が単純な変数だけでなく、構造体のフィールドや配列の要素である場合も少なくありませんでした。例えば、a.b[0]のような式は、コンパイラ内部ではより複雑な抽象構文木（AST）として表現されます。

このコミットの背景には、Goコンパイラがこのような複雑な式のローテーションパターンを認識できず、結果として非効率な複数のシフト・OR命令に展開されてしまうという問題がありました。特に、SHA3のようなビットローテーションを多用するアルゴリズムにおいて、この非効率性がパフォーマンスのボトルネックとなっていたと考えられます。この変更は、コンパイラの最適化能力を向上させ、より広範なローテーションパターンを効率的なCPU命令にマッピングすることで、Goプログラムの実行速度を向上させることを目的としています。

前提知識の解説

このコミットを理解するためには、以下の概念に関する基本的な知識が必要です。

1. ビット単位のローテーション (Bitwise Rotation): ビット単位のローテーションは、数値のビットを左または右に循環的に移動させる操作です。例えば、32ビットの数値xを左にNビットローテーションする場合、x << N | x >> (32 - N)という式で表現できます（右ローテーションの場合はx >> N | x << (32 - N)）。これは、シフト演算とOR演算の組み合わせで実現されますが、多くのCPUにはこの操作を単一の命令で実行する機能があります（例: x86のROL (Rotate Left) やROR (Rotate Right)）。

2. コンパイラの最適化 (Compiler Optimization): コンパイラの最適化とは、ソースコードを機械語に変換する際に、生成される機械語コードの実行速度やサイズを改善するプロセスです。これには、冗長な計算の削除、ループの最適化、特定のパターンをより効率的なCPU命令に置き換える（命令選択）など、様々な手法があります。本コミットは、後者の命令選択の最適化に該当します。

3. Goコンパイラ (cmd/gc): Go言語の公式コンパイラは、gc（Go Compiler）と呼ばれ、Goのソースコードを機械語に変換します。gcは、フロントエンド（構文解析、意味解析）、中間コード生成、最適化、バックエンド（コード生成）といった複数のフェーズで構成されています。このコミットの変更は、主に最適化フェーズ、特に抽象構文木（AST）のウォーク（走査）と変換を行う部分に関連しています。

4. 抽象構文木 (Abstract Syntax Tree, AST): コンパイラは、ソースコードを直接処理するのではなく、まずその構造を抽象的なツリー形式で表現します。これがASTです。例えば、a.b[0]という式は、OINDEX（インデックス操作）ノードの下にODOT（フィールドアクセス）ノードがあり、その下にONAME（変数名）ノードがある、といった階層構造で表現されます。コンパイラの最適化は、このASTを走査し、パターンを認識してより効率的なASTに変換することで行われます。

5. src/cmd/gc/walk.c: Goコンパイラのソースコードの一部で、ASTの走査（"walking"）と変換を行うロジックが含まれています。walk.cは、コンパイラの最適化パスにおいて重要な役割を果たし、ASTをより低レベルの表現に変換したり、最適化を適用したりします。

6. Node構造体: Goコンパイラ内部でASTの各ノードを表すデータ構造です。Nodeは、操作の種類（opフィールド、例: ONAME, ODOT, OINDEX, OSHL, OSHR, OOR）、子ノードへのポインタ（left, rightフィールド）、シンボル情報（symフィールド）、定数値（valフィールド）などを含みます。

7. ONAME, ODOT, ODOTPTR, OINDEX, OSHL, OSHR, OOR: これらはGoコンパイラ内部で定義されているASTノードの操作タイプ（Node.op）を表す定数です。

   • ONAME: 変数名や識別子。
   • ODOT: 構造体やインターフェースのフィールドアクセス（例: obj.field）。
   • ODOTPTR: ポインタを介した構造体フィールドアクセス（例: ptr.field）。
   • OINDEX: 配列やスライスのインデックスアクセス（例: arr[idx]）。
   • OSHL: 左シフト演算子（<<）。
   • OSHR: 右シフト演算子（>>）。
   • OOR: ビット単位のOR演算子（|）。

技術的詳細

このコミットの核心は、src/cmd/gc/walk.cファイル内のsamecheap関数の変更にあります。samecheap関数は、Goコンパイラの最適化パスにおいて、2つの式が「安価に（cheaply）」同じであると見なせるかどうかを判断するために使用されます。ここでいう「安価に同じ」とは、コンパイラがそれらを同一のメモリ位置や値を持つものとして扱える、あるいは同一の最適化を適用できる、といった意味合いです。

変更前のsamecheap関数は非常に単純で、ONAME（変数名）ノードの場合にのみ、2つのノードが完全に同一であるかをチェックしていました。それ以外のノードタイプについては、TODOコメントがあるように、ほとんど考慮されていませんでした。

変更後、samecheap関数は大幅に拡張され、より複雑な式の比較に対応できるようになりました。主な変更点は以下の通りです。

1. ループによる再帰的な比較: 関数はwhileループを使用し、aとbという2つのNodeポインタを、式の根元に向かって（a = a->left; b = b->left;）再帰的に比較する構造になりました。これにより、a.b[0]のようなネストされた式も適切に比較できるようになります。

2. ODOT / ODOTPTR のサポート: case ODOT:およびcase ODOTPTR:が追加されました。これらのケースでは、フィールドアクセス（.演算子）を比較します。

   • ar = a->right; br = b->right;: ODOTノードのrightフィールドは、アクセスされるフィールド名を表すONAMEノードを指します。
   • if(ar->op != ONAME || br->op != ONAME || ar->sym != br->sym): 比較対象の両方のノードがONAMEであり、かつそれらが同じシンボル（つまり同じフィールド名）を参照していることを確認します。これにより、obj1.fieldとobj2.fieldのように、異なるベースオブジェクトでも同じフィールドにアクセスしている場合に、そのフィールドアクセス部分が「同じ」と見なされる可能性が生まれます。

3. OINDEX のサポート: case OINDEX:が追加されました。このケースでは、配列やスライスのインデックスアクセス（[]演算子）を比較します。

   • ar = a->right; br = b->right;: OINDEXノードのrightフィールドは、インデックスを表す式を指します。
   • if(!isconst(ar, CTINT) || !isconst(br, CTINT) || mpcmpfixfix(ar->val.u.xval, br->val.u.xval) != 0): ここでは、インデックスが両方とも整数定数であること（isconst(..., CTINT)）と、その定数値が同じであること（mpcmpfixfix(...) != 0）をチェックします。これにより、arr[0]とanother_arr[0]のように、異なる配列でも同じ定数インデックスにアクセスしている場合に、そのインデックスアクセス部分が「同じ」と見なされる可能性が生まれます。

このsamecheap関数の拡張により、コンパイラはa.b[0]<<N | a.b[0]>>(32-N)のようなパターンにおいて、a.b[0]の部分が両方のシフト操作で同じ「安価な」式であると認識できるようになります。この認識が可能になることで、コンパイラのバックエンドは、このパターン全体を単一のROLLアセンブリ命令に変換する最適化を適用できるようになり、結果としてより効率的な機械語コードが生成されます。

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

変更はsrc/cmd/gc/walk.cファイル内のsamecheap関数に集中しています。

--- a/src/cmd/gc/walk.c
+++ b/src/cmd/gc/walk.c
@@ -2897,14 +2897,29 @@ hard:
 static int
 samecheap(Node *a, Node *b)
 {
-	if(a == N || b == N || a->op != b->op)
-		return 0;
-	
-	switch(a->op) {
-	case ONAME:
-		return a == b;
-	// TODO: Could do more here, but maybe this is enough.
-	// It's all cheapexpr does.
+	Node *ar, *br;
+	while(a != N && b != N && a->op == b->op) {
+		switch(a->op) {
+		default:
+			return 0;
+		case ONAME:
+			return a == b;
+		case ODOT:
+		case ODOTPTR:
+			ar = a->right;
+			br = b->right;
+			if(ar->op != ONAME || br->op != ONAME || ar->sym != br->sym)
+				return 0;
+			break;
+		case OINDEX:
+			ar = a->right;
+			br = b->right;
+			if(!isconst(ar, CTINT) || !isconst(br, CTINT) || mpcmpfixfix(ar->val.u.xval, br->val.u.xval) != 0)
+				return 0;
+			break;
+		}
+		a = a->left;
+		b = b->left;
 	}
 	return 0;
 }

コアとなるコードの解説

samecheap関数は、Goコンパイラの最適化フェーズにおいて、2つの抽象構文木（AST）ノードaとbが「安価に同じ」であるかどうかを判定する役割を担っています。この「安価に同じ」という概念は、コンパイラが特定の最適化（この場合はビットローテーションの認識）を適用する際に、対象となるサブ式が同一であると見なせるかどうかの基準となります。

変更前のコードは、非常に限定的なチェックしか行っていませんでした。

• if(a == N || b == N || a->op != b->op) return 0;: どちらかのノードがNULLであるか、または操作タイプ（op）が異なる場合は、即座に異なるものと判断していました。
• case ONAME: return a == b;: ONAME（変数名）の場合のみ、ノードポインタ自体が同一であるかをチェックしていました。これは、同じ変数名を参照している場合にのみ「同じ」と見なすという、最も単純なケースです。

変更後のコードは、この機能を大幅に拡張しています。

1. while(a != N && b != N && a->op == b->op): このループは、2つのASTノードaとbが、その操作タイプが同じである限り、式の根元に向かって（a = a->left; b = b->left;）比較を続行することを意味します。これにより、a.b[0]のようなネストされた式を、その構成要素ごとに比較できるようになります。

2. switch(a->op): 現在のノードの操作タイプに基づいて、異なる比較ロジックを適用します。

   • default: return 0;: ONAME, ODOT, ODOTPTR, OINDEX以外の操作タイプの場合、samecheapはそれらを「安価に同じ」とは見なしません。これは、これらの操作タイプに対する詳細な比較ロジックが実装されていないためです。

   • case ONAME: return a == b;: これは変更前と同じで、ONAMEノードの場合、ノードポインタ自体が同一であるかをチェックします。

   • case ODOT: case ODOTPTR:: 構造体やポインタを介したフィールドアクセス（例: s.fieldやptr->field）を比較します。

     • ar = a->right; br = b->right;: ODOT/ODOTPTRノードのrightフィールドは、アクセスされるフィールド名を表すONAMEノードを指します。
     • if(ar->op != ONAME || br->op != ONAME || ar->sym != br->sym) return 0;: ここで、両方のrightノードがONAMEであり、かつそれらが同じシンボル（つまり同じフィールド名）を参照していることを確認します。これにより、obj1.fieldとobj2.fieldのように、ベースオブジェクトが異なっていても、アクセスしているフィールドが同じであれば、そのフィールドアクセス部分が「安価に同じ」と見なされる可能性が生まれます。

   • case OINDEX:: 配列やスライスのインデックスアクセス（例: arr[idx]）を比較します。

     • ar = a->right; br = b->right;: OINDEXノードのrightフィールドは、インデックスを表す式を指します。
     • if(!isconst(ar, CTINT) || !isconst(br, CTINT) || mpcmpfixfix(ar->val.u.xval, br->val.u.xval) != 0) return 0;: ここで、インデックスが両方とも整数定数であること（isconst(..., CTINT)）と、その定数値が同じであること（mpcmpfixfix(...) != 0）をチェックします。これにより、arr[0]とanother_arr[0]のように、異なる配列でも同じ定数インデックスにアクセスしている場合に、そのインデックスアクセス部分が「安価に同じ」と見なされる可能性が生まれます。

   • a = a->left; b = b->left;: 各ケースの処理後、ループの次のイテレーションのために、ノードをそのleft子ノードに更新します。これは、ODOTやOINDEXのようなノードでは、leftフィールドがベースとなる式（例: a.bのa、a[0]のa）を指すため、そのベース部分の比較を続行するためです。

この拡張されたsamecheap関数により、コンパイラは、ビットローテーションのパターン（X << N | X >> (32 - N)）において、Xがa.b[0]のような複雑な式であっても、両方のシフト操作でXが「安価に同じ」であると正確に判断できるようになります。この正確な判断が、コンパイラが最終的に単一のROLLアセンブリ命令を生成するための鍵となります。

関連リンク

• Go言語の公式リポジトリ: https://github.com/golang/go
• Go言語のコンパイラに関するドキュメント（一般的な情報）: https://go.dev/doc/compiler
• Go言語のコンパイラソースコード（src/cmd/compile以下）: https://github.com/golang/go/tree/master/src/cmd/compile

参考にした情報源リンク

• コミットメッセージに記載されているSHA3ベンチマークの提案: https://golang.org/cl/7760044/
• このコミットのCode Review: https://golang.org/cl/7944043
• ビットローテーションに関する一般的な情報（例: Wikipedia）
• コンパイラの最適化に関する一般的な情報（例: コンパイラ設計の教科書）
• x86アセンブリのROL/ROR命令に関する情報（例: Intel/AMDの命令セットリファレンス）