Line data Source code
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:
36 5765583 : Level()
37 5765583 : : value_(0), suffix_value_(0)
38 : { }
39 :
40 36782100 : Level(int value, int suffix)
41 : : value_(value), suffix_value_(suffix)
42 : { }
43 :
44 : // Return this level's value.
45 : int
46 29347539 : value() const
47 29347539 : { return this->value_; }
48 :
49 : // Return this level's suffix value.
50 : int
51 29335707 : suffix_value() const
52 17642 : { return this->suffix_value_; }
53 :
54 : // Increase the level because a node is dereferenced.
55 : Level
56 9159492 : increase() const
57 : {
58 8811815 : if (this->value_ <= MIN_LEVEL)
59 : return Level(MIN_LEVEL, 0);
60 :
61 6100188 : return Level(this->value_ + 1, this->suffix_value_ + 1);
62 : }
63 :
64 : // Decrease the level because a node is referenced.
65 : Level
66 2958077 : decrease() const
67 : {
68 2958077 : if (this->value_ <= MIN_LEVEL)
69 : return Level(MIN_LEVEL, 0);
70 :
71 2342659 : return Level(this->value_ - 1, this->suffix_value_ - 1);
72 : }
73 :
74 : // Model a node being copied.
75 : Level
76 36782100 : copy() const
77 : {
78 36782100 : 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
83 29318065 : min(const Level& l) const
84 : {
85 29318065 : return Level(std::min(this->value_, l.value()),
86 29318065 : std::min(this->suffix_value_, l.suffix_value()));
87 : }
88 :
89 : // Compare two levels for equality.
90 : bool
91 29318065 : operator==(const Level& l) const
92 : {
93 29318065 : return (this->value_ == l.value()
94 29318065 : && this->suffix_value_ == l.suffix_value());
95 : }
96 :
97 : // Create a level from an integer value.
98 : static Level
99 1081273 : From(int i)
100 : {
101 1081273 : if (i <= MIN_LEVEL)
102 : return Level(MIN_LEVEL, 0);
103 1081273 : 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 :
153 5765583 : Escape_state()
154 5765583 : : 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.
174 2673800 : Node(Named_object* no)
175 2673800 : : classification_(NODE_OBJECT), state_(NULL), encoding_(ESCAPE_UNKNOWN),
176 2673800 : child_(NULL)
177 2673800 : { this->u_.object_val = no; }
178 :
179 9156239 : Node(Expression* e)
180 9156239 : : classification_(NODE_EXPRESSION), state_(NULL), encoding_(ESCAPE_UNKNOWN),
181 9156239 : child_(NULL)
182 9156239 : { this->u_.expression_val = e; }
183 :
184 422696 : Node(Statement* s)
185 422696 : : classification_(NODE_STATEMENT), state_(NULL), encoding_(ESCAPE_UNKNOWN),
186 422696 : child_(NULL)
187 422696 : { this->u_.statement_val = s; }
188 :
189 121663 : Node(Node *n)
190 121663 : : classification_(NODE_INDIRECT), state_(NULL), encoding_(ESCAPE_UNKNOWN),
191 121663 : 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*
239 94418937 : object() const
240 : {
241 94418937 : return (this->classification_ == NODE_OBJECT
242 80540912 : ? this->u_.object_val
243 36608342 : : NULL);
244 : }
245 :
246 : Expression*
247 305019366 : expr() const
248 : {
249 4073259 : return (this->classification_ == NODE_EXPRESSION
250 300946107 : ? this->u_.expression_val
251 189002742 : : NULL);
252 : }
253 :
254 : Statement*
255 970049 : statement() const
256 : {
257 970049 : return (this->classification_ == NODE_STATEMENT
258 970049 : ? this->u_.statement_val
259 959103 : : NULL);
260 : }
261 :
262 : bool
263 4175321 : is_indirect() const
264 4175321 : { 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*
270 1277221 : child() const
271 1277221 : { return this->child_; }
272 :
273 : // Set the child node.
274 : void
275 12229 : set_child(Node* n)
276 12229 : { 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*
386 58113508 : gogo() const
387 58113508 : { return this->gogo_; }
388 :
389 : // Return the current function being analyzed.
390 : Named_object*
391 5357995 : current_function() const
392 5357995 : { return this->current_function_; }
393 :
394 : // Change the function being analyzed.
395 : void
396 1384539 : set_current_function(Named_object* fn)
397 1384539 : { 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
405 142344 : recursive() const
406 142344 : { return this->recursive_; }
407 :
408 : // Return the special sink node for this context.
409 : Node*
410 1347916 : sink()
411 1347916 : { return this->sink_; }
412 :
413 : // Return the current loop depth.
414 : int
415 580009 : loop_depth() const
416 580009 : { return this->loop_depth_; }
417 :
418 : // Increase the loop depth.
419 : void
420 53500 : increase_loop_depth()
421 53500 : { this->loop_depth_++; }
422 :
423 : // Decrease the loop depth.
424 : void
425 53271 : decrease_loop_depth()
426 53271 : { this->loop_depth_--; }
427 :
428 : void
429 373224 : set_loop_depth(int depth)
430 373224 : { this->loop_depth_ = depth; }
431 :
432 : // Return the destination nodes encountered in this context.
433 : const std::set<Node*>&
434 : dsts() const
435 : { return this->dsts_; }
436 :
437 : // Add a destination node.
438 : void
439 1038975 : add_dst(Node* dst)
440 1038975 : { this->dsts_.insert(dst); }
441 :
442 : // Return the nodes initially marked as non-escaping before flooding.
443 : const std::vector<Node*>&
444 0 : non_escaping_nodes() const
445 0 : { 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
461 48067761 : flood_id() const
462 48067761 : { return this->flood_id_; }
463 :
464 : void
465 1081273 : increase_flood_id()
466 1081273 : { this->flood_id_++; }
467 :
468 : int
469 0 : pdepth() const
470 0 : { return this->pdepth_; }
471 :
472 : void
473 36782100 : increase_pdepth()
474 36782100 : { this->pdepth_++; }
475 :
476 : void
477 36752626 : decrease_pdepth()
478 36752626 : { 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)
|
