escape.hpp revision 65
1879N/A * Copyright 2005-2006 Sun Microsystems, Inc. All Rights Reserved. 2327N/A * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 1010N/A * This code is free software; you can redistribute it and/or modify it 1010N/A * under the terms of the GNU General Public License version 2 only, as 1010N/A * published by the Free Software Foundation. 1010N/A * This code is distributed in the hope that it will be useful, but WITHOUT 1010N/A * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 1010N/A * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 1010N/A * version 2 for more details (a copy is included in the LICENSE file that 1010N/A * You should have received a copy of the GNU General Public License version 1010N/A * 2 along with this work; if not, write to the Free Software Foundation, 1010N/A * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 1010N/A * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara, 1472N/A * CA 95054 USA or visit www.sun.com if you need additional information or 1879N/A// Adaptation for C2 of the escape analysis algorithm described in: 1879N/A// [Choi99] Jong-Deok Shoi, Manish Gupta, Mauricio Seffano, 1879N/A// Vugranam C. Sreedhar, Sam Midkiff, 1879N/A// "Escape Analysis for Java", Procedings of ACM SIGPLAN 1879N/A// OOPSLA Conference, November 1, 1999 1879N/A// The flow-insensitive analysis described in the paper has been implemented. 1879N/A// The analysis requires construction of a "connection graph" (CG) for 1879N/A// the method being analyzed. The nodes of the connection graph are: 1879N/A// - Fields of an object (OF), these also include array elements 1879N/A// The CG contains 3 types of edges: 1879N/A// - PointsTo (-P>) {LV, OF} to JO 1879N/A// - Deferred (-D>) from {LV, OF} to {LV, OF} 1879N/A// - Field (-F>) from JO to OF 1879N/A// The following utility functions is used by the algorithm: 1879N/A// PointsTo(n) - n is any CG node, it returns the set of JO that n could 2327N/A// The algorithm describes how to construct the connection graph 2327N/A// in the following 4 cases: 1010N/A// (1) p = new T() LV -P> JO 1010N/A// (3) p.f = q JO -F> OF, OF -D> LV 1010N/A// (4) p = q.f JO -F> OF, LV -D> OF 1010N/A// In all these cases, p and q are local variables. For static field 1010N/A// references, we can construct a local variable containing a reference 1010N/A// C2 does not have local variables. However for the purposes of constructing 1010N/A// the connection graph, the following IR nodes are treated as local variables: 1010N/A// Proj#5 (value returned from callnodes including allocations) 1197N/A// The LoadP, Proj and CheckCastPP behave like variables assigned to only once. 1197N/A// Only a Phi can have multiple assignments. Each input to a Phi is treated 1010N/A// The following node types are JavaObject: // Parm (for incoming arguments) // CastX2P ("unsafe" operations) // AddP nodes are fields. // After building the graph, a pass is made over the nodes, deleting deferred // nodes and copying the edges from the target of the deferred edge to the // source. This results in a graph with no deferred edges, only: // OF -P> JO (the object whose oop is stored in the field) // Then, for each node which is GlobalEscape, anything it could point to // is marked GlobalEscape. Finally, for any node marked ArgEscape, anything // it could point to is marked ArgEscape. NoEscape =
1,
// A scalar replaceable object with unique type. ArgEscape =
2,
// An object passed as argument or referenced by // argument (and not globally escape during call). GlobalEscape =
3 // An object escapes the method and thread. Node*
_node;
// Ideal node corresponding to this PointsTo node. int _offset;
// Object fields offsets. // which may return it creating a hidden alias. // count of outgoing edges // node index of target of outgoing edge "e" // type of outgoing edge "e" // add a edge of the specified type pointing to the specified target // remove an edge of the specified type pointing to the specified target // the call build_connection_graph(). bool _collecting;
// Indicates whether escape information // is still being collected. If false, // no new nodes will be processed. // non-escaping allocations. // that pointer values loaded from // a field which has not been set // are assumed to point to. // address of an element in _nodes. Used when the element is to be modified // Add node to ConnectionGraph. // offset of a field reference // compute the escape state for arguments to a call // compute the escape state for the return value of a call // Populate Connection Graph with Ideal nodes. // Build Connection Graph and set nodes escape state. // walk the connection graph starting at the node corresponding to "n" and // add the index of everything it could point to, to "ptset". This may cause // Phi's encountered to get (re)processed (which requires "phase".) // Edge manipulation. The "from_i" and "to_i" arguments are the // node indices of the source and destination of the edge // Add an edge to node given by "to_i" from any field of adr_i whose offset // matches "offset" A deferred edge is added if to_i is a LocalVar, and // a pointsto edge is added if it is a JavaObject // Add a deferred edge from node given by "from_i" to any field // of adr_i whose offset matches "offset" // Remove outgoing deferred edges from the node referenced by "ni". // Any outgoing edges from the target of the deferred edge are copied // Used for the following purposes: // Memory Phi - most recent unique Phi split out // MemNode - new memory input for this node // ChecCastPP - allocation that this is a cast of // allocation - CheckCastPP of the allocation // Propagate unique types created for unescaped allocated objects // manage entries in _node_map // Notify optimizer that a node has been modified // Node: This assumes that escape analysis is run before // Set the escape state of a node // Get Compile object for current compilation. // Compute the escape information // escape state of a node // other information we have collected