Keyboard shortcuts

Press or to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

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

このコミットは、Go言語の初期のコンパイラ(6g、64ビットアーキテクチャ向け)におけるシフト代入演算子(>>= および <<=)に関するバグ修正です。具体的には、レジスタ割り当ての際に、オペランドの型を誤って参照していた問題を修正しています。

コミット

commit d2472eb812382fd2d6224f5dfc4182d943f7aaff
Author: Ken Thompson <ken@golang.org>
Date:   Sat Nov 1 17:53:12 2008 -0700

    >>= and <<= shift bug
    
    R=r
    OCL=18322
    CL=18322
---
 src/cmd/6g/gen.c | 6 +++---
 1 file changed, 3 insertions(+), 3 deletions(-)

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

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

元コミット内容

このコミットは、Go言語のコンパイラ(6g)において、シフト代入演算子(>>= および <<=)の処理に存在するバグを修正するものです。このバグは、レジスタ割り当ての際に、シフト量(右オペランド)の型ではなく、シフトされる変数(左オペランド)の型を誤って使用していたことに起因します。

変更の背景

Go言語のコンパイラは、ソースコードを機械語に変換する過程で、中間表現を生成し、レジスタ割り当てやコード生成を行います。シフト代入演算子(例: a >>= ba = a >> b と同等)は、変数の値をビット単位でシフトし、その結果を変数に再代入する複合演算子です。

このコミットが行われた2008年11月は、Go言語がまだ一般に公開される前の初期開発段階でした。当時のコンパイラは、6g(64ビットアーキテクチャ向け)、8g(32ビットx86アーキテクチャ向け)、5g(ARMアーキテクチャ向け)など、ターゲットアーキテクチャごとに異なる実装を持っていました。src/cmd/6g/gen.c は、6g コンパイラのコード生成部分を担当するファイルであり、アセンブリコードの生成やレジスタの管理といった低レベルな処理が含まれています。

このバグは、シフト演算の右オペランド(シフト量)の型が、レジスタ割り当ての際に正しく考慮されていなかったために発生しました。これにより、コンパイラが生成する機械語が不正になり、プログラムの実行時に予期せぬ結果やクラッシュを引き起こす可能性がありました。特に、シフト量として異なる型の変数や定数が使用された場合に問題が顕在化したと考えられます。

前提知識の解説

このコミットを理解するためには、以下の前提知識が必要です。

  • コンパイラの基本構造: コンパイラは通常、字句解析、構文解析、意味解析、中間コード生成、最適化、コード生成の各フェーズで構成されます。このコミットが関連するのは、主にコード生成フェーズです。
  • レジスタ割り当て (Register Allocation): CPUのレジスタは非常に高速な記憶領域であり、プログラムの実行速度に大きく影響します。レジスタ割り当ては、コンパイラがプログラムの変数や中間結果をどのレジスタに格納するかを決定するプロセスです。効率的なレジスタ割り当ては、生成されるコードの性能を向上させます。
  • Ullman Number (ウルマン数): コンパイラ最適化において、式の評価順序を決定するために使用されるヒューリスティックの一つです。Ullman数は、式の各ノード(オペランドや演算子)に割り当てられる数値で、レジスタの使用効率を考慮して計算されます。一般的に、Ullman数の大きいサブツリーから評価することで、必要なレジスタ数を最小限に抑えることができます。
  • 抽象構文木 (Abstract Syntax Tree, AST): ソースコードの構文構造を木構造で表現したものです。コンパイラの構文解析フェーズで生成され、意味解析やコード生成の入力となります。Node *nnl, nr は、ASTのノードを指していると考えられます。
  • シフト演算子 (Shift Operators):
    • << (左シフト): ビットを左に移動させます。左にシフトされたビットは失われ、右からは0が埋められます。実質的に2のべき乗を掛けることになります。
    • >> (右シフト): ビットを右に移動させます。右にシフトされたビットは失われます。左から埋められるビットは、符号なし整数では0、符号付き整数では最上位ビット(符号ビット)がコピーされる(算術右シフト)か、0が埋められる(論理右シフト)か、言語や実装に依存します。
  • 複合代入演算子 (Compound Assignment Operators): +=, -=, *=, /=, %=, &=, |=, ^=, <<=, >>= などがあります。a op= ba = a op b と同等です。

技術的詳細

src/cmd/6g/gen.c ファイルは、Goコンパイラのバックエンドの一部であり、Goの抽象構文木(AST)をターゲットアーキテクチャ(この場合はAMD64)のアセンブリコードに変換する役割を担っています。cgen_asop 関数は、複合代入演算子(+=, -=, <<=, >>= など)のコード生成を担当しています。

このバグは、cgen_asop 関数内で、シフト代入演算子(>>= および <<=)のレジスタ割り当てロジックに潜んでいました。具体的には、以下の3箇所でレジスタ割り当ての際に誤った型情報が使用されていました。

  1. シフト量のレジスタ割り当て: シフト演算では、シフトされる値(左オペランド)とシフト量(右オペランド)の2つのオペランドがあります。このバグでは、シフト量を格納するためのレジスタを割り当てる際に、シフトされる値の型(nl->type)を誤って使用していました。正しい動作は、シフト量の型(nr->type)を使用することです。シフト量は通常、整数型ですが、その具体的なサイズ(例: int8, int16, int32, int64)は、生成されるシフト命令に影響を与える可能性があります。
  2. 最終結果のレジスタ割り当て: シフト演算の結果を格納するためのレジスタを割り当てる際にも、誤った型情報が使用されていました。以前はシフト量の型(nr->type)を使用していましたが、シフト演算の結果は、シフトされる値(左オペランド)と同じ型を持つべきです。したがって、左オペランドの型(nl->type)を使用するのが正しいです。

これらの誤った型情報に基づくレジスタ割り当ては、生成されるアセンブリコードが、期待されるデータ型と異なるサイズのレジスタを使用したり、不適切な命令を選択したりする原因となります。結果として、シフト演算が正しく実行されず、プログラムの誤動作やクラッシュにつながる可能性がありました。

ullman 値の比較 (nr->ullman > nl->ullman) は、レジスタ割り当ての最適化戦略の一部です。Ullman数が大きい方のサブツリーを先に評価することで、レジスタの使用効率を高めようとします。しかし、この最適化ロジックの中で、レジスタ割り当ての型指定が誤っていたのが問題でした。

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

diff --git a/src/cmd/6g/gen.c b/src/cmd/6g/gen.c
index f4a15f2f20..add8ba3988 100644
--- a/src/cmd/6g/gen.c
+++ b/src/cmd/6g/gen.c
@@ -752,12 +752,12 @@ cgen_asop(Node *n)
 	}
 
 	if(nr->ullman > nl->ullman) {
-		regalloc(&n2, nl->type, N);
+		regalloc(&n2, nr->type, N);
 		cgen(nr, &n2);
 		igen(nl, &n1, N);
 	} else {
 		igen(nl, &n1, N);
-		regalloc(&n2, nl->type, N);
+		regalloc(&n2, nr->type, N);
 		cgen(nr, &n2);
 	}
 
@@ -766,7 +766,7 @@ cgen_asop(Node *n)
 	n3.right = &n2;
 	n3.op = n->etype;
 
-	regalloc(&n4, nr->type, N);
+	regalloc(&n4, nl->type, N);
 	cgen(&n3, &n4);
 	gmove(&n4, &n1);
 

コアとなるコードの解説

変更は src/cmd/6g/gen.c ファイル内の cgen_asop 関数に集中しています。この関数は、複合代入演算子(例: a >>= b)のコード生成を担当しています。

  1. シフト量のレジスタ割り当ての修正 (2箇所):

    -		regalloc(&n2, nl->type, N);
    +		regalloc(&n2, nr->type, N);
    

    この変更は、if(nr->ullman > nl->ullman) ブロック内と else ブロック内の両方で行われています。

    • regalloc(&n2, type, N) は、n2 というノード(おそらく中間結果を保持する一時的なノード)に対して、指定された type のレジスタを割り当てる関数呼び出しです。
    • 変更前は nl->type を使用していました。nl は左オペランド(シフトされる変数、例: a)を指します。
    • 変更後は nr->type を使用しています。nr は右オペランド(シフト量、例: b)を指します。
    • 意味: シフト量 nr の値を格納するためのレジスタを割り当てる際に、そのレジスタの型を nr 自身の型に合わせるように修正されました。これにより、シフト量に応じた適切なサイズのレジスタが確保され、正しいシフト命令が生成されるようになります。
  2. シフト結果のレジスタ割り当ての修正 (1箇所):

    -	regalloc(&n4, nr->type, N);
    +	regalloc(&n4, nl->type, N);
    

    この変更は、cgen_asop 関数の後半部分で行われています。

    • n4 は、シフト演算の最終的な結果を保持するノードです。
    • 変更前は nr->type を使用していました。これはシフト量の型です。
    • 変更後は nl->type を使用しています。これは左オペランド(シフトされる変数)の型です。
    • 意味: シフト演算の結果は、シフトされる変数 nl と同じ型を持つべきです。例えば、int32 の変数をシフトした場合、結果も int32 であるべきです。この修正により、シフト結果を格納するレジスタが、元の変数の型に正しく適合するようになり、型の一貫性が保たれます。

これらの変更により、Goコンパイラはシフト代入演算子に対して、より正確で堅牢なコードを生成できるようになりました。

関連リンク

参考にした情報源リンク

  • Go言語のソースコード(特に src/cmd/6g/gen.c の関連部分)
  • コンパイラ設計に関する一般的な知識(レジスタ割り当て、AST、中間表現など)