静的単一代入(SSA)形式

SSA形式とは、変数の定義がプログラムの字面上で唯一になるようにしたプログラムの表現形式である。静的とは、プログラムの字面上で、という意味である。変数の定義が唯一になるように変数の名前替えを行うが、これは普通変数の添字をつけて表す。この結果、SSA形式ではプログラムの上で、変数の定義が1箇所だけになる。

参考: http://coins-compiler.osdn.jp/050303/ssa/ssa-nyumon.pdf

Go言語のSSA

コンパイラで用いるSSAと解析用のSSAのパッケージは異なる。静的解析用のパッケージを使う。

コンパイラ用
- https://github.com/golang/go/tree/master/src/cmd/compile/internal/ssa
静的解析用
- https://github.com/golang/tools/tree/master/go/ssa

SSA形式でわかること/わからないこと

参考: ソースコードを堪能せよ

わかること

コントロールグラフ
- 分岐や繰り返しの簡略化
- 処理の前後関係を追いやすい
- 有向グラフなのでグラフ理論のアルゴリズムが使える
単一の代入であることが保証されている
- 同じ値に対する処理を見つけやすい
  - ある値のメソッドを呼び出しているか

わからないこと

公開された変数への代入
- 外部パッケージから変更される可能性がある
ポインタを介した変更
- どう変更されるかわからない
- unsafe.Pointerを用いるとポインタ演算されてしまう
インターフェースを介した処理
- どう代入されるかわからない
リフレクションを介した動作
- 動的に決まるので難しい

パッケージの全体像

ソースコードを堪能せよ P.34 より引用

実装例

ディレクトリ構成は以下を想定する。

.
├── cmd
│   └── sample-analysis
│       └── main.go
├── go.mod
├── go.sum
├── sample-analysis.go
├── sample-analysis_test.go
└── testdata
    └── src
        └── a
            └── a.go

a.go が検査したいコードである。

a.go

package a

func f() {
    n := 10
    if n < 10 {
        println("n < 10")
    } else {
        println("n >= 10")
    }
}

まずはSSA形式でどのように出力されるか確認してみる。

sample-analysis.go

package testanalysis

import (
    "fmt"
    "os"

    "golang.org/x/tools/go/analysis"
    "golang.org/x/tools/go/analysis/passes/buildssa"
)

var Analyzer = &analysis.Analyzer{
    Name: "sample-analysis",
    Doc:  Doc,
    Run:  run,
    Requires: []*analysis.Analyzer{
        buildssa.Analyzer,
    },
}

const Doc = "sample-analysis is ..."

func run(pass *analysis.Pass) (interface{}, error) {
    funcs := pass.ResultOf[buildssa.Analyzer].(*buildssa.SSA).SrcFuncs

    for i := range funcs {
        // デバッグ出力
        funcs[i].WriteTo(os.Stdout)
        for _, b := range funcs[i].Blocks {
            fmt.Printf("funcs[i].Blocks -> %#v\n", funcs[i].Blocks)
            // すべての命令を調べる
            for _, instr := range b.Instrs {
                fmt.Printf("instr -> %#v\n", instr)
            }
        }
    }

    return nil, nil
}

sample-analysis_test.go

package testanalysis_test

import (
    "testing"

    "github.com/d-tsuji/testanalysis"

    "golang.org/x/tools/go/analysis/analysistest"
)

func Test(t *testing.T) {
    testdata := analysistest.TestData()
    analysistest.Run(t, testdata, testanalysis.Analyzer, "a")
}

テストとして実行すると、以下のように出力されることがわかる。

$ go test
# Name: a.f
# Package: a
# Location: C:\Users\dramt\go\src\github.com\d-tsuji\testanlysis\testdata\src\a\a.go:3:6
func f():
0:                                                                entry P:0 S:2
        t0 = 10:int < 10:int                                               bool
        if t0 goto 1 else 3
1:                                                              if.then P:1 S:1
        t1 = println("n < 10":string)                                        ()
        jump 2
2:                                                              if.done P:2 S:0
        return
3:                                                              if.else P:1 S:1
        t2 = println("n >= 10":string)                                       ()
        jump 2

funcs[i].Blocks -> []*ssa.BasicBlock{(*ssa.BasicBlock)(0xc0002d2210), (*ssa.BasicBlock)(0xc0002d22c0), (*ssa.BasicBlock)(0xc0002d2370), (*ssa.BasicBlock)(0xc0002d2420)}
instr -> &ssa.BinOp{register:ssa.register{anInstruction:ssa.anInstruction{block:(*ssa.BasicBlock)(0xc0002d2210)}, num:0, typ:(*types.Basic)(0xa87ea0), pos:38, referrers:[]ssa.Instruction{(*ssa.If)(0xc000187c40)}}, Op:40, X:(*ssa.Const)(0xc000187ba0), Y:(*ssa.Const)(0xc000187c20)}
instr -> &ssa.If{anInstruction:ssa.anInstruction{block:(*ssa.BasicBlock)(0xc0002d2210)}, Cond:(*ssa.BinOp)(0xc0001c81c0)}
funcs[i].Blocks -> []*ssa.BasicBlock{(*ssa.BasicBlock)(0xc0002d2210), (*ssa.BasicBlock)(0xc0002d22c0), (*ssa.BasicBlock)(0xc0002d2370), (*ssa.BasicBlock)(0xc0002d2420)}
instr -> &ssa.Call{register:ssa.register{anInstruction:ssa.anInstruction{block:(*ssa.BasicBlock)(0xc0002d22c0)}, num:1, typ:(*types.Tuple)(nil), pos:0, referrers:[]ssa.Instruction(nil)}, Call:ssa.CallCommon{Value:(*ssa.Builtin)(0xc000187c60), Method:(*types.Func)(nil), Args:[]ssa.Value{(*ssa.Const)(0xc000187c80)}, pos:54}}
instr -> &ssa.Jump{anInstruction:ssa.anInstruction{block:(*ssa.BasicBlock)(0xc0002d22c0)}}
funcs[i].Blocks -> []*ssa.BasicBlock{(*ssa.BasicBlock)(0xc0002d2210), (*ssa.BasicBlock)(0xc0002d22c0), (*ssa.BasicBlock)(0xc0002d2370), (*ssa.BasicBlock)(0xc0002d2420)}
instr -> &ssa.Return{anInstruction:ssa.anInstruction{block:(*ssa.BasicBlock)(0xc0002d2370)}, Results:[]ssa.Value(nil), pos:0}
funcs[i].Blocks -> []*ssa.BasicBlock{(*ssa.BasicBlock)(0xc0002d2210), (*ssa.BasicBlock)(0xc0002d22c0), (*ssa.BasicBlock)(0xc0002d2370), (*ssa.BasicBlock)(0xc0002d2420)}
instr -> &ssa.Call{register:ssa.register{anInstruction:ssa.anInstruction{block:(*ssa.BasicBlock)(0xc0002d2420)}, num:2, typ:(*types.Tuple)(nil), pos:0, referrers:[]ssa.Instruction(nil)}, Call:ssa.CallCommon{Value:(*ssa.Builtin)(0xc000187cc0), Method:(*types.Func)(nil), Args:[]ssa.Value{(*ssa.Const)(0xc000187ce0)}, pos:84}}
instr -> &ssa.Jump{anInstruction:ssa.anInstruction{block:(*ssa.BasicBlock)(0xc0002d2420)}}
--- PASS: Test (0.15s)
PASS

ここからわかることは、全部で4つのBlockに分かれているということだ。いくつか最適化されている気がする。例えば n := 10 という宣言が出力されていない。if 文の条件を締めているブロック 0 にはリテラルとして 10:int と表示されている。return の条件が使い回されているのが面白い。つまりブロック1からも3からも最終的にブロック2の return を呼び出している。

余談だが、ブラウザ上でソースコードをSSA形式に変換して表示してくれるサイトがあった。面白いし、役に立つ。

https://golang-ssaview.herokuapp.com/

ドキュメント

BasicBlock

BasicBlock は以下のような構造体である。

type BasicBlock struct {
    Index        int            // index of this block within Parent().Blocks
    Comment      string         // optional label; no semantic significance
    parent       *Function      // parent function
    Instrs       []Instruction  // instructions in order
    Preds, Succs []*BasicBlock  // predecessors and successors
    succs2       [2]*BasicBlock // initial space for Succs
    dom          domInfo        // dominator tree info
    gaps         int            // number of nil Instrs (transient)
    rundefers    int            // number of rundefers (transient)
}

Instruction を内包していて Instruction は以下のようなメソッドをもつインターフェースである。(ドキュメントを除く)

Instruction

type Instruction interface {
    String() string
    Parent() *Function
    Block() *BasicBlock
    setBlock(*BasicBlock)
    Operands(rands []*Value) []*Value
    Pos() token.Pos
}

Instruction インターフェースを満たしている構造体は以下の通りである。同様に Value インターフェースや Member インターフェースを満たしている構造体もGoDocに示されている。

https://godoc.org/golang.org/x/tools/go/ssa

	Value?	Instruction?	Member?
*Alloc	✔	✔
*BinOp	✔	✔
*Builtin	✔
*Call	✔	✔
*ChangeInterface	✔	✔
*ChangeType	✔	✔
*Const	✔
*Convert	✔	✔
*DebugRef		✔
*Defer		✔
*Extract	✔	✔
*Field	✔	✔
*FieldAddr	✔	✔
*FreeVar	✔
*Function	✔	✔	(func)
*Global	✔	✔	(var)
*Go		✔
*If		✔
*Index	✔	✔
*IndexAddr	✔	✔
*Jump		✔
*Lookup	✔	✔
*MakeChan	✔	✔
*MakeClosure	✔	✔
*MakeInterface	✔	✔
*MakeMap	✔	✔
*MakeSlice	✔	✔
*MapUpdate		✔
*NamedConst		✔	(const)
*Next	✔	✔
*Panic		✔
*Parameter	✔
*Phi	✔	✔
*Range	✔	✔
*Return		✔
*RunDefers		✔
*Select	✔	✔
*Send		✔
*Slice	✔	✔
*Store		✔
*Type		✔	(type)
*TypeAssert	✔	✔
*UnOp	✔	✔

BasicBlock のグラフを遷移するには Instruction を型アサーションして、型に応じた処理をすることになるだろう。

例えば nilerr というチェックツールでは以下のようにして、条件を取り出している。if文の条件を取得する実装は b.Instrs[len(b.Instrs)-1].(*ssa.If) である。*If の型であることがわかると、Condフィールド(これも Value インターフェースを満たしている)が取得できるため、これが *BinOp 型であるかどうか型アサーションをして確かめ、*BinOp 型であれば、必要なフィールドを用いて、ロジックを実装することになる。

func binOpErrNil(b *ssa.BasicBlock, op token.Token) ssa.Value {
    if len(b.Instrs) == 0 {
        return nil
    }

    ifinst, ok := b.Instrs[len(b.Instrs)-1].(*ssa.If)
    if !ok {
        return nil
    }

    binop, ok := ifinst.Cond.(*ssa.BinOp)
    if !ok {
        return nil
    }

    if binop.Op != op {
        return nil
    }

    if !types.Implements(binop.X.Type(), errType) {
        return nil
    }

    if !types.Implements(binop.Y.Type(), errType) {
        return nil
    }

    xIsConst, yIsConst := isConst(binop.X), isConst(binop.Y)
    switch {
    case !xIsConst && yIsConst: // err != nil or err == nil
        return binop.X
    case xIsConst && !yIsConst: // nil != err or nil == err
        return binop.Y
    }

    return nil
}

func isConst(v ssa.Value) bool {
    _, ok := v.(*ssa.Const)
    return ok
}

https://github.com/gostaticanalysis/nilerr/blob/master/nilerr.go#L58-L99

*BinOp 型に含まれる X や Y フィールドもまた Value インターフェースであるため、定数かどうかは *Const 型であるかどうか型アサーションをすることになる。このあたりは割と愚直な印象である。

技術メモ

ラフなメモ

Goで静的単一代入(SSA)形式に入門する