/*

 * 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 const char *node_type_names[] = {

  "UnknownType",

  "JavaObject",

  "LocalVar",

  "Field"

};

static const char *esc_names[] = {

  "UnknownEscape",

  "NoEscape",

  "ArgEscape",

  "GlobalEscape"

};

static const 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 %s [[", node_type_names[(int) nt], esc_names[(int) es], _scalar_replaceable ? "" : "NSR");

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

  int sz = C->unique();

  _nodes = new(C->comp_arena()) GrowableArray<PointsToNode>(C->comp_arena(), sz, sz, dummy);

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

  PointsToNode *phn = ptnode_adr(_phantom_object);

  phn->_node = C->top();

  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::address_offset(Node* adr, PhaseTransform *phase) {

  const Type *adr_type = phase->type(adr);

  if (adr->is_AddP() && adr_type->isa_oopptr() == NULL &&

      adr->in(AddPNode::Address)->is_Proj() &&

      adr->in(AddPNode::Address)->in(0)->is_Allocate()) {

    // We are computing a raw address for a store captured by an Initialize

    // compute an appropriate address type. AddP cases #3 and #5 (see below).

    int offs = (int)phase->find_intptr_t_con(adr->in(AddPNode::Offset), Type::OffsetBot);

    assert(offs != Type::OffsetBot ||

           adr->in(AddPNode::Address)->in(0)->is_AllocateArray(),

           "offset must be a constant or it is initialization of array");

    return offs;

  }

  const TypePtr *t_ptr = adr_type->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);

}

void ConnectionGraph::add_node(Node *n, PointsToNode::NodeType nt,

                               PointsToNode::EscapeState es, bool done) {

  PointsToNode* ptadr = ptnode_adr(n->_idx);

  ptadr->_node = n;

  ptadr->set_node_type(nt);

  // inline set_escape_state(idx, es);

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

  if (es > old_es)

    ptadr->set_escape_state(es);

  if (done)

    _processed.set(n->_idx);

}

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

  uint idx = n->_idx;

  PointsToNode::EscapeState es;

  // If we are still collecting or there were no non-escaping allocations

  // we don't know the answer yet

  if (_collecting || !_has_allocations)

    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->adr_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 = n->uncast();

  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;

  }

  worklist.push(n->_idx);

  while(worklist.length() > 0) {

    int ni = worklist.pop();

    PointsToNode pn = _nodes->at_grow(ni);

    if (!visited.test_set(ni)) {

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

      assert(!_collecting || !pn._node->is_Phi() || _processed.test(ni),"");

      int edges_processed = 0;

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

        uint etgt = pn.edge_target(e);

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

        if (et == PointsToNode::PointsToEdge) {

          ptset.set(etgt);

          edges_processed++;

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

          worklist.push(etgt);

          edges_processed++;

        } else {

          assert(false,"neither PointsToEdge or DeferredEdge");

        }

      }

      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, GrowableArray<uint>* deferred_edges, VectorSet* visited) {

  // This method is most expensive during ConnectionGraph construction.

  // Reuse vectorSet and an additional growable array for deferred edges.

  deferred_edges->clear();

  visited->Clear();

  uint i = 0;

  PointsToNode *ptn = ptnode_adr(ni);

  // Mark current edges as visited and move deferred edges to separate array.

    uint t = ptn->edge_target(i);

#ifdef ASSERT

    assert(!visited->test_set(t), "expecting no duplications");

#else

    visited->set(t);

#endif

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

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

      deferred_edges->append(t);

    }

  }

  for (int next = 0; next < deferred_edges->length(); ++next) {

    uint t = deferred_edges->at(next);

    PointsToNode *ptt = ptnode_adr(t);

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

      uint n1 = ptt->edge_target(j);

      if (visited->test_set(n1))

        continue;

      switch(ptt->edge_type(j)) {

        case PointsToNode::PointsToEdge:

          add_pointsto_edge(ni, n1);

          if(n1 == _phantom_object) {

            // Special case - field set outside (globally escaping).

            ptn->set_escape_state(PointsToNode::GlobalEscape);

          }

          break;

        case PointsToNode::DeferredEdge:

          deferred_edges->append(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);

    }

  }

}

// Helper functions

static Node* get_addp_base(Node *addp) {

  assert(addp->is_AddP(), "must be AddP");

  //

  // AddP cases for Base and Address inputs:

  // case #1. Direct object's field reference:

  //     Allocate

  //       |

  //     Proj #5 ( oop result )

  //       |

  //     CheckCastPP (cast to instance type)

  //      | |

  //     AddP  ( base == address )

  //

  // case #2. Indirect object's field reference:

  //      Phi

  //       |

  //     CastPP (cast to instance type)

  //      | |

  //     AddP  ( base == address )

  //

  // case #3. Raw object's field reference for Initialize node:

  //      Allocate

  //        |

  //      Proj #5 ( oop result )

  //  top   |

  //     \  |

  //     AddP  ( base == top )

  //

  // case #4. Array's element reference:

  //   {CheckCastPP | CastPP}

  //     |  | |

  //     |  AddP ( array's element offset )

  //     |  |

  //     AddP ( array's offset )

  //

  // case #5. Raw object's field reference for arraycopy stub call:

  //          The inline_native_clone() case when the arraycopy stub is called

  //          after the allocation before Initialize and CheckCastPP nodes.

  //      Allocate

  //        |

  //      Proj #5 ( oop result )

  //       | |

  //       AddP  ( base == address )

  //

  // case #6. Constant Pool, ThreadLocal, CastX2P or

  //          Raw object's field reference:

  //      {ConP, ThreadLocal, CastX2P, raw Load}

  //  top   |

  //     \  |

  //     AddP  ( base == top )

  //

  // case #7. Klass's field reference.

  //      LoadKlass

  //       | |

  //       AddP  ( base == address )

  //

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

  if (base->is_top()) { // The AddP case #3 and #6.

    base = addp->in(AddPNode::Address)->uncast();

    assert(base->Opcode() == Op_ConP || base->Opcode() == Op_ThreadLocal ||

           base->Opcode() == Op_CastX2P ||

           (base->is_Mem() && base->bottom_type() == TypeRawPtr::NOTNULL) ||

           (base->is_Proj() && base->in(0)->is_Allocate()), "sanity");

  }

  return base;

}

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

  assert(addp->is_AddP() && addp->outcnt() > 0, "Don't process dead nodes");

  Node* addp2 = addp->raw_out(0);

  if (addp->outcnt() == 1 && addp2->is_AddP() &&

      addp2->in(AddPNode::Base) == n &&

      addp2->in(AddPNode::Address) == addp) {

    assert(addp->in(AddPNode::Base) == n, "expecting the same base");

    //

    // Find array's offset to push it on worklist first and

    // as result process an array's element offset first (pushed second)

    // to avoid CastPP for the array's offset.

    // Otherwise the inserted CastPP (LocalVar) will point to what

    // the AddP (Field) points to. Which would be wrong since

    // the algorithm expects the CastPP has the same point as

    // as AddP's base CheckCastPP (LocalVar).

    //

    //    ArrayAllocation

    //     |

    //    CheckCastPP

    //     |

    //    memProj (from ArrayAllocation CheckCastPP)

    //     |  ||

    //     |  ||   Int (element index)

    //     |  ||    |   ConI (log(element size))

    //     |  ||    |   /

    //     |  ||   LShift

    //     |  ||  /

    //     |  AddP (array's element offset)

    //     |  |

    //     |  | ConI (array's offset: #12(32-bits) or #24(64-bits))

    //     | / /

    //     AddP (array's offset)

    //      |

    //     Load/Store (memory operation on array's element)

    //

    return addp2;

  }

  return NULL;

}

//

// 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 *base_t = igvn->type(base)->isa_oopptr();

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

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

  if (t == NULL) {

    // We are computing a raw address for a store captured by an Initialize

    // compute an appropriate address type.

    assert(igvn->type(addp) == TypeRawPtr::NOTNULL, "must be raw pointer");

    assert(addp->in(AddPNode::Address)->is_Proj(), "base of raw address must be result projection from allocation");

    int offs = (int)igvn->find_intptr_t_con(addp->in(AddPNode::Offset), Type::OffsetBot);

    assert(offs != Type::OffsetBot, "offset must be a constant");

    t = base_t->add_offset(offs)->is_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();

  // Do NOT remove the next call: ensure an new 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 != NULL && 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));