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: detect and apply more CMOV optimizations #27780

Open
agnivade opened this issue Sep 20, 2018 · 1 comment
Open

cmd/compile: detect and apply more CMOV optimizations #27780

agnivade opened this issue Sep 20, 2018 · 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

@agnivade
Copy link
Contributor

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

go version go1.11 linux/amd64

Does this issue reproduce with the latest release?

Yes. And checked with master as of (go version devel +7f3de1f275 Thu Sep 20 14:44:04 2018 +0530 linux/amd64)

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

GOARCH="amd64"
GOBIN=""
GOCACHE="/home/agniva/.cache/go-build"
GOEXE=""
GOFLAGS=""
GOHOSTARCH="amd64"
GOHOSTOS="linux"
GOOS="linux"
GOPATH="/home/agniva/play/go"
GOPROXY=""
GORACE=""
GOROOT="/usr/local/go"
GOTMPDIR=""
GOTOOLDIR="/usr/local/go/pkg/tool/linux_amd64"
GCCGO="gccgo"
CC="gcc"
CXX="g++"
CGO_ENABLED="1"
GOMOD=""
CGO_CFLAGS="-g -O2"
CGO_CPPFLAGS=""
CGO_CXXFLAGS="-g -O2"
CGO_FFLAGS="-g -O2"
CGO_LDFLAGS="-g -O2"
PKG_CONFIG="pkg-config"
GOGCCFLAGS="-fPIC -m64 -pthread -fmessage-length=0 -fdebug-prefix-map=/tmp/go-build407760751=/tmp/go-build -gno-record-gcc-switches"

What did you do?

Consider this code -

package main

func min2(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func min3(a, b, c int) int {
	if a < b {
		if a < c {
			return a
		}
	} else if b < c {
		return b
	}
	return c
}

var a, b, c int
var d int

func main() {
	d = min2(min2(a, b), c)
	d = min3(a, b, c)
}

What did you expect to see?

Here, both functions are trying to get the min of 3 integers, albeit in slightly different manners. First one performs min of 2 integers twice, second one performs them in a single function. One would think that the compiler would be smart enough so that the generated code would be equivalent. Or atleast, not be 14% faster than the other.

What did you see instead?

But on investigating the assembly, we see interesting results

1st one
 0x0000 00000 (funcreg.go:34)    MOVQ    "".c(SB), AX
        0x0007 00007 (funcreg.go:34)    MOVQ    "".a(SB), CX
        0x000e 00014 (funcreg.go:34)    MOVQ    "".b(SB), DX
        0x0015 00021 (funcreg.go:34)    CMPQ    CX, DX
        0x0018 00024 (funcreg.go:34)    CMOVQLT CX, DX
        0x001c 00028 (funcreg.go:34)    CMPQ    DX, AX
        0x001f 00031 (funcreg.go:34)    CMOVQLT DX, AX
        0x0023 00035 (funcreg.go:34)    MOVQ    AX, "".d(SB)

2nd one
        0x002a 00042 (funcreg.go:35)    MOVQ    "".c(SB), AX
        0x0031 00049 (funcreg.go:35)    MOVQ    "".a(SB), CX
        0x0038 00056 (funcreg.go:35)    MOVQ    "".b(SB), DX
        0x003f 00063 (funcreg.go:35)    CMPQ    CX, DX
        0x0042 00066 (funcreg.go:34)    JGE     86
        0x0044 00068 (funcreg.go:35)    CMPQ    CX, AX
        0x0047 00071 (funcreg.go:35)    JGE     81
        0x0049 00073 (funcreg.go:35)    MOVQ    CX, "".d(SB)
        0x0050 00080 (funcreg.go:36)    RET
        0x0051 00081 (funcreg.go:35)    MOVQ    AX, CX
        0x0054 00084 (funcreg.go:35)    JMP     73
        0x0056 00086 (funcreg.go:35)    CMPQ    DX, AX
        0x0059 00089 (funcreg.go:35)    JGE     81
        0x005b 00091 (funcreg.go:35)    MOVQ    DX, CX
        0x005e 00094 (funcreg.go:35)    JMP     73

Notice that there is no CMOV generated in the 2nd case.

Only if we change the min3 code to behave like min2 like this -

func min3(a, b, c int) int {
	min := b
	if a < b {
		min = a
	}
	if c < min {
		min = c
	}
	return min
}

then we get CMOV generated. But this is only after I realized how the compiler is converting the code to explicitly generate the CMOV instruction.

Originally discussed in a golang-dev thread here - https://groups.google.com/forum/#!topic/golang-dev/JaYi4D-tsbY.

/cc @randall77 @rasky
@agnivade agnivade added Performance NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. labels Sep 20, 2018
@agnivade agnivade added this to the Unplanned milestone Sep 20, 2018
@randall77 randall77 mentioned this issue Aug 26, 2021
Open
@thepudds
Copy link
Contributor

In-lining a comment from @philhofer from the golang-dev thread:

Author of the original branchelim code here.

The reason the example with returns doesn't get optimized is because the compiler doesn't do return block unification.

Keith wrote a patch once to implement it, but it was never merged.

The optimization has no trouble rewriting that function once it is inlined because the target of the 'return' branch
is simply another basic block in the function. (In some sense, inlining has to implement return block unification.)

(At least, I think that was from @philhofer).

@gopherbot gopherbot added the compiler/runtime Issues related to the Go compiler and/or runtime. label Jul 13, 2022
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
3 participants
@agnivade @gopherbot @thepudds