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

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

このコミットは、Goコンパイラ（5gと8g）における64ビットインデックスの静的境界チェックに関する内部エラーを修正するものです。具体的には、コンパイル時にインデックスが境界内にあることが静的に判明している場合でも、誤ってパニックコールへの分岐が生成されてしまうバグ（Issue 4448）に対処しています。この修正により、不必要なパニックチェックが回避され、生成されるコードの正確性と効率が向上します。

コミット

  • Author: Rémy Oudompheng oudomphe@phare.normalesup.org
  • Date: Tue Nov 27 21:37:38 2012 +0100
  • Commit Hash: f134742f24f950bd3b7c563fc36cccda8fd85e81

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

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

元コミット内容

cmd/5g, cmd/8g: fix internal error on 64-bit indices statically bounded

Fixes #4448.

R=golang-dev, rsc
CC=golang-dev
https://golang.org/cl/6855100

変更の背景

このコミットは、Go言語のコンパイラ（5gと8g）が抱えていた特定のバグ、Issue 4448を修正するために行われました。このバグは、配列やスライスへのアクセスにおいて、インデックスが64ビット整数であり、かつそのインデックスがコンパイル時に静的に（つまりコードの実行前に）有効な範囲内にあることが保証されている場合に発生しました。

通常、Goコンパイラは配列やスライスへのアクセス時に、インデックスが有効な範囲内にあるかを実行時にチェックするコード（境界チェック）を生成します。インデックスが範囲外であった場合、プログラムはパニック（panic）を起こして異常終了します。これはGoのメモリ安全性を保証するための重要な機能です。

しかし、Issue 4448では、インデックスが静的に境界内にあることが分かっているにもかかわらず、コンパイラが誤って「パニックコールへの分岐」を生成してしまうという問題がありました。これは、本来不要なコードパスが生成されるだけでなく、場合によっては「ダングリングブランチ（dangling branch）」、つまり到達不能な、あるいは意図しない動作を引き起こす可能性のあるコード分岐を生み出す可能性がありました。この「内部エラー」は、コンパイラ自身のロジックの欠陥を示しており、生成されるバイナリの正確性に影響を与える可能性がありました。

この修正の目的は、静的に境界が保証された64ビットインデックスに対して、コンパイラが正しく最適化を行い、不必要な境界チェックや誤ったパニック分岐を生成しないようにすることでした。

前提知識の解説

Goコンパイラ (5g, 8g)

Go言語の初期のコンパイラは、ターゲットアーキテクチャごとに異なる名前を持っていました。

  • 5g: ARMアーキテクチャ（例: ARMv5, ARMv6, ARMv7）向けのGoコンパイラです。
  • 8g: x86-64アーキテクチャ（64ビットIntel/AMDプロセッサ）向けのGoコンパイラです。

これらのコンパイラは、Goのソースコードをそれぞれのターゲットアーキテクチャの機械語に変換する役割を担っていました。現在のGoツールチェインでは、これらのコンパイラは統合され、go buildコマンドの背後で透過的に動作しますが、当時のGo開発においては、これらの特定のコンパイラが直接言及されることが一般的でした。

64ビットインデックス

Go言語では、配列やスライスのインデックスは通常int型で表現されます。int型のサイズはシステムに依存し、32ビットシステムでは32ビット、64ビットシステムでは64ビットになります。この問題は、特に64ビットシステム上で、インデックスが64ビット整数として扱われる場合に顕在化しました。64ビットインデックスは非常に大きな範囲を表現できるため、その境界チェックのロジックはより複雑になります。

静的境界チェック (Statically Bounded)

「静的に境界が定められている（statically bounded）」とは、コンパイル時に、ある変数の値が特定の範囲内にあることが確定している状態を指します。例えば、for i := 0; i < len(s); i++のようなループにおいて、iは常に0からlen(s)-1の範囲内にあることが静的に分かります。このような場合、理論的には実行時の境界チェックを省略して最適化することができます。

パニックコール (Panic Call)

Go言語における「パニック（panic）」は、プログラムの回復不可能なエラー状態を示すメカニズムです。配列のインデックスが範囲外である場合など、Goランタイムはパニックを発生させ、通常はプログラムを終了させます。コンパイラは、このような状況を検出するために、インデックスが不正な場合にパニックをトリガーするコード（パニックコールへの分岐）を生成します。

ダングリングブランチ (Dangling Branch)

「ダングリングブランチ」とは、プログラムの制御フローにおいて、到達不能であるか、あるいは意図しない場所へ分岐してしまうコードパスを指します。コンパイラのバグによって、本来実行されるべきではないパニックコールへの分岐が誤って生成されると、それがダングリングブランチとなり、コンパイラの内部エラーや、最悪の場合、生成されたバイナリの誤動作につながる可能性があります。

技術的詳細

このコミットの技術的詳細は、Goコンパイラのコード生成部分、特に配列インデックスの処理ロジックに焦点を当てています。修正は主にsrc/cmd/5g/cgen.cとsrc/cmd/8g/cgen.c、そして関連するヘッダファイルsrc/cmd/5g/gg.h、src/cmd/5g/gsubr.cに及びます。

問題の核心は、cgenindex（5g用）およびigenindex（8g用）という関数にありました。これらの関数は、配列インデックスのコード生成と、それに伴う境界チェックのロジックを担当しています。

変更前は、これらの関数内でdebug['B']というグローバルなデバッグフラグのみが境界チェックの生成を制御していました。debug['B']が設定されている場合、境界チェックはスキップされ、nil（パニックコールへのパッチを必要としない）が返されていました。しかし、インデックスが静的に境界内にあることがコンパイラによって認識されている場合（n->boundedフラグによって示される）、debug['B']が設定されていなくても、同様に境界チェックをスキップし、パニックコールへの分岐を生成しないようにする必要がありました。

修正は、cgenindexとigenindex関数に新しい引数boundedを追加することによって行われました。このbounded引数は、debug['B']フラグと、ノードnが持つn->boundedフラグの論理和（debug['B'] || n->bounded）として渡されます。

これにより、以下のロジックが適用されます。

  1. debug['B']が真の場合（デバッグモードで境界チェックを無効にしている場合）。
  2. n->boundedが真の場合（コンパイル時にインデックスが静的に境界内にあると判断された場合）。

上記のいずれかの条件が満たされる場合、cgenindexおよびigenindex関数は、パニックコールへの分岐を生成せず、nilを返します。これにより、静的に安全なインデックスアクセスに対して不必要な境界チェックコードが生成されることがなくなり、コンパイラの内部エラーが解消されます。

また、agenr（5g）およびagen（8g）関数内のOINDEX（インデックス操作）ケースにおいて、cgenindexやigenindexを呼び出す際に、この新しいbounded引数が正しく渡されるように修正されています。これにより、コンパイラ全体でこの新しい境界チェックロジックが適用されるようになります。

test/fixedbugs/issue4448.goは、このバグを再現し、修正が正しく機能することを確認するためのテストケースです。特にMinPos関数内のbitPos[((w&-w)*b26)>>58]のような複雑なインデックス計算が、静的に境界内にあると判断されるケースをシミュレートしています。

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

src/cmd/5g/cgen.c

--- a/src/cmd/5g/cgen.c
+++ b/src/cmd/5g/cgen.c
@@ -521,7 +521,7 @@ ret:
  * returns Prog* to patch to panic call.
  */
 Prog*
-cgenindex(Node *n, Node *res)
+cgenindex(Node *n, Node *res, int bounded)
 {
 	Node tmp, lo, hi, zero, n1, n2;
 
@@ -534,7 +534,7 @@ cgenindex(Node *n, Node *res)
 	cgen(n, &tmp);
 	split64(&tmp, &lo, &hi);
 	gmove(&lo, res);
-	if(debug['B']) {
+	if(bounded) {
 		splitclean();
 		return nil;
 	}
@@ -889,6 +889,7 @@ agenr(Node *n, Node *a, Node *res)
 	Prog *p1, *p2;
 	uint32 w;
 	uint64 v;
+	int bounded;
 
 	if(debug['g'])
 		dump("agenr-n", n);
@@ -915,13 +916,14 @@ agenr(Node *n, Node *a, Node *res)
 	case OINDEX:
 		p2 = nil;  // to be patched to panicindex.
 		w = n->type->width;
+		bounded = debug['B'] || n->bounded;
 		if(nr->addable) {
 			if(!isconst(nr, CTINT))
 				tempname(&tmp, types[TINT32]);
 			if(!isconst(nl, CTSTR))
 				agenr(nl, &n3, res);
 			if(!isconst(nr, CTINT)) {
-				p2 = cgenindex(nr, &tmp);
+				p2 = cgenindex(nr, &tmp, bounded);
 				regalloc(&n1, tmp.type, N);
 				gmove(&tmp, &n1);
 			}
@@ -929,7 +931,7 @@ agenr(Node *n, Node *a, Node *res)
 		if(nl->addable) {
 			if(!isconst(nr, CTINT)) {
 				tempname(&tmp, types[TINT32]);
-				p2 = cgenindex(nr, &tmp);
+				p2 = cgenindex(nr, &tmp, bounded);
 				regalloc(&n1, tmp.type, N);
 				gmove(&tmp, &n1);
 			}
@@ -938,7 +940,7 @@ agenr(Node *n, Node *a, Node *res)
 			}
 		} else {
 			tempname(&tmp, types[TINT32]);
-			p2 = cgenindex(nr, &tmp);
+			p2 = cgenindex(nr, &tmp, bounded);
 			nr = &tmp;
 			if(!isconst(nl, CTSTR))
 				agenr(nl, &n3, res);

src/cmd/5g/gg.h

--- a/src/cmd/5g/gg.h
+++ b/src/cmd/5g/gg.h
@@ -88,7 +88,7 @@ void	ginscall(Node*, int);
  * cgen
  */
 void	agen(Node*, Node*);
-Prog* cgenindex(Node *, Node *);
+Prog* cgenindex(Node *, Node *, int);
 void	igen(Node*, Node*, Node*);
 void agenr(Node *n, Node *a, Node *res);
 vlong	fieldoffset(Type*, Node*);

src/cmd/5g/gsubr.c

--- a/src/cmd/5g/gsubr.c
+++ b/src/cmd/5g/gsubr.c
@@ -1937,7 +1937,7 @@ oindex:
 		t = types[TINT32];
 	regalloc(reg1, t, N);
 	regalloc(&n3, types[TINT32], reg1);
-	p2 = cgenindex(r, &n3);
+	p2 = cgenindex(r, &n3, debug['B'] || n->bounded);
 	gmove(&n3, reg1);
 	regfree(&n3);

src/cmd/8g/cgen.c

--- a/src/cmd/8g/cgen.c
+++ b/src/cmd/8g/cgen.c
@@ -464,8 +464,8 @@ flt2:	// binary
  * n is an array index, and might be any size; res width is <= 32-bit.\n  * returns Prog* to patch to panic call.
  */
 Prog*
-igenindex(Node *n, Node *res)
+static Prog*
+igenindex(Node *n, Node *res, int bounded)
 {
 	Node tmp, lo, hi, zero;
 
@@ -485,7 +485,7 @@ igenindex(Node *n, Node *res)
 	split64(&tmp, &lo, &hi);
 	tempname(res, types[TUINT32]);
 	gmove(&lo, res);
-	if(debug['B']) {
+	if(bounded) {
 		splitclean();
 		return nil;
 	}
@@ -508,6 +508,7 @@ agen(Node *n, Node *res)
 	uint32 w;
 	uint64 v;
 	Prog *p1, *p2;
+	int bounded;
 
 	if(debug['g']) {
 		dump("\nagen-res", res);
@@ -584,26 +585,27 @@ agen(Node *n, Node *res)
 	case OINDEX:
 		p2 = nil;  // to be patched to panicindex.
 		w = n->type->width;
+		bounded = debug['B'] || n->bounded;
 		if(nr->addable) {
 			// Generate &nl first, and move nr into register.
 			if(!isconst(nl, CTSTR))
 				igen(nl, &n3, res);
 			if(!isconst(nr, CTINT)) {
-				p2 = igenindex(nr, &tmp);
+				p2 = igenindex(nr, &tmp, bounded);
 				regalloc(&n1, tmp.type, N);
 				gmove(&tmp, &n1);
 			}
 		} else if(nl->addable) {
 			// Generate nr first, and move &nl into register.
 			if(!isconst(nr, CTINT)) {
-				p2 = igenindex(nr, &tmp);
+				p2 = igenindex(nr, &tmp, bounded);
 				regalloc(&n1, tmp.type, N);
 				gmove(&tmp, &n1);
 			}
 			if(!isconst(nl, CTSTR))
 				igen(nl, &n3, res);
 		} else {
-			p2 = igenindex(nr, &tmp);
+			p2 = igenindex(nr, &tmp, bounded);
 			nr = &tmp;
 			if(!isconst(nl, CTSTR))
 				igen(nl, &n3, res);

test/fixedbugs/issue4448.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 4448: 64-bit indices that are statically known
// to be bounded make 5g and 8g generate a dangling branch.

package main

const b26 uint64 = 0x022fdd63cc95386d

var bitPos [64]int

func init() {
	for p := uint(0); p < 64; p++ {
		bitPos[b26<<p>>58] = int(p)
	}
}

func MinPos(w uint64) int {
	if w == 0 {
		panic("bit: MinPos(0) undefined")
	}
	return bitPos[((w&-w)*b26)>>58]
}

func main() {
	const one = uint64(1)
	for i := 0; i < 64; i++ {
		if MinPos(1<<uint(i)) != i {
			println("i =", i)
			panic("MinPos(1<<uint(i)) != i")
		}
	}
}

コアとなるコードの解説

この修正の核心は、Goコンパイラが配列やスライスのインデックスを処理する際に、そのインデックスが「静的に境界内にある」と判断できる場合に、不必要な実行時境界チェックコードの生成を抑制することです。

  1. cgenindex / igenindex 関数のシグネチャ変更:

    • 変更前: Prog* cgenindex(Node *n, Node *res)
    • 変更後: Prog* cgenindex(Node *n, Node *res, int bounded)
    • 新しいbounded引数が追加されました。この引数は、現在のインデックス操作が静的に境界内にあるかどうかを示すフラグとして機能します。

  2. 境界チェックの条件変更:

    • 変更前: if(debug['B']) { ... return nil; }
    • 変更後: if(bounded) { ... return nil; }
    • cgenindexおよびigenindex関数内で、パニックコールへの分岐を生成するかどうかを決定する条件が変更されました。以前はデバッグフラグdebug['B']のみがこの動作を制御していましたが、修正後は新しく導入されたbounded引数が使用されます。
    • boundedが真の場合、関数はnilを返します。これは、パニックコールへのパッチが必要ないことを意味し、結果として不必要な境界チェックコードが生成されなくなります。

  3. bounded引数の伝播:

    • agenr（5g）およびagen（8g）関数内のOINDEX（インデックス操作）を処理する部分で、bounded変数が導入されました。
    • bounded = debug['B'] || n->bounded;
      • ここで、bounded変数は、グローバルなデバッグフラグdebug['B']と、現在のノードnが持つn->boundedフラグの論理和として計算されます。
      • n->boundedは、コンパイラがこのインデックスが静的に有効な範囲内にあると判断した場合に設定されるフラグです。
    • この計算されたbounded値が、cgenindexまたはigenindexを呼び出す際に新しい引数として渡されます。
    • これにより、コンパイラは、デバッグモードであるか、またはインデックスが静的に安全であるかのいずれかの条件が満たされる場合に、不必要な境界チェックコードの生成を抑制できるようになります。

この修正により、コンパイラはより賢くコードを生成し、静的に安全なインデックスアクセスに対しては余分なオーバーヘッドを発生させなくなります。これは、生成されるバイナリのパフォーマンス向上と、コンパイラ自身の正確性の向上に寄与します。特に、64ビットインデックスのような大きな値の範囲を扱う際に、この最適化は重要になります。

関連リンク

参考にした情報源リンク