1 // escape.h -- 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 #ifndef GO_ESCAPE_H 8 #define GO_ESCAPE_H 9 10 #include "gogo.h" 11 12 class Named_object; 13 class Expression; 14 class Statement; 15 class Escape_context; 16 17 // There can be loops in the escape graph that lead to arbitrary recursions. 18 // See comment in gc/esc.go. 19 static const int MIN_LEVEL = -2; 20 21 // Level models the escapement of a Node using two integers that are computed 22 // by backwards-analyzing the flow of a function from its sink and increasing or 23 // decreasing based on dereferences and addressing, respectively. 24 // One integer, known as the level's VALUE (think absolute value), is just the 25 // sum of indirections (via referencing or dereferencing) applied to the Node. 26 // The second, known as the level's SUFFIX_VALUE, is the amount of indirections 27 // applied after some data has been copied from the node. When accessing a 28 // field F of an object O and then applying indirections, for example, the field 29 // access O.F is assumed to copy that data from O before applying indirections. 30 // With this, even if O.F escapes, it might mean that the content of O escape, 31 // but not the object O itself. 32 33 class Level 34 { 35 public: Level()36 Level() 37 : value_(0), suffix_value_(0) 38 { } 39 Level(int value,int suffix)40 Level(int value, int suffix) 41 : value_(value), suffix_value_(suffix) 42 { } 43 44 // Return this level's value. 45 int value()46 value() const 47 { return this->value_; } 48 49 // Return this level's suffix value. 50 int suffix_value()51 suffix_value() const 52 { return this->suffix_value_; } 53 54 // Increase the level because a node is dereferenced. 55 Level increase()56 increase() const 57 { 58 if (this->value_ <= MIN_LEVEL) 59 return Level(MIN_LEVEL, 0); 60 61 return Level(this->value_ + 1, this->suffix_value_ + 1); 62 } 63 64 // Decrease the level because a node is referenced. 65 Level decrease()66 decrease() const 67 { 68 if (this->value_ <= MIN_LEVEL) 69 return Level(MIN_LEVEL, 0); 70 71 return Level(this->value_ - 1, this->suffix_value_ - 1); 72 } 73 74 // Model a node being copied. 75 Level copy()76 copy() const 77 { 78 return Level(this->value_, std::max(this->suffix_value_, 0)); 79 } 80 81 // Return a level with the minimum values of this level and l. 82 Level min(const Level & l)83 min(const Level& l) const 84 { 85 return Level(std::min(this->value_, l.value()), 86 std::min(this->suffix_value_, l.suffix_value())); 87 } 88 89 // Compare two levels for equality. 90 bool 91 operator==(const Level& l) const 92 { 93 return (this->value_ == l.value() 94 && this->suffix_value_ == l.suffix_value()); 95 } 96 97 // Create a level from an integer value. 98 static Level From(int i)99 From(int i) 100 { 101 if (i <= MIN_LEVEL) 102 return Level(MIN_LEVEL, 0); 103 return Level(i, 0); 104 } 105 106 private: 107 // The sum of all references (-1) and indirects (+1) applied to a Node. 108 int value_; 109 // The sum of all references (-1) abd indirects (+1) applied to a copied Node. 110 int suffix_value_; 111 }; 112 113 // A node in the escape graph. This node is an alias to a particular node 114 // in the Go parse tree. Specifically, it can represent an expression node, 115 // a statement node, or a named object node (a variable or function). 116 117 class Node 118 { 119 public: 120 // This classification represents type of nodes in the Go parse tree that are 121 // interesting during the analysis. 122 enum Node_classification 123 { 124 NODE_OBJECT, 125 NODE_EXPRESSION, 126 NODE_STATEMENT, 127 // A "fake" node that models the indirection of its child node. 128 // This node does not correspond to an AST node. 129 NODE_INDIRECT 130 }; 131 132 // The state necessary to keep track of how a node escapes. 133 struct Escape_state 134 { 135 // The current function. 136 Named_object* fn; 137 // A list of source nodes that flow into this node. 138 std::set<Node*> flows; 139 // If the node is a function call, the list of nodes returned. 140 std::vector<Node*> retvals; 141 // The node's loop depth. 142 int loop_depth; 143 // There is an extra loop depth in the flood phase used to account for 144 // variables referenced across closures. This is the maximum value of the 145 // extra loop depth seen during the flood that touches this node. 146 int max_extra_loop_depth; 147 // The node's level. 148 Level level; 149 // An ID given to a node when it is encountered as a flow from the current 150 // dst node. This is used to avoid infinite recursion of cyclic nodes. 151 int flood_id; 152 Escape_stateEscape_state153 Escape_state() 154 : fn(NULL), loop_depth(0), max_extra_loop_depth(0), flood_id(0) 155 { } 156 }; 157 158 // Note: values in this enum appear in export data, and therefore MUST NOT 159 // change. 160 enum Escapement_encoding 161 { 162 ESCAPE_UNKNOWN, 163 // Does not escape to heap, result, or parameters. 164 ESCAPE_NONE, 165 // Is returned or reachable from a return statement. 166 ESCAPE_RETURN, 167 // Reachable from the heap. 168 ESCAPE_HEAP, 169 // By construction will not escape. 170 ESCAPE_NEVER 171 }; 172 173 // Multiple constructors for each classification. Node(Named_object * no)174 Node(Named_object* no) 175 : classification_(NODE_OBJECT), state_(NULL), encoding_(ESCAPE_UNKNOWN), 176 child_(NULL) 177 { this->u_.object_val = no; } 178 Node(Expression * e)179 Node(Expression* e) 180 : classification_(NODE_EXPRESSION), state_(NULL), encoding_(ESCAPE_UNKNOWN), 181 child_(NULL) 182 { this->u_.expression_val = e; } 183 Node(Statement * s)184 Node(Statement* s) 185 : classification_(NODE_STATEMENT), state_(NULL), encoding_(ESCAPE_UNKNOWN), 186 child_(NULL) 187 { this->u_.statement_val = s; } 188 Node(Node * n)189 Node(Node *n) 190 : classification_(NODE_INDIRECT), state_(NULL), encoding_(ESCAPE_UNKNOWN), 191 child_(n) 192 {} 193 194 ~Node(); 195 196 // Return this node's type. 197 Type* 198 type() const; 199 200 // Return this node's location. 201 Location 202 location() const; 203 204 // Return the location where the node's underlying object is defined. 205 Location 206 definition_location() const; 207 208 // Return this node's AST formatted string. 209 std::string 210 ast_format(Gogo*) const; 211 212 // Return this node's detailed format string. 213 std::string 214 details(); 215 216 std::string 217 op_format() const; 218 219 // Return this node's escape state. 220 Escape_state* 221 state(Escape_context* context, Named_object* fn); 222 223 // Return this node's escape encoding. 224 int 225 encoding(); 226 227 // Set the node's escape encoding. 228 void 229 set_encoding(int enc); 230 231 bool 232 is_big(Escape_context*) const; 233 234 bool 235 is_sink() const; 236 237 // Methods to return the underlying value in the Node union. 238 Named_object* object()239 object() const 240 { 241 return (this->classification_ == NODE_OBJECT 242 ? this->u_.object_val 243 : NULL); 244 } 245 246 Expression* expr()247 expr() const 248 { 249 return (this->classification_ == NODE_EXPRESSION 250 ? this->u_.expression_val 251 : NULL); 252 } 253 254 Statement* statement()255 statement() const 256 { 257 return (this->classification_ == NODE_STATEMENT 258 ? this->u_.statement_val 259 : NULL); 260 } 261 262 bool is_indirect()263 is_indirect() const 264 { return this->classification_ == NODE_INDIRECT; } 265 266 // Return its child node. 267 // Child node is used only in indirect node, and in expression node 268 // representing slicing an array. 269 Node* child()270 child() const 271 { return this->child_; } 272 273 // Set the child node. 274 void set_child(Node * n)275 set_child(Node* n) 276 { this->child_ = n; } 277 278 // Static creation methods for each value supported in the union. 279 static Node* 280 make_node(Named_object*); 281 282 static Node* 283 make_node(Expression*); 284 285 static Node* 286 make_node(Statement*); 287 288 static Node* 289 make_indirect_node(Node*); 290 291 // Return the maximum of an existing escape encoding E and a new 292 // escape type. 293 static int 294 max_encoding(int e, int etype); 295 296 // Return a modified encoding for an input parameter that flows into an 297 // output parameter. 298 static int 299 note_inout_flows(int e, int index, Level level); 300 301 // Reclaim nodes. 302 static void 303 reclaim_nodes(); 304 305 private: 306 // The classification of this Node. 307 Node_classification classification_; 308 // The value union. 309 union 310 { 311 // If NODE_OBJECT. 312 Named_object* object_val; 313 // If NODE_EXPRESSION. 314 Expression* expression_val; 315 // If NODE_STATEMENT. 316 Statement* statement_val; 317 } u_; 318 // The node's escape state. 319 Escape_state* state_; 320 // The node's escape encoding. 321 // The encoding: 322 // | Return Encoding: (width - ESCAPE_RETURN_BITS) | 323 // | Content Escapes bit: 1 | 324 // | Escapement_encoding: ESCAPE_BITS | 325 int encoding_; 326 327 // Child node, used only in indirect node, and expression node representing 328 // slicing an array. 329 Node* child_; 330 331 // Cache all the Nodes created via Node::make_node to make the API simpler. 332 static Unordered_map(Named_object*, Node*) objects; 333 static Unordered_map(Expression*, Node*) expressions; 334 static Unordered_map(Statement*, Node*) statements; 335 336 // Collection of all NODE_INDIRECT Nodes, used for reclaiming memory. This 337 // is not a cache -- each make_indirect_node will make a fresh Node. 338 static std::vector<Node*> indirects; 339 }; 340 341 // The amount of bits used for the escapement encoding. 342 static const int ESCAPE_BITS = 3; 343 344 // Mask used to extract encoding. 345 static const int ESCAPE_MASK = (1 << ESCAPE_BITS) - 1; 346 347 // Value obtained by indirect of parameter escapes to heap. 348 static const int ESCAPE_CONTENT_ESCAPES = 1 << ESCAPE_BITS; 349 350 // The amount of bits used in encoding of return values. 351 static const int ESCAPE_RETURN_BITS = ESCAPE_BITS + 1; 352 353 // For each output, the number of bits for a tag. 354 static const int ESCAPE_BITS_PER_OUTPUT_IN_TAG = 3; 355 356 // The bit max to extract a single tag. 357 static const int ESCAPE_BITS_MASK_FOR_TAG = (1 << ESCAPE_BITS_PER_OUTPUT_IN_TAG) - 1; 358 359 // The largest level that can be stored in a tag. 360 static const int ESCAPE_MAX_ENCODED_LEVEL = ESCAPE_BITS_MASK_FOR_TAG - 1; 361 362 // A helper for converting escape notes from encoded integers to a 363 // textual format and vice-versa. 364 365 class Escape_note 366 { 367 public: 368 // Return the string representation of an escapement encoding. 369 static std::string 370 make_tag(int encoding); 371 372 // Return the escapement encoding for a string tag. 373 static int 374 parse_tag(std::string* tag); 375 }; 376 377 // The escape context for a set of functions being analyzed. 378 379 class Escape_context 380 { 381 public: 382 Escape_context(Gogo* gogo, bool recursive); 383 384 // Return the Go IR. 385 Gogo* gogo()386 gogo() const 387 { return this->gogo_; } 388 389 // Return the current function being analyzed. 390 Named_object* current_function()391 current_function() const 392 { return this->current_function_; } 393 394 // Change the function being analyzed. 395 void set_current_function(Named_object * fn)396 set_current_function(Named_object* fn) 397 { this->current_function_ = fn; } 398 399 // Return the name of the current function. 400 std::string 401 current_function_name() const; 402 403 // Return true if this is the context for a mutually recursive set of functions. 404 bool recursive()405 recursive() const 406 { return this->recursive_; } 407 408 // Return the special sink node for this context. 409 Node* sink()410 sink() 411 { return this->sink_; } 412 413 // Return the current loop depth. 414 int loop_depth()415 loop_depth() const 416 { return this->loop_depth_; } 417 418 // Increase the loop depth. 419 void increase_loop_depth()420 increase_loop_depth() 421 { this->loop_depth_++; } 422 423 // Decrease the loop depth. 424 void decrease_loop_depth()425 decrease_loop_depth() 426 { this->loop_depth_--; } 427 428 void set_loop_depth(int depth)429 set_loop_depth(int depth) 430 { this->loop_depth_ = depth; } 431 432 // Return the destination nodes encountered in this context. 433 const std::set<Node*>& dsts()434 dsts() const 435 { return this->dsts_; } 436 437 // Add a destination node. 438 void add_dst(Node * dst)439 add_dst(Node* dst) 440 { this->dsts_.insert(dst); } 441 442 // Return the nodes initially marked as non-escaping before flooding. 443 const std::vector<Node*>& non_escaping_nodes()444 non_escaping_nodes() const 445 { return this->noesc_; } 446 447 // Initialize the dummy return values for this Node N using the results 448 // in FNTYPE. 449 void 450 init_retvals(Node* n, Function_type* fntype); 451 452 // Return the indirection of Node N. 453 Node* 454 add_dereference(Node* n); 455 456 // Keep track of possibly non-escaping node N. 457 void 458 track(Node* n); 459 460 int flood_id()461 flood_id() const 462 { return this->flood_id_; } 463 464 void increase_flood_id()465 increase_flood_id() 466 { this->flood_id_++; } 467 468 int pdepth()469 pdepth() const 470 { return this->pdepth_; } 471 472 void increase_pdepth()473 increase_pdepth() 474 { this->pdepth_++; } 475 476 void decrease_pdepth()477 decrease_pdepth() 478 { this->pdepth_--; } 479 480 private: 481 // The Go IR. 482 Gogo* gogo_; 483 // The current function being analyzed. 484 Named_object* current_function_; 485 // Return whether this is the context for a recursive function or a group of mutually 486 // recursive functions. 487 bool recursive_; 488 // The sink for this escape context. Nodes whose reference objects created 489 // outside the current function are assigned to the sink as well as nodes that 490 // the analysis loses track of. 491 Node* sink_; 492 // Used to detect nested loop scopes. 493 int loop_depth_; 494 // All the destination nodes considered in this set of analyzed functions. 495 std::set<Node*> dsts_; 496 // All the nodes that were noted as possibly not escaping in this context. 497 std::vector<Node*> noesc_; 498 // An ID given to each dst and the flows discovered through DFS of that dst. 499 // This is used to avoid infinite recursion from nodes that point to each 500 // other within the flooding phase. 501 int flood_id_; 502 // The current level of recursion within a flooded section; used to debug. 503 int pdepth_; 504 }; 505 506 #endif // !defined(GO_ESCAPE_H) 507