/*

 * 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.

 *

 */

#include "incls/_precompiled.incl"

#include "incls/_escape.cpp.incl"

uint PointsToNode::edge_target(uint e) const {

  assert(_edges != NULL && e < (uint)_edges->length(), "valid edge index");

  return (_edges->at(e) >> EdgeShift);

}

PointsToNode::EdgeType PointsToNode::edge_type(uint e) const {

  assert(_edges != NULL && e < (uint)_edges->length(), "valid edge index");

  return (EdgeType) (_edges->at(e) & EdgeMask);

}

void PointsToNode::add_edge(uint targIdx, PointsToNode::EdgeType et) {

  uint v = (targIdx << EdgeShift) + ((uint) et);

  if (_edges == NULL) {

     Arena *a = Compile::current()->comp_arena();

    _edges = new(a) GrowableArray<uint>(a, INITIAL_EDGE_COUNT, 0, 0);

  }

  _edges->append_if_missing(v);

}

void PointsToNode::remove_edge(uint targIdx, PointsToNode::EdgeType et) {

  uint v = (targIdx << EdgeShift) + ((uint) et);

  _edges->remove(v);

}

#ifndef PRODUCT

static char *node_type_names[] = {

  "UnknownType",

  "JavaObject",

  "LocalVar",

  "Field"

};

static char *esc_names[] = {

  "UnknownEscape",

  "NoEscape     ",

  "ArgEscape    ",

  "GlobalEscape "

};

static char *edge_type_suffix[] = {

 "?", // UnknownEdge

 "P", // PointsToEdge

 "D", // DeferredEdge

 "F"  // FieldEdge

};

void PointsToNode::dump() const {

  NodeType nt = node_type();

  EscapeState es = escape_state();

  tty->print("%s  %s  [[", node_type_names[(int) nt], esc_names[(int) es]);

  for (uint i = 0; i < edge_count(); i++) {

    tty->print(" %d%s", edge_target(i), edge_type_suffix[(int) edge_type(i)]);

  }

  tty->print("]]  ");

  if (_node == NULL)

    tty->print_cr("<null>");

  else

    _node->dump();

}

#endif

ConnectionGraph::ConnectionGraph(Compile * C) : _processed(C->comp_arena()), _node_map(C->comp_arena()) {

  _collecting = true;

  this->_compile = C;

  const PointsToNode &dummy = PointsToNode();

  _nodes = new(C->comp_arena()) GrowableArray<PointsToNode>(C->comp_arena(), (int) INITIAL_NODE_COUNT, 0, dummy);

  _phantom_object = C->top()->_idx;

  PointsToNode *phn = ptnode_adr(_phantom_object);

  phn->set_node_type(PointsToNode::JavaObject);

  phn->set_escape_state(PointsToNode::GlobalEscape);

}

void ConnectionGraph::add_pointsto_edge(uint from_i, uint to_i) {

  PointsToNode *f = ptnode_adr(from_i);

  PointsToNode *t = ptnode_adr(to_i);

  assert(f->node_type() != PointsToNode::UnknownType && t->node_type() != PointsToNode::UnknownType, "node types must be set");

  assert(f->node_type() == PointsToNode::LocalVar || f->node_type() == PointsToNode::Field, "invalid source of PointsTo edge");

  assert(t->node_type() == PointsToNode::JavaObject, "invalid destination of PointsTo edge");

  f->add_edge(to_i, PointsToNode::PointsToEdge);

}

void ConnectionGraph::add_deferred_edge(uint from_i, uint to_i) {

  PointsToNode *f = ptnode_adr(from_i);

  PointsToNode *t = ptnode_adr(to_i);

  assert(f->node_type() != PointsToNode::UnknownType && t->node_type() != PointsToNode::UnknownType, "node types must be set");

  assert(f->node_type() == PointsToNode::LocalVar || f->node_type() == PointsToNode::Field, "invalid source of Deferred edge");

  assert(t->node_type() == PointsToNode::LocalVar || t->node_type() == PointsToNode::Field, "invalid destination of Deferred edge");

  // don't add a self-referential edge, this can occur during removal of

  // deferred edges

  if (from_i != to_i)

    f->add_edge(to_i, PointsToNode::DeferredEdge);

}

int ConnectionGraph::type_to_offset(const Type *t) {

  const TypePtr *t_ptr = t->isa_ptr();

  assert(t_ptr != NULL, "must be a pointer type");

  return t_ptr->offset();

}

void ConnectionGraph::add_field_edge(uint from_i, uint to_i, int offset) {

  PointsToNode *f = ptnode_adr(from_i);

  PointsToNode *t = ptnode_adr(to_i);

  assert(f->node_type() != PointsToNode::UnknownType && t->node_type() != PointsToNode::UnknownType, "node types must be set");

  assert(f->node_type() == PointsToNode::JavaObject, "invalid destination of Field edge");

  assert(t->node_type() == PointsToNode::Field, "invalid destination of Field edge");

  assert (t->offset() == -1 || t->offset() == offset, "conflicting field offsets");

  t->set_offset(offset);

  f->add_edge(to_i, PointsToNode::FieldEdge);

}

void ConnectionGraph::set_escape_state(uint ni, PointsToNode::EscapeState es) {

  PointsToNode *npt = ptnode_adr(ni);

  PointsToNode::EscapeState old_es = npt->escape_state();

  if (es > old_es)

    npt->set_escape_state(es);

}

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

  uint idx = n->_idx;

  PointsToNode::EscapeState es;

  // If we are still collecting we don't know the answer yet

  if (_collecting)

    return PointsToNode::UnknownEscape;

  // if the node was created after the escape computation, return

  // UnknownEscape

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

    return PointsToNode::UnknownEscape;

  es = _nodes->at_grow(idx).escape_state();

  // if we have already computed a value, return it

  if (es != PointsToNode::UnknownEscape)

    return es;

  // compute max escape state of anything this node could point to

  VectorSet ptset(Thread::current()->resource_area());

  PointsTo(ptset, n, phase);

  for( VectorSetI i(&ptset); i.test() && es != PointsToNode::GlobalEscape; ++i ) {

    uint pt = i.elem;

    PointsToNode::EscapeState pes = _nodes->at(pt).escape_state();

    if (pes > es)

      es = pes;

  }

  // cache the computed escape state

  assert(es != PointsToNode::UnknownEscape, "should have computed an escape state");

  _nodes->adr_at(idx)->set_escape_state(es);

  return es;

}

void ConnectionGraph::PointsTo(VectorSet &ptset, Node * n, PhaseTransform *phase) {

  VectorSet visited(Thread::current()->resource_area());

  GrowableArray<uint>  worklist;

  n = skip_casts(n);

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

  // If we have a JavaObject, return just that object

  if (npt.node_type() == PointsToNode::JavaObject) {

    ptset.set(n->_idx);

    return;

  }

  // we may have a Phi which has not been processed

  if (npt._node == NULL) {

    assert(n->is_Phi(), "unprocessed node must be a Phi");

    record_for_escape_analysis(n);

    npt = _nodes->at(n->_idx);

  }

  worklist.push(n->_idx);

  while(worklist.length() > 0) {

    int ni = worklist.pop();

    PointsToNode pn = _nodes->at_grow(ni);

    if (!visited.test(ni)) {

      visited.set(ni);

      // ensure that all inputs of a Phi have been processed

      if (_collecting && pn._node->is_Phi()) {

        PhiNode *phi = pn._node->as_Phi();

        process_phi_escape(phi, phase);

      }

      int edges_processed = 0;

      for (uint e = 0; e < pn.edge_count(); e++) {

        PointsToNode::EdgeType et = pn.edge_type(e);

        if (et == PointsToNode::PointsToEdge) {

          ptset.set(pn.edge_target(e));

          edges_processed++;

        } else if (et == PointsToNode::DeferredEdge) {

          worklist.push(pn.edge_target(e));

          edges_processed++;

        }

      }

      if (edges_processed == 0) {

        // no deferred or pointsto edges found.  Assume the value was set outside

        // this method.  Add the phantom object to the pointsto set.

        ptset.set(_phantom_object);

      }

    }

  }

}

void ConnectionGraph::remove_deferred(uint ni) {

  VectorSet visited(Thread::current()->resource_area());

  uint i = 0;

  PointsToNode *ptn = ptnode_adr(ni);

  while(i < ptn->edge_count()) {

    if (ptn->edge_type(i) != PointsToNode::DeferredEdge) {

      i++;

    } else {

      uint t = ptn->edge_target(i);

      PointsToNode *ptt = ptnode_adr(t);

      ptn->remove_edge(t, PointsToNode::DeferredEdge);

      if(!visited.test(t)) {

        visited.set(t);

        for (uint j = 0; j < ptt->edge_count(); j++) {

          uint n1 = ptt->edge_target(j);

          PointsToNode *pt1 = ptnode_adr(n1);

          switch(ptt->edge_type(j)) {

            case PointsToNode::PointsToEdge:

               add_pointsto_edge(ni, n1);

              break;

            case PointsToNode::DeferredEdge:

              add_deferred_edge(ni, n1);

              break;

            case PointsToNode::FieldEdge:

              assert(false, "invalid connection graph");

              break;

          }

        }

      }

    }

  }

}

//  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 ConnectionGraph::add_edge_from_fields(uint adr_i, uint to_i, int offs) {

  PointsToNode an = _nodes->at_grow(adr_i);

  PointsToNode to = _nodes->at_grow(to_i);

  bool deferred = (to.node_type() == PointsToNode::LocalVar);

  for (uint fe = 0; fe < an.edge_count(); fe++) {

    assert(an.edge_type(fe) == PointsToNode::FieldEdge, "expecting a field edge");

    int fi = an.edge_target(fe);

    PointsToNode pf = _nodes->at_grow(fi);

    int po = pf.offset();

    if (po == offs || po == Type::OffsetBot || offs == Type::OffsetBot) {

      if (deferred)

        add_deferred_edge(fi, to_i);

      else

        add_pointsto_edge(fi, to_i);

    }

  }

}

//  Add a deferred  edge from node given by "from_i" to any field of adr_i whose offset

//  matches "offset"

void ConnectionGraph::add_deferred_edge_to_fields(uint from_i, uint adr_i, int offs) {

  PointsToNode an = _nodes->at_grow(adr_i);

  for (uint fe = 0; fe < an.edge_count(); fe++) {

    assert(an.edge_type(fe) == PointsToNode::FieldEdge, "expecting a field edge");

    int fi = an.edge_target(fe);

    PointsToNode pf = _nodes->at_grow(fi);

    int po = pf.offset();

    if (pf.edge_count() == 0) {

      // we have not seen any stores to this field, assume it was set outside this method

      add_pointsto_edge(fi, _phantom_object);

    }

    if (po == offs || po == Type::OffsetBot || offs == Type::OffsetBot) {

      add_deferred_edge(from_i, fi);

    }

  }

}

//

// Search memory chain of "mem" to find a MemNode whose address

// is the specified alias index.  Returns the MemNode found or the

// first non-MemNode encountered.

//

Node *ConnectionGraph::find_mem(Node *mem, int alias_idx, PhaseGVN  *igvn) {

  if (mem == NULL)

    return mem;

  while (mem->is_Mem()) {

    const Type *at = igvn->type(mem->in(MemNode::Address));

    if (at != Type::TOP) {

      assert (at->isa_ptr() != NULL, "pointer type required.");

      int idx = _compile->get_alias_index(at->is_ptr());

      if (idx == alias_idx)

        break;

    }

    mem = mem->in(MemNode::Memory);

  }

  return mem;

}

//

// Adjust the type and inputs of an AddP which computes the

// address of a field of an instance

//

void ConnectionGraph::split_AddP(Node *addp, Node *base,  PhaseGVN  *igvn) {

  const TypeOopPtr *t = igvn->type(addp)->isa_oopptr();

  const TypeOopPtr *base_t = igvn->type(base)->isa_oopptr();

  assert(t != NULL,  "expecting oopptr");

  assert(base_t != NULL && base_t->is_instance(), "expecting instance oopptr");

  uint inst_id =  base_t->instance_id();

  assert(!t->is_instance() || t->instance_id() == inst_id,

                             "old type must be non-instance or match new type");

  const TypeOopPtr *tinst = base_t->add_offset(t->offset())->is_oopptr();

  // ensure an alias index is allocated for the instance type

  int alias_idx = _compile->get_alias_index(tinst);

  igvn->set_type(addp, tinst);

  // record the allocation in the node map

  set_map(addp->_idx, get_map(base->_idx));

  // if the Address input is not the appropriate instance type (due to intervening

  // casts,) insert a cast

  Node *adr = addp->in(AddPNode::Address);

  const TypeOopPtr  *atype = igvn->type(adr)->isa_oopptr();

  if (atype->instance_id() != inst_id) {

    assert(!atype->is_instance(), "no conflicting instances");

    const TypeOopPtr *new_atype = base_t->add_offset(atype->offset())->isa_oopptr();

    Node *acast = new (_compile, 2) CastPPNode(adr, new_atype);

    acast->set_req(0, adr->in(0));

    igvn->set_type(acast, new_atype);

    record_for_optimizer(acast);

    Node *bcast = acast;

    Node *abase = addp->in(AddPNode::Base);

    if (abase != adr) {

      bcast = new (_compile, 2) CastPPNode(abase, base_t);

      bcast->set_req(0, abase->in(0));

      igvn->set_type(bcast, base_t);

      record_for_optimizer(bcast);

    }

    igvn->hash_delete(addp);

    addp->set_req(AddPNode::Base, bcast);

    addp->set_req(AddPNode::Address, acast);

    igvn->hash_insert(addp);

    record_for_optimizer(addp);

  }

}

//

// Create a new version of orig_phi if necessary. Returns either the newly

// created phi or an existing phi.  Sets create_new to indicate wheter  a new

// phi was created.  Cache the last newly created phi in the node map.

//

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

  Compile *C = _compile;

  new_created = false;

  int phi_alias_idx = C->get_alias_index(orig_phi->adr_type());

  // nothing to do if orig_phi is bottom memory or matches alias_idx

  if (phi_alias_idx == Compile::AliasIdxBot || phi_alias_idx == alias_idx) {

    return orig_phi;

  }

  // have we already created a Phi for this alias index?

  PhiNode *result = get_map_phi(orig_phi->_idx);

  const TypePtr *atype = C->get_adr_type(alias_idx);

  if (result != NULL && C->get_alias_index(result->adr_type()) == alias_idx) {

    return result;

  }

  orig_phi_worklist.append_if_missing(orig_phi);

  result = PhiNode::make(orig_phi->in(0), NULL, Type::MEMORY, atype);

  set_map_phi(orig_phi->_idx, result);

  igvn->set_type(result, result->bottom_type());

  record_for_optimizer(result);

  new_created = true;

  return result;

}

//

// Return a new version  of Memory Phi "orig_phi" with the inputs having the

// specified alias index.

//

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

  assert(alias_idx != Compile::AliasIdxBot, "can't split out bottom memory");

  Compile *C = _compile;

  bool new_phi_created;

  PhiNode *result =  create_split_phi(orig_phi, alias_idx, orig_phi_worklist, igvn, new_phi_created);

  if (!new_phi_created) {

    return result;

  }

  GrowableArray<PhiNode *>  phi_list;

  GrowableArray<uint>  cur_input;

  PhiNode *phi = orig_phi;

  uint idx = 1;

  bool finished = false;

  while(!finished) {

    while (idx < phi->req()) {

      Node *mem = find_mem(phi->in(idx), alias_idx, igvn);

      if (mem != NULL && mem->is_Phi()) {

        PhiNode *nphi = create_split_phi(mem->as_Phi(), alias_idx, orig_phi_worklist, igvn, new_phi_created);

        if (new_phi_created) {

          // found an phi for which we created a new split, push current one on worklist and begin

          // processing new one

          phi_list.push(phi);

          cur_input.push(idx);

          phi = mem->as_Phi();

          result = nphi;

          idx = 1;

          continue;

        } else {

          mem = nphi;

        }

      }

      result->set_req(idx++, mem);

    }

#ifdef ASSERT

    // verify that the new Phi has an input for each input of the original

    assert( phi->req() == result->req(), "must have same number of inputs.");

    assert( result->in(0) != NULL && result->in(0) == phi->in(0), "regions must match");

    for (uint i = 1; i < phi->req(); i++) {

      assert((phi->in(i) == NULL) == (result->in(i) == NULL), "inputs must correspond.");

    }

#endif

    // we have finished processing a Phi, see if there are any more to do

    finished = (phi_list.length() == 0 );

    if (!finished) {

      phi = phi_list.pop();

      idx = cur_input.pop();

      PhiNode *prev_phi = get_map_phi(phi->_idx);

      prev_phi->set_req(idx++, result);

      result = prev_phi;

    }

  }

  return result;

}

//

//  Convert the types of unescaped object to instance types where possible,

//  propagate the new type information through the graph, and update memory

//  edges and MergeMem inputs to reflect the new type.

//

//  We start with allocations (and calls which may be allocations)  on alloc_worklist.

//  The processing is done in 4 phases:

//

//  Phase 1:  Process possible allocations from alloc_worklist.  Create instance

//            types for the CheckCastPP for allocations where possible.

//            Propagate the the new types through users as follows:

//               casts and Phi:  push users on alloc_worklist

//               AddP:  cast Base and Address inputs to the instance type

//                      push any AddP users on alloc_worklist and push any memnode

//                      users onto memnode_worklist.

//  Phase 2:  Process MemNode's from memnode_worklist. compute new address type and

//            search the Memory chain for a store with the appropriate type

//            address type.  If a Phi is found, create a new version with

//            the approriate memory slices from each of the Phi inputs.

//            For stores, process the users as follows:

//               MemNode:  push on memnode_worklist

//               MergeMem: push on mergemem_worklist

//  Phase 3:  Process MergeMem nodes from mergemem_worklist.  Walk each memory slice

//            moving the first node encountered of each  instance type to the

//            the input corresponding to its alias index.

//            appropriate memory slice.

//  Phase 4:  Update the inputs of non-instance memory Phis and the Memory input of memnodes.

//

// In the following example, the CheckCastPP nodes are the cast of allocation

// results and the allocation of node 29 is unescaped and eligible to be an

// instance type.

//

// We start with:

//

//     7 Parm #memory

//    10  ConI  "12"

//    19  CheckCastPP   "Foo"

//    20  AddP  _ 19 19 10  Foo+12  alias_index=4

//    29  CheckCastPP   "Foo"

//    30  AddP  _ 29 29 10  Foo+12  alias_index=4

//

//    40  StoreP  25   7  20   ... alias_index=4

//    50  StoreP  35  40  30   ... alias_index=4

//    60  StoreP  45  50  20   ... alias_index=4

//    70  LoadP    _  60  30   ... alias_index=4

//    80  Phi     75  50  60   Memory alias_index=4

//    90  LoadP    _  80  30   ... alias_index=4

//   100  LoadP    _  80  20   ... alias_index=4

//

//

// Phase 1 creates an instance type for node 29 assigning it an instance id of 24

// and creating a new alias index for node 30.  This gives:

//

//     7 Parm #memory

//    10  ConI  "12"

//    19  CheckCastPP   "Foo"

//    20  AddP  _ 19 19 10  Foo+12  alias_index=4

//    29  CheckCastPP   "Foo"  iid=24

//    30  AddP  _ 29 29 10  Foo+12  alias_index=6  iid=24

//