1 // escape.cc -- Go escape analysis (based on Go compiler algorithm).
2
3 // Copyright 2016 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 <limits>
10 #include <stack>
11 #include <sstream>
12
13 #include "gogo.h"
14 #include "types.h"
15 #include "expressions.h"
16 #include "statements.h"
17 #include "escape.h"
18 #include "lex.h"
19 #include "ast-dump.h"
20 #include "go-optimize.h"
21 #include "go-diagnostics.h"
22 #include "go-sha1.h"
23
24 // class Node.
25
26 // Return the node's type, if it makes sense for it to have one.
27
28 Type*
type() const29 Node::type() const
30 {
31 if (this->object() != NULL
32 && this->object()->is_variable())
33 return this->object()->var_value()->type();
34 else if (this->object() != NULL
35 && this->object()->is_function())
36 return this->object()->func_value()->type();
37 else if (this->expr() != NULL)
38 return this->expr()->type();
39 else if (this->is_indirect())
40 {
41 if (this->child()->type()->deref()->is_void_type())
42 // This is a void*. The referred type can be actually any type,
43 // which may also be pointer. We model it as another void*, so
44 // we don't lose pointer-ness.
45 return this->child()->type();
46 else if (this->child()->type()->is_slice_type())
47 // We model "indirect" of a slice as dereferencing its pointer
48 // field (to get element). Use element type here.
49 return this->child()->type()->array_type()->element_type();
50 else if (this->child()->type()->is_string_type())
51 return Type::lookup_integer_type("uint8");
52 else
53 return this->child()->type()->deref();
54 }
55 else if (this->statement() != NULL
56 && this->statement()->temporary_statement() != NULL)
57 return this->statement()->temporary_statement()->type();
58 else
59 return NULL;
60 }
61
62 // A helper for reporting; return this node's location.
63
64 Location
location() const65 Node::location() const
66 {
67 if (this->object() != NULL && !this->object()->is_sink())
68 return this->object()->location();
69 else if (this->expr() != NULL)
70 return this->expr()->location();
71 else if (this->statement() != NULL)
72 return this->statement()->location();
73 else if (this->is_indirect())
74 return this->child()->location();
75 else
76 return Linemap::unknown_location();
77 }
78
79 // A helper for reporting; return the location where the underlying
80 // object is defined.
81
82 Location
definition_location() const83 Node::definition_location() const
84 {
85 if (this->object() != NULL && !this->object()->is_sink())
86 {
87 Named_object* no = this->object();
88 if (no->is_variable() || no->is_result_variable())
89 return no->location();
90 }
91 else if (this->expr() != NULL)
92 {
93 Var_expression* ve = this->expr()->var_expression();
94 if (ve != NULL)
95 {
96 Named_object* no = ve->named_object();
97 if (no->is_variable() || no->is_result_variable())
98 return no->location();
99 }
100 Enclosed_var_expression* eve = this->expr()->enclosed_var_expression();
101 if (eve != NULL)
102 {
103 Named_object* no = eve->variable();
104 if (no->is_variable() || no->is_result_variable())
105 return no->location();
106 }
107 }
108 return this->location();
109 }
110
111 // To match the cmd/gc debug output, strip away the packed prefixes on functions
112 // and variable/expressions.
113
114 std::string
strip_packed_prefix(Gogo * gogo,const std::string & s)115 strip_packed_prefix(Gogo* gogo, const std::string& s)
116 {
117 std::string packed_prefix = "." + gogo->pkgpath() + ".";
118 std::string fmt = s;
119 for (size_t pos = fmt.find(packed_prefix);
120 pos != std::string::npos;
121 pos = fmt.find(packed_prefix))
122 fmt.erase(pos, packed_prefix.length());
123 return fmt;
124 }
125
126 // A helper for debugging; return this node's AST formatted string.
127 // This is an implementation of gc's Nconv with obj.FmtShort.
128
129 std::string
ast_format(Gogo * gogo) const130 Node::ast_format(Gogo* gogo) const
131 {
132 std::ostringstream ss;
133 if (this->is_sink())
134 ss << ".sink";
135 else if (this->object() != NULL)
136 {
137 Named_object* no = this->object();
138 if (no->is_function() && no->func_value()->enclosing() != NULL)
139 return "func literal";
140 ss << no->message_name();
141 }
142 else if (this->expr() != NULL)
143 {
144 Expression* e = this->expr();
145
146 bool is_call = e->call_expression() != NULL;
147 if (is_call)
148 e = e->call_expression()->fn();
149 Func_expression* fe = e->func_expression();;
150 if (fe != NULL)
151 {
152 Named_object* no = fe->named_object();
153 if (no->is_function() && no->func_value()->enclosing() != NULL)
154 {
155 if (is_call)
156 return "(func literal)()";
157 return "func literal";
158 }
159 }
160
161 Ast_dump_context::dump_to_stream(this->expr(), &ss);
162 }
163 else if (this->statement() != NULL)
164 {
165 Statement* s = this->statement();
166 Goto_unnamed_statement* unnamed = s->goto_unnamed_statement();
167 if (unnamed != NULL)
168 {
169 Statement* derived = unnamed->unnamed_label()->derived_from();
170 if (derived != NULL)
171 {
172 switch (derived->classification())
173 {
174 case Statement::STATEMENT_FOR:
175 case Statement::STATEMENT_FOR_RANGE:
176 return "for loop";
177 break;
178
179 case Statement::STATEMENT_SWITCH:
180 return "switch";
181 break;
182
183 case Statement::STATEMENT_TYPE_SWITCH:
184 return "type switch";
185 break;
186
187 default:
188 break;
189 }
190 }
191 }
192 Temporary_statement* tmp = s->temporary_statement();
193 if (tmp != NULL)
194 {
195 // Temporary's format can never match gc's output, and
196 // temporaries are inserted differently anyway. We just
197 // print something convenient.
198 ss << "tmp." << (uintptr_t) tmp;
199 if (tmp->init() != NULL)
200 {
201 ss << " [ = ";
202 Ast_dump_context::dump_to_stream(tmp->init(), &ss);
203 ss << " ]";
204 }
205 }
206 else
207 Ast_dump_context::dump_to_stream(s, &ss);
208 }
209 else if (this->is_indirect())
210 return "*(" + this->child()->ast_format(gogo) + ")";
211
212 std::string s = strip_packed_prefix(gogo, ss.str());
213
214 // trim trailing space
215 return s.substr(0, s.find_last_not_of(' ') + 1);
216 }
217
218 // A helper for debugging; return this node's detailed format string.
219 // This is an implementation of gc's Jconv with obj.FmtShort.
220
221 std::string
details()222 Node::details()
223 {
224 std::stringstream details;
225
226 if (!this->is_sink())
227 details << " l(" << Linemap::location_to_line(this->location()) << ")";
228
229 bool is_varargs = false;
230 bool is_address_taken = false;
231 bool is_in_heap = false;
232 bool is_assigned = false;
233 std::string class_name;
234
235 Expression* e = this->expr();
236 Named_object* node_object = NULL;
237 if (this->object() != NULL)
238 node_object = this->object();
239 else if (e != NULL && e->var_expression() != NULL)
240 node_object = e->var_expression()->named_object();
241
242 if (node_object)
243 {
244 // TODO(cmang): For named variables and functions, we want to output
245 // the function depth.
246 if (node_object->is_variable())
247 {
248 Variable* var = node_object->var_value();
249 is_varargs = var->is_varargs_parameter();
250 is_address_taken = (var->is_address_taken()
251 || var->is_non_escaping_address_taken());
252 is_in_heap = var->is_in_heap();
253 is_assigned = var->init() != NULL;
254
255 if (var->is_global())
256 class_name = "PEXTERN";
257 else if (var->is_parameter())
258 class_name = "PPARAM";
259 else if (var->is_closure())
260 class_name = "PPARAMREF";
261 else
262 class_name = "PAUTO";
263 }
264 else if (node_object->is_result_variable())
265 class_name = "PPARAMOUT";
266 else if (node_object->is_function()
267 || node_object->is_function_declaration())
268 class_name = "PFUNC";
269 }
270 else if (e != NULL && e->enclosed_var_expression() != NULL)
271 {
272 Named_object* enclosed = e->enclosed_var_expression()->variable();
273 if (enclosed->is_variable())
274 {
275 Variable* var = enclosed->var_value();
276 is_address_taken = (var->is_address_taken()
277 || var->is_non_escaping_address_taken());
278 }
279 else
280 {
281 Result_variable* var = enclosed->result_var_value();
282 is_address_taken = (var->is_address_taken()
283 || var->is_non_escaping_address_taken());
284 }
285 class_name = "PPARAMREF";
286 }
287
288 if (!class_name.empty())
289 {
290 details << " class(" << class_name;
291 if (is_in_heap)
292 details << ",heap";
293 details << ")";
294 }
295
296 switch ((this->encoding() & ESCAPE_MASK))
297 {
298 case Node::ESCAPE_UNKNOWN:
299 break;
300
301 case Node::ESCAPE_HEAP:
302 details << " esc(h)";
303 break;
304
305 case Node::ESCAPE_NONE:
306 details << " esc(no)";
307 break;
308
309 case Node::ESCAPE_NEVER:
310 details << " esc(N)";
311 break;
312
313 default:
314 details << " esc(" << this->encoding() << ")";
315 break;
316 }
317
318 if (this->state_ != NULL && this->state_->loop_depth != 0)
319 details << " ld(" << this->state_->loop_depth << ")";
320
321 if (is_varargs)
322 details << " isddd(1)";
323 if (is_address_taken)
324 details << " addrtaken";
325 if (is_assigned)
326 details << " assigned";
327
328 return details.str();
329 }
330
331 std::string
op_format() const332 Node::op_format() const
333 {
334 std::stringstream op;
335 Ast_dump_context adc(&op, false);
336 if (this->expr() != NULL)
337 {
338 Expression* e = this->expr();
339 switch (e->classification())
340 {
341 case Expression::EXPRESSION_UNARY:
342 adc.dump_operator(e->unary_expression()->op());
343 break;
344
345 case Expression::EXPRESSION_BINARY:
346 adc.dump_operator(e->binary_expression()->op());
347 break;
348
349 case Expression::EXPRESSION_CALL:
350 op << "function call";
351 break;
352
353 case Expression::EXPRESSION_FUNC_REFERENCE:
354 if (e->func_expression()->is_runtime_function())
355 {
356 switch (e->func_expression()->runtime_code())
357 {
358 case Runtime::GOPANIC:
359 op << "panic";
360 break;
361
362 case Runtime::GROWSLICE:
363 op << "append";
364 break;
365
366 case Runtime::TYPEDSLICECOPY:
367 op << "copy";
368 break;
369
370 case Runtime::MAKECHAN:
371 case Runtime::MAKECHAN64:
372 case Runtime::MAKEMAP:
373 case Runtime::MAKESLICE:
374 case Runtime::MAKESLICE64:
375 op << "make";
376 break;
377
378 case Runtime::DEFERPROC:
379 op << "defer";
380 break;
381
382 case Runtime::GORECOVER:
383 op << "recover";
384 break;
385
386 case Runtime::CLOSE:
387 op << "close";
388 break;
389
390 default:
391 break;
392 }
393 }
394 break;
395
396 case Expression::EXPRESSION_ALLOCATION:
397 op << "new";
398 break;
399
400 case Expression::EXPRESSION_RECEIVE:
401 op << "<-";
402 break;
403
404 default:
405 break;
406 }
407 }
408
409 if (this->statement() != NULL)
410 {
411 switch (this->statement()->classification())
412 {
413 case Statement::STATEMENT_DEFER:
414 op << "defer";
415 break;
416
417 case Statement::STATEMENT_RETURN:
418 op << "return";
419 break;
420
421 default:
422 break;
423 }
424 }
425 if (this->is_indirect())
426 op << "*";
427 return op.str();
428 }
429
430 // Return this node's state, creating it if has not been initialized.
431
432 Node::Escape_state*
state(Escape_context * context,Named_object * fn)433 Node::state(Escape_context* context, Named_object* fn)
434 {
435 if (this->state_ == NULL)
436 {
437 if (this->expr() != NULL && this->expr()->var_expression() != NULL)
438 {
439 // Tie state of variable references to underlying variables.
440 Named_object* var_no = this->expr()->var_expression()->named_object();
441 Node* var_node = Node::make_node(var_no);
442 this->state_ = var_node->state(context, fn);
443 }
444 else
445 {
446 this->state_ = new Node::Escape_state;
447 if (fn == NULL)
448 fn = context->current_function();
449
450 this->state_->fn = fn;
451 }
452 }
453 go_assert(this->state_ != NULL);
454 return this->state_;
455 }
456
~Node()457 Node::~Node()
458 {
459 if (this->state_ != NULL)
460 {
461 if (this->expr() == NULL || this->expr()->var_expression() == NULL)
462 // Var expression Node is excluded since it shares state with the
463 // underlying var Node.
464 delete this->state_;
465 }
466 }
467
468 int
encoding()469 Node::encoding()
470 {
471 if (this->expr() != NULL
472 && this->expr()->var_expression() != NULL)
473 {
474 // Get the underlying object's encoding.
475 Named_object* no = this->expr()->var_expression()->named_object();
476 int enc = Node::make_node(no)->encoding();
477 this->encoding_ = enc;
478 }
479 return this->encoding_;
480 }
481
482 void
set_encoding(int enc)483 Node::set_encoding(int enc)
484 {
485 this->encoding_ = enc;
486 if (this->expr() != NULL)
487 {
488 if (this->expr()->var_expression() != NULL)
489 {
490 // Set underlying object as well.
491 Named_object* no = this->expr()->var_expression()->named_object();
492 Node::make_node(no)->set_encoding(enc);
493 }
494 else if (this->expr()->func_expression() != NULL)
495 {
496 // Propagate the escape state to the underlying
497 // closure (heap expression).
498 Expression* closure = this->expr()->func_expression()->closure();
499 if (closure != NULL)
500 Node::make_node(closure)->set_encoding(enc);
501 }
502 }
503 }
504
505 bool
is_big(Escape_context * context) const506 Node::is_big(Escape_context* context) const
507 {
508 Type* t = this->type();
509 if (t == NULL
510 || t->is_call_multiple_result_type()
511 || t->is_sink_type()
512 || t->is_void_type()
513 || t->is_abstract())
514 return false;
515
516 bool big = false;
517 if (t->struct_type() != NULL
518 || (t->array_type() != NULL && !t->is_slice_type()))
519 {
520 int64_t size;
521 bool ok = t->backend_type_size(context->gogo(), &size);
522 big = ok && (size < 0 || size > 10 * 1024 * 1024);
523 }
524
525 if (this->expr() != NULL)
526 {
527 if (this->expr()->allocation_expression() != NULL)
528 {
529 Type* pt = t->deref();
530 if (pt->struct_type() != NULL
531 || (pt->array_type() != NULL && !pt->is_slice_type()))
532 {
533 int64_t size;
534 bool ok = pt->backend_type_size(context->gogo(), &size);
535 if (ok)
536 big = big || size <= 0 || size >= (1 << 16);
537 }
538 }
539 else if (this->expr()->call_expression() != NULL)
540 {
541 Call_expression* call = this->expr()->call_expression();
542 Func_expression* fn = call->fn()->func_expression();
543 if (fn != NULL
544 && fn->is_runtime_function()
545 && (fn->runtime_code() == Runtime::MAKESLICE
546 || fn->runtime_code() == Runtime::MAKESLICE64))
547 {
548 // Second argument is length.
549 Expression_list::iterator p = call->args()->begin();
550 ++p;
551
552 Expression* e = *p;
553 if (e->temporary_reference_expression() != NULL)
554 {
555 Temporary_reference_expression* tre = e->temporary_reference_expression();
556 if (tre->statement() != NULL && tre->statement()->init() != NULL)
557 e = tre->statement()->init();
558 }
559
560 Numeric_constant nc;
561 unsigned long v;
562 if (e->numeric_constant_value(&nc)
563 && nc.to_unsigned_long(&v) == Numeric_constant::NC_UL_VALID)
564 big = big || v >= (1 << 16);
565 }
566 }
567 }
568
569 return big;
570 }
571
572 bool
is_sink() const573 Node::is_sink() const
574 {
575 if (this->object() != NULL
576 && this->object()->is_sink())
577 return true;
578 else if (this->expr() != NULL
579 && this->expr()->is_sink_expression())
580 return true;
581 return false;
582 }
583
584 Unordered_map(Named_object*, Node*) Node::objects;
585 Unordered_map(Expression*, Node*) Node::expressions;
586 Unordered_map(Statement*, Node*) Node::statements;
587 std::vector<Node*> Node::indirects;
588
589 // Make a object node or return a cached node for this object.
590
591 Node*
make_node(Named_object * no)592 Node::make_node(Named_object* no)
593 {
594 std::pair<Named_object*, Node*> val(no, NULL);
595 std::pair<Unordered_map(Named_object*, Node*)::iterator, bool> ins =
596 Node::objects.insert(val);
597 if (ins.second)
598 ins.first->second = new Node(no);
599 return ins.first->second;
600 }
601
602 // Make an expression node or return a cached node for this expression.
603
604 Node*
make_node(Expression * e)605 Node::make_node(Expression* e)
606 {
607 std::pair<Expression*, Node*> val(e, NULL);
608 std::pair<Unordered_map(Expression*, Node*)::iterator, bool> ins =
609 Node::expressions.insert(val);
610 if (ins.second)
611 ins.first->second = new Node(e);
612 return ins.first->second;
613 }
614
615 // Make a statement node or return a cached node for this statement.
616
617 Node*
make_node(Statement * s)618 Node::make_node(Statement* s)
619 {
620 std::pair<Statement*, Node*> val(s, NULL);
621 std::pair<Unordered_map(Statement*, Node*)::iterator, bool> ins =
622 Node::statements.insert(val);
623 if (ins.second)
624 ins.first->second = new Node(s);
625 return ins.first->second;
626 }
627
628 // Make an indirect node with given child.
629
630 Node*
make_indirect_node(Node * child)631 Node::make_indirect_node(Node* child)
632 {
633 Node* n = new Node(child);
634 Node::indirects.push_back(n);
635 return n;
636 }
637
638 // Returns the maximum of an exisiting escape value
639 // (and its additional parameter flow flags) and a new escape type.
640
641 int
max_encoding(int e,int etype)642 Node::max_encoding(int e, int etype)
643 {
644 if ((e & ESCAPE_MASK) > etype)
645 return e;
646 if (etype == Node::ESCAPE_NONE || etype == Node::ESCAPE_RETURN)
647 return (e & ~ESCAPE_MASK) | etype;
648 return etype;
649 }
650
651 // Return a modified encoding for an input parameter that flows into an
652 // output parameter.
653
654 int
note_inout_flows(int e,int index,Level level)655 Node::note_inout_flows(int e, int index, Level level)
656 {
657 // Flow+level is encoded in two bits.
658 // 00 = not flow, xx = level+1 for 0 <= level <= maxEncodedLevel.
659 // 16 bits for Esc allows 6x2bits or 4x3bits or 3x4bits if additional
660 // information would be useful.
661 if (level.value() <= 0 && level.suffix_value() > 0)
662 return Node::max_encoding(e|ESCAPE_CONTENT_ESCAPES, Node::ESCAPE_NONE);
663 if (level.value() < 0)
664 return Node::ESCAPE_HEAP;
665 if (level.value() > ESCAPE_MAX_ENCODED_LEVEL)
666 level = Level::From(ESCAPE_MAX_ENCODED_LEVEL);
667
668 int encoded = level.value() + 1;
669 int shift = ESCAPE_BITS_PER_OUTPUT_IN_TAG * index + ESCAPE_RETURN_BITS;
670 int old = (e >> shift) & ESCAPE_BITS_MASK_FOR_TAG;
671 if (old == 0
672 || (encoded != 0 && encoded < old))
673 old = encoded;
674
675 int encoded_flow = old << shift;
676 if (((encoded_flow >> shift) & ESCAPE_BITS_MASK_FOR_TAG) != old)
677 {
678 // Failed to encode. Put this on the heap.
679 return Node::ESCAPE_HEAP;
680 }
681
682 return (e & ~(ESCAPE_BITS_MASK_FOR_TAG << shift)) | encoded_flow;
683 }
684
685 // Class Escape_context.
686
Escape_context(Gogo * gogo,bool recursive)687 Escape_context::Escape_context(Gogo* gogo, bool recursive)
688 : gogo_(gogo), current_function_(NULL), recursive_(recursive),
689 sink_(Node::make_node(Named_object::make_sink())), loop_depth_(0),
690 flood_id_(0), pdepth_(0)
691 {
692 // The sink always escapes to heap and strictly lives outside of the
693 // current function i.e. loop_depth == -1.
694 Node::Escape_state* state = this->sink_->state(this, NULL);
695 state->loop_depth = -1;
696 }
697
698 std::string
debug_function_name(Named_object * fn)699 debug_function_name(Named_object* fn)
700 {
701 if (fn == NULL)
702 return "<S>";
703
704 if (!fn->is_function())
705 return Gogo::unpack_hidden_name(fn->name());
706
707 std::string fnname = Gogo::unpack_hidden_name(fn->name());
708 if (fn->func_value()->is_method())
709 {
710 // Methods in gc compiler are named "T.m" or "(*T).m" where
711 // T is the receiver type. Add the receiver here.
712 Type* rt = fn->func_value()->type()->receiver()->type();
713 switch (rt->classification())
714 {
715 case Type::TYPE_NAMED:
716 fnname = rt->named_type()->name() + "." + fnname;
717 break;
718
719 case Type::TYPE_POINTER:
720 {
721 Named_type* nt = rt->points_to()->named_type();
722 if (nt != NULL)
723 fnname = "(*" + nt->name() + ")." + fnname;
724 break;
725 }
726
727 default:
728 break;
729 }
730 }
731
732 return fnname;
733 }
734
735 // Return the name of the current function.
736
737 std::string
current_function_name() const738 Escape_context::current_function_name() const
739 {
740 return debug_function_name(this->current_function_);
741 }
742
743 // Initialize the dummy return values for this Node N using the results
744 // in FNTYPE.
745
746 void
init_retvals(Node * n,Function_type * fntype)747 Escape_context::init_retvals(Node* n, Function_type* fntype)
748 {
749 if (fntype == NULL || fntype->results() == NULL)
750 return;
751
752 Node::Escape_state* state = n->state(this, NULL);
753 state->retvals.clear();
754 Location loc = n->location();
755
756 int i = 0;
757 char buf[50];
758 for (Typed_identifier_list::const_iterator p = fntype->results()->begin();
759 p != fntype->results()->end();
760 ++p, ++i)
761 {
762 snprintf(buf, sizeof buf, ".out%d", i);
763 Variable* dummy_var = new Variable(p->type(), NULL, false, false,
764 false, loc);
765 dummy_var->set_is_used();
766 Named_object* dummy_no =
767 Named_object::make_variable(buf, NULL, dummy_var);
768 Node* dummy_node = Node::make_node(dummy_no);
769 // Initialize the state of the dummy output node.
770 Node::Escape_state* dummy_node_state = dummy_node->state(this, NULL);
771 dummy_node_state->loop_depth = this->loop_depth_;
772
773 // Add dummy node to the retvals of n.
774 state->retvals.push_back(dummy_node);
775 }
776 }
777
778
779 // Apply an indirection to N and return the result.
780
781 Node*
add_dereference(Node * n)782 Escape_context::add_dereference(Node* n)
783 {
784 Expression* e = n->expr();
785 Location loc = n->location();
786 Node* ind;
787 if (e != NULL
788 && e->type()->points_to() != NULL
789 && !e->type()->points_to()->is_void_type())
790 {
791 // We don't dereference void*, which can be actually any pointer type.
792 Expression* deref_expr = Expression::make_unary(OPERATOR_MULT, e, loc);
793 ind = Node::make_node(deref_expr);
794 }
795 else
796 // The gc compiler simply makes an OIND node. We can't do it
797 // for non-pointer type because that will result in a type error.
798 // Instead, we model this by making a node with a special flavor.
799 ind = Node::make_indirect_node(n);
800
801 // Initialize the state.
802 Node::Escape_state* state = ind->state(this, NULL);
803 state->loop_depth = n->state(this, NULL)->loop_depth;
804 return ind;
805 }
806
807 void
track(Node * n)808 Escape_context::track(Node* n)
809 {
810 n->set_encoding(Node::ESCAPE_NONE);
811 // Initialize this node's state if it hasn't been encountered
812 // before.
813 Node::Escape_state* state = n->state(this, NULL);
814 state->loop_depth = this->loop_depth_;
815
816 this->noesc_.push_back(n);
817 }
818
819 // Return the string representation of an escapement encoding.
820
821 std::string
make_tag(int encoding)822 Escape_note::make_tag(int encoding)
823 {
824 char buf[50];
825 snprintf(buf, sizeof buf, "esc:0x%x", encoding);
826 return buf;
827 }
828
829 // Return the escapement encoding for a string tag.
830
831 int
parse_tag(std::string * tag)832 Escape_note::parse_tag(std::string* tag)
833 {
834 if (tag == NULL || tag->substr(0, 4) != "esc:")
835 return Node::ESCAPE_UNKNOWN;
836 int encoding = (int)strtol(tag->substr(4).c_str(), NULL, 0);
837 if (encoding == 0)
838 return Node::ESCAPE_UNKNOWN;
839 return encoding;
840 }
841
842
843 // The -fgo-optimize-alloc flag activates this escape analysis.
844
845 Go_optimize optimize_allocation_flag("allocs", true);
846
847 // A helper function to compute whether a function name has a
848 // matching hash value.
849
850 static bool
escape_hash_match(std::string suffix,std::string name)851 escape_hash_match(std::string suffix, std::string name)
852 {
853 if (suffix.empty())
854 return true;
855 if (suffix.at(0) == '-')
856 return !escape_hash_match(suffix.substr(1), name);
857
858 const char* p = name.c_str();
859 Go_sha1_helper* sha1_helper = go_create_sha1_helper();
860 sha1_helper->process_bytes(p, strlen(p));
861 std::string s = sha1_helper->finish();
862 delete sha1_helper;
863
864 int j = suffix.size() - 1;
865 for (int i = s.size() - 1; i >= 0; i--)
866 {
867 char c = s.at(i);
868 for (int k = 0; k < 8; k++, j--, c>>=1)
869 {
870 if (j < 0)
871 return true;
872 char bit = suffix.at(j) - '0';
873 if ((c&1) != bit)
874 return false;
875 }
876 }
877 return false;
878 }
879
880 // Analyze the program flow for escape information.
881
882 void
analyze_escape()883 Gogo::analyze_escape()
884 {
885 if (saw_errors())
886 return;
887
888 if (!optimize_allocation_flag.is_enabled()
889 && !this->compiling_runtime())
890 // We always run escape analysis when compiling runtime.
891 return;
892
893 // Discover strongly connected groups of functions to analyze for escape
894 // information in this package.
895 this->discover_analysis_sets();
896
897 if (!this->debug_escape_hash().empty())
898 std::cerr << "debug-escape-hash " << this->debug_escape_hash() << "\n";
899
900 for (std::vector<Analysis_set>::iterator p = this->analysis_sets_.begin();
901 p != this->analysis_sets_.end();
902 ++p)
903 {
904 std::vector<Named_object*> stack = p->first;
905
906 if (!this->debug_escape_hash().empty())
907 {
908 bool match = false;
909 for (std::vector<Named_object*>::const_iterator fn = stack.begin();
910 fn != stack.end();
911 ++fn)
912 match = match || escape_hash_match(this->debug_escape_hash(), (*fn)->message_name());
913 if (!match)
914 {
915 // Escape analysis won't run on these functions, but still
916 // need to tag them, so the caller knows.
917 for (std::vector<Named_object*>::iterator fn = stack.begin();
918 fn != stack.end();
919 ++fn)
920 if ((*fn)->is_function())
921 {
922 Function_type* fntype = (*fn)->func_value()->type();
923 fntype->set_is_tagged();
924
925 std::cerr << "debug-escape-hash disables " << debug_function_name(*fn) << "\n";
926 }
927
928 continue;
929 }
930 for (std::vector<Named_object*>::const_iterator fn = stack.begin();
931 fn != stack.end();
932 ++fn)
933 if ((*fn)->is_function())
934 std::cerr << "debug-escape-hash triggers " << debug_function_name(*fn) << "\n";
935 }
936
937 Escape_context* context = new Escape_context(this, p->second);
938
939 // Analyze the flow of each function; build the connection graph.
940 // This is the assign phase.
941 for (std::vector<Named_object*>::reverse_iterator fn = stack.rbegin();
942 fn != stack.rend();
943 ++fn)
944 {
945 context->set_current_function(*fn);
946 this->assign_connectivity(context, *fn);
947 }
948
949 // Propagate levels across each dst. This is the flood phase.
950 std::set<Node*> dsts = context->dsts();
951 Unordered_map(Node*, int) escapes;
952 for (std::set<Node*>::iterator n = dsts.begin();
953 n != dsts.end();
954 ++n)
955 {
956 escapes[*n] = (*n)->encoding();
957 this->propagate_escape(context, *n);
958 }
959 for (;;)
960 {
961 // Reflood if the roots' escape states increase. Run until fix point.
962 // This is rare.
963 bool done = true;
964 for (std::set<Node*>::iterator n = dsts.begin();
965 n != dsts.end();
966 ++n)
967 {
968 if ((*n)->object() == NULL
969 && ((*n)->expr() == NULL
970 || ((*n)->expr()->var_expression() == NULL
971 && (*n)->expr()->enclosed_var_expression() == NULL
972 && (*n)->expr()->func_expression() == NULL)))
973 continue;
974 if (escapes[*n] != (*n)->encoding())
975 {
976 done = false;
977 if (this->debug_escape_level() > 2)
978 go_debug((*n)->location(), "Reflooding %s %s",
979 debug_function_name((*n)->state(context, NULL)->fn).c_str(),
980 (*n)->ast_format(this).c_str());
981 escapes[*n] = (*n)->encoding();
982 this->propagate_escape(context, *n);
983 }
984 }
985 if (done)
986 break;
987 }
988
989 // Tag each exported function's parameters with escape information.
990 for (std::vector<Named_object*>::iterator fn = stack.begin();
991 fn != stack.end();
992 ++fn)
993 this->tag_function(context, *fn);
994
995 if (this->debug_escape_level() != 0)
996 {
997 std::vector<Node*> noesc = context->non_escaping_nodes();
998 for (std::vector<Node*>::const_iterator n = noesc.begin();
999 n != noesc.end();
1000 ++n)
1001 {
1002 Node::Escape_state* state = (*n)->state(context, NULL);
1003 if ((*n)->encoding() == Node::ESCAPE_NONE)
1004 go_debug((*n)->location(), "%s %s does not escape",
1005 strip_packed_prefix(this, debug_function_name(state->fn)).c_str(),
1006 (*n)->ast_format(this).c_str());
1007 }
1008 }
1009 delete context;
1010 }
1011 }
1012
1013 // Traverse the program, discovering the functions that are roots of strongly
1014 // connected components. The goal of this phase to produce a set of functions
1015 // that must be analyzed in order.
1016
1017 class Escape_analysis_discover : public Traverse
1018 {
1019 public:
Escape_analysis_discover(Gogo * gogo)1020 Escape_analysis_discover(Gogo* gogo)
1021 : Traverse(traverse_functions | traverse_func_declarations),
1022 gogo_(gogo), component_ids_()
1023 { }
1024
1025 int
1026 function(Named_object*);
1027
1028 int
1029 function_declaration(Named_object*);
1030
1031 int
1032 visit(Named_object*);
1033
1034 int
1035 visit_code(Named_object*, int);
1036
1037 private:
1038 // A counter used to generate the ID for the function node in the graph.
1039 static int id;
1040
1041 // Type used to map functions to an ID in a graph of connected components.
1042 typedef Unordered_map(Named_object*, int) Component_ids;
1043
1044 // The Go IR.
1045 Gogo* gogo_;
1046 // The list of functions encountered during connected component discovery.
1047 Component_ids component_ids_;
1048 // The stack of functions that this component consists of.
1049 std::stack<Named_object*> stack_;
1050 };
1051
1052 int Escape_analysis_discover::id = 0;
1053
1054 // Visit each function.
1055
1056 int
function(Named_object * fn)1057 Escape_analysis_discover::function(Named_object* fn)
1058 {
1059 this->visit(fn);
1060 return TRAVERSE_CONTINUE;
1061 }
1062
1063 int
function_declaration(Named_object * fn)1064 Escape_analysis_discover::function_declaration(Named_object* fn)
1065 {
1066 this->visit(fn);
1067 return TRAVERSE_CONTINUE;
1068 }
1069
1070 // Visit a function FN, adding it to the current stack of functions
1071 // in this connected component. If this is the root of the component,
1072 // create a set of functions to be analyzed later.
1073 //
1074 // Finding these sets is finding strongly connected components
1075 // in the static call graph. The algorithm for doing that is taken
1076 // from Sedgewick, Algorithms, Second Edition, p. 482, with two
1077 // adaptations.
1078 //
1079 // First, a closure (fn->func_value()->enclosing() == NULL) cannot be the
1080 // root of a connected component. Refusing to use it as a root
1081 // forces it into the component of the function in which it appears.
1082 // This is more convenient for escape analysis.
1083 //
1084 // Second, each function becomes two virtual nodes in the graph,
1085 // with numbers n and n+1. We record the function's node number as n
1086 // but search from node n+1. If the search tells us that the component
1087 // number (min) is n+1, we know that this is a trivial component: one function
1088 // plus its closures. If the search tells us that the component number is
1089 // n, then there was a path from node n+1 back to node n, meaning that
1090 // the function set is mutually recursive. The escape analysis can be
1091 // more precise when analyzing a single non-recursive function than
1092 // when analyzing a set of mutually recursive functions.
1093
1094 int
visit(Named_object * fn)1095 Escape_analysis_discover::visit(Named_object* fn)
1096 {
1097 Component_ids::const_iterator p = this->component_ids_.find(fn);
1098 if (p != this->component_ids_.end())
1099 // Already visited.
1100 return p->second;
1101
1102 this->id++;
1103 int id = this->id;
1104 this->component_ids_[fn] = id;
1105 this->id++;
1106 int min = this->id;
1107
1108 this->stack_.push(fn);
1109 min = this->visit_code(fn, min);
1110 if ((min == id || min == id + 1)
1111 && ((fn->is_function() && fn->func_value()->enclosing() == NULL)
1112 || fn->is_function_declaration()))
1113 {
1114 bool recursive = min == id;
1115 std::vector<Named_object*> group;
1116
1117 for (; !this->stack_.empty(); this->stack_.pop())
1118 {
1119 Named_object* n = this->stack_.top();
1120 if (n == fn)
1121 {
1122 this->stack_.pop();
1123 break;
1124 }
1125
1126 group.push_back(n);
1127 this->component_ids_[n] = std::numeric_limits<int>::max();
1128 }
1129 group.push_back(fn);
1130 this->component_ids_[fn] = std::numeric_limits<int>::max();
1131
1132 std::reverse(group.begin(), group.end());
1133 this->gogo_->add_analysis_set(group, recursive);
1134 }
1135
1136 return min;
1137 }
1138
1139 // Helper class for discovery step. Traverse expressions looking for
1140 // function calls and closures to visit during the discovery step.
1141
1142 class Escape_discover_expr : public Traverse
1143 {
1144 public:
Escape_discover_expr(Escape_analysis_discover * ead,int min)1145 Escape_discover_expr(Escape_analysis_discover* ead, int min)
1146 : Traverse(traverse_expressions),
1147 ead_(ead), min_(min)
1148 { }
1149
1150 int
min()1151 min()
1152 { return this->min_; }
1153
1154 int
1155 expression(Expression** pexpr);
1156
1157 private:
1158 // The original discovery analysis.
1159 Escape_analysis_discover* ead_;
1160 // The minimum component ID in this group.
1161 int min_;
1162 };
1163
1164 // Visit any calls or closures found when discovering expressions.
1165
1166 int
expression(Expression ** pexpr)1167 Escape_discover_expr::expression(Expression** pexpr)
1168 {
1169 Expression* e = *pexpr;
1170 Named_object* fn = NULL;
1171 if (e->call_expression() != NULL
1172 && e->call_expression()->fn()->func_expression() != NULL)
1173 {
1174 // Method call or function call.
1175 fn = e->call_expression()->fn()->func_expression()->named_object();
1176 }
1177 else if (e->func_expression() != NULL)
1178 {
1179 Named_object* no = e->func_expression()->named_object();
1180 if (no->is_function() && no->func_value()->enclosing() != NULL)
1181 {
1182 // Nested function.
1183 fn = no;
1184 }
1185 }
1186
1187 if (fn != NULL)
1188 this->min_ = std::min(this->min_, this->ead_->visit(fn));
1189 return TRAVERSE_CONTINUE;
1190 }
1191
1192 // Visit the body of each function, returns ID of the minimum connected
1193 // component found in the body.
1194
1195 int
visit_code(Named_object * fn,int min)1196 Escape_analysis_discover::visit_code(Named_object* fn, int min)
1197 {
1198 if (!fn->is_function())
1199 return min;
1200
1201 Escape_discover_expr ede(this, min);
1202 fn->func_value()->traverse(&ede);
1203 return ede.min();
1204 }
1205
1206 // Discover strongly connected groups of functions to analyze.
1207
1208 void
discover_analysis_sets()1209 Gogo::discover_analysis_sets()
1210 {
1211 Escape_analysis_discover ead(this);
1212 this->traverse(&ead);
1213 }
1214
1215 // Traverse all label and goto statements and mark the underlying label
1216 // as looping or not looping.
1217
1218 class Escape_analysis_loop : public Traverse
1219 {
1220 public:
Escape_analysis_loop()1221 Escape_analysis_loop()
1222 : Traverse(traverse_statements)
1223 { }
1224
1225 int
1226 statement(Block*, size_t*, Statement*);
1227 };
1228
1229 int
statement(Block *,size_t *,Statement * s)1230 Escape_analysis_loop::statement(Block*, size_t*, Statement* s)
1231 {
1232 if (s->label_statement() != NULL)
1233 s->label_statement()->label()->set_nonlooping();
1234 else if (s->goto_statement() != NULL)
1235 {
1236 if (s->goto_statement()->label()->nonlooping())
1237 s->goto_statement()->label()->set_looping();
1238 }
1239 return TRAVERSE_CONTINUE;
1240 }
1241
1242 // Traversal class used to look at all interesting statements within a function
1243 // in order to build a connectivity graph between all nodes within a context's
1244 // scope.
1245
1246 class Escape_analysis_assign : public Traverse
1247 {
1248 public:
Escape_analysis_assign(Escape_context * context,Named_object * fn)1249 Escape_analysis_assign(Escape_context* context, Named_object* fn)
1250 : Traverse(traverse_statements
1251 | traverse_expressions),
1252 context_(context), fn_(fn)
1253 { }
1254
1255 // Model statements within a function as assignments and flows between nodes.
1256 int
1257 statement(Block*, size_t*, Statement*);
1258
1259 // Model expressions within a function as assignments and flows between nodes.
1260 int
1261 expression(Expression**);
1262
1263 // Model calls within a function as assignments and flows between arguments
1264 // and results.
1265 void
1266 call(Call_expression* call);
1267
1268 // Model the assignment of DST to SRC.
1269 void
1270 assign(Node* dst, Node* src);
1271
1272 // Model the assignment of DST to dereference of SRC.
1273 void
1274 assign_deref(Node* dst, Node* src);
1275
1276 // Model the input-to-output assignment flow of one of a function call's
1277 // arguments, where the flow is encoding in NOTE.
1278 int
1279 assign_from_note(std::string* note, const std::vector<Node*>& dsts,
1280 Node* src);
1281
1282 // Record the flow of SRC to DST in DST.
1283 void
1284 flows(Node* dst, Node* src);
1285
1286 private:
1287 // The escape context for this set of functions.
1288 Escape_context* context_;
1289 // The current function being analyzed.
1290 Named_object* fn_;
1291 };
1292
1293 // Helper function to detect self assignment like the following.
1294 //
1295 // func (b *Buffer) Foo() {
1296 // n, m := ...
1297 // b.buf = b.buf[n:m]
1298 // }
1299
1300 static bool
is_self_assignment(Expression * lhs,Expression * rhs)1301 is_self_assignment(Expression* lhs, Expression* rhs)
1302 {
1303 Unary_expression* lue =
1304 (lhs->field_reference_expression() != NULL
1305 ? lhs->field_reference_expression()->expr()->unary_expression()
1306 : lhs->unary_expression());
1307 Var_expression* lve =
1308 (lue != NULL && lue->op() == OPERATOR_MULT ? lue->operand()->var_expression() : NULL);
1309 Array_index_expression* raie = rhs->array_index_expression();
1310 String_index_expression* rsie = rhs->string_index_expression();
1311 Expression* rarray =
1312 (raie != NULL && raie->end() != NULL && raie->array()->type()->is_slice_type()
1313 ? raie->array()
1314 : (rsie != NULL && rsie->type()->is_string_type() ? rsie->string() : NULL));
1315 Unary_expression* rue =
1316 (rarray != NULL && rarray->field_reference_expression() != NULL
1317 ? rarray->field_reference_expression()->expr()->unary_expression()
1318 : (rarray != NULL ? rarray->unary_expression() : NULL));
1319 Var_expression* rve =
1320 (rue != NULL && rue->op() == OPERATOR_MULT ? rue->operand()->var_expression() : NULL);
1321 return lve != NULL && rve != NULL
1322 && lve->named_object() == rve->named_object();
1323 }
1324
1325 // Model statements within a function as assignments and flows between nodes.
1326
1327 int
statement(Block *,size_t *,Statement * s)1328 Escape_analysis_assign::statement(Block*, size_t*, Statement* s)
1329 {
1330 // Adjust the loop depth as we enter/exit blocks related to for statements.
1331 bool is_for_statement = (s->is_block_statement()
1332 && s->block_statement()->is_lowered_for_statement());
1333 if (is_for_statement)
1334 this->context_->increase_loop_depth();
1335
1336 s->traverse_contents(this);
1337
1338 if (is_for_statement)
1339 this->context_->decrease_loop_depth();
1340
1341 Gogo* gogo = this->context_->gogo();
1342 int debug_level = gogo->debug_escape_level();
1343 if (debug_level > 1
1344 && s->unnamed_label_statement() == NULL
1345 && s->expression_statement() == NULL
1346 && !s->is_block_statement())
1347 {
1348 Node* n = Node::make_node(s);
1349 std::string fn_name = this->context_->current_function_name();
1350 go_debug(s->location(), "[%d] %s esc: %s",
1351 this->context_->loop_depth(), fn_name.c_str(),
1352 n->ast_format(gogo).c_str());
1353 }
1354
1355 switch (s->classification())
1356 {
1357 case Statement::STATEMENT_VARIABLE_DECLARATION:
1358 {
1359 Named_object* var = s->variable_declaration_statement()->var();
1360 Node* var_node = Node::make_node(var);
1361 Node::Escape_state* state = var_node->state(this->context_, NULL);
1362 state->loop_depth = this->context_->loop_depth();
1363
1364 // Set the loop depth for this declaration.
1365 if (var->is_variable()
1366 && var->var_value()->init() != NULL)
1367 {
1368 Node* init_node = Node::make_node(var->var_value()->init());
1369 this->assign(var_node, init_node);
1370 }
1371 }
1372 break;
1373
1374 case Statement::STATEMENT_TEMPORARY:
1375 {
1376 Expression* init = s->temporary_statement()->init();
1377 if (init != NULL)
1378 {
1379 Node* n = Node::make_node(init);
1380 if (s->temporary_statement()->value_escapes())
1381 this->assign(this->context_->sink(), n);
1382 else
1383 this->assign(Node::make_node(s), n);
1384 }
1385 }
1386 break;
1387
1388 case Statement::STATEMENT_LABEL:
1389 {
1390 Label_statement* label_stmt = s->label_statement();
1391 if (label_stmt->label()->looping())
1392 this->context_->increase_loop_depth();
1393
1394 if (debug_level > 1)
1395 {
1396 std::string label_type = (label_stmt->label()->looping()
1397 ? "looping"
1398 : "nonlooping");
1399 go_inform(s->location(), "%s %s label",
1400 label_stmt->label()->name().c_str(),
1401 label_type.c_str());
1402 }
1403 }
1404 break;
1405
1406 case Statement::STATEMENT_SWITCH:
1407 case Statement::STATEMENT_TYPE_SWITCH:
1408 // Want to model the assignment of each case variable to the switched upon
1409 // variable. This should be lowered into assignment statements; nothing
1410 // to here if that's the case.
1411 break;
1412
1413 case Statement::STATEMENT_ASSIGNMENT:
1414 {
1415 Assignment_statement* assn = s->assignment_statement();
1416 Expression* lhs = assn->lhs();
1417 Expression* rhs = assn->rhs();
1418 Node* lhs_node = Node::make_node(lhs);
1419 Node* rhs_node = Node::make_node(rhs);
1420
1421 // Filter out the following special case.
1422 //
1423 // func (b *Buffer) Foo() {
1424 // n, m := ...
1425 // b.buf = b.buf[n:m]
1426 // }
1427 //
1428 // This assignment is a no-op for escape analysis,
1429 // it does not store any new pointers into b that were not already there.
1430 // However, without this special case b will escape.
1431 if (is_self_assignment(lhs, rhs))
1432 {
1433 if (debug_level != 0)
1434 go_inform(s->location(), "%s ignoring self-assignment to %s",
1435 strip_packed_prefix(gogo, this->context_->current_function_name()).c_str(),
1436 lhs_node->ast_format(gogo).c_str());
1437 break;
1438 }
1439
1440 this->assign(lhs_node, rhs_node);
1441 }
1442 break;
1443
1444 case Statement::STATEMENT_SEND:
1445 {
1446 Node* sent_node = Node::make_node(s->send_statement()->val());
1447 this->assign(this->context_->sink(), sent_node);
1448 }
1449 break;
1450
1451 case Statement::STATEMENT_DEFER:
1452 if (this->context_->loop_depth() == 1)
1453 {
1454 // Defer statement may need to allocate a thunk. When it is
1455 // not inside a loop, this can be stack allocated, as it
1456 // runs before the function finishes.
1457 Node* n = Node::make_node(s);
1458 n->set_encoding(Node::ESCAPE_NONE);
1459 break;
1460 }
1461 // fallthrough
1462
1463 case Statement::STATEMENT_GO:
1464 {
1465 // Defer f(x) or go f(x).
1466 // Both f and x escape to the heap.
1467 Thunk_statement* thunk = s->thunk_statement();
1468 if (thunk->call()->call_expression() == NULL)
1469 break;
1470
1471 Call_expression* call = thunk->call()->call_expression();
1472 Node* func_node = Node::make_node(call->fn());
1473 this->assign(this->context_->sink(), func_node);
1474 if (call->args() != NULL)
1475 {
1476 for (Expression_list::const_iterator p = call->args()->begin();
1477 p != call->args()->end();
1478 ++p)
1479 {
1480 Node* arg_node = Node::make_node(*p);
1481 this->assign(this->context_->sink(), arg_node);
1482 }
1483 }
1484 }
1485 break;
1486
1487 default:
1488 break;
1489 }
1490 return TRAVERSE_SKIP_COMPONENTS;
1491 }
1492
1493 // Helper function to emit moved-to-heap diagnostics.
1494
1495 static void
move_to_heap(Gogo * gogo,Expression * expr)1496 move_to_heap(Gogo* gogo, Expression *expr)
1497 {
1498 Named_object* no;
1499 if (expr->var_expression() != NULL)
1500 no = expr->var_expression()->named_object();
1501 else if (expr->enclosed_var_expression() != NULL)
1502 no = expr->enclosed_var_expression()->variable();
1503 else
1504 return;
1505
1506 if ((no->is_variable()
1507 && !no->var_value()->is_global())
1508 || no->is_result_variable())
1509 {
1510 Node* n = Node::make_node(expr);
1511 if (gogo->debug_escape_level() != 0)
1512 go_debug(n->definition_location(),
1513 "moved to heap: %s",
1514 n->ast_format(gogo).c_str());
1515 if (gogo->compiling_runtime() && gogo->package_name() == "runtime")
1516 go_error_at(expr->location(),
1517 "%s escapes to heap, not allowed in runtime",
1518 n->ast_format(gogo).c_str());
1519 }
1520 }
1521
1522 // Model expressions within a function as assignments and flows between nodes.
1523
1524 int
expression(Expression ** pexpr)1525 Escape_analysis_assign::expression(Expression** pexpr)
1526 {
1527 Gogo* gogo = this->context_->gogo();
1528 int debug_level = gogo->debug_escape_level();
1529
1530 // Big stuff escapes unconditionally.
1531 Node* n = Node::make_node(*pexpr);
1532 if ((n->encoding() & ESCAPE_MASK) != int(Node::ESCAPE_HEAP)
1533 && n->is_big(this->context_))
1534 {
1535 if (debug_level > 1)
1536 go_debug((*pexpr)->location(), "%s too large for stack",
1537 n->ast_format(gogo).c_str());
1538 move_to_heap(gogo, *pexpr);
1539 n->set_encoding(Node::ESCAPE_HEAP);
1540 (*pexpr)->address_taken(true);
1541 this->assign(this->context_->sink(), n);
1542 }
1543
1544 if ((*pexpr)->func_expression() == NULL)
1545 (*pexpr)->traverse_subexpressions(this);
1546
1547 if (debug_level > 1)
1548 {
1549 std::string fn_name = this->context_->current_function_name();
1550 go_debug((*pexpr)->location(), "[%d] %s esc: %s",
1551 this->context_->loop_depth(), fn_name.c_str(),
1552 n->ast_format(gogo).c_str());
1553 }
1554
1555 switch ((*pexpr)->classification())
1556 {
1557 case Expression::EXPRESSION_CALL:
1558 {
1559 Call_expression* call = (*pexpr)->call_expression();
1560 if (call->is_builtin())
1561 {
1562 Builtin_call_expression* bce = call->builtin_call_expression();
1563 switch (bce->code())
1564 {
1565 case Builtin_call_expression::BUILTIN_PANIC:
1566 {
1567 // Argument could leak through recover.
1568 Node* panic_arg = Node::make_node(call->args()->front());
1569 this->assign(this->context_->sink(), panic_arg);
1570 }
1571 break;
1572
1573 case Builtin_call_expression::BUILTIN_APPEND:
1574 {
1575 // The contents being appended leak.
1576 if (call->is_varargs())
1577 {
1578 // append(slice1, slice2...) -- slice2 itself does not escape, but contents do
1579 Node* appended = Node::make_node(call->args()->back());
1580 this->assign_deref(this->context_->sink(), appended);
1581 if (debug_level > 2)
1582 go_debug((*pexpr)->location(),
1583 "special treatment of append(slice1, slice2...)");
1584 }
1585 else
1586 {
1587 for (Expression_list::const_iterator pa =
1588 call->args()->begin() + 1;
1589 pa != call->args()->end();
1590 ++pa)
1591 {
1592 Node* arg = Node::make_node(*pa);
1593 this->assign(this->context_->sink(), arg);
1594 }
1595 }
1596
1597 // The content of the original slice leaks as well.
1598 Node* appendee = Node::make_node(call->args()->front());
1599 this->assign_deref(this->context_->sink(), appendee);
1600 }
1601 break;
1602
1603 case Builtin_call_expression::BUILTIN_COPY:
1604 {
1605 // Lose track of the copied content.
1606 Node* copied = Node::make_node(call->args()->back());
1607 this->assign_deref(this->context_->sink(), copied);
1608 }
1609 break;
1610
1611 case Builtin_call_expression::BUILTIN_CLOSE:
1612 case Builtin_call_expression::BUILTIN_DELETE:
1613 case Builtin_call_expression::BUILTIN_PRINT:
1614 case Builtin_call_expression::BUILTIN_PRINTLN:
1615 case Builtin_call_expression::BUILTIN_LEN:
1616 case Builtin_call_expression::BUILTIN_CAP:
1617 case Builtin_call_expression::BUILTIN_COMPLEX:
1618 case Builtin_call_expression::BUILTIN_REAL:
1619 case Builtin_call_expression::BUILTIN_IMAG:
1620 case Builtin_call_expression::BUILTIN_RECOVER:
1621 case Builtin_call_expression::BUILTIN_ALIGNOF:
1622 case Builtin_call_expression::BUILTIN_OFFSETOF:
1623 case Builtin_call_expression::BUILTIN_SIZEOF:
1624 // these do not escape.
1625 break;
1626
1627 case Builtin_call_expression::BUILTIN_ADD:
1628 case Builtin_call_expression::BUILTIN_SLICE:
1629 // handled in ::assign.
1630 break;
1631
1632 case Builtin_call_expression::BUILTIN_MAKE:
1633 case Builtin_call_expression::BUILTIN_NEW:
1634 // should have been lowered to runtime calls at this point.
1635 // fallthrough
1636 default:
1637 go_unreachable();
1638 }
1639 break;
1640 }
1641 Func_expression* fe = call->fn()->func_expression();
1642 if (fe != NULL && fe->is_runtime_function())
1643 {
1644 switch (fe->runtime_code())
1645 {
1646 case Runtime::MAKECHAN:
1647 case Runtime::MAKECHAN64:
1648 case Runtime::MAKEMAP:
1649 case Runtime::MAKEMAP64:
1650 case Runtime::MAKESLICE:
1651 case Runtime::MAKESLICE64:
1652 this->context_->track(n);
1653 break;
1654
1655 case Runtime::MAPASSIGN:
1656 {
1657 // Map key escapes. The last argument is the address
1658 // of the key.
1659 Node* key_node = Node::make_node(call->args()->back());
1660 this->assign_deref(this->context_->sink(), key_node);
1661 }
1662 break;
1663
1664 case Runtime::MAPASSIGN_FAST32PTR:
1665 case Runtime::MAPASSIGN_FAST64PTR:
1666 case Runtime::MAPASSIGN_FASTSTR:
1667 {
1668 // Map key escapes. The last argument is the key.
1669 Node* key_node = Node::make_node(call->args()->back());
1670 this->assign(this->context_->sink(), key_node);
1671 }
1672 break;
1673
1674 case Runtime::IFACEE2T2:
1675 case Runtime::IFACEI2T2:
1676 {
1677 // x, ok = v.(T), where T is non-pointer non-interface,
1678 // is lowered to
1679 // ok = IFACEI2T2(type, v, (void*)&tmp_x)
1680 // Here v flows to tmp_x.
1681 // Note: other IFACEX2Y2 returns the conversion result.
1682 // Those are handled in ::assign.
1683 Node* src_node = Node::make_node(call->args()->at(1));
1684 Node* dst_node;
1685 Expression* arg2 = call->args()->at(2);
1686 // Try to pull tmp_x out of the arg2 expression, and let v
1687 // flows into it, instead of simply dereference arg2,
1688 // which looks like dereference of an arbitrary pointer
1689 // and causes v immediately escape.
1690 // The expression form matches statement.cc,
1691 // Tuple_type_guard_assignment_statement::lower_to_object_type.
1692 Unary_expression* ue =
1693 (arg2->conversion_expression() != NULL
1694 ? arg2->conversion_expression()->expr()->unary_expression()
1695 : arg2->unary_expression());
1696 if (ue != NULL && ue->op() == OPERATOR_AND)
1697 {
1698 if (!ue->operand()->type()->has_pointer())
1699 // Don't bother flowing non-pointer.
1700 break;
1701 dst_node = Node::make_node(ue->operand());
1702 }
1703 else
1704 dst_node = this->context_->add_dereference(Node::make_node(arg2));
1705 this->assign(dst_node, src_node);
1706 }
1707 break;
1708
1709 case Runtime::MEMCMP:
1710 case Runtime::DECODERUNE:
1711 case Runtime::INTSTRING:
1712 case Runtime::MAKEMAP_SMALL:
1713 case Runtime::MAPACCESS1:
1714 case Runtime::MAPACCESS1_FAST32:
1715 case Runtime::MAPACCESS1_FAST64:
1716 case Runtime::MAPACCESS1_FASTSTR:
1717 case Runtime::MAPACCESS1_FAT:
1718 case Runtime::MAPACCESS2:
1719 case Runtime::MAPACCESS2_FAST32:
1720 case Runtime::MAPACCESS2_FAST64:
1721 case Runtime::MAPACCESS2_FASTSTR:
1722 case Runtime::MAPACCESS2_FAT:
1723 case Runtime::MAPASSIGN_FAST32:
1724 case Runtime::MAPASSIGN_FAST64:
1725 case Runtime::MAPITERINIT:
1726 case Runtime::MAPITERNEXT:
1727 case Runtime::MAPCLEAR:
1728 case Runtime::CHANRECV2:
1729 case Runtime::SELECTGO:
1730 case Runtime::SELECTNBSEND:
1731 case Runtime::SELECTNBRECV:
1732 case Runtime::BLOCK:
1733 case Runtime::IFACET2IP:
1734 case Runtime::EQTYPE:
1735 case Runtime::MEMCLRHASPTR:
1736 case Runtime::FIELDTRACK:
1737 case Runtime::BUILTIN_MEMSET:
1738 case Runtime::PANIC_SLICE_CONVERT:
1739 // these do not escape.
1740 break;
1741
1742 case Runtime::IFACEE2E2:
1743 case Runtime::IFACEI2E2:
1744 case Runtime::IFACEE2I2:
1745 case Runtime::IFACEI2I2:
1746 case Runtime::IFACEE2T2P:
1747 case Runtime::IFACEI2T2P:
1748 // handled in ::assign.
1749 break;
1750
1751 default:
1752 // should not see other runtime calls. they are not yet
1753 // lowered to runtime calls at this point.
1754 go_unreachable();
1755 }
1756 }
1757 else
1758 this->call(call);
1759 }
1760 break;
1761
1762 case Expression::EXPRESSION_ALLOCATION:
1763 // This is Runtime::NEW.
1764 this->context_->track(n);
1765 break;
1766
1767 case Expression::EXPRESSION_STRING_CONCAT:
1768 this->context_->track(n);
1769 break;
1770
1771 case Expression::EXPRESSION_CONVERSION:
1772 {
1773 Type_conversion_expression* tce = (*pexpr)->conversion_expression();
1774 Type* ft = tce->expr()->type();
1775 Type* tt = tce->type();
1776 if ((ft->is_string_type() && tt->is_slice_type())
1777 || (ft->is_slice_type() && tt->is_string_type())
1778 || (ft->integer_type() != NULL && tt->is_string_type()))
1779 {
1780 // string([]byte), string([]rune), []byte(string), []rune(string), string(rune)
1781 this->context_->track(n);
1782 break;
1783 }
1784 Node* tce_node = Node::make_node(tce);
1785 Node* converted = Node::make_node(tce->expr());
1786 this->context_->track(tce_node);
1787
1788 this->assign(tce_node, converted);
1789 }
1790 break;
1791
1792 case Expression::EXPRESSION_UNSAFE_CONVERSION:
1793 {
1794 Unsafe_type_conversion_expression* uce =
1795 (*pexpr)->unsafe_conversion_expression();
1796 Node* expr_node = Node::make_node(uce->expr());
1797 this->assign(n, expr_node);
1798 }
1799 break;
1800
1801 case Expression::EXPRESSION_FIXED_ARRAY_CONSTRUCTION:
1802 case Expression::EXPRESSION_SLICE_CONSTRUCTION:
1803 {
1804 Node* array_node = Node::make_node(*pexpr);
1805 if ((*pexpr)->slice_literal() != NULL)
1806 this->context_->track(array_node);
1807
1808 Expression_list* vals = ((*pexpr)->slice_literal() != NULL
1809 ? (*pexpr)->slice_literal()->vals()
1810 : (*pexpr)->array_literal()->vals());
1811
1812 if (vals != NULL)
1813 {
1814 // Connect the array to its values.
1815 for (Expression_list::const_iterator p = vals->begin();
1816 p != vals->end();
1817 ++p)
1818 if ((*p) != NULL)
1819 this->assign(array_node, Node::make_node(*p));
1820 }
1821 }
1822 break;
1823
1824 case Expression::EXPRESSION_STRUCT_CONSTRUCTION:
1825 {
1826 Node* struct_node = Node::make_node(*pexpr);
1827 Expression_list* vals = (*pexpr)->struct_literal()->vals();
1828 if (vals != NULL)
1829 {
1830 // Connect the struct to its values.
1831 for (Expression_list::const_iterator p = vals->begin();
1832 p != vals->end();
1833 ++p)
1834 {
1835 if ((*p) != NULL)
1836 this->assign(struct_node, Node::make_node(*p));
1837 }
1838 }
1839 }
1840 break;
1841
1842 case Expression::EXPRESSION_SLICE_VALUE:
1843 {
1844 // Connect the pointer field to the slice value.
1845 Node* slice_node = Node::make_node(*pexpr);
1846 Node* ptr_node =
1847 Node::make_node((*pexpr)->slice_value_expression()->valmem());
1848 this->assign(slice_node, ptr_node);
1849 }
1850 break;
1851
1852 case Expression::EXPRESSION_HEAP:
1853 {
1854 Node* pointer_node = Node::make_node(*pexpr);
1855 Node* lit_node = Node::make_node((*pexpr)->heap_expression()->expr());
1856 this->context_->track(pointer_node);
1857
1858 // Connect pointer node to literal node; if the pointer node escapes, so
1859 // does the literal node.
1860 this->assign(pointer_node, lit_node);
1861 }
1862 break;
1863
1864 case Expression::EXPRESSION_BOUND_METHOD:
1865 {
1866 Node* bound_node = Node::make_node(*pexpr);
1867 this->context_->track(bound_node);
1868
1869 Expression* obj = (*pexpr)->bound_method_expression()->first_argument();
1870 Node* obj_node = Node::make_node(obj);
1871
1872 // A bound method implies the receiver will be used outside of the
1873 // lifetime of the method in some way. We lose track of the receiver.
1874 this->assign(this->context_->sink(), obj_node);
1875 }
1876 break;
1877
1878 case Expression::EXPRESSION_MAP_CONSTRUCTION:
1879 {
1880 Map_construction_expression* mce = (*pexpr)->map_literal();
1881 Node* map_node = Node::make_node(mce);
1882 this->context_->track(map_node);
1883
1884 // All keys and values escape to memory.
1885 if (mce->vals() != NULL)
1886 {
1887 for (Expression_list::const_iterator p = mce->vals()->begin();
1888 p != mce->vals()->end();
1889 ++p)
1890 {
1891 if ((*p) != NULL)
1892 this->assign(this->context_->sink(), Node::make_node(*p));
1893 }
1894 }
1895 }
1896 break;
1897
1898 case Expression::EXPRESSION_FUNC_REFERENCE:
1899 {
1900 Func_expression* fe = (*pexpr)->func_expression();
1901 if (fe->closure() != NULL)
1902 {
1903 // Connect captured variables to the closure.
1904 Node* closure_node = Node::make_node(fe);
1905 this->context_->track(closure_node);
1906
1907 // A closure expression already exists as the heap expression:
1908 // &struct{f func_code, v []*Variable}{...}.
1909 // Link closure to the addresses of the variables enclosed.
1910 Heap_expression* he = fe->closure()->heap_expression();
1911 Struct_construction_expression* sce = he->expr()->struct_literal();
1912
1913 // First field is function code, other fields are variable
1914 // references.
1915 Expression_list::const_iterator p = sce->vals()->begin();
1916 ++p;
1917 for (; p != sce->vals()->end(); ++p)
1918 {
1919 Node* enclosed_node = Node::make_node(*p);
1920 this->context_->track(enclosed_node);
1921 this->assign(closure_node, enclosed_node);
1922 }
1923 }
1924 }
1925 break;
1926
1927 case Expression::EXPRESSION_UNARY:
1928 {
1929 Expression* operand = (*pexpr)->unary_expression()->operand();
1930
1931 if ((*pexpr)->unary_expression()->op() == OPERATOR_AND)
1932 {
1933 this->context_->track(n);
1934
1935 Named_object* var = NULL;
1936 if (operand->var_expression() != NULL)
1937 var = operand->var_expression()->named_object();
1938 else if (operand->enclosed_var_expression() != NULL)
1939 var = operand->enclosed_var_expression()->variable();
1940
1941 if (var != NULL
1942 && ((var->is_variable() && var->var_value()->is_parameter())
1943 || var->is_result_variable()))
1944 {
1945 Node::Escape_state* addr_state = n->state(this->context_, NULL);
1946 addr_state->loop_depth = 1;
1947 break;
1948 }
1949 }
1950
1951 if ((*pexpr)->unary_expression()->op() != OPERATOR_AND
1952 && (*pexpr)->unary_expression()->op() != OPERATOR_MULT)
1953 break;
1954
1955 // For &x and *x, use the loop depth of x if known.
1956 Node::Escape_state* expr_state = n->state(this->context_, NULL);
1957 Node* operand_node = Node::make_node(operand);
1958 Node::Escape_state* operand_state = operand_node->state(this->context_, NULL);
1959 if (operand_state->loop_depth != 0)
1960 expr_state->loop_depth = operand_state->loop_depth;
1961 }
1962 break;
1963
1964 case Expression::EXPRESSION_ARRAY_INDEX:
1965 {
1966 Array_index_expression* aie = (*pexpr)->array_index_expression();
1967
1968 // Propagate the loopdepth to element.
1969 Node* array_node = Node::make_node(aie->array());
1970 Node::Escape_state* elem_state = n->state(this->context_, NULL);
1971 Node::Escape_state* array_state = array_node->state(this->context_, NULL);
1972 elem_state->loop_depth = array_state->loop_depth;
1973
1974 if (aie->end() != NULL && !aie->array()->type()->is_slice_type())
1975 {
1976 // Slicing an array. This effectively takes the address of the array.
1977 Expression* addr = Expression::make_unary(OPERATOR_AND, aie->array(),
1978 aie->location());
1979 Node* addr_node = Node::make_node(addr);
1980 n->set_child(addr_node);
1981 this->context_->track(addr_node);
1982
1983 Node::Escape_state* addr_state = addr_node->state(this->context_, NULL);
1984 if (array_state->loop_depth != 0)
1985 addr_state->loop_depth = array_state->loop_depth;
1986 }
1987 }
1988 break;
1989
1990 case Expression::EXPRESSION_FIELD_REFERENCE:
1991 {
1992 // Propagate the loopdepth to field.
1993 Node* struct_node =
1994 Node::make_node((*pexpr)->field_reference_expression()->expr());
1995 Node::Escape_state* field_state = n->state(this->context_, NULL);
1996 Node::Escape_state* struct_state = struct_node->state(this->context_, NULL);
1997 field_state->loop_depth = struct_state->loop_depth;
1998 }
1999 break;
2000
2001 default:
2002 break;
2003 }
2004 return TRAVERSE_SKIP_COMPONENTS;
2005 }
2006
2007 // Model calls within a function as assignments and flows between arguments
2008 // and results.
2009
2010 void
call(Call_expression * call)2011 Escape_analysis_assign::call(Call_expression* call)
2012 {
2013 Gogo* gogo = this->context_->gogo();
2014 int debug_level = gogo->debug_escape_level();
2015
2016 Func_expression* fn = call->fn()->func_expression();
2017 Function_type* fntype = call->get_function_type();
2018 bool indirect = false;
2019
2020 // Interface method calls or closure calls are indirect calls.
2021 if (fntype == NULL
2022 || (fntype->is_method()
2023 && fntype->receiver()->type()->interface_type() != NULL)
2024 || fn == NULL
2025 || (fn->named_object()->is_function()
2026 && fn->named_object()->func_value()->enclosing() != NULL))
2027 indirect = true;
2028
2029 Node* call_node = Node::make_node(call);
2030 std::vector<Node*> arg_nodes;
2031 if (call->fn()->interface_field_reference_expression() != NULL)
2032 {
2033 Interface_field_reference_expression* ifre =
2034 call->fn()->interface_field_reference_expression();
2035 Node* field_node = Node::make_node(ifre->expr());
2036 arg_nodes.push_back(field_node);
2037 }
2038
2039 if (call->args() != NULL)
2040 {
2041 for (Expression_list::const_iterator p = call->args()->begin();
2042 p != call->args()->end();
2043 ++p)
2044 arg_nodes.push_back(Node::make_node(*p));
2045 }
2046
2047 if (indirect)
2048 {
2049 // We don't know what happens to the parameters through indirect calls.
2050 // Be conservative and assume they all flow to theSink.
2051 for (std::vector<Node*>::iterator p = arg_nodes.begin();
2052 p != arg_nodes.end();
2053 ++p)
2054 {
2055 if (debug_level > 2)
2056 go_debug(call->location(),
2057 "esccall:: indirect call <- %s, untracked",
2058 (*p)->ast_format(gogo).c_str());
2059 this->assign(this->context_->sink(), *p);
2060 }
2061
2062 this->context_->init_retvals(call_node, fntype);
2063
2064 // It could be a closure call that returns captured variable.
2065 // Model this by flowing the func expression to result.
2066 // See issue #14409.
2067 Node* fn_node = Node::make_node(call->fn());
2068 std::vector<Node*> retvals = call_node->state(this->context_, NULL)->retvals;
2069 for (std::vector<Node*>::const_iterator p = retvals.begin();
2070 p != retvals.end();
2071 ++p)
2072 this->assign_deref(*p, fn_node);
2073
2074 return;
2075 }
2076
2077 // If FN is an untagged function.
2078 if (fn != NULL
2079 && fn->named_object()->is_function()
2080 && !fntype->is_tagged())
2081 {
2082 if (debug_level > 2)
2083 go_debug(call->location(), "esccall:: %s in recursive group",
2084 call_node->ast_format(gogo).c_str());
2085
2086 Function* f = fn->named_object()->func_value();
2087 const Bindings* callee_bindings = f->block()->bindings();
2088 Function::Results* results = f->result_variables();
2089 if (results != NULL)
2090 {
2091 // Setup output list on this call node.
2092 Node::Escape_state* state = call_node->state(this->context_, NULL);
2093 for (Function::Results::const_iterator p1 = results->begin();
2094 p1 != results->end();
2095 ++p1)
2096 {
2097 Node* result_node = Node::make_node(*p1);
2098 state->retvals.push_back(result_node);
2099 }
2100 }
2101
2102 std::vector<Node*>::iterator p = arg_nodes.begin();
2103 if (fntype->is_method())
2104 {
2105 std::string rcvr_name = fntype->receiver()->name();
2106 if (rcvr_name.empty() || Gogo::is_sink_name(rcvr_name)
2107 || !fntype->receiver()->type()->has_pointer())
2108 ;
2109 else
2110 {
2111 Named_object* rcvr_no =
2112 callee_bindings->lookup_local(fntype->receiver()->name());
2113 go_assert(rcvr_no != NULL);
2114 Node* rcvr_node = Node::make_node(rcvr_no);
2115 if (fntype->receiver()->type()->points_to() == NULL
2116 && (*p)->expr()->type()->points_to() != NULL)
2117 // This is a call to a value method that has been lowered into a call
2118 // to a pointer method. Gccgo generates a pointer method for all
2119 // method calls and takes the address of the value passed as the
2120 // receiver then immediately dereferences it within the function.
2121 // In this case, the receiver address does not escape; its content
2122 // flows to the call.
2123 this->assign_deref(rcvr_node, *p);
2124 else
2125 this->assign(rcvr_node, *p);
2126 }
2127 ++p;
2128 }
2129
2130 const Typed_identifier_list* til = fntype->parameters();
2131 if (til != NULL)
2132 {
2133 for (Typed_identifier_list::const_iterator p1 = til->begin();
2134 p1 != til->end();
2135 ++p1, ++p)
2136 {
2137 if (p1->name().empty() || Gogo::is_sink_name(p1->name()))
2138 continue;
2139
2140 Named_object* param_no =
2141 callee_bindings->lookup_local(p1->name());
2142 go_assert(param_no != NULL);
2143 Expression* arg = (*p)->expr();
2144 if (arg->var_expression() != NULL
2145 && arg->var_expression()->named_object() == param_no)
2146 continue;
2147
2148 Node* param_node = Node::make_node(param_no);
2149 this->assign(param_node, *p);
2150 }
2151
2152 for (; p != arg_nodes.end(); ++p)
2153 {
2154 if (debug_level > 2)
2155 go_debug(call->location(), "esccall:: ... <- %s, untracked",
2156 (*p)->ast_format(gogo).c_str());
2157 this->assign(this->context_->sink(), *p);
2158 }
2159 }
2160
2161 return;
2162 }
2163
2164 if (debug_level > 2)
2165 go_debug(call->location(), "esccall:: %s not recursive",
2166 call_node->ast_format(gogo).c_str());
2167
2168 Node::Escape_state* call_state = call_node->state(this->context_, NULL);
2169 if (!call_state->retvals.empty())
2170 go_error_at(Linemap::unknown_location(),
2171 "esc already decorated call %s",
2172 call_node->ast_format(gogo).c_str());
2173 this->context_->init_retvals(call_node, fntype);
2174
2175 // Receiver.
2176 std::vector<Node*>::iterator p = arg_nodes.begin();
2177 if (fntype->is_method()
2178 && p != arg_nodes.end())
2179 {
2180 // First argument to call will be the receiver.
2181 std::string* note = fntype->receiver()->note();
2182 if (fntype->receiver()->type()->points_to() == NULL
2183 && (*p)->expr()->type()->points_to() != NULL)
2184 // This is a call to a value method that has been lowered into a call
2185 // to a pointer method. Gccgo generates a pointer method for all
2186 // method calls and takes the address of the value passed as the
2187 // receiver then immediately dereferences it within the function.
2188 // In this case, the receiver address does not escape; its content
2189 // flows to the call.
2190 this->assign_from_note(note, call_state->retvals,
2191 this->context_->add_dereference(*p));
2192 else
2193 {
2194 if (!Type::are_identical(fntype->receiver()->type(),
2195 (*p)->expr()->type(), Type::COMPARE_TAGS,
2196 NULL))
2197 {
2198 // This will be converted later, preemptively track it instead
2199 // of its conversion expression which will show up in a later pass.
2200 this->context_->track(*p);
2201 }
2202 this->assign_from_note(note, call_state->retvals, *p);
2203 }
2204 p++;
2205 }
2206
2207 const Typed_identifier_list* til = fntype->parameters();
2208 if (til != NULL)
2209 {
2210 for (Typed_identifier_list::const_iterator pn = til->begin();
2211 pn != til->end() && p != arg_nodes.end();
2212 ++pn, ++p)
2213 {
2214 if (!Type::are_identical(pn->type(), (*p)->expr()->type(),
2215 Type::COMPARE_TAGS, NULL))
2216 {
2217 // This will be converted later, preemptively track it instead
2218 // of its conversion expression which will show up in a later pass.
2219 this->context_->track(*p);
2220 }
2221
2222 Type* t = pn->type();
2223 if (t != NULL
2224 && t->has_pointer())
2225 {
2226 std::string* note = pn->note();
2227 int enc = this->assign_from_note(note, call_state->retvals, *p);
2228 if (enc == Node::ESCAPE_NONE
2229 && !call->is_deferred()
2230 && !call->is_concurrent())
2231 {
2232 // TODO(cmang): Mark the argument as strictly non-escaping?
2233 // In the gc compiler this is for limiting the lifetime of
2234 // temporaries. We probably don't need this?
2235 }
2236 }
2237 }
2238
2239 for (; p != arg_nodes.end(); ++p)
2240 {
2241 if (debug_level > 2)
2242 go_debug(call->location(), "esccall:: ... <- %s, untracked",
2243 (*p)->ast_format(gogo).c_str());
2244 this->assign(this->context_->sink(), *p);
2245 }
2246 }
2247 }
2248
2249 // Model the assignment of DST to SRC.
2250 // Assert that SRC somehow gets assigned to DST.
2251 // DST might need to be examined for evaluations that happen inside of it.
2252 // For example, in [DST]*f(x) = [SRC]y, we lose track of the indirection and
2253 // DST becomes the sink in our model.
2254
2255 void
assign(Node * dst,Node * src)2256 Escape_analysis_assign::assign(Node* dst, Node* src)
2257 {
2258 Gogo* gogo = this->context_->gogo();
2259 int debug_level = gogo->debug_escape_level();
2260 if (debug_level > 1)
2261 go_debug(dst->location(), "[%d] %s escassign: %s(%s)[%s] = %s(%s)[%s]",
2262 this->context_->loop_depth(),
2263 strip_packed_prefix(gogo, this->context_->current_function_name()).c_str(),
2264 dst->ast_format(gogo).c_str(), dst->details().c_str(),
2265 dst->op_format().c_str(),
2266 src->ast_format(gogo).c_str(), src->details().c_str(),
2267 src->op_format().c_str());
2268
2269 if (dst->is_indirect())
2270 // Lose track of the dereference.
2271 dst = this->context_->sink();
2272 else if (dst->expr() != NULL)
2273 {
2274 // Analyze the lhs of the assignment.
2275 // Replace DST with this->context_->sink() if we can't track it.
2276 Expression* e = dst->expr();
2277 switch (e->classification())
2278 {
2279 case Expression::EXPRESSION_VAR_REFERENCE:
2280 {
2281 // If DST is a global variable, we have no way to track it.
2282 Named_object* var = e->var_expression()->named_object();
2283 if (var->is_variable() && var->var_value()->is_global())
2284 dst = this->context_->sink();
2285 }
2286 break;
2287
2288 case Expression::EXPRESSION_FIELD_REFERENCE:
2289 {
2290 Expression* strct = e->field_reference_expression()->expr();
2291 if (strct->heap_expression() != NULL)
2292 {
2293 // When accessing the field of a struct reference, we lose
2294 // track of the indirection.
2295 dst = this->context_->sink();
2296 break;
2297 }
2298
2299 // Treat DST.x = SRC as if it were DST = SRC.
2300 Node* struct_node = Node::make_node(strct);
2301 this->assign(struct_node, src);
2302 return;
2303 }
2304
2305 case Expression::EXPRESSION_ARRAY_INDEX:
2306 {
2307 Array_index_expression* are = e->array_index_expression();
2308 if (!are->array()->type()->is_slice_type())
2309 {
2310 // Treat DST[i] = SRC as if it were DST = SRC if DST if a fixed
2311 // array.
2312 Node* array_node = Node::make_node(are->array());
2313 this->assign(array_node, src);
2314 return;
2315 }
2316
2317 // Lose track of the slice dereference.
2318 dst = this->context_->sink();
2319 }
2320 break;
2321
2322 case Expression::EXPRESSION_UNARY:
2323 // Lose track of the dereference.
2324 if (e->unary_expression()->op() == OPERATOR_MULT)
2325 dst = this->context_->sink();
2326 break;
2327
2328 case Expression::EXPRESSION_MAP_INDEX:
2329 {
2330 // Lose track of the map's key and value.
2331 Expression* index = e->map_index_expression()->index();
2332 Node* index_node = Node::make_node(index);
2333 this->assign(this->context_->sink(), index_node);
2334
2335 dst = this->context_->sink();
2336 }
2337 break;
2338
2339 case Expression::EXPRESSION_TEMPORARY_REFERENCE:
2340 {
2341 // Temporary is tracked through the underlying Temporary_statement.
2342 Temporary_statement* t =
2343 dst->expr()->temporary_reference_expression()->statement();
2344 if (t->value_escapes())
2345 dst = this->context_->sink();
2346 else
2347 dst = Node::make_node(t);
2348 }
2349 break;
2350
2351 default:
2352 // TODO(cmang): Add debugging info here: only a few expressions
2353 // should leave DST unmodified.
2354 break;
2355 }
2356 }
2357
2358 if (src->object() != NULL)
2359 this->flows(dst, src);
2360 else if (src->is_indirect())
2361 this->flows(dst, src);
2362 else if (src->expr() != NULL)
2363 {
2364 Expression* e = src->expr();
2365 switch (e->classification())
2366 {
2367 case Expression::EXPRESSION_VAR_REFERENCE:
2368 case Expression::EXPRESSION_ENCLOSED_VAR_REFERENCE:
2369 // DST = var
2370 case Expression::EXPRESSION_HEAP:
2371 // DST = &T{...}.
2372 case Expression::EXPRESSION_FIXED_ARRAY_CONSTRUCTION:
2373 case Expression::EXPRESSION_SLICE_CONSTRUCTION:
2374 // DST = [...]T{...}.
2375 case Expression::EXPRESSION_MAP_CONSTRUCTION:
2376 // DST = map[T]V{...}.
2377 case Expression::EXPRESSION_STRUCT_CONSTRUCTION:
2378 // DST = T{...}.
2379 case Expression::EXPRESSION_SLICE_VALUE:
2380 // DST = slice{ptr, len, cap}
2381 case Expression::EXPRESSION_ALLOCATION:
2382 // DST = new(T).
2383 case Expression::EXPRESSION_BOUND_METHOD:
2384 // DST = x.M.
2385 case Expression::EXPRESSION_STRING_CONCAT:
2386 // DST = str1 + str2
2387 this->flows(dst, src);
2388 break;
2389
2390 case Expression::EXPRESSION_UNSAFE_CONVERSION:
2391 {
2392 Expression* underlying = e->unsafe_conversion_expression()->expr();
2393 Node* underlying_node = Node::make_node(underlying);
2394 this->assign(dst, underlying_node);
2395 }
2396 break;
2397
2398 case Expression::EXPRESSION_SLICE_INFO:
2399 {
2400 Slice_info_expression* sie = e->slice_info_expression();
2401 if (sie->info() == Expression::SLICE_INFO_VALUE_POINTER)
2402 {
2403 Node* slice = Node::make_node(sie->slice());
2404 this->assign(dst, slice);
2405 }
2406 }
2407 break;
2408
2409 case Expression::EXPRESSION_CALL:
2410 {
2411 Call_expression* call = e->call_expression();
2412 if (call->is_builtin())
2413 {
2414 Builtin_call_expression* bce = call->builtin_call_expression();
2415 switch (bce->code())
2416 {
2417 case Builtin_call_expression::BUILTIN_APPEND:
2418 {
2419 // Append returns the first argument.
2420 // The subsequent arguments are already leaked because
2421 // they are operands to append.
2422 Node* appendee = Node::make_node(call->args()->front());
2423 this->assign(dst, appendee);
2424 }
2425 break;
2426
2427 case Builtin_call_expression::BUILTIN_ADD:
2428 {
2429 // unsafe.Add(p, off).
2430 // Flow p to result.
2431 Node* arg = Node::make_node(call->args()->front());
2432 this->assign(dst, arg);
2433 }
2434 break;
2435
2436 case Builtin_call_expression::BUILTIN_SLICE:
2437 {
2438 // unsafe.Slice(p, len).
2439 // The resulting slice has the same backing store as p. Flow p to result.
2440 Node* arg = Node::make_node(call->args()->front());
2441 this->assign(dst, arg);
2442 }
2443 break;
2444
2445 case Builtin_call_expression::BUILTIN_LEN:
2446 case Builtin_call_expression::BUILTIN_CAP:
2447 case Builtin_call_expression::BUILTIN_COMPLEX:
2448 case Builtin_call_expression::BUILTIN_REAL:
2449 case Builtin_call_expression::BUILTIN_IMAG:
2450 case Builtin_call_expression::BUILTIN_RECOVER:
2451 case Builtin_call_expression::BUILTIN_ALIGNOF:
2452 case Builtin_call_expression::BUILTIN_OFFSETOF:
2453 case Builtin_call_expression::BUILTIN_SIZEOF:
2454 // these do not escape.
2455 break;
2456
2457 case Builtin_call_expression::BUILTIN_COPY:
2458 // handled in ::expression.
2459 break;
2460
2461 case Builtin_call_expression::BUILTIN_CLOSE:
2462 case Builtin_call_expression::BUILTIN_DELETE:
2463 case Builtin_call_expression::BUILTIN_PRINT:
2464 case Builtin_call_expression::BUILTIN_PRINTLN:
2465 case Builtin_call_expression::BUILTIN_PANIC:
2466 // these do not have result.
2467 // fallthrough
2468 case Builtin_call_expression::BUILTIN_MAKE:
2469 case Builtin_call_expression::BUILTIN_NEW:
2470 // should have been lowered to runtime calls at this point.
2471 // fallthrough
2472 default:
2473 go_unreachable();
2474 }
2475 break;
2476 }
2477 Func_expression* fe = call->fn()->func_expression();
2478 if (fe != NULL && fe->is_runtime_function())
2479 {
2480 switch (fe->runtime_code())
2481 {
2482 case Runtime::MAKECHAN:
2483 case Runtime::MAKECHAN64:
2484 case Runtime::MAKEMAP:
2485 case Runtime::MAKESLICE:
2486 case Runtime::MAKESLICE64:
2487 // DST = make(...).
2488 this->flows(dst, src);
2489 break;
2490
2491 default:
2492 break;
2493 }
2494 break;
2495 }
2496 else if (fe != NULL
2497 && fe->named_object()->is_function()
2498 && fe->named_object()->func_value()->is_method()
2499 && (call->is_deferred()
2500 || call->is_concurrent()))
2501 {
2502 // For a method call thunk, lose track of the call and treat it
2503 // as if DST = RECEIVER.
2504 Node* rcvr_node = Node::make_node(call->args()->front());
2505 this->assign(dst, rcvr_node);
2506 break;
2507 }
2508
2509 // Result flows to dst.
2510 Node* call_node = Node::make_node(e);
2511 Node::Escape_state* call_state = call_node->state(this->context_, NULL);
2512 std::vector<Node*> retvals = call_state->retvals;
2513 for (std::vector<Node*>::const_iterator p = retvals.begin();
2514 p != retvals.end();
2515 ++p)
2516 this->flows(dst, *p);
2517 }
2518 break;
2519
2520 case Expression::EXPRESSION_CALL_RESULT:
2521 {
2522 Call_result_expression* cre = e->call_result_expression();
2523 Call_expression* call = cre->call()->call_expression();
2524 if (call->is_builtin())
2525 break;
2526 if (call->fn()->func_expression() != NULL
2527 && call->fn()->func_expression()->is_runtime_function())
2528 {
2529 switch (call->fn()->func_expression()->runtime_code())
2530 {
2531 case Runtime::IFACEE2E2:
2532 case Runtime::IFACEI2E2:
2533 case Runtime::IFACEE2I2:
2534 case Runtime::IFACEI2I2:
2535 case Runtime::IFACEE2T2P:
2536 case Runtime::IFACEI2T2P:
2537 {
2538 // x, ok = v.(T), where T is a pointer or interface,
2539 // is lowered to
2540 // x, ok = IFACEI2E2(v), or
2541 // x, ok = IFACEI2I2(type, v)
2542 // The last arg flows to the first result.
2543 // Note: IFACEX2T2 has different signature, handled by
2544 // ::expression.
2545 if (cre->index() != 0)
2546 break;
2547 Node* arg_node = Node::make_node(call->args()->back());
2548 this->assign(dst, arg_node);
2549 }
2550 break;
2551
2552 default:
2553 break;
2554 }
2555 break;
2556 }
2557
2558 Node* call_node = Node::make_node(call);
2559 Node* ret_node = call_node->state(context_, NULL)->retvals[cre->index()];
2560 this->assign(dst, ret_node);
2561 }
2562 break;
2563
2564 case Expression::EXPRESSION_FUNC_REFERENCE:
2565 if (e->func_expression()->closure() != NULL)
2566 this->flows(dst, src);
2567 break;
2568
2569 case Expression::EXPRESSION_CONVERSION:
2570 {
2571 Type_conversion_expression* tce = e->conversion_expression();
2572 Type* ft = tce->expr()->type();
2573 Type* tt = tce->type();
2574 if ((ft->is_string_type() && tt->is_slice_type())
2575 || (ft->is_slice_type() && tt->is_string_type())
2576 || (ft->integer_type() != NULL && tt->is_string_type())
2577 || tt->interface_type() != NULL)
2578 {
2579 // string([]byte), string([]rune), []byte(string), []rune(string), string(rune),
2580 // interface(T)
2581 this->flows(dst, src);
2582 break;
2583 }
2584 // Conversion preserves input value.
2585 Expression* underlying = tce->expr();
2586 this->assign(dst, Node::make_node(underlying));
2587 }
2588 break;
2589
2590 case Expression::EXPRESSION_FIELD_REFERENCE:
2591 {
2592 // A non-pointer can't escape from a struct.
2593 if (!e->type()->has_pointer())
2594 break;
2595 }
2596 // Fall through.
2597
2598 case Expression::EXPRESSION_TYPE_GUARD:
2599 case Expression::EXPRESSION_ARRAY_INDEX:
2600 case Expression::EXPRESSION_STRING_INDEX:
2601 {
2602 Expression* left = NULL;
2603 if (e->field_reference_expression() != NULL)
2604 {
2605 left = e->field_reference_expression()->expr();
2606 if (left->unary_expression() != NULL
2607 && left->unary_expression()->op() == OPERATOR_MULT)
2608 {
2609 // DST = (*x).f
2610 this->flows(dst, src);
2611 break;
2612 }
2613 }
2614 else if (e->type_guard_expression() != NULL)
2615 left = e->type_guard_expression()->expr();
2616 else if (e->array_index_expression() != NULL)
2617 {
2618 Array_index_expression* aie = e->array_index_expression();
2619 if (aie->end() != NULL)
2620 // slicing
2621 if (aie->array()->type()->is_slice_type())
2622 left = aie->array();
2623 else
2624 {
2625 // slicing an array
2626 // The gc compiler has an implicit address operator.
2627 go_assert(src->child() != NULL);
2628 this->assign(dst, src->child());
2629 break;
2630 }
2631 else if (!aie->array()->type()->is_slice_type())
2632 {
2633 // Indexing an array preserves the input value.
2634 Node* array_node = Node::make_node(aie->array());
2635 this->assign(dst, array_node);
2636 break;
2637 }
2638 else
2639 {
2640 this->flows(dst, src);
2641 break;
2642 }
2643 }
2644 else if (e->string_index_expression() != NULL)
2645 {
2646 String_index_expression* sie = e->string_index_expression();
2647 if (e->type()->is_string_type())
2648 // slicing
2649 left = sie->string();
2650 else
2651 {
2652 this->flows(dst, src);
2653 break;
2654 }
2655 }
2656 go_assert(left != NULL);
2657
2658 // Conversions, field access, and slicing all preserve the input
2659 // value.
2660 Node* left_node = Node::make_node(left);
2661 this->assign(dst, left_node);
2662 }
2663 break;
2664
2665 case Expression::EXPRESSION_BINARY:
2666 {
2667 switch (e->binary_expression()->op())
2668 {
2669 case OPERATOR_PLUS:
2670 case OPERATOR_MINUS:
2671 case OPERATOR_XOR:
2672 case OPERATOR_OR:
2673 case OPERATOR_MULT:
2674 case OPERATOR_DIV:
2675 case OPERATOR_MOD:
2676 case OPERATOR_LSHIFT:
2677 case OPERATOR_RSHIFT:
2678 case OPERATOR_AND:
2679 case OPERATOR_BITCLEAR:
2680 {
2681 Node* left = Node::make_node(e->binary_expression()->left());
2682 this->assign(dst, left);
2683 Node* right = Node::make_node(e->binary_expression()->right());
2684 this->assign(dst, right);
2685 }
2686 break;
2687
2688 default:
2689 break;
2690 }
2691 }
2692 break;
2693
2694 case Expression::EXPRESSION_UNARY:
2695 {
2696 switch (e->unary_expression()->op())
2697 {
2698 case OPERATOR_PLUS:
2699 case OPERATOR_MINUS:
2700 case OPERATOR_XOR:
2701 {
2702 Node* op_node =
2703 Node::make_node(e->unary_expression()->operand());
2704 this->assign(dst, op_node);
2705 }
2706 break;
2707
2708 case OPERATOR_MULT:
2709 // DST = *x
2710 case OPERATOR_AND:
2711 // DST = &x
2712 this->flows(dst, src);
2713 break;
2714
2715 default:
2716 break;
2717 }
2718 }
2719 break;
2720
2721 case Expression::EXPRESSION_TEMPORARY_REFERENCE:
2722 {
2723 Statement* temp = e->temporary_reference_expression()->statement();
2724 this->assign(dst, Node::make_node(temp));
2725 }
2726 break;
2727
2728 case Expression::EXPRESSION_CONDITIONAL:
2729 {
2730 Conditional_expression* ce = e->conditional_expression();
2731 this->assign(dst, Node::make_node(ce->then_expr()));
2732 this->assign(dst, Node::make_node(ce->else_expr()));
2733 }
2734 break;
2735
2736 case Expression::EXPRESSION_COMPOUND:
2737 {
2738 Compound_expression* ce = e->compound_expression();
2739 this->assign(dst, Node::make_node(ce->expr()));
2740 }
2741 break;
2742
2743 default:
2744 // TODO(cmang): Add debug info here; this should not be reachable.
2745 // For now, just to be conservative, we'll just say dst flows to src.
2746 break;
2747 }
2748 }
2749 else if (src->statement() != NULL && src->statement()->temporary_statement() != NULL)
2750 this->flows(dst, src);
2751 }
2752
2753 // Model the assignment of DST to an indirection of SRC.
2754
2755 void
assign_deref(Node * dst,Node * src)2756 Escape_analysis_assign::assign_deref(Node* dst, Node* src)
2757 {
2758 if (src->expr() != NULL)
2759 {
2760 switch (src->expr()->classification())
2761 {
2762 case Expression::EXPRESSION_BOOLEAN:
2763 case Expression::EXPRESSION_STRING:
2764 case Expression::EXPRESSION_INTEGER:
2765 case Expression::EXPRESSION_FLOAT:
2766 case Expression::EXPRESSION_COMPLEX:
2767 case Expression::EXPRESSION_NIL:
2768 case Expression::EXPRESSION_IOTA:
2769 // No need to try indirections on literal values
2770 // or numeric constants.
2771 return;
2772
2773 default:
2774 break;
2775 }
2776 }
2777
2778 this->assign(dst, this->context_->add_dereference(src));
2779 }
2780
2781 // Model the input-to-output assignment flow of one of a function call's
2782 // arguments, where the flow is encoded in NOTE.
2783
2784 int
assign_from_note(std::string * note,const std::vector<Node * > & dsts,Node * src)2785 Escape_analysis_assign::assign_from_note(std::string* note,
2786 const std::vector<Node*>& dsts,
2787 Node* src)
2788 {
2789 int enc = Escape_note::parse_tag(note);
2790 if (src->expr() != NULL)
2791 {
2792 switch (src->expr()->classification())
2793 {
2794 case Expression::EXPRESSION_BOOLEAN:
2795 case Expression::EXPRESSION_STRING:
2796 case Expression::EXPRESSION_INTEGER:
2797 case Expression::EXPRESSION_FLOAT:
2798 case Expression::EXPRESSION_COMPLEX:
2799 case Expression::EXPRESSION_NIL:
2800 case Expression::EXPRESSION_IOTA:
2801 // There probably isn't a note for a literal value. Literal values
2802 // usually don't escape unless we lost track of the value some how.
2803 return enc;
2804
2805 default:
2806 break;
2807 }
2808 }
2809
2810 if (this->context_->gogo()->debug_escape_level() > 2)
2811 go_debug(src->location(), "assignfromtag:: src=%s em=%s",
2812 src->ast_format(context_->gogo()).c_str(),
2813 Escape_note::make_tag(enc).c_str());
2814
2815 if (enc == Node::ESCAPE_UNKNOWN)
2816 {
2817 // Lost track of the value.
2818 this->assign(this->context_->sink(), src);
2819 return enc;
2820 }
2821 else if (enc == Node::ESCAPE_NONE)
2822 return enc;
2823
2824 // If the content inside a parameter (reached via indirection) escapes to
2825 // the heap, mark it.
2826 if ((enc & ESCAPE_CONTENT_ESCAPES) != 0)
2827 this->assign(this->context_->sink(), this->context_->add_dereference(src));
2828
2829 int save_enc = enc;
2830 enc >>= ESCAPE_RETURN_BITS;
2831 for (std::vector<Node*>::const_iterator p = dsts.begin();
2832 enc != 0 && p != dsts.end();
2833 ++p)
2834 {
2835 // Prefer the lowest-level path to the reference (for escape purposes).
2836 // Two-bit encoding (for example. 1, 3, and 4 bits are other options)
2837 // 01 = 0-level
2838 // 10 = 1-level, (content escapes),
2839 // 11 = 2-level, (content of content escapes).
2840 int bits = enc & ESCAPE_BITS_MASK_FOR_TAG;
2841 if (bits > 0)
2842 {
2843 Node* n = src;
2844 for (int i = 0; i < bits - 1; ++i)
2845 {
2846 // Encode level > 0 as indirections.
2847 n = this->context_->add_dereference(n);
2848 }
2849 this->assign(*p, n);
2850 }
2851 enc >>= ESCAPE_BITS_PER_OUTPUT_IN_TAG;
2852 }
2853
2854 // If there are too many outputs to fit in the tag, that is handled on the
2855 // encoding end as ESCAPE_HEAP, so there is no need to check here.
2856 return save_enc;
2857 }
2858
2859 // Record the flow of SRC to DST in DST.
2860
2861 void
flows(Node * dst,Node * src)2862 Escape_analysis_assign::flows(Node* dst, Node* src)
2863 {
2864 // Don't bother capturing the flow from scalars.
2865 if (src->type() != NULL && !src->type()->has_pointer())
2866 return;
2867
2868 // Don't confuse a blank identifier with the sink.
2869 if (dst->is_sink() && dst != this->context_->sink())
2870 return;
2871
2872 Node::Escape_state* dst_state = dst->state(this->context_, NULL);
2873 Node::Escape_state* src_state = src->state(this->context_, NULL);
2874 if (dst == src
2875 || dst_state == src_state
2876 || dst_state->flows.find(src) != dst_state->flows.end())
2877 return;
2878
2879 Gogo* gogo = this->context_->gogo();
2880 if (gogo->debug_escape_level() > 2)
2881 go_debug(Linemap::unknown_location(), "flows:: %s <- %s",
2882 dst->ast_format(gogo).c_str(), src->ast_format(gogo).c_str());
2883
2884 if (dst_state->flows.empty())
2885 this->context_->add_dst(dst);
2886
2887 dst_state->flows.insert(src);
2888 }
2889
2890 // Build a connectivity graph between nodes in the function being analyzed.
2891
2892 void
assign_connectivity(Escape_context * context,Named_object * fn)2893 Gogo::assign_connectivity(Escape_context* context, Named_object* fn)
2894 {
2895 // Must be defined outside of this package.
2896 if (!fn->is_function())
2897 return;
2898
2899 int save_depth = context->loop_depth();
2900 context->set_loop_depth(1);
2901
2902 Escape_analysis_assign ea(context, fn);
2903 Function::Results* res = fn->func_value()->result_variables();
2904 if (res != NULL)
2905 {
2906 for (Function::Results::const_iterator p = res->begin();
2907 p != res->end();
2908 ++p)
2909 {
2910 Node* res_node = Node::make_node(*p);
2911 Node::Escape_state* res_state = res_node->state(context, fn);
2912 res_state->fn = fn;
2913 res_state->loop_depth = 0;
2914
2915 // If this set of functions is recursive, we lose track of the return values.
2916 // Just say that the result flows to the sink.
2917 if (context->recursive())
2918 ea.flows(context->sink(), res_node);
2919 }
2920 }
2921
2922 const Bindings* callee_bindings = fn->func_value()->block()->bindings();
2923 Function_type* fntype = fn->func_value()->type();
2924 Typed_identifier_list* params = (fntype->parameters() != NULL
2925 ? fntype->parameters()->copy()
2926 : new Typed_identifier_list);
2927 if (fntype->receiver() != NULL)
2928 params->push_back(*fntype->receiver());
2929
2930 for (Typed_identifier_list::const_iterator p = params->begin();
2931 p != params->end();
2932 ++p)
2933 {
2934 if (p->name().empty() || Gogo::is_sink_name(p->name()))
2935 continue;
2936
2937 Named_object* param_no = callee_bindings->lookup_local(p->name());
2938 go_assert(param_no != NULL);
2939 Node* param_node = Node::make_node(param_no);
2940 Node::Escape_state* param_state = param_node->state(context, fn);
2941 param_state->fn = fn;
2942 param_state->loop_depth = 1;
2943
2944 if (!p->type()->has_pointer())
2945 continue;
2946
2947 param_node->set_encoding(Node::ESCAPE_NONE);
2948 context->track(param_node);
2949 }
2950
2951 Escape_analysis_loop el;
2952 fn->func_value()->traverse(&el);
2953
2954 fn->func_value()->traverse(&ea);
2955 context->set_loop_depth(save_depth);
2956 }
2957
2958 class Escape_analysis_flood
2959 {
2960 public:
Escape_analysis_flood(Escape_context * context)2961 Escape_analysis_flood(Escape_context* context)
2962 : context_(context)
2963 { }
2964
2965 // Use the escape information in dst to update the escape information in src
2966 // and src's upstream.
2967 void
2968 flood(Level, Node* dst, Node* src, int);
2969
2970 private:
2971 // The escape context for the group of functions being flooded.
2972 Escape_context* context_;
2973 };
2974
2975 // Whenever we hit a dereference node, the level goes up by one, and whenever
2976 // we hit an address-of, the level goes down by one. as long as we're on a
2977 // level > 0 finding an address-of just means we're following the upstream
2978 // of a dereference, so this address doesn't leak (yet).
2979 // If level == 0, it means the /value/ of this node can reach the root of this
2980 // flood so if this node is an address-of, its argument should be marked as
2981 // escaping iff its current function and loop depth are different from the
2982 // flood's root.
2983 // Once an object has been moved to the heap, all of its upstream should be
2984 // considered escaping to the global scope.
2985 // This is an implementation of gc/esc.go:escwalkBody.
2986
2987 void
flood(Level level,Node * dst,Node * src,int extra_loop_depth)2988 Escape_analysis_flood::flood(Level level, Node* dst, Node* src,
2989 int extra_loop_depth)
2990 {
2991 // No need to flood src if it is a literal.
2992 if (src->expr() != NULL)
2993 {
2994 switch (src->expr()->classification())
2995 {
2996 case Expression::EXPRESSION_BOOLEAN:
2997 case Expression::EXPRESSION_STRING:
2998 case Expression::EXPRESSION_INTEGER:
2999 case Expression::EXPRESSION_FLOAT:
3000 case Expression::EXPRESSION_COMPLEX:
3001 case Expression::EXPRESSION_NIL:
3002 case Expression::EXPRESSION_IOTA:
3003 return;
3004
3005 default:
3006 break;
3007 }
3008 }
3009
3010 Node::Escape_state* src_state = src->state(this->context_, NULL);
3011 if (src_state->flood_id == this->context_->flood_id())
3012 {
3013 // Esclevels are vectors, do not compare as integers,
3014 // and must use "min" of old and new to guarantee
3015 // convergence.
3016 level = level.min(src_state->level);
3017 if (level == src_state->level)
3018 {
3019 // Have we been here already with an extraloopdepth,
3020 // or is the extraloopdepth provided no improvement on
3021 // what's already been seen?
3022 if (src_state->max_extra_loop_depth >= extra_loop_depth
3023 || src_state->loop_depth >= extra_loop_depth)
3024 return;
3025 src_state->max_extra_loop_depth = extra_loop_depth;
3026 }
3027 }
3028 else
3029 src_state->max_extra_loop_depth = -1;
3030
3031 src_state->flood_id = this->context_->flood_id();
3032 src_state->level = level;
3033 int mod_loop_depth = std::max(extra_loop_depth, src_state->loop_depth);
3034
3035 Gogo* gogo = this->context_->gogo();
3036 int debug_level = gogo->debug_escape_level();
3037 if (debug_level > 1)
3038 go_debug(Linemap::unknown_location(),
3039 "escwalk: level:{%d %d} depth:%d "
3040 "op=%s %s(%s) "
3041 "scope:%s[%d] "
3042 "extraloopdepth=%d",
3043 level.value(), level.suffix_value(), this->context_->pdepth(),
3044 src->op_format().c_str(),
3045 src->ast_format(gogo).c_str(),
3046 src->details().c_str(),
3047 debug_function_name(src_state->fn).c_str(),
3048 src_state->loop_depth,
3049 extra_loop_depth);
3050
3051 this->context_->increase_pdepth();
3052
3053 // Input parameter flowing into output parameter?
3054 Named_object* src_no = NULL;
3055 if (src->expr() != NULL && src->expr()->var_expression() != NULL)
3056 src_no = src->expr()->var_expression()->named_object();
3057 else
3058 src_no = src->object();
3059 bool src_is_param = (src_no != NULL
3060 && src_no->is_variable()
3061 && src_no->var_value()->is_parameter());
3062
3063 Named_object* dst_no = NULL;
3064 if (dst->expr() != NULL && dst->expr()->var_expression() != NULL)
3065 dst_no = dst->expr()->var_expression()->named_object();
3066 else
3067 dst_no = dst->object();
3068 bool dst_is_result = dst_no != NULL && dst_no->is_result_variable();
3069 Node::Escape_state* dst_state = dst->state(this->context_, NULL);
3070
3071 if (src_is_param
3072 && dst_is_result
3073 && src_state->fn == dst_state->fn
3074 && (src->encoding() & ESCAPE_MASK) < int(Node::ESCAPE_HEAP)
3075 && dst->encoding() != Node::ESCAPE_HEAP)
3076 {
3077 // This case handles:
3078 // 1. return in
3079 // 2. return &in
3080 // 3. tmp := in; return &tmp
3081 // 4. return *in
3082 if (debug_level != 0)
3083 {
3084 if (debug_level == 1)
3085 go_debug(src->definition_location(),
3086 "leaking param: %s to result %s level=%d",
3087 src->ast_format(gogo).c_str(),
3088 dst->ast_format(gogo).c_str(),
3089 level.value());
3090 else
3091 go_debug(src->definition_location(),
3092 "leaking param: %s to result %s level={%d %d}",
3093 src->ast_format(gogo).c_str(),
3094 dst->ast_format(gogo).c_str(),
3095 level.value(), level.suffix_value());
3096 }
3097
3098 if ((src->encoding() & ESCAPE_MASK) != Node::ESCAPE_RETURN)
3099 {
3100 int enc =
3101 Node::ESCAPE_RETURN | (src->encoding() & ESCAPE_CONTENT_ESCAPES);
3102 src->set_encoding(enc);
3103 }
3104
3105 int enc = Node::note_inout_flows(src->encoding(),
3106 dst_no->result_var_value()->index(),
3107 level);
3108 src->set_encoding(enc);
3109
3110 // In gc/esc.go:escwalkBody, this is a goto to the label for recursively
3111 // flooding the connection graph. Inlined here for convenience.
3112 level = level.copy();
3113 for (std::set<Node*>::const_iterator p = src_state->flows.begin();
3114 p != src_state->flows.end();
3115 ++p)
3116 this->flood(level, dst, *p, extra_loop_depth);
3117 return;
3118 }
3119
3120 // If parameter content escape to heap, set ESCAPE_CONTENT_ESCAPES.
3121 // Note minor confusion around escape from pointer-to-struct vs
3122 // escape from struct.
3123 if (src_is_param
3124 && dst->encoding() == Node::ESCAPE_HEAP
3125 && (src->encoding() & ESCAPE_MASK) < int(Node::ESCAPE_HEAP)
3126 && level.value() > 0)
3127 {
3128 int enc =
3129 Node::max_encoding((src->encoding() | ESCAPE_CONTENT_ESCAPES),
3130 Node::ESCAPE_NONE);
3131 src->set_encoding(enc);
3132 if (debug_level != 0)
3133 go_debug(src->definition_location(), "mark escaped content: %s",
3134 src->ast_format(gogo).c_str());
3135 }
3136
3137 // A src object leaks if its value or address is assigned to a dst object
3138 // in a different scope (at a different loop depth).
3139 bool src_leaks = (level.value() <= 0
3140 && level.suffix_value() <= 0
3141 && dst_state->loop_depth < mod_loop_depth);
3142 src_leaks = src_leaks || (level.value() <= 0
3143 && (dst->encoding() & ESCAPE_MASK) == Node::ESCAPE_HEAP);
3144 // old src encoding, used to prevent duplicate error messages
3145 int osrcesc = src->encoding();
3146
3147 if (src_is_param
3148 && (src_leaks || dst_state->loop_depth < 0)
3149 && (src->encoding() & ESCAPE_MASK) < int(Node::ESCAPE_HEAP))
3150 {
3151 if (level.suffix_value() > 0)
3152 {
3153 int enc =
3154 Node::max_encoding((src->encoding() | ESCAPE_CONTENT_ESCAPES),
3155 Node::ESCAPE_NONE);
3156 src->set_encoding(enc);
3157 if (debug_level != 0 && osrcesc != src->encoding())
3158 go_debug(src->definition_location(), "leaking param content: %s",
3159 src->ast_format(gogo).c_str());
3160 }
3161 else
3162 {
3163 if (debug_level != 0)
3164 go_debug(src->definition_location(), "leaking param: %s",
3165 src->ast_format(gogo).c_str());
3166 src->set_encoding(Node::ESCAPE_HEAP);
3167 }
3168 }
3169 else if (src->expr() != NULL)
3170 {
3171 Expression* e = src->expr();
3172 if (e->enclosed_var_expression() != NULL)
3173 {
3174 if (src_leaks && debug_level != 0)
3175 go_debug(src->location(), "leaking closure reference %s",
3176 src->ast_format(gogo).c_str());
3177
3178 Node* enclosed_node =
3179 Node::make_node(e->enclosed_var_expression()->variable());
3180 this->flood(level, dst, enclosed_node, -1);
3181 }
3182 else if (e->heap_expression() != NULL
3183 || (e->unary_expression() != NULL
3184 && e->unary_expression()->op() == OPERATOR_AND))
3185 {
3186 // Pointer literals and address-of expressions.
3187 Expression* underlying;
3188 if (e->heap_expression())
3189 underlying = e->heap_expression()->expr();
3190 else
3191 underlying = e->unary_expression()->operand();
3192 Node* underlying_node = Node::make_node(underlying);
3193
3194 // If the address leaks, the underyling object must be moved
3195 // to the heap.
3196 underlying->address_taken(src_leaks);
3197 if (src_leaks)
3198 {
3199 src->set_encoding(Node::ESCAPE_HEAP);
3200 if (osrcesc != src->encoding())
3201 {
3202 move_to_heap(gogo, underlying);
3203 if (debug_level > 1)
3204 go_debug(src->location(),
3205 "%s escapes to heap, level={%d %d}, "
3206 "dst.eld=%d, src.eld=%d",
3207 src->ast_format(gogo).c_str(), level.value(),
3208 level.suffix_value(), dst_state->loop_depth,
3209 mod_loop_depth);
3210 else if (debug_level > 0)
3211 go_debug(src->location(), "%s escapes to heap",
3212 src->ast_format(gogo).c_str());
3213 }
3214
3215 this->flood(level.decrease(), dst,
3216 underlying_node, mod_loop_depth);
3217 extra_loop_depth = mod_loop_depth;
3218 }
3219 else
3220 {
3221 // Decrease the level each time we take the address of the object.
3222 this->flood(level.decrease(), dst, underlying_node, -1);
3223 }
3224 }
3225 else if (e->slice_literal() != NULL)
3226 {
3227 Slice_construction_expression* slice = e->slice_literal();
3228 if (slice->vals() != NULL)
3229 {
3230 for (Expression_list::const_iterator p = slice->vals()->begin();
3231 p != slice->vals()->end();
3232 ++p)
3233 {
3234 if ((*p) != NULL)
3235 this->flood(level.decrease(), dst, Node::make_node(*p), -1);
3236 }
3237 }
3238 if (src_leaks)
3239 {
3240 src->set_encoding(Node::ESCAPE_HEAP);
3241 if (debug_level != 0 && osrcesc != src->encoding())
3242 go_debug(src->location(), "%s escapes to heap",
3243 src->ast_format(gogo).c_str());
3244 extra_loop_depth = mod_loop_depth;
3245 }
3246 }
3247 else if (e->call_expression() != NULL)
3248 {
3249 Call_expression* call = e->call_expression();
3250 if (call->is_builtin())
3251 {
3252 Builtin_call_expression* bce = call->builtin_call_expression();
3253 if (bce->code() == Builtin_call_expression::BUILTIN_APPEND)
3254 {
3255 // Propagate escape information to appendee.
3256 Expression* appendee = call->args()->front();
3257 this->flood(level, dst, Node::make_node(appendee), -1);
3258 }
3259 }
3260 else if (call->fn()->func_expression() != NULL
3261 && call->fn()->func_expression()->is_runtime_function())
3262 {
3263 switch (call->fn()->func_expression()->runtime_code())
3264 {
3265 case Runtime::MAKECHAN:
3266 case Runtime::MAKECHAN64:
3267 case Runtime::MAKEMAP:
3268 case Runtime::MAKESLICE:
3269 case Runtime::MAKESLICE64:
3270 if (src_leaks)
3271 {
3272 src->set_encoding(Node::ESCAPE_HEAP);
3273 if (debug_level != 0 && osrcesc != src->encoding())
3274 go_debug(src->location(), "%s escapes to heap",
3275 src->ast_format(gogo).c_str());
3276 extra_loop_depth = mod_loop_depth;
3277 }
3278 break;
3279
3280 default:
3281 break;
3282 }
3283 }
3284 else if (src_state->retvals.size() > 0)
3285 {
3286 // In this case a link went directly to a call, but should really go
3287 // to the dummy .outN outputs that were created for the call that
3288 // themselves link to the inputs with levels adjusted.
3289 // See e.g. #10466.
3290 // This can only happen with functions returning a single result.
3291 go_assert(src_state->retvals.size() == 1);
3292 if (debug_level > 2)
3293 go_debug(src->location(), "[%d] dst %s escwalk replace src: %s with %s",
3294 this->context_->loop_depth(),
3295 dst->ast_format(gogo).c_str(),
3296 src->ast_format(gogo).c_str(),
3297 src_state->retvals[0]->ast_format(gogo).c_str());
3298 src = src_state->retvals[0];
3299 src_state = src->state(this->context_, NULL);
3300 }
3301 }
3302 else if (e->allocation_expression() != NULL && src_leaks)
3303 {
3304 // Calls to Runtime::NEW get lowered into an allocation expression.
3305 src->set_encoding(Node::ESCAPE_HEAP);
3306 if (debug_level != 0 && osrcesc != src->encoding())
3307 go_debug(src->location(), "%s escapes to heap",
3308 src->ast_format(gogo).c_str());
3309 extra_loop_depth = mod_loop_depth;
3310 }
3311 else if ((e->map_literal() != NULL
3312 || e->string_concat_expression() != NULL
3313 || (e->func_expression() != NULL && e->func_expression()->closure() != NULL)
3314 || e->bound_method_expression() != NULL)
3315 && src_leaks)
3316 {
3317 src->set_encoding(Node::ESCAPE_HEAP);
3318 if (debug_level != 0 && osrcesc != src->encoding())
3319 go_debug(src->location(), "%s escapes to heap",
3320 src->ast_format(gogo).c_str());
3321 extra_loop_depth = mod_loop_depth;
3322 }
3323 else if (e->conversion_expression() != NULL && src_leaks)
3324 {
3325 Type_conversion_expression* tce = e->conversion_expression();
3326 Type* ft = tce->expr()->type();
3327 Type* tt = tce->type();
3328 if ((ft->is_string_type() && tt->is_slice_type())
3329 || (ft->is_slice_type() && tt->is_string_type())
3330 || (ft->integer_type() != NULL && tt->is_string_type())
3331 || tt->interface_type() != NULL)
3332 {
3333 // string([]byte), string([]rune), []byte(string), []rune(string), string(rune),
3334 // interface(T)
3335 src->set_encoding(Node::ESCAPE_HEAP);
3336 if (debug_level != 0 && osrcesc != src->encoding())
3337 go_debug(src->location(), "%s escapes to heap",
3338 src->ast_format(gogo).c_str());
3339 extra_loop_depth = mod_loop_depth;
3340 if (tt->interface_type() != NULL
3341 && ft->has_pointer()
3342 && !ft->is_direct_iface_type())
3343 // We're converting from a non-direct interface type.
3344 // The interface will hold a heap copy of the data
3345 // Flow the data to heap. See issue 29353.
3346 this->flood(level, this->context_->sink(),
3347 Node::make_node(tce->expr()), -1);
3348 }
3349 }
3350 else if (e->array_index_expression() != NULL
3351 && !e->array_index_expression()->array()->type()->is_slice_type())
3352 {
3353 Array_index_expression* aie = e->array_index_expression();
3354 if (aie->end() != NULL)
3355 {
3356 // Slicing an array.
3357 // Flow its implicit address-of node to DST.
3358 this->flood(level, dst, src->child(), -1);
3359 }
3360 else
3361 {
3362 // Indexing an array.
3363 // An array element flowing to DST behaves like the array
3364 // flowing to DST.
3365 Expression* underlying = e->array_index_expression()->array();
3366 Node* underlying_node = Node::make_node(underlying);
3367 this->flood(level, dst, underlying_node, -1);
3368 }
3369 }
3370 else if ((e->field_reference_expression() != NULL
3371 && e->field_reference_expression()->expr()->unary_expression() == NULL)
3372 || e->type_guard_expression() != NULL
3373 || (e->array_index_expression() != NULL
3374 && e->array_index_expression()->end() != NULL)
3375 || (e->string_index_expression() != NULL
3376 && e->type()->is_string_type()))
3377 {
3378 Expression* underlying;
3379 if (e->field_reference_expression() != NULL)
3380 underlying = e->field_reference_expression()->expr();
3381 else if (e->type_guard_expression() != NULL)
3382 underlying = e->type_guard_expression()->expr();
3383 else if (e->array_index_expression() != NULL)
3384 underlying = e->array_index_expression()->array();
3385 else
3386 underlying = e->string_index_expression()->string();
3387
3388 Node* underlying_node = Node::make_node(underlying);
3389 this->flood(level, dst, underlying_node, -1);
3390 }
3391 else if ((e->field_reference_expression() != NULL
3392 && e->field_reference_expression()->expr()->unary_expression() != NULL)
3393 || e->array_index_expression() != NULL
3394 || e->map_index_expression() != NULL
3395 || (e->unary_expression() != NULL
3396 && e->unary_expression()->op() == OPERATOR_MULT))
3397 {
3398 Expression* underlying;
3399 if (e->field_reference_expression() != NULL)
3400 {
3401 underlying = e->field_reference_expression()->expr();
3402 underlying = underlying->unary_expression()->operand();
3403 }
3404 else if (e->array_index_expression() != NULL)
3405 underlying = e->array_index_expression()->array();
3406 else if (e->map_index_expression() != NULL)
3407 underlying = e->map_index_expression()->map();
3408 else
3409 underlying = e->unary_expression()->operand();
3410
3411 // Increase the level for a dereference.
3412 Node* underlying_node = Node::make_node(underlying);
3413 this->flood(level.increase(), dst, underlying_node, -1);
3414 }
3415 else if (e->temporary_reference_expression() != NULL)
3416 {
3417 Statement* t = e->temporary_reference_expression()->statement();
3418 this->flood(level, dst, Node::make_node(t), -1);
3419 }
3420 }
3421 else if (src->is_indirect())
3422 // Increase the level for a dereference.
3423 this->flood(level.increase(), dst, src->child(), -1);
3424
3425 level = level.copy();
3426 for (std::set<Node*>::const_iterator p = src_state->flows.begin();
3427 p != src_state->flows.end();
3428 ++p)
3429 this->flood(level, dst, *p, extra_loop_depth);
3430
3431 this->context_->decrease_pdepth();
3432 }
3433
3434 // Propagate escape information across the nodes modeled in this Analysis_set.
3435 // This is an implementation of gc/esc.go:escflood.
3436
3437 void
propagate_escape(Escape_context * context,Node * dst)3438 Gogo::propagate_escape(Escape_context* context, Node* dst)
3439 {
3440 if (dst->object() == NULL
3441 && (dst->expr() == NULL
3442 || (dst->expr()->var_expression() == NULL
3443 && dst->expr()->enclosed_var_expression() == NULL
3444 && dst->expr()->func_expression() == NULL)))
3445 return;
3446
3447 Node::Escape_state* state = dst->state(context, NULL);
3448 Gogo* gogo = context->gogo();
3449 if (gogo->debug_escape_level() > 1)
3450 go_debug(Linemap::unknown_location(), "escflood:%d: dst %s scope:%s[%d]",
3451 context->flood_id(), dst->ast_format(gogo).c_str(),
3452 debug_function_name(state->fn).c_str(),
3453 state->loop_depth);
3454
3455 Escape_analysis_flood eaf(context);
3456 for (std::set<Node*>::const_iterator p = state->flows.begin();
3457 p != state->flows.end();
3458 ++p)
3459 {
3460 context->increase_flood_id();
3461 eaf.flood(Level::From(0), dst, *p, -1);
3462 }
3463 }
3464
3465 class Escape_analysis_tag
3466 {
3467 public:
Escape_analysis_tag(Escape_context * context)3468 Escape_analysis_tag(Escape_context* context)
3469 : context_(context)
3470 { }
3471
3472 // Add notes to the function's type about the escape information of its
3473 // input parameters.
3474 void
3475 tag(Named_object* fn);
3476
3477 private:
3478 Escape_context* context_;
3479 };
3480
3481 void
tag(Named_object * fn)3482 Escape_analysis_tag::tag(Named_object* fn)
3483 {
3484 // External functions are assumed unsafe
3485 // unless //go:noescape is given before the declaration.
3486 if (fn->is_function_declaration())
3487 {
3488 Function_declaration* fdcl = fn->func_declaration_value();
3489 if ((fdcl->pragmas() & GOPRAGMA_NOESCAPE) != 0)
3490 {
3491 Function_type* fntype = fdcl->type();
3492 if (fntype->parameters() != NULL)
3493 {
3494 const Typed_identifier_list* til = fntype->parameters();
3495 int i = 0;
3496 for (Typed_identifier_list::const_iterator p = til->begin();
3497 p != til->end();
3498 ++p, ++i)
3499 if (p->type()->has_pointer())
3500 fntype->add_parameter_note(i, Node::ESCAPE_NONE);
3501 }
3502 }
3503 }
3504
3505 if (!fn->is_function())
3506 return;
3507
3508 Function_type* fntype = fn->func_value()->type();
3509 Bindings* bindings = fn->func_value()->block()->bindings();
3510
3511 if (fntype->is_method())
3512 {
3513 if (fntype->receiver()->name().empty()
3514 || Gogo::is_sink_name(fntype->receiver()->name()))
3515 // Unnamed receiver is not used in the function body, does not escape.
3516 fntype->add_receiver_note(Node::ESCAPE_NONE);
3517 else
3518 {
3519 Named_object* rcvr_no = bindings->lookup(fntype->receiver()->name());
3520 go_assert(rcvr_no != NULL);
3521 Node* rcvr_node = Node::make_node(rcvr_no);
3522 switch ((rcvr_node->encoding() & ESCAPE_MASK))
3523 {
3524 case Node::ESCAPE_NONE: // not touched by flood
3525 case Node::ESCAPE_RETURN:
3526 if (fntype->receiver()->type()->has_pointer())
3527 // Don't bother tagging for scalars.
3528 fntype->add_receiver_note(rcvr_node->encoding());
3529 break;
3530
3531 case Node::ESCAPE_HEAP: // flooded, moved to heap.
3532 break;
3533
3534 default:
3535 break;
3536 }
3537 }
3538 }
3539
3540 int i = 0;
3541 if (fntype->parameters() != NULL)
3542 {
3543 const Typed_identifier_list* til = fntype->parameters();
3544 for (Typed_identifier_list::const_iterator p = til->begin();
3545 p != til->end();
3546 ++p, ++i)
3547 {
3548 if (p->name().empty() || Gogo::is_sink_name(p->name()))
3549 {
3550 // Parameter not used in the function body, does not escape.
3551 if (p->type()->has_pointer())
3552 fntype->add_parameter_note(i, Node::ESCAPE_NONE);
3553 continue;
3554 }
3555
3556 Named_object* param_no = bindings->lookup(p->name());
3557 go_assert(param_no != NULL);
3558 Node* param_node = Node::make_node(param_no);
3559 switch ((param_node->encoding() & ESCAPE_MASK))
3560 {
3561 case Node::ESCAPE_NONE: // not touched by flood
3562 case Node::ESCAPE_RETURN:
3563 if (p->type()->has_pointer())
3564 // Don't bother tagging for scalars.
3565 fntype->add_parameter_note(i, param_node->encoding());
3566 break;
3567
3568 case Node::ESCAPE_HEAP: // flooded, moved to heap.
3569 break;
3570
3571 default:
3572 break;
3573 }
3574 }
3575 }
3576 fntype->set_is_tagged();
3577 }
3578
3579 // Tag each top-level function with escape information that will be used to
3580 // retain analysis results across imports.
3581
3582 void
tag_function(Escape_context * context,Named_object * fn)3583 Gogo::tag_function(Escape_context* context, Named_object* fn)
3584 {
3585 Escape_analysis_tag eat(context);
3586 eat.tag(fn);
3587 }
3588
3589 // Reclaim memory of escape analysis Nodes.
3590
3591 void
reclaim_escape_nodes()3592 Gogo::reclaim_escape_nodes()
3593 {
3594 Node::reclaim_nodes();
3595 }
3596
3597 void
reclaim_nodes()3598 Node::reclaim_nodes()
3599 {
3600 for (Unordered_map(Named_object*, Node*)::iterator p =
3601 Node::objects.begin();
3602 p != Node::objects.end();
3603 ++p)
3604 delete p->second;
3605 Node::objects.clear();
3606
3607 for (Unordered_map(Expression*, Node*)::iterator p =
3608 Node::expressions.begin();
3609 p != Node::expressions.end();
3610 ++p)
3611 delete p->second;
3612 Node::expressions.clear();
3613
3614 for (Unordered_map(Statement*, Node*)::iterator p =
3615 Node::statements.begin();
3616 p != Node::statements.end();
3617 ++p)
3618 delete p->second;
3619 Node::statements.clear();
3620
3621 for (std::vector<Node*>::iterator p = Node::indirects.begin();
3622 p != Node::indirects.end();
3623 ++p)
3624 delete *p;
3625 Node::indirects.clear();
3626 }
3627