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.

Sign up for GitHub

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: use branchless instructions for simple conditionals #11813

Closed
dsnet opened this issue Jul 22, 2015 · 11 comments
Closed

cmd/compile: use branchless instructions for simple conditionals #11813

dsnet opened this issue Jul 22, 2015 · 11 comments
Labels
FrozenDueToAge NeedsFix The path to resolution is known, but the work has not been done. Performance
Milestone
Go1.8

Comments

@dsnet
Copy link
Member

dsnet commented Jul 22, 2015

When I compile the following:

func sign(b bool) int {
    // Equivalent to: return 2*btoi(b)-1
    if b {
        return +1
    }
    return -1
}

func btoi(b bool) int {
    if b {
        return 1
    }
    return 0
}

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

func abs(a int) int {
    if a < 0 {
        return -a
    }
    return a
}

I notice the following output:

"".sign t=1 size=32 value=0 args=0x10 locals=0x0
    0x0000 00000 (/home/rawr/main7.go:3)    TEXT    "".sign(SB), $0-16
    0x0000 00000 (/home/rawr/main7.go:3)    NOP
    0x0000 00000 (/home/rawr/main7.go:3)    NOP
    0x0000 00000 (/home/rawr/main7.go:3)    FUNCDATA    $0, gclocals·23e8278e2b69a3a75fa59b23c49ed6ad(SB)
    0x0000 00000 (/home/rawr/main7.go:3)    FUNCDATA    $1, gclocals·33cdeccccebe80329f1fdbee7f5874cb(SB)
    0x0000 00000 (/home/rawr/main7.go:4)    CMPB    "".b+8(FP), $0
    0x0005 00005 (/home/rawr/main7.go:4)    JEQ 17
    0x0007 00007 (/home/rawr/main7.go:5)    MOVQ    $1, "".~r1+16(FP)
    0x0010 00016 (/home/rawr/main7.go:5)    RET
    0x0011 00017 (/home/rawr/main7.go:7)    MOVQ    $-1, "".~r1+16(FP)
    0x001a 00026 (/home/rawr/main7.go:7)    RET
    0x0000 80 7c 24 08 00 74 0a 48 c7 44 24 10 01 00 00 00  .|$..t.H.D$.....
    0x0010 c3 48 c7 44 24 10 ff ff ff ff c3                 .H.D$......
"".btoi t=1 size=32 value=0 args=0x10 locals=0x0
    0x0000 00000 (/home/rawr/main7.go:10)   TEXT    "".btoi(SB), $0-16
    0x0000 00000 (/home/rawr/main7.go:10)   NOP
    0x0000 00000 (/home/rawr/main7.go:10)   NOP
    0x0000 00000 (/home/rawr/main7.go:10)   FUNCDATA    $0, gclocals·23e8278e2b69a3a75fa59b23c49ed6ad(SB)
    0x0000 00000 (/home/rawr/main7.go:10)   FUNCDATA    $1, gclocals·33cdeccccebe80329f1fdbee7f5874cb(SB)
    0x0000 00000 (/home/rawr/main7.go:11)   CMPB    "".b+8(FP), $0
    0x0005 00005 (/home/rawr/main7.go:11)   JEQ 17
    0x0007 00007 (/home/rawr/main7.go:12)   MOVQ    $1, "".~r1+16(FP)
    0x0010 00016 (/home/rawr/main7.go:12)   RET
    0x0011 00017 (/home/rawr/main7.go:14)   MOVQ    $0, "".~r1+16(FP)
    0x001a 00026 (/home/rawr/main7.go:14)   RET
    0x0000 80 7c 24 08 00 74 0a 48 c7 44 24 10 01 00 00 00  .|$..t.H.D$.....
    0x0010 c3 48 c7 44 24 10 00 00 00 00 c3                 .H.D$......
"".min t=1 size=32 value=0 args=0x18 locals=0x0
    0x0000 00000 (/home/rawr/main7.go:17)   TEXT    "".min(SB), $0-24
    0x0000 00000 (/home/rawr/main7.go:17)   NOP
    0x0000 00000 (/home/rawr/main7.go:17)   NOP
    0x0000 00000 (/home/rawr/main7.go:17)   MOVQ    "".a+8(FP), CX
    0x0005 00005 (/home/rawr/main7.go:17)   MOVQ    "".b+16(FP), AX
    0x000a 00010 (/home/rawr/main7.go:17)   FUNCDATA    $0, gclocals·790e5cc5051fc0affc980ade09e929ec(SB)
    0x000a 00010 (/home/rawr/main7.go:17)   FUNCDATA    $1, gclocals·33cdeccccebe80329f1fdbee7f5874cb(SB)
    0x000a 00010 (/home/rawr/main7.go:18)   CMPQ    CX, AX
    0x000d 00013 (/home/rawr/main7.go:18)   JGE 21
    0x000f 00015 (/home/rawr/main7.go:19)   MOVQ    CX, "".~r2+24(FP)
    0x0014 00020 (/home/rawr/main7.go:19)   RET
    0x0015 00021 (/home/rawr/main7.go:21)   MOVQ    AX, "".~r2+24(FP)
    0x001a 00026 (/home/rawr/main7.go:21)   RET
    0x0000 48 8b 4c 24 08 48 8b 44 24 10 48 39 c1 7d 06 48  H.L$.H.D$.H9.}.H
    0x0010 89 4c 24 18 c3 48 89 44 24 18 c3                 .L$..H.D$..
"".abs t=1 size=32 value=0 args=0x10 locals=0x0
    0x0000 00000 (/home/rawr/main7.go:24)   TEXT    "".abs(SB), $0-16
    0x0000 00000 (/home/rawr/main7.go:24)   NOP
    0x0000 00000 (/home/rawr/main7.go:24)   NOP
    0x0000 00000 (/home/rawr/main7.go:24)   MOVQ    "".a+8(FP), AX
    0x0005 00005 (/home/rawr/main7.go:24)   FUNCDATA    $0, gclocals·23e8278e2b69a3a75fa59b23c49ed6ad(SB)
    0x0005 00005 (/home/rawr/main7.go:24)   FUNCDATA    $1, gclocals·33cdeccccebe80329f1fdbee7f5874cb(SB)
    0x0005 00005 (/home/rawr/main7.go:25)   CMPQ    AX, $0
    0x0009 00009 (/home/rawr/main7.go:25)   JGE 23
    0x000b 00011 (/home/rawr/main7.go:26)   MOVQ    AX, BX
    0x000e 00014 (/home/rawr/main7.go:26)   NEGQ    BX
    0x0011 00017 (/home/rawr/main7.go:26)   MOVQ    BX, "".~r1+16(FP)
    0x0016 00022 (/home/rawr/main7.go:26)   RET
    0x0017 00023 (/home/rawr/main7.go:28)   MOVQ    AX, "".~r1+16(FP)
    0x001c 00028 (/home/rawr/main7.go:28)   RET

The compiled program uses the JGE and JEQ instruction to branch when it is possible to compile the above functions without branches.

This optimization is useful in situations where the conditional is not easily predictable, leading to poor branch predictor performance.

I'm using Go1.5beta2
@bradfitz
Copy link
Contributor

You didn't state the compiler version. I recall work on this happening in Go 1.5.

@dsnet
Copy link
Member Author

dsnet commented Jul 22, 2015

Just tried it on Go1.5beta2, and it still produces that output.

@bradfitz bradfitz added this to the Go1.6 milestone Jul 22, 2015
@bradfitz
Copy link
Contributor

/cc @randall77 @josharian @tzneal for SSA stuff.

@randall77
Copy link
Contributor

This optimization probably won't happen in the first release of SSA, but it is on the radar.

@rsc rsc modified the milestones: dev.ssa, Go1.6 Nov 4, 2015
@bradfitz bradfitz modified the milestones: dev.ssa, Go1.7 Mar 2, 2016
@rsc rsc changed the title cmd/compile: Use branchless instructions for simple conditionals cmd/compile: use branchless instructions for simple conditionals May 17, 2016
@rsc rsc modified the milestones: Go1.8, Go1.7 May 17, 2016
@quentinmit quentinmit added the NeedsFix The path to resolution is known, but the work has not been done. label Oct 11, 2016
@quentinmit
Copy link
Contributor

Is SSA smart enough to do this yet?

@bradfitz
Copy link
Contributor

Yes, in some cases.

@dsnet
Copy link
Member Author

dsnet commented Oct 11, 2016

I've seen some rewrite added to handle specific cases, but as of 3a90728, all of the examples I listed still include a branch.

@randall77
Copy link
Contributor

Most cases like this are not handled yet. Here's one which is:

func b2i(b bool) int {
    r := 0
    if b {
        r = 1
    }
    return r
}

@dsnet
Copy link
Member Author

dsnet commented Oct 11, 2016

It seems finicky. That example is logically identical to my btoi function above:

func btoi(b bool) int {
    if b {
        return 1
    }
    return 0
}

Yet my version doesn't benefit from the optimization :(

@bradfitz
Copy link
Contributor

@dsnet, known. See https://golang.org/cl/22711 and a25a7ad which uses it.

Also, this is kinda a dup of #6011

@randall77
Copy link
Contributor

Closing as dup of #6011.

@golang golang locked and limited conversation to collaborators Oct 17, 2017
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Assignees
No one assigned
Labels
FrozenDueToAge NeedsFix The path to resolution is known, but the work has not been done. Performance
Projects
None yet
Milestone
Go1.8
Development

No branches or pull requests
6 participants
@bradfitz @rsc @quentinmit @dsnet @randall77 @gopherbot