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

cmd/compile: consider dropping Greater* and Geq* generic ops #37316

Closed
mundaym opened this issue Feb 20, 2020 · 16 comments
Closed

cmd/compile: consider dropping Greater* and Geq* generic ops #37316

mundaym opened this issue Feb 20, 2020 · 16 comments
Assignees

Comments

@mundaym
Copy link
Member

@mundaym mundaym commented Feb 20, 2020

We could, I think, fairly easily drop the following generic ops since they are trivial to implement by swapping the operands to Less* and Leq* ops (e.g. (Greater64 x y) is the same operation as (Less64 y x)):

Greater64
Greater32
Greater16
Greater8
Greater64U
Greater32U
Greater16U
Greater8U
Geq64
Geq32
Geq16
Geq8
Geq64U
Geq32U
Geq16U
Geq8U

I think this might help make CL 165998 a fair bit simpler. Of course we could also drop the Less ops instead, but Greater is more characters :).

Before I start looking into this any further, does anyone have any initial concerns or objections that come to mind?

(Note that we can probably also do the same thing with the floating point comparisons - but those aren't necessary for the CL above).

@mundaym

This comment has been minimized.

Copy link
Member Author

@mundaym mundaym commented Feb 20, 2020

@mundaym mundaym self-assigned this Feb 20, 2020
@josharian

This comment has been minimized.

Copy link
Contributor

@josharian josharian commented Feb 20, 2020

I don’t have much of an opinion about parsimony. But if we don’t want to go that route, we could also decide to canonlicalize during rewrites, the way we do with the many lsh/rsh widths.

cc @dr2chase

@dr2chase

This comment has been minimized.

Copy link
Contributor

@dr2chase dr2chase commented Feb 20, 2020

Any chance of approaching this first as a simplifying pass, to see what we gain downstream (and ensure no losses), then flush them if all goes well? Seems like this would be almost entirely a win, trying to imagine how it would not.

@mundaym

This comment has been minimized.

Copy link
Member Author

@mundaym mundaym commented Feb 20, 2020

Yeah, I've started playing around with it and it seems trivial to remove them (for the most part it is literally just deleting code and swapping arguments here and there). I'll put together a CL soon and we can use that for further discussion.

@gopherbot

This comment has been minimized.

Copy link

@gopherbot gopherbot commented Feb 20, 2020

Change https://golang.org/cl/220417 mentions this issue: cmd/compile: remove Greater* and Geq* generic integer ops

@mundaym

This comment has been minimized.

Copy link
Member Author

@mundaym mundaym commented Feb 20, 2020

The CL above implements this change. I'm fairly happy with it. It doesn't seem to affect the generated code very much and the prove pass still seems to work reliably. It ends up removing about 4000 lines of code. I still need to run the benchmarks on it but if they look OK I think we should do this.

@josharian

This comment has been minimized.

Copy link
Contributor

@josharian josharian commented Feb 20, 2020

It doesn't seem to affect the generated code very much

If you want to know more precisely, try updating to the latest compilecmp and run

compilecmp -fn=changed -cl=220417 -platforms=arch

or for just (likely) regressions:

compilecmp -fn=bigger -cl=220417 -platforms=arch

And to investigate a particular function:

compilecmp -dumpssa=FUNCNAME -cl=220417 -platforms=arch

(or whatever particular platform you want to dig into, e.g. -platforms=js/wasm.

@mundaym

This comment has been minimized.

Copy link
Member Author

@mundaym mundaym commented Feb 23, 2020

I'm still investigating but there are some interesting things going on in the compilecmp output. The negative effects I've seen so far appear to stem from the fact that the lowered CSE pass can't merge comparison instructions unless the arguments are in the same order. This appears to happen more often after the CL since we are more likely to change the argument order when emitting a comparison instruction.

Example:

CMP R0, R1
BGT x
CMP R0, R1 // can be CSE'd
BLT y
CMP R1, R0
BLT x
CMP R0, R1 // can't be CSE'd
BLT y

I don't think this should necessarily stop us - there are some functions that benefit from the reversed order and overall the effect is probably not very noticeable - but I'll see if it can be mitigated at all.

@mundaym

This comment has been minimized.

Copy link
Member Author

@mundaym mundaym commented Feb 23, 2020

One possibility is to canonicalize the order of arguments to comparisons using something like the value IDs. I'll give that a go, see how unpleasant it is.

@mundaym

This comment has been minimized.

Copy link
Member Author

@mundaym mundaym commented Feb 24, 2020

Canonicalization seems to be a reasonable solution. Though it does make the compiler output slightly less predictable. It does make some code slightly worse but only because sometimes it turns out it is better to keep the original duplicate comparisons than it is to CSE them and then let flagAlloc to regenerate them. Flags are clobbered frequently so we quite often end up regenerating them when they are CSE'd.

@gopherbot

This comment has been minimized.

Copy link

@gopherbot gopherbot commented Feb 24, 2020

Change https://golang.org/cl/220425 mentions this issue: cmd/compile: canonicalize comparison argument order

@josharian

This comment has been minimized.

Copy link
Contributor

@josharian josharian commented Feb 24, 2020

I don't think this should necessarily stop us - there are some functions that benefit from the reversed order and overall the effect is probably not very noticeable - but I'll see if it can be mitigated at all.

Yeah. I've definitely found myself chasing compilecmp regressions. On balance, I think it is a good thing, if only because I understand much better the consequences of a change, but it has definitely been a time sink.

Though it does make the compiler output slightly less predictable.

Does it also make it less stable? I.e. when you add a new unrelated optimization, does it tend to perturb the overall output more? Now that I'm investigating regressions, I'm starting to value that stability a lot. :)

Flags are clobbered frequently so we quite often end up regenerating them often when they are CSE'd.

I have run into this TODO from flagalloc a bunch of times: // TODO: Remove original instructions if they are never used. I keep hoping someone else will fix it. :)

@mundaym

This comment has been minimized.

Copy link
Member Author

@mundaym mundaym commented Feb 25, 2020

Does it also make it less stable? I.e. when you add a new unrelated optimization, does it tend to perturb the overall output more? Now that I'm investigating regressions, I'm starting to value that stability a lot. :)

I hope not. I think it will be roughly as stable as the ordering of value IDs. They aren't designed to be stable in the presence of changes so any stability we get is luck-based.

I'm tempted to rebase the integer-in-range change back onto master so that the Greater/Geq elimination changes can be more easily reverted (or just not merged) if it turns out they are more trouble than they are worth.

@josharian

This comment has been minimized.

Copy link
Contributor

@josharian josharian commented Feb 25, 2020

I’m personally ok either way. I’ll leave a final call on this to someone else.

@randall77

This comment has been minimized.

Copy link
Contributor

@randall77 randall77 commented Feb 25, 2020

I'm like both of the CLs here (getting rid of Greater, and canonicalizing comparisons). Let's do it.

I have run into this TODO from flagalloc a bunch of times: // TODO: Remove original instructions if they are never used. I keep hoping someone else will fix it. :)

Ditto.

gopherbot pushed a commit that referenced this issue Feb 26, 2020
Ensure that any comparison between two values has the same argument
order. This helps ensure that they can be eliminated during the
lowered CSE pass which will be particularly important if we eliminate
the Greater and Geq ops (see #37316).

Example:

  CMP R0, R1
  BLT L1
  CMP R1, R0 // different order, cannot eliminate
  BEQ L2

  CMP R0, R1
  BLT L1
  CMP R0, R1 // same order, can eliminate
  BEQ L2

This does have some drawbacks. Notably comparisons might 'flip'
direction in the assembly output after even small changes to the
code or compiler. It should help make optimizations more reliable
however.

compilecmp master -> HEAD
master (218f457): text/template: make reflect.Value indirections more robust
HEAD (f1661fef3e): cmd/compile: canonicalize comparison argument order
platform: linux/amd64

file      before    after     Δ       %
api       6063927   6068023   +4096   +0.068%
asm       5191757   5183565   -8192   -0.158%
cgo       4893518   4901710   +8192   +0.167%
cover     5330345   5326249   -4096   -0.077%
fix       3417778   3421874   +4096   +0.120%
pprof     14889456  14885360  -4096   -0.028%
test2json 2848138   2844042   -4096   -0.144%
trace     11746239  11733951  -12288  -0.105%
total     132739173 132722789 -16384  -0.012%

Change-Id: I11736b3fe2a4553f6fc65018f475e88217fa22f9
Reviewed-on: https://go-review.googlesource.com/c/go/+/220425
Run-TryBot: Michael Munday <mike.munday@ibm.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Keith Randall <khr@golang.org>
@gopherbot

This comment has been minimized.

Copy link

@gopherbot gopherbot commented Mar 6, 2020

Change https://golang.org/cl/222397 mentions this issue: cmd/compile: delete the floating point Greater and Geq ops

@gopherbot gopherbot closed this in bfd569f Apr 7, 2020
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Linked pull requests

Successfully merging a pull request may close this issue.

None yet
5 participants
You can’t perform that action at this time.