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