/*

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

 *

 */

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(bool print_state) const {

  NodeType nt = node_type();

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

  if (print_state) {

    EscapeState es = escape_state();

    tty->print("%s %s ", esc_names[(int) es], _scalar_replaceable ? "":"NSR");

  }

  tty->print("[[");

  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, PhaseIterGVN *igvn) :

  _nodes(C->comp_arena(), C->unique(), C->unique(), PointsToNode()),

  _processed(C->comp_arena()),

  _collecting(true),

  _progress(false),

  _compile(C),

  _igvn(igvn),

  _node_map(C->comp_arena()) {

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

  add_node(C->top(), PointsToNode::JavaObject, PointsToNode::GlobalEscape,true);

  // Add ConP(#NULL) and ConN(#NULL) nodes.

  Node* oop_null = igvn->zerocon(T_OBJECT);

  _oop_null = oop_null->_idx;

  assert(_oop_null < C->unique(), "should be created already");

  add_node(oop_null, PointsToNode::JavaObject, PointsToNode::NoEscape, true);

  if (UseCompressedOops) {

    Node* noop_null = igvn->zerocon(T_NARROWOOP);

    _noop_null = noop_null->_idx;

    assert(_noop_null < C->unique(), "should be created already");

    add_node(noop_null, PointsToNode::JavaObject, PointsToNode::NoEscape, true);

  }

}

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

  add_edge(f, 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)

    add_edge(f, 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);

  add_edge(f, 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) {

  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)

    return PointsToNode::UnknownEscape;

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

  // UnknownEscape

  if (idx >= nodes_size())

    return PointsToNode::UnknownEscape;

  es = ptnode_adr(idx)->escape_state();

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

  if (es != PointsToNode::UnknownEscape &&

      ptnode_adr(idx)->node_type() == PointsToNode::JavaObject)

    return es;

  // PointsTo() calls n->uncast() which can return a new ideal node.

  if (n->uncast()->_idx >= nodes_size())

    return PointsToNode::UnknownEscape;

  PointsToNode::EscapeState orig_es = es;

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

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

  PointsTo(ptset, n);

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

    uint pt = i.elem;

    PointsToNode::EscapeState pes = ptnode_adr(pt)->escape_state();

    if (pes > es)

      es = pes;

  }

  if (orig_es != es) {

    // cache the computed escape state

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

    ptnode_adr(idx)->set_escape_state(es);

  } // orig_es could be PointsToNode::UnknownEscape

  return es;

}

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

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

  GrowableArray<uint>  worklist;

#ifdef ASSERT

  Node *orig_n = n;

#endif

  n = n->uncast();

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

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

  if (npt->node_type() == PointsToNode::JavaObject) {

    ptset.set(n->_idx);

    return;

  }

#ifdef ASSERT

  if (npt->_node == NULL) {

    if (orig_n != n)

      orig_n->dump();

    n->dump();

    assert(npt->_node != NULL, "unregistered node");

  }

#endif

  worklist.push(n->_idx);

  while(worklist.length() > 0) {

    int ni = worklist.pop();

    if (visited.test_set(ni))

      continue;

    PointsToNode* pn = ptnode_adr(ni);

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

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

    int edges_processed = 0;

    uint e_cnt = pn->edge_count();

    for (uint e = 0; e < e_cnt; 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();

  visited->set(ni);

  PointsToNode *ptn = ptnode_adr(ni);

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

  for (uint i = 0; i < ptn->edge_count(); ) {

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

    } else {

      i++;

    }

  }

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

    uint t = deferred_edges->at(next);

    PointsToNode *ptt = ptnode_adr(t);

    uint e_cnt = ptt->edge_count();

    for (uint e = 0; e < e_cnt; e++) {

      uint etgt = ptt->edge_target(e);

      if (visited->test_set(etgt))

        continue;

      PointsToNode::EdgeType et = ptt->edge_type(e);

      if (et == PointsToNode::PointsToEdge) {

        add_pointsto_edge(ni, etgt);

        if(etgt == _phantom_object) {

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

          ptn->set_escape_state(PointsToNode::GlobalEscape);

        }

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

        deferred_edges->append(etgt);

      } else {

        assert(false,"invalid connection graph");

      }

    }

  }

}

//  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 = ptnode_adr(adr_i);

  PointsToNode* to = ptnode_adr(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 = ptnode_adr(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 = ptnode_adr(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 = ptnode_adr(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 )

  //

  // case #8. narrow Klass's field reference.

  //      LoadNKlass

  //       |

  //      DecodeN

  //       | |

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

    while (base->is_AddP()) {

      // Case #6 (unsafe access) may have several chained AddP nodes.

      assert(base->in(AddPNode::Base)->is_top(), "expected unsafe access address only");

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

    }

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

           base->Opcode() == Op_CastX2P || base->is_DecodeN() ||

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