cmd/compile/internal/gc: generalize self-assignment handling in escape analysis

[quasilyte]

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:

x.buf = x.buf[a:b]

Later, some more patterns were added, so these are recognized, too:

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:

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":

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:

base(x[:])    => x
base(x[:][:]) => x

Given base function, we can express self-assignment as (pseudo 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):

func j(p *string) {
    *p = *p
}

More interesting examples of self-assignments that were not recognized until generalization:

type node struct { next *node }
func createLoop(n *node) {
    n.next = n // n was leaking param before
}

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

---

Collect new escape analysis results info:

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:

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:

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

---

For additional examples, see proposed test suite extension:

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"
}

[gopherbot]

Change https://golang.org/cl/136496 mentions this issue: cmd/compile/internal/gc: generalize self-assignment

[bradfitz]

/cc @randall77 @dr2chase

[dr2chase]

I'm slightly worried about the case where x is a slice or its elements are slices in

base(x[i][j]) // => x[i]

I think slice dereference counts as an indirection, where array dereference does not.

Search for IsArray in esc.go, I think you will see the distinction made. Safest route forward might be to put on all cases of indexing, see what you get with just dots, then add array (not slice!) to the base test in a separate CL in case there are subtle bugs.

ODOT is different, because I think there we rewrite to ODOTPTR when there is an explicit dereference.

[gopherbot]

Change https://golang.org/cl/172421 mentions this issue: test: add regress test cases for self-assignment