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