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

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

このコミットは、Goコンパイラ（6gおよび8g）における定数伝播の最適化に関するバグ修正です。具体的には、インライン化された関数呼び出しにおいて、冗長な設定操作のチェック時にシンボル名ではなくノードポインタを使用して比較するように変更することで、誤った最適化（LEAQ命令の誤った削除）を防ぎ、定数伝播がインライン化とより適切に連携するように改善しています。

コミット

  • コミットハッシュ: fff732ea2c4d3cb449c4383a6957ff80ca75c70a
  • Author: Jamie Gennis jgennis@google.com
  • Date: Wed Feb 8 10:25:13 2012 -0500
  • コミットメッセージ: 
    6g,8g: make constant propagation inlining-friendly.

This changes makes constant propagation compare 'from' values using node
pointers rather than symbol names when checking to see whether a set
operation is redundant. When a function is inlined multiple times in a
calling function its arguments will share symbol names even though the values
are different. Prior to this fix the bug409 test would hit a case with 6g
where an LEAQ instruction was incorrectly eliminated from the second inlined
function call. 8g appears to have had the same bug, but the test did not fail
there.

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

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

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

元コミット内容

6g,8g: make constant propagation inlining-friendly.

This changes makes constant propagation compare 'from' values using node
pointers rather than symbol names when checking to see whether a set
operation is redundant. When a function is inlined multiple times in a
calling function its arguments will share symbol names even though the values
are different. Prior to this fix the bug409 test would hit a case with 6g
where an LEAQ instruction was incorrectly eliminated from the second inlined
function call. 8g appears to have had the same bug, but the test did not fail
there.

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

変更の背景

この変更は、Goコンパイラ（特に6gと8g、それぞれx86-64とx86アーキテクチャ向けのコンパイラ）における最適化のバグを修正するために行われました。問題は、関数が呼び出し元関数内で複数回インライン化される場合に発生しました。

インライン化とは、関数呼び出しのオーバーヘッドを削減するために、呼び出される関数のコードを呼び出し元の場所に直接埋め込むコンパイラ最適化手法です。このプロセス中に、異なる呼び出しであっても、インライン化された関数の引数が同じ「シンボル名」を共有してしまうことがありました。

Goコンパイラの定数伝播（Constant Propagation）最適化は、変数の値がコンパイル時に定数であることが判明した場合に、その変数の使用箇所を直接その定数で置き換えることで、実行時の計算を削減するものです。この最適化は、ある「設定操作」（set operation）が冗長であるかどうかを判断する際に、from値の比較を行っていました。

バグは、この冗長性チェックがfrom値の比較に「シンボル名」を使用していたことに起因します。関数が複数回インライン化されると、それぞれのインライン化されたインスタンスで引数の値は異なるにもかかわらず、それらが同じシンボル名を持つことがありました。これにより、コンパイラは異なる値を持つ引数を同じものと誤認し、誤った最適化を適用してしまう可能性がありました。

具体的には、bug409というテストケースで、6gコンパイラが2回目のインライン化された関数呼び出しからLEAQ命令（Load Effective Address）を誤って削除してしまうケースが報告されました。LEAQ命令は、メモリのアドレスを計算してレジスタにロードするために使用される命令であり、これが誤って削除されると、プログラムの動作が不正になる可能性があります。8gコンパイラでも同様のバグが存在したと考えられますが、bug409テストでは8gで失敗することはなかったようです。

このコミットは、この誤った最適化を防ぎ、定数伝播がインライン化されたコードに対して正しく機能するようにするために、比較ロジックをシンボル名から「ノードポインタ」に変更することで問題を解決しました。

前提知識の解説

Goコンパイラ (6g, 8g)

Go言語の初期のコンパイラは、ターゲットアーキテクチャごとに異なる名前を持っていました。

  • 6g: x86-64 (AMD64) アーキテクチャ向けのGoコンパイラ。
  • 8g: x86 (32-bit Intel) アーキテクチャ向けのGoコンパイラ。 現在では、これらのコンパイラはgo tool compileコマンドに統合されており、ユーザーが直接6gや8gを呼び出すことは稀です。しかし、このコミットが作成された2012年当時は、これらの名前が一般的に使われていました。

コンパイラ最適化

コンパイラ最適化とは、コンパイラがソースコードを機械語に変換する際に、生成される機械語コードの実行速度やサイズを改善するための様々な技術の総称です。

インライン化 (Inlining)

インライン化は、関数呼び出しのオーバーヘッド（スタックフレームのセットアップ、引数の渡し、戻り値の処理など）を削減するためのコンパイラ最適化手法の一つです。具体的には、呼び出される関数の本体コードを、その関数が呼び出される場所に直接展開（コピー＆ペースト）します。これにより、関数呼び出しのコストがなくなるため、プログラムの実行速度が向上する可能性があります。しかし、コードサイズが増加する可能性もあります。

定数伝播 (Constant Propagation)

定数伝播は、コンパイラ最適化の一種で、プログラム中の変数がコンパイル時に定数であることが判明した場合に、その変数の使用箇所を直接その定数で置き換えるものです。例えば、x = 10; y = x + 5;というコードがあった場合、定数伝播によってy = 10 + 5;となり、さらにy = 15;と最適化される可能性があります。これにより、実行時の計算が削減され、パフォーマンスが向上します。

シンボル名 (Symbol Name)

コンパイラやリンカの文脈における「シンボル」とは、変数、関数、ラベルなどのプログラム要素を一意に識別するための名前です。コンパイルの過程で、これらのシンボルはメモリ上の特定のアドレスやレジスタにマッピングされます。シンボル名は、プログラムの異なる部分が同じデータや関数を参照できるようにするために使用されます。

ノードポインタ (Node Pointer)

コンパイラの内部では、ソースコードは抽象構文木（Abstract Syntax Tree, AST）や中間表現（Intermediate Representation, IR）として表現されます。この木構造やグラフ構造の各要素は「ノード」と呼ばれます。ノードポインタは、これらのノードを指し示すメモリ上のアドレスです。同じシンボル名を持つ複数の変数や式であっても、それらが異なる実行コンテキスト（例えば、異なるインライン化された関数呼び出しのインスタンス）に属する場合、コンパイラ内部ではそれぞれ異なるノードとして表現され、異なるノードポインタを持つことになります。

LEAQ 命令 (Load Effective Address)

LEAQ (Load Effective Address) は、x86およびx86-64アーキテクチャの命令セットにおけるアセンブリ命令の一つです。この命令は、オペランドで指定されたメモリのアドレスを計算し、その結果をレジスタにロードします。データそのものをメモリからロードするMOV命令とは異なり、LEAQはアドレスの計算のみを行い、メモリへのアクセスは伴いません。ポインタの計算や、複数の値を加算するなどの算術演算の高速化にも利用されることがあります。

技術的詳細

このコミットの技術的な核心は、Goコンパイラのバックエンド、特に最適化フェーズにおける定数伝播のロジックの修正にあります。変更はsrc/cmd/6g/peep.cとsrc/cmd/8g/peep.cというファイルで行われています。これらのファイルは、それぞれ6gと8gコンパイラの「ピーフホール最適化（Peephole Optimization）」を担当する部分です。

ピーフホール最適化は、コンパイラが生成したアセンブリコードの小さな「窓」（ピーフホール）を覗き込み、より効率的な命令シーケンスに置き換えることで、コードを改善する最適化手法です。この文脈では、定数伝播に関連する冗長な設定操作を特定し、削除するロジックが含まれています。

問題のコードは、loopというラベル内のcase 3: // setの部分にあります。これは、ある設定操作（p）が、以前の設定操作（p0）と冗長であるかどうかをチェックするロジックです。冗長であると判断された場合、pは削除される可能性があります。

変更前は、この冗長性チェックの一部として、p->from.sym == p0->from.symという比較が行われていました。これは、設定操作の「元」（from）が同じシンボル名を持つかどうかを確認するものです。

しかし、前述の通り、関数が複数回インライン化されると、異なるインライン化されたインスタンスの引数であっても、コンパイラ内部で同じシンボル名が割り当てられることがありました。これにより、実際には異なる値を持つ引数に対して、コンパイラが「同じシンボル名だから冗長だ」と誤って判断し、LEAQ命令のような重要な命令を削除してしまうバグが発生しました。

このコミットでは、この比較をp->from.sym == p0->from.symからp->from.node == p0->from.nodeに変更しています。

  • p->from.sym: 設定操作の「元」が参照するシンボルの名前。
  • p->from.node: 設定操作の「元」が参照するコンパイラ内部のノードのポインタ。

ノードポインタは、コンパイラ内部の抽象構文木や中間表現における個々の要素を一意に識別します。たとえ同じシンボル名を持つ変数であっても、それが異なるインライン化された関数呼び出しのインスタンスに属する場合、コンパイラはそれらを異なるノードとして表現し、それぞれに異なるノードポインタを割り当てます。

したがって、比較をシンボル名からノードポインタに変更することで、コンパイラは異なる実行コンテキストに属する同じシンボル名の変数を正しく区別できるようになります。これにより、定数伝播の冗長性チェックがより正確になり、誤った最適化（LEAQ命令の誤った削除など）が防止され、インライン化されたコードの正確性が保証されます。

test/fixedbugs/bug409.goは、このバグを再現し、修正が正しく機能することを確認するためのテストケースです。このテストは、Fという関数を複数回呼び出し、その結果をaとbに格納し、printlnで出力するというシンプルなものです。F関数は、[2]float64型の配列を受け取り、それをそのまま返すという、インライン化されやすい構造をしています。このテストが、LEAQ命令の誤った削除という特定のケースを捉えるように設計されています。

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

このコミットにおける主要なコード変更は、src/cmd/6g/peep.cとsrc/cmd/8g/peep.cの2つのファイルにあります。両ファイルで全く同じ変更が行われています。

diff --git a/src/cmd/6g/peep.c b/src/cmd/6g/peep.c
index 63ef3f78f0..3710033b20 100644
--- a/src/cmd/6g/peep.c
+++ b/src/cmd/6g/peep.c
@@ -987,7 +987,7 @@ loop:
 	case 3:	// set
 		if(p->as == p0->as)
 		if(p->from.type == p0->from.type)
-		if(p->from.sym == p0->from.sym)
+		if(p->from.node == p0->from.node)
 		if(p->from.offset == p0->from.offset)
 		if(p->from.scale == p0->from.scale)
 		if(p->from.dval == p0->from.dval)
diff --git a/src/cmd/8g/peep.c b/src/cmd/8g/peep.c
index e0e44a5ef4..b8a2825e5a 100644
--- a/src/cmd/8g/peep.c
+++ b/src/cmd/8g/peep.c
@@ -878,7 +878,7 @@ loop:
 	case 3:	// set
 		if(p->as == p0->as)
 		if(p->from.type == p0->from.type)
-		if(p->from.sym == p0->from.sym)
+		if(p->from.node == p0->from.node)
 		if(p->from.offset == p0->from.offset)
 		if(p->from.scale == p0->from.scale)
 		if(p->from.dval == p0->from.dval)

また、この修正を検証するための新しいテストケースが追加されています。

diff --git a/test/fixedbugs/bug409.go b/test/fixedbugs/bug409.go
new file mode 100644
index 0000000000..884d333708
--- /dev/null
+++ b/test/fixedbugs/bug409.go
@@ -0,0 +1,20 @@
+// $G $D/$F.go && $L $F.$A && ./$A.out 2>&1 | cmp - $D/$F.out
+
+// Copyright 2012 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.
+
+// Multiple inlined calls to a function that causes
+// redundant address loads.
+
+package main
+
+func F(v [2]float64) [2]float64 {
+	return [2]float64{v[0], v[1]}
+}
+
+func main() {
+	a := F([2]float64{1, 2})
+	b := F([2]float64{3, 4})
+	println(a[0], a[1], b[0], b[1])
+}
diff --git a/test/fixedbugs/bug409.out b/test/fixedbugs/bug409.out
new file mode 100644
index 0000000000..3cb40ed59a
--- /dev/null
+++ b/test/fixedbugs/bug409.out
@@ -0,0 +1 @@
++1.000000e+000 +2.000000e+000 +3.000000e+000 +4.000000e+000

コアとなるコードの解説

src/cmd/6g/peep.cとsrc/cmd/8g/peep.cは、Goコンパイラのバックエンドにおけるピーフホール最適化のロジックを実装しています。これらのファイルは、アセンブリコードレベルでの最適化を担当し、冗長な命令の削除やより効率的な命令への置き換えを行います。

変更が行われたコードスニペットは、以下のような条件分岐の一部です。

		if(p->as == p0->as)
		if(p->from.type == p0->from.type)
		if(p->from.sym == p0->from.sym) // 変更前
		if(p->from.node == p0->from.node) // 変更後
		if(p->from.offset == p0->from.offset)
		if(p->from.scale == p0->from.scale)
		if(p->from.dval == p0->from.dval)

この一連のif文は、現在の命令pが、以前の命令p0と「同じ」である、つまりpがp0の冗長なコピーであるかどうかを判断するためのものです。もしこれらの条件がすべて真であれば、pは冗長であると判断され、削除される可能性があります。

各条件の意味は以下の通りです。

  • p->as == p0->as: 命令の種類（アセンブリ命令のオペコード）が同じか。
  • p->from.type == p0->from.type: 命令のfromオペランドの型が同じか。
  • p->from.sym == p0->from.sym (変更前): 命令のfromオペランドが参照するシンボル名が同じか。
  • p->from.node == p0->from.node (変更後): 命令のfromオペランドが参照するコンパイラ内部のノードポインタが同じか。
  • p->from.offset == p0->from.offset: 命令のfromオペランドのオフセットが同じか。
  • p->from.scale == p0->from.scale: 命令のfromオペランドのスケールファクタが同じか（配列アクセスなどで使用）。
  • p->from.dval == p0->from.dval: 命令のfromオペランドの定数値が同じか（定数である場合）。

変更の重要性: 変更前は、p->from.sym == p0->from.symという条件が、インライン化された関数呼び出しのバグの原因でした。関数が複数回インライン化されると、それぞれの呼び出しで異なる値を持つ引数であっても、コンパイラが内部的に同じシンボル名を割り当ててしまうことがありました。このため、コンパイラは異なる値を持つ引数を同じものと誤認し、冗長な命令として削除してしまう可能性がありました。

例えば、F([2]float64{1, 2})とF([2]float64{3, 4})のように同じ関数Fが異なる引数で2回インライン化された場合、Fの引数vに対応するシンボルは、両方のインライン化されたインスタンスで同じ名前を持つことがありました。しかし、それぞれのvは異なるメモリ位置にあり、異なる値を持っています。p->from.symで比較すると、これらが同じであると誤って判断され、例えば2回目のF呼び出しで必要なLEAQ命令が「冗長」と見なされて削除されてしまう、という問題が発生しました。

p->from.node == p0->from.nodeへの変更は、この問題を解決します。nodeはコンパイラ内部の抽象構文木や中間表現における個々の要素を指すポインタです。たとえ同じシンボル名を持つ変数であっても、それが異なるインライン化された関数呼び出しのインスタンスに属する場合、コンパイラはそれらを異なるノードとして表現し、それぞれに異なるノードポインタを割り当てます。

したがって、ノードポインタで比較することで、コンパイラは異なる実行コンテキストに属する同じシンボル名の変数を正しく区別できるようになります。これにより、定数伝播の冗長性チェックがより正確になり、インライン化されたコードに対して誤った最適化が適用されることがなくなり、プログラムの正確性が保証されます。

関連リンク

参考にした情報源リンク

  • Go言語のソースコード (特にsrc/cmd/6g/peep.c, src/cmd/8g/peep.c, test/fixedbugs/bug409.go)
  • Go言語のコンパイラに関する一般的な知識
  • コンパイラ最適化（インライン化、定数伝播、ピーフホール最適化）に関する一般的な知識
  • x86/x86-64アセンブリ命令（LEAQ）に関する一般的な知識