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

runtime: simplify right shift and zero test #30272

Open
TuomLarsen opened this issue Feb 16, 2019 · 5 comments
Open

runtime: simplify right shift and zero test #30272

TuomLarsen opened this issue Feb 16, 2019 · 5 comments
Labels
compiler/runtime Issues related to the Go compiler and/or runtime. NeedsFix The path to resolution is known, but the work has not been done. Performance
Milestone

Comments

@TuomLarsen
Copy link

TuomLarsen commented Feb 16, 2019

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

1.11

What did you do?

Please consider the following dummy code:

func Dummy(x uint64) int {
    i := 0
    for {
        x >>= 1
        if x == 0 {
            break
        }
        i -= 1
    }
    return i
}

What did you expect to see?

Main part of the loop could compile down to (i.e. without the test for zero):

SHRQ $1, AX
JNE label

or even:

SHRQ AX
JNE label

What did you see instead?

It compiles down to (on x86):

SHRQ $1, AX
TESTQ AX, AX
JNE label

PS: I've just noticed similar situation occurs with - 1, instead of >> 1:

func DummySub(x int64) int {
    if x == 0 {
        x = 10
    }
    i := 0
    for {
        x -= 1
        if x == 0 {
            break
        }
        i += 1
    }
    return i
}

There the:

DECQ AX
CMPQ AX, $1
JNE label

could also be replaced by:

SUBQ AX, $1 // or DECQ AX
JE label
@randall77 randall77 added this to the Unplanned milestone Feb 16, 2019
@mvdan mvdan added the NeedsFix The path to resolution is known, but the work has not been done. label Feb 16, 2019
@seebs
Copy link
Contributor

seebs commented Feb 16, 2019

not that this matters at all, but:

func Dummy2(x uint64) int {
	if x == 0 {
		return 0
	}
	return bits.LeadingZeros64(x) - 63
}

(or 1 - bits.Len64(x).)

I don't know whether it's intentional that both 0 and 1 inputs yield 0. It's irrelevant to the optimization opportunity, though.

@andybons andybons changed the title Simplification of right shift and zero test runtime: simplify right shift and zero test Feb 17, 2019
@josharian
Copy link
Contributor

@TuomLarsen w.r.t. to SHRQ AX vs SHRQ $1, AX, they both encode to the same instruction. Am I missing something, or did you have in mind just the difference in the presentation?

@TuomLarsen
Copy link
Author

@josharian SHRQ AX is encoded as 48d1e8 (the 1 implicit), whereas SHRQ $1, AX can also be encoded as 48c1e801. I'm not sure which one Go uses, that's why I commented on both.

@josharian
Copy link
Contributor

Ah, I mistranslated the assembly when checking on the encoding and used the wrong width register. Sigh.

We should start generating the shorter version. I’m AFK—would you mind opening a new issue for this so that it can be tracked separately from re-using the flags result of the shift? Thanks. It’d actually make a decent starter issue for someone who wanted to contribute to SSA world, since we also make last minute encoding decisions in a similar way e.g. to use MOVL instead of MOVQ for small constants. cc @martisch

@TuomLarsen
Copy link
Author

I've just checked and it seems that Go is indeed generating the shorter (implicit 1) version for the shift so I guess there is no need to open a separate issue. The disassembler says SHRQ $0x1, AX but the content of memory is 48d1e8.

@gopherbot gopherbot added the compiler/runtime Issues related to the Go compiler and/or runtime. label Jul 7, 2022
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
compiler/runtime Issues related to the Go compiler and/or runtime. NeedsFix The path to resolution is known, but the work has not been done. Performance
Projects
None yet
Development

No branches or pull requests

6 participants