Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

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

このコミットは、Goコンパイラ（cmd/6g および cmd/8g）における定数伝播のバグ修正に関するものです。具体的には、定数ではないLEA（Load Effective Address）命令の定数伝播を防ぐための変更が加えられています。これにより、コンパイラが誤った最適化を行うことを防ぎ、プログラムの正確性を保証します。

コミット

commit 3c3ce8e7fbe98a233cadbc59a05afdbbcacb0fe5
Author: Daniel Morsing <daniel.morsing@gmail.com>
Date:   Fri Jul 5 16:11:22 2013 +0200

    cmd/6g, cmd/8g: prevent constant propagation of non-constant LEA.
    
    Fixes #5809.
    
    R=golang-dev, dave, rsc, nigeltao
    CC=golang-dev
    https://golang.org/cl/10785043

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

https://github.com/golang/go/commit/3c3ce8e7fbe98a233cadbc59a05afdbbcacb0fe5

元コミット内容

cmd/6g, cmd/8g: prevent constant propagation of non-constant LEA.

Fixes #5809.

R=golang-dev, dave, rsc, nigeltao
CC=golang-dev
https://golang.org/cl/10785043

変更の背景

このコミットは、Goコンパイラ（cmd/6g および cmd/8g）が、LEA（Load Effective Address）命令に対して誤った定数伝播を行う可能性があったバグ（Issue 5809）を修正するために導入されました。

LEA命令は、メモリのアドレスを計算する命令ですが、その計算結果が必ずしも定数になるとは限りません。例えば、レジスタの値や配列のインデックスなど、実行時に変動する値に基づいてアドレスが計算される場合、その結果は定数ではありません。

しかし、Goコンパイラの最適化フェーズにおいて、LEA命令の計算結果が定数であるかのように扱われ、誤って定数伝播が行われるケースがありました。これにより、本来実行時に計算されるべきアドレスがコンパイル時に固定されてしまい、プログラムの動作が不正になる可能性がありました。特に、配列のインデックスが変数である場合などにこの問題が発生しやすかったと考えられます。

このバグは、test/fixedbugs/issue5809.go という新しいテストファイルで再現されており、LEA命令が非定数インデックスを持つ場合に、誤った値が計算されることを示しています。このコミットは、このような誤った最適化を防ぎ、コンパイラの生成するコードの正確性を保証することを目的としています。

前提知識の解説

定数伝播 (Constant Propagation)

定数伝播は、コンパイラの最適化手法の一つです。プログラム中で定数であることが判明している変数の値を、その変数が使用されている箇所に直接置き換えることで、実行時の計算を減らし、パフォーマンスを向上させます。

例:

a := 10
b := a + 5
c := b * 2

このコードは、定数伝播によって以下のように最適化される可能性があります。

a := 10
b := 10 + 5 // b := 15
c := 15 * 2 // c := 30

最終的には、c の値が 30 であることがコンパイル時に確定し、c を使用する箇所では直接 30 が使われるようになります。

しかし、定数ではない値（例えば、ユーザー入力や実行時に変化するレジスタの値など）が誤って定数として扱われると、プログラムの動作が不正になります。

LEA (Load Effective Address) 命令

LEA（Load Effective Address）は、x86アーキテクチャのCPU命令の一つです。この命令は、メモリのアドレスを計算し、その計算結果をレジスタに格納します。重要なのは、LEA命令は実際にメモリからデータを読み込むわけではなく、単にアドレスの計算を行うだけであるという点です。

LEA命令の一般的な形式は LEA destination_register, source_operand です。source_operand は、ベースレジスタ、インデックスレジスタ、スケール、オフセット（ディスプレースメント）の組み合わせで表現されるメモリオペランドです。

例: LEA EAX, [EBX + ECX*4 + 10h] この命令は、EBX + ECX * 4 + 16（16進数の10hは10進数で16）という計算を行い、その結果を EAX レジスタに格納します。この計算は、配列の要素のアドレスを効率的に計算する際によく使用されます。

LEA命令は、以下のような特徴と用途があります。

  • メモリアクセスなし: MOV 命令がメモリの内容を読み込むのに対し、LEAはアドレス計算のみを行います。
  • 効率的な算術演算: 加算や乗算（1, 2, 4, 8倍）を単一の命令で実行できるため、汎用的な算術演算にも利用されます。
  • アドレスの取得: ローカル変数やグローバル変数のアドレスを取得する際に使用されます。
  • 位置独立コード (PIC): 現代のOSでは、RIP（命令ポインタ）相対アドレス指定と組み合わせて、位置独立コードの生成に利用されます。

cmd/6g と cmd/8g

これらは、Go言語の初期のコンパイラです。

  • cmd/6g: AMD64 (x86-64) アーキテクチャ向けのGoコンパイラ。
  • cmd/8g: x86 (32-bit) アーキテクチャ向けのGoコンパイラ。

Goコンパイラは、ソースコードを中間表現に変換し、その後、ターゲットアーキテクチャの機械語に変換します。この過程で、様々な最適化が行われます。peep.c は、これらのコンパイラのバックエンドの一部であり、命令の最適化（peephole optimization）を担当しています。

技術的詳細

このコミットの技術的な核心は、GoコンパイラのバックエンドにおけるLEA命令の定数伝播のロジックにあります。LEA命令は、その性質上、アドレス計算の結果が定数になる場合と、実行時に変動する非定数になる場合があります。

LEA命令のオペランドは、p->from という構造体で表現され、その中に index というフィールドがあります。この index フィールドは、LEA命令がインデックスレジスタを使用しているかどうか、そしてそのインデックスが定数であるか非定数であるかを示す情報を含んでいます。

LEA命令の定数伝播を行う conprop(r) 関数は、LEA命令の計算結果が定数である場合にのみ呼び出されるべきです。しかし、これまでの実装では、p->from.sym != S という条件（シンボルがNULLでないこと）のみで定数伝播の可否を判断していました。この条件だけでは、インデックスが非定数であるLEA命令に対しても conprop が呼び出されてしまう可能性がありました。

具体的には、p->from.index が D_NONE（インデックスなし）または D_CONST（定数インデックス）の場合にのみ、LEA命令の計算結果が定数として扱えるべきです。それ以外の場合（例えば、インデックスがレジスタである場合など）は、計算結果は非定数であり、定数伝播を行うべきではありません。

このコミットでは、peep.c ファイル内の peep 関数において、LEA命令（ALEAQ および ALEAL）の処理に新しい条件 p->from.index == D_NONE || p->from.index == D_CONST を追加しました。この条件により、LEA命令のソースオペランドがインデックスレジスタを使用していないか、または定数インデックスを使用している場合にのみ conprop 関数が呼び出されるようになります。これにより、非定数LEAの誤った定数伝播が効果的に防止されます。

この修正は、コンパイラが生成するコードの正確性を向上させ、特に配列の動的なインデックスアクセスなどを含むプログラムにおいて、予期せぬバグが発生するのを防ぎます。

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

diff --git a/src/cmd/6g/peep.c b/src/cmd/6g/peep.c
index e77d65e873..5db9f4cf16 100644
--- a/src/cmd/6g/peep.c
+++ b/src/cmd/6g/peep.c
@@ -154,6 +154,7 @@ peep(void)
 		case ALEAQ:
 			if(regtyp(&p->to))
 			if(p->from.sym != S)
+			if(p->from.index == D_NONE || p->from.index == D_CONST)
 				conprop(r);
 			break;

diff --git a/src/cmd/8g/peep.c b/src/cmd/8g/peep.c
index 6b7e4363d8..e4c8afa372 100644
--- a/src/cmd/8g/peep.c
+++ b/src/cmd/8g/peep.c
@@ -147,6 +147,7 @@ peep(void)
 		case ALEAL:
 			if(regtyp(&p->to))
 			if(p->from.sym != S)
+			if(p->from.index == D_NONE || p->from.index == D_CONST)
 				conprop(r);
 			break;

diff --git a/test/fixedbugs/issue5809.go b/test/fixedbugs/issue5809.go
new file mode 100644
index 0000000000..ca060b55de
--- /dev/null
+++ b/test/fixedbugs/issue5809.go
@@ -0,0 +1,27 @@
+// run
+
+// Copyright 2013 The Go Authors.  All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+// issue 5809: 6g and 8g attempted to constant propagate indexed LEA
+
+package main
+
+import "fmt"
+
+func main() {
+	const d16 = "0123456789ABCDEF"
+	k := 0x1234
+	var x [4]byte
+	
+	x[0] = d16[k>>12&0xf]
+	x[1] = d16[k>>8&0xf]
+	x[2] = d16[k>>4&0xf]
+	x[3] = d16[k&0xf]
+	
+	if x != [4]byte{'1','2','3','4'} {
+		fmt.Println(x)
+		panic("x != [4]byte{'1','2','3','4'}")
+	}
+}

コアとなるコードの解説

変更は src/cmd/6g/peep.c と src/cmd/8g/peep.c の両方に適用されています。これらのファイルは、それぞれAMD64とx86アーキテクチャ向けのGoコンパイラのバックエンドにおける命令最適化（peephole optimization）を担当しています。

追加された行は以下の通りです。

			if(p->from.index == D_NONE || p->from.index == D_CONST)
				conprop(r);

このコードは、LEA命令（ALEAQ はAMD64、ALEAL はx86におけるLEA命令のオペコード）の処理ブロック内に挿入されています。

  • p: 現在処理している命令（Prog 構造体）へのポインタ。
  • p->from: 命令のソースオペランドを表す構造体。
  • p->from.index: ソースオペランドがインデックスレジスタを使用しているかどうか、およびそのインデックスの種類を示すフィールド。
    • D_NONE: インデックスレジスタが使用されていないことを示します。この場合、アドレス計算はベースレジスタとオフセットのみで行われ、結果は定数になり得ます。
    • D_CONST: インデックスが定数であることを示します。この場合も、アドレス計算の結果は定数になり得ます。
  • conprop(r): 定数伝播を行う関数。r はレジスタを表すポインタです。

変更の意図:

この条件 if(p->from.index == D_NONE || p->from.index == D_CONST) が追加される前は、LEA命令の定数伝播は if(p->from.sym != S) という条件（シンボルがNULLでないこと）のみで行われていました。しかし、この条件だけでは、インデックスがレジスタであるなど、実行時に値が変動する非定数LEA命令に対しても誤って定数伝播が適用されてしまう可能性がありました。

新しい条件が追加されたことで、LEA命令のソースオペランドがインデックスレジスタを使用していない (D_NONE) か、または定数インデックスを使用している (D_CONST) 場合にのみ、conprop 関数が呼び出されるようになります。これにより、非定数LEA命令の誤った定数伝播が効果的に防止され、コンパイラが生成するコードの正確性が保証されます。

また、test/fixedbugs/issue5809.go という新しいテストファイルが追加されています。このテストは、LEA命令が非定数インデックスを持つ場合に、修正前のコンパイラが誤ったコードを生成し、パニックを引き起こすことを再現しています。このテストの追加により、修正が正しく機能していることが検証され、将来的な回帰を防ぐことができます。

関連リンク

参考にした情報源リンク

  • LEA instruction assembly x86: https://www.google.com/search?q=LEA+instruction+assembly+x86
  • Go言語のソースコード（src/cmd/6g/peep.c, src/cmd/8g/peep.c, test/fixedbugs/issue5809.go）
  • コンパイラの最適化に関する一般的な知識（定数伝播など）
  • x86アセンブリ言語に関する一般的な知識（LEA命令など）