1 /*
   2  * Copyright 2005-2008 Sun Microsystems, Inc.  All Rights Reserved.
   3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   4  *
   5  * This code is free software; you can redistribute it and/or modify it
   6  * under the terms of the GNU General Public License version 2 only, as
   7  * published by the Free Software Foundation.
   8  *
   9  * This code is distributed in the hope that it will be useful, but WITHOUT
  10  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  11  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  12  * version 2 for more details (a copy is included in the LICENSE file that
  13  * accompanied this code).
  14  *
  15  * You should have received a copy of the GNU General Public License version
  16  * 2 along with this work; if not, write to the Free Software Foundation,
  17  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  18  *
  19  * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
  20  * CA 95054 USA or visit www.sun.com if you need additional information or
  21  * have any questions.
  22  *
  23  */
  24 
  25 //
  26 // Adaptation for C2 of the escape analysis algorithm described in:
  27 //
  28 // [Choi99] Jong-Deok Shoi, Manish Gupta, Mauricio Seffano,
  29 //          Vugranam C. Sreedhar, Sam Midkiff,
  30 //          "Escape Analysis for Java", Procedings of ACM SIGPLAN
  31 //          OOPSLA  Conference, November 1, 1999
  32 //
  33 // The flow-insensitive analysis described in the paper has been implemented.
  34 //
  35 // The analysis requires construction of a "connection graph" (CG) for
  36 // the method being analyzed.  The nodes of the connection graph are:
  37 //
  38 //     -  Java objects (JO)
  39 //     -  Local variables (LV)
  40 //     -  Fields of an object (OF),  these also include array elements
  41 //
  42 // The CG contains 3 types of edges:
  43 //
  44 //   -  PointsTo  (-P>)    {LV, OF} to JO
  45 //   -  Deferred  (-D>)    from {LV, OF} to {LV, OF}
  46 //   -  Field     (-F>)    from JO to OF
  47 //
  48 // The following  utility functions is used by the algorithm:
  49 //
  50 //   PointsTo(n) - n is any CG node, it returns the set of JO that n could
  51 //                 point to.
  52 //
  53 // The algorithm describes how to construct the connection graph
  54 // in the following 4 cases:
  55 //
  56 //          Case                  Edges Created
  57 //
  58 // (1)   p   = new T()              LV -P> JO
  59 // (2)   p   = q                    LV -D> LV
  60 // (3)   p.f = q                    JO -F> OF,  OF -D> LV
  61 // (4)   p   = q.f                  JO -F> OF,  LV -D> OF
  62 //
  63 // In all these cases, p and q are local variables.  For static field
  64 // references, we can construct a local variable containing a reference
  65 // to the static memory.
  66 //
  67 // C2 does not have local variables.  However for the purposes of constructing
  68 // the connection graph, the following IR nodes are treated as local variables:
  69 //     Phi    (pointer values)
  70 //     LoadP
  71 //     Proj#5 (value returned from callnodes including allocations)
  72 //     CheckCastPP, CastPP
  73 //
  74 // The LoadP, Proj and CheckCastPP behave like variables assigned to only once.
  75 // Only a Phi can have multiple assignments.  Each input to a Phi is treated
  76 // as an assignment to it.
  77 //
  78 // The following node types are JavaObject:
  79 //
  80 //     top()
  81 //     Allocate
  82 //     AllocateArray
  83 //     Parm  (for incoming arguments)
  84 //     CastX2P ("unsafe" operations)
  85 //     CreateEx
  86 //     ConP
  87 //     LoadKlass
  88 //     ThreadLocal
  89 //
  90 // AddP nodes are fields.
  91 //
  92 // After building the graph, a pass is made over the nodes, deleting deferred
  93 // nodes and copying the edges from the target of the deferred edge to the
  94 // source.  This results in a graph with no deferred edges, only:
  95 //
  96 //    LV -P> JO
  97 //    OF -P> JO (the object whose oop is stored in the field)
  98 //    JO -F> OF
  99 //
 100 // Then, for each node which is GlobalEscape, anything it could point to
 101 // is marked GlobalEscape.  Finally, for any node marked ArgEscape, anything
 102 // it could point to is marked ArgEscape.
 103 //
 104 
 105 class  Compile;
 106 class  Node;
 107 class  CallNode;
 108 class  PhiNode;
 109 class  PhaseTransform;
 110 class  Type;
 111 class  TypePtr;
 112 class  VectorSet;
 113 
 114 class PointsToNode {
 115 friend class ConnectionGraph;
 116 public:
 117   typedef enum {
 118     UnknownType = 0,
 119     JavaObject  = 1,
 120     LocalVar    = 2,
 121     Field       = 3
 122   } NodeType;
 123 
 124   typedef enum {
 125     UnknownEscape = 0,
 126     NoEscape      = 1, // A scalar replaceable object with unique type.
 127     ArgEscape     = 2, // An object passed as argument or referenced by
 128                        // argument (and not globally escape during call).
 129     GlobalEscape  = 3  // An object escapes the method and thread.
 130   } EscapeState;
 131 
 132   typedef enum {
 133     UnknownEdge   = 0,
 134     PointsToEdge  = 1,
 135     DeferredEdge  = 2,
 136     FieldEdge     = 3
 137   } EdgeType;
 138 
 139 private:
 140   enum {
 141     EdgeMask = 3,
 142     EdgeShift = 2,
 143 
 144     INITIAL_EDGE_COUNT = 4
 145   };
 146 
 147   NodeType             _type;
 148   EscapeState          _escape;
 149   GrowableArray<uint>* _edges;   // outgoing edges
 150 
 151 public:
 152   Node* _node;              // Ideal node corresponding to this PointsTo node.
 153   int   _offset;            // Object fields offsets.
 154   bool  _scalar_replaceable;// Not escaped object could be replaced with scalar
 155   bool  _hidden_alias;      // This node is an argument to a function.
 156                             // which may return it creating a hidden alias.
 157 
 158   PointsToNode():
 159     _type(UnknownType),
 160     _escape(UnknownEscape),
 161     _edges(NULL),
 162     _node(NULL),
 163     _offset(-1),
 164     _scalar_replaceable(true),
 165     _hidden_alias(false) {}
 166 
 167 
 168   EscapeState escape_state() const { return _escape; }
 169   NodeType node_type() const { return _type;}
 170   int offset() { return _offset;}
 171 
 172   void set_offset(int offs) { _offset = offs;}
 173   void set_escape_state(EscapeState state) { _escape = state; }
 174   void set_node_type(NodeType ntype) {
 175     assert(_type == UnknownType || _type == ntype, "Can't change node type");
 176     _type = ntype;
 177   }
 178 
 179   // count of outgoing edges
 180   uint edge_count() const { return (_edges == NULL) ? 0 : _edges->length(); }
 181 
 182   // node index of target of outgoing edge "e"
 183   uint edge_target(uint e) const {
 184     assert(_edges != NULL, "valid edge index");
 185     return (_edges->at(e) >> EdgeShift);
 186   }
 187   // type of outgoing edge "e"
 188   EdgeType edge_type(uint e) const {
 189     assert(_edges != NULL, "valid edge index");
 190     return (EdgeType) (_edges->at(e) & EdgeMask);
 191   }
 192 
 193   // add a edge of the specified type pointing to the specified target
 194   void add_edge(uint targIdx, EdgeType et);
 195 
 196   // remove an edge of the specified type pointing to the specified target
 197   void remove_edge(uint targIdx, EdgeType et);
 198 
 199 #ifndef PRODUCT
 200   void dump(bool print_state=true) const;
 201 #endif
 202 
 203 };
 204 
 205 class ConnectionGraph: public ResourceObj {
 206 private:
 207   GrowableArray<PointsToNode>  _nodes; // Connection graph nodes indexed
 208                                        // by ideal node index.
 209 
 210   Unique_Node_List  _delayed_worklist; // Nodes to be processed before
 211                                        // the call build_connection_graph().
 212 
 213   VectorSet                _processed; // Records which nodes have been
 214                                        // processed.
 215 
 216   bool                    _collecting; // Indicates whether escape information
 217                                        // is still being collected. If false,
 218                                        // no new nodes will be processed.
 219 
 220   uint                _phantom_object; // Index of globally escaping object
 221                                        // that pointer values loaded from
 222                                        // a field which has not been set
 223                                        // are assumed to point to.
 224   uint                      _oop_null; // ConP(#NULL)
 225   uint                     _noop_null; // ConN(#NULL)
 226 
 227   Compile *                  _compile; // Compile object for current compilation
 228 
 229   // Address of an element in _nodes.  Used when the element is to be modified
 230   PointsToNode *ptnode_adr(uint idx) const {
 231     // There should be no new ideal nodes during ConnectionGraph build,
 232     // growableArray::adr_at() will throw assert otherwise.
 233     return _nodes.adr_at(idx);
 234   }
 235   uint nodes_size() const { return _nodes.length(); }
 236 
 237   // Add node to ConnectionGraph.
 238   void add_node(Node *n, PointsToNode::NodeType nt, PointsToNode::EscapeState es, bool done);
 239 
 240   // offset of a field reference
 241   int address_offset(Node* adr, PhaseTransform *phase);
 242 
 243   // compute the escape state for arguments to a call
 244   void process_call_arguments(CallNode *call, PhaseTransform *phase);
 245 
 246   // compute the escape state for the return value of a call
 247   void process_call_result(ProjNode *resproj, PhaseTransform *phase);
 248 
 249   // Populate Connection Graph with Ideal nodes.
 250   void record_for_escape_analysis(Node *n, PhaseTransform *phase);
 251 
 252   // Build Connection Graph and set nodes escape state.
 253   void build_connection_graph(Node *n, PhaseTransform *phase);
 254 
 255   // walk the connection graph starting at the node corresponding to "n" and
 256   // add the index of everything it could point to, to "ptset".  This may cause
 257   // Phi's encountered to get (re)processed  (which requires "phase".)
 258   void PointsTo(VectorSet &ptset, Node * n, PhaseTransform *phase);
 259 
 260   //  Edge manipulation.  The "from_i" and "to_i" arguments are the
 261   //  node indices of the source and destination of the edge
 262   void add_pointsto_edge(uint from_i, uint to_i);
 263   void add_deferred_edge(uint from_i, uint to_i);
 264   void add_field_edge(uint from_i, uint to_i, int offs);
 265 
 266 
 267   // Add an edge to node given by "to_i" from any field of adr_i whose offset
 268   // matches "offset"  A deferred edge is added if to_i is a LocalVar, and
 269   // a pointsto edge is added if it is a JavaObject
 270   void add_edge_from_fields(uint adr, uint to_i, int offs);
 271 
 272   // Add a deferred  edge from node given by "from_i" to any field
 273   // of adr_i whose offset matches "offset"
 274   void add_deferred_edge_to_fields(uint from_i, uint adr, int offs);
 275 
 276 
 277   // Remove outgoing deferred edges from the node referenced by "ni".
 278   // Any outgoing edges from the target of the deferred edge are copied
 279   // to "ni".
 280   void remove_deferred(uint ni, GrowableArray<uint>* deferred_edges, VectorSet* visited);
 281 
 282   Node_Array _node_map; // used for bookeeping during type splitting
 283                         // Used for the following purposes:
 284                         // Memory Phi    - most recent unique Phi split out
 285                         //                 from this Phi
 286                         // MemNode       - new memory input for this node
 287                         // ChecCastPP    - allocation that this is a cast of
 288                         // allocation    - CheckCastPP of the allocation
 289   bool split_AddP(Node *addp, Node *base,  PhaseGVN  *igvn);
 290   PhiNode *create_split_phi(PhiNode *orig_phi, int alias_idx, GrowableArray<PhiNode *>  &orig_phi_worklist, PhaseGVN  *igvn, bool &new_created);
 291   PhiNode *split_memory_phi(PhiNode *orig_phi, int alias_idx, GrowableArray<PhiNode *>  &orig_phi_worklist, PhaseGVN  *igvn);
 292   Node *find_mem(Node *mem, int alias_idx, PhaseGVN  *igvn);
 293   Node *find_inst_mem(Node *mem, int alias_idx,GrowableArray<PhiNode *>  &orig_phi_worklist,  PhaseGVN  *igvn);
 294 
 295   // Propagate unique types created for unescaped allocated objects
 296   // through the graph
 297   void split_unique_types(GrowableArray<Node *>  &alloc_worklist);
 298 
 299   // manage entries in _node_map
 300   void  set_map(int idx, Node *n)        { _node_map.map(idx, n); }
 301   void  set_map_phi(int idx, PhiNode *p) { _node_map.map(idx, (Node *) p); }
 302   Node *get_map(int idx)                 { return _node_map[idx]; }
 303   PhiNode *get_map_phi(int idx) {
 304     Node *phi = _node_map[idx];
 305     return (phi == NULL) ? NULL : phi->as_Phi();
 306   }
 307 
 308   // Notify optimizer that a node has been modified
 309   // Node:  This assumes that escape analysis is run before
 310   //        PhaseIterGVN creation
 311   void record_for_optimizer(Node *n) {
 312     _compile->record_for_igvn(n);
 313   }
 314 
 315   // Set the escape state of a node
 316   void set_escape_state(uint ni, PointsToNode::EscapeState es);
 317 
 318 public:
 319   ConnectionGraph(Compile *C);
 320 
 321   // Check for non-escaping candidates
 322   static bool has_candidates(Compile *C);
 323 
 324   // Compute the escape information
 325   bool compute_escape();
 326 
 327   // escape state of a node
 328   PointsToNode::EscapeState escape_state(Node *n, PhaseTransform *phase);
 329   // other information we have collected
 330   bool is_scalar_replaceable(Node *n) {
 331     if (_collecting || (n->_idx >= nodes_size()))
 332       return false;
 333     PointsToNode* ptn = ptnode_adr(n->_idx);
 334     return ptn->escape_state() == PointsToNode::NoEscape && ptn->_scalar_replaceable;
 335   }
 336 
 337   bool hidden_alias(Node *n) {
 338     if (_collecting || (n->_idx >= nodes_size()))
 339       return true;
 340     PointsToNode* ptn = ptnode_adr(n->_idx);
 341     return (ptn->escape_state() != PointsToNode::NoEscape) || ptn->_hidden_alias;
 342   }
 343 
 344 #ifndef PRODUCT
 345   void dump();
 346 #endif
 347 };