/*

 * Copyright 2005-2009 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/_c1_LIRGenerator.cpp.incl"

#ifdef ASSERT

#define __ gen()->lir(__FILE__, __LINE__)->

#else

#define __ gen()->lir()->

#endif

void PhiResolverState::reset(int max_vregs) {

  // Initialize array sizes

  _virtual_operands.at_put_grow(max_vregs - 1, NULL, NULL);

  _virtual_operands.trunc_to(0);

  _other_operands.at_put_grow(max_vregs - 1, NULL, NULL);

  _other_operands.trunc_to(0);

  _vreg_table.at_put_grow(max_vregs - 1, NULL, NULL);

  _vreg_table.trunc_to(0);

}

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

// PhiResolver

// Resolves cycles:

//

//  r1 := r2  becomes  temp := r1

//  r2 := r1           r1 := r2

//                     r2 := temp

// and orders moves:

//

//  r2 := r3  becomes  r1 := r2

//  r1 := r2           r2 := r3

PhiResolver::PhiResolver(LIRGenerator* gen, int max_vregs)

 : _gen(gen)

 , _state(gen->resolver_state())

 , _temp(LIR_OprFact::illegalOpr)

{

  // reinitialize the shared state arrays

  _state.reset(max_vregs);

}

void PhiResolver::emit_move(LIR_Opr src, LIR_Opr dest) {

  assert(src->is_valid(), "");

  assert(dest->is_valid(), "");

  __ move(src, dest);

}

void PhiResolver::move_temp_to(LIR_Opr dest) {

  assert(_temp->is_valid(), "");

  emit_move(_temp, dest);

  NOT_PRODUCT(_temp = LIR_OprFact::illegalOpr);

}

void PhiResolver::move_to_temp(LIR_Opr src) {

  assert(_temp->is_illegal(), "");

  _temp = _gen->new_register(src->type());

  emit_move(src, _temp);

}

// Traverse assignment graph in depth first order and generate moves in post order

// ie. two assignments: b := c, a := b start with node c:

// Call graph: move(NULL, c) -> move(c, b) -> move(b, a)

// Generates moves in this order: move b to a and move c to b

// ie. cycle a := b, b := a start with node a

// Call graph: move(NULL, a) -> move(a, b) -> move(b, a)

// Generates moves in this order: move b to temp, move a to b, move temp to a

void PhiResolver::move(ResolveNode* src, ResolveNode* dest) {

  if (!dest->visited()) {

    dest->set_visited();

    for (int i = dest->no_of_destinations()-1; i >= 0; i --) {

      move(dest, dest->destination_at(i));

    }

  } else if (!dest->start_node()) {

    // cylce in graph detected

    assert(_loop == NULL, "only one loop valid!");

    _loop = dest;

    move_to_temp(src->operand());

    return;

  } // else dest is a start node

  if (!dest->assigned()) {

    if (_loop == dest) {

      move_temp_to(dest->operand());

      dest->set_assigned();

    } else if (src != NULL) {

      emit_move(src->operand(), dest->operand());

      dest->set_assigned();

    }

  }

}

PhiResolver::~PhiResolver() {

  int i;

  // resolve any cycles in moves from and to virtual registers

  for (i = virtual_operands().length() - 1; i >= 0; i --) {

    ResolveNode* node = virtual_operands()[i];

    if (!node->visited()) {

      _loop = NULL;

      move(NULL, node);

      node->set_start_node();

      assert(_temp->is_illegal(), "move_temp_to() call missing");

    }

  }

  // generate move for move from non virtual register to abitrary destination

  for (i = other_operands().length() - 1; i >= 0; i --) {

    ResolveNode* node = other_operands()[i];

    for (int j = node->no_of_destinations() - 1; j >= 0; j --) {

      emit_move(node->operand(), node->destination_at(j)->operand());

    }

  }

}

ResolveNode* PhiResolver::create_node(LIR_Opr opr, bool source) {

  ResolveNode* node;

  if (opr->is_virtual()) {

    int vreg_num = opr->vreg_number();

    node = vreg_table().at_grow(vreg_num, NULL);

    assert(node == NULL || node->operand() == opr, "");

    if (node == NULL) {

      node = new ResolveNode(opr);

      vreg_table()[vreg_num] = node;

    }

    // Make sure that all virtual operands show up in the list when

    // they are used as the source of a move.

    if (source && !virtual_operands().contains(node)) {

      virtual_operands().append(node);

    }

  } else {

    assert(source, "");

    node = new ResolveNode(opr);

    other_operands().append(node);

  }

  return node;

}

void PhiResolver::move(LIR_Opr src, LIR_Opr dest) {

  assert(dest->is_virtual(), "");

  // tty->print("move "); src->print(); tty->print(" to "); dest->print(); tty->cr();

  assert(src->is_valid(), "");

  assert(dest->is_valid(), "");

  ResolveNode* source = source_node(src);

  source->append(destination_node(dest));

}

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

// LIRItem

void LIRItem::set_result(LIR_Opr opr) {

  assert(value()->operand()->is_illegal() || value()->operand()->is_constant(), "operand should never change");

  value()->set_operand(opr);

  if (opr->is_virtual()) {

    _gen->_instruction_for_operand.at_put_grow(opr->vreg_number(), value(), NULL);

  }

  _result = opr;

}

void LIRItem::load_item() {

  if (result()->is_illegal()) {

    // update the items result

    _result = value()->operand();

  }

  if (!result()->is_register()) {

    LIR_Opr reg = _gen->new_register(value()->type());

    __ move(result(), reg);

    if (result()->is_constant()) {

      _result = reg;

    } else {

      set_result(reg);

    }

  }

}

void LIRItem::load_for_store(BasicType type) {

  if (_gen->can_store_as_constant(value(), type)) {

    _result = value()->operand();

    if (!_result->is_constant()) {

      _result = LIR_OprFact::value_type(value()->type());

    }

  } else if (type == T_BYTE || type == T_BOOLEAN) {

    load_byte_item();

  } else {

    load_item();

  }

}

void LIRItem::load_item_force(LIR_Opr reg) {

  LIR_Opr r = result();

  if (r != reg) {

    if (r->type() != reg->type()) {

      // moves between different types need an intervening spill slot

      LIR_Opr tmp = _gen->force_to_spill(r, reg->type());

      __ move(tmp, reg);

    } else {

      __ move(r, reg);

    }

    _result = reg;

  }

}

ciObject* LIRItem::get_jobject_constant() const {

  ObjectType* oc = type()->as_ObjectType();

  if (oc) {

    return oc->constant_value();

  }

  return NULL;

}

jint LIRItem::get_jint_constant() const {

  assert(is_constant() && value() != NULL, "");

  assert(type()->as_IntConstant() != NULL, "type check");

  return type()->as_IntConstant()->value();

}

jint LIRItem::get_address_constant() const {

  assert(is_constant() && value() != NULL, "");

  assert(type()->as_AddressConstant() != NULL, "type check");

  return type()->as_AddressConstant()->value();

}

jfloat LIRItem::get_jfloat_constant() const {

  assert(is_constant() && value() != NULL, "");

  assert(type()->as_FloatConstant() != NULL, "type check");

  return type()->as_FloatConstant()->value();

}

jdouble LIRItem::get_jdouble_constant() const {

  assert(is_constant() && value() != NULL, "");

  assert(type()->as_DoubleConstant() != NULL, "type check");

  return type()->as_DoubleConstant()->value();

}

jlong LIRItem::get_jlong_constant() const {

  assert(is_constant() && value() != NULL, "");

  assert(type()->as_LongConstant() != NULL, "type check");

  return type()->as_LongConstant()->value();

}

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

void LIRGenerator::init() {

  _bs = Universe::heap()->barrier_set();

}

void LIRGenerator::block_do_prolog(BlockBegin* block) {

#ifndef PRODUCT

  if (PrintIRWithLIR) {

    block->print();

  }

#endif

  // set up the list of LIR instructions

  assert(block->lir() == NULL, "LIR list already computed for this block");

  _lir = new LIR_List(compilation(), block);

  block->set_lir(_lir);

  __ branch_destination(block->label());

  if (LIRTraceExecution &&

      Compilation::current_compilation()->hir()->start()->block_id() != block->block_id() &&

      !block->is_set(BlockBegin::exception_entry_flag)) {

    assert(block->lir()->instructions_list()->length() == 1, "should come right after br_dst");

    trace_block_entry(block);

  }

}

void LIRGenerator::block_do_epilog(BlockBegin* block) {

#ifndef PRODUCT

  if (PrintIRWithLIR) {

    tty->cr();

  }

#endif

  // LIR_Opr for unpinned constants shouldn't be referenced by other

  // blocks so clear them out after processing the block.

  for (int i = 0; i < _unpinned_constants.length(); i++) {

    _unpinned_constants.at(i)->clear_operand();

  }

  _unpinned_constants.trunc_to(0);

  // clear our any registers for other local constants

  _constants.trunc_to(0);

  _reg_for_constants.trunc_to(0);

}

void LIRGenerator::block_do(BlockBegin* block) {

  CHECK_BAILOUT();

  block_do_prolog(block);

  set_block(block);

  for (Instruction* instr = block; instr != NULL; instr = instr->next()) {

    if (instr->is_pinned()) do_root(instr);

  }

  set_block(NULL);

  block_do_epilog(block);

}

//-------------------------LIRGenerator-----------------------------

// This is where the tree-walk starts; instr must be root;

void LIRGenerator::do_root(Value instr) {

  CHECK_BAILOUT();

  InstructionMark im(compilation(), instr);

  assert(instr->is_pinned(), "use only with roots");

  assert(instr->subst() == instr, "shouldn't have missed substitution");

  instr->visit(this);

  assert(!instr->has_uses() || instr->operand()->is_valid() ||

         instr->as_Constant() != NULL || bailed_out(), "invalid item set");

}

// This is called for each node in tree; the walk stops if a root is reached

void LIRGenerator::walk(Value instr) {

  InstructionMark im(compilation(), instr);

  //stop walk when encounter a root

  if (instr->is_pinned() && instr->as_Phi() == NULL || instr->operand()->is_valid()) {

    assert(instr->operand() != LIR_OprFact::illegalOpr || instr->as_Constant() != NULL, "this root has not yet been visited");

  } else {

    assert(instr->subst() == instr, "shouldn't have missed substitution");

    instr->visit(this);

    // assert(instr->use_count() > 0 || instr->as_Phi() != NULL, "leaf instruction must have a use");

  }

}

CodeEmitInfo* LIRGenerator::state_for(Instruction* x, ValueStack* state, bool ignore_xhandler) {

  int index;

  Value value;

  for_each_stack_value(state, index, value) {

    assert(value->subst() == value, "missed substition");

    if (!value->is_pinned() && value->as_Constant() == NULL && value->as_Local() == NULL) {

      walk(value);

      assert(value->operand()->is_valid(), "must be evaluated now");

    }

  }

  ValueStack* s = state;

  int bci = x->bci();

  for_each_state(s) {

    IRScope* scope = s->scope();

    ciMethod* method = scope->method();

    MethodLivenessResult liveness = method->liveness_at_bci(bci);

    if (bci == SynchronizationEntryBCI) {

      if (x->as_ExceptionObject() || x->as_Throw()) {

        // all locals are dead on exit from the synthetic unlocker

        liveness.clear();

      } else {

        assert(x->as_MonitorEnter(), "only other case is MonitorEnter");

      }

    }

    if (!liveness.is_valid()) {

      // Degenerate or breakpointed method.

      bailout("Degenerate or breakpointed method");

    } else {

      assert((int)liveness.size() == s->locals_size(), "error in use of liveness");

      for_each_local_value(s, index, value) {

        assert(value->subst() == value, "missed substition");

        if (liveness.at(index) && !value->type()->is_illegal()) {

          if (!value->is_pinned() && value->as_Constant() == NULL && value->as_Local() == NULL) {

            walk(value);

            assert(value->operand()->is_valid(), "must be evaluated now");

          }

        } else {

          // NULL out this local so that linear scan can assume that all non-NULL values are live.

          s->invalidate_local(index);

        }

      }

    }

    bci = scope->caller_bci();

  }

  return new CodeEmitInfo(x->bci(), state, ignore_xhandler ? NULL : x->exception_handlers());

}

CodeEmitInfo* LIRGenerator::state_for(Instruction* x) {

  return state_for(x, x->lock_stack());

}

void LIRGenerator::jobject2reg_with_patching(LIR_Opr r, ciObject* obj, CodeEmitInfo* info) {

  if (!obj->is_loaded() || PatchALot) {

    assert(info != NULL, "info must be set if class is not loaded");

    __ oop2reg_patch(NULL, r, info);

  } else {

    // no patching needed

    __ oop2reg(obj->encoding(), r);

  }

}

void LIRGenerator::array_range_check(LIR_Opr array, LIR_Opr index,

                                    CodeEmitInfo* null_check_info, CodeEmitInfo* range_check_info) {

  CodeStub* stub = new RangeCheckStub(range_check_info, index);

  if (index->is_constant()) {

    cmp_mem_int(lir_cond_belowEqual, array, arrayOopDesc::length_offset_in_bytes(),

                index->as_jint(), null_check_info);

    __ branch(lir_cond_belowEqual, T_INT, stub); // forward branch

  } else {

    cmp_reg_mem(lir_cond_aboveEqual, index, array,

                arrayOopDesc::length_offset_in_bytes(), T_INT, null_check_info);

    __ branch(lir_cond_aboveEqual, T_INT, stub); // forward branch

  }

}

void LIRGenerator::nio_range_check(LIR_Opr buffer, LIR_Opr index, LIR_Opr result, CodeEmitInfo* info) {

  CodeStub* stub = new RangeCheckStub(info, index, true);

  if (index->is_constant()) {

    cmp_mem_int(lir_cond_belowEqual, buffer, java_nio_Buffer::limit_offset(), index->as_jint(), info);

    __ branch(lir_cond_belowEqual, T_INT, stub); // forward branch

  } else {

    cmp_reg_mem(lir_cond_aboveEqual, index, buffer,

                java_nio_Buffer::limit_offset(), T_INT, info);

    __ branch(lir_cond_aboveEqual, T_INT, stub); // forward branch

  }

  __ move(index, result);

}

// increment a counter returning the incremented value

LIR_Opr LIRGenerator::increment_and_return_counter(LIR_Opr base, int offset, int increment) {

  LIR_Address* counter = new LIR_Address(base, offset, T_INT);

  LIR_Opr result = new_register(T_INT);

  __ load(counter, result);

  __ add(result, LIR_OprFact::intConst(increment), result);

  __ store(result, counter);

  return result;

}

void LIRGenerator::arithmetic_op(Bytecodes::Code code, LIR_Opr result, LIR_Opr left, LIR_Opr right, bool is_strictfp, LIR_Opr tmp_op, CodeEmitInfo* info) {

  LIR_Opr result_op = result;

  LIR_Opr left_op   = left;

  LIR_Opr right_op  = right;

  if (TwoOperandLIRForm && left_op != result_op) {

    assert(right_op != result_op, "malformed");

    __ move(left_op, result_op);

    left_op = result_op;

  }

  switch(code) {

    case Bytecodes::_dadd:

    case Bytecodes::_fadd:

    case Bytecodes::_ladd:

    case Bytecodes::_iadd:  __ add(left_op, right_op, result_op); break;

    case Bytecodes::_fmul:

    case Bytecodes::_lmul:  __ mul(left_op, right_op, result_op); break;

    case Bytecodes::_dmul:

      {

        if (is_strictfp) {

          __ mul_strictfp(left_op, right_op, result_op, tmp_op); break;

        } else {

          __ mul(left_op, right_op, result_op); break;

        }

      }

      break;

    case Bytecodes::_imul:

      {

        bool    did_strength_reduce = false;

        if (right->is_constant()) {

          int c = right->as_jint();

          if (is_power_of_2(c)) {

            // do not need tmp here

            __ shift_left(left_op, exact_log2(c), result_op);

            did_strength_reduce = true;

          } else {

            did_strength_reduce = strength_reduce_multiply(left_op, c, result_op, tmp_op);