Mercurial > hg > truffle
annotate src/share/vm/opto/escape.hpp @ 1145:e018e6884bd8
6631166: CMS: better heuristics when combatting fragmentation
Summary: Autonomic per-worker free block cache sizing, tunable coalition policies, fixes to per-size block statistics, retuned gain and bandwidth of some feedback loop filters to allow quicker reactivity to abrupt changes in ambient demand, and other heuristics to reduce fragmentation of the CMS old gen. Also tightened some assertions, including those related to locking.
Reviewed-by: jmasa
| author | ysr |
|---|---|
| date | Wed, 23 Dec 2009 09:23:54 -0800 |
| parents | c3e045194476 |
| children | f96a1a986f7b |
| 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(); } | |
|
244
524eca34ea76
6684714: Optimize EA Connection Graph build performance
kvn
parents:
101
diff
changeset
|
181 |
| 0 | 182 // node index of target of outgoing edge "e" |
|
244
524eca34ea76
6684714: Optimize EA Connection Graph build performance
kvn
parents:
101
diff
changeset
|
183 uint edge_target(uint e) const { |
|
524eca34ea76
6684714: Optimize EA Connection Graph build performance
kvn
parents:
101
diff
changeset
|
184 assert(_edges != NULL, "valid edge index"); |
|
524eca34ea76
6684714: Optimize EA Connection Graph build performance
kvn
parents:
101
diff
changeset
|
185 return (_edges->at(e) >> EdgeShift); |
|
524eca34ea76
6684714: Optimize EA Connection Graph build performance
kvn
parents:
101
diff
changeset
|
186 } |
| 0 | 187 // type of outgoing edge "e" |
|
244
524eca34ea76
6684714: Optimize EA Connection Graph build performance
kvn
parents:
101
diff
changeset
|
188 EdgeType edge_type(uint e) const { |
|
524eca34ea76
6684714: Optimize EA Connection Graph build performance
kvn
parents:
101
diff
changeset
|
189 assert(_edges != NULL, "valid edge index"); |
|
524eca34ea76
6684714: Optimize EA Connection Graph build performance
kvn
parents:
101
diff
changeset
|
190 return (EdgeType) (_edges->at(e) & EdgeMask); |
|
524eca34ea76
6684714: Optimize EA Connection Graph build performance
kvn
parents:
101
diff
changeset
|
191 } |
|
524eca34ea76
6684714: Optimize EA Connection Graph build performance
kvn
parents:
101
diff
changeset
|
192 |
| 0 | 193 // add a edge of the specified type pointing to the specified target |
| 194 void add_edge(uint targIdx, EdgeType et); | |
|
244
524eca34ea76
6684714: Optimize EA Connection Graph build performance
kvn
parents:
101
diff
changeset
|
195 |
| 0 | 196 // remove an edge of the specified type pointing to the specified target |
| 197 void remove_edge(uint targIdx, EdgeType et); | |
|
244
524eca34ea76
6684714: Optimize EA Connection Graph build performance
kvn
parents:
101
diff
changeset
|
198 |
| 0 | 199 #ifndef PRODUCT |
|
253
b0fe4deeb9fb
6726999: nsk/stress/jck12a/jck12a010 assert(n != null,"Bad immediate dominator info.")
kvn
parents:
245
diff
changeset
|
200 void dump(bool print_state=true) const; |
| 0 | 201 #endif |
| 202 | |
| 203 }; | |
| 204 | |
| 205 class ConnectionGraph: public ResourceObj { | |
| 206 private: | |
|
244
524eca34ea76
6684714: Optimize EA Connection Graph build performance
kvn
parents:
101
diff
changeset
|
207 GrowableArray<PointsToNode> _nodes; // Connection graph nodes indexed |
| 65 | 208 // by ideal node index. |
| 0 | 209 |
| 65 | 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. | |
| 0 | 215 |
| 65 | 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. | |
|
253
b0fe4deeb9fb
6726999: nsk/stress/jck12a/jck12a010 assert(n != null,"Bad immediate dominator info.")
kvn
parents:
245
diff
changeset
|
224 uint _oop_null; // ConP(#NULL) |
|
b0fe4deeb9fb
6726999: nsk/stress/jck12a/jck12a010 assert(n != null,"Bad immediate dominator info.")
kvn
parents:
245
diff
changeset
|
225 uint _noop_null; // ConN(#NULL) |
| 65 | 226 |
| 227 Compile * _compile; // Compile object for current compilation | |
| 0 | 228 |
|
244
524eca34ea76
6684714: Optimize EA Connection Graph build performance
kvn
parents:
101
diff
changeset
|
229 // Address of an element in _nodes. Used when the element is to be modified |
|
524eca34ea76
6684714: Optimize EA Connection Graph build performance
kvn
parents:
101
diff
changeset
|
230 PointsToNode *ptnode_adr(uint idx) const { |
|
524eca34ea76
6684714: Optimize EA Connection Graph build performance
kvn
parents:
101
diff
changeset
|
231 // There should be no new ideal nodes during ConnectionGraph build, |
|
524eca34ea76
6684714: Optimize EA Connection Graph build performance
kvn
parents:
101
diff
changeset
|
232 // growableArray::adr_at() will throw assert otherwise. |
|
524eca34ea76
6684714: Optimize EA Connection Graph build performance
kvn
parents:
101
diff
changeset
|
233 return _nodes.adr_at(idx); |
| 0 | 234 } |
|
244
524eca34ea76
6684714: Optimize EA Connection Graph build performance
kvn
parents:
101
diff
changeset
|
235 uint nodes_size() const { return _nodes.length(); } |
| 0 | 236 |
| 65 | 237 // Add node to ConnectionGraph. |
| 238 void add_node(Node *n, PointsToNode::NodeType nt, PointsToNode::EscapeState es, bool done); | |
| 239 | |
| 0 | 240 // offset of a field reference |
| 65 | 241 int address_offset(Node* adr, PhaseTransform *phase); |
| 0 | 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 | |
| 65 | 249 // Populate Connection Graph with Ideal nodes. |
| 250 void record_for_escape_analysis(Node *n, PhaseTransform *phase); | |
| 0 | 251 |
| 65 | 252 // Build Connection Graph and set nodes escape state. |
| 253 void build_connection_graph(Node *n, PhaseTransform *phase); | |
| 0 | 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 | |
| 65 | 272 // Add a deferred edge from node given by "from_i" to any field |
| 273 // of adr_i whose offset matches "offset" | |
| 0 | 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". | |
|
101
a6cb86dd209b
6681577: PIT: some VM tests fails with -XX:+AggressiveOpts in 6u5p b01
kvn
parents:
65
diff
changeset
|
280 void remove_deferred(uint ni, GrowableArray<uint>* deferred_edges, VectorSet* visited); |
| 0 | 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 | |
|
293
c3e045194476
6731641: assert(m->adr_type() == mach->adr_type(),"matcher should not change adr type")
kvn
parents:
253
diff
changeset
|
289 bool split_AddP(Node *addp, Node *base, PhaseGVN *igvn); |
| 0 | 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); | |
| 65 | 293 Node *find_inst_mem(Node *mem, int alias_idx,GrowableArray<PhiNode *> &orig_phi_worklist, PhaseGVN *igvn); |
| 294 | |
| 0 | 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 | |
|
244
524eca34ea76
6684714: Optimize EA Connection Graph build performance
kvn
parents:
101
diff
changeset
|
321 // Check for non-escaping candidates |
|
524eca34ea76
6684714: Optimize EA Connection Graph build performance
kvn
parents:
101
diff
changeset
|
322 static bool has_candidates(Compile *C); |
|
524eca34ea76
6684714: Optimize EA Connection Graph build performance
kvn
parents:
101
diff
changeset
|
323 |
| 65 | 324 // Compute the escape information |
|
244
524eca34ea76
6684714: Optimize EA Connection Graph build performance
kvn
parents:
101
diff
changeset
|
325 bool compute_escape(); |
| 0 | 326 |
| 327 // escape state of a node | |
| 328 PointsToNode::EscapeState escape_state(Node *n, PhaseTransform *phase); | |
| 65 | 329 // other information we have collected |
| 330 bool is_scalar_replaceable(Node *n) { | |
|
244
524eca34ea76
6684714: Optimize EA Connection Graph build performance
kvn
parents:
101
diff
changeset
|
331 if (_collecting || (n->_idx >= nodes_size())) |
| 65 | 332 return false; |
|
244
524eca34ea76
6684714: Optimize EA Connection Graph build performance
kvn
parents:
101
diff
changeset
|
333 PointsToNode* ptn = ptnode_adr(n->_idx); |
|
524eca34ea76
6684714: Optimize EA Connection Graph build performance
kvn
parents:
101
diff
changeset
|
334 return ptn->escape_state() == PointsToNode::NoEscape && ptn->_scalar_replaceable; |
| 65 | 335 } |
| 0 | 336 |
| 337 bool hidden_alias(Node *n) { | |
|
244
524eca34ea76
6684714: Optimize EA Connection Graph build performance
kvn
parents:
101
diff
changeset
|
338 if (_collecting || (n->_idx >= nodes_size())) |
| 0 | 339 return true; |
|
244
524eca34ea76
6684714: Optimize EA Connection Graph build performance
kvn
parents:
101
diff
changeset
|
340 PointsToNode* ptn = ptnode_adr(n->_idx); |
|
524eca34ea76
6684714: Optimize EA Connection Graph build performance
kvn
parents:
101
diff
changeset
|
341 return (ptn->escape_state() != PointsToNode::NoEscape) || ptn->_hidden_alias; |
| 0 | 342 } |
| 343 | |
| 344 #ifndef PRODUCT | |
| 345 void dump(); | |
| 346 #endif | |
| 347 }; |