Viewing file:  escape.h (12.86 KB) -rw-r--r--
Select action/file-type:
 (+) |  (+) |  (+) | Code (+) | Session (+) |  (+) | SDB (+) |  (+) |  (+) |  (+) |  (+) |  (+) |
// 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)
|
