From f9f96987536295eb79dafb3274ad578679a2eaee Mon Sep 17 00:00:00 2001 From: Ian Lance Taylor Date: Fri, 6 Jan 2012 21:47:49 +0000 Subject: compiler, runtime: Implement struct and array comparisons. From-SVN: r182971 --- gcc/go/gofrontend/backend.h | 10 +- gcc/go/gofrontend/expressions.cc | 335 +++++++++++-- gcc/go/gofrontend/expressions.h | 86 ++++ gcc/go/gofrontend/go.cc | 3 + gcc/go/gofrontend/gogo-tree.cc | 15 +- gcc/go/gofrontend/gogo.cc | 56 +++ gcc/go/gofrontend/gogo.h | 44 ++ gcc/go/gofrontend/runtime.def | 3 + gcc/go/gofrontend/types.cc | 1005 +++++++++++++++++++++++++++++++++----- gcc/go/gofrontend/types.h | 148 +++++- 10 files changed, 1530 insertions(+), 175 deletions(-) (limited to 'gcc/go') diff --git a/gcc/go/gofrontend/backend.h b/gcc/go/gofrontend/backend.h index 24a0132..382f5a1 100644 --- a/gcc/go/gofrontend/backend.h +++ b/gcc/go/gofrontend/backend.h @@ -379,9 +379,9 @@ class Backend // must be a pointer to this struct type. // // We must create the named structure before we know its - // initializer, because the initializer refer to its own address. - // After calling this the frontend will call - // set_immutable_struct_initializer. + // initializer, because the initializer may refer to its own + // address. After calling this the frontend will call + // immutable_struct_set_init. virtual Bvariable* immutable_struct(const std::string& name, bool is_common, Btype* type, Location) = 0; @@ -400,8 +400,8 @@ class Backend // Create a reference to a named immutable initialized data // structure defined in some other package. This will be a - // structure created by a call to immutable_struct_expression with - // the same NAME and TYPE and with IS_COMMON passed as false. This + // structure created by a call to immutable_struct with the same + // NAME and TYPE and with IS_COMMON passed as false. This // corresponds to an extern const global variable in C. virtual Bvariable* immutable_struct_reference(const std::string& name, Btype* type, diff --git a/gcc/go/gofrontend/expressions.cc b/gcc/go/gofrontend/expressions.cc index dfe9b51..84c18a3 100644 --- a/gcc/go/gofrontend/expressions.cc +++ b/gcc/go/gofrontend/expressions.cc @@ -1135,6 +1135,63 @@ Expression::make_temporary_reference(Temporary_statement* statement, return new Temporary_reference_expression(statement, location); } +// Class Set_and_use_temporary_expression. + +// Return the type. + +Type* +Set_and_use_temporary_expression::do_type() +{ + return this->statement_->type(); +} + +// Take the address. + +void +Set_and_use_temporary_expression::do_address_taken(bool) +{ + this->statement_->set_is_address_taken(); +} + +// Return the backend representation. + +tree +Set_and_use_temporary_expression::do_get_tree(Translate_context* context) +{ + Bvariable* bvar = this->statement_->get_backend_variable(context); + tree var_tree = var_to_tree(bvar); + tree expr_tree = this->expr_->get_tree(context); + if (var_tree == error_mark_node || expr_tree == error_mark_node) + return error_mark_node; + Location loc = this->location(); + return build2_loc(loc.gcc_location(), COMPOUND_EXPR, TREE_TYPE(var_tree), + build2_loc(loc.gcc_location(), MODIFY_EXPR, void_type_node, + var_tree, expr_tree), + var_tree); +} + +// Dump. + +void +Set_and_use_temporary_expression::do_dump_expression( + Ast_dump_context* ast_dump_context) const +{ + ast_dump_context->ostream() << '('; + ast_dump_context->dump_temp_variable_name(this->statement_); + ast_dump_context->ostream() << " = "; + this->expr_->dump_expression(ast_dump_context); + ast_dump_context->ostream() << ')'; +} + +// Make a set-and-use temporary. + +Set_and_use_temporary_expression* +Expression::make_set_and_use_temporary(Temporary_statement* statement, + Expression* expr, Location location) +{ + return new Set_and_use_temporary_expression(statement, expr, location); +} + // A sink expression--a use of the blank identifier _. class Sink_expression : public Expression @@ -4468,11 +4525,38 @@ Unary_expression::do_check_types(Gogo*) tree Unary_expression::do_get_tree(Translate_context* context) { + Location loc = this->location(); + + // Taking the address of a set-and-use-temporary expression requires + // setting the temporary and then taking the address. + if (this->op_ == OPERATOR_AND) + { + Set_and_use_temporary_expression* sut = + this->expr_->set_and_use_temporary_expression(); + if (sut != NULL) + { + Temporary_statement* temp = sut->temporary(); + Bvariable* bvar = temp->get_backend_variable(context); + tree var_tree = var_to_tree(bvar); + Expression* val = sut->expression(); + tree val_tree = val->get_tree(context); + if (var_tree == error_mark_node || val_tree == error_mark_node) + return error_mark_node; + tree addr_tree = build_fold_addr_expr_loc(loc.gcc_location(), + var_tree); + return build2_loc(loc.gcc_location(), COMPOUND_EXPR, + TREE_TYPE(addr_tree), + build2_loc(sut->location().gcc_location(), + MODIFY_EXPR, void_type_node, + var_tree, val_tree), + addr_tree); + } + } + tree expr = this->expr_->get_tree(context); if (expr == error_mark_node) return error_mark_node; - Location loc = this->location(); switch (this->op_) { case OPERATOR_PLUS: @@ -5398,7 +5482,8 @@ Binary_expression::eval_complex(Operator op, Type* left_type, // constants. Expression* -Binary_expression::do_lower(Gogo*, Named_object*, Statement_inserter*, int) +Binary_expression::do_lower(Gogo* gogo, Named_object*, + Statement_inserter* inserter, int) { Location location = this->location(); Operator op = this->op_; @@ -5727,9 +5812,183 @@ Binary_expression::do_lower(Gogo*, Named_object*, Statement_inserter*, int) mpz_clear(right_val); } + // Lower struct and array comparisons. + if (op == OPERATOR_EQEQ || op == OPERATOR_NOTEQ) + { + if (left->type()->struct_type() != NULL) + return this->lower_struct_comparison(gogo, inserter); + else if (left->type()->array_type() != NULL + && !left->type()->is_slice_type()) + return this->lower_array_comparison(gogo, inserter); + } + return this; } +// Lower a struct comparison. + +Expression* +Binary_expression::lower_struct_comparison(Gogo* gogo, + Statement_inserter* inserter) +{ + Struct_type* st = this->left_->type()->struct_type(); + Struct_type* st2 = this->right_->type()->struct_type(); + if (st2 == NULL) + return this; + if (st != st2 && !Type::are_identical(st, st2, false, NULL)) + return this; + if (!Type::are_compatible_for_comparison(true, this->left_->type(), + this->right_->type(), NULL)) + return this; + + // See if we can compare using memcmp. As a heuristic, we use + // memcmp rather than field references and comparisons if there are + // more than two fields. + if (st->compare_is_identity() && st->total_field_count() > 2) + return this->lower_compare_to_memcmp(gogo, inserter); + + Location loc = this->location(); + + Expression* left = this->left_; + Temporary_statement* left_temp = NULL; + if (left->var_expression() == NULL + && left->temporary_reference_expression() == NULL) + { + left_temp = Statement::make_temporary(left->type(), NULL, loc); + inserter->insert(left_temp); + left = Expression::make_set_and_use_temporary(left_temp, left, loc); + } + + Expression* right = this->right_; + Temporary_statement* right_temp = NULL; + if (right->var_expression() == NULL + && right->temporary_reference_expression() == NULL) + { + right_temp = Statement::make_temporary(right->type(), NULL, loc); + inserter->insert(right_temp); + right = Expression::make_set_and_use_temporary(right_temp, right, loc); + } + + Expression* ret = Expression::make_boolean(true, loc); + const Struct_field_list* fields = st->fields(); + unsigned int field_index = 0; + for (Struct_field_list::const_iterator pf = fields->begin(); + pf != fields->end(); + ++pf, ++field_index) + { + if (field_index > 0) + { + if (left_temp == NULL) + left = left->copy(); + else + left = Expression::make_temporary_reference(left_temp, loc); + if (right_temp == NULL) + right = right->copy(); + else + right = Expression::make_temporary_reference(right_temp, loc); + } + Expression* f1 = Expression::make_field_reference(left, field_index, + loc); + Expression* f2 = Expression::make_field_reference(right, field_index, + loc); + Expression* cond = Expression::make_binary(OPERATOR_EQEQ, f1, f2, loc); + ret = Expression::make_binary(OPERATOR_ANDAND, ret, cond, loc); + } + + if (this->op_ == OPERATOR_NOTEQ) + ret = Expression::make_unary(OPERATOR_NOT, ret, loc); + + return ret; +} + +// Lower an array comparison. + +Expression* +Binary_expression::lower_array_comparison(Gogo* gogo, + Statement_inserter* inserter) +{ + Array_type* at = this->left_->type()->array_type(); + Array_type* at2 = this->right_->type()->array_type(); + if (at2 == NULL) + return this; + if (at != at2 && !Type::are_identical(at, at2, false, NULL)) + return this; + if (!Type::are_compatible_for_comparison(true, this->left_->type(), + this->right_->type(), NULL)) + return this; + + // Call memcmp directly if possible. This may let the middle-end + // optimize the call. + if (at->compare_is_identity()) + return this->lower_compare_to_memcmp(gogo, inserter); + + // Call the array comparison function. + Named_object* hash_fn; + Named_object* equal_fn; + at->type_functions(gogo, this->left_->type()->named_type(), NULL, NULL, + &hash_fn, &equal_fn); + + Location loc = this->location(); + + Expression* func = Expression::make_func_reference(equal_fn, NULL, loc); + + Expression_list* args = new Expression_list(); + args->push_back(this->operand_address(inserter, this->left_)); + args->push_back(this->operand_address(inserter, this->right_)); + args->push_back(Expression::make_type_info(at, TYPE_INFO_SIZE)); + + Expression* ret = Expression::make_call(func, args, false, loc); + + if (this->op_ == OPERATOR_NOTEQ) + ret = Expression::make_unary(OPERATOR_NOT, ret, loc); + + return ret; +} + +// Lower a struct or array comparison to a call to memcmp. + +Expression* +Binary_expression::lower_compare_to_memcmp(Gogo*, Statement_inserter* inserter) +{ + Location loc = this->location(); + + Expression* a1 = this->operand_address(inserter, this->left_); + Expression* a2 = this->operand_address(inserter, this->right_); + Expression* len = Expression::make_type_info(this->left_->type(), + TYPE_INFO_SIZE); + + Expression* call = Runtime::make_call(Runtime::MEMCMP, loc, 3, a1, a2, len); + + mpz_t zval; + mpz_init_set_ui(zval, 0); + Expression* zero = Expression::make_integer(&zval, NULL, loc); + mpz_clear(zval); + + return Expression::make_binary(this->op_, call, zero, loc); +} + +// Return the address of EXPR, cast to unsafe.Pointer. + +Expression* +Binary_expression::operand_address(Statement_inserter* inserter, + Expression* expr) +{ + Location loc = this->location(); + + if (!expr->is_addressable()) + { + Temporary_statement* temp = Statement::make_temporary(expr->type(), NULL, + loc); + inserter->insert(temp); + expr = Expression::make_set_and_use_temporary(temp, expr, loc); + } + expr = Expression::make_unary(OPERATOR_AND, expr, loc); + static_cast(expr)->set_does_not_escape(); + Type* void_type = Type::make_void_type(); + Type* unsafe_pointer_type = Type::make_pointer_type(void_type); + return Expression::make_cast(unsafe_pointer_type, expr, loc); +} + // Return the integer constant value, if it has one. bool @@ -6072,49 +6331,28 @@ Binary_expression::check_operator_type(Operator op, Type* type, Type* otype, case OPERATOR_EQEQ: case OPERATOR_NOTEQ: - if (type->integer_type() == NULL - && type->float_type() == NULL - && type->complex_type() == NULL - && !type->is_string_type() - && type->points_to() == NULL - && !type->is_nil_type() - && !type->is_boolean_type() - && type->interface_type() == NULL - && (type->array_type() == NULL - || type->array_type()->length() != NULL) - && type->map_type() == NULL - && type->channel_type() == NULL - && type->function_type() == NULL) - { - error_at(location, - ("expected integer, floating, complex, string, pointer, " - "boolean, interface, slice, map, channel, " - "or function type")); - return false; - } - if ((type->is_slice_type() - || type->map_type() != NULL - || type->function_type() != NULL) - && !otype->is_nil_type()) - { - error_at(location, - ("slice, map, and function types may only " - "be compared to nil")); - return false; - } + { + std::string reason; + if (!Type::are_compatible_for_comparison(true, type, otype, &reason)) + { + error_at(location, "%s", reason.c_str()); + return false; + } + } break; case OPERATOR_LT: case OPERATOR_LE: case OPERATOR_GT: case OPERATOR_GE: - if (type->integer_type() == NULL - && type->float_type() == NULL - && !type->is_string_type()) - { - error_at(location, "expected integer, floating, or string type"); - return false; - } + { + std::string reason; + if (!Type::are_compatible_for_comparison(false, type, otype, &reason)) + { + error_at(location, "%s", reason.c_str()); + return false; + } + } break; case OPERATOR_PLUS: @@ -12740,10 +12978,10 @@ class Composite_literal_expression : public Parser_expression lower_struct(Gogo*, Type*); Expression* - lower_array(Type*); + lower_array(Gogo*, Type*); Expression* - make_array(Type*, Expression_list*); + make_array(Gogo*, Type*, Expression_list*); Expression* lower_map(Gogo*, Named_object*, Statement_inserter*, Type*); @@ -12810,7 +13048,7 @@ Composite_literal_expression::do_lower(Gogo* gogo, Named_object* function, else if (type->struct_type() != NULL) ret = this->lower_struct(gogo, type); else if (type->array_type() != NULL) - ret = this->lower_array(type); + ret = this->lower_array(gogo, type); else if (type->map_type() != NULL) ret = this->lower_map(gogo, function, inserter, type); else @@ -13023,11 +13261,11 @@ Composite_literal_expression::lower_struct(Gogo* gogo, Type* type) // Lower an array composite literal. Expression* -Composite_literal_expression::lower_array(Type* type) +Composite_literal_expression::lower_array(Gogo* gogo, Type* type) { Location location = this->location(); if (this->vals_ == NULL || !this->has_keys_) - return this->make_array(type, this->vals_); + return this->make_array(gogo, type, this->vals_); std::vector vals; vals.reserve(this->vals_->size()); @@ -13127,14 +13365,15 @@ Composite_literal_expression::lower_array(Type* type) for (size_t i = 0; i < size; ++i) list->push_back(vals[i]); - return this->make_array(type, list); + return this->make_array(gogo, type, list); } // Actually build the array composite literal. This handles // [...]{...}. Expression* -Composite_literal_expression::make_array(Type* type, Expression_list* vals) +Composite_literal_expression::make_array(Gogo* gogo, Type* type, + Expression_list* vals) { Location location = this->location(); Array_type* at = type->array_type(); @@ -13146,6 +13385,10 @@ Composite_literal_expression::make_array(Type* type, Expression_list* vals) Expression* elen = Expression::make_integer(&vlen, NULL, location); mpz_clear(vlen); at = Type::make_array_type(at->element_type(), elen); + + // This is after the finalize_methods pass, so run that now. + at->finalize_methods(gogo); + type = at; } if (at->length() != NULL) diff --git a/gcc/go/gofrontend/expressions.h b/gcc/go/gofrontend/expressions.h index 4e06b24..668f8a1 100644 --- a/gcc/go/gofrontend/expressions.h +++ b/gcc/go/gofrontend/expressions.h @@ -25,6 +25,7 @@ class Struct_field; class Expression_list; class Var_expression; class Temporary_reference_expression; +class Set_and_use_temporary_expression; class String_expression; class Binary_expression; class Call_expression; @@ -60,6 +61,7 @@ class Expression EXPRESSION_CONST_REFERENCE, EXPRESSION_VAR_REFERENCE, EXPRESSION_TEMPORARY_REFERENCE, + EXPRESSION_SET_AND_USE_TEMPORARY, EXPRESSION_SINK, EXPRESSION_FUNC_REFERENCE, EXPRESSION_UNKNOWN_REFERENCE, @@ -134,6 +136,13 @@ class Expression static Temporary_reference_expression* make_temporary_reference(Temporary_statement*, Location); + // Make an expressions which sets a temporary variable and then + // evaluates to a reference to that temporary variable. This is + // used to set a temporary variable while retaining the order of + // evaluation. + static Set_and_use_temporary_expression* + make_set_and_use_temporary(Temporary_statement*, Expression*, Location); + // Make a sink expression--a reference to the blank identifier _. static Expression* make_sink(Location); @@ -396,6 +405,15 @@ class Expression EXPRESSION_TEMPORARY_REFERENCE>(); } + // If this is a set-and-use-temporary, return the + // Set_and_use_temporary_expression. Otherwise, return NULL. + Set_and_use_temporary_expression* + set_and_use_temporary_expression() + { + return this->convert(); + } + // Return whether this is a sink expression. bool is_sink_expression() const @@ -1021,6 +1039,62 @@ class Temporary_reference_expression : public Expression bool is_lvalue_; }; +// Set and use a temporary variable. + +class Set_and_use_temporary_expression : public Expression +{ + public: + Set_and_use_temporary_expression(Temporary_statement* statement, + Expression* expr, Location location) + : Expression(EXPRESSION_SET_AND_USE_TEMPORARY, location), + statement_(statement), expr_(expr) + { } + + // Return the temporary. + Temporary_statement* + temporary() const + { return this->statement_; } + + // Return the expression. + Expression* + expression() const + { return this->expr_; } + + protected: + Type* + do_type(); + + void + do_determine_type(const Type_context*) + { } + + Expression* + do_copy() + { + return make_set_and_use_temporary(this->statement_, this->expr_, + this->location()); + } + + bool + do_is_addressable() const + { return true; } + + void + do_address_taken(bool); + + tree + do_get_tree(Translate_context*); + + void + do_dump_expression(Ast_dump_context*) const; + + private: + // The statement where the temporary variable is defined. + Temporary_statement* statement_; + // The expression to assign to the temporary. + Expression* expr_; +}; + // A string expression. class String_expression : public Expression @@ -1200,6 +1274,18 @@ class Binary_expression : public Expression do_dump_expression(Ast_dump_context*) const; private: + Expression* + lower_struct_comparison(Gogo*, Statement_inserter*); + + Expression* + lower_array_comparison(Gogo*, Statement_inserter*); + + Expression* + lower_compare_to_memcmp(Gogo*, Statement_inserter*); + + Expression* + operand_address(Statement_inserter*, Expression*); + // The binary operator to apply. Operator op_; // The left hand side operand. diff --git a/gcc/go/gofrontend/go.cc b/gcc/go/gofrontend/go.cc index 39af549..bfa3afd 100644 --- a/gcc/go/gofrontend/go.cc +++ b/gcc/go/gofrontend/go.cc @@ -106,6 +106,9 @@ go_parse_input_files(const char** filenames, unsigned int filename_count, // form which is easier to use. ::gogo->lower_parse_tree(); + // Write out queued up functions for hash and comparison of types. + ::gogo->write_specific_type_functions(); + // Now that we have seen all the names, verify that types are // correct. ::gogo->verify_types(); diff --git a/gcc/go/gofrontend/gogo-tree.cc b/gcc/go/gofrontend/gogo-tree.cc index dd66a7f..0a7cd56 100644 --- a/gcc/go/gofrontend/gogo-tree.cc +++ b/gcc/go/gofrontend/gogo-tree.cc @@ -116,10 +116,10 @@ Gogo::define_builtin_function_trees() NULL_TREE), true); - // We use __builtin_memmove for the predeclared copy function. - define_builtin(BUILT_IN_MEMMOVE, "__builtin_memmove", "memmove", - build_function_type_list(ptr_type_node, - ptr_type_node, + // We use __builtin_memcmp for struct comparisons. + define_builtin(BUILT_IN_MEMCMP, "__builtin_memcmp", "memcmp", + build_function_type_list(integer_type_node, + const_ptr_type_node, const_ptr_type_node, size_type_node, NULL_TREE), @@ -647,7 +647,8 @@ Gogo::write_globals() this->build_interface_method_tables(); Bindings* bindings = this->current_bindings(); - size_t count = bindings->size_definitions(); + size_t count_definitions = bindings->size_definitions(); + size_t count = count_definitions; tree* vec = new tree[count]; @@ -822,6 +823,10 @@ Gogo::write_globals() || this->is_main_package()) this->write_initialization_function(init_fndecl, init_stmt_list); + // We should not have seen any new bindings created during the + // conversion. + go_assert(count_definitions == this->current_bindings()->size_definitions()); + // Pass everything back to the middle-end. wrapup_global_declarations(vec, count); diff --git a/gcc/go/gofrontend/gogo.cc b/gcc/go/gofrontend/gogo.cc index dc5ac75..eb24947 100644 --- a/gcc/go/gofrontend/gogo.cc +++ b/gcc/go/gofrontend/gogo.cc @@ -38,6 +38,8 @@ Gogo::Gogo(Backend* backend, Linemap* linemap, int int_type_size, unique_prefix_(), unique_prefix_specified_(false), interface_types_(), + specific_type_functions_(), + specific_type_functions_are_written_(false), named_types_are_converted_(false) { const Location loc = Linemap::predeclared_location(); @@ -978,6 +980,16 @@ Gogo::declare_package_type(const std::string& name, Location location) return this->package_->bindings()->add_type_declaration(name, NULL, location); } +// Declare a function at the package level. + +Named_object* +Gogo::declare_package_function(const std::string& name, Function_type* type, + Location location) +{ + return this->package_->bindings()->add_function_declaration(name, NULL, type, + location); +} + // Define a type which was already declared. void @@ -1116,6 +1128,46 @@ Gogo::clear_file_scope() } } +// Queue up a type specific function for later writing. These are +// written out in write_specific_type_functions, called after the +// parse tree is lowered. + +void +Gogo::queue_specific_type_function(Type* type, Named_type* name, + const std::string& hash_name, + Function_type* hash_fntype, + const std::string& equal_name, + Function_type* equal_fntype) +{ + go_assert(!this->specific_type_functions_are_written_); + go_assert(!this->in_global_scope()); + Specific_type_function* tsf = new Specific_type_function(type, name, + hash_name, + hash_fntype, + equal_name, + equal_fntype); + this->specific_type_functions_.push_back(tsf); +} + +// Write out type specific functions. + +void +Gogo::write_specific_type_functions() +{ + while (!this->specific_type_functions_.empty()) + { + Specific_type_function* tsf = this->specific_type_functions_.back(); + this->specific_type_functions_.pop_back(); + tsf->type->write_specific_type_functions(this, tsf->name, + tsf->hash_name, + tsf->hash_fntype, + tsf->equal_name, + tsf->equal_fntype); + delete tsf; + } + this->specific_type_functions_are_written_ = true; +} + // Traverse the tree. void @@ -1468,6 +1520,10 @@ Finalize_methods::type(Type* t) t->struct_type()->finalize_methods(this->gogo_); break; + case Type::TYPE_ARRAY: + t->array_type()->finalize_methods(this->gogo_); + break; + default: break; } diff --git a/gcc/go/gofrontend/gogo.h b/gcc/go/gofrontend/gogo.h index 6efce18..ac1707a 100644 --- a/gcc/go/gofrontend/gogo.h +++ b/gcc/go/gofrontend/gogo.h @@ -277,6 +277,11 @@ class Gogo Named_object* declare_function(const std::string&, Function_type*, Location); + // Declare a function at the package level. This is used for + // functions generated for a type. + Named_object* + declare_package_function(const std::string&, Function_type*, Location); + // Add a label. Label* add_label_definition(const std::string&, Location); @@ -364,6 +369,20 @@ class Gogo void clear_file_scope(); + // Queue up a type-specific function to be written out. This is + // used when a type-specific function is needed when not at the top + // level. + void + queue_specific_type_function(Type* type, Named_type* name, + const std::string& hash_name, + Function_type* hash_fntype, + const std::string& equal_name, + Function_type* equal_fntype); + + // Write out queued specific type functions. + void + write_specific_type_functions(); + // Traverse the tree. See the Traverse class. void traverse(Traverse*); @@ -603,6 +622,27 @@ class Gogo // Type used to map special names in the sys package. typedef std::map Sys_names; + // Type used to queue writing a type specific function. + struct Specific_type_function + { + Type* type; + Named_type* name; + std::string hash_name; + Function_type* hash_fntype; + std::string equal_name; + Function_type* equal_fntype; + + Specific_type_function(Type* atype, Named_type* aname, + const std::string& ahash_name, + Function_type* ahash_fntype, + const std::string& aequal_name, + Function_type* aequal_fntype) + : type(atype), name(aname), hash_name(ahash_name), + hash_fntype(ahash_fntype), equal_name(aequal_name), + equal_fntype(aequal_fntype) + { } + }; + // The backend generator. Backend* backend_; // The object used to keep track of file names and line numbers. @@ -635,6 +675,10 @@ class Gogo bool unique_prefix_specified_; // A list of interface types defined while parsing. std::vector interface_types_; + // Type specific functions to write out. + std::vector specific_type_functions_; + // Whether we are done writing out specific type functions. + bool specific_type_functions_are_written_; // Whether named types have been converted. bool named_types_are_converted_; }; diff --git a/gcc/go/gofrontend/runtime.def b/gcc/go/gofrontend/runtime.def index fe842c9..438864c 100644 --- a/gcc/go/gofrontend/runtime.def +++ b/gcc/go/gofrontend/runtime.def @@ -28,6 +28,9 @@ // the name. The third is the parameter types and the fourth is the // result types. +// The standard C memcmp function, used for struct comparisons. +DEF_GO_RUNTIME(MEMCMP, "memcmp", P3(POINTER, POINTER, UINTPTR), R1(INT)) + // Range over a string, returning the next index. DEF_GO_RUNTIME(STRINGITER, "runtime.stringiter", P2(STRING, INT), R1(INT)) diff --git a/gcc/go/gofrontend/types.cc b/gcc/go/gofrontend/types.cc index d1901e1..334dc33 100644 --- a/gcc/go/gofrontend/types.cc +++ b/gcc/go/gofrontend/types.cc @@ -474,6 +474,115 @@ Type::are_compatible_for_binop(const Type* lhs, const Type* rhs) return false; } +// Return true if a value with type T1 may be compared with a value of +// type T2. IS_EQUALITY_OP is true for == or !=, false for <, etc. + +bool +Type::are_compatible_for_comparison(bool is_equality_op, const Type *t1, + const Type *t2, std::string *reason) +{ + if (t1 != t2 + && !Type::are_assignable(t1, t2, NULL) + && !Type::are_assignable(t2, t1, NULL)) + { + if (reason != NULL) + *reason = "incompatible types in binary expression"; + return false; + } + + if (!is_equality_op) + { + if (t1->integer_type() == NULL + && t1->float_type() == NULL + && !t1->is_string_type()) + { + if (reason != NULL) + *reason = _("invalid comparison of non-ordered type"); + return false; + } + } + else if (t1->is_slice_type() + || t1->map_type() != NULL + || t1->function_type() != NULL + || t2->is_slice_type() + || t2->map_type() != NULL + || t2->function_type() != NULL) + { + if (!t1->is_nil_type() && !t2->is_nil_type()) + { + if (reason != NULL) + { + if (t1->is_slice_type() || t2->is_slice_type()) + *reason = _("slice can only be compared to nil"); + else if (t1->map_type() != NULL || t2->map_type() != NULL) + *reason = _("map can only be compared to nil"); + else + *reason = _("func can only be compared to nil"); + + // Match 6g error messages. + if (t1->interface_type() != NULL || t2->interface_type() != NULL) + { + char buf[200]; + snprintf(buf, sizeof buf, _("invalid operation (%s)"), + reason->c_str()); + *reason = buf; + } + } + return false; + } + } + else + { + if (!t1->is_boolean_type() + && t1->integer_type() == NULL + && t1->float_type() == NULL + && t1->complex_type() == NULL + && !t1->is_string_type() + && t1->points_to() == NULL + && t1->channel_type() == NULL + && t1->interface_type() == NULL + && t1->struct_type() == NULL + && t1->array_type() == NULL + && !t1->is_nil_type()) + { + if (reason != NULL) + *reason = _("invalid comparison of non-comparable type"); + return false; + } + + if (t1->named_type() != NULL) + return t1->named_type()->named_type_is_comparable(reason); + else if (t2->named_type() != NULL) + return t2->named_type()->named_type_is_comparable(reason); + else if (t1->struct_type() != NULL) + { + const Struct_field_list* fields = t1->struct_type()->fields(); + for (Struct_field_list::const_iterator p = fields->begin(); + p != fields->end(); + ++p) + { + if (!p->type()->is_comparable()) + { + if (reason != NULL) + *reason = _("invalid comparison of non-comparable struct"); + return false; + } + } + } + else if (t1->array_type() != NULL) + { + if (!t1->array_type()->element_type()->is_comparable()) + { + if (reason != NULL) + *reason = _("invalid comparison of non-comparable array"); + return false; + } + } + } + + return true; +} + // Return true if a value with type RHS may be assigned to a variable // with type LHS. If CHECK_HIDDEN_FIELDS is true, check whether any // hidden fields are modified. If REASON is not NULL, set *REASON to @@ -897,44 +1006,17 @@ Type::make_type_descriptor_var(Gogo* gogo) phash = &ins.first->second; } - std::string var_name; - if (nt == NULL) - var_name = this->unnamed_type_descriptor_var_name(gogo); - else - var_name = this->type_descriptor_var_name(gogo); + std::string var_name = this->type_descriptor_var_name(gogo, nt); // Build the contents of the type descriptor. Expression* initializer = this->do_type_descriptor(gogo, NULL); Btype* initializer_btype = initializer->type()->get_backend(gogo); - // See if this type descriptor is defined in a different package. - bool is_defined_elsewhere = false; - if (nt != NULL) - { - if (nt->named_object()->package() != NULL) - { - // This is a named type defined in a different package. The - // type descriptor should be defined in that package. - is_defined_elsewhere = true; - } - } - else - { - if (this->points_to() != NULL - && this->points_to()->named_type() != NULL - && this->points_to()->named_type()->named_object()->package() != NULL) - { - // This is an unnamed pointer to a named type defined in a - // different package. The descriptor should be defined in - // that package. - is_defined_elsewhere = true; - } - } - Location loc = nt == NULL ? Linemap::predeclared_location() : nt->location(); - if (is_defined_elsewhere) + const Package* dummy; + if (this->type_descriptor_defined_elsewhere(nt, &dummy)) { this->type_descriptor_var_ = gogo->backend()->immutable_struct_reference(var_name, @@ -984,21 +1066,15 @@ Type::make_type_descriptor_var(Gogo* gogo) binitializer); } -// Return the name of the type descriptor variable for an unnamed -// type. +// Return the name of the type descriptor variable. If NT is not +// NULL, use it to get the name. Otherwise this is an unnamed type. std::string -Type::unnamed_type_descriptor_var_name(Gogo* gogo) +Type::type_descriptor_var_name(Gogo* gogo, Named_type* nt) { - return "__go_td_" + this->mangled_name(gogo); -} - -// Return the name of the type descriptor variable for a named type. + if (nt == NULL) + return "__go_td_" + this->mangled_name(gogo); -std::string -Type::type_descriptor_var_name(Gogo* gogo) -{ - Named_type* nt = this->named_type(); Named_object* no = nt->named_object(); const Named_object* in_function = nt->in_function(); std::string ret = "__go_tdn_"; @@ -1026,6 +1102,39 @@ Type::type_descriptor_var_name(Gogo* gogo) return ret; } +// Return true if this type descriptor is defined in a different +// package. If this returns true it sets *PACKAGE to the package. + +bool +Type::type_descriptor_defined_elsewhere(Named_type* nt, + const Package** package) +{ + if (nt != NULL) + { + if (nt->named_object()->package() != NULL) + { + // This is a named type defined in a different package. The + // type descriptor should be defined in that package. + *package = nt->named_object()->package(); + return true; + } + } + else + { + if (this->points_to() != NULL + && this->points_to()->named_type() != NULL + && this->points_to()->named_type()->named_object()->package() != NULL) + { + // This is an unnamed pointer to a named type defined in a + // different package. The descriptor should be defined in + // that package. + *package = this->points_to()->named_type()->named_object()->package(); + return true; + } + } + return false; +} + // Return a composite literal for a type descriptor. Expression* @@ -1157,8 +1266,8 @@ Type::make_type_descriptor_type() // The type descriptor type. Typed_identifier_list* params = new Typed_identifier_list(); - params->push_back(Typed_identifier("", unsafe_pointer_type, bloc)); - params->push_back(Typed_identifier("", uintptr_type, bloc)); + params->push_back(Typed_identifier("key", unsafe_pointer_type, bloc)); + params->push_back(Typed_identifier("key_size", uintptr_type, bloc)); Typed_identifier_list* results = new Typed_identifier_list(); results->push_back(Typed_identifier("", uintptr_type, bloc)); @@ -1166,9 +1275,9 @@ Type::make_type_descriptor_type() Type* hashfn_type = Type::make_function_type(NULL, params, results, bloc); params = new Typed_identifier_list(); - params->push_back(Typed_identifier("", unsafe_pointer_type, bloc)); - params->push_back(Typed_identifier("", unsafe_pointer_type, bloc)); - params->push_back(Typed_identifier("", uintptr_type, bloc)); + params->push_back(Typed_identifier("key1", unsafe_pointer_type, bloc)); + params->push_back(Typed_identifier("key2", unsafe_pointer_type, bloc)); + params->push_back(Typed_identifier("key_size", uintptr_type, bloc)); results = new Typed_identifier_list(); results->push_back(Typed_identifier("", Type::lookup_bool_type(), bloc)); @@ -1213,67 +1322,278 @@ Type::make_type_descriptor_ptr_type() return ret; } -// Return the names of runtime functions which compute a hash code for -// this type and which compare whether two values of this type are -// equal. +// Set *HASH_FN and *EQUAL_FN to the runtime functions which compute a +// hash code for this type and which compare whether two values of +// this type are equal. If NAME is not NULL it is the name of this +// type. HASH_FNTYPE and EQUAL_FNTYPE are the types of these +// functions, for convenience; they may be NULL. void -Type::type_functions(const char** hash_fn, const char** equal_fn) const +Type::type_functions(Gogo* gogo, Named_type* name, Function_type* hash_fntype, + Function_type* equal_fntype, Named_object** hash_fn, + Named_object** equal_fn) { - switch (this->base()->classification()) + if (hash_fntype == NULL || equal_fntype == NULL) { - case Type::TYPE_ERROR: - case Type::TYPE_VOID: - case Type::TYPE_NIL: - // These types can not be hashed or compared. - *hash_fn = "__go_type_hash_error"; - *equal_fn = "__go_type_equal_error"; - break; + Location bloc = Linemap::predeclared_location(); - case Type::TYPE_BOOLEAN: - case Type::TYPE_INTEGER: - case Type::TYPE_FLOAT: - case Type::TYPE_COMPLEX: - case Type::TYPE_POINTER: - case Type::TYPE_CHANNEL: - *hash_fn = "__go_type_hash_identity"; - *equal_fn = "__go_type_equal_identity"; - break; + 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); - case Type::TYPE_STRING: - *hash_fn = "__go_type_hash_string"; - *equal_fn = "__go_type_equal_string"; - break; + if (hash_fntype == NULL) + { + Typed_identifier_list* params = new Typed_identifier_list(); + params->push_back(Typed_identifier("key", unsafe_pointer_type, + bloc)); + params->push_back(Typed_identifier("key_size", uintptr_type, bloc)); - case Type::TYPE_STRUCT: - case Type::TYPE_ARRAY: - case Type::TYPE_FUNCTION: - case Type::TYPE_MAP: - // These types can not be hashed or compared. - *hash_fn = "__go_type_hash_error"; - *equal_fn = "__go_type_equal_error"; - break; + Typed_identifier_list* results = new Typed_identifier_list(); + results->push_back(Typed_identifier("", uintptr_type, bloc)); - case Type::TYPE_INTERFACE: - if (this->interface_type()->is_empty()) + hash_fntype = Type::make_function_type(NULL, params, results, bloc); + } + if (equal_fntype == NULL) { - *hash_fn = "__go_type_hash_empty_interface"; - *equal_fn = "__go_type_equal_empty_interface"; + 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)); + params->push_back(Typed_identifier("key_size", uintptr_type, bloc)); + + Typed_identifier_list* results = new Typed_identifier_list(); + results->push_back(Typed_identifier("", Type::lookup_bool_type(), + bloc)); + + equal_fntype = Type::make_function_type(NULL, params, results, bloc); } - else + } + + const char* hash_fnname; + const char* equal_fnname; + if (this->compare_is_identity()) + { + hash_fnname = "__go_type_hash_identity"; + equal_fnname = "__go_type_equal_identity"; + } + else if (!this->is_comparable()) + { + hash_fnname = "__go_type_hash_error"; + equal_fnname = "__go_type_equal_error"; + } + else + { + switch (this->base()->classification()) { - *hash_fn = "__go_type_hash_interface"; - *equal_fn = "__go_type_equal_interface"; + case Type::TYPE_ERROR: + case Type::TYPE_VOID: + case Type::TYPE_NIL: + case Type::TYPE_FUNCTION: + case Type::TYPE_MAP: + // For these types is_comparable should have returned false. + go_unreachable(); + + case Type::TYPE_BOOLEAN: + case Type::TYPE_INTEGER: + case Type::TYPE_POINTER: + case Type::TYPE_CHANNEL: + // For these types compare_is_identity should have returned true. + go_unreachable(); + + case Type::TYPE_FLOAT: + hash_fnname = "__go_type_hash_float"; + equal_fnname = "__go_type_equal_float"; + break; + + case Type::TYPE_COMPLEX: + hash_fnname = "__go_type_hash_complex"; + equal_fnname = "__go_type_equal_complex"; + break; + + case Type::TYPE_STRING: + hash_fnname = "__go_type_hash_string"; + equal_fnname = "__go_type_equal_string"; + break; + + case Type::TYPE_STRUCT: + { + // This is a struct which can not be compared using a + // simple identity function. We need to build a function + // for comparison. + this->specific_type_functions(gogo, name, hash_fntype, + equal_fntype, hash_fn, equal_fn); + return; + } + + case Type::TYPE_ARRAY: + if (this->is_slice_type()) + { + // Type::is_compatible_for_comparison should have + // returned false. + go_unreachable(); + } + else + { + // This is an array which can not be compared using a + // simple identity function. We need to build a + // function for comparison. + this->specific_type_functions(gogo, name, hash_fntype, + equal_fntype, hash_fn, equal_fn); + return; + } + break; + + case Type::TYPE_INTERFACE: + if (this->interface_type()->is_empty()) + { + hash_fnname = "__go_type_hash_empty_interface"; + equal_fnname = "__go_type_equal_empty_interface"; + } + else + { + hash_fnname = "__go_type_hash_interface"; + equal_fnname = "__go_type_equal_interface"; + } + break; + + case Type::TYPE_NAMED: + case Type::TYPE_FORWARD: + go_unreachable(); + + default: + go_unreachable(); } - break; + } - case Type::TYPE_NAMED: - case Type::TYPE_FORWARD: - go_unreachable(); - default: - go_unreachable(); + Location bloc = Linemap::predeclared_location(); + *hash_fn = Named_object::make_function_declaration(hash_fnname, NULL, + hash_fntype, bloc); + (*hash_fn)->func_declaration_value()->set_asm_name(hash_fnname); + *equal_fn = Named_object::make_function_declaration(equal_fnname, NULL, + equal_fntype, bloc); + (*equal_fn)->func_declaration_value()->set_asm_name(equal_fnname); +} + +// A hash table mapping types to the specific hash functions. + +Type::Type_functions Type::type_functions_table; + +// Handle a type function which is specific to a type: a struct or +// array which can not use an identity comparison. + +void +Type::specific_type_functions(Gogo* gogo, Named_type* name, + Function_type* hash_fntype, + Function_type* equal_fntype, + Named_object** hash_fn, + Named_object** equal_fn) +{ + Hash_equal_fn fnull(NULL, NULL); + std::pair val(name != NULL ? name : this, fnull); + std::pair ins = + Type::type_functions_table.insert(val); + if (!ins.second) + { + // We already have functions for this type + *hash_fn = ins.first->second.first; + *equal_fn = ins.first->second.second; + return; } + + std::string base_name; + if (name == NULL) + base_name = gogo->pack_hidden_name(this->mangled_name(gogo), false); + else + { + // This name is already hidden or not as appropriate. + base_name = name->name(); + const Named_object* in_function = name->in_function(); + if (in_function != NULL) + base_name += '$' + in_function->name(); + } + std::string hash_name = base_name + "$hash"; + std::string equal_name = base_name + "$equal"; + + Location bloc = Linemap::predeclared_location(); + + const Package* package = NULL; + bool is_defined_elsewhere = + this->type_descriptor_defined_elsewhere(name, &package); + if (is_defined_elsewhere) + { + *hash_fn = Named_object::make_function_declaration(hash_name, package, + hash_fntype, bloc); + *equal_fn = Named_object::make_function_declaration(equal_name, package, + equal_fntype, bloc); + } + else + { + *hash_fn = gogo->declare_package_function(hash_name, hash_fntype, bloc); + *equal_fn = gogo->declare_package_function(equal_name, equal_fntype, + bloc); + } + + ins.first->second.first = *hash_fn; + ins.first->second.second = *equal_fn; + + if (!is_defined_elsewhere) + { + if (gogo->in_global_scope()) + this->write_specific_type_functions(gogo, name, hash_name, hash_fntype, + equal_name, equal_fntype); + else + gogo->queue_specific_type_function(this, name, hash_name, hash_fntype, + equal_name, equal_fntype); + } +} + +// Write the hash and equality functions for a type which needs to be +// written specially. + +void +Type::write_specific_type_functions(Gogo* gogo, Named_type* name, + const std::string& hash_name, + Function_type* hash_fntype, + const std::string& equal_name, + Function_type* equal_fntype) +{ + Location bloc = Linemap::predeclared_location(); + + Named_object* hash_fn = gogo->start_function(hash_name, hash_fntype, false, + bloc); + gogo->start_block(bloc); + + if (this->struct_type() != NULL) + this->struct_type()->write_hash_function(gogo, name, hash_fntype, + equal_fntype); + else if (this->array_type() != NULL) + this->array_type()->write_hash_function(gogo, name, hash_fntype, + equal_fntype); + else + go_unreachable(); + + Block* b = gogo->finish_block(bloc); + gogo->add_block(b, bloc); + gogo->lower_block(hash_fn, b); + gogo->finish_function(bloc); + + Named_object *equal_fn = gogo->start_function(equal_name, equal_fntype, + false, bloc); + gogo->start_block(bloc); + + if (this->struct_type() != NULL) + this->struct_type()->write_equal_function(gogo, name); + else if (this->array_type() != NULL) + this->array_type()->write_equal_function(gogo, name); + else + go_unreachable(); + + b = gogo->finish_block(bloc); + gogo->add_block(b, bloc); + gogo->lower_block(equal_fn, b); + gogo->finish_function(bloc); } // Return a composite literal for the type descriptor for a plain type @@ -1320,25 +1640,20 @@ Type::type_descriptor_constructor(Gogo* gogo, int runtime_type_kind, mpz_set_ui(iv, this->hash_for_method(gogo)); vals->push_back(Expression::make_integer(&iv, p->type(), bloc)); - const char* hash_fn; - const char* equal_fn; - this->type_functions(&hash_fn, &equal_fn); - ++p; go_assert(p->is_field_name("hashfn")); - Function_type* fntype = p->type()->function_type(); - Named_object* no = Named_object::make_function_declaration(hash_fn, NULL, - fntype, - bloc); - no->func_declaration_value()->set_asm_name(hash_fn); - vals->push_back(Expression::make_func_reference(no, NULL, bloc)); + Function_type* hash_fntype = p->type()->function_type(); ++p; go_assert(p->is_field_name("equalfn")); - fntype = p->type()->function_type(); - no = Named_object::make_function_declaration(equal_fn, NULL, fntype, bloc); - no->func_declaration_value()->set_asm_name(equal_fn); - vals->push_back(Expression::make_func_reference(no, NULL, bloc)); + Function_type* equal_fntype = p->type()->function_type(); + + Named_object* hash_fn; + Named_object* equal_fn; + this->type_functions(gogo, name, hash_fntype, equal_fntype, &hash_fn, + &equal_fn); + vals->push_back(Expression::make_func_reference(hash_fn, NULL, bloc)); + vals->push_back(Expression::make_func_reference(equal_fn, NULL, bloc)); ++p; go_assert(p->is_field_name("string")); @@ -1680,6 +1995,10 @@ class Error_type : public Type { } protected: + bool + do_compare_is_identity() const + { return false; } + Btype* do_get_backend(Gogo* gogo) { return gogo->backend()->error_type(); } @@ -1714,6 +2033,10 @@ class Void_type : public Type { } protected: + bool + do_compare_is_identity() const + { return false; } + Btype* do_get_backend(Gogo* gogo) { return gogo->backend()->void_type(); } @@ -1748,6 +2071,10 @@ class Boolean_type : public Type { } protected: + bool + do_compare_is_identity() const + { return true; } + Btype* do_get_backend(Gogo* gogo) { return gogo->backend()->bool_type(); } @@ -2335,6 +2662,10 @@ class Sink_type : public Type { } protected: + bool + do_compare_is_identity() const + { return false; } + Btype* do_get_backend(Gogo*) { go_unreachable(); } @@ -3243,6 +3574,10 @@ class Nil_type : public Type { } protected: + bool + do_compare_is_identity() const + { return false; } + Btype* do_get_backend(Gogo* gogo) { return gogo->backend()->pointer_type(gogo->backend()->void_type()); } @@ -3290,6 +3625,10 @@ class Call_multiple_result_type : public Type return false; } + bool + do_compare_is_identity() const + { return false; } + Btype* do_get_backend(Gogo* gogo) { @@ -3564,6 +3903,25 @@ Struct_type::struct_has_hidden_fields(const Named_type* within, return false; } +// Whether comparisons of this struct type are simple identity +// comparisons. + +bool +Struct_type::do_compare_is_identity() const +{ + const Struct_field_list* fields = this->fields_; + if (fields == NULL) + return true; + for (Struct_field_list::const_iterator pf = fields->begin(); + pf != fields->end(); + ++pf) + if (!pf->type()->compare_is_identity()) + return false; + return true; +} + +// Build identity and hash functions for this struct. + // Hash code. unsigned int @@ -3779,6 +4137,17 @@ Struct_type::is_unexported_local_field(Gogo* gogo, void Struct_type::finalize_methods(Gogo* gogo) { + // If this type needs explicit comparison and hash functions, create + // them now. It would be a bit better to do this only if the + // functions are needed, but they will be static so the backend can + // discard them if they are not used. + if (!this->compare_is_identity() && this->is_comparable()) + { + Named_object* hash_fn; + Named_object* equal_fn; + this->type_functions(gogo, NULL, NULL, NULL, &hash_fn, &equal_fn); + } + if (this->all_methods_ != NULL) return; Type::finalize_methods(gogo, this, this->location_, &this->all_methods_); @@ -3952,6 +4321,170 @@ Struct_type::do_type_descriptor(Gogo* gogo, Named_type* name) return Expression::make_struct_composite_literal(stdt, vals, bloc); } +// Write the hash function for a struct which can not use the identity +// function. + +void +Struct_type::write_hash_function(Gogo* gogo, Named_type*, + Function_type* hash_fntype, + Function_type* equal_fntype) +{ + Location bloc = Linemap::predeclared_location(); + + // The pointer to the struct that we are going to hash. This is an + // argument to the hash function we are implementing here. + Named_object* key_arg = gogo->lookup("key", NULL); + go_assert(key_arg != NULL); + Type* key_arg_type = key_arg->var_value()->type(); + + Type* uintptr_type = Type::lookup_integer_type("uintptr"); + + // Get a 0. + mpz_t ival; + mpz_init_set_ui(ival, 0); + Expression* zero = Expression::make_integer(&ival, uintptr_type, bloc); + mpz_clear(ival); + + // Make a temporary to hold the return value, initialized to 0. + Temporary_statement* retval = Statement::make_temporary(uintptr_type, zero, + bloc); + gogo->add_statement(retval); + + // Make a temporary to hold the key as a uintptr. + Expression* ref = Expression::make_var_reference(key_arg, bloc); + ref = Expression::make_cast(uintptr_type, ref, bloc); + Temporary_statement* key = Statement::make_temporary(uintptr_type, ref, + bloc); + gogo->add_statement(key); + + // Loop over the struct fields. + bool first = true; + const Struct_field_list* fields = this->fields_; + for (Struct_field_list::const_iterator pf = fields->begin(); + pf != fields->end(); + ++pf) + { + if (first) + first = false; + else + { + // Multiply retval by 33. + mpz_init_set_ui(ival, 33); + Expression* i33 = Expression::make_integer(&ival, uintptr_type, + bloc); + mpz_clear(ival); + + ref = Expression::make_temporary_reference(retval, bloc); + Statement* s = Statement::make_assignment_operation(OPERATOR_MULTEQ, + ref, i33, bloc); + gogo->add_statement(s); + } + + // Get a pointer to the value of this field. + Expression* offset = Expression::make_struct_field_offset(this, &*pf); + ref = Expression::make_temporary_reference(key, bloc); + Expression* subkey = Expression::make_binary(OPERATOR_PLUS, ref, offset, + bloc); + subkey = Expression::make_cast(key_arg_type, subkey, bloc); + + // Get the size of this field. + Expression* size = Expression::make_type_info(pf->type(), + Expression::TYPE_INFO_SIZE); + + // Get the hash function to use for the type of this field. + Named_object* hash_fn; + Named_object* equal_fn; + pf->type()->type_functions(gogo, pf->type()->named_type(), hash_fntype, + equal_fntype, &hash_fn, &equal_fn); + + // Call the hash function for the field. + Expression_list* args = new Expression_list(); + args->push_back(subkey); + args->push_back(size); + Expression* func = Expression::make_func_reference(hash_fn, NULL, bloc); + Expression* call = Expression::make_call(func, args, false, bloc); + + // Add the field's hash value to retval. + Temporary_reference_expression* tref = + Expression::make_temporary_reference(retval, bloc); + tref->set_is_lvalue(); + Statement* s = Statement::make_assignment_operation(OPERATOR_PLUSEQ, + tref, call, bloc); + gogo->add_statement(s); + } + + // Return retval to the caller of the hash function. + Expression_list* vals = new Expression_list(); + ref = Expression::make_temporary_reference(retval, bloc); + vals->push_back(ref); + Statement* s = Statement::make_return_statement(vals, bloc); + gogo->add_statement(s); +} + +// Write the equality function for a struct which can not use the +// identity function. + +void +Struct_type::write_equal_function(Gogo* gogo, Named_type* name) +{ + Location bloc = Linemap::predeclared_location(); + + // The pointers to the structs we are going to compare. + Named_object* key1_arg = gogo->lookup("key1", NULL); + Named_object* key2_arg = gogo->lookup("key2", NULL); + go_assert(key1_arg != NULL && key2_arg != NULL); + + // Build temporaries with the right types. + Type* pt = Type::make_pointer_type(name != NULL + ? static_cast(name) + : static_cast(this)); + + Expression* ref = Expression::make_var_reference(key1_arg, bloc); + ref = Expression::make_unsafe_cast(pt, ref, bloc); + Temporary_statement* p1 = Statement::make_temporary(pt, ref, bloc); + gogo->add_statement(p1); + + ref = Expression::make_var_reference(key2_arg, bloc); + ref = Expression::make_unsafe_cast(pt, ref, bloc); + Temporary_statement* p2 = Statement::make_temporary(pt, ref, bloc); + gogo->add_statement(p2); + + const Struct_field_list* fields = this->fields_; + unsigned int field_index = 0; + for (Struct_field_list::const_iterator pf = fields->begin(); + pf != fields->end(); + ++pf, ++field_index) + { + // Compare one field in both P1 and P2. + Expression* f1 = Expression::make_temporary_reference(p1, bloc); + f1 = Expression::make_unary(OPERATOR_MULT, f1, bloc); + f1 = Expression::make_field_reference(f1, field_index, bloc); + + Expression* f2 = Expression::make_temporary_reference(p2, bloc); + f2 = Expression::make_unary(OPERATOR_MULT, f2, bloc); + f2 = Expression::make_field_reference(f2, field_index, bloc); + + Expression* cond = Expression::make_binary(OPERATOR_NOTEQ, f1, f2, bloc); + + // If the values are not equal, return false. + gogo->start_block(bloc); + Expression_list* vals = new Expression_list(); + vals->push_back(Expression::make_boolean(false, bloc)); + Statement* s = Statement::make_return_statement(vals, bloc); + gogo->add_statement(s); + Block* then_block = gogo->finish_block(bloc); + + s = Statement::make_if_statement(cond, then_block, NULL, bloc); + gogo->add_statement(s); + } + + // All the fields are equal, so return true. + Expression_list* vals = new Expression_list(); + vals->push_back(Expression::make_boolean(true, bloc)); + Statement* s = Statement::make_return_statement(vals, bloc); + gogo->add_statement(s); +} + // Reflection string. void @@ -4190,6 +4723,25 @@ Array_type::is_identical(const Array_type* t, bool errors_are_identical) const return false; } +// If this type needs explicit comparison and hash functions, create +// them now. It would be a bit better to do this only if the +// functions are needed, but they will be static so the backend can +// discard them if they are not used. + +void +Array_type::finalize_methods(Gogo* gogo) +{ + if (this->length_ != NULL + && !this->length_->is_nil_expression() + && !this->compare_is_identity() + && this->is_comparable()) + { + Named_object* hash_fn; + Named_object* equal_fn; + this->type_functions(gogo, NULL, NULL, NULL, &hash_fn, &equal_fn); + } +} + // Traversal. int @@ -4298,6 +4850,198 @@ Array_type::do_hash_for_method(Gogo* gogo) const return this->element_type_->hash_for_method(gogo) + 1; } +// Write the hash function for an array which can not use the identify +// function. + +void +Array_type::write_hash_function(Gogo* gogo, Named_type* name, + Function_type* hash_fntype, + Function_type* equal_fntype) +{ + Location bloc = Linemap::predeclared_location(); + + // The pointer to the array that we are going to hash. This is an + // argument to the hash function we are implementing here. + Named_object* key_arg = gogo->lookup("key", NULL); + go_assert(key_arg != NULL); + Type* key_arg_type = key_arg->var_value()->type(); + + Type* uintptr_type = Type::lookup_integer_type("uintptr"); + + // Get a 0. + mpz_t ival; + mpz_init_set_ui(ival, 0); + Expression* zero = Expression::make_integer(&ival, uintptr_type, bloc); + mpz_clear(ival); + + // Make a temporary to hold the return value, initialized to 0. + Temporary_statement* retval = Statement::make_temporary(uintptr_type, zero, + bloc); + gogo->add_statement(retval); + + // Make a temporary to hold the key as a uintptr. + Expression* ref = Expression::make_var_reference(key_arg, bloc); + ref = Expression::make_cast(uintptr_type, ref, bloc); + Temporary_statement* key = Statement::make_temporary(uintptr_type, ref, + bloc); + gogo->add_statement(key); + + // Loop over the array elements. + // for i = range a + Type* int_type = Type::lookup_integer_type("int"); + Temporary_statement* index = Statement::make_temporary(int_type, NULL, bloc); + gogo->add_statement(index); + + 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(name) + : static_cast(this)); + aref = Expression::make_cast(pt, aref, bloc); + For_range_statement* for_range = Statement::make_for_range_statement(iref, + NULL, + aref, + bloc); + + gogo->start_block(bloc); + + // Multiply retval by 33. + mpz_init_set_ui(ival, 33); + Expression* i33 = Expression::make_integer(&ival, uintptr_type, bloc); + mpz_clear(ival); + + ref = Expression::make_temporary_reference(retval, bloc); + Statement* s = Statement::make_assignment_operation(OPERATOR_MULTEQ, ref, + i33, bloc); + gogo->add_statement(s); + + // Get the hash function for the element type. + Named_object* hash_fn; + Named_object* equal_fn; + this->element_type_->type_functions(gogo, this->element_type_->named_type(), + hash_fntype, equal_fntype, &hash_fn, + &equal_fn); + + // Get a pointer to this element in the loop. + Expression* subkey = Expression::make_temporary_reference(key, bloc); + subkey = Expression::make_cast(key_arg_type, subkey, bloc); + + // Get the size of each element. + Expression* ele_size = Expression::make_type_info(this->element_type_, + Expression::TYPE_INFO_SIZE); + + // Get the hash of this element. + Expression_list* args = new Expression_list(); + args->push_back(subkey); + args->push_back(ele_size); + Expression* func = Expression::make_func_reference(hash_fn, NULL, bloc); + Expression* call = Expression::make_call(func, args, false, bloc); + + // Add the element's hash value to retval. + Temporary_reference_expression* tref = + Expression::make_temporary_reference(retval, bloc); + tref->set_is_lvalue(); + s = Statement::make_assignment_operation(OPERATOR_PLUSEQ, tref, call, bloc); + gogo->add_statement(s); + + // Increase the element pointer. + tref = Expression::make_temporary_reference(key, bloc); + tref->set_is_lvalue(); + s = Statement::make_assignment_operation(OPERATOR_PLUSEQ, tref, ele_size, + bloc); + + Block* statements = gogo->finish_block(bloc); + + for_range->add_statements(statements); + gogo->add_statement(for_range); + + // Return retval to the caller of the hash function. + Expression_list* vals = new Expression_list(); + ref = Expression::make_temporary_reference(retval, bloc); + vals->push_back(ref); + s = Statement::make_return_statement(vals, bloc); + gogo->add_statement(s); +} + +// Write the equality function for an array which can not use the +// identity function. + +void +Array_type::write_equal_function(Gogo* gogo, Named_type* name) +{ + Location bloc = Linemap::predeclared_location(); + + // The pointers to the arrays we are going to compare. + Named_object* key1_arg = gogo->lookup("key1", NULL); + Named_object* key2_arg = gogo->lookup("key2", NULL); + go_assert(key1_arg != NULL && key2_arg != NULL); + + // Build temporaries for the keys with the right types. + Type* pt = Type::make_pointer_type(name != NULL + ? static_cast(name) + : static_cast(this)); + + Expression* ref = Expression::make_var_reference(key1_arg, bloc); + ref = Expression::make_unsafe_cast(pt, ref, bloc); + Temporary_statement* p1 = Statement::make_temporary(pt, ref, bloc); + gogo->add_statement(p1); + + ref = Expression::make_var_reference(key2_arg, bloc); + ref = Expression::make_unsafe_cast(pt, ref, bloc); + Temporary_statement* p2 = Statement::make_temporary(pt, ref, bloc); + gogo->add_statement(p2); + + // Loop over the array elements. + // for i = range a + Type* int_type = Type::lookup_integer_type("int"); + Temporary_statement* index = Statement::make_temporary(int_type, NULL, bloc); + gogo->add_statement(index); + + Expression* iref = Expression::make_temporary_reference(index, bloc); + Expression* aref = Expression::make_temporary_reference(p1, bloc); + For_range_statement* for_range = Statement::make_for_range_statement(iref, + NULL, + aref, + bloc); + + gogo->start_block(bloc); + + // Compare element in P1 and P2. + Expression* e1 = Expression::make_temporary_reference(p1, bloc); + e1 = Expression::make_unary(OPERATOR_MULT, e1, bloc); + ref = Expression::make_temporary_reference(index, bloc); + e1 = Expression::make_array_index(e1, ref, NULL, bloc); + + Expression* e2 = Expression::make_temporary_reference(p2, bloc); + e2 = Expression::make_unary(OPERATOR_MULT, e2, bloc); + ref = Expression::make_temporary_reference(index, bloc); + e2 = Expression::make_array_index(e2, ref, NULL, bloc); + + Expression* cond = Expression::make_binary(OPERATOR_NOTEQ, e1, e2, bloc); + + // If the elements are not equal, return false. + gogo->start_block(bloc); + Expression_list* vals = new Expression_list(); + vals->push_back(Expression::make_boolean(false, bloc)); + Statement* s = Statement::make_return_statement(vals, bloc); + gogo->add_statement(s); + Block* then_block = gogo->finish_block(bloc); + + s = Statement::make_if_statement(cond, then_block, NULL, bloc); + gogo->add_statement(s); + + Block* statements = gogo->finish_block(bloc); + + for_range->add_statements(statements); + gogo->add_statement(for_range); + + // All the elements are equal, so return true. + vals = new Expression_list(); + vals->push_back(Expression::make_boolean(true, bloc)); + s = Statement::make_return_statement(vals, bloc); + gogo->add_statement(s); +} + // Get a tree for the length of a fixed array. The length may be // computed using a function call, so we must only evaluate it once. @@ -4730,10 +5474,8 @@ Map_type::do_traverse(Traverse* traverse) bool Map_type::do_verify() { - if (this->key_type_->struct_type() != NULL - || this->key_type_->array_type() != NULL - || this->key_type_->function_type() != NULL - || this->key_type_->map_type() != NULL) + // The runtime support uses "map[void]void". + if (!this->key_type_->is_comparable() && !this->key_type_->is_void_type()) { error_at(this->location_, "invalid map key type"); return false; @@ -6292,6 +7034,21 @@ Named_type::is_named_error_type() const return ret; } +// Whether this type is comparable. We have to be careful about +// circular type definitions. + +bool +Named_type::named_type_is_comparable(std::string* reason) const +{ + if (this->seen_) + return false; + this->seen_ = true; + bool ret = Type::are_compatible_for_comparison(true, this->type_, + this->type_, reason); + this->seen_ = false; + return ret; +} + // Add a method to this type. Named_object* @@ -6367,6 +7124,20 @@ Named_type::is_unexported_local_method(Gogo* gogo, void Named_type::finalize_methods(Gogo* gogo) { + // If this type needs explicit comparison and hash functions, create + // them now. It would be a bit better to do this only if the + // functions are needed, but they will be static so the backend can + // discard them if they are not used. + if ((this->struct_type() != NULL + || (this->array_type() != NULL && !this->is_slice_type())) + && !this->compare_is_identity() + && this->is_comparable()) + { + Named_object* hash_fn; + Named_object* equal_fn; + this->type_functions(gogo, this, NULL, NULL, &hash_fn, &equal_fn); + } + if (this->all_methods_ != NULL) return; @@ -6616,6 +7387,20 @@ Named_type::do_has_pointer() const return ret; } +// Return whether comparisons for this type can use the identity +// function. + +bool +Named_type::do_compare_is_identity() const +{ + if (this->seen_) + return false; + this->seen_ = true; + bool ret = this->type_->compare_is_identity(); + this->seen_ = false; + return ret; +} + // Return a hash code. This is used for method lookup. We simply // hash on the name itself. diff --git a/gcc/go/gofrontend/types.h b/gcc/go/gofrontend/types.h index 035444f..b00b007 100644 --- a/gcc/go/gofrontend/types.h +++ b/gcc/go/gofrontend/types.h @@ -522,6 +522,21 @@ class Type static bool are_compatible_for_binop(const Type* t1, const Type* t2); + // Return true if two types are compatible for use with the + // comparison operator. IS_EQUALITY_OP is true if this is an + // equality comparison, false if it is an ordered comparison. This + // is an equivalence relation. If this returns false, and REASON is + // not NULL, it sets *REASON. + static bool + are_compatible_for_comparison(bool is_equality_op, const Type *t1, + const Type *t2, std::string* reason); + + // Return true if a type is comparable with itself. This is true of + // most types, but false for, e.g., function types. + bool + is_comparable() const + { return Type::are_compatible_for_comparison(true, this, this, NULL); } + // Return true if a value with type RHS is assignable to a variable // with type LHS. This is not an equivalence relation. If this // returns false, and REASON is not NULL, it sets *REASON. @@ -549,6 +564,13 @@ class Type bool has_hidden_fields(const Named_type* within, std::string* reason) const; + // Return true if values of this type can be compared using an + // identity function which gets nothing but a pointer to the value + // and a size. + bool + compare_is_identity() const + { return this->do_compare_is_identity(); } + // Return a hash code for this type for the method hash table. // Types which are equivalent according to are_identical will have // the same hash code. @@ -839,6 +861,20 @@ class Type std::string mangled_name(Gogo*) const; + // Get the hash and equality functions for a type. + void + type_functions(Gogo*, Named_type* name, Function_type* hash_fntype, + Function_type* equal_fntype, Named_object** hash_fn, + Named_object** equal_fn); + + // Write the hash and equality type functions. + void + write_specific_type_functions(Gogo*, Named_type*, + const std::string& hash_name, + Function_type* hash_fntype, + const std::string& equal_name, + Function_type* equal_fntype); + // Export the type. void export_type(Export* exp) const @@ -866,6 +902,9 @@ class Type do_has_pointer() const { return false; } + virtual bool + do_compare_is_identity() const = 0; + virtual unsigned int do_hash_for_method(Gogo*) const; @@ -878,7 +917,6 @@ class Type virtual void do_reflection(Gogo*, std::string*) const = 0; - virtual void do_mangled_name(Gogo*, std::string*) const = 0; @@ -1002,18 +1040,24 @@ class Type void make_type_descriptor_var(Gogo*); - // Return the name of the type descriptor variable for an unnamed - // type. + // Return the name of the type descriptor variable. If NAME is not + // NULL, it is the name to use. std::string - unnamed_type_descriptor_var_name(Gogo*); + type_descriptor_var_name(Gogo*, Named_type* name); - // Return the name of the type descriptor variable for a named type. - std::string - type_descriptor_var_name(Gogo*); + // Return true if the type descriptor for this type should be + // defined in some other package. If NAME is not NULL, it is the + // name of this type. If this returns true it sets *PACKAGE to the + // package where the type descriptor is defined. + bool + type_descriptor_defined_elsewhere(Named_type* name, const Package** package); - // Get the hash and equality functions for a type. + // Build the hash and equality type functions for a type which needs + // specific functions. void - type_functions(const char** hash_fn, const char** equal_fn) const; + specific_type_functions(Gogo*, Named_type*, Function_type* hash_fntype, + Function_type* equal_fntype, Named_object** hash_fn, + Named_object** equal_fn); // Build a composite literal for the uncommon type information. Expression* @@ -1097,6 +1141,14 @@ class Type // A list of builtin named types. static std::vector named_builtin_types; + // A map from types which need specific type functions to the type + // functions themselves. + typedef std::pair Hash_equal_fn; + typedef Unordered_map_hash(const Type*, Hash_equal_fn, Type_hash_identical, + Type_identical) Type_functions; + + static Type_functions type_functions_table; + // The type classification. Type_classification classification_; // The backend representation of the type, once it has been @@ -1314,6 +1366,10 @@ class Integer_type : public Type is_identical(const Integer_type* t) const; protected: + bool + do_compare_is_identity() const + { return true; } + unsigned int do_hash_for_method(Gogo*) const; @@ -1383,6 +1439,10 @@ class Float_type : public Type is_identical(const Float_type* t) const; protected: + bool + do_compare_is_identity() const + { return false; } + unsigned int do_hash_for_method(Gogo*) const; @@ -1448,6 +1508,10 @@ class Complex_type : public Type is_identical(const Complex_type* t) const; protected: + bool + do_compare_is_identity() const + { return false; } + unsigned int do_hash_for_method(Gogo*) const; @@ -1504,6 +1568,10 @@ class String_type : public Type do_has_pointer() const { return true; } + bool + do_compare_is_identity() const + { return false; } + Btype* do_get_backend(Gogo*); @@ -1618,6 +1686,10 @@ class Function_type : public Type do_has_pointer() const { return true; } + bool + do_compare_is_identity() const + { return false; } + unsigned int do_hash_for_method(Gogo*) const; @@ -1699,6 +1771,10 @@ class Pointer_type : public Type do_has_pointer() const { return true; } + bool + do_compare_is_identity() const + { return true; } + unsigned int do_hash_for_method(Gogo*) const; @@ -1944,6 +2020,14 @@ class Struct_type : public Type static Type* make_struct_type_descriptor_type(); + // Write the hash function for this type. + void + write_hash_function(Gogo*, Named_type*, Function_type*, Function_type*); + + // Write the equality function for this type. + void + write_equal_function(Gogo*, Named_type*); + protected: int do_traverse(Traverse*); @@ -1954,6 +2038,9 @@ class Struct_type : public Type bool do_has_pointer() const; + bool + do_compare_is_identity() const; + unsigned int do_hash_for_method(Gogo*) const; @@ -2022,6 +2109,10 @@ class Array_type : public Type array_has_hidden_fields(const Named_type* within, std::string* reason) const { return this->element_type_->has_hidden_fields(within, reason); } + // Build the hash and equality functions if necessary. + void + finalize_methods(Gogo*); + // Return a tree for the pointer to the values in an array. tree value_pointer_tree(Gogo*, tree array) const; @@ -2052,6 +2143,14 @@ class Array_type : public Type static Type* make_slice_type_descriptor_type(); + // Write the hash function for this type. + void + write_hash_function(Gogo*, Named_type*, Function_type*, Function_type*); + + // Write the equality function for this type. + void + write_equal_function(Gogo*, Named_type*); + protected: int do_traverse(Traverse* traverse); @@ -2065,6 +2164,13 @@ class Array_type : public Type return this->length_ == NULL || this->element_type_->has_pointer(); } + bool + do_compare_is_identity() const + { + return (this->length_ != NULL + && this->element_type_->compare_is_identity()); + } + unsigned int do_hash_for_method(Gogo*) const; @@ -2155,6 +2261,10 @@ class Map_type : public Type do_has_pointer() const { return true; } + bool + do_compare_is_identity() const + { return false; } + unsigned int do_hash_for_method(Gogo*) const; @@ -2237,6 +2347,10 @@ class Channel_type : public Type do_has_pointer() const { return true; } + bool + do_compare_is_identity() const + { return true; } + unsigned int do_hash_for_method(Gogo*) const; @@ -2348,6 +2462,10 @@ class Interface_type : public Type do_has_pointer() const { return true; } + bool + do_compare_is_identity() const + { return false; } + unsigned int do_hash_for_method(Gogo*) const; @@ -2480,6 +2598,11 @@ class Named_type : public Type bool is_named_error_type() const; + // Return whether this type is comparable. If REASON is not NULL, + // set *REASON when returning false. + bool + named_type_is_comparable(std::string* reason) const; + // Add a method to this type. Named_object* add_method(const std::string& name, Function*); @@ -2572,6 +2695,9 @@ class Named_type : public Type bool do_has_pointer() const; + bool + do_compare_is_identity() const; + unsigned int do_hash_for_method(Gogo*) const; @@ -2704,6 +2830,10 @@ class Forward_declaration_type : public Type do_has_pointer() const { return this->real_type()->has_pointer(); } + bool + do_compare_is_identity() const + { return this->real_type()->compare_is_identity(); } + unsigned int do_hash_for_method(Gogo* gogo) const { return this->real_type()->hash_for_method(gogo); } -- cgit v1.1