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: teach prove about range of results of math/bits.*Zeros #40084

Open
randall77 opened this issue Jul 6, 2020 · 1 comment
Open

cmd/compile: teach prove about range of results of math/bits.*Zeros #40084

randall77 opened this issue Jul 6, 2020 · 1 comment
Labels
compiler/runtime Issues related to the Go compiler and/or runtime. NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. Performance
Milestone
Unplanned

Comments

@randall77
Copy link
Contributor 

package p

import "math/bits"

func f(x uint64) uint64 {
	if x != 0 {
		b := uint(bits.TrailingZeros64(x))
		x >>= b
		return x
	}
	return 0
}

Since x != 0, we know that bits.TrailingZeros64 will return a result in the range 0-63. We can use that information to remove the code that fixes up shifts that are not in range.
Right now it generates:

	0x0000 00000 (/Users/khr/gowork/tmp2.go:6)	MOVQ	"".x+8(SP), AX
	0x0005 00005 (/Users/khr/gowork/tmp2.go:6)	TESTQ	AX, AX
	0x0008 00008 (/Users/khr/gowork/tmp2.go:6)	JEQ	36
	0x000a 00010 (/Users/khr/gowork/tmp2.go:7)	BSFQ	AX, DX
	0x000e 00014 (/Users/khr/gowork/tmp2.go:8)	CMPQ	DX, $64
	0x0012 00018 (/Users/khr/gowork/tmp2.go:8)	SBBQ	BX, BX
	0x0015 00021 (/Users/khr/gowork/tmp2.go:8)	MOVQ	DX, CX
	0x0018 00024 (/Users/khr/gowork/tmp2.go:8)	SHRQ	CX, AX
	0x001b 00027 (/Users/khr/gowork/tmp2.go:8)	ANDQ	BX, AX
	0x001e 00030 (/Users/khr/gowork/tmp2.go:9)	MOVQ	AX, "".~r1+16(SP)
	0x0023 00035 (/Users/khr/gowork/tmp2.go:9)	RET
	0x0024 00036 (/Users/khr/gowork/tmp2.go:11)	MOVQ	$0, "".~r1+16(SP)
	0x002d 00045 (/Users/khr/gowork/tmp2.go:11)	RET

(And even worse without the uint cast.)

We could get rid of the CMPQ/SBBQ/ANDQ I think. Add &63 to the end of the shift line to see what it could be...

@zdjones @rasky @josharian
@randall77 randall77 added this to the Unplanned milestone Jul 6, 2020
@dmitshur dmitshur added the NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. label Jul 7, 2020
@ericlagergren
Copy link
Contributor

Dupe of #25086?

@gopherbot gopherbot added the compiler/runtime Issues related to the Go compiler and/or runtime. label Jul 13, 2022
@cuonglm cuonglm mentioned this issue Feb 5, 2023
Closed
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
compiler/runtime Issues related to the Go compiler and/or runtime. 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
4 participants
@dmitshur @ericlagergren @randall77 @gopherbot