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