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

Comments

@TuomLarsen
Copy link

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 label Feb 16, 2019
@seebs

This comment has been minimized.

Copy link
Contributor

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

This comment has been minimized.

Copy link
Contributor

commented Feb 17, 2019

@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

This comment has been minimized.

Copy link
Author

commented Feb 17, 2019

@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

This comment has been minimized.

Copy link
Contributor

commented Feb 17, 2019

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

This comment has been minimized.

Copy link
Author

commented Feb 17, 2019

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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
5 participants
You can’t perform that action at this time.