Branch data 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 : 5765589 : Level()
37 : 5765589 : : value_(0), suffix_value_(0)
38 : : { }
39 : :
40 : 36877478 : Level(int value, int suffix)
41 : : : value_(value), suffix_value_(suffix)
42 : : { }
43 : :
44 : : // Return this level's value.
45 : : int
46 : 29400693 : value() const
47 : 29400693 : { return this->value_; }
48 : :
49 : : // Return this level's suffix value.
50 : : int
51 : 29388858 : suffix_value() const
52 : 17651 : { return this->suffix_value_; }
53 : :
54 : : // Increase the level because a node is dereferenced.
55 : : Level
56 : 9180048 : increase() const
57 : : {
58 : 8838285 : if (this->value_ <= MIN_LEVEL)
59 : : return Level(MIN_LEVEL, 0);
60 : :
61 : 6120360 : return Level(this->value_ + 1, this->suffix_value_ + 1);
62 : : }
63 : :
64 : : // Decrease the level because a node is referenced.
65 : : Level
66 : 2930635 : decrease() const
67 : : {
68 : 2930635 : if (this->value_ <= MIN_LEVEL)
69 : : return Level(MIN_LEVEL, 0);
70 : :
71 : 2315182 : return Level(this->value_ - 1, this->suffix_value_ - 1);
72 : : }
73 : :
74 : : // Model a node being copied.
75 : : Level
76 : 36877478 : copy() const
77 : : {
78 : 36877478 : 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 : 29371207 : min(const Level& l) const
84 : : {
85 : 29371207 : return Level(std::min(this->value_, l.value()),
86 : 29371207 : std::min(this->suffix_value_, l.suffix_value()));
87 : : }
88 : :
89 : : // Compare two levels for equality.
90 : : bool
91 : 29371207 : operator==(const Level& l) const
92 : : {
93 : 29371207 : return (this->value_ == l.value()
94 : 29371207 : && this->suffix_value_ == l.suffix_value());
95 : : }
96 : :
97 : : // Create a level from an integer value.
98 : : static Level
99 : 1081271 : From(int i)
100 : : {
101 : 1081271 : if (i <= MIN_LEVEL)
102 : : return Level(MIN_LEVEL, 0);
103 : 1081271 : 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 : 5765589 : Escape_state()
154 : 5765589 : : 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 : 9156237 : Node(Expression* e)
180 : 9156237 : : classification_(NODE_EXPRESSION), state_(NULL), encoding_(ESCAPE_UNKNOWN),
181 : 9156237 : child_(NULL)
182 : 9156237 : { 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 : 94531047 : object() const
240 : : {
241 : 94531047 : return (this->classification_ == NODE_OBJECT
242 : 80653038 : ? this->u_.object_val
243 : : : NULL);
244 : : }
245 : :
246 : : Expression*
247 : 305576804 : expr() const
248 : : {
249 : 4073265 : return (this->classification_ == NODE_EXPRESSION
250 : 301503539 : ? this->u_.expression_val
251 : : : NULL);
252 : : }
253 : :
254 : : Statement*
255 : 970049 : statement() const
256 : : {
257 : 970049 : return (this->classification_ == NODE_STATEMENT
258 : 970049 : ? this->u_.statement_val
259 : : : 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 : 1271307 : child() const
271 : 1271307 : { 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 : 58208877 : gogo() const
387 : 58208877 : { return this->gogo_; }
388 : :
389 : : // Return the current function being analyzed.
390 : : Named_object*
391 : 5358001 : current_function() const
392 : 5358001 : { 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 : 48120619 : flood_id() const
462 : 48120619 : { return this->flood_id_; }
463 : :
464 : : void
465 : 1081271 : increase_flood_id()
466 : 1081271 : { this->flood_id_++; }
467 : :
468 : : int
469 : 0 : pdepth() const
470 : 0 : { return this->pdepth_; }
471 : :
472 : : void
473 : 36877478 : increase_pdepth()
474 : 36877478 : { this->pdepth_++; }
475 : :
476 : : void
477 : 36847992 : decrease_pdepth()
478 : 36847992 : { 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)
|
