From 2a30f87f75644bb5ff3e8f42d4922bef99511b4a Mon Sep 17 00:00:00 2001 From: Chris Manghane Date: Fri, 6 May 2016 17:37:55 +0000 Subject: [PATCH] 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 --- gcc/go/ChangeLog | 5 ++ gcc/go/Make-lang.in | 1 + gcc/go/gofrontend/MERGE | 2 +- gcc/go/gofrontend/escape.cc | 95 +++++++++++++++++++++++++++++++++++++ gcc/go/gofrontend/escape.h | 44 +++++++++++++++++ gcc/go/gofrontend/gogo.h | 36 ++++++++++++++ 6 files changed, 182 insertions(+), 1 deletion(-) create mode 100644 gcc/go/gofrontend/escape.cc create mode 100644 gcc/go/gofrontend/escape.h diff --git a/gcc/go/ChangeLog b/gcc/go/ChangeLog index c179e79e281..e486a305a01 100644 --- a/gcc/go/ChangeLog +++ b/gcc/go/ChangeLog @@ -1,3 +1,8 @@ +2016-05-06 Chris Manghane + + * Make-lang.in (GO_OBJS): Add go/escape.o (based on an entirely + new escape.cc). + 2016-04-29 Chris Manghane * 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 df27e217828..d5b2a776776 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 1874a2ea3be..d925f37948d 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 00000000000..51084c21b0e --- /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::iterator p = this->analysis_sets_.begin(); + p != this->analysis_sets_.end(); + ++p) + { + std::vector 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::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 dsts = context->dsts(); + // for (std::vector::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::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 00000000000..c83037338b8 --- /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 45c38578102..b7a2e566a2f 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, bool> Analysis_set; + + // Add a GROUP of possibly RECURSIVE functions to the Analysis_set for this + // package. + void + add_analysis_set(const std::vector& 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_sets_; }; // A block of statements. -- 2.30.2