/*

 * 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 "memory/allocation.inline.hpp"

#include "opto/ad.hpp"

#include "opto/addnode.hpp"

#include "opto/callnode.hpp"

#include "opto/idealGraphPrinter.hpp"

#include "opto/matcher.hpp"

#include "opto/memnode.hpp"

#include "opto/movenode.hpp"

#include "opto/opcodes.hpp"

#include "opto/regmask.hpp"

#include "opto/rootnode.hpp"

#include "opto/runtime.hpp"

#include "opto/type.hpp"

#include "opto/vectornode.hpp"

#include "runtime/os.hpp"

OptoReg::Name OptoReg::c_frame_pointer;

const RegMask *Matcher::idealreg2regmask[_last_machine_leaf];

RegMask Matcher::mreg2regmask[_last_Mach_Reg];

RegMask Matcher::STACK_ONLY_mask;

RegMask Matcher::c_frame_ptr_mask;

const uint Matcher::_begin_rematerialize = _BEGIN_REMATERIALIZE;

const uint Matcher::_end_rematerialize   = _END_REMATERIALIZE;

//---------------------------Matcher-------------------------------------------

Matcher::Matcher()

: PhaseTransform( Phase::Ins_Select ),

#ifdef ASSERT

  _old2new_map(C->comp_arena()),

  _new2old_map(C->comp_arena()),

#endif

  _shared_nodes(C->comp_arena()),

  _reduceOp(reduceOp), _leftOp(leftOp), _rightOp(rightOp),

  _swallowed(swallowed),

  _begin_inst_chain_rule(_BEGIN_INST_CHAIN_RULE),

  _end_inst_chain_rule(_END_INST_CHAIN_RULE),

  _must_clone(must_clone),

  _register_save_policy(register_save_policy),

  _c_reg_save_policy(c_reg_save_policy),

  _register_save_type(register_save_type),

  _ruleName(ruleName),

  _allocation_started(false),

  _states_arena(Chunk::medium_size),

  _visited(&_states_arena),

  _shared(&_states_arena),

  _dontcare(&_states_arena) {

  C->set_matcher(this);

  idealreg2spillmask  [Op_RegI] = NULL;

  idealreg2spillmask  [Op_RegN] = NULL;

  idealreg2spillmask  [Op_RegL] = NULL;

  idealreg2spillmask  [Op_RegF] = NULL;

  idealreg2spillmask  [Op_RegD] = NULL;

  idealreg2spillmask  [Op_RegP] = NULL;

  idealreg2spillmask  [Op_VecS] = NULL;

  idealreg2spillmask  [Op_VecD] = NULL;

  idealreg2spillmask  [Op_VecX] = NULL;

  idealreg2spillmask  [Op_VecY] = NULL;

  idealreg2debugmask  [Op_RegI] = NULL;

  idealreg2debugmask  [Op_RegN] = NULL;

  idealreg2debugmask  [Op_RegL] = NULL;

  idealreg2debugmask  [Op_RegF] = NULL;

  idealreg2debugmask  [Op_RegD] = NULL;

  idealreg2debugmask  [Op_RegP] = NULL;

  idealreg2debugmask  [Op_VecS] = NULL;

  idealreg2debugmask  [Op_VecD] = NULL;

  idealreg2debugmask  [Op_VecX] = NULL;

  idealreg2debugmask  [Op_VecY] = NULL;

  idealreg2mhdebugmask[Op_RegI] = NULL;

  idealreg2mhdebugmask[Op_RegN] = NULL;

  idealreg2mhdebugmask[Op_RegL] = NULL;

  idealreg2mhdebugmask[Op_RegF] = NULL;

  idealreg2mhdebugmask[Op_RegD] = NULL;

  idealreg2mhdebugmask[Op_RegP] = NULL;

  idealreg2mhdebugmask[Op_VecS] = NULL;

  idealreg2mhdebugmask[Op_VecD] = NULL;

  idealreg2mhdebugmask[Op_VecX] = NULL;

  idealreg2mhdebugmask[Op_VecY] = NULL;

  debug_only(_mem_node = NULL;)   // Ideal memory node consumed by mach node

}

//------------------------------warp_incoming_stk_arg------------------------

// This warps a VMReg into an OptoReg::Name

OptoReg::Name Matcher::warp_incoming_stk_arg( VMReg reg ) {

  OptoReg::Name warped;

  if( reg->is_stack() ) {  // Stack slot argument?

    warped = OptoReg::add(_old_SP, reg->reg2stack() );

    warped = OptoReg::add(warped, C->out_preserve_stack_slots());

    if( warped >= _in_arg_limit )

      _in_arg_limit = OptoReg::add(warped, 1); // Bump max stack slot seen

    if (!RegMask::can_represent_arg(warped)) {

      // the compiler cannot represent this method's calling sequence

      C->record_method_not_compilable_all_tiers("unsupported incoming calling sequence");

      return OptoReg::Bad;

    }

    return warped;

  }

  return OptoReg::as_OptoReg(reg);

}

//---------------------------compute_old_SP------------------------------------

OptoReg::Name Compile::compute_old_SP() {

  int fixed    = fixed_slots();

  int preserve = in_preserve_stack_slots();

  return OptoReg::stack2reg(round_to(fixed + preserve, Matcher::stack_alignment_in_slots()));

}

#ifdef ASSERT

void Matcher::verify_new_nodes_only(Node* xroot) {

  // Make sure that the new graph only references new nodes

  ResourceMark rm;

  Unique_Node_List worklist;

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

  worklist.push(xroot);

  while (worklist.size() > 0) {

    Node* n = worklist.pop();

    visited <<= n->_idx;

    assert(C->node_arena()->contains(n), "dead node");

    for (uint j = 0; j < n->req(); j++) {

      Node* in = n->in(j);

      if (in != NULL) {

        assert(C->node_arena()->contains(in), "dead node");

        if (!visited.test(in->_idx)) {

          worklist.push(in);

        }

      }

    }

  }

}

#endif

//---------------------------match---------------------------------------------

void Matcher::match( ) {

  if( MaxLabelRootDepth < 100 ) { // Too small?

    assert(false, "invalid MaxLabelRootDepth, increase it to 100 minimum");

    MaxLabelRootDepth = 100;

  }

  // One-time initialization of some register masks.

  init_spill_mask( C->root()->in(1) );

  _return_addr_mask = return_addr();

#ifdef _LP64

  // Pointers take 2 slots in 64-bit land

  _return_addr_mask.Insert(OptoReg::add(return_addr(),1));

#endif

  // Map a Java-signature return type into return register-value

  // machine registers for 0, 1 and 2 returned values.

  const TypeTuple *range = C->tf()->range();

  if( range->cnt() > TypeFunc::Parms ) { // If not a void function

    // Get ideal-register return type

    int ireg = range->field_at(TypeFunc::Parms)->ideal_reg();

    // Get machine return register

    uint sop = C->start()->Opcode();

    OptoRegPair regs = return_value(ireg, false);

    // And mask for same

    _return_value_mask = RegMask(regs.first());

    if( OptoReg::is_valid(regs.second()) )

      _return_value_mask.Insert(regs.second());

  }

  // ---------------

  // Frame Layout

  // Need the method signature to determine the incoming argument types,

  // because the types determine which registers the incoming arguments are

  // in, and this affects the matched code.

  const TypeTuple *domain = C->tf()->domain();

  uint             argcnt = domain->cnt() - TypeFunc::Parms;

  BasicType *sig_bt        = NEW_RESOURCE_ARRAY( BasicType, argcnt );

  VMRegPair *vm_parm_regs  = NEW_RESOURCE_ARRAY( VMRegPair, argcnt );

  _parm_regs               = NEW_RESOURCE_ARRAY( OptoRegPair, argcnt );

  _calling_convention_mask = NEW_RESOURCE_ARRAY( RegMask, argcnt );

  uint i;

  for( i = 0; i<argcnt; i++ ) {

    sig_bt[i] = domain->field_at(i+TypeFunc::Parms)->basic_type();

  }

  // Pass array of ideal registers and length to USER code (from the AD file)

  // that will convert this to an array of register numbers.

  const StartNode *start = C->start();

  start->calling_convention( sig_bt, vm_parm_regs, argcnt );

#ifdef ASSERT

  // Sanity check users' calling convention.  Real handy while trying to

  // get the initial port correct.

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

      if( !vm_parm_regs[i].first()->is_valid() && !vm_parm_regs[i].second()->is_valid() ) {

        assert(domain->field_at(i+TypeFunc::Parms)==Type::HALF, "only allowed on halve" );

        _parm_regs[i].set_bad();

        continue;

      }

      VMReg parm_reg = vm_parm_regs[i].first();

      assert(parm_reg->is_valid(), "invalid arg?");

      if (parm_reg->is_reg()) {

        OptoReg::Name opto_parm_reg = OptoReg::as_OptoReg(parm_reg);

        assert(can_be_java_arg(opto_parm_reg) ||

               C->stub_function() == CAST_FROM_FN_PTR(address, OptoRuntime::rethrow_C) ||

               opto_parm_reg == inline_cache_reg(),

               "parameters in register must be preserved by runtime stubs");

      }

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

        assert(parm_reg != vm_parm_regs[j].first(),

               "calling conv. must produce distinct regs");

      }

    }

  }

#endif

  // Do some initial frame layout.

  // Compute the old incoming SP (may be called FP) as

  //   OptoReg::stack0() + locks + in_preserve_stack_slots + pad2.

  _old_SP = C->compute_old_SP();

  assert( is_even(_old_SP), "must be even" );

  // Compute highest incoming stack argument as

  //   _old_SP + out_preserve_stack_slots + incoming argument size.

  _in_arg_limit = OptoReg::add(_old_SP, C->out_preserve_stack_slots());

  assert( is_even(_in_arg_limit), "out_preserve must be even" );

  for( i = 0; i < argcnt; i++ ) {

    // Permit args to have no register

    _calling_convention_mask[i].Clear();

    if( !vm_parm_regs[i].first()->is_valid() && !vm_parm_regs[i].second()->is_valid() ) {

      continue;

    }

    // calling_convention returns stack arguments as a count of

    // slots beyond OptoReg::stack0()/VMRegImpl::stack0.  We need to convert this to

    // the allocators point of view, taking into account all the

    // preserve area, locks & pad2.

    OptoReg::Name reg1 = warp_incoming_stk_arg(vm_parm_regs[i].first());

    if( OptoReg::is_valid(reg1))

      _calling_convention_mask[i].Insert(reg1);

    OptoReg::Name reg2 = warp_incoming_stk_arg(vm_parm_regs[i].second());

    if( OptoReg::is_valid(reg2))

      _calling_convention_mask[i].Insert(reg2);

    // Saved biased stack-slot register number

    _parm_regs[i].set_pair(reg2, reg1);

  }

  // Finally, make sure the incoming arguments take up an even number of

  // words, in case the arguments or locals need to contain doubleword stack

  // slots.  The rest of the system assumes that stack slot pairs (in

  // particular, in the spill area) which look aligned will in fact be

  // aligned relative to the stack pointer in the target machine.  Double

  // stack slots will always be allocated aligned.

  _new_SP = OptoReg::Name(round_to(_in_arg_limit, RegMask::SlotsPerLong));

  // Compute highest outgoing stack argument as

  //   _new_SP + out_preserve_stack_slots + max(outgoing argument size).

  _out_arg_limit = OptoReg::add(_new_SP, C->out_preserve_stack_slots());

  assert( is_even(_out_arg_limit), "out_preserve must be even" );

  if (!RegMask::can_represent_arg(OptoReg::add(_out_arg_limit,-1))) {

    // the compiler cannot represent this method's calling sequence

    C->record_method_not_compilable("must be able to represent all call arguments in reg mask");

  }

  if (C->failing())  return;  // bailed out on incoming arg failure

  // ---------------

  // Collect roots of matcher trees.  Every node for which

  // _shared[_idx] is cleared is guaranteed to not be shared, and thus

  // can be a valid interior of some tree.

  find_shared( C->root() );

  find_shared( C->top() );

  C->print_method(PHASE_BEFORE_MATCHING);

  // Create new ideal node ConP #NULL even if it does exist in old space

  // to avoid false sharing if the corresponding mach node is not used.

  // The corresponding mach node is only used in rare cases for derived

  // pointers.

  Node* new_ideal_null = ConNode::make(TypePtr::NULL_PTR);

  // Swap out to old-space; emptying new-space

  Arena *old = C->node_arena()->move_contents(C->old_arena());

  // Save debug and profile information for nodes in old space:

  _old_node_note_array = C->node_note_array();

  if (_old_node_note_array != NULL) {

    C->set_node_note_array(new(C->comp_arena()) GrowableArray<Node_Notes*>

                           (C->comp_arena(), _old_node_note_array->length(),

                            0, NULL));

  }

  // Pre-size the new_node table to avoid the need for range checks.

  grow_new_node_array(C->unique());

  // Reset node counter so MachNodes start with _idx at 0

  int nodes = C->unique(); // save value

  C->set_unique(0);

  C->reset_dead_node_list();

  // Recursively match trees from old space into new space.

  // Correct leaves of new-space Nodes; they point to old-space.

  _visited.Clear();             // Clear visit bits for xform call

  C->set_cached_top_node(xform( C->top(), nodes ));

  if (!C->failing()) {

    Node* xroot =        xform( C->root(), 1 );

    if (xroot == NULL) {

      Matcher::soft_match_failure();  // recursive matching process failed

      C->record_method_not_compilable("instruction match failed");

    } else {

      // During matching shared constants were attached to C->root()

      // because xroot wasn't available yet, so transfer the uses to

      // the xroot.

      for( DUIterator_Fast jmax, j = C->root()->fast_outs(jmax); j < jmax; j++ ) {

        Node* n = C->root()->fast_out(j);

        if (C->node_arena()->contains(n)) {

          assert(n->in(0) == C->root(), "should be control user");

          n->set_req(0, xroot);

          --j;

          --jmax;

        }

      }

      // Generate new mach node for ConP #NULL

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

      _mach_null = match_tree(new_ideal_null);

      // Don't set control, it will confuse GCM since there are no uses.

      // The control will be set when this node is used first time

      // in find_base_for_derived().

      assert(_mach_null != NULL, "");

      C->set_root(xroot->is_Root() ? xroot->as_Root() : NULL);

#ifdef ASSERT

      verify_new_nodes_only(xroot);

#endif

    }

  }

  if (C->top() == NULL || C->root() == NULL) {

    C->record_method_not_compilable("graph lost"); // %%% cannot happen?

  }

  if (C->failing()) {

    // delete old;

    old->destruct_contents();

    return;

  }

  assert( C->top(), "" );

  assert( C->root(), "" );

  validate_null_checks();

  // Now smoke old-space

  NOT_DEBUG( old->destruct_contents() );

  // ------------------------

  // Set up save-on-entry registers

  Fixup_Save_On_Entry( );

}

//------------------------------Fixup_Save_On_Entry----------------------------

// The stated purpose of this routine is to take care of save-on-entry

// registers.  However, the overall goal of the Match phase is to convert into

// machine-specific instructions which have RegMasks to guide allocation.

// So what this procedure really does is put a valid RegMask on each input

// to the machine-specific variations of all Return, TailCall and Halt

// instructions.  It also adds edgs to define the save-on-entry values (and of

// course gives them a mask).

static RegMask *init_input_masks( uint size, RegMask &ret_adr, RegMask &fp ) {

  RegMask *rms = NEW_RESOURCE_ARRAY( RegMask, size );

  // Do all the pre-defined register masks

  rms[TypeFunc::Control  ] = RegMask::Empty;

  rms[TypeFunc::I_O      ] = RegMask::Empty;

  rms[TypeFunc::Memory   ] = RegMask::Empty;

  rms[TypeFunc::ReturnAdr] = ret_adr;

  rms[TypeFunc::FramePtr ] = fp;

  return rms;

}

//---------------------------init_first_stack_mask-----------------------------

// Create the initial stack mask used by values spilling to the stack.

// Disallow any debug info in outgoing argument areas by setting the

// initial mask accordingly.

void Matcher::init_first_stack_mask() {

  // Allocate storage for spill masks as masks for the appropriate load type.

  RegMask *rms = (RegMask*)C->comp_arena()->Amalloc_D(sizeof(RegMask) * (3*6+4));

  idealreg2spillmask  [Op_RegN] = &rms[0];

  idealreg2spillmask  [Op_RegI] = &rms[1];

  idealreg2spillmask  [Op_RegL] = &rms[2];

  idealreg2spillmask  [Op_RegF] = &rms[3];

  idealreg2spillmask  [Op_RegD] = &rms[4];

  idealreg2spillmask  [Op_RegP] = &rms[5];

  idealreg2debugmask  [Op_RegN] = &rms[6];

  idealreg2debugmask  [Op_RegI] = &rms[7];

  idealreg2debugmask  [Op_RegL] = &rms[8];

  idealreg2debugmask  [Op_RegF] = &rms[9];

  idealreg2debugmask  [Op_RegD] = &rms[10];

  idealreg2debugmask  [Op_RegP] = &rms[11];

  idealreg2mhdebugmask[Op_RegN] = &rms[12];

  idealreg2mhdebugmask[Op_RegI] = &rms[13];

  idealreg2mhdebugmask[Op_RegL] = &rms[14];

  idealreg2mhdebugmask[Op_RegF] = &rms[15];

  idealreg2mhdebugmask[Op_RegD] = &rms[16];

  idealreg2mhdebugmask[Op_RegP] = &rms[17];

  idealreg2spillmask  [Op_VecS] = &rms[18];

  idealreg2spillmask  [Op_VecD] = &rms[19];

  idealreg2spillmask  [Op_VecX] = &rms[20];

  idealreg2spillmask  [Op_VecY] = &rms[21];

  OptoReg::Name i;

  // At first, start with the empty mask

  C->FIRST_STACK_mask().Clear();

  // Add in the incoming argument area

  OptoReg::Name init_in = OptoReg::add(_old_SP, C->out_preserve_stack_slots());

  for (i = init_in; i < _in_arg_limit; i = OptoReg::add(i,1)) {

    C->FIRST_STACK_mask().Insert(i);

  }

  // Add in all bits past the outgoing argument area

  guarantee(RegMask::can_represent_arg(OptoReg::add(_out_arg_limit,-1)),

            "must be able to represent all call arguments in reg mask");

  OptoReg::Name init = _out_arg_limit;

  for (i = init; RegMask::can_represent(i); i = OptoReg::add(i,1)) {

    C->FIRST_STACK_mask().Insert(i);

  }

  // Finally, set the "infinite stack" bit.

  C->FIRST_STACK_mask().set_AllStack();

  // Make spill masks.  Registers for their class, plus FIRST_STACK_mask.

  RegMask aligned_stack_mask = C->FIRST_STACK_mask();

  // Keep spill masks aligned.

  aligned_stack_mask.clear_to_pairs();

  assert(aligned_stack_mask.is_AllStack(), "should be infinite stack");

  *idealreg2spillmask[Op_RegP] = *idealreg2regmask[Op_RegP];

#ifdef _LP64

  *idealreg2spillmask[Op_RegN] = *idealreg2regmask[Op_RegN];

   idealreg2spillmask[Op_RegN]->OR(C->FIRST_STACK_mask());

   idealreg2spillmask[Op_RegP]->OR(aligned_stack_mask);

#else

   idealreg2spillmask[Op_RegP]->OR(C->FIRST_STACK_mask());

#endif

  *idealreg2spillmask[Op_RegI] = *idealreg2regmask[Op_RegI];

   idealreg2spillmask[Op_RegI]->OR(C->FIRST_STACK_mask());

  *idealreg2spillmask[Op_RegL] = *idealreg2regmask[Op_RegL];

   idealreg2spillmask[Op_RegL]->OR(aligned_stack_mask);

  *idealreg2spillmask[Op_RegF] = *idealreg2regmask[Op_RegF];

   idealreg2spillmask[Op_RegF]->OR(C->FIRST_STACK_mask());

  *idealreg2spillmask[Op_RegD] = *idealreg2regmask[Op_RegD];

   idealreg2spillmask[Op_RegD]->OR(aligned_stack_mask);

  if (Matcher::vector_size_supported(T_BYTE,4)) {

    *idealreg2spillmask[Op_VecS] = *idealreg2regmask[Op_VecS];

     idealreg2spillmask[Op_VecS]->OR(C->FIRST_STACK_mask());

  }

  if (Matcher::vector_size_supported(T_FLOAT,2)) {

    // For VecD we need dual alignment and 8 bytes (2 slots) for spills.

    // RA guarantees such alignment since it is needed for Double and Long values.

    *idealreg2spillmask[Op_VecD] = *idealreg2regmask[Op_VecD];

     idealreg2spillmask[Op_VecD]->OR(aligned_stack_mask);

  }

  if (Matcher::vector_size_supported(T_FLOAT,4)) {

    // For VecX we need quadro alignment and 16 bytes (4 slots) for spills.

    //

    // RA can use input arguments stack slots for spills but until RA

    // we don't know frame size and offset of input arg stack slots.

    //

    // Exclude last input arg stack slots to avoid spilling vectors there

    // otherwise vector spills could stomp over stack slots in caller frame.

    OptoReg::Name in = OptoReg::add(_in_arg_limit, -1);

    for (int k = 1; (in >= init_in) && (k < RegMask::SlotsPerVecX); k++) {

      aligned_stack_mask.Remove(in);

      in = OptoReg::add(in, -1);

    }

     aligned_stack_mask.clear_to_sets(RegMask::SlotsPerVecX);

     assert(aligned_stack_mask.is_AllStack(), "should be infinite stack");

    *idealreg2spillmask[Op_VecX] = *idealreg2regmask[Op_VecX];

     idealreg2spillmask[Op_VecX]->OR(aligned_stack_mask);