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

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

このコミットは、Goコンパイラの抽象構文木（AST）におけるOAS2RECVノードの厳密なツリープロパティの修正に関するものです。具体的には、typecheckおよびwalkフェーズにおいて、OAS2RECVからOAS2およびOSELRECV2への変換時に、ASTのノードが誤って複製され、ASTの厳密なツリー構造が破壊される問題に対処しています。この問題は、エスケープ解析（esc.c）やインライン化（inl.c）など、ASTのツリー構造に依存するコンパイラパスに影響を与えていました。

コミット

  • Author: Luuk van Dijk lvd@golang.org
  • Date: Mon Oct 22 10:01:14 2012 +0200
  • Commit Hash: e7f89fcb1cdd5fc41377108fcaad2363d4456b24

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

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

元コミット内容

cmd/gc: fix strict tree property for AST for OAS2RECV nodes.

in typecheck and walk, conversion from OAS2RECV to OAS2
and to OSELRECV2 duplicated the ->rlist->n to ->right
thereby destroying the strict tree-ness of the AST (up to
ONAMES) of course.  Several recursions in esc.c and inl.c
and probably elsewhere assume nodes of the tree aren't duplicated.
rather than defensively code around this, i'd rather assert
these cases away and fix their cause.

(this was tripped in 6741044)

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

変更の背景

このコミットは、Goコンパイラの内部的な問題、特にASTの構造の整合性に関するバグを修正するために行われました。コミットメッセージによると、OAS2RECVノード（チャネルからの2値受信代入、例: x, ok = <-c）がtypecheckおよびwalkフェーズでOAS2やOSELRECV2に変換される際に、ノードのポインタが誤って複製されていました。具体的には、->rlist->nが->rightに複製されることで、ASTの「厳密なツリー性（strict tree-ness）」が損なわれていました。

ASTが厳密なツリー構造を持つことは、コンパイラの様々な最適化パスや解析パス（例: エスケープ解析 esc.c、インライン化 inl.c）が正しく機能するための前提条件です。ノードの複製は、これらのパスが同じノードを複数回処理したり、予期しない状態に遭遇したりする原因となり、コンパイラの誤動作やクラッシュにつながる可能性があります。コミットメッセージでは、この問題が以前のコミット（6741044）でトリガーされたと述べられており、その根本原因を修正する必要がありました。

前提知識の解説

GoコンパイラのAST (Abstract Syntax Tree)

Goコンパイラは、ソースコードを解析する際に、その構造を抽象構文木（AST）として表現します。ASTは、プログラムの構造を木構造で表現したもので、各ノードはプログラムの要素（変数、関数呼び出し、演算子など）に対応します。コンパイラは、このASTを様々なフェーズ（型チェック、最適化、コード生成など）で処理していきます。

OAS2RECV、ORECV、OSELRECV2

これらはGoコンパイラの内部的な操作コード（Op）であり、ASTノードの種類を示します。

  • ORECV: 単純なチャネル受信操作（例: <-c）を表します。
  • OAS2RECV: チャネルからの2値受信代入（例: x, ok = <-c）を表します。これは、受信値と成功/失敗を示すブール値の両方を受け取るパターンです。
  • OAS2: 一般的な2値代入操作を表します。
  • OSELRECV2: selectステートメント内で使用される、チャネルからの2値受信操作を表します。selectブロック内のcase文でx, ok = <-cのような形式がこれに該当します。

ASTの「厳密なツリー性（strict tree-ness）」

ASTが「厳密なツリー性」を持つとは、各ノードがAST内で一意であり、複数の親ノードから参照されることがない状態を指します。つまり、ASTはグラフではなく、純粋な木構造であるべきだという原則です。この原則が破られると、コンパイラの内部処理でノードが重複して処理されたり、状態管理が複雑になったり、予期せぬ副作用が発生したりする可能性があります。

typecheckとwalkフェーズ

Goコンパイラの主要なフェーズの一部です。

  • typecheck: ASTの各ノードに対して型チェックを行い、型の整合性を検証します。このフェーズで、一部のASTノードはより具体的な操作コードに変換されることがあります。
  • walk: ASTを走査し、様々な変換や最適化を行います。例えば、一部のASTノードはより低レベルの表現に変換されたり、最適化のために構造が変更されたりします。

esc.cとinl.c

これらはGoコンパイラのソースファイルの一部であり、それぞれ以下の機能に関連しています。

  • esc.c: エスケープ解析（Escape Analysis）を担当します。変数がヒープにエスケープするかどうかを判断し、スタックに割り当てられるべき変数を特定することで、ガベージコレクションの負荷を軽減します。エスケープ解析は、変数の参照関係をAST上で追跡するため、ASTの厳密なツリー構造に強く依存します。
  • inl.c: インライン化（Inlining）を担当します。小さな関数呼び出しを呼び出し元に直接展開することで、関数呼び出しのオーバーヘッドを削減し、パフォーマンスを向上させます。インライン化もASTの構造を操作するため、ASTの整合性が重要です。

技術的詳細

このコミットが修正している問題は、OAS2RECVノードがtypecheckおよびwalkフェーズで処理される際の、ASTノードの不適切なポインタ操作に起因します。

元のコードでは、x, ok = <-cのようなOAS2RECVノードが、typecheckフェーズでOSELRECV2（select文内での2値受信）やOAS2（一般的な2値代入）に変換される際に、n->rlist->n（受信操作の右辺のノード）がn->rightに直接代入されていました。

// 変更前 (typecheck.c)
case ORECV:
    n->op = OAS2RECV;
    n->right = n->rlist->n; // ここでノードが複製される問題
    goto common;

そして、select.cのtypecheckselect関数内でも同様のパターンが見られました。

// 変更前 (select.c)
case OAS2RECV:
    // ...
    n->right = n->rlist->n; // ここでもノードが複製される問題
    break;

このn->right = n->rlist->n;という代入は、n->rlist->nが指す既存のノードをn->rightにも指させることになります。これにより、同じASTノードが複数の親ノード（この場合はn->rlistとn）から参照される状態が発生し、ASTの「厳密なツリー性」が破壊されます。

ASTの厳密なツリー性が破壊されると、esc.cやinl.cのような、ASTを再帰的に走査して処理を行うコンパイラパスが問題に直面します。これらのパスは、各ノードが一度だけ処理されること、またはツリー構造が予測可能であることを前提としています。ノードが複製されていると、例えばエスケープ解析が同じ変数を複数回処理して誤った結果を出したり、インライン化が不正なASTを生成したりする可能性があります。

コミットメッセージにある「rather than defensively code around this, i'd rather assert these cases away and fix their cause.」という記述は、この問題に対して、各コンパイラパスで防御的なコードを追加して対処するのではなく、根本原因であるASTのツリー構造の破壊を修正するという方針を示しています。

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

このコミットでは、主にsrc/cmd/gc/select.cとsrc/cmd/gc/typecheck.cの2つのファイルが変更されています。

src/cmd/gc/select.c

--- a/src/cmd/gc/select.c
+++ b/src/cmd/gc/select.c
@@ -62,7 +62,7 @@ typecheckselect(Node *sel)
 
 			case OAS2RECV:
 				// convert x, ok = <-c into OSELRECV2(x, <-c) with ntest=ok
-				if(n->right->op != ORECV) {
+				if(n->rlist->n->op != ORECV) {
 					yyerror("select assignment must have receive on right hand side");
 					break;
 				}
@@ -70,6 +70,7 @@ typecheckselect(Node *sel)
 				n->left = n->list->n;
 				n->ntest = n->list->next->n;
 				n->right = n->rlist->n;
+				n->rlist = nil;
 				break;
 
 			case ORECV:
@@ -146,7 +147,7 @@ walkselect(Node *sel)
 				
 				a = nod(OAS2, N, N);
 				a->list = n->list;
-				a->rlist = n->rlist;
+				a->rlist = list1(n->right);
 				n = a;
 				typecheck(&n, Etop);
 				break;

src/cmd/gc/typecheck.c

--- a/src/cmd/gc/typecheck.c
+++ b/src/cmd/gc/typecheck.c
@@ -2574,7 +2574,6 @@ typecheckas2(Node *n)
 			goto common;
 		case ORECV:
 			n->op = OAS2RECV;
-			n->right = n->rlist->n;
 			goto common;
 		case ODOTTYPE:
 			n->op = OAS2DOTTYPE;

コアとなるコードの解説

src/cmd/gc/select.cの変更

  1. typecheckselect関数内の変更:

    • if(n->right->op != ORECV)からif(n->rlist->n->op != ORECV)への変更: これは、OAS2RECVノードの右辺がORECV（受信操作）であることを確認するチェックです。変更前はn->rightを見ていましたが、n->rightは変換後に設定されるため、変換前の元の受信ノードはn->rlist->nにあります。この修正により、チェックがより正確なASTノードに対して行われるようになります。
    • n->rlist = nil;の追加: n->right = n->rlist->n;によってn->rlist->nがn->rightに「移動」された後、元のn->rlistは不要になります。この行を追加することで、n->rlistをnilに設定し、古い参照をクリアすることで、ASTのツリー構造の整合性を保ちます。これにより、同じノードが複数のパスから参照されることを防ぎます。

  2. walkselect関数内の変更:

    • a->rlist = n->rlist;からa->rlist = list1(n->right);への変更: walkselect関数は、select文のcase内のOAS2RECVノードをOAS2ノードに変換する処理を行います。変更前は、新しいOAS2ノードのrlistに古いOAS2RECVノードのrlistを直接代入していました。しかし、typecheckselectでn->rlistがnilに設定されるため、この代入は正しくありません。 新しいコードでは、a->rlist = list1(n->right);としています。これは、n->rightが既に変換後の受信ノードを指しているため、そのノードを新しいOAS2ノードのrlistのリストとして設定することで、ASTの整合性を維持します。list1は単一のノードからなるリストを作成するヘルパー関数です。

src/cmd/gc/typecheck.cの変更

  • n->right = n->rlist->n;の削除: typecheckas2関数は、2値代入（OAS2）の型チェックを行う関数です。ORECV（受信操作）が右辺にある場合にOAS2RECVに変換するロジックが含まれています。変更前は、ここでn->right = n->rlist->n;という行があり、これがASTノードの複製を引き起こしていました。この行を削除することで、OAS2RECVノードが作成される際に、n->rlist->nがn->rightに重複して参照されることを防ぎ、ASTの厳密なツリー性を維持します。この修正により、OAS2RECVノードの構造がよりクリーンになり、後続のコンパイラパスでの問題が回避されます。

これらの変更は、GoコンパイラのAST内部表現の整合性を保つために重要であり、特にエスケープ解析やインライン化といった、ASTの正確な構造に依存する最適化パスの信頼性を向上させます。

関連リンク

参考にした情報源リンク