Go patch committed: Add flattening pass

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

This patch from Chris Manghane adds a flattening pass to the Go
frontend.  This is a step toward moving more types of expressions into
the backend interface.  Bootstrapped and ran Go testsuite on
x86_64-unknown-linux-gnu.  Committed to mainline.

Ian

diff -r 447683c37ddf go/expressions.h
--- a/go/expressions.h	Thu Jan 09 15:16:28 2014 -0800
+++ b/go/expressions.h	Thu Jan 09 15:18:09 2014 -0800
@@ -575,6 +575,18 @@
 	int iota_value)
   { return this->do_lower(gogo, function, inserter, iota_value); }
 
+  // Flatten an expression. This is called after order_evaluation.
+  // FUNCTION is the function we are in; it will be NULL for an
+  // expression initializing a global variable.  INSERTER may be used
+  // to insert statements before the statement or initializer
+  // containing this expression; it is normally used to create
+  // temporary variables. This function must resolve expressions
+  // which could not be fully parsed into their final form.  It
+  // returns the same Expression or a new one.
+  Expression*
+  flatten(Gogo* gogo, Named_object* function, Statement_inserter* inserter)
+  { return this->do_flatten(gogo, function, inserter); }
+
   // Determine the real type of an expression with abstract integer,
   // floating point, or complex type.  TYPE_CONTEXT describes the
   // expected type.
@@ -698,6 +710,12 @@
   do_lower(Gogo*, Named_object*, Statement_inserter*, int)
   { return this; }
 
+  // Return a flattened expression.
+  virtual Expression*
+  do_flatten(Gogo*, Named_object*, Statement_inserter*)
+  { return this; }
+
+
   // Return whether this is a constant expression.
   virtual bool
   do_is_constant() const
diff -r 447683c37ddf go/go.cc
--- a/go/go.cc	Thu Jan 09 15:16:28 2014 -0800
+++ b/go/go.cc	Thu Jan 09 15:18:09 2014 -0800
@@ -119,12 +119,15 @@
   // Use temporary variables to force order of evaluation.
   ::gogo->order_evaluations();
 
+  // Flatten the parse tree.
+  ::gogo->flatten();
+
   // Build thunks for functions which call recover.
   ::gogo->build_recover_thunks();
 
   // Convert complicated go and defer statements into simpler ones.
   ::gogo->simplify_thunk_statements();
-  
+
   // Dump ast, use filename[0] as the base name
   ::gogo->dump_ast(filenames[0]);
 }
diff -r 447683c37ddf go/gogo.cc
--- a/go/gogo.cc	Thu Jan 09 15:16:28 2014 -0800
+++ b/go/gogo.cc	Thu Jan 09 15:18:09 2014 -0800
@@ -2703,6 +2703,169 @@
   this->traverse(&order_eval);
 }
 
+// Traversal to flatten parse tree after order of evaluation rules are applied.
+
+class Flatten : public Traverse
+{
+ public:
+  Flatten(Gogo* gogo, Named_object* function)
+    : Traverse(traverse_variables
+	       | traverse_functions
+	       | traverse_statements
+	       | traverse_expressions),
+      gogo_(gogo), function_(function), inserter_()
+  { }
+
+  void
+  set_inserter(const Statement_inserter* inserter)
+  { this->inserter_ = *inserter; }
+
+  int
+  variable(Named_object*);
+
+  int
+  function(Named_object*);
+
+  int
+  statement(Block*, size_t* pindex, Statement*);
+
+  int
+  expression(Expression**);
+
+ private:
+  // General IR.
+  Gogo* gogo_;
+  // The function we are traversing.
+  Named_object* function_;
+  // Current statement inserter for use by expressions.
+  Statement_inserter inserter_;
+};
+
+// Flatten variables.
+
+int
+Flatten::variable(Named_object* no)
+{
+  if (!no->is_variable())
+    return TRAVERSE_CONTINUE;
+
+  if (no->is_variable() && no->var_value()->is_global())
+    {
+      // Global variables can have loops in their initialization
+      // expressions.  This is handled in flatten_init_expression.
+      no->var_value()->flatten_init_expression(this->gogo_, this->function_,
+                                               &this->inserter_);
+      return TRAVERSE_CONTINUE;
+    }
+
+  go_assert(!no->var_value()->has_pre_init());
+
+  return TRAVERSE_SKIP_COMPONENTS;
+}
+
+// Flatten the body of a function.  Record the function while flattening it,
+// so that we can pass it down when flattening an expression.
+
+int
+Flatten::function(Named_object* no)
+{
+  go_assert(this->function_ == NULL);
+  this->function_ = no;
+  int t = no->func_value()->traverse(this);
+  this->function_ = NULL;
+
+  if (t == TRAVERSE_EXIT)
+    return t;
+  return TRAVERSE_SKIP_COMPONENTS;
+}
+
+// Flatten statement parse trees.
+
+int
+Flatten::statement(Block* block, size_t* pindex, Statement* sorig)
+{
+  // Because we explicitly traverse the statement's contents
+  // ourselves, we want to skip block statements here.  There is
+  // nothing to flatten in a block statement.
+  if (sorig->is_block_statement())
+    return TRAVERSE_CONTINUE;
+
+  Statement_inserter hold_inserter(this->inserter_);
+  this->inserter_ = Statement_inserter(block, pindex);
+
+  // Flatten the expressions first.
+  int t = sorig->traverse_contents(this);
+  if (t == TRAVERSE_EXIT)
+    {
+      this->inserter_ = hold_inserter;
+      return t;
+    }
+
+  // Keep flattening until nothing changes.
+  Statement* s = sorig;
+  while (true)
+    {
+      Statement* snew = s->flatten(this->gogo_, this->function_, block,
+                                   &this->inserter_);
+      if (snew == s)
+	break;
+      s = snew;
+      t = s->traverse_contents(this);
+      if (t == TRAVERSE_EXIT)
+	{
+	  this->inserter_ = hold_inserter;
+	  return t;
+	}
+    }
+
+  if (s != sorig)
+    block->replace_statement(*pindex, s);
+
+  this->inserter_ = hold_inserter;
+  return TRAVERSE_SKIP_COMPONENTS;
+}
+
+// Flatten expression parse trees.
+
+int
+Flatten::expression(Expression** pexpr)
+{
+  // Keep flattening until nothing changes.
+  while (true)
+    {
+      Expression* e = *pexpr;
+      if (e->traverse_subexpressions(this) == TRAVERSE_EXIT)
+        return TRAVERSE_EXIT;
+
+      Expression* enew = e->flatten(this->gogo_, this->function_,
+                                    &this->inserter_);
+      if (enew == e)
+	break;
+      *pexpr = enew;
+    }
+  return TRAVERSE_SKIP_COMPONENTS;
+}
+
+// Flatten an expression.  INSERTER may be NULL, in which case the
+// expression had better not need to create any temporaries.
+
+void
+Gogo::flatten_expression(Named_object* function, Statement_inserter* inserter,
+                         Expression** pexpr)
+{
+  Flatten flatten(this, function);
+  if (inserter != NULL)
+    flatten.set_inserter(inserter);
+  flatten.expression(pexpr);
+}
+
+void
+Gogo::flatten()
+{
+  Flatten flatten(this, NULL);
+  this->traverse(&flatten);
+}
+
 // Traversal to convert calls to the predeclared recover function to
 // pass in an argument indicating whether it can recover from a panic
 // or not.
@@ -4286,10 +4449,11 @@
     backend_(NULL), is_global_(is_global), is_parameter_(is_parameter),
     is_receiver_(is_receiver), is_varargs_parameter_(false), is_used_(false),
     is_address_taken_(false), is_non_escaping_address_taken_(false),
-    seen_(false), init_is_lowered_(false), type_from_init_tuple_(false),
-    type_from_range_index_(false), type_from_range_value_(false),
-    type_from_chan_element_(false), is_type_switch_var_(false),
-    determined_type_(false), in_unique_section_(false)
+    seen_(false), init_is_lowered_(false), init_is_flattened_(false),
+    type_from_init_tuple_(false), type_from_range_index_(false),
+    type_from_range_value_(false), type_from_chan_element_(false),
+    is_type_switch_var_(false), determined_type_(false),
+    in_unique_section_(false)
 {
   go_assert(type != NULL || init != NULL);
   go_assert(!is_parameter || init == NULL);
@@ -4351,6 +4515,40 @@
     }
 }
 
+// Flatten the initialization expression after ordering evaluations.
+
+void
+Variable::flatten_init_expression(Gogo* gogo, Named_object* function,
+                                  Statement_inserter* inserter)
+{
+  Named_object* dep = gogo->var_depends_on(this);
+  if (dep != NULL && dep->is_variable())
+    dep->var_value()->flatten_init_expression(gogo, function, inserter);
+
+  if (this->init_ != NULL && !this->init_is_flattened_)
+    {
+      if (this->seen_)
+	{
+	  // We will give an error elsewhere, this is just to prevent
+	  // an infinite loop.
+	  return;
+	}
+      this->seen_ = true;
+
+      Statement_inserter global_inserter;
+      if (this->is_global_)
+	{
+	  global_inserter = Statement_inserter(gogo, this);
+	  inserter = &global_inserter;
+	}
+
+      gogo->flatten_expression(function, inserter, &this->init_);
+
+      this->seen_ = false;
+      this->init_is_flattened_ = true;
+    }
+}
+
 // Get the preinit block.
 
 Block*
diff -r 447683c37ddf go/gogo.h
--- a/go/gogo.h	Thu Jan 09 15:16:28 2014 -0800
+++ b/go/gogo.h	Thu Jan 09 15:18:09 2014 -0800
@@ -487,6 +487,10 @@
   void
   lower_constant(Named_object*);
 
+  // Flatten an expression.
+  void
+  flatten_expression(Named_object* function, Statement_inserter*, Expression**);
+
   // Create all necessary function descriptors.
   void
   create_function_descriptors();
@@ -531,6 +535,10 @@
   void
   order_evaluations();
 
+  // Flatten parse tree.
+  void
+  flatten();
+
   // Build thunks for functions which call recover.
   void
   build_recover_thunks();
@@ -1447,6 +1455,10 @@
   void
   lower_init_expression(Gogo*, Named_object*, Statement_inserter*);
 
+  // Flatten the initialization expression after ordering evaluations.
+  void
+  flatten_init_expression(Gogo*, Named_object*, Statement_inserter*);
+
   // A special case: the init value is used only to determine the
   // type.  This is used if the variable is defined using := with the
   // comma-ok form of a map index or a receive expression.  The init
@@ -1580,6 +1592,8 @@
   bool seen_ : 1;
   // True if we have lowered the initialization expression.
   bool init_is_lowered_ : 1;
+  // True if we have flattened the initialization expression.
+  bool init_is_flattened_ : 1;
   // True if init is a tuple used to set the type.
   bool type_from_init_tuple_ : 1;
   // True if init is a range clause and the type is the index type.
diff -r 447683c37ddf go/statements.cc
--- a/go/statements.cc	Thu Jan 09 15:16:28 2014 -0800
+++ b/go/statements.cc	Thu Jan 09 15:18:09 2014 -0800
@@ -246,6 +246,16 @@
   return this;
 }
 
+// Flatten the variable's initialization expression.
+
+Statement*
+Variable_declaration_statement::do_flatten(Gogo* gogo, Named_object* function,
+                                           Block*, Statement_inserter* inserter)
+{
+  this->var_->var_value()->flatten_init_expression(gogo, function, inserter);
+  return this;
+}
+
 // Convert a variable declaration to the backend representation.
 
 Bstatement*
diff -r 447683c37ddf go/statements.h
--- a/go/statements.h	Thu Jan 09 15:16:28 2014 -0800
+++ b/go/statements.h	Thu Jan 09 15:18:09 2014 -0800
@@ -306,6 +306,16 @@
 	Statement_inserter* inserter)
   { return this->do_lower(gogo, function, block, inserter); }
 
+  // Flatten a statement.  This is called immediately after the order of
+  // evaluation rules are applied to statements.  It returns the same
+  // Statement or a new one.  FUNCTION is the function containing this
+  // statement.  BLOCK is the block containing this statement.
+  // INSERTER can be used to insert new statements before this one.
+  Statement*
+  flatten(Gogo* gogo, Named_object* function, Block* block,
+          Statement_inserter* inserter)
+  { return this->do_flatten(gogo, function, block, inserter); }
+
   // Set type information for unnamed constants.
   void
   determine_types();
@@ -412,6 +422,12 @@
   do_lower(Gogo*, Named_object*, Block*, Statement_inserter*)
   { return this; }
 
+  // Implemented by the child class: lower this statement to a simpler
+  // one.
+  virtual Statement*
+  do_flatten(Gogo*, Named_object*, Block*, Statement_inserter*)
+  { return this; }
+
   // Implemented by child class: set type information for unnamed
   // constants.  Any statement which includes an expression needs to
   // implement this.
@@ -583,6 +599,9 @@
   Statement*
   do_lower(Gogo*, Named_object*, Block*, Statement_inserter*);
 
+  Statement*
+  do_flatten(Gogo*, Named_object*, Block*, Statement_inserter*);
+
   Bstatement*
   do_get_backend(Translate_context*);