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

このコミットは、Go言語のARMアーキテクチャ向けツールチェインとmath/bigパッケージに、先行ゼロカウント（Count Leading Zeros: CLZ）命令のサポートを追加するものです。具体的には、アセンブラ（cmd/5a）、リンカ（cmd/5l）がCLZ命令を認識・処理できるように更新され、math/bigパッケージ内のARMアセンブリコードでこの新しい命令が利用されるようになります。

変更されたファイルは以下の通りです。

• src/cmd/5a/lex.c: Goアセンブラの字句解析器（lexer）に関連するファイル。新しい命令（CLZ）のキーワードが追加されます。
• src/cmd/5l/5.out.h: Goリンカの出力形式や命令コードの定義が含まれるヘッダファイル。CLZ命令の定数が追加されます。
• src/cmd/5l/asm.c: Goリンカのアセンブリコード生成部分。CLZ命令の機械語への変換ロジックが追加されます。
• src/cmd/5l/optab.c: Goリンカのオペコードテーブル。CLZ命令のエントリが追加されます。
• src/cmd/5l/span.c: Goリンカのコード生成パスの一部。CLZ命令の処理が追加されます。
• src/pkg/math/big/arith_arm.s: Goのmath/bigパッケージにおけるARMアーキテクチャ向けのアセンブリ実装ファイル。bitLen関数でCLZ命令が利用されるようになります。

コミット

このコミットは、ARMv5以降のARMアーキテクチャでサポートされるCLZ（Count Leading Zeros）命令をGo言語のツールチェインに追加し、math/bigパッケージでその命令を利用するように変更します。これにより、math/bigパッケージのbitLen関数など、ビット操作を伴う処理のパフォーマンス向上が期待されます。

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

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

元コミット内容

commit d186d07eda6cb043c4c75ef6ec3e161e7f6c5a3e
Author: Shenghou Ma <minux.ma@gmail.com>
Date:   Sun Jun 3 03:08:49 2012 +0800

    cmd/5a, cmd/5l, math: add CLZ instruction for ARM
            Supported in ARMv5 and above.
    
    R=golang-dev, rsc
    CC=golang-dev
    https://golang.org/cl/6284043

変更の背景

この変更の背景には、ARMアーキテクチャにおける特定のビット操作の効率化があります。特に、数値の先行ゼロを数える操作（Count Leading Zeros: CLZ）は、多くのアルゴリズム、特に多倍長整数演算やビットマップ操作において頻繁に利用されます。

Go言語のmath/bigパッケージは、任意精度の整数演算を提供しており、その内部ではbitLen（ビット長を計算する）のようなビット操作が多用されます。これらの操作は、通常、ループとビットシフトを組み合わせてソフトウェア的に実装されますが、CLZ命令のようなハードウェアサポートがあれば、はるかに高速に実行できます。

ARMv5以降のARMプロセッサには、このCLZ命令が導入されており、特定のレジスタの値の先行ゼロの数を直接計算できます。Go言語がARMアーキテクチャをサポートする上で、このハードウェア機能を活用しない手はありません。このコミットは、Goのツールチェイン（アセンブラとリンカ）がCLZ命令を認識し、適切に機械語に変換できるように拡張し、さらにmath/bigパッケージがその恩恵を受けられるようにすることで、ARMプラットフォーム上でのGoプログラムのパフォーマンス向上を目指しています。

前提知識の解説

ARMアーキテクチャと命令セット

ARM（Advanced RISC Machine）は、モバイルデバイスや組み込みシステムで広く使用されているRISC（Reduced Instruction Set Computer）ベースのプロセッサアーキテクチャです。ARMプロセッサは、その低消費電力と高性能のバランスから、スマートフォン、タブレット、IoTデバイスなど、多岐にわたる分野で採用されています。

ARM命令セットは、固定長の命令形式を持ち、ロード/ストアアーキテクチャを採用しています。これは、メモリへのアクセスがロード（メモリからレジスタへ）とストア（レジスタからメモリへ）命令に限定され、演算命令はレジスタ間で行われることを意味します。

CLZ (Count Leading Zeros) 命令

CLZ命令は、特定のレジスタに格納された32ビット（または64ビット）のバイナリ値の最上位ビットから見て、最初に1が現れるまでの連続する0の数を数える命令です。例えば、32ビット値 0000 0000 0000 0000 0000 0000 0000 1010 (10進数の10) の場合、CLZ命令は28を返します。これは、最上位ビットから数えて28個の0が連続しているためです。

この命令は、以下のような用途で非常に有用です。

• ビット長の計算: 数値の有効ビット長（bitLen）を効率的に計算できます。例えば、32ビット値のビット長は 32 - CLZ(x) で求められます。
• 正規化: 浮動小数点数の正規化や、ビットフィールド操作において、シフト量を決定するために使用されます。
• 優先度エンコーディング: 最も高い優先度を持つビットを見つける際に役立ちます。

CLZ命令はARMv5T（Thumb-2命令セットの一部として）またはARMv5TEJ以降のARMプロセッサでサポートされています。

Go言語のツールチェイン

Go言語は、独自のコンパイラ、アセンブラ、リンカを含むツールチェインを持っています。

• cmd/5a (アセンブラ): Goのアセンブリ言語（Plan 9アセンブリ）を機械語に変換します。5aはARMアーキテクチャ（GOARCH=arm）を指します。
• cmd/5l (リンカ): アセンブルされたオブジェクトファイルやコンパイルされたGoコードをリンクし、実行可能ファイルを生成します。5lもARMアーキテクチャを指します。
• src/pkg/math/big: Goの標準ライブラリの一部で、任意精度の整数（big.Int）や有理数（big.Rat）を扱うためのパッケージです。内部的には、効率的な演算のためにプラットフォーム固有のアセンブリコード（例: arith_arm.s）を使用することがあります。

Plan 9アセンブリ

Go言語のアセンブリは、Bell LabsのPlan 9オペレーティングシステムで使用されていたアセンブリ言語の構文に基づいています。これは、一般的なIntel構文やAT&T構文とは異なる独特の構文を持ちます。例えば、ソースとデスティネーションのオペランドの順序が逆であったり、レジスタの表記方法が異なったりします。

技術的詳細

このコミットは、CLZ命令をGoのARMツールチェインに統合するために、複数のコンポーネントにわたる変更を加えています。

1. アセンブラ (cmd/5a) の変更:

   • src/cmd/5a/lex.c: アセンブラの字句解析器に、新しいキーワード CLZ を追加します。これにより、アセンブリソースコード内で CLZ 命令が記述された際に、アセンブラがそれを認識できるようになります。LTYPE2 は、2つのオペランドを持つ命令のタイプを示し、ACLZ はCLZ命令に対応する内部的なオペコード定数です。

2. リンカ (cmd/5l) の変更:

   • src/cmd/5l/5.out.h: リンカが使用する命令コードの列挙型 enum as に、ACLZ という新しい定数を追加します。これは、CLZ命令をリンカ内部で一意に識別するためのIDとなります。
   • src/cmd/5l/optab.c: リンカのオペコードテーブル optab に、ACLZ 命令のエントリを追加します。このエントリは、CLZ命令がどのようなオペランド（C_REG はレジスタオペランドを意味します）を取り、リンカがどのようにそれを処理すべきか（97 は命令のタイプ、4 は命令のバイト長、0 はフラグ）を定義します。
   • src/cmd/5l/asm.c: リンカのアセンブリコード生成ロジックに、ACLZ 命令を機械語に変換するための新しいケースを追加します。
     • case 97: /* CLZ Rm, Rd */: これはoptab.cで定義されたCLZ命令のタイプ97に対応します。
     • o1 = oprrr(p->as, p->scond);: oprrr関数は、レジスタ-レジスタ-レジスタ形式の命令の共通部分を生成します。
     • o1 |= p->to.reg << 12;: 宛先レジスタ（Rd）を命令の適切なビット位置に配置します。ARMのCLZ命令では、宛先レジスタはビット15-12にエンコードされます。
     • o1 |= p->from.reg;: ソースレジスタ（Rm）を命令の適切なビット位置に配置します。ARMのCLZ命令では、ソースレジスタはビット3-0にエンコードされます。
     • case ACLZ: の部分では、CLZ命令の特定のビットパターン（0x16f<<16) | (0xf1<<4)）が設定されます。これは、ARMのCLZ命令の機械語エンコーディングの一部であり、特定のビットが命令の種類とオペランドを示します。CLZ命令は条件コード（.Sサフィックス）をサポートしないため、その点も考慮されています。
   • src/cmd/5l/span.c: リンカのコード生成パスの一部で、命令のサイズ計算や配置に関連する処理が行われます。ACLZ が新しい命令として認識され、適切に処理されるように switch 文に case ACLZ: が追加されています。

3. math/bigパッケージの変更:

   • src/pkg/math/big/arith_arm.s: math/bigパッケージのARMアセンブリ実装ファイルで、bitLen関数の実装が変更されます。
     • 変更前: WORD $0xe16f0f10 // CLZ R0, R0 (count leading zeros) これは、CLZ命令の機械語コードを直接埋め込む形式です。これは移植性が低く、アセンブラが命令を直接サポートしていない場合に用いられることがあります。
     • 変更後: CLZ R0, R0 これは、新しいアセンブラが認識するCLZ命令のニーモニックを使用する形式です。これにより、コードの可読性が向上し、ツールチェインが命令を適切に処理できるようになります。
     • MOVW $32, R1 と SUB.S R0, R1 は、32ビット値のビット長を 32 - CLZ(x) で計算するロジックです。CLZ命令が先行ゼロの数を返すため、全体のビット幅から先行ゼロの数を引くことで、有効なビット数を取得できます。

これらの変更により、GoのARMツールチェインはCLZ命令を完全にサポートし、Goプログラム、特にmath/bigパッケージのような数値演算が重要な部分で、ARMプロセッサのハードウェア機能を最大限に活用できるようになります。

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

src/cmd/5a/lex.c

--- a/src/cmd/5a/lex.c
+++ b/src/cmd/5a/lex.c
@@ -406,6 +406,8 @@ struct
 
 	"PLD",		LTYPEPLD, APLD,
 	"UNDEF",	LTYPEE,	AUNDEF,
+	"CLZ",		LTYPE2, ACLZ,
+
 	0
 };

src/cmd/5l/5.out.h

--- a/src/cmd/5l/5.out.h
+++ b/src/cmd/5l/5.out.h
@@ -184,9 +184,11 @@ enum
 	ASTREXD,
 
 	APLD,
-\t
+
 	AUNDEF,
 
+\tACLZ,
+\n
 	ALAST,
 };

src/cmd/5l/asm.c

--- a/src/cmd/5l/asm.c
+++ b/src/cmd/5l/asm.c
@@ -1801,6 +1801,11 @@ if(debug['G']) print("%ux: %s: arm %d\n", (uint32)(p->pc), p->from.sym->name, p-
 		o1 = opbra(ABL, C_SCOND_NONE);
 		o1 |= (v >> 2) & 0xffffff;
 		break;
+	case 97:	/* CLZ Rm, Rd */
+ 		o1 = oprrr(p->as, p->scond);
+ 		o1 |= p->to.reg << 12;
+ 		o1 |= p->from.reg;
+		break;
 	}
 	
 out[0] = o1;
@@ -1958,6 +1963,10 @@ oprrr(int a, int sc)
 		return o | (0xe<<24) | (0x1<<20) | (0xb<<8) | (1<<4);
 	case ACMP+AEND:	// cmp imm
 		return o | (0x3<<24) | (0x5<<20);
+
+	case ACLZ:
+		// CLZ doesn't support .S
+		return (o & (0xf<<28)) | (0x16f<<16) | (0xf1<<4);
 	}
 	diag("bad rrr %d", a);
 	prasm(curp);

src/cmd/5l/optab.c

--- a/src/cmd/5l/optab.c
+++ b/src/cmd/5l/optab.c
@@ -236,5 +236,7 @@ Optab	optab[] =
 	
 	{ AUNDEF,		C_NONE,	C_NONE,	C_NONE,		96, 4, 0 },
 
+	{ ACLZ,		C_REG,	C_NONE,	C_REG,		97, 4, 0 },
+
 	{ AXXX,		C_NONE,	C_NONE,	C_NONE,		 0, 4, 0 },
 };

src/cmd/5l/span.c

--- a/src/cmd/5l/span.c
+++ b/src/cmd/5l/span.c
@@ -848,6 +848,7 @@ buildop(void)
 		case ATST:
 		case APLD:
 		case AUNDEF:
+		case ACLZ:
 			break;
 		}
 	}

src/pkg/math/big/arith_arm.s

--- a/src/pkg/math/big/arith_arm.s
+++ b/src/pkg/math/big/arith_arm.s
@@ -314,7 +314,7 @@ TEXT ·mulWW(SB),7,$0
 // func bitLen(x Word) (n int)
 TEXT ·bitLen(SB),7,$0
 	MOVW	x+0(FP), R0
-\tWORD	$0xe16f0f10 // CLZ R0, R0  (count leading zeros)
+\tCLZ 	R0, R0
 	MOVW	$32, R1
 	SUB.S	R0, R1
 	MOVW	R1, n+4(FP)

コアとなるコードの解説

src/cmd/5a/lex.c の変更

lex.cでは、Goアセンブラが認識する命令のリストにCLZが追加されています。

• "CLZ": アセンブリコードで記述される命令のニーモニック（名前）。
• LTYPE2: この命令が2つのオペランド（ソースとデスティネーション）を取ることを示すタイプ。
• ACLZ: リンカ内部でCLZ命令を識別するための定数。

これにより、アセンブラはCLZ R0, R0のような記述を正しく字句解析できるようになります。

src/cmd/5l/5.out.h の変更

5.out.hでは、リンカが使用する命令の列挙型にACLZが追加されています。これは、リンカがCLZ命令を内部的に処理する際に使用する一意の識別子となります。

src/cmd/5l/asm.c の変更

asm.cは、アセンブリ命令を実際の機械語に変換するリンカの核心部分です。

• case 97: /* CLZ Rm, Rd */: optab.cで定義されたCLZ命令のタイプ97に対応する処理ブロックです。
• o1 = oprrr(p->as, p->scond);: oprrr関数は、レジスタ-レジスタ-レジスタ形式の命令の共通部分の機械語を生成します。CLZ命令は、ソースレジスタとデスティネーションレジスタが同じである場合が多いですが、形式としてはレジスタ-レジスタ命令として扱われます。
• o1 |= p->to.reg << 12;: デスティネーションレジスタ（Rd）の番号を、ARM命令の機械語フォーマットにおける適切なビット位置（ビット12から15）にシフトしてo1にORします。
• o1 |= p->from.reg;: ソースレジスタ（Rm）の番号を、ARM命令の機械語フォーマットにおける適切なビット位置（ビット0から3）にシフトしてo1にORします。
• case ACLZ: のブロックでは、CLZ命令固有の機械語パターンが生成されます。0x16f<<16と0xf1<<4は、ARMのCLZ命令の特定のビットフィールド（命令の種類、オペランドのエンコーディングなど）を構成する定数です。CLZ命令は条件コード（.Sサフィックス）をサポートしないため、その点も考慮された機械語が生成されます。

src/cmd/5l/optab.c の変更

optab.cでは、リンカのオペコードテーブルにACLZのエントリが追加されています。

• { ACLZ, C_REG, C_NONE, C_REG, 97, 4, 0 }:
  • ACLZ: 命令の内部識別子。
  • C_REG: 最初のオペランドがレジスタであることを示す。
  • C_NONE: 2番目のオペランドがないことを示す（CLZは通常2つのレジスタオペランドを取るが、ここでは簡略化されているか、または特定の形式を指す）。
  • C_REG: 3番目のオペランド（結果を格納するレジスタ）がレジスタであることを示す。
  • 97: この命令のタイプ番号。asm.cのswitch文でこの番号が使われます。
  • 4: 命令のバイト長（ARM命令は通常4バイト）。
  • 0: フラグ。

このエントリにより、リンカはCLZ命令の構文と、それをどのように機械語に変換すべきかを認識します。

src/cmd/5l/span.c の変更

span.cは、リンカが命令のサイズを計算し、コードを配置する際に使用されます。buildop関数内のswitch文にcase ACLZ:が追加されたことで、CLZ命令も他の命令と同様に適切に処理され、コードの配置やジャンプ先の計算に影響を与えないようになります。

src/pkg/math/big/arith_arm.s の変更

arith_arm.sでは、bitLen関数の実装が変更されています。

• 変更前はWORD $0xe16f0f10という形でCLZ命令の機械語コードを直接埋め込んでいました。これは、アセンブラがCLZ命令を直接サポートしていない場合の回避策です。
• 変更後はCLZ R0, R0という、より可読性の高いアセンブリニーモニックを使用しています。これは、GoツールチェインがCLZ命令を正式にサポートしたため可能になりました。
• MOVW $32, R1とSUB.S R0, R1は、32ビット値のビット長を計算するロジックです。CLZ命令は先行ゼロの数を返すため、32からその値を引くことで、数値の有効なビット長（最上位ビットから見て最初に1が現れるまでのビット数）が得られます。

この変更により、math/bigパッケージのbitLen関数は、ARMv5以降のプロセッサでハードウェアのCLZ命令を直接利用できるようになり、パフォーマンスが向上します。

関連リンク

• Go CL (Change List) 6284043: https://golang.org/cl/6284043

参考にした情報源リンク

• ARM Architecture Reference Manual (CLZ instruction details)
• Go Assembly Language (Plan 9 Assembly): https://go.dev/doc/asm
• Go math/big package documentation: https://pkg.go.dev/math/big
• Count Leading Zeros - Wikipedia: https://en.wikipedia.org/wiki/Count_leading_zeros
• ARM Instruction Set Overview (for general ARM instruction format): https://developer.arm.com/documentation/ddi0406/c/ (具体的なバージョンはコミット当時のARMv5T/TEJのドキュメントを参照)