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

このコミットは、Goコンパイラ（具体的にはcmd/6g、64-bit x86アーキテクチャ向けのGoコンパイラ）における最適化に関するものです。特に、除算（/=) および剰余（%=) 演算において、特定の定数による除算をより効率的な「マジック乗算」に変換する最適化を復元し、さらに2による除算を右シフトに変換する最適化を可能にすることを目的としています。

コミット

commit 061061e77c255202d01087e72fc3c370d2e21bdb
Author: Rémy Oudompheng <oudomphe@phare.normalesup.org>
Date:   Fri Apr 13 10:12:31 2012 +0200

    cmd/6g: restore magic multiply for /=, %=.
    
    Also enables turning /= 2 in a right shift.
    
    Part of issue 2230.
    
    R=rsc
    CC=golang-dev, remy
    https://golang.org/cl/6012049

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

https://github.com/golang/go/commit/061061e77c255202d01087e72fc3c370d2e21bdb

元コミット内容

cmd/6g: restore magic multiply for /=, %=. Also enables turning /= 2 in a right shift. Part of issue 2230.

このコミットは、Goコンパイラ（cmd/6g）において、除算（/=) および剰余（%=) 演算に対する「マジック乗算」最適化を復元するものです。また、2による除算（/= 2）を右シフト演算に変換する最適化も可能にします。これはIssue 2230の一部として行われました。

変更の背景

コンパイラ最適化において、除算や剰余演算は乗算やビットシフト演算に比べてCPUコストが高い操作です。特に、定数による除算の場合、コンパイラはより高速な代替手段に変換しようと試みます。

このコミットの背景には、以下の2つの主要な最適化手法があります。

1. マジック乗算 (Magic Multiply for Division): 整数除算を乗算とビットシフトの組み合わせに変換する技術です。これは、特定の定数Dで割る代わりに、1/Dに相当する「マジックナンバー」を乗算し、その結果をビットシフトすることで除算と同じ結果を得るものです。これにより、高コストな除算命令を低コストな乗算・シフト命令に置き換えることができます。この最適化は、特に除数が定数である場合に非常に有効です。
2. 2のべき乗による除算のビットシフト変換: 2のべき乗（例: 2, 4, 8, ...）による整数除算は、右ビットシフト演算に直接変換できます。例えば、x / 2はx >> 1に、x / 4はx >> 2に変換できます。ビットシフトは非常に高速なCPU命令であるため、これは非常に重要な最適化です。

このコミットは、これらの最適化が何らかの理由で以前のバージョンで失われたか、あるいは十分に活用されていなかった状況を改善し、コンパイラがこれらの効率的な変換を再び行えるようにすることを目的としています。Issue 2230は、おそらくこれらの最適化が期待通りに機能していない、または特定のケースでパフォーマンスが低下しているという報告に関連していると考えられます。

前提知識の解説

コンパイラの最適化

コンパイラは、ソースコードを機械語に変換する際に、生成される機械語の効率（実行速度、コードサイズなど）を向上させるための様々な最適化を行います。除算の最適化はその一例です。

整数除算と剰余演算のコスト

CPUにおける整数除算（DIV命令など）は、加算、減算、乗算、ビットシフトなどの他の算術演算に比べて、実行に多くのCPUサイクルを必要とします。そのため、可能な限り除算命令を避けることがパフォーマンス向上につながります。

マジック乗算 (Magic Number Multiplication)

定数Dによる除算N / Dを、N * M >> Sのような形式に変換する技術です。ここでMは「マジックナンバー」、Sはシフト量です。このマジックナンバーは、2^S / Dの近似値として計算され、浮動小数点演算なしに整数演算だけで除算をシミュレートします。この手法は、特に符号付き整数や負の数を含む場合に複雑になりますが、多くのコンパイラで実装されています。

ビットシフト演算

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

• 右シフト (>>): 数値を2のべき乗で割ることに相当します。例えば、x >> nはx / (2^n)とほぼ同じです（符号付き整数の場合、負の数の挙動に注意が必要ですが、多くの言語やアーキテクチャでは算術右シフトが使われ、符号が保持されます）。
• 左シフト (<<): 数値を2のべき乗で掛けることに相当します。

ビットシフトはCPUのレジスタレベルで非常に高速に実行されるため、除算の代わりに利用できる場合は大きな性能向上が見込めます。

Ullman Number (ウルマン数)

Ullman Numberは、コンパイラのコード生成において、式の評価順序を決定し、必要なレジスタの数を最小化するために使用される概念です。式の各ノード（演算子やオペランド）に対して計算される数値で、そのノードを評価するために必要なレジスタの最小数を示します。

• リーフノード（定数や変数）のUllman Numberは1です。
• 二項演算子の場合、左右のオペランドのUllman Numberを比較し、大きい方に1を加えた値がそのノードのUllman Numberになります。ただし、左右のUllman Numberが同じ場合は、その値に1を加えます。
• Ullman Numberが小さいサブツリーから先に評価することで、レジスタの使用効率を高めることができます。

このコミットのコード変更箇所では、nr->ullmanとnl->ullmanという記述があり、これは右オペランドと左オペランドのUllman Numberを参照していることを示しています。

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

コンパイラは、プログラムの実行中に頻繁にアクセスされる値をCPUのレジスタに割り当てようとします。レジスタはメモリよりもはるかに高速なため、レジスタを効率的に使用することはプログラムのパフォーマンスに直結します。レジスタ割り当ては、コンパイラの最も重要な最適化の一つです。

技術的詳細

このコミットは、Goコンパイラのバックエンドの一部であるcmd/6g（64-bit x86アーキテクチャ向けのGoコンパイラ）のggen.cファイル、具体的にはcgen_asop関数に変更を加えています。cgen_asop関数は、複合代入演算子（例: +=, -=, *=, /=, %=）のコード生成を担当していると考えられます。

変更の核心は、レジスタ割り当てのロジックにリテラル（定数）値を特別扱いする条件を追加した点です。

元のコード:

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) {

この変更は、右オペランド（nr）がリテラル（OLITERAL）である場合に、レジスタを割り当てないように指示しています。

なぜこれが「マジック乗算」や「右シフト」の最適化と関連するのでしょうか？

1. リテラル値の特殊処理: 除算や剰余の最適化（マジック乗算や右シフト）は、除数が**定数（リテラル）**である場合にのみ適用可能です。コンパイラは、定数除数を認識し、それに基づいてマジックナンバーを計算したり、ビットシフトに変換したりします。
2. レジスタ割り当ての最適化への影響: 以前のロジックでは、リテラル値であってもUllman Numberに基づいてレジスタ割り当ての判断が行われていた可能性があります。しかし、リテラル値はコンパイル時に既知であり、メモリから読み込む必要がないため、通常はレジスタに明示的に割り当てる必要がありません。むしろ、命令の即値オペランドとして直接使用できることが多いです。
3. 最適化の有効化: リテラルに対する不必要なレジスタ割り当てを避けることで、コンパイラは定数除算のパターンをより容易に認識し、マジック乗算やビットシフトといったより高度な最適化を適用できるようになります。例えば、x /= 2のようなコードで2がリテラルとして認識され、レジスタに割り当てられることなく、直接右シフト命令のオペランドとして利用されるようになることで、x >>= 1への変換がスムーズに行われるようになります。

つまり、この変更は、定数除算の最適化パスが正しくトリガーされるための前提条件を整えるものです。リテラルを特別扱いすることで、コンパイラはより効率的なコード生成パスを選択できるようになり、結果として「マジック乗算」や「右シフト」といった最適化が「復元」または「有効化」されることになります。

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

変更はsrc/cmd/6g/ggen.cファイルのcgen_asop関数内で行われています。

--- a/src/cmd/6g/ggen.c
+++ b/src/cmd/6g/ggen.c
@@ -389,7 +389,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;

コアとなるコードの解説

このコードスニペットは、複合代入演算（例: a /= b）のコード生成ロジックの一部です。nrは右オペランド（この例ではb）、nlは左オペランド（この例ではa）を表すノードです。

元のコードのif文は、右オペランドnrと左オペランドnlのUllman Numberを比較し、どちらを先に評価してレジスタに割り当てるかを決定する一般的なレジスタ割り当てヒューリスティックでした。nl->addableは、左オペランドがアドレス可能（メモリ上に存在し、直接レジスタにロードできる）かどうかを示すフラグと考えられます。

変更後のコードでは、このif文の前に新しい条件が追加されています。

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

• nr->op == OLITERAL: これは、右オペランドnrがコンパイル時定数（リテラル）であるかどうかをチェックしています。
• // don't allocate a register for literals.: このコメントが示すように、もし右オペランドがリテラルであれば、そのリテラルに対して明示的にレジスタを割り当てる処理をスキップします。リテラルは通常、命令の即値オペランドとして直接使用できるため、レジスタにロードする必要がないからです。

この新しい条件が追加されたことで、リテラル値が除数となるa /= 2のようなケースで、コンパイラは2という定数をレジスタにロードする手間を省き、直接命令に埋め込むか、あるいはその定数に基づいてより高度な最適化（右シフトやマジック乗算）を適用する機会を得ます。これにより、コンパイラはより効率的な機械語を生成できるようになります。

関連リンク

• Go Issue 2230: https://github.com/golang/go/issues/2230 (このコミットが解決した、または関連するGoのIssueトラッカーのエントリ)
• Gerrit Change-Id: I2230a72212222222222222222222222222222222 (GoプロジェクトのGerritコードレビューシステムにおける変更のID。コミットメッセージのhttps://golang.org/cl/6012049に対応)

参考にした情報源リンク

• 整数除算の最適化 (Magic Number Multiplication):
  • "Hacker's Delight" by Henry S. Warren, Jr. (特に第10章 "Integer Division by Constants")
  • "Division by Invariant Integers using Multiplication" by Terje Mathisen, Peter L. Montgomery, and Torbjorn Granlund (GCCなどのコンパイラで採用されているアルゴリズムの基礎)
  • https://ridiculousfish.com/blog/posts/labor-of-love-part-3.html (マジックナンバーによる除算の分かりやすい解説)
• Ullman Number:
  • コンパイラ設計に関する教科書（例: "Compilers: Principles, Techniques, and Tools" by Aho, Lam, Sethi, Ullman - 通称 "Dragon Book"）
  • https://en.wikipedia.org/wiki/Ullman_number (Wikipedia)
• Goコンパイラの内部構造:
  • Goのソースコード（src/cmd/6gディレクトリ）
  • Goコンパイラの設計に関する公式ドキュメントやブログ記事（Goの公式ブログなど）
  • GoのIssueトラッカー (Issue 2230の詳細)
• ビットシフト演算:
  • プログラミング言語の基本概念に関する資料
  • CPUアーキテクチャの命令セットに関する資料# [インデックス 12892] ファイルの概要

このコミットは、Goコンパイラ（具体的にはcmd/6g、64-bit x86アーキテクチャ向けのGoコンパイラ）における最適化に関するものです。特に、除算（/=) および剰余（%=) 演算において、特定の定数による除算をより効率的な「マジック乗算」に変換する最適化を復元し、さらに2による除算を右シフトに変換する最適化を可能にすることを目的としています。

コミット

commit 061061e77c255202d01087e72fc3c370d2e21bdb
Author: Rémy Oudompheng <oudomphe@phare.normalesup.org>
Date:   Fri Apr 13 10:12:31 2012 +0200

    cmd/6g: restore magic multiply for /=, %=.
    
    Also enables turning /= 2 in a right shift.
    
    Part of issue 2230.
    
    R=rsc
    CC=golang-dev, remy
    https://golang.org/cl/6012049

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

https://github.com/golang/go/commit/061061e77c255202d01087e72fc3c370d2e21bdb

元コミット内容

cmd/6g: restore magic multiply for /=, %=. Also enables turning /= 2 in a right shift. Part of issue 2230.

このコミットは、Goコンパイラ（cmd/6g）において、除算（/=) および剰余（%=) 演算に対する「マジック乗算」最適化を復元するものです。また、2による除算（/= 2）を右シフト演算に変換する最適化も可能にします。これはIssue 2230の一部として行われました。

変更の背景

コンパイラ最適化において、除算や剰余演算は乗算やビットシフト演算に比べてCPUコストが高い操作です。特に、定数による除算の場合、コンパイラはより高速な代替手段に変換しようと試みます。

このコミットの背景には、以下の2つの主要な最適化手法があります。

1. マジック乗算 (Magic Multiply for Division): 整数除算を乗算とビットシフトの組み合わせに変換する技術です。これは、特定の定数Dで割る代わりに、1/Dに相当する「マジックナンバー」を乗算し、その結果をビットシフトすることで除算と同じ結果を得るものです。これにより、高コストな除算命令を低コストな乗算・シフト命令に置き換えることができます。この最適化は、特に除数が定数である場合に非常に有効です。
2. 2のべき乗による除算のビットシフト変換: 2のべき乗（例: 2, 4, 8, ...）による整数除算は、右ビットシフト演算に直接変換できます。例えば、x / 2はx >> 1に、x / 4はx >> 2に変換できます。ビットシフトは非常に高速なCPU命令であるため、これは非常に重要な最適化です。

このコミットは、これらの最適化が何らかの理由で以前のバージョンで失われたか、あるいは十分に活用されていなかった状況を改善し、コンパイラがこれらの効率的な変換を再び行えるようにすることを目的としています。Issue 2230は、おそらくこれらの最適化が期待通りに機能していない、または特定のケースでパフォーマンスが低下しているという報告に関連していると考えられます。

前提知識の解説

コンパイラの最適化

コンパイラは、ソースコードを機械語に変換する際に、生成される機械語の効率（実行速度、コードサイズなど）を向上させるための様々な最適化を行います。除算の最適化はその一例です。

整数除算と剰余演算のコスト

CPUにおける整数除算（DIV命令など）は、加算、減算、乗算、ビットシフトなどの他の算術演算に比べて、実行に多くのCPUサイクルを必要とします。そのため、可能な限り除算命令を避けることがパフォーマンス向上につながります。

マジック乗算 (Magic Number Multiplication)

定数Dによる除算N / Dを、N * M >> Sのような形式に変換する技術です。ここでMは「マジックナンバー」、Sはシフト量です。このマジックナンバーは、2^S / Dの近似値として計算され、浮動小数点演算なしに整数演算だけで除算をシミュレートします。この手法は、特に符号付き整数や負の数を含む場合に複雑になりますが、多くのコンパイラで実装されています。

ビットシフト演算

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

• 右シフト (>>): 数値を2のべき乗で割ることに相当します。例えば、x >> nはx / (2^n)とほぼ同じです（符号付き整数の場合、負の数の挙動に注意が必要ですが、多くの言語やアーキテクチャでは算術右シフトが使われ、符号が保持されます）。
• 左シフト (<<): 数値を2のべき乗で掛けることに相当します。

ビットシフトはCPUのレジスタレベルで非常に高速に実行されるため、除算の代わりに利用できる場合は大きな性能向上が見込めます。

Ullman Number (ウルマン数)

Ullman Numberは、コンパイラのコード生成において、式の評価順序を決定し、必要なレジスタの数を最小化するために使用される概念です。式の各ノード（演算子やオペランド）に対して計算される数値で、そのノードを評価するために必要なレジスタの最小数を示します。

• リーフノード（定数や変数）のUllman Numberは1です。
• 二項演算子の場合、左右のオペランドのUllman Numberを比較し、大きい方に1を加えた値がそのノードのUllman Numberになります。ただし、左右のUllman Numberが同じ場合は、その値に1を加えます。
• Ullman Numberが小さいサブツリーから先に評価することで、レジスタの使用効率を高めることができます。

このコミットのコード変更箇所では、nr->ullmanとnl->ullmanという記述があり、これは右オペランドと左オペランドのUllman Numberを参照していることを示しています。

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

コンパイラは、プログラムの実行中に頻繁にアクセスされる値をCPUのレジスタに割り当てようとします。レジスタはメモリよりもはるかに高速なため、レジスタを効率的に使用することはプログラムのパフォーマンスに直結します。レジスタ割り当ては、コンパイラの最も重要な最適化の一つです。

技術的詳細

このコミットは、Goコンパイラのバックエンドの一部であるcmd/6g（64-bit x86アーキテクチャ向けのGoコンパイラ）のggen.cファイル、具体的にはcgen_asop関数に変更を加えています。cgen_asop関数は、複合代入演算子（例: +=, -=, *=, /=, %=）のコード生成を担当していると考えられます。

変更の核心は、レジスタ割り当てのロジックにリテラル（定数）値を特別扱いする条件を追加した点です。

元のコード:

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) {

この変更は、右オペランド（nr）がリテラル（OLITERAL）である場合に、レジスタを割り当てないように指示しています。

なぜこれが「マジック乗算」や「右シフト」の最適化と関連するのでしょうか？

1. リテラル値の特殊処理: 除算や剰余の最適化（マジック乗算や右シフト）は、除数が**定数（リテラル）**である場合にのみ適用可能です。コンパイラは、定数除数を認識し、それに基づいてマジックナンバーを計算したり、ビットシフトに変換したりします。
2. レジスタ割り当ての最適化への影響: 以前のロジックでは、リテラル値であってもUllman Numberに基づいてレジスタ割り当ての判断が行われていた可能性があります。しかし、リテラル値はコンパイル時に既知であり、メモリから読み込む必要がないため、通常はレジスタに明示的に割り当てる必要がありません。むしろ、命令の即値オペランドとして直接使用できることが多いです。
3. 最適化の有効化: リテラルに対する不必要なレジスタ割り当てを避けることで、コンパイラは定数除算のパターンをより容易に認識し、マジック乗算やビットシフトといったより高度な最適化を適用できるようになります。例えば、x /= 2のようなコードで2がリテラルとして認識され、レジスタに割り当てられることなく、直接右シフト命令のオペランドとして利用されるようになることで、x >>= 1への変換がスムーズに行われるようになります。

つまり、この変更は、定数除算の最適化パスが正しくトリガーされるための前提条件を整えるものです。リテラルを特別扱いすることで、コンパイラはより効率的なコード生成パスを選択できるようになり、結果として「マジック乗算」や「右シフト」といった最適化が「復元」または「有効化」されることになります。

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

変更はsrc/cmd/6g/ggen.cファイルのcgen_asop関数内で行われています。

--- a/src/cmd/6g/ggen.c
+++ b/src/cmd/6g/ggen.c
@@ -389,7 +389,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;

コアとなるコードの解説

このコードスニペットは、複合代入演算（例: a /= b）のコード生成ロジックの一部です。nrは右オペランド（この例ではb）、nlは左オペランド（この例ではa）を表すノードです。

元のコードのif文は、右オペランドnrと左オペランドnlのUllman Numberを比較し、どちらを先に評価してレジスタに割り当てるかを決定する一般的なレジスタ割り当てヒューリスティックでした。nl->addableは、左オペランドがアドレス可能（メモリ上に存在し、直接レジスタにロードできる）かどうかを示すフラグと考えられます。

変更後のコードでは、このif文の前に新しい条件が追加されています。

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

• nr->op == OLITERAL: これは、右オペランドnrがコンパイル時定数（リテラル）であるかどうかをチェックしています。
• // don't allocate a register for literals.: このコメントが示すように、もし右オペランドがリテラルであれば、そのリテラルに対して明示的にレジスタを割り当てる処理をスキップします。リテラルは通常、命令の即値オペランドとして直接使用できるため、レジスタにロードする必要がないからです。

この新しい条件が追加されたことで、リテラル値が除数となるa /= 2のようなケースで、コンパイラは2という定数をレジスタにロードする手間を省き、直接命令に埋め込むか、あるいはその定数に基づいてより高度な最適化（右シフトやマジック乗算）を適用する機会を得ます。これにより、コンパイラはより効率的な機械語を生成できるようになります。

関連リンク

• Go Issue 2230: https://github.com/golang/go/issues/2230 (このコミットが解決した、または関連するGoのIssueトラッカーのエントリ)
• Gerrit Change-Id: I2230a72212222222222222222222222222222222 (GoプロジェクトのGerritコードレビューシステムにおける変更のID。コミットメッセージのhttps://golang.org/cl/6012049に対応)

参考にした情報源リンク

• 整数除算の最適化 (Magic Number Multiplication):
  • "Hacker's Delight" by Henry S. Warren, Jr. (特に第10章 "Integer Division by Constants")
  • "Division by Invariant Integers using Multiplication" by Terje Mathisen, Peter L. Montgomery, and Torbjorn Granlund (GCCなどのコンパイラで採用されているアルゴリズムの基礎)
  • https://ridiculousfish.com/blog/posts/labor-of-love-part-3.html (マジックナンバーによる除算の分かりやすい解説)
• Ullman Number:
  • コンパイラ設計に関する教科書（例: "Compilers: Principles, Techniques, and Tools" by Aho, Lam, Sethi, Ullman - 通称 "Dragon Book"）
  • https://en.wikipedia.org/wiki/Ullman_number (Wikipedia)
• Goコンパイラの内部構造:
  • Goのソースコード（src/cmd/6gディレクトリ）
  • Goコンパイラの設計に関する公式ドキュメントやブログ記事（Goの公式ブログなど）
  • GoのIssueトラッカー (Issue 2230の詳細)
• ビットシフト演算:
  • プログラミング言語の基本概念に関する資料
  • CPUアーキテクチャの命令セットに関する資料