1 // escape.cc -- Go frontend escape analysis.
2
3 // Copyright 2015 The Go Authors. All rights reserved.
4 // Use of this source code is governed by a BSD-style
5 // license that can be found in the LICENSE file.
6
7 #include "go-system.h"
8
9 #include <fstream>
10
11 #include "go-c.h"
12 #include "go-dump.h"
13 #include "go-optimize.h"
14 #include "types.h"
15 #include "statements.h"
16 #include "expressions.h"
17 #include "dataflow.h"
18 #include "gogo.h"
19 #include "escape.h"
20
21 // Class Node.
22
Node(Node_classification classification,Named_object * object)23 Node::Node(Node_classification classification, Named_object* object)
24 : classification_(classification), object_(object)
25 {
26 // Give every node a unique ID for representation purposes.
27 static int count;
28 this->id_ = count++;
29 }
30
~Node()31 Node::~Node()
32 {
33 }
34
35 // Make a call node for FUNCTION.
36
37 Node*
make_call(Named_object * function)38 Node::make_call(Named_object* function)
39 {
40 return new Call_node(function);
41 }
42
43 // Make a connection node for OBJECT.
44
45 Node*
make_connection(Named_object * object,Escapement_lattice e)46 Node::make_connection(Named_object* object, Escapement_lattice e)
47 {
48 return new Connection_node(object, e);
49 }
50
51 // Return this node's label, which will be the name seen in the graphical
52 // representation.
53
54 const std::string&
label()55 Node::label()
56 {
57 if (this->label_.empty())
58 {
59 this->label_ = "[label=\"";
60 this->label_ += this->object_->name();
61 this->label_ += "\"]";
62 }
63 return this->label_;
64 }
65
66 // Class Call_node.
67
Call_node(Named_object * function)68 Call_node::Call_node(Named_object* function)
69 : Node(NODE_CALL, function)
70 { go_assert(function->is_function() || function->is_function_declaration()); }
71
72 const std::string&
name()73 Call_node::name()
74 {
75 if (this->get_name().empty())
76 {
77 char buf[30];
78 snprintf(buf, sizeof buf, "CallNode%d", this->id());
79 this->set_name(std::string(buf));
80 }
81 return this->get_name();
82 }
83
84 // Class Connection_node.
85
86 const std::string&
name()87 Connection_node::name()
88 {
89 if (this->get_name().empty())
90 {
91 char buf[30];
92 snprintf(buf, sizeof buf, "ConnectionNode%d", this->id());
93 this->set_name(std::string(buf));
94 }
95 return this->get_name();
96 }
97
98 const std::string&
label()99 Connection_node::label()
100 {
101 if (this->get_label().empty())
102 {
103 std::string label = "[label=\"";
104 label += this->object()->name();
105 label += "\",color=";
106 switch (this->escape_state_)
107 {
108 case ESCAPE_GLOBAL:
109 label += "red";
110 break;
111 case ESCAPE_ARG:
112 label += "blue";
113 break;
114 case ESCAPE_NONE:
115 label += "black";
116 break;
117 }
118 label += "]";
119 this->set_label(label);
120 }
121 return this->get_label();
122 }
123
124 // Dump a connection node and its edges to a dump file.
125
126 void
dump_connection(Connection_dump_context * cdc)127 Connection_node::dump_connection(Connection_dump_context* cdc)
128 {
129 cdc->write_string(this->name() + this->label());
130 cdc->write_c_string("\n");
131
132 for (std::set<Node*>::const_iterator p = this->edges().begin();
133 p != this->edges().end();
134 ++p)
135 {
136 cdc->write_string(this->name());
137 cdc->write_c_string("->");
138
139 if ((*p)->object()->is_function())
140 {
141 char buf[100];
142 snprintf(buf, sizeof buf, "dummy%d[lhead=cluster%d]",
143 (*p)->id(), (*p)->id());
144 cdc->write_c_string(buf);
145 }
146 else
147 cdc->write_string((*p)->name());
148 cdc->write_c_string("\n");
149 }
150 }
151
152 // The -fgo-dump-calls flag to activate call graph dumps in GraphViz DOT format.
153
154 Go_dump call_graph_dump_flag("calls");
155
156 // Class Call_dump_context.
157
Call_dump_context(std::ostream * out)158 Call_dump_context::Call_dump_context(std::ostream* out)
159 : ostream_(out), gogo_(NULL)
160 { }
161
162 // Dump files will be named %basename%.calls.dot
163
164 const char* kCallDumpFileExtension = ".calls.dot";
165
166 // Dump the call graph in DOT format.
167
168 void
dump(Gogo * gogo,const char * basename)169 Call_dump_context::dump(Gogo* gogo, const char* basename)
170 {
171 std::ofstream* out = new std::ofstream();
172 std::string dumpname(basename);
173 dumpname += kCallDumpFileExtension;
174 out->open(dumpname.c_str());
175
176 if (out->fail())
177 {
178 error("cannot open %s:%m, -fgo-dump-calls ignored", dumpname.c_str());
179 return;
180 }
181
182 this->gogo_ = gogo;
183 this->ostream_ = out;
184
185 this->write_string("digraph CallGraph {\n");
186 std::set<Node*> call_graph = gogo->call_graph();
187
188 // Generate GraphViz nodes for each node.
189 for (std::set<Node*>::const_iterator p = call_graph.begin();
190 p != call_graph.end();
191 ++p)
192 {
193 this->write_string((*p)->name() + (*p)->label());
194 this->write_c_string("\n");
195
196 // Generate a graphical representation of the caller-callee relationship.
197 std::set<Node*> callees = (*p)->edges();
198 for (std::set<Node*>::const_iterator ce = callees.begin();
199 ce != callees.end();
200 ++ce)
201 {
202 this->write_string((*p)->name() + "->" + (*ce)->name());
203 this->write_c_string("\n");
204 }
205 }
206 this->write_string("}");
207 out->close();
208 }
209
210 // Dump the Call Graph of the program to the dump file.
211
dump_call_graph(const char * basename)212 void Gogo::dump_call_graph(const char* basename)
213 {
214 if (::call_graph_dump_flag.is_enabled())
215 {
216 Call_dump_context cdc;
217 cdc.dump(this, basename);
218 }
219 }
220
221 // Implementation of String_dump interface.
222
223 void
write_c_string(const char * s)224 Call_dump_context::write_c_string(const char* s)
225 {
226 this->ostream() << s;
227 }
228
229 void
write_string(const std::string & s)230 Call_dump_context::write_string(const std::string& s)
231 {
232 this->ostream() << s;
233 }
234
235 // The -fgo-dump-conns flag to activate connection graph dumps in
236 // GraphViz DOT format.
237
238 Go_dump connection_graph_dump_flag("conns");
239
240 // Class Connection_dump_context.
241
Connection_dump_context(std::ostream * out)242 Connection_dump_context::Connection_dump_context(std::ostream* out)
243 : ostream_(out), gogo_(NULL)
244 { }
245
246 // Dump files will be named %basename%.conns.dot
247
248 const char* kConnectionDumpFileExtension = ".conns.dot";
249
250 // Dump the connection graph in DOT format.
251
252 void
dump(Gogo * gogo,const char * basename)253 Connection_dump_context::dump(Gogo* gogo, const char* basename)
254 {
255 std::ofstream* out = new std::ofstream();
256 std::string dumpname(basename);
257 dumpname += kConnectionDumpFileExtension;
258 out->open(dumpname.c_str());
259
260 if (out->fail())
261 {
262 error("cannot open %s:%m, -fgo-dump-conns ignored", dumpname.c_str());
263 return;
264 }
265
266 this->gogo_ = gogo;
267 this->ostream_ = out;
268
269 this->write_string("digraph ConnectionGraph {\n");
270 this->write_string("compound=true\n");
271
272 // Dump global objects.
273 std::set<Node*> globals = this->gogo_->global_connections();
274 this->write_c_string("subgraph globals{\n");
275 this->write_c_string("label=\"NonLocalGraph\"\n");
276 this->write_c_string("color=red\n");
277 for (std::set<Node*>::const_iterator p1 = globals.begin();
278 p1 != globals.end();
279 ++p1)
280 (*p1)->connection_node()->dump_connection(this);
281 this->write_c_string("}\n");
282
283 std::set<Node*> roots = this->gogo_->connection_roots();
284 for (std::set<Node*>::const_reverse_iterator p1 = roots.rbegin();
285 p1 != roots.rend();
286 ++p1)
287 {
288 std::set<Node*> objects = (*p1)->connection_node()->objects();
289
290 char buf[150];
291 snprintf(buf, sizeof buf, "subgraph cluster%d", (*p1)->id());
292 this->write_c_string(buf);
293 this->write_string("{\n");
294 snprintf(buf, sizeof buf, "dummy%d[shape=point,style=invis]\n",
295 (*p1)->id());
296 this->write_c_string(buf);
297 this->write_string("label = \"" + (*p1)->object()->name() + "\"\n");
298
299 for (std::set<Node*>::const_iterator p2 = objects.begin();
300 p2 != objects.end();
301 ++p2)
302 (*p2)->connection_node()->dump_connection(this);
303
304 this->write_string("}\n");
305 }
306 this->write_string("}");
307 out->close();
308 }
309
310 void
dump_connection_graphs(const char * basename)311 Gogo::dump_connection_graphs(const char* basename)
312 {
313 if (::connection_graph_dump_flag.is_enabled())
314 {
315 Connection_dump_context cdc;
316 cdc.dump(this, basename);
317 }
318 }
319
320 // Implementation of String_dump interface.
321
322 void
write_c_string(const char * s)323 Connection_dump_context::write_c_string(const char* s)
324 {
325 this->ostream() << s;
326 }
327
328 void
write_string(const std::string & s)329 Connection_dump_context::write_string(const std::string& s)
330 {
331 this->ostream() << s;
332 }
333
334 // A traversal class used to build a call graph for this program.
335
336 class Build_call_graph : public Traverse
337 {
338 public:
Build_call_graph(Gogo * gogo)339 Build_call_graph(Gogo* gogo)
340 : Traverse(traverse_functions
341 | traverse_expressions),
342 gogo_(gogo), current_function_(NULL)
343 { }
344
345 int
346 function(Named_object*);
347
348 int
349 expression(Expression**);
350
351 private:
352 // The IR.
353 Gogo* gogo_;
354 // The current function being traversed, for reference when traversing the
355 // function body.
356 Named_object* current_function_;
357 };
358
359 // Add each function to the call graph and then traverse each function's
360 // body to find callee functions.
361
362 int
function(Named_object * fn)363 Build_call_graph::function(Named_object* fn)
364 {
365 this->gogo_->add_call_node(fn);
366 go_assert(this->current_function_ == NULL);
367 this->current_function_ = fn;
368 fn->func_value()->traverse(this);
369 this->current_function_ = NULL;
370 return TRAVERSE_CONTINUE;
371 }
372
373 // Find function calls and add them as callees to CURRENT_FUNCTION.
374
375 int
expression(Expression ** pexpr)376 Build_call_graph::expression(Expression** pexpr)
377 {
378 if (this->current_function_ == NULL)
379 return TRAVERSE_CONTINUE;
380
381 Expression* expr = *pexpr;
382 Named_object* fn;
383 if (expr->call_expression() != NULL)
384 {
385 Func_expression* func = expr->call_expression()->fn()->func_expression();
386 if (func == NULL)
387 {
388 // This is probably a variable holding a function value or a closure.
389 return TRAVERSE_CONTINUE;
390 }
391 fn = func->named_object();
392 }
393 else if (expr->func_expression() != NULL)
394 fn = expr->func_expression()->named_object();
395 else
396 return TRAVERSE_CONTINUE;
397
398 Node* caller = this->gogo_->lookup_call_node(this->current_function_);
399 go_assert(caller != NULL);
400
401 // Create the callee here if it hasn't been seen yet. This could also be a
402 // function defined in another package.
403 Node* callee = this->gogo_->add_call_node(fn);
404 caller->add_edge(callee);
405 return TRAVERSE_CONTINUE;
406 }
407
408 // Build the call graph.
409
410 void
build_call_graph()411 Gogo::build_call_graph()
412 {
413 Build_call_graph build_calls(this);
414 this->traverse(&build_calls);
415 }
416
417 // A traversal class used to build a connection graph for each node in the
418 // call graph.
419
420 class Build_connection_graphs : public Traverse
421 {
422 public:
Build_connection_graphs(Gogo * gogo)423 Build_connection_graphs(Gogo* gogo)
424 : Traverse(traverse_variables
425 | traverse_statements),
426 gogo_(gogo), dataflow_(new Dataflow), current_function_(NULL)
427 {
428 // Collect dataflow information for this program.
429 this->dataflow_->initialize(this->gogo_);
430 }
431
432 void
set_current_function(Named_object * function)433 set_current_function(Named_object* function)
434 { this->current_function_ = function; }
435
436 int
437 variable(Named_object*);
438
439 int
440 statement(Block*, size_t*, Statement*);
441
442
443 private:
444 // Handle a call EXPR referencing OBJECT.
445 void
446 handle_call(Named_object* object, Expression* expr);
447
448 // Get the initialization values of a composite literal EXPR.
449 Expression_list*
450 get_composite_arguments(Expression* expr);
451
452 // Handle defining OBJECT as a composite literal EXPR.
453 void
454 handle_composite_literal(Named_object* object, Expression* expr);
455
456 // Handle analysis of the left and right operands of a binary expression
457 // with respect to OBJECT.
458 void
459 handle_binary(Named_object* object, Expression* expr);
460
461 // Resolve the outermost named object of EXPR if there is one.
462 Named_object*
463 resolve_var_reference(Expression* expr);
464
465 // The IR.
466 Gogo* gogo_;
467 // The Dataflow information for this program.
468 Dataflow* dataflow_;
469 // The current function whose connection graph is being built.
470 Named_object* current_function_;
471 };
472
473 // Given an expression, return the outermost Named_object that it refers to.
474 // This is used to model the simplification between assignments in our analysis.
475
476 Named_object*
resolve_var_reference(Expression * expr)477 Build_connection_graphs::resolve_var_reference(Expression* expr)
478 {
479 bool done = false;
480 Expression* orig = expr;
481 while (!done)
482 {
483 // The goal of this loop is to find the variable being referenced, p,
484 // when the expression is:
485 switch (expr->classification())
486 {
487 case Expression::EXPRESSION_UNARY:
488 // &p or *p
489 expr = expr->unary_expression()->operand();
490 break;
491
492 case Expression::EXPRESSION_ARRAY_INDEX:
493 // p[i][j]
494 expr = expr->array_index_expression()->array();
495 break;
496
497 case Expression::EXPRESSION_FIELD_REFERENCE:
498 // p.i.j
499 orig = expr;
500 expr = expr->field_reference_expression()->expr();
501 break;
502
503 case Expression::EXPRESSION_RECEIVE:
504 // <- p
505 expr = expr->receive_expression()->channel();
506 break;
507
508 case Expression::EXPRESSION_BOUND_METHOD:
509 // p.c
510 expr = expr->bound_method_expression()->first_argument();
511 break;
512
513 case Expression::EXPRESSION_CALL:
514 // p.c()
515 expr = expr->call_expression()->fn();
516 break;
517
518 case Expression::EXPRESSION_TEMPORARY_REFERENCE:
519 // This is used after lowering, so try to retrieve the original
520 // expression that might have been lowered into a temporary statement.
521 expr = expr->temporary_reference_expression()->statement()->init();
522 if (expr == NULL)
523 return NULL;
524 break;
525
526 case Expression::EXPRESSION_SET_AND_USE_TEMPORARY:
527 expr = expr->set_and_use_temporary_expression()->expression();
528 break;
529
530 case Expression::EXPRESSION_COMPOUND:
531 // p && q
532 expr = expr->compound_expression()->init();
533 break;
534
535 case Expression::EXPRESSION_CONDITIONAL:
536 // if p {
537 expr = expr->conditional_expression()->condition();
538 break;
539
540 case Expression::EXPRESSION_CONVERSION:
541 // T(p)
542 expr = expr->conversion_expression()->expr();
543 break;
544
545 case Expression::EXPRESSION_TYPE_GUARD:
546 // p.(T)
547 expr = expr->type_guard_expression()->expr();
548 break;
549
550 case Expression::EXPRESSION_UNSAFE_CONVERSION:
551 {
552 Expression* e = expr->unsafe_conversion_expression()->expr();
553 if (e->call_result_expression() != NULL
554 && e->call_result_expression()->index() == 0)
555 {
556 // a, ok := p.(T) gets lowered into a call to one of the interface
557 // to type conversion functions instead of a type guard expression.
558 // We only want to make a connection between a and p, the bool
559 // result should not escape because p escapes.
560 e = e->call_result_expression()->call();
561
562 Named_object* fn =
563 e->call_expression()->fn()->func_expression()->named_object();
564 std::string fn_name = fn->name();
565 if (fn->package() == NULL
566 && fn->is_function_declaration()
567 && !fn->func_declaration_value()->asm_name().empty())
568 {
569 if (fn_name == "ifaceI2E2"
570 || fn_name == "ifaceI2I2")
571 e = e->call_expression()->args()->at(0);
572 else if (fn_name == "ifaceE2I2"
573 || fn_name == "ifaceI2I2"
574 || fn_name == "ifaceE2T2P"
575 || fn_name == "ifaceI2T2P"
576 || fn_name == "ifaceE2T2"
577 || fn_name == "ifaceI2T2")
578 e = e->call_expression()->args()->at(1);
579 }
580 }
581 expr = e;
582 }
583 break;
584
585 default:
586 done = true;
587 break;
588 }
589 }
590
591 Var_expression* ve = expr->var_expression();
592 if (ve != NULL)
593 {
594 Named_object* no = ve->named_object();
595 go_assert(no->is_variable() || no->is_result_variable());
596
597 if (no->is_variable()
598 && no->var_value()->is_closure()
599 && this->current_function_->func_value()->needs_closure())
600 {
601 // CURRENT_FUNCTION is a closure and NO is being set to a
602 // variable in the enclosing function.
603 Named_object* closure = this->current_function_;
604
605 // If NO is a closure variable, the expression is a field
606 // reference to the enclosed variable.
607 Field_reference_expression* fre =
608 orig->deref()->field_reference_expression();
609 if (fre == NULL)
610 return NULL;
611
612 unsigned int closure_index = fre->field_index();
613 no = closure->func_value()->enclosing_var(closure_index - 1);
614 }
615 return no;
616 }
617 return NULL;
618 }
619
620 // For a call that references OBJECT, associate the OBJECT argument with the
621 // appropriate call parameter.
622
623 void
handle_call(Named_object * object,Expression * e)624 Build_connection_graphs::handle_call(Named_object* object, Expression* e)
625 {
626 // Only call expression statements are interesting
627 // e.g. 'func(var)' for which we can show var does not escape.
628 Call_expression* ce = e->call_expression();
629 if (ce == NULL)
630 return;
631 else if (ce->args() == NULL)
632 {
633 if (ce->fn()->interface_field_reference_expression() != NULL)
634 {
635 // This is a call to an interface method with no arguments. OBJECT
636 // must be the receiver and we assume it escapes.
637 Connection_node* rcvr_node =
638 this->gogo_->add_connection_node(object)->connection_node();
639 rcvr_node->set_escape_state(Node::ESCAPE_ARG);
640 }
641 return;
642 }
643
644 // If the function call that references OBJECT is unknown, we must be
645 // conservative and assume every argument escapes. A function call is unknown
646 // if it is a call to a function stored in a variable or a call to an
647 // interface method.
648 if (ce->fn()->func_expression() == NULL)
649 {
650 for (Expression_list::const_iterator arg = ce->args()->begin();
651 arg != ce->args()->end();
652 ++arg)
653 {
654 Named_object* arg_no = this->resolve_var_reference(*arg);
655 if (arg_no != NULL)
656 {
657 Connection_node* arg_node =
658 this->gogo_->add_connection_node(arg_no)->connection_node();
659 arg_node->set_escape_state(Node::ESCAPE_ARG);
660 }
661 else if ((*arg)->call_expression() != NULL)
662 this->handle_call(object, *arg);
663 }
664 return;
665 }
666
667 Named_object* callee = ce->fn()->func_expression()->named_object();
668 Function_type* fntype;
669 if (callee->is_function())
670 fntype = callee->func_value()->type();
671 else
672 fntype = callee->func_declaration_value()->type();
673
674 Node* callee_node = this->gogo_->lookup_connection_node(callee);
675 if (callee_node == NULL && callee->is_function())
676 {
677 // Might be a nested closure that hasn't been analyzed yet.
678 Named_object* currfn = this->current_function_;
679 callee_node = this->gogo_->add_connection_node(callee);
680 this->current_function_ = callee;
681 callee->func_value()->traverse(this);
682 this->current_function_ = currfn;
683 }
684
685 // First find which arguments OBJECT is to CALLEE. Given a function call,
686 // OBJECT could be an argument multiple times e.g. CALLEE(OBJECT, OBJECT).
687 // TODO(cmang): This should be done by the Dataflow analysis so we don't have
688 // to do it each time we see a function call. FIXME.
689 Expression_list* args = ce->args()->copy();
690 if (fntype->is_varargs()
691 && args->back()->slice_literal() != NULL)
692 {
693 // Is the function is varargs, the last argument is lowered into a slice
694 // containing all original arguments. We want to traverse the original
695 // arguments here.
696 Slice_construction_expression* sce = args->back()->slice_literal();
697 for (Expression_list::const_iterator p = sce->vals()->begin();
698 p != sce->vals()->end();
699 ++p)
700 {
701 if (*p != NULL)
702 args->push_back(*p);
703 }
704 }
705
706 // ARG_POSITION is just a counter used to keep track of the index in the list
707 // of arguments to this call. In a method call, the receiver will always be
708 // the first argument. When looking at the function type, it will not be the
709 // first element in the parameter list; instead, the receiver will be
710 // non-NULL. For convenience, mark the position of the receiver argument
711 // as negative.
712 int arg_position = fntype->is_method() ? -1 : 0;
713 std::list<int> positions;
714 for (Expression_list::const_iterator p = args->begin();
715 p != args->end();
716 ++p, ++arg_position)
717 {
718 Expression* arg = *p;
719
720 // An argument might be a chain of method calls, some of which are
721 // converted from value to pointer types. Just remove the unary
722 // conversion if it exists.
723 if (arg->unary_expression() != NULL)
724 arg = arg->unary_expression()->operand();
725
726 // The reference to OBJECT might be in a nested call argument.
727 if (arg->call_expression() != NULL)
728 this->handle_call(object, arg);
729
730 std::vector<Named_object*> objects;
731 if (arg->is_composite_literal()
732 || arg->heap_expression() != NULL)
733 {
734 // For a call that has a composite literal as an argument, traverse
735 // the initializers of the composite literal for extra objects to
736 // associate with a parameter in this function.
737 Expression_list* comp_args = this->get_composite_arguments(arg);
738 if (comp_args == NULL)
739 continue;
740
741 for (size_t i = 0; i < comp_args->size(); ++i)
742 {
743 Expression* comp_arg = comp_args->at(i);
744 if (comp_arg == NULL)
745 continue;
746 else if (comp_arg->is_composite_literal()
747 || comp_arg->heap_expression() != NULL)
748 {
749 // Of course, there are situations where a composite literal
750 // initialization value is also a composite literal.
751 Expression_list* nested_args =
752 this->get_composite_arguments(comp_arg);
753 if (nested_args != NULL)
754 comp_args->append(nested_args);
755 }
756
757 Named_object* no = this->resolve_var_reference(comp_arg);
758 if (no != NULL)
759 objects.push_back(no);
760 }
761 }
762 else
763 {
764 Named_object* arg_no = this->resolve_var_reference(arg);
765 if (arg_no != NULL)
766 objects.push_back(arg_no);
767 }
768
769 // There are no variables to consider for this parameter.
770 if (objects.empty())
771 continue;
772
773 for (std::vector<Named_object*>::const_iterator p1 = objects.begin();
774 p1 != objects.end();
775 ++p1)
776 {
777 // If CALLEE is defined in another package and we have imported escape
778 // information about its parameters, update the escape state of this
779 // argument appropriately. If there is no escape information for this
780 // function, we have to assume all arguments escape.
781 if (callee->package() != NULL
782 || fntype->is_builtin())
783 {
784 Node::Escapement_lattice param_escape = Node::ESCAPE_NONE;
785 if (fntype->has_escape_info())
786 {
787 if (arg_position == -1)
788 {
789 // Use the escape info from the receiver.
790 param_escape = fntype->receiver_escape_state();
791 }
792 else if (fntype->parameters() != NULL)
793 {
794 const Node::Escape_states* states =
795 fntype->parameter_escape_states();
796
797 int param_size = fntype->parameters()->size();
798 if (arg_position >= param_size)
799 {
800 go_assert(fntype->is_varargs());
801 param_escape = states->back();
802 }
803 else
804 param_escape =
805 fntype->parameter_escape_states()->at(arg_position);
806 }
807 }
808 else
809 param_escape = Node::ESCAPE_ARG;
810
811 Connection_node* arg_node =
812 this->gogo_->add_connection_node(*p1)->connection_node();
813 if (arg_node->escape_state() > param_escape)
814 arg_node->set_escape_state(param_escape);
815 }
816
817 if (*p1 == object)
818 positions.push_back(arg_position);
819 }
820 }
821
822 // If OBJECT was not found in CALLEE's arguments, OBJECT is likely a
823 // subexpression of one of the arguments e.g. CALLEE(a[OBJECT]). This call
824 // does not give any useful information about whether OBJECT escapes.
825 if (positions.empty())
826 return;
827
828 // The idea here is to associate the OBJECT in the caller context with the
829 // parameter in the callee context. This also needs to consider varargs.
830 // This only works with functions with arguments.
831 if (!callee->is_function())
832 return;
833
834 // Use the bindings in the callee to lookup the associated parameter.
835 const Bindings* callee_bindings = callee->func_value()->block()->bindings();
836
837 // Next find the corresponding named parameters in the function signature.
838 const Typed_identifier_list* params = fntype->parameters();
839 for (std::list<int>::const_iterator pos = positions.begin();
840 params != NULL && pos != positions.end();
841 ++pos)
842 {
843 std::string param_name;
844 if (*pos >= 0 && params->size() <= static_cast<size_t>(*pos))
845 {
846 // There were more arguments than there are parameters. This must be
847 // varargs and the argument corresponds to the last parameter.
848 go_assert(fntype->is_varargs());
849 param_name = params->back().name();
850 }
851 else if (*pos < 0)
852 {
853 // We adjust the recorded position of method arguments by one to
854 // account for the receiver, so *pos == -1 implies this is the
855 // receiver and this must be a method call.
856 go_assert(fntype->is_method() && fntype->receiver() != NULL);
857 param_name = fntype->receiver()->name();
858 }
859 else
860 param_name = params->at(*pos).name();
861
862 if (Gogo::is_sink_name(param_name) || param_name.empty())
863 continue;
864
865 // Get the object for the associated parameter in this binding.
866 Named_object* param_no = callee_bindings->lookup_local(param_name);
867 go_assert(param_no != NULL);
868
869 // Add an edge from ARG_NODE in the caller context to the PARAM_NODE in
870 // the callee context.
871 if (object->is_variable() && object->var_value()->is_closure())
872 {
873 int position = *pos;
874 if (fntype->is_method())
875 ++position;
876
877 // Calling a function within a closure with a closure argument.
878 // Resolve the real variable using the closure argument.
879 object = this->resolve_var_reference(ce->args()->at(position));
880 }
881
882 Node* arg_node = this->gogo_->add_connection_node(object);
883 Node* param_node = this->gogo_->add_connection_node(param_no);
884 param_node->add_edge(arg_node);
885 }
886
887 // This is a method call with one argument: the receiver.
888 if (params == NULL)
889 {
890 go_assert(positions.size() == 1);
891 std::string rcvr_name = fntype->receiver()->name();
892 if (Gogo::is_sink_name(rcvr_name) || rcvr_name.empty())
893 return;
894
895 Named_object* rcvr_no = callee_bindings->lookup_local(rcvr_name);
896 Node* arg_node = this->gogo_->add_connection_node(object);
897 Node* rcvr_node = this->gogo_->add_connection_node(rcvr_no);
898 rcvr_node->add_edge(arg_node);
899 }
900 }
901
902 // Given a composite literal expression, return the initialization values.
903 // This is used to handle situations where call and composite literal
904 // expressions have nested composite literals as arguments/initializers.
905
906 Expression_list*
get_composite_arguments(Expression * expr)907 Build_connection_graphs::get_composite_arguments(Expression* expr)
908 {
909 // A heap expression is just any expression that takes the address of a
910 // composite literal.
911 if (expr->heap_expression() != NULL)
912 expr = expr->heap_expression()->expr();
913
914 switch (expr->classification())
915 {
916 case Expression::EXPRESSION_STRUCT_CONSTRUCTION:
917 return expr->struct_literal()->vals();
918
919 case Expression::EXPRESSION_FIXED_ARRAY_CONSTRUCTION:
920 return expr->array_literal()->vals();
921
922 case Expression::EXPRESSION_SLICE_CONSTRUCTION:
923 return expr->slice_literal()->vals();
924
925 case Expression::EXPRESSION_MAP_CONSTRUCTION:
926 return expr->map_literal()->vals();
927
928 default:
929 return NULL;
930 }
931 }
932
933 // Given an OBJECT defined as a composite literal EXPR, create edges between
934 // OBJECT and all variables referenced in EXPR.
935
936 void
handle_composite_literal(Named_object * object,Expression * expr)937 Build_connection_graphs::handle_composite_literal(Named_object* object,
938 Expression* expr)
939 {
940 Expression_list* args = this->get_composite_arguments(expr);
941 if (args == NULL)
942 return;
943
944 std::vector<Named_object*> composite_args;
945 for (Expression_list::const_iterator p = args->begin();
946 p != args->end();
947 ++p)
948 {
949 if (*p == NULL)
950 continue;
951 else if ((*p)->call_expression() != NULL)
952 this->handle_call(object, *p);
953 else if ((*p)->func_expression() != NULL)
954 composite_args.push_back((*p)->func_expression()->named_object());
955 else if ((*p)->is_composite_literal()
956 || (*p)->heap_expression() != NULL)
957 this->handle_composite_literal(object, *p);
958
959 Named_object* no = this->resolve_var_reference(*p);
960 if (no != NULL)
961 composite_args.push_back(no);
962 }
963
964 Node* object_node = this->gogo_->add_connection_node(object);
965 for (std::vector<Named_object*>::const_iterator p = composite_args.begin();
966 p != composite_args.end();
967 ++p)
968 {
969 Node* arg_node = this->gogo_->add_connection_node(*p);
970 object_node->add_edge(arg_node);
971 }
972 }
973
974 // Given an OBJECT reference in a binary expression E, analyze the left and
975 // right operands for possible edges.
976
977 void
handle_binary(Named_object * object,Expression * e)978 Build_connection_graphs::handle_binary(Named_object* object, Expression* e)
979 {
980 Binary_expression* be = e->binary_expression();
981 go_assert(be != NULL);
982 Expression* left = be->left();
983 Expression* right = be->right();
984
985 if (left->call_result_expression() != NULL)
986 left = left->call_result_expression()->call();
987 if (left->call_expression() != NULL)
988 this->handle_call(object, left);
989 else if (left->binary_expression() != NULL)
990 this->handle_binary(object, left);
991 if (right->call_result_expression() != NULL)
992 right = right->call_result_expression()->call();
993 if (right->call_expression() != NULL)
994 this->handle_call(object, right);
995 else if (right->binary_expression() != NULL)
996 this->handle_binary(object, right);
997 }
998
999 // Create connection nodes for each variable in a called function.
1000
1001 int
variable(Named_object * var)1002 Build_connection_graphs::variable(Named_object* var)
1003 {
1004 Node* var_node = this->gogo_->add_connection_node(var);
1005 Node* root = this->gogo_->lookup_connection_node(this->current_function_);
1006 go_assert(root != NULL);
1007
1008 // Add VAR to the set of objects in CURRENT_FUNCTION's connection graph.
1009 root->connection_node()->add_object(var_node);
1010
1011 // A function's results always escape.
1012 if (var->is_result_variable())
1013 var_node->connection_node()->set_escape_state(Node::ESCAPE_ARG);
1014
1015 // Create edges from a variable to its definitions.
1016 const Dataflow::Defs* defs = this->dataflow_->find_defs(var);
1017 if (defs != NULL)
1018 {
1019 for (Dataflow::Defs::const_iterator p = defs->begin();
1020 p != defs->end();
1021 ++p)
1022 {
1023 Expression* def = p->val;
1024 if (def == NULL)
1025 continue;
1026
1027 if (def->conversion_expression() != NULL)
1028 def = def->conversion_expression()->expr();
1029 if (def->func_expression() != NULL)
1030 {
1031 // VAR is being defined as a function object.
1032 Named_object* fn = def->func_expression()->named_object();
1033 Node* fn_node = this->gogo_->add_connection_node(fn);
1034 var_node->add_edge(fn_node);
1035 }
1036 else if(def->is_composite_literal()
1037 || def->heap_expression() != NULL)
1038 this->handle_composite_literal(var, def);
1039
1040 Named_object* ref = this->resolve_var_reference(def);
1041 if (ref == NULL)
1042 continue;
1043
1044 Node* ref_node = this->gogo_->add_connection_node(ref);
1045 var_node->add_edge(ref_node);
1046 }
1047 }
1048
1049 // Create edges from a reference to a variable.
1050 const Dataflow::Refs* refs = this->dataflow_->find_refs(var);
1051 if (refs != NULL)
1052 {
1053 for (Dataflow::Refs::const_iterator p = refs->begin();
1054 p != refs->end();
1055 ++p)
1056 {
1057 switch (p->statement->classification())
1058 {
1059 case Statement::STATEMENT_ASSIGNMENT:
1060 {
1061 Assignment_statement* assn =
1062 p->statement->assignment_statement();
1063 Named_object* lhs_no = this->resolve_var_reference(assn->lhs());
1064 Named_object* rhs_no = this->resolve_var_reference(assn->rhs());
1065
1066 Expression* rhs = assn->rhs();
1067 if (rhs->is_composite_literal()
1068 || rhs->heap_expression() != NULL)
1069 this->handle_composite_literal(var, rhs);
1070
1071 if (rhs->call_result_expression() != NULL)
1072 {
1073 // V's initialization will be a call result if
1074 // V, V1 := call(VAR).
1075 // There are no useful edges to make from V, but we want
1076 // to make sure we handle the call that references VAR.
1077 rhs = rhs->call_result_expression()->call();
1078 }
1079 if (rhs->call_expression() != NULL)
1080 this->handle_call(var, rhs);
1081
1082 // If there is no standalone variable on the rhs, this could be a
1083 // binary expression, which isn't interesting for analysis or a
1084 // composite literal or call expression, which we handled above.
1085 // If the underlying variable on the rhs isn't VAR then it is
1086 // likely an indexing expression where VAR is the index.
1087 if(lhs_no == NULL
1088 || rhs_no == NULL
1089 || rhs_no != var)
1090 break;
1091
1092 Node* def_node = this->gogo_->add_connection_node(lhs_no);
1093 def_node->add_edge(var_node);
1094 }
1095 break;
1096
1097 case Statement::STATEMENT_SEND:
1098 {
1099 Send_statement* send = p->statement->send_statement();
1100 Named_object* chan_no = this->resolve_var_reference(send->channel());
1101 Named_object* val_no = resolve_var_reference(send->val());
1102
1103 if (chan_no == NULL || val_no == NULL)
1104 break;
1105
1106 Node* chan_node = this->gogo_->add_connection_node(chan_no);
1107 Node* val_node = this->gogo_->add_connection_node(val_no);
1108 chan_node->add_edge(val_node);
1109 }
1110 break;
1111
1112 case Statement::STATEMENT_EXPRESSION:
1113 {
1114 Expression* call = p->statement->expression_statement()->expr();
1115 if (call->call_result_expression() != NULL)
1116 call = call->call_result_expression()->call();
1117 this->handle_call(var, call);
1118 }
1119 break;
1120
1121 case Statement::STATEMENT_GO:
1122 case Statement::STATEMENT_DEFER:
1123 // Any variable referenced via a go or defer statement escapes to
1124 // a different goroutine.
1125 if (var_node->connection_node()->escape_state() > Node::ESCAPE_ARG)
1126 var_node->connection_node()->set_escape_state(Node::ESCAPE_ARG);
1127 this->handle_call(var, p->statement->thunk_statement()->call());
1128 break;
1129
1130 case Statement::STATEMENT_IF:
1131 {
1132 // If this is a reference via an if statement, it is interesting
1133 // if there is a function call in the condition. References in
1134 // the then and else blocks would be discovered in an earlier
1135 // case.
1136 If_statement* if_stmt = p->statement->if_statement();
1137 Expression* cond = if_stmt->condition();
1138 if (cond->call_expression() != NULL)
1139 this->handle_call(var, cond);
1140 else if (cond->binary_expression() != NULL)
1141 this->handle_binary(var, cond);
1142 }
1143 break;
1144
1145 case Statement::STATEMENT_VARIABLE_DECLARATION:
1146 {
1147 // VAR could be referenced as the initialization for another
1148 // variable, V e.g. V := call(VAR) or V := &T{field: VAR}.
1149 Variable_declaration_statement* decl =
1150 p->statement->variable_declaration_statement();
1151 Named_object* decl_no = decl->var();
1152 Variable* v = decl_no->var_value();
1153
1154 Expression* init = v->init();
1155 if (init == NULL)
1156 break;
1157
1158 if (init->is_composite_literal()
1159 || init->heap_expression() != NULL)
1160 {
1161 // Create edges between DECL_NO and each named object in the
1162 // composite literal.
1163 this->handle_composite_literal(decl_no, init);
1164 }
1165
1166 if (init->call_result_expression() != NULL)
1167 init = init->call_result_expression()->call();
1168 if (init->call_expression() != NULL)
1169 this->handle_call(var, init);
1170 else if (init->binary_expression() != NULL)
1171 this->handle_binary(var, init);
1172 }
1173 break;
1174
1175 case Statement::STATEMENT_TEMPORARY:
1176 {
1177 // A call to a function with mutliple results that references VAR
1178 // will be lowered into a temporary at this point. Make sure the
1179 // call that references VAR is handled.
1180 Expression* init = p->statement->temporary_statement()->init();
1181 if (init == NULL)
1182 break;
1183 else if (init->call_result_expression() != NULL)
1184 {
1185 Expression* call = init->call_result_expression()->call();
1186 this->handle_call(var, call);
1187 }
1188 }
1189
1190 default:
1191 break;
1192 }
1193 }
1194 }
1195 return TRAVERSE_CONTINUE;
1196 }
1197
1198 // Traverse statements to find interesting references that might have not
1199 // been recorded in the dataflow analysis. For example, many statements
1200 // in closures are not properly recorded during dataflow analysis. This should
1201 // handle all of the cases handled above in statements that reference a
1202 // variable. FIXME.
1203
1204 int
statement(Block *,size_t *,Statement * s)1205 Build_connection_graphs::statement(Block*, size_t*, Statement* s)
1206 {
1207 switch(s->classification())
1208 {
1209 case Statement::STATEMENT_ASSIGNMENT:
1210 {
1211 Assignment_statement* assn = s->assignment_statement();
1212 Named_object* lhs_no = this->resolve_var_reference(assn->lhs());
1213
1214 if (lhs_no == NULL)
1215 break;
1216
1217 Expression* rhs = assn->rhs();
1218 if (rhs->temporary_reference_expression() != NULL)
1219 rhs = rhs->temporary_reference_expression()->statement()->init();
1220 if (rhs == NULL)
1221 break;
1222
1223 if (rhs->call_result_expression() != NULL)
1224 rhs = rhs->call_result_expression()->call();
1225 if (rhs->call_expression() != NULL)
1226 {
1227 // It's not clear what variables we are trying to find references to
1228 // so just use the arguments to this call.
1229 Expression_list* args = rhs->call_expression()->args();
1230 if (args == NULL)
1231 break;
1232
1233 for (Expression_list::const_iterator p = args->begin();
1234 p != args->end();
1235 ++p)
1236 {
1237 Named_object* no = this->resolve_var_reference(*p);
1238 if (no != NULL) {
1239 Node* lhs_node = this->gogo_->add_connection_node(lhs_no);
1240 Node* rhs_node = this->gogo_->add_connection_node(no);
1241 lhs_node->add_edge(rhs_node);
1242 }
1243 }
1244
1245 this->handle_call(lhs_no, rhs);
1246 }
1247 else if (rhs->func_expression() != NULL)
1248 {
1249 Node* lhs_node = this->gogo_->add_connection_node(lhs_no);
1250 Named_object* fn = rhs->func_expression()->named_object();
1251 Node* fn_node = this->gogo_->add_connection_node(fn);
1252 lhs_node->add_edge(fn_node);
1253 }
1254 else
1255 {
1256 Named_object* rhs_no = this->resolve_var_reference(rhs);
1257 if (rhs_no != NULL)
1258 {
1259 Node* lhs_node = this->gogo_->add_connection_node(lhs_no);
1260 Node* rhs_node = this->gogo_->add_connection_node(rhs_no);
1261 lhs_node->add_edge(rhs_node);
1262 }
1263 }
1264 }
1265 break;
1266
1267 case Statement::STATEMENT_SEND:
1268 {
1269 Send_statement* send = s->send_statement();
1270 Named_object* chan_no = this->resolve_var_reference(send->channel());
1271 Named_object* val_no = this->resolve_var_reference(send->val());
1272
1273 if (chan_no == NULL || val_no == NULL)
1274 break;
1275
1276 Node* chan_node = this->gogo_->add_connection_node(chan_no);
1277 Node* val_node = this->gogo_->add_connection_node(val_no);
1278 chan_node->add_edge(val_node);
1279 }
1280 break;
1281
1282 case Statement::STATEMENT_EXPRESSION:
1283 {
1284 Expression* expr = s->expression_statement()->expr();
1285 if (expr->call_result_expression() != NULL)
1286 expr = expr->call_result_expression()->call();
1287 if (expr->call_expression() != NULL)
1288 {
1289 // It's not clear what variables we are trying to find references to
1290 // so just use the arguments to this call.
1291 Expression_list* args = expr->call_expression()->args();
1292 if (args == NULL)
1293 break;
1294
1295 for (Expression_list::const_iterator p = args->begin();
1296 p != args->end();
1297 ++p)
1298 {
1299 Named_object* no = this->resolve_var_reference(*p);
1300 if (no != NULL)
1301 this->handle_call(no, expr);
1302 }
1303 }
1304 }
1305 break;
1306
1307 case Statement::STATEMENT_GO:
1308 case Statement::STATEMENT_DEFER:
1309 {
1310 // Any variable referenced via a go or defer statement escapes to
1311 // a different goroutine.
1312 Expression* call = s->thunk_statement()->call();
1313 if (call->call_expression() != NULL)
1314 {
1315 // It's not clear what variables we are trying to find references to
1316 // so just use the arguments to this call.
1317 Expression_list* args = call->call_expression()->args();
1318 if (args == NULL)
1319 break;
1320
1321 for (Expression_list::const_iterator p = args->begin();
1322 p != args->end();
1323 ++p)
1324 {
1325 Named_object* no = this->resolve_var_reference(*p);
1326 if (no != NULL)
1327 this->handle_call(no, call);
1328 }
1329 }
1330 }
1331 break;
1332
1333 case Statement::STATEMENT_VARIABLE_DECLARATION:
1334 {
1335 Variable_declaration_statement* decl =
1336 s->variable_declaration_statement();
1337 Named_object* decl_no = decl->var();
1338 Variable* v = decl_no->var_value();
1339
1340 Expression* init = v->init();
1341 if (init == NULL)
1342 break;
1343
1344 if (init->is_composite_literal()
1345 || init->heap_expression() != NULL)
1346 {
1347 // Create edges between DECL_NO and each named object in the
1348 // composite literal.
1349 this->handle_composite_literal(decl_no, init);
1350 }
1351
1352 if (init->call_result_expression() != NULL)
1353 init = init->call_result_expression()->call();
1354 if (init->call_expression() != NULL)
1355 {
1356 // It's not clear what variables we are trying to find references to
1357 // so just use the arguments to this call.
1358 Expression_list* args = init->call_expression()->args();
1359 if (args == NULL)
1360 break;
1361
1362 for (Expression_list::const_iterator p = args->begin();
1363 p != args->end();
1364 ++p)
1365 {
1366 Named_object* no = this->resolve_var_reference(*p);
1367 if (no != NULL)
1368 this->handle_call(no, init);
1369 }
1370 }
1371 }
1372 break;
1373
1374 default:
1375 break;
1376 }
1377
1378 return TRAVERSE_CONTINUE;
1379 }
1380
1381 // Build the connection graphs for each function present in the call graph.
1382
1383 void
build_connection_graphs()1384 Gogo::build_connection_graphs()
1385 {
1386 Build_connection_graphs build_conns(this);
1387
1388 for (std::set<Node*>::const_iterator p = this->call_graph_.begin();
1389 p != this->call_graph_.end();
1390 ++p)
1391 {
1392 Named_object* func = (*p)->object();
1393
1394 go_assert(func->is_function() || func->is_function_declaration());
1395 Function_type* fntype;
1396 if (func->is_function())
1397 fntype = func->func_value()->type();
1398 else
1399 fntype = func->func_declaration_value()->type();
1400 if (fntype->is_builtin())
1401 continue;
1402
1403 this->add_connection_node(func);
1404 build_conns.set_current_function(func);
1405 if (func->is_function())
1406 {
1407 // A pointer receiver of a method always escapes from the method.
1408 if (fntype->is_method() &&
1409 fntype->receiver()->type()->points_to() != NULL)
1410 {
1411 const Bindings* callee_bindings =
1412 func->func_value()->block()->bindings();
1413 std::string rcvr_name = fntype->receiver()->name();
1414 if (Gogo::is_sink_name(rcvr_name) || rcvr_name.empty())
1415 return;
1416
1417 Named_object* rcvr_no = callee_bindings->lookup_local(rcvr_name);
1418 Node* rcvr_node = this->add_connection_node(rcvr_no);
1419 rcvr_node->connection_node()->set_escape_state(Node::ESCAPE_ARG);
1420 }
1421 func->func_value()->traverse(&build_conns);
1422 }
1423 }
1424 }
1425
1426 void
analyze_reachability()1427 Gogo::analyze_reachability()
1428 {
1429 std::list<Node*> worklist;
1430
1431 // Run reachability analysis on all globally escaping objects.
1432 for (std::set<Node*>::const_iterator p = this->global_connections_.begin();
1433 p != this->global_connections_.end();
1434 ++p)
1435 worklist.push_back(*p);
1436
1437 while (!worklist.empty())
1438 {
1439 Node* m = worklist.front();
1440 worklist.pop_front();
1441
1442 std::set<Node*> reachable = m->edges();
1443 if (m->object()->is_function()
1444 && m->object()->func_value()->needs_closure())
1445 {
1446 // If a closure escapes everything it closes over also escapes.
1447 Function* closure = m->object()->func_value();
1448 for (size_t i = 0; i < closure->closure_field_count(); i++)
1449 {
1450 Named_object* enclosed = closure->enclosing_var(i);
1451 Node* enclosed_node = this->lookup_connection_node(enclosed);
1452 go_assert(enclosed_node != NULL);
1453 reachable.insert(enclosed_node);
1454 }
1455 }
1456 for (std::set<Node*>::iterator n = reachable.begin();
1457 n != reachable.end();
1458 ++n)
1459 {
1460 // If an object can be reached from a node with ESCAPE_GLOBAL,
1461 // it also must ESCAPE_GLOBAL.
1462 if ((*n)->connection_node()->escape_state() != Node::ESCAPE_GLOBAL)
1463 {
1464 (*n)->connection_node()->set_escape_state(Node::ESCAPE_GLOBAL);
1465 worklist.push_back(*n);
1466 }
1467 }
1468 }
1469
1470 // Run reachability analysis on all objects that escape via arguments.
1471 for (Named_escape_nodes::const_iterator p =
1472 this->named_connection_nodes_.begin();
1473 p != this->named_connection_nodes_.end();
1474 ++p)
1475 {
1476 if (p->second->connection_node()->escape_state() < Node::ESCAPE_NONE)
1477 worklist.push_back(p->second);
1478 }
1479
1480 while (!worklist.empty())
1481 {
1482 Node* m = worklist.front();
1483 worklist.pop_front();
1484
1485 std::set<Node*> reachable = m->edges();
1486 if (m->object()->is_function()
1487 && m->object()->func_value()->needs_closure())
1488 {
1489 // If a closure escapes everything it closes over also escapes.
1490 Function* closure = m->object()->func_value();
1491 for (size_t i = 0; i < closure->closure_field_count(); i++)
1492 {
1493 Named_object* enclosed = closure->enclosing_var(i);
1494 Node* enclosed_node = this->lookup_connection_node(enclosed);
1495 go_assert(enclosed_node != NULL);
1496 reachable.insert(enclosed_node);
1497 }
1498 }
1499 for (std::set<Node*>::iterator n = reachable.begin();
1500 n != reachable.end();
1501 ++n)
1502 {
1503 // If an object can be reached from a node with ESCAPE_ARG,
1504 // it is ESCAPE_ARG or ESCAPE_GLOBAL.
1505 Node::Escapement_lattice e = m->connection_node()->escape_state();
1506 if ((*n)->connection_node()->escape_state() > e)
1507 {
1508 (*n)->connection_node()->set_escape_state(e);
1509 worklist.push_back(*n);
1510 }
1511 }
1512 }
1513 }
1514
1515 // Iterate over all functions analyzed in the analysis, recording escape
1516 // information for each receiver and parameter.
1517
1518 void
mark_escaping_signatures()1519 Gogo::mark_escaping_signatures()
1520 {
1521 for (std::set<Node*>::const_iterator p = this->call_graph_.begin();
1522 p != this->call_graph_.end();
1523 ++p)
1524 {
1525 Named_object* fn = (*p)->object();
1526 if (!fn->is_function())
1527 continue;
1528
1529 Function* func = fn->func_value();
1530 Function_type* fntype = func->type();
1531 const Bindings* bindings = func->block()->bindings();
1532
1533 // If this is a method, set the escape state of the receiver.
1534 if (fntype->is_method())
1535 {
1536 std::string rcvr_name = fntype->receiver()->name();
1537 if (rcvr_name.empty() || Gogo::is_sink_name(rcvr_name))
1538 fntype->set_receiver_escape_state(Node::ESCAPE_NONE);
1539 else
1540 {
1541 Named_object* rcvr_no = bindings->lookup_local(rcvr_name);
1542 go_assert(rcvr_no != NULL);
1543
1544 Node* rcvr_node = this->lookup_connection_node(rcvr_no);
1545 if (rcvr_node != NULL)
1546 {
1547 Node::Escapement_lattice e =
1548 rcvr_node->connection_node()->escape_state();
1549 fntype->set_receiver_escape_state(e);
1550 }
1551 else
1552 fntype->set_receiver_escape_state(Node::ESCAPE_NONE);
1553 }
1554 fntype->set_has_escape_info();
1555 }
1556
1557 const Typed_identifier_list* params = fntype->parameters();
1558 if (params == NULL)
1559 continue;
1560
1561 fntype->set_has_escape_info();
1562 Node::Escape_states* param_escape_states = new Node::Escape_states;
1563 for (Typed_identifier_list::const_iterator p1 = params->begin();
1564 p1 != params->end();
1565 ++p1)
1566 {
1567 std::string param_name = p1->name();
1568 if (param_name.empty() || Gogo::is_sink_name(param_name))
1569 param_escape_states->push_back(Node::ESCAPE_NONE);
1570 else
1571 {
1572 Named_object* param_no = bindings->lookup_local(param_name);
1573 go_assert(param_no != NULL);
1574
1575 Node* param_node = this->lookup_connection_node(param_no);
1576 if (param_node == NULL)
1577 {
1578 param_escape_states->push_back(Node::ESCAPE_NONE);
1579 continue;
1580 }
1581
1582 Node::Escapement_lattice e =
1583 param_node->connection_node()->escape_state();
1584 param_escape_states->push_back(e);
1585 }
1586 }
1587 go_assert(params->size() == param_escape_states->size());
1588 fntype->set_parameter_escape_states(param_escape_states);
1589 }
1590 }
1591
1592 class Optimize_allocations : public Traverse
1593 {
1594 public:
Optimize_allocations(Gogo * gogo)1595 Optimize_allocations(Gogo* gogo)
1596 : Traverse(traverse_variables),
1597 gogo_(gogo)
1598 { }
1599
1600 int
1601 variable(Named_object*);
1602
1603 private:
1604 // The IR.
1605 Gogo* gogo_;
1606 };
1607
1608 // The -fgo-optimize-alloc flag activates this escape analysis.
1609
1610 Go_optimize optimize_allocation_flag("allocs");
1611
1612 // Propagate escape information for each variable.
1613
1614 int
variable(Named_object * var)1615 Optimize_allocations::variable(Named_object* var)
1616 {
1617 Node* var_node = this->gogo_->lookup_connection_node(var);
1618 if (var_node == NULL
1619 || var_node->connection_node()->escape_state() != Node::ESCAPE_NONE)
1620 return TRAVERSE_CONTINUE;
1621
1622 if (var->is_variable())
1623 {
1624 var->var_value()->set_does_not_escape();
1625 if (var->var_value()->init() != NULL
1626 && var->var_value()->init()->allocation_expression() != NULL)
1627 {
1628 Allocation_expression* alloc =
1629 var->var_value()->init()->allocation_expression();
1630 alloc->set_allocate_on_stack();
1631 }
1632 }
1633
1634 return TRAVERSE_CONTINUE;
1635 }
1636
1637 // Perform escape analysis on this program and optimize allocations using
1638 // the derived information if -fgo-optimize-allocs.
1639
1640 void
optimize_allocations(const char ** filenames)1641 Gogo::optimize_allocations(const char** filenames)
1642 {
1643 if (!::optimize_allocation_flag.is_enabled() || saw_errors())
1644 return;
1645
1646 // Build call graph for this program.
1647 this->build_call_graph();
1648
1649 // Dump the call graph for this program if -fgo-dump-calls is enabled.
1650 this->dump_call_graph(filenames[0]);
1651
1652 // Build the connection graphs for this program.
1653 this->build_connection_graphs();
1654
1655 // Dump the connection graphs if -fgo-dump-connections is enabled.
1656 this->dump_connection_graphs(filenames[0]);
1657
1658 // Given the connection graphs for this program, perform a reachability
1659 // analysis to determine what objects escape.
1660 this->analyze_reachability();
1661
1662 // Propagate escape information to variables and variable initializations.
1663 Optimize_allocations optimize_allocs(this);
1664 this->traverse(&optimize_allocs);
1665
1666 // Store escape information for a function's receivers and parameters in the
1667 // function's signature for use when exporting package information.
1668 this->mark_escaping_signatures();
1669 }
1670