cmd/compile: use branchless instructions for simple conditionals

[dsnet]

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]

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

[dsnet]

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

[bradfitz]

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

[randall77]

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

[quentinmit]

Is SSA smart enough to do this yet?

[bradfitz]

Yes, in some cases.

[dsnet]

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]

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]

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]

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

Also, this is kinda a dup of #6011

[randall77]

Closing as dup of #6011.