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

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

このコミットは、Goコンパイラのsrc/cmd/gc/walk.cファイルに対する変更です。walk.cは、Goコンパイラのバックエンドの一部であり、抽象構文木（AST）を走査（walk）し、コード生成の準備をする役割を担っています。具体的には、式の評価順序の最適化や、一時変数の導入など、コードの変換処理を行います。

コミット

commit 2bba3a610d7d4cb42391b724408c694ff9ebb791
Author: Ken Thompson <ken@golang.org>
Date:   Wed Jun 11 12:25:44 2008 -0700

    reorder1 - function first instead of last
    
    SVN=122160

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

https://github.com/golang/go/commit/2bba3a610d7d4cb42391b724408c694ff9ebb791

元コミット内容

--- a/src/cmd/gc/walk.c
+++ b/src/cmd/gc/walk.c
@@ -1224,6 +1224,7 @@ convas(Node *n)
 	if(n->op != OAS)
 		fatal("convas: not as %O", n->op);
 
+	ullmancalc(n);
 	l = n->left;
 	r = n->right;
 	if(l == N || r == N)
@@ -1321,7 +1322,7 @@ loop1:
 		if(c == 0 || t == 1)
 			return n;
 		if(c > 1) {
-\t\t\tyyerror("reorder1: too many funcation calls evaluating parameters");
+\t\t\tyyerror("reorder1: too many function calls evaluating parameters");
 			return n;
 		}
 		goto pass2;
@@ -1337,21 +1338,18 @@ loop1:
 
 pass2:
 	l = listfirst(&save, &n);
-\tf = N;\t// isolated function call
-\tr = N;\t// rest of them
+\tr = N;\t// rest
+\tf = N;\t// fncall
 
 loop2:
 	if(l == N) {
-\t\tif(r == N || f == N)
-\t\t\tfatal("reorder1 not nil 1");
 		r = nod(OLIST, f, r);
-\t\treturn rev(r);
+\t\tr = rev(r);
+\t\treturn r;
 	}
-\tif(l->ullman >= UINF) {
-\t\tif(f != N)
-\t\t\tfatal("reorder1 not nil 2");
+\tif(l->ullman >= UINF)
 		f = l;
-\t} else
+\telse
 	if(r == N)
 		r = l;
 	else

変更の背景

このコミットの背景には、Goコンパイラが式の評価順序を最適化する際の戦略変更があります。特に、関数呼び出しを含む複雑な式において、評価の効率性やレジスタ割り当ての最適化を目指しています。

従来の評価戦略では、関数呼び出しが式の最後に評価されるような順序になっていた可能性があります。しかし、関数呼び出しは副作用を持つことが多く、またレジスタを多く消費する可能性があるため、これを早期に評価することで、コンパイラがより効率的なコードを生成できる場合があります。

コミットメッセージにある「reorder1 - function first instead of last」は、この評価順序の変更、すなわち関数呼び出しを他のオペランドよりも先に評価する新しい戦略を明確に示しています。また、コード内のullmancalcの導入とullmanプロパティの利用は、この評価順序決定にセシ・ウルマン数（Sethi-Ullman numbers）のような概念を適用していることを示唆しています。

前提知識の解説

このコミットを理解するためには、以下の概念が重要です。

  1. Goコンパイラの構造: Goコンパイラは、ソースコードを解析し、抽象構文木（AST）を構築し、中間表現に変換し、最終的に機械語を生成します。src/cmd/gc/walk.cは、ASTを走査し、コード生成に適した形に変換する「ウォーク（walk）」フェーズを担当します。このフェーズでは、式の最適化、一時変数の導入、関数呼び出しの処理などが行われます。

  2. 抽象構文木（AST）: プログラムのソースコードを木構造で表現したものです。各ノードは、変数、演算子、関数呼び出しなどのプログラム要素に対応します。コンパイラはASTを走査して、コードの意味を理解し、変換を行います。

  3. 式の評価順序: プログラミング言語において、複雑な式（例: a + b * c()）がどのように評価されるかという順序です。言語仕様によって厳密に定義されている場合もあれば、コンパイラが最適化のために順序を変更できる場合もあります。関数呼び出しは副作用を持つ可能性があるため、その評価順序は特に重要です。

  4. セシ・ウルマン数（Sethi-Ullman numbers）: コンパイラ最適化の分野で用いられる概念で、式ツリーの各ノードに対して計算される値です。この値は、そのノードに対応する部分式を評価するために必要な最小レジスタ数を示します。セシ・ウルマンアルゴリズムは、レジスタ割り当てを最適化し、コード生成の効率を高めるために使用されます。

    • 葉ノード（定数や変数）のウルマン数は1です。
    • 二項演算子ノードの場合、左右の子ノードのウルマン数を比較し、大きい方に1を加えた値がそのノードのウルマン数となります。ただし、左右の子ノードのウルマン数が異なる場合は、大きい方のウルマン数がそのままそのノードのウルマン数となります。
    • 関数呼び出しのような複雑な操作は、非常に高い（あるいは無限大に近い）ウルマン数を持つと見なされることがあります。これは、それらが多くのレジスタを消費したり、予測不能な副作用を持ったりするためです。

  5. Node構造体: GoコンパイラのASTにおけるノードを表すデータ構造です。この構造体には、ノードの種類（op）、左右の子ノード（left, right）、そしてこのコミットで重要となるullmanプロパティなどが含まれます。

技術的詳細

このコミットの主要な変更点は、Goコンパイラが式の評価順序を決定するロジック、特にreorder1という処理における関数呼び出しの扱いを変更したことです。

  1. ullmancalc(n)の導入: convas関数（おそらく「convert assignment」の略で、代入式の変換を行う関数）の冒頭にullmancalc(n)が追加されました。これは、ノードnに対してウルマン数を計算する関数であると推測されます。この計算により、各ノードの複雑度やレジスタ要求に関する情報がn->ullmanプロパティに格納されます。この情報は、後続の評価順序決定ロジックで利用されます。

  2. reorder1ロジックの変更: reorder1は、おそらく式の評価順序を再編成する処理の一部です。このコミットでは、pass2およびloop2内のロジックが大幅に変更されています。

    • 変数fとrの役割:
      • fは「fncall」（関数呼び出し）を表すノードとして再定義されました。以前は「isolated function call」とコメントされていました。
      • rは「rest」（残りの部分）を表すノードとして再定義されました。以前は「rest of them」とコメントされていました。
    • 評価順序の優先: loop2内の条件if(l->ullman >= UINF)が重要です。UINFはおそらく「Ullman Infinity」を意味し、非常に高いウルマン数を持つノード（すなわち、関数呼び出しや非常に複雑な式）を識別するために使用されます。 この条件が真の場合、つまり現在のノードlが関数呼び出しのような特別なノードである場合、そのノードlはf（関数呼び出しノード）として扱われます。それ以外の場合、lはr（残りの部分）に追加されます。 これにより、listfirst(&save, &n)で取得されたノードのリストを走査する際に、関数呼び出しノードが優先的にfに割り当てられ、最終的にr = nod(OLIST, f, r);によって、関数呼び出しがリストの先頭（または他の要素よりも前）に配置されるようになります。これは「function first instead of last」というコミットメッセージの意図と完全に一致します。

  3. エラーハンドリングの緩和: fatal("reorder1 not nil 1")やfatal("reorder1 not nil 2")といった厳密なエラーチェックが削除されました。これは、新しい評価順序ロジックが、以前は致命的なエラーを引き起こしていた特定のエッジケースをより適切に処理できるようになったことを示唆しています。

  4. typoの修正: yyerror("reorder1: too many funcation calls evaluating parameters");がyyerror("reorder1: too many function calls evaluating parameters");に修正されました。これは機能的な変更ではありませんが、コード品質の向上に貢献します。

この変更により、Goコンパイラは、関数呼び出しを含む式を評価する際に、より予測可能で効率的なコードを生成できるようになります。特に、レジスタの利用効率が向上したり、副作用の発生タイミングがより制御しやすくなったりする可能性があります。

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

  • src/cmd/gc/walk.c
    • convas関数内でullmancalc(n);が追加された行。
    • loop1内のyyerrorメッセージのtypo修正。
    • pass2およびloop2ブロック内のfとrの初期化、およびloop2内の条件分岐ロジックの変更。特にif(l->ullman >= UINF)の条件と、それに続くf = l;の割り当て。
    • fatal呼び出しの削除。

コアとなるコードの解説

// src/cmd/gc/walk.c
// convas関数の一部
@@ -1224,6 +1224,7 @@ convas(Node *n)
 	if(n->op != OAS)
 		fatal("convas: not as %O", n->op);
 
+	ullmancalc(n); // ノードnのウルマン数を計算し、n->ullmanに格納
 	l = n->left;
 	r = n->right;
 	if(l == N || r == N)

convas関数は代入式を処理する際に、まず代入対象のノードnに対してullmancalcを呼び出し、そのウルマン数を計算します。これにより、このノードの複雑度やレジスタ要求に関するメタデータが準備されます。

// src/cmd/gc/walk.c
// loop1内のエラーメッセージ修正
@@ -1321,7 +1322,7 @@ loop1:
 		if(c == 0 || t == 1)
 			return n;
 		if(c > 1) {
-\t\t\tyyerror("reorder1: too many funcation calls evaluating parameters");
+\t\t\tyyerror("reorder1: too many function calls evaluating parameters"); // typo修正
 			return n;
 		}
 		goto pass2;

これは単なるtypo修正であり、機能的な変更はありません。

// src/cmd/gc/walk.c
// pass2およびloop2ブロック
@@ -1337,21 +1338,18 @@ loop1:
 
 pass2:
 	l = listfirst(&save, &n); // 保存されたノードリストの最初の要素を取得
-\tf = N;\t// isolated function call
-\tr = N;\t// rest of them
+\tr = N;\t// rest // 残りのノード
+\tf = N;\t// fncall // 関数呼び出しノード
 
 loop2:
 	if(l == N) { // リストの終端に達した場合
-\t\tif(r == N || f == N)
-\t\t\tfatal("reorder1 not nil 1"); // 削除されたエラーチェック
 		r = nod(OLIST, f, r); // 関数呼び出しノードfをリストrの先頭に追加
-\t\treturn rev(r); // 削除されたrev呼び出し
+\t\tr = rev(r); // リストrを反転
+\t\treturn r; // 反転されたリストを返す
 	}
-\tif(l->ullman >= UINF) { // 現在のノードlのウルマン数がUINF以上の場合（関数呼び出しなど）
-\t\tif(f != N)
-\t\t\tfatal("reorder1 not nil 2"); // 削除されたエラーチェック
+\tif(l->ullman >= UINF) // 現在のノードlのウルマン数がUINF以上の場合（関数呼び出しなど）
 		f = l; // lを関数呼び出しノードfとして扱う
-\t} else
+\telse // それ以外の場合
 	if(r == N) // rがまだ空の場合
 		r = l; // lをrの最初の要素とする
 	else

この部分が評価順序変更の核心です。

  • fとrの役割が明確化され、fが関数呼び出し、rがそれ以外の部分を表すようになりました。
  • loop2では、ノードリストを走査し、各ノードlのullmanプロパティをチェックします。
  • l->ullman >= UINFという条件は、lが関数呼び出しのように特別な処理が必要なノードであるかを判断します。
  • この条件が真の場合、lはfに割り当てられ、関数呼び出しとしてマークされます。
  • 最終的に、r = nod(OLIST, f, r);によって、関数呼び出しノードfが、それ以外のノードを含むリストrの先頭に配置されます。これにより、「関数が最初に評価される」という新しい順序が実現されます。
  • 以前存在したfatalエラーチェックが削除されたのは、この新しいロジックがより堅牢になり、以前はエラーと見なされていた状況を適切に処理できるようになったためと考えられます。
  • return rev(r);の変更は、リストの反転処理がより効率的になったか、あるいはロジックの変更に伴い不要になった部分が整理されたことを示唆しています。

関連リンク

  • Go言語のコンパイラに関する公式ドキュメントや設計資料（当時のものがあれば）
  • コンパイラ最適化、特にセシ・ウルマンアルゴリズムに関する一般的な情報

参考にした情報源リンク

  • Goコンパイラのソースコード（特にsrc/cmd/gc/ディレクトリ）
  • コンパイラ設計に関する教科書やオンラインリソース（例: Dragon Book - Compilers: Principles, Techniques, and Tools）
  • セシ・ウルマンアルゴリズムに関する学術論文や解説記事
  • Go言語の初期のコミット履歴や開発者間の議論（もし公開されていれば）
  • Web検索結果: "Go compiler reorder1 ullman numbers" (ただし、直接的な関連は薄かった)
    • Goコンパイラの命令再配置、構造体フィールドの再配置、一般的な最適化に関する情報。
    • Ullman numbersがコンパイラ設計（レジスタ割り当て、命令スケジューリング）で使われる一般的な概念であること。