escape.hpp 12.6 KB
Newer Older
D
duke 已提交
1
/*
2
 * Copyright (c) 2005, 2008, Oracle and/or its affiliates. All rights reserved.
D
duke 已提交
3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
 *
 * This code is free software; you can redistribute it and/or modify it
 * under the terms of the GNU General Public License version 2 only, as
 * published by the Free Software Foundation.
 *
 * This code is distributed in the hope that it will be useful, but WITHOUT
 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
 * version 2 for more details (a copy is included in the LICENSE file that
 * accompanied this code).
 *
 * You should have received a copy of the GNU General Public License version
 * 2 along with this work; if not, write to the Free Software Foundation,
 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
 *
19 20 21
 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
 * or visit www.oracle.com if you need additional information or have any
 * questions.
D
duke 已提交
22 23 24 25 26 27
 *
 */

//
// Adaptation for C2 of the escape analysis algorithm described in:
//
28 29 30 31
// [Choi99] Jong-Deok Shoi, Manish Gupta, Mauricio Seffano,
//          Vugranam C. Sreedhar, Sam Midkiff,
//          "Escape Analysis for Java", Procedings of ACM SIGPLAN
//          OOPSLA  Conference, November 1, 1999
D
duke 已提交
32 33 34
//
// The flow-insensitive analysis described in the paper has been implemented.
//
35 36
// The analysis requires construction of a "connection graph" (CG) for
// the method being analyzed.  The nodes of the connection graph are:
D
duke 已提交
37 38 39 40 41 42 43
//
//     -  Java objects (JO)
//     -  Local variables (LV)
//     -  Fields of an object (OF),  these also include array elements
//
// The CG contains 3 types of edges:
//
44 45
//   -  PointsTo  (-P>)    {LV, OF} to JO
//   -  Deferred  (-D>)    from {LV, OF} to {LV, OF}
D
duke 已提交
46 47 48 49
//   -  Field     (-F>)    from JO to OF
//
// The following  utility functions is used by the algorithm:
//
50 51
//   PointsTo(n) - n is any CG node, it returns the set of JO that n could
//                 point to.
D
duke 已提交
52
//
53 54
// The algorithm describes how to construct the connection graph
// in the following 4 cases:
D
duke 已提交
55 56 57
//
//          Case                  Edges Created
//
58 59 60 61
// (1)   p   = new T()              LV -P> JO
// (2)   p   = q                    LV -D> LV
// (3)   p.f = q                    JO -F> OF,  OF -D> LV
// (4)   p   = q.f                  JO -F> OF,  LV -D> OF
D
duke 已提交
62
//
63 64 65
// In all these cases, p and q are local variables.  For static field
// references, we can construct a local variable containing a reference
// to the static memory.
D
duke 已提交
66 67 68 69 70
//
// C2 does not have local variables.  However for the purposes of constructing
// the connection graph, the following IR nodes are treated as local variables:
//     Phi    (pointer values)
//     LoadP
71 72
//     Proj#5 (value returned from callnodes including allocations)
//     CheckCastPP, CastPP
D
duke 已提交
73
//
74 75
// The LoadP, Proj and CheckCastPP behave like variables assigned to only once.
// Only a Phi can have multiple assignments.  Each input to a Phi is treated
D
duke 已提交
76 77
// as an assignment to it.
//
78
// The following node types are JavaObject:
D
duke 已提交
79 80 81 82 83
//
//     top()
//     Allocate
//     AllocateArray
//     Parm  (for incoming arguments)
84
//     CastX2P ("unsafe" operations)
D
duke 已提交
85 86 87
//     CreateEx
//     ConP
//     LoadKlass
88
//     ThreadLocal
D
duke 已提交
89 90 91 92 93 94 95 96
//
// AddP nodes are fields.
//
// After building the graph, a pass is made over the nodes, deleting deferred
// nodes and copying the edges from the target of the deferred edge to the
// source.  This results in a graph with no deferred edges, only:
//
//    LV -P> JO
97
//    OF -P> JO (the object whose oop is stored in the field)
D
duke 已提交
98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117
//    JO -F> OF
//
// Then, for each node which is GlobalEscape, anything it could point to
// is marked GlobalEscape.  Finally, for any node marked ArgEscape, anything
// it could point to is marked ArgEscape.
//

class  Compile;
class  Node;
class  CallNode;
class  PhiNode;
class  PhaseTransform;
class  Type;
class  TypePtr;
class  VectorSet;

class PointsToNode {
friend class ConnectionGraph;
public:
  typedef enum {
118 119 120 121
    UnknownType = 0,
    JavaObject  = 1,
    LocalVar    = 2,
    Field       = 3
D
duke 已提交
122 123 124 125
  } NodeType;

  typedef enum {
    UnknownEscape = 0,
126 127 128 129
    NoEscape      = 1, // A scalar replaceable object with unique type.
    ArgEscape     = 2, // An object passed as argument or referenced by
                       // argument (and not globally escape during call).
    GlobalEscape  = 3  // An object escapes the method and thread.
D
duke 已提交
130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148
  } EscapeState;

  typedef enum {
    UnknownEdge   = 0,
    PointsToEdge  = 1,
    DeferredEdge  = 2,
    FieldEdge     = 3
  } EdgeType;

private:
  enum {
    EdgeMask = 3,
    EdgeShift = 2,

    INITIAL_EDGE_COUNT = 4
  };

  NodeType             _type;
  EscapeState          _escape;
149
  GrowableArray<uint>* _edges;   // outgoing edges
D
duke 已提交
150 151

public:
152 153 154 155 156 157 158 159 160 161 162 163 164 165
  Node* _node;              // Ideal node corresponding to this PointsTo node.
  int   _offset;            // Object fields offsets.
  bool  _scalar_replaceable;// Not escaped object could be replaced with scalar
  bool  _hidden_alias;      // This node is an argument to a function.
                            // which may return it creating a hidden alias.

  PointsToNode():
    _type(UnknownType),
    _escape(UnknownEscape),
    _edges(NULL),
    _node(NULL),
    _offset(-1),
    _scalar_replaceable(true),
    _hidden_alias(false) {}
D
duke 已提交
166 167 168 169 170 171 172 173 174 175 176 177 178 179 180


  EscapeState escape_state() const { return _escape; }
  NodeType node_type() const { return _type;}
  int offset() { return _offset;}

  void set_offset(int offs) { _offset = offs;}
  void set_escape_state(EscapeState state) { _escape = state; }
  void set_node_type(NodeType ntype) {
    assert(_type == UnknownType || _type == ntype, "Can't change node type");
    _type = ntype;
  }

  // count of outgoing edges
  uint edge_count() const { return (_edges == NULL) ? 0 : _edges->length(); }
181

D
duke 已提交
182
  // node index of target of outgoing edge "e"
183 184 185 186
  uint edge_target(uint e) const {
    assert(_edges != NULL, "valid edge index");
    return (_edges->at(e) >> EdgeShift);
  }
D
duke 已提交
187
  // type of outgoing edge "e"
188 189 190 191 192
  EdgeType edge_type(uint e) const {
    assert(_edges != NULL, "valid edge index");
    return (EdgeType) (_edges->at(e) & EdgeMask);
  }

D
duke 已提交
193 194
  // add a edge of the specified type pointing to the specified target
  void add_edge(uint targIdx, EdgeType et);
195

D
duke 已提交
196 197
  // remove an edge of the specified type pointing to the specified target
  void remove_edge(uint targIdx, EdgeType et);
198

D
duke 已提交
199
#ifndef PRODUCT
200
  void dump(bool print_state=true) const;
D
duke 已提交
201 202 203 204 205 206
#endif

};

class ConnectionGraph: public ResourceObj {
private:
207
  GrowableArray<PointsToNode>  _nodes; // Connection graph nodes indexed
208 209 210 211
                                       // by ideal node index.

  Unique_Node_List  _delayed_worklist; // Nodes to be processed before
                                       // the call build_connection_graph().
D
duke 已提交
212

213 214
  GrowableArray<MergeMemNode *>  _mergemem_worklist; // List of all MergeMem nodes

215 216
  VectorSet                _processed; // Records which nodes have been
                                       // processed.
D
duke 已提交
217

218 219 220 221 222 223 224 225
  bool                    _collecting; // Indicates whether escape information
                                       // is still being collected. If false,
                                       // no new nodes will be processed.

  uint                _phantom_object; // Index of globally escaping object
                                       // that pointer values loaded from
                                       // a field which has not been set
                                       // are assumed to point to.
226 227
  uint                      _oop_null; // ConP(#NULL)
  uint                     _noop_null; // ConN(#NULL)
228 229

  Compile *                  _compile; // Compile object for current compilation
D
duke 已提交
230

231 232 233 234 235
  // Address of an element in _nodes.  Used when the element is to be modified
  PointsToNode *ptnode_adr(uint idx) const {
    // There should be no new ideal nodes during ConnectionGraph build,
    // growableArray::adr_at() will throw assert otherwise.
    return _nodes.adr_at(idx);
D
duke 已提交
236
  }
237
  uint nodes_size() const { return _nodes.length(); }
D
duke 已提交
238

239 240 241
  // Add node to ConnectionGraph.
  void add_node(Node *n, PointsToNode::NodeType nt, PointsToNode::EscapeState es, bool done);

D
duke 已提交
242
  // offset of a field reference
243
  int address_offset(Node* adr, PhaseTransform *phase);
D
duke 已提交
244 245 246 247 248 249 250

  // compute the escape state for arguments to a call
  void process_call_arguments(CallNode *call, PhaseTransform *phase);

  // compute the escape state for the return value of a call
  void process_call_result(ProjNode *resproj, PhaseTransform *phase);

251 252
  // Populate Connection Graph with Ideal nodes.
  void record_for_escape_analysis(Node *n, PhaseTransform *phase);
D
duke 已提交
253

254 255
  // Build Connection Graph and set nodes escape state.
  void build_connection_graph(Node *n, PhaseTransform *phase);
D
duke 已提交
256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273

  // walk the connection graph starting at the node corresponding to "n" and
  // add the index of everything it could point to, to "ptset".  This may cause
  // Phi's encountered to get (re)processed  (which requires "phase".)
  void PointsTo(VectorSet &ptset, Node * n, PhaseTransform *phase);

  //  Edge manipulation.  The "from_i" and "to_i" arguments are the
  //  node indices of the source and destination of the edge
  void add_pointsto_edge(uint from_i, uint to_i);
  void add_deferred_edge(uint from_i, uint to_i);
  void add_field_edge(uint from_i, uint to_i, int offs);


  // Add an edge to node given by "to_i" from any field of adr_i whose offset
  // matches "offset"  A deferred edge is added if to_i is a LocalVar, and
  // a pointsto edge is added if it is a JavaObject
  void add_edge_from_fields(uint adr, uint to_i, int offs);

274 275
  // Add a deferred  edge from node given by "from_i" to any field
  // of adr_i whose offset matches "offset"
D
duke 已提交
276 277 278 279 280 281
  void add_deferred_edge_to_fields(uint from_i, uint adr, int offs);


  // Remove outgoing deferred edges from the node referenced by "ni".
  // Any outgoing edges from the target of the deferred edge are copied
  // to "ni".
282
  void remove_deferred(uint ni, GrowableArray<uint>* deferred_edges, VectorSet* visited);
D
duke 已提交
283 284 285 286 287 288 289 290

  Node_Array _node_map; // used for bookeeping during type splitting
                        // Used for the following purposes:
                        // Memory Phi    - most recent unique Phi split out
                        //                 from this Phi
                        // MemNode       - new memory input for this node
                        // ChecCastPP    - allocation that this is a cast of
                        // allocation    - CheckCastPP of the allocation
291
  bool split_AddP(Node *addp, Node *base,  PhaseGVN  *igvn);
D
duke 已提交
292 293
  PhiNode *create_split_phi(PhiNode *orig_phi, int alias_idx, GrowableArray<PhiNode *>  &orig_phi_worklist, PhaseGVN  *igvn, bool &new_created);
  PhiNode *split_memory_phi(PhiNode *orig_phi, int alias_idx, GrowableArray<PhiNode *>  &orig_phi_worklist, PhaseGVN  *igvn);
294
  void  move_inst_mem(Node* n, GrowableArray<PhiNode *>  &orig_phis, PhaseGVN *igvn);
295 296
  Node *find_inst_mem(Node *mem, int alias_idx,GrowableArray<PhiNode *>  &orig_phi_worklist,  PhaseGVN  *igvn);

D
duke 已提交
297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318
  // Propagate unique types created for unescaped allocated objects
  // through the graph
  void split_unique_types(GrowableArray<Node *>  &alloc_worklist);

  // manage entries in _node_map
  void  set_map(int idx, Node *n)        { _node_map.map(idx, n); }
  Node *get_map(int idx)                 { return _node_map[idx]; }
  PhiNode *get_map_phi(int idx) {
    Node *phi = _node_map[idx];
    return (phi == NULL) ? NULL : phi->as_Phi();
  }

  // Notify optimizer that a node has been modified
  // Node:  This assumes that escape analysis is run before
  //        PhaseIterGVN creation
  void record_for_optimizer(Node *n) {
    _compile->record_for_igvn(n);
  }

  // Set the escape state of a node
  void set_escape_state(uint ni, PointsToNode::EscapeState es);

319 320 321
  // Search for objects which are not scalar replaceable.
  void verify_escape_state(int nidx, VectorSet& ptset, PhaseTransform* phase);

D
duke 已提交
322 323 324
public:
  ConnectionGraph(Compile *C);

325 326 327
  // Check for non-escaping candidates
  static bool has_candidates(Compile *C);

328
  // Compute the escape information
329
  bool compute_escape();
D
duke 已提交
330 331 332

  // escape state of a node
  PointsToNode::EscapeState escape_state(Node *n, PhaseTransform *phase);
333 334
  // other information we have collected
  bool is_scalar_replaceable(Node *n) {
335
    if (_collecting || (n->_idx >= nodes_size()))
336
      return false;
337 338
    PointsToNode* ptn = ptnode_adr(n->_idx);
    return ptn->escape_state() == PointsToNode::NoEscape && ptn->_scalar_replaceable;
339
  }
D
duke 已提交
340 341

  bool hidden_alias(Node *n) {
342
    if (_collecting || (n->_idx >= nodes_size()))
D
duke 已提交
343
      return true;
344 345
    PointsToNode* ptn = ptnode_adr(n->_idx);
    return (ptn->escape_state() != PointsToNode::NoEscape) || ptn->_hidden_alias;
D
duke 已提交
346 347 348 349 350 351
  }

#ifndef PRODUCT
  void dump();
#endif
};