This patch to the Go frontend and libgo eliminates the scase.kind field, saving some space on the stack when running a select statement. Instead of using a kind, the compiler now sorts all the send cases before the receive cases, and gives the default case a special index of -1. This is in preparation for updating to the Go 1.16beta1 release. Bootstrapped and ran Go testsuite on x86_64-pc-linux-gnu. Committed to mainline.
Ian
ff3028b66d567b9afdcc9a5d12719e84e8516397 diff --git a/gcc/go/gofrontend/MERGE b/gcc/go/gofrontend/MERGE index bb537f152b9..c70b60c657f 100644 --- a/gcc/go/gofrontend/MERGE +++ b/gcc/go/gofrontend/MERGE @@ -1,4 +1,4 @@ -eca96e39cb895805b617e0e1f184f893ed3e46bb +d091cd25a5894ac751fe1868197648fc486cf322 The first line of this file holds the git revision number of the last merge done from the gofrontend repository. diff --git a/gcc/go/gofrontend/runtime.def b/gcc/go/gofrontend/runtime.def index 4b606a6c00c..7ab94a3ffbc 100644 --- a/gcc/go/gofrontend/runtime.def +++ b/gcc/go/gofrontend/runtime.def @@ -195,8 +195,8 @@ DEF_GO_RUNTIME(CHANRECV2, "runtime.chanrecv2", P2(CHAN, POINTER), R1(BOOL)) // Run a select, returning the index of the selected clause and // whether that channel received a value. -DEF_GO_RUNTIME(SELECTGO, "runtime.selectgo", P3(POINTER, POINTER, INT), - R2(INT, BOOL)) +DEF_GO_RUNTIME(SELECTGO, "runtime.selectgo", + P5(POINTER, POINTER, INT, INT, BOOL), R2(INT, BOOL)) // Non-blocking send a value on a channel, used for two-case select // statement with a default case. diff --git a/gcc/go/gofrontend/statements.cc b/gcc/go/gofrontend/statements.cc index 398b8fd82f2..da0e0843a73 100644 --- a/gcc/go/gofrontend/statements.cc +++ b/gcc/go/gofrontend/statements.cc @@ -5291,22 +5291,23 @@ Select_clauses::Select_clause::traverse(Traverse* traverse) void Select_clauses::Select_clause::lower(Gogo* gogo, Named_object* function, Block* b, Temporary_statement* scases, - size_t index, Temporary_statement* recvok) + int index, Temporary_statement* recvok) { Location loc = this->location_; - Expression* scase = Expression::make_temporary_reference(scases, loc); - Expression* index_expr = Expression::make_integer_ul(index, NULL, loc); - scase = Expression::make_array_index(scase, index_expr, NULL, NULL, loc); + this->set_case_index(index); if (this->is_default_) { go_assert(this->channel_ == NULL && this->val_ == NULL); - this->lower_default(b, scase); this->is_lowered_ = true; return; } + Expression* scase = Expression::make_temporary_reference(scases, loc); + Expression* index_expr = Expression::make_integer_sl(index, NULL, loc); + scase = Expression::make_array_index(scase, index_expr, NULL, NULL, loc); + // Evaluate the channel before the select statement. Temporary_statement* channel_temp = Statement::make_temporary(NULL, this->channel_, @@ -5326,15 +5327,6 @@ Select_clauses::Select_clause::lower(Gogo* gogo, Named_object* function, this->val_ = NULL; } -// Lower a default clause in a select statement. - -void -Select_clauses::Select_clause::lower_default(Block* b, Expression* scase) -{ - Location loc = this->location_; - this->set_case(b, scase, Expression::make_nil(loc), NULL, caseDefault); -} - // Lower a send clause in a select statement. void @@ -5366,7 +5358,7 @@ Select_clauses::Select_clause::lower_send(Block* b, Expression* scase, Type* unsafe_pointer_type = Type::make_pointer_type(Type::make_void_type()); valaddr = Expression::make_cast(unsafe_pointer_type, valaddr, loc); - this->set_case(b, scase, chanref, valaddr, caseSend); + this->set_case(b, scase, chanref, valaddr); } // Lower a receive clause in a select statement. @@ -5392,7 +5384,7 @@ Select_clauses::Select_clause::lower_recv(Gogo* gogo, Named_object* function, Type* unsafe_pointer_type = Type::make_pointer_type(Type::make_void_type()); valaddr = Expression::make_cast(unsafe_pointer_type, valaddr, loc); - this->set_case(b, scase, chanref, valaddr, caseRecv); + this->set_case(b, scase, chanref, valaddr); // If the block of statements is executed, arrange for the received // value to move from VAL to the place where the statements expect @@ -5447,8 +5439,7 @@ void Select_clauses::Select_clause::set_case(Block* b, Expression* scase, Expression* chanref, - Expression* elem, - int kind) + Expression* elem) { Location loc = this->location_; Struct_type* scase_type = scase->type()->struct_type(); @@ -5469,14 +5460,6 @@ Select_clauses::Select_clause::set_case(Block* b, s = Statement::make_assignment(ref, elem, loc); b->add_statement(s); } - - field_index = 2; - go_assert(scase_type->field(field_index)->is_field_name("kind")); - Type* uint16_type = Type::lookup_integer_type("uint16"); - Expression* k = Expression::make_integer_ul(kind, uint16_type, loc); - ref = Expression::make_field_reference(scase->copy(), field_index, loc); - s = Statement::make_assignment(ref, k, loc); - b->add_statement(s); } // Determine types. @@ -5577,6 +5560,19 @@ Select_clauses::Select_clause::dump_clause( // Class Select_clauses. +// Whether there is a default case. + +bool +Select_clauses::has_default() const +{ + for (Clauses::const_iterator p = this->clauses_.begin(); + p != this->clauses_.end(); + ++p) + if (p->is_default()) + return true; + return false; +} + // Traversal. int @@ -5594,17 +5590,60 @@ Select_clauses::traverse(Traverse* traverse) // Lowering. Here we pull out the channel and the send values, to // enforce the order of evaluation. We also add explicit send and -// receive statements to the clauses. +// receive statements to the clauses. This builds the entries in the +// local array of scase values. It sets *P_SEND_COUNT and +// *P_RECV_COUNT. void Select_clauses::lower(Gogo* gogo, Named_object* function, Block* b, - Temporary_statement* scases, Temporary_statement* recvok) + Temporary_statement* scases, Temporary_statement* recvok, + int *p_send_count, int *p_recv_count) { - size_t i = 0; + int send_count = 0; + int recv_count = 0; + bool has_default = false; for (Clauses::iterator p = this->clauses_.begin(); p != this->clauses_.end(); - ++p, ++i) - p->lower(gogo, function, b, scases, i, recvok); + ++p) + { + if (p->is_default()) + has_default = true; + else if (p->is_send()) + ++send_count; + else + ++recv_count; + } + + *p_send_count = send_count; + *p_recv_count = recv_count; + + int send_index = 0; + int recv_index = send_count; + for (Clauses::iterator p = this->clauses_.begin(); + p != this->clauses_.end(); + ++p) + { + int index; + if (p->is_default()) + index = -1; + else if (p->is_send()) + { + index = send_index; + ++send_index; + } + else + { + index = recv_index; + ++recv_index; + } + + p->lower(gogo, function, b, scases, index, recvok); + } + + go_assert(send_index == send_count); + go_assert(recv_index == send_count + recv_count); + go_assert(static_cast<size_t>(recv_index + (has_default ? 1 : 0)) + == this->size()); } // Determine types. @@ -5664,7 +5703,8 @@ Select_clauses::get_backend(Translate_context* context, p != this->clauses_.end(); ++p, ++i) { - Expression* index_expr = Expression::make_integer_ul(i, int_type, + Expression* index_expr = Expression::make_integer_sl(p->case_index(), + int_type, location); cases[i].push_back(index_expr->get_backend(context)); @@ -5749,6 +5789,7 @@ Select_statement::do_lower(Gogo* gogo, Named_object* function, Block* b = new Block(enclosing, loc); int ncases = this->clauses_->size(); + bool has_default = this->clauses_->has_default(); // Zero-case select. Just block the execution. if (ncases == 0) @@ -5766,11 +5807,13 @@ Select_statement::do_lower(Gogo* gogo, Named_object* function, // Two-case select with one default case. It is a non-blocking // send/receive. - if (ncases == 2 - && (this->clauses_->at(0).is_default() - || this->clauses_->at(1).is_default())) + if (ncases == 2 && has_default) return this->lower_two_case(b); + // We don't allocate an entry in scases for the default case. + if (has_default) + --ncases; + Type* scase_type = Channel_type::select_case_type(); Expression* ncases_expr = Expression::make_integer_ul(ncases, NULL, @@ -5803,7 +5846,10 @@ Select_statement::do_lower(Gogo* gogo, Named_object* function, b->add_statement(recvok); // Initialize the scases array. - this->clauses_->lower(gogo, function, b, scases, recvok); + int send_count; + int recv_count; + this->clauses_->lower(gogo, function, b, scases, recvok, &send_count, + &recv_count); // Build the call to selectgo. Later, in do_get_backend, we will // build a switch on the result that branches to the various cases. @@ -5817,11 +5863,18 @@ Select_statement::do_lower(Gogo* gogo, Named_object* function, order_ref = Expression::make_unary(OPERATOR_AND, order_ref, loc); order_ref = Expression::make_cast(unsafe_pointer_type, order_ref, loc); - Expression* count_expr = Expression::make_integer_ul(ncases, int_type, loc); + Expression* send_count_expr = Expression::make_integer_sl(send_count, + int_type, + loc); + Expression* recv_count_expr = Expression::make_integer_sl(recv_count, + int_type, + loc); + Expression* block_expr = Expression::make_boolean(!has_default, loc); - Call_expression* call = Runtime::make_call(Runtime::SELECTGO, loc, 3, + Call_expression* call = Runtime::make_call(Runtime::SELECTGO, loc, 5, scases_ref, order_ref, - count_expr); + send_count_expr, recv_count_expr, + block_expr); Expression* result = Expression::make_call_result(call, 0); Expression* ref = Expression::make_temporary_reference(this->index_, loc); diff --git a/gcc/go/gofrontend/statements.h b/gcc/go/gofrontend/statements.h index 47092b4912a..c08b493e6c9 100644 --- a/gcc/go/gofrontend/statements.h +++ b/gcc/go/gofrontend/statements.h @@ -1092,6 +1092,9 @@ class Select_clauses size() const { return this->clauses_.size(); } + bool + has_default() const; + // Traverse the select clauses. int traverse(Traverse*); @@ -1099,7 +1102,7 @@ class Select_clauses // Lower statements. void lower(Gogo*, Named_object*, Block*, Temporary_statement*, - Temporary_statement*); + Temporary_statement*, int* send_count, int* recv_count); // Determine types. void @@ -1138,8 +1141,9 @@ class Select_clauses Named_object* closedvar, bool is_default, Block* statements, Location location) : channel_(channel), val_(val), closed_(closed), var_(var), - closedvar_(closedvar), statements_(statements), location_(location), - is_send_(is_send), is_default_(is_default), is_lowered_(false) + closedvar_(closedvar), statements_(statements), case_index_(0), + location_(location), is_send_(is_send), is_default_(is_default), + is_lowered_(false), is_case_index_set_(false) { go_assert(is_default ? channel == NULL : channel != NULL); } // Traverse the select clause. @@ -1148,7 +1152,7 @@ class Select_clauses // Lower statements. void - lower(Gogo*, Named_object*, Block*, Temporary_statement*, size_t, + lower(Gogo*, Named_object*, Block*, Temporary_statement*, int, Temporary_statement*); // Determine types. @@ -1210,6 +1214,23 @@ class Select_clauses location() const { return this->location_; } + // Return the case index for this clause. + int + case_index() const + { + go_assert(this->is_case_index_set_); + return this->case_index_; + } + + // Set the case index. + void + set_case_index(int i) + { + go_assert(!this->is_case_index_set_); + this->case_index_ = i; + this->is_case_index_set_ = true; + } + // Whether this clause may fall through to the statement which // follows the overall select statement. bool @@ -1224,17 +1245,6 @@ class Select_clauses dump_clause(Ast_dump_context*) const; private: - // These values must match the values in libgo/go/runtime/select.go. - enum - { - caseRecv = 1, - caseSend = 2, - caseDefault = 3, - }; - - void - lower_default(Block*, Expression*); - void lower_send(Block*, Expression*, Expression*); @@ -1243,7 +1253,7 @@ class Select_clauses Temporary_statement*); void - set_case(Block*, Expression*, Expression*, Expression*, int); + set_case(Block*, Expression*, Expression*, Expression*); // The channel. Expression* channel_; @@ -1259,6 +1269,10 @@ class Select_clauses Named_object* closedvar_; // The statements to execute. Block* statements_; + // The index of this clause in the switch statement. If + // runtime.selectgo returns this index, this clause has been + // chosen. + int case_index_; // The location of this clause. Location location_; // Whether this is a send or a receive. @@ -1267,6 +1281,8 @@ class Select_clauses bool is_default_; // Whether this has been lowered. bool is_lowered_; + // Whether the case index has been set. + bool is_case_index_set_; }; Select_clause& diff --git a/gcc/go/gofrontend/types.cc b/gcc/go/gofrontend/types.cc index 12e783010db..16f0eb59a50 100644 --- a/gcc/go/gofrontend/types.cc +++ b/gcc/go/gofrontend/types.cc @@ -8905,13 +8905,10 @@ Channel_type::select_case_type() { Type* unsafe_pointer_type = Type::make_pointer_type(Type::make_void_type()); - Type* uint16_type = Type::lookup_integer_type("uint16"); - Type* int64_type = Type::lookup_integer_type("int64"); scase_type = - Type::make_builtin_struct_type(3, + Type::make_builtin_struct_type(2, "c", unsafe_pointer_type, - "elem", unsafe_pointer_type, - "kind", uint16_type); + "elem", unsafe_pointer_type); scase_type->set_is_struct_incomparable(); } return scase_type; diff --git a/libgo/go/runtime/select.go b/libgo/go/runtime/select.go index c31aa344b55..45cc2847945 100644 --- a/libgo/go/runtime/select.go +++ b/libgo/go/runtime/select.go @@ -18,23 +18,12 @@ import ( 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 } func sellock(scases []scase, lockorder []uint16) { @@ -121,7 +110,7 @@ func block() { // 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, ncases int) (int, bool) { +func selectgo(cas0 *scase, order0 *uint16, nsends, nrecvs int, block bool) (int, bool) { if debugSelect { print("select: cas0=", cas0, "\n") } @@ -131,6 +120,7 @@ func selectgo(cas0 *scase, order0 *uint16, ncases int) (int, bool) { 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] @@ -154,16 +144,12 @@ func selectgo(cas0 *scase, order0 *uint16, ncases int) (int, bool) { } // 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 } @@ -246,8 +232,7 @@ func selectgo(cas0 *scase, order0 *uint16, ncases int) (int, bool) { cas = &scases[casi] c = cas.c - switch cas.kind { - case caseRecv: + if casi >= nsends { sg = c.sendq.dequeue() if sg != nil { goto recv @@ -258,8 +243,7 @@ func selectgo(cas0 *scase, order0 *uint16, ncases int) (int, bool) { if c.closed != 0 { goto rclose } - - case caseSend: + } else { if c.closed != 0 { goto sclose } @@ -273,9 +257,9 @@ func selectgo(cas0 *scase, order0 *uint16, ncases int) (int, bool) { } } - if dfli >= 0 { + if !block { selunlock(scases, lockorder) - casi = dfli + casi = -1 goto retc } @@ -304,12 +288,10 @@ func selectgo(cas0 *scase, order0 *uint16, ncases int) (int, bool) { *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) } } @@ -357,7 +339,7 @@ func selectgo(cas0 *scase, order0 *uint16, ncases int) (int, bool) { } } else { c = k.c - if k.kind == caseSend { + if int(casei) < nsends { c.sendq.dequeueSudoG(sglist) } else { c.recvq.dequeueSudoG(sglist) @@ -376,13 +358,15 @@ func selectgo(cas0 *scase, order0 *uint16, ncases int) (int, bool) { 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 } selunlock(scases, lockorder) @@ -451,7 +435,7 @@ retc: // Check preemption, since unlike gc we don't check on every call. // A test case for this one is BenchmarkPingPongHog in proc_test.go. - if dfli >= 0 && getg().preempt { + if block && getg().preempt { checkPreempt() } @@ -492,20 +476,49 @@ func reflect_rselect(cases []runtimeSelect) (int, bool) { 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 } - return selectgo(&sel[0], &order[0], len(cases)) + // 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)) + + chosen, recvOK := selectgo(&sel[0], &order[0], 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) {