compiler: revamp scheme for ordering calls to import init fcns.

    
    Switch to a new method for determining the order in which import init
    functions are invoked: build an init fcn dependence DAG and walk the DAG
    to rewrite/adjust priorities to account for discrepancies introduced by
    "go test".
    
    This patch includes a change to the export data format generated
    by gccgo. Older versions of gccgo will not be able to read object files
    produced by a newer gccgo, but the new gcc will still be able to read
    old object files.
    
    Fixes golang/go#15738.
    
    Reviewed-on: https://go-review.googlesource.com/25301

From-SVN: r239708

7 files changed, 538 insertions, 160 deletions

diff --git a/gcc/go/gofrontend/MERGE b/gcc/go/gofrontend/MERGE
index 0cf4f03..f73d5dd 100644
--- a/gcc/go/gofrontend/MERGE
+++ b/gcc/go/gofrontend/MERGE
@@ -1,4 +1,4 @@
-0476944600d456b2616981fff90c77be5e06edd5
+0e505f5d191182abd8beb9b4c8232174bc116f97
 
 The first line of this file holds the git revision number of the last
 merge done from the gofrontend repository.
diff --git a/gcc/go/gofrontend/export.cc b/gcc/go/gofrontend/export.cc
index e07246e..e9040ef 100644
--- a/gcc/go/gofrontend/export.cc
+++ b/gcc/go/gofrontend/export.cc
@@ -19,16 +19,21 @@
 
 // Class Export.
 
-// Version 1 magic number.
+const int Export::magic_len;
 
-const int Export::v1_magic_len;
+// Current version magic string.
+const char Export::cur_magic[Export::magic_len] =
+  {
+    'v', '2', ';', '\n'
+  };
 
-const char Export::v1_magic[Export::v1_magic_len] =
+// Magic string for previous version (still supported)
+const char Export::v1_magic[Export::magic_len] =
   {
     'v', '1', ';', '\n'
   };
 
-const int Export::v1_checksum_len;
+const int Export::checksum_len;
 
 // Constructor.
 
@@ -93,11 +98,10 @@ void
 Export::export_globals(const std::string& package_name,
 		       const std::string& prefix,
 		       const std::string& pkgpath,
-		       int package_priority,
 		       const std::map<std::string, Package*>& packages,
 		       const std::map<std::string, Package*>& imports,
 		       const std::string& import_init_fn,
-		       const std::set<Import_init>& imported_init_fns,
+                       const Import_init_set& imported_init_fns,
 		       const Bindings* bindings)
 {
   // If there have been any errors so far, don't try to export
@@ -134,8 +138,8 @@ Export::export_globals(const std::string& package_name,
 
   // Although the export data is readable, at least this version is,
   // it is conceptually a binary format.  Start with a four byte
-  // verison number.
-  this->write_bytes(Export::v1_magic, Export::v1_magic_len);
+  // version number.
+  this->write_bytes(Export::cur_magic, Export::magic_len);
 
   // The package name.
   this->write_c_string("package ");
@@ -156,16 +160,11 @@ Export::export_globals(const std::string& package_name,
     }
   this->write_c_string(";\n");
 
-  // The package priority.
-  char buf[100];
-  snprintf(buf, sizeof buf, "priority %d;\n", package_priority);
-  this->write_c_string(buf);
-
   this->write_packages(packages);
 
   this->write_imports(imports);
 
-  this->write_imported_init_fns(package_name, package_priority, import_init_fn,
+  this->write_imported_init_fns(package_name, import_init_fn,
 				imported_init_fns);
 
   // FIXME: It might be clever to add something about the processor
@@ -250,17 +249,17 @@ void
 Export::write_imports(const std::map<std::string, Package*>& imports)
 {
   // Sort the imports for more consistent output.
-  std::vector<std::pair<std::string, Package*> > imp;
+  std::vector<std::pair<std::string, Package*> > sorted_imports;
   for (std::map<std::string, Package*>::const_iterator p = imports.begin();
        p != imports.end();
        ++p)
-    imp.push_back(std::make_pair(p->first, p->second));
+    sorted_imports.push_back(std::make_pair(p->first, p->second));
 
-  std::sort(imp.begin(), imp.end(), import_compare);
+  std::sort(sorted_imports.begin(), sorted_imports.end(), import_compare);
 
   for (std::vector<std::pair<std::string, Package*> >::const_iterator p =
-	 imp.begin();
-       p != imp.end();
+	 sorted_imports.begin();
+       p != sorted_imports.end();
        ++p)
     {
       this->write_c_string("import ");
@@ -275,18 +274,62 @@ Export::write_imports(const std::map<std::string, Package*>& imports)
     }
 }
 
+void
+Export::add_init_graph_edge(Init_graph* init_graph, unsigned src, unsigned sink)
+{
+  Init_graph::iterator it = init_graph->find(src);
+  if (it != init_graph->end())
+    it->second.insert(sink);
+  else
+    {
+      std::set<unsigned> succs;
+      succs.insert(sink);
+      (*init_graph)[src] = succs;
+    }
+}
+
+// Constructs the imported portion of the init graph, e.g. those
+// edges that we read from imported packages.
+
+void
+Export::populate_init_graph(Init_graph* init_graph,
+                            const Import_init_set& imported_init_fns,
+                            const std::map<std::string, unsigned>& init_idx)
+{
+  for (Import_init_set::const_iterator p = imported_init_fns.begin();
+       p != imported_init_fns.end();
+       ++p)
+    {
+      const Import_init* ii = *p;
+      std::map<std::string, unsigned>::const_iterator srcit =
+          init_idx.find(ii->init_name());
+      go_assert(srcit != init_idx.end());
+      unsigned src = srcit->second;
+      for (std::set<std::string>::const_iterator pci = ii->precursors().begin();
+           pci != ii->precursors().end();
+           ++pci)
+	{
+	  std::map<std::string, unsigned>::const_iterator it =
+	      init_idx.find(*pci);
+	  go_assert(it != init_idx.end());
+	  unsigned sink = it->second;
+	  add_init_graph_edge(init_graph, src, sink);
+	}
+    }
+}
+
 // Write out the initialization functions which need to run for this
 // package.
 
 void
-Export::write_imported_init_fns(
-    const std::string& package_name,
-    int priority,
-    const std::string& import_init_fn,
-    const std::set<Import_init>& imported_init_fns)
+Export::write_imported_init_fns(const std::string& package_name,
+                                const std::string& import_init_fn,
+                                const Import_init_set& imported_init_fns)
 {
-  if (import_init_fn.empty() && imported_init_fns.empty())
-    return;
+  if (import_init_fn.empty() && imported_init_fns.empty()) return;
+
+  // Maps a given init function to the its index in the exported "init" clause.
+  std::map<std::string, unsigned> init_idx;
 
   this->write_c_string("init");
 
@@ -296,35 +339,154 @@ Export::write_imported_init_fns(
       this->write_string(package_name);
       this->write_c_string(" ");
       this->write_string(import_init_fn);
-      char buf[100];
-      snprintf(buf, sizeof buf, " %d", priority);
-      this->write_c_string(buf);
+      init_idx[import_init_fn] = 0;
     }
 
-  if (!imported_init_fns.empty())
+  if (imported_init_fns.empty())
     {
-      // Sort the list of functions for more consistent output.
-      std::vector<Import_init> v;
-      for (std::set<Import_init>::const_iterator p = imported_init_fns.begin();
-	   p != imported_init_fns.end();
-	   ++p)
-	v.push_back(*p);
-      std::sort(v.begin(), v.end());
-
-      for (std::vector<Import_init>::const_iterator p = v.begin();
-	   p != v.end();
-	   ++p)
+      this->write_c_string(";\n");
+      return;
+    }
+
+  typedef std::map<int, std::vector<std::string> > level_map;
+  Init_graph init_graph;
+  level_map inits_at_level;
+
+  // Walk through the set of import inits (already sorted by
+  // init fcn name) and write them out to the exports.
+  for (Import_init_set::const_iterator p = imported_init_fns.begin();
+       p != imported_init_fns.end();
+       ++p)
+    {
+      const Import_init* ii = *p;
+      this->write_c_string(" ");
+      this->write_string(ii->package_name());
+      this->write_c_string(" ");
+      this->write_string(ii->init_name());
+
+      // Populate init_idx.
+      go_assert(init_idx.find(ii->init_name()) == init_idx.end());
+      unsigned idx = init_idx.size();
+      init_idx[ii->init_name()] = idx;
+
+      // If the init function has a non-negative priority value, this
+      // is an indication that it was referred to in an older version
+      // export data section (e.g. we read a legacy object
+      // file). Record such init fcns so that we can fix up the graph
+      // for them (handled later in this function).
+      if (ii->priority() > 0)
+	{
+	  level_map::iterator it = inits_at_level.find(ii->priority());
+	  if (it == inits_at_level.end())
+	    {
+	      std::vector<std::string> l;
+	      l.push_back(ii->init_name());
+	      inits_at_level[ii->priority()] = l;
+	    }
+	  else
+	    it->second.push_back(ii->init_name());
+	}
+    }
+  this->write_c_string(";\n");
+
+  // Create the init graph. Start by populating the graph with
+  // all the edges we inherited from imported packages.
+  populate_init_graph(&init_graph, imported_init_fns, init_idx);
+
+  // Now add edges from the local init function to each of the
+  // imported fcns.
+  if (!import_init_fn.empty())
+    {
+      unsigned src = 0;
+      go_assert(init_idx[import_init_fn] == 0);
+      for (Import_init_set::const_iterator p = imported_init_fns.begin();
+           p != imported_init_fns.end();
+           ++p)
+	{
+          const Import_init* ii = *p;
+	  unsigned sink = init_idx[ii->init_name()];
+	  add_init_graph_edge(&init_graph, src, sink);
+	}
+    }
+
+  // In the scenario where one or more of the packages we imported
+  // was written with the legacy export data format, add dummy edges
+  // to capture the priority relationships. Here is a package import
+  // graph as an example:
+  //
+  //       *A
+  //       /|
+  //      / |
+  //     B  *C
+  //       /|
+  //      / |
+  //    *D *E
+  //     | /|
+  //     |/ |
+  //    *F  *G
+  //
+  // Let's suppose that the object for package "C" is from an old
+  // gccgo, e.g. it has the old export data format. All other
+  // packages are compiled with the new compiler and have the new
+  // format. Packages with *'s have init functions. The scenario is
+  // that we're compiling a package "A"; during this process we'll
+  // read the export data for "C". It should look something like
+  //
+  //   init F F..import 1 G G..import 1 D D..import 2 E E..import 2;
+  //
+  // To capture this information and convey it to the consumers of
+  // "A", the code below adds edges to the graph from each priority K
+  // function to every priority K-1 function for appropriate values
+  // of K. This will potentially add more edges than we need (for
+  // example, an edge from D to G), but given that we don't expect
+  // to see large numbers of old objects, this will hopefully be OK.
+
+  if (inits_at_level.size() > 0)
+    {
+      for (level_map::reverse_iterator it = inits_at_level.rbegin();
+           it != inits_at_level.rend(); ++it)
+	{
+	  int level = it->first;
+	  if (level < 2) break;
+	  const std::vector<std::string>& fcns_at_level = it->second;
+	  for (std::vector<std::string>::const_iterator sit =
+	           fcns_at_level.begin();
+	       sit != fcns_at_level.end(); ++sit)
+	    {
+	      unsigned src = init_idx[*sit];
+	      level_map::iterator it2 = inits_at_level.find(level - 1);
+	      if (it2 != inits_at_level.end())
+		{
+		  const std::vector<std::string> fcns_at_lm1 = it2->second;
+		  for (std::vector<std::string>::const_iterator mit =
+		           fcns_at_lm1.begin();
+		       mit != fcns_at_lm1.end(); ++mit)
+		    {
+		      unsigned sink = init_idx[*mit];
+		      add_init_graph_edge(&init_graph, src, sink);
+		    }
+		}
+	    }
+	}
+    }
+
+  // Write out the resulting graph.
+  this->write_c_string("init_graph");
+  for (Init_graph::const_iterator ki = init_graph.begin();
+       ki != init_graph.end(); ++ki)
+    {
+      unsigned src = ki->first;
+      const std::set<unsigned>& successors = ki->second;
+      for (std::set<unsigned>::const_iterator vi = successors.begin();
+           vi != successors.end(); ++vi)
 	{
 	  this->write_c_string(" ");
-	  this->write_string(p->package_name());
+	  this->write_unsigned(src);
+	  unsigned sink = (*vi);
 	  this->write_c_string(" ");
-	  this->write_string(p->init_name());
-	  char buf[100];
-	  snprintf(buf, sizeof buf, " %d", p->priority());
-	  this->write_c_string(buf);
+	  this->write_unsigned(sink);
 	}
     }
-
   this->write_c_string(";\n");
 }
 
@@ -339,6 +501,26 @@ Export::write_name(const std::string& name)
     this->write_string(Gogo::message_name(name));
 }
 
+// Write an integer value to the export stream.
+
+void
+Export::write_int(int value)
+{
+  char buf[100];
+  snprintf(buf, sizeof buf, "%d", value);
+  this->write_c_string(buf);
+}
+
+// Write an integer value to the export stream.
+
+void
+Export::write_unsigned(unsigned value)
+{
+  char buf[100];
+  snprintf(buf, sizeof buf, "%u", value);
+  this->write_c_string(buf);
+}
+
 // Export a type.  We have to ensure that on import we create a single
 // Named_type node for each named type.  We do this by keeping a hash
 // table mapping named types to reference numbers.  The first time we
@@ -531,11 +713,11 @@ Export::Stream::checksum()
   // Use a union to provide the required alignment.
   union
   {
-    char checksum[Export::v1_checksum_len];
+    char checksum[Export::checksum_len];
     long align;
   } u;
   sha1_finish_ctx(this->checksum_, u.checksum);
-  return std::string(u.checksum, Export::v1_checksum_len);
+  return std::string(u.checksum, Export::checksum_len);
 }
 
 // Write the checksum string to the export data.
diff --git a/gcc/go/gofrontend/export.h b/gcc/go/gofrontend/export.h
index c3972d8..ee61d27 100644
--- a/gcc/go/gofrontend/export.h
+++ b/gcc/go/gofrontend/export.h
@@ -15,6 +15,7 @@ class Import_init;
 class Bindings;
 class Type;
 class Package;
+class Import_init_set;
 
 // Codes used for the builtin types.  These are all negative to make
 // them easily distinct from the codes assigned by Export::write_type.
@@ -47,6 +48,17 @@ enum Builtin_code
   SMALLEST_BUILTIN_CODE = -21
 };
 
+// Export data version number. New export data is written with the
+// "current" version, but there is support for reading files with
+// older version export data (at least for now).
+
+enum Export_data_version {
+  EXPORT_FORMAT_UNKNOWN = 0,
+  EXPORT_FORMAT_V1 = 1,
+  EXPORT_FORMAT_V2 = 2,
+  EXPORT_FORMAT_CURRENT = EXPORT_FORMAT_V2
+};
+
 // This class manages exporting Go declarations.  It handles the main
 // loop of exporting.  A pointer to this class is also passed to the
 // various specific export implementations.
@@ -103,12 +115,15 @@ class Export : public String_dump
 
   Export(Stream*);
 
-  // The magic code for version 1 export data.
-  static const int v1_magic_len = 4;
-  static const char v1_magic[v1_magic_len];
+  // Size of export data magic string (which includes version number).
+  static const int magic_len = 4;
 
-  // The length of the v1 checksum string.
-  static const int v1_checksum_len = 20;
+  // Magic strings (current version and older v1 version).
+  static const char cur_magic[magic_len];
+  static const char v1_magic[magic_len];
+
+  // The length of the checksum string.
+  static const int checksum_len = 20;
 
   // Register the builtin types.
   void
@@ -119,7 +134,6 @@ class Export : public String_dump
   // is nothing to export, this->stream_->write will not be called.
   // PREFIX is the package prefix.  PKGPATH is the package path.
   // Only one of PREFIX and PKGPATH will be non-empty.
-  // PACKAGE_PRIORITY is the priority to use for this package.
   // PACKAGES is all the packages we have seen.
   // IMPORTS is the explicitly imported packages.
   // IMPORT_INIT_FN is the name of the import initialization function
@@ -130,11 +144,10 @@ class Export : public String_dump
   export_globals(const std::string& package_name,
 		 const std::string& prefix,
 		 const std::string& pkgpath,
-		 int package_priority,
 		 const std::map<std::string, Package*>& packages,
 		 const std::map<std::string, Package*>& imports,
 		 const std::string& import_init_fn,
-		 const std::set<Import_init>& imported_init_fns,
+		 const Import_init_set& imported_init_fns,
 		 const Bindings* bindings);
 
   // Write a string to the export stream.
@@ -166,6 +179,14 @@ class Export : public String_dump
   void
   write_escape(std::string* note);
 
+  // Write an integer value.
+  void
+  write_int(int);
+
+  // Write an unsigned value.
+  void
+  write_unsigned(unsigned);
+
  private:
   Export(const Export&);
   Export& operator=(const Export&);
@@ -174,14 +195,24 @@ class Export : public String_dump
   void
   write_packages(const std::map<std::string, Package*>& packages);
 
+  typedef std::map<unsigned, std::set<unsigned> > Init_graph;
+
+  static void
+  add_init_graph_edge(Init_graph* init_graph, unsigned src, unsigned sink);
+
+  static void
+  populate_init_graph(Init_graph* init_graph,
+                      const Import_init_set& imported_init_fns,
+                      const std::map<std::string, unsigned>& init_idx);
+
   // Write out the imported packages.
   void
   write_imports(const std::map<std::string, Package*>& imports);
 
-  // Write out the imported initialization functions.
+  // Write out the imported initialization functions and init graph.
   void
-  write_imported_init_fns(const std::string& package_name, int priority,
-			  const std::string&, const std::set<Import_init>&);
+  write_imported_init_fns(const std::string& package_name,
+			  const std::string&, const Import_init_set&);
 
   // Register one builtin type.
   void
diff --git a/gcc/go/gofrontend/gogo.cc b/gcc/go/gofrontend/gogo.cc
index 0bbf6ac..e1ebd65 100644
--- a/gcc/go/gofrontend/gogo.cc
+++ b/gcc/go/gofrontend/gogo.cc
@@ -513,40 +513,49 @@ Gogo::import_package(const std::string& filename,
   delete stream;
 }
 
+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 (std::set<Import_init>::const_iterator p =
+  for (Import_init_set::iterator p =
 	 this->imported_init_fns_.begin();
        p != this->imported_init_fns_.end();
        ++p)
     {
-      if (p->init_name() == init_name)
+      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 (p->package_name() != package_name)
+	  if (ii->package_name() != package_name)
 	    {
 	      error("duplicate package initialization name %qs",
 		    Gogo::message_name(init_name).c_str());
-	      inform(UNKNOWN_LOCATION, "used by package %qs at priority %d",
-		     Gogo::message_name(p->package_name()).c_str(),
-		     p->priority());
-	      inform(UNKNOWN_LOCATION, " and by package %qs at priority %d",
-		     Gogo::message_name(package_name).c_str(), prio);
+	      inform(UNKNOWN_LOCATION, "used by package %qs",
+		     Gogo::message_name(ii->package_name()).c_str());
+	      inform(UNKNOWN_LOCATION, " and by package %qs",
+		     Gogo::message_name(package_name).c_str());
 	    }
-	  return;
+          ii->set_priority(prio);
+          return;
 	}
     }
 
-  this->imported_init_fns_.insert(Import_init(package_name, init_name,
-					      prio));
+  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.
@@ -581,6 +590,62 @@ Gogo::current_bindings() const
     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 = this->lookup_init(*pci);
+          nonroots.insert(ii);
+        }
+    }
+
+  // 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.
@@ -598,23 +663,27 @@ Gogo::init_imports(std::vector<Bstatement*>& init_stmts)
       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<Import_init> v;
-  for (std::set<Import_init>::const_iterator p =
+  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)
     v.push_back(*p);
-  std::sort(v.begin(), v.end());
+  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<Import_init>::const_iterator p = v.begin();
+  for (std::vector<const Import_init*>::const_iterator p = v.begin();
        p != v.end();
        ++p)
     {
-      std::string user_name = p->package_name() + ".init";
-      const std::string& init_name(p->init_name());
+      const Import_init* ii = *p;
+      std::string user_name = ii->package_name() + ".init";
+      const std::string& init_name(ii->init_name());
 
       Bfunction* pfunc = this->backend()->function(fntype, user_name, init_name,
                                                    true, true, true, false,
@@ -4326,21 +4395,6 @@ Gogo::check_return_statements()
   this->traverse(&traverse);
 }
 
-// Work out the package priority.  It is one more than the maximum
-// priority of an imported package.
-
-int
-Gogo::package_priority() const
-{
-  int priority = 0;
-  for (Packages::const_iterator p = this->packages_.begin();
-       p != this->packages_.end();
-       ++p)
-    if (p->second->priority() > priority)
-      priority = p->second->priority();
-  return priority + 1;
-}
-
 // Export identifiers as requested.
 
 void
@@ -4368,7 +4422,6 @@ Gogo::do_exports()
   exp.export_globals(this->package_name(),
 		     prefix,
 		     pkgpath,
-		     this->package_priority(),
 		     this->packages_,
 		     this->imports_,
 		     (this->need_init_fn_ && !this->is_main_package()
@@ -7595,11 +7648,10 @@ Unnamed_label::get_goto(Translate_context* context, Location location)
 Package::Package(const std::string& pkgpath,
 		 const std::string& pkgpath_symbol, Location location)
   : pkgpath_(pkgpath), pkgpath_symbol_(pkgpath_symbol),
-    package_name_(), bindings_(new Bindings(NULL)), priority_(0),
+    package_name_(), bindings_(new Bindings(NULL)),
     location_(location)
 {
   go_assert(!pkgpath.empty());
-  
 }
 
 // Set the package name.
@@ -7640,16 +7692,6 @@ Package::set_pkgpath_symbol(const std::string& pkgpath_symbol)
     go_assert(this->pkgpath_symbol_ == pkgpath_symbol);
 }
 
-// Set the priority.  We may see multiple priorities for an imported
-// package; we want to use the largest one.
-
-void
-Package::set_priority(int priority)
-{
-  if (priority > this->priority_)
-    this->priority_ = priority;
-}
-
 // Note that symbol from this package was and qualified by ALIAS.
 
 void
diff --git a/gcc/go/gofrontend/gogo.h b/gcc/go/gofrontend/gogo.h
index d2262e3..0c45443 100644
--- a/gcc/go/gofrontend/gogo.h
+++ b/gcc/go/gofrontend/gogo.h
@@ -78,33 +78,64 @@ class Import_init
   init_name() const
   { return this->init_name_; }
 
-  // The priority of the initialization function.  Functions with a
-  // lower priority number must be run first.
+  // Older V1 export data uses a priority scheme to order
+  // initialization functions; functions with a lower priority number
+  // must be run first. This value will be set to -1 for current
+  // generation objects, and will take on a non-negative value only
+  // when importing a V1-vintage object.
   int
   priority() const
   { return this->priority_; }
 
+  // Reset priority.
+  void
+  set_priority(int new_priority)
+  { this->priority_ = new_priority; }
+
+  // Record the fact that some other init fcn must be run before this init fcn.
+  void
+  record_precursor_fcn(std::string init_fcn_name)
+  { this->precursor_functions_.insert(init_fcn_name); }
+
+  // Return the list of precursor fcns for this fcn (must be run before it).
+  const std::set<std::string>&
+  precursors() const
+  { return this->precursor_functions_; }
+
  private:
   // The name of the package being imported.
   std::string package_name_;
   // The name of the package's init function.
   std::string init_name_;
-  // The priority.
+  // Names of init functions that must be run before this fcn.
+  std::set<std::string> precursor_functions_;
+  // Priority for this function. See note above on obsolescence.
   int priority_;
 };
 
 // For sorting purposes.
 
+struct Import_init_lt {
+  bool operator()(const Import_init* i1, const Import_init* i2)
+  {
+    return i1->init_name() < i2->init_name();
+  }
+};
+
+// Set of import init objects.
+class Import_init_set : public std::set<Import_init*, Import_init_lt> {
+};
+
 inline bool
-operator<(const Import_init& i1, const Import_init& i2)
+priority_compare(const Import_init* i1, const Import_init* i2)
 {
-  if (i1.priority() < i2.priority())
+  if (i1->priority() < i2->priority())
     return true;
-  if (i1.priority() > i2.priority())
+  if (i1->priority() > i2->priority())
     return false;
-  if (i1.package_name() != i2.package_name())
-    return i1.package_name() < i2.package_name();
-  return i1.init_name() < i2.init_name();
+  if (i1->package_name() != i2->package_name())
+    return i1->package_name() < i2->package_name();
+  return i1->init_name() < i2->init_name();
 }
 
 // The holder for the internal representation of the entire
@@ -249,12 +280,6 @@ class Gogo
   set_debug_escape_level(int level)
   { this->debug_escape_level_ = level; }
 
-  // Return the priority to use for the package we are compiling.
-  // This is two more than the largest priority of any package we
-  // import.
-  int
-  package_priority() const;
-
   // Import a package.  FILENAME is the file name argument, LOCAL_NAME
   // is the local name to give to the package.  If LOCAL_NAME is empty
   // the declarations are added to the global scope.
@@ -609,6 +634,10 @@ class Gogo
   add_import_init_fn(const std::string& package_name,
 		     const std::string& init_name, int prio);
 
+  // Return the Import_init for a given init name.
+  Import_init*
+  lookup_init(const std::string& init_name);
+
   // Turn short-cut operators (&&, ||) into explicit if statements.
   void
   remove_shortcuts();
@@ -754,6 +783,15 @@ class Gogo
     { }
   };
 
+  // Recompute init priorities.
+  void
+  recompute_init_priorities();
+
+  // Recursive helper used by the routine above.
+  void
+  update_init_priority(Import_init* ii,
+                       std::set<const Import_init *>* visited);
+
   // The backend generator.
   Backend* backend_;
   // The object used to keep track of file names and line numbers.
@@ -787,7 +825,7 @@ class Gogo
   // The name of the magic initialization function.
   std::string init_fn_name_;
   // A list of import control variables for packages that we import.
-  std::set<Import_init> imported_init_fns_;
+  Import_init_set imported_init_fns_;
   // The package path used for reflection data.
   std::string pkgpath_;
   // The package path to use for a symbol name.
@@ -2875,17 +2913,6 @@ class Package
     return this->package_name_;
   }
 
-  // The priority of this package.  The init function of packages with
-  // lower priority must be run before the init function of packages
-  // with higher priority.
-  int
-  priority() const
-  { return this->priority_; }
-
-  // Set the priority.
-  void
-  set_priority(int priority);
-
   // Return the bindings.
   Bindings*
   bindings()
@@ -2977,10 +3004,6 @@ class Package
   std::string package_name_;
   // The names in this package.
   Bindings* bindings_;
-  // The priority of this package.  A package has a priority higher
-  // than the priority of all of the packages that it imports.  This
-  // is used to run init functions in the right order.
-  int priority_;
   // The location of the most recent import statement.
   Location location_;
   // The set of aliases associated with this package.
diff --git a/gcc/go/gofrontend/import.cc b/gcc/go/gofrontend/import.cc
index b90ea83..54fd4c9 100644
--- a/gcc/go/gofrontend/import.cc
+++ b/gcc/go/gofrontend/import.cc
@@ -200,8 +200,7 @@ Import::try_suffixes(std::string* pfilename)
 // Look for export data in the file descriptor FD.
 
 Import::Stream*
-Import::find_export_data(const std::string& filename, int fd,
-			 Location location)
+Import::find_export_data(const std::string& filename, int fd, Location location)
 {
   // See if we can read this as an object file.
   Import::Stream* stream = Import::find_object_export_data(filename, fd, 0,
@@ -209,7 +208,7 @@ Import::find_export_data(const std::string& filename, int fd,
   if (stream != NULL)
     return stream;
 
-  const int len = MAX(Export::v1_magic_len, Import::archive_magic_len);
+  const int len = MAX(Export::magic_len, Import::archive_magic_len);
 
   if (lseek(fd, 0, SEEK_SET) < 0)
     {
@@ -223,7 +222,8 @@ Import::find_export_data(const std::string& filename, int fd,
     return NULL;
 
   // Check for a file containing nothing but Go export data.
-  if (memcmp(buf, Export::v1_magic, Export::v1_magic_len) == 0)
+  if (memcmp(buf, Export::cur_magic, Export::magic_len) == 0 ||
+      memcmp(buf, Export::v1_magic, Export::magic_len) == 0)
     return new Stream_from_file(fd);
 
   // See if we can read this as an archive.
@@ -270,7 +270,7 @@ Import::Import(Stream* stream, Location location)
   : gogo_(NULL), stream_(stream), location_(location), package_(NULL),
     add_to_globals_(false),
     builtin_types_((- SMALLEST_BUILTIN_CODE) + 1),
-    types_()
+    types_(), version_(EXPORT_FORMAT_UNKNOWN)
 {
 }
 
@@ -293,8 +293,26 @@ Import::import(Gogo* gogo, const std::string& local_name,
       // The vector of types is package specific.
       this->types_.clear();
 
-      stream->require_bytes(this->location_, Export::v1_magic,
-			    Export::v1_magic_len);
+      // Check magic string / version number.
+      if (stream->match_bytes(Export::cur_magic, Export::magic_len))
+	{
+	  stream->require_bytes(this->location_, Export::cur_magic,
+	                        Export::magic_len);
+	  this->version_ = EXPORT_FORMAT_CURRENT;
+	}
+      else if (stream->match_bytes(Export::v1_magic, Export::magic_len))
+	{
+	  stream->require_bytes(this->location_, Export::v1_magic,
+	                        Export::magic_len);
+	  this->version_ = EXPORT_FORMAT_V1;
+	}
+      else
+	{
+	  error_at(this->location_,
+	           ("error in import data at %d: invalid magic string"),
+	           stream->pos());
+	  return NULL;
+	}
 
       this->require_c_string("package ");
       std::string package_name = this->read_identifier();
@@ -330,13 +348,16 @@ Import::import(Gogo* gogo, const std::string& local_name,
 	  return NULL;
 	}
 
-      this->require_c_string("priority ");
-      std::string priority_string = this->read_identifier();
-      int prio;
-      if (!this->string_to_int(priority_string, false, &prio))
-	return NULL;
-      this->package_->set_priority(prio);
-      this->require_c_string(";\n");
+      // Read and discard priority if older V1 export data format.
+      if (version() == EXPORT_FORMAT_V1)
+	{
+	  this->require_c_string("priority ");
+	  std::string priority_string = this->read_identifier();
+	  int prio;
+	  if (!this->string_to_int(priority_string, false, &prio))
+	    return NULL;
+	  this->require_c_string(";\n");
+	}
 
       while (stream->match_c_string("package"))
 	this->read_one_package();
@@ -377,7 +398,7 @@ Import::import(Gogo* gogo, const std::string& local_name,
       // verify that the checksum matches at link time or at dynamic
       // load time.
       this->require_c_string("checksum ");
-      stream->advance(Export::v1_checksum_len * 2);
+      stream->advance(Export::checksum_len * 2);
       this->require_c_string(";\n");
     }
 
@@ -423,26 +444,88 @@ Import::read_one_import()
   p->set_package_name(package_name, this->location());
 }
 
-// Read the list of import control functions.
+// Read the list of import control functions and/or init graph.
 
 void
 Import::read_import_init_fns(Gogo* gogo)
 {
   this->require_c_string("init");
+
+  // Maps init function to index in the "init" clause; needed
+  // to read the init_graph section.
+  std::map<std::string, unsigned> init_idx;
+
   while (!this->match_c_string(";"))
     {
+      int priority = -1;
+
       this->require_c_string(" ");
       std::string package_name = this->read_identifier();
       this->require_c_string(" ");
       std::string init_name = this->read_identifier();
-      this->require_c_string(" ");
-      std::string prio_string = this->read_identifier();
-      int prio;
-      if (!this->string_to_int(prio_string, false, &prio))
-	return;
-      gogo->add_import_init_fn(package_name, init_name, prio);
+      if (this->version_ == EXPORT_FORMAT_V1)
+        {
+          // Older version 1 init fcn export data format is:
+          //
+          //   <packname> <fcn> <priority>
+          this->require_c_string(" ");
+          std::string prio_string = this->read_identifier();
+          if (!this->string_to_int(prio_string, false, &priority))
+            return;
+        }
+      gogo->add_import_init_fn(package_name, init_name, priority);
+
+      // Record the index of this init fcn so that we can look it
+      // up by index in the subsequent init_graph section.
+      unsigned idx = init_idx.size();
+      init_idx[init_name] = idx;
     }
   this->require_c_string(";\n");
+
+  if (this->match_c_string("init_graph"))
+    {
+      this->require_c_string("init_graph");
+
+      // Build a vector mapping init fcn slot to Import_init pointer.
+      go_assert(init_idx.size() > 0);
+      std::vector<Import_init*> import_initvec;
+      import_initvec.resize(init_idx.size());
+      for (std::map<std::string, unsigned>::const_iterator it =
+               init_idx.begin();
+           it != init_idx.end(); ++it)
+	{
+	  const std::string& init_name = it->first;
+	  Import_init* ii = gogo->lookup_init(init_name);
+	  import_initvec[it->second] = ii;
+	}
+
+      // Init graph format is:
+      //
+      //    init_graph <src1> <sink1> <src2> <sink2> ... ;
+      //
+      // where src + sink are init functions indices.
+
+      while (!this->match_c_string(";"))
+	{
+	  this->require_c_string(" ");
+	  std::string src_string = this->read_identifier();
+	  unsigned src;
+	  if (!this->string_to_unsigned(src_string, &src)) return;
+
+	  this->require_c_string(" ");
+	  std::string sink_string = this->read_identifier();
+	  unsigned sink;
+	  if (!this->string_to_unsigned(sink_string, &sink)) return;
+
+	  go_assert(src < import_initvec.size());
+	  Import_init* ii_src = import_initvec[src];
+	  go_assert(sink < import_initvec.size());
+	  Import_init* ii_sink = import_initvec[sink];
+
+	  ii_src->record_precursor_fcn(ii_sink->init_name());
+	}
+      this->require_c_string(";\n");
+    }
 }
 
 // Import a constant.
diff --git a/gcc/go/gofrontend/import.h b/gcc/go/gofrontend/import.h
index 9dbdaf7..aab4b89 100644
--- a/gcc/go/gofrontend/import.h
+++ b/gcc/go/gofrontend/import.h
@@ -232,7 +232,7 @@ class Import
   void
   read_one_import();
 
-  // Read the import control functions.
+  // Read the import control functions and init graph.
   void
   read_import_init_fns(Gogo*);
 
@@ -260,6 +260,21 @@ class Import
   bool
   string_to_int(const std::string&, bool is_neg_ok, int* ret);
 
+  // Get an unsigned integer from a string.
+  bool
+  string_to_unsigned(const std::string& s, unsigned* ret)
+  {
+    int ivalue;
+    if (!this->string_to_int(s, false, &ivalue))
+      return false;
+    *ret = static_cast<unsigned>(ivalue);
+    return true;
+  }
+
+  // Return the version number of the export data we're reading.
+  Export_data_version
+  version() const { return this->version_; }
+
   // The general IR.
   Gogo* gogo_;
   // The stream from which to read import data.
@@ -275,6 +290,8 @@ class Import
   std::vector<Named_type*> builtin_types_;
   // Mapping from exported type codes to Type structures.
   std::vector<Type*> types_;
+  // Version of export data we're reading.
+  Export_data_version version_;
 };
 
 // Read import data from a string.