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

このコミットは、Go言語のリンカ cmd/6l におけるループアライメント（ループの開始アドレスを特定のバイト境界に揃える最適化）に関する変更です。この機能は実装されましたが、当時のパフォーマンス測定では効果がなかったため、無効化されています。しかし、将来的な改善の可能性に備えてコードは残されています。

コミット

コミットハッシュ: c48ce6930ffcab5d4beaf9654e276bb132a2b66c
Author: Russ Cox rsc@golang.org
Date: Fri Jun 1 10:23:15 2012 -0400
変更ファイル:
- src/cmd/6l/l.h
- src/cmd/6l/span.c
- src/libmach/8db.c
変更概要: 3ファイルが変更され、62行が追加され、1行が削除されました。

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

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

元コミット内容

cmd/6l: loop alignment, disabled

Saving the code in case we improve things enough that
it matters later, but at least right now it is not worth doing.

R=ken2
CC=golang-dev
https://golang.org/cl/6248071

変更の背景

この変更の背景には、プログラムの実行性能を向上させるための一般的な最適化手法である「ループアライメント」の導入試行があります。ループアライメントは、CPUのキャッシュラインや命令フェッチの効率を最大化するために、ループの開始アドレスを特定のメモリアドレス境界に揃える技術です。

コミットメッセージと関連するコードレビュー（https://golang.org/cl/6248071）によると、このループアライメントのコードは実装されたものの、当時のGoリンカ 6l においては、この最適化がパフォーマンスに有意な改善をもたらさないことが判明しました。実際には、わずかながらも負の影響が見られたため、この機能は MaxLoopPad = 0 と設定することで無効化されました。

しかし、将来的にGoコンパイラやリンカの最適化が進み、このアライメントが効果を発揮する可能性を考慮し、コード自体は削除せずに残しておくという判断がなされました。これは、将来のパフォーマンス改善のための「保険」としてコードベースに保持されたことを意味します。

前提知識の解説

1. ループアライメント (Loop Alignment)

ループアライメントとは、プログラムのループ構造の開始アドレスを、CPUのキャッシュラインサイズや命令フェッチユニットの境界に揃える最適化手法です。

CPUキャッシュ: 現代のCPUは、メインメモリよりも高速なキャッシュメモリ（L1, L2, L3など）を持っています。CPUがデータを読み込む際、キャッシュラインと呼ばれる固定サイズのブロック単位でメモリからキャッシュにデータが転送されます。
命令フェッチ: CPUはプログラムを実行する際、メモリから命令を読み込み（フェッチ）、デコードし、実行します。このフェッチも通常、特定のバイト境界（例えば16バイトや32バイト）で行われます。
アライメントの利点:
- キャッシュミス削減: ループの開始がキャッシュラインの先頭に揃っていると、ループ本体の命令が複数のキャッシュラインにまたがりにくくなり、キャッシュミス（必要なデータがキャッシュにない状態）の発生を減らすことができます。
- 命令フェッチ効率の向上: CPUが命令をフェッチする際に、ループの開始がフェッチ境界に揃っていると、一度のフェッチでより多くのループ命令を効率的に読み込むことができます。これにより、命令パイプラインのストール（停止）を減らし、実行速度を向上させる可能性があります。
実装方法: 通常、アライメントのために、ループの開始アドレスの直前に「NOP (No Operation)」命令を挿入して、アドレスを調整します。

2. NOP (No Operation) 命令

NOP命令は、CPUに対して何もしないことを指示する命令です。CPUはNOP命令をフェッチ、デコード、実行しますが、レジスタやメモリの状態は変化しません。

用途:
- アライメント: コードのアドレスを特定の境界に揃えるために、必要なバイト数だけNOP命令を挿入します。
- タイミング調整: 非常に短い遅延を挿入するために使用されることもあります。
- デバッグ: ブレークポイントのプレースホルダーとして使用されることもあります。
x86-64アーキテクチャにおけるNOP: x86-64アーキテクチャでは、単一バイトの 0x90 が最も一般的なNOP命令ですが、より長いバイト数のNOP命令も存在します。これらは通常、MOV 命令や LEA 命令の形式を模倣していますが、実際には副作用がないように設計されています。このコミットのコードでは、様々な長さのNOP命令のバイト列が定義されています。

3. リンカ (Linker) `cmd/6l`

Go言語のツールチェインにおいて、6l はx86-64アーキテクチャ（AMD64）向けのリンカです。リンカは、コンパイラによって生成されたオブジェクトファイル（機械語コードとデータを含む）を結合し、実行可能なバイナリファイルを作成する役割を担います。

リンカの役割:
- シンボル解決: 異なるオブジェクトファイル間で参照される関数や変数のアドレスを解決します。
- アドレス割り当て: プログラムの各セクション（コード、データなど）をメモリ上のどこに配置するかを決定し、実際のアドレスを割り当てます。
- 再配置: アドレスが決定された後、コード内の相対アドレス参照などを絶対アドレスに修正します。
- 最適化: 場合によっては、リンカレベルでの最適化（例: コードの再配置、パディングの挿入）を行うことがあります。

このコミットは、リンカがコードを配置する際に、ループのアライメントを考慮してNOP命令を挿入しようとする試みを示しています。

技術的詳細

このコミットは、Go言語のx86-64リンカ cmd/6l に、ループの開始アドレスを特定のバイト境界にアライメントするためのロジックを追加しています。

1. アライメント定数 (`src/cmd/6l/l.h`)

src/cmd/6l/l.h に以下の定数が追加されました。

LoopAlign = 16: ループの開始アドレスを16バイト境界にアライメントしたいことを示します。これは、一般的なCPUのキャッシュラインサイズや命令フェッチの粒度を考慮した値です。
MaxLoopPad = 0: アライメントのために挿入できるNOP命令の最大バイト数を示します。このコミットでは 0 に設定されており、事実上ループアライメント機能が無効化されています。コメントには、gcc が MaxLoopPad = 10 を使用していることや、この機能が一時的に無効化されている理由が明記されています。

2. NOP命令の定義と挿入関数 (`src/cmd/6l/span.c`)

src/cmd/6l/span.c には、様々な長さのNOP命令のバイト列を定義した nop 配列と、それらをメモリに書き込む fillnop 関数が追加されました。

static uchar nop[][16]: 1バイトから10バイトまでのNOP命令のバイト列が定義されています。これらのバイト列は、手動で構築され、gdb で逆アセンブルして検証されたとコメントされています。例えば、0x90 は1バイトNOP、0x66, 0x90 は2バイトNOPなどです。
static void fillnop(uchar *p, int n): 指定されたアドレス p に、n バイト分のNOP命令を書き込む関数です。n の値に応じて、nop 配列から適切な長さのNOP命令を選択し、繰り返し書き込むことで、任意の長さのNOPパディングを生成します。

3. ループヘッドの識別とパディングロジック (`src/cmd/6l/span.c`)

span1 関数は、リンカがシンボルのコードセクションを処理する主要な関数です。この関数内で、ループヘッド（後方ジャンプのターゲット）を識別し、必要に応じてNOPパディングを挿入するロジックが追加されました。

ループヘッドの識別:
- p->back |= 1; // backward jump: 後方ジャンプ（ループを形成するジャンプ）を検出した命令 p にフラグ 1 を立てます。
- q->back |= 4; // loop head: その後方ジャンプのターゲットとなる命令 q にフラグ 4 を立て、これがループヘッドであることを示します。
NOPパディングの挿入:
- if((p->back & 4) && (c&(LoopAlign-1)) != 0): 現在処理している命令 p がループヘッドであり（p->back & 4）、かつ現在のコードオフセット c が LoopAlign (16) の境界に揃っていない場合（c&(LoopAlign-1)) != 0）、パディングが必要と判断されます。
- v = -c&(LoopAlign-1): 必要なパディングのバイト数を計算します。例えば、c が10で LoopAlign が16の場合、v は6になります（16 - 10）。
- if(v <= MaxLoopPad): 計算されたパディングバイト数 v が MaxLoopPad 以下である場合にのみ、パディングが実行されます。このコミットでは MaxLoopPad が 0 なので、この条件は常に偽となり、パディングは行われません。
- symgrow(s, c+v); fillnop(s->p+c, v); c += v;: もしパディングが許可されていれば、シンボル s のコード領域を拡張し、fillnop 関数を使って必要なバイト数だけNOP命令を挿入し、現在のコードオフセット c を更新します。

--- a/src/cmd/6l/l.h
+++ b/src/cmd/6l/l.h
@@ -41,6 +41,23 @@ enum
 {
 	thechar = '6',
 	PtrSize = 8,
+	
+	// Loop alignment constants:
+	// want to align loop entry to LoopAlign-byte boundary,
+	// and willing to insert at most MaxLoopPad bytes of NOP to do so.
+	// We define a loop entry as the target of a backward jump.
+	//
+	// gcc uses MaxLoopPad = 10 for its 'generic x86-64' config,
+	// and it aligns all jump targets, not just backward jump targets.
+	//
+	// As of 6/1/2012, the effect of setting MaxLoopPad = 10 here
+	// is very slight but negative, so the alignment is disabled by
+	// setting MaxLoopPad = 0. The code is here for reference and
+	// for future experiments.
+	// 
+	LoopAlign = 16,
+	MaxLoopPad = 0,
+
 	FuncAlign = 16
 };

`src/cmd/6l/span.c`

--- a/src/cmd/6l/span.c
+++ b/src/cmd/6l/span.c
@@ -37,6 +37,37 @@ static int
 rexflag;
 static int
 asmode;
 static vlong
 vadd(Adr*, Reloc*);
 
+// single-instruction no-ops of various lengths.
+// constructed by hand and disassembled with gdb to verify.
+// see http://www.agner.org/optimize/optimizing_assembly.pdf for discussion.
+static uchar nop[][16] = {
+	{0x90},
+	{0x66, 0x90},
+	{0x0F, 0x1F, 0x00},
+	{0x0F, 0x1F, 0x40, 0x00},
+	{0x0F, 0x1F, 0x44, 0x00, 0x00},
+	{0x66, 0x0F, 0x1F, 0x44, 0x00, 0x00},
+	{0x0F, 0x1F, 0x80, 0x00, 0x00, 0x00, 0x00},
+	{0x0F, 0x1F, 0x84, 0x00, 0x00, 0x00, 0x00, 0x00},
+	{0x66, 0x0F, 0x1F, 0x84, 0x00, 0x00, 0x00, 0x00, 0x00},
+	{0x66, 0x66, 0x0F, 0x1F, 0x84, 0x00, 0x00, 0x00, 0x00, 0x00},
+};
+
+static void
+fillnop(uchar *p, int n)
+{
+	int m;
+
+	while(n > 0) {
+		m = n;
+		if(m > nelem(nop))
+			m = nelem(nop);
+		memmove(p, nop[m-1], m);
+		p += m;
+		n -= m;
+	}
+}
+
 void
 span1(Sym *s)
 {
@@ -52,8 +83,10 @@ span1(Sym *s)\n 
 	for(p = s->text; p != P; p = p->link) {
 		p->back = 2;	// use short branches first time through
 		if((q = p->pcond) != P && (q->back & 2)) {
 			p->back |= 1;	// backward jump
+			q->back |= 4;   // loop head
+		}
 
 		if(p->as == AADJSP) {
 			p->to.type = D_SP;
@@ -78,6 +111,16 @@ span1(Sym *s)\n 
 		s->np = 0;
 		c = 0;
 		for(p = s->text; p != P; p = p->link) {
+			if((p->back & 4) && (c&(LoopAlign-1)) != 0) {
+				// pad with NOPs
+				v = -c&(LoopAlign-1);
+				if(v <= MaxLoopPad) {
+					symgrow(s, c+v);
+					fillnop(s->p+c, v);
+					c += v;
+				}
+			}
+
 			p->pc = c;
 
 			// process forward jumps to p

`src/libmach/8db.c`

--- a/src/libmach/8db.c
+++ b/src/libmach/8db.c
@@ -622,6 +622,7 @@ static Optable optab0F[256]=\n [0x15] =\t{ RM,0,\t\t"UNPCKH%s\t%x,%X" },\n [0x16] =\t{ RM,0,\t\t"MOV[L]H%s\t%x,%X" },\t/* TO DO: L if source is XMM */\n [0x17] =\t{ RM,0,\t\t"MOVH%s\t%X,%x" },\n+[0x1F] =\t{ RM,0,\t\t"NOP%S\t%e" },\n [0x20] =\t{ RMR,0,\t\t"MOVL\t%C,%e" },\n [0x21] =\t{ RMR,0,\t\t"MOVL\t%D,%e" },\n [0x22] =\t{ RMR,0,\t\t"MOVL\t%e,%C" },

コアとなるコードの解説

`src/cmd/6l/l.h`

LoopAlign = 16: ループの開始アドレスを16バイト境界に揃えることを目標としています。これは、CPUの命令フェッチやキャッシュラインの効率を考慮した一般的な値です。
MaxLoopPad = 0: ループアライメントのために挿入できるNOP命令の最大バイト数を0に設定しています。これにより、このコミット時点ではループアライメント機能が実質的に無効化されています。コメントには、gcc が10バイトのパディングを許容していることや、この機能が将来のために残されていることが明記されています。

`src/cmd/6l/span.c`

nop 配列: 1バイトから10バイトまでの様々な長さのNOP命令のバイト列が定義されています。これらの命令は、x86-64アーキテクチャにおける実際のNOP命令のパターン（例: 0x90 は単一バイトNOP、0x0F 0x1F 0x00 は3バイトNOPなど）に対応しています。これらは、コードのアライメント調整のために使用されます。
fillnop 関数: 指定されたポインタ p に、指定されたバイト数 n だけNOP命令を書き込むユーティリティ関数です。n の値に応じて、nop 配列から適切な長さのNOP命令を選択し、memmove を使ってコピーすることで、必要な長さのパディングを生成します。
span1 関数内のループアライメントロジック:
- q->back |= 4; // loop head: 後方ジャンプのターゲット（つまりループの開始点）である命令 q に 4 のフラグを立てることで、ループヘッドを識別します。
- if((p->back & 4) && (c&(LoopAlign-1)) != 0): この条件は、現在の命令 p がループヘッドであり、かつ現在のコードオフセット c が LoopAlign (16) の境界に揃っていない場合に真となります。
- v = -c&(LoopAlign-1): 必要なパディングバイト数を計算します。例えば、現在のオフセットが10で LoopAlign が16の場合、v は6になります（16 - 10 = 6）。
- if(v <= MaxLoopPad): 計算されたパディングバイト数 v が MaxLoopPad 以下である場合にのみ、実際にパディングが挿入されます。このコミットでは MaxLoopPad が0なので、この条件は常に偽となり、NOPは挿入されません。
- symgrow(s, c+v); fillnop(s->p+c, v); c += v;: もしパディングが許可されていれば、シンボルのコード領域を拡張し、fillnop を使ってNOP命令を挿入し、コードオフセットを更新します。

`src/libmach/8db.c`

[0x1F] = { RM,0, "NOP%S\t%e" }: デバッガが機械語命令を逆アセンブルする際に使用するテーブルに、0x1F オペコード（x86のNOP命令の一部）に対するエントリが追加されました。これにより、デバッガはこれらのNOP命令を「NOP」として正しく表示できるようになります。

参考にした情報源リンク

Optimizing Assembly Code (by Agner Fog): http://www.agner.org/optimize/optimizing_assembly.pdf (コミット内のコメントで参照されている資料)
CPUキャッシュとアライメントに関する一般的な情報源 (例: Wikipedia, 各種技術ブログ)
Go言語のリンカに関する一般的な情報源 (例: Goの公式ドキュメント、Goのソースコード解説)

comemo

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

コミット

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

元コミット内容

変更の背景

前提知識の解説

1. ループアライメント (Loop Alignment)

2. NOP (No Operation) 命令

3. リンカ (Linker) `cmd/6l`

技術的詳細

1. アライメント定数 (`src/cmd/6l/l.h`)

2. NOP命令の定義と挿入関数 (`src/cmd/6l/span.c`)

3. ループヘッドの識別とパディングロジック (`src/cmd/6l/span.c`)

4. デバッガ情報 (`src/libmach/8db.c`)

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

`src/cmd/6l/l.h`

`src/cmd/6l/span.c`

`src/libmach/8db.c`

コアとなるコードの解説

`src/cmd/6l/l.h`

`src/cmd/6l/span.c`

`src/libmach/8db.c`

関連リンク

参考にした情報源リンク

Keyboard shortcuts

comemo