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

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

このコミットは、Goコンパイラのコード生成部分、特に複合代入演算子(op=、例: +=, -=, *= など)の処理を改善し、除算(/=)と剰余(%=)演算子における既存のバグを修正するものです。変更は主にsrc/cmd/6g/gen.csrc/cmd/6g/gg.hの2つのファイルにわたります。

コミット

commit ef61a4cb1ec9ba332ee2d5a788c509d9ae851f19
Author: Ken Thompson <ken@golang.org>
Date:   Thu Jun 12 14:21:09 2008 -0700

    better version of op=
    fixed bugs in /= and %/
    
    SVN=122493

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

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

元コミット内容

better version of op=
fixed bugs in /= and %/

SVN=122493

変更の背景

このコミットは、Go言語の初期のコンパイラ(6g、x86-64アーキテクチャ向け)におけるコード生成の品質と正確性を向上させることを目的としています。特に、a op= bのような複合代入演算子(例: x += yz /= w)の処理に焦点を当てています。

以前の実装では、これらの演算子、特に除算(/=)と剰余(%=)において、正しくないコードが生成されるバグが存在していました。これは、オペランドの評価順序やレジスタ割り当ての最適化が不十分であったことに起因すると考えられます。コンパイラは、ソースコードを機械語に変換する際に、式の評価順序を最適化し、レジスタを効率的に使用する必要があります。このコミットは、Ullman数に基づく評価順序の改善と、より堅牢なレジスタ管理によって、これらの問題を解決しようとしています。

前提知識の解説

  • Goコンパイラ (6g): このコミットが対象としているのは、Go言語の初期のコンパイラの一つである6gです。これは、x86-64アーキテクチャ(64ビットIntel/AMDプロセッサ)向けのGoコードをコンパイルするためのツールでした。Goコンパイラは、フロントエンド(構文解析、意味解析)とバックエンド(コード生成、最適化)に分かれています。この変更はバックエンドのコード生成部分に該当します。
  • AST (Abstract Syntax Tree): コンパイラはソースコードを解析し、抽象構文木(AST)と呼ばれるツリー構造に変換します。ASTの各ノードは、変数、演算子、関数呼び出しなどのプログラム要素を表します。
  • Node構造体: Goコンパイラ内部では、ASTの各要素がNode構造体として表現されます。n->leftn->rightは、二項演算子の場合に左右のオペランドのノードを指します。
  • cgen (Code Generation): cgen関数は、ASTノードを受け取り、それに対応する機械語命令を生成する役割を担います。
  • igen (Address Generation): igen関数は、変数のアドレスを計算し、レジスタにロードするなどの処理を行います。
  • regalloc / regfree (Register Allocation/Deallocation): regallocは、計算結果を一時的に保持するために利用可能なCPUレジスタを割り当てます。regfreeは、使用済みのレジスタを解放します。レジスタはCPUが直接アクセスできる高速なメモリであり、その効率的な利用は生成されるコードの性能に直結します。
  • gins (Generate Instruction): ginsは、指定されたオペレーション(例: 加算、乗算)に対応する機械語命令を生成します。
  • gmove (Generate Move Instruction): gmoveは、ある場所(レジスタ、メモリ)から別の場所へデータを移動する機械語命令を生成します。
  • Ullman数 (Ullman Number): Ullman数は、コンパイラの最適化において、式の評価順序を決定するために使用されるヒューリスティックな値です。ツリー構造の各ノードに対して計算され、そのノードを評価するために必要なレジスタの最小数を示します。Ullman数が大きいサブツリーは、より多くのレジスタを必要とするため、先に評価することでレジスタの競合を減らし、効率的なコードを生成できる可能性があります。

技術的詳細

このコミットの核心は、src/cmd/6g/gen.c内のcgen_asop関数の変更にあります。この関数は、a op= b形式の複合代入演算子(例: x += yp *= q)のコード生成を担当します。

変更点:

  1. 関数シグネチャの変更:

    • 変更前: void cgen_asop(Node *nl, Node *nr, int op)
    • 変更後: void cgen_asop(Node *n) 変更前は左辺(nl)、右辺(nr)、演算子タイプ(op)を直接引数として受け取っていましたが、変更後は単一のNode *nを受け取るようになりました。このnは複合代入演算子全体のASTノードを表し、そのleftフィールドが左辺、rightフィールドが右辺、etypeフィールドが実際の演算子(例: OADDODIV)を保持します。これにより、関数のインターフェースがより統一され、AST構造との整合性が高まりました。
  2. Ullman数に基づく評価順序の最適化: 最も重要な変更は、右辺(nr)と左辺(nl)のUllman数を比較し、評価順序を動的に決定するロジックが導入されたことです。

    • 変更前:
      if(nr->ullman > nl->ullman) {
          fatal("gcgen_asopen");
      }
      
      このコードは、右辺のUllman数が左辺より大きい場合にfatalエラーを発生させていました。これは、コンパイラがそのようなケースを適切に処理できないか、特定の評価順序を前提としていたことを示唆しています。特に、右辺が複雑な式である場合に問題が発生しやすかったと考えられます。
    • 変更後:
      if(nr->ullman > nl->ullman) {
          // 右辺が左辺より複雑な場合、右辺を先に評価
          regalloc(&n2, nl->type, N); // nrの評価結果を保持するレジスタを割り当て
          cgen(nr, &n2);              // nrのコードを生成し、結果をn2に格納
          igen(nl, &n1, N);           // nlのアドレスをn1に格納
      } else {
          // 左辺が右辺より複雑、または同等の場合、左辺のアドレスを先に生成
          igen(nl, &n1, N);           // nlのアドレスをn1に格納
          regalloc(&n2, nl->type, N); // nrの評価結果を保持するレジスタを割り当て
          cgen(nr, &n2);              // nrのコードを生成し、結果をn2に格納
      }
      
      この新しいロジックは、Ullman数に基づいて、より複雑なオペランドを先に評価するようにレジスタ割り当てとコード生成の順序を調整します。これにより、レジスタの競合を最小限に抑え、より効率的で正しいコードが生成されるようになります。特に、除算や剰余のような特定のレジスタを必要とする演算において、この評価順序の最適化はバグの修正に貢献します。
  3. 汎用的な複合代入処理: 新しいコードでは、一時的なNode n3を作成し、これに元の演算子(n->etype)と、評価済みの左辺(n1)と右辺(n2)を割り当てています。

    n3 = *n;
    n3.left = &n1;
    n3.right = &n2;
    n3.op = n->etype; // 元の演算子(例: OADD, ODIV)
    
    regalloc(&n4, nr->type, N); // 演算結果を保持するレジスタを割り当て
    cgen(&n3, &n4);             // n3(二項演算)のコードを生成し、結果をn4に格納
    gmove(&n4, &n1);            // n4の結果をnlのアドレス(n1)に移動
    

    このアプローチにより、複合代入演算子を一般的な二項演算として扱い、その結果を左辺のメモリ位置に格納するという、より汎用的で堅牢なコード生成パスが実現されます。これにより、特定の演算子(/=%=)に特有のバグが修正されたと考えられます。

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

src/cmd/6g/gen.c

--- a/src/cmd/6g/gen.c
+++ b/src/cmd/6g/gen.c
@@ -275,7 +275,7 @@ loop:
 		break;
 
 	case OASOP:
-		cgen_asop(n->left, n->right, n->etype);
+		cgen_asop(n);
 		break;
 
 	case OAS:
@@ -683,40 +683,40 @@ cgen_ret(Node *n)\n }\n \n void
-cgen_asop(Node *nl, Node *nr, int op)\n+\tNode n1, n2, n3, n4;\n+\tNode *nl, *nr;\n+\n+\tnl = n->left;\n+\tnr = n->right;\n \n \tif(nr->ullman >= UINF && nl->ullman >= UINF) {\n \t\tfatal(\"cgen_asop both sides call\");\n \t}\n \n-// BOTCH make special case for DIVQ\n-\n-\ta = optoas(op, nl->type);\n-\tif(nl->addable) {\n-\t\tregalloc(&n2, nr->type, N);\n+\tif(nr->ullman > nl->ullman) {\n+\t\tregalloc(&n2, nl->type, N);\n+\t\tcgen(nr, &n2);\n+\t\tigen(nl, &n1, N);\n+\t} else {\n+\t\tigen(nl, &n1, N);\n+\t\tregalloc(&n2, nl->type, N);\
 \t\tcgen(nr, &n2);\n-\t\tregalloc(&n1, nl->type, N);\n-\t\tcgen(nl, &n1);\n-\t\tgins(a, &n2, &n1);\n-\t\tgmove(&n1, nl);\n-\t\tregfree(&n1);\n-\t\tregfree(&n2);\n-\t\treturn;\n \t}\n \n-\tif(nr->ullman > nl->ullman) {\n-\t\tfatal(\"gcgen_asopen\");\n-\t}\n+\tn3 = *n;\n+\tn3.left = &n1;\n+\tn3.right = &n2;\n+\tn3.op = n->etype;\n+\n+\tregalloc(&n4, nr->type, N);\n+\tcgen(&n3, &n4);\n+\tgmove(&n4, &n1);\
 \n-\tregalloc(&n1, nl->type, N);\n-\tigen(nl, &n2, N);\n-\tcgen(nr, &n1);\n-\tgins(a, &n1, &n2);\n \tregfree(&n1);\n \tregfree(&n2);\n+\tregfree(&n4);\n }\n \n void

src/cmd/6g/gg.h

--- a/src/cmd/6g/gg.h
+++ b/src/cmd/6g/gg.h
@@ -109,7 +109,7 @@ Node*\tlookdot(Node*, Node*, int);\n void\tinarggen(void);\n void\tagen_inter(Node*, Node*);\n void\tcgen_as(Node*, Node*, int);\n-void\tcgen_asop(Node*, Node*, int);\n+void\tcgen_asop(Node*);\n void\tcgen_ret(Node*);\n void\tcgen_call(Node*);\n void\tcgen_callmeth(Node*);\

コアとなるコードの解説

変更されたcgen_asop関数は、複合代入演算子(a op= b)のコード生成をより堅牢かつ効率的に行います。

  1. 引数の変更と内部でのノード抽出: 関数はNode *nという単一の引数を受け取ります。このnは、OASOP(複合代入演算子)タイプのASTノードです。関数内部で、n->leftから左辺(nl)を、n->rightから右辺(nr)を抽出します。

  2. Ullman数による評価順序の決定: if(nr->ullman > nl->ullman)の条件分岐が導入されました。

    • もし右辺nrのUllman数が左辺nlより大きい場合(つまり、nrの評価がより複雑で多くのレジスタを必要とする場合)、まずnrのコードを生成し、その結果を一時レジスタn2に格納します。その後、nlのアドレスをn1に格納します。
    • そうでない場合(nlnrより複雑、または同等の場合)、まずnlのアドレスをn1に格納し、その後nrのコードを生成して結果をn2に格納します。 このロジックにより、レジスタの競合を避け、効率的なコード生成が可能になります。
  3. 汎用的な二項演算の生成: Node n3が宣言され、元の複合代入ノードnの内容がコピーされます。そして、n3.leftn1(左辺のアドレス)、n3.rightn2(右辺の値)、n3.opに元の演算子タイプ(n->etype、例: OADDODIV)が設定されます。 これにより、n3nl op nrという通常の二項演算を表すノードとして機能します。

  4. 結果の格納: cgen(&n3, &n4)が呼び出され、n3で表される二項演算のコードが生成され、その結果が一時レジスタn4に格納されます。 最後に、gmove(&n4, &n1)によって、n4に格納された演算結果が、左辺nlのアドレスを指すn1に移動(ストア)されます。これにより、nlの値が更新されます。

  5. レジスタの解放: 使用した一時レジスタn1, n2, n4regfreeによって解放されます。

この一連の変更により、複合代入演算子のコード生成がより構造化され、特に除算や剰余のような複雑な演算において、オペランドの評価順序とレジスタ管理が最適化され、以前のバグが修正されました。

関連リンク

  • Go言語の初期のコンパイラに関する情報は、現在のGoのソースコードリポジトリのsrc/cmd/compile以下や、Goの歴史に関するドキュメントに散見されます。
  • Ullman数やコンパイラのコード生成に関する一般的な情報は、コンパイラ設計の教科書(例: Dragon Book)に詳しく記載されています。

参考にした情報源リンク

  • Go言語のソースコード (特にsrc/cmd/6gディレクトリの歴史的なコミット)
  • コンパイラ設計の原則に関する一般的な知識
  • Ullman数のアルゴリズムに関する情報