From 08c8a26e9ca87ad2dd5b26d397e6107b68adfe76 Mon Sep 17 00:00:00 2001 From: Ian Lance Taylor Date: Fri, 3 May 2019 21:45:35 +0000 Subject: [PATCH] compiler: recognize and optimize array range clear Recognize for i := range a { a[i] = zero } for array or slice a, and rewrite it to call memclr, as the gc compiler does. Reviewed-on: https://go-review.googlesource.com/c/gofrontend/+/169398 From-SVN: r270862 --- gcc/go/gofrontend/MERGE | 2 +- gcc/go/gofrontend/expressions.cc | 116 ++++++++++++++++++++++++++++++ gcc/go/gofrontend/expressions.h | 32 ++++++++- gcc/go/gofrontend/runtime.def | 8 +++ gcc/go/gofrontend/statements.cc | 118 +++++++++++++++++++++++++++++++ gcc/go/gofrontend/statements.h | 5 ++ libgo/go/runtime/mbarrier.go | 1 + 7 files changed, 280 insertions(+), 2 deletions(-) diff --git a/gcc/go/gofrontend/MERGE b/gcc/go/gofrontend/MERGE index a1bcb4b0d9d..6cb0662957e 100644 --- a/gcc/go/gofrontend/MERGE +++ b/gcc/go/gofrontend/MERGE @@ -1,4 +1,4 @@ -208521930c9b5adcfb495799ee01b6aec86c2ccf +4b3015de639cf22ed11ff96097555700909827c8 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/expressions.cc b/gcc/go/gofrontend/expressions.cc index 0dd869bb9c2..efb3d0dae6c 100644 --- a/gcc/go/gofrontend/expressions.cc +++ b/gcc/go/gofrontend/expressions.cc @@ -1671,6 +1671,10 @@ class Boolean_expression : public Expression do_is_constant() const { return true; } + bool + do_is_zero_value() const + { return this->val_ == false; } + bool do_is_static_initializer() const { return true; } @@ -2054,6 +2058,10 @@ class Integer_expression : public Expression do_is_constant() const { return true; } + bool + do_is_zero_value() const + { return mpz_sgn(this->val_) == 0; } + bool do_is_static_initializer() const { return true; } @@ -2474,6 +2482,13 @@ class Float_expression : public Expression do_is_constant() const { return true; } + bool + do_is_zero_value() const + { + return mpfr_zero_p(this->val_) != 0 + && mpfr_signbit(this->val_) == 0; + } + bool do_is_static_initializer() const { return true; } @@ -2685,6 +2700,15 @@ class Complex_expression : public Expression do_is_constant() const { return true; } + bool + do_is_zero_value() const + { + return mpfr_zero_p(mpc_realref(this->val_)) != 0 + && mpfr_signbit(mpc_realref(this->val_)) == 0 + && mpfr_zero_p(mpc_imagref(this->val_)) != 0 + && mpfr_signbit(mpc_imagref(this->val_)) == 0; + } + bool do_is_static_initializer() const { return true; } @@ -2922,6 +2946,10 @@ class Const_expression : public Expression do_is_constant() const { return true; } + bool + do_is_zero_value() const + { return this->constant_->const_value()->expr()->is_zero_value(); } + bool do_is_static_initializer() const { return true; } @@ -3289,6 +3317,10 @@ class Nil_expression : public Expression do_is_constant() const { return true; } + bool + do_is_zero_value() const + { return true; } + bool do_is_static_initializer() const { return true; } @@ -3533,6 +3565,28 @@ Type_conversion_expression::do_is_constant() const return true; } +// Return whether a type conversion is a zero value. + +bool +Type_conversion_expression::do_is_zero_value() const +{ + if (!this->expr_->is_zero_value()) + return false; + + // Some type conversion from zero value is still not zero value. + // For example, []byte("") or interface{}(0). + // Conservatively, only report true if the RHS is nil. + Type* type = this->type_; + if (type->integer_type() == NULL + && type->float_type() == NULL + && type->complex_type() == NULL + && !type->is_boolean_type() + && !type->is_string_type()) + return this->expr_->is_nil_expression(); + + return true; +} + // Return whether a type conversion can be used in a constant // initializer. @@ -6879,6 +6933,19 @@ String_concat_expression::do_is_constant() const return true; } +bool +String_concat_expression::do_is_zero_value() const +{ + for (Expression_list::const_iterator pe = this->exprs_->begin(); + pe != this->exprs_->end(); + ++pe) + { + if (!(*pe)->is_zero_value()) + return false; + } + return true; +} + bool String_concat_expression::do_is_static_initializer() const { @@ -13007,6 +13074,33 @@ Struct_construction_expression::is_constant_struct() const return true; } +// Return whether this is a zero value. + +bool +Struct_construction_expression::do_is_zero_value() const +{ + if (this->vals() == NULL) + return true; + for (Expression_list::const_iterator pv = this->vals()->begin(); + pv != this->vals()->end(); + ++pv) + if (*pv != NULL && !(*pv)->is_zero_value()) + return false; + + const Struct_field_list* fields = this->type_->struct_type()->fields(); + for (Struct_field_list::const_iterator pf = fields->begin(); + pf != fields->end(); + ++pf) + { + // Interface conversion may cause a zero value being converted + // to a non-zero value, like interface{}(0). Be conservative. + if (pf->type()->interface_type() != NULL) + return false; + } + + return true; +} + // Return whether this struct can be used as a constant initializer. bool @@ -13288,6 +13382,28 @@ Array_construction_expression::is_constant_array() const return true; } +// Return whether this is a zero value. + +bool +Array_construction_expression::do_is_zero_value() const +{ + if (this->vals() == NULL) + return true; + + // Interface conversion may cause a zero value being converted + // to a non-zero value, like interface{}(0). Be conservative. + if (this->type_->array_type()->element_type()->interface_type() != NULL) + return false; + + for (Expression_list::const_iterator pv = this->vals()->begin(); + pv != this->vals()->end(); + ++pv) + if (*pv != NULL && !(*pv)->is_zero_value()) + return false; + + return true; +} + // Return whether this can be used a constant initializer. bool diff --git a/gcc/go/gofrontend/expressions.h b/gcc/go/gofrontend/expressions.h index af7b00c081d..d2a34728972 100644 --- a/gcc/go/gofrontend/expressions.h +++ b/gcc/go/gofrontend/expressions.h @@ -544,6 +544,11 @@ class Expression is_constant() const { return this->do_is_constant(); } + // Return whether this is the zero value of its type. + bool + is_zero_value() const + { return this->do_is_zero_value(); } + // Return whether this expression can be used as a static // initializer. This is true for an expression that has only // numbers and pointers to global variables or composite literals @@ -1066,6 +1071,11 @@ class Expression do_is_constant() const { return false; } + // Return whether this is the zero value of its type. + virtual bool + do_is_zero_value() const + { return false; } + // Return whether this expression can be used as a constant // initializer. virtual bool @@ -1599,6 +1609,10 @@ class String_expression : public Expression do_is_constant() const { return true; } + bool + do_is_zero_value() const + { return this->val_ == ""; } + bool do_is_static_initializer() const { return true; } @@ -1692,6 +1706,9 @@ class Type_conversion_expression : public Expression bool do_is_constant() const; + bool + do_is_zero_value() const; + bool do_is_static_initializer() const; @@ -1755,6 +1772,10 @@ class Unsafe_type_conversion_expression : public Expression int do_traverse(Traverse* traverse); + bool + do_is_zero_value() const + { return this->expr_->is_zero_value(); } + bool do_is_static_initializer() const; @@ -2151,6 +2172,9 @@ class String_concat_expression : public Expression bool do_is_constant() const; + bool + do_is_zero_value() const; + bool do_is_static_initializer() const; @@ -3570,7 +3594,7 @@ class Struct_construction_expression : public Expression, type_(type) { } - // Return whether this is a constant initializer. + // Return whether this is a constant initializer. bool is_constant_struct() const; @@ -3578,6 +3602,9 @@ class Struct_construction_expression : public Expression, int do_traverse(Traverse* traverse); + bool + do_is_zero_value() const; + bool do_is_static_initializer() const; @@ -3642,6 +3669,9 @@ protected: virtual int do_traverse(Traverse* traverse); + bool + do_is_zero_value() const; + bool do_is_static_initializer() const; diff --git a/gcc/go/gofrontend/runtime.def b/gcc/go/gofrontend/runtime.def index a87b4d270d4..0fcc0a8c780 100644 --- a/gcc/go/gofrontend/runtime.def +++ b/gcc/go/gofrontend/runtime.def @@ -313,6 +313,14 @@ DEF_GO_RUNTIME(GCWRITEBARRIER, "runtime.gcWriteBarrier", DEF_GO_RUNTIME(TYPEDMEMMOVE, "runtime.typedmemmove", P3(TYPE, POINTER, POINTER), R0()) +// Clear memory that contains no pointer. +DEF_GO_RUNTIME(MEMCLRNOPTR, "runtime.memclrNoHeapPointers", + P2(POINTER, UINTPTR), R0()) + +// Clear memory that contains pointer. +DEF_GO_RUNTIME(MEMCLRHASPTR, "runtime.memclrHasPointers", + P2(POINTER, UINTPTR), R0()) + // Lock the printer (for print/println). DEF_GO_RUNTIME(PRINTLOCK, "runtime.printlock", P0(), R0()) diff --git a/gcc/go/gofrontend/statements.cc b/gcc/go/gofrontend/statements.cc index 6dd179a7088..1827f81901b 100644 --- a/gcc/go/gofrontend/statements.cc +++ b/gcc/go/gofrontend/statements.cc @@ -5516,6 +5516,21 @@ For_range_statement::do_lower(Gogo* gogo, Named_object*, Block* enclosing, return Statement::make_block_statement(temp_block, loc); } } + else if (range_type->array_type() != NULL) + { + // Slice or array. + Statement* clear = this->lower_array_range_clear(gogo, + range_type, + orig_range_expr, + temp_block, + range_object, + range_temp, loc); + if (clear != NULL) + { + temp_block->add_statement(clear); + return Statement::make_block_statement(temp_block, loc); + } + } Temporary_statement* index_temp = Statement::make_temporary(index_type, NULL, loc); @@ -6237,6 +6252,109 @@ For_range_statement::lower_map_range_clear(Type* map_type, return Statement::make_statement(call, true); } +// Match +// +// for i := range a { a[i] = zero } +// +// Lower it to call memclr on match, and return the statement. Return +// NULL otherwise. + +Statement* +For_range_statement::lower_array_range_clear(Gogo* gogo, + Type* array_type, + Expression* orig_range_expr, + Block* temp_block, + Named_object* range_object, + Temporary_statement* range_temp, + Location loc) +{ + if (this->value_var_ != NULL) + return NULL; + if (this->index_var_ == NULL) + return NULL; + + // Match the body, a single assignment statement a[i] = zero. + const std::vector* statements = this->statements_->statements(); + if (statements->size() != 1) + return NULL; + Assignment_statement* as = statements->at(0)->assignment_statement(); + if (as == NULL || !as->rhs()->is_zero_value()) + return NULL; + if (as->lhs()->type()->interface_type() != NULL + && as->rhs()->type()->interface_type() == NULL + && !as->rhs()->type()->is_nil_type()) + // Implicit type conversion may change a zero value to non-zero, like + // interface{}(0). + return NULL; + Array_index_expression* aie = as->lhs()->array_index_expression(); + if (aie == NULL || aie->end() != NULL + || !Expression::is_same_variable(orig_range_expr, aie->array()) + || !Expression::is_same_variable(this->index_var_, aie->start())) + return NULL; + + // Everything matches. Rewrite to + // + // if len(a) != 0 { + // tmp1 = &a[0] + // tmp2 = len(a)*sizeof(elem(a)) + // memclr{NoHeap,Has}Pointers(tmp1, tmp2) + // i = len(a) - 1 + // } + + Type* elem_type = array_type->array_type()->element_type(); + int64_t elme_sz; + bool ok = elem_type->backend_type_size(gogo, &elme_sz); + if (!ok) + return NULL; + + Block* b = new Block(temp_block, loc); + + Expression* ref; + if (range_object == NULL && range_temp == NULL) + // is_same_variable implies no side effect, so it is ok to copy. + ref = orig_range_expr->copy(); + else + ref = this->make_range_ref(range_object, range_temp, loc); + Expression* len = this->call_builtin(gogo, "len", ref, loc); + Temporary_statement* tslen = Statement::make_temporary(NULL, len, loc); + temp_block->add_statement(tslen); + + Expression* zero = Expression::make_integer_ul(0, this->index_var_->type(), loc); + ref = ref->copy(); + Expression* elem = Expression::make_array_index(ref, zero, NULL, NULL, loc); + elem->array_index_expression()->set_needs_bounds_check(false); + Expression* e1 = Expression::make_unary(OPERATOR_AND, elem, loc); + Temporary_statement* ts1 = Statement::make_temporary(NULL, e1, loc); + b->add_statement(ts1); + + len = Expression::make_temporary_reference(tslen, loc); + Expression* sz = Expression::make_integer_int64(elme_sz, len->type(), loc); + Expression* e2 = Expression::make_binary(OPERATOR_MULT, len, sz, loc); + Temporary_statement* ts2 = Statement::make_temporary(NULL, e2, loc); + b->add_statement(ts2); + + Expression* arg1 = Expression::make_temporary_reference(ts1, loc); + Expression* arg2 = Expression::make_temporary_reference(ts2, loc); + Runtime::Function code = (elem_type->has_pointer() + ? Runtime::MEMCLRHASPTR + : Runtime::MEMCLRNOPTR); + Expression* call = Runtime::make_call(code, loc, 2, arg1, arg2); + Statement* cs3 = Statement::make_statement(call, true); + b->add_statement(cs3); + + len = Expression::make_temporary_reference(tslen, loc); + Expression* one = Expression::make_integer_ul(1, len->type(), loc); + Expression* rhs = Expression::make_binary(OPERATOR_MINUS, len, one, loc); + Expression* lhs = this->index_var_->copy(); + Statement* as4 = Statement::make_assignment(lhs, rhs, loc); + b->add_statement(as4); + + len = Expression::make_temporary_reference(tslen, loc); + zero = zero->copy(); + Expression* cond = Expression::make_binary(OPERATOR_NOTEQ, len, zero, loc); + return Statement::make_if_statement(cond, b, NULL, loc); +} + // Return the break LABEL_EXPR. Unnamed_label* diff --git a/gcc/go/gofrontend/statements.h b/gcc/go/gofrontend/statements.h index 67c8e4343b7..ec9ade3f9e7 100644 --- a/gcc/go/gofrontend/statements.h +++ b/gcc/go/gofrontend/statements.h @@ -1622,6 +1622,11 @@ class For_range_statement : public Statement lower_map_range_clear(Type*, Block*, Expression*, Named_object*, Temporary_statement*, Location); + Statement* + lower_array_range_clear(Gogo*, Type*, Expression*, Block*, + Named_object*, Temporary_statement*, + Location); + // The variable which is set to the index value. Expression* index_var_; // The variable which is set to the element value. This may be diff --git a/libgo/go/runtime/mbarrier.go b/libgo/go/runtime/mbarrier.go index d3ffd3c518d..89febb9d4a2 100644 --- a/libgo/go/runtime/mbarrier.go +++ b/libgo/go/runtime/mbarrier.go @@ -23,6 +23,7 @@ import ( // //go:linkname typedmemmove runtime.typedmemmove //go:linkname typedslicecopy runtime.typedslicecopy +//go:linkname memclrHasPointers runtime.memclrHasPointers // Go uses a hybrid barrier that combines a Yuasa-style deletion // barrier—which shades the object whose reference is being -- 2.30.2