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: use conditional execution in place of branches for small blocks on arm #10382

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

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

josharian opened this issue Apr 8, 2015 · 6 comments
Milestone
Unplanned

Comments

@josharian
Copy link
Contributor

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
Copy link
Member

minux commented Apr 8, 2015 via email

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

Do we generate conditional move instructions on i386/amd64?

@minux
Copy link
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
Copy link
Member

4ad commented Apr 8, 2015

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

@davecheney
Copy link
Contributor

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
Copy link
Contributor Author

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 cmd/5g: use conditional execution in place of branches for small blocks 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
Assignees
No one assigned
Labels
None yet
Projects
None yet
Milestone
Unplanned
Development

No branches or pull requests
6 participants
@davecheney @josharian @rsc @minux @4ad @ianlancetaylor