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

Jump to bottom

cmd/compile: use devirtualization in escape analysis #33160

Closed
FiloSottile opened this issue Jul 17, 2019 · 8 comments
Closed

cmd/compile: use devirtualization in escape analysis #33160

FiloSottile opened this issue Jul 17, 2019 · 8 comments
Labels
FrozenDueToAge NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. Performance
Milestone
Backlog

Comments

@FiloSottile
Copy link
Contributor

#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 the NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. label Jul 17, 2019
@FiloSottile FiloSottile added this to the Go1.14 milestone Jul 17, 2019
@randall77
Copy link
Contributor

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
Copy link
Contributor

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
Copy link
Contributor

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
Copy link
Member

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
Copy link
Member

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.

@rsc rsc modified the milestones: Go1.14, Backlog Oct 9, 2019
@randall77 randall77 mentioned this issue Feb 1, 2020
Open
@lukechampine lukechampine mentioned this issue Mar 9, 2020
Open
@gopherbot
Copy link

Change https://golang.org/cl/264837 mentions this issue: cmd/compile: early devirtualization of interface method calls

@gopherbot
Copy link

Change https://golang.org/cl/266199 mentions this issue: cmd/compile: improve inlining and static analysis

gopherbot pushed a commit that referenced this issue Oct 29, 2020
@mdempsky
cmd/compile: improve inlining and static analysis
f2c0c2b 
When inlining a function call "f()", if "f" contains exactly 1
"return" statement and doesn't name its result parameters, it's
inlined to declare+initialize the result value using the AST
representation that's compatible with staticValue.

Also, extend staticValue to skip over OCONVNOP nodes (often introduced
by inlining), and fix various bits of code related to handling method
expressions.

Updates #33160.

Change-Id: If8652e319f0a5700cf9d40a7a62e369a2a359229
Reviewed-on: https://go-review.googlesource.com/c/go/+/266199
Trust: Matthew Dempsky <mdempsky@google.com>
Run-TryBot: Matthew Dempsky <mdempsky@google.com>
TryBot-Result: Go Bot <gobot@golang.org>
Reviewed-by: David Chase <drchase@google.com>
@gopherbot
Copy link

Change https://golang.org/cl/266719 mentions this issue: cmd/compile: fix recognition of unnamed return variables

gopherbot pushed a commit that referenced this issue Nov 1, 2020
@mdempsky
cmd/compile: fix recognition of unnamed return variables
063a91c 
In golang.org/cl/266199, I reused the existing code in inlining that
recognizes anonymous variables. However, it turns out that code
mistakenly recognizes anonymous return parameters as named when
inlining a function from the same package.

The issue is funcargs (which is only used for functions parsed from
source) synthesizes ~r names for anonymous return parameters, but
funcargs2 (which is only used for functions imported from export data)
does not.

This CL fixes the behavior so that anonymous return parameters are
handled identically whether a function is inlined within the same
package or across packages. It also adds a proper cross-package test
case demonstrating #33160 is fixed in both cases.

Change-Id: Iaa39a23f5666979a1f5ca6d09fc8c398e55b784c
Reviewed-on: https://go-review.googlesource.com/c/go/+/266719
Run-TryBot: Matthew Dempsky <mdempsky@google.com>
TryBot-Result: Go Bot <gobot@golang.org>
Reviewed-by: Cuong Manh Le <cuong.manhle.vn@gmail.com>
Reviewed-by: David Chase <drchase@google.com>
Trust: Matthew Dempsky <mdempsky@google.com>
@lukechampine lukechampine mentioned this issue Aug 3, 2021
Open
@golang golang locked and limited conversation to collaborators Oct 30, 2021
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Assignees
No one assigned
Labels
FrozenDueToAge NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. Performance
Projects
None yet
Milestone
Backlog
Development

No branches or pull requests
6 participants
@mdempsky @rsc @FiloSottile @dr2chase @randall77 @gopherbot