escape: Add skeleton for gc analysis.

    
    Introduces a skeleton replacement escape analysis
    which contains four different phases extracted from the escape
    analysis implementation in gc/esc.go.  Also introduces the
    Escape_context each phase uses to make decisions.
    
    Reviewed-on: https://go-review.googlesource.com/18220

From-SVN: r235982

6 files changed, 182 insertions, 1 deletions

diff --git a/gcc/go/ChangeLog b/gcc/go/ChangeLog
index c179e79..e486a30 100644
--- a/gcc/go/ChangeLog
+++ b/gcc/go/ChangeLog
@@ -1,3 +1,8 @@
+2016-05-06  Chris Manghane  <cmang@google.com>
+
+	* Make-lang.in (GO_OBJS): Add go/escape.o (based on an entirely
+	new escape.cc).
+
 2016-04-29  Chris Manghane  <cmang@google.com>
 
 	* Make-lang.in (GO_OBJS): Remove go/dataflow.o, go/escape.o.
diff --git a/gcc/go/Make-lang.in b/gcc/go/Make-lang.in
index df27e21..d5b2a77 100644
--- a/gcc/go/Make-lang.in
+++ b/gcc/go/Make-lang.in
@@ -50,6 +50,7 @@ go-warn = $(STRICT_WARN)
 
 GO_OBJS = \
 	go/ast-dump.o \
+	go/escape.o \
 	go/export.o \
 	go/expressions.o \
 	go/go-backend.o \
diff --git a/gcc/go/gofrontend/MERGE b/gcc/go/gofrontend/MERGE
index 1874a2e..d925f37 100644
--- a/gcc/go/gofrontend/MERGE
+++ b/gcc/go/gofrontend/MERGE
@@ -1,4 +1,4 @@
-46b108136c0d102f181f0cc7c398e3db8c4d08a3
+33f1d1d151721305ba37f3e23652d21310f868af
 
 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/escape.cc b/gcc/go/gofrontend/escape.cc
new file mode 100644
index 0000000..51084c2
--- /dev/null
+++ b/gcc/go/gofrontend/escape.cc
@@ -0,0 +1,95 @@
+// escape.cc -- Go escape analysis (based on Go compiler algorithm).
+
+// Copyright 2016 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 "gogo.h"
+#include "escape.h"
+
+// Analyze the program flow for escape information.
+
+void
+Gogo::analyze_escape()
+{
+  // Discover strongly connected groups of functions to analyze for escape
+  // information in this package.
+  this->discover_analysis_sets();
+
+  for (std::vector<Analysis_set>::iterator p = this->analysis_sets_.begin();
+       p != this->analysis_sets_.end();
+       ++p)
+    {
+      std::vector<Named_object*> stack = p->first;
+      Escape_context* context = new Escape_context(p->second);
+
+      // Analyze the flow of each function; build the connection graph.
+      // This is the assign phase.
+      for (std::vector<Named_object*>::reverse_iterator fn = stack.rbegin();
+           fn != stack.rend();
+           ++fn)
+	{
+	  context->set_current_function(*fn);
+	  this->assign_connectivity(context, *fn);
+	}
+
+      // TODO(cmang): Introduce escape node.
+      // Propagate levels across each dst.  This is the flood phase.
+      // std::vector<Node*> dsts = context->dsts();
+      // for (std::vector<Node*>::iterator n = dsts.begin();
+      //      n != dsts.end();
+      //      ++n)
+      //   this->propagate_escape(context, *n);
+
+      // Tag each exported function's parameters with escape information.
+      for (std::vector<Named_object*>::iterator fn = stack.begin();
+           fn != stack.end();
+           ++fn)
+        this->tag_function(context, *fn);
+
+      delete context;
+    }
+}
+
+// Discover strongly connected groups of functions to analyze.
+
+void
+Gogo::discover_analysis_sets()
+{
+  // TODO(cmang): Implement Analysis_set discovery traversal.
+  // Escape_analysis_discover(this);
+  // this->traverse(&ead);
+}
+
+// Build a connectivity graph between nodes in the function being analyzed.
+
+void
+Gogo::assign_connectivity(Escape_context*, Named_object*)
+{
+  // TODO(cmang): Model the flow analysis of input parameters and results for a
+  // function.
+  // TODO(cmang): Analyze the current function's body.
+}
+
+// Propagate escape information across the nodes modeled in this Analysis_set,
+// TODO(cmang): Introduce escape analysis node.
+
+void
+Gogo::propagate_escape(Escape_context*)
+{
+  // TODO(cmang): Do a breadth-first traversal of a node's upstream, adjusting
+  // the Level appropriately.
+}
+
+
+// Tag each top-level function with escape information that will be used to
+// retain analysis results across imports.
+
+void
+Gogo::tag_function(Escape_context*, Named_object*)
+{
+  // TODO(cmang): Create escape information notes for each input and output
+  // parameter in a given function.
+  // Escape_analysis_tag eat(context, fn);
+  // this->traverse(&eat);
+}
diff --git a/gcc/go/gofrontend/escape.h b/gcc/go/gofrontend/escape.h
new file mode 100644
index 0000000..c830373
--- /dev/null
+++ b/gcc/go/gofrontend/escape.h
@@ -0,0 +1,44 @@
+// escape.h -- Go escape analysis (based on Go compiler algorithm).
+
+// Copyright 2016 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.
+
+#ifndef GO_ESCAPE_H
+#define GO_ESCAPE_H
+
+class Named_object;
+
+// The escape context for a set of functions being analyzed.
+
+class Escape_context
+{
+ public:
+  Escape_context(bool recursive)
+    : current_function_(NULL), recursive_(recursive)
+  { }
+
+  // Return the current function being analyzed.
+  Named_object*
+  current_function() const
+  { return this->current_function_; }
+
+  // Change the function being analyzed.
+  void
+  set_current_function(Named_object* fn)
+  { this->current_function_ = fn; }
+
+  // Return true if this is the context for a mutually recursive set of functions.
+  bool
+  recursive() const
+  { return this->recursive_; }
+
+ private:
+  // The current function being analyzed.
+  Named_object* current_function_;
+  // Return whether this is the context for a recursive function or a group of mutually
+  // recursive functions.
+  bool recursive_;
+};
+
+#endif // !defined(GO_ESCAPE_H)
diff --git a/gcc/go/gofrontend/gogo.h b/gcc/go/gofrontend/gogo.h
index 45c3857..b7a2e56 100644
--- a/gcc/go/gofrontend/gogo.h
+++ b/gcc/go/gofrontend/gogo.h
@@ -50,6 +50,7 @@ class Bblock;
 class Bvariable;
 class Blabel;
 class Bfunction;
+class Escape_context;
 
 // This file declares the basic classes used to hold the internal
 // representation of Go which is built by the parser.
@@ -345,6 +346,16 @@ class Gogo
   add_label_reference(const std::string&, Location,
 		      bool issue_goto_errors);
 
+  // An analysis set is a list of functions paired with a boolean that indicates
+  // whether the list of functions are recursive.
+  typedef std::pair<std::vector<Named_object*>, bool> Analysis_set;
+
+  // Add a GROUP of possibly RECURSIVE functions to the Analysis_set for this
+  // package.
+  void
+  add_analysis_set(const std::vector<Named_object*>& group, bool recursive)
+  { this->analysis_sets_.push_back(std::make_pair(group, recursive)); }
+
   // Return a snapshot of the current binding state.
   Bindings_snapshot*
   bindings_snapshot(Location);
@@ -544,6 +555,28 @@ class Gogo
   void
   check_return_statements();
 
+  // Analyze the program flow for escape information.
+  void
+  analyze_escape();
+
+  // Discover the groups of possibly recursive functions in this package.
+  void
+  discover_analysis_sets();
+
+  // Build a connectivity graph between the objects in each analyzed function.
+  void
+  assign_connectivity(Escape_context*, Named_object*);
+
+  // Traverse the objects in the connecitivty graph from the sink, adjusting the
+  // escape levels of each object.
+  void
+  propagate_escape(Escape_context*);
+
+  // Add notes about the escape level of a function's input and output
+  // parameters for exporting and importing top level functions. 
+  void
+  tag_function(Escape_context*, Named_object*);
+
   // Do all exports.
   void
   do_exports();
@@ -762,6 +795,9 @@ class Gogo
   bool specific_type_functions_are_written_;
   // Whether named types have been converted.
   bool named_types_are_converted_;
+  // A list containing groups of possibly mutually recursive functions to be
+  // considered during escape analysis.
+  std::vector<Analysis_set> analysis_sets_;
 };
 
 // A block of statements.