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

このコミットは、Goコンパイラ（cmd/gc）におけるnilチェック除去の最適化処理に存在した無限ループのバグを修正するものです。具体的には、src/cmd/gc/popt.c内のnilwalkfwd関数が、特定のコードパターン、特に後方ジャンプを含むループ構造を処理する際に無限ループに陥る問題を解決します。この修正により、コンパイラの安定性と堅牢性が向上し、特定の有効なGoプログラムがコンパイル時にハングアップするのを防ぎます。

コミット

commit daf9308066a71802ed723ba96459afe2558c62d9
Author: Russ Cox <rsc@golang.org>
Date:   Tue May 27 23:58:49 2014 -0400

    cmd/gc: fix infinite loop in nil check removal
    
    Fixes #8076.
    
    LGTM=iant
    R=golang-codereviews, iant
    CC=golang-codereviews
    https://golang.org/cl/93610043

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

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

元コミット内容

cmd/gc: fix infinite loop in nil check removal

Fixes #8076.

LGTM=iant
R=golang-codereviews, iant
CC=golang-codereviews
https://golang.org/cl/93610043

変更の背景

Goコンパイラは、生成されるバイナリのパフォーマンスを向上させるために様々な最適化を行います。その一つに「nilチェック除去」があります。これは、あるポインタがnilでないことが既に保証されているコードパスにおいて、冗長なnilポインタチェックを削除する最適化です。これにより、実行時のオーバーヘッドが削減されます。

しかし、このnilチェック除去のロジック、特にsrc/cmd/gc/popt.c内のnilwalkfwd関数にバグが存在しました。この関数は、コードの制御フローを順方向に辿りながらnilポインタの安全性を分析します。問題は、コード内に後方ジャンプ（goto文などによるループ）が存在する場合に発生しました。nilwalkfwdが後方ジャンプに遭遇すると、既に処理した命令を再度処理しようとし、結果として無限ループに陥り、コンパイルプロセスがハングアップするという現象が発生していました。

この問題はGo issue #8076として報告され、コンパイラが特定の有効なGoプログラムをコンパイルできないという重大なバグとして認識されました。このコミットは、この無限ループを解消し、コンパイラの安定性を確保するために導入されました。

前提知識の解説

Goコンパイラ (`cmd/gc`)

cmd/gcは、Go言語の公式コンパイラです。Goのソースコードを機械語に変換する役割を担っています。コンパイルプロセスには、構文解析、型チェック、中間表現の生成、最適化、コード生成など、複数のフェーズが含まれます。

nilチェック除去 (Nil Check Removal)

nilチェック除去は、コンパイラ最適化の一種です。Go言語では、nilポインタのデリファレンス（nilポインタが指すメモリへのアクセス）はランタイムパニックを引き起こします。コンパイラは、このようなパニックを防ぐために、ポインタのデリファレンス前にnilチェックを挿入します。しかし、ある時点でポインタがnilでないことが確定している場合（例：if x != nil { ... *x ... }のようなコード）、その後の*xに対するnilチェックは冗長になります。nilチェック除去最適化は、このような冗長なチェックを特定し、削除することで、生成されるコードのサイズを小さくし、実行速度を向上させます。

データフロー解析 (Data Flow Analysis)

データフロー解析は、プログラムの実行中に変数の値やプロパティがどのように変化するかを分析するコンパイラ技術です。nilチェック除去のような最適化は、このデータフロー解析の結果に基づいて行われます。nilwalkfwd関数は、順方向データフロー解析の一種を実行し、特定のプログラムポイントにおけるポインタのnilness（nilであるか、nilでないか）の情報を伝播させます。

プログラムカウンタと命令の流れ

コンパイラがコードを分析する際、内部的には命令のシーケンスとして扱います。Prog構造体は、コンパイラの内部表現における単一の命令（または命令ブロック）を表すと考えられます。NilFlow構造体は、この命令の流れにおけるnilチェック関連のデータフロー情報を保持します。uniqs関数は、おそらく命令のユニークなリストを生成するか、または命令間の接続を管理するユーティリティ関数です。

後方ジャンプとループ

プログラムの制御フローには、順次実行、条件分岐、ループ（繰り返し）があります。ループは、特定の条件が満たされるまで一連の命令を繰り返し実行する構造です。forループやgoto文を使ったループなど、様々な形で実装されます。コンパイラがデータフロー解析を行う際、後方ジャンプ（現在の命令から、よりアドレスの小さい過去の命令へジャンプすること）は、ループの存在を示唆します。データフロー解析がループ内で無限に繰り返されないように、特別な処理が必要です。

技術的詳細

このバグは、src/cmd/gc/popt.c内のnilwalkfwd関数に起因していました。この関数は、NilFlow構造体のリストを順方向に辿りながら、nilチェック除去のためのデータフロー解析を行います。NilFlow構造体は、Prog（プログラム命令）へのポインタと、その命令に関連するnilフロー情報を含んでいます。

元のコードでは、for(r = (NilFlow*)uniqs(&rcheck->f); r != nil; r = (NilFlow*)uniqs(&r->f))というループで命令を順次処理していました。このループは、rがnilになるまで、またはreturn文で明示的に終了するまで続きます。しかし、uniqs(&r->f)が返す次のNilFlowポインタが、既に処理済みのNilFlowポインタと同じか、それよりも「前」のメモリ位置を指す場合（これは後方ジャンプ、つまりループの存在を示唆します）、nilwalkfwdは同じ命令シーケンスを繰り返し処理しようとし、無限ループに陥りました。

この問題は、test/fixedbugs/issue8076.goで示されているような、nilデリファレンスと無限ループが組み合わされた特定のコードパターンで顕在化しました。

func main() {
	_ = *(*int)(nil) // nilデリファレンス
L:
	_ = 0
	goto L // 無限ループ
}

このようなコードは、_ = *(*int)(nil)でパニックを引き起こすはずですが、コンパイラのバグにより、パニック発生前にコンパイルがハングアップしていました。

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

変更はsrc/cmd/gc/popt.cファイルに集中しています。

--- a/src/cmd/gc/popt.c
+++ b/src/cmd/gc/popt.c
@@ -956,7 +956,7 @@ nilwalkback(NilFlow *rcheck)
 static void
 nilwalkfwd(NilFlow *rcheck)
 {
-	NilFlow *r;
+	NilFlow *r, *last;
 	Prog *p;
 	ProgInfo info;
 	
@@ -967,6 +967,7 @@ nilwalkfwd(NilFlow *rcheck)
 	// avoid problems like:
 	//	_ = *x // should panic
 	//	for {} // no writes but infinite loop may be considered visible
+	last = nil;
 	for(r = (NilFlow*)uniqs(&rcheck->f); r != nil; r = (NilFlow*)uniqs(&r->f)) {
 		p = r->f.prog;
 		proginfo(&info, p);
@@ -989,5 +990,12 @@ nilwalkfwd(NilFlow *rcheck)
 		// Stop if memory write.
 		if((info.flags & RightWrite) && !regtyp(&p->to))
 			return;
+		// Stop if we jump backward.
+		// This test is valid because all the NilFlow* are pointers into
+		// a single contiguous array. We will need to add an explicit
+		// numbering when the code is converted to Go.
+		if(last != nil && r <= last)
+			return;
+		last = r;
 	}
 }

また、バグを再現し、修正を検証するためのテストケースがtest/fixedbugs/issue8076.goとして追加されました。

// compile

// Copyright 2014 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 8076. nilwalkfwd walked forward forever
// on the instruction loop following the dereference.

package main

func main() {
	_ = *(*int)(nil)
L:
	_ = 0
	goto L
}

コアとなるコードの解説

src/cmd/gc/popt.cのnilwalkfwd関数への変更は非常にシンプルですが、効果的です。

last変数の導入: NilFlow *last;という新しい変数が導入され、ループの各イテレーションで現在処理しているNilFlowポインタrの「直前の」値を保持するために使用されます。last = nil;で初期化されます。
後方ジャンプの検出: ループの内部に以下の新しい条件チェックが追加されました。
```
if(last != nil && r <= last)
    return;
```
この条件は、以下のことをチェックします。
- last != nil: lastが初期値のnilでないこと、つまり少なくとも1回はループが実行され、lastに有効なNilFlowポインタが設定されていること。
- r <= last: 現在のNilFlowポインタrが、直前のNilFlowポインタlastよりも「小さい」か「等しい」こと。ここで「小さい」とは、メモリ上のアドレスが前にあることを意味します。Goコンパイラの内部では、NilFlowオブジェクトが連続した配列に格納されているため、ポインタの比較（<=）によって命令の順序を判断できます。r <= lastが真である場合、それは後方ジャンプが発生し、既に処理した命令シーケンスに戻ったことを示唆します。
ループの終了: 後方ジャンプが検出された場合、return;によってnilwalkfwd関数が直ちに終了します。これにより、無限ループが回避されます。
lastの更新: ループの最後にlast = r;が追加され、次のイテレーションのために現在のrの値をlastに保存します。

この修正は、nilwalkfwdがデータフロー解析を行う際に、無限ループに陥る可能性のある後方ジャンプを検出し、その時点で解析を打ち切ることで、コンパイラのハングアップを防ぎます。コメントにあるように、このポインタ比較による検出方法は、NilFlowポインタが連続したメモリ領域に配置されているという前提に基づいています。将来的にGo言語でコードが書き直される際には、明示的な番号付けなどのより堅牢なメカニズムが必要になる可能性が示唆されています。

test/fixedbugs/issue8076.goは、このバグを再現するための最小限のテストケースです。_ = *(*int)(nil)でnilデリファレンスを発生させ、その直後にgoto Lによる無限ループを配置することで、nilwalkfwdが無限ループに陥る状況を意図的に作り出しています。このテストがコンパイル時にハングアップせず、期待通りにパニックを発生させることで、修正が正しく機能していることを検証します。

参考にした情報源リンク

Go issue #8076に関するWeb検索結果
Go CL 93610043のコンテンツ
Goコンパイラの最適化に関する一般的な知識
データフロー解析に関する一般的な知識
Go言語のnilポインタとパニックに関する知識

comemo