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 };