diff options
author | Ian Lance Taylor <ian@gcc.gnu.org> | 2020-01-02 21:55:32 +0000 |
---|---|---|
committer | Ian Lance Taylor <ian@gcc.gnu.org> | 2020-01-02 21:55:32 +0000 |
commit | 10172a64cedd95b302a9709429a4832a879667da (patch) | |
tree | 736b88eb69baa715a8ac1dbfb4b059eece8a049f /gcc/go | |
parent | 9279b5ba4538da8041f074db3f5fcd9e8ecff93e (diff) | |
download | gcc-10172a64cedd95b302a9709429a4832a879667da.zip gcc-10172a64cedd95b302a9709429a4832a879667da.tar.gz gcc-10172a64cedd95b302a9709429a4832a879667da.tar.bz2 |
compiler, runtime, reflect: generate hash functions only for map keys
Right now we generate hash functions for all types, just in case they
are used as map keys. That's a lot of wasted effort and binary size
for types which will never be used as a map key. Instead, generate
hash functions only for types that we know are map keys.
Just doing that is a bit too simple, since maps with an interface type
as a key might have to hash any concrete key type that implements that
interface. So for that case, implement hashing of such types at
runtime (instead of with generated code). It will be slower, but only
for maps with interface types as keys, and maybe only a bit slower as
the aeshash time probably dominates the dispatch time.
Reorg where we keep the equals and hash functions. Move the hash function
from the key type to the map type, saving a field in every non-map type.
That leaves only one function in the alg structure, so get rid of that and
just keep the equal function in the type descriptor itself.
While we're here, reorganize the rtype struct to more closely match
the gc version.
This is the gofrontend version of https://golang.org/cl/191198.
Reviewed-on: https://go-review.googlesource.com/c/gofrontend/+/212843
From-SVN: r279848
Diffstat (limited to 'gcc/go')
-rw-r--r-- | gcc/go/gofrontend/MERGE | 2 | ||||
-rw-r--r-- | gcc/go/gofrontend/gogo.cc | 26 | ||||
-rw-r--r-- | gcc/go/gofrontend/gogo.h | 5 | ||||
-rw-r--r-- | gcc/go/gofrontend/names.cc | 10 | ||||
-rw-r--r-- | gcc/go/gofrontend/types.cc | 209 | ||||
-rw-r--r-- | gcc/go/gofrontend/types.h | 15 |
6 files changed, 106 insertions, 161 deletions
diff --git a/gcc/go/gofrontend/MERGE b/gcc/go/gofrontend/MERGE index 5e00d4f..ea09abe 100644 --- a/gcc/go/gofrontend/MERGE +++ b/gcc/go/gofrontend/MERGE @@ -1,4 +1,4 @@ -b5c950fb98042fe434edca0c2403234692f25cd4 +9163fa28b89222cd851c0d24bd6a1384d1379c55 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/gogo.cc b/gcc/go/gofrontend/gogo.cc index db533bb..b50d8a2 100644 --- a/gcc/go/gofrontend/gogo.cc +++ b/gcc/go/gofrontend/gogo.cc @@ -2722,7 +2722,7 @@ Gogo::clear_file_scope() // parse tree is lowered. void -Gogo::queue_hash_function(Type* type, Named_type* name, int64_t size, +Gogo::queue_hash_function(Type* type, int64_t size, const std::string& hash_name, Function_type* hash_fntype) { @@ -2730,7 +2730,7 @@ Gogo::queue_hash_function(Type* type, Named_type* name, int64_t size, go_assert(!this->in_global_scope()); Specific_type_function::Specific_type_function_kind kind = Specific_type_function::SPECIFIC_HASH; - Specific_type_function* tsf = new Specific_type_function(type, name, size, + Specific_type_function* tsf = new Specific_type_function(type, NULL, size, kind, hash_name, hash_fntype); this->specific_type_functions_.push_back(tsf); @@ -2783,10 +2783,7 @@ Specific_type_functions::type(Type* t) if (nt->is_alias()) return TRAVERSE_CONTINUE; if (t->needs_specific_type_functions(this->gogo_)) - { - t->equal_function(this->gogo_, nt, NULL); - t->hash_function(this->gogo_, nt, NULL); - } + t->equal_function(this->gogo_, nt, NULL); // If this is a struct type, we don't want to make functions // for the unnamed struct. @@ -2820,10 +2817,15 @@ Specific_type_functions::type(Type* t) case Type::TYPE_STRUCT: case Type::TYPE_ARRAY: if (t->needs_specific_type_functions(this->gogo_)) - { - t->equal_function(this->gogo_, NULL, NULL); - t->hash_function(this->gogo_, NULL, NULL); - } + t->equal_function(this->gogo_, NULL, NULL); + break; + + case Type::TYPE_MAP: + { + Type* key_type = t->map_type()->key_type(); + if (key_type->needs_specific_type_functions(this->gogo_)) + key_type->hash_function(this->gogo_, NULL); + } break; default: @@ -2846,8 +2848,8 @@ Gogo::write_specific_type_functions() Specific_type_function* tsf = this->specific_type_functions_.back(); this->specific_type_functions_.pop_back(); if (tsf->kind == Specific_type_function::SPECIFIC_HASH) - tsf->type->write_hash_function(this, tsf->name, tsf->size, - tsf->fnname, tsf->fntype); + tsf->type->write_hash_function(this, tsf->size, tsf->fnname, + tsf->fntype); else tsf->type->write_equal_function(this, tsf->name, tsf->size, tsf->fnname, tsf->fntype); diff --git a/gcc/go/gofrontend/gogo.h b/gcc/go/gofrontend/gogo.h index cd4e38f..27d7b4c 100644 --- a/gcc/go/gofrontend/gogo.h +++ b/gcc/go/gofrontend/gogo.h @@ -602,8 +602,7 @@ class Gogo // is used when a type-specific hash function is needed when not at // top level. void - queue_hash_function(Type* type, Named_type* name, int64_t size, - const std::string& hash_name, + queue_hash_function(Type* type, int64_t size, const std::string& hash_name, Function_type* hash_fntype); // Queue up a type-specific equal function to be written out. This @@ -879,7 +878,7 @@ class Gogo // Return the name of the hash function for TYPE. std::string - hash_function_name(const Type*, const Named_type*); + hash_function_name(const Type*); // Return the name of the equal function for TYPE. std::string diff --git a/gcc/go/gofrontend/names.cc b/gcc/go/gofrontend/names.cc index 959415a..f4ad1815 100644 --- a/gcc/go/gofrontend/names.cc +++ b/gcc/go/gofrontend/names.cc @@ -287,16 +287,12 @@ Gogo::stub_method_name(const Package* package, const std::string& mname) return ret; } -// Return the name of the hash function for TYPE. If NAME is not NULL -// it is the name of the type. +// Return the name of the hash function for TYPE. std::string -Gogo::hash_function_name(const Type* type, const Named_type* name) +Gogo::hash_function_name(const Type* type) { - const Type* rtype = type; - if (name != NULL) - rtype = name; - std::string tname = rtype->mangled_name(this); + std::string tname = type->mangled_name(this); return tname + "..hash"; } diff --git a/gcc/go/gofrontend/types.cc b/gcc/go/gofrontend/types.cc index 1004040..27d53df 100644 --- a/gcc/go/gofrontend/types.cc +++ b/gcc/go/gofrontend/types.cc @@ -1540,6 +1540,11 @@ Type::convert_builtin_named_types(Gogo* gogo) } } +// Values to store in the tflag field of a type descriptor. This must +// match the definitions in libgo/go/runtime/type.go. + +const int TFLAG_REGULAR_MEMORY = 1 << 3; + // Return the type of a type descriptor. We should really tie this to // runtime.Type rather than copying it. This must match the struct "_type" // declared in libgo/go/runtime/type.go. @@ -1566,21 +1571,11 @@ Type::make_type_descriptor_type() Type* void_type = Type::make_void_type(); Type* unsafe_pointer_type = Type::make_pointer_type(void_type); - Typed_identifier_list *params = new Typed_identifier_list(); - params->push_back(Typed_identifier("key", unsafe_pointer_type, bloc)); - params->push_back(Typed_identifier("seed", uintptr_type, bloc)); - - Typed_identifier_list* results = new Typed_identifier_list(); - results->push_back(Typed_identifier("", uintptr_type, bloc)); - - Type* hash_fntype = Type::make_function_type(NULL, params, results, - bloc); - - params = new Typed_identifier_list(); + Typed_identifier_list* params = new Typed_identifier_list(); params->push_back(Typed_identifier("key1", unsafe_pointer_type, bloc)); params->push_back(Typed_identifier("key2", unsafe_pointer_type, bloc)); - results = new Typed_identifier_list(); + Typed_identifier_list* results = new Typed_identifier_list(); results->push_back(Typed_identifier("", Type::lookup_bool_type(), bloc)); Type* equal_fntype = Type::make_function_type(NULL, params, results, @@ -1624,11 +1619,11 @@ Type::make_type_descriptor_type() "size", uintptr_type, "ptrdata", uintptr_type, "hash", uint32_type, - "kind", uint8_type, + "tflag", uint8_type, "align", uint8_type, "fieldAlign", uint8_type, - "hashfn", hash_fntype, - "equalfn", equal_fntype, + "kind", uint8_type, + "equal", equal_fntype, "gcdata", pointer_uint8_type, "string", pointer_string_type, "", pointer_uncommon_type, @@ -1741,18 +1736,13 @@ Type::needs_specific_type_functions(Gogo* gogo) } // Return the runtime function that computes the hash of this type. -// If NAME is not NULL it is the name of this type. HASH_FNTYPE is -// the type of the hash function function, for convenience; it may be -// NULL. This returns NULL if the type is not comparable. +// HASH_FNTYPE is the type of the hash function function, for +// convenience; it may be NULL. This returns NULL if the type is not +// comparable. Named_object* -Type::hash_function(Gogo* gogo, Named_type* name, Function_type* hash_fntype) +Type::hash_function(Gogo* gogo, Function_type* hash_fntype) { - // If the unaliased type is not a named type, then the type does not - // have a name after all. - if (name != NULL) - name = name->unalias()->named_type(); - if (!this->is_comparable()) return NULL; @@ -1803,7 +1793,7 @@ Type::hash_function(Gogo* gogo, Named_type* name, Function_type* hash_fntype) // We don't have a built-in function for a type of this // size. Build a function to use that calls the generic // hash functions for identity, passing the size. - return this->build_hash_function(gogo, name, size, hash_fntype); + return this->build_hash_function(gogo, size, hash_fntype); } } else @@ -1861,7 +1851,7 @@ Type::hash_function(Gogo* gogo, Named_type* name, Function_type* hash_fntype) // This is a struct which can not be compared using a simple // identity function. We need to build a function to // compute the hash. - return this->build_hash_function(gogo, name, -1, hash_fntype); + return this->build_hash_function(gogo, -1, hash_fntype); case Type::TYPE_ARRAY: if (this->is_slice_type()) @@ -1875,7 +1865,7 @@ Type::hash_function(Gogo* gogo, Named_type* name, Function_type* hash_fntype) // This is an array which can not be compared using a // simple identity function. We need to build a // function to compute the hash. - return this->build_hash_function(gogo, name, -1, hash_fntype); + return this->build_hash_function(gogo, -1, hash_fntype); } break; @@ -1895,7 +1885,6 @@ Type::hash_function(Gogo* gogo, Named_type* name, Function_type* hash_fntype) } } - Location bloc = Linemap::predeclared_location(); Named_object *hash_fn = Named_object::make_function_declaration(hash_fnname, NULL, @@ -1913,12 +1902,20 @@ Type::Type_function Type::type_hash_functions_table; // this is a struct or array type that cannot use an identity // comparison. Otherwise, it is a type that uses an identity // comparison but is not one of the standard supported sizes. +// +// Unlike an equality function, hash functions are not in type +// descriptors, so we can't assume that a named type has defined a +// hash function in the package that defines the type. So hash +// functions are always defined locally. FIXME: It would be better to +// define hash functions with comdat linkage so that duplicate hash +// functions can be coalesced at link time. Named_object* -Type::build_hash_function(Gogo* gogo, Named_type* name, int64_t size, - Function_type* hash_fntype) +Type::build_hash_function(Gogo* gogo, int64_t size, Function_type* hash_fntype) { - std::pair<Type*, Named_object*> val(name != NULL ? name : this, NULL); + Type* type = this->base(); + + std::pair<Type*, Named_object*> val(type, NULL); std::pair<Type_function::iterator, bool> ins = Type::type_hash_functions_table.insert(val); if (!ins.second) @@ -1927,30 +1924,19 @@ Type::build_hash_function(Gogo* gogo, Named_type* name, int64_t size, return ins.first->second; } - std::string hash_name = gogo->hash_function_name(this, name); + std::string hash_name = gogo->hash_function_name(type); Location bloc = Linemap::predeclared_location(); - const Package* package = NULL; - bool is_defined_elsewhere = - this->type_descriptor_defined_elsewhere(name, &package); - - Named_object* hash_fn; - if (is_defined_elsewhere) - hash_fn = Named_object::make_function_declaration(hash_name, package, - hash_fntype, bloc); - else - hash_fn = gogo->declare_package_function(hash_name, hash_fntype, bloc); + Named_object* hash_fn = gogo->declare_package_function(hash_name, + hash_fntype, bloc); ins.first->second = hash_fn; - if (!is_defined_elsewhere) - { - if (gogo->in_global_scope()) - this->write_hash_function(gogo, name, size, hash_name, hash_fntype); - else - gogo->queue_hash_function(this, name, size, hash_name, hash_fntype); - } + if (gogo->in_global_scope()) + type->write_hash_function(gogo, size, hash_name, hash_fntype); + else + gogo->queue_hash_function(type, size, hash_name, hash_fntype); return hash_fn; } @@ -1958,7 +1944,7 @@ Type::build_hash_function(Gogo* gogo, Named_type* name, int64_t size, // Write the hash function for a type that needs it written specially. void -Type::write_hash_function(Gogo* gogo, Named_type* name, int64_t size, +Type::write_hash_function(Gogo* gogo, int64_t size, const std::string& hash_name, Function_type* hash_fntype) { @@ -1979,12 +1965,10 @@ Type::write_hash_function(Gogo* gogo, Named_type* name, int64_t size, if (size != -1) this->write_identity_hash(gogo, size); - else if (name != NULL && name->real_type()->named_type() != NULL) - this->write_named_hash(gogo, name, hash_fntype); else if (this->struct_type() != NULL) - this->struct_type()->write_hash_function(gogo, name, hash_fntype); + this->struct_type()->write_hash_function(gogo, hash_fntype); else if (this->array_type() != NULL) - this->array_type()->write_hash_function(gogo, name, hash_fntype); + this->array_type()->write_hash_function(gogo, hash_fntype); else go_unreachable(); @@ -2052,54 +2036,6 @@ Type::write_identity_hash(Gogo* gogo, int64_t size) gogo->add_statement(s); } -// Write a hash function that simply calls the hash function for a -// named type. This is used when one named type is defined as -// another. This ensures that this case works when the other named -// type is defined in another package and relies on calling hash -// functions defined only in that package. - -void -Type::write_named_hash(Gogo* gogo, Named_type* name, - Function_type* hash_fntype) -{ - Location bloc = Linemap::predeclared_location(); - - Named_type* base_type = name->real_type()->named_type(); - while (base_type->is_alias()) - { - base_type = base_type->real_type()->named_type(); - go_assert(base_type != NULL); - } - go_assert(base_type != NULL); - - // The pointer to the type we are going to hash. This is an - // unsafe.Pointer. - Named_object* key_arg = gogo->lookup("key", NULL); - go_assert(key_arg != NULL); - - // The seed argument to the hash function. - Named_object* seed_arg = gogo->lookup("seed", NULL); - go_assert(seed_arg != NULL); - - Named_object* hash_fn = name->real_type()->hash_function(gogo, base_type, - hash_fntype); - - // Call the hash function for the base type. - Expression* key_ref = Expression::make_var_reference(key_arg, bloc); - Expression* seed_ref = Expression::make_var_reference(seed_arg, bloc); - Expression_list* args = new Expression_list(); - args->push_back(key_ref); - args->push_back(seed_ref); - Expression* func = Expression::make_func_reference(hash_fn, NULL, bloc); - Expression* call = Expression::make_call(func, args, false, bloc); - - // Return the hash of the base type. - Expression_list* vals = new Expression_list(); - vals->push_back(call); - Statement* s = Statement::make_return_statement(vals, bloc); - gogo->add_statement(s); -} - // Return the runtime function that compares whether two values of // this type are equal. If NAME is not NULL it is the name of this // type. EQUAL_FNTYPE is the type of the equality function, for @@ -2572,9 +2508,11 @@ Type::type_descriptor_constructor(Gogo* gogo, int runtime_type_kind, vals->push_back(Expression::make_integer_ul(h, p->type(), bloc)); ++p; - go_assert(p->is_field_name("kind")); - vals->push_back(Expression::make_integer_ul(runtime_type_kind, p->type(), - bloc)); + go_assert(p->is_field_name("tflag")); + unsigned long tflag = 0; + if (this->compare_is_identity(gogo)) + tflag |= TFLAG_REGULAR_MEMORY; + vals->push_back(Expression::make_integer_ul(tflag, p->type(), bloc)); ++p; go_assert(p->is_field_name("align")); @@ -2587,18 +2525,12 @@ Type::type_descriptor_constructor(Gogo* gogo, int runtime_type_kind, vals->push_back(Expression::make_type_info(this, type_info)); ++p; - go_assert(p->is_field_name("hashfn")); - Function_type* hash_fntype = p->type()->function_type(); - Named_object* hash_fn = this->hash_function(gogo, name, hash_fntype); - if (hash_fn == NULL) - vals->push_back(Expression::make_cast(hash_fntype, - Expression::make_nil(bloc), - bloc)); - else - vals->push_back(Expression::make_func_reference(hash_fn, NULL, bloc)); + go_assert(p->is_field_name("kind")); + vals->push_back(Expression::make_integer_ul(runtime_type_kind, p->type(), + bloc)); ++p; - go_assert(p->is_field_name("equalfn")); + go_assert(p->is_field_name("equal")); Function_type* equal_fntype = p->type()->function_type(); Named_object* equal_fn = this->equal_function(gogo, name, equal_fntype); if (equal_fn == NULL) @@ -6603,8 +6535,7 @@ Struct_type::do_type_descriptor(Gogo* gogo, Named_type* name) // function. void -Struct_type::write_hash_function(Gogo* gogo, Named_type*, - Function_type* hash_fntype) +Struct_type::write_hash_function(Gogo* gogo, Function_type* hash_fntype) { Location bloc = Linemap::predeclared_location(); @@ -6650,8 +6581,7 @@ Struct_type::write_hash_function(Gogo* gogo, Named_type*, subkey = Expression::make_cast(key_arg_type, subkey, bloc); // Get the hash function to use for the type of this field. - Named_object* hash_fn = - pf->type()->hash_function(gogo, pf->type()->named_type(), hash_fntype); + Named_object* hash_fn = pf->type()->hash_function(gogo, hash_fntype); // Call the hash function for the field, passing retval as the seed. ref = Expression::make_temporary_reference(retval, bloc); @@ -7447,8 +7377,7 @@ Array_type::do_hash_for_method(Gogo* gogo, int flags) const // function. void -Array_type::write_hash_function(Gogo* gogo, Named_type* name, - Function_type* hash_fntype) +Array_type::write_hash_function(Gogo* gogo, Function_type* hash_fntype) { Location bloc = Linemap::predeclared_location(); @@ -7485,9 +7414,7 @@ Array_type::write_hash_function(Gogo* gogo, Named_type* name, Expression* iref = Expression::make_temporary_reference(index, bloc); Expression* aref = Expression::make_var_reference(key_arg, bloc); - Type* pt = Type::make_pointer_type(name != NULL - ? static_cast<Type*>(name) - : static_cast<Type*>(this)); + Type* pt = Type::make_pointer_type(static_cast<Type*>(this)); aref = Expression::make_cast(pt, aref, bloc); For_range_statement* for_range = Statement::make_for_range_statement(iref, NULL, @@ -7497,9 +7424,8 @@ Array_type::write_hash_function(Gogo* gogo, Named_type* name, gogo->start_block(bloc); // Get the hash function for the element type. - Named_object* hash_fn = - this->element_type_->hash_function(gogo, this->element_type_->named_type(), - hash_fntype); + Named_object* hash_fn = this->element_type_->hash_function(gogo, + hash_fntype); // Get a pointer to this element in the loop. Expression* subkey = Expression::make_temporary_reference(key, bloc); @@ -8291,13 +8217,28 @@ Map_type::make_map_type_descriptor_type() Type* uint8_type = Type::lookup_integer_type("uint8"); Type* uint16_type = Type::lookup_integer_type("uint16"); Type* uint32_type = Type::lookup_integer_type("uint32"); + Type* uintptr_type = Type::lookup_integer_type("uintptr"); + Type* void_type = Type::make_void_type(); + Type* unsafe_pointer_type = Type::make_pointer_type(void_type); + + Location bloc = Linemap::predeclared_location(); + Typed_identifier_list *params = new Typed_identifier_list(); + params->push_back(Typed_identifier("key", unsafe_pointer_type, bloc)); + params->push_back(Typed_identifier("seed", uintptr_type, bloc)); + + Typed_identifier_list* results = new Typed_identifier_list(); + results->push_back(Typed_identifier("", uintptr_type, bloc)); + + Type* hasher_fntype = Type::make_function_type(NULL, params, results, + bloc); Struct_type* sf = - Type::make_builtin_struct_type(8, + Type::make_builtin_struct_type(9, "", tdt, "key", ptdt, "elem", ptdt, "bucket", ptdt, + "hasher", hasher_fntype, "keysize", uint8_type, "valuesize", uint8_type, "bucketsize", uint16_type, @@ -8380,6 +8321,18 @@ Map_type::do_type_descriptor(Gogo* gogo, Named_type* name) vals->push_back(Expression::make_type_descriptor(bucket_type, bloc)); ++p; + go_assert(p->is_field_name("hasher")); + Function_type* hasher_fntype = p->type()->function_type(); + Named_object* hasher_fn = this->key_type_->hash_function(gogo, + hasher_fntype); + if (hasher_fn == NULL) + vals->push_back(Expression::make_cast(hasher_fntype, + Expression::make_nil(bloc), + bloc)); + else + vals->push_back(Expression::make_func_reference(hasher_fn, NULL, bloc)); + + ++p; go_assert(p->is_field_name("keysize")); if (keysize > Map_type::max_key_size) vals->push_back(Expression::make_integer_int64(ptrsize, uint8_type, bloc)); diff --git a/gcc/go/gofrontend/types.h b/gcc/go/gofrontend/types.h index 55c5912..ef81589 100644 --- a/gcc/go/gofrontend/types.h +++ b/gcc/go/gofrontend/types.h @@ -1061,7 +1061,7 @@ class Type // Get the hash function for a type. Returns NULL if the type is // not comparable. Named_object* - hash_function(Gogo*, Named_type* name, Function_type* hash_fntype); + hash_function(Gogo*, Function_type* hash_fntype); // Write the equal function for a type. void @@ -1071,8 +1071,7 @@ class Type // Write the hash function for a type. void - write_hash_function(Gogo*, Named_type*, int64_t size, - const std::string& hash_name, + write_hash_function(Gogo*, int64_t size, const std::string& hash_name, Function_type* hash_fntype); // Return the alignment required by the memequalN function. @@ -1284,8 +1283,7 @@ class Type // Build the hash function for a type that needs specific functions. Named_object* - build_hash_function(Gogo*, Named_type*, int64_t size, - Function_type* hash_fntype); + build_hash_function(Gogo*, int64_t size, Function_type* hash_fntype); // Build the equal function for a type that needs specific functions. Named_object* @@ -1299,9 +1297,6 @@ class Type write_identity_equal(Gogo*, int64_t size); void - write_named_hash(Gogo*, Named_type*, Function_type* hash_fntype); - - void write_named_equal(Gogo*, Named_type*); // Build a composite literal for the uncommon type information. @@ -2628,7 +2623,7 @@ class Struct_type : public Type // Write the hash function for this type. void - write_hash_function(Gogo*, Named_type*, Function_type*); + write_hash_function(Gogo*, Function_type*); // Write the equality function for this type. void @@ -2815,7 +2810,7 @@ class Array_type : public Type // Write the hash function for this type. void - write_hash_function(Gogo*, Named_type*, Function_type*); + write_hash_function(Gogo*, Function_type*); // Write the equality function for this type. void |