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

このコミットは、Go言語の実験的なSSA (Static Single Assignment) パッケージ (exp/ssa) において、SSAグラフの構造をより効率的に辿るための新しいメソッド Instruction.Operands と Value.Referrers を追加するものです。これらのメソッドは、後続のSSAリネームなどの最適化処理のために、命令が使用する値（オペランド）と、ある値を使用する命令（参照元）をプログラム的に取得する機能を提供します。

コミット

commit 928fe516616f6a9acae814acd90c00209029f99d
Author: Alan Donovan <adonovan@google.com>
Date:   Wed Feb 13 00:15:07 2013 -0500

    exp/ssa: add Instruction.Operands and Value.Referrers methods.
    
    Operands returns the SSA values used by an instruction.
    Referrers returns the SSA instructions that use a value, for
    some values.  These will be used for SSA renaming, to follow.
    
    R=iant, gri
    CC=golang-dev
    https://golang.org/cl/7312090

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

https://github.com/golang/go/commit/928fe516616f6a9acae814acd90c00209029f99d

元コミット内容

exp/ssa パッケージに Instruction.Operands および Value.Referrers メソッドを追加します。

Operands は命令が使用するSSA値を返します。 Referrers は、一部の値について、その値を使用するSSA命令を返します。これらのメソッドは、後続のSSAリネームのために使用されます。

変更の背景

コンパイラの最適化において、SSA (Static Single Assignment) 形式は非常に強力な中間表現です。SSA形式では、各変数が一度だけ定義されるため、データフロー解析や最適化が容易になります。しかし、SSAグラフ上での効率的なナビゲーションは、様々な最適化パス（例えば、デッドコード削除、共通部分式除去、レジスタ割り当て、そしてこのコミットで言及されているSSAリネームなど）を実装するために不可欠です。

このコミット以前は、SSA命令がどの値を使用しているか、またはある値がどの命令によって使用されているかを直接的に問い合わせる標準的なメカニズムが exp/ssa パッケージにはありませんでした。これらの情報は、SSAグラフを効率的に走査し、変数の定義と使用の関係を追跡するために必要です。特に「SSAリネーム」は、SSA形式の変数を実際のレジスタやメモリ位置に割り当てる前に行われる重要なステップであり、変数の使用箇所を正確に特定する能力が求められます。

したがって、Instruction.Operands と Value.Referrers メソッドの追加は、exp/ssa パッケージの機能性を向上させ、より高度なSSAベースの最適化を可能にするための基盤を構築することを目的としています。

前提知識の解説

SSA (Static Single Assignment) 形式

SSA形式は、コンパイラの中間表現の一種で、プログラム内の各変数が一度だけ定義されるという特性を持ちます。これにより、データフロー解析が大幅に簡素化され、多くの最適化がより効果的に行えるようになります。

例:

a = x + y
b = a + 1
a = z + w  // SSAではこれは許されない。新しい変数名が必要 (例: a1)

SSA形式では、上記のコードは次のようになります:

a0 = x + y
b0 = a0 + 1
a1 = z + w

このように、変数の定義ごとに新しいバージョンが作成されます。

SSAグラフの要素

Value (値): SSA形式における「値」は、計算結果や定数、関数の引数などを表します。各値は一意の定義を持ちます。
Instruction (命令): SSAグラフにおける「命令」は、値を生成したり、副作用を持つ操作（例: メモリへの書き込み、関数呼び出し）を実行したりするものです。命令は0個以上のオペランド（入力値）を取り、0個以上の結果値（出力値）を生成します。
Operands (オペランド): ある命令がその計算のために使用する入力値のことです。例えば、c = a + b という命令では、a と b がオペランドです。
Referrers (参照元): ある値が、どの命令によって使用されているかを示すものです。これはオペランドの逆の関係にあたります。例えば、値 a が命令 c = a + b と d = a * 2 の両方で使用されている場合、これらの2つの命令が a の参照元となります。

SSAリネーム

SSAリネームは、SSA形式の変数を、コンパイラのバックエンドが理解できる形式（例えば、レジスタやメモリ位置）にマッピングするプロセスの一部です。これには、変数のライブ範囲（定義されてから最後に使用されるまでの期間）を分析し、競合するライブ範囲を持つ変数を異なるレジスタに割り当てるなどの作業が含まれます。Operands と Referrers の情報は、このライブ範囲分析やレジスタ割り当ての際に、変数の定義と使用の関係を効率的に追跡するために不可欠です。

技術的詳細

このコミットの主要な変更点は、Value インターフェースと Instruction インターフェースに新しいメソッドを追加し、それらの実装を提供することです。

`Value.Referrers() *[]Instruction`

目的: このメソッドは、特定のSSA値を使用するすべての命令のリストへのポインタを返します。これにより、ある値がプログラムのどこで使われているかを効率的に追跡できます。
戻り値の型: *[]Instruction とポインタを返すことで、呼び出し元が参照元のリストを直接変更できる柔軟性を提供します。これは、SSAリネームのような最適化で、参照元を動的に更新する必要がある場合に有用です。
実装の制約: コミットメッセージにもあるように、Referrers は現在、関数ローカルな値（Capture, Parameter、および値定義命令）に対してのみ定義されています。Function, Builtin, Literal, Global のような値に対しては nil を返します。これは、これらの値の参照元を追跡する必要性が低いか、追跡方法が異なるためと考えられます。
構築タイミング: Referrers の情報は、func.go 内の Function.finish() メソッドの最後で構築されます。これは、SSAグラフが完全に構築された後、最適化フェーズに入る前に、参照元情報を一度に計算してキャッシュするためです。

`Instruction.Operands(rands []Value) []Value`

目的: このメソッドは、特定のSSA命令がオペランドとして使用するすべてのSSA値のリストを返します。これにより、命令の入力依存関係を効率的に取得できます。
引数 rands []*Value: このメソッドは、rands というスライスを引数として受け取り、そのスライスにオペランドのアドレスを追加して返します。これは、メモリ割り当てを避けるための一般的なGoのイディオムです。呼び出し元は、再利用可能なスライスを渡すことで、ガベージコレクションのオーバーヘッドを削減できます。
戻り値: オペランドのアドレスが追加されたスライスを返します。
順序: オペランドが追加される順序は未定義です。
ポインタの利用: 返されるのは *Value のスライスであり、オペランドの値そのものではなく、その値へのポインタです。これにより、クライアントはポインタを介して値を変更できます（例: SSAリネームで値を置き換える場合）。
Value.Referrers との関係: Instruction.Operands は Value.Referrers の逆の関係の一部です。ただし、Referrers はすべての種類の Value に対して追跡されるわけではないため、「一部」の逆関係となります。

`Function.finish()` における `Referrers` グラフの構築

src/pkg/exp/ssa/func.go の Function.finish() メソッドに、Referrers グラフを構築するための新しいループが追加されました。このループは、関数のすべての基本ブロックと命令をイテレートし、各命令のオペランドを抽出し、そのオペランドの Referrers リストに現在の命令を追加します。

// Build immediate-use (referrers) graph.
var rands []*Value
for _, b := range f.Blocks {
    for _, instr := range b.Instrs {
        rands = instr.Operands(rands[:0]) // recycle storage
        for _, rand := range rands {
            if r := *rand; r != nil {
                if ref := r.Referrers(); ref != nil {
                    *ref = append(*ref, instr)
                }
            }
        }
    }
}

このコードは、instr.Operands を呼び出して命令のオペランドを取得し、それぞれのオペランドに対して r.Referrers() を呼び出して参照元リストを取得し、そこに現在の命令 instr を追加しています。rands[:0] は、スライスの容量を再利用しつつ、長さを0にリセットするGoのテクニックです。

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

このコミットでは、主に以下のファイルが変更されています。

src/pkg/exp/ssa/func.go:
- Function.finish() メソッドに、Value.Referrers グラフを構築するためのループが追加されました。
- Capture 構造体の初期化で、Outer フィールドの指定方法が変更されました (Outer: f.Enclosing.lookup(...))。
src/pkg/exp/ssa/ssa.go:
- Value インターフェースに Referrers() *[]Instruction メソッドが追加されました。
- Instruction インターフェースに Operands(rands []*Value) []*Value メソッドが追加されました。
- Capture, Parameter, Alloc, Register 構造体に referrers []Instruction フィールドが追加され、Referrers() メソッドの実装が追加されました。
- Builtin, Global, Function, Literal の Referrers() メソッドが nil を返すように実装されました。
- Alloc, BinOp, CallCommon, ChangeInterface, Conv, Extract, Field, FieldAddr, If, Index, IndexAddr, Jump, Lookup, MakeChan, MakeClosure, MakeInterface, MakeMap, MakeSlice, MapUpdate, Next, Phi, Range, Ret, Select, Send, Slice, Store, TypeAssert, UnOp など、すべての具体的な Instruction 型に対して Operands() メソッドの実装が追加されました。
src/pkg/exp/ssa/interp/interp.go:
- MakeClosure 命令の処理において、instr.Fn の型アサーションが *ssa.Function から *ssa.Function に変更されました。これは、MakeClosure の Fn フィールドが Value 型になったことによる修正です。
src/pkg/exp/ssa/literal.go:
- Literal 型に Referrers() *[]Instruction メソッドが追加され、nil を返すように実装されました。

コアとなるコードの解説

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

`Value` インターフェースの変更

type Value interface {
    // ... 既存のメソッド ...

    // Referrers returns the list of instructions that have this
    // value as one of their operands; it may contain duplicates
    // if an instruction has a repeated operand.
    //
    // Referrers actually returns a pointer through which the
    // caller may perform mutations to the object's state.
    //
    // Referrers is currently only defined for the function-local
    // values Capture, Parameter and all value-defining instructions.
    // It returns nil for Function, Builtin, Literal and Global.
    //
    // Instruction.Operands contains the inverse of this relation.
    Referrers() *[]Instruction

    // Dummy method to indicate the "implements" relation.
    ImplementsValue()
}

Value インターフェースに Referrers() メソッドが追加されました。このメソッドは、その値を使用する命令のリストへのポインタを返します。ポインタを返すことで、呼び出し元がリストを直接変更できる柔軟性を提供します。

`Instruction` インターフェースの変更

type Instruction interface {
    // ... 既存のメソッド ...

    // Operands returns the operands of this instruction: the
    // set of Values it references.
    //
    // Specifically, it appends their addresses to rands, a
    // user-provided slice, and returns the resulting slice,
    // permitting avoidance of memory allocation.
    //
    // The operands are appended in undefined order; the addresses
    // are always non-nil but may point to a nil Value.  Clients
    // may store through the pointers, e.g. to effect a value
    // renaming.
    //
    // Value.Referrers is a subset of the inverse of this
    // relation.  (Referrers are not tracked for all types of
    // Values.)
    Operands(rands []*Value) []*Value

    // Dummy method to indicate the "implements" relation.
    ImplementsInstruction()
}

Instruction インターフェースに Operands() メソッドが追加されました。このメソッドは、命令が参照するSSA値（オペランド）のリストを返します。rands []*Value 引数を使用することで、メモリ割り当てを最小限に抑えながらオペランドを効率的に収集できます。

構造体への `referrers` フィールドの追加と `Referrers()` の実装

Capture, Parameter, Alloc, Register などの構造体に referrers []Instruction というスライスが追加され、それぞれの Referrers() メソッドがこのスライスへのポインタを返すように実装されました。

例:

type Capture struct {
    Outer     Value // the Value captured from the enclosing context.
    referrers []Instruction
}

func (v *Capture) Referrers() *[]Instruction { return &v.referrers }

各 `Instruction` 型の `Operands()` メソッドの実装

BinOp, CallCommon, Phi など、すべての具体的な命令型に対して Operands() メソッドが実装されました。これらの実装は、それぞれの命令が持つフィールドの中からSSA値であるものを抽出し、rands スライスに追加して返します。

例: BinOp (二項演算) の Operands

func (v *BinOp) Operands(rands []*Value) []*Value {
    return append(rands, &v.X, &v.Y)
}

BinOp は X と Y の2つのオペランドを持つため、それらのアドレスを rands スライスに追加しています。

例: Phi (ファイノード) の Operands

func (v *Phi) Operands(rands []*Value) []*Value {
    for i := range v.Edges {
        rands = append(rands, &v.Edges[i])
    }
    return rands
}

Phi ノードは複数のエッジ（入力値）を持つため、ループでそれらすべてのアドレスを追加しています。

`src/pkg/exp/ssa/func.go` の変更

`Function.finish()` における `Referrers` グラフの構築

func (f *Function) finish() {
    // ... 既存の処理 ...

    // Build immediate-use (referrers) graph.
    var rands []*Value
    for _, b := range f.Blocks {
        for _, instr := range b.Instrs {
            rands = instr.Operands(rands[:0]) // recycle storage
            for _, rand := range rands {
                if r := *rand; r != nil {
                    if ref := r.Referrers(); ref != nil {
                        *ref = append(*ref, instr)
                    }
                }
            }
        }
    }

    // ... 既存の処理 ...
}

このコードブロックは、関数内のすべての命令を走査し、各命令のオペランドを取得します。そして、取得したオペランドが Referrers を持つ場合（つまり、Referrers() が nil 以外を返す場合）、そのオペランドの参照元リストに現在の命令を追加します。これにより、SSAグラフの構築が完了した後に、各値の参照元情報が効率的に集約されます。

参考にした情報源リンク

Go言語のソースコード (特に src/pkg/exp/ssa ディレクトリ)
コンパイラ設計に関する一般的な知識 (SSA形式、データフロー解析など)
コミットメッセージと差分情報

comemo

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

コミット

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

元コミット内容

変更の背景

前提知識の解説

SSA (Static Single Assignment) 形式

SSAグラフの要素

SSAリネーム

技術的詳細

`Value.Referrers() *[]Instruction`

`Instruction.Operands(rands []Value) []Value`

`Function.finish()` における `Referrers` グラフの構築

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

コアとなるコードの解説

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

`Value` インターフェースの変更

`Instruction` インターフェースの変更

構造体への `referrers` フィールドの追加と `Referrers()` の実装

各 `Instruction` 型の `Operands()` メソッドの実装

`src/pkg/exp/ssa/func.go` の変更

`Function.finish()` における `Referrers` グラフの構築

関連リンク

参考にした情報源リンク

Keyboard shortcuts

comemo