From 2c418e1f8f7e2b2196a8a1e45edd2db0439c8b41 Mon Sep 17 00:00:00 2001 From: Ian Lance Taylor Date: Fri, 6 May 2016 21:24:19 +0000 Subject: [PATCH] escape: Add escape graph nodes. Introduces the nodes used to model connectivity in the escape graph and related state: a node's escape level and an encoding that will be added to import and export data. Reviewed-on: https://go-review.googlesource.com/18268 From-SVN: r235988 --- gcc/go/gofrontend/MERGE | 2 +- gcc/go/gofrontend/escape.cc | 272 +++++++++++++++++++++++- gcc/go/gofrontend/escape.h | 404 +++++++++++++++++++++++++++++++++++- gcc/go/gofrontend/gogo.h | 3 +- gcc/go/gofrontend/types.h | 45 +++- 5 files changed, 709 insertions(+), 17 deletions(-) diff --git a/gcc/go/gofrontend/MERGE b/gcc/go/gofrontend/MERGE index d925f37948d..01f6e23183c 100644 --- a/gcc/go/gofrontend/MERGE +++ b/gcc/go/gofrontend/MERGE @@ -1,4 +1,4 @@ -33f1d1d151721305ba37f3e23652d21310f868af +7f5a9fde801eb755a5252fd4ff588b0a47475bd3 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 index 51084c21b0e..4a5c46c5522 100644 --- a/gcc/go/gofrontend/escape.cc +++ b/gcc/go/gofrontend/escape.cc @@ -4,9 +4,263 @@ // Use of this source code is governed by a BSD-style // license that can be found in the LICENSE file. +#include +#include + #include "gogo.h" +#include "types.h" +#include "expressions.h" +#include "statements.h" #include "escape.h" +// class Node. + +// Return the node's type, if it makes sense for it to have one. + +Type* +Node::type() const +{ + if (this->object() != NULL + && this->object()->is_variable()) + return this->object()->var_value()->type(); + else if (this->object() != NULL + && this->object()->is_function()) + return this->object()->func_value()->type(); + else if (this->expr() != NULL) + return this->expr()->type(); + else + return NULL; +} + +// A helper for reporting; return this node's location. + +Location +Node::location() const +{ + if (this->object() != NULL && !this->object()->is_sink()) + return this->object()->location(); + else if (this->expr() != NULL) + return this->expr()->location(); + else if (this->statement() != NULL) + return this->statement()->location(); + else + return Linemap::unknown_location(); +} + +// Return this node's state, creating it if has not been initialized. + +Node::Escape_state* +Node::state(Escape_context* context, Named_object* fn) +{ + if (this->state_ == NULL) + { + if (this->expr() != NULL && this->expr()->var_expression() != NULL) + { + // Tie state of variable references to underlying variables. + Named_object* var_no = this->expr()->var_expression()->named_object(); + Node* var_node = Node::make_node(var_no); + this->state_ = var_node->state(context, fn); + } + else + { + this->state_ = new Node::Escape_state; + if (fn == NULL) + fn = context->current_function(); + + this->state_->fn = fn; + } + } + go_assert(this->state_ != NULL); + return this->state_; +} + +void +Node::set_encoding(int enc) +{ + this->encoding_ = enc; + if (this->expr() != NULL + && this->expr()->var_expression() != NULL) + { + // Set underlying object as well. + Named_object* no = this->expr()->var_expression()->named_object(); + Node::make_node(no)->set_encoding(enc); + } +} + +bool +Node::is_sink() const +{ + if (this->object() != NULL + && this->object()->is_sink()) + return true; + else if (this->expr() != NULL + && this->expr()->is_sink_expression()) + return true; + return false; +} + +std::map Node::objects; +std::map Node::expressions; +std::map Node::statements; + +// Make a object node or return a cached node for this object. + +Node* +Node::make_node(Named_object* no) +{ + if (Node::objects.find(no) != Node::objects.end()) + return Node::objects[no]; + + Node* n = new Node(no); + std::pair val(no, n); + Node::objects.insert(val); + return n; +} + +// Make an expression node or return a cached node for this expression. + +Node* +Node::make_node(Expression* e) +{ + if (Node::expressions.find(e) != Node::expressions.end()) + return Node::expressions[e]; + + Node* n = new Node(e); + std::pair val(e, n); + Node::expressions.insert(val); + return n; +} + +// Make a statement node or return a cached node for this statement. + +Node* +Node::make_node(Statement* s) +{ + if (Node::statements.find(s) != Node::statements.end()) + return Node::statements[s]; + + Node* n = new Node(s); + std::pair val(s, n); + Node::statements.insert(val); + return n; +} + +// Returns the maximum of an exisiting escape value +// (and its additional parameter flow flags) and a new escape type. + +int +Node::max_encoding(int e, int etype) +{ + if ((e & ESCAPE_MASK) >= etype) + return e; + if (etype == Node::ESCAPE_NONE || etype == Node::ESCAPE_RETURN) + return (e & ~ESCAPE_MASK) | etype; + return etype; +} + +// Return a modified encoding for an input parameter that flows into an +// output parameter. + +// Class Escape_context. + +Escape_context::Escape_context(Gogo* gogo, bool recursive) + : gogo_(gogo), current_function_(NULL), recursive_(recursive), + sink_(Node::make_node(Named_object::make_sink())), loop_depth_(0) +{ + // The sink always escapes to heap and strictly lives outside of the + // current function i.e. loop_depth == -1. + this->sink_->set_encoding(Node::ESCAPE_HEAP); + Node::Escape_state* state = this->sink_->state(this, NULL); + state->loop_depth = -1; +} + +// Initialize the dummy return values for this Node N using the results +// in FNTYPE. + +void +Escape_context::init_retvals(Node* n, Function_type* fntype) +{ + if (fntype == NULL || fntype->results() == NULL) + return; + + Node::Escape_state* state = n->state(this, NULL); + Location loc = n->location(); + + int i = 0; + char buf[50]; + for (Typed_identifier_list::const_iterator p = fntype->results()->begin(); + p != fntype->results()->end(); + ++p, ++i) + { + snprintf(buf, sizeof buf, ".out%d", i); + Variable* dummy_var = new Variable(p->type(), NULL, false, false, + false, loc); + dummy_var->set_is_used(); + Named_object* dummy_no = + Named_object::make_variable(buf, NULL, dummy_var); + Node* dummy_node = Node::make_node(dummy_no); + // Initialize the state of the dummy output node. + dummy_node->state(this, NULL); + + // Add dummy node to the retvals of n. + state->retvals.push_back(dummy_node); + } +} + + +// Apply an indirection to N and return the result. +// This really only works if N is an expression node; it essentially becomes +// Node::make_node(n->expr()->deref()). We need the escape context to set the +// correct loop depth, however. + +Node* +Escape_context::add_dereference(Node* n) +{ + // Just return the original node if we can't add an indirection. + if (n->object() != NULL || n->statement() != NULL) + return n; + + Node* ind = Node::make_node(n->expr()->deref()); + // Initialize the state if this node doesn't already exist. + ind->state(this, NULL); + return ind; +} + +void +Escape_context::track(Node* n) +{ + n->set_encoding(Node::ESCAPE_NONE); + // Initialize this node's state if it hasn't been encountered + // before. + Node::Escape_state* state = n->state(this, NULL); + state->loop_depth = this->loop_depth_; + + this->noesc_.push_back(n); +} + +// Return the string representation of an escapement encoding. + +std::string +Escape_note::make_tag(int encoding) +{ + char buf[50]; + snprintf(buf, sizeof buf, "esc:0x%x", encoding); + return buf; +} + +// Return the escapement encoding for a string tag. + +int +Escape_note::parse_tag(std::string* tag) +{ + if (tag == NULL || tag->substr(0, 4) != "esc:") + return Node::ESCAPE_UNKNOWN; + int encoding = (int)strtol(tag->substr(4).c_str(), NULL, 0); + if (encoding == 0) + return Node::ESCAPE_UNKNOWN; + return encoding; +} + // Analyze the program flow for escape information. void @@ -21,7 +275,7 @@ Gogo::analyze_escape() ++p) { std::vector stack = p->first; - Escape_context* context = new Escape_context(p->second); + Escape_context* context = new Escape_context(this, p->second); // Analyze the flow of each function; build the connection graph. // This is the assign phase. @@ -33,13 +287,12 @@ Gogo::analyze_escape() 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); + std::set dsts = context->dsts(); + for (std::set::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(); @@ -71,11 +324,10 @@ Gogo::assign_connectivity(Escape_context*, Named_object*) // 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. +// Propagate escape information across the nodes modeled in this Analysis_set. void -Gogo::propagate_escape(Escape_context*) +Gogo::propagate_escape(Escape_context*, Node*) { // TODO(cmang): Do a breadth-first traversal of a node's upstream, adjusting // the Level appropriately. diff --git a/gcc/go/gofrontend/escape.h b/gcc/go/gofrontend/escape.h index c83037338b8..c409acb310c 100644 --- a/gcc/go/gofrontend/escape.h +++ b/gcc/go/gofrontend/escape.h @@ -7,16 +7,324 @@ #ifndef GO_ESCAPE_H #define GO_ESCAPE_H +#include "gogo.h" + class Named_object; +class Expression; +class Statement; +class Escape_context; + +// There can be loops in the escape graph that lead to arbitrary recursions. +// See comment in gc/esc.go. +static const int MIN_LEVEL = -2; + +// Level models the escapement of a Node using two integers that are computed +// by backwards-analyzing the flow of a function from its sink and increasing or +// decreasing based on dereferences and addressing, respectively. +// One integer, known as the level's VALUE (think absolute value), is just the +// sum of indirections (via referencing or dereferencing) applied to the Node. +// The second, known as the level's SUFFIX_VALUE, is the amount of indirections +// applied after some data has been copied from the node. When accessing a +// field F of an object O and then applying indirections, for example, the field +// access O.F is assumed to copy that data from O before applying indirections. +// With this, even if O.F escapes, it might mean that the content of O escape, +// but not the object O itself. + +class Level +{ +public: + Level() + : value_(0), suffix_value_(0) + { } + + Level(int value, int suffix) + : value_(value), suffix_value_(suffix) + { } + + // Return this level's value. + int + value() const + { return this->value_; } + + // Return this level's suffix value. + int + suffix_value() const + { return this->suffix_value_; } + + // Increase the level because a node is referenced. + Level + increase() const + { + if (this->value_ <= MIN_LEVEL) + return Level(MIN_LEVEL, 0); + + return Level(this->value_ + 1, this->suffix_value_ + 1); + } + + // Decrease the level because a node is dereferenced. + Level + decrease() const + { + if (this->value_ <= MIN_LEVEL) + return Level(MIN_LEVEL, 0); + + return Level(this->value_ - 1, this->suffix_value_ - 1); + } + + // Model a node being copied. + Level + copy() const + { + return Level(this->value_, std::max(this->suffix_value_, 0)); + } + + // Return a level with the minimum values of this level and l. + Level + min(const Level& l) const + { + return Level(std::min(this->value_, l.value()), + std::min(this->suffix_value_, l.suffix_value())); + } + + // Compare two levels for equality. + bool + operator==(const Level& l) const + { + return (this->value_ == l.value() + && this->suffix_value_ == l.suffix_value()); + } + + // Create a level from an integer value. + static Level + From(int i) + { + if (i <= MIN_LEVEL) + return Level(MIN_LEVEL, 0); + return Level(i, 0); + } + +private: + // The sum of all indirects (-1) and references (+1) applied to a Node. + int value_; + // The sum of all indirects (-1) abd references (+1) applied to a copied Node. + int suffix_value_; +}; + +// A node in the escape graph. This node is an alias to a particular node +// in the Go parse tree. Specifically, it can represent an expression node, +// a statement node, or a named object node (a variable or function). + +class Node +{ + public: + // This classification represents type of nodes in the Go parse tree that are + // interesting during the analysis. + enum Node_classification + { + NODE_OBJECT, + NODE_EXPRESSION, + NODE_STATEMENT + }; + + // The state necessary to keep track of how a node escapes. + struct Escape_state + { + // The current function. + Named_object* fn; + // A list of source nodes that flow into this node. + std::set flows; + // If the node is a function call, the list of nodes returned. + std::vector retvals; + // The node's loop depth. + int loop_depth; + // There is an extra loop depth in the flood phase used to account for + // variables referenced across closures. This is the maximum value of the + // extra loop depth seen during the flood that touches this node. + int max_extra_loop_depth; + // The node's level. + Level level; + // An ID given to a node when it is encountered as a flow from the current + // dst node. This is used to avoid infinite recursion of cyclic nodes. + int flood_id; + + Escape_state() + : fn(NULL), loop_depth(0), max_extra_loop_depth(0), flood_id(0) + { } + }; + + // Note: values in this enum appear in export data, and therefore MUST NOT + // change. + enum Escapement_encoding + { + ESCAPE_UNKNOWN, + // Does not escape to heap, result, or parameters. + ESCAPE_NONE, + // Is returned or reachable from a return statement. + ESCAPE_RETURN, + // Allocated in an inner loop, assigned to an outer loop, + // which allows construction of non-escaping but arbitrarily large linked + // data structures (i.e., not eligible for allocation in a fixed-size stack + // stack frame). + ESCAPE_SCOPE, + // Reachable from the heap. + ESCAPE_HEAP, + // By construction will not escape. + ESCAPE_NEVER + }; + + // Multiple constructors for each classification. + Node(Named_object* no) + : classification_(NODE_OBJECT), state_(NULL), encoding_(ESCAPE_UNKNOWN) + { this->u_.object_val = no; } + + Node(Expression* e) + : classification_(NODE_EXPRESSION), state_(NULL), encoding_(ESCAPE_UNKNOWN) + { this->u_.expression_val = e; } + + Node(Statement* s) + : classification_(NODE_STATEMENT), state_(NULL), encoding_(ESCAPE_UNKNOWN) + { this->u_.statement_val = s; } + + // Return this node's type. + Type* + type() const; + + // Return this node's location. + Location + location() const; + + // Return this node's escape state. + Escape_state* + state(Escape_context* context, Named_object* fn); + + // Return this node's escape encoding. + int + encoding() const + { return this->encoding_; } + + // Set the node's escape encoding. + void + set_encoding(int enc); + + // Is this node a sink? + bool + is_sink() const; + + // Methods to return the underlying value in the Node union. + Named_object* + object() const + { + return (this->classification_ == NODE_OBJECT + ? this->u_.object_val + : NULL); + } + + Expression* + expr() const + { + return (this->classification_ == NODE_EXPRESSION + ? this->u_.expression_val + : NULL); + } + + Statement* + statement() const + { + return (this->classification_ == NODE_STATEMENT + ? this->u_.statement_val + : NULL); + } + + // Static creation methods for each value supported in the union. + static Node* + make_node(Named_object*); + + static Node* + make_node(Expression*); + + static Node* + make_node(Statement*); + + // Return the maximum of an existing escape encoding E and a new + // escape type. + static int + max_encoding(int e, int etype); + + private: + // The classification of this Node. + Node_classification classification_; + // The value union. + union + { + // If NODE_OBJECT. + Named_object* object_val; + // If NODE_EXPRESSION. + Expression* expression_val; + // If NODE_STATEMENT. + Statement* statement_val; + } u_; + // The node's escape state. + Escape_state* state_; + // The node's escape encoding. + // The encoding: + // | Return Encoding: (width - ESCAPE_RETURN_BITS) | + // | Content Escapes bit: 1 | + // | Escapement_encoding: ESCAPE_BITS | + int encoding_; + + // Cache all the Nodes created via Node::make_node to make the API simpler. + static std::map objects; + static std::map expressions; + static std::map statements; +}; + +// The amount of bits used for the escapement encoding. +static const int ESCAPE_BITS = 3; + +// Mask used to extract encoding. +static const int ESCAPE_MASK = (1 << ESCAPE_BITS) - 1; + +// Value obtained by indirect of parameter escapes to heap. +static const int ESCAPE_CONTENT_ESCAPES = 1 << ESCAPE_BITS; + +// The amount of bits used in encoding of return values. +static const int ESCAPE_RETURN_BITS = ESCAPE_BITS + 1; + +// For each output, the number of bits for a tag. +static const int ESCAPE_BITS_PER_OUTPUT_IN_TAG = 3; + +// The bit max to extract a single tag. +static const int ESCAPE_BITS_MASK_FOR_TAG = (1 << ESCAPE_BITS_PER_OUTPUT_IN_TAG) - 1; + +// The largest level that can be stored in a tag. +static const int ESCAPE_MAX_ENCODED_LEVEL = ESCAPE_BITS_MASK_FOR_TAG - 1; + +// A helper for converting escape notes from encoded integers to a +// textual format and vice-versa. + +class Escape_note +{ + public: + // Return the string representation of an escapement encoding. + static std::string + make_tag(int encoding); + + // Return the escapement encoding for a string tag. + static int + parse_tag(std::string* tag); +}; // The escape context for a set of functions being analyzed. class Escape_context { public: - Escape_context(bool recursive) - : current_function_(NULL), recursive_(recursive) - { } + Escape_context(Gogo* gogo, bool recursive); + + // Return the Go IR. + Gogo* + gogo() const + { return this->gogo_; } // Return the current function being analyzed. Named_object* @@ -33,12 +341,102 @@ class Escape_context recursive() const { return this->recursive_; } + // Return the special sink node for this context. + Node* + sink() + { return this->sink_; } + + // Return the current loop depth. + int + loop_depth() const + { return this->loop_depth_; } + + // Increase the loop depth. + void + increase_loop_depth() + { this->loop_depth_++; } + + // Decrease the loop depth. + void + decrease_loop_depth() + { this->loop_depth_--; } + + void + set_loop_depth(int depth) + { this->loop_depth_ = depth; } + + // Return the destination nodes encountered in this context. + const std::set& + dsts() const + { return this->dsts_; } + + // Add a destination node. + void + add_dst(Node* dst) + { this->dsts_.insert(dst); } + + // Return the nodes initially marked as non-escaping before flooding. + const std::vector& + non_escaping_nodes() const + { return this->noesc_; } + + // Initialize the dummy return values for this Node N using the results + // in FNTYPE. + void + init_retvals(Node* n, Function_type* fntype); + + // Return the indirection of Node N. + Node* + add_dereference(Node* n); + + // Keep track of possibly non-escaping node N. + void + track(Node* n); + + int + flood_id() const + { return this->flood_id_; } + + void + increase_flood_id() + { this->flood_id_++; } + + int + pdepth() const + { return this->pdepth_; } + + void + increase_pdepth() + { this->pdepth_++; } + + void + decrease_pdepth() + { this->pdepth_--; } + private: + // The Go IR. + Gogo* gogo_; // 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_; + // The sink for this escape context. Nodes whose reference objects created + // outside the current function are assigned to the sink as well as nodes that + // the analysis loses track of. + Node* sink_; + // Used to detect nested loop scopes. + int loop_depth_; + // All the destination nodes considered in this set of analyzed functions. + std::set dsts_; + // All the nodes that were noted as possibly not escaping in this context. + std::vector noesc_; + // An ID given to each dst and the flows discovered through DFS of that dst. + // This is used to avoid infinite recursion from nodes that point to each + // other within the flooding phase. + int flood_id_; + // The current level of recursion within a flooded section; used to debug. + int pdepth_; }; #endif // !defined(GO_ESCAPE_H) diff --git a/gcc/go/gofrontend/gogo.h b/gcc/go/gofrontend/gogo.h index b7a2e566a2f..a04999e7f36 100644 --- a/gcc/go/gofrontend/gogo.h +++ b/gcc/go/gofrontend/gogo.h @@ -51,6 +51,7 @@ class Bvariable; class Blabel; class Bfunction; class Escape_context; +class Node; // This file declares the basic classes used to hold the internal // representation of Go which is built by the parser. @@ -570,7 +571,7 @@ class Gogo // Traverse the objects in the connecitivty graph from the sink, adjusting the // escape levels of each object. void - propagate_escape(Escape_context*); + propagate_escape(Escape_context*, Node*); // Add notes about the escape level of a function's input and output // parameters for exporting and importing top level functions. diff --git a/gcc/go/gofrontend/types.h b/gcc/go/gofrontend/types.h index bf673e63ca8..682f61145d2 100644 --- a/gcc/go/gofrontend/types.h +++ b/gcc/go/gofrontend/types.h @@ -8,6 +8,7 @@ #define GO_TYPES_H #include "go-linemap.h" +#include "escape.h" class Gogo; class Package; @@ -1324,7 +1325,7 @@ class Typed_identifier public: Typed_identifier(const std::string& name, Type* type, Location location) - : name_(name), type_(type), location_(location) + : name_(name), type_(type), location_(location), note_(NULL) { } // Get the name. @@ -1351,6 +1352,16 @@ class Typed_identifier this->type_ = type; } + // Get the escape note. + std::string* + note() const + { return this->note_; } + + // Set the escape note. + void + set_note(const std::string& note) + { this->note_ = new std::string(note); } + private: // Identifier name. std::string name_; @@ -1358,6 +1369,9 @@ class Typed_identifier Type* type_; // The location where the name was seen. Location location_; + // Escape note for this typed identifier. Used when importing and exporting + // functions. + std::string* note_; }; // A list of Typed_identifiers. @@ -1422,6 +1436,10 @@ class Typed_identifier_list back() const { return this->entries_.back(); } + Typed_identifier& + at(size_t i) + { return this->entries_.at(i); } + const Typed_identifier& at(size_t i) const { return this->entries_.at(i); } @@ -1778,7 +1796,7 @@ class Function_type : public Type : Type(TYPE_FUNCTION), receiver_(receiver), parameters_(parameters), results_(results), location_(location), is_varargs_(false), is_builtin_(false), - fnbtype_(NULL) + fnbtype_(NULL), is_tagged_(false) { } // Get the receiver. @@ -1786,6 +1804,11 @@ class Function_type : public Type receiver() const { return this->receiver_; } + // Add an escape note for the receiver. + void + add_receiver_note(int encoding) + { this->receiver_->set_note(Escape_note::make_tag(encoding)); } + // Get the return names and types. const Typed_identifier_list* results() const @@ -1796,6 +1819,21 @@ class Function_type : public Type parameters() const { return this->parameters_; } + // Add an escape note for the ith parameter. + void + add_parameter_note(int index, int encoding) + { this->parameters_->at(index).set_note(Escape_note::make_tag(encoding)); } + + // Whether this function has been tagged during escape analysis. + bool + is_tagged() const + { return this->is_tagged_; } + + // Mark this function as tagged after analyzing its escape. + void + set_is_tagged() + { this->is_tagged_ = true; } + // Whether this is a varargs function. bool is_varargs() const @@ -1950,6 +1988,9 @@ class Function_type : public Type // The backend representation of this type for backend function // declarations and definitions. Btype* fnbtype_; + // Whether this function has been analyzed by escape analysis. If this is + // TRUE, this function type's parameters contain a summary of the analysis. + bool is_tagged_; }; // The type of a function's backend representation. -- 2.30.2