/*
* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
*
* under the terms of the GNU General Public License version 2 only, as
* published by the Free Software Foundation.
*
* This code is distributed in the hope that it will be useful, but WITHOUT
* ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
* FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
* version 2 for more details (a copy is included in the LICENSE file that
* accompanied this code).
*
* You should have received a copy of the GNU General Public License version
* 2 along with this work; if not, write to the Free Software Foundation,
* Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
*
* Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
* or visit www.oracle.com if you need additional information or have any
* questions.
*
*/
#ifndef SHARE_VM_OPTO_ESCAPE_HPP
#define SHARE_VM_OPTO_ESCAPE_HPP
#include "opto/addnode.hpp"
#include "utilities/growableArray.hpp"
//
// Adaptation for C2 of the escape analysis algorithm described in:
//
// [Choi99] Jong-Deok Shoi, Manish Gupta, Mauricio Seffano,
// Vugranam C. Sreedhar, Sam Midkiff,
// "Escape Analysis for Java", Procedings of ACM SIGPLAN
// OOPSLA Conference, November 1, 1999
//
// The flow-insensitive analysis described in the paper has been implemented.
//
// The analysis requires construction of a "connection graph" (CG) for
// the method being analyzed. The nodes of the connection graph are:
//
// - Java objects (JO)
// - Local variables (LV)
// - Fields of an object (OF), these also include array elements
//
// The CG contains 3 types of edges:
//
// - PointsTo (-P>) {LV, OF} to JO
// - Deferred (-D>) from {LV, OF} to {LV, OF}
// - Field (-F>) from JO to OF
//
// The following utility functions is used by the algorithm:
//
// PointsTo(n) - n is any CG node, it returns the set of JO that n could
// point to.
//
// The algorithm describes how to construct the connection graph
// in the following 4 cases:
//
// Case Edges Created
//
// (1) p = new T() LV -P> JO
// (2) p = q LV -D> LV
// (3) p.f = q JO -F> OF, OF -D> LV
// (4) p = q.f JO -F> OF, LV -D> OF
//
// In all these cases, p and q are local variables. For static field
// references, we can construct a local variable containing a reference
// to the static memory.
//
// C2 does not have local variables. However for the purposes of constructing
// the connection graph, the following IR nodes are treated as local variables:
// Phi (pointer values)
// LoadP, LoadN
// Proj#5 (value returned from callnodes including allocations)
// CheckCastPP, CastPP
//
// The LoadP, Proj and CheckCastPP behave like variables assigned to only once.
// Only a Phi can have multiple assignments. Each input to a Phi is treated
// as an assignment to it.
//
// The following node types are JavaObject:
//
// phantom_object (general globally escaped object)
// Allocate
// AllocateArray
// Parm (for incoming arguments)
// CastX2P ("unsafe" operations)
// CreateEx
// ConP
// LoadKlass
// ThreadLocal
// CallStaticJava (which returns Object)
//
// 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:
//
// LV -P> JO
// OF -P> JO (the object whose oop is stored in the field)
// JO -F> OF
//
// 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.
//
class Compile;
class Node;
class CallNode;
class PhiNode;
class PhaseTransform;
class PointsToNode;
class Type;
class TypePtr;
class VectorSet;
class JavaObjectNode;
class LocalVarNode;
class FieldNode;
class ArraycopyNode;
// ConnectionGraph nodes
public:
typedef enum {
UnknownType = 0,
} NodeType;
typedef enum {
UnknownEscape = 0,
// not passed to call. It could be replaced with scalar.
// passed as argument to call or referenced by argument
// and it does not escape during call.
} EscapeState;
typedef enum {
} NodeFlags;
_node(n),
}
void set_scalar_replaceable(bool v) {
if (v)
else
_flags &= ~ScalarReplaceable;
}
// Mark base edge use to distinguish from stored value edge.
bool add_base_use(FieldNode* use) { return _uses.append_if_missing((PointsToNode*)((intptr_t)use + 1)); }
static PointsToNode* get_use_node(PointsToNode* use) { return (PointsToNode*)(((intptr_t)use) & ~1); }
// Return true if this node points to specified node or nodes it points to.
// Return true if this node points only to non-escaping allocations.
bool non_escaping_allocation();
// Return true if one node points to an other.
#ifndef PRODUCT
void dump(bool print_state=true) const;
#endif
};
public:
};
public:
set_scalar_replaceable(false);
}
};
public:
_has_unknown_base(false) {}
#ifdef ASSERT
// Return true if bases points to this java object.
#endif
};
public:
};
// Iterators for PointsTo node's edges:
// for (EdgeIterator i(n); i.has_next(); i.next()) {
// PointsToNode* u = i.get();
protected:
const int cnt;
int i;
public:
inline void next() { i++; }
};
public:
};
public:
};
public:
};
private:
// ConnectionGraph nodes.
// is still being collected. If false,
// no new nodes will be processed.
// Address of an element in _nodes. Used when the element is to be modified
// There should be no new ideal nodes during ConnectionGraph build,
// growableArray::at() will throw assert otherwise.
}
// Add nodes to ConnectionGraph.
// Compute the escape state for arguments to a call.
// Add PointsToNode node corresponding to a call
// Map ideal node to existing PointsTo node (usually phantom_object).
}
// Utility function for nodes that load an object
// Create PointsToNode node and add it to Connection Graph.
// Add final simple edges to graph.
void add_final_edges(Node *n);
// Finish Graph construction.
#ifdef ASSERT
#endif
// Add all references to this JavaObject node.
// Put node on worklist if it is (or was) not there.
return;
}
// Put on worklist all uses of this node.
}
// Put on worklist all field's uses and related field nodes.
// Put on worklist all related field nodes.
// Find fields which have unknown value.
// Find fields initializing values for allocations.
// Set the escape state of an object and its fields.
// Don't change non-escaping state of NULL pointer.
}
}
// Don't change non-escaping state of NULL pointer.
}
}
// Propagate GlobalEscape and ArgEscape escape states to all nodes
// and check that we still have non-escaping java objects.
// Adjust scalar_replaceable state after Connection Graph is built.
// Optimize ideal graph.
// Optimize objects compare.
// Returns unique corresponding java object or NULL.
// Add an edge of the specified type pointing to the specified target.
if (to == phantom_obj) {
if (from->has_unknown_ptr()) {
return false; // already points to phantom_obj
}
}
if (is_new) { // New edge?
}
return is_new;
}
// Add an edge from Field node to its base and back.
if (to == phantom_obj) {
if (from->has_unknown_base()) {
return false; // already has phantom_obj base
}
}
if (is_new) { // New edge?
return is_new; // Don't add fields to NULL pointer.
if (to->is_JavaObject()) {
} else {
}
}
return is_new;
}
// Add LocalVar node and edge if possible
add_local_var(n, es);
delayed_worklist->push(n);
return; // Process it later.
}
} else {
}
}
// Helper functions
// offset of a field reference
// Propagate unique types created for unescaped allocated objects
// through the graph
// Helper methods for unique types split.
PhiNode *create_split_phi(PhiNode *orig_phi, int alias_idx, GrowableArray<PhiNode *> &orig_phi_worklist, bool &new_created);
PhiNode *split_memory_phi(PhiNode *orig_phi, int alias_idx, GrowableArray<PhiNode *> &orig_phi_worklist);
// Used for the following purposes:
// Memory Phi - most recent unique Phi split out
// from this Phi
// MemNode - new memory input for this node
// ChecCastPP - allocation that this is a cast of
// allocation - CheckCastPP of the allocation
// manage entries in _node_map
}
}
// Notify optimizer that a node has been modified
}
// Compute the escape information
bool compute_escape();
public:
// Check for non-escaping candidates
static bool has_candidates(Compile *C);
// Perform escape analysis
bool not_global_escape(Node *n);
#ifndef PRODUCT
#endif
};
#endif // SHARE_VM_OPTO_ESCAPE_HPP