/*

 * Copyright (c) 1997, 2012, 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 "asm/assembler.hpp"

#include "classfile/systemDictionary.hpp"

#include "code/exceptionHandlerTable.hpp"

#include "code/nmethod.hpp"

#include "compiler/compileLog.hpp"

#include "compiler/oopMap.hpp"

#include "opto/addnode.hpp"

#include "opto/block.hpp"

#include "opto/c2compiler.hpp"

#include "opto/callGenerator.hpp"

#include "opto/callnode.hpp"

#include "opto/cfgnode.hpp"

#include "opto/chaitin.hpp"

#include "opto/compile.hpp"

#include "opto/connode.hpp"

#include "opto/divnode.hpp"

#include "opto/escape.hpp"

#include "opto/idealGraphPrinter.hpp"

#include "opto/loopnode.hpp"

#include "opto/machnode.hpp"

#include "opto/macro.hpp"

#include "opto/matcher.hpp"

#include "opto/memnode.hpp"

#include "opto/mulnode.hpp"

#include "opto/node.hpp"

#include "opto/opcodes.hpp"

#include "opto/output.hpp"

#include "opto/parse.hpp"

#include "opto/phaseX.hpp"

#include "opto/rootnode.hpp"

#include "opto/runtime.hpp"

#include "opto/stringopts.hpp"

#include "opto/type.hpp"

#include "opto/vectornode.hpp"

#include "runtime/arguments.hpp"

#include "runtime/signature.hpp"

#include "runtime/stubRoutines.hpp"

#include "runtime/timer.hpp"

#include "utilities/copy.hpp"

#ifdef TARGET_ARCH_MODEL_x86_32

# include "adfiles/ad_x86_32.hpp"

#endif

#ifdef TARGET_ARCH_MODEL_x86_64

# include "adfiles/ad_x86_64.hpp"

#endif

#ifdef TARGET_ARCH_MODEL_sparc

# include "adfiles/ad_sparc.hpp"

#endif

#ifdef TARGET_ARCH_MODEL_zero

# include "adfiles/ad_zero.hpp"

#endif

#ifdef TARGET_ARCH_MODEL_arm

# include "adfiles/ad_arm.hpp"

#endif

#ifdef TARGET_ARCH_MODEL_ppc

# include "adfiles/ad_ppc.hpp"

#endif

// -------------------- Compile::mach_constant_base_node -----------------------

// Constant table base node singleton.

MachConstantBaseNode* Compile::mach_constant_base_node() {

  if (_mach_constant_base_node == NULL) {

    _mach_constant_base_node = new (C) MachConstantBaseNode();

    _mach_constant_base_node->add_req(C->root());

  }

  return _mach_constant_base_node;

}

/// Support for intrinsics.

// Return the index at which m must be inserted (or already exists).

// The sort order is by the address of the ciMethod, with is_virtual as minor key.

int Compile::intrinsic_insertion_index(ciMethod* m, bool is_virtual) {

#ifdef ASSERT

  for (int i = 1; i < _intrinsics->length(); i++) {

    CallGenerator* cg1 = _intrinsics->at(i-1);

    CallGenerator* cg2 = _intrinsics->at(i);

    assert(cg1->method() != cg2->method()

           ? cg1->method()     < cg2->method()

           : cg1->is_virtual() < cg2->is_virtual(),

           "compiler intrinsics list must stay sorted");

  }

#endif

  // Binary search sorted list, in decreasing intervals [lo, hi].

  int lo = 0, hi = _intrinsics->length()-1;

  while (lo <= hi) {

    int mid = (uint)(hi + lo) / 2;

    ciMethod* mid_m = _intrinsics->at(mid)->method();

    if (m < mid_m) {

      hi = mid-1;

    } else if (m > mid_m) {

      lo = mid+1;

    } else {

      // look at minor sort key

      bool mid_virt = _intrinsics->at(mid)->is_virtual();

      if (is_virtual < mid_virt) {

        hi = mid-1;

      } else if (is_virtual > mid_virt) {

        lo = mid+1;

      } else {

        return mid;  // exact match

      }

    }

  }

  return lo;  // inexact match

}

void Compile::register_intrinsic(CallGenerator* cg) {

  if (_intrinsics == NULL) {

    _intrinsics = new GrowableArray<CallGenerator*>(60);

  }

  // This code is stolen from ciObjectFactory::insert.

  // Really, GrowableArray should have methods for

  // insert_at, remove_at, and binary_search.

  int len = _intrinsics->length();

  int index = intrinsic_insertion_index(cg->method(), cg->is_virtual());

  if (index == len) {

    _intrinsics->append(cg);

  } else {

#ifdef ASSERT

    CallGenerator* oldcg = _intrinsics->at(index);

    assert(oldcg->method() != cg->method() || oldcg->is_virtual() != cg->is_virtual(), "don't register twice");

#endif

    _intrinsics->append(_intrinsics->at(len-1));

    int pos;

    for (pos = len-2; pos >= index; pos--) {

      _intrinsics->at_put(pos+1,_intrinsics->at(pos));

    }

    _intrinsics->at_put(index, cg);

  }

  assert(find_intrinsic(cg->method(), cg->is_virtual()) == cg, "registration worked");

}

CallGenerator* Compile::find_intrinsic(ciMethod* m, bool is_virtual) {

  assert(m->is_loaded(), "don't try this on unloaded methods");

  if (_intrinsics != NULL) {

    int index = intrinsic_insertion_index(m, is_virtual);

    if (index < _intrinsics->length()

        && _intrinsics->at(index)->method() == m

        && _intrinsics->at(index)->is_virtual() == is_virtual) {

      return _intrinsics->at(index);

    }

  }

  // Lazily create intrinsics for intrinsic IDs well-known in the runtime.

  if (m->intrinsic_id() != vmIntrinsics::_none &&

      m->intrinsic_id() <= vmIntrinsics::LAST_COMPILER_INLINE) {

    CallGenerator* cg = make_vm_intrinsic(m, is_virtual);

    if (cg != NULL) {

      // Save it for next time:

      register_intrinsic(cg);

      return cg;

    } else {

      gather_intrinsic_statistics(m->intrinsic_id(), is_virtual, _intrinsic_disabled);

    }

  }

  return NULL;

}

// Compile:: register_library_intrinsics and make_vm_intrinsic are defined

// in library_call.cpp.

#ifndef PRODUCT

// statistics gathering...

juint  Compile::_intrinsic_hist_count[vmIntrinsics::ID_LIMIT] = {0};

jubyte Compile::_intrinsic_hist_flags[vmIntrinsics::ID_LIMIT] = {0};

bool Compile::gather_intrinsic_statistics(vmIntrinsics::ID id, bool is_virtual, int flags) {

  assert(id > vmIntrinsics::_none && id < vmIntrinsics::ID_LIMIT, "oob");

  int oflags = _intrinsic_hist_flags[id];

  assert(flags != 0, "what happened?");

  if (is_virtual) {

    flags |= _intrinsic_virtual;

  }

  bool changed = (flags != oflags);

  if ((flags & _intrinsic_worked) != 0) {

    juint count = (_intrinsic_hist_count[id] += 1);

    if (count == 1) {

      changed = true;           // first time

    }

    // increment the overall count also:

    _intrinsic_hist_count[vmIntrinsics::_none] += 1;

  }

  if (changed) {

    if (((oflags ^ flags) & _intrinsic_virtual) != 0) {

      // Something changed about the intrinsic's virtuality.

      if ((flags & _intrinsic_virtual) != 0) {

        // This is the first use of this intrinsic as a virtual call.

        if (oflags != 0) {

          // We already saw it as a non-virtual, so note both cases.

          flags |= _intrinsic_both;

        }

      } else if ((oflags & _intrinsic_both) == 0) {

        // This is the first use of this intrinsic as a non-virtual

        flags |= _intrinsic_both;

      }

    }

    _intrinsic_hist_flags[id] = (jubyte) (oflags | flags);

  }

  // update the overall flags also:

  _intrinsic_hist_flags[vmIntrinsics::_none] |= (jubyte) flags;

  return changed;

}

static char* format_flags(int flags, char* buf) {

  buf[0] = 0;

  if ((flags & Compile::_intrinsic_worked) != 0)    strcat(buf, ",worked");

  if ((flags & Compile::_intrinsic_failed) != 0)    strcat(buf, ",failed");

  if ((flags & Compile::_intrinsic_disabled) != 0)  strcat(buf, ",disabled");

  if ((flags & Compile::_intrinsic_virtual) != 0)   strcat(buf, ",virtual");

  if ((flags & Compile::_intrinsic_both) != 0)      strcat(buf, ",nonvirtual");

  if (buf[0] == 0)  strcat(buf, ",");

  assert(buf[0] == ',', "must be");

  return &buf[1];

}

void Compile::print_intrinsic_statistics() {

  char flagsbuf[100];

  ttyLocker ttyl;

  if (xtty != NULL)  xtty->head("statistics type='intrinsic'");

  tty->print_cr("Compiler intrinsic usage:");

  juint total = _intrinsic_hist_count[vmIntrinsics::_none];

  if (total == 0)  total = 1;  // avoid div0 in case of no successes

  #define PRINT_STAT_LINE(name, c, f) \

    tty->print_cr("  %4d (%4.1f%%) %s (%s)", (int)(c), ((c) * 100.0) / total, name, f);

  for (int index = 1 + (int)vmIntrinsics::_none; index < (int)vmIntrinsics::ID_LIMIT; index++) {

    vmIntrinsics::ID id = (vmIntrinsics::ID) index;

    int   flags = _intrinsic_hist_flags[id];

    juint count = _intrinsic_hist_count[id];

    if ((flags | count) != 0) {

      PRINT_STAT_LINE(vmIntrinsics::name_at(id), count, format_flags(flags, flagsbuf));

    }

  }

  PRINT_STAT_LINE("total", total, format_flags(_intrinsic_hist_flags[vmIntrinsics::_none], flagsbuf));

  if (xtty != NULL)  xtty->tail("statistics");

}

void Compile::print_statistics() {

  { ttyLocker ttyl;

    if (xtty != NULL)  xtty->head("statistics type='opto'");

    Parse::print_statistics();

    PhaseCCP::print_statistics();

    PhaseRegAlloc::print_statistics();

    Scheduling::print_statistics();

    PhasePeephole::print_statistics();

    PhaseIdealLoop::print_statistics();

    if (xtty != NULL)  xtty->tail("statistics");

  }

  if (_intrinsic_hist_flags[vmIntrinsics::_none] != 0) {

    // put this under its own <statistics> element.

    print_intrinsic_statistics();

  }

}

#endif //PRODUCT

// Support for bundling info

Bundle* Compile::node_bundling(const Node *n) {

  assert(valid_bundle_info(n), "oob");

  return &_node_bundling_base[n->_idx];

}

bool Compile::valid_bundle_info(const Node *n) {

  return (_node_bundling_limit > n->_idx);

}

void Compile::gvn_replace_by(Node* n, Node* nn) {

  for (DUIterator_Last imin, i = n->last_outs(imin); i >= imin; ) {

    Node* use = n->last_out(i);

    bool is_in_table = initial_gvn()->hash_delete(use);

    uint uses_found = 0;

    for (uint j = 0; j < use->len(); j++) {

      if (use->in(j) == n) {

        if (j < use->req())

          use->set_req(j, nn);

        else

          use->set_prec(j, nn);

        uses_found++;

      }

    }

    if (is_in_table) {

      // reinsert into table

      initial_gvn()->hash_find_insert(use);

    }

    record_for_igvn(use);

    i -= uses_found;    // we deleted 1 or more copies of this edge

  }

}

// Identify all nodes that are reachable from below, useful.

// Use breadth-first pass that records state in a Unique_Node_List,

// recursive traversal is slower.

void Compile::identify_useful_nodes(Unique_Node_List &useful) {

  int estimated_worklist_size = unique();

  useful.map( estimated_worklist_size, NULL );  // preallocate space

  // Initialize worklist

  if (root() != NULL)     { useful.push(root()); }

  // If 'top' is cached, declare it useful to preserve cached node

  if( cached_top_node() ) { useful.push(cached_top_node()); }

  // Push all useful nodes onto the list, breadthfirst

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

    assert( next < unique(), "Unique useful nodes < total nodes");

    Node *n  = useful.at(next);

    uint max = n->len();

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

      Node *m = n->in(i);

      if( m == NULL ) continue;

      useful.push(m);

    }

  }

}

// Disconnect all useless nodes by disconnecting those at the boundary.

void Compile::remove_useless_nodes(Unique_Node_List &useful) {

  uint next = 0;

  while (next < useful.size()) {

    Node *n = useful.at(next++);

    // Use raw traversal of out edges since this code removes out edges

    int max = n->outcnt();

    for (int j = 0; j < max; ++j) {

      Node* child = n->raw_out(j);

      if (! useful.member(child)) {

        assert(!child->is_top() || child != top(),

               "If top is cached in Compile object it is in useful list");

        // Only need to remove this out-edge to the useless node

        n->raw_del_out(j);

        --j;

        --max;

      }

    }

    if (n->outcnt() == 1 && n->has_special_unique_user()) {

      record_for_igvn(n->unique_out());

    }

  }

  // Remove useless macro and predicate opaq nodes

  for (int i = C->macro_count()-1; i >= 0; i--) {

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

    if (!useful.member(n)) {

      remove_macro_node(n);

    }

  }

  debug_only(verify_graph_edges(true/*check for no_dead_code*/);)

}

//------------------------------frame_size_in_words-----------------------------

// frame_slots in units of words

int Compile::frame_size_in_words() const {

  // shift is 0 in LP32 and 1 in LP64

  const int shift = (LogBytesPerWord - LogBytesPerInt);

  int words = _frame_slots >> shift;

  assert( words << shift == _frame_slots, "frame size must be properly aligned in LP64" );

  return words;

}

// ============================================================================

//------------------------------CompileWrapper---------------------------------

class CompileWrapper : public StackObj {

  Compile *const _compile;

 public:

  CompileWrapper(Compile* compile);

  ~CompileWrapper();

};

CompileWrapper::CompileWrapper(Compile* compile) : _compile(compile) {

  // the Compile* pointer is stored in the current ciEnv:

  ciEnv* env = compile->env();

  assert(env == ciEnv::current(), "must already be a ciEnv active");

  assert(env->compiler_data() == NULL, "compile already active?");

  env->set_compiler_data(compile);

  assert(compile == Compile::current(), "sanity");

  compile->set_type_dict(NULL);

  compile->set_type_hwm(NULL);

  compile->set_type_last_size(0);

  compile->set_last_tf(NULL, NULL);

  compile->set_indexSet_arena(NULL);

  compile->set_indexSet_free_block_list(NULL);

  compile->init_type_arena();

  Type::Initialize(compile);

  _compile->set_scratch_buffer_blob(NULL);

  _compile->begin_method();

}

CompileWrapper::~CompileWrapper() {

  _compile->end_method();

  if (_compile->scratch_buffer_blob() != NULL)

    BufferBlob::free(_compile->scratch_buffer_blob());

  _compile->env()->set_compiler_data(NULL);

}

//----------------------------print_compile_messages---------------------------

void Compile::print_compile_messages() {

#ifndef PRODUCT

  // Check if recompiling

  if (_subsume_loads == false && PrintOpto) {

    // Recompiling without allowing machine instructions to subsume loads

    tty->print_cr("*********************************************************");

    tty->print_cr("** Bailout: Recompile without subsuming loads          **");

    tty->print_cr("*********************************************************");

  }

  if (_do_escape_analysis != DoEscapeAnalysis && PrintOpto) {

    // Recompiling without escape analysis

    tty->print_cr("*********************************************************");

    tty->print_cr("** Bailout: Recompile without escape analysis          **");

    tty->print_cr("*********************************************************");

  }

  if (env()->break_at_compile()) {

    // Open the debugger when compiling this method.

    tty->print("### Breaking when compiling: ");

    method()->print_short_name();

    tty->cr();

    BREAKPOINT;

  }

  if( PrintOpto ) {

    if (is_osr_compilation()) {

      tty->print("[OSR]%3d", _compile_id);

    } else {

      tty->print("%3d", _compile_id);

    }

  }

#endif

}

//-----------------------init_scratch_buffer_blob------------------------------

// Construct a temporary BufferBlob and cache it for this compile.

void Compile::init_scratch_buffer_blob(int const_size) {

  // If there is already a scratch buffer blob allocated and the

  // constant section is big enough, use it.  Otherwise free the

  // current and allocate a new one.

  BufferBlob* blob = scratch_buffer_blob();

  if ((blob != NULL) && (const_size <= _scratch_const_size)) {

    // Use the current blob.

  } else {

    if (blob != NULL) {

      BufferBlob::free(blob);

    }

    ResourceMark rm;

    _scratch_const_size = const_size;

    int size = (MAX_inst_size + MAX_stubs_size + _scratch_const_size);

    blob = BufferBlob::create("Compile::scratch_buffer", size);

    // Record the buffer blob for next time.

    set_scratch_buffer_blob(blob);

    // Have we run out of code space?

    if (scratch_buffer_blob() == NULL) {

      // Let CompilerBroker disable further compilations.

      record_failure("Not enough space for scratch buffer in CodeCache");

      return;

    }

  }

  // Initialize the relocation buffers

  relocInfo* locs_buf = (relocInfo*) blob->content_end() - MAX_locs_size;

  set_scratch_locs_memory(locs_buf);

}

//-----------------------scratch_emit_size-------------------------------------

// Helper function that computes size by emitting code

uint Compile::scratch_emit_size(const Node* n) {

  // Start scratch_emit_size section.

  set_in_scratch_emit_size(true);

  // Emit into a trash buffer and count bytes emitted.

  // This is a pretty expensive way to compute a size,

  // but it works well enough if seldom used.

  // All common fixed-size instructions are given a size

  // method by the AD file.

  // Note that the scratch buffer blob and locs memory are

  // allocated at the beginning of the compile task, and

  // may be shared by several calls to scratch_emit_size.

  // The allocation of the scratch buffer blob is particularly

  // expensive, since it has to grab the code cache lock.

  BufferBlob* blob = this->scratch_buffer_blob();

  assert(blob != NULL, "Initialize BufferBlob at start");

  assert(blob->size() > MAX_inst_size, "sanity");

  relocInfo* locs_buf = scratch_locs_memory();

  address blob_begin = blob->content_begin();

  address blob_end   = (address)locs_buf;

  assert(blob->content_contains(blob_end), "sanity");