| // 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 | |
| #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 dereferenced. | |
| 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 referenced. | |
| 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 references (-1) and indirects (+1) applied to a Node. | |
| int value_; | |
| // The sum of all references (-1) abd indirects (+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, | |
| // A "fake" node that models the indirection of its child node. | |
| // This node does not correspond to an AST node. | |
| NODE_INDIRECT | |
| }; | |
| // 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<Node*> flows; | |
| // If the node is a function call, the list of nodes returned. | |
| std::vector<Node*> 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, | |
| // 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), | |
| child_(NULL) | |
| { this->u_.object_val = no; } | |
| Node(Expression* e) | |
| : classification_(NODE_EXPRESSION), state_(NULL), encoding_(ESCAPE_UNKNOWN), | |
| child_(NULL) | |
| { this->u_.expression_val = e; } | |
| Node(Statement* s) | |
| : classification_(NODE_STATEMENT), state_(NULL), encoding_(ESCAPE_UNKNOWN), | |
| child_(NULL) | |
| { this->u_.statement_val = s; } | |
| Node(Node *n) | |
| : classification_(NODE_INDIRECT), state_(NULL), encoding_(ESCAPE_UNKNOWN), | |
| child_(n) | |
| {} | |
| ~Node(); | |
| // Return this node's type. | |
| Type* | |
| type() const; | |
| // Return this node's location. | |
| Location | |
| location() const; | |
| // Return the location where the node's underlying object is defined. | |
| Location | |
| definition_location() const; | |
| // Return this node's AST formatted string. | |
| std::string | |
| ast_format(Gogo*) const; | |
| // Return this node's detailed format string. | |
| std::string | |
| details(); | |
| std::string | |
| op_format() const; | |
| // Return this node's escape state. | |
| Escape_state* | |
| state(Escape_context* context, Named_object* fn); | |
| // Return this node's escape encoding. | |
| int | |
| encoding(); | |
| // Set the node's escape encoding. | |
| void | |
| set_encoding(int enc); | |
| bool | |
| is_big(Escape_context*) const; | |
| 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); | |
| } | |
| bool | |
| is_indirect() const | |
| { return this->classification_ == NODE_INDIRECT; } | |
| // Return its child node. | |
| // Child node is used only in indirect node, and in expression node | |
| // representing slicing an array. | |
| Node* | |
| child() const | |
| { return this->child_; } | |
| // Set the child node. | |
| void | |
| set_child(Node* n) | |
| { this->child_ = n; } | |
| // 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*); | |
| static Node* | |
| make_indirect_node(Node*); | |
| // Return the maximum of an existing escape encoding E and a new | |
| // escape type. | |
| static int | |
| max_encoding(int e, int etype); | |
| // Return a modified encoding for an input parameter that flows into an | |
| // output parameter. | |
| static int | |
| note_inout_flows(int e, int index, Level level); | |
| // Reclaim nodes. | |
| static void | |
| reclaim_nodes(); | |
| 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_; | |
| // Child node, used only in indirect node, and expression node representing | |
| // slicing an array. | |
| Node* child_; | |
| // Cache all the Nodes created via Node::make_node to make the API simpler. | |
| static Unordered_map(Named_object*, Node*) objects; | |
| static Unordered_map(Expression*, Node*) expressions; | |
| static Unordered_map(Statement*, Node*) statements; | |
| // Collection of all NODE_INDIRECT Nodes, used for reclaiming memory. This | |
| // is not a cache -- each make_indirect_node will make a fresh Node. | |
| static std::vector<Node*> indirects; | |
| }; | |
| // 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(Gogo* gogo, bool recursive); | |
| // Return the Go IR. | |
| Gogo* | |
| gogo() const | |
| { return this->gogo_; } | |
| // 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 the name of the current function. | |
| std::string | |
| current_function_name() const; | |
| // Return true if this is the context for a mutually recursive set of functions. | |
| bool | |
| 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<Node*>& | |
| 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<Node*>& | |
| 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<Node*> dsts_; | |
| // All the nodes that were noted as possibly not escaping in this context. | |
| std::vector<Node*> 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) |