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: boolean operations not constant folded #32713

Closed
marigonzes opened this issue Jun 20, 2019 · 8 comments
Closed

cmd/compile: boolean operations not constant folded #32713

marigonzes opened this issue Jun 20, 2019 · 8 comments
Labels

Comments

@marigonzes
Copy link

@marigonzes marigonzes commented Jun 20, 2019

What version of Go are you using (go version)?

$ go version
go version devel +c82e7e7 Tue Jun 18 22:21:45 2019 +0000 linux/amd64

Does this issue reproduce with the latest release?

Yes.

What did you do?

I inspected the assembly code generated for the following functions:

func f1(b bool) bool {
    return b && !b
}
func f2(b bool) bool {
    return b || !b
}

What did you expect to see?

I expected them to be compiled to a simple return: false in the first case, true in the second.

What did you see instead?

Instead, boolean operations are performed on the variable b.

@martisch

This comment has been minimized.

Copy link
Member

@martisch martisch commented Jun 21, 2019

Where those examples constructed or found in real code? Im not sure how often they would trigger.

What is the scope of the feature request:

  1. to support these specific cases or
  2. be able to prove all tautologies and contradictions in boolean expressions (e.g. pierce law ((P→Q)→P)→P written as: !(!(!p || q) || p) || p)?

Im asking because if its the former we want to collect cases that are easy to detect and happen frequently and if its the later whether Go gc needs to contain a full propositional prover (e.g. SAT solver) applied to boolean expressions that also keeps side effects if any. The later might be too complex and takes to much compile time vs the gain achieved on real code.

Looking at gcc C++ it seems to detect p || !p but e.g. not p || !q || !p.

Constant folding (the above dont contain constants) in Go gc should generally work e.g.:
p || true is compiled to true.

Interestingly gcc Go seems to not completely optimize p || true: https://godbolt.org/z/peYHWU
cc @cherrymui

@marigonzes

This comment has been minimized.

Copy link
Author

@marigonzes marigonzes commented Jun 21, 2019

I found these examples out of curiosity, because I wanted to know how the Go compile would behave, but I imagine code like this being auto-generated.
I posted this issue just to know if anyone was thinking about this.
But if code like this doesn't appear in the wild, I think we should close it.

@cherrymui

This comment has been minimized.

Copy link
Contributor

@cherrymui cherrymui commented Jun 21, 2019

Interestingly gcc Go seems to not completely optimize p || true: https://godbolt.org/z/peYHWU

You need to specify optimization level. The default is -O0, which does not optimize. -O1 and above do.

@cherrymui

This comment has been minimized.

Copy link
Contributor

@cherrymui cherrymui commented Jun 21, 2019

As @martisch mentioned, b || !b is not constant folding, as the input is not constant. It is true that for all possible input, the expression is false, but normal constant folding wouldn't do that. If this doesn't come up in real code, I agree that it is not worth the extra complexity.

@martisch

This comment has been minimized.

Copy link
Member

@martisch martisch commented Jun 21, 2019

You need to specify optimization level. The default is -O0, which does not optimize. -O1 and above do.

Oops. Thanks for the correction. I was distracted from adding flags by GCC C++ seemingly optimizing this even without any additional flags in godbolt: https://godbolt.org/z/SMYxsz

@marigonzes

This comment has been minimized.

Copy link
Author

@marigonzes marigonzes commented Jun 21, 2019

Personally, I've never seen code like this. I was just curious about the output of the compiler, given this two functions.
Leaving the decision to you 😉

@katiehockman

This comment has been minimized.

Copy link
Member

@katiehockman katiehockman commented Jun 21, 2019

Since this seems like an edge case that won't appear in the wild or cause people any issues, it sounds like we should close this. @martisch can you confirm/close this if so?

@martisch

This comment has been minimized.

Copy link
Member

@martisch martisch commented Jun 25, 2019

TL;DR I think we should wait to see an actual use case where this would help and then implement some optimizations for propositional tautologies/contradicions preferably in the compiler backend.

This might very well come up after some optimizations triggered in the compiler backend but then detecting tautologies/contradictions in the frontend for simple cases like shown wont help. To not solve the made up cases and not detect the actual cases where this triggers I would think we should wait for code in the wild to show up that could use this. If somebody has an example that can not be just simplified by code review without compromising readability I think we can close this.

Linters and static code checks meanwhile can detect simple cases such as b || q || !b and suggest simplification.

@marigonzes thank you for the report. Filing reports of optimization opportunities especially if you can find existing code that can benefit from them is much appreciated.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
4 participants
You can’t perform that action at this time.