/*

 * Copyright 2005-2006 Sun Microsystems, Inc.  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 Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,

 * CA 95054 USA or visit www.sun.com if you need additional information or

 * have any questions.

 *

 */

//

// Adaptation for C2 of the escape analysis algorithm described in:

//

//

// The flow-insensitive analysis described in the paper has been implemented.

//

//

//     -  Java objects (JO)

//     -  Local variables (LV)

//     -  Fields of an object (OF),  these also include array elements

//

// The CG contains 3 types of edges:

//

//   -  Field     (-F>)    from JO to OF

//

// The following  utility functions is used by the algorithm:

//

//

//

//          Case                  Edges Created

//

//

//

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

//

// as an assignment to it.

//

//

//     top()

//     Allocate

//     AllocateArray

//     Parm  (for incoming arguments)

//     CreateEx

//     ConP

//     LoadKlass

//

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

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

class  TypePtr;

class  VectorSet;

class PointsToNode {

friend class ConnectionGraph;

public:

  typedef enum {

  } NodeType;

  typedef enum {

    UnknownEscape = 0,

  } EscapeState;

  typedef enum {

    UnknownEdge   = 0,

    PointsToEdge  = 1,

    DeferredEdge  = 2,

    FieldEdge     = 3

  } EdgeType;

private:

  enum {

    EdgeMask = 3,

    EdgeShift = 2,

    INITIAL_EDGE_COUNT = 4

  };

  NodeType             _type;

  EscapeState          _escape;

public:

  EscapeState escape_state() const { return _escape; }

  NodeType node_type() const { return _type;}

  int offset() { return _offset;}

  void set_offset(int offs) { _offset = offs;}

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

  void set_node_type(NodeType ntype) {

    assert(_type == UnknownType || _type == ntype, "Can't change node type");

    _type = ntype;

  }

  // count of outgoing edges

  uint edge_count() const { return (_edges == NULL) ? 0 : _edges->length(); }

  // node index of target of outgoing edge "e"

  uint edge_target(uint e)  const;

  // type of outgoing edge "e"

  EdgeType edge_type(uint e)  const;

  // add a edge of the specified type pointing to the specified target

  void add_edge(uint targIdx, EdgeType et);

  // remove an edge of the specified type pointing to the specified target

  void remove_edge(uint targIdx, EdgeType et);

#ifndef PRODUCT

  void dump() const;

#endif

};

class ConnectionGraph: public ResourceObj {

private:

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

  PointsToNode *ptnode_adr(uint idx) {

    if ((uint)_nodes->length() <= idx) {

      // expand _nodes array

      PointsToNode dummy = _nodes->at_grow(idx);

    }

    return _nodes->adr_at(idx);

  }

  // offset of a field reference

  // compute the escape state for arguments to a call

  void process_call_arguments(CallNode *call, PhaseTransform *phase);

  // compute the escape state for the return value of a call

  void process_call_result(ProjNode *resproj, PhaseTransform *phase);

  // 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".)

  void PointsTo(VectorSet &ptset, Node * n, PhaseTransform *phase);

  //  Edge manipulation.  The "from_i" and "to_i" arguments are the

  //  node indices of the source and destination of the edge

  void add_pointsto_edge(uint from_i, uint to_i);

  void add_deferred_edge(uint from_i, uint to_i);

  void add_field_edge(uint from_i, uint to_i, int offs);

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

  void add_edge_from_fields(uint adr, uint to_i, int offs);

  void add_deferred_edge_to_fields(uint from_i, uint adr, int offs);

  // Remove outgoing deferred edges from the node referenced by "ni".

  // Any outgoing edges from the target of the deferred edge are copied

  // to "ni".

  void remove_deferred(uint ni);

  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

  void split_AddP(Node *addp, Node *base,  PhaseGVN  *igvn);

  PhiNode *create_split_phi(PhiNode *orig_phi, int alias_idx, GrowableArray<PhiNode *>  &orig_phi_worklist, PhaseGVN  *igvn, bool &new_created);

  PhiNode *split_memory_phi(PhiNode *orig_phi, int alias_idx, GrowableArray<PhiNode *>  &orig_phi_worklist, PhaseGVN  *igvn);

  Node *find_mem(Node *mem, int alias_idx, PhaseGVN  *igvn);

  // Propagate unique types created for unescaped allocated objects

  // through the graph

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

  // manage entries in _node_map

  void  set_map(int idx, Node *n)        { _node_map.map(idx, n); }

  void  set_map_phi(int idx, PhiNode *p) { _node_map.map(idx, (Node *) p); }

  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

  // Node:  This assumes that escape analysis is run before

  //        PhaseIterGVN creation

  void record_for_optimizer(Node *n) {

    _compile->record_for_igvn(n);

  }

  // Set the escape state of a node

  void set_escape_state(uint ni, PointsToNode::EscapeState es);

  // Get Compile object for current compilation.

  Compile *C() const        { return _compile; }

public:

  ConnectionGraph(Compile *C);

  void compute_escape();

  // escape state of a node

  PointsToNode::EscapeState escape_state(Node *n, PhaseTransform *phase);

  bool hidden_alias(Node *n) {

    if (_collecting)

      return true;

    PointsToNode  ptn = _nodes->at_grow(n->_idx);

    return (ptn.escape_state() != PointsToNode::NoEscape) || ptn._hidden_alias;

  }

#ifndef PRODUCT

  void dump();

#endif

};