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,runtime: compile multiway select statements as switch statements #19331

Closed
mdempsky opened this issue Feb 28, 2017 · 14 comments

Comments

Projects
None yet
10 participants
@mdempsky
Copy link
Member

commented Feb 28, 2017

Currently, code like:

select {
case c1 <- v1:      f1()
case v2 = <-c2:     f2()
case v3, ok = <-c3: f3()
default:            f4()
}

gets rewritten by cmd/compile into:

var sel struct {
	tcase, ncase               uint16
	pollorder, lockorder       *uint8
	scase                      [4]runtime.scase
	lockorderarr, pollorderarr [4]uint8
}
runtime.newselect(&sel, unsafe.Sizeof(sel), 4)
if runtime.selectsend(&sel, c1, &v1)       { f1(); goto after }
if runtime.selectrecv(&sel, c2, &v2)       { f2(); goto after }
if runtime.selectrecv2(&sel, c3, &v3, &ok) { f3(); goto after }
if runtime.selectdefault(&sel)             { f4(); goto after }
runtime.selectgo(&sel)
after:

The select{send,recv,recv2,default} functions always return false the first time they're called, but internally they save the caller's PC into &sel. runtime.selectgo never returns; instead it waits for a channel operation that can succeed, and then returns to the appropriate PC, behaving as though the function call returned twice.

(To make a C analogy, select{send,recv,recv2,default} are like setjmp, and selectgo is like longjmp.)

This proposal is to instead compile it as (something like):

var sel = struct{...}{tcase: 4, scase: [4]runtime.scase{
    {elem: &v1, chan: c1, kind: runtime.caseSend},
    {elem: &v2, chan: c2, kind: runtime.caseRecv},
    {elem: &v3, chan: c3, kind: runtime.caseRecv, receivedp: &ok},
    {kind: runtime.caseDefault},
}}
switch runtime.select(&sel) {
case 0: f1()
case 1: f2()
case 2: f3()
case 3: f4()
default: undef
}

Pros:

  1. The returns-twice and returns-never logic complicates the CFG. For example, the liveness analysis pass needs to traverse these implicit edges by recognizing runtime.selectfoo function calls. It has also caused bugs in SSA optimizations (for example https://go-review.googlesource.com/#/c/37376/).

  2. gccgo already does this according to @ianlancetaylor

  3. I wouldn't be surprised if the compiler is able to more efficiently initialize the select data structure as a straight forward composite literal, than as a bunch of runtime calls.

  4. We can eliminate a few fields. For example, hselect.ncase and scase.{pc,so}. Potentially more simplifications.

Cons:

  1. Currently switch statements are compiled into binary searches, whereas the current select implementation is able to directly jump to the appropriate destination PC. We could optimize switch statements to use jump tables though, at least for the special case of lowered select statements.

@ianlancetaylor @randall77 @rsc @aclements

@mdempsky mdempsky added the Proposal label Feb 28, 2017

@cespare

This comment has been minimized.

Copy link
Contributor

commented Feb 28, 2017

(Related switch-optimization issues are #5496 and #15780.)

@randall77

This comment has been minimized.

Copy link
Contributor

commented Feb 28, 2017

A similar return-twice pattern happens for defer. If possible we should do a similar thing for defers.

@mdempsky

This comment has been minimized.

Copy link
Member Author

commented Feb 28, 2017

@randall77 I think cleaning up deferproc is likely worth doing for similar reasons, but I think the details are distinct enough to track in a separate proposal.

@josharian

This comment has been minimized.

Copy link
Contributor

commented Mar 1, 2017

I like it. Most select cases are small (https://github.com/josharian/countselectcases/blob/master/README.md has some old data), so it'll be a linear not binary search, but I'd wager it'll be imperceptible, particularly since we're eliminating a linear number of function calls.

@aclements

This comment has been minimized.

Copy link
Member

commented Mar 1, 2017

I admit that I don't fully understand the reasons why it's done the way it is today, but I support this change, too. In addition to dramatically simplifying some very strange semantics in the runtime, this would eliminate the only use of setcallerpc in the runtime, which has been a thorn in my side before.

@ianlancetaylor

This comment has been minimized.

Copy link
Contributor

commented Mar 1, 2017

I believe it would eliminate the only use of setcallerpc anywhere.

@griesemer

This comment has been minimized.

Copy link
Contributor

commented Mar 1, 2017

I'm all for this. The suggestion approach seems much cleaner.

@bradfitz bradfitz added this to the Proposal milestone Mar 1, 2017

@mdempsky

This comment has been minimized.

Copy link
Member Author

commented Mar 1, 2017

One minor complication I discovered while prototyping this: currently we perform race instrumentation within selectgo using the caller PCs recorded by select{send,recv,default}. This shows up when case ch <- v: races with close(ch) or case v = <-ch: races with another load/store of v.

We could continue instrumenting within selectgo, but it would mean any races would point to the entire select statement, rather than the individual case.

Alternatively, we can have the compiler insert instrumentation around the selectgo call, so they can have appropriate line numbers and precise race reports. This would amount to a raceread call for each send case, and just rewriting case v = <-ch: to case vtmp := <-ch: v = vtmp (which we already do at least in some cases) so the compiler's usual instrumentation pass can handle it.

@gopherbot

This comment has been minimized.

Copy link

commented Mar 2, 2017

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

@mdempsky

This comment has been minimized.

Copy link
Member Author

commented Mar 2, 2017

CL 37661 gets rid of the setjmp/longjmp control flow, but keeps the selectfoo calls in place for the purpose of race instrumentation. Post-walk, the AST now looks like:

var sel struct { ... }
runtime.newselect(&sel, unsafe.Sizeof(sel), 4)
runtime.selectsend(&sel, c1, &v1)
runtime.selectrecv(&sel, c2, &v2, nil)
runtime.selectrecv(&sel, c3, &v3, &ok)
runtime.selectdefault(&sel)
chosen := runtime.selectgo(&sel)
if chosen == 0 { f1(); goto after }
if chosen == 1 { f2(); goto after }
if chosen == 2 { f3(); goto after }
if chosen == 3 { f4(); goto after }
undef
after:

Further simplifications are still possible.

@rsc rsc changed the title proposal: cmd/compile,runtime: compile multiway select statements as switch statements cmd/compile,runtime: compile multiway select statements as switch statements Mar 6, 2017

@rsc rsc modified the milestones: Go1.9Early, Proposal Mar 6, 2017

@rsc

This comment has been minimized.

Copy link
Contributor

commented Mar 6, 2017

If this makes things better for you, great. I can see select getting better from this. I am not as sure about being able to do the same for deferreturn. That will be harder due to stack frame layouts.

gopherbot pushed a commit that referenced this issue Mar 7, 2017

cmd/compile, runtime: simplify multiway select implementation
This commit reworks multiway select statements to use normal control
flow primitives instead of the previous setjmp/longjmp-like behavior.
This simplifies liveness analysis and should prevent issues around
"returns twice" function calls within SSA passes.

test/live.go is updated because liveness analysis's CFG is more
representative of actual control flow. The case bodies are the only
real successors of the selectgo call, but previously the selectsend,
selectrecv, etc. calls were included in the successors list too.

Updates #19331.

Change-Id: I7f879b103a4b85e62fc36a270d812f54c0aa3e83
Reviewed-on: https://go-review.googlesource.com/37661
Run-TryBot: Matthew Dempsky <mdempsky@google.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Keith Randall <khr@golang.org>
@mdempsky

This comment has been minimized.

Copy link
Member Author

commented Mar 8, 2017

Closing as the core issue (eliminating setjmp/longjmp in select) is fixed.

@mdempsky mdempsky closed this Mar 8, 2017

@rsc

This comment has been minimized.

Copy link
Contributor

commented Mar 8, 2017

It also occurs to me that deferreturn has basically none of the control flow issues that select did. In effect deferreturn just backs up the PC by 1 to cause itself to run again as a simple way to cause a loop. But to any control flow analysis of the code involved, that's indistinguishable from deferreturn containing a loop and only returning once. So it probably isn't worth changing.

@randall77

This comment has been minimized.

Copy link
Contributor

commented Mar 8, 2017

The issue with defer for me is not with deferreturn, it is with deferproc returning twice (once when first called, again when an panic occurs and that defer recovers).
It would be nice if we could arrange that defer to return directly to the deferreturn call instead of to immediately after the deferproc call. In any case, something for another issue.

@golang golang locked and limited conversation to collaborators Mar 8, 2018

Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
You can’t perform that action at this time.