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

このコミットは、Go言語の実験的なSSA (Static Single Assignment) パッケージ exp/ssa において、Function および BasicBlock 型の定義と、それらに対する基本的な最適化処理（デッドブロック除去、ブロック結合、ジャンプスレッディング）を導入するものです。コンパイラのバックエンドにおける中間表現の構築と最適化の基盤を形成します。

コミット

commit 8f90915692d6a8205a996d1116c9eb703f91c40c
Author: Alan Donovan <adonovan@google.com>
Date:   Mon Jan 28 18:14:09 2013 -0500

    exp/ssa: (#3 of 5): Function, BasicBlock and optimisations
    
    R=gri, iant, iant
    CC=golang-dev
    https://golang.org/cl/7202051
---
 src/pkg/exp/ssa/blockopt.go | 190 +++++++++++++++++++++
 src/pkg/exp/ssa/func.go     | 404 ++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 594 insertions(+)

diff --git a/src/pkg/exp/ssa/blockopt.go b/src/pkg/exp/ssa/blockopt.go
new file mode 100644
index 0000000000..77a98b3e01
--- /dev/null
+++ b/src/pkg/exp/ssa/blockopt.go
@@ -0,0 +1,190 @@
+package ssa
+
+// Simple block optimisations to simplify the control flow graph.
+
+// TODO(adonovan): instead of creating several "unreachable" blocks
+// per function in the Builder, reuse a single one (e.g. at Blocks[1])
+// to reduce garbage.
+//
+// TODO(adonovan): in the absence of multiway branch instructions,
+// each BasicBlock has 0, 1, or 2 successors.  We should preallocate
+// the backing array for the Succs slice inline in BasicBlock.
+
+import (
+	"fmt"
+	"os"
+)
+
+const debugBlockOpt = false
+
+func hasPhi(b *BasicBlock) bool {
+	_, ok := b.Instrs[0].(*Phi)
+	return ok
+}
+
+// prune attempts to prune block b if it is unreachable (i.e. has no
+// predecessors other than itself), disconnecting it from the CFG.
+// The result is true if the optimisation was applied.  i is the block
+// index within the function.
+//
+func prune(f *Function, i int, b *BasicBlock) bool {
+	if i == 0 {
+		return false // don't prune entry block
+	}
+	if len(b.Preds) == 0 || len(b.Preds) == 1 && b.Preds[0] == b {
+		// Disconnect it from its successors.
+		for _, c := range b.Succs {
+			c.removePred(b)
+		}
+		if debugBlockOpt {
+			fmt.Fprintln(os.Stderr, "prune", b.Name)
+		}
+
+		// Delete b.
+		f.Blocks[i] = nil
+		return true
+	}
+	return false
+}
+
+// jumpThreading attempts to apply simple jump-threading to block b,
+// in which a->b->c become a->c if b is just a Jump.
+// The result is true if the optimisation was applied.
+// i is the block index within the function.
+//
+func jumpThreading(f *Function, i int, b *BasicBlock) bool {
+	if i == 0 {
+		return false // don't apply to entry block
+	}
+	if b.Instrs == nil {
+		fmt.Println("empty block ", b.Name)
+		return false
+	}
+	if _, ok := b.Instrs[0].(*Jump); !ok {
+		return false // not just a jump
+	}
+	c := b.Succs[0]
+	if c == b {
+		return false // don't apply to degenerate jump-to-self.
+	}
+	if hasPhi(c) {
+		return false // not sound without more effort
+	}
+	for j, a := range b.Preds {
+		a.replaceSucc(b, c)
+
+		// If a now has two edges to c, replace its degenerate If by Jump.
+		if len(a.Succs) == 2 && a.Succs[0] == c && a.Succs[1] == c {
+			jump := new(Jump)
+			jump.SetBlock(a)
+			a.Instrs[len(a.Instrs)-1] = jump
+			a.Succs = a.Succs[:1]
+			c.removePred(b)
+		} else {
+			if j == 0 {
+				c.replacePred(b, a)
+			} else {
+				c.Preds = append(c.Preds, a)
+			}
+		}
+
+		if debugBlockOpt {
+			fmt.Fprintln(os.Stderr, "jumpThreading", a.Name, b.Name, c.Name)
+		}
+	}
+	f.Blocks[i] = nil
+	return true
+}
+
+// fuseBlocks attempts to apply the block fusion optimisation to block
+// a, in which a->b becomes ab if len(a.Succs)==len(b.Preds)==1.
+// The result is true if the optimisation was applied.
+//
+func fuseBlocks(f *Function, a *BasicBlock) bool {
+	if len(a.Succs) != 1 {
+		return false
+	}
+	b := a.Succs[0]
+	if len(b.Preds) != 1 {
+		return false
+	}
+	// Eliminate jump at end of A, then copy all of B across.
+	a.Instrs = append(a.Instrs[:len(a.Instrs)-1], b.Instrs...)
+	for _, instr := range b.Instrs {
+		instr.SetBlock(a)
+	}
+
+	// A inherits B's successors
+	a.Succs = b.Succs
+
+	// Fix up Preds links of all successors of B.
+	for _, c := range b.Succs {
+		c.replacePred(b, a)
+	}
+
+	if debugBlockOpt {
+		fmt.Fprintln(os.Stderr, "fuseBlocks", a.Name, b.Name)
+	}
+
+	// Make b unreachable.  Subsequent pruning will reclaim it.
+	b.Preds = nil
+	return true
+}
+
+// optimizeBlocks() performs some simple block optimizations on a
+// completed function: dead block elimination, block fusion, jump
+// threading.
+//
+func optimizeBlocks(f *Function) {
+	// Loop until no further progress.
+	changed := true
+	for changed {
+		changed = false
+
+		if debugBlockOpt {
+			f.DumpTo(os.Stderr)
+			MustSanityCheck(f, nil)
+		}
+
+		for i, b := range f.Blocks {
+			// f.Blocks will temporarily contain nils to indicate
+			// deleted blocks; we remove them at the end.
+			if b == nil {
+				continue
+			}
+
+			// Prune unreachable blocks (including all empty blocks).
+			if prune(f, i, b) {
+				changed = true
+				continue // (b was pruned)
+			}
+
+			// Fuse blocks.  b->c becomes bc.
+			if fuseBlocks(f, b) {
+				changed = true
+			}
+
+			// a->b->c becomes a->c if b contains only a Jump.
+			if jumpThreading(f, i, b) {
+				changed = true
+				continue // (b was disconnected)
+			}
+		}
+	}
+
+	// Eliminate nils from Blocks.
+	j := 0
+	for _, b := range f.Blocks {
+		if b != nil {
+			f.Blocks[j] = b
+			j++
+		}
+	}
+	// Nil out b.Blocks[j:] to aid GC.
+	for i := j; i < len(f.Blocks); i++ {
+		f.Blocks[i] = nil
+	}
+	f.Blocks = f.Blocks[:j]
+}
diff --git a/src/pkg/exp/ssa/func.go b/src/pkg/exp/ssa/func.go
new file mode 100644
index 0000000000..d0c5440516
--- /dev/null
+++ b/src/pkg/exp/ssa/func.go
@@ -0,0 +1,404 @@
+package ssa
+
+// This file implements the Function and BasicBlock types.
+
+import (
+	"fmt"
+	"go/ast"
+	"go/types"
+	"io"
+	"os"
+)
+
+// addEdge adds a control-flow graph edge from from to to.
+func addEdge(from, to *BasicBlock) {
+	from.Succs = append(from.Succs, to)
+	to.Preds = append(to.Preds, from)
+}
+
+// emit appends an instruction to the current basic block.
+// If the instruction defines a Value, it is returned.
+//
+func (b *BasicBlock) emit(i Instruction) Value {
+	i.SetBlock(b)
+	b.Instrs = append(b.Instrs, i)
+	v, _ := i.(Value)
+	return v
+}
+
+// phis returns the prefix of b.Instrs containing all the block's φ-nodes.
+func (b *BasicBlock) phis() []Instruction {
+	for i, instr := range b.Instrs {
+		if _, ok := instr.(*Phi); !ok {
+			return b.Instrs[:i]
+		}
+	}
+	return nil // unreachable in well-formed blocks
+}
+
+// replacePred replaces all occurrences of p in b's predecessor list with q.
+// Ordinarily there should be at most one.
+//
+func (b *BasicBlock) replacePred(p, q *BasicBlock) {
+	for i, pred := range b.Preds {
+		if pred == p {
+			b.Preds[i] = q
+		}
+	}
+}
+
+// replaceSucc replaces all occurrences of p in b's successor list with q.
+// Ordinarily there should be at most one.
+//
+func (b *BasicBlock) replaceSucc(p, q *BasicBlock) {
+	for i, succ := range b.Succs {
+		if succ == p {
+			b.Succs[i] = q
+		}
+	}
+}
+
+// removePred removes all occurrences of p in b's
+// predecessor list and φ-nodes.
+// Ordinarily there should be at most one.
+//
+func (b *BasicBlock) removePred(p *BasicBlock) {
+	phis := b.phis()
+
+	// We must preserve edge order for φ-nodes.
+	j := 0
+	for i, pred := range b.Preds {
+		if pred != p {
+			b.Preds[j] = b.Preds[i]
+			// Strike out φ-edge too.
+			for _, instr := range phis {
+				phi := instr.(*Phi)
+				phi.Edges[j] = phi.Edges[i]
+			}
+			j++
+		}
+	}
+	// Nil out b.Preds[j:] and φ-edges[j:] to aid GC.
+	for i := j; i < len(b.Preds); i++ {
+		b.Preds[i] = nil
+		for _, instr := range phis {
+			instr.(*Phi).Edges[i] = nil
+		}
+	}
+	b.Preds = b.Preds[:j]
+	for _, instr := range phis {
+		phi := instr.(*Phi)
+		phi.Edges = phi.Edges[:j]
+	}
+}
+
+// Destinations associated with unlabelled for/switch/select stmts.
+// We push/pop one of these as we enter/leave each construct and for
+// each BranchStmt we scan for the innermost target of the right type.
+//
+type targets struct {
+	tail         *targets // rest of stack
+	_break       *BasicBlock
+	_continue    *BasicBlock
+	_fallthrough *BasicBlock
+}
+
+// Destinations associated with a labelled block.
+// We populate these as labels are encountered in forward gotos or
+// labelled statements.
+//
+type lblock struct {
+	_goto     *BasicBlock
+	_break    *BasicBlock
+	_continue *BasicBlock
+}
+
+// funcSyntax holds the syntax tree for the function declaration and body.
+type funcSyntax struct {
+	recvField    *ast.FieldList
+	paramFields  *ast.FieldList
+	resultFields *ast.FieldList
+	body         *ast.BlockStmt
+}
+
+// labelledBlock returns the branch target associated with the
+// specified label, creating it if needed.
+//
+func (f *Function) labelledBlock(label *ast.Ident) *lblock {
+	lb := f.lblocks[label.Obj]
+	if lb == nil {
+		lb = &lblock{_goto: f.newBasicBlock("label." + label.Name)}
+		f.lblocks[label.Obj] = lb
+	}
+	return lb
+}
+
+// addParam adds a (non-escaping) parameter to f.Params of the
+// specified name and type.
+//
+func (f *Function) addParam(name string, typ types.Type) *Parameter {
+	v := &Parameter{
+		Name_: name,
+		Type_: pointer(typ), // address of param
+	}
+	f.Params = append(f.Params, v)
+	return v
+}
+
+func (f *Function) addObjParam(obj types.Object) *Parameter {
+	p := f.addParam(obj.GetName(), obj.GetType())
+	f.objects[obj] = p
+	return p
+}
+
+// start initializes the function prior to generating SSA code for its body.
+// Precondition: f.Type() already set.
+//
+// If f.syntax != nil, f is a Go source function and idents must be a
+// mapping from syntactic identifiers to their canonical type objects;
+// Otherwise, idents is ignored and the usual set-up for Go source
+// functions is skipped.
+//
+func (f *Function) start(mode BuilderMode, idents map[*ast.Ident]types.Object) {
+	if mode&LogSource != 0 {
+		fmt.Fprintf(os.Stderr, "build function %s @ %s\n", f.FullName(), f.Prog.Files.Position(f.Pos))
+	}
+	f.currentBlock = f.newBasicBlock("entry")
+	f.objects = make(map[types.Object]Value) // needed for some synthetics, e.g. init
+	if f.syntax == nil {
+		return // synthetic function; no syntax tree
+	}
+	f.lblocks = make(map[*ast.Object]*lblock)
+
+	// Receiver (at most one inner iteration).
+	if f.syntax.recvField != nil {
+		for _, field := range f.syntax.recvField.List {
+			for _, n := range field.Names {
+				f.addObjParam(idents[n])
+			}
+			if field.Names == nil {
+				f.addParam(f.Signature.Recv.Name, f.Signature.Recv.Type)
+			}
+		}
+	}
+
+	// Parameters.
+	if f.syntax.paramFields != nil {
+		for _, field := range f.syntax.paramFields.List {
+			for _, n := range field.Names {
+				f.addObjParam(idents[n])
+			}
+		}
+	}
+
+	// Results.
+	if f.syntax.resultFields != nil {
+		for _, field := range f.syntax.resultFields.List {
+			// Implicit "var" decl of locals for named results.
+			for _, n := range field.Names {
+				f.results = append(f.results, f.addNamedLocal(idents[n]))
+			}
+		}
+	}
+}
+
+// finish() finalizes the function after SSA code generation of its body.
+func (f *Function) finish(mode BuilderMode) {
+	f.objects = nil
+	f.results = nil
+	f.currentBlock = nil
+	f.lblocks = nil
+	f.syntax = nil
+
+	// Remove any f.Locals that are now heap-allocated.
+	j := 0
+	for _, l := range f.Locals {
+		if !l.Heap {
+			f.Locals[j] = l
+			j++
+		}
+	}
+	// Nil out f.Locals[j:] to aid GC.
+	for i := j; i < len(f.Locals); i++ {
+		f.Locals[i] = nil
+	}
+	f.Locals = f.Locals[:j]
+
+	// Ensure all value-defining Instructions have register names.
+	// (Non-Instruction Values are named at construction.)
+	tmp := 0
+	for _, b := range f.Blocks {
+		for _, instr := range b.Instrs {
+			switch instr := instr.(type) {
+			case *Alloc:
+				// Local Allocs may already be named.
+				if instr.Name_ == "" {
+					instr.Name_ = fmt.Sprintf("t%d", tmp)
+					tmp++
+				}
+			case Value:
+				instr.(interface {
+					setNum(int)
+				}).setNum(tmp)
+				tmp++
+			}
+		}
+	}
+	optimizeBlocks(f)
+
+	if mode&LogFunctions != 0 {
+		f.DumpTo(os.Stderr)
+	}
+	if mode&SanityCheckFunctions != 0 {
+		MustSanityCheck(f, nil)
+	}
+	if mode&LogSource != 0 {
+		fmt.Fprintf(os.Stderr, "build function %s done\n", f.FullName())
+	}
+}
+
+// addNamedLocal creates a local variable, adds it to function f and
+// returns it.  Its name and type are taken from obj.  Subsequent
+// calls to f.lookup(obj) will return the same local.
+//
+// Precondition: f.syntax != nil (i.e. a Go source function).
+//
+func (f *Function) addNamedLocal(obj types.Object) *Alloc {
+	l := f.addLocal(obj.GetType())
+	l.Name_ = obj.GetName()
+	f.objects[obj] = l
+	return l
+}
+
+// addLocal creates an anonymous local variable of type typ, adds it
+// to function f and returns it.
+//
+func (f *Function) addLocal(typ types.Type) *Alloc {
+	v := &Alloc{Type_: pointer(typ)}
+	f.Locals = append(f.Locals, v)
+	f.emit(v)
+	return v
+}
+
+// lookup returns the address of the named variable identified by obj
+// that is local to function f or one of its enclosing functions.
+// If escaping, the reference comes from a potentially escaping pointer
+// expression and the referent must be heap-allocated.
+//
+func (f *Function) lookup(obj types.Object, escaping bool) Value {
+	if v, ok := f.objects[obj]; ok {
+		if escaping {
+			switch v := v.(type) {
+			case *Capture:
+				// TODO(adonovan): fix: we must support this case.
+				// Requires copying to a 'new' Alloc.
+				fmt.Fprintln(os.Stderr, "Error: escaping reference to Capture")
+			case *Parameter:
+				v.Heap = true
+			case *Alloc:
+				v.Heap = true
+			default:
+				panic(fmt.Sprintf("Unexpected Function.objects kind: %T", v))
+			}
+		}
+		return v // function-local var (address)
+	}
+
+	// Definition must be in an enclosing function;
+	// plumb it through intervening closures.
+	if f.Enclosing == nil {
+		panic("no Value for type.Object " + obj.GetName())
+	}
+	v := &Capture{f.Enclosing.lookup(obj, true)} // escaping
+	f.objects[obj] = v
+	f.FreeVars = append(f.FreeVars, v)
+	return v
+}
+
+// emit emits the specified instruction to function f, updating the
+// control-flow graph if required.
+//
+func (f *Function) emit(instr Instruction) Value {
+	return f.currentBlock.emit(instr)
+}
+
+// DumpTo prints to w a human readable "disassembly" of the SSA code of
+// all basic blocks of function f.
+//
+func (f *Function) DumpTo(w io.Writer) {
+	fmt.Fprintf(w, "# Name: %s\n", f.FullName())
+	fmt.Fprintf(w, "# Declared at %s\n", f.Prog.Files.Position(f.Pos))
+	fmt.Fprintf(w, "# Type: %s\n", f.Type())
+
+	if f.Enclosing != nil {
+		fmt.Fprintf(w, "# Parent: %s\n", f.Enclosing.Name())
+	}
+
+	if f.FreeVars != nil {
+		io.WriteString(w, "# Free variables:\n")
+		for i, fv := range f.FreeVars {
+			fmt.Fprintf(w, "# % 3d:\t%s %s\n", i, fv.Name(), fv.Type())
+		}
+	}
+
+	params := f.Params
+	if f.Signature.Recv != nil {
+		fmt.Fprintf(w, "func (%s) %s(", params[0].Name(), f.Name())
+		params = params[1:]
+	} else {
+		fmt.Fprintf(w, "func %s(", f.Name())
+	}
+	for i, v := range params {
+		if i > 0 {
+			io.WriteString(w, ", ")
+		}
+		io.WriteString(w, v.Name())
+	}
+	io.WriteString(w, "):\\n")
+
+	for _, b := range f.Blocks {
+		if b == nil {
+			// Corrupt CFG.
+			fmt.Fprintf(w, ".nil:\\n")
+			continue
+		}
+		fmt.Fprintf(w, ".%s:\t\t\t\t\t\t\t\t       P:%d S:%d\n", b.Name, len(b.Preds), len(b.Succs))
+		if false { // CFG debugging
+			fmt.Fprintf(w, "\t# CFG: %s --> %s --> %s\n", blockNames(b.Preds), b.Name, blockNames(b.Succs))
+		}
+		for _, instr := range b.Instrs {
+			io.WriteString(w, "\t")
+			if v, ok := instr.(Value); ok {
+				l := 80 // for old time's sake.
+				// Left-align the instruction.
+				if name := v.Name(); name != "" {
+					n, _ := fmt.Fprintf(w, "%s = ", name)
+					l -= n
+				}
+				n, _ := io.WriteString(w, instr.String())
+				l -= n
+				// Right-align the type.
+				if t := v.Type(); t != nil {
+					fmt.Fprintf(w, "%*s", l-9, t)
+				}
+			} else {
+				io.WriteString(w, instr.String())
+			}
+			io.WriteString(w, "\n")
+		}
+	}
+	fmt.Fprintf(w, "\n")
+}
+
+// newBasicBlock adds to f a new basic block with a unique name and
+// returns it.  It does not automatically become the current block for
+// subsequent calls to emit.
+//
+func (f *Function) newBasicBlock(name string) *BasicBlock {
+	b := &BasicBlock{
+		Name: fmt.Sprintf("%d.%s", len(f.Blocks), name),
+		Func: f,
+	}
+	f.Blocks = append(f.Blocks, b)
+	return b
+}

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

https://github.com/golang/go/commit/8f90915692d6a8205a996d1116c9eb703f91c40c

元コミット内容

exp/ssa: (#3 of 5): Function, BasicBlock and optimisations

R=gri, iant, iant
CC=golang-dev
https://golang.org/cl/7202051

変更の背景

このコミットは、Go言語のコンパイラにおける中間表現（IR: Intermediate Representation）としてSSA (Static Single Assignment) 形式を導入するための、一連の変更の3番目にあたります。Goコンパイラは元々、AST (Abstract Syntax Tree) を直接操作してコード生成を行っていましたが、より高度な最適化を適用するためには、SSAのようなより構造化された中間表現が必要とされていました。

exp/ssa パッケージは、GoプログラムのSSA形式への変換と、そのSSA形式に対する最適化を実験的に実装するために作成されました。このコミットでは、SSA形式の基本的な構成要素である Function と BasicBlock の定義、およびそれらに対する初期の最適化パスが導入されています。これにより、Goコンパイラがより効率的で高性能なコードを生成するための基盤が築かれました。

前提知識の解説

1. SSA (Static Single Assignment) 形式

SSA形式は、コンパイラ最適化において広く用いられる中間表現の一種です。SSA形式では、各変数がただ一度だけ代入されるという特性を持ちます。これにより、データフロー解析が大幅に簡素化され、より強力な最適化（例: 共通部分式除去、定数伝播、デッドコード除去など）を適用しやすくなります。

SSA形式の重要な概念として、Φ (Phi) 関数があります。これは、複数の制御フローパスが合流する地点（例: if文やループの終了後）で、異なるパスから来る同じ論理変数に異なるSSA変数名が割り当てられている場合に、それらを結合して単一のSSA変数として扱うために導入されます。Φ関数は、実行時には何も計算を行わず、コンパイラの解析を助けるための論理的な構造です。

2. 制御フローグラフ (CFG: Control Flow Graph)

CFGは、プログラムの実行可能なパスを抽象的に表現したグラフ構造です。

• ノード: プログラムの基本的な実行単位である基本ブロック (Basic Block) を表します。
• エッジ: 基本ブロック間の制御フローの遷移を表します。

3. 基本ブロック (Basic Block)

基本ブロックは、以下の特性を持つ命令のシーケンスです。

• 単一のエントリポイント: 実行は常にブロックの最初の命令から開始されます。
• 単一の終了ポイント: 実行は常にブロックの最後の命令で終了し、次のブロックへ制御が移ります。
• 内部に分岐なし: ブロック内の命令は、最後の命令を除いて、分岐命令を含みません。

コンパイラは、ソースコードをまず基本ブロックに分割し、それらの基本ブロック間の関係をCFGとして構築します。

4. コンパイラ最適化

このコミットで導入される主な最適化は以下の通りです。

• デッドブロック除去 (Dead Block Elimination): どの実行パスからも到達できない基本ブロック（デッドブロック）をCFGから削除する最適化です。これにより、生成されるコードのサイズが削減され、実行効率が向上します。
• ブロック結合 (Block Fusion / Block Merging): ある基本ブロック A の直後に、そのブロックからのみ到達可能で、かつそのブロックにのみ到達可能な基本ブロック B が続く場合（つまり A -> B という一対一の関係がある場合）、A と B を結合して一つの大きな基本ブロック AB にする最適化です。これにより、分岐命令の数を減らし、キャッシュ効率を向上させることができます。
• ジャンプスレッディング (Jump Threading): A -> B -> C のように、基本ブロック B が単一の無条件ジャンプ命令のみを含み、かつ A から B へのジャンプが B から C へのジャンプに置き換えられる場合、A -> C という直接的なエッジを作成する最適化です。これにより、不要なジャンプを削減し、実行パスを短縮します。特に、if 文の条件が定数に評価される場合などに有効です。

技術的詳細

exp/ssa パッケージは、Goプログラムの抽象構文木 (AST) からSSA形式の中間表現を構築し、それに対して様々な最適化を適用するためのフレームワークを提供します。

func.go では、Function と BasicBlock というSSA形式の基本的な構成要素が定義されています。

• Function は、Goの関数に対応し、その関数内のすべての BasicBlock を管理します。また、関数のパラメータ、ローカル変数、フリー変数（クロージャでキャプチャされる変数）なども管理します。
• BasicBlock は、命令のリスト (Instrs)、先行ブロック (Preds)、後続ブロック (Succs) を持ち、CFGのノードを構成します。

blockopt.go では、optimizeBlocks 関数が定義されており、これは Function 内の BasicBlock に対して、デッドブロック除去、ブロック結合、ジャンプスレッディングといった基本的な制御フロー最適化を適用します。これらの最適化は、コンパイラのバックエンドでコード生成の前に実行され、生成される機械語コードの効率を向上させることを目的としています。

特に、optimizeBlocks は、変更がなくなるまでループを繰り返すことで、複数の最適化パスを適用します。これは、ある最適化が別の最適化の機会を生み出す可能性があるため、一般的なコンパイラ最適化の手法です。

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

このコミットでは、以下の2つのファイルが新規作成されています。

• src/pkg/exp/ssa/blockopt.go: 制御フローグラフの最適化（デッドブロック除去、ブロック結合、ジャンプスレッディング）を実装する関数群が含まれます。
• src/pkg/exp/ssa/func.go: Function および BasicBlock 型の定義、およびそれらの操作（エッジの追加、命令の発行、先行/後続ブロックの置換/削除など）に関するメソッドが含まれます。

合計で594行のコードが追加されており、これは exp/ssa パッケージのSSA中間表現の基盤と初期最適化の大部分を形成しています。

コアとなるコードの解説

src/pkg/exp/ssa/func.go

このファイルは、SSA形式の基本的なデータ構造を定義しています。

• addEdge(from, to *BasicBlock): 制御フローグラフに from から to へのエッジを追加します。from の後続ブロックリスト (Succs) に to を追加し、to の先行ブロックリスト (Preds) に from を追加します。
• (*BasicBlock) emit(i Instruction) Value: 現在の基本ブロックに命令 i を追加します。命令が Value を定義する場合、その Value を返します。
• (*BasicBlock) phis() []Instruction: 基本ブロックの先頭にあるΦ関数（Phi ノード）のリストを返します。Φ関数は、複数の制御フローパスが合流する地点で変数の値を結合するために使用されます。
• (*BasicBlock) replacePred(p, q *BasicBlock): 基本ブロックの先行ブロックリスト内で、p のすべての出現を q に置き換えます。
• (*BasicBlock) replaceSucc(p, q *BasicBlock): 基本ブロックの後続ブロックリスト内で、p のすべての出現を q に置き換えます。
• (*BasicBlock) removePred(p *BasicBlock): 基本ブロックの先行ブロックリストおよびΦ関数のエッジから、p のすべての出現を削除します。これは、デッドブロック除去やジャンプスレッディングの際に、不要になったエッジを削除するために使用されます。
• (*Function) start(mode BuilderMode, idents map[*ast.Ident]types.Object): 関数のSSAコード生成を開始する前に、関数を初期化します。エントリブロックの作成、パラメータと結果変数の処理などを行います。
• (*Function) finish(mode BuilderMode): 関数のSSAコード生成が完了した後に、関数を最終処理します。ローカル変数のヒープ割り当ての調整、命令へのレジスタ名の割り当て、そして optimizeBlocks 関数を呼び出してブロック最適化を実行します。
• (*Function) addParam(name string, typ types.Type) *Parameter: 関数にパラメータを追加します。
• (*Function) addNamedLocal(obj types.Object) *Alloc: 名前付きローカル変数を関数に追加します。
• (*Function) addLocal(typ types.Type) *Alloc: 匿名ローカル変数を関数に追加します。
• (*Function) lookup(obj types.Object, escaping bool) Value: 指定されたオブジェクト（変数）に対応する Value を検索します。クロージャによるキャプチャも考慮されます。
• (*Function) emit(instr Instruction) Value: 現在のブロックに命令を発行します。
• (*Function) DumpTo(w io.Writer): 関数のSSAコードを人間が読める形式で出力します。デバッグや解析に非常に役立ちます。
• (*Function) newBasicBlock(name string) *BasicBlock: 新しい基本ブロックを作成し、関数に追加します。

src/pkg/exp/ssa/blockopt.go

このファイルは、Function の BasicBlock に対する基本的な最適化を実装しています。

• prune(f *Function, i int, b *BasicBlock) bool: デッドブロック除去を行います。基本ブロック b が到達不可能（先行ブロックがない、または自身へのループのみ）である場合、そのブロックをCFGから切断し、削除します。エントリブロックは削除されません。
• jumpThreading(f *Function, i int, b *BasicBlock) bool: ジャンプスレッディングを行います。基本ブロック b が単一の Jump 命令のみを含み、A -> B -> C のような構造になっている場合、A -> C という直接的なエッジに置き換えます。Φ関数を持つブロックに対しては、追加の処理が必要なため、現時点では適用されません。
• fuseBlocks(f *Function, a *BasicBlock) bool: ブロック結合を行います。基本ブロック a が単一の後続ブロック b を持ち、かつ b が単一の先行ブロック a を持つ場合（つまり a -> b が一対一の関係である場合）、a と b を結合して一つのブロックにします。これにより、a の末尾のジャンプ命令が不要になり、b の命令が a にマージされます。
• optimizeBlocks(f *Function): Function 内のすべての基本ブロックに対して、prune、fuseBlocks、jumpThreading の各最適化を、変更がなくなるまで繰り返し適用します。これにより、CFGが簡素化され、後続の最適化やコード生成の効率が向上します。最後に、削除された（nil になった）ブロックを f.Blocks スライスから除去し、メモリを解放します。

これらの関数は、コンパイラの最適化フェーズにおいて、SSA中間表現の品質を向上させ、最終的な機械語コードの性能を高めるために不可欠な役割を果たします。

関連リンク

• Go SSA Builder Design Document: https://go.dev/s/go13ssa (このコミットが関連するGo 1.3のSSAビルダーに関する設計ドキュメント)
• Go issue 5800: cmd/gc: generate SSA form for functions: https://go.dev/issue/5800 (GoコンパイラにおけるSSA導入のメインイシュー)

参考にした情報源リンク

• Static single assignment form - Wikipedia: https://en.wikipedia.org/wiki/Static_single_assignment_form
• Control-flow graph - Wikipedia: https://en.wikipedia.org/wiki/Control-flow_graph
• Basic block - Wikipedia: https://en.wikipedia.org/wiki/Basic_block
• Compiler optimization - Wikipedia: https://en.wikipedia.org/wiki/Compiler_optimization
• Go 1.3 Release Notes - SSA: https://go.dev/doc/go1.3#ssa
• Go source code (exp/ssa package): https://github.com/golang/go/tree/master/src/cmd/compile/internal/ssa (現在のGoコンパイラのSSAパッケージの場所。exp/ssa は実験的なものであり、後にこの場所に移管された)
• golang/go commit 8f90915692d6a8205a996d1116c9eb703f91c40c: https://github.com/golang/go/commit/8f90915692d6a8205a996d1116c9eb703f91c40c