gccgo patch committed: Fix initialization order bug

[Ian Lance Taylor <iant at google dot com>]

This patch to the Go frontend fixes a bug determining the initialization
order.  I've committed a test case for the bug to the master Go
repository:

https://code.google.com/p/go/source/detail?spec=svn921e53d4863c8827756c0e7b228ab210441e4032&r=c3155f9f1bb64c8b3adb2b6f5527895d51f83b74

The old algorithm was overly clever and frankly I don't know what I was
thinking.  The new algorithm is simpler and probably more efficient.
Bootstrapped and ran Go testsuite on x86_64-unknown-linux-gnu.
Committed to mainline.

Ian

diff -r ee18ff1199b6 go/expressions.h
--- a/go/expressions.h	Fri Jan 25 16:13:13 2013 -0800
+++ b/go/expressions.h	Mon Jan 28 16:23:26 2013 -0800
@@ -983,6 +983,11 @@
       statement_(statement), is_lvalue_(false)
   { }
 
+  // The temporary that this expression refers to.
+  Temporary_statement*
+  statement() const
+  { return this->statement_; }
+
   // Indicate that this reference appears on the left hand side of an
   // assignment statement.
   void
diff -r ee18ff1199b6 go/gogo-tree.cc
--- a/go/gogo-tree.cc	Fri Jan 25 16:13:13 2013 -0800
+++ b/go/gogo-tree.cc	Mon Jan 28 16:23:26 2013 -0800
@@ -499,7 +499,7 @@
   // A hash table we use to avoid looping.  The index is the name of a
   // named object.  We only look through objects defined in this
   // package.
-  typedef Unordered_set(std::string) Seen_objects;
+  typedef Unordered_set(const void*) Seen_objects;
 
   Find_var(Named_object* var, Seen_objects* seen_objects)
     : Traverse(traverse_expressions),
@@ -547,7 +547,7 @@
 	  if (init != NULL)
 	    {
 	      std::pair<Seen_objects::iterator, bool> ins =
-		this->seen_objects_->insert(v->name());
+		this->seen_objects_->insert(v);
 	      if (ins.second)
 		{
 		  // This is the first time we have seen this name.
@@ -568,7 +568,7 @@
       if (f->is_function() && f->package() == NULL)
 	{
 	  std::pair<Seen_objects::iterator, bool> ins =
-	    this->seen_objects_->insert(f->name());
+	    this->seen_objects_->insert(f);
 	  if (ins.second)
 	    {
 	      // This is the first time we have seen this name.
@@ -578,6 +578,25 @@
 	}
     }
 
+  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;
 }
 
@@ -613,11 +632,11 @@
 {
  public:
   Var_init()
-    : var_(NULL), init_(NULL_TREE), waiting_(0)
+    : var_(NULL), init_(NULL_TREE)
   { }
 
   Var_init(Named_object* var, tree init)
-    : var_(var), init_(init), waiting_(0)
+    : var_(var), init_(init)
   { }
 
   // Return the variable.
@@ -630,24 +649,11 @@
   init() const
   { return this->init_; }
 
-  // Return the number of variables waiting for this one to be
-  // initialized.
-  size_t
-  waiting() const
-  { return this->waiting_; }
-
-  // Increment the number waiting.
-  void
-  increment_waiting()
-  { ++this->waiting_; }
-
  private:
   // The variable being initialized.
   Named_object* var_;
   // The initialization expression to run.
   tree init_;
-  // The number of variables which are waiting for this one.
-  size_t waiting_;
 };
 
 typedef std::list<Var_init> Var_inits;
@@ -660,6 +666,10 @@
 static void
 sort_var_inits(Gogo* gogo, Var_inits* var_inits)
 {
+  typedef std::pair<Named_object*, Named_object*> No_no;
+  typedef std::map<No_no, bool> Cache;
+  Cache cache;
+
   Var_inits ready;
   while (!var_inits->empty())
     {
@@ -670,23 +680,30 @@
       Named_object* dep = gogo->var_depends_on(var->var_value());
 
       // Start walking through the list to see which variables VAR
-      // needs to wait for.  We can skip P1->WAITING variables--that
-      // is the number we've already checked.
+      // needs to wait for.
       Var_inits::iterator p2 = p1;
       ++p2;
-      for (size_t i = p1->waiting(); i > 0; --i)
-	++p2;
 
       for (; p2 != var_inits->end(); ++p2)
 	{
 	  Named_object* p2var = p2->var();
-	  if (expression_requires(init, preinit, dep, p2var))
+	  No_no key(var, p2var);
+	  std::pair<Cache::iterator, bool> ins =
+	    cache.insert(std::make_pair(key, false));
+	  if (ins.second)
+	    ins.first->second = expression_requires(init, preinit, dep, p2var);
+	  if (ins.first->second)
 	    {
 	      // Check for cycles.
-	      if (expression_requires(p2var->var_value()->init(),
+	      key = std::make_pair(p2var, var);
+	      ins = cache.insert(std::make_pair(key, false));
+	      if (ins.second)
+		ins.first->second =
+		  expression_requires(p2var->var_value()->init(),
 				      p2var->var_value()->preinit(),
 				      gogo->var_depends_on(p2var->var_value()),
-				      var))
+				      var);
+	      if (ins.first->second)
 		{
 		  error_at(var->location(),
 			   ("initialization expressions for %qs and "
@@ -700,12 +717,8 @@
 	      else
 		{
 		  // We can't emit P1 until P2 is emitted.  Move P1.
-		  // Note that the WAITING loop always executes at
-		  // least once, which is what we want.
-		  p2->increment_waiting();
 		  Var_inits::iterator p3 = p2;
-		  for (size_t i = p2->waiting(); i > 0; --i)
-		    ++p3;
+		  ++p3;
 		  var_inits->splice(p3, *var_inits, p1);
 		}
 	      break;
diff -r ee18ff1199b6 go/statements.h
--- a/go/statements.h	Fri Jan 25 16:13:13 2013 -0800
+++ b/go/statements.h	Mon Jan 28 16:23:26 2013 -0800
@@ -490,6 +490,11 @@
   Type*
   type() const;
 
+  // Return the initializer if there is one.
+  Expression*
+  init() const
+  { return this->init_; }
+
   // Note that it is OK for this statement to set hidden fields.
   void
   set_hidden_fields_are_ok()