Mercurial > hg > truffle
annotate src/share/vm/opto/escape.hpp @ 196:d1605aabd0a1 jdk7-b30
6719955: Update copyright year
Summary: Update copyright year for files that have been modified in 2008
Reviewed-by: ohair, tbell
| author | xdono |
|---|---|
| date | Wed, 02 Jul 2008 12:55:16 -0700 |
| parents | a6cb86dd209b |
| children | 4a4c365f777d |
| rev | line source |
|---|---|
| 0 | 1 /* |
| 196 | 2 * Copyright 2005-2008 Sun Microsystems, Inc. All Rights Reserved. |
| 0 | 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 // | |
| 65 | 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 | |
| 0 | 32 // |
| 33 // The flow-insensitive analysis described in the paper has been implemented. | |
| 34 // | |
| 65 | 35 // The analysis requires construction of a "connection graph" (CG) for |
| 36 // the method being analyzed. The nodes of the connection graph are: | |
| 0 | 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 // | |
| 65 | 44 // - PointsTo (-P>) {LV, OF} to JO |
| 45 // - Deferred (-D>) from {LV, OF} to {LV, OF} | |
| 0 | 46 // - Field (-F>) from JO to OF |
| 47 // | |
| 48 // The following utility functions is used by the algorithm: | |
| 49 // | |
| 65 | 50 // PointsTo(n) - n is any CG node, it returns the set of JO that n could |
| 51 // point to. | |
| 0 | 52 // |
| 65 | 53 // The algorithm describes how to construct the connection graph |
| 54 // in the following 4 cases: | |
| 0 | 55 // |
| 56 // Case Edges Created | |
| 57 // | |
| 65 | 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 | |
| 0 | 62 // |
| 65 | 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. | |
| 0 | 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 | |
| 65 | 71 // Proj#5 (value returned from callnodes including allocations) |
| 72 // CheckCastPP, CastPP | |
| 0 | 73 // |
| 65 | 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 | |
| 0 | 76 // as an assignment to it. |
| 77 // | |
| 65 | 78 // The following node types are JavaObject: |
| 0 | 79 // |
| 80 // top() | |
| 81 // Allocate | |
| 82 // AllocateArray | |
| 83 // Parm (for incoming arguments) | |
| 65 | 84 // CastX2P ("unsafe" operations) |
| 0 | 85 // CreateEx |
| 86 // ConP | |
| 87 // LoadKlass | |
| 65 | 88 // ThreadLocal |
| 0 | 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 | |
| 65 | 97 // OF -P> JO (the object whose oop is stored in the field) |
| 0 | 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 { | |
| 65 | 118 UnknownType = 0, |
| 119 JavaObject = 1, | |
| 120 LocalVar = 2, | |
| 121 Field = 3 | |
| 0 | 122 } NodeType; |
| 123 | |
| 124 typedef enum { | |
| 125 UnknownEscape = 0, | |
| 65 | 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. | |
| 0 | 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; | |
| 65 | 149 GrowableArray<uint>* _edges; // outgoing edges |
| 0 | 150 |
| 151 public: | |
| 65 | 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. | |
| 0 | 157 |
| 65 | 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) {} | |
| 0 | 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 // node index of target of outgoing edge "e" | |
| 182 uint edge_target(uint e) const; | |
| 183 // type of outgoing edge "e" | |
| 184 EdgeType edge_type(uint e) const; | |
| 185 // add a edge of the specified type pointing to the specified target | |
| 186 void add_edge(uint targIdx, EdgeType et); | |
| 187 // remove an edge of the specified type pointing to the specified target | |
| 188 void remove_edge(uint targIdx, EdgeType et); | |
| 189 #ifndef PRODUCT | |
| 190 void dump() const; | |
| 191 #endif | |
| 192 | |
| 193 }; | |
| 194 | |
| 195 class ConnectionGraph: public ResourceObj { | |
| 196 private: | |
| 65 | 197 GrowableArray<PointsToNode>* _nodes; // Connection graph nodes indexed |
| 198 // by ideal node index. | |
| 0 | 199 |
| 65 | 200 Unique_Node_List _delayed_worklist; // Nodes to be processed before |
| 201 // the call build_connection_graph(). | |
| 202 | |
| 203 VectorSet _processed; // Records which nodes have been | |
| 204 // processed. | |
| 0 | 205 |
| 65 | 206 bool _collecting; // Indicates whether escape information |
| 207 // is still being collected. If false, | |
| 208 // no new nodes will be processed. | |
| 209 | |
| 210 bool _has_allocations; // Indicates whether method has any | |
| 211 // non-escaping allocations. | |
| 212 | |
| 213 uint _phantom_object; // Index of globally escaping object | |
| 214 // that pointer values loaded from | |
| 215 // a field which has not been set | |
| 216 // are assumed to point to. | |
| 217 | |
| 218 Compile * _compile; // Compile object for current compilation | |
| 0 | 219 |
| 220 // address of an element in _nodes. Used when the element is to be modified | |
| 221 PointsToNode *ptnode_adr(uint idx) { | |
| 222 if ((uint)_nodes->length() <= idx) { | |
| 223 // expand _nodes array | |
| 224 PointsToNode dummy = _nodes->at_grow(idx); | |
| 225 } | |
| 226 return _nodes->adr_at(idx); | |
| 227 } | |
| 228 | |
| 65 | 229 // Add node to ConnectionGraph. |
| 230 void add_node(Node *n, PointsToNode::NodeType nt, PointsToNode::EscapeState es, bool done); | |
| 231 | |
| 0 | 232 // offset of a field reference |
| 65 | 233 int address_offset(Node* adr, PhaseTransform *phase); |
| 0 | 234 |
| 235 // compute the escape state for arguments to a call | |
| 236 void process_call_arguments(CallNode *call, PhaseTransform *phase); | |
| 237 | |
| 238 // compute the escape state for the return value of a call | |
| 239 void process_call_result(ProjNode *resproj, PhaseTransform *phase); | |
| 240 | |
| 65 | 241 // Populate Connection Graph with Ideal nodes. |
| 242 void record_for_escape_analysis(Node *n, PhaseTransform *phase); | |
| 0 | 243 |
| 65 | 244 // Build Connection Graph and set nodes escape state. |
| 245 void build_connection_graph(Node *n, PhaseTransform *phase); | |
| 0 | 246 |
| 247 // walk the connection graph starting at the node corresponding to "n" and | |
| 248 // add the index of everything it could point to, to "ptset". This may cause | |
| 249 // Phi's encountered to get (re)processed (which requires "phase".) | |
| 250 void PointsTo(VectorSet &ptset, Node * n, PhaseTransform *phase); | |
| 251 | |
| 252 // Edge manipulation. The "from_i" and "to_i" arguments are the | |
| 253 // node indices of the source and destination of the edge | |
| 254 void add_pointsto_edge(uint from_i, uint to_i); | |
| 255 void add_deferred_edge(uint from_i, uint to_i); | |
| 256 void add_field_edge(uint from_i, uint to_i, int offs); | |
| 257 | |
| 258 | |
| 259 // Add an edge to node given by "to_i" from any field of adr_i whose offset | |
| 260 // matches "offset" A deferred edge is added if to_i is a LocalVar, and | |
| 261 // a pointsto edge is added if it is a JavaObject | |
| 262 void add_edge_from_fields(uint adr, uint to_i, int offs); | |
| 263 | |
| 65 | 264 // Add a deferred edge from node given by "from_i" to any field |
| 265 // of adr_i whose offset matches "offset" | |
| 0 | 266 void add_deferred_edge_to_fields(uint from_i, uint adr, int offs); |
| 267 | |
| 268 | |
| 269 // Remove outgoing deferred edges from the node referenced by "ni". | |
| 270 // Any outgoing edges from the target of the deferred edge are copied | |
| 271 // to "ni". | |
|
101
a6cb86dd209b
6681577: PIT: some VM tests fails with -XX:+AggressiveOpts in 6u5p b01
kvn
parents:
65
diff
changeset
|
272 void remove_deferred(uint ni, GrowableArray<uint>* deferred_edges, VectorSet* visited); |
| 0 | 273 |
| 274 Node_Array _node_map; // used for bookeeping during type splitting | |
| 275 // Used for the following purposes: | |
| 276 // Memory Phi - most recent unique Phi split out | |
| 277 // from this Phi | |
| 278 // MemNode - new memory input for this node | |
| 279 // ChecCastPP - allocation that this is a cast of | |
| 280 // allocation - CheckCastPP of the allocation | |
| 281 void split_AddP(Node *addp, Node *base, PhaseGVN *igvn); | |
| 282 PhiNode *create_split_phi(PhiNode *orig_phi, int alias_idx, GrowableArray<PhiNode *> &orig_phi_worklist, PhaseGVN *igvn, bool &new_created); | |
| 283 PhiNode *split_memory_phi(PhiNode *orig_phi, int alias_idx, GrowableArray<PhiNode *> &orig_phi_worklist, PhaseGVN *igvn); | |
| 284 Node *find_mem(Node *mem, int alias_idx, PhaseGVN *igvn); | |
| 65 | 285 Node *find_inst_mem(Node *mem, int alias_idx,GrowableArray<PhiNode *> &orig_phi_worklist, PhaseGVN *igvn); |
| 286 | |
| 0 | 287 // Propagate unique types created for unescaped allocated objects |
| 288 // through the graph | |
| 289 void split_unique_types(GrowableArray<Node *> &alloc_worklist); | |
| 290 | |
| 291 // manage entries in _node_map | |
| 292 void set_map(int idx, Node *n) { _node_map.map(idx, n); } | |
| 293 void set_map_phi(int idx, PhiNode *p) { _node_map.map(idx, (Node *) p); } | |
| 294 Node *get_map(int idx) { return _node_map[idx]; } | |
| 295 PhiNode *get_map_phi(int idx) { | |
| 296 Node *phi = _node_map[idx]; | |
| 297 return (phi == NULL) ? NULL : phi->as_Phi(); | |
| 298 } | |
| 299 | |
| 300 // Notify optimizer that a node has been modified | |
| 301 // Node: This assumes that escape analysis is run before | |
| 302 // PhaseIterGVN creation | |
| 303 void record_for_optimizer(Node *n) { | |
| 304 _compile->record_for_igvn(n); | |
| 305 } | |
| 306 | |
| 307 // Set the escape state of a node | |
| 308 void set_escape_state(uint ni, PointsToNode::EscapeState es); | |
| 309 | |
| 310 // Get Compile object for current compilation. | |
| 311 Compile *C() const { return _compile; } | |
| 312 | |
| 313 public: | |
| 314 ConnectionGraph(Compile *C); | |
| 315 | |
| 65 | 316 // Compute the escape information |
| 0 | 317 void compute_escape(); |
| 318 | |
| 319 // escape state of a node | |
| 320 PointsToNode::EscapeState escape_state(Node *n, PhaseTransform *phase); | |
| 65 | 321 // other information we have collected |
| 322 bool is_scalar_replaceable(Node *n) { | |
| 323 if (_collecting) | |
| 324 return false; | |
| 325 PointsToNode ptn = _nodes->at_grow(n->_idx); | |
| 326 return ptn.escape_state() == PointsToNode::NoEscape && ptn._scalar_replaceable; | |
| 327 } | |
| 0 | 328 |
| 329 bool hidden_alias(Node *n) { | |
| 330 if (_collecting) | |
| 331 return true; | |
| 332 PointsToNode ptn = _nodes->at_grow(n->_idx); | |
| 333 return (ptn.escape_state() != PointsToNode::NoEscape) || ptn._hidden_alias; | |
| 334 } | |
| 335 | |
| 336 #ifndef PRODUCT | |
| 337 void dump(); | |
| 338 #endif | |
| 339 }; |