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: escape analysis reports that make() is using a non-constant size after inlining with a constant size #47524

Open
renthraysk opened this issue Aug 3, 2021 · 5 comments

Comments

@renthraysk
Copy link

@renthraysk renthraysk commented Aug 3, 2021

What version of Go are you using (go version)?

$ go version
go version go1.16.6 linux/amd64

Does this issue reproduce with the latest release?

What operating system and processor architecture are you using (go env)?

go env Output
$ go env

What did you do?

package main

// translate translates any byte in s between (lower, upper) to (newLower, newLower + upper - lower)
func translate(s string, cap int, lower, upper, newLower byte) string {
	// code removed
	b := append(make([]byte, 0, cap), s...)
	// code removed
	return string(b)
}

// toLower returns s with all upper case characters replaced with their lower case counterparts.
func toLower(s string, cap int) string {
	return translate(s, cap, 'A', 'Z', 'a')
}

// lookup ASCII case insensitive map lookup.
func lookup(m map[string]string, key string) (string, bool) {
	if len(key) > 32 {
		return "", false
	}
	r, ok := m[toLower(key, 32)]
	return r, ok
}

What did you expect to see?

translate() inlines into toLower() and resulting toLower() will also inline into it's caller. So in lookup() when toLower() is inlined would expect the capacity of slice created in translate() to be constant and therefore able to be reserved on the stack.

What did you see instead?

make([]byte, 0, cap) escapes to heap (non-constant size), when it is inlined into lookup().
If use a fixed capacity like make([]byte, 0, 32) in translate() the slice is always reserved on the stack.

@randall77
Copy link
Contributor

@randall77 randall77 commented Aug 3, 2021

I think this is just a limitation of the constant propagation in escape analysis. Inlining introduces temporaries and we don't propagate through those temporaries.

@randall77 randall77 added this to the Unplanned milestone Aug 3, 2021
@zpavlinovic
Copy link
Contributor

@zpavlinovic zpavlinovic commented Aug 4, 2021

Just out of curiosity, why is propagation of constants not happening in such cases?

@randall77
Copy link
Contributor

@randall77 randall77 commented Aug 4, 2021

No one has implemented it.
It's a bit tricky in that phase of the compiler because you have to prove that a variable never changes value. That involves looking for other assignments to that variable, including through pointers.

@zpavlinovic
Copy link
Contributor

@zpavlinovic zpavlinovic commented Aug 4, 2021

My understanding might be a bit off, but the constant propagation should take care of this. That is, it should not touch pointers or anything like that. It should do its job in propagating 32 to cap after inlining. Of course, if all of the temporaries are implemented as pointers, then I can see the issue.

@renthraysk
Copy link
Author

@renthraysk renthraysk commented Aug 5, 2021

In a perfect implementation, the cap parameter wouldn't be required.

As after len() check in lookup() the compiler should know the possible range of len(key) is (0, 32). Then rather than need to use an explicit fixed capacity, could use make([]byte, 0, len(s)) and compiler determines that the upper limit is small enough to always be stack allocated.

Using bounds checking elimination to move smaller non escaping allocations to the stack.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Linked pull requests

Successfully merging a pull request may close this issue.

None yet
4 participants