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

このコミットは、Go言語の初期のコンパイラである6g（64-bit x86アーキテクチャ向け）のコードジェネレータsrc/cmd/6g/gen.cに対する修正です。具体的には、ビットシフト演算における特定のバグ、特にシフト量がオペランドのビット幅を超える場合に発生する問題に対処しています。

コミット

commit 93c8d3c41bcb116779541679922029c48a788dfb
Author: Ken Thompson <ken@golang.org>
Date:   Tue Nov 18 17:15:42 2008 -0800

    another shift bug
    
    R=r
    OCL=19525
    CL=19525

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

https://github.com/golang/go/commit/93c8d3c41bcb116779541679922029c48a788dfb

元コミット内容

このコミットは、Go言語のコンパイラ6gにおけるビットシフト演算のバグを修正するものです。特に、シフト量がオペランドの型が持つビット幅以上である場合に、予期せぬ結果が生じる可能性があった問題に対応しています。

変更の概要は以下の通りです。

• src/cmd/6g/gen.cファイルにおいて、cgen_shift関数内のシフト演算のコード生成ロジックが修正されました。
• シフト量がオペランドのビット幅（nl->type->width*8）以上である場合、特殊な処理が適用されます。
• この特殊なケースでは、width*8-1（つまり、ビット幅-1）の量で2回シフトを実行することで、結果がゼロになるようにしています。これは、多くのプロセッサアーキテクチャにおける「大きなシフト量」の挙動をエミュレートし、未定義動作を避けるための一般的な手法です。

変更の背景

このコミットの背景には、Go言語の初期開発段階におけるコンパイラの堅牢性向上の取り組みがあります。ビットシフト演算は、低レベルのプログラミングにおいて非常に頻繁に使用される基本的な操作ですが、その挙動はプロセッサアーキテクチャやプログラミング言語の仕様によって微妙に異なります。

特に、シフト量がオペランドのビット幅を超える場合（例えば、32ビット整数を32ビット以上シフトする場合）の挙動は、C言語などでは未定義動作とされています。しかし、Go言語のような新しい言語では、このようなエッジケースにおいても明確で予測可能な挙動を提供することが重要です。

この「another shift bug」というコミットメッセージは、以前にも同様のシフト関連のバグが存在し、それが修正されたことを示唆しています。Ken Thompsonによるこの修正は、コンパイラが生成するコードが、あらゆる有効な入力に対して正しく、かつ安全に動作することを保証するための継続的な努力の一環です。これにより、Goプログラムが異なるプラットフォームで一貫した動作を示すことが保証されます。

前提知識の解説

1. ビットシフト演算

ビットシフト演算は、数値のバイナリ表現のビットを左または右に移動させる操作です。

• 左シフト (<<): 数値を2のN乗倍する効果があります。例えば、x << nはx * 2^nと等価です。左にシフトされたビットは失われ、右からは0が埋められます。
• 右シフト (>>): 数値を2のN乗で割る効果があります。例えば、x >> nはx / 2^nと等価です。右にシフトされたビットは失われます。左から埋められるビットは、符号なし整数では0、符号付き整数では最上位ビット（符号ビット）がコピーされる（算術右シフト）か、0が埋められる（論理右シフト）か、言語やコンパイラによって異なります。Go言語では、符号なし整数と符号付き整数で挙動が異なります。

2. シフト量と未定義動作

多くのCPUアーキテクチャでは、シフト命令のシフト量は、オペランドのビット幅のモジュロ（剰余）を取るか、あるいはビット幅以上のシフト量に対しては結果をゼロにするなどの特定の挙動が定義されています。しかし、C/C++のような言語では、シフト量がオペランドのビット幅以上である場合の挙動は「未定義動作 (Undefined Behavior)」とされています。これは、コンパイラがその状況でどのようなコードを生成してもよいことを意味し、予期せぬ結果やセキュリティ上の脆弱性につながる可能性があります。

Go言語では、このような未定義動作を避け、常に予測可能な挙動を提供することを目指しています。そのため、コンパイラは、基盤となるハードウェアの挙動に依存するのではなく、言語仕様に沿った正しい結果を生成するように設計されています。

3. 6gコンパイラ

6gは、Go言語の初期に開発されたコンパイラの一つで、主に64-bit x86アーキテクチャ（AMD64/Intel 64）をターゲットとしていました。Go言語のコンパイラは、当初はC言語で書かれていましたが、後にGo自身で書かれるようになりました（セルフホスティング）。6gはそのC言語で書かれた時代のコンパイラの一つであり、Goのソースコードを機械語に変換する役割を担っていました。gen.cファイルは、このコンパイラのコード生成部分を担当するファイルです。

技術的詳細

このコミットの技術的詳細は、コンパイラのコード生成におけるビットシフト演算のエッジケース処理にあります。

Go言語の仕様では、シフト量がオペランドのビット幅以上の場合、結果はゼロになることが保証されています。例えば、uint32型の変数を32ビット以上左シフトまたは右シフトした場合、結果は0になります。

しかし、多くのCPUのシフト命令（例: x86のSHL, SHR）は、シフト量がレジスタのビット幅以上の場合、シフト量をレジスタのビット幅のモジュロ（剰余）でマスクする挙動を示します。例えば、32ビットレジスタに対して32ビットシフト命令を実行すると、シフト量が32 % 32 = 0と解釈され、結果として何もシフトされない（元の値がそのまま残る）ことがあります。これはGo言語の仕様と矛盾します。

このコミットは、この矛盾を解消するためにcgen_shift関数内で特別なチェックを追加しています。

if(mpgetfix(nr->val.u.xval) >= nl->type->width*8) {
    // large shift gets 2 shifts by width
    nodconst(&n3, types[TUINT32], nl->type->width*8-1);
    gins(a, &n3, &n1);
    gins(a, &n3, &n1);
} else
    gins(a, nr, &n1);

• mpgetfix(nr->val.u.xval): シフト量（nr）が定数である場合に、その定数値を整数として取得します。
• nl->type->width*8: オペランド（nl）の型が持つビット幅を計算します（widthはバイト単位なので8を掛ける）。
• if(mpgetfix(nr->val.u.xval) >= nl->type->width*8): シフト量がオペランドのビット幅以上であるかをチェックします。
• nodconst(&n3, types[TUINT32], nl->type->width*8-1);: n3という一時的なノードを作成し、その定数値をビット幅-1に設定します。例えば、32ビット整数なら31、64ビット整数なら63です。
• gins(a, &n3, &n1); gins(a, &n3, &n1);: ここが核心的な修正です。シフト量が大きすぎる場合、元のシフト量nrで一度シフトする代わりに、ビット幅-1という大きなシフト量で2回シフト命令を生成します。

なぜビット幅-1で2回シフトするのか？ 多くのCPUアーキテクチャでは、シフト量がビット幅-1の場合、そのレジスタのすべてのビットがシフトされ、結果として0または符号ビットの繰り返しになります。これを2回行うことで、確実にレジスタの内容を0にすることができます。例えば、32ビットレジスタで31ビット左シフトを2回行うと、元の値が何であっても最終的には0になります。これは、Go言語の「大きなシフト量では結果がゼロになる」という仕様を、基盤となるCPUの挙動に依存せずに確実に実現するためのテクニックです。

この修正により、コンパイラは、シフト量がオペランドのビット幅を超えるようなエッジケースにおいても、Go言語の仕様に厳密に準拠した正しいコードを生成できるようになりました。

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

変更はsrc/cmd/6g/gen.cファイルのcgen_shift関数内で行われています。

--- a/src/cmd/6g/gen.c
+++ b/src/cmd/6g/gen.c
@@ -1212,7 +1211,13 @@ cgen_shift(int op, Node *nl, Node *nr, Node *res)
 	if(nr->op == OLITERAL) {
 		regalloc(&n1, nl->type, res);
 		cgen(nl, &n1);
-		gins(a, nr, &n1);
+		if(mpgetfix(nr->val.u.xval) >= nl->type->width*8) {
+			// large shift gets 2 shifts by width
+			nodconst(&n3, types[TUINT32], nl->type->width*8-1);
+			gins(a, &n3, &n1);
+			gins(a, &n3, &n1);
+		} else
+			gins(a, nr, &n1);
 		gmove(&n1, res);
 		regfree(&n1);
 		goto ret;

コアとなるコードの解説

cgen_shift関数は、Go言語のソースコード中のシフト演算（<<や>>）を、ターゲットアーキテクチャの機械語命令に変換する役割を担っています。

変更された部分のコンテキストは、シフト量が定数リテラル（nr->op == OLITERAL）である場合の処理です。

1. regalloc(&n1, nl->type, res); cgen(nl, &n1);: まず、シフトされるオペランドnlの値を一時レジスタn1にロードします。resは結果を格納する場所です。

2. if(mpgetfix(nr->val.u.xval) >= nl->type->width*8): ここで、シフト量nrが定数である場合に、その値（mpgetfix(nr->val.u.xval)）が、シフトされるオペランドnlの型が持つビット幅（nl->type->width*8）以上であるかをチェックします。

   • nl->type->widthはバイト単位の幅なので、*8でビット単位の幅に変換します。
   • 例えば、int32型であれば4 * 8 = 32ビット、int64型であれば8 * 8 = 64ビットとなります。

3. ifブロック内（シフト量が大きすぎる場合）:

   // large shift gets 2 shifts by width
   nodconst(&n3, types[TUINT32], nl->type->width*8-1);
   gins(a, &n3, &n1);
   gins(a, &n3, &n1);
   

   • nodconst(&n3, types[TUINT32], nl->type->width*8-1);: n3という新しいノードを作成し、その値をオペランドのビット幅から1を引いた値（例: 31 for 32-bit, 63 for 64-bit）に設定します。これは、その型の最大シフト量に相当します。
   • gins(a, &n3, &n1); gins(a, &n3, &n1);: ここで、実際のシフト命令を2回生成します。aはシフトの種類（左シフトか右シフトか）を示すオペコードです。n3（ビット幅-1）の量でn1（オペランドの値）をシフトする命令を2回発行します。
   • この2回のシフトにより、Go言語の仕様通り、シフト量がビット幅以上の場合に結果が確実にゼロになるようにします。例えば、32ビットの値を31ビット左シフトすると、最上位ビットが失われ、残りのビットもすべて失われるか、ゼロで埋められます。これをもう一度行うことで、確実にゼロになります。

4. elseブロック内（通常のシフト量の場合）:

   gins(a, nr, &n1);
   

   • シフト量nrがオペランドのビット幅未満である場合は、これまで通り、通常のシフト命令を1回生成します。

5. gmove(&n1, res); regfree(&n1);: シフト結果が格納された一時レジスタn1の内容を最終的な結果の場所resに移動し、n1を解放します。

この修正は、コンパイラが生成する機械語が、Go言語の厳密なセマンティクス（特にシフト演算のエッジケース）に準拠することを保証するための重要な変更です。

関連リンク

• Go言語の仕様 (The Go Programming Language Specification):
  • https://go.dev/ref/spec#Shift_operators (シフト演算子のセクション)
• Go言語の初期のコンパイラに関する情報:
  • https://go.dev/doc/faq#compilers (Go FAQのコンパイラに関するセクション)

参考にした情報源リンク

• Go言語の公式ドキュメントと仕様
• コンパイラ設計に関する一般的な知識
• x86アセンブリ言語のシフト命令に関する情報 (例: Intel Software Developer's Manual)
• Gitのコミット履歴と差分表示
• Ken ThompsonのGo言語への貢献に関する情報 (一般的な知識)