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

このコミットは、Goコンパイラのバックエンドにおける整数除算のコード生成を最適化するものです。具体的には、src/cmd/6g/ggen.c と src/cmd/8g/ggen.c の2つのファイルが変更されています。これらはそれぞれ、Go言語の64ビットアーキテクチャ（amd64）および32ビットアーキテクチャ（x86）向けのコンパイラにおけるコード生成を担当する部分です。変更の目的は、特定の整数除算の特殊ケース、特に最小負の整数を-1で割る場合の処理を簡素化することにあります。

コミット

• コミットハッシュ: a617d06252e9a529e7c2df43ba725a507a6df677
• Author: Rémy Oudompheng oudomphe@phare.normalesup.org
• Date: Wed Dec 12 08:35:08 2012 +0100

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

https://github.com/golang/go/commit/a617d06252e9a529e7c2df43ba725a507a6df677

元コミット内容

cmd/6g, cmd/8g: simplify integer division code.

Change suggested by iant. The compiler generates
special code for a/b when a is -0x80...0 and b = -1.
A single instruction can cover the case where b is -1,
so only one comparison is needed.

Fixes #3551.

R=golang-dev, rsc
CC=golang-dev
https://golang.org/cl/6922049

変更の背景

この変更の背景には、Goコンパイラが整数除算を処理する際の特定の「エッジケース」の最適化があります。特に、2の補数表現における最小の負の整数（例えば、32ビット整数では -2,147,483,648、64ビット整数では -9,223,372,036,854,775,808）を -1 で除算する場合の挙動が問題となります。

数学的には、この除算の結果は対応する正の最大値になるはずですが、2の補数表現では、最小の負の整数に対応する正の整数を表現できない場合があります（例えば、32ビット整数では 2,147,483,648 は int32 の範囲外です）。このような場合、多くのプロセッサアーキテクチャでは、この除算がオーバーフロー例外を引き起こしたり、未定義の動作になったりする可能性があります。

Go言語では、整数演算のオーバーフローはラップアラウンド（modulo arithmetic）として定義されています。したがって、MIN_INT / -1 の結果は MIN_INT 自身になります。コンパイラは、このような特殊なケースを正しく、かつ効率的に処理するための特別なコードを生成する必要があります。

以前のコンパイラは、この MIN_INT / -1 のケースを処理するために、複数の比較と条件分岐を含む、やや複雑なコードを生成していました。このコミットは、iant 氏からの提案に基づき、-1 で除算されるケースを単一の命令でカバーできるようにすることで、このコードを簡素化し、より効率的なコード生成を目指しています。これにより、必要な比較の回数が減り、生成されるアセンブリコードがよりコンパクトになります。

コミットメッセージにある Fixes #3551 については、Goの公式Issueトラッカーで 3551 を検索しても、この整数除算の最適化に直接関連する公開されたIssueは見つかりませんでした。検索結果はMattermostのセキュリティ脆弱性に関するものでした。これは、内部的なバグトラッキングシステムでのIDであるか、あるいは非常に古い、現在は公開されていないIssueである可能性があります。

前提知識の解説

1. 2の補数表現 (Two's Complement)

現代のコンピュータシステムで符号付き整数を表現する最も一般的な方法です。

• 正の数: 最上位ビット（MSB）が0で、残りのビットが数値の絶対値を表します。
• 負の数: 数値の絶対値のビットを反転（1の補数）し、それに1を加えることで得られます。最上位ビットは常に1になります。 この表現の重要な特性は、0 の表現が一意であることと、加算・減算が符号の有無にかかわらず同じハードウェアロジックで実行できることです。 しかし、2の補数表現では、表現できる負の数の範囲が正の数の範囲よりも1つ大きくなります。例えば、8ビットの符号付き整数では、-128 から +127 までを表現できます。ここで、-128 は MIN_INT に相当し、これに対応する正の +128 は表現できません。

2. 整数除算の挙動 (Integer Division Behavior)

Go言語における整数除算（/ 演算子）は、結果が常にゼロ方向へ切り捨てられます（truncation towards zero）。

• 5 / 2 は 2
• -5 / 2 は -2 これは、多くのプログラミング言語で採用されている一般的な挙動です。

3. MIN_INT / -1 の特殊性

前述の2の補数表現の特性により、MIN_INT を -1 で除算すると、数学的には |MIN_INT| となるはずです。しかし、|MIN_INT| は通常、そのデータ型で表現できる最大の正の数 MAX_INT を超えてしまいます。 例えば、32ビット符号付き整数で考えると、MIN_INT は -2,147,483,648 です。これを -1 で割ると 2,147,483,648 となりますが、これは32ビット符号付き整数の MAX_INT である 2,147,483,647 を1だけ超えています。 Go言語では、このような整数オーバーフローが発生した場合、結果はラップアラウンドします。したがって、MIN_INT / -1 の結果は MIN_INT そのものになります。これは、プロセッサによってはこの操作が例外（例えば、Intel x86/x64のIDIV命令における#DE (Divide Error)例外）を引き起こす可能性があるため、コンパイラはこれを特別に処理する必要があります。

4. cmd/6g と cmd/8g

これらはGo言語の初期のコンパイラツールチェーンの一部です。

• cmd/6g: gc コンパイラのamd64（64ビット）アーキテクチャ向けバックエンド。
• cmd/8g: gc コンパイラのx86（32ビット）アーキテクチャ向けバックエンド。 これらのファイルは、Goのソースコードをアセンブリコードに変換する過程で、特定の操作（この場合は整数除算）に対する低レベルの命令を生成する役割を担っています。

技術的詳細

Goコンパイラは、dodiv 関数内で整数除算（ODIV）と剰余（OMOD）のコード生成を処理します。この関数は、除算のオペランドが符号付きであるかどうか、および除数が定数であるかどうかなど、様々なケースを考慮します。

特に問題となるのは、除数が -1 である場合です。

• a / -1 は -a になります。
• a % -1 は常に 0 になります。

そして、最も重要なのが MIN_INT / -1 のケースです。このケースでは、結果がオーバーフローするため、Goの仕様に従って MIN_INT が返されるようにする必要があります。

変更前のコードでは、この MIN_INT / -1 のケースを検出するために、除数が -1 であることのチェックに加えて、被除数が MIN_INT であることのチェックも行っていました。具体的には、以下の2つの条件をチェックしていました。

1. 除数が -1 であるか (n3 == -1)
2. 被除数（ax レジスタに格納されている）が MIN_INT であるか (ax == MIN_INT)

これらの条件が両方とも真の場合、特別な処理（MIN_INT を結果として設定し、ジャンプする）を行っていました。この処理は、p1 と p2 という2つの分岐命令と、それに続く p3 という無条件ジャンプ命令によって制御されていました。

変更後のコードでは、このロジックが大幅に簡素化されています。 除数が -1 であることだけをチェックし、その条件が真であれば、以下の処理を行います。

• 除算 (ODIV) の場合: 被除数 a の符号を反転する命令（OMINUS）を生成し、その結果を最終的な結果レジスタに移動します。これは a / -1 = -a という数学的関係を利用したものです。MIN_INT / -1 の場合も、Goのオーバーフロー規則により -MIN_INT が MIN_INT にラップアラウンドするため、この単一の操作で正しい結果が得られます。
• 剰余 (OMOD) の場合: 結果を 0 に設定する命令を生成します。これは a % -1 = 0 という数学的関係を利用したものです。

この変更により、MIN_INT のチェックが不要になり、p2 という分岐命令が削除されました。結果として、コードパスが短縮され、コンパイラが生成するアセンブリコードがより効率的になります。これは、コンパイラの最適化の一環として、特定のパターンをより少ない命令で表現できるようにする典型的な例です。

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

src/cmd/6g/ggen.c

--- a/src/cmd/6g/ggen.c
+++ b/src/cmd/6g/ggen.c
@@ -454,10 +454,10 @@ void
 dodiv(int op, Node *nl, Node *nr, Node *res)
 {
 	int a, check;
-	Node n3, n4, n5;
+	Node n3, n4;
 	Type *t, *t0;
 	Node ax, dx, ax1, n31, oldax, olddx;
-	Prog *p1, *p2, *p3;
+	Prog *p1, *p2;
 
 	// Have to be careful about handling
 	// most negative int divided by -1 correctly.
@@ -508,30 +508,22 @@ dodiv(int op, Node *nl, Node *nr, Node *res)
 		gmove(&n31, &n3);
 	}
 
-	p3 = P;
+	p2 = P;
 	if(check) {
 		nodconst(&n4, t, -1);
 		gins(optoas(OCMP, t), &n3, &n4);
 		p1 = gbranch(optoas(ONE, t), T, +1);
-		nodconst(&n4, t, -1LL<<(t->width*8-1));
-		if(t->width == 8) {
-			n5 = n4;
-			regalloc(&n4, t, N);
-			gins(AMOVQ, &n5, &n4);
-		}
-		gins(optoas(OCMP, t), &ax, &n4);
-		p2 = gbranch(optoas(ONE, t), T, +1);
-		if(op == ODIV)
-			gmove(&n4, res);
-		if(op == OMOD) {
+		if(op == ODIV) {
+			// a / (-1) is -a.
+			gins(optoas(OMINUS, t), N, &ax);
+			gmove(&ax, res);
+		} else {
+			// a % (-1) is 0.
 			nodconst(&n4, t, 0);
 			gmove(&n4, res);
 		}
-		p3 = gbranch(AJMP, T, 0);
+		p2 = gbranch(AJMP, T, 0);
 		patch(p1, pc);
-		patch(p2, pc);
 	}
 	savex(D_DX, &dx, &olddx, res, t);
 	if(!issigned[t->etype]) {
@@ -547,7 +539,7 @@ dodiv(int op, Node *nl, Node *nr, Node *res)
 		gmove(&dx, res);
 	restx(&dx, &olddx);
 	if(check)
-		patch(p3, pc);
+		patch(p2, pc);
 	restx(&ax, &oldax);
 }

src/cmd/8g/ggen.c

--- a/src/cmd/8g/ggen.c
+++ b/src/cmd/8g/ggen.c
@@ -495,7 +495,7 @@ dodiv(int op, Node *nl, Node *nr, Node *res, Node *ax, Node *dx)\n \tint check;\n \tNode n1, t1, t2, t3, t4, n4, nz;\n \tType *t, *t0;\n-\tProg *p1, *p2, *p3;\n+\tProg *p1, *p2;\n \n \t// Have to be careful about handling\n \t// most negative int divided by -1 correctly.\n@@ -544,23 +544,22 @@ dodiv(int op, Node *nl, Node *nr, Node *res, Node *ax, Node *dx)\n \t\tregalloc(&n1, t, N);\n \tgmove(&t2, &n1);\n \tgmove(&t1, ax);\n-\tp3 = P;\n+\tp2 = P;\n \tif(check) {\n \t\tnodconst(&n4, t, -1);\n \t\tgins(optoas(OCMP, t), &n1, &n4);\n \t\tp1 = gbranch(optoas(ONE, t), T, +1);\n-\t\tnodconst(&n4, t, -1LL<<(t->width*8-1));\n-\t\tgins(optoas(OCMP, t), ax, &n4);\n-\t\tp2 = gbranch(optoas(ONE, t), T, +1);\n-\t\tif(op == ODIV)\n-\t\t\tgmove(&n4, res);\n-\t\tif(op == OMOD) {\n+\t\tif(op == ODIV) {\n+\t\t\t// a / (-1) is -a.\n+\t\t\tgins(optoas(OMINUS, t), N, ax);\n+\t\t\tgmove(ax, res);\n+\t\t} else {\n+\t\t\t// a % (-1) is 0.\n \t\t\tnodconst(&n4, t, 0);\n \t\t\tgmove(&n4, res);\n \t\t}\n-\t\tp3 = gbranch(AJMP, T, 0);\n+\t\tp2 = gbranch(AJMP, T, 0);\n \t\tpatch(p1, pc);\n-\t\tpatch(p2, pc);\n \t}\n \tif(!issigned[t->etype]) {\n \t\tnodconst(&nz, t, 0);\n@@ -575,7 +574,7 @@ dodiv(int op, Node *nl, Node *nr, Node *res, Node *ax, Node *dx)\n \telse\n \t\tgmove(dx, res);\n \tif(check)\n-\t\tpatch(p3, pc);\n+\t\tpatch(p2, pc);\n }\n \n static void

コアとなるコードの解説

両ファイルにおける変更はほぼ同じロジックを反映しています。

1. 不要な変数の削除:

   • src/cmd/6g/ggen.c から Node n5; が削除されました。これは、以前の MIN_INT チェックに関連する一時的なノードでした。
   • 両ファイルから Prog *p3; が削除され、代わりに Prog *p2; がその役割を引き継いでいます。これは、分岐ロジックの簡素化に伴うものです。

2. MIN_INT チェックの削除とロジックの簡素化:

   • 変更前は、除数が -1 であることをチェックする p1 の分岐に加えて、被除数が MIN_INT であることをチェックする p2 の分岐がありました。
   • 変更後、p2 の分岐（gins(optoas(OCMP, t), &ax, &n4); p2 = gbranch(optoas(ONE, t), T, +1); の部分）が完全に削除されました。
   • 代わりに、除数が -1 であることが確認された場合（p1 の分岐が成功した場合）に、以下の簡素化されたロジックが適用されます。
     • 除算 (ODIV) の場合: gins(optoas(OMINUS, t), N, &ax); gmove(&ax, res); これは、被除数 ax の符号を反転する命令（OMINUS）を生成し、その結果を最終的な結果レジスタ res に移動します。Goの整数オーバーフローの挙動により、MIN_INT の符号を反転すると MIN_INT にラップアラウンドするため、この単一の操作で MIN_INT / -1 のケースも正しく処理されます。
     • 剰余 (OMOD) の場合: nodconst(&n4, t, 0); gmove(&n4, res); これは、結果を定数 0 に設定します。任意の整数を -1 で割った剰余は常に 0 であるため、これも正しい処理です。

3. 分岐パッチの変更:

   • 以前は patch(p1, pc); patch(p2, pc); と2つの分岐をパッチしていましたが、p2 の分岐が削除されたため、patch(p2, pc); の行が削除されました。
   • 最終的なジャンプ先をパッチする行も patch(p3, pc); から patch(p2, pc); に変更されています。これは、p3 が削除され、p2 がその役割を引き継いだためです。

この変更により、コンパイラは MIN_INT / -1 の特殊ケースを、より少ない命令とより単純なロジックで処理できるようになり、生成されるバイナリの効率が向上します。

関連リンク

• GitHubコミットページ: https://github.com/golang/go/commit/a617d06252e9a529e7c2df43ba725a507a6df677
• Go CL (Code Review): https://golang.org/cl/6922049 (現在はGitHubのコミットページにリダイレクトされます)
• Issue #3551: コミットメッセージに Fixes #3551 とありますが、Goの公式Issueトラッカーでこの番号のIssueを検索しても、この整数除算の最適化に直接関連するものは見つかりませんでした。検索結果はMattermostのセキュリティ脆弱性に関するものであり、このコミットとは無関係です。これは、内部的なバグトラッキングシステムでのIDであるか、あるいは非常に古い、現在は公開されていないIssueである可能性があります。

参考にした情報源リンク

• Go言語における整数除算の挙動:
  • Go by Example: Integer Division
  • Go: Integer Division and Modulo
• 2の補数表現と MIN_INT / -1 のオーバーフロー:
  • Integer Overflow in Go
• Go言語のIssueトラッカー検索結果:
  • GO-2025-3551 (CVE-2025-25068) - pkg.go.dev
  • CVE-2025-25068 - osv.dev
• Goコンパイラに関する一般的な情報:
  • The Go Programming Language Specification - Arithmetic operators
  • Go compiler source code (GitHub)