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

このコミットは、Goコンパイラの最適化フェーズにおけるバグ修正を目的としています。具体的には、STOstring（おそらく文字列ストア操作に関連する内部表現）に関する最適化の不具合に対処しています。変更は主に、Goコンパイラのバックエンドにおけるピーフホール最適化器のコードに集中しており、特定のメモリ操作命令（ASTOSB, ASTOSL, ASTOSQ, AMOVSB, AMOVSL, AMOVSQ）のレジスタ使用状況の追跡と最適化のロジックが修正されています。

コミット

commit 4f49b88dda80a80ec1272447e3a2ca219b6c0436
Author: Ken Thompson <ken@golang.org>
Date:   Thu Jan 29 15:13:36 2009 -0800

    optimizer bug w STOstring
    
    R=r
    OCL=23820
    CL=23820

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

https://github.com/golang/go/commit/4f49b88dda80a80ec1272447e3a2ca219b6c0436

元コミット内容

    optimizer bug w STOstring
    
    R=r
    OCL=23820
    CL=23820

変更の背景

このコミットは、Goコンパイラの最適化器に存在するバグを修正するために行われました。コミットメッセージにある「optimizer bug w STOstring」は、「STOstring（ストア文字列）に関連する最適化器のバグ」を意味しています。Goコンパイラは、ソースコードを機械語に変換する過程で様々な最適化を適用し、生成されるコードの効率を高めます。しかし、最適化のロジックに不備があると、誤ったコードが生成されたり、予期せぬ動作を引き起こしたりする可能性があります。

この特定のバグは、文字列のストア操作（メモリへの書き込み）が関わる場合に、最適化器がレジスタの使用状況を正しく追跡できていなかったことに起因すると推測されます。ピーフホール最適化器は、生成されたアセンブリコードの小さなシーケンスをより効率的なシーケンスに置き換えることで最適化を行います。この過程で、レジスタの内容が変更される可能性がある命令（特にメモリ操作命令）が正しく扱われないと、後続の命令が古いレジスタ値に依存してしまい、誤った結果を生むことがあります。

Ken Thompson氏によるこの修正は、Go言語がまだ初期段階にあった2009年に行われたものであり、コンパイラの安定性と正確性を確保するための重要なステップでした。

前提知識の解説

Goコンパイラと最適化

Goコンパイラは、Go言語のソースコードをターゲットアーキテクチャ（例: x86-64, ARM）の機械語に変換するツールチェーンの一部です。コンパイルプロセスには、字句解析、構文解析、意味解析、中間コード生成、最適化、コード生成といった複数のフェーズがあります。

最適化フェーズ: 生成される機械語コードのサイズを削減したり、実行速度を向上させたりするために、様々な変換を適用します。これには、デッドコード削除、定数畳み込み、インライン化、レジスタ割り当て、そしてピーフホール最適化などが含まれます。

ピーフホール最適化 (Peephole Optimization)

ピーフホール最適化は、コンパイラのコード生成フェーズの後に適用される最適化手法の一つです。生成されたアセンブリコードを「ピーフホール」（小さな窓）を通して覗き込むように、数命令の短いシーケンスを検査し、より効率的な同等のシーケンスに置き換えます。

例:

MOV AX, 0
ADD AX, BX を
MOV AX, BX に置き換えるなど。

この最適化は、局所的な改善に焦点を当てますが、全体的なコード品質に大きな影響を与えることがあります。ピーフホール最適化器は、レジスタの使用状況（どのレジスタがどの値を保持しているか、いつその値が「死ぬ」（もう使われない）か）を正確に追跡する必要があります。

レジスタとメモリ操作命令

CPUには、データを一時的に保持するための高速な記憶領域であるレジスタがあります。プログラムの実行中、データはレジスタとメモリの間で頻繁にやり取りされます。

メモリ操作命令: メモリからレジスタへデータを読み込む（ロード）命令や、レジスタからメモリへデータを書き込む（ストア）命令などがあります。
- MOV (Move): データを移動させる汎用的な命令。
- STO (Store): メモリにデータを書き込む操作。
- MOV S (Move String): 文字列（バイト列）を移動させる命令。

Goコンパイラ内部のアセンブリ命令

Goコンパイラは、各ターゲットアーキテクチャ向けに独自のアセンブリ命令セット（Plan 9アセンブリに似た構文）を使用します。このコミットで登場する命令は、その内部アセンブリ命令です。

AMOVSB, AMOVSL, AMOVSQ: それぞれバイト (Byte)、ロング (Long, 4バイト)、クアッド (Quad, 8バイト) サイズのデータをメモリ間で移動させる命令（Move Stringのバリエーション）。これらは通常、文字列やバイト列のコピーに使用されます。
ASTOSB, ASTOSL, ASTOSQ: それぞれバイト、ロング、クアッドサイズのデータをメモリにストアする命令（Store Stringのバリエーション）。これらは通常、特定の値をメモリ領域に書き込む（例: ゼロクリア、特定のバイトパターンで埋める）ために使用されます。
AREP, AREPN: 繰り返しプレフィックスに関連する命令。REPプレフィックスは、文字列操作命令（MOVS, STOSなど）と組み合わせて使用され、CXレジスタで指定された回数だけ操作を繰り返します。

`subprop` と `copyu` 関数

Goコンパイラのピーフホール最適化器のコード（peep.cファイル）には、subpropとcopyuという関数が登場します。

subprop (substitute propagation): サブスティテューション伝播。レジスタに格納された値が、そのレジスタが変更されるまで有効であることを追跡し、そのレジスタを使用する後続の命令を、レジスタの代わりにその値で直接置き換えることで最適化を図ります。これにより、冗長なロードやストアを削減できます。
copyu (copy propagation utility): コピー伝播ユーティリティ。あるレジスタの内容が別のレジスタにコピーされた場合、元のレジスタが変更されるまで、コピー先のレジスタを使用する命令を元のレジスタに置き換えることで最適化を図ります。

これらの関数は、レジスタのライブネス（値が有効である期間）と、命令がどのレジスタを読み書きするかを正確に把握する必要があります。

技術的詳細

このコミットの技術的詳細は、Goコンパイラのピーフホール最適化器が、特定のメモリ操作命令（ASTOSB, ASTOSL, ASTOSQ, AMOVSB, AMOVSL, AMOVSQ）がレジスタに与える影響を正しく認識していなかったという点にあります。

peep.cファイルは、Goコンパイラの各アーキテクチャ（6cはamd64、6gはamd64のGoコンパイラ、8cは386）向けのピーフホール最適化器のロジックを含んでいます。

変更は主に以下の2つの関数で行われています。

subprop(Reg *r0):
- この関数は、レジスタのサブスティテューション伝播を行います。つまり、あるレジスタが特定の値を保持している場合、そのレジスタが上書きされるまで、そのレジスタを使用する命令を最適化しようとします。
- 変更前は、AMOVSLとAMOVSQ命令がレジスタの内容を変更しない（または、最適化器がその影響を無視できる）と見なされていました。
- 変更後、ASTOSB, ASTOSL, ASTOSQ, AMOVSB, AMOVSL, AMOVSQ命令が、レジスタの内容を破壊する可能性がある命令として追加されました。これらの命令が実行されると、関連するレジスタ（特にDI, SI, AX, CXなど、文字列操作やストア操作で暗黙的に使用されるレジスタ）の内容が変更されるため、subpropはそれらのレジスタに関する伝播を停止する必要があります。return 0;は、これらの命令がレジスタの値を破壊するため、それ以上の伝播が不可能であることを示しています。
copyu(Prog *p, Adr *v, Adr *s):
- この関数は、コピー伝播のユーティリティ関数であり、ある命令が特定のレジスタ（v）の内容を読み取るか、または書き込むかを判断します。戻り値は、レジスタが読み取られるか（1）、書き込まれるか（2）、または両方か（3）を示します。
- 変更前は、AMOVSLとAMOVSQがD_CX, D_DI, D_SIレジスタを読み取る（return 2;は書き込みを示唆しているが、文脈から読み取りと判断されることが多い）と見なされていました。
- 変更後、より詳細なレジスタの依存関係が考慮されています。
  - AMOVSB, AMOVSL, AMOVSQ命令は、D_DIまたはD_SIレジスタを読み取る（または影響を与える）と明示されています。これらのレジスタは、文字列操作のソース/デスティネーションポインタとして使用されます。
  - ASTOSB, ASTOSL, ASTOSQ命令は、D_AXまたはD_DIレジスタを読み取る（または影響を与える）と明示されています。D_AXはストアされる値、D_DIはデスティネーションアドレスとして使用されることがあります。
  - AREP, AREPN命令は、D_CXレジスタを読み取る（または影響を与える）と明示されています。D_CXは繰り返し回数を保持します。

この修正により、ピーフホール最適化器は、これらのメモリ操作命令がレジスタの状態に与える影響を正確に認識し、誤った最適化を避けることができるようになりました。これにより、STOstringに関連するバグが解消され、コンパイラが生成するコードの正確性が向上します。

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

`src/cmd/6c/peep.c` (amd64 Cコンパイラ)

--- a/src/cmd/6c/peep.c
+++ b/src/cmd/6c/peep.c
@@ -377,6 +377,10 @@ subprop(Reg *r0)
 		case ACDQ:
 		case ACQO:
 
+		case ASTOSB:
+		case ASTOSL:
+		case ASTOSQ:
+		case AMOVSB:
 		case AMOVSL:
 		case AMOVSQ:
 			return 0;
@@ -755,11 +759,23 @@ copyu(Prog *p, Adr *v, Adr *s)
 			return 2;
 		goto caseread;
 
-	case AMOVSL:
-	case AMOVSQ:
 	case AREP:
 	case AREPN:
-		if(v->type == D_CX || v->type == D_DI || v->type == D_SI)
+		if(v->type == D_CX)
+			return 2;
+		goto caseread;
+
+	case AMOVSB:
+	case AMOVSL:
+	case AMOVSQ:
+		if(v->type == D_DI || v->type == D_SI)
+			return 2;
+		goto caseread;
+
+	case ASTOSB:
+	case ASTOSL:
+	case ASTOSQ:
+		if(v->type == D_AX || v->type == D_DI)
 			return 2;
 		goto caseread;

`src/cmd/6g/peep.c` (amd64 Goコンパイラ)

6cとほぼ同様の変更。

--- a/src/cmd/6g/peep.c
+++ b/src/cmd/6g/peep.c
@@ -392,6 +392,10 @@ subprop(Reg *r0)
 		case ACDQ:
 		case ACQO:
 
+		case ASTOSB:
+		case ASTOSL:
+		case ASTOSQ:
+		case AMOVSB:
 		case AMOVSL:
 		case AMOVSQ:
 			return 0;
@@ -770,11 +774,23 @@ copyu(Prog *p, Adr *v, Adr *s)
 			return 2;
 		goto caseread;
 
-	case AMOVSL:
-	case AMOVSQ:
 	case AREP:
 	case AREPN:
-		if(v->type == D_CX || v->type == D_DI || v->type == D_SI)
+		if(v->type == D_CX)
+			return 2;
+		goto caseread;
+
+	case AMOVSB:
+	case AMOVSL:
+	case AMOVSQ:
+		if(v->type == D_DI || v->type == D_SI)
+			return 2;
+		goto caseread;
+
+	case ASTOSB:
+	case ASTOSL:
+	case ASTOSQ:
+		if(v->type == D_AX || v->type == D_DI)
 			return 2;
 		goto caseread;

`src/cmd/8c/peep.c` (386 Cコンパイラ)

32ビットアーキテクチャのため、Q（クアッド）サフィックスの命令は存在しない。

--- a/src/cmd/8c/peep.c
+++ b/src/cmd/8c/peep.c
@@ -305,6 +305,9 @@ subprop(Reg *r0)
 		case ACWD:
 		case ACDQ:
 
+		case ASTOSB:
+		case ASTOSL:
+		case AMOVSB:
 		case AMOVSL:
 		case AFSTSW:
 			return 0;
@@ -669,10 +672,21 @@ copyu(Prog *p, Adr *v, Adr *s)
 			return 2;
 		goto caseread;
 
-	case AMOVSL:
 	case AREP:
 	case AREPN:
-		if(v->type == D_CX || v->type == D_DI || v->type == D_SI)
+		if(v->type == D_CX)
+			return 2;
+		goto caseread;
+
+	case AMOVSB:
+	case AMOVSL:
+		if(v->type == D_DI || v->type == D_SI)
+			return 2;
+		goto caseread;
+
+	case ASTOSB:
+	case ASTOSL:
+		if(v->type == D_AX || v->type == D_DI)
 			return 2;
 		goto caseread;

コアとなるコードの解説

このコミットの核心は、Goコンパイラのピーフホール最適化器が、特定のメモリ操作命令がレジスタの状態に与える影響をより正確にモデル化するように修正された点です。

`subprop` 関数内の変更

subprop関数は、レジスタの「サブスティテューション伝播」を行います。これは、あるレジスタが特定の値を保持している場合、そのレジスタが上書きされるまで、そのレジスタを使用する後続の命令を最適化しようとするものです。

変更前は、AMOVSLやAMOVSQといった命令が、レジスタの内容を破壊しない（または、最適化器がその影響を無視できる）と誤って見なされていました。しかし、これらの命令は、文字列操作のためにSI（ソースインデックス）、DI（デスティネーションインデックス）、CX（カウント）といったレジスタを暗黙的に使用し、その内容を変更する可能性があります。

変更後、以下の命令がsubpropのcase文に追加され、これらの命令が実行された場合には、レジスタのサブスティテューション伝播を停止する（return 0;）ように修正されました。

ASTOSB, ASTOSL, ASTOSQ: これらはバイト、ロング、クアッドサイズのデータをメモリにストアする命令です。通常、AXレジスタ（ストアする値）とDIレジスタ（デスティネーションアドレス）を使用し、DIをインクリメント/デクリメントします。
AMOVSB, AMOVSL, AMOVSQ: これらはバイト、ロング、クアッドサイズのデータをメモリ間で移動させる命令です。通常、SIレジスタ（ソースアドレス）とDIレジスタ（デスティネーションアドレス）を使用し、両方をインクリメント/デクリメントします。

これらの命令がレジスタの内容を破壊する可能性があるため、subpropはこれらの命令の後に、それらのレジスタに関する以前のサブスティテューション情報を無効にする必要があります。これにより、最適化器が古い、無効なレジスタ値に基づいて誤った最適化を行うことを防ぎます。

`copyu` 関数内の変更

copyu関数は、ある命令が特定のレジスタ（v）の内容を読み取るか、または書き込むかを判断するユーティリティ関数です。この関数は、コピー伝播などの最適化でレジスタのライブネス（値が有効である期間）を追跡するために使用されます。

変更前は、AMOVSLとAMOVSQがD_CX, D_DI, D_SIレジスタを読み取る（または影響を与える）と一括して扱われていました。

変更後、より詳細かつ正確なレジスタの依存関係が定義されました。

AREP, AREPN (繰り返しプレフィックス): これらの命令は、繰り返し回数を制御するD_CXレジスタに影響を与えます。そのため、if(v->type == D_CX)の場合にreturn 2;（レジスタへの書き込み/変更）とマークされます。
AMOVSB, AMOVSL, AMOVSQ: これらの命令は、ソースポインタD_SIとデスティネーションポインタD_DIを操作します。したがって、if(v->type == D_DI || v->type == D_SI)の場合にreturn 2;とマークされます。
ASTOSB, ASTOSL, ASTOSQ: これらの命令は、ストアする値が格納されるD_AXレジスタと、デスティネーションポインタD_DIを操作します。したがって、if(v->type == D_AX || v->type == D_DI)の場合にreturn 2;とマークされます。

これらの変更により、copyu関数は、各メモリ操作命令がどのレジスタを読み書きするかをより正確に報告できるようになりました。これにより、ピーフホール最適化器はレジスタのライブネス情報をより正確に維持し、STOstringに関連する最適化バグを解消することができます。

要するに、このコミットは、Goコンパイラのピーフホール最適化器が、文字列操作やメモリストア操作に関連するアセンブリ命令がレジスタの状態に与える影響を正しく理解していなかった問題を修正し、コンパイラが生成するコードの正確性と信頼性を向上させたものです。

参考にした情報源リンク

Goコンパイラのソースコード (特に src/cmd/6c/peep.c, src/cmd/6g/peep.c, src/cmd/8c/peep.c)
コンパイラ最適化に関する一般的な知識 (ピーフホール最適化、レジスタ割り当て、データフロー解析など)
x86アセンブリ言語の基本的な知識 (SI, DI, CX, AXレジスタの役割、MOVS, STOS命令など)
Go言語の初期のコミット履歴と開発に関する情報
Go言語の内部アセンブリに関するドキュメントや解説 (Goのソースコード内のsrc/cmd/internal/objやsrc/cmd/asmディレクトリに関連情報があることが多い)
GoのIssue Tracker (該当するバグ報告がある場合)
Goのメーリングリストやフォーラム (過去の議論がある場合)
Goのコードレビューシステム (OCL/CL番号から辿れる場合)