Repository navigation
cmd/compile: use devirtualization in escape analysis #33160
Description
#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
Reacted by Michael Munday, Carlo Alberto Ferraris, Justin Nuß, thepudds, Joe Tsai, Ahmed W., Aliaksandr Valialkin, George Moschovitis, Luke Champine, Whyrusleeping and 10 more
Activity
randall77 commentedon 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
[-]cmd/compile: devirtualize more calls when concrete type is known[/-][+]cmd/compile: use devirtualization in escape analysis[/+]dr2chase commentedon 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 commentedon Jul 18, 2019
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.Newwill be inlined. (It would be really nice ifsha256.Newreturned a concrete type instead of an interface type. Too late now.)mdempsky commentedon 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 commentedon 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.
gopherbot commentedon Oct 24, 2020
Change https://golang.org/cl/264837 mentions this issue:
cmd/compile: early devirtualization of interface method callsgopherbot commentedon Oct 29, 2020
Change https://golang.org/cl/266199 mentions this issue:
cmd/compile: improve inlining and static analysiscmd/compile: improve inlining and static analysis
gopherbot commentedon Oct 30, 2020
Change https://golang.org/cl/266719 mentions this issue:
cmd/compile: fix recognition of unnamed return variablescmd/compile: fix recognition of unnamed return variables