Mercurial > jdk8-mips64-public > hotspot / file revision

 /*

  * Copyright (c) 2005, 2012, Oracle and/or its affiliates. All rights reserved.

  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.

  *

  * This code is free software; you can redistribute it and/or modify it

  * 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 "opto/node.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

 class PointsToNode : public ResourceObj {

   GrowableArray<PointsToNode*> _edges; // List of nodes this node points to

   GrowableArray<PointsToNode*> _uses;  // List of nodes which point to this node

   const u1           _type;  // NodeType

   u1                _flags;  // NodeFlags

   u1               _escape;  // EscapeState of object

   u1        _fields_escape;  // EscapeState of object's fields

   Node* const        _node;  // Ideal node corresponding to this PointsTo node.

   const int           _idx;  // Cached ideal node's _idx

 public:

   typedef enum {

     UnknownType = 0,

     JavaObject  = 1,

     LocalVar    = 2,

     Field       = 3,

     Arraycopy   = 4

   } NodeType;

   typedef enum {

     UnknownEscape = 0,

     NoEscape      = 1, // An object does not escape method or thread and it is

                        // not passed to call. It could be replaced with scalar.

     ArgEscape     = 2, // An object does not escape method or thread but it is

                        // passed as argument to call or referenced by argument

                        // and it does not escape during call.

     GlobalEscape  = 3  // An object escapes the method or thread.

   } EscapeState;

   typedef enum {

     ScalarReplaceable = 1,  // Not escaped object could be replaced with scalar

     PointsToUnknown   = 2,  // Has edge to phantom_object

     ArraycopySrc      = 4,  // Has edge from Arraycopy node

     ArraycopyDst      = 8   // Has edge to Arraycopy node

   } NodeFlags;

   PointsToNode(Compile *C, Node* n, EscapeState es, NodeType type):

     _edges(C->comp_arena(), 2, 0, NULL),

     _uses (C->comp_arena(), 2, 0, NULL),

     _node(n),

     _idx(n->_idx),

     _type((u1)type),

     _escape((u1)es),

     _fields_escape((u1)es),

     _flags(ScalarReplaceable) {

     assert(n != NULL && es != UnknownEscape, "sanity");

   }

   Node* ideal_node()   const { return _node; }

   int          idx()   const { return _idx; }

   bool is_JavaObject() const { return _type == (u1)JavaObject; }

   bool is_LocalVar()   const { return _type == (u1)LocalVar; }

   bool is_Field()      const { return _type == (u1)Field; }

   bool is_Arraycopy()  const { return _type == (u1)Arraycopy; }

   JavaObjectNode* as_JavaObject() { assert(is_JavaObject(),""); return (JavaObjectNode*)this; }

   LocalVarNode*   as_LocalVar()   { assert(is_LocalVar(),"");   return (LocalVarNode*)this; }

   FieldNode*      as_Field()      { assert(is_Field(),"");      return (FieldNode*)this; }

   ArraycopyNode*  as_Arraycopy()  { assert(is_Arraycopy(),"");  return (ArraycopyNode*)this; }

   EscapeState escape_state() const { return (EscapeState)_escape; }

   void    set_escape_state(EscapeState state) { _escape = (u1)state; }

   EscapeState fields_escape_state() const { return (EscapeState)_fields_escape; }

   void    set_fields_escape_state(EscapeState state) { _fields_escape = (u1)state; }

   bool     has_unknown_ptr() const { return (_flags & PointsToUnknown) != 0; }

   void set_has_unknown_ptr()       { _flags |= PointsToUnknown; }

   bool     arraycopy_src() const { return (_flags & ArraycopySrc) != 0; }

   void set_arraycopy_src()       { _flags |= ArraycopySrc; }

   bool     arraycopy_dst() const { return (_flags & ArraycopyDst) != 0; }

   void set_arraycopy_dst()       { _flags |= ArraycopyDst; }

   bool     scalar_replaceable() const { return (_flags & ScalarReplaceable) != 0;}

   void set_scalar_replaceable(bool v) {

     if (v)

       _flags |= ScalarReplaceable;

     else

       _flags &= ~ScalarReplaceable;

   }

   int edge_count()              const { return _edges.length(); }

   PointsToNode* edge(int e)     const { return _edges.at(e); }

   bool add_edge(PointsToNode* edge)    { return _edges.append_if_missing(edge); }

   int use_count()             const { return _uses.length(); }

   PointsToNode* use(int e)    const { return _uses.at(e); }

   bool add_use(PointsToNode* use)    { return _uses.append_if_missing(use); }

   // 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 bool is_base_use(PointsToNode* use) { return (((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.

   bool points_to(JavaObjectNode* ptn) const;

   // Return true if this node points only to non-escaping allocations.

   bool non_escaping_allocation();

   // Return true if one node points to an other.

   bool meet(PointsToNode* ptn);

 #ifndef PRODUCT

   NodeType node_type() const { return (NodeType)_type;}

   void dump(bool print_state=true) const;

 #endif

 };

 class LocalVarNode: public PointsToNode {

 public:

   LocalVarNode(Compile *C, Node* n, EscapeState es):

     PointsToNode(C, n, es, LocalVar) {}

 };

 class JavaObjectNode: public PointsToNode {

 public:

   JavaObjectNode(Compile *C, Node* n, EscapeState es):

     PointsToNode(C, n, es, JavaObject) {

       if (es > NoEscape)

         set_scalar_replaceable(false);

     }

 };

 class FieldNode: public PointsToNode {

   GrowableArray<PointsToNode*> _bases; // List of JavaObject nodes which point to this node

   const int   _offset; // Field's offset.

   const bool  _is_oop; // Field points to object

         bool  _has_unknown_base; // Has phantom_object base

 public:

   FieldNode(Compile *C, Node* n, EscapeState es, int offs, bool is_oop):

     PointsToNode(C, n, es, Field),

     _offset(offs), _is_oop(is_oop),

     _has_unknown_base(false) {}

   int      offset()              const { return _offset;}

   bool     is_oop()              const { return _is_oop;}

   bool     has_unknown_base()    const { return _has_unknown_base; }

   void set_has_unknown_base()          { _has_unknown_base = true; }

   int base_count()              const { return _bases.length(); }

   PointsToNode* base(int e)     const { return _bases.at(e); }

   bool add_base(PointsToNode* base)    { return _bases.append_if_missing(base); }

 #ifdef ASSERT

   // Return true if bases points to this java object.

   bool has_base(JavaObjectNode* ptn) const;

 #endif

 };

 class ArraycopyNode: public PointsToNode {

 public:

   ArraycopyNode(Compile *C, Node* n, EscapeState es):

     PointsToNode(C, n, es, Arraycopy) {}

 };

 // Iterators for PointsTo node's edges:

 //   for (EdgeIterator i(n); i.has_next(); i.next()) {

 //     PointsToNode* u = i.get();

 class PointsToIterator: public StackObj {

 protected:

   const PointsToNode* node;

   const int cnt;

   int i;

 public:

   inline PointsToIterator(const PointsToNode* n, int cnt) : node(n), cnt(cnt), i(0) { }

   inline bool has_next() const { return i < cnt; }

   inline void next() { i++; }

   PointsToNode* get() const { ShouldNotCallThis(); return NULL; }

 };

 class EdgeIterator: public PointsToIterator {

 public:

   inline EdgeIterator(const PointsToNode* n) : PointsToIterator(n, n->edge_count()) { }

   inline PointsToNode* get() const { return node->edge(i); }

 };

 class UseIterator: public PointsToIterator {

 public:

   inline UseIterator(const PointsToNode* n) : PointsToIterator(n, n->use_count()) { }

   inline PointsToNode* get() const { return node->use(i); }

 };

 class BaseIterator: public PointsToIterator {

 public:

   inline BaseIterator(const FieldNode* n) : PointsToIterator(n, n->base_count()) { }

   inline PointsToNode* get() const { return ((PointsToNode*)node)->as_Field()->base(i); }

 };

 class ConnectionGraph: public ResourceObj {

 private:

   GrowableArray<PointsToNode*>  _nodes; // Map from ideal nodes to

                                         // ConnectionGraph nodes.

   GrowableArray<PointsToNode*>  _worklist; // Nodes to be processed

   bool            _collecting; // Indicates whether escape information

                                // is still being collected. If false,

                                // no new nodes will be processed.

   bool               _verify;  // verify graph

   JavaObjectNode* phantom_obj; // Unknown object

   JavaObjectNode*    null_obj;

   Node*             _pcmp_neq; // ConI(#CC_GT)

   Node*              _pcmp_eq; // ConI(#CC_EQ)

   Compile*           _compile; // Compile object for current compilation

   PhaseIterGVN*         _igvn; // Value numbering

   Unique_Node_List ideal_nodes; // Used by CG construction and types splitting.

   // Address of an element in _nodes.  Used when the element is to be modified

   PointsToNode* ptnode_adr(int idx) const {

     // There should be no new ideal nodes during ConnectionGraph build,

     // growableArray::at() will throw assert otherwise.

     return _nodes.at(idx);

   }

   uint nodes_size() const { return _nodes.length(); }

   // Add nodes to ConnectionGraph.

   void add_local_var(Node* n, PointsToNode::EscapeState es);

   void add_java_object(Node* n, PointsToNode::EscapeState es);

   void add_field(Node* n, PointsToNode::EscapeState es, int offset);

   void add_arraycopy(Node* n, PointsToNode::EscapeState es, PointsToNode* src, PointsToNode* dst);

   // Compute the escape state for arguments to a call.

   void process_call_arguments(CallNode *call);

   // Add PointsToNode node corresponding to a call

   void add_call_node(CallNode* call);

   // Map ideal node to existing PointsTo node (usually phantom_object).

   void map_ideal_node(Node *n, PointsToNode* ptn) {

     assert(ptn != NULL, "only existing PointsTo node");

     _nodes.at_put(n->_idx, ptn);

   }

   // Utility function for nodes that load an object

   void add_objload_to_connection_graph(Node *n, Unique_Node_List *delayed_worklist);

   // Create PointsToNode node and add it to Connection Graph.

   void add_node_to_connection_graph(Node *n, Unique_Node_List *delayed_worklist);

   // Add final simple edges to graph.

   void add_final_edges(Node *n);

   // Finish Graph construction.

   bool complete_connection_graph(GrowableArray<PointsToNode*>&   ptnodes_worklist,

                                  GrowableArray<JavaObjectNode*>& non_escaped_worklist,

                                  GrowableArray<JavaObjectNode*>& java_objects_worklist,

                                  GrowableArray<FieldNode*>&      oop_fields_worklist);

 #ifdef ASSERT

   void verify_connection_graph(GrowableArray<PointsToNode*>&   ptnodes_worklist,

                                GrowableArray<JavaObjectNode*>& non_escaped_worklist,

                                GrowableArray<JavaObjectNode*>& java_objects_worklist,

                                GrowableArray<Node*>& addp_worklist);

 #endif

   // Add all references to this JavaObject node.

   int add_java_object_edges(JavaObjectNode* jobj, bool populate_worklist);

   // Put node on worklist if it is (or was) not there.

   void add_to_worklist(PointsToNode* pt) {

     _worklist.push(pt);

     return;

   }

   // Put on worklist all uses of this node.

   void add_uses_to_worklist(PointsToNode* pt) {

     for (UseIterator i(pt); i.has_next(); i.next())

       _worklist.push(i.get());

   }

   // Put on worklist all field's uses and related field nodes.

   void add_field_uses_to_worklist(FieldNode* field);

   // Put on worklist all related field nodes.

   void add_fields_to_worklist(FieldNode* field, PointsToNode* base);

   // Find fields which have unknown value.

   int find_field_value(FieldNode* field);

   // Find fields initializing values for allocations.

   int find_init_values(JavaObjectNode* ptn, PointsToNode* init_val, PhaseTransform* phase);

   // Set the escape state of an object and its fields.

   void set_escape_state(PointsToNode* ptn, PointsToNode::EscapeState esc) {

     // Don't change non-escaping state of NULL pointer.

     if (ptn != null_obj) {

       if (ptn->escape_state() < esc)

         ptn->set_escape_state(esc);

       if (ptn->fields_escape_state() < esc)

         ptn->set_fields_escape_state(esc);

     }

   }

   void set_fields_escape_state(PointsToNode* ptn, PointsToNode::EscapeState esc) {

     // Don't change non-escaping state of NULL pointer.

     if (ptn != null_obj) {

       if (ptn->fields_escape_state() < esc)

         ptn->set_fields_escape_state(esc);

     }

   }

   // Propagate GlobalEscape and ArgEscape escape states to all nodes

   // and check that we still have non-escaping java objects.

   bool find_non_escaped_objects(GrowableArray<PointsToNode*>& ptnodes_worklist,

                                 GrowableArray<JavaObjectNode*>& non_escaped_worklist);

   // Adjust scalar_replaceable state after Connection Graph is built.

   void adjust_scalar_replaceable_state(JavaObjectNode* jobj);

   // Optimize ideal graph.

   void optimize_ideal_graph(GrowableArray<Node*>& ptr_cmp_worklist,

                             GrowableArray<Node*>& storestore_worklist);

   // Optimize objects compare.

   Node* optimize_ptr_compare(Node* n);

   // Returns unique corresponding java object or NULL.

   JavaObjectNode* unique_java_object(Node *n);

   // Add an edge of the specified type pointing to the specified target.

   bool add_edge(PointsToNode* from, PointsToNode* to) {

     assert(!from->is_Field() || from->as_Field()->is_oop(), "sanity");

     if (to == phantom_obj) {

       if (from->has_unknown_ptr()) {

         return false; // already points to phantom_obj

       }

       from->set_has_unknown_ptr();

     }

     bool is_new = from->add_edge(to);

     assert(to != phantom_obj || is_new, "sanity");

     if (is_new) { // New edge?

       assert(!_verify, "graph is incomplete");

       is_new = to->add_use(from);

       assert(is_new, "use should be also new");

     }

     return is_new;

   }

   // Add an edge from Field node to its base and back.

   bool add_base(FieldNode* from, PointsToNode* to) {

     assert(!to->is_Arraycopy(), "sanity");

     if (to == phantom_obj) {

       if (from->has_unknown_base()) {

         return false; // already has phantom_obj base

       }

       from->set_has_unknown_base();

     }

     bool is_new = from->add_base(to);

     assert(to != phantom_obj || is_new, "sanity");

     if (is_new) {      // New edge?

       assert(!_verify, "graph is incomplete");

       if (to == null_obj)

         return is_new; // Don't add fields to NULL pointer.

       if (to->is_JavaObject()) {

         is_new = to->add_edge(from);

       } else {

         is_new = to->add_base_use(from);

       }

       assert(is_new, "use should be also new");

     }

     return is_new;

   }

   // Add LocalVar node and edge if possible

   void add_local_var_and_edge(Node* n, PointsToNode::EscapeState es, Node* to,

                               Unique_Node_List *delayed_worklist) {

     PointsToNode* ptn = ptnode_adr(to->_idx);

     if (delayed_worklist != NULL) { // First iteration of CG construction

       add_local_var(n, es);

       if (ptn == NULL) {

         delayed_worklist->push(n);

         return; // Process it later.

       }

     } else {

       assert(ptn != NULL, "node should be registered");

     }

     add_edge(ptnode_adr(n->_idx), ptn);

  }

   // Helper functions

   bool   is_oop_field(Node* n, int offset, bool* unsafe);

  static Node* get_addp_base(Node *addp);

  static Node* find_second_addp(Node* addp, Node* n);

   // offset of a field reference

   int address_offset(Node* adr, PhaseTransform *phase);

   // Propagate unique types created for unescaped allocated objects

   // through the graph

   void split_unique_types(GrowableArray<Node *>  &alloc_worklist);

   // Helper methods for unique types split.

   bool split_AddP(Node *addp, Node *base);

   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);

   void  move_inst_mem(Node* n, GrowableArray<PhiNode *>  &orig_phis);

   Node* find_inst_mem(Node* mem, int alias_idx,GrowableArray<PhiNode *>  &orig_phi_worklist);

   Node* step_through_mergemem(MergeMemNode *mmem, int alias_idx, const TypeOopPtr *toop);

   GrowableArray<MergeMemNode*>  _mergemem_worklist; // List of all MergeMem nodes

   Node_Array _node_map; // used for bookeeping during type splitting

                         // 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

   void  set_map(Node* from, Node* to)  {

     ideal_nodes.push(from);

     _node_map.map(from->_idx, to);

   }

   Node* get_map(int idx) { return _node_map[idx]; }

   PhiNode* get_map_phi(int idx) {

     Node* phi = _node_map[idx];

     return (phi == NULL) ? NULL : phi->as_Phi();

   }

   // Notify optimizer that a node has been modified

   void record_for_optimizer(Node *n) {

     _igvn->_worklist.push(n);

     _igvn->add_users_to_worklist(n);

   }

   // Compute the escape information

   bool compute_escape();

 public:

   ConnectionGraph(Compile *C, PhaseIterGVN *igvn);

   // Check for non-escaping candidates

   static bool has_candidates(Compile *C);

   // Perform escape analysis

   static void do_analysis(Compile *C, PhaseIterGVN *igvn);

   bool not_global_escape(Node *n);

 #ifndef PRODUCT

   void dump(GrowableArray<PointsToNode*>& ptnodes_worklist);

 #endif

 };

 #endif // SHARE_VM_OPTO_ESCAPE_HPP