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: 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
NeedsInvestigation Performance
Milestone

Comments

@randall77
Copy link
Contributor

@randall77 randall77 commented Jul 6, 2020

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 label Jul 7, 2020
@ericlagergren
Copy link
Contributor

@ericlagergren ericlagergren commented Jan 13, 2022

Dupe of #25086?

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
NeedsInvestigation Performance
Projects
None yet
Development

No branches or pull requests

3 participants