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

このコミットは、Goコンパイラのcmd/gcパッケージにおける最適化に関するものです。具体的には、整数型に対する2のべき乗による乗算（例: x * 8）を、より効率的な左ビットシフト演算（例: x << 3）に置き換えるための変更が加えられています。この最適化は、コンパイル時にコードのパフォーマンスを向上させることを目的としています。

コミット

commit 31072e41f4e2ed0a135c46816cb2a65daba12540
Author: Russ Cox <rsc@golang.org>
Date:   Thu Feb 14 14:54:00 2013 -0500

    cmd/gc: replace x*8 by x<<3 etc
    
    Fixes #4199.
    
    R=ken2
    CC=golang-dev
    https://golang.org/cl/7322081

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

https://github.com/golang/go/commit/31072e41f4e2ed0a135c46816cb2a65daba12540

元コミット内容

cmd/gc: replace x*8 by x<<3 etc

このコミットは、Goコンパイラのcmd/gc部分において、x * 8のような乗算をx << 3のようなビットシフトに置き換えることを目的としています。

変更の背景

コンパイラ最適化において、乗算は一般的にビットシフトよりも多くのCPUサイクルを必要とする演算です。特に、2のべき乗（2, 4, 8, 16など）による乗算は、対応するビットシフト演算（それぞれ1, 2, 3, 4ビットの左シフト）に置き換えることができます。この置き換えは、生成される機械語コードの効率を大幅に向上させ、プログラムの実行速度を速める効果があります。

このコミットは、Goコンパイラがこのような基本的な最適化を自動的に適用するようにすることで、開発者が明示的にビットシフトを使用しなくても、コンパイラが最適なコードを生成するように改善することを目的としています。コミットメッセージにあるFixes #4199は、この最適化が特定のバグやパフォーマンスの問題を解決するために導入されたことを示唆していますが、現在の公開されているGoのIssueトラッカーでは該当するIssueが見つかりませんでした。これは、古いIssueトラッカーの参照であるか、内部的なIssue番号である可能性があります。同様に、https://golang.org/cl/7322081も古いGoのコードレビューシステム（Gerrit）の変更リスト（Change-list, CL）へのリンクである可能性が高いですが、現在の公開システムでは直接アクセスできません。

前提知識の解説

• コンパイラ最適化: ソースコードを機械語コードに変換する際に、プログラムの実行速度を向上させたり、メモリ使用量を削減したりするために行われる変換プロセスです。
• ビットシフト演算: 整数型に対してビット単位で値を移動させる演算です。
  • 左ビットシフト (<<): 数値を左にNビットシフトすると、元の数値に2のN乗を掛けたのと同じ結果になります。例えば、x << 3はx * 2^3、つまりx * 8と同じです。
  • 右ビットシフト (>>): 数値を右にNビットシフトすると、元の数値を2のN乗で割ったのと同じ結果になります（整数除算）。
• cmd/gc: Go言語の公式コンパイラの一部で、Goのソースコードを中間表現に変換し、最終的に実行可能なバイナリを生成する役割を担っています。gcは「Go Compiler」の略です。
• walk.c: cmd/gcディレクトリ内のファイルで、コンパイラの「ウォーク」フェーズを担当します。このフェーズでは、抽象構文木（AST）を走査し、型チェック、定数畳み込み、一部の最適化、および中間コードへの変換などを行います。

技術的詳細

このコミットの核心は、walkmulという新しい静的関数がsrc/cmd/gc/walk.cに追加されたことです。この関数は、整数型の乗算ノード（OMUL）を処理し、乗算の右オペランドまたは左オペランドが2のべき乗である定数である場合に、その乗算を左ビットシフト演算に変換します。

walkmul関数のロジックは以下の通りです。

1. 型チェック: まず、乗算の対象が整数型であるかを確認します。整数型でない場合は、最適化を行わずに終了します。
2. 定数オペランドの特定: 乗算の2つのオペランド（左と右）のうち、どちらか一方がリテラル（定数）であるかをチェックします。定数でない場合は、最適化を行いません。
3. x * 0の最適化: 定数オペランドが0の場合、結果は0になるため、cheapexprで副作用を処理した後、ノードを定数0に置き換えます。
4. 2のべき乗の検出: 定数オペランドが2のべき乗であるかをpowtwo関数（既存の関数と推測される）で判定します。
   • powtwoは、定数が2のべき乗であればその指数を返し、負の2のべき乗（例: -16）であれば1000を加算した値を返します（例: -16はpow=4+1000）。
   • pow >= 1000の場合、負の2のべき乗として処理し、negフラグを立ててpowから1000を引きます。
5. シフト量のチェック: 計算されたシフト量powが、オペランドの型のビット幅（nl->type->width*8）を超えないことを確認します。
6. x * 1の最適化: シフト量powが0の場合（つまり、定数が1の場合）、乗算は不要であり、ノードを左オペランドに置き換えます。
7. シフト演算への変換: 上記の条件を満たす場合、乗算ノードを左ビットシフトノード（OLSH）に変換します。左オペランドは元の乗算の非定数オペランド、右オペランドは計算されたシフト量powを表す定数ノードになります。
8. 負の数への対応: もし元の定数が負の2のべき乗であった場合（negフラグが立っている場合）、最終的な結果にOMINUS（単項マイナス）演算子を適用して符号を反転させます。
9. 再帰的なウォーク: 変換されたノードに対してtypecheckとwalkexprを再帰的に呼び出し、さらなる最適化や処理を適用します。

このwalkmul関数は、walkexpr関数内のOMUL（乗算）ケースに追加され、乗算ノードが処理される際に呼び出されるようになりました。これにより、コンパイラは自動的にこの最適化を適用できるようになります。

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

src/cmd/gc/walk.cファイルに以下の変更が加えられています。

1. walkexpr関数のswitch文からOMULケースが削除され、独立したOMULケースが追加されました。
2. 新しい静的関数walkmulが追加されました。
3. walkmul関数のプロトタイプ宣言がファイルの先頭付近に追加されました。

--- a/src/cmd/gc/walk.c
+++ b/src/cmd/gc/walk.c
@@ -24,6 +24,7 @@ static	Node*	append(Node*, NodeList**);
 static	Node*	sliceany(Node*, NodeList**);
 static	void	walkcompare(Node**, NodeList**);
 static	void	walkrotate(Node**);
+static	void	walkmul(Node**, NodeList**); // 追加
 static	void	walkdiv(Node**, NodeList**);
 static	int	bounded(Node*, int64);
 static	Mpint	mpzero;
@@ -481,7 +482,6 @@ walkexpr(Node **np, NodeList **init)
 
 	case OAND:
 	case OSUB:
-	case OMUL: // 削除
 	case OHMUL:
 	case OLT:
 	case OLE:
@@ -932,6 +932,12 @@ walkexpr(Node **np, NodeList **init)
 		walkexpr(&n->right, init);
 		goto ret;
 
+	case OMUL: // 追加
+		walkexpr(&n->left, init);
+		walkexpr(&n->right, init);
+		walkmul(&n, init);
+		goto ret;
+
 	case ODIV:
 	case OMOD:
 		walkexpr(&n->left, init);
@@ -2897,6 +2903,70 @@ yes:
 	return;
 }
 
+/*
+ * walkmul rewrites integer multiplication by powers of two as shifts.
+ */
+static void
+walkmul(Node **np, NodeList **init)
+{
+	Node *n, *nl, *nr;
+	int pow, neg, w;
+	
+	n = *np;
+	if(!isint[n->type->etype])
+		return;
+
+	if(n->right->op == OLITERAL) {
+		nl = n->left;
+		nr = n->right;
+	} else if(n->left->op == OLITERAL) {
+		nl = n->right;
+		nr = n->left;
+	} else
+		return;
+
+	neg = 0;
+
+	// x*0 is 0 (and side effects of x).
+	if(mpgetfix(nr->val.u.xval) == 0) {
+		cheapexpr(nl, init);
+		nodconst(n, n->type, 0);
+		goto ret;
+	}
+
+	// nr is a constant.
+	pow = powtwo(nr);
+	if(pow < 0)
+		return;
+	if(pow >= 1000) {
+		// negative power of 2, like -16
+		neg = 1;
+		pow -= 1000;
+	}
+
+	w = nl->type->width*8;
+	if(pow+1 >= w)// too big, shouldn't happen
+		return;
+
+	nl = cheapexpr(nl, init);
+
+	if(pow == 0) {
+		// x*1 is x
+		n = nl;
+		goto ret;
+	}
+	
+	n = nod(OLSH, nl, nodintconst(pow));
+
+ret:
+	if(neg)
+		n = nod(OMINUS, n, N);
+
+	typecheck(&n, Erv);
+	walkexpr(&n, init);
+	*np = n;
+}
+
 /*
  * walkdiv rewrites division by a constant as less expensive
  * operations.

コアとなるコードの解説

追加されたwalkmul関数は、Goコンパイラのバックエンドにおける重要な最適化パスを実装しています。この関数は、抽象構文木（AST）の乗算ノードを分析し、定数による2のべき乗乗算をビットシフトに変換することで、生成される機械語コードの効率を高めます。

• Node *n, *nl, *nr;: nは現在の乗算ノード、nlは左オペランド、nrは右オペランドを指します。
• if(!isint[n->type->etype]) return;: 乗算の対象が整数型でない場合、この最適化は適用できないため、関数を終了します。
• if(n->right->op == OLITERAL) { ... } else if(n->left->op == OLITERAL) { ... } else return;: 乗算のどちらかのオペランドがリテラル（定数）であるかをチェックします。定数でない場合は、この最適化の対象外です。
• if(mpgetfix(nr->val.u.xval) == 0) { ... }: 定数オペランドが0の場合、乗算結果は0になるため、左オペランドの副作用を処理し（cheapexpr）、ノードを定数0に置き換えます。
• pow = powtwo(nr);: powtwo関数は、定数nrが2のべき乗であるかを判定し、その指数を返します。例えば、8であれば3を返します。負の2のべき乗（例: -16）の場合、特別な値（1000を加算した値）を返して区別します。
• if(pow >= 1000) { neg = 1; pow -= 1000; }: powが1000以上の場合、それは負の2のべき乗であることを意味するため、negフラグを立てて実際の指数を計算します。
• w = nl->type->width*8; if(pow+1 >= w) return;: シフト量powが、オペランドの型が表現できるビット幅を超えないことを確認します。これはオーバーフローを防ぐためのチェックです。
• nl = cheapexpr(nl, init);: 左オペランドに副作用がある場合、それを処理します。
• if(pow == 0) { n = nl; goto ret; }: シフト量が0の場合（つまり、定数が1の場合）、x * 1はxと同じなので、ノードを左オペランドに置き換えます。
• n = nod(OLSH, nl, nodintconst(pow));: ここが最適化の核心です。乗算ノードを左ビットシフトノード（OLSH）に変換します。nlがシフトされる値、nodintconst(pow)がシフト量です。
• if(neg) n = nod(OMINUS, n, N);: 元の定数が負の2のべき乗であった場合、シフト結果に単項マイナス演算子を適用して正しい符号にします。
• typecheck(&n, Erv); walkexpr(&n, init); *np = n;: 変換されたノードに対して型チェックを行い、さらにwalkexprを再帰的に呼び出すことで、変換後のノードに対するさらなる最適化や処理を可能にします。最後に、元のノードポインタ*npを新しいノードnで更新します。

この一連の処理により、コンパイラはx * 8のようなコードを自動的にx << 3のような効率的なコードに変換し、Goプログラムの実行性能を向上させます。

関連リンク

• Go言語のコンパイラに関するドキュメントやブログ記事
• コンパイラ最適化に関する一般的な情報（例: ビットシフト最適化）

参考にした情報源リンク

• Go言語の公式ドキュメント (go.dev)
• Go言語のソースコード (github.com/golang/go)
• コンパイラ最適化に関する一般的な情報源 (例: Wikipedia, コンパイラ設計の教科書)