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

このコミットは、Goコンパイラのcmd/6g（64-bit x86アーキテクチャ向けコンパイラ）における命令デコードロジックを共通関数に集約し、最適化パスの堅牢性と保守性を向上させるものです。これまで複数の最適化パスで重複し、かつ不正確であった命令に関する情報を一元化することで、コードの品質と将来的な拡張性を高めています。

コミット

commit 24c8035fbe113dfe644f4419eadcb826e08788ee
Author: Russ Cox <rsc@golang.org>
Date:   Sun Aug 11 21:46:38 2013 -0400

    cmd/6g: move opt instruction decode into common function
    
    Add new proginfo function that returns information about a
    Prog*. The information includes various instruction
    description bits as well as a list of required registers set
    and used and indexing registers used.
    
    Convert the large instruction switches to use proginfo.
    
    This information was formerly duplicated in multiple
    optimization passes, inconsistently. For example, the
    information about which registers an instruction requires
    appeared three times for most instructions.
    
    Most of the switches were incomplete or incorrect in some way.
    For example, the switch in copyu did not list cases for INCB,
    JPS, MOVAPD, MOVBWSX, MOVBWZX, PCDATA, POPQ, PUSHQ, STD,
    TESTB, TESTQ, and XCHGL. Those were all falling into the
    "unknown instruction" default case and stopping the rewrite,
    perhaps unnecessarily. Similarly, the switch in needc only
    listed a handful of the instructions that use or set the carry bit.
    
    We still need to decide whether to use proginfo to generalize
    a few of the remaining smaller switches in peep.c.
    
    If this goes well, we'll make similar changes in 8g and 5g.
    
    R=ken2
    CC=golang-dev
    https://golang.org/cl/12637051

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

https://github.com/golang/go/commit/24c8035fbe113dfe644f4419eadcb826e08788ee

元コミット内容

cmd/6g: 最適化命令デコードを共通関数に移動

Prog*に関する情報（様々な命令記述ビット、使用・設定される必須レジスタ、インデックスレジスタ）を返す新しいproginfo関数を追加。

大規模な命令スイッチをproginfoを使用するように変換。

この情報は以前、複数の最適化パスで重複し、一貫性がなかった。例えば、命令が必要とするレジスタに関する情報は、ほとんどの命令で3回出現していた。

ほとんどのスイッチは、何らかの形で不完全または不正確だった。例えば、copyuのスイッチはINCB, JPS, MOVAPD, MOVBWSX, MOVBWZX, PCDATA, POPQ, PUSHQ, STD, TESTB, TESTQ, XCHGLのケースをリストしておらず、これらはすべて「不明な命令」のデフォルトケースにフォールバックし、不必要に書き換えを停止させていた可能性がある。同様に、needcのスイッチは、キャリービットを使用または設定する命令のごく一部しかリストしていなかった。

peep.cに残っているいくつかの小さなスイッチをproginfoで一般化するかどうかは、まだ決定する必要がある。

これがうまくいけば、8gと5gでも同様の変更を行う予定。

変更の背景

Goコンパイラの最適化フェーズにおいて、各命令（Prog*構造体で表現される）がどのような特性を持つか（例：どのレジスタを使用・変更するか、キャリーフラグに影響するか、命令の種類など）に関する情報が、複数の異なる最適化パス（copyu, needcなど）で個別に、かつswitch文を用いてハードコードされていました。

このアプローチには以下の問題がありました。

1. 情報の重複と不整合: 同じ命令に関する情報が複数の場所で定義されており、変更があった場合にすべての箇所を更新する必要がありました。これにより、情報が不整合になるリスクが高まりました。
2. 不完全性・不正確性: 各switch文がすべての命令を網羅しているわけではなく、一部の命令が「不明な命令」として扱われ、最適化が早期に停止してしまう問題がありました。これは、本来最適化可能なコードが最適化されない原因となっていました。コミットメッセージでは、copyuにおけるINCB, JPS, MOVAPDなどの命令や、needcにおけるキャリービット関連の命令の例が挙げられています。
3. 保守性の低下: 新しい命令が追加されたり、既存の命令の特性が変更されたりするたびに、関連するすべての最適化パスのswitch文を更新する必要があり、保守コストが高く、エラーの温床となっていました。

このコミットは、これらの問題を解決するために、命令に関する情報を一元化されたproginfo関数とprogtableに集約し、各最適化パスがこの共通の情報源を参照するように変更することで、コードの堅牢性、正確性、保守性を大幅に向上させることを目的としています。

前提知識の解説

このコミットを理解するためには、以下のGoコンパイラの内部構造とx86アセンブリの基本的な知識が必要です。

• Goコンパイラ (cmd/6g, cmd/8g, cmd/5g):
  • Go言語のコンパイラは、ターゲットアーキテクチャごとに異なるバックエンドを持っています。
  • cmd/6g: x86-64 (AMD64) アーキテクチャ向けのコンパイラバックエンドです。
  • cmd/8g: ARMアーキテクチャ向けのコンパイラバックエンドです。
  • cmd/5g: ARMv5/v6/v7アーキテクチャ向けのコンパイラバックエンドです。
  • これらのコンパイラは、Goのソースコードを中間表現に変換し、最終的にターゲットアーキテクチャの機械語に変換します。この過程で様々な最適化パスが適用されます。
• Prog*構造体:
  • Goコンパイラのバックエンドにおいて、Prog構造体は単一のアセンブリ命令を表す内部表現です。
  • 各Progインスタンスは、命令の種類（p->as）、オペランド（p->from, p->to）、リンク（p->linkで次の命令へのポインタ）などの情報を含みます。
  • 最適化パスは、このProgのリストを走査し、命令の追加、削除、変更などを行います。
• 最適化パス:
  • コンパイラは、生成されるコードの性能を向上させるために様々な最適化を行います。
  • peep.c (Peephole Optimizer): 局所的な命令列をより効率的な命令列に置き換える最適化です。例えば、MOV AX, BX; MOV BX, CXをMOV AX, CXに変換するなど、ごく短い命令シーケンスを対象とします。
  • reg.c (Register Allocator): プログラム変数に物理レジスタを割り当てる処理を行います。レジスタの使用状況（どのレジスタが使用され、どのレジスタが変更されるか）を正確に把握することが重要です。
  • copyu関数: peep.c内で使用される関数で、あるアドレス（レジスタやメモリ位置）が命令によってどのように使用または変更されるかを分析します。
  • needc関数: peep.c内で使用される関数で、キャリーフラグ（CPUのステータスレジスタの一部）が特定の命令によって使用されるかどうかを判断します。
• レジスタとフラグ:
  • レジスタ: CPU内部の高速な記憶領域で、演算の対象となるデータやアドレスを一時的に保持します。x86-64アーキテクチャでは、AX, BX, CX, DX, DI, SIなどの汎用レジスタがあります。
  • キャリーフラグ (Carry Flag, CF): 算術演算の結果、最上位ビットからの桁上がり（または桁借り）が発生したことを示すフラグです。ADC (Add with Carry) や SBB (Subtract with Borrow) などの命令で使用されます。
  • RtoBマクロ: レジスタの型（D_AXなど）をビットマスクに変換するためのマクロです。これにより、複数のレジスタをビット単位のORで表現し、レジスタの集合を効率的に管理できます。

技術的詳細

このコミットの核心は、命令に関するメタデータを一元化するためのProgInfo構造体と、その情報を取得するためのproginfo関数、そしてそのデータが格納されたprogtableの導入です。

ProgInfo構造体 (src/cmd/6g/opt.hに追加)

typedef struct ProgInfo ProgInfo;
struct ProgInfo
{
	uint32 flags;    // 命令の特性を示すビットフラグ
	uint32 reguse;   // この命令で必須となる使用レジスタのビットマスク
	uint32 regset;   // この命令で必須となる設定レジスタのビットマスク
	uint32 regindex; // アドレス指定モードで使用されるレジスタのビットマスク
};

• flags: 命令の様々な特性をビットフラグで表現します。
  • Pseudo: 擬似命令（TEXT, GLOBLなど）。
  • OK: 特に言うべきことはないが、問題ない命令。
  • SizeB, SizeW, SizeL, SizeQ, SizeF, SizeD: 命令が操作するデータのサイズ（バイト、ワード、ロング、クアッド、float32、float64）。
  • LeftAddr, LeftRead, LeftWrite: 左オペランド（p->from）がアドレス、読み込み、書き込みのいずれかであるか。
  • RightAddr, RightRead, RightWrite: 右オペランド（p->to）がアドレス、読み込み、書き込みのいずれかであるか。
  • SetCarry, UseCarry, KillCarry: キャリーフラグの設定、使用、または無効化。
  • Move, Conv, Cjmp, Break, Call, Jump, Skip: 命令の種類（移動、型変換、条件分岐、制御フロー中断、関数呼び出し、無条件ジャンプ、データ命令）。
  • ShiftCX, ImulAXDX: CXレジスタによるシフト、DX:AXへの乗算など、特定のレジスタ使用パターン。
• reguse: 命令が実行されるために読み込みが必要なレジスタのビットマスク。
• regset: 命令が実行された結果、書き込みが行われるレジスタのビットマスク。
• regindex: メモリアドレス指定モード（例：[BX+SI*4]）において、アドレス計算に使用されるレジスタのビットマスク。

progtable (src/cmd/6g/prog.cに新規追加)

progtableは、ALAST（命令の最大値）までの各命令コードに対応するProgInfo構造体の配列です。このテーブルは、各命令の静的な特性を定義します。

static ProgInfo progtable[ALAST] = {
	[ATYPE]=	{Pseudo | Skip},
	[ATEXT]=	{Pseudo},
	// ... 多くの命令の定義 ...
	[AADCL]=	{SizeL | LeftRead | RightRdwr | SetCarry | UseCarry},
	[AADDQ]=	{SizeQ | LeftRead | RightRdwr | SetCarry | UseCarry},
	// ...
};

このテーブルにより、各命令の特性が中央集権的に管理され、重複や不整合が解消されます。

proginfo関数 (src/cmd/6g/prog.cに新規追加)

void
proginfo(ProgInfo *info, Prog *p)
{
	*info = progtable[p->as]; // 命令コードに対応する情報をテーブルから取得
	if(info->flags == 0)
		fatal("unknown instruction %P", p); // 未知の命令はエラー

	// 特殊なレジスタ使用パターンに対する調整
	if((info->flags & ShiftCX) && p->from.type != D_CONST)
		info->reguse |= CX; // シフト量が定数でない場合、CXレジスタが使用される

	if(info->flags & ImulAXDX) {
		if(p->to.type == D_NONE) {
			info->reguse |= AX;
			info->regset |= AX | DX; // IMUL命令でDX:AXが使用される場合
		} else {
			info->flags |= RightRdwr;
		}
	}

	// アドレス指定モードによるレジスタ使用の追加
	if(p->from.type >= D_INDIR)
		info->regindex |= RtoB(p->from.type-D_INDIR);
	if(p->from.index != D_NONE)
		info->regindex |= RtoB(p->from.index);
	if(p->to.type >= D_INDIR)
		info->regindex |= RtoB(p->to.type-D_INDIR);
	if(p->to.index != D_NONE)
		info->regindex |= RtoB(p->to.index);
}

proginfo関数は、与えられたProg*（命令）から、その命令の特性を記述するProgInfo構造体を生成します。これはprogtableから基本情報を取得し、さらに命令のオペランド（p->from, p->to）に基づいて、CXレジスタによるシフトやDX:AXレジスタへの乗算、アドレス指定モードで使用されるレジスタなど、動的なレジスタ使用情報を追加します。

既存コードの変更

• src/cmd/6g/peep.c:
  • needc, prevl, subprop, copyuなどの関数で、巨大なswitch文がproginfo関数からの情報を使用するように置き換えられました。これにより、命令の特性判断が簡潔かつ正確になりました。
  • 例えば、copyu関数では、以前は命令の種類ごとに複雑なswitch文でレジスタの使用・設定を判断していましたが、proginfoから得られるinfo.reguse, info.regset, info.flags（LeftRead, RightWriteなど）を使って汎用的に処理できるようになりました。
• src/cmd/6g/reg.c:
  • レジスタアロケータの主要な関数であるregopt内で、命令の特性（スキップすべき命令、制御フローを中断する命令など）を判断するためにproginfoが使用されるようになりました。
  • レジスタの使用（r->use1, r->use2）と設定（r->set）のビットマスクを計算する際にも、proginfoから得られるinfo.reguse, info.regset, info.regindex、およびinfo.flags（LeftRead, RightWriteなど）が直接利用されるようになりました。

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

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

• src/cmd/6g/opt.h:
  • ProgInfo構造体の定義が追加されました。
  • ProgInfo構造体で使用されるビットフラグのenum定義が追加されました。
  • proginfo関数のプロトタイプ宣言が追加されました。
• src/cmd/6g/peep.c:
  • needc, peep, prevl, subprop, copyuなどの関数内で、命令の特性を判断するために使用されていた大規模なswitch文が削除または大幅に簡略化され、新しく導入されたproginfo関数からの情報を使用するように変更されました。
• src/cmd/6g/prog.c: (新規ファイル)
  • progtableという静的なProgInfo構造体の配列が定義され、各命令の静的な特性がここに一元的に記述されました。
  • proginfo関数が実装されました。この関数は、progtableから基本情報を取得し、命令のオペランドに基づいて動的なレジスタ使用情報を追加します。
• src/cmd/6g/reg.c:
  • regopt関数内で、命令の特性（レジスタの使用、設定、インデックスレジスタ、制御フローの特性など）を判断するために、proginfo関数が呼び出されるようになりました。これにより、レジスタアロケーションのロジックが簡潔かつ正確になりました。

コアとなるコードの解説

src/cmd/6g/prog.c (新規ファイル)

このファイルは、命令に関するすべてのメタデータを集約する中心的な役割を担います。

• progtable:
  • Goコンパイラがサポートする各x86-64命令（ALASTまでの列挙型で識別される）に対して、その命令の特性を定義するProgInfo構造体が静的に初期化されています。
  • 例えば、AADCL (Add with Carry Long) 命令は、SizeL (32ビット操作)、LeftRead (左オペランドを読み込む)、RightRdwr (右オペランドを読み書きする)、SetCarry (キャリーフラグを設定する)、UseCarry (キャリーフラグを使用する) といった特性を持つことが明確に定義されています。
  • ADIVL (Divide Long) のように、AXやDXレジスタを暗黙的に使用・設定する命令についても、reguseとregsetフィールドでその情報が記述されています。
• proginfo関数:
  • この関数は、Prog* p（特定のアセンブリ命令）を受け取り、その命令の完全なProgInfoを返します。
  • まず、progtable[p->as]から命令の基本的な静的特性を取得します。
  • 次に、命令のオペランド（p->from, p->to）を検査し、ShiftCX（シフト命令でCXがシフト量として使われる場合）やImulAXDX（IMUL命令でDX:AXが暗黙的に使われる場合）のような動的なレジスタ使用パターンをreguseやregsetに追加します。
  • さらに、メモリアドレス指定モード（例：[base + index*scale + disp]）で使用されるレジスタ（p->from.type-D_INDIR, p->from.indexなど）をregindexに追加します。これにより、アドレス計算に必要なレジスタも正確に追跡できます。

src/cmd/6g/peep.c

このファイルは、命令の特性を判断するためにproginfoをどのように利用するかを示しています。

• needc関数:
  • 以前は、キャリーフラグを使用する命令を個別のcase文で列挙していましたが、proginfoのUseCarryフラグとSetCarry/KillCarryフラグを使用するように変更されました。
  • これにより、キャリーフラグの依存関係をより正確かつ簡潔に判断できるようになりました。
• copyu関数:
  • この関数は、あるアドレスvが命令pによってどのように使用または変更されるかを分析します。
  • 以前は、命令の種類ごとに非常に長いswitch文があり、各命令のレジスタ使用・設定、アドレス指定モードなどを個別に処理していました。
  • 変更後、proginfo(&info, p)を呼び出して命令の特性を取得し、info.flags（LeftRead, RightWriteなど）、info.reguse, info.regsetなどに基づいて汎用的なロジックで処理するようになりました。これにより、コードの重複が大幅に削減され、新しい命令が追加された際の保守が容易になりました。

src/cmd/6g/reg.c

このファイルは、レジスタアロケータがproginfoをどのように利用してレジスタの使用状況を追跡するかを示しています。

• regopt関数:
  • 各命令pに対してproginfo(&info, p)を呼び出し、その命令の特性を取得します。
  • info.flags & Skipを使用して、最適化の対象外となる擬似命令などをスキップします。
  • info.flags & Breakを使用して、RETやJMPのような制御フローを中断する命令を識別し、レジスタフロー分析を適切に処理します。
  • r->use1.b[0] |= info.reguse | info.regindex; および r->set.b[0] |= info.regset; のように、proginfoから得られたレジスタ使用・設定情報を直接レジスタアロケータの内部データ構造に反映させます。これにより、レジスタのライブネス分析（どのレジスタがどの時点で有効か）がより正確に行えるようになります。
  • オペランド（p->from, p->to）のレジスタ使用・設定も、info.flags（LeftAddr, LeftRead, LeftWrite, RightAddr, RightRead, RightWrite）に基づいて汎用的に処理されるようになりました。

これらの変更により、Goコンパイラのバックエンドにおける命令デコードと最適化のロジックが大幅に改善され、より堅牢で保守性の高いコードベースが実現されました。

関連リンク

• Go Gerrit Change: https://golang.org/cl/12637051
• GitHub Commit: https://github.com/golang/go/commit/24c8035fbe113dfe644f4419eadcb826e08788ee

参考にした情報源リンク

• Go言語のコンパイラに関する一般的な情報:
  • Go Compiler Internals - The Go Programming Language (一般的なGoコンパイラの概要)
• x86-64アセンブリ命令セットに関する情報:
  • Intel® 64 and IA-32 Architectures Software Developer’s Manuals (詳細な命令リファレンス)
• コンパイラの最適化に関する一般的な情報:
  • Compiler optimization - Wikipedia
  • Peephole optimization - Wikipedia
• レジスタ割り当てに関する一般的な情報:
  • Register allocation - Wikipedia
• Goコンパイラのソースコード (特にsrc/cmd/6gディレクトリ):
  • golang/go - GitHub
• Goコンパイラの開発に関する議論:
  • golang-dev mailing list (コミットメッセージにCC=golang-devとあるため)
• GoのCL (Change List) について:
  • Go Code Review Comments - The Go Programming Language (GoのコードレビュープロセスとCLの役割について)
• Prog構造体やD_AXなどの定数に関する情報:
  • Goコンパイラのソースコード内の関連ファイル（例: src/cmd/internal/obj/x86/x86.go や src/cmd/internal/obj/x86/a.h など、当時のC言語実装における対応するヘッダファイル）
• RtoBマクロの概念:
  • ビットマスクを用いたレジスタ集合の表現は、コンパイラやOSカーネルなどの低レベルプログラミングで一般的に用いられる手法です。
• fatal関数:
  • Goコンパイラ内部で使用されるエラー報告関数。
• u.h, libc.h, gg.h, opt.hなどのヘッダファイル:
  • GoコンパイラのC言語部分で使用される内部ヘッダファイル。
• D_INDIR, D_AXなどの定数:
  • Goコンパイラの内部で、オペランドの種類やレジスタを識別するために使用される定数。