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

このコミットは、Goコンパイラのcmd/6c (32-bit x86アーキテクチャ向け) および cmd/8c (64-bit x86-64アーキテクチャ向け) において、特定のビットローテーションパターンを最適化し、対応するCPUのローテーション命令（ROLLなど）を使用するように改善するものです。これにより、生成されるアセンブリコードがより効率的になります。

コミット

commit bb192d13996abdeeec86cf756f8176a42e5c2672
Author: Matthew Dempsky <mdempsky@google.com>
Date:   Fri Jan 18 17:29:53 2013 -0500

    cmd/6c: Optimize rotate expressions to use rotate instructions.
    
    For simplicity, only recognizes expressions of the exact form
    "(x << a) | (x >> b)" where x is a variable and a and b are
    integer constant expressions that add to x's bit width.
    
    Fixes #4629.
    
    $ cat rotate.c
    unsigned int
    rotate(unsigned int x)
    {
            x = (x << 3) | (x >> (sizeof(x) * 8 - 3));
            return x;
    }
    
    ## BEFORE
    $ go tool 6c -S rotate.c
    (rotate.c:2)    TEXT    rotate+0(SB),$0-8
    (rotate.c:2)    MOVL    x+0(FP),!!DX
    (rotate.c:4)    MOVL    DX,!!AX
    (rotate.c:4)    SALL    $3,!!AX
    (rotate.c:4)    MOVL    DX,!!CX
    (rotate.c:4)    SHRL    $29,!!CX
    (rotate.c:4)    ORL     CX,!!AX
    (rotate.c:5)    RET     ,!!
    (rotate.c:5)    RET     ,!!
    (rotate.c:5)    END     ,!!
    
    ## AFTER
    $ go tool 6c -S rotate.c
    (rotate.c:2)    TEXT    rotate+0(SB),$0-8
    (rotate.c:4)    MOVL    x+0(FP),!!AX
    (rotate.c:4)    ROLL    $3,!!AX
    (rotate.c:5)    RET     ,!!
    (rotate.c:5)    RET     ,!!
    (rotate.c:5)    END     ,!!
    
    R=rsc, minux.ma
    CC=golang-dev
    https://golang.org/cl/7069056

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

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

元コミット内容

上記「コミット」セクションを参照してください。

変更の背景

この変更の背景には、Goコンパイラが生成するアセンブリコードの効率性向上が挙げられます。特にビットローテーション操作は、暗号化アルゴリズムやハッシュ関数など、多くの低レベルな処理で頻繁に使用されます。

コミットメッセージの例にあるように、x = (x << 3) | (x >> (sizeof(x) * 8 - 3)); のようなビットローテーションのC言語表現は、最適化されていないコンパイラでは複数の命令（左シフト、右シフト、論理OR）に展開されていました。これは、CPUが提供する単一のローテーション命令（x86アーキテクチャのROL/ROR命令など）と比較して、命令数が増え、実行サイクルも多くなるため、パフォーマンス上のボトルネックとなる可能性がありました。

Go言語のIssue #4629（"cmd/6c: optimize rotate expressions"）でこの問題が報告されており、このコミットはその問題に対する直接的な解決策として実装されました。コンパイラがソースコード中の特定のパターンを認識し、それをより効率的なCPU命令に置き換えることで、生成されるバイナリの性能を向上させることが目的です。

前提知識の解説

1. ビットローテーション (Bit Rotation)

ビットローテーションは、数値のビットを循環的にシフトする操作です。通常のビットシフト（左シフト << や右シフト >>）では、シフトによって押し出されたビットは失われ、反対側からはゼロが埋められます。しかし、ローテーションでは、押し出されたビットが反対側の端に戻ってきます。

例えば、8ビットの数値 10000000 を左に1ビットローテーションすると 00000001 になります。 C言語では、直接的なローテーション演算子はありませんが、x << a | x >> (BIT_WIDTH - a) のように、左シフトと右シフト、そして論理ORを組み合わせることでローテーションを表現できます。

2. x86アセンブリのローテーション命令 (ROL, ROR)

x86アーキテクチャのCPUには、ビットローテーションを直接実行するための命令が用意されています。

• ROL (Rotate Left): オペランドのビットを左に循環シフトします。
• ROR (Rotate Right): オペランドのビットを右に循環シフトします。

これらの命令は、単一のCPUサイクルでローテーションを実行できるため、複数のシフトとOR命令を組み合わせるよりもはるかに効率的です。

3. コンパイラの最適化と中間表現 (IR)

コンパイラは、ソースコードを機械語に変換する過程で、様々な最適化を行います。その一つが、高レベルな言語の構造を、より効率的な低レベルな命令に置き換えることです。

このプロセスでは、ソースコードはまず抽象構文木 (AST: Abstract Syntax Tree) に変換され、その後、中間表現 (IR: Intermediate Representation) に変換されることが一般的です。IRは、特定のCPUアーキテクチャに依存しない形式でプログラムの操作を表現します。最適化フェーズでは、このIRに対して様々な変換が適用され、最終的にターゲットアーキテクチャの機械語が生成されます。

このコミットでは、ASTまたはIRの段階で特定のビットローテーションパターンを認識し、それに対応する新しい中間演算子（OROTL）を導入し、最終的にターゲットのアセンブリ命令（ROLL）にマッピングしています。

4. Goコンパイラのcmd/6cとcmd/8c

Go言語のツールチェインには、様々なアーキテクチャ向けのコンパイラが含まれています。

• cmd/6c: Plan 9アセンブラの伝統を受け継ぐ、32-bit x86 (Intel 386) アーキテクチャ向けのCコンパイラです。Go言語の初期のコンパイラはC言語で書かれており、これらのツールがGoコードのコンパイルにも利用されていました。
• cmd/8c: 同様に、64-bit x86-64 (AMD64) アーキテクチャ向けのCコンパイラです。

これらのコンパイラは、Go言語のソースコードを中間表現に変換し、最終的にターゲットアーキテクチャのアセンブリコードを生成する役割を担っています。このコミットは、これらのバックエンドコンパイラに最適化ルールを追加するものです。

技術的詳細

このコミットの核心は、コンパイラのコード生成フェーズにおいて、特定のビットローテーションパターンを識別し、それを単一のCPUローテーション命令に変換する点にあります。

具体的には、以下の条件を満たす式をビットローテーションと認識します。

1. 論理OR (OOR) 演算: 式の最上位が論理ORであること。
2. 左右のオペランド:
   • 左オペランドが左シフト (OASHL) であること。
   • 右オペランドが論理右シフト (OLSHR) であること。
3. 定数シフト量: 左右のシフト量が定数 (OCONST) であること。
4. 同一変数: 左右のシフト操作の対象となる変数が同一 (ONAME かつ l->left->sym == r->left->sym) であること。
5. ビット幅の合計: 左シフト量 (l->right->vconst) と右シフト量 (r->right->vconst) の合計が、対象変数のビット幅 (8 * l->left->type->width) に等しいこと。例えば、32ビット整数であれば、シフト量の合計が32になる必要があります。

これらの条件が全て満たされた場合、コンパイラは従来の「左シフト + 右シフト + OR」の3命令の組み合わせではなく、新しい中間演算子 OROTL (Rotate Left) を生成します。この OROTL は、最終的なアセンブリコード生成フェーズで、ターゲットアーキテクチャの ROLL 命令にマッピングされます。

コミットメッセージの例では、unsigned int x (32ビット) に対して (x << 3) | (x >> (sizeof(x) * 8 - 3)) という式が使われています。ここで sizeof(x) * 8 は 32 であり、3 + (32 - 3) = 32 となるため、上記の条件を満たし、ROLL $3, %AX のような単一命令に最適化されます。

この最適化は、コンパイラのバックエンド（cgen.c と txt.c）に実装されており、ASTのパターンマッチングと、中間コードからアセンブリ命令へのマッピングの変更を含みます。

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

このコミットで変更された主要なファイルとコードスニペットは以下の通りです。

src/cmd/6c/cgen.c および src/cmd/8c/cgen.c

これらのファイルは、それぞれ32ビットおよび64ビットアーキテクチャ向けのCコードジェネレータです。ASTノードを走査し、中間コードを生成する役割を担います。

// src/cmd/6c/cgen.c (同様の変更が src/cmd/8c/cgen.c にも適用)
@@ -265,6 +265,18 @@ cgen(Node *n, Node *nn)
 		// ... 既存のコード ...
 		}
 	}
+	// ビットローテーションパターンの検出
+	if(n->op == OOR && l->op == OASHL && r->op == OLSHR
+	&& l->right->op == OCONST && r->right->op == OCONST
+	&& l->left->op == ONAME && r->left->op == ONAME
+	&& l->left->sym == r->left->sym
+	&& l->right->vconst + r->right->vconst == 8 * l->left->type->width) {
+		regalloc(&nod, l->left, nn); // レジスタを割り当て
+		cgen(l->left, &nod);         // 変数xのコードを生成
+		gopcode(OROTL, n->type, l->right, &nod); // OROTL命令を生成
+		gmove(&nod, nn);             // 結果を移動
+		regfree(&nod);               // レジスタを解放
+		break;                       // このノードの処理を終了
+	}
 	if(n->op == OADD && l->op == OASHL && l->right->op == OCONST
 	// ... 既存のコード ...

src/cmd/6c/txt.c および src/cmd/8c/txt.c

これらのファイルは、中間コードのオペコードを実際のアセンブリ命令にマッピングする役割を担います。

// src/cmd/6c/txt.c (同様の変更が src/cmd/8c/txt.c にも適用)
@@ -1360,6 +1360,16 @@ gopcode(int o, Type *ty, Node *f, Node *t)
 		// ... 既存のコード ...
 		break;
 
+	case OROTL: // 新しく追加されたローテーションオペコード
+		a = AROLL; // デフォルトはROLL命令
+		if(et == TCHAR || et == TUCHAR)
+			a = AROLB; // 8ビットの場合
+		if(et == TSHORT || et == TUSHORT)
+			a = AROLW; // 16ビットの場合
+		if(et == TVLONG || et == TUVLONG || et == TIND) // 64ビットの場合 (6cではTVLONG/TUVLONGは使われないが、8cでは使われる)
+			a = AROLQ;
+		break;
+
 	case OFUNC:
 	// ... 既存のコード ...

src/cmd/cc/cc.h

コンパイラ全体で共有されるヘッダファイルで、中間演算子（オペコード）の列挙型が定義されています。

// src/cmd/cc/cc.h
@@ -325,6 +325,7 @@ enum
 	OINDEX,
 	OFAS,
 	OREGPAIR,
+	OROTL, // 新しいローテーションオペコードを追加
 
 	OEND
 };

src/cmd/cc/sub.c

オペコードの文字列表現を定義するファイルです。デバッグや診断出力で使用されます。

// src/cmd/cc/sub.c
@@ -1515,6 +1515,7 @@ Init	onamesinit[] =
 	OINDEX,		0,	"INDEX",
 	OFAS,		0,	"FAS",
 	OREGPAIR,	0,	"REGPAIR",
+	OROTL,		0,	"ROTL", // 新しいオペコードの文字列を追加
 	OEND,		0,	"END",
 	-1,		0,	0,
 };

コアとなるコードの解説

cgen.c (cgen 関数内)

この部分が、ソースコードのASTを走査し、ビットローテーションパターンを検出する主要なロジックです。

if(n->op == OOR && l->op == OASHL && r->op == OLSHR
&& l->right->op == OCONST && r->right->op == OCONST
&& l->left->op == ONAME && r->left->op == ONAME
&& l->left->sym == r->left->sym
&& l->right->vconst + r->right->vconst == 8 * l->left->type->width) {

この if 文は、前述の「技術的詳細」で説明した5つの条件を厳密にチェックしています。

• n->op == OOR: 現在のノードが論理OR演算であるか。
• l->op == OASHL && r->op == OLSHR: 左の子ノードが算術左シフト、右の子ノードが論理右シフトであるか。
• l->right->op == OCONST && r->right->op == OCONST: シフト量が定数であるか。
• l->left->op == ONAME && r->left->op == ONAME && l->left->sym == r->left->sym: シフト対象が同じ変数であるか。
• l->right->vconst + r->right->vconst == 8 * l->left->type->width: 左シフト量と右シフト量の合計が、変数のビット幅（バイト数 * 8）に等しいか。

これらの条件が全て真であれば、それはビットローテーションパターンであると判断されます。

	regalloc(&nod, l->left, nn);
	cgen(l->left, &nod);
	gopcode(OROTL, n->type, l->right, &nod);
	gmove(&nod, nn);
	regfree(&nod);
	break;

パターンが検出された場合、以下の処理が行われます。

1. regalloc(&nod, l->left, nn);: ローテーション操作の結果を格納するためのレジスタを割り当てます。
2. cgen(l->left, &nod);: ローテーション対象の変数 x の値をレジスタにロードするコードを生成します。
3. gopcode(OROTL, n->type, l->right, &nod);: ここが最も重要な部分です。新しく定義された中間オペコード OROTL を生成します。l->right はシフト量（定数）を表します。これにより、コンパイラは「この変数をこの量だけローテーションする」という意図を表現します。
4. gmove(&nod, nn);: ローテーション結果を最終的な出力先（nn）に移動します。
5. regfree(&nod);: 割り当てたレジスタを解放します。
6. break;: このASTノードの処理を終了し、これ以上のコード生成は行いません。

txt.c (gopcode 関数内)

この部分が、中間オペコード OROTL を実際のアセンブリ命令に変換する役割を担います。

case OROTL:
	a = AROLL;
	if(et == TCHAR || et == TUCHAR)
		a = AROLB;
	if(et == TSHORT || et == TUSHORT)
		a = AROLW;
	if(et == TVLONG || et == TUVLONG || et == TIND)
		a = AROLQ;
	break;

gopcode 関数は、中間オペコード o と型情報 ty を受け取り、対応するアセンブリ命令 a を決定します。

• case OROTL:: OROTL オペコードが渡された場合。
• a = AROLL;: デフォルトでは、汎用的な左ローテーション命令 ROLL を選択します。
• 続く if 文群は、オペランドのデータ型（et）に基づいて、適切なサイズのローテーション命令を選択します。
  • TCHAR / TUCHAR (8ビット): AROLB (Byte Rotate Left)
  • TSHORT / TUSHORT (16ビット): AROLW (Word Rotate Left)
  • TVLONG / TUVLONG / TIND (64ビット): AROLQ (Quadword Rotate Left)
    • TVLONG / TUVLONG はGoのint64/uint64に対応し、TINDはポインタ型に対応します。これはcmd/8c (64ビットコンパイラ) で特に重要です。

このマッピングにより、コンパイラは OROTL という抽象的な操作を、ターゲットCPUが提供する最も効率的なローテーション命令に変換することができます。

関連リンク

• GitHubコミットページ: https://github.com/golang/go/commit/bb192d13996abdeeec86cf756f8176a42e5c2672
• Go Issue #4629: https://github.com/golang/go/issues/4629
• Gerrit Code Review (CL 7069056): https://golang.org/cl/7069056

参考にした情報源リンク

• Go Issue #4629: "cmd/6c: optimize rotate expressions" (コミットの背景理解のため)
• x86 Assembly/Shift and Rotate Instructions: https://en.wikibooks.org/wiki/X86_Assembly/Shift_and_Rotate_Instructions (ROL/ROR命令の理解のため)
• Go言語のコンパイラ構造に関する一般的な知識 (cmd/6c, cmd/8c, AST, IRなどの理解のため)
• C言語におけるビット操作の一般的な知識 (ビットローテーションのC言語表現の理解のため)