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

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

このコミットは、Goコンパイラの初期バージョンである6g（AMD64アーキテクチャ向け）のコードジェネレーション部分におけるバグ修正と堅牢性向上を目的としています。具体的には、関数呼び出しの結果が非アドレス可能（nonaddressable）な場合や、複雑な式（Ullman数が無限大に近いもの）が関わるコード生成において発生しうるエラーを検出し、修正するための変更が加えられています。

コミット

commit 6b8bd3556ad77141729d836999d93fdd1923e3b2
Author: Ken Thompson <ken@golang.org>
Date:   Fri Jun 6 16:49:35 2008 -0700

    nonaddressable = functioncall
    code gen error
    
    SVN=121541

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

https://github.com/golang/go/commit/6b8bd3556ad77141729d836999d93fdd1923e3b2

元コミット内容

nonaddressable = functioncall
code gen error

SVN=121541

変更の背景

このコミットは、Go言語の初期開発段階、特にコンパイラのコード生成フェーズにおける特定のバグに対処するために行われました。コミットメッセージにある「nonaddressable = functioncall」と「code gen error」は、関数呼び出しの結果が直接アドレス指定できない（メモリ上の特定の位置に直接書き込めない）場合に、コンパイラが誤ったコードを生成してしまう問題があったことを示唆しています。

コンパイラは、プログラムの各部分（式、変数、関数呼び出しなど）を評価し、その結果をレジスタやメモリに配置する際に、効率的かつ正確なコードを生成する必要があります。しかし、関数呼び出しのような複雑な操作は、その結果が一時的なものであったり、直接メモリにマッピングできない性質を持つことがあります。このような「非アドレス可能」な値を扱う際に、コンパイラが適切な中間処理（例えば、一時レジスタへの格納）を行わないと、不正な機械語が生成され、プログラムがクラッシュしたり、予期せぬ動作をしたりする原因となります。

このコミットは、このような状況を検出し、必要に応じて一時レジスタを使用するなどの適切なコード生成パスを導入することで、コンパイラの堅牢性と正確性を向上させることを目的としています。

前提知識の解説

Goコンパイラ (6g)

このコミットは2008年のものであり、Go言語がまだ初期段階にあった頃のものです。6gは、当時のGoコンパイラ群の一つで、AMD64（x86-64）アーキテクチャ向けのコンパイラを指します。Goコンパイラは、Go言語のソースコードを機械語に変換する役割を担っており、その過程で構文解析、型チェック、最適化、コード生成などのフェーズを経ます。

Ullman数 (Ullman Number)

Ullman数は、コンパイラ最適化の分野で用いられる概念で、特定の式を評価するために必要な最小レジスタ数を表します。これは、式の複雑さや、その評価順序を決定する際に重要な指標となります。

  • 定義: 式の各ノード（演算子やオペランド）に対して計算される数値で、そのノード以下のサブツリーを評価するために必要なレジスタの最小数を示します。
  • 計算方法:
    • 葉ノード（定数、変数など）のUllman数は1です。
    • 二項演算子（例: a + b）の場合、左右のオペランドのUllman数を比較し、大きい方に1を加えたものがそのノードのUllman数となります。ただし、左右のUllman数が同じ場合は、大きい方に2を加えます（これは、一方のオペランドを評価してレジスタに格納し、もう一方を評価する際に、そのレジスタを一時的に保持する必要があるためです）。
  • UINF (Ullman Infinity): このコミットで登場するUINFは、Ullman数が「無限大」または非常に大きいことを示す特別な値です。これは通常、関数呼び出しや、副作用を持つ複雑な式など、レジスタ割り当ての通常のルールでは扱いにくい、あるいはレジスタに収まらない可能性のある式に対して割り当てられます。UINFを持つ式は、評価に特別な注意が必要であり、一時的なメモリ領域やスタックを使用する必要があることを示唆します。

アドレス可能性 (Addressability)

コンパイラの文脈における「アドレス可能性」とは、ある値や式の結果が、メモリ上の特定のアドレスに直接対応しているかどうかを指します。

  • アドレス可能 (addable): 変数、配列の要素、構造体のフィールドなど、メモリ上の固定された位置に存在する値はアドレス可能です。これらの値は、そのアドレスを介して直接読み書きできます。
  • 非アドレス可能 (nonaddressable): 関数呼び出しの結果、一時的な計算結果、レジスタにのみ存在する値などは非アドレス可能です。これらの値は、直接メモリ上のアドレスを持たないか、そのアドレスが一時的で不安定なものです。非アドレス可能な値をメモリに格納したり、別の場所に移動させたりするには、一時レジスタやスタックを経由するなどの追加のコード生成が必要になります。

このコミットは、特に「非アドレス可能」な関数呼び出しの結果を適切に処理するためのロジックを追加しています。

技術的詳細

このコミットは、Goコンパイラのコード生成フェーズにおけるsrc/cmd/6g/cgen.cとsrc/cmd/6g/gen.cの2つのファイルに修正を加えています。主な変更点は、Ullman数とアドレス可能性の概念を利用して、特定のコード生成エラーを検出し、回避するためのロジックの追加です。

src/cmd/6g/cgen.cの変更

cgen関数は、Go言語の抽象構文木（AST）のノードnを評価し、その結果をresノードに格納するための機械語を生成する主要な関数です。

  1. Ullman数に基づくエラーチェックの追加:

    if(n->ullman >= UINF) {
    if(n->op == OINDREG)
        fatal("cgen: this is going to misscompile");
    if(res->ullman >= UINF)
        fatal("cgen: fun both sides");
}
    • n->ullman >= UINF: 評価対象の式nが関数呼び出しや複雑な式（Ullman数が無限大）である場合。
    • n->op == OINDREG: nが間接レジスタ操作（例: *R1のようなポインタ参照）である場合。この組み合わせは、コンパイラが正しくコンパイルできない状況（"misscompile"）を引き起こすため、致命的エラーとされます。これは、関数呼び出しの結果が間接参照されるような複雑なケースで、レジスタ割り当てや値のライフタイム管理が困難になることを示唆しています。
    • res->ullman >= UINF: 結果を格納するresノードも関数呼び出しや複雑な式である場合。これは「fun both sides」（両側が関数）というエラーメッセージで示され、両側が複雑な式であるような代入や操作は、コンパイラが安全に処理できないと判断されます。

  2. 非アドレス可能な結果ノードの処理改善:

    if(!res->addable) {
    if(n->ullman > res->ullman) {
        regalloc(&n1, nr->type, res);
        cgen(n, &n1);
        cgen(&n1, res);
        regfree(&n1);
        return;
    }
    igen(res, &n1, N);
    cgen(n, &n1);
    regfree(&n1);
}
    • !res->addable: 結果を格納するresノードが直接アドレス可能でない場合（例: 関数呼び出しの結果を直接別の関数呼び出しの結果に代入しようとするなど）。
    • n->ullman > res->ullman: さらに、評価対象の式nのUllman数がresのUllman数よりも大きい場合（つまり、nの方がresよりも複雑な式である場合）。
      • この条件が真の場合、新しいコードパスが導入されます。これは、一時的なレジスタn1を割り当て、まずnの評価結果をn1に格納し（cgen(n, &n1)）、次にn1の内容をresに格納する（cgen(&n1, res)）という二段階の処理を行います。これにより、非アドレス可能なresへの複雑な式の代入が安全に行えるようになります。これは、nの評価がresの評価よりも多くのレジスタを必要とする場合に、resの評価がnの評価を妨げないようにするための戦略です。
    • 上記の条件が偽の場合（n->ullman <= res->ullman）、既存のigenとcgenの組み合わせが使用されます。igenは、非アドレス可能なresを一時的なレジスタn1に「実体化」し、その後nの結果をn1に格納するという流れです。

src/cmd/6g/gen.cの変更

gen.cは、より具体的なコード生成ルーチン、特に代入操作（cgen_as）や比較代入操作（cgen_asop）を扱います。

  1. cgen_asop (比較代入操作) の変更:

    if(nr->ullman >= UINF && nl->ullman >= UINF) {
    fatal("cgen_asop both sides call");
}
// ...
if(nr->ullman > nl->ullman) {
    fatal("gcgen_asopen");
}
    • nr->ullman >= UINF && nl->ullman >= UINF: 比較代入の両側のオペランド（nlとnr）が共に複雑な式（関数呼び出しなど）である場合、致命的エラーとされます。これは、両側の評価が同時に行われるとレジスタ競合や評価順序の問題が発生する可能性があるためです。
    • nr->ullman > nl->ullman: 右側のオペランドnrのUllman数が左側のオペランドnlのUllman数よりも大きい場合、致命的エラーとされます。これは、代入操作において、通常は左側のオペランド（代入先）が右側のオペランド（代入元）よりも評価が単純であるか、少なくとも同等であるべきという前提があるためと考えられます。右側がより複雑な場合、評価順序やレジスタ割り当てに問題が生じる可能性があります。

  2. cgen_as (代入操作) の変更:

    if(nr->ullman >= UINF && nl->ullman >= UINF) {
    fatal("cgen_as both sides call");
}
    • nr->ullman >= UINF && nl->ullman >= UINF: cgen_asopと同様に、代入の両側のオペランドが共に複雑な式である場合、致命的エラーとされます。

これらの変更は、コンパイラが特定の複雑な式や非アドレス可能な値の組み合わせを処理する際に、誤ったコードを生成するのを防ぐためのガードレールとして機能します。特に、Ullman数を利用して式の複雑さを判断し、必要に応じて一時レジスタを導入したり、安全でないパターンを検出してエラーを報告したりすることで、コンパイラの安定性と信頼性を向上させています。

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

src/cmd/6g/cgen.c

--- a/src/cmd/6g/cgen.c
+++ b/src/cmd/6g/cgen.c
@@ -22,6 +22,13 @@ cgen(Node *n, Node *res)
 	if(res == N || res->type == T)
 		fatal("cgen: res nil");
 
+	if(n->ullman >= UINF) {
+		if(n->op == OINDREG)
+			fatal("cgen: this is going to misscompile");
+		if(res->ullman >= UINF)
+			fatal("cgen: fun both sides");
+	}
+
 	lno = dynlineno;
 	if(n->op != ONAME)
 		dynlineno = n->lineno;	// for diagnostics
@@ -32,6 +39,14 @@ cgen(Node *n, Node *res)
 	}
 
 	if(!res->addable) {
+		if(n->ullman > res->ullman) {
+			regalloc(&n1, nr->type, res);
+			cgen(n, &n1);
+			cgen(&n1, res);
+			regfree(&n1);
+			return;
+		}
+
 		igen(res, &n1, N);
 		cgen(n, &n1);
 		regfree(&n1);

src/cmd/6g/gen.c

--- a/src/cmd/6g/gen.c
+++ b/src/cmd/6g/gen.c
@@ -688,10 +688,15 @@ cgen_asop(Node *nl, Node *nr, int op)
 	Node n1, n2;
 	int a;
 
-	// botch compare ullman numbers
-	// and use temp for functions
+	if(nr->ullman >= UINF && nl->ullman >= UINF) {
+		fatal("cgen_asop both sides call");
+	}
 
 	a = optoas(op, nl->type);
+	if(nr->ullman > nl->ullman) {
+		fatal("gcgen_asopen");
+	}
+
 	regalloc(&n1, nl->type, N);
 	if(nl->addable) {
 		cgen(nr, &n1);
@@ -815,5 +820,9 @@ cgen_as(Node *nl, Node *nr, int op)
 		nr->addable = 1;
 		ullmancalc(nr);
 	}\n+\n+\tif(nr->ullman >= UINF && nl->ullman >= UINF) {\n+\t\tfatal("cgen_as both sides call");\n+\t}\n 	cgen(nr, nl);
 }

コアとなるコードの解説

src/cmd/6g/cgen.c

  • Ullman数チェックの追加:
    • if(n->ullman >= UINF)ブロックは、評価対象の式nが非常に複雑な場合（関数呼び出しなど）に、特定の危険なパターンを検出します。
    • if(n->op == OINDREG): nが間接レジスタ操作（例: *reg）であり、かつUllman数がUINFである場合、コンパイラが正しくコードを生成できないと判断し、fatal("cgen: this is going to misscompile")でコンパイルを停止します。これは、関数呼び出しの結果が間接参照されるような状況で、レジスタ割り当てや値のライフタイム管理が非常に困難になるためです。
    • if(res->ullman >= UINF): nとresの両方がUINFを持つ場合、つまり「両側が関数呼び出し」のような状況では、fatal("cgen: fun both sides")でコンパイルを停止します。これは、このような複雑な代入や操作が安全に処理できないことを示します。
  • 非アドレス可能な結果ノードの処理ロジックの改善:
    • if(!res->addable)ブロックは、結果を格納するresノードが直接アドレス可能でない場合に実行されます。
    • if(n->ullman > res->ullman): この新しい条件は、評価対象の式nが結果ノードresよりも複雑である場合に、より安全なコード生成パスを選択します。
      • regalloc(&n1, nr->type, res);: 一時的なレジスタn1を割り当てます。nr->typeは、おそらくnの型を指すものと思われます。
      • cgen(n, &n1);: まず、複雑な式nの評価結果をこの一時レジスタn1に格納します。
      • cgen(&n1, res);: 次に、一時レジスタn1の内容を最終的な結果ノードresに格納します。
      • regfree(&n1);: 使用した一時レジスタを解放します。
      • この二段階の処理により、nの評価がresの評価に影響を与えず、非アドレス可能なresへの安全な値の転送が可能になります。これは、Ullman数の大小関係に基づいて、より複雑な式を先に評価し、その結果を一時的に保持することで、レジスタの競合や評価順序の問題を回避する戦略です。

src/cmd/6g/gen.c

  • cgen_asopおよびcgen_asにおけるUllman数チェック:
    • if(nr->ullman >= UINF && nl->ullman >= UINF): cgen_asop（比較代入）とcgen_as（代入）の両方で、左右のオペランド（nlとnr）が共にUINFを持つ場合（つまり、両側が関数呼び出しのような複雑な式である場合）、fatal("cgen_asop both sides call")またはfatal("cgen_as both sides call")でコンパイルを停止します。これは、このような状況でのレジスタ割り当てや評価順序の複雑さを避けるためのガードです。
    • if(nr->ullman > nl->ullman): cgen_asopにおいて、右側のオペランドnrのUllman数が左側のオペランドnlのUllman数よりも大きい場合、fatal("gcgen_asopen")でコンパイルを停止します。これは、代入操作において、代入元が代入先よりも複雑であるという予期せぬ状況を検出し、不正なコード生成を防ぐためのものです。通常、代入先は変数など単純なものであることが期待されます。

これらの変更は、Goコンパイラの初期段階におけるコード生成のロジックを強化し、特定の複雑な式や非アドレス可能な値の組み合わせが原因で発生する可能性のあるコンパイルエラーや不正なコード生成を防ぐための重要なステップでした。Ullman数という概念を積極的に利用することで、式の複雑さを定量的に評価し、それに基づいて安全なコード生成パスを選択または危険なパターンを早期に検出しています。

関連リンク

参考にした情報源リンク

  • Ullman Number (Compiler Optimization): https://en.wikipedia.org/wiki/Ullman_number
  • Compiler Design - Code Generation: https://www.geeksforgeeks.org/compiler-design-code-generation/
  • Go Compiler Internals (General Concepts): https://go.dev/doc/articles/go_compiler_internals.html (より現代のGoコンパイラに関する情報ですが、基本的な概念理解に役立ちます)
  • Go言語の初期の設計に関する議論やドキュメント（当時のメーリングリストやデザインドキュメントなどがあれば、より詳細な背景が得られる可能性がありますが、今回は一般的な情報源に留めます。）
  • src/cmd/6gに関する情報（Goの古いコンパイラに関する情報は限られていますが、Goのソースコード自体が最も信頼できる情報源です。）
  • addableの概念に関するコンパイラ設計の一般的な情報。# [インデックス 107] ファイルの概要

このコミットは、Goコンパイラの初期バージョンである6g（AMD64アーキテクチャ向け）のコードジェネレーション部分におけるバグ修正と堅牢性向上を目的としています。具体的には、関数呼び出しの結果が非アドレス可能（nonaddressable）な場合や、複雑な式（Ullman数が無限大に近いもの）が関わるコード生成において発生しうるエラーを検出し、修正するための変更が加えられています。

コミット

commit 6b8bd3556ad77141729d836999d93fdd1923e3b2
Author: Ken Thompson <ken@golang.org>
Date:   Fri Jun 6 16:49:35 2008 -0700

    nonaddressable = functioncall
    code gen error
    
    SVN=121541

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

https://github.com/golang/go/commit/6b8bd3556ad77141729d836999d93fdd1923e3b2

元コミット内容

nonaddressable = functioncall
code gen error

SVN=121541

変更の背景

このコミットは、Go言語の初期開発段階、特にコンパイラのコード生成フェーズにおける特定のバグに対処するために行われました。コミットメッセージにある「nonaddressable = functioncall」と「code gen error」は、関数呼び出しの結果が直接アドレス指定できない（メモリ上の特定の位置に直接書き込めない）場合に、コンパイラが誤ったコードを生成してしまう問題があったことを示唆しています。

コンパイラは、プログラムの各部分（式、変数、関数呼び出しなど）を評価し、その結果をレジスタやメモリに配置する際に、効率的かつ正確なコードを生成する必要があります。しかし、関数呼び出しのような複雑な操作は、その結果が一時的なものであったり、直接メモリにマッピングできない性質を持つことがあります。このような「非アドレス可能」な値を扱う際に、コンパイラが適切な中間処理（例えば、一時レジスタへの格納）を行わないと、不正な機械語が生成され、プログラムがクラッシュしたり、予期せぬ動作をしたりする原因となります。

このコミットは、このような状況を検出し、必要に応じて一時レジスタを使用するなどの適切なコード生成パスを導入することで、コンパイラの堅牢性と正確性を向上させることを目的としています。

前提知識の解説

Goコンパイラ (6g)

このコミットは2008年のものであり、Go言語がまだ初期段階にあった頃のものです。6gは、当時のGoコンパイラ群の一つで、AMD64（x86-64）アーキテクチャ向けのコンパイラを指します。Goコンパイラは、Go言語のソースコードを機械語に変換する役割を担っており、その過程で構文解析、型チェック、最適化、コード生成などのフェーズを経ます。

Ullman数 (Ullman Number)

Ullman数は、コンパイラ最適化の分野で用いられる概念で、特定の式を評価するために必要な最小レジスタ数を表します。これは、式の複雑さや、その評価順序を決定する際に重要な指標となります。

  • 定義: 式の各ノード（演算子やオペランド）に対して計算される数値で、そのノード以下のサブツリーを評価するために必要なレジスタの最小数を示します。
  • 計算方法:
    • 葉ノード（定数、変数など）のUllman数は1です。
    • 二項演算子（例: a + b）の場合、左右のオペランドのUllman数を比較し、大きい方に1を加えたものがそのノードのUllman数となります。ただし、左右のUllman数が同じ場合は、大きい方に2を加えます（これは、一方のオペランドを評価してレジスタに格納し、もう一方を評価する際に、そのレジスタを一時的に保持する必要があるためです）。
  • UINF (Ullman Infinity): このコミットで登場するUINFは、Ullman数が「無限大」または非常に大きいことを示す特別な値です。これは通常、関数呼び出しや、副作用を持つ複雑な式など、レジスタ割り当ての通常のルールでは扱いにくい、あるいはレジスタに収まらない可能性のある式に対して割り当てられます。UINFを持つ式は、評価に特別な注意が必要であり、一時的なメモリ領域やスタックを使用する必要があることを示唆します。

アドレス可能性 (Addressability)

コンパイラの文脈における「アドレス可能性」とは、ある値や式の結果が、メモリ上の特定のアドレスに直接対応しているかどうかを指します。

  • アドレス可能 (addable): 変数、配列の要素、構造体のフィールドなど、メモリ上の固定された位置に存在する値はアドレス可能です。これらの値は、そのアドレスを介して直接読み書きできます。
  • 非アドレス可能 (nonaddressable): 関数呼び出しの結果、一時的な計算結果、レジスタにのみ存在する値などは非アドレス可能です。これらの値は、直接メモリ上のアドレスを持たないか、そのアドレスが一時的で不安定なものです。非アドレス可能な値をメモリに格納したり、別の場所に移動させたりするには、一時レジスタやスタックを経由するなどの追加のコード生成が必要になります。

このコミットは、特に「非アドレス可能」な関数呼び出しの結果を適切に処理するためのロジックを追加しています。

技術的詳細

このコミットは、Goコンパイラのコード生成フェーズにおけるsrc/cmd/6g/cgen.cとsrc/cmd/6g/gen.cの2つのファイルに修正を加えています。主な変更点は、Ullman数とアドレス可能性の概念を利用して、特定のコード生成エラーを検出し、回避するためのロジックの追加です。

src/cmd/6g/cgen.cの変更

cgen関数は、Go言語の抽象構文木（AST）のノードnを評価し、その結果をresノードに格納するための機械語を生成する主要な関数です。

  1. Ullman数に基づくエラーチェックの追加:

    if(n->ullman >= UINF) {
    if(n->op == OINDREG)
        fatal("cgen: this is going to misscompile");
    if(res->ullman >= UINF)
        fatal("cgen: fun both sides");
}
    • n->ullman >= UINF: 評価対象の式nが関数呼び出しや複雑な式（Ullman数が無限大）である場合。
    • n->op == OINDREG: nが間接レジスタ操作（例: *R1のようなポインタ参照）である場合。この組み合わせは、コンパイラが正しくコンパイルできない状況（"misscompile"）を引き起こすため、致命的エラーとされます。これは、関数呼び出しの結果が間接参照されるような複雑なケースで、レジスタ割り当てや値のライフタイム管理が困難になることを示唆しています。
    • res->ullman >= UINF: 結果を格納するresノードも関数呼び出しや複雑な式である場合。これは「fun both sides」（両側が関数）というエラーメッセージで示され、両側が複雑な式であるような代入や操作は、コンパイラが安全に処理できないと判断されます。

  2. 非アドレス可能な結果ノードの処理改善:

    if(!res->addable) {
    if(n->ullman > res->ullman) {
        regalloc(&n1, nr->type, res);
        cgen(n, &n1);
        cgen(&n1, res);
        regfree(&n1);
        return;
    }
    igen(res, &n1, N);
    cgen(n, &n1);
    regfree(&n1);
}
    • !res->addable: 結果を格納するresノードが直接アドレス可能でない場合（例: 関数呼び出しの結果を直接別の関数呼び出しの結果に代入しようとするなど）。
    • n->ullman > res->ullman: さらに、評価対象の式nのUllman数がresのUllman数よりも大きい場合（つまり、nの方がresよりも複雑な式である場合）。
      • この条件が真の場合、新しいコードパスが導入されます。これは、一時的なレジスタn1を割り当て、まずnの評価結果をn1に格納し（cgen(n, &n1)）、次にn1の内容をresに格納する（cgen(&n1, res)）という二段階の処理を行います。これにより、非アドレス可能なresへの複雑な式の代入が安全に行えるようになります。これは、nの評価がresの評価よりも多くのレジスタを必要とする場合に、resの評価がnの評価を妨げないようにするための戦略です。
    • 上記の条件が偽の場合（n->ullman <= res->ullman）、既存のigenとcgenの組み合わせが使用されます。igenは、非アドレス可能なresを一時的なレジスタn1に「実体化」し、その後nの結果をn1に格納するという流れです。

src/cmd/6g/gen.cの変更

gen.cは、より具体的なコード生成ルーチン、特に代入操作（cgen_as）や比較代入操作（cgen_asop）を扱います。

  1. cgen_asop (比較代入操作) の変更:

    if(nr->ullman >= UINF && nl->ullman >= UINF) {
    fatal("cgen_asop both sides call");
}
// ...
if(nr->ullman > nl->ullman) {
    fatal("gcgen_asopen");
}
    • nr->ullman >= UINF && nl->ullman >= UINF: 比較代入の両側のオペランド（nlとnr）が共に複雑な式（関数呼び出しなど）である場合、致命的エラーとされます。これは、両側の評価が同時に行われるとレジスタ競合や評価順序の問題が発生する可能性があるためです。
    • nr->ullman > nl->ullman: 右側のオペランドnrのUllman数が左側のオペランドnlのUllman数よりも大きい場合、致命的エラーとされます。これは、代入操作において、通常は左側のオペランド（代入先）が右側のオペランド（代入元）よりも評価が単純であるか、少なくとも同等であるべきという前提があるためと考えられます。右側がより複雑な場合、評価順序やレジスタ割り当てに問題が生じる可能性があります。

  2. cgen_as (代入操作) の変更:

    if(nr->ullman >= UINF && nl->ullman >= UINF) {
    fatal("cgen_as both sides call");
}
    • nr->ullman >= UINF && nl->ullman >= UINF: cgen_asopと同様に、代入の両側のオペランドが共に複雑な式である場合、致命的エラーとされます。

これらの変更は、コンパイラが特定の複雑な式や非アドレス可能な値の組み合わせを処理する際に、誤ったコードを生成するのを防ぐためのガードレールとして機能します。特に、Ullman数を利用して式の複雑さを判断し、必要に応じて一時レジスタを導入したり、安全でないパターンを検出してエラーを報告したりすることで、コンパイラの堅牢性と正確性を向上させています。

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

src/cmd/6g/cgen.c

--- a/src/cmd/6g/cgen.c
+++ b/src/cmd/6g/cgen.c
@@ -22,6 +22,13 @@ cgen(Node *n, Node *res)
 	if(res == N || res->type == T)
 		fatal("cgen: res nil");
 
+	if(n->ullman >= UINF) {
+		if(n->op == OINDREG)
+			fatal("cgen: this is going to misscompile");
+		if(res->ullman >= UINF)
+			fatal("cgen: fun both sides");
+	}
+
 	lno = dynlineno;
 	if(n->op != ONAME)
 		dynlineno = n->lineno;	// for diagnostics
@@ -32,6 +39,14 @@ cgen(Node *n, Node *res)
 	}
 
 	if(!res->addable) {
+		if(n->ullman > res->ullman) {
+			regalloc(&n1, nr->type, res);
+			cgen(n, &n1);
+			cgen(&n1, res);
+			regfree(&n1);
+			return;
+		}
+
 		igen(res, &n1, N);
 		cgen(n, &n1);
 		regfree(&n1);

src/cmd/6g/gen.c

--- a/src/cmd/6g/gen.c
+++ b/src/cmd/6g/gen.c
@@ -688,10 +688,15 @@ cgen_asop(Node *nl, Node *nr, int op)
 	Node n1, n2;
 	int a;
 
-	// botch compare ullman numbers
-	// and use temp for functions
+	if(nr->ullman >= UINF && nl->ullman >= UINF) {
+		fatal("cgen_asop both sides call");
+	}
 
 	a = optoas(op, nl->type);
+	if(nr->ullman > nl->ullman) {
+		fatal("gcgen_asopen");
+	}
+
 	regalloc(&n1, nl->type, N);
 	if(nl->addable) {
 		cgen(nr, &n1);
@@ -815,5 +820,9 @@ cgen_as(Node *nl, Node *nr, int op)
 		nr->addable = 1;
 		ullmancalc(nr);
 	}\n+\n+\tif(nr->ullman >= UINF && nl->ullman >= UINF) {\n+\t\tfatal("cgen_as both sides call");\n+\t}\n 	cgen(nr, nl);
 }

コアとなるコードの解説

src/cmd/6g/cgen.c

  • Ullman数チェックの追加:
    • if(n->ullman >= UINF)ブロックは、評価対象の式nが非常に複雑な場合（関数呼び出しなど）に、特定の危険なパターンを検出します。
    • if(n->op == OINDREG): nが間接レジスタ操作（例: *reg）であり、かつUllman数がUINFである場合、コンパイラが正しくコードを生成できないと判断し、fatal("cgen: this is going to misscompile")でコンパイルを停止します。これは、関数呼び出しの結果が間接参照されるような状況で、レジスタ割り当てや値のライフタイム管理が非常に困難になるためです。
    • if(res->ullman >= UINF): nとresの両方がUINFを持つ場合、つまり「両側が関数呼び出し」のような状況では、fatal("cgen: fun both sides")でコンパイルを停止します。これは、このような複雑な代入や操作が安全に処理できないことを示します。
  • 非アドレス可能な結果ノードの処理ロジックの改善:
    • if(!res->addable)ブロックは、結果を格納するresノードが直接アドレス可能でない場合に実行されます。
    • if(n->ullman > res->ullman): この新しい条件は、評価対象の式nが結果ノードresよりも複雑である場合に、より安全なコード生成パスを選択します。
      • regalloc(&n1, nr->type, res);: 一時的なレジスタn1を割り当てます。nr->typeは、おそらくnの型を指すものと思われます。
      • cgen(n, &n1);: まず、複雑な式nの評価結果をこの一時レジスタn1に格納します。
      • cgen(&n1, res);: 次に、一時レジスタn1の内容を最終的な結果ノードresに格納します。
      • regfree(&n1);: 使用した一時レジスタを解放します。
      • この二段階の処理により、nの評価がresの評価に影響を与えず、非アドレス可能なresへの安全な値の転送が可能になります。これは、Ullman数の大小関係に基づいて、より複雑な式を先に評価し、その結果を一時的に保持することで、レジスタの競合や評価順序の問題を回避する戦略です。

src/cmd/6g/gen.c

  • cgen_asopおよびcgen_asにおけるUllman数チェック:
    • if(nr->ullman >= UINF && nl->ullman >= UINF): cgen_asop（比較代入）とcgen_as（代入）の両方で、左右のオペランド（nlとnr）が共にUINFを持つ場合（つまり、両側が関数呼び出しのような複雑な式である場合）、fatal("cgen_asop both sides call")またはfatal("cgen_as both sides call")でコンパイルを停止します。これは、このような状況でのレジスタ割り当てや評価順序の複雑さを避けるためのガードです。
    • if(nr->ullman > nl->ullman): cgen_asopにおいて、右側のオペランドnrのUllman数が左側のオペランドnlのUllman数よりも大きい場合、fatal("gcgen_asopen")でコンパイルを停止します。これは、代入操作において、代入元が代入先よりも複雑であるという予期せぬ状況を検出し、不正なコード生成を防ぐためのものです。通常、代入先は変数など単純なものであることが期待されます。

これらの変更は、Goコンパイラの初期段階におけるコード生成のロジックを強化し、特定の複雑な式や非アドレス可能な値の組み合わせが原因で発生する可能性のあるコンパイルエラーや不正なコード生成を防ぐための重要なステップでした。Ullman数という概念を積極的に利用することで、式の複雑さを定量的に評価し、それに基づいて安全なコード生成パスを選択または危険なパターンを早期に検出しています。

関連リンク

参考にした情報源リンク

  • Ullman Number (Compiler Optimization): https://en.wikipedia.org/wiki/Ullman_number
  • Compiler Design - Code Generation: https://www.geeksforgeeks.org/compiler-design-code-generation/
  • Go Compiler Internals (General Concepts): https://go.dev/doc/articles/go_compiler_internals.html (より現代のGoコンパイラに関する情報ですが、基本的な概念理解に役立ちます)
  • Go言語の初期の設計に関する議論やドキュメント（当時のメーリングリストやデザインドキュメントなどがあれば、より詳細な背景が得られる可能性がありますが、今回は一般的な情報源に留めます。）
  • src/cmd/6gに関する情報（Goの古いコンパイラに関する情報は限られていますが、Goのソースコード自体が最も信頼できる情報源です。）
  • addableの概念に関するコンパイラ設計の一般的な情報。