[インデックス 163] ファイルの概要
このコミットは、Goコンパイラのコード生成部分、特に複合代入演算子(op=
、例: +=
, -=
, *=
など)の処理を改善し、除算(/=
)と剰余(%=
)演算子における既存のバグを修正するものです。変更は主にsrc/cmd/6g/gen.c
とsrc/cmd/6g/gg.h
の2つのファイルにわたります。
コミット
commit ef61a4cb1ec9ba332ee2d5a788c509d9ae851f19
Author: Ken Thompson <ken@golang.org>
Date: Thu Jun 12 14:21:09 2008 -0700
better version of op=
fixed bugs in /= and %/
SVN=122493
GitHub上でのコミットページへのリンク
https://github.com/golang/go/commit/ef61a4cb1ec9ba332ee2d5a788c509d9ae851f19
元コミット内容
better version of op=
fixed bugs in /= and %/
SVN=122493
変更の背景
このコミットは、Go言語の初期のコンパイラ(6g
、x86-64アーキテクチャ向け)におけるコード生成の品質と正確性を向上させることを目的としています。特に、a op= b
のような複合代入演算子(例: x += y
、z /= w
)の処理に焦点を当てています。
以前の実装では、これらの演算子、特に除算(/=
)と剰余(%=
)において、正しくないコードが生成されるバグが存在していました。これは、オペランドの評価順序やレジスタ割り当ての最適化が不十分であったことに起因すると考えられます。コンパイラは、ソースコードを機械語に変換する際に、式の評価順序を最適化し、レジスタを効率的に使用する必要があります。このコミットは、Ullman数に基づく評価順序の改善と、より堅牢なレジスタ管理によって、これらの問題を解決しようとしています。
前提知識の解説
- Goコンパイラ (6g): このコミットが対象としているのは、Go言語の初期のコンパイラの一つである
6g
です。これは、x86-64アーキテクチャ(64ビットIntel/AMDプロセッサ)向けのGoコードをコンパイルするためのツールでした。Goコンパイラは、フロントエンド(構文解析、意味解析)とバックエンド(コード生成、最適化)に分かれています。この変更はバックエンドのコード生成部分に該当します。 - AST (Abstract Syntax Tree): コンパイラはソースコードを解析し、抽象構文木(AST)と呼ばれるツリー構造に変換します。ASTの各ノードは、変数、演算子、関数呼び出しなどのプログラム要素を表します。
Node
構造体: Goコンパイラ内部では、ASTの各要素がNode
構造体として表現されます。n->left
やn->right
は、二項演算子の場合に左右のオペランドのノードを指します。cgen
(Code Generation):cgen
関数は、ASTノードを受け取り、それに対応する機械語命令を生成する役割を担います。igen
(Address Generation):igen
関数は、変数のアドレスを計算し、レジスタにロードするなどの処理を行います。regalloc
/regfree
(Register Allocation/Deallocation):regalloc
は、計算結果を一時的に保持するために利用可能なCPUレジスタを割り当てます。regfree
は、使用済みのレジスタを解放します。レジスタはCPUが直接アクセスできる高速なメモリであり、その効率的な利用は生成されるコードの性能に直結します。gins
(Generate Instruction):gins
は、指定されたオペレーション(例: 加算、乗算)に対応する機械語命令を生成します。gmove
(Generate Move Instruction):gmove
は、ある場所(レジスタ、メモリ)から別の場所へデータを移動する機械語命令を生成します。- Ullman数 (Ullman Number): Ullman数は、コンパイラの最適化において、式の評価順序を決定するために使用されるヒューリスティックな値です。ツリー構造の各ノードに対して計算され、そのノードを評価するために必要なレジスタの最小数を示します。Ullman数が大きいサブツリーは、より多くのレジスタを必要とするため、先に評価することでレジスタの競合を減らし、効率的なコードを生成できる可能性があります。
技術的詳細
このコミットの核心は、src/cmd/6g/gen.c
内のcgen_asop
関数の変更にあります。この関数は、a op= b
形式の複合代入演算子(例: x += y
、p *= q
)のコード生成を担当します。
変更点:
-
関数シグネチャの変更:
- 変更前:
void cgen_asop(Node *nl, Node *nr, int op)
- 変更後:
void cgen_asop(Node *n)
変更前は左辺(nl
)、右辺(nr
)、演算子タイプ(op
)を直接引数として受け取っていましたが、変更後は単一のNode *n
を受け取るようになりました。このn
は複合代入演算子全体のASTノードを表し、そのleft
フィールドが左辺、right
フィールドが右辺、etype
フィールドが実際の演算子(例:OADD
、ODIV
)を保持します。これにより、関数のインターフェースがより統一され、AST構造との整合性が高まりました。
- 変更前:
-
Ullman数に基づく評価順序の最適化: 最も重要な変更は、右辺(
nr
)と左辺(nl
)のUllman数を比較し、評価順序を動的に決定するロジックが導入されたことです。- 変更前:
このコードは、右辺のUllman数が左辺より大きい場合にif(nr->ullman > nl->ullman) { fatal("gcgen_asopen"); }
fatal
エラーを発生させていました。これは、コンパイラがそのようなケースを適切に処理できないか、特定の評価順序を前提としていたことを示唆しています。特に、右辺が複雑な式である場合に問題が発生しやすかったと考えられます。 - 変更後:
この新しいロジックは、Ullman数に基づいて、より複雑なオペランドを先に評価するようにレジスタ割り当てとコード生成の順序を調整します。これにより、レジスタの競合を最小限に抑え、より効率的で正しいコードが生成されるようになります。特に、除算や剰余のような特定のレジスタを必要とする演算において、この評価順序の最適化はバグの修正に貢献します。if(nr->ullman > nl->ullman) { // 右辺が左辺より複雑な場合、右辺を先に評価 regalloc(&n2, nl->type, N); // nrの評価結果を保持するレジスタを割り当て cgen(nr, &n2); // nrのコードを生成し、結果をn2に格納 igen(nl, &n1, N); // nlのアドレスをn1に格納 } else { // 左辺が右辺より複雑、または同等の場合、左辺のアドレスを先に生成 igen(nl, &n1, N); // nlのアドレスをn1に格納 regalloc(&n2, nl->type, N); // nrの評価結果を保持するレジスタを割り当て cgen(nr, &n2); // nrのコードを生成し、結果をn2に格納 }
- 変更前:
-
汎用的な複合代入処理: 新しいコードでは、一時的な
Node n3
を作成し、これに元の演算子(n->etype
)と、評価済みの左辺(n1
)と右辺(n2
)を割り当てています。n3 = *n; n3.left = &n1; n3.right = &n2; n3.op = n->etype; // 元の演算子(例: OADD, ODIV) regalloc(&n4, nr->type, N); // 演算結果を保持するレジスタを割り当て cgen(&n3, &n4); // n3(二項演算)のコードを生成し、結果をn4に格納 gmove(&n4, &n1); // n4の結果をnlのアドレス(n1)に移動
このアプローチにより、複合代入演算子を一般的な二項演算として扱い、その結果を左辺のメモリ位置に格納するという、より汎用的で堅牢なコード生成パスが実現されます。これにより、特定の演算子(
/=
や%=
)に特有のバグが修正されたと考えられます。
コアとなるコードの変更箇所
src/cmd/6g/gen.c
--- a/src/cmd/6g/gen.c
+++ b/src/cmd/6g/gen.c
@@ -275,7 +275,7 @@ loop:
break;
case OASOP:
- cgen_asop(n->left, n->right, n->etype);
+ cgen_asop(n);
break;
case OAS:
@@ -683,40 +683,40 @@ cgen_ret(Node *n)\n }\n \n void
-cgen_asop(Node *nl, Node *nr, int op)\n+\tNode n1, n2, n3, n4;\n+\tNode *nl, *nr;\n+\n+\tnl = n->left;\n+\tnr = n->right;\n \n \tif(nr->ullman >= UINF && nl->ullman >= UINF) {\n \t\tfatal(\"cgen_asop both sides call\");\n \t}\n \n-// BOTCH make special case for DIVQ\n-\n-\ta = optoas(op, nl->type);\n-\tif(nl->addable) {\n-\t\tregalloc(&n2, nr->type, N);\n+\tif(nr->ullman > nl->ullman) {\n+\t\tregalloc(&n2, nl->type, N);\n+\t\tcgen(nr, &n2);\n+\t\tigen(nl, &n1, N);\n+\t} else {\n+\t\tigen(nl, &n1, N);\n+\t\tregalloc(&n2, nl->type, N);\
\t\tcgen(nr, &n2);\n-\t\tregalloc(&n1, nl->type, N);\n-\t\tcgen(nl, &n1);\n-\t\tgins(a, &n2, &n1);\n-\t\tgmove(&n1, nl);\n-\t\tregfree(&n1);\n-\t\tregfree(&n2);\n-\t\treturn;\n \t}\n \n-\tif(nr->ullman > nl->ullman) {\n-\t\tfatal(\"gcgen_asopen\");\n-\t}\n+\tn3 = *n;\n+\tn3.left = &n1;\n+\tn3.right = &n2;\n+\tn3.op = n->etype;\n+\n+\tregalloc(&n4, nr->type, N);\n+\tcgen(&n3, &n4);\n+\tgmove(&n4, &n1);\
\n-\tregalloc(&n1, nl->type, N);\n-\tigen(nl, &n2, N);\n-\tcgen(nr, &n1);\n-\tgins(a, &n1, &n2);\n \tregfree(&n1);\n \tregfree(&n2);\n+\tregfree(&n4);\n }\n \n void
src/cmd/6g/gg.h
--- a/src/cmd/6g/gg.h
+++ b/src/cmd/6g/gg.h
@@ -109,7 +109,7 @@ Node*\tlookdot(Node*, Node*, int);\n void\tinarggen(void);\n void\tagen_inter(Node*, Node*);\n void\tcgen_as(Node*, Node*, int);\n-void\tcgen_asop(Node*, Node*, int);\n+void\tcgen_asop(Node*);\n void\tcgen_ret(Node*);\n void\tcgen_call(Node*);\n void\tcgen_callmeth(Node*);\
コアとなるコードの解説
変更されたcgen_asop
関数は、複合代入演算子(a op= b
)のコード生成をより堅牢かつ効率的に行います。
-
引数の変更と内部でのノード抽出: 関数は
Node *n
という単一の引数を受け取ります。このn
は、OASOP
(複合代入演算子)タイプのASTノードです。関数内部で、n->left
から左辺(nl
)を、n->right
から右辺(nr
)を抽出します。 -
Ullman数による評価順序の決定:
if(nr->ullman > nl->ullman)
の条件分岐が導入されました。- もし右辺
nr
のUllman数が左辺nl
より大きい場合(つまり、nr
の評価がより複雑で多くのレジスタを必要とする場合)、まずnr
のコードを生成し、その結果を一時レジスタn2
に格納します。その後、nl
のアドレスをn1
に格納します。 - そうでない場合(
nl
がnr
より複雑、または同等の場合)、まずnl
のアドレスをn1
に格納し、その後nr
のコードを生成して結果をn2
に格納します。 このロジックにより、レジスタの競合を避け、効率的なコード生成が可能になります。
- もし右辺
-
汎用的な二項演算の生成:
Node n3
が宣言され、元の複合代入ノードn
の内容がコピーされます。そして、n3.left
にn1
(左辺のアドレス)、n3.right
にn2
(右辺の値)、n3.op
に元の演算子タイプ(n->etype
、例:OADD
、ODIV
)が設定されます。 これにより、n3
はnl op nr
という通常の二項演算を表すノードとして機能します。 -
結果の格納:
cgen(&n3, &n4)
が呼び出され、n3
で表される二項演算のコードが生成され、その結果が一時レジスタn4
に格納されます。 最後に、gmove(&n4, &n1)
によって、n4
に格納された演算結果が、左辺nl
のアドレスを指すn1
に移動(ストア)されます。これにより、nl
の値が更新されます。 -
レジスタの解放: 使用した一時レジスタ
n1
,n2
,n4
はregfree
によって解放されます。
この一連の変更により、複合代入演算子のコード生成がより構造化され、特に除算や剰余のような複雑な演算において、オペランドの評価順序とレジスタ管理が最適化され、以前のバグが修正されました。
関連リンク
- Go言語の初期のコンパイラに関する情報は、現在のGoのソースコードリポジトリの
src/cmd/compile
以下や、Goの歴史に関するドキュメントに散見されます。 - Ullman数やコンパイラのコード生成に関する一般的な情報は、コンパイラ設計の教科書(例: Dragon Book)に詳しく記載されています。
参考にした情報源リンク
- Go言語のソースコード (特に
src/cmd/6g
ディレクトリの歴史的なコミット) - コンパイラ設計の原則に関する一般的な知識
- Ullman数のアルゴリズムに関する情報