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

このコミットは、Goコンパイラ（cmd/gc）におけるビットクリア演算子 &^（AND NOT）のコード生成バグを修正するものです。具体的には、コンパイラの最適化フェーズの一つである「ウォーク（walk）」処理において、&^ 演算子が内部的に AND と NOT の組み合わせに変換された際に、その新しいノードの「Ullman数」が正しく再計算されない問題に対処しています。この誤ったUllman数により、コードジェネレータがレジスタ割り当てを誤り、特に関数呼び出しを跨いで値をレジスタに保持しようとする不適切なコードが生成される可能性がありました。

コミット

commit 399dcc75a882fcb3a7edbcb0b272ad4d12ee2555
Author: Russ Cox <rsc@golang.org>
Date:   Mon Feb 4 00:21:44 2013 -0500

    cmd/gc: fix &^ code generation bug
    
    Was not re-walking the new AND node, so that its ullman
    count was wrong, so that the code generator attempted to
    store values in registers across the call.
    
    Fixes #4752.
    
    R=ken2
    CC=golang-dev
    https://golang.org/cl/7288054

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

https://github.com/golang/go/commit/399dcc75a882fcb3a7edbcb0b272ad4d12ee2555

元コミット内容

Goコンパイラ（cmd/gc）において、ビットクリア演算子 &^ のコード生成にバグがありました。このバグは、&^ 演算子が内部的に AND ノードと NOT ノードの組み合わせに変換された後、その新しい AND ノードがコンパイラの「ウォーク」フェーズで適切に再処理されなかったことに起因します。結果として、そのノードのUllman数が誤って計算され、コードジェネレータが関数呼び出しを跨いで値をレジスタに保持しようとする不適切な命令を生成していました。この問題はGoのIssue #4752として報告されていました。

変更の背景

この変更の背景には、Goコンパイラが特定のビット演算子 &^（ビットクリア、AND NOT）を処理する際の内部的な挙動に潜んでいたバグがあります。Go言語では、x &^ y は x AND (NOT y) と等価です。コンパイラは、この &^ 演算子を処理する際に、内部的に抽象構文木（AST）上で OAND（AND演算）と OCOM（ビット反転、NOT演算）の組み合わせに変換します。

問題は、この変換が行われた後、コンパイラの「ウォーク（walk）」フェーズが、新しく生成された OAND ノードを適切に再評価していなかった点にありました。ウォークフェーズは、ASTを走査し、各ノードのプロパティ（例えば、Ullman数）を計算したり、最適化を行ったりする重要な段階です。この再評価の欠如により、OAND ノードのUllman数が誤った値となり、その後のコード生成フェーズに悪影響を及ぼしました。

具体的には、誤ったUllman数に基づいて、コードジェネレータがレジスタ割り当ての判断を誤りました。特に、関数呼び出しを跨いで値をレジスタに保持しようとする不適切なコードが生成され、これが実行時の誤動作やパニックを引き起こす可能性がありました。このバグはGoのIssue #4752として報告されており、本コミットはその修正を目的としています。

前提知識の解説

このコミットを理解するためには、以下のGoコンパイラの内部動作と関連するコンピュータサイエンスの概念について知っておく必要があります。

1. Goコンパイラ (cmd/gc) の構造:

   • Goコンパイラは、ソースコードを機械語に変換する多段階のプロセスを持ちます。主要なフェーズには、字句解析、構文解析、型チェック、中間表現（IR）の生成、最適化、コード生成などがあります。
   • src/cmd/gc/walk.c は、コンパイラの「ウォーク（walk）」フェーズの一部を実装しているファイルです。このフェーズでは、抽象構文木（AST）を走査し、型チェックの完了後、コード生成の準備として様々な変換や最適化を行います。

2. 抽象構文木 (AST):

   • ソースコードは、コンパイラによってツリー構造の抽象構文木に変換されます。各ノードは、変数、演算子、関数呼び出しなどのプログラムの要素を表します。
   • OANDNOT は &^ 演算子（ビットクリア）、OAND は & 演算子（ビットAND）、OCOM は ^ 演算子（ビット反転、NOT）をASTノードとして表します。

3. Ullman数 (Ullman Number):

   • Ullman数（またはUllmanのアルゴリズム）は、コンパイラのコード生成において、式の評価順序を決定し、レジスタの使用を最適化するために用いられる概念です。
   • 具体的には、ASTの各ノードに対して、そのノードを評価するために必要なレジスタの最小数を推定する値です。葉ノード（定数や変数）は通常1、二項演算子ノードは左右の子ノードのUllman数に基づいて計算されます。
   • Ullman数が大きいほど、その式を評価するためにより多くのレジスタが必要になるか、あるいはより複雑なレジスタ割り当て戦略が必要になることを示唆します。コードジェネレータは、このUllman数を利用して、レジスタスピル（レジスタからメモリへの退避）を最小限に抑えるようなコードを生成しようとします。
   • Ullman数が誤っていると、コードジェネレータはレジスタの利用可能性について誤った判断を下し、非効率的または誤ったコード（例: 必要な値をレジスタに保持できない、または不必要にメモリに退避させる）を生成する可能性があります。

4. レジスタ割り当て (Register Allocation):

   • CPUのレジスタは非常に高速な記憶領域であり、プログラムの実行速度に大きく影響します。レジスタ割り当ては、プログラムの変数や中間結果をどのレジスタに割り当てるかを決定するコンパイラの重要な最適化フェーズです。
   • 関数呼び出しを跨いでレジスタの値を保持することは、呼び出し規約（calling convention）によって厳密に管理されます。一般的に、呼び出し元が保存すべきレジスタ（caller-saved registers）と、呼び出し先が保存すべきレジスタ（callee-saved registers）があります。コンパイラがこの規約を誤って解釈すると、関数呼び出しによってレジスタの値が破壊され、バグにつながります。

これらの概念を理解することで、&^ 演算子の変換、Ullman数の誤計算、そしてそれがレジスタ割り当てに与える影響という一連のバグの流れが明確になります。

技術的詳細

このバグは、Goコンパイラの src/cmd/gc/walk.c ファイル内の walkexpr 関数、特に OANDNOT（ビットクリア演算子 &^）の処理ロジックに存在していました。

Go言語の x &^ y というビットクリア演算は、論理的には x & (~y) と等価です。コンパイラはこれを抽象構文木（AST）上で表現するために、OANDNOT ノードを以下のように変換します。

1. n->op = OAND;：元の OANDNOT ノードの演算子を OAND（ビットAND）に変更します。
2. n->right = nod(OCOM, n->right, N);：元の OANDNOT ノードの右オペランド（y に相当）に対して、OCOM（ビット反転、NOT）ノードを新しく作成し、それを新しい OAND ノードの右オペランドとして設定します。
3. typecheck(&n->right, Erv);：新しく作成された OCOM ノードに対して型チェックを実行します。

問題は、この変換が行われた後、新しく生成された OCOM ノードを含む n->right サブツリーに対して、再度 walkexpr が呼び出されていなかった点にありました。

元のコードでは、OANDNOT の処理に入る前に n->right に対して walkexpr が一度呼び出されていましたが、これは OANDNOT が OAND と OCOM に変換される前の元の y に相当するノードに対してでした。変換後、n->right は新しい OCOM ノードを指すようになりますが、この新しいノードのプロパティ（特にUllman数）は、walkexpr が再実行されない限り正しく計算されません。

Ullman数が誤っていると、その後のコード生成フェーズで、レジスタ割り当てのヒューリスティックが誤った判断を下します。コミットメッセージにあるように、「コードジェネレータが関数呼び出しを跨いで値をレジスタに保持しようとした」のは、Ullman数が低く見積もられたために、その値がレジスタに収まり、かつ関数呼び出し後も安全に保持できると誤って判断されたためと考えられます。しかし実際には、関数呼び出しによってそのレジスタの内容が破壊される可能性があり、これがバグの原因となりました。

修正は、typecheck(&n->right, Erv); の直後に walkexpr(&n->right, init); を追加することで、新しく変換された OCOM ノードを含む右サブツリーが適切にウォークされ、そのUllman数を含むすべてのプロパティが正しく計算されるようにしました。これにより、コードジェネレータは正しい情報に基づいてレジスタ割り当てを行うことができるようになり、バグが解消されました。

test/fixedbugs/issue4752.go に追加されたテストケースは、このバグを再現し、修正を検証するために作成されました。特に、G 関数では型アサーション xi.(uint64) と yi.(uint64) の結果に対して直接 &^ 演算を行っており、これがバグをトリガーする特定のパターンでした。F 関数は、型アサーションの結果を変数に代入してから演算を行うため、バグが顕在化しにくいケースとして比較のために用意されています。テストは、両方のケースで期待される結果（0 &^ (1 << 63) が 0 になること）が得られることを確認しています。

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

変更は src/cmd/gc/walk.c ファイルの walkexpr 関数内、OANDNOT ケースにあります。

--- a/src/cmd/gc/walk.c
+++ b/src/cmd/gc/walk.c
@@ -926,10 +926,10 @@ walkexpr(Node **np, NodeList **init)
 
 	case OANDNOT:
 		walkexpr(&n->left, init);
-		walkexpr(&n->right, init); // [削除] 変換前の右オペランドに対するウォーク
 		n->op = OAND;
 		n->right = nod(OCOM, n->right, N);
 		typecheck(&n->right, Erv);
+		walkexpr(&n->right, init); // [追加] 変換後の新しい右オペランド（OCOMノード）に対するウォーク
 		goto ret;
 
 	case ODIV:

コアとなるコードの解説

この変更は、OANDNOT 演算子（Go言語の &^）の処理ロジックを修正しています。

1. walkexpr(&n->left, init);:

   • これは &^ 演算子の左オペランド（x に相当）を再帰的にウォークする部分で、変更はありません。左オペランドは変換の影響を受けないため、これは正しい処理です。

2. - walkexpr(&n->right, init);:

   • この行は削除されました。これは、OANDNOT が OAND と OCOM に変換される前の右オペランド（y に相当）に対して walkexpr を呼び出していました。変換後、n->right は新しい OCOM ノードを指すようになるため、この時点でのウォークは不適切でした。

3. n->op = OAND;:

   • OANDNOT ノードのオペレーションタイプを OAND（ビットAND）に変更します。これは x & (~y) の & 部分を表現します。

4. n->right = nod(OCOM, n->right, N);:

   • 新しい OCOM（ビット反転、NOT）ノードを作成し、元の n->right（y に相当）をその子として設定します。そして、この新しい OCOM ノードを、変換後の OAND ノードの右オペランドとして設定します。これにより、~y の部分が表現されます。

5. typecheck(&n->right, Erv);:

   • 新しく作成された OCOM ノードに対して型チェックを実行します。これは、新しいノードがGoの型システムに適合していることを確認するために必要です。

6. + walkexpr(&n->right, init);:

   • この行が追加された修正の核心です。OANDNOT が OAND と OCOM に変換され、新しい OCOM ノードが n->right に割り当てられた後に、その新しい n->right（つまり OCOM ノード）に対して walkexpr が再帰的に呼び出されます。
   • これにより、新しく生成された OCOM ノードとそのサブツリーが適切にウォークされ、そのUllman数を含むすべてのプロパティが正しく計算されるようになります。この正しいUllman数に基づいて、コードジェネレータはレジスタ割り当てを正確に行うことができ、関数呼び出しを跨ぐレジスタの誤用を防ぎます。

この修正により、コンパイラは &^ 演算子を正しく処理し、最適化フェーズでの誤った情報伝達を防ぎ、結果として正しい機械語コードを生成できるようになりました。

関連リンク

• Go Issue #4752: https://github.com/golang/go/issues/4752
• Gerrit Change-ID: https://golang.org/cl/7288054

参考にした情報源リンク

• Go Issue #4752 (上記に同じ)
• Ullman's algorithm for register allocation (一般的なコンパイラの教科書やオンラインリソース)
  • 例: https://en.wikipedia.org/wiki/Ullman%27s_algorithm (Ullmanのアルゴリズムに関する一般的な情報)
• Goコンパイラのソースコード (src/cmd/gc/walk.c および関連ファイル)
• Go言語のビット演算子に関する公式ドキュメントまたは仕様