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