Mon, 23 Jun 2014 13:33:23 +0200
8046289: compiler/6340864/TestLongVect.java timeout with
Reviewed-by: iveresov, vlivanov
duke@435 | 1 | /* |
kvn@3651 | 2 | * Copyright (c) 2005, 2012, Oracle and/or its affiliates. All rights reserved. |
duke@435 | 3 | * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. |
duke@435 | 4 | * |
duke@435 | 5 | * This code is free software; you can redistribute it and/or modify it |
duke@435 | 6 | * under the terms of the GNU General Public License version 2 only, as |
duke@435 | 7 | * published by the Free Software Foundation. |
duke@435 | 8 | * |
duke@435 | 9 | * This code is distributed in the hope that it will be useful, but WITHOUT |
duke@435 | 10 | * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or |
duke@435 | 11 | * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License |
duke@435 | 12 | * version 2 for more details (a copy is included in the LICENSE file that |
duke@435 | 13 | * accompanied this code). |
duke@435 | 14 | * |
duke@435 | 15 | * You should have received a copy of the GNU General Public License version |
duke@435 | 16 | * 2 along with this work; if not, write to the Free Software Foundation, |
duke@435 | 17 | * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. |
duke@435 | 18 | * |
trims@1907 | 19 | * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA |
trims@1907 | 20 | * or visit www.oracle.com if you need additional information or have any |
trims@1907 | 21 | * questions. |
duke@435 | 22 | * |
duke@435 | 23 | */ |
duke@435 | 24 | |
stefank@2314 | 25 | #ifndef SHARE_VM_OPTO_ESCAPE_HPP |
stefank@2314 | 26 | #define SHARE_VM_OPTO_ESCAPE_HPP |
stefank@2314 | 27 | |
stefank@2314 | 28 | #include "opto/addnode.hpp" |
stefank@2314 | 29 | #include "opto/node.hpp" |
stefank@2314 | 30 | #include "utilities/growableArray.hpp" |
stefank@2314 | 31 | |
duke@435 | 32 | // |
duke@435 | 33 | // Adaptation for C2 of the escape analysis algorithm described in: |
duke@435 | 34 | // |
kvn@500 | 35 | // [Choi99] Jong-Deok Shoi, Manish Gupta, Mauricio Seffano, |
kvn@500 | 36 | // Vugranam C. Sreedhar, Sam Midkiff, |
kvn@500 | 37 | // "Escape Analysis for Java", Procedings of ACM SIGPLAN |
kvn@500 | 38 | // OOPSLA Conference, November 1, 1999 |
duke@435 | 39 | // |
duke@435 | 40 | // The flow-insensitive analysis described in the paper has been implemented. |
duke@435 | 41 | // |
kvn@500 | 42 | // The analysis requires construction of a "connection graph" (CG) for |
kvn@500 | 43 | // the method being analyzed. The nodes of the connection graph are: |
duke@435 | 44 | // |
duke@435 | 45 | // - Java objects (JO) |
duke@435 | 46 | // - Local variables (LV) |
duke@435 | 47 | // - Fields of an object (OF), these also include array elements |
duke@435 | 48 | // |
duke@435 | 49 | // The CG contains 3 types of edges: |
duke@435 | 50 | // |
kvn@500 | 51 | // - PointsTo (-P>) {LV, OF} to JO |
kvn@500 | 52 | // - Deferred (-D>) from {LV, OF} to {LV, OF} |
duke@435 | 53 | // - Field (-F>) from JO to OF |
duke@435 | 54 | // |
duke@435 | 55 | // The following utility functions is used by the algorithm: |
duke@435 | 56 | // |
kvn@500 | 57 | // PointsTo(n) - n is any CG node, it returns the set of JO that n could |
kvn@500 | 58 | // point to. |
duke@435 | 59 | // |
kvn@500 | 60 | // The algorithm describes how to construct the connection graph |
kvn@500 | 61 | // in the following 4 cases: |
duke@435 | 62 | // |
duke@435 | 63 | // Case Edges Created |
duke@435 | 64 | // |
kvn@500 | 65 | // (1) p = new T() LV -P> JO |
kvn@500 | 66 | // (2) p = q LV -D> LV |
kvn@500 | 67 | // (3) p.f = q JO -F> OF, OF -D> LV |
kvn@500 | 68 | // (4) p = q.f JO -F> OF, LV -D> OF |
duke@435 | 69 | // |
kvn@500 | 70 | // In all these cases, p and q are local variables. For static field |
kvn@500 | 71 | // references, we can construct a local variable containing a reference |
kvn@500 | 72 | // to the static memory. |
duke@435 | 73 | // |
duke@435 | 74 | // C2 does not have local variables. However for the purposes of constructing |
duke@435 | 75 | // the connection graph, the following IR nodes are treated as local variables: |
duke@435 | 76 | // Phi (pointer values) |
kvn@3254 | 77 | // LoadP, LoadN |
kvn@500 | 78 | // Proj#5 (value returned from callnodes including allocations) |
kvn@500 | 79 | // CheckCastPP, CastPP |
duke@435 | 80 | // |
kvn@500 | 81 | // The LoadP, Proj and CheckCastPP behave like variables assigned to only once. |
kvn@500 | 82 | // Only a Phi can have multiple assignments. Each input to a Phi is treated |
duke@435 | 83 | // as an assignment to it. |
duke@435 | 84 | // |
kvn@500 | 85 | // The following node types are JavaObject: |
duke@435 | 86 | // |
kvn@3254 | 87 | // phantom_object (general globally escaped object) |
duke@435 | 88 | // Allocate |
duke@435 | 89 | // AllocateArray |
duke@435 | 90 | // Parm (for incoming arguments) |
kvn@500 | 91 | // CastX2P ("unsafe" operations) |
duke@435 | 92 | // CreateEx |
duke@435 | 93 | // ConP |
duke@435 | 94 | // LoadKlass |
kvn@500 | 95 | // ThreadLocal |
kvn@3254 | 96 | // CallStaticJava (which returns Object) |
duke@435 | 97 | // |
duke@435 | 98 | // AddP nodes are fields. |
duke@435 | 99 | // |
duke@435 | 100 | // After building the graph, a pass is made over the nodes, deleting deferred |
duke@435 | 101 | // nodes and copying the edges from the target of the deferred edge to the |
duke@435 | 102 | // source. This results in a graph with no deferred edges, only: |
duke@435 | 103 | // |
duke@435 | 104 | // LV -P> JO |
kvn@500 | 105 | // OF -P> JO (the object whose oop is stored in the field) |
duke@435 | 106 | // JO -F> OF |
duke@435 | 107 | // |
duke@435 | 108 | // Then, for each node which is GlobalEscape, anything it could point to |
duke@435 | 109 | // is marked GlobalEscape. Finally, for any node marked ArgEscape, anything |
duke@435 | 110 | // it could point to is marked ArgEscape. |
duke@435 | 111 | // |
duke@435 | 112 | |
duke@435 | 113 | class Compile; |
duke@435 | 114 | class Node; |
duke@435 | 115 | class CallNode; |
duke@435 | 116 | class PhiNode; |
duke@435 | 117 | class PhaseTransform; |
kvn@3651 | 118 | class PointsToNode; |
duke@435 | 119 | class Type; |
duke@435 | 120 | class TypePtr; |
duke@435 | 121 | class VectorSet; |
duke@435 | 122 | |
kvn@3651 | 123 | class JavaObjectNode; |
kvn@3651 | 124 | class LocalVarNode; |
kvn@3651 | 125 | class FieldNode; |
kvn@3651 | 126 | class ArraycopyNode; |
kvn@3651 | 127 | |
kvn@3651 | 128 | // ConnectionGraph nodes |
kvn@3651 | 129 | class PointsToNode : public ResourceObj { |
kvn@3651 | 130 | GrowableArray<PointsToNode*> _edges; // List of nodes this node points to |
kvn@3651 | 131 | GrowableArray<PointsToNode*> _uses; // List of nodes which point to this node |
kvn@3651 | 132 | |
kvn@3651 | 133 | const u1 _type; // NodeType |
kvn@3651 | 134 | u1 _flags; // NodeFlags |
kvn@3651 | 135 | u1 _escape; // EscapeState of object |
kvn@3651 | 136 | u1 _fields_escape; // EscapeState of object's fields |
kvn@3651 | 137 | |
kvn@3651 | 138 | Node* const _node; // Ideal node corresponding to this PointsTo node. |
kvn@3651 | 139 | const int _idx; // Cached ideal node's _idx |
kvn@3651 | 140 | |
duke@435 | 141 | public: |
duke@435 | 142 | typedef enum { |
kvn@500 | 143 | UnknownType = 0, |
kvn@500 | 144 | JavaObject = 1, |
kvn@500 | 145 | LocalVar = 2, |
kvn@3651 | 146 | Field = 3, |
kvn@3651 | 147 | Arraycopy = 4 |
duke@435 | 148 | } NodeType; |
duke@435 | 149 | |
duke@435 | 150 | typedef enum { |
duke@435 | 151 | UnknownEscape = 0, |
kvn@3254 | 152 | NoEscape = 1, // An object does not escape method or thread and it is |
kvn@3254 | 153 | // not passed to call. It could be replaced with scalar. |
kvn@3254 | 154 | ArgEscape = 2, // An object does not escape method or thread but it is |
kvn@3254 | 155 | // passed as argument to call or referenced by argument |
kvn@3254 | 156 | // and it does not escape during call. |
kvn@3254 | 157 | GlobalEscape = 3 // An object escapes the method or thread. |
duke@435 | 158 | } EscapeState; |
duke@435 | 159 | |
duke@435 | 160 | typedef enum { |
kvn@3651 | 161 | ScalarReplaceable = 1, // Not escaped object could be replaced with scalar |
kvn@3651 | 162 | PointsToUnknown = 2, // Has edge to phantom_object |
kvn@3651 | 163 | ArraycopySrc = 4, // Has edge from Arraycopy node |
kvn@3651 | 164 | ArraycopyDst = 8 // Has edge to Arraycopy node |
kvn@3651 | 165 | } NodeFlags; |
duke@435 | 166 | |
duke@435 | 167 | |
kvn@3651 | 168 | PointsToNode(Compile *C, Node* n, EscapeState es, NodeType type): |
kvn@3651 | 169 | _edges(C->comp_arena(), 2, 0, NULL), |
kvn@3651 | 170 | _uses (C->comp_arena(), 2, 0, NULL), |
kvn@3651 | 171 | _node(n), |
kvn@3651 | 172 | _idx(n->_idx), |
kvn@3651 | 173 | _type((u1)type), |
kvn@3651 | 174 | _escape((u1)es), |
kvn@3651 | 175 | _fields_escape((u1)es), |
kvn@3651 | 176 | _flags(ScalarReplaceable) { |
kvn@3651 | 177 | assert(n != NULL && es != UnknownEscape, "sanity"); |
kvn@679 | 178 | } |
kvn@679 | 179 | |
kvn@3651 | 180 | Node* ideal_node() const { return _node; } |
kvn@3651 | 181 | int idx() const { return _idx; } |
kvn@679 | 182 | |
kvn@3651 | 183 | bool is_JavaObject() const { return _type == (u1)JavaObject; } |
kvn@3651 | 184 | bool is_LocalVar() const { return _type == (u1)LocalVar; } |
kvn@3651 | 185 | bool is_Field() const { return _type == (u1)Field; } |
kvn@3651 | 186 | bool is_Arraycopy() const { return _type == (u1)Arraycopy; } |
kvn@3651 | 187 | |
kvn@3651 | 188 | JavaObjectNode* as_JavaObject() { assert(is_JavaObject(),""); return (JavaObjectNode*)this; } |
kvn@3651 | 189 | LocalVarNode* as_LocalVar() { assert(is_LocalVar(),""); return (LocalVarNode*)this; } |
kvn@3651 | 190 | FieldNode* as_Field() { assert(is_Field(),""); return (FieldNode*)this; } |
kvn@3651 | 191 | ArraycopyNode* as_Arraycopy() { assert(is_Arraycopy(),""); return (ArraycopyNode*)this; } |
kvn@3651 | 192 | |
kvn@3651 | 193 | EscapeState escape_state() const { return (EscapeState)_escape; } |
kvn@3651 | 194 | void set_escape_state(EscapeState state) { _escape = (u1)state; } |
kvn@3651 | 195 | |
kvn@3651 | 196 | EscapeState fields_escape_state() const { return (EscapeState)_fields_escape; } |
kvn@3651 | 197 | void set_fields_escape_state(EscapeState state) { _fields_escape = (u1)state; } |
kvn@3651 | 198 | |
kvn@3651 | 199 | bool has_unknown_ptr() const { return (_flags & PointsToUnknown) != 0; } |
kvn@3651 | 200 | void set_has_unknown_ptr() { _flags |= PointsToUnknown; } |
kvn@3651 | 201 | |
kvn@3651 | 202 | bool arraycopy_src() const { return (_flags & ArraycopySrc) != 0; } |
kvn@3651 | 203 | void set_arraycopy_src() { _flags |= ArraycopySrc; } |
kvn@3651 | 204 | bool arraycopy_dst() const { return (_flags & ArraycopyDst) != 0; } |
kvn@3651 | 205 | void set_arraycopy_dst() { _flags |= ArraycopyDst; } |
kvn@3651 | 206 | |
kvn@3651 | 207 | bool scalar_replaceable() const { return (_flags & ScalarReplaceable) != 0;} |
kvn@3651 | 208 | void set_scalar_replaceable(bool v) { |
kvn@3651 | 209 | if (v) |
kvn@3651 | 210 | _flags |= ScalarReplaceable; |
kvn@3651 | 211 | else |
kvn@3651 | 212 | _flags &= ~ScalarReplaceable; |
kvn@3651 | 213 | } |
kvn@3651 | 214 | |
kvn@3651 | 215 | int edge_count() const { return _edges.length(); } |
kvn@3651 | 216 | PointsToNode* edge(int e) const { return _edges.at(e); } |
kvn@3651 | 217 | bool add_edge(PointsToNode* edge) { return _edges.append_if_missing(edge); } |
kvn@3651 | 218 | |
kvn@3651 | 219 | int use_count() const { return _uses.length(); } |
kvn@3651 | 220 | PointsToNode* use(int e) const { return _uses.at(e); } |
kvn@3651 | 221 | bool add_use(PointsToNode* use) { return _uses.append_if_missing(use); } |
kvn@3651 | 222 | |
kvn@3651 | 223 | // Mark base edge use to distinguish from stored value edge. |
kvn@3651 | 224 | bool add_base_use(FieldNode* use) { return _uses.append_if_missing((PointsToNode*)((intptr_t)use + 1)); } |
kvn@3651 | 225 | static bool is_base_use(PointsToNode* use) { return (((intptr_t)use) & 1); } |
kvn@3651 | 226 | static PointsToNode* get_use_node(PointsToNode* use) { return (PointsToNode*)(((intptr_t)use) & ~1); } |
kvn@3651 | 227 | |
kvn@3651 | 228 | // Return true if this node points to specified node or nodes it points to. |
kvn@3651 | 229 | bool points_to(JavaObjectNode* ptn) const; |
kvn@3651 | 230 | |
kvn@3651 | 231 | // Return true if this node points only to non-escaping allocations. |
kvn@3651 | 232 | bool non_escaping_allocation(); |
kvn@3651 | 233 | |
kvn@3651 | 234 | // Return true if one node points to an other. |
kvn@3651 | 235 | bool meet(PointsToNode* ptn); |
kvn@679 | 236 | |
duke@435 | 237 | #ifndef PRODUCT |
kvn@3651 | 238 | NodeType node_type() const { return (NodeType)_type;} |
kvn@688 | 239 | void dump(bool print_state=true) const; |
duke@435 | 240 | #endif |
duke@435 | 241 | |
duke@435 | 242 | }; |
duke@435 | 243 | |
kvn@3651 | 244 | class LocalVarNode: public PointsToNode { |
kvn@3651 | 245 | public: |
kvn@3651 | 246 | LocalVarNode(Compile *C, Node* n, EscapeState es): |
kvn@3651 | 247 | PointsToNode(C, n, es, LocalVar) {} |
kvn@3651 | 248 | }; |
kvn@3651 | 249 | |
kvn@3651 | 250 | class JavaObjectNode: public PointsToNode { |
kvn@3651 | 251 | public: |
kvn@3651 | 252 | JavaObjectNode(Compile *C, Node* n, EscapeState es): |
kvn@3651 | 253 | PointsToNode(C, n, es, JavaObject) { |
kvn@3651 | 254 | if (es > NoEscape) |
kvn@3651 | 255 | set_scalar_replaceable(false); |
kvn@3651 | 256 | } |
kvn@3651 | 257 | }; |
kvn@3651 | 258 | |
kvn@3651 | 259 | class FieldNode: public PointsToNode { |
kvn@3651 | 260 | GrowableArray<PointsToNode*> _bases; // List of JavaObject nodes which point to this node |
kvn@3651 | 261 | const int _offset; // Field's offset. |
kvn@3651 | 262 | const bool _is_oop; // Field points to object |
kvn@3651 | 263 | bool _has_unknown_base; // Has phantom_object base |
kvn@3651 | 264 | public: |
kvn@3651 | 265 | FieldNode(Compile *C, Node* n, EscapeState es, int offs, bool is_oop): |
kvn@3651 | 266 | PointsToNode(C, n, es, Field), |
kvn@3651 | 267 | _offset(offs), _is_oop(is_oop), |
kvn@3651 | 268 | _has_unknown_base(false) {} |
kvn@3651 | 269 | |
kvn@3651 | 270 | int offset() const { return _offset;} |
kvn@3651 | 271 | bool is_oop() const { return _is_oop;} |
kvn@3651 | 272 | bool has_unknown_base() const { return _has_unknown_base; } |
kvn@3651 | 273 | void set_has_unknown_base() { _has_unknown_base = true; } |
kvn@3651 | 274 | |
kvn@3651 | 275 | int base_count() const { return _bases.length(); } |
kvn@3651 | 276 | PointsToNode* base(int e) const { return _bases.at(e); } |
kvn@3651 | 277 | bool add_base(PointsToNode* base) { return _bases.append_if_missing(base); } |
kvn@3651 | 278 | #ifdef ASSERT |
kvn@3651 | 279 | // Return true if bases points to this java object. |
kvn@3651 | 280 | bool has_base(JavaObjectNode* ptn) const; |
kvn@3651 | 281 | #endif |
kvn@3651 | 282 | |
kvn@3651 | 283 | }; |
kvn@3651 | 284 | |
kvn@3651 | 285 | class ArraycopyNode: public PointsToNode { |
kvn@3651 | 286 | public: |
kvn@3651 | 287 | ArraycopyNode(Compile *C, Node* n, EscapeState es): |
kvn@3651 | 288 | PointsToNode(C, n, es, Arraycopy) {} |
kvn@3651 | 289 | }; |
kvn@3651 | 290 | |
kvn@3651 | 291 | // Iterators for PointsTo node's edges: |
kvn@3651 | 292 | // for (EdgeIterator i(n); i.has_next(); i.next()) { |
kvn@3651 | 293 | // PointsToNode* u = i.get(); |
kvn@3651 | 294 | class PointsToIterator: public StackObj { |
kvn@3651 | 295 | protected: |
kvn@3651 | 296 | const PointsToNode* node; |
kvn@3651 | 297 | const int cnt; |
kvn@3651 | 298 | int i; |
kvn@3651 | 299 | public: |
kvn@3651 | 300 | inline PointsToIterator(const PointsToNode* n, int cnt) : node(n), cnt(cnt), i(0) { } |
kvn@3651 | 301 | inline bool has_next() const { return i < cnt; } |
kvn@3651 | 302 | inline void next() { i++; } |
kvn@3651 | 303 | PointsToNode* get() const { ShouldNotCallThis(); return NULL; } |
kvn@3651 | 304 | }; |
kvn@3651 | 305 | |
kvn@3651 | 306 | class EdgeIterator: public PointsToIterator { |
kvn@3651 | 307 | public: |
kvn@3651 | 308 | inline EdgeIterator(const PointsToNode* n) : PointsToIterator(n, n->edge_count()) { } |
kvn@3651 | 309 | inline PointsToNode* get() const { return node->edge(i); } |
kvn@3651 | 310 | }; |
kvn@3651 | 311 | |
kvn@3651 | 312 | class UseIterator: public PointsToIterator { |
kvn@3651 | 313 | public: |
kvn@3651 | 314 | inline UseIterator(const PointsToNode* n) : PointsToIterator(n, n->use_count()) { } |
kvn@3651 | 315 | inline PointsToNode* get() const { return node->use(i); } |
kvn@3651 | 316 | }; |
kvn@3651 | 317 | |
kvn@3651 | 318 | class BaseIterator: public PointsToIterator { |
kvn@3651 | 319 | public: |
kvn@3651 | 320 | inline BaseIterator(const FieldNode* n) : PointsToIterator(n, n->base_count()) { } |
kvn@3651 | 321 | inline PointsToNode* get() const { return ((PointsToNode*)node)->as_Field()->base(i); } |
kvn@3651 | 322 | }; |
kvn@3651 | 323 | |
kvn@3651 | 324 | |
duke@435 | 325 | class ConnectionGraph: public ResourceObj { |
duke@435 | 326 | private: |
kvn@3651 | 327 | GrowableArray<PointsToNode*> _nodes; // Map from ideal nodes to |
kvn@3651 | 328 | // ConnectionGraph nodes. |
duke@435 | 329 | |
kvn@3651 | 330 | GrowableArray<PointsToNode*> _worklist; // Nodes to be processed |
duke@435 | 331 | |
kvn@3651 | 332 | bool _collecting; // Indicates whether escape information |
kvn@3651 | 333 | // is still being collected. If false, |
kvn@3651 | 334 | // no new nodes will be processed. |
kvn@1535 | 335 | |
kvn@3651 | 336 | bool _verify; // verify graph |
kvn@500 | 337 | |
kvn@3651 | 338 | JavaObjectNode* phantom_obj; // Unknown object |
kvn@3651 | 339 | JavaObjectNode* null_obj; |
kvn@3651 | 340 | Node* _pcmp_neq; // ConI(#CC_GT) |
kvn@3651 | 341 | Node* _pcmp_eq; // ConI(#CC_EQ) |
kvn@500 | 342 | |
kvn@3651 | 343 | Compile* _compile; // Compile object for current compilation |
kvn@3651 | 344 | PhaseIterGVN* _igvn; // Value numbering |
kvn@2276 | 345 | |
kvn@3651 | 346 | Unique_Node_List ideal_nodes; // Used by CG construction and types splitting. |
duke@435 | 347 | |
kvn@679 | 348 | // Address of an element in _nodes. Used when the element is to be modified |
kvn@3651 | 349 | PointsToNode* ptnode_adr(int idx) const { |
kvn@679 | 350 | // There should be no new ideal nodes during ConnectionGraph build, |
kvn@3651 | 351 | // growableArray::at() will throw assert otherwise. |
kvn@3651 | 352 | return _nodes.at(idx); |
duke@435 | 353 | } |
kvn@679 | 354 | uint nodes_size() const { return _nodes.length(); } |
duke@435 | 355 | |
kvn@3651 | 356 | // Add nodes to ConnectionGraph. |
kvn@3651 | 357 | void add_local_var(Node* n, PointsToNode::EscapeState es); |
kvn@3651 | 358 | void add_java_object(Node* n, PointsToNode::EscapeState es); |
kvn@3651 | 359 | void add_field(Node* n, PointsToNode::EscapeState es, int offset); |
kvn@3651 | 360 | void add_arraycopy(Node* n, PointsToNode::EscapeState es, PointsToNode* src, PointsToNode* dst); |
kvn@3318 | 361 | |
kvn@3651 | 362 | // Compute the escape state for arguments to a call. |
kvn@3651 | 363 | void process_call_arguments(CallNode *call); |
kvn@3651 | 364 | |
kvn@3651 | 365 | // Add PointsToNode node corresponding to a call |
kvn@3651 | 366 | void add_call_node(CallNode* call); |
kvn@3651 | 367 | |
kvn@3651 | 368 | // Map ideal node to existing PointsTo node (usually phantom_object). |
kvn@3651 | 369 | void map_ideal_node(Node *n, PointsToNode* ptn) { |
kvn@3651 | 370 | assert(ptn != NULL, "only existing PointsTo node"); |
kvn@3651 | 371 | _nodes.at_put(n->_idx, ptn); |
kvn@3651 | 372 | } |
kvn@3651 | 373 | |
roland@4106 | 374 | // Utility function for nodes that load an object |
roland@4106 | 375 | void add_objload_to_connection_graph(Node *n, Unique_Node_List *delayed_worklist); |
kvn@3651 | 376 | // Create PointsToNode node and add it to Connection Graph. |
kvn@3651 | 377 | void add_node_to_connection_graph(Node *n, Unique_Node_List *delayed_worklist); |
kvn@3651 | 378 | |
kvn@3651 | 379 | // Add final simple edges to graph. |
kvn@3651 | 380 | void add_final_edges(Node *n); |
kvn@3651 | 381 | |
kvn@3651 | 382 | // Finish Graph construction. |
kvn@3651 | 383 | bool complete_connection_graph(GrowableArray<PointsToNode*>& ptnodes_worklist, |
kvn@3651 | 384 | GrowableArray<JavaObjectNode*>& non_escaped_worklist, |
kvn@3651 | 385 | GrowableArray<JavaObjectNode*>& java_objects_worklist, |
kvn@3651 | 386 | GrowableArray<FieldNode*>& oop_fields_worklist); |
kvn@3651 | 387 | |
kvn@3651 | 388 | #ifdef ASSERT |
kvn@3651 | 389 | void verify_connection_graph(GrowableArray<PointsToNode*>& ptnodes_worklist, |
kvn@3651 | 390 | GrowableArray<JavaObjectNode*>& non_escaped_worklist, |
kvn@3651 | 391 | GrowableArray<JavaObjectNode*>& java_objects_worklist, |
kvn@3651 | 392 | GrowableArray<Node*>& addp_worklist); |
kvn@3651 | 393 | #endif |
kvn@3651 | 394 | |
kvn@3651 | 395 | // Add all references to this JavaObject node. |
kvn@3651 | 396 | int add_java_object_edges(JavaObjectNode* jobj, bool populate_worklist); |
kvn@3651 | 397 | |
kvn@3651 | 398 | // Put node on worklist if it is (or was) not there. |
kvn@3651 | 399 | void add_to_worklist(PointsToNode* pt) { |
kvn@3651 | 400 | _worklist.push(pt); |
kvn@3651 | 401 | return; |
kvn@3651 | 402 | } |
kvn@3651 | 403 | |
kvn@3651 | 404 | // Put on worklist all uses of this node. |
kvn@3651 | 405 | void add_uses_to_worklist(PointsToNode* pt) { |
kvn@3651 | 406 | for (UseIterator i(pt); i.has_next(); i.next()) |
kvn@3651 | 407 | _worklist.push(i.get()); |
kvn@3651 | 408 | } |
kvn@3651 | 409 | |
kvn@3651 | 410 | // Put on worklist all field's uses and related field nodes. |
kvn@3651 | 411 | void add_field_uses_to_worklist(FieldNode* field); |
kvn@3651 | 412 | |
kvn@3651 | 413 | // Put on worklist all related field nodes. |
kvn@3651 | 414 | void add_fields_to_worklist(FieldNode* field, PointsToNode* base); |
kvn@3651 | 415 | |
kvn@3651 | 416 | // Find fields which have unknown value. |
kvn@3651 | 417 | int find_field_value(FieldNode* field); |
kvn@3651 | 418 | |
kvn@3651 | 419 | // Find fields initializing values for allocations. |
kvn@3651 | 420 | int find_init_values(JavaObjectNode* ptn, PointsToNode* init_val, PhaseTransform* phase); |
kvn@3651 | 421 | |
kvn@3651 | 422 | // Set the escape state of an object and its fields. |
kvn@3651 | 423 | void set_escape_state(PointsToNode* ptn, PointsToNode::EscapeState esc) { |
kvn@3651 | 424 | // Don't change non-escaping state of NULL pointer. |
kvn@3651 | 425 | if (ptn != null_obj) { |
kvn@3651 | 426 | if (ptn->escape_state() < esc) |
kvn@3651 | 427 | ptn->set_escape_state(esc); |
kvn@3651 | 428 | if (ptn->fields_escape_state() < esc) |
kvn@3651 | 429 | ptn->set_fields_escape_state(esc); |
kvn@3651 | 430 | } |
kvn@3651 | 431 | } |
kvn@3651 | 432 | void set_fields_escape_state(PointsToNode* ptn, PointsToNode::EscapeState esc) { |
kvn@3651 | 433 | // Don't change non-escaping state of NULL pointer. |
kvn@3651 | 434 | if (ptn != null_obj) { |
kvn@3651 | 435 | if (ptn->fields_escape_state() < esc) |
kvn@3651 | 436 | ptn->set_fields_escape_state(esc); |
kvn@3651 | 437 | } |
kvn@3651 | 438 | } |
kvn@3651 | 439 | |
kvn@3651 | 440 | // Propagate GlobalEscape and ArgEscape escape states to all nodes |
kvn@3651 | 441 | // and check that we still have non-escaping java objects. |
kvn@3651 | 442 | bool find_non_escaped_objects(GrowableArray<PointsToNode*>& ptnodes_worklist, |
kvn@3651 | 443 | GrowableArray<JavaObjectNode*>& non_escaped_worklist); |
kvn@3651 | 444 | |
kvn@3651 | 445 | // Adjust scalar_replaceable state after Connection Graph is built. |
kvn@3651 | 446 | void adjust_scalar_replaceable_state(JavaObjectNode* jobj); |
kvn@3651 | 447 | |
kvn@3651 | 448 | // Optimize ideal graph. |
kvn@3651 | 449 | void optimize_ideal_graph(GrowableArray<Node*>& ptr_cmp_worklist, |
kvn@3651 | 450 | GrowableArray<Node*>& storestore_worklist); |
kvn@3651 | 451 | // Optimize objects compare. |
kvn@3651 | 452 | Node* optimize_ptr_compare(Node* n); |
kvn@3651 | 453 | |
kvn@3651 | 454 | // Returns unique corresponding java object or NULL. |
kvn@3651 | 455 | JavaObjectNode* unique_java_object(Node *n); |
kvn@3651 | 456 | |
kvn@3651 | 457 | // Add an edge of the specified type pointing to the specified target. |
kvn@3651 | 458 | bool add_edge(PointsToNode* from, PointsToNode* to) { |
kvn@3651 | 459 | assert(!from->is_Field() || from->as_Field()->is_oop(), "sanity"); |
kvn@3651 | 460 | |
kvn@3651 | 461 | if (to == phantom_obj) { |
kvn@3651 | 462 | if (from->has_unknown_ptr()) { |
kvn@3651 | 463 | return false; // already points to phantom_obj |
kvn@3651 | 464 | } |
kvn@3651 | 465 | from->set_has_unknown_ptr(); |
kvn@3651 | 466 | } |
kvn@3651 | 467 | |
kvn@3651 | 468 | bool is_new = from->add_edge(to); |
kvn@3651 | 469 | assert(to != phantom_obj || is_new, "sanity"); |
kvn@3651 | 470 | if (is_new) { // New edge? |
kvn@3651 | 471 | assert(!_verify, "graph is incomplete"); |
kvn@3651 | 472 | is_new = to->add_use(from); |
kvn@3651 | 473 | assert(is_new, "use should be also new"); |
kvn@3651 | 474 | } |
kvn@3651 | 475 | return is_new; |
kvn@3651 | 476 | } |
kvn@3651 | 477 | |
kvn@3651 | 478 | // Add an edge from Field node to its base and back. |
kvn@3651 | 479 | bool add_base(FieldNode* from, PointsToNode* to) { |
kvn@3651 | 480 | assert(!to->is_Arraycopy(), "sanity"); |
kvn@3651 | 481 | if (to == phantom_obj) { |
kvn@3651 | 482 | if (from->has_unknown_base()) { |
kvn@3651 | 483 | return false; // already has phantom_obj base |
kvn@3651 | 484 | } |
kvn@3651 | 485 | from->set_has_unknown_base(); |
kvn@3651 | 486 | } |
kvn@3651 | 487 | bool is_new = from->add_base(to); |
kvn@3651 | 488 | assert(to != phantom_obj || is_new, "sanity"); |
kvn@3651 | 489 | if (is_new) { // New edge? |
kvn@3651 | 490 | assert(!_verify, "graph is incomplete"); |
kvn@3651 | 491 | if (to == null_obj) |
kvn@3651 | 492 | return is_new; // Don't add fields to NULL pointer. |
kvn@3651 | 493 | if (to->is_JavaObject()) { |
kvn@3651 | 494 | is_new = to->add_edge(from); |
kvn@3651 | 495 | } else { |
kvn@3651 | 496 | is_new = to->add_base_use(from); |
kvn@3651 | 497 | } |
kvn@3651 | 498 | assert(is_new, "use should be also new"); |
kvn@3651 | 499 | } |
kvn@3651 | 500 | return is_new; |
kvn@3651 | 501 | } |
kvn@3651 | 502 | |
kvn@3651 | 503 | // Add LocalVar node and edge if possible |
kvn@3651 | 504 | void add_local_var_and_edge(Node* n, PointsToNode::EscapeState es, Node* to, |
kvn@3651 | 505 | Unique_Node_List *delayed_worklist) { |
kvn@3651 | 506 | PointsToNode* ptn = ptnode_adr(to->_idx); |
kvn@3651 | 507 | if (delayed_worklist != NULL) { // First iteration of CG construction |
kvn@3651 | 508 | add_local_var(n, es); |
kvn@3651 | 509 | if (ptn == NULL) { |
kvn@3651 | 510 | delayed_worklist->push(n); |
kvn@3651 | 511 | return; // Process it later. |
kvn@3651 | 512 | } |
kvn@3651 | 513 | } else { |
kvn@3651 | 514 | assert(ptn != NULL, "node should be registered"); |
kvn@3651 | 515 | } |
kvn@3651 | 516 | add_edge(ptnode_adr(n->_idx), ptn); |
twisti@3969 | 517 | } |
kvn@3651 | 518 | // Helper functions |
twisti@3969 | 519 | bool is_oop_field(Node* n, int offset, bool* unsafe); |
twisti@3969 | 520 | static Node* get_addp_base(Node *addp); |
twisti@3969 | 521 | static Node* find_second_addp(Node* addp, Node* n); |
duke@435 | 522 | // offset of a field reference |
kvn@500 | 523 | int address_offset(Node* adr, PhaseTransform *phase); |
duke@435 | 524 | |
duke@435 | 525 | |
kvn@3651 | 526 | // Propagate unique types created for unescaped allocated objects |
kvn@3651 | 527 | // through the graph |
kvn@3651 | 528 | void split_unique_types(GrowableArray<Node *> &alloc_worklist); |
duke@435 | 529 | |
kvn@3651 | 530 | // Helper methods for unique types split. |
kvn@3651 | 531 | bool split_AddP(Node *addp, Node *base); |
duke@435 | 532 | |
kvn@3651 | 533 | PhiNode *create_split_phi(PhiNode *orig_phi, int alias_idx, GrowableArray<PhiNode *> &orig_phi_worklist, bool &new_created); |
kvn@3651 | 534 | PhiNode *split_memory_phi(PhiNode *orig_phi, int alias_idx, GrowableArray<PhiNode *> &orig_phi_worklist); |
duke@435 | 535 | |
kvn@3651 | 536 | void move_inst_mem(Node* n, GrowableArray<PhiNode *> &orig_phis); |
kvn@3651 | 537 | Node* find_inst_mem(Node* mem, int alias_idx,GrowableArray<PhiNode *> &orig_phi_worklist); |
kvn@3651 | 538 | Node* step_through_mergemem(MergeMemNode *mmem, int alias_idx, const TypeOopPtr *toop); |
kvn@2556 | 539 | |
duke@435 | 540 | |
kvn@3651 | 541 | GrowableArray<MergeMemNode*> _mergemem_worklist; // List of all MergeMem nodes |
duke@435 | 542 | |
duke@435 | 543 | Node_Array _node_map; // used for bookeeping during type splitting |
duke@435 | 544 | // Used for the following purposes: |
duke@435 | 545 | // Memory Phi - most recent unique Phi split out |
duke@435 | 546 | // from this Phi |
duke@435 | 547 | // MemNode - new memory input for this node |
duke@435 | 548 | // ChecCastPP - allocation that this is a cast of |
duke@435 | 549 | // allocation - CheckCastPP of the allocation |
duke@435 | 550 | |
duke@435 | 551 | // manage entries in _node_map |
kvn@3651 | 552 | |
kvn@3651 | 553 | void set_map(Node* from, Node* to) { |
kvn@3651 | 554 | ideal_nodes.push(from); |
kvn@3651 | 555 | _node_map.map(from->_idx, to); |
kvn@3651 | 556 | } |
kvn@3651 | 557 | |
kvn@3651 | 558 | Node* get_map(int idx) { return _node_map[idx]; } |
kvn@3651 | 559 | |
kvn@3651 | 560 | PhiNode* get_map_phi(int idx) { |
kvn@3651 | 561 | Node* phi = _node_map[idx]; |
duke@435 | 562 | return (phi == NULL) ? NULL : phi->as_Phi(); |
duke@435 | 563 | } |
duke@435 | 564 | |
duke@435 | 565 | // Notify optimizer that a node has been modified |
duke@435 | 566 | void record_for_optimizer(Node *n) { |
kvn@1989 | 567 | _igvn->_worklist.push(n); |
kvn@3318 | 568 | _igvn->add_users_to_worklist(n); |
duke@435 | 569 | } |
duke@435 | 570 | |
kvn@2556 | 571 | // Compute the escape information |
kvn@2556 | 572 | bool compute_escape(); |
kvn@1535 | 573 | |
duke@435 | 574 | public: |
kvn@1989 | 575 | ConnectionGraph(Compile *C, PhaseIterGVN *igvn); |
duke@435 | 576 | |
kvn@679 | 577 | // Check for non-escaping candidates |
kvn@679 | 578 | static bool has_candidates(Compile *C); |
kvn@679 | 579 | |
kvn@1989 | 580 | // Perform escape analysis |
kvn@1989 | 581 | static void do_analysis(Compile *C, PhaseIterGVN *igvn); |
kvn@1989 | 582 | |
kvn@3651 | 583 | bool not_global_escape(Node *n); |
kvn@1989 | 584 | |
duke@435 | 585 | #ifndef PRODUCT |
kvn@3651 | 586 | void dump(GrowableArray<PointsToNode*>& ptnodes_worklist); |
duke@435 | 587 | #endif |
duke@435 | 588 | }; |
stefank@2314 | 589 | |
stefank@2314 | 590 | #endif // SHARE_VM_OPTO_ESCAPE_HPP |