Thu, 16 Feb 2012 17:12:49 -0800
7145346: VerifyStackAtCalls is broken
Summary: Replace call_epilog() encoding with macroassembler use. Moved duplicated code to x86.ad. Fixed return_addr() definition.
Reviewed-by: never
duke@435 | 1 | /* |
kvn@2556 | 2 | * Copyright (c) 2005, 2011, 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; |
duke@435 | 118 | class Type; |
duke@435 | 119 | class TypePtr; |
duke@435 | 120 | class VectorSet; |
duke@435 | 121 | |
duke@435 | 122 | class PointsToNode { |
duke@435 | 123 | friend class ConnectionGraph; |
duke@435 | 124 | public: |
duke@435 | 125 | typedef enum { |
kvn@500 | 126 | UnknownType = 0, |
kvn@500 | 127 | JavaObject = 1, |
kvn@500 | 128 | LocalVar = 2, |
kvn@500 | 129 | Field = 3 |
duke@435 | 130 | } NodeType; |
duke@435 | 131 | |
duke@435 | 132 | typedef enum { |
duke@435 | 133 | UnknownEscape = 0, |
kvn@3254 | 134 | NoEscape = 1, // An object does not escape method or thread and it is |
kvn@3254 | 135 | // not passed to call. It could be replaced with scalar. |
kvn@3254 | 136 | ArgEscape = 2, // An object does not escape method or thread but it is |
kvn@3254 | 137 | // passed as argument to call or referenced by argument |
kvn@3254 | 138 | // and it does not escape during call. |
kvn@3254 | 139 | GlobalEscape = 3 // An object escapes the method or thread. |
duke@435 | 140 | } EscapeState; |
duke@435 | 141 | |
duke@435 | 142 | typedef enum { |
duke@435 | 143 | UnknownEdge = 0, |
duke@435 | 144 | PointsToEdge = 1, |
duke@435 | 145 | DeferredEdge = 2, |
duke@435 | 146 | FieldEdge = 3 |
duke@435 | 147 | } EdgeType; |
duke@435 | 148 | |
duke@435 | 149 | private: |
duke@435 | 150 | enum { |
duke@435 | 151 | EdgeMask = 3, |
duke@435 | 152 | EdgeShift = 2, |
duke@435 | 153 | |
duke@435 | 154 | INITIAL_EDGE_COUNT = 4 |
duke@435 | 155 | }; |
duke@435 | 156 | |
duke@435 | 157 | NodeType _type; |
duke@435 | 158 | EscapeState _escape; |
kvn@3254 | 159 | GrowableArray<uint>* _edges; // outgoing edges |
kvn@3254 | 160 | Node* _node; // Ideal node corresponding to this PointsTo node. |
kvn@3254 | 161 | int _offset; // Object fields offsets. |
kvn@3254 | 162 | bool _scalar_replaceable; // Not escaped object could be replaced with scalar |
kvn@3318 | 163 | bool _has_unknown_ptr; // Has edge to phantom_object |
duke@435 | 164 | |
duke@435 | 165 | public: |
kvn@500 | 166 | PointsToNode(): |
kvn@500 | 167 | _type(UnknownType), |
kvn@500 | 168 | _escape(UnknownEscape), |
kvn@500 | 169 | _edges(NULL), |
kvn@500 | 170 | _node(NULL), |
kvn@500 | 171 | _offset(-1), |
kvn@3318 | 172 | _has_unknown_ptr(false), |
kvn@3254 | 173 | _scalar_replaceable(true) {} |
duke@435 | 174 | |
duke@435 | 175 | |
duke@435 | 176 | EscapeState escape_state() const { return _escape; } |
duke@435 | 177 | NodeType node_type() const { return _type;} |
duke@435 | 178 | int offset() { return _offset;} |
kvn@3254 | 179 | bool scalar_replaceable() { return _scalar_replaceable;} |
kvn@3318 | 180 | bool has_unknown_ptr() { return _has_unknown_ptr;} |
duke@435 | 181 | |
duke@435 | 182 | void set_offset(int offs) { _offset = offs;} |
duke@435 | 183 | void set_escape_state(EscapeState state) { _escape = state; } |
duke@435 | 184 | void set_node_type(NodeType ntype) { |
duke@435 | 185 | assert(_type == UnknownType || _type == ntype, "Can't change node type"); |
duke@435 | 186 | _type = ntype; |
duke@435 | 187 | } |
kvn@3254 | 188 | void set_scalar_replaceable(bool v) { _scalar_replaceable = v; } |
kvn@3318 | 189 | void set_has_unknown_ptr() { _has_unknown_ptr = true; } |
duke@435 | 190 | |
duke@435 | 191 | // count of outgoing edges |
duke@435 | 192 | uint edge_count() const { return (_edges == NULL) ? 0 : _edges->length(); } |
kvn@679 | 193 | |
duke@435 | 194 | // node index of target of outgoing edge "e" |
kvn@679 | 195 | uint edge_target(uint e) const { |
kvn@679 | 196 | assert(_edges != NULL, "valid edge index"); |
kvn@679 | 197 | return (_edges->at(e) >> EdgeShift); |
kvn@679 | 198 | } |
duke@435 | 199 | // type of outgoing edge "e" |
kvn@679 | 200 | EdgeType edge_type(uint e) const { |
kvn@679 | 201 | assert(_edges != NULL, "valid edge index"); |
kvn@679 | 202 | return (EdgeType) (_edges->at(e) & EdgeMask); |
kvn@679 | 203 | } |
kvn@679 | 204 | |
duke@435 | 205 | // add a edge of the specified type pointing to the specified target |
duke@435 | 206 | void add_edge(uint targIdx, EdgeType et); |
kvn@679 | 207 | |
duke@435 | 208 | // remove an edge of the specified type pointing to the specified target |
duke@435 | 209 | void remove_edge(uint targIdx, EdgeType et); |
kvn@679 | 210 | |
duke@435 | 211 | #ifndef PRODUCT |
kvn@688 | 212 | void dump(bool print_state=true) const; |
duke@435 | 213 | #endif |
duke@435 | 214 | |
duke@435 | 215 | }; |
duke@435 | 216 | |
duke@435 | 217 | class ConnectionGraph: public ResourceObj { |
duke@435 | 218 | private: |
kvn@679 | 219 | GrowableArray<PointsToNode> _nodes; // Connection graph nodes indexed |
kvn@500 | 220 | // by ideal node index. |
duke@435 | 221 | |
kvn@500 | 222 | Unique_Node_List _delayed_worklist; // Nodes to be processed before |
kvn@500 | 223 | // the call build_connection_graph(). |
duke@435 | 224 | |
kvn@1535 | 225 | GrowableArray<MergeMemNode *> _mergemem_worklist; // List of all MergeMem nodes |
kvn@1535 | 226 | |
kvn@500 | 227 | VectorSet _processed; // Records which nodes have been |
kvn@500 | 228 | // processed. |
kvn@500 | 229 | |
kvn@500 | 230 | bool _collecting; // Indicates whether escape information |
kvn@500 | 231 | // is still being collected. If false, |
kvn@500 | 232 | // no new nodes will be processed. |
kvn@500 | 233 | |
kvn@2276 | 234 | bool _progress; // Indicates whether new Graph's edges |
kvn@2276 | 235 | // were created. |
kvn@2276 | 236 | |
kvn@500 | 237 | uint _phantom_object; // Index of globally escaping object |
kvn@500 | 238 | // that pointer values loaded from |
kvn@500 | 239 | // a field which has not been set |
kvn@500 | 240 | // are assumed to point to. |
kvn@3254 | 241 | uint _oop_null; // ConP(#NULL)->_idx |
kvn@3254 | 242 | uint _noop_null; // ConN(#NULL)->_idx |
kvn@3309 | 243 | Node* _pcmp_neq; // ConI(#CC_GT) |
kvn@3309 | 244 | Node* _pcmp_eq; // ConI(#CC_EQ) |
kvn@500 | 245 | |
kvn@500 | 246 | Compile * _compile; // Compile object for current compilation |
kvn@1989 | 247 | PhaseIterGVN * _igvn; // Value numbering |
duke@435 | 248 | |
kvn@679 | 249 | // Address of an element in _nodes. Used when the element is to be modified |
kvn@679 | 250 | PointsToNode *ptnode_adr(uint idx) const { |
kvn@679 | 251 | // There should be no new ideal nodes during ConnectionGraph build, |
kvn@679 | 252 | // growableArray::adr_at() will throw assert otherwise. |
kvn@679 | 253 | return _nodes.adr_at(idx); |
duke@435 | 254 | } |
kvn@679 | 255 | uint nodes_size() const { return _nodes.length(); } |
duke@435 | 256 | |
kvn@3318 | 257 | bool is_null_ptr(uint idx) const { return (idx == _noop_null || idx == _oop_null); } |
kvn@3318 | 258 | |
kvn@500 | 259 | // Add node to ConnectionGraph. |
kvn@500 | 260 | void add_node(Node *n, PointsToNode::NodeType nt, PointsToNode::EscapeState es, bool done); |
kvn@500 | 261 | |
duke@435 | 262 | // offset of a field reference |
kvn@500 | 263 | int address_offset(Node* adr, PhaseTransform *phase); |
duke@435 | 264 | |
duke@435 | 265 | // compute the escape state for arguments to a call |
duke@435 | 266 | void process_call_arguments(CallNode *call, PhaseTransform *phase); |
duke@435 | 267 | |
duke@435 | 268 | // compute the escape state for the return value of a call |
duke@435 | 269 | void process_call_result(ProjNode *resproj, PhaseTransform *phase); |
duke@435 | 270 | |
kvn@500 | 271 | // Populate Connection Graph with Ideal nodes. |
kvn@500 | 272 | void record_for_escape_analysis(Node *n, PhaseTransform *phase); |
duke@435 | 273 | |
kvn@500 | 274 | // Build Connection Graph and set nodes escape state. |
kvn@500 | 275 | void build_connection_graph(Node *n, PhaseTransform *phase); |
duke@435 | 276 | |
duke@435 | 277 | // walk the connection graph starting at the node corresponding to "n" and |
duke@435 | 278 | // add the index of everything it could point to, to "ptset". This may cause |
duke@435 | 279 | // Phi's encountered to get (re)processed (which requires "phase".) |
kvn@2556 | 280 | VectorSet* PointsTo(Node * n); |
kvn@2556 | 281 | |
kvn@2556 | 282 | // Reused structures for PointsTo(). |
kvn@2556 | 283 | VectorSet pt_ptset; |
kvn@2556 | 284 | VectorSet pt_visited; |
kvn@2556 | 285 | GrowableArray<uint> pt_worklist; |
duke@435 | 286 | |
duke@435 | 287 | // Edge manipulation. The "from_i" and "to_i" arguments are the |
duke@435 | 288 | // node indices of the source and destination of the edge |
duke@435 | 289 | void add_pointsto_edge(uint from_i, uint to_i); |
duke@435 | 290 | void add_deferred_edge(uint from_i, uint to_i); |
duke@435 | 291 | void add_field_edge(uint from_i, uint to_i, int offs); |
duke@435 | 292 | |
kvn@2276 | 293 | // Add an edge of the specified type pointing to the specified target. |
kvn@2276 | 294 | // Set _progress if new edge is added. |
kvn@2276 | 295 | void add_edge(PointsToNode *f, uint to_i, PointsToNode::EdgeType et) { |
kvn@2276 | 296 | uint e_cnt = f->edge_count(); |
kvn@2276 | 297 | f->add_edge(to_i, et); |
kvn@2276 | 298 | _progress |= (f->edge_count() != e_cnt); |
kvn@2276 | 299 | } |
duke@435 | 300 | |
duke@435 | 301 | // Add an edge to node given by "to_i" from any field of adr_i whose offset |
duke@435 | 302 | // matches "offset" A deferred edge is added if to_i is a LocalVar, and |
duke@435 | 303 | // a pointsto edge is added if it is a JavaObject |
duke@435 | 304 | void add_edge_from_fields(uint adr, uint to_i, int offs); |
duke@435 | 305 | |
kvn@500 | 306 | // Add a deferred edge from node given by "from_i" to any field |
kvn@500 | 307 | // of adr_i whose offset matches "offset" |
duke@435 | 308 | void add_deferred_edge_to_fields(uint from_i, uint adr, int offs); |
duke@435 | 309 | |
duke@435 | 310 | |
duke@435 | 311 | // Remove outgoing deferred edges from the node referenced by "ni". |
duke@435 | 312 | // Any outgoing edges from the target of the deferred edge are copied |
duke@435 | 313 | // to "ni". |
kvn@536 | 314 | void remove_deferred(uint ni, GrowableArray<uint>* deferred_edges, VectorSet* visited); |
duke@435 | 315 | |
duke@435 | 316 | Node_Array _node_map; // used for bookeeping during type splitting |
duke@435 | 317 | // Used for the following purposes: |
duke@435 | 318 | // Memory Phi - most recent unique Phi split out |
duke@435 | 319 | // from this Phi |
duke@435 | 320 | // MemNode - new memory input for this node |
duke@435 | 321 | // ChecCastPP - allocation that this is a cast of |
duke@435 | 322 | // allocation - CheckCastPP of the allocation |
kvn@728 | 323 | bool split_AddP(Node *addp, Node *base, PhaseGVN *igvn); |
duke@435 | 324 | PhiNode *create_split_phi(PhiNode *orig_phi, int alias_idx, GrowableArray<PhiNode *> &orig_phi_worklist, PhaseGVN *igvn, bool &new_created); |
duke@435 | 325 | PhiNode *split_memory_phi(PhiNode *orig_phi, int alias_idx, GrowableArray<PhiNode *> &orig_phi_worklist, PhaseGVN *igvn); |
kvn@1536 | 326 | void move_inst_mem(Node* n, GrowableArray<PhiNode *> &orig_phis, PhaseGVN *igvn); |
kvn@500 | 327 | Node *find_inst_mem(Node *mem, int alias_idx,GrowableArray<PhiNode *> &orig_phi_worklist, PhaseGVN *igvn); |
kvn@500 | 328 | |
duke@435 | 329 | // Propagate unique types created for unescaped allocated objects |
duke@435 | 330 | // through the graph |
duke@435 | 331 | void split_unique_types(GrowableArray<Node *> &alloc_worklist); |
duke@435 | 332 | |
duke@435 | 333 | // manage entries in _node_map |
duke@435 | 334 | void set_map(int idx, Node *n) { _node_map.map(idx, n); } |
duke@435 | 335 | Node *get_map(int idx) { return _node_map[idx]; } |
duke@435 | 336 | PhiNode *get_map_phi(int idx) { |
duke@435 | 337 | Node *phi = _node_map[idx]; |
duke@435 | 338 | return (phi == NULL) ? NULL : phi->as_Phi(); |
duke@435 | 339 | } |
duke@435 | 340 | |
duke@435 | 341 | // Notify optimizer that a node has been modified |
duke@435 | 342 | void record_for_optimizer(Node *n) { |
kvn@1989 | 343 | _igvn->_worklist.push(n); |
kvn@3318 | 344 | _igvn->add_users_to_worklist(n); |
duke@435 | 345 | } |
duke@435 | 346 | |
duke@435 | 347 | // Set the escape state of a node |
duke@435 | 348 | void set_escape_state(uint ni, PointsToNode::EscapeState es); |
duke@435 | 349 | |
kvn@3254 | 350 | // Find fields initializing values for allocations. |
kvn@3254 | 351 | void find_init_values(Node* n, VectorSet* visited, PhaseTransform* phase); |
kvn@3254 | 352 | |
kvn@2556 | 353 | // Adjust escape state after Connection Graph is built. |
kvn@3254 | 354 | void adjust_escape_state(Node* n); |
kvn@3254 | 355 | |
kvn@3254 | 356 | // Propagate escape states to referenced nodes. |
kvn@3254 | 357 | bool propagate_escape_state(GrowableArray<int>* cg_worklist, |
kvn@3254 | 358 | GrowableArray<uint>* worklist, |
kvn@3254 | 359 | PointsToNode::EscapeState esc_state); |
kvn@2556 | 360 | |
kvn@3309 | 361 | // Optimize objects compare. |
kvn@3309 | 362 | Node* optimize_ptr_compare(Node* n); |
kvn@3309 | 363 | |
kvn@2556 | 364 | // Compute the escape information |
kvn@2556 | 365 | bool compute_escape(); |
kvn@1535 | 366 | |
duke@435 | 367 | public: |
kvn@1989 | 368 | ConnectionGraph(Compile *C, PhaseIterGVN *igvn); |
duke@435 | 369 | |
kvn@679 | 370 | // Check for non-escaping candidates |
kvn@679 | 371 | static bool has_candidates(Compile *C); |
kvn@679 | 372 | |
kvn@1989 | 373 | // Perform escape analysis |
kvn@1989 | 374 | static void do_analysis(Compile *C, PhaseIterGVN *igvn); |
kvn@1989 | 375 | |
duke@435 | 376 | // escape state of a node |
kvn@1989 | 377 | PointsToNode::EscapeState escape_state(Node *n); |
kvn@1989 | 378 | |
duke@435 | 379 | #ifndef PRODUCT |
duke@435 | 380 | void dump(); |
duke@435 | 381 | #endif |
duke@435 | 382 | }; |
stefank@2314 | 383 | |
stefank@2314 | 384 | #endif // SHARE_VM_OPTO_ESCAPE_HPP |