[インデックス 123] ファイルの概要
このコミットは、Goコンパイラのx86-64アーキテクチャ向けバックエンドである6g
のコード生成部分、具体的にはsrc/cmd/6g/gen.c
ファイルに対する変更です。このファイルは、Go言語のソースコードをx86-64アセンブリコードに変換する際の、様々な命令の生成ロジックを含んでいます。特に、整数除算(div
)と剰余(mod
)演算のコード生成に関する改善が行われています。
コミット
more div/mod
SVN=121577
GitHub上でのコミットページへのリンク
https://github.com/golang/go/commit/181ad4743cdf29a4ef71f97ad1ea0d2840696714
元コミット内容
commit 181ad4743cdf29a4ef71f97ad1ea0d2840696714
Author: Ken Thompson <ken@golang.org>
Date: Fri Jun 6 21:21:54 2008 -0700
more div/mod
SVN=121577
変更の背景
このコミットは、Goコンパイラの初期段階における、x86-64アーキテクチャでの整数除算および剰余演算のコード生成ロジックの改善を目的としています。x86アーキテクチャでは、DIV
命令やIDIV
命令(符号付き除算)は、特定のレジスタ(RAX
とRDX
)を暗黙的に使用するという特殊な性質を持っています。具体的には、除算の被除数はRDX:RAX
レジスタペアに格納され、除算後には商がRAX
に、剰余がRDX
に格納されます。
従来のコード生成では、これらのレジスタが既に他の目的で使用されている場合に、コンパイラが適切にレジスタを退避・復元する処理が不足していた可能性があります。その結果、レジスタの衝突が発生し、誤ったコードが生成されたり、コンパイラが異常終了したりする可能性がありました。
このコミットは、cgen_div
関数(除算のコード生成を担当する関数)において、RAX
とRDX
レジスタが既に占有されている場合に、それらのレジスタの内容を一時的に退避し、除算命令の実行後に復元するロジックを追加することで、この問題を解決しようとしています。これにより、より堅牢で正しい除算・剰余のコード生成が可能になります。
前提知識の解説
x86-64アーキテクチャにおける整数除算とレジスタ
x86-64アーキテクチャでは、整数除算命令(DIV
またはIDIV
)は、以下のように特定のレジスタを暗黙的に使用します。
RAX
(Accumulator Register): 64ビットの汎用レジスタ。除算命令では、被除数の下位64ビットを格納し、除算後には商が格納されます。RDX
(Data Register): 64ビットの汎用レジスタ。除算命令では、被除数の上位64ビットを格納し、除算後には剰余が格納されます。
符号付き除算(IDIV
)の場合、被除数が64ビットであっても、除算前にRAX
の内容をRDX
に符号拡張するCQO
(Convert Quadword to Octaword)命令(32ビットの場合はCDQ
)がよく使用されます。これにより、RDX:RAX
レジスタペア全体で128ビットの被除数を表現します。
コンパイラのレジスタ割り当て
コンパイラは、プログラムの実行速度を最大化するために、頻繁に使用される値をCPUのレジスタに割り当てます。これをレジスタ割り当て(Register Allocation)と呼びます。しかし、レジスタの数は限られているため、コンパイラはどの値をどのレジスタに割り当てるかを慎重に決定する必要があります。
特定の命令(今回のDIV
/IDIV
のように)が特定のレジスタを暗黙的に使用する場合、コンパイラはそのレジスタが他の目的で使用されていないことを確認するか、もし使用されている場合はその内容を一時的にメモリに退避(spill)し、命令実行後にレジスタに復元(reload)する必要があります。このプロセスは「レジスタの退避と復元」と呼ばれます。
Ullman Number (ウルマン数)
Ullman Numberは、コンパイラの最適化、特にレジスタ割り当ての文脈で用いられる概念です。式木の各ノードに対して計算される値で、そのノードを評価するために必要なレジスタの最小数を示します。Ullman Numberが大きいほど、そのサブツリーの評価にはより多くのレジスタが必要となる可能性があり、コンパイラはレジスタの利用効率を考慮してコード生成の順序を決定します。
このコミットのコードでは、nl->ullman >= nr->ullman
という条件が見られます。これは、左オペランド(nl
)と右オペランド(nr
)のどちらを先に評価するかを決定する際に、Ullman Numberを考慮していることを示唆しています。一般的に、Ullman Numberが大きい方を先に評価することで、レジスタのスピルを減らすことができる場合があります。
Goコンパイラ(6g
)の内部関数
nodreg(Node *n, Type *t, int r)
: 指定されたレジスタr
に対応するノードn
を作成します。regalloc(Node *n, Type *t, Node *res)
: レジスタを割り当てます。n
にレジスタを割り当て、その結果をres
に格納します。regfree(Node *n)
: 割り当てられたレジスタを解放します。gmove(Node *f, Node *t)
:f
からt
へデータを移動するアセンブリ命令を生成します。gins(int as, Node *f, Node *t)
: 指定されたアセンブリ命令as
とオペランドf
,t
を用いてアセンブリ命令を生成します。AMOVQ
: 64ビットデータを移動する命令(MOVQ
)。ACDQ
: 32ビットのEAX
レジスタの内容をEDX:EAX
に符号拡張する命令(CDQ
)。64ビットの場合はCQO
に相当する処理が行われます。
optoas(int op, Type *t)
: Goの演算子(op
)を対応するアセンブリ命令(as
)に変換します。ODIV
は除算、OMOD
は剰余に対応します。
技術的詳細
このコミットの主要な変更は、cgen_div
関数におけるRAX
(D_AX
)とRDX
(D_DX
)レジスタの取り扱いを改善した点です。
変更前は、cgen_div
の冒頭でreg[D_AX] || reg[D_DX]
が真の場合にfatal("registers occupide")
としてコンパイラを異常終了させていました。これは、除算命令がこれらのレジスタを暗黙的に使用するため、既に占有されている場合は処理できないという単純な実装でした。
変更後は、samereg
という新しいヘルパー関数が導入され、RAX
またはRDX
が既に占有されている場合でも、そのレジスタが除算結果の格納先(res
)と同じでない限り、レジスタの内容を一時的に退避・復元するロジックが追加されました。
samereg
関数の追加
+int
+samereg(Node *a, Node *b)
+{
+\tif(a->op != OREGISTER)
+\t\treturn 0;
+\tif(b->op != OREGISTER)
+\t\treturn 0;
+\tif(a->val.vval != b->val.vval)
+\t\treturn 0;
+\treturn 1;
+}
この関数は、2つのNode
が同じレジスタを表しているかどうかをチェックします。OREGISTER
オペランドであり、かつval.vval
(レジスタ番号)が同じであれば、同じレジスタであると判断します。
cgen_div
関数の変更点
-
レジスタ退避・復元ロジックの追加:
RAX
(D_AX
)とRDX
(D_DX
)レジスタが既に占有されている場合、かつそのレジスタが除算結果の格納先(res
)ではない場合に、以下の処理を行います。- 一時的なノード
n3
を割り当てます。 - 占有されているレジスタ(
n1
またはn2
)の内容をn3
に移動(AMOVQ
)して退避します。 - 占有されているレジスタを解放(
regfree
)し、reg[D_AX]
またはreg[D_DX]
を0に設定して、レジスタが空いている状態にします。 - 再帰的に
cgen_div
を呼び出し、除算のコードを生成させます。 - 除算処理が完了した後、退避しておいた
n3
の内容を元のレジスタ(n1
またはn2
)に復元(AMOVQ
)します。 - 一時的なノード
n3
を解放します。
この再帰的な呼び出しと退避・復元メカニズムにより、
RAX
やRDX
が一時的に必要となる除算命令の実行中に、これらのレジスタが他の目的で占有されていても、その内容が失われることなく処理を進めることができるようになります。 - 一時的なノード
-
Ullman Numberに基づく評価順序の改善: 変更前は、
nl->ullman >= nr->ullman
の条件分岐内で、nr->addable
(右オペランドが直接アセンブリ命令のオペランドとして使用可能か)によってコード生成のパスが分かれていました。 変更後は、このnr->addable
による分岐が削除され、常にcgen(nr, &n3); gins(a, &n3, N);
という形式で右オペランドを評価し、その結果をレジスタn3
に格納してから除算命令を実行するようになりました。これにより、コード生成のロジックが簡素化され、一貫性が保たれています。 -
レジスタ解放のタイミングの調整: 変更前は、
n3
レジスタの解放が条件分岐の内部で行われていましたが、変更後はcgen_div
関数の最後に一度だけregfree(&n3);
が呼び出されるようになりました。これにより、n3
レジスタのライフタイムが適切に管理され、不要なレジスタの占有を防ぎます。
コアとなるコードの変更箇所
--- a/src/cmd/6g/gen.c
+++ b/src/cmd/6g/gen.c
@@ -827,49 +827,85 @@ cgen_as(Node *nl, Node *nr, int op)\n cgen(nr, nl);\n }\n \n+int\n+samereg(Node *a, Node *b)\n+{\n+\tif(a->op != OREGISTER)\n+\t\treturn 0;\n+\tif(b->op != OREGISTER)\n+\t\treturn 0;\n+\tif(a->val.vval != b->val.vval)\n+\t\treturn 0;\n+\treturn 1;\n+}\n+\n void\n cgen_div(int op, Node *nl, Node *nr, Node *res)\n {\n Node n1, n2, n3;\n-\tint a;\n+\tint a, rax, rdx;\n \n-\tif(reg[D_AX] || reg[D_DX]) {\n-\t\tfatal(\"registers occupide\");\n-\t}\n+\tnodreg(&n1, types[TINT64], D_AX);\
+\tnodreg(&n2, types[TINT64], D_DX);\
\n-\ta = optoas(op, nl->type);\
+\trax = reg[D_AX];\
+\trdx = reg[D_DX];\
+\n \t// hold down the DX:AX registers\n-\tnodreg(&n1, types[TINT64], D_AX);\
-\tnodreg(&n2, types[TINT64], D_DX);\
\tregalloc(&n1, nr->type, &n1);\
+\tif(rax && !samereg(res, &n1)) {\
+\t\t// clean out the AX register\n+\t\tregalloc(&n3, types[TINT64], N);\
+\t\tgins(AMOVQ, &n1, &n3);\
+\t\tregfree(&n1);\
+\n+\t\treg[D_AX] = 0;\
+\t\tcgen_div(op, nl, nr, res);\
+\t\treg[D_AX] = rax;\
+\n+\t\tgins(AMOVQ, &n3, &n1);\
+\t\tregfree(&n3);\
+\t\treturn;\n+\t}\n+\n \tregalloc(&n2, nr->type, &n2);\
+\tif(rdx && !samereg(res, &n2)) {\
+\t\t// clean out the DX register\n+\t\tregalloc(&n3, types[TINT64], N);\
+\t\tgins(AMOVQ, &n2, &n3);\
+\t\tregfree(&n1);\
+\n+\t\treg[D_DX] = 0;\
+\t\tcgen_div(op, nl, nr, res);\
+\t\treg[D_DX] = rdx;\
+\n+\t\tgins(AMOVQ, &n3, &n2);\
+\t\tregfree(&n3);\
+\t\treturn;\n+\t}\n+\n+\ta = optoas(op, nl->type);\
\n \tif(!issigned[nl->type->etype]) {\n \t\tnodconst(&n3, nl->type, 0);\
\t\tgmove(&n3, &n2);\
\t}\n \n+\tregalloc(&n3, nr->type, res);\
\tif(nl->ullman >= nr->ullman) {\n \t\tcgen(nl, &n1);\
\t\tif(issigned[nl->type->etype])\n \t\t\tgins(ACDQ, N, N);\
-\t\tif(!nr->addable) {\n-\t\t\tregalloc(&n3, nr->type, res);\
-\t\t\tcgen(nr, &n3);\
-\t\t\tgins(a, &n3, N);\
-\t\t\tregfree(&n3);\
-\t\t} else\n-\t\t\tgins(a, nr, N);\
+\t\tcgen(nr, &n3);\
+\t\tgins(a, &n3, N);\
\t} else {\n-\t\tregalloc(&n3, nr->type, res);\
\t\tcgen(nr, &n3);\
\t\tcgen(nl, &n1);\
\t\tif(issigned[nl->type->etype])\n \t\t\tgins(ACDQ, N, N);\
\t\tgins(a, &n3, N);\
-\t\tregfree(&n3);\
\t}\n+\tregfree(&n3);\
\n \tif(op == ODIV)\n \t\tgmove(&n1, res);\
コアとなるコードの解説
samereg
関数の追加 (行 831-838)
- この新しい関数は、2つのノードが同じレジスタを参照しているかどうかを効率的にチェックするために導入されました。
a->op != OREGISTER
やb->op != OREGISTER
で、ノードがレジスタではない場合は即座に0
(偽)を返します。a->val.vval != b->val.vval
で、レジスタの識別子(レジスタ番号)が異なる場合も0
を返します。- 両方の条件を満たせば、同じレジスタであると判断し
1
(真)を返します。
cgen_div
関数の変更 (行 841-885)
-
レジスタ退避・復元ロジックの導入 (行 846-869):
rax = reg[D_AX];
とrdx = reg[D_DX];
で、現在のRAX
とRDX
レジスタの占有状態を保存します。nodreg(&n1, types[TINT64], D_AX);
とnodreg(&n2, types[TINT64], D_DX);
で、RAX
とRDX
に対応するノードを作成します。regalloc(&n1, nr->type, &n1);
とregalloc(&n2, nr->type, &n2);
で、RAX
とRDX
を割り当てます。if(rax && !samereg(res, &n1))
とif(rdx && !samereg(res, &n2))
のブロックが、レジスタ退避・復元の中核です。rax
またはrdx
が0
でない(つまり、RAX
またはRDX
が既に占有されている)ことを確認します。!samereg(res, &n1)
または!samereg(res, &n2)
で、除算結果の格納先レジスタ(res
)が、現在占有されているRAX
またはRDX
とは異なることを確認します。- これらの条件が満たされた場合、以下の処理が行われます。
regalloc(&n3, types[TINT64], N);
で一時レジスタn3
を割り当てます。gins(AMOVQ, &n1, &n3);
またはgins(AMOVQ, &n2, &n3);
で、占有されているレジスタの内容をn3
に退避します。regfree(&n1);
またはregfree(&n2);
で、占有されているレジスタを解放します。reg[D_AX] = 0;
またはreg[D_DX] = 0;
で、コンパイラのレジスタ管理状態を更新し、該当レジスタが空いているとマークします。cgen_div(op, nl, nr, res);
で、cgen_div
関数を再帰的に呼び出します。これにより、RAX
/RDX
が空いている状態で除算のコードが生成されます。reg[D_AX] = rax;
またはreg[D_DX] = rdx;
で、元のレジスタ占有状態を復元します。gins(AMOVQ, &n3, &n1);
またはgins(AMOVQ, &n3, &n2);
で、退避しておいた内容を元のレジスタに戻します。regfree(&n3);
で一時レジスタn3
を解放します。return;
で、現在のcgen_div
の実行を終了します。再帰呼び出しによって既に処理が完了しているためです。
-
被除数の符号拡張 (行 875, 881):
if(issigned[nl->type->etype]) gins(ACDQ, N, N);
は、被除数(nl
)が符号付き整数型の場合に、RAX
の内容をRDX:RAX
に符号拡張する命令(ACDQ
はCDQ
またはCQO
に相当)を生成します。これは、符号付き除算の前に必須のステップです。
-
右オペランドの評価と除算命令の生成 (行 876-877, 882-883):
regalloc(&n3, nr->type, res);
で、右オペランド(除数)を格納するための一時レジスタn3
を割り当てます。cgen(nr, &n3);
で、右オペランドnr
のコードを生成し、結果をn3
に格納します。gins(a, &n3, N);
で、除算命令(a
はIDIV
またはDIV
)を生成します。この命令は、RDX:RAX
をn3
の内容で除算します。
-
レジスタ解放の統一 (行 885):
regfree(&n3);
が関数の最後に移動され、n3
レジスタの解放が統一的に行われるようになりました。これにより、レジスタのライフタイム管理が改善されています。
関連リンク
- Go言語のコンパイラに関する情報: https://go.dev/doc/compiler
- x86-64命令セットリファレンス(Intel Software Developer's Manualなど)
- コンパイラのレジスタ割り当てに関する一般的な情報
参考にした情報源リンク
- https://github.com/golang/go/commit/181ad4743cdf29a4ef71f97ad1ea0d2840696714
- x86 Assembly Guide: https://www.cs.virginia.edu/~evans/cs216/guides/x86.html
- Ullman's Algorithm for Register Allocation: https://en.wikipedia.org/wiki/Ullman%27s_algorithm (一般的な情報源として)
- Go Compiler Source Code (for context on
6g
,Node
,Type
,reg
etc.): https://github.com/golang/go