| 1 |
// escape.cc -- Go escape analysis (based on Go compiler algorithm). |
| 2 |
|
| 3 |
// Copyright 2016 The Go Authors. All rights reserved. |
| 4 |
// Use of this source code is governed by a BSD-style |
| 5 |
// license that can be found in the LICENSE file. |
| 6 |
|
| 7 |
#include "go-system.h" |
| 8 |
|
| 9 |
#include <limits> |
| 10 |
#include <stack> |
| 11 |
#include <sstream> |
| 12 |
|
| 13 |
#include "gogo.h" |
| 14 |
#include "types.h" |
| 15 |
#include "expressions.h" |
| 16 |
#include "statements.h" |
| 17 |
#include "escape.h" |
| 18 |
#include "lex.h" |
| 19 |
#include "ast-dump.h" |
| 20 |
#include "go-optimize.h" |
| 21 |
#include "go-diagnostics.h" |
| 22 |
#include "go-sha1.h" |
| 23 |
|
| 24 |
// class Node. |
| 25 |
|
| 26 |
// Return the node's type, if it makes sense for it to have one. |
| 27 |
|
| 28 |
Type* |
| 29 |
Node::type() const |
| 30 |
{ |
| 31 |
if (this->object() != NULL |
| 32 |
&& this->object()->is_variable()) |
| 33 |
return this->object()->var_value()->type(); |
| 34 |
else if (this->object() != NULL |
| 35 |
&& this->object()->is_function()) |
| 36 |
return this->object()->func_value()->type(); |
| 37 |
else if (this->expr() != NULL) |
| 38 |
return this->expr()->type(); |
| 39 |
else if (this->is_indirect()) |
| 40 |
{ |
| 41 |
if (this->child()->type()->deref()->is_void_type()) |
| 42 |
// This is a void*. The referred type can be actually any type, |
| 43 |
// which may also be pointer. We model it as another void*, so |
| 44 |
// we don't lose pointer-ness. |
| 45 |
return this->child()->type(); |
| 46 |
else 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 |
return this->child()->type()->array_type()->element_type(); |
| 50 |
else if (this->child()->type()->is_string_type()) |
| 51 |
return Type::lookup_integer_type("uint8"); |
| 52 |
else |
| 53 |
return this->child()->type()->deref(); |
| 54 |
} |
| 55 |
else if (this->statement() != NULL |
| 56 |
&& this->statement()->temporary_statement() != NULL) |
| 57 |
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 |
Node::location() const |
| 66 |
{ |
| 67 |
if (this->object() != NULL && !this->object()->is_sink()) |
| 68 |
return this->object()->location(); |
| 69 |
else if (this->expr() != NULL) |
| 70 |
return this->expr()->location(); |
| 71 |
else if (this->statement() != NULL) |
| 72 |
return this->statement()->location(); |
| 73 |
else if (this->is_indirect()) |
| 74 |
return this->child()->location(); |
| 75 |
else |
| 76 |
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 |
Node::definition_location() const |
| 84 |
{ |
| 85 |
if (this->object() != NULL && !this->object()->is_sink()) |
| 86 |
{ |
| 87 |
Named_object* no = this->object(); |
| 88 |
if (no->is_variable() || no->is_result_variable()) |
| 89 |
return no->location(); |
| 90 |
} |
| 91 |
else if (this->expr() != NULL) |
| 92 |
{ |
| 93 |
Var_expression* ve = this->expr()->var_expression(); |
| 94 |
if (ve != NULL) |
| 95 |
{ |
| 96 |
Named_object* no = ve->named_object(); |
| 97 |
if (no->is_variable() || no->is_result_variable()) |
| 98 |
return no->location(); |
| 99 |
} |
| 100 |
Enclosed_var_expression* eve = this->expr()->enclosed_var_expression(); |
| 101 |
if (eve != NULL) |
| 102 |
{ |
| 103 |
Named_object* no = eve->variable(); |
| 104 |
if (no->is_variable() || no->is_result_variable()) |
| 105 |
return no->location(); |
| 106 |
} |
| 107 |
} |
| 108 |
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 |
strip_packed_prefix(Gogo* gogo, const std::string& s) |
| 116 |
{ |
| 117 |
std::string packed_prefix = "." + gogo->pkgpath() + "."; |
| 118 |
std::string fmt = s; |
| 119 |
for (size_t pos = fmt.find(packed_prefix); |
| 120 |
pos != std::string::npos; |
| 121 |
pos = fmt.find(packed_prefix)) |
| 122 |
fmt.erase(pos, packed_prefix.length()); |
| 123 |
return fmt; |
| 124 |
} |
| 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 |
Node::ast_format(Gogo* gogo) const |
| 131 |
{ |
| 132 |
std::ostringstream ss; |
| 133 |
if (this->is_sink()) |
| 134 |
ss << ".sink"; |
| 135 |
else if (this->object() != NULL) |
| 136 |
{ |
| 137 |
Named_object* no = this->object(); |
| 138 |
if (no->is_function() && no->func_value()->enclosing() != NULL) |
| 139 |
return "func literal"; |
| 140 |
ss << no->message_name(); |
| 141 |
} |
| 142 |
else if (this->expr() != NULL) |
| 143 |
{ |
| 144 |
Expression* e = this->expr(); |
| 145 |
|
| 146 |
bool is_call = e->call_expression() != NULL; |
| 147 |
if (is_call) |
| 148 |
e = e->call_expression()->fn(); |
| 149 |
Func_expression* fe = e->func_expression();; |
| 150 |
if (fe != NULL) |
| 151 |
{ |
| 152 |
Named_object* no = fe->named_object(); |
| 153 |
if (no->is_function() && no->func_value()->enclosing() != NULL) |
| 154 |
{ |
| 155 |
if (is_call) |
| 156 |
return "(func literal)()"; |
| 157 |
return "func literal"; |
| 158 |
} |
| 159 |
} |
| 160 |
|
| 161 |
Ast_dump_context::dump_to_stream(this->expr(), &ss); |
| 162 |
} |
| 163 |
else if (this->statement() != NULL) |
| 164 |
{ |
| 165 |
Statement* s = this->statement(); |
| 166 |
Goto_unnamed_statement* unnamed = s->goto_unnamed_statement(); |
| 167 |
if (unnamed != NULL) |
| 168 |
{ |
| 169 |
Statement* derived = unnamed->unnamed_label()->derived_from(); |
| 170 |
if (derived != NULL) |
| 171 |
{ |
| 172 |
switch (derived->classification()) |
| 173 |
{ |
| 174 |
case Statement::STATEMENT_FOR: |
| 175 |
case Statement::STATEMENT_FOR_RANGE: |
| 176 |
return "for loop"; |
| 177 |
break; |
| 178 |
|
| 179 |
case Statement::STATEMENT_SWITCH: |
| 180 |
return "switch"; |
| 181 |
break; |
| 182 |
|
| 183 |
case Statement::STATEMENT_TYPE_SWITCH: |
| 184 |
return "type switch"; |
| 185 |
break; |
| 186 |
|
| 187 |
default: |
| 188 |
break; |
| 189 |
} |
| 190 |
} |
| 191 |
} |
| 192 |
Temporary_statement* tmp = s->temporary_statement(); |
| 193 |
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 |
ss << "tmp." << (uintptr_t) tmp; |
| 199 |
if (tmp->init() != NULL) |
| 200 |
{ |
| 201 |
ss << " [ = "; |
| 202 |
Ast_dump_context::dump_to_stream(tmp->init(), &ss); |
| 203 |
ss << " ]"; |
| 204 |
} |
| 205 |
} |
| 206 |
else |
| 207 |
Ast_dump_context::dump_to_stream(s, &ss); |
| 208 |
} |
| 209 |
else if (this->is_indirect()) |
| 210 |
return "*(" + this->child()->ast_format(gogo) + ")"; |
| 211 |
|
| 212 |
std::string s = strip_packed_prefix(gogo, ss.str()); |
| 213 |
|
| 214 |
// trim trailing space |
| 215 |
return s.substr(0, s.find_last_not_of(' ') + 1); |
| 216 |
} |
| 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 |
Node::details() |
| 223 |
{ |
| 224 |
std::stringstream details; |
| 225 |
|
| 226 |
if (!this->is_sink()) |
| 227 |
details << " l(" << Linemap::location_to_line(this->location()) << ")"; |
| 228 |
|
| 229 |
bool is_varargs = false; |
| 230 |
bool is_address_taken = false; |
| 231 |
bool is_in_heap = false; |
| 232 |
bool is_assigned = false; |
| 233 |
std::string class_name; |
| 234 |
|
| 235 |
Expression* e = this->expr(); |
| 236 |
Named_object* node_object = NULL; |
| 237 |
if (this->object() != NULL) |
| 238 |
node_object = this->object(); |
| 239 |
else if (e != NULL && e->var_expression() != NULL) |
| 240 |
node_object = e->var_expression()->named_object(); |
| 241 |
|
| 242 |
if (node_object) |
| 243 |
{ |
| 244 |
// TODO(cmang): For named variables and functions, we want to output |
| 245 |
// the function depth. |
| 246 |
if (node_object->is_variable()) |
| 247 |
{ |
| 248 |
Variable* var = node_object->var_value(); |
| 249 |
is_varargs = var->is_varargs_parameter(); |
| 250 |
is_address_taken = (var->is_address_taken() |
| 251 |
|| var->is_non_escaping_address_taken()); |
| 252 |
is_in_heap = var->is_in_heap(); |
| 253 |
is_assigned = var->init() != NULL; |
| 254 |
|
| 255 |
if (var->is_global()) |
| 256 |
class_name = "PEXTERN"; |
| 257 |
else if (var->is_parameter()) |
| 258 |
class_name = "PPARAM"; |
| 259 |
else if (var->is_closure()) |
| 260 |
class_name = "PPARAMREF"; |
| 261 |
else |
| 262 |
class_name = "PAUTO"; |
| 263 |
} |
| 264 |
else if (node_object->is_result_variable()) |
| 265 |
class_name = "PPARAMOUT"; |
| 266 |
else if (node_object->is_function() |
| 267 |
|| node_object->is_function_declaration()) |
| 268 |
class_name = "PFUNC"; |
| 269 |
} |
| 270 |
else if (e != NULL && e->enclosed_var_expression() != NULL) |
| 271 |
{ |
| 272 |
Named_object* enclosed = e->enclosed_var_expression()->variable(); |
| 273 |
if (enclosed->is_variable()) |
| 274 |
{ |
| 275 |
Variable* var = enclosed->var_value(); |
| 276 |
is_address_taken = (var->is_address_taken() |
| 277 |
|| var->is_non_escaping_address_taken()); |
| 278 |
} |
| 279 |
else |
| 280 |
{ |
| 281 |
Result_variable* var = enclosed->result_var_value(); |
| 282 |
is_address_taken = (var->is_address_taken() |
| 283 |
|| var->is_non_escaping_address_taken()); |
| 284 |
} |
| 285 |
class_name = "PPARAMREF"; |
| 286 |
} |
| 287 |
|
| 288 |
if (!class_name.empty()) |
| 289 |
{ |
| 290 |
details << " class(" << class_name; |
| 291 |
if (is_in_heap) |
| 292 |
details << ",heap"; |
| 293 |
details << ")"; |
| 294 |
} |
| 295 |
|
| 296 |
switch ((this->encoding() & ESCAPE_MASK)) |
| 297 |
{ |
| 298 |
case Node::ESCAPE_UNKNOWN: |
| 299 |
break; |
| 300 |
|
| 301 |
case Node::ESCAPE_HEAP: |
| 302 |
details << " esc(h)"; |
| 303 |
break; |
| 304 |
|
| 305 |
case Node::ESCAPE_NONE: |
| 306 |
details << " esc(no)"; |
| 307 |
break; |
| 308 |
|
| 309 |
case Node::ESCAPE_NEVER: |
| 310 |
details << " esc(N)"; |
| 311 |
break; |
| 312 |
|
| 313 |
default: |
| 314 |
details << " esc(" << this->encoding() << ")"; |
| 315 |
break; |
| 316 |
} |
| 317 |
|
| 318 |
if (this->state_ != NULL && this->state_->loop_depth != 0) |
| 319 |
details << " ld(" << this->state_->loop_depth << ")"; |
| 320 |
|
| 321 |
if (is_varargs) |
| 322 |
details << " isddd(1)"; |
| 323 |
if (is_address_taken) |
| 324 |
details << " addrtaken"; |
| 325 |
if (is_assigned) |
| 326 |
details << " assigned"; |
| 327 |
|
| 328 |
return details.str(); |
| 329 |
} |
| 330 |
|
| 331 |
std::string |
| 332 |
Node::op_format() const |
| 333 |
{ |
| 334 |
std::stringstream op; |
| 335 |
Ast_dump_context adc(&op, false); |
| 336 |
if (this->expr() != NULL) |
| 337 |
{ |
| 338 |
Expression* e = this->expr(); |
| 339 |
switch (e->classification()) |
| 340 |
{ |
| 341 |
case Expression::EXPRESSION_UNARY: |
| 342 |
adc.dump_operator(e->unary_expression()->op()); |
| 343 |
break; |
| 344 |
|
| 345 |
case Expression::EXPRESSION_BINARY: |
| 346 |
adc.dump_operator(e->binary_expression()->op()); |
| 347 |
break; |
| 348 |
|
| 349 |
case Expression::EXPRESSION_CALL: |
| 350 |
op << "function call"; |
| 351 |
break; |
| 352 |
|
| 353 |
case Expression::EXPRESSION_FUNC_REFERENCE: |
| 354 |
if (e->func_expression()->is_runtime_function()) |
| 355 |
{ |
| 356 |
switch (e->func_expression()->runtime_code()) |
| 357 |
{ |
| 358 |
case Runtime::GOPANIC: |
| 359 |
op << "panic"; |
| 360 |
break; |
| 361 |
|
| 362 |
case Runtime::GROWSLICE: |
| 363 |
op << "append"; |
| 364 |
break; |
| 365 |
|
| 366 |
case Runtime::TYPEDSLICECOPY: |
| 367 |
op << "copy"; |
| 368 |
break; |
| 369 |
|
| 370 |
case Runtime::MAKECHAN: |
| 371 |
case Runtime::MAKECHAN64: |
| 372 |
case Runtime::MAKEMAP: |
| 373 |
case Runtime::MAKESLICE: |
| 374 |
case Runtime::MAKESLICE64: |
| 375 |
op << "make"; |
| 376 |
break; |
| 377 |
|
| 378 |
case Runtime::DEFERPROC: |
| 379 |
op << "defer"; |
| 380 |
break; |
| 381 |
|
| 382 |
case Runtime::GORECOVER: |
| 383 |
op << "recover"; |
| 384 |
break; |
| 385 |
|
| 386 |
case Runtime::CLOSE: |
| 387 |
op << "close"; |
| 388 |
break; |
| 389 |
|
| 390 |
default: |
| 391 |
break; |
| 392 |
} |
| 393 |
} |
| 394 |
break; |
| 395 |
|
| 396 |
case Expression::EXPRESSION_ALLOCATION: |
| 397 |
op << "new"; |
| 398 |
break; |
| 399 |
|
| 400 |
case Expression::EXPRESSION_RECEIVE: |
| 401 |
op << "<-"; |
| 402 |
break; |
| 403 |
|
| 404 |
default: |
| 405 |
break; |
| 406 |
} |
| 407 |
} |
| 408 |
|
| 409 |
if (this->statement() != NULL) |
| 410 |
{ |
| 411 |
switch (this->statement()->classification()) |
| 412 |
{ |
| 413 |
case Statement::STATEMENT_DEFER: |
| 414 |
op << "defer"; |
| 415 |
break; |
| 416 |
|
| 417 |
case Statement::STATEMENT_RETURN: |
| 418 |
op << "return"; |
| 419 |
break; |
| 420 |
|
| 421 |
default: |
| 422 |
break; |
| 423 |
} |
| 424 |
} |
| 425 |
if (this->is_indirect()) |
| 426 |
op << "*"; |
| 427 |
return op.str(); |
| 428 |
} |
| 429 |
|
| 430 |
// Return this node's state, creating it if has not been initialized. |
| 431 |
|
| 432 |
Node::Escape_state* |
| 433 |
Node::state(Escape_context* context, Named_object* fn) |
| 434 |
{ |
| 435 |
if (this->state_ == NULL) |
| 436 |
{ |
| 437 |
if (this->expr() != NULL && this->expr()->var_expression() != NULL) |
| 438 |
{ |
| 439 |
// Tie state of variable references to underlying variables. |
| 440 |
Named_object* var_no = this->expr()->var_expression()->named_object(); |
| 441 |
Node* var_node = Node::make_node(var_no); |
| 442 |
this->state_ = var_node->state(context, fn); |
| 443 |
} |
| 444 |
else |
| 445 |
{ |
| 446 |
this->state_ = new Node::Escape_state; |
| 447 |
if (fn == NULL) |
| 448 |
fn = context->current_function(); |
| 449 |
|
| 450 |
this->state_->fn = fn; |
| 451 |
} |
| 452 |
} |
| 453 |
go_assert(this->state_ != NULL); |
| 454 |
return this->state_; |
| 455 |
} |
| 456 |
|
| 457 |
Node::~Node() |
| 458 |
{ |
| 459 |
if (this->state_ != NULL) |
| 460 |
{ |
| 461 |
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 |
delete this->state_; |
| 465 |
} |
| 466 |
} |
| 467 |
|
| 468 |
int |
| 469 |
Node::encoding() |
| 470 |
{ |
| 471 |
if (this->expr() != NULL |
| 472 |
&& this->expr()->var_expression() != NULL) |
| 473 |
{ |
| 474 |
// Get the underlying object's encoding. |
| 475 |
Named_object* no = this->expr()->var_expression()->named_object(); |
| 476 |
int enc = Node::make_node(no)->encoding(); |
| 477 |
this->encoding_ = enc; |
| 478 |
} |
| 479 |
return this->encoding_; |
| 480 |
} |
| 481 |
|
| 482 |
void |
| 483 |
Node::set_encoding(int enc) |
| 484 |
{ |
| 485 |
this->encoding_ = enc; |
| 486 |
if (this->expr() != NULL) |
| 487 |
{ |
| 488 |
if (this->expr()->var_expression() != NULL) |
| 489 |
{ |
| 490 |
// Set underlying object as well. |
| 491 |
Named_object* no = this->expr()->var_expression()->named_object(); |
| 492 |
Node::make_node(no)->set_encoding(enc); |
| 493 |
} |
| 494 |
else if (this->expr()->func_expression() != NULL) |
| 495 |
{ |
| 496 |
// Propagate the escape state to the underlying |
| 497 |
// closure (heap expression). |
| 498 |
Expression* closure = this->expr()->func_expression()->closure(); |
| 499 |
if (closure != NULL) |
| 500 |
Node::make_node(closure)->set_encoding(enc); |
| 501 |
} |
| 502 |
} |
| 503 |
} |
| 504 |
|
| 505 |
bool |
| 506 |
Node::is_big(Escape_context* context) const |
| 507 |
{ |
| 508 |
Type* t = this->type(); |
| 509 |
if (t == NULL |
| 510 |
|| t->is_call_multiple_result_type() |
| 511 |
|| t->is_sink_type() |
| 512 |
|| t->is_void_type() |
| 513 |
|| t->is_abstract()) |
| 514 |
return false; |
| 515 |
|
| 516 |
bool big = false; |
| 517 |
if (t->struct_type() != NULL |
| 518 |
|| (t->array_type() != NULL && !t->is_slice_type())) |
| 519 |
{ |
| 520 |
int64_t size; |
| 521 |
bool ok = t->backend_type_size(context->gogo(), &size); |
| 522 |
big = ok && (size < 0 || size > 10 * 1024 * 1024); |
| 523 |
} |
| 524 |
|
| 525 |
if (this->expr() != NULL) |
| 526 |
{ |
| 527 |
if (this->expr()->allocation_expression() != NULL) |
| 528 |
{ |
| 529 |
Type* pt = t->deref(); |
| 530 |
if (pt->struct_type() != NULL |
| 531 |
|| (pt->array_type() != NULL && !pt->is_slice_type())) |
| 532 |
{ |
| 533 |
int64_t size; |
| 534 |
bool ok = pt->backend_type_size(context->gogo(), &size); |
| 535 |
if (ok) |
| 536 |
big = big || size <= 0 || size >= (1 << 16); |
| 537 |
} |
| 538 |
} |
| 539 |
else if (this->expr()->call_expression() != NULL) |
| 540 |
{ |
| 541 |
Call_expression* call = this->expr()->call_expression(); |
| 542 |
Func_expression* fn = call->fn()->func_expression(); |
| 543 |
if (fn != NULL |
| 544 |
&& fn->is_runtime_function() |
| 545 |
&& (fn->runtime_code() == Runtime::MAKESLICE |
| 546 |
|| fn->runtime_code() == Runtime::MAKESLICE64)) |
| 547 |
{ |
| 548 |
// Second argument is length. |
| 549 |
Expression_list::iterator p = call->args()->begin(); |
| 550 |
++p; |
| 551 |
|
| 552 |
Expression* e = *p; |
| 553 |
if (e->temporary_reference_expression() != NULL) |
| 554 |
{ |
| 555 |
Temporary_reference_expression* tre = e->temporary_reference_expression(); |
| 556 |
if (tre->statement() != NULL && tre->statement()->init() != NULL) |
| 557 |
e = tre->statement()->init(); |
| 558 |
} |
| 559 |
|
| 560 |
Numeric_constant nc; |
| 561 |
unsigned long v; |
| 562 |
if (e->numeric_constant_value(&nc) |
| 563 |
&& nc.to_unsigned_long(&v) == Numeric_constant::NC_UL_VALID) |
| 564 |
big = big || v >= (1 << 16); |
| 565 |
} |
| 566 |
} |
| 567 |
} |
| 568 |
|
| 569 |
return big; |
| 570 |
} |
| 571 |
|
| 572 |
bool |
| 573 |
Node::is_sink() const |
| 574 |
{ |
| 575 |
if (this->object() != NULL |
| 576 |
&& this->object()->is_sink()) |
| 577 |
return true; |
| 578 |
else if (this->expr() != NULL |
| 579 |
&& this->expr()->is_sink_expression()) |
| 580 |
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 |
Node::make_node(Named_object* no) |
| 593 |
{ |
| 594 |
std::pair<Named_object*, Node*> val(no, NULL); |
| 595 |
std::pair<Unordered_map(Named_object*, Node*)::iterator, bool> ins = |
| 596 |
Node::objects.insert(val); |
| 597 |
if (ins.second) |
| 598 |
ins.first->second = new Node(no); |
| 599 |
return ins.first->second; |
| 600 |
} |
| 601 |
|
| 602 |
// Make an expression node or return a cached node for this expression. |
| 603 |
|
| 604 |
Node* |
| 605 |
Node::make_node(Expression* e) |
| 606 |
{ |
| 607 |
std::pair<Expression*, Node*> val(e, NULL); |
| 608 |
std::pair<Unordered_map(Expression*, Node*)::iterator, bool> ins = |
| 609 |
Node::expressions.insert(val); |
| 610 |
if (ins.second) |
| 611 |
ins.first->second = new Node(e); |
| 612 |
return ins.first->second; |
| 613 |
} |
| 614 |
|
| 615 |
// Make a statement node or return a cached node for this statement. |
| 616 |
|
| 617 |
Node* |
| 618 |
Node::make_node(Statement* s) |
| 619 |
{ |
| 620 |
std::pair<Statement*, Node*> val(s, NULL); |
| 621 |
std::pair<Unordered_map(Statement*, Node*)::iterator, bool> ins = |
| 622 |
Node::statements.insert(val); |
| 623 |
if (ins.second) |
| 624 |
ins.first->second = new Node(s); |
| 625 |
return ins.first->second; |
| 626 |
} |
| 627 |
|
| 628 |
// Make an indirect node with given child. |
| 629 |
|
| 630 |
Node* |
| 631 |
Node::make_indirect_node(Node* child) |
| 632 |
{ |
| 633 |
Node* n = new Node(child); |
| 634 |
Node::indirects.push_back(n); |
| 635 |
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 |
Node::max_encoding(int e, int etype) |
| 643 |
{ |
| 644 |
if ((e & ESCAPE_MASK) > etype) |
| 645 |
return e; |
| 646 |
if (etype == Node::ESCAPE_NONE || etype == Node::ESCAPE_RETURN) |
| 647 |
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 |
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 |
if (level.value() <= 0 && level.suffix_value() > 0) |
| 662 |
return Node::max_encoding(e|ESCAPE_CONTENT_ESCAPES, Node::ESCAPE_NONE); |
| 663 |
if (level.value() < 0) |
| 664 |
return Node::ESCAPE_HEAP; |
| 665 |
if (level.value() > ESCAPE_MAX_ENCODED_LEVEL) |
| 666 |
level = Level::From(ESCAPE_MAX_ENCODED_LEVEL); |
| 667 |
|
| 668 |
int encoded = level.value() + 1; |
| 669 |
int shift = ESCAPE_BITS_PER_OUTPUT_IN_TAG * index + ESCAPE_RETURN_BITS; |
| 670 |
int old = (e >> shift) & ESCAPE_BITS_MASK_FOR_TAG; |
| 671 |
if (old == 0 |
| 672 |
|| (encoded != 0 && encoded < old)) |
| 673 |
old = encoded; |
| 674 |
|
| 675 |
int encoded_flow = old << shift; |
| 676 |
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 |
return (e & ~(ESCAPE_BITS_MASK_FOR_TAG << shift)) | encoded_flow; |
| 683 |
} |
| 684 |
|
| 685 |
// Class Escape_context. |
| 686 |
|
| 687 |
Escape_context::Escape_context(Gogo* gogo, bool recursive) |
| 688 |
: gogo_(gogo), current_function_(NULL), recursive_(recursive), |
| 689 |
sink_(Node::make_node(Named_object::make_sink())), loop_depth_(0), |
| 690 |
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 |
Node::Escape_state* state = this->sink_->state(this, NULL); |
| 695 |
state->loop_depth = -1; |
| 696 |
} |
| 697 |
|
| 698 |
std::string |
| 699 |
debug_function_name(Named_object* fn) |
| 700 |
{ |
| 701 |
if (fn == NULL) |
| 702 |
return "<S>"; |
| 703 |
|
| 704 |
if (!fn->is_function()) |
| 705 |
return Gogo::unpack_hidden_name(fn->name()); |
| 706 |
|
| 707 |
std::string fnname = Gogo::unpack_hidden_name(fn->name()); |
| 708 |
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 |
Type* rt = fn->func_value()->type()->receiver()->type(); |
| 713 |
switch (rt->classification()) |
| 714 |
{ |
| 715 |
case Type::TYPE_NAMED: |
| 716 |
fnname = rt->named_type()->name() + "." + fnname; |
| 717 |
break; |
| 718 |
|
| 719 |
case Type::TYPE_POINTER: |
| 720 |
{ |
| 721 |
Named_type* nt = rt->points_to()->named_type(); |
| 722 |
if (nt != NULL) |
| 723 |
fnname = "(*" + nt->name() + ")." + fnname; |
| 724 |
break; |
| 725 |
} |
| 726 |
|
| 727 |
default: |
| 728 |
break; |
| 729 |
} |
| 730 |
} |
| 731 |
|
| 732 |
return fnname; |
| 733 |
} |
| 734 |
|
| 735 |
// Return the name of the current function. |
| 736 |
|
| 737 |
std::string |
| 738 |
Escape_context::current_function_name() const |
| 739 |
{ |
| 740 |
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 |
Escape_context::init_retvals(Node* n, Function_type* fntype) |
| 748 |
{ |
| 749 |
if (fntype == NULL || fntype->results() == NULL) |
| 750 |
return; |
| 751 |
|
| 752 |
Node::Escape_state* state = n->state(this, NULL); |
| 753 |
state->retvals.clear(); |
| 754 |
Location loc = n->location(); |
| 755 |
|
| 756 |
int i = 0; |
| 757 |
char buf[50]; |
| 758 |
for (Typed_identifier_list::const_iterator p = fntype->results()->begin(); |
| 759 |
p != fntype->results()->end(); |
| 760 |
++p, ++i) |
| 761 |
{ |
| 762 |
snprintf(buf, sizeof buf, ".out%d", i); |
| 763 |
Variable* dummy_var = new Variable(p->type(), NULL, false, false, |
| 764 |
false, loc); |
| 765 |
dummy_var->set_is_used(); |
| 766 |
Named_object* dummy_no = |
| 767 |
Named_object::make_variable(buf, NULL, dummy_var); |
| 768 |
Node* dummy_node = Node::make_node(dummy_no); |
| 769 |
// Initialize the state of the dummy output node. |
| 770 |
Node::Escape_state* dummy_node_state = dummy_node->state(this, NULL); |
| 771 |
dummy_node_state->loop_depth = this->loop_depth_; |
| 772 |
|
| 773 |
// Add dummy node to the retvals of n. |
| 774 |
state->retvals.push_back(dummy_node); |
| 775 |
} |
| 776 |
} |
| 777 |
|
| 778 |
|
| 779 |
// Apply an indirection to N and return the result. |
| 780 |
|
| 781 |
Node* |
| 782 |
Escape_context::add_dereference(Node* n) |
| 783 |
{ |
| 784 |
Expression* e = n->expr(); |
| 785 |
Location loc = n->location(); |
| 786 |
Node* ind; |
| 787 |
if (e != NULL |
| 788 |
&& e->type()->points_to() != NULL |
| 789 |
&& !e->type()->points_to()->is_void_type()) |
| 790 |
{ |
| 791 |
// We don't dereference void*, which can be actually any pointer type. |
| 792 |
Expression* deref_expr = Expression::make_unary(OPERATOR_MULT, e, loc); |
| 793 |
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 |
ind = Node::make_indirect_node(n); |
| 800 |
|
| 801 |
// Initialize the state. |
| 802 |
Node::Escape_state* state = ind->state(this, NULL); |
| 803 |
state->loop_depth = n->state(this, NULL)->loop_depth; |
| 804 |
return ind; |
| 805 |
} |
| 806 |
|
| 807 |
void |
| 808 |
Escape_context::track(Node* n) |
| 809 |
{ |
| 810 |
n->set_encoding(Node::ESCAPE_NONE); |
| 811 |
// Initialize this node's state if it hasn't been encountered |
| 812 |
// before. |
| 813 |
Node::Escape_state* state = n->state(this, NULL); |
| 814 |
state->loop_depth = this->loop_depth_; |
| 815 |
|
| 816 |
this->noesc_.push_back(n); |
| 817 |
} |
| 818 |
|
| 819 |
// Return the string representation of an escapement encoding. |
| 820 |
|
| 821 |
std::string |
| 822 |
Escape_note::make_tag(int encoding) |
| 823 |
{ |
| 824 |
char buf[50]; |
| 825 |
snprintf(buf, sizeof buf, "esc:0x%x", encoding); |
| 826 |
return buf; |
| 827 |
} |
| 828 |
|
| 829 |
// Return the escapement encoding for a string tag. |
| 830 |
|
| 831 |
int |
| 832 |
Escape_note::parse_tag(std::string* tag) |
| 833 |
{ |
| 834 |
if (tag == NULL || tag->substr(0, 4) != "esc:") |
| 835 |
return Node::ESCAPE_UNKNOWN; |
| 836 |
int encoding = (int)strtol(tag->substr(4).c_str(), NULL, 0); |
| 837 |
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 |
escape_hash_match(std::string suffix, std::string name) |
| 852 |
{ |
| 853 |
if (suffix.empty()) |
| 854 |
return true; |
| 855 |
if (suffix.at(0) == '-') |
| 856 |
return !escape_hash_match(suffix.substr(1), name); |
| 857 |
|
| 858 |
const char* p = name.c_str(); |
| 859 |
Go_sha1_helper* sha1_helper = go_create_sha1_helper(); |
| 860 |
sha1_helper->process_bytes(p, strlen(p)); |
| 861 |
std::string s = sha1_helper->finish(); |
| 862 |
delete sha1_helper; |
| 863 |
|
| 864 |
int j = suffix.size() - 1; |
| 865 |
for (int i = s.size() - 1; i >= 0; i--) |
| 866 |
{ |
| 867 |
char c = s.at(i); |
| 868 |
for (int k = 0; k < 8; k++, j--, c>>=1) |
| 869 |
{ |
| 870 |
if (j < 0) |
| 871 |
return true; |
| 872 |
char bit = suffix.at(j) - '0'; |
| 873 |
if ((c&1) != bit) |
| 874 |
return false; |
| 875 |
} |
| 876 |
} |
| 877 |
return false; |
| 878 |
} |
| 879 |
|
| 880 |
// Analyze the program flow for escape information. |
| 881 |
|
| 882 |
void |
| 883 |
Gogo::analyze_escape() |
| 884 |
{ |
| 885 |
if (saw_errors()) |
| 886 |
return; |
| 887 |
|
| 888 |
if (!optimize_allocation_flag.is_enabled() |
| 889 |
&& !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 |
this->discover_analysis_sets(); |
| 896 |
|
| 897 |
if (!this->debug_escape_hash().empty()) |
| 898 |
std::cerr << "debug-escape-hash " << this->debug_escape_hash() << "\n"; |
| 899 |
|
| 900 |
for (std::vector<Analysis_set>::iterator p = this->analysis_sets_.begin(); |
| 901 |
p != this->analysis_sets_.end(); |
| 902 |
++p) |
| 903 |
{ |
| 904 |
std::vector<Named_object*> stack = p->first; |
| 905 |
|
| 906 |
if (!this->debug_escape_hash().empty()) |
| 907 |
{ |
| 908 |
bool match = false; |
| 909 |
for (std::vector<Named_object*>::const_iterator fn = stack.begin(); |
| 910 |
fn != stack.end(); |
| 911 |
++fn) |
| 912 |
match = match || escape_hash_match(this->debug_escape_hash(), (*fn)->message_name()); |
| 913 |
if (!match) |
| 914 |
{ |
| 915 |
// Escape analysis won't run on these functions, but still |
| 916 |
// need to tag them, so the caller knows. |
| 917 |
for (std::vector<Named_object*>::iterator fn = stack.begin(); |
| 918 |
fn != stack.end(); |
| 919 |
++fn) |
| 920 |
if ((*fn)->is_function()) |
| 921 |
{ |
| 922 |
Function_type* fntype = (*fn)->func_value()->type(); |
| 923 |
fntype->set_is_tagged(); |
| 924 |
|
| 925 |
std::cerr << "debug-escape-hash disables " << debug_function_name(*fn) << "\n"; |
| 926 |
} |
| 927 |
|
| 928 |
continue; |
| 929 |
} |
| 930 |
for (std::vector<Named_object*>::const_iterator fn = stack.begin(); |
| 931 |
fn != stack.end(); |
| 932 |
++fn) |
| 933 |
if ((*fn)->is_function()) |
| 934 |
std::cerr << "debug-escape-hash triggers " << debug_function_name(*fn) << "\n"; |
| 935 |
} |
| 936 |
|
| 937 |
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 |
for (std::vector<Named_object*>::reverse_iterator fn = stack.rbegin(); |
| 942 |
fn != stack.rend(); |
| 943 |
++fn) |
| 944 |
{ |
| 945 |
context->set_current_function(*fn); |
| 946 |
this->assign_connectivity(context, *fn); |
| 947 |
} |
| 948 |
|
| 949 |
// Propagate levels across each dst. This is the flood phase. |
| 950 |
std::set<Node*> dsts = context->dsts(); |
| 951 |
Unordered_map(Node*, int) escapes; |
| 952 |
for (std::set<Node*>::iterator n = dsts.begin(); |
| 953 |
n != dsts.end(); |
| 954 |
++n) |
| 955 |
{ |
| 956 |
escapes[*n] = (*n)->encoding(); |
| 957 |
this->propagate_escape(context, *n); |
| 958 |
} |
| 959 |
for (;;) |
| 960 |
{ |
| 961 |
// Reflood if the roots' escape states increase. Run until fix point. |
| 962 |
// This is rare. |
| 963 |
bool done = true; |
| 964 |
for (std::set<Node*>::iterator n = dsts.begin(); |
| 965 |
n != dsts.end(); |
| 966 |
++n) |
| 967 |
{ |
| 968 |
if ((*n)->object() == NULL |
| 969 |
&& ((*n)->expr() == NULL |
| 970 |
|| ((*n)->expr()->var_expression() == NULL |
| 971 |
&& (*n)->expr()->enclosed_var_expression() == NULL |
| 972 |
&& (*n)->expr()->func_expression() == NULL))) |
| 973 |
continue; |
| 974 |
if (escapes[*n] != (*n)->encoding()) |
| 975 |
{ |
| 976 |
done = false; |
| 977 |
if (this->debug_escape_level() > 2) |
| 978 |
go_debug((*n)->location(), "Reflooding %s %s", |
| 979 |
debug_function_name((*n)->state(context, NULL)->fn).c_str(), |
| 980 |
(*n)->ast_format(this).c_str()); |
| 981 |
escapes[*n] = (*n)->encoding(); |
| 982 |
this->propagate_escape(context, *n); |
| 983 |
} |
| 984 |
} |
| 985 |
if (done) |
| 986 |
break; |
| 987 |
} |
| 988 |
|
| 989 |
// Tag each exported function's parameters with escape information. |
| 990 |
for (std::vector<Named_object*>::iterator fn = stack.begin(); |
| 991 |
fn != stack.end(); |
| 992 |
++fn) |
| 993 |
this->tag_function(*fn); |
| 994 |
|
| 995 |
if (this->debug_escape_level() != 0) |
| 996 |
{ |
| 997 |
std::vector<Node*> noesc = context->non_escaping_nodes(); |
| 998 |
for (std::vector<Node*>::const_iterator n = noesc.begin(); |
| 999 |
n != noesc.end(); |
| 1000 |
++n) |
| 1001 |
{ |
| 1002 |
Node::Escape_state* state = (*n)->state(context, NULL); |
| 1003 |
if ((*n)->encoding() == Node::ESCAPE_NONE) |
| 1004 |
go_debug((*n)->location(), "%s %s does not escape", |
| 1005 |
strip_packed_prefix(this, debug_function_name(state->fn)).c_str(), |
| 1006 |
(*n)->ast_format(this).c_str()); |
| 1007 |
} |
| 1008 |
} |
| 1009 |
delete context; |
| 1010 |
} |
| 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 |
Escape_analysis_discover(Gogo* gogo) |
| 1021 |
: Traverse(traverse_functions | traverse_func_declarations), |
| 1022 |
gogo_(gogo), component_ids_() |
| 1023 |
{ } |
| 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 |
Escape_analysis_discover::function(Named_object* fn) |
| 1058 |
{ |
| 1059 |
this->visit(fn); |
| 1060 |
return TRAVERSE_CONTINUE; |
| 1061 |
} |
| 1062 |
|
| 1063 |
int |
| 1064 |
Escape_analysis_discover::function_declaration(Named_object* fn) |
| 1065 |
{ |
| 1066 |
this->visit(fn); |
| 1067 |
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 |
Escape_analysis_discover::visit(Named_object* fn) |
| 1096 |
{ |
| 1097 |
Component_ids::const_iterator p = this->component_ids_.find(fn); |
| 1098 |
if (p != this->component_ids_.end()) |
| 1099 |
// Already visited. |
| 1100 |
return p->second; |
| 1101 |
|
| 1102 |
this->id++; |
| 1103 |
int id = this->id; |
| 1104 |
this->component_ids_[fn] = id; |
| 1105 |
this->id++; |
| 1106 |
int min = this->id; |
| 1107 |
|
| 1108 |
this->stack_.push(fn); |
| 1109 |
min = this->visit_code(fn, min); |
| 1110 |
if ((min == id || min == id + 1) |
| 1111 |
&& ((fn->is_function() && fn->func_value()->enclosing() == NULL) |
| 1112 |
|| fn->is_function_declaration())) |
| 1113 |
{ |
| 1114 |
bool recursive = min == id; |
| 1115 |
std::vector<Named_object*> group; |
| 1116 |
|
| 1117 |
for (; !this->stack_.empty(); this->stack_.pop()) |
| 1118 |
{ |
| 1119 |
Named_object* n = this->stack_.top(); |
| 1120 |
if (n == fn) |
| 1121 |
{ |
| 1122 |
this->stack_.pop(); |
| 1123 |
break; |
| 1124 |
} |
| 1125 |
|
| 1126 |
group.push_back(n); |
| 1127 |
this->component_ids_[n] = std::numeric_limits<int>::max(); |
| 1128 |
} |
| 1129 |
group.push_back(fn); |
| 1130 |
this->component_ids_[fn] = std::numeric_limits<int>::max(); |
| 1131 |
|
| 1132 |
std::reverse(group.begin(), group.end()); |
| 1133 |
this->gogo_->add_analysis_set(group, recursive); |
| 1134 |
} |
| 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 |
class Escape_discover_expr : public Traverse |
| 1143 |
{ |
| 1144 |
public: |
| 1145 |
Escape_discover_expr(Escape_analysis_discover* ead, int min) |
| 1146 |
: Traverse(traverse_expressions), |
| 1147 |
ead_(ead), min_(min) |
| 1148 |
{ } |
| 1149 |
|
| 1150 |
int |
| 1151 |
min() |
| 1152 |
{ 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 |
Escape_discover_expr::expression(Expression** pexpr) |
| 1168 |
{ |
| 1169 |
Expression* e = *pexpr; |
| 1170 |
Named_object* fn = NULL; |
| 1171 |
if (e->call_expression() != NULL |
| 1172 |
&& e->call_expression()->fn()->func_expression() != NULL) |
| 1173 |
{ |
| 1174 |
// Method call or function call. |
| 1175 |
fn = e->call_expression()->fn()->func_expression()->named_object(); |
| 1176 |
} |
| 1177 |
else if (e->func_expression() != NULL) |
| 1178 |
{ |
| 1179 |
Named_object* no = e->func_expression()->named_object(); |
| 1180 |
if (no->is_function() && no->func_value()->enclosing() != NULL) |
| 1181 |
{ |
| 1182 |
// Nested function. |
| 1183 |
fn = no; |
| 1184 |
} |
| 1185 |
} |
| 1186 |
|
| 1187 |
if (fn != NULL) |
| 1188 |
this->min_ = std::min(this->min_, this->ead_->visit(fn)); |
| 1189 |
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 |
Escape_analysis_discover::visit_code(Named_object* fn, int min) |
| 1197 |
{ |
| 1198 |
if (!fn->is_function()) |
| 1199 |
return min; |
| 1200 |
|
| 1201 |
Escape_discover_expr ede(this, min); |
| 1202 |
fn->func_value()->traverse(&ede); |
| 1203 |
return ede.min(); |
| 1204 |
} |
| 1205 |
|
| 1206 |
// Discover strongly connected groups of functions to analyze. |
| 1207 |
|
| 1208 |
void |
| 1209 |
Gogo::discover_analysis_sets() |
| 1210 |
{ |
| 1211 |
Escape_analysis_discover ead(this); |
| 1212 |
this->traverse(&ead); |
| 1213 |
} |
| 1214 |
|
| 1215 |
// Traverse all label and goto statements and mark the underlying label |
| 1216 |
// as looping or not looping. |
| 1217 |
|
| 1218 |
class Escape_analysis_loop : public Traverse |
| 1219 |
{ |
| 1220 |
public: |
| 1221 |
Escape_analysis_loop() |
| 1222 |
: Traverse(traverse_statements) |
| 1223 |
{ } |
| 1224 |
|
| 1225 |
int |
| 1226 |
statement(Block*, size_t*, Statement*); |
| 1227 |
}; |
| 1228 |
|
| 1229 |
int |
| 1230 |
Escape_analysis_loop::statement(Block*, size_t*, Statement* s) |
| 1231 |
{ |
| 1232 |
if (s->label_statement() != NULL) |
| 1233 |
s->label_statement()->label()->set_nonlooping(); |
| 1234 |
else if (s->goto_statement() != NULL) |
| 1235 |
{ |
| 1236 |
if (s->goto_statement()->label()->nonlooping()) |
| 1237 |
s->goto_statement()->label()->set_looping(); |
| 1238 |
} |
| 1239 |
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 |
class Escape_analysis_assign : public Traverse |
| 1247 |
{ |
| 1248 |
public: |
| 1249 |
Escape_analysis_assign(Escape_context* context) |
| 1250 |
: Traverse(traverse_statements |
| 1251 |
| traverse_expressions), |
| 1252 |
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 |
is_self_assignment(Expression* lhs, Expression* rhs) |
| 1300 |
{ |
| 1301 |
Unary_expression* lue = |
| 1302 |
(lhs->field_reference_expression() != NULL |
| 1303 |
? lhs->field_reference_expression()->expr()->unary_expression() |
| 1304 |
: lhs->unary_expression()); |
| 1305 |
Var_expression* lve = |
| 1306 |
(lue != NULL && lue->op() == OPERATOR_MULT ? lue->operand()->var_expression() : NULL); |
| 1307 |
Array_index_expression* raie = rhs->array_index_expression(); |
| 1308 |
String_index_expression* rsie = rhs->string_index_expression(); |
| 1309 |
Expression* rarray = |
| 1310 |
(raie != NULL && raie->end() != NULL && raie->array()->type()->is_slice_type() |
| 1311 |
? raie->array() |
| 1312 |
: (rsie != NULL && rsie->type()->is_string_type() ? rsie->string() : NULL)); |
| 1313 |
Unary_expression* rue = |
| 1314 |
(rarray != NULL && rarray->field_reference_expression() != NULL |
| 1315 |
? rarray->field_reference_expression()->expr()->unary_expression() |
| 1316 |
: (rarray != NULL ? rarray->unary_expression() : NULL)); |
| 1317 |
Var_expression* rve = |
| 1318 |
(rue != NULL && rue->op() == OPERATOR_MULT ? rue->operand()->var_expression() : NULL); |
| 1319 |
return lve != NULL && rve != NULL |
| 1320 |
&& lve->named_object() == rve->named_object(); |
| 1321 |
} |
| 1322 |
|
| 1323 |
// Model statements within a function as assignments and flows between nodes. |
| 1324 |
|
| 1325 |
int |
| 1326 |
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 |
bool is_for_statement = (s->is_block_statement() |
| 1330 |
&& s->block_statement()->is_lowered_for_statement()); |
| 1331 |
if (is_for_statement) |
| 1332 |
this->context_->increase_loop_depth(); |
| 1333 |
|
| 1334 |
s->traverse_contents(this); |
| 1335 |
|
| 1336 |
if (is_for_statement) |
| 1337 |
this->context_->decrease_loop_depth(); |
| 1338 |
|
| 1339 |
Gogo* gogo = this->context_->gogo(); |
| 1340 |
int debug_level = gogo->debug_escape_level(); |
| 1341 |
if (debug_level > 1 |
| 1342 |
&& s->unnamed_label_statement() == NULL |
| 1343 |
&& s->expression_statement() == NULL |
| 1344 |
&& !s->is_block_statement()) |
| 1345 |
{ |
| 1346 |
Node* n = Node::make_node(s); |
| 1347 |
std::string fn_name = this->context_->current_function_name(); |
| 1348 |
go_debug(s->location(), "[%d] %s esc: %s", |
| 1349 |
this->context_->loop_depth(), fn_name.c_str(), |
| 1350 |
n->ast_format(gogo).c_str()); |
| 1351 |
} |
| 1352 |
|
| 1353 |
switch (s->classification()) |
| 1354 |
{ |
| 1355 |
case Statement::STATEMENT_VARIABLE_DECLARATION: |
| 1356 |
{ |
| 1357 |
Named_object* var = s->variable_declaration_statement()->var(); |
| 1358 |
Node* var_node = Node::make_node(var); |
| 1359 |
Node::Escape_state* state = var_node->state(this->context_, NULL); |
| 1360 |
state->loop_depth = this->context_->loop_depth(); |
| 1361 |
|
| 1362 |
// Set the loop depth for this declaration. |
| 1363 |
if (var->is_variable() |
| 1364 |
&& var->var_value()->init() != NULL) |
| 1365 |
{ |
| 1366 |
Node* init_node = Node::make_node(var->var_value()->init()); |
| 1367 |
this->assign(var_node, init_node); |
| 1368 |
} |
| 1369 |
} |
| 1370 |
break; |
| 1371 |
|
| 1372 |
case Statement::STATEMENT_TEMPORARY: |
| 1373 |
{ |
| 1374 |
Expression* init = s->temporary_statement()->init(); |
| 1375 |
if (init != NULL) |
| 1376 |
{ |
| 1377 |
Node* n = Node::make_node(init); |
| 1378 |
if (s->temporary_statement()->value_escapes()) |
| 1379 |
this->assign(this->context_->sink(), n); |
| 1380 |
else |
| 1381 |
this->assign(Node::make_node(s), n); |
| 1382 |
} |
| 1383 |
} |
| 1384 |
break; |
| 1385 |
|
| 1386 |
case Statement::STATEMENT_LABEL: |
| 1387 |
{ |
| 1388 |
Label_statement* label_stmt = s->label_statement(); |
| 1389 |
if (label_stmt->label()->looping()) |
| 1390 |
this->context_->increase_loop_depth(); |
| 1391 |
|
| 1392 |
if (debug_level > 1) |
| 1393 |
{ |
| 1394 |
std::string label_type = (label_stmt->label()->looping() |
| 1395 |
? "looping" |
| 1396 |
: "nonlooping"); |
| 1397 |
go_inform(s->location(), "%s %s label", |
| 1398 |
label_stmt->label()->name().c_str(), |
| 1399 |
label_type.c_str()); |
| 1400 |
} |
| 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 |
case Statement::STATEMENT_ASSIGNMENT: |
| 1412 |
{ |
| 1413 |
Assignment_statement* assn = s->assignment_statement(); |
| 1414 |
Expression* lhs = assn->lhs(); |
| 1415 |
Expression* rhs = assn->rhs(); |
| 1416 |
Node* lhs_node = Node::make_node(lhs); |
| 1417 |
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 |
if (is_self_assignment(lhs, rhs)) |
| 1430 |
{ |
| 1431 |
if (debug_level != 0) |
| 1432 |
go_inform(s->location(), "%s ignoring self-assignment to %s", |
| 1433 |
strip_packed_prefix(gogo, this->context_->current_function_name()).c_str(), |
| 1434 |
lhs_node->ast_format(gogo).c_str()); |
| 1435 |
break; |
| 1436 |
} |
| 1437 |
|
| 1438 |
this->assign(lhs_node, rhs_node); |
| 1439 |
} |
| 1440 |
break; |
| 1441 |
|
| 1442 |
case Statement::STATEMENT_SEND: |
| 1443 |
{ |
| 1444 |
Node* sent_node = Node::make_node(s->send_statement()->val()); |
| 1445 |
this->assign(this->context_->sink(), sent_node); |
| 1446 |
} |
| 1447 |
break; |
| 1448 |
|
| 1449 |
case Statement::STATEMENT_DEFER: |
| 1450 |
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 |
Node* n = Node::make_node(s); |
| 1456 |
n->set_encoding(Node::ESCAPE_NONE); |
| 1457 |
break; |
| 1458 |
} |
| 1459 |
// fallthrough |
| 1460 |
|
| 1461 |
case Statement::STATEMENT_GO: |
| 1462 |
{ |
| 1463 |
// Defer f(x) or go f(x). |
| 1464 |
// Both f and x escape to the heap. |
| 1465 |
Thunk_statement* thunk = s->thunk_statement(); |
| 1466 |
if (thunk->call()->call_expression() == NULL) |
| 1467 |
break; |
| 1468 |
|
| 1469 |
Call_expression* call = thunk->call()->call_expression(); |
| 1470 |
Node* func_node = Node::make_node(call->fn()); |
| 1471 |
this->assign(this->context_->sink(), func_node); |
| 1472 |
if (call->args() != NULL) |
| 1473 |
{ |
| 1474 |
for (Expression_list::const_iterator p = call->args()->begin(); |
| 1475 |
p != call->args()->end(); |
| 1476 |
++p) |
| 1477 |
{ |
| 1478 |
Node* arg_node = Node::make_node(*p); |
| 1479 |
this->assign(this->context_->sink(), arg_node); |
| 1480 |
} |
| 1481 |
} |
| 1482 |
} |
| 1483 |
break; |
| 1484 |
|
| 1485 |
default: |
| 1486 |
break; |
| 1487 |
} |
| 1488 |
return TRAVERSE_SKIP_COMPONENTS; |
| 1489 |
} |
| 1490 |
|
| 1491 |
// Helper function to emit moved-to-heap diagnostics. |
| 1492 |
|
| 1493 |
static void |
| 1494 |
move_to_heap(Gogo* gogo, Expression *expr) |
| 1495 |
{ |
| 1496 |
Named_object* no; |
| 1497 |
if (expr->var_expression() != NULL) |
| 1498 |
no = expr->var_expression()->named_object(); |
| 1499 |
else if (expr->enclosed_var_expression() != NULL) |
| 1500 |
no = expr->enclosed_var_expression()->variable(); |
| 1501 |
else |
| 1502 |
return; |
| 1503 |
|
| 1504 |
if ((no->is_variable() |
| 1505 |
&& !no->var_value()->is_global()) |
| 1506 |
|| no->is_result_variable()) |
| 1507 |
{ |
| 1508 |
Node* n = Node::make_node(expr); |
| 1509 |
if (gogo->debug_escape_level() != 0) |
| 1510 |
go_debug(n->definition_location(), |
| 1511 |
"moved to heap: %s", |
| 1512 |
n->ast_format(gogo).c_str()); |
| 1513 |
if (gogo->compiling_runtime() && gogo->package_name() == "runtime") |
| 1514 |
go_error_at(expr->location(), |
| 1515 |
"%s escapes to heap, not allowed in runtime", |
| 1516 |
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 |
Escape_analysis_assign::expression(Expression** pexpr) |
| 1524 |
{ |
| 1525 |
Gogo* gogo = this->context_->gogo(); |
| 1526 |
int debug_level = gogo->debug_escape_level(); |
| 1527 |
|
| 1528 |
// Big stuff escapes unconditionally. |
| 1529 |
Node* n = Node::make_node(*pexpr); |
| 1530 |
if ((n->encoding() & ESCAPE_MASK) != int(Node::ESCAPE_HEAP) |
| 1531 |
&& n->is_big(this->context_)) |
| 1532 |
{ |
| 1533 |
if (debug_level > 1) |
| 1534 |
go_debug((*pexpr)->location(), "%s too large for stack", |
| 1535 |
n->ast_format(gogo).c_str()); |
| 1536 |
move_to_heap(gogo, *pexpr); |
| 1537 |
n->set_encoding(Node::ESCAPE_HEAP); |
| 1538 |
(*pexpr)->address_taken(true); |
| 1539 |
this->assign(this->context_->sink(), n); |
| 1540 |
} |
| 1541 |
|
| 1542 |
if ((*pexpr)->func_expression() == NULL) |
| 1543 |
(*pexpr)->traverse_subexpressions(this); |
| 1544 |
|
| 1545 |
if (debug_level > 1) |
| 1546 |
{ |
| 1547 |
std::string fn_name = this->context_->current_function_name(); |
| 1548 |
go_debug((*pexpr)->location(), "[%d] %s esc: %s", |
| 1549 |
this->context_->loop_depth(), fn_name.c_str(), |
| 1550 |
n->ast_format(gogo).c_str()); |
| 1551 |
} |
| 1552 |
|
| 1553 |
switch ((*pexpr)->classification()) |
| 1554 |
{ |
| 1555 |
case Expression::EXPRESSION_CALL: |
| 1556 |
{ |
| 1557 |
Call_expression* call = (*pexpr)->call_expression(); |
| 1558 |
if (call->is_builtin()) |
| 1559 |
{ |
| 1560 |
Builtin_call_expression* bce = call->builtin_call_expression(); |
| 1561 |
switch (bce->code()) |
| 1562 |
{ |
| 1563 |
case Builtin_call_expression::BUILTIN_PANIC: |
| 1564 |
{ |
| 1565 |
// Argument could leak through recover. |
| 1566 |
Node* panic_arg = Node::make_node(call->args()->front()); |
| 1567 |
this->assign(this->context_->sink(), panic_arg); |
| 1568 |
} |
| 1569 |
break; |
| 1570 |
|
| 1571 |
case Builtin_call_expression::BUILTIN_APPEND: |
| 1572 |
{ |
| 1573 |
// The contents being appended leak. |
| 1574 |
if (call->is_varargs()) |
| 1575 |
{ |
| 1576 |
// append(slice1, slice2...) -- slice2 itself does not escape, but contents do |
| 1577 |
Node* appended = Node::make_node(call->args()->back()); |
| 1578 |
this->assign_deref(this->context_->sink(), appended); |
| 1579 |
if (debug_level > 2) |
| 1580 |
go_debug((*pexpr)->location(), |
| 1581 |
"special treatment of append(slice1, slice2...)"); |
| 1582 |
} |
| 1583 |
else |
| 1584 |
{ |
| 1585 |
for (Expression_list::const_iterator pa = |
| 1586 |
call->args()->begin() + 1; |
| 1587 |
pa != call->args()->end(); |
| 1588 |
++pa) |
| 1589 |
{ |
| 1590 |
Node* arg = Node::make_node(*pa); |
| 1591 |
this->assign(this->context_->sink(), arg); |
| 1592 |
} |
| 1593 |
} |
| 1594 |
|
| 1595 |
// The content of the original slice leaks as well. |
| 1596 |
Node* appendee = Node::make_node(call->args()->front()); |
| 1597 |
this->assign_deref(this->context_->sink(), appendee); |
| 1598 |
} |
| 1599 |
break; |
| 1600 |
|
| 1601 |
case Builtin_call_expression::BUILTIN_COPY: |
| 1602 |
{ |
| 1603 |
// Lose track of the copied content. |
| 1604 |
Node* copied = Node::make_node(call->args()->back()); |
| 1605 |
this->assign_deref(this->context_->sink(), copied); |
| 1606 |
} |
| 1607 |
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 |
case Builtin_call_expression::BUILTIN_MAKE: |
| 1631 |
case Builtin_call_expression::BUILTIN_NEW: |
| 1632 |
// should have been lowered to runtime calls at this point. |
| 1633 |
// fallthrough |
| 1634 |
default: |
| 1635 |
go_unreachable(); |
| 1636 |
} |
| 1637 |
break; |
| 1638 |
} |
| 1639 |
Func_expression* fe = call->fn()->func_expression(); |
| 1640 |
if (fe != NULL && fe->is_runtime_function()) |
| 1641 |
{ |
| 1642 |
switch (fe->runtime_code()) |
| 1643 |
{ |
| 1644 |
case Runtime::MAKECHAN: |
| 1645 |
case Runtime::MAKECHAN64: |
| 1646 |
case Runtime::MAKEMAP: |
| 1647 |
case Runtime::MAKEMAP64: |
| 1648 |
case Runtime::MAKESLICE: |
| 1649 |
case Runtime::MAKESLICE64: |
| 1650 |
this->context_->track(n); |
| 1651 |
break; |
| 1652 |
|
| 1653 |
case Runtime::MAPASSIGN: |
| 1654 |
{ |
| 1655 |
// Map key escapes. The last argument is the address |
| 1656 |
// of the key. |
| 1657 |
Node* key_node = Node::make_node(call->args()->back()); |
| 1658 |
this->assign_deref(this->context_->sink(), key_node); |
| 1659 |
} |
| 1660 |
break; |
| 1661 |
|
| 1662 |
case Runtime::MAPASSIGN_FAST32PTR: |
| 1663 |
case Runtime::MAPASSIGN_FAST64PTR: |
| 1664 |
case Runtime::MAPASSIGN_FASTSTR: |
| 1665 |
{ |
| 1666 |
// Map key escapes. The last argument is the key. |
| 1667 |
Node* key_node = Node::make_node(call->args()->back()); |
| 1668 |
this->assign(this->context_->sink(), key_node); |
| 1669 |
} |
| 1670 |
break; |
| 1671 |
|
| 1672 |
case Runtime::IFACEE2T2: |
| 1673 |
case Runtime::IFACEI2T2: |
| 1674 |
{ |
| 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 |
Node* src_node = Node::make_node(call->args()->at(1)); |
| 1682 |
Node* dst_node; |
| 1683 |
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 |
Unary_expression* ue = |
| 1691 |
(arg2->conversion_expression() != NULL |
| 1692 |
? arg2->conversion_expression()->expr()->unary_expression() |
| 1693 |
: arg2->unary_expression()); |
| 1694 |
if (ue != NULL && ue->op() == OPERATOR_AND) |
| 1695 |
{ |
| 1696 |
if (!ue->operand()->type()->has_pointer()) |
| 1697 |
// Don't bother flowing non-pointer. |
| 1698 |
break; |
| 1699 |
dst_node = Node::make_node(ue->operand()); |
| 1700 |
} |
| 1701 |
else |
| 1702 |
dst_node = this->context_->add_dereference(Node::make_node(arg2)); |
| 1703 |
this->assign(dst_node, src_node); |
| 1704 |
} |
| 1705 |
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 |
default: |
| 1750 |
// should not see other runtime calls. they are not yet |
| 1751 |
// lowered to runtime calls at this point. |
| 1752 |
go_unreachable(); |
| 1753 |
} |
| 1754 |
} |
| 1755 |
else |
| 1756 |
this->call(call); |
| 1757 |
} |
| 1758 |
break; |
| 1759 |
|
| 1760 |
case Expression::EXPRESSION_ALLOCATION: |
| 1761 |
// This is Runtime::NEW. |
| 1762 |
this->context_->track(n); |
| 1763 |
break; |
| 1764 |
|
| 1765 |
case Expression::EXPRESSION_STRING_CONCAT: |
| 1766 |
this->context_->track(n); |
| 1767 |
break; |
| 1768 |
|
| 1769 |
case Expression::EXPRESSION_CONVERSION: |
| 1770 |
{ |
| 1771 |
Type_conversion_expression* tce = (*pexpr)->conversion_expression(); |
| 1772 |
Type* ft = tce->expr()->type(); |
| 1773 |
Type* tt = tce->type(); |
| 1774 |
if ((ft->is_string_type() && tt->is_slice_type()) |
| 1775 |
|| (ft->is_slice_type() && tt->is_string_type()) |
| 1776 |
|| (ft->integer_type() != NULL && tt->is_string_type())) |
| 1777 |
{ |
| 1778 |
// string([]byte), string([]rune), []byte(string), []rune(string), string(rune) |
| 1779 |
this->context_->track(n); |
| 1780 |
break; |
| 1781 |
} |
| 1782 |
Node* tce_node = Node::make_node(tce); |
| 1783 |
Node* converted = Node::make_node(tce->expr()); |
| 1784 |
this->context_->track(tce_node); |
| 1785 |
|
| 1786 |
this->assign(tce_node, converted); |
| 1787 |
} |
| 1788 |
break; |
| 1789 |
|
| 1790 |
case Expression::EXPRESSION_UNSAFE_CONVERSION: |
| 1791 |
{ |
| 1792 |
Unsafe_type_conversion_expression* uce = |
| 1793 |
(*pexpr)->unsafe_conversion_expression(); |
| 1794 |
Node* expr_node = Node::make_node(uce->expr()); |
| 1795 |
this->assign(n, expr_node); |
| 1796 |
} |
| 1797 |
break; |
| 1798 |
|
| 1799 |
case Expression::EXPRESSION_FIXED_ARRAY_CONSTRUCTION: |
| 1800 |
case Expression::EXPRESSION_SLICE_CONSTRUCTION: |
| 1801 |
{ |
| 1802 |
Node* array_node = Node::make_node(*pexpr); |
| 1803 |
if ((*pexpr)->slice_literal() != NULL) |
| 1804 |
this->context_->track(array_node); |
| 1805 |
|
| 1806 |
Expression_list* vals = ((*pexpr)->slice_literal() != NULL |
| 1807 |
? (*pexpr)->slice_literal()->vals() |
| 1808 |
: (*pexpr)->array_literal()->vals()); |
| 1809 |
|
| 1810 |
if (vals != NULL) |
| 1811 |
{ |
| 1812 |
// Connect the array to its values. |
| 1813 |
for (Expression_list::const_iterator p = vals->begin(); |
| 1814 |
p != vals->end(); |
| 1815 |
++p) |
| 1816 |
if ((*p) != NULL) |
| 1817 |
this->assign(array_node, Node::make_node(*p)); |
| 1818 |
} |
| 1819 |
} |
| 1820 |
break; |
| 1821 |
|
| 1822 |
case Expression::EXPRESSION_STRUCT_CONSTRUCTION: |
| 1823 |
{ |
| 1824 |
Node* struct_node = Node::make_node(*pexpr); |
| 1825 |
Expression_list* vals = (*pexpr)->struct_literal()->vals(); |
| 1826 |
if (vals != NULL) |
| 1827 |
{ |
| 1828 |
// Connect the struct to its values. |
| 1829 |
for (Expression_list::const_iterator p = vals->begin(); |
| 1830 |
p != vals->end(); |
| 1831 |
++p) |
| 1832 |
{ |
| 1833 |
if ((*p) != NULL) |
| 1834 |
this->assign(struct_node, Node::make_node(*p)); |
| 1835 |
} |
| 1836 |
} |
| 1837 |
} |
| 1838 |
break; |
| 1839 |
|
| 1840 |
case Expression::EXPRESSION_SLICE_VALUE: |
| 1841 |
{ |
| 1842 |
// Connect the pointer field to the slice value. |
| 1843 |
Node* slice_node = Node::make_node(*pexpr); |
| 1844 |
Node* ptr_node = |
| 1845 |
Node::make_node((*pexpr)->slice_value_expression()->valmem()); |
| 1846 |
this->assign(slice_node, ptr_node); |
| 1847 |
} |
| 1848 |
break; |
| 1849 |
|
| 1850 |
case Expression::EXPRESSION_HEAP: |
| 1851 |
{ |
| 1852 |
Node* pointer_node = Node::make_node(*pexpr); |
| 1853 |
Node* lit_node = Node::make_node((*pexpr)->heap_expression()->expr()); |
| 1854 |
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 |
this->assign(pointer_node, lit_node); |
| 1859 |
} |
| 1860 |
break; |
| 1861 |
|
| 1862 |
case Expression::EXPRESSION_BOUND_METHOD: |
| 1863 |
{ |
| 1864 |
Node* bound_node = Node::make_node(*pexpr); |
| 1865 |
this->context_->track(bound_node); |
| 1866 |
|
| 1867 |
Expression* obj = (*pexpr)->bound_method_expression()->first_argument(); |
| 1868 |
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 |
this->assign(this->context_->sink(), obj_node); |
| 1873 |
} |
| 1874 |
break; |
| 1875 |
|
| 1876 |
case Expression::EXPRESSION_MAP_CONSTRUCTION: |
| 1877 |
{ |
| 1878 |
Map_construction_expression* mce = (*pexpr)->map_literal(); |
| 1879 |
Node* map_node = Node::make_node(mce); |
| 1880 |
this->context_->track(map_node); |
| 1881 |
|
| 1882 |
// All keys and values escape to memory. |
| 1883 |
if (mce->vals() != NULL) |
| 1884 |
{ |
| 1885 |
for (Expression_list::const_iterator p = mce->vals()->begin(); |
| 1886 |
p != mce->vals()->end(); |
| 1887 |
++p) |
| 1888 |
{ |
| 1889 |
if ((*p) != NULL) |
| 1890 |
this->assign(this->context_->sink(), Node::make_node(*p)); |
| 1891 |
} |
| 1892 |
} |
| 1893 |
} |
| 1894 |
break; |
| 1895 |
|
| 1896 |
case Expression::EXPRESSION_FUNC_REFERENCE: |
| 1897 |
{ |
| 1898 |
Func_expression* fe = (*pexpr)->func_expression(); |
| 1899 |
if (fe->closure() != NULL) |
| 1900 |
{ |
| 1901 |
// Connect captured variables to the closure. |
| 1902 |
Node* closure_node = Node::make_node(fe); |
| 1903 |
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 |
Heap_expression* he = fe->closure()->heap_expression(); |
| 1909 |
Struct_construction_expression* sce = he->expr()->struct_literal(); |
| 1910 |
|
| 1911 |
// First field is function code, other fields are variable |
| 1912 |
// references. |
| 1913 |
Expression_list::const_iterator p = sce->vals()->begin(); |
| 1914 |
++p; |
| 1915 |
for (; p != sce->vals()->end(); ++p) |
| 1916 |
{ |
| 1917 |
Node* enclosed_node = Node::make_node(*p); |
| 1918 |
this->context_->track(enclosed_node); |
| 1919 |
this->assign(closure_node, enclosed_node); |
| 1920 |
} |
| 1921 |
} |
| 1922 |
} |
| 1923 |
break; |
| 1924 |
|
| 1925 |
case Expression::EXPRESSION_UNARY: |
| 1926 |
{ |
| 1927 |
Expression* operand = (*pexpr)->unary_expression()->operand(); |
| 1928 |
|
| 1929 |
if ((*pexpr)->unary_expression()->op() == OPERATOR_AND) |
| 1930 |
{ |
| 1931 |
this->context_->track(n); |
| 1932 |
|
| 1933 |
Named_object* var = NULL; |
| 1934 |
if (operand->var_expression() != NULL) |
| 1935 |
var = operand->var_expression()->named_object(); |
| 1936 |
else if (operand->enclosed_var_expression() != NULL) |
| 1937 |
var = operand->enclosed_var_expression()->variable(); |
| 1938 |
|
| 1939 |
if (var != NULL |
| 1940 |
&& ((var->is_variable() && var->var_value()->is_parameter()) |
| 1941 |
|| var->is_result_variable())) |
| 1942 |
{ |
| 1943 |
Node::Escape_state* addr_state = n->state(this->context_, NULL); |
| 1944 |
addr_state->loop_depth = 1; |
| 1945 |
break; |
| 1946 |
} |
| 1947 |
} |
| 1948 |
|
| 1949 |
if ((*pexpr)->unary_expression()->op() != OPERATOR_AND |
| 1950 |
&& (*pexpr)->unary_expression()->op() != OPERATOR_MULT) |
| 1951 |
break; |
| 1952 |
|
| 1953 |
// For &x and *x, use the loop depth of x if known. |
| 1954 |
Node::Escape_state* expr_state = n->state(this->context_, NULL); |
| 1955 |
Node* operand_node = Node::make_node(operand); |
| 1956 |
Node::Escape_state* operand_state = operand_node->state(this->context_, NULL); |
| 1957 |
if (operand_state->loop_depth != 0) |
| 1958 |
expr_state->loop_depth = operand_state->loop_depth; |
| 1959 |
} |
| 1960 |
break; |
| 1961 |
|
| 1962 |
case Expression::EXPRESSION_ARRAY_INDEX: |
| 1963 |
{ |
| 1964 |
Array_index_expression* aie = (*pexpr)->array_index_expression(); |
| 1965 |
|
| 1966 |
// Propagate the loopdepth to element. |
| 1967 |
Node* array_node = Node::make_node(aie->array()); |
| 1968 |
Node::Escape_state* elem_state = n->state(this->context_, NULL); |
| 1969 |
Node::Escape_state* array_state = array_node->state(this->context_, NULL); |
| 1970 |
elem_state->loop_depth = array_state->loop_depth; |
| 1971 |
|
| 1972 |
if (aie->end() != NULL && !aie->array()->type()->is_slice_type()) |
| 1973 |
{ |
| 1974 |
// Slicing an array. This effectively takes the address of the array. |
| 1975 |
Expression* addr = Expression::make_unary(OPERATOR_AND, aie->array(), |
| 1976 |
aie->location()); |
| 1977 |
Node* addr_node = Node::make_node(addr); |
| 1978 |
n->set_child(addr_node); |
| 1979 |
this->context_->track(addr_node); |
| 1980 |
|
| 1981 |
Node::Escape_state* addr_state = addr_node->state(this->context_, NULL); |
| 1982 |
if (array_state->loop_depth != 0) |
| 1983 |
addr_state->loop_depth = array_state->loop_depth; |
| 1984 |
} |
| 1985 |
} |
| 1986 |
break; |
| 1987 |
|
| 1988 |
case Expression::EXPRESSION_FIELD_REFERENCE: |
| 1989 |
{ |
| 1990 |
// Propagate the loopdepth to field. |
| 1991 |
Node* struct_node = |
| 1992 |
Node::make_node((*pexpr)->field_reference_expression()->expr()); |
| 1993 |
Node::Escape_state* field_state = n->state(this->context_, NULL); |
| 1994 |
Node::Escape_state* struct_state = struct_node->state(this->context_, NULL); |
| 1995 |
field_state->loop_depth = struct_state->loop_depth; |
| 1996 |
} |
| 1997 |
break; |
| 1998 |
|
| 1999 |
default: |
| 2000 |
break; |
| 2001 |
} |
| 2002 |
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 |
Escape_analysis_assign::call(Call_expression* call) |
| 2010 |
{ |
| 2011 |
Gogo* gogo = this->context_->gogo(); |
| 2012 |
int debug_level = gogo->debug_escape_level(); |
| 2013 |
|
| 2014 |
Func_expression* fn = call->fn()->func_expression(); |
| 2015 |
Function_type* fntype = call->get_function_type(); |
| 2016 |
bool indirect = false; |
| 2017 |
|
| 2018 |
// Interface method calls or closure calls are indirect calls. |
| 2019 |
if (fntype == NULL |
| 2020 |
|| (fntype->is_method() |
| 2021 |
&& fntype->receiver()->type()->interface_type() != NULL) |
| 2022 |
|| fn == NULL |
| 2023 |
|| (fn->named_object()->is_function() |
| 2024 |
&& fn->named_object()->func_value()->enclosing() != NULL)) |
| 2025 |
indirect = true; |
| 2026 |
|
| 2027 |
Node* call_node = Node::make_node(call); |
| 2028 |
std::vector<Node*> arg_nodes; |
| 2029 |
if (call->fn()->interface_field_reference_expression() != NULL) |
| 2030 |
{ |
| 2031 |
Interface_field_reference_expression* ifre = |
| 2032 |
call->fn()->interface_field_reference_expression(); |
| 2033 |
Node* field_node = Node::make_node(ifre->expr()); |
| 2034 |
arg_nodes.push_back(field_node); |
| 2035 |
} |
| 2036 |
|
| 2037 |
if (call->args() != NULL) |
| 2038 |
{ |
| 2039 |
for (Expression_list::const_iterator p = call->args()->begin(); |
| 2040 |
p != call->args()->end(); |
| 2041 |
++p) |
| 2042 |
arg_nodes.push_back(Node::make_node(*p)); |
| 2043 |
} |
| 2044 |
|
| 2045 |
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 |
for (std::vector<Node*>::iterator p = arg_nodes.begin(); |
| 2050 |
p != arg_nodes.end(); |
| 2051 |
++p) |
| 2052 |
{ |
| 2053 |
if (debug_level > 2) |
| 2054 |
go_debug(call->location(), |
| 2055 |
"esccall:: indirect call <- %s, untracked", |
| 2056 |
(*p)->ast_format(gogo).c_str()); |
| 2057 |
this->assign(this->context_->sink(), *p); |
| 2058 |
} |
| 2059 |
|
| 2060 |
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 |
Node* fn_node = Node::make_node(call->fn()); |
| 2066 |
std::vector<Node*> retvals = call_node->state(this->context_, NULL)->retvals; |
| 2067 |
for (std::vector<Node*>::const_iterator p = retvals.begin(); |
| 2068 |
p != retvals.end(); |
| 2069 |
++p) |
| 2070 |
this->assign_deref(*p, fn_node); |
| 2071 |
|
| 2072 |
return; |
| 2073 |
} |
| 2074 |
|
| 2075 |
// If FN is an untagged function. |
| 2076 |
if (fn != NULL |
| 2077 |
&& fn->named_object()->is_function() |
| 2078 |
&& !fntype->is_tagged()) |
| 2079 |
{ |
| 2080 |
if (debug_level > 2) |
| 2081 |
go_debug(call->location(), "esccall:: %s in recursive group", |
| 2082 |
call_node->ast_format(gogo).c_str()); |
| 2083 |
|
| 2084 |
Function* f = fn->named_object()->func_value(); |
| 2085 |
const Bindings* callee_bindings = f->block()->bindings(); |
| 2086 |
Function::Results* results = f->result_variables(); |
| 2087 |
if (results != NULL) |
| 2088 |
{ |
| 2089 |
// Setup output list on this call node. |
| 2090 |
Node::Escape_state* state = call_node->state(this->context_, NULL); |
| 2091 |
for (Function::Results::const_iterator p1 = results->begin(); |
| 2092 |
p1 != results->end(); |
| 2093 |
++p1) |
| 2094 |
{ |
| 2095 |
Node* result_node = Node::make_node(*p1); |
| 2096 |
state->retvals.push_back(result_node); |
| 2097 |
} |
| 2098 |
} |
| 2099 |
|
| 2100 |
std::vector<Node*>::iterator p = arg_nodes.begin(); |
| 2101 |
if (fntype->is_method()) |
| 2102 |
{ |
| 2103 |
std::string rcvr_name = fntype->receiver()->name(); |
| 2104 |
if (rcvr_name.empty() || Gogo::is_sink_name(rcvr_name) |
| 2105 |
|| !fntype->receiver()->type()->has_pointer()) |
| 2106 |
; |
| 2107 |
else |
| 2108 |
{ |
| 2109 |
Named_object* rcvr_no = |
| 2110 |
callee_bindings->lookup_local(fntype->receiver()->name()); |
| 2111 |
go_assert(rcvr_no != NULL); |
| 2112 |
Node* rcvr_node = Node::make_node(rcvr_no); |
| 2113 |
if (fntype->receiver()->type()->points_to() == NULL |
| 2114 |
&& (*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 |
this->assign_deref(rcvr_node, *p); |
| 2122 |
else |
| 2123 |
this->assign(rcvr_node, *p); |
| 2124 |
} |
| 2125 |
++p; |
| 2126 |
} |
| 2127 |
|
| 2128 |
const Typed_identifier_list* til = fntype->parameters(); |
| 2129 |
if (til != NULL) |
| 2130 |
{ |
| 2131 |
for (Typed_identifier_list::const_iterator p1 = til->begin(); |
| 2132 |
p1 != til->end(); |
| 2133 |
++p1, ++p) |
| 2134 |
{ |
| 2135 |
if (p1->name().empty() || Gogo::is_sink_name(p1->name())) |
| 2136 |
continue; |
| 2137 |
|
| 2138 |
Named_object* param_no = |
| 2139 |
callee_bindings->lookup_local(p1->name()); |
| 2140 |
go_assert(param_no != NULL); |
| 2141 |
Expression* arg = (*p)->expr(); |
| 2142 |
if (arg->var_expression() != NULL |
| 2143 |
&& arg->var_expression()->named_object() == param_no) |
| 2144 |
continue; |
| 2145 |
|
| 2146 |
Node* param_node = Node::make_node(param_no); |
| 2147 |
this->assign(param_node, *p); |
| 2148 |
} |
| 2149 |
|
| 2150 |
for (; p != arg_nodes.end(); ++p) |
| 2151 |
{ |
| 2152 |
if (debug_level > 2) |
| 2153 |
go_debug(call->location(), "esccall:: ... <- %s, untracked", |
| 2154 |
(*p)->ast_format(gogo).c_str()); |
| 2155 |
this->assign(this->context_->sink(), *p); |
| 2156 |
} |
| 2157 |
} |
| 2158 |
|
| 2159 |
return; |
| 2160 |
} |
| 2161 |
|
| 2162 |
if (debug_level > 2) |
| 2163 |
go_debug(call->location(), "esccall:: %s not recursive", |
| 2164 |
call_node->ast_format(gogo).c_str()); |
| 2165 |
|
| 2166 |
Node::Escape_state* call_state = call_node->state(this->context_, NULL); |
| 2167 |
if (!call_state->retvals.empty()) |
| 2168 |
go_error_at(Linemap::unknown_location(), |
| 2169 |
"esc already decorated call %s", |
| 2170 |
call_node->ast_format(gogo).c_str()); |
| 2171 |
this->context_->init_retvals(call_node, fntype); |
| 2172 |
|
| 2173 |
// Receiver. |
| 2174 |
std::vector<Node*>::iterator p = arg_nodes.begin(); |
| 2175 |
if (fntype->is_method() |
| 2176 |
&& p != arg_nodes.end()) |
| 2177 |
{ |
| 2178 |
// First argument to call will be the receiver. |
| 2179 |
std::string* note = fntype->receiver()->note(); |
| 2180 |
if (fntype->receiver()->type()->points_to() == NULL |
| 2181 |
&& (*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 |
this->assign_from_note(note, call_state->retvals, |
| 2189 |
this->context_->add_dereference(*p)); |
| 2190 |
else |
| 2191 |
{ |
| 2192 |
if (!Type::are_identical(fntype->receiver()->type(), |
| 2193 |
(*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 |
this->context_->track(*p); |
| 2199 |
} |
| 2200 |
this->assign_from_note(note, call_state->retvals, *p); |
| 2201 |
} |
| 2202 |
p++; |
| 2203 |
} |
| 2204 |
|
| 2205 |
const Typed_identifier_list* til = fntype->parameters(); |
| 2206 |
if (til != NULL) |
| 2207 |
{ |
| 2208 |
for (Typed_identifier_list::const_iterator pn = til->begin(); |
| 2209 |
pn != til->end() && p != arg_nodes.end(); |
| 2210 |
++pn, ++p) |
| 2211 |
{ |
| 2212 |
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 |
this->context_->track(*p); |
| 2218 |
} |
| 2219 |
|
| 2220 |
Type* t = pn->type(); |
| 2221 |
if (t != NULL |
| 2222 |
&& t->has_pointer()) |
| 2223 |
{ |
| 2224 |
std::string* note = pn->note(); |
| 2225 |
int enc = this->assign_from_note(note, call_state->retvals, *p); |
| 2226 |
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 |
for (; p != arg_nodes.end(); ++p) |
| 2238 |
{ |
| 2239 |
if (debug_level > 2) |
| 2240 |
go_debug(call->location(), "esccall:: ... <- %s, untracked", |
| 2241 |
(*p)->ast_format(gogo).c_str()); |
| 2242 |
this->assign(this->context_->sink(), *p); |
| 2243 |
} |
| 2244 |
} |
| 2245 |
} |
| 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 |
Escape_analysis_assign::assign(Node* dst, Node* src) |
| 2255 |
{ |
| 2256 |
Gogo* gogo = this->context_->gogo(); |
| 2257 |
int debug_level = gogo->debug_escape_level(); |
| 2258 |
if (debug_level > 1) |
| 2259 |
go_debug(dst->location(), "[%d] %s escassign: %s(%s)[%s] = %s(%s)[%s]", |
| 2260 |
this->context_->loop_depth(), |
| 2261 |
strip_packed_prefix(gogo, this->context_->current_function_name()).c_str(), |
| 2262 |
dst->ast_format(gogo).c_str(), dst->details().c_str(), |
| 2263 |
dst->op_format().c_str(), |
| 2264 |
src->ast_format(gogo).c_str(), src->details().c_str(), |
| 2265 |
src->op_format().c_str()); |
| 2266 |
|
| 2267 |
if (dst->is_indirect()) |
| 2268 |
// Lose track of the dereference. |
| 2269 |
dst = this->context_->sink(); |
| 2270 |
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 |
Expression* e = dst->expr(); |
| 2275 |
switch (e->classification()) |
| 2276 |
{ |
| 2277 |
case Expression::EXPRESSION_VAR_REFERENCE: |
| 2278 |
{ |
| 2279 |
// If DST is a global variable, we have no way to track it. |
| 2280 |
Named_object* var = e->var_expression()->named_object(); |
| 2281 |
if (var->is_variable() && var->var_value()->is_global()) |
| 2282 |
dst = this->context_->sink(); |
| 2283 |
} |
| 2284 |
break; |
| 2285 |
|
| 2286 |
case Expression::EXPRESSION_FIELD_REFERENCE: |
| 2287 |
{ |
| 2288 |
Expression* strct = e->field_reference_expression()->expr(); |
| 2289 |
if (strct->heap_expression() != NULL) |
| 2290 |
{ |
| 2291 |
// When accessing the field of a struct reference, we lose |
| 2292 |
// track of the indirection. |
| 2293 |
dst = this->context_->sink(); |
| 2294 |
break; |
| 2295 |
} |
| 2296 |
|
| 2297 |
// Treat DST.x = SRC as if it were DST = SRC. |
| 2298 |
Node* struct_node = Node::make_node(strct); |
| 2299 |
this->assign(struct_node, src); |
| 2300 |
return; |
| 2301 |
} |
| 2302 |
|
| 2303 |
case Expression::EXPRESSION_ARRAY_INDEX: |
| 2304 |
{ |
| 2305 |
Array_index_expression* are = e->array_index_expression(); |
| 2306 |
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 |
Node* array_node = Node::make_node(are->array()); |
| 2311 |
this->assign(array_node, src); |
| 2312 |
return; |
| 2313 |
} |
| 2314 |
|
| 2315 |
// Lose track of the slice dereference. |
| 2316 |
dst = this->context_->sink(); |
| 2317 |
} |
| 2318 |
break; |
| 2319 |
|
| 2320 |
case Expression::EXPRESSION_UNARY: |
| 2321 |
// Lose track of the dereference. |
| 2322 |
if (e->unary_expression()->op() == OPERATOR_MULT) |
| 2323 |
dst = this->context_->sink(); |
| 2324 |
break; |
| 2325 |
|
| 2326 |
case Expression::EXPRESSION_MAP_INDEX: |
| 2327 |
{ |
| 2328 |
// Lose track of the map's key and value. |
| 2329 |
Expression* index = e->map_index_expression()->index(); |
| 2330 |
Node* index_node = Node::make_node(index); |
| 2331 |
this->assign(this->context_->sink(), index_node); |
| 2332 |
|
| 2333 |
dst = this->context_->sink(); |
| 2334 |
} |
| 2335 |
break; |
| 2336 |
|
| 2337 |
case Expression::EXPRESSION_TEMPORARY_REFERENCE: |
| 2338 |
{ |
| 2339 |
// Temporary is tracked through the underlying Temporary_statement. |
| 2340 |
Temporary_statement* t = |
| 2341 |
dst->expr()->temporary_reference_expression()->statement(); |
| 2342 |
if (t->value_escapes()) |
| 2343 |
dst = this->context_->sink(); |
| 2344 |
else |
| 2345 |
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 |
if (src->object() != NULL) |
| 2357 |
this->flows(dst, src); |
| 2358 |
else if (src->is_indirect()) |
| 2359 |
this->flows(dst, src); |
| 2360 |
else if (src->expr() != NULL) |
| 2361 |
{ |
| 2362 |
Expression* e = src->expr(); |
| 2363 |
switch (e->classification()) |
| 2364 |
{ |
| 2365 |
case Expression::EXPRESSION_VAR_REFERENCE: |
| 2366 |
case Expression::EXPRESSION_ENCLOSED_VAR_REFERENCE: |
| 2367 |
// DST = var |
| 2368 |
case Expression::EXPRESSION_HEAP: |
| 2369 |
// DST = &T{...}. |
| 2370 |
case Expression::EXPRESSION_FIXED_ARRAY_CONSTRUCTION: |
| 2371 |
case Expression::EXPRESSION_SLICE_CONSTRUCTION: |
| 2372 |
// DST = [...]T{...}. |
| 2373 |
case Expression::EXPRESSION_MAP_CONSTRUCTION: |
| 2374 |
// DST = map[T]V{...}. |
| 2375 |
case Expression::EXPRESSION_STRUCT_CONSTRUCTION: |
| 2376 |
// DST = T{...}. |
| 2377 |
case Expression::EXPRESSION_SLICE_VALUE: |
| 2378 |
// DST = slice{ptr, len, cap} |
| 2379 |
case Expression::EXPRESSION_ALLOCATION: |
| 2380 |
// DST = new(T). |
| 2381 |
case Expression::EXPRESSION_BOUND_METHOD: |
| 2382 |
// DST = x.M. |
| 2383 |
case Expression::EXPRESSION_STRING_CONCAT: |
| 2384 |
// DST = str1 + str2 |
| 2385 |
this->flows(dst, src); |
| 2386 |
break; |
| 2387 |
|
| 2388 |
case Expression::EXPRESSION_UNSAFE_CONVERSION: |
| 2389 |
{ |
| 2390 |
Expression* underlying = e->unsafe_conversion_expression()->expr(); |
| 2391 |
Node* underlying_node = Node::make_node(underlying); |
| 2392 |
this->assign(dst, underlying_node); |
| 2393 |
} |
| 2394 |
break; |
| 2395 |
|
| 2396 |
case Expression::EXPRESSION_SLICE_INFO: |
| 2397 |
{ |
| 2398 |
Slice_info_expression* sie = e->slice_info_expression(); |
| 2399 |
if (sie->info() == Expression::SLICE_INFO_VALUE_POINTER) |
| 2400 |
{ |
| 2401 |
Node* slice = Node::make_node(sie->slice()); |
| 2402 |
this->assign(dst, slice); |
| 2403 |
} |
| 2404 |
} |
| 2405 |
break; |
| 2406 |
|
| 2407 |
case Expression::EXPRESSION_CALL: |
| 2408 |
{ |
| 2409 |
Call_expression* call = e->call_expression(); |
| 2410 |
if (call->is_builtin()) |
| 2411 |
{ |
| 2412 |
Builtin_call_expression* bce = call->builtin_call_expression(); |
| 2413 |
switch (bce->code()) |
| 2414 |
{ |
| 2415 |
case Builtin_call_expression::BUILTIN_APPEND: |
| 2416 |
{ |
| 2417 |
// Append returns the first argument. |
| 2418 |
// The subsequent arguments are already leaked because |
| 2419 |
// they are operands to append. |
| 2420 |
Node* appendee = Node::make_node(call->args()->front()); |
| 2421 |
this->assign(dst, appendee); |
| 2422 |
} |
| 2423 |
break; |
| 2424 |
|
| 2425 |
case Builtin_call_expression::BUILTIN_ADD: |
| 2426 |
{ |
| 2427 |
// unsafe.Add(p, off). |
| 2428 |
// Flow p to result. |
| 2429 |
Node* arg = Node::make_node(call->args()->front()); |
| 2430 |
this->assign(dst, arg); |
| 2431 |
} |
| 2432 |
break; |
| 2433 |
|
| 2434 |
case Builtin_call_expression::BUILTIN_SLICE: |
| 2435 |
{ |
| 2436 |
// unsafe.Slice(p, len). |
| 2437 |
// The resulting slice has the same backing store as p. Flow p to result. |
| 2438 |
Node* arg = Node::make_node(call->args()->front()); |
| 2439 |
this->assign(dst, arg); |
| 2440 |
} |
| 2441 |
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 |
case Builtin_call_expression::BUILTIN_CLOSE: |
| 2460 |
case Builtin_call_expression::BUILTIN_DELETE: |
| 2461 |
case Builtin_call_expression::BUILTIN_PRINT: |
| 2462 |
case Builtin_call_expression::BUILTIN_PRINTLN: |
| 2463 |
case Builtin_call_expression::BUILTIN_PANIC: |
| 2464 |
// these do not have result. |
| 2465 |
// fallthrough |
| 2466 |
case Builtin_call_expression::BUILTIN_MAKE: |
| 2467 |
case Builtin_call_expression::BUILTIN_NEW: |
| 2468 |
// should have been lowered to runtime calls at this point. |
| 2469 |
// fallthrough |
| 2470 |
default: |
| 2471 |
go_unreachable(); |
| 2472 |
} |
| 2473 |
break; |
| 2474 |
} |
| 2475 |
Func_expression* fe = call->fn()->func_expression(); |
| 2476 |
if (fe != NULL && fe->is_runtime_function()) |
| 2477 |
{ |
| 2478 |
switch (fe->runtime_code()) |
| 2479 |
{ |
| 2480 |
case Runtime::MAKECHAN: |
| 2481 |
case Runtime::MAKECHAN64: |
| 2482 |
case Runtime::MAKEMAP: |
| 2483 |
case Runtime::MAKESLICE: |
| 2484 |
case Runtime::MAKESLICE64: |
| 2485 |
// DST = make(...). |
| 2486 |
this->flows(dst, src); |
| 2487 |
break; |
| 2488 |
|
| 2489 |
default: |
| 2490 |
break; |
| 2491 |
} |
| 2492 |
break; |
| 2493 |
} |
| 2494 |
else if (fe != NULL |
| 2495 |
&& fe->named_object()->is_function() |
| 2496 |
&& fe->named_object()->func_value()->is_method() |
| 2497 |
&& (call->is_deferred() |
| 2498 |
|| call->is_concurrent())) |
| 2499 |
{ |
| 2500 |
// For a method call thunk, lose track of the call and treat it |
| 2501 |
// as if DST = RECEIVER. |
| 2502 |
Node* rcvr_node = Node::make_node(call->args()->front()); |
| 2503 |
this->assign(dst, rcvr_node); |
| 2504 |
break; |
| 2505 |
} |
| 2506 |
|
| 2507 |
// Result flows to dst. |
| 2508 |
Node* call_node = Node::make_node(e); |
| 2509 |
Node::Escape_state* call_state = call_node->state(this->context_, NULL); |
| 2510 |
std::vector<Node*> retvals = call_state->retvals; |
| 2511 |
for (std::vector<Node*>::const_iterator p = retvals.begin(); |
| 2512 |
p != retvals.end(); |
| 2513 |
++p) |
| 2514 |
this->flows(dst, *p); |
| 2515 |
} |
| 2516 |
break; |
| 2517 |
|
| 2518 |
case Expression::EXPRESSION_CALL_RESULT: |
| 2519 |
{ |
| 2520 |
Call_result_expression* cre = e->call_result_expression(); |
| 2521 |
Call_expression* call = cre->call()->call_expression(); |
| 2522 |
if (call->is_builtin()) |
| 2523 |
break; |
| 2524 |
if (call->fn()->func_expression() != NULL |
| 2525 |
&& call->fn()->func_expression()->is_runtime_function()) |
| 2526 |
{ |
| 2527 |
switch (call->fn()->func_expression()->runtime_code()) |
| 2528 |
{ |
| 2529 |
case Runtime::IFACEE2E2: |
| 2530 |
case Runtime::IFACEI2E2: |
| 2531 |
case Runtime::IFACEE2I2: |
| 2532 |
case Runtime::IFACEI2I2: |
| 2533 |
case Runtime::IFACEE2T2P: |
| 2534 |
case Runtime::IFACEI2T2P: |
| 2535 |
{ |
| 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 |
if (cre->index() != 0) |
| 2544 |
break; |
| 2545 |
Node* arg_node = Node::make_node(call->args()->back()); |
| 2546 |
this->assign(dst, arg_node); |
| 2547 |
} |
| 2548 |
break; |
| 2549 |
|
| 2550 |
default: |
| 2551 |
break; |
| 2552 |
} |
| 2553 |
break; |
| 2554 |
} |
| 2555 |
|
| 2556 |
Node* call_node = Node::make_node(call); |
| 2557 |
Node* ret_node = call_node->state(context_, NULL)->retvals[cre->index()]; |
| 2558 |
this->assign(dst, ret_node); |
| 2559 |
} |
| 2560 |
break; |
| 2561 |
|
| 2562 |
case Expression::EXPRESSION_FUNC_REFERENCE: |
| 2563 |
if (e->func_expression()->closure() != NULL) |
| 2564 |
this->flows(dst, src); |
| 2565 |
break; |
| 2566 |
|
| 2567 |
case Expression::EXPRESSION_CONVERSION: |
| 2568 |
{ |
| 2569 |
Type_conversion_expression* tce = e->conversion_expression(); |
| 2570 |
Type* ft = tce->expr()->type(); |
| 2571 |
Type* tt = tce->type(); |
| 2572 |
if ((ft->is_string_type() && tt->is_slice_type()) |
| 2573 |
|| (ft->is_slice_type() && tt->is_string_type()) |
| 2574 |
|| (ft->integer_type() != NULL && tt->is_string_type()) |
| 2575 |
|| tt->interface_type() != NULL) |
| 2576 |
{ |
| 2577 |
// string([]byte), string([]rune), []byte(string), []rune(string), string(rune), |
| 2578 |
// interface(T) |
| 2579 |
this->flows(dst, src); |
| 2580 |
break; |
| 2581 |
} |
| 2582 |
// Conversion preserves input value. |
| 2583 |
Expression* underlying = tce->expr(); |
| 2584 |
this->assign(dst, Node::make_node(underlying)); |
| 2585 |
} |
| 2586 |
break; |
| 2587 |
|
| 2588 |
case Expression::EXPRESSION_FIELD_REFERENCE: |
| 2589 |
{ |
| 2590 |
// A non-pointer can't escape from a struct. |
| 2591 |
if (!e->type()->has_pointer()) |
| 2592 |
break; |
| 2593 |
} |
| 2594 |
// Fall through. |
| 2595 |
|
| 2596 |
case Expression::EXPRESSION_TYPE_GUARD: |
| 2597 |
case Expression::EXPRESSION_ARRAY_INDEX: |
| 2598 |
case Expression::EXPRESSION_STRING_INDEX: |
| 2599 |
{ |
| 2600 |
Expression* left = NULL; |
| 2601 |
if (e->field_reference_expression() != NULL) |
| 2602 |
{ |
| 2603 |
left = e->field_reference_expression()->expr(); |
| 2604 |
if (left->unary_expression() != NULL |
| 2605 |
&& left->unary_expression()->op() == OPERATOR_MULT) |
| 2606 |
{ |
| 2607 |
// DST = (*x).f |
| 2608 |
this->flows(dst, src); |
| 2609 |
break; |
| 2610 |
} |
| 2611 |
} |
| 2612 |
else if (e->type_guard_expression() != NULL) |
| 2613 |
left = e->type_guard_expression()->expr(); |
| 2614 |
else if (e->array_index_expression() != NULL) |
| 2615 |
{ |
| 2616 |
Array_index_expression* aie = e->array_index_expression(); |
| 2617 |
if (aie->end() != NULL) |
| 2618 |
// slicing |
| 2619 |
if (aie->array()->type()->is_slice_type()) |
| 2620 |
left = aie->array(); |
| 2621 |
else |
| 2622 |
{ |
| 2623 |
// slicing an array |
| 2624 |
// The gc compiler has an implicit address operator. |
| 2625 |
go_assert(src->child() != NULL); |
| 2626 |
this->assign(dst, src->child()); |
| 2627 |
break; |
| 2628 |
} |
| 2629 |
else if (!aie->array()->type()->is_slice_type()) |
| 2630 |
{ |
| 2631 |
// Indexing an array preserves the input value. |
| 2632 |
Node* array_node = Node::make_node(aie->array()); |
| 2633 |
this->assign(dst, array_node); |
| 2634 |
break; |
| 2635 |
} |
| 2636 |
else |
| 2637 |
{ |
| 2638 |
this->flows(dst, src); |
| 2639 |
break; |
| 2640 |
} |
| 2641 |
} |
| 2642 |
else if (e->string_index_expression() != NULL) |
| 2643 |
{ |
| 2644 |
String_index_expression* sie = e->string_index_expression(); |
| 2645 |
if (e->type()->is_string_type()) |
| 2646 |
// slicing |
| 2647 |
left = sie->string(); |
| 2648 |
else |
| 2649 |
{ |
| 2650 |
this->flows(dst, src); |
| 2651 |
break; |
| 2652 |
} |
| 2653 |
} |
| 2654 |
go_assert(left != NULL); |
| 2655 |
|
| 2656 |
// Conversions, field access, and slicing all preserve the input |
| 2657 |
// value. |
| 2658 |
Node* left_node = Node::make_node(left); |
| 2659 |
this->assign(dst, left_node); |
| 2660 |
} |
| 2661 |
break; |
| 2662 |
|
| 2663 |
case Expression::EXPRESSION_BINARY: |
| 2664 |
{ |
| 2665 |
switch (e->binary_expression()->op()) |
| 2666 |
{ |
| 2667 |
case OPERATOR_PLUS: |
| 2668 |
case OPERATOR_MINUS: |
| 2669 |
case OPERATOR_XOR: |
| 2670 |
case OPERATOR_OR: |
| 2671 |
case OPERATOR_MULT: |
| 2672 |
case OPERATOR_DIV: |
| 2673 |
case OPERATOR_MOD: |
| 2674 |
case OPERATOR_LSHIFT: |
| 2675 |
case OPERATOR_RSHIFT: |
| 2676 |
case OPERATOR_AND: |
| 2677 |
case OPERATOR_BITCLEAR: |
| 2678 |
{ |
| 2679 |
Node* left = Node::make_node(e->binary_expression()->left()); |
| 2680 |
this->assign(dst, left); |
| 2681 |
Node* right = Node::make_node(e->binary_expression()->right()); |
| 2682 |
this->assign(dst, right); |
| 2683 |
} |
| 2684 |
break; |
| 2685 |
|
| 2686 |
default: |
| 2687 |
break; |
| 2688 |
} |
| 2689 |
} |
| 2690 |
break; |
| 2691 |
|
| 2692 |
case Expression::EXPRESSION_UNARY: |
| 2693 |
{ |
| 2694 |
switch (e->unary_expression()->op()) |
| 2695 |
{ |
| 2696 |
case OPERATOR_PLUS: |
| 2697 |
case OPERATOR_MINUS: |
| 2698 |
case OPERATOR_XOR: |
| 2699 |
{ |
| 2700 |
Node* op_node = |
| 2701 |
Node::make_node(e->unary_expression()->operand()); |
| 2702 |
this->assign(dst, op_node); |
| 2703 |
} |
| 2704 |
break; |
| 2705 |
|
| 2706 |
case OPERATOR_MULT: |
| 2707 |
// DST = *x |
| 2708 |
case OPERATOR_AND: |
| 2709 |
// DST = &x |
| 2710 |
this->flows(dst, src); |
| 2711 |
break; |
| 2712 |
|
| 2713 |
default: |
| 2714 |
break; |
| 2715 |
} |
| 2716 |
} |
| 2717 |
break; |
| 2718 |
|
| 2719 |
case Expression::EXPRESSION_TEMPORARY_REFERENCE: |
| 2720 |
{ |
| 2721 |
Statement* temp = e->temporary_reference_expression()->statement(); |
| 2722 |
this->assign(dst, Node::make_node(temp)); |
| 2723 |
} |
| 2724 |
break; |
| 2725 |
|
| 2726 |
case Expression::EXPRESSION_CONDITIONAL: |
| 2727 |
{ |
| 2728 |
Conditional_expression* ce = e->conditional_expression(); |
| 2729 |
this->assign(dst, Node::make_node(ce->then_expr())); |
| 2730 |
this->assign(dst, Node::make_node(ce->else_expr())); |
| 2731 |
} |
| 2732 |
break; |
| 2733 |
|
| 2734 |
case Expression::EXPRESSION_COMPOUND: |
| 2735 |
{ |
| 2736 |
Compound_expression* ce = e->compound_expression(); |
| 2737 |
this->assign(dst, Node::make_node(ce->expr())); |
| 2738 |
} |
| 2739 |
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 |
else if (src->statement() != NULL && src->statement()->temporary_statement() != NULL) |
| 2748 |
this->flows(dst, src); |
| 2749 |
} |
| 2750 |
|
| 2751 |
// Model the assignment of DST to an indirection of SRC. |
| 2752 |
|
| 2753 |
void |
| 2754 |
Escape_analysis_assign::assign_deref(Node* dst, Node* src) |
| 2755 |
{ |
| 2756 |
if (src->expr() != NULL) |
| 2757 |
{ |
| 2758 |
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 |
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 |
Escape_analysis_assign::assign_from_note(std::string* note, |
| 2784 |
const std::vector<Node*>& dsts, |
| 2785 |
Node* src) |
| 2786 |
{ |
| 2787 |
int enc = Escape_note::parse_tag(note); |
| 2788 |
if (src->expr() != NULL) |
| 2789 |
{ |
| 2790 |
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 |
if (this->context_->gogo()->debug_escape_level() > 2) |
| 2809 |
go_debug(src->location(), "assignfromtag:: src=%s em=%s", |
| 2810 |
src->ast_format(context_->gogo()).c_str(), |
| 2811 |
Escape_note::make_tag(enc).c_str()); |
| 2812 |
|
| 2813 |
if (enc == Node::ESCAPE_UNKNOWN) |
| 2814 |
{ |
| 2815 |
// Lost track of the value. |
| 2816 |
this->assign(this->context_->sink(), src); |
| 2817 |
return enc; |
| 2818 |
} |
| 2819 |
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 |
if ((enc & ESCAPE_CONTENT_ESCAPES) != 0) |
| 2825 |
this->assign(this->context_->sink(), this->context_->add_dereference(src)); |
| 2826 |
|
| 2827 |
int save_enc = enc; |
| 2828 |
enc >>= ESCAPE_RETURN_BITS; |
| 2829 |
for (std::vector<Node*>::const_iterator p = dsts.begin(); |
| 2830 |
enc != 0 && p != dsts.end(); |
| 2831 |
++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 |
int bits = enc & ESCAPE_BITS_MASK_FOR_TAG; |
| 2839 |
if (bits > 0) |
| 2840 |
{ |
| 2841 |
Node* n = src; |
| 2842 |
for (int i = 0; i < bits - 1; ++i) |
| 2843 |
{ |
| 2844 |
// Encode level > 0 as indirections. |
| 2845 |
n = this->context_->add_dereference(n); |
| 2846 |
} |
| 2847 |
this->assign(*p, n); |
| 2848 |
} |
| 2849 |
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 |
Escape_analysis_assign::flows(Node* dst, Node* src) |
| 2861 |
{ |
| 2862 |
// Don't bother capturing the flow from scalars. |
| 2863 |
if (src->type() != NULL && !src->type()->has_pointer()) |
| 2864 |
return; |
| 2865 |
|
| 2866 |
// Don't confuse a blank identifier with the sink. |
| 2867 |
if (dst->is_sink() && dst != this->context_->sink()) |
| 2868 |
return; |
| 2869 |
|
| 2870 |
Node::Escape_state* dst_state = dst->state(this->context_, NULL); |
| 2871 |
Node::Escape_state* src_state = src->state(this->context_, NULL); |
| 2872 |
if (dst == src |
| 2873 |
|| dst_state == src_state |
| 2874 |
|| dst_state->flows.find(src) != dst_state->flows.end()) |
| 2875 |
return; |
| 2876 |
|
| 2877 |
Gogo* gogo = this->context_->gogo(); |
| 2878 |
if (gogo->debug_escape_level() > 2) |
| 2879 |
go_debug(Linemap::unknown_location(), "flows:: %s <- %s", |
| 2880 |
dst->ast_format(gogo).c_str(), src->ast_format(gogo).c_str()); |
| 2881 |
|
| 2882 |
if (dst_state->flows.empty()) |
| 2883 |
this->context_->add_dst(dst); |
| 2884 |
|
| 2885 |
dst_state->flows.insert(src); |
| 2886 |
} |
| 2887 |
|
| 2888 |
// Build a connectivity graph between nodes in the function being analyzed. |
| 2889 |
|
| 2890 |
void |
| 2891 |
Gogo::assign_connectivity(Escape_context* context, Named_object* fn) |
| 2892 |
{ |
| 2893 |
// Must be defined outside of this package. |
| 2894 |
if (!fn->is_function()) |
| 2895 |
return; |
| 2896 |
|
| 2897 |
int save_depth = context->loop_depth(); |
| 2898 |
context->set_loop_depth(1); |
| 2899 |
|
| 2900 |
Escape_analysis_assign ea(context); |
| 2901 |
Function::Results* res = fn->func_value()->result_variables(); |
| 2902 |
if (res != NULL) |
| 2903 |
{ |
| 2904 |
for (Function::Results::const_iterator p = res->begin(); |
| 2905 |
p != res->end(); |
| 2906 |
++p) |
| 2907 |
{ |
| 2908 |
Node* res_node = Node::make_node(*p); |
| 2909 |
Node::Escape_state* res_state = res_node->state(context, fn); |
| 2910 |
res_state->fn = fn; |
| 2911 |
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 |
if (context->recursive()) |
| 2916 |
ea.flows(context->sink(), res_node); |
| 2917 |
} |
| 2918 |
} |
| 2919 |
|
| 2920 |
const Bindings* callee_bindings = fn->func_value()->block()->bindings(); |
| 2921 |
Function_type* fntype = fn->func_value()->type(); |
| 2922 |
Typed_identifier_list* params = (fntype->parameters() != NULL |
| 2923 |
? fntype->parameters()->copy() |
| 2924 |
: new Typed_identifier_list); |
| 2925 |
if (fntype->receiver() != NULL) |
| 2926 |
params->push_back(*fntype->receiver()); |
| 2927 |
|
| 2928 |
for (Typed_identifier_list::const_iterator p = params->begin(); |
| 2929 |
p != params->end(); |
| 2930 |
++p) |
| 2931 |
{ |
| 2932 |
if (p->name().empty() || Gogo::is_sink_name(p->name())) |
| 2933 |
continue; |
| 2934 |
|
| 2935 |
Named_object* param_no = callee_bindings->lookup_local(p->name()); |
| 2936 |
go_assert(param_no != NULL); |
| 2937 |
Node* param_node = Node::make_node(param_no); |
| 2938 |
Node::Escape_state* param_state = param_node->state(context, fn); |
| 2939 |
param_state->fn = fn; |
| 2940 |
param_state->loop_depth = 1; |
| 2941 |
|
| 2942 |
if (!p->type()->has_pointer()) |
| 2943 |
continue; |
| 2944 |
|
| 2945 |
param_node->set_encoding(Node::ESCAPE_NONE); |
| 2946 |
context->track(param_node); |
| 2947 |
} |
| 2948 |
|
| 2949 |
Escape_analysis_loop el; |
| 2950 |
fn->func_value()->traverse(&el); |
| 2951 |
|
| 2952 |
fn->func_value()->traverse(&ea); |
| 2953 |
context->set_loop_depth(save_depth); |
| 2954 |
} |
| 2955 |
|
| 2956 |
class Escape_analysis_flood |
| 2957 |
{ |
| 2958 |
public: |
| 2959 |
Escape_analysis_flood(Escape_context* context) |
| 2960 |
: 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 |
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 |
if (src->expr() != NULL) |
| 2991 |
{ |
| 2992 |
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 |
Node::Escape_state* src_state = src->state(this->context_, NULL); |
| 3009 |
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 |
level = level.min(src_state->level); |
| 3015 |
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 |
if (src_state->max_extra_loop_depth >= extra_loop_depth |
| 3021 |
|| src_state->loop_depth >= extra_loop_depth) |
| 3022 |
return; |
| 3023 |
src_state->max_extra_loop_depth = extra_loop_depth; |
| 3024 |
} |
| 3025 |
} |
| 3026 |
else |
| 3027 |
src_state->max_extra_loop_depth = -1; |
| 3028 |
|
| 3029 |
src_state->flood_id = this->context_->flood_id(); |
| 3030 |
src_state->level = level; |
| 3031 |
int mod_loop_depth = std::max(extra_loop_depth, src_state->loop_depth); |
| 3032 |
|
| 3033 |
Gogo* gogo = this->context_->gogo(); |
| 3034 |
int debug_level = gogo->debug_escape_level(); |
| 3035 |
if (debug_level > 1) |
| 3036 |
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 |
level.value(), level.suffix_value(), this->context_->pdepth(), |
| 3042 |
src->op_format().c_str(), |
| 3043 |
src->ast_format(gogo).c_str(), |
| 3044 |
src->details().c_str(), |
| 3045 |
debug_function_name(src_state->fn).c_str(), |
| 3046 |
src_state->loop_depth, |
| 3047 |
extra_loop_depth); |
| 3048 |
|
| 3049 |
this->context_->increase_pdepth(); |
| 3050 |
|
| 3051 |
// Input parameter flowing into output parameter? |
| 3052 |
Named_object* src_no = NULL; |
| 3053 |
if (src->expr() != NULL && src->expr()->var_expression() != NULL) |
| 3054 |
src_no = src->expr()->var_expression()->named_object(); |
| 3055 |
else |
| 3056 |
src_no = src->object(); |
| 3057 |
bool src_is_param = (src_no != NULL |
| 3058 |
&& src_no->is_variable() |
| 3059 |
&& src_no->var_value()->is_parameter()); |
| 3060 |
|
| 3061 |
Named_object* dst_no = NULL; |
| 3062 |
if (dst->expr() != NULL && dst->expr()->var_expression() != NULL) |
| 3063 |
dst_no = dst->expr()->var_expression()->named_object(); |
| 3064 |
else |
| 3065 |
dst_no = dst->object(); |
| 3066 |
bool dst_is_result = dst_no != NULL && dst_no->is_result_variable(); |
| 3067 |
Node::Escape_state* dst_state = dst->state(this->context_, NULL); |
| 3068 |
|
| 3069 |
if (src_is_param |
| 3070 |
&& dst_is_result |
| 3071 |
&& src_state->fn == dst_state->fn |
| 3072 |
&& (src->encoding() & ESCAPE_MASK) < int(Node::ESCAPE_HEAP) |
| 3073 |
&& 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 |
if (debug_level != 0) |
| 3081 |
{ |
| 3082 |
if (debug_level == 1) |
| 3083 |
go_debug(src->definition_location(), |
| 3084 |
"leaking param: %s to result %s level=%d", |
| 3085 |
src->ast_format(gogo).c_str(), |
| 3086 |
dst->ast_format(gogo).c_str(), |
| 3087 |
level.value()); |
| 3088 |
else |
| 3089 |
go_debug(src->definition_location(), |
| 3090 |
"leaking param: %s to result %s level={%d %d}", |
| 3091 |
src->ast_format(gogo).c_str(), |
| 3092 |
dst->ast_format(gogo).c_str(), |
| 3093 |
level.value(), level.suffix_value()); |
| 3094 |
} |
| 3095 |
|
| 3096 |
if ((src->encoding() & ESCAPE_MASK) != Node::ESCAPE_RETURN) |
| 3097 |
{ |
| 3098 |
int enc = |
| 3099 |
Node::ESCAPE_RETURN | (src->encoding() & ESCAPE_CONTENT_ESCAPES); |
| 3100 |
src->set_encoding(enc); |
| 3101 |
} |
| 3102 |
|
| 3103 |
int enc = Node::note_inout_flows(src->encoding(), |
| 3104 |
dst_no->result_var_value()->index(), |
| 3105 |
level); |
| 3106 |
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 |
level = level.copy(); |
| 3111 |
for (std::set<Node*>::const_iterator p = src_state->flows.begin(); |
| 3112 |
p != src_state->flows.end(); |
| 3113 |
++p) |
| 3114 |
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 |
if (src_is_param |
| 3122 |
&& dst->encoding() == Node::ESCAPE_HEAP |
| 3123 |
&& (src->encoding() & ESCAPE_MASK) < int(Node::ESCAPE_HEAP) |
| 3124 |
&& level.value() > 0) |
| 3125 |
{ |
| 3126 |
int enc = |
| 3127 |
Node::max_encoding((src->encoding() | ESCAPE_CONTENT_ESCAPES), |
| 3128 |
Node::ESCAPE_NONE); |
| 3129 |
src->set_encoding(enc); |
| 3130 |
if (debug_level != 0) |
| 3131 |
go_debug(src->definition_location(), "mark escaped content: %s", |
| 3132 |
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 |
bool src_leaks = (level.value() <= 0 |
| 3138 |
&& level.suffix_value() <= 0 |
| 3139 |
&& dst_state->loop_depth < mod_loop_depth); |
| 3140 |
src_leaks = src_leaks || (level.value() <= 0 |
| 3141 |
&& (dst->encoding() & ESCAPE_MASK) == Node::ESCAPE_HEAP); |
| 3142 |
// old src encoding, used to prevent duplicate error messages |
| 3143 |
int osrcesc = src->encoding(); |
| 3144 |
|
| 3145 |
if (src_is_param |
| 3146 |
&& (src_leaks || dst_state->loop_depth < 0) |
| 3147 |
&& (src->encoding() & ESCAPE_MASK) < int(Node::ESCAPE_HEAP)) |
| 3148 |
{ |
| 3149 |
if (level.suffix_value() > 0) |
| 3150 |
{ |
| 3151 |
int enc = |
| 3152 |
Node::max_encoding((src->encoding() | ESCAPE_CONTENT_ESCAPES), |
| 3153 |
Node::ESCAPE_NONE); |
| 3154 |
src->set_encoding(enc); |
| 3155 |
if (debug_level != 0 && osrcesc != src->encoding()) |
| 3156 |
go_debug(src->definition_location(), "leaking param content: %s", |
| 3157 |
src->ast_format(gogo).c_str()); |
| 3158 |
} |
| 3159 |
else |
| 3160 |
{ |
| 3161 |
if (debug_level != 0) |
| 3162 |
go_debug(src->definition_location(), "leaking param: %s", |
| 3163 |
src->ast_format(gogo).c_str()); |
| 3164 |
src->set_encoding(Node::ESCAPE_HEAP); |
| 3165 |
} |
| 3166 |
} |
| 3167 |
else if (src->expr() != NULL) |
| 3168 |
{ |
| 3169 |
Expression* e = src->expr(); |
| 3170 |
if (e->enclosed_var_expression() != NULL) |
| 3171 |
{ |
| 3172 |
if (src_leaks && debug_level != 0) |
| 3173 |
go_debug(src->location(), "leaking closure reference %s", |
| 3174 |
src->ast_format(gogo).c_str()); |
| 3175 |
|
| 3176 |
Node* enclosed_node = |
| 3177 |
Node::make_node(e->enclosed_var_expression()->variable()); |
| 3178 |
this->flood(level, dst, enclosed_node, -1); |
| 3179 |
} |
| 3180 |
else if (e->heap_expression() != NULL |
| 3181 |
|| (e->unary_expression() != NULL |
| 3182 |
&& e->unary_expression()->op() == OPERATOR_AND)) |
| 3183 |
{ |
| 3184 |
// Pointer literals and address-of expressions. |
| 3185 |
Expression* underlying; |
| 3186 |
if (e->heap_expression()) |
| 3187 |
underlying = e->heap_expression()->expr(); |
| 3188 |
else |
| 3189 |
underlying = e->unary_expression()->operand(); |
| 3190 |
Node* underlying_node = Node::make_node(underlying); |
| 3191 |
|
| 3192 |
// If the address leaks, the underyling object must be moved |
| 3193 |
// to the heap. |
| 3194 |
underlying->address_taken(src_leaks); |
| 3195 |
if (src_leaks) |
| 3196 |
{ |
| 3197 |
src->set_encoding(Node::ESCAPE_HEAP); |
| 3198 |
if (osrcesc != src->encoding()) |
| 3199 |
{ |
| 3200 |
move_to_heap(gogo, underlying); |
| 3201 |
if (debug_level > 1) |
| 3202 |
go_debug(src->location(), |
| 3203 |
"%s escapes to heap, level={%d %d}, " |
| 3204 |
"dst.eld=%d, src.eld=%d", |
| 3205 |
src->ast_format(gogo).c_str(), level.value(), |
| 3206 |
level.suffix_value(), dst_state->loop_depth, |
| 3207 |
mod_loop_depth); |
| 3208 |
else if (debug_level > 0) |
| 3209 |
go_debug(src->location(), "%s escapes to heap", |
| 3210 |
src->ast_format(gogo).c_str()); |
| 3211 |
} |
| 3212 |
|
| 3213 |
this->flood(level.decrease(), dst, |
| 3214 |
underlying_node, mod_loop_depth); |
| 3215 |
extra_loop_depth = mod_loop_depth; |
| 3216 |
} |
| 3217 |
else |
| 3218 |
{ |
| 3219 |
// Decrease the level each time we take the address of the object. |
| 3220 |
this->flood(level.decrease(), dst, underlying_node, -1); |
| 3221 |
} |
| 3222 |
} |
| 3223 |
else if (e->slice_literal() != NULL) |
| 3224 |
{ |
| 3225 |
Slice_construction_expression* slice = e->slice_literal(); |
| 3226 |
if (slice->vals() != NULL) |
| 3227 |
{ |
| 3228 |
for (Expression_list::const_iterator p = slice->vals()->begin(); |
| 3229 |
p != slice->vals()->end(); |
| 3230 |
++p) |
| 3231 |
{ |
| 3232 |
if ((*p) != NULL) |
| 3233 |
this->flood(level.decrease(), dst, Node::make_node(*p), -1); |
| 3234 |
} |
| 3235 |
} |
| 3236 |
if (src_leaks) |
| 3237 |
{ |
| 3238 |
src->set_encoding(Node::ESCAPE_HEAP); |
| 3239 |
if (debug_level != 0 && osrcesc != src->encoding()) |
| 3240 |
go_debug(src->location(), "%s escapes to heap", |
| 3241 |
src->ast_format(gogo).c_str()); |
| 3242 |
extra_loop_depth = mod_loop_depth; |
| 3243 |
} |
| 3244 |
} |
| 3245 |
else if (e->call_expression() != NULL) |
| 3246 |
{ |
| 3247 |
Call_expression* call = e->call_expression(); |
| 3248 |
if (call->is_builtin()) |
| 3249 |
{ |
| 3250 |
Builtin_call_expression* bce = call->builtin_call_expression(); |
| 3251 |
if (bce->code() == Builtin_call_expression::BUILTIN_APPEND) |
| 3252 |
{ |
| 3253 |
// Propagate escape information to appendee. |
| 3254 |
Expression* appendee = call->args()->front(); |
| 3255 |
this->flood(level, dst, Node::make_node(appendee), -1); |
| 3256 |
} |
| 3257 |
} |
| 3258 |
else if (call->fn()->func_expression() != NULL |
| 3259 |
&& call->fn()->func_expression()->is_runtime_function()) |
| 3260 |
{ |
| 3261 |
switch (call->fn()->func_expression()->runtime_code()) |
| 3262 |
{ |
| 3263 |
case Runtime::MAKECHAN: |
| 3264 |
case Runtime::MAKECHAN64: |
| 3265 |
case Runtime::MAKEMAP: |
| 3266 |
case Runtime::MAKESLICE: |
| 3267 |
case Runtime::MAKESLICE64: |
| 3268 |
if (src_leaks) |
| 3269 |
{ |
| 3270 |
src->set_encoding(Node::ESCAPE_HEAP); |
| 3271 |
if (debug_level != 0 && osrcesc != src->encoding()) |
| 3272 |
go_debug(src->location(), "%s escapes to heap", |
| 3273 |
src->ast_format(gogo).c_str()); |
| 3274 |
extra_loop_depth = mod_loop_depth; |
| 3275 |
} |
| 3276 |
break; |
| 3277 |
|
| 3278 |
default: |
| 3279 |
break; |
| 3280 |
} |
| 3281 |
} |
| 3282 |
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 |
go_assert(src_state->retvals.size() == 1); |
| 3290 |
if (debug_level > 2) |
| 3291 |
go_debug(src->location(), "[%d] dst %s escwalk replace src: %s with %s", |
| 3292 |
this->context_->loop_depth(), |
| 3293 |
dst->ast_format(gogo).c_str(), |
| 3294 |
src->ast_format(gogo).c_str(), |
| 3295 |
src_state->retvals[0]->ast_format(gogo).c_str()); |
| 3296 |
src = src_state->retvals[0]; |
| 3297 |
src_state = src->state(this->context_, NULL); |
| 3298 |
} |
| 3299 |
} |
| 3300 |
else if (e->allocation_expression() != NULL && src_leaks) |
| 3301 |
{ |
| 3302 |
// Calls to Runtime::NEW get lowered into an allocation expression. |
| 3303 |
src->set_encoding(Node::ESCAPE_HEAP); |
| 3304 |
if (debug_level != 0 && osrcesc != src->encoding()) |
| 3305 |
go_debug(src->location(), "%s escapes to heap", |
| 3306 |
src->ast_format(gogo).c_str()); |
| 3307 |
extra_loop_depth = mod_loop_depth; |
| 3308 |
} |
| 3309 |
else if ((e->map_literal() != NULL |
| 3310 |
|| e->string_concat_expression() != NULL |
| 3311 |
|| (e->func_expression() != NULL && e->func_expression()->closure() != NULL) |
| 3312 |
|| e->bound_method_expression() != NULL) |
| 3313 |
&& src_leaks) |
| 3314 |
{ |
| 3315 |
src->set_encoding(Node::ESCAPE_HEAP); |
| 3316 |
if (debug_level != 0 && osrcesc != src->encoding()) |
| 3317 |
go_debug(src->location(), "%s escapes to heap", |
| 3318 |
src->ast_format(gogo).c_str()); |
| 3319 |
extra_loop_depth = mod_loop_depth; |
| 3320 |
} |
| 3321 |
else if (e->conversion_expression() != NULL && src_leaks) |
| 3322 |
{ |
| 3323 |
Type_conversion_expression* tce = e->conversion_expression(); |
| 3324 |
Type* ft = tce->expr()->type(); |
| 3325 |
Type* tt = tce->type(); |
| 3326 |
if ((ft->is_string_type() && tt->is_slice_type()) |
| 3327 |
|| (ft->is_slice_type() && tt->is_string_type()) |
| 3328 |
|| (ft->integer_type() != NULL && tt->is_string_type()) |
| 3329 |
|| tt->interface_type() != NULL) |
| 3330 |
{ |
| 3331 |
// string([]byte), string([]rune), []byte(string), []rune(string), string(rune), |
| 3332 |
// interface(T) |
| 3333 |
src->set_encoding(Node::ESCAPE_HEAP); |
| 3334 |
if (debug_level != 0 && osrcesc != src->encoding()) |
| 3335 |
go_debug(src->location(), "%s escapes to heap", |
| 3336 |
src->ast_format(gogo).c_str()); |
| 3337 |
extra_loop_depth = mod_loop_depth; |
| 3338 |
if (tt->interface_type() != NULL |
| 3339 |
&& ft->has_pointer() |
| 3340 |
&& !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 |
this->flood(level, this->context_->sink(), |
| 3345 |
Node::make_node(tce->expr()), -1); |
| 3346 |
} |
| 3347 |
} |
| 3348 |
else if (e->array_index_expression() != NULL |
| 3349 |
&& !e->array_index_expression()->array()->type()->is_slice_type()) |
| 3350 |
{ |
| 3351 |
Array_index_expression* aie = e->array_index_expression(); |
| 3352 |
if (aie->end() != NULL) |
| 3353 |
{ |
| 3354 |
// Slicing an array. |
| 3355 |
// Flow its implicit address-of node to DST. |
| 3356 |
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 |
Expression* underlying = e->array_index_expression()->array(); |
| 3364 |
Node* underlying_node = Node::make_node(underlying); |
| 3365 |
this->flood(level, dst, underlying_node, -1); |
| 3366 |
} |
| 3367 |
} |
| 3368 |
else if ((e->field_reference_expression() != NULL |
| 3369 |
&& e->field_reference_expression()->expr()->unary_expression() == NULL) |
| 3370 |
|| e->type_guard_expression() != NULL |
| 3371 |
|| (e->array_index_expression() != NULL |
| 3372 |
&& e->array_index_expression()->end() != NULL) |
| 3373 |
|| (e->string_index_expression() != NULL |
| 3374 |
&& e->type()->is_string_type())) |
| 3375 |
{ |
| 3376 |
Expression* underlying; |
| 3377 |
if (e->field_reference_expression() != NULL) |
| 3378 |
underlying = e->field_reference_expression()->expr(); |
| 3379 |
else if (e->type_guard_expression() != NULL) |
| 3380 |
underlying = e->type_guard_expression()->expr(); |
| 3381 |
else if (e->array_index_expression() != NULL) |
| 3382 |
underlying = e->array_index_expression()->array(); |
| 3383 |
else |
| 3384 |
underlying = e->string_index_expression()->string(); |
| 3385 |
|
| 3386 |
Node* underlying_node = Node::make_node(underlying); |
| 3387 |
this->flood(level, dst, underlying_node, -1); |
| 3388 |
} |
| 3389 |
else if ((e->field_reference_expression() != NULL |
| 3390 |
&& e->field_reference_expression()->expr()->unary_expression() != NULL) |
| 3391 |
|| e->array_index_expression() != NULL |
| 3392 |
|| e->map_index_expression() != NULL |
| 3393 |
|| (e->unary_expression() != NULL |
| 3394 |
&& e->unary_expression()->op() == OPERATOR_MULT)) |
| 3395 |
{ |
| 3396 |
Expression* underlying; |
| 3397 |
if (e->field_reference_expression() != NULL) |
| 3398 |
{ |
| 3399 |
underlying = e->field_reference_expression()->expr(); |
| 3400 |
underlying = underlying->unary_expression()->operand(); |
| 3401 |
} |
| 3402 |
else if (e->array_index_expression() != NULL) |
| 3403 |
underlying = e->array_index_expression()->array(); |
| 3404 |
else if (e->map_index_expression() != NULL) |
| 3405 |
underlying = e->map_index_expression()->map(); |
| 3406 |
else |
| 3407 |
underlying = e->unary_expression()->operand(); |
| 3408 |
|
| 3409 |
// Increase the level for a dereference. |
| 3410 |
Node* underlying_node = Node::make_node(underlying); |
| 3411 |
this->flood(level.increase(), dst, underlying_node, -1); |
| 3412 |
} |
| 3413 |
else if (e->temporary_reference_expression() != NULL) |
| 3414 |
{ |
| 3415 |
Statement* t = e->temporary_reference_expression()->statement(); |
| 3416 |
this->flood(level, dst, Node::make_node(t), -1); |
| 3417 |
} |
| 3418 |
} |
| 3419 |
else if (src->is_indirect()) |
| 3420 |
// Increase the level for a dereference. |
| 3421 |
this->flood(level.increase(), dst, src->child(), -1); |
| 3422 |
|
| 3423 |
level = level.copy(); |
| 3424 |
for (std::set<Node*>::const_iterator p = src_state->flows.begin(); |
| 3425 |
p != src_state->flows.end(); |
| 3426 |
++p) |
| 3427 |
this->flood(level, dst, *p, extra_loop_depth); |
| 3428 |
|
| 3429 |
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 |
Gogo::propagate_escape(Escape_context* context, Node* dst) |
| 3437 |
{ |
| 3438 |
if (dst->object() == NULL |
| 3439 |
&& (dst->expr() == NULL |
| 3440 |
|| (dst->expr()->var_expression() == NULL |
| 3441 |
&& dst->expr()->enclosed_var_expression() == NULL |
| 3442 |
&& dst->expr()->func_expression() == NULL))) |
| 3443 |
return; |
| 3444 |
|
| 3445 |
Node::Escape_state* state = dst->state(context, NULL); |
| 3446 |
Gogo* gogo = context->gogo(); |
| 3447 |
if (gogo->debug_escape_level() > 1) |
| 3448 |
go_debug(Linemap::unknown_location(), "escflood:%d: dst %s scope:%s[%d]", |
| 3449 |
context->flood_id(), dst->ast_format(gogo).c_str(), |
| 3450 |
debug_function_name(state->fn).c_str(), |
| 3451 |
state->loop_depth); |
| 3452 |
|
| 3453 |
Escape_analysis_flood eaf(context); |
| 3454 |
for (std::set<Node*>::const_iterator p = state->flows.begin(); |
| 3455 |
p != state->flows.end(); |
| 3456 |
++p) |
| 3457 |
{ |
| 3458 |
context->increase_flood_id(); |
| 3459 |
eaf.flood(Level::From(0), dst, *p, -1); |
| 3460 |
} |
| 3461 |
} |
| 3462 |
|
| 3463 |
class Escape_analysis_tag |
| 3464 |
{ |
| 3465 |
public: |
| 3466 |
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 |
Escape_analysis_tag::tag(Named_object* fn) |
| 3477 |
{ |
| 3478 |
// External functions are assumed unsafe |
| 3479 |
// unless //go:noescape is given before the declaration. |
| 3480 |
if (fn->is_function_declaration()) |
| 3481 |
{ |
| 3482 |
Function_declaration* fdcl = fn->func_declaration_value(); |
| 3483 |
if ((fdcl->pragmas() & GOPRAGMA_NOESCAPE) != 0) |
| 3484 |
{ |
| 3485 |
Function_type* fntype = fdcl->type(); |
| 3486 |
if (fntype->parameters() != NULL) |
| 3487 |
{ |
| 3488 |
const Typed_identifier_list* til = fntype->parameters(); |
| 3489 |
int i = 0; |
| 3490 |
for (Typed_identifier_list::const_iterator p = til->begin(); |
| 3491 |
p != til->end(); |
| 3492 |
++p, ++i) |
| 3493 |
if (p->type()->has_pointer()) |
| 3494 |
fntype->add_parameter_note(i, Node::ESCAPE_NONE); |
| 3495 |
} |
| 3496 |
} |
| 3497 |
} |
| 3498 |
|
| 3499 |
if (!fn->is_function()) |
| 3500 |
return; |
| 3501 |
|
| 3502 |
Function_type* fntype = fn->func_value()->type(); |
| 3503 |
Bindings* bindings = fn->func_value()->block()->bindings(); |
| 3504 |
|
| 3505 |
if (fntype->is_method()) |
| 3506 |
{ |
| 3507 |
if (fntype->receiver()->name().empty() |
| 3508 |
|| Gogo::is_sink_name(fntype->receiver()->name())) |
| 3509 |
// Unnamed receiver is not used in the function body, does not escape. |
| 3510 |
fntype->add_receiver_note(Node::ESCAPE_NONE); |
| 3511 |
else |
| 3512 |
{ |
| 3513 |
Named_object* rcvr_no = bindings->lookup(fntype->receiver()->name()); |
| 3514 |
go_assert(rcvr_no != NULL); |
| 3515 |
Node* rcvr_node = Node::make_node(rcvr_no); |
| 3516 |
switch ((rcvr_node->encoding() & ESCAPE_MASK)) |
| 3517 |
{ |
| 3518 |
case Node::ESCAPE_NONE: // not touched by flood |
| 3519 |
case Node::ESCAPE_RETURN: |
| 3520 |
if (fntype->receiver()->type()->has_pointer()) |
| 3521 |
// Don't bother tagging for scalars. |
| 3522 |
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 |
int i = 0; |
| 3535 |
if (fntype->parameters() != NULL) |
| 3536 |
{ |
| 3537 |
const Typed_identifier_list* til = fntype->parameters(); |
| 3538 |
for (Typed_identifier_list::const_iterator p = til->begin(); |
| 3539 |
p != til->end(); |
| 3540 |
++p, ++i) |
| 3541 |
{ |
| 3542 |
if (p->name().empty() || Gogo::is_sink_name(p->name())) |
| 3543 |
{ |
| 3544 |
// Parameter not used in the function body, does not escape. |
| 3545 |
if (p->type()->has_pointer()) |
| 3546 |
fntype->add_parameter_note(i, Node::ESCAPE_NONE); |
| 3547 |
continue; |
| 3548 |
} |
| 3549 |
|
| 3550 |
Named_object* param_no = bindings->lookup(p->name()); |
| 3551 |
go_assert(param_no != NULL); |
| 3552 |
Node* param_node = Node::make_node(param_no); |
| 3553 |
switch ((param_node->encoding() & ESCAPE_MASK)) |
| 3554 |
{ |
| 3555 |
case Node::ESCAPE_NONE: // not touched by flood |
| 3556 |
case Node::ESCAPE_RETURN: |
| 3557 |
if (p->type()->has_pointer()) |
| 3558 |
// Don't bother tagging for scalars. |
| 3559 |
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 |
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 |
Gogo::tag_function(Named_object* fn) |
| 3578 |
{ |
| 3579 |
Escape_analysis_tag eat; |
| 3580 |
eat.tag(fn); |
| 3581 |
} |
| 3582 |
|
| 3583 |
// Reclaim memory of escape analysis Nodes. |
| 3584 |
|
| 3585 |
void |
| 3586 |
Gogo::reclaim_escape_nodes() |
| 3587 |
{ |
| 3588 |
Node::reclaim_nodes(); |
| 3589 |
} |
| 3590 |
|
| 3591 |
void |
| 3592 |
Node::reclaim_nodes() |
| 3593 |
{ |
| 3594 |
for (Unordered_map(Named_object*, Node*)::iterator p = |
| 3595 |
Node::objects.begin(); |
| 3596 |
p != Node::objects.end(); |
| 3597 |
++p) |
| 3598 |
delete p->second; |
| 3599 |
Node::objects.clear(); |
| 3600 |
|
| 3601 |
for (Unordered_map(Expression*, Node*)::iterator p = |
| 3602 |
Node::expressions.begin(); |
| 3603 |
p != Node::expressions.end(); |
| 3604 |
++p) |
| 3605 |
delete p->second; |
| 3606 |
Node::expressions.clear(); |
| 3607 |
|
| 3608 |
for (Unordered_map(Statement*, Node*)::iterator p = |
| 3609 |
Node::statements.begin(); |
| 3610 |
p != Node::statements.end(); |
| 3611 |
++p) |
| 3612 |
delete p->second; |
| 3613 |
Node::statements.clear(); |
| 3614 |
|
| 3615 |
for (std::vector<Node*>::iterator p = Node::indirects.begin(); |
| 3616 |
p != Node::indirects.end(); |
| 3617 |
++p) |
| 3618 |
delete *p; |
| 3619 |
Node::indirects.clear(); |
| 3620 |
} |