cmd/compile: use conditional execution in place of branches for small blocks on arm

[josharian]

For example, consider max:

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

This compiles roughly to:

MOVW    "".a(FP), R3
MOVW    "".b+4(FP), R2
CMP R2, R3
BLE a
MOVW    R3, "".~r2+8(FP)
RET
a:
MOVW    R2, "".~r2+8(FP)
RET

But it could be:

MOVW    "".a(FP), R3
MOVW    "".b+4(FP), R2
CMP R2, R3
MOVW.LE R2, "".~r2+8(FP)
RET.LE
MOVW    R3, "".~r2+8(FP)
RET

The general guidance from ARM is that it is worth branching instead of using conditional instructions when you reach 4-6 conditional instructions.

It's unclear to me when this should be done:

• during codegen (would require significant state to be passed around)
• as a peephole optimization
• at instruction selection time (since it already moves branch sequences around)
• as part of the 1.6 SSA effort (probably the best option)

Not urgent.

/cc @davecheney @4ad @minux

[minux]

This is only applicable to 5g. arm64 doesn't have conditionally executed instructions except conditional branches.

On arm64, we need to use CSEL and others (C(S)INC, C(S)INV, etc).

[ianlancetaylor]

Do we generate conditional move instructions on i386/amd64?

[minux]

As far as I know, gc don't generate conditional move (or conditonal arithmetic) instructions for any of the supported architectures directly (in cmd/5g, there is a predicate pass that try to convert branches to conditionally executed instructions, but that pass is not enabled yet [@josharian, if you want to work on this issue, please take a look at the predicate function in cmd/5g/peep.go; we might be able to port that to 8g/6g to make use of cmovcc]).

I think josh has a change to make bgen use setcc on amd64.

I imagine it will be easier to use condition move instructions in the new SSA-based backend with graph matching based instruction selection.

[4ad]

Note that on arm64 we get a 68kB reduction in godoc, which is significant.

[davecheney]

I watched Aram write a bunch of peephole rules this afternoon, each totalling 60-70kb reduction in godoc, given we're removing one 32 bit instruction per rule, that tells you how common these patterns that the peep optimiser is targeting are.

On Thu, Apr 9, 2015 at 7:03 AM, Aram Hăvărneanu notifications@github.com wrote:

Note that on arm64 we get a 68kB reduction in godoc, which is significant.

— Reply to this email directly or view it on GitHub https://github.com/golang/go/issues/10382#issuecomment-91036842.

[josharian]

Do we generate conditional move instructions on i386/amd64?

No, although as @minux said, we will hopefully soon generate SETcc. I'm working on reviving that CL now.

Also, ARM can attach conditions to most instructions, not just MOVs. CMOV also has the pitfall that it unconditionally loads the source from memory; it is only the resulting store than is conditional. These are probably good reasons to make this happen after the initial codegen.

if you want to work on this issue, please take a look at the predicate function in cmd/5g/peep.go; we might be able to port that to 8g/6g to make use of cmovcc

Thanks! I'll take a look, although if this will all be eclipsed by SSA in 1.6, it might not be worth the effort and risk right now. (I'm worried about the same issue w.r.t. to the SETcc work, but I've already done a lot of the work, so I'll see it through.)

totalling 60-70kb reduction in godoc, given we're removing one 32 bit instruction per rule

Pretty awesome.