// 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 "go-system.h" #include #include #include #include "gogo.h" #include "types.h" #include "expressions.h" #include "statements.h" #include "escape.h" #include "ast-dump.h" #include "go-optimize.h" #include "go-diagnostics.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(); } // To match the cmd/gc debug output, strip away the packed prefixes on functions // and variable/expressions. std::string strip_packed_prefix(Gogo* gogo, const std::string& s) { std::string packed_prefix = "." + gogo->pkgpath() + "."; std::string fmt = s; for (size_t pos = fmt.find(packed_prefix); pos != std::string::npos; pos = fmt.find(packed_prefix)) fmt.erase(pos, packed_prefix.length()); return fmt; } // A helper for debugging; return this node's AST formatted string. // This is an implementation of gc's Nconv with obj.FmtShort. std::string Node::ast_format(Gogo* gogo) const { std::ostringstream ss; if (this->is_sink()) ss << ".sink"; else if (this->object() != NULL) { Named_object* no = this->object(); if (no->is_function() && no->func_value()->enclosing() != NULL) return "func literal"; ss << no->name(); } else if (this->expr() != NULL) { Expression* e = this->expr(); bool is_call = e->call_expression() != NULL; if (is_call) e->call_expression()->fn(); Func_expression* fe = e->func_expression();; bool is_closure = fe != NULL && fe->closure() != NULL; if (is_closure) { if (is_call) return "(func literal)()"; return "func literal"; } Ast_dump_context::dump_to_stream(this->expr(), &ss); } else { Statement* s = this->statement(); Goto_unnamed_statement* unnamed = s->goto_unnamed_statement(); if (unnamed != NULL) { Statement* derived = unnamed->unnamed_label()->derived_from(); if (derived != NULL) { switch (derived->classification()) { case Statement::STATEMENT_FOR: case Statement::STATEMENT_FOR_RANGE: return "for loop"; break; case Statement::STATEMENT_SWITCH: return "switch"; break; case Statement::STATEMENT_TYPE_SWITCH: return "type switch"; break; default: break; } } } Ast_dump_context::dump_to_stream(s, &ss); } return strip_packed_prefix(gogo, ss.str()); } // A helper for debugging; return this node's detailed format string. // This is an implementation of gc's Jconv with obj.FmtShort. std::string Node::details() const { std::stringstream details; if (!this->is_sink()) details << " l(" << Linemap::location_to_line(this->location()) << ")"; bool is_varargs = false; bool is_address_taken = false; bool is_in_heap = false; bool is_assigned = false; std::string class_name; Expression* e = this->expr(); Named_object* node_object = NULL; if (this->object() != NULL) node_object = this->object(); else if (e != NULL && e->var_expression() != NULL) node_object = e->var_expression()->named_object(); if (node_object) { // TODO(cmang): For named variables and functions, we want to output // the function depth. if (node_object->is_variable()) { Variable* var = node_object->var_value(); is_varargs = var->is_varargs_parameter(); is_address_taken = (var->is_address_taken() || var->is_non_escaping_address_taken()); is_in_heap = var->is_in_heap(); is_assigned = var->init() != NULL; if (var->is_global()) class_name = "PEXTERN"; else if (var->is_parameter()) class_name = "PPARAM"; else if (var->is_closure()) class_name = "PPARAMREF"; else class_name = "PAUTO"; } else if (node_object->is_result_variable()) class_name = "PPARAMOUT"; else if (node_object->is_function() || node_object->is_function_declaration()) class_name = "PFUNC"; } else if (e != NULL && e->enclosed_var_expression() != NULL) { Named_object* enclosed = e->enclosed_var_expression()->variable(); if (enclosed->is_variable()) { Variable* var = enclosed->var_value(); is_address_taken = (var->is_address_taken() || var->is_non_escaping_address_taken()); } else { Result_variable* var = enclosed->result_var_value(); is_address_taken = (var->is_address_taken() || var->is_non_escaping_address_taken()); } class_name = "PPARAMREF"; } if (!class_name.empty()) { details << " class(" << class_name; if (is_in_heap) details << ",heap"; details << ")"; } switch ((this->encoding() & ESCAPE_MASK)) { case Node::ESCAPE_UNKNOWN: break; case Node::ESCAPE_HEAP: details << " esc(h)"; break; case Node::ESCAPE_SCOPE: details << " esc(s)"; break; case Node::ESCAPE_NONE: details << " esc(no)"; break; case Node::ESCAPE_NEVER: details << " esc(N)"; break; default: details << " esc(" << this->encoding() << ")"; break; } if (this->state_ != NULL && this->state_->loop_depth != 0) details << " ld(" << this->state_->loop_depth << ")"; if (is_varargs) details << " isddd(1)"; if (is_address_taken) details << " addrtaken"; if (is_assigned) details << " assigned"; return details.str(); } std::string Node::op_format() const { std::stringstream op; Ast_dump_context adc(&op, false); if (this->expr() != NULL) { Expression* e = this->expr(); switch (e->classification()) { case Expression::EXPRESSION_UNARY: adc.dump_operator(e->unary_expression()->op()); break; case Expression::EXPRESSION_BINARY: adc.dump_operator(e->binary_expression()->op()); break; case Expression::EXPRESSION_CALL: op << "function call"; break; case Expression::EXPRESSION_FUNC_REFERENCE: if (e->func_expression()->is_runtime_function()) { switch (e->func_expression()->runtime_code()) { case Runtime::GOPANIC: op << "panic"; break; case Runtime::GROWSLICE: op << "append"; break; case Runtime::SLICECOPY: case Runtime::SLICESTRINGCOPY: case Runtime::TYPEDSLICECOPY: op << "copy"; break; case Runtime::MAKECHAN: case Runtime::MAKEMAP: case Runtime::MAKESLICE: case Runtime::MAKESLICE64: op << "make"; break; case Runtime::DEFERPROC: op << "defer"; break; case Runtime::GORECOVER: op << "recover"; break; case Runtime::CLOSE: op << "close"; break; default: break; } } break; case Expression::EXPRESSION_ALLOCATION: op << "new"; break; case Expression::EXPRESSION_RECEIVE: op << "<-"; break; default: break; } } if (this->statement() != NULL) { switch (this->statement()->classification()) { case Statement::STATEMENT_DEFER: op << "defer"; break; case Statement::STATEMENT_RETURN: op << "return"; break; default: break; } } return op.str(); } // 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_big(Escape_context* context) const { Type* t = this->type(); if (t == NULL || t->is_call_multiple_result_type() || t->is_sink_type() || t->is_void_type() || t->is_abstract()) return false; int64_t size; bool ok = t->backend_type_size(context->gogo(), &size); bool big = ok && (size < 0 || size > 10 * 1024 * 1024); if (this->expr() != NULL) { if (this->expr()->allocation_expression() != NULL) { ok = t->deref()->backend_type_size(context->gogo(), &size); big = big || size <= 0 || size >= (1 << 16); } else if (this->expr()->call_expression() != NULL) { Call_expression* call = this->expr()->call_expression(); Func_expression* fn = call->fn()->func_expression(); if (fn != NULL && fn->is_runtime_function() && (fn->runtime_code() == Runtime::MAKESLICE || fn->runtime_code() == Runtime::MAKESLICE64)) { // Second argument is length. Expression_list::iterator p = call->args()->begin(); ++p; Numeric_constant nc; unsigned long v; if ((*p)->numeric_constant_value(&nc) && nc.to_unsigned_long(&v) == Numeric_constant::NC_UL_VALID) big = big || v >= (1 << 16); } } } return big; } 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. int Node::note_inout_flows(int e, int index, Level level) { // Flow+level is encoded in two bits. // 00 = not flow, xx = level+1 for 0 <= level <= maxEncodedLevel. // 16 bits for Esc allows 6x2bits or 4x3bits or 3x4bits if additional // information would be useful. if (level.value() <= 0 && level.suffix_value() > 0) return Node::max_encoding(e|ESCAPE_CONTENT_ESCAPES, Node::ESCAPE_NONE); if (level.value() < 0) return Node::ESCAPE_HEAP; if (level.value() > ESCAPE_MAX_ENCODED_LEVEL) level = Level::From(ESCAPE_MAX_ENCODED_LEVEL); int encoded = level.value() + 1; int shift = ESCAPE_BITS_PER_OUTPUT_IN_TAG * index + ESCAPE_RETURN_BITS; int old = (e >> shift) & ESCAPE_BITS_MASK_FOR_TAG; if (old == 0 || (encoded != 0 && encoded < old)) old = encoded; int encoded_flow = old << shift; if (((encoded_flow >> shift) & ESCAPE_BITS_MASK_FOR_TAG) != old) { // Failed to encode. Put this on the heap. return Node::ESCAPE_HEAP; } return (e & ~(ESCAPE_BITS_MASK_FOR_TAG << shift)) | encoded_flow; } // 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), flood_id_(0), pdepth_(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; } std::string debug_function_name(Named_object* fn) { if (fn == NULL) return ""; if (!fn->is_function() || fn->func_value()->enclosing() == NULL) return Gogo::unpack_hidden_name(fn->name()); // Closures are named ".$nested#" where # starts from 0 to distinguish // between closures. The cmd/gc closures are named in the format // "enclosing.func#" where # starts from 1. If this is a closure, format // its name to match cmd/gc. Named_object* enclosing = fn->func_value()->enclosing(); // Extract #. std::string name = Gogo::unpack_hidden_name(fn->name()); int closure_num = (int)strtol(name.substr(6).c_str(), NULL, 0); closure_num++; name = Gogo::unpack_hidden_name(enclosing->name()); char buf[200]; snprintf(buf, sizeof buf, "%s.func%d", name.c_str(), closure_num); return buf; } // Return the name of the current function. std::string Escape_context::current_function_name() const { return debug_function_name(this->current_function_); } // 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; } // The -fgo-optimize-alloc flag activates this escape analysis. Go_optimize optimize_allocation_flag("allocs"); // Analyze the program flow for escape information. void Gogo::analyze_escape() { if (!optimize_allocation_flag.is_enabled() || saw_errors()) return; // 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(this, 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); } // Propagate levels across each dst. This is the flood phase. 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(); fn != stack.end(); ++fn) this->tag_function(context, *fn); if (this->debug_escape_level() != 0) { std::vector noesc = context->non_escaping_nodes(); for (std::vector::const_iterator n = noesc.begin(); n != noesc.end(); ++n) { Node::Escape_state* state = (*n)->state(context, NULL); if (((*n)->encoding() & ESCAPE_MASK) == int(Node::ESCAPE_NONE)) go_inform((*n)->location(), "%s %s does not escape", strip_packed_prefix(this, debug_function_name(state->fn)).c_str(), (*n)->ast_format(this).c_str()); } // TODO(cmang): Which objects in context->noesc actually don't escape. } delete context; } } // Traverse the program, discovering the functions that are roots of strongly // connected components. The goal of this phase to produce a set of functions // that must be analyzed in order. class Escape_analysis_discover : public Traverse { public: Escape_analysis_discover(Gogo* gogo) : Traverse(traverse_functions), gogo_(gogo), component_ids_() { } int function(Named_object*); int visit(Named_object*); int visit_code(Named_object*, int); private: // A counter used to generate the ID for the function node in the graph. static int id; // Type used to map functions to an ID in a graph of connected components. typedef Unordered_map(Named_object*, int) Component_ids; // The Go IR. Gogo* gogo_; // The list of functions encountered during connected component discovery. Component_ids component_ids_; // The stack of functions that this component consists of. std::stack stack_; }; int Escape_analysis_discover::id = 0; // Visit each function. int Escape_analysis_discover::function(Named_object* fn) { this->visit(fn); return TRAVERSE_CONTINUE; } // Visit a function FN, adding it to the current stack of functions // in this connected component. If this is the root of the component, // create a set of functions to be analyzed later. // // Finding these sets is finding strongly connected components // in the static call graph. The algorithm for doing that is taken // from Sedgewick, Algorithms, Second Edition, p. 482, with two // adaptations. // // First, a closure (fn->func_value()->enclosing() == NULL) cannot be the // root of a connected component. Refusing to use it as a root // forces it into the component of the function in which it appears. // This is more convenient for escape analysis. // // Second, each function becomes two virtual nodes in the graph, // with numbers n and n+1. We record the function's node number as n // but search from node n+1. If the search tells us that the component // number (min) is n+1, we know that this is a trivial component: one function // plus its closures. If the search tells us that the component number is // n, then there was a path from node n+1 back to node n, meaning that // the function set is mutually recursive. The escape analysis can be // more precise when analyzing a single non-recursive function than // when analyzing a set of mutually recursive functions. int Escape_analysis_discover::visit(Named_object* fn) { Component_ids::const_iterator p = this->component_ids_.find(fn); if (p != this->component_ids_.end()) // Already visited. return p->second; this->id++; int id = this->id; this->component_ids_[fn] = id; this->id++; int min = this->id; this->stack_.push(fn); min = this->visit_code(fn, min); if ((min == id || min == id + 1) && fn->is_function() && fn->func_value()->enclosing() == NULL) { bool recursive = min == id; std::vector group; for (; !this->stack_.empty(); this->stack_.pop()) { Named_object* n = this->stack_.top(); if (n == fn) { this->stack_.pop(); break; } group.push_back(n); this->component_ids_[n] = std::numeric_limits::max(); } group.push_back(fn); this->component_ids_[fn] = std::numeric_limits::max(); std::reverse(group.begin(), group.end()); this->gogo_->add_analysis_set(group, recursive); } return min; } // Helper class for discovery step. Traverse expressions looking for // function calls and closures to visit during the discovery step. class Escape_discover_expr : public Traverse { public: Escape_discover_expr(Escape_analysis_discover* ead, int min) : Traverse(traverse_expressions), ead_(ead), min_(min) { } int min() { return this->min_; } int expression(Expression** pexpr); private: // The original discovery analysis. Escape_analysis_discover* ead_; // The minimum component ID in this group. int min_; }; // Visit any calls or closures found when discovering expressions. int Escape_discover_expr::expression(Expression** pexpr) { Expression* e = *pexpr; Named_object* fn = NULL; if (e->call_expression() != NULL && e->call_expression()->fn()->func_expression() != NULL) { // Method call or function call. fn = e->call_expression()->fn()->func_expression()->named_object(); } else if (e->func_expression() != NULL && e->func_expression()->closure() != NULL) { // Closure. fn = e->func_expression()->named_object(); } if (fn != NULL) this->min_ = std::min(this->min_, this->ead_->visit(fn)); return TRAVERSE_CONTINUE; } // Visit the body of each function, returns ID of the minimum connected // component found in the body. int Escape_analysis_discover::visit_code(Named_object* fn, int min) { if (!fn->is_function()) return min; Escape_discover_expr ede(this, min); fn->func_value()->traverse(&ede); return ede.min(); } // Discover strongly connected groups of functions to analyze. void Gogo::discover_analysis_sets() { Escape_analysis_discover ead(this); this->traverse(&ead); } // Traverse all label and goto statements and mark the underlying label // as looping or not looping. class Escape_analysis_loop : public Traverse { public: Escape_analysis_loop() : Traverse(traverse_statements) { } int statement(Block*, size_t*, Statement*); }; int Escape_analysis_loop::statement(Block*, size_t*, Statement* s) { if (s->label_statement() != NULL) s->label_statement()->label()->set_nonlooping(); else if (s->goto_statement() != NULL) { if (s->goto_statement()->label()->nonlooping()) s->goto_statement()->label()->set_looping(); } return TRAVERSE_CONTINUE; } // Traversal class used to look at all interesting statements within a function // in order to build a connectivity graph between all nodes within a context's // scope. class Escape_analysis_assign : public Traverse { public: Escape_analysis_assign(Escape_context* context, Named_object* fn) : Traverse(traverse_statements | traverse_expressions), context_(context), fn_(fn) { } // Model statements within a function as assignments and flows between nodes. int statement(Block*, size_t*, Statement*); // Model expressions within a function as assignments and flows between nodes. int expression(Expression**); // Model calls within a function as assignments and flows between arguments // and results. void call(Call_expression* call); // Model the assignment of DST to SRC. void assign(Node* dst, Node* src); // Model the assignment of DST to dereference of SRC. void assign_deref(Node* dst, Node* src); // Model the input-to-output assignment flow of one of a function call's // arguments, where the flow is encoding in NOTE. int assign_from_note(std::string* note, const std::vector& dsts, Node* src); // Record the flow of SRC to DST in DST. void flows(Node* dst, Node* src); private: // The escape context for this set of functions. Escape_context* context_; // The current function being analyzed. Named_object* fn_; }; // Model statements within a function as assignments and flows between nodes. int Escape_analysis_assign::statement(Block*, size_t*, Statement* s) { // Adjust the loop depth as we enter/exit blocks related to for statements. bool is_for_statement = (s->is_block_statement() && s->block_statement()->is_lowered_for_statement()); if (is_for_statement) this->context_->increase_loop_depth(); s->traverse_contents(this); if (is_for_statement) this->context_->decrease_loop_depth(); Gogo* gogo = this->context_->gogo(); int debug_level = gogo->debug_escape_level(); if (debug_level > 1 && s->unnamed_label_statement() == NULL && s->expression_statement() == NULL && !s->is_block_statement()) { Node* n = Node::make_node(s); std::string fn_name = this->context_->current_function_name(); go_inform(s->location(), "[%d] %s esc: %s", this->context_->loop_depth(), fn_name.c_str(), n->ast_format(gogo).c_str()); } switch (s->classification()) { case Statement::STATEMENT_VARIABLE_DECLARATION: { Named_object* var = s->variable_declaration_statement()->var(); Node* var_node = Node::make_node(var); Node::Escape_state* state = var_node->state(this->context_, NULL); state->loop_depth = this->context_->loop_depth(); // Set the loop depth for this declaration. if (var->is_variable() && var->var_value()->init() != NULL) { Node* init_node = Node::make_node(var->var_value()->init()); this->assign(var_node, init_node); } } break; case Statement::STATEMENT_LABEL: { Label_statement* label_stmt = s->label_statement(); if (label_stmt->label()->looping()) this->context_->increase_loop_depth(); if (debug_level > 1) { std::string label_type = (label_stmt->label()->looping() ? "looping" : "nonlooping"); go_inform(s->location(), "%s %s label", label_stmt->label()->name().c_str(), label_type.c_str()); } } break; case Statement::STATEMENT_SWITCH: case Statement::STATEMENT_TYPE_SWITCH: // Want to model the assignment of each case variable to the switched upon // variable. This should be lowered into assignment statements; nothing // to here if that's the case. // TODO(cmang): Verify. break; case Statement::STATEMENT_ASSIGNMENT: { Assignment_statement* assn = s->assignment_statement(); Node* lhs = Node::make_node(assn->lhs()); Node* rhs = Node::make_node(assn->rhs()); // TODO(cmang): Add special case for escape analysis no-op: // func (b *Buffer) Foo() { // n, m := ... // b.buf = b.buf[n:m] // } // This is okay for now, it just means b escapes; it is conservative. this->assign(lhs, rhs); } break; case Statement::STATEMENT_SEND: { Node* sent_node = Node::make_node(s->send_statement()->val()); this->assign(this->context_->sink(), sent_node); } break; case Statement::STATEMENT_DEFER: if (this->context_->loop_depth() == 1) break; // fallthrough case Statement::STATEMENT_GO: { // Defer f(x) or go f(x). // Both f and x escape to the heap. Thunk_statement* thunk = s->thunk_statement(); if (thunk->call()->call_expression() == NULL) break; Call_expression* call = thunk->call()->call_expression(); Node* func_node = Node::make_node(call->fn()); this->assign(this->context_->sink(), func_node); if (call->args() != NULL) { for (Expression_list::const_iterator p = call->args()->begin(); p != call->args()->end(); ++p) { Node* arg_node = Node::make_node(*p); this->assign(this->context_->sink(), arg_node); } } } break; // TODO(cmang): Associate returned values with dummy return nodes. default: break; } return TRAVERSE_SKIP_COMPONENTS; } // Model expressions within a function as assignments and flows between nodes. int Escape_analysis_assign::expression(Expression** pexpr) { Gogo* gogo = this->context_->gogo(); int debug_level = gogo->debug_escape_level(); // Big stuff escapes unconditionally. Node* n = Node::make_node(*pexpr); if ((n->encoding() & ESCAPE_MASK) != int(Node::ESCAPE_HEAP) && n->is_big(this->context_)) { if (debug_level > 1) go_inform((*pexpr)->location(), "too large for stack"); n->set_encoding(Node::ESCAPE_HEAP); (*pexpr)->address_taken(true); this->assign(this->context_->sink(), n); } if ((*pexpr)->func_expression() == NULL) (*pexpr)->traverse_subexpressions(this); if (debug_level > 1) { Node* n = Node::make_node(*pexpr); std::string fn_name = this->context_->current_function_name(); go_inform((*pexpr)->location(), "[%d] %s esc: %s", this->context_->loop_depth(), fn_name.c_str(), n->ast_format(gogo).c_str()); } switch ((*pexpr)->classification()) { case Expression::EXPRESSION_CALL: { Call_expression* call = (*pexpr)->call_expression(); this->call(call); Func_expression* fe = call->fn()->func_expression(); if (fe != NULL && fe->is_runtime_function()) { switch (fe->runtime_code()) { case Runtime::GOPANIC: { // Argument could leak through recover. Node* panic_arg = Node::make_node(call->args()->front()); this->assign(this->context_->sink(), panic_arg); } break; case Runtime::GROWSLICE: { // The contents being appended leak. if (call->is_varargs()) { Node* appended = Node::make_node(call->args()->back()); this->assign_deref(this->context_->sink(), appended); } else { for (Expression_list::const_iterator pa = call->args()->begin(); pa != call->args()->end(); ++pa) { Node* arg = Node::make_node(*pa); this->assign(this->context_->sink(), arg); } } if (debug_level > 2) go_error_at((*pexpr)->location(), "special treatment of append(slice1, slice2...)"); // The content of the original slice leaks as well. Node* appendee = Node::make_node(call->args()->front()); this->assign_deref(this->context_->sink(), appendee); } break; case Runtime::SLICECOPY: case Runtime::SLICESTRINGCOPY: case Runtime::TYPEDSLICECOPY: { // Lose track of the copied content. Node* copied = Node::make_node(call->args()->back()); this->assign_deref(this->context_->sink(), copied); } break; case Runtime::MAKECHAN: case Runtime::MAKEMAP: case Runtime::MAKESLICE: case Runtime::MAKESLICE64: case Runtime::SLICEBYTETOSTRING: case Runtime::SLICERUNETOSTRING: case Runtime::STRINGTOSLICEBYTE: case Runtime::STRINGTOSLICERUNE: case Runtime::CONCATSTRINGS: case Runtime::CONCATSTRING2: case Runtime::CONCATSTRING3: case Runtime::CONCATSTRING4: case Runtime::CONCATSTRING5: case Runtime::CONSTRUCT_MAP: case Runtime::INTSTRING: { Node* runtime_node = Node::make_node(fe); this->context_->track(runtime_node); } break; default: break; } } } break; case Expression::EXPRESSION_ALLOCATION: { // Same as above; this is Runtime::NEW. Node* alloc_node = Node::make_node(*pexpr); this->context_->track(alloc_node); } break; case Expression::EXPRESSION_CONVERSION: { Type_conversion_expression* tce = (*pexpr)->conversion_expression(); Node* tce_node = Node::make_node(tce); Node* converted = Node::make_node(tce->expr()); this->context_->track(tce_node); this->assign(tce_node, converted); } break; case Expression::EXPRESSION_FIXED_ARRAY_CONSTRUCTION: case Expression::EXPRESSION_SLICE_CONSTRUCTION: { Node* array_node = Node::make_node(*pexpr); if ((*pexpr)->slice_literal() != NULL) this->context_->track(array_node); Expression_list* vals = ((*pexpr)->slice_literal() != NULL ? (*pexpr)->slice_literal()->vals() : (*pexpr)->array_literal()->vals()); if (vals != NULL) { // Connect the array to its values. for (Expression_list::const_iterator p = vals->begin(); p != vals->end(); ++p) if ((*p) != NULL) this->assign(array_node, Node::make_node(*p)); } } break; case Expression::EXPRESSION_STRUCT_CONSTRUCTION: { Node* struct_node = Node::make_node(*pexpr); Expression_list* vals = (*pexpr)->struct_literal()->vals(); if (vals != NULL) { // Connect the struct to its values. for (Expression_list::const_iterator p = vals->begin(); p != vals->end(); ++p) { if ((*p) != NULL) this->assign(struct_node, Node::make_node(*p)); } } } break; case Expression::EXPRESSION_HEAP: { Node* pointer_node = Node::make_node(*pexpr); Node* lit_node = Node::make_node((*pexpr)->heap_expression()->expr()); this->context_->track(pointer_node); // Connect pointer node to literal node; if the pointer node escapes, so // does the literal node. this->assign(pointer_node, lit_node); } break; case Expression::EXPRESSION_BOUND_METHOD: { Node* bound_node = Node::make_node(*pexpr); this->context_->track(bound_node); Expression* obj = (*pexpr)->bound_method_expression()->first_argument(); Node* obj_node = Node::make_node(obj); // A bound method implies the receiver will be used outside of the // lifetime of the method in some way. We lose track of the receiver. this->assign(this->context_->sink(), obj_node); } break; case Expression::EXPRESSION_MAP_CONSTRUCTION: { Map_construction_expression* mce = (*pexpr)->map_literal(); Node* map_node = Node::make_node(mce); this->context_->track(map_node); // All keys and values escape to memory. if (mce->vals() != NULL) { for (Expression_list::const_iterator p = mce->vals()->begin(); p != mce->vals()->end(); ++p) { if ((*p) != NULL) this->assign(this->context_->sink(), Node::make_node(*p)); } } } break; case Expression::EXPRESSION_FUNC_REFERENCE: { Func_expression* fe = (*pexpr)->func_expression(); if (fe->closure() != NULL) { // Connect captured variables to the closure. Node* closure_node = Node::make_node(fe); this->context_->track(closure_node); // A closure expression already exists as the heap expression: // &struct{f func_code, v []*Variable}{...}. // Link closure to the addresses of the variables enclosed. Heap_expression* he = fe->closure()->heap_expression(); Struct_construction_expression* sce = he->expr()->struct_literal(); // First field is function code, other fields are variable // references. Expression_list::const_iterator p = sce->vals()->begin(); ++p; for (; p != sce->vals()->end(); ++p) { Node* enclosed_node = Node::make_node(*p); Node::Escape_state* state = enclosed_node->state(this->context_, NULL); state->loop_depth = this->context_->loop_depth(); this->assign(closure_node, enclosed_node); } } } break; case Expression::EXPRESSION_UNARY: { if ((*pexpr)->unary_expression()->op() != OPERATOR_AND) break; Node* addr_node = Node::make_node(*pexpr); this->context_->track(addr_node); Expression* operand = (*pexpr)->unary_expression()->operand(); Named_object* var = NULL; if (operand->var_expression() != NULL) var = operand->var_expression()->named_object(); else if (operand->enclosed_var_expression() != NULL) var = operand->enclosed_var_expression()->variable(); else if (operand->temporary_reference_expression() != NULL) { // Found in runtime/chanbarrier_test.go. The address of a struct // reference is usually a heap expression, except when it is a part // of a case statement. In that case, it is lowered into a // temporary reference and never linked to the heap expression that // initializes it. In general, when taking the address of some // temporary, the analysis should really be looking at the initial // value of that temporary. Temporary_reference_expression* tre = operand->temporary_reference_expression(); if (tre->statement() != NULL && tre->statement()->temporary_statement()->init() != NULL) { Expression* init = tre->statement()->temporary_statement()->init(); Node* init_node = Node::make_node(init); this->assign(addr_node, init_node); } } if (var == NULL) break; if (var->is_variable() && !var->var_value()->is_parameter()) { // For &x, use the loop depth of x if known. Node::Escape_state* addr_state = addr_node->state(this->context_, NULL); Node* operand_node = Node::make_node(operand); Node::Escape_state* operand_state = operand_node->state(this->context_, NULL); if (operand_state->loop_depth != 0) addr_state->loop_depth = operand_state->loop_depth; } else if ((var->is_variable() && var->var_value()->is_parameter()) || var->is_result_variable()) { Node::Escape_state* addr_state = addr_node->state(this->context_, NULL); addr_state->loop_depth = 1; } } break; default: break; } return TRAVERSE_SKIP_COMPONENTS; } // Model calls within a function as assignments and flows between arguments // and results. void Escape_analysis_assign::call(Call_expression* call) { Gogo* gogo = this->context_->gogo(); int debug_level = gogo->debug_escape_level(); Func_expression* fn = call->fn()->func_expression(); Function_type* fntype = call->get_function_type(); bool indirect = false; // Interface method calls or closure calls are indirect calls. if (fntype == NULL || (fntype->is_method() && fntype->receiver()->type()->interface_type() != NULL) || fn == NULL || (fn->named_object()->is_function() && fn->named_object()->func_value()->enclosing() != NULL)) indirect = true; Node* call_node = Node::make_node(call); std::vector arg_nodes; if (call->fn()->interface_field_reference_expression() != NULL) { Interface_field_reference_expression* ifre = call->fn()->interface_field_reference_expression(); Node* field_node = Node::make_node(ifre->expr()); arg_nodes.push_back(field_node); } if (call->args() != NULL) { for (Expression_list::const_iterator p = call->args()->begin(); p != call->args()->end(); ++p) arg_nodes.push_back(Node::make_node(*p)); } if (indirect) { // We don't know what happens to the parameters through indirect calls. // Be conservative and assume they all flow to theSink. for (std::vector::iterator p = arg_nodes.begin(); p != arg_nodes.end(); ++p) { if (debug_level > 2) go_inform(call->location(), "esccall:: indirect call <- %s, untracked", (*p)->ast_format(gogo).c_str()); this->assign(this->context_->sink(), *p); } this->context_->init_retvals(call_node, fntype); return; } // If FN is an untagged function. if (fn != NULL && fn->named_object()->is_function() && !fntype->is_tagged()) { if (debug_level > 2) go_inform(call->location(), "esccall:: %s in recursive group", call_node->ast_format(gogo).c_str()); Function* f = fn->named_object()->func_value(); const Bindings* callee_bindings = f->block()->bindings(); const Typed_identifier_list* results = fntype->results(); if (results != NULL) { // Setup output list on this call node. Node::Escape_state* state = call_node->state(this->context_, NULL); for (Typed_identifier_list::const_iterator p1 = results->begin(); p1 != results->end(); ++p1) { if (p1->name().empty() || Gogo::is_sink_name(p1->name())) continue; Named_object* result_no = callee_bindings->lookup_local(p1->name()); go_assert(result_no != NULL); Node* result_node = Node::make_node(result_no); state->retvals.push_back(result_node); } } std::vector::iterator p = arg_nodes.begin(); if (fntype->is_method() && fntype->receiver()->type()->has_pointer()) { std::string rcvr_name = fntype->receiver()->name(); if (rcvr_name.empty() || Gogo::is_sink_name(rcvr_name)) ; else { Named_object* rcvr_no = callee_bindings->lookup_local(fntype->receiver()->name()); go_assert(rcvr_no != NULL); Node* rcvr_node = Node::make_node(rcvr_no); this->assign(rcvr_node, *p); } ++p; } const Typed_identifier_list* til = fntype->parameters(); if (til != NULL) { for (Typed_identifier_list::const_iterator p1 = til->begin(); p1 != til->end(); ++p1, ++p) { if (p1->name().empty() || Gogo::is_sink_name(p1->name())) continue; Named_object* param_no = callee_bindings->lookup_local(p1->name()); go_assert(param_no != NULL); Expression* arg = (*p)->expr(); if (arg->var_expression() != NULL && arg->var_expression()->named_object() == param_no) continue; Node* param_node = Node::make_node(param_no); this->assign(param_node, *p); } for (; p != arg_nodes.end(); ++p) { if (debug_level > 2) go_inform(call->location(), "esccall:: ... <- %s, untracked", (*p)->ast_format(gogo).c_str()); this->assign(this->context_->sink(), *p); } } return; } if (debug_level > 2) go_inform(call->location(), "esccall:: %s not recursive", call_node->ast_format(gogo).c_str()); Node::Escape_state* call_state = call_node->state(this->context_, NULL); if (!call_state->retvals.empty()) go_error_at(Linemap::unknown_location(), "esc already decorated call %s", call_node->ast_format(gogo).c_str()); this->context_->init_retvals(call_node, fntype); // Receiver. std::vector::iterator p = arg_nodes.begin(); if (fntype->is_method() && fntype->receiver()->type()->has_pointer() && p != arg_nodes.end()) { // First argument to call will be the receiver. std::string* note = fntype->receiver()->note(); if (fntype->receiver()->type()->points_to() == NULL && (*p)->expr()->unary_expression() != NULL && (*p)->expr()->unary_expression()->op() == OPERATOR_AND) { // This is a call to a value method that has been lowered into a call // to a pointer method. Gccgo generates a pointer method for all // method calls and takes the address of the value passed as the // receiver then immediately dereferences it within the function. // In this case, the receiver does not escape. } else { if (!Type::are_identical(fntype->receiver()->type(), (*p)->expr()->type(), true, NULL)) { // This will be converted later, preemptively track it instead // of its conversion expression which will show up in a later pass. this->context_->track(*p); } this->assign_from_note(note, call_state->retvals, *p); } p++; } const Typed_identifier_list* til = fntype->parameters(); if (til != NULL) { for (Typed_identifier_list::const_iterator pn = til->begin(); pn != til->end() && p != arg_nodes.end(); ++pn, ++p) { if (!Type::are_identical(pn->type(), (*p)->expr()->type(), true, NULL)) { // This will be converted later, preemptively track it instead // of its conversion expression which will show up in a later pass. this->context_->track(*p); } // TODO(cmang): Special care for varargs parameter? Type* t = pn->type(); if (t != NULL && t->has_pointer()) { std::string* note = pn->note(); int enc = this->assign_from_note(note, call_state->retvals, *p); if (enc == Node::ESCAPE_NONE && (call->is_deferred() || call->is_concurrent())) { // TODO(cmang): Mark the argument as strictly non-escaping. } } } for (; p != arg_nodes.end(); ++p) { if (debug_level > 2) go_inform(call->location(), "esccall:: ... <- %s, untracked", (*p)->ast_format(gogo).c_str()); this->assign(this->context_->sink(), *p); } } } // Model the assignment of DST to SRC. // Assert that SRC somehow gets assigned to DST. // DST might need to be examined for evaluations that happen inside of it. // For example, in [DST]*f(x) = [SRC]y, we lose track of the indirection and // DST becomes the sink in our model. void Escape_analysis_assign::assign(Node* dst, Node* src) { Gogo* gogo = this->context_->gogo(); int debug_level = gogo->debug_escape_level(); if (debug_level > 1) go_inform(dst->location(), "[%d] %s escassign: %s(%s)[%s] = %s(%s)[%s]", this->context_->loop_depth(), strip_packed_prefix(gogo, this->context_->current_function_name()).c_str(), dst->ast_format(gogo).c_str(), dst->details().c_str(), dst->op_format().c_str(), src->ast_format(gogo).c_str(), src->details().c_str(), src->op_format().c_str()); if (dst->expr() != NULL) { // Analyze the lhs of the assignment. // Replace DST with this->context_->sink() if we can't track it. Expression* e = dst->expr(); switch (e->classification()) { case Expression::EXPRESSION_VAR_REFERENCE: { // If DST is a global variable, we have no way to track it. Named_object* var = e->var_expression()->named_object(); if (var->is_variable() && var->var_value()->is_global()) dst = this->context_->sink(); } break; case Expression::EXPRESSION_FIELD_REFERENCE: { Expression* strct = e->field_reference_expression()->expr(); if (strct->heap_expression() != NULL) { // When accessing the field of a struct reference, we lose // track of the indirection. dst = this->context_->sink(); break; } // Treat DST.x = SRC as if it were DST = SRC. Node* struct_node = Node::make_node(strct); this->assign(struct_node, src); return; } case Expression::EXPRESSION_ARRAY_INDEX: { Array_index_expression* are = e->array_index_expression(); if (!are->array()->type()->is_slice_type()) { // Treat DST[i] = SRC as if it were DST = SRC if DST if a fixed // array. Node* array_node = Node::make_node(are->array()); this->assign(array_node, src); return; } // Lose track of the slice dereference. dst = this->context_->sink(); } break; case Expression::EXPRESSION_UNARY: // Lose track of the dereference. if (e->unary_expression()->op() == OPERATOR_MULT) dst = this->context_->sink(); break; case Expression::EXPRESSION_MAP_INDEX: { // Lose track of the map's key and value. Expression* index = e->map_index_expression()->index(); Node* index_node = Node::make_node(index); this->assign(this->context_->sink(), index_node); dst = this->context_->sink(); } break; default: // TODO(cmang): Add debugging info here: only a few expressions // should leave DST unmodified. break; } } if (src->expr() != NULL) { Expression* e = src->expr(); switch (e->classification()) { case Expression::EXPRESSION_VAR_REFERENCE: // DST = var case Expression::EXPRESSION_HEAP: // DST = &T{...}. case Expression::EXPRESSION_FIXED_ARRAY_CONSTRUCTION: case Expression::EXPRESSION_SLICE_CONSTRUCTION: // DST = [...]T{...}. case Expression::EXPRESSION_MAP_CONSTRUCTION: // DST = map[T]V{...}. case Expression::EXPRESSION_STRUCT_CONSTRUCTION: // DST = T{...}. case Expression::EXPRESSION_ALLOCATION: // DST = new(T). case Expression::EXPRESSION_BOUND_METHOD: // DST = x.M. this->flows(dst, src); break; case Expression::EXPRESSION_UNSAFE_CONVERSION: { Expression* underlying = e->unsafe_conversion_expression()->expr(); Node* underlying_node = Node::make_node(underlying); this->assign(dst, underlying_node); } break; case Expression::EXPRESSION_ENCLOSED_VAR_REFERENCE: { Named_object* var = e->enclosed_var_expression()->variable(); Node* var_node = Node::make_node(var); this->flows(dst, var_node); } break; case Expression::EXPRESSION_CALL: { Call_expression* call = e->call_expression(); Func_expression* fe = call->fn()->func_expression(); if (fe != NULL && fe->is_runtime_function()) { switch (fe->runtime_code()) { case Runtime::GROWSLICE: { // Append returns the first argument. // The subsequent arguments are already leaked because // they are operands to append. Node* appendee = Node::make_node(call->args()->front()); this->assign(dst, appendee); break; } case Runtime::MAKECHAN: case Runtime::MAKEMAP: case Runtime::MAKESLICE: case Runtime::MAKESLICE64: // DST = make(...). case Runtime::SLICEBYTETOSTRING: // DST = string([]byte{...}). case Runtime::SLICERUNETOSTRING: // DST = string([]int{...}). case Runtime::STRINGTOSLICEBYTE: // DST = []byte(str). case Runtime::STRINGTOSLICERUNE: // DST = []rune(str). case Runtime::CONCATSTRINGS: case Runtime::CONCATSTRING2: case Runtime::CONCATSTRING3: case Runtime::CONCATSTRING4: case Runtime::CONCATSTRING5: // DST = str1 + str2 case Runtime::CONSTRUCT_MAP: // When building a map literal's backend representation. // Likely never seen here and covered in // Expression::EXPRESSION_MAP_CONSTRUCTION. case Runtime::INTSTRING: // DST = string(i). case Runtime::IFACEE2E2: case Runtime::IFACEI2E2: case Runtime::IFACEE2I2: case Runtime::IFACEI2I2: case Runtime::IFACEE2T2P: case Runtime::IFACEI2T2P: case Runtime::IFACEE2T2: case Runtime::IFACEI2T2: case Runtime::REQUIREITAB: // All versions of interface conversion that might result // from a type assertion. Some of these are the result of // a tuple type assertion statement and may not be covered // by the case in Expression::EXPRESSION_CONVERSION or // Expression::EXPRESSION_TYPE_GUARD. this->flows(dst, src); break; default: break; } break; } else if (fe != NULL && fe->named_object()->is_function() && fe->named_object()->func_value()->is_method() && (call->is_deferred() || call->is_concurrent())) { // For a method call thunk, lose track of the call and treat it // as if DST = RECEIVER. Node* rcvr_node = Node::make_node(call->args()->front()); this->assign(dst, rcvr_node); break; } // TODO(cmang): Handle case from issue 4529. // Node* call_node = Node::make_node(e); // Node::Escape_state* call_state = call_node->state(this->context_, NULL); // std::vector retvals = call_state->retvals; // for (std::vector::const_iterator p = retvals.begin(); // p != retvals.end(); // ++p) // this->flows(dst, *p); } break; case Expression::EXPRESSION_FUNC_REFERENCE: if (e->func_expression()->closure() != NULL) { // If SRC is a reference to a function closure, DST flows into // the underyling closure variable. Expression* closure = e->func_expression()->closure(); Node* closure_node = Node::make_node(closure); this->flows(dst, closure_node); } break; case Expression::EXPRESSION_FIELD_REFERENCE: { // A non-pointer can't escape from a struct. if (!e->type()->has_pointer()) break; } // Fall through. case Expression::EXPRESSION_CONVERSION: case Expression::EXPRESSION_TYPE_GUARD: case Expression::EXPRESSION_ARRAY_INDEX: case Expression::EXPRESSION_STRING_INDEX: { Expression* left = NULL; if (e->field_reference_expression() != NULL) { left = e->field_reference_expression()->expr(); if (left->unary_expression() != NULL && left->unary_expression()->op() == OPERATOR_MULT) { // DST = (*x).f this->flows(dst, src); break; } } else if (e->conversion_expression() != NULL) left = e->conversion_expression()->expr(); else if (e->type_guard_expression() != NULL) left = e->type_guard_expression()->expr(); else if (e->array_index_expression() != NULL) { Array_index_expression* aie = e->array_index_expression(); if (e->type()->is_slice_type()) left = aie->array(); else if (!aie->array()->type()->is_slice_type()) { // Indexing an array preserves the input value. Node* array_node = Node::make_node(aie->array()); this->assign(dst, array_node); break; } else { this->flows(dst, src); break; } } else if (e->string_index_expression() != NULL) { String_index_expression* sie = e->string_index_expression(); if (e->type()->is_slice_type()) left = sie->string(); else if (!sie->string()->type()->is_slice_type()) { // Indexing a string preserves the input value. Node* string_node = Node::make_node(sie->string()); this->assign(dst, string_node); break; } else { this->flows(dst, src); break; } } go_assert(left != NULL); // Conversions, field access, and slicing all preserve the input // value. Node* left_node = Node::make_node(left); this->assign(dst, left_node); } break; case Expression::EXPRESSION_BINARY: { switch (e->binary_expression()->op()) { case OPERATOR_PLUS: case OPERATOR_MINUS: case OPERATOR_XOR: case OPERATOR_MULT: case OPERATOR_DIV: case OPERATOR_MOD: case OPERATOR_LSHIFT: case OPERATOR_RSHIFT: case OPERATOR_AND: case OPERATOR_BITCLEAR: { Node* left = Node::make_node(e->binary_expression()->left()); this->assign(dst, left); Node* right = Node::make_node(e->binary_expression()->right()); this->assign(dst, right); } break; default: break; } } break; case Expression::EXPRESSION_UNARY: { switch (e->unary_expression()->op()) { case OPERATOR_PLUS: case OPERATOR_MINUS: case OPERATOR_XOR: { Node* op_node = Node::make_node(e->unary_expression()->operand()); this->assign(dst, op_node); } break; case OPERATOR_MULT: // DST = *x case OPERATOR_AND: // DST = &x this->flows(dst, src); break; default: break; } } break; case Expression::EXPRESSION_TEMPORARY_REFERENCE: { Statement* temp = e->temporary_reference_expression()->statement(); if (temp != NULL && temp->temporary_statement()->init() != NULL) { Expression* init = temp->temporary_statement()->init(); Node* init_node = Node::make_node(init); this->assign(dst, init_node); } } break; default: // TODO(cmang): Add debug info here; this should not be reachable. // For now, just to be conservative, we'll just say dst flows to src. break; } } } // Model the assignment of DST to an indirection of SRC. void Escape_analysis_assign::assign_deref(Node* dst, Node* src) { if (src->expr() != NULL) { switch (src->expr()->classification()) { case Expression::EXPRESSION_BOOLEAN: case Expression::EXPRESSION_STRING: case Expression::EXPRESSION_INTEGER: case Expression::EXPRESSION_FLOAT: case Expression::EXPRESSION_COMPLEX: case Expression::EXPRESSION_NIL: case Expression::EXPRESSION_IOTA: // No need to try indirections on literal values // or numeric constants. return; case Expression::EXPRESSION_FIXED_ARRAY_CONSTRUCTION: case Expression::EXPRESSION_SLICE_CONSTRUCTION: case Expression::EXPRESSION_STRUCT_CONSTRUCTION: { // Dereferencing an array, slice, or struct is like accessing each // of its values. In this situation, we model the flow from src to // dst where src is one of the above as a flow from each of src's // values to dst. Expression* e = src->expr(); Expression_list* vals = NULL; if (e->slice_literal() != NULL) vals = e->slice_literal()->vals(); else if (e->array_literal() != NULL) vals = e->array_literal()->vals(); else vals = e->struct_literal()->vals(); if (vals != NULL) { for (Expression_list::const_iterator p = vals->begin(); p != vals->end(); ++p) { if ((*p) != NULL) this->assign(dst, Node::make_node(*p)); } } } return; default: break; } } this->assign(dst, this->context_->add_dereference(src)); } // Model the input-to-output assignment flow of one of a function call's // arguments, where the flow is encoded in NOTE. int Escape_analysis_assign::assign_from_note(std::string* note, const std::vector& dsts, Node* src) { int enc = Escape_note::parse_tag(note); if (src->expr() != NULL) { switch (src->expr()->classification()) { case Expression::EXPRESSION_BOOLEAN: case Expression::EXPRESSION_STRING: case Expression::EXPRESSION_INTEGER: case Expression::EXPRESSION_FLOAT: case Expression::EXPRESSION_COMPLEX: case Expression::EXPRESSION_NIL: case Expression::EXPRESSION_IOTA: // There probably isn't a note for a literal value. Literal values // usually don't escape unless we lost track of the value some how. return enc; default: break; } } if (this->context_->gogo()->debug_escape_level() > 2) go_inform(src->location(), "assignfromtag:: src= em=%s", Escape_note::make_tag(enc).c_str()); if (enc == Node::ESCAPE_UNKNOWN) { // Lost track of the value. this->assign(this->context_->sink(), src); return enc; } else if (enc == Node::ESCAPE_NONE) return enc; // If the content inside a parameter (reached via indirection) escapes to // the heap, mark it. if ((enc & ESCAPE_CONTENT_ESCAPES) != 0) this->assign(this->context_->sink(), this->context_->add_dereference(src)); int save_enc = enc; enc >>= ESCAPE_RETURN_BITS; for (std::vector::const_iterator p = dsts.begin(); enc != 0 && p != dsts.end(); ++p) { // Prefer the lowest-level path to the reference (for escape purposes). // Two-bit encoding (for example. 1, 3, and 4 bits are other options) // 01 = 0-level // 10 = 1-level, (content escapes), // 11 = 2-level, (content of content escapes). int bits = enc & ESCAPE_BITS_MASK_FOR_TAG; if (bits > 0) { Node* n = src; for (int i = 0; i < bits - 1; ++i) { // Encode level > 0 as indirections. n = this->context_->add_dereference(n); } this->assign(*p, n); } enc >>= ESCAPE_BITS_PER_OUTPUT_IN_TAG; } // If there are too many outputs to fit in the tag, that is handled on the // encoding end as ESCAPE_HEAP, so there is no need to check here. return save_enc; } // Record the flow of SRC to DST in DST. void Escape_analysis_assign::flows(Node* dst, Node* src) { // Don't bother capturing the flow from scalars. if (src->expr() != NULL && !src->expr()->type()->has_pointer()) return; // Don't confuse a blank identifier with the sink. if (dst->is_sink() && dst != this->context_->sink()) return; Node::Escape_state* dst_state = dst->state(this->context_, NULL); Node::Escape_state* src_state = src->state(this->context_, NULL); if (dst == src || dst_state == src_state || dst_state->flows.find(src) != dst_state->flows.end() || src_state->flows.find(dst) != src_state->flows.end()) return; Gogo* gogo = this->context_->gogo(); if (gogo->debug_escape_level() > 2) go_inform(Linemap::unknown_location(), "flows:: %s <- %s", dst->ast_format(gogo).c_str(), src->ast_format(gogo).c_str()); if (dst_state->flows.empty()) this->context_->add_dst(dst); dst_state->flows.insert(src); } // Build a connectivity graph between nodes in the function being analyzed. void Gogo::assign_connectivity(Escape_context* context, Named_object* fn) { // Must be defined outside of this package. if (!fn->is_function()) return; int save_depth = context->loop_depth(); context->set_loop_depth(1); Escape_analysis_assign ea(context, fn); Function::Results* res = fn->func_value()->result_variables(); if (res != NULL) { for (Function::Results::const_iterator p = res->begin(); p != res->end(); ++p) { Node* res_node = Node::make_node(*p); Node::Escape_state* res_state = res_node->state(context, fn); res_state->loop_depth = 0; // If this set of functions is recursive, we lose track of the return values. // Just say that the result flows to the sink. if (context->recursive()) ea.flows(context->sink(), res_node); } } const Bindings* callee_bindings = fn->func_value()->block()->bindings(); Function_type* fntype = fn->func_value()->type(); Typed_identifier_list* params = (fntype->parameters() != NULL ? fntype->parameters()->copy() : new Typed_identifier_list); if (fntype->receiver() != NULL) params->push_back(*fntype->receiver()); for (Typed_identifier_list::const_iterator p = params->begin(); p != params->end(); ++p) { if (p->name().empty() || Gogo::is_sink_name(p->name())) continue; Named_object* param_no = callee_bindings->lookup_local(p->name()); go_assert(param_no != NULL); Node* param_node = Node::make_node(param_no); Node::Escape_state* param_state = param_node->state(context, fn); param_state->loop_depth = 1; if (!p->type()->has_pointer()) continue; // External function? Parameters must escape unless //go:noescape is set. // TODO(cmang): Implement //go:noescape directive. if (fn->package() != NULL) param_node->set_encoding(Node::ESCAPE_HEAP); else param_node->set_encoding(Node::ESCAPE_NONE); // TODO(cmang): Track this node in no_escape list. } Escape_analysis_loop el; fn->func_value()->traverse(&el); fn->func_value()->traverse(&ea); context->set_loop_depth(save_depth); } class Escape_analysis_flood { public: Escape_analysis_flood(Escape_context* context) : context_(context) { } // Use the escape information in dst to update the escape information in src // and src's upstream. void flood(Level, Node* dst, Node* src, int); private: // The escape context for the group of functions being flooded. Escape_context* context_; }; // Whenever we hit a dereference node, the level goes up by one, and whenever // we hit an address-of, the level goes down by one. as long as we're on a // level > 0 finding an address-of just means we're following the upstream // of a dereference, so this address doesn't leak (yet). // If level == 0, it means the /value/ of this node can reach the root of this // flood so if this node is an address-of, its argument should be marked as // escaping iff its current function and loop depth are different from the // flood's root. // Once an object has been moved to the heap, all of its upstream should be // considered escaping to the global scope. // This is an implementation of gc/esc.go:escwalkBody. void Escape_analysis_flood::flood(Level level, Node* dst, Node* src, int extra_loop_depth) { // No need to flood src if it is a literal. if (src->expr() != NULL) { switch (src->expr()->classification()) { case Expression::EXPRESSION_BOOLEAN: case Expression::EXPRESSION_STRING: case Expression::EXPRESSION_INTEGER: case Expression::EXPRESSION_FLOAT: case Expression::EXPRESSION_COMPLEX: case Expression::EXPRESSION_NIL: case Expression::EXPRESSION_IOTA: return; default: break; } } Node::Escape_state* src_state = src->state(this->context_, NULL); if (src_state->flood_id == this->context_->flood_id()) { // Esclevels are vectors, do not compare as integers, // and must use "min" of old and new to guarantee // convergence. level = level.min(src_state->level); if (level == src_state->level) { // Have we been here already with an extraloopdepth, // or is the extraloopdepth provided no improvement on // what's already been seen? if (src_state->max_extra_loop_depth >= extra_loop_depth || src_state->loop_depth >= extra_loop_depth) return; src_state->max_extra_loop_depth = extra_loop_depth; } } else src_state->max_extra_loop_depth = -1; src_state->flood_id = this->context_->flood_id(); src_state->level = level; int mod_loop_depth = std::max(extra_loop_depth, src_state->loop_depth); Gogo* gogo = this->context_->gogo(); int debug_level = gogo->debug_escape_level(); if (debug_level > 1) go_inform(Linemap::unknown_location(), "escwalk: level:{%d %d} depth:%d " "op=%s %s(%s) " "scope:%s[%d] " "extraloopdepth=%d", level.value(), level.suffix_value(), this->context_->pdepth(), src->op_format().c_str(), src->ast_format(gogo).c_str(), src->details().c_str(), debug_function_name(src_state->fn).c_str(), src_state->loop_depth, extra_loop_depth); this->context_->increase_pdepth(); // Input parameter flowing into output parameter? Named_object* src_no = NULL; if (src->expr() != NULL && src->expr()->var_expression() != NULL) src_no = src->expr()->var_expression()->named_object(); else src_no = src->object(); bool src_is_param = (src_no != NULL && src_no->is_variable() && src_no->var_value()->is_parameter()); Named_object* dst_no = NULL; if (dst->expr() != NULL && dst->expr()->var_expression() != NULL) dst_no = dst->expr()->var_expression()->named_object(); else dst_no = dst->object(); bool dst_is_result = dst_no != NULL && dst_no->is_result_variable(); if (src_is_param && dst_is_result && (src->encoding() & ESCAPE_MASK) < int(Node::ESCAPE_SCOPE) && dst->encoding() != Node::ESCAPE_HEAP) { // This case handles: // 1. return in // 2. return &in // 3. tmp := in; return &tmp // 4. return *in if (debug_level != 0) { if (debug_level == 1) go_inform(src->location(), "leaking param: %s to result %s level=%d", src->ast_format(gogo).c_str(), dst->ast_format(gogo).c_str(), level.value()); else go_inform(src->location(), "leaking param: %s to result %s level={%d %d}", src->ast_format(gogo).c_str(), dst->ast_format(gogo).c_str(), level.value(), level.suffix_value()); } if ((src->encoding() & ESCAPE_MASK) != Node::ESCAPE_RETURN) { int enc = Node::ESCAPE_RETURN | (src->encoding() & ESCAPE_CONTENT_ESCAPES); src->set_encoding(enc); } int enc = Node::note_inout_flows(src->encoding(), dst_no->result_var_value()->index(), level); src->set_encoding(enc); // In gc/esc.go:escwalkBody, this is a goto to the label for recursively // flooding the connection graph. Inlined here for convenience. level = level.copy(); for (std::set::const_iterator p = src_state->flows.begin(); p != src_state->flows.end(); ++p) this->flood(level, dst, *p, extra_loop_depth); return; } // If parameter content escape to heap, set ESCAPE_CONTENT_ESCAPES. // Note minor confusion around escape from pointer-to-struct vs // escape from struct. if (src_is_param && dst->encoding() == Node::ESCAPE_HEAP && (src->encoding() & ESCAPE_MASK) < int(Node::ESCAPE_SCOPE) && level.value() > 0) { int enc = Node::max_encoding((src->encoding() | ESCAPE_CONTENT_ESCAPES), Node::ESCAPE_NONE); src->set_encoding(enc); if (debug_level != 0) go_inform(src->location(), "mark escaped content: %s", src->ast_format(gogo).c_str()); } // A src object leaks if its value or address is assigned to a dst object // in a different scope (at a different loop depth). Node::Escape_state* dst_state = dst->state(this->context_, NULL); bool src_leaks = (level.value() <= 0 && level.suffix_value() <= 0 && dst_state->loop_depth < mod_loop_depth); if (src_is_param && (src_leaks || dst_state->loop_depth < 0) && (src->encoding() & ESCAPE_MASK) < int(Node::ESCAPE_SCOPE)) { if (level.suffix_value() > 0) { int enc = Node::max_encoding((src->encoding() | ESCAPE_CONTENT_ESCAPES), Node::ESCAPE_NONE); src->set_encoding(enc); if (debug_level != 0) go_inform(src->location(), "leaking param content: %s", src->ast_format(gogo).c_str()); } else { if (debug_level != 0) go_inform(src->location(), "leaking param"); src->set_encoding(Node::ESCAPE_SCOPE); } } else if (src->expr() != NULL) { Expression* e = src->expr(); if (e->enclosed_var_expression() != NULL) { if (src_leaks && debug_level != 0) go_inform(src->location(), "leaking closure reference %s", src->ast_format(gogo).c_str()); Node* enclosed_node = Node::make_node(e->enclosed_var_expression()->variable()); this->flood(level, dst, enclosed_node, -1); } else if (e->heap_expression() != NULL || (e->unary_expression() != NULL && e->unary_expression()->op() == OPERATOR_AND)) { // Pointer literals and address-of expressions. Expression* underlying; if (e->heap_expression()) underlying = e->heap_expression()->expr(); else underlying = e->unary_expression()->operand(); Node* underlying_node = Node::make_node(underlying); // If the address leaks, the underyling object must be moved // to the heap. underlying->address_taken(src_leaks); if (src_leaks) { src->set_encoding(Node::ESCAPE_HEAP); if (debug_level != 0) { go_inform(underlying->location(), "moved to heap: %s", underlying_node->ast_format(gogo).c_str()); if (debug_level > 1) go_inform(src->location(), "%s escapes to heap, level={%d %d}, " "dst.eld=%d, src.eld=%d", src->ast_format(gogo).c_str(), level.value(), level.suffix_value(), dst_state->loop_depth, mod_loop_depth); else go_inform(src->location(), "%s escapes to heap", src->ast_format(gogo).c_str()); } this->flood(level.decrease(), dst, underlying_node, mod_loop_depth); extra_loop_depth = mod_loop_depth; } else { // Decrease the level each time we take the address of the object. this->flood(level.decrease(), dst, underlying_node, -1); } } else if (e->slice_literal() != NULL) { Slice_construction_expression* slice = e->slice_literal(); if (slice->vals() != NULL) { for (Expression_list::const_iterator p = slice->vals()->begin(); p != slice->vals()->end(); ++p) { if ((*p) != NULL) this->flood(level.decrease(), dst, Node::make_node(*p), -1); } } if (src_leaks) { src->set_encoding(Node::ESCAPE_HEAP); if (debug_level != 0) go_inform(src->location(), "%s escapes to heap", src->ast_format(gogo).c_str()); extra_loop_depth = mod_loop_depth; } } else if (e->call_expression() != NULL) { Call_expression* call = e->call_expression(); if (call->fn()->func_expression() != NULL) { Func_expression* func = call->fn()->func_expression(); if (func->is_runtime_function()) { switch (func->runtime_code()) { case Runtime::GROWSLICE: { // Propagate escape information to appendee. Expression* appendee = call->args()->front(); this->flood(level, dst, Node::make_node(appendee), -1); } break; case Runtime::MAKECHAN: case Runtime::MAKEMAP: case Runtime::MAKESLICE: case Runtime::MAKESLICE64: case Runtime::SLICEBYTETOSTRING: case Runtime::SLICERUNETOSTRING: case Runtime::STRINGTOSLICEBYTE: case Runtime::STRINGTOSLICERUNE: case Runtime::CONCATSTRINGS: case Runtime::CONCATSTRING2: case Runtime::CONCATSTRING3: case Runtime::CONCATSTRING4: case Runtime::CONCATSTRING5: case Runtime::CONSTRUCT_MAP: case Runtime::INTSTRING: case Runtime::REQUIREITAB: // All runtime calls that involve allocation of memory // except new. Runtime::NEW gets lowered into an // allocation expression. if (src_leaks) { src->set_encoding(Node::ESCAPE_HEAP); if (debug_level != 0) go_inform(src->location(), "%s escapes to heap", src->ast_format(gogo).c_str()); extra_loop_depth = mod_loop_depth; } break; default: break; } } else if (src_leaks && (func->closure() != NULL || func->bound_method_expression() != NULL)) { // A closure or bound method; we lost track of actual function // so if this leaks, this call must be done on the heap. src->set_encoding(Node::ESCAPE_HEAP); if (debug_level != 0) go_inform(src->location(), "%s escapes to heap", src->ast_format(gogo).c_str()); } } } else if (e->allocation_expression() != NULL && src_leaks) { // Calls to Runtime::NEW get lowered into an allocation expression. src->set_encoding(Node::ESCAPE_HEAP); if (debug_level != 0) go_inform(src->location(), "%s escapes to heap", src->ast_format(gogo).c_str()); } else if ((e->field_reference_expression() != NULL && e->field_reference_expression()->expr()->unary_expression() == NULL) || e->type_guard_expression() != NULL || (e->array_index_expression() != NULL && e->type()->is_slice_type()) || (e->string_index_expression() != NULL && e->type()->is_slice_type())) { Expression* underlying; if (e->field_reference_expression() != NULL) underlying = e->field_reference_expression()->expr(); else if (e->type_guard_expression() != NULL) underlying = e->type_guard_expression()->expr(); else if (e->array_index_expression() != NULL) underlying = e->array_index_expression()->array(); else underlying = e->string_index_expression()->string(); Node* underlying_node = Node::make_node(underlying); this->flood(level, dst, underlying_node, -1); } else if ((e->field_reference_expression() != NULL && e->field_reference_expression()->expr()->unary_expression() != NULL) || e->array_index_expression() != NULL || e->map_index_expression() != NULL || (e->unary_expression() != NULL && e->unary_expression()->op() == OPERATOR_MULT)) { Expression* underlying; if (e->field_reference_expression() != NULL) { underlying = e->field_reference_expression()->expr(); underlying = underlying->unary_expression()->operand(); } else if (e->array_index_expression() != NULL) { underlying = e->array_index_expression()->array(); if (!underlying->type()->is_slice_type()) { Node* underlying_node = Node::make_node(underlying); this->flood(level, dst, underlying_node, 1); } } else if (e->map_index_expression() != NULL) underlying = e->map_index_expression()->map(); else underlying = e->unary_expression()->operand(); // Increase the level for a dereference. Node* underlying_node = Node::make_node(underlying); this->flood(level.increase(), dst, underlying_node, -1); } // TODO(cmang): Add case for Issue #10466. } level = level.copy(); for (std::set::const_iterator p = src_state->flows.begin(); p != src_state->flows.end(); ++p) this->flood(level, dst, *p, extra_loop_depth); this->context_->decrease_pdepth(); } // Propagate escape information across the nodes modeled in this Analysis_set. // This is an implementation of gc/esc.go:escflood. void Gogo::propagate_escape(Escape_context* context, Node* dst) { Node::Escape_state* state = dst->state(context, NULL); Gogo* gogo = context->gogo(); if (gogo->debug_escape_level() > 1) go_inform(Linemap::unknown_location(), "escflood:%d: dst %s scope:%s[%d]", context->flood_id(), dst->ast_format(gogo).c_str(), debug_function_name(state->fn).c_str(), state->loop_depth); Escape_analysis_flood eaf(context); for (std::set::const_iterator p = state->flows.begin(); p != state->flows.end(); ++p) { context->increase_flood_id(); eaf.flood(Level::From(0), dst, *p, -1); } } class Escape_analysis_tag { public: Escape_analysis_tag(Escape_context* context) : context_(context) { } // Add notes to the function's type about the escape information of its // input parameters. void tag(Named_object* fn); private: Escape_context* context_; }; void Escape_analysis_tag::tag(Named_object* fn) { // External functions are assumed unsafe // unless //go:noescape is given before the declaration. if (fn->package() != NULL || !fn->is_function()) { // TODO(cmang): Implement //go:noescape directive for external functions; // mark input parameters as not escaping. return; } Function_type* fntype = fn->func_value()->type(); Bindings* bindings = fn->func_value()->block()->bindings(); if (fntype->is_method() && !fntype->receiver()->name().empty() && !Gogo::is_sink_name(fntype->receiver()->name())) { Named_object* rcvr_no = bindings->lookup(fntype->receiver()->name()); go_assert(rcvr_no != NULL); Node* rcvr_node = Node::make_node(rcvr_no); switch ((rcvr_node->encoding() & ESCAPE_MASK)) { case Node::ESCAPE_NONE: // not touched by flood case Node::ESCAPE_RETURN: if (fntype->receiver()->type()->has_pointer()) // Don't bother tagging for scalars. fntype->add_receiver_note(rcvr_node->encoding()); break; case Node::ESCAPE_HEAP: // flooded, moved to heap. case Node::ESCAPE_SCOPE: // flooded, value leaves scope. break; default: break; } } int i = 0; if (fntype->parameters() != NULL) { const Typed_identifier_list* til = fntype->parameters(); for (Typed_identifier_list::const_iterator p = til->begin(); p != til->end(); ++p, ++i) { if (p->name().empty() || Gogo::is_sink_name(p->name())) continue; Named_object* param_no = bindings->lookup(p->name()); go_assert(param_no != NULL); Node* param_node = Node::make_node(param_no); switch ((param_node->encoding() & ESCAPE_MASK)) { case Node::ESCAPE_NONE: // not touched by flood case Node::ESCAPE_RETURN: if (p->type()->has_pointer()) // Don't bother tagging for scalars. fntype->add_parameter_note(i, param_node->encoding()); break; case Node::ESCAPE_HEAP: // flooded, moved to heap. case Node::ESCAPE_SCOPE: // flooded, value leaves scope. break; default: break; } } } fntype->set_is_tagged(); } // Tag each top-level function with escape information that will be used to // retain analysis results across imports. void Gogo::tag_function(Escape_context* context, Named_object* fn) { Escape_analysis_tag eat(context); eat.tag(fn); }