cmd/compile: storing pointer of a local value escapes

[dsnet]

Using go.1.5.1

Consider the following program:

package main

func foo() {
    type node struct{ n0, n1 *node }
    var nodeCache [1024]node
    var nodePtrs [1024]*node
    nodes := nodePtrs[:0]

    n := &nodeCache[0]
    n.n0 = &nodeCache[1]
    n.n1 = &nodeCache[2]

    nodes = append(nodes, n)
}

func main() {
}

Currently, the compiler thinks that nodeCache escapes:

joetsai@zynx: ~ $ go build -gcflags=-m main11.go 
# command-line-arguments
./main11.go:16: can inline main
./main11.go:5: moved to heap: nodeCache
./main11.go:10: &nodeCache[1] escapes to heap
./main11.go:11: &nodeCache[2] escapes to heap
./main11.go:9: &nodeCache[0] escapes to heap
./main11.go:7: foo nodePtrs does not escape

The compiler should be able to track that pointers to nodeCache leak to nodePtrs and since nodePtrs never escapes, nodeCache never escapes as well.

This would be really useful for operating on trees and graphs (that are bounded in size) without any heap allocations.

[randall77]

@dr2chase

[dr2chase]

I think this requires tracking the size of nodes (as a slice) to know that the append won't require a heap (re)allocation, so this is not likely to happen especially soon. I can imagine optimistically performing SSA before escape analysis and doing escape analysis there (along with constant propagation and bounds check elimination) but what you see here is the sum total of the thought that's been put into it.

[rsc]

It's not just the append. There are cycles here that in general are very difficult to represent precisely in the analysis. I don't see this happening any time soon.

[gopherbot]

CL https://golang.org/cl/20959 mentions this issue.

[cespare]

I think the cycle issue here is the same as #7921 in which bytes.Buffer is heap-allocated if you call the WriteXxx methods.

[mdempsky]

@cespare I think this issue is separate from (and trickier than) #7921.

A simpler test case demonstrating this issue is:

var s [1]*int
_ = append(s[:0], new(int))

Currently new(int) escapes to heap because we pessimistically assume append might need to allocate a new slice on the heap and copy the arguments there. To fix this issue, escape analysis would need to be able to do range analysis to know we can do an in-place append.

I expect the long-term way to address this is to defer running escape analysis until after SSA form.