cmd/compile: lay out loop-free, likeliness-free control flow more compactly

[josharian]

package p

func f() int {
	x := 0
	for i := 0; i < 10; i++ {
		odd := 0
		if i%2 == 0 {
			odd = 2 // not 1, otherwise this branch gets optimized away!
		}
		x += odd
		// Distract the layout pass with a bunch of loops.
		for j := 0; j < 10; j++ {
			for j := 0; j < 10; j++ {
				for j := 0; j < 10; j++ {
					x++
				}
			}
		}
	}
	return x
}

In this code, we have even odds of the if i%2 == 0 branch being taken. But the code layout is pretty uneven. In this CFG, b3 is that branch, and b6 and b19 are the taken/not-taken blocks; both feed into b7. It seems like a good layout for this would be b3 b6 b19 b7 or b3 b19 b6 b7. But we put b19 at the very end of the function.

This is a simplified version of something that also happens in the fannkuch benchmark. See also #20355 and #18977.

For details on how to read this image, see #20355.

cc @randall77 @dr2chase @cherrymui

Marking 1.9Maybe because we removed the old backend's instruction re-ordering pass during 1.9; this may help prevent regressions from that.

[josharian]

Seems like the layout pass would benefit from being made generally loop-aware.

[cherrymui]

Does it improve performance by laying b6 and b19 together?

Does the old follow pass put them together? Maybe I should investigate this.

What tool did you use to generate the graphs? I have done this a few times with pen and paper. A tool seems very helpful.

[gopherbot]

CL https://golang.org/cl/43464 mentions this issue.

[josharian]

Does it improve performance by laying b6 and b19 together?

I think it will, in larger functions. There are trade-offs--number of jumps, fwd vs backward, code compactness, jump encoding, etc. I need to experiment, although there are enough other layout-related things in flight (CL 43293, issue #20355), that I'd like to wait a little bit. Just filing this so I don't forget and to gather input from experienced hands.

Does the old follow pass put them together? Maybe I should investigate this.

I don't know. I'd be curious to find out.

What tool did you use to generate the graphs? I have done this a few times with pen and paper. A tool seems very helpful.

I used CL 43464, which gopherbot has helpfully linked to. It has major problems, though. Maybe I'll email golang-dev to get opinions and solicit help on it...

[dr2chase]

@laboger had mentioned that our likeliness/layout was not all that they had hoped.

One possibility I had intended to try was to introduce at least one more level of (un)likeliness, for things like branches to panics where we are "really sure" about likeliness, versus all the cases where we're making less-educated guesses. As a general rule we expect p(loopbackedge) > p(return) > p(panic).

[josharian]

Note to self: Interesting test cases for this are moderate-complexity autogenerated SSA rule functions, like rewriteValuedec_OpStore_0.

[josharian]

One possibility I had intended to try was to introduce at least one more level of (un)likeliness, for things like branches to panics where we are "really sure" about likeliness, versus all the cases where we're making less-educated guesses. As a general rule we expect p(loopbackedge) > p(return) > p(panic).

See CL 43293 for branches to panics; could be improved, but it is a simple and fairly effective first cut. And see the first (somewhat awful) patchset of that CL for what adding new likeliness levels looks like.

And yes, I think spending some time in 1.10 on likeliness and code layout is worthwhile.

[josharian]

Another observation for 1.10 use. It appears that a lot of the non-compactness I observed here may simply be due to the fact that posdegree (and zerodegree) are effectively stacks instead of queues. Though that may become irrelevant if lay out code based primarily on loop nesting information.

[gopherbot]

CL https://golang.org/cl/43501 mentions this issue.

[josharian]

I think CL 43491 (and possibly @dr2chase's follow-up) is enough to address the 1.9 regression. Punting this to 1.10.