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

このコミットは、Go言語の実験的なSSA (Static Single Assignment) バックエンドにおいて、rangeループの内部的な処理方法を、イテレート対象の型に基づいて最適化し、特殊化する変更を導入しています。これにより、rangeループのセマンティクスがより正確に、かつ効率的にSSA形式に変換されるようになります。

コミット

commit d8e3b16f8b1b78be15775c7d09fe9e60e6e84e72
Author: Alan Donovan <adonovan@google.com>
Date:   Mon Feb 11 22:12:56 2013 -0500

    exp/ssa: special-case 'range' loops based on type of range expression.

    The lowering of ast.RangeStmt now has three distinct cases:

    1) rangeIter for maps and strings; approximately:
        it = range x
        for {
          k, v, ok = next it
          if !ok { break }
          ...
        }
       The Range instruction and the interpreter's "iter"
       datatype are now restricted to these types.

    2) rangeChan for channels; approximately:
        for {
          k, ok = <-x
          if !ok { break }
          ...
        }

    3) rangeIndexed for slices, arrays, and *array; approximately:
        for k, l = 0, len(x); k++ {
          v = x[k]
          ...
        }

    In all cases we now evaluate the side effects of the range expression
    exactly once, per comments on http://code.google.com/p/go/issues/detail?id=4644.

    However the exact spec wording is still being discussed in
    https://golang.org/cl/7307083/.  Further (small)
    changes may be required once the dust settles.

    R=iant
    CC=golang-dev
    https://golang.org/cl/7303074

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

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

元コミット内容

このコミットは、Go言語のrangeステートメントのSSA (Static Single Assignment) 形式への変換ロジックを改善するものです。以前は、rangeループの処理がより汎用的なイテレータベースのアプローチに依存していましたが、この変更により、イテレート対象のデータ型（マップ、文字列、チャネル、スライス、配列、ポインタ配列）に応じて、より特化した効率的なコード生成パスが導入されました。

主な変更点は以下の通りです。

1. ast.RangeStmtの変換の特殊化: rangeステートメントの抽象構文木 (AST) からSSA形式への変換が、イテレート対象の型に基づいて3つの異なるケースに分岐するようになりました。
   • rangeIter: マップと文字列のイテレーションに使用されます。これは、Range命令とインタープリタの"iter"データ型に限定されます。
   • rangeChan: チャネルからの受信によるイテレーションに使用されます。
   • rangeIndexed: スライス、配列、およびポインタ配列（*array）のインデックスベースのイテレーションに使用されます。
2. range式の副作用の評価: range式の副作用（例: range f() の f() の呼び出し）が、ループの開始時に正確に一度だけ評価されるようになりました。これは、Goのrangeループのセマンティクスに合致させるための重要な変更であり、Go issue 4644で議論されていた内容に対応しています。
3. インタープリタの変更: SSAインタープリタのrangeIter関数が、マップと文字列のみを処理するように制限され、配列、スライス、チャネルのイテレータ関連のコードが削除されました。

変更の背景

この変更の背景には、Go言語のrangeループのセマンティクスをSSAバックエンドでより正確かつ効率的に表現する必要がありました。特に、以下の点が挙げられます。

1. range式の副作用の評価タイミング: Go言語の仕様では、range式の評価はループの開始時に一度だけ行われると定められています。しかし、SSAバックエンドの初期の実装では、このセマンティクスが常に正確に反映されているとは限りませんでした。例えば、range f() のような場合、f() が複数回呼び出される可能性があり、これはGoの仕様に反します。このコミットは、Go issue 4644で報告されたこの問題を解決するために、range式の副作用が一度だけ評価されるように修正しています。
2. 型に応じた最適化: rangeループは、イテレート対象の型（マップ、文字列、チャネル、スライス、配列）によって内部的な動作が大きく異なります。例えば、スライスや配列はインデックスアクセスが可能であるため、単純なforループに変換できますが、マップやチャネルはより複雑なイテレータや受信操作が必要です。このコミットは、これらの型の特性を活かして、SSA形式への変換時にそれぞれの型に特化した効率的なコードパスを生成することで、パフォーマンスの向上とコードの簡素化を図っています。
3. 実験的なSSAバックエンドの成熟: exp/ssaはGoコンパイラの実験的なSSAバックエンドであり、Go言語のセマンティクスを正確に表現し、最適化を適用するための基盤を構築している段階でした。このコミットは、rangeループというGo言語の重要な構文要素の変換ロジックを改善することで、SSAバックエンドの正確性と堅牢性を高める一環として行われました。

前提知識の解説

このコミットを理解するためには、以下の概念についての前提知識があると役立ちます。

1. Go言語のrangeループ

Go言語のfor...rangeループは、配列、スライス、文字列、マップ、チャネルといったコレクション型をイテレートするための構文です。イテレート対象の型によって、返される値や動作が異なります。

• スライス、配列、ポインタ配列: インデックスと要素のコピーが返されます。

  for i, v := range []int{1, 2, 3} {
      // i はインデックス、v は要素のコピー
  }
  

• 文字列: Unicodeコードポイントの開始バイトインデックスとルーン（Unicodeコードポイント）が返されます。

  for i, r := range "Go" {
      // i はバイトインデックス、r はルーン
  }
  

• マップ: キーと値のコピーが返されます。イテレーションの順序は保証されません。

  for k, v := range map[string]int{"a": 1, "b": 2} {
      // k はキー、v は値
  }
  

• チャネル: チャネルがクローズされるまで、チャネルから受信した値が返されます。

  for v := range ch {
      // v はチャネルから受信した値
  }
  

2. SSA (Static Single Assignment) 形式

SSA (Static Single Assignment) 形式は、コンパイラの最適化段階で中間表現として使用されるプログラムの表現形式です。SSA形式では、各変数が一度だけ代入されるという特性を持ちます。これにより、データフロー解析や最適化が容易になります。

• SSAの利点:
  • データフロー解析の簡素化: 各変数の定義と使用が明確になるため、変数の値がどこから来るのか、どこで使われるのかを追跡しやすくなります。
  • 最適化の促進: 共通部分式除去、デッドコード除去、レジスタ割り当てなどの最適化がより効果的に行えます。
• GoコンパイラにおけるSSA: Goコンパイラは、AST (Abstract Syntax Tree) からSSA形式に変換し、SSA形式上で様々な最適化を行った後、最終的な機械語コードを生成します。exp/ssaは、このSSAバックエンドの実験的な実装でした。

3. AST (Abstract Syntax Tree)

AST (Abstract Syntax Tree) は、ソースコードの構文構造を木構造で表現したものです。コンパイラのフロントエンドがソースコードを解析して生成し、その後の最適化やコード生成の入力となります。ast.RangeStmtは、Goのrangeステートメントに対応するASTノードです。

4. Goのtypesパッケージ

Goのtypesパッケージは、Goプログラムの型情報を表現するためのパッケージです。コンパイラやツールが型チェックや型推論を行う際に使用されます。types.Array, types.Slice, types.Map, types.Chan, types.Basic, types.Pointerなどは、それぞれGoの配列、スライス、マップ、チャネル、基本型、ポインタ型を表す構造体です。

5. Go issue 4644

Go issue 4644は、for...rangeループのイテレーション変数のセマンティクスに関するバグ報告です。特に、range式の副作用がループごとに評価される可能性があるという問題が指摘されていました。Goの仕様では、range式はループの開始時に一度だけ評価されるべきです。このコミットは、この問題に対処するための変更の一部です。

技術的詳細

このコミットの技術的詳細は、主にsrc/pkg/exp/ssa/builder.goにおけるrangeStmt関数の変更に集約されています。この関数は、Goのast.RangeStmt（for...rangeステートメント）をSSA形式に変換する役割を担っています。

変更前は、rangeStmt関数は、すべてのrangeループに対して比較的汎用的なイテレータベースのアプローチを使用していました。これは、Range命令とNext命令を組み合わせてイテレータを生成し、そのイテレータからキーと値を取得するというものでした。しかし、このアプローチでは、特定の型（スライス、配列、チャネル）に対して非効率であったり、range式の副作用の評価タイミングに関するGoのセマンティクスを正確に反映できないという問題がありました。

このコミットでは、rangeStmt関数が、イテレート対象の型に基づいて以下の3つの新しいヘルパー関数を呼び出すように変更されました。

1. rangeIndexed(fn *Function, x Value, tv types.Type) (k, v Value, loop, done *BasicBlock):

   • 目的: スライス、配列、およびポインタ配列（*array）のrangeループを処理します。これらの型はインデックスアクセスが可能であるため、従来のforループに近い形式に変換するのが最も効率的です。
   • 生成されるSSA構造:

     //      length = len(x)
     //      index = -1
     // loop:                                   (target of continue)
     //      index++
     //      if index < length goto body else done
     // body:
     //      k = index
     //      v = x[index]
     //      ...body...
     //      jump loop
     // done:                                   (target of break)
     

   • 詳細:
     • まず、len(x)を計算してループの長さを決定します。配列の場合、長さは型情報から静的に取得できます。
     • indexというローカル変数を導入し、-1で初期化します。
     • ループの各イテレーションでindexをインクリメントし、lengthと比較してループの終了条件をチェックします。
     • k（キー）にはindexの値を、v（値）にはx[index]（インデックスアクセス）の結果を割り当てます。
     • これにより、スライスや配列のrangeループが、SSA形式で効率的なインデックスベースのループに変換されます。

2. rangeIter(fn *Function, x Value, tk, tv types.Type) (k, v Value, loop, done *BasicBlock):

   • 目的: マップと文字列のrangeループを処理します。これらの型は、イテレータを介して要素にアクセスする必要があります。
   • 生成されるSSA構造:

     //      it = range x
     // loop:                                   (target of continue)
     //      okv = next it                      (ok, key, value)
     //      ok = extract okv #0
     //      if ok goto body else done
     // body:
     //      k = extract okv #1
     //      v = extract okv #2
     //      ...body...
     //      jump loop
     // done:                                   (target of break)
     

   • 詳細:
     • Range命令を使用してイテレータitを生成します。
     • ループの各イテレーションでNext命令を呼び出し、okv（ok, key, valueのタプル）を取得します。
     • okvからok（イテレーションが成功したか）を抽出し、ループの終了条件をチェックします。
     • okvからk（キー）とv（値）を抽出します。
     • このアプローチは、マップや文字列のイテレーションの性質を反映しています。

3. rangeChan(fn *Function, x Value, tk types.Type) (k Value, loop, done *BasicBlock):

   • 目的: チャネルのrangeループを処理します。チャネルのイテレーションは、チャネルからの受信操作に基づいています。
   • 生成されるSSA構造:

     // loop:                                   (target of continue)
     //      ko = <-x                           (key, ok)
     //      ok = extract ko #1
     //      if ok goto body else done
     // body:
     //      k = extract ko #0
     //      ...
     //      goto loop
     // done:                                   (target of break)
     

   • 詳細:
     • ループの各イテレーションで、UnOp（単項演算子）のtoken.ARROW（チャネル受信）を使用してチャネルxから値を受信します。この操作は、値とok（チャネルがクローズされていないか）のタプルkoを返します。
     • koからokを抽出し、ループの終了条件をチェックします。
     • koからk（受信した値）を抽出します。
     • これにより、チャネルのrangeループが、SSA形式で効率的なチャネル受信ベースのループに変換されます。

これらの変更により、range式の副作用がループの開始時に一度だけ評価されることが保証されます。これは、rangeIndexed、rangeIter、rangeChanのいずれのパスでも、range式の評価（b.expr(fn, s.X)）がrangeStmt関数の冒頭で一度だけ行われるためです。

また、src/pkg/exp/ssa/interp/ops.goとsrc/pkg/exp/ssa/interp/value.goでは、SSAインタープリタのrangeIter関数から、配列、スライス、チャネルに関するイテレータのロジックが削除されました。これは、これらの型がもはや汎用的なrangeIterパスを使用せず、それぞれ特化したrangeIndexedやrangeChanパスで処理されるようになったためです。

src/pkg/exp/ssa/ssa.goでは、Range命令のコメントが更新され、そのXフィールドが文字列またはマップに限定されることが明記されました。

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

このコミットのコアとなるコードの変更は、主に以下のファイルに集中しています。

1. src/pkg/exp/ssa/builder.go:

   • rangeStmt関数が大幅にリファクタリングされ、イテレート対象の型に基づいてrangeIndexed、rangeIter、rangeChanのいずれかのヘルパー関数を呼び出すようになりました。
   • 新しくrangeIndexed、rangeIter、rangeChanの3つのヘルパー関数が追加され、それぞれの型に特化したSSAコード生成ロジックが実装されました。
   • 既存のrangeStmt内の配列/スライス/チャネルに関する汎用的なイテレータ処理ロジックが削除されました。

2. src/pkg/exp/ssa/interp/ops.go:

   • rangeIter関数から、nil、*value（ポインタ配列）、array、[]value（スライス）、chan valueのケースが削除されました。これにより、rangeIterはマップと文字列のみを処理するようになりました。

3. src/pkg/exp/ssa/interp/value.go:

   • arrayIterとchanIterの型定義および関連するnext()メソッドが完全に削除されました。これは、これらのイテレータがSSAインタープリタで直接使用されなくなったためです。

4. src/pkg/exp/ssa/ssa.go:

   • Range構造体のコメントが更新され、Xフィールドがstringまたはmapに限定されることが明記されました。

コアとなるコードの解説

src/pkg/exp/ssa/builder.go の変更点

このファイルは、GoのASTをSSA形式に変換するビルダの主要部分です。

rangeStmt 関数の変更

// rangeStmt emits to fn code for the range statement s, optionally
// labelled by label.
//
func (b *Builder) rangeStmt(fn *Function, s *ast.RangeStmt, label *lblock) {
	var tk, tv types.Type
	if !isBlankIdent(s.Key) {
		tk = b.exprType(s.Key)
	}
	if s.Value != nil && !isBlankIdent(s.Value) {
		tv = b.exprType(s.Value)
	}

	// If iteration variables are defined (:=), this
	// is a short variable declaration. The spec says:
	// "The iteration variables may be declared by the 'range' clause
	// using a form of short variable declaration (:=). In this case
	// their types are inferred from the types of the expression elements
	// and their scope is the body of the 'for' statement and any
	// subsequent (nested) 'for' statements."
	// using := never redeclares an existing variable; it
	// always creates a new one.
	if s.Tok == token.DEFINE {
		if tk != nil {
			fn.addNamedLocal(b.obj(s.Key.(*ast.Ident)))
		}
		if tv != nil {
			fn.addNamedLocal(b.obj(s.Value.(*ast.Ident)))
		}
	}

	x := b.expr(fn, s.X) // range式の評価はここで一度だけ行われる

	var k, v Value
	var loop, done *BasicBlock
	switch rt := underlyingType(x.Type()).(type) {
	case *types.Slice, *types.Array, *types.Pointer: // *array
		k, v, loop, done = b.rangeIndexed(fn, x, tv)

	case *types.Chan:
		k, loop, done = b.rangeChan(fn, x, tk)

	case *types.Map, *types.Basic: // string
		k, v, loop, done = b.rangeIter(fn, x, tk, tv)

	default:
		panic("Cannot range over: " + rt.String())
	}

	// Evaluate both LHS expressions before we update either.
	var kl, vl lvalue
	if tk != nil {
		kl = b.addr(fn, s.Key, false) // non-escaping
	}
	if tv != nil {
		vl = b.addr(fn, s.Value, false) // non-escaping
	}
	if tk != nil {
		kl.store(fn, k)
	}
	if tv != nil {
		vl.store(fn, v)
	}

	if label != nil {
		label._break = done
		label._continue = loop
	}

	fn.targets = &targets{
		tail:      fn.targets,
		_break:    done,
		_continue: loop,
	}
	b.stmt(fn, s.Body) // ループ本体のSSA変換
	fn.targets = fn.targets.tail

	emitJump(fn, loop) // ループの先頭に戻る
	fn.currentBlock = done
}

• b.expr(fn, s.X): range式の評価がループの開始前に一度だけ行われることを保証します。これにより、Goの仕様に準拠します。
• switch rt := underlyingType(x.Type()).(type): range式の基底型に基づいて、適切なヘルパー関数（rangeIndexed, rangeChan, rangeIter）を呼び出します。これがこのコミットの主要な分岐ロジックです。
• kl.store(fn, k) / vl.store(fn, v): ループ変数にキーと値を格納します。

rangeIndexed 関数の追加

// rangeIndexed emits to fn the header for an integer indexed loop
// over array, *array or slice value x.
// The v result is defined only if tv is non-nil.
//
func (b *Builder) rangeIndexed(fn *Function, x Value, tv types.Type) (k, v Value, loop, done *BasicBlock) {
	// Determine number of iterations.
	var length Value
	if arr, ok := deref(x.Type()).(*types.Array); ok {
		// For array or *array, the number of iterations is
		// known statically thanks to the type.
		length = intLiteral(arr.Len)
	} else {
		// length = len(x).
		var call Call
		call.Func = b.globals[types.Universe.Lookup("len")]
		call.Args = []Value{x}
		call.setType(tInt)
		length = fn.emit(&call)
	}

	index := fn.addLocal(tInt)
	emitStore(fn, index, intLiteral(-1))

	loop = fn.newBasicBlock("rangeindex.loop")
	emitJump(fn, loop)
	fn.currentBlock = loop

	incr := &BinOp{
		Op: token.ADD,
		X:  emitLoad(fn, index),
		Y:  intLiteral(1),
	}
	incr.setType(tInt)
	emitStore(fn, index, fn.emit(incr))

	body := fn.newBasicBlock("rangeindex.body")
	done = fn.newBasicBlock("rangeindex.done")
	emitIf(fn, emitCompare(fn, token.LSS, incr, length), body, done)
	fn.currentBlock = body

	k = emitLoad(fn, index)
	if tv != nil {
		switch t := underlyingType(x.Type()).(type) {
		case *types.Array:
			instr := &Index{X: x, Index: k}
			instr.setType(t.Elt)
			v = fn.emit(instr)

		case *types.Pointer: // *array
			instr := &IndexAddr{X: x, Index: k}
			instr.setType(pointer(t.Base.(*types.Array).Elt))
			v = emitLoad(fn, fn.emit(instr))

		case *types.Slice:
			instr := &IndexAddr{X: x, Index: k}
			instr.setType(pointer(t.Elt))
			v = emitLoad(fn, fn.emit(instr))

		default:
			panic("rangeIndexed x:" + t.String())
		}
	}
	return
}

• 配列、スライス、ポインタ配列のrangeループを、インデックスベースのforループに変換します。
• len(x)を計算してループ回数を決定し、index変数を管理します。
• IndexまたはIndexAddr命令を使用して、インデックスkに基づいて要素vにアクセスします。

rangeIter 関数の追加

// rangeIter emits to fn the header for a loop using
// Range/Next/Extract to iterate over map or string value x.
// tk and tv are the types of the key/value results k and v, or nil
// if the respective component is not wanted.
//
func (b *Builder) rangeIter(fn *Function, x Value, tk, tv types.Type) (k, v Value, loop, done *BasicBlock) {
	rng := &Range{X: x}
	rng.setType(tRangeIter)
	it := fn.emit(rng)

	loop = fn.newBasicBlock("rangeiter.loop")
	emitJump(fn, loop)
	fn.currentBlock = loop

	okv := &Next{Iter: it}
	okv.setType(&types.Result{Values: []*types.Var{
		varOk,
		{Name: "k", Type: tk},
		{Name: "v", Type: tv},
	}})
	fn.emit(okv)

	body := fn.newBasicBlock("rangeiter.body")
	done = fn.newBasicBlock("rangeiter.done")
	emitIf(fn, emitExtract(fn, okv, 0, tBool), body, done)
	fn.currentBlock = body

	if tk != nil {
		k = emitExtract(fn, okv, 1, tk)
	}
	if tv != nil {
		v = emitExtract(fn, okv, 2, tv)
	}
	return
}

• マップと文字列のrangeループを、Range命令でイテレータを生成し、Next命令で次の要素を取得する形式に変換します。
• emitExtractを使用して、Next命令が返すタプルからok、k、vを抽出します。

rangeChan 関数の追加

// rangeChan emits to fn the header for a loop that receives from
// channel x until it fails.
// tk is the channel's element type, or nil if the k result is not
// wanted
//
func (b *Builder) rangeChan(fn *Function, x Value, tk types.Type) (k Value, loop, done *BasicBlock) {
	loop = fn.newBasicBlock("rangechan.loop")
	emitJump(fn, loop)
	fn.currentBlock = loop
	recv := &UnOp{
		Op:      token.ARROW,
		X:       x,
		CommaOk: true,
	}
	recv.setType(&types.Result{Values: []*types.Var{
		{Name: "k", Type: tk},
		varOk,
	}})
	ko := fn.emit(recv)
	body := fn.newBasicBlock("rangechan.body")
	done = fn.newBasicBlock("rangechan.done")
	emitIf(fn, emitExtract(fn, ko, 1, tBool), body, done)
	fn.currentBlock = body
	if tk != nil {
		k = emitExtract(fn, ko, 0, tk)
	}
	return
}

• チャネルのrangeループを、<-x（チャネル受信）操作に変換します。
• UnOp命令（単項演算子）とtoken.ARROWを使用してチャネル受信を表現し、値とokのタプルkoを取得します。
• emitExtractを使用して、koからokとkを抽出します。

src/pkg/exp/ssa/interp/ops.go および src/pkg/exp/ssa/interp/value.go の変更点

これらのファイルはSSAインタープリタのコードです。rangeIter関数から、配列、スライス、チャネルに関するイテレータのロジックが削除されました。これは、これらの型がもはや汎用的なrangeIterパスを使用せず、SSAビルダによってそれぞれの型に特化したSSA命令に変換されるようになったため、インタープリタ側でこれらのイテレータを直接処理する必要がなくなったためです。

src/pkg/exp/ssa/ssa.go の変更点

このファイルはSSA命令の定義を含んでいます。Range命令のコメントが更新され、そのXフィールドがstringまたはmapに限定されることが明記されました。これは、Range命令が汎用的なイテレータではなく、特定の型（マップと文字列）のイテレーションに特化されたことを反映しています。

関連リンク

• Go issue 4644: https://code.google.com/p/go/issues/detail?id=4644 (現在はGitHubに移行しているため、直接アクセスできない可能性がありますが、Goのrangeループのセマンティクスに関する議論の歴史的背景を示しています。)
• Go CL 7307083: https://golang.org/cl/7307083/ (Goのrangeループの仕様に関する議論の変更リスト)
• Go CL 7303074: https://golang.org/cl/7303074 (このコミットの変更リスト)

参考にした情報源リンク

• Go Programming Language Specification - For statements: https://go.dev/ref/spec#For_statements
• Go SSA: https://go.dev/blog/go1.7-ssa (Go 1.7でSSAがデフォルトになった際のブログ記事。SSAの概要を理解するのに役立ちます。)
• Static Single Assignment form - Wikipedia: https://en.wikipedia.org/wiki/Static_single-assignment_form