/*

 * Copyright 1997-2007 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/_compile.cpp.incl"

/// 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) {

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

}

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

    }

  }

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

  if (_compile->failing()) {

    _compile->print_method("Failed");

  }

  _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 compiing 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

}

void Compile::init_scratch_buffer_blob() {

  if( scratch_buffer_blob() != NULL )  return;

  // Construct a temporary CodeBuffer to have it construct a BufferBlob

  // Cache this BufferBlob for this compile.

  ResourceMark rm;

  int size = (MAX_inst_size + MAX_stubs_size + MAX_const_size);

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

  // Record the buffer blob for next time.

  set_scratch_buffer_blob(blob);

  guarantee(scratch_buffer_blob() != NULL, "Need BufferBlob for code generation");

  // Initialize the relocation buffers

  relocInfo* locs_buf = (relocInfo*) blob->instructions_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) {

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

  address blob_end   = (address)locs_buf;

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

  CodeBuffer buf(blob_begin, blob_end - blob_begin);

  buf.initialize_consts_size(MAX_const_size);

  buf.initialize_stubs_size(MAX_stubs_size);

  assert(locs_buf != NULL, "sanity");

  int lsize = MAX_locs_size / 2;

  buf.insts()->initialize_shared_locs(&locs_buf[0],     lsize);

  buf.stubs()->initialize_shared_locs(&locs_buf[lsize], lsize);

  n->emit(buf, this->regalloc());

  return buf.code_size();

}

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

//------------------------------Compile standard-------------------------------

debug_only( int Compile::_debug_idx = 100000; )

// Compile a method.  entry_bci is -1 for normal compilations and indicates

// the continuation bci for on stack replacement.

Compile::Compile( ciEnv* ci_env, C2Compiler* compiler, ciMethod* target, int osr_bci, bool subsume_loads, bool do_escape_analysis )

                : Phase(Compiler),

                  _env(ci_env),

                  _log(ci_env->log()),

                  _compile_id(ci_env->compile_id()),

                  _save_argument_registers(false),

                  _stub_name(NULL),

                  _stub_function(NULL),

                  _stub_entry_point(NULL),

                  _method(target),

                  _entry_bci(osr_bci),

                  _initial_gvn(NULL),

                  _for_igvn(NULL),

                  _warm_calls(NULL),

                  _subsume_loads(subsume_loads),

                  _do_escape_analysis(do_escape_analysis),

                  _failure_reason(NULL),

                  _code_buffer("Compile::Fill_buffer"),

                  _orig_pc_slot(0),

                  _orig_pc_slot_offset_in_bytes(0),

                  _node_bundling_limit(0),

                  _node_bundling_base(NULL),

#ifndef PRODUCT

                  _trace_opto_output(TraceOptoOutput || method()->has_option("TraceOptoOutput")),

                  _printer(IdealGraphPrinter::printer()),

#endif

                  _congraph(NULL) {

  C = this;

  CompileWrapper cw(this);

#ifndef PRODUCT

  if (TimeCompiler2) {

    tty->print(" ");

    target->holder()->name()->print();

    tty->print(".");

    target->print_short_name();

    tty->print("  ");

  }

  TraceTime t1("Total compilation time", &_t_totalCompilation, TimeCompiler, TimeCompiler2);

  TraceTime t2(NULL, &_t_methodCompilation, TimeCompiler, false);

  bool print_opto_assembly = PrintOptoAssembly || _method->has_option("PrintOptoAssembly");

  if (!print_opto_assembly) {

    bool print_assembly = (PrintAssembly || _method->should_print_assembly());

    if (print_assembly && !Disassembler::can_decode()) {

      tty->print_cr("PrintAssembly request changed to PrintOptoAssembly");

      print_opto_assembly = true;

    }

  }

  set_print_assembly(print_opto_assembly);

#endif

  if (ProfileTraps) {

    // Make sure the method being compiled gets its own MDO,

    // so we can at least track the decompile_count().

    method()->build_method_data();

  }

  Init(::AliasLevel);

  print_compile_messages();

  if (UseOldInlining || PrintCompilation NOT_PRODUCT( || PrintOpto) )

    _ilt = InlineTree::build_inline_tree_root();

  else

    _ilt = NULL;

  // Even if NO memory addresses are used, MergeMem nodes must have at least 1 slice

  assert(num_alias_types() >= AliasIdxRaw, "");

#define MINIMUM_NODE_HASH  1023

  // Node list that Iterative GVN will start with

  Unique_Node_List for_igvn(comp_arena());

  set_for_igvn(&for_igvn);

  // GVN that will be run immediately on new nodes

  uint estimated_size = method()->code_size()*4+64;

  estimated_size = (estimated_size < MINIMUM_NODE_HASH ? MINIMUM_NODE_HASH : estimated_size);

  PhaseGVN gvn(node_arena(), estimated_size);

  set_initial_gvn(&gvn);

  { // Scope for timing the parser

    TracePhase t3("parse", &_t_parser, true);

    // Put top into the hash table ASAP.

    initial_gvn()->transform_no_reclaim(top());

    // Set up tf(), start(), and find a CallGenerator.

    CallGenerator* cg;

    if (is_osr_compilation()) {

      const TypeTuple *domain = StartOSRNode::osr_domain();

      const TypeTuple *range = TypeTuple::make_range(method()->signature());

      init_tf(TypeFunc::make(domain, range));

      StartNode* s = new (this, 2) StartOSRNode(root(), domain);

      initial_gvn()->set_type_bottom(s);

      init_start(s);

      cg = CallGenerator::for_osr(method(), entry_bci());

    } else {

      // Normal case.

      init_tf(TypeFunc::make(method()));

      StartNode* s = new (this, 2) StartNode(root(), tf()->domain());

      initial_gvn()->set_type_bottom(s);

      init_start(s);

      float past_uses = method()->interpreter_invocation_count();

      float expected_uses = past_uses;

      cg = CallGenerator::for_inline(method(), expected_uses);

    }

    if (failing())  return;

    if (cg == NULL) {