Repository: go
Issue: cmd/compile/internal/gc: generalize self-assignment handling in escape analysis
Labels: Performance,NeedsInvestigation

Right now, there are at least 2 quite adhoc patterns that are recognized by
escape analysis as safe. It skips detailed analysis when it sees
self-assignment statement that does not introduce new pointers that need tracking.

Initially, only some simple self-slicing assignments like this were handled:

```go
x.buf = x.buf[a:b]
```

Later, some more patterns were added, so these are recognized, too:

```go
x.ptr1 = x.ptr2
val.pointers[i] = val.pointers[j]
```

The problem with them is that they are very fragile and can't match expressions
that are different from the simplest cases, but still represents self-assignments:

```go
x.a.b.buf = x.a.b.buf[a:b]
```

It is possible to generalize all self-assignment patterns with a concept of "base object".
What we see above is a matching of object field assignment to the object itself.
The base object is that object, the one that contains referenced field.

For the simplest cases, base object is just 1 syntactical level "above":

```go
base(x.y)     // => x
base(x.y.z)   // => x.y
base(x[i])    // => x
base(x[i][j]) // => x[i]
```

For cases where expression effectively returns the same object, we can skip several levels:

```go
base(x[:])    => x
base(x[:][:]) => x
```

Given `base` function, we can express self-assignment as (pseudo Go):

```go
// See samesafeexpr from cmd/compile/internal/gc/typecheck.go
return samesafeexpr(base(dst), base(src))
```

This covers all patterns above, plus a few more.
As a bonus, it also solves trivial `*p = *p` case (see https://github.com/golang/go/issues/5919):

```go
func j(p *string) {
	*p = *p
}
```

More interesting examples of self-assignments that were not recognized until generalization:

```go
type node struct { next *node }
func createLoop(n *node) {
	n.next = n // n was leaking param before
}
```

```go
type foo struct {
	pi *int
	i  int
}
func (f *foo) example() {
	f.pi = &f.i // f was leaking param before
}
```

This solution (if it is correct or can be made correct):
- Makes self-assignment check less adhoc, more powerfull (hopefully, more useful)
- It makes implementation simpler, reduces code duplication

<hr>

Collect new escape analysis results info:

```bash
go build -a -gcflags=-m ./src/... 2>&1 | grep 'does not escape' > new_noescapes.txt
go build -a -gcflags=-m ./src/... 2>&1 | grep 'leaking param' > new_leakparam.txt
```

And now with unpatched `go tool compile`:

```bash
go build -a -gcflags=-m ./src/... 2>&1 | grep 'does not escape' > old_noescapes.txt
go build -a -gcflags=-m ./src/... 2>&1 | grep 'leaking param' > old_leakparam.txt
```

Now it is possible to do some comparisons.

New non-escaping values/parameters:

```
src/net/net.go:687:7: (*Buffers).consume v does not escape
src/net/net.go:674:7: (*Buffers).Read v does not escape
src/internal/poll/fd.go:48:14: consume v does not escape
src/compress/flate/inflate.go:325:10: (*decompressor).nextBlock &f.h1 does not escape
src/compress/flate/inflate.go:326:10: (*decompressor).nextBlock &f.h2 does not escape
src/cmd/compile/internal/gc/const.go:668:15: evconst &nl does not escape
src/container/ring/ring.go:121:7: (*Ring).Len r does not escape
src/cmd/compile/internal/types/type.go:727:13: (*Type).copy &nt does not escape
```

Since `ring.Ring.Len` receiver no longer escapes, we can try to verify and measure it with benchmarks:

```go
package foo

import (
	"container/ring"
	"testing"
)

func BenchmarkRingLen(b *testing.B) {
	for i := 0; i < b.N; i++ {
		var r ring.Ring
		_ = r.Len()
	}
}
```

Old is unpatched escape analysis with leaking `r`. New is non-leaking `r`:

```
name       old time/op    new time/op    delta
RingLen-8    35.6ns ± 6%     3.0ns ± 0%   -91.46%  (p=0.000 n=10+10)

name       old alloc/op   new alloc/op   delta
RingLen-8     32.0B ± 0%      0.0B       -100.00%  (p=0.000 n=10+10)

name       old allocs/op  new allocs/op  delta
RingLen-8      1.00 ± 0%      0.00       -100.00%  (p=0.000 n=10+10)
```

Here is `ring.Ring.Len` method implementation, for the reference:

https://golang.org/src/container/ring/ring.go?s=2869:2893#L111

<hr>

For additional examples, see proposed test suite extension:

```go
package foo

var sink interface{}

func length(xs []byte) int { // ERROR "leaking param: xs"
	sink = xs // ERROR "xs escapes to heap"
	return len(xs)
}

func zero() int { return 0 }

type buffer struct {
	arr        [64]byte
	buf1       []byte
	buf2       []byte
	bufPtr1    *[]byte
	bufPtr2    *[]byte
	bufList    [][]byte
	bufArr     [5][]byte
	bufPtrList []*[]byte
	str1       string
	str2       string
	next       *buffer
	buffers    []*buffer
}

func (b *buffer) getNext() *buffer { // ERROR "leaking param: b to result ~r0 level=1"
	return b.next
}

// When referring to the "old" implementation, cases that are covered in
// escape2.go are implied.
// Most tests here are based on those tests, but with slight changes,
// like extra selector expression level.

func (b *buffer) noEsc() { // ERROR "\(\*buffer\).noEsc b does not escape"
	// Like original slicing self-assignment test, but with additional
	// slicing expressions inside the RHS.
	b.buf1 = b.buf1[:][1:2]        // ERROR "ignoring self-assignment to b.buf1$"
	b.buf1 = b.buf1[1:][1:2:3]     // ERROR "ignoring self-assignment to b.buf1$"
	b.buf1 = b.buf2[:2][1:][1:2]   // ERROR "ignoring self-assignment to b.buf1$"
	b.buf1 = b.buf2[:][1:2][1:2:3] // ERROR "ignoring self-assignment to b.buf1$"

	// The "left" (base) part is generalized and can be arbitrary,
	// as long as it doesn't affect memory.
	// Basically, these cases add "next" in the buf accessing chain.
	b.next.buf1 = b.next.buf1[1:2]             // ERROR "ignoring self-assignment to b.next.buf1$"
	b.next.buf1 = b.next.buf1[1:2:3]           // ERROR "ignoring self-assignment to b.next.buf1$"
	b.next.buf1 = b.next.buf2[1:2]             // ERROR "ignoring self-assignment to b.next.buf1$"
	b.next.next.buf1 = b.next.next.buf2[1:2:3] // ERROR "ignoring self-assignment to b.next.next.buf1$"

	// Indexing functionally is almost identical to field accessing.
	// It's permitted to have different trailing indexes just as it's
	// permitted to have different trailing selectors.
	index1 := 10
	index2 := index1
	b.bufList[0] = b.bufList[1][1:2]             // ERROR "ignoring self-assignment to b.bufList\[0\]$"
	b.bufList[index1] = b.bufList[index2][1:2:3] // ERROR "ignoring self-assignment to b.bufList\[index1]$"
	b.bufArr[0] = b.bufArr[1+1][1:2]             // ERROR "ignoring self-assignment to b.bufArr\[0]$"
	*b.bufPtrList[2] = (*b.bufPtrList[1])[1:2:3] // ERROR "ignoring self-assignment to \*b.bufPtrList\[2\]$"
	// Same indexes should work as well.
	b.bufList[0] = b.bufList[0][1:2]             // ERROR "ignoring self-assignment to b.bufList\[0\]$"
	b.bufList[index1] = b.bufList[index1][1:2:3] // ERROR "ignoring self-assignment to b.bufList\[index1]$"
	b.bufArr[1+1] = b.bufArr[1+1][1:2]           // ERROR "ignoring self-assignment to b.bufArr\[1 \+ 1\]$"
	*b.bufPtrList[2] = (*b.bufPtrList[2])[1:2:3] // ERROR "ignoring self-assignment to \*b.bufPtrList\[2\]$"
	// Works for chained indexing as well, but indexing in base objects must match.
	b.buffers[0].bufList[0] = b.buffers[0].bufList[0][1:2]                           // ERROR "ignoring self-assignment to b.buffers\[0\].bufList\[0\]"
	b.buffers[index1+1].bufList[index1] = b.buffers[index1+1].bufList[index1][1:2:3] // ERROR "ignoring self-assignment to b.buffers\[index1\ \+ 1].bufList\[index1\]"
	b.buffers[1+1].bufArr[1+1] = b.buffers[1+1].bufArr[1+1][1:2]                     // ERROR "ignoring self-assignment to b.buffers\[1 \+ 1\].bufArr\[1 \+ 1\]"
	*b.buffers[1].bufPtrList[2] = (*b.buffers[1].bufPtrList[2])[1:2:3]               // ERROR "ignoring self-assignment to \*b.buffers\[1\].bufPtrList\[2\]"
}

func (b *buffer) esc() { // ERROR "leaking param content: b"
	// None of the cases below should trigger self-assignment optimization.

	// These slice expressions contain sub-exprs that may affect memory.
	b.buf1 = b.buf1[:length(b.buf1)][1:2]
	b.buf1 = b.buf1[1:length(b.buf1)][1:2:3]
	b.buf1 = b.buf2[:][zero():length(b.buf2)][1:2]
	b.buf1 = b.buf2[zero()+1:][:][1:2:3]

	// Due to method call inside the chain, these should not be optimized.
	// The baseObject(x) returns b.getNext() node for both sides,
	// but samesafeexpr would not consider them as "same".
	b.getNext().buf1 = b.getNext().buf1[1:2]
	b.getNext().buf1 = b.getNext().buf1[1:2:3]
	b.getNext().buf1 = b.getNext().buf2[1:2]
	b.getNext().buf1 = b.getNext().buf2[1:2:3]

	// Different base objects.
	b.next.next.buf1 = b.next.buf1[1:2]
	b.next.next.buf1 = b.next.buf1[1:2:3]
	b.next.buf1 = b.next.next.buf2[1:2]
	b.next.buf1 = b.next.next.buf2[1:2:3]
	b.bufList[0] = b.bufArr[0][1:2]

	// Different indexes are not permitted inside base objects.
	index1 := 10
	index2 := index1
	b.buffers[0].bufList[0] = b.buffers[1].bufList[0][1:2]
	b.buffers[index1].bufList[index1] = b.buffers[index2].bufList[index1][1:2:3]
	b.buffers[1+1].bufArr[1+1] = b.buffers[1+0].bufArr[1+1][1:2]
	*b.buffers[0].bufPtrList[2] = (*b.buffers[1].bufPtrList[2])[1:2:3]
	b.buffers[index1+1].bufList[index1] = b.buffers[index1+2].bufList[index1][1:2:3]
}

func (b *buffer) sanity1() { // ERROR "leaking param content: b"
	b.next.buf1 = b.next.buf2[:] // ERROR "ignoring self-assignment to b.next.buf1"
	sink = b.next.buf1           // ERROR "b.next.buf1 escapes to heap"
	sink = b.next.buf2           // ERROR "b.next.buf2 escapes to heap"
}

func (b *buffer) sanity2() { // ERROR "b does not escape"
	b.bufList = b.bufList[:len(b.bufList)-1] // ERROR "ignoring self-assignment to b.bufList"
}
```