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

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

このコミットは、Goコンパイラの6g（x86-64アーキテクチャ向け）におけるコード生成の改善に焦点を当てています。特に、シフト演算と乗算のコード生成ロジックが大幅に強化され、除算の処理も洗練されています。これにより、生成されるアセンブリコードの効率性と正確性が向上しています。

コミット

commit f7753f16876cffe0e97b3890d8d3917bdc4a2246
Author: Ken Thompson <ken@golang.org>
Date:   Sat Jun 7 15:21:02 2008 -0700

    more code generation - mostly shift and multiply
    
    SVN=121585

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

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

元コミット内容

このコミットの元のメッセージは「more code generation - mostly shift and multiply」であり、シフト演算と乗算を中心としたコード生成のさらなる改善を示唆しています。これは、Goコンパイラの初期開発段階において、基本的な算術演算の効率的な機械語への変換が継続的に洗練されていたことを示しています。

変更の背景

Go言語のコンパイラは、ソースコードを効率的な機械語に変換する役割を担っています。特に、シフト演算（ビットシフト）や乗算、除算といった基本的な算術演算は、プログラムのパフォーマンスに直結するため、そのコード生成の最適化は非常に重要です。

このコミットが行われた2008年6月は、Go言語がまだ一般に公開される前の初期開発段階にあたります。当時のGoコンパイラ（gc、特にx86-64向けの6g）は、継続的に機能追加と最適化が行われていました。シフト演算や乗算は、CPUの特定のレジスタ（例: シフト量にはCLレジスタ、除算の被除数にはDX:AXレジスタペア）を使用するといったx86アーキテクチャ特有の制約や慣習があります。これらの制約を考慮しつつ、レジスタの競合を避け、効率的なアセンブリ命令を生成するためのロジックが不足していたり、改善の余地があったと考えられます。

このコミットは、これらの演算に対するコード生成の堅牢性と効率性を向上させ、より最適化されたバイナリを生成することを目的としています。特に、シフト演算のための専用関数cgen_shiftの導入は、この演算の複雑なレジスタ要件を適切に処理するための重要なステップです。

前提知識の解説

このコミットの変更内容を理解するためには、以下の前提知識が役立ちます。

  1. Goコンパイラ (gc/6g):

    • gcはGo言語の公式コンパイラです。
    • 6gは、gcコンパイラのうち、AMD64（x86-64）アーキテクチャをターゲットとする部分を指します。Goコンパイラは、ターゲットアーキテクチャごとに異なるバックエンドを持っています。
    • コンパイラの主要なフェーズには、字句解析、構文解析、意味解析、中間コード生成、最適化、コード生成などがあります。このコミットは主に「コード生成」フェーズに関わります。

  2. x86アセンブリ言語の基本:

    • レジスタ: CPU内部の高速な記憶領域。x86-64アーキテクチャには、汎用レジスタ（RAX, RBX, RCX, RDXなど）や特殊な用途のレジスタがあります。
      • AX / EAX / RAX: 算術演算の主要なアキュムレータ。
      • DX / EDX / RDX: 除算の剰余や乗算の上位ビット、あるいは除算の被除数の上位部分に使用される。
      • CX / ECX / RCX: ループカウンタや、シフト命令のシフト量（CLレジスタ、CXの下位8ビット）として使用される。
    • シフト命令:
      • SHL (Shift Left): 論理左シフト。
      • SHR (Shift Right): 論理右シフト（符号なし数に適用）。
      • SAR (Shift Arithmetic Right): 算術右シフト（符号あり数に適用、符号ビットを保持）。
      • これらの命令は、シフト量が即値でない場合、CLレジスタにシフト量をロードする必要があります。
    • 乗算命令:
      • IMUL (Integer Multiply): 符号付き乗算。オペランドのサイズに応じて、結果はAX、DX:AX、EDX:EAX、RDX:RAXなどに格納されます。
      • MUL (Unsigned Multiply): 符号なし乗算。
    • 除算命令:
      • IDIV (Integer Divide): 符号付き除算。被除数はDX:AX（またはEDX:EAX, RDX:RAX）に格納され、商はAX（またはEAX, RAX）、剰余はDX（またはEDX, RDX）に格納されます。
      • DIV (Unsigned Divide): 符号なし除算。
    • 符号拡張命令:
      • CWD (Convert Word to Doubleword): AXの内容をDX:AXに符号拡張。
      • CDQ (Convert Doubleword to Quadword): EAXの内容をEDX:EAXに符号拡張。
      • CQO (Convert Quadword to Octaword): RAXの内容をRDX:RAXに符号拡張。 これらは、除算命令の前に被除数を適切なレジスタペアに設定するために使用されます。

  3. Ullman Number (ウルマン数):

    • コンパイラ最適化において、式の評価に必要な最小レジスタ数を推定するための指標です。
    • 式の複雑さやレジスタの圧迫度を示すために使用され、レジスタ割り当てのヒューリスティックに利用されます。ウルマン数が低いほど、レジスタの競合が少なく、効率的なコード生成が期待できます。
    • このコミットでは、nl->ullman >= nr->ullmanのような比較が見られ、これは左右のオペランドのウルマン数を比較して、どちらを先に評価するか（レジスタを割り当てるか）を決定していることを示しています。

  4. レジスタ割り当て (Register Allocation):

    • プログラムの変数をCPUのレジスタに割り当てるプロセスです。レジスタはメモリよりもはるかに高速なため、適切にレジスタを使用することでプログラムの実行速度が向上します。
    • コンパイラは、レジスタの数が限られているため、どの変数をどのレジスタに割り当てるか、いつレジスタを解放するかを決定する必要があります。

技術的詳細

このコミットは、Goコンパイラのコード生成バックエンド（6g）における、特にシフト演算と乗算、そして除算の処理を改善しています。

  1. シフト演算の専用処理 (cgen_shiftの導入):

    • 以前はcgen.cの汎用的な非対称二項演算（abop）の一部として扱われていたOLSH（左シフト）とORSH（右シフト）が、cgen_shiftという新しい専用関数に分離されました。
    • これは、シフト演算がx86アーキテクチャにおいて特殊なレジスタ要件（シフト量が即値でない場合はCLレジスタを使用）を持つため、汎用的な処理では効率的または正確にコードを生成できない場合があるためです。
    • cgen_shift関数は、シフト量が定数であるか否かを判断し、定数の場合は直接シフト命令を生成します。
    • シフト量が変数である場合は、CLレジスタの現在の状態を保存し、シフト量をCLにロードし、シフト命令を実行した後にCLレジスタを元の状態に戻すという、複雑なレジスタ管理ロジックを含んでいます。これにより、CLレジスタの競合を安全に解決し、正しいコードを生成します。

  2. 非対称二項演算のレジスタ割り当ての改善 (cgen.cのabop):

    • OSUB（減算）などの非対称二項演算の処理において、レジスタ割り当てのロジックが変更されました。
    • 以前は、右オペランドがaddable（直接アドレス指定可能）な場合に特別な処理を行っていましたが、新しいロジックでは、左右のオペランドのウルマン数（ullman）を比較し、より複雑な式（ウルマン数が大きい方）を先に評価してレジスタを割り当てるようになりました。
    • これにより、レジスタの競合をより効果的に管理し、レジスタスピル（レジスタの内容をメモリに一時的に退避させること）を減らすことで、生成されるコードの効率が向上する可能性があります。

  3. 除算処理の洗練 (cgen_divの改善):

    • 除算はx86アーキテクチャにおいて、被除数がDX:AX（またはEDX:EAX, RDX:RAX）レジスタペアに格納されるという特殊な要件があります。
    • cgen_div関数は、AXレジスタとDXレジスタが既に他の用途で使用されている場合に、それらの内容を一時的に保存し、除算後に復元する「レジスタのクリーンアップ」ロジックをより堅牢にしました。
    • 符号付き除算の前に必要な符号拡張命令（CWD, CDQ, CQO）の生成において、以前はACDQという特定の命令を直接使用していましたが、optoas(OFOR, nl->type)という汎用的な方法に変更されました。これは、オペランドの型に基づいて適切な符号拡張命令を動的に選択することを可能にし、コードの柔軟性と保守性を向上させます。

  4. optoas関数の拡張と整理 (gsubr.c):

    • optoas関数は、Goの抽象構文木（AST）の演算子と型に基づいて、対応するx86アセンブリ命令のオペコードを返す役割を担っています。
    • シフト命令の追加: OLSHとORSHに対して、8ビット、16ビット、32ビット、64ビットの各整数型に対応するSHL、SHR、SAR命令のオペコードが追加されました。これにより、cgen_shift関数が適切なアセンブリ命令を生成できるようになります。
    • 乗算命令の整理: OMUL（乗算）のケースが整理され、符号付き・符号なしの区別なく、AIMULB, AIMULW, AIMULL, AIMULQといった符号付き整数乗算命令が使用されるようになりました。IMUL命令は、オペランドのサイズに応じて結果を適切に生成するため、多くの場合、符号付き・符号なしの区別なく使用できます。
    • OFOR命令の追加: OFORという新しい内部演算子（おそらく除算前の符号拡張を表す）が導入され、TINT16, TINT32, TINT64の各型に対して、それぞれACWD, ACDQ, ACQO（CWD, CDQ, CQOに対応）のオペコードがマッピングされました。これは、cgen_divにおける符号拡張の汎用化をサポートします。

  5. ヘッダファイルの更新 (gg.h):

    • 新しく追加されたcgen_shift関数のプロトタイプ宣言がgg.hに追加されました。

  6. ビルドスクリプトの微修正 (mksys.bash):

    • src/cmd/gc/mksys.bashにおいて、edコマンドの対象ファイルがfoop.6からsys.6に変更されています。これはビルドシステム内部のファイル名変更であり、コード生成ロジック自体には直接的な影響はありません。

これらの変更は、Goコンパイラがより効率的で正確な機械語を生成するための重要なステップであり、特にx86アーキテクチャの特性を考慮した低レベルの最適化が施されています。

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

このコミットにおける主要なコード変更は以下のファイルに集中しています。

  • src/cmd/6g/cgen.c:

    • cgen関数内で、OLSHとORSHの処理がcgen_shift関数に委譲されるように変更。
    • abop（非対称二項演算）のレジスタ割り当てロジックが、ウルマン数に基づいて改善。
    • agen（アドレス生成）関数における配列インデックスの乗算処理が、符号付き・符号なしに関わらずTINT64またはTUINT64で統一的に処理されるように変更。

  • src/cmd/6g/gen.c:

    • cgen_div関数内で、AXおよびDXレジスタのクリーンアップロジックが改善され、符号拡張命令の生成がACDQからoptoas(OFOR, ...)に変更。
    • cgen_shift関数が新規追加。この関数はシフト演算のコード生成を担当し、シフト量が定数か変数かによって異なる処理を行い、CLレジスタの管理も行う。

  • src/cmd/6g/gg.h:

    • cgen_shift関数のプロトタイプ宣言が追加。

  • src/cmd/6g/gsubr.c:

    • optoas関数内で、OLSHとORSHの各型に対するx86シフト命令（SHL, SHR, SAR）のマッピングが追加。
    • OMUL（乗算）の各型に対するx86乗算命令（AIMUL）のマッピングが整理。
    • OFOR（符号拡張）の各型に対するx86符号拡張命令（CWD, CDQ, CQO）のマッピングが追加。

コアとなるコードの解説

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

 // cgen関数内
 case OSUB:
-//	case OLSH: // 削除
-//	case ORSH: // 削除
 	a = optoas(n->op, nl->type);
 	goto abop;

 // ...

 case ODIV:
 	cgen_div(n->op, nl, nr, res);
 	break;
+case OLSH: // 追加
+case ORSH: // 追加
+	cgen_shift(n->op, nl, nr, res); // cgen_shiftを呼び出す
+	break;

cgen関数は、GoのASTノードをアセンブリコードに変換する主要な関数です。この変更により、左シフト(OLSH)と右シフト(ORSH)の処理が、汎用的な非対称二項演算のパスから削除され、新しく導入されたcgen_shift関数に処理が委譲されるようになりました。これは、シフト演算が持つx86アーキテクチャ特有の複雑なレジスタ要件（特にシフト量が変数である場合）を、専用の関数でより適切に処理するためです。

 // abop (asymmetric binary operation) のレジスタ割り当てロジック
 if(nl->ullman >= nr->ullman) { // 左右のオペランドのウルマン数を比較
 	regalloc(&n1, nl->type, res);
 	cgen(nl, &n1);
 	regalloc(&n2, nr->type, N);
 	cgen(nr, &n2);
 } else {
 	regalloc(&n2, nr->type, N);
 	cgen(nr, &n2);
 	regalloc(&n1, nl->type, res);
 	cgen(nl, &n1);
 }
 gins(a, &n2, &n1); // 命令生成
 gmove(&n1, res);
 regfree(&n1);
 regfree(&n2);

非対称二項演算（例: 減算）のコード生成において、左右のオペランドの評価順序とレジスタ割り当てのロジックが改善されました。以前は右オペランドがaddable（直接アドレス指定可能）かどうかに基づいていましたが、新しいロジックでは、各オペランドのウルマン数（ullman）を比較します。ウルマン数が大きい方（より複雑な式）を先に評価することで、レジスタの競合を減らし、レジスタスピルを最小限に抑えることを目指しています。これにより、より効率的なアセンブリコードが生成される可能性が高まります。

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

 // cgen_div関数内
 // AXレジスタのクリーンアップ
 if(rax && !samereg(res, &n1)) {
 	regalloc(&n3, types[TINT64], N);
 	gins(AMOVQ, &n1, &n3);
 	regfree(&n1);
 	regfree(&n2); // 追加
 	reg[D_AX] = 0;
 	cgen_div(op, nl, nr, res);
 	reg[D_AX] = rax;
 	gins(AMOVQ, &n3, &n1);
 	regfree(&n3);
 	return;
 }
 // DXレジスタのクリーンアップも同様に改善

cgen_div関数は除算のコード生成を担当します。x86アーキテクチャでは、除算の被除数はDX:AXレジスタペアに格納されるという特殊な要件があります。この変更では、AXレジスタやDXレジスタが既に他の用途で使用されている場合に、それらの内容を一時的に保存し、除算後に復元するロジックがより堅牢になりました。これにより、レジスタの競合による誤動作を防ぎ、正しい除算コードを生成します。

 // cgen_div関数内
 if(issigned[nl->type->etype])
-	gins(ACDQ, N, N); // 削除
+	gins(optoas(OFOR, nl->type), N, N); // 追加

符号付き除算の前に、被除数を符号拡張してDX:AXレジスタペアに設定する必要があります。以前はACDQ（Convert Doubleword to Quadword）という特定の命令を直接生成していましたが、この変更によりoptoas(OFOR, nl->type)という汎用的な方法に変更されました。OFORは、オペランドの型に応じて適切な符号拡張命令（CWD, CDQ, CQO）をoptoas関数が選択するように指示する内部演算子です。これにより、コードの柔軟性が向上し、異なる整数サイズに対応できるようになります。

 // cgen_shift関数 (新規追加)
 void
 cgen_shift(int op, Node *nl, Node *nr, Node *res)
 {
 	Node n1, n2;
 	int a, rcl;

 	a = optoas(op, nl->type); // シフト命令のオペコードを取得

 	if(nr->op == OLITERAL) { // シフト量が定数の場合
 		regalloc(&n1, nr->type, res);
 		cgen(nl, &n1);
 		gins(a, nr, &n1); // 直接シフト命令を生成
 		gmove(&n1, res);
 		regfree(&n1);
 		return;
 	}

 	rcl = reg[D_CX]; // CLレジスタの状態を保存

 	nodreg(&n1, types[TINT64], D_CX);
 	regalloc(&n1, nr->type, &n1);

 	// CLレジスタのクリーンアップ
 	if(rcl && !samereg(res, &n1)) {
 		regalloc(&n2, types[TINT64], N);
 		gins(AMOVQ, &n1, &n2);
 		regfree(&n1);

 		reg[D_CX] = 0;
 		cgen_shift(op, nl, nr, res); // 再帰呼び出しで処理
 		reg[D_CX] = rcl;

 		gins(AMOVQ, &n2, &n1);
 		regfree(&n2);
 		return;
 	}

 	regalloc(&n2, nl->type, res);
 	if(nl->ullman >= nr->ullman) {
 		cgen(nl, &n2);
 		cgen(nr, &n1);
 	} else {
 		cgen(nr, &n1);
 		cgen(nl, &n2);
 	}
 	gins(a, &n1, &n2); // シフト命令を生成
 	gmove(&n2, res);

 	regfree(&n1);
 	regfree(&n2);
 }

cgen_shift関数は、このコミットの最も重要な追加点です。シフト演算のコード生成を専門に行います。

  • シフト量が定数の場合: シフト量がリテラル（定数）であれば、x86のシフト命令は即値をシフト量として直接受け取れるため、シンプルに命令を生成します。
  • シフト量が変数の場合: シフト量が変数である場合、x86アーキテクチャではシフト量をCLレジスタ（CXレジスタの下位8ビット）にロードする必要があります。この関数は、CLレジスタが既に他の用途で使用されている場合に、その内容を一時的に保存し、シフト演算後に復元するロジックを含んでいます。これにより、CLレジスタの競合を安全に解決し、正しいシフトコードを生成します。
  • レジスタ割り当ても、ウルマン数に基づいて最適化されています。

src/cmd/6g/gsubr.c の変更点

 // optoas関数内
 case CASE(OLSH, TINT8):
 case CASE(OLSH, TUINT8):
 	a = ASHLB; // 8ビット左シフト
 	break;
 // ... 他の型とシフト命令のマッピング
 case CASE(ORSH, TUINT8):
 	a = ASHRB; // 8ビット論理右シフト
 	break;
 // ... 他の型と論理右シフト命令のマッピング
 case CASE(ORSH, TINT8):
 	a = ASARB; // 8ビット算術右シフト
 	break;
 // ... 他の型と算術右シフト命令のマッピング

optoas関数は、Goの演算子と型に基づいて、対応するx86アセンブリ命令のオペコードを返します。この変更により、OLSH（左シフト）とORSH（右シフト）に対して、各整数サイズ（8, 16, 32, 64ビット）に対応するx86シフト命令（SHL, SHR, SAR）のオペコードが追加されました。これにより、cgen_shift関数が適切なアセンブリ命令を動的に選択できるようになります。特に、符号なし右シフトにはSHR、符号あり右シフトにはSARが使用される点が重要です。

 // optoas関数内
 case CASE(OMUL, TINT8):
 case CASE(OMUL, TUINT8):
 	a = AIMULB; // 8ビット符号付き乗算
 	break;
 // ... 他の型と乗算命令のマッピング

乗算命令のマッピングが整理されました。以前は符号付きと符号なしで異なる命令（AIMULB/AMULBなど）をマッピングしていましたが、この変更により、すべての整数型に対してAIMUL（Integer Multiply）命令が使用されるようになりました。IMUL命令は、オペランドのサイズに応じて結果を適切に生成するため、多くの場合、符号付き・符号なしの区別なく使用できます。これにより、optoasのロジックが簡素化されます。

 // optoas関数内
 case CASE(OFOR, TINT16):
 	a = ACWD; // Word to Doubleword (AX -> DX:AX)
 	break;
 case CASE(OFOR, TINT32):
 	a = ACDQ; // Doubleword to Quadword (EAX -> EDX:EAX)
 	break;
 case CASE(OFOR, TINT64):
 	a = ACQO; // Quadword to Octaword (RAX -> RDX:RAX)
 	break;

OFORという新しい内部演算子（おそらく除算前の符号拡張を表す）が導入され、TINT16, TINT32, TINT64の各型に対して、それぞれACWD, ACDQ, ACQO（CWD, CDQ, CQOに対応）のオペコードがマッピングされました。これは、cgen_divにおける符号拡張の汎用化をサポートし、異なる整数サイズの除算に柔軟に対応できるようにします。

これらの変更は、Goコンパイラがx86アーキテクチャの特性を深く理解し、より効率的で正確な機械語を生成するための、低レベルかつ重要な最適化を示しています。

関連リンク

  • Go言語の公式ウェブサイト: https://go.dev/
  • Goコンパイラのソースコード（GitHub）: https://github.com/golang/go
  • x86命令セットリファレンス（Intel/AMDの公式ドキュメントを参照するのが最も正確です）

参考にした情報源リンク

  • Goコンパイラのソースコード（特にsrc/cmd/6gディレクトリ内のファイル）
  • x86アセンブリ言語に関する一般的な知識
  • コンパイラ設計に関する一般的な知識（レジスタ割り当て、中間表現など）
  • Ullman Numberに関する情報（コンパイラ最適化の文脈で）
  • Go言語の初期開発に関する歴史的資料（もしあれば）