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

このコミットは、Goコンパイラ（cmd/gc）がビットローテーション操作を認識する際のロジックを拡張するものです。具体的には、これまでビットローテーションとして認識される条件がOR演算子（|）に限定されていたものを、XOR演算子（^）も含むように変更しています。これにより、u<<1 op u>>31のような形式で表現されるビットローテーションが、opが|だけでなく^である場合にもコンパイラによって最適化されるようになります。

コミット

コミットハッシュ: 947a3ddf871794c109f85218de42511a9f02f02e
Author: Nigel Tao nigeltao@golang.org
Date: Mon Jun 4 20:53:32 2012 +1000

コミットメッセージ:

cmd/gc: recognize u<<1 op u>>31 as a rotate when op is ^, not just |.

R=rsc
CC=golang-dev
https://golang.org/cl/6249071

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

https://github.com/golang/go/commit/947a3ddf871794c109f85218de42511a9f02f02e

元コミット内容

cmd/gc: recognize u<<1 op u>>31 as a rotate when op is ^, not just |.

R=rsc
CC=golang-dev
https://golang.org/cl/6249071

変更の背景

Goコンパイラは、特定のコードパターンを認識し、より効率的な機械語命令に変換する最適化を行います。ビットローテーション（circular shift）は、特に暗号化アルゴリズムやハッシュ関数などで頻繁に使用される操作であり、多くのCPUにはこの操作を直接実行するための専用命令（例: x86のROL/ROR命令）が用意されています。

Go言語では、ビットローテーションを直接サポートする組み込み演算子はありません。しかし、x << n | x >> (BITS - n)のような形式で表現することで、論理シフトとビットOR演算を組み合わせてビットローテーションをエミュレートできます。Goコンパイラは、このようなパターンを認識し、可能であれば単一のCPU命令に最適化することで、生成されるコードのパフォーマンスを向上させていました。

このコミット以前は、コンパイラがビットローテーションとして認識するパターンは、論理シフトの結果を結合する演算子として|（ビットOR）のみを考慮していました。しかし、ビットローテーションは^（ビットXOR）演算子を使用しても同様に表現できる場合があります（特に、特定のビットパターンを持つ値に対して）。この変更の背景には、コンパイラがより多くのビットローテーションの表現形式を認識し、最適化の機会を増やすことで、Goプログラムの実行効率をさらに高めるという目的があります。

前提知識の解説

1. ビットローテーション（Circular Shift）

ビットローテーションは、数値のビットを循環的にシフトする操作です。通常の論理シフトや算術シフトでは、シフトによって空いたビット位置には0が埋められたり、最上位ビットが複製されたりしますが、ビットローテーションでは、シフトによって「押し出された」ビットが反対側の端に「戻って」きます。

例えば、8ビットの数値10110010を左に1ビットローテーションすると、最上位ビットの1が最下位ビットに移動し、01100101となります。

Go言語には直接のビットローテーション演算子がないため、通常は以下のように論理シフトとビット演算を組み合わせて実装します。

左ローテーション: (x << n) | (x >> (BITS - n))
右ローテーション: (x >> n) | (x << (BITS - n))

ここでBITSは、対象となる数値のビット幅（例: uint32なら32、uint64なら64）です。

2. ビット演算子

| (ビットOR): 両方のオペランドの対応するビットの少なくとも一方が1であれば、結果のビットは1になります。
^ (ビットXOR): 両方のオペランドの対応するビットが異なる場合（一方が0で他方が1の場合）にのみ、結果のビットは1になります。同じ場合は0になります。

3. Goコンパイラ（`cmd/gc`）

cmd/gcは、Go言語の公式コンパイラです。Goのソースコードを機械語に変換する役割を担っています。コンパイルプロセスには、構文解析、型チェック、中間表現（IR）の生成、最適化、コード生成などの段階が含まれます。

4. `walk.c`

walk.cは、Goコンパイラのバックエンドの一部であり、中間表現（IR）のツリーを「ウォーク（走査）」しながら、様々な変換や最適化を行うファイルです。このファイルには、特定のパターンを認識して最適化されたコードに変換するロジックが含まれています。walkrotate関数は、ビットローテーションのパターンを認識し、最適化を行うための重要な部分です。

5. `Node`と`NodeList`

Goコンパイラ内部では、プログラムの構造は抽象構文木（AST）として表現され、その後、より低レベルの中間表現（IR）の「ノード（Node）」のツリーに変換されます。Nodeは、変数、定数、演算子、関数呼び出しなど、プログラムのあらゆる要素を表します。NodeListは、これらのノードのリストです。

技術的詳細

このコミットの核心は、Goコンパイラのcmd/gcがビットローテーションを認識する際の条件を緩和し、XOR演算子（^）を使用した場合もローテーションとして扱うようにした点にあります。

以前のコンパイラでは、walkrotate関数がビットローテーションパターンを認識する際に、結合演算子としてOOR（ビットOR）のみをチェックしていました。これは、u << N | u >> (BITS - N)という典型的なローテーションの表現に対応しています。

しかし、特定の状況下では、u << N ^ u >> (BITS - N)という形式も有効なビットローテーションとして機能します。特に、シフトされる値が特定のビットパターンを持つ場合、ORとXORは同じ結果をもたらすことがあります。例えば、シフトされるビットが互いに重ならない場合（つまり、u << Nとu >> (BITS - N)の結果が、ビットが1である位置で重ならない場合）、ORとXORは同じ結果になります。ビットローテーションの性質上、シフトされたビットは循環するため、この条件が満たされることがよくあります。

この変更により、コンパイラはOORだけでなくOXOR（ビットXOR）もローテーションの結合演算子として認識するようになります。これにより、開発者がXORを使ってビットローテーションを表現した場合でも、コンパイラがそれを最適化された単一のCPU命令（例: ROL/ROR）に変換できる可能性が広がります。これは、特に低レベルのビット操作を多用するコード（例: ハッシュ関数、チェックサム計算、暗号化アルゴリズム）において、パフォーマンスの向上に寄与する可能性があります。

また、test/rotate.goの変更は、この新しい認識ロジックが正しく機能することを検証するためのテストカバレッジを拡張しています。テストジェネレータは、|と^の両方の演算子を使用してローテーションパターンを生成し、コンパイラがそれらを正しく処理するかどうかを確認します。

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

このコミットでは、主に以下の2つのファイルが変更されています。

src/cmd/gc/walk.c: Goコンパイラのバックエンドにおける中間表現の処理と最適化ロジックが含まれるファイル。
test/rotate.go: ビットローテーションのコンパイラ最適化をテストするためのGoプログラムを生成するテストスクリプト。

`src/cmd/gc/walk.c` の変更点

--- a/src/cmd/gc/walk.c
+++ b/src/cmd/gc/walk.c
@@ -468,7 +468,6 @@ walkexpr(Node **np, NodeList **init)
 		goto ret;
 
 	case OAND:
-	case OXOR:
 	case OSUB:
 	case OMUL:
 	case OLT:
@@ -483,6 +482,7 @@ walkexpr(Node **np, NodeList **init)
 		goto ret;
 
 	case OOR:
+	case OXOR:
 		walkexpr(&n->left, init);
 		walkexpr(&n->right, init);
 		walkrotate(&n);
@@ -2708,10 +2708,10 @@ walkrotate(Node **np)
 	
 	n = *np;
 
-	// Want << | >> or >> | << on unsigned value.
-	l = n->left;
-	r = n->right;
-	if(n->op != OOR ||
+	// Want << | >> or >> | << or << ^ >> or >> ^ << on unsigned value.
+	l = n->left;
+	r = n->right;
+	if((n->op != OOR && n->op != OXOR) ||
 	   (l->op != OLSH && l->op != ORSH) ||
 	   (r->op != OLSH && r->op != ORSH) ||
 	   n->type == T || issigned[n->type->etype] ||

`test/rotate.go` の変更点

--- a/test/rotate.go
+++ b/test/rotate.go
@@ -9,7 +9,7 @@
 // Generate test of shift and rotate by constants.
 // The output is compiled and run.
 //
-// The output takes around a minute to compile, link, and run
+// The output takes around a minute or two to compile, link, and run
 // but it is only done during ./run, not in normal builds using run.go.
 
 package main
@@ -86,6 +86,26 @@ func main() {
 
 `
 
+var (
+	uop = [2]func(x, y uint64) uint64{
+		func(x, y uint64) uint64 {
+			return x | y
+		},
+		func(x, y uint64) uint64 {
+			return x ^ y
+		},
+	}
+	iop = [2]func(x, y int64) int64{
+		func(x, y int64) int64 {
+			return x | y
+		},
+		func(x, y int64) int64 {
+			return x ^ y
+		},
+	}
+	cop = [2]byte{'|', '^'}
+)
+
 func gentest(b *bufio.Writer, bits uint, unsigned, inverted bool) {
 	fmt.Fprintf(b, "func init() {\n")
 	defer fmt.Fprintf(b, "}\n")
@@ -93,48 +113,49 @@ func gentest(b *bufio.Writer, bits uint, unsigned, inverted bool) {
 	// Generate tests for left/right and right/left.
 	for l := uint(0); l <= bits; l++ {
 		for r := uint(0); r <= bits; r++ {
-			typ := fmt.Sprintf("int%d", bits)
-			v := fmt.Sprintf("i%d", bits)
-			if unsigned {
-				typ = "u" + typ
-				v = "u" + v
-			}
-			v0 := int64(0x123456789abcdef0)
-			if inverted {
-				v = "n" + v
-				v0 = ^v0
-			}
-			expr1 := fmt.Sprintf("%s<<%d | %s>>%d", v, l, v, r)
-			expr2 := fmt.Sprintf("%s>>%d | %s<<%d", v, r, v, l)
-			
-			var result string
-			if unsigned {
-				v := uint64(v0) >> (64 - bits)
-				v = v<<l | v>>r
-				v <<= 64 - bits
-				v >>= 64 - bits
-				result = fmt.Sprintf("%#x", v)
-			} else {
-				v := int64(v0) >> (64 - bits)
-				v = v<<l | v>>r
-				v <<= 64 - bits
-				v >>= 64 - bits
-				result = fmt.Sprintf("%#x", v)
-			}
-
-			fmt.Fprintf(b, "\tcheck(%q, %s, %s(%s))\n", expr1, expr1, typ, result)
-			fmt.Fprintf(b, "\tcheck(%q, %s, %s(%s))\n", expr2, expr2, typ, result)
-
-			// Chop test into multiple functions so that there's not one
-			// enormous function to compile/link.
-			// All the functions are named init so we don't have to do
-			// anything special to call them.  ☺
-			if n++; n >= 100 {
-				fmt.Fprintf(b, "}\n")
-				fmt.Fprintf(b, "func init() {\n")
-				n = 0
+			for o, op := range cop {
+				typ := fmt.Sprintf("int%d", bits)
+				v := fmt.Sprintf("i%d", bits)
+				if unsigned {
+					typ = "u" + typ
+					v = "u" + v
+				}
+				v0 := int64(0x123456789abcdef0)
+				if inverted {
+					v = "n" + v
+					v0 = ^v0
+				}
+				expr1 := fmt.Sprintf("%s<<%d %c %s>>%d", v, l, op, v, r)
+				expr2 := fmt.Sprintf("%s>>%d %c %s<<%d", v, r, op, v, l)
+
+				var result string
+				if unsigned {
+					v := uint64(v0) >> (64 - bits)
+					v = uop[o](v<<l, v>>r)
+					v <<= 64 - bits
+					v >>= 64 - bits
+					result = fmt.Sprintf("%#x", v)
+				} else {
+					v := int64(v0) >> (64 - bits)
+					v = iop[o](v<<l, v>>r)
+					v <<= 64 - bits
+					v >>= 64 - bits
+					result = fmt.Sprintf("%#x", v)
+				}
+
+				fmt.Fprintf(b, "\tcheck(%q, %s, %s(%s))\n", expr1, expr1, typ, result)
+				fmt.Fprintf(b, "\tcheck(%q, %s, %s(%s))\n", expr2, expr2, typ, result)
+
+				// Chop test into multiple functions so that there's not one
+				// enormous function to compile/link.
+				// All the functions are named init so we don't have to do
+				// anything special to call them.  ☺
+				if n++; n >= 50 {
+					fmt.Fprintf(b, "}\n")
+					fmt.Fprintf(b, "func init() {\n")
+					n = 0
+				}
 			}
 		}
 	}
 }
-

コアとなるコードの解説

`src/cmd/gc/walk.c`

walkexpr関数の変更:
- case OXOR:がOANDのグループから削除され、OORのグループに移動されました。
- これは、OXOR演算子もOORと同様に、ビットローテーションのパターン認識の対象となることを示しています。OORとOXORのケースでは、walkexprが再帰的に左右のオペランドを処理した後、walkrotate関数が呼び出され、ビットローテーションの最適化が試みられます。
walkrotate関数の変更:
- コメントが// Want << | >> or >> | << on unsigned value.から// Want << | >> or >> | << or << ^ >> or >> ^ << on unsigned value.に変更され、XOR演算子もローテーションの一部として認識されることが明示されました。
- 最も重要な変更は、if条件文です。
  - 変更前: if(n->op != OOR || ...)
  - 変更後: if((n->op != OOR && n->op != OXOR) || ...)
- この変更により、walkrotate関数は、ノードnの演算子（n->op）がOOR（ビットOR）またはOXOR（ビットXOR）のいずれかである場合に、そのノードがビットローテーションのパターンに合致するかどうかをチェックするようになりました。これにより、XORを使ったローテーション表現もコンパイラの最適化対象となります。

`test/rotate.go`

このファイルは、Goコンパイラのビットローテーション最適化が正しく機能するかを検証するためのテストコードを動的に生成するスクリプトです。

新しい変数の追加:
- uop: uint64型に対する|と^演算を行う関数を格納する配列。
- iop: int64型に対する|と^演算を行う関数を格納する配列。
- cop: 演算子文字|と^を格納するバイト配列。
gentest関数のループの変更:
- 既存のlとrのループの内側に、for o, op := range copという新しいループが追加されました。
- この新しいループにより、|と^の両方の演算子を使用して、ビットローテーションのテストケースが生成されるようになりました。
- expr1とexpr2の文字列フォーマットが変更され、op変数（|または^）が挿入されるようになりました。
- 結果の計算部分も変更され、uop[o]またはiop[o]を使用して、現在のループで選択されている演算子（|または^）に基づいて結果が計算されるようになりました。
- テスト関数の分割ロジックも変更され、n >= 100からn >= 50に条件が緩和されました。これは、|と^の両方のケースをテストするため、生成されるテストケースの総数が増加し、個々のinit関数が大きくなりすぎるのを防ぐためと考えられます。

これらの変更により、コンパイラがXOR演算子を含むビットローテーションパターンを正しく認識し、最適化できるようになったことを、テストスイートが網羅的に検証できるようになりました。

参考にした情報源リンク

Go言語の公式ドキュメント
Go言語のソースコード
ビットローテーションに関する一般的なコンピュータサイエンスの知識
Goコンパイラの最適化に関する一般的な情報 (Web検索)
- "Go compiler bitwise optimization"
- "Go compiler rotate instruction"
- "Go compiler walk.c"
- "Go compiler intermediate representation"
- "Go compiler OOR OXOR"
- "Go compiler walkrotate"
- "Go compiler CL 6249071" (Go Code ReviewのCL番号)
- https://go.dev/cl/6249071 (Go Code Reviewのページ)
- https://go.dev/src/cmd/compile/internal/walk/walk.go (現在のGoコンパイラのwalkパッケージのソースコード。walk.cはGoに移行済み)

comemo