/*

 * Copyright (c) 2005, 2015, 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.

 *

 */

#include "precompiled.hpp"

#include "ci/bcEscapeAnalyzer.hpp"

#include "compiler/compileLog.hpp"

#include "libadt/vectset.hpp"

#include "memory/allocation.hpp"

#include "opto/c2compiler.hpp"

#include "opto/arraycopynode.hpp"

#include "opto/callnode.hpp"

#include "opto/cfgnode.hpp"

#include "opto/compile.hpp"

#include "opto/escape.hpp"

#include "opto/phaseX.hpp"

#include "opto/movenode.hpp"

#include "opto/rootnode.hpp"

ConnectionGraph::ConnectionGraph(Compile * C, PhaseIterGVN *igvn) :

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

  _in_worklist(C->comp_arena()),

  _next_pidx(0),

  _collecting(true),

  _verify(false),

  _compile(C),

  _igvn(igvn),

  _node_map(C->comp_arena()) {

  // Add unknown java object.

  add_java_object(C->top(), PointsToNode::GlobalEscape);

  phantom_obj = ptnode_adr(C->top()->_idx)->as_JavaObject();

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

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

  assert(oop_null->_idx < nodes_size(), "should be created already");

  add_java_object(oop_null, PointsToNode::NoEscape);

  null_obj = ptnode_adr(oop_null->_idx)->as_JavaObject();

  if (UseCompressedOops) {

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

    assert(noop_null->_idx < nodes_size(), "should be created already");

    map_ideal_node(noop_null, null_obj);

  }

  _pcmp_neq = NULL; // Should be initialized

  _pcmp_eq  = NULL;

}

bool ConnectionGraph::has_candidates(Compile *C) {

  // EA brings benefits only when the code has allocations and/or locks which

  // are represented by ideal Macro nodes.

  int cnt = C->macro_count();

  for (int i = 0; i < cnt; i++) {

    Node *n = C->macro_node(i);

    if (n->is_Allocate())

      return true;

    if (n->is_Lock()) {

      Node* obj = n->as_Lock()->obj_node()->uncast();

      if (!(obj->is_Parm() || obj->is_Con()))

        return true;

    }

    if (n->is_CallStaticJava() &&

        n->as_CallStaticJava()->is_boxing_method()) {

      return true;

    }

  }

  return false;

}

void ConnectionGraph::do_analysis(Compile *C, PhaseIterGVN *igvn) {

  Compile::TracePhase tp("escapeAnalysis", &Phase::timers[Phase::_t_escapeAnalysis]);

  ResourceMark rm;

  // Add ConP#NULL and ConN#NULL nodes before ConnectionGraph construction

  // to create space for them in ConnectionGraph::_nodes[].

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

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

  ConnectionGraph* congraph = new(C->comp_arena()) ConnectionGraph(C, igvn);

  // Perform escape analysis

  if (congraph->compute_escape()) {

    // There are non escaping objects.

    C->set_congraph(congraph);

  }

  // Cleanup.

  if (oop_null->outcnt() == 0)

    igvn->hash_delete(oop_null);

  if (noop_null->outcnt() == 0)

    igvn->hash_delete(noop_null);

}

bool ConnectionGraph::compute_escape() {

  Compile* C = _compile;

  PhaseGVN* igvn = _igvn;

  // Worklists used by EA.

  Unique_Node_List delayed_worklist;

  GrowableArray<Node*> alloc_worklist;

  GrowableArray<Node*> ptr_cmp_worklist;

  GrowableArray<Node*> storestore_worklist;

  GrowableArray<ArrayCopyNode*> arraycopy_worklist;

  GrowableArray<PointsToNode*>   ptnodes_worklist;

  GrowableArray<JavaObjectNode*> java_objects_worklist;

  GrowableArray<JavaObjectNode*> non_escaped_worklist;

  GrowableArray<FieldNode*>      oop_fields_worklist;

  DEBUG_ONLY( GrowableArray<Node*> addp_worklist; )

  { Compile::TracePhase tp("connectionGraph", &Phase::timers[Phase::_t_connectionGraph]);

  // 1. Populate Connection Graph (CG) with PointsTo nodes.

  ideal_nodes.map(C->live_nodes(), NULL);  // preallocate space

  // Initialize worklist

  if (C->root() != NULL) {

    ideal_nodes.push(C->root());

  }

  // Processed ideal nodes are unique on ideal_nodes list

  // but several ideal nodes are mapped to the phantom_obj.

  // To avoid duplicated entries on the following worklists

  // add the phantom_obj only once to them.

  ptnodes_worklist.append(phantom_obj);

  java_objects_worklist.append(phantom_obj);

  for( uint next = 0; next < ideal_nodes.size(); ++next ) {

    Node* n = ideal_nodes.at(next);

    // Create PointsTo nodes and add them to Connection Graph. Called

    // only once per ideal node since ideal_nodes is Unique_Node list.

    add_node_to_connection_graph(n, &delayed_worklist);

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

    if (ptn != NULL && ptn != phantom_obj) {

      ptnodes_worklist.append(ptn);

      if (ptn->is_JavaObject()) {

        java_objects_worklist.append(ptn->as_JavaObject());

        if ((n->is_Allocate() || n->is_CallStaticJava()) &&

            (ptn->escape_state() < PointsToNode::GlobalEscape)) {

          // Only allocations and java static calls results are interesting.

          non_escaped_worklist.append(ptn->as_JavaObject());

        }

      } else if (ptn->is_Field() && ptn->as_Field()->is_oop()) {

        oop_fields_worklist.append(ptn->as_Field());

      }

    }

    if (n->is_MergeMem()) {

      // Collect all MergeMem nodes to add memory slices for

      // scalar replaceable objects in split_unique_types().

      _mergemem_worklist.append(n->as_MergeMem());

    } else if (OptimizePtrCompare && n->is_Cmp() &&

               (n->Opcode() == Op_CmpP || n->Opcode() == Op_CmpN)) {

      // Collect compare pointers nodes.

      ptr_cmp_worklist.append(n);

    } else if (n->is_MemBarStoreStore()) {

      // Collect all MemBarStoreStore nodes so that depending on the

      // escape status of the associated Allocate node some of them

      // may be eliminated.

      storestore_worklist.append(n);

    } else if (n->is_MemBar() && (n->Opcode() == Op_MemBarRelease) &&

               (n->req() > MemBarNode::Precedent)) {

      record_for_optimizer(n);

#ifdef ASSERT

    } else if (n->is_AddP()) {

      // Collect address nodes for graph verification.

      addp_worklist.append(n);

#endif

    } else if (n->is_ArrayCopy()) {

      // Keep a list of ArrayCopy nodes so if one of its input is non

      // escaping, we can record a unique type

      arraycopy_worklist.append(n->as_ArrayCopy());

    }

    for (DUIterator_Fast imax, i = n->fast_outs(imax); i < imax; i++) {

      Node* m = n->fast_out(i);   // Get user

      ideal_nodes.push(m);

    }

  }

  if (non_escaped_worklist.length() == 0) {

    _collecting = false;

    return false; // Nothing to do.

  }

  // Add final simple edges to graph.

  while(delayed_worklist.size() > 0) {

    Node* n = delayed_worklist.pop();

    add_final_edges(n);

  }

  int ptnodes_length = ptnodes_worklist.length();

#ifdef ASSERT

  if (VerifyConnectionGraph) {

    // Verify that no new simple edges could be created and all

    // local vars has edges.

    _verify = true;

    for (int next = 0; next < ptnodes_length; ++next) {

      PointsToNode* ptn = ptnodes_worklist.at(next);

      add_final_edges(ptn->ideal_node());

      if (ptn->is_LocalVar() && ptn->edge_count() == 0) {

        ptn->dump();

        assert(ptn->as_LocalVar()->edge_count() > 0, "sanity");

      }

    }

    _verify = false;

  }

#endif

  // Bytecode analyzer BCEscapeAnalyzer, used for Call nodes

  // processing, calls to CI to resolve symbols (types, fields, methods)

  // referenced in bytecode. During symbol resolution VM may throw

  // an exception which CI cleans and converts to compilation failure.

  if (C->failing())  return false;

  // 2. Finish Graph construction by propagating references to all

  //    java objects through graph.

  if (!complete_connection_graph(ptnodes_worklist, non_escaped_worklist,

                                 java_objects_worklist, oop_fields_worklist)) {

    // All objects escaped or hit time or iterations limits.

    _collecting = false;

    return false;

  }

  // 3. Adjust scalar_replaceable state of nonescaping objects and push

  //    scalar replaceable allocations on alloc_worklist for processing

  //    in split_unique_types().

  int non_escaped_length = non_escaped_worklist.length();

  for (int next = 0; next < non_escaped_length; next++) {

    JavaObjectNode* ptn = non_escaped_worklist.at(next);

    bool noescape = (ptn->escape_state() == PointsToNode::NoEscape);

    Node* n = ptn->ideal_node();

    if (n->is_Allocate()) {

      n->as_Allocate()->_is_non_escaping = noescape;

    }

    if (n->is_CallStaticJava()) {

      n->as_CallStaticJava()->_is_non_escaping = noescape;

    }

    if (noescape && ptn->scalar_replaceable()) {

      adjust_scalar_replaceable_state(ptn);

      if (ptn->scalar_replaceable()) {

        alloc_worklist.append(ptn->ideal_node());

      }

    }

  }

#ifdef ASSERT

  if (VerifyConnectionGraph) {

    // Verify that graph is complete - no new edges could be added or needed.

    verify_connection_graph(ptnodes_worklist, non_escaped_worklist,

                            java_objects_worklist, addp_worklist);

  }

  assert(C->unique() == nodes_size(), "no new ideal nodes should be added during ConnectionGraph build");

  assert(null_obj->escape_state() == PointsToNode::NoEscape &&

         null_obj->edge_count() == 0 &&

         !null_obj->arraycopy_src() &&

         !null_obj->arraycopy_dst(), "sanity");

#endif

  _collecting = false;

  } // TracePhase t3("connectionGraph")

  // 4. Optimize ideal graph based on EA information.

  bool has_non_escaping_obj = (non_escaped_worklist.length() > 0);

  if (has_non_escaping_obj) {

    optimize_ideal_graph(ptr_cmp_worklist, storestore_worklist);

  }

#ifndef PRODUCT

  if (PrintEscapeAnalysis) {

    dump(ptnodes_worklist); // Dump ConnectionGraph

  }

#endif

  bool has_scalar_replaceable_candidates = (alloc_worklist.length() > 0);

#ifdef ASSERT

  if (VerifyConnectionGraph) {

    int alloc_length = alloc_worklist.length();

    for (int next = 0; next < alloc_length; ++next) {

      Node* n = alloc_worklist.at(next);

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

      assert(ptn->escape_state() == PointsToNode::NoEscape && ptn->scalar_replaceable(), "sanity");

    }

  }

#endif

  // 5. Separate memory graph for scalar replaceable allcations.

  if (has_scalar_replaceable_candidates &&

      C->AliasLevel() >= 3 && EliminateAllocations) {

    // Now use the escape information to create unique types for

    // scalar replaceable objects.

    split_unique_types(alloc_worklist, arraycopy_worklist);

    if (C->failing())  return false;

    C->print_method(PHASE_AFTER_EA, 2);

#ifdef ASSERT

  } else if (Verbose && (PrintEscapeAnalysis || PrintEliminateAllocations)) {

    tty->print("=== No allocations eliminated for ");

    C->method()->print_short_name();

    if(!EliminateAllocations) {

      tty->print(" since EliminateAllocations is off ===");

    } else if(!has_scalar_replaceable_candidates) {

      tty->print(" since there are no scalar replaceable candidates ===");

    } else if(C->AliasLevel() < 3) {

      tty->print(" since AliasLevel < 3 ===");

    }

    tty->cr();

#endif

  }

  return has_non_escaping_obj;

}

// Utility function for nodes that load an object

void ConnectionGraph::add_objload_to_connection_graph(Node *n, Unique_Node_List *delayed_worklist) {

  // Using isa_ptr() instead of isa_oopptr() for LoadP and Phi because

  // ThreadLocal has RawPtr type.

  const Type* t = _igvn->type(n);

  if (t->make_ptr() != NULL) {

    Node* adr = n->in(MemNode::Address);

#ifdef ASSERT

    if (!adr->is_AddP()) {

      assert(_igvn->type(adr)->isa_rawptr(), "sanity");

    } else {

      assert((ptnode_adr(adr->_idx) == NULL ||

              ptnode_adr(adr->_idx)->as_Field()->is_oop()), "sanity");

    }

#endif

    add_local_var_and_edge(n, PointsToNode::NoEscape,

                           adr, delayed_worklist);

  }

}

// Populate Connection Graph with PointsTo nodes and create simple

// connection graph edges.

void ConnectionGraph::add_node_to_connection_graph(Node *n, Unique_Node_List *delayed_worklist) {

  assert(!_verify, "this method should not be called for verification");

  PhaseGVN* igvn = _igvn;

  uint n_idx = n->_idx;

  PointsToNode* n_ptn = ptnode_adr(n_idx);

  if (n_ptn != NULL)

    return; // No need to redefine PointsTo node during first iteration.

  if (n->is_Call()) {

    // Arguments to allocation and locking don't escape.

    if (n->is_AbstractLock()) {

      // Put Lock and Unlock nodes on IGVN worklist to process them during

      // first IGVN optimization when escape information is still available.

      record_for_optimizer(n);

    } else if (n->is_Allocate()) {

      add_call_node(n->as_Call());

      record_for_optimizer(n);

    } else {

      if (n->is_CallStaticJava()) {

        const char* name = n->as_CallStaticJava()->_name;

        if (name != NULL && strcmp(name, "uncommon_trap") == 0)

          return; // Skip uncommon traps

      }

      // Don't mark as processed since call's arguments have to be processed.

      delayed_worklist->push(n);

      // Check if a call returns an object.

      if ((n->as_Call()->returns_pointer() &&

           n->as_Call()->proj_out(TypeFunc::Parms) != NULL) ||

          (n->is_CallStaticJava() &&

           n->as_CallStaticJava()->is_boxing_method())) {

        add_call_node(n->as_Call());

      }

    }

    return;

  }

  // Put this check here to process call arguments since some call nodes

  // point to phantom_obj.

  if (n_ptn == phantom_obj || n_ptn == null_obj)

    return; // Skip predefined nodes.

  int opcode = n->Opcode();

  switch (opcode) {

    case Op_AddP: {

      Node* base = get_addp_base(n);

      PointsToNode* ptn_base = ptnode_adr(base->_idx);

      // Field nodes are created for all field types. They are used in

      // adjust_scalar_replaceable_state() and split_unique_types().

      // Note, non-oop fields will have only base edges in Connection

      // Graph because such fields are not used for oop loads and stores.

      int offset = address_offset(n, igvn);

      add_field(n, PointsToNode::NoEscape, offset);

      if (ptn_base == NULL) {

        delayed_worklist->push(n); // Process it later.

      } else {

        n_ptn = ptnode_adr(n_idx);

        add_base(n_ptn->as_Field(), ptn_base);

      }

      break;

    }

    case Op_CastX2P: {

      map_ideal_node(n, phantom_obj);

      break;

    }

    case Op_CastPP:

    case Op_CheckCastPP:

    case Op_EncodeP:

    case Op_DecodeN:

    case Op_EncodePKlass:

    case Op_DecodeNKlass: {

      add_local_var_and_edge(n, PointsToNode::NoEscape,

                             n->in(1), delayed_worklist);

      break;

    }

    case Op_CMoveP: {

      add_local_var(n, PointsToNode::NoEscape);

      // Do not add edges during first iteration because some could be

      // not defined yet.

      delayed_worklist->push(n);

      break;

    }

    case Op_ConP:

    case Op_ConN:

    case Op_ConNKlass: {

      // assume all oop constants globally escape except for null

      PointsToNode::EscapeState es;

      const Type* t = igvn->type(n);

      if (t == TypePtr::NULL_PTR || t == TypeNarrowOop::NULL_PTR) {

        es = PointsToNode::NoEscape;

      } else {

        es = PointsToNode::GlobalEscape;

      }

      add_java_object(n, es);

      break;

    }

    case Op_CreateEx: {

      // assume that all exception objects globally escape

      map_ideal_node(n, phantom_obj);

      break;

    }

    case Op_LoadKlass:

    case Op_LoadNKlass: {

      // Unknown class is loaded

      map_ideal_node(n, phantom_obj);

      break;

    }

    case Op_LoadP:

    case Op_LoadN:

    case Op_LoadPLocked: {

      add_objload_to_connection_graph(n, delayed_worklist);

      break;

    }

    case Op_Parm: {

      map_ideal_node(n, phantom_obj);

      break;

    }

    case Op_PartialSubtypeCheck: {

      // Produces Null or notNull and is used in only in CmpP so

      // phantom_obj could be used.

      map_ideal_node(n, phantom_obj); // Result is unknown

      break;

    }

    case Op_Phi: {

      // Using isa_ptr() instead of isa_oopptr() for LoadP and Phi because

      // ThreadLocal has RawPtr type.

      const Type* t = n->as_Phi()->type();

      if (t->make_ptr() != NULL) {

        add_local_var(n, PointsToNode::NoEscape);

        // Do not add edges during first iteration because some could be

        // not defined yet.

        delayed_worklist->push(n);

      }

      break;

    }

    case Op_Proj: {

      // we are only interested in the oop result projection from a call

      if (n->as_Proj()->_con == TypeFunc::Parms && n->in(0)->is_Call() &&

          n->in(0)->as_Call()->returns_pointer()) {

        add_local_var_and_edge(n, PointsToNode::NoEscape,

                               n->in(0), delayed_worklist);

      }

      break;

    }

    case Op_Rethrow: // Exception object escapes

    case Op_Return: {

      if (n->req() > TypeFunc::Parms &&

          igvn->type(n->in(TypeFunc::Parms))->isa_oopptr()) {

        // Treat Return value as LocalVar with GlobalEscape escape state.

        add_local_var_and_edge(n, PointsToNode::GlobalEscape,

                               n->in(TypeFunc::Parms), delayed_worklist);

      }

      break;

    }