Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

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

Open
quasilyte opened this issue Sep 20, 2018 · 4 comments
Labels
NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. Performance
Milestone

Comments

@quasilyte
Copy link
Contributor

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 #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"
}
@quasilyte quasilyte changed the title cmd/compile/internal/gc: generalize self-assignments cmd/compile/internal/gc: generalize self-assignment handling in escape analysis Sep 20, 2018
@gopherbot
Copy link

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

@bradfitz
Copy link
Contributor

/cc @randall77 @dr2chase

@dr2chase
Copy link
Contributor

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.

@bcmills bcmills added the NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. label Sep 22, 2018
@bcmills bcmills added this to the Unplanned milestone Sep 22, 2018
@gopherbot
Copy link

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

gopherbot pushed a commit that referenced this issue Apr 17, 2019
Cherry pointed out this case in review for CL 136496. That CL was
slightly too aggressive, and I likely would have made the same mistake
if I tried it myself.

Updates #27772.

Change-Id: I1fafabb9f8d9aba0494aa71333a4e17cf1bac5c8
Reviewed-on: https://go-review.googlesource.com/c/go/+/172421
Run-TryBot: Matthew Dempsky <mdempsky@google.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Cherry Zhang <cherryyz@google.com>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. Performance
Projects
None yet
Development

No branches or pull requests

5 participants