compiler: optimize append of make

    
    The gc compiler recognizes append(s, make([]T, n)...), and
    generates code to directly zero the tail instead of allocating a
    new slice and copying. This CL lets the Go frontend do basically
    the same.
    
    The difficulty is that at the point we handle append, there may
    already be temporaries introduced (e.g. in order_evaluations),
    which makes it hard to find the append-of-make pattern. The
    compiler could "see through" the value of a temporary, but it is
    only safe to do if the temporary is not assigned multiple times.
    For this, we add tracking of assignments and uses for temporaries.
    
    This also helps in optimizing non-escape slice make. We already
    optimize non-escape slice make with constant len/cap to stack
    allocation. But it failed to handle things like f(make([]T, n))
    (where the slice doesn't escape and n is constant), because of
    the temporary. With tracking of temporary assignments and uses,
    it can handle this now as well.
    
    Reviewed-on: https://go-review.googlesource.com/c/gofrontend/+/179597

From-SVN: r271822

8 files changed, 266 insertions, 93 deletions

diff --git a/gcc/go/gofrontend/MERGE b/gcc/go/gofrontend/MERGE
index 420248b..d377e22 100644
--- a/gcc/go/gofrontend/MERGE
+++ b/gcc/go/gofrontend/MERGE
@@ -1,4 +1,4 @@
-e521123b23494148d534755e2f3d7806b42c96ad
+52176566485e20968394a5cb67a89ac676182594
 
 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 f0c12f4..9d8c085 100644
--- a/gcc/go/gofrontend/expressions.cc
+++ b/gcc/go/gofrontend/expressions.cc
@@ -1052,6 +1052,7 @@ Temporary_reference_expression*
 Expression::make_temporary_reference(Temporary_statement* statement,
 				     Location location)
 {
+  statement->add_use();
   return new Temporary_reference_expression(statement, location);
 }
 
@@ -8286,23 +8287,87 @@ Builtin_call_expression::flatten_append(Gogo* gogo, Named_object* function,
   Temporary_statement* l2tmp = NULL;
   Expression_list* add = NULL;
   Expression* len2;
+  Call_expression* makecall = NULL;
   if (this->is_varargs())
     {
       go_assert(args->size() == 2);
 
-      // s2tmp := s2
-      s2tmp = Statement::make_temporary(NULL, args->back(), loc);
-      inserter->insert(s2tmp);
+      std::pair<Call_expression*, Temporary_statement*> p =
+        Expression::find_makeslice_call(args->back());
+      makecall = p.first;
+      if (makecall != NULL)
+        {
+          // We are handling
+          // 	append(s, make([]T, len[, cap])...))
+          // which has already been lowered to
+          // 	append(s, runtime.makeslice(T, len, cap)).
+          // We will optimize this to directly zeroing the tail,
+          // instead of allocating a new slice then copy.
+
+          // Retrieve the length. Cannot reference s2 as we will remove
+          // the makeslice call.
+          Expression* len_arg = makecall->args()->at(1);
+          len_arg = Expression::make_cast(int_type, len_arg, loc);
+          l2tmp = Statement::make_temporary(int_type, len_arg, loc);
+          inserter->insert(l2tmp);
+
+          Expression* cap_arg = makecall->args()->at(2);
+          cap_arg = Expression::make_cast(int_type, cap_arg, loc);
+          Temporary_statement* c2tmp =
+            Statement::make_temporary(int_type, cap_arg, loc);
+          inserter->insert(c2tmp);
+
+          // Check bad len/cap here.
+          // if len2 < 0 { panicmakeslicelen(); }
+          len2 = Expression::make_temporary_reference(l2tmp, loc);
+          Expression* zero = Expression::make_integer_ul(0, int_type, loc);
+          Expression* cond = Expression::make_binary(OPERATOR_LT, len2,
+                                                     zero, loc);
+          Expression* arg =
+            Expression::make_integer_ul(RUNTIME_ERROR_MAKE_SLICE_LEN_OUT_OF_BOUNDS,
+                                        NULL, loc);
+          Expression* call = Runtime::make_call(Runtime::RUNTIME_ERROR,
+                                                loc, 1, arg);
+          cond = Expression::make_conditional(cond, call, zero->copy(), loc);
+          gogo->lower_expression(function, inserter, &cond);
+          gogo->flatten_expression(function, inserter, &cond);
+          Statement* s = Statement::make_statement(cond, false);
+          inserter->insert(s);
+
+          // if cap2 < 0 { panicmakeslicecap(); }
+          Expression* cap2 = Expression::make_temporary_reference(c2tmp, loc);
+          cond = Expression::make_binary(OPERATOR_LT, cap2,
+                                         zero->copy(), loc);
+          arg = Expression::make_integer_ul(RUNTIME_ERROR_MAKE_SLICE_CAP_OUT_OF_BOUNDS,
+                                            NULL, loc);
+          call = Runtime::make_call(Runtime::RUNTIME_ERROR, loc, 1, arg);
+          cond = Expression::make_conditional(cond, call, zero->copy(), loc);
+          gogo->lower_expression(function, inserter, &cond);
+          gogo->flatten_expression(function, inserter, &cond);
+          s = Statement::make_statement(cond, false);
+          inserter->insert(s);
+
+          // Remove the original makeslice call.
+          Temporary_statement* ts = p.second;
+          if (ts != NULL && ts->uses() == 1)
+            ts->set_init(Expression::make_nil(loc));
+        }
+      else
+        {
+          // s2tmp := s2
+          s2tmp = Statement::make_temporary(NULL, args->back(), loc);
+          inserter->insert(s2tmp);
 
-      // l2tmp := len(s2tmp)
-      lenref = Expression::make_func_reference(lenfn, NULL, loc);
-      call_args = new Expression_list();
-      call_args->push_back(Expression::make_temporary_reference(s2tmp, loc));
-      len = Expression::make_call(lenref, call_args, false, loc);
-      gogo->lower_expression(function, inserter, &len);
-      gogo->flatten_expression(function, inserter, &len);
-      l2tmp = Statement::make_temporary(int_type, len, loc);
-      inserter->insert(l2tmp);
+          // l2tmp := len(s2tmp)
+          lenref = Expression::make_func_reference(lenfn, NULL, loc);
+          call_args = new Expression_list();
+          call_args->push_back(Expression::make_temporary_reference(s2tmp, loc));
+          len = Expression::make_call(lenref, call_args, false, loc);
+          gogo->lower_expression(function, inserter, &len);
+          gogo->flatten_expression(function, inserter, &len);
+          l2tmp = Statement::make_temporary(int_type, len, loc);
+          inserter->insert(l2tmp);
+        }
 
       // len2 = l2tmp
       len2 = Expression::make_temporary_reference(l2tmp, loc);
@@ -8422,52 +8487,92 @@ Builtin_call_expression::flatten_append(Gogo* gogo, Named_object* function,
       inserter->insert(assign);
     }
 
+  Type* uintptr_type = Type::lookup_integer_type("uintptr");
+
   if (this->is_varargs())
     {
-      if (element_type->has_pointer())
+      if (makecall != NULL)
         {
-          // copy(s1tmp[l1tmp:], s2tmp)
-          a1 = Expression::make_temporary_reference(s1tmp, loc);
-          ref = Expression::make_temporary_reference(l1tmp, loc);
-          Expression* nil = Expression::make_nil(loc);
-          a1 = Expression::make_array_index(a1, ref, nil, NULL, loc);
-          a1->array_index_expression()->set_needs_bounds_check(false);
-
-          a2 = Expression::make_temporary_reference(s2tmp, loc);
-
-          Named_object* copyfn = gogo->lookup_global("copy");
-          Expression* copyref = Expression::make_func_reference(copyfn, NULL, loc);
-          call_args = new Expression_list();
-          call_args->push_back(a1);
-          call_args->push_back(a2);
-          call = Expression::make_call(copyref, call_args, false, loc);
-        }
-      else
-        {
-          // memmove(&s1tmp[l1tmp], s2tmp.ptr, l2tmp*sizeof(elem))
+          // memclr(&s1tmp[l1tmp], l2tmp*sizeof(elem))
           a1 = Expression::make_temporary_reference(s1tmp, loc);
           ref = Expression::make_temporary_reference(l1tmp, loc);
           a1 = Expression::make_array_index(a1, ref, NULL, NULL, loc);
           a1->array_index_expression()->set_needs_bounds_check(false);
           a1 = Expression::make_unary(OPERATOR_AND, a1, loc);
 
-          a2 = Expression::make_temporary_reference(s2tmp, loc);
-          a2 = (a2->type()->is_string_type()
-                ? Expression::make_string_info(a2,
-                                               STRING_INFO_DATA,
-                                               loc)
-                : Expression::make_slice_info(a2,
-                                              SLICE_INFO_VALUE_POINTER,
-                                              loc));
-
-          Type* uintptr_type = Type::lookup_integer_type("uintptr");
           ref = Expression::make_temporary_reference(l2tmp, loc);
           ref = Expression::make_cast(uintptr_type, ref, loc);
-          a3 = Expression::make_type_info(element_type, TYPE_INFO_SIZE);
-          a3 = Expression::make_binary(OPERATOR_MULT, a3, ref, loc);
+          a2 = Expression::make_type_info(element_type, TYPE_INFO_SIZE);
+          a2 = Expression::make_binary(OPERATOR_MULT, a2, ref, loc);
 
-          call = Runtime::make_call(Runtime::BUILTIN_MEMMOVE, loc, 3,
-                                    a1, a2, a3);
+          Runtime::Function code = (element_type->has_pointer()
+                                    ? Runtime::MEMCLRHASPTR
+                                    : Runtime::MEMCLRNOPTR);
+          call = Runtime::make_call(code, loc, 2, a1, a2);
+
+          if (element_type->has_pointer())
+            {
+              // For a slice containing pointers, growslice already zeroed
+              // the memory. We only need to zero in non-growing case.
+              // Note: growslice does not zero the memory in non-pointer case.
+              Expression* left =
+                Expression::make_temporary_reference(ntmp, loc);
+              left = Expression::make_cast(uint_type, left, loc);
+              Expression* right =
+                Expression::make_temporary_reference(c1tmp, loc);
+              right = Expression::make_cast(uint_type, right, loc);
+              Expression* cond =
+                Expression::make_binary(OPERATOR_GT, left, right, loc);
+              Expression* zero = Expression::make_integer_ul(0, int_type, loc);
+              call = Expression::make_conditional(cond, call, zero, loc);
+            }
+        }
+      else
+        {
+          if (element_type->has_pointer())
+            {
+              // copy(s1tmp[l1tmp:], s2tmp)
+              a1 = Expression::make_temporary_reference(s1tmp, loc);
+              ref = Expression::make_temporary_reference(l1tmp, loc);
+              Expression* nil = Expression::make_nil(loc);
+              a1 = Expression::make_array_index(a1, ref, nil, NULL, loc);
+              a1->array_index_expression()->set_needs_bounds_check(false);
+
+              a2 = Expression::make_temporary_reference(s2tmp, loc);
+
+              Named_object* copyfn = gogo->lookup_global("copy");
+              Expression* copyref = Expression::make_func_reference(copyfn, NULL, loc);
+              call_args = new Expression_list();
+              call_args->push_back(a1);
+              call_args->push_back(a2);
+              call = Expression::make_call(copyref, call_args, false, loc);
+            }
+          else
+            {
+              // memmove(&s1tmp[l1tmp], s2tmp.ptr, l2tmp*sizeof(elem))
+              a1 = Expression::make_temporary_reference(s1tmp, loc);
+              ref = Expression::make_temporary_reference(l1tmp, loc);
+              a1 = Expression::make_array_index(a1, ref, NULL, NULL, loc);
+              a1->array_index_expression()->set_needs_bounds_check(false);
+              a1 = Expression::make_unary(OPERATOR_AND, a1, loc);
+
+              a2 = Expression::make_temporary_reference(s2tmp, loc);
+              a2 = (a2->type()->is_string_type()
+                    ? Expression::make_string_info(a2,
+                                                   STRING_INFO_DATA,
+                                                   loc)
+                    : Expression::make_slice_info(a2,
+                                                  SLICE_INFO_VALUE_POINTER,
+                                                  loc));
+
+              ref = Expression::make_temporary_reference(l2tmp, loc);
+              ref = Expression::make_cast(uintptr_type, ref, loc);
+              a3 = Expression::make_type_info(element_type, TYPE_INFO_SIZE);
+              a3 = Expression::make_binary(OPERATOR_MULT, a3, ref, loc);
+
+              call = Runtime::make_call(Runtime::BUILTIN_MEMMOVE, loc, 3,
+                                        a1, a2, a3);
+            }
         }
       gogo->lower_expression(function, inserter, &call);
       gogo->flatten_expression(function, inserter, &call);
@@ -16540,6 +16645,45 @@ Expression::make_slice_value(Type* at, Expression* valmem, Expression* len,
   return new Slice_value_expression(at, valmem, len, cap, location);
 }
 
+// Look through the expression of a Slice_value_expression's valmem to
+// find an call to makeslice.  If found, return the call expression and
+// the containing temporary statement (if any).
+
+std::pair<Call_expression*, Temporary_statement*>
+Expression::find_makeslice_call(Expression* expr)
+{
+  Unsafe_type_conversion_expression* utce =
+    expr->unsafe_conversion_expression();
+  if (utce != NULL)
+    expr = utce->expr();
+
+  Slice_value_expression* sve = expr->slice_value_expression();
+  if (sve == NULL)
+    return std::make_pair<Call_expression*, Temporary_statement*>(NULL, NULL);
+  expr = sve->valmem();
+
+  utce = expr->unsafe_conversion_expression();
+  if (utce != NULL)
+    expr = utce->expr();
+
+  Temporary_reference_expression* tre = expr->temporary_reference_expression();
+  Temporary_statement* ts = (tre != NULL ? tre->statement() : NULL);
+  if (ts != NULL && ts->init() != NULL && !ts->assigned()
+      && !ts->is_address_taken())
+    expr = ts->init();
+
+  Call_expression* call = expr->call_expression();
+  if (call == NULL)
+    return std::make_pair<Call_expression*, Temporary_statement*>(NULL, NULL);
+
+  Func_expression* fe = call->fn()->func_expression();
+  if (fe != NULL
+      && fe->runtime_code() == Runtime::MAKESLICE)
+    return std::make_pair(call, ts);
+
+  return std::make_pair<Call_expression*, Temporary_statement*>(NULL, NULL);
+}
+
 // An expression that evaluates to some characteristic of a non-empty interface.
 // This is used to access the method table or underlying object of an interface.
 
diff --git a/gcc/go/gofrontend/expressions.h b/gcc/go/gofrontend/expressions.h
index 3527d7a..ea98fac 100644
--- a/gcc/go/gofrontend/expressions.h
+++ b/gcc/go/gofrontend/expressions.h
@@ -1068,6 +1068,11 @@ class Expression
   static Expression*
   unpack_direct_iface(Expression*, Location);
 
+  // Look through the expression of a Slice_value_expression's valmem to
+  // find an call to makeslice.
+  static std::pair<Call_expression*, Temporary_statement*>
+  find_makeslice_call(Expression*);
+
   // Dump an expression to a dump constext.
   void
   dump_expression(Ast_dump_context*) const;
diff --git a/gcc/go/gofrontend/gogo.h b/gcc/go/gofrontend/gogo.h
index e67a8a5..fd28ed1 100644
--- a/gcc/go/gofrontend/gogo.h
+++ b/gcc/go/gofrontend/gogo.h
@@ -3627,21 +3627,24 @@ static const int RUNTIME_ERROR_STRING_SLICE_OUT_OF_BOUNDS = 5;
 // locations.
 static const int RUNTIME_ERROR_NIL_DEREFERENCE = 6;
 
-// Slice length or capacity out of bounds in make: negative or
-// overflow or length greater than capacity.
-static const int RUNTIME_ERROR_MAKE_SLICE_OUT_OF_BOUNDS = 7;
+// Slice length out of bounds in make: negative or overflow
+// or length greater than capacity.
+static const int RUNTIME_ERROR_MAKE_SLICE_LEN_OUT_OF_BOUNDS = 7;
+
+// Slice capacity out of bounds in make: negative.
+static const int RUNTIME_ERROR_MAKE_SLICE_CAP_OUT_OF_BOUNDS = 8;
 
 // Map capacity out of bounds in make: negative or overflow.
-static const int RUNTIME_ERROR_MAKE_MAP_OUT_OF_BOUNDS = 8;
+static const int RUNTIME_ERROR_MAKE_MAP_OUT_OF_BOUNDS = 9;
 
 // Channel capacity out of bounds in make: negative or overflow.
-static const int RUNTIME_ERROR_MAKE_CHAN_OUT_OF_BOUNDS = 9;
+static const int RUNTIME_ERROR_MAKE_CHAN_OUT_OF_BOUNDS = 10;
 
 // Division by zero.
-static const int RUNTIME_ERROR_DIVISION_BY_ZERO = 10;
+static const int RUNTIME_ERROR_DIVISION_BY_ZERO = 11;
 
 // Go statement with nil function.
-static const int RUNTIME_ERROR_GO_NIL = 11;
+static const int RUNTIME_ERROR_GO_NIL = 12;
 
 // This is used by some of the langhooks.
 extern Gogo* go_get_gogo();
diff --git a/gcc/go/gofrontend/statements.cc b/gcc/go/gofrontend/statements.cc
index e335489..fe9b748 100644
--- a/gcc/go/gofrontend/statements.cc
+++ b/gcc/go/gofrontend/statements.cc
@@ -1043,6 +1043,9 @@ Assignment_statement*
 Statement::make_assignment(Expression* lhs, Expression* rhs,
 			   Location location)
 {
+  Temporary_reference_expression* tre = lhs->temporary_reference_expression();
+  if (tre != NULL)
+    tre->statement()->set_assigned();
   return new Assignment_statement(lhs, rhs, location);
 }
 
diff --git a/gcc/go/gofrontend/statements.h b/gcc/go/gofrontend/statements.h
index 2985daa..d621a9a 100644
--- a/gcc/go/gofrontend/statements.h
+++ b/gcc/go/gofrontend/statements.h
@@ -675,7 +675,7 @@ class Temporary_statement : public Statement
   Temporary_statement(Type* type, Expression* init, Location location)
     : Statement(STATEMENT_TEMPORARY, location),
       type_(type), init_(init), bvariable_(NULL), is_address_taken_(false),
-      value_escapes_(false)
+      value_escapes_(false), assigned_(false), uses_(0)
   { }
 
   // Return the type of the temporary variable.
@@ -687,6 +687,17 @@ class Temporary_statement : public Statement
   init() const
   { return this->init_; }
 
+  // Set the initializer.
+  void
+  set_init(Expression* expr)
+  { this->init_ = expr; }
+
+  // Whether something takes the address of this temporary
+  // variable.
+  bool
+  is_address_taken()
+  { return this->is_address_taken_; }
+
   // Record that something takes the address of this temporary
   // variable.
   void
@@ -703,6 +714,26 @@ class Temporary_statement : public Statement
   set_value_escapes()
   { this->value_escapes_ = true; }
 
+  // Whether this temporary variable is assigned (after initialization).
+  bool
+  assigned()
+  { return this->assigned_; }
+
+  // Record that this temporary variable is assigned.
+  void
+  set_assigned()
+  { this->assigned_ = true; }
+
+  // Number of uses of this temporary variable.
+  int
+  uses()
+  { return this->uses_; }
+
+  // Add one use of this temporary variable.
+  void
+  add_use()
+  { this->uses_++; }
+
   // Return the temporary variable.  This should not be called until
   // after the statement itself has been converted.
   Bvariable*
@@ -745,6 +776,10 @@ class Temporary_statement : public Statement
   // True if the value assigned to this temporary variable escapes.
   // This is used for select statements.
   bool value_escapes_;
+  // True if this temporary variable is assigned (after initialization).
+  bool assigned_;
+  // Number of uses of this temporary variable.
+  int uses_;
 };
 
 // A variable declaration.  This marks the point in the code where a
diff --git a/gcc/go/gofrontend/wb.cc b/gcc/go/gofrontend/wb.cc
index 1d12269..2eae08f 100644
--- a/gcc/go/gofrontend/wb.cc
+++ b/gcc/go/gofrontend/wb.cc
@@ -41,9 +41,6 @@ class Mark_address_taken : public Traverse
   expression(Expression**);
 
  private:
-  Call_expression*
-  find_makeslice_call(Expression*);
-
   // General IR.
   Gogo* gogo_;
   // The function we are traversing.
@@ -100,31 +97,6 @@ Mark_address_taken::statement(Block* block, size_t* pindex, Statement* s)
   return TRAVERSE_CONTINUE;
 }
 
-// Look through the expression of a Slice_value_expression's valmem to
-// find an call to makeslice.
-
-Call_expression*
-Mark_address_taken::find_makeslice_call(Expression* expr)
-{
-  Unsafe_type_conversion_expression* utce =
-    expr->unsafe_conversion_expression();
-  if (utce != NULL)
-    expr = utce->expr();
-
-  Call_expression* call = expr->call_expression();
-  if (call == NULL)
-    return NULL;
-
-  Func_expression* fe = call->fn()->func_expression();
-  if (fe != NULL && fe->runtime_code() == Runtime::MAKESLICE)
-    return call;
-
-  // We don't worry about MAKESLICE64 bcause we don't want to use a
-  // stack allocation for a large slice anyhow.
-
-  return NULL;
-}
-
 // Mark variable addresses taken.
 
 int
@@ -173,7 +145,10 @@ Mark_address_taken::expression(Expression** pexpr)
   Slice_value_expression* sve = expr->slice_value_expression();
   if (sve != NULL)
     {
-      Call_expression* call = this->find_makeslice_call(sve->valmem());
+      std::pair<Call_expression*, Temporary_statement*> p =
+        Expression::find_makeslice_call(sve);
+      Call_expression* call = p.first;
+      Temporary_statement* ts = p.second;
       if (call != NULL
 	  && Node::make_node(call)->encoding() == Node::ESCAPE_NONE)
         {
@@ -203,6 +178,8 @@ Mark_address_taken::expression(Expression** pexpr)
 		Expression::make_slice_value(expr->type(), ptr, len_arg,
 					     cap_arg, loc);
               *pexpr = slice;
+              if (ts != NULL && ts->uses() == 1)
+                ts->set_init(Expression::make_nil(loc));
             }
         }
     }
diff --git a/libgo/runtime/go-runtime-error.c b/libgo/runtime/go-runtime-error.c
index 5db3555..c9ccf98 100644
--- a/libgo/runtime/go-runtime-error.c
+++ b/libgo/runtime/go-runtime-error.c
@@ -38,21 +38,24 @@ enum
      memory locations.  */
   NIL_DEREFERENCE = 6,
 
-  /* Slice length or capacity out of bounds in make: negative or
-     overflow or length greater than capacity.  */
-  MAKE_SLICE_OUT_OF_BOUNDS = 7,
+  /* Slice length out of bounds in make: negative or overflow or length
+     greater than capacity.  */
+  MAKE_SLICE_LEN_OUT_OF_BOUNDS = 7,
+
+  /* Slice capacity out of bounds in make: negative.  */
+  MAKE_SLICE_CAP_OUT_OF_BOUNDS = 8,
 
   /* Map capacity out of bounds in make: negative or overflow.  */
-  MAKE_MAP_OUT_OF_BOUNDS = 8,
+  MAKE_MAP_OUT_OF_BOUNDS = 9,
 
   /* Channel capacity out of bounds in make: negative or overflow.  */
-  MAKE_CHAN_OUT_OF_BOUNDS = 9,
+  MAKE_CHAN_OUT_OF_BOUNDS = 10,
 
   /* Integer division by zero.  */
-  DIVISION_BY_ZERO = 10,
+  DIVISION_BY_ZERO = 11,
 
   /* Go statement with nil function.  */
-  GO_NIL = 11
+  GO_NIL = 12
 };
 
 extern void __go_runtime_error (int32) __attribute__ ((noreturn));
@@ -88,8 +91,11 @@ __go_runtime_error (int32 i)
     case NIL_DEREFERENCE:
       runtime_panicstring ("nil pointer dereference");
 
-    case MAKE_SLICE_OUT_OF_BOUNDS:
-      runtime_panicstring ("make slice len or cap out of range");
+    case MAKE_SLICE_LEN_OUT_OF_BOUNDS:
+      runtime_panicstring ("make slice len out of range");
+
+    case MAKE_SLICE_CAP_OUT_OF_BOUNDS:
+      runtime_panicstring ("make slice cap out of range");
 
     case MAKE_MAP_OUT_OF_BOUNDS:
       runtime_panicstring ("make map len out of range");