runtime: eliminate scase.kind field
Currently, we include a "kind" field on scase to distinguish the three
kinds of cases in a select statement: sends, receives, and defaults.
This commit removes by kind field by instead arranging for the
compiler to always place sends before receives, and to provide their
counts separately. It also passes an explicit "block bool" parameter
to avoid needing to include a default case in the array.
It's safe to shuffle cases like this because the runtime will
randomize the order they're polled in anyway.
Fixes #40410.
Change-Id: Iaeaed4cf7bddd576d78f2c863bd91a03a5c82df2
Reviewed-on: https://go-review.googlesource.com/c/go/+/245125
Reviewed-by: Keith Randall <khr@golang.org>
diff --git a/src/cmd/compile/internal/gc/builtin.go b/src/cmd/compile/internal/gc/builtin.go
index eafdb0e..861ffaa 100644
--- a/src/cmd/compile/internal/gc/builtin.go
+++ b/src/cmd/compile/internal/gc/builtin.go
@@ -302,7 +302,7 @@
typs[96] = types.NewPtr(typs[6])
typs[97] = functype(nil, []*Node{anonfield(typs[3]), anonfield(typs[96]), anonfield(typs[84])}, []*Node{anonfield(typs[6])})
typs[98] = functype(nil, []*Node{anonfield(typs[63])}, nil)
- typs[99] = functype(nil, []*Node{anonfield(typs[1]), anonfield(typs[1]), anonfield(typs[63]), anonfield(typs[15])}, []*Node{anonfield(typs[15]), anonfield(typs[6])})
+ typs[99] = functype(nil, []*Node{anonfield(typs[1]), anonfield(typs[1]), anonfield(typs[63]), anonfield(typs[15]), anonfield(typs[15]), anonfield(typs[6])}, []*Node{anonfield(typs[15]), anonfield(typs[6])})
typs[100] = functype(nil, []*Node{anonfield(typs[1]), anonfield(typs[15]), anonfield(typs[15])}, []*Node{anonfield(typs[7])})
typs[101] = functype(nil, []*Node{anonfield(typs[1]), anonfield(typs[22]), anonfield(typs[22])}, []*Node{anonfield(typs[7])})
typs[102] = functype(nil, []*Node{anonfield(typs[1]), anonfield(typs[15]), anonfield(typs[15]), anonfield(typs[7])}, []*Node{anonfield(typs[7])})
diff --git a/src/cmd/compile/internal/gc/builtin/runtime.go b/src/cmd/compile/internal/gc/builtin/runtime.go
index 25f86ef..635da80 100644
--- a/src/cmd/compile/internal/gc/builtin/runtime.go
+++ b/src/cmd/compile/internal/gc/builtin/runtime.go
@@ -170,7 +170,7 @@
func selectnbrecv2(elem *any, received *bool, hchan <-chan any) bool
func selectsetpc(pc *uintptr)
-func selectgo(cas0 *byte, order0 *byte, pc0 *uintptr, ncases int) (int, bool)
+func selectgo(cas0 *byte, order0 *byte, pc0 *uintptr, nsends int, nrecvs int, block bool) (int, bool)
func block()
func makeslice(typ *byte, len int, cap int) unsafe.Pointer
diff --git a/src/cmd/compile/internal/gc/select.go b/src/cmd/compile/internal/gc/select.go
index 8eb31eb..bae7ed3 100644
--- a/src/cmd/compile/internal/gc/select.go
+++ b/src/cmd/compile/internal/gc/select.go
@@ -106,18 +106,16 @@
}
func walkselectcases(cases *Nodes) []*Node {
- n := cases.Len()
+ ncas := cases.Len()
sellineno := lineno
// optimization: zero-case select
- if n == 0 {
+ if ncas == 0 {
return []*Node{mkcall("block", nil, nil)}
}
// optimization: one-case select: single op.
- // TODO(rsc): Reenable optimization once order.go can handle it.
- // golang.org/issue/7672.
- if n == 1 {
+ if ncas == 1 {
cas := cases.First()
setlineno(cas)
l := cas.Ninit.Slice()
@@ -178,10 +176,12 @@
// convert case value arguments to addresses.
// this rewrite is used by both the general code and the next optimization.
+ var dflt *Node
for _, cas := range cases.Slice() {
setlineno(cas)
n := cas.Left
if n == nil {
+ dflt = cas
continue
}
switch n.Op {
@@ -202,15 +202,10 @@
}
// optimization: two-case select but one is default: single non-blocking op.
- if n == 2 && (cases.First().Left == nil || cases.Second().Left == nil) {
- var cas *Node
- var dflt *Node
- if cases.First().Left == nil {
+ if ncas == 2 && dflt != nil {
+ cas := cases.First()
+ if cas == dflt {
cas = cases.Second()
- dflt = cases.First()
- } else {
- dflt = cases.Second()
- cas = cases.First()
}
n := cas.Left
@@ -257,74 +252,73 @@
return []*Node{r, nod(OBREAK, nil, nil)}
}
+ if dflt != nil {
+ ncas--
+ }
+ casorder := make([]*Node, ncas)
+ nsends, nrecvs := 0, 0
+
var init []*Node
// generate sel-struct
lineno = sellineno
- selv := temp(types.NewArray(scasetype(), int64(n)))
+ selv := temp(types.NewArray(scasetype(), int64(ncas)))
r := nod(OAS, selv, nil)
r = typecheck(r, ctxStmt)
init = append(init, r)
- order := temp(types.NewArray(types.Types[TUINT16], 2*int64(n)))
+ order := temp(types.NewArray(types.Types[TUINT16], 2*int64(ncas)))
r = nod(OAS, order, nil)
r = typecheck(r, ctxStmt)
init = append(init, r)
var pc0, pcs *Node
if flag_race {
- pcs = temp(types.NewArray(types.Types[TUINTPTR], int64(n)))
+ pcs = temp(types.NewArray(types.Types[TUINTPTR], int64(ncas)))
pc0 = typecheck(nod(OADDR, nod(OINDEX, pcs, nodintconst(0)), nil), ctxExpr)
} else {
pc0 = nodnil()
}
// register cases
- for i, cas := range cases.Slice() {
+ for _, cas := range cases.Slice() {
setlineno(cas)
init = append(init, cas.Ninit.Slice()...)
cas.Ninit.Set(nil)
- // Keep in sync with runtime/select.go.
- const (
- caseNil = iota
- caseRecv
- caseSend
- caseDefault
- )
-
- var c, elem *Node
- var kind int64 = caseDefault
-
- if n := cas.Left; n != nil {
- init = append(init, n.Ninit.Slice()...)
-
- switch n.Op {
- default:
- Fatalf("select %v", n.Op)
- case OSEND:
- kind = caseSend
- c = n.Left
- elem = n.Right
- case OSELRECV, OSELRECV2:
- kind = caseRecv
- c = n.Right.Left
- elem = n.Left
- }
+ n := cas.Left
+ if n == nil { // default:
+ continue
}
+ var i int
+ var c, elem *Node
+ switch n.Op {
+ default:
+ Fatalf("select %v", n.Op)
+ case OSEND:
+ i = nsends
+ nsends++
+ c = n.Left
+ elem = n.Right
+ case OSELRECV, OSELRECV2:
+ nrecvs++
+ i = ncas - nrecvs
+ c = n.Right.Left
+ elem = n.Left
+ }
+
+ casorder[i] = cas
+
setField := func(f string, val *Node) {
r := nod(OAS, nodSym(ODOT, nod(OINDEX, selv, nodintconst(int64(i))), lookup(f)), val)
r = typecheck(r, ctxStmt)
init = append(init, r)
}
- setField("kind", nodintconst(kind))
- if c != nil {
- c = convnop(c, types.Types[TUNSAFEPTR])
- setField("c", c)
- }
+ c = convnop(c, types.Types[TUNSAFEPTR])
+ setField("c", c)
if elem != nil {
elem = convnop(elem, types.Types[TUNSAFEPTR])
setField("elem", elem)
@@ -337,6 +331,9 @@
init = append(init, r)
}
}
+ if nsends+nrecvs != ncas {
+ Fatalf("walkselectcases: miscount: %v + %v != %v", nsends, nrecvs, ncas)
+ }
// run the select
lineno = sellineno
@@ -345,7 +342,7 @@
r = nod(OAS2, nil, nil)
r.List.Set2(chosen, recvOK)
fn := syslook("selectgo")
- r.Rlist.Set1(mkcall1(fn, fn.Type.Results(), nil, bytePtrToIndex(selv, 0), bytePtrToIndex(order, 0), pc0, nodintconst(int64(n))))
+ r.Rlist.Set1(mkcall1(fn, fn.Type.Results(), nil, bytePtrToIndex(selv, 0), bytePtrToIndex(order, 0), pc0, nodintconst(int64(nsends)), nodintconst(int64(nrecvs)), nodbool(dflt == nil)))
r = typecheck(r, ctxStmt)
init = append(init, r)
@@ -357,14 +354,11 @@
}
// dispatch cases
- for i, cas := range cases.Slice() {
- setlineno(cas)
-
- cond := nod(OEQ, chosen, nodintconst(int64(i)))
+ dispatch := func(cond, cas *Node) {
cond = typecheck(cond, ctxExpr)
cond = defaultlit(cond, nil)
- r = nod(OIF, cond, nil)
+ r := nod(OIF, cond, nil)
if n := cas.Left; n != nil && n.Op == OSELRECV2 {
x := nod(OAS, n.List.First(), recvOK)
@@ -377,6 +371,15 @@
init = append(init, r)
}
+ if dflt != nil {
+ setlineno(dflt)
+ dispatch(nod(OLT, chosen, nodintconst(0)), dflt)
+ }
+ for i, cas := range casorder {
+ setlineno(cas)
+ dispatch(nod(OEQ, chosen, nodintconst(int64(i))), cas)
+ }
+
return init
}
@@ -395,7 +398,6 @@
scase = tostruct([]*Node{
namedfield("c", types.Types[TUNSAFEPTR]),
namedfield("elem", types.Types[TUNSAFEPTR]),
- namedfield("kind", types.Types[TUINT16]),
})
scase.SetNoalg(true)
}
diff --git a/src/reflect/all_test.go b/src/reflect/all_test.go
index ed2f225..5a12699 100644
--- a/src/reflect/all_test.go
+++ b/src/reflect/all_test.go
@@ -1725,6 +1725,14 @@
_, _, _ = Select(sCases)
}
+func TestSelectNop(t *testing.T) {
+ // "select { default: }" should always return the default case.
+ chosen, _, _ := Select([]SelectCase{{Dir: SelectDefault}})
+ if chosen != 0 {
+ t.Fatalf("expected Select to return 0, but got %#v", chosen)
+ }
+}
+
func BenchmarkSelect(b *testing.B) {
channel := make(chan int)
close(channel)
diff --git a/src/runtime/select.go b/src/runtime/select.go
index d7c7d9f..80768b2 100644
--- a/src/runtime/select.go
+++ b/src/runtime/select.go
@@ -12,23 +12,12 @@
const debugSelect = false
-// scase.kind values.
-// Known to compiler.
-// Changes here must also be made in src/cmd/compile/internal/gc/select.go's walkselectcases.
-const (
- caseNil = iota
- caseRecv
- caseSend
- caseDefault
-)
-
// Select case descriptor.
// Known to compiler.
// Changes here must also be made in src/cmd/internal/gc/select.go's scasetype.
type scase struct {
c *hchan // chan
elem unsafe.Pointer // data element
- kind uint16
}
var (
@@ -115,7 +104,7 @@
// ordinal position of its respective select{recv,send,default} call.
// Also, if the chosen scase was a receive operation, it reports whether
// a value was received.
-func selectgo(cas0 *scase, order0 *uint16, pc0 *uintptr, ncases int) (int, bool) {
+func selectgo(cas0 *scase, order0 *uint16, pc0 *uintptr, nsends, nrecvs int, block bool) (int, bool) {
if debugSelect {
print("select: cas0=", cas0, "\n")
}
@@ -125,6 +114,7 @@
cas1 := (*[1 << 16]scase)(unsafe.Pointer(cas0))
order1 := (*[1 << 17]uint16)(unsafe.Pointer(order0))
+ ncases := nsends + nrecvs
scases := cas1[:ncases:ncases]
pollorder := order1[:ncases:ncases]
lockorder := order1[ncases:][:ncases:ncases]
@@ -158,16 +148,12 @@
// optimizing (and needing to test).
// generate permuted order
- dfli := -1
norder := 0
for i := range scases {
cas := &scases[i]
// Omit cases without channels from the poll and lock orders.
if cas.c == nil {
- if cas.kind == caseDefault {
- dfli = i
- }
cas.elem = nil // allow GC
continue
}
@@ -250,8 +236,7 @@
cas = &scases[casi]
c = cas.c
- switch cas.kind {
- case caseRecv:
+ if casi >= nsends {
sg = c.sendq.dequeue()
if sg != nil {
goto recv
@@ -262,8 +247,7 @@
if c.closed != 0 {
goto rclose
}
-
- case caseSend:
+ } else {
if raceenabled {
racereadpc(c.raceaddr(), casePC(casi), chansendpc)
}
@@ -280,9 +264,9 @@
}
}
- if dfli >= 0 {
+ if !block {
selunlock(scases, lockorder)
- casi = dfli
+ casi = -1
goto retc
}
@@ -311,12 +295,10 @@
*nextp = sg
nextp = &sg.waitlink
- switch cas.kind {
- case caseRecv:
- c.recvq.enqueue(sg)
-
- case caseSend:
+ if casi < nsends {
c.sendq.enqueue(sg)
+ } else {
+ c.recvq.enqueue(sg)
}
}
@@ -359,7 +341,7 @@
}
} else {
c = k.c
- if k.kind == caseSend {
+ if int(casei) < nsends {
c.sendq.dequeueSudoG(sglist)
} else {
c.recvq.dequeueSudoG(sglist)
@@ -378,27 +360,29 @@
c = cas.c
if debugSelect {
- print("wait-return: cas0=", cas0, " c=", c, " cas=", cas, " kind=", cas.kind, "\n")
+ print("wait-return: cas0=", cas0, " c=", c, " cas=", cas, " send=", casi < nsends, "\n")
}
- if cas.kind == caseRecv {
+ if casi < nsends {
+ if !caseSuccess {
+ goto sclose
+ }
+ } else {
recvOK = caseSuccess
- } else if cas.kind == caseSend && !caseSuccess {
- goto sclose
}
if raceenabled {
- if cas.kind == caseRecv && cas.elem != nil {
- raceWriteObjectPC(c.elemtype, cas.elem, casePC(casi), chanrecvpc)
- } else if cas.kind == caseSend {
+ if casi < nsends {
raceReadObjectPC(c.elemtype, cas.elem, casePC(casi), chansendpc)
+ } else if cas.elem != nil {
+ raceWriteObjectPC(c.elemtype, cas.elem, casePC(casi), chanrecvpc)
}
}
if msanenabled {
- if cas.kind == caseRecv && cas.elem != nil {
- msanwrite(cas.elem, c.elemtype.size)
- } else if cas.kind == caseSend {
+ if casi < nsends {
msanread(cas.elem, c.elemtype.size)
+ } else if cas.elem != nil {
+ msanwrite(cas.elem, c.elemtype.size)
}
}
@@ -526,29 +510,57 @@
block()
}
sel := make([]scase, len(cases))
- order := make([]uint16, 2*len(cases))
- for i := range cases {
- rc := &cases[i]
+ orig := make([]int, len(cases))
+ nsends, nrecvs := 0, 0
+ dflt := -1
+ for i, rc := range cases {
+ var j int
switch rc.dir {
case selectDefault:
- sel[i] = scase{kind: caseDefault}
+ dflt = i
+ continue
case selectSend:
- sel[i] = scase{kind: caseSend, c: rc.ch, elem: rc.val}
+ j = nsends
+ nsends++
case selectRecv:
- sel[i] = scase{kind: caseRecv, c: rc.ch, elem: rc.val}
+ nrecvs++
+ j = len(cases) - nrecvs
}
+
+ sel[j] = scase{c: rc.ch, elem: rc.val}
+ orig[j] = i
}
+ // Only a default case.
+ if nsends+nrecvs == 0 {
+ return dflt, false
+ }
+
+ // Compact sel and orig if necessary.
+ if nsends+nrecvs < len(cases) {
+ copy(sel[nsends:], sel[len(cases)-nrecvs:])
+ copy(orig[nsends:], orig[len(cases)-nrecvs:])
+ }
+
+ order := make([]uint16, 2*(nsends+nrecvs))
var pc0 *uintptr
if raceenabled {
- pcs := make([]uintptr, len(cases))
+ pcs := make([]uintptr, nsends+nrecvs)
for i := range pcs {
selectsetpc(&pcs[i])
}
pc0 = &pcs[0]
}
- return selectgo(&sel[0], &order[0], pc0, len(cases))
+ chosen, recvOK := selectgo(&sel[0], &order[0], pc0, nsends, nrecvs, dflt == -1)
+
+ // Translate chosen back to caller's ordering.
+ if chosen < 0 {
+ chosen = dflt
+ } else {
+ chosen = orig[chosen]
+ }
+ return chosen, recvOK
}
func (q *waitq) dequeueSudoG(sgp *sudog) {
