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

このコミットは、Go言語のコンパイラの一部である src/cmd/5g/ggen.c ファイルに対する変更を扱っています。このファイルは、ARMアーキテクチャ向けのGoコンパイラ（5g）におけるコード生成ロジック、特にシフト演算の最適化に関連する部分です。

コミット

commit d8008a9eef07e235358f0f7ca94a729aad4aa3b1
Author: Dave Cheney <dave@cheney.net>
Date:   Sun Nov 4 20:06:37 2012 +1100

    cmd/5g: improve shift code generation
    
    This CL is a backport of 6012049 which improves code
    generation for shift operations.
    
    benchmark       old ns/op    new ns/op    delta
    BenchmarkLSL            9            5  -49.67%
    BenchmarkLSR            9            4  -50.00%
    
    R=golang-dev, minux.ma, r, rsc
    CC=golang-dev
    https://golang.org/cl/6813045

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

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

元コミット内容

cmd/5g: シフトコード生成の改善

この変更リスト（CL）は、シフト操作のコード生成を改善する6012049のバックポートです。

ベンチマーク結果:

benchmark       old ns/op    new ns/op    delta
BenchmarkLSL            9            5  -49.67%
BenchmarkLSR            9            4  -50.00%

レビュー担当者: golang-dev, minux.ma, r, rsc CC: golang-dev 関連CL: https://golang.org/cl/6813045

変更の背景

このコミットの主な目的は、Go言語のARMアーキテクチャ向けコンパイラ（cmd/5g）におけるシフト演算のコード生成効率を向上させることです。コミットメッセージに示されているベンチマーク結果が示すように、BenchmarkLSL（論理左シフト）とBenchmarkLSR（論理右シフト）の両方で、実行時間が約50%削減されています。これは、シフト操作が頻繁に行われるような計算集約型のアプリケーションにおいて、顕著なパフォーマンス向上をもたらす可能性を秘めています。

この変更は、元々別の変更リスト（CL 6012049）で導入された改善の「バックポート」です。バックポートとは、あるブランチ（この場合はおそらくより新しい開発ブランチ）で行われた変更を、別のブランチ（この場合は安定版または特定のリリースブランチ）に適用するプロセスを指します。これにより、新しい機能や最適化が、より広範なユーザーベースに迅速に提供されることになります。

具体的な問題点としては、コンパイラがシフト演算の右オペランド（シフト量）がリテラル値（定数）である場合に、不必要なレジスタ割り当てを行っていたことが考えられます。リテラル値はプログラム実行中に変化しないため、レジスタにロードする必要がない場合が多く、直接命令に埋め込むことで効率的なコードを生成できます。このコミットは、この非効率性を解消し、より最適化された機械語命令を生成することを目指しています。

前提知識の解説

Goコンパイラとcmd/5g

Go言語のコンパイラは、ソースコードを機械語に変換するツールチェーンです。Goはクロスコンパイルを強力にサポートしており、異なるCPUアーキテクチャやオペレーティングシステム向けにバイナリを生成できます。 cmd/5gは、Goコンパイラツールチェーンの一部であり、具体的にはARMアーキテクチャ（GOARCH=arm）向けのGoプログラムをコンパイルする際に使用されるコンパイラです。Goのコンパイラは、gc（Go Compiler）という名前で知られる主要なコンパイラ群の一部であり、5gはそのARM版を指します（歴史的に、8gはx86-64、6gはx86、5gはARMを指していました）。

コード生成

コード生成は、コンパイラの最終段階の一つで、抽象構文木（AST）や中間表現（IR）から、ターゲットとなるCPUアーキテクチャの機械語命令を生成するプロセスです。この段階では、レジスタ割り当て、命令スケジューリング、最適化などが行われ、最終的な実行可能バイナリの性能に大きく影響します。

シフト演算

シフト演算は、数値のビットを左右に移動させる操作です。

• 論理左シフト (LSL: Logical Shift Left): ビットを左に移動させ、右から0を埋めます。実質的に2のべき乗を掛ける操作に相当します。
• 論理右シフト (LSR: Logical Shift Right): ビットを右に移動させ、左から0を埋めます。符号なし整数に対しては2のべき乗で割る操作に相当します。 これらの操作は、低レベルのプログラミングやビット操作、パフォーマンスが重要な場面で頻繁に使用されます。

レジスタ割り当て

CPUには、データを一時的に保持するための高速な記憶領域であるレジスタがあります。コンパイラは、プログラムの変数をこれらのレジスタに効率的に割り当てることで、メモリへのアクセス回数を減らし、プログラムの実行速度を向上させます。レジスタ割り当てはコンパイラの重要な最適化の一つです。不必要なレジスタ割り当ては、レジスタの枯渇や余分なロード/ストア命令の発生につながり、性能を低下させます。

Ullman Number (ウルマン数)

Ullman Number（ウルマン数）は、コンパイラのコード生成において、式の評価順序を決定し、レジスタ割り当てを最適化するためのヒューリスティックです。式の各ノード（演算子やオペランド）に対して計算される数値で、そのノードを評価するために必要なレジスタの最小数を示唆します。Ullman Numberが大きいオペランドから先に評価することで、レジスタの使用効率を高め、レジスタスピル（レジスタからメモリへの退避）を減らすことができます。

OLITERAL

OLITERALは、Goコンパイラの内部で使われるノードタイプの一つで、ソースコード中のリテラル値（例: 10, 3.14, "hello"など）を表します。コンパイラは、これらのリテラル値を特別に扱い、多くの場合、実行時にレジスタにロードするのではなく、直接機械語命令の一部として埋め込むことで効率化を図ります。

技術的詳細

このコミットは、src/cmd/5g/ggen.cファイル内のcgen_asop関数に焦点を当てています。cgen_asop関数は、代入演算子（例: a = b << c のような形式）のコードを生成する役割を担っています。

変更前のコードでは、シフト演算の右オペランド（nr）がリテラル値であるかどうかにかかわらず、nr->ullman >= nl->ullman || nl->addableという条件に基づいてレジスタ割り当ての判断を行っていました。この条件は、Ullman Numberやオペランドが「addable」（アドレス可能、つまりメモリから直接アクセス可能か、レジスタにロードしやすいか）であるかどうかに基づいて、どちらのオペランドを先に評価し、レジスタにロードするかを決定するための一般的なヒューリスティックです。

しかし、シフト演算の右オペランドがリテラル値である場合、その値はコンパイル時に既知であり、実行中に変化することはありません。このようなリテラル値に対してレジスタを割り当てることは、多くの場合、不必要であり、レジスタ資源の無駄遣いにつながります。レジスタは限られた資源であり、不必要な割り当ては、他の重要な値がレジスタに保持できなくなり、メモリへのスピル（退避）が発生する原因となります。メモリへのアクセスはレジスタへのアクセスよりもはるかに遅いため、これがパフォーマンスのボトルネックとなることがあります。

このコミットの変更は、この非効率性を解消するために、if文の条件を修正しています。具体的には、nr->op == OLITERALという新しい条件が追加されました。これは、「もし右オペランド（nr）がリテラル値であるならば、レジスタを割り当てない」という明確な指示をコンパイラに与えるものです。

// 変更前
if(nr->ullman >= nl->ullman || nl->addable) {
    // ... レジスタ割り当てとコード生成 ...
}

// 変更後
if(nr->op == OLITERAL) {
    // don't allocate a register for literals.
} else if(nr->ullman >= nl->ullman || nl->addable) {
    // ... レジスタ割り当てとコード生成 ...
}

この変更により、コンパイラはシフト演算の右オペランドがリテラルである場合に、レジスタ割り当てのロジックをスキップし、より直接的かつ効率的な機械語命令（例: シフト量を命令の即値として埋め込むなど）を生成できるようになります。これにより、レジスタの利用効率が向上し、結果としてベンチマークで示されたような大幅なパフォーマンス改善が実現されました。

ベンチマーク結果の具体的な数値は以下の通りです。

• BenchmarkLSL: 9 ns/op から 5 ns/op へ（-49.67%）
• BenchmarkLSR: 9 ns/op から 4 ns/op へ（-50.00%） これは、シフト操作1回あたりの平均実行時間が約半分になったことを意味し、特にビット操作が多用される場面でのGoプログラムの実行速度に大きな影響を与えます。

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

--- a/src/cmd/5g/ggen.c
+++ b/src/cmd/5g/ggen.c
@@ -407,7 +407,9 @@ cgen_asop(Node *n)
 hard:
 	n2.op = 0;
 	n1.op = 0;
-	if(nr->ullman >= nl->ullman || nl->addable) {
+	if(nr->op == OLITERAL) {
+		// don't allocate a register for literals.
+	} else if(nr->ullman >= nl->ullman || nl->addable) {
 		regalloc(&n2, nr->type, N);
 		cgen(nr, &n2);
 		nr = &n2;

コアとなるコードの解説

変更は、cgen_asop関数内のhard:ラベルの直後にあるif文の条件にあります。

変更前:

if(nr->ullman >= nl->ullman || nl->addable) {
    // ...
}

この条件は、右オペランド（nr）のUllman Numberが左オペランド（nl）以上であるか、または左オペランドが「addable」である場合に、右オペランドに対してレジスタを割り当て、そのコードを生成するというロジックでした。これは一般的なレジスタ割り当てのヒューリスティックですが、リテラル値の特殊性を考慮していませんでした。

変更後:

if(nr->op == OLITERAL) {
    // don't allocate a register for literals.
} else if(nr->ullman >= nl->ullman || nl->addable) {
    // ...
}

新しいコードでは、まず最初にnr->op == OLITERALという条件が追加されました。

• nr->op == OLITERAL: これは、シフト演算の右オペランド（シフト量）がコンパイラ内部でリテラル値として認識されているかどうかをチェックします。
• もし右オペランドがリテラル値であれば、その後のブロック（コメント// don't allocate a register for literals.がある部分）が実行されます。このブロックは空であり、明示的にレジスタ割り当てのロジックをスキップします。これにより、リテラル値に対して不必要なレジスタが割り当てられるのを防ぎます。
• リテラル値でない場合（else if）、元のnr->ullman >= nl->ullman || nl->addableという条件が評価され、通常のレジスタ割り当てとコード生成のロジックが適用されます。

この変更の核心は、リテラル値の特性を特別扱いすることで、コンパイラがより効率的な機械語命令を生成できるようにした点にあります。リテラル値は実行時に変化しないため、レジスタにロードする手間を省き、直接命令のオペランドとして利用できる場合が多いです。これにより、命令数やレジスタの競合が減少し、結果として実行速度が向上します。

関連リンク

• Go CL 6813045: https://golang.org/cl/6813045

参考にした情報源リンク

• Go言語のコンパイラに関する一般的な情報 (Go Compiler, cmd/gc, cmd/5gなど)
• コンパイラの最適化、特にレジスタ割り当てとUllman Numberに関する情報
• ビットシフト演算 (LSL, LSR) の概念
• Gitのバックポートに関する情報