go/gogo.cc

// gogo.cc -- Go frontend parsed representation.

// Copyright 2009 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

#include "go-system.h"

#include <fstream>

#include "filenames.h"

#include "go-c.h"
#include "go-diagnostics.h"
#include "go-encode-id.h"
#include "go-dump.h"
#include "go-optimize.h"
#include "lex.h"
#include "types.h"
#include "statements.h"
#include "expressions.h"
#include "runtime.h"
#include "import.h"
#include "export.h"
#include "backend.h"
#include "gogo.h"

// Class Gogo.

Gogo::Gogo(Backend* backend, Linemap* linemap, int, int pointer_size)
  : backend_(backend),
    linemap_(linemap),
    package_(NULL),
    functions_(),
    globals_(new Bindings(NULL)),
    file_block_names_(),
    imports_(),
    imported_unsafe_(false),
    current_file_imported_unsafe_(false),
    packages_(),
    init_functions_(),
    var_deps_(),
    need_init_fn_(false),
    init_fn_name_(),
    imported_init_fns_(),
    pkgpath_(),
    pkgpath_symbol_(),
    prefix_(),
    pkgpath_set_(false),
    pkgpath_from_option_(false),
    prefix_from_option_(false),
    relative_import_path_(),
    c_header_(),
    check_divide_by_zero_(true),
    check_divide_overflow_(true),
    compiling_runtime_(false),
    debug_escape_level_(0),
    debug_optimization_(false),
    nil_check_size_threshold_(4096),
    need_eqtype_(false),
    verify_types_(),
    interface_types_(),
    specific_type_functions_(),
    specific_type_functions_are_written_(false),
    named_types_are_converted_(false),
    analysis_sets_(),
    gc_roots_(),
    type_descriptors_(),
    imported_inlinable_functions_(),
    imported_inline_functions_()
{
  const Location loc = Linemap::predeclared_location();

  Named_type* uint8_type = Type::make_integer_type("uint8", true, 8,
						   RUNTIME_TYPE_KIND_UINT8);
  this->add_named_type(uint8_type);
  this->add_named_type(Type::make_integer_type("uint16", true,  16,
					       RUNTIME_TYPE_KIND_UINT16));
  this->add_named_type(Type::make_integer_type("uint32", true,  32,
					       RUNTIME_TYPE_KIND_UINT32));
  this->add_named_type(Type::make_integer_type("uint64", true,  64,
					       RUNTIME_TYPE_KIND_UINT64));

  this->add_named_type(Type::make_integer_type("int8",  false,   8,
					       RUNTIME_TYPE_KIND_INT8));
  this->add_named_type(Type::make_integer_type("int16", false,  16,
					       RUNTIME_TYPE_KIND_INT16));
  Named_type* int32_type = Type::make_integer_type("int32", false,  32,
						   RUNTIME_TYPE_KIND_INT32);
  this->add_named_type(int32_type);
  this->add_named_type(Type::make_integer_type("int64", false,  64,
					       RUNTIME_TYPE_KIND_INT64));

  this->add_named_type(Type::make_float_type("float32", 32,
					     RUNTIME_TYPE_KIND_FLOAT32));
  this->add_named_type(Type::make_float_type("float64", 64,
					     RUNTIME_TYPE_KIND_FLOAT64));

  this->add_named_type(Type::make_complex_type("complex64", 64,
					       RUNTIME_TYPE_KIND_COMPLEX64));
  this->add_named_type(Type::make_complex_type("complex128", 128,
					       RUNTIME_TYPE_KIND_COMPLEX128));

  int int_type_size = pointer_size;
  if (int_type_size < 32)
    int_type_size = 32;
  this->add_named_type(Type::make_integer_type("uint", true,
					       int_type_size,
					       RUNTIME_TYPE_KIND_UINT));
  Named_type* int_type = Type::make_integer_type("int", false, int_type_size,
						 RUNTIME_TYPE_KIND_INT);
  this->add_named_type(int_type);

  this->add_named_type(Type::make_integer_type("uintptr", true,
					       pointer_size,
					       RUNTIME_TYPE_KIND_UINTPTR));

  // "byte" is an alias for "uint8".
  uint8_type->integer_type()->set_is_byte();
  Named_object* byte_type = Named_object::make_type("byte", NULL, uint8_type,
						    loc);
  byte_type->type_value()->set_is_alias();
  this->add_named_type(byte_type->type_value());

  // "rune" is an alias for "int32".
  int32_type->integer_type()->set_is_rune();
  Named_object* rune_type = Named_object::make_type("rune", NULL, int32_type,
						    loc);
  rune_type->type_value()->set_is_alias();
  this->add_named_type(rune_type->type_value());

  this->add_named_type(Type::make_named_bool_type());

  this->add_named_type(Type::make_named_string_type());

  // "error" is interface { Error() string }.
  {
    Typed_identifier_list *methods = new Typed_identifier_list;
    Typed_identifier_list *results = new Typed_identifier_list;
    results->push_back(Typed_identifier("", Type::lookup_string_type(), loc));
    Type *method_type = Type::make_function_type(NULL, NULL, results, loc);
    methods->push_back(Typed_identifier("Error", method_type, loc));
    Interface_type *error_iface = Type::make_interface_type(methods, loc);
    error_iface->finalize_methods();
    Named_type *error_type = Named_object::make_type("error", NULL, error_iface, loc)->type_value();
    this->add_named_type(error_type);
  }

  this->globals_->add_constant(Typed_identifier("true",
						Type::make_boolean_type(),
						loc),
			       NULL,
			       Expression::make_boolean(true, loc),
			       0);
  this->globals_->add_constant(Typed_identifier("false",
						Type::make_boolean_type(),
						loc),
			       NULL,
			       Expression::make_boolean(false, loc),
			       0);

  this->globals_->add_constant(Typed_identifier("nil", Type::make_nil_type(),
						loc),
			       NULL,
			       Expression::make_nil(loc),
			       0);

  Type* abstract_int_type = Type::make_abstract_integer_type();
  this->globals_->add_constant(Typed_identifier("iota", abstract_int_type,
						loc),
			       NULL,
			       Expression::make_iota(),
			       0);

  Function_type* new_type = Type::make_function_type(NULL, NULL, NULL, loc);
  new_type->set_is_varargs();
  new_type->set_is_builtin();
  this->globals_->add_function_declaration("new", NULL, new_type, loc);

  Function_type* make_type = Type::make_function_type(NULL, NULL, NULL, loc);
  make_type->set_is_varargs();
  make_type->set_is_builtin();
  this->globals_->add_function_declaration("make", NULL, make_type, loc);

  Typed_identifier_list* len_result = new Typed_identifier_list();
  len_result->push_back(Typed_identifier("", int_type, loc));
  Function_type* len_type = Type::make_function_type(NULL, NULL, len_result,
						     loc);
  len_type->set_is_builtin();
  this->globals_->add_function_declaration("len", NULL, len_type, loc);

  Typed_identifier_list* cap_result = new Typed_identifier_list();
  cap_result->push_back(Typed_identifier("", int_type, loc));
  Function_type* cap_type = Type::make_function_type(NULL, NULL, len_result,
						     loc);
  cap_type->set_is_builtin();
  this->globals_->add_function_declaration("cap", NULL, cap_type, loc);

  Function_type* print_type = Type::make_function_type(NULL, NULL, NULL, loc);
  print_type->set_is_varargs();
  print_type->set_is_builtin();
  this->globals_->add_function_declaration("print", NULL, print_type, loc);

  print_type = Type::make_function_type(NULL, NULL, NULL, loc);
  print_type->set_is_varargs();
  print_type->set_is_builtin();
  this->globals_->add_function_declaration("println", NULL, print_type, loc);

  Type *empty = Type::make_empty_interface_type(loc);
  Typed_identifier_list* panic_parms = new Typed_identifier_list();
  panic_parms->push_back(Typed_identifier("e", empty, loc));
  Function_type *panic_type = Type::make_function_type(NULL, panic_parms,
						       NULL, loc);
  panic_type->set_is_builtin();
  this->globals_->add_function_declaration("panic", NULL, panic_type, loc);

  Typed_identifier_list* recover_result = new Typed_identifier_list();
  recover_result->push_back(Typed_identifier("", empty, loc));
  Function_type* recover_type = Type::make_function_type(NULL, NULL,
							 recover_result,
							 loc);
  recover_type->set_is_builtin();
  this->globals_->add_function_declaration("recover", NULL, recover_type, loc);

  Function_type* close_type = Type::make_function_type(NULL, NULL, NULL, loc);
  close_type->set_is_varargs();
  close_type->set_is_builtin();
  this->globals_->add_function_declaration("close", NULL, close_type, loc);

  Typed_identifier_list* copy_result = new Typed_identifier_list();
  copy_result->push_back(Typed_identifier("", int_type, loc));
  Function_type* copy_type = Type::make_function_type(NULL, NULL,
						      copy_result, loc);
  copy_type->set_is_varargs();
  copy_type->set_is_builtin();
  this->globals_->add_function_declaration("copy", NULL, copy_type, loc);

  Function_type* append_type = Type::make_function_type(NULL, NULL, NULL, loc);
  append_type->set_is_varargs();
  append_type->set_is_builtin();
  this->globals_->add_function_declaration("append", NULL, append_type, loc);

  Function_type* complex_type = Type::make_function_type(NULL, NULL, NULL, loc);
  complex_type->set_is_varargs();
  complex_type->set_is_builtin();
  this->globals_->add_function_declaration("complex", NULL, complex_type, loc);

  Function_type* real_type = Type::make_function_type(NULL, NULL, NULL, loc);
  real_type->set_is_varargs();
  real_type->set_is_builtin();
  this->globals_->add_function_declaration("real", NULL, real_type, loc);

  Function_type* imag_type = Type::make_function_type(NULL, NULL, NULL, loc);
  imag_type->set_is_varargs();
  imag_type->set_is_builtin();
  this->globals_->add_function_declaration("imag", NULL, imag_type, loc);

  Function_type* delete_type = Type::make_function_type(NULL, NULL, NULL, loc);
  delete_type->set_is_varargs();
  delete_type->set_is_builtin();
  this->globals_->add_function_declaration("delete", NULL, delete_type, loc);
}

std::string
Gogo::pkgpath_for_symbol(const std::string& pkgpath)
{
  go_assert(!pkgpath.empty());
  return go_encode_id(pkgpath);
}

// Return a hash code for a string, given a starting hash.

unsigned int
Gogo::hash_string(const std::string& s, unsigned int h)
{
  const char* p = s.data();
  size_t len = s.length();
  for (; len > 0; --len)
    {
      h ^= *p++;
      h*= 16777619;
    }
  return h;
}

// Get the package path to use for type reflection data.  This should
// ideally be unique across the entire link.

const std::string&
Gogo::pkgpath() const
{
  go_assert(this->pkgpath_set_);
  return this->pkgpath_;
}

// Set the package path from the -fgo-pkgpath command line option.

void
Gogo::set_pkgpath(const std::string& arg)
{
  go_assert(!this->pkgpath_set_);
  this->pkgpath_ = go_mangle_pkgpath(arg);
  this->pkgpath_set_ = true;
  this->pkgpath_from_option_ = true;
}

// Get the package path to use for symbol names.

const std::string&
Gogo::pkgpath_symbol() const
{
  go_assert(this->pkgpath_set_);
  return this->pkgpath_symbol_;
}

// Set the unique prefix to use to determine the package path, from
// the -fgo-prefix command line option.

void
Gogo::set_prefix(const std::string& arg)
{
  go_assert(!this->prefix_from_option_);
  this->prefix_ = arg;
  this->prefix_from_option_ = true;
}

// Given a name which may or may not have been hidden, append the
// appropriate version of the name to the result string. Take care
// to avoid creating a sequence that will be rejected by go_encode_id
// (avoid ..u, ..U, ..z).
void
Gogo::append_possibly_hidden_name(std::string *result, const std::string& name)
{
  // FIXME: This adds in pkgpath twice for hidden symbols, which is
  // less than ideal.
  if (!Gogo::is_hidden_name(name))
    (*result) += name;
  else
    {
      std::string n = ".";
      std::string pkgpath = Gogo::hidden_name_pkgpath(name);
      char lastR = result->at(result->length() - 1);
      char firstP = pkgpath.at(0);
      if (lastR == '.' && (firstP == 'u' || firstP == 'U' || firstP == 'z'))
        n = "_.";
      n.append(pkgpath);
      n.append(1, '.');
      n.append(Gogo::unpack_hidden_name(name));
      (*result) += n;
    }
}

// Munge name for use in an error message.

std::string
Gogo::message_name(const std::string& name)
{
  return go_localize_identifier(Gogo::unpack_hidden_name(name).c_str());
}

// Get the package name.

const std::string&
Gogo::package_name() const
{
  go_assert(this->package_ != NULL);
  return this->package_->package_name();
}

// Set the package name.

void
Gogo::set_package_name(const std::string& package_name,
		       Location location)
{
  if (this->package_ != NULL)
    {
      if (this->package_->package_name() != package_name)
	go_error_at(location, "expected package %<%s%>",
		    Gogo::message_name(this->package_->package_name()).c_str());
      return;
    }

  // Now that we know the name of the package we are compiling, set
  // the package path to use for reflect.Type.PkgPath and global
  // symbol names.
  if (this->pkgpath_set_)
    this->pkgpath_symbol_ = Gogo::pkgpath_for_symbol(this->pkgpath_);
  else
    {
      if (!this->prefix_from_option_ && package_name == "main")
	{
	  this->pkgpath_ = package_name;
	  this->pkgpath_symbol_ = Gogo::pkgpath_for_symbol(package_name);
	}
      else
	{
	  if (!this->prefix_from_option_)
	    this->prefix_ = "go";
	  this->pkgpath_ = (go_mangle_pkgpath(this->prefix_) + '.'
			    + package_name);
	  this->pkgpath_symbol_ = (Gogo::pkgpath_for_symbol(this->prefix_) + '.'
				   + Gogo::pkgpath_for_symbol(package_name));
	}
      this->pkgpath_set_ = true;
    }

  this->package_ = this->register_package(this->pkgpath_,
					  this->pkgpath_symbol_, location);
  this->package_->set_package_name(package_name, location);

  if (this->is_main_package())
    {
      // Declare "main" as a function which takes no parameters and
      // returns no value.
      Location uloc = Linemap::unknown_location();
      this->declare_function(Gogo::pack_hidden_name("main", false),
			     Type::make_function_type (NULL, NULL, NULL, uloc),
			     uloc);
    }
}

// Return whether this is the "main" package.  This is not true if
// -fgo-pkgpath or -fgo-prefix was used.

bool
Gogo::is_main_package() const
{
  return (this->package_name() == "main"
	  && !this->pkgpath_from_option_
	  && !this->prefix_from_option_);
}

// Import a package.

void
Gogo::import_package(const std::string& filename,
		     const std::string& local_name,
		     bool is_local_name_exported,
		     bool must_exist,
		     Location location)
{
  if (filename.empty())
    {
      go_error_at(location, "import path is empty");
      return;
    }

  const char *pf = filename.data();
  const char *pend = pf + filename.length();
  while (pf < pend)
    {
      unsigned int c;
      int adv = Lex::fetch_char(pf, &c);
      if (adv == 0)
	{
	  go_error_at(location, "import path contains invalid UTF-8 sequence");
	  return;
	}
      if (c == '\0')
	{
	  go_error_at(location, "import path contains NUL");
	  return;
	}
      if (c < 0x20 || c == 0x7f)
	{
	  go_error_at(location, "import path contains control character");
	  return;
	}
      if (c == '\\')
	{
	  go_error_at(location, "import path contains backslash; use slash");
	  return;
	}
      if (Lex::is_unicode_space(c))
	{
	  go_error_at(location, "import path contains space character");
	  return;
	}
      if (c < 0x7f && strchr("!\"#$%&'()*,:;<=>?[]^`{|}", c) != NULL)
	{
	  go_error_at(location,
                      "import path contains invalid character '%c'", c);
	  return;
	}
      pf += adv;
    }

  if (IS_ABSOLUTE_PATH(filename.c_str()))
    {
      go_error_at(location, "import path cannot be absolute path");
      return;
    }

  if (local_name == "init")
    go_error_at(location, "cannot import package as init");

  if (filename == "unsafe")
    {
      this->import_unsafe(local_name, is_local_name_exported, location);
      this->current_file_imported_unsafe_ = true;
      return;
    }

  Imports::const_iterator p = this->imports_.find(filename);
  if (p != this->imports_.end())
    {
      Package* package = p->second;
      package->set_location(location);
      std::string ln = local_name;
      bool is_ln_exported = is_local_name_exported;
      if (ln.empty())
	{
	  ln = package->package_name();
	  go_assert(!ln.empty());
	  is_ln_exported = Lex::is_exported_name(ln);
	}
      if (ln == "_")
        ;
      else if (ln == ".")
	{
	  Bindings* bindings = package->bindings();
	  for (Bindings::const_declarations_iterator pd =
		 bindings->begin_declarations();
	       pd != bindings->end_declarations();
	       ++pd)
	    this->add_dot_import_object(pd->second);
          std::string dot_alias = "." + package->package_name();
          package->add_alias(dot_alias, location);
	}
      else
	{
          package->add_alias(ln, location);
	  ln = this->pack_hidden_name(ln, is_ln_exported);
	  this->package_->bindings()->add_package(ln, package);
	}
      return;
    }

  Import::Stream* stream = Import::open_package(filename, location,
						this->relative_import_path_);
  if (stream == NULL)
    {
      if (must_exist)
	go_error_at(location, "import file %qs not found", filename.c_str());
      return;
    }

  Import* imp = new Import(stream, location);
  imp->register_builtin_types(this);
  Package* package = imp->import(this, local_name, is_local_name_exported);
  if (package != NULL)
    {
      if (package->pkgpath() == this->pkgpath())
	go_error_at(location,
		    ("imported package uses same package path as package "
		     "being compiled (see %<-fgo-pkgpath%> option)"));

      this->imports_.insert(std::make_pair(filename, package));
    }

  imp->clear_stream();
  delete stream;

  // FIXME: we never delete imp; we may need it for inlinable functions.
}

Import_init *
Gogo::lookup_init(const std::string& init_name)
{
  Import_init tmp("", init_name, -1);
  Import_init_set::iterator it = this->imported_init_fns_.find(&tmp);
  return (it != this->imported_init_fns_.end()) ? *it : NULL;
}

// Add an import control function for an imported package to the list.

void
Gogo::add_import_init_fn(const std::string& package_name,
			 const std::string& init_name, int prio)
{
  for (Import_init_set::iterator p =
	 this->imported_init_fns_.begin();
       p != this->imported_init_fns_.end();
       ++p)
    {
      Import_init *ii = (*p);
      if (ii->init_name() == init_name)
	{
	  // If a test of package P1, built as part of package P1,
	  // imports package P2, and P2 imports P1 (perhaps
	  // indirectly), then we will see the same import name with
	  // different import priorities.  That is OK, so don't give
	  // an error about it.
	  if (ii->package_name() != package_name)
	    {
	      go_error_at(Linemap::unknown_location(),
		       "duplicate package initialization name %qs",
		       Gogo::message_name(init_name).c_str());
	      go_inform(Linemap::unknown_location(), "used by package %qs",
			Gogo::message_name(ii->package_name()).c_str());
	      go_inform(Linemap::unknown_location(), " and by package %qs",
			Gogo::message_name(package_name).c_str());
	    }
          ii->set_priority(prio);
          return;
	}
    }

  Import_init* nii = new Import_init(package_name, init_name, prio);
  this->imported_init_fns_.insert(nii);
}

// Return whether we are at the global binding level.

bool
Gogo::in_global_scope() const
{
  return this->functions_.empty();
}

// Return the current binding contour.

Bindings*
Gogo::current_bindings()
{
  if (!this->functions_.empty())
    return this->functions_.back().blocks.back()->bindings();
  else if (this->package_ != NULL)
    return this->package_->bindings();
  else
    return this->globals_;
}

const Bindings*
Gogo::current_bindings() const
{
  if (!this->functions_.empty())
    return this->functions_.back().blocks.back()->bindings();
  else if (this->package_ != NULL)
    return this->package_->bindings();
  else
    return this->globals_;
}

void
Gogo::update_init_priority(Import_init* ii,
                           std::set<const Import_init *>* visited)
{
  visited->insert(ii);
  int succ_prior = -1;

  for (std::set<std::string>::const_iterator pci =
           ii->precursors().begin();
       pci != ii->precursors().end();
       ++pci)
    {
      Import_init* succ = this->lookup_init(*pci);
      if (visited->find(succ) == visited->end())
        update_init_priority(succ, visited);
      succ_prior = std::max(succ_prior, succ->priority());
    }
  if (ii->priority() <= succ_prior)
    ii->set_priority(succ_prior + 1);
}

void
Gogo::recompute_init_priorities()
{
  std::set<Import_init *> nonroots;

  for (Import_init_set::const_iterator p =
           this->imported_init_fns_.begin();
       p != this->imported_init_fns_.end();
       ++p)
    {
      const Import_init *ii = *p;
      for (std::set<std::string>::const_iterator pci =
               ii->precursors().begin();
           pci != ii->precursors().end();
           ++pci)
        {
          Import_init* ii_init = this->lookup_init(*pci);
          nonroots.insert(ii_init);
        }
    }

  // Recursively update priorities starting at roots.
  std::set<const Import_init*> visited;
  for (Import_init_set::iterator p =
           this->imported_init_fns_.begin();
       p != this->imported_init_fns_.end();
       ++p)
    {
      Import_init* ii = *p;
      if (nonroots.find(ii) != nonroots.end())
        continue;
      update_init_priority(ii, &visited);
    }
}

// Add statements to INIT_STMTS which run the initialization
// functions for imported packages.  This is only used for the "main"
// package.

void
Gogo::init_imports(std::vector<Bstatement*>& init_stmts, Bfunction *bfunction)
{
  go_assert(this->is_main_package());

  if (this->imported_init_fns_.empty())
    return;

  Location unknown_loc = Linemap::unknown_location();
  Function_type* func_type =
      Type::make_function_type(NULL, NULL, NULL, unknown_loc);
  Btype* fntype = func_type->get_backend_fntype(this);

  // Recompute init priorities based on a walk of the init graph.
  recompute_init_priorities();

  // We must call them in increasing priority order.
  std::vector<const Import_init*> v;
  for (Import_init_set::const_iterator p =
	 this->imported_init_fns_.begin();
       p != this->imported_init_fns_.end();
       ++p)
    {
      // Don't include dummy inits. They are not real functions.
      if ((*p)->is_dummy())
        continue;
      if ((*p)->priority() < 0)
	go_error_at(Linemap::unknown_location(),
		    "internal error: failed to set init priority for %s",
		    (*p)->package_name().c_str());
      v.push_back(*p);
    }
  std::sort(v.begin(), v.end(), priority_compare);

  // We build calls to the init functions, which take no arguments.
  std::vector<Bexpression*> empty_args;
  for (std::vector<const Import_init*>::const_iterator p = v.begin();
       p != v.end();
       ++p)
    {
      const Import_init* ii = *p;
      std::string user_name = ii->package_name() + ".init";
      const std::string& init_name(ii->init_name());
      const unsigned int flags =
	(Backend::function_is_visible
	 | Backend::function_is_declaration
	 | Backend::function_is_inlinable);
      Bfunction* pfunc = this->backend()->function(fntype, user_name, init_name,
						   flags, unknown_loc);
      Bexpression* pfunc_code =
          this->backend()->function_code_expression(pfunc, unknown_loc);
      Bexpression* pfunc_call =
          this->backend()->call_expression(bfunction, pfunc_code, empty_args,
                                           NULL, unknown_loc);
      init_stmts.push_back(this->backend()->expression_statement(bfunction,
                                                                 pfunc_call));
    }
}

// Register global variables with the garbage collector.  We need to
// register all variables which can hold a pointer value.  They become
// roots during the mark phase.  We build a struct that is easy to
// hook into a list of roots.

// type gcRoot struct {
// 	decl    unsafe.Pointer // Pointer to variable.
//	size    uintptr        // Total size of variable.
// 	ptrdata uintptr        // Length of variable's gcdata.
// 	gcdata  *byte          // Pointer mask.
// }
//
// type gcRootList struct {
// 	next  *gcRootList
// 	count int
// 	roots [...]gcRoot
// }

// The last entry in the roots array has a NULL decl field.

void
Gogo::register_gc_vars(const std::vector<Named_object*>& var_gc,
		       std::vector<Bstatement*>& init_stmts,
                       Bfunction* init_bfn)
{
  if (var_gc.empty() && this->gc_roots_.empty())
    return;

  Type* pvt = Type::make_pointer_type(Type::make_void_type());
  Type* uintptr_type = Type::lookup_integer_type("uintptr");
  Type* byte_type = this->lookup_global("byte")->type_value();
  Type* pointer_byte_type = Type::make_pointer_type(byte_type);
  Struct_type* root_type =
    Type::make_builtin_struct_type(4,
				   "decl", pvt,
				   "size", uintptr_type,
				   "ptrdata", uintptr_type,
				   "gcdata", pointer_byte_type);

  Location builtin_loc = Linemap::predeclared_location();
  unsigned long roots_len = var_gc.size() + this->gc_roots_.size();
  Expression* length = Expression::make_integer_ul(roots_len, NULL,
                                                   builtin_loc);
  Array_type* root_array_type = Type::make_array_type(root_type, length);
  root_array_type->set_is_array_incomparable();

  Type* int_type = Type::lookup_integer_type("int");
  Struct_type* root_list_type =
      Type::make_builtin_struct_type(3,
                                     "next", pvt,
				     "count", int_type,
                                     "roots", root_array_type);

  // Build an initializer for the roots array.

  Expression_list* roots_init = new Expression_list();

  for (std::vector<Named_object*>::const_iterator p = var_gc.begin();
       p != var_gc.end();
       ++p)
    {
      Expression_list* init = new Expression_list();

      Location no_loc = (*p)->location();
      Expression* decl = Expression::make_var_reference(*p, no_loc);
      Expression* decl_addr =
          Expression::make_unary(OPERATOR_AND, decl, no_loc);
      decl_addr->unary_expression()->set_does_not_escape();
      decl_addr = Expression::make_cast(pvt, decl_addr, no_loc);
      init->push_back(decl_addr);

      Expression* size =
	Expression::make_type_info(decl->type(),
				   Expression::TYPE_INFO_SIZE);
      init->push_back(size);

      Expression* ptrdata =
	Expression::make_type_info(decl->type(),
				   Expression::TYPE_INFO_BACKEND_PTRDATA);
      init->push_back(ptrdata);

      Expression* gcdata = Expression::make_ptrmask_symbol(decl->type());
      init->push_back(gcdata);

      Expression* root_ctor =
          Expression::make_struct_composite_literal(root_type, init, no_loc);
      roots_init->push_back(root_ctor);
    }

  for (std::vector<Expression*>::const_iterator p = this->gc_roots_.begin();
       p != this->gc_roots_.end();
       ++p)
    {
      Expression_list *init = new Expression_list();

      Expression* expr = *p;
      Location eloc = expr->location();
      init->push_back(Expression::make_cast(pvt, expr, eloc));

      Type* type = expr->type()->points_to();
      go_assert(type != NULL);

      Expression* size =
	Expression::make_type_info(type,
				   Expression::TYPE_INFO_SIZE);
      init->push_back(size);

      Expression* ptrdata =
	Expression::make_type_info(type,
				   Expression::TYPE_INFO_BACKEND_PTRDATA);
      init->push_back(ptrdata);

      Expression* gcdata = Expression::make_ptrmask_symbol(type);
      init->push_back(gcdata);

      Expression* root_ctor =
	Expression::make_struct_composite_literal(root_type, init, eloc);
      roots_init->push_back(root_ctor);
    }

  // Build a constructor for the struct.

  Expression_list* root_list_init = new Expression_list();
  root_list_init->push_back(Expression::make_nil(builtin_loc));
  root_list_init->push_back(Expression::make_integer_ul(roots_len, int_type,
							builtin_loc));

  Expression* roots_ctor =
      Expression::make_array_composite_literal(root_array_type, roots_init,
                                               builtin_loc);
  root_list_init->push_back(roots_ctor);

  Expression* root_list_ctor =
      Expression::make_struct_composite_literal(root_list_type, root_list_init,
                                                builtin_loc);

  Expression* root_addr = Expression::make_unary(OPERATOR_AND, root_list_ctor,
                                                 builtin_loc);
  root_addr->unary_expression()->set_is_gc_root();
  Expression* register_roots = Runtime::make_call(Runtime::REGISTER_GC_ROOTS,
                                                  builtin_loc, 1, root_addr);

  Translate_context context(this, NULL, NULL, NULL);
  Bexpression* bcall = register_roots->get_backend(&context);
  init_stmts.push_back(this->backend()->expression_statement(init_bfn, bcall));
}

// Build the list of type descriptors defined in this package. This is to help
// the reflect package to find compiler-generated types.

// type typeDescriptorList struct {
// 	 count int
// 	 types [...]unsafe.Pointer
// }

static Struct_type*
type_descriptor_list_type(unsigned long len)
{
  Location builtin_loc = Linemap::predeclared_location();
  Type* int_type = Type::lookup_integer_type("int");
  Type* ptr_type = Type::make_pointer_type(Type::make_void_type());
  // Avoid creating zero-length type.
  unsigned long nelems = (len != 0 ? len : 1);
  Expression* len_expr = Expression::make_integer_ul(nelems, NULL,
                                                     builtin_loc);
  Array_type* array_type = Type::make_array_type(ptr_type, len_expr);
  array_type->set_is_array_incomparable();
  Struct_type* list_type =
    Type::make_builtin_struct_type(2, "count", int_type,
                                   "types", array_type);
  return list_type;
}

void
Gogo::build_type_descriptor_list()
{
  // Create the list type
  Location builtin_loc = Linemap::predeclared_location();
  unsigned long len = this->type_descriptors_.size();
  Struct_type* list_type = type_descriptor_list_type(len);
  Btype* bt = list_type->get_backend(this);
  Btype* bat = list_type->field(1)->type()->get_backend(this);

  // Create the variable
  std::string name = this->type_descriptor_list_symbol(this->pkgpath_symbol());
  Bvariable* bv = this->backend()->implicit_variable(name, name, bt,
                                                     false, true, false,
                                                     0);

  // Build the initializer
  std::vector<unsigned long> indexes;
  std::vector<Bexpression*> vals;
  std::vector<Type*>::iterator p = this->type_descriptors_.begin();
  for (unsigned long i = 0; i < len; ++i, ++p)
    {
      Bexpression* bexpr = (*p)->type_descriptor_pointer(this,
                                                         builtin_loc);
      indexes.push_back(i);
      vals.push_back(bexpr);
    }
  Bexpression* barray =
    this->backend()->array_constructor_expression(bat, indexes, vals,
                                                  builtin_loc);

  Translate_context context(this, NULL, NULL, NULL);
  std::vector<Bexpression*> fields;
  Expression* len_expr = Expression::make_integer_ul(len, NULL,
                                                     builtin_loc);
  fields.push_back(len_expr->get_backend(&context));
  fields.push_back(barray);
  Bexpression* binit =
    this->backend()->constructor_expression(bt, fields, builtin_loc);

  this->backend()->implicit_variable_set_init(bv, name, bt, false,
                                              true, false, binit);
}

// Register the type descriptors with the runtime.  This is to help
// the reflect package to find compiler-generated types.

void
Gogo::register_type_descriptors(std::vector<Bstatement*>& init_stmts,
                                Bfunction* init_bfn)
{
  // Create the list type
  Location builtin_loc = Linemap::predeclared_location();
  Struct_type* list_type = type_descriptor_list_type(1);
  Btype* bt = list_type->get_backend(this);

  // Collect type lists from transitive imports.
  std::vector<std::string> list_names;
  for (Import_init_set::iterator it = this->imported_init_fns_.begin();
       it != this->imported_init_fns_.end();
       ++it)
    {
      std::string pkgpath =
        this->pkgpath_from_init_fn_name((*it)->init_name());
      list_names.push_back(this->type_descriptor_list_symbol(pkgpath));
    }
  // Add the main package itself.
  list_names.push_back(this->type_descriptor_list_symbol("main"));

  // Build a list of lists.
  std::vector<unsigned long> indexes;
  std::vector<Bexpression*> vals;
  unsigned long i = 0;
  for (std::vector<std::string>::iterator p = list_names.begin();
       p != list_names.end();
       ++p)
    {
      Bvariable* bv =
        this->backend()->implicit_variable_reference(*p, *p, bt);
      Bexpression* bexpr = this->backend()->var_expression(bv, builtin_loc);
      bexpr = this->backend()->address_expression(bexpr, builtin_loc);

      indexes.push_back(i);
      vals.push_back(bexpr);
      i++;
    }
  Expression* len_expr = Expression::make_integer_ul(i, NULL, builtin_loc);
  Type* list_ptr_type = Type::make_pointer_type(list_type);
  Type* list_array_type = Type::make_array_type(list_ptr_type, len_expr);
  Btype* bat = list_array_type->get_backend(this);
  Bexpression* barray =
    this->backend()->array_constructor_expression(bat, indexes, vals,
                                                  builtin_loc);

  // Create a variable holding the list.
  std::string name = this->typelists_symbol();
  Bvariable* bv = this->backend()->implicit_variable(name, name, bat,
                                                     true, true, false,
                                                     0);
  this->backend()->implicit_variable_set_init(bv, name, bat, true, true,
                                              false, barray);

  // Build the call in main package's init function.
  Translate_context context(this, NULL, NULL, NULL);
  Bexpression* bexpr = this->backend()->var_expression(bv, builtin_loc);
  bexpr = this->backend()->address_expression(bexpr, builtin_loc);
  Type* array_ptr_type = Type::make_pointer_type(list_array_type);
  Expression* expr = Expression::make_backend(bexpr, array_ptr_type,
                                              builtin_loc);
  expr = Runtime::make_call(Runtime::REGISTER_TYPE_DESCRIPTORS,
                            builtin_loc, 2, len_expr->copy(), expr);
  Bexpression* bcall = expr->get_backend(&context);
  init_stmts.push_back(this->backend()->expression_statement(init_bfn,
                                                             bcall));
}

// Build the decl for the initialization function.

Named_object*
Gogo::initialization_function_decl()
{
  std::string name = this->get_init_fn_name();
  Location loc = this->package_->location();

  Function_type* fntype = Type::make_function_type(NULL, NULL, NULL, loc);
  Function* initfn = new Function(fntype, NULL, NULL, loc);
  return Named_object::make_function(name, NULL, initfn);
}

// Create the magic initialization function.  CODE_STMT is the
// code that it needs to run.

Named_object*
Gogo::create_initialization_function(Named_object* initfn,
				     Bstatement* code_stmt)
{
  // Make sure that we thought we needed an initialization function,
  // as otherwise we will not have reported it in the export data.
  go_assert(this->is_main_package() || this->need_init_fn_);

  if (initfn == NULL)
    initfn = this->initialization_function_decl();

  // Bind the initialization function code to a block.
  Bfunction* fndecl = initfn->func_value()->get_or_make_decl(this, initfn);
  Location pkg_loc = this->package_->location();
  std::vector<Bvariable*> vars;
  this->backend()->block(fndecl, NULL, vars, pkg_loc, pkg_loc);

  if (!this->backend()->function_set_body(fndecl, code_stmt))
    {
      go_assert(saw_errors());
      return NULL;
    }
  return initfn;
}

// Given an expression, collect all the global variables defined in
// this package that it references.

class Find_vars : public Traverse
{
 private:
  // The list of variables we accumulate.
  typedef Unordered_set(Named_object*) Vars;

  // A hash table we use to avoid looping.  The index is a
  // Named_object* or a Temporary_statement*.  We only look through
  // objects defined in this package.
  typedef Unordered_set(const void*) Seen_objects;

 public:
  Find_vars()
    : Traverse(traverse_expressions),
      vars_(), seen_objects_()
  { }

  // An iterator through the variables found, after the traversal.
  typedef Vars::const_iterator const_iterator;

  const_iterator
  begin() const
  { return this->vars_.begin(); }

  const_iterator
  end() const
  { return this->vars_.end(); }

  int
  expression(Expression**);

 private:
  // Accumulated variables.
  Vars vars_;
  // Objects we have already seen.
  Seen_objects seen_objects_;
};

// Collect global variables referenced by EXPR.  Look through function
// calls and variable initializations.

int
Find_vars::expression(Expression** pexpr)
{
  Expression* e = *pexpr;

  Var_expression* ve = e->var_expression();
  if (ve != NULL)
    {
      Named_object* v = ve->named_object();
      if (!v->is_variable() || v->package() != NULL)
	{
	  // This is a result parameter or a variable defined in a
	  // different package.  Either way we don't care about it.
	  return TRAVERSE_CONTINUE;
	}

      std::pair<Seen_objects::iterator, bool> ins =
	this->seen_objects_.insert(v);
      if (!ins.second)
	{
	  // We've seen this variable before.
	  return TRAVERSE_CONTINUE;
	}

      if (v->var_value()->is_global())
	this->vars_.insert(v);

      Expression* init = v->var_value()->init();
      if (init != NULL)
	{
	  if (Expression::traverse(&init, this) == TRAVERSE_EXIT)
	    return TRAVERSE_EXIT;
	}
    }

  // We traverse the code of any function or bound method we see.  Note that
  // this means that we will traverse the code of a function or bound method
  // whose address is taken even if it is not called.
  Func_expression* fe = e->func_expression();
  Bound_method_expression* bme = e->bound_method_expression();
  if (fe != NULL || bme != NULL)
    {
      const Named_object* f = fe != NULL ? fe->named_object() : bme->function();
      if (f->is_function() && f->package() == NULL)
	{
	  std::pair<Seen_objects::iterator, bool> ins =
	    this->seen_objects_.insert(f);
	  if (ins.second)
	    {
	      // This is the first time we have seen this name.
	      if (f->func_value()->block()->traverse(this) == TRAVERSE_EXIT)
		return TRAVERSE_EXIT;
	    }
	}
    }

  Temporary_reference_expression* tre = e->temporary_reference_expression();
  if (tre != NULL)
    {
      Temporary_statement* ts = tre->statement();
      Expression* init = ts->init();
      if (init != NULL)
	{
	  std::pair<Seen_objects::iterator, bool> ins =
	    this->seen_objects_.insert(ts);
	  if (ins.second)
	    {
	      // This is the first time we have seen this temporary
	      // statement.
	      if (Expression::traverse(&init, this) == TRAVERSE_EXIT)
		return TRAVERSE_EXIT;
	    }
	}
    }

  return TRAVERSE_CONTINUE;
}

// Return true if EXPR, PREINIT, or DEP refers to VAR.

static bool
expression_requires(Expression* expr, Block* preinit, Named_object* dep,
		    Named_object* var)
{
  Find_vars find_vars;
  if (expr != NULL)
    Expression::traverse(&expr, &find_vars);
  if (preinit != NULL)
    preinit->traverse(&find_vars);
  if (dep != NULL)
    {
      Expression* init = dep->var_value()->init();
      if (init != NULL)
	Expression::traverse(&init, &find_vars);
      if (dep->var_value()->has_pre_init())
	dep->var_value()->preinit()->traverse(&find_vars);
    }

  for (Find_vars::const_iterator p = find_vars.begin();
       p != find_vars.end();
       ++p)
    {
      if (*p == var)
	return true;
    }
  return false;
}

// Sort variable initializations.  If the initialization expression
// for variable A refers directly or indirectly to the initialization
// expression for variable B, then we must initialize B before A.

class Var_init
{
 public:
  Var_init()
    : var_(NULL), init_(NULL), refs_(NULL), dep_count_(0)
  { }

  Var_init(Named_object* var, Bstatement* init)
    : var_(var), init_(init), refs_(NULL), dep_count_(0)
  { }

  // Return the variable.
  Named_object*
  var() const
  { return this->var_; }

  // Return the initialization expression.
  Bstatement*
  init() const
  { return this->init_; }

  // Add a reference.
  void
  add_ref(Named_object* var);

  // The variables which this variable's initializers refer to.
  const std::vector<Named_object*>*
  refs()
  { return this->refs_; }

  // Clear the references, if any.
  void
  clear_refs();

  // Return the number of remaining dependencies.
  size_t
  dep_count() const
  { return this->dep_count_; }

  // Increment the number of dependencies.
  void
  add_dependency()
  { ++this->dep_count_; }

  // Decrement the number of dependencies.
  void
  remove_dependency()
  { --this->dep_count_; }

 private:
  // The variable being initialized.
  Named_object* var_;
  // The backend initialization statement.
  Bstatement* init_;
  // Variables this refers to.
  std::vector<Named_object*>* refs_;
  // The number of initializations this is dependent on.  A variable
  // initialization should not be emitted if any of its dependencies
  // have not yet been resolved.
  size_t dep_count_;
};

// Add a reference.

void
Var_init::add_ref(Named_object* var)
{
  if (this->refs_ == NULL)
    this->refs_ = new std::vector<Named_object*>;
  this->refs_->push_back(var);
}

// Clear the references, if any.

void
Var_init::clear_refs()
{
  if (this->refs_ != NULL)
    {
      delete this->refs_;
      this->refs_ = NULL;
    }
}

// For comparing Var_init keys in a map.

inline bool
operator<(const Var_init& v1, const Var_init& v2)
{ return v1.var()->name() < v2.var()->name(); }

typedef std::list<Var_init> Var_inits;

// Sort the variable initializations.  The rule we follow is that we
// emit them in the order they appear in the array, except that if the
// initialization expression for a variable V1 depends upon another
// variable V2 then we initialize V1 after V2.

static void
sort_var_inits(Gogo* gogo, Var_inits* var_inits)
{
  if (var_inits->empty())
    return;

  std::map<Named_object*, Var_init*> var_to_init;

  // A mapping from a variable initialization to a set of
  // variable initializations that depend on it.
  typedef std::map<Var_init, std::set<Var_init*> > Init_deps;
  Init_deps init_deps;
  bool init_loop = false;

  // Compute all variable references.
  for (Var_inits::iterator pvar = var_inits->begin();
       pvar != var_inits->end();
       ++pvar)
    {
      Named_object* var = pvar->var();
      var_to_init[var] = &*pvar;

      Find_vars find_vars;
      Expression* init = var->var_value()->init();
      if (init != NULL)
	Expression::traverse(&init, &find_vars);
      if (var->var_value()->has_pre_init())
	var->var_value()->preinit()->traverse(&find_vars);
      Named_object* dep = gogo->var_depends_on(var->var_value());
      if (dep != NULL)
	{
	  Expression* dinit = dep->var_value()->init();
	  if (dinit != NULL)
	    Expression::traverse(&dinit, &find_vars);
	  if (dep->var_value()->has_pre_init())
	    dep->var_value()->preinit()->traverse(&find_vars);
	}
      for (Find_vars::const_iterator p = find_vars.begin();
	   p != find_vars.end();
	   ++p)
	pvar->add_ref(*p);
    }

  // Add dependencies to init_deps, and check for cycles.
  for (Var_inits::iterator pvar = var_inits->begin();
       pvar != var_inits->end();
       ++pvar)
    {
      Named_object* var = pvar->var();

      const std::vector<Named_object*>* refs = pvar->refs();
      if (refs == NULL)
	continue;
      for (std::vector<Named_object*>::const_iterator pdep = refs->begin();
	   pdep != refs->end();
	   ++pdep)
	{
	  Named_object* dep = *pdep;
	  if (var == dep)
	    {
	      // This is a reference from a variable to itself, which
	      // may indicate a loop.  We only report an error if
	      // there is an initializer and there is no dependency.
	      // When there is no initializer, it means that the
	      // preinitializer sets the variable, which will appear
	      // to be a loop here.
	      if (var->var_value()->init() != NULL
		  && gogo->var_depends_on(var->var_value()) == NULL)
		go_error_at(var->location(),
			    ("initialization expression for %qs "
			     "depends upon itself"),
			    var->message_name().c_str());

	      continue;
	    }

	  Var_init* dep_init = var_to_init[dep];
	  if (dep_init == NULL)
	    {
	      // This is a dependency on some variable that doesn't
	      // have an initializer, so for purposes of
	      // initialization ordering this is irrelevant.
	      continue;
	    }

	  init_deps[*dep_init].insert(&(*pvar));
	  pvar->add_dependency();

	  // Check for cycles.
	  const std::vector<Named_object*>* deprefs = dep_init->refs();
	  if (deprefs == NULL)
	    continue;
	  for (std::vector<Named_object*>::const_iterator pdepdep =
		 deprefs->begin();
	       pdepdep != deprefs->end();
	       ++pdepdep)
	    {
	      if (*pdepdep == var)
		{
		  go_error_at(var->location(),
			      ("initialization expressions for %qs and "
			       "%qs depend upon each other"),
			      var->message_name().c_str(),
			      dep->message_name().c_str());
		  go_inform(dep->location(), "%qs defined here",
			    dep->message_name().c_str());
		  init_loop = true;
		  break;
		}
	    }
	}
    }

  var_to_init.clear();
  for (Var_inits::iterator pvar = var_inits->begin();
       pvar != var_inits->end();
       ++pvar)
    pvar->clear_refs();

  // If there are no dependencies then the declaration order is sorted.
  if (!init_deps.empty() && !init_loop)
    {
      // Otherwise, sort variable initializations by emitting all variables with
      // no dependencies in declaration order. VAR_INITS is already in
      // declaration order.
      Var_inits ready;
      while (!var_inits->empty())
	{
	  Var_inits::iterator v1;;
	  for (v1 = var_inits->begin(); v1 != var_inits->end(); ++v1)
	    {
	      if (v1->dep_count() == 0)
		break;
	    }
	  go_assert(v1 != var_inits->end());

	  // V1 either has no dependencies or its dependencies have already
	  // been emitted, add it to READY next.  When V1 is emitted, remove
	  // a dependency from each V that depends on V1.
	  ready.splice(ready.end(), *var_inits, v1);

	  Init_deps::iterator p1 = init_deps.find(*v1);
	  if (p1 != init_deps.end())
	    {
	      std::set<Var_init*> resolved = p1->second;
	      for (std::set<Var_init*>::iterator pv = resolved.begin();
		   pv != resolved.end();
		   ++pv)
		(*pv)->remove_dependency();
	      init_deps.erase(p1);
	    }
	}
      var_inits->swap(ready);
      go_assert(init_deps.empty());
    }
}

// Give an error if the initialization expression for VAR depends on
// itself.  We only check if INIT is not NULL and there is no
// dependency; when INIT is NULL, it means that PREINIT sets VAR,
// which we will interpret as a loop.

void
Gogo::check_self_dep(Named_object* var)
{
  Expression* init = var->var_value()->init();
  Block* preinit = var->var_value()->preinit();
  Named_object* dep = this->var_depends_on(var->var_value());
  if (init != NULL
      && dep == NULL
      && expression_requires(init, preinit, NULL, var))
    go_error_at(var->location(),
		"initialization expression for %qs depends upon itself",
		var->message_name().c_str());
}

// Write out the global definitions.

void
Gogo::write_globals()
{
  this->build_interface_method_tables();

  Bindings* bindings = this->current_bindings();

  for (Bindings::const_declarations_iterator p = bindings->begin_declarations();
       p != bindings->end_declarations();
       ++p)
    {
      // If any function declarations needed a descriptor, make sure
      // we build it.
      Named_object* no = p->second;
      if (no->is_function_declaration())
	no->func_declaration_value()->build_backend_descriptor(this);
    }

  // Lists of globally declared types, variables, constants, and functions
  // that must be defined.
  std::vector<Btype*> type_decls;
  std::vector<Bvariable*> var_decls;
  std::vector<Bexpression*> const_decls;
  std::vector<Bfunction*> func_decls;

  // The init function declaration and associated Bfunction, if necessary.
  Named_object* init_fndecl = NULL;
  Bfunction* init_bfn = NULL;

  std::vector<Bstatement*> init_stmts;
  std::vector<Bstatement*> var_init_stmts;

  if (this->is_main_package())
    {
      init_fndecl = this->initialization_function_decl();
      init_bfn = init_fndecl->func_value()->get_or_make_decl(this, init_fndecl);
    }

  // A list of variable initializations.
  Var_inits var_inits;

  // A list of variables which need to be registered with the garbage
  // collector.
  size_t count_definitions = bindings->size_definitions();
  std::vector<Named_object*> var_gc;
  var_gc.reserve(count_definitions);

  for (Bindings::const_definitions_iterator p = bindings->begin_definitions();
       p != bindings->end_definitions();
       ++p)
    {
      Named_object* no = *p;
      go_assert(!no->is_type_declaration() && !no->is_function_declaration());

      // There is nothing to do for a package.
      if (no->is_package())
        continue;

      // There is nothing to do for an object which was imported from
      // a different package into the global scope.
      if (no->package() != NULL)
        continue;

      // Skip blank named functions and constants.
      if ((no->is_function() && no->func_value()->is_sink())
	  || (no->is_const() && no->const_value()->is_sink()))
        continue;

      // There is nothing useful we can output for constants which
      // have ideal or non-integral type.
      if (no->is_const())
        {
          Type* type = no->const_value()->type();
          if (type == NULL)
            type = no->const_value()->expr()->type();
          if (type->is_abstract() || !type->is_numeric_type())
            continue;
        }

      if (!no->is_variable())
        no->get_backend(this, const_decls, type_decls, func_decls);
      else
	{
          Variable* var = no->var_value();
	  Bvariable* bvar = no->get_backend_variable(this, NULL);
          var_decls.push_back(bvar);

	  // Check for a sink variable, which may be used to run an
	  // initializer purely for its side effects.
	  bool is_sink = no->name()[0] == '_' && no->name()[1] == '.';

          Bstatement* var_init_stmt = NULL;
	  if (!var->has_pre_init())
	    {
              // If the backend representation of the variable initializer is
              // constant, we can just set the initial value using
              // global_var_set_init instead of during the init() function.
              // The initializer is constant if it is the zero-value of the
              // variable's type or if the initial value is an immutable value
              // that is not copied to the heap.
	      Expression* init = var->init();

	      // If we see "a = b; b = x", and x is a static
	      // initializer, just set a to x.
	      while (init != NULL && init->var_expression() != NULL)
		{
		  Named_object* ino = init->var_expression()->named_object();
		  if (!ino->is_variable() || ino->package() != NULL)
		    break;
		  Expression* ino_init = ino->var_value()->init();
		  if (ino->var_value()->has_pre_init()
		      || ino_init == NULL
		      || !ino_init->is_static_initializer())
		    break;
		  init = ino_init;
		}

              bool is_static_initializer;
              if (init == NULL)
                is_static_initializer = true;
              else
                {
                  Type* var_type = var->type();
                  init = Expression::make_cast(var_type, init, var->location());
                  is_static_initializer = init->is_static_initializer();
                }

	      // Non-constant variable initializations might need to create
	      // temporary variables, which will need the initialization
	      // function as context.
	      Named_object* var_init_fn;
	      if (is_static_initializer)
		var_init_fn = NULL;
	      else
		{
		  if (init_fndecl == NULL)
                    {
                      init_fndecl = this->initialization_function_decl();
                      Function* func = init_fndecl->func_value();
                      init_bfn = func->get_or_make_decl(this, init_fndecl);
                    }
		  var_init_fn = init_fndecl;
		}

	      Bexpression* var_binit;
	      if (init == NULL)
		var_binit = NULL;
	      else
		{
		  Translate_context context(this, var_init_fn, NULL, NULL);
		  var_binit = init->get_backend(&context);
		}

              if (var_binit == NULL)
		;
	      else if (is_static_initializer)
		{
		  if (expression_requires(var->init(), NULL,
					  this->var_depends_on(var), no))
		    go_error_at(no->location(),
				"initialization expression for %qs depends "
				"upon itself",
				no->message_name().c_str());
		  this->backend()->global_variable_set_init(bvar, var_binit);
		}
	      else if (is_sink)
	        var_init_stmt =
                    this->backend()->expression_statement(init_bfn, var_binit);
	      else
                {
                  Location loc = var->location();
                  Bexpression* var_expr =
                      this->backend()->var_expression(bvar, loc);
                  var_init_stmt =
                      this->backend()->assignment_statement(init_bfn, var_expr,
                                                            var_binit, loc);
                }
	    }
	  else
	    {
	      // We are going to create temporary variables which
	      // means that we need an fndecl.
              if (init_fndecl == NULL)
		init_fndecl = this->initialization_function_decl();

	      Bvariable* var_decl = is_sink ? NULL : bvar;
	      var_init_stmt = var->get_init_block(this, init_fndecl, var_decl);
	    }

	  if (var_init_stmt != NULL)
	    {
	      if (var->init() == NULL && !var->has_pre_init())
                var_init_stmts.push_back(var_init_stmt);
	      else
                var_inits.push_back(Var_init(no, var_init_stmt));
	    }
	  else if (this->var_depends_on(var) != NULL)
	    {
	      // This variable is initialized from something that is
	      // not in its init or preinit.  This variable needs to
	      // participate in dependency analysis sorting, in case
	      // some other variable depends on this one.
              Btype* btype = no->var_value()->type()->get_backend(this);
              Bexpression* zero = this->backend()->zero_expression(btype);
              Bstatement* zero_stmt =
                  this->backend()->expression_statement(init_bfn, zero);
	      var_inits.push_back(Var_init(no, zero_stmt));
	    }

	  // Collect a list of all global variables with pointers,
	  // to register them for the garbage collector.
	  if (!is_sink && var->type()->has_pointer())
	    {
	      // Avoid putting runtime.gcRoots itself on the list.
	      if (this->compiling_runtime()
		  && this->package_name() == "runtime"
		  && (Gogo::unpack_hidden_name(no->name()) == "gcRoots"
                   || Gogo::unpack_hidden_name(no->name()) == "gcRootsIndex"))
		;
	      else
		var_gc.push_back(no);
	    }
	}
    }

  // Output inline functions, which are in different packages.
  for (std::vector<Named_object*>::const_iterator p =
	 this->imported_inline_functions_.begin();
       p != this->imported_inline_functions_.end();
       ++p)
    (*p)->get_backend(this, const_decls, type_decls, func_decls);

  // Build the list of type descriptors.
  this->build_type_descriptor_list();

  if (this->is_main_package())
    {
      // Register the type descriptor lists, so that at run time
      // the reflect package can find compiler-created types, and
      // deduplicate if the same type is created with reflection.
      // This needs to be done before calling any package's init
      // function, as it may create type through reflection.
      this->register_type_descriptors(init_stmts, init_bfn);

      // Initialize imported packages.
      this->init_imports(init_stmts, init_bfn);
    }

  // Register global variables with the garbage collector.
  this->register_gc_vars(var_gc, init_stmts, init_bfn);

  // Simple variable initializations, after all variables are
  // registered.
  init_stmts.push_back(this->backend()->statement_list(var_init_stmts));

  // Complete variable initializations, first sorting them into a
  // workable order.
  if (!var_inits.empty())
    {
      sort_var_inits(this, &var_inits);
      for (Var_inits::const_iterator p = var_inits.begin();
           p != var_inits.end();
           ++p)
        init_stmts.push_back(p->init());
    }

  // After all the variables are initialized, call the init
  // functions if there are any.  Init functions take no arguments, so
  // we pass in EMPTY_ARGS to call them.
  std::vector<Bexpression*> empty_args;
  for (std::vector<Named_object*>::const_iterator p =
           this->init_functions_.begin();
       p != this->init_functions_.end();
       ++p)
    {
      Location func_loc = (*p)->location();
      Function* func = (*p)->func_value();
      Bfunction* initfn = func->get_or_make_decl(this, *p);
      Bexpression* func_code =
          this->backend()->function_code_expression(initfn, func_loc);
      Bexpression* call = this->backend()->call_expression(init_bfn, func_code,
                                                           empty_args,
							   NULL, func_loc);
      Bstatement* ist = this->backend()->expression_statement(init_bfn, call);
      init_stmts.push_back(ist);
    }

  // Set up a magic function to do all the initialization actions.
  // This will be called if this package is imported.
  Bstatement* init_fncode = this->backend()->statement_list(init_stmts);
  if (this->need_init_fn_ || this->is_main_package())
    {
      init_fndecl =
	this->create_initialization_function(init_fndecl, init_fncode);
      if (init_fndecl != NULL)
	func_decls.push_back(init_fndecl->func_value()->get_decl());
    }

  // We should not have seen any new bindings created during the conversion.
  go_assert(count_definitions == this->current_bindings()->size_definitions());

  // Define all globally declared values.
  if (!saw_errors())
    this->backend()->write_global_definitions(type_decls, const_decls,
					      func_decls, var_decls);
}

// Return the current block.

Block*
Gogo::current_block()
{
  if (this->functions_.empty())
    return NULL;
  else
    return this->functions_.back().blocks.back();
}

// Look up a name in the current binding contour.  If PFUNCTION is not
// NULL, set it to the function in which the name is defined, or NULL
// if the name is defined in global scope.

Named_object*
Gogo::lookup(const std::string& name, Named_object** pfunction) const
{
  if (pfunction != NULL)
    *pfunction = NULL;

  if (Gogo::is_sink_name(name))
    return Named_object::make_sink();

  for (Open_functions::const_reverse_iterator p = this->functions_.rbegin();
       p != this->functions_.rend();
       ++p)
    {
      Named_object* ret = p->blocks.back()->bindings()->lookup(name);
      if (ret != NULL)
	{
	  if (pfunction != NULL)
	    *pfunction = p->function;
	  return ret;
	}
    }

  if (this->package_ != NULL)
    {
      Named_object* ret = this->package_->bindings()->lookup(name);
      if (ret != NULL)
	{
	  if (ret->package() != NULL)
            {
              std::string dot_alias = "." + ret->package()->package_name();
              ret->package()->note_usage(dot_alias);
            }
	  return ret;
	}
    }

  // We do not look in the global namespace.  If we did, the global
  // namespace would effectively hide names which were defined in
  // package scope which we have not yet seen.  Instead,
  // define_global_names is called after parsing is over to connect
  // undefined names at package scope with names defined at global
  // scope.

  return NULL;
}

// Look up a name in the current block, without searching enclosing
// blocks.

Named_object*
Gogo::lookup_in_block(const std::string& name) const
{
  go_assert(!this->functions_.empty());
  go_assert(!this->functions_.back().blocks.empty());
  return this->functions_.back().blocks.back()->bindings()->lookup_local(name);
}

// Look up a name in the global namespace.

Named_object*
Gogo::lookup_global(const char* name) const
{
  return this->globals_->lookup(name);
}

// Add an imported package.

Package*
Gogo::add_imported_package(const std::string& real_name,
			   const std::string& alias_arg,
			   bool is_alias_exported,
			   const std::string& pkgpath,
			   const std::string& pkgpath_symbol,
			   Location location,
			   bool* padd_to_globals)
{
  Package* ret = this->register_package(pkgpath, pkgpath_symbol, location);
  ret->set_package_name(real_name, location);

  *padd_to_globals = false;

  if (alias_arg == "_")
    ;
  else if (alias_arg == ".")
    {
      *padd_to_globals = true;
      std::string dot_alias = "." + real_name;
      ret->add_alias(dot_alias, location);
    }
  else
    {
      std::string alias = alias_arg;
      if (alias.empty())
	{
	  alias = real_name;
	  is_alias_exported = Lex::is_exported_name(alias);
	}
      ret->add_alias(alias, location);
      alias = this->pack_hidden_name(alias, is_alias_exported);
      Named_object* no = this->package_->bindings()->add_package(alias, ret);
      if (!no->is_package())
	return NULL;
    }

  return ret;
}

// Register a package.  This package may or may not be imported.  This
// returns the Package structure for the package, creating if it
// necessary.  LOCATION is the location of the import statement that
// led us to see this package.  PKGPATH_SYMBOL is the symbol to use
// for names in the package; it may be the empty string, in which case
// we either get it later or make a guess when we need it.

Package*
Gogo::register_package(const std::string& pkgpath,
		       const std::string& pkgpath_symbol, Location location)
{
  Package* package = NULL;
  std::pair<Packages::iterator, bool> ins =
    this->packages_.insert(std::make_pair(pkgpath, package));
  if (!ins.second)
    {
      // We have seen this package name before.
      package = ins.first->second;
      go_assert(package != NULL && package->pkgpath() == pkgpath);
      if (!pkgpath_symbol.empty())
	package->set_pkgpath_symbol(pkgpath_symbol);
      if (Linemap::is_unknown_location(package->location()))
	package->set_location(location);
    }
  else
    {
      // First time we have seen this package name.
      package = new Package(pkgpath, pkgpath_symbol, location);
      go_assert(ins.first->second == NULL);
      ins.first->second = package;
    }

  return package;
}

// Return the pkgpath symbol for a package, given the pkgpath.

std::string
Gogo::pkgpath_symbol_for_package(const std::string& pkgpath)
{
  Packages::iterator p = this->packages_.find(pkgpath);
  go_assert(p != this->packages_.end());
  return p->second->pkgpath_symbol();
}

// Start compiling a function.

Named_object*
Gogo::start_function(const std::string& name, Function_type* type,
		     bool add_method_to_type, Location location)
{
  bool at_top_level = this->functions_.empty();

  Block* block = new Block(NULL, location);

  Named_object* enclosing = (at_top_level
			 ? NULL
			 : this->functions_.back().function);

  Function* function = new Function(type, enclosing, block, location);

  if (type->is_method())
    {
      const Typed_identifier* receiver = type->receiver();
      Variable* this_param = new Variable(receiver->type(), NULL, false,
					  true, true, location);
      std::string rname = receiver->name();
      unsigned rcounter = 0;

      // We need to give a nameless receiver parameter a synthesized name to
      // avoid having it clash with some other nameless param. FIXME.
      Gogo::rename_if_empty(&rname, "r", &rcounter);

      block->bindings()->add_variable(rname, NULL, this_param);
    }

  const Typed_identifier_list* parameters = type->parameters();
  bool is_varargs = type->is_varargs();
  unsigned pcounter = 0;
  if (parameters != NULL)
    {
      for (Typed_identifier_list::const_iterator p = parameters->begin();
	   p != parameters->end();
	   ++p)
	{
	  Variable* param = new Variable(p->type(), NULL, false, true, false,
					 p->location());
	  if (is_varargs && p + 1 == parameters->end())
	    param->set_is_varargs_parameter();

	  std::string pname = p->name();

          // We need to give each nameless parameter a non-empty name to avoid
          // having it clash with some other nameless param. FIXME.
          Gogo::rename_if_empty(&pname, "p", &pcounter);

	  block->bindings()->add_variable(pname, NULL, param);
	}
    }

  function->create_result_variables(this);

  const std::string* pname;
  std::string nested_name;
  bool is_init = false;
  if (Gogo::unpack_hidden_name(name) == "init" && !type->is_method())
    {
      if ((type->parameters() != NULL && !type->parameters()->empty())
	  || (type->results() != NULL && !type->results()->empty()))
	go_error_at(location,
		    "func init must have no arguments and no return values");
      // There can be multiple "init" functions, so give them each a
      // different name.
      nested_name = this->init_function_name();
      pname = &nested_name;
      is_init = true;
    }
  else if (!name.empty())
    pname = &name;
  else
    {
      // Invent a name for a nested function.
      nested_name = this->nested_function_name(enclosing);
      pname = &nested_name;
    }

  Named_object* ret;
  if (Gogo::is_sink_name(*pname))
    {
      std::string sname(this->sink_function_name());
      ret = Named_object::make_function(sname, NULL, function);
      ret->func_value()->set_is_sink();

      if (!type->is_method())
	ret = this->package_->bindings()->add_named_object(ret);
      else if (add_method_to_type)
	{
	  // We should report errors even for sink methods.
	  Type* rtype = type->receiver()->type();
	  // Avoid points_to and deref to avoid getting an error if
	  // the type is not yet defined.
	  if (rtype->classification() == Type::TYPE_POINTER)
	    rtype = rtype->points_to();
	  while (rtype->named_type() != NULL
		 && rtype->named_type()->is_alias())
	    rtype = rtype->named_type()->real_type()->forwarded();
	  if (rtype->is_error_type())
	    ;
	  else if (rtype->named_type() != NULL)
	    {
	      if (rtype->named_type()->named_object()->package() != NULL)
		go_error_at(type->receiver()->location(),
			    "may not define methods on non-local type");
	    }
	  else if (rtype->forward_declaration_type() != NULL)
	    {
	      // Go ahead and add the method in case we need to report
	      // an error when we see the definition.
	      rtype->forward_declaration_type()->add_existing_method(ret);
	    }
	  else
	    go_error_at(type->receiver()->location(),
			("invalid receiver type "
			 "(receiver must be a named type)"));
	}
    }
  else if (!type->is_method())
    {
      ret = this->package_->bindings()->add_function(*pname, NULL, function);
      if (!ret->is_function() || ret->func_value() != function)
	{
	  // Redefinition error.  Invent a name to avoid knockon
	  // errors.
	  std::string rname(this->redefined_function_name());
	  ret = this->package_->bindings()->add_function(rname, NULL, function);
	}
    }
  else
    {
      if (!add_method_to_type)
	ret = Named_object::make_function(name, NULL, function);
      else
	{
	  go_assert(at_top_level);
	  Type* rtype = type->receiver()->type();

	  while (rtype->named_type() != NULL
		 && rtype->named_type()->is_alias())
	    rtype = rtype->named_type()->real_type()->forwarded();

	  // We want to look through the pointer created by the
	  // parser, without getting an error if the type is not yet
	  // defined.
	  if (rtype->classification() == Type::TYPE_POINTER)
	    rtype = rtype->points_to();

	  while (rtype->named_type() != NULL
		 && rtype->named_type()->is_alias())
	    rtype = rtype->named_type()->real_type()->forwarded();

	  if (rtype->is_error_type())
	    ret = Named_object::make_function(name, NULL, function);
	  else if (rtype->named_type() != NULL)
	    {
	      if (rtype->named_type()->named_object()->package() != NULL)
		{
		  go_error_at(type->receiver()->location(),
			      "may not define methods on non-local type");
		  ret = Named_object::make_function(name, NULL, function);
		}
	      else
		{
		  ret = rtype->named_type()->add_method(name, function);
		  if (!ret->is_function())
		    {
		      // Redefinition error.
		      ret = Named_object::make_function(name, NULL, function);
		    }
		}
	    }
	  else if (rtype->forward_declaration_type() != NULL)
	    {
	      Named_object* type_no =
		rtype->forward_declaration_type()->named_object();
	      if (type_no->is_unknown())
		{
		  // If we are seeing methods it really must be a
		  // type.  Declare it as such.  An alternative would
		  // be to support lists of methods for unknown
		  // expressions.  Either way the error messages if
		  // this is not a type are going to get confusing.
		  Named_object* declared =
		    this->declare_package_type(type_no->name(),
					       type_no->location());
		  go_assert(declared
			     == type_no->unknown_value()->real_named_object());
		}
	      ret = rtype->forward_declaration_type()->add_method(name,
								  function);
	    }
	  else
            {
	      go_error_at(type->receiver()->location(),
			  ("invalid receiver type (receiver must "
			   "be a named type)"));
              ret = Named_object::make_function(name, NULL, function);
            }
	}
      this->package_->bindings()->add_method(ret);
    }

  this->functions_.resize(this->functions_.size() + 1);
  Open_function& of(this->functions_.back());
  of.function = ret;
  of.blocks.push_back(block);

  if (is_init)
    {
      this->init_functions_.push_back(ret);
      this->need_init_fn_ = true;
    }

  return ret;
}

// Finish compiling a function.

void
Gogo::finish_function(Location location)
{
  this->finish_block(location);
  go_assert(this->functions_.back().blocks.empty());
  this->functions_.pop_back();
}

// Return the current function.

Named_object*
Gogo::current_function() const
{
  go_assert(!this->functions_.empty());
  return this->functions_.back().function;
}

// Start a new block.

void
Gogo::start_block(Location location)
{
  go_assert(!this->functions_.empty());
  Block* block = new Block(this->current_block(), location);
  this->functions_.back().blocks.push_back(block);
}

// Finish a block.

Block*
Gogo::finish_block(Location location)
{
  go_assert(!this->functions_.empty());
  go_assert(!this->functions_.back().blocks.empty());
  Block* block = this->functions_.back().blocks.back();
  this->functions_.back().blocks.pop_back();
  block->set_end_location(location);
  return block;
}

// Add an erroneous name.

Named_object*
Gogo::add_erroneous_name(const std::string& name)
{
  return this->package_->bindings()->add_erroneous_name(name);
}

// Add an unknown name.

Named_object*
Gogo::add_unknown_name(const std::string& name, Location location)
{
  return this->package_->bindings()->add_unknown_name(name, location);
}

// Declare a function.

Named_object*
Gogo::declare_function(const std::string& name, Function_type* type,
		       Location location)
{
  if (!type->is_method())
    return this->current_bindings()->add_function_declaration(name, NULL, type,
							      location);
  else
    {
      // We don't bother to add this to the list of global
      // declarations.
      Type* rtype = type->receiver()->type();

      while (rtype->named_type() != NULL
	  && rtype->named_type()->is_alias())
	rtype = rtype->named_type()->real_type()->forwarded();

      // We want to look through the pointer created by the
      // parser, without getting an error if the type is not yet
      // defined.
      if (rtype->classification() == Type::TYPE_POINTER)
	rtype = rtype->points_to();

      while (rtype->named_type() != NULL
	  && rtype->named_type()->is_alias())
	rtype = rtype->named_type()->real_type()->forwarded();

      if (rtype->is_error_type())
	return NULL;
      else if (rtype->named_type() != NULL)
	return rtype->named_type()->add_method_declaration(name, NULL, type,
							   location);
      else if (rtype->forward_declaration_type() != NULL)
	{
	  Forward_declaration_type* ftype = rtype->forward_declaration_type();
	  return ftype->add_method_declaration(name, NULL, type, location);
	}
      else
        {
	  go_error_at(type->receiver()->location(),
		      "invalid receiver type (receiver must be a named type)");
          return Named_object::make_erroneous_name(name);
        }
    }
}

// Add a label definition.

Label*
Gogo::add_label_definition(const std::string& label_name,
			   Location location)
{
  go_assert(!this->functions_.empty());
  Function* func = this->functions_.back().function->func_value();
  Label* label = func->add_label_definition(this, label_name, location);
  this->add_statement(Statement::make_label_statement(label, location));
  return label;
}

// Add a label reference.

Label*
Gogo::add_label_reference(const std::string& label_name,
			  Location location, bool issue_goto_errors)
{
  go_assert(!this->functions_.empty());
  Function* func = this->functions_.back().function->func_value();
  return func->add_label_reference(this, label_name, location,
				   issue_goto_errors);
}

// Return the current binding state.

Bindings_snapshot*
Gogo::bindings_snapshot(Location location)
{
  return new Bindings_snapshot(this->current_block(), location);
}

// Add a statement.

void
Gogo::add_statement(Statement* statement)
{
  go_assert(!this->functions_.empty()
	     && !this->functions_.back().blocks.empty());
  this->functions_.back().blocks.back()->add_statement(statement);
}

// Add a block.

void
Gogo::add_block(Block* block, Location location)
{
  go_assert(!this->functions_.empty()
	     && !this->functions_.back().blocks.empty());
  Statement* statement = Statement::make_block_statement(block, location);
  this->functions_.back().blocks.back()->add_statement(statement);
}

// Add a constant.

Named_object*
Gogo::add_constant(const Typed_identifier& tid, Expression* expr,
		   int iota_value)
{
  return this->current_bindings()->add_constant(tid, NULL, expr, iota_value);
}

// Add a type.

void
Gogo::add_type(const std::string& name, Type* type, Location location)
{
  Named_object* no = this->current_bindings()->add_type(name, NULL, type,
							location);
  if (!this->in_global_scope() && no->is_type())
    {
      Named_object* f = this->functions_.back().function;
      unsigned int index;
      if (f->is_function())
	index = f->func_value()->new_local_type_index();
      else
	index = 0;
      no->type_value()->set_in_function(f, index);
    }
}

// Add a named type.

void
Gogo::add_named_type(Named_type* type)
{
  go_assert(this->in_global_scope());
  this->current_bindings()->add_named_type(type);
}

// Declare a type.

Named_object*
Gogo::declare_type(const std::string& name, Location location)
{
  Bindings* bindings = this->current_bindings();
  Named_object* no = bindings->add_type_declaration(name, NULL, location);
  if (!this->in_global_scope() && no->is_type_declaration())
    {
      Named_object* f = this->functions_.back().function;
      unsigned int index;
      if (f->is_function())
	index = f->func_value()->new_local_type_index();
      else
	index = 0;
      no->type_declaration_value()->set_in_function(f, index);
    }
  return no;
}

// Declare a type at the package level.

Named_object*
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);
}

// Add a function declaration to the list of functions we may want to
// inline.

void
Gogo::add_imported_inlinable_function(Named_object* no)
{
  go_assert(no->is_function_declaration());
  Function_declaration* fd = no->func_declaration_value();
  if (fd->is_on_inlinable_list())
    return;
  this->imported_inlinable_functions_.push_back(no);
  fd->set_is_on_inlinable_list();
}

// Define a type which was already declared.

void
Gogo::define_type(Named_object* no, Named_type* type)
{
  this->current_bindings()->define_type(no, type);
}

// Add a variable.

Named_object*
Gogo::add_variable(const std::string& name, Variable* variable)
{
  Named_object* no = this->current_bindings()->add_variable(name, NULL,
							    variable);

  // In a function the middle-end wants to see a DECL_EXPR node.
  if (no != NULL
      && no->is_variable()
      && !no->var_value()->is_parameter()
      && !this->functions_.empty())
    this->add_statement(Statement::make_variable_declaration(no));

  return no;
}

void
Gogo::rename_if_empty(std::string* pname, const char* tag, unsigned* count)
{
  if (pname->empty() || Gogo::is_sink_name(*pname))
    {
      char buf[50];
      go_assert(strlen(tag) < 10);
      snprintf(buf, sizeof buf, "%s.%u", tag, *count);
      ++(*count);
      *pname = buf;
    }
}


// Add a sink--a reference to the blank identifier _.

Named_object*
Gogo::add_sink()
{
  return Named_object::make_sink();
}

// Add a named object for a dot import.

void
Gogo::add_dot_import_object(Named_object* no)
{
  // If the name already exists, then it was defined in some file seen
  // earlier.  If the earlier name is just a declaration, don't add
  // this name, because that will cause the previous declaration to
  // merge to this imported name, which should not happen.  Just add
  // this name to the list of file block names to get appropriate
  // errors if we see a later definition.
  Named_object* e = this->package_->bindings()->lookup(no->name());
  if (e != NULL && e->package() == NULL)
    {
      if (e->is_unknown())
	e = e->resolve();
      if (e->package() == NULL
	  && (e->is_type_declaration()
	      || e->is_function_declaration()
	      || e->is_unknown()))
	{
	  this->add_file_block_name(no->name(), no->location());
	  return;
	}
    }

  this->current_bindings()->add_named_object(no);
}

// Add a linkname.  This implements the go:linkname compiler directive.
// We only support this for functions and function declarations.

void
Gogo::add_linkname(const std::string& go_name, bool is_exported,
		   const std::string& ext_name, Location loc)
{
  Named_object* no =
    this->package_->bindings()->lookup(this->pack_hidden_name(go_name,
							      is_exported));
  if (no == NULL)
    go_error_at(loc, "%s is not defined", go_name.c_str());
  else if (no->is_function())
    {
      if (ext_name.empty())
	no->func_value()->set_is_exported_by_linkname();
      else
	no->func_value()->set_asm_name(ext_name);
    }
  else if (no->is_function_declaration())
    {
      if (ext_name.empty())
	go_error_at(loc,
		    ("%<//go:linkname%> missing external name "
		     "for declaration of %s"),
		    go_name.c_str());
      else
	no->func_declaration_value()->set_asm_name(ext_name);
    }
  else
    go_error_at(loc,
		("%s is not a function; "
		 "%<//go:linkname%> is only supported for functions"),
		go_name.c_str());
}

// Mark all local variables used.  This is used when some types of
// parse error occur.

void
Gogo::mark_locals_used()
{
  for (Open_functions::iterator pf = this->functions_.begin();
       pf != this->functions_.end();
       ++pf)
    {
      for (std::vector<Block*>::iterator pb = pf->blocks.begin();
	   pb != pf->blocks.end();
	   ++pb)
	(*pb)->bindings()->mark_locals_used();
    }
}

// Record that we've seen an interface type.

void
Gogo::record_interface_type(Interface_type* itype)
{
  this->interface_types_.push_back(itype);
}

// Define the global names.  We do this only after parsing all the
// input files, because the program might define the global names
// itself.

void
Gogo::define_global_names()
{
  if (this->is_main_package())
    {
      // Every Go program has to import the runtime package, so that
      // it is properly initialized.  We can't use
      // predeclared_location here as it will cause runtime functions
      // to appear to be builtin functions.
      this->import_package("runtime", "_", false, false,
			   this->package_->location());
    }

  for (Bindings::const_declarations_iterator p =
	 this->globals_->begin_declarations();
       p != this->globals_->end_declarations();
       ++p)
    {
      Named_object* global_no = p->second;
      std::string name(Gogo::pack_hidden_name(global_no->name(), false));
      Named_object* no = this->package_->bindings()->lookup(name);
      if (no == NULL)
	continue;
      no = no->resolve();
      if (no->is_type_declaration())
	{
	  if (global_no->is_type())
	    {
	      if (no->type_declaration_value()->has_methods())
		{
		  for (std::vector<Named_object*>::const_iterator pm =
			 no->type_declaration_value()->methods()->begin();
		       pm != no->type_declaration_value()->methods()->end();
		       pm++)
		    go_error_at((*pm)->location(),
				"may not define methods on non-local type");
		}
	      no->set_type_value(global_no->type_value());
	    }
	  else
	    {
	      go_error_at(no->location(), "expected type");
	      Type* errtype = Type::make_error_type();
	      Named_object* err =
                Named_object::make_type("erroneous_type", NULL, errtype,
                                        Linemap::predeclared_location());
	      no->set_type_value(err->type_value());
	    }
	}
      else if (no->is_unknown())
	no->unknown_value()->set_real_named_object(global_no);
    }

  // Give an error if any name is defined in both the package block
  // and the file block.  For example, this can happen if one file
  // imports "fmt" and another file defines a global variable fmt.
  for (Bindings::const_declarations_iterator p =
	 this->package_->bindings()->begin_declarations();
       p != this->package_->bindings()->end_declarations();
       ++p)
    {
      if (p->second->is_unknown()
	  && p->second->unknown_value()->real_named_object() == NULL)
	{
	  // No point in warning about an undefined name, as we will
	  // get other errors later anyhow.
	  continue;
	}
      File_block_names::const_iterator pf =
	this->file_block_names_.find(p->second->name());
      if (pf != this->file_block_names_.end())
	{
	  std::string n = p->second->message_name();
	  go_error_at(p->second->location(),
		      "%qs defined as both imported name and global name",
		      n.c_str());
	  go_inform(pf->second, "%qs imported here", n.c_str());
	}

      // No package scope identifier may be named "init".
      if (!p->second->is_function()
	  && Gogo::unpack_hidden_name(p->second->name()) == "init")
	{
	  go_error_at(p->second->location(),
		      "cannot declare init - must be func");
	}
    }
}

// Clear out names in file scope.

void
Gogo::clear_file_scope()
{
  this->package_->bindings()->clear_file_scope(this);

  // Warn about packages which were imported but not used.
  bool quiet = saw_errors();
  for (Packages::iterator p = this->packages_.begin();
       p != this->packages_.end();
       ++p)
    {
      Package* package = p->second;
      if (package != this->package_ && !quiet)
        {
          for (Package::Aliases::const_iterator p1 = package->aliases().begin();
               p1 != package->aliases().end();
               ++p1)
            {
              if (!p1->second->used())
                {
                  // Give a more refined error message if the alias name is known.
                  std::string pkg_name = package->package_name();
                  if (p1->first != pkg_name && p1->first[0] != '.')
                    {
		      go_error_at(p1->second->location(),
				  "imported and not used: %s as %s",
				  Gogo::message_name(pkg_name).c_str(),
				  Gogo::message_name(p1->first).c_str());
                    }
                  else
		    go_error_at(p1->second->location(),
				"imported and not used: %s",
				Gogo::message_name(pkg_name).c_str());
                }
            }
        }
      package->clear_used();
    }

  this->current_file_imported_unsafe_ = false;
}

// Queue up a type-specific hash function for later writing.  These
// are written out in write_specific_type_functions, called after the
// parse tree is lowered.

void
Gogo::queue_hash_function(Type* type, int64_t size,
			  const std::string& hash_name,
			  Function_type* hash_fntype)
{
  go_assert(!this->specific_type_functions_are_written_);
  go_assert(!this->in_global_scope());
  Specific_type_function::Specific_type_function_kind kind =
    Specific_type_function::SPECIFIC_HASH;
  Specific_type_function* tsf = new Specific_type_function(type, NULL, size,
							   kind, hash_name,
							   hash_fntype);
  this->specific_type_functions_.push_back(tsf);
}

// Queue up a type-specific equal function for later writing.  These
// are written out in write_specific_type_functions, called after the
// parse tree is lowered.

void
Gogo::queue_equal_function(Type* type, Named_type* name, int64_t size,
			   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::Specific_type_function_kind kind =
    Specific_type_function::SPECIFIC_EQUAL;
  Specific_type_function* tsf = new Specific_type_function(type, name, size,
							   kind, equal_name,
							   equal_fntype);
  this->specific_type_functions_.push_back(tsf);
}

// Look for types which need specific hash or equality functions.

class Specific_type_functions : public Traverse
{
 public:
  Specific_type_functions(Gogo* gogo)
    : Traverse(traverse_types),
      gogo_(gogo)
  { }

  int
  type(Type*);

 private:
  Gogo* gogo_;
};

int
Specific_type_functions::type(Type* t)
{
  switch (t->classification())
    {
    case Type::TYPE_NAMED:
      {
	Named_type* nt = t->named_type();
	if (nt->is_alias())
	  return TRAVERSE_CONTINUE;
	if (t->needs_specific_type_functions(this->gogo_))
	  t->equal_function(this->gogo_, nt, NULL);

	// If this is a struct type, we don't want to make functions
	// for the unnamed struct.
	Type* rt = nt->real_type();
	if (rt->struct_type() == NULL)
	  {
	    if (Type::traverse(rt, this) == TRAVERSE_EXIT)
	      return TRAVERSE_EXIT;
	  }
	else
	  {
	    // If this type is defined in another package, then we don't
	    // need to worry about the unexported fields.
	    bool is_defined_elsewhere = nt->named_object()->package() != NULL;
	    const Struct_field_list* fields = rt->struct_type()->fields();
	    for (Struct_field_list::const_iterator p = fields->begin();
		 p != fields->end();
		 ++p)
	      {
		if (is_defined_elsewhere
		    && Gogo::is_hidden_name(p->field_name()))
		  continue;
		if (Type::traverse(p->type(), this) == TRAVERSE_EXIT)
		  return TRAVERSE_EXIT;
	      }
	  }

	return TRAVERSE_SKIP_COMPONENTS;
      }

    case Type::TYPE_STRUCT:
    case Type::TYPE_ARRAY:
      if (t->needs_specific_type_functions(this->gogo_))
	t->equal_function(this->gogo_, NULL, NULL);
      break;

    case Type::TYPE_MAP:
      {
	Type* key_type = t->map_type()->key_type();
	if (key_type->needs_specific_type_functions(this->gogo_))
	  key_type->hash_function(this->gogo_, NULL);
      }
      break;

    default:
      break;
    }

  return TRAVERSE_CONTINUE;
}

// Write out type specific functions.

void
Gogo::write_specific_type_functions()
{
  Specific_type_functions stf(this);
  this->traverse(&stf);

  while (!this->specific_type_functions_.empty())
    {
      Specific_type_function* tsf = this->specific_type_functions_.back();
      this->specific_type_functions_.pop_back();
      if (tsf->kind == Specific_type_function::SPECIFIC_HASH)
	tsf->type->write_hash_function(this, tsf->size, tsf->fnname,
				       tsf->fntype);
      else
	tsf->type->write_equal_function(this, tsf->name, tsf->size,
					tsf->fnname, tsf->fntype);
      delete tsf;
    }
  this->specific_type_functions_are_written_ = true;
}

// Traverse the tree.

void
Gogo::traverse(Traverse* traverse)
{
  // Traverse the current package first for consistency.  The other
  // packages will only contain imported types, constants, and
  // declarations.
  if (this->package_->bindings()->traverse(traverse, true) == TRAVERSE_EXIT)
    return;
  for (Packages::const_iterator p = this->packages_.begin();
       p != this->packages_.end();
       ++p)
    {
      if (p->second != this->package_)
	{
	  if (p->second->bindings()->traverse(traverse, true) == TRAVERSE_EXIT)
	    break;
	}
    }
}

// Add a type to verify.  This is used for types of sink variables, in
// order to give appropriate error messages.

void
Gogo::add_type_to_verify(Type* type)
{
  this->verify_types_.push_back(type);
}

// Traversal class used to verify types.

class Verify_types : public Traverse
{
 public:
  Verify_types()
    : Traverse(traverse_types)
  { }

  int
  type(Type*);
};

// Verify that a type is correct.

int
Verify_types::type(Type* t)
{
  if (!t->verify())
    return TRAVERSE_SKIP_COMPONENTS;
  return TRAVERSE_CONTINUE;
}

// Verify that all types are correct.

void
Gogo::verify_types()
{
  Verify_types traverse;
  this->traverse(&traverse);

  for (std::vector<Type*>::iterator p = this->verify_types_.begin();
       p != this->verify_types_.end();
       ++p)
    (*p)->verify();
  this->verify_types_.clear();
}

// Traversal class used to lower parse tree.

class Lower_parse_tree : public Traverse
{
 public:
  Lower_parse_tree(Gogo* gogo, Named_object* function)
    : Traverse(traverse_variables
	       | traverse_constants
	       | traverse_functions
	       | traverse_statements
	       | traverse_expressions),
      gogo_(gogo), function_(function), iota_value_(-1), inserter_()
  { }

  void
  set_inserter(const Statement_inserter* inserter)
  { this->inserter_ = *inserter; }

  int
  variable(Named_object*);

  int
  constant(Named_object*, bool);

  int
  function(Named_object*);

  int
  statement(Block*, size_t* pindex, Statement*);