/*

 * Copyright (c) 2005, 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 "c1/c1_Compilation.hpp"

#include "c1/c1_FrameMap.hpp"

#include "c1/c1_Instruction.hpp"

#include "c1/c1_LIRAssembler.hpp"

#include "c1/c1_LIRGenerator.hpp"

#include "c1/c1_ValueStack.hpp"

#include "ci/ciArrayKlass.hpp"

#include "ci/ciInstance.hpp"

#include "ci/ciObjArray.hpp"

#include "runtime/sharedRuntime.hpp"

#include "runtime/stubRoutines.hpp"

#include "utilities/bitMap.inline.hpp"

#include "utilities/macros.hpp"

#if INCLUDE_ALL_GCS

#include "gc_implementation/g1/heapRegion.hpp"

#endif // INCLUDE_ALL_GCS

#ifdef ASSERT

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

#else

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

#endif

// TODO: ARM - Use some recognizable constant which still fits architectural constraints

#ifdef ARM

#define PATCHED_ADDR  (204)

#else

#define PATCHED_ADDR  (max_jint)

#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 !defined(ARM) && !defined(E500V2)

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

      // moves between different types need an intervening spill slot

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

    }

#endif

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

  assert(state != NULL, "state must be defined");

#ifndef PRODUCT

  state->verify();

#endif

  ValueStack* s = state;

  for_each_state(s) {

    if (s->kind() == ValueStack::EmptyExceptionState) {

      assert(s->stack_size() == 0 && s->locals_size() == 0 && (s->locks_size() == 0 || s->locks_size() == 1), "state must be empty");

      continue;

    }

    int index;

    Value value;

    for_each_stack_value(s, index, value) {

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

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

        walk(value);

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

      }

    }

    int bci = s->bci();

    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() || x->as_ProfileInvoke(), "only other cases are MonitorEnter and ProfileInvoke");

      }

    }

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

        }

      }

    }

  }

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

}

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

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

}

void LIRGenerator::klass2reg_with_patching(LIR_Opr r, ciMetadata* obj, CodeEmitInfo* info) {

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

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

    __ klass2reg_patch(NULL, r, info);

  } else {

    // no patching needed

    __ metadata2reg(obj->constant_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);

}

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: