[インデックス 1034] ファイルの概要
本コミットは、Go言語の初期のコンパイラである6g
における、符号なし整数の除算処理に関する修正です。具体的には、src/cmd/6g/gen.c
ファイル内のdodiv
関数において、符号なし除算の際にdx
レジスタ(除算の被除数の上位ビットを保持するレジスタ)の初期化が適切に行われるように変更されています。
コミット
commit 250ec1665a8d142a4b4f7e634991aeac50bb14f8
Author: Ken Thompson <ken@golang.org>
Date: Mon Nov 3 13:27:16 2008 -0800
unsigned divide by fn()
R=r
OCL=18351
CL=18351
GitHub上でのコミットページへのリンク
https://github.com/golang/go/commit/250ec1665a8d142a4b4f7e634991aeac50bb14f8
元コミット内容
unsigned divide by fn()
このコミットメッセージは非常に簡潔ですが、「関数による符号なし除算」という問題に対処していることを示唆しています。これは、除算の被除数が符号なし整数であり、かつ除数が関数呼び出しの結果である場合に、特定のコンパイラ最適化やコード生成のロジックが正しく機能しない可能性があったことを示しています。
変更の背景
Go言語のコンパイラは、ソースコードを機械語に変換する過程で、様々な最適化やレジスタ割り当てを行います。特に除算のような演算は、CPUのアーキテクチャに依存する特性が強く、符号付き/符号なしの区別が重要になります。
x86アーキテクチャでは、DIV
命令(符号なし除算)やIDIV
命令(符号付き除算)が提供されています。これらの命令は、被除数をAX
(またはEAX
/RAX
)とDX
(またはEDX
/RDX
)レジスタの組み合わせで表現します。具体的には、DX:AX
(またはEDX:EAX
/RDX:RAX
)が被除数となり、AX
(またはEAX
/RAX
)が被除数の下位ビット、DX
(またはEDX
/RDX
)が上位ビットを保持します。
符号なし除算の場合、被除数が32ビット(または64ビット)であれば、DX
レジスタは通常0に初期化されている必要があります。これは、被除数が単一のレジスタに収まる場合でも、DIV
命令がDX:AX
を被除数として扱うためです。もしDX
が適切に0クリアされていないと、意図しない大きな値が被除数として扱われ、誤った除算結果やオーバーフローを引き起こす可能性があります。
このコミットは、dodiv
関数(Goコンパイラが除算操作を処理する部分)において、符号なし除算の際にdx
レジスタの初期化が不足していた、あるいは誤ったタイミングで行われていた問題を修正することを目的としています。特に、除数が関数呼び出しの結果である場合など、コンパイラが被除数の値を事前に完全に把握できない状況で、dx
の初期化が漏れるケースがあったと考えられます。
前提知識の解説
Go言語のコンパイラ 6g
6g
は、Go言語の初期のコンパイラの一つで、主にx86-64アーキテクチャ(AMD64)をターゲットとしていました。Go言語のコンパイラは、フロントエンド(構文解析、型チェックなど)とバックエンド(コード生成、最適化など)に分かれています。src/cmd/6g/gen.c
は、このバックエンドの一部であり、Goの抽象構文木(AST)をターゲットアーキテクチャの機械語命令に変換するコード生成ロジックを含んでいます。
Node
構造体
Goコンパイラ内部では、プログラムの各要素(変数、定数、演算子、関数呼び出しなど)がNode
構造体として表現されます。Node
は、その要素の型、値、レジスタ割り当て情報、Ullman数(式の複雑度を示す指標)など、コンパイルに必要な様々な情報を含んでいます。
レジスタ割り当てとコード生成
コンパイラは、効率的なコードを生成するために、CPUのレジスタを最大限に活用します。regalloc
はレジスタを割り当てる関数、regfree
はレジスタを解放する関数です。gmove
は、あるNode
から別のNode
へ値を移動させる(多くの場合、レジスタ間またはレジスタとメモリ間の移動に対応する機械語命令を生成する)関数です。gins
は、指定されたオペレーション(optoas
で変換されたアセンブリ命令)に対応する機械語命令を生成する関数です。
符号付き整数と符号なし整数
コンピュータにおける整数は、その表現方法によって「符号付き(signed)」と「符号なし(unsigned)」に分けられます。
- 符号付き整数: 最上位ビットを符号ビットとして使用し、正の値と負の値を表現します(例:
int
,long
)。 - 符号なし整数: 全てのビットを値の表現に使用し、非負の値のみを表現します(例:
uint
,ulong
)。
除算演算において、符号付きと符号なしでは結果の解釈や、CPUが使用する命令が異なります。特に、符号なし除算では、被除数が負になることはないため、DX
レジスタは通常0に初期化される必要があります。
dodiv
関数
dodiv
関数は、Goコンパイラが除算(ODIV
)および剰余(OMOD
)演算を処理するための内部関数です。この関数は、被除数(nl
)、除数(nr
)、結果を格納するres
、そしてax
とdx
レジスタに対応するNode
を受け取ります。この関数内で、実際の除算命令が生成されます。
技術的詳細
このコミットの核心は、dodiv
関数における符号なし除算のdx
レジスタの初期化ロジックの変更です。
変更前のコードでは、if(!issigned[t->etype]) { nodconst(&n3, t, 0); gmove(&n3, dx); }
というブロックが、regalloc
の呼び出しよりも前に存在していました。これは、被除数の型が符号なしの場合に、dx
レジスタを0で初期化しようとするものです。しかし、この位置では、nl
(被除数)やnr
(除数)のコード生成がまだ行われていないため、dx
レジスタが他の目的で使用されたり、その値が上書きされたりする可能性がありました。
変更後のコードでは、dx
レジスタの0初期化ロジックが、cgen(nl, ax)
(被除数のコード生成)の直後、かつgins(optoas(OFOR, t), N, N)
(符号拡張命令の生成)の直前に移動されています。
具体的には、以下の2つのパスでdx
の初期化が行われるようになりました。
-
nl->ullman >= nr->ullman
の場合(被除数の複雑度が除数以上の場合):cgen(nl, ax);
で被除数をax
レジスタにロードします。if(!issigned[t->etype]) { nodconst(&n4, t, 0); gmove(&n4, dx); }
で、被除数が符号なしの場合にdx
を0クリアします。- その後、符号付きの場合に
OFOR
命令(符号拡張)を生成し、除数のコード生成と除算命令の生成が続きます。
-
nl->ullman < nr->ullman
の場合(除数の複雑度が被除数より高い場合):cgen(nr, &n3);
で除数をn3
にロードします。cgen(nl, ax);
で被除数をax
レジスタにロードします。if(!issigned[t->etype]) { nodconst(&n4, t, 0); gmove(&n4, dx); }
で、被除数が符号なしの場合にdx
を0クリアします。- その後、符号付きの場合に
OFOR
命令(符号拡張)を生成し、除算命令の生成が続きます。
この変更により、dx
レジスタの0初期化が、被除数がax
レジスタにロードされた直後に行われるようになり、その後の除算命令が正しいDX:AX
のペアで実行されることが保証されます。特に、除数が関数呼び出しの結果である場合など、コンパイラが被除数の値を事前に完全に把握できない状況でも、dx
の初期化が適切なタイミングで行われるようになります。
また、Node n3;
が Node n3, n4;
に変更され、n4
という新しいNode
が導入されています。これは、dx
レジスタを0で初期化するために使用される一時的なNode
としてn4
が使われるようになったためです。
コアとなるコードの変更箇所
src/cmd/6g/gen.c
ファイルの dodiv
関数内。
--- a/src/cmd/6g/gen.c
+++ b/src/cmd/6g/gen.c
@@ -907,7 +907,7 @@ void
dodiv(int op, Node *nl, Node *nr, Node *res, Node *ax, Node *dx)
{
int a;
- Node n3;
+ Node n3, n4;
Type *t;
t = nl->type;
@@ -919,25 +919,25 @@ dodiv(int op, Node *nl, Node *nr, Node *res, Node *ax, Node *dx)
}
a = optoas(op, t);
- if(!issigned[t->etype]) {
- nodconst(&n3, t, 0);
- gmove(&n3, dx);
- }
-
regalloc(&n3, nr->type, N);
if(nl->ullman >= nr->ullman) {
cgen(nl, ax);
- if(issigned[t->etype])
+ if(!issigned[t->etype]) {
+ nodconst(&n4, t, 0);
+ gmove(&n4, dx);
+ } else
gins(optoas(OFOR, t), N, N);
cgen(nr, &n3);
- gins(a, &n3, N);
} else {
cgen(nr, &n3);
cgen(nl, ax);
- if(issigned[t->etype])
+ if(!issigned[t->etype]) {
+ nodconst(&n4, t, 0);
+ gmove(&n4, dx);
+ } else
gins(optoas(OFOR, t), N, N);
- gins(a, &n3, N);
}
+ gins(a, &n3, N);
regfree(&n3);
if(op == ODIV)
コアとなるコードの解説
変更点1: Node n3;
から Node n3, n4;
へ
- Node n3;
+ Node n3, n4;
n4
という新しいNode
変数が追加されました。これは、dx
レジスタを0で初期化するために使用される一時的なNode
として導入されました。以前はn3
がこの目的にも使われていましたが、n3
は除数を保持するためにも使われるため、役割を分離することでコードの明確性と正確性を高めています。
変更点2: dx
レジスタの0初期化ロジックの移動と修正
- if(!issigned[t->etype]) {
- nodconst(&n3, t, 0);
- gmove(&n3, dx);
- }
このブロックは削除されました。以前はdodiv
関数の冒頭近くでdx
を0クリアしていましたが、このタイミングでは被除数の値がax
にロードされる前であり、dx
が他の目的で使われたり、その値が上書きされたりする可能性がありました。
if(nl->ullman >= nr->ullman) {
cgen(nl, ax);
- if(issigned[t->etype])
+ if(!issigned[t->etype]) {
+ nodconst(&n4, t, 0);
+ gmove(&n4, dx);
+ } else
gins(optoas(OFOR, t), N, N);
cgen(nr, &n3);
- gins(a, &n3, N);
} else {
cgen(nr, &n3);
cgen(nl, ax);
- if(issigned[t->etype])
+ if(!issigned[t->etype]) {
+ nodconst(&n4, t, 0);
+ gmove(&n4, dx);
+ } else
gins(optoas(OFOR, t), N, N);
- gins(a, &n3, N);
}
+ gins(a, &n3, N);
dx
レジスタの0初期化ロジックが、被除数(nl
)がax
レジスタにロードされた直後に移動されました。
cgen(nl, ax);
:被除数の値をax
レジスタに生成(ロード)します。if(!issigned[t->etype]) { nodconst(&n4, t, 0); gmove(&n4, dx); }
:!issigned[t->etype]
:被除数の型が符号なしであるかをチェックします。nodconst(&n4, t, 0);
:型t
の定数0を表すNode
をn4
に作成します。gmove(&n4, dx);
:n4
(定数0)の値をdx
レジスタに移動させます。これにより、符号なし除算の前にdx
が確実に0クリアされます。
else gins(optoas(OFOR, t), N, N);
:被除数が符号付きの場合、OFOR
命令(符号拡張命令)を生成します。これは、符号付き除算の前にax
レジスタの符号をdx
レジスタに拡張するために必要です。
この変更により、dx
レジスタの初期化が、除算命令が実行される直前の適切なタイミングで行われるようになり、符号なし除算における正確性が保証されます。
変更点3: gins(a, &n3, N);
の移動
- gins(a, &n3, N);
...
- gins(a, &n3, N);
...
+ gins(a, &n3, N);
除算命令を生成するgins(a, &n3, N);
の呼び出しが、if/else
ブロックの外に移動され、一度だけ呼び出されるようになりました。これにより、コードの重複が解消され、より簡潔になっています。除算命令は、被除数と除数のコード生成が完了し、dx
レジスタの初期化(必要であれば)も済んだ後に行われるべきであるため、この位置が適切です。
関連リンク
- Go言語のGitHubリポジトリ: https://github.com/golang/go
- Go言語の初期のコンパイラに関する情報(Goの歴史など): https://go.dev/doc/history
参考にした情報源リンク
- x86アセンブリ言語の除算命令(DIV, IDIV)に関する情報:
- コンパイラのコード生成とレジスタ割り当てに関する一般的な情報:
- コンパイラ設計に関する書籍やオンラインリソース(例: Dragon Book)
- Go言語のコンパイラ内部構造に関する情報(より現代のコンパイラに関するものが多いですが、基本的な概念は共通しています):
- https://go.dev/blog/go1.5compiler (Go 1.5以降のコンパイラに関する記事ですが、コンパイラの役割を理解するのに役立ちます)
- https://go.dev/src/cmd/compile/internal/ (Goコンパイラのソースコード)私は、ご要望いただいたコミット解説を生成しました。上記をご確認ください。