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: use devirtualization in escape analysis #33160

Open
FiloSottile opened this issue Jul 17, 2019 · 5 comments

Comments

@FiloSottile
Copy link
Member

commented Jul 17, 2019

#19361 introduced devirtualization when the concrete type is known statically. This would be extremely useful to compensate for the unfortunate design of the hash.Hash functions, which make it impossible not to make the input escape.

However, it looks like it doesn't figure out the sha256.New return value, even if that function gets inlined.

package sha256 // import "crypto/sha256"

func New() hash.Hash
    New returns a new hash.Hash computing the SHA256 checksum. The Hash also
    implements encoding.BinaryMarshaler and encoding.BinaryUnmarshaler to
    marshal and unmarshal the internal state of the hash.
type Hash interface {
        io.Writer

        Sum(b []byte) []byte
        Reset()
        Size() int
        BlockSize() int
}
package main

import "crypto/sha256"

func main() {
	s := make([]byte, 128)
	h := sha256.New()
	h.Write(s)
	h.Sum(nil)
}
$ gotip version
go version devel +5bc46cb7 Wed Jul 17 17:34:32 2019 +0000 darwin/amd64
$ gotip build -gcflags -m=2 .
# x
./x.go:5:6: cannot inline main: function too complex: cost 204 exceeds budget 80
./x.go:7:17: inlining call to sha256.New func() hash.Hash { var sha256.d·2 *sha256.digest; sha256.d·2 = <N>; sha256.d·2 = new(sha256.digest); sha256.d·2.Reset(); return hash.Hash(sha256.d·2) }
./x.go:6:11: make([]byte, 128) escapes to heap
./x.go:7:17: new(sha256.digest) escapes to heap
./x.go:7:17: hash.Hash(sha256.d·2) escapes to heap

If there is some tweak that can be made in the sha256 package to make this work, I'm happy to make this change, otherwise it would be nice to extend the optimization.

/cc @randall77

@FiloSottile FiloSottile added this to the Go1.14 milestone Jul 17, 2019

@randall77

This comment has been minimized.

Copy link
Contributor

commented Jul 18, 2019

It looks like the compiler does devirtualize all the calls in this function.

The problem I think is that the devirtualization happens late in compilation, particularly after escape analysis. So even though the calls are devirtualized, during escape analysis they are still interface calls and cause their arguments to escape. We need earlier devirtualization to catch this. It shouldn't be hard, as inlining has already happened, so we just need some intraprocedural devirtualization as part of escape analysis. Maybe?
@mdempsky @dr2chase

@FiloSottile FiloSottile changed the title cmd/compile: devirtualize more calls when concrete type is known cmd/compile: use devirtualization in escape analysis Jul 18, 2019

@dr2chase

This comment has been minimized.

Copy link
Contributor

commented Jul 18, 2019

I guess the question is do we just leave escape analysis in the front end and add this other analysis there as well? It would be a lot of work to move escape analysis into (a variant of) SSA, but that might be profitable.

@randall77

This comment has been minimized.

Copy link
Contributor

commented Jul 18, 2019

I guess the question is do we just leave escape analysis in the front end and add this other analysis there as well? It would be a lot of work to move escape analysis into (a variant of) SSA, but that might be profitable.

Yes, I think so. Phase ordering is kind of a fundamental problem in a compiler, this is just one instance of it. We're not going to solve phase ordering generally. But we can do some simple things in escape analysis to catch common cases like this issue.

As well as this issue, inlining itself could use devirtualization. Right now none of the method calls on the result of sha256.New will be inlined. (It would be really nice if sha256.New returned a concrete type instead of an interface type. Too late now.)

@mdempsky

This comment has been minimized.

Copy link
Member

commented Jul 18, 2019

A type tightening pass in the frontend seems reasonable to me. I'm assuming we just look for local, non-addrtaken variables of interface type, that are always assigned an OCONVIFACE expressions that were converted from the same concrete type. We can then change the local variable's type, eliminate those OCONVIFACEs, and add new ones as necessary to preserve type correctness.

I agree that pushing this forward into inlining probably makes more sense than integrating it into escape analysis though.

@mdempsky

This comment has been minimized.

Copy link
Member

commented Jul 19, 2019

After playing with this a little, I realized this can't be done in the naive control/data-flow-insensitive way I suggested. Since interface-typed variables are always initialized to nil, there's at least always one assignment that's not to a concrete type.

Maybe there's a slightly more sophisticated solution that (1) works well in practice, but (2) doesn't require a complete SSA analysis or equivalent reimplemented in the frontend.

I think I'm leaning towards just continuing to move the frontend's post-typecheck code from Node to SSA; and once escape analysis is done on SSA, it should be easy to implement early de-virtualization.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
4 participants
You can’t perform that action at this time.