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: In bits.Len(x|1), compiler doesn't realize argument is never zero #51964

Closed
greatroar opened this issue Mar 26, 2022 · 3 comments
Closed

cmd/compile: In bits.Len(x|1), compiler doesn't realize argument is never zero #51964

greatroar opened this issue Mar 26, 2022 · 3 comments
Labels
FrozenDueToAge

Comments

@greatroar
Copy link

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

$ go version
go version go1.18 linux/amd64
$ gotip version
go version devel go1.19-ab0f7611d73 Mon Mar 14 09:19:01 2022 +0000 linux/amd64

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

GOARCH=amd64
GOAMD64=v2

What did you do?

func len1(x uint64) int { return bits.Len64(x | 1) }

The expression bits.Len64(x|1) occurs in output from a protobuf compiler, where it calculates the size of a varint.

What did you expect to see?

ORQ	$1, AX
BSRQ	AX, AX
INCQ	AX
RET

What did you see instead?

ORQ	$1, AX
BSRQ	AX, CX
MOVQ	$-1, DX
CMOVQEQ	DX, CX
LEAQ    1(CX), AX
RET

It looks like this could be solved by extending the following rule to handle BSRQ:

go/src/cmd/compile/internal/ssa/gen/AMD64.rules

Lines 2075 to 2076 in 0652274

// We don't need the conditional move if we know the arg of BSF is not zero.
(CMOVQEQ x _ (Select1 (BSFQ (ORQconst [c] _)))) && c != 0 => x

@gopherbot
Copy link

Change https://go.dev/cl/396034 mentions this issue: cmd/compile: optimize BSRQ with nonzero input

@gopherbot
Copy link

Change https://go.dev/cl/396035 mentions this issue: cmd/compile: better propagation of desired registers

@renthraysk
Copy link

bits.Len32() still outputs unnecessary code for nonzero arguments. As it does x := uint64(arg)*2 + 1 to ensure a nonzero argument for BSFQ rather than use a conditional move after.

gopherbot pushed a commit that referenced this issue Mar 31, 2022
@randall77
cmd/compile: better propagation of desired registers
bdd0f0f 
This fixes two independent problems:

We normally propagate desired registers backwards through opcodes that
are marked resultInArg0. Unfortunately for the desired register
computation, ADDQconst is not marked as resultInArg0. This is because
the amd64 backend can write it out as LEAQ instead if the input and
output registers don't match. For desired register purposes, we want
to treat ADDQconst as resultInArg0, so that we get an ADDQ instead of
a LEAQ if we can.

Desired registers don't currently work for tuple-generating opcodes.
Declare that the desired register applies to the first element of the
tuple, and propagate the desired register back through Select0.

Noticed when fixing #51964

Change-Id: I83346b988882cd58c2d7e7e5b419a2b9a244ab66
Reviewed-on: https://go-review.googlesource.com/c/go/+/396035
Trust: Keith Randall <khr@golang.org>
Run-TryBot: Keith Randall <khr@golang.org>
Reviewed-by: David Chase <drchase@google.com>
TryBot-Result: Gopher Robot <gobot@golang.org>
@golang golang locked and limited conversation to collaborators Mar 27, 2023
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Assignees
No one assigned
Labels
FrozenDueToAge
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
3 participants
@gopherbot @renthraysk @greatroar