1 // escape.h -- Go escape analysis (based on Go compiler algorithm).
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.
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;
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.
37 : value_(0), suffix_value_(0)
40 Level(int value
, int suffix
)
41 : value_(value
), suffix_value_(suffix
)
44 // Return this level's value.
47 { return this->value_
; }
49 // Return this level's suffix value.
52 { return this->suffix_value_
; }
54 // Increase the level because a node is referenced.
58 if (this->value_
<= MIN_LEVEL
)
59 return Level(MIN_LEVEL
, 0);
61 return Level(this->value_
+ 1, this->suffix_value_
+ 1);
64 // Decrease the level because a node is dereferenced.
68 if (this->value_
<= MIN_LEVEL
)
69 return Level(MIN_LEVEL
, 0);
71 return Level(this->value_
- 1, this->suffix_value_
- 1);
74 // Model a node being copied.
78 return Level(this->value_
, std::max(this->suffix_value_
, 0));
81 // Return a level with the minimum values of this level and l.
83 min(const Level
& l
) const
85 return Level(std::min(this->value_
, l
.value()),
86 std::min(this->suffix_value_
, l
.suffix_value()));
89 // Compare two levels for equality.
91 operator==(const Level
& l
) const
93 return (this->value_
== l
.value()
94 && this->suffix_value_
== l
.suffix_value());
97 // Create a level from an integer value.
102 return Level(MIN_LEVEL
, 0);
107 // The sum of all indirects (-1) and references (+1) applied to a Node.
109 // The sum of all indirects (-1) abd references (+1) applied to a copied Node.
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).
120 // This classification represents type of nodes in the Go parse tree that are
121 // interesting during the analysis.
122 enum Node_classification
129 // The state necessary to keep track of how a node escapes.
132 // The current function.
134 // A list of source nodes that flow into this node.
135 std::set
<Node
*> flows
;
136 // If the node is a function call, the list of nodes returned.
137 std::vector
<Node
*> retvals
;
138 // The node's loop depth.
140 // There is an extra loop depth in the flood phase used to account for
141 // variables referenced across closures. This is the maximum value of the
142 // extra loop depth seen during the flood that touches this node.
143 int max_extra_loop_depth
;
146 // An ID given to a node when it is encountered as a flow from the current
147 // dst node. This is used to avoid infinite recursion of cyclic nodes.
151 : fn(NULL
), loop_depth(0), max_extra_loop_depth(0), flood_id(0)
155 // Note: values in this enum appear in export data, and therefore MUST NOT
157 enum Escapement_encoding
160 // Does not escape to heap, result, or parameters.
162 // Is returned or reachable from a return statement.
164 // Allocated in an inner loop, assigned to an outer loop,
165 // which allows construction of non-escaping but arbitrarily large linked
166 // data structures (i.e., not eligible for allocation in a fixed-size stack
169 // Reachable from the heap.
171 // By construction will not escape.
175 // Multiple constructors for each classification.
176 Node(Named_object
* no
)
177 : classification_(NODE_OBJECT
), state_(NULL
), encoding_(ESCAPE_UNKNOWN
)
178 { this->u_
.object_val
= no
; }
181 : classification_(NODE_EXPRESSION
), state_(NULL
), encoding_(ESCAPE_UNKNOWN
)
182 { this->u_
.expression_val
= e
; }
185 : classification_(NODE_STATEMENT
), state_(NULL
), encoding_(ESCAPE_UNKNOWN
)
186 { this->u_
.statement_val
= s
; }
188 // Return this node's type.
192 // Return this node's location.
196 // Return this node's AST formatted string.
198 ast_format(Gogo
*) const;
200 // Return this node's detailed format string.
207 // Return this node's escape state.
209 state(Escape_context
* context
, Named_object
* fn
);
211 // Return this node's escape encoding.
214 { return this->encoding_
; }
216 // Set the node's escape encoding.
218 set_encoding(int enc
);
221 is_big(Escape_context
*) const;
226 // Methods to return the underlying value in the Node union.
230 return (this->classification_
== NODE_OBJECT
231 ? this->u_
.object_val
238 return (this->classification_
== NODE_EXPRESSION
239 ? this->u_
.expression_val
246 return (this->classification_
== NODE_STATEMENT
247 ? this->u_
.statement_val
251 // Static creation methods for each value supported in the union.
253 make_node(Named_object
*);
256 make_node(Expression
*);
259 make_node(Statement
*);
261 // Return the maximum of an existing escape encoding E and a new
264 max_encoding(int e
, int etype
);
266 // Return a modified encoding for an input parameter that flows into an
269 note_inout_flows(int e
, int index
, Level level
);
272 // The classification of this Node.
273 Node_classification classification_
;
278 Named_object
* object_val
;
279 // If NODE_EXPRESSION.
280 Expression
* expression_val
;
281 // If NODE_STATEMENT.
282 Statement
* statement_val
;
284 // The node's escape state.
285 Escape_state
* state_
;
286 // The node's escape encoding.
288 // | Return Encoding: (width - ESCAPE_RETURN_BITS) |
289 // | Content Escapes bit: 1 |
290 // | Escapement_encoding: ESCAPE_BITS |
293 // Cache all the Nodes created via Node::make_node to make the API simpler.
294 static std::map
<Named_object
*, Node
*> objects
;
295 static std::map
<Expression
*, Node
*> expressions
;
296 static std::map
<Statement
*, Node
*> statements
;
299 // The amount of bits used for the escapement encoding.
300 static const int ESCAPE_BITS
= 3;
302 // Mask used to extract encoding.
303 static const int ESCAPE_MASK
= (1 << ESCAPE_BITS
) - 1;
305 // Value obtained by indirect of parameter escapes to heap.
306 static const int ESCAPE_CONTENT_ESCAPES
= 1 << ESCAPE_BITS
;
308 // The amount of bits used in encoding of return values.
309 static const int ESCAPE_RETURN_BITS
= ESCAPE_BITS
+ 1;
311 // For each output, the number of bits for a tag.
312 static const int ESCAPE_BITS_PER_OUTPUT_IN_TAG
= 3;
314 // The bit max to extract a single tag.
315 static const int ESCAPE_BITS_MASK_FOR_TAG
= (1 << ESCAPE_BITS_PER_OUTPUT_IN_TAG
) - 1;
317 // The largest level that can be stored in a tag.
318 static const int ESCAPE_MAX_ENCODED_LEVEL
= ESCAPE_BITS_MASK_FOR_TAG
- 1;
320 // A helper for converting escape notes from encoded integers to a
321 // textual format and vice-versa.
326 // Return the string representation of an escapement encoding.
328 make_tag(int encoding
);
330 // Return the escapement encoding for a string tag.
332 parse_tag(std::string
* tag
);
335 // The escape context for a set of functions being analyzed.
340 Escape_context(Gogo
* gogo
, bool recursive
);
345 { return this->gogo_
; }
347 // Return the current function being analyzed.
349 current_function() const
350 { return this->current_function_
; }
352 // Change the function being analyzed.
354 set_current_function(Named_object
* fn
)
355 { this->current_function_
= fn
; }
357 // Return the name of the current function.
359 current_function_name() const;
361 // Return true if this is the context for a mutually recursive set of functions.
364 { return this->recursive_
; }
366 // Return the special sink node for this context.
369 { return this->sink_
; }
371 // Return the current loop depth.
374 { return this->loop_depth_
; }
376 // Increase the loop depth.
378 increase_loop_depth()
379 { this->loop_depth_
++; }
381 // Decrease the loop depth.
383 decrease_loop_depth()
384 { this->loop_depth_
--; }
387 set_loop_depth(int depth
)
388 { this->loop_depth_
= depth
; }
390 // Return the destination nodes encountered in this context.
391 const std::set
<Node
*>&
393 { return this->dsts_
; }
395 // Add a destination node.
398 { this->dsts_
.insert(dst
); }
400 // Return the nodes initially marked as non-escaping before flooding.
401 const std::vector
<Node
*>&
402 non_escaping_nodes() const
403 { return this->noesc_
; }
405 // Initialize the dummy return values for this Node N using the results
408 init_retvals(Node
* n
, Function_type
* fntype
);
410 // Return the indirection of Node N.
412 add_dereference(Node
* n
);
414 // Keep track of possibly non-escaping node N.
420 { return this->flood_id_
; }
424 { this->flood_id_
++; }
428 { return this->pdepth_
; }
441 // The current function being analyzed.
442 Named_object
* current_function_
;
443 // Return whether this is the context for a recursive function or a group of mutually
444 // recursive functions.
446 // The sink for this escape context. Nodes whose reference objects created
447 // outside the current function are assigned to the sink as well as nodes that
448 // the analysis loses track of.
450 // Used to detect nested loop scopes.
452 // All the destination nodes considered in this set of analyzed functions.
453 std::set
<Node
*> dsts_
;
454 // All the nodes that were noted as possibly not escaping in this context.
455 std::vector
<Node
*> noesc_
;
456 // An ID given to each dst and the flows discovered through DFS of that dst.
457 // This is used to avoid infinite recursion from nodes that point to each
458 // other within the flooding phase.
460 // The current level of recursion within a flooded section; used to debug.
464 #endif // !defined(GO_ESCAPE_H)