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: No BCE for x&(len(p)-1) #57243

Closed
greatroar opened this issue Dec 11, 2022 · 3 comments
Closed

cmd/compile: No BCE for x&(len(p)-1) #57243

greatroar opened this issue Dec 11, 2022 · 3 comments
Labels
compiler/runtime Issues related to the Go compiler and/or runtime. FrozenDueToAge NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. Performance
Milestone
Unplanned

Comments

@greatroar
Copy link

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

$ go version
go version go1.19 linux/amd64
$ gotip version
go version devel go1.20-9b8750f53e Sat Dec 10 00:35:24 2022 +0000 linux/amd64

What did you do?

Distilled from a custom hash table:

package ht

func get(p []string, h uint) string {
	if len(p) == 0 {
		return ""
	}
	i := h & uint(len(p)-1)
	return p[i]
}

What did you expect to see?

BCE for the expression p[i]. From the if statement, the compiler knows that len(p) > 0, so len(p)-1 is non-negative and in bounds, and so is h&(len(p)-1).

What did you see instead?

./bce.go:8:10: Found IsInBounds

It doesn't seem to matter if I put the cast on h or change the length check to <=0.
@gopherbot gopherbot added the compiler/runtime Issues related to the Go compiler and/or runtime. label Dec 11, 2022
@randall77 randall77 added this to the Unplanned milestone Dec 11, 2022
@RuinanSun
Copy link
Contributor

I would like to have a try on this. Maybe need a little bit changes on CL 419555

@thanm thanm added the NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. label Dec 12, 2022
@Jorropo
Copy link
Member

Jorropo commented Dec 27, 2022

Just so you know, this is harder than it looks currently the facts table is filled in by OpCode specific knowlege first, then CFG is explored.

prove currently know how to handle everything in this example except the OpSub64 value.
It is rarely true that the result of a subtraction is always smaller or equal than the first input (it only happen if you prove that the second operand is always smaller or equal than the first one in the first place, such as in this case).

There are many ways you could solve this, I'm just saying this isn't a trivial thing like it might look like.

@gopherbot
Copy link

Change https://go.dev/cl/419555 mentions this issue: cmd/compile: get more bounds info from logic operators in prove pass

@golang golang locked and limited conversation to collaborators Apr 6, 2024
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Assignees
No one assigned
Labels
compiler/runtime Issues related to the Go compiler and/or runtime. 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
Unplanned
Development

No branches or pull requests
6 participants
@randall77 @gopherbot @thanm @Jorropo @greatroar @RuinanSun