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: elide branches that must be taken #17862

Open
dsnet opened this Issue Nov 9, 2016 · 4 comments

Comments

Projects
None yet
7 participants
@dsnet
Member

dsnet commented Nov 9, 2016

Consider the following two benchmarks:

var sink int
var A, B, C = 1, 2, 3

func BenchmarkA(b *testing.B) {
	for i := 0; i < b.N; i++ {
		var m int
		if A != 0 && B+1 <= C {
			m = 0
		} else {
			panic("never called")
		}
		sink = m
	}
}

func BenchmarkB(b *testing.B) {
	for i := 0; i < b.N; i++ {
		var m int
		if A != 0 && B+1 <= C {
			m = 0
		} else {
			m = -1
		}
		if m == -1 {
			panic("never called")
		}
		sink = m
	}
}

On Go 1.8, version A is 25% slower faster than version B. The reason for this is because the compiler actually sets m = -1 and then does the subsequent conditional check m == -1. The compiler should be able to prove that this unnecessary.

Code that looks like this commonly occurs when a smaller inlineable helper is used for a quick path and then a conditional is used to check for a fallback. For example:

m := tryMethod()
if m != -1 {
	m = slowMethod()
}

This came up in http://golang.org/cl/32921.

/cc @bradfitz @randall77

@dsnet dsnet added the Performance label Nov 9, 2016

@ianlancetaylor

This comment has been minimized.

Contributor

ianlancetaylor commented Nov 9, 2016

Did you mean to say that version A is 25% faster? Because otherwise I don't understand.

The traditional compiler optimization to fix this is Value Range Propagation.

@josharian

This comment has been minimized.

Contributor

josharian commented Nov 9, 2016

@josharian josharian added this to the Go1.9 milestone Nov 9, 2016

@randall77 randall77 modified the milestones: Go1.10, Go1.9 May 31, 2017

@bradfitz bradfitz modified the milestones: Go1.10, Go1.11 Nov 28, 2017

@bradfitz bradfitz modified the milestones: Go1.11, Unplanned May 18, 2018

@aclements

This comment has been minimized.

Member

aclements commented May 18, 2018

@dsnet, I'm not sure I understand the issue here. Since A, B, and C are variables, some code outside of the benchmarks could modify these, and then the benchmark functions would have to take the panic branch. We can't statically eliminate that. If A, B, and C are consts, then the compiler will recognize that it can statically prove the panic branch condition and will eliminate the panic branch in both benchmarks.

Perhaps you're suggesting that the compiler should recognize that it can lift the panic if up into both predecessor blocks and then optimize it differently in each predecessor?

@dr2chase

This comment has been minimized.

Contributor

dr2chase commented May 19, 2018

@aclements The issue is that m is local, so it's not being modified elsewhere. One way to look at this is that conditional A is followed by conditional B, and both arms of A determine subsequent execution of B. B could be "inlined" (as a continuation, exactly that) into the two arms of A and then simplified.

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