|
111
|
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 Level()
|
|
|
37 : value_(0), suffix_value_(0)
|
|
|
38 { }
|
|
|
39
|
|
|
40 Level(int value, int suffix)
|
|
|
41 : value_(value), suffix_value_(suffix)
|
|
|
42 { }
|
|
|
43
|
|
|
44 // Return this level's value.
|
|
|
45 int
|
|
|
46 value() const
|
|
|
47 { return this->value_; }
|
|
|
48
|
|
|
49 // Return this level's suffix value.
|
|
|
50 int
|
|
|
51 suffix_value() const
|
|
|
52 { return this->suffix_value_; }
|
|
|
53
|
|
131
|
54 // Increase the level because a node is dereferenced.
|
|
111
|
55 Level
|
|
|
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
|
|
131
|
64 // Decrease the level because a node is referenced.
|
|
111
|
65 Level
|
|
|
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
|
|
|
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
|
|
|
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
|
|
|
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:
|
|
131
|
107 // The sum of all references (-1) and indirects (+1) applied to a Node.
|
|
111
|
108 int value_;
|
|
131
|
109 // The sum of all references (-1) abd indirects (+1) applied to a copied Node.
|
|
111
|
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,
|
|
131
|
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
|
|
111
|
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 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.
|
|
|
174 Node(Named_object* no)
|
|
131
|
175 : classification_(NODE_OBJECT), state_(NULL), encoding_(ESCAPE_UNKNOWN),
|
|
|
176 child_(NULL)
|
|
111
|
177 { this->u_.object_val = no; }
|
|
|
178
|
|
|
179 Node(Expression* e)
|
|
131
|
180 : classification_(NODE_EXPRESSION), state_(NULL), encoding_(ESCAPE_UNKNOWN),
|
|
|
181 child_(NULL)
|
|
111
|
182 { this->u_.expression_val = e; }
|
|
|
183
|
|
|
184 Node(Statement* s)
|
|
131
|
185 : classification_(NODE_STATEMENT), state_(NULL), encoding_(ESCAPE_UNKNOWN),
|
|
|
186 child_(NULL)
|
|
111
|
187 { this->u_.statement_val = s; }
|
|
|
188
|
|
131
|
189 Node(Node *n)
|
|
|
190 : classification_(NODE_INDIRECT), state_(NULL), encoding_(ESCAPE_UNKNOWN),
|
|
|
191 child_(n)
|
|
|
192 {}
|
|
|
193
|
|
|
194 ~Node();
|
|
|
195
|
|
111
|
196 // Return this node's type.
|
|
|
197 Type*
|
|
|
198 type() const;
|
|
|
199
|
|
|
200 // Return this node's location.
|
|
|
201 Location
|
|
|
202 location() const;
|
|
|
203
|
|
131
|
204 // Return the location where the node's underlying object is defined.
|
|
|
205 Location
|
|
|
206 definition_location() const;
|
|
|
207
|
|
111
|
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
|
|
131
|
214 details();
|
|
111
|
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
|
|
131
|
225 encoding();
|
|
111
|
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 object() const
|
|
|
240 {
|
|
|
241 return (this->classification_ == NODE_OBJECT
|
|
|
242 ? this->u_.object_val
|
|
|
243 : NULL);
|
|
|
244 }
|
|
|
245
|
|
|
246 Expression*
|
|
|
247 expr() const
|
|
|
248 {
|
|
|
249 return (this->classification_ == NODE_EXPRESSION
|
|
|
250 ? this->u_.expression_val
|
|
|
251 : NULL);
|
|
|
252 }
|
|
|
253
|
|
|
254 Statement*
|
|
|
255 statement() const
|
|
|
256 {
|
|
|
257 return (this->classification_ == NODE_STATEMENT
|
|
|
258 ? this->u_.statement_val
|
|
|
259 : NULL);
|
|
|
260 }
|
|
|
261
|
|
131
|
262 bool
|
|
|
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*
|
|
|
270 child() const
|
|
|
271 { return this->child_; }
|
|
|
272
|
|
|
273 // Set the child node.
|
|
|
274 void
|
|
|
275 set_child(Node* n)
|
|
|
276 { this->child_ = n; }
|
|
|
277
|
|
111
|
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
|
|
131
|
288 static Node*
|
|
|
289 make_indirect_node(Node*);
|
|
|
290
|
|
111
|
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
|
|
131
|
301 // Reclaim nodes.
|
|
|
302 static void
|
|
|
303 reclaim_nodes();
|
|
|
304
|
|
111
|
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
|
|
131
|
327 // Child node, used only in indirect node, and expression node representing
|
|
|
328 // slicing an array.
|
|
|
329 Node* child_;
|
|
|
330
|
|
111
|
331 // Cache all the Nodes created via Node::make_node to make the API simpler.
|
|
145
|
332 static Unordered_map(Named_object*, Node*) objects;
|
|
|
333 static Unordered_map(Expression*, Node*) expressions;
|
|
|
334 static Unordered_map(Statement*, Node*) statements;
|
|
131
|
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;
|
|
111
|
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 gogo() const
|
|
|
387 { return this->gogo_; }
|
|
|
388
|
|
|
389 // Return the current function being analyzed.
|
|
|
390 Named_object*
|
|
|
391 current_function() const
|
|
|
392 { return this->current_function_; }
|
|
|
393
|
|
|
394 // Change the function being analyzed.
|
|
|
395 void
|
|
|
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
|
|
|
405 recursive() const
|
|
|
406 { return this->recursive_; }
|
|
|
407
|
|
|
408 // Return the special sink node for this context.
|
|
|
409 Node*
|
|
|
410 sink()
|
|
|
411 { return this->sink_; }
|
|
|
412
|
|
|
413 // Return the current loop depth.
|
|
|
414 int
|
|
|
415 loop_depth() const
|
|
|
416 { return this->loop_depth_; }
|
|
|
417
|
|
|
418 // Increase the loop depth.
|
|
|
419 void
|
|
|
420 increase_loop_depth()
|
|
|
421 { this->loop_depth_++; }
|
|
|
422
|
|
|
423 // Decrease the loop depth.
|
|
|
424 void
|
|
|
425 decrease_loop_depth()
|
|
|
426 { this->loop_depth_--; }
|
|
|
427
|
|
|
428 void
|
|
|
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*>&
|
|
|
434 dsts() const
|
|
|
435 { return this->dsts_; }
|
|
|
436
|
|
|
437 // Add a destination node.
|
|
|
438 void
|
|
|
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*>&
|
|
|
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
|
|
|
461 flood_id() const
|
|
|
462 { return this->flood_id_; }
|
|
|
463
|
|
|
464 void
|
|
|
465 increase_flood_id()
|
|
|
466 { this->flood_id_++; }
|
|
|
467
|
|
|
468 int
|
|
|
469 pdepth() const
|
|
|
470 { return this->pdepth_; }
|
|
|
471
|
|
|
472 void
|
|
|
473 increase_pdepth()
|
|
|
474 { this->pdepth_++; }
|
|
|
475
|
|
|
476 void
|
|
|
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)
|
