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

このコミットは、Goコンパイラ（cmd/gc）における論理演算子 && および || を含む式のコード生成順序付けに関するバグを修正します。具体的には、これらの演算子を含む式が評価される際に、副作用を持つ初期化処理（ninit）が正しく考慮されず、コードの再順序付けによって予期せぬ動作を引き起こす可能性があった問題に対処しています。この修正により、式の評価順序が保証され、より堅牢なコード生成が実現されます。

コミット

• コミットハッシュ: 5efd5624cc5b22f50d2739b0f1dbce32402206cb
• Author: Luuk van Dijk lvd@golang.org
• Date: Mon Feb 6 15:41:01 2012 +0100

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

https://github.com/golang/go/commit/5efd5624cc5b22f50d2739b0f1dbce32402206cb

元コミット内容

cmd/gc: fix codegen reordering for expressions involving && and ||

Fixes #2821.

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

変更の背景

Goコンパイラ（cmd/gc）は、プログラムのソースコードを機械語に変換する過程で、最適化のために式の評価順序を再編成（reordering）することがあります。しかし、論理AND (&&) や論理OR (||) のようなショートサーキット評価を行う演算子を含む式の場合、その評価順序は厳密に保証される必要があります。特に、式の一部が副作用を持つ初期化処理（ninit）を伴う場合、コンパイラがその副作用を考慮せずに再順序付けを行うと、プログラムの動作が変わり、バグにつながる可能性があります。

このコミットは、Goの内部バグトラッカーで報告されたIssue 2821を修正するために作成されました。このIssueは、&& や || を含む式において、コンパイラがコード生成時に誤った順序で処理を行うことで発生する問題を示していました。具体的には、true && a.equal() のような式で、a.equal() の評価が true の評価よりも前に実行されてしまうようなケースが問題となっていました。これは、&& 演算子が左から右へ評価され、左オペランドが false であれば右オペランドは評価されない（ショートサーキット）というGoの言語仕様に反します。

前提知識の解説

Goコンパイラ (cmd/gc)

Go言語の公式コンパイラの一つで、Goのソースコードをバイナリ実行ファイルに変換します。gc はGoのツールチェインの中核をなすコンポーネントであり、最適化やコード生成を担当します。

論理演算子 && と || (ショートサーキット評価)

Go言語における論理AND (&&) と論理OR (||) は、ショートサーキット評価を行います。

• A && B: A が false であれば、B は評価されません。
• A || B: A が true であれば、B は評価されません。 この特性は、例えば if obj != nil && obj.Method() のように、nilチェックとメソッド呼び出しを安全に組み合わせる際に非常に重要です。

式の再順序付け (Expression Reordering)

コンパイラは、生成される機械語の効率を向上させるために、式の評価順序を最適化することがあります。これは、依存関係のない独立した計算を並列化したり、レジスタの使用効率を高めたりするために行われます。しかし、副作用を持つ式や、厳密な評価順序が言語仕様で定められている式（例: ショートサーキット評価）の場合、この再順序付けは慎重に行われる必要があります。

Ullman Number (ウルマン数)

コンパイラの最適化において、式の複雑度やレジスタ割り当ての優先度を決定するために使用される概念です。Ullman数は、式のツリー構造を走査し、各ノードに必要なレジスタの数を推定します。Ullman数が高いノードは、より多くのレジスタを必要とするか、より複雑な計算を伴うことを示唆します。コンパイラは、Ullman数に基づいてコード生成の順序を決定し、レジスタのスピル（メモリへの退避）を最小限に抑えようとします。

Node 構造体と ninit

Goコンパイラの内部では、プログラムの各要素（式、文、関数など）が抽象構文木（AST）のノードとして表現されます。これらのノードは Node 構造体で表されます。 ninit は Node 構造体の一部であり、そのノードに関連付けられた初期化文のリストを保持します。例えば、複合リテラルや関数呼び出しなど、評価に先立って何らかの初期化や準備が必要な場合に ninit が使用されます。ninit に含まれる文は、そのノードが評価される前に実行されることが期待されます。

技術的詳細

このコミットの核心は、Goコンパイラのコード生成フェーズにおいて、&& や || のようなショートサーキット演算子を含む式の評価順序が、ninit に関連付けられた副作用によって乱される可能性があった問題の修正です。

Goコンパイラは、式のコード生成順序を決定する際にUllman数を使用します。Ullman数が小さい式から順にコードを生成することで、レジスタの使用効率を高めようとします。しかし、ninit を持つノード（つまり、評価に先立って初期化処理が必要なノード）の場合、その初期化処理自体が副作用を持つ可能性があり、その副作用がUllman数の計算やコード生成の順序に影響を与えるべきです。

元の実装では、ullmancalc 関数がノードのUllman数を計算する際に、ninit の存在を適切に考慮していませんでした。これにより、ninit を持つノードが、その副作用が実行される前に再順序付けされてしまう可能性がありました。特に、&& や || の右オペランドが ninit を持つ場合、ショートサーキット評価の原則が破られ、右オペランドが不必要に評価されてしまうことが問題でした。

この修正は、以下の2つの主要な変更によってこの問題に対処しています。

1. ullmancalc 関数における ninit の考慮: src/cmd/gc/subr.c の ullmancalc 関数に、ノードが ninit を持つ場合にそのUllman数を UINF (無限大、つまり非常に高い値) に設定するロジックが追加されました。これにより、ninit を持つノードは、他のノードよりも低い優先度でコード生成されるようになり、その初期化処理が適切に評価されることが保証されます。UINF に設定することで、コンパイラはそのノードを再順序付けの対象から外し、依存関係が解決されるまで評価を遅らせるようになります。

2. addinit 関数における ullman のリセット: src/cmd/gc/subr.c の addinit 関数は、ノードに初期化文（ninit）を追加する役割を担っています。この関数に、ninit を追加したノードのUllman数を UINF にリセットする行が追加されました。これは、ノードに初期化文が追加された時点で、そのノードのUllman数が再計算される必要があることを示しています。これにより、ninit が追加されたノードが、その副作用が考慮されないまま誤って再順序付けされることを防ぎます。

3. walkexpr 関数における ullmancalc の呼び出し順序の変更: src/cmd/gc/walk.c の walkexpr 関数は、式のウォーク（走査）と変換を行う関数です。この関数内で、ullmancalc(n) の呼び出し位置が変更されました。以前は lineno = lno; *np = n; の後に呼び出されていましたが、修正後は ret: ラベルの直後、つまり式のウォークが完了し、ノードが最終的な形になった直後に呼び出されるようになりました。これにより、ノードの ninit が完全に構築された後にUllman数が計算されることが保証され、より正確なUllman数の評価が可能になります。

これらの変更により、&& や || のようなショートサーキット演算子を含む式において、ninit に関連付けられた副作用が正しく考慮され、コンパイラがコードを再順序付けする際に予期せぬ動作を引き起こすことがなくなりました。

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

src/cmd/gc/subr.c

--- a/src/cmd/gc/subr.c
+++ b/src/cmd/gc/subr.c
@@ -1670,6 +1670,11 @@ ullmancalc(Node *n)
 	if(n == N)
 		return;
 
+	if(n->ninit != nil) {
+		ul = UINF;
+		goto out;
+	}
+
 	switch(n->op) {
 	case OREGISTER:
 	case OLITERAL:
@@ -3577,4 +3582,5 @@ addinit(Node **np, NodeList *init)
 		break;
 	}
 	n->ninit = concat(init, n->ninit);
+	n->ullman = UINF;
 }

src/cmd/gc/walk.c

--- a/src/cmd/gc/walk.c
+++ b/src/cmd/gc/walk.c
@@ -1203,10 +1203,11 @@ walkexpr(Node **np, NodeList **init)
 	fatal("missing switch %O", n->op);
 
 ret:
+	ullmancalc(n);
+
 	if(debug['w'] && n != N)
 		dump("walk", n);
 
-	ullmancalc(n);
 	lineno = lno;
 	*np = n;
 }

test/fixedbugs/bug406.go (新規追加)

// $G $D/$F.go && $L $F.$A && ./$A.out || echo "Bug406"

// 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.

// Issue 2821
package main

type matrix struct {
	e []int
}

func (a matrix) equal() bool {
	for _ = range a.e {
	}
	return true
}

func main() {
	var a matrix
	var i interface{}
	i = true && a.equal()
	_ = i
}

コアとなるコードの解説

src/cmd/gc/subr.c の変更点

1. ullmancalc(Node *n) 関数内:

   +	if(n->ninit != nil) {
   +		ul = UINF;
   +		goto out;
   +	}
   

   このコードブロックは、ノード n が ninit（初期化文のリスト）を持っているかどうかをチェックします。もし持っている場合、そのノードのUllman数を UINF (Ullman Infinity) に設定し、関数の残りの部分をスキップして out ラベルにジャンプします。 目的: ninit を持つノードは、その初期化処理が副作用を持つ可能性があるため、コンパイラがその評価順序を勝手に変更すべきではありません。Ullman数を UINF に設定することで、このノードはコード生成の際に最も低い優先度を与えられ、その初期化処理が適切に実行されることが保証されます。これにより、ショートサーキット評価の原則が守られ、&& や || の右オペランドが不必要に評価されることを防ぎます。

2. addinit(Node **np, NodeList *init) 関数内:

   +	n->ullman = UINF;
   

   この行は、ノード n に新しい初期化文 init が追加された直後に、そのノードのUllman数を UINF にリセットします。 目的: ノードに ninit が追加されたということは、そのノードの評価に副作用が伴う可能性が生じたことを意味します。したがって、以前に計算されたUllman数は無効になる可能性があり、再計算が必要になります。UINF に設定することで、このノードが再順序付けの対象から外れ、その初期化処理が適切に考慮されるようになります。

src/cmd/gc/walk.c の変更点

1. walkexpr(Node **np, NodeList **init) 関数内:

   --- a/src/cmd/gc/walk.c
   +++ b/src/cmd/gc/walk.c
   @@ -1203,10 +1203,11 @@ walkexpr(Node **np, NodeList **init)
    	fatal("missing switch %O", n->op);
    
    ret:
   +	ullmancalc(n);
   +
    	if(debug['w'] && n != N)
    		dump("walk", n);
    
   -	ullmancalc(n);
    	lineno = lno;
    	*np = n;
    }
   

   ullmancalc(n) の呼び出し位置が、ret: ラベルの直後に移動しました。以前は dump("walk", n) の後に呼び出されていました。 目的: walkexpr 関数は、式の抽象構文木を走査し、変換を行う過程で ninit を含むノードを構築します。ullmancalc を ret: ラベルの直後に移動することで、ノード n の ninit が完全に構築され、最終的な形になった後にUllman数が計算されることが保証されます。これにより、ninit の存在がUllman数の計算に正確に反映され、コード生成の順序付けがより正確になります。

test/fixedbugs/bug406.go の新規追加

このテストケースは、true && a.equal() のような式で、a.equal() が matrix 型のメソッド呼び出しであり、これが ninit を生成する可能性があることを示しています。このテストは、修正が正しく機能し、&& 演算子のショートサーキット評価が保証されることを検証します。もしバグが修正されていなければ、a.equal() が不必要に評価され、テストが失敗する可能性があります。

関連リンク

• GitHubコミットページ: https://github.com/golang/go/commit/5efd5624cc5b22f50d2739b0f1dbce32402206cb
• Go CL (Change List): https://golang.org/cl/5606061

参考にした情報源リンク

• コミットメッセージと差分
• Go言語の公式ドキュメント（論理演算子、コンパイラに関する一般的な情報）
• コンパイラ最適化に関する一般的な知識（Ullman数、式の再順序付け）
• Goコンパイラのソースコード（src/cmd/gc/subr.c, src/cmd/gc/walk.c）
• Go Issue 2821 (コミットメッセージに記載されているが、公開されているGoのIssueトラッカーでは見つからなかったため、内部的なIssueであると推測される)