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
54 // Increase the level because a node is dereferenced.
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
64 // Decrease the level because a node is referenced.
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:
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 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)
175 : classification_(NODE_OBJECT), state_(NULL), encoding_(ESCAPE_UNKNOWN),
176 child_(NULL)
177 { this->u_.object_val = no; }
178
179 Node(Expression* e)
180 : classification_(NODE_EXPRESSION), state_(NULL), encoding_(ESCAPE_UNKNOWN),
181 child_(NULL)
182 { this->u_.expression_val = e; }
183
184 Node(Statement* s)
185 : classification_(NODE_STATEMENT), state_(NULL), encoding_(ESCAPE_UNKNOWN),
186 child_(NULL)
187 { this->u_.statement_val = s; }
188
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*
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
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
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 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)