?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
compiler: stack allocate defer thunk
[official-gcc.git] / gcc / go / gofrontend / escape.cc
blob65ccf9bd0db015b5d085564f89dd4dafbeef3655
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 {
1424 // Defer statement may need to allocate a thunk. When it is
1425 // not inside a loop, this can be stack allocated, as it
1426 // runs before the function finishes.
1427 Node* n = Node::make_node(s);
1428 n->set_encoding(Node::ESCAPE_NONE);
1429 break;
1430 }
1431 // fallthrough
1432
1433 case Statement::STATEMENT_GO:
1434 {
1435 // Defer f(x) or go f(x).
1436 // Both f and x escape to the heap.
1437 Thunk_statement* thunk = s->thunk_statement();
1438 if (thunk->call()->call_expression() == NULL)
1439 break;
1440
1441 Call_expression* call = thunk->call()->call_expression();
1442 Node* func_node = Node::make_node(call->fn());
1443 this->assign(this->context_->sink(), func_node);
1444 if (call->args() != NULL)
1445 {
1446 for (Expression_list::const_iterator p = call->args()->begin();
1447 p != call->args()->end();
1448 ++p)
1449 {
1450 Node* arg_node = Node::make_node(*p);
1451 this->assign(this->context_->sink(), arg_node);
1452 }
1453 }
1454 }
1455 break;
1456
1457 default:
1458 break;
1459 }
1460 return TRAVERSE_SKIP_COMPONENTS;
1461 }
1462
1463 // Model expressions within a function as assignments and flows between nodes.
1464
1465 int
1466 Escape_analysis_assign::expression(Expression** pexpr)
1467 {
1468 Gogo* gogo = this->context_->gogo();
1469 int debug_level = gogo->debug_escape_level();
1470
1471 // Big stuff escapes unconditionally.
1472 Node* n = Node::make_node(*pexpr);
1473 if ((n->encoding() & ESCAPE_MASK) != int(Node::ESCAPE_HEAP)
1474 && n->is_big(this->context_))
1475 {
1476 if (debug_level > 1)
1477 go_inform((*pexpr)->location(), "%s too large for stack",
1478 n->ast_format(gogo).c_str());
1479 if (debug_level != 0
1480 && ((*pexpr)->var_expression() != NULL
1481 || (*pexpr)->enclosed_var_expression() != NULL))
1482 go_inform(n->definition_location(),
1483 "moved to heap: %s",
1484 n->ast_format(gogo).c_str());
1485
1486 n->set_encoding(Node::ESCAPE_HEAP);
1487 (*pexpr)->address_taken(true);
1488 this->assign(this->context_->sink(), n);
1489 }
1490
1491 if ((*pexpr)->func_expression() == NULL)
1492 (*pexpr)->traverse_subexpressions(this);
1493
1494 if (debug_level > 1)
1495 {
1496 Node* n = Node::make_node(*pexpr);
1497 std::string fn_name = this->context_->current_function_name();
1498 go_inform((*pexpr)->location(), "[%d] %s esc: %s",
1499 this->context_->loop_depth(), fn_name.c_str(),
1500 n->ast_format(gogo).c_str());
1501 }
1502
1503 switch ((*pexpr)->classification())
1504 {
1505 case Expression::EXPRESSION_CALL:
1506 {
1507 Call_expression* call = (*pexpr)->call_expression();
1508 if (call->is_builtin())
1509 {
1510 Builtin_call_expression* bce = call->builtin_call_expression();
1511 switch (bce->code())
1512 {
1513 case Builtin_call_expression::BUILTIN_PANIC:
1514 {
1515 // Argument could leak through recover.
1516 Node* panic_arg = Node::make_node(call->args()->front());
1517 this->assign(this->context_->sink(), panic_arg);
1518 }
1519 break;
1520
1521 case Builtin_call_expression::BUILTIN_APPEND:
1522 {
1523 // The contents being appended leak.
1524 if (call->is_varargs())
1525 {
1526 // append(slice1, slice2...) -- slice2 itself does not escape, but contents do
1527 Node* appended = Node::make_node(call->args()->back());
1528 this->assign_deref(this->context_->sink(), appended);
1529 if (debug_level > 2)
1530 go_inform((*pexpr)->location(),
1531 "special treatment of append(slice1, slice2...)");
1532 }
1533 else
1534 {
1535 for (Expression_list::const_iterator pa =
1536 call->args()->begin() + 1;
1537 pa != call->args()->end();
1538 ++pa)
1539 {
1540 Node* arg = Node::make_node(*pa);
1541 this->assign(this->context_->sink(), arg);
1542 }
1543 }
1544
1545 // The content of the original slice leaks as well.
1546 Node* appendee = Node::make_node(call->args()->front());
1547 this->assign_deref(this->context_->sink(), appendee);
1548 }
1549 break;
1550
1551 case Builtin_call_expression::BUILTIN_COPY:
1552 {
1553 // Lose track of the copied content.
1554 Node* copied = Node::make_node(call->args()->back());
1555 this->assign_deref(this->context_->sink(), copied);
1556 }
1557 break;
1558
1559 default:
1560 break;
1561 }
1562 break;
1563 }
1564 Func_expression* fe = call->fn()->func_expression();
1565 if (fe != NULL && fe->is_runtime_function())
1566 {
1567 switch (fe->runtime_code())
1568 {
1569 case Runtime::MAKECHAN:
1570 case Runtime::MAKEMAP:
1571 case Runtime::MAKESLICE:
1572 case Runtime::MAKESLICE64:
1573 this->context_->track(n);
1574 break;
1575
1576 case Runtime::MAPASSIGN:
1577 {
1578 // Map key escapes. The last argument is the address
1579 // of the key.
1580 Node* key_node = Node::make_node(call->args()->back());
1581 this->assign_deref(this->context_->sink(), key_node);
1582 }
1583 break;
1584
1585 case Runtime::SELECTSEND:
1586 {
1587 // Send to a channel, lose track. The last argument is
1588 // the address of the value to send.
1589 Node* arg_node = Node::make_node(call->args()->back());
1590 this->assign_deref(this->context_->sink(), arg_node);
1591 }
1592 break;
1593
1594 case Runtime::IFACEE2T2:
1595 case Runtime::IFACEI2T2:
1596 {
1597 // x, ok = v.(T), where T is non-pointer non-interface,
1598 // is lowered to
1599 // ok = IFACEI2T2(type, v, (void*)&tmp_x)
1600 // Here v flows to tmp_x.
1601 // Note: other IFACEX2Y2 returns the conversion result.
1602 // Those are handled in ::assign.
1603 Node* src_node = Node::make_node(call->args()->at(1));
1604 Node* dst_node;
1605 Expression* arg2 = call->args()->at(2);
1606 // Try to pull tmp_x out of the arg2 expression, and let v
1607 // flows into it, instead of simply dereference arg2,
1608 // which looks like dereference of an arbitrary pointer
1609 // and causes v immediately escape.
1610 // The expression form matches statement.cc,
1611 // Tuple_type_guard_assignment_statement::lower_to_object_type.
1612 Unary_expression* ue =
1613 (arg2->conversion_expression() != NULL
1614 ? arg2->conversion_expression()->expr()->unary_expression()
1615 : arg2->unary_expression());
1616 if (ue != NULL && ue->op() == OPERATOR_AND)
1617 {
1618 if (!ue->operand()->type()->has_pointer())
1619 // Don't bother flowing non-pointer.
1620 break;
1621 dst_node = Node::make_node(ue->operand());
1622 }
1623 else
1624 dst_node = this->context_->add_dereference(Node::make_node(arg2));
1625 this->assign(dst_node, src_node);
1626 }
1627 break;
1628
1629 default:
1630 break;
1631 }
1632 }
1633 else
1634 this->call(call);
1635 }
1636 break;
1637
1638 case Expression::EXPRESSION_ALLOCATION:
1639 // This is Runtime::NEW.
1640 this->context_->track(n);
1641 break;
1642
1643 case Expression::EXPRESSION_STRING_CONCAT:
1644 this->context_->track(n);
1645 break;
1646
1647 case Expression::EXPRESSION_CONVERSION:
1648 {
1649 Type_conversion_expression* tce = (*pexpr)->conversion_expression();
1650 Type* ft = tce->expr()->type();
1651 Type* tt = tce->type();
1652 if ((ft->is_string_type() && tt->is_slice_type())
1653 || (ft->is_slice_type() && tt->is_string_type())
1654 || (ft->integer_type() != NULL && tt->is_string_type()))
1655 {
1656 // string([]byte), string([]rune), []byte(string), []rune(string), string(rune)
1657 this->context_->track(n);
1658 break;
1659 }
1660 Node* tce_node = Node::make_node(tce);
1661 Node* converted = Node::make_node(tce->expr());
1662 this->context_->track(tce_node);
1663
1664 this->assign(tce_node, converted);
1665 }
1666 break;
1667
1668 case Expression::EXPRESSION_FIXED_ARRAY_CONSTRUCTION:
1669 case Expression::EXPRESSION_SLICE_CONSTRUCTION:
1670 {
1671 Node* array_node = Node::make_node(*pexpr);
1672 if ((*pexpr)->slice_literal() != NULL)
1673 this->context_->track(array_node);
1674
1675 Expression_list* vals = ((*pexpr)->slice_literal() != NULL
1676 ? (*pexpr)->slice_literal()->vals()
1677 : (*pexpr)->array_literal()->vals());
1678
1679 if (vals != NULL)
1680 {
1681 // Connect the array to its values.
1682 for (Expression_list::const_iterator p = vals->begin();
1683 p != vals->end();
1684 ++p)
1685 if ((*p) != NULL)
1686 this->assign(array_node, Node::make_node(*p));
1687 }
1688 }
1689 break;
1690
1691 case Expression::EXPRESSION_STRUCT_CONSTRUCTION:
1692 {
1693 Node* struct_node = Node::make_node(*pexpr);
1694 Expression_list* vals = (*pexpr)->struct_literal()->vals();
1695 if (vals != NULL)
1696 {
1697 // Connect the struct to its values.
1698 for (Expression_list::const_iterator p = vals->begin();
1699 p != vals->end();
1700 ++p)
1701 {
1702 if ((*p) != NULL)
1703 this->assign(struct_node, Node::make_node(*p));
1704 }
1705 }
1706 }
1707 break;
1708
1709 case Expression::EXPRESSION_HEAP:
1710 {
1711 Node* pointer_node = Node::make_node(*pexpr);
1712 Node* lit_node = Node::make_node((*pexpr)->heap_expression()->expr());
1713 this->context_->track(pointer_node);
1714
1715 // Connect pointer node to literal node; if the pointer node escapes, so
1716 // does the literal node.
1717 this->assign(pointer_node, lit_node);
1718 }
1719 break;
1720
1721 case Expression::EXPRESSION_BOUND_METHOD:
1722 {
1723 Node* bound_node = Node::make_node(*pexpr);
1724 this->context_->track(bound_node);
1725
1726 Expression* obj = (*pexpr)->bound_method_expression()->first_argument();
1727 Node* obj_node = Node::make_node(obj);
1728
1729 // A bound method implies the receiver will be used outside of the
1730 // lifetime of the method in some way. We lose track of the receiver.
1731 this->assign(this->context_->sink(), obj_node);
1732 }
1733 break;
1734
1735 case Expression::EXPRESSION_MAP_CONSTRUCTION:
1736 {
1737 Map_construction_expression* mce = (*pexpr)->map_literal();
1738 Node* map_node = Node::make_node(mce);
1739 this->context_->track(map_node);
1740
1741 // All keys and values escape to memory.
1742 if (mce->vals() != NULL)
1743 {
1744 for (Expression_list::const_iterator p = mce->vals()->begin();
1745 p != mce->vals()->end();
1746 ++p)
1747 {
1748 if ((*p) != NULL)
1749 this->assign(this->context_->sink(), Node::make_node(*p));
1750 }
1751 }
1752 }
1753 break;
1754
1755 case Expression::EXPRESSION_FUNC_REFERENCE:
1756 {
1757 Func_expression* fe = (*pexpr)->func_expression();
1758 if (fe->closure() != NULL)
1759 {
1760 // Connect captured variables to the closure.
1761 Node* closure_node = Node::make_node(fe);
1762 this->context_->track(closure_node);
1763
1764 // A closure expression already exists as the heap expression:
1765 // &struct{f func_code, v []*Variable}{...}.
1766 // Link closure to the addresses of the variables enclosed.
1767 Heap_expression* he = fe->closure()->heap_expression();
1768 Struct_construction_expression* sce = he->expr()->struct_literal();
1769
1770 // First field is function code, other fields are variable
1771 // references.
1772 Expression_list::const_iterator p = sce->vals()->begin();
1773 ++p;
1774 for (; p != sce->vals()->end(); ++p)
1775 {
1776 Node* enclosed_node = Node::make_node(*p);
1777 Node::Escape_state* state =
1778 enclosed_node->state(this->context_, NULL);
1779 state->loop_depth = this->context_->loop_depth();
1780 this->assign(closure_node, enclosed_node);
1781 }
1782 }
1783 }
1784 break;
1785
1786 case Expression::EXPRESSION_UNARY:
1787 {
1788 if ((*pexpr)->unary_expression()->op() != OPERATOR_AND)
1789 break;
1790
1791 Node* addr_node = Node::make_node(*pexpr);
1792 this->context_->track(addr_node);
1793
1794 Expression* operand = (*pexpr)->unary_expression()->operand();
1795 Named_object* var = NULL;
1796 if (operand->var_expression() != NULL)
1797 var = operand->var_expression()->named_object();
1798 else if (operand->enclosed_var_expression() != NULL)
1799 var = operand->enclosed_var_expression()->variable();
1800
1801 if (var == NULL)
1802 break;
1803
1804 if (var->is_variable()
1805 && !var->var_value()->is_parameter())
1806 {
1807 // For &x, use the loop depth of x if known.
1808 Node::Escape_state* addr_state =
1809 addr_node->state(this->context_, NULL);
1810 Node* operand_node = Node::make_node(operand);
1811 Node::Escape_state* operand_state =
1812 operand_node->state(this->context_, NULL);
1813 if (operand_state->loop_depth != 0)
1814 addr_state->loop_depth = operand_state->loop_depth;
1815 }
1816 else if ((var->is_variable()
1817 && var->var_value()->is_parameter())
1818 || var->is_result_variable())
1819 {
1820 Node::Escape_state* addr_state =
1821 addr_node->state(this->context_, NULL);
1822 addr_state->loop_depth = 1;
1823 }
1824 }
1825 break;
1826
1827 case Expression::EXPRESSION_ARRAY_INDEX:
1828 {
1829 Array_index_expression* aie = (*pexpr)->array_index_expression();
1830 if (aie->end() != NULL && !aie->array()->type()->is_slice_type())
1831 {
1832 // Slicing an array.
1833 Expression* addr = Expression::make_unary(OPERATOR_AND, aie->array(),
1834 aie->location());
1835 Node* addr_node = Node::make_node(addr);
1836 n->set_child(addr_node);
1837 this->context_->track(addr_node);
1838 }
1839 }
1840 break;
1841
1842 default:
1843 break;
1844 }
1845 return TRAVERSE_SKIP_COMPONENTS;
1846 }
1847
1848 // Model calls within a function as assignments and flows between arguments
1849 // and results.
1850
1851 void
1852 Escape_analysis_assign::call(Call_expression* call)
1853 {
1854 Gogo* gogo = this->context_->gogo();
1855 int debug_level = gogo->debug_escape_level();
1856
1857 Func_expression* fn = call->fn()->func_expression();
1858 Function_type* fntype = call->get_function_type();
1859 bool indirect = false;
1860
1861 // Interface method calls or closure calls are indirect calls.
1862 if (fntype == NULL
1863 || (fntype->is_method()
1864 && fntype->receiver()->type()->interface_type() != NULL)
1865 || fn == NULL
1866 || (fn->named_object()->is_function()
1867 && fn->named_object()->func_value()->enclosing() != NULL))
1868 indirect = true;
1869
1870 Node* call_node = Node::make_node(call);
1871 std::vector<Node*> arg_nodes;
1872 if (call->fn()->interface_field_reference_expression() != NULL)
1873 {
1874 Interface_field_reference_expression* ifre =
1875 call->fn()->interface_field_reference_expression();
1876 Node* field_node = Node::make_node(ifre->expr());
1877 arg_nodes.push_back(field_node);
1878 }
1879
1880 if (call->args() != NULL)
1881 {
1882 for (Expression_list::const_iterator p = call->args()->begin();
1883 p != call->args()->end();
1884 ++p)
1885 arg_nodes.push_back(Node::make_node(*p));
1886 }
1887
1888 if (indirect)
1889 {
1890 // We don't know what happens to the parameters through indirect calls.
1891 // Be conservative and assume they all flow to theSink.
1892 for (std::vector<Node*>::iterator p = arg_nodes.begin();
1893 p != arg_nodes.end();
1894 ++p)
1895 {
1896 if (debug_level > 2)
1897 go_inform(call->location(),
1898 "esccall:: indirect call <- %s, untracked",
1899 (*p)->ast_format(gogo).c_str());
1900 this->assign(this->context_->sink(), *p);
1901 }
1902
1903 this->context_->init_retvals(call_node, fntype);
1904
1905 // It could be a closure call that returns captured variable.
1906 // Model this by flowing the func expression to result.
1907 // See issue #14409.
1908 Node* fn_node = Node::make_node(call->fn());
1909 std::vector<Node*> retvals = call_node->state(this->context_, NULL)->retvals;
1910 for (std::vector<Node*>::const_iterator p = retvals.begin();
1911 p != retvals.end();
1912 ++p)
1913 this->assign_deref(*p, fn_node);
1914
1915 return;
1916 }
1917
1918 // If FN is an untagged function.
1919 if (fn != NULL
1920 && fn->named_object()->is_function()
1921 && !fntype->is_tagged())
1922 {
1923 if (debug_level > 2)
1924 go_inform(call->location(), "esccall:: %s in recursive group",
1925 call_node->ast_format(gogo).c_str());
1926
1927 Function* f = fn->named_object()->func_value();
1928 const Bindings* callee_bindings = f->block()->bindings();
1929 Function::Results* results = f->result_variables();
1930 if (results != NULL)
1931 {
1932 // Setup output list on this call node.
1933 Node::Escape_state* state = call_node->state(this->context_, NULL);
1934 for (Function::Results::const_iterator p1 = results->begin();
1935 p1 != results->end();
1936 ++p1)
1937 {
1938 Node* result_node = Node::make_node(*p1);
1939 state->retvals.push_back(result_node);
1940 }
1941 }
1942
1943 std::vector<Node*>::iterator p = arg_nodes.begin();
1944 if (fntype->is_method())
1945 {
1946 std::string rcvr_name = fntype->receiver()->name();
1947 if (rcvr_name.empty() || Gogo::is_sink_name(rcvr_name)
1948 || !fntype->receiver()->type()->has_pointer())
1949 ;
1950 else
1951 {
1952 Named_object* rcvr_no =
1953 callee_bindings->lookup_local(fntype->receiver()->name());
1954 go_assert(rcvr_no != NULL);
1955 Node* rcvr_node = Node::make_node(rcvr_no);
1956 if (fntype->receiver()->type()->points_to() == NULL
1957 && (*p)->expr()->type()->points_to() != NULL)
1958 // This is a call to a value method that has been lowered into a call
1959 // to a pointer method. Gccgo generates a pointer method for all
1960 // method calls and takes the address of the value passed as the
1961 // receiver then immediately dereferences it within the function.
1962 // In this case, the receiver address does not escape; its content
1963 // flows to the call.
1964 this->assign_deref(rcvr_node, *p);
1965 else
1966 this->assign(rcvr_node, *p);
1967 }
1968 ++p;
1969 }
1970
1971 const Typed_identifier_list* til = fntype->parameters();
1972 if (til != NULL)
1973 {
1974 for (Typed_identifier_list::const_iterator p1 = til->begin();
1975 p1 != til->end();
1976 ++p1, ++p)
1977 {
1978 if (p1->name().empty() || Gogo::is_sink_name(p1->name()))
1979 continue;
1980
1981 Named_object* param_no =
1982 callee_bindings->lookup_local(p1->name());
1983 go_assert(param_no != NULL);
1984 Expression* arg = (*p)->expr();
1985 if (arg->var_expression() != NULL
1986 && arg->var_expression()->named_object() == param_no)
1987 continue;
1988
1989 Node* param_node = Node::make_node(param_no);
1990 this->assign(param_node, *p);
1991 }
1992
1993 for (; p != arg_nodes.end(); ++p)
1994 {
1995 if (debug_level > 2)
1996 go_inform(call->location(), "esccall:: ... <- %s, untracked",
1997 (*p)->ast_format(gogo).c_str());
1998 this->assign(this->context_->sink(), *p);
1999 }
2000 }
2001
2002 return;
2003 }
2004
2005 if (debug_level > 2)
2006 go_inform(call->location(), "esccall:: %s not recursive",
2007 call_node->ast_format(gogo).c_str());
2008
2009 Node::Escape_state* call_state = call_node->state(this->context_, NULL);
2010 if (!call_state->retvals.empty())
2011 go_error_at(Linemap::unknown_location(),
2012 "esc already decorated call %s",
2013 call_node->ast_format(gogo).c_str());
2014 this->context_->init_retvals(call_node, fntype);
2015
2016 // Receiver.
2017 std::vector<Node*>::iterator p = arg_nodes.begin();
2018 if (fntype->is_method()
2019 && p != arg_nodes.end())
2020 {
2021 // First argument to call will be the receiver.
2022 std::string* note = fntype->receiver()->note();
2023 if (fntype->receiver()->type()->points_to() == NULL
2024 && (*p)->expr()->type()->points_to() != NULL)
2025 // This is a call to a value method that has been lowered into a call
2026 // to a pointer method. Gccgo generates a pointer method for all
2027 // method calls and takes the address of the value passed as the
2028 // receiver then immediately dereferences it within the function.
2029 // In this case, the receiver address does not escape; its content
2030 // flows to the call.
2031 this->assign_from_note(note, call_state->retvals,
2032 this->context_->add_dereference(*p));
2033 else
2034 {
2035 if (!Type::are_identical(fntype->receiver()->type(),
2036 (*p)->expr()->type(), true, NULL))
2037 {
2038 // This will be converted later, preemptively track it instead
2039 // of its conversion expression which will show up in a later pass.
2040 this->context_->track(*p);
2041 }
2042 this->assign_from_note(note, call_state->retvals, *p);
2043 }
2044 p++;
2045 }
2046
2047 const Typed_identifier_list* til = fntype->parameters();
2048 if (til != NULL)
2049 {
2050 for (Typed_identifier_list::const_iterator pn = til->begin();
2051 pn != til->end() && p != arg_nodes.end();
2052 ++pn, ++p)
2053 {
2054 if (!Type::are_identical(pn->type(), (*p)->expr()->type(),
2055 true, NULL))
2056 {
2057 // This will be converted later, preemptively track it instead
2058 // of its conversion expression which will show up in a later pass.
2059 this->context_->track(*p);
2060 }
2061
2062 Type* t = pn->type();
2063 if (t != NULL
2064 && t->has_pointer())
2065 {
2066 std::string* note = pn->note();
2067 int enc = this->assign_from_note(note, call_state->retvals, *p);
2068 if (enc == Node::ESCAPE_NONE
2069 && !call->is_deferred()
2070 && !call->is_concurrent())
2071 {
2072 // TODO(cmang): Mark the argument as strictly non-escaping?
2073 // In the gc compiler this is for limiting the lifetime of
2074 // temporaries. We probably don't need this?
2075 }
2076 }
2077 }
2078
2079 for (; p != arg_nodes.end(); ++p)
2080 {
2081 if (debug_level > 2)
2082 go_inform(call->location(), "esccall:: ... <- %s, untracked",
2083 (*p)->ast_format(gogo).c_str());
2084 this->assign(this->context_->sink(), *p);
2085 }
2086 }
2087 }
2088
2089 // Model the assignment of DST to SRC.
2090 // Assert that SRC somehow gets assigned to DST.
2091 // DST might need to be examined for evaluations that happen inside of it.
2092 // For example, in [DST]*f(x) = [SRC]y, we lose track of the indirection and
2093 // DST becomes the sink in our model.
2094
2095 void
2096 Escape_analysis_assign::assign(Node* dst, Node* src)
2097 {
2098 Gogo* gogo = this->context_->gogo();
2099 int debug_level = gogo->debug_escape_level();
2100 if (debug_level > 1)
2101 go_inform(dst->location(), "[%d] %s escassign: %s(%s)[%s] = %s(%s)[%s]",
2102 this->context_->loop_depth(),
2103 strip_packed_prefix(gogo, this->context_->current_function_name()).c_str(),
2104 dst->ast_format(gogo).c_str(), dst->details().c_str(),
2105 dst->op_format().c_str(),
2106 src->ast_format(gogo).c_str(), src->details().c_str(),
2107 src->op_format().c_str());
2108
2109 if (dst->is_indirect())
2110 // Lose track of the dereference.
2111 dst = this->context_->sink();
2112 else if (dst->expr() != NULL)
2113 {
2114 // Analyze the lhs of the assignment.
2115 // Replace DST with this->context_->sink() if we can't track it.
2116 Expression* e = dst->expr();
2117 switch (e->classification())
2118 {
2119 case Expression::EXPRESSION_VAR_REFERENCE:
2120 {
2121 // If DST is a global variable, we have no way to track it.
2122 Named_object* var = e->var_expression()->named_object();
2123 if (var->is_variable() && var->var_value()->is_global())
2124 dst = this->context_->sink();
2125 }
2126 break;
2127
2128 case Expression::EXPRESSION_FIELD_REFERENCE:
2129 {
2130 Expression* strct = e->field_reference_expression()->expr();
2131 if (strct->heap_expression() != NULL)
2132 {
2133 // When accessing the field of a struct reference, we lose
2134 // track of the indirection.
2135 dst = this->context_->sink();
2136 break;
2137 }
2138
2139 // Treat DST.x = SRC as if it were DST = SRC.
2140 Node* struct_node = Node::make_node(strct);
2141 this->assign(struct_node, src);
2142 return;
2143 }
2144
2145 case Expression::EXPRESSION_ARRAY_INDEX:
2146 {
2147 Array_index_expression* are = e->array_index_expression();
2148 if (!are->array()->type()->is_slice_type())
2149 {
2150 // Treat DST[i] = SRC as if it were DST = SRC if DST if a fixed
2151 // array.
2152 Node* array_node = Node::make_node(are->array());
2153 this->assign(array_node, src);
2154 return;
2155 }
2156
2157 // Lose track of the slice dereference.
2158 dst = this->context_->sink();
2159 }
2160 break;
2161
2162 case Expression::EXPRESSION_UNARY:
2163 // Lose track of the dereference.
2164 if (e->unary_expression()->op() == OPERATOR_MULT)
2165 dst = this->context_->sink();
2166 break;
2167
2168 case Expression::EXPRESSION_MAP_INDEX:
2169 {
2170 // Lose track of the map's key and value.
2171 Expression* index = e->map_index_expression()->index();
2172 Node* index_node = Node::make_node(index);
2173 this->assign(this->context_->sink(), index_node);
2174
2175 dst = this->context_->sink();
2176 }
2177 break;
2178
2179 case Expression::EXPRESSION_TEMPORARY_REFERENCE:
2180 {
2181 // Temporary is tracked through the underlying Temporary_statement.
2182 Statement* t = dst->expr()->temporary_reference_expression()->statement();
2183 dst = Node::make_node(t);
2184 }
2185 break;
2186
2187 default:
2188 // TODO(cmang): Add debugging info here: only a few expressions
2189 // should leave DST unmodified.
2190 break;
2191 }
2192 }
2193
2194 if (src->object() != NULL)
2195 this->flows(dst, src);
2196 else if (src->is_indirect())
2197 this->flows(dst, src);
2198 else if (src->expr() != NULL)
2199 {
2200 Expression* e = src->expr();
2201 switch (e->classification())
2202 {
2203 case Expression::EXPRESSION_VAR_REFERENCE:
2204 case Expression::EXPRESSION_ENCLOSED_VAR_REFERENCE:
2205 // DST = var
2206 case Expression::EXPRESSION_HEAP:
2207 // DST = &T{...}.
2208 case Expression::EXPRESSION_FIXED_ARRAY_CONSTRUCTION:
2209 case Expression::EXPRESSION_SLICE_CONSTRUCTION:
2210 // DST = [...]T{...}.
2211 case Expression::EXPRESSION_MAP_CONSTRUCTION:
2212 // DST = map[T]V{...}.
2213 case Expression::EXPRESSION_STRUCT_CONSTRUCTION:
2214 // DST = T{...}.
2215 case Expression::EXPRESSION_ALLOCATION:
2216 // DST = new(T).
2217 case Expression::EXPRESSION_BOUND_METHOD:
2218 // DST = x.M.
2219 case Expression::EXPRESSION_STRING_CONCAT:
2220 // DST = str1 + str2
2221 this->flows(dst, src);
2222 break;
2223
2224 case Expression::EXPRESSION_UNSAFE_CONVERSION:
2225 {
2226 Expression* underlying = e->unsafe_conversion_expression()->expr();
2227 Node* underlying_node = Node::make_node(underlying);
2228 this->assign(dst, underlying_node);
2229 }
2230 break;
2231
2232 case Expression::EXPRESSION_CALL:
2233 {
2234 Call_expression* call = e->call_expression();
2235 if (call->is_builtin())
2236 {
2237 Builtin_call_expression* bce = call->builtin_call_expression();
2238 if (bce->code() == Builtin_call_expression::BUILTIN_APPEND)
2239 {
2240 // Append returns the first argument.
2241 // The subsequent arguments are already leaked because
2242 // they are operands to append.
2243 Node* appendee = Node::make_node(call->args()->front());
2244 this->assign(dst, appendee);
2245 }
2246 break;
2247 }
2248 Func_expression* fe = call->fn()->func_expression();
2249 if (fe != NULL && fe->is_runtime_function())
2250 {
2251 switch (fe->runtime_code())
2252 {
2253 case Runtime::MAKECHAN:
2254 case Runtime::MAKEMAP:
2255 case Runtime::MAKESLICE:
2256 case Runtime::MAKESLICE64:
2257 // DST = make(...).
2258 this->flows(dst, src);
2259 break;
2260
2261 default:
2262 break;
2263 }
2264 break;
2265 }
2266 else if (fe != NULL
2267 && fe->named_object()->is_function()
2268 && fe->named_object()->func_value()->is_method()
2269 && (call->is_deferred()
2270 || call->is_concurrent()))
2271 {
2272 // For a method call thunk, lose track of the call and treat it
2273 // as if DST = RECEIVER.
2274 Node* rcvr_node = Node::make_node(call->args()->front());
2275 this->assign(dst, rcvr_node);
2276 break;
2277 }
2278
2279 // Result flows to dst.
2280 Node* call_node = Node::make_node(e);
2281 Node::Escape_state* call_state = call_node->state(this->context_, NULL);
2282 std::vector<Node*> retvals = call_state->retvals;
2283 for (std::vector<Node*>::const_iterator p = retvals.begin();
2284 p != retvals.end();
2285 ++p)
2286 this->flows(dst, *p);
2287 }
2288 break;
2289
2290 case Expression::EXPRESSION_CALL_RESULT:
2291 {
2292 Call_result_expression* cre = e->call_result_expression();
2293 Call_expression* call = cre->call()->call_expression();
2294 if (call->is_builtin())
2295 break;
2296 if (call->fn()->func_expression() != NULL
2297 && call->fn()->func_expression()->is_runtime_function())
2298 {
2299 switch (call->fn()->func_expression()->runtime_code())
2300 {
2301 case Runtime::IFACEE2E2:
2302 case Runtime::IFACEI2E2:
2303 case Runtime::IFACEE2I2:
2304 case Runtime::IFACEI2I2:
2305 case Runtime::IFACEE2T2P:
2306 case Runtime::IFACEI2T2P:
2307 {
2308 // x, ok = v.(T), where T is a pointer or interface,
2309 // is lowered to
2310 // x, ok = IFACEI2E2(v), or
2311 // x, ok = IFACEI2I2(type, v)
2312 // The last arg flows to the first result.
2313 // Note: IFACEX2T2 has different signature, handled by
2314 // ::expression.
2315 if (cre->index() != 0)
2316 break;
2317 Node* arg_node = Node::make_node(call->args()->back());
2318 this->assign(dst, arg_node);
2319 }
2320 break;
2321
2322 default:
2323 break;
2324 }
2325 break;
2326 }
2327
2328 Node* call_node = Node::make_node(call);
2329 Node* ret_node = call_node->state(context_, NULL)->retvals[cre->index()];
2330 this->assign(dst, ret_node);
2331 }
2332 break;
2333
2334 case Expression::EXPRESSION_FUNC_REFERENCE:
2335 if (e->func_expression()->closure() != NULL)
2336 this->flows(dst, src);
2337 break;
2338
2339 case Expression::EXPRESSION_CONVERSION:
2340 {
2341 Type_conversion_expression* tce = e->conversion_expression();
2342 Type* ft = tce->expr()->type();
2343 Type* tt = tce->type();
2344 if ((ft->is_string_type() && tt->is_slice_type())
2345 || (ft->is_slice_type() && tt->is_string_type())
2346 || (ft->integer_type() != NULL && tt->is_string_type()))
2347 {
2348 // string([]byte), string([]rune), []byte(string), []rune(string), string(rune)
2349 this->flows(dst, src);
2350 break;
2351 }
2352 // Conversion preserves input value.
2353 Expression* underlying = tce->expr();
2354 this->assign(dst, Node::make_node(underlying));
2355 }
2356 break;
2357
2358 case Expression::EXPRESSION_FIELD_REFERENCE:
2359 {
2360 // A non-pointer can't escape from a struct.
2361 if (!e->type()->has_pointer())
2362 break;
2363 }
2364 // Fall through.
2365
2366 case Expression::EXPRESSION_TYPE_GUARD:
2367 case Expression::EXPRESSION_ARRAY_INDEX:
2368 case Expression::EXPRESSION_STRING_INDEX:
2369 {
2370 Expression* left = NULL;
2371 if (e->field_reference_expression() != NULL)
2372 {
2373 left = e->field_reference_expression()->expr();
2374 if (left->unary_expression() != NULL
2375 && left->unary_expression()->op() == OPERATOR_MULT)
2376 {
2377 // DST = (*x).f
2378 this->flows(dst, src);
2379 break;
2380 }
2381 }
2382 else if (e->type_guard_expression() != NULL)
2383 left = e->type_guard_expression()->expr();
2384 else if (e->array_index_expression() != NULL)
2385 {
2386 Array_index_expression* aie = e->array_index_expression();
2387 if (aie->end() != NULL)
2388 // slicing
2389 if (aie->array()->type()->is_slice_type())
2390 left = aie->array();
2391 else
2392 {
2393 // slicing an array
2394 // The gc compiler has an implicit address operator.
2395 go_assert(src->child() != NULL);
2396 this->assign(dst, src->child());
2397 break;
2398 }
2399 else if (!aie->array()->type()->is_slice_type())
2400 {
2401 // Indexing an array preserves the input value.
2402 Node* array_node = Node::make_node(aie->array());
2403 this->assign(dst, array_node);
2404 break;
2405 }
2406 else
2407 {
2408 this->flows(dst, src);
2409 break;
2410 }
2411 }
2412 else if (e->string_index_expression() != NULL)
2413 {
2414 String_index_expression* sie = e->string_index_expression();
2415 if (e->type()->is_string_type())
2416 // slicing
2417 left = sie->string();
2418 else
2419 {
2420 this->flows(dst, src);
2421 break;
2422 }
2423 }
2424 go_assert(left != NULL);
2425
2426 // Conversions, field access, and slicing all preserve the input
2427 // value.
2428 Node* left_node = Node::make_node(left);
2429 this->assign(dst, left_node);
2430 }
2431 break;
2432
2433 case Expression::EXPRESSION_BINARY:
2434 {
2435 switch (e->binary_expression()->op())
2436 {
2437 case OPERATOR_PLUS:
2438 case OPERATOR_MINUS:
2439 case OPERATOR_XOR:
2440 case OPERATOR_OR:
2441 case OPERATOR_MULT:
2442 case OPERATOR_DIV:
2443 case OPERATOR_MOD:
2444 case OPERATOR_LSHIFT:
2445 case OPERATOR_RSHIFT:
2446 case OPERATOR_AND:
2447 case OPERATOR_BITCLEAR:
2448 {
2449 Node* left = Node::make_node(e->binary_expression()->left());
2450 this->assign(dst, left);
2451 Node* right = Node::make_node(e->binary_expression()->right());
2452 this->assign(dst, right);
2453 }
2454 break;
2455
2456 default:
2457 break;
2458 }
2459 }
2460 break;
2461
2462 case Expression::EXPRESSION_UNARY:
2463 {
2464 switch (e->unary_expression()->op())
2465 {
2466 case OPERATOR_PLUS:
2467 case OPERATOR_MINUS:
2468 case OPERATOR_XOR:
2469 {
2470 Node* op_node =
2471 Node::make_node(e->unary_expression()->operand());
2472 this->assign(dst, op_node);
2473 }
2474 break;
2475
2476 case OPERATOR_MULT:
2477 // DST = *x
2478 case OPERATOR_AND:
2479 // DST = &x
2480 this->flows(dst, src);
2481 break;
2482
2483 default:
2484 break;
2485 }
2486 }
2487 break;
2488
2489 case Expression::EXPRESSION_TEMPORARY_REFERENCE:
2490 {
2491 Statement* temp = e->temporary_reference_expression()->statement();
2492 this->assign(dst, Node::make_node(temp));
2493 }
2494 break;
2495
2496 default:
2497 // TODO(cmang): Add debug info here; this should not be reachable.
2498 // For now, just to be conservative, we'll just say dst flows to src.
2499 break;
2500 }
2501 }
2502 else if (src->statement() != NULL && src->statement()->temporary_statement() != NULL)
2503 this->flows(dst, src);
2504 }
2505
2506 // Model the assignment of DST to an indirection of SRC.
2507
2508 void
2509 Escape_analysis_assign::assign_deref(Node* dst, Node* src)
2510 {
2511 if (src->expr() != NULL)
2512 {
2513 switch (src->expr()->classification())
2514 {
2515 case Expression::EXPRESSION_BOOLEAN:
2516 case Expression::EXPRESSION_STRING:
2517 case Expression::EXPRESSION_INTEGER:
2518 case Expression::EXPRESSION_FLOAT:
2519 case Expression::EXPRESSION_COMPLEX:
2520 case Expression::EXPRESSION_NIL:
2521 case Expression::EXPRESSION_IOTA:
2522 // No need to try indirections on literal values
2523 // or numeric constants.
2524 return;
2525
2526 default:
2527 break;
2528 }
2529 }
2530
2531 this->assign(dst, this->context_->add_dereference(src));
2532 }
2533
2534 // Model the input-to-output assignment flow of one of a function call's
2535 // arguments, where the flow is encoded in NOTE.
2536
2537 int
2538 Escape_analysis_assign::assign_from_note(std::string* note,
2539 const std::vector<Node*>& dsts,
2540 Node* src)
2541 {
2542 int enc = Escape_note::parse_tag(note);
2543 if (src->expr() != NULL)
2544 {
2545 switch (src->expr()->classification())
2546 {
2547 case Expression::EXPRESSION_BOOLEAN:
2548 case Expression::EXPRESSION_STRING:
2549 case Expression::EXPRESSION_INTEGER:
2550 case Expression::EXPRESSION_FLOAT:
2551 case Expression::EXPRESSION_COMPLEX:
2552 case Expression::EXPRESSION_NIL:
2553 case Expression::EXPRESSION_IOTA:
2554 // There probably isn't a note for a literal value. Literal values
2555 // usually don't escape unless we lost track of the value some how.
2556 return enc;
2557
2558 default:
2559 break;
2560 }
2561 }
2562
2563 if (this->context_->gogo()->debug_escape_level() > 2)
2564 go_inform(src->location(), "assignfromtag:: src=%s em=%s",
2565 src->ast_format(context_->gogo()).c_str(),
2566 Escape_note::make_tag(enc).c_str());
2567
2568 if (enc == Node::ESCAPE_UNKNOWN)
2569 {
2570 // Lost track of the value.
2571 this->assign(this->context_->sink(), src);
2572 return enc;
2573 }
2574 else if (enc == Node::ESCAPE_NONE)
2575 return enc;
2576
2577 // If the content inside a parameter (reached via indirection) escapes to
2578 // the heap, mark it.
2579 if ((enc & ESCAPE_CONTENT_ESCAPES) != 0)
2580 this->assign(this->context_->sink(), this->context_->add_dereference(src));
2581
2582 int save_enc = enc;
2583 enc >>= ESCAPE_RETURN_BITS;
2584 for (std::vector<Node*>::const_iterator p = dsts.begin();
2585 enc != 0 && p != dsts.end();
2586 ++p)
2587 {
2588 // Prefer the lowest-level path to the reference (for escape purposes).
2589 // Two-bit encoding (for example. 1, 3, and 4 bits are other options)
2590 // 01 = 0-level
2591 // 10 = 1-level, (content escapes),
2592 // 11 = 2-level, (content of content escapes).
2593 int bits = enc & ESCAPE_BITS_MASK_FOR_TAG;
2594 if (bits > 0)
2595 {
2596 Node* n = src;
2597 for (int i = 0; i < bits - 1; ++i)
2598 {
2599 // Encode level > 0 as indirections.
2600 n = this->context_->add_dereference(n);
2601 }
2602 this->assign(*p, n);
2603 }
2604 enc >>= ESCAPE_BITS_PER_OUTPUT_IN_TAG;
2605 }
2606
2607 // If there are too many outputs to fit in the tag, that is handled on the
2608 // encoding end as ESCAPE_HEAP, so there is no need to check here.
2609 return save_enc;
2610 }
2611
2612 // Record the flow of SRC to DST in DST.
2613
2614 void
2615 Escape_analysis_assign::flows(Node* dst, Node* src)
2616 {
2617 // Don't bother capturing the flow from scalars.
2618 if (src->type() != NULL && !src->type()->has_pointer())
2619 return;
2620
2621 // Don't confuse a blank identifier with the sink.
2622 if (dst->is_sink() && dst != this->context_->sink())
2623 return;
2624
2625 Node::Escape_state* dst_state = dst->state(this->context_, NULL);
2626 Node::Escape_state* src_state = src->state(this->context_, NULL);
2627 if (dst == src
2628 || dst_state == src_state
2629 || dst_state->flows.find(src) != dst_state->flows.end())
2630 return;
2631
2632 Gogo* gogo = this->context_->gogo();
2633 if (gogo->debug_escape_level() > 2)
2634 go_inform(Linemap::unknown_location(), "flows:: %s <- %s",
2635 dst->ast_format(gogo).c_str(), src->ast_format(gogo).c_str());
2636
2637 if (dst_state->flows.empty())
2638 this->context_->add_dst(dst);
2639
2640 dst_state->flows.insert(src);
2641 }
2642
2643 // Build a connectivity graph between nodes in the function being analyzed.
2644
2645 void
2646 Gogo::assign_connectivity(Escape_context* context, Named_object* fn)
2647 {
2648 // Must be defined outside of this package.
2649 if (!fn->is_function())
2650 return;
2651
2652 int save_depth = context->loop_depth();
2653 context->set_loop_depth(1);
2654
2655 Escape_analysis_assign ea(context, fn);
2656 Function::Results* res = fn->func_value()->result_variables();
2657 if (res != NULL)
2658 {
2659 for (Function::Results::const_iterator p = res->begin();
2660 p != res->end();
2661 ++p)
2662 {
2663 Node* res_node = Node::make_node(*p);
2664 Node::Escape_state* res_state = res_node->state(context, fn);
2665 res_state->fn = fn;
2666 res_state->loop_depth = 0;
2667
2668 // If this set of functions is recursive, we lose track of the return values.
2669 // Just say that the result flows to the sink.
2670 if (context->recursive())
2671 ea.flows(context->sink(), res_node);
2672 }
2673 }
2674
2675 const Bindings* callee_bindings = fn->func_value()->block()->bindings();
2676 Function_type* fntype = fn->func_value()->type();
2677 Typed_identifier_list* params = (fntype->parameters() != NULL
2678 ? fntype->parameters()->copy()
2679 : new Typed_identifier_list);
2680 if (fntype->receiver() != NULL)
2681 params->push_back(*fntype->receiver());
2682
2683 for (Typed_identifier_list::const_iterator p = params->begin();
2684 p != params->end();
2685 ++p)
2686 {
2687 if (p->name().empty() || Gogo::is_sink_name(p->name()))
2688 continue;
2689
2690 Named_object* param_no = callee_bindings->lookup_local(p->name());
2691 go_assert(param_no != NULL);
2692 Node* param_node = Node::make_node(param_no);
2693 Node::Escape_state* param_state = param_node->state(context, fn);
2694 param_state->fn = fn;
2695 param_state->loop_depth = 1;
2696
2697 if (!p->type()->has_pointer())
2698 continue;
2699
2700 // External function? Parameters must escape unless //go:noescape is set.
2701 // TODO(cmang): Implement //go:noescape directive.
2702 if (fn->package() != NULL)
2703 param_node->set_encoding(Node::ESCAPE_HEAP);
2704 else
2705 {
2706 param_node->set_encoding(Node::ESCAPE_NONE);
2707 context->track(param_node);
2708 }
2709 }
2710
2711 Escape_analysis_loop el;
2712 fn->func_value()->traverse(&el);
2713
2714 fn->func_value()->traverse(&ea);
2715 context->set_loop_depth(save_depth);
2716 }
2717
2718 class Escape_analysis_flood
2719 {
2720 public:
2721 Escape_analysis_flood(Escape_context* context)
2722 : context_(context)
2723 { }
2724
2725 // Use the escape information in dst to update the escape information in src
2726 // and src's upstream.
2727 void
2728 flood(Level, Node* dst, Node* src, int);
2729
2730 private:
2731 // The escape context for the group of functions being flooded.
2732 Escape_context* context_;
2733 };
2734
2735 // Whenever we hit a dereference node, the level goes up by one, and whenever
2736 // we hit an address-of, the level goes down by one. as long as we're on a
2737 // level > 0 finding an address-of just means we're following the upstream
2738 // of a dereference, so this address doesn't leak (yet).
2739 // If level == 0, it means the /value/ of this node can reach the root of this
2740 // flood so if this node is an address-of, its argument should be marked as
2741 // escaping iff its current function and loop depth are different from the
2742 // flood's root.
2743 // Once an object has been moved to the heap, all of its upstream should be
2744 // considered escaping to the global scope.
2745 // This is an implementation of gc/esc.go:escwalkBody.
2746
2747 void
2748 Escape_analysis_flood::flood(Level level, Node* dst, Node* src,
2749 int extra_loop_depth)
2750 {
2751 // No need to flood src if it is a literal.
2752 if (src->expr() != NULL)
2753 {
2754 switch (src->expr()->classification())
2755 {
2756 case Expression::EXPRESSION_BOOLEAN:
2757 case Expression::EXPRESSION_STRING:
2758 case Expression::EXPRESSION_INTEGER:
2759 case Expression::EXPRESSION_FLOAT:
2760 case Expression::EXPRESSION_COMPLEX:
2761 case Expression::EXPRESSION_NIL:
2762 case Expression::EXPRESSION_IOTA:
2763 return;
2764
2765 default:
2766 break;
2767 }
2768 }
2769
2770 Node::Escape_state* src_state = src->state(this->context_, NULL);
2771 if (src_state->flood_id == this->context_->flood_id())
2772 {
2773 // Esclevels are vectors, do not compare as integers,
2774 // and must use "min" of old and new to guarantee
2775 // convergence.
2776 level = level.min(src_state->level);
2777 if (level == src_state->level)
2778 {
2779 // Have we been here already with an extraloopdepth,
2780 // or is the extraloopdepth provided no improvement on
2781 // what's already been seen?
2782 if (src_state->max_extra_loop_depth >= extra_loop_depth
2783 || src_state->loop_depth >= extra_loop_depth)
2784 return;
2785 src_state->max_extra_loop_depth = extra_loop_depth;
2786 }
2787 }
2788 else
2789 src_state->max_extra_loop_depth = -1;
2790
2791 src_state->flood_id = this->context_->flood_id();
2792 src_state->level = level;
2793 int mod_loop_depth = std::max(extra_loop_depth, src_state->loop_depth);
2794
2795 Gogo* gogo = this->context_->gogo();
2796 int debug_level = gogo->debug_escape_level();
2797 if (debug_level > 1)
2798 go_inform(Linemap::unknown_location(),
2799 "escwalk: level:{%d %d} depth:%d "
2800 "op=%s %s(%s) "
2801 "scope:%s[%d] "
2802 "extraloopdepth=%d",
2803 level.value(), level.suffix_value(), this->context_->pdepth(),
2804 src->op_format().c_str(),
2805 src->ast_format(gogo).c_str(),
2806 src->details().c_str(),
2807 debug_function_name(src_state->fn).c_str(),
2808 src_state->loop_depth,
2809 extra_loop_depth);
2810
2811 this->context_->increase_pdepth();
2812
2813 // Input parameter flowing into output parameter?
2814 Named_object* src_no = NULL;
2815 if (src->expr() != NULL && src->expr()->var_expression() != NULL)
2816 src_no = src->expr()->var_expression()->named_object();
2817 else
2818 src_no = src->object();
2819 bool src_is_param = (src_no != NULL
2820 && src_no->is_variable()
2821 && src_no->var_value()->is_parameter());
2822
2823 Named_object* dst_no = NULL;
2824 if (dst->expr() != NULL && dst->expr()->var_expression() != NULL)
2825 dst_no = dst->expr()->var_expression()->named_object();
2826 else
2827 dst_no = dst->object();
2828 bool dst_is_result = dst_no != NULL && dst_no->is_result_variable();
2829 Node::Escape_state* dst_state = dst->state(this->context_, NULL);
2830
2831 if (src_is_param
2832 && dst_is_result
2833 && src_state->fn == dst_state->fn
2834 && (src->encoding() & ESCAPE_MASK) < int(Node::ESCAPE_HEAP)
2835 && dst->encoding() != Node::ESCAPE_HEAP)
2836 {
2837 // This case handles:
2838 // 1. return in
2839 // 2. return &in
2840 // 3. tmp := in; return &tmp
2841 // 4. return *in
2842 if (debug_level != 0)
2843 {
2844 if (debug_level == 1)
2845 go_inform(src->definition_location(),
2846 "leaking param: %s to result %s level=%d",
2847 src->ast_format(gogo).c_str(),
2848 dst->ast_format(gogo).c_str(),
2849 level.value());
2850 else
2851 go_inform(src->definition_location(),
2852 "leaking param: %s to result %s level={%d %d}",
2853 src->ast_format(gogo).c_str(),
2854 dst->ast_format(gogo).c_str(),
2855 level.value(), level.suffix_value());
2856 }
2857
2858 if ((src->encoding() & ESCAPE_MASK) != Node::ESCAPE_RETURN)
2859 {
2860 int enc =
2861 Node::ESCAPE_RETURN | (src->encoding() & ESCAPE_CONTENT_ESCAPES);
2862 src->set_encoding(enc);
2863 }
2864
2865 int enc = Node::note_inout_flows(src->encoding(),
2866 dst_no->result_var_value()->index(),
2867 level);
2868 src->set_encoding(enc);
2869
2870 // In gc/esc.go:escwalkBody, this is a goto to the label for recursively
2871 // flooding the connection graph. Inlined here for convenience.
2872 level = level.copy();
2873 for (std::set<Node*>::const_iterator p = src_state->flows.begin();
2874 p != src_state->flows.end();
2875 ++p)
2876 this->flood(level, dst, *p, extra_loop_depth);
2877 return;
2878 }
2879
2880 // If parameter content escape to heap, set ESCAPE_CONTENT_ESCAPES.
2881 // Note minor confusion around escape from pointer-to-struct vs
2882 // escape from struct.
2883 if (src_is_param
2884 && dst->encoding() == Node::ESCAPE_HEAP
2885 && (src->encoding() & ESCAPE_MASK) < int(Node::ESCAPE_HEAP)
2886 && level.value() > 0)
2887 {
2888 int enc =
2889 Node::max_encoding((src->encoding() | ESCAPE_CONTENT_ESCAPES),
2890 Node::ESCAPE_NONE);
2891 src->set_encoding(enc);
2892 if (debug_level != 0)
2893 go_inform(src->definition_location(), "mark escaped content: %s",
2894 src->ast_format(gogo).c_str());
2895 }
2896
2897 // A src object leaks if its value or address is assigned to a dst object
2898 // in a different scope (at a different loop depth).
2899 bool src_leaks = (level.value() <= 0
2900 && level.suffix_value() <= 0
2901 && dst_state->loop_depth < mod_loop_depth);
2902 src_leaks = src_leaks || (level.value() <= 0
2903 && (dst->encoding() & ESCAPE_MASK) == Node::ESCAPE_HEAP);
2904 // old src encoding, used to prevent duplicate error messages
2905 int osrcesc = src->encoding();
2906
2907 if (src_is_param
2908 && (src_leaks || dst_state->loop_depth < 0)
2909 && (src->encoding() & ESCAPE_MASK) < int(Node::ESCAPE_HEAP))
2910 {
2911 if (level.suffix_value() > 0)
2912 {
2913 int enc =
2914 Node::max_encoding((src->encoding() | ESCAPE_CONTENT_ESCAPES),
2915 Node::ESCAPE_NONE);
2916 src->set_encoding(enc);
2917 if (debug_level != 0 && osrcesc != src->encoding())
2918 go_inform(src->definition_location(), "leaking param content: %s",
2919 src->ast_format(gogo).c_str());
2920 }
2921 else
2922 {
2923 if (debug_level != 0)
2924 go_inform(src->definition_location(), "leaking param: %s",
2925 src->ast_format(gogo).c_str());
2926 src->set_encoding(Node::ESCAPE_HEAP);
2927 }
2928 }
2929 else if (src->expr() != NULL)
2930 {
2931 Expression* e = src->expr();
2932 if (e->enclosed_var_expression() != NULL)
2933 {
2934 if (src_leaks && debug_level != 0)
2935 go_inform(src->location(), "leaking closure reference %s",
2936 src->ast_format(gogo).c_str());
2937
2938 Node* enclosed_node =
2939 Node::make_node(e->enclosed_var_expression()->variable());
2940 this->flood(level, dst, enclosed_node, -1);
2941 }
2942 else if (e->heap_expression() != NULL
2943 || (e->unary_expression() != NULL
2944 && e->unary_expression()->op() == OPERATOR_AND))
2945 {
2946 // Pointer literals and address-of expressions.
2947 Expression* underlying;
2948 if (e->heap_expression())
2949 underlying = e->heap_expression()->expr();
2950 else
2951 underlying = e->unary_expression()->operand();
2952 Node* underlying_node = Node::make_node(underlying);
2953
2954 // If the address leaks, the underyling object must be moved
2955 // to the heap.
2956 underlying->address_taken(src_leaks);
2957 if (src_leaks)
2958 {
2959 src->set_encoding(Node::ESCAPE_HEAP);
2960 if (debug_level != 0 && osrcesc != src->encoding())
2961 {
2962 if (underlying->var_expression() != NULL
2963 || underlying->enclosed_var_expression() != NULL)
2964 go_inform(underlying_node->definition_location(),
2965 "moved to heap: %s",
2966 underlying_node->ast_format(gogo).c_str());
2967
2968 if (debug_level > 1)
2969 go_inform(src->location(),
2970 "%s escapes to heap, level={%d %d}, "
2971 "dst.eld=%d, src.eld=%d",
2972 src->ast_format(gogo).c_str(), level.value(),
2973 level.suffix_value(), dst_state->loop_depth,
2974 mod_loop_depth);
2975 else
2976 go_inform(src->location(), "%s escapes to heap",
2977 src->ast_format(gogo).c_str());
2978 }
2979
2980 this->flood(level.decrease(), dst,
2981 underlying_node, mod_loop_depth);
2982 extra_loop_depth = mod_loop_depth;
2983 }
2984 else
2985 {
2986 // Decrease the level each time we take the address of the object.
2987 this->flood(level.decrease(), dst, underlying_node, -1);
2988 }
2989 }
2990 else if (e->slice_literal() != NULL)
2991 {
2992 Slice_construction_expression* slice = e->slice_literal();
2993 if (slice->vals() != NULL)
2994 {
2995 for (Expression_list::const_iterator p = slice->vals()->begin();
2996 p != slice->vals()->end();
2997 ++p)
2998 {
2999 if ((*p) != NULL)
3000 this->flood(level.decrease(), dst, Node::make_node(*p), -1);
3001 }
3002 }
3003 if (src_leaks)
3004 {
3005 src->set_encoding(Node::ESCAPE_HEAP);
3006 if (debug_level != 0 && osrcesc != src->encoding())
3007 go_inform(src->location(), "%s escapes to heap",
3008 src->ast_format(gogo).c_str());
3009 extra_loop_depth = mod_loop_depth;
3010 }
3011 }
3012 else if (e->call_expression() != NULL)
3013 {
3014 Call_expression* call = e->call_expression();
3015 if (call->is_builtin())
3016 {
3017 Builtin_call_expression* bce = call->builtin_call_expression();
3018 if (bce->code() == Builtin_call_expression::BUILTIN_APPEND)
3019 {
3020 // Propagate escape information to appendee.
3021 Expression* appendee = call->args()->front();
3022 this->flood(level, dst, Node::make_node(appendee), -1);
3023 }
3024 }
3025 else if (call->fn()->func_expression() != NULL
3026 && call->fn()->func_expression()->is_runtime_function())
3027 {
3028 switch (call->fn()->func_expression()->runtime_code())
3029 {
3030 case Runtime::MAKECHAN:
3031 case Runtime::MAKEMAP:
3032 case Runtime::MAKESLICE:
3033 case Runtime::MAKESLICE64:
3034 if (src_leaks)
3035 {
3036 src->set_encoding(Node::ESCAPE_HEAP);
3037 if (debug_level != 0 && osrcesc != src->encoding())
3038 go_inform(src->location(), "%s escapes to heap",
3039 src->ast_format(gogo).c_str());
3040 extra_loop_depth = mod_loop_depth;
3041 }
3042 break;
3043
3044 default:
3045 break;
3046 }
3047 }
3048 else if (src_state->retvals.size() > 0)
3049 {
3050 // In this case a link went directly to a call, but should really go
3051 // to the dummy .outN outputs that were created for the call that
3052 // themselves link to the inputs with levels adjusted.
3053 // See e.g. #10466.
3054 // This can only happen with functions returning a single result.
3055 go_assert(src_state->retvals.size() == 1);
3056 if (debug_level > 2)
3057 go_inform(src->location(), "[%d] dst %s escwalk replace src: %s with %s",
3058 this->context_->loop_depth(),
3059 dst->ast_format(gogo).c_str(),
3060 src->ast_format(gogo).c_str(),
3061 src_state->retvals[0]->ast_format(gogo).c_str());
3062 src = src_state->retvals[0];
3063 src_state = src->state(this->context_, NULL);
3064 }
3065 }
3066 else if (e->allocation_expression() != NULL && src_leaks)
3067 {
3068 // Calls to Runtime::NEW get lowered into an allocation expression.
3069 src->set_encoding(Node::ESCAPE_HEAP);
3070 if (debug_level != 0 && osrcesc != src->encoding())
3071 go_inform(src->location(), "%s escapes to heap",
3072 src->ast_format(gogo).c_str());
3073 extra_loop_depth = mod_loop_depth;
3074 }
3075 else if ((e->map_literal() != NULL
3076 || e->string_concat_expression() != NULL
3077 || (e->func_expression() != NULL && e->func_expression()->closure() != NULL)
3078 || e->bound_method_expression() != NULL)
3079 && src_leaks)
3080 {
3081 src->set_encoding(Node::ESCAPE_HEAP);
3082 if (debug_level != 0 && osrcesc != src->encoding())
3083 go_inform(src->location(), "%s escapes to heap",
3084 src->ast_format(gogo).c_str());
3085 extra_loop_depth = mod_loop_depth;
3086 }
3087 else if (e->conversion_expression() != NULL && src_leaks)
3088 {
3089 Type_conversion_expression* tce = e->conversion_expression();
3090 Type* ft = tce->expr()->type();
3091 Type* tt = tce->type();
3092 if ((ft->is_string_type() && tt->is_slice_type())
3093 || (ft->is_slice_type() && tt->is_string_type())
3094 || (ft->integer_type() != NULL && tt->is_string_type()))
3095 {
3096 // string([]byte), string([]rune), []byte(string), []rune(string), string(rune)
3097 src->set_encoding(Node::ESCAPE_HEAP);
3098 if (debug_level != 0 && osrcesc != src->encoding())
3099 go_inform(src->location(), "%s escapes to heap",
3100 src->ast_format(gogo).c_str());
3101 extra_loop_depth = mod_loop_depth;
3102 }
3103 }
3104 else if (e->array_index_expression() != NULL
3105 && !e->array_index_expression()->array()->type()->is_slice_type())
3106 {
3107 Array_index_expression* aie = e->array_index_expression();
3108 if (aie->end() != NULL)
3109 {
3110 // Slicing an array.
3111 // Flow its implicit address-of node to DST.
3112 this->flood(level, dst, src->child(), -1);
3113 }
3114 else
3115 {
3116 // Indexing an array.
3117 // An array element flowing to DST behaves like the array
3118 // flowing to DST.
3119 Expression* underlying = e->array_index_expression()->array();
3120 Node* underlying_node = Node::make_node(underlying);
3121 this->flood(level, dst, underlying_node, -1);
3122 }
3123 }
3124 else if ((e->field_reference_expression() != NULL
3125 && e->field_reference_expression()->expr()->unary_expression() == NULL)
3126 || e->type_guard_expression() != NULL
3127 || (e->array_index_expression() != NULL
3128 && e->array_index_expression()->end() != NULL)
3129 || (e->string_index_expression() != NULL
3130 && e->type()->is_string_type()))
3131 {
3132 Expression* underlying;
3133 if (e->field_reference_expression() != NULL)
3134 underlying = e->field_reference_expression()->expr();
3135 else if (e->type_guard_expression() != NULL)
3136 underlying = e->type_guard_expression()->expr();
3137 else if (e->array_index_expression() != NULL)
3138 underlying = e->array_index_expression()->array();
3139 else
3140 underlying = e->string_index_expression()->string();
3141
3142 Node* underlying_node = Node::make_node(underlying);
3143 this->flood(level, dst, underlying_node, -1);
3144 }
3145 else if ((e->field_reference_expression() != NULL
3146 && e->field_reference_expression()->expr()->unary_expression() != NULL)
3147 || e->array_index_expression() != NULL
3148 || e->map_index_expression() != NULL
3149 || (e->unary_expression() != NULL
3150 && e->unary_expression()->op() == OPERATOR_MULT))
3151 {
3152 Expression* underlying;
3153 if (e->field_reference_expression() != NULL)
3154 {
3155 underlying = e->field_reference_expression()->expr();
3156 underlying = underlying->unary_expression()->operand();
3157 }
3158 else if (e->array_index_expression() != NULL)
3159 underlying = e->array_index_expression()->array();
3160 else if (e->map_index_expression() != NULL)
3161 underlying = e->map_index_expression()->map();
3162 else
3163 underlying = e->unary_expression()->operand();
3164
3165 // Increase the level for a dereference.
3166 Node* underlying_node = Node::make_node(underlying);
3167 this->flood(level.increase(), dst, underlying_node, -1);
3168 }
3169 else if (e->temporary_reference_expression() != NULL)
3170 {
3171 Statement* t = e->temporary_reference_expression()->statement();
3172 this->flood(level, dst, Node::make_node(t), -1);
3173 }
3174 }
3175 else if (src->is_indirect())
3176 // Increase the level for a dereference.
3177 this->flood(level.increase(), dst, src->child(), -1);
3178
3179 level = level.copy();
3180 for (std::set<Node*>::const_iterator p = src_state->flows.begin();
3181 p != src_state->flows.end();
3182 ++p)
3183 this->flood(level, dst, *p, extra_loop_depth);
3184
3185 this->context_->decrease_pdepth();
3186 }
3187
3188 // Propagate escape information across the nodes modeled in this Analysis_set.
3189 // This is an implementation of gc/esc.go:escflood.
3190
3191 void
3192 Gogo::propagate_escape(Escape_context* context, Node* dst)
3193 {
3194 if (dst->object() == NULL
3195 && (dst->expr() == NULL
3196 || (dst->expr()->var_expression() == NULL
3197 && dst->expr()->enclosed_var_expression() == NULL
3198 && dst->expr()->func_expression() == NULL)))
3199 return;
3200
3201 Node::Escape_state* state = dst->state(context, NULL);
3202 Gogo* gogo = context->gogo();
3203 if (gogo->debug_escape_level() > 1)
3204 go_inform(Linemap::unknown_location(), "escflood:%d: dst %s scope:%s[%d]",
3205 context->flood_id(), dst->ast_format(gogo).c_str(),
3206 debug_function_name(state->fn).c_str(),
3207 state->loop_depth);
3208
3209 Escape_analysis_flood eaf(context);
3210 for (std::set<Node*>::const_iterator p = state->flows.begin();
3211 p != state->flows.end();
3212 ++p)
3213 {
3214 context->increase_flood_id();
3215 eaf.flood(Level::From(0), dst, *p, -1);
3216 }
3217 }
3218
3219 class Escape_analysis_tag
3220 {
3221 public:
3222 Escape_analysis_tag(Escape_context* context)
3223 : context_(context)
3224 { }
3225
3226 // Add notes to the function's type about the escape information of its
3227 // input parameters.
3228 void
3229 tag(Named_object* fn);
3230
3231 private:
3232 Escape_context* context_;
3233 };
3234
3235 void
3236 Escape_analysis_tag::tag(Named_object* fn)
3237 {
3238 // External functions are assumed unsafe
3239 // unless //go:noescape is given before the declaration.
3240 if (fn->package() != NULL)
3241 return;
3242
3243 if (fn->is_function_declaration())
3244 {
3245 Function_declaration* fdcl = fn->func_declaration_value();
3246 if ((fdcl->pragmas() & GOPRAGMA_NOESCAPE) != 0)
3247 {
3248 Function_type* fntype = fdcl->type();
3249 if (fntype->parameters() != NULL)
3250 {
3251 const Typed_identifier_list* til = fntype->parameters();
3252 int i = 0;
3253 for (Typed_identifier_list::const_iterator p = til->begin();
3254 p != til->end();
3255 ++p, ++i)
3256 if (p->type()->has_pointer())
3257 fntype->add_parameter_note(i, Node::ESCAPE_NONE);
3258 }
3259 }
3260 }
3261
3262 if (!fn->is_function())
3263 return;
3264
3265 Function_type* fntype = fn->func_value()->type();
3266 Bindings* bindings = fn->func_value()->block()->bindings();
3267
3268 if (fntype->is_method()
3269 && !fntype->receiver()->name().empty()
3270 && !Gogo::is_sink_name(fntype->receiver()->name()))
3271 {
3272 Named_object* rcvr_no = bindings->lookup(fntype->receiver()->name());
3273 go_assert(rcvr_no != NULL);
3274 Node* rcvr_node = Node::make_node(rcvr_no);
3275 switch ((rcvr_node->encoding() & ESCAPE_MASK))
3276 {
3277 case Node::ESCAPE_NONE: // not touched by flood
3278 case Node::ESCAPE_RETURN:
3279 if (fntype->receiver()->type()->has_pointer())
3280 // Don't bother tagging for scalars.
3281 fntype->add_receiver_note(rcvr_node->encoding());
3282 break;
3283
3284 case Node::ESCAPE_HEAP: // flooded, moved to heap.
3285 break;
3286
3287 default:
3288 break;
3289 }
3290 }
3291
3292 int i = 0;
3293 if (fntype->parameters() != NULL)
3294 {
3295 const Typed_identifier_list* til = fntype->parameters();
3296 for (Typed_identifier_list::const_iterator p = til->begin();
3297 p != til->end();
3298 ++p, ++i)
3299 {
3300 if (p->name().empty() || Gogo::is_sink_name(p->name()))
3301 {
3302 // Parameter not used in the function body, does not escape.
3303 if (p->type()->has_pointer())
3304 fntype->add_parameter_note(i, Node::ESCAPE_NONE);
3305 continue;
3306 }
3307
3308 Named_object* param_no = bindings->lookup(p->name());
3309 go_assert(param_no != NULL);
3310 Node* param_node = Node::make_node(param_no);
3311 switch ((param_node->encoding() & ESCAPE_MASK))
3312 {
3313 case Node::ESCAPE_NONE: // not touched by flood
3314 case Node::ESCAPE_RETURN:
3315 if (p->type()->has_pointer())
3316 // Don't bother tagging for scalars.
3317 fntype->add_parameter_note(i, param_node->encoding());
3318 break;
3319
3320 case Node::ESCAPE_HEAP: // flooded, moved to heap.
3321 break;
3322
3323 default:
3324 break;
3325 }
3326 }
3327 }
3328 fntype->set_is_tagged();
3329 }
3330
3331 // Tag each top-level function with escape information that will be used to
3332 // retain analysis results across imports.
3333
3334 void
3335 Gogo::tag_function(Escape_context* context, Named_object* fn)
3336 {
3337 Escape_analysis_tag eat(context);
3338 eat.tag(fn);
3339 }
Mirror of the offical gcc git repository hosted at gcc.gnu.org