From 269f05ff58289cfdd3a35f0d9afc8e229a98f50e Mon Sep 17 00:00:00 2001 From: Ian Lance Taylor Date: Thu, 6 Jun 2019 00:44:01 +0000 Subject: [PATCH] compiler: make use of specialized fast map routines In the runtime there are specialized fast map routines for certain kep types. This CL lets the compiler make use of these functions, instead of always using the generic ones. As we now generate multiple versions of map delete calls, to make things easier we delay the expansion of the built-in delete function to flatten phase. Reviewed-on: https://go-review.googlesource.com/c/gofrontend/+/180858 From-SVN: r271983 --- gcc/go/gofrontend/MERGE | 2 +- gcc/go/gofrontend/escape.cc | 10 ++ gcc/go/gofrontend/expressions.cc | 237 ++++++++++++++++++++++--------- gcc/go/gofrontend/runtime.def | 59 ++++++++ gcc/go/gofrontend/statements.cc | 145 +++++++++++++------ gcc/go/gofrontend/types.cc | 45 +++++- gcc/go/gofrontend/types.h | 25 +++- libgo/go/runtime/map_fast32.go | 9 ++ libgo/go/runtime/map_fast64.go | 9 ++ libgo/go/runtime/map_faststr.go | 8 ++ 10 files changed, 435 insertions(+), 114 deletions(-) diff --git a/gcc/go/gofrontend/MERGE b/gcc/go/gofrontend/MERGE index d596f02f3fe..2b7525548f2 100644 --- a/gcc/go/gofrontend/MERGE +++ b/gcc/go/gofrontend/MERGE @@ -1,4 +1,4 @@ -2609f9b8420e2341fbbe40d7cf6af42b0fba7293 +bc7374913367fba9b10dc284af87eb539fb6c5b2 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/escape.cc b/gcc/go/gofrontend/escape.cc index 47c133150ec..2957c0d1e50 100644 --- a/gcc/go/gofrontend/escape.cc +++ b/gcc/go/gofrontend/escape.cc @@ -1622,6 +1622,16 @@ Escape_analysis_assign::expression(Expression** pexpr) } break; + case Runtime::MAPASSIGN_FAST32PTR: + case Runtime::MAPASSIGN_FAST64PTR: + case Runtime::MAPASSIGN_FASTSTR: + { + // Map key escapes. The last argument is the key. + Node* key_node = Node::make_node(call->args()->back()); + this->assign(this->context_->sink(), key_node); + } + break; + case Runtime::IFACEE2T2: case Runtime::IFACEI2T2: { diff --git a/gcc/go/gofrontend/expressions.cc b/gcc/go/gofrontend/expressions.cc index 1493ddc675f..061db5aa8b9 100644 --- a/gcc/go/gofrontend/expressions.cc +++ b/gcc/go/gofrontend/expressions.cc @@ -7843,63 +7843,33 @@ Builtin_call_expression::do_lower(Gogo*, Named_object* function, case BUILTIN_DELETE: { - // Lower to a runtime function call. - const Expression_list* args = this->args(); - if (args == NULL || args->size() < 2) - this->report_error(_("not enough arguments")); - else if (args->size() > 2) - this->report_error(_("too many arguments")); - else if (args->front()->type()->map_type() == NULL) - this->report_error(_("argument 1 must be a map")); - else - { - // Since this function returns no value it must appear in - // a statement by itself, so we don't have to worry about - // order of evaluation of values around it. Evaluate the - // map first to get order of evaluation right. - Map_type* mt = args->front()->type()->map_type(); - Temporary_statement* map_temp = - Statement::make_temporary(mt, args->front(), loc); - inserter->insert(map_temp); - - Temporary_statement* key_temp = - Statement::make_temporary(mt->key_type(), args->back(), loc); - inserter->insert(key_temp); - - Expression* e1 = Expression::make_type_descriptor(mt, loc); - Expression* e2 = Expression::make_temporary_reference(map_temp, - loc); - Expression* e3 = Expression::make_temporary_reference(key_temp, - loc); - - // If the call to delete is deferred, and is in a loop, - // then the loop will only have a single instance of the - // temporary variable. Passing the address of the - // temporary variable here means that the deferred call - // will see the last value in the loop, not the current - // value. So for this unusual case copy the value into - // the heap. - if (!this->is_deferred()) - e3 = Expression::make_unary(OPERATOR_AND, e3, loc); - else - { - Expression* a = Expression::make_allocation(mt->key_type(), - loc); - Temporary_statement* atemp = - Statement::make_temporary(NULL, a, loc); - inserter->insert(atemp); - - a = Expression::make_temporary_reference(atemp, loc); - a = Expression::make_dereference(a, NIL_CHECK_NOT_NEEDED, loc); - Statement* s = Statement::make_assignment(a, e3, loc); - inserter->insert(s); - - e3 = Expression::make_temporary_reference(atemp, loc); - } - - return Runtime::make_call(Runtime::MAPDELETE, this->location(), - 3, e1, e2, e3); - } + const Expression_list* args = this->args(); + if (args == NULL || args->size() < 2) + this->report_error(_("not enough arguments")); + else if (args->size() > 2) + this->report_error(_("too many arguments")); + else if (args->front()->type()->map_type() == NULL) + this->report_error(_("argument 1 must be a map")); + else + { + Type* key_type = + args->front()->type()->map_type()->key_type(); + Expression_list::iterator pa = this->args()->begin(); + pa++; + Type* arg_type = (*pa)->type(); + std::string reason; + if (!Type::are_assignable(key_type, arg_type, &reason)) + { + if (reason.empty()) + go_error_at(loc, "argument 2 has incompatible type"); + else + go_error_at(loc, "argument 2 has incompatible type (%s)", + reason.c_str()); + this->set_is_error(); + } + else if (!Type::are_identical(key_type, arg_type, 0, NULL)) + *pa = Expression::make_cast(key_type, *pa, loc); + } } break; @@ -7935,6 +7905,12 @@ Expression* Builtin_call_expression::do_flatten(Gogo* gogo, Named_object* function, Statement_inserter* inserter) { + if (this->is_error_expression()) + { + go_assert(saw_errors()); + return this; + } + Location loc = this->location(); switch (this->code_) @@ -8078,6 +8054,96 @@ Builtin_call_expression::do_flatten(Gogo* gogo, Named_object* function, } } break; + + case BUILTIN_DELETE: + { + // Lower to a runtime function call. + const Expression_list* args = this->args(); + + // Since this function returns no value it must appear in + // a statement by itself, so we don't have to worry about + // order of evaluation of values around it. Evaluate the + // map first to get order of evaluation right. + Map_type* mt = args->front()->type()->map_type(); + Temporary_statement* map_temp = + Statement::make_temporary(mt, args->front(), loc); + inserter->insert(map_temp); + + Temporary_statement* key_temp = + Statement::make_temporary(mt->key_type(), args->back(), loc); + inserter->insert(key_temp); + + Expression* e1 = Expression::make_type_descriptor(mt, loc); + Expression* e2 = Expression::make_temporary_reference(map_temp, + loc); + Expression* e3 = Expression::make_temporary_reference(key_temp, + loc); + + Runtime::Function code; + switch (mt->algorithm(gogo)) + { + case Map_type::MAP_ALG_FAST32: + case Map_type::MAP_ALG_FAST32PTR: + { + code = Runtime::MAPDELETE_FAST32; + Type* uint32_type = Type::lookup_integer_type("uint32"); + Type* uint32_ptr_type = Type::make_pointer_type(uint32_type); + e3 = Expression::make_unary(OPERATOR_AND, e3, loc); + e3 = Expression::make_unsafe_cast(uint32_ptr_type, e3, + loc); + e3 = Expression::make_dereference(e3, + Expression::NIL_CHECK_NOT_NEEDED, + loc); + break; + } + case Map_type::MAP_ALG_FAST64: + case Map_type::MAP_ALG_FAST64PTR: + { + code = Runtime::MAPDELETE_FAST64; + Type* uint64_type = Type::lookup_integer_type("uint64"); + Type* uint64_ptr_type = Type::make_pointer_type(uint64_type); + e3 = Expression::make_unary(OPERATOR_AND, e3, loc); + e3 = Expression::make_unsafe_cast(uint64_ptr_type, e3, + loc); + e3 = Expression::make_dereference(e3, + Expression::NIL_CHECK_NOT_NEEDED, + loc); + break; + } + case Map_type::MAP_ALG_FASTSTR: + code = Runtime::MAPDELETE_FASTSTR; + break; + default: + code = Runtime::MAPDELETE; + + // If the call to delete is deferred, and is in a loop, + // then the loop will only have a single instance of the + // temporary variable. Passing the address of the + // temporary variable here means that the deferred call + // will see the last value in the loop, not the current + // value. So for this unusual case copy the value into + // the heap. + if (!this->is_deferred()) + e3 = Expression::make_unary(OPERATOR_AND, e3, loc); + else + { + Expression* a = Expression::make_allocation(mt->key_type(), + loc); + Temporary_statement* atemp = + Statement::make_temporary(NULL, a, loc); + inserter->insert(atemp); + + a = Expression::make_temporary_reference(atemp, loc); + a = Expression::make_dereference(a, NIL_CHECK_NOT_NEEDED, loc); + Statement* s = Statement::make_assignment(a, e3, loc); + inserter->insert(s); + + e3 = Expression::make_temporary_reference(atemp, loc); + } + } + + return Runtime::make_call(code, loc, 3, e1, e2, e3); + } } return this; @@ -10159,6 +10225,9 @@ Builtin_call_expression::do_export(Export_function_body* efb) const case BUILTIN_CAP: s = "cap"; break; + case BUILTIN_DELETE: + s = "delete"; + break; case BUILTIN_PRINT: s = "print"; break; @@ -13031,20 +13100,54 @@ Map_index_expression::get_value_pointer(Gogo* gogo) this->index_, loc); + Expression* type_expr = Expression::make_type_descriptor(type, loc); Expression* zero = type->fat_zero_value(gogo); - Expression* map_index; - if (zero == NULL) - map_index = - Runtime::make_call(Runtime::MAPACCESS1, loc, 3, - Expression::make_type_descriptor(type, loc), - map_ref, index_ptr); + { + Runtime::Function code; + Expression* key; + switch (type->algorithm(gogo)) + { + case Map_type::MAP_ALG_FAST32: + case Map_type::MAP_ALG_FAST32PTR: + { + Type* uint32_type = Type::lookup_integer_type("uint32"); + Type* uint32_ptr_type = Type::make_pointer_type(uint32_type); + key = Expression::make_unsafe_cast(uint32_ptr_type, index_ptr, + loc); + key = Expression::make_dereference(key, NIL_CHECK_NOT_NEEDED, + loc); + code = Runtime::MAPACCESS1_FAST32; + break; + } + case Map_type::MAP_ALG_FAST64: + case Map_type::MAP_ALG_FAST64PTR: + { + Type* uint64_type = Type::lookup_integer_type("uint64"); + Type* uint64_ptr_type = Type::make_pointer_type(uint64_type); + key = Expression::make_unsafe_cast(uint64_ptr_type, index_ptr, + loc); + key = Expression::make_dereference(key, NIL_CHECK_NOT_NEEDED, + loc); + code = Runtime::MAPACCESS1_FAST64; + break; + } + case Map_type::MAP_ALG_FASTSTR: + key = this->index_; + code = Runtime::MAPACCESS1_FASTSTR; + break; + default: + key = index_ptr; + code = Runtime::MAPACCESS1; + break; + } + map_index = Runtime::make_call(code, loc, 3, + type_expr, map_ref, key); + } else - map_index = - Runtime::make_call(Runtime::MAPACCESS1_FAT, loc, 4, - Expression::make_type_descriptor(type, loc), - map_ref, index_ptr, zero); + map_index = Runtime::make_call(Runtime::MAPACCESS1_FAT, loc, 4, + type_expr, map_ref, index_ptr, zero); Type* val_type = type->val_type(); this->value_pointer_ = diff --git a/gcc/go/gofrontend/runtime.def b/gcc/go/gofrontend/runtime.def index b0e686161fe..34c86e8aafc 100644 --- a/gcc/go/gofrontend/runtime.def +++ b/gcc/go/gofrontend/runtime.def @@ -109,6 +109,18 @@ DEF_GO_RUNTIME(CONSTRUCT_MAP, "__go_construct_map", DEF_GO_RUNTIME(MAPACCESS1, "runtime.mapaccess1", P3(TYPE, MAP, POINTER), R1(POINTER)) +// Look up a uint32 key in a map. +DEF_GO_RUNTIME(MAPACCESS1_FAST32, "runtime.mapaccess1_fast32", + P3(TYPE, MAP, UINT32), R1(POINTER)) + +// Look up a uint64 key in a map. +DEF_GO_RUNTIME(MAPACCESS1_FAST64, "runtime.mapaccess1_fast64", + P3(TYPE, MAP, UINT64), R1(POINTER)) + +// Look up a string key in a map. +DEF_GO_RUNTIME(MAPACCESS1_FASTSTR, "runtime.mapaccess1_faststr", + P3(TYPE, MAP, STRING), R1(POINTER)) + // Look up a key in a map when the value is large. DEF_GO_RUNTIME(MAPACCESS1_FAT, "runtime.mapaccess1_fat", P4(TYPE, MAP, POINTER, POINTER), R1(POINTER)) @@ -118,6 +130,21 @@ DEF_GO_RUNTIME(MAPACCESS1_FAT, "runtime.mapaccess1_fat", DEF_GO_RUNTIME(MAPACCESS2, "runtime.mapaccess2", P3(TYPE, MAP, POINTER), R2(POINTER, BOOL)) +// Look up a uint32 key in a map returning the value and whether +// it is present. +DEF_GO_RUNTIME(MAPACCESS2_FAST32, "runtime.mapaccess2_fast32", + P3(TYPE, MAP, UINT32), R2(POINTER, BOOL)) + +// Look up a uint64 key in a map returning the value and whether +// it is present. +DEF_GO_RUNTIME(MAPACCESS2_FAST64, "runtime.mapaccess2_fast64", + P3(TYPE, MAP, UINT64), R2(POINTER, BOOL)) + +// Look up a string key in a map returning the value and whether +// it is present. +DEF_GO_RUNTIME(MAPACCESS2_FASTSTR, "runtime.mapaccess2_faststr", + P3(TYPE, MAP, STRING), R2(POINTER, BOOL)) + // Look up a key in a map, returning the value and whether it is // present, when the value is large. DEF_GO_RUNTIME(MAPACCESS2_FAT, "runtime.mapaccess2_fat", @@ -127,9 +154,41 @@ DEF_GO_RUNTIME(MAPACCESS2_FAT, "runtime.mapaccess2_fat", DEF_GO_RUNTIME(MAPASSIGN, "runtime.mapassign", P3(TYPE, MAP, POINTER), R1(POINTER)) +// Assignment to a uint32 key in a map. +DEF_GO_RUNTIME(MAPASSIGN_FAST32, "runtime.mapassign_fast32", + P3(TYPE, MAP, UINT32), R1(POINTER)) + +// Assignment to a uint64 key in a map. +DEF_GO_RUNTIME(MAPASSIGN_FAST64, "runtime.mapassign_fast64", + P3(TYPE, MAP, UINT64), R1(POINTER)) + +// Assignment to a 32-bit pointer key in a map. +DEF_GO_RUNTIME(MAPASSIGN_FAST32PTR, "runtime.mapassign_fast32ptr", + P3(TYPE, MAP, POINTER), R1(POINTER)) + +// Assignment to a 64-bit pointer key in a map. +DEF_GO_RUNTIME(MAPASSIGN_FAST64PTR, "runtime.mapassign_fast64ptr", + P3(TYPE, MAP, POINTER), R1(POINTER)) + +// Assignment to a string key in a map. +DEF_GO_RUNTIME(MAPASSIGN_FASTSTR, "runtime.mapassign_faststr", + P3(TYPE, MAP, STRING), R1(POINTER)) + // Delete a key from a map. DEF_GO_RUNTIME(MAPDELETE, "runtime.mapdelete", P3(TYPE, MAP, POINTER), R0()) +// Delete a uint32 key from a map. +DEF_GO_RUNTIME(MAPDELETE_FAST32, "runtime.mapdelete_fast32", + P3(TYPE, MAP, UINT32), R0()) + +// Delete a uint64 key from a map. +DEF_GO_RUNTIME(MAPDELETE_FAST64, "runtime.mapdelete_fast64", + P3(TYPE, MAP, UINT64), R0()) + +// Delete a string key from a map. +DEF_GO_RUNTIME(MAPDELETE_FASTSTR, "runtime.mapdelete_faststr", + P3(TYPE, MAP, STRING), R0()) + // Begin a range over a map. DEF_GO_RUNTIME(MAPITERINIT, "runtime.mapiterinit", P3(TYPE, MAP, POINTER), R0()) diff --git a/gcc/go/gofrontend/statements.cc b/gcc/go/gofrontend/statements.cc index fe9b748de72..8368c5b72bb 100644 --- a/gcc/go/gofrontend/statements.cc +++ b/gcc/go/gofrontend/statements.cc @@ -816,7 +816,7 @@ Assignment_statement::do_traverse_assignments(Traverse_assignments* tassign) // call. Mark some slice assignments as not requiring a write barrier. Statement* -Assignment_statement::do_lower(Gogo*, Named_object*, Block* enclosing, +Assignment_statement::do_lower(Gogo* gogo, Named_object*, Block* enclosing, Statement_inserter*) { Map_index_expression* mie = this->lhs_->map_index_expression(); @@ -864,7 +864,59 @@ Assignment_statement::do_lower(Gogo*, Named_object*, Block* enclosing, Temporary_reference_expression* ref = Expression::make_temporary_reference(key_temp, loc); Expression* a3 = Expression::make_unary(OPERATOR_AND, ref, loc); - Expression* call = Runtime::make_call(Runtime::MAPASSIGN, loc, 3, + Runtime::Function code; + Map_type::Map_alg alg = mt->algorithm(gogo); + switch (alg) + { + case Map_type::MAP_ALG_FAST32: + { + code = Runtime::MAPASSIGN_FAST32; + Type* uint32_type = Type::lookup_integer_type("uint32"); + Type* uint32_ptr_type = Type::make_pointer_type(uint32_type); + a3 = Expression::make_unsafe_cast(uint32_ptr_type, a3, + loc); + a3 = Expression::make_dereference(a3, + Expression::NIL_CHECK_NOT_NEEDED, + loc); + break; + } + case Map_type::MAP_ALG_FAST64: + { + code = Runtime::MAPASSIGN_FAST64; + Type* uint64_type = Type::lookup_integer_type("uint64"); + Type* uint64_ptr_type = Type::make_pointer_type(uint64_type); + a3 = Expression::make_unsafe_cast(uint64_ptr_type, a3, + loc); + a3 = Expression::make_dereference(a3, + Expression::NIL_CHECK_NOT_NEEDED, + loc); + break; + } + case Map_type::MAP_ALG_FAST32PTR: + case Map_type::MAP_ALG_FAST64PTR: + { + code = (alg == Map_type::MAP_ALG_FAST32PTR + ? Runtime::MAPASSIGN_FAST32PTR + : Runtime::MAPASSIGN_FAST64PTR); + Type* ptr_type = + Type::make_pointer_type(Type::make_void_type()); + Type* ptr_ptr_type = Type::make_pointer_type(ptr_type); + a3 = Expression::make_unsafe_cast(ptr_ptr_type, a3, + loc); + a3 = Expression::make_dereference(a3, + Expression::NIL_CHECK_NOT_NEEDED, + loc); + break; + } + case Map_type::MAP_ALG_FASTSTR: + code = Runtime::MAPASSIGN_FASTSTR; + a3 = ref; + break; + default: + code = Runtime::MAPASSIGN; + break; + } + Expression* call = Runtime::make_call(code, loc, 3, a1, a2, a3); Type* ptrval_type = Type::make_pointer_type(mt->val_type()); call = Expression::make_cast(ptrval_type, call, loc); @@ -1451,7 +1503,47 @@ Tuple_map_assignment_statement::do_lower(Gogo* gogo, Named_object*, Expression* a4 = map_type->fat_zero_value(gogo); Call_expression* call; if (a4 == NULL) - call = Runtime::make_call(Runtime::MAPACCESS2, loc, 3, a1, a2, a3); + { + Runtime::Function code; + Map_type::Map_alg alg = map_type->algorithm(gogo); + switch (alg) + { + case Map_type::MAP_ALG_FAST32: + case Map_type::MAP_ALG_FAST32PTR: + { + code = Runtime::MAPACCESS2_FAST32; + Type* uint32_type = Type::lookup_integer_type("uint32"); + Type* uint32_ptr_type = Type::make_pointer_type(uint32_type); + a3 = Expression::make_unsafe_cast(uint32_ptr_type, a3, + loc); + a3 = Expression::make_dereference(a3, + Expression::NIL_CHECK_NOT_NEEDED, + loc); + break; + } + case Map_type::MAP_ALG_FAST64: + case Map_type::MAP_ALG_FAST64PTR: + { + code = Runtime::MAPACCESS2_FAST64; + Type* uint64_type = Type::lookup_integer_type("uint64"); + Type* uint64_ptr_type = Type::make_pointer_type(uint64_type); + a3 = Expression::make_unsafe_cast(uint64_ptr_type, a3, + loc); + a3 = Expression::make_dereference(a3, + Expression::NIL_CHECK_NOT_NEEDED, + loc); + break; + } + case Map_type::MAP_ALG_FASTSTR: + code = Runtime::MAPACCESS2_FASTSTR; + a3 = ref; + break; + default: + code = Runtime::MAPACCESS2; + break; + } + call = Runtime::make_call(code, loc, 3, a1, a2, a3); + } else call = Runtime::make_call(Runtime::MAPACCESS2_FAT, loc, 4, a1, a2, a3, a4); ref = Expression::make_temporary_reference(val_ptr_temp, loc); @@ -6325,47 +6417,20 @@ For_range_statement::lower_map_range_clear(Type* map_type, if (enclosing->bindings()->lookup_local(index_no->name()) != index_no) return NULL; - // Match the body. When lowering the builtin delete function, we have - // inserted temporaries, so we actually match for - // - // tmp1 = m - // tmp2 = k - // runtime.mapdelete(TYPE, tmp1, &tmp2) - + // Match the body, a single call statement delete(m, k). const std::vector* statements = this->statements_->statements(); - if (statements->size() != 3) - return NULL; - - Temporary_statement* ts1 = statements->at(0)->temporary_statement(); - Temporary_statement* ts2 = statements->at(1)->temporary_statement(); - Expression_statement* es3 = statements->at(2)->expression_statement(); - if (ts1 == NULL || ts2 == NULL || es3 == NULL - || !Expression::is_same_variable(orig_range_expr, ts1->init()) - || !Expression::is_same_variable(this->index_var_, ts2->init())) - return NULL; - Call_expression* call = es3->expr()->call_expression(); - if (call == NULL) - return NULL; - Func_expression* fe = call->fn()->func_expression(); - if (fe == NULL || !fe->is_runtime_function() - || fe->runtime_code() != Runtime::MAPDELETE) + if (statements->size() != 1) return NULL; - Expression* a1 = call->args()->at(1); - a1 = (a1->unsafe_conversion_expression() != NULL - ? a1->unsafe_conversion_expression()->expr() - : a1); - Temporary_reference_expression* tre = a1->temporary_reference_expression(); - if (tre == NULL || tre->statement() != ts1) + Expression_statement* es = statements->at(0)->expression_statement(); + if (es == NULL) return NULL; - Expression* a2 = call->args()->at(2); - a2 = (a2->conversion_expression() != NULL - ? a2->conversion_expression()->expr() - : a2); - Unary_expression* ue = a2->unary_expression(); - if (ue == NULL || ue->op() != OPERATOR_AND) + Call_expression* call = es->expr()->call_expression(); + if (call == NULL || !call->is_builtin() + || call->builtin_call_expression()->code() + != Builtin_call_expression::BUILTIN_DELETE) return NULL; - tre = ue->operand()->temporary_reference_expression(); - if (tre == NULL || tre->statement() != ts2) + if (!Expression::is_same_variable(call->args()->at(0), orig_range_expr) + || !Expression::is_same_variable(call->args()->at(1), this->index_var_)) return NULL; // Everything matches. Rewrite to mapclear(TYPE, MAP). diff --git a/gcc/go/gofrontend/types.cc b/gcc/go/gofrontend/types.cc index 011a7afe54d..cc65bd8d749 100644 --- a/gcc/go/gofrontend/types.cc +++ b/gcc/go/gofrontend/types.cc @@ -7890,7 +7890,7 @@ int64_t Map_type::zero_value_align; // pass as the zero value to those functions. Otherwise, in the // normal case, return NULL. The map requires the "fat" functions if // the value size is larger than max_zero_size bytes. max_zero_size -// must match maxZero in libgo/go/runtime/hashmap.go. +// must match maxZero in libgo/go/runtime/map.go. Expression* Map_type::fat_zero_value(Gogo* gogo) @@ -7938,6 +7938,43 @@ Map_type::fat_zero_value(Gogo* gogo) return z; } +// Map algorithm to use for this map type. + +Map_type::Map_alg +Map_type::algorithm(Gogo* gogo) +{ + int64_t size; + bool ok = this->val_type_->backend_type_size(gogo, &size); + if (!ok || size > Map_type::max_val_size) + return MAP_ALG_SLOW; + + Type* key_type = this->key_type_; + if (key_type->is_string_type()) + return MAP_ALG_FASTSTR; + if (!key_type->compare_is_identity(gogo)) + return MAP_ALG_SLOW; + + ok = key_type->backend_type_size(gogo, &size); + if (!ok) + return MAP_ALG_SLOW; + if (size == 4) + return (key_type->has_pointer() + ? MAP_ALG_FAST32PTR + : MAP_ALG_FAST32); + if (size == 8) + { + if (!key_type->has_pointer()) + return MAP_ALG_FAST64; + Type* ptr_type = Type::make_pointer_type(Type::make_void_type()); + ok = ptr_type->backend_type_size(gogo, &size); + if (ok && size == 8) + return MAP_ALG_FAST64PTR; + // Key contains pointer but is not a single pointer. + // Use slow version. + } + return MAP_ALG_SLOW; +} + // Return whether VAR is the map zero value. bool @@ -8027,7 +8064,7 @@ Map_type::do_hash_for_method(Gogo* gogo, int flags) const // Get the backend representation for a map type. A map type is // represented as a pointer to a struct. The struct is hmap in -// runtime/hashmap.go. +// runtime/map.go. Btype* Map_type::do_get_backend(Gogo* gogo) @@ -8233,7 +8270,7 @@ Map_type::do_type_descriptor(Gogo* gogo, Named_type* name) } // Return the bucket type to use for a map type. This must correspond -// to libgo/go/runtime/hashmap.go. +// to libgo/go/runtime/map.go. Type* Map_type::bucket_type(Gogo* gogo, int64_t keysize, int64_t valsize) @@ -8265,7 +8302,7 @@ Map_type::bucket_type(Gogo* gogo, int64_t keysize, int64_t valsize) // be marked as having no pointers. Arrange for the bucket to have // no pointers by changing the type of the overflow field to uintptr // in this case. See comment on the hmap.overflow field in - // libgo/go/runtime/hashmap.go. + // libgo/go/runtime/map.go. Type* overflow_type; if (!key_type->has_pointer() && !val_type->has_pointer()) overflow_type = Type::lookup_integer_type("uintptr"); diff --git a/gcc/go/gofrontend/types.h b/gcc/go/gofrontend/types.h index 721d1fc64ac..375f7112742 100644 --- a/gcc/go/gofrontend/types.h +++ b/gcc/go/gofrontend/types.h @@ -2912,6 +2912,27 @@ class Map_type : public Type Expression* fat_zero_value(Gogo*); + // Map algorithm to use for this map type. We may use specialized + // fast map routines for certain key types. + enum Map_alg + { + // 32-bit key. + MAP_ALG_FAST32, + // 32-bit pointer key. + MAP_ALG_FAST32PTR, + // 64-bit key. + MAP_ALG_FAST64, + // 64-bit pointer key. + MAP_ALG_FAST64PTR, + // String key. + MAP_ALG_FASTSTR, + // Anything else. + MAP_ALG_SLOW, + }; + + Map_alg + algorithm(Gogo*); + // Return whether VAR is the map zero value. static bool is_zero_value(Variable* var); @@ -2931,7 +2952,7 @@ class Map_type : public Type static Type* make_map_type_descriptor_type(); - // This must be in sync with libgo/go/runtime/hashmap.go. + // This must be in sync with libgo/go/runtime/map.go. static const int bucket_size = 8; protected: @@ -2974,7 +2995,7 @@ class Map_type : public Type do_export(Export*) const; private: - // These must be in sync with libgo/go/runtime/hashmap.go. + // These must be in sync with libgo/go/runtime/map.go. static const int max_key_size = 128; static const int max_val_size = 128; static const int max_zero_size = 1024; diff --git a/libgo/go/runtime/map_fast32.go b/libgo/go/runtime/map_fast32.go index 1fa5cd968e4..07a35e18fc6 100644 --- a/libgo/go/runtime/map_fast32.go +++ b/libgo/go/runtime/map_fast32.go @@ -9,6 +9,15 @@ import ( "unsafe" ) +// For gccgo, use go:linkname to rename compiler-called functions to +// themselves, so that the compiler will export them. +// +//go:linkname mapaccess1_fast32 runtime.mapaccess1_fast32 +//go:linkname mapaccess2_fast32 runtime.mapaccess2_fast32 +//go:linkname mapassign_fast32 runtime.mapassign_fast32 +//go:linkname mapassign_fast32ptr runtime.mapassign_fast32ptr +//go:linkname mapdelete_fast32 runtime.mapdelete_fast32 + func mapaccess1_fast32(t *maptype, h *hmap, key uint32) unsafe.Pointer { if raceenabled && h != nil { callerpc := getcallerpc() diff --git a/libgo/go/runtime/map_fast64.go b/libgo/go/runtime/map_fast64.go index d23ac23eb14..d21bf066343 100644 --- a/libgo/go/runtime/map_fast64.go +++ b/libgo/go/runtime/map_fast64.go @@ -9,6 +9,15 @@ import ( "unsafe" ) +// For gccgo, use go:linkname to rename compiler-called functions to +// themselves, so that the compiler will export them. +// +//go:linkname mapaccess1_fast64 runtime.mapaccess1_fast64 +//go:linkname mapaccess2_fast64 runtime.mapaccess2_fast64 +//go:linkname mapassign_fast64 runtime.mapassign_fast64 +//go:linkname mapassign_fast64ptr runtime.mapassign_fast64ptr +//go:linkname mapdelete_fast64 runtime.mapdelete_fast64 + func mapaccess1_fast64(t *maptype, h *hmap, key uint64) unsafe.Pointer { if raceenabled && h != nil { callerpc := getcallerpc() diff --git a/libgo/go/runtime/map_faststr.go b/libgo/go/runtime/map_faststr.go index eced15a6d5d..083980fac45 100644 --- a/libgo/go/runtime/map_faststr.go +++ b/libgo/go/runtime/map_faststr.go @@ -9,6 +9,14 @@ import ( "unsafe" ) +// For gccgo, use go:linkname to rename compiler-called functions to +// themselves, so that the compiler will export them. +// +//go:linkname mapaccess1_faststr runtime.mapaccess1_faststr +//go:linkname mapaccess2_faststr runtime.mapaccess2_faststr +//go:linkname mapassign_faststr runtime.mapassign_faststr +//go:linkname mapdelete_faststr runtime.mapdelete_faststr + func mapaccess1_faststr(t *maptype, h *hmap, ky string) unsafe.Pointer { if raceenabled && h != nil { callerpc := getcallerpc() -- 2.30.2