[インデックス 122] ファイルの概要
このコミットは、Go言語の初期のコンパイラである 6g
(AMD64アーキテクチャ向け) において、除算 (div
) および剰余 (mod
) 演算子のコード生成ロジックを改善し、より正確かつ効率的にアセンブリコードに変換できるようにするためのものです。具体的には、これらの演算子に対する専用のコード生成関数 cgen_div
を導入し、符号付き/符号なし整数、および異なるデータ型サイズに応じた適切なx86アセンブリ命令(DIV
, IDIV
)を生成するように拡張しています。
コミット
div and mod operators
SVN=121576
GitHub上でのコミットページへのリンク
https://github.com/golang/go/commit/d83b994da62f88d9bee5ab62702cb560e9c3ad48
元コミット内容
commit d83b994da62f88d9bee5ab62702cb560e9c3ad48
Author: Ken Thompson <ken@golang.org>
Date: Fri Jun 6 20:43:29 2008 -0700
div and mod operators
SVN=121576
変更の背景
Go言語の初期開発段階において、コンパイラは様々な演算子に対するコード生成ロジックを段階的に実装していました。除算と剰余演算は、特にx86アーキテクチャにおいて、他の二項演算子(加算、減算など)とは異なる特殊なアセンブリ命令とレジスタの使用パターンを必要とします。具体的には、DIV
(符号なし除算) および IDIV
(符号付き除算) 命令は、被除数を DX:AX
(または EDX:EAX
, RDX:RAX
) レジスタペアに配置し、商を AX
(または EAX
, RAX
) に、剰余を DX
(または EDX
, RDX
) に格納するという独特の動作をします。
このコミット以前は、除算と剰余のコード生成が他の一般的な二項演算子と同じような非対称二項演算子として扱われていた可能性があります。しかし、その特殊性から、専用のコード生成パスとレジスタ管理が必要とされました。この変更は、6g
コンパイラがGo言語の除算および剰余演算を正確かつ効率的に機械語に変換できるようにするために導入されました。また、SVN=121576
という記述は、このコミットがGoプロジェクトがSubversionからGitへ移行する過程で取り込まれたものであり、当時のSubversionリビジョン番号を示しています。
前提知識の解説
Go言語の初期コンパイラ 6g
Go言語の初期には、各アーキテクチャ向けに異なるコンパイラが存在しました。6g
は、AMD64 (x86-64) アーキテクチャをターゲットとするGoコンパイラの名称でした。Goのコンパイラは、gc
(Go compiler) という共通のコードベースから派生し、ターゲットアーキテクチャに応じて 8g
(ARM), 5g
(PowerPC) などと命名されていました。これらのコンパイラは、Go言語のソースコードを直接アセンブリコードに変換する役割を担っていました。
コンパイラのコード生成フェーズ
コンパイラは、ソースコードを機械語に変換する過程で複数のフェーズを経ます。
- 字句解析 (Lexical Analysis): ソースコードをトークンに分割します。
- 構文解析 (Parsing): トークン列から抽象構文木 (AST) を構築します。
- 意味解析 (Semantic Analysis): 型チェックや名前解決などを行い、ASTに意味的な情報を付加します。
- 中間表現生成 (Intermediate Representation Generation): ASTを、より機械語に近い中間表現に変換します。
- コード生成 (Code Generation): 中間表現をターゲットアーキテクチャの機械語(アセンブリコード)に変換します。このコミットは、このコード生成フェーズにおける除算・剰余演算の処理に焦点を当てています。
- 最適化 (Optimization): 生成されたコードの効率を改善します。
x86アセンブリにおける除算・剰余演算
x86アーキテクチャでは、整数除算には DIV
(unsigned division) と IDIV
(signed division) の2つの命令があります。これらの命令は、他の算術命令とは異なり、特定のレジスタを使用するという特徴があります。
- 被除数 (Dividend): 除算を行う前に、被除数は
DX:AX
(16ビット除算の場合)、EDX:EAX
(32ビット除算の場合)、またはRDX:RAX
(64ビット除算の場合) のレジスタペアに格納されます。例えば、32ビットの除算を行う場合、被除数の上位32ビットがEDX
に、下位32ビットがEAX
に格納されます。 - 除数 (Divisor): 除数は、命令のオペランドとして指定されたレジスタまたはメモリ位置に格納されます。
- 結果:
- 商 (Quotient):
AX
(EAX
/RAX
) レジスタに格納されます。 - 剰余 (Remainder):
DX
(EDX
/RDX
) レジスタに格納されます。
- 商 (Quotient):
符号拡張 (Sign Extension)
符号付き除算 (IDIV
) の場合、被除数が負の値であると、DX:AX
レジスタペア全体で正しい符号を表現するために、符号拡張が必要です。これは CDQ
(Convert Doubleword to Quadword) 命令などを用いて行われます。CDQ
は EAX
の符号ビットを EDX
の全ビットにコピーすることで、EDX:EAX
を符号付き64ビット値として正しく表現します。
Ullman Number (ウルマン数)
Ullman Numberは、コンパイラの最適化、特にレジスタ割り当てにおいて使用される概念です。抽象構文木 (AST) の各ノードに割り当てられる数値で、そのノードを評価するために必要なレジスタの最小数を示します。Ullman Numberが低いノードから評価することで、レジスタの使用効率を高め、レジスタスピル(レジスタの内容をメモリに退避させること)を減らすことができます。このコミットのコードでは、nl->ullman >= nr->ullman
のような比較があり、これは左右のオペランドの評価順序を決定する際にUllman Numberを考慮していることを示唆しています。
技術的詳細
このコミットの主要な技術的変更点は、除算と剰余演算のための専用コード生成関数 cgen_div
の導入と、それに伴うコンパイラの各モジュールの連携です。
-
src/cmd/6g/cgen.c
の変更:- 以前は
OMOD
(剰余) とODIV
(除算) がOSUB
(減算) などと同じ「非対称二項演算子」のカテゴリで処理されていました。 - この変更により、
OMOD
とODIV
はこのカテゴリから削除され、代わりにcgen_div(n->op, nl, nr, res);
という専用の関数呼び出しに置き換えられました。これは、除算と剰余が特殊な処理を必要とすることを明確に示しています。
- 以前は
-
src/cmd/6g/gen.c
へのcgen_div
関数の追加:cgen_div(int op, Node *nl, Node *nr, Node *res)
関数が新しく追加されました。この関数が除算と剰余のコード生成の核心を担います。- レジスタ管理:
D_AX
(AX/EAX/RAX) とD_DX
(DX/EDX/RDX) レジスタが除算命令で排他的に使用されるため、関数冒頭でこれらのレジスタが占有されていないかチェックしています (fatal("registers occupide")
)。これは、コンパイラがこれらのレジスタを他の目的で使用していないことを保証するためです。 - レジスタ割り当て:
nodreg
とregalloc
を使用して、D_AX
とD_DX
に対応する一時レジスタノードn1
とn2
を割り当てています。n1
は商、n2
は剰余を格納するために使用されます。 - 符号なし除算の準備: オペランドが符号なし (
!issigned[nl->type->etype]
) の場合、DX
レジスタ (n2
) をゼロクリアしています (nodconst(&n3, nl->type, 0); gmove(&n3, &n2);
)。これは、符号なし除算ではDX
の上位ビットがゼロである必要があるためです。 - オペランド評価順序:
if(nl->ullman >= nr->ullman)
の条件で、左右のオペランド (nl
,nr
) のUllman Numberを比較し、レジスタ使用効率を考慮した評価順序を決定しています。Ullman Numberが大きい方(より多くのレジスタを必要とする可能性のある方)を先に評価することで、レジスタの競合を減らします。- 左オペランド (
nl
) をAX
(n1
) に生成し、符号付きの場合はACDQ
(x86のCDQ
命令に対応) で符号拡張を行います。 - 右オペランド (
nr
) が直接アセンブリ命令のオペランドとして使用できない場合 (!nr->addable
) は、一時レジスタn3
に生成してから除算命令を実行します。
- 左オペランド (
- 除算命令の生成:
gins(a, &n3, N)
またはgins(a, nr, N)
を呼び出して、実際の除算命令を生成します。a
はoptoas
関数によって決定された適切なアセンブリ命令(AIDIVB
,ADIVB
など)です。 - 結果の格納:
op == ODIV
(除算) の場合、AX
レジスタ (n1
) の内容を結果ノードres
に移動します (gmove(&n1, res);
)。- それ以外 (
OMOD
、剰余) の場合、DX
レジスタ (n2
) の内容を結果ノードres
に移動します (gmove(&n2, res);
)。
- レジスタ解放: 最後に
regfree(&n1); regfree(&n2);
で一時レジスタを解放します。
-
src/cmd/6g/gg.h
の変更:cgen_div
関数のプロトタイプvoid cgen_div(int, Node*, Node*, Node*);
が追加されました。これにより、他のコンパイラモジュールからcgen_div
を呼び出すことが可能になります。
-
src/cmd/6g/gsubr.c
のoptoas
関数の変更:optoas
関数は、Goの演算子 (op
) と型 (t
) に基づいて、対応するx86アセンブリ命令のオペコードを返す役割を担っています。- このコミットでは、
OMOD
(剰余) 演算子に対するケースが追加されました。これにより、OMOD
がODIV
と同じように、データ型サイズ(8ビット、16ビット、32ビット、64ビット)と符号付き/符号なしに応じて、適切なAIDIV*
(符号付き) またはADIV*
(符号なし) 命令にマッピングされるようになりました。- 例:
CASE(OMOD, TINT8)
はAIDIVB
に、CASE(OMOD, TUINT8)
はADIVB
にマッピングされます。
- 例:
これらの変更により、Goコンパイラは除算と剰余演算を、x86アーキテクチャの特性を考慮した上で、より正確かつ効率的なアセンブリコードに変換できるようになりました。
コアとなるコードの変更箇所
src/cmd/6g/cgen.c
--- a/src/cmd/6g/cgen.c
+++ b/src/cmd/6g/cgen.c
@@ -112,9 +112,7 @@ cgen(Node *n, Node *res)
goto sbop;
// asymmetric binary
- case OMOD:
case OSUB:
- case ODIV:
case OLSH:
case ORSH:
a = optoas(n->op, nl->type);
@@ -237,6 +235,11 @@ cgen(Node *n, Node *res)
cgen_call(n);
cgen_callret(n, res);
break;
+
+ case OMOD:
+ case ODIV:
+ cgen_div(n->op, nl, nr, res);
+ break;
}
goto ret;
src/cmd/6g/gen.c
--- a/src/cmd/6g/gen.c
+++ b/src/cmd/6g/gen.c
@@ -826,3 +826,56 @@ cgen_as(Node *nl, Node *nr, int op)
}
cgen(nr, nl);
}
+
+void
+cgen_div(int op, Node *nl, Node *nr, Node *res)
+{
+ Node n1, n2, n3;
+ int a;
+
+ if(reg[D_AX] || reg[D_DX]) {
+ fatal("registers occupide");
+ }
+
+ a = optoas(op, nl->type);
+
+ // hold down the DX:AX registers
+ nodreg(&n1, types[TINT64], D_AX);
+ nodreg(&n2, types[TINT64], D_DX);
+ regalloc(&n1, nr->type, &n1);
+ regalloc(&n2, nr->type, &n2);
+
+ if(!issigned[nl->type->etype]) {
+ nodconst(&n3, nl->type, 0);
+ gmove(&n3, &n2);
+ }
+
+ if(nl->ullman >= nr->ullman) {
+ cgen(nl, &n1);
+ if(issigned[nl->type->etype])
+ gins(ACDQ, N, N);
+ if(!nr->addable) {
+ regalloc(&n3, nr->type, res);
+ cgen(nr, &n3);
+ gins(a, &n3, N);
+ regfree(&n3);
+ } else
+ gins(a, nr, N);
+ } else {
+ regalloc(&n3, nr->type, res);
+ cgen(nr, &n3);
+ cgen(nl, &n1);
+ if(issigned[nl->type->etype])
+ gins(ACDQ, N, N);
+ gins(a, &n3, N);
+ regfree(&n3);
+ }
+
+ if(op == ODIV)
+ gmove(&n1, res);
+ else
+ gmove(&n2, res);
+
+ regfree(&n1);
+ regfree(&n2);
+}
src/cmd/6g/gg.h
--- a/src/cmd/6g/gg.h
+++ b/src/cmd/6g/gg.h
@@ -117,6 +117,7 @@ void cgen_call(Node*);
void cgen_callmeth(Node*);
void cgen_callinter(Node*, Node*);
void cgen_callret(Node*, Node*);
+void cgen_div(int, Node*, Node*, Node*);
void genpanic(void);
int needconvert(Type*, Type*);
void genconv(Type*, Type*);
src/cmd/6g/gsubr.c
--- a/src/cmd/6g/gsubr.c
+++ b/src/cmd/6g/gsubr.c
@@ -1397,36 +1397,46 @@ optoas(int op, Type *t)
break;
case CASE(ODIV, TINT8):
+ case CASE(OMOD, TINT8):
a = AIDIVB;
break;
case CASE(ODIV, TUINT8):
+ case CASE(OMOD, TUINT8):
a = ADIVB;
break;
case CASE(ODIV, TINT16):
+ case CASE(OMOD, TINT16):
a = AIDIVW;
break;
case CASE(ODIV, TUINT16):
+ case CASE(OMOD, TUINT16):
a = ADIVW;
break;
case CASE(ODIV, TINT32):
+ case CASE(OMOD, TINT32):
a = AIDIVL;
break;
case CASE(ODIV, TUINT32):
case CASE(ODIV, TPTR32):
+ case CASE(OMOD, TUINT32):
+ case CASE(OMOD, TPTR32):
a = ADIVL;
break;
case CASE(ODIV, TINT64):
+ case CASE(OMOD, TINT64):
a = AIDIVQ;
break;
case CASE(ODIV, TUINT64):
case CASE(ODIV, TPTR64):
+ case CASE(OMOD, TUINT64):
+ case CASE(OMOD, TPTR64):
a = ADIVQ;
break;
コアとなるコードの解説
src/cmd/6g/cgen.c
の変更
cgen
関数は、抽象構文木 (AST) のノードを受け取り、それに対応するアセンブリコードを生成する主要な関数です。この変更では、OMOD
(剰余) と ODIV
(除算) のケースが、以前の一般的な非対称二項演算子群から分離され、独立した case
ブロックに移されました。そして、これらの演算子に対しては、新しく定義された cgen_div
関数が呼び出されるようになりました。これにより、除算と剰余に特化した複雑なレジスタ操作や命令選択のロジックを cgen_div
にカプセル化し、cgen
関数の可読性と保守性を向上させています。
src/cmd/6g/gen.c
に追加された cgen_div
関数
cgen_div
関数は、除算 (ODIV
) と剰余 (OMOD
) 演算子のための専用のコード生成ロジックを実装しています。
- レジスタの排他利用チェック:
if(reg[D_AX] || reg[D_DX]) { fatal("registers occupide"); }
は、x86の除算命令がAX
/DX
(またはその拡張) レジスタペアを暗黙的に使用するため、これらのレジスタが既に他の目的で占有されていないことを確認しています。もし占有されていれば、コンパイラは致命的なエラーを発生させます。 - 命令の選択:
a = optoas(op, nl->type);
は、演算子 (op
) と左オペランドの型 (nl->type
) に基づいて、適切なx86除算/剰余命令(例:AIDIVB
,ADIVL
など)のオペコードを取得します。 DX:AX
レジスタの確保:nodreg
とregalloc
を使って、D_AX
とD_DX
に対応するレジスタノードn1
とn2
を確保します。これらはそれぞれ商と剰余を格納するために使用されます。- 符号なし除算の準備:
if(!issigned[nl->type->etype]) { ... gmove(&n3, &n2); }
のブロックは、被除数が符号なしの場合にDX
レジスタ (n2
) をゼロクリアします。これは、符号なし除算命令がDX
レジスタの上位ビットがゼロであることを期待するためです。 - オペランド評価順序の最適化:
if(nl->ullman >= nr->ullman)
の条件は、Ullman Numberに基づいて左右のオペランドの評価順序を決定します。これにより、レジスタの競合を最小限に抑え、効率的なコードを生成します。 - 符号拡張:
if(issigned[nl->type->etype]) gins(ACDQ, N, N);
は、被除数が符号付きの場合にACDQ
(x86のCDQ
命令に相当) を生成します。CDQ
はEAX
の符号をEDX
に拡張し、EDX:EAX
を正しい符号付き64ビット値として準備します。 - 除算命令の生成:
gins(a, &n3, N);
またはgins(a, nr, N);
は、optoas
で選択された実際の除算/剰余命令を生成します。 - 結果の格納:
if(op == ODIV) gmove(&n1, res);
は、除算の場合、商が格納されているAX
レジスタ (n1
) の内容を結果ノードres
に移動します。else gmove(&n2, res);
は、剰余の場合、剰余が格納されているDX
レジスタ (n2
) の内容を結果ノードres
に移動します。
- レジスタの解放:
regfree(&n1); regfree(&n2);
は、使用した一時レジスタを解放し、他のコード生成で再利用できるようにします。
src/cmd/6g/gg.h
の変更
このファイルは、6g
コンパイラのヘッダファイルであり、関数のプロトタイプ宣言が含まれています。cgen_div
関数のプロトタイプがここに追加されたことで、コンパイラの他の部分からこの新しいコード生成関数を呼び出すことが可能になりました。
src/cmd/6g/gsubr.c
の optoas
関数の変更
optoas
関数は、Go言語の抽象的な演算子とデータ型を、具体的なx86アセンブリ命令のオペコードにマッピングする役割を担っています。このコミットでは、OMOD
(剰余) 演算子に対するマッピングが追加されました。これにより、OMOD
も ODIV
と同様に、オペランドの型(8ビット、16ビット、32ビット、64ビット、ポインタ型)と符号付き/符号なしの区別に基づいて、適切な AIDIV*
(符号付き除算/剰余) または ADIV*
(符号なし除算/剰余) 命令に変換されるようになりました。この変更により、コンパイラはGo言語の剰余演算子を正しくアセンブリ命令に変換できるようになります。
関連リンク
- Go言語の初期開発に関する情報: https://go.dev/doc/history
- x86アセンブリ命令セットリファレンス (Intel/AMDの公式ドキュメントを参照するのが最も正確です)
参考にした情報源リンク
- Go言語のソースコード (GitHub): https://github.com/golang/go
- x86 Assembly/Instructions: https://en.wikibooks.org/wiki/X86_Assembly/Instructions
- Ullman's algorithm for register allocation: https://en.wikipedia.org/wiki/Ullman%27s_algorithm
- Compiler design principles (一般的なコンパイラ設計の教科書)```markdown
[インデックス 122] ファイルの概要
このコミットは、Go言語の初期のコンパイラである 6g
(AMD64アーキテクチャ向け) において、除算 (div
) および剰余 (mod
) 演算子のコード生成ロジックを改善し、より正確かつ効率的にアセンブリコードに変換できるようにするためのものです。具体的には、これらの演算子に対する専用のコード生成関数 cgen_div
を導入し、符号付き/符号なし整数、および異なるデータ型サイズに応じた適切なx86アセンブリ命令(DIV
, IDIV
)を生成するように拡張しています。
コミット
div and mod operators
SVN=121576
GitHub上でのコミットページへのリンク
https://github.com/golang/go/commit/d83b994da62f88d9bee5ab62702cb560e9c3ad48
元コミット内容
commit d83b994da62f88d9bee5ab62702cb560e9c3ad48
Author: Ken Thompson <ken@golang.org>
Date: Fri Jun 6 20:43:29 2008 -0700
div and mod operators
SVN=121576
変更の背景
Go言語の初期開発段階において、コンパイラは様々な演算子に対するコード生成ロジックを段階的に実装していました。除算と剰余演算は、特にx86アーキテクチャにおいて、他の二項演算子(加算、減算など)とは異なる特殊なアセンブリ命令とレジスタの使用パターンを必要とします。具体的には、DIV
(符号なし除算) および IDIV
(符号付き除算) 命令は、被除数を DX:AX
(または EDX:EAX
, RDX:RAX
) レジスタペアに配置し、商を AX
(または EAX
, RAX
) に、剰余を DX
(または EDX
, RDX
) に格納するという独特の動作をします。
このコミット以前は、除算と剰余のコード生成が他の一般的な二項演算子と同じような非対称二項演算子として扱われていた可能性があります。しかし、その特殊性から、専用のコード生成パスとレジスタ管理が必要とされました。この変更は、6g
コンパイラがGo言語の除算および剰余演算を正確かつ効率的に機械語に変換できるようにするために導入されました。また、SVN=121576
という記述は、このコミットがGoプロジェクトがSubversionからGitへ移行する過程で取り込まれたものであり、当時のSubversionリビジョン番号を示しています。
前提知識の解説
Go言語の初期コンパイラ 6g
Go言語の初期には、各アーキテクチャ向けに異なるコンパイラが存在しました。6g
は、AMD64 (x86-64) アーキテクチャをターゲットとするGoコンパイラの名称でした。Goのコンパイラは、gc
(Go compiler) という共通のコードベースから派生し、ターゲットアーキテクチャに応じて 8g
(ARM), 5g
(PowerPC) などと命名されていました。これらのコンパイラは、Go言語のソースコードを直接アセンブリコードに変換する役割を担っていました。
コンパイラのコード生成フェーズ
コンパイラは、ソースコードを機械語に変換する過程で複数のフェーズを経ます。
- 字句解析 (Lexical Analysis): ソースコードをトークンに分割します。
- 構文解析 (Parsing): トークン列から抽象構文木 (AST) を構築します。
- 意味解析 (Semantic Analysis): 型チェックや名前解決などを行い、ASTに意味的な情報を付加します。
- 中間表現生成 (Intermediate Representation Generation): ASTを、より機械語に近い中間表現に変換します。
- コード生成 (Code Generation): 中間表現をターゲットアーキテクチャの機械語(アセンブリコード)に変換します。このコミットは、このコード生成フェーズにおける除算・剰余演算の処理に焦点を当てています。
- 最適化 (Optimization): 生成されたコードの効率を改善します。
x86アセンブリにおける除算・剰余演算
x86アーキテクチャでは、整数除算には DIV
(unsigned division) と IDIV
(signed division) の2つの命令があります。これらの命令は、他の算術命令とは異なり、特定のレジスタを使用するという特徴があります。
- 被除数 (Dividend): 除算を行う前に、被除数は
DX:AX
(16ビット除算の場合)、EDX:EAX
(32ビット除算の場合)、またはRDX:RAX
(64ビット除算の場合) のレジスタペアに格納されます。例えば、32ビットの除算を行う場合、被除数の上位32ビットがEDX
に、下位32ビットがEAX
に格納されます。 - 除数 (Divisor): 除数は、命令のオペランドとして指定されたレジスタまたはメモリ位置に格納されます。
- 結果:
- 商 (Quotient):
AX
(EAX
/RAX
) レジスタに格納されます。 - 剰余 (Remainder):
DX
(EDX
/RDX
) レジスタに格納されます。
- 商 (Quotient):
符号拡張 (Sign Extension)
符号付き除算 (IDIV
) の場合、被除数が負の値であると、DX:AX
レジスタペア全体で正しい符号を表現するために、符号拡張が必要です。これは CDQ
(Convert Doubleword to Quadword) 命令などを用いて行われます。CDQ
は EAX
の符号ビットを EDX
の全ビットにコピーすることで、EDX:EAX
を符号付き64ビット値として正しく表現します。
Ullman Number (ウルマン数)
Ullman Numberは、コンパイラの最適化、特にレジスタ割り当てにおいて使用される概念です。抽象構文木 (AST) の各ノードに割り当てられる数値で、そのノードを評価するために必要なレジスタの最小数を示します。Ullman Numberが低いノードから評価することで、レジスタの使用効率を高め、レジスタスピル(レジスタの内容をメモリに退避させること)を減らすことができます。このコミットのコードでは、nl->ullman >= nr->ullman
のような比較があり、これは左右のオペランドの評価順序を決定する際にUllman Numberを考慮していることを示唆しています。
技術的詳細
このコミットの主要な技術的変更点は、除算と剰余演算のための専用コード生成関数 cgen_div
の導入と、それに伴うコンパイラの各モジュールの連携です。
-
src/cmd/6g/cgen.c
の変更:- 以前は
OMOD
(剰余) とODIV
(除算) がOSUB
(減算) などと同じ「非対称二項演算子」のカテゴリで処理されていました。 - この変更により、
OMOD
とODIV
はこのカテゴリから削除され、代わりにcgen_div(n->op, nl, nr, res);
という専用の関数呼び出しに置き換えられました。これは、除算と剰余が特殊な処理を必要とすることを明確に示しています。
- 以前は
-
src/cmd/6g/gen.c
へのcgen_div
関数の追加:cgen_div(int op, Node *nl, Node *nr, Node *res)
関数が新しく追加されました。この関数が除算と剰余のコード生成の核心を担います。- レジスタ管理:
D_AX
(AX/EAX/RAX) とD_DX
(DX/EDX/RDX) レジスタが除算命令で排他的に使用されるため、関数冒頭でこれらのレジスタが占有されていないかチェックしています (fatal("registers occupide")
)。これは、コンパイラがこれらのレジスタを他の目的で使用していないことを保証するためです。 - レジスタ割り当て:
nodreg
とregalloc
を使用して、D_AX
とD_DX
に対応する一時レジスタノードn1
とn2
を割り当てています。n1
は商、n2
は剰余を格納するために使用されます。 - 符号なし除算の準備: オペランドが符号なし (
!issigned[nl->type->etype]
) の場合、DX
レジスタ (n2
) をゼロクリアしています (nodconst(&n3, nl->type, 0); gmove(&n3, &n2);
)。これは、符号なし除算ではDX
の上位ビットがゼロである必要があるためです。 - オペランド評価順序:
if(nl->ullman >= nr->ullman)
の条件で、左右のオペランド (nl
,nr
) のUllman Numberを比較し、レジスタ使用効率を考慮した評価順序を決定しています。Ullman Numberが大きい方(より多くのレジスタを必要とする可能性のある方)を先に評価することで、レジスタの競合を減らします。- 左オペランド (
nl
) をAX
(n1
) に生成し、符号付きの場合はACDQ
(x86のCDQ
命令に対応) で符号拡張を行います。 - 右オペランド (
nr
) が直接アセンブリ命令のオペランドとして使用できない場合 (!nr->addable
) は、一時レジスタn3
に生成してから除算命令を実行します。
- 左オペランド (
- 除算命令の生成:
gins(a, &n3, N)
またはgins(a, nr, N)
を呼び出して、実際の除算命令を生成します。a
はoptoas
関数によって決定された適切なアセンブリ命令(AIDIVB
,ADIVB
など)です。 - 結果の格納:
op == ODIV
(除算) の場合、AX
レジスタ (n1
) の内容を結果ノードres
に移動します (gmove(&n1, res);
)。- それ以外 (
OMOD
、剰余) の場合、DX
レジスタ (n2
) の内容を結果ノードres
に移動します (gmove(&n2, res);
)。
- レジスタ解放: 最後に
regfree(&n1); regfree(&n2);
で一時レジスタを解放します。
-
src/cmd/6g/gg.h
の変更:cgen_div
関数のプロトタイプvoid cgen_div(int, Node*, Node*, Node*);
が追加されました。これにより、他のコンパイラモジュールからcgen_div
を呼び出すことが可能になります。
-
src/cmd/6g/gsubr.c
のoptoas
関数の変更:optoas
関数は、Goの演算子 (op
) と型 (t
) に基づいて、対応するx86アセンブリ命令のオペコードを返す役割を担っています。- このコミットでは、
OMOD
(剰余) 演算子に対するケースが追加されました。これにより、OMOD
がODIV
と同じように、データ型サイズ(8ビット、16ビット、32ビット、64ビット)と符号付き/符号なしに応じて、適切なAIDIV*
(符号付き) またはADIV*
(符号なし) 命令にマッピングされるようになりました。- 例:
CASE(OMOD, TINT8)
はAIDIVB
に、CASE(OMOD, TUINT8)
はADIVB
にマッピングされます。
- 例:
これらの変更により、Goコンパイラは除算と剰余演算を、x86アーキテクチャの特性を考慮した上で、より正確かつ効率的なアセンブリコードに変換できるようになりました。
コアとなるコードの変更箇所
src/cmd/6g/cgen.c
--- a/src/cmd/6g/cgen.c
+++ b/src/cmd/6g/cgen.c
@@ -112,9 +112,7 @@ cgen(Node *n, Node *res)
goto sbop;
// asymmetric binary
- case OMOD:
case OSUB:
- case ODIV:
case OLSH:
case ORSH:
a = optoas(n->op, nl->type);
@@ -237,6 +235,11 @@ cgen(Node *n, Node *res)
cgen_call(n);
cgen_callret(n, res);
break;
+
+ case OMOD:
+ case ODIV:
+ cgen_div(n->op, nl, nr, res);
+ break;
}
goto ret;
src/cmd/6g/gen.c
--- a/src/cmd/6g/gen.c
+++ b/src/cmd/6g/gen.c
@@ -826,3 +826,56 @@ cgen_as(Node *nl, Node *nr, int op)
}
cgen(nr, nl);
}
+
+void
+cgen_div(int op, Node *nl, Node *nr, Node *res)
+{
+ Node n1, n2, n3;
+ int a;
+
+ if(reg[D_AX] || reg[D_DX]) {
+ fatal("registers occupide");
+ }
+
+ a = optoas(op, nl->type);
+
+ // hold down the DX:AX registers
+ nodreg(&n1, types[TINT64], D_AX);
+ nodreg(&n2, types[TINT64], D_DX);
+ regalloc(&n1, nr->type, &n1);
+ regalloc(&n2, nr->type, &n2);
+
+ if(!issigned[nl->type->etype]) {
+ nodconst(&n3, nl->type, 0);
+ gmove(&n3, &n2);
+ }
+
+ if(nl->ullman >= nr->ullman) {
+ cgen(nl, &n1);
+ if(issigned[nl->type->etype])
+ gins(ACDQ, N, N);
+ if(!nr->addable) {
+ regalloc(&n3, nr->type, res);
+ cgen(nr, &n3);
+ gins(a, &n3, N);
+ regfree(&n3);
+ } else
+ gins(a, nr, N);
+ } else {
+ regalloc(&n3, nr->type, res);
+ cgen(nr, &n3);
+ cgen(nl, &n1);
+ if(issigned[nl->type->etype])
+ gins(ACDQ, N, N);
+ gins(a, &n3, N);
+ regfree(&n3);
+ }
+
+ if(op == ODIV)
+ gmove(&n1, res);
+ else
+ gmove(&n2, res);
+
+ regfree(&n1);
+ regfree(&n2);
+}
src/cmd/6g/gg.h
--- a/src/cmd/6g/gg.h
+++ b/src/cmd/6g/gg.h
@@ -117,6 +117,7 @@ void cgen_call(Node*);
void cgen_callmeth(Node*);
void cgen_callinter(Node*, Node*);
void cgen_callret(Node*, Node*);
+void cgen_div(int, Node*, Node*, Node*);
void genpanic(void);
int needconvert(Type*, Type*);
void genconv(Type*, Type*);
src/cmd/6g/gsubr.c
--- a/src/cmd/6g/gsubr.c
+++ b/src/cmd/6g/gsubr.c
@@ -1397,36 +1397,46 @@ optoas(int op, Type *t)
break;
case CASE(ODIV, TINT8):
+ case CASE(OMOD, TINT8):
a = AIDIVB;
break;
case CASE(ODIV, TUINT8):
+ case CASE(OMOD, TUINT8):
a = ADIVB;
break;
case CASE(ODIV, TINT16):
+ case CASE(OMOD, TINT16):
a = AIDIVW;
break;
case CASE(ODIV, TUINT16):
+ case CASE(OMOD, TUINT16):
a = ADIVW;
break;
case CASE(ODIV, TINT32):
+ case CASE(OMOD, TINT32):
a = AIDIVL;
break;
case CASE(ODIV, TUINT32):
case CASE(ODIV, TPTR32):
+ case CASE(OMOD, TUINT32):
+ case CASE(OMOD, TPTR32):
a = ADIVL;
break;
case CASE(ODIV, TINT64):
+ case CASE(OMOD, TINT64):
a = AIDIVQ;
break;
case CASE(ODIV, TUINT64):
case CASE(ODIV, TPTR64):
+ case CASE(OMOD, TUINT64):
+ case CASE(OMOD, TPTR64):
a = ADIVQ;
break;
コアとなるコードの解説
src/cmd/6g/cgen.c
の変更
cgen
関数は、抽象構文木 (AST) のノードを受け取り、それに対応するアセンブリコードを生成する主要な関数です。この変更では、OMOD
(剰余) と ODIV
(除算) のケースが、以前の一般的な非対称二項演算子群から分離され、独立した case
ブロックに移されました。そして、これらの演算子に対しては、新しく定義された cgen_div
関数が呼び出されるようになりました。これにより、除算と剰余に特化した複雑なレジスタ操作や命令選択のロジックを cgen_div
にカプセル化し、cgen
関数の可読性と保守性を向上させています。
src/cmd/6g/gen.c
に追加された cgen_div
関数
cgen_div
関数は、除算 (ODIV
) と剰余 (OMOD
) 演算子のための専用のコード生成ロジックを実装しています。
- レジスタの排他利用チェック:
if(reg[D_AX] || reg[D_DX]) { fatal("registers occupide"); }
は、x86の除算命令がAX
/DX
(またはその拡張) レジスタペアを暗黙的に使用するため、これらのレジスタが既に他の目的で占有されていないことを確認しています。もし占有されていれば、コンパイラは致命的なエラーを発生させます。 - 命令の選択:
a = optoas(op, nl->type);
は、演算子 (op
) と左オペランドの型 (nl->type
) に基づいて、適切なx86除算/剰余命令(例:AIDIVB
,ADIVL
など)のオペコードを取得します。 DX:AX
レジスタの確保:nodreg
とregalloc
を使って、D_AX
とD_DX
に対応するレジスタノードn1
とn2
を確保します。これらはそれぞれ商と剰余を格納するために使用されます。- 符号なし除算の準備:
if(!issigned[nl->type->etype]) { ... gmove(&n3, &n2); }
のブロックは、被除数が符号なしの場合にDX
レジスタ (n2
) をゼロクリアします。これは、符号なし除算命令がDX
レジスタの上位ビットがゼロであることを期待するためです。 - オペランド評価順序の最適化:
if(nl->ullman >= nr->ullman)
の条件は、Ullman Numberに基づいて左右のオペランドの評価順序を決定します。これにより、レジスタの競合を最小限に抑え、効率的なコードを生成します。 - 符号拡張:
if(issigned[nl->type->etype]) gins(ACDQ, N, N);
は、被除数が符号付きの場合にACDQ
(x86のCDQ
命令に相当) を生成します。CDQ
はEAX
の符号をEDX
に拡張し、EDX:EAX
を正しい符号付き64ビット値として準備します。 - 除算命令の生成:
gins(a, &n3, N);
またはgins(a, nr, N);
は、optoas
で選択された実際の除算/剰余命令を生成します。 - 結果の格納:
if(op == ODIV) gmove(&n1, res);
は、除算の場合、商が格納されているAX
レジスタ (n1
) の内容を結果ノードres
に移動します。else gmove(&n2, res);
は、剰余の場合、剰余が格納されているDX
レジスタ (n2
) の内容を結果ノードres
に移動します。
- レジスタの解放:
regfree(&n1); regfree(&n2);
は、使用した一時レジスタを解放し、他のコード生成で再利用できるようにします。
src/cmd/6g/gg.h
の変更
このファイルは、6g
コンパイラのヘッダファイルであり、関数のプロトタイプ宣言が含まれています。cgen_div
関数のプロトタイプがここに追加されたことで、コンパイラの他の部分からこの新しいコード生成関数を呼び出すことが可能になりました。
src/cmd/6g/gsubr.c
の optoas
関数の変更
optoas
関数は、Go言語の抽象的な演算子とデータ型を、具体的なx86アセンブリ命令のオペコードにマッピングする役割を担っています。このコミットでは、OMOD
(剰余) 演算子に対するマッピングが追加されました。これにより、OMOD
も ODIV
と同様に、オペランドの型(8ビット、16ビット、32ビット、64ビット、ポインタ型)と符号付き/符号なしの区別に基づいて、適切な AIDIV*
(符号付き除算/剰余) または ADIV*
(符号なし除算/剰余) 命令に変換されるようになりました。この変更により、コンパイラはGo言語の剰余演算子を正しくアセンブリ命令に変換できるようになります。
関連リンク
- Go言語の初期開発に関する情報: https://go.dev/doc/history
- x86アセンブリ命令セットリファレンス (Intel/AMDの公式ドキュメントを参照するのが最も正確です)
参考にした情報源リンク
- Go言語のソースコード (GitHub): https://github.com/golang/go
- x86 Assembly/Instructions: https://en.wikibooks.org/wiki/X86_Assembly/Instructions
- Ullman's algorithm for register allocation: https://en.wikipedia.org/wiki/Ullman%27s_algorithm
- Compiler design principles (一般的なコンパイラ設計の教科書)