Branch data 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 : 14594131 : Node::type() const
30 : : {
31 : 14596825 : if (this->object() != NULL
32 : 718976 : && this->object()->is_variable())
33 : 709164 : return this->object()->var_value()->type();
34 : 13887661 : else if (this->object() != NULL
35 : 9812 : && this->object()->is_function())
36 : 0 : return this->object()->func_value()->type();
37 : 13887661 : else if (this->expr() != NULL)
38 : 12981973 : return this->expr()->type();
39 : 905688 : else if (this->is_indirect())
40 : : {
41 : 512948 : 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 : 253780 : 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 : 141292 : else if (this->child()->type()->is_string_type())
51 : 1884 : return Type::lookup_integer_type("uint8");
52 : : else
53 : 139408 : 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 : 642042 : Node::location() const
66 : : {
67 : 643176 : if (this->object() != NULL && !this->object()->is_sink())
68 : 0 : return this->object()->location();
69 : 643176 : else if (this->expr() != NULL)
70 : 642042 : 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 : 98321700 : Node::state(Escape_context* context, Named_object* fn)
434 : : {
435 : 98321700 : if (this->state_ == NULL)
436 : : {
437 : 7090100 : if (this->expr() != NULL && this->expr()->var_expression() != NULL)
438 : : {
439 : : // Tie state of variable references to underlying variables.
440 : 1324503 : Named_object* var_no = this->expr()->var_expression()->named_object();
441 : 1324503 : Node* var_node = Node::make_node(var_no);
442 : 1324503 : this->state_ = var_node->state(context, fn);
443 : : }
444 : : else
445 : : {
446 : 5765597 : this->state_ = new Node::Escape_state;
447 : 5765597 : if (fn == NULL)
448 : 5358005 : fn = context->current_function();
449 : :
450 : 5765597 : this->state_->fn = fn;
451 : : }
452 : : }
453 : 98321700 : go_assert(this->state_ != NULL);
454 : 98321700 : return this->state_;
455 : : }
456 : :
457 : 12374408 : Node::~Node()
458 : : {
459 : 12374408 : if (this->state_ != NULL)
460 : : {
461 : 7090100 : 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 : 5765597 : delete this->state_;
465 : : }
466 : 12374408 : }
467 : :
468 : : int
469 : 85635667 : Node::encoding()
470 : : {
471 : 85635667 : if (this->expr() != NULL
472 : 45641723 : && this->expr()->var_expression() != NULL)
473 : : {
474 : : // Get the underlying object's encoding.
475 : 20071463 : Named_object* no = this->expr()->var_expression()->named_object();
476 : 20071463 : int enc = Node::make_node(no)->encoding();
477 : 20071463 : this->encoding_ = enc;
478 : : }
479 : 85635667 : return this->encoding_;
480 : : }
481 : :
482 : : void
483 : 5458915 : Node::set_encoding(int enc)
484 : : {
485 : 7066162 : this->encoding_ = enc;
486 : 7066162 : if (this->expr() != NULL)
487 : : {
488 : 3854371 : if (this->expr()->var_expression() != NULL)
489 : : {
490 : : // Set underlying object as well.
491 : 1582054 : Named_object* no = this->expr()->var_expression()->named_object();
492 : 1582054 : Node::make_node(no)->set_encoding(enc);
493 : : }
494 : 2272317 : 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 : 5458915 : }
504 : :
505 : : bool
506 : 9084455 : Node::is_big(Escape_context* context) const
507 : : {
508 : 9084455 : Type* t = this->type();
509 : 9084455 : if (t == NULL
510 : 9084455 : || t->is_call_multiple_result_type()
511 : 8991635 : || t->is_sink_type()
512 : 8985450 : || t->is_void_type()
513 : 17841338 : || t->is_abstract())
514 : 362686 : return false;
515 : :
516 : 8721769 : bool big = false;
517 : 16690532 : if (t->struct_type() != NULL
518 : 654046 : || (t->array_type() != NULL && !t->is_slice_type()))
519 : : {
520 : 853245 : int64_t size;
521 : 853245 : bool ok = t->backend_type_size(context->gogo(), &size);
522 : 1706080 : big = ok && (size < 0 || size > 10 * 1024 * 1024);
523 : : }
524 : :
525 : 8721769 : if (this->expr() != NULL)
526 : : {
527 : 8721769 : 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 : 8715291 : else if (this->expr()->call_expression() != NULL)
540 : : {
541 : 458143 : Call_expression* call = this->expr()->call_expression();
542 : 458143 : Func_expression* fn = call->fn()->func_expression();
543 : 427578 : if (fn != NULL
544 : 427578 : && 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 : 1728608 : Node::is_sink() const
574 : : {
575 : 1728608 : if (this->object() != NULL
576 : 801761 : && this->object()->is_sink())
577 : : return true;
578 : 1219589 : else if (this->expr() != NULL
579 : 713444 : && 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 : 27418982 : Node::make_node(Named_object* no)
593 : : {
594 : 27418982 : std::pair<Named_object*, Node*> val(no, NULL);
595 : 27418982 : std::pair<Unordered_map(Named_object*, Node*)::iterator, bool> ins =
596 : 27418982 : Node::objects.insert(val);
597 : 27418982 : if (ins.second)
598 : 2673810 : ins.first->second = new Node(no);
599 : 27418982 : return ins.first->second;
600 : : }
601 : :
602 : : // Make an expression node or return a cached node for this expression.
603 : :
604 : : Node*
605 : 30898927 : Node::make_node(Expression* e)
606 : : {
607 : 30898927 : std::pair<Expression*, Node*> val(e, NULL);
608 : 30898927 : std::pair<Unordered_map(Expression*, Node*)::iterator, bool> ins =
609 : 30898927 : Node::expressions.insert(val);
610 : 30898927 : if (ins.second)
611 : 9156253 : ins.first->second = new Node(e);
612 : 30898927 : return ins.first->second;
613 : : }
614 : :
615 : : // Make a statement node or return a cached node for this statement.
616 : :
617 : : Node*
618 : 2039937 : Node::make_node(Statement* s)
619 : : {
620 : 2039937 : std::pair<Statement*, Node*> val(s, NULL);
621 : 2039937 : std::pair<Unordered_map(Statement*, Node*)::iterator, bool> ins =
622 : 2039937 : Node::statements.insert(val);
623 : 2039937 : if (ins.second)
624 : 422696 : ins.first->second = new Node(s);
625 : 2039937 : return ins.first->second;
626 : : }
627 : :
628 : : // Make an indirect node with given child.
629 : :
630 : : Node*
631 : 121649 : Node::make_indirect_node(Node* child)
632 : : {
633 : 121649 : Node* n = new Node(child);
634 : 121649 : Node::indirects.push_back(n);
635 : 121649 : 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 : 280347 : Node::max_encoding(int e, int etype)
643 : : {
644 : 280347 : if ((e & ESCAPE_MASK) > etype)
645 : : return e;
646 : 276815 : if (etype == Node::ESCAPE_NONE || etype == Node::ESCAPE_RETURN)
647 : 276815 : 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 : 29494 : 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 : 29494 : if (level.value() <= 0 && level.suffix_value() > 0)
662 : 615 : return Node::max_encoding(e|ESCAPE_CONTENT_ESCAPES, Node::ESCAPE_NONE);
663 : 28879 : if (level.value() < 0)
664 : : return Node::ESCAPE_HEAP;
665 : 26149 : if (level.value() > ESCAPE_MAX_ENCODED_LEVEL)
666 : : level = Level::From(ESCAPE_MAX_ENCODED_LEVEL);
667 : :
668 : 26149 : int encoded = level.value() + 1;
669 : 26149 : int shift = ESCAPE_BITS_PER_OUTPUT_IN_TAG * index + ESCAPE_RETURN_BITS;
670 : 26149 : int old = (e >> shift) & ESCAPE_BITS_MASK_FOR_TAG;
671 : 26149 : if (old == 0
672 : 6222 : || (encoded != 0 && encoded < old))
673 : 20107 : old = encoded;
674 : :
675 : 26149 : int encoded_flow = old << shift;
676 : 26149 : 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 : 26149 : 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 : 593668 : Escape_context::init_retvals(Node* n, Function_type* fntype)
748 : : {
749 : 593668 : if (fntype == NULL || fntype->results() == NULL)
750 : 186955 : return;
751 : :
752 : 406713 : Node::Escape_state* state = n->state(this, NULL);
753 : 406713 : state->retvals.clear();
754 : 406713 : Location loc = n->location();
755 : :
756 : 406713 : int i = 0;
757 : 406713 : char buf[50];
758 : 406713 : for (Typed_identifier_list::const_iterator p = fntype->results()->begin();
759 : 904141 : p != fntype->results()->end();
760 : 497428 : ++p, ++i)
761 : : {
762 : 497428 : snprintf(buf, sizeof buf, ".out%d", i);
763 : 497428 : Variable* dummy_var = new Variable(p->type(), NULL, false, false,
764 : 497428 : false, loc);
765 : 497428 : dummy_var->set_is_used();
766 : 497428 : Named_object* dummy_no =
767 : 497428 : Named_object::make_variable(buf, NULL, dummy_var);
768 : 497428 : Node* dummy_node = Node::make_node(dummy_no);
769 : : // Initialize the state of the dummy output node.
770 : 497428 : Node::Escape_state* dummy_node_state = dummy_node->state(this, NULL);
771 : 497428 : dummy_node_state->loop_depth = this->loop_depth_;
772 : :
773 : : // Add dummy node to the retvals of n.
774 : 497428 : state->retvals.push_back(dummy_node);
775 : : }
776 : : }
777 : :
778 : :
779 : : // Apply an indirection to N and return the result.
780 : :
781 : : Node*
782 : 235329 : Escape_context::add_dereference(Node* n)
783 : : {
784 : 235329 : Expression* e = n->expr();
785 : 235329 : Location loc = n->location();
786 : 235329 : Node* ind;
787 : 235329 : if (e != NULL
788 : 234385 : && e->type()->points_to() != NULL
789 : 350356 : && !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 : 121649 : ind = Node::make_indirect_node(n);
800 : :
801 : : // Initialize the state.
802 : 235329 : Node::Escape_state* state = ind->state(this, NULL);
803 : 235329 : state->loop_depth = n->state(this, NULL)->loop_depth;
804 : 235329 : return ind;
805 : : }
806 : :
807 : : void
808 : 937732 : Escape_context::track(Node* n)
809 : : {
810 : 937732 : n->set_encoding(Node::ESCAPE_NONE);
811 : : // Initialize this node's state if it hasn't been encountered
812 : : // before.
813 : 937732 : Node::Escape_state* state = n->state(this, NULL);
814 : 937732 : state->loop_depth = this->loop_depth_;
815 : :
816 : 937732 : this->noesc_.push_back(n);
817 : 937732 : }
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 : 4644 : Gogo::analyze_escape()
884 : : {
885 : 4644 : if (saw_errors())
886 : : return;
887 : :
888 : 4250 : if (!optimize_allocation_flag.is_enabled()
889 : 4250 : && !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 : 4250 : this->discover_analysis_sets();
896 : :
897 : 4250 : if (!this->debug_escape_hash().empty())
898 : 0 : std::cerr << "debug-escape-hash " << this->debug_escape_hash() << "\n";
899 : :
900 : 1362000 : for (std::vector<Analysis_set>::iterator p = this->analysis_sets_.begin();
901 : 1362000 : p != this->analysis_sets_.end();
902 : 1357750 : ++p)
903 : : {
904 : 1357750 : std::vector<Named_object*> stack = p->first;
905 : :
906 : 1357750 : 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 : 2742295 : for (std::vector<Named_object*>::reverse_iterator fn = stack.rbegin();
942 : 2742295 : fn != stack.rend();
943 : 1384545 : ++fn)
944 : : {
945 : 1384545 : context->set_current_function(*fn);
946 : 1384545 : 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 : 2396715 : for (std::set<Node*>::iterator n = dsts.begin();
953 : 2396715 : n != dsts.end();
954 : 1038965 : ++n)
955 : : {
956 : 1038965 : escapes[*n] = (*n)->encoding();
957 : 1038965 : 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 : 2475191 : for (std::set<Node*>::iterator n = dsts.begin();
965 : 2475191 : n != dsts.end();
966 : 1115605 : ++n)
967 : : {
968 : 1115605 : if ((*n)->object() == NULL
969 : 1115605 : && ((*n)->expr() == NULL
970 : 510247 : || ((*n)->expr()->var_expression() == NULL
971 : 899337 : && (*n)->expr()->enclosed_var_expression() == NULL
972 : 899337 : && (*n)->expr()->func_expression() == NULL)))
973 : 577506 : continue;
974 : 538099 : if (escapes[*n] != (*n)->encoding())
975 : : {
976 : 2731 : done = false;
977 : 2731 : 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 : 2731 : escapes[*n] = (*n)->encoding();
982 : 2731 : 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 : 2742295 : for (std::vector<Named_object*>::iterator fn = stack.begin();
991 : 2742295 : fn != stack.end();
992 : 1384545 : ++fn)
993 : 1384545 : 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 : 4250 : Escape_analysis_discover(Gogo* gogo)
1021 : 4250 : : Traverse(traverse_functions | traverse_func_declarations),
1022 : 4250 : gogo_(gogo), component_ids_()
1023 : 4250 : { }
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 : 186705 : Escape_analysis_discover::function(Named_object* fn)
1058 : : {
1059 : 186705 : this->visit(fn);
1060 : 186705 : return TRAVERSE_CONTINUE;
1061 : : }
1062 : :
1063 : : int
1064 : 1149082 : Escape_analysis_discover::function_declaration(Named_object* fn)
1065 : : {
1066 : 1149082 : this->visit(fn);
1067 : 1149082 : 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 : 2087571 : Escape_analysis_discover::visit(Named_object* fn)
1096 : : {
1097 : 2087571 : Component_ids::const_iterator p = this->component_ids_.find(fn);
1098 : 2087571 : if (p != this->component_ids_.end())
1099 : : // Already visited.
1100 : 702937 : return p->second;
1101 : :
1102 : 1384634 : this->id++;
1103 : 1384634 : int id = this->id;
1104 : 1384634 : this->component_ids_[fn] = id;
1105 : 1384634 : this->id++;
1106 : 1384634 : int min = this->id;
1107 : :
1108 : 1384634 : this->stack_.push(fn);
1109 : 1384634 : min = this->visit_code(fn, min);
1110 : 1383180 : if ((min == id || min == id + 1)
1111 : 2765008 : && ((fn->is_function() && fn->func_value()->enclosing() == NULL)
1112 : 1222007 : || fn->is_function_declaration()))
1113 : : {
1114 : 1357750 : bool recursive = min == id;
1115 : 1357750 : std::vector<Named_object*> group;
1116 : :
1117 : 1384545 : for (; !this->stack_.empty(); this->stack_.pop())
1118 : : {
1119 : 1384545 : Named_object* n = this->stack_.top();
1120 : 1384545 : if (n == fn)
1121 : : {
1122 : 1357750 : this->stack_.pop();
1123 : 1357750 : break;
1124 : : }
1125 : :
1126 : 26795 : group.push_back(n);
1127 : 26795 : 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 : 186705 : class Escape_discover_expr : public Traverse
1143 : : {
1144 : : public:
1145 : 186705 : Escape_discover_expr(Escape_analysis_discover* ead, int min)
1146 : 186705 : : Traverse(traverse_expressions),
1147 : 186705 : ead_(ead), min_(min)
1148 : : { }
1149 : :
1150 : : int
1151 : 186705 : min()
1152 : 186705 : { 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 : 727575 : fn = e->call_expression()->fn()->func_expression()->named_object();
1176 : : }
1177 : 8448195 : else if (e->func_expression() != NULL)
1178 : : {
1179 : 753993 : Named_object* no = e->func_expression()->named_object();
1180 : 753993 : if (no->is_function() && no->func_value()->enclosing() != NULL)
1181 : : {
1182 : : // Nested function.
1183 : : fn = no;
1184 : : }
1185 : : }
1186 : :
1187 : 751784 : if (fn != NULL)
1188 : 756507 : 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 : 1384634 : Escape_analysis_discover::visit_code(Named_object* fn, int min)
1197 : : {
1198 : 1384634 : if (!fn->is_function())
1199 : : return min;
1200 : :
1201 : 186705 : Escape_discover_expr ede(this, min);
1202 : 186705 : fn->func_value()->traverse(&ede);
1203 : 186705 : return ede.min();
1204 : 186705 : }
1205 : :
1206 : : // Discover strongly connected groups of functions to analyze.
1207 : :
1208 : : void
1209 : 4250 : Gogo::discover_analysis_sets()
1210 : : {
1211 : 4250 : Escape_analysis_discover ead(this);
1212 : 4250 : this->traverse(&ead);
1213 : 4250 : }
1214 : :
1215 : : // Traverse all label and goto statements and mark the underlying label
1216 : : // as looping or not looping.
1217 : :
1218 : 186616 : class Escape_analysis_loop : public Traverse
1219 : : {
1220 : : public:
1221 : 186616 : Escape_analysis_loop()
1222 : 186616 : : Traverse(traverse_statements)
1223 : : { }
1224 : :
1225 : : int
1226 : : statement(Block*, size_t*, Statement*);
1227 : : };
1228 : :
1229 : : int
1230 : 3765724 : Escape_analysis_loop::statement(Block*, size_t*, Statement* s)
1231 : : {
1232 : 3765724 : if (s->label_statement() != NULL)
1233 : 1507 : s->label_statement()->label()->set_nonlooping();
1234 : 3764217 : 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 : 3765724 : 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 : 373232 : class Escape_analysis_assign : public Traverse
1247 : : {
1248 : : public:
1249 : 186616 : Escape_analysis_assign(Escape_context* context)
1250 : 186616 : : Traverse(traverse_statements
1251 : : | traverse_expressions),
1252 : 186616 : 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 : 716614 : is_self_assignment(Expression* lhs, Expression* rhs)
1300 : : {
1301 : 716614 : Unary_expression* lue =
1302 : 716614 : (lhs->field_reference_expression() != NULL
1303 : 79638 : ? lhs->field_reference_expression()->expr()->unary_expression()
1304 : 63384 : : lhs->unary_expression());
1305 : : Var_expression* lve =
1306 : 736031 : (lue != NULL && lue->op() == OPERATOR_MULT ? lue->operand()->var_expression() : NULL);
1307 : 716614 : Array_index_expression* raie = rhs->array_index_expression();
1308 : 716614 : String_index_expression* rsie = rhs->string_index_expression();
1309 : 716614 : Expression* rarray =
1310 : 35652 : (raie != NULL && raie->end() != NULL && raie->array()->type()->is_slice_type()
1311 : 724881 : ? raie->array()
1312 : 1424961 : : (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 : 716655 : (rue != NULL && rue->op() == OPERATOR_MULT ? rue->operand()->var_expression() : NULL);
1319 : 716614 : return lve != NULL && rve != NULL
1320 : 716614 : && lve->named_object() == rve->named_object();
1321 : : }
1322 : :
1323 : : // Model statements within a function as assignments and flows between nodes.
1324 : :
1325 : : int
1326 : 3765724 : 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 : 3765724 : bool is_for_statement = (s->is_block_statement()
1330 : 3765724 : && s->block_statement()->is_lowered_for_statement());
1331 : 53271 : if (is_for_statement)
1332 : 53271 : this->context_->increase_loop_depth();
1333 : :
1334 : 3765724 : s->traverse_contents(this);
1335 : :
1336 : 3765724 : if (is_for_statement)
1337 : 53271 : this->context_->decrease_loop_depth();
1338 : :
1339 : 3765724 : Gogo* gogo = this->context_->gogo();
1340 : 3765724 : int debug_level = gogo->debug_escape_level();
1341 : 3765724 : if (debug_level > 1
1342 : 3765724 : && s->unnamed_label_statement() == NULL
1343 : : && s->expression_statement() == NULL
1344 : 3765724 : && !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 : 3765724 : switch (s->classification())
1354 : : {
1355 : 382188 : case Statement::STATEMENT_VARIABLE_DECLARATION:
1356 : 382188 : {
1357 : 382188 : Named_object* var = s->variable_declaration_statement()->var();
1358 : 382188 : Node* var_node = Node::make_node(var);
1359 : 382188 : Node::Escape_state* state = var_node->state(this->context_, NULL);
1360 : 382188 : state->loop_depth = this->context_->loop_depth();
1361 : :
1362 : : // Set the loop depth for this declaration.
1363 : 382188 : if (var->is_variable()
1364 : 382188 : && var->var_value()->init() != NULL)
1365 : : {
1366 : 280522 : Node* init_node = Node::make_node(var->var_value()->init());
1367 : 280522 : 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 : : ? "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 : 716614 : case Statement::STATEMENT_ASSIGNMENT:
1412 : 716614 : {
1413 : 716614 : Assignment_statement* assn = s->assignment_statement();
1414 : 716614 : Expression* lhs = assn->lhs();
1415 : 716614 : Expression* rhs = assn->rhs();
1416 : 716614 : Node* lhs_node = Node::make_node(lhs);
1417 : 716614 : 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 : 716614 : 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 : 715012 : this->assign(lhs_node, rhs_node);
1439 : : }
1440 : 715012 : 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 : 3765724 : return TRAVERSE_SKIP_COMPONENTS;
1489 : : }
1490 : :
1491 : : // Helper function to emit moved-to-heap diagnostics.
1492 : :
1493 : : static void
1494 : 65434 : move_to_heap(Gogo* gogo, Expression *expr)
1495 : : {
1496 : 65434 : Named_object* no;
1497 : 65434 : if (expr->var_expression() != NULL)
1498 : 26947 : 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 : 29071 : if ((no->is_variable()
1505 : 28942 : && !no->var_value()->is_global())
1506 : 33377 : || no->is_result_variable())
1507 : : {
1508 : 24765 : Node* n = Node::make_node(expr);
1509 : 24765 : 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 : 24765 : 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 : 9084461 : Escape_analysis_assign::expression(Expression** pexpr)
1524 : : {
1525 : 9084461 : Gogo* gogo = this->context_->gogo();
1526 : 9084461 : int debug_level = gogo->debug_escape_level();
1527 : :
1528 : : // Big stuff escapes unconditionally.
1529 : 9084461 : Node* n = Node::make_node(*pexpr);
1530 : 9084461 : if ((n->encoding() & ESCAPE_MASK) != int(Node::ESCAPE_HEAP)
1531 : 9084461 : && 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 : 9084461 : if ((*pexpr)->func_expression() == NULL)
1543 : 8330644 : (*pexpr)->traverse_subexpressions(this);
1544 : :
1545 : 9084461 : 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 : 9084461 : switch ((*pexpr)->classification())
1554 : : {
1555 : 781333 : case Expression::EXPRESSION_CALL:
1556 : 781333 : {
1557 : 781333 : Call_expression* call = (*pexpr)->call_expression();
1558 : 781333 : 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 : 649285 : Func_expression* fe = call->fn()->func_expression();
1640 : 595351 : 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 : 605187 : 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 : 124845 : 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 : 753817 : case Expression::EXPRESSION_FUNC_REFERENCE:
1897 : 753817 : {
1898 : 753817 : Func_expression* fe = (*pexpr)->func_expression();
1899 : 753817 : 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 : 38246 : for (; p != sce->vals()->end(); ++p)
1916 : : {
1917 : 25279 : Node* enclosed_node = Node::make_node(*p);
1918 : 25279 : this->context_->track(enclosed_node);
1919 : 25279 : this->assign(closure_node, enclosed_node);
1920 : : }
1921 : : }
1922 : : }
1923 : : break;
1924 : :
1925 : 618406 : case Expression::EXPRESSION_UNARY:
1926 : 618406 : {
1927 : 618406 : Expression* operand = (*pexpr)->unary_expression()->operand();
1928 : :
1929 : 618406 : if ((*pexpr)->unary_expression()->op() == OPERATOR_AND)
1930 : : {
1931 : 163673 : this->context_->track(n);
1932 : :
1933 : 163673 : Named_object* var = NULL;
1934 : 163673 : if (operand->var_expression() != NULL)
1935 : 74304 : 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 : 76517 : if (var != NULL
1940 : 76517 : && ((var->is_variable() && var->var_value()->is_parameter())
1941 : 62953 : || var->is_result_variable()))
1942 : : {
1943 : 14006 : Node::Escape_state* addr_state = n->state(this->context_, NULL);
1944 : 14006 : addr_state->loop_depth = 1;
1945 : 14006 : 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 : 9084461 : 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 : 605187 : Escape_analysis_assign::call(Call_expression* call)
2010 : : {
2011 : 605187 : Gogo* gogo = this->context_->gogo();
2012 : 605187 : int debug_level = gogo->debug_escape_level();
2013 : :
2014 : 605187 : Func_expression* fn = call->fn()->func_expression();
2015 : 605187 : Function_type* fntype = call->get_function_type();
2016 : 605187 : bool indirect = false;
2017 : :
2018 : : // Interface method calls or closure calls are indirect calls.
2019 : 605187 : if (fntype == NULL
2020 : 605187 : || (fntype->is_method()
2021 : 249881 : && fntype->receiver()->type()->interface_type() != NULL)
2022 : 605187 : || fn == NULL
2023 : 1156440 : || (fn->named_object()->is_function()
2024 : 329193 : && fn->named_object()->func_value()->enclosing() != NULL))
2025 : : indirect = true;
2026 : :
2027 : 605187 : Node* call_node = Node::make_node(call);
2028 : 605187 : std::vector<Node*> arg_nodes;
2029 : 605187 : 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 : 605187 : if (call->args() != NULL)
2038 : : {
2039 : 548971 : for (Expression_list::const_iterator p = call->args()->begin();
2040 : 1634605 : p != call->args()->end();
2041 : 1085634 : ++p)
2042 : 1085634 : arg_nodes.push_back(Node::make_node(*p));
2043 : : }
2044 : :
2045 : 605187 : 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 : 130081 : for (std::vector<Node*>::iterator p = arg_nodes.begin();
2050 : 130081 : 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 : 57658 : 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 : 57658 : Node* fn_node = Node::make_node(call->fn());
2066 : 57658 : std::vector<Node*> retvals = call_node->state(this->context_, NULL)->retvals;
2067 : 106538 : for (std::vector<Node*>::const_iterator p = retvals.begin();
2068 : 106538 : p != retvals.end();
2069 : 48880 : ++p)
2070 : 48880 : this->assign_deref(*p, fn_node);
2071 : :
2072 : 57658 : return;
2073 : 57658 : }
2074 : :
2075 : : // If FN is an untagged function.
2076 : 547529 : if (fn != NULL
2077 : 547529 : && fn->named_object()->is_function()
2078 : 872998 : && !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 : 536010 : 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 : 536010 : Node::Escape_state* call_state = call_node->state(this->context_, NULL);
2167 : 536010 : 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 : 536010 : this->context_->init_retvals(call_node, fntype);
2172 : :
2173 : : // Receiver.
2174 : 536010 : std::vector<Node*>::iterator p = arg_nodes.begin();
2175 : 536010 : if (fntype->is_method()
2176 : 536010 : && 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 : 536010 : const Typed_identifier_list* til = fntype->parameters();
2206 : 536010 : if (til != NULL)
2207 : : {
2208 : 413478 : for (Typed_identifier_list::const_iterator pn = til->begin();
2209 : 1184956 : pn != til->end() && p != arg_nodes.end();
2210 : 771478 : ++pn, ++p)
2211 : : {
2212 : 1542956 : 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 : 771478 : Type* t = pn->type();
2221 : 771478 : if (t != NULL
2222 : 1542956 : && 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 : 413478 : 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 : 605187 : }
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 : 3161911 : Escape_analysis_assign::assign(Node* dst, Node* src)
2255 : : {
2256 : 4175303 : Gogo* gogo = this->context_->gogo();
2257 : 4175303 : int debug_level = gogo->debug_escape_level();
2258 : 4175303 : 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 : 4175303 : if (dst->is_indirect())
2268 : : // Lose track of the dereference.
2269 : 0 : dst = this->context_->sink();
2270 : 4175303 : 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 : 2326746 : Expression* e = dst->expr();
2275 : 2326746 : switch (e->classification())
2276 : : {
2277 : 955947 : case Expression::EXPRESSION_VAR_REFERENCE:
2278 : 955947 : {
2279 : : // If DST is a global variable, we have no way to track it.
2280 : 955947 : Named_object* var = e->var_expression()->named_object();
2281 : 955947 : 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 : 4066159 : if (src->object() != NULL)
2357 : 141773 : this->flows(dst, src);
2358 : 3924386 : else if (src->is_indirect())
2359 : 120705 : this->flows(dst, src);
2360 : 3803681 : else if (src->expr() != NULL)
2361 : : {
2362 : 3483980 : Expression* e = src->expr();
2363 : 3483980 : switch (e->classification())
2364 : : {
2365 : 904053 : case Expression::EXPRESSION_VAR_REFERENCE:
2366 : 904053 : case Expression::EXPRESSION_ENCLOSED_VAR_REFERENCE:
2367 : : // DST = var
2368 : 904053 : case Expression::EXPRESSION_HEAP:
2369 : : // DST = &T{...}.
2370 : 904053 : case Expression::EXPRESSION_FIXED_ARRAY_CONSTRUCTION:
2371 : 904053 : case Expression::EXPRESSION_SLICE_CONSTRUCTION:
2372 : : // DST = [...]T{...}.
2373 : 904053 : case Expression::EXPRESSION_MAP_CONSTRUCTION:
2374 : : // DST = map[T]V{...}.
2375 : 904053 : case Expression::EXPRESSION_STRUCT_CONSTRUCTION:
2376 : : // DST = T{...}.
2377 : 904053 : case Expression::EXPRESSION_SLICE_VALUE:
2378 : : // DST = slice{ptr, len, cap}
2379 : 904053 : case Expression::EXPRESSION_ALLOCATION:
2380 : : // DST = new(T).
2381 : 904053 : case Expression::EXPRESSION_BOUND_METHOD:
2382 : : // DST = x.M.
2383 : 904053 : case Expression::EXPRESSION_STRING_CONCAT:
2384 : : // DST = str1 + str2
2385 : 904053 : this->flows(dst, src);
2386 : 904053 : 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 : 311799 : case Expression::EXPRESSION_CALL:
2408 : 311799 : {
2409 : 311799 : Call_expression* call = e->call_expression();
2410 : 311799 : 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 : 255371 : Func_expression* fe = call->fn()->func_expression();
2476 : 237943 : 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 : 219001 : else if (fe != NULL
2495 : 201573 : && fe->named_object()->is_function()
2496 : 116285 : && fe->named_object()->func_value()->is_method()
2497 : 273470 : && (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 : 219001 : Node* call_node = Node::make_node(e);
2509 : 219001 : Node::Escape_state* call_state = call_node->state(this->context_, NULL);
2510 : 438002 : std::vector<Node*> retvals = call_state->retvals;
2511 : 437999 : for (std::vector<Node*>::const_iterator p = retvals.begin();
2512 : 437999 : p != retvals.end();
2513 : 218998 : ++p)
2514 : 218998 : this->flows(dst, *p);
2515 : : }
2516 : 219001 : 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 : 16661 : case Expression::EXPRESSION_FUNC_REFERENCE:
2563 : 16661 : 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 : 236184 : case Expression::EXPRESSION_UNARY:
2693 : 236184 : {
2694 : 236184 : 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 : 232621 : case OPERATOR_MULT:
2707 : : // DST = *x
2708 : 232621 : case OPERATOR_AND:
2709 : : // DST = &x
2710 : 232621 : this->flows(dst, src);
2711 : 232621 : 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 : 72727 : Escape_analysis_assign::assign_deref(Node* dst, Node* src)
2755 : : {
2756 : 72727 : if (src->expr() != NULL)
2757 : : {
2758 : 72727 : 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 : 72332 : 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 : 2308023 : Escape_analysis_assign::flows(Node* dst, Node* src)
2861 : : {
2862 : : // Don't bother capturing the flow from scalars.
2863 : 2308023 : if (src->type() != NULL && !src->type()->has_pointer())
2864 : : return;
2865 : :
2866 : : // Don't confuse a blank identifier with the sink.
2867 : 1728608 : if (dst->is_sink() && dst != this->context_->sink())
2868 : : return;
2869 : :
2870 : 1726956 : Node::Escape_state* dst_state = dst->state(this->context_, NULL);
2871 : 1726956 : Node::Escape_state* src_state = src->state(this->context_, NULL);
2872 : 1726956 : if (dst == src
2873 : 1726956 : || dst_state == src_state
2874 : 3436115 : || dst_state->flows.find(src) != dst_state->flows.end())
2875 : 19458 : return;
2876 : :
2877 : 1707498 : Gogo* gogo = this->context_->gogo();
2878 : 1707498 : 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 : 1707498 : if (dst_state->flows.empty())
2883 : 1038965 : this->context_->add_dst(dst);
2884 : :
2885 : 1707498 : dst_state->flows.insert(src);
2886 : : }
2887 : :
2888 : : // Build a connectivity graph between nodes in the function being analyzed.
2889 : :
2890 : : void
2891 : 1384545 : Gogo::assign_connectivity(Escape_context* context, Named_object* fn)
2892 : : {
2893 : : // Must be defined outside of this package.
2894 : 1384545 : if (!fn->is_function())
2895 : 1197929 : return;
2896 : :
2897 : 186616 : int save_depth = context->loop_depth();
2898 : 186616 : context->set_loop_depth(1);
2899 : :
2900 : 186616 : Escape_analysis_assign ea(context);
2901 : 186616 : Function::Results* res = fn->func_value()->result_variables();
2902 : 186616 : if (res != NULL)
2903 : : {
2904 : 257510 : for (Function::Results::const_iterator p = res->begin();
2905 : 257510 : p != res->end();
2906 : 142348 : ++p)
2907 : : {
2908 : 142348 : Node* res_node = Node::make_node(*p);
2909 : 142348 : Node::Escape_state* res_state = res_node->state(context, fn);
2910 : 142348 : res_state->fn = fn;
2911 : 142348 : 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 : 142348 : if (context->recursive())
2916 : 3623 : ea.flows(context->sink(), res_node);
2917 : : }
2918 : : }
2919 : :
2920 : 186616 : const Bindings* callee_bindings = fn->func_value()->block()->bindings();
2921 : 186616 : Function_type* fntype = fn->func_value()->type();
2922 : 186616 : Typed_identifier_list* params = (fntype->parameters() != NULL
2923 : 186616 : ? fntype->parameters()->copy()
2924 : 65721 : : new Typed_identifier_list);
2925 : 186616 : if (fntype->receiver() != NULL)
2926 : 76932 : params->push_back(*fntype->receiver());
2927 : :
2928 : 458883 : for (Typed_identifier_list::const_iterator p = params->begin();
2929 : 458883 : 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 : 186616 : Escape_analysis_loop el;
2950 : 186616 : fn->func_value()->traverse(&el);
2951 : :
2952 : 186616 : fn->func_value()->traverse(&ea);
2953 : 186616 : context->set_loop_depth(save_depth);
2954 : 186616 : }
2955 : :
2956 : : class Escape_analysis_flood
2957 : : {
2958 : : public:
2959 : 503068 : Escape_analysis_flood(Escape_context* context)
2960 : 503068 : : 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 : 48383100 : 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 : 48383100 : if (src->expr() != NULL)
2991 : : {
2992 : 37650514 : 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 : 48118740 : Node::Escape_state* src_state = src->state(this->context_, NULL);
3009 : 48118740 : 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 : 29371027 : level = level.min(src_state->level);
3015 : 29371027 : 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 : 11719794 : if (src_state->max_extra_loop_depth >= extra_loop_depth
3021 : 1177523 : || src_state->loop_depth >= extra_loop_depth)
3022 : : return;
3023 : 476759 : src_state->max_extra_loop_depth = extra_loop_depth;
3024 : : }
3025 : : }
3026 : : else
3027 : 18747713 : src_state->max_extra_loop_depth = -1;
3028 : :
3029 : 36875705 : src_state->flood_id = this->context_->flood_id();
3030 : 36875705 : src_state->level = level;
3031 : 36875705 : int mod_loop_depth = std::max(extra_loop_depth, src_state->loop_depth);
3032 : :
3033 : 36875705 : Gogo* gogo = this->context_->gogo();
3034 : 36875705 : int debug_level = gogo->debug_escape_level();
3035 : 36875705 : 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 : 36875705 : this->context_->increase_pdepth();
3050 : :
3051 : : // Input parameter flowing into output parameter?
3052 : 36875705 : Named_object* src_no = NULL;
3053 : 36875705 : if (src->expr() != NULL && src->expr()->var_expression() != NULL)
3054 : 11894303 : src_no = src->expr()->var_expression()->named_object();
3055 : : else
3056 : 24981402 : src_no = src->object();
3057 : 14469955 : bool src_is_param = (src_no != NULL
3058 : 14469955 : && src_no->is_variable()
3059 : 28326128 : && src_no->var_value()->is_parameter());
3060 : :
3061 : 36875705 : Named_object* dst_no = NULL;
3062 : 36875705 : if (dst->expr() != NULL && dst->expr()->var_expression() != NULL)
3063 : 4410037 : dst_no = dst->expr()->var_expression()->named_object();
3064 : : else
3065 : 32465668 : dst_no = dst->object();
3066 : 36057917 : bool dst_is_result = dst_no != NULL && dst_no->is_result_variable();
3067 : 36875705 : Node::Escape_state* dst_state = dst->state(this->context_, NULL);
3068 : :
3069 : 36875705 : if (src_is_param
3070 : 36875705 : && dst_is_result
3071 : 193762 : && src_state->fn == dst_state->fn
3072 : 43168 : && (src->encoding() & ESCAPE_MASK) < int(Node::ESCAPE_HEAP)
3073 : 36905199 : && 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 : 29494 : 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 : 29494 : if ((src->encoding() & ESCAPE_MASK) != Node::ESCAPE_RETURN)
3097 : : {
3098 : 21784 : int enc =
3099 : 21784 : Node::ESCAPE_RETURN | (src->encoding() & ESCAPE_CONTENT_ESCAPES);
3100 : 21784 : src->set_encoding(enc);
3101 : : }
3102 : :
3103 : 29494 : int enc = Node::note_inout_flows(src->encoding(),
3104 : : dst_no->result_var_value()->index(),
3105 : : level);
3106 : 29494 : 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 : 29494 : level = level.copy();
3111 : 33100 : for (std::set<Node*>::const_iterator p = src_state->flows.begin();
3112 : 33100 : p != src_state->flows.end();
3113 : 3606 : ++p)
3114 : 3606 : 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 : 36846211 : if (src_is_param
3122 : 4409655 : && dst->encoding() == Node::ESCAPE_HEAP
3123 : 1102007 : && (src->encoding() & ESCAPE_MASK) < int(Node::ESCAPE_HEAP)
3124 : 36889155 : && level.value() > 0)
3125 : : {
3126 : 42897 : int enc =
3127 : 42897 : Node::max_encoding((src->encoding() | ESCAPE_CONTENT_ESCAPES),
3128 : : Node::ESCAPE_NONE);
3129 : 42897 : src->set_encoding(enc);
3130 : 42897 : 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 : 36846211 : bool src_leaks = (level.value() <= 0
3138 : 16341125 : && level.suffix_value() <= 0
3139 : 52417691 : && dst_state->loop_depth < mod_loop_depth);
3140 : 28504990 : src_leaks = src_leaks || (level.value() <= 0
3141 : 7999904 : && (dst->encoding() & ESCAPE_MASK) == Node::ESCAPE_HEAP);
3142 : : // old src encoding, used to prevent duplicate error messages
3143 : 36846211 : int osrcesc = src->encoding();
3144 : :
3145 : 36846211 : if (src_is_param
3146 : 4409655 : && (src_leaks || dst_state->loop_depth < 0)
3147 : 39357332 : && (src->encoding() & ESCAPE_MASK) < int(Node::ESCAPE_HEAP))
3148 : : {
3149 : 315680 : if (level.suffix_value() > 0)
3150 : : {
3151 : 236835 : int enc =
3152 : 236835 : Node::max_encoding((src->encoding() | ESCAPE_CONTENT_ESCAPES),
3153 : : Node::ESCAPE_NONE);
3154 : 236835 : src->set_encoding(enc);
3155 : 236835 : 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 : 78845 : if (debug_level != 0)
3162 : 0 : go_debug(src->definition_location(), "leaking param: %s",
3163 : 0 : src->ast_format(gogo).c_str());
3164 : 78845 : src->set_encoding(Node::ESCAPE_HEAP);
3165 : : }
3166 : : }
3167 : 36530531 : else if (src->expr() != NULL)
3168 : : {
3169 : 28189438 : Expression* e = src->expr();
3170 : 28189438 : if (e->enclosed_var_expression() != NULL)
3171 : : {
3172 : 289765 : 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 : 289765 : Node* enclosed_node =
3177 : 289765 : Node::make_node(e->enclosed_var_expression()->variable());
3178 : 289765 : this->flood(level, dst, enclosed_node, -1);
3179 : : }
3180 : 27899673 : else if (e->heap_expression() != NULL
3181 : 28270731 : || (e->unary_expression() != NULL
3182 : 2194380 : && e->unary_expression()->op() == OPERATOR_AND))
3183 : : {
3184 : : // Pointer literals and address-of expressions.
3185 : 1823322 : Expression* underlying;
3186 : 1823322 : if (e->heap_expression())
3187 : 356718 : underlying = e->heap_expression()->expr();
3188 : : else
3189 : 1466604 : underlying = e->unary_expression()->operand();
3190 : 1823322 : Node* underlying_node = Node::make_node(underlying);
3191 : :
3192 : : // If the address leaks, the underyling object must be moved
3193 : : // to the heap.
3194 : 1823322 : underlying->address_taken(src_leaks);
3195 : 1823322 : if (src_leaks)
3196 : : {
3197 : 535086 : src->set_encoding(Node::ESCAPE_HEAP);
3198 : 535086 : if (osrcesc != src->encoding())
3199 : : {
3200 : 64778 : move_to_heap(gogo, underlying);
3201 : 64778 : 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 : 64778 : 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 : 768894 : this->flood(level.decrease(), dst,
3214 : : underlying_node, mod_loop_depth);
3215 : 535086 : extra_loop_depth = mod_loop_depth;
3216 : : }
3217 : : else
3218 : : {
3219 : : // Decrease the level each time we take the address of the object.
3220 : 2490807 : this->flood(level.decrease(), dst, underlying_node, -1);
3221 : : }
3222 : : }
3223 : 26076351 : else if (e->slice_literal() != NULL)
3224 : : {
3225 : 628689 : Slice_construction_expression* slice = e->slice_literal();
3226 : 628689 : if (slice->vals() != NULL)
3227 : : {
3228 : 1732825 : for (Expression_list::const_iterator p = slice->vals()->begin();
3229 : 1732825 : p != slice->vals()->end();
3230 : 1107264 : ++p)
3231 : : {
3232 : 1107264 : if ((*p) != NULL)
3233 : 1986024 : this->flood(level.decrease(), dst, Node::make_node(*p), -1);
3234 : : }
3235 : : }
3236 : 628689 : if (src_leaks)
3237 : : {
3238 : 200447 : src->set_encoding(Node::ESCAPE_HEAP);
3239 : 200447 : 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 : 200447 : extra_loop_depth = mod_loop_depth;
3243 : : }
3244 : : }
3245 : 25447662 : else if (e->call_expression() != NULL)
3246 : : {
3247 : 316270 : Call_expression* call = e->call_expression();
3248 : 316270 : if (call->is_builtin())
3249 : : {
3250 : 20501 : Builtin_call_expression* bce = call->builtin_call_expression();
3251 : 20501 : if (bce->code() == Builtin_call_expression::BUILTIN_APPEND)
3252 : : {
3253 : : // Propagate escape information to appendee.
3254 : 20494 : Expression* appendee = call->args()->front();
3255 : 20494 : this->flood(level, dst, Node::make_node(appendee), -1);
3256 : : }
3257 : : }
3258 : 295769 : else if (call->fn()->func_expression() != NULL
3259 : 284408 : && call->fn()->func_expression()->is_runtime_function())
3260 : : {
3261 : 97405 : switch (call->fn()->func_expression()->runtime_code())
3262 : : {
3263 : 97405 : case Runtime::MAKECHAN:
3264 : 97405 : case Runtime::MAKECHAN64:
3265 : 97405 : case Runtime::MAKEMAP:
3266 : 97405 : case Runtime::MAKESLICE:
3267 : 97405 : case Runtime::MAKESLICE64:
3268 : 97405 : if (src_leaks)
3269 : : {
3270 : 31850 : src->set_encoding(Node::ESCAPE_HEAP);
3271 : 31850 : 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 : 31850 : extra_loop_depth = mod_loop_depth;
3275 : : }
3276 : : break;
3277 : :
3278 : : default:
3279 : : break;
3280 : : }
3281 : : }
3282 : 198364 : 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 : 198364 : go_assert(src_state->retvals.size() == 1);
3290 : 198364 : 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 : 198364 : src = src_state->retvals[0];
3297 : 198364 : src_state = src->state(this->context_, NULL);
3298 : : }
3299 : : }
3300 : 25131392 : 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 : 25114435 : else if ((e->map_literal() != NULL
3310 : 25142618 : || e->string_concat_expression() != NULL
3311 : 25088544 : || (e->func_expression() != NULL && e->func_expression()->closure() != NULL)
3312 : 54074 : || e->bound_method_expression() != NULL)
3313 : 54074 : && 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 : 25083225 : else if (e->conversion_expression() != NULL && src_leaks)
3322 : : {
3323 : 706950 : Type_conversion_expression* tce = e->conversion_expression();
3324 : 706950 : Type* ft = tce->expr()->type();
3325 : 706950 : Type* tt = tce->type();
3326 : 808801 : if ((ft->is_string_type() && tt->is_slice_type())
3327 : 725224 : || (ft->is_slice_type() && tt->is_string_type())
3328 : 701792 : || (ft->integer_type() != NULL && tt->is_string_type())
3329 : 706950 : || tt->interface_type() != NULL)
3330 : : {
3331 : : // string([]byte), string([]rune), []byte(string), []rune(string), string(rune),
3332 : : // interface(T)
3333 : 702257 : src->set_encoding(Node::ESCAPE_HEAP);
3334 : 702257 : 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 : 702257 : extra_loop_depth = mod_loop_depth;
3338 : 38245478 : if (tt->interface_type() != NULL
3339 : 697010 : && ft->has_pointer()
3340 : 574746 : && !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 : 24376275 : else if (e->array_index_expression() != NULL
3349 : 1947758 : && !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 : 24371728 : else if ((e->field_reference_expression() != NULL
3369 : 24371728 : && e->field_reference_expression()->expr()->unary_expression() == NULL)
3370 : 24374324 : || e->type_guard_expression() != NULL
3371 : 24242557 : || (e->array_index_expression() != NULL
3372 : 1943211 : && e->array_index_expression()->end() != NULL)
3373 : 291 : || (e->string_index_expression() != NULL
3374 : 291 : && e->type()->is_string_type()))
3375 : : {
3376 : 129462 : Expression* underlying;
3377 : 129462 : if (e->field_reference_expression() != NULL)
3378 : 124834 : 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 : 129462 : Node* underlying_node = Node::make_node(underlying);
3387 : 129462 : this->flood(level, dst, underlying_node, -1);
3388 : : }
3389 : 24242266 : else if ((e->field_reference_expression() != NULL
3390 : 24242266 : && e->field_reference_expression()->expr()->unary_expression() != NULL)
3391 : 24970032 : || e->array_index_expression() != NULL
3392 : 24970032 : || e->map_index_expression() != NULL
3393 : 16131571 : || (e->unary_expression() != NULL
3394 : 727776 : && e->unary_expression()->op() == OPERATOR_MULT))
3395 : : {
3396 : 8838471 : Expression* underlying;
3397 : 8838471 : if (e->field_reference_expression() != NULL)
3398 : : {
3399 : 6169273 : underlying = e->field_reference_expression()->expr();
3400 : 6169273 : underlying = underlying->unary_expression()->operand();
3401 : : }
3402 : 2669198 : else if (e->array_index_expression() != NULL)
3403 : 1940906 : underlying = e->array_index_expression()->array();
3404 : 728292 : else if (e->map_index_expression() != NULL)
3405 : 526 : underlying = e->map_index_expression()->map();
3406 : : else
3407 : 727766 : underlying = e->unary_expression()->operand();
3408 : :
3409 : : // Increase the level for a dereference.
3410 : 8838471 : Node* underlying_node = Node::make_node(underlying);
3411 : 14650302 : this->flood(level.increase(), dst, underlying_node, -1);
3412 : : }
3413 : 15403795 : else if (e->temporary_reference_expression() != NULL)
3414 : : {
3415 : 1245404 : Statement* t = e->temporary_reference_expression()->statement();
3416 : 1245404 : this->flood(level, dst, Node::make_node(t), -1);
3417 : : }
3418 : : }
3419 : 8341093 : else if (src->is_indirect())
3420 : : // Increase the level for a dereference.
3421 : 650373 : this->flood(level.increase(), dst, src->child(), -1);
3422 : :
3423 : 36846211 : level = level.copy();
3424 : 70166449 : for (std::set<Node*>::const_iterator p = src_state->flows.begin();
3425 : 70166449 : p != src_state->flows.end();
3426 : 33320238 : ++p)
3427 : 33320238 : this->flood(level, dst, *p, extra_loop_depth);
3428 : :
3429 : 36846211 : 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 : 1041696 : Gogo::propagate_escape(Escape_context* context, Node* dst)
3437 : : {
3438 : 1041696 : if (dst->object() == NULL
3439 : 838053 : && (dst->expr() == NULL
3440 : 476001 : || (dst->expr()->var_expression() == NULL
3441 : 851494 : && dst->expr()->enclosed_var_expression() == NULL
3442 : 838053 : && dst->expr()->func_expression() == NULL)))
3443 : 538628 : return;
3444 : :
3445 : 503068 : Node::Escape_state* state = dst->state(context, NULL);
3446 : 503068 : Gogo* gogo = context->gogo();
3447 : 503068 : 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 : 503068 : Escape_analysis_flood eaf(context);
3454 : 1584252 : for (std::set<Node*>::const_iterator p = state->flows.begin();
3455 : 1584252 : p != state->flows.end();
3456 : 1081184 : ++p)
3457 : : {
3458 : 1081184 : context->increase_flood_id();
3459 : 1081184 : eaf.flood(Level::From(0), dst, *p, -1);
3460 : : }
3461 : : }
3462 : :
3463 : : class Escape_analysis_tag
3464 : : {
3465 : : public:
3466 : 1384545 : 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 : 1384545 : Escape_analysis_tag::tag(Named_object* fn)
3477 : : {
3478 : : // External functions are assumed unsafe
3479 : : // unless //go:noescape is given before the declaration.
3480 : 1384545 : if (fn->is_function_declaration())
3481 : : {
3482 : 1197929 : Function_declaration* fdcl = fn->func_declaration_value();
3483 : 1197929 : 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 : 1384545 : if (!fn->is_function())
3500 : : return;
3501 : :
3502 : 186616 : Function_type* fntype = fn->func_value()->type();
3503 : 186616 : Bindings* bindings = fn->func_value()->block()->bindings();
3504 : :
3505 : 186616 : 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 : 186616 : int i = 0;
3535 : 186616 : 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 : 186616 : 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 : 1384545 : Gogo::tag_function(Named_object* fn)
3578 : : {
3579 : 1384545 : Escape_analysis_tag eat;
3580 : 1384545 : eat.tag(fn);
3581 : 1384545 : }
3582 : :
3583 : : // Reclaim memory of escape analysis Nodes.
3584 : :
3585 : : void
3586 : 4644 : Gogo::reclaim_escape_nodes()
3587 : : {
3588 : 4644 : Node::reclaim_nodes();
3589 : 4644 : }
3590 : :
3591 : : void
3592 : 4644 : Node::reclaim_nodes()
3593 : : {
3594 : 2678454 : for (Unordered_map(Named_object*, Node*)::iterator p =
3595 : 4644 : Node::objects.begin();
3596 : 2678454 : p != Node::objects.end();
3597 : 2673810 : ++p)
3598 : 2673810 : delete p->second;
3599 : 4644 : Node::objects.clear();
3600 : :
3601 : 9160897 : for (Unordered_map(Expression*, Node*)::iterator p =
3602 : 4644 : Node::expressions.begin();
3603 : 9160897 : p != Node::expressions.end();
3604 : 9156253 : ++p)
3605 : 9156253 : delete p->second;
3606 : 4644 : Node::expressions.clear();
3607 : :
3608 : 427340 : for (Unordered_map(Statement*, Node*)::iterator p =
3609 : 4644 : Node::statements.begin();
3610 : 427340 : p != Node::statements.end();
3611 : 422696 : ++p)
3612 : 422696 : delete p->second;
3613 : 4644 : Node::statements.clear();
3614 : :
3615 : 126293 : for (std::vector<Node*>::iterator p = Node::indirects.begin();
3616 : 126293 : p != Node::indirects.end();
3617 : 121649 : ++p)
3618 : 121649 : delete *p;
3619 : 4644 : Node::indirects.clear();
3620 : 4644 : }
|
