Rewrite conversion of named types to backend representation.

git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@170627 138bc75d-0d04-0410-961f-82ee72b054a4

7 files changed, 576 insertions, 311 deletions

diff --git a/gcc/go/gofrontend/expressions.cc b/gcc/go/gofrontend/expressions.cc
index cebcbca7a07..ee486ffb27a 100644
--- a/gcc/go/gofrontend/expressions.cc
+++ b/gcc/go/gofrontend/expressions.cc
@@ -7013,6 +7013,8 @@ Builtin_call_expression::do_integer_constant_value(bool iota_is_constant,
 	return false;
       if (arg_type->is_abstract())
 	return false;
+      if (arg_type->named_type() != NULL)
+	arg_type->named_type()->convert(this->gogo_);
       tree arg_type_tree = arg_type->get_tree(this->gogo_);
       if (arg_type_tree == error_mark_node)
 	return false;
@@ -7057,6 +7059,8 @@ Builtin_call_expression::do_integer_constant_value(bool iota_is_constant,
       Type* st = struct_expr->type();
       if (st->struct_type() == NULL)
 	return false;
+      if (st->named_type() != NULL)
+	st->named_type()->convert(this->gogo_);
       tree struct_tree = st->get_tree(this->gogo_);
       gcc_assert(TREE_CODE(struct_tree) == RECORD_TYPE);
       tree field = TYPE_FIELDS(struct_tree);
@@ -8793,10 +8797,21 @@ Call_expression::do_get_tree(Translate_context* context)
       return error_mark_node;
     }
 
-  // This is to support builtin math functions when using 80387 math.
   tree fndecl = fn;
   if (TREE_CODE(fndecl) == ADDR_EXPR)
     fndecl = TREE_OPERAND(fndecl, 0);
+
+  // Add a type cast in case the type of the function is a recursive
+  // type which refers to itself.
+  if (!DECL_P(fndecl) || !DECL_IS_BUILTIN(fndecl))
+    {
+      tree fnt = fntype->get_tree(gogo);
+      if (fnt == error_mark_node)
+	return error_mark_node;
+      fn = fold_convert_loc(location, fnt, fn);
+    }
+
+  // This is to support builtin math functions when using 80387 math.
   tree excess_type = NULL_TREE;
   if (DECL_P(fndecl)
       && DECL_IS_BUILTIN(fndecl)
@@ -8842,7 +8857,7 @@ Call_expression::do_get_tree(Translate_context* context)
   // to the correct type.
   if (TREE_TYPE(ret) == ptr_type_node)
     {
-      tree t = this->type()->get_tree(gogo);
+      tree t = this->type()->base()->get_tree(gogo);
       ret = fold_convert_loc(location, t, ret);
     }
 
diff --git a/gcc/go/gofrontend/go.cc b/gcc/go/gofrontend/go.cc
index 2f30fd804b6..7b1fd7eccbb 100644
--- a/gcc/go/gofrontend/go.cc
+++ b/gcc/go/gofrontend/go.cc
@@ -118,9 +118,6 @@ go_parse_input_files(const char** filenames, unsigned int filename_count,
   // Export global identifiers as appropriate.
   ::gogo->do_exports();
 
-  // Build required interface method tables.
-  ::gogo->build_interface_method_tables();
-
   // Turn short-cut operators (&&, ||) into explicit if statements.
   ::gogo->remove_shortcuts();
 
diff --git a/gcc/go/gofrontend/gogo-tree.cc b/gcc/go/gofrontend/gogo-tree.cc
index 3228c42ec3b..722a23a52d7 100644
--- a/gcc/go/gofrontend/gogo-tree.cc
+++ b/gcc/go/gofrontend/gogo-tree.cc
@@ -640,6 +640,9 @@ sort_var_inits(Var_inits* var_inits)
 void
 Gogo::write_globals()
 {
+  this->convert_named_types();
+  this->build_interface_method_tables();
+
   Bindings* bindings = this->current_bindings();
   size_t count = bindings->size_definitions();
 
diff --git a/gcc/go/gofrontend/gogo.cc b/gcc/go/gofrontend/gogo.cc
index a63abfefde3..bb2fcab8230 100644
--- a/gcc/go/gofrontend/gogo.cc
+++ b/gcc/go/gofrontend/gogo.cc
@@ -34,7 +34,8 @@ Gogo::Gogo(int int_type_size, int pointer_size)
     imported_init_fns_(),
     unique_prefix_(),
     unique_prefix_specified_(false),
-    interface_types_()
+    interface_types_(),
+    named_types_are_converted_(false)
 {
   const source_location loc = BUILTINS_LOCATION;
 
@@ -1119,11 +1120,6 @@ class Verify_types : public Traverse
 int
 Verify_types::type(Type* t)
 {
-  // Don't verify types defined in other packages.
-  Named_type* nt = t->named_type();
-  if (nt != NULL && nt->named_object()->package() != NULL)
-    return TRAVERSE_SKIP_COMPONENTS;
-
   if (!t->verify())
     return TRAVERSE_SKIP_COMPONENTS;
   return TRAVERSE_CONTINUE;
@@ -2520,6 +2516,83 @@ Gogo::do_exports()
 		     this->package_->bindings());
 }
 
+// Find the blocks in order to convert named types defined in blocks.
+
+class Convert_named_types : public Traverse
+{
+ public:
+  Convert_named_types(Gogo* gogo)
+    : Traverse(traverse_blocks),
+      gogo_(gogo)
+  { }
+
+ protected:
+  int
+  block(Block* block);
+
+ private:
+  Gogo* gogo_;
+};
+
+int
+Convert_named_types::block(Block* block)
+{
+  this->gogo_->convert_named_types_in_bindings(block->bindings());
+  return TRAVERSE_CONTINUE;
+}
+
+// Convert all named types to the backend representation.  Since named
+// types can refer to other types, this needs to be done in the right
+// sequence, which is handled by Named_type::convert.  Here we arrange
+// to call that for each named type.
+
+void
+Gogo::convert_named_types()
+{
+  this->convert_named_types_in_bindings(this->globals_);
+  for (Packages::iterator p = this->packages_.begin();
+       p != this->packages_.end();
+       ++p)
+    {
+      Package* package = p->second;
+      this->convert_named_types_in_bindings(package->bindings());
+    }
+
+  Convert_named_types cnt(this);
+  this->traverse(&cnt);
+
+  // Make all the builtin named types used for type descriptors, and
+  // then convert them.  They will only be written out if they are
+  // needed.
+  Type::make_type_descriptor_type();
+  Type::make_type_descriptor_ptr_type();
+  Function_type::make_function_type_descriptor_type();
+  Pointer_type::make_pointer_type_descriptor_type();
+  Struct_type::make_struct_type_descriptor_type();
+  Array_type::make_array_type_descriptor_type();
+  Array_type::make_slice_type_descriptor_type();
+  Map_type::make_map_type_descriptor_type();
+  Channel_type::make_chan_type_descriptor_type();
+  Interface_type::make_interface_type_descriptor_type();
+  Type::convert_builtin_named_types(this);
+
+  this->named_types_are_converted_ = true;
+}
+
+// Convert all names types in a set of bindings.
+
+void
+Gogo::convert_named_types_in_bindings(Bindings* bindings)
+{
+  for (Bindings::const_definitions_iterator p = bindings->begin_definitions();
+       p != bindings->end_definitions();
+       ++p)
+    {
+      if ((*p)->is_type())
+	(*p)->type_value()->convert(this);
+    }
+}
+
 // Class Function.
 
 Function::Function(Function_type* type, Function* enclosing, Block* block,
diff --git a/gcc/go/gofrontend/gogo.h b/gcc/go/gofrontend/gogo.h
index 57928d6600b..8db802ea53e 100644
--- a/gcc/go/gofrontend/gogo.h
+++ b/gcc/go/gofrontend/gogo.h
@@ -405,6 +405,20 @@ class Gogo
   void
   simplify_thunk_statements();
 
+  // Convert named types to the backend representation.
+  void
+  convert_named_types();
+
+  // Convert named types in a list of bindings.
+  void
+  convert_named_types_in_bindings(Bindings*);
+
+  // True if named types have been converted to the backend
+  // representation.
+  bool
+  named_types_are_converted() const
+  { return this->named_types_are_converted_; }
+
   // Write out the global values.
   void
   write_globals();
@@ -661,6 +675,8 @@ class Gogo
   bool unique_prefix_specified_;
   // A list of interface types defined while parsing.
   std::vector<Interface_type*> interface_types_;
+  // Whether named types have been converted.
+  bool named_types_are_converted_;
 };
 
 // A block of statements.
diff --git a/gcc/go/gofrontend/types.cc b/gcc/go/gofrontend/types.cc
index 3e149b93734..368ecae127a 100644
--- a/gcc/go/gofrontend/types.cc
+++ b/gcc/go/gofrontend/types.cc
@@ -835,8 +835,9 @@ Type::get_tree(Gogo* gogo)
     Type::type_trees.insert(val);
   if (!ins.second && ins.first->second != NULL_TREE)
     {
-      this->tree_ = ins.first->second;
-      return this->tree_;
+      if (gogo != NULL && gogo->named_types_are_converted())
+	this->tree_ = ins.first->second;
+      return ins.first->second;
     }
 
   tree t = this->get_tree_without_hash(gogo);
@@ -850,6 +851,8 @@ Type::get_tree(Gogo* gogo)
       // which in turns uses an identical unnamed type.  Use the tree
       // we created earlier and ignore the one we just built.
       t = ins.first->second;
+      if (gogo == NULL || !gogo->named_types_are_converted())
+	return t;
       this->tree_ = t;
     }
 
@@ -874,6 +877,9 @@ Type::get_tree_without_hash(Gogo* gogo)
       if (t == ptr_type_node && this->forward_declaration_type() != NULL)
 	return t;
 
+      if (gogo == NULL || !gogo->named_types_are_converted())
+	return t;
+
       this->tree_ = t;
       go_preserve_from_gc(t);
     }
@@ -961,6 +967,10 @@ Type::make_builtin_struct_type(int nfields, ...)
   return Type::make_struct_type(sfl, bloc);
 }
 
+// A list of builtin named types.
+
+std::vector<Named_type*> Type::named_builtin_types;
+
 // Make a builtin named type.
 
 Named_type*
@@ -968,7 +978,25 @@ Type::make_builtin_named_type(const char* name, Type* type)
 {
   source_location bloc = BUILTINS_LOCATION;
   Named_object* no = Named_object::make_type(name, NULL, type, bloc);
-  return no->type_value();
+  Named_type* ret = no->type_value();
+  Type::named_builtin_types.push_back(ret);
+  return ret;
+}
+
+// Convert the named builtin types.
+
+void
+Type::convert_builtin_named_types(Gogo* gogo)
+{
+  for (std::vector<Named_type*>::const_iterator p =
+	 Type::named_builtin_types.begin();
+       p != Type::named_builtin_types.end();
+       ++p)
+    {
+      bool r = (*p)->verify();
+      gcc_assert(r);
+      (*p)->convert(gogo);
+    }
 }
 
 // Return the type of a type descriptor.  We should really tie this to
@@ -3309,20 +3337,10 @@ Call_multiple_result_type::do_get_tree(Gogo* gogo)
   gcc_assert(fntype != NULL);
   const Typed_identifier_list* results = fntype->results();
   gcc_assert(results != NULL && results->size() > 1);
-
-  Struct_field_list* sfl = new Struct_field_list;
-  for (Typed_identifier_list::const_iterator p = results->begin();
-       p != results->end();
-       ++p)
-    {
-      const std::string name = ((p->name().empty()
-				 || p->name() == Import::import_marker)
-				? "UNNAMED"
-				: p->name());
-      sfl->push_back(Struct_field(Typed_identifier(name, p->type(),
-						   this->call_->location())));
-    }
-  return Type::make_struct_type(sfl, this->call_->location())->get_tree(gogo);
+  tree fntype_tree = fntype->get_tree(gogo);
+  if (fntype_tree == error_mark_node)
+    return error_mark_node;
+  return TREE_TYPE(fntype_tree);
 }
 
 // Make a call result type.
@@ -3782,7 +3800,6 @@ Struct_type::fill_in_tree(Gogo* gogo, tree type)
 {
   tree field_trees = NULL_TREE;
   tree* pp = &field_trees;
-  bool has_pointer = false;
   for (Struct_field_list::const_iterator p = this->fields_->begin();
        p != this->fields_->end();
        ++p)
@@ -3790,20 +3807,10 @@ Struct_type::fill_in_tree(Gogo* gogo, tree type)
       std::string name = Gogo::unpack_hidden_name(p->field_name());
       tree name_tree = get_identifier_with_length(name.data(), name.length());
 
-      // Don't follow pointers yet, so that we don't get confused by a
-      // pointer to an array of this struct type.
-      tree field_type_tree;
-      if (p->type()->points_to() != NULL || p->type()->function_type() != NULL)
-	{
-	  field_type_tree = ptr_type_node;
-	  has_pointer = true;
-	}
-      else
-	{
-	  field_type_tree = p->type()->get_tree(gogo);
-	  if (field_type_tree == error_mark_node)
-	    return error_mark_node;
-	}
+      tree field_type_tree = p->type()->get_tree(gogo);
+      if (field_type_tree == error_mark_node)
+	return error_mark_node;
+      gcc_assert(TYPE_SIZE(field_type_tree) != NULL_TREE);
 
       tree field = build_decl(p->location(), FIELD_DECL, name_tree,
 			      field_type_tree);
@@ -3816,35 +3823,9 @@ Struct_type::fill_in_tree(Gogo* gogo, tree type)
 
   layout_type(type);
 
-  if (has_pointer)
-    {
-      tree field = field_trees;
-      for (Struct_field_list::const_iterator p = this->fields_->begin();
-	   p != this->fields_->end();
-	   ++p, field = DECL_CHAIN(field))
-	{
-	  if (p->type()->points_to() != NULL
-	      || p->type()->function_type() != NULL)
-	    TREE_TYPE(field) = p->type()->get_tree(gogo);
-	}
-    }
-
   return type;
 }
 
-// Make sure that all structs which must be converted to the backend
-// representation before this one are in fact converted.
-
-void
-Struct_type::convert_prerequisites(Gogo* gogo)
-{
-  for (std::vector<Named_type*>::const_iterator p
-	 = this->prerequisites_.begin();
-       p != this->prerequisites_.end();
-       ++p)
-    (*p)->get_tree(gogo);
-}
-
 // Initialize struct fields.
 
 tree
@@ -4487,6 +4468,8 @@ Array_type::fill_in_array_tree(Gogo* gogo, tree array_type)
       || length_tree == error_mark_node)
     return error_mark_node;
 
+  gcc_assert(TYPE_SIZE(element_type_tree) != NULL_TREE);
+
   length_tree = fold_convert(sizetype, length_tree);
 
   // build_index_type takes the maximum index, which is one less than
@@ -6074,70 +6057,86 @@ tree
 Interface_type::do_get_tree(Gogo* gogo)
 {
   if (this->methods_ == NULL)
+    return Interface_type::empty_type_tree(gogo);
+  else
     {
-      // At the tree level, use the same type for all empty
-      // interfaces.  This lets us assign them to each other directly
-      // without triggering GIMPLE type errors.
-      tree dtype = Type::make_type_descriptor_type()->get_tree(gogo);
-      dtype = build_pointer_type(build_qualified_type(dtype, TYPE_QUAL_CONST));
-      static tree empty_interface;
-      return Gogo::builtin_struct(&empty_interface, "__go_empty_interface",
-				  NULL_TREE, 2,
-				  "__type_descriptor",
-				  dtype,
-				  "__object",
-				  ptr_type_node);
+      tree t = Interface_type::non_empty_type_tree(this->location_);
+      return this->fill_in_tree(gogo, t);
     }
-
-  return this->fill_in_tree(gogo, make_node(RECORD_TYPE));
 }
 
-// Fill in the tree for an interface type.  This is used for named
-// interface types.
+// Return a singleton struct for an empty interface type.  We use the
+// same type for all empty interfaces.  This lets us assign them to
+// each other directly without triggering GIMPLE type errors.
 
 tree
-Interface_type::fill_in_tree(Gogo* gogo, tree type)
+Interface_type::empty_type_tree(Gogo* gogo)
 {
-  gcc_assert(this->methods_ != NULL);
+  static tree empty_interface;
+  if (empty_interface != NULL_TREE)
+    return empty_interface;
+
+  tree dtype = Type::make_type_descriptor_type()->get_tree(gogo);
+  dtype = build_pointer_type(build_qualified_type(dtype, TYPE_QUAL_CONST));
+  return Gogo::builtin_struct(&empty_interface, "__go_empty_interface",
+			      NULL_TREE, 2,
+			      "__type_descriptor",
+			      dtype,
+			      "__object",
+			      ptr_type_node);
+}
 
-  // Because the methods may refer to the interface type itself, we
-  // need to build the interface type first, and then update the
-  // method pointer later.
+// Return a new struct for a non-empty interface type.  The correct
+// values are filled in by fill_in_tree.
+
+tree
+Interface_type::non_empty_type_tree(source_location location)
+{
+  tree ret = make_node(RECORD_TYPE);
 
   tree field_trees = NULL_TREE;
   tree* pp = &field_trees;
 
   tree name_tree = get_identifier("__methods");
-  tree methods_field = build_decl(this->location_, FIELD_DECL, name_tree,
-				  ptr_type_node);
-  DECL_CONTEXT(methods_field) = type;
-  *pp = methods_field;
-  pp = &DECL_CHAIN(methods_field);
+  tree field = build_decl(location, FIELD_DECL, name_tree, ptr_type_node);
+  DECL_CONTEXT(field) = ret;
+  *pp = field;
+  pp = &DECL_CHAIN(field);
 
   name_tree = get_identifier("__object");
-  tree field = build_decl(this->location_, FIELD_DECL, name_tree,
-			  ptr_type_node);
-  DECL_CONTEXT(field) = type;
+  field = build_decl(location, FIELD_DECL, name_tree, ptr_type_node);
+  DECL_CONTEXT(field) = ret;
   *pp = field;
 
-  TYPE_FIELDS(type) = field_trees;
+  TYPE_FIELDS(ret) = field_trees;
 
-  layout_type(type);
+  layout_type(ret);
+
+  return ret;
+}
+
+// Fill in the tree for an interface type.  This is used for named
+// interface types.
+
+tree
+Interface_type::fill_in_tree(Gogo* gogo, tree type)
+{
+  gcc_assert(this->methods_ != NULL);
 
   // Build the type of the table of methods.
 
   tree method_table = make_node(RECORD_TYPE);
 
   // The first field is a pointer to the type descriptor.
-  name_tree = get_identifier("__type_descriptor");
+  tree name_tree = get_identifier("__type_descriptor");
   tree dtype = Type::make_type_descriptor_type()->get_tree(gogo);
   dtype = build_pointer_type(build_qualified_type(dtype, TYPE_QUAL_CONST));
-  field = build_decl(this->location_, FIELD_DECL, name_tree, dtype);
+  tree field = build_decl(this->location_, FIELD_DECL, name_tree, dtype);
   DECL_CONTEXT(field) = method_table;
   TYPE_FIELDS(method_table) = field;
 
   std::string last_name = "";
-  pp = &DECL_CHAIN(field);
+  tree* pp = &DECL_CHAIN(field);
   for (Typed_identifier_list::const_iterator p = this->methods_->begin();
        p != this->methods_->end();
        ++p)
@@ -6159,7 +6158,10 @@ Interface_type::fill_in_tree(Gogo* gogo, tree type)
 
   // Update the type of the __methods field from a generic pointer to
   // a pointer to the method table.
-  TREE_TYPE(methods_field) = build_pointer_type(method_table);
+  field = TYPE_FIELDS(type);
+  gcc_assert(strcmp(IDENTIFIER_POINTER(DECL_NAME(field)), "__methods") == 0);
+
+  TREE_TYPE(field) = build_pointer_type(method_table);
 
   return type;
 }
@@ -6876,7 +6878,7 @@ Named_type::named_type_has_hidden_fields(std::string* reason) const
 class Find_type_use : public Traverse
 {
  public:
-  Find_type_use(Type* find_type)
+  Find_type_use(Named_type* find_type)
     : Traverse(traverse_types),
       find_type_(find_type), found_(false)
   { }
@@ -6892,7 +6894,7 @@ class Find_type_use : public Traverse
 
  private:
   // The type we are looking for.
-  Type* find_type_;
+  Named_type* find_type_;
   // Whether we found the type.
   bool found_;
 };
@@ -6902,11 +6904,12 @@ class Find_type_use : public Traverse
 int
 Find_type_use::type(Type* type)
 {
-  if (this->find_type_ == type)
+  if (type->named_type() != NULL && this->find_type_ == type->named_type())
     {
       this->found_ = true;
       return TRAVERSE_EXIT;
     }
+
   // It's OK if we see a reference to the type in any type which is
   // essentially a pointer: a pointer, a slice, a function, a map, or
   // a channel.
@@ -6940,6 +6943,42 @@ Find_type_use::type(Type* type)
       return TRAVERSE_SKIP_COMPONENTS;
     }
 
+  // Otherwise, FIND_TYPE_ depends on TYPE, in the sense that we need
+  // to convert TYPE to the backend representation before we convert
+  // FIND_TYPE_.
+  if (type->named_type() != NULL)
+    {
+      switch (type->base()->classification())
+	{
+	case Type::TYPE_ERROR:
+	case Type::TYPE_BOOLEAN:
+	case Type::TYPE_INTEGER:
+	case Type::TYPE_FLOAT:
+	case Type::TYPE_COMPLEX:
+	case Type::TYPE_STRING:
+	case Type::TYPE_NIL:
+	  break;
+
+	case Type::TYPE_ARRAY:
+	case Type::TYPE_STRUCT:
+	  this->find_type_->add_dependency(type->named_type());
+	  break;
+
+	case Type::TYPE_VOID:
+	case Type::TYPE_SINK:
+	case Type::TYPE_FUNCTION:
+	case Type::TYPE_POINTER:
+	case Type::TYPE_CALL_MULTIPLE_RESULT:
+	case Type::TYPE_MAP:
+	case Type::TYPE_CHANNEL:
+	case Type::TYPE_INTERFACE:
+	case Type::TYPE_NAMED:
+	case Type::TYPE_FORWARD:
+	default:
+	  gcc_unreachable();
+	}
+    }
+
   return TRAVERSE_CONTINUE;
 }
 
@@ -6995,36 +7034,6 @@ Named_type::do_verify()
 	return false;
     }
 
-  // If this is a struct, then if any of the fields of the struct
-  // themselves have struct type, or array of struct type, then this
-  // struct must be converted to the backend representation before the
-  // field's type is converted.  That may seem backward, but it works
-  // because if the field's type refers to this one, e.g., via a
-  // pointer, then the conversion process will pick up the half-built
-  // struct and do the right thing.
-  if (this->struct_type() != NULL)
-    {
-      const Struct_field_list* fields = this->struct_type()->fields();
-      for (Struct_field_list::const_iterator p = fields->begin();
-	   p != fields->end();
-	   ++p)
-	{
-	  Struct_type* st = p->type()->struct_type();
-	  if (st != NULL)
-	    st->add_prerequisite(this);
-	  else
-	    {
-	      Array_type* at = p->type()->array_type();
-	      if (at != NULL && !at->is_open_array_type())
-		{
-		  st = at->element_type()->struct_type();
-		  if (st != NULL)
-		    st->add_prerequisite(this);
-		}
-	    }
-	}
-    }
-
   return true;
 }
 
@@ -7074,21 +7083,109 @@ Named_type::do_hash_for_method(Gogo* gogo) const
   return ret;
 }
 
-// Get a tree for a named type.
+// Convert a named type to the backend representation.  In order to
+// get dependencies right, we fill in a dummy structure for this type,
+// then convert all the dependencies, then complete this type.  When
+// this function is complete, the size of the type is known.
 
-tree
-Named_type::do_get_tree(Gogo* gogo)
+void
+Named_type::convert(Gogo* gogo)
+{
+  if (this->is_error_ || this->is_converted_)
+    return;
+
+  this->create_placeholder(gogo);
+
+  // Convert all the dependencies.  If they refer indirectly back to
+  // this type, they will pick up the intermediate tree we just
+  // created.
+  for (std::vector<Named_type*>::const_iterator p = this->dependencies_.begin();
+       p != this->dependencies_.end();
+       ++p)
+    (*p)->convert(gogo);
+
+  // Complete this type.
+  tree t = this->named_tree_;
+  Type* base = this->type_->base();
+  switch (base->classification())
+    {
+    case TYPE_VOID:
+    case TYPE_BOOLEAN:
+    case TYPE_INTEGER:
+    case TYPE_FLOAT:
+    case TYPE_COMPLEX:
+    case TYPE_STRING:
+    case TYPE_NIL:
+      break;
+
+    case TYPE_MAP:
+    case TYPE_CHANNEL:
+      break;
+
+    case TYPE_FUNCTION:
+    case TYPE_POINTER:
+      // The size of these types is already correct.
+      break;
+
+    case TYPE_STRUCT:
+      t = base->struct_type()->fill_in_tree(gogo, t);
+      break;
+
+    case TYPE_ARRAY:
+      if (!base->is_open_array_type())
+	t = base->array_type()->fill_in_array_tree(gogo, t);
+      break;
+
+    case TYPE_INTERFACE:
+      if (!base->interface_type()->is_empty())
+	t = base->interface_type()->fill_in_tree(gogo, t);
+      break;
+
+    case TYPE_ERROR:
+      return;
+
+    default:
+    case TYPE_SINK:
+    case TYPE_CALL_MULTIPLE_RESULT:
+    case TYPE_NAMED:
+    case TYPE_FORWARD:
+      gcc_unreachable();
+    }
+
+  this->named_tree_ = t;
+
+  if (t == error_mark_node)
+    this->is_error_ = true;
+  else
+    gcc_assert(TYPE_SIZE(t) != NULL_TREE);
+
+  this->is_converted_ = true;
+}
+
+// Create the placeholder for a named type.  This is the first step in
+// converting to the backend representation.
+
+void
+Named_type::create_placeholder(Gogo* gogo)
 {
   if (this->is_error_)
-    return error_mark_node;
+    this->named_tree_ = error_mark_node;
 
-  // Go permits types to refer to themselves in various ways.  Break
-  // the recursion here.
+  if (this->named_tree_ != NULL_TREE)
+    return;
+
+  // Create the structure for this type.  Note that because we call
+  // base() here, we don't attempt to represent a named type defined
+  // as another named type.  Instead both named types will point to
+  // different base representations.
+  Type* base = this->type_->base();
   tree t;
-  switch (this->type_->forwarded()->classification())
+  switch (base->classification())
     {
     case TYPE_ERROR:
-      return error_mark_node;
+      this->is_error_ = true;
+      this->named_tree_ = error_mark_node;
+      return;
 
     case TYPE_VOID:
     case TYPE_BOOLEAN:
@@ -7097,163 +7194,194 @@ Named_type::do_get_tree(Gogo* gogo)
     case TYPE_COMPLEX:
     case TYPE_STRING:
     case TYPE_NIL:
-      // These types can not refer to themselves.
-    case TYPE_MAP:
-    case TYPE_CHANNEL:
-      // All maps and channels have the same type in GENERIC.
-      t = Type::get_named_type_tree(gogo, this->type_);
+      // These are simple basic types, we can just create them
+      // directly.
+      t = Type::get_named_type_tree(gogo, base);
       if (t == error_mark_node)
-	return error_mark_node;
-      // Build a copy to set TYPE_NAME.
+	{
+	  this->is_error_ = true;
+	  this->named_tree_ = error_mark_node;
+	  return;
+	}
       t = build_variant_type_copy(t);
       break;
 
-    case TYPE_FUNCTION:
-      // GENERIC can't handle a pointer to a function type whose
-      // return type is a pointer to the function type itself.  It
-      // goes into an infinite loop when walking the types.
-      if (this->seen_ > 0)
+    case TYPE_MAP:
+    case TYPE_CHANNEL:
+      // All maps and channels have the same type in GENERIC.
+      t = Type::get_named_type_tree(gogo, base);
+      if (t == error_mark_node)
 	{
-	  Function_type* fntype = this->type_->function_type();
-	  if (fntype->results() != NULL
-	      && fntype->results()->size() == 1
-	      && fntype->results()->front().type()->forwarded() == this)
-	    return ptr_type_node;
-
-	  // We can legitimately see ourselves here twice when a named
-	  // type is defined using a struct which refers to the named
-	  // type.  If we see ourselves too often we are in a loop.
-	  if (this->seen_ > 3)
-	    return ptr_type_node;
+	  this->is_error_ = true;
+	  this->named_tree_ = error_mark_node;
+	  return;
 	}
-      ++this->seen_;
-      t = Type::get_named_type_tree(gogo, this->type_);
-      --this->seen_;
-      if (t == error_mark_node)
-	return error_mark_node;
       t = build_variant_type_copy(t);
       break;
 
+    case TYPE_FUNCTION:
     case TYPE_POINTER:
-      // Don't recur infinitely if a pointer type refers to itself.
-      // Ideally we would build a circular data structure here, but
-      // GENERIC can't handle them.
-      if (this->seen_ > 0)
-	{
-	  if (this->type_->points_to()->forwarded() == this)
-	    return ptr_type_node;
-
-	  if (this->seen_ > 3)
-	    return ptr_type_node;
-	}
-      ++this->seen_;
-      t = Type::get_named_type_tree(gogo, this->type_);
-      --this->seen_;
-      if (t == error_mark_node)
-	return error_mark_node;
-      t = build_variant_type_copy(t);
+      t = build_variant_type_copy(ptr_type_node);
       break;
 
     case TYPE_STRUCT:
-      // If there are structs which must be converted first, do them.
-      if (this->seen_ == 0)
-	{
-	  ++this->seen_;
-	  this->type_->struct_type()->convert_prerequisites(gogo);
-	  --this->seen_;
-	}
-
-      if (this->named_tree_ != NULL_TREE)
-	return this->named_tree_;
-
       t = make_node(RECORD_TYPE);
-      this->named_tree_ = t;
-      t = this->type_->struct_type()->fill_in_tree(gogo, t);
-      if (t == error_mark_node)
-	{
-	  this->named_tree_ = error_mark_node;
-	  return error_mark_node;
-	}
       break;
 
     case TYPE_ARRAY:
-      if (this->named_tree_ != NULL_TREE)
-	return this->named_tree_;
-      if (!this->is_open_array_type())
-	{
-	  t = make_node(ARRAY_TYPE);
-	  this->named_tree_ = t;
-	  t = this->type_->array_type()->fill_in_array_tree(gogo, t);
-	}
+      if (base->is_open_array_type())
+	t = gogo->slice_type_tree(void_type_node);
       else
-	{
-	  t = gogo->slice_type_tree(void_type_node);
-	  this->named_tree_ = t;
-	  t = this->type_->array_type()->fill_in_slice_tree(gogo, t);
-	}
-      if (t == error_mark_node)
-	return error_mark_node;
-      t = build_variant_type_copy(t);
+	t = make_node(ARRAY_TYPE);
       break;
 
     case TYPE_INTERFACE:
-      if (this->type_->interface_type()->is_empty())
+      if (base->interface_type()->is_empty())
 	{
-	  t = Type::get_named_type_tree(gogo, this->type_);
-	  if (t == error_mark_node)
-	    return error_mark_node;
+	  t = Interface_type::empty_type_tree(gogo);
 	  t = build_variant_type_copy(t);
 	}
       else
 	{
-	  if (this->named_tree_ != NULL_TREE)
-	    return this->named_tree_;
-	  t = make_node(RECORD_TYPE);
-	  this->named_tree_ = t;
-	  t = this->type_->interface_type()->fill_in_tree(gogo, t);
-	  if (t == error_mark_node)
-	    {
-	      this->named_tree_ = error_mark_node;
-	      return error_mark_node;
-	    }
+	  source_location loc = base->interface_type()->location();
+	  t = Interface_type::non_empty_type_tree(loc);
 	}
       break;
 
-    case TYPE_NAMED:
-      {
-	// When a named type T1 is defined as another named type T2,
-	// the definition must simply be "type T1 T2".  If the
-	// definition of T2 may refer to T1, then we must simply
-	// return the type for T2 here.  It's not precisely correct,
-	// but it's as close as we can get with GENERIC.
-	++this->seen_;
-	t = Type::get_named_type_tree(gogo, this->type_);
-	--this->seen_;
-	if (this->seen_ > 0)
-	  return t;
-	if (t == error_mark_node)
-	  return error_mark_node;
-	t = build_variant_type_copy(t);
-      }
-      break;
-
-    case TYPE_FORWARD:
-      // An undefined forwarding type.  Make sure the error is
-      // emitted.
-      this->type_->forward_declaration_type()->real_type();
-      return error_mark_node;
-
     default:
     case TYPE_SINK:
     case TYPE_CALL_MULTIPLE_RESULT:
+    case TYPE_NAMED:
+    case TYPE_FORWARD:
       gcc_unreachable();
     }
 
+  // Create the named type.
+
   tree id = this->named_object_->get_id(gogo);
   tree decl = build_decl(this->location_, TYPE_DECL, id, t);
   TYPE_NAME(t) = decl;
 
-  return t;
+  this->named_tree_ = t;
+}
+
+// Get a tree for a named type.
+
+tree
+Named_type::do_get_tree(Gogo* gogo)
+{
+  if (this->is_error_)
+    return error_mark_node;
+
+  tree t = this->named_tree_;
+
+  // FIXME: GOGO can be NULL when called from go_type_for_size, which
+  // is only used for basic types.
+  if (gogo == NULL || !gogo->named_types_are_converted())
+    {
+      // We have not completed converting named types.  NAMED_TREE_ is
+      // a placeholder and we shouldn't do anything further.
+      if (t != NULL_TREE)
+	return t;
+
+      // We don't build dependencies for types whose sizes do not
+      // change or are not relevant, so we may see them here while
+      // converting types.
+      this->create_placeholder(gogo);
+      t = this->named_tree_;
+      gcc_assert(t != NULL_TREE);
+      return t;
+    }
+
+  // We are not converting types.  This should only be called if the
+  // type has already been converted.
+  gcc_assert(this->is_converted_);
+  gcc_assert(t != NULL_TREE && TYPE_SIZE(t) != NULL_TREE);
+
+  // Complete the tree.
+  Type* base = this->type_->base();
+  tree t1;
+  switch (base->classification())
+    {
+    case TYPE_ERROR:
+      return error_mark_node;
+
+    case TYPE_VOID:
+    case TYPE_BOOLEAN:
+    case TYPE_INTEGER:
+    case TYPE_FLOAT:
+    case TYPE_COMPLEX:
+    case TYPE_STRING:
+    case TYPE_NIL:
+    case TYPE_MAP:
+    case TYPE_CHANNEL:
+    case TYPE_STRUCT:
+    case TYPE_INTERFACE:
+      return t;
+
+    case TYPE_FUNCTION:
+      // Don't build a circular data structure.  GENERIC can't handle
+      // it.
+      if (this->seen_ > 0)
+	{
+	  this->is_circular_ = true;
+	  return ptr_type_node;
+	}
+      ++this->seen_;
+      t1 = Type::get_named_type_tree(gogo, base);
+      --this->seen_;
+      if (t1 == error_mark_node)
+	return error_mark_node;
+      if (this->is_circular_)
+	t1 = ptr_type_node;
+      gcc_assert(t != NULL_TREE && TREE_CODE(t) == POINTER_TYPE);
+      gcc_assert(TREE_CODE(t1) == POINTER_TYPE);
+      TREE_TYPE(t) = TREE_TYPE(t1);
+      return t;
+
+    case TYPE_POINTER:
+      // Don't build a circular data structure. GENERIC can't handle
+      // it.
+      if (this->seen_ > 0)
+	{
+	  this->is_circular_ = true;
+	  return ptr_type_node;
+	}
+      ++this->seen_;
+      t1 = Type::get_named_type_tree(gogo, base);
+      --this->seen_;
+      if (t1 == error_mark_node)
+	return error_mark_node;
+      if (this->is_circular_)
+	t1 = ptr_type_node;
+      gcc_assert(t != NULL_TREE && TREE_CODE(t) == POINTER_TYPE);
+      gcc_assert(TREE_CODE(t1) == POINTER_TYPE);
+      TREE_TYPE(t) = TREE_TYPE(t1);
+      return t;
+
+    case TYPE_ARRAY:
+      if (base->is_open_array_type())
+	{
+	  if (this->seen_ > 0)
+	    return t;
+	  else
+	    {
+	      ++this->seen_;
+	      t = base->array_type()->fill_in_slice_tree(gogo, t);
+	      --this->seen_;
+	    }
+	}
+      return t;
+
+    default:
+    case TYPE_SINK:
+    case TYPE_CALL_MULTIPLE_RESULT:
+    case TYPE_NAMED:
+    case TYPE_FORWARD:
+      gcc_unreachable();
+    }
+
+  gcc_unreachable();
 }
 
 // Build a type descriptor for a named type.
diff --git a/gcc/go/gofrontend/types.h b/gcc/go/gofrontend/types.h
index b0dbefed455..8e91dfcab07 100644
--- a/gcc/go/gofrontend/types.h
+++ b/gcc/go/gofrontend/types.h
@@ -799,6 +799,10 @@ class Type
   check_make_expression(Expression_list* args, source_location location)
   { return this->do_check_make_expression(args, location); }
 
+  // Convert the builtin named types.
+  static void
+  convert_builtin_named_types(Gogo*);
+
   // Return a tree representing this type.
   tree
   get_tree(Gogo*);
@@ -1082,6 +1086,9 @@ class Type
 
   static Type_trees type_trees;
 
+  // A list of builtin named types.
+  static std::vector<Named_type*> named_builtin_types;
+
   // The type classification.
   Type_classification classification_;
   // The tree representation of the type, once it has been determined.
@@ -1605,6 +1612,9 @@ class Function_type : public Type
   Function_type*
   copy_with_receiver(Type*) const;
 
+  static Type*
+  make_function_type_descriptor_type();
+
  protected:
   int
   do_traverse(Traverse*);
@@ -1636,9 +1646,6 @@ class Function_type : public Type
   do_export(Export*) const;
 
  private:
-  static Type*
-  make_function_type_descriptor_type();
-
   Expression*
   type_descriptor_params(Type*, const Typed_identifier*,
 			 const Typed_identifier_list*);
@@ -1680,6 +1687,9 @@ class Pointer_type : public Type
   static Pointer_type*
   do_import(Import*);
 
+  static Type*
+  make_pointer_type_descriptor_type();
+
  protected:
   int
   do_traverse(Traverse*);
@@ -1710,9 +1720,6 @@ class Pointer_type : public Type
   do_export(Export*) const;
 
  private:
-  static Type*
-  make_pointer_type_descriptor_type();
-
   // The type to which this type points.
   Type* to_type_;
 };
@@ -1841,8 +1848,7 @@ class Struct_type : public Type
  public:
   Struct_type(Struct_field_list* fields, source_location location)
     : Type(TYPE_STRUCT),
-      fields_(fields), location_(location), all_methods_(NULL),
-      prerequisites_()
+      fields_(fields), location_(location), all_methods_(NULL)
   { }
 
   // Return the field NAME.  This only looks at local fields, not at
@@ -1937,16 +1943,8 @@ class Struct_type : public Type
   tree
   fill_in_tree(Gogo*, tree);
 
-  // Note that a struct must be converted to the backend
-  // representation before we convert this struct.
-  void
-  add_prerequisite(Named_type* nt)
-  { this->prerequisites_.push_back(nt); }
-
-  // If there are any structs which must be converted to the backend
-  // representation before this one, convert them.
-  void
-  convert_prerequisites(Gogo*);
+  static Type*
+  make_struct_type_descriptor_type();
 
  protected:
   int
@@ -1992,25 +1990,12 @@ class Struct_type : public Type
 			source_location, Saw_named_type*,
 			unsigned int* depth) const;
 
-  static Type*
-  make_struct_type_descriptor_type();
-
   // The fields of the struct.
   Struct_field_list* fields_;
   // The place where the struct was declared.
   source_location location_;
   // If this struct is unnamed, a list of methods.
   Methods* all_methods_;
-  // A list of structs which must be converted to the backend
-  // representation before this struct can be converted.  This is for
-  // cases like
-  //   type S1 { p *S2 }
-  //   type S2 { s S1 }
-  // where we must start converting S2 before we start converting S1.
-  // That is because we can fully convert S1 before S2 is complete,
-  // but we can not fully convert S2 before S1 is complete.  If we
-  // start converting S1 first, we won't be able to convert S2.
-  std::vector<Named_type*> prerequisites_;
 };
 
 // The type of an array.
@@ -2066,6 +2051,12 @@ class Array_type : public Type
   tree
   fill_in_slice_tree(Gogo*, tree);
 
+  static Type*
+  make_array_type_descriptor_type();
+
+  static Type*
+  make_slice_type_descriptor_type();
+
  protected:
   int
   do_traverse(Traverse* traverse);
@@ -2114,12 +2105,6 @@ class Array_type : public Type
   tree
   get_length_tree(Gogo*);
 
-  Type*
-  make_array_type_descriptor_type();
-
-  Type*
-  make_slice_type_descriptor_type();
-
   Expression*
   array_type_descriptor(Gogo*, Named_type*);
 
@@ -2162,6 +2147,9 @@ class Map_type : public Type
   static Map_type*
   do_import(Import*);
 
+  static Type*
+  make_map_type_descriptor_type();
+
  protected:
   int
   do_traverse(Traverse*);
@@ -2202,9 +2190,6 @@ class Map_type : public Type
   do_export(Export*) const;
 
  private:
-  static Type*
-  make_map_type_descriptor_type();
-
   // The key type.
   Type* key_type_;
   // The value type.
@@ -2248,6 +2233,9 @@ class Channel_type : public Type
   static Channel_type*
   do_import(Import*);
 
+  static Type*
+  make_chan_type_descriptor_type();
+
  protected:
   int
   do_traverse(Traverse* traverse)
@@ -2286,9 +2274,6 @@ class Channel_type : public Type
   do_export(Export*) const;
 
  private:
-  static Type*
-  make_chan_type_descriptor_type();
-
   // Whether this channel can send data.
   bool may_send_;
   // Whether this channel can receive data.
@@ -2308,6 +2293,11 @@ class Interface_type : public Type
       methods_(methods), location_(location)
   { gcc_assert(methods == NULL || !methods->empty()); }
 
+  // The location where the interface type was defined.
+  source_location
+  location() const
+  { return this->location_; }
+
   // Return whether this is an empty interface.
   bool
   is_empty() const
@@ -2361,10 +2351,21 @@ class Interface_type : public Type
   static Interface_type*
   do_import(Import*);
 
+  // Make a struct for an empty interface type.
+  static tree
+  empty_type_tree(Gogo*);
+
+  // Make a struct for non-empty interface type.
+  static tree
+  non_empty_type_tree(source_location);
+
   // Fill in the fields for a named interface type.
   tree
   fill_in_tree(Gogo*, tree);
 
+  static Type*
+  make_interface_type_descriptor_type();
+
  protected:
   int
   do_traverse(Traverse*);
@@ -2395,9 +2396,6 @@ class Interface_type : public Type
   do_export(Export*) const;
 
  private:
-  static Type*
-  make_interface_type_descriptor_type();
-
   // The list of methods associated with the interface.  This will be
   // NULL for the empty interface.
   Typed_identifier_list* methods_;
@@ -2419,8 +2417,9 @@ class Named_type : public Type
       named_object_(named_object), in_function_(NULL), type_(type),
       local_methods_(NULL), all_methods_(NULL),
       interface_method_tables_(NULL), pointer_interface_method_tables_(NULL),
-      location_(location), named_tree_(NULL), is_visible_(true),
-      is_error_(false), seen_(0)
+      location_(location), named_tree_(NULL), dependencies_(),
+      is_visible_(true), is_error_(false), is_converted_(false),
+      is_circular_(false), seen_(0)
   { }
 
   // Return the associated Named_object.  This holds the actual name.
@@ -2493,6 +2492,12 @@ class Named_type : public Type
   is_builtin() const
   { return this->location_ == BUILTINS_LOCATION; }
 
+  // Whether this is a circular type: a pointer or function type that
+  // refers to itself, which is not possible in C.
+  bool
+  is_circular() const
+  { return this->is_circular_; }
+
   // Return the base type for this type.
   Type*
   named_base();
@@ -2567,6 +2572,12 @@ class Named_type : public Type
   bool
   named_type_has_hidden_fields(std::string* reason) const;
 
+  // Note that a type must be converted to the backend representation
+  // before we convert this type.
+  void
+  add_dependency(Named_type* nt)
+  { this->dependencies_.push_back(nt); }
+
   // Export the type.
   void
   export_named_type(Export*, const std::string& name) const;
@@ -2575,6 +2586,10 @@ class Named_type : public Type
   static void
   import_named_type(Import*, Named_type**);
 
+  // Initial conversion to backend representation.
+  void
+  convert(Gogo*);
+
  protected:
   int
   do_traverse(Traverse* traverse)
@@ -2618,6 +2633,10 @@ class Named_type : public Type
   do_export(Export*) const;
 
  private:
+  // Create the placeholder during conversion.
+  void
+  create_placeholder(Gogo*);
+
   // A mapping from interfaces to the associated interface method
   // tables for this type.  This maps to a decl.
   typedef Unordered_map_hash(const Interface_type*, tree, Type_hash_identical,
@@ -2647,6 +2666,14 @@ class Named_type : public Type
   // The tree for this type while converting to GENERIC.  This is used
   // to avoid endless recursion when a named type refers to itself.
   tree named_tree_;
+  // A list of types which must be converted to the backend
+  // representation before this type can be converted.  This is for
+  // cases like
+  //   type S1 { p *S2 }
+  //   type S2 { s S1 }
+  // where we can't convert S2 to the backend representation unless we
+  // have converted S1.
+  std::vector<Named_type*> dependencies_;
   // Whether this type is visible.  This is false if this type was
   // created because it was referenced by an imported object, but the
   // type itself was not exported.  This will always be true for types
@@ -2654,6 +2681,12 @@ class Named_type : public Type
   bool is_visible_;
   // Whether this type is erroneous.
   bool is_error_;
+  // Whether this type has been converted to the backend
+  // representation.
+  bool is_converted_;
+  // Whether this is a pointer or function type which refers to the
+  // type itself.
+  bool is_circular_;
   // In a recursive operation such as has_hidden_fields, this flag is
   // used to prevent infinite recursion when a type refers to itself.
   // This is mutable because it is always reset to false when the