/*

 * Copyright (c) 1997, 2013, 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 "compiler/compileLog.hpp"

#include "interpreter/linkResolver.hpp"

#include "oops/method.hpp"

#include "opto/addnode.hpp"

#include "opto/idealGraphPrinter.hpp"

#include "opto/locknode.hpp"

#include "opto/memnode.hpp"

#include "opto/parse.hpp"

#include "opto/rootnode.hpp"

#include "opto/runtime.hpp"

#include "runtime/arguments.hpp"

#include "runtime/handles.inline.hpp"

#include "runtime/sharedRuntime.hpp"

#include "utilities/copy.hpp"

// Static array so we can figure out which bytecodes stop us from compiling

// the most. Some of the non-static variables are needed in bytecodeInfo.cpp

// and eventually should be encapsulated in a proper class (gri 8/18/98).

int nodes_created              = 0;

int methods_parsed             = 0;

int methods_seen               = 0;

int blocks_parsed              = 0;

int blocks_seen                = 0;

int explicit_null_checks_inserted = 0;

int explicit_null_checks_elided   = 0;

int all_null_checks_found         = 0, implicit_null_checks              = 0;

int implicit_null_throws          = 0;

int reclaim_idx  = 0;

int reclaim_in   = 0;

int reclaim_node = 0;

#ifndef PRODUCT

bool Parse::BytecodeParseHistogram::_initialized = false;

uint Parse::BytecodeParseHistogram::_bytecodes_parsed [Bytecodes::number_of_codes];

uint Parse::BytecodeParseHistogram::_nodes_constructed[Bytecodes::number_of_codes];

uint Parse::BytecodeParseHistogram::_nodes_transformed[Bytecodes::number_of_codes];

uint Parse::BytecodeParseHistogram::_new_values       [Bytecodes::number_of_codes];

#endif

//------------------------------print_statistics-------------------------------

#ifndef PRODUCT

void Parse::print_statistics() {

  tty->print_cr("--- Compiler Statistics ---");

  tty->print("Methods seen: %d  Methods parsed: %d", methods_seen, methods_parsed);

  tty->print("  Nodes created: %d", nodes_created);

  tty->cr();

  if (methods_seen != methods_parsed)

    tty->print_cr("Reasons for parse failures (NOT cumulative):");

  tty->print_cr("Blocks parsed: %d  Blocks seen: %d", blocks_parsed, blocks_seen);

  if( explicit_null_checks_inserted )

    tty->print_cr("%d original NULL checks - %d elided (%2d%%); optimizer leaves %d,", explicit_null_checks_inserted, explicit_null_checks_elided, (100*explicit_null_checks_elided)/explicit_null_checks_inserted, all_null_checks_found);

  if( all_null_checks_found )

    tty->print_cr("%d made implicit (%2d%%)", implicit_null_checks,

                  (100*implicit_null_checks)/all_null_checks_found);

  if( implicit_null_throws )

    tty->print_cr("%d implicit null exceptions at runtime",

                  implicit_null_throws);

  if( PrintParseStatistics && BytecodeParseHistogram::initialized() ) {

    BytecodeParseHistogram::print();

  }

}

#endif

//------------------------------ON STACK REPLACEMENT---------------------------

// Construct a node which can be used to get incoming state for

// on stack replacement.

Node *Parse::fetch_interpreter_state(int index,

                                     BasicType bt,

                                     Node *local_addrs,

                                     Node *local_addrs_base) {

  Node *mem = memory(Compile::AliasIdxRaw);

  Node *adr = basic_plus_adr( local_addrs_base, local_addrs, -index*wordSize );

  Node *ctl = control();

  // Very similar to LoadNode::make, except we handle un-aligned longs and

  // doubles on Sparc.  Intel can handle them just fine directly.

  Node *l;

  switch (bt) {                // Signature is flattened

  case T_INT:     l = new (C) LoadINode(ctl, mem, adr, TypeRawPtr::BOTTOM, TypeInt::INT,        MemNode::unordered); break;

  case T_FLOAT:   l = new (C) LoadFNode(ctl, mem, adr, TypeRawPtr::BOTTOM, Type::FLOAT,         MemNode::unordered); break;

  case T_ADDRESS: l = new (C) LoadPNode(ctl, mem, adr, TypeRawPtr::BOTTOM, TypeRawPtr::BOTTOM,  MemNode::unordered); break;

  case T_OBJECT:  l = new (C) LoadPNode(ctl, mem, adr, TypeRawPtr::BOTTOM, TypeInstPtr::BOTTOM, MemNode::unordered); break;

  case T_LONG:

  case T_DOUBLE: {

    // Since arguments are in reverse order, the argument address 'adr'

    // refers to the back half of the long/double.  Recompute adr.

    adr = basic_plus_adr(local_addrs_base, local_addrs, -(index+1)*wordSize);

    if (Matcher::misaligned_doubles_ok) {

      l = (bt == T_DOUBLE)

        ? (Node*)new (C) LoadDNode(ctl, mem, adr, TypeRawPtr::BOTTOM, Type::DOUBLE, MemNode::unordered)

        : (Node*)new (C) LoadLNode(ctl, mem, adr, TypeRawPtr::BOTTOM, TypeLong::LONG, MemNode::unordered);

    } else {

      l = (bt == T_DOUBLE)

        ? (Node*)new (C) LoadD_unalignedNode(ctl, mem, adr, TypeRawPtr::BOTTOM, MemNode::unordered)

        : (Node*)new (C) LoadL_unalignedNode(ctl, mem, adr, TypeRawPtr::BOTTOM, MemNode::unordered);

    }

    break;

  }

  default: ShouldNotReachHere();

  }

  return _gvn.transform(l);

}

// Helper routine to prevent the interpreter from handing

// unexpected typestate to an OSR method.

// The Node l is a value newly dug out of the interpreter frame.

// The type is the type predicted by ciTypeFlow.  Note that it is

// not a general type, but can only come from Type::get_typeflow_type.

// The safepoint is a map which will feed an uncommon trap.

Node* Parse::check_interpreter_type(Node* l, const Type* type,

                                    SafePointNode* &bad_type_exit) {

  const TypeOopPtr* tp = type->isa_oopptr();

  // TypeFlow may assert null-ness if a type appears unloaded.

  if (type == TypePtr::NULL_PTR ||

      (tp != NULL && !tp->klass()->is_loaded())) {

    // Value must be null, not a real oop.

    Node* chk = _gvn.transform( new (C) CmpPNode(l, null()) );

    Node* tst = _gvn.transform( new (C) BoolNode(chk, BoolTest::eq) );

    IfNode* iff = create_and_map_if(control(), tst, PROB_MAX, COUNT_UNKNOWN);

    set_control(_gvn.transform( new (C) IfTrueNode(iff) ));

    Node* bad_type = _gvn.transform( new (C) IfFalseNode(iff) );

    bad_type_exit->control()->add_req(bad_type);

    l = null();

  }

  // Typeflow can also cut off paths from the CFG, based on

  // types which appear unloaded, or call sites which appear unlinked.

  // When paths are cut off, values at later merge points can rise

  // toward more specific classes.  Make sure these specific classes

  // are still in effect.

  if (tp != NULL && tp->klass() != C->env()->Object_klass()) {

    // TypeFlow asserted a specific object type.  Value must have that type.

    Node* bad_type_ctrl = NULL;

    l = gen_checkcast(l, makecon(TypeKlassPtr::make(tp->klass())), &bad_type_ctrl);

    bad_type_exit->control()->add_req(bad_type_ctrl);

  }

  BasicType bt_l = _gvn.type(l)->basic_type();

  BasicType bt_t = type->basic_type();

  assert(_gvn.type(l)->higher_equal(type), "must constrain OSR typestate");

  return l;

}

// Helper routine which sets up elements of the initial parser map when

// performing a parse for on stack replacement.  Add values into map.

// The only parameter contains the address of a interpreter arguments.

void Parse::load_interpreter_state(Node* osr_buf) {

  int index;

  int max_locals = jvms()->loc_size();

  int max_stack  = jvms()->stk_size();

  // Mismatch between method and jvms can occur since map briefly held

  // an OSR entry state (which takes up one RawPtr word).

  assert(max_locals == method()->max_locals(), "sanity");

  assert(max_stack  >= method()->max_stack(),  "sanity");

  assert((int)jvms()->endoff() == TypeFunc::Parms + max_locals + max_stack, "sanity");

  assert((int)jvms()->endoff() == (int)map()->req(), "sanity");

  // Find the start block.

  Block* osr_block = start_block();

  assert(osr_block->start() == osr_bci(), "sanity");

  // Set initial BCI.

  set_parse_bci(osr_block->start());

  // Set initial stack depth.

  set_sp(osr_block->start_sp());

  // Check bailouts.  We currently do not perform on stack replacement

  // of loops in catch blocks or loops which branch with a non-empty stack.

  if (sp() != 0) {

    C->record_method_not_compilable("OSR starts with non-empty stack");

    return;

  }

  // Do not OSR inside finally clauses:

  if (osr_block->has_trap_at(osr_block->start())) {

    C->record_method_not_compilable("OSR starts with an immediate trap");

    return;

  }

  // Commute monitors from interpreter frame to compiler frame.

  assert(jvms()->monitor_depth() == 0, "should be no active locks at beginning of osr");

  int mcnt = osr_block->flow()->monitor_count();

  Node *monitors_addr = basic_plus_adr(osr_buf, osr_buf, (max_locals+mcnt*2-1)*wordSize);

  for (index = 0; index < mcnt; index++) {

    // Make a BoxLockNode for the monitor.

    Node *box = _gvn.transform(new (C) BoxLockNode(next_monitor()));

    // Displaced headers and locked objects are interleaved in the

    // temp OSR buffer.  We only copy the locked objects out here.

    // Fetch the locked object from the OSR temp buffer and copy to our fastlock node.

    Node *lock_object = fetch_interpreter_state(index*2, T_OBJECT, monitors_addr, osr_buf);

    // Try and copy the displaced header to the BoxNode

    Node *displaced_hdr = fetch_interpreter_state((index*2) + 1, T_ADDRESS, monitors_addr, osr_buf);

    store_to_memory(control(), box, displaced_hdr, T_ADDRESS, Compile::AliasIdxRaw, MemNode::unordered);

    // Build a bogus FastLockNode (no code will be generated) and push the

    // monitor into our debug info.

    const FastLockNode *flock = _gvn.transform(new (C) FastLockNode( 0, lock_object, box ))->as_FastLock();

    map()->push_monitor(flock);

    // If the lock is our method synchronization lock, tuck it away in

    // _sync_lock for return and rethrow exit paths.

    if (index == 0 && method()->is_synchronized()) {

      _synch_lock = flock;

    }

  }

  // Use the raw liveness computation to make sure that unexpected

  // values don't propagate into the OSR frame.

  MethodLivenessResult live_locals = method()->liveness_at_bci(osr_bci());

  if (!live_locals.is_valid()) {

    // Degenerate or breakpointed method.

    C->record_method_not_compilable("OSR in empty or breakpointed method");

    return;

  }

  // Extract the needed locals from the interpreter frame.

  Node *locals_addr = basic_plus_adr(osr_buf, osr_buf, (max_locals-1)*wordSize);

  // find all the locals that the interpreter thinks contain live oops

  const BitMap live_oops = method()->live_local_oops_at_bci(osr_bci());

  for (index = 0; index < max_locals; index++) {

    if (!live_locals.at(index)) {

      continue;

    }

    const Type *type = osr_block->local_type_at(index);

    if (type->isa_oopptr() != NULL) {

      // 6403625: Verify that the interpreter oopMap thinks that the oop is live

      // else we might load a stale oop if the MethodLiveness disagrees with the

      // result of the interpreter. If the interpreter says it is dead we agree

      // by making the value go to top.

      //

      if (!live_oops.at(index)) {

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

          C->log()->elem("OSR_mismatch local_index='%d'",index);

        }

        set_local(index, null());

        // and ignore it for the loads

        continue;

      }

    }

    // Filter out TOP, HALF, and BOTTOM.  (Cf. ensure_phi.)

    if (type == Type::TOP || type == Type::HALF) {

      continue;

    }

    // If the type falls to bottom, then this must be a local that

    // is mixing ints and oops or some such.  Forcing it to top

    // makes it go dead.

    if (type == Type::BOTTOM) {

      continue;

    }

    // Construct code to access the appropriate local.

    BasicType bt = type->basic_type();

    if (type == TypePtr::NULL_PTR) {

      // Ptr types are mixed together with T_ADDRESS but NULL is

      // really for T_OBJECT types so correct it.

      bt = T_OBJECT;

    }

    Node *value = fetch_interpreter_state(index, bt, locals_addr, osr_buf);

    set_local(index, value);

  }

  // Extract the needed stack entries from the interpreter frame.

  for (index = 0; index < sp(); index++) {

    const Type *type = osr_block->stack_type_at(index);

    if (type != Type::TOP) {

      // Currently the compiler bails out when attempting to on stack replace

      // at a bci with a non-empty stack.  We should not reach here.

      ShouldNotReachHere();

    }

  }

  // End the OSR migration

  make_runtime_call(RC_LEAF, OptoRuntime::osr_end_Type(),

                    CAST_FROM_FN_PTR(address, SharedRuntime::OSR_migration_end),

                    "OSR_migration_end", TypeRawPtr::BOTTOM,

                    osr_buf);

  // Now that the interpreter state is loaded, make sure it will match

  // at execution time what the compiler is expecting now:

  SafePointNode* bad_type_exit = clone_map();

  bad_type_exit->set_control(new (C) RegionNode(1));

  assert(osr_block->flow()->jsrs()->size() == 0, "should be no jsrs live at osr point");

  for (index = 0; index < max_locals; index++) {

    if (stopped())  break;

    Node* l = local(index);

    if (l->is_top())  continue;  // nothing here

    const Type *type = osr_block->local_type_at(index);

    if (type->isa_oopptr() != NULL) {

      if (!live_oops.at(index)) {

        // skip type check for dead oops

        continue;

      }

    }

    if (osr_block->flow()->local_type_at(index)->is_return_address()) {

      // In our current system it's illegal for jsr addresses to be

      // live into an OSR entry point because the compiler performs

      // inlining of jsrs.  ciTypeFlow has a bailout that detect this

      // case and aborts the compile if addresses are live into an OSR

      // entry point.  Because of that we can assume that any address

      // locals at the OSR entry point are dead.  Method liveness

      // isn't precise enought to figure out that they are dead in all

      // cases so simply skip checking address locals all

      // together. Any type check is guaranteed to fail since the

      // interpreter type is the result of a load which might have any

      // value and the expected type is a constant.

      continue;

    }

    set_local(index, check_interpreter_type(l, type, bad_type_exit));

  }

  for (index = 0; index < sp(); index++) {

    if (stopped())  break;

    Node* l = stack(index);

    if (l->is_top())  continue;  // nothing here

    const Type *type = osr_block->stack_type_at(index);

    set_stack(index, check_interpreter_type(l, type, bad_type_exit));

  }

  if (bad_type_exit->control()->req() > 1) {

    // Build an uncommon trap here, if any inputs can be unexpected.

    bad_type_exit->set_control(_gvn.transform( bad_type_exit->control() ));

    record_for_igvn(bad_type_exit->control());

    SafePointNode* types_are_good = map();

    set_map(bad_type_exit);

    // The unexpected type happens because a new edge is active

    // in the CFG, which typeflow had previously ignored.

    // E.g., Object x = coldAtFirst() && notReached()? "str": new Integer(123).

    // This x will be typed as Integer if notReached is not yet linked.

    // It could also happen due to a problem in ciTypeFlow analysis.

    uncommon_trap(Deoptimization::Reason_constraint,

                  Deoptimization::Action_reinterpret);

    set_map(types_are_good);

  }

}

//------------------------------Parse------------------------------------------

// Main parser constructor.

Parse::Parse(JVMState* caller, ciMethod* parse_method, float expected_uses, Parse* parent)

  : _exits(caller), _parent(parent)

{

  // Init some variables

  _caller = caller;

  _method = parse_method;

  _expected_uses = expected_uses;

  _depth = 1 + (caller->has_method() ? caller->depth() : 0);

  _wrote_final = false;

  _wrote_volatile = false;

  _alloc_with_final = NULL;

  _entry_bci = InvocationEntryBci;

  _tf = NULL;

  _block = NULL;

  debug_only(_block_count = -1);

  debug_only(_blocks = (Block*)-1);

#ifndef PRODUCT

  if (PrintCompilation || PrintOpto) {

    // Make sure I have an inline tree, so I can print messages about it.

    JVMState* ilt_caller = is_osr_parse() ? caller->caller() : caller;

    InlineTree::find_subtree_from_root(C->ilt(), ilt_caller, parse_method);

  }

  _max_switch_depth = 0;

  _est_switch_depth = 0;

#endif

  _tf = TypeFunc::make(method());

  _iter.reset_to_method(method());

  _flow = method()->get_flow_analysis();

  if (_flow->failing()) {

    C->record_method_not_compilable_all_tiers(_flow->failure_reason());

  }

#ifndef PRODUCT

  if (_flow->has_irreducible_entry()) {

    C->set_parsed_irreducible_loop(true);

  }

#endif

  if (_expected_uses <= 0) {

    _prof_factor = 1;

  } else {

    float prof_total = parse_method->interpreter_invocation_count();

    if (prof_total <= _expected_uses) {

      _prof_factor = 1;

    } else {

      _prof_factor = _expected_uses / prof_total;

    }

  }

  CompileLog* log = C->log();

  if (log != NULL) {

    log->begin_head("parse method='%d' uses='%g'",

                    log->identify(parse_method), expected_uses);

    if (depth() == 1 && C->is_osr_compilation()) {

      log->print(" osr_bci='%d'", C->entry_bci());

    }

    log->stamp();

    log->end_head();

  }

  // Accumulate deoptimization counts.

  // (The range_check and store_check counts are checked elsewhere.)

  ciMethodData* md = method()->method_data();

  for (uint reason = 0; reason < md->trap_reason_limit(); reason++) {

    uint md_count = md->trap_count(reason);

    if (md_count != 0) {

      if (md_count == md->trap_count_limit())

        md_count += md->overflow_trap_count();

      uint total_count = C->trap_count(reason);

      uint old_count   = total_count;

      total_count += md_count;

      // Saturate the add if it overflows.

      if (total_count < old_count || total_count < md_count)

        total_count = (uint)-1;

      C->set_trap_count(reason, total_count);

      if (log != NULL)

        log->elem("observe trap='%s' count='%d' total='%d'",

                  Deoptimization::trap_reason_name(reason),

                  md_count, total_count);

    }

  }

  // Accumulate total sum of decompilations, also.

  C->set_decompile_count(C->decompile_count() + md->decompile_count());

  _count_invocations = C->do_count_invocations();

  _method_data_update = C->do_method_data_update();

  if (log != NULL && method()->has_exception_handlers()) {

    log->elem("observe that='has_exception_handlers'");

  }

  assert(method()->can_be_compiled(),       "Can not parse this method, cutout earlier");

  assert(method()->has_balanced_monitors(), "Can not parse unbalanced monitors, cutout earlier");

  // Always register dependence if JVMTI is enabled, because

  // either breakpoint setting or hotswapping of methods may

  // cause deoptimization.

  if (C->env()->jvmti_can_hotswap_or_post_breakpoint()) {

    C->dependencies()->assert_evol_method(method());

  }

  methods_seen++;

  // Do some special top-level things.

  if (depth() == 1 && C->is_osr_compilation()) {

    _entry_bci = C->entry_bci();

    _flow = method()->get_osr_flow_analysis(osr_bci());

    if (_flow->failing()) {

      C->record_method_not_compilable(_flow->failure_reason());

#ifndef PRODUCT

      if (PrintOpto && (Verbose || WizardMode)) {

        tty->print_cr("OSR @%d type flow bailout: %s", _entry_bci, _flow->failure_reason());

        if (Verbose) {

          method()->print();

          method()->print_codes();

          _flow->print();

        }

      }

#endif

    }

    _tf = C->tf();     // the OSR entry type is different

  }

#ifdef ASSERT

  if (depth() == 1) {

    assert(C->is_osr_compilation() == this->is_osr_parse(), "OSR in sync");

    if (C->tf() != tf()) {

      MutexLockerEx ml(Compile_lock, Mutex::_no_safepoint_check_flag);

      assert(C->env()->system_dictionary_modification_counter_changed(),

             "Must invalidate if TypeFuncs differ");

    }

  } else {

    assert(!this->is_osr_parse(), "no recursive OSR");

  }