escape.hpp revision 2874:8c57262447d3
1/* 2 * Copyright (c) 2005, 2011, Oracle and/or its affiliates. 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 Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 20 * or visit www.oracle.com if you need additional information or have any 21 * questions. 22 * 23 */ 24 25#ifndef SHARE_VM_OPTO_ESCAPE_HPP 26#define SHARE_VM_OPTO_ESCAPE_HPP 27 28#include "opto/addnode.hpp" 29#include "opto/node.hpp" 30#include "utilities/growableArray.hpp" 31 32// 33// Adaptation for C2 of the escape analysis algorithm described in: 34// 35// [Choi99] Jong-Deok Shoi, Manish Gupta, Mauricio Seffano, 36// Vugranam C. Sreedhar, Sam Midkiff, 37// "Escape Analysis for Java", Procedings of ACM SIGPLAN 38// OOPSLA Conference, November 1, 1999 39// 40// The flow-insensitive analysis described in the paper has been implemented. 41// 42// The analysis requires construction of a "connection graph" (CG) for 43// the method being analyzed. The nodes of the connection graph are: 44// 45// - Java objects (JO) 46// - Local variables (LV) 47// - Fields of an object (OF), these also include array elements 48// 49// The CG contains 3 types of edges: 50// 51// - PointsTo (-P>) {LV, OF} to JO 52// - Deferred (-D>) from {LV, OF} to {LV, OF} 53// - Field (-F>) from JO to OF 54// 55// The following utility functions is used by the algorithm: 56// 57// PointsTo(n) - n is any CG node, it returns the set of JO that n could 58// point to. 59// 60// The algorithm describes how to construct the connection graph 61// in the following 4 cases: 62// 63// Case Edges Created 64// 65// (1) p = new T() LV -P> JO 66// (2) p = q LV -D> LV 67// (3) p.f = q JO -F> OF, OF -D> LV 68// (4) p = q.f JO -F> OF, LV -D> OF 69// 70// In all these cases, p and q are local variables. For static field 71// references, we can construct a local variable containing a reference 72// to the static memory. 73// 74// C2 does not have local variables. However for the purposes of constructing 75// the connection graph, the following IR nodes are treated as local variables: 76// Phi (pointer values) 77// LoadP, LoadN 78// Proj#5 (value returned from callnodes including allocations) 79// CheckCastPP, CastPP 80// 81// The LoadP, Proj and CheckCastPP behave like variables assigned to only once. 82// Only a Phi can have multiple assignments. Each input to a Phi is treated 83// as an assignment to it. 84// 85// The following node types are JavaObject: 86// 87// phantom_object (general globally escaped object) 88// Allocate 89// AllocateArray 90// Parm (for incoming arguments) 91// CastX2P ("unsafe" operations) 92// CreateEx 93// ConP 94// LoadKlass 95// ThreadLocal 96// CallStaticJava (which returns Object) 97// 98// AddP nodes are fields. 99// 100// After building the graph, a pass is made over the nodes, deleting deferred 101// nodes and copying the edges from the target of the deferred edge to the 102// source. This results in a graph with no deferred edges, only: 103// 104// LV -P> JO 105// OF -P> JO (the object whose oop is stored in the field) 106// JO -F> OF 107// 108// Then, for each node which is GlobalEscape, anything it could point to 109// is marked GlobalEscape. Finally, for any node marked ArgEscape, anything 110// it could point to is marked ArgEscape. 111// 112 113class Compile; 114class Node; 115class CallNode; 116class PhiNode; 117class PhaseTransform; 118class Type; 119class TypePtr; 120class VectorSet; 121 122class PointsToNode { 123friend class ConnectionGraph; 124public: 125 typedef enum { 126 UnknownType = 0, 127 JavaObject = 1, 128 LocalVar = 2, 129 Field = 3 130 } NodeType; 131 132 typedef enum { 133 UnknownEscape = 0, 134 NoEscape = 1, // An object does not escape method or thread and it is 135 // not passed to call. It could be replaced with scalar. 136 ArgEscape = 2, // An object does not escape method or thread but it is 137 // passed as argument to call or referenced by argument 138 // and it does not escape during call. 139 GlobalEscape = 3 // An object escapes the method or thread. 140 } EscapeState; 141 142 typedef enum { 143 UnknownEdge = 0, 144 PointsToEdge = 1, 145 DeferredEdge = 2, 146 FieldEdge = 3 147 } EdgeType; 148 149private: 150 enum { 151 EdgeMask = 3, 152 EdgeShift = 2, 153 154 INITIAL_EDGE_COUNT = 4 155 }; 156 157 NodeType _type; 158 EscapeState _escape; 159 GrowableArray<uint>* _edges; // outgoing edges 160 Node* _node; // Ideal node corresponding to this PointsTo node. 161 int _offset; // Object fields offsets. 162 bool _scalar_replaceable; // Not escaped object could be replaced with scalar 163 164public: 165 PointsToNode(): 166 _type(UnknownType), 167 _escape(UnknownEscape), 168 _edges(NULL), 169 _node(NULL), 170 _offset(-1), 171 _scalar_replaceable(true) {} 172 173 174 EscapeState escape_state() const { return _escape; } 175 NodeType node_type() const { return _type;} 176 int offset() { return _offset;} 177 bool scalar_replaceable() { return _scalar_replaceable;} 178 179 void set_offset(int offs) { _offset = offs;} 180 void set_escape_state(EscapeState state) { _escape = state; } 181 void set_node_type(NodeType ntype) { 182 assert(_type == UnknownType || _type == ntype, "Can't change node type"); 183 _type = ntype; 184 } 185 void set_scalar_replaceable(bool v) { _scalar_replaceable = v; } 186 187 // count of outgoing edges 188 uint edge_count() const { return (_edges == NULL) ? 0 : _edges->length(); } 189 190 // node index of target of outgoing edge "e" 191 uint edge_target(uint e) const { 192 assert(_edges != NULL, "valid edge index"); 193 return (_edges->at(e) >> EdgeShift); 194 } 195 // type of outgoing edge "e" 196 EdgeType edge_type(uint e) const { 197 assert(_edges != NULL, "valid edge index"); 198 return (EdgeType) (_edges->at(e) & EdgeMask); 199 } 200 201 // add a edge of the specified type pointing to the specified target 202 void add_edge(uint targIdx, EdgeType et); 203 204 // remove an edge of the specified type pointing to the specified target 205 void remove_edge(uint targIdx, EdgeType et); 206 207#ifndef PRODUCT 208 void dump(bool print_state=true) const; 209#endif 210 211}; 212 213class ConnectionGraph: public ResourceObj { 214private: 215 GrowableArray<PointsToNode> _nodes; // Connection graph nodes indexed 216 // by ideal node index. 217 218 Unique_Node_List _delayed_worklist; // Nodes to be processed before 219 // the call build_connection_graph(). 220 221 GrowableArray<MergeMemNode *> _mergemem_worklist; // List of all MergeMem nodes 222 223 VectorSet _processed; // Records which nodes have been 224 // processed. 225 226 bool _collecting; // Indicates whether escape information 227 // is still being collected. If false, 228 // no new nodes will be processed. 229 230 bool _progress; // Indicates whether new Graph's edges 231 // were created. 232 233 uint _phantom_object; // Index of globally escaping object 234 // that pointer values loaded from 235 // a field which has not been set 236 // are assumed to point to. 237 uint _oop_null; // ConP(#NULL)->_idx 238 uint _noop_null; // ConN(#NULL)->_idx 239 Node* _pcmp_neq; // ConI(#CC_GT) 240 Node* _pcmp_eq; // ConI(#CC_EQ) 241 242 Compile * _compile; // Compile object for current compilation 243 PhaseIterGVN * _igvn; // Value numbering 244 245 // Address of an element in _nodes. Used when the element is to be modified 246 PointsToNode *ptnode_adr(uint idx) const { 247 // There should be no new ideal nodes during ConnectionGraph build, 248 // growableArray::adr_at() will throw assert otherwise. 249 return _nodes.adr_at(idx); 250 } 251 uint nodes_size() const { return _nodes.length(); } 252 253 // Add node to ConnectionGraph. 254 void add_node(Node *n, PointsToNode::NodeType nt, PointsToNode::EscapeState es, bool done); 255 256 // offset of a field reference 257 int address_offset(Node* adr, PhaseTransform *phase); 258 259 // compute the escape state for arguments to a call 260 void process_call_arguments(CallNode *call, PhaseTransform *phase); 261 262 // compute the escape state for the return value of a call 263 void process_call_result(ProjNode *resproj, PhaseTransform *phase); 264 265 // Populate Connection Graph with Ideal nodes. 266 void record_for_escape_analysis(Node *n, PhaseTransform *phase); 267 268 // Build Connection Graph and set nodes escape state. 269 void build_connection_graph(Node *n, PhaseTransform *phase); 270 271 // walk the connection graph starting at the node corresponding to "n" and 272 // add the index of everything it could point to, to "ptset". This may cause 273 // Phi's encountered to get (re)processed (which requires "phase".) 274 VectorSet* PointsTo(Node * n); 275 276 // Reused structures for PointsTo(). 277 VectorSet pt_ptset; 278 VectorSet pt_visited; 279 GrowableArray<uint> pt_worklist; 280 281 // Edge manipulation. The "from_i" and "to_i" arguments are the 282 // node indices of the source and destination of the edge 283 void add_pointsto_edge(uint from_i, uint to_i); 284 void add_deferred_edge(uint from_i, uint to_i); 285 void add_field_edge(uint from_i, uint to_i, int offs); 286 287 // Add an edge of the specified type pointing to the specified target. 288 // Set _progress if new edge is added. 289 void add_edge(PointsToNode *f, uint to_i, PointsToNode::EdgeType et) { 290 uint e_cnt = f->edge_count(); 291 f->add_edge(to_i, et); 292 _progress |= (f->edge_count() != e_cnt); 293 } 294 295 // Add an edge to node given by "to_i" from any field of adr_i whose offset 296 // matches "offset" A deferred edge is added if to_i is a LocalVar, and 297 // a pointsto edge is added if it is a JavaObject 298 void add_edge_from_fields(uint adr, uint to_i, int offs); 299 300 // Add a deferred edge from node given by "from_i" to any field 301 // of adr_i whose offset matches "offset" 302 void add_deferred_edge_to_fields(uint from_i, uint adr, int offs); 303 304 305 // Remove outgoing deferred edges from the node referenced by "ni". 306 // Any outgoing edges from the target of the deferred edge are copied 307 // to "ni". 308 void remove_deferred(uint ni, GrowableArray<uint>* deferred_edges, VectorSet* visited); 309 310 Node_Array _node_map; // used for bookeeping during type splitting 311 // Used for the following purposes: 312 // Memory Phi - most recent unique Phi split out 313 // from this Phi 314 // MemNode - new memory input for this node 315 // ChecCastPP - allocation that this is a cast of 316 // allocation - CheckCastPP of the allocation 317 bool split_AddP(Node *addp, Node *base, PhaseGVN *igvn); 318 PhiNode *create_split_phi(PhiNode *orig_phi, int alias_idx, GrowableArray<PhiNode *> &orig_phi_worklist, PhaseGVN *igvn, bool &new_created); 319 PhiNode *split_memory_phi(PhiNode *orig_phi, int alias_idx, GrowableArray<PhiNode *> &orig_phi_worklist, PhaseGVN *igvn); 320 void move_inst_mem(Node* n, GrowableArray<PhiNode *> &orig_phis, PhaseGVN *igvn); 321 Node *find_inst_mem(Node *mem, int alias_idx,GrowableArray<PhiNode *> &orig_phi_worklist, PhaseGVN *igvn); 322 323 // Propagate unique types created for unescaped allocated objects 324 // through the graph 325 void split_unique_types(GrowableArray<Node *> &alloc_worklist); 326 327 // manage entries in _node_map 328 void set_map(int idx, Node *n) { _node_map.map(idx, n); } 329 Node *get_map(int idx) { return _node_map[idx]; } 330 PhiNode *get_map_phi(int idx) { 331 Node *phi = _node_map[idx]; 332 return (phi == NULL) ? NULL : phi->as_Phi(); 333 } 334 335 // Notify optimizer that a node has been modified 336 // Node: This assumes that escape analysis is run before 337 // PhaseIterGVN creation 338 void record_for_optimizer(Node *n) { 339 _igvn->_worklist.push(n); 340 } 341 342 // Set the escape state of a node 343 void set_escape_state(uint ni, PointsToNode::EscapeState es); 344 345 // Find fields initializing values for allocations. 346 void find_init_values(Node* n, VectorSet* visited, PhaseTransform* phase); 347 348 // Adjust escape state after Connection Graph is built. 349 void adjust_escape_state(Node* n); 350 351 // Propagate escape states to referenced nodes. 352 bool propagate_escape_state(GrowableArray<int>* cg_worklist, 353 GrowableArray<uint>* worklist, 354 PointsToNode::EscapeState esc_state); 355 356 // Optimize objects compare. 357 Node* optimize_ptr_compare(Node* n); 358 359 // Compute the escape information 360 bool compute_escape(); 361 362public: 363 ConnectionGraph(Compile *C, PhaseIterGVN *igvn); 364 365 // Check for non-escaping candidates 366 static bool has_candidates(Compile *C); 367 368 // Perform escape analysis 369 static void do_analysis(Compile *C, PhaseIterGVN *igvn); 370 371 // escape state of a node 372 PointsToNode::EscapeState escape_state(Node *n); 373 374#ifndef PRODUCT 375 void dump(); 376#endif 377}; 378 379#endif // SHARE_VM_OPTO_ESCAPE_HPP 380