x/tools/go/ssa/interp: phi nodes are not executed in parallel (the "swap problem")

[chai2010]

Go version

go1.23

Output of go env in your module/workspace:

GO111MODULE=''
GOARCH='amd64'
GOBIN=''
GOCACHE='/Users/chai/Library/Caches/go-build'
GOENV='/Users/chai/Library/Application Support/go/env'
GOEXE=''
GOEXPERIMENT=''
GOFLAGS=''
GOHOSTARCH='amd64'
GOHOSTOS='darwin'
GOINSECURE=''
GOMODCACHE='/Users/chai/go/pkg/mod'
GONOPROXY=''
GONOSUMDB=''
GOOS='darwin'
GOPATH='/Users/chai/go'
GOPRIVATE=''
GOPROXY='https://goproxy.cn,direct'
GOROOT='/usr/local/go'
GOSUMDB='off'
GOTMPDIR=''
GOTOOLCHAIN='auto'
GOTOOLDIR='/usr/local/go/pkg/tool/darwin_amd64'
GOVCS=''
GOVERSION='go1.23.1'
GODEBUG=''
GOTELEMETRY='local'
GOTELEMETRYDIR='/Users/chai/Library/Application Support/go/telemetry'
GCCGO='gccgo'
GOAMD64='v1'
AR='ar'
CC='clang'
CXX='clang++'
CGO_ENABLED='1'
GOMOD='/dev/null'
GOWORK=''
CGO_CFLAGS='-O2 -g'
CGO_CPPFLAGS=''
CGO_CXXFLAGS='-O2 -g'
CGO_FFLAGS='-O2 -g'
CGO_LDFLAGS='-O2 -g'
PKG_CONFIG='pkg-config'
GOGCCFLAGS='-fPIC -arch x86_64 -m64 -pthread -fno-caret-diagnostics -Qunused-arguments -fmessage-length=0 -ffile-prefix-map=/var/folders/d0/q0b3c09s2_nb6sjjhbnf0t1h0000gq/T/go-build2141529561=/tmp/go-build -gno-record-gcc-switches -fno-common'

What did you do?

i use x/tools/go/ssa to print ssa text:

https://go.dev/play/p/dxj4fTu2M5G

package main

import (
	"go/ast"
	"go/parser"
	"go/token"
	"go/types"
	"log"
	"os"

	"golang.org/x/tools/go/ssa"
)

const src = `
package main

func main() {
	root = &mapNode{}
	insert()
	println(root)
}

var root *mapNode

type mapNode struct {
	Child *mapNode
}

func insert() {
	var x *mapNode = root
	var y *mapNode = x
	for x != nil {
		y = x
		println(y)
		x = x.Child
	}
	println(y)
}
`

func main() {
	fset := token.NewFileSet()
	f, err := parser.ParseFile(fset, "hello.go", src, parser.AllErrors)
	if err != nil {
		log.Fatal(err)
	}

	info := &types.Info{
		Types:      make(map[ast.Expr]types.TypeAndValue),
		Defs:       make(map[*ast.Ident]types.Object),
		Uses:       make(map[*ast.Ident]types.Object),
		Implicits:  make(map[ast.Node]types.Object),
		Selections: make(map[*ast.SelectorExpr]*types.Selection),
		Scopes:     make(map[ast.Node]*types.Scope),
	}

	conf := types.Config{Importer: nil}
	pkg, err := conf.Check("hello.go", fset, []*ast.File{f}, info)
	if err != nil {
		log.Fatal(err)
	}

	var ssaProg = ssa.NewProgram(fset, ssa.SanityCheckFunctions)
	var ssaPkg = ssaProg.CreatePackage(pkg, []*ast.File{f}, info, true)

	ssaPkg.Build()

	ssaPkg.WriteTo(os.Stdout)
	ssaPkg.Func("insert").WriteTo(os.Stdout)
}

What did you see happen?

the insert func ssa:

# Name: hello.go.insert
# Package: hello.go
# Location: hello.go:16:6
func insert():
0:                                                                entry P:0 S:1
	t0 = *root                                                     *mapNode
	jump 3
1:                                                             for.body P:1 S:1
	t1 = println(t5)                                                     ()
	t2 = &t5.Child [#0]                                           **mapNode
	t3 = *t2                                                       *mapNode
	jump 3
2:                                                             for.done P:1 S:0
	t4 = println(t6)                                                     ()
	return
3:                                                             for.loop P:2 S:2
	t5 = phi [0: t0, 1: t3] #x                                     *mapNode
	t6 = phi [0: t0, 1: t5] #y                                     *mapNode
	t7 = t5 != nil:*mapNode                                            bool
	if t7 goto 1 else 2

What did you expect to see?

i guess the ssa lose the y = x in for loop. the test code should print(root) twice.

t1 = *root
jump 3

3:
t6 = t1 = *root
t7 = t1 = *toot
t8 = t6 != nil = true
if t8 goto 1 else 2 = goto 1

1:
println(t6) = println(*root)
t3 = &t6.Child = root.Child
t4 = *t3 = t6.Child = root.Child
jump 3

3:
t6 = t4 = t6.Child = root.Child
t7 = t6 = root.Child
t8 = t6 != nil = root.Child != nil = false
if t8 goto 1 else 2 = goto 2

2:
println(t7) = println(root.Child)
return

but the ssa print(root) and print(root.Child).

[gabyhelp]

Related Issues and Documentation

• x/tools/go/ssa/interp: TestGorootTest persistently failing on plan9 #60226 (closed)
• x/tools/go/ssa: panic: cannot convert interface #62085 (closed)
• x/tools/go/ssa: panic: no ssa.Value for function argument #33279
• x/tools/go/ssa/builder.go: panic("nil underlyin") while executing *ssa.Program.Build() #68195 (closed)
• x/tools/go/ssa: multiple assign ssa.FieldAddr instr order error #55086 (closed)
• go/ssa: crash during SSA construction #9569 (closed)
• cmd/compile: GOSSAFUNC=main open ssa.html: permission denied #33278 (closed)
• cmd/compile/internal/ssa: incorrect deadcode elim #47594 (closed)
• x/tools/go/ssa: function.Origin() panics with "index out of range" #59427 (closed)
• x/tools/go/ssa: addNamedLocal panic: runtime error: invalid memory address or nil pointer dereference #58600

_{(Emoji vote if this was helpful or unhelpful; more detailed feedback welcome in this discussion.)}

[adonovan]

The variable y is not lost. It is translated to a phi node, that is, a node whose value depends on which incoming edge control came through to reach the current block:

	t6 = phi [0: t0, 1: t5] #y

The comment tells you that this value corresponds to y, and the phi notation tells you that y's value is either t0 (*root) when coming from block zero (i.e. on the first iteration), or t5 (x) on all later iterations.

Unlike traditional intermediate representations, there are no local assignments in SSA, so you can't "update" y. The representation expresses the conditionality in a stateless form. This is the nature of SSA. I suggest you read some introductory material on the topic, such as the Wikipedia article.

[chai2010]

I hope the development team can treat community feedback with mutual respect. This is my newly added test result.

By comparing “go run hello.go” and “x/tools/go/ssa/interp”, I still found differences when executing the following:

$ go run main.go
0xc0000949b0
<nil>
0xc0000949b0
$ go run ./hello/hello.go 
0xc00004e008
0xc00004e008
0xc00004e008
$ 

As a gopher who doesn't understand SSA, I am rather confused as to why the above two execution results are different?

man.go code:

package main

import (
	"fmt"
	"go/ast"
	"go/parser"
	"go/token"
	"go/types"

	"golang.org/x/tools/go/ssa"
	"golang.org/x/tools/go/ssa/interp"
)

const src = `
package main

func main() {
	root = &mapNode{}
	insert()
	println(root)
}

var root *mapNode

type mapNode struct {
	Child *mapNode
}

func insert() {
	var x *mapNode = root
	var y *mapNode = x
	for x != nil {
		y = x
		println(y)
		x = x.Child
	}
	println(y)
}
`

func main() {
	prog := NewProgram(map[string]string{
		"main": src,
		"runtime": `
			package runtime

			type errorString string

			func (e errorString) RuntimeError() {}
			func (e errorString) Error() string { return "runtime error: " + string(e) }

			type Error interface {
				error
				RuntimeError()
			}
		`,
	})

	prog.LoadPackage("main")
	prog.LoadPackage("runtime")

	var ssaProg = ssa.NewProgram(prog.fset, ssa.SanityCheckFunctions)
	var ssaMainPkg *ssa.Package

	for name, pkg := range prog.pkgs {
		ssaPkg := ssaProg.CreatePackage(pkg, []*ast.File{prog.ast[name]}, prog.infos[name], true)
		if name == "main" {
			ssaMainPkg = ssaPkg
		}
	}
	ssaProg.Build()

	exitCode := interp.Interpret(
		ssaMainPkg, 0, &types.StdSizes{8, 8},
		"main", []string{},
	)
	if exitCode != 0 {
		fmt.Println("exitCode:", exitCode)
	}
}

type Program struct {
	fs    map[string]string
	ast   map[string]*ast.File
	pkgs  map[string]*types.Package
	infos map[string]*types.Info
	fset  *token.FileSet
}

func NewProgram(fs map[string]string) *Program {
	return &Program{
		fs:    fs,
		ast:   make(map[string]*ast.File),
		pkgs:  make(map[string]*types.Package),
		infos: make(map[string]*types.Info),
		fset:  token.NewFileSet(),
	}
}

func (p *Program) LoadPackage(path string) (pkg *types.Package, f *ast.File, err error) {
	if pkg, ok := p.pkgs[path]; ok {
		return pkg, p.ast[path], nil
	}

	f, err = parser.ParseFile(p.fset, path, p.fs[path], parser.AllErrors)
	if err != nil {
		return nil, nil, err
	}

	info := &types.Info{
		Types:      make(map[ast.Expr]types.TypeAndValue),
		Defs:       make(map[*ast.Ident]types.Object),
		Uses:       make(map[*ast.Ident]types.Object),
		Implicits:  make(map[ast.Node]types.Object),
		Selections: make(map[*ast.SelectorExpr]*types.Selection),
		Scopes:     make(map[ast.Node]*types.Scope),
	}

	conf := types.Config{Importer: p}
	pkg, err = conf.Check(path, p.fset, []*ast.File{f}, info)
	if err != nil {
		return nil, nil, err
	}

	p.ast[path] = f
	p.pkgs[path] = pkg
	p.infos[path] = info
	return pkg, f, nil
}

func (p *Program) Import(path string) (*types.Package, error) {
	if pkg, ok := p.pkgs[path]; ok {
		return pkg, nil
	}
	pkg, _, err := p.LoadPackage(path)
	return pkg, err
}

./hello/hello.go:

package main

func main() {
	root = &mapNode{}
	insert()
	println(root)
}

var root *mapNode

type mapNode struct {
	Child *mapNode
}

func insert() {
	var x *mapNode = root
	var y *mapNode = x
	for x != nil {
		y = x
		println(y)
		x = x.Child
	}
	println(y)
}

[3dgen]

The variable y is not lost. It is translated to a phi node, that is, a node whose value depends on which incoming edge control came through to reach the current block:

	t6 = phi [0: t0, 1: t5] #y

The comment tells you that this value corresponds to y, and the phi notation tells you that y's value is either t0 (*root) when coming from block zero (i.e. on the first iteration), or t5 (x) on all later iterations.

Unlike traditional intermediate representations, there are no local assignments in SSA, so you can't "update" y. The representation expresses the conditionality in a stateless form. This is the nature of SSA. I suggest you read some introductory material on the topic, such as the Wikipedia article.

We know how phi works, this problem is not about losing y, it's about incorrect instructions generated by for.

According to SSA code above, on all iterations after for, t5 will always been assigned to t6(y), and t5 always comes from x.child, that means when block 2 is reached, t6 must be nil, obviously it's not right.

Using ssa/interp.Interpret() to run the SSA code above shows exactly the same error.

[adonovan]

Apologies for my previous comment. I mistakenly thought I was addressing someone unfamiliar with SSA basics, though even if that were so I now see how the tone of my comment came across as condescending.

The subtlety in this case is that the two phis are interdependent:

        t5 = phi(t0, t3) # x 
        t6 = phi(t0, t5) # y

The SSA builder acts as if all consecutive phis are executed in parallel, which is consistent with the interpretation that phis are really virtual instructions at the end of each predecessor block. Annotating the purpose of each value below shows that the final print(t6) is correct: it prints the value of y on entry to the final (false) loop test:

entry:
        t0 = *root     // t0 is x or y before loop
        jump test

body:
        println(t5)    // t5 is x at loop entry
	t3 = t5.Child // t3 is x after loop
	jump test

test:
        t5 = phi(t0, t3) // t5 is x at loop entry
        t6 = phi(t0, t5) // t6 is y at loop entry
	if t5 != nil goto body else done

done:
        println(t6)
	return

However, the ssa/interp logic gets this case wrong because it shouldn't update the environment for t5 and t6 one instruction at a time; it must wait until both phis have been evaluated. So I think this is a problem in the interpreter, not the builder, though perhaps the documentation should clarify the parallel nature of phis.

[3dgen]

...
However, the ssa/interp logic gets this case wrong because it shouldn't update the environment for t5 and t6 one instruction at a time; it must wait until both phis have been evaluated. So I think this is a problem in the interpreter, not the builder, though perhaps the documentation should clarify the parallel nature of phis.

That explains all.

Thanks!

[adonovan]

For how to efficiently replace phi nodes with explicit copies while preserving parallel semantics, see the "swap problem" in Briggs et al's Practical Improvements to the Construction and Destruction of Static Single Assignment Form.

[gopherbot]

Change https://go.dev/cl/621595 mentions this issue: go/ssa/interp: assign phi nodes in parallel

[adonovan]

Thanks for reporting the bug, with a nice reproducible test case.