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

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

Open
josharian opened this Issue Apr 8, 2015 · 6 comments

Comments

Projects
None yet
6 participants
@josharian
Contributor

josharian commented Apr 8, 2015

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

@josharian josharian added the repo-main label Apr 8, 2015

@minux

This comment has been minimized.

Member

minux commented Apr 8, 2015

@josharian josharian changed the title from cmd/{5,7}g: use conditional execution in place of branches for small blocks to cmd/5g: use conditional execution in place of branches for small blocks Apr 8, 2015

@ianlancetaylor

This comment has been minimized.

Contributor

ianlancetaylor commented Apr 8, 2015

Do we generate conditional move instructions on i386/amd64?

@minux

This comment has been minimized.

Member

minux commented Apr 8, 2015

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

This comment has been minimized.

Member

4ad commented Apr 8, 2015

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

@davecheney

This comment has been minimized.

Contributor

davecheney commented Apr 8, 2015

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
#10382 (comment).

@josharian

This comment has been minimized.

Contributor

josharian commented Apr 8, 2015

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.

@rsc rsc added this to the Unplanned milestone Apr 10, 2015

@rsc rsc removed the repo-main label Apr 14, 2015

@rsc rsc changed the title from cmd/5g: use conditional execution in place of branches for small blocks to cmd/compile: use conditional execution in place of branches for small blocks on arm Jun 8, 2015

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment