LCOV - code coverage report
Current view: top level - gcc/go/gofrontend - escape.h (source / functions) Hit Total Coverage
Test: gcc.info Lines: 88 92 95.7 %
Date: 2020-03-28 11:57:23 Functions: 0 0 -
Legend: Lines: hit not hit | Branches: + taken - not taken # not executed Branches: 0 0 -

           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                 :    4706480 :   Level()
      37                 :    4706480 :     : value_(0), suffix_value_(0)
      38                 :            :   { }
      39                 :            : 
      40                 :   20801700 :   Level(int value, int suffix)
      41                 :            :     : value_(value), suffix_value_(suffix)
      42                 :            :   { }
      43                 :            : 
      44                 :            :   // Return this level's value.
      45                 :            :   int
      46                 :   30571700 :   value() const
      47                 :   12210000 :   { return this->value_; }
      48                 :            : 
      49                 :            :   // Return this level's suffix value.
      50                 :            :   int
      51                 :   13885700 :   suffix_value() const
      52                 :    4246250 :   { return this->suffix_value_; }
      53                 :            : 
      54                 :            :   // Increase the level because a node is dereferenced.
      55                 :            :   Level
      56                 :    2803410 :   increase() const
      57                 :            :   {
      58                 :    2630450 :     if (this->value_ <= MIN_LEVEL)
      59                 :    2803410 :       return Level(MIN_LEVEL, 0);
      60                 :            : 
      61                 :    2781590 :     return Level(this->value_ + 1, this->suffix_value_ + 1);
      62                 :            :   }
      63                 :            : 
      64                 :            :   // Decrease the level because a node is referenced.
      65                 :            :   Level
      66                 :     811843 :   decrease() const
      67                 :            :   {
      68                 :     811843 :     if (this->value_ <= MIN_LEVEL)
      69                 :     811843 :       return Level(MIN_LEVEL, 0);
      70                 :            : 
      71                 :     756852 :     return Level(this->value_ - 1, this->suffix_value_ - 1);
      72                 :            :   }
      73                 :            : 
      74                 :            :   // Model a node being copied.
      75                 :            :   Level
      76                 :   10426500 :   copy() const
      77                 :            :   {
      78                 :   10734800 :     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                 :    5931110 :   min(const Level& l) const
      84                 :            :   {
      85                 :   17793300 :     return Level(std::min(this->value_, l.value()),
      86                 :    8561170 :                  std::min(this->suffix_value_, l.suffix_value()));
      87                 :            :   }
      88                 :            : 
      89                 :            :   // Compare two levels for equality.
      90                 :            :   bool
      91                 :    5931110 :   operator==(const Level& l) const
      92                 :            :   {
      93                 :    5931110 :     return (this->value_ == l.value()
      94                 :    5931110 :             && this->suffix_value_ == l.suffix_value());
      95                 :            :   }
      96                 :            : 
      97                 :            :   // Create a level from an integer value.
      98                 :            :   static Level
      99                 :     905653 :   From(int i)
     100                 :            :   {
     101                 :     905653 :     if (i <= MIN_LEVEL)
     102                 :            :       return Level(MIN_LEVEL, 0);
     103                 :     905653 :     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                 :    4706480 :     Escape_state()
     154                 :    4706480 :       : 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                 :    2094640 :   Node(Named_object* no)
     175                 :    2094640 :     : classification_(NODE_OBJECT), state_(NULL), encoding_(ESCAPE_UNKNOWN),
     176                 :    2094640 :       child_(NULL)
     177                 :    2094640 :   { this->u_.object_val = no; }
     178                 :            : 
     179                 :    7666560 :   Node(Expression* e)
     180                 :    7666560 :     : classification_(NODE_EXPRESSION), state_(NULL), encoding_(ESCAPE_UNKNOWN),
     181                 :    7666560 :       child_(NULL)
     182                 :    7666560 :   { this->u_.expression_val = e; }
     183                 :            : 
     184                 :     312964 :   Node(Statement* s)
     185                 :     312964 :     : classification_(NODE_STATEMENT), state_(NULL), encoding_(ESCAPE_UNKNOWN),
     186                 :     312964 :       child_(NULL)
     187                 :     312964 :   { this->u_.statement_val = s; }
     188                 :            : 
     189                 :     103131 :   Node(Node *n)
     190                 :     103131 :     : classification_(NODE_INDIRECT), state_(NULL), encoding_(ESCAPE_UNKNOWN),
     191                 :     103131 :       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                 :   48827400 :   object() const
     240                 :            :   {
     241                 :    1249000 :     return (this->classification_ == NODE_OBJECT
     242                 :   35448500 :             ? this->u_.object_val
     243                 :            :             : NULL);
     244                 :            :   }
     245                 :            : 
     246                 :            :   Expression*
     247                 :  226909000 :   expr() const
     248                 :            :   {
     249                 :   81286000 :     return (this->classification_ == NODE_EXPRESSION
     250                 :  121782000 :             ? this->u_.expression_val
     251                 :            :             : NULL);
     252                 :            :   }
     253                 :            : 
     254                 :            :   Statement*
     255                 :    1989540 :   statement() const
     256                 :            :   {
     257                 :     742866 :     return (this->classification_ == NODE_STATEMENT
     258                 :     751426 :             ? this->u_.statement_val
     259                 :            :             : NULL);
     260                 :            :   }
     261                 :            : 
     262                 :            :   bool
     263                 :    9794710 :   is_indirect() const
     264                 :    9794710 :   { 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                 :     973864 :   child() const
     271                 :     960677 :   { return this->child_; }
     272                 :            : 
     273                 :            :   // Set the child node.
     274                 :            :   void
     275                 :       8698 :   set_child(Node* n)
     276                 :       8698 :   { 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                 :   28159800 :   gogo() const
     387                 :   28159800 :   { return this->gogo_; }
     388                 :            : 
     389                 :            :   // Return the current function being analyzed.
     390                 :            :   Named_object*
     391                 :    4367160 :   current_function() const
     392                 :    4367160 :   { return this->current_function_; }
     393                 :            : 
     394                 :            :   // Change the function being analyzed.
     395                 :            :   void
     396                 :    1042980 :   set_current_function(Named_object* fn)
     397                 :    1042980 :   { 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                 :     116660 :   recursive() const
     406                 :     116660 :   { return this->recursive_; }
     407                 :            : 
     408                 :            :   // Return the special sink node for this context.
     409                 :            :   Node*
     410                 :    1102500 :   sink()
     411                 :    1102500 :   { return this->sink_; }
     412                 :            : 
     413                 :            :   // Return the current loop depth.
     414                 :            :   int
     415                 :     463409 :   loop_depth() const
     416                 :     463409 :   { return this->loop_depth_; }
     417                 :            : 
     418                 :            :   // Increase the loop depth.
     419                 :            :   void
     420                 :      46056 :   increase_loop_depth()
     421                 :      46056 :   { this->loop_depth_++; }
     422                 :            : 
     423                 :            :   // Decrease the loop depth.
     424                 :            :   void
     425                 :      45817 :   decrease_loop_depth()
     426                 :      45817 :   { this->loop_depth_--; }
     427                 :            : 
     428                 :            :   void
     429                 :     298676 :   set_loop_depth(int depth)
     430                 :     298676 :   { this->loop_depth_ = depth; }
     431                 :            : 
     432                 :            :   // Return the destination nodes encountered in this context.
     433                 :            :   const std::set<Node*>&
     434                 :    1030420 :   dsts() const
     435                 :    1030420 :   { return this->dsts_; }
     436                 :            : 
     437                 :            :   // Add a destination node.
     438                 :            :   void
     439                 :     867034 :   add_dst(Node* dst)
     440                 :     867034 :   { 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                 :   24409500 :   flood_id() const
     462                 :   24409500 :   { return this->flood_id_; }
     463                 :            : 
     464                 :            :   void
     465                 :     905653 :   increase_flood_id()
     466                 :     905653 :   { this->flood_id_++; }
     467                 :            : 
     468                 :            :   int
     469                 :          0 :   pdepth() const
     470                 :          0 :   { return this->pdepth_; }
     471                 :            : 
     472                 :            :   void
     473                 :   10426500 :   increase_pdepth()
     474                 :   10426500 :   { this->pdepth_++; }
     475                 :            : 
     476                 :            :   void
     477                 :   10401800 :   decrease_pdepth()
     478                 :   10401800 :   { 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)

Generated by: LCOV version 1.0

LCOV profile is generated on x86_64 machine using following configure options: configure --disable-bootstrap --enable-coverage=opt --enable-languages=c,c++,fortran,go,jit,lto --enable-host-shared. GCC test suite is run with the built compiler.