compiler: initial support for exporting function bodies

Create a framework for putting function bodies in export data.  At
present only empty functions will be put there, and they will be
ignored on import.  Later patches will get this to the point of
supporting inlining of (some) functions defined in other packages.

Change-Id: Iab6d0d59f36b9f909a86e649aa79a4d8c068a9c9
Reviewed-on: https://go-review.googlesource.com/c/150061
Reviewed-by: Cherry Zhang <cherryyz@google.com>
Reviewed-by: Than McIntosh <thanm@google.com>
diff --git a/go/export.h b/go/export.h
index 84077a2..5751488 100644
--- a/go/export.h
+++ b/go/export.h
@@ -286,4 +286,60 @@
   std::string string_;
 };
 
+// Class to manage exporting a function body.  This is passed around
+// to Statements and Expressions.  It builds up the export data for
+// the function.
+
+class Export_function_body
+{
+ public:
+  Export_function_body(int indent)
+    : indent_(indent)
+  { }
+
+  // Write a character to the body.
+  void
+  write_char(char c)
+  { this->body_.append(1, c); }
+
+  // Write a NUL terminated string to the body.
+  void
+  write_c_string(const char* str)
+  { this->body_.append(str); }
+
+  // Write a string to the body.
+  void
+  write_string(const std::string& str)
+  { this->body_.append(str); }
+
+  // Append as many spaces as the current indentation level.
+  void
+  indent()
+  {
+    for (int i = this->indent_; i > 0; i--)
+      this->write_char(' ');
+  }
+
+  // Increment the indentation level.
+  void
+  increment_indent()
+  { ++this->indent_; }
+
+  // Decrement the indentation level.
+  void
+  decrement_indent()
+  { --this->indent_; }
+
+  // Return a reference to the completed body.
+  const std::string&
+  body() const
+  { return this->body_; }
+
+ private:
+  // The body we are building.
+  std::string body_;
+  // Current indentation level: the number of spaces before each statement.
+  int indent_;
+};
+
 #endif // !defined(GO_EXPORT_H)
diff --git a/go/expressions.h b/go/expressions.h
index f53cc6e..33ea9b2 100644
--- a/go/expressions.h
+++ b/go/expressions.h
@@ -939,6 +939,11 @@
   copy()
   { return this->do_copy(); }
 
+  // Return the cost of this statement for inlining purposes.
+  int
+  inlining_cost()
+  { return this->do_inlining_cost(); }
+
   // Return whether the expression is addressable--something which may
   // be used as the operand of the unary & operator.
   bool
@@ -1084,6 +1089,13 @@
   virtual Expression*
   do_copy() = 0;
 
+  // Child class implements determining the cost of this statement for
+  // inlining.  The default cost is high, so we only need to define
+  // this method for expressions that can be inlined.
+  virtual int
+  do_inlining_cost()
+  { return 0x100000; }
+
   // Child class implements whether the expression is addressable.
   virtual bool
   do_is_addressable() const
diff --git a/go/gogo.cc b/go/gogo.cc
index 6ea247a..354eaba 100644
--- a/go/gogo.cc
+++ b/go/gogo.cc
@@ -4691,11 +4691,130 @@
   this->traverse(&traverse);
 }
 
+// Traversal class to decide whether a function body is less than the
+// inlining budget.  This adjusts *available as it goes, and stops the
+// traversal if it goes negative.
+
+class Inline_within_budget : public Traverse
+{
+ public:
+  Inline_within_budget(int* available)
+    : Traverse(traverse_statements
+	       | traverse_expressions),
+      available_(available)
+  { }
+
+  int
+  statement(Block*, size_t*, Statement*);
+
+  int
+  expression(Expression**);
+
+ private:
+  // Pointer to remaining budget.
+  int* available_;
+};
+
+// Adjust the budget for the inlining cost of a statement.
+
+int
+Inline_within_budget::statement(Block*, size_t*, Statement* s)
+{
+  if (*this->available_ < 0)
+    return TRAVERSE_EXIT;
+  *this->available_ -= s->inlining_cost();
+  return TRAVERSE_CONTINUE;
+}
+
+// Adjust the budget for the inlining cost of an expression.
+
+int
+Inline_within_budget::expression(Expression** pexpr)
+{
+  if (*this->available_ < 0)
+    return TRAVERSE_EXIT;
+  *this->available_ -= (*pexpr)->inlining_cost();
+  return TRAVERSE_CONTINUE;
+}
+
+// Traversal class to find functions whose body should be exported for
+// inlining by other packages.
+
+class Mark_inline_candidates : public Traverse
+{
+ public:
+  Mark_inline_candidates()
+    : Traverse(traverse_functions
+	       | traverse_types)
+  { }
+
+  int
+  function(Named_object*);
+
+  int
+  type(Type*);
+
+ private:
+  // We traverse the function body trying to determine how expensive
+  // it is for inlining.  We start with a budget, and decrease that
+  // budget for each statement and expression.  If the budget goes
+  // negative, we do not export the function body.  The value of this
+  // budget is a heuristic.  In the usual GCC spirit, we could
+  // consider setting this via a command line option.
+  const int budget_heuristic = 80;
+};
+
+// Mark a function if it is an inline candidate.
+
+int
+Mark_inline_candidates::function(Named_object* no)
+{
+  Function* func = no->func_value();
+  int budget = budget_heuristic;
+  Inline_within_budget iwb(&budget);
+  func->block()->traverse(&iwb);
+  if (budget >= 0)
+    func->set_export_for_inlining();
+  return TRAVERSE_CONTINUE;
+}
+
+// Mark methods if they are inline candidates.
+
+int
+Mark_inline_candidates::type(Type* t)
+{
+  Named_type* nt = t->named_type();
+  if (nt == NULL || nt->is_alias())
+    return TRAVERSE_CONTINUE;
+  const Bindings* methods = nt->local_methods();
+  if (methods == NULL)
+    return TRAVERSE_CONTINUE;
+  for (Bindings::const_definitions_iterator p = methods->begin_definitions();
+       p != methods->end_definitions();
+       ++p)
+    {
+      Named_object* no = *p;
+      go_assert(no->is_function());
+      Function *func = no->func_value();
+      int budget = budget_heuristic;
+      Inline_within_budget iwb(&budget);
+      func->block()->traverse(&iwb);
+      if (budget >= 0)
+	func->set_export_for_inlining();
+    }
+  return TRAVERSE_CONTINUE;
+}
+
 // Export identifiers as requested.
 
 void
 Gogo::do_exports()
 {
+  // Mark any functions whose body should be exported for inlining by
+  // other packages.
+  Mark_inline_candidates mic;
+  this->traverse(&mic);
+
   // For now we always stream to a section.  Later we may want to
   // support streaming to a separate file.
   Stream_to_section stream(this->backend());
@@ -4962,7 +5081,7 @@
     results_are_named_(false), is_unnamed_type_stub_method_(false),
     calls_recover_(false), is_recover_thunk_(false), has_recover_thunk_(false),
     calls_defer_retaddr_(false), is_type_specific_function_(false),
-    in_unique_section_(false)
+    in_unique_section_(false), export_for_inlining_(false)
 {
 }
 
@@ -5316,15 +5435,20 @@
 void
 Function::export_func(Export* exp, const std::string& name) const
 {
+  Block* block = NULL;
+  if (this->export_for_inlining())
+    block = this->block_;
   Function::export_func_with_type(exp, name, this->type_,
-				  this->is_method() && this->nointerface());
+				  this->is_method() && this->nointerface(),
+				  block);
 }
 
 // Export a function with a type.
 
 void
 Function::export_func_with_type(Export* exp, const std::string& name,
-				const Function_type* fntype, bool nointerface)
+				const Function_type* fntype, bool nointerface,
+				Block* block)
 {
   exp->write_c_string("func ");
 
@@ -5404,7 +5528,32 @@
 	  exp->write_c_string(")");
 	}
     }
-  exp->write_c_string("\n");
+
+  if (block == NULL)
+    exp->write_c_string("\n");
+  else
+    {
+      int indent = 1;
+      if (fntype->is_method())
+	indent++;
+
+      Export_function_body efb(indent);
+
+      efb.indent();
+      efb.write_c_string("// ");
+      efb.write_string(Linemap::location_to_file(block->start_location()));
+      efb.write_char('\n');
+      block->export_block(&efb);
+
+      const std::string& body(efb.body());
+
+      char buf[100];
+      snprintf(buf, sizeof buf, " <inl:%lu>\n",
+	       static_cast<unsigned long>(body.length()));
+      exp->write_c_string(buf);
+
+      exp->write_string(body);
+    }
 }
 
 // Import a function.
@@ -5480,7 +5629,7 @@
   *pparameters = parameters;
 
   Typed_identifier_list* results;
-  if (imp->peek_char() != ' ')
+  if (imp->peek_char() != ' ' || imp->match_c_string(" <inl"))
     results = NULL;
   else
     {
@@ -5511,9 +5660,46 @@
 	  imp->require_c_string(")");
 	}
     }
-  imp->require_semicolon_if_old_version();
-  imp->require_c_string("\n");
   *presults = results;
+
+  if (!imp->match_c_string(" <inl:"))
+    {
+      imp->require_semicolon_if_old_version();
+      imp->require_c_string("\n");
+    }
+  else
+    {
+      imp->require_c_string(" <inl:");
+      std::string lenstr;
+      int c;
+      while (true)
+	{
+	  c = imp->peek_char();
+	  if (c < '0' || c > '9')
+	    break;
+	  lenstr += c;
+	  imp->get_char();
+	}
+      imp->require_c_string(">\n");
+
+      errno = 0;
+      char* end;
+      long llen = strtol(lenstr.c_str(), &end, 10);
+      if (*end != '\0'
+	  || llen < 0
+	  || (llen == LONG_MAX && errno == ERANGE))
+	{
+	  go_error_at(imp->location(), "invalid inline function length %s",
+		      lenstr.c_str());
+	  return;
+	}
+
+      imp->read(static_cast<size_t>(llen));
+
+      // Here we should record the body for later parsing if we see a
+      // call to this function.  This is not yet implemented.  For now
+      // we just discard the information.
+    }
 }
 
 // Get the backend representation.
@@ -6234,6 +6420,35 @@
   return this->statements_.back()->may_fall_through();
 }
 
+// Write export data for a block.
+
+void
+Block::export_block(Export_function_body* efb)
+{
+  for (Block::iterator p = this->begin();
+       p != this->end();
+       ++p)
+    {
+      efb->indent();
+
+      efb->increment_indent();
+      (*p)->export_statement(efb);
+      efb->decrement_indent();
+
+      Location loc = (*p)->location();
+      if ((*p)->is_block_statement())
+	{
+	  // For a block we put the start location on the first brace
+	  // in Block_statement::do_export_statement.  Here we put the
+	  // end location on the final brace.
+	  loc = (*p)->block_statement()->block()->end_location();
+	}
+      char buf[50];
+      snprintf(buf, sizeof buf, " //%d\n", Linemap::location_to_line(loc));
+      efb->write_c_string(buf);
+    }
+}
+
 // Convert a block to the backend representation.
 
 Bblock*
diff --git a/go/gogo.h b/go/gogo.h
index 48359eb..1b13e5c 100644
--- a/go/gogo.h
+++ b/go/gogo.h
@@ -41,6 +41,7 @@
 class Translate_context;
 class Backend;
 class Export;
+class Export_function_body;
 class Import;
 class Bexpression;
 class Btype;
@@ -1139,6 +1140,10 @@
   bool
   may_fall_through() const;
 
+  // Write the export data for the block's statements to the string.
+  void
+  export_block(Export_function_body*);
+
   // Convert the block to the backend representation.
   Bblock*
   get_backend(Translate_context*);
@@ -1404,6 +1409,16 @@
   set_in_unique_section()
   { this->in_unique_section_ = true; }
 
+  // Return whether this function should be exported for inlining.
+  bool
+  export_for_inlining() const
+  { return this->export_for_inlining_; }
+
+  // Mark the function to be exported for inlining.
+  void
+  set_export_for_inlining()
+  { this->export_for_inlining_ = true; }
+
   // Swap with another function.  Used only for the thunk which calls
   // recover.
   void
@@ -1461,7 +1476,7 @@
   // Export a function with a type.
   static void
   export_func_with_type(Export*, const std::string& name,
-			const Function_type*, bool nointerface);
+			const Function_type*, bool nointerface, Block* block);
 
   // Import a function.
   static void
@@ -1539,6 +1554,9 @@
   // True if this function should be put in a unique section.  This is
   // turned on for field tracking.
   bool in_unique_section_ : 1;
+  // True if we should export the body of this function for
+  // cross-package inlining.
+  bool export_for_inlining_ : 1;
 };
 
 // A snapshot of the current binding state.
@@ -1654,7 +1672,8 @@
   export_func(Export* exp, const std::string& name) const
   {
     Function::export_func_with_type(exp, name, this->fntype_,
-				    this->is_method() && this->nointerface());
+				    this->is_method() && this->nointerface(),
+				    NULL);
   }
 
   // Check that the types used in this declaration's signature are defined.
diff --git a/go/import.cc b/go/import.cc
index d30068f..a0a1f18 100644
--- a/go/import.cc
+++ b/go/import.cc
@@ -1230,6 +1230,24 @@
   return ret;
 }
 
+// Read LENGTH bytes from the stream.
+
+std::string
+Import::read(size_t length)
+{
+  const char* data;
+  if (!this->stream_->peek(length, &data))
+    {
+      if (!this->stream_->saw_error())
+	go_error_at(this->location_, "import error at %d: expected %d bytes",
+		    this->stream_->pos(), static_cast<int>(length));
+      this->stream_->set_saw_error();
+      return "";
+    }
+  this->advance(length);
+  return std::string(data, length);
+}
+
 // Turn a string into a integer with appropriate error handling.
 
 bool
diff --git a/go/import.h b/go/import.h
index cc7703b..9c6cbfe 100644
--- a/go/import.h
+++ b/go/import.h
@@ -169,6 +169,11 @@
   get_char()
   { return this->stream_->get_char(); }
 
+  // Read LENGTH characters into a string and advance past them.  On
+  // EOF reports an error and returns an empty string.
+  std::string
+  read(size_t length);
+
   // Return true at the end of the stream.
   bool
   at_eof()
diff --git a/go/statements.cc b/go/statements.cc
index c35002d..718139c 100644
--- a/go/statements.cc
+++ b/go/statements.cc
@@ -11,6 +11,7 @@
 #include "types.h"
 #include "expressions.h"
 #include "gogo.h"
+#include "export.h"
 #include "runtime.h"
 #include "backend.h"
 #include "statements.h"
@@ -1781,6 +1782,27 @@
   return new Expression_statement(expr, is_ignored);
 }
 
+// Export data for a block.
+
+void
+Block_statement::do_export_statement(Export_function_body* efb)
+{
+  // We are already indented to the right position.
+  char buf[50];
+  snprintf(buf, sizeof buf, "{ //%d\n",
+	   Linemap::location_to_line(this->block_->start_location()));
+  efb->write_c_string(buf);
+
+  this->block_->export_block(efb);
+  // The indentation is correct for the statements in the block, so
+  // subtract one for the closing curly brace.
+  efb->decrement_indent();
+  efb->indent();
+  efb->write_c_string("}");
+  // Increment back to the value the caller thinks it has.
+  efb->increment_indent();
+}
+
 // Convert a block to the backend representation of a statement.
 
 Bstatement*
diff --git a/go/statements.h b/go/statements.h
index 81b26b3..ff57a21 100644
--- a/go/statements.h
+++ b/go/statements.h
@@ -15,6 +15,7 @@
 class Block;
 class Function;
 class Unnamed_label;
+class Export_function_body;
 class Assignment_statement;
 class Temporary_statement;
 class Variable_declaration_statement;
@@ -326,6 +327,17 @@
   check_types(Gogo* gogo)
   { this->do_check_types(gogo); }
 
+  // Return the cost of this statement for inlining purposes.
+  int
+  inlining_cost()
+  { return this->do_inlining_cost(); }
+
+  // Export data for this statement to BODY.  INDENT is an indentation
+  // level used if the export data requires multiple lines.
+  void
+  export_statement(Export_function_body* efb)
+  { this->do_export_statement(efb); }
+
   // Return whether this is a block statement.
   bool
   is_block_statement() const
@@ -488,6 +500,22 @@
   do_check_types(Gogo*)
   { }
 
+  // Implemented by child class: return the cost of this statement for
+  // inlining.  The default cost is high, so we only need to define
+  // this method for statements that can be inlined.
+  virtual int
+  do_inlining_cost()
+  { return 0x100000; }
+
+  // Implemented by child class: write export data for this statement
+  // to the string.  The integer is an indentation level used if the
+  // export data requires multiple lines.  This need only be
+  // implemented by classes that implement do_inlining_cost with a
+  // reasonable value.
+  virtual void
+  do_export_statement(Export_function_body*)
+  { go_unreachable(); }
+
   // Implemented by child class: return true if this statement may
   // fall through.
   virtual bool
@@ -819,6 +847,11 @@
       block_(block), is_lowered_for_statement_(false)
   { }
 
+  // Return the actual block.
+  Block*
+  block() const
+  { return this->block_; }
+
   void
   set_is_lowered_for_statement()
   { this->is_lowered_for_statement_ = true; }
@@ -836,6 +869,13 @@
   do_determine_types()
   { this->block_->determine_types(); }
 
+  int
+  do_inlining_cost()
+  { return 0; }
+
+  void
+  do_export_statement(Export_function_body*);
+
   bool
   do_may_fall_through() const
   { return this->block_->may_fall_through(); }
diff --git a/libgo/go/go/internal/gccgoimporter/parser.go b/libgo/go/go/internal/gccgoimporter/parser.go
index dc61e4c..c23002f 100644
--- a/libgo/go/go/internal/gccgoimporter/parser.go
+++ b/libgo/go/go/internal/gccgoimporter/parser.go
@@ -15,6 +15,7 @@
 	"strconv"
 	"strings"
 	"text/scanner"
+	"unicode/utf8"
 )
 
 type parser struct {
@@ -41,7 +42,7 @@
 func (p *parser) initScanner(filename string, src io.Reader) {
 	p.scanner.Init(src)
 	p.scanner.Error = func(_ *scanner.Scanner, msg string) { p.error(msg) }
-	p.scanner.Mode = scanner.ScanIdents | scanner.ScanInts | scanner.ScanFloats | scanner.ScanStrings | scanner.ScanComments | scanner.SkipComments
+	p.scanner.Mode = scanner.ScanIdents | scanner.ScanInts | scanner.ScanFloats | scanner.ScanStrings
 	p.scanner.Whitespace = 1<<'\t' | 1<<' '
 	p.scanner.Filename = filename // for good error messages
 	p.next()
@@ -393,7 +394,7 @@
 
 // NamedType = TypeName [ "=" ] Type { Method } .
 // TypeName  = ExportedName .
-// Method    = "func" "(" Param ")" Name ParamList ResultList ";" .
+// Method    = "func" "(" Param ")" Name ParamList ResultList [InlineBody] ";" .
 func (p *parser) parseNamedType(n int) types.Type {
 	pkg, name := p.parseExportedName()
 	scope := pkg.Scope()
@@ -455,6 +456,7 @@
 			name := p.parseName()
 			params, isVariadic := p.parseParamList(pkg)
 			results := p.parseResultList(pkg)
+			p.skipInlineBody()
 			p.expectEOL()
 
 			sig := types.NewSignature(receiver, params, results, isVariadic)
@@ -566,7 +568,11 @@
 func (p *parser) parseResultList(pkg *types.Package) *types.Tuple {
 	switch p.tok {
 	case '<':
-		return types.NewTuple(types.NewParam(token.NoPos, pkg, "", p.parseType(pkg)))
+		p.next()
+		if p.tok == scanner.Ident && p.lit == "inl" {
+			return nil
+		}
+		return types.NewTuple(types.NewParam(token.NoPos, pkg, "", p.parseTypeAfterAngle(pkg)))
 
 	case '(':
 		params, _ := p.parseParamList(pkg)
@@ -584,7 +590,7 @@
 	return types.NewSignature(nil, params, results, isVariadic)
 }
 
-// Func = Name FunctionType .
+// Func = Name FunctionType [InlineBody] .
 func (p *parser) parseFunc(pkg *types.Package) *types.Func {
 	name := p.parseName()
 	if strings.ContainsRune(name, '$') {
@@ -593,7 +599,9 @@
 		p.discardDirectiveWhileParsingTypes(pkg)
 		return nil
 	}
-	return types.NewFunc(token.NoPos, pkg, name, p.parseFunctionType(pkg))
+	f := types.NewFunc(token.NoPos, pkg, name, p.parseFunctionType(pkg))
+	p.skipInlineBody()
+	return f
 }
 
 // InterfaceType = "interface" "{" { ("?" Type | Func) ";" } "}" .
@@ -717,8 +725,13 @@
 }
 
 // Type = "<" "type" ( "-" int | int [ TypeDefinition ] ) ">" .
-func (p *parser) parseType(pkg *types.Package) (t types.Type) {
+func (p *parser) parseType(pkg *types.Package) types.Type {
 	p.expect('<')
+	return p.parseTypeAfterAngle(pkg)
+}
+
+// (*parser).Type after reading the "<".
+func (p *parser) parseTypeAfterAngle(pkg *types.Package) (t types.Type) {
 	p.expectKeyword("type")
 
 	switch p.tok {
@@ -748,6 +761,39 @@
 	return
 }
 
+// InlineBody = "<inl:NN>" .{NN}
+// Reports whether a body was skipped.
+func (p *parser) skipInlineBody() {
+	// We may or may not have seen the '<' already, depending on
+	// whether the function had a result type or not.
+	if p.tok == '<' {
+		p.next()
+		p.expectKeyword("inl")
+	} else if p.tok != scanner.Ident || p.lit != "inl" {
+		return
+	} else {
+		p.next()
+	}
+
+	p.expect(':')
+	want := p.parseInt()
+	p.expect('>')
+
+	defer func(w uint64) {
+		p.scanner.Whitespace = w
+	}(p.scanner.Whitespace)
+	p.scanner.Whitespace = 0
+
+	got := int64(0)
+	for got < want {
+		r := p.scanner.Next()
+		if r == scanner.EOF {
+			p.error("unexpected EOF")
+		}
+		got += int64(utf8.RuneLen(r))
+	}
+}
+
 // Types = "types" maxp1 exportedp1 (offset length)* .
 func (p *parser) parseTypes(pkg *types.Package) {
 	maxp1 := p.parseInt()
@@ -766,6 +812,11 @@
 		total += len
 	}
 
+	defer func(w uint64) {
+		p.scanner.Whitespace = w
+	}(p.scanner.Whitespace)
+	p.scanner.Whitespace = 0
+
 	// We should now have p.tok pointing to the final newline.
 	// The next runes from the scanner should be the type data.