Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

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

このコミットは、Goコンパイラの一部であるcmd/8gにおける、小さな整数定数最適化のロールバックに関するものです。具体的には、以前導入された最適化がレジスタ不足を引き起こす問題に対処するため、その最適化を元に戻しています。また、この変更に関連するバグを再現するための新しいテストファイルtest/fixedbugs/bug451.goが追加されています。

コミット

commit 251199c430929d072cbe4cc8dc97659fa3d1ce6a
Author: Nigel Tao <nigeltao@golang.org>
Date:   Thu Aug 23 16:17:22 2012 +1000

    cmd/8g: roll back the small integer constant optimizations introduced
    in 13416:67c0b8c8fb29 "faster code, mainly for rotate" [1]. The codegen
    can run out of registers if there are too many small-int arithmetic ops.
    
    An alternative approach is to copy 6g's sbop/abop codegen to 8g, but
    this change is less risky.
    
    Fixes #3835.
    
    [1] http://code.google.com/p/go/source/diff?spec=svn67c0b8c8fb29b1b7b6221977af6b89cae787b941&name=67c0b8c8fb29&r=67c0b8c8fb29b1b7b6221977af6b89cae787b941&format=side&path=/src/cmd/8g/cgen.c
    
    R=rsc, remyoudompheng, r
    CC=golang-dev
    https://golang.org/cl/6450163

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

https://github.com/golang/go/commit/251199c430929d072cbe4cc8dc97659fa3d1ce6a

元コミット内容

cmd/8g: roll back the small integer constant optimizations introduced
in 13416:67c0b8c8fb29 "faster code, mainly for rotate" [1]. The codegen
can run out of registers if there are too many small-int arithmetic ops.

An alternative approach is to copy 6g's sbop/abop codegen to 8g, but
this change is less risky.

Fixes #3835.

[1] http://code.google.com/p/go/source/diff?spec=svn67c0b8c8fb29b1b7b6221977af6b89cae787b941&name=67c0b8c8fb29&r=67c0b8c8fb29b1b7b6221977af6b89cae787b941&format=side&path=/src/cmd/8g/cgen.c

R=rsc, remyoudompheng, r
CC=golang-dev
https://golang.org/cl/6450163

変更の背景

このコミットは、Goコンパイラcmd/8gにおいて、以前導入された「小さな整数定数最適化」が原因で発生した問題に対処するために行われました。この最適化は、コミット13416:67c0b8c8fb29（"faster code, mainly for rotate"）で導入されたもので、特定の算術演算においてコード生成を高速化することを目的としていました。

しかし、この最適化が適用されると、特に小さな整数定数を用いた算術演算が多数存在するコードにおいて、コンパイラのコード生成（codegen）が利用可能なレジスタを使い果たしてしまうという問題が発生しました。これは、レジスタ不足（register exhaustion）として知られる状況で、コンパイラが一時的な値を格納するためのレジスタを確保できなくなり、結果としてコンパイルエラーや非効率なコード生成につながる可能性があります。

この問題はGoのIssue #3835として報告されており、本コミットはその修正を目的としています。コミットメッセージでは、6g（別のアーキテクチャ向けのGoコンパイラ）のsbop/abopコード生成を8gにコピーするという代替案も検討されたものの、よりリスクの低い「最適化のロールバック」が選択されたことが述べられています。

前提知識の解説

  • Goコンパイラ (cmd/8g, 6g): Go言語は、異なるCPUアーキテクチャ向けに複数のコンパイラを持っています。
    • cmd/8g: x86-64 (64-bit Intel/AMD) アーキテクチャ向けのGoコンパイラです。Go 1.5以降はcmd/compileに統合されていますが、このコミット当時は独立したコンパイラとして存在していました。
    • cmd/6g: x86 (32-bit Intel/AMD) アーキテクチャ向けのGoコンパイラです。 これらのコンパイラは、Goのソースコードを特定アーキテクチャの機械語に変換する役割を担っています。
  • コード生成 (Codegen): コンパイラの最終段階で、中間表現からターゲットアーキテクチャの機械語コードを生成するプロセスです。このプロセスでは、効率的な実行のためにレジスタ割り当てや命令スケジューリングなどの最適化が行われます。
  • レジスタ (Registers): CPU内部にある高速な記憶領域です。プログラムの実行中に頻繁にアクセスされるデータを一時的に保持するために使用されます。レジスタへのアクセスはメモリへのアクセスよりもはるかに高速であるため、コンパイラは可能な限り多くの値をレジスタに割り当てようとします。
  • レジスタ不足 (Register Exhaustion): コンパイラがコード生成を行う際に、利用可能なレジスタが不足してしまう状況を指します。これにより、コンパイラは一時的な値をメモリにスピル（spill、退避）せざるを得なくなり、プログラムの実行速度が低下する原因となります。
  • 小さな整数定数最適化 (Small Integer Constant Optimizations): コンパイラが、プログラム中の小さな整数定数（例: 1, 2, 3など）を含む算術演算を特別に扱う最適化手法です。例えば、定数を直接命令に埋め込んだり、特定のレジスタに割り当てたりすることで、より効率的なコードを生成しようとします。
  • sbop (Symmetric Binary Operation): 左右のオペランドが対称的な二項演算（例: 加算 a + b、乗算 a * b）。オペランドの順序を入れ替えても結果が変わらない演算です。
  • abop (Asymmetric Binary Operation): 左右のオペランドが非対称な二項演算（例: 減算 a - b、除算 a / b）。オペランドの順序を入れ替えると結果が変わる演算です。
  • ullman (Ullman Number): コンパイラのコード生成において、式の評価順序を決定するために使用されるヒューリスティックな値です。Ullman数は、式のツリー構造におけるノードの複雑さを示し、レジスタ割り当ての効率化に役立ちます。一般的に、Ullman数の大きいサブツリーから評価することで、レジスタの使用を最適化しようとします。

技術的詳細

このコミットの核心は、cmd/8gコンパイラにおける「小さな整数定数最適化」のロールバックです。

問題点: 以前のコミット67c0b8c8fb29で導入された最適化は、abop（非対称二項演算）のコード生成において、右オペランド（nr）が小さな整数定数（smallintconst(nr)）である場合に特別な処理を行っていました。具体的には、右オペランドが小さな整数定数である場合、その定数をレジスタに割り当て（regalloc）、左オペランド（nl）を評価した後に、定数と左オペランドに対して演算を実行していました。

このアプローチは、一部のケースでコード生成を効率化する可能性がありましたが、問題は、多数の小さな整数定数を含む算術演算が連鎖する場合に顕在化しました。例えば、a + 1 + b + 2 + c + 3 ...のような式では、多くの定数がレジスタに割り当てられようとします。x86-64アーキテクチャ（8gのターゲット）のレジスタは限られているため、このような状況ではコンパイラがレジスタを使い果たし、結果としてレジスタスピルが発生し、パフォーマンスが低下するか、最悪の場合コンパイルに失敗する可能性がありました。

解決策: このコミットでは、src/cmd/8g/cgen.c内のabop処理から、smallintconst(nr)の条件分岐を削除することで、この最適化をロールバックしています。これにより、右オペランドが小さな整数定数であるかどうかにかかわらず、nl->ullman >= nr->ullmanというUllman数に基づいた従来のレジスタ割り当て戦略が適用されるようになります。

この変更は、特定のケースでの最適化の機会を失うことになりますが、レジスタ不足の問題を回避し、コンパイラの安定性と堅牢性を向上させるという点で、より安全なアプローチと判断されました。コミットメッセージにあるように、6gのより洗練されたsbop/abopコード生成ロジックを8gに移植するという代替案も存在しましたが、それはより大規模でリスクの高い変更となるため、今回は見送られました。

また、この変更に伴い、test/fixedbugs/bug451.goという新しいテストファイルが追加されました。このテストファイルは、多数の小さな整数定数を含む算術演算を行う関数fooと、異なる整数型での複雑な算術演算を行う関数barを含んでおり、レジスタ不足の問題が再現されることを確認するためのものです。このテストがパスすることで、ロールバックが正しく機能し、問題が解決されたことが検証されます。

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

src/cmd/8g/cgen.cファイルのabop関数内の変更です。

--- a/src/cmd/8g/cgen.c
+++ b/src/cmd/8g/cgen.c
@@ -392,13 +392,7 @@ sbop:	// symmetric binary
 	}
 
 abop:	// asymmetric binary
-	if(smallintconst(nr)) {
-		regalloc(&n1, nr->type, res);
-		cgen(nl, &n1);
-		gins(a, nr, &n1);
-		gmove(&n1, res);
-		regfree(&n1);
-	} else if(nl->ullman >= nr->ullman) {
+	if(nl->ullman >= nr->ullman) {
 		tempname(&nt, nl->type);
 		cgen(nl, &nt);
 		mgen(nr, &n2, N);

test/fixedbugs/bug451.goが新規追加されています。

// run

// Copyright 2012 The Go Authors.  All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

// Issue 3835: 8g tries to optimize arithmetic involving integer
// constants, but can run out of registers in the process.

package main

var a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z, A, B, C, D, E, F, G int

func foo() int {
	return a + 1 + b + 2 + c + 3 + d + 4 + e + 5 + f + 6 + g + 7 + h + 8 + i + 9 + j + 10 +
		k + 1 + l + 2 + m + 3 + n + 4 + o + 5 + p + 6 + q + 7 + r + 8 + s + 9 + t + 10 +
		u + 1 + v + 2 + w + 3 + x + 4 + y + 5 + z + 6 + A + 7 + B + 8 + C + 9 + D + 10 +
		E + 1 + F + 2 + G + 3
}

func bar() int8 {
	var (
		W int16
		X int32
		Y int32
		Z int32
	)
	return int8(W+int16(X+3)+3) * int8(Y+3+Z*3)
}

func main() {
	if foo() == 0 {
		panic("foo")
	}
	if bar() == 0 {
		panic("bar")
	}
}

コアとなるコードの解説

src/cmd/8g/cgen.cの変更は、abop（非対称二項演算）のコード生成ロジックを修正しています。

変更前:

abop:	// asymmetric binary
	if(smallintconst(nr)) {
		regalloc(&n1, nr->type, res);
		cgen(nl, &n1);
		gins(a, nr, &n1);
		gmove(&n1, res);
		regfree(&n1);
	} else if(nl->ullman >= nr->ullman) {
		// ... 既存のロジック ...
	}

このコードは、右オペランドnrが小さな整数定数である場合に、特別な最適化パスを実行していました。このパスでは、nrをレジスタn1に割り当て、左オペランドnlを評価した後、gins（命令生成）で演算を実行し、結果をresに移動していました。この「小さな整数定数」を優先的にレジスタに割り当てる戦略が、多数の定数がある場合にレジスタ不足を引き起こしていました。

変更後:

abop:	// asymmetric binary
	if(nl->ullman >= nr->ullman) {
		// ... 既存のロジック ...
	}

if(smallintconst(nr))で始まるブロックが完全に削除されました。これにより、右オペランドが小さな整数定数であるかどうかにかかわらず、常にnl->ullman >= nr->ullmanという条件に基づく通常のコード生成パスが実行されるようになります。このパスでは、Ullman数に基づいてオペランドの評価順序を決定し、必要に応じて一時変数（tempname）を使用することで、レジスタの競合を緩和します。

この変更は、特定の最適化を削除することで、コンパイラのレジスタ割り当て戦略を簡素化し、より堅牢なコード生成を実現しています。

test/fixedbugs/bug451.goは、この問題が修正されたことを検証するための回帰テストです。

  • foo()関数は、多数の変数と小さな整数定数の加算を連鎖させています。これは、以前の最適化がレジスタ不足を引き起こした典型的なパターンを模倣しています。
  • bar()関数は、異なる整数型（int16, int32, int8）と定数を用いたより複雑な算術演算を含んでいます。これもまた、コンパイラのコード生成が正しく行われることを確認するためのものです。 main()関数では、これらの関数がパニックを起こさずに実行されることを確認しています。これにより、コンパイラがこれらの複雑な算術式を正しく処理し、レジスタ不足に陥らないことが保証されます。

関連リンク

参考にした情報源リンク